摘? 要? 支持向量机(SVM)方法通过核函数进行空间映射并构造最优分类超平面解决分类器的构造问题, 该方法在文本自动分类应用中具有明显优势. XML 文档是文本内容信息与结构信息的综合体, 作为一种新的数据形式,成为当前的研究热点. 文中以结构链接向量模型为基础, 研究了基于支持向量机的 XML 文档自动分类方法, 提出了适合 XML 文档分类的核函数及其参数的学习方法, 从而将 XML 文档的结构分析与内容分析有机地结合起来.在 INEX 数据集上的测试结果表明, 该方法的分类准确性明显高于 INEX 评测中所公布各方法的评测结果.

关键词? XML 文档; 文档分类; 核函数; 支持向量机; 文档模型

1 引  言

由于具有结构化、 可扩展性、 跨平台性等特点,XML( eXtensible Markup Language) 逐渐成为信息存储与交换的主要格式, XML 文档数量随之迅速增长. XML 方面的研究工作迅速展开, 从最初的 XML标准研究, 发展到 XML 文档存储、 检索与管理等多角度研究, 而面向 XML 文档集的智能分析挖掘成为当前的研究热点.2002 年, 欧洲 DELOS 组织成立 INEX?( Initi?ative for the Evaluation of XML retrieval) 评测机构, 每年组织 XML 文档检索方面的评测, 获得IEEE 计算机学会的认可与支持. 2005 年底, 首次举行 XML 文档挖掘评测? XML Document MiningChallenge??.

XML 文档是文本内容信息与结构信息的综合体, 作为一种新的数据形式 XML 文档分析区别于传统的文本分析的关键在于结构信息与文本内容的综合利用.目前, XML 方面的研究成果主要集中于 XML标准、 数据模型、 存储、 检索等方面, 在面向 XML 文档集的文本挖掘方面的研究成果还相对很少. Yi 等人提出了一种用于半结构化文档分类的扩展向量模型, 它采用嵌套定义的向量来描述文档元素, 并在此模型基础上利用概率统计方法进行文档分类[ 1];Zhang 等人提出一种采用编辑距离进行 XML 文档结构相似度计算的方法 [ 2] ; Denoyer 等人研究了利用贝叶斯网络模型进行半结构化文档分类的方法 [ 3] ;Kc 等人研究了通过自组织映射技术进行 XML 文档自动聚类和分类的方法 [ 4] ; Yong 等人采用图形神经网络进行 XML 文档分类取得了较好的实验效果 [ 5] .支持向量机( SVM)[ 6]是公认的具有较好效果的文本自动分类方法之一[ 7]. 但是基于支持向量机的文本自动分类方法考虑的仅是文本内容信息, 不涉及文本的结构信息.

本文作者在文献[ 8] 中对经典的文本向量空间模型[ 9]进行了扩展, 提出了结构链接向量模型, 综合描述了 XML 文档中的结构信息与内容信息.本文研究了采用支持向量机对 XML 文档进行自动分类的问题, 提出了适合 XML 文档分类的核函数以及基于支持向量机回归学习进行核函数参数学习的方法. 在 INEX 数据集上的测试结果表明, 该方法具有很好的分类效果, 分类准确性明显高于INEX 评测中公布的各方法的评测结果.本文第 2节简单介绍支持向量机及结构链接向量模型; 第 3 节提出基于支持向量机的 XML 文档自动分类的基本方法; 第 4 节讨论基于支持向量机回归学习进行核函数参数优化的方法; 第 5 节给出本文方法在 INEX 数据集上的实验结果; 最后一节对本文工作进行总结.

2 ? 背景知识

2. 1? 支持向量机( SVM)支持向量机( SVM)[ 6]的基本思想是根据 Vapnik提出的结构风险最小化原理, 通过最大化分类间隔尽量提高学习机的泛化能力. 对于线性可分情况,SVM 给出一种用规划方法求解最大间隔的方法; 对于线性不可分情况, SVM 则利用核函数将原问题映射到高维空间, 从而转化成线性可分的问题. 考虑到求解最优分类面算法的性质, 在高维空间中, 只需进行内积运算即可.对于线性可分样本集:(x i , y i ); i= 1, 2, ?, n; x ? R d ; y ? {+ 1, - 1}满足y i [ (w ?x i ) + b] - 1?0; i= 1, 2, ?, n.SVM 训练的求解最优分类面问题可转换成如下二次函数的寻优问题:max?Q( ? )=?ni = 1? i -12?ni, j = 1 ?i ? j y i y j ( x i ?x j ) ? (1)约束条件:?ni = 1y i ? i = 0 和 ? i ? 0; i= 1, 2, ?, n.解该问题后得到最优分类函数:f ( x) = sgn{ ?ni = 1?*i y i (x i ?x)+ b * } (2)其中 b*是分类阈值.对于非线性问题, 通过非线性变换转化为高维空间中的线性问题, 在变换后的空间求最优分类面.设非线性映射为 ?: R d ?H . 在特征空间 H 中构造最优超平面时, 训练算法仅使用空间中的点积?(x i ) ? ?(x j ) , 而没有单独的 ?(x i )出现. 因此, 可通过核函数 K , K (x i , x j )= ?( x i ) ? ?( x j ), 实现非线性变换后的线性分类, 此时, 训练函数为max?Q( ? ) =?ni= 1? i -12 ?ni, j = 1 ?i ? j y i y j K ( x i , x j ) (3)相应的分类函数为f (x)= sgn?ni = 1?*i y i K (x i , x) + b * (4)

2. 2?向量空间模型(VSM)向量空间模型( VSM)[ 9]是一种常用的文档模型. 它以词语为维度构造一个高维空间, 每个词语为该空间的一个维, 每个文档被看作该空间中的一个向量.x= ?x (1) , x (2) , ?, x (n) ?T(5)其中 n 是文档集合中不同词语的个数.T FIDF[ 9]是 VSM 模型中一种常用的文档向量化方法, 它综合考虑了词语在单个文档中出现的频度和该词语在文档集合中出现的频度. x (i) = T F(w i , doc x )?IDF(w i ) ( 6)其中, TF(w i , doc x )是词 w i 在文档 doc x 中出现的次数; IDF( w i )= log(| D| / DF( w i )), | D| 是文档集合中文档总数, DF( w i ) 是包含词语 w i 的文档个数.IDF(w i ) 是词语 w i 全局特性, 用来体现词语 w i 区分文档的能力.在VSM 模型中, 两个文档 doc x 和doc y 之间的相似度通常采用相应的两个向量 x 和y 的点积表示.sim(doc x , doc y )= x?y=?ni = 1( x (i) ?y (i) ) ( 7)其中, x 和y 分别是文档 doc x 和doc y 对应的向量, n是文档集合中不同词语的个数.

2. 3? 结构链接向量模型(SLVM)VSM 模型能有效地描述文本内容, 广泛应用于文本检索与文本挖掘之中. 但是 VSM 模型不能描述文档中的结构信息.XML 等半结构化文档中包含丰富的结构信息,结构信息在半结构化文档检索与分析中具有重要价值. 为了能综合描述 XML 文档中的内容信息和结构信息, 本文作者在文献[ 8] 中对 VSM 模型进行了扩展, 提出了结构链接向量模型( SLVM) .SLVM 模型的基本思想是根据结构单元中的内容, 将 XML 文档中的每个结构单元看作一个向量, 类似于 VSM 模型的一个文档, 整个 XML 文档则被量化为一组向量, 以一个矩阵来表示, 从而达到将 XML 文档的结构分析与文本内容分析相结合的目的.SLVM 模型中结构链接向量由 3 部分组成: 结构向量、 链出向量和链入向量. 该模型中链出向量与链入向量是以链出目标资源和链入起始资源的结构向量进行表示的, 为简化论述突出重点, 本文仅考虑SLVM 模型中的结构向量.具体来说, 在 SLVM 模型中, 文档 doc x 被表示成一个矩阵x ? R n? m , 矩阵的每列为一个结构单元对应一个 n 维向量:x= ? x (1) , x (2) , ?, x (m) ? ( 8)x (i) = ?x (1, i) , x (2, i) , ?, x (n, i) ? T ( 9)其中, m 是 XML 文档中不同结构单元(如 XML 元素、 XML 结构树的结点路径)的个数, n 是文档集合中不同词语的个数. x (i, j) 的取值采用类似 T FIDF 的计算方法, 综合考虑词语 w i 在文档 doc x 的结构单元e j 中出现的情况及该词的全局权重.x (i, j ) = T F(w i , doc x .e j ) ? IDF(w i ) (10) 其中, T F(w i , doc x .e j )为词条 w i 在文档doc x 的结构单元e j 中出现的频度.IDF(w i )= log( | D| / DF(w i )), | D| 是文档集合中文档总数, DF(w i ) 是包含词语 w i 的文档个数.IDF( w i )是词语w i 全局特性, 用来体现词语 w i 区分文档的能力.

3 ?基于 SVM 的 XML文档自动分类

3. 1?XML文档的向量表示在 SVM 分类方法中, 每个样本采用向量进行表示. 向量空间模型( VSM) 中, 每个文档采用一个向量表示, 可直接用于 SVM 进行训练与自动分类.而结构链接向量模型( SLVM) , 将每个 XML采用一组向量表示, 不能直接应用于 SVM 进行自动分类. 为此, 采用式( 11) 的形式, 将 SLVM 模型中表示一个 XML 文档的一组向量( m 个 n 维向量)转换成一个向量(m ? n 维) .x ^ = ?x (1, 1) , ?, x (n, 1) , ?, x (1, m) , ?, x (n, m) ?T(11)该向量是按结构单元顺序将 m 个 n 维向量依次排列, 组成一个新的 m ? n 维向量, 向量的每维分别对应一个结构单元中的一个词语.

3. 2? 核函数基于式( 11) 对 XML 文档集进行向量化后, 如果把这些代表 XML 文档的向量样本集看作是线性可分的话, 则 SVM 的训练函数和分类函数如式( 1)和( 2) 所示. 这种情况要求向量各维是互相独立的,XML 文档中各结构单元之间无相关性.但是 XML 文档中各结构单元之间存在相关性, 即 SLVM 模型所构造的特征空间并不是一个正交空间. 举例来说, ? 计算机?这个词出现在 A、 B、 C三个文档中: A、 B 文档的? 标题?中和 C 文档的? 摘要?中. 直观地看, 仅考虑? 计算机?这个词的情况下,虽然? 计算机?这个词出现在文档 A 和 C 的不同结构单元( 元素) 中, 但它对 A、 C 文档间的相似度有一定的贡献, 但这种贡献要小于它对 A、 B 文档间相似度的贡献.如本文 2 ? 1节中所述, 对于非线性问题, 可通过构造核函数进行空间映射来求解最优分类超平面.为此, 本文提出函数( 12) 作为基于 SVM 的XML 文档分类的核函数, 通过该函数对 XML 文档中结构单元之间的关系进行建模描述. K (x i , x j )=?mp = 1?mq = 1g( p, q)? ?nk = 1(x i(k, p) ?x j (k, q) )(12)其中, 该公式的后半部分 ?nk = 1 ( xi(k, p) ?x j(k, q) ) 可看作是文档 x i 的结构单元e p 和文档x j 的结构单元e q 在VSM 模型中的相似度(参见式(7)) ;g(p, q)是描述两个文档结构单元 e p 和 e q 之间相似度对两个文档间相似度的贡献函数.式(12)所描述的核函数可看作是在 SLVM 模型中计算两个 XML 文档之间的相似度, 该相似度是由两文档中各结构单元之间相似度的加权累加之和.容易证明, 式(12)的核函数满足 Mercer 条件.如果忽略不同结构单元之间相似度对文档间相似度的贡献, 而仅考虑相同结构单元之间相似度对文档间相似度的贡献时, 则函数 g(p , q) 将采用式(13)的形式, 核函数退化为式(14) 的形式, 即简单的向量点积函数, 分类问题退化为简单的线性可分问题.g(p , q)1, p = q0, p ?q(13)K (x i , x j ) =?mp = 1?nk = 1(x i(k, p ) ?x j (k, p) ) = x? Ti ?x ^ j (14)

4 ?核函数的学习

获取 XML 文档中结构单元之间的关系是面向XML 文档集的文本挖掘研究的基本课题之一, 如Zhang 等人在文献[ 2] 中采用编辑距离进行 XML文档结构相似度的计算. 其基本思想是将文档结构抽象为一个树结构, 不同结构单元之间的相似性是通过计算编辑距离获得. 这种方法对某些文档相似度计算是有效的, 但它是以一种固定的模式计算结构之间的关系, 并不真正代表结构单元之间的语义关系, 不能随着文档结构的组织形式的变化而变化.如果以不同的方式来组织相同的结构关系, 则计算的结果也可能会有很大的差别, 其适用性受到很大限制.通过学习的方法进行这种关系的训练学习可避免这种方法的限制. 本文作者在文献[ 10] 中提出了通过矩阵迭代的方法进行结构相关矩阵的学习, 从而提高了 XML 文档的聚类效果. 该方法虽然可用于有指导的学习, 但基本思想是无指导的学习. 本文采用基于支持向量机的 XML 文档结构单元相关性的学习方法, 并用于核函数的计算.在式(12)中, 函数 g( p, q) 描述是文档结构单元间的相关性, 其两个自变量取值均为[ 1. . m] , m 为结构单元的个数. 为此, 函数 g( p, q) 可用 m ? m 维的矩阵G 来表示, 并可进一步表示成一维向量的方式:G^ = ?G (1, 1) , ?, G (m, 1) , ?, G (1, m), ?, G (m, m) ?T.此时, 式(12) 可表示成:K( x i , x j )=?mp = 1?mq = 1(G (p, q) ?s( x i , p , x j , q)) (15)其中,s(x i , p, x j , q)=?nk = 1(x i(k, p ) ?x j(k, q) ) (16)表示XML 文档 x i 的第p 个结构单元与文档x j 的第q 个结构单元中文本内容的相似度, 可直接计算获得.从而式(12) 描述的核函数 K (x i , x j ) 可看作是关于 G的 m ? m 维的向量.K( x i , x j )= VT?G^(17)其中,V= ?v (1, 1) , ?, v (m, 1) , ?, v (1, m) , ?, v (m, m) ?,v (p, q) = s( x i , p, x j , q)=?nk = 1(x i(k, p) ?x j(k, q) ).同时, 核函数 K ( x i , x j ) 表示的是两个 XML 文档之间的相似度. 对于 XML 文档集, 两两文档作为一组, 可获得式(17)所示的向量, 且? ? y( i, j )= K( x i , x j )=1, x i 与x j 属于相同的类别0, x i 与x j 属于不同的类别.从而, 训练样本的 XML 文档集, 两两构成一个向量, 形成一组训练样本, 采用 SVM 的回归学习方法则可求解并获得向量G^ , 即矩阵 G, 从而可获得函数 g( p, q)的具体形式.进一步, 根据G^值的权重排序, 可对取值小的项进行裁减, 从而降低算法的计算量. 针对大规模XML 文档集, 该裁减能明显提高计算速度.

5 ?实 ?验

5. 1?实验环境与数据集实验使用 Intel P4 3 ?0GHz CPU, 512MB 内存的个人计算机, 在 Windows XP Professional 操作系统上以 Visual C+ + 6 ?0 作为开发环境.实验选用 INEX 提供的XML 文档实验数据集.该数据集含有 12107篇 XML 文档, 来源于 IEEE 的18种计算机类期刊杂志的文章. 文档的总大小为494MB, 包含 192 个不同的元素, 平均每篇 XML 文档包含 1532 个结点项, 平均结点深度为 6 ?9. 为进行文档分类评测, 文档集根据文章内容被人工标注为 18 类别, 6053 个文档用于训练, 6054 个用于测试.

5. 2? 评价函数实验中, 采用 INEX 提供的评价程序进行结果的评测. 该评价程序是将自动分类的结果作为其输入、输出为分类结果的评价值 Micro F1 和 Macro F1.precision( i)= A i / B i ,recall(i)= A i / C i ,其中, A i 为正确分到第i 类的文档数; B i 为被分到第i 类的总文档数; C i 为第 i 类实际包含的总文档数.F1(i) =2? p recision(i) ? recall( i)precision( i)+ recall(i),Macro_F1=?mi = 1F1(i) / m,Micro_F1=?mi = 1F1(i) ?C i / N,其中, m 为类别总数, N 为文档总数.5. 3? 实验结果为方便对比, 先将参加 INEX 评测的各方法的实验结果整理如表 1 所示.表 1? INEX评测结果方法 Micro_F1 Macro_F1Graph Neural Network 0 ? 721440 0 ? 713969Contextual Self?OrganizingMap for Structures0 ? 365079 0 ? 326469Doucet 0 ? 348828 0 ? 290379PCXSS 0 ? 088824 0 ? 044641Xing 0 ? 592901 0 ? 580350首先采用两个基本方法进行实验对比:( 1) VSM 法. 仅考虑 XML 中的纯文本内容,不考虑其中的置标内容, 并采用向量空间模型( VSM) 进行文档向量化;( 2) 基本 SLVM 法. 采用结构链接向量模型( SLVM) 对 XML 文档进行向量化, 并且不考虑结构单元之间的关系, 即函数 g(p , q)采用式( 13) 的形式, 分别采取如下两种不同的方式选取结构单元: ? 基本 SLVM 法( 元素) . 以 XML 文档的元素为基本结构单元, 对于相同的元素, 不论其出现在结构树的什么位置, 将其内容都统一向量化到一个结构单元中;? 基本 SLVM 法( 路径) . 以 XML 文档的结构树的路径为基本结构单元, 对结构树的不同路径分别进行向量化.实验结果如表 2所示.表 2? 基本方法对比结果方法 Micro_F1 Macro_F1VSM 0 ? 708293 0 ? 702650基本SLVM 法( 元素) 0 ? 768723 0 ? 761243基本SLVM 法( 路径) 0 ? 789338 0 ? 780885实验表明, 采用简单的 VSM 模型进行向量化的效果一般, 略低于 INEX 评测中的 Graph NeuralNetwork, 但明显高于其它方法. 而基本 SLVM 法高于 INEX 评测中公布的所有方法以及 VSM 法.同时, 采用结构树路径为结构单元的方法要好于采用元素为结构单元的方法, 因为相同的元素可能出现在结构树的不同位置, 其实际意义会有所不同, 例如: 元素?Name?可分别作为元素?Conf erence?和元素?A uthor?的子元素. 采用元素为结构单元的方法, 不能区分这种情况, 而采用结构树路径为结构单元的方法可对这一情况进行区分.各结构单元中的内容长短有明显差别, 例如: 正文中的内容通常有数千个词, 向量化后占据的权重比例大, 而标题等只有 10 个左右的词, 所占总权重很小. 为此, 对结构单元的向量进行单位化, 使得每个结构单元的向量长度都为 1. 即将式(8)变换成式(18)的形式.x~(i) = ?x (1, i) / | x ( i) | , x (2, i) / | x (i) | ?x (n, i) / | x ( i) |? T(18)单位化处理后, 实验效果大幅改进, F1 接近100%, 实验中只有一个文档被错误分类. 实验结果如表 3 所示.表 3? 结构单元向量化后结果方法 Micro_F1 Macro_F1SLVM 法(元素) 0 ? 999835 0 ? 999823SLVM 法(路径) 0 ? 999835 0 ? 999823获得如此高准确性的原因在于 XML 文档中有两个元素( ?f no?和?doi?) 与文档的分类情况一一对应, 进行结构单元单位化后, 其重要性明显体现出来, SVM 训练过程自动学习获得这一特性并体现在分类模型中, 分类过程中主要以这两个元素内容进行自动分类.为进一步试验方法的有效性, 实验中将这两个元素剔除, 实验结果如表 4 所示.表 4? 剔除元素?f no?和?doi?的实验结果方法 Micro_F1 Macro_F1SLVM 法( 元素, 未单位化) 0 ? 741510 0 ? 733432SLVM 法( 路径, 未单位化) 0 ? 761417 0 ? 750191SLVM 法( 元素, 单位化) 0 ? 882676 0 ? 886292SLVM 法( 路径, 单位化) 0 ? 902404 0 ? 901225实验结果表明, 虽然剔除了两个对分类具有重要指示意义的元素, 但分类效果仍好于 INEX 评测中公布的所有方法, 特别是单位化后具有明显效果.实验进一步采用式( 17) , 利用 SVM 的回归学习方法对核函数中的矩阵 G进行学习. 由于回归学习的样本向量数为文档个数的平方( 6053 2 = 36638809) ,全部采用的话, 训练时间太长, 也没有实际意义, 为此, 实验中随机选取其中 10000 个进行回归学习. 实验结果如表 5所示.表 5? 对矩阵 G进行回归学习的实验结果方法 Micro_F1 Macro_F1SLVM 法(元素, 单位化) 0 ? 923074 0 ? 921920SLVM 法(路径, 单位化) 0 ? 946391 0 ? 942948实验表明, 对矩阵 G 进行回归学习可较明显提高分类的准确性.

6 ? 结 ? 论

本文研究了基于支持向量机的 XML 文档自动分类方法, 提出了适合 XML 文档分类的核函数以及基于支持向量机回归学习的核函数参数训练方法, 从而将 XML 文档的结构分析与内容分析有机地结合起来. 在 INEX 数据集上的测试结果表明, 该方法具有很好的分类效果, 分类准确性明显高于INEX 评测中公布的其它方法的评测结果.

    参 考 文 献[ 1] Yi J, Sundaresan N. A classifier for semi?structured docu ?ments/ / Proceedings of the 6th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining( KDD? 00) . Boston, MA, USA, 2000: 340?344[ 2] Zhang Z P, Li R, Cao S L, Zhu Y Y. Similarity metric forXML documents/ / Proceedings of the 2003 Workshop onKnowledge and Experience Management ( FGWM? 03) .Karlsruhe, 2003[ 3] Denoyer L, Gallinari P. Bayesian network model for semi?structured document classification. Information Processingand M anagement, 2004, 40( 5) : 807 ?827[ 4] Kc M, Hagenbuchner M et al. XML document mining usingcontextual self?organizing maps for structures/ / Proceedings ofthe Initiative for the Evaluation of XML Retrieval( INEX? 06) .Schloss Dagstuhl, Germany, 2006: 510 ?524[ 5] Yong S L, Hagenbuchner M et al. XML document miningusing graph neural network/ / Proceedings of the Initiative forthe Evaluation of XML Retrieval( INEX? 06) . Schloss Dags?tuhl, Germany, 2006: 458?472[ 6] Vapnik V N. The Nature of Statistical Learning Theory.New York: Springer ?Verlag, 1995[ 7] Yang Y, Liu X. A re?examination of tex t categorizationmethods/ / Proceedings of the ACM SIGIR Conference on Re?search and Development in Information Retrieval( SIGIR? 99) .Berkeley, USA, 1999: 42?49[ 8] Yang J W, Chen X O. A semi ?structured document model fortex t mining. Journal of Computer Science and T echnology,2002, 17( 5): 603 ?610[ 9] Salton G, M cGill M J. Introduction to M odern InformationRetrieval. New York: M cGraw?Hill, 1983[ 10] Yang J W, Cheung W K, Chen X O. Integrating elementkernel and term semantics for similarity?based XML docu ?ment clustering/ / Proceedings of the 2005 IEEE/ WIC/ ACMInternational Conference on Web Intellig ence ( WI? 05 ) .Compiegne, France, 2005: 222 ?228