相似性搜索中的近似算法研究

《相似性搜索中的近似算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、相似性搜索中的近似算法研究（申请清华大学工学博士学位论文）培养单位：计算机科学与技术系学科：计算机科学与技术研究生：蒋琪夏指导教师：孙茂松教授二〇一二年四月ResearchonApproximateSimilaritySearchDissertationSubmittedtoTsinghuaUniversityinpartialfulfillmentoftherequirementforthedegreeofDoctorofPhilosophyinComputerScienceandTechnologybyJiangQixiaDissertatio

2、nSupervisor:ProfessorSunMaosongApril,2012关于学位论文使用授权的说明本人完全了解清华大学有关保留、使用学位论文的规定，即：清华大学拥有在著作权法规定范围内学位论文的使用权，其中包括：（1）已获学位的研究生必须按学校规定提交学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的学位论文；（2）为教学和科研目的，学校可以将公开的学位论文作为资料在图书馆、资料室等场所供校内师生阅读，或在校园网上供校内师生浏览部分内容；（3）根据《中华人民共和国学位条例暂行实施办法》，向国家图书馆报送可以公开的学位论文。本

3、人保证遵守上述规定。（（（保保保密密密的的的论论论文文文在在在解解解密密密后后后应应应遵遵遵守守守此此此规规规定定定）））作者签名：导师签名：日期：日期：摘要摘要相似性搜索是指对于给定样本对象，在对象集合中查找与之内容最相似的对象的技术。如何快速地进行相似性搜索一直是研究的热点和难点。目前主流的方法是使用基于数字指纹的近似搜索策略以达到平衡搜索效率与搜索效果的目的。这类近似算法的主要思想是利用指纹函数将数据表示成固定长度的二进制数字指纹，指纹间的差异程度反映了数据对象在原始空间中的相似程度，从而将原始空间中的搜索问题转换为指纹的匹配问题。然而，现

4、有的近似搜索算法往往因为数据对象的指纹不够紧凑而效率低下。本文从提高相似性搜索中近似算法的效率和效果入手开展了研究工作。论文工作包括：提出了基于数据对象内部信息和类别信息，利用有监督学习算法构建指纹函数的算法，进行近似搜索。该方法依靠数据对象内部信息度量对象间的相似度，同时利用类别信息作为约束，构建指纹函数，进行近似搜索。实验证明，该方法能够有效地为同一类别下数据对象生成相似的数字指纹，提高了相似性搜索的效率和效果。提出了基于数据对象外部信息，利用有监督隐含主题模型构建主题的近似搜索算法。针对相似性度量受限于数据对象内部信息不足以及噪声问题，提出

5、利用有监督隐含主题模型构建对象主题，进行基于主题的近似搜索。并针对基于变分法的有监督隐含主题模型不准确的问题，提出基于蒙特卡罗法的有监督隐含主题模型。文本近似搜索的实验证明该算法能更准确地构建文本主题，并有效提升相似性搜索性能。针对现有数据无关的指纹函数对数据空间分布敏感的问题，设计了基于空间数据分析的指纹函数，进行近似搜索。该方法同时利用了数据对象在原始空间中的相似度和整个数据集合在空间中的分布来构建指纹函数，从而进行近似搜索。实验证明，该方法能够有效地综合数据对象间的相似度信息以及数据集的分布信息，一定程度上提升了病态分布数据的相似性搜索性能

6、。提出了基于数据聚类结果构建指纹函数的算法，进行近似搜索。针对数据自身内部信息缺失严重的问题，提出利用层次聚类对数据进行聚类，聚类结果指导指纹函数的构建，进行近似搜索。实验证明该方法能更好地构建指纹函数，有效进行相似性搜索。关键词：相似性搜索；近似算法；近似搜索；指纹函数；数字指纹IAbstractAbstractSimilaritysearchistofindarelevantobjecttothequeryinadatasetorontheweb.Similaritysearchplaysanimportantroleinmoderninfor

7、mationretrieval,patternrecognition,etc.Recently,fingerprint-basedApproximateSimilaritySearch(ANN)hasbeenwidelyusedinreal-worldapplicationstobalancethesearchaccuracyandsearchefficiency.Thiskindofapproachuseshashfunctiontomapanobjecttosmallbinaryvaluesofafixedlength,knownasfingerpri

8、nt.Thedifferencebetweenfingerprintswellreflectsthesimilarityofobjectsin