（计算机软件与理论专业论文）基于距离的聚类和孤立点检测算法研究.pdf

摘要 摘要 数据挖掘技术可以从大量数据中发现潜在的、有价值的知识，它给人们在信息 时代所积累的海量数据赋予了新的意义。随着数据挖掘技术的迅速发展，作为其重 要组成部分，聚类分析和孤立点检测技术已经广泛应用于模式识别、数据分析、图 像处理、市场研究等许多领域。聚类及孤立点检测算法研究已经成为数据挖掘研究 领域中非常活跃的一个研究课题。 本文介绍了数据挖掘理论，对聚类及孤立点检测算法进行了深入地分析研究。 在分析基于距离和基于密度的聚类算法的基础上，提出了基于距离的聚类和孤立点 检测算法( d i s t a n c e b a s e dc l u s t e r i n ga n do u t l i e rd e t e c t i o na l g o r i t h m ) ，对算 法进行了较为详细的描述，阐述了算法中各个函数的功能，给出了程序流程图。该 算法根据距离阈值对数据点进行聚类，在聚类过程中记录所有数据点的密度，并根 据密度闽值确定数据点是否为孤立点，根据类中元素个数判定所得聚类是有效聚类 还是孤立点类。该算法时间复杂度是o ( n b ，空间复杂度是o ( n ) ，其中，n 是数据规 模。 本文使用v i s u a lc + + 6 0 实现了基于距离的聚类和孤立点检测算法、k - m e a n s 算法和d b s c a n 算法，做了大量的对比实验，包括聚类算法和孤立点检测正确性实验； 聚类算法和孤立点检测精度实验；算法执行时间实验；参数对聚类和孤立点检测结 果的影响实验；数据输入顺序对算法聚类和孤立点精度的影响实验；数据集密度对 算法有效性的影响等。 实验结果表明，基于距离的聚类和孤立点检测算法不仅能够对数据集进行正确 的聚类，同时能有效进行孤立点检测，有效解决了传统算法只能聚类或只能进行孤 立点检测的缺陷；比k - m e a n s 算法有更好的聚类精度；比d b s c a n 算法的聚类效率高； 适于均匀密度数据集、高密度数据集的聚类和孤立点检测：可以发现任意形状的聚 类，对噪音数据、数据输入顺序不敏感；对参数敏感；但对多密度数据集的聚类及 孤立点检测结果不理想。 总之基于距离的聚类和孤立点检测算法能够准确、有效的发现聚类和孤立点， 算法在执行效率、聚类及孤立点检测效果等方面有一定的优越性。 关键词：数据挖掘，聚类算法，孤立点检测，距离，密度 摘要 a b s t r a c t d a t am i n i n gt e c h n i q u e sc a nb eu s e dt of i n do u tp o t e n t i a la n du s e f u l k n o w l e d g ef r o mt h ev a s ta m o u n to fd a t a ，a n di tp l a y san e ws i g n i f i c a n tr o l e t ot h es t o r e dd a t ai nt h ei n f o t i m e s w i t ht h er a p i dd e v e l o p m e n to ft h ed a t a m i n i n gt e c h n i q u e s ，c l u s t e r i n ga n a l y s i sa n do u t li e rd e t e c t i o n ，a si m p o r t a n t p a r t so fd a t am i n i n g ，a r ew i d e l ya p p l l e dt ot h ef i e l d s s u c ha sp a t t e r n r e c o g n i t i o n ，d a t aa n a l y s i s ，i m a g ep r o c e s s i n g ，a n dm a r k e tr e s e a r c h r e s e a r c h o ne l u s t e r i n ga n a l y s i sa n do u t li e rd e t e c t i o na l g o r i t h m sh a sb e c o m ea h i g h l y a c t i v et o p i ci nt h ed a t am i n i n gr e s e a r c h i nt h i st h e s i s ，t h ea u t h o rp r e s e n t st h et h e o r yo fd a t am i n i n g ，a n dd e e p l y a n a l y z e st h ea l g o r i t h m so fc l u s t e r i n ga n do u t l i e r sd e t e c t i o n b a s e do nt h e a n a l y s i so fd i s t a n c e b a s e da n dd e n s i t y b a s e dc l u s t e r i n ga l g o r i t h m ，t h e a u t h o ra d v a n c e sd i s t a n c e b a s e dc l u s t e r i n ga n do u t l i e rd e t e c t i o na l g o r i t h m ( d b c o d ) ，e l a b o r a t e st h ei d e ao ft h ea l g o r i t h m ，e x p o u n d st h ef u n c t i o n so f a l g o r i t h m ，a n dd e s i g n sp r o g r a mf l o wc h a r t s t h ed b c o da l g o r i t h mr e c o r d st h e d a t u mp o i n t sb yd i s t a n c et h r e s h o l d ，c o u n t st h ed e n s i t yo fe v e r yd a t u mp o i n t i nc l u s t e r i n g ，i d e n t i f i e so u t l i e r sb yd e n s i t yt h r e s h o l d ，d e t e r m i n a t e sv a l i d c l u s t e ra n do u t l i e rc l u s t e rb yt h en u m b e ro fd a t u mp o i n t si ni t t h e c o m p u t a t i o n a lc o m p l e x i t yo ft h ed b c o da l g o r i t h mi s0 ( n 2 ) a n dt h es p a t i a l c o m p l e x i t yo ft h ea l g o r i t h mi s0 ( n ) 。w h e r eni st h en u m b e ro fd a t a s e to b j e c t s i nt h i st h e s i s ，w eh a v ed e v e l o p e dd b c o da l g o r i t h ma n di m p l e m e n t e di t u s i n gv i s u mc + + 6 0 f o rc o n t r a s te x p e r i m e n t s k m e a n sa n dd b s c a n a l g o r i t h m sa r ea l s oi m p l e m e n t e du s i n gv i s u a lc + + 6 0 w ec o n d u c t e das e r i e s o fe x p e r i m e n t s ，i n c l u d i n gt h ee x p e r i m e n to ft h ec o r r e c t n e s so fc l u s t e r i n g a n do u t li e rd e t e c t i o n ，t h ee x p e r i m e n to ft h ep r e c i s i o no fc l u s t e r i n ga n d o u t l i e rd e t e c t i o n t h ee x p e r i m e n to ft h er u n t i m e ，t h ee x p e r i m e n to ft h e e f f e c to fc l u s t e r i n ga n do u t li e rd e t e c t i o no np a r a m e t e r s ，t h ee x p e r i m e n t o ft h ei m p a c to fc l u s t e r i n ga n do u t l i e rd e t e c t i o np r e c i s i o nb yt h eo r d e r o fd a t ai n p u t ，a n dt h ee x p e r i m e n to ft h ee f f e c to ft h ea l g o r i t h mv a l i d n c s s b yt h ed e n s i t yc h a r a c t e ro fd a t a s e t a ss h o w ni nt h ee x p e r i m e n t a lr e s u l t s ，d b c o da l g o r i t h mc a nn o to n l y e l u s t e rt h ed a t a s e tp r o p e r l yb u tt e s to u t l i e r si nt h ed a t a s e t ，a n di t e f f e c t i v e l ys o l v e st h ep r o b l e mt h a tt r a d i t i o n a la l g o r i t h m sc a nc l u s t e ro n y o rf i n do u t l i e r so n l y ：t h ep r e c i s i o no fd b c o da l g o r i t h mi sb e t t e rt h a nt h a t o fk - m e a n s ：i t se f f i c i e n c yi sh i g h e rt h a nt h a to fd b s c a n ：i tw o r k sw e l lf o r e v e nd e n s i t yd a t a s e ta n dh i g hd e n s i t yd a t a s e t s ：i tc a nd i s c o r e rc l u s t e r so f a r b i t r a r ys h a p e s ：i ti ss e n s i t i v en o tt on o i s ea n do u t l i e rd a t ab u tt o p a r a m e t e rv a l u e s ：b u ti t i si m p e r f e c tt oc l u s t e ra n df i n do u t ii e r si n m u l t i d e n s i t yd a t a s e t 摘要 t os u mu p ，t h ed b c o da l g o r i t h mc a rf i n dc l u s t e r sa n do u t l i e r sa c c u r a t e l y a n dv a l i d l y ，a n dt h ea l g o r i t h mh a s s u p e r i o r i t i e si nt h ee f f i c i e n c ya n d p r e c i s i o no fc l u s t e r sa n do u t l i e r s k e yw o r d s ：d a t am i n i n g ，c l u s t e r i n ga l g o r i t h m s o u t l i e rd e t e c t i o n d i s t a n c e d e n s i t y i i i 郑重声明 矿7 8 2 2 1 2 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、 抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生 的一切法律责任和法律后果，特此郑重声明。 学位论文作者( 签名) ： 加d 岁年岁月2 - 0 日 第1 章弓l言 1 1 研究背景与意义 第1 章引言 由于计算技术和存储技术的飞速发展，使人们在短时间里就可以从各种信息源 搜集和存储大量的人工难以管理的资料。虽然现代数据库技术可以对这些资料进行 经济地存储，但还是需要一种技术来帮助人们分析、理解甚至可视化这些资料。因 此就产生了k d d ( 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 包括很多内容，其核心部分就是数据 挖掘( d a t am i n i n g ) 。近十多年来，数据挖掘逐渐成为数据库和人工智能等研究领 域的一个热点。 聚类( c l u s t e r i n g ) 是数据挖掘中重要组成部分，所谓聚类，就是将数据对象分组成 多个类或簇( c l u s t e r ) ，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对 象差别较大。聚类源于许多研究领域，包括数据挖掘，统计学，机器学习，空间数据 库，生物学和市场营销等。目前它已经广泛应用于模式识别、数据分析、图象处理和 市场分析等。 聚类已经被广泛地研究了许多年，迄今为止，研究人员已经提出了许多聚类算法， 大体上，主要的聚类算法可以分为基于划分的方法、基于层次的方法、基于密度的方 法、基于网格的方法、基于模型的方法。 孤立点检测是数据挖掘中的一项重要技术，其目标是发现数据集中行为异常的 少量的数据对象。在数据挖掘中，孤立点检测算法大体上可以分为：基于统计学的 方法、基于偏离的方法、基于距离的方法、基于密度的方法、基于聚类的方法、基 于小波的孤立点检测、局部孤立点等。 聚类和孤立点检测是非常有用的数据处理技术，该技术为将海量数据转换为信息 和知识提供了强有力的分析手段。我们相信聚类和孤立点检测理论具有广阔的发展空 间，今后将会在更多的领域发挥作用。 同时需要指出，虽然数据挖掘理论研究成果令人注目，数据挖掘技术非常丰富， 但是，这阻止不了对该领域知识的研究。所有聚类和孤立点检测算法不是万能的， 一种聚类算法或孤立点检测算法应用范围是有限的，在处理某种数据集可能是有效 的，而在处理其他的数据集可能会存在这样那样的问题；聚类分析和孤立点的研究 并不是孤立的，通常在聚类的过程中要决定如何处理孤立点的问题，检测孤立点也 要使用聚类的技术。但就目前已有的算法来看，聚类和孤立点的研究是分离的，在 研究聚类的过程中，对孤立点的处理只是简单的丢弃( 看作噪声) ，没有将聚类过程 和查找孤立点的过程有效地结合起来。单纯地使用某一个方法不一定能有效地解决 所有问题，这意味着需要其它方法补充，需要研究新的算法，可以尝试将聚类与孤 立点检测过程相结合来丰富算法的功能。 第1 章引言 r 1 2 研究内容与思路 针对上面的分析，本文就以下内容进行了研究： 1 对数据挖掘理论、聚类分析算法、孤立点检测算法、聚类与孤立点检测的关系 等进行了系统的研究提出了改进算法。 系统地研究了数据挖掘理论、聚类算法、孤立点检测算法，在研究聚类算法和孤 立点算法的基础上，将聚类和孤立点检测的过程相结合，提出了基于距离的聚类和孤 立点检测算法。 2 基于距离的聚类和孤立点检测算法的描述与实现。 对基于距离的聚类和孤立点检测算法进行了描述，对算法中的数据结构、函数 进行了说明，给出了程序流程图，并分析了该算法的时间复杂度和空间复杂度。用 v i s u a lc + + 6 o 编程实现了该算法算法。 3 对比实验及结果分析。 编程实现了k - m e a n s 、d b s c a n 两个算法做了多个对比实验，包括聚类及孤立 点检测正确性、精度、算法执行时间、参数设置、数据输入顺序、数据集密度等，对 实验结果进行对比分析，对算法进行测试、分析、评价。 1 3 论文组织结构 本文共分五章。其余部分按以下说明组织： 第二章系统研究了数据挖掘、聚类分析和孤立点检测理论，给出了一些基本概 念，重点分析了各种聚类算法和孤立点检测算法。 第三章在聚类算法和孤立点检测算法研究基础上，提出了基于距离的聚类和孤 立点检测算法对该算法进行了深入地分析。 第四章通过实验，分析了该算法的性能，并将该算法与k - m e a n s 、d b s c a n 的实 验结果进行了对比、分析。 第五章对前面研究工作进行了总结与展望，给出了本文的主要创新点，并提出 了今后的研究方向。 第2 章数据挖掘和聚类分析 第2 章数据挖掘和聚类分析 2 1 数据挖掘概述 随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的数 据急剧增加，可是能用于对这些数据进行分析处理的工具却很少。目前数据库系统 所能做到的只是对数据库中已有的数据进行存取和简单的操作，人们通过这些数据 所获得的信息量仅仅是整个数据库所包含的信息量的很少一部分，隐藏在这些数据 之后的更重要的信息是关于这些数据的整体特征的描述及对其发展趋势的预测，这 些信息在决策生成的过程中具有重要的参考价值。这就引起了对强有力的数据分析 工具的急切需求。 面对这种挑战，数据库中的知识发现( k d d ) 技术逐渐发展起来。k d d 就是从大量、 不完全、有噪声的异质模糊数据中挖掘隐含的潜在有用知识的过程，它不但能够学习 已有的知识，而且又可以发现未知的规律。同时，k d d 也是一门新兴的交叉学科，汇 聚了数据库、人工智能、统计、可视化和并行计算等不同领域的研究人员。 一般将k d d 中进行知识学习的阶段称为数据挖掘( d a t a m i n i n g ) ，它是整个数据 库中的知识发现过程中一个非常重要的处理环节，所以两者往往混用。一般而言。 在数据库、统计和数据分析等工程应用领域称为数据挖掘，而在人工智能和机器学 习界等研究领域人t f n f l 称之为数据库中的知识发现。本文将不加区分地使用两者。 2 1 1 数据挖掘概念 知识发现k d d 是指从大量数据中提取出可信的、新颖的、有效的、潜在有用 的并能被人理解的模式的非平凡处理过程。这种处理过程是一种高级的处理过程。 在上述定义中，数据是指有关事实的集合，记录和事物有关的原始信息。模式 是一个用语言来表示的一个表达式，它可用来描述数据集的某个子集。我们所说的 知识，是对数据包涵的信息更抽象的描述。对大量数据进行分析的过程，包括数据 准备、模式搜索、知识评价，以及反复的修改求精。该过程要求是非平儿的，意思 是要有一定程度的智能性、自动性( 仅仅给出所有数据的总和不能算作是一个发现过 程) 。有效性是指发现的模式对于新的数据仍保持有一定的可信度。新颖性要求发现 的模式应该是新的。潜在有用性是指发现的知识将来有实际效用，如用于决策支持 系统里可提高经济效益。最终可理解性要求发现的模式能被用户理解，目前它主要 体现在简洁性上”1 。 2 。1 2 数据挖掘过程 数据挖掘过程可粗略地分为按需选择数据、数据集成、数据预处理、数据转换、 挖掘过程以及模式评估和知识表示等。i “。 第2 章数据挖掘扣聚类分析 图2 1 数据挖掘的过程 ( 1 ) 数据选择 从数据源中检索与分析任务相关的数据。 ( 2 ) 数据集成 建立目标数据集。根据数据挖掘目标，从原始数据中选择相关数据集，并将不 同数据源中的数据集成起来，以确定数据挖掘的操作对象，需要解决平台、操作系 统和数据类型不同产生的数据物理格式差异。 ( 3 ) 数据预处理 数据集中不可避免地存在着不完整、不一致、不精确和重复的数据，这些数据 统称为脏数据。数据抽取之后须利用领域专门知识对脏数据进行清洗。通常采用基 于规则的方法、神经网络方法和模糊匹配技术分析多数据源数据之间的联系，然后 再对它们实旌相应的处理。 ( 4 ) 数据转换 根据分析任务目标，选用关键特征表示数据，并将数据通过汇总或聚集等操作 转换为适于数据挖掘处理的形式。 ( 5 ) 挖掘算法 使用智能方法提取数据模式。这些方法包括概括、分类、回归和聚类等。 ( 6 ) 模式评估 采用有关方法对数据挖掘发现的模式进行评价，根据某种兴趣度度量，识别表 示知识的真正兴趣的模式。 ( 7 ) 知识表示 使用可视化和知识表示技术，向用户提供挖掘的知识，帮助用户理解发现的模 式。 第2 章数据挖掘和聚类分析 由上述过程可知，整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途 中发现选择的数掘不太好，或使用的挖掘技术产生不了期望的结果，这时，用户需 要重复先前的过程，甚至从头重新开始。 基于这种观点，加拿大华裔科学家j i a w e ih a n 提出典型的数据挖掘系统具有以 下主要成分( 如图2 2 ) ： ( 1 ) 数据库、数据仓库或其它信息库这是一个或一组数据库、数据仓库、电子 表格或其它类型的信息库。可以在数据一l 进行数据清理和集成。 ( 2 ) 数据库或数据仓库服务器根据用户的数据挖掘请求，数据库或数掘仓库服 务器负责提取相关数据。 ( 3 ) 知识库这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这种知 识可能包括概念分层，用于将属性或属性值组织成不同的抽象层。用户信念方面的 知识也可以包含在内。可以使用这种知识，根据意外性评估模式的兴趣度。领域知 识的其它例子有兴趣度限制或闽值和元数据。 ( 4 ) 数据挖掘引擎这是数据挖掘系统的基本部分，由一组功能模块组成，用于 特征化、关联、分类、聚类分析以及演变和偏差分析。 ( 5 ) 模式评估模块通常，此成分使用兴趣度度量，并与数据挖掘模块交互，以 便将搜索聚焦在有趣的模式上。它可能使用兴趣度闽值过滤发现的模式。模式评估 模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。对于有 效的数据挖掘，建议尽可能深地将模式评估推进到挖掘过程之中，以便将搜索限制 在有兴趣的模式上。 ( 6 ) 图形用户界面本模块在用户和数据挖掘系统之间通信，允许用户与系统交 互，指定数据挖掘的任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结果进 行探索式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓库模式或数据结 构。评估挖掘的模式，以不同的形式对模式可视化。 图2 2 典型的数据挖掘系统结构 第2 章数据挖掘和聚类分析 2 1 3 数据挖掘的功链 数据挖掘的功能反映了数据挖掘算法发现的模式的种类。根据履行功能的不 同，我们将数据挖掘问题分为数据概括、联接分析、分类、聚类、依赖建模、孤立 点分析以及演变分析等几个类别。 ( i ) 数据概括 数据库数据是最基本的信息，不能满足不同层次的用户希望从不同的层次和角度 对数据进行处理或浏览的需求。数据概括是一种把数据库数据从低层次抽象到高层次 的过程，换言之，就是对数据进行浓缩，用紧凑形式重新对其进行表示。 ( 2 ) 联接分析 联接分析用于重新建立数据对象之间业已存在的隐含联系，这种联系有关联规 则和序列模式两种表现形式。关联规则反映的是同时频繁出现的数据对象之间的蕴 涵关系，序列模式表明的是时念数据中频繁出现的事件序列。 ( 3 ) 分类 数据分类是根掘一个分类模型，在数据库中的对象集合中找到一些共同的属性， 并把它们分成不同类型的过程。其目的在于根据历史数据自动创建能预测未来行为钓 分类规则。分类规则反映的是属性数据对象和类别标识之间的因果关系。在分类问题 中。待产生的类别的数目是事先知道的，而且，训练数据中同时包含有属性数据和类 别标识数据。 ( 4 ) 聚类 数据的聚类分析是根据使类内部的相似性最大，而使类问的相似性最小的原则 将一组数据分组( 没有预先定义的类属性) 。这种将实际的或抽象的对象分成相似对 象的类的分组过程叫做聚类。聚类分析有利于在大量对象集合上建立有意义的划分， 而这种划分是一种分而治之的方法，即将大规模的系统分解成较小的组成部分以简 化设计和实现。聚类也便于分类编制，将观察到的内容组织成类分层结构，把类似 的事件组织在一起。 ( 5 ) 依赖建模 依赖建模用于发现反映变量间非平凡依赖关系的模型。依赖模型逻辑上由结构 层和量化层两部分组成。结构层表明的是变量间的局部相互依赖关系，通常以图形 方式描述：而量化层则是对变量间依赖关系强弱的定量描述。利用依赖建模可以从 某一对象的信息推断另一对象的信息。 ( 6 ) 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这些 数据对象是孤立点( o u t li e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常而丢 弃。然而，在一些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那些更有趣。 孤立点数据分析称作孤立点挖掘( o u t l i e rm i n i n g ) 或孤立点检测( o u t l i e r d e t e c t i o n ) 。 ( 7 ) 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋 势，并对其建模。尽管也包括了时态数掘的分类、聚类和关联分析等，但时间序列 数据分析、序列或周期模式匹配和基于相似性的数据分析等是进化分析区别于其它 方法的特征。 6 第2 章数据挖掘和聚类分析 2 1 4 数据挖掘方法 数据挖掘方法研究旨在提供数据挖掘的方法论，制定实现知识发现目标的宏观策 略，几种方法可以只能解决一个数据挖掘问题。数据挖掘方法主要包括决策树方法、 遗传算法、神经网络方法、贝叶斯网络方法、粗糙集方法、规则归纳方法、数据库方 法、可视化方法等。另外还有模糊论方法和信息论方法等。其实，随着数据挖掘研究 的更加深入和应用的同益广泛，各种数据挖掘方法会相互融合，全新的数据挖掘方法 也会出现。因此，和其它许多领域一样，数据挖掘方法无法穷尽。 2 1 5 数据挖掘算法组成 数据挖掘算法是对某种数据挖掘方法的具体实现，可以看作是一些基本技术和原 理的综合体。数据挖掘算法一般由三个部分组成模型；性能准则：搜索算法。 数据挖掘有许多不同的算法。这些算法的区别在于它们作用的数据种类( 如文件、 事务数据库、事态数据库和空间数据库等) 和发现的知识类型( 如分类规则、聚类规则 和序列模式等) 各异。按照所发现知识类型的不同，比较成熟且应用广泛的数据挖掘 算法主要有：分类规则挖掘算法、聚类规则挖掘算法、关联规则挖掘算法、序列模式 挖掘算法。 2 1 6 复杂类型数据的挖掘 传统的数据挖掘技术面对的是以结构化数据为主的关系数据库、事务数据库和 数据仓库。随着数据处理工具、先进的数据库技术以及w w w 技术的迅速发展，大量 的形式各异的复杂类型的数据，如非结构化数据、超文本与多媒体类型的数据不断 涌现。因此，数据挖掘面临的一个重要难题就是如何针对复杂类型的数据的挖掘“3 。 这包括空间数据库挖掘、多媒体数据库挖掘、时序数据和序列数据的挖掘、文本数 据库挖掘、w e b 挖掘。 2 2 聚类分析 将物理或抽象对象的集合分组成由类似对象组成的多个类的过程被称为聚类。 聚类分析已经广泛地用在许多应用中，如图像处理、模式识剐、市场研究等。 通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的发布模式，以及数据 属性之间的有趣的相互关系。在商务上，聚类能帮助市场分析人员从客户基本库中 发现不同的客户群，并能用不同的购买模式来刻画不同的客户群的特征：在地理信 息系统中，通过聚类发现特征空间来建立主题索引：在空间数据挖掘中，检测并解 释空间中的簇：在网络服务方面，聚类能帮助人们对w e b 文档进行分类，以发现信 息。 作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据的发布 情况，观察每个簇的特点，集中对特定的某些簇做进一步的分析，此外，聚类分析 可以作为其他算法( 如特征和分类等) 的预处理步骤，这些算法再在生成的簇上进行 处理。例如，先用聚类算法对数据分类，再对生成的类进行特征抽取或利用生成的 类对其他数据进行分类。 第2 章数据挖掘和聚类分析 聚类分析的作用已经越来越受到人们的重视。已经成为数据挖掘研究领域中一 个非常活跃的研究课题。数据挖掘对聚类的典型要求“1 有：( 1 ) 可伸缩性：( 2 ) 处理 不同字段类型的能力；( 3 ) 发现具有任意形状的聚类的能力：( 4 ) 输入参数对领域知 识的弱依赖性：( 5 ) 能够处理异常数据；( 6 ) 结果对输入记录顺序的无关性；( 7 ) 处理 高维数据的能力：( 8 ) 增加限制条件后的聚类分析能力：( 9 ) 结果的可解释性和可用 性。 2 3 聚类分析中的数据类型 我们研究在聚类分析中经常出现的数据类型，以及如何对其进行预处理。假设 要聚类的数据集包含n 个数据对象，这些数据对象可能表示人、房子、文档、国家 等。许多基于内存的聚类算法选择如下两种有代表性的数据结构： 数据矩阵( d a t am a t t i x ，或称为对象与变量结构) 它用p 个变量( 也称为度量或 属性) 来表现n 个对象，例如用年龄、身高、体重、性别、种族等属性来表现对象“人”。 这种数据结构是关系表的形式，或者看成n p ( 1 3 个对象p 个变量) 的矩阵。 f ： x i l ： x m x l i x t p ： x u x 1 ： x ，x ( 2 1 ) 相异度矩阵( d i s s i m i l a r i t ym a t r i x ，或称为对象一对象结构) 存储n 个对象两 两之间的近似性，表现形式是n n 维的矩阵。 0 屯d 0 4 3 , 04 3 , 2 ) 0 礅1 ) 如2 ) 0 ( 2 2 ) 其中d ( i ，j ) 是对象i 和对象j 之间相异性的量化表示，通常为非负数， d ( i ，j ) = d ( j ，i ) ，d ( i ，i ) = 0 。对象i 和对象j 越相似或“接近”，则以d ( i ，j ) 越接 近于0 ，对象i 和对象j 的差异越大，则d ( i ，j ) 越大。 因为数据矩阵的行和列含义不同，所以它经常被称为二模矩阵，而相异度矩阵 的行和列代表同一个实体，所以它经常被称为单模矩阵。 许多聚类算法是以相异度矩阵为基础的。如果数据是以数据矩阵的形式给出， 可以将数据矩阵转化为相异度矩阵。有的聚类算法以相似度矩阵为基础，而不是相 异度矩阵。相似度矩阵通常用距离公式计算得到。 那么对不同的变量应该如何估量相异度呢? 不同的变量估量方法是不一样的。 区间标度变量是一个粗略线性标度的连续变量。典型的例子包括重量和高度， 经度和纬度坐标以及大气温度。 8 第2 章数据挖掘和聚类分析 选用的度量单位将直接影响聚类分析的结果。一般而言，选用的单位越小，交 量可能的值域就越大，这样对聚类结果的影响就越大。因此为了避免聚类结果对单 位选择的依赖，数据应当标准化。标准化处理后，对象间的相异度是基于距离来计 算的。最常用的距离度量方法是欧几里得距离，它的定义为： d ( f ，) = l 一x ，1 2 + 1 x ，：一x ，：1 2 + t 一十i x 驴一x 胪1 2 ( 2 3 ) 其中i = ( x x m ，x 。) 和1 3 = ( x mx m ，x j ，) 是两个p 维的数据对象。在饺 用欧几里得距离时，要特别注意样本诸测量值的选取，应是有效地反映类别属性的 特征。 另外两个著名的度量方法是曼哈坦距离： 4 i ，j ) = i x 1 - - x j l l + l x 。2 一x j2 i + + l x 十一x l ( 2 4 ) 和明考斯基距离： 4 i ，) = f ，一x 一”+ l x 。：- - x j 2 1 4 + + i x ，一x ，1 9 ( 2 j ) 可以看出，明考斯基距离是欧几里得距离和曼哈坦距离的概化，当q = l 时，它 表示曼哈坦距离：当q = 2 时它表示欧几里得距离。 如果对每个变量根据其重要性赋予一个权重，加权的欧几里得距离可以计算如 下：d ( f ，_ ，) = w 。i z ，一x 1 2 + w ：l x ，：- x j 2 1 2 + - + w ， x ，一x ，i 2 ( 2 6 ) 加权也可以用于曼哈坦距离和明考斯基距离。 二元变量一个二元变量只有两个状态：0 或者1 ，0 表示该变量为空，1 表示 该变量存在。例如，给出一个描述病人的变量s m o k e r ，1 表示病人抽烟，而0 表示 病人不抽烟。 如果二元变量有相同的权重，则可以得到一个两行两列的可能性表2 一l ，这个 表反映了两个对象的变量取值可能性情况。在表中，q 是对象i 和对象j 值若为1 的变量的数目，r 是对象i 值为1 而对象j 为0 的变量的数目，s 是对象i 值为0 而对于对象j 为1 的变量的数目，t 是对象i 和j 值都为0 的变量的数目。变量的 总数是p ，p = q + r + s + t 。 表2 1 二元变量可能性表 对象j l0求和 如果二元变量的两个状态是同等价值的，并有相同的权重，n - - - 元变量是对 称的。基于对称二元变量的相似度称为恒定的相似度，对恒定的相似度来说，评价 两个对象i 和j 的相异度的最著名的系数是简单匹配系数，其定义如下： d ( i ，j ) = 揣 ( 2 7j 如果二元变量的两个状态的输出不是同样重要，那么该二元变量是不对稼的。 例如一个疾病检查的肯定和否定的结果。根据惯例我们将比较重要的输出结果，通 常也是出现几率比较小的结果编码为l ，而将另一种结果编码为0 。给定两个不对 叮o q p p r 什 s q s 旷 和 0 求 缘对 第2 章数据挖掘和聚类分析 称的二元变量，两个都取1 的情况被认为比两个都取0 的情况更有意义。基于这样 变量的相似度被称为非恒定的相似度。对非恒定的相似度，最著名的评价系数是 j a c c a r d 系数，其定义为： - ，、 d v ，j j = ；嚣。 ( 2 8 ) 标称型、序数型和比例标度型变量 ( 1 ) 标称变量是二元变量的推广，它可以具有多于两个的状态值。例如 m a p c o l o r 是一个标称变量，它可能有五个状态：红色，黄色，绿色，粉红色和兰 色。 假设一个标称变量的状态数目是m 。每一个状态值可以用字母、符号或者一组 整数来表示，则两个对象i 和j 之间的相异度可以用简单匹配方法来计算： d ( f ，) = 等 ( 2 9 ) 这里m 是匹配数，即i 和j 取值相同的变量的数目，而p 是全部变量的数目。 ( 2 ) 序数型变量序数型变量可以是离散的，也可以是连续的。在连续型的序数 变量中，值的相对顺序是必要的，而其实际的大小则不重要。在相异度的计算中， 需要把每个变量的值域映射到 0 0 ，1 0 上，以便每个变量都有相同的权重。然后 可以采用距离的计算方法进行相异度的计算。 ( 3 ) 比例标度型变量比例标度型变量是非线性的标度取正的度量值。计算时可 以采用与处理区间标度变量相同的方法；也可以先进行对数变换，再进行计算：也 可以借用序数性变量，采用秩作为区间标度的值来对待。 混合类型的变量在许多真实的数据库中，对象是由混合类型的变量描述的。 一般来说，一个数据库可能包含上面列出的全部类型。 计算相异度时，一种方法是将变量按类型分组，对每种类型的变量进行单独聚 类分析，如果这些分析得到兼容的结果，这种方法是可行的。但是在实际的应用中， 这种情况是不大可能的，因为数据对象可能包含多种变量类型。另种方法是将所 有的变量一起处理，只进行次聚类分析。但是这需要将不同类型的变量组合在单 个相异度矩阵中，把所有有意义的变量转换到共同的值域区间 0 0 ，1 o 上，这样， 当描述对象的变量是不同类型时，对象之间的相异度也能够进行计算。 2 4 聚类算法综述 2 4 1 基于划分的聚类方法 给定一个包含n 个数据对象的数据集，以及要生成的簇的数目，一个划分的算 法将数据对象组织成k 个划分( k n ) ，其中每个划分代表一个簇。通常会采用一个 划分准则( 经常称为相似度函数) ，例如距离，以便在同一个簇中的对象是“相似的”， 而不同簇中的对象是“相异的”。 基于划分的聚类算法中，k - m e a n s ”3 算法最简单。给定k ，k - m e a n s 算法的处理 流程如下： 1 ) 随机的把所有对象分配到k 个非空的簇中； 第2 章数据挖掘和聚类分析 2 ) 计算每个簇的平均值，并用陔平均值代表相应的簇； 3 ) 将每个对象根据其与各个簇中心的距离。重新分配到与它最近的簇中； 4 ) 转第2 ) 步，直到准则函数收敛。 通常k - m e a n s 算法的准则函数采用平方误差准则，定义为 后= 二州i i x 吨i 2 ( 2 1 0 ) 其中e 是数据集中所有对象的平方误差的总和；p 是给定的数据对象，m 。是簇 c 的平均值( p 和m 都是多维的) 。这个准则的作用是使生成的簇尽可能地紧凑和独 立。 对处理大型数据集而言，k - m e a n s 算法是相对可伸缩的和高效的，因为算法的 复杂度为0 ( n t k ) ，并且k 和t 通常都远远小于n 。这里n 是数据对象的个数，k 是 簇的个数，t 是迭代的次数。k 平均算法通常终止于局部最优解。但是，k - m e a n s 算 法具有一些不足之处，如：只有当平均值有意义的情况下才能使用，对于分类变量 不适用；必须事先给定要生成的簇的个数；对“噪声”和异常数据敏感：不能发现 非凸面形状的数据。 k - m e a n s 算法的一些变种试图弥补k - m e a n s 算法的一些不足。这些变种主要在 下面几个方面作些变动：初始k 个平均值的选择、相异度的计算、计算簇的平均值 的策略。k 一模算法是k - m e a n s 算法的一个变种，它可以处理分类变量。k 一模算法用 模来替代平均值、用新的相异度计算方法来处理分类变量、用基于频率的方法来修 改簇的模。另一个变种k 一原型算法综合了k - m e a n s 算法和k 一模算法，能同时处理分 类变量和数值型变量。 k 一中心点算法与k - m e a n s 算法类似。k 一中心点算法用簇的中心点来代表簇，而 k - m e a n s 算法用簇中所有对象的平均值来代表簇。围绕中心点的划分方法 p a m ( p a r t i t i o n i n ga r o u n dm e d o i d s ) 是最早提出来的k 一中心点算法之一，它的基本 思想是，设定一个中心点的初始集合，然后反复的用非中心点对象来替代中心点对 象，以改进聚类的质量。p a m 算法可以用下面的过程来描述： 1 ) 随机选择k 个真实的数据对象来作为k 个簇的初始的中心点； 2 ) 将非中心点对象指派给离它最近的中心点所代表的簇； 3 ) 随机地选择非中心点对象h ，计算用h 替换中心对象i 的总代价r c 。如果 r c 。， o ，那么用h 替换i 作为中心对象，然后将每一个非中心点对象根据与中心点 的距离分配给离它最近的中心点： 4 ) 重复步骤2 ) 、3 ) ，直到聚类结果不发生变化。 p a m 算法的代价函数可以用平方误差函数来表示，定义为 r = ：。鸸怕一j 2 - i p - m 。1 2 j ( 2 1 1 ) 其中r c 。是用h 替换中心对象j 的总代价，p 是给定的数据对象。m 是簇c ，的中心 点，m 。是簇c 用h 替换j 作为中心对象后的中心点。 与k - m e a n s 算法相比，p a m 算法处理大型数据集时执行代价高，没有良好的可 伸缩性，但是它受数据中的“噪声”和“孤立点”的影响较小。c l a r a 算法( c 1 u s t e r i n g l a r g ea p p l i c a t i o n s ) 和c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o n r a n d o m i z e ds e a r c h ) 是出p a m 算法经过改进后得到的两个算法。c l a r a 算法适合处 第2 章数据挖掘和聚类分析 理大型数据集，该算法首先获得数据集的多个采样，然后在每个采样上使用p a m 算 法，最后返回最好的聚类结果作为输出。 c l a r a 算法的缺点是，效率依赖于采样的大小，而且，如果样本发生偏斜，基 于样本的一个好的聚类并不一定是整个数据集的一个好的聚类。与c l a r a 算法相比， c l a r a n s 算法可以改进聚类的质量和可伸缩性。c l a r a n s ”1 算法在搜索的每一步动态 地、随机地抽取一个样本，聚类过程可以被描述为对一个图的搜索，图中的每个节 点是一个潜在的解，即k 个中心点的集合。在替换了一个中心点后得到的结果被称 为当前结果的邻居。随机试探中心点寻找更好邻居的次数由用户限制。在搜索