（计算机应用技术专业论文）二阶段文本分类器及分类在推荐系统中的应用.pdf

摘要 文本分类在文本挖掘和信息检索系统中发挥着重要的作用。这种技术可以改 善检索性能、提供导航浏览机制、发现相似文本等。因此，文本分类已成为一 种处理和研究文本的重要技术。 目前，基于统计和机器学习的文本分类算法已经比较成熟，但可以考虑通过 某种方式引入其他方法来改进分类效果，比如下面所提的统计方法。分类算法除 了在文本挖掘和信息检索系统中发挥着重要的作用外，还可以考虑在电子商务个 性化推荐系统中的应用。针对上述二方面，本人做了以下工作i 第一：提出了基于k m e a n s 的二阶段多类s v m 分类方法。该方法分为二个 阶段，第一阶段采用k m e a n s 聚类，在聚类结束以后，抽样调查每个小类的分类 精准度，完全分对的类可以不必进行第二步的分类，从而降低了已经聚类正确的 实例再次分类的风险：第二阶段采用l i b s v m 来进行分类。本文在理论论证后， 使用中英文语料，通过实验证实该方法切实可行，相较于直接使用l i b s v m 进 行分类，分类准确度分别提高了9 3 5 和1 5 。 第二：用户个性化推荐是电子商务领域中的研究热点与核心技术，近年来得 到了广泛的关注和快速的发展，本文将分类技术引入推荐系统。文中提出了基于 分类的用户多兴趣个性化推荐方法。该方法分为二个模块，第一模块是长期兴趣 模块( l i m ) ，针对用户多兴趣的特征，通过分类来提高推荐准确度；第二是短 期兴趣模块( s i m ) ，针对用户短期兴趣的专注性，引入w e b 日志上下文分析的 方法。最后，本文分别对l i m 和s i m 进行了实验证实，证实该方法切实可行， 相较于传统方法，推荐准确度及用户满意度都得到了较好提升。 关键词：文本分类，k 。m e a n s ，二阶段多类s v m 分类方法，用户个性化推荐 v a b s t r a c t t e x tc l a s s i f i c a t i o np l a y sa ni m p o r t a n tr o l ei nt e x tm i n i n ga n di n f o r m a t i o n r e t r i e v a ls y s t e m s i tc a l li m p r o v et h er e s u l to fq u e r i e s ；p r o v i d ei n t u i t i v en a v i g a t i o na n d b r o w s i n gm e c h a n i s m s ；a n df i n ds i m i l a rt e x t s t h e r e f o r e ，t h et e x tc l a s s i f i c a t i o nh a s b e c o m ea ni m p o r t a n tt e c h n o l o g yt or e s e a r c ha n dt r e a tt h et e x t a tp r e s e n t ，b a s e do nt h es t a t i s t i c sa n dm a c h i n el e a r n i n gt e x tc a t e g o r i z a t i o n a l g o r i t h mh a sm o r em a t u r e ，b u tc a nc o n s i d e rw a yi n t oo t h e rw a y st oi m p r o v e c l a s s i f i c a t i o ne f f e c t , f o re x a m p l es t a t i s t i c sm e t h o db e l o w e x c e p ti nt h et e x t c l a s s i f i c a t i o na l g o r i t h ma n di n f o r m a t i o nr e t r i e v a ls y s t e mp l a y sa ni m p o r t a n tr o l e ， c l a s s i f i c a t i o na l s ot a i lp l a yar o l ei np e r s o n a lr e c o m m e n d e rs y s t e m b a s e do nt h e a b o v ei s s u e s ，id ot h ef o l l o w i n gw o r k ： 1 i nt h i sp a p e r , t w os t a g e sm u l t i - l a b e ls v mc l a s s i f i e rb a s e do nk - m e a n sh a s b e e np r o p o s e d t h i sm e t h o dd i v i d e si n t ot w os t a g e s ，t h ef i r s ts t a g eu s e st h ek - m e a n s c l u s t e r , e n h a n c e st h ec l u s t e ra c c u r a c yt h r o u g ht h es a m p l i n gp r e c i s i o n ；，i nt h ee n d ，t h e c l u s t e rs a m p l i n gs u r v e yo fe a c hs m a l lc l a s s i f i c a t i o na c c u r a c yo fc l a s si fi ti sf u l l r i g h t ， t h es e c o n ds t e pi s n tb ec l a s s i f i e d ，t h e r e b yh a sb e e nr e d u c e do n c ea g a i na ne x a m p l e o ft h ec o r r e c tc l u s t e r i n go fr i s kc l a s s i f i c a t i o n ；t h es e c o n ds t a g eu s e sl i b s v mt oc a i t y o nt h e c l a s s i f i c a t i o n t h i sa r t i c l ea f t e rt h e o r yp r o o f , u s e st h ee n g l i s ha n dc h i n e s e l a n g u a g et e s ts e t s ，t h r o u g he x p e r i m e n tc o n f i r m e dt h a tt h i sm e t h o dw a sp r a c t i c a la n d f e a s i b l e ，c o m p a r e dt o t h ed i r e c tu s eo fl i b s v mc l a s s i f y , t h ec l a s s i f i e da c c u r a c y i n c r e a s e d9 3 5 a n d1 5 ，r e s p e c t i v e l y 2 p e r s o n a l i z e dr e c o m m e n d e rs y s t e ma r eh o ts p o t sa n dc o r et e c h n o l o g yi nt h e f i e l do fe = c o m m e r c e i nr e c e n ty e a r s ，i th a sb e e nw i d e s p r e a dc o n c e ma n dr a p i d d e v e l o p m e n t i nt h i sp a p e r , w ep r o p o s e ab a s e do nt h ec l a s s i f i c a t i o no fu s e r s m u l t i - i n t e r e s ti np e r s o n a l i z e dr e c o m m e n d e rs y s t e m t h em e t h o di sd i v i d e di n t ot w o m o d u l e s ，t h ef i r s tm o d u l ei st h el o n g - t e r mi n t e r e s tm o d u l e ( l i m ) ，f o rt h e u s e r s m u l t i - i n t e r e s tc h a r a c t e r i s t i c s ，t h r o u g ht h ec l a s s i f i c a t i o nt oi m p r o v et h ea c c u r a c y r e c o m m e n d ；t h es h o r t t e r mi n t e r e s tm o d u l ei st h es e c o n dm o d u l e ( s i m ) ，f o ru s e r s i n t e r e s t e di ns h o r t - t e r mf o c u s ，j o i n e dt h ec o n t e x to ft h ew e bl o ga n a l y s i s f i n a l l y , t h i sa r t i c l ec a r r yo u tt h ee x p e r i m e n tc o n f i r m e dt h el i m & s i mc l a s s i f i c a t i o ne f f e c t f e a s i b l e c o m p a r e dt o t r a d i t i o n a lm e t h o d s ，r e c o m m e n d e ra c c u r a c ya n dc u s t o m e r v l s a t i s f yh a v e b e e nu p g r a d e d k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；k r e c a l l sc l u s t e r i n ga l g o r i t h m ；t w os t a g e sm u l t i l a b e l s v mc l a s s i f i e r ；p e r s o n a l i z e dr e c o m m e n d e r v i l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得江西财经大学或其他教育机构的学位或证书所使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 张蝉吼丑里方 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其 他复制手段保存论文。 ( 保密的论文在解密后遵守此规定) 兰徭 日期：2 2 ：堕2 口 1 绪论 l 绪论 1 1 课题的背景及意义 随着i n t e m e t 的迅猛发展，w e b ，电子邮件，聊天室和数字图书馆等电子文 本成几何级数迅猛增长，当前我们正处于一个信息爆炸的时代。假定信息杂乱无 序，信息量又如此巨大，我们将很难找到自己所需的信息。一方面，互联网上面 蕴涵的信息是海量的，人们可以随意获取，但是面对规模巨大的信息汪洋，人们 又无法有效地利用这些资源，这增加了人们对于快速、自动文本分类的迫切需求： 另一方面激增的信息资源又为基于机器学习的文本分类方法准备了充分的实验 数据。通过文本自动分类系统把文本数据进行归类，可以帮助人们更好地发现、 过滤和分析文本信息资源。 文本分类是基于文本内容将待定文本划分到一个或多个预先定义的类中的 方法，最初的文本分类是依靠专家手工进行的，它对领域知识要求较高且花费巨 大，不能满足大规模文档处理的要求。2 0 世纪9 0 年代逐渐成熟的基于机器学 习的文本分类方法，更注重分类器的模型自动挖掘和生成及动态优化能力，在分 类效果和灵活性上都比之前基于知识工程和专家系统的文本分类模式有所突破， 成为相关领域研究和应用的经典范例。典型的自动文本分类方法包括决策树和规 则学习算法、回归方法、k n n 方法、朴素贝叶斯方法、神经网络、支持向量机 篁f l 】 寸。 文本自动分类的目的就是对文本集进行有序组织，把相似与相关的文本组织 在一起。它作为知识的组织工具，为信息检索提供了更高效的搜索策略和更准确 地查询结果，使得检索的查全率和准确率都得到了提高。传统的人工分类的做法 存在许多弊端，如耗费大量人力、物力以及精力，且分类结果一致性不高。因而， 构造一个有效的文本分类系统是十分必要且必需的。文本分类作为信息过滤、信 息检索、搜索引擎、文本数据库、数字化图书馆等领域的技术基础，有着广泛的 应用前景。 1 2 国内外研究现状 1 2 1 国外现状 国外自动分类研究始于1 9 5 0 年末，h p l u h n 在这一领域进行了开创性的研 二阶段文本分类器及分类在推荐系统中的应用 究，他将词频统计的思想引入文本分类中。接着，1 9 6 0 年m a r o n 在j o u r n a lo f a s m 上发表了有关自动分类的第一篇论文“o nr e l e v a n c ep r o b a b i l i t i ci n d e x i n ga n d i n f o r m a r i o nr e t r i r a l ”。其后许多学者在这一领域进行了卓有成效的研究。国外文 本数据分类研究大体上可以分为三个阶段： 第一阶段是从2 0 世纪6 0 年代直到2 0 世纪8 0 年代前，m a r o n 和k u h n 提出了概率 标引模型，并应用于信息检索领域【2 ，3 】；1 9 6 2 年r o s e n b l a t t 设计了感知机，通过具 有阈值的神经元处理二类分类问题【4 】；s a l o n 于1 9 7 5 年提出了向量空间模型用于 对文本进行描述1 5 1 。这一阶段主要是集中在对分类理论的研究。 第二阶段是2 0 世纪8 0 年代到9 0 年代。这期间最有效的文本分类系统一直 是由专家人工构建的基于知识工程技术的分类系统。典型的系统为c o n s t r u e 系 统。 第三阶段是9 0 年代以后，基于机器学习和统计学习的分类技术开始取代基 于知识工程的方法成为文本分类的主流技术，这种分类方法不再需要专家的介 入，节约了大量的人力资源，同时加快了分类系统的建立速度，至此，文本自动 分类技术才开始蓬勃发展，形成了众多的分类模型和分类算法。 国外当前流行的文本分类方法包括r o c c h i o 法及其变异方法、k 近邻法 ( 1 心n ) 、决策树、朴素贝叶斯、贝叶斯网络、支持向量机( s v m ) 等方法。近几 年，国外的研究主要集中在以下几方面：一方面是针对已有分类方法进行改良， 如使用词典【1o 】或w i k i t l l l 扩展特征值选取，一方面是针对半监督文本分类方法的 研究【1 扣1 3 1 。 国外很多研究人员对英文文本分类领域的各个问题都有相当深入的研究，对 几种流行的方法进行了大量的对比研究。s e b a s t i a n if 与y a n gy i m i n g 1 ，1 4 1 分别在 一些标准英文文本分类数据集上对一些流行的方法进行了理论分析和对比研究。 结果表明这些算法各有优缺，没有占绝对优势的算法，总的来讲，支持向量机、 k 近邻和神经网络具有比较高的分类准确率，但是它们的分类时间比较长，而贝 叶斯方法分类精度稍差但具有较快的分类速度。找到一种分类精度高分类速度快 的文本分类算法是文本自动分类领域的研究方向之一。 1 2 2 国内现状 国内对文本分类的研究起步较晚，开始于2 0 世纪8 0 年代初期。大体上经历 2 1 绪论 了可行性探讨、辅助分类、自动分类系统三个发展阶段。早期对中文文本的分类 研究较少，采用的技术也主要是把英文文本分类的技术应用到中文文本分类当 中。自上世纪9 0 年代后期才开始着重于对中文文本分类的研究，结合中文文本 的特点，形成中文文本数据分类研究体系。 1 9 8 1 年候汉清先生首先对自动分类在文献中的应用作了探讨，从计算机管 理分类、计算机分类检索、计算机自动分类、机编分类等四个方面介绍了国外的 发展概况【1 5 1 。这是理论方面，随后在1 9 8 6 年，上海交大电脑应用技术研究所的 朱兰娟、王永成等开发的中文科技文献( 计算机类) 实验性分类系统。该系统检索 并累计特征词在类主题表中的类归属度，采用b a y e s 分类准则，对每一篇文献计 算相应的条件概率，当该文献属于某一类的条件概率超过一定闽值的时候，就把 它划分为该类，但是由于该系统缺乏全文、没有摘要、类目必须事先确定，分类 结构粗糙，不适合专用文献【1 6 】。1 9 9 8 年，东北大学的计算机系的张月杰、姚天 顺研制的新闻语料汉语文本自动分类模型，通过计算预定义类别和文本特征项之 间相关性来进行自动分类的。该分类方法的特征向量规范化，采用多重加权处理 方法【17 1 。 在评测方面，已经有了比较标准的语料库，如复旦大学自然语言处理小组提 供的文本分类语料库和人民日报标注语料库，一些搜索引擎公司也提供相应的语 料的下载，如s o h u 等；在分词方面，主要的代表是中科院计算所中文词语一 体化分析系统i c t c l a s ，其次有国家语委文字所应用句法分析技术的汉语自动 分词系统、清华大学的s e g t a g 系统和哈尔滨工业大学词法分析系统等。这些 都为中文文本分类技术的深入研究提供了一个良好的环境。现有中文文本分类的 方法是支持向量机、最近邻分类、b o o s t i n g 、基于序列的文本分类等。 以计算机学报、软件学报、中文信息学报近期发表的文章为参考，可以大致 了解国内这二年的研究状况。针对基于支持度一置信度架构的关联分类方法仅仅 是选择频繁文字构建分类规则，忽略了文字的分类有效性，陈志雄等人提出了基 于信息增益的关联分类算法【1 8 】。孙景广等人提出了一种使用知网作为语义资源选 取分类特征，并使用最大熵模型进行分类的方法，该方法用于问答系统中的问题 分类【1 9 1 。针对半监督的文本分类，郑海清等人提出一种基于紧密度衡量的半监督 的文本分类算法，其主要思路是先提取出一些可信的负例，然后再根据紧密度衡 二阶段文本分类器及分类在推荐系统中的应用 量对提取出的负例集合进行扩展，进而得到包含正负例的训练集合，从而提高分 类器的性能【2 0 1 。最近邻分类器是假定局部的类条件概率不变，而这个假定在高维 特征空间中无效，王煜等人针对这种情况提出了一种改进k n n 算法1 2 。由于 l 心n 分类方法存在着计算量大和训练文档分布不均所造成的分类准确率下降等 问题，王修君等人提出基于最小化学习误差的增量思想，将学习型矢量量化( l v q ) 和生长型神经气( g n g ) 结合起来提出一种新的增量学习型矢量量化方法【2 2 1 。 文本分类的研究主要围绕算法方面进行，如特征提取、权重计算、分类模型 的算法的分析与改进，而刘华则从特征项的粒度选择和获取方面进行研究，认为 关键短语作为特征项有助于文本分类】。王小冷等人提出基于n 一伊锄模型的 贝叶斯分类方法，该方法利用了所有相邻汉字之间的依赖关系，提高了抗噪音能 力【2 4 1 。孙宏纲等人将h o w n e t 语义词典引入到v s m 特征向量生成的过程中，通 过在语义层面扩展特征向量的维数，即合理地增加特征向量的维数，使扩展后的 特征向量不仅较好的符合原始文档的语义要求，又能满足v s m 分类模型的要 求，进而改善复杂语料的分类结剁2 5 1 。 数据流具有数据持续到达、到达速度快、数据规模巨大等特点，王涛等人针 对这种情况提出一种基于线索化排序- - x 树的增量模糊决策树分类算法【2 6 】。传统 的文本分类方法，即非增量学习算法，根据当前所获得的所有训练样本计算得到 文本分类模型，存在二方面问题，一是训练样本很难一次性获得，二是内存限制。 罗长升等人提出基于推拉策略的文本分类增量学习方法1 2 7 1 。随着深度网的重要日 益显著，d e e pw 曲数据库资源信息进行分类或聚类逐渐成为研究热点1 2 s l 。分类 器对某些类别的判别能力不强，我们称这些类别为混淆类。混淆类的存在造成了 文本分类性能的下降，朱靖波等人提出一种混淆类的判别技术，并采用两个阶段 的分类来提高分类性能【2 9 1 。l d a ( l a t e n td i r i c h l e ta l l o c a t i o n ) 模型是近年来提出 的一种能够提取文本隐含主题的非监督学习模型，针对l d a 模型用于分类时强 制分配隐含主题的缺陷，李文波等人提出提出了一种附加类别标签的l d a 模型 p o i o 总的来讲，国内在分类方面取得很大进展，但相对国外的研究还存一定差距， 需要我们进一步的研究。 1 3 本文的工作和论文组织 4 1 绪论 基于机器学习文本分类技术由文本的表示( r e p r e s e n t a t i o n ) 、分类方法及效果 ( e f f e c t i v e n e s s ) 评估三个部分组成。本文主要研究分类方法。聚类可以看成是无“标 签 的分类过程，与分类有着密切关系。本文针对二者的关系，提出先聚类再分 类的二阶段分类方法。其基本思想是：第一阶段先对文本进行聚类，并对聚类结 果进行样本抽样，对抽样结果不理想的类进行第二阶段分类。本文的主要工作有： ( 1 ) 采用k m e a n s 与s v m 结合，即：在第一阶段的聚类中采用k - m e a n s 算法， 第二阶段分类采用s v m 算法。第一阶段的k m e a n s 算法采用j a 、，a 实现，第二 阶段的s v m 采用l i b s v m 软件。方案采用中、英文语料。 ( 2 ) 作为中文文本分类技术的应用之一，根据当前电子商务推荐系统的不 足，提出基于分类的用户多兴趣个性化推荐方法。该方法分为二个模块，第一模 块是长期兴趣模块( l i m ) ，针对用户多兴趣的特征，通过分类来提高推荐准确 度；第二是短期兴趣模块( s i m ) ，针对用户短期兴趣的专注性，引入w e b 日志 上下文分析的方法。文中分别对l i m 和s i m 进行了实验证实，证实该方法切实 可行，相较于传统方法，推荐准确度及用户满意度都得到了较好提升。 本文的组织结构： 第一章：分析了分类技术发展的国内外现状，提出本文的工作及组织结构； 第二章：介绍中文文本分类基础理论和系统架构； 第三章：提出二阶段分类器的设计构想，并通过实验对分类器进行了实验； 第四章：在电子商务领域中，分类技术有着广泛的应用，本文根据现有推荐 系统的不足，提出基于分类的用户多兴趣个性化推荐方法； 第五章：对本文的工作进行总结，并提出下一步的工作打算。 二阶段文本分类器及分类在推荐系统中的应用 2 中文文本分类技术概述 文本自动分类的研究包括很多学科领域，包括自然语言处理，图书馆科学中 的分类学，数学领域的统计学等知识，以及计算机领域的模式识别、人工神经网 络等研究课题。本章将分别介绍文本分类的基本概念和文本自动分类系统的基础 理论及相关技术，并对其典型的系统结构进行了分析研究【3 1 1 。 2 1 文本分类定义 文本分类是指按照预先定义的分类体系，根据文本的内容自动地将文本集合 的每个文本归入某个类别，这是分类过程，它需经过二个过程：输入与输出，系 统的输入是需要进行分类处理的大量文本，而输出是与文本关联的类别。简单地 说，文本分类就是对文档标以合适的文本类标签。 从数学的角度来看，文本分类也可以看成是一个映射过程，它将未标明类别 的文本映射到现有类别中，这种映射可以是一一映射，也可以是一对多映射，因 为通常一篇文本可以与多个类别相关联。文本分类的映射规则是：系统根据已知 类别中若干样本的数据信息得出各类别的特征，然后总结出分类的规律性，建立 类别判别公式和判别规则，下次当遇到新文本时，根据总结出的类别判别规则确 定文本所属的类别，从而得到正确的分类判别。 在理论研究方面，对单类别分类的研究要多于对多类别分类的研究。主要原 因是由于单类别分类算法与多类别分类算法存在很多相通之处，二者之间的转化 必须满足这样一个假设条件，即各个类之间是独立的，没有相互依存关系或其它 影响，当然在实际应用中，绝大多数情况是可以满足此假设条件的。因此，在文 本分类的研究中，大部分实验都是基于单类别分类问题的探讨，不过，本文的研 究是基于多类别。 2 2 自动分词 汉语自动分词是对汉语文本进行自动分析的第一个步骤。大家可以这样设想 汉语自动分词过程的困难：如果把某个英语文本中的所有空格符都去掉，然后让 计算机自动恢复文本中原有的空格符，这就是词的识别过程，此过程的主要问题 是对大量歧义现象的处理；而中文文本是不存在空格的，所以相对于英文文本首 先必须解决分词的问题。 6 2 中文文本分类技术概述 分词体现了汉语与英语的显著的不同。英语文本是小字符集上的已充分分隔 开的词串，而汉语文本是大字符集上的连续字串。这里把字串分隔成词串，就是自 动分词系统需要做的工作。由于“在中文信息处理中，凡是涉及句法，语义等研 究项目都要以词为基本单位“，所以中文分词技术属于自然语言处理技术范畴， 对于一句话，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计 算机也能理解? 其处理过程就是分词算法，现有的分词算法包括三大类：基于字 符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。 2 2 1 自动分词方法 ( 1 ) 基于字符串匹配的分词方法【3 2 】 这类方法又称机械分词方法，它是按照一定的规则将待分析的汉字串与机器 词典中的词条进行配，若在词典中找到这个字符串，则匹配成功( 识别出一个词) ， 如没有找到则为不成功。机械分词的方法又可以按不同的方式区分为不同种类： 一是按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配二种方 法；二是按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最 短) 匹配方法：三是按照是否与词性标注过程相结合，又可以分为单纯分词方法 和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：正向最大匹 配法( 由左到右的方向) 、逆向最大匹配法( 由右到左的方向) 和最少切分( 使 每一句中切出的词数最小) 。 ( 2 ) 基于理解的分词方法 这种分词方法是在语义上进行分词，涉及到自然语言处理的知识，它通过让 计算机模拟人对句子的理解，达到识别词的效果，其基本思想就是在分词的同时， 进行句法、语义分析，利用语义信息来处理歧义现象。这种分词方法通常包括三 个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词 子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，这模 拟了人对句子的理解过程，它需要使用大量的语言知识和信息。但由于汉语语言 知识的复杂性，难以将各种语言信息组织成机器可直接读取与理解的形式，因此 目前基于理解的分词系统还处在试验阶段。 ( 3 ) 基于统计的分词方法 从形式上看，词是稳定的字的组合，所以在上下文中相邻的字同时出现的次 二阶段文本分类器及分类在推荐系统中的应用 数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的 反映成词的可信度，所以我们可以对语料中相邻共现的各个字的组合的频度进行 统计，计算它们的互现信息。这里，定义两个字的互现信息，用于计算两个汉字 x 、y 的相邻共现概率。注意，这里的互现信息体现了汉字之间结合大系的紧密 程度，当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词，反之 则不应该把它分成一个词。这种分词方法只需对语料中的字组频度进行预先统 计，并不需要切分词典，因而又叫做无词典分词法也称统计取词方法。但这种方 法也有一定的局限性，会经常抽出一些并不是词的常用字组，例如f 这一j 、我 的j 、之一j 、f 许多的j 、有的j 等，并且对常用词的识别精度不高，时空开销 很大。实际应用的统计分词系统都是与机械分词系统结合在一起使用，首先使用 一部基本的分词词典( 常用词词典) 进行串匹配分词，同时使用统计方法识别一 些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率 高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 2 2 2 分词中的难题 成熟的分词算法有了，是否就能容易的解决中文分词的所有问题呢? 事实远 非如此。中文不象英文，它是一种十分复杂的语言，让计算机理解中文语言更为 困难。在中文分词过程中，有几个难题一直没有完全突破。 ( 1 ) 歧义识别 典型的歧义有交集型歧义( 约占全部歧义的8 5 以上) 和组合型歧义。这种 歧义的消除只有向分词系统提供进一步的语法、语义知识才有可能作出正确的决 策。排除歧义常常使用的方法是添加其它信息，如词频、词长、词间关系等信息， 比如“真正在 这个组合中，“真作为单字词的频率大大低于”在”作为单字词的 频率，所以应切成”真正在”。有时切分歧义发生在- d , 段文字中，但我们为了排除 歧义则需要看较长的一段文字，比如”学生会”既可能是一个名词，指一种学生组织， 也可能是”学生会”，其中”会”为”可能”或”能够”的意思，具体取哪一种，还需要结 合上下文的信息，如在“学生会主席 中只能是前者，在”学生会去”中只能是后者， 在“学生会组织义演活动 中歧义仍然排除不了，则需要看更多的语境信息。 ( 2 ) 新词识别 新词就是那些在字典中都没有收录过，但又确实能称为词的那些词。典型的 8 2 中文文本分类技术概述 是人名，大家可以很容易理解句子f 王军虎去广州了j 中，王军虎j 是个词， 因为它代表一个人的名字，但计算机如何去识别就困难了。因为如果把王军虎j 做为一个词收录到字典中去，中国有那么多名字，且时时刻刻都有新增的人名， 收录这些人名本身就是一项巨大的工程，同时也会大大增加词典的容量，降低分 词的速度。即使这项工作可以完成，还是会存在其它问题，例如：在句子f 王军 虎头虎脑的j 中，f 王军虎j 就不能算词。新词中除了人名以外，还有地名、机 构名、商标名、产品名、省略语、简称等都是很难处理的问题，而且这些又正好 是人们经常使用的词。因此，分词系统中的新词识别十分重要，所以新词识别准 确率已经成为评价一个分词系统好坏的重要标志。 ( 3 ) 分词与理解的先后 计算机无法像人在阅读汉语文章时那样边理解边分词，而只能是先分词后理 解，因为计算机理解文本的前提是识别出词、获得词的各项信息。这就是逻辑上 的两难：分词要以理解为前提，而理解又是以分词为前提。由于计算机只能在对 输入文本尚无理解的条件下进行分词，则任何分词系统都不可能企求百分之百的 切分正确率。 2 3 文本表示 ( 1 ) 向量空间模型 文本是一个由众多字符构成的字符串，无法被学习算法自己用于训练或分 类，所以要将机器学习技术运用于文本分类问题，首先需要将作为训练和分类的 文档转化为电脑易于处理的向量形式。即运用各种文本形式化表示方法，最常用 的如向量空间模型对文档进行文本形式化表示。 文本形式化首先要解决的问题是特征粒度的选择，即是选择字、词、句或其 他来分类。刚开始的选择是用字，后来发现用二元同现字串的分类方法的准确率 要比用字的方法高，所以现在又使用词，随着汉语自动分词技术的日益成熟，基 于词的汉语文本自动分类已经成为了我们的一个研究热点。实践表明基于词的分 类方法优于基于字和基于二元同现串的分类方法。特征粒度确定了以后，通常文 本表示方法有：向量空间模型( v e c t o rs p a c em o d e l ) ，布尔模型( b o o l e a nm o d e l ) ， 概率模型( p r o b a b i l i s t i cm o d e l ) ，聚类模型( c l u s t e rm o d e l ) 和基于知识模型 ( k n o w l e d g e b a s e dm o d e l ) 等。 9 二阶段文本分类器及分类在推荐系统中的应用 g s a l t o n 提出的向量空间模型【3 3 】( v s m ) 有较好的计算性和可操作性，相对 应用也较广泛且效果较好的一种模型，向量空间模型成功应用于信息检索领域， 随后推广到文本分类领域。向量空间模型有一个基本假设是，一份文档所属的类 别仅与某些特定的词或词组在该文档中出现的频数有关，但是与这些单河或词组 在该文档中出现的位置或顺序无关。我们如果将构成文本的各种语义单位( 如单 词、词组) 统称为“词项 ，把词项在文本中出现的频数称为“词频 ，文档中蕴 涵的各个词项的词频信息就足以用来对其进行正确的分类。在向量空间模型中文 本被形式化为n 维空间中的向量： d = ( 2 1 ) 上式为第i 个特征的权重。如果特征项选择为词语，那么就刻画出了词语在 表示文本内容时所起到的重要程度。 ( 2 ) 权值计算公式 目前，赋权重最普遍的方法是运用统计的方法，即用文本的统计信息，主要 是词频信息，来计算特征项的权重。最初的特征项权重计算方法是o 、1 赋值法， 即布尔权重( b o o l e a nw e i g h t i n g ) 。如果特征项未出现，则其权重为零；如果特征 项出现次数大于零，则其权重为l 。布尔权重无法体现特征项在文本中的作用程 度，故逐渐被更精确的词频代替。 词频通常分为绝对词频和相对词频。绝对词频，就是使用特征项在文本中出 现的频率表示文本；相对词频为归一化的词频，计算方法主要运用t f i d f 公式。 其中t f 是特征项在文本中的绝对频率，而i d f 表示特征项在文本中的文本内频 数。t f 越大，此特征项在文档集中出现的范围越广，说明它的重要程度越高； i d f 越大，此特征项在文档中的分布越集中，说明它在区分该文档内容属性方面 的能力越强。 目前存在多种t f i d f 公式，下式是一种使用比较普遍的t f i d f 公式： 缈( f ，西：丝垒丝丝丝型坠一( 2 - 2 ) 蔚【( ，d ) l o g ( n n , + o 0 1 ) 】2 其中，w ( t ，孑) 为词t 在孑的权重，f ( t ，西) 为词t 在万的词频，n 为训练文本 的总数，为训练文本集中出现t 的文本数，分母为归一化因子。 ( 3 ) 相似度计算公式 1 0 2 中文文本分类技术概述 文档表示成向量后，文档之间的语义相似度就可以通过空间中的这两个向量 间的几何关系来进行度量，主要是采用有相似函数与距离函数两类函数。 相似度通常可以采用三种函数来计算，即内积、夹角余弦与相关系数。 内积函数是一种简单且常用的相似度计算函数，在基于支持向量的分类算法 中被广泛使用。计算公式如下： 溉= z z ( 2 - 3 ) j 夹角余弦函数是采用空间中的两个向量的夹角的余弦值来度量文档之间的 语义相似度。两个向量在空间中的夹角越小，余弦值就越大，表明其语义相似度 越高，文档越相似，反之如果夹角大，则文档相似度低。余弦函数是文本领域中 应用最广泛的相似度计算函数。它的计算公式如下： 置r s i m , = ，：兰：；：一 ( 2 - 4 ) ，yx ：r 2 y ，j 相关系数是对向量做标准差标准化后的余弦函数。它表示两个向量的线性相 关的程度。 2 4 特征提取 在中文文本分类中，文本集经过分词后变成词集，然后去掉停用词得到特征 集。但是，特征集一般仍然是个高维的特征空间，对于分类算法来说维数太大。 因此，面临寻求一种有效的特征抽取方法，用于降低特征空间的维数，提高分类 的效率和精度。特征提取算法是文本分类中的关键技术和瓶颈技术，如何找到最 小的特征子集来表达文本主题内容，是文本特征抽取算法的研究所在。 常见的特征选择f 3 4 】，【3 5 】有：信息增益( i g ) 、文档频率( d f ) 、z 统计- 量( c h i ) 、 互信息( m i ) 等。这些降维算法各有优缺点，需要根据具体系统应用来确定最优方 法。但其基本思想都是对每一个特征即词条，计算它的某种统计的度量值，然后 设定一个阈值t ，把度量值小于阈值t 的那些特征过滤掉，剩下的即认为是有效 特征。下面简单介绍一下常用的各种特征选择方法。 ( 1 ) 特征词的文档频率( d f ) 文本中某个特征的文档频率( d o c u m e n tf r e q u e n c y ，简记为d r ) 是指在文档集 中含有该特征的文档数目。之所以采用d f 作为特征选择，是基于如下基本假设： d f 值低于某个阂值的词条是低频词，它们不含或含有较少的类别信息，不应将 二阶段文本分类器及分类在推荐系统中的应用 其作为特征词来区分类别，将这样的词条从原始特征空间中除去，既可以降低特 征空间的维数，又能提高分类的精度。文档频率是最简单的特征抽取技术，由于 其相对于训练语料规模具有线性的计算复杂度，所以计算速度快，能够很容易被 用于大规模语料统计。相反，在信息检索研究中通常却认为d f 值低的词条相对 于d f 值高的词条具有较多的信息量，不应该将它们完全移除。不同的应用将对 d f 值的认识不同，应考虑具体情况来使用该方法。 ( 2 ) 信息增益方法( i g ) 信息增益( i n f o r m a t i o ng a i n ，简记为i g ) 在机器学习领域被广泛使用。对于词 条t 和文档类别c ，用i g 考察文档类别c 中出现和不出现词条t 的文档频数来衡 量词条t 对于文档类别c 的信息增益。我们采用如下的定义式： g a i n = 一i u l p ( c , ) 1 0 9 p ( c j ) + 户( ，) ：尸( q o g 尸( q 协尸( ) ：e ( c , i t ) 1 0 9 尸( q l - ) ( 2 5 ) 其中p ( q ) 表示c 类文档在语料中出现的概率，p ( t ) 表示语料中包含词条t 的 文档的概率，p ( qlf ) 表示文档包含词条t 时属于c 类的条件概率，尸( f ) 表示语料 中不包含词条t 的文档的概率，尸( qi ，) 表示文档不包含词条t 时属于c 的条件概 率，m 表示类别数。 ( 3 ) 互信息方法( m i ) 互信息( m u t u a li n f o r m a t i o n ，简记为m i ) 在统计语言模型中得到广泛应用，其 中m i 值越大表明共现程度越大。我们先假定用a 表示包含词条t 且属于类别c 的文档频数，b 为包含t 但是不属于c 的文档频数，c 表示属于c 但是不包含t 的的文档频数，n 表示语料中文档总数，则t 和c 的互信息可以由下式计算： m 一礼g 篇札g 酱叫昭 ( 4 ) x2 统计量( c h i ) 彳n ( 彳+ c ) ( 彳+ b ) ( 2 6 ) z 2 统计方法度量词条t 和文档类别c 之间的相关程度，并有一个基本假设t 和c 之间符合具有一阶自由度的z 2 分布。词条t 对于某类的z 2 统计值越高，表 明它与该类之间的相关性越大，携带的类别信息越多，越应该选择为特征词。令 1 2 2 中文文本分类技术概述 n ，a ，b ，c 的含义同上式2 - 6 中描述的相同，这里再假定d 是既不属于c 也不包含 t 的文档频数。若a d 三g 毒? c b o口 图2 1 一条具有较小分类间隔的决策线( 实线) ，分类间隔定义为两条平行虚线之间的距离 oo o o 己= o 图2 - 2 具有最大分类间隔的决策线，虚线上的数据点为支持向量 图2 1 和图2 2 中的实线显示了两个可能的决策平面，每个面都可以正确分 割两组数据。与实线平行的虚线表示决策平面平移后得到的平面，这种平移不会 造成数据的分割错误。平行线间的距离称为分类间隔。s v m 就是要在训练集中 找到具有最大分类间隔的决策平面。 可以通过在s v m 中引入软分类间隔或者将原来的数据空间映射到更高维空 间( 该空间中的新特征包含原空间中特征的交互作用，该新空间中线性可分) 的方 法将解决线性可分情况推广到解决线性不可分的情况。如果用内积k ( x ，薯) 代替 最优分类面中的点积，就相当于把原特征空间变换到了某一新的特征空间。采用 不同的内积函数将导致不同的支持向量机算法，目前得到研究的内积函数形式主 要有三类，它们都与己有的方法有对应关系：分别为多项式形式的内积函数、核 函数型内积、s 形函数( 双曲正切函数s i g t m o i d ) 内积。 支持向量机的优点在于： ( 1 ) 它是专门针对有限样本情况的分类方法，其目标是得到现有信息下的最 优解而不仅仅是样本数趋于无穷大时的最优值，该算法最终将转化成为一个二次 型最优问题，理论上得到的将是全局最优点，避免了局部极值问题。 ( 2 ) 该方法将实际问题通过非线性变换转换到高维的特征空间，在高维特征 二阶段文本分类器及分类在推荐系统中的应用 空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证具 有良好的推广能力，计算的复杂度不再取决于空间维数，而是取决于样本数，尤 其是样本中的支持向量数，这些特点就可能有效地用于解决高维问题。 ( 3 ) 该方法对稀疏数据不敏感，更好的捕捉了