Probabilistic Top-k Query:Model and Application on Web Traffic Analysis

Top-k ranking of websites according to traffic volume is important for Internet Service Providers(ISPs) to understand network status and optimize network resources. However, the ranking result always has a big deviation with actual rank for the existence of unknown web traffic, which cannot be identified accurately under current techniques. In this paper, we introduce a novel method to approximate the actual rank. This method associates unknown web traffic with websites according to statistical probabilities. Then, we construct a probabilistic top-k query model to rank websites. We conduct several experiments by using real HTTP traffic traces collected from a commercial ISP covering an entire city in northern China. Experimental results show that the proposed techniques can reduce the deviation existing between the ground truth and the ranking results vastly. In addition, we find that the websites providing video service have higher ratio of unknown IP as well as higher ratio of unknown traffic than the websites providing text web page service. Specifically, we find that the top-3 video websites have more than 90% of unknown web traffic. All these findings are helpful for ISPs understanding network status and deploying Content Distributed Network(CDN).

基于概念邻近度的本体映射重用

为减少映射查找时相似度的冗余计算,改善映射查找效果,提出了一种通过考察待查概念与已有映射概念之间的邻近度,来推断待查概念映射关系的映射重用算法。构建概念描述概要间的语义二分图联系,从最佳匹配的角度,计算已有映射中概念与待查概念间的邻近程度,以已有映射中概念的邻近概念具有相似映射关系为前提,根据概念间相似度传递性决定待查概念间的映射关系。实验结果表明,该映射重用算法明显改善了映射查找的效果。

基于聚类与二分图匹配的语义Web服务发现

为高效准确地查找语义Web服务,引入聚类与二分图匹配技术,提出一种新的语义Web服务发现方法。根据服务描述信息将相似服务聚集到一起,采用空间向量模型表示服务,针对标准K-Means算法的缺陷设计基于k值优化和粒子群优化的K-Means聚类算法对服务进行聚类。借鉴带权二分图最优匹配思想对服务的功能属性进行匹配,设计基于Word Net的概念间语义相似度计算方法用于计算二分图的权值,并针对如何构建满足最优匹配条件的带权二分图问题给出解决方案。实验结果表明,该方法在查全率和匹配效率上均优于OWLS-MX方法。

混合语义相似度计算优化模糊查询的智能信息检索算法

针对搜索引擎领域存在的因查询条件模糊而严重影响信息检索性能的问题,提出了一种混合语义相似度优化模糊查询算法。首先,根据相似度计算概念提出了与其接近的新概念提取方法;然后,利用TF-IQF模型将链接划分成标记,并使用这些标记组成的集合表示出查询;最后,构建二分图识别出相关的查询,使用二分图计算出查询相似度。实验结果表明,相比点击文档、相关查询和反向查询三种算法,取得了更好的全查率、检索精度及F-度量。

利用二部图生成概念格

概念格作为一种有效的知识发现与数据处理的工具,在许多领域得到了广泛应用,概念格的构造在其应用中具有重要的意义。每个概念格的形式背景都可以对应一个二部图,本文通过二部图的极大完全子图的概念来生成概念格,给出了基于二部图的深度优先的概念格的迭代算法。首先,对形式背景进行必要的约简;其次,利用二部图的极大完全子图得到顶层概念的直接子概念;最后,通过求二部图的导出子图来简化形式背景,并得出每个概念的直接子概念和所有子概念,从而生成概念格。

利用二元拟阵K_n图的一种建格方法

由于交通网络纷繁复杂,难以直观分析和直接处理。若出行者根据自己喜好和习惯决定出行策略,则需对出行方案有清楚的了解。针对此问题,建立交通网络图——K_n模型,对具有带环路和重边路的复杂网络结构图,可以完全转化为K_n图处理。通过概念格理论,得到Hasse示图,方便人们对某些属性条件方案的提取,便于后续工作处理。对K_n图进行研究之后发现,在特定的多个属性影响下,会形成一个三角形圈,于是结合拟阵中二元拟阵的标准矩阵的定义,挖掘出一种特殊形式背景。根据这种形式背景的特殊性,给出基于二元拟阵的K_n图的概念格算法。结合生活中的例子,验证该算法可行性。由于模型具有这种普遍性,所有结果可推广到具有类似形式背景的其他领域研究中。

数据库汉语查询系统中隐含知识查询的研究

该文讨论了目前现有数据库汉语查询系统中的存在问题,根据关系数据库中数据表示与自然语言(汉语)查询句的语义模型不同,提出了数据库汉语查询时隐含知识的查询,对数据库中的隐含知识以概念图来表示,从而建立了自然语言和数据库查询命令SQL语言的直接联系。实现了这种数据库隐含知识查询的实验系统,从一定程度上提高了数据库汉语查询的智能性。

基于概念图的信息检索的查询扩展模型

针对传统的基于关键词匹配的信息检索存在的查全率和精确率不高的问题,提出一种基于概念图匹配的查询扩展方法:一方面通过知网对用户查询的词或者句子进行扩展后,将用户查询和文档生成概念图;另一方面利用概念图的不完全匹配和语义相似度的计算方法计算概念图的相似度,以提高检索效果。实验结果表明该方法取得了良好的效果。

弦二部图的概念格表示

本文首先讨论了二部图中双单纯边与概念格中概念之间的对应关系;其次研究了弦二部图和约简的形式背景的若干性质;最后将概念格中元素的消除理论应用于二部图的研究,给出了弦二部图的概念格刻画.结果表明,一个二部图是弦二部图当且仅当对应的概念格中有一个∨∧—不可约元的完美消除序列.

基于朴素贝叶斯点击预测的查询推荐方法

查询推荐作为一种改善用户查询体验和效率的重要方式,可以帮助用户筛选并提供更加准确的查询描述。目前很多查询推荐方法主要集中在热门推荐或是基于相似度匹配的推荐上,忽略了用户的查询意图,无法有效提供个性化推荐。为此,基于对用户查询点击日志进行分析与挖掘,训练出一个朴素贝叶斯模型,针对用户输入的查询,根据历史数据预测其与URL的点击率,再利用二分图将URL的预测点击值平均分配给相对应的每个查询项,最后结合Jaccard相似度和时间相关因子综合分析用户当前输入的查询与历史中查询的相关度,并给出推荐。实验证明了该方法的可行性并取得了较好的推荐效果。

基于查询-概念的用户兴趣模型构建

针对查询-概念二分图因概念抓取和查询词权重设计不足而导致构建的用户兴趣模型不合理的问题,提出一种基于查询-概念二分图的用户兴趣建模算法。通过tf×idf公式抓取概念,并利用用户对查询词的浏览时间计算查询词的权重,确保改进后的查询-概念二分图能更准确地表示用户的查询意图。实验结果表明,该算法构建的用户兴趣更为合理。

偶查询优化的图论方法

本文针对一类特殊的多关系查询——偶查询,提出了一种建立在图论偶图和匹配理论基础上的查询优化方法,这种方法具有多项式复杂性。

基于二部图半监督方法的查询日志实体挖掘

基于用户查询日志的命名实体挖掘的目标是从用户查询日志中挖掘一组具有指定类别的命名实体。为解决已有用户查询日志实体挖掘研究工作中的种子实体不充分的问题,提出了一种基于二部图的半监督排序方法,利用实体之间的关系(实体共享查询模板)来改善实体排序效果。该方法首先基于候选实体和查询模板构建一个二部图,然后基于二部图将种子实体的类别相关性传播到其他候选实体,最后按照类别相关性得分对候选实体进行排序,并进一步给出方法中迭代过程的等价优化框架。实验结果表明本文提出的方法优于基准方法,具有较好的挖掘效果。