依赖模糊C均值聚类的网络数据库特定数据检索算法

胡六四

(安徽电子信息职业技术学院 软件学院，安徽 蚌埠 233000)

在我国，伴随着计算机技术和大数据的飞速发展，网络数据目前已经成为数据库与文件管理系统的主要工具[1-2]。网络数据库具有面向多个客户被同时共享访问的特点[3]，网络数据库扩大的同时网络数据库的结构拓扑也发生了改变，在这种情况下，使用一个有效的聚类算法从网络数据库内搜索到需要的信息成为目前急需解决的问题[4-5]。但是，网络数据库内的数据信息搜索能够从客户寻求服务的操作过程开始，提高网络数据库的搜索速度是行之有效的策略[6]。

本文使用模糊C均值聚类来对网络数据库特定数据的检索，将网络数据库特定数据检索问题转化为一系列面向模糊C均值聚类问题进行检索，从而考查本文所提算法检索复杂网络数据库特定数据的能力。

1　网络数据库特定数据检索算法

如图1所示，数据与POS标注依次出现于第一与第二列中，在第三列中则表明了此处数据是否和奇周边数据存在数据关系。当此数据与其左边邻近数据存在数据关系时，以“LH”(代表“父节点位于左处”)来表示；当此数据与其右边数据存在关系，以“RH”表示；当不存在上述关系时，则将其表示为“O”。其中，“_”符号代表其后边字串是当存在数据关系时所对应的数据关系种类。

图1邻近数据关系检索器图2邻近数据关系的标注形式Ⅰ图3邻近数据的关系标注形式Ⅱ

本文从构建树的数据结构层面进行分析，先对每个数据序列是否跟其父节点存在相邻关系并进一步判断是否为完整子树节点，当满足上述条件时则为其标注数据关系，具体见图2。

通过对比图1与图3可知，图3内的标记“O”具有明显歧义性质。该标记一方面可以表示该数据和邻近数据间无数据关系，另一方面也能够表示该数据和邻近数据间存在数据关系，只是在当前条件下不能对其进行归约处理而只可将其通过“O”的形式进行标记。这是因为存在没有找齐该数据的所有数据类型(例如，“主演”与“的”)或者是在同一方向上的连续数据关系只能被归约为最低模型策略而受到限制(例如，“知名”这类数据)。为将此类歧义充分消除，可以重新回归至图1的方式，对于具有数据关系的所有相邻数据都需标注。为构建树结构，需利用专门的归约决策标注器对规约数据进行标注。图4(a)中的最后一列“r”代表此数据符合归约条件，可以构建相应的模型。

为确保能够以最快速度对网络数据库特定数据进行全局搜索，选择CRF模型作为归约决策的标注器。但是在实际情况下，通过这一顺序标注的方式无法达到对全局进行真正的快速搜索目标。所以我们对数据关系以及归约决策进行统一标记，并通过“_”符号进行连接，图4(b)显示了以标注器构建序列的具体模型。采取这一标注方式的另外一个原因是可以防止在归约决策过程中对于数据关系的标注产生过度依赖。

图4邻近数据的关系标注形式Ⅲ

从另一层面考虑，采用以上标注形式检索“邻近”数据的关系时更符合网络数据库特定数据的直接表达方式，同时将归约决策进行独立处理后，也可以更加清晰地表达归约约束。从图5看出，可以利用流程图的方式对复杂英语进行整体检索。

当把网络数据库特定数据的邻近关系及其归约决策标注都输入之后，其中一些数据被归约成邻近数据的孩子，而剩余数据则在完成重新组合后进入后续检索过程，直至剩余单一数据或至已经没有被标记成可归约类型的数据为止。

2　实验结果分析

本实验在英语标准库上完成。相关英语数据从宾州树库的《华尔街日报》语料中选取，具体划分标准为：以02～21节作为训练样本，以22节作为开发集，并对23节进行测试(总共包含的数据数量为53624)。通过Penn2Malt工具获得统一的中心数据提取规则并得到数据关系集合，该模型中总共包括了12种不同的数据关系。对于测试集与开发集上的POS标注则通过MXPOST分析软件自主获取，对于测试集进行标注可以实现高达97.41%的正确率。

图5检索算法的流程示意图

本文实验将分割策略应用到了MaltParser中，以此提高检索速率，根据后续输入数据的POS标注对SVM分类器进行分割从而使其形成许多小分类器，同时将各分类器的训练案例数量设定为至少1000。Yamada03对应的特征选取窗口宽度是6，并且将该数据加入到数据关系特征集中，SVM分类器是在对左焦点数据进行POS标注的划分之后再进行训练。

如下所示，表1与表2中分别显示了5个基线系统与不同检索模型对英语数据集进行测试结果。其中，R代表模型中各训练实例对应的数据关系标记数量。以Viterbi算法为基础的CRF序列的模型复杂度是O(R2n)。基于模型算法在搜索输入网络数据库特定数据时所需的模型个数上限为n，对应的算法复杂度是O(R2n2)。

表1　不同模型的网络数据库特定数据检索测试结果

表2　各基于模型的模型英语检索结果

对上述各个模型进行对比分析可知，基于模型算法与基于转换算法具有更高的完全匹配率与数据正确率。

检索表2结果显示，采用依次标注法(LDP2)时，由于无法达到最快的全局结构检索速率，并且检索的精度也不高；选择分离模型则可以根据各个模型的特征获得良好的性能；LDPnrAll归约可以在当前模型中生成完整数据，因此模型中将存在长度大于1的网络数据库特定数据，导致线性模糊C均值聚类的性能受到限制；对于LDPdiv而言，其能够有效消除标记“O”引起的歧义，因此有助于提高检索精度。实际上，建立在模糊C均值聚类之上的网络数据库特定数据检索算法具有很强的适应性，当语料标注集较大或需要高搜索效率时，可利用拆分标注与压缩标注集的方式来达到所需的性能；同时，自然语言数据具有聚集性，检索遇到高模型情况时，序列长度将快速降低，此时如果网络数据库特定数据长度较大也依然不会占用较多的时间。

3　结论

本文提出了一种依赖模糊C均值聚类的网络数据库特定数据检索算法。以网络数据库特定数据为检索单位，自底向上构建网络数据库特定数据的各向异性模型。实验结果表明：本文网络数据库特定数据检索算法在检索精度方面和当前各主流算法相近，准确率则介于基于图与基于转换算法间，同时可以达到极高的检索速率。该算法对于网络数据库特定数据进行搜索处理时将表现出极大的优势。

(编辑：严佩峰)