关键词: 单词移动距离, 推土机距离, 局部敏感哈希, 近似[k]近邻, 层次化查询

Abstract:

Recently, a good metric, word mover's distance (WMD) has been proposed to measure document similarity, which combines the Word2Vec model and computes the distance between two documents by earth mover's distance (EMD). However, it has two drawbacks. Firstly, it takes imprecise term frequency as word weight. Secondly, the existing query method is extremely inefficient under WMD metric. In order to increase the accuracy of document applications when using WMD, TF-IDF (term frequency-inverse document frequency) is taken as word weight and an improved WMD(TI-WMD) is achieved. To improve the efficiency of document query under WMD metric, this paper proposes an approximate hierarchical query mehod(HQ). First of all, according to word centroid vector of every document, it constructs the indexes for the document data set by locality-sensitive hashing(LSH). In the query process, it achieves a candidate document set according to the word centroid of the query document and multi-probe LSH query method. And then, on the basis of the document signature and the filter-and-refinement frame, it can obtain the approximate k nearest neighbor under TI-WMD metric. The empirical study over Reuters-21578 and 20-Newsgroups data sets demonstrates the superior accuracy and efficiency of TI-WMD metric and the hierarchical query method, compared with WMD and PrefetchPrune under WMD metric.

Key words: word mover's distance, earth mover??s distance, locality-sensitive Hashing, approximate k nearest neighbor, hierarchical query