科创中国

提供一种确定数据点的相似度的方法，包括：(a)将所有数据点进行线性投影；(b)基于线性投影后的数据点来构建包括预定数量的具有预定深度的树的随机森林，其中，按照测试函数将随机森林的每个分割结点中的数据点分割到左孩子结点或右孩子结点；(c)获取每个数据点在每颗树上的分割路径；(d)根据获取的分割路径来确定数据点的哈希码，并根据确定的哈希码来确定数据点的相似度。在根据本发明示例性实施例的确定数据点的相似度的方法中，生成的哈希码的长度突破了原始数据点的维度的限制，比现有的哈希编码方法更加灵活，可以更好地应用于各种数据的相似性的比较。

一种确定数据点的相似度的方法，其特征在于，包括：(a)将所有数据点进行线性投影；(b)基于线性投影后的数据点来构建包括预定数量的具有预定深度的树的随机森林，其中，按照测试函数将随机森林的每个分割结点中的数据点分割到左孩子结点或右孩子结点；(c)获取每个数据点在每颗树上的分割路径；(d)根据获取的分割路径来确定数据点的哈希码，并根据确定的哈希码来确定数据点的相似度；针对随机森林的第s个分割结点中的第i个数据点，测试函数表示为如下定义的其中，表示随机森林的第s个分割结点中的第i个数据点的向量，和分别表示的第h1个分量和第h2个分量，sl和sr分别表示第s个分割结点的左孩子结点和右孩子结点，表示第s个分割结点中的所有数据点的di(h1,h2)的均值。

随着网络上大量的图像和其它媒介数据的产生，近似最近邻搜索变得越来越重 要。它现在已成为机器学习中最重要的问题之一，已经被用于许多计算机视觉任务，比如图 像检索。在这个领域内，基于哈希的近似最近邻是一个普遍被使用的方法。这种方法把高维 的数据点编码成紧凑的二值码，这些二值码保留了高维数据点的相似性，而且可以让内存 容下更大的数据集，同时能够实现高效率的相似性搜索。

[0003] 大量的用于学习相似性保留的二值码方法已经被提出。在这些方法中，位置敏感 哈希(LSH)是最流行的哈希编码方法之一，

中国科学院深圳先进技术研究院提升了粤港地区及我国先进制造业和现代服务业的自主创新能力，推动我国自主知识产权新工业的建立，成为国际一流的工业研究院。 深圳先进院目前已初步构建了以科研为主的集科研、教育、产业、资本为一体的微型协同创新生态系统，由九个研究平台，国科大深圳先进技术学院，多个特色产业育成基地、多支产业发展基金、多个具有独立法人资质的新型专业科研机构等组成。开展先进技术研究，促进科技发展。信息、电子、通讯技术研究新材料、新能源技术研究高性能计算、自动化、精密机械研究生物医学与医疗仪器研究相关学历教育、博士后培养与学术交流。

本发明的示例性实施例在于提供一种确定数据点的相似度的方法，以解决至少一 个上述的问题。在根据本发明示例性实施例的确定数据点的相似度的方法中，生成的哈希码的长 度突破了原始数据点的维度的限制，可以通过增加随机森林中树的数量或者增长树的深度 来扩展哈希码的长度，比现有的哈希编码方法更加灵活，可以更好地应用于各种数据的相 似性的比较。

技术合作

由于树形结构的使用，根据本发明示例性实施例的方法生成哈希码的速度非常 快，使用未优化的C++代码，生成一个查询点的哈希码大约花费0.1ms的时间。若使用现代 CPU上的并行处理，这个时间可以进一步缩短。分别使用512个、64个投影向量做投影运算大 约消耗Ims和0.1ms的时间。生成512-比特的二值码，根据本发明示例性实施例的方法生成 哈希码的时间大约为〇. 2ms，而LSH大约消耗了 Ims，根据本发明示例性实施例的方法比LSH 更尚效。

[0072] 应注意，本发明的以上各个实施例仅仅是示例性的，而本发明并不受限于此。本领 域技术人员应该理解:在不脱离本发明的原理和精神的情况下，可对这些实施例进行改变， 其中，本发明的范围在权利要求及其等同物中限定。