（计算机应用技术专业论文）基于web文本的聚类算法的应用研究.pdf

湖北工业大学硕士学位论文 摘要 随着因特网的讯速发展，互联网的数据信息量越来越大。如何对互联网的信 息进行分析，便捷准确的挖掘出需要的信息知识急需解决。对聚类分析的研究可 在相当程度上解决这个问题，不仅可以节省时间，并且可以提高效率。将聚类研 究理论用于w e b 挖掘具有深刻的理论意义和重要的实际价值。本文从理论和实践 两个方面分析与研究了聚类技术在w e b 文本挖掘中的应用。 w e b 文本挖掘涉及众多领域的重要内容，包括：数据挖掘、信息检索、智能 算法等。而本文研究的文本聚类技术是其中的重要内容之一，它不仅是一种非指 导学习方法，而且不需干涉，可由计算机自动处理。 本文研究的重点是通过文本聚类技术对中文文本对象进行聚类操作，首先有 侧重点的对挖掘过程中的重要阶段进行研究，主要包含文本的预处理阶、聚类分 析阶段。在预处理阶段，根据特征选取的特点，利用遗传学的基本知识采用一种 基于遗传策略的特征选取方法。它可以在非监督学习的情况下对用特征向量来表 示的文本个体进行降维操作，可以起到降低聚类算法的复杂度，保证聚类精度的 作用。在聚类算法阶段，通过比较各种聚类算法的优缺点，重点分析了经典的 k m e a n s 算法，然后提出一种对孤立点先检测再提取最后归并的改进 k m e a n s ( w l p d ) 算法。改进的w i p d 算法首先遍历整个样本数据集，找出所有的孤 立点等异常数据进行提取，接下来对提取后的样本集进行聚类，在处理时采用自 适应策略与基于最大距离的聚类中心相结合的选取方法，在相当程度上避免了聚 类结果陷入局部最优的局面，在聚类完成后再将这些孤立点整理后归并入聚类结 果当中，从而确保聚类结果的完整性，排除孤立点对聚类结果的影响。通过在m a t l a b 平台的实验证明改进的w i p d 算法具有优良的属性，并且新算法具有的特点比原 算法要好的多。最后，本文将改进前后的聚类算法应用到实际的系统当中，实现 了中文w e b 文本聚类的整个过程，通过系统和实验证明了新算法的可行性和有效 性。 关键词：w e b 文本；特征选择；遗传算法；孤立点；聚类。 湖北工业大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n t e r a c t i th a sal a r g ea m o u n t so fi n f o r m a t i o n ，a n di t h a sb e c o m em o r ea n dm o r e n o wh o wt oa n a l y z ei n f o r m a t i o no ft h ei n t e r n e th a v et ob e r e s o l v e d t h er e s e a r c ho fc l u s t e r i n gc a ns o l v et h i sp r o b l e mt os o m ee x t e n t ；b yu s i n gi t u s e r sw i l ln o to n l ys a v et i m eb u ta l s oc a ng r e a t l yi m p r o v ee f j f i c i e n c y t h i st h e s i sw i l l d i s c u s st h et h e o r ya n da p p l i c a t i o n so fc l u s t e r i n gt e c h n o l o g y t e x tm i n i n gi sa ni n t e r d i s c i p l i n a r yr e s e a r c hf i e l di n c l u d e ：i n f o r m a t i o nr e t r i e v a l d a t am i n i n g ，i n t e l l i g e n ta l g o r i t h ma ns oo n i nt h i s p a p e r , t h et e x to ft h ec l u s t e r i n g t e c h n o l o g yi so n eo ft h ei m p o r t a n tc o n t e n t s i ti sn o to n l yan o n d i r e c t i v el e a r n i n g a n d w i t h o u ti n t e r f e r e n c e ，a n dc a nb ea u t o m a t i cp r o c e s s e db yc o m p u t e r i nt h ep a p e r ，t h et a r g e to fc h i n e s ew 曲b a s e dt e x tc l u s t e r i n gi st e ：x td a t a t h e r ei sa f o c u so nt h ec h i n e s ew e bt e x tm i n i n gt od e a lw i t ht h ev a r i o u ss t a g e so ft h er e s e a c ho f c h i n e s ew e bi n c l u d i n gt h es t a g eo ft e x tp r e t r e a t m e n ta n dt h es t a g eo ft e x tc l u s t e r i n g b yu s i n gb a s i ck n o w l e d g eo fg e n e t i c s ，am e t h o db a s e do ng e n e t i ca l g o r i t h mf e a t u r e s e l e c t i o nh a sb e e np r o p o s e do nt h es t a g eo ft e x tp r e t r e a t m e n t i tn o to n l yc a nr e d u c et h e d i m e n s i o n a l i t yo ft e x tf e a t u r e ，b u ta l s o c a l lr e d u c et h ec o m p l e x i t yo fc l u s t e r i n g o p e r a t i o n ，a n dm a k eag o o df o u d a t i o nt oa s s u r et h eq u a l i t yo fc l u s t e r i n gr e s u l t s a n di n t h en e x t ，b yc o m p a r i n gt h ep r o n sa n dc o r n so ft h ev a r i o u sc l u s t e r i n ga l g o r i t h m s ， a n a l y s i so ft h ec l a s s i c a lk m e a n sa l g o r i t h m a n dt h e na ni r e p r o v e dk m e a n sm e t h o d w i t ho u t l i e sd e t e c t i o n e x t r a c t i o na n dm e r g i n gh a sb e e np r o p o s e d t 1 1 i sm e t h o do fd a t a c o l l e c t i o no nt h ew e bo fo u t l i e rd e t e c t i o nf i r s t l yf o re x t r a c t i o ni no r d e rt oa v i o dt h e i n f i u n c eo fi s o l a t e dp o i n t s a t i e rc l u s t e r i n g o u t l i e sw i l lb ei n t e g r a t e di n t ot h ec l u s t e r i n g r e s u l t si no r d e rt oh a v ei n t e g r a t e dr e s u l t so fc l u s t e r i n g m e a n w h i l e i nt h ep r o c e s so f c l u s t e r i n g t r a d i t i o n a lb a s i n g o nm i d d l ef u n c t i o nw a si m p r o v e d , u s i n gb a s e d o nt h e l o n g e s td i s t a n c ew i t ha d a p t i v es t r a t e g yf u n c t i o n ，t os o m ee x t e n t ，i tc a na v o i df a l l i n gi n t o l o c a lo p t i m u m e x p e r i m e n t ss h o wt h a tt h ei m p r o v e da l g o r i t h mh a sg o o da d a p t a b i l i t y , m a n ya s p e c t ss u p e r i o rt ot h eo r i g i n a la l g o r i t h m f i n a l l y , t h er e a l i z a t i o no fac h i n e s e 6t e x tc l u s t e r i n gs y s t e mh a sb e e nr e a l i z e d 。c h i n e s e 耽6 绝x th a sa c h i e y e dt h ew h o l e p r o c e s so fc l u s t e r i n g a n di tp r o v et h a tt h en e wa l g o r i t h mh a sg o o de f f e c t i v e n e s s f e a s i b i l i t ya n de f f e c t i v e n e s s k e y w o r d s ：w e bt e x t ；f e a t u r es e l e c t i o n ；g a ；o u t l i e r ；c l u s t e r i n g i i 潮班二堂火学 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体己经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果由本人承担。 学位论文作槲：硌嚷焘吼7 年乡月互乡日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校确权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学雠文储挠馅嗄积指制僦：珏i 公 日期：沙呻年岁月“日日期：弘刁年岁月乞6 日 湖北工业大学硕士学位论文 1 1 研究背景 第1 章绪论 当今社会是一个信息社会，随着互联网的飞速发展，文本作为重要的信息载 体之越来越发挥着重要的作用。在去年发布的一个关于互联网发展状况的报告 指出，到前年为止网页总数将要达到百亿之多，每年以百分之百的速度在增长。 而在这些网页信息当，文本将近占了九成，其次是图像扩音频和视频网页数量相 对比例不耐1 1 。从这份报告可以看出，尽管网络上的资源各种各样，但文本还是占 了大多数比例。因为在某些特殊的情况下，其它类型的资源也可以借用文本这种 形式来传递信息。通过阅览各种各样丰富的文本信息，增长了我们的见识，但同 时也带来了一些负面的因素，比如由于网页之间重复的转载所造成的严重的文本 冗余现象；因查找的技术手段的缺陷而不能从大量的文本信息中查找出有价值的 信息这种查找相对困难的情况；还有互联网上存在的垃圾邮件、短信息泛滥以及 不健康信息污染严重的情况，这些情况就是人们常说的“信息爆炸但知识相对匾 乏”现象。另外，尽管以往存在很多的获取信息的方法，但这些方法已经落后于 人们对有意义信息的需求。所以大量的文本信息如何被计算机有效的处理并从中 挖掘出有价值的信息已经成为一个热点的研究课题。在这种背景下，文本挖掘技 术应运而生。 文本挖掘是一个交叉学科的研究领域，它除了涉及到挖掘技术、模式识别而 且还与信息检索、智能算法等多个领域的内容紧密相关，研究学者根据各自的研 究背景和已有的知识出发，对文本挖掘的认识也有他们不同的理解。例如，有些 研究学者从数据挖掘角度出发，认为文本挖掘就是利用挖掘技术自动地从文本集 中发现隐含模式的过程1 2 j 1 3 】；而另一些学者则认为文本挖掘所处理的对象是非结构 化的文本不同于传统的数据挖掘中的结构化数据，而将文本挖掘归入以信息检索、 自然语言理解等技术为基础的文本信息处理领域【4 】【5 1 。尽管不同研究学者对文本挖 掘的定义各不相同，但是现在得到比较认同的文本挖掘定义为：通过从文本数据 对象中发现满足用户需求的有某种意义的规则的处理过程，利用这些规则可以给 用户带来极大的方便，从而满足社会发展的要求【6 】。 通过上述的含义可以得知，文本分类、文本聚类、文本检索、文本摘要、文 本情感分析、文本趋势分析等等都可以看作是文本挖掘中的子任务。目前，文本 湖北工业大学硕士学位论文 挖掘领域的相关工作受到的广泛的关注和研究8 j 【9 j 【1 0 】【12 1 。本文的工作重点在文 本聚类问题的研究。 1 2 课题研究的意义 在国外，很多著名学者针对本国的文本语言的特点，对文本聚类技术做了非 常有价值的工作，有非常重要的应用价值，有的学者针对英文的特点结合关系规 则图来进行文本挖掘的处理，还有的学者提出了新的改进的聚类分析方法来提高 聚类的效果与质量，另外有的学者将统计学和概率论的知识与聚类相结合产生新 的方法，例如，d a n i e lb o l e 提出的a r i - p 和p d d p 算法。文本聚类应用的一个例 子【1 3 】【1 4 】是通过对顾客的e m a i l 进行分析来找出不同用户群的购物特点，为商业决 策提供支持。 虽然在中国对中文文本聚类技术的研究还处于初级阶段，但在广大学者的积 极努力下已经取得了比较有意义的成果，例如有的学者在中文分词方面做了大量 的研究，在著作中提出了高效的分词方法，还有的学者为高效率的获取早现实世 界中的有重要价值的规则信息提出了新的聚类分析方法，另外，有的学者将自然 界中的规律结合具体的文本预处理阶段的特征选择方法演变出新的方法来进行特 征选取操作。 文本聚类的产生和应用虽然还处于初级阶段，但对它的研究却越来越具有当 代特色，但现在各个高校和科研机构越来越重视对它的研究，文本聚类技术在未 来必将在人们的日常生活中扮演重要的角色。 1 3w e b 文本聚类面对的挑战 聚类【1 5 】【1 6 1 由于它是没有先验知识的方法，所以相对其它方法来说比较困难。 它所面临的问题预先是不知道的，再加上基于w e b 的文本有其独有的特点，在以 它为对象进行聚类是就显得尤为困难。对它进行聚类时有以下几个方面需要进一 步注意： 处理网页的复杂性。 网页的结构相对比较复杂，为降低在后续处理工作当中的复杂性，需要预先 对网页的内容进行处理，提取出对后续工作有用的信息。 文本对象的高维性。 在文本预处理阶段，通过中文文本分词以后，一句话，一篇文章可能被处理 湖北工业大学硕士学位论文 成很多的词语，通过文本表示后，特征向量的维数会很高，这样就会给聚类处理 阶段带来很大的负担。 文本对象属性的稀疏性。 在文本特征选取阶段，通过从特征向量选取权重较大的特征项与其组成新的 特征向量以达到降维的目的，在这个过程中因为权重的选择通常只能提取一部分 特征项，这样就会导致其它大量特征项闲置的情况。 词的字面和潜在语义关系。 存在这样一种现象，描述同一个对象的名称可能有几个，假如在同一个文本 中出现这种情况就会造成关键信息的缺失，但若过高的抽象词语的意义也会出现 误差。 文本内容的多样性。 现在文本的内容越来越丰富，有的情况下，可能会出现同一个文本分别属于 多个类别的情况，就会给聚类处理带来较大难度。 w e b 聚类算法难度性。 由于网页有其自己的特性，与其它文本不同，因此将聚类应用于w e b 文本比 其它普通文本更有难度，通常的做法将w e b 文本转化成普通文本进行处理。 1 4 本文的主要内容结构 第一章绪论部分主要介绍了课题的研究背景与意义、国内外的研究现状和本 课题所面临的挑战，然后介绍本文的主要内容等。 第二章为相关概念的介绍，介绍了数据挖掘的特点和研究本课题所要用到的 相关概念，为以后章节的论述提供良好的理论基础。 第三章为w e b 文本挖掘技术，根据本文研究的方向，介绍了基于w e b 的中文 文本挖掘的基本步骤，然后阐述了中文w e b 文本预处理采用的相关技术。 第四章介绍了一种基于遗传策略的特征选取方法。本方法从初始特征向量中 选择出最具有代表性的特征项，得到原特征向量的最优特征子向量作为特征选取 的结果。有效的对特征向量实现了降维，从而也就缓解了聚类计算复杂度过高的 情况，在某种程度上保证了聚类的质量。然后经过实验表明，这个方法是可行的 并且是有效的。 第五章介绍了各种常见的聚类算法及其优缺点，重点分析了经典的k m e a n s 算法，然后提出了一种自适应策略与带孤立点检测相结合的改进k m e a n s ( w l p d ) 算法。它不但解决了原算法对孤立点敏感的缺点，又在相当程度上避免聚类的结 果陷入局部最优的局面，通过实验证明了改进后的方法比原方法算法有更好的聚 湖北工业大学硕士学位论文 类质量和效果。 第六章进行了总结与展望，并对本文所做的工作做了阐述。 4 湖北工业大学硕士学位论文 2 1 数据挖掘 2 1 1 数据挖掘特点 第2 章相关概念 数据挖掘的通常定义【1 7 】是：根据用户的需求从海量的样本集合中寻找出有现 实意义和重要价值的知识。 从数据库的数据对象集合中通过数据挖掘技术可以抽取出有意义的知识、规 则或有价值的信息，并从多个方面来进行显示，使数据库成为一个可利用的有价 值的资源，为决策提供信息支持。现在数据挖掘被应用于许多领域，在电子商务 中，影响购买者购买商品的因素很多，凭借以往的方法和经验不能得知影响购买 的主要或关键因素，而利用数据挖掘发现顾客的购买行为，找出影响顾客购买的 关键因素，从而提高经济效益。数据挖掘具有以下特剧1 8 】： ( 1 ) 数据处理的规模庞大，经常达到g b 、t b 数量级，有时甚至更大。 ( 2 ) 决策者通常提出的查询为随机查询，一般情况下不能形成准确的查询要 求。而利用数据挖掘进行挖掘的信息规则是不能被预知的。 ( 3 ) 基于大样本的统计规律是数据挖掘中发现规则的重要方法之一，抽取出来 的规则不一定适应于所有的对象，当它达到某一设定的临界值时就是有效的，所 以利用数据挖掘可发现大量规则。 ( 4 ) 数据挖掘发现、监管的潜在规则是动态的。 2 1 2 数据挖掘常用方法 ( 1 ) 聚类 本文主要针对的是文本聚类，则文本聚类是在没有预知的情况下，根据文本的 信息内容，将文本集中的文本分成若干类，满足类中的文本间的相似度尽可能小， 而不同类中，文本之间的相似度尽可能大。 ( 2 ) 分类 分类是指根据预先确定的主题类别，为文本对象集合中的每一个文本对象都确 定一个类别的过程。分类是一个典型的机器学习问题，分类的目的是让机器掌握 分类规则，该规则能够将w e b 文本映射到一个或者多个已经存在的主题类中，这 样虽小但容易浏览文件对象，而且可以使用户能快速、准确的查找自己需要的文 湖北工业大学硕士学位论文 本对象。具有代表性的有朴素贝叶斯算法【1 9 j 、支持向量机【2 0 j 【2 1 】等。 ( 3 ) 关联规则 关联分析是指从文本集合中找出不同文本对象间的相互联系。常用的算法是著 名的a p r i o r i 算法【2 2 】。 2 2w e b 文本挖掘 2 2 1 w e b 挖掘 w e b 挖掘是抽象出与因特网相关的数据，它不仅可以是网页包含的数据，而且 也可以是w e b 操作本身产生的各类数据。根据w e b 挖掘的特点，可分为以下几类： ( 1 ) 网页文本包含的信息。 ( 2 ) 网页内部的相关结构，其中包括h t m l 或者x m l 标记。 ( 3 ) 网页与网页之间的嵌套链接结构。 ( 4 ) 记录访问网页的数据。 ( 5 ) 用户的访问信息，访问人数统计的信息、注册信息和从相关的控件中获取 的信息。 w e b 挖掘通常可分为三类，如图2 1 所示：w e b 内容挖掘、w e b 结构挖掘和 w e b 使用记录挖掘。 图2 1w e b 挖掘的分类 2 2 2 文本挖掘简介 文本挖掘【2 3 】是指从文本数据对象中挖掘出潜在的、事先未能预知的、对用 6 湖北工业大学硕士学位论文 户有意义的知识或规则的过程。一般挖掘的任务包括关键字搜索、聚类和分类以 及关联规则等。对文本来说，文本最复杂的一个问题就是把自然语言处理技术应 用到文本挖掘中，结合文本内容来发现文本中隐含的语义。 而文本聚类技术是一种最重要的文本挖掘技术之一。文本聚类指的是将文本集 中的文本对象划分到更小的簇中，并且要求同一簇中的文本之间的相似性尽可能 的大，而簇与簇之间的文本相似性尽可能的小。 2 3 数据标准化 通常情况下，不恰当的度量单位的选用也会给聚类分析的结果带来严重的影 响，比如将体积由“立方米改成“立方毫米 ，面积由“平方米 改成“平方公 里”，这样得到的聚类质量有较大的差别。本文在这里方法如下： 最小最大标准化处理。设变量x 的最大值和最小值分别为i n x 。和i n n 。则最 d , 最大标准化可以通过计算一下公式 w m n ，、 w = l ( 甩一l r l x x 一玎一r n n 工) + n i l l n j ( 2 - s ) m x x 一瑚x 来将x 的值w 映射nx e i 盲q n _ m x ，nm n 中的w 。 2 4 文本表示 通常情况下计算机不能像人类一样具有智能，它不能正确理解文本内容。那 么如何将文本表示成计算机可以识别和处理的模式在文本挖掘中为经常遇到的重 要问题之一。为将文本表示成文本挖掘任务能识别和处理的模式，文本表示处理 的首步就是转化文本，对文本信息进行特征化表示。文本表示具体指在文本预处 理阶段，文本在经过分词后将其表示成特征向量的过程。向量空间模型的详细的 内容将在下面的章节进行介绍。 2 4 1 向量空间模型 在本世纪六十年代末到七十年代初期，向量空间模型是由s a l t o n 等提出来的。 向量空间模型通常用来将文本对象表示成特征向量，通过它表示后就可以为后续 的机器学习方法识别和处理，可以在一定程度上降低学习方法的复杂度，是一种 非常有效的表示方法，它最大的优点是可以容易地计算特征向量对应文本对象之 间的相似性。 7 湖北工业大学硕士学位论文 2 4 2 特征抽取 通常来说文本对象的特征数量很多，因而用来表示文本对象的特征向量的维 数也很高，常常可达到几万维有时候可达到几十万维，这样就会对后续的聚类处 理带来很大的压力，因此需要进行降维处理。可以起到两个作用：一方面可以提 高程序的效率，从而节约运行时间，降低程序的时间复杂度；另一方面存在这么 多个特征就会对文本聚类产生不同的影响，所以为提高聚类效果，应删除对聚类 效果影响程度不大的那些特征项，从而挑选出可以提高聚类效果的特征集。在文 本预处理阶段中对特征向量进行降维操作，通过利用遗传学的知识推演出一种遗 传策略来进行特征选择和抽取操作。 2 5 本章小结 本章重点介绍数据挖掘的基本知识和特点，以及在文本聚类的整个过程中所 需要用到的专业术语和知识，为以后章节的进一步研究提供了必要的预备理论知 识。 湖北工业大学硕士学位论文 第3 章w e b 文本挖掘技术 3 1w e b 文本挖掘的过程 w e b 文本挖掘包括w e b 文本去噪、文本分词、文本特征表示、文本特征选取、 学习与知识模式提取，知识模式评价、知识模型输出7 个阶段【2 5 】f 2 6 】。通常将前五 个阶段称为文本挖掘的预处理阶段。本文将在后续的章节中将重点讨论特征选取 与聚类阶段的重要工作。 首先从因特网上下载一定量的w e b 文本，选取待处理和分析的文本数据集合， 从文本样本集的内容中删掉和文本去噪不需要的标记，然后再将除标记以后的文 本转换成的文本文档格式的文本存放起来，为以后工作做准备；对待处理的文本 进行分词处理，因为本文的研究对象是中文文本，又因为中文的基本单元是字并 不是词语，它不像英文的词语那样，词语与词语之间有间隔，所以还得将中文文 本切分成特征词条；然后还要对挖掘的文本对象的进行特征表示的工作，文本的 特征表示是指在文本分词后将文本对象进行特征表示的过程，简而言之，就是以 结构化形式来描述文本对象的信息，而量化后特征项就可以成为文本对象的中间 表示形式。在通常情况下，由于文本数据对象有非结构化的特点，在文本对象集 合表示的过程中，初始特征向量的维数会非常高，这种高维的特性就会在很大程 度上增加各种学习方法的运行时间，并且经常得到和分词处理后的特征子集没有 关联的结果，所以这就需要对其进行降维的操作，因而特征向量的选取工作就成 为文本挖掘处理过程中的一个非常重要的阶段。特征选取就是从初始特征集中选 取一个真子集，在这个过程中原始向量空间的性质并不会发生变化，它根据用户 需求和规则通过原始向量空间选择具有代表性的特征项，来建立新的低维空间； 在文本特征向量维数完成降维后，确定其使用的范围，明确应用所要达到的效果， 便可以利用各种机器学习的方法( 比如文本分类、关联规则或聚类等方法) 以产生面 向用户应用需求的某种知识规则。最后对提取后的应用规则来进行质量评估，模 型质量评估常用的指标有聚类正确率、查准率与查全率，查准率与查全率的几何平 均数、信息估值、兴趣性。通过利用上述指标进行评价后，如果得到的知识规则 达到用户的需求标准则提取并输出知识模型，否则的话，返回到前面步骤对影响 模型质量的环节研究分析，将其更改后再进行前面所述的步骤继续运行，直到产 生达到用户的标准。 9 湖北工业大学硕士学位论文 基于w e b 的文本挖掘的步骤可以用图表示如下： 图3 1 文本挖掘的流程 3 2w e b 文本预处理技术 3 2 1w e b 文本去噪 w e b 中的文本内容含有h t m l 标记，有些情况下还包含某些形式的超文本。 所以需要先进行去噪处理，即提取出重要的文本信息，删除其中的噪音信息，过 滤掉其中与文本内容不相关的信息，然后转化为t x t 格式的纯文本。在去除h t m l 标记时，通常用h t m l 标记来作依据以设置网页相关内容的权重。 因为h t m l 标记含有t a g ，所以常常利用t a g 去除h t m l 标记。通常有以下几 种情况： ( 1 ) 中的标题，不但高度概括了网页的主要信息，而且还是网页 中信息的核心说明，所以这个标题有关键的参考作用。 ( 2 ) 关键字标题基本都是专业术语和词汇。 ( 3 ) 页面描述标题，它简明扼要的说明网页的基本信息。相对于正文中词汇来 讲，页面描述中的词汇与类区分的关系更重要。 3 2 2 中文文本分词 在一般情况下，在进行文本分词的时候选用文本中具有广泛代表性的词语来标 示文本信息，在这个过程当中，选取词语的代表性的程度在某种程度上面就表明 特征选取的好坏，而进一步进行分词为其中非常关键的步骤之一，因为它影响到 后续学习方法能够有效处理特征向量集合。 比较中文和英文两种语言，显然两者在形式上是不相同的。写英文时，词之间 1 0 湖北工业大学硕士学位论文 是用空格隔开的，词问界限清晰可见；而中文是字的组合序列，词与词之问并没 有间隔符号，通常词又作为汉语中最小的能够独立使用的语法单位，所以经过分 词处理后，计算机才能进行后续操作与处理。 另外，虽然汉语词汇各不相同，但它们的含义丰富多彩，文本分词的作用并不 是考察词语的形状，而是进行词语的分词处理操作，因为它不想英文词语之间有 空格来间隔，通过分词处理，文本中的词语就可以有间隔。所以通过分词操作， 将词语集合进行有序的切分，这样就可以为后续文本表示阶段的工作提供一个良 好的前提条件。 目前比较常用和实用联想回溯法、基于统计的分词【2 7 】【2 8 1 。本文采用基于词表 的分词一最大匹配( m m ) 法。最大匹配( m m ) 法基本过程如下： ( 1 ) 首先将文件指针指向最后一个字； ( 2 ) 从文件指针逆向抽取最大长度( 取6 ) 的字符串l ，如无词可取，则算法结束； ( 3 ) 在内存词典d i c t i o n a r y 中用二分法查找l 词尾的位置； ( 4 ) f o r ( i = 6 ；i 0 ；i 一) 从l 的词头部分逆向抽取字数为i 的字符串p ) 在词头结构链表中查找p ，如匹配成功，文件指针向文件首移动i + 1 个词， 转到( 2 ) ： ) ( 5 ) 匹配失败文件指针向文件首移动一个词，转n ( 2 ) 。 3 2 3 文本特征表示 文本表示的主要任务是将经过文本分词处理后的文本对象的信息集合用特征 向量的形式来表示，简而言之，就是建立文本对象与特征向量的对应关系，在文 本表示的过程当中，文本对象中的词语发挥这非常关键的作用，而文本表示操作 就是利用这些词语来进行表示的。 文本特征表示的模型常用的有：布尔逻辑模型，向量空间模型( v s m ) ，潜在语 义索引和概率模型掣2 9 】【3 0 】【3 l 】。向量空间模型是本文用的主要方法。 1 向量空间模型 向量空间模型的基本思想是使用词袋法【1 7 1 表示文本，它可以用一下几个名词来 解释：有特征项及其权重，相似度计算等。 ( 1 ) 特征项。例如文本可以表示为d m = d ( t 1 ，t 2 ，ae * t i ，et n ) ，其中第i 个特 征项用t i 表示。 ( 2 ) 权重用来表示特征项的重要程度。 ( 3 ) 利用v s m ，就可用特征向量来表示文本对象，对应于特征向量空间的点。 例如文本k 表示为：v ( 尼) = ( t 1 ，w l ；t f ，w f ；t 。，w 。) 。 湖北工业大学硕士学位论文 ( 4 ) 相似度。相似度常用来衡量文本对象之间的相似程度，它在某种程度影响 这聚类结果的划分，而基于距离相似度方法为常用的计算相似度的方法。 2 特征项权重 特征向量的权重如前描述的那样用来表示特征项对应词语的重要程度，如果 权重越高则表明其被选中用来组成特征向量的几率越大，权重越小表明重要程度 较低，被选中的几率也越低。常用的权重生成方法有w i d f 函数、t f i d f , i t c 权重 等【3 2 】【3 3 】。公式如下： ( 瑚) = 丝丝些些竺坠( 3 - 1 ) ”4 z , 。a o c ( t , d ) x l n ( n n t + o 0 1 ) 2 其中，词t 在文本d 中的权重和词频分别用w ( t ，d ) 、f ( t ，d ) 来表示。 3 相似度计算 基于距离相似度方法为常用的计算相似度的方法。通过利用相似度计算来考 察文本对象之间的相似度程度，可以找出具有相似属性的对象样本，从而划分成 若干类。作为划分文本对象类别的重要指标之一，它在聚类分析处理阶段起着至 关重要的作用。常用的距离函数有：欧式距离、曼哈顿距离、明氏距离、马氏距 离等【蚓【3 5 】【3 6 】。本文采用欧式距离方法计算如下： d ( m ，) = ( lm ，一mj 2 ) 1 ，2 ( 3 2 ) 3 2 4 文本特征选取 在文本特征表示阶段，特征向量通常用来表示文本对象。但由于组成特征向 量的特征项常常是文本对象中的词语，经过词语的自动处理并被表示成特征向量 后，就经常存在着特征向量的维数过高的问题。对于大部分机器学习算法来说都 难以承受特征向量的维数太高的问题。所以人们希望在不影响学习方法效果的前 提下找到能够降低特征向量空间的方法，这就是特征选取算法。本文将在下一章 中重点介绍。 文本特征选取指在文本集中通过选取最有代表性的特征项来代表原来的特征 向量【3 7 】。 评估函数法是现在常用的特征选取方法( 本文不采用这种方法，因此只做简单 介绍) ，它通过对特征数据集中的每个特征项进行独立的评估然后再给出一个评估 分数，结合特征项的权值进行排序，通常采用的评估方法有：信息增益选取预定 数目的最佳特征作为特征子集、互信息，x 统计、期望交叉熵和几率比等f 3 8 3 9 】f 4 0 1 1 4 。 本文选用的方法是基于遗传算法的特征选取方法，将在下一章详细介绍。 湖北工业大学硕士学位论文 3 3 本章小结 本章介绍了w e b 文本挖掘的步骤以及本文后续过程中要用到的技术，描述了 中文w e b 文本挖掘的预处理的基本步骤，并着重介绍了本文在w e b 文本去噪阶段、 中文文本分词阶段、文本特征表示阶段和文本特征选取阶段将会采用的相关技术。 湖北工业大学硕士学位论文 第4 章基于遗传策略的特征选取方法 关于预处理阶段的特征选取方法【4 2 】的相关内容比较少。本章将详细介绍这 种特征选取方法的重要内容。 4 1 遗传算法 通过借鉴自然生物界的选择规律和遗传原理的随机搜索算法就是经常提到的 遗传算法( g a ) ，它是通过模拟达尔文的遗传学原理中生物进化学说提出的模型 】。遗传算法的思想源于生物遗传学和适者生存的自然规律，它以群体中的所有 个体为对象，并利用随机化技术对被编码的参数空间进行高效全局的搜索，生成 初始种群，再进行适应度的计算与评估，然后进行选择、交叉和变异等遗传算法 的遗传操作，经过这一系列的过程( 选择、交叉和变异) ，产生的新一代个体不同 于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是 更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断 的重复，每个个体被评价，计算出适应度，两个个体交叉，然后变异，产生第三 代。如此往复，直到满足终止条件为止。做为一种随机化的搜索算法，遗传算法 不不仅具有简单通用、鲁棒性强、适于并行处理等特点而且还具有高效、实用等 显著特点，因此它在各个领域得到了广泛应用，并逐渐成为越来越重要的智能算 法之，一。 4 2 基于遗传策略的特征选取方法 4 2 1 基本思想 聚类分析前，文本集合需要经过文本预处理，在特征表示阶段，一般用特征 向量来表示文本对象。但因为文本中具有大量的词语，而文本中的词语常常作为 特征项而组成特征向量，通常情况下特征向量维数的高低通常与文本中词汇的数 量紧密相关，般说来，含有词汇数量大的文本对象经过特征表示后，形成的特 征向量的维度就会很高，反之，词汇数量小，特征向量的维度就会很低。在这种 情况下，聚类算法在遇到特征向量很高的时候，它的复杂度会很高。所以在本文 的研究过程中，特征选取阶段的任务就是利用已有的知识，结合特征选取的特点， 寻找一种对聚类分析算法影响较小的方法用以完成特征选取工作。而聚类是一种 1 4 湖北工业大学硕士学位论文 无教师监督的分析方法，因此在特征选取阶段并没有先验知识可用。本文中，组 成初始个体种群是通过从特征向量中选择部分特征项来完成的，然后再从中进化 出最佳的特征向量用来表示原特征向量，这样就可以完成特征选取阶段的任务。 4 2 2 算法的基本流程 图4 1 遗传算法流程图 湖北工业大学硕士学位论文 ( 1 ) 初始种群建立阶段 特征选取是为了得到经过降维处理的特征向量集合，在选取和降维的处理过 程中，需要借鉴遗传学的基本知识即特征向量集合与种群的编制方法。本文中采 用二进制编码【4 5 】的方法，而二进制编码位与原特征向量的特征项的选取情况相对 应。具体的编码方式如下： 对原特征向量v 和染色体r ；来说，为了建立两者的对应关系，有以下规则， 假如特征向量v 是n 维的，则r 。就转变为n 位的二进制数，染色体基因对应与r ； 中的每一位f 4 们。在染色体与特征向量的对应关系中，假如染色体中某个基因为为1 则意味着与其相对应的特征项被命中，假如为0 的话则表明与其相对应的特征项 没有被命中。具体的对应关系如下图所示。 图4 2 个体与特征向量对应图 在遗传算法中，初始种群的建立不得不通过原特征向量来随机产生的一个重 要原因就是因为没有先验知识。本文为了保证结果的客观性，通过采用随机选取 的方法来进行个体中基因位的选择。首先，设一个数，这个数比基因为相对应的 特征向量的维数要小，然后在与之相对应的染色体选这个数值的基因位并将它们 都取l 。为保证算法的全局最优，产生的初始种群的条件必须满足这样一个条件， 就是组成与初始种群相对应的的存在的特征项都进行计算，这样就实现了染色体 的基因位与特征向量中的特征项的全面的对应关系。当然有些情况下，会出现规 模过大的情况。出现这种情况的时候，就在种群生成的过程中可以选择某数量在 前面处理中没有建立关系的特征项。特殊情况下，可以强制设某染色体对应的特 征项的数量。最简单的一种方法，可以取某数值，表示在某个染色体内只可以对 应某数值的特征项。这样就可以有效的控制特征向量的维数。 1 6 湖北工业大学硕士学位论文 ( 2 ) 计算适应度阶段 适应度函数【4 6 】计算的选择在遗传算法中是很非常重要的，它在某种程度上会 对算法的运算趋势产生影响，严重的情况下，会对算法的运行结果产生负面的影 响。一般适应度函数通过目标函数来表示，在某个文本中，某个染色体的基因与 表示文本的特征向量中的特征项相对应，在这里词语就代表特征项。那么，好的 有代表性的词语可以基本体现某个文本的主要的信息，有些情况下可体现其它文 本的相关信息，这说明这两个文本之间有较好的相似度。那么适应度计算阶段的 主要工作就是利用适应度函数来衡量文本对象之间的适应度，在这个过程中主要 通过计算平均相似度来体现适应度，它们的求解趋势是一致的。所以有每个文本 对象r ；，它的平均相似度函数计算公式如下： 1 。誓 厂( f ) = t ( r j ，r ，) ( _ 4 - 1 ) ，i j - - i 在这里，本章的相似度计算采用欧式距离公式如下： = = = 一 t ( x ，d = n ( x ，聊= i 一z 2 ( 4 2 ) 这里，文本对象x ，y 的欧式距离用n ( x ，y ) 表示，其中x ；= q 。b ；。原特征向 量中第i 个特征项的权重用q 。表示，个体x 在第i 位的二进制值用b ；表示。n ( x ，y ) 值越大，x 与y 之间的相似度越小。特征向量的维数低就表明特征选取的效果好， 就可以为后续处理打下一个良好的基础。本文针对降维的幅度来引进一个考察函 数以此来考察特征选取工作的降维效果： 川) = 斟 ( 4 - 3 ) 在这里，与r ；对应的特征向量的维数用ir ；1 来表示，即取1 的二进制编码中的 位数与个体中基因位的取值相对应，特征项维数用iv l 来表示。在加入考察因子后， 最终的适应度函数为： 1 删= 而衰而 ( 4 - 4 ) 为保证前面分式得到有意义的结果，通常在分母加入常数九( 固定数值这里 取0 1 ) 。如果f ( i ) 值越高，说明个体的适应度就越好，表示个体被选中的几率也 就越大。 ( 3 ) 选择算子操作 本文所用的选择算子是带最优比例选择策略的方法，第一步就保存上代的染 色体，通过上代中染色体适用度的计算，将结果中数值较高的保存在一起，较低 湖北工业大学硕士学位论文 的保存在一起。然后根据概率的不同将另外的染色体中的基因也保存起来。通常 情况下，染色体的基因的适应度和与其相对应的概率数值成正比例关系。被选取 的概率大则说明染色体的适应度高，被选取的概率小的话则说明染色体的适应度 低。本文采用的概率公式为： p ( f ) = 盟 ( 4 5 ) f ( n ) 甩= 1 ( 4 ) 交叉算子操作 为产生新的染色体，通常两个染色体重组它们各自的一部分来完成，这个过 程被称作交叉操作。一般情况下，文本以5 0 的概率来进行双点交叉处理。在这个 过程中，重组随机生成的从第i 位开始到第j 位结束的基因位，通过这个操作就 完成了产生两个新染色体的任务。具体过程如下图所示。 三 二二工工二 1 i 囊交x jt 三工 二二 卫 图4 3 交叉操作 ( 5 ) 变异算子操作 这个运算是在交叉操作完成之后的基础上进行的，一般情况下；变异算子操作 首先对种群中所有个体以设定的概率判断是否进行变异，然后对进行变异的个体 随机选择变异位进行变异。本文使用变异概率p m = 1 2 对下代个体中的基因进行 变异操作。 ( 6 ) 算法的出口条件判别 本文遗传算法采用以下评判规则来作为迭代终止条件： 粥川= 警蒜产 t7 的条件下，y ，将成为孤立点。关于临 界值t7 计算公式如下： 丁= 口丁= t ( 5 - 2 ) ，- f = l 在上式( 5 6 ) 中，文本对象的总体平均相似度用t 来表示，它实