XML文档分类中特征表达方法的研究

摘要：XML文档分类技术可以高效地管理海量存在的数据，XML文档同时拥有结构信息和文本信息。为充分利用XML特点，优化分类效果，在结构链接表达模型（structured link vector model，簡称SLVM）的基础上，提出了一种新的特征表达方法，即P-SLVM表达模型。该模型在传统的tf*idf的权重设置方式基础上，根据特征词在类中的分布情况，对特征词权重设置进行改进，同时利用泊松分布理论、特征词所在位置等对结构单元进行加权，以更为有效地表达结构信息和内容信息。实验结果表明，在P-SLVM表达模型下进行的XML文档的分类，有更好的分类效果。

（Collage of Computer Science and Technology，China University of Petroleum（East China），Qingdao，Shandong 266580，China）

Abstract：XML document classification technology can efficiently manage massive data，XML documents have both structural and textual information. In order to make full use of the characteristics of XML and optimize the classification effect，this paper proposes a new feature expression method based on structured link vector model （SLVM），namely P-SLVM expression model. Based on the traditional tf*idf weight setting method，the model improves the feature word weight setting according to the distribution of feature words in the class，and uses the Poisson distribution theory and the location of the feature words to weight the structural units. To more effectively express structural information and content information. The experimental results show that the classification of XML documents under the P-SLVM expression model has a better classification effect.

Key words：XML document;classification; structure link model;tf*idf;Poisson distribution

在大数据时代的今天，对用作数据交换和传输标准的XML文档进行分析、归纳、整理，以提高数

据的利用率是非常必要的。分类技术是数据挖掘下的重要技术，能够提取文档特征，根据文档特征将

文档分到不同类别中，以提高数据管理的效率。其中的特征表达过程是用数字的形式提取文档文字信息的过程，是影响分类效果的关键的环节。

XML文档同时具有文本信息和结构信息，所以对XML文档特征表达不同于普通文本的表达，它需要同时表达内容信息以及结构信息。M.Zaki等人提出的XRules是挖掘各类文档的频繁子树形成规则分类[1]; Nierman等人提出的基于树结构进行

编辑距离[2]，用最小的编辑距离来衡量两个文档之间的相似度。这些都是提取结构特征进行分类，造成内容信息的丢失。当前广泛使用的向量空间特征表达模型[3]（Vector Space Model，VSM）是表达文档中每个开始标记和结束标记之间的文本内容特征，无法表达XML文档的结构特征。Yang等人提出

VSM表达模型的基础上进行扩展，将原本仅仅只能表达内容信息的向量表示转化为矩阵表示，以综合表达XML文档的结构信息和文本内容信息，这个特征表达模型解决了VSM模型只包含内容信息，不包含文档结构信息的问题。然而，这个模型并没有考虑不同的结构单元对文档的分类贡献度不同的问题，模型中使用的传统tf*idf并没有考虑特征词类别分布情况对分类结果的影响。

在结构链接表达模型的基础上，提出了一种新的特征表达模型P-SLVM，它对传统的tf*idf的特征词权重进行设置时，考虑特征词的类别分布情况，同时采用XML文档树的路径作为结构单元，根据不同的结构单元的位置，引入泊松分布进行权重的设置[5]。

XML文档有结构层次信息，可以转化为一个文档树的形式。图1是一个XML文档的片段及它的文档树形式。

现在对XML文档的分类普遍采用的方法是仅仅提取文档树中叶子节点上的内容特征信息，舍弃了XML文档的结构信息，造成信息的丢失。

……

…XML…

XML文档无法直接被现有的分类算法识别，通常需要将XML文档的特征提取转化为分类算法能识别的数字形式，这个过程叫做文档特征表达。特征表达模型的建立直接关系文档信息的提取，是影响分类效果的关键的环节。

向量空间模型[3]（Vector Space Model，VSM）是现在使用最广泛的文本表达模型，它将一个XML文档表示成特征向量的形式，特征向量中的每一维表示从文档中选取的特征词的特征属性值，也表示这个特征词在分类过程中的权重，表达公式如下：

其中，表示Dx文档x的特征向量，n表示这个文档特征词的数量。D

x（i）表示x文档中第i个特征词的特征属性值，特征值一般由公式TF*IDF来计算：

（k，j）是在文档Dj中所有特征词出现的总次数;D是文档集的文档数目;DF（wi）表示有特征词的文档的数目。从公式看出，一个特征词在某个文档中出现的频率越高，在总文档中出现的次数越少，这个特征词的特征向量值越大，也就是权重越大，越能区分文档类别。

VSM表达模型仅仅表达文档的内容信息，对普通文本分类有很好的分类效果。但是，对于XML文档，如果直接使用VSM模型，则会丢失XML文档结构信息，表达不充分。在VSM模型基础上提出了SLVM表达模型（Structured Link Vector Model）[4]。SLVM引入了结构信息，能够同时表示文档的结构信息以及内容信息。SLVM表达模型将XML文档分成一个个结构单元（标签、路径等），再把每个结构单元都表示成一维向量，对应VSM模型中的一个文档。这样，每个XML文档都用一组向量表示，形成矩阵形式。该矩阵综合体现了XML文档的结构与文本内容。

SLVM模型中结构链接向量[5]由三部分组成，分别是结构向量、链出向量和链入向量。链接向量用于表示不同文档之间的互相链入和链出关系，为文本挖掘算法提供更多的文档关系信息。由于本文的研究重点是改进XML文档的特征表示模型，所以我们仅考虑SLVM的结构向量。SLVM的结构向量由以下模型表示：

（j，i）是表示文档D中第个结构下的第j个特征词的权重，TF（wi，Dx .ej）表示特征词wi在Dx文档中的结构单元ej下的出现频率。

每个结构单元包含的特征词数量是不同的，为了消除其影响，将结构单元进行单位化，其公式如下：

用特征模型表达的文档可以直接被分类算法识别。当前，有很多分类算法可用于XML文档分类，决策树[6]、贝叶斯[7]、人工神经网络[8]、支持向量机[9]、极限学习机[10-11]等，其中神经网络是分类效果较好的算法之一。因为分类算法并不是本文研究的重点，所以我们选择了BP神经网络作为分类器。这里，对其原理进行简单分析。

BP神经网络模型如图2所示，模型分为三层结构：输入层、隐藏层和输出层。其分类过程分为两个阶段，第一个阶段是数据的前向传播，指的是数据从输入层到隐藏层再到输出层的过程;第二个阶段是误差的反向传播，指的是根据实际和期望的偏差值经输出层到隐藏层再到输入层不断期间的权重和偏置的过程。

前向传播过程比较简单，上一层节点用表示下一层的节点则用yj表示，wij表示节点xi和节点yj之间的权重，bj是节点yj的阈值，f（）是激活函数，通常是Sigmoid函数。下一层节点yj的值为：

这是前向传播过程。反向传播过程是通过实际结果和期望结果的差值，不断反馈调节权重和阈值，以达到最小的误差值。期望结果用dj表示，实际结果是yj，误差函数E为：

BP神经网络是基于梯度下降的，以目标的负梯度方向进行调整。根据误差函数，wij和bij的修正值为：

SLVM特征表达模型将XML文档的文本内容和结构内容都引入了分类中。但是，单纯以节点为结构单元并没有考虑节点位置的作用，已经证明了使用路径作为结构单元的分类效果比使用节点作为结构单元的分类效果要好[12]。这里，我们选择了效果更好的路径作为结构单元，进行我们的改进实验。

基本思路有二。一是作为结构单元的路径长度应该是影响该结构单元的权重。XML文档文本内容信息只出现在文档树的叶子节点中，也就是说，特征词只存在于文档树的叶子节点，因而路径长度代表了特征词所在文档树的深度。同一特征词的深度不同，对于文档的表达能力也就不同。路径越长，包含的文本内容离根节点越远，对文档的描述能力越弱，对分类的贡献度越小。例如图1中，在articles/article/title和articles/article/content/chapter两个路径都有同一个特征词XML，但显然article1更可能是XML的類别。二是不同的路径本身对分类的贡献程度也是不一样的。比如，某XML文档中出现了“赛制”一类的路径，很可能该文档属于体育类新闻。通过下面公式给不同的结构单元赋予不同的权重，来充分利用XML文档的结构信息。

（i）长度，k是一个小于1的调节因子[13]。特征词所经过的路径越短，其结构单元权重越大，结构单元内的特征词越接近根节点，越能代表文档分类。由于每个XML文档树深度都可能是不同的，为防止异常情况，比如文档树T1深度为3，T2深度为10，但在T1中路径长度为3的特征词比在T2中路径长度为4的权重大，可对lp

p（i）表示路径本身的权重。不同的路径对分类的作用也不同，这里我们引入泊松分布[15]来计算。

在信息检索领域，泊松分布用于选择有效的查询词语。这里，我们用来衡量路径对于文档分类的作用。根据泊松分布，如果一个路径被设置较大的权重应具备两点特征：第一个是该路径所携带的信息与这个文档所属类别应该存在很大的关联度，即该路径的出现和文档属于某个类别并不是独立的。因为泊松分布预测独立事件发生的概率，所以该路径在这个类别的文档中的分布就应该偏离泊松分布，偏离程度越大，路径与文档所属类别的关联度就越大，权重设置应该越大;另一个特征是该路径在非这个类中应该服从泊松分布。这是因为这个路径与非这个类的文档之间不应该存在依赖关系，该路径的出现是随机独立事件，应该被泊松分布所预测。根据以上分析，可使用以下公式为路径赋予权重：

这里，aij是包含路径pi同时属于类别cj的文档数目，bij是不包含路径pi同时属于类别bij的文档数目，cij是包含路径pi同时但不属于类别cj的文档数目，dij是不包含路径pi同时不属于类别cj的文档数目。

p（pi，cj）能够反映一个特征词偏离泊松分布的程度，可用其数值表示该路径跟一个类的依赖程度。

根据公式（2），特征词在文档中出现的频率越高，tf越大;特征词在总文档中出现的文档数越多，则idf越小。但这个公式存在不完善的地方，下面进行详细的分析。表1给出了两个类、四个文档中特征词a、b、c的分布情况。

首先，特征词a均匀分布在一个类中，特征词b则分散在两个类中，显然，特征词a更能区分文档的类别，但是，根据公式（2.b），idf（a）和idf（b）相等，并不合理。再者，特征词c集中分布在一个文档中，idf（a）小于idf（c），因而特征词c的权重比特征词a的大，这同样不合理。可见，并不是一个特征词在总文档中出现的频率越高，这个特征词对文档分类的贡献度越大小，而应该是在非这个类中出现的频率越高，对这个类的分类贡献越小。同时，还应该考虑特征词在类中分布是否均匀。改进的TF*IDF公式为：

其中，IDF（wi，cj）表示在类cj中出现特征词 wi的文档数量，D（cj）表示测试集中类cj的文档数量，D（wi，cj）是特征词wi在类cj中出现文档数量。是特征词在类中分布的均匀程度，如果是均匀分布则数值越大，表明这个特征词越能代表这个类。是特征词wi在一个非cj类中的出现情况，如果关键词wi在非cj类中出现的次数多，数值越小，则权重越小。改进后的TF*IDF值引入了特征词在类中分布情况使特征词的权重设置更加合理。

用分类算法对表达模型的效果进行了验证。文档的预处理是在MyEclipse环境下进行的。分别采用SLVM和P-SLVM表达模型，经过预处理生成不同的输入数据。分类过程则是在Matlab环境下进行的。测试用的数据集有两组，分别来自维基百科[17]和Reuters-21578。在两个数据集中，分别挑取10个类别，每个类别随机挑选500个XML文档，按照4：1的比例分别划分训练集和测试集。

實验中，首先对数据进行清洗，包括分词、去停用词、同义词转化等。其次是文本特征选择。原始数据维数很高，有些特征词对于分类作用很小，需要选择出对文档分类贡献度大的特征词。特征选择的方法有很多[17-18]，选择了效果比较好的卡方统计。再者，分别使用SLVM和P-SLVM表达模型将处理好的数据集转换为分类算法能识别的形式。最后，用bp神经网络分类算法进行测试。测试时，激活函数采用Sigmoid函数，调节因子k为0.8。

分类效果的评价采用了准确率（precision）、召回率（recall）及F1[19]，其计算方式是：

其中，TP表示一个类中分类正确的文档数，FP是错误将其它类的文档分到这个类中的文档数，FN是这个类中被错误分到其它类的总数。图3、图4分别是在测试集1和2上的分类准确率的测试结果。

百科数据集或者Reuters-21578数据集上，无论隐藏层的节点数为多少，改进后的P-SLVM表达模型的分类准确度都高于SLVM表达模型。

可以看出，采用改进的P-SLVM表达模型进行XML文档分类，准确率、召回率和F1指标都优于SLVM表达模型。

针对XML文档同时包含结构和内容的特点，提出了一种新的特征表达模型，在SLVM的基础上，引入了特征词在类中的分布情况，使tf*idf权重设置更合理。同时，用路径作为结构单元，引入了泊松分布、特征词在文档树的深度等对结构单元进行权重的设置。实验表明，改进的表达模型在准确率、召回率以及F1等指数上比之前都有所提高，有更好的分类效果。

[1] ZAKI M，AGGARWAL C.Xrules：an effective stucturan classifier for XML data[C]//Proc of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2003.

[2] NIERMAN A，JAGADISH H V. Evaluating structural similarity in XML documents[C] // Proceedings of the ACM SIGMOD International Workshop on the Web and Databases，2002，2：61-66.

[3] SALTON，G M J，MICHAEL J.Introduction to modern infornation retrieval[M]. New York：McGraw-Hill Inc，1983.

[4] YANG J W，CHEN X O .A semistructured document model for text mining .Journal of Computer Science and T echnology，2002，17（5）：603-61.

[5] BI X，ZHAO X，WANG G，et al. Distributed extreme learning machine with kernels based on mapReduce[J]. Neurocomputing，2015，149：456-463.

[6] RUGGIERI S. Efficient C4.5[J]. IEEE Computer Society，2000，14（2）：438-444.

[7] JIANG L，LI C Q，WANG S S，et al. Deep feature weighting for naiveBayes and its application to text classification[J]. Engineering Applications of Artificial Intelligence，2016，52 ：26-39.

[8] RAMASUNDARAM S， V S P. Text categotization by backpropagtions neragations netword[J]. International Journal of Computer Application，2010，8（3-4）：1-5.

[9] RAMESH B，SATHIASEELAN J G R. An advanced multiClass instance selection based support vector machine for text classification[J] Procedia Computer Science，2015，57：1124-1130.

[10] HUANG G B，ZHU Q Y，SIEW C K. Extreme learning machine：theory and applications[J]. Neurocomputing，2006，70（1）：489-501.

[11] HUANG G B.An insight into extreme learning machines：random neurons，random features and kernels[J] Cognitive Computation，2014，6 （3）：376-390.

[12] 基于核方法的XML文檔自动分类[J].计算机学报，2011，34（2）：353-359.

[13] ZHANG L J，LI Z H，CHEN Q，et al. Classifying XML documents based on term semantics[J]. Journal of Jilin University：Engineering and Technology Edition，2012，42（6）：1510-1514.

[14] GAO N，DENG Z H，JIANG J J，et al. Combining strategics for XML retrieval[C]//Proceedings of INEX Conference，Berlin：Springer-Verlag，2011：319-331.

[15] HIROSHI O，HIROMI A，MASATO M. Feature selection with ameasure of deviations from Poisson in Applications，2009，36（6826-6832）.

[16] DENOYER L，GALLINARI P. The Wikipedia XML corpus [J]. ACM SIGIR Forum，2006，40（1）：64-69.

[17] CANTU-PAZ E，NEWSAM S，KAMATH C. Feature selection in scientific application[C]. In Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2004：788-793.

[18] CHEN X，WASIKOWSKI M. FAST：a ROC-based feature selection metric for small samples and imbalanced data classification problems[C]. KDD'08，2008，124-132.

[19] SEBASTIANI F.Machine learning in automated text categorization[J]. ACM Computing Surveys，2002，34（1）：1-47.