（计算机应用技术专业论文）关联规则在文本分类中的研究.pdf

摘要 摘要 关联规则挖掘和文本分类都是数据挖掘领域的核心问题，两种方法都被广 泛应用于许多其它数据挖掘任务中，近年来越来越受到学术界的关注。本文对 关联规则在文本分类中的应用进行了深入的研究，在做此研究时，本文主要是 从提高文本分类效率的角度出发，来对改进关联文本分类算法。 本文重点学习研究了以下几个方面的问题：文本分类特征提取选择、文本 分类常用算法、关联规则挖掘a p f i o f i 算法、经典关联文本分类c b a 算法并提 出更有效的关联文本分类算法。目前关联文本分类c b a 算法c b a r g 步骤中主 要是使用了a p f i o f i 算法来发现频繁模式或关联规则，本文针对a p r i o f i 算法效率 不高的弱点，从不同角度对r u l eg e n e r a t o r 步骤进行了改进，给出两种改进算法。 主要的创新内容包括： 1 、利用完全图的特性改进关联文本分类算法 完全图的关联文本改进算法结合项集的特性构造矩阵，根据矩阵生成频繁 项集关联图，再进一步发掘了频繁项集关联图与完全子图的对应关系。该算法 的优点还在于它可以不用根据k 1 项集求出k 项集，它可以通过直接求出频繁 项集关联图的完全子图来求得k 项集。 2 、利用二进制粒计算的特性改进关联文本分类算法 提出了一种新的基于二进制g r a n u l e 计算的关联规则算法，该算法从信息粒 的角度出发，通过使用粒的“与运算 ，把a p f i o f i 算法中需要扫描数据库的链接 步，改成了适合计算机操作的二进制“与运算，从而简化了算法；通过做完“与 运算 以后直接统计信息粒中l 的个数是否大于最小支持度的支持计数，消除 了单独的剪枝过程，提高了算法的效率。再把二进制粒计算的关联规则算法应 用于c b a r g 过程中，替换了c b a 算法中的原有的a p f i o f i 算法，从而提高了 文本关联分类算法的效率。 这两种关联文本分类算法的效率均优于经典c b a 算法，两种算法之间也各 有优点，针对不同的文本数据库，效率各有不同。 关键词：关联规则；文本分类；a p f i o f i 算法；c b a 算法；g r a n u l e 计算；完全图 a b s t r a c t a b s t r a c t a s s o c i a t i o nr u l e sm i n i n ga n dt e x tc l a s s i f i c a t i o na r eb o t ht h ek e yp r o b l e m si nt h e d a t am i n i n gf i e l d ，w h i c ha r ew i d e l ya p p l i e dt od a t am i n i n gt a s ka n dw e r ef o c u s e do n b ya c a d e m i cw o r l di nr e c e n ty e a r s f o l l o w e db yaf u r t h e rs u r v e ya c c o r d i n gt ot h e a p p l i c a t i o n so fa s s o c i a t e dr u l e s i nt e x tc l a s s i f i c a t i o n ，t h ea r t i c l ei m p r o v e dt h e a s s o c i a t i o nt e x tc l a s s i f i c a t i o na l g o r i t h mi nt h el i g h to fu p g r a d i n gt h ee f f i c i e n c yo ft e x t c l a s s i f i c a t i o n t h ef o l l o w i n ga s p e c t sa r ew h a tt h ea r t i c l es t u d i e do n ：t e x tf e a t u r ee x t r a c t ，f e a t u r e s e l e c t ，g e n e r a la l g o r i t h m so nt e x tc l a s s i f i c a t i o n ，a p r i o r ia l g o r i t h mo na s s o c i a t i o nr u l e s m i n i n g ，c b aa l g o r i t h mo nt e x ta s s o c i a t i o nc a t e g o r i z a t i o na n dam o r ee f f e c t i v 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 mw a sp u tf o r w a r d ；a i m i n ga tt h ew e a kp o i n to fa p r i o r i a l g o r i t h m l o we f f i c i e n c y , t h es t e p so fr u l eg e n e r a t o rw a si m p r o v e df r o md i f f e r e n t p o i n to fv i e w , t w oi m p r o v e da l g o r i t h m sw e r eg i v e n t h em a i ni n n o v a t i v ep o i n t sa r e a sf o l l o w s ： 1 i m p r o v i n gt e x ta s s o c i a t i o nc l a s s i f i c a t i o na l g o r i t h mb yu s i n gt h ec h a r a c t e r i s t i c s o fc o m p l e t eg r a p h a c c o r d i n gt ot h ef r e q u e n ti t e m s e ta s s o c i a t e dd i a g r a mt h a tw a sg e n e r a t e db y m a t r i xw h i c hw a sg e n e r a t e db yt h ei m p r o v e da s s o c i a t e dt e x ta l g o r i t h mc o m b i n e d w i t ht h ec h a r a c t e r i s t i c so fi t e m s e t ，t h ec o r r e s p o n d i n gr e l a t i o n s h i pb e t w e e nf r e q u e n t i t e m s e ta s s o c i a t e dd i a g r a ma n d c o m p l e t es u b g r a p hw a sf u r t h e rd i s i n t e r e d t h em e r i t o ft h ea l g o r i t h mi st h a ti tn ol o n g e rn e e d sk 一1i t e m s e t sb u td i r e c t l yp r o d u c e st h e c o m p l e t es u b g r a p ho fa s s o c i a t e dd i a g r a mt og e tk i t e m s e t s 2 b i n a r yg r a n u l a rc o m p u t i n gw a su s e dt oi m p r o v et h e a s s o c i a t e dt e x t c l a s s i f i c a t i o na l g o r i t h m ak i n do fi m p r o v e da l g o r i t h mo fa s s o c i a t e dr u l e sb a s e do nb i n a r yg r a n u l a r c o m p u t i n gw a sp r o p o s e d ，t h ea l g o r i t h mw a sb a s e do nt h ei n f o r m a t i o ng r a n u l a r , t h e l i n k i n gs t e po fs c a n n i n gt h ed a t a b a s et h a tw a sn e e d e di na p r i o r ia l g o r i t h mw a s m o d i f i e dt ot h eb i n a r y “a n d ”o p e r a t i o n ，w h i c hr e d u c e dt h ec o m p l e x i t yo ft h e a l g o r i t h m ；w h e t h e rt h es t a t i s t i c a ln u m b e ro f “1 ”i nt h eg r a n u l a rw a sl a r g e rt h a nt h e i i 垒里兰坐曼! m i n i m a ls u p p o r td e g r e ew a s j u d g e da f t e rt h ea b o v eo p e r a t i o n ，w h i c he l i m i i l a t e dt l l e s m g l ep r u n i n gp r o c e s sa n dt h ee f f i c i e n c yo ft h ea l g o r i t h mw a su p g r a d e d a s s o c i a t e d r u l ea l g o r i t h mb a s e do nb i n a r yg r a n u l a rc o m p u t i n gw a s a p p l i e dt ot h ec b a r g p r o c e s s w h i c hr e p l a c e dt h eo r i g i n a l a p r i o r ia l g o r i t h mi nc b aa l g o r i t h m t h u s i m p r o v e dt h ee f f i c i e n c yo ft h et e x ta s s o c i a t e dc l a s s i f i c a t i o na j g o r i t l l 】m t h ee f f i c i e n c yo ft h o s et w oa s s o c i a t e dt e x tc l a s s i f i c a t i o na l g o r i t h m si s h i g h e r t h a nt h a to fc b a a l g o r i t h m ；t h e yh a v et h e i rs e p a r a t e dm e r i t sm a td i 腩r e n te m c i e n c v a i m i n gt od i f f e r e n tt e x td a t a b a s e s 1 哟啊o r 醇s ：a s s o c i a t i o nr u l e s ；t e x t c l a s s i f i c a t i o n ；a p r i o r ia l g o r i t h m ；c b aa l g 嘶t 1 1 1 1 1 ； g r a n u l ec o m p u t i n g ；c o m p l e t eg r a p h h i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得直昌太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 v 学位论文作者签名( 手写) ：轰q ：- 签字日期： p 。y 年忙月，日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权南昌大学可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。同时授 权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 、 学位论文作者签名( 手写) ：霆仁导师签名( 手写) ：又澎： 久 签字日期：洲年，z 月厂彳日签字日期：矽，g 年，1 月1 1 日 第1 章绪论 第1 章绪论 本章主要介绍关联文本分类研究的背景、意义和目的，并简单介绍本文的 组织与架构。本章1 1 节首先阐述了文本分类的研究背景；1 2 节介绍了当前国 内外关联文本分类的研究动态和水平；在1 3 节分析了本文的研究内容、研究意 义；并在1 4 节给出了论文的组织结构。 1 1 研究背景 随着信息技术的飞速发展和互联网的大规模普及，给我们带来便捷的同时， 也让我们面临了前所未有的挑战。一方面，互联网上的文本信息呈爆炸性增长， 这些文本资源中蕴含着许多有价值的信息；而另一方面因为技术手段的落后， 从大量文本资源中获取需要的信息十分困难。 在过去的数十年中，每天都会产生海量的数据而且这些数据正在以惊人的 速度增长。以下统计数字是对我们所处的海量信息时代的直观说明： 1 、搜索引擎：1 9 9 8 年g o o g l e 索引数量还只有2 6 0 0 万，2 0 0 0 年达到1 0 亿， 现在g o o g l e 只是每天新索引的网页就超过数百亿。截止2 0 0 7 年9 月g o o g l e 的 每天处理的数据量已超过了2 0 p b ，集群数量已经达到11 0 0 0 台，这些服务器的 配置大多采用两颗英特尔至强( h t ) 处理器和4 g b 内存，两个1 6 0 g b 的硬盘，并 采用以太网连接【1 1 。2 0 0 8 年7 月，g o o g l e 在官方博客中公布其索引的网页数量 已经突破1 万亿幅。 2 、期刊图书：全世界每年出版图书8 0 万种，期刊4 0 万种，其他文献信息 资料4 0 0 万种；发表科学论文大约5 0 0 万篇，平均每天1 4 0 0 0 篇左右，每3 5 秒 就有l 篇论文发表，不到1 分钟就有1 本新书问世，每小时出现近2 0 项技术发 明，每天约有4 0 亿个信息单位的信息量向全世界发送。德国学者哈根曾说，一 个科学家即使目前夜以继日地工作，也只能阅读有关他自己专业世界上全部出 版物的5 。 3 、w e b 数据：美国调研公司n e m e r t e s 公布的研究报告，互联网用户于2 0 0 7 年生成1 6 1 e b ( 1 e b 等于1 1 亿g b ) 的新数据，即使如此，仍有专家指出因特 网还尚未到达它的快速增长期。 第1 章绪论 面对网上的海量信息，传统的做法是对网上信息进行人工分类，并加以组 织和整理，为人们提供一种相对有效的信息获取手段。但是，这种传统的人工 分类的做法存在着许多弊端：一是耗费大量的人力，物力和精力；二是存在分 类结果一致性不高的问题。这就要求我们探索计算机文本分类的有效方法，使 得分类的正确率提高、分类速度加快。文本分类作为信息过滤、信息检索、搜 索引擎、文本数据库、数字化图书馆等领域等技术的基础研究，有着广泛的应 用前景【2 l 。 常用的文本分类方法包括：最邻近分类、决策树、神经网络、贝叶斯分类、 支持向量机、r o c c h i o 方法等。关联文本分类方法结合了可理解性强和准确率高 的优点，在文本分类领域也j 下引起越来越多研究者的关注。尽管如此，如何从 众多规则中选择恰当的子集形成分类器这个关联分类中的难点及重点问题仍未 得到很好的解决。 1 2 国内外研究动态和水平 关联文本分类的出现相对最邻近分类、决策树、神经网络、贝叶斯分类、 支持向量机等方法发展的较晚，但是其准确率高、可理解性强等优点已经成为 分类算法家族中的研究热点。以下将介绍关联分类方法的国内外研究状况。 关联文本分类方法来自于文本分类和关联规则挖掘的结合，将关联规则应 用于文本分类领域时，则产生了关联文本分类。以下将分别介绍基于关联规则 的文本分类的研究现状。 关联规则挖掘最早脱胎于超市购物篮分析，用于发现顾客放入购物篮中的 不同商品之间的联系。如：分析顾客的购买习惯同一次购买中，哪些商品经常 会被一起购买? 简单的说关联规则挖掘就是发现大量数据中项集之间有趣的关 联。在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集 合之间的频繁模式、关联、相关性或因果结构。 关联分析如今已经成为数据挖掘领域的基石之一，广泛应用于商务管理、 决策分析等领域，当今的数据库厂商如o r a c l e 、i b m 、m i c r o s o f t 等公司也纷纷 在其产品中集成了关联分析功能川。最为著名的关联挖掘算法是a p r i o r i l 2 1 算法和 f p g r o w t h 方法，a p r i o r i 算法利用a p r i o r i 性质即频繁项集的所有非空子集都必须 也是频繁的进行剪枝，f p g r o w t h 方法利用模式频繁树( f p 树) 存放压缩的频繁模 2 第1 章绪论 式信息以避免多次重复扫描数据库。b i n gl i u 等通过改造a p r i o r i 算法，将关联 规则和分类规则的挖掘结合起来，设计出基于关联的分类规则挖掘算法c b a 。 分类规则挖掘的目标是在训练数据集中寻找规则的子集以形成一个精确的分类 器【3 1 。 关联规则挖掘能够找出所有满足最小支持度的规则，在较低的支持度阈值 下，大量的规则形成了对底层数据较为完整的描述，在这些规则基础上所形成 的分类器理当具有更好的性能，因此考虑将关联挖掘和分类器构建结合起来。 c b a 算法首先通过关联挖掘找出项和类别之间的关联规则，这种后件被限定为 类别属性的规则被称为关联分类规则，然后从这部分规则的集合中找出一部分 子集形成分类器。分类器的产生过程是通过对产生的所有规则按照其准确率( 置 信度) 、频度( 支持度) 和生成的先后次序形成一个全序，然后从该全序中按照规 则在训练数据上的分类正确率进行筛选，选出规则的集合形成分类器。 c b a 算法开辟了一种新的途径来挖掘分类规则，由于是在所有的关联分类 规则中寻找适合分类器的规则，因此发现有趣的规则就变成了一个后处理的任 务，可以结合机器学习和其它领域的一些技术来确保有趣的规则能够被发现， 同时也确保发现的规则一定是有趣的 4 1 。 将关联分类应用到文本分类领域要面临以下两个问题：一是如何利用文档 本身的特性加快关联分类的速度和提高关联分类的性能，二是由于文档本身的 形式和结构多样，一般的文本包括标题，作者、正文等信息，新闻稿一般还有 新闻来源和时间，科技文档则包括关键词、分类号等内容，w e b 文档中还含有 超链接、t a g 标记等信息因此文档的预处理以及在文档的什么层面上挖掘分类规 则，怎样提高文本分类速度等都是值得研究的问题【5 】。 1 3 论文所做的工作及意义 本人在研究文本分类的基础上，将关联规则挖掘与文本分类中结合起来， 提出基于完全图的关联文本改进算法和基于二进制g r a n u l e 计算的关联文本改进 算法，主要研究的内容如下： 1 文本分类的研究 学习文本分类中常用的最邻近分类、决策树、神经网络、贝叶斯分类、支 持向量机等方法；深入学习关联规则挖掘算法一a p r i o r i 算法：研究各种分类 3 第1 章绪论 算法的特点和优缺点，为选择改进挖掘算法的不足提供理论深度的支持。 2 关联文本分类的研究 关联文本挖掘是文本挖掘领域重要的挖掘任务之一，其多数方法是从关联 规则挖掘借鉴而来。在关联规则挖掘过程中，为产生频繁项集需要用户指定最 小支持度阈值，往往利用传统的a p r i o r i 和f p g r o w t h 算法进行挖掘。对关联规 则算法在文本分类上的应用全过程进行深入的学习和研究，包括文本数据预处 理、关联文本分类c b a 算法及文本分类模型的评估等。 3 基于关联规则的文本分类的研究 对关联规则算法在文本分类上的应用进行深入的研究并改进。由于传统的 关联文本分类方法c b a ，利用a p r i o r i 算法计算得出，需要反复扫描数据库，导 致挖掘关联规则的效率较为低下。在本文中给出了两种改进的文本关联规则挖 掘算法：基于完全图的关联文本改进算法、基于二进制g r a n u l e 计算的关联文本 改进算法。这两种挖掘算法的效率均优于原算法。两算法之间也各有优点，针 对不同的文本数据库，效率各有不同。 本课题的研究有较强的理论意义，主要体现在以下两个方面： 1 针对现阶段关联规则挖掘算法的效率不理想的情况，本文对c b a 算法中的 c b a r g 步骤进行改进，使改进后的算法在时间复杂度和空问复杂度上都有 了很大的提高。 2 近年来用的较多的文本分类算法有支持向量机、k 一近邻、神经网络、朴素 贝叶斯等算法，本课题中主要研究了关联规则挖掘算法在文本分类中的应 用，并提出两种文本关联规则的改进算法。提出的算法比原有算法在生成关 联规则的步骤上，效率有了很大的提高。 1 4 论文的组织结构 本文共分为5 章，论文具体的结构安排如下： 第1 章绪论简要介绍本课题研究的背景及意义、国内外的研究动向及本课 题的主要研究内容和工作。 第2 章介绍目前文本挖掘、文本分类及关联规则的基本概念，包括文本挖 掘的定义、文本分类的介绍、文本的特征表示、文本分类常用算法及关联规则 挖掘a p r i o r i 算法。 4 第1 章绪论 第3 章详细介绍了关联规则在文本分类中的应用过程，基于关联规则的文 本分类c b a 方法。 第4 章给出了两种对c b a 的改进算法，基于完全图的关联文本改进算法和 基于二进制g r a n u l e 计算的关联文本改进算法，并在最后对原算法与两种改进挖 掘算法给出了算法复杂度的比较。 第5 章总结了研究期间的主要工作并作出结论，对未来研究工作进行展望 并提出了进一步的研究方向。 5 第2 章文本分类及关联规则简介 第2 章文本分类及关联规则简介 文本分类作为文本挖掘的一个重要主题，引起了人们的极大兴趣，同时它 也是一个富有争议的研究方向。本章2 。l 节概要介绍了文本挖掘的基本概念；2 2 节简要介绍了文本分类的概念、文本的特征表示及常用的文本分类算法，文本 分类算法中介绍了支持向量机s v m 、k n n 、朴素贝叶斯及关联文本分类算法； 2 3 节详细介绍了关联规则挖掘算法中的经典算法a p r i o r i 算法。 2 1 文本挖掘概述 2 1 1 文本挖掘定义 文本挖掘也称为文本数据挖掘h e a r s t 9 7 或文本知识发现f e l d m n a 9 5 ，其 主要目的是从非结构化的文本文档中提取有趣的、重要的模式和知识。可以看 成是基于数据库的数据挖掘或知识发现的扩展f a y y d a 9 6 ，s i m o u d i s 9 6 。文本挖 掘是从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘定义相类似。但 与传统的数据挖掘相比，文本挖掘有其独特之处，主要表现在：文档本身是半 结构化或非结构化的，无确定形式并且缺乏机器可理解的语义；而数据挖掘的 对象以数据库中的结构化数据为主，并利用关系表等存储结构来发现知识【6 j 。 文本挖掘是文本挖掘的一个分支，它涉及到数据挖掘、信息检索、自然语 言处理、机器学习等多个领域的内容，不同的研究者从各自的研究领域出发， 对文本挖掘的含义有不同的理解，不同应用目的文本挖掘项目也各有其侧重 点。因此，对文本挖掘的定义也有多种，其中被普遍认可的文本挖掘定义如下【7 j ： 文本挖掘是指从大量文本信息中发现隐含的模式p ，如果将文本信息看作输 入，p 看作输出，那么文本挖掘的过程实质上就是从输入到输出的一个映射： 文本信息专p 嗍。 直观的说，大量文本数据中抽取事先未知的、可理解的、最终可用的知识 的过程，同时运用这些知识更好地组织信息以便将来参考。当数据挖掘的对象 完全由文本这种数据类型组成时，这个过程就称为文本挖掘。 文本挖掘和通常的文本挖掘有类似之处，但是，文档中的标记给文档提供 了额外的信息，可以借此提高文本挖掘的性能。因此，有些数据挖掘技术并不 6 第2 章文本分类及关联规则简介 适用于文本挖掘。即使可用，也需要建立在对文本集预处理的基础之上。 2 1 2 文本挖掘过程 文本挖掘大体上可分为四个步骤【8 】： 1 信息检索：主要目标为检索与任务相关的文档集合。 2 信息抽取：从选择的文档集合中抽取信息，一种典型的方式是填充用户指定 的期望信息模扳。它的本质是形成数据库。 3 信息挖掘：采用标准数据挖掘技术从数据中发现模式。 在文本挖掘的过程中要建立文本特征向量，必须用结构化的数据来表示文 档集，但是目前所存在的文档表示方法中，存在一个难以解决的问题是文档向 量具有惊人的维数，所以特征集的缩减在文本挖掘的过程中是一个必不可少的 环节，文档向量维数缩减后，便可以利用机器学习的各种方法来提取面向各种 应用目的的知识模式。最后对获得的知识模式进行评价，若评价结果满足一定 的要求，则存储该模式。文本挖掘的具体处理过程可用下图表示【9 j 。 特征的 建立 知识 模式 图2 1 ：文本数据挖掘的一股过程 1 特征的建立：与数据库中的结构化数据相比它们缺乏像关系数据库中数据的 组织完整性，要将这些文档用一种类似关系数据库中较规范的记录且能反映 文档内容的形式表示出来，一般需要对文本进行预处理，抽取出代表其特征 的元数据，这些特征可以以结构化的形式保存，作为文档的中间表示形式。 2 特征集的缩减：当将文档转化为一种类似于关系数据库记录的比较规整并且 能反映文档内容的文档特征向量后，该文档特征向量的维数非常的大，所以 必须对特征集进行缩减。 3 学习与知识模式的提取：完成文档特征向量的维数的缩减后，便可利用机器 学习的各种方法来提取面向特定应用目的的知识模式。 4 模型质量的评价：对所获取的知识模型进行质量评价，若满足事先定的要求， 则保存该知识模式，否则返回以前的某个环节进行分析改进后进行新一轮的 挖掘工作【1 0 j 。 7 第2 章文本分类及关联规则简介 2 2 文本分类 2 2 1 文本分类简介 文本分类( t e x tc l a s s i f i c a t i o n ，或t e x tc a t e g o r i z a t i o n ) ，是指按照预先给定的 主题类别，为文档集合中的每个文档确定一个类别。这样用户不但能够方便地 浏览文档，还可以通过限制搜索引擎范围来使文档的查找更为容易。利用文本 分类技术可以快速、有效地对大量文档进行自动分类【1 1 】。 目前文本分类主要是通过机器学习技术来实现的，其形式化定义如下【1 2 】： 设d = d l ，d 2 , - , d l d t 是一个将要被分类的文档集，c = c i ，c 2 ，c l c l 是- 个预 先定义的类别集， = dxc 是一个布尔矩阵，其中的元素 为t r u e 表示 文档d i 属于类别e j ， 为f a l s e 表示文档d i 不属于类别c j 。文本分类的目的 就是训练出一个分类函数( 或称为分类器) ：d x c = t r u e ，f a l s e ，其中d d ，c c 。 根据实际中的应用情况，对文本分类任务可以施加不同的约束。如果每个 文档d 仅仅属于类别集c 中的一个类别，这样的文本分类问题称为单类别文本 分类( s i n g l e l a b e lt e x tc l a s s i f i c a t i o n ) ；如果每个文档可能属于类别集中的一个或 多个类别，这样的文本分类问题称为多类别文本分类( m u l t i l a b e lt e x t c l a s s i f i c a t i o n ) ；如果类别集中的类别可以构成一个层次关系，这样的文本分类问 题称为层次文本分类( h i e r a r c h i c a lt e x tc l a s s i f i c a t i o n ) e 1 3 】。 由于文本是一个由众多字符构成的字符串，属于一种非结构化的数据，无 法被训练算法直接用于训练或分类。要将自主训练技术运用于文本分类问题， 首先需要将作为训练和分类对象的文本，转化为自主训练算法易于处理的形式。 即运用各种文本表示方法，将所有文本都表示成具有某种相同结构的数据。其 中涉及的关键技术大致包括以下几节的几个方面。 2 2 2 文本的特征表示 与数据库中的结构化数据相比，文档具有有限的结构，或者根本就没有结 构。此外，文档的内容是人类所使用的自然语言，计算机很难处理其语义。文 本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上。我们需 要对文本进行预处理，抽取代表其特征的元数据。这些特征可以用结构化的形 式保存，作为文档的中间表示形式。对文本内容的特征表示主要有布尔模型、 8 第2 章文本分类及关联规则简介 向量空间模型、概率模型和基于知识的表示模型。因为布尔模型和向量空间模 型易于理解且计算复杂度较低，所以成为文本表示的主要工具【1 4 】。 表示文本特征主要有以下两种方式： ( 1 ) 特征抽取 特征抽取是依据某种原则构造从原始特征空间到低维空间的一个变换，从 而将原始特征空间所包含的分类信息转移到新的低维空间中来。在特征抽取方 面，主成分分析 j o l l i f f e 8 6 、线性区分分析 m a r t i n e z 0 1 、概念索弓l k a r y p i s 0 0 等 等众多方法都先后被提出或引入到文本领域。 中文文档中的词与词之间不像英文文档那样具有分隔符，因此中、英文文 档特征的抽取步骤略有不同。 ( 2 ) 特征选择 特征选择也称特征子集选择或特征集缩减。经过特征抽取获得的特征词数 量很多，有时达数万个特征。如此多的特征对许多文本挖掘方法，如文本分类、 聚类、文本关联分析来说未必都是有意义的；而过大的特征空间还会严重影响 文本挖掘的效率，因此选择适当的特征子集十分必要【l5 1 。 2 2 3 文本分类算法 文本分类的任务就是在给定的分类体系下，根据文本的内容自动地确定文 本关联的类别。从数学角度来看，文本分类是一个映射的过程，它将未标明类 别的文本映射到已有的类别中，该映射可以是一一映射，也可以是一对多的映 射，因为通常一篇文本可以同多个类别相关联。用数学公式表示如下： f ：a b 其中：a 为待分类的文本集合，b 为分类体系中的类别集合。 文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总 结出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据 总结出的判别规则，确定文本相关的类别【8 j 。 许多学者对文本分类的几种算法进行了实验比较，结果表明因使用的训练 和测试的语料库的不同，算法的查全率和查准率也会有差异。y i m i n gy a n g 和x i n l i u 6 1 曾对支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) ，k 一近邻( k n e a r e s t n e i g h b o r ，k n n ) ，神经网络( n e u r a ln e t w o r k ，n n e t ) ，线性最小平方拟合( l i n e a r l e a s t s q u a r ef i t ( l l s f ) 映射和朴素贝叶斯( n a i v eb a y e s ，n b ) 五种文本分类方法进 行的受限估计研究结果表明：s v m 、k n n 比n n e t 、n b 、l l s f 分类效果显 9 第2 章文本分类及关联规则简介 然要好。从分类效果和算法的时间复杂度上考虑，本文仅介绍s v m 、k n n 和朴 素贝叶斯算法。 2 2 3 1 支持向量机s v m 算法 s v m 方法不同于常规的统计和神经网络方法，它不是通过减少特征的个数 来控制模型的复杂性。s v m 提供了一个与问题维数无关的刻画函数复杂性的方 法，它引入高维特征空i 、日j ，将输入空间的非线性决策边界转化为高维特征空间 的线性决策边界，利用线性函数的对偶核，解决了数值优化的二次规划求解问 题。目前常用的核函数主要有三类：多项式核函数、径向基形式核函数、s 核函 数。根据不同的分类问题，可以选用不同的核函数【l7 1 。 s v m 基本思想可用下图说明，图中实心点和空心点分别代表两类样本，h 为分类超平面，h l 、h 2 分别为过各类中离超平面最近的样本且平行于超平面的 直线，它们之间的距离叫做分类间隔( m a r g i n ) 。 o 图2 2 最优分类超平面 最优分类超平面就是要求超平面不但能将两类正确分开( 即训练错误率为 o ) ，而且要使分类间隔最大。分类超平面的方程为【强】： w r x + b = 0 ( 2 1 ) 线性可分样本集为( x l ，y 1 ) ，( x 2 ，y 2 ) ，( x i ，y i ) ，x r n ，y e + l ，- 1 满足： y 。t w 。x f + b ) - l 0 ，i = l 2 ，n ( 2 2 ) 这样分类间隔就等于2 i l6 0 | i ，使间隔最大等价于使( w ) = 0 w 旷最小。要 求分类面对所有样本正确分类，即满足w7 x + b = 0 且使2 川6 0i i 最小的超平面 就是最优分类超平面。h l 、h 2 上的训练样本点就称作支持向量。 对于多类分类问题，解决的方式大概有下面两种： ( 1 ) 通过某种方式构造一系列的两类分类器并将它们组合在一起来实现多类分 l o 第2 章文本分类及关联规则简介 类；( 2 ) 将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化 问题“一次性 地实现多类分类。 第二种方法尽管看起来简洁，但是在最优化问题求解过程中的变量远远多 于第一种方法，训练速度不及第一种方法，而且在分类精度上也不占优。当训 练样本数量非常大时，这一问题更加突出。正因如此，第一种方法更为常用1 9 】【2 0 1 。 2 2 - 3 2k n n 算法 k n n 分类算法是一种传统的基于统计的模式识别方法，和s v m 都是基于 向量空间模型的，它在文本分类领域使用较多。其算法思想很简单，对于一篇 待分类文档x ，在训练集中找到k 个最相近的邻居，使用这k 个邻居的类别为 该文档的候选类别，该文档与k 个邻居之间的相似度为候选类别的权重，然后 使用设定的相似度闭值，就可以得到该文档的最终分类1 2 1 1 。k n n 算法的定义如 下公式所示： y b ，c _ ，) = es i mg ，d ，涉p i , c j ) 一b _ ， ( 2 3 ) d e k n n ， x 为待分类文档的特征向量表示，z 为训练集中的一篇文档的特征向量表 示；c ，为一类别；y 忆，c ，) 0 ，1 ) 表示d i 是否属于c ，当属于c f 时取1 ，反之 取o ；b ，为预先计算测定的c ，的阈值，首先要使用训练集和测试集来训练该闽值， 取得最佳f l 值的闭值即为最优的阈值；s i m ( x ，d ，) 为待分类文档与训练集中文档 之间的相似度。方便起见，两个文档的相似度我们采用两个向量的夹角余弦表 示： s i m ( x ，吐) = r t l w k ，i cw i k k = l ( 2 4 ) 其中：x 为新文本的特征向量，d i 为训练集中文本的向量，m 为特征向量的 维数，w k 为向量的第k 维。 2 2 3 3 朴素贝叶斯算法 朴素贝叶斯( n a i v eb a y e s ) 算法的基本思路是计算文本属于类别的概率，文本 属于类别的概率等于文本中每个词属于类别的概率的综合表达式。即文本中的 词汇在确定文本类别的作用上相互独立，它首先计算特征词属于每个类别的先 第2 章文本分类及关联规则简介 验概率，在新文本到达时，根据特征词的先验概率计算该文本属于每一个类别 的后验概率，最后取后验概率最大的类别作为分类结果。贝叶斯分类器由m a r o n 提出，将文章看作独立的单词集合，通过训练集由贝叶斯理论得到每个单词在 不同类的概率大小，构造出贝叶斯模型【2 引。 朴素贝叶斯分类法将训练实例分解成特征向量w 和决策类别变量c 。朴素 贝叶斯分类法假定特征向量的各分量间相对于决策变量是相对独立的，即各个 特征独立作用于类别，这就是特征独立性假设。对文本分类来说，它假设各个 单词w i 和w i 之间两两独立，其原理如下副2 3 1 。 图2 3 朴素贝叶斯分类器 贝叶斯算法的主要思想有一个各类统一的单词列表v = ( t l ，”，t 。) ，其长度( 即 不同特征个数) 为n 。朴素贝叶斯算法计算文本d i = ( d i l ，d i n ) 属于不同类别的后验 概率，将该文本分配到具有最大后验概率的类别中去。文档d i 属于类别c k 的后 验概率采用贝叶斯规则计算，公式如下： p ( c kld i ) = 掣 ( 2 5 ) 分类规则为： 其中i c l 表示类别总数，类别的先验概率p ( c k ) 采用最大似然估计( m a x i m u m l i k e l i h o o de s t i m a t e ，简称m l e ) 进行求取，求取过程公式如下所示： d = d t ，d 1 0 1 ) 为已标记文档的集合( 训练集) ，i d i 表示其中所含文档的数 目。当文档d 属于类别c k 时，p ( c k l d i ) = l ，否则p ( c k l d i ) = o 。 c l a s s ( z ) = a r g l m ；蚓a x d p ( q z ) ) = a r g l m 敛a x 球l 尸( q ) p ( z q ) ) 1 2 第2 章文本分类及关联规则简介 p ( c k4 ) 尸( q ) = 生面一 p ( c 七i 吐) = 兀p ( t jic k ) 咖 ( 2 6 ) 其中：d u 表示文档d i 中特征t j 的词频或权值( 进行特征处理后) 。p ( t j l c k ) 的计 算根据采用的模型和平滑算法不同而各异【2 4 1 。 2 2 3 4 关联文本分类算法 关联规则挖掘是指从海量的数据中挖掘出有意义的、有用的关联关系，这 些关联关系用于反映一个事物与其他事物之间存在的相互依赖性及关联性，为 决策者提供有用的决策信息。a p f i o f i 算法是一种最有影响的挖掘关联规则频繁 项集的算法，已经为大部分商业产品所使用。尽管如此，a p f i o f i 算法还是存在 很大的优化空间，如何能够更有效的提高关联规则算法执行效率，怎样设计更 有效、更实用的算法，成为我们要考虑的问题。众多学者针对a p f i o f i 算法的不 足，提出了许多较好的改进方案，如：f p g r o w t h 算法【2 5 1 、d h p 算法【2 6 1 、频繁 闭项集法【2 7 】等等。 文本数据被转化成结构化形式后，就成为文本挖掘过程的基础，文本关联 规则挖掘与关系数据库中关联规则的挖掘方法类似，在下一节将对该算法进行 详细的介绍。 2 3 关联规则挖掘算法 文本关联分类本质上属于一种基于规则的文本分类方法，关联规则挖掘算 法是构成关联文本分类的基础。关联分类规则有两种不同的形成方式，部分研 究者在所有类别的训练集中挖掘规则，部分研究者则将不同类别的训练集分开 挖掘规则，这两种方式各有利弊和适用范围。本节将介绍关联规则挖掘算法及 其部分相关概念。 2 3 1a p r i o r i 算法 关联规则即根据一个事务中某些项的状态可推导出另一些项在同一事务中 的状态。其有关定义为：i = i l ，i 2 ，i m ) 是所有项目的集合，t t l ，t 2 ，t n 事务 是i 的子集，d 是所有事务的集合，每个事务可以用唯一的标识符t i d 来表示。 关联规则表示为a _ b 的形式，其中a c i ，b c i ，a n b = 由。支持度s u p p o r t 包含 1 3 第2 章文本分类及关联规则简介 au b 事务量与d 的总事务比例，即s u p p o r t ( a = b ) = p ( a ub ) 。置信度c o n f i d e n c e 为d 中包含a 的事务同时也包含b 的百分比，即c o n f i d e n c e ( a b ) = p ( b l a ) = s u p p o r t ( a t _ jb ) s u p p o r t ( a ) t 2 s l 。 a p f i o f i 算法为了生成所