应用特征聚合进行中文文本分类的改进KNN算法-Journalof

1、第 24卷第 3期东 北 大学学 报( 自然科学版 )Vol124 ,No. 32003年3月Journal of NortheasternUniversity()Mar.2003Natural Science文章编号 :1005 23026 ( 2003) 0320229 204应用特征聚合进行中文文本分类的改进KNN 算法张晓辉,李莹,王华勇,赵宏( 东北大学软件中心 , 辽宁 沈阳110004 )摘要 : 针对以KNN 为代表的VSM 模型存在的向量各特征项孤立处理问题,提出了一种应用特征聚合方式的改进算法?该算法通过CHI 概率统计计算文本特征词对分类的贡献, 将对分类有相同贡献的文本

2、特征词聚合, 使用它们共同的分类贡献模式代替传统算法中单个词对应向量一维的方式 ?该算法提高了稀有词对分类的贡献、强化了关联词的分类效果、并降低了文本向量的维数?与传统KNN 算法进行的对比实验证明,该算法明显提高了分类的准确率和召回率?关键词 : KNN 算法 ;中文文本分类; 分类贡献模式;特征聚合中图分类号: TP 391 ;TP 393文献标识码: A文本自动分类通常指将一篇文章自动指定至一个或几个预定义的文本类别中 ? 现有方法主要包括支持向量机 ( SVM ) 、K 近邻 ( KNN ) 、神经元网络 ( Nnet ) 、线性最小二乘方估计 (LL SF) 和贝叶斯算法 (Baye

3、s) 等 1 ?其中多数方法采用向量空间模型 ( VSM ) ,即将文本向量化为向量空间的点,通过计算向量间夹角距离决定文本所属类别?有些研究则完全放弃提出了自己的解VSM ,决办法 ?如文献 4 提出一种概念推理网模型, 通过机器学习和数据挖掘等技术进行知识获取并最终形成若干个概念推理网?通过知识库进行分类前的降维优化5 、应用 SVM 6 进行自动文本分类 7 等方面的研究也显示出了其有效性?事实上 ,KNN 被证明是效果最好的VSM 方法之一 1 ,8 ,所以本工作仍以KNN 为基础进行 ?1 KNN 文本分类算法及改进算法分析KNN 是一种基于实例的文本分类算法,首先为测试文本属于超过

4、阈值的所有类?目前提取特征词的方法主要有7 种3 :互信息 、期望交叉熵 、信息增益 、文本证据权 、几率比 、词频法和 CHI 概率统计 ? 针对 Reuters221578 和OHSUM ED等数据集合的一个测试结果证实CHI 概率统计通常比其他特征词提取方法优越 9 ? CHI 的主要思想是认为词与类别之间符合 2 分布 ,2 统计量的值越高 , 词和类别之间的独立性越小 、相关性越强 , 词对这一类别的贡献越大 3 ?一般取单词在所有类别中的平均值或所有类别中的最大值为其 CHI 值 ?特征词在文章中的特征值一般采用 TF2IDF 公式8计算,并需要对向量归一化 X =( x1 , x

5、2 , , x n)( x1 , x2 , , x n)?然后通过求两个向量的夹角余弦值 10 计算文本相似度?还可采用加权方式突出不同维的重要程度 2 ?KNN 被认为是VSM 理论下最好的分类算法 1 ,8 ?但 KNN 算法同样存在VSM 的不足 :一方将测试文本特征化为一个向量, 然后通过计算向面 若选取特征词的数量过大将导致文本向量维,量的夹角余弦值得到它与训练样本集中每个文本数很高 ,增加计算开销 ;同时 ,相当多的维对类别没的文本相似度 依文本相似度找出k 个最相似的,有足够的区分能力 ?而单纯减少特征词数又会丢失训练文本 ,把测试文本指派给其中相似样本最多分类工作的重要信息 ?

6、另一方面 ,向量距离计算不的一类 ?为了分类合理 , 需要选定一个阈值 , 可认涉及向量中各特征间的关系,各项平均用力 ,这使收稿日期 : 2002209205基金项目 : 国家“八六三”高技术计划项目 ( 86323062ZD0220226) ?作者简介 : 张晓辉 ( 1972 - ) ,男 ,辽宁沈阳人 ,东北大学博士研究生; 赵宏 (1954 - ) ,男 ,河北河间人 ,东北大学教授 ,博士生导师 ?230东北大学学报(自然科学版 )第 24卷得距离计算不精确,进而影响分类的精度 ?特征属性 ,认为它们具有相同的分布模式?通过分针对KNN存在的问题,出现了一些改进算析5 000个特征

7、词的CHI分布曲线可知每个词,法 ,并取得了一定的效果?文献 2 提出了一种最大 CHI 值变化范围是81347 877 761566 93 ,WA KNN 的加权方法 ,该方法在给每个特征词加大部分 CHI 值均低于5 ?由此定义特征词的规格权时 ,逐一尝试权值,直到找到最有效的为止?化分类贡献向量为 :WA KNN 方法取得了一定的效果,但计算代价也val uet=(t)(),同时大幅增加 ?文献 3 也针对 KNN 的缺点提出val ue i ,1 i C其中 , val uet i = 2 ( t ,i ) /5, (1iC) ?改进 ,它主要考虑文档间特征词属性关联与“共现”对相似度

8、的作用用一个匹配系数调整两文档,间的距离 ?其实质是对相似度的一种加权,未对特征词的选取和特征向量做任何改进?2应用特征聚合技术的改进 KNN 分类算法传统 KNN 方法存在缺陷 ,现有改进算法并不理想 ?需要通过分析特征词的分类贡献找出相互关联的词,并把它们聚合为一个特征项? KNN方法中之所以可采用 CHI 统计方法提取特征词,是因为它体现了词与文本类别间的相关程度?这种相关程度恰恰表示了词条对某一类别的贡献?因而有理由认为 :具有相同 CHI 分布的特征词对分类有相同的贡献 ?本算法通过如下几个方面对传统KNN 算法进行了改进 ,其中特征聚合是改进的关键?2. 1 提取特征词本算法不介意

9、特征词数目 ,因为向量的维数和特征词数间不成正比关系 ?它的目标是聚合属性相近的特征词 ,去掉那些区分能力不强的词 ?在以下算法描述中 , 使用 CHI 统计值选出前 5 000 个特征词 ?2. 2 特征聚合每个特征词t 都能得到C (类别总数 ) 个 CHI值 ,表示为 2 ( t , i ) , (1 i C) ?于是 ,每个词可得到一条其对分类的贡献分布曲线?可认为那些有相同分布曲线的特征词是相互关联的 ,对分类有相同的贡献 ?通过下面的分析 ,能得到一种通用方法 , 可以将分类贡献分布相同的词聚合为一个模式 ?从而最终得到 m 个不同的分布模式 ( m 0t( ) 的所有特征词聚合认

10、为ue j = 01 j C ,j i,它们有“相同分布模式” ?图 2规格化以后的CHI 分布模式Fig. 2Formalized CHI distributionpatterns所有的 5 000 个特征词经过上面公式规格化并应用聚合规则后,最终得到了776 个不同的分布模式 ?其中最大的模式包含 266 个特征词 “(致癌物质”等 ,均只在大众科技类别出现 ) “;考生”、“考试”和“学生”规格化并应用聚合规则后,合并为一个模式 ?同时 ,模式和类别间无一一对应关系 ,如包含特征词 “留学生” 的模式同时对应国际第 3 期张晓辉等 : 应用特征聚合进行中文文本分类的改进KNN 算法231

11、新闻和文教卫生两个类?2. 3 构造特征向量每篇文章都根据所有不同的分布模式构造成一个m 维的向量 ?仍用TF2IDF 公式计算特征词的特征值 ?同一维所有特征词的特征值相加,其和作为文本向量这一维的值,即 xi =vi ? 并对1 6i m其归一化得到特征向量?算法的其他部分与传统方法相同 ?3 对比实验与分析3. 1 数据和评估方式测试环境为P2内存 、10 ,并800 ,128 MVC6利用如下数据进行了测试?目前为止,在中文文本分类中还没有一个标准的 、普遍可接受的训练集和测试集?因此 ,采用自己制作的一套训练集和测试集文本对传统KNN 方法和聚合方法进行结果对比:通过开发的一个网络新

12、闻搜索系统来获得 Internet 新闻网站的信息 ?该系统覆盖了新浪 、搜狐 、新华网 、证券之星等 400 余个中文网站 ?去除重复新闻后 ,将相邻两天的网上新闻手工分成15 个类别 ?前一天的作为训练集 ,包含 10028 篇文本 ; 后一天的作为测试集 包含篇文本?由于网络信息分布不,11 458均衡 每类中的文本数不同(见表 ),1 ?表 1 各个类别的宏平均召回率( maR) 与准确率 ( maP) 对照表Table 1maR and maP result of the test类 别数据量传统算法2000词传统算法5000词特征聚合/ 个m aR/ %m aP/ %maR / %

13、m aP/ %maR / %maP / %1.国际新闻2 28587. 490. 083.894.788.091.22.大陆新闻1 86566. 868. 958.674.766.168.53.港澳台新闻39075. 174. 074.187.388.987.24.社会新闻1 60564. 767. 344.668.065.565.85.国内足坛47180. 792. 278.394.189.095.16.国际足坛56786. 490. 381.695.793.193.87.篮排球16090. 089. 681.898.595.692.68.棋牌7780. 596. 972.798.297.7

14、98.79.综合体育报道37081. 987. 372.289.385.688.1A. 生活时尚17760. 569. 925.471.490.490.9B. 影视娱乐72578. 764. 853.988.480.077.7C. 休闲旅游3548. 642. 58. 5721.474.370.3D. 计算机科技92980. 587. 261.990.993.493.5E. 大众科技12846. 152. 734.356.469.574.2F. 文教卫生24434. 837. 031.649.360.471.0使用的中文分词系统包含98 000个基本词表1为各类大小、和maP对比结果,表m a

15、R条的词库 ,可根据规则区分出姓名、地名等 ; 并使2 是测试结果的mi R 和 mi P 图 3 和图 4为按类?用停用词表去除无用词?使用 CHI提取特征词 :别进行的结果对比 ?传统 KNN 算法分别提取2 000 个和 5 000 个特征表 2微平均召回率与准确率对照表词 ; 改进算法提取5 000个特征词 ,经特征聚合后Table 2miRandmiP result of the test5 000 维降低为776 个模式 ?项目传统 2 000 词传统 5 000 词 特征聚合规定每个文本至多属于一个类? 选取 KNN/ %/ %/ %微平均召回率 miR70. 8557. 568

16、2. 50的 k 近邻值为10?对于一篇测试文本,将所有与微平均准确率 miP74. 0478. 5683. 91其相似度大于15的训练文本按相似度降序排0列计算前10个分属各类别的总和找出最大值,所属的一类 ,即将测试文章归入此类? 若无大于015 的相似度,则认为该文本不可分类?3. 2 测试结果及分析计算两个基本指标:召回率 ( recall) 和准确率(precision)9;并使用两种评估方法:微平均和宏平均 ?微平均 ( micro2average) 指所有类的准确率和召回率平均值 ; 宏平均 ( macro2average) 指每单图 3按类别对照两种方法的召回率个类的准确率和召

17、回率平均值1 ?Fig. 3Comparationof recall232东北大学学报(自然科学版 )第 24 卷分类算法能够解决关联特征维的提取和向量空间维数高的问题?实验证明 , 它比传统 KN N 分类算法 ,明显提高了分类的准确率和召回率, 是一种文本分类的新尝试?图 4按类别对照两种方法的准确率Fig. 4Comparationof precision从上面的结果可以看出, 改进算法使准确率和召回率有显著提高?对于如篮排球类 、棋牌类 、计算机科技类等类别界限较清晰的类, 准确率和召回率提高比较明显?这些类别有些是由于其划分比较细,如体育类可分成若干明显内聚的小类;有些是类别本身的区

18、分特征非常明显 , 如计算机科技类 ?而对于有交叉和类似内容的类别 ,如大陆新闻和社会新闻 ,由于区分特征不明显 ,则特征聚合方法对其影响不大 , 甚至导致了准确率和召回率的下降 ,可通过选取代表性强的文章及特征项加权的方式来解决 ?改进算法的学习时间(44 mi ns) 较原始算法(37) 要长,而分类时间基本相同(29)mi nsmi ns?相对于结果的质量提高,这个时间是可以接受的?总的说来 , 特征聚合的KN N 改进算法比传统算法优越的主要原因有以下3 点 ?1) 聚合使特征词对分类更有效,突出了稀有词 , 并排除了大量对分类无意义的低有效词 ; 2) 多特征词聚合成的相同分布模式代

19、替原有向量中一维表示一个特征词的作法 , 加强了特征项对文本分类的贡献 , 起到了自动提取相关概念的作用 ;3) 聚合模式降低了向量的维数,大大缩减了计算开销 ?4结论本文提出的基于特征聚合模式的KNN 文本参考文献:1 YangY ,L i uX.Are2exami nation oftextcategoriz ationmethods A .Proceedings, 22nd AnnualInternationalACMSIGIRConference on Research and Development in Informa 2tion Retrieval(SIGIR ) C.Berke

20、ley:A CMPress ,991999 .42 - 49.2 HanEH ,GeorgeK , VipinK.Textcategorizationusingweightadjustedk 2nearest neighborclassif icationR .Techni 2cal Report# 002046 ,Universityof Minnesota,2000.3 孙丽华 , 张积东 ,李静梅 ? 一种改进的 KN N 方法及其在文本分类中的应用 J ?应用科技? 2002 , 29():25 - 27?2( S unLH ,ZhangJ D ,L i J M.A n i m pro

21、vedknnsystemand itsapplicationto textclassif icationJ .Applied Scienceand Technology ,2002 ,29 (2) : 25 - 27. )4 李晓黎 , 刘继敏 , 史忠植? 概念推理网及其在文本分类中的应用 J ? 计算机研究与发展 , 2000 , 37( 9) : 1032 - 1038?( L i X L ,L i u JM,S hiZ Z.The concept -reasoni ng net2workanditsapplicationi n textclassif icationJ . Journa

22、l ofComputer Research&Development , 2000 , 37 ( 9 ) : 1032 -1038 . )5 刁倩 , 张惠惠 ,王永成 ,等? 中文文献自动分类中的知识库构造及其仿人算法 J ? 情报学报 , 2000 ,19 (3) :248 - 253?( Diao Q , Zhang H H , WangY C , et al .Know ledge baseconst ructingandaperyalgorithmi n Chi nese automaticcate 2gorizingJ .Journal of The China Society Fo

23、r Scientific andTechnical Information,2000 ,19 ( 3) :248 - 253. )6 Joachi msT.Advancesin kernel methods2supportvectorlearning M.Cambri dgeMA: M I T Press ,1998 . 169 -184 .7 Joachi msT.Opti mizingsearchengi nes usi ngclickthroughdataA .The EighthACM SIGKDD International Confer2enceonKnowledge Discov

24、ery and Data Mining( KDD2002 ) C.Edmonton:A CMPress , 2002 . 102 - 110 .8 He J ,Tan A H , TanC L.Acomparativestudy on chi nesetext categorizationmethodsA .Proceedingsofthe Interna 2tional Workshop on Text and Web Mining C .Si ngapore :Melbourne, 2000 .24 - 35. 9 YangY ,Pedersen J P. A comparativest

25、udy on f eat ure se2lectioni n text categorization A.Proceedings of theFour2teenthInternationalConferenceonMachineLearning( ICML 97) C. SanFrancisco : MorganKaufmannPub2lishers, 1997 . 412 - 420 . 10SlatonG.Automatictextprocessing : thetransformation ,analysis, and retrievalof informationby computer M .MA :A ddison 2Wesley Publishi ng Co , 1989. 202 - 220.AnImprovedKNNAlgorithmAppliedTermFeatureCombinationTechnology forChinese TextualCla