基于主权迭代搜索的概念关系快速发现方法

技术领域

本发明涉及一种概念关系快速发现方法，尤其涉及一种基于主权 迭代搜索的概念关系快速发现方法，属于语义网络技术领域。

背景技术

在自然语言世界中，概念是对客观实体的抽象描述，是客观实体 属性特征的集合。由于客观实体的相互作用，概念之间亦产生千丝万 缕的关联，我们称之为概念关系。概念及概念关系共同构成了自然语 言世界的基础，如果说自然语言世界是一个语义网络，那么概念就是 语义的载体，而概念关系就是语义载体间的纽带。通过研究概念关系 可以反射得出客观世界中实体关联的内容与性质，进而为人类的工作 和生活服务。

在当前信息社会中，互联网无疑是数据的最大载体，以超链接关 联的超文本信息日益增长，构成了信息网络世界，已经彻底改变了现 代人类的工作和生活的方式。然而，亦是因为信息的爆炸式增长，管 理和使用信息越来越复杂，越来越困难。为适应语义推理和智能化服 务的需求，语义Web为代表的下一代信息互联网络试图在任何微小数 据间构建连接，而概念关系正是构建语义网络的基础。因此，概念关 系抽取技术是人类信息第二次变革的基础。

搜索引擎和文本挖掘是平台门户系统的核心技术，而概念和文本 的“语义相关度计算”又是搜索引擎和文本挖掘的关键基础。在纯粹 的统计模型下，由于缺少知识智能的支持，只能以“相似度”代替“语 义相关度”，作为搜索引擎和文本挖掘中解决一系列复杂技术问题的基 础。

但是，随着信息量爆炸增长、信息结构日益复杂化和互联网的社 会化趋势，人们对搜索引擎和文本挖掘提出了愈发强烈的搜索智能和 个性化服务的需求，此时，语义相关度计算的问题再次置于搜索引擎 和文本挖掘技术面前，“相似度”计算无论在准确性还是物理意义上都 已经无法满足这种需求，“语义相关度”计算似乎已经成为一个智能搜 索时代必须解决的基础问题。

目前，布尔模型和向量空间模型均在文本分类中得到广泛而有效 的应用。布尔搜索可以快速发现概念关系，但是准确性和召回率均无 法得到保证，而且用于构造布尔查询的特征元素数目亦难以确定，查 询特征过少则会导致查询效率降低，结果数过多，查询特征过多则召 回率降低。扩展的布尔搜索可以对查询匹配的特征元素赋予权重，可 以一定程度上提高召回率，但是不能解决查询逻辑的构造问题。向量 空间模型也存在一些缺点，主要表现为：向量空间的维数往往很高， 导致计算量大，影响系统速度。此外，向量中特征权值的确定也是较 难考量的一个部分。

发明内容

针对现有技术所存在的不足，本发明所要解决的技术问题在于提 供一种概念关系快速发现方法。该方法既可保证查询效率，亦可保证 准确性和召回率

为实现上述的发明目的，本发明采用下述的技术方案：

一种基于主权迭代搜索的概念关系快速发现方法，包括：

使用布尔搜索消除不包含相同非零元素或者仅包含极少非零元素 的概念对；

使用枚举法计算向量空间下的概念相关度；

排序求得最相关概念。

更进一步地，所述布尔搜索包括：

将概念的语义特征向量转化为布尔表达式，并构建特征向量正向 索引和特征倒排索引，使用目标概念的语义特征构造逻辑查询，在逻 辑表达式集合中搜索得到目标概念的相关概念集。

更进一步地所述使用枚举法计算向量空间下的概念相关度步骤包 括：

a.搜索器根据特征向量正向索引搜索特征向量；

b.根据搜索到的特征向量获取主权特征；

c.搜索器以进行关联搜索，选出候选相关概念，并放入候选相关 概念集；

d.候选概念选取策略得到候选概念；

e.候选概念集饱和控制策略搜索到关联特征倒排拉链后，选取候 选概念；

f.判断候选概念集是否已达到饱和，若候选概念集未达到饱和则 返回b，重复b～f，直到候选概念集达到饱和；

f.若候选概念集已达到饱和迭代搜索停止，精确计算目标概念同 候选相关概念的相关度。

更进一步地，所述候选概念选取策略包括：

a.搜索器使用关联特征为查询键，在特征倒排索引中执行查询， 得到候选概念拉链；

b.将窗口为M的滑动窗口置于拉链首部，若元素不多于M，则全 部选为候选概念；

c.如果元素多于M，监督器监测监督条件，即将首尾权重减幅和 幅度阈值进行对比；

d.若首尾权重减幅小于或等于幅度阈值，滑动窗口移动一位并返 c，重复c～d，直到首尾权重减幅大于幅度阈值；

e.若首尾权重减幅大于幅度阈值，则将窗口后的元素剪掉，剩余 即选为候选概念。

更进一步地，所述候选概念集饱和控制策略包括：

a.搜索候选概念，若候选概念已存在于候选相关概念集中，对关 联特征增量计算“伪相关度”，若候选概念为新增概念使用关联特征计 算“伪相关度”；

b.重新调整候选概念拉链顺序；

c.滑动窗口置于拉链首部，判断元素数和窗口的大小，若元素数 不大于窗口大小，重新执行候选概念选取策略，若元素数不小于窗口 大小，则检查首尾候选概念“伪相关度”减幅，与幅度阈值比较；

d.若“伪相关度”减幅小于幅度阈值，向拉链尾部滑动窗口进入 步骤，若已到达拉链尾部，重新执行候选概念选取策略，否则返回c， 重复c～d，直到“伪相关度”减幅不小于幅度阈值；

e.若“伪相关度”减幅不小于幅度阈值，候选相关概念集达到饱 和，停止迭代搜索。

更进一步地，所述构建特征向量正向索引包括：

对所有概念进行编号，对所有概念的语义特征按照权重降序，并 将特征向量归一化为单位向量；

以“概念编号-特征向量”的键值关系构造特征向量正向索引。

更进一步地，所述构建特征倒排索引包括：

将每个单位特征向量看作一个文档，以向量特征为倒排词条，索 引拉链中的概念编号按照特征权重大小降序排列，构造特征倒排索引。

本发明基于布尔模型的概念关系发现方法和基于向量空间模型的 枚举关系发现方法，将两者的优点进行融合，扬长避短，给出一种时 间效率接近前者，而准确率和召回率接近后者的快速方法。

附图说明

下面结合附图和具体实施方式对本发明作进一步的详细说明。

图1是特征向量单位归一化及索引结构示意图；

图2是特征倒排构建及索引结构示意图；

图3是单次迭代搜索的操作流程示意图；

图4是基于主权迭代搜索的关系发现流程示意图；

图5是候选概念选取策略的执行流程示意图；

图6是候选概念集饱和控制策略的执行流程示意图；

图7是召回率和时间效率的对比实验总体流程示意图；

图8是单次搜索概念选取数平均值示意图；

图9是饱和控制策略参数调控下的平均召回率示意图；

图10是饱和控制策略参数调控下的平均召回率示意图；

图11是时间效率和召回率对比示意图。

具体实施方式

概念关系发现是指发现语义关系密切的概念关系对，它是概念关 系抽取的关键步骤。概念关系发现一般只搜寻和概念关系最为紧密的 Top-M个概念。一般情况下，M为自然数且取值不大，在两位数的范围， M值过大就失去了相关概念的意义。

对于一个目标概念，从300万个候选概念中搜寻Top-M(M＜100) 个最相关概念，有效率仅为1/10000。如果使用枚举法搜寻最相关概 念，则99.99％的计算资源都将被用在计算与非相关概念的相关度上， 这是极不划算的。概念语义特征向量的平均元素个数仅为300左右， 相对于300万维的概念语义空间来说，特征向量仅有1/10000非零元 素，可谓极其稀疏。因此，绝大多数概念对之间并不包含相同的非零 元素，即使包含相同的非零元素，大部分概念对仅包含极少数的相同 非零元素。

本发明使用布尔搜索消除不包含相同非零元素或者仅包含极少非 零元素的概念对，在量级上缩小候选概念集，然后，在概念集内使用 枚举法计算向量空间下的概念相关度，而后排序求得Top-M最相关概 念。则即可保证查询效率，亦可保证准确性和召回率。

布尔模型就是采用布尔表达式对文本进行表示。布尔模型在传统 的信息检索中有广泛的应用，它通过与用户给出的检索式进行逻辑比 较来检索文本，是一种基于关键词的匹配。在标准的布尔模型中，文 本如式(1)所示：

d_i＝(w_i1，w_i2，......w_ik......w_in)，其中k＝1，2，...，n    (1)

其中n为特征项的个数，w_ik为0或1，表示第k个特征项在文本i 中是否出现。布尔模型易于实现，但在文本分类领域，它的准确率和 召回率较差。

假如，概念共同包含某个或某几个特征是概念间存在紧密语义关 系的充分条件，那么，概念关系发现即可转化为布尔模型下的搜索过 程。将概念的语义特征向量转化为布尔表达式，并构建倒排索引，使 用目标概念的语义特征构造逻辑查询，在逻辑表达式集合中搜索即可 得到目标概念的相关概念集。

布尔模型将连续值离散化为0或1，仅在存在与否间做抉择，虽 然一刀切的做法不甚精准，但是却有着极高的效率。但是，在高维的 语义空间中，一个概念的语义性质是特征向量中所有的语义特征共同 决定的，而且他们的决定权重大相径庭。因此，基于布尔模型的搜索 方法亦不可直接用于海量概念的关系发现。

相对布尔搜索，缩小候选概念集后再使用枚举法计算向量空间下 的相关度，可以提高准确率。但是要保证很好的召回率，则需要尽可 能的将相关概念包含在缩小后的候选概念集中，然而，为了保证效率， 候选概念集合又不能太大。所以，如何尽量使用布尔逻辑缩小候选概 念关系集合而又尽量少损失相关概念是本方法的核心关键问题。

向量空间模型是由Gerard Salton和McGill于1969年提出的。 因其概念简单，在信息检索(Information Retrieval，简称IR)中 得到广泛应用。在文本自动分类中使用这种方法主要是从IR中引进过 来的。向量空间模型的基本思想是：将每个词条作为特征空间坐标系 的一维，将文本看作特征空间的一个向量，用两个向量之间的夹角来 衡量两个文本之间的相似度。在向量空间模型中，每一个文本都被表 示为由一组规范化正交词条向量所张成的向量空间的一个点，即形式 化为n维空间中的向量，因此我们可以将文本抽象为式(2)所示：

V(d_i)＝((t₁，w_1j)，......(t_i，w_ij)，......(t_n，w_nj))，i＝1，2，......n    (2)

其中，t_i是特征项i，w_ij是t_i在文本d_j中的权重。对于一个训练 文本集合，我们就可以得到如下表1所示的一个向量空间W：

表1向量空间下的文本表示

W通常是一个稀疏矩阵。训练文本和待分类文本在向量空间模型 中都可用相同的方法表示出来。待分类文本的向量越接近训练文本向 量，说明其与训练空间中的文本的相似度越大，越有可能和训练文本 属于同一个类别。

向量空间模型是目前广泛使用的文本表示模型，具有如下优点：

(1)文本内容被形式化到多维空间中的一个点，通过向量形式给 出，将文本以量的形式定义到了实数域中，提高了自然语言文本的可 计算性和可操作性；

(2)为词计算权值，通过调节词对应权值的大小来反映词与所在 文本的相关程度，克服了传统布尔模型的缺陷；

(3)通过计算文本之间的相似度，使属性相似的文本尽量聚拢在 一起，以提高匹配效率。

向量空间模型下通过向量余弦夹角的方法计算最相关概念，在本 质上有别于布尔模型。在向量空间模型中，维度之间是离散的，但是 在任一维度内部，又是连续的。向量空间模型正是用这种离散和连续 结合的方式实现了特征间的共同作用，不绝对依赖某个特征，但是又 不放弃任何一个特征。

对语料库中的每一个概念，使用表现语义构造法构建语义特征向 量，用TF-ODF特征赋权，并基于中文语用进行调权，特征降维之后即 可得到概念的解释语义特征向量表示。

设向量平均长度为n，对特征进行排序后可以在O(n)的时间内计算 余弦夹角，采用快速排序时间复杂度为O(nlogn)，故最终时间复杂度为 O(nlogn)。

基于解释关系构造概念语义特征向量后，对语义特征赋权，两两 计算概念相关度后排序，就可获取任意概念的Top-M相关概念。假设 开放百科语料库中的概念总数为N，两两计算时间复杂度为O(N²)。对 任一概念使用最大堆搜寻保存当前最大的M个相关度值及对应概念， 则计算完所有概念对的相关度后即可得到任一概念的Top-M最相关概 念，最大堆每次调整时间消耗为logM。又已知概念相关度计算的平均 复杂度为O(nlogn)，则可知使用两两计算概念相关度的方法Top-M相关 概念发现的时间复杂度为O(N²nlognlogM)。其中，n为向量平均特征个 数，降维后n约为300，而N为开放百科语料库概念总数，约为300 万。粗略计算，运算能力在10亿/s的单台计算机需要约3年才可完 成，这显然是不可接受的。

在向量空间模型中，每一维特征项所对应的权值称为特征权重， 简称权重。主权特征指语义特征向量中起主导作用特征。统计表明， 在80％特征向量中，权重之和的80％集中在前20％的特征中。迭代搜索 是在搜索过程中不断调整并维护候选概念集，直到满足一定的条件终 止迭代，确定候选概念集合。

基于主权迭代搜索的概念关系快速发现方法结合布尔模型和向量 空间模型，取长补短，利用布尔模型的效率优势进行粗略计算，将候 选相关概念限定在小数量级范围，而后再利用向量空间模型的准确性 优势进行细致计算，最终得到Top-M最相关概念。

如图1所示，首先，我们对所有概念进行编号，代替概念词语进 行存储以节省空间，之后对所有概念的语义特征按照权重降序，并将 特征向量归一化为单位向量。单位向量的模为1，便于在计算向量的 夹角余弦，也便于横向比较同一特征在不同向量中的权重。此外，以 “概念编号-特征向量”的键值关系构造索引，方便随机快速的获取 任一概念编号对应的特征向量。为了和后续构建的特征倒排索引相区 别，我们称此处构建的索引为特征向量正向索引。

然后，将每个单位特征向量看作一个文档，以向量特征为倒排词 条，构造倒排索引，索引拉链中的概念编号按照特征权重大小降序排 列。如图2所示，这种结构可以方便快速地随机访问任一语义特征横 向关联的概念集合，概念按权重大小排序，利于由强到弱的顺序访问 关联概念。

特征向量的正向索引和特征倒排索引是后续搜索迭代的结构基础 和效率保障，索引构造完毕后即可按照搜索迭代方法进行概念关系发 现。为方便方法描述，我们将待计算相关概念的概念称为目标概念。

搜索迭代方法包括“搜索器”和“候选相关概念集”两部分。候 选相关概念集由候选相关概念组成，初始为空集。搜索器以目标概念 的高权重特征为关联特征进行关联搜索，选出候选相关概念，并放入 候选相关概念集。候选概念同目标概念具有相同的关联特征，使用这 些动态变化的关联特征计算候选概念与目标概念的相关度，我们称为 “伪相关度”。之所以称其为“伪相关度”，是因为其仅是目标概念与 候选概念部分匹配特征计算得到。但由于关联特征是目标概念的主要 权重特征，而候选概念又是从关联特征列表的首部取得，因此，“伪相 关度”是“真实相关度”的主要部分，当关联特征趋近于目标概念的 全部特征时，“伪相关度”等于“真实相关度”。因为特征向量均已被 单位归一化，模为1，所以“伪相关度”的计算无需考虑向量的模， 进而可实现增量计算，提高计算效率。迭代搜索流程框架如图3所示， 图中将前两位的主权特征搜索合并在一起进行展示。图4是基于主权 迭代搜索的关系发现流程示意图。

迭代搜索的过程有两个关键策略步骤，一是搜索到关联特征倒排 拉链后，选取多少候选概念，我们称为“候选概念选取策略”；二是候 选相关概念集何时饱和，停止关联搜索，我们称为“候选概念集饱和 控制策略”。带监督器的滑动窗口可以用过调控监督器一定程度上保证 剪枝掉的元素较大概率的不会出现在目标结果集中。我们亦将带监督 器的滑动窗口引入此处的两个策略步骤中，同特征降维一样，监督器 的参数亦通过实验得出。

带监督器的滑动窗口需要设定窗口大小winLen和幅度阈值δ。由于 我们欲获取Top-M个相关概念，因此，设定候选概念选取策略的滑动 窗口大小为winLen₁＝M，幅度阈值δ₁则通过实验得出。候选概念集饱和 控制策略滑动窗口大小设为winLen₂，幅度阈值设为δ₂。

如图5所示，候选概念选取策略的执行步骤如下：

步骤401，搜索器使用关联特征为查询键，在特征倒排索引中执 行查询，得到候选概念拉链，进入步骤402。

步骤402，将窗口为M的滑动窗口置于拉链首部，若元素不多于M， 则全部选为候选概念，如果元素多于M则进入步骤404。

步骤404，监督器监测监督条件，即将首尾权重减幅和幅度阈值δ₁进行对比进入步骤405。

步骤405，若首尾权重减幅小于或等于幅度阈值，进入步骤407； 若首尾权重减幅大于幅度阈值，进入步骤406。

步骤406，则将窗口后的元素剪掉，剩余即选为候选概念。

步骤407，滑动窗口移动一位，并返回到步骤404。

如图6所示候选概念集饱和控制策略的执行步骤如下：

步骤501，搜索候选概念，若候选概念已存在于候选相关概念集 中，进入步骤502；若候选概念为新增概念进入步骤503。

步骤502，对关联特征增量计算“伪相关度”，进入步骤504。

步骤503，搜索候选概念，使用关联特征计算“伪相关度”，进入 步骤504。

步骤504，根据“伪相关度”重新调整候选概念拉链顺序，进入 步骤505。

步骤505，滑动窗口置于拉链首部进入步骤506。

步骤506，判断元素数和winLen₂的大小，若元素数不大于winLen₂， 重新执行候选概念选取策略进入子流程4；若元素数不小于winLen₂， 则进入步骤507。

步骤507，监督器检查首尾候选概念“伪相关度”减幅，与幅度 阈值δ₂比较进入步骤508。

步骤508，若“伪相关度”减幅不小于δ₂，进入步骤509；若“伪 相关度”减幅小于δ₂，则进入步骤510。

步骤509，候选相关概念集达到饱和，停止迭代搜索，候选概念 集饱和控制策略流程结束。

步骤510，向拉链尾部滑动窗口进入步骤511。

步骤511，若已到达拉链尾部，重新执行候选概念选取策略，进 入子流程4；否则回到步骤507。

候选概念集达到饱和后，迭代搜索停止，此时就确定了候选相关 概集合，集合规模远小于开放百科的全体概念集合。进一步精确计算 目标概念同候选相关概念的相关度，排序后即可得到Top-M最相关概 念。基于主权迭代搜索的概念关系发现方法整体数据流程如图6所示， 具体步骤如下：

步骤601，目标概念搜索开始，进入步骤603。

步骤602，对所有概念进行编号，构建特征向量正向索引。

步骤603，搜索器根据特征向量正向索引搜索特征向量，进入步 骤604。

步骤603，根据搜索到的特征向量获取主权特征，进入步骤606。

步骤605，以向量特征为倒排词条，构造特征倒排索引。

步骤606，搜索器以目标概念的高权重特征为关联特征进行关联 搜索，选出候选相关概念，并放入候选相关概念集。

步骤4，候选概念选取策略子流程得到候选概念，进入步骤5。

步骤5，候选概念集饱和控制策略子流程搜索到关联特征倒排拉 链后，选取候选概念进入步骤607。

步骤607，判断候选概念集是否已达到饱和，若候选概念集已达 到饱和迭代搜索停止，进入步骤608；候选概念集未达到饱和则返回 到步骤603。

步骤608，精确计算目标概念同候选相关概念的相关度，排序后 即可得到Top-M最相关概念，进入步骤609。

步骤609，基于主权迭代搜索的概念关系发现方法流程结束。

特征向量正向索引、向量特征倒排索引、搜索器、候选相关概念 集、候选概念选取策略和候选概念集饱和控制策略组成了基于主权迭 代搜索的关系发现系统。

在此基础上，进一步对基于主权迭代搜索的进行验证，求取候选 概念选择策略和候选概念集饱和控制策略的最优滑动窗口参数，并同 “布尔模型下的关系发现”和“向量空间模型下穷举关系发现”在效 率和召回率上进行对比。

效率问题是概念关系发现需重点解决的问题，也是基于主权迭代 搜索方法提出的目的，因此，时间效率是本实验的重要考察指标。计 算一个概念的Top-M相关概念所需的时间记为Time_relM，我们使用平 均时间作为衡量一个概念关系发现方法的时间效率指标。

概念关系发现的平均用时固然可以反应方法的时间效率，但是由 于迭代搜索方法分为多个步骤，为更清晰的分析时间效率在各个步骤 之间的分布以找出效率瓶颈，我们追加迭代搜索次数和饱和候选相关 概念集大小作为两个辅助时间效率指标。每一次迭代搜索需要查询特 征向量正向索引，饱和候选相关概念集的大小直接影响后续准确相关 度的计算量，因此这两个指标能够很好的反映迭代搜索的效率变化。

我们将向量空间模型下穷举概念相关度计算得到的Top-M相关概 念作为召回标准，计算关系发现的召回率，将穷举概念相关度计算得 到的Top-M相关概念集合记为Φ_std，将待评估相关概念集合记为Φ_est， 使用Card(Φ)表示可数集合包含的元素个数，则召回率计算公式如下：

$\mathrm{recall}\left({\Phi }_{\mathrm{est}}\right|{\Phi }_{\mathrm{std}})=\frac{\mathrm{card}({\Phi }_{\mathrm{std}}\cap {\Phi }_{\mathrm{est}})}{\mathrm{card}\left({\Phi }_{\mathrm{std}}\right)}*100\%---\left(3\right)$

尽管召回率不能反应相关概念在不同位序缺失的差异性，但是相 关概念的质量评估更注重级差质量，因此，召回率能够直接反应基于 搜索的快速关系发现方法为计算效率付出的结果质量代价。

上述基于主权迭代搜索的关系发现方法有三个参数需要实验确 定，候选概念选取策略幅度阈值δ₁，候选概念集饱和控制策略滑动窗 口大小winLen₂和幅度阈值δ₂。其中δ₁∈(0，1)，winLen₂∈[M，+∞)，δ₂∈(0，1)。 这三个变量同候选概念选取策略滑动窗口大小winLen₁＝M之间相互影 响，关系复杂。同时实验三个变量会增加实验分组使实验结果而复杂 难于分析。

候选概念选取策略幅度阈值δ₁的大小会影响单次搜索选取的概念 数，进而在候选概念集饱和控制策略滑动窗口大小winLen₂和幅度阈值 δ₂确定的情况下影响迭代搜索的次数。幅度阈值δ₁过大会使单次搜索 选取的概念数过大，进而可能导致迭代搜索的次数下降而降低召回率； 幅度阈值过小则会使单次搜索选取的概念数偏少，进而可能导致搜索 迭代次数上升而使时间效率降低。由于候选概念选取策略的滑动窗口 已经确定，经过反复试验的经验，单次搜索选取的概念数在[M，2M]之 间为佳，因此，可先通过单次搜索选取概念数作为结果反馈缩小幅度 阈值的范围。

确定候选概念选取策略的参数后，可对候选相关概念集饱和控制 策略的两个参数联合实验。先根据召回率的走势确定滑动窗口的大小， 然后配以多组幅度阈值组合分析实验的召回率和时间效率，确定最优 参数组合。

参数确定后，基于主权迭代搜索的关系发现方法达到已知最优状 态，进而同布尔模型下的搜索方法、向量空间模型下的枚举方法进行 召回率和时间效率的对比实验，以验证方法的有效性。

如图7所示，主权迭代搜索的关系发现方法同布尔模型下的搜索 方法、向量空间模型下的枚举方法进行召回率和时间效率的对比实验 大致分为三个阶段，候选概念选取策略幅度阈值的确定、候选相关概 念集饱和控制参数的确定、关系发现方法效率和召回率对比。

(1)候选概念选取策略幅度阈值实验

设计2*9组实验，M取值为10和20，δ₁取值为5％、10％、15％、20％、 25％、30％、35％、40％、45％。每组实验计算目标概念集中所有目标概念 的单次搜索选取的平均概念数，每个概念选取前M位的特征进行关联 搜索。结果如下表2所示：

表2单次搜索选取概念数平均值

如图8所示，单次搜索选取概念数平均值的2倍M值出现在幅度 阈值25％和30％之间，由于参数之间是相互影响的，所以单参数的小范 围浮动可以在其他参数中调整达到最优。通过本实验结果分析，我们 选用更接近2倍M的25％作为候选概念选取策略的幅度阈值继续后续 试验。

(2)候选相关概念集饱和控制策略参数实验

饱和控制策略参数是本发明的重要实验内容，因为该策略对关系 发现的召回率和时间效率有着决定性的影响。实际操作中，该实验经 过多次反复迭代才得以完成，实验发现，待发现关系数M处于不同范 围时，策略参数有着很大的差异。为了方便描述，现将实验划分为两 部分，第一部分针对M≥10的情况进行实验描述并分析总结，第二部分 对0＜M＜10的情况进行实验并分析。

首先，阐述实验的第一部分。设计4*10*7组实验参数，其中M值 为4组、滑动窗口为5组，幅度阈值为7组。幅度阈值的实验设定值 为20％、30％、40％、50％、60％、70％和80％。滑动窗口大小以M值为初 始值，首先翻倍增长直到接近或变为M2，然后按等量线性增长。M值 和滑动窗口的取值组合如下表3所示：

表3M值和滑动窗口实验取值

每组实验参数都可生成一个特定的饱和控制策略，使用每一组参 数进行迭代搜索方式的关系发现实验，求取目标概念集的相关概念， 记录候选概念集的饱和值。同时使用枚举法计算得到标准相关概念集 合，然后根据召回率公式计算关系发现的召回率。

我们求取记录的饱和相关概念集概念数平均值，在4组不同的M 值下，以幅度阈值为横轴变量，以概念数值为纵轴，制作不同滑动窗 口下的饱和集概念数随幅度阈值的变化曲线。由于概念数会随着滑动 窗口的增大超出线性的速度增长，因此我们使用指数变化的纵轴，以 方便观察不同滑动窗口下的曲线。

图9示出了饱和相关集概念数平均值，如下图9包含的四幅小图 所示，从左至右，从上至下分别为M取值10、20、30、50时的饱和集 概念数曲线图，记为饱和集10，饱和集20，饱和集30和饱和集50。 从这四幅图中可以发现，当滑动窗口较小时，饱和集概念数会对幅度 阈值比较敏感，随着幅度阈值的增加而增大，但是随着滑动窗口的增 加，敏感度会大大减弱，甚至达到一定窗口大小时，饱和集概念数基 本不变，只是在幅度阈值较大时会有少量增长，但就增长的相对比例 而言基本可以忽略。

四幅图中都出现了较小滑动窗口饱和集超出较大滑动窗口的现 象，此现象可如下进行解释：当滑动窗口很小时，幅度变化监督器只 能监测相对较小的范围，当该范围小于概念相关度的局部区分能力， 就会导致迭代搜索持续不止，最终候选相关概念集的概念数就有可能 超过较大滑动窗口在同一幅度阈值下的水平。因此，滑动窗口要对着 M值得增大而适量增加，避免出现迭代搜索持续不止的情况。

接下来，对目标概念集的关系召回率计算平均值，在4组不同的 M值下制作滑动窗口和浮动阈值不同组合情况下的平均召回率折线图。 其中横坐标为滑动窗口大小，纵坐标为召回率，每个幅度阈值对应一 条彩色曲线。如下四幅图从左至右，从上至下分别为M取值10、20、 30、50时的召回率曲线图，记为召回率10，召回率20，召回率30 和召回率50。

从图10所包含的四幅图中容易看出，随着滑动窗口的增加，各幅 度阈值下的召回率变化趋势是相似的。当幅度阈值不变时，随着滑动 窗口的增大，召回率也会随之增加，但增速由快至缓，直到升至(0.95，1) 区间后，趋于平缓。当滑动窗口大小不变时，随着幅度阈值的增加， 召回率会有所上升，但是并不能在滑动窗口较小时达到一个令人满意 的值。

总结分析召回率实验结果可以得到以下结论：

1)当滑动窗口不变时，可通过增大幅度阈值的方法提高召回率， 但是幅度阈值的调节能力有限，若滑动窗口太小，仅通过调节幅度阈 值无法获取令人满意的召回率。

2)当幅度阈值不变时，可通过增大滑动窗口的方法提高召回率， 但是滑动窗口值无需一味增大，当窗口增大到一定程度时召回率达到 一定水平将不会再有明显的提升

3)当滑动窗口达到一定大小时，幅度阈值在实验中看不出明显的 作用。当幅度阈值极尽趋于零时可能会有召回率的下降，但是此种情 况不具有实际意义。

4)召回率在超过95％后就不再由明显的变化，当滑动窗口大小达 到一定数值时均可使召回率达到95％，而与幅度阈值的关系不甚明显。

增加浮动阈值并不能保证召回率一定会上升，在300万的基数上 增加滑动窗口大小会对计算效率产生很大影响，更何况换来的召回率 并不能保证相关系数的增加。因此，我们在95％召回的条件下选择更 小的滑动窗口。

图中的深色线标出在各M值下，召回率快速增长区和稳定区的边 界，实验证明不同的幅度阈值对边界的影响很小。因为一个确定的滑 动窗口大小对候选相关概念饱和控制策略非常重要，所以我们希望通 过分析拟合M值同边界的关系。记录M值与边界窗口的关系如下表4 所示：

表4M值和边界滑动窗口的对应关系

我们选用了常用拟合方法——多项式拟合对M值和边界滑动窗口 之间的关系数据进行处理，并对拟合结果进行简化，得出如下公式：

WinLen₂＝M²    (4)

虽然拟参考数据只有四对，但是公式对关系数据基本吻合，而且 对本方法的工程需求而言，确定的关系本身意义大于关系的精准性意 义。对于此滑动窗口值，可以满足关系发现的需要。

为了对比布尔模型下搜索关系发现、向量空间模型下枚举关系发 现和基于主权迭代搜索的关系发现等三种关系发现方法的时间效率和 召回率，我们设计了3*10组实验，每组实验对目标概念集中的所有概 念计算Top-M最相关概念，记录并计算平均召回率和用时，并制作曲 线图。

如图11所示，其中左边的一张为三种关系发现方法的效率对比 图，横轴为5～50的M取值，纵轴为执行关系发现的用时，由于三种 方法效率差别较大，超出了线性范围，故纵轴使用以10为底的对数刻 度，范围为0.0001秒到10000秒。

右边的一张为三种关系方法的召回率对比图，同样横轴为5～50 的M取值，纵轴为召回率百分比。

从效率曲线图可以看出，三种方法的时间效率关系是：布尔搜索 高于主权迭代搜索，而后者又高于向量对枚举方法。其中布尔搜索和 主权迭代搜索方法效率差别在同一量级，而向量对枚举法效率低了5～ 6个量级，即平均用时超出数十万倍。随着M值得增加，三种方法平 均用时均有增长。由于纵轴坐标为对数刻度，所以图中给出了y＝x的 对比线。从三条效率曲线斜率同对比线的比较可以看出，枚举法用时 基本随M值得增长成线性增长，而布尔搜索和主权特征迭代搜搜两种 方法的增长率高于线性，M值较小时尤为明显。

从召回率曲线图可以看出，三种方法的召回率关系是：向量对枚 举法高于主权迭代搜索，而后者又高于布尔搜索方法。由于向量对枚 举是召回率的对比标准，因此其召回率为100％。布尔搜索方法虽然具 有很高的效率，但是召回率不尽人意，总体平均水平低于50％，当M 较大时甚至无法达到30％。相比之下，主权迭代搜索的平均召回率超 出95％，而且对M值不敏感。

综合评价主权迭代搜索，效率虽然稍逊于同布尔搜索，但处于同 一量级，召回率却超出布尔搜索很多，接近100％。

上面对本发明所提供的基于主权迭代搜索的概念关系快速发现方 法进行了详细的说明。对本领域的一般技术人员而言，在不背离本发 明实质精神的前提下对它所做的任何显而易见的改动，都将构成对本 发明专利权的侵犯，将承担相应的法律责任。