（计算机应用技术专业论文）一种改进的k_means聚类算法研究.pdf

， - 、 c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho na n i m p r o v e dc l u s t e r i n g a l g o r i t h mo fk _ m e a n s c a n d i d a t e ：l i uz h e n g u a n g s u p e r v i s o r ：p r o f l i u j i e a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo fs u b m i s s i o n ：j a n u a r y ，2 010 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 01o u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y ， f ： 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 己在文中指出，并与参考文献相对应。除文中己注明引用的内 容外，本论文不包含任何其他个人或集体己经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 i7 作者( 签字) ：莎i 彤良7 _ 日期：o d 年弓月w e t 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可函在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：衣- j 掘7 -导师( 签字) ：云1 煮 日期： 沙o 年月心日o 年弓月日 哈尔滨工程大学硕七学位论文 摘要 随着网络的快速发展和信息化技术的不断进步，各种数据以惊人的速度 膨胀，如何从这些数据中找到有用信息，并对这些数据和信息进行分类，变 得日益迫切。数据挖掘技术的出现，使得大量数据处理成为可能。聚类是一 项重要数据挖掘技术，已成为研究热点之一。 本文主要针对km e a n s 算法对孤立点敏感和对初始点选择敏感的局限 性，对km e a n s 算法的聚类过程提出两点改进。首先，对km e a n s 算法中孤 立点检测问题进行深入研究，提出了基于网格的数据预处理算法。该方法对 数据集网格划分之后，进行孤立点的检测。其次，分析km e a n s 算法的初始 点选择，提出了基于平均点的初始点选择算法。该方法是在基于网格的数据 预处理算法基础之上，直接在网格中进行初始点的选择，使初始点更加合理 和接近实际的聚类中心。最后，在km e a n s 算法的聚类过程中，应用两个算 法进行孤立点处理和初始点选择，给出了改进的km e a n s 算法。 本文通过实验对改进的km e a n s 进行验证和分析，实验结果表明改进的 km e a n s 算法在一定程度上提高了聚类的准确率。 关键词：聚类；k - m e a n s 算法；网格；平均点 哈尔滨t 程大学硕士学位论文 a bs t r a c t w i t ht h e r a p i dd e v e l o p m e n t o fn e t w o r ka n dt h e s t e a d yp r o g r e s s o f i n f o r m a t i o nt e c h n o l o g y , av a r i e t yo fd a t ae x p a n dr a p i d l y h o wt o f i n du s e f u l i n f o r m a t i o na n dt oc l a s s i f yt h e mh a sb e e nb e c o m i n gi n c r e a s i n g l yu r g e n t t h e a p p e a r a n c e o fd a t am i n i n gt e c h n o l o g i e sm a k e si tp o s s i b l et op r o c e s sl a r g e a m o u n t so fd a t a c l u s t e r i n gi so n eo fi m p o r t a n td a t am i n i n gt e c h n o l o g ya n dh a s b e e nb e c o m i n gar e s e a r c hh o t s p o t i nt h i sp a p e r , t w oi m p r o v i n gp o i n t so ft h ek m e a n sc l u s t e r i n ga l g o r i t h m sa r e p r o p o s e dt os o l v et h el i m i t a t i o no fi t ss e n s i t i v i t yt o o u t l i e r sa n dt h es e l e c t i o no f i n i t i a lp o i n t s f i r s t l y , a f t e ro u t l i e rd e t e c t i o np r o b l e mo ft h ek m e a n sa l g o r i t h mi s s t u d i e dd e e p l y , a 鲥d b a s e dd a t ap r e p r o c e s s i n ga l g o r i t h mi sp r o p o s e d t h i s - m e t h o dd e t e c t so u t l i e r sb yd i v i d i n gt h ed a t a s e tg r i d s e c o n d l y , o nt h eb a s eo f a n a l y z i n gt h es e l e c t i o no fi n i t i a lp o i n t s ，a na l g o r i t h mo fi n i t i a lp o i n ts e l e c t i o ni s p r o p o s e d t h i sm e t h o dd i r e c t l yc h o o s e st h ei n i t i a lp o i n tb a s e do nt h eg r i d b a s e d a t a sp r e - p r o c e s s i n g ，s ot h a tt h ei n i t i a lp o i n ti sm o r er e a s o n a b l ea n dc l o s e rt ot h e a c t u a lc l u s t e rc e n t e r f i n a l l y , d u r i n gt h ep r o c e s so fk m e a n sc l u s t e r i n g ，t h o s et w o a l g o r i t h m sa r eu s e dt o d e a lt h eo u t l i e ra n dt os e l e c tt h ei n i t i a lp o i n ta n dt h e i m p r o v e dk _ m e a n sa l g o r i t h mi sg i v e n t h ei m p r o v e dk _ m e a n sa l g o r i t h mi sv e r i f i e da n da n a l y z e db ye x p e r i m e n t s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e dk m e a n sa l g o r i t h mi m p r o v e st h e a c c u r a c yo fc l u s t e r i n gi na c e r t a i ne x t e n t k e 3 o r d s ：c l u s t e r i n g ；k m e a n sa l g o r i t h m ；n e t w o r k ；a v e r a g ep o i n t 哈尔滨丁程大学硕士学位论文 目录 第l 章绪论1 1 1 研究背景及目的一1 1 2 国内外研究现状一2 1 3 论文研究内容及组织4 i 3 1 论文研究内容4 1 3 2 论文的组织结构6 第2 章相关知识及理论7 2 1 引言7 2 2 文本挖掘及聚类相关知识7 2 2 1 文本挖掘7 2 2 2 聚类概述12 2 2 3 距离与相似系数1 5 2 2 4 聚类的特征l8 2 3 聚类算法l9 2 3 1 基于网格的聚类算法1 9 2 3 2 基于密度的聚类算法2 0 2 3 3 基于划分的聚类算法2 1 2 3 4 基于层次的聚类算法2 1 2 - 3 5 基于模型的聚类算法2 2 2 3 6 其他的聚类算法2 2 2 4 本章小结2 3 第3 章基于网格的数据预处理算法2 5 3 1 引言2 5 3 2km e a n s 算法2 6 3 2 1km e a n s 算法概述2 6 3 2 2km e a n s 算法分析2 9 一 哈尔滨工程大学硕士学位论文 3 3 孤立点及检测方法31 3 3 1 孤立点概述3 1 3 3 2 孤立点检测方法3 3 3 4 网格化数据预处理方法3 6 3 4 1 网格化方法3 6 3 4 2 基于网格的孤立点检测方法3 8 3 4 3 孤立点处理方法3 8 3 4 4 网格化预处理数据算法3 9 3 4 5 实验结果及分析4 2 3 5 本章小结4 4 第4 章基于平均点的初始点选择算法4 5 4 1 引言4 5 4 2 初始点的选择方法4 5 4 3 基于平均点的初始点选择方法4 7 4 4 基于平均点的初始点选择算法4 9 4 5 实验结果及分析5 1 4 6 本章小结5 3 结论一5 4 参考文献5 6 攻读硕士学位期间发表的论文和取得的科研成果6 1 致谢6 2 哈尔滨工程大学硕士学位论文 1 1 研究背景及目的 第l 章绪论 随着i n t e m e t 的大规模普及、信息处理技术和数据处理技术的发展及企 业信息化程度的提高，各种网络资源以爆炸式速度迅猛增长，现存的网络资 源以数据库存储的形式为主，数据的形式以半结构化和结构化的形式存储。 但是在网络技术迅猛发达的今天，数据库中的数据量更是以惊人的速度发展， 就形成了数据量很大而对于有用的信息的发掘和利用成为一大难题的现象， 也成为现在研究的热点问题。特别是信息过滤、信息检索和数据挖掘等方面 的研究出现了前所未有的热潮。 数据挖掘就是从大量的、有噪声的、不完全的、随机的、模糊的数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在的有用信息和知识的过 程 1 1 。数据挖掘的过程般可分为：问题的定义、数据的收集和预处理、数 据挖掘算法的执行，挖掘结果的解释和评估，如图1 1 所示。 图1 1 数据挖掘的过程 数据挖掘是对大量数据的处理，而挖掘的过程中又分为很多阶段，每一 个阶段也是现在研究热点。在数据挖掘的过程中，聚类技术己成为数据信息 挖掘技术中的核心技术。聚类分析主要是对最后挖掘的数据根据不同的用户 哈尔滨工程大学硕士学位论文 需求进行最后的分类，最后得到让用户满意的数据结果。如何能准确的、高 效的聚类出用户想要的结果，成为聚类算法的主要研究方向。由于现实数据 量非常大，那么实际应用中算法根据数据的类型、聚类的目的和应用等不同， 出现了多种聚类算法。目前文献中出现大量的聚类算法，主要可分为：划分 方法( p a r t i t i o n i n gm e t h o d ) 、层次方法( h i e r a r c h e c a lm e t h o d ) 、基于密度的方 法( d e n s i t y - b a s e dm e t h o d ) 、基于网格的方法( g r i d b a s e dm e t h o d ) 和基于模 型的方法( m o d e l b a s e dm e t h o s ) 五大类【2 1 ，每一大类有一些代表性的算法。 当今的工程应用中，特别是对于数据挖掘方向的实际应用中，聚类已经 成为工程中的核心，聚类结果的质量，直接影响整个工程的质量。那么对于 聚类的研究和分析必然成为我们研究的一个重点，这对于我们在聚类方面研 究来说，既是一个机遇，也是一个挑战。 虽然聚类方向的研究比较晚，但是已经提出了很多经典聚类算法，而且 它们已经成为人们现在使用频率最高的算法，但是原始的经典聚类算法存在 相应的缺点，针对聚类算法的研究方询和算法存在的缺点，本问旨在原 km e a n s 的算法基础上，对km e a n s 算法进行两个方面的改进，提出了一种 新的改进km e a n s 聚类算法。 1 2 国内外研究现状 聚类是通过对大量数据的分析，利用聚类算法和根据用户的需求，将原 始数据集合分成若干个簇，并要求单个簇内聚类数据的相似性应尽可能大， 而簇与簇之间的相似度应尽可能小【3 1 。 在文本聚类过程中，对文本集进行处理之后，将会得到一个特别大的数 据集合，使用聚类算法进行聚类的时候，将会是一个很大的工程，并且最后 的聚类结果准确性差、信息丢失、时间长等很多问题。因此如何更好的处理 这些问题，已经成为当今文本聚类研究的一个课题。 现在所有的聚类算法中，在数据集和应用环境要求不同的情况下，基本 上没有一种聚类算法可以得到普遍应用。在长时间的研究过程中，根据不同 哈尔滨工程大学硕十学何论文 的应用环境和应用要求，人们提出了大量不周的聚类算法。人们根据聚类算 法的特点，大致分为：划分式聚类算法、层次化聚类算法、基于密度的聚类 算法、基于网格的聚类算法和基于模型的聚类算法。 km e a n s 算法是最经典的划分式聚类算法，其他划分方法大都是这种方 法的改进。以经典k m e a n s 算法为基础，根据应用环境和要求的不同，人们 提出了很多改进的k m e a n s 聚类算法。由于存在k m e a n s 算法仅适合于数值 属性数据聚类的局限性，在1 9 9 8 年，h u a n g 为克服其局限性而提出了一种适 合于分类属性数据聚类的k - m o d e s 算法 4 3 。该算法从以下几个方面对k m e a n s 进行了扩展：用m o d e s 来代替m e a n s ，为使聚类代价函数值达到最小化，在 聚类过程中利用基于频度的方法来修正m o d e s ，引入新的相异性度量方法( 简 单的相异性度量匹配模式) 来处理分类对象。 km e a n s 算法从提出到现在也经历了一个很长的发展阶段，由于其经典 性、可应用性强、快速和简单等特点，人们进行了大量的研究。k 算_means 法的应用主要体现在一下几个方面：( 1 ) km e a f f s 算法在高维数据中的应用； ( 2 ) km e a n s 算法在流式数据中的应用；( 3 ) km e a n s 算法在部分信息数据 中的应用；( 4 ) km e a n s 算法在有偏数据中的应用。 1 9 9 7 年，m i t c h e l l 5 就如何以混合模型算法的形式，对基于平方欧几里德 距离的l 卜均值算法进行了研究分析。2 0 0 0 年，s t e i n b a c h ，k a r y p i s 矛t l k u m a r j 提出了二分l 卜均值算法，该算法进行对整个数据集进行划分，知道用户设 定类的个数，该算法聚类效果和计算效率都比较好，还一定程度解决了原 km e a n s 算法选取初始点方法所产生的问题。2 0 0 2 年，d h i l l o n ，g u a n 禾i k o g a n 【j 提出了局部搜索策略“f i r s tv a r i a t i o n ”，改进了基于余弦相似度的k 一均值算 法。2 0 0 3 年，d h i l l o n 8 9 】等提出了辅助文本分类的文本属性聚类方法和基于信 息理论的联合聚类方法，他是从信息理论的角度对基于k l 散度的k 均值算法 进行研究。由于km e a n s 算法对孤立点很敏感，初始点的选择该算法的影响 比较大，因此人们近些来在这些方面也做了大量的研究。p s b r a d l e y 和u m f a y y a d 1 0 提出了一种初始聚类中心的算法r a ，该算法不在整个数据集上 哈尔滨工程大学硕七学伊论文 选取样本，并用自动的方法选取初始点，减小了时间复杂度和孤立点对聚类 结果的影响。孙秀娟和刘希玉提出了基于初始中心优化的遗传km e a n s 聚类 新算法 】，该算法基本实现了对初始点的依赖性问题，聚类质量高，收敛也 很快。张忠平等提出了一种基于广度优先搜索的km e a n s 初始化算法 】2 1 ，该 算法能有效降低孤立点对初始点的影响。d a q i l i 等提出了一种基于网格的快速 km e a n s 聚类算法 13 1 ，该算法采用分割数据集的方法，来处理数据，最终减 少了数据计算的复杂度，增加了聚类结果的精确度。km e a n s 算法作为划分 聚类的一种，与基于密度、基于层次等聚类方法也有很多的组合，这方面研 究也很多。赵大伟等提出一种改进的基于密度和样本数量的km e a n s 算法u j ， 该算法还利用d b s c a n 算法对小类进行合并，聚类的质量和稳定性都得到了 提高。 km e a n s 算法在经过长期的发展过程中，虽然得到了很多的改进，对其 缺点和优点人们也进行了大量的研究，但是其改进的方向还是比较多，作为 经典算法还有其继续研究的价值，一般有以下几个方面的研究【1 4 0 6 】：( 1 ) 消 除“均匀效应”的不良影响；( 2 ) 选择该算法更好的评价标准；( 3 ) 如何在 特定的领域应用不同的距离函数，并理论上证明在特定领域应用特定近似函 数更好；( 4 ) 提出更好的与该算法组合的改进算法；( 5 ) 用km e a n s 算法的 迭代寻优算法解决更多的优化问题；( 6 ) 随着数据量的越来越大，新的数据 特征出现，km e a n s 算法如何才能适合这样的变化。从目前来看，这样的研 究还是很有意义的。 1 3 论文研究内容及组织 1 3 1 论文研究内容 本文根据km e a n s 算法存在的缺点，对其聚类过程进行改进。km e a n s 算法对数据不做任何处理就进行中心点的选择，然后进行算法处理，这样就 会存在以下缺点：( 1 ) 如果数据中存在孤立点，算法的结果就会受到孤立点 的影响；( 2 ) 如果数据中存在孤立点，中心点的选择过程也会受到影响：( 3 ) 4 哈尔滨t 程大学硕士学位论文 初始中心点的分布不合理。 针对上述缺点，本文提出了对整个聚类过程的两点改进方法，首先对数 据进行网格化预处理，然后在此基础上进行基于平均点的中心点的选择。网 格化预处理数据的目的是：( 1 ) 对数据网格划分进行孤立点的检测，尽可能 的找到数据集中存在的孤立点，消除孤立点对k m e a n s 算法的影响；( 2 ) 检 测孤立点后，在划分好网格的基础上进行初始点的选择，消除了孤立点对中 心点选择的影响；( 3 ) 利用网格的个数来确定最后的聚类个数，尽可能的减 少对参数k 值的依赖性；( 4 ) 把检测到的孤立点作为一类输出供以后挖掘应 用，对孤立点的处理更加合理化。基于平均点的初始中心的选择算法主要是 针对km e a n s 算法中心点的选择存在的不足进行改进，它的目的是：( 1 ) 在 对数据网格划分后进行中心点的选择，每一个网格中选择一个中心点，使初 始中心点分布更加合理化；( 2 ) 在每一个网格中利用平均点的方法进行数据 的中心点的计算，使中心点在每一个网格中合理化；( 3 ) 在每一个网格中， 根据网格中数据量的多少，利用不同的方法选择数据点的个数进行平均点的 计算，使算法具有伸缩性。那么本文的两点改进方法的主要思想如下： 1 基于网格的数据预处理 由于km e a n s 聚类算法在聚类的过程中，对孤立点非常的敏感，孤立点 的存在直接影响了整个数据的聚类效果。本文根据此聚类特征，首先对整个 的聚类数据，在各维上进行划分，把整个数据域划分为多个网格区域，在每 个网格区域内，根据提出的寻找孤立点的方法，找出存在的孤立点，并进行 反复操作，直到找不到孤立点为止。这样就会找出一定数量的孤立点，减少 了孤立点影响聚类效果的概率，并且对整个数据进行了网格划分，为下面的 初始点选取做了很好的准备。 2 基于平均点的初始点选择 原始km e a n s 算法对初始点的选取只是随机的选取，那么选取的过程中， 就会出现初始点的距离很近或几个聚类中心非常近的可能性，在进行最终聚 类中心寻找的过程中，增加迭代次数，甚至不能得到最优解。本文根据此聚 哈尔滨t 程大学硕士学位论文 类特征，在基于网格的数据处理步骤之后，马上在网格划分的基础上，进行 聚类初始点的选择，这样是所有选择的初始点能更合理的分布在整个数据域 中，减少迭代次数，对大数据量的聚类效果会更加明显。 1 3 2 论文的组织结构 第1 章介绍论文研究背景及目的，聚类和km e a n s 聚类算法的国内外研 究现状，并阐述本文的研究内容。 第2 章介绍相关知识及理论，概括文本挖掘和聚类的相关知识和常用技 术，并介绍和总结了几种经典的聚类算法。 第3 章详细阐述了km e a n s 算法和其优缺点，研究km e a n s 算法中存在 的孤立点问题，并对数据域进行网格划分处理进行解决，重点研究基于网格 划分的方法。本章分别阐述了网格划分思想，基于网格的孤立点检测思想和 孤立点处理方法，利用网格划分方法改进km e a n s 聚类算法，在整个数据域 网格化处理的算法和实验的分析。 第4 章研究km e a n s 聚类算法初始点选取的特点和该方法对聚类结果的 影响，利用网格划分后的结果，进行初始点的选择，使初始点的选取和分布 更加合理化，并阐述了平均点的思想，最后对实验结果进行分析。 6 哈尔滨 二程大学硕士学位论文 2 1 引言 第2 章相关知识及理论 数据挖掘技术出现的时间不长，相应聚类方面的研究时间也不长，但是 其发展非常迅速，在工程中的应用，特别是在搜索引擎中的应用非常广泛， 聚类的理论和技术迅速增加。各种经典聚类算法相应出现，在聚类过程中， 每种聚类算法表现出一定的缺点和局限性，针对这些问题，人们不断的对聚 类算法的再改进，同时提出相应的理论作为改进的基础。比如提出孤立点的 问题，计算样本间距离的不同计算方法，聚类结果质量的评定等。 km e a n s 算法作为一种基于划分的经典算法，开始只是提出了一种聚类 过程的思想，当然存在很多缺点和局限性。从提出到现在的整个发展过程中， 人们针对它存在的问题，在原km e a n s 算法的基础上提出了大量的改进算法。 所有的改进算法，大部分都是把其他的聚类方法，比如，基于层次方法、基 于密度方法等，应用到km e a n s 的算法步骤当中，而改进之后，也只是解决 某一方面的问题。 现在随着网络用户的快速增加，数据信息的膨胀速度更是惊人，那么在 聚类过程中对大数据量的聚类效果和时间也成为聚类研究非常关心的问题， 人们也提出了一些解决办法，但是真正解决还需时间。针对km e a n s 算法， 改进之后会出现用户输入参数增加，聚类数据形状要求严格等问题现在一直 没有得到很好的解决。而最关键的用户输入参数直接影响聚类的效果，如何 解决这一问题，还需要进一步研究。 2 2 文本挖掘及聚类相关知识 2 2 1 文本挖掘 数据挖掘就是从大量的数据中找到有用的数据，文本挖掘作为数据 哈尔滨1 = 程大学硕十学伊论文 挖掘的一个重要分支，特别是在我们国家的研究和发展都非常迅猛。由 于文本和数值也可以通过一定的映射关系进行转换，因此实际应用中， 也通过这样的转换关系直接进行数值型聚类。因此研究文本挖掘的过程 对实际的研究有很大的意义。 文本挖掘【1 7 】( t e x tm i n i n g ) 是指从大量文本数据中抽取事先未知的、可 理解的、最终可用的信息、或知识的过程。文本挖掘的处理过程大致可分为如 下步骤：在大量文档集合的内容中建立特征集、对特征集进行缩减、对知识 模式进行提取、对模式质量进行评价等。文本挖掘过程如图2 1 所示： 爨 祷 钗 预处 理 标准化 l 结 i 构 剖化 。j 数 i 据 特征 提取 量化 形 式 化 数 据 学习与知识 模式的提取 文本挖掘 知 识 模 式 模式 评价 可视 化 知识 图2 1 文本挖掘过程 ( 1 ) 建立特征集：文本具有非结构化的特征，在处理过程中，无法直接 应用现有的数据挖掘技术和方法，因此需要从文本中提取一定量的、能代表 其特征的元数据作为特征项，并用结构化的形式保存这些特征，这一过程就 实现对非结构化的文本进行处理。 ( 2 ) 缩减特征集：在含有大量词汇的自然语言文本集合中，如果把所有 的词都列为其特征，那么它的维数高的惊人，处理它们也是相当困难，并且 很多特征对于即将进行的分类学习不是重要和有益的，因此我们需要去掉一 些冗余的、对分类影响不大的词汇来降低维数。 ( 3 ) 提取知识模式：在进行完缩减特征集之后，就可以通过利用机器学 习的各种方法和技术来实现面向特定应用目的知识模式，主要是进行文本聚 类和文本分类等。 r 哈尔滨t 程大学硕士学位论文 ( 4 ) 评价模式质量：为了对文本挖掘的效果进行准确的、客观地、有效 的评价，很多评测方法被提出并得到应用，比较常用的评测方法有查全率和 准确率。所有判断的文本在人工分类结果吻合的文本中所占的比率称为准确 率。人工分类结果应有的文本在分类系统吻合的文本中所占的比率称为查全 率。 以上所有步骤不一定需要一次性完成，其中某些或者全部步骤可能需要 反复进行。 文本通常采用向量空间模型【1 8 1 ( v e c t o rs p a c em o d e l ，v s m ) 、布尔模型和 概率模型来表示。 ( 1 ) 向量空间模型：在该模型中，把每个文本d 作为向量空间中的一个 向量。在该文本集合中出现的所有词的集合称为文本集合d 的特征空间，用 乃= 川v t d ，v d d ) 表示。在实际的应用中，文本集合d 在很多种情况下 都具有相当大的规模，因此l 是非常庞大的。一般t 在整个文本集合中的出 现频度通常用f r e q u e n c y ( t ) 来表示，一些词的特征如下： f i e q u e n c y ( t ) 1 或f r e q u e n c y ( t ) 岛 的取值范围接近1 ，的取值范围接近o 。即词t 在d 中出现在非常 少的文本中，或者在d 中出现在非常多的文本中。研究和实验证明这些词在 文本的聚类过程中产生的作用非常小，但是对聚类结果的效果影响很大，因 此选取文本的特征的时候，需要找到能更好的区分文本词的集合。度量特征 向量一般使用t f i d f 来表示，文本每个词t 的权重在该度量已给出，计算权重 的公式【1 9 】如下： t f i d f ( d , t ) = t f ( d , t ) 刈。g 赤 其中n 表示文本集合d 的大小，d f ( t ) 表示文本集合d 中包含词t 的所 有的数目的多少，o c ( d ，) 表示词t 在文本d 中的词频的大小。 因此任意文本可以表示如下： 9 哈尔滨工程大学硕十学伊论文 其中够表示含有第i 个词的文本数目的多少，矿表示文本中的第i 个词 频度大小。 在计算文本相似度的时候，不同长度的文本会对其有一定的影响，因此 需要对每个文本向量的模进行模l 标准化，设： d 删= 则模l 标准化后，表示如下： 锄2 荒丽丽斫蔗l 0 9 0 蓊d f ) 丽，丽霖雨t f 1 磊0 9 0 霸d f ) 丽 则有| | = 1 。 在文本聚类之前需要进行文本相似度的计算，很多种计算文本相似度的 方法被提出，现在文本相似度的计算方法比较流行的有欧氏距离法 2 明和余弦 距离法1 2 l j 。 利用欧氏距离度量文本之间的相似度。 假设文本d i ，d i d 则： d i s 弛嘭) 三瓜j 再可i 瓦可了而 利用余弦距离度量文本之间的相似度。 假设文本d ，d i d 则： d d c o s ( 矿) 2 而而知 当每个文本向量被归一化到单位长度之后，即l | l l _ 1 ，则两个文本向 量的点积为其余弦相似度，即c o s ( d ，d ，) = d i d ，。 ( 2 ) 布尔模型：它是基于集合论和布尔代数的一种简单检索模型。把文 本的特征性表示为二值变量的集合。1 表示特征变量在文本对象中出现，0 表示特征变量在文本对象中不出现，利用布尔运算法则和运算符n o t 、o r 和a n d 来处理。布尔模型以其清楚、简单的形式而被广泛应用。但是缺陷 也很明显，第一：由于检索策略只有相关和不相关两种状态，所以文本分级 概念比较少，相应的检索功能下降。第二：在处理过程中全部要使用布尔表 达式，如何将用户的大量信息与布尔表达式对应起来，也是非常困难的过程。 1 0 哈尔滨工程大学硕士学位论文 ( 3 ) 概率模型：利用文档概率模型来评估给定用户查询串与文档相关的 概率，该模型假设概率仅仅决定于文档和查询串。把所有包含给定用户查询 串的相关文档集合设为一个理想结果文档集，从中得到结果文档，对结果文 档集属性进行处理，但是怎么才能知道结果文档集的属性，就需要我们做一 个初步的估计，需要系统和用户进行交互。过程如下：用户对查看的结果文 档进行相关和不相关的分类，系统会利用该信息自动进行理想结果集概率描 述的重新定义，重复该过程，直到接近真正的结果文档集。优点是：文档根 据相关概率递减的顺序可以计算秩。缺点是：模型没有考虑索引术语在文档 中的频率，索引术语间相互独立。 文本聚类作为聚类的一种特殊的聚类类型，在我国有很广泛的研究 价值和应用前景。由于中文的词汇量非常的大，所以文本聚类与一般的 聚类方法有很大的差别，主要体现在对数据的处理方面。通常用矩阵来 表示文本对象，每一行记录代表一个文本对象，而矩阵中每一个数据点 表示文本中的一个词，就会出现高维的稀疏矩阵，处理就会非常的困难， 一般要对文本进行先期处理。其过程一般需要分词、停用词处理和特征 选择等，文本聚类的过程如图2 2 所示： 停用文本文本 输出 文本 卜 分词 j 词等 扒特征八权重j 表示 八 聚类 j 聚类 集合 1 1 选择 1 计算 v1 v 处理模型算法结果 图2 2 文本聚类流程图 ( 1 ) 分词：文本中是以字为单位组合形成的，那么如何提取出这 些字，如何找到其中的词，是分词处理过程必须做的。比如：伟大的中 华民族。这里不能简单的分为“伟”、“大”、“的”、“中”、“华”、“民”、 “族”这七个字，这样不但增加维度数，聚类结果也不会准确，需要把 哈尔滨工程大学硕士学位论文 其中的词提取出来，利用分词，结果为：“伟大”、“的”、和“中华民族”。 ( 2 ) 停用词处理：在一个文本对象中，如果一个字或词汇出现的 频率过高或者过低，那么我们认为它们对聚类的贡献是不大的，但是如 果它们存在，就会增加整个数据集的维度，处理也很复杂，处理速度会 大大降低。比如：“的”、“得”和“我们”等字和词，一般都会处理掉。 ( 3 ) 特征选择：一个文本对象的字和词汇都很大，如果很多文本 组成的文本集，其中的字和词汇更是一个惊人的数字，如何提取出代表 其特征的字和词汇，成为处理聚类处理过程中的重点。使用比较成熟的 特征选择方法有：信息增益、互信息、文本证据权、优势率等。 2 2 2 聚类概述 聚类作为数据挖掘后阶段的核心，起有非常大的影响。将抽象的或 者物理的对象集合划分成由相似对象组成的很多类的过程称为聚类。簇 是聚类过程中产生的一组数据对象的集合。聚类的效果希望簇内的对象 间相似度很高，而与相异簇中的对象相似度很低。聚类一般分为软聚类 和硬聚类，如果一个对象聚类后只属于一个簇称为硬聚类，如果一个对 象聚类后可能存在多个簇内称为软聚类。 分类问题在现实生活和实际应用中非常多，俗话说“物以类聚，人 以群分”，很多问题只能在更好的分类之后，才能有助与对后面的问题 做进一步的分析和研究。在聚类过程中，提出了聚类分析理论，又称为 群分析，他是一种统计分析的方法，目的是研究分类，因此聚类分析源 于分类学。但是聚类作为计算机科学研究的个重要分支，聚类也不等 于分类。聚类对于要进行划分的类的类型数量是未知的。在原始的分类 学中，人们对于分类只是根据人们的经验，随着知识和信息量的不断膨 胀，人们渐渐的把数学工具应用到分类学中，形成了后来的数值分类学， 随着技术的进步，人们又将多元分析的技术引入其中从而形成了聚类分 析。聚类分析包含丰富的内容，有图论聚类法、模糊聚类法、系统聚类 1 2 哈尔滨工程大学硕士学位论文 法、动态聚类法等。 聚类的应用也非常广泛，比如在生物学上，可以推导动植物的分类， 对基因分类后，可以获得对种群原有结构的认识等；在商务上，市场分 析人员通过客户数据库中的数据特征，可以挖掘不同的客户群体，可以 建立不同客户群体的购买模式；还可以对一个城市的房屋根据其位置、 价位等进行分组；在网络平台上可以对w e b 上抽取的文档进行分类，发 现有用的信息等。 聚类的过程描述如下： 对一个给定的数据集合d = d l ，d ：，d 。) ，利用相应的聚类算法，经过 聚类，最终得到一个聚类结果集合c = c 。，c ：，气) ，其中c ，cd ( i _ 1 ，2 ，k ) ，使得3 c ，( c ，c ) v d ，( d ，d ) ，有d f c ，同时使得目标函数q ( c ) 达到最小，其中n 为数据的总数目，k 为最终的聚类个数，且j ，c ，nc ，= 。 聚类分析过程如图2 3 所示。 图2 3 聚类分析过程 聚类分析中有很多聚类算法，但对于所有的聚类算法它都有一些潜在的 要求，有的算法满足其中的一些，如果有些要求不能被满足，那么一般对不 能被满足的要求会成为该算法的局限性，潜在的要求如下【2 2 】： ( 1 ) 伸缩性：算法提出以后，一般对于小数据量和低维数据的处理效果 都比较好，而对于大数据量和高维的数据一般很难适应，而算法的伸缩性要 求算法对于上面的两种情况都能处理，特别是推广到大数据量和高维数据的 时候，算法的准确率和时间复杂度都不能太高，这是算法实际应用的需要。 ( 2 ) 能够对不同类型的字段处理：一般算法都是以处理值类型的字段为 1 3 哈尔滨t 程大学硕士学位论文 基础进行实验，那么算法还应能够处理其他的字段类型，比如：字符型、布 尔型等。 ( 3 ) 处理不同形状数据的能力：很多算法在计算距离的过程中，一般使 用欧几里德距离的方法，而该方法在处理球形的数据和密度相近的类时效果 比较好，在实际的应用中，大部分的数据都不是球形，如何处理和发现不是 球形的数据，是对算法的一个要求。 ( 4 ) 输入参数的依赖性：很多算法在实际的应用中，需要用户自己确定 和输入一些必要的参数，比如km e a n s 算法中k 值的确定等，这些对于一些 专业领域的用户还可以，可是对于般用户，很难确定参数值，特别是对于 大数据量和高维数据，很多参数很难确定。因此一个算法的提出，必须解决 参数值的确定问题。 ( 5 ) 能够处理异常数据：对于算法要处理的数据，很多数据都有一定的 缺陷，甚至有一些错误的数据，还有孤立点的存在等，这些数据的存在，对 最后的聚类结果会有很大的影响，如何处理这些异常数据，是算法必须具备 的一个能力。 ( 6 ) 数据的输入和聚类结果的无关性：在算法处理数据的过程中，由于 数据来源和用户的不同，会出现不同的输入顺序，有些算法会由于数据的输 入顺序的不同产生不同的结果，这是不希望得到的结果。 ( 7 ) 处理高维数据的能力：很多算法提出以后，所做的实验一般都是利 用二维数据进行，但是在实际的应用中，绝大部分数据都是多维的，即使有 些高维数据经过处理进行降维，最后处理的数据也不是二维，高维的数据还 具有稀疏和形状不规则等特点。因此，一个算法是否能够很好的处理高维数 据，也是评判一个算法好坏的依据。 ( 8 ) 条件增加后的聚类能力：实际的聚类过程中，人们根据自己的需要， 会对加入各种各样的限制条件，在加入条件后，人们希望最后的聚类结果仍 然会比较满意。 ( 9 ) 可理解和可应用的结果：任何算法最终都是要为人们服务，给用户 1 4 哈尔滨t 程大学硕士学位论文 想要的结果，那么无论是什么样的语义环境和领域知识，算法的结果都应该 能让用户容易理解和应用。 2 2 3 距离与相似系数 假设一个聚类中有葺( 江1 , 2 ，n ) n 个样品，把所有的样品中各取出p 个 变量，利用间隔尺度的方法进行度量，把任意两个样品i ，j 之间的观测值记 做，则p 个变量的观测值的矩阵形式如下： x = 其中任意样品i 的p 个变量的观测值的向量形式为：x ，= ( x 门，一：，x 胂) 7 。 由于样品本身的各种性质可能使用不同的单位度量，那么有的观测值可 能很大，有的可能很小，而很大的观测值会对很小的观测值有弋定的影响， 为了减少影响，一般需要进行数据的中心化和标准化的变化处理。 把所有变量的观测值都在相同的基点下进行处理，即观测值与相应变量 的平均值的差，这个过程称为数据的中心化。任意变量j 的平均值一般记为： ；j = 三x ： = 1 ，2 ，p 1 百 把任意变量j 的n 个数据进行中心化变换的过程如下： 一 x 扩= x f x j i = 1 , 2 ，玎 通过中心化变换，所有变量的均值将会是0 ，所有变量就有了相同基点。 变化过程还可以如下： x 2 一m m i n 。( x i ，) 所有变量的最小值称为o ，这是正规化的过程。 中心化后，继续进行变换，使所有变量在变换的过程中，变换范围一样， 这一过程称为标准化。变化范围可以利用不同的方法进行衡量，那么相应的 1 5 哈尔滨工程大学硕十学位论文 标准化过程的交换方法也不相同，一般方法有【2 3 】： ( 1 ) 标准差标准化 任意变量j 的标准差记为： s j = 任意变量j 的1 1 个数据进行标准差标准化的过程如下： x ， 一