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

安徽大学硕士论文 中文摘要 “物以类聚，人以群分”，聚类伴随着人类社会的产生和发展而不断深化， 人类要认识世界就必须区分不同的事物并认识事物间的相似性，而每个概念 的最初形成无不借助于事物的聚类分析。聚类分析是数据挖掘领域中的一项 重要的研究课题，它既可以作为单独的工具以发现数据源的数据分布信息， 也可以作为其他数据挖掘算法的一个预处理步骤，因此研究如何提高聚类算 法的性能具有重要的意义。 本文首先研究分析了数据挖掘、聚类的基本概念和一般方法，对聚类分 析的前期工作：样本数据规格化、距离计算、关联程度的计算方法进行了综 述；然后详细分析了现有的聚类算法，指出了它们的优缺点，重点提出了一 种新的聚类算法覆盖聚类算法( c c a ) ，同时对提出的算法进行了一定的 应用研究，归纳起来，本文的主要研究工作如下： ( 1 ) 讨论了当前一些代表性的聚类算法，详细研究分析了基于统计理论 的系统聚类算法、基于划分的k m e t n s 算法、基于矢量的l b g 算法，对三种 算法的数学理论、实现过程、性能进行了评述，并指出了它们的优点与缺点， 为课题的进一步研究打下了基础。 ( 2 ) 因为传统聚类算法具有如下问题：算法的效率问题、初值的选择问 题、算法对输入参数的依赖性问题等。鉴于此，本文提出了一种新的聚类算 法一覆盖聚类算法，该算法采用覆盖的概念将比较集中的样本聚合在一起， 从而发现隐含在样本集中的类，对于周围稀疏的样本结合最短距离法，获得 聚类效果。该算法可以在覆盖后求重心，不断调整所做的覆盖，对大量的样 本数据不需要迭代，因而解决了其他聚类算法难以解决的问题：初值的选择 和聚类速度。 ( 3 ) 本文最后把覆盖聚类算法应用到医药公司药品销售数据聚类中，对 药品销售数据进行聚类，实验数据证明了覆盖聚类算法的可行性和有效性。 关键词：数据挖掘聚类覆盖聚类算法人工神经网络 安徽大学硕士论文 a b s t r a c t t h i n g so fo n ek i n d c o m et o g e t h e r , a n dm a nl i v e si ng a n g ”c l u s t e r i n g c e a s e l e s s l yp r o g r e s s e sw i t ht h ed e v e l o p m e n to ft h eh u m a ns o c i e t y h u m a nb e i n g l l s ec l u s t e r i n gt od i s t i n g u i s ho b j e c t sa n dt oa n a l y z et h es i m i l a r i t i e so fd i f f e r e n t t h i n g s c l u s t e r i n gi so n eo ft h ei m p o r t a n tr e s e a r c hs u b j e c t si nd a t am i n i n g i tn o t o n l yc a nb eu s e da sas e p a r a t et o o lt of i n dd a t ad i s t r i b u t i n gi n f o r m a t i o n , b u ta l s o c a nb eu s e da sap r e t r e a t m e n ts t e po fo t h e ra l g o r i t h m si nd a m m i n i n g t h u s ，i ti s s i g n i f i c a n t t or e s e a r c hh o wt o i m p r o v et h ep e r f o r m a n c eo ft h ec l u s t e r i n g a l g o r i t h m s t h eb a s i cc o n c e p t sa n dm e t h o d so fc l u s t e r i n ga r ef i r s t l yi n t r o d u c e di nt h i s t h e s i s ，a n dt h ep r e - w o r ko f t h ec l u s t e r i n ga r es u m m a r i z e d ，s u c ha st h ep r e t r e a t m e n t o ft h es a m p l ed a t a , t h em e t h o d so fd i s t a n c ea n dt h ed e g r e eo fc o r r e l a t i o n c o m p u t i n g s e c o n d l yt h ee x i s l i n gc l u s t e r i n ga l g o r i t h m sa a n a l y z e d i nd e t a i l t h e i r a d v a n t a g e sa n dd i s a d v a n t a g e sa r cp o i n t e do u t f i n a l l yan e wc l u s t e r i n ga l g o r i t h m w h i c hc a l l e d c o v e rc l u s t e r i n ga l g o r i t h m ”i sp u t t e df o r w a r d ，a n di ti sa l s o a p p l i e d i ns u m m a r y , t h em a j o rc o n t e n t so f t h i st h e s i sa r ei n c l u d e d 蹈f o l l o w s ( 1 ) t h ec u r r e n tt y p i c a lc l u s t e r i n ga l g o r i t h m sf i r ed i s c u s s e di nt h i st h e s i s ，s u c h a st h eh i e m r c t f i c a lc l u s t e r i n ga l g o r i t h m sb a s e do ns t a t i s t i c st h e o r i e s ，k - m e a n s a l g o r i t h mb a s e do np a r t i t i o na n dl b ga l g o r i t h m b a s e do nv e c t o r s t h e i r m a t h e m a t i ct h e 嘶e s ，p r o c e s s e sa n df u n c t i o n sa r ec o m m e n t e do n ，a n dt h e i r a d v a n t a g e sa n dd i s a d v a n t a g e sa r ed i s c u s s e d t h ew o r kl a y st h ef o u n d a t i o nf o rt h e f u l l e rr e s e a r c h e s ( 2 ) b e c a u s eo ft h ed e f e c t so ft h ec u r r e n tc l u s t e r i n ga l g o r i t h m s ，s u c ha s e f f i c i e n c y , s e l e c t i o no fi n i t i a ld a t a , d e p e n d e n c eo fp a r a m e t e r sa n ds oo n ，an e w c l u s t e r i n ga l g o r i t h m c o v e rc l u s t e r i n ga l g o r i t h m ”i sp u a e df o r w a r di nt h i st h e s i s w i t ht h i sa l g o r i t h m ，t h ec l o s es a m p l e sa r ec l u s t e r e da n dt h eg r o u p si m p l i e di n s a m p l e sa r ef o u n do u t t ot h es p a r s es a m p l e s ，t h es h o r t e s td i s t a n c em e t h o dc a nb e a d o p t e d a f t e rc o v e r i n g ，t h eg r a v i t yc e n t e r so fc o v e r sa r er e c a l c u l a t e dt oa c h i e v e i i 安徽大学硕士论文 b e t t e re f f e c t t h ei t e r a t i v e n e s so fs a m p l e si sn o tn c o d e c l t h e r e f o r e ，t h ep r o b l e m s ， s u c h 硒t h ec h o i c eo f i n i t i a ls a m p l ea n dt h ec l u s t e r i n gs p e e d , a r es o l v e d w h i c hc a r l n o tb es o l v e dw i t ho t h e ra l g o r i t h m s ( 3 ) f i n a l l bt h ec o v e r i n gc l u s t e r i n ga l g o r i t h mi sa p p l i e dt od r u g sm a r k e t i n g i nm e d i c a lb u s i n e s sc o m p a n y , t h ee x p e r i m e n t si n d i c a t et h ep r a c t i c a b i l i t ya n d e f f e c t i v e n e s s k e yw o r d s ：d a t am i n i n gc l u s t e r i n gc o v e r i n gc l u s t e r i n ga l g o r i t h m a r t i f i c i a ln e u r a ln e t w o r k i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名箱 坂缸 签字日期：埘年r 月护日 学位论文版权使用授权书 本学位论文作者完全了解宴镐匙嘻有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权耋物以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者挠拟祆锄始按蕊翠 签字日期：j 町年r 月p 日签字日期：2 防了年j 月，o 日 学位论文作者毕业去向： 工作单位：电话： 通讯地址：邮编： 第1 章绪论 第1 章绪论 本章首先阐明了本文所选课题的研究背景及其所具有的研究价值，对数 据挖掘、聚类分析的基本概念进行了简要介绍，然后指出了本文的组织结构。 l 。1 本文的选题背景与研究意义 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们可以 非常方便地获取和存储大量的数据。面对大规模的海量的数据，传统的数据 分析工兵( 如管理信息系统) 只能进行一些表层的处理( 如查询、统计等) ， 而不能获得数据之间的内在关系和隐含的信息。为了摆脱“数据丰富，知识 贫乏”的困境，人们迫切霈要一种能够智能地自动地把数据转换成有用信息 和知识的技术和工具，这种对强有力数据分析工具的迫切需求使得数据挖掘 技术应运而生。 聚类是一种重要的数据分析技术，搜索并识别一个有限豹种类集合或簇 集合，从而描述数据。聚类分析作为统计学的一个分支，已经被广泛研究了 许多年。而且，聚类分析也已经广泛地应用到诸多领域中，包括模式识别、 数据分析、图像处理以及市场研究m 。通过蒙类，入们能够识别密集的和稀疏 的区域，因而发现全局的分布模式，以及数据属性之间的有趣的相互关系。 在商务上，聚类能帮助市场分析人员从客户基本信息痒中发现不同的客户群， 并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导 植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类 在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及根据房 屋的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。 作为一个数据挖掘的重要功能，聚类分析能作为一个独立的工具来获得 数据的分布情况，观察每个类的特点，集中对特定的某些类做进一步的分析。 如对w e b 上的文档进行分类，以发现信息。此外，聚类分析也可以作为其它 算法( 如关联分析和分类) 的预处理步骤，这些算法再在生成的类上进行处 理。这样可以大大提商这些算法豹执行效率。因此聚类分析已经成为数据挖 掘领域中一个非常活跃的研究课题。卅。鉴于以上认识，本文对传统聚类算法 基于覆盖的聚粪算法研究 进行了分析和研究，在此基础上提出了新的聚类算法基于覆盖的聚类算 法。为构建离效的数据挖掘聚类算法做出了自己的努力。 j 。2 数据挖掘概述 数据挖掘( d a t am i n i n g ，d m ) 的定义与另一个常用的术语“数据库知识 发现”( 常简称为知识发现，k n o w l e d g ed i s c o v e z “li nd a t a b a s e s ，k d d ) 密切 相关。一和观点陆吨1 认为知识发现是从大规模数据中发现知识的整个过程，而 数据挖掘只是这个过程的一个重要步骤。另一种观点9 1 ”则认为两者是等价的 概念，均指发现知识的全过程。本文采用文献 9 的观点，认为数据控掘从理 论和技术上继承了知识发现领域的成果，同时又有着独特的内涵。数据挖掘 更着眼于设计赢效的算法以达到从巨量数据中发现知识的目的。 l 。2 。1 数据挖掘定义h 3 数据挖掘( d a t am i n i n g ) 的具体定为“数据挖掘是一个从大型数据库中 抽取隐含的、事先未知的、其有潜在有用的信息或知识的非平凡过程”。它的 二作流程由以下步骤组成n 2 1 ： 固+ 奇圆茹 蹲e 簖 h 挫国辘冠巍捌，琏i 瞽曲1 1 j 鼍 图1 1 数据挖掘的一般过程 ( 1 ) 数据预处理 k d d 的处理对象是大量的数据，这些数据一般存储在数据库系统中，是长 期积累的结果。但往往不适合直接在这些数据上面进行知识挖掘，需要做数 据准备工作，一般来说针对源数据进行的数据准备主要包括三方面的内容： 1 ) 数据选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于 数据挖掘应用的数据。 2 ) 数据清理 现实世界的数据一般是不完整的和不一般的。数据清理例程试图填充空 缺的值，识刹孤立点、消除噪声，并纠正数据中的不一致。 2 第1 章绪论 3 ) 数据转换 将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的，建 立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 4 ) 数据归约 数据归约得到数据集的压缩表示，它通常比原数据集小得多，数据归约 必然会损失数据集中部分信息，当损失的信息与挖掘目的相关性不大时，采 用归约后的数据集能够产生同样的( 或几乎同样的) 分析结果。 数据预处理是k d d 的第一个步骤，也是比较重要的一个步骤。数据准备 是否做好将影响到数据挖掘的效率和准确度以及最终模式的有效性。 ( 2 ) 数据挖掘 数据挖掘是k d d 最关键的步骤，也是技术难点所在。研究k d d 的人员中 大部分都在研究数据挖掘技术，采用较多的技术有决策树、分类、隳类、粗 糙集、关联规则、神经网络、遗传算法等。数据挖掘根据k d d 的目标，选取 相应算法的参数，分祈数据，得到可能形成知识的模式模型。 ( 3 ) 评估、解释模式模型 上面通过数据挖掘得到的模式模型，有可能是没有实际意义或没有实用 价值的，也有可能是其不能准确反映数据的真实意义，甚至在某些情况下是 与事实相反的，因此需要评估，确定哪些是有效的、有用的模式。评估可以 根据用户多年的经验，有些模式也可以直接用数据来检验其准确性，这个步 骤还包括把模式以易于理解的方式里现给用户。 ( 4 ) 巩固知识，运用知识 用户理解的、并被认为是符合实际和有价值的模式模型形成了知识。在 发现知识的同时还要注意对知识做一致性检查，解决与以前得到的知识互相 冲突、矛盾的地方，使知识得到巩固。发现知识是为了运用，如何使知识能 被运用也是k d d 的步骤之。运用知识有两种方法：一种是只需看知识所描 述的关系或结果，就可以对决策提供支持；另一种是要求对新的数据运用知 识，由此可能产生新的问题，而需要对知识傲进一步的优化。 k d d 过程可能需要多次的循环反复，每一个步骤一旦与预期目标不符，都 要回到前面的步骤，重新调整，重薪执行。 3 基于覆盖的聚类算法研究 1 2 2 数据挖掘的封的 通过数据挖掘，可从数据库中挖掘出有意义的知识、规律、或更高层次 的信息，笋可以从多个角度对其进行浏览察看。所挖掘出的知识可以帮助进 行挟簧支持、过程控制、信息管理、查询处理等等。因此数据挖掘被认为是 数据库系统最重要的前沿研究领域之一，也是信息工业中最富有前景的数据 库应用领域之一。 数据挖掘技术在企业市场营销中得到了比较普遍的应用，通过收集、加 二：和处理涉及消费者消费行为的大量信息，确定特定消费群体或个体的兴趣、 消费习惯、消费倾向和消费需求，进而推断出相应消费群体或个体下一步豹 消费行为，然后以此为基础，对所识别出来的消费群体进行特定内容的定向 营销，这与传统手段相比，节省了营销成本，提高了营销效果，从而为企业 辛 来更多的利润。 1 。2 。3 数据挖掘豹分类 由于数据挖掘源于多个学科，因此数据挖掘研究产生了大量的、各种不 同类型的数据挖掘系统。因此，就需要对数据挖掘系统给出一个清楚的分类。 其中，根据挖掘知识类型，可以分为关联分析、分类和预测、聚类分析、特 征化和区分、孤立点分析、演变分析等等“。 特征提取 特征提取目的是对数据进行浓缩，给出它的紧凑描述。作为一种数据挖 掘任务，特征提取不是数据的简单枚举，而是产生数据的特征化和 b 较描述， 其中的特 芷化提供给定数据汇集的简洁汇总，而概念或类的比较则提供两个 或多个数据汇集的比较描述。 关联分析 关联分析是指在数据库的记录或对象间抽取关联性。它展示了数据闻未 知的依赖关系。根据这种关联性就可从任一数据对象的信息来推断另一数据 对象的信息。关联性是一种统计意义上的关系，并以置信度因子衡量关联的程 度。因此，为了发现出有意义的关联规则，需要给定两个阈值：最小支持度和 摄小可信度。目前，关联分析研究已经从单一概念层次关联规则豹发现发展 4 第1 章绪论 到多个概念层次的关联规则的发现。 分类分析 分类是最基本的一种认知形式。数据分类就是对数据集中的每一类数据， 挖掘出关于该类数据的描述或模型。而这些数据库中的类是事先利用训练数 据建立起来的。作为数据挖掘的一个重要主题、数据分类在统计学、机器学 习、人工智能等领域中得到了较旱的研究，只是近些年来，人们才将它与数 据库技术结合起来解决实际问题。在数据挖掘中，分类算法的研究成果较多， 常用的数据分类算法有：c a r t 、c 4 5 、i d 3 ，s l i q 等。 聚类分析 在机器学习中，数据分类称监督学习，而数据聚类则称为非监督学习， 两者所采用的方法相差甚远。数据聚类是将物理的或抽象的对象分成几个群 体，在每个群体内部、对象之间具有较高的相似性，丽在不同的群体之间， 相似性则比较低。一般地，一个群体也就是一个类，它与数据分类不同的是， 蒙类结果主要基于当前所处理的数据，我们事先并不知道类耳结构及每个对 象所属的类别。另外，数据聚类计算量巨大，其时间复杂度也要比数据分类 大很多。后面我们会对聚类的相关知识进行详细的讨论。 在解决实际问题时，经常要同时使用多种模式。分类分析和特征提取是 使用最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督 知识，因为在建立模式前数据的结果是己知的，可以直接用来检测模式的准 确性，模式的产生是在受监督的情况下进行的。一般在建立这些模式时，使 用一部分数据作为样本，用另一部分数据来检验、校正模式。聚类分析、关 联分析、序列模式分析则是非监督知识，因为在模式建立前结果是未知的， 模式的产生不受任何监督。 。3 聚类分折概述 1 3 1 桨类分析酌定义 “物以类聚，入以群分”，聚类是人类一项最基本的认识活动。通过适当 聚类，事物才自便于研究，事物的内部规律才可能为人类所了解掌握。聚类 基于覆盖的聚共算法研究 分析又称为群分析和点群分析，是指将物理或抽象对象的集合分组成为由类 似豹对象组成的多个类的过程。简单的说，就是识别出一组聚类规则，将数 据分成若干类。它与分类分析不同，聚类分祈在对数据对象划分类别之前并 ? ；明确地知道划分规则，要通过对聚类结果的分析才能最终得出。由隳类所 生成的簇( c l u s t e r ) 是一组数据对象的集合，这些对象与同一个簇中的对象 相似，与其他簇中的对象楣异或称作簇内较大的相似性和簇间较大的相异性。 在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一。 它已经被广泛的研究了许多年，主要集中在基于距离的聚类分析。它主要研 ；基于几何距离的聚类，如欧式距离、明考斯基距离等。这种聚类方法是一 种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分：因此它 要求所有的数据必须预先给定，而不能动态增加新的数据对象。聚类分析方 法不具有线性的计算复杂度，难以适用于数据库非常大的情况。 在机器学习中，聚类称作无监督或无教师归纳：因为和分类学习相比， 分类学习的例子或数据对象有类别标记，丽要聚类的例子则没有标记，需要 臼聚类学习算法来自动确定。很多人工智能文献中，聚类也称概念聚类：因 为这里的距离不再是统计方法中的几何距离，丽是根据概念的描述来确定的。 当聚类对象可以动态增加时，概念聚类贝g 称是概念形成。 在神经网络中，有一类监督学习方法：自组织神经网络方法，如k o h o n e n 匀组织特征映射网络、竞争学习网络等等，在数据挖掘领域里，神经网络聚 类方法主要是自组织特征映射方法和b p 神经网络方法，i b m 在其发布的数据 挖掘自皮书中就特别提到了使用前者进行数据库聚类分割。 l ，3 ，2 聚类分析算法分类 在聚类方法划分上，目前存在着数于个算法，主要的分类方法有： ( 1 ) 按照样本调整状态聚类分析算法可以划分为系统聚类和动态聚类。 在聚类时把待聚类的每一个样本都自成一类，然后计算类与类之间的距离， 把距离最小的两个样本并为一类，此后，重新计算类与类之间豹距离，并把 距离最小的两类合并成一新类。如此下去直至所有的样本归为一类。这种聚 类方法称为系统聚类法，它又细分为八种，即最短距离法、最长距离法、中 第1 章绪论 间距离法、重心法、类平均法、可变类平均法、可变法、离差平方和法。若 在聚类时，根据经验或专业知识，先把所有的样本大致分为几类，然后按照 某种原则逐步进行调整，直到比较合理为止，这种聚类方法称为动态聚类法， 如k - m e a n s 算法。 ( 2 ) 按照计算方法的新旧聚类分析算法可化为传统算法和现代算法。传 统算法比如k - m e a n s 法、l b g 法等，这些算法形成较早，且都有着广泛应用。 随着计算机的发展，很多新算法得以研究应用，比如神经网络( n n ) ，遗传算 法( g a ) ，模拟退火( s a ) 这些算法在聚类分析中不断得以应用，从而聚类分 析算法中产生大量现代算法。 ( 3 ) 按照算法的应用来划分聚类分析算法可化为单一算法和混合算法。 过去我们常常研究某个算法来进行分类，但是聚类问题条件复杂，常常某个 单独算法具有这样那样的缺点，于是混合算法就出现了，它们综合了各个算 法的优点，取优补缺，使算法更有效。 聚类分析算法还有许多其他的划分，比如，分割聚类( 如k - m e a n s 算法) ， 分层聚类( b r i c h ，c u r e ，r o c k ，c h a n g e l e o n ) ，基于密度的聚类( d b s c a n ) ，基 于网格的聚类( s t r i n g ) ，基于模型的聚类( 统计学方法和神经网络法) 。 1 3 3 聚类分析的基本知识 1 3 3 1 聚类算法的一般步骤 聚类分析算法一般经过特征提取，聚类策 略，选取阐值三个步骤： ( 1 ) 特征提取。我们一般要从样本中提 取我们感兴趣的特征，使用这些特征进行聚类 分析计算，特征的选取将直接影响聚类的结果， 如果我们第一步就选择了与聚类要求根本无关 的量，即使后继步骤多么正确，都将会导致错 误的聚类结果。合理的特征选取应当使得分类 结果中同类样本距离较小，异类样本距离较大。 我们必须去除我们不感兴趣的特征，但是这些 7 圈1 2 聚类的一般步骤 基于覆盖的聚类算法研究 特征往往具有鲜明的个性! 数据千差万别，为了使运算方便，往往把这些数 据映射到 0 ，1 区间，即规格化。我们说的特征提取，一般包括从样本提 取原始特征并对其进行规格化。规格化后的数据一般是n * m 矩阵，即n 个样 本，每个样本含有i l l 维特征。这n * m 矩阵中的元素均是介于 0 ，1 之问的数据。 x i x l l 2k 毛， 屯l x 2 2 kx 2 m k k k k 工m 2k _ 其中0 嘞1 。 ( 2 ) 聚类策略。根据聚类分析的需要合理选取聚类算法进行聚类运算。 目前聚类分析算法有数千种之多，但是很多算 法仍是不成熟，选取什么聚类分析算法将直接 影响聚类的结果和结果的有效性。 聚类策略实际上是根据样本特征将样本进 行归类，经过规格化后的数据已经没有其实际 意义，聚类过程不需要再有知识领域的专家参 与。聚类结果可以画成一个谱系图。 j 莆 o 1z 3l5 7 图1 3 谱系示意图 ( 3 ) 选取阈值。这一步里我们要选取合理的阙值，由于分类要具有现实 l 广l m o 1z 345 7 图1 4 谱系闻值选取示意圉 对样本的了解。 意义，阈值的选取往往需要有领域专家经验 和领域知识，结合具体情况和应用场所决定 阈值的大小。没有领域专家的参与，仅仅根 据聚类谱系图寻找阈值，或者求最小生成树， 往往不能得到满意的结果。领域专家结合领 域知识往往可阱进一步分析数据，从而加深 1 3 3 2 聚类的定义 聚类的非形式化定义如下： 定义：聚类是一种在无导师的情况下根据对象问的相似程度自动地将其 分割为一组有意义的类的处理过程。 8 第1 章绪论 对于上面聚类的定义有以下几点需要说明： ( 1 ) 无导师是指待分类对象没有预先给定的类标示，这是聚类与分类最 大区别。 ( 2 ) 对象在数据库中包括记录和属性，对记录的聚类称为q 型聚类，对 属性的聚类称为r 型聚类。 ( 3 ) 有意义是指聚类的结果应该反映原始数据的自然结构特征。一个好 的聚类要使类内( i n t r a - c l u s t e r ) 相似性尽可能的大，类澜( i n t e r c l u s t e r ) 相似性尽可能的小，同时希望聚类能发现数据中一些隐含特征。 ( 4 ) 聚类结构的好坏取决于算法设计者对聚类的具体定义和表示，对象 问的相似度定义及聚类算法的具体实现。 聚类的严格数学描述如下“”： 被研究的样本集为e ，类c 定义为e 的一个非空子集， 即c c 占且c 移 聚类就是满足下列两个条件的类e 。，g ，& 盼集合 1 ，c 1 u c 2 u u c t = e 2 。en c ，= ( 对任意i j ) 由第一个条件可知，样本集e 中的每个样本必定属于某一个类；由第二 个条件可知，样本集e 中的每个样本最多只属于一个类。 1 ，3 。3 。3 祥晶与指标 设有n 个持分类样本，有m 个特性指标，得到一个样本矩阵x ，记为； 工= 五】 五2 z 2 1x 2 2 t dk 2 薯。 也。 -1- x 为了对它们进行分类，我们称矩阵x 中每一行为一个样品，磊，如，吃 为第1 个样本的m 个特性指标。而矩阵x 中的每一列称为一个特性指标，如 第j 列指标为，t 。，x 二，分类的对象是就样品而言的，即一个样品成包 基于覆盖的聚类算法研究 括m 个指标，换言之，我们研究的对象样品，其特征可用1 i 1 个指标来表 示。从向量空间的观点看，样品实质上就是m 维空间上一个点。 1 3 3 4 对数据规格化计算方法的分析 由于m 个指标的量纲和数量级不同，直接利用原始数据进行计算，就可 能提高某些数量级特别大的特性指标对分类的作用，而降低甚至排斥某些数 量级较小的特性的作用，导致一个指标只要改变一下单位，也会改变分类结 果。所以，必须对原始数据进行无量纲化处理，使每一指标值统一于某种相 同的数据特性范围。 设一分类问题有n 个待分类样本，有1 1 1 个特性指标，则数据矩阵如下： x = ix 1 2 x 2 1x 2 2 kk x n lx n 2 k而， k x 2 m kk k x 删 并规定毛o ，文献 1 8 提出了以下6 种规格化方法 ( 1 ) 标准差规格化 x 一x f 2 言 式中i = 去喜砖，t = i 吾阿 ( 2 ) 极大值规格化 工 2 。 一 式中t 。= m a x k ，工：，aa ，) ( 3 ) 极差规格化 l ：喜二兰警 。 x ，一一m 式中t 。意义同上，t 。= m i i l k ，t ，a ax j ( 4 ) 均值规格化 ( 1 2 ) ( 1 3 ) 第1 章缡论 y ：垒( 1 。4 ) x 。2 寺 、1 “7 石j ( 5 ) 中心规格化 为= 舀一； ( 1 。5 ) ( 6 ) 对数规格化 = l o g x ； ( 1 6 ) 显然公式( i 5 ) 、( 1 。6 ) 不能达到无量纲化的目的。容易推导出，采用 方法( 1 ) ( 4 ) 变换后数据特征如表1 1 所示，一个较好的方法，在实现 无量纲化的同时，还应保持原有各指标的分辨力，即变异性大小。方法( 1 ) 变换后，各指标的均值与标准差完全相同。分辨力已被完全同化，方法( 3 ) 一般也存缩小指标间变异程度差异的作用。分辨力也部分同化，只有方法( 2 ) 、 l 4 ) 的变换，不改变原有数据的变异程度。但方法( 2 ) 易受个别极端值的 影响，故方法( 4 ) 应是最好的方法。 表1 1 方法数据范围平均值标准差变异系数 。 原始数据 不定 絮 o lc 巧 ( 1 )一2 2 ol o - ( 2 )o 1 o5 z 算术平均最小法 m i n ( x , , ，如) = 竿i 一 寺( 以+ 以) 1 一、“ j “ t 1 ( 1 3 ) 几何平均最小法 ( 1 2 5 ) m i n ( x * ，x 。k 、 ：土l 一 ( 1 2 6 ) q 羔属瓦 、。 上述式中，c 为一特定正数，使0 = 1 ，o 1 。 文献 1 8 将以上1 3 种方法分为3 类，方法( 1 ) 、( 2 ) 、( 3 ) 、( 4 ) 、( 5 ) 、 ( 7 ) 为距离法：( 6 ) 、( 8 ) 、( 9 ) 、( 1 0 ) 为相似系数法；( 1 1 ) 、( 1 2 ) 、( 1 3 ) 为贴近度法。这种分类方法一方面把一些性质不同的相似性归为一类，如将 ( 7 ) 归入距离法，将( 6 ) 归入相似系数法，而实际上把( 7 ) 归入贴近度法， 把( 6 ) 归入距离法更合适。另一方面也没有反映各类相似性的实质。 1 3 4 聚类算法研究面临的挑战 聚类算法研究是一个具有很强挑战性的研究领域，它的一些潜在应用对 聚类算法提出了特别的要求“1 ： ( 1 ) 可伸缩性( s c a l a b i l i t y ) 实际应用要求聚类算法能够处理大数据集， 且时间复杂度不能太高( 最好是多项式时间) ，消耗的内存空间也有限，目前， 为了将算法拓展到超大数据库( v l d b ) 领域，研究人员已经进行了许多有益 的尝试，包括：增量式挖掘、可靠的采样、数据挤压( d a t as q u a s h i n g ) 等， 其中，数据挤压技术首先通过扫描数据来获得数据的统计信息，然后在这些 统计信息的基础上进行聚类分析。比如b i r c h 算法中使用c f 树就是属于数据 挤压技术。 ( 2 ) 能够处理不同类型的属性。现实中的数据对象已远远超出关系型数据 的范畴，比如空间数据、多媒体数据、遗传学数据、时间序列数据、文本数 据、万维网上的数据、以及目前逐渐兴起的数据流，这些数据对象的属性类 基于疆盖的聚类算法研究 型往往是由多种数据类型综合面成的。 ( 3 ) 能够发现任意形状的簇 ( 4 ) 尽量减少用于决定输入参数的领域知识。 ( 5 ) 能够处理噪声数据及孤立点。 ( 6 ) 对输入数据记录的顺序不敏感。 ( 7 ) 高维性( h i g h d i m e n s i o n a l ) 。一个数据集可能包含若干个维，较高的 缝数给聚类分析带来两个问题；首先，不相关的属性削弱了数据会聚豹趋势， 使得数据分布非常稀疏，尽管这种情况在低维空间中并不多见，但是随着维 数的增加，不相关属性的出现概率及数量也会增加，最后导致数据空间中几 乎j ；存在簇，其次，高维使得在低维中很有效的区分数据标准在高维空间中 矢效了。譬如在高维空间中，数据点到最近邻点的距离与到其他点的距离没 多少分别，从而导致最近邻查询在高维空间中不稳定，此时若根据接近度 哭划分簇，结果是不可信的。 ( 8 ) 能够根据用户指定的约束条件进彳亍聚粪。 ( 9 ) 聚类结果具有可解释性和可用性。 上述的要求使目前聚类算法研究的热点集中到了研究有效适用于大型数 据库的可伸缩性聚类算法，能够识别复杂形状的簇的聚类算法、高维聚类分 析算法以及针对大型数据库中混合数值的聚类算法。 1 。4 本论文韵组织 聚类分析既可以作为单独的挖掘工具以发现数据源的数据分布信息，也 可以作为其他数据挖掘算法的个预处理步骤，因此研究如何提高聚类算法 的性能具有重要的意义。本文首先介绍了聚类分析的有关概念，然后详细分 析：三种传统的聚类算法基于统计理论的系统聚类算法、基于划分的动 态聚类( k - m e a n s 算法) 及基于矢量的l b t 3 算法，分别讨论了每种算法的思想、 女i 程及性能分析，同时探讨了基于覆盖的神经网络分类算法，并由此启发将 覆盖算法用于聚类分析，结合最短距离系统聚类算法提出了一种新的基于覆 盖的聚类算法( c c a ) ，并将其应用分类中，通过与传统聚类算法的性能相比， 证明了这种算法的可行性和有效性。 第1 章绪论 本文组织如下； 第一章绪论部分首先介绍了课题研究的背景、意义以及数据挖掘的有关 知识，然后详细分析了聚类的定义，聚类分祈算法的分类、聚类分析的基本 知识及面临的挑战，最后给出本文的组织结构。 第二章系统介绍了三种经典的聚类算法：基于统计理论的系统聚类法的8 种算法、基于划分的动态聚类法的k - m e a n s 算法以及基于矢量的l b g 算法， 分别对每种算法的思想、步骤及算法的性能作了详细分析。 第三章详细介绍了覆盖算法用于分类的相关概念、原理，并在此基础上 提出了一种新的基于覆盖的聚类算法( c c a ) ，讨论了算法的思想、具体步骤、 性能分析，同时经实验证明了该算法的有效性和可行性。 第四章详细分析了覆盖聚类算法在医药公司药品销售数据中的应用。 第五章全文总结。对全文主要豹研究工作做了总结，并对以后的研究方 向作了进一步的展望。 17 基于覆盖的聚类算法研究 第望章传统聚类算法的分析与研究 三，。1 系统聚樊法 互l 。l 算法思想 系统聚类算法( 封e f 盯幽e a lc l u s t e r i n gm e f h o d ) 也称分层聚类法，是目前 i - 目内外使用最多的一种分类方法。凡是具有数值特征的变量和样品都可以通 过选择不同的距离和系统聚类方法而获得满意的数值分类效果。 我们可以把聚类问题看成是将n 个样本划分成c 类的划分序列。第一级 划分是把样本集分成n 个类，每个样本自成一类：第二级划分是把样本集分 成l 。1 个类等等，直到第n 级划分时，把样本集仅分成一个类。这种划分序 n 具有如下性质；在某一级划分时归入同一类的样本，在后面的划分时，它 们永远属于同一类。这里的类问合并通常选取类间距离最小的两类进行，根 据英问距离的不同定义，又有多种不同的具体方案。 曼i 。2 算法步骤 在系统聚类法中，我们设有n 个样品，每个样品有p 个变量，故每个样 一h a - ”f 以看成群中的一个点，n 个样品就组成酽中的n 个点，于是可以用样品 啷i 离来度量样品之间接近的程度。因为原始数据往往测量值相差悬殊，同 时受量纲能影响，所以在进行聚娄前，我们需要先对数据标准化，然后用标 准化后的数据计算距离。关于几种距离公式、相似系数等相关知识，本文已 经在第一章给予了说明，这里不再重复。 对n 个研究对象( 样品或指标) 进行系统聚类分析的步骤如下： ( 1 ) 构造n 个类，每个类只包含一个样品( 或指标) 。 ( 2 ) 铲算n 个样品( 或指标) 两两之间的距离 d ；，) ( 或相似系数) ，记作 d ”二汛。) 。 ( 3 ) 合并距离摄近的两类为一新类，称作第n + l 类，并取消刚合并的那 两娄，这样得到n 一1 类。 l 4 ) f 算新类与剩余各类的距离，其它各类间距不变，得到降一级的新 第2 章传统聚类算法的分析与研究 距离矩阵d “k ( d 。“) f 。) ，若类的个数等于l ，则转到步骤5 ，否则，回到 步骤3 。 ( 5 ) 得到聚类结果，画出聚类图。 在以上的步骤中，涉及两类计算方法的选择： 样品相似程度测度方法选择：即第2 步中确定样品( 或指标) 两两之闯 的距离( 或相似系数) 的方法问题。研究对象的样品( 指标) 分为间隔尺度、 有序尺度、名义尺度3 大类，其距离或相似性的度量方法有很大差异。使用 中用到最多的是间隔尺度的度量方法：欧氏距离、明考斯基距离、马氏距离 或夹角余弦系数、相关系数、指数相似系数等。对于有序尺度常用g 量 l 6 0 0 d m a n - k r u s k a l ) 来度量。对于名义尺度指标常用联列系数来度量。 类间距离测度方法选择：& 9 为第3 步中合并距离最近的两类为一新类的 方法问题。类间距离的衡量是系统聚类算法的核心。由于类的形状是多种多 样的，所以类与类之间的距离也有多种计算方法，根据类间距离的不同定义， 导出了多种不同的具体算法。最常用的系统聚类算法有最短距离法、最长距 离法、中间距离法、类平均法、重心距离法、可变类平均法、可变法、离差 平方和法( w a r d 法) 8 种算法。 下面我们约定用d ：。表示第i 个样本与第j 个样本之间的距离，用g 。，g 。， 表示类，其元素个数分别为n ，n 。，用珥。表示g 。类与g 。类间的距离。 1 、犀短距离法 类间距离的定义为d ，。= m i n d i j ，每一次都选取类间距离最小的两类进行合 并，当把g ，类与g 。类合并成一个新类g ，盾，即e = 岛，g 。) ，新类与其它类之间 韵距离计算可有迭代公式： d ，r t r _ i n d ，d n ) ( 2 。1 ) 具体算法步骤如下： 规定样本之间的距离，计算样本两两距离的对称阵，记为d ( o ) ，开始 每个样品自成一类，因此瑰。= d 蹦 选择d ( 0 ) 的最小元素，设为d 。将g ，与g 。合并为一类，记为g r = g ，g 。) ； 计算新类与其他类之间的距离； 基于覆盏的聚类算法研究 一一 。= 翱舀= 蚵n ，；r a 。，i ，呜n4 。，；恶翘略) r e i n 虹， 将d 。中的p ，q 行p ，q 列合并为一个新行新列，它对应c ，所得到的矩 阵! 州做d ( 1 ) ； 对d ( 1 ) 重复上面对d ( o ) 的两步，得到d ( 2 ) ，如此下去直到所有的元素 羧为一类，如果某一步中最小的元素不止一个，则对应这些最小元素的类同 时台并。 其它7 种方法聚类步骤与最短距离法基本类似，只是并类后的新类与其 它类的距离递推公式不同，从丽形成不同的聚类方法，下蟊一一给出它们类 问计算距离的公式。 2 、最长距离法 与最短距离法不同，最长距离法选取样本距离矩阵中最大值， ) 。= t r y l 霞k d o ，同样，每一次都选取类间距离最小的两类合并，当把g p 类与 2 5 0 ，6 0 “ 此同时g q 类合并成一个额类g r