基于信息瓶颈和拉普拉斯SVM的Web文档分类算法
王自强1, 2，孙霞1，钱旭2
(1. 河南工业大学 信息科学与工程学院，河南 郑州，450001；
2. 中国矿业大学(北京) 机电与信息工程学院，北京，100083)
摘 要：
传统文档表示的高维性及利用大量的无标记样本数据来共同提高Web文档分类算法的分类性能，提出了基于信息瓶颈和拉普拉斯SVM的Web文档分类算法。该算法首先利用基于信息瓶颈的词聚类方法来抽取用于文档简洁表示的鉴别性特征，然后，再在降维后的低维特征空间利用拉普拉斯SVM分类器进行分类判决。实验结果表明，该算法具有很好的分类性能。
关键词：
中图分类号：TP18 文献标志码：A 文章编号：1672-7207(2011)S1-0731-06
Web document classification algorithm based on IB and LapSVM
WANG Zi-qiang1, 2, SUN Xia1, QIAN Xu2
(1. School of Information Science and Engineering, Henan University of Technology, Zhengzhou 450001, China;
2. College of Mechanical Electronic and Information Engineering,
China University of Mining and Technology(Beijing), Beijing 100083, China)
Abstract: To effectively overcome the high-dimensionality of document representation and improve the performance of Web document classification algorithm with a large amount of unlabeled data, the Web document classification algorithm based on information bottleneck (IB) and Laplacian support vector machine (LapSVM) was proposed. First, the information bottleneck-based word clustering algorithm was used to obtain the discrimination feature for concise document representation, then the LapSVM classifier was applied to classifying documents in the reduced lower dimensional feature space. Experimental results show that the proposed classification algorithm achieves superior classification performance.
Key words: data mining; document classification; information bottleneck; LapSVM
文档分类的任务是将一个给定的文档分配到一个或者多个确定的类别中。近年来，随着大量的数字化和在线文档被人们很容易地生成、存储和存取，因而如何高效地对这些文档进行组织、分类和检索日益成为一项重要的研究课题。随着全球互联网技术的蓬勃发展，网上的文档数据更是呈“爆炸式增长”，因而研究开发面向Web文档的智能分类技术就显得更加迫切和必要了。在过去的几年中，有关学者对Web文档的分类技术进行了大量的探索，提出了多种基于机器学习的文档自动分类算法[1]。这些文档分类算法都涉及到如下2个关键问题：(1) 如何提取用于文档表示的鉴别性特征；(2) 如何在特征提取的基础上对新的测试文档进行分类。在文档特征的提取方面，大部分文档分类算法都是采用向量空间或者词袋(Bag of Words)模型来表示文档向量。在该文档向量表示中，文档中的每个词对映一个特征。尽管该模型具有概念简单、直观易懂的特点，但是其不足之处是容易产生“维数灾难”问题，这将严重影响后继文档分类器的分类性能和计算效率[2]。 另外，分类器的选择是文档特征提取之后的另一个关键问题，目前常用的分类器算法可以分为无监督、有监督和半监督3种类型。尤其是近年来基于图的半监督学习分类器由于在众多模式分类任务中取得了很好的分类性能而受到人们的广泛关注[3]，但是将其应用于大规模高维Web文档的自动分类还是一个有待研究的难点问题之一。为了有效地克服传统文档表示的高维性及利用大量的无标记样本数据来共同提高文档分类算法的分类性能，我们提出了一种基于信息瓶颈[4-7]和拉普拉斯SVM的Web文档分类算法，并通过在大规模文档测试数据集上的实验结果说明该算法的有效性。
1 Web文档鉴别性特征提取
为了有效地获取Web文档简洁表示的鉴别性特征，以克服文档表示时的“维数灾难”问题，提高后继文档分类器的分类性能和计算效率，我们采用基于信息瓶颈的Web文档鉴别性特征提取方法。该方法的优点是：利用信息瓶颈获得的词聚类表示能够在获得词之间相似性度量优化解的同时取得最小化类内散度和最大化类间散度，以便最大程度地获得用于文档表示简洁表示的鉴别性特征。
信息瓶颈(IB)旨在通过把随机变量X划分成能够保持和另一个相关变量Y之间互信息的不同域来实现对X的相关编码或简洁表示。假设变量X和Y之间的联合概率分布为P(X，Y)，X的划分(即：聚类)为
，于是IB的优化目标函数可形式化地描述如下：
(1)
约束条件为：
(2)
式中：β表示对变量X中的信息约简程度；
和
分别表示划分和Y及X之间的互信息，其定义如下：
(3)
(4)
式中：H(X)表示随机变量X的熵，其定义如下：
(5)
式(1)中的IB的优化目标旨在最小化X的划分和最大化与Y的互信息之间寻找一种优化折衷。事实上，在式(2)约束下，式(1)中的优化问题的解可以利用下式来描述：
(6)
式中：Z(β，X)是一个正则化因子；β是用于约束信息的拉格朗日系数，一般利用模拟退火法来控制所需要的聚类数目，β与聚类数目对应相关；
可以利用如下贝叶斯规则进行计算：
(7)
(8)
在利用信息瓶颈(IB)算法进行词聚类以获得文档简洁表示的过程中，上述描述中的变量X表示出现在文档中的词，变量Y表示文档的类别标记，利用元组(w，c)来描述联合概率分布P(X，Y)，其中：w表示文档中的词，c表示包含词w的文档的类别标记。对于指定的聚类数目k，IB算法首先生成一个包含全部输入数据的聚类，然后在每次循环中利用增加模拟退火系数和式(6)~(8)对聚类进行划分直至达到最大循环迭代次数为止，最后将每个词分配到一个词聚类中并输出最终的词聚类结果，以便于后继文档分类器的高效分类判决。
2 文档分类器设计
对于Web文档分类问题，一旦利用信息瓶颈算法获得高维文档数据的低维简洁表示之后，文档分类器的设计和优化便是另一个需要解决的关键问题。由于在Web文档分类任务中，人们很容易得到大量没有类别标记的样本数据，得到的有标记样本数据由于受到人力和财力的限制而十分有限，因此我们必须采用基于半监督学习的分类器来充分利用部分有标记的样本数据和大量的无标记样本数据来共同提高文档分类算法的分类性能和泛化能力。基于上述考虑，我们提出了如下利用流形正则化的拉普拉斯SVM(LapSVM)[8]文档分类器。
假设给定l个有类别标记的文档数据集
和u个无类别标记的文档数据集
，其中：类别标记
表示文档数据xi所属的类别，假设存在一个通用的分类决策函数f，基于正则化框架的半监督学习的目标是最小化如下目标函数：
(9)
式中：V(，)表示定义在有类别标记文档上的损失函数；γA用于控制在相关希尔伯特空间(Hilbert Space)上决策函数f的复杂性；γM用于控制在大间隔数据分布所展示的内在流形几何结构上决策函数f的复杂性。
根据核空间理论中的表示定理可知：式(9)中的最小优化问题的解可由有标记和无标记样本数据的如下扩展构成：
(10)
其中：K(，)表示核函数。
由于在式(9)中可以通过使用不同的损失函数V(，)和正则化项
来形成不同的半监督分类器算法，在本文中，我们采用了SVM分类器中的如下损失函数：
(11)
另外，由核空间理论可知：在希尔伯特空间上的决策函数f可表示为如下形式：
(12)
其中：w表示SVM中的法向量；φ表示文档数据到希尔伯特空间的非线性映射；K表示由如下核函数构成的核矩阵：
(13)
同时，由核空间中的可再生理论可知：w由希尔伯特空间中的所有有标记样本和无标记样本数据线性组合而成，即：
(14)
式中：
，
。
另外，根据流形(平滑)假设理论可知：具有相同流形结构的点可能具有相同的类别标记。而在流形学习中，文档数据的内在流形结构是通过有标记和无标记数据共同构成的加权无向图来描述的，于是式(9)中等式右边的第3项可重写为如下形式：
(15)
式中：L=D-W，称为图拉普拉斯；对角矩阵D的计算方式如下：
(16)
另外，式(15)中矩阵f的表示形式根据式(10)可重写为如下形式：
(17)
于是，将式(17)代入式(15)可得:
(18)
将式(11)、(12)和(18)分别代入式(9)可得拉普拉斯SVM的如下优化目标函数：
(19)
约束条件为:
(20)
为了获得在式(20)约束下的式(19)中的优化解，可以通过拉格朗日函数法求解如下对偶问题获得：
(21)
约束条件为:
(22)
(23)
式中，
(24)
(25)
由于式(21)中的拉普拉斯SVM优化函数是一个二次规划问题，因此，我们可以用训练传统SVM的高效训练方法来训练拉普拉斯SVM。一旦获得优化的β*后，即可利用式(25)获得支持向量α。于是，对于一个新的文档测试数据x，拉普拉斯SVM分类器可以利用如下决策函数判断其类别标记：
(26)
3 文档分类算法描述
基于信息瓶颈和拉普拉斯SVM的Web文档分类算法的具体实现过程可描述如下：
步骤1：信息瓶颈(IB)的目标函数建立。设X表示出现在文档中的词，变量Y表示文档的类别标记，利用元组(w，c)来描述联合几率分布P(X，Y)，其中w表示文档中的词，c表示包含词w的文档的类别标记。利用式(1)和(2)建立IB的优化目标函数，以使得最小化对X划分的同时最大化与Y之间的互信息。
步骤2：生成用于文档低维特征表示的词聚类。首先，利用在每次循环迭代中增加模拟退火系数和式 (6)~(8)对词聚类进行划分直至达到最大循环迭代次数为止；然后，将每个词分配到一个词聚类中并输出最终的词聚类结果，以便将每个词聚类作为文档低维表示的鉴别性特征输入到后继拉普拉斯SVM分类器中进行训练。
步骤3：邻接图中加权矩阵的构造。设在低维特征空间中存在l个有类别标记的文档特征集和
个无类别标记的文档特征集。首先利用这(l+u)个文档特征数据集创建无向邻接图。该图中加权矩阵Wij的构造方法如下：如果在该邻接图中顶点i所表示的文档特征数据xi是顶点j所表示的文档特征数据xj的最近邻居之一，则在顶点i和顶点j之间创建一条边，且该边的权重Wij=1，否则Wij=0。
步骤4：核矩阵的计算。利用式(13)计算出核矩阵K中的每个元素Kij。
步骤5：拉普拉斯SVM优化目标函数的建立。根据式(19)和(20)建立拉普拉斯SVM的优化目标函数，并利用拉格朗日函数法得到其对偶函数(式(21))。
步骤6：拉普拉斯SVM分类器的判决函数构建。首先，通过求解式(21)中的二次规划问题获得优化的β*；然后，根据式(25)计算出优化的支持向量α；最后，根据式(26)建立拉普拉斯SVM分类器的判决函数对新的文档测试数据进行分类预测。
4 实验结果
为了检测我们提出的基于信息瓶颈和拉普拉斯SVM的Web文档分类算法的性能，我们采用了WebKB[9]和20NG[10]这2个著名的文档测试数据集作为实验数据来源。文档分类算法的性能评价采用了常用的3个度量标准：分类准确率(Classification Accuracy)、均衡点(Break-Even Point)值和F1值。他们的值越大说明文档分类算法的分类性能越好。
为了测试我们提出的Web文档分类算法的分类性能，我们对如下3种文档分类算法在WebKB和20NG数据集上的分类性能进行了综合测试比较：
第1种，首先，采用潜在语义索引(LSI)法对高维文档数据进行特征提取；然后，再利用支持向量机(SVM)分类器进行文档分类，简称LSI-SVM算法。
第2种，首先，采用信息瓶颈(IB)法对高维文档数据进行特征提取；然后，再利用支持向量机(SVM)分类器进行文档分类，简称IB-SVM算法。
第3种，首先，采用信息瓶颈(IB)法对高维文档数据进行特征提取；然后，再利用拉普拉斯SVM(LapSVM)分类器进行文档分类，简称IB-LapSVM算法。
支持向量机(SVM)和拉普拉斯SVM(LapSVM)中的核函数采用了高斯核函数：
(27)
式中：核宽度参数σ利用十次交叉验证法进行优化设置，LapSVM中的最近邻居数设置为10，γA和γM的取值采用网格搜索法进行优化设置。
为了测试文档分类算法LSI-SVM，IB-SVM和IB-LapSVM在文档测试数据集WebKB和20NG上的分类性能，我们随机选择每个类中的20%有类别标记的文档数据集和剩余的30%无标记样本数据作为训练集；再将剩余的文档数据子集作为测试集。同时，为了确保分类算法测试的稳定性，将10次随机划分训练集和测试集的平均运行结果作为最终测试结果。表1和表2分别给出了上述3种文档分类算法在WebKB和20NG数据集上的分类准确率、均衡点值和F1度量值的测试结果。
从表1和表2中的实验数据可以看出：我们提出的Web文档算法IB-LapSVM的分类性能在所比较的3种分类算法中表现最好，算法LSI-SVM的分类性能表现最差。主要原因在于：基于信息瓶颈(IB)的词聚类方法能够在获得词之间相似性度量优化解的同时取得最小化类内散度和最大化类间散度，因而最大程度地达到了分类鉴别的目的，提高了后继文档分类器的性能和计算效率。另外，LapSVM分类器不仅能够有效地利用少量的有标记样本信息来最大间隔化具有不同类别的文档数据，而且还能够利用大量的无标记信息来发现文档数据内在的局部流形结构，从而进一步提高了LapSVM分类器的分类鉴别能力，所以我们提出的LapSVM算法在文档测试数据集WebKB和20NG上取得了很好的分类性能。
表1 在WebKB数据集上的分类性能比较
Table 1 Classification performance comparison on WebKB
表2 在20NG数据集上的分类性能比较
Table 2 Classification performance comparison on 20NG
另外，由于参数γA和γM是分类算法IB-LapSVM中的2个关键参数，其中参数γA用于控制在希尔伯特空间上决策函数f的复杂性，参数γM用于控制在流形几何结构上决策函数f的复杂性。为了测试参数γA和γM对算法IB-LapSVM的分类性能，图1
和2给出了他们之间的比值
与分类准确率之
间的关系，从图1和2可以看出：当Δ≈1，即：γA≈γM时，分类算法IB-LapSVM在测试数据集WebKB和20NG上的分类准确率最高。原因在于：当γA≈γM时，算法IB-LapSVM能够在少量的有监督信息和大量的无监督信息之间达到一种平衡，进而能够充分地利用少量的有标记样本信息来最大间隔化具有不同类别的文档数据；同时，还可以利用大量的无标记样本数据所揭示的局部流形结构来进一步提高其分类鉴别能力，所以取得了较高的分类准确率。
图1 在WebKB中Δ与准确率之间的变化示意图
Fig.1 Accuracy variation with Δ on WebKB
图2 在20NG中Δ与准确率之间的变化示意图
Fig.2 Accuracy variation with Δ on 20NG
5 结论
为了有效地克服传统文档表示的高维性及利用大量的无标记样本数据来共同提高文档分类算法的分类性能，本文提出了一种基于信息瓶颈和拉普拉斯SVM的Web文档分类算法，在大规模文档数据WebKB和20NG上的实验结果表明：该算法具有很好的分类 性能。
参考文献：
[1] Sebastiani F. Machine learning in automated text categorization[J]. ACM Computing Surveys, 2002, 34(1): 1-47.
[2] 苏金树, 张博锋, 徐昕. 基于机器学习的文本分类技术研究进展[J]. 软件学报, 2006, 17(9): 1848-1859.
SU Jin-shu, ZHANG Bo-feng, XU Xin. Advances in machine learning based text categorization[J]. Journal of Software, 2006, 17(9): 1848-1859.
[3] Belkin M, Niyogi P. Semi-supervised learning on Riemannian manifolds[J]. Machine Learning, 2004, 56(1/3): 209-239.
[4] Tishby N, Pereira F C, Bialek W. The information bottleneck method[C]//Proceedings of the 37th Annual Allerton Conference on Communication, Control and Computing(ACCCC’99). Champaign, USA, 1999: 368-377.
[5] Al-Mubaid H, Umair S A. A new text categorization technique using distributional clustering and learning logic[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(9): 1156-1165.
[6] Bekkerman R, El-Yaniv R, Tishby N, et al. Distributional word clusters vs. words for text categorization[J]. Journal of Machine Learning Research, 2003, 3: 1183-1208.
[7] Dhillon I S, Mallela S, Kumar R. A divisive information-theoretic feature clustering algorithm for text classification[J]. Journal of Machine Learning Research, 2003, 3: 1265-1287.
[8] Belkin M, Niyogi P, Sindhwani V. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples[J]. Journal of Machine Learning Research, 2006, 7: 2399-2434.
[9] Craven M, DiPasquo D, Freitag D, et al. Learning to extract symbolic knowledge from the world wide Web[C]//Proceedings of the Fifteenth National Conference on Artificial Intelligence(AAAI’98). Madison, USA, 1998: 509-516.
[10] 20 News Group[EB/OL]. [1999-10-20]. http://kdd.ics.uci.edu/ databases/20newsgroups/20newsgroups.html.
(编辑 杨华)
收稿日期：2011-04-15；修回日期：2011-06-15
基金项目：国家自然科学基金资助项目(70701013)；河南省自然科学基金资助项目(102300410020)
通信作者：王自强(1973-)，男，河南太康人，博士，副教授，从事机器学习与模式识别研究；电话：13838368359；E-mail：wzqagent@126.com
摘要：为了有效地克服传统文档表示的高维性及利用大量的无标记样本数据来共同提高Web文档分类算法的分类性能，提出了基于信息瓶颈和拉普拉斯SVM的Web文档分类算法。该算法首先利用基于信息瓶颈的词聚类方法来抽取用于文档简洁表示的鉴别性特征，然后，再在降维后的低维特征空间利用拉普拉斯SVM分类器进行分类判决。实验结果表明，该算法具有很好的分类性能。
