（计算机系统结构专业论文）基于关联规则的中文文本自动分类算法研究.pdf

重庆大学硕士学位论文中文摘要 摘要 面对浩如烟海的电子信息，如何帮助人们有效地收集和选择感兴趣的信息，如 何帮助用户在日益增多的信息中发现潜在有用的知识已成为信息技术领域的热点 问题。数据挖掘就是为解决这一问题而产生的研究领域。自9 0 年代产生以来，对 数据挖掘的研究已经比较深入，研究范围涉及到关联分析、分类分析、聚类分析、 趋势分析等多个方面。由于现实生活中绝大部分信息资源是以非结构化数据的形 式存在，而数据挖掘则普遍以结构化数据如关系数据库中的数据为对象，因此如 何对非结构化数据进行挖掘成为了一个重要的研究课题。 在常见的非结构化数据如文本、图象、视频中，文本数据是应用最为广泛的 一种形式，常用于数字图书馆、产品目录、新闻组、医学报告、组织及个人主页。 在自然语言理解、文本自动摘要、信息提取、信息过滤、信息检索等领域，文本 挖掘技术都有着广泛的应用，因而在数据挖掘领域具有较高的商业价值。 本文以文本数据为研究对象，对文本关联分类进行研究，主要包括文本特征 提取、选择、表示和文本关联分析、文本关联分类，并提出更有效的文本关联分 类算法。本文的研究工作和创新内容包括以下几个方面： 特征选择、向量空间表示方法研究 目前文本分类中常用的文档表示方法主要有布尔矩阵、词频矩阵等表示形式。 采用布尔矩阵表示文档向量，优点在于表示方式简洁且计算效率比较高，缺点在 于只是考虑特征在文档中出现与否会使得表示不够精确；而使用词频向量表示虽 然表达比较精确，但简洁性相对较低，生成向量空间需要更多的计算。本文提出 特征权重阂值的方法来更加准确的表示文本向量空间，从而改善文本分类质量。 文本关联分析的研究 文本关联分析中，由于文本集具有高维稀疏的特性，采用a p r i o r i 等传统的关联 挖掘算法效率比较低，而采用f p g r o w t h 等算法又会使得其挖掘f p - t r e e 时递归的次 数比较多，另外，传统的关联挖掘需要自己指定最小支持度阈值，这在文本关联挖 掘中需要反复摸索实验，不好确定。针对以上不足，本文提出根据文本训练集规模 动态调整与c o f i t r e e 压缩结构相结合的d l - c o f i 算法，该算法可以先根据训练文 档规模动态确定l 的值，再利用c o f i 算法进行挖掘，动态确定全局最频繁的l 个 规则。 综合置信度与支持度对未知文档分类 传统的c b a 、a r c 等分类算法对修剪策略与分类预测均考虑得不够全面，在 修剪策略方面，很多方法均不能取得满意的效果，本文结合了两种常用修剪策略 重庆大学硕士学位论文 中文摘要 的优点，提出超规则- j m e a 咖算法；在对测试文档分类方面，c b a 只考虑覆盖 样本的第一条规则，a r c 只考虑计算覆盖文档某个类的置信度之和，虽然有综合 考虑置信度与支持度的研究，但却忽略了二者之间的权重关系。本文权衡置信度 与支持度之间的比例关系，提出了两个影响因子进行综合计算类区分度的c d d 算法。 最后，利用提出的关联分类算法与原有的传统关联分类算法相比，能够得到 较好的查全率、查准率、f 1 值，达到了提高分类质量与分类效率的目的。 关键词：文本挖掘，特征向量表示，文本关联分类，关联分析 n 重庆大学硕士学位论文英文摘要 a b s t r a c t w i mt h er a p i dd e v e l o p m e n ta n ds p r e a do fi n t e r n e t t h es i z eo fe l e c t r o n i c i n f o r m a t i o ni si n c r e a s i n g l ye n l a r g e d i nt h ea r e ao fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y , i ti sac o m p r e h e n s i v ei s s u et ol o o kf o rl a t e n ta sw e l la si n t e r e s t e di n f o r m a t i o na n d k n o w l e d g eq u i c k l y , a c c u r a t e l ya n dc o m p l e t e l y d a t am i n i n g ( d m ) t e c h n o l o g yi saw a y t os o l v et h ep r o b l e m t h er e s e a r c h e so nd m ，w h i c hi n v o l v ea s s o c i a t i o na n a l y s i s ， c a t e g o r i z a t i o na n a l y s i s ，c l u s t e ra n a l y s i s ，t r e n da n a l y s i s ，e t c ，h a v eb e e nc o n d u c t e d d e e p l ys i n c et h ec o n c e p to fd mw a sp r o p o s e di n1 9 9 0 s s t r u c t u r e dd a t as u c ha s r e l a t i o n a ld a t a b a s ei st h em a i nr e s e a r c ho b j e c to fd m ，h o w e v e r , am a j o r i t yo f i n f o r m a t i o ne x i s t sw i t ht h ef o r mo fu n s t r u c t u r e dd a t ap r a c t i c a l l y s o ，m i n i n gt h e u n s t r u c t u r e di n f o r m a t i o ns u c c e s s f u l l yi sb e c o m i n gan e w c h a l l e n g e t e x td a t a , w h i c hi sak i n do fi n f o r m a t i o nf o r mu s e dm o s ta m o n gc o m m o n u n s t r u c t u r e dd a t as u c ha st e x t ，i m a g ea n dv i d e o ，e t c ，i so f t e nu s e di nd i g i t a ll i b r a r y , p r o d u c tc a t a l o g , n e w sg r o u p ，m e d i c i n er e p o r t ，o r g a n i z a t i o no ri n d i v i d u a lh o m e p a g e s ， a n di sa l s oa p p l i e db r o a d l yt on a t u r a ll a n g u a g eu n d e r s t a n d ，t e x ts u m m a r i z e , i n f o r m a t i o n e x t r a c t ，i n f o r m a t i o nf i l t e r , i n f o r m a t i o nr e t r i e v a l ，e t c t h e r e f o r ei to w n se n o r m o u s c o m m e r c i a lv a l u e t l l i sp a p e rd e a l sw i t l lc h i n e s et 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 n , w h i c hc o n s i d e r st e x t d a t aa sar e s e a r c ho b j e c t i tm a i n l yc o n c e r n so nt e x tf e a t u r ee x t r a c t i o n ，f e a t u r es e l e c t i o n , f e a t u r ev e c t o rs p a c ed e n o t a t i o na n da n a l y s i so ft e x ta s s o c i a t i o n , t e x ta s s o c i a t i o n c a t e g o r i z a t i o n t h ea u t h o rp r o p o s e sam o r ee f f i c i e n ta l g o r i t h m t h ep r i m a r yw o r k i n c l u d e s ： 耵l er e s e a r c ho nf e a t u r es e l e c t i o na n dv e c t o rs p a c ed e n o t a t i o n c u r r e n t l y , c o m n l o nm e t h o d so ft e x td e n o t a t i o ni n v o l v eb o o l e a nm a t r i x ，t e r m f r e q u e n c ym a t r i xe t e w 1 1 i l ed e n o t i n gt e x tv e c t o r sw i mab o o l e a nm a t r i x t h em a i n a d v a n t a g e sa r et h ec o n c i s ed e n o t a t i o na n dh i g he f f i c i e n c yi nc o m p u t i n g , y e tt h ew e a k p o i n t i st h a tw e j u s tc o n s i d e rt h ea p p e a r a n c eo f f e a t u r e s ，s oi tw i l ll e a dt ot h ei n a c c u r a c y h o w e v e r , b yu s i n go f t e r mf r e q u e n c ym a t r i x ，t h o u g hi t sd e m o n s t r a t i o ni sm o r ea c c u r a t e ， i t ss i m p l i c i t yi sd e g r a d e d ，a n dm o r ec o m p u t a t i o ni sn e e d e di nf o r m i n gv e c t o rs p a c e t l l i sp a p e ra d d r e s s e sam o r ea c c u r a t ea p p r o a c ho ff e a t u r ew e i g h tt h r e s h o l dt of o r mt h e t e x tv e c t o rs p a c e ，w h i c hw i l li m p r o v et h eq u a l i t yo f c h i n e s et e x tc a t e g o r i z a t i o n 1 1 1 er e s e a r c ho f t e x ta s s o c i a t i o nm i n i n g i i i 重庆大学硕士学位论文 英文摘要 d u r i n gt h et e x ta s s o c i a t i o nm i n i n g , d o c u m e n t sa l w a y so w nt h ep r o p e r t yo fh i g h s p a r s i t y , i tw i l lb el o we f f i c i e n c yw h e na d o p t i n gs o m et r a d i t i o n a la s s o c i a t i o nm i n i n g a l g o r i t h ms u c ha sa p r i o r i a n dw i l lb er e c u r s i v ef r e q u e n t l yw h e na d o p t i n gf p 。g r o w t h ， o t h e r w i s e , y o us h o u l da s s i g n m i n i m a ls u p p o r tt h r e s h o l dy o u r s e l fi nt r a d i t i o n a l a s s o c i a t i o nm i n i n g , i tn e e d sf r e q u e n t a t i v ee x p e r i m e n t st og e ti ti nt e x ta s s o c i a t i o n m i n i n g , s oi ti sh a r dt od e t e r m i n e a i ma tt h e s ew e a k n e s s ，t h i sp a p e rp r o p o s ea l g o r i t h m d l c o f lw h i c hc o m b i n e db yc o m p r e s s i v es t r u c t u r ec o f i t r e ea n dd y n a m i ca d j u s t a c c o r d i n gt ot h es c a l eo ft r a i n i n gt e x t s ，t h i sa l g o r i t h mc a nd y n a m i cd e t e r m i n ev a l u el a c c o r d i n g t o t h es c a l e o f t r a i n i n g t e x t s ，a n d u t i l i z e c o f i a l g o r i t h m t o m i n e t h ei m p r o v e m e n to f s t r a t e g yo nr u l e sp r l m l ea n dc l a s s i f i c a t i o n i ti sn o te n o u g hi np r u n es t r a t e g ya n dc a t e g o r i z a t i o np r e d i c t i o na st r a d i t i o n a l a l g o r i t h mc b a , a r c e t e i nt h ea s p e c to fp r u n es t r a t e g y , i tc a n tg e tc o n t e n tc o n c l u s i o n i nm a n ya l g o r i t h m s t h i sp a p e rc o m b i n e st h ea d v a n t a g eo f t w oc o m m o np r u n es t r a t e g y , p r o p o s et h ea l g o r i t h m o f s u p e r - r o l e - j - m e a s u r e ；i n a n o t h e ra s p e c ta sp r e d i c t i o n c a t e g o f i z a d o n c b ao n i yc o n s i d e rt h em o s ts u i t a b l eo n er o l e , a r co n l yc o n s i d e rt h e s u mo fr o l e sc o n f i d e n c ew h i c hc o v e rs o m ec l a s sd o c u m e n t s ，i nt h ep a p e r , i td o e s n t c o n s i d e rt h ei n f l u e n c eo fc o n f i d e n c ea n ds u p p o r t s ow ep r o p o s eac d da l g o r i t h m ， w h i c ht a k e st w oi n f l u e n c ef a c t o r si n t oc o n s i d e r a t i o n f i n a l l y , c o m p a r e dw i t h t r a d i t i o n a la l g o r i t h m s ，t h ep r o p o s e da l g o r i t h mr e a c h e s b e t t e rp r e c i s e , r e c a l la n df ls t a n d a r d ，w h i c hi m p r o v e sq u a l i t ya n de f f i c i e n c yo f c a t e g o r i z a t i o n k e y w o r d s ：t e x tm i n i n g ，f e a t u r ev e c t o r , t e x t a s s o c i a t i o nc l a s s i f i c a t i o n , a s s o c i a t i o n a n a l y s i s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：乃7 7签字日期：沙7 年月铲日 l 学位论文版权使用授权书 本学位论文作者完全了解重废塞堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重医太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：移驴7 签字醐5 叩引肿日 导师签名：张玉芳 签字日期：扣7 年6 月牛日 重庆大学硕士学位论文l 绪论 1 绪论 随着互联网的大规模普及和企业信息化程度的提高，文本信息的快速积累使 公司、政府和科研机构在信息处理和使用中面临前所未有的挑战。一方面，互联 网和企业信息系统每天都不断产生大量文本数据，这些文本资源中蕴含着许多有 价值的信息；而另一方面因为技术手段的落后，从大量数据资源中获取需要的信 息十分困难，人们迫切需要研究出方便有效的工具去从大规模文本信息资源中提 取符合需要的简洁、精炼、可理解的知识，文本挖掘就是为解决这个问题产生的 研究方向。 文本分类隶属于文本挖掘领域，本章首先阐述文本挖掘的研究背景，包括文 本挖掘的基本概念、研究现状与已有的成果；然后，介绍本文的研究内容以及组 织结构。 1 1 研究背景 自然语言是人们在社会经济生活中主要的交流和表达思想的工具，虽然对自 然语言的研究已有较长的时间，但对理解和使用自然语言这种能力的解释仍然有 限。传统的自然语言理解是对文本进行较低层次的理解，主要进行基于词、语法 和语义信息的分析，并通过词在句子中出现的次序发现有意义的信息。在这一层 次遇到的问题多与句法和语义歧义性相关。 另一方面，对文本较高层次的理解主要集中在研究如何从各种形式的文本和 文本集中抽取隐含的模式和知识。文本高层次理解的对象可以是仅包含简单句子 的单个文本也可以是多个文本组成的文本集，但是现有的技术手段虽然基本上解 决了单个句子的分析问题，但是还很难覆盖所有的语言现象，特别是对整个段落 或篇章的理解还无从下手。 恰巧在这个时期，在1 9 世纪早期发展起来的以统计技术为基础的数据挖掘技 术已经发展得较为成熟，并在大规模结构化关系数据库上应用取得成功。人们自 然想到将数据挖掘的成果用于分析以自然语言描述的文本，这种方法被称为文本 挖掘( t e x tm i n i n g , t m ) 或文本知识发现( k n o w l e d g ed i s c o v e r yi nt e x t k d t ) 。 与传统自然语言处理( n a t u r a ll a n g u a g ep r o c e s s i n g , n l p ) 关注词语和句子的理解 不同，文本挖掘的主要目标是在大规模文本集中发现隐藏的有意义的知识，即对 文本集的理解和文本间关系的理解。因此，文本挖掘是自然语言处理和数据挖掘 技术发展到一定阶段的产物。 重庆大学硕士学位论文1 绪论 1 1 1 文本挖掘的定义 定义1 1 文本挖掘是指从大量文本数据中抽取事先未知的、可理解的、最终 可用的知识的过程，同时运用这些知识更好地组织信息以便将来参考。 直观地说，当数据挖掘的对象完全由文本这种数据类型组成时，这个过程就 称为文本挖掘。而文本分类是文本挖掘中的一个分支。 文本挖掘也称为文本数据挖掘1 1 或文本知识发现【2 1 ，文本数据挖掘的主要目的 是从非结构化文本文档中提取有趣的、重要的模式和知识。可以看成是基于数据 库的数据挖掘或知识发现的扩展【3 】。 1 1 2 文本挖掘的过程 文本知识发现主要由以下步骤组成，如图i 1 ： 黟 文档集合 评估与表示 国已 文档中间形式模式 知识 图1 1 文本知识发现图 f i g1 1s t e p so f t h et e x tk n o w l e d g ed i s c o v e r y 文本预处理 选取任务相关的文本并将其转化为文本挖掘工具可以处理的中间形式。 通常包括两个主要步骤( 图1 2 ) 1 ) 特征抽取：建立文档集的特征表示，将文本转化成一种类似关系数据且能表现 文本内容的结构化形式。 2 1 特征选择：一般说来结构化文本的特征空间维数较高，需要对其进行缩减，只 保留对表达文本内容作用较大的一些特征。 图1 2 文本预处理的一般过程 f i g1 2t h ep r o c e s so f t e x tp r e p r o c e s s 2 重庆大学硕士学位论文i 绪论 文本挖掘文本分类： 在完成文本预处理后，可以利用机器学习、数据挖掘以及模式识别等方法提 取面向特定应用目标的知识或模式。 模式评估与表示： 最后一个环节是利用已经定义好的评估指标对获取的知识或模式进行评价。 如果评价结果符合要求，就存储该模式以备用户使用；否则返回到前面的某个环 节重新调整和改进，然后再进行新一轮的发现。 1 2 文本挖掘现状 在文本挖掘过程中，文本的特征表示是整个挖掘过程的基础；而关联分析、 文本分类是两种最主要也是最基本的功能。下面，以文本特征表示和文本挖掘的 核心功能为线索，对文本挖掘的研究现状和已经取得的成果作简要介绍。 1 2 1 文本特征表示 传统数据挖掘所处理的数据是结构化的，其特征通常不超过几百个；而非结 构化或半结构化的文本数据转换成特征向量后，特征数可能高达几万甚至几十万。 所以，文本挖掘面临的首要问题是如何在计算机中合理的表示文本。这种表示法 既要包含足够的信息以反映文本的特征，又不至于太过庞大使学习算法无法处理。 这就涉及到文本特征的抽取和选择。 文本特征指的是关于文本的元数据，可以分为描述性特征，如文本的名称、 日期、大小、类型以及语义性特征，如文本的作者、标题、机构、内容。描述性 特征易于获得，而语义特征较难获得。在文本特征表示方面，内容特征是被研究 得最多的问题。 定义1 2 当文本内容被简单地看成由它所包含的基本语言单位( 字、词、词组 或短语等) 组成的集合时，这些基本的语言单位被称为项( t e r m ) 。 对文本内容的特征表示主要有布尔模型、向量空间模型、概率模型和基于知 识的表示模型。因为布尔模型和向量空间模型易于理解且计算复杂度较低，所以 成为文本表示的主要工具。 特征提取 中文文档中的词与词之间不像英文文档中那样具有分隔符，因此中、英文文 档内容特征的提取步骤略有不同。 3 重庆大学硕士学位论文1 绪论 英文文档集 中文文档集 消除停用词 词语切分 图1 3 文本特征提取的一般过程 f i g1 3g e n e r a lp r o c e s so f t e x tf e a t u r ee x t r a c t i o n 消除停用词： 文本集有时包含一些没有意义但使用频率极高的词。解决这个问题的方法是 用这些词构造一个停词表或禁用词表( s t o pw o r dl i s t ) 4 j ，在特征抽取过程中删去停 词表中出现的特征词。 词干抽取； 词干抽取( s t e m m i n g ) 有四种不同的策略：词缀排除( a f f i xr e m o v a l ) 、词干表查 询( t a b l el o o k u p ) 、后继变化( s u c c e s s o rv a r i e t y ) 和胛一g r a m 。 词干抽取将具有不同词缀的词合并成一个词，降低文本挖掘系统中特征词的 总数，从而提高了挖掘系统的性能。 当然，也有两点需要注意： a 词干抽取对文本挖掘性能的提高仅在基于统计原理的各种分析和挖掘技术 下有效。在进行涉及语义和语法的自然语言处理时，不适宜采用词干抽取技术。 b 词干抽取对文本挖掘或信息检索准确性的影响至今没有令人信服的结论， 因此许多搜索引擎和文本挖掘系统不使用任何词干抽取算法。 汉语切分： 汉语的分词问题已经基本解决，并出现了多种分词方法。这些分词方法可以 分为两类：一类是理解式分词法，即利用汉语的语法知识、语义知识及心理学知 识进行分词；另一类是机械式分词法，一般以分词词典为依据，通过文本中的汉 字串和词表中的词逐一匹配完成词语切分。本文分词实验是采用中科院提供的开 源i c t c l a s 2 1 】的j a v a 版本i c t c l a s d l l 。 特征选择 国外对特征选择的研究较多，特别是已有专门针对文本分类特征选择方法的 比较研究【5 1 。国内对这一问题的研究以跟踪研究为主，集中在将国外现有的特征评 4 重庆大学硕士学位论文1 绪论 估函数用于中文文本特征选科6 1 及对其进行改进【刀。在第三章中将进一步讨论特征 选择的问题。 1 2 2 基于关键字的关联分析 与关系数据库中关联规则的挖掘方法类似，基于关键词的关联规则产生过程 包括两个阶段： 关联挖掘阶段： 这一阶段产生所有的支持度大于等于最小支持度阈值的关键词集，即频繁项 集。 规则生成阶段： 利用前一阶段产生的频繁项集构造满足最小置信度约束的关联规则。 根据不同的挖掘需要，可以利用不同的挖掘方法，如关联挖掘、最大模式挖 掘或层次关联挖掘，完成相应的文本分析任务。 1 2 3 文本分类 文本分类是文本挖掘中一项非常重要的任务，也是国内外研究较多的一种挖 掘技术。在机器学习中分类称作有监督学习或有教师归纳，其目的是提出一个分 类函数或分类模型( 也称作分类器) ，该模型能把数据库中的数据项映射到给定类 别中的一个。 一般来讲，文本分类需要四个步骤： 获取训练文本集：训练文本集由一组经过预处理的文本特征向量组成，每 个训练文本( 或称训练样本) 有一个类别标号； 选择分类方法并训练分类模型：文本分类方法有统计方法、机器学习方法、 神经网络方法等等。在对待分类样本进行分类前，要根据所选择的分类方法，利 用训练集进行训练并得出分类模型； 用导出的分类模型对其它待分类文本进行分类； 根据分类结果评估分类模型。 另外需要注意的是，文本分类的效果一般和数据集本身的特点有关。目前， 普遍认为不存在某种方法能适合于各种特点的数据8 l 【9 】。 随着i n t e r n e t 技术的发展和普及，在线文本信息迅速增加，文本分类成为处理 和组织大量文本数据的关键技术。而近二十多年来计算机软、硬件技术的发展和 自然语言处理、人工智能等领域的研究进展为文本自动分类提供了技术条件和理 论基础。迄今为止，文本分类研究已经取得了很大的进展，提出了一系列有效的 方法，其中分类质量较好的有k 最近邻( k - n e a r e s tn e i g h b k n n ) p 】、支持向量机 ( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 0 1 、朴素贝叶斯( n a v eb a y e s ，n b ) 1 1 】【1 2 】。1 9 9 8 年文 献【1 3 1 提出了基于关联规则的分类方法c b a ，此后陆续有人进行这方面的研究，如 5 重庆大学硕士学位论文1 绪论 c a e p 1 4 1 、j e p 1 蜘、d e e p s 1 6 1 、c m a r 1 7 】和用于文本分类的a r c t l 8 1 。 国内对中文文本自动分类的研究起步较晚，尽管已有一些研究成果，但由于 尚没有通用的标准语料和评价方法，很难对这些成果进行比较。而对基于关联规 则的中文文本分类的研究在国内才刚刚开始。进展非常有刚1 9 】。本文的四、五章 将对中文文本关联分类进行系统的研究，并提出对现有文本关联分类方法的改进。 1 - 3 本文工作 1 3 1 研究目标与研究内容 本文的主要研究目标是针对中文文本关联分类，提出更有效的模型与算法， 具体包括特征选择与向量表示、文本关联分析、文本关联分类。 针对以上研究目标，本文的具体研究内容如下： 特征选择、向量表示方法研究 目前文本分类中常用的，基于评估函数的特征选择方法难以避免地使特征选择 的结果受到噪声信息的干扰，同一特征选择函数针对不同文档集所得到的效果也 不同。本文将针对特征表示中，如何有效地过滤噪声信息这一问题进行研究，提 出特征权重阈值的方法来更加准确的表示文本特征向量空间，从而改善文本分类 质量。 文本关联分析的研究 文本关联分析是文本挖掘领域重要的挖掘任务之一，其多数方法是从关联规则 挖掘借鉴而来。在关联规则挖掘过程中，为产生频繁项集需要用户指定最小支持 度阈值；而在高维稀疏的文本数据库中，往往利用传统的a p d o n 和f p g r o w t h 算 法进行挖掘，由于最小支持度需要反复进行摸索实验才能得到，不容易确定；所 以本文不使用最小支持度，而是提出一种动态挖掘规则数目的( d y n a m i c - l i m i t e d ) 方法，并将该方法与c o f i - t r e e 压缩3 9 1 的结构相结合，提出d l - c o f i 算法。 规则裁剪、综合置信度与支持度对未知文档分类 本文对传统关联分类算法的修剪策略与分类预测进行分析。在修剪策略方面， 本文结合了超规则与j - m e a s u r e 算法的优点，提出了超规则j m e a s u r e 算法，改进 了传统规则修剪策略的效率与质量。在对测试文档分类方面，针对传统c b a 、a r c 的缺点，提出了综合考虑置信度与支持度，并设置其影响因子进行综合计算类别 区分度的算法。 1 3 2 本文结构 文本共分为六章，第一章为绪论，第二章介绍目前主要的文本分类算法与常 用的评估方法，第六章为结论与展望，第三章到第五章为本文主要研究内容。 第二章文本分类 6 重庆大学硕士学位论文 1 绪论 本章主要介绍文本分类的问题定义、几种主要的文本分类方法和文本分类模 型的评估方法。 第三章文本预处理 首先阐述文本预处理过程中可能遇到的主要概念和方法，给出几个具体的文 本特征抽取和文本特征选择方法，然后提出基于最小权重阂值的向量空问表示方 法，最后在基于j a v a 的e c l i p s e 平台上完成实验，利用中科院的i c t c l a s 分词 ( i c t c l a s d 1 1 ) 组件和l u e e n e 2 2 1 的倒排索引来完成。文档集是c n l p ( h t t p ：w w w n l p o r g c n ) 提供的人民日报标准语料库。 第四章文本关联分析 首先阐述基本的关联规则挖掘问题，描述解决这个问题的主要技术。由于关 联规则挖掘的核心问题还是频繁项集挖掘，因此集中讨论几种主要的频繁项集挖 掘方法并对其分类。然后，提出改进的限制频繁项集挖掘算法d l - c o f i 。并在同 样的e c l i p s e 平台下使用w e k a 【2 3 1 进行关联挖掘实验。 第五章文本关联分类 给出文本关联分类的一般模型，讨论目前主要的关联分类算法，阐述当前关 联分类问题的研究重点并集中讨论了关联分类的规则修剪策略和分类预测策略， 然后提出规则修剪的超规则一j m e a s u r e 修剪算法，综合考虑置信度与支持度的c d d ( c l a s sd i f f e r e n t i a t ed e 蓼e e ) 类别区分度改进算法。最后将本算法和c b a 以及a r c 算法等进行比较实验。 第六章结论及展望 总结全文的研究工作，并对今后进一步研究工作做出展望。 7 重庆大学硕士学位论文2 文本分类及其评估方法 2 文本分类及其评估方法 文本分类是指把一个或多个预先指定的类别标号自动分配给未分类文本的过 程。文本分类的研究可以追溯到6 0 年代早期，但直到9 0 年代早期才成为信息处 理、数据挖掘和机器学习领域的主要研究问题，这主要归功于日益增长的应用需 求以及硬件能力。本章主要介绍文本分类的问题定义、几种主要的文本分类方法 和文本分类模型的评估方法。 2 1 引言 文本分类是文本挖掘领域中一个极为重要的问题，特别是在半结构化的w e b 文本信息极为丰富的情况下，以文本分类为基础的各种应用，如个人信息代理、 搜索引擎、网上信息发布等，己成为有效控制和利用海量信息的重要手段。文本 分类是一个复杂的系统问题，是涉及文本表示、特征选择、学习算法以及算法决 策等多种复杂技术的综合应用。 2 2 问题描述 2 2 1 文本分类 分类可用数据库术语描述为：给定一训练数据的集合t ，t 中的元素记录由若 干个属性描述。在属性中有且仅有一个属性作为类别属性。属性集合用矢量 工= ( x ，x ：，x 。) 表示，其中x 。对应各非类别属性，可以具有不同的值域。当一 个属性的值域为连续域时，称该属性为连续属性( n u m e r i c a la t t r i b u t e ) ，否则称为 离散属性( d i s c r e t e a t t r i b u t e ) i 2 3 1 。用c 表示类别属性，c = c l ，g ，即数据集有 k 个不同的类别。那么，t 就隐含地确定了一个从矢量x 到类别属性c 的映射函 数h ：，) 一c ，分类的目的就是采用某种方法( 模型) 将该隐含的函数h 表示出 来。 2 2 2 单标号文本分类与多标号文本分类 若文本集中的每个文本必须属于且只能属于一个类别，即只能为文本指定一 个类标号，那么这种分类称为单标号文本分类( s i n g l e - l a b e l ) ，也称为非重叠分类。 若文本集中的每个文本可以属于一个或多个类，那么这种分类称为多标号文 本分类( m u l t i l a b e lt e x tc a t e g o r i z a t i o n ) ，也称重叠分类。 2 2 3 类别中心分类与文档中心分类 利用分类器分类文档有两种不同的模式：类别中心分类( c a t e g o r y - p i v o t e d c a t e g o r i z a t i o n , c p c ) 和文档中心分类( d o c u m e n t - p i v o t e dc a t e g o r i z a t i o n , d p c ) 。 重庆大学硕士学位论文2 文本分类及其评估方法 类别中心分类是指给定类别c l ，发现e 类的所有文档。 文档中心分类则是给定文档d ，发现文档d ，所属的所有类别。 一般情况下，当文档集的状态随时间变化而变化时，适于采用d p c 方式，如 文本过滤。当类别集c = c 1 ，q 随时间变化而变化时，原来按类别集 c = c 1 ，q ) 分类的文档因新类别g 肌。的加入而需要重新分类，这种情况下适合 采用c p c 方式分类。 2 3 文本分类应用 文本分类的应用范围很广，不同种类应用之间界限也很模糊，有时是人为地进 行划分。 2 3 1 自动索引 早期的文本分类研究主要用于布尔型信息检索系统的自动索引。文本索引的 目的是将每篇文档用词典中的一个或多个关键字短语表示。如果将所有词典中的 关键词短语看成类别，文本索引实际就是确定每篇文本相关的类别，即相关的关 键词，所以说文本索引实际就是文本分类的一种特殊情况。在这种情况下适合采 用以文本为中心的分类模式【2 4 】。 2 3 2 文本过滤 文本过滤可以看成一种两类分类。进入过滤系统的文档被分成两个互不相交 的类别：相关类和不相关类。此外，过滤系统也可以对相关类进一步分类，比如 可以将相关类文本迸一步按主题进行划分。 2 3 3 w 曲文档分类 由于w e b 文档的类别划分不是一成不变的，随着时间的推移，会有新的类别 加入或者有过时的类别被删除，因此w e b 文档的自动分类适合采用以类别为中心 的分类模式。此外，与普通文档分类不同，w e b 文档自动分类有两个主要特性 2 4 1 ： 文档的超文本性质：超链接含有丰富的信息，有助于理解被链接页面与链 接页面之间的关联。这方面的研究在文酬2 5 】1 2 6 1 中提到，而文献鲫对几种分析超文 本的方法进行了比较实验。 类别集具有层次结构，利用层次分类技术可以将复杂的分类问题分解为简 单的分类问题。 2 4 文本分类器 在各类分类方法中，k 最邻近分类，支持向量机分类，朴素贝叶斯分类是应用 较广的文本分类方法，本章主要介绍这几种分类方法。关联分类是l i u 1 3 1 9 8 年新 提出的方法，目前对它的研究还不太深入。本文的第五章集中讨论文本关联分类 9 重庆大学硕士学位论文 2 文本分类及其评估方法 问题。 2 4 1k n n | 最邻近( k n n ) g - - 种传统的模式识别方法哪! ，可以用于文本分类。本质上讲， k n n 根据到测试样本最近的k 个训练样本对测试样本进行分类，通常使用以下几 种距离度量。 欧氏距离： d ( 多，孑) = ，( n - q ，) 2 ( 2 1 ) 内积： o ( p ，孑) = p ；q ， ( 2 2 ) 乙p l q i 余弦距离：。q ，g 2 旆 q 3 对测试样本的分类以其最近的k 个训练样本为基础，选取这k 个训练样本中多 数样本所属的类别作为预测结果，形式化地，测试样本石的类别贴) 是这样给出的 y ( 力= a r g m a x f n ( x ，c f ) i 石，k n n ) ( 2 4 ) 这里n ( x j ，q ) 是k 最邻近集k n n 中属于c t 的训练样本的数量。 2 4 2 支持向量机 支持向量机岱v m ) 是机器学习领域较新的一种学习方法，最先由v a p n i k 和他 的合作者提出。该方法基于计算学习理论的结构风险极小化原理，寻求一个决策 面把训练数据点分成两类并且以训练集中选择的代表数据作为支持向量进行决 策。 已知线性可分点集s = 葺l i = 1 , 2 ， ，点而属于两个被标记成乃 - l ，+ 1 ) 的 类中的一个，由公式( 2 5 ) 定义的分离超平面将s 分成两部分，每部分只包含具有 相同类标记的点。 w o x + b = 0 ( 2 5 ) 任何位于超平面上的点x 和任一训练样本薯s 满足 y ，( w 。五4 - 6 ) 1( 2 6 ) s v m 学习的目标是找出最佳分离超平面( o p t i m a ls e p a r a t i n g h y p e r - p l a n e ，o s h ) ， 使其距离两侧的空白边界最大，可以公式化为： m i n i m i z e 去i i 叫1 2 s u b j e c t t o ) ，( w - + 6 ) 1( 2 7 ) 距o s h 最近的点称为支持向量( 如图2 1 ) 。 i o 重庆大学硕士学位论文 2 文本分类及其评估方法 图2 1 分离超平面 f i g2 1s e p a r a t i n gh y p e r p l a n e 分离超平面( 实线集) ，最优分离超平面( 粗实线) ，以及支持向量( 虚线上的 数据点) 。虚线确定最大边缘。 在分类过程中，s v m 基于全局最优分离超平面做出决策。它只是简单地找出 测试样本位于o s h 的哪一边。 s v m 问题可以扩展到非线性的情况，采用基