针对搜索结果的位图表示及聚类算法改进研究

发布时间：2020-10-09 08:48

　　 网络科技和搜索技术的迅猛发展使得人们越来越多地通过互联网和搜索引擎获取信息,搜索结果种类多、排列乱是影响用户快速获取有效信息的重要因素。为提高用户获取有效信息的速度、改善用户的搜索体验,聚类分析技术被广泛应用到搜索结果中。目前,针对搜索结果聚类的大部分研究集中于聚类方式,忽略了搜索结果的表示方法对聚类效果和收敛速率的影响;此外,常用于搜索结果聚类的K-means算法的聚类效果和收敛速率受初始聚类中心影响较大,而当前关于初始聚类中心的研究仍然存在一些不足。基于此,本文从搜索结果的表示方法和初始聚类中心的选择两个方面展开研究,具体完成了以下几项工作:(1)针对向量空间模型存在文本相似度计算耗时以及存储空间需求较大的问题,本文结合向量空间模型和布尔模型各自的优点提出了基于位图的文本表示方法表示搜索结果。该方法先用向量空间模型将搜索结果表示成特征向量,然后将特征权重转换为对应的布尔值,最后以位为单位存储布尔值形成位图特征向量。实验结果表明,本文提出的位图文本表示方法可以有效的提高搜索结果的文本相似度计算速率,同时减少特征矩阵所需的存储空间。(2)针对K-means算法随机选择初始聚类中心导致算法不可重复实现,同时可能使算法陷入局部最优解、减缓算法收敛速率的问题,本文提出了基于悲观准则和近邻算法的初始聚类中心选择算法。通过悲观准则选择K个相距最远的数据作为备选初始聚类中心,然后寻找各个备选初始聚类中心的近邻簇,最后以各个近邻簇的中心作为初始聚类中心。实验结果表明,本文提出的基于悲观准则和近邻算法的初始聚类中心选择算法可以有效的提高K-means算法的聚类效果和收敛速率,同时保证了算法的稳定性。(3)针对现有聚类搜索引擎产品存在的问题,本文设计并实现了一个基于本文研究成果的聚类搜索引擎原型系统。该原型系统实现了搜索结果获取、预处理、特征表示、初始聚类中心选择、聚类以及搜索结果展示等功能。其运行效果表明,将本文研究成果应用到搜索结果聚类中,能够有效地提高用户获取信息的效率,改善用户的使用体验,同时为将来类似的聚类搜索引擎系统的研发提供了借鉴参考。
【学位单位】：武汉理工大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP391.3
【部分图文】：

21（c）数据集 Clustering 的聚类结果图 2-4 不同参数下的聚类结果4 中每条曲线的交点为一组 α、β 得到的 DBI 值。从 yz 方向重要度 α 相同的情况下，随着特征转换阈值 β 的增长，其原因是：当 β 较小时，所有特征的特征值都为 1，这会低，导致特征向量无法准确的表示搜索结果，聚类效果必可以提高聚类效果、降低 DBI 值；但如果 β 较大，特征向征才能表达，丢失了很多表示搜索结果的特征，这会使聚当 β 达到某个阈值，继续增大 β 会降低聚类效果、增大 方向可以观察到在特征转换阈值 β 相同的情况下，随着标

24（c）数据集 Clustering 的聚类耗时图 2-6 不同文本表示方法的聚类耗时从图 2-6 可以看出，在相同的数据集中，VSM 文本表示方法聚类耗时比 BM和 BTM 两种文本表示方法聚类耗时长。分析原因主要是 VSM 采用普通的四则混合运算计算相似度，而 BM 和 BTM 均是采用计算速率比四则混合运算快的布尔逻辑运算计算相似度。从图中还可以看出，BTM 比 BM 聚类耗时少，其中一个原因是 BTM 表示的特征向量进行了压缩，所以需要计算的长度比 BM 少；另一个原因是 BTM 文本表示方法对搜索结果表示的更加准确，这样 K-means 算法在迭代过程中，迭代的次数会相应减少，聚类速率相应提高。从图 2-6 还可以看出，随着数据量的增大（三组数据集的数据量从小到大依

图 3-1 定义 3.3 的实例 3-1 中 A1、A2、A3属于集合 A，B1、B2、B3属于集合 B。为了求出 A 的最大距离，首先求出 B 中每个点到集合 A 的最小距离，比如 B1到集合 A 中各个点的距离为红色连线段的长度，其中红色虚线度最小，即点 B1到集合 A 的最小距离为线段 A1B1的长度。同理， A 的最小距离分别为黑色虚线 A2B2、蓝色虚线 A2B3线段的长度，虚线段的长度，找到三条虚线段长度的最大值，即图 3-1 中黑色加2。因此集合 B 到集合 A 的最大距离是点 B2到点 A2的距离，而 B2使集合 B 到集合 A 最大距离成立的数据点。 PC 算法满足初始聚类中心第一准则证明C 算法是为了满足初始聚类中心第一准则的要求提出的，为验证算本节需要证明 PC 算法中所有涉及到初始聚类中心选择的步骤都满心第一准则的要求。PC 算法中包含初始聚类中心选择的步骤有步

【相似文献】

相关期刊论文 前10条

1 曹宇;尹刚;李翔;程荣斌;王怀民;;聚类搜索引擎研究进展浅析[J];电脑知识与技术;2011年22期

2 黄建年;侯汉清;;聚类搜索引擎探究[J];图书馆学研究;2009年01期

3 苏建华;张灿;;聚类搜索引擎研究[J];新世纪图书馆;2009年06期

4 袁津生;程超然;;基于文本聚类搜索引擎的查询扩展算法[J];计算机工程与应用;2012年03期

5 王倩;;文档聚类技术在搜索引擎中的应用研究[J];图书馆学研究;2008年11期

6 靖培栋;田亮;;聚类在搜索引擎中的应用[J];情报理论与实践;2006年04期

7 卢希;;聚类搜索在电子商务中的应用研究[J];科技信息;2012年24期

8 周鸿;朱东华;董萍萍;;聚类搜索引擎研究进展综述[J];计算机系统应用;2012年05期

9 苍宏宇;谭宗颖;;聚类搜索引擎发展现状研究[J];图书情报工作;2009年02期

10 王佳乐;;搜索引擎的文本聚类研究[J];商业经济;2014年03期

相关会议论文 前1条

1 李斌;曲维光;陈小荷;;名词转喻的自动理解[A];中国计算机语言学研究前沿进展（2007-2009）[C];2009年

相关硕士学位论文 前9条

1 陈腊生;针对搜索结果的位图表示及聚类算法改进研究[D];武汉理工大学;2018年

2 陈飞;聚类搜索引擎关键技术的研究[D];北京邮电大学;2011年

3 陈平;中文聚类搜索引擎中主要技术的研究[D];吉林大学;2009年

4 程超然;基于文本聚类搜索引擎查询扩展算法的研究与实现[D];北京林业大学;2012年

5 玉兆辉;基于MapReduce的分布式聚类搜索引擎设计与实现[D];电子科技大学;2014年

6 谢红伟;基于Nutch的聚类搜索引擎的研究与实现[D];华南理工大学;2013年

7 罗克刚;基于自组织映射的文本聚类研究[D];哈尔滨工业大学;2007年

8 戴雪梅;面向购物的聚类搜索引擎的研究与实现[D];北京交通大学;2011年

9 郭峰;面向行业搜索引擎的WEB文本挖掘技术研究[D];兰州大学;2006年

本文编号：2833495