一种基于多样性和比例特性的关键词检索方法

摘要

本发明涉及一种基于多样性和比例特性的关键词检索方法，对用户所输入的关键词和自然数l，然后根据关键词与各元组信息之间的链接关系，运用算法返回给用户l条最全面的基于关键词的元组信息。步骤一：受链接分析算法PageRank的启发，设计静态离线排序评价分数，生成所有节点的初始值；步骤二：输入关键词生成备选的OS；步骤三：输入自然数l根据得到的OS用k‑LASP算法生成最终含有l个节点的以DS为根的树。经实验结果证明，本方法得到的实验效果显著。

主权项

一种基于多样性和比例特性的关键词检索方法，其特征在于：该方法的实施步骤如下，步骤一：受链接分析算法PageRank的启发，设计静态离线排序评价分数，生成所有节点的初始值；步骤1.1：收集并整理数据集，构建数据关系；这时定义有向图G(V，E)，其中V(v₁,...,v_n)是节点集，这里的节点代表各类信息，E是代表边的集合，E＝{<v_i,v_j>|v_i,v_j∈V}，<v_i,v_j>表示从v_i到v_j的一条边，即v_i的信息能够链接到v_j；步骤1.2：r是一个矢量即各个的页面的评价分数的队列，其中每个节点v_i都存在相应的r_i，则通过以下公式来迭代计算矢量r的评价分数：$r=dAr+(1-d)\frac{e}{\left|V\right|}---\left(1\right)$其中d是一个(0,1)的阻尼系数，此系数能够保证得到更精确的结果，一般取值为0.85；A是一个n*n矩阵，n代表顶点个数，其中若存在从v_i到v_j的边(弧)，则表示v_j的出度)，否则为0，也就是说若有三个节点，则A是一个3*3矩阵，v₀到v₁和v₂都有边且v₁到v₂有边，则且A₂₁＝1，其余都为0；e＝[1....1]^T；|V|为顶点个数；综上，迭代计算出数据集中各个节点的评价分数，这时将这个值称作为全局权值，即gi(v_i)代表v_i节点的初始值；全局权值global importance，缩写为gi；步骤二：输入关键词生成备选的OS；步骤2.1：输入关键词(即DS)，系统生成一个以DS顶点为根节点(即R^DS)，以能与R^DS链接的关系为子孙的树，即OS；在生成OS的过程中为了区分OS中的每个元组节点v_i的重要性，将一个局部权值(local importance，缩写为li)是由这个元组在数据库中的全局权值(gi)和这个元组在OS中的与R^DS的亲和度两部分所决定的；亲和度为Affinity，缩写为Af；步骤2.2：在生成OS中，G^DS中与R^DS有较高亲和力的关系将被加入到OS中，R_i到R^DS的亲和度Af(R_i)由以下公式迭代计算：$Af\left(R_i\right)=\underset{j}{\Sigma }{w}_j{m}_j·Af\left(R_{Parent}\right)---\left(2\right)$其中j是一个范围，这个范围为指标集合(m₁,m₂,...,m_n)和它的相应的权值集合(w₁,w₂,...,w_n)，这里考虑四个指标：指标m₁为R_i到R^DS的距离，也就是两个关系之间的距离越小，亲和度就越高；指标m₂为关系的相对基数，也就是R_i与R_Patent中每个元组相连的平均元组的数量；指标m₃为关系的反相对基数，即R_Patent与R_i中的一个元组相连的平均数量；指标m₄为R_i的模式的连通性，即R_i在关系图中的链接的数量；Af(R_Parent)是指R_i的父亲节点与R^DS的亲和度，初始值为1，即R^DS本身的亲和度为1；指标的分数范围是[0,1]，相应的权值的总和为1(上述四个指标相应的权值都为0.25)；而且在OS的生成中，所有关系节点的亲和度都应该高于一个临界值θ；步骤2.3：计算出备选的size‑l OS S的重要性Im(S)的公式为：$\mathrm{Im}\left(S\right)=\underset{n_i\in S}{\Sigma }\mathrm{Im}(OS,R_i)---\left(3\right)$其中Im(OS,R_i)是OS中节点R_i的li值，Im(OS,R_i)可以由以下公式算出：Im(OS,R_i)＝Im(R_i)·Af(R_i)   (4)其中，Im(R_i)是R_i的gl值，Af(R_i)为R_i到R^DS的亲和度；综上根据输入的关键词计算出Im值，生成备选的OS；步骤三：输入自然数l根据得到的OS用k‑LASP算法(详见步骤3.3)生成最终含有l个节点的以DS为根的树；在此步骤中将考虑三个因素：多样性削弱量(dv)、比例特性增量(pv)和静态值(li)，最终将他们分别结合来得出最后的一个分数(即dw，pw)；步骤3.1：多样性(Dsize‑l)为了避免重要性过高的相似信息的重复出现，应选择输出l条多样化的信息，所以给出一个如下多样性削弱量的计算方法：$dv\left(v_i\right)=1-\frac{z\left(g\right(v_i\left)\right)-1}{l-1}---\left(5\right)$其中，g(v_i)是指与v_i相似的元组节点；z(g(v_i))‑1是指在size‑l OS内与v_i节点相似的元组节点的总和；z(g(v_i))是指g(v_i)要出现在size‑l OS中的次数；dv(v_i)的值域是[0,1]；定义dv[z]为节点在size‑l OS中出现z次的多样性削弱量值，例令l＝10，“Marry”出现2次，即z＝2，则然后，Dsize‑lOS中的一个节点静态值与多样性削弱量值结合的多样性权值由如下公式计算：dw(v_i)＝li(v_i)·dv(v_i)   (6)综上，给出一个OS和l，生成一个Dsize‑l OS需要满足以下条件：1.Dsize‑lOS中的元组个数为l(l≤|OS|)；2.这l个节点都必须与根节点相连；3.每一个节点v_i都有与之对应的多样性权值即dw(v_i)；4.一个Dsize‑l OS的汇总得分为$\mathrm{Im}\left(DSl\right)=\underset{v_i\in DSl}{\Sigma }dw\left(v_i\right)---\left(7\right)$步骤3.2：比例特性(Psize‑l)鉴于在一个OS中一个元组节点可能多次地出现，但是这些节点可能拥有较弱的静态值，而它们的频率在实际的要得到的size‑l OS中有着与DS重要的联系，由此，比例特性增量值可由如下公式计算：$pq\left(v_i\right)=\frac{fr\left(g\left(v_i\right)\right)}{\alpha ·z\left(g\left(v_i\right)\right)+1}---\left(8\right)$其中，fr(g(v_i))为g(v_i)出现在OS中的次数；z(g(v_i))是指g(v_i)要出现在size‑l OS中的次数；α是一个可以调整比例的常数，一般取α＝2；然后Psize‑l OS中的一个节点静态值与比例特性增量值结合的比例特性权值由如下公式计算：pw(v_i)＝li(v_i)·pq(v_i)   (9)综上，给出一个OS和l，生成一个Psize‑l OS需要满足以下条件：1.Psize‑l OS中的元组个数为l(l≤|OS|)2.这l个节点都必须与根节点相连3.每一个节点v_i都有与之对应的多样性权值即pw(v_i)4.一个Psize‑l OS的汇总得分为$\mathrm{Im}\left(PSl\right)=\underset{v_i\in PSl}{\Sigma }pw\left(v_i\right)---\left(10\right)$步骤3.3：用k‑LASP算法生成最终含有l个节点的以DS为根的树；k‑LASP(k‑Largest Averaged Score Path)即k个节点的最大平均值路径(也就是一条路径上的k个节点权值的平均值)，在此步骤中，将dw和pw值统称为权值w；OS中的每一个节点v_i都有一个权值w(v_i)，与之对应的v_i与其先辈节点(个数n,n＝max(k—1,实际长度))的平均权值定义为在生成OS的过程中，需要一个哈希表，用HFr表示，HFr包括三个部分，一是将v_i中的i作为图节点的编号，二是v_i在OS中出现的次数fr(v_i)，三是v_i在size‑l OS中出现的次数z(v_i)；为了更好地管理OS中节点和对应的AP值，建立一个队列W来保存这些信息，在这个队列里节点的顺序按相对应的AP值递减排列；k‑LASP算法生成size‑l OS的过程为：1)生成OS，包括构建HFr、计算AP(v_i)和生成W2)若|size‑l|<l，转3)，否则转11)3)p_i表示当前W中拥有最大AP值的节点到根节点的路径，将p_i里的前l‑|size‑l|个节点加入到size‑l OS中4)如果|size‑l|<l，转5)，否则转10)5.将所选p_i中的l‑|size‑l|个节点从OS和W中移除6)对于p_i每个节点的子孙节点v_j做如下更新：在OS和W中更新AP(v_j)值；子孙节点的个数为n,n＝max(k—1,实际长度)；7.对于p_i中的每个节点g(v)，若g(v)在HFr，转8)，否则转10)；8.HFr(g(v)).z++9)对于OS中每个使得g(n)＝g(v)的节点n做如下更新：对于每一个以节点n为根的子树中的每个节点n_i做：用HFr(g(v)).z值在OS和W中更新AP(n_i)值9.转2)11)返回size‑l OS此时返回的size‑l OS即所需的将要检索到的l条元组信息；经实验结果证明，本方法得到的实验效果显著。