一种行业领域词库标识树的正确性检测算法研究

张志强 王伟钧 杨晋浩 周晓清 郑加林

摘 要： 在知识挖掘应用中，行业领域数据识别是知识挖掘的重要过程。对大量的行业领域数据进行数据识别需要借助领域词库标识树来完成，而影响数据识别准确率的重要因素是领域词库标识树构建的正确性。领域词库数据量一般很大，以其构建的领域词库标识树结构复杂，在复杂结构的标识树中通过已有的检测方法判断其正确性往往很困难。为了解决这个问题，提出一种词库标识树的正确性检测算法。该算法通过构建词库特征向量空间矩阵，计算树节点的相关性系数来自动检测树节点构建的正确性，同时可以根据判定阈值来确定正确性判定范围。实验结果表明，无论树结构如何复杂，该算法都能高效准确地实现标识树的正确性检测和发现错误。

关键词： 词库标识树； 正确性检测； 特征向量空间矩阵； 相关性系数； 知识挖掘； 数据识别

中图分类号： TN911.23?34； TP391.1 文献标识码： A 文章编号： 1004?373X（2018）18?0088?04

Research on correctness detection algorithm for thesaurus identification

tree in profession domain

ZHANG Zhiqiang， WANG Weijun， YANG Jinhao， ZHOU Xiaoqing， ZHENG Jialin

（School of Information Science and Engineering， Chengdu University， Chengdu 610106， China）

Abstract： In the knowledge mining application， the data recognition in profession domain is an important process of knowledge mining. The identification of massive profession domain data is accomplished by means of the identification tree of the domain thesaurus. An important factor of affecting the accuracy rate of data recognition is the construction correctness of the identification tree of the domain thesaurus. As the data quantity of the domain thesaurus is generally large， the constructed identification tree of the domain thesaurus has a complex structure， which makes it difficult to judge the correctness of the identification tree with a complex structure by using the existing detection methods. A correctness detection algorithm for the thesaurus identification tree is proposed to solve the above problem. In the algorithm， the correlation coefficient of tree nodes is calculated to automatically detect the construction correctness of tree nodes by building the space matrix of thesaurus feature vectors， and the judgment range of correctness is determined according to the decision threshold. The experimental results show that， no matter how complex the tree structure is， the algorithm can effectively and accurately implement the correctness detection of the identification tree and find errors.

Keywords： thesaurus identification tree； correctness detection； feature vector space matrix； correlation coefficient； knowledge mining； data identification

0 引 言

在知识挖掘中，利用知识树进行知识挖掘和提取是目前研究的方向，其可应用于行为挖掘和图像检索[1?2]等。在树的构建方面，目前有如下策略：基于文本聚类的构建方法[3]、基于文本词汇功能描述的构建方法[4]、基于汉语自动句法分析和语言知识库的构建方法[5]、基于文本敏感信息过滤算法的构建方法[6]等。针对行业领域数据的知识挖掘应用，利用行业领域标准对大量的行业领域数据进行数据识别也是知识挖掘的重要过程。数据识别过程中，首先需要利用分词算法对行业领域标准文档进行分词并建立领域词库；然后根据领域词库中的所有词汇按照类别构建领域词库标识树；最后根据数据识别算法利用词库标识树对行业领域数据进行自动识别。显然，構建无识别歧义的正确标识树是数据识别高准确率的保证，同时，标识树的正确性又与分词的准确性密切关联。为了能够检测和发现树的错误信息，目前已提出的检测方法有：基于规则的方法检测[7]、基于计算语句相似度的检测方法[8]、基于文本相似度计算的检测方法[9]、基于词汇相似度计算的检测方法[10]等。领域词库数据量一般比较大，通过词库构建的标识树结构复杂，利用已有的方法来判断标识树的正确性一般比较困难。为了能够高效准确地进行标识树的正确性检测，本文提出一种基于树节点间相关性系数计算策略的判定方式来实现标识树正确性检测算法。在算法中利用词库特征向量空间矩阵计算树节点间相关性系数，来判断树节点间的相似度，从而有效地进行树的正确性检测，发现存在识别歧义的错误信息。实验结果表明，该算法能够高效准确地检测并发现树的错误信息。

1 检测算法的目标

检测算法的目标是通过领域词库构建词库标识树，并对标识树进行高效准确地正确性检测，然后根据检测结果发现，树中有识别歧义的树节点信息，根据错误信息改进前期的分词算法。检测算法在数据识别处理流程中的阶段如图1所示。

2 检测算法的设计

本文算法进行检测的关键是构建词库特征向量空间矩阵，通过该矩阵获得标识树中任何树节点的词汇特征向量空间，然后利用词汇特征向量空间计算标识树中各节点间的相关性系数。

2.1 词库特征向量空间矩阵的构建

为了获取词库中词汇的相互关联信息，需要构建词库中每个词汇的特征向量空间，将所有词汇特征向量空间组合在一起构建词库特征向量空间矩阵。词汇特征向量空间需要由词库标识树来构建。构建词库标识树的策略是：首先自定义根节点；然后将词库中的所有词汇类别作为树的非叶子节点、所有词汇作为叶子节点构建标识树。以本文实验采用的政府采购信息样本数据为依据，构建的词库标识树结构如图2所示。

在图2中，“服务业”一词的类别数据在词库中为“A01”，为其构建为一个非叶子节点、“交通运输”一词的类别数据在词库中为“A0101”，为其构建一个非叶子节点，词汇构建为叶子节点；依次类推，将词库中所有的词汇数据和词汇类别数据构建标识树。标识树的节点层次体现了不同词汇的类别归属关系，如“交通运输”归属于“服务业”。这种归属关系也是后期数据识别的重要判定依据。根据词库标识树构建词库特征向量空间矩阵[T（m×n）]。其中[m]=[{词库中的所有詞汇集合}]，[n={词库中所有词汇类别数据集合}]。当某个词汇是标识树的叶子节点时，如图2中的“交通运输”，其在树中祖先节点集合为{“[A]”，“[A01]”，“[A0101]”}，在矩阵[T]中，将该词汇所在行的对应列“[A]”，列“[A01]”，列“[A0101]”的值分别置1，其余列的值全部置0。根据这种策略，构建的矩阵[T]定义为：

式中：word1，word2等是词库中的所有词汇；A，A01，A0101等是词库中词汇所属类别数据。从矩阵[T]可见，词汇“交通运输”的特征向量空间[S′]（“交通运输”）={1，1，1，0，0，…}，其为[T]中对应行向量值。同理，根据矩阵[T]，词汇类别数据“[A01]”的特征向量空间[S]（“[A01]”）={1，0，1，1，…}，其为[T]中对应列向量值。根据矩阵[T]，可以获取词库中任意词汇和词汇类别数据的特征向量空间。

2.2 矩阵存储的处理

当[n]值很大时，矩阵[T]在存储数据表时会出现“[n] >系统数据表列数最大值”错误，采用多表关联方式解决相关问题。本文构建了词汇表、词汇类别表、词汇向量空间表，3个表的ER图设计如图3所示。

通过3个表的关联，矩阵[T]从3个表中还原。不管矩阵[T]的规模有多大，矩阵[T]都可以存入数据库。

2.3 树节点相关性系数计算

标识树的同层非叶子节点间相关性系数是判定数据识别歧义的重要标准，树节点[nodei]与[nodej]间相关性系数[ρi，j]定义为：

[ρi，j=Ai·Ajqi×qj，Ai=S（nodei），Aj=S（nodej）， 1≤i≤n，1≤j≤nAi·Aj=k=1mAi[k]×Aj[k]，qi=k=1mAi[k]×Aj[k]， qj=k=1mAj[k]×Aj[k]] （2）

式中，树节点[nodei]和[nodej]的相关性系数[ρi，j]的值与节点的特征向量空间[S]密切联系。树中同层非叶子节点[nodei]和[nodej]的相关性系数[ρi，j]表示从根节点到节点[nodei]之间构成的分支树所属词汇集合与根节点到节点[nodej]之间构成的分支树所属词汇集合的相似度。如果标识树中不同分子树所属词汇集合的相似度较高，会出现识别歧义问题。当[ρi，j]=0，表示两个分支树所属词汇集合完全不相同，其相似度为0，从理论上说这一种最理想的情况；当[ρi，j]=1，表示两个分支树所属词汇集合完全相同，其相似度为1，从理论上说这是一种最坏的情况；当[ρi，j>a]，表示两个分支树所属词汇集合的相似度大于[a]，这里[a]为判定阈值，说明节点所属词汇集合存在识别歧义问题。

2.4 算法的实现

算法实现的步骤如下：

1） 设定检测标识树的层次数[t]，其作为参数传递到算法中处理。

2） 根据数据库中已有的领域词库构建词库标识树。

3） 根据词库标识树构建词库特征向量空间矩阵[T]，并存入数据库中。

4） 构建树的第[i]层（根层忽略）的同层所有非叶子节点集合。

5） 从节点集合中任意选择两个不同节点，从矩阵[T]获取节点的特征向量空间，计算该节点对的相关性系数[ρi，j]，并存入数据库中，用于数据分析。

6） 将[i]的范围设定为1～[t]，循环从步骤4）开始执行，直到[i]范围执行结束。

3 算法实验

算法采用Java编程实现，算法测试的样本数据基于政府采购标准信息数据，并利用前期的分词算法对这些行业领域标准进行分词，构建了领域词库并存储在数据库中。测试的样本数据量如表1所示。

3.1 实验结果及分析

利用检测算法对样本数据词库构建的词库标识树进行检测，检测层次参数设为4（表示检测从第1层到第4层的树节点信息），根所在的层忽略不计，运行的测试结果如表2所示。

在表2中，相关性系数为1的节点对的数据记录条数为16，说明标识树中有16个节点对的分支树所属词汇集合的相似度为1。例如，算法检测出“A031103”和“A170203”两个同层树节点对的相关性系数为1，通过对标识树的分析发现，两个节点的分支树所属词汇集合均为{“纤维”}，其在标识树中如图4所示。在图4中，这两个树节点的特征向量空间相同，即：[S]（“A031103”） =[S]（“A170203”），从而使得相关性系数[ρi，j=1]，显然在后期识别“纤维”词汇时会出现识别歧义的问题，其他15个节点对也有类似的问题。对于其他相关性系数值范围的节点对，如图5中“A031016”和“C220203”两个同层树节点对的相关性系数为0.707 11；图6中“C0205”和“C1005”两个同层树节点对的相关性系数为0.408 25。从图5和图6可知，当同层树节点对的相关性系数[ρi，j>a]时，表示相应的两个节点在标识树中的所属词汇集合中有相同词汇数据，其可能影响后期数据识别的准确度。从实验结果分析可以看出，不管标识树的结构如何复杂，算法都能准确高效地检测标识树的正确性、发现错误。

3.2 判定阈值的下界设定

确定判定阈值[a]的下界对数据分析非常重要。本文以相关性系数值为x轴，以数据记录条数为y轴，将相关性系数值为0～0.1范围的数据量作为在x轴0.1刻度的数据采集，相关性系数值为0.1～0.2范围的数据量作为在x轴0.2刻度的数据采集、依次类推，数据变化曲线如图7所示。从图7可见，当[0.3≤ρi，j≤1]时，数据量的变化幅度不大，将判定阈值[a]的下界设定为0.3时较为合适。有时确定判定阈值还需要行业领域数据特点、识别要求、词性、词频等因素综合考虑。

4 结 语

标识树的检测是数据识别过程中非常重要的处理流程。本文提出的标识树正确性检测算法，其通过词库特征向量空间矩阵计算树中同层非叶子节点的相关性系数来判断和发现标识树中存在识别歧义的错误信息。实验结果表明，不管树结构如何复杂，算法都能高效准确地检测和发现错误。

参考文献

[1] 王东波，朱丹浩.面向汉语句法功能分布知识库的词汇类别知识挖掘研究[J].现代图书情报技术，2013，29（3）：33?37.

WANG Dongbo， ZHU Danhao. Research of mining the word category knowledge for Chinese syntactic function distribution knowledge base [J]. New technology of library and information service， 2013， 29（3）： 33?37.

[2] 陈晓宁.一种基于词汇树结构的图像检索方法研究[J].电子世界，2013（9）：172?173.

CHEN Xiaoning. A method of image retrieval based on lexical tree structure [J]. Electronics world， 2013（9）： 172?173.

[3] 钟将，刘杰.一种基于文本分类的知识树自动构建方法[J].计算机应用研究，2010，27（2）：475?478.

ZHONG Jiang， LIU Jie. Automatic construction of knowledge tree based on text clustering [J]. Application research of computers， 2010， 27（2）： 475?478.

[4] 张明杰，张跃，姚天顺.一种基于词汇功能描述的树库构建方法[J].东北大学学报（自然科学版），2000，21（3）：263?265.

ZHANG Mingjie， ZHANG Yue， YAO Tianshun. Constructing tree?bank based on lexical functional description [J]. Journal of Northeastern University （Natural science）， 2000， 21（3）： 263?265.

[5] 王东波，朱丹浩，谢靖.面向汉语自动句法分析的语法知识库构建[J].现代图书情报技术，2011，27（4）：42?47.

WANG Dongbo， ZHU Danhao， XIE Jing. Constructing the grammar knowledge database orienting Chinese automatic sentence analysis [J]. New technology of library and information service， 2011， 27（4）： 42?47.

[6] 邓一贵，伍玉英.基于文本内容的敏感词决策树信息过滤算法[J].计算机工程，2014，40（9）：300?304.

DENG Yigui， WU Yuying. Information filtering algorithm of text content?based sensitive words decision tree [J]. Computer engineering， 2014， 40（9）： 300?304.

[7] 史林林，邱立坤，亢世勇.基于规则的依存树库错误自动检测与分析[J].北京大学学报（自然科学版），2016，52（1）：58?64.

SHI Linlin， QIU Likun， KANG Shiyong. Rule?based detection and analysis of annotation errors in dependency Treebank [J]. Acta Scientiarum Naturalium Universitatis Pekinensis， 2016， 52（1）： 58?64.

[8] 杨喜权，国頔娜，胡加·托和塔森，等.基于领域本体的词语相似度计算[J].计算机应用，2009，29（z1）：164?166.

YANG Xiquan， GUO Dina， TOHTASEN Hoja， et al. Word similarity computation based on domain ontology [J]. Journal of computer applications， 2009， 29（S1）： 164?166.

[9] 王晋，孙涌，王璁玮.基于领域本体的文本相似度算法[J].苏州大学学报（工科版），2011，31（3）：13?17.

WANG Jin， SUN Yong， WANG Congwei. Text similarity computing based on domain ontology [J]. Journal of Soochow University （Engineering science edition）， 2011， 31（3）： 13?17.

[10] 崔诚煜，冉晓旻，冯琳.基于领域本体的专业领域词汇相似度算法[J].信息工程大学学报，2014，15（1）：68?73.

CUI Chengyu， RAN Xiaomin， FENG Lin. Calculation of field term similarity based on domain ontology [J]. Journal of Information Engineering University， 2014， 15（1）： 68?73.