（计算机应用技术专业论文）支持向量机的神经网络中文文本聚类研究.pdf

摘要 随着信息技术的发展，以电子形式存在的文本信息已经成为人们 主要的信息来源。人们迫切需要能够快速、有效地发现资源和知识的 工具。近年来针对文本数据的文本聚类已逐渐成为人们研究的新课 题，已经引起了人们的广泛重视。但是国内中文文本聚类的研究还处 于初期阶段，还存在许多问题亟待解决。 本文首先对文本聚类的研究背景和国内外的研究现状进行了介 绍，并分析了数据挖掘的相关概念、主要的聚类分析算法以及支持向 量机理论。 其次，针对汉语自身的特点分析了中文文本聚类中所涉及到的关 键问题及技术，包括中文切词技术、中文文档特征表示：向量空间模 型( v s m ) 和特征降维的方法，并提出了广义特征降维的理念。 然后，结合自组织特征映射神经网络( s o m ) 和支持向量机理 论( s v m ) 给出了一种文本聚类算法一支持向量机的神经网络中文 文本聚类算法( s v m s o m ) ，阐述了算法原理，分析了算法的收敛 性并列出了算法步骤。 最后，根据上述研究，本文实现了s o m 和s v m s o m 算法，并 在此基础上，利用现实领域中提供的语料库对聚类效果进行了测试， 同时利用f 值、查准率和查全率对两种算法进行了对比实验，并通过 加入噪声数据测试了两者的鲁棒性。从实验结果来看后者可以提高聚 类效果并具有更好的鲁棒性。 关键词聚类分析，中文文本聚类，自组织特征映射，支持向量机 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , e l e c t r o n i ct e x t s h a v eb e c o m em o r ea n dm o r ep o p u l a ra ss o u r c eo fi n f o r m a t i o n p e o p l e n e e ds o m et o o l st of i n dr e s o u r c ea n dk n o w l e d g eu r g e n t l y t h ep r o c e s s i n g u p o nt e x t so f f e r s m u c hp o t e n t i a lf o rd e v e l o p m e n ti ns u c hf i e l d s a s i n f o r m a t i o nr e t r i e v a l ，e s p e c i a l l yi nt e x tc l u s t e r i n g b u tt h er e s e a r c ho f c h i n e s et e x tc l u s t e r i n gi sa ti t se a r l ys t a g e ，a n dt h e r ea r es t i l lm a n y p r o b l e m s t ob er e s o l v e d i nt h i sp a p e r , w ef i r s t l ym a k ea ni n t r o d u c t i o na b o u tt h er e s e a r c h b a c k g r o u n da n d s t a t eo ft e x tc l u s t e r i n g ，a f t e rw h i c ht h ec o n c e p t i o no fd a t a m i n i n g ，t h em a i na l g o r i t h mo fc l u s t e r i n ga n d t h et h e o r yo fs u p p o r tv e c t o r m a c h i n ea r ea n a l y z e d s e c o n d l y , w ea n a l y z e ds e v e r a lp i v o t a lt o p i c s a n dt e c h n o l o g yo n c h i n e s et e x tc l u s t e r i n gf o rm ec h a r a c t e r i s t i co fc h i n e s e ，i n c l u d e dt e x t s e p a r a t e d e x p r e s so f c h i n e s et e x t sf e a t u r e ( v e c t o rs p a c em o d e l ，v s m ) a n dt h et e c h n i q u eo fd i m e n s i o nr e d u c e d w ea sw e l la sp r o p o s e dab r o a d c o n c e p ta b o u t r e d u c eo ft h ed i m e n s i o n t h i r d l y , w ep r o p o s e dt h ea l g o r i t h mo fs u p p o r tv e c t o rm a c h i n e & s e l f - o r g a n i z i n gf e a t u r em a pf o rc h i n e s et e x t c l u s t e r i n g ( s v m - s o m ) ， c o m b i n i n gs e l f - o r g a n i z i n g f e a t u r em a p ( s o m ) a n ds u p p o r t v e c t o r m a c h i n e ( s v m ) a n dt h e nt h ep r i n c i p i u m ，c o n v e r g e n c ea n ds t e po f t h e s v m s o ma r ee l a b o r a t e d f i n a l l y , t h es o ma n ds v m s o ma l g o r i t h m a r ei m p l e m e n t e d m o r e o v e r , t h et e s t i n gd a t as e t s i nt h er e a ll i f ea r eu s e dt ot e s tt h e c l u s t e r i n ge f f e c t ，a f t e rw h i c hw ec o m p a r et h e s e t w oa l g o r i t h m sb y c o m p u t i n gt h ef - v a l u e ，p r e c i s i o na n d r e c a l lv a l u ew h i c hi sw i d e l yu s e di n t h ei n f o r m a t i o nr e t r i e v a lf i e l d a tl a s tt h er o b u s to ft h e ma r et e s t e db y a d d i n gn o i s ed a t a t h er e s u l t ss h o wt h a to u rm e t h o dc a l li m p r o v et h e i i e f f e c to fc l u s t e r i n ga n dm o r er o b u s t k e yw o r d s c l u s t e r i n g ，c h i n e s et e x tc l u s t e r i n g ，s e l f - o r g a n i z i n g f e a t u r em a p ，s u p p o r tv e c t o rm a c h i n e i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 日期：哗年上月趁日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：缢导师签名蝴日期：耸年上月丛日 硕士学位论文 第一章绪论 1 1 课题背景及意义 第一章绪论帚一早殖 下匕 我们正处在一个信息“大爆炸的时代，近年来，随着先进的计算机技术和 网络通信技术的发展，尤其是随着互联网的迅速普及，电子形式的信息飞速增长， 互联网已经成为人们不可或缺的重要信息来源。目前，互联网上资源的以指数级 的速度增长，其信息量无论是数量还是种类都达到了难以想象的程度，可以用“海 量 来形容。要从“海量 的信息里面获取所需要的信息就要花费大量的时间和 精力。因此，如何快速而有效的获取所期望的信息已经引起越来越多人的重视。 数据挖掘技术正是在这样的背景下发展起来的，数据挖掘( d a t am i n i n g ) ，又 称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) ，就是从大 量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。 简单的说，数据挖掘就是从大量数据中提取或“挖掘 知识。它是一门很广义的 交叉学科，汇聚了数据库、人工智能、机器学习、统计学、模式识别、可视化、 并行计算和神经网络等不同学科和领域，近年来取得了长足发展并引起广泛关 注。 信息以文字、图像、音频、视频等多种形式广泛存在，但大部分信息还是以 文本形式存在的，所以文本挖掘成为数据挖掘中很重要的一个分支。传统的信息 检索技术有很大的局限性，比如信息丢失、返回信息太多、信息无关等，已不适 应日益增加的大量文本数据处理的需要。在这个信息激增的年代，从浩如烟海的 信息中找出所期望的信息就必须进行文本挖掘，文本挖掘( t e x tm i n i n g ) 成为数据 挖掘一个很有前途的研究方向。文本挖掘是一项综合技术，涉及数据挖掘、自然 语言处理、计算机语言学、信息检索及分类、知识管理等多个领域。将获取的知 识应用于相关领域可以有效地改变相应系统的性能。 文本聚类是文本挖掘的研究内容之一，同时聚类分析涉及到许多研究领域， 包括数据挖掘、统计学、生物学以及机器学习等。聚类分析是数据挖掘领域的研 究热点之一，其基本思想是将数据对象分组成为多个类或簇，使得在同一个簇中 的对象具有较高的相似度，而不同簇的对象之间差别较大【l 】。目前聚类分析已应 用于许多方面，包括模式识别、数据压缩、图像处理、声音处理，以及市场分析 等等。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式， 以及数据属性之间有趣的相互关系。因此，文本聚类是一个将文本集分组的全自 硕士学位论文第一章绪论 动处理过程。每个组里的文本在一定方面互相接近。如果把文本的内容作为聚类 的基础，不同的组则与文本集不同的主题相对应。文本聚类是一个发现文本集包 含内容的方法【2 】。 现在人们可以很容易地从互联网、数字图书馆、新闻机构和公司内部网上获 得大量的文本文档。于是，人们对发展能够帮助用户有效地导航、总结和组织这 些文本信息技术兴趣越来越强。快速和高质量的文本聚类技术在实现这个目标过 程中扮演了重要的角色。通过将大量信息组织成少数有意义的簇，这种技术能够 提供导航一浏览机制，或者，通过聚类驱动的降维或权值调整来极大地改善检索 性能。同时文本聚类也是发现关联文档的有效手段，利用文本聚类可以改善搜索 引擎，将搜索结果自动聚类提供给用户优质的服务。著名的网站y a h o o 就是采 用类似的技术来自动生成文档的分类。因此，文本聚类研究成为当前数据挖掘的 一个重要课题，具有很广的应用范围和很高的应用价值。 1 2 文本聚类技术研究现状 作为一种无监督的机器学习方法，聚类技术已经成为对文本信息进行有效地 组织、摘要和导航的重要手段，为越来越多的研究人员所关注【3 】 4 】【5 1 。 1 2 1 国外文本聚类研究现状 国外在文本挖掘中的文本分类技术以及相关的信息抽取等领域进行了较为 深入的研究，取得了令人瞩目的研究成果，产生了一些可用的文本挖掘系统【6 】。 ( 1 ) 文档聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤。 其中比较典型的例子是哥伦比亚大学开发的多文档自动文摘系统n e w s b l a s t e 一7 1 。 n e w s b l a s t e r 将每天发生的重要新闻进行聚类处理，并对同主题文档进行冗余消 除、信息融合、文本生成等处理，从而生成一篇简明扼要的摘要文档。 ( 2 ) 对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息【8 1 。比 较典型的系统有v i v i s i m o ( h t t p ：w w w v i v i s i m o t o m ) 和i n f o n e t w a r e ( h t t p ：w w w i n f o n e t w a r e c o m ) 等。系统允许用户输入检索关键词，而后对检索到的文档进行聚 类处理，并输出各个不同类别的简要描述，从而可以缩小检索的范围，用户只需 关注比较感兴趣的主题。 ( 3 ) 对用户感兴趣的文档( 如用户浏览器c a c h e 中的网页) 进行聚类，从而发现 用户的兴趣模式并用于信息过滤和信息主动推荐等服务【9 】。 ( 4 ) 数字图书馆服务。通过s o m ( 自组织映射) 等方法，可以将高维空间的 文档向量拓扑保序地映射到二维空间，使得聚类结果可视化和便于理解，如 s o m l i b 1 0 系统。 2 硕士学位论文第一章绪论 ( 5 ) 文档集合的自动整理。如s c a t t e r g a t h e r ( 】是一个基于聚类的文档浏览系 统。而微软的j i r o n g w o n 等人则利用聚类技术对用户提出的查询记录进行聚类， 并利用结果更新搜索引擎网站的f a q 。 此外，国外在文本聚类方面还对特征项的选择进行了较深入的研究，取得了 很好的效果；对分类算法有着较完整的研究和比较；存在比较标准的语料库；有 较为规范的测试方法；已经开始研究未标记文本对文本分类系统的影响；逐渐将 文本分类技术应用到某些特定的信息服务中。 1 2 2 国内文本聚类研究现状 国外对英文文本聚类已经进行了大量的研究。与国外相比，国内对中文文本 聚类的研究和应用起步较晚，目前国内仅有少数单位从事中文文本聚类算法的研 究及其应用。中国科学院计算技术研究所智能信息处理开放重点实验室在国内率 先展开了对中文文本聚类研究。宫秀军和史忠植提出了基于b a y e s 潜在语义模型 的半监督文本挖掘【1 2 1 ；吴斌等人提出了一种基于群体智能的w e b 文档聚类算法。 另外，陈宁等人提出了基于模糊概念图的文档聚类算法；西安交通大学的宋擒豹 和沈钧毅提出了基于关联规则的w e b 文档聚类算法；合肥工业大学的陈福集、 杨善林提出了一种基于s o m 的中文w e b 文档层次聚类方法【1 4 】等。 但是，总的来说，在文本聚类方向上的研究相对落后，主要存在着以下一些 问题： ( 1 ) 缺少统一的中文语料库 不存在标准的用于文本分类的中文语料库，各个学者分头收集自己的训练文 本集，并在此基础上开展研究，因此，系统的性能可比性不强。同时，出于财力、 人力有限，中文语料库的规模普遍不大，其中最有代表性的是北京大学计算语言 学研究所的语料库。 ( 2 ) 向量空间模型的研究还不十分成熟 国内的学者，例如吴立德和黄置著也提出了如何选择特征项的问题，他们提 出可以使用字、词、概念作为特征项构建向量空间模型，并对以此为基础的文本 分类系统进行了初步的性能比较，但是在这方面的研究还没有深入的开展，尤其 是对于概念的定义不清楚，没有全面的比较和测试系统。另外，在特征项抽取算 法方面也缺少系统深入的研究成果。 ( 3 ) 测试标准不统一 在国内，由于缺少标准的用于分类的中文语料库，所以文本分类系统的性能 测试可比性较差，测试方法也比较简单，通常仅给出整个系统的准确率，很少分 析测试文档数量和质量对文本分类系统性能的影响。 ( 4 ) 文本分类技术与其他信息技术尚未很好结合 3 硕士学位论文第一章绪论 国内的文本分类系统主要应用于图书馆等专业信息处理机构，在信息服务领 域，除了与搜索引擎有所结合外，文本分类技术与其它信息技术还没有很好的结 合，还没有得到充分的应用。 总之，目前国内对文本挖掘技术，特别是文本分类技术已经进行了很多的研 究，也取得了不少的成果，但是仍然存在很多尚待解决的问题。 1 3 本文的主要工作 本文首先介绍了课题背景和国内外文本聚类的研究现状，阐述了数据挖掘的 相关概念和主要的聚类分析算法，分析了支持向量机的有关理论，包括最优分类 超平面、软间隔和核函数等，并总结了支持向量机的优点。 其次详细说明了中文文本聚类的关键技术，包括中文切词、中文文档表示、 特征降维和聚类结果有效性评价等，并提出了广义特征降维的理念：即基于文本 频度的选择方法、停用词处理、基于词频统计的方法和基于词权重的方法均属于 特征降维的范畴。 然后阐述了经典的自组织特征映射神经网络的网络模型、网络特性和网络学 习算法。结合支持向量机理论( s v m ) 和经典的自组织特征映射神经网络模型 ( s o m ) 给出了一种中文文本聚类算法一支持向量机的神经网络中文文本聚类算 法( s v m s o m ) ，从理论上说明了算法原理，分析了算法的收敛性并列出了算法 的详细步骤。 最后实现了s v m s o m 和经典s o m 算法，并将两种算法作了仿真对比实验， 实验结果表明：选择了合适的核函数的支持向量机的神经网络中文文本聚类算法 具有比经典s o m 神经网络算法更好的聚类效果和更强的鲁棒性。 1 4 本文的内容组织安排 第一章绪论。介绍了课题背景和意义，对国内外文本聚类的研究现状进行 了总结。 第二章文本聚类相关理论概述。分析了数据挖掘的相关概念、主要的聚类 分析算法以及支持向量机理论。 第三章数据预处理。详细分析了中文文本聚类的关键技术，并提出了广义 的特征降维的理念t 即基于文本频度的选择方法、停用词处理、基于词频统计的 方法和基于词权重的方法均属于特征降维的范畴。 第四章支持向量机的神经网络中文文本聚类算法。阐述了经典的s o m 神 经网络的网络模型、网络特性和网络学习算法。结合支持向量机理论和经典的 4 硕士学位论文第一章绪论 s o m 神经网络模型给出了一种中文文本聚类算法一支持向量机的神经网络中文 文本聚类算法( s v m s o m ) ，说明了算法原理，分析了算法的收敛性并列出了 算法的详细步骤。 第五章实验及结果分析。实现了s v m s o m 和经典s o m 算法，并对经典 s o m 神经网络算法和支持向量机的神经网络中文文本聚类算法( s v m s o m ) 在 中文文本聚类效果和鲁棒性方面作了仿真研究和对比实验。 第六章结束语。对全文进行了总结并展望了以后的工作方向。 5 硕士学位论文 第二章文本聚类相关理论概述 2 i 数据挖掘 第二章文本聚类相关理论概述 数据挖掘是一个处理过程，它是数据库、人工智能和数理统计技术的结合和 发展，它利用一种或多种计算机学习技术，从数据库中自动分析并提取知识。 2 1 1 数据挖掘定义和功能 数据挖掘( d a t am i n i n g ，d m ) 就是从大量不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程。提取的知识表示为概念( c o n c e p t s ) 、规贝j j ( r u l e s ) 、规律 ( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。数据挖掘是一个多学科交叉研究领域，它 融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、 信息检索、高性能计算以及数据可视化等最新技术的研究成果【l 5 1 。 数据挖掘的功能用于指定数据挖掘任务中要寻找的模式类型。数据挖掘主要 功能有：概念类描述、关联分析、分类分析和预测、聚类分析、孤立点分析、 演变分析。 ( 1 ) 概念类描述：特征化和区分 概念描述是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念 描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不 是同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的 共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 ( 2 ) 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量 的取值之间存在某种规律性，则称为关联。关联可分为简单关联、时序关联、因 果关联。关联分析的目的是从数据库中发现关联规则，这些关联规则展示了给定 数据集中数据项之间的潜在的联系。关联分析广泛应用于购物篮分析和事务数据 分析。 ( 2 ) 分类和预测 分类找出描述并区分数据类或概念的模型，以便能够使用模型预测类、标记 未知的类。例如，建立分类模型对银行贷款的安全风险进行分类。预测是构造和 使用模型评估无标号样本类，或评估给定的样本可能具有的属性值或值区间，预 测未来的数据趋势。例如，建立预测模型对商品的销售量、股票价格、产品合格 6 硕士学位论文 第二章文本聚类相关理论概述 率等进行预测。 ( 4 ) 聚类分析 聚类就是将数据对象分组成为若干个类或簇，在同一族中的对象之间具有较 高的相似度，而不同的族中的对象之间差别较大。与分类不同的是，聚类要划分 的类是未知的。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先 决条件。 ( 5 ) 孤立点分析 孤立点可能是度量或执行错误所导致的，也可能是固有的数据变异性的结 果。许多挖掘算法试图使孤立点的影响最小化或者排除他们，但这可能导致重要 信息的丢失，因为孤立点本身可能是很重要的。 ( 6 ) 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。它包 括时间序列数据分析、序列或周期模式匹配和数据分析。 2 1 2 数据挖掘过程 在数据挖掘中被研究的业务对象是整个过程的基础，它驱动了整个数据挖掘 过程，也是检验最后结果和指引分析人员完成数据挖掘的依据。数据挖掘过程如 图2 - 1 所示，图中各步骤是按一定顺序完成的。 图2 1 数据挖掘的基本过程和主要步骤 7 硕士学位论文第二章文本聚类相关理论概述 一个完整的数据挖掘过程包括： ( 1 ) 定义商业问题：了解数据和业务问题，定义一个清晰明确的目标。 ( 2 ) 数据准备：包括数据选择、数据清洗和预处理、数据变换三个步骤。 ( a ) 数据选择：搜索所有与业务对象有关的内部和外部数据消息，并从中选 择出使用于数据挖掘应用的数据。 ( b ) 数据清洗和预处理：研究数据的质量，为进一步的分析做准备，并确定 将要进行的挖掘操作的类型。 ( c ) 数据变换：将数据转换成一个分析模型。 ( 3 ) 建立模型：选取数据挖掘工具提供的算法并应用于准备好的数据，选取相应 的参数，生成模型。 ( 4 ) 评价模型：对模型进行比较和评估，生成一个相对最优模型，并对此模型用 业务语言加以解释。 ( 5 ) 实施与维护模型：对模型在实际应用的表现进行监控，并对模型进一步的考 察和修正，以反映业务运作规律的变化。 2 2 聚类分析 2 2 1 聚类分析定义 聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对象之间具较高 的相似度，而在不同簇中的对象差别较大【1 6 】【1 7 1 。将物理或抽象对象的集合分组 成为由类似的对象组成的多个类的过程，被称为聚类。由聚类所生成的簇是一组 数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相 异1 8 】【1 9 1 。聚类分析的主要目的是通过对数据集的合理划分来发现数据集的结构 特征。利用聚类结果，我们能够提取数据集中隐藏的信息，对未来数据进行预测 和分类。 聚类是数据挖掘的功能之一，聚类与分类不同：分类是一种监督学习，其类 别是根据应用的需要事先确定的，根据表示事物特征的数据可以识别其类别。而 聚类是一种非监督的学习，其类别不是人为指定的而是分析数据的结果，聚类完 全由计算机自动进行，不需要人工干预【2 0 】【2 l 】【2 2 1 。聚类通过比较数据的相似性和 差异性，能发现数据的内在特征及分布规律，从而获得对数据更深刻的理解与认 识【2 3 】。 2 2 2 聚类分析主要算法 目前存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的和应 8 硕士学位论文第二章文本聚类相关理论概述 用。如果聚类分析被用作描述或探察的工具，可以对同样的数据尝试多种算法， 以发现数据可能揭示的某些潜在的规律。 主要的聚类算法可以分为如下几类： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) 划分聚类法主要基于这样的假设：即类的中心可以代表整个类，并且一般由 该类包含对象的平均值来描述。假设集合有n 个对象，动态聚类法将对象划分 为k 个组，每个组代表一个聚类，并且k n 。对于给定的k 值，该方法首先给 出一个初始的划分，然后进行反复多次迭代来改变分组，使定义的优化函数每次 都有所改进，直到结果收敛或者达到某一迭代次数为止。 划分方法首先创建k 个划分，k 为要创建的划分个数；然后利用一个循环定 位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。划分算法把 聚类问题转化成一个组合优化问题，通常从一个初始划分或初始聚类集合开始， 利用迭代控制策略优化目标函数。典型的划分方法包括：k - m e a n s ，k m e d o i d s ， c l a r a ( c l u s t e r i n gl a r g ea p p l i c a t i o n ) ，c l a r a n s l 2 4 1 ( c l u s t e r i n gl a r g ea p p l i c a t i o n b a s e du p o nr a n d o m i z e ds e a r c h ) 等。 动态划分方法本质上是一种贪心算法，难以保证全局最优。动态划分方法每 次执行的结构都可能不同，它跟初始值的选取有很大的关系。为了避免其对初始 值比较敏感，还可以将算法执行多次，并取其中效果比较好的一次。由于基于划 分的聚类算法首先要初始化为k 个划分，因此划分聚类的难点在于如何在聚类之 前确定划分的类别数目k 。如果k 值选取得不合适，或者选择的初始点分布不均 匀，没有代表性，都将延缓聚类进程，影响聚类结果。此外，提前确定划分的类 别数目，这又直接违反了聚类的无指导性和无监督原则。 k - m e a n s 算法是聚类方法中一种典型的划分方法，其基本思想是通过迭代把 数据对象划分到不同的簇中，使簇内部对象之间的相似度很大，而簇之间对象的 相似度很小。k - m e a n s 算法是一种“硬”聚类算法。开始时需要设置初始的聚类 中心，将样本类别判定为距某聚类中心最近的类别，当所有的数据对象都按照这 个原则确定类别后，重新计算每个聚类中心或其样本均值，直到迭代结束【2 5 1 。 k - m e a n s 算法的具体过程如下： 输入：n 个待聚类的文档，聚类数目k 。 输出：k 个类别，每个文档属于其中一个类别。 ( a ) 任意选择k 个对象作为初始的聚类中心； ( b ) 根据聚类中心值，将每个对象( 重新) 赋给最相似的簇； ( c ) 重新计算每个簇中对象的平均值，用此平均值作为新的聚类中心； ( d ) 重复执行步骤( b ) ，( c ) ，直到聚类的中心不再发生变化为止。 9 硕士学位论文第二章文本聚类相关理论概述 k - m e a n s 算法聚类结果受初始聚类中心的选择影响较大，如果初始聚类中心 选取不当，聚类结果可能会陷入局部最优解，而得不到较好的聚类效果。 k - m e a n s 算法对脏数据很敏感，例如在算法中，用欧式距离作为样本距离度量时 经常会出现某类中只有一个样本数据的情况，因为这个孤立样本离其他的样本点 都很远，而且它可能是噪声数据。按照算法要求，把这个孤立点加入某个类别将 会使该类别中心偏离比较大，以至于最终结果会与正确聚类结果出现较大偏差。 ( 2 ) 层次方法( h i e r a r c h i c a lm e t h o d ) 层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如何形 成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法， 一开始将每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所 有的组合并为一个( 层次的最上层) ，或者达到一个终止条件。分裂的方法，也 称为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中， 一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个 终止条件。 典型的层次方法包括：b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n g u s i n gh i e r a r c h i e s ) 方法，它首先利用树的结构对对象集进行划分，然后再利用其 它聚类方法对这些聚类进行优化；c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ) 方法， 它利用固定数目代表对象来表示相应聚类，然后对各聚类按照指定量( 向聚类中 心) 进行收缩；r o c k 方法，它利用聚类间的连接进行聚类合并；c h e m a l o e n 方法，它是在层次聚类时构造动态模型。 下面的步骤描述了c u r e 算法的核心： ( a ) 从源数据对象中抽取一个随机样本s 。 ( b ) 将样本s 分割为一组划分。 ( c ) 对每个划分局部的聚类。 ( d ) 通过随机取样剔除孤立点。如果一个簇增长的太慢就去掉它。 ( e ) 对局部的簇进行聚类。落在每个新形成的簇中的代表点根据用户定义的一 个收缩因子a 收缩或向簇中心移动。这些点代表和捕捉到了簇的形状。 ( f ) 用相应的簇标签来标记数据。 层次聚类方法具有聚类结果比较精细的优点，在九十年代早期曾一度是文本 聚类的主流技术。但该方法的缺点是聚类效率较低，并且难以找到最佳划分。网 络信息量的爆炸增长迫切需要能够处理大量文档的技术，这就要求聚类算法要更 加有效率，且效果要好。这样一些其他处理聚类问题的方法便应运而生，其中比 较有效的方法包括动态划分的方法和自组织特征映射网络等方法。 ( 3 ) 基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 1 0 硕士学位论文第二章文本聚类相关理论概述 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状 的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类 方法，其主要思想是：只要临近区域的密度( 对象或数据点的数目) 超过某个阈值， 就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必 须至少包括某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任 意形状的簇。 典型基于密度方法包括：g d b s c a n 、d b c l a s d 、d e n c l u e ( d e n s i t y - b a s e d c l u s t e r i n g ) 、d b s c a n t o j ( d e n s i t y - b a s e ds p a t i a lc l u s t e r i n go fa p p l i c a t i o nw i t h n o i s e ) ：该算法通过不断生长足够高密度区域来进行聚类，它能从含有噪声的空 间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连接”的 点集。o p t i c s 2 7 ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) ：该算法并不 明确产生一个聚类，而是为自动交互的聚类分析计算出一个增强聚类顺序。 定义2 - 1 给定对象半径内的区域称为该对象的邻域。 定义2 2 如果一个对象的邻域至少包含最小数目m i n p t s 个对象，则称该 对象为核心对象。 定义2 3 给定一个对象集合d ，如果p 在q 的邻域内，而q 是一个核心对 象，称对象p 从对象q 出发是直接密度可达的。 定义2 _ 4 如果存在一个对象链p l ，p ：，见，p = q ，见= p ， 对只d ，( 1 f 咒) ，取。是从p i 关于和m i n p t s 直接密度可达的，则对象p 是从 对象q 关于和m i n p t s 密度可达的。 定义2 5 如果对象集合d 中存在一个对象o ，使对象p 和q 是从0 关于8 和m i n p t s 密度可达的，那么对象p 和q 是关于8 和m i n p t s 密度相连的。 d b s c a n 算法的聚类过程通过收集基于密度直接可达的对象来完成的。针 对待聚类对象集中的每一个对象p ，检查其邻域内是否至少包含m i n p t s 个对象， 也就是确定对象p 是否为核心对象。如果p 是核心对象，那么就创建一个初始的 类c ，c 中包含对象p 及从p 基于密度直接可达的所有对象，也就是包含对象p 及其一邻域内的所有对象。然后，再确定该邻域中的每一个对象g 是否为核心对 象。如果是核心对象，那么就将其8 邻域内尚未包含在类c 中的所有对象追加 到c 中，并继续确定这些新追加到c 中的对象是否为核心对象，如果是，则继 续进行上述的对象追加过程。这一过程一直持续到没有新的对象可以追加到c 中为止，类c 也就完全确定下来了。 ( 4 ) 基于网格的方法( g r i d - b a s e dm e t h o d ) 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。 所有的聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优点 硕士学位论文第二章文本聚类相关理论概述 是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一 维的单元数目有关。 典型的基于网格的方法是s t i n g 2 8 ( s t a t i s t i c a li n f o r m a t i o ng r i d ) ，它一个利用 网格单元保存的统计信息来进行基于网格聚类的方法。c l i q u e ( c l u s t e r i n gi n q u e s t ) 和w a v e c l u s t e 则是将基于网格与基于密度相结合的方法。 基于网格聚类方法利用多维网格数据结构，它将空间划分为有限数目的单 元，以构成一个可以进行聚类分析的网格结构。为了减少搜索复杂度，需要考虑 多边形分段区域。一个分段区域就是空间中一个划分的小超立方体，每一个分段 区域就称为一个单元。网格聚类算法把对于数据的分割转换成对于空间的分割。 数据分割通过数据点之间的关系导致的空间分割而产生，但是空间分割则是基于 输入数据累加的空间小超立方体( 网格) 的。本质上，它经过了如下的转换过程： 数据网格数据空间分割数据分割。这样不直接对数据进行处理的优点是网格数 据的增加使得基于网格的聚类技术不受数据次序的影响。基于网格的聚类算法适 用于各种类型属性的数据，不像基于密度的聚类算法仅对数值属性的数据有较好 的效果。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟 合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚 类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪声 数据或孤立点， 从而产生健壮的聚类方法。 基于模型的方法主要有两类：统计学方法和神经网络方法。典型的基于模型 方法包括：统计方法c o b w e b ，这是一个常用的且简单的增量式概念聚类方法。 它的输入对象是采用符号量( 属性- 值) 对来加以描述的，采用分类树的形式来 创建一个层次聚类：神经网络方法将每个类描述为一个标本，标本作为聚类的原 型，不一定对应一个特定的数据实例或对象。根据某些距离度量，新的对象可以 被分配给标本与其最相似的类，被分配给一个类的对象的属性可以根据该类的标 本的属性来预测。典型的神经网络方法自组织特征映射( s e l f - o r g a n i z i n gf e a t u r e m a p s ，s o m ) 将在第四章详细阐述。 2 3 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是基于统计学习理论的机器学习 方法。现有机器学习方法的重要理论基础之一是统计学，传统统计学是样本数目 趋于无穷大时的渐近理论，但在实际问题中，样本数往往是有限的，因此一些理 论上很优秀的学习方法在实际中的表现却可能不尽如人意【2 9 】【3 0 】。统计学习理论 1 2 硕士学位论文 第二章文本聚类相关理论概述 是研究小样本统计估计和预测的理论，v a p n i k 等人从二十世纪六、七十年代开始 致力于此方面研究，统计学习理论的主要内容包括以下四个方面【3 1 】【3 2 】：经验风 险最小化准, 贝s j ( e m p i r i c a l 鼬s km i n i m i z a t i o n , e r m ) 下统计学习一致性条件：统计学 习方法推广性的界；在推广性的界的基础上建立的结构风险最小化原则；实现这 些准则的支持向量机方法。 支持向量机最初来自两类模式识别问题，它包含三个核心思想【3 3 】【3 4 】【3 5 】：求 最优分类面以取得较好的推广能力；提出软间隔的概念以解决线性不可分问题； 引入核函数使解平面从线性扩展到非线性。 2 3 1 线性可分情形与最优分类超平面 支持向量机是从线性可分情况下的最优分类面发展而来的。支持向量机基本 思想可用图2 - 2 说明。图2 2 中，方形点和圆形点分别代表两类样本。h 为分类 线，h l 和h 2 分别为通过各类中离分类线最近的样本且平行于分类线的直线，它 们之间的距离被称为分类间隔。所谓最优分类面就是要求分类面不但能将两类正 确分开( 训练错误率为0 ，经验风险最小) ，而且使分类间隔最大( 控制推广能 力) 【3 6 】【3 刀【3 引。 如图2 - 2 所示，设分类面为国x + b = 0 ，则分类间隔等于2 1 彩1 i ，因此，使 分类间隔最大就等价于使1 2 ( a ) r o 彩) 最小。设训练样本集 ( 毛，y 。) ，( 而，赐) ，( 而，乃) ，石r ”，y + 1 ，- 1 ) 线性可分，要求分类面能将两类正确分 开，就是要求分类面满足如下约束条件： x t + 6 0 ，觊= 1( 2 1 ) 国7 而+ 6 - 1 i = 1 ，2 ，z ( 2 - 3 ) ( 2 4 ) 上述优化问题的解就确定了线性可分问题的最优分类面。当图2 - 2 中h 为最 优分类面时，h l ，h 2 上的训练样本就被称为支持向型3 9 】【删【4 l 】。从图中可以看出， 对支持向量的分类等价于对所有训练样本的分类，因此，支持向量包含了分类的 重要信息，是分类的重要样本【4 2 】。 2 3 2 线性不可分情形与软间隔 当训练样本集不能被线性函数完全分开时，优化问题( 2 3 ) 、( 2 4 ) 没有可行解， 为了在训练样本线性不可分的情况下构造最优分类面，v a p n i k 提出了软间隔的概 念：即在被错分的样本数目为最少的情况下构造最优分类面。此时，在图2 2 的 h l 和h 2 之间会出现被错分的样本( 也有一些被错分的样本位于h l 和h 2 的外侧) ， 显然，这些样本对决策函数也有贡献，所以也被称为支持向量【4 3 】【州。由于允许 错分，引入松弛变量毒0 ，把约束条件改为： y i ( c o t x f + 6 ) 1 一蠡 毒0i = 1 ，2 ，m ( 2 5 ) ( 2 - 6 ) 同时，目标函数变为( c 是一个常数，在这里被称为惩罚因子，使分类间隔和分 类错误达到某种折中) ： 幽互1 ( 小咖c ( 善i 缶) 对优纠6i h - jn ( 2 - 5 ) - ( 2 7 ) ，其对偶问题为( q 为l a g r a n g e 乘子) 【4 5 】： 11， m a x w ( a ) = 一去q 咒乃誓_ i - 1 f ，- l j z q 咒= oi = 1 ，2 ，7 0 哆ci = l ，2 ， ( 2 - 7 ) ( 2 - 8 ) ( 2 9 ) ( 2 - 1 0 ) 硕士学位论文第二章文本聚类相关理论概述 决策函数为： ， 厂( x ) = s g n ( a , 儿x , x j + 6 ) l = 1 ( 2 - 1 1 ) 由式( 2