论文部分内容阅读
随着大数据时代的到来以及数据处理量的日益增加,在大规模数据中进行数据搜索,数据查找已经变得越来越重要。最近邻搜索是数据检索中的常规操作,因此得到了广泛关注。从目前来看,最为经典的最近邻搜索算法是位置敏感哈希算法(Location sensitive hash,简称LSH)。位置敏感哈希算法有着严格的理论证明,算法实现简单,具有稳定的概率保证。然而LSH没有充分利用数据集的分布信息,在维度较高的数据集中,LSH的查询效果下降非常明显。为了充分利用数据集的分布信息和提高查询效果,很多学者提出基于学习的哈希算法。基于学习的哈希算法通过训练将数据集进行分区或者提取数据集的主要成分,例如数据导向型位置敏感哈希算法(Data-Oriented Locality Sensitive Hashing,简称DSH)结合主成分分析法(Principal Component Analysis,简称PCA)和位置敏感哈希来解决最近邻查找问题。然而,DSH算法的成功率没有严格的理论保证。最近的一篇理论论文里提出迭代PCA方法。迭代PCA方法反复的对数据集进行PCA,理论证明迭代次数是有限的。然而,迭代PCA方法的参数难以确定,点到空间的距离定义不合理,算法实现复杂。为了达到充分利用数据集的分布信息、算法实现简单、严格的理论保证这三个目的,本文结合DSH算法和迭代PCA方法的优点提出迭代PCA哈希算法。本文的主要研究内容及贡献如下:首先,本文提出迭代PCA哈希算法。具体包括,通过解决迭代PCA方法参数难以设定,点到空间的距离定义不合理两大难题,借鉴迭代PCA方法的理论证明和DSH算法的实现方法,提出迭代PCA哈希算法。理论分析了迭代PCA哈希算法点到空间定义的可行性和迭代次数的有限性。其次,通过实验验证迭代PCA哈希算法查询效果良好。具体包括,运用python实现LSH算法、DSH算法和迭代PCA哈希算法。通过实验结果分析得出(1)在遍历相同候选点的前提下,迭代PCA哈希算法较LSH算法和DSH算法查询精度高。(2)迭代PCA哈希算法不存在奇异点(0,0),表明数据集经迭代PCA哈希算法投影后分布更加稠密,均匀。(3)迭代PCA哈希算法实验结果更快的收敛到较高精度位置,减少寻找合适阈值w的时间开销。