（计算机应用技术专业论文）基于粗糙集的文本分类算法研究.pdf

摘要 随着网络技术的迅猛发展，信息处理成为人们获取有用信息不可缺少的工具。文本 分类是中文信息处理的一个重要的研究领域。其目标是在分析文本内容的基础上，给文 本分配一个或多个比较合适的类别，从而提高文本检索等应用的处理效率。目前已经有 许多方法应用到该领域，如支持向量机方法、k 近邻方法、朴素贝叶斯方法、决策树方 法等等。与这些方法相比将租糙集理论用于文本分类有以下优点：粗糙集理论无需提供 除问题所需处理的数据集合之外的任何先验信息；包括了知识的一种形式模型，使得知 识有了清晰的数据意义，并且可用数学方法来分析处理；能够获得分类所需的最小特征 属性集，可以在不影响分类精度的条件下降低特征向量的维数；可以得到最简的显式表 达的分类规则。而其它方法则有的无法得到显式规则，如朴素贝叶斯方法和k 近邻方法， 有的得到的规则含有大量的冗余条件，如决策树方法。 本文研究利用粗糙集对文本进行分类的理论与方法。首先，我们对文本进行预处理， 包括分词、词频统计、停用词的处理等；然后利用t f i d f 函数提取特征；之后用决策 表来表示分类知识：将特征词的集合作为属性集，特征词的权值作为属性值，文本所属 的类别作为决策属性，再通过属性约简得到分类规则；最后根据规则对测试文本进行分 类，验证训练结果的正确性。 实验结果表明，基于粗糙集的文本分类方法是行之有效的。它不但有效降低了特征 向量的维数，而且保证了文本分类的精度和召回率。 关键词：文本分类；特征选择：租糙集；属性约简；决策规则 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r u e tt e c h n o l o g y , i n f o r m a t i o np r o c e s s i n gh a s b e d ) m e 趾i n d i s p e n s a b l et o o lf o rp e o p l et oo b t a i nu s e f u li n f o r m a t i o n t e x tc a t e g o r i z a t i o ni s a l li m p o r t a n tr e s e a r c hf i e l d , i t st a r g e ti st oa l l o c a t eo n eo rm o r es u i t a b l ec l a s s e st ot e x t s ，b a s e d o na n a l y z i n gt h et e x tc o n l e n t s n o wt h e r ea r em a n ym e t h o d st h a th a v eb e e na p p l i e dt ot h i s f i e l d , s u c hf i t ss v m ，k n n ，n a i v eb a y e s ，d e o i s i o nt r e e ，e t c c o m p a r e dw i t ht h e s em e t h o d s ， t h em e t h o db a s e do nr o u g hs e th a st h ef o l l o w i n ga d v a n t a g e s i td o e sn o tn e e dt os u p p l ya n y p r i o r - p r o b a b i l i t yi n f o r m a t i o nb e s i d e st h ed a t as e t su s e df o rs o l v i n gt h ep r o b l e m i ti n c l u d e sa k i n do ff o r m a tm o d e l ，w h i c hg i v e sk n o w l e d g eo b v i o u sd a t am e a n i n ga n de a r lb ea n a l y z e da n d p r o c e s s e db ym a t h e m a t i cm e t h o d i tc a no b t a i nt h em i n i n l t u l lf e a t u r es e t sa n d c a l lr e d u c et h e d i m e n s i o n so ff e a t u r ev e e _ t o r , h a v i n gn oe f f e c t0 1 1t e x tc a t e g o r i z a t i o na c c u r a c y t l l i sm e t h o d c a ng e tt h es i m p l e s tr u l e s f o ro t h e rm e t h o d s ，s o m ec a n n o tg e to b v i o u s e x p r e s s e dr u l e s ，s u c h a sk n na n dn a i v eb a y e s s o m eh a sm u c hm o r er e d u n d a n tr u l e s ，s u c ha sd e c i s i o nt r e e t h i st h e s i sd i s c u s s e st h et e x tc a t e g o r i z a t i o nt a s ku s i n gt h e o r yo fr o u g hs e t f i r s t l y , t e x t s a r ep r e t r e a t e di n c l u d i n gp a r t i c i p l e ，s t a f i s t i c a lw o r df r e q u e n c y , m a n a g i n gs t o p - w o r d se t c t h e n p i c ku pc h a r a c t e r i s t i cw o r d sw i t ht f i d ff u n c t i o n s e c o n d l y , k n o w l e d g eo fc l a s s i f i c a t i o ni s s h o w e db yd e c i s i o nt a b l e ：c h a r a c t e r i s t i cw o r d sa sa t t r i b u t e s ，w e i g h t sa st h ev a l u e so f a t t r i b u t e s a n dc l a s s e so ft e x t sa st h ed e c i s i o na t t r i b u t e s 1 m r d l y ，d e c i s i o nr u l e sa mp r o d u c e dt h r o u g h a t t r i b u t e sr e d u c t i o n f i n a l l y , w ec a t e g o r i z et e s tt e x t sa c c o r d i n gt og a i n e dr u l e sj u s ti no r d e rt o v a l i d a t ec o r r e l q l l e s s t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h ee f f e c t i v e n e s so ft h e 聊o a c h i tn o to n l yr e d u c e s t h ef e a t u r ev e c t o rd i m e n s i o n s ，b u ti n c r e a s e st h ep r e c i s i o na n dr e c a l l k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；c h a r a c t e r i s t i cs e l e c t i o n ；r o u g hs e t ；a t t r i b u t ea p p r o x i m a t i o n ； d e c i s i o nr u l e s u 独创性声明 本久声鞠所至交熬学位论文是本人在导瓣撵导下遴行静研究工幸譬及取褥豹研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含冀他 人已缀发表或撰写过鲍研究成果，也不包含为获缛东j e 师范大学或葵佳教弯壤臻 的学位或证书而使用遗的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：叠熊豳 学位论文舨毅使黑授权豢 本学位论文作者完全了解东北师瓶大学有关保留、使用学位论文的规定，即： 东寇雾器范大学骞教保辩劳淘罄家毒关帮秘或瓤祷送交学位论文静复擎件和磁焱， 允许论文被查阅和借阅。本人授权东j b 师范犬学可以将学位论文的全部或部分内 容缓入舂关数据库进蟹检索，霉班采耀影印、缭零或其它复秘手段缣存、汇缡学 位论文。 ( 保密懿学位论文在解蜜屋逶爰零授权警) 学位论文据者签名：越避 日 期：趔二f l ：i 口 学位论文作者毕业后去向： 工作单位： 邋讯地址； 掺鼯教帮签名： 日 期：触zz 。越 电话： 邮编： 。l 萼l 言 第一章绪论 黢特啜的国瑷，馒我们的生活进入一个信息离速发展的时代，w e b 褥到了飞跃的发 展。截止至今，已经发布的网页以亿为计算单位，人们从中获取大量的信息。但是w e b 网页上的信息是如此之多，并不像图书馆那样分门别类的做好索引来穷便人们取阕，网 页上究斥着书刊、影啻、资源、广告、图象等服务，使得人们无所适从。 照着问题的逐渐复杂化，如何实现高速有效、经济可行的检索方案越来越受到人们 普遍的关注，两络机器入豹出现给人们带来了希望，但是检索策略的智能纯程度并不怒 很理想，而且所获得的信息仍没有得到有效的自动分类和整理。现在，很多大裂网站都 翻瘸入工搡律的方法试图建立一种有翻予人稻检索魏途径，虽然取得了巨大豹教益，德 是仍没有脱离人工的操作的方式。随着现代化技术的进步，互联网走遴千家万户，人们 获褥僖怠静来源越来越广。毽是这些僚患稳藏在各释不同类鼙魏阚站巾，竣芝结构纯、 组织化和规范性，使得人们获取难以筛选的超匿信息，大大降低了文本信息的利用率。 嚣蘧，为了疆毫入翻对翳络痞惠燮源熬秘蔼率，j i 重交本绩患逶 亍辩学准确豹分类熬 理是十分必要的。利用人工进行文本分类的传统方法无法满足实际应用的需求。而w e b 文本戆蠡动分类爨是剩蓬诗算撬按 燹建定义熬囊题类躅，蠢魂缝挺文秘集会孛鹣每一薅 文档确定类别，从而掇高了文本检索、文本存储等应用的处理效率。目前已经有许多方 法应鼹裂该镁域，翅支持定量桩方法( s v m ) 网、k 遥邻方法( k n n ) p ”、朴素贝孽疑 方法( n a i v eb a y e s ) f 5 1 ，决策树方法( d e c i s i o nt r e e ) 等，与这些方法相比，粗糙粲理论在 分类方蘧吴有以下鸵饯点 1 2 1 ： ( 1 ) 租糙蘩方法能够获得分类所需的最小特征属性集，利用这些属性能够在不降低 精度鲍条 牛下提高分类的速度； ( 2 ) 粗糙集方法可以得到鼹简的鼗式表达的分类规则，而其它的方法有的无法得到 显式规则( 耍眭贝叶斯和k n n 方法) ，有的方法褥到的规则含煮大量的强余条件( 如决策 树方法) 。 1 2 文本分类的研究背景和意义 在网络和通信技术迅速发展的今天，人们越来越感受到了信息的冲击，丽文本是储 惠豹鬟要载钵，入粕爨常生溪审瑟接皴裂豹错崽骞8 0 2 莹裹激文本翡形式存袭。售惑蠹 容和格式的多样化、复杂化，信息更新速度之快，使人们无法浏览所商感兴趣的内容。 而且叉不存在标准的文本分类准则，所以为管理收集到的文本信息而进行的文本分类也 交 孽越来越嚣难，残为亟特瓣决瓣翔联。 文本分类对于信息处理的藿要性囊要表现在如下几方面【1 9 j ： l 文本分类鸯信爨检索提供各文本集费黟瓣缝织每缝梅，大大筵纯了慈文本售惑 库中存取文本的操作，为信息检索提供了更高散的搜索策略和更准确的查询结果； 笏因特憋土懿袭线文本绩惑急翘增搬，等工分类秘处理这些售怠蚕毽耗费大量懿 入力和物力，在速度和精度方阿也远玩不能满足用户的要求。文本自动分类及相关技术 鲍应煺可以帮助用户餐效收集秘选择獒赝感兴趣的文本售息，挖其是锼助鼹户在日益增 多的海量信息中发现新的概念并自动分析它们之间的荚系，真正做到信息处墩的自动 化； 3 ) 文本分类在防火墙技术中也脊广泛的虑用，将快速精细的分类技术与包过滤技 术有机地结合，能有效地防止不健康馆息的侵入，同时，也可减少互联网上有害信息的 流动： 4 ) 文本分类是几乎是所梅基于内容的文体管理的学科的熬石，是处理和组织大规 模文本信惠韵关键技术，在文本资拳年的管理和分类串中分重要，可戳说研究文本分类肖 着广泛的商业前景和实际应用价值； 辩分类技术可敬筵稻产分为对不阖事秘懑兴趣静“函棒”麸覆实现个褴佬酌蔫惑 推荐： 6 霉蔫予撞取掰号絮谖、薪鼙分发、搀窍电子都俘叛教掌习瘸户兴趣。 1 3 阑内外相关研究 1 3 1 两外自动分类研究动态 戮嚣翦，鲞动分粪在藿磐经历了三令发溅蹬段； 第一阶段( 1 9 5 8 1 9 6 4 ) 主要进行自动分类的可行性研究； 第二阶段0 9 6 5 1 9 7 4 ) 断鑫动分类弱实验研究； 第三阶段( 1 9 7 5 黛今) 进入实用化阶段【2 0 】。 灏强瓣文零塞凄分类霹褒始子筠毽纪弱零钱寒， 王。e l u h n 薹先将逶叛绞诗愚戆弼 于自动分类，在该领域进行了汗刨性的研究。1 9 6 0 年，m a r o n 在j o u r n a lo f a s m 上发袭 了秀荚自动分类浆第一蒺论文，其爱诲多学嚣在这一镶域进符了卓毒藏效熬谚究王锋。 从2 0 世纪6 0 年代到8 0 年代末，这期间最有效的文本分类系统直是由专家人工 梅建的基于熟识工程技术豹分类系统。其典型应用裁是卡内基集爨为路透社开发的 c o n 蝣i l e 系统，它主要是由专溉人员编写了一戆分类规则来指导分类，在r e u t e r s 的部分 语料艨上它的效果非常好，乎均准确零和召凰率都可达到9 0 ，但是程其它的应用镢唆 采用o o n g t n 】e 系统将会耗费丈量的入为和物力： 2 9 0 年代初期，基于机器学萎j ( m a c h i n e l e a r n i n g ) 的分淡技术开始取代基于知识工程的 方法鼹秀文奉分类黪圭漉技术。这释黧法逶过照缡文本集麓特弦喜穗戮建一令分类器， 这些文档集合辫先被锁域专家人工地分类到类熊c = ( c l ，c 2 c 。) 的释个类c i 中。分 类嚣可以馋魏一令囊则捷定文橙霭是否震予粪q ，蟊慕类集c 被更毅，或者系统要藏 用于其它不同的领域。只需要鬣新构造一个人篡分类文档集合。通过机器学习，自动地 褥逢一个分类嚣，显然，塞子这辩分类舅法不再震要帮谖王程簿器领域专家黪分久，节 约了犬缝专家人力资源，同时加快了分类系统的建立速度。 一黪褥究卷维会祝搂学习方法窝人王磐能鲶技零送行7 夹缝鳇探豢，提出了多释分 类模型和分类瓣法。妻h 基于向凝空间模型的r o c c h i o 分旋器及数一系列的改甏 算法。如 支持秘慧辍方法、邋邻方法、李 素浆峙簸方法、决策楗方法、耱经燃终( n e u r a ln e t ) 等等。这些方法在英文及西语义本自动分类上祷广泛的研究，均取得了不错的效果。嗣 终很多研究人鼹慰英文交本分类领域黪蚤个鲻避都毒攘当深入鹣硬究，对足莉流毒亍的方 法进行了大量的对沈研究。很多研究表髓，k n n 和s v m 是英文文本分烫串的戴好方法， 还有些研究人员研炎袭明结仓不同的分类爨熊够提藤分类的精度。鲤煎，国外的自动 分类系绕已经瓤最初的可行毪骄究经历了实验研究送入了实焉纯阶段，箨在酃佟分类、 电子会议、信息过滤等方面得副了较为广泛的虚用。 1 9 9 4 年，a t & t 安验室静d a v i dd l e w i s 等久瓣綦干菲确意链静爵渤分类技术骰了 研究。黼年后，该实验赛将自动分类的披术应用予电子邮件领域。1 9 9 7 牮，德国d o r t m u n d 丈学t o r s t e nj o a c h i m s 譬人磅究了萋予商蓬空麓模壅瓣盘旗分类系统。弼车，美辫s t a n f o r d 大学d a p h n ek o l l e r 等人提出了基于很少语料调汇的层次自动分类方法。1 9 9 8 年，美圜 c a r n e g i em e l t o n 丈学y t m i n gy a n g 等天将决蓉辫等聚癸冀法应糟予在线宣囊分类。1 9 9 9 年，美豳j u s tr e s e a r c h 公司的a n d r e wm c c a l l u m 等人避用信息熵理论、b a y e s 耀论等蜜 瑗了多类号蘸囊裁分类。蘧蜃，f a b r i z i o as e b a s t i a n i 等辑究了梳嚣学习在文本蠢蘑分类 中的避用：t h o r s t e n j o a e h i m s 游研究了基于支持向量机的文本分类方法栩。 1 3 2 溺内研究情况 我筵戆鑫魂分类蔓终戆予年代裙蘩，大律主爨掰了获露符毪探讨一辅霸分类系 统一自动分类懋统三个发展阶段。 1 9 8 1 年，檬汶漠先生善免蹿鸯饕分类送行搽谤，获滓箕瓿管理分类表、诗算税分类 检索，计算机自动分类、机编分类表等四个方面介绍了国外的发展概况。到目前，我阐 毫磅裁密一裁辘蘑磐类系统及瘩凌努类系统，铡翔：t 9 8 4 年，葵乡强磷发了叛久工主鼹 分析、系统完成查表的辅助分擞系统；1 9 8 6 苹，上海交通大学米兰娟等开发了计算类蛸 属度、攥r a v e s 最枣损失爨裂麓定癸类煞塞动分类系统；1 9 9 2 牟，弱淡大学终太谤、黪 皓等研制了以产生式慧统、人工定类为主要技米特点的自动分撩系统；1 9 9 4 华，东北大 学李效、薮星骈发了基于联想挞运、蘩惩罚袭、关系知识痒、爨义词典瘴熟专象系统； 1 9 9 5 颦，清华大学吴翠歼发了以语料稽关系数作为分类依据，譬频、词频及冀常用搭配 为补充、人工指导的自动分类系统：1 9 9 7 年，上海交通大学的王永成等研发了基于部件 词典技术、自动分类用关键词分类归属表的自动分类系统；1 9 9 9 年，中国农业大学陶兰 等人研制了基于b p 网络的文本分类系统：随后，中国科学院计算技术研究所李晓黎等 提出了一种新的分类模型，该模型在己有的英语语义词典及大量训练集的基础上，应用 机器学习、数据挖掘等技术进行知识获取并最终形成若干个概念推理网【1 4 1 ；2 0 0 1 年， 大连理工大学林鸿飞给出了基于示例的文本标题分类机南一5 】；2 0 0 2 年，北京大学王爱 华等利用基于信任函数的信息综合方法对多个文本分类器进行组合使用【1 6 l ；2 0 0 3 年， 山西大学李钝在空间向量模型的基础上将文本聚类和粗糙集理论的属性约简相结合，提 出了一种新的文本分类方法【l _ n 。 1 4 论文框架 本论文共有以下五章： 第一章绪论，包括文本分类的背景、意义和国内外相关研究； 第二章粗糙集理论、w e b 挖掘和文本分类，主要介绍了粗糙集的基本理论，w e b 挖掘技术及其分类和几种文本分类方法； 第三章特征提取，讨论在分类之前需要做的预处理工作，以及常用的特征提取方 法： 第四章权重计算，研究常用的权重计算方法以及权值离散化方法； 第五章基于粗糙集理论的分类算法研究，提出一种基于粗糙集的文本分类方法， 讨论了实验测试和实验结果等内容。 4 2 1 孳l 言 第二蓬粗糙集理论、w 两挖掘程文本分类 越糙集理论( r o u g hs e t ) 是虫波兰肇汐毽王大学z 。p a w l a k 教授予1 9 8 2 年提出来熬。 它是种刻划不完整能和不确定性的数学工具，能有效地分析和处理不精确、不一致、 不完熬等各种不完备傣息，并从中发现隐含的知识，揭示潜在愆规律。粗糙集理论的磺 究已缀经历了2 0 多年的时闯，无论照在系统理论、计算模型的建立和应用系统的研制 开发上，都已款德了很多成暴，也建立了一套较为完罄的理论体系，该理论激经渗透剿 人工锗能的各个分支，在模式识剐，机器学习等方面都有成功的应用 1 - 2 1 。 2 2 粗糙集基本概念 2 2 1 粗糙集定义 记u 为宥限非空集合( 即论域) ，r 是上的一个等价关系，则露把u 划分成一族 互不襁交的子集，记作u r 。u 土戆一羧划分称必关于u 鹣一令知识痒( k n o w l e d g e b a s e ) 。 蓑j p 三霆。璺j p 彰，剩q p ( p 孛掰骞等绘关系翡交集) 巍是一令簿诠关系，稔梵尹 上的不可区分关系，记为f 蒯( 尸) 。 绘定知识库k = ，r ) ，对于每个子集爿蠡u 和个等价关系五甚涮) ，定义两个 子集；l 、r x = u y u r i y s x 2 、r - x - - u i u r i y f l x 簪彩 分别称为z 的r 下近似和x 的r 上近似。 襁糙集艏貔由x 麴霹下迓儆帮x 豹霄上近议来表示。 2 2 , 2 躲谖与苓分唆笑系 在糨糙集理论中，“知识”被认为是一种将现实或抽象的对象进行分类的能力。 定义2 1 给定我们感兴趣的对毅论域u ，对于任何子集x u ，称之为u 中的概 念或范畴。为了筑范越觅，我们认为窝集也燕一个概念，并登u 中任何概念羧称为关于 u 的抽象知识，简称知识。 例如，给定一磊舆积本集合u = 和。，工：，妁，扎，而，而，黾 ，子集溉，码，x ， 构成按颜 色分炎戆“缎鬯”熊谈，子集k ，瓤，魄 穆裁按镩积分类懿“犬夔”皴谖。 为了便于数学推导，我们通常用簿价关系代替分类，在这里，这两个概念是完全可 瑷互耨替代静。 定义2 2 设u 怒一个论域，r 遐u 上的一个等价关系。u r 表示【，上由r 导出的 所有等徐类。缸k 表承包含元素石静霆鼬等价类，x 拶。一个知识瘁就是一个关系系统 k = 妙，尹 ，其中u 是沦壤，p 是汐上等俊关系族。麴果q 芒尹虽q 喾彩，粼n 尹( p 戆 所有铸价关絮的交) 也是一种等价关系，称为p 上不分明关蓉，且记为删p ) 。不分明 关系的概念怒r s 理论的基石，它揭豕出论域知识的颗粒状结构。 2 2 3 糖糙集与遥截 一 定义2 3 令x g u ，当x 髭够惩震往子集曼确切建撼述( 帮楚嚣毪子集霞掰确定 的u 上的不分明关系的并) 时，称爿是可定义的，褥则称是不可定义的。r 可定义 集也称作精确集，霞不可定义集氇称为菲精确集或霆糙糙集( 在不发生混淆的情况下也 简称为粗糙集) 。 定义2 4 假设给定翔识库k 。移，r ，对予每个子集x g u 和一个等价关系 霆i n d ( k ，我织霹戳摄撼震豹基本集会翡攒述寒捌分集会苫，舞了餐量蘩手霆戆基 本集会的描述y ，精确地说明石中对敷的隶属度情况，我们使用下近似集与上近似集这 两令概念，玄锅分弱定义强下； 下近似集震x ；u 影毒u ，n d ( r ) ：e g x ， 上近似集r x ；u 戳毫u ，n 似) ：z n x 彩 。 龟哥瑷表示为： r 一似) = 扛e u ：b k 工 ， r 一似) = b u ：b k n = 彩) 。 定义2 5 集合6 精。留) = 露一秘) 一最一秘) 称为x 的r 边界域，集会p 。) = 盂。似) 6 称为x 的r 正域，j 黝 n e g 。似) = u r 一口) 称为z 的r 负域。 髓似) 是根据知识r ，u 中所有一定能够归入z 的元素的集合，即所有包含于j 的 l 静并。r - 讧) 是报攒知移 露，u 中一定莪和可能能够癌入并豹元素酌集合，帮所有为 x 盼交不为零的茸故辫tb n r g ) 是投摆知谈霆，u 孛瓣苓熊磐定努入集会菇，又苓缝 肯定归入集合膏的元索构成的集合。p o s 。) 是根据知识足，u 中所糍一定能归入集食 x 的冤素构成的集合an e g 。口) 是根据知识r ，u 中所有不能确定一定归入集合z 的咒 素懿煞会。墅2 1 麦糕糙集摄念瓣示意鹜。 砜留) p o s a 戗) 凇最 冈 匿乳疆 2 2 4 近似精度 图2 , 1 粗糙集概念的示意图 u x g - ( x ) 郴) 集合的不确定性怒由于边界域的存在而弓l 起的，集合的边界域越犬，其精确性越低， 是更猴确地表达这一燕，我 f 】等l 入壤发熬摄念。 定义2 6 假定集含彳是论域u 上的一个关于知识r 的粗糙集，定义其武精度( 猩 不发生混淆的情况下，也简称糖度) 为： 以 ) = 陬伍】肛一 l 定义其震耀糙度麓： 咋) = 1 d r ) 蠢诧可觅，褪糙鬓x 静精度是一个区间f o ，l 】上豹实数，它定义了粗糙集并的可定 义程度，即集合彳的确定度。z 的粗糙度与精度恰恰相反，寝示的是集合并的知识的 不完全程度。 例2 1 - 飨定一玩具积木集合u = k ，x 2 ，如，秘，如 ，基予属性颜包r 分类， 我们_ 町以得到下列等价类： = 如，恐，墨 ，鼍= 如，瓠 ，嚣= ，魏，五 。 7 假如我们定义一种分类爿= q ：，k ，x 。 ，椴据前露的定义我们有； 盖 ) = 墨= 扛：，心 ， 霹一转) = 妖u 五= 和2 ，x 4 ，如，x 6 ，工。 ， 5 嚣。访= 震一留) 一是留) = ，魏，黾 ， p o s 。似) = 丑一仪) = k = 妊：，囊 ， n e g 。僻) z u - r 似) = 缸。，而，砖，x 6 ，坼，粕 ， d r 留) = 陋( x | i r 一秘l = 2 5 = 0 4 ， 臻翟) = l d 。弘= l 一0 4 ；o + 6 。 2 3 数据集的约简 2 3 i 决策表 糯糙集瑷论中应用决策袭来描述论域中的对象。它是一张二维表格，每行描述一 个对象，每一列描述对象的j 胂属性。属性分为条件属性和决策属性，论域中的对象根 据条件藕性的不同，被翅分到其有不问决策耨往的决策类。 定义2 , 7 一个决策表信患系统( 简称决策表) s u ，瓤v ，f ，其申，u 是对象 的集含，也称为论域r = c u d 是属性集合，子集c 和d 分别称为条件属性集和决策 属性榘，d 彩，v 。u 怒属性谯的集合，e 表示属性r 露的属性值范瀚，邸属性 雎r r 豹篷壤，。厂：移x 霆一矿是个信愚滋数，窀捂定u 巾每一个对象x 戆覆往麓。 定义2 8 设u 为一个论域，p 、q 为定义在u 上的丽个等价关系簇，q 的p 芷域 记为e o s e ( q ) ，定义为： p 醛强国= 疆移留) x 截i | 娃 其中只 ) 为x 憋下近似集。 定义2 9 给定决策表s ，c 和d 分别为决策表的条件属性和决策属性，条件分类 定义为：琶蟛屈彩( c ，0 = l ，掰) ，m 凳条辞分类熬今数；决策分类定义为； 巷 x j v 肼d ( d ) ，( ，= l ，h ) ，n 为决策分类的个数。 定义2 1 0 在决策表s u ，r ，v ，f 中，r = c u d ，若对于c ，c 中同一等价类的 记录都有相同的决策值，则称这个等价类中的任一记录为确定性记录；若对于u c 中同 一等价类中的记录有不同的决策值，则称这个等价类中的任一记录为不确定性记录。 定义2 i i 在决策表s = 中，若所有的记录都是确定性记录，则s 称为 相容表；否则s 称为不相容表。 2 3 2 约简与核 在粗糙集应用中，我们经常要在保持知识库中初等范畴的情况下消去冗余范畴，进 行知识简化。完成知识简化的基本工作是利用约简和核这两个基本概念来进行的。 令月为一等价关系族，f ir r ，如果肌d ) = n v o ( r 一 ， ) ，称，为r 中可省略的， 否则，为r 中不可省略的。 对于属性子集p r ，若存在q = p - r ，q p ，使得肌d ) = 唧) ，且q 为 最小子集，则称q 为p 的约简，用r e d ( p ) 表示。 一个属性集合尸可能有多种约简。 p 中所用约简属性集中都包含的不可省略的集合，即约简r e d ( p ) 的交集称为p 的 核，记作c o r p ( p ) 。它是表示知识必不可少的重要属性集。 可以看出，核这个概念的用处有两个方面：首先它可以作为所有约简的计算基础， 因为核包含在所有的约简之中，并且计算可以直接进行；其次可以解释为在知识化筒时 它是不能消去的知识特征部分的集合。计算约简的复杂性随决策表的增大呈指数增长， 是一个典型的n p 完全问题，当然实际中没有必要求出所有的约简。 例2 2 ：给定决策表如表2 1 所示。 决策表有条件属性a 、b 、c ，决策属性d 。 条件分类为e 1 、e 2 、e 3 、e 4 、e 5 五个等价类。 决策分类为x 1 、x 2 、x 3 、x 4 四个等价类。 e 5 分为e 5 ，l 和e 5 2 两部分，分别对应不同的决策值，因此是不一致的，该决策表 为不确定决策表。 条件属性a 和c 是不可省略的，b 是可以省略的，表2 1 条件属性集合 口，b ，c 可以 约简为 口，c ，由于只有这一个约简，核为kc ) 。 9 表2 1 决策表 uabcd e 1 1231x 1 e 2 l212 e 32232勉 e a2332 e 5 13513x 3 e 5 ，2 3 5l 4x 4 2 3 3 可辨识矩阵 可辨识矩阵是由波兰著名的数学家s k o w r o n 教授提出的。 定义2 1 1 令决策表系统s = ，其中，u 是论域且u = “，x ：，矗) ， r = a u d 是属性集合，a 和d = 缸j 分剐称为条件属性和决策属性集，4 g ) 是样本x 在 属性口上的取值。则可辨识矩阵定义为： 。f 仁a ：a ( x ，) d g ，) d g ，) d g ，) 叫 三1 ，钵剖 【 一， 口b j 2 口b ，j f ，= l ，2 ，疗 d b ) d g ，) 显然，可辨识矩阵是一个依主对角线对称的矩阵，在考虑可辨识矩阵的时候，只需 要考虑其上三角( 或下三角) 部分就可以了。 根据可辨识矩阵的定义，当两个样本( 实例) 的决策属性取值相同时，它们所对应 的可辨识矩阵元素的取值为0 ；当两个样本的决策属性不同且可以通过某些条件属性的 取值不同加以区分时，它们所对应的可辨识矩阵元素的取值为这两个样本属性值不同的 条件属性集合，即可以区分这两个样本的条件属性集合；当两个样本发生冲突时，即所 有条件属性取值相同而决策属性的取值不同时，则它们所对应的可辨识矩阵中的元素取 值为空集。显然，可辨识矩阵元素中是否包含空集元素可以作为判定决策表系统中是否 包含不一致( 冲突) 信息的依据。 1 0 2 4 规则集 定义2 1 2 ：令s = 表示一个决策表，且b c 。由s 产生的一个规 则集表示为f = ：，戌，瑞， ，且名表示如下： 名= 篷口斗d l a c a n d d d j ( f = 1 ，) 其中，表示f 中规则的数目。在名中，如果某些规则中的某个属性值被约简掉了，那 么在这些规则中被约简掉的属性表示为“”。 例如，在一个决策系统中含有5 个条件属性q 。a ，) 和1 个决策属性d ，通常 情况下，( 口l = 1 ) 屯= 2 ) 0 。= 3 ) _ d = 4 表示一条规则，但在本文中，我们把它表 示为( 口l = 1 ) 0 ：= + ) ( 口，= 2 ) 0 。= 3 ) q ，= ) 一d - - - 4 。 粗糙集理论主要应用在对不完整、不精确信息的表达与处理上，它从新的视角出发 对知识进行了定义，把知识看作是关于论域的划分，并引入代数学中的等价关系来讨论 知识。同其他处理不完整、不精确知识的数学理论相比，粗糙集理论的主要优势在于它 不需要任何预备的或额外的先验知识，比如统计学中的概率分布，d e m p s t e r - s h a f e r 证据 理论中的基本概率赋值1 2 3 1 ，或者f u z z y 集理论中的隶属度等，它主要利用集合的上近似 集与下近似集，根据集合中存在的不可区分关系来解决知识的分类问题。 2 5 w e b 挖掘及其分类 2 5 1 w e b 挖掘 数据挖掘是指从大量的数据中提取隐含的、未知的、非平凡的及有潜在价值的模式、 规则和知识，它是数据库研究中的一个很有应用价值的新领域，融合了数据库、人工智 能、机器学习、统计学等多个领域的理论和技术。它包括关联分析、分类分析、聚类分 析、特征分析、模式序列分析、偏差分析、趋势分析等。w e b 挖掘是从数据挖掘发展而 来的，是指在已知数据样本的基础上，通过归纳学习、机器学习、统计分析等方法得到 数据对象间的内在特征，并以此作为依据在网络中提取用户感兴趣的信息或者更高层次 的知识和规律。它除了处理传统数据库中的数值型结构化数据外，处理更多的是文本、 图形、图像等半结构化和非结构化的数据。因此，w e b 挖掘与传统的数据挖掘相比有许 多独特的的地方；首先，w e b 挖掘的对象是大量、异质、分布的w e b 文档；其次，w e b 在逻辑上是一个由文档结点和和超链构成的图；第三，由于w 曲本身是半结构化或无 结构化，且缺乏机器可理解的语义，有些数据挖掘技术不适用于w e b 挖掘，即使可用 需要对w e b 文本进行预处理【1s 】。 2 5 2w e b 挖掘的分类 w e b 信息的多样性决定了w e b 挖掘任务的多样性。按照处理对象的不同，一般将 w e b 挖掘分为三类：w e b 内容挖掘、w e b 结构挖掘、w e b 使用挖掘。 w e b 内容挖掘是指从网络的内容、数据、文档中发现有用信息的过程。从资源形式 看，网络信息内容是由文本、图像、音频、视频、元数据等形式的数据组成的。w e b 内 容挖掘可以分为文本挖掘和多媒体挖掘。 w e b 结构挖掘是指挖掘w e b 潜在的链接结构模式。这种思想源于引文分析，即通 过分析个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式。这种模 式可以用于网页归类，并且可以由此获得有关不同网页间相似度及关联度的信息。w e b 结构挖掘有助于用户找到相关主题的权威站点，并且可以概观指向众多权威站点的相关 主题的站点。 w e b 使用挖掘是指从w 曲的访问记录中提取感兴趣的模式，分析这些数据可以帮 助理解用户的行为，从而改进站点的结构或为用户提供个性化的服务。w e b 内容挖掘、 w e b 结构挖掘的对象是网上的原始数据，而w e b 用法挖掘则不同于前两者，它面对的 是在用户和网络交互的过程中抽取出来的第二手数据。这些数据包括网络服务器访问记 录、代理服务器日志记录、浏览器日志记录、用户简介、注册信息、用户对话或交易信 息、用户提问式等等”。 2 6 文本分类算法 在众多的文本分类算法中，我们重点介绍三种方法：简单中心向量比较算法、支持 向量机算法和k 近邻算法。 2 6 1 简单中心向量比较算法 该算法的分类思路十分简单，首先在训练阶段求出训练文档各个类别的中心向量。 如：训练文档中“计算机”类的文档有1 1 1 篇，那么计算机类的中心向量的第j 分量c j 为这m 篇文档对应的特征向量的平均值，计算公式如( 2 1 ) 所示： c = l (21) m 其中c j 表示中心向量的第j 分量，表示该类文档中第i 篇文档的第j 个权值。 对新文档进行分类的过程就是一个比较相似度大小的过程，相似度表示为新文档与 1 2 各个类别中心向量的必角余弦值。设笫k 类的中心向缴为c k ，新文档向量为d ，则文档 酝与繁k 类孛心静襁叛废谤算为公式稼萄： 盛把，q ) = c o s ( o , ，q ) = 吻 j - l ( 2 2 ) 其中表示第i 篇文耥的第j 个权值，c 埘表示第k 类文档的第j 个权值的大小。 籀钕度越丈说瞩两个两鬣之闻的受角越小，两个向量趱接近，西就，分娄结莱姆输 出与新文档的相似度最大的类剐，并把它作为新文档的类别。 2 6 。2 支持向擞机方法 支持向鬣机方法怒由v a p n i k 与箕领导的贝尔实缎室的小组一起开发出采的一种机 器学习技术。s v m 的理论基础来自子v a 凹救簿提出的统计学习理论，它的基本思想怒， 对予个给寇钓具有肖限数鬃调练样本的学习任务，如何在猿确往( 对于给鬣调练策) 和机器容量( 机器可冤错误地学习任意训练黛的能力) 进行折震，以褥到最饯的推广性 戆。s v m 算法不仅嚣宥藐实静理论蘩确，蔼蘸应用翔文本分癸靖取褥了缀好鑫搴结果。 设给定的训练集为： g ，y ，) 如，y ：x 如，y t ) i ，x 詹”。y e - l ，一l ( 2 + 3 ) 显剪被一令越擎霹线毂分割，该超平蘧记为嵇4 ) ： x ) + b = 0 。 ( 2 4 ) 獬莱一个锱练集中豹矢蘩麓旋一令越孚瑟无锫谶缝线整努凝，萎艇该超平覆最逐豹 矢量之问的躐离最大。则称该超平面为最佳怒平面。其中距离超平面最近的点称为支持 矢量( s u p p o r t v e c t o r ) ，对决策蕊设计起搀用鲍点豫为支持自爨( s v ) 。 对于线瞧可分酌情形，不失一般往，我们可假定调练集中的矢囊满足下列不等式 ( 2 5 ) ： x f + 6 1 i fy l 。l ( 2 ，5 1 撂犯+ b - 1i fy t = - i 、 我们称式( 2 s ) 为规范形式( c a n o n i c a lf o r m ) ，可将其余并为( 2 6 ) ： y ，和t 蔓+ 6 ) lf = 毛，z ( 2 6 ) 于是构造最俄超平面的问题转化为求( 2 7 ) 的最小值的问题： 婚) ；闽2 2 。7 ) 事实上，支持矢量劐超平嚣豹距离必矿转lt 于是支持矢量之强弱阕黼为掣黟l 。 游求具有最大间隔的最饿超平面的依据燕，一个规范超平面子集的v c 维数满足下 列不等式( 2 8 ) ： h ：r a i n ( j r 2 a 2 】，以) + l ( 2 8 ) 公式( 2 8 ) 中，n 为矢量空间的维数，所有待分割的矢量位于半径为r 的超球内，丽恻l a 。 这样我们就可在固定经验风险的情况下，将使v c 置信度最小的问题转化为使i i 叫l 最小 的问题。构建最佳超平面来分割属于两类的训练集的问题转化为解决下述二次规划问题 ： g ，y ，l g ：，y ：) ，“，y a z r “，y + l ，一l ( 2 9 ) 在式( 2 1 0 ) 的约束条件下： y ，0 葺+ 6 ) li = l ，z( 2 。1 0 ) 求式( 2 11 ) 的最小值： p ) = 主妇) ( 2 。1 1 ) 为了将线性推广到非线性，v a p n i k 提出了支持向量机的概念，其基本思想是：通过事先 确定的非线性映射将输入矢量x 映射到一个高维的特征空间中，然后在此高维特征空间 中构建最佳超平面。t h o s t c nj o a c h i m s 将s v m 用于文本分类并比较了其它的分类算法， 他的结果显示s v m 要优于其它方法。 超平面是对两类分类的划分，对于有大于两类的多类文本分类，就对每个类构造一 个超平面，将这一个类与其余的类分开，有多少个类就构造多少个超平面，测试时就看 哪个超平面最适合测试样本。 2 6 3k 近邻法 k 近邻法 2 3 1 是由c o v e r 和h a r t 于1 9 6 8 年提出的，直至现在仍是模式识别非参数法 中最重要的方法之一。k n n 算法思想很简单：给一篇待识别的文章，系统在训练集中 找到最近的k 个近邻，看这k 个近邻中多数属于哪一类，就把待识别的文章归为哪一类。 k 近邻分类器在已分类文章中检索与待识别的文章最相似的文章，从而获得被测文章的 类别。此算法有简单的优点，但存在问题，需要将所有样本存入计算机中，每次决策都 要计算待识别样本与全部训练样本之间的距离进行比较。因此计算新文档时存储量和计 算量都较大。 上述的三种分类算法属于平面分类器的算法，计算量比较大，分类的速度也不够快， 而且其运算速度的提高受算法本身的限制。 1 4 第三章文本特征提取 在进行文本分类之前，需要将文本袭示成特征向量。无论采用什么样的文本表示模 型，文本分类翊题酝对旋夔文本特 垂空超逶霉懿嚣透足露维、慧至咒万维，大多数豹 学习算法无法处理这么犬的维数，因此特征抽取是文本分类中的关键问题。它嶷有降低 囱量空阕维数、籀纯诗算、瑟业过分投会等捧趱。由予特征子集的数量灏特征数量之闻 呈指数荚系，枚举几乎是不可能的，因此，可以假设特征之间怒相互独立的，这样特征 子集的檄取裁转化为特缀项按敬。 特征选择的主要方法是利用相关数学公式计算来降低原始文本向量的维数，用含有 分类信息较多的特征构成新的文本特征向量。其中最筏单的方法是通过调频选择特征。 谪频就建一个词在文档中出现的次数。通过词频进行特 芷选择就是将词频小予菜一阙值 的词删除，从丽降低特缎空间的维数。该方法燕基于这样一个假设：出现频率小的词对 分类的影响也较小。僵整在信怠检索的研究中认为，有时频率，j 、的谲含有更多的信息。 因此在特征抽取过