基于密度聚类的空间文本查询

发布时间：2020-09-30 14:41

　　近年来,基于位置服务的应用发展迅速。用户可以基于位置进行信息检索,从而得到更加符合现实需求的检索结果。作为基于位置的信息检索的基础,空间文本查询越来越受到学者的关注。在空间文本查询领域,学者提出了多种查询方式解决现实场景中的问题,但现有的查询方式鲜有考虑到周围兴趣点对返回结果的影响。基于Top-k空间文本聚集查询,本文提出了基于密度聚类的空间文本查询。该查询方式为用户返回符合密度要求的结果簇集,即为用户推荐符合查询条件且空间文本对象密集的区域。本文提出的查询方式解决了Top-k空间文本聚集查询中系统IO开销大和索引结构参数敏感等问题。该方法首先使用IR~2树索引结构对空间文本对象进行索引。然后,根据查询关键字和最大可接受距离对IR~2树进行搜索,并返回相关空间文本对象集。最后,使用基于密度的聚类算法对相关对象集进行聚类,并返回最终的结果簇集。这样可以避免对整个数据集进行遍历,降低了系统IO开销和查询时间。本文将IR~2树索引结构与传统的DBSCAN算法相结合,设计了基于DBSCAN的聚类空间文本查询算法。然而,DBSCAN算法时间复杂度高,影响查询效率。针对这一问题,本文提出了两种不同的改进算法:(1)基于规则的聚类空间文本查询改进算法。该算法使用规则策略减少了DBSCAN算法中对于核心对象的?邻域中对象的扩展数量,从而降低聚类时间。(2)基于快速DBSCAN的聚类空间文本查询改进算法。该算法根据用户输入的查询条件建立网格结构,并结合快速DBSCAN算法,降低了算法的时间复杂度。通过对IR~2树索引结构和本文查询方式的分析,本文发现搜索IR~2树时,可以去除掉包含明显异常对象的节点。针对这一问题,本文提出了基于剪枝策略的聚类空间文本近似查询算法。首先,本文通过增加IR~2树中签名文件的标志位改进了IR~2树索引结构。其次,本文设计了具体的剪枝策略,对改进后的IR~2树的搜索过程进行剪枝,实现了近似查询算法。近似查询算法对改进的IR~2树进行搜索时能在树的高层及时去掉包含明显异常对象的节点,降低了系统IO开销和IR~2树搜索时间。为了验证不同查询参数对各个算法运行时间和系统IO开销的影响,本文在两个不同规模的数据集上对本文所设计算法进行对比实验。实验结果表明,在相同实验条件下,基于快速DBSCAN的改进算法较本文其他精准算法相比效果最好。此外,本文提出的近似查询算法能够有效识别到包含异常对象的节点,并对其进行剪枝,进一步提升了算法性能。
【学位单位】：西安电子科技大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TP311.13;TP391.1
【部分图文】：

影响图,关键字,对象集,对相

西安电子科技大学硕士学位论文40图5.1 查询关键字个数对相关对象集和系统 IO 开销的影响图图5.2 查询关键字个数对精准算法的影响图图 5.2 展示了不同算法的运行时间与查询关键字数量之间的关系。实验表明，随着查询关键字个数的增多，搜索到的相关空间文本对象的数量在不断增加，各个算法的运行时间都有不同程度的增加，主要有如下两方面的原因：一是随着查询关键字数量的增多，在对IR2树搜索时需要遍历到更多的节点，增加了生成相关对象集的时间；二是相关对象集的增大，增加了对相关对象集进行基于密度聚类的时间。随着查询关键字个数的增加 Base 算法的运行时间增长幅度最大。因为当查询关键字个数多时，相关对象集中对象的密度会变大

影响图,关键字,影响图,相关对象

40图5.1 查询关键字个数对相关对象集和系统 IO 开销的影响图图5.2 查询关键字个数对精准算法的影响图图 5.2 展示了不同算法的运行时间与查询关键字数量之间的关系。实验表明，随着查询关键字个数的增多，搜索到的相关空间文本对象的数量在不断增加，各个算法的运行时间都有不同程度的增加，主要有如下两方面的原因：一是随着查询关键字数量的增多，在对IR2树搜索时需要遍历到更多的节点，增加了生成相关对象集的时间；二是相关对象集的增大，增加了对相关对象集进行基于密度聚类的时间。随着查询关键字个数的增加 Base 算法的运行时间增长幅度最大。因为当查询关键字个数多时，相关对象集中对象的密度会变大

对象集,对相,文本对象,相关对象

在使用基于密度聚类的空间文本查询方法时，用户可以输入指定的最大可接受距离 r，即返回的所有相关空间文本对象都在此区域内，避免了返回的结果簇集距离查询点过远用户难以接受的情况。如图5.3所示，随着用户输入最大可接受距离的增大，会有更多的相关对象产生。相比于查询关键字数量对相关对象集中对象数量的影响，最大可接受距离的影响较小。这是因为数据集中空间文本对象的密度固定，增大距离搜索到的相关对象集变化较小。同样随着最大可接受距离的增大，在对 IR2树搜索时需要访问更多的节点从而增加了系统的 IO 开销。最大可接受距离和查询关键字数量对系统 IO 开销的影响类似，在相同最大接受距离的情况下，雁塔区数据集的系统 IO开销大。图 5.4 展示了不同最大可接受距离对各算法运行时间的影响，各算法的运行时间增加主要有如下两方面的原因：首先是随着最大可接受距离的增大，对 IR2树中的节点搜索增加

【相似文献】