基于经验风险的中心文本分类算法

周晓堂,欧阳继红,李熙铭

(吉林大学 计算机科学与技术学院,长春 130012)

互联网的快速发展为信息共享提供了一个通用平台.文本是信息的主要载体,研究文本自动分类可系统地规范文本,提高信息检索速度,因此,对文本分类算法的研究具有重要意义[1].近年来,人们已提出了许多文本分类算法,包括中心分类法[2]、朴素Bayes算法[3]、支持向量机[4]、人工神经网络[5]、K近邻算法[4]和决策树[6]等.其中,中心分类法具有高效、健壮和计算简便并易于编程等优点,得到广泛应用.但中心分类法的训练过程忽略了文本权值对类别中心的影响.针对中心分类法的缺陷,目前已提出了许多改进.文献[7]提出的权重调整方法中,使用特征的“纯度”表示每个特征的区别能力,然后根据验证集上的错误率使用“纯度”迭代调整文本向量中的所有特征权重,该方法认为平均分配在各类中的特征具有较低的“纯度”和区别能力,而非平均分布在各类中的特征具有较高的“纯度”和区别能力.文献[8]提出的基于特征分布方法中,考虑了特征在类中的分布,并使用特征分布加强特征权重函数.文献[9]提出的类-特征-中心方法中,应用类间和类内特征索引构建相对于传统方法具有更好初始值的类中心向量.文献[10]提出的拖拽方法利用训练集上的分类错误信息通过拖拽方法改善类中心向量,并提出了按组更新的中心分类法,该方法对类中心进行拖拽,使其靠近属于该类且被错误分到其他类的文本,同时远离不属于该类且被错误分到该类的文本.在引入训练集分类错误信息的基础上,为提高模型分类的泛化能力,谭松波等[11]又引入了训练集边界信息,定义了数据的假设边界,并依此对类中心进行拖拽,使类中心靠近属于该类且处在假设边界附近的文本,该方法利用训练集上的分类错误信息和训练集的边界信息定义了目标函数,通过利用梯度下降法求得目标函数的最小值指导类中心的拖拽.但该方法给出的目标函数并不处处光滑、可导,在应用梯度下降方法时,可能会产生异常结果.

本文在传统中心分类法的基础上,基于经验风险最小化原则构建目标函数,通过引入Sigmoid函数平滑得到一个处处光滑、可导的目标函数,解决了文献[11]中目标函数的可导性问题.使用最优化技术优化目标函数调整类中心向量,求得了代表性更强的类中心向量,进而提高了分类性能.实验结果表明,本文算法具有与支持向量机相近的分类性能,并适用于偏斜数据集,鲁棒性较强.

1 中心分类法

中心分类法的基本思想：根据训练文本集合的信息为每个类别构建中心特征向量作为该类的代表向量,待分类文本则根据与各个中心特征向量的相似度决定所属类别.

1) 预处理阶段.使用向量空间模型处理非结构化的文本数据,计算每个文本对应的数值特征向量d=(w(t1,d),w(t2,d),…,w(tNT,d)),各项特征权重w(ti,d)的计算公式为

(1)

该数值特征向量由特征空间中的特征权重组成,包含了文本内部潜在的统计信息.其中:d表示来自训练集的一篇文本;tf(ti,d)表示在文本d中特征ti的出现次数;Nti表示训练集D中包含特征ti的文本总数;分母为规范化因子,使每个数值特征向量都具有单位长度,消除不同文本的不同长度对特征权重的影响.

(2)

3) 测试阶段.中心分类法使用余弦函数度量测试文本d和类别中心Ci的相似度.相似度计算公式为

(3)

其中,“·”表示两个向量的点积.

经过相似度对比,中心分类法认为测试文本d属于与文本d具有最大相似度类别中心所代表的类别.引入变量Cjudge(d,C),判别公式为

(4)

2 本文算法

传统中心分类法使用算术平均值计算类别的中心向量.该策略给每篇文本相同的权重,未考虑不同文本的表达能力是不同的,影响了中心向量的表达能力,从而影响了中心分类法的分类性能.针对此问题,本文基于经验风险最小化的原则构建目标函数,通过梯度下降算法计算目标函数极值点求得类别中心向量.同时,为了解决文献[11]中目标函数不是处处可导的问题,本文引入Sigmoid函数平滑目标函数,避免其不可导产生的不稳定因素.

(5)

其中: 函数Cneighbor(d,C)表示集合C中与文本d的相似度最高且属于不同类别的类中心向量;函数Ctrue(d,C)表示集合C中与文本d同类的类中心向量;函数Sgn(x)是指示函数,定义如下：

(6)

由式(6)可见,当函数Sgn(cos(d,Cneighbor(d,C))-cos(d,Ctrue(d,C)))=0时,表明文本d被正确分类；否则,表明文本d被错误分类.因此,目标函数RSgn(D,C)有效表达了中心分类法在训练集D上的经验误差.

通过最小化函数RSgn(D,C),可得到更具代表性的类中心,提高中心分类法的分类性能.但由于指示函数Sgn(x)的阶梯函数性质,使得目标函数RSgn(D,C)不是处处光滑且不可导,不能直接使用解析法求解极值.因此,本文使用平滑单调函数Sigmoid(x)近似模拟指示函数Sgn(x),以得到处处光滑、可导的目标函数RSig(D,C),定义如下：

(7)

其中

(8)

λ为控制Sigmoid(x)函数形状的参数.

最后,得到类中心的梯度更新公式为

(9)

(10)

其中

(11)

在经验风险最小化原则下,使用梯度下降法获得最优类中心的算法伪代码如下：

输入：训练集D,最大迭代次数Max_iter.

输出：最优类中心向量集CMax_iter.

按式(2)初始化起始类中心向量集C0

Fort=1∶Max_iter//迭代开始；

Fori=1∶ND//迭代的第一部分

计算文本di和当前所有类中心Ct-1的相似度

计算文本di的Cneigbor(di,Ct-1)值

End for

Fori=1∶K//迭代的第二部分

Forj=1∶NT

按式(9)更新类中心

End for

End for

End for//迭代结束

ReturnCMax_iter

3 实验结果

3.1 实验数据集及评价标准

实验数据集选取来自TREC,OHSUMED和Reuters-21578这3个基准文本数据集中的4个子文本数据集la12,new3,ohscal和re1.其中: la12和new3来自TREC;ohscal来自OHSUMED;re1来自Reuters-21578.4个子文本数据集la12,new3,ohscal和re1的特征列于表1.由数据集规模大小可见,la12和ohscal是大数据集,new3和re1是小数据集；由数据集平衡程度可见,la12,ohscal,new3是平衡数据集,re1是不平衡数据集.

表1 文本数据集Table 1 Text data

实验选用宏平均F1值和微平均F1值[12]度量分类性能.宏平均F1值为整个测试集上的F1值,微平均F1值为测试集各类别上F1值的均值.F1值为查准率和查全率的调和平均值,定义如下：

F1=2×[(查准率×查全率)/(查准率+查全率)].

(12)

3.2 实验结果

为了获得模型预测能力的准确估计,减弱训练集、测试集分割时对实验结果产生的影响,实验过程采用三折交叉验证方式[13].实验选取的对比算法包括传统中心分类法(BCC)及支持向量机的两个变体SVMTorch和LibSVM.实验结果如图1和图2所示.

图1 不同方法的宏平均F1值对比Fig.1 Comparison of macro-F1 mean values by different methods

图2 不同方法的微平均F1值对比Fig.2 Comparison of micro-F1 mean values by different methods

由图1和图2可见,本文算法的分类性能明显高于传统中心分类法.此外,本文算法在弥补了传统中心分类法在平衡数据集上分类性能较差的缺点、使其分类性能逼近支持向量机方法的同时,进一步增强了传统中心分类法在偏斜数据上分类性能较强的优势,使其分类性能明显优于支持向量机方法.

综上所述,本文提出的经验风险最小化原则下的中心分类法相比于传统中心分类法,能得到代表性更强的类中心,其分类性能逼近支持向量机方法,且在偏斜数据集上优于支持向量机方法.

[1] XUE Gui-rong,XING Di-kan,YANG Qiang,et al.Deep Classification in Large-Scale Text Hierarchies [C]//Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York: ACM,2008: 619-626.

[2] Han E H,George K.Centroid-Based Document Classification: Analysis and Experimental Results [C]//Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery.London: Springer-Verlag,2000: 424-431.

[3] Ashraf M K,Eibe F,Bernhard P,et al.Multinomial Naive Bayes for Text Categorization Revisited [C]//Proceedings of the 17th Australian Joint Conference on Artificial Intelligence.Berlin: Springer Verlag,2004: 488-499.

[4] Naohiro I,Tsuyoshi M,Takahiro Y,et al.Text Classification by Combining Grouping,LSA and kNN [C]//Proceedings of the 5th IEEE/ACIS International Conference on Computer and Information Science.Washington DC: IEEE Computer Society,2006: 148-154.

[5] Rowena C,Chunghsing Y,Katea S.A Neural Network Model for Hierarchical Multilingual Text Categorization [C]//Proceedings of the Second International Symposium on Neural Networks.Berlin: Springer Verlag,2005: 238-245.

[6] GAO Sheng,WU Wen,LEE Chin-hui,et al.A Maximal Figure-of-Merit (MFoM)-Learning Approach to Robust Classifier Design for Text Categorization [J].ACM Transactions on Information Systems,2006,24(2): 190-218.

[7] Shrikanth S,George K.A Feature Weight Adjustment Algorithm for Document Categorization [C]//Proceedings of the KDD-2000 Workshop on Text Mining.Boston: Citeseer,2000: 12-19.

[8] Verayuth L,Thanaruk T.Effect of Term Distributions on Centroid-Based Text Categorization [J].Information Sciences,2004,158: 89-115.

[9] GUAN Hu,ZHOU Jing-yu,GUO Min-yi.A Class-Feature-Centroid Classifier for Text Categorization [C]//Proceedings of the 18th International Conference on World Wide Web.New York: ACM,2009: 201-210.

[10] TAN Song-bo.Large Margin DragPushing Strategy for Centroid Text Categorization [J].Expert Systems with Applications,2007,33(1): 215-220.

[11] TAN Song-bo,CHENG Xue-qi.Using Hypothesis Margin to Boost Centroid Text Classifier [C]//Proceedings of the 2007 ACM Symposium on Applied Computing.New York: ACM,2007: 398-403.

[12] Michael B,Fredric G.The Relationship between Recall and Precision [J].Journal of the American Society for Information Science,1994,45(1): 12-19.

[13] Christopherd M,Prabhakar R,Schütze H.Introduction to Information Retrieval [M].New York: Cambridge University Press,2008: 151-176.