基于核覆盖算法的中文文本分类研究

杨丽玲

(漳州职业技术学院 计算机工程系,福建 漳州 363000)

0 引言

互联网的快速发展，带来了信息的海量增长．如何从海量信息资源中高效准确地找到所需的信息，信息分类是必不可少的第一步．传统上的文本分类工作通过人工来完成，这样做在准确性上相对较有保障，但远远无法满足人们多元化的需求．而文本自动分类技术为我们完成这项工作提供了很大的帮助，其在信息检索技术中具有重要的地位．

1 文本分类的定义

文本分类的工作就是将文本按照其特定的涵义划分到相应的类别中．即利用预先定义好的文本类别训练文本，找出训练文档与类别之间的关系，并由此指导测试文本的学习,从而确定新文本所属类别．文本分类是一个构造映射函数ф的过程，设文档集D= {d1,d2,…,dj,…,},预定义类集C= {C1,C2,…,Ci,…,},确定任意一个元组〈dj,Ci〉映射到集合{K,P}上的值，即函数ф:D×C→{K,P}．从广义上来讲,分类是数据挖掘的一种方法．但与传统的数据挖掘不同的是,文本分类面对的是非结构化的数据．而目前在文本分类过程中大部分是将非结构化的数据结构化后,再进行传统的分类方法．即文档建模的过程．

2 文本分类的主要过程及关键技术

文本分类过程首先是文本预处理；其次是选择合适的特征，并为每个特征计算出相应的权重；再次是根据预处理后的训练集建模，构建出分类器，并对分类器分类效果进行评估；最后是使用分类器对测试文本进行分类[1]．其中关键技术是特征选取、赋权以及分类器构造．如图1 所示．

图1 文本分类模型

经过文本预处理后，我们用特征项(词组) 的权重表示一个向量，但此时特征向量维数仍较大，需要我们利用有效的工具进行特征选取，从而寻找最有效的特征构成较低维数的模式向量．

特征选取是通过某种方法挑选出跟文档主题概念关系密切的特征,组成一个新的低维空间，以降低特征矩阵的维数，同时不改变原有特征空间的性质．其准则是经特征选择后能有效提高文本准确率．

特征选取主要有特征频度TF，文档频度DF,信息增益IG,X2统计,互信息 MI，相关系数法CC以及期望交叉熵ECE等方法[2-3]．这些方法的基本思想是对每一个特征计算它的权值，把权值小于指定阈值p的那些特征删除，那么最后留下的即认为是有效特征．当然这些算法有其存在的不足点，我们需要根据具体系统来进行选择确定．

2.1 特征频度TF

特征频度指特征在训练集中出现的频率．这是较为简单的特征选择方法．如果特征在训练集中出现频率越大,则认为其对文本分类越有用．因此,通过设定一个阈值来过滤低频特征，从而降低维度．因此，特征频度主要用在文本分类时直接删除某些低频特征．

2.2 互信息MI

互信息MI主要体现了特征项与类别的关系程度．对于特征项w和某一类别cj∈(c1,c2,c3,…ck)，如果特征项在cj中出现的概率高，而在其它类别中出现的概率低，那么特征项w将获得较高的互信息，也就有可能被选取为类别cj的特征．w和cj的互信息定义如式(1)：

(1)

式中P(w|cj)表示在文档中特征项出现的概率，也可以表示为式(2)形式：

(2)

式中A表示特征w与类cj同时出现的概率；B表示特征w不在类cj中出现的概率；C表示类cj中没有出现特征w的文本数；N表示总的文本数．

在训练过程中，这些概率可以用文本在训练集中相应的出现频率进行计算．但互信息有一个不足，互信息评估函数经常倾向于选择稀有单词,而这在特征选取时会删掉很多高频的有用词条．

2.3 相关系数法 CC

特征的相关系数法主要考虑的是特征与类型的正相关性．如式(3)所示

(3)

式中c表示类别；n表示总文本数；A表示w和c同时出现的次数；B表示w出现而c没有出现的次数；C表示c出现而w没有出现的次数；D表示w和c都没有出现的次数．进行特征选择时,选择CC值大的特征，进一步强调特征和类之间的相关性．

2.4 期望交叉熵ECE

交叉熵，与信息增益类似，但其只考虑特征在文本中出现的这种情况．假定c为文本类变量，C为文本类的集合，对于特征f，其交叉熵记为CE(f)，则有：

(4)

若只考虑单个类，则有：

(5)

3 核覆盖算法

核覆盖算法就是在普通覆盖算法上引入支持向量机SVM的核函数法的一种新算法，用它来处理高维海量数据的学习方法[4-7]．

核覆盖算法利用核函数将数据映射到一个更易识别的高维空间,然后在此空间中利用普通覆盖算法进行求解．这样不仅克服了原覆盖算法映射到一个充分大的球面上的不足，而且其识别的方法简单，准确率高[8-10]．

具体算法如下：

①先计算所有样本的中心，再找离中心最近的样本点t，并从该样本点t开始覆盖；

②求出离t最近的异类点的距离x1和离t最远的同类点的距离记为x2(x2

③求领域C(t)所覆盖的点的重心t′,按②步骤计算其半径,得球形领域C(t′)；

④重复②③，直到覆盖的样本数少于求重心前的样本数；

⑤求t的平移点t″,并求对应的球形领域C(t″).若C(t″)覆盖的点数大于C(t),则进入③,否则,得到一个覆盖K1类点的局部最大领域C(t)，覆盖的K1中的子集记为K1i；

⑥找一个不同类的点t开始覆盖，其类别为K2，令T<-K1/K1t，K1<-K2，K2<-T；

⑦重复②～⑥，直到处理完所有类点．

4 实验结果

选取中文自然语言处理平台的计算机等五类中文文本,采用多种特征提取方法对高维文本数据进行多次实验，本文所有实验都是在CPU为intel pentinum4 2.6 GHZ,编程环境为MATLAB6.5.1下完成的．实验结果如表1所示．

表1 不同特征选取的实验结果对比表

从实验结果中，我们看到：

①对语料库中的文本信息采用不同的特征选取方法，得到的实验结果相差较大．其中互信息MI方法只有不到40%的识别率，这是由于互信息特征提取方法受词条边缘概率的影响较大，易造成互信息评估函数经常倾向于选择稀有单词而删除高频的有用词条，从而造成较低的识别率和文本覆盖数较少．而其它的几种特征选取方法得到的识别率和覆盖数都比较高．

②构造性学习虽然在多文本分类问题上处理效率高，但存在计算量大等不足．而核覆盖算法将SVM 中的核函数法与覆盖算法相融合，克服了以上缺点，具有运算速度快、精度高的优点．但其也存在一些不足，如核函数的参数选取对实验的结果影响较大，需经过多次的实验及计算才能找到合适的参数，造成文本分类工作量的增大．

[1]杨丽玲.基于概率的覆盖算法在文本分类器中的应用[J].漳州职业技术学院学报，2009，11(2):1～3．

[2]陈 涛,谢阳群.文本分类中的特征降维方法综述[J].情报学报，2005，24(6):690～695．

[3]刘 里.中文文本分类而有信中特征描述及分类器构造方法研究[D].重庆：重庆大学，2006．

[4]吴 涛,张 铃,张燕平.机器学习中的核覆盖算法[J].计算机学报，2005，28(8):1295～1301．

[5]赵 姝，张燕平，张 媛，等.基于交叉覆盖算法的改进算法——核平移覆盖算法[J].微机发展,2004,14(11):1～3．

[6]吴 涛，张燕平，张 铃.前向神经网络交叉覆盖算法的一种改进[J].微机发展,2003,13(3):50～52．

[7]赵 姝，张燕平，张 铃，等.覆盖聚类算法[J].安徽大学学报(自然科学版)，2005,29(2):28～32．

[8]苏小英,胡彦鹏,杨竣辉,等.一种新的用于文本分类的概率分类器设计[J].计算机技术与发展,2014,24(3):46～48,53．

[9]董 贺,荣光怡.数据挖掘中数据分类算法的比较分析[J].吉林师范大学学报(自然科学版)，2008,29(4):107～108．

[10]田苗苗.基于决策树的文本分类研究[J].吉林师范大学学报(自然科学版)，2008，29(1):54～56．