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

t 武汉科技大学 研究生学位论文创新性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研 究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的 工作外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：京砑袈 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位 的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定， 同意学校保留并向有关部门( 按照武汉科技大学关于研究生学位论文收录 工作的规定执行) 送交论文的复印件和电子版本，允许论文被查i nc h 借阅， 同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行 检索和对j b n 务。 论文作者签名：庭益 指导教师签名： 垒翌豳 日 一 、， j ， 4 i 一 _ r 武汉科技大学 硕士学位论文第1 页 摘要 文本聚类是数据挖掘和信息检索领域的一个重要研究方向。随着网络上堆积的数据同 益庞大，且大部分数据以文本形式存储，人们对从大量文本中获取信息的需求越来越高。 文本聚类方法具有无监督的学习能力，可由计算机自动进行，通过比较文本的相似性，发 现文本内在特征及分布规律，它既可对w e b 文档进行有效地组织，还可形成分类模板用来 指导w e b 文档分类，以便检索和阅读，所以对文本聚类技术的研究就显得尤为重要。近年 来，人们受自然界中蚂蚁堆积尸体等现象的启发，提出了基于蚁群的聚类算法( a n t c o l o n y t e x tc l u s t e ra l g o r i t h m ) 。蚁群聚类算法与文本聚类技术的结合形成了基于蚁群的文本聚类 算法，该算法具有良好的扩充性、并行计算和j 下反馈，不必预设聚类中心数目，实现自组 织聚类过程，具有健壮性、可视化等优点，但仍存在不足。 本文将禁忌算法的思想引进蚁群聚类算法中，提出了蚁群禁忌融合的文本聚类算法 a t i c a ( a n t t a b ut e x tc l u s t e r a l g o r i t h m ) 。在蚁群算法生成初始解后，禁忌搜索算法在初始 解的基础上进行局部搜索，这样既克服了蚁群算法易陷入局部最优的缺点，同时也克服了 禁忌搜索算法对初始解的依赖性，实现二者优势互补。实验结果表明，改进后的算法较基 于蚁群的文本聚类算法具有更高的准确率。 关键词：数据挖掘；文本聚类：蚁群算法；禁忌搜索算法 第1 i 页武汉科技大学 硕士学位论文 a b s t r a c t t e x tc l u s t e r i n gi sa ni m p o r t a n tr e s e a r c ho r i e n t a t i o ni nt h ef i e l do fd a t am i n i n ga n d i n f o r m a t i o nr e t r i e v a l w i t ht h ei n c r e a s eo fs t a c k e dd a t ao nn e t w o r k ，a n dm o r e o v e r , m o s to ft h e d a t as t o r e db ym e a n so ft e x tf o r m ，t h ed e m a n do fa c q u i r i n gi n f o r m a t i o nf r o ml a r g ea m o u n to f t e x t sb e c o m e sh i g h e ra n dh i g h e rf o r p e o p l e t e x tc l u s t e r i n gp o s s e s s e s t h ec a p a c i t yo f u n s u p e r v i s e dl e a r n i n g ，a n dc a nb ec o n d u c t e da u t o m a t i c a l l yb yc o m p u t e r b yc o m p a r i n gt h e s i m i l a r i t yo ft h et e x t ，t h ei n h e r e n tc h a r a c t e r i s t i c sa n dd i s t r i b u t i o np r i n c i p l e so ft e x t sc a n b ef o u n d ， t h en e x t s t e p i st oo r g a n i z et h ew e bd o c u m e n te f f e c t i v e l ya n df o r mc l a s s i f i c a t i o nm o d e lt o i n s t r u c tt h ec a t e g o r i z a t i o no fw e bd o c u m e n t ，a n ds oa st or e t r i e v ea n dr e a d h e n c e ，t h er e s e a r c h o nt e x tc l u s t e r i n gi s p a r t i c u l a r l yi m p o r t a n t i n r e c e n t y e a r s ，r e s e a r c h e r si n s p i r e db yt h e p h e n o m e n o no f a c c u m u l a t i o no fd e a db o d i e sb ya n t si nn a t u r e ，a n dp r o p o s e dc l u s t e r i n g a l g o r i t h mb a s e do na n tc o l o n y ( a n t c o l o n yt e x tc l u s t e ra l g o r i t h m ) t h ec o m b i n a t i o no f a n t c o l o n yc l u s t e r i n ga l g o r i t h ma n dt e x tc l u s t e r i n gt e c h n o l o g yp r o d u c e san e wa l g o r i t h mn a m e d a n t b a s e dt e x tc l u s t e r i n ga l g o r i t h m t h ep r o p o s e da l g o r i t h mh a se x c e l l e n te x t e n s i o na b i l i t y , p a r a l l e lc o m p u t a t i o n s ，a n dp o s i t i v ef e e d b a c k ，d on o tn e e dt op r e - s e tn u m b e ro fc l u s t e rc e n t e r s ， a c h i e v es e l f - o r g a n i z i n gc l u s t e r i n gp r o c e s s ，w i t hr o b u s t n e s s ，v i s u a l i z a t i o na n do t h e ra d v a n t a g e s ， a l t h o u g ht h e r es t i l le x i s ts o m ed i s a d v a n t a g e s t h ei d e ao ft h et a b us e r c ha l g o r i t h mt ot h ea n tc o l o n yc l u s t e r i n ga l g o r i t h mi si n t r o d u c e di n t h i sp a p e r , a n dt h ei n t e g r a t i o nt e x tc l u s t e r i n ga l g o r i t h mo fa n tc o l o n ya n dt a b ua l g o r i t h m a i t c a ( a n t - t a b ut e x tc l u s t e ra l g o r i t h m ) i sp r o p o s e d a f t e rt h ea n tc o l o n ya l g o r i t h mg e n e r a t e s i n i t i a ls o l u t i o n ，t h et a b us e a r c ha l g o r i t h mb a s e do nt h ei n i t i a ls o l u t i o nf o rl o c a ls e a r c h ，t h i sw i l l n o to n l yo v e r c o m et h ea n tc o l o n ya l g o r i t h mf e a t u r e se a s yt of a l li n t ol o c a lo p t i m u m ，b u ta l s o o v e r c o m et h et a b o os e a r c h a l g o r i t h md e p e n d e n t o nt h ei n i t i a ls o l u t i o n ，t oa c h i e v e c o m p l e m e n t a r ya d v a n t a g e s e x p e r i m e n t a lr e s u l t ss h o w t h a tt h ei m p r o v e da l g o r i t h mh a sah i g h e r a c c u r a c yt h a nt h et e x tc l u s t e r i n ga l g o r i t h mb a s e d o na n tc o l o n y k e y - w o r d s ：d a t am i n i n g ；t e x tc l u s t e r i n g ；a n tc o l o n ya l g o r i t h m ；t a b us e a r c ha l g o r i t h m 一 - ， f l 武汉科技大学硕士学位论文第1 i i 页 目录 摘重要1 a b s t r a c t i i 目录i i i 第一章绪论1 1 1 选题背景及意义1 1 2 国内外研究现状2 1 3 本文的主要工作及结构安排3 1 3 1 本文主要工作3 1 3 2 本文结构安排3 第二章文本聚类概述4 2 1 文本聚类的概念4 2 1 1 文本聚类的定义及意义4 2 1 2 聚类的典型要求4 2 2 文本聚类的过程5 2 3 文本表示6 2 3 1 向量空间模型7 2 3 2 其他文本表示方法。7 2 4 文本降维技术8 2 4 1 特征选取8 2 4 2 特征提取1 0 2 5 主要的聚类算法。1 1 2 5 1 基于划分的方法1 1 2 5 2 基于层次的方法1 2 2 5 3 基于密度的方法1 2 2 5 4 基于网格的方法1 3 2 5 5 基于模型的方法1 3 2 6 聚类质量的评价1 4 2 7 聚类算法存在的问题1 5 2 8 本章小结1 5 第三章蚁群聚类算法1 6 3 1 蚁群算法简介1 6 3 1 1 蚁群算法原理1 7 3 1 2 蚁群系统介绍1 7 第1 v 页武汉科技大学硕士学位论文 3 1 3 蚁群算法描述1 9 3 2 基于蚁群的聚类算法的优化2 0 3 2 1 基于蚁群行为特征的聚类2 0 3 2 2 多种群蚂蚁聚类2 1 3 2 3 混合的蚂蚁聚类算法。2 2 3 3 蚁群算法的优点2 2 3 4 本章小结2 3 第四章蚁群禁忌融合的文本聚类算法。2 4 4 1 基于蚁群的文本聚类算法( a t c a ) 2 4 4 1 1 算法a t c a 的基本思想2 4 4 1 2 算法a t c a 的描述2 5 4 2 禁忌搜索算法2 6 4 2 1 禁忌搜索基本思想2 7 4 2 2 禁忌搜索算法的流程2 7 4 3 蚁群算法与禁忌搜索相融合的文本聚类算法2 8 4 3 1 蚁群聚类算法的不足2 8 4 3 2 局部搜索策略的改进。2 8 4 3 3 改进算法的描述2 8 4 4 本章小结3 0 第五章实验与分析3 1 5 1 数据准备3 1 5 5 1 实验数据3 1 5 5 2 预处理3 2 5 2 算法设计的实现过程：3 4 5 3 文本挖掘3 6 5 4 结果分析与评价3 9 5 5 本章小结。4 2 第六章总结与展望4 3 6 1 工作总结4 3 6 2 展望4 3 参考文献4 4 致谢：4 8 附录a 攻读学位期间发表的论文4 9 武汉科技大学硕士学位论文第1 页 1 1 选题背景及意义 第一章绪论 随着网络的深入发展和企业信息化程度的提高，互联网上的资源呈爆炸式增长，数据 量越来越大1 1 ，引，传统的数据分析技术已经远不能满足现实需要，它迫切要求一种技术，能 快速智能的将待处理的数据转化为有用的信息和知识，达到为决策服务的目的。数据挖掘 1 3 l 正是为迎合这种需要而产生的用于开发信息资源的一种数据处理技术。 简单地说，数据挖掘是从大量数据信息中提取知识，它是一种从大量的、有噪声的、 不完全的、模糊的、随机的数据集中识别新颖的、有效的、潜在有用的，以及最终可理解 的模式的过程，也就是根据预定的目标，对大量的数据进行分析，揭示其中隐含的规律， 并进一步将其模型化的先进有效技术过程i l j 。它是一个多学科领域，从多个学科汲取营养， 包括数据库技术、信息检索、机器学习、人工智能、统计学、模式识别、神经网络、数据 可视化和高性能计算。 随着数据挖掘技术的不断深入研究，2 0 世纪9 0 年代，数据挖掘在大规模的结构化数 据上有了很好的应用，随后人们开始将其应用到庞大而繁复的文本上，从而帮助人们从文 字海洋中找到潜在的、有意义的信息。这种针对文本进行数据挖掘与知识描述、知识发现 的过程被统称为文本挖掘( t e x tm i n i n g ) 【2 j ，又称文本数据挖掘或文本知识发现，它是- n 交叉性学科，涉及数据挖掘、机器学习等多个领域。 文本聚类技术是文本挖掘的一个重要研究领域。通过文本聚类，能有效的管理文本， 同时，它也是文本挖掘的自身需要。聚类，是人类的一项基本认识活动，通过适当聚类， 事物才便于研究，事物的内部规律才可能为人类所掌握。从技术角度讲，聚类的目的就是 将数据空间中的数据点划分到不同的类中。它是在无监督的情况下根据一定的相似性或距 离计算函数自动的将数据集分成若干类。文本聚类技术的目的是得到一些文本簇，使得文 本之间具有最大的簇内相似性，同时具有最小的簇间相似性，它是一个将文本集分组的全 自动处理过程，是一种典型的无教师的机器学习问题。 随着文本聚类技术在信息检索、智能搜索引擎和文本分类器的构造等领域的广泛应 用，文本聚类的研究已经成为信息处理的一个前沿课题，有着广泛的应用前景和重要的研 究意义。 随着聚类技术的深入研究，人们受自然界中蚂蚁堆积尸体，分类蚂蚁幼体等现象的启 发，提出了一种基于蚁群的聚类算法，该算法通过个体与个体及个体与环境的交互作用， 实现自组织聚类。其优点在于不必预没聚类中心数目，实现了自组织聚类；另外，该算法 采用随机性启发策略，具有可视化和健壮性等特点。蚁群算法与文本聚类的结合尚处于初 期阶段，无论足算法本身，还是文本聚类技术，都还有很大的改进余地，因此，对此技术 的研究具有很大的意义。 第2 页武汉科技大学硕士学位论文 1 2 国内外研究现状 早在2 0 世纪6 0 年代，人们对聚类的研究就己开始，至今仍备受关注。聚类是指根据 “物以类聚”原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合 叫做簇，并且对每一个这样的簇进行描述的过程。进行聚类前并不知道将要划分成多少个 组，也不知道根据哪些空问区分规则来定义组。聚类技术f 蓬勃发展，它已成为数据挖掘 研究领域中一个非常活跃的研究课题。 把蚁群算法引入到聚类问题中，最早源于1 9 9 1 年d e n e u b o u r g 对真实蚂蚁群中蚁卵分 类行为进行观察之后提出的蚁卵分类模型i 引，该模型利用个体与个体及个体与环境间的交 互作用，实现自组织聚类，其过程可大致描述为：首先将数据对象随机投放在一个平面上， 然后每只蚂蚁随机的选择一个数据对象，根据该对象在局部区域的相似性而得到概率，决 定蚂蚁是否“拾起”、“移动”或者“放下”该对象。经过有限次的迭代，平面上的数据对 象按其相似性而聚集，最后得到聚类结果和聚类数目。 目前基于蚁群算法的聚类方法从原理上可以分为4 种【5 】：运用蚂蚁觅食的原理利用信 息素来实现聚类，利用蚂蚁自我聚集行为聚类、基于蚂蚁堆的形成原理实现数据聚类以及 运用蚁巢分类模型利用蚂蚁化学识别系统进行聚类。 1 9 9 4 年l u m e r 和f a i e t a 6 1 ，提出将数据对象之间相似度的度量引入到d e n e u b o u r g 分类 模型中，为蚂蚁增加了记忆功能，提出了l f 聚类算法，他们的思想很大程度上促进了蚁 群算法的发展。虽然l f 改进了算法的性能，但却增加了算法的复杂度。随后，h o e 等人 在l f 算法的基础上，将蚁群聚类算法应用于文本聚类分析1 7 1 。h o e 等人提出的算法中，对 群体相似度函数、拾起概率和放下概率的计算方法进行了简化，因此，其优势就在于算法 简洁高效。然而，他们的算法只是对小规模的文档集合进行了实验，且实验效果也只局限 于小集合的w e b 文档中，因此，对与大规模的文档聚类效果还不够理想。后来，n m o n m a r c h e 等人1 3 j 提出了a n t c l a s s 算法1 8 】，这是一种混合的聚类算法，交替使用蚁群聚类算法和 k - m e a n s 算法修正误差从而得到高质量的聚类，且使用了分类错误率来评估聚类质量。虽 然，a n t c l a s s 算法聚类效果好，且算法思路新颖，但其本质思想与当初d e n e u b o u r g 提出的 聚类模型的思想严重不同，以至于由a n t c l a s s 算法处理得到的结果不能与其他蚁群聚类算 法通用。 以上蚁群聚类算法所依据的都是d e n e u b o u r g 的蚁群行为模型。此外，n i c o l a sl a b r o c h e 也提出了一种新的基于蚂蚁化学识别系统的聚类模型a n t c l u s t 聚类模型以及后来的 a n t c l u s t 改进算澍9 。该模型中，聚类分两个阶段进行，前一阶段与基本的蚁群聚类模型 类似，后一阶段再次利用蚁群聚类模型对每个簇进行二次处理，减少了聚类结果中出现的 小簇，使结果更精确。然而，a n t c l u s t 聚类模型中，算法停止的标准是由迭代的次数决定 的，因此当算法停止后，仍然存在许多没有被归类的对象，导致算法最后产生了很多体积 很小的聚类。 在田内，吴斌等人对d e n e u b o u r g 分类模型进行简化之后，提出了c s i 聚类算法l l o 1 1 l ， 武汉科技大学 硕士学位论文第3 页 并将算法应用于w e b 文档聚类和c r m 的客户行为分析中。此外，北京理工大学也有专家 对蚁群聚类算法有深入研究f 1 2 】。 基于以上分析，可以看出，对于不同的问题，蚁群聚类算法的版本也不同，各自有各 自的优势。尽管算法经历几个版本的修改和完善，但仍有较大的改进空问。 1 3 本文的主要工作及结构安排 1 3 1 本文主要工作 本文的主要研究工作就是围绕基于蚁群的文本聚类算法展开的。具体如下： 1 ) 介绍文本聚类的步骤和关键技术； 2 ) 阐述主要的聚类算法，以及各类算法的优缺点； 3 l 详细介绍蚁群聚类算法及蚁群聚类算法的优点； 4 ) 通过对蚁群算法的研究，找出使用该算法用于文本聚类的不足之处，并进行改进， 提出相应的改进方法； 5 ) 将改进后的算法与蚁群聚类算法进行对比实验，计算聚类评价函数，证明改进后 的算法的优越性。 1 3 2 本文结构安排 本文分为六章，各章具体安排如下： 第一章绪论。简要介绍了文本聚类的研究背景和意义，分析了国内外在该领域的研 究现状，并介绍了本文的主要工作和结构安排。 第二章文本聚类概述。介绍了文本聚类的概念、步骤、文本聚类的关键技术、几种 主要的聚类算法，以及聚类质量的评估和聚类算法存在的问题。 第三章蚁群聚类算法。介绍了蚁群算法的基本概念、原理、算法描述，并重点介绍 了蚁群聚类模型及优化。 第四章蚁群禁忌融合的文本聚类算法。该章为本文的重点章节，集中介绍了本文所 做的主要工作。针对目前蚁群算法用于文本聚类的过程中所产生的问题，将 禁忌搜索算法的思想引入到蚁群算法中，提出了蚁群禁忌融合的文本聚类算 法，并对该算法的具体步骤进行了详细描述。 第五章实验与分析。对改进后的算法和蚁群算法进行对比实验，介绍了实验所采用 的数据集、具体的实验步骤，并对实验结果进行了分析与比较。 第六章总结与展望。对本文的工作进行了总结，概括了本文的工作创新点及不足之 处，并对下一步的工作做出了展望。 第4 页武汉科技大学硕士学位论文 2 1 文本聚类的概念 2 1 1 文本聚类的定义及意义 第二章文本聚类概述 文本聚类，是一种有效的文本挖掘方法，它既是文本挖掘中信息获取的一种技术，又 是一种文本处理过程。 现实生活中，众多领域都在不断产生海量数据，尤其是文本数据。如何从这些数据中 发掘有用的知识已成为一个日益迫切的问题。因此，对文本聚类的研究有极其重要的意义。 文本聚类是文本挖掘的自身需要。所谓的文本挖掘就是以文本数据作为数据挖掘的对 象，从大量的文本数据中挖掘出潜在的、事先未知的、对用户有用的知识的过程，而这个 过程中就包括文本预处理、文本分类、文本聚类、模式评估与表示等步骤。 文本聚类处理是文本有效管理的基础。在i n t e m e t 上对大量的文本信息进行分类聚类， 能够为人们提供一个清晰的搜索框架，方便人们寻找所需信息，目前，各种搜索引擎、数 字图书馆、电子商务等领域的研究者已经在信息分类和检索方面取得了令人可喜的成绩， 但仍有很大的发展空间。 文本聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤，其中比较典型 的例子是哥伦比亚大学开发的多文档自动文摘系统n e w s b l a s t e r 1 3 l ，它将新闻进行聚类处 理，并对同主题文档进行冗余消除、信息融合等处理，最后生成一篇简明扼要的摘要文档。 聚类技术还可以改善文本分类的结果，找出潜在的主题【1 4 j 。 利用聚类技术还可以完成文档集合的自动整理，如对个人邮件进行分类，对个人短信 息自动分类处理1 1 5 j 等。 2 1 2 聚类的典型要求 目前，聚类分析已经广泛地用于许多应用领域，包括图像处理、数据分析、模式识别、 市场研究等。然而，聚类是一个极富有挑战性的研究领域，它的潜在应用对聚类提出了各 自特殊的要求。数据挖掘对聚类的典型要求如下： 1 1 ) 可伸缩性 一般的聚类算法对于处理小数据集合( 小于几百个) 工作得很好，但对于包含有百万个 对象的大型数据集样本进行聚类可能会有些偏差，这要求聚类算法具备高度可伸缩性。 2 ) 发现任意形状的聚类 多数聚类算法都是基于欧几罩得或者曼哈顿距离度量束决定簇的，基于此类距离度量 的算法趋向于发现具自相近尺寸和密度的球状簇。然而，簇叮能足任意形状的，丌发能够 武汉科技大学硕士学位论文第5 页 发现任意形状的簇的算法是很有必要的。 3 1 处理不同类型的数据 在应用当中，我们可能需要聚类多种类型的数据，如序数的、分类标称的、二元的， 或者这些数据类型的混合，然而，许多算法设计只是用末聚类基于数值类型( 区间) 的数据， 因此，具备处理多种类型数据的能力是聚类的一大要求。 4 ) 对输入记录的次序不敏感和增量聚类 一些聚类算法对于输入数据的次序非常敏感，比如，对于给定的数据对象集合，若输 入对象的次序不同，则这些算法可能产生差别很大的聚类结果。或者，一些聚类算法不能 满足数据库的更新，也就是说，如果新插入一个数据，此类算法不能及时将该数据合并到 已有的聚类结构中，而是需要重新进行聚类。所以，开发对输入次序不敏感的算法和增量 聚类算法具有重要的意义。 5 ) 对于决定输入参数的领域知识需求最小 大多数聚类算法都要求用户在聚类分析时输入一定的参数，比如聚类结果的支持度、 置信度，或者期望的簇的数目等。聚类结果对于输入参数十分敏感。通常，输入参数是很 难确定的，尤其是对于包含高维对象的数据集来说更是如此，不仅给用户增加了负担，也 使得聚类质量难以保证。 6 ) 处理带噪声数据的能力 现实世界中，绝大多数数据库都包含了离群点、未知、缺失或者错误的数据，但一些 聚类算法对于这类数据敏感，可能导致聚类质量不高。所以，开发能处理带噪声数据的聚 类算法就显得非常必要了。 乃可解释性和可用性 如果一个聚类需要与特定的语义解释或应用相联系，那么用户希望聚类结果是可解 释、可理解和可用的。 2 2 文本聚类的过程 文本聚类作为文本挖掘技术的一个重要组成部分，它主要是依据聚类假设：同类的文 档相似度较大，非同类的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不 需要训练过程、不需要预先对文档手工标注类别，因此具有较高的灵活性和自动化处理能 力。文本聚类的过程如图2 1 所示。 第6 页武汉科技大学硕士学位论文 图2 1 文本聚类的过程 1 ) 数据准备 针对待挖掘的目标，收集和整理原始文档集，即对文档数据集进行预处理，将数据集 表示成聚类算法能处理的由文本特征向量组成的结构化文本形式。 2 1 算法设计 聚类算法有很多种，但是没有一个通用的方法能解决所有的聚类问题，所以要根据具 体要解决的问题的特色结合各聚类算法的特点，来选择和设计具体的聚类算法。 3 ) 文本挖掘 使用设计好的算法对数据集进行知识的提取。即输入特征矩阵，经过运算后得到一个 聚类的划分。 4 1 结果评价 对聚类结果进行评价，将挖掘得到的结果与测试集的人工分类结果进行对比分析。常 用的评价指标是查全率、查准率和f l 值，后面会详细讲到。 2 3 文本表示 大部分数据挖掘的研究主要是针对结构化数据，如关系的、事务的和数据仓库数据。 而事实上，可获取的大部分信息都存储在文本数据库中，由来自各种数据源的大量文档组 成。这种存放在文本数据库中的数据是半结构化的数据，它们既不是完全的非结构化，也 不是完全结构化。比如，文档中可能包含如标题、作者、出版日期、类别等结构化的字段， 也可能包含如摘要、内容等非结构化的文本数据。 计算机不具有人类的智能，不能像人一样对文字信息产生认识和了解，所以在进行聚 类前，应将非数值的文本表示成计算机能理解的文本表示模型。文本的表示，既要方便计 算机的处理，也要包含足够的信息以准确反应文本的内容。 用于表示文本的基本单位通常称为文本的特征或特征项，特征项必需具备以下特性： 1 ) 特征项要能够确实标识文本内容； 2 ) 特征项具有将目标文本与其他文本桐区分的能力 武汉科技大学硕士学位论文第7 页 3 ) 特征项的个数不能太多 4 ) 特征项分离要比较容易实现。 在建立模型之前要对文本的特征进行选择和抽取，这个过程称为文本预处理过程1 1 引。 文本的表示过程【1 7 1 ，就是把一个无结构的原始文本转化为结构化的计算机可以识别处理的 信息的过程，即对文本进行科学的抽象，建立对应的数学模型来代替文本。 2 3 1 向量空间模型 向量空间模型v s m 1 8 】，是最常用的相似度计算模型，在自然语言处理中有着广泛的 应用，它产生于2 0 世纪6 0 年代后期。v s m 涉及到的基本概念有： 文档( d o c u m e n t ) ：通常是文档中具有一定规模的片段，从句子到篇章，都可以看成是 一个文档。 项、特征集( t e r m , f e a t u r et e r m ) ：特征项是v s m 中不可分的语言单元，可以是字、词、 短语等。一个文档内容被看成是所有特征项的集合，表示为d o c u m e n t = d ( t l , t 2 ，t m ) ， 其中f ( k ) 是特征项，1s ksn 。 项的权重( t e r mw e i g h t ) ：对于含有n 个特征项的文档d ( t l , t 2 ，t a r ) ，每一个特征都依 据一定的原理被赋予一个权重w ( k ) ，表示它们在文档中的重要程度。通常特征词条的权 值由词条对于文档在文档集中被检索到的贡献度来决定，并与其成正比。这样，一个文档 d 可用它含有的特征项及其特征项对应的权重来表示，d = d ( t l , w l ；t 2 ，w 2 ；t n ，w n ) ，其 中“k ) 就是特征项，( k ) 的权重， 1sksn 。 一个文档在上述约定下可以看出是n 维空问中的一个向量，这就是向量空问模型，它 有两个特点：一是各个特征项互异，二是各个特征项无先后顺序关系，即不考虑文档的内 部结构。这样，r ( k ) ，k “) ，就是一个n 维坐标系，w ( k ) 就是坐标值，一个文本就是 这个n 维空间的一个向量。 向量空间模型的优点在于，将文档集用词条及其权重集合的向量表示，从而把文本聚 类问题转化为空间聚类问题，易于操作和计算。在此基础上，若引入一些成熟的统计方法， 能在更大程度上挖掘文本中隐藏的信息。如主成分分析【1 9 , 2 0 l 、小波变换【2 1 j 、奇异值分解【2 2 , 2 3 l 等。但它也存在一些不足，比如关于特征选取和权重标准等没有统一的理论基础、特征词 之间是相互独立的，而实际上，自然语言中词与词问存在同义、近义或从属等关系，这样 就忽略了特征之问的语义相关性和特征之间的序关系。因此，有许多改进的技术1 2 4 , 2 5 j ，以 获取深层潜藏的语义结构。 2 3 2 其他文本表示方法 l s i 是一种隐性语义检索的算法，在大规模文本集合中，通过引入概念空川，宋解决 同义 词、多义词的i u j 题。其原理是，考察词所在的上下文的棚似性，那么所有 现在与其 第8 页武汉科技大学硕士学位论文 相似的上下文中的词，就被认为在用法或含义上相似，在概念空间中也相互接近。l s i 的 优点是能够挖掘潜在语义，同时能降低特征空问的维数，缺点是表示效率较低。 概率模型1 2 6 l 是信息检索领域发展的比较成熟的模型，在很多应用中都取得了很好的效 果。它是基于这样一种理论：给定一个用户的查询串和集合中的文档，概率模型来估计用 户查询串与文档的相关概率，该模型假设这种概率仅仅由查询串和文档决定，但这种假设 存在缺陷，因为它没有明确给出如何确定相关度的概率。概率模型的长处是，文档可以根 据它们相关概率的递减顺序来计算秩( r a n k ) 。 布尔空间模型z7 】是一种比较简单的检索模型，在传统的信息检索中有广泛的应用。布 尔空间模型是基于集合论和布尔代数的，其原理如下，首先把文本用布尔表达式进行标识， 然后把用户输入的检索式与被检索的文档进行逻辑比较。因此，布尔空间模型也可以说是 一种基于关键词的匹配的模型。在此模型中，文档d 表示为如下形式： 。也以，。 ，舢，= f ：，嚣鬻埘特蹶、 布尔模型的优点在于简单，但由于它仅仅利用特征项在文本中是否出现来表示文本特 征向量，所以不能准确表示文本，也不能准确区分不同特征项在文本关联性程度上的差异。 2 4 文本降维技术 在文本聚类任务中，高维数据空间的处理一直是一个关键问题。文档集中的单词、短 语通常多达上万个，甚至十几万个，如果直接用向量空间模型表示，势必导致如下问题： 1 ) 计算复杂度太高，严重影响文本聚类算法的效率和聚类速度； 2 ) 产生高维空间中的稀疏样本问题，即“维数灾难”，影响聚类效果。 因此，在文本聚类前进行降维处理是非常必要的。在将高维空间转化为低维空间的过 程中，一方面要尽可能多的保留原始数据集中的信息，另一方面要能有效地将原始数据集 中的噪声数据滤除。 降维技术，也称维数约减，即在不影响聚类质量的前提下，对聚类空间进行维度削减。 通过降维，达到降低计算复杂度，提高聚类速度和效率的目的。目前，用的比较多的降维 技术是特征选择( f e a t u r es e l e c t i o n ) 和特征提取( f e a t u r ee x t r a c t i o n ) 两类。 2 4 1 特征选取 特征选择，又称独立评估法，即从一组特征中挑选出一些最有效的特征以达到降低特 征空间维数的目的。特征选择的基本思想是，构造一个评估函数，对原始特征集的每个特 征项进行评估，并对每个特征项打分，这样每个特征项都获得了一个评估值，又称为权值， 然后依据权值的大小对所有特征项排序，提取预定数目的最优特征项作为提取结果的特征 子集1 2 引。显然，影响特征选择效果的关键凶素是评估函数的质量。 目自，常用的文本特征选择方法丰要有信息增6 一, t ( i n f o r m a t i o ng a i n ，i g ) 、文档频数 武汉科技大学 硕士学位论文第9 页 ( d o c u m e n tf r e q u e n t ，d f ) 、互信，包, ( m u t u a li n f o r m a t i o n ，m i ) 、z 2 统计量( 彳2s t a t i s t i c ) 等。 1 、信息增益( i n f o r m a t i o ng a i n ，i g ) 信息增益是通过统计某个特征项在文本中是否出现或者出现与不出现的次数来推算 此特征项代表的信息量，通常应用于机器学习领域中。 文本特征项n 对于类别c ，的信息增益，g ( n ，c ，) 的定义如下： g ( n c j ) _ - p ( n ) p ( np c j n ) l o g 等+ p ( - ) p ( c 瘌。g 等， ( 2 2 ) 其中，p ( n ) 表示特征项n 出现的概率，p ( c ，n ) 表示含有特征项n 的文本出现在类别 c ，中的概率，p ( c ，) 表示类别c ，出现的概率，p ( w ) 表示特征项n 不出现的概率，p ( c ，w ) 表示不存在特征项n 的文本出现在类别c 中的概率。 2 、文档频数( d o c u m e n tf r e q u e n t ，d f ) 文档频数的计算相对要简单些，是特征选择方法中最简单的一个，一般作为辅助方法 使用。文档频数，指的是含有某特征项的文本数。计算公式为： 即沪k 0 7 嚣， 他3 ， 其中，是特征项，d ，是文本，p ( ，d ，) 表示对应特征项是否在文本中出现。假设所 有训练文本的总数为n ，则d f 的表达式为： d f ( w j ) = 尸( w ，嘭) 。 ( 2 4 ) 文档频数的时间复杂度与文本数量成线性关系，所以很适合超大规模文本数据集的特 征选取。 3 、互信，皂, ( m u t u a li n f o r m a t i o n ，m i ) 互信息是统计学中的概念，是两个随机变量统计相关性的测度，通常用来衡量某个特 征词与类别之间的相关性。互信息的含义即，对于每一个特征项，它对各个类别的贡献为 该特征项在各个类别中出现的次数与在整个文本集中出现的次数的比值。 若文本特征项用n 表示，类别用q 表示，则n 与q 的互信息m i ( n ，c j ) 定义为： m i ( n , c ：j ) = l o g 篙， ( 2 5 ) p ( n c j ) 表示特征项n 在类别q 中出现的概率，计算公式如下： 1 + 琴m ( n ，d i ) p ( n c j ) = 骨丌一 ( 2 6 ) lvl + 罗罗m ( n d ) _ 一_ ， 其中，i d i 表示类别c j 的训练集文本数，m ( n ，d ；) 表示特征项n 在d ，中的词频，i v i 为 第1 0 页武汉科技大学硕士学位论文 i v l 吲 该类的总的特征项数，薹薹m ( n 。，d ；) 表示该类所有特征项的词频和。 p ( n ) 表示特征项n 出现的频率，即特征项出现次数与所有训练文本数的比值，其计算 公式如下： 1 + m ( n ，d t ) p ( n ) = 暴r iv i + 薹善m ( n s , d i ) 其中，i d i 表示训练集文本数，l v i 表示训练集总的特征项数， 集中所有特征项的词颇和。 ( 2 7 ) l v ll 型 茎善m ( n 。，d t ) 表示训练 4 、z 2 统计量( z 2s t a t i s t i c ) z 2 统计量是一种常见的统计量，与互信息类似，也能检验两个变量之间的独立性。假 设给出文本特征项n 和类q ，要检验这两个变量之间是独立无关还是具有显著依赖关系。 对于类别q 和文本特征项n 的z 2 统计量定义如下： 以= 型端蒜铲 8 ， 其中，p ( n ，c ，) 表示文本中含有特征项n 且属于类q 的概率，p ( n ，c ，) 表示文本中没 有特征项n 且不属于类q 的概率，p ( n ，c ，) 表示文本中含有特征项n 但不属于类q 的概 率，p ( n , c j ) 表示文本中没有特征项n 但属于类q 的概率，p ( n ) 表示特征项n 出现的概 率，p ( n ) 表示特征项n 不出现的概率，尸( c ，) 表示类c j 出现的概率，尸( c ，) 表示类q 不 出现的概率。 2 4 2 特征提取 在文本信息中，通常会出现近义词、一词多义、双关、歧义等情况，导致特征集出现 冗余，无法准确的表示文本含义，特征提取能很好的解决这一难题。 特征提取【2 9 j 实际上是一种数学