一种基于改进LSH的多特征文档检索方法

摘要

本发明提出一种基于改进LSH的多特征文档检索方法。首先，将文档的关键字，标题，作者信息，更新时间和检索次数作为特征量，将这些特征量转换成距离并利用TF-IDF(Term？Frequency–Inverse？Document？Frequency)方法对每个距离设置权重。其次，将以上加权后的距离求和得到综合距离，通过综合距离的大小排序来选择回收最近邻数据。该方法将文档的多个特征量综合考虑，应用改进的LSH(Locality-Sensitive？Hashing)算法，实现快速检索的同时提高了检索的准确性。

说明书

技术领域

本发明涉及文档检索的技术领域，尤其涉及一种基于改进LSH的多特征 文档检索方法。

背景技术

随着知识信息化的快速发展，信息技术极大的影响了人们的生活方式。互 联网使得信息的获取，传播以及积累的速度和规模达到了前所未有的地步，实 现了世界信息的共享与交互。随着因特网的不断建设和完善，网络带宽的不断 增加，需要用各种方法对大量的知识信息进行管理，例如检索方法，以用来提 高生活水平和发展生产力。

近几十年来，有越来越多的文档检索方法。有基于局部敏感哈希 (Locality-SensitiveHashing，LSH)的检索方法，有基于内容的图像格式中文 文档检索方法，有基于文档结构的文档检索方法，也有考虑文档中的数值数据 的相似度的文档检索方法。但是，它们都只结合了文档的一个或两个因素，并 不能多方面综合。因此，检索结果不能令使用人满意。

LSH(Locality-SensitiveHashing)对于特征丰富的数据转换而成的高维数 据，它是一个相当有效的索引构建和搜索方法。利用哈希表中数据点的出现次 数来近似数据点与查询点的距离来对从哈希表中回收的数据进行排序，从而节 省了计算距离的时间以及减少了排序的时间，因此改善了LSH (Locality-SensitiveHashing)的时间效率，可以提高检索时间。但是，该方法 也因此降低了在回收同等数量的数据情况下的搜索的质量。

综上，对于现在已经出现的文档检索的方法，它们的计算方法繁重，检索 时间长。

发明内容

本发明旨在至少解决现有技术中存在的技术问题，特别创新地提出了一种 基于改进LSH的多特征文档检索方法。

为了实现本发明的上述目的，本发明提供了一种基于改进LSH的多特征 文档检索方法，包括如下步骤：

S1，对多特征文档数据库构造哈希表，存储数据索引，接受用户输入的查 询内容，根据查询内容获取查询点；

S2，对于查询点周围的数据点所对应的文档，进行特征量提取，将提取的 特征量转换成为查询点之间的距离量；

S3，对特征量通过TF-IDF算法设置该特征量的权重；

S4，对设置完成权重的特征量进行综合距离判断，依次从最小到最大的顺 序，对综合距离的数据进行回收处理，获取若干最近邻的查询数据。

所述的基于改进LSH的多特征文档检索方法，优选的，所述S1包括：

S1-1，设置多特征文档数据库组成的数据集为X，设置哈希表的数目为L；

S1-2，每个哈希表包含r个随机生成的哈希函数；

S1-3，对随机生成的哈希函数存储该数据的索引信息。

所述的基于改进LSH的多特征文档检索方法，优选的，所述S1中构造哈 希表包括：

当前数据库中的文档特征组成的数据集为X，L是哈希表数目，每个哈希 表包含r个随机生成的哈希函数；

A，对多特征文档的每种特征进行汉明空间转换，将X映射到汉明空间上。

B，选取合适的参数L、r、W，初始化哈希函数族H＝{h1，...，hL}，计算 特征在索引中的位置，每个哈希函数的值由下式决定，

$h_{a,b}=\frac{a\times v+b}{W},$

其中，a和b服从高斯随机分布，v是数据库中的文档的特征向量，W为 哈希表宽度，计算后得到哈希函数族：

$g\left(v\right)=\left(h_{a_1,b_1}\right(v),\mathrm{...},h_{a_r,b_r}(v\left)\right);$

C，利用计算后的哈希函数，将相应的特征存入相应的哈希表项。

所述的基于改进LSH的多特征文档检索方法，优选的，所述S2包括：

对于若干数据点所对应的多特征文档，该文档的关键字C₁，标题C₂，作者 信息C₃，更新时间C₄和检索次数C₅进行特征量提取，从而将这些特征量转换 成与查询点q间的距离，即C_s＝D_s(x_i,q),s＝1,2,3,4,5,i＝1,2,…,k，其中k为数 据点的个数且为正整数，对于文档的关键字，标题，作者信息， D₁(x,q),D₂(x,q),D₃(x,q),采用汉明距离；对于更新时间，D₄(x,q)等于用户查询时 刻与文档更新时刻的差值；对于检索次数，D₅(x,q)即为数据库记录的检索次数。

所述的基于改进LSH的多特征文档检索方法，优选的，所述S3的特征量 权重包括：

关键字特征量的权重：

$w_1=e^{{\mathrm{tf}}_{q,C_1}}\times {\mathrm{idf}}_{C_1}=e^{\frac{{\alpha }_q\times {\beta }_q}{{\tau }_{C_1}}}\times \log (\frac{N}{n}+0.01)\times 0.2$

其中，w₁为查询点q在关键字C₁中的权重；为查询点q在关键字中出 现的词频；为逆文档频率；α_q为查询点q在关键字中出现的次数，β_q为查 询点q的字数，为目前文档关键字的总字数；N为数据库中总文档数，n为 数据库中出现查询点q的文档数。

所述的基于改进LSH的多特征文档检索方法，优选的，所述S3的特征量 权重包括：

标题特征量的权重：

$w_2=e^{{\mathrm{tf}}_{q,C_2}}\times {\mathrm{idf}}_{C_2}=e^{\frac{{\alpha }_q\times {\beta }_q}{{\tau }_{C_2}}}\times \log (\frac{N}{n}+0.01)\times 0.2$

其中，w₂为查询点q在标题C₂中的权重；为查询点q在标题中出现 的词频；为逆文档频率；α_q为查询点q在标题中出现的次数，β_q为查询点 q的字数，为目前文档标题的总字数；N为数据库中总文档数，n为数据库 中出现查询点q的文档数。

所述的基于改进LSH的多特征文档检索方法，优选的，所述S3的特征量 权重包括：

作者特征量的权重：

$w_3=e^{{\mathrm{tf}}_{q,C_3}}\times {\mathrm{idf}}_{C_3}=e^{\frac{{\alpha }_q\times {\beta }_q}{{\tau }_{C_3}}}\times log(\frac{N}{n}+0.01)\times 0.2$

其中，w₃为查询点q在作者C₃中的权重；为查询点q在作者中出现 的词频；为逆文档频率；α_q为查询点q在作者中出现的次数，β_q为查询点 q的字数，为目前文档作者的总字数；N为数据库中总文档数，n为数据库 中出现查询点q的文档数。

所述的基于改进LSH的多特征文档检索方法，优选的，所述S3的特征量 权重包括：

更新时间、检索次数的权重：

因为要满足所有特征量的权重相加为1，故

$w_4=w_5=\frac{1-w_1-w_2-w_3}{2}$

其中，w₁为查询点q在关键字C₁中的权重；w₂为查询点q在标题C₂中的权 重；w₃为查询点q在作者C₃中的权重；w₄为查询点q在更新时间C₄中的权重； w₅为查询点q在检索时间C₅中的权重。

所述的基于改进LSH的多特征文档检索方法，优选的，所述S4包括：

S4-1，在设置特征量的权重过程中设置阈值，判断更新时间和检索次数的 权重是否超过阈值；若超过阈值，则进行S4-2；若没超过阈值，则进行S4-3；

S4-2、对关键字，标题，作者信息，更新时间和检索次数重新设置权重值， 再进入S4-3；

S4-3、将设置完成权重的特征量进行综合距离判断。

所述的基于改进LSH的多特征文档检索方法，优选的，所述S4的综合距 离计算包括：

将以上设置好权重的特征量按照以下方式进行处理：

$D_i=\underset{m=1}{\overset{4}{\Sigma }}{w}_m{C}_m-w_5{C}_5,$i＝1,2,…,k

其中，D_i为数据点x_i与查询点q间的综合距离；w_m为各特征量对应的权 重值；C_m为各特征量转换后的距离；k为数据点的个数且为正整数；D_i越小， 则表明该数据点距查询点越近，更符合检索要求。

综上所述，由于采用了上述技术方案，本发明的有益效果是：

首先，本发明将文档的关键字，标题，作者信息，更新时间和检索次数等 特征综合起来考虑，有效提高了检索的准确性。

其次，本发明针对LSH算法提出了一种改进的距离度量方法——将文档 的多个特征加权转换为综合距离，通过综合距离的大小排序来选择回收最近邻 数据，实现快速检索的同时提高了检索的准确性。

本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描 述中变得明显，或通过本发明的实践了解到。

附图说明

本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中 将变得明显和容易理解，其中：

图1是本发明总体流程图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自 始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元 件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能 理解为对本发明的限制。

在本发明的描述中，需要理解的是，术语“纵向”、“横向”、“上”、“下”、“前”、 “后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”“内”、“外”等指示的方位或位 置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描 述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位 构造和操作，因此不能理解为对本发明的限制。

在本发明的描述中，除非另有规定和限定，需要说明的是，术语“安装”、 “相连”、“连接”应做广义理解，例如，可以是机械连接或电连接，也可以是两 个元件内部的连通，可以是直接相连，也可以通过中间媒介间接相连，对于本 领域的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。

如图1所示，步骤1、构造哈希表，假设当前数据库中的文档特征组成的 数据集为X。L是哈希表数目，每个哈希表包含r个随机生成的哈希函数，存 储数据索引。

步骤2、接受用户输入的查询内容，获取查询点q。

步骤3、获得查询点附近的k个数据点x_i(i＝1,2,…,k)。

步骤4、对于k个数据点所对应的文档，将每个文档的以下特征：文档的 关键字C₁，标题C₂，作者信息C₃，更新时间C₄和检索次数C₅进行特征量提取， 从而将这些特征量转换成与查询点q间的距离，即 C_s＝D_s(x_i,q),s＝1,2,3,4,5,i＝1,2,…,k。对于文档的关键字，标题，作者信息， D₁(x,q),D₂(x,q),D₃(x,q),采用汉明距离；对于更新时间，D₄(x,q)等于用户查询时 刻与文档更新时刻的差值；对于检索次数，D₅(x,q)即为数据库记录的检索次数。

步骤5、利用TF-IDF(TermFrequency–InverseDocumentFrequency)算法 对文档的关键字，标题，作者信息，更新时间和检索次数等特征量C_s分别设置 权重w_s，s＝1，2，3，4，5。

步骤6、对更新时间和检索次数的权重设置一个阈值，并判断更新时间和 检索次数的权重值是否超过阈值；若超过阈值，则进行步骤7；若没有，则进 行步骤8。

步骤7、对关键字，标题，作者信息，更新时间和检索次数重新设置权重 值，再进入步骤8。

步骤8、将以上设置好权重的特征量按照以下方式进行处理：

$D_i=\underset{m=1}{\overset{4}{\Sigma }}{w}_m{C}_m-w_5{C}_5,$i＝1,2,…,k

其中，D_i为数据点x_i与查询点q间的综合距离；w_m为各特征量对应的权重 值；C_m为各特征量转换后的距离；k为数据点的个数且为正整数。D_i越小，则 表明该数据点距查询点越近，更符合检索要求。

步骤9、按照数据点的综合距离，将其从小到大依次排序，然后从综合距 离最小的数据开始回收，直到获得K个最近邻数据。

本实施方式中在步骤1中，哈希表的构造方法具体如下：

假设当前数据库中的文档特征组成的数据集为X。L是哈希表数目，每个 哈希表包含r个随机生成的哈希函数，哈希表宽度是W。

(1)对文档的每种特征进行汉明(Hamming)空间转换，将X映射到汉 明空间上。

(2)选取合适的参数L、r、W。初始化哈希函数族H＝{h1，...，hL}，计 算特征在索引中的位置，每个哈希函数的值由下式决定

$h_{a,b}=\frac{a\times v+b}{W}---\left(1\right)$

其中，a和b服从高斯随机分布，v是数据库中的文档的特征向量，W 为哈希表宽度，计算后得到哈希函数族

$g\left(v\right)=\left(h_{a_1,b_1}\right(v),\mathrm{...},h_{a_r,b_r}(v\left)\right).$

(3)利用这些哈希函数，将特征存入相应的哈希表项。

本实施方式中在步骤5中，具体采用以下方式进行权重设置：

(1)关键字特征的权重：

$w_1=e^{{\mathrm{tf}}_{q,C_1}}\times {\mathrm{idf}}_{C_1}=e^{\frac{{\alpha }_q\times {\beta }_q}{{\tau }_{C_1}}}\times log(\frac{N}{n}+0.01)\times 0.2---\left(2\right)$

其中，w₁为查询点q在关键字C₁中的权重；为查询点q在关键字中出 现的词频；为逆文档频率；α_q为查询点q在关键字中出现的次数，β_q为查 询点q的字数，为目前文档关键字的总字数；N为数据库中总文档数，n为 数据库中出现查询点q的文档数。

(2)标题特征的权重：

$w_2=e^{{\mathrm{tf}}_{q,C_2}}\times {\mathrm{idf}}_{C_2}=e^{\frac{{\alpha }_q\times {\beta }_q}{{\tau }_{C_2}}}\times log(\frac{N}{n}+0.01)\times 0.2---\left(3\right)$

其中，w₂为查询点q在标题C₂中的权重；为查询点q在标题中出现的 词频；为逆文档频率；α_q为查询点q在标题中出现的次数，β_q为查询点q 的字数，为目前文档标题的总字数；N为数据库中总文档数，n为数据库中 出现查询点q的文档数。

(3)作者特征的权重：

$w_3=e^{{\mathrm{tf}}_{q,C_3}}\times {\mathrm{idf}}_{C_3}=e^{\frac{{\alpha }_q\times {\beta }_q}{{\tau }_{C_3}}}\times log(\frac{N}{n}+0.01)\times 0.2---\left(4\right)$

其中，w₃为查询点q在作者C₃中的权重；为查询点q在作者中出现的 词频；为逆文档频率；α_q为查询点q在作者中出现的次数，β_q为查询点q 的字数，为目前文档作者的总字数；N为数据库中总文档数，n为数据库中 出现查询点q的文档数。

(4)检索次数、更新时间的权重：

因为要满足所有特征量的权重相加为1，故

$w_4=w_5=\frac{1-w_1-w_2-w_3}{2}---\left(5\right)$

其中，w₁为查询点q在关键字C₁中的权重；w₂为查询点q在标题C₂中的权 重；w₃为查询点q在作者C₃中的权重；w₄为查询点q在更新时间C₄中的权重； w₅为查询点q在检索时间C₅中的权重。

本实施方式中在步骤6中，具体采用以下方式进行权重阈值设置：

为保证检索结果的有效性和准确性，要对更新时间和检索次数的权重设置 一个阈值。具体的，当更新时间的权重值w₄和检索次数的权重值w₅之和大于 阈值0.4时，进而进入步骤7。

本实施方式中在步骤7中，具体采用以下方式进行权重的重新设置：

将w₄、w₅分别减去0.025，同时将关键字的权重值w₁加上0.05，进而进入 步骤8。

本实施方式中在步骤8中，计算综合距离的原理如下：

在一个LSH(Locality-SensitiveHashing)算法的哈希表中，与查询点相近 的数据点出现在于查询点一样的桶中的可能性远远大于与查询点相距较远的 点，也就是说，距离越小，数据间的相似性更强，回收的数据更有效。因此， 我们可以预期综合距离越小，则该数据点与查询点相似性更高。所以，我们利 用综合距离来衡量数据的相似性。

综合距离的定义：

$D_i=\underset{m=1}{\overset{4}{\Sigma }}{w}_n{C}_m-w_5{C}_5,$i＝1,2,…,k

其中，D_i为数据点x_i与查询点q间的综合距离；w_m为各特征量对应的权重 值；C_m为各特征量转换后的距离；k为数据点的个数且为正整数。

其含义为：综合距离＝关键字对应距离×权值+标题对应距离×权值+作者信 息对应距离×权值+更新时间对应距离×权值-检索次数对应距离×权值，对应距 离为本实施方式中步骤4所述的距离，权值为本实施方式中步骤5所计算得到 的权值。对于关键字，标题，作者信息和更新时间的对应距离，值越小则表明 与查询点越相近；对于检索次数，距离值越大则表明检索次数越多，可能与查 询点的相似性更大。而综合距离是期望得到更小的值，故在上式中要减去检索 次数的对应距离。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、 “具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特 征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明 书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描 述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中 以合适的方式结合。

尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理 解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、 修改、替换和变型，本发明的范围由权利要求及其等同物限定。