（应用数学专业论文）无尺度图k中心点聚类算法研究.pdf

河南大学研究生硕士学位论文第1 页 摘要 文本聚类在文本挖掘和知识发现中起着很重要的作用。这种理论和方法可以 对文本进行有效的管理和组织，可以对信息检索的结果进行改善，提供导航浏览 机制，发现相似的文本等。因此，文本聚类已经成为重要的研究方向和研究课题。 目前多数文本聚类算法都是以向量空间模型( v s m ) 为基础。这种文本表示 方法非常简单，但却引发了高维稀疏的问题。它还无法解决文本数据所特有的两 个语义问题：近义词和多义词。而且，传统的聚类算法对于任意形状的聚类显得 “束手无策，尤其是样本数据不为“凸 时，算法陷入“局部 最优。最后，对 于存在“孤立点数据，影响传统数据挖掘的效果。所有这些问题都极大干扰了 文本聚类算法的效率和准确性，使文本聚类的性能下降。尽管人们提出了通过特 征提取的降维方法，表示文本特征时更多加入词频和词性等语义信息来解决上述 问题，但是，这些方法都有自身的缺点，仅仅能非常有限的提高文本聚类的性能。 本文为了解决上述的问题，( 1 ) 提出了一种无尺度图k 中心点聚类算法，不 仅解决传统聚类算法高维稀疏问题，孤立点问题，算法的伸缩性较差的问题，而 且，从根本解决了传统聚类算法对于样本不为“凸时，算法陷入“局部修最优 的问题。( 2 ) 引进知网进行文本间语义相似度计算，利用概念集合表示文本模型， 对概念集合进行义原扩展，使用集合相似度的比较方法，比较文本的义原集合， 从某种程度上解决了文本聚类中的语义问题：近义词和多义词。( 3 ) 最后，通过 实验验证该算法比传统聚类算法有更好的效果。 关键字：文本聚类；语义相似度；概念集合；聚类算法；知网；集合相似度 第1 i 页河南大学研究生硕士学位论文 a bs t r a c t t e x tc l u s t e r i n gp l a y sa l li m p o r t a n tr o l ei nt e x tm i n i n ga n dk n o w l e d g ed i s c o v e r y s y s t e m s t h et h e o r ya n dm e t h o dc a nm a n a g ea n do r g a n i z et e x t ；i tc a ni m p r o v et h er e s u l t o fq u e r i e s ；p r o v i d ei n t u i t i v en a v i g a t i o na n db r o w s i n gm e c h a n i s m s ；a n df i n ds i m i l a r t e x t s s ot e x tc l u s t e r i n gh a v eb e e na ni m p o r t a n tr e s e a r c hd i r e c t i o na n dr e s e a r c ht o p i c s a tp r e s e n t ，m o s to ft e x tc l u s t e r i n ga l g o r i t h mr e p r e s e n tt e x to rd o c u m e n tu s i n g v e c t o rs p a c em o d e l t h i sr e p r e s e n t a t i o ni sv e r ys i m p l e ，b u tr a i s e so n es e v e r ep r o b l e m ： t h eh i g hd i m e n s i o n a l i t yo ft h ef e a t u r e sp a c ea n dt h ei n h e r e n td a t as p a r s e l y i na d d i t i o n , t h i sr e p r e s e n t a t i o na l s oc a n ts o l v et e x td a t a sp o l y s e m yp r o b l e ma n ds y n o n y mp r o b l e m t r a d i t i o n a lt e x tc l u s t e r i n ga l g o r i t h m sf o rc l u s t e r i n ga r b i t r a r ys h a p e sa p p e a r ”h e l p l e s s ”， w h e ns a m p l es p a c ei sn o tc o n v e x ，t h ea l g o r i t h mp e r f o r m a n c eo na ”l o c a l ”o p t i m i z a t i o n , t h ee x i s t e n c e o f l ! o u n i e r d a t ai m p a c t so nt h ee f f e c t i v e n e s so ft r a d i t i o n a lt e x tc l u s t e r i n g a l lt h e s ep r o b l e m si n t e r f e r ew i t hc l a s s i f i c a t i o no rc l u s t e r i n gl e a r n i n gp r o c e s s e sg r e a t l y a n dm a k et h e i rp e r f o r m a n c e sb ed r a m a t i c a l l yd r o p p e d t h em a i nt e c h n o l o g i e st os o l v e t h ep r o b l e ma r e d i m e n s i o n a l i t yr e d u c t i o n , t oa d dw o r df r e q u e n c ya n dp a r to fs p e e c h s u c ha ss e m a n t i ci n f o r m a t i o nw h e nr e p r e s e n t i n gt e x tf e a t u r e s ，b u tt h e s em e t h o d sh a v e t h e i ro w nd e f e c t s ，s oi ti m p r o v e st h eq u a l i t yo fc l u s t e r i n gal i t t l e t t os o l v et h ep r o b l e m sm e n t i o n e d ，( 1 ) t h es c a l ef r e eg r a p hk - m e d o i d s c l u s t e r a l g o r i t h m n o to n l ys o l v et h ep r o b l e m so ft h eh i g hd i m e n s i o n a l i t yo ft h ef e a t u r e sp a c e a n dt h ei n h e r e n td a t as p a r s e l y , t h e ”o u t l i e r ”d a t a ，t h es c a l a b i l i t y , b u ta l s oc h a n g et h e s i t u a t i o no fa l g o r i t h mp e r f o r m a n c i n go na ”l o c a l ”o p t i m i z a t i o n ，w h e ns a m p l es p a c ei s n o tc o n v e x ( 2 ) t h i st e x tp r o p o s e dan e wm e t h o df o rt e x tc l u s t e r i n gb a s e do ns e m a n t i c s i m i l a r i t yb yu s i n gh o w n e t , r e p r e s e n t st e x t o rd o c u m e n tu s i n gc o n c e p ts e tm o d e l ， s e m e m ee x p a n d i n go fc o n c e p t ，c a l c u l a t es e ts i m i l a r i t yb e t w e e ns e m e m es e t ，t h em e t h o d s o l v e ss e m a n t i cp r o b l e mt os o m ee x t e n t ：p o l y s e m yp r o b l e ma n ds y n o n y mp r o b l e m ， ( 3 ) a tl a s t , t h er e s u l t ss h o w e dt h a tt h es c a l ef r e eg r a p hk - m e d o i d sc l u s t e ra l g o r i t h m p r o d u c e db e t t e re f f e c tt h a nt r a d i t i o n a lt e x tc l u s t e ra l g o r i t h m k e y w o r d s ：t e x tc l u s t e r i n g ；s e m a n t i cs i m i l a r i t y ；c o n c e p ts e t ；c l u s t e r i n ga l g o r i t h m ； h o w n e t ；s e ts i m i l a r i t y 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学住申请。本人郑重声明：所呈交酌学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构番勺学位或证书而 使用过酌材料。与我一同工作酌同事对本研究所儆的任何贡献均已在论文中作 了明确旮勺说明并表示了谢意。 学位申请人( 学位论文作者) 釜名：垒垄! 兰! 幻6 罗半月，旦 关于学位论文著作权使用授权书 本人经河南大学审核批准援予硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论交( 氟质文 本和电子文本) 泓供公众检素、查阅。本人授权河南大学出于宣扬、展览学校 学术发展争进行学术交流等目的，可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 擘住获得者( 学位论文作者) 釜名： 2 0d 学位论文指导教师釜名： 哺多切 2 。口一月 7 日 河南大学研究生硕士学位论文第1 页 第1 章绪论 在现实世界中，文本数据种类繁多( 如电子书籍、新闻文章、邮件消息、互联 网页面等) ，数据量也不断膨胀，对文档的自动分类成为文本挖掘的重要工作将大 量的电子文档行自动分类组织，能够更好的对文档进行检索和分析，对文本数据 的管理至关重要。 文本聚类是一种无监督的学习技术，利用相似特性将组文本对象进行自动 归类。所处理的数据对象，与结构化数据挖掘对象有所不同，主要是一些非结构 化或半结构化的文本数据，例如：文本文件、e m a i l 电子邮件、h t m l 超文本文件 等。这些数据有一些突出特征，高维稀疏性，存在着一些“孤立点”，某些样本数 据不为“凸等特点，因此，发现和研究一种高效，合适的方法如何处理这些大 量，无结构的海量数据是一项重要任务，而文本聚类的方法正是为了满足人们的 需要而产生。 1 1 文本聚类的研究背景 网络的迅速发展使得网络的信息量急剧的膨胀，目前很难精确估量总的信息 量。如此繁多的信息，如何找到需要的信息已经成为一个迫在眉睫的问题，可以 r 说在浩如烟海的信息世界中，准确找到需要的信息犹如大海捞针，以至于“信息 宝库变成了“信息垃圾 。例如，百度搜索引擎对用户输入关键字的反应是列举 出所有与该关键字相匹配的网页，但是，不同的网页尽管包含相同的关键字，但 却可能表达不同的主题，比如，在百度中输入关键字“挖掘 ，搜索的结果大约有 2 0 ，0 0 0 ，0 0 0 多个网页，其中包含有挖掘机信息的网页，有数据挖掘的网页，也有一 些含有关键字“挖掘的文学作品的相关网页。而且还有一些内容重复的冗余信 息页面。这种主题杂乱的搜索结果和冗余的信息页面给用户找到自己感兴趣的信 息带来了很多的不方便。截止到2 0 0 8 年，我国的网民达1 5 亿，网络用户的增多 第2 页河南大学研究生硕士学位论文 带来了网络活动日益频繁，用户的个人信息，比如e - m a i l ，电子文档，所浏览的 网页等也飞速增长。以电子邮件为例，每天在网络上流动的邮件信息量将达到 p ( 1 0 ) b 的规模。如果把这么多的邮件放在一起，没有进行良好的组织和管理，那 么从中寻找一个e _ m a i l 信息将变的极其困难。 无论是网络信息，企业信息还是个人信息，其信息的主要载体是文本，随着 网络的飞速发展，网络的文本也在增加，因此迫切的需要一种能自动将海量数据 转化为有用的信息和知识的技术来实现各种信息相关的服务，而这些技术中最为 重要的一个就是文本聚类。 文本聚类在文本挖掘和知识发现中起着很重要的作用。这种理论和方法可以 对文本进行有效的管理和组织，可以对信息检索的结果进行改善，提供导航浏览 机制，发现相似的文本等。因此，文本聚类已经成为重要的研究方向和研究课题。 1 2 国内外研究现状 文本挖掘就是从大量的，无规则的数据集中发现潜在的模式，趋势，规则等 知识。传统的文本挖掘方法很多，例如文本结构分析、文本摘要、文本分类、文 本聚类、文本关联分析等。文献 1 】通过建立文本的逻辑结构，即文本结构树，对 文本结构进行分析。文本摘要就是从文档中抽取关键信息，对文档内容进行解释 和概括，文献【2 5 】通过语义层次分析和概念统计方法对英文进行自动文摘和自动 标引，文献【6 提出了使用中心文档表示文档集合，使用中心词汇表示文档的方法。 文本分类就是通过训练样本集合，得到文本分类的模型，通过模型拟合未知样本 数据，分类的算法主要有朴素向量空间模型【8 l ，决策树，贝叶斯分类( n a t i v e b a y e s ) i t ，支持向量机1 9 1 ，遗传算法，基于中心点的分类方法【1 0 1 ，粗糙集以及线性 最小二乘【l l 】，文献 1 2 1 的方法基于向量空间模型( v s m ) ，以“概念”为基础，考虑 词义的上下位关系，进而提到了分类的。文献 1 3 】对智能文本分类进行了研究。 文本聚类算法在国外的研究同样早在2 0 世纪6 0 年代，由于当时的应用环境 的限制，直到2 0 世纪9 0 年代，随着网络文本数据的“泛滥 ，才有了很大的“用 河南大学研究生硕士学位论文第3 页 武之地”，取得了重大的突破，并一度成为计算机研究的热点。国外对英文文本的 聚类进行了大量的研究，m o n t e s 等人提出了基于概念图的文本挖掘( t e x tm i n i n g w i t hc o n c e p t u a lg r a p h s ) ；d a n i e lb o l e y 提出的a r h p ( a s s o c i a t i o nr u l eh y p e r g r a p h p a r t i t i o n i n g ) 和p d d p ( p r i n c i p a ld i r e c t i o nd i v i s i v ep a r t i t i o n i n g ) 算法；印度理工学院的 b h o o p e s hc h o u d h a r y 和p u s h p a k 提出了基于语义聚类的方法等。现在文本聚类已经 成功地应用在信息检索领域，如：用聚类改善检索页面的重复问题。h e a r s t 等人 的研究已经证明了“聚类假设 ，查询相关的文档比较聚集1 1 4 1 。目前，文本聚类算 法，大致可以分成两种基本类型：层次凝聚法和平面划分法1 1 6 1 。文献【1 7 】提出了 将g - h a c 和k m e a n s 结合起来的b u c k s h o t 方法和f r a c t i o n a t i o n 方法。同时，国外 很多学者也提出了针对不同的领域的文本聚类算法，i l l h o iy o o 把语义文本挖掘应 用在生物医学资料挖掘方面【1 8 1 ，y u e n h s i e nt s e n g 等人利用文本数据挖掘技术进行 专利数据的分析等【1 9 1 。 ， 国内对于中文文本聚类的研究比较晚，目前，国内一部分学者，单位正从事 中文文本聚类算法的研究及其应用，例如，李家福用模糊聚类的算法对文本聚类 1 2 0 ，陈福集开发并实现了基于s o m 的w e b 文档层次聚类算法【2 1 1 ，从而帮助人们 快速进行文本信息导航，获取重要的知识。孙辉等提出了一种基于语句词条矩阵 的聚簇式动态增长聚类算法圈。周水庚等人在对d b s c a n 算法的改进方面，提出 了s d b s c a n l 2 3 1 ：孔锐等人提出了基于核的k 均值聚类洲。 尽管传统的文本聚类技术取得了很大的进步，但是，传统的文本聚类方法存 在很多问题。 一首先，一些文本聚类算法伸缩性不是很理想，当处理一些小样本文本数据时 候，算法的效率，分类精度比较好。但是，随着文本集数量的增加，聚类的效果 明显降低。 第二，传统的文本聚类方法很多，如k - m e a n s 算法，层次凝聚法等。这些算 法都是建立在凸球形的样本空间上，当样本空间不为凸时，算法就陷入“局部” 最优。 第4 页河南大学研究生硕士学位论文 第三，传统文档的向量表示方法基于“词袋 模型，去除一些停用词后，使 用所有的“词袋 表示文档向量，这可能导致几千维的向量表示文档，出现了高 维稀疏的问题，也即“维灾难”问题。 第四，在数据挖掘的过程中，存在着不符合数据模型的数据对象，这些数据 通常被看着是数据集中的噪声，也就是被称着“孤立点 ，他们的存在会影响数据 挖掘的精确度，对于传统的文本聚类会产生非常差的挖掘效果。 最后，大多数文本聚类不考虑特征词和特征短语间的语义联系，例如，在临 床医学上的词语，伤风，感冒，流感等这些同义次和多义词，尽管他们词语不同 的，但表达的语义却是相同的，这可能导致可能表达相同意思的文档，在关联度 上趋向为不同类的文档，因为文本意义的表达是多样化的，从而在文本的相似度 比较时，产生了很大的差异。事实上，这种问题本质上来自于传统上的文本聚类 方法或者算法并没有“理解 文档的意思，对于文本的同义词，多义词的问题就 “束手无策”。 1 3 本文的研究 在传统文本挖掘的方法不能很好处理海量文本信息的时候，需要对传统的文本 挖掘方法进行改进或者提高。针对上述问题，本文着重在聚类方法进行研究。聚类 分析是传统的数据挖掘的方法，其目的是根据样本的相似性对数据集进行合理的分 割，它不需要先验知识和假设，是一种无监督的学习。本文的主要贡献如下： 1 提出无尺度图k 中心点聚类算法。一些研究表明：大量的文本因相似度而 相互连接，相互连接的文本集构成一种文本网络，这种网络服从无尺度网络的特 征。本文提出一种无尺度图k 中心点聚类算法解决一些传统的文本聚类算法中的 一些问题，例如，当数据样本不为凸时，算法陷入“局部 最优。并且随着文本 数量的剧增，算法效率很差，伸缩性不是很好。另外，一些传统的文本聚类算法 处理高维数据和存在孤立点的样本数据能力很差。 2 本文采用知网得出概念的义原，然后计算文本义原的集合相似度，得出文 河南大学研究生硕士学位论文第5 页 本之间的相似度，进而引进文本的语义信息。通常，在比较文本相似度方面都是 基于向量空间模型，然后比较向量之间的余弦距离，在一定程度上割裂了特征词 与特征词之间的联系，很少考虑词语的语义关系，本方法一定程度上解决文本同 义词和近义词问题。 3 在以上理论研究的基础上，通过实验与传统的文本聚类算法进行比较。实 验结果表明：该算法效率较高，某种程度上解决了传统文本聚类的不足，算法无 论在聚类的评估标准上，分类的精度上都比传统的文本聚类有所提高。 1 4 论文大纲 本文共有六章，内容安排如下： 第一章是绪论。主要讨论文本聚类的研究背景，国内外研究现状和研究的不 足，然后提出本文的研究工作和创新点。 第二章介绍文本聚类的理论基础。首先讨论文本聚类的数学定义，文本聚类 的过程和模型，其中文本聚类的模型。我们重点介绍文本表示的几种模型，如向 量空间模型，词袋模型等，简单描述文本特征提取的方法，如文档频率d f ，信息 增益等。最后，给出文本聚类中几种距离度量的方法。 第三章是本文研究的重点之一。介绍基于知网的语义相似度计算。这一章首 先介绍知网的相关知识，定义了概念集合概念，用概念集合的模型表示文档，然 后利用知网对概念集合进行义原扩展，最后利用集合相似度的计算方法，计 算文本之间义原集合的相似度。 第四章是本文研究的核心内容。首先，介绍传统的、比较有代表性的、经典 的文本聚类算法，这些算法在伸缩性，高维数据，存在孤立点数据，以及不为凸 的样本处理上都存在某些不足。然后，重点讨论本文提出的无尺度图k 中心点聚 类算法，并对这种算法进行详细描述。 第五章通过实验与传统的文本聚类进行对比分析，实验结果表明本文算法无 论在效率上，还是可行性上都比传统的文本聚类算法更有提高和进步。 第6 页河南大学研究生硕士学位论文 第2 章文本聚类的相关理论 文本聚类处理的大都是一些非结构化的数据，这些非结构化的数据在计算机 里都必须采用一些特定的数学模型进行表示。任何文本数据在表示前都必须进行 一些预处理，预处理主要包括分词，停用词过滤，特征提取。现在的分词方法主 要有基于词库的分词算法和无词典的分词技术两种。通过停用词表法去除一些含 有很少语义信息的停用词。特征提取一方面降低特征的维数，另一方面减少影响 文本语义处理的语义信息，据统计，表达一篇文本的意义的关键部分都存在几十 个关键的特征中。通过文本的预处理后，每一个文本都被一些特征词所表示，特 征反应的就是文本的核心意义。最常用的文本表示方法是向量空间表示法，这种 方法尽管很简单，却引发了高维稀疏的问题，因为本文在下章所要论述的表示文 本相似度的方法，采用语义相似度的计算方法，采用该模型不利于语义的计算， 在本章的最后提出了一种新的文本表示方法一概念集合表示法。 2 1 文本聚类的概述 文本聚类在没有任何预知的信息的情况下，将文档集合分成为若干个簇，要求 同一簇内的文档内容的相似度尽可能地大，而不同簇间的相似度尽可能地小【2 6 】， 从而发现整个文档集合的整体分布特点。它与分类的不同就是，分类是一种有监 督的学习，需要样本分类的先验知识，而聚类是一种无监督的学习，通过对数据 文本的聚类，能发现文本集合的整体分布特点。 作为一种无监督的机器学习方法，聚类由于不需要训练过程，以及不需要预先 对文档手工标注类别，因此具有一定的灵活性和较高的自动处理能力，因此，成 为对文本信息进行有效组织，摘要和导航的重要手段，为越来越多的研究人员所 关注。 定义2 1 文本聚类：d = ud i 表示文本数据集ag 代表d 的一个子集，那 河南大学研究生硕士学位论文第7 页 么文本聚类的任务就是将d 分割成k 个子集，使其满足： d = uq 且c nc , 2 = o ( 2 1 ) j 1 j 上面公式是文本聚类的基本条件，文本聚类的实际意义就是聚类的结果使一个 簇中的文本在语义上近可能相似，而且不同簇间的文本在语义上尽可能的远或则 不同。 2 2 文本聚类的过程和模型 文本聚类的主要处理过程是对大量的文档集合的内容进行预处理，特征提取， 文本聚类等。下图2 1 给出了文本聚类的一般处理过程。 2 2 1 数据预处理 图2 1 文本聚类的流程图 文本数据的数据对象是半结构化的或非结构化的，并且文本内容是自然语言 表示的，对于现在的计算机难以“理解其真正的含义。文本特殊性使得传统的 数据挖掘方法不能直接进行使用，需要对文本进行预处理和特征表示，从而使文 本最终以结构化的形式出现，同时，文本的表示方法能够更准确代表文本，文本 相互闻更具区分性，且利于后面步骤的文本处理，如分类、聚类等。现有的文本 模型主要有：布尔模型【2 7 1 、向量空间模型【2 8 】、潜在语义索引模型【矧、概率模型 第8 页河南大学研究生硕士学位论文 例等。目前广泛使用的是向量空间模型m c t o rs p a c e m o d e l ) 。 预处理技术主要包括中文分词、除去停用词和特征降维。因为文本是一种无结 构的数据，而传统上计算机仅仅能处理结构化数据，把文本数据变成计算机能够 识别，处理的数据对于高效的文本处理是一个重要过程。因此，文本的特殊性使 得数据预处理技术在文本聚类中更加重要。 2 2 2 分词技术 文档进行特征提取前，首先，需要进行文本预处理，对于英文需进行词根 s t e m m i n g 处理，对于中文的差别比较大，对于中文而言，词与词之间没有固有的 间隔符( 空格) ，需要进行分词处理，其难度相对比较大。目前主要有基于词库的分 词算法和基于统计方法的分词算法两种，前者主要是利用词典库匹配的方法，后 者主要是基于语料库的经验方法。 基于词库的分词算法主要有正向最小匹配、正向最大匹配、逆向匹配及逐词 遍历匹配法等【3 1 1 。其算法特点：实现简单，分词效率高；但分词的正确性率不高， 分词的正确性很大程度上取决于所建的词库【3 2 】。文献【3 3 】提出了一种改进的算法， 该算法能显著提高分词效率，其效率优于传统的分词匹配方法，文献 3 4 】中采用了 基于词典的正向逐词遍历匹配法，其效果得到了提高。 基于统计的方法也就是无词典的分词技术，其基本思想是基于词频的统计， 文献 3 5 3 6 】中把文本中任意位置上相邻的两个字作为一个词进行出现频率统计， 出现频率越高，成为固定词的概率越大，其频率超过某个阈值时，将其作为词进 行索引，该算法对于未登录词【3 5 】【3 6 】提取具有很高效率。文献 3 7 】设计了一个基于 基于语料库的无词典分词的算法，能够比较准确，高效地切分出文本中的新词。 文献 3 8 基于层次隐马尔科夫模型，设计开发了“汉语词法分析系统 ，将分词、 词语排歧、未登录词的识别三个过程融合到一个相对统一的理论模型中，从而使 得分词的效率显著提高。 河南大学研究生硕士学位论文第9 页 2 2 3 特征提取 传统的向量空间模型中的特征维数高达数十万维，很多特征对于文本的聚类 未必全是必需的、有用的( 一般只选择2 5 的最佳特征作为分类依据) ，而且高 维的特征影响文本处理的效率，因此，特征提取具有重要的作用。特征提取的本 质是构造一个评价函数，评估每个特征对于表示文本的重要性，然后选取重要的 特征表示文本。常用的评估函数有文档频率、期望交叉熵( e x p e c t e dc r o s se n t r o p y ) 、 互信息( m u t u a lh a f o r m a t i o n ) 、信息增益( i n f o r m a t i o ng a i n ) 、文本证据权( t h ew e i g h t o fe v i d e n c ef o rt e x t ) 。 2 ，2 3 。1 文档频率d f ( d o c u m e n tf r e q u e n e y ) 文档频率的方法是基于统计的方法，很多文本挖掘的特征提取都用到该方法， 特征词文档频率是指在文档集中出现该特征词的文档总数。文档频率的特征提取 方法基于如下的前提：在一个文档中，一个特征词出现频率越高，说明对表达文 本的意义越重要，也即对于文本的分类越重要，把低于某个阈值的特征频率作为 低频词，它们几乎不包含任何类别信息，把该特征项从特征空间中移除，能够降 低特征维度，提高效率。 文档频率方法简单，效率高。缺点：低频词可能是表达文档意义的更有用信息， 而高频词也可能不含有任何有意义的信息。 2 2 3 2 信息增益lg ( in f o r m a t io ng ain ) 信息论中一个重要的概念：信息增益，它代表某个特征词的存在与否对类别 分类的影响，考虑某个特征词在文本中出现前后的信息熵之差。一个特征词的信 息增益值越大，说明对信息贡献越大，同时，对分类也越重要。信息增益在文本 挖掘中常常被用作特征项评价的标准，它是一个基于熵的评估理论，定义为某特 征在文档中出现前后的信息熵之差。通过训练数据样本，计算出每个文本中特征 词的信息增益量，然后，根据信息增益量的大小对特征进行排序，去除信息增益 第1 0 页河南大学研究生硕士学位论文 量小的特征，保留信息增益大的特征词用来表示文本。 定义2 2 信息增益评估函数： 粥( w ) = 喜p ( q ) l 0 9 2 ( 轰b ) 一p ( w ) 喜烈q l w ) 1 0 9 i 未丽一烈i ) 善烈q1 ) l 。颤云未面 q ) ：。表示样本分类的类集c ，w 为特征项，烈w ) 为特征词出现的概率，w 表 示特征词w 不出现，烈q ) 为f 类出现概率，p ( qlw ) 为特征项出现且属于第i 类的 条件概率。 信息增益方法的缺点在于它考虑了特征项未发生的情况，尤其是类分布和特 征项分布不平衡的情况下，绝大多数特征都不出现，此时信息增益值由不出现的 特征项所决定。因此，信息增益效果降低很快。 2 2 3 3 互信息m i ( m u t u al ln f o r m a tio n ) 互信息体现了特征词和类别的相关程度，被用来建立词关联统计模型的重要 标准，因此，互信息大多数情况下被用在相关语言统计模型中。 定义2 3 互信息评估函数： m i ( w , c ) = 喜? ( q ) l 0 9 2 丽p ( w 丽l c , ) w 表示特征词，c 表示类别，p ( w f q ) 定义为w 和c 的同现概率，p ( w ) 定义为w 出现的概率，p ( q ) 定义为第f 类值的出现概率。 互信息的缺点在于其值受词条的边缘概率的影响，如下式： 尥( 鹕c ) = l 0 9 2p ( w lc ) 一l 0 9 2p ( w ) ) 对于相等条件概率p ( w l c ) 的特征词，稀疏词比长见词的得分高，这对于频率相 差很大的特征词，得分不具有可比性，由此导致互信息评估函数放弃高频词而选 择稀疏特征词作为文本的特征。 2 2 3 4 x 2 统计c h l ( c h i - s q u a r e ，c h l ) 河南大学研究生硕士学位论文第1 1 页 。定义2 4 统计评估函数： x ：( w ，c ) = 坐塑型煎笙匕攻坚幽堕盟 、7 p ( w ) p ( w ) p 0 ) p ( c ) 上式中p 【w ，c ) 是指对于文本x ，特征词w 不存在其中，但是x 属于类c 中， 是训练集的势。如果，0 ，f ) 的值小，说明特征词w 对于类c 的独立程度就高，因 此，特征提取时，选择x 2 ( w ，c ) 值最大的特征项。 2 2 3 5 期望交叉熵e c e ( e x p e c t e dc r o s se n t r o p y ) 定义2 5 期望交叉熵评估函数： c r o s s e n t r o p y ( f 却( w ) p ( c i g 等 其中p ( c , 1 w ) 表示文档出现特征项w 时，文本属于岛概率，鹏) 表示类别出现 概率。如果词条和类别相关强度大，也就是p ( 0 1 w ) 值大，并且对应类别出现概率 小的话，则说明特征词对分类很重要，所得的函数值就大，因此，很可能被选中 作为特征项。交叉熵反映了文本类别的概率分布和在出现了某个特定词的条件卞 文本类别的概率分布之间的距离，属性词w 的交叉熵越大，对文本类别分布的影 响也越大。 - 2 2 3 6 文本证据权( t h ew e i g h to fe v i d e n c ef o rt e x t ) 文本证据权是一种比较新的评估函数，它的本质是衡量类的概率和给定特征 时，类的条件概率之间的差别。 定义2 6 文本证据权评估函数： w e ( w ) 叫喀p 坩c l il o g 裂篙篇l 上式中l o ( w ) y g 特征词w 出现概率，p 为第i 类值出现概率，p ( c j f w ) 为特征 词w 出现时属于第i 类的条件概率值。 第1 2 页河南大学研究生硕士学位论文 2 3 文本聚类中距离计算方法 对于文本聚类来说，相似度的定义是至关重要的。相似度一般定义为界于【0 ， 1 】之间的一个值。下面介绍几种常用的相似度的定义。其中比和面表示两个文本 的向量。 2 3 1min k o w s ki 距离 定义2 7m i n k o w s k i 距离： l ( d o ，吒) = ( h - t , ，。i 严 该公式几何上的标准度量单位。，当p = 2 的时候，由上式得到的是e u c l i d e a n 距 离。但是，从上式可以看到，m i n k o w s k i 距离不是界于 0 ，1 】之间的，这就需要一 个标准化的过程。在e u c l i d e a n 空间中，使用定义( 2 7 ) 来把距离d 和相似度s i m i l a r y 关联起来。 s i m i l a r y ：p 一扩 ( 2 1 ) 根据公式( 2 1 ) ，【0 ，1 】标准化的e u c l i d e a n 距离定义如下： s e ( 吃，吃) = p 也q i ( 2 2 ) 2 3 2c o sin e 距离 文本对象相似度最广泛的定义是c o s i n e 距离。c o s i n e 距离是两个文本对象表 示向量间夹角的余弦。 定义2 8c o s i n e 距离： c o s ( d e ，d b ) = 旒 其中，以么为标准向量点积，定义为屹，分母中的i d of 和i 吃1 分别表 河南大学研究生硕士学位论文第1 3 页 示两个向量的长度，定义为j 吃l = 瓜。 c o s i n e 距离的一个特性就是它不依赖于文本表示向量的长度，即它具有特性： c o s ( a d o ，吃) = c o s ( d , ，磊) ( 2 3 ) 这种特性使得包含有同样的词但是不同长度的文本被等同地看待，从而使 c o s i n e 距离得到了最广泛的应用。 2 。3 。3 p e a r s o n 距离 性。 在协同过滤中，相关性常常用来在已知的属性的一组相似对象中预测一个属 定义2 9p e a r s o n 距离： ，= 嬲+ 1 其中，d 表示d 上所有维的平均值。 2 3 4 扩展d a c c a r d 距离 二元j a c c a r d 系数是用来度量两个集合重叠的程度的标准，它是通过计算两个 文本对象的布尔向量中共现词的数目和非共现词的比例得到的。 定义2 1 0j a c c a r d 距离： 批“，= 锑剁 通过扩展二元j a c c a r d 系数到连续的或者离散的非负属性上，可以得到扩展 的j a c c a r d 距离如下： 定义2 1 1 扩展j a c c a r d 距离： ! i 元，吃) = 再云- _ 糯 当向量的属性都为布尔型时，扩展的j a c e a r d 相似度等同于二元j a c c a r d 相似度。 第1 4 页河南大学研究生硕士学位论文 另一种和j a c c a r d 距离密切相关的相似度定义是d i c e 系数，定义如下： s c ，= 孝 亿4 ， 2 3 5k ul ib a c k - l eibie r ( k l ) 距离 k l 距离即相对熵，用于比较两个分布的不同。如果把文本的向量表示看成 是两个分布，则可以用k l 距离来表示两个文本的相似度。当用于计算文本相似度 时，一般使用对称k l 距离，其定义如式： 定义2 12k u l l b a c k l e i b l e r ( 1 姐) 距离： 以) = ( ( p o i d o ) - 删。g 黜 2 4 特征表示 特征表示是指以某些特征项( 如词条或描述) 表示文档，文本挖掘也即对某些 重要的特征项进行处理，从而实现对于非结构化的文本处理。其实质是个非结 构化向结构化转换的处理步骤，也为后续的文本算法提供了一个精确的数学模型。 特征表示的构造过程就是挖掘模型的构造过程。特征表示模型很多，例如布尔逻 辑型、向量空间模型、概率型以及混合型等，下面我们主要讨论下向量空间模型， 布尔模型，概率模型。 2 4 1 向量空间模型 在v s m 模型中，把t , 匕，厶看成一个n 维的特征空间，w i 彻，耽仰w n 彻 为相应的特征对应的数值，因此，任意的文本被看成是维空间中一个规范化特 征矢量，其数学表达为：哟= p j ，w ，彻i ；t j ，w f 彻i i 岛，俐。其中w 彻通 常被定义为矗在d 中的出现频率研仰的函数，即 河南大学研究生硕士学位论文第1 5 页 w ( d ) = 砂够p ” ( 2 5 ) 常用的有布尔函数、平方根函数、对数函数、t f i d 函数等。 2 4 2 布尔模型 布尔模型是v s m 模型的一种简化形式。它被定义成二值映射函数 厂? ，_ 冯，元数据玉的值不再是权值，两是一个布尔值，文本表示的结果是0 - 1 向量，即： 一! ，= 黝 ( 2 6 )y 2 1 仍矿：d u 内 2 4 3 概率模型 概率检索模型有多种形式，常见的为第二概率检索模型，首先设定标引词的 概率值，一般是对检索作业重复若干次，每一次检索用户对检出文档进行相关性 判断。再利用这种反馈信息，根据每个词在相关文档集合和无关文档集合的分布 情况来计算它们的相关概率，将词的权值设计为： 铝黹。2 圳 其中p ，p7 分别表示某词在相关文档集和无关文档集中出现的概率。某一文 档的权值则是它所含的标引词权值之和。 定义2 1 3 文档d 与用户查询p 相关概率： 洲驯= i o g 删 其中m 和办分别为矿在相关文档和无关文档中的概率。上式中右边和式是对 所有出现在文档d 和查询q 中的词w 求和，即w d f l q 第1 6 页河南大学研究生硕士学位论文 2 5 概念集合表示法 向量空间模型是一种很简单的文本表示模型，但却存在高维稀疏的问题，而 且无法解决文本中近义词和多义词的问题。尽管很多研究者在降维和调整文本的 特征权重方面做了很大的改进，但是，解决问题的同时却带来了效率上的问题， 降维的代价一般都非常大。布尔模型实现简单，其优点是速度快。但布尔模型忽 略了元数据的文档频率，所以无法在匹配结果集中进行相关性大小排序。且逻辑 表达式过于严格，造成重要特征大量的遗漏。 二些基于语义相似度的文档聚类算法采用名词列表【3 9 】表示文本，因为任何文 本中实词最能表达文本的中心思想，而名词又是实词中最主要的部分。但是，这 种方法却忽略了名词的词频对文本相似度的影响，因此，大大降低了聚类的正确 性。为了解决名词的词频对聚类效果的影响，孙爽等提出了概念列表【钔】的表示方 法，概念列表的表示形式如一个三元组： d = ( w i a ，c ；) ，( w 2 , a c 2 ) 蕊c 0 ( 2 2 2 ) 其中，w ，文档中的特征词z 是w ，在文档中的出现频率，c ，是特征w ，所具有的名 词含义的个数，这种表示方法综合了词频信息，词性的语义信息，减少了计算相 似度时的时间复杂度，某种程度上提高了语义相似度计算的效果。 本文采用全新的思路来进行文本聚类，这就是利用语义相似度来作为文本间 相似性的度量，这也就需要一种更有利于语义相似度计算的文本表示法。于是本 文提出了一种新的文本表示法一概念集合表示法( c o n c e vs e t ) 。 概念集合的定义：通过对文档的分词，词性标注，过滤停用词等方法后，剩 下最能表达文本意义的特征词集合。 概念集合的数学定义： d = ( w 1 ，c 1 ) ，( w 2 ，乞) ( 心，巳) ) ( 2 2 3 ) 其中，w i 表示文本中的特征词，o 是特征w i 所具有的词性。本文使用的概念集 合的方法，一方面集合是一种动态的数据结构，为下一章用到对概念进行义原的 河南大学研究生硕士学位论文第1 7 页 扩展提供方便，随着概念义原增多，集合可以动态扩充内存。另一方面，本文引 进知网进行语义的义原扩展，对于一个文本特征，特征的词性对于语义信息 很重要，利用知网的工具，本文关键是对实词的义原扩展，忽略虚词的作用， 从某种程度上可以降低特征的维度，有利于文本的聚类。 2 6 本章小结 本章主要讨论了文本聚类的定义，文本聚类的模型和过程，以及文本聚类的预 处理过程中的分词，过滤停用词，特征提取的一些理论和方法，介绍了文本聚类 过程中的一些文本距离计算方法。最后，介绍了文本表示的常用模型，并且针对 本文的相似度比较的特点，提出了概念集合的文本表示模型。下一章，我们将介 绍利用知网强大的语义信息来进行文本的相似度计算，知网中的概念是由义原表 示，义