聚类数据挖掘技术.ppt

《聚类数据挖掘技术.ppt》由会员分享，可在线阅读，更多相关《聚类数据挖掘技术.ppt（66页珍藏版）》请在金锄头文库上搜索。

1、第八章第八章 聚类数据挖掘技术聚类数据挖掘技术， 一、聚类一、聚类: :l按照数据之间的按照数据之间的相似性相似性，对数据集进行分组或分类，对数据集进行分组或分类（簇（簇, cluster）的过程，试图使类内差距最小化，的过程，试图使类内差距最小化，类间差距最大化。类间差距最大化。l利用聚类结果，可以提取数据集中隐藏的信息，对利用聚类结果，可以提取数据集中隐藏的信息，对未来数据进行未来数据进行预测和分类预测和分类。应用于数据挖掘、模式。应用于数据挖掘、模式识别、图像处理、经济学识别、图像处理、经济学“物以类聚，人以群分物以类聚，人以群分”l聚类分析源于许多研究领域，包括数据挖掘、聚类分析源于许

2、多研究领域，包括数据挖掘、统计学、机器学习、模式识别等。作为一个数统计学、机器学习、模式识别等。作为一个数据挖掘中的一个功能，聚类分析能作为一个独据挖掘中的一个功能，聚类分析能作为一个独立的工具来获得数据分布的情况，并且概括出立的工具来获得数据分布的情况，并且概括出每个簇的特点，或者集中注意力对特定的某些每个簇的特点，或者集中注意力对特定的某些簇做进一步的分析。簇做进一步的分析。l数据挖掘技术的一个突出的特点是处理巨大数据挖掘技术的一个突出的特点是处理巨大的、复杂的数据集，这对聚类分析技术提出了的、复杂的数据集，这对聚类分析技术提出了特殊的挑战，要求算法具有可伸缩性、处理不特殊的挑战，要求算法

3、具有可伸缩性、处理不同类型属性的能力、发现任意形状的类、处理同类型属性的能力、发现任意形状的类、处理高维数据的能力等。根据潜在的各项应用，数高维数据的能力等。根据潜在的各项应用，数据挖掘对聚类分析方法提出了不同要求。据挖掘对聚类分析方法提出了不同要求。二、聚类在数据挖掘中的典型应用：二、聚类在数据挖掘中的典型应用：n聚类分析可以作为其它算法的预处理步骤聚类分析可以作为其它算法的预处理步骤：利用聚类进：利用聚类进行数据预处理，可以获得数据的基本概况，在此基础上行数据预处理，可以获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也进行特征抽取或分类就可以提高精确度和挖掘效

4、率。也可将聚类结果用于进一步关联分析，以获得进一步的有可将聚类结果用于进一步关联分析，以获得进一步的有用信息。用信息。n可以作为一个独立的工具来获得数据的分布情况可以作为一个独立的工具来获得数据的分布情况：聚类：聚类分析是获得数据分布情况的有效方法。通过观察聚类得分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步到的每个簇的特点，可以集中对特定的某些簇作进一步分析。这在诸如市场细分、目标顾客定位、业绩估评、分析。这在诸如市场细分、目标顾客定位、业绩估评、生物种群划分等方面具有广阔的应用前景。生物种群划分等方面具有广阔的应用前景。n聚类分析可以完成孤

5、立点挖掘聚类分析可以完成孤立点挖掘：许多数据挖掘算法试图：许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。然而孤立点本身使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。着欺诈行为的存在。 广泛的应用领域广泛的应用领域l商务：商务：帮助市场分析人员从客户信息库中发现不同的帮助市场分析人员从客户信息库中发现不同的客户群客户群，用购买模式来刻画不同的客户群的特征用购买模式来刻画不同的客户群的特征l土地使用：土地使用：在地球观测数据库中识别土地使用情况相在地球观测数据库中识别土地使用

6、情况相似的地区似的地区l保险业：保险业：汽车保险单持有者的分组汽车保险单持有者的分组l城市规划：城市规划：根据根据房子的类型，价值和地理分布对房子房子的类型，价值和地理分布对房子分组分组l生物学：生物学：推导植物和动物的分类，对基因进行分类推导植物和动物的分类，对基因进行分类n聚类分析的目标就是形成的数据簇，并且满足聚类分析的目标就是形成的数据簇，并且满足下面两个条件：下面两个条件：n一个簇内的数据尽量相似（一个簇内的数据尽量相似（high high intra-classintra-class similaritysimilarity）；）；n不同簇的数据尽量不相似（不同簇的数据尽量不相似（

7、low low inter-classinter-class similaritysimilarity）。）。n衡量一个聚类分析算法质量，依靠：衡量一个聚类分析算法质量，依靠：n相似度测量机制是否合适。相似度测量机制是否合适。n是否能发现数据背后潜在的、手工难以发现的类知识。是否能发现数据背后潜在的、手工难以发现的类知识。三、聚类分析的目标三、聚类分析的目标: :四、聚类分析方法的分类四、聚类分析方法的分类: :n按照聚类的标准，聚类方法可分为如下两种：按照聚类的标准，聚类方法可分为如下两种：n统计聚类方法：这种聚类方法主要基于对象之间的几统计聚类方法：这种聚类方法主要基于对象之间的几何距离的

8、。何距离的。n概念聚类方法：概念聚类方法基于对象具有的概念进概念聚类方法：概念聚类方法基于对象具有的概念进行聚类。行聚类。n按照聚类算法所处理的数据类型，聚类方法可分为三种：按照聚类算法所处理的数据类型，聚类方法可分为三种：n数值型数据聚类方法：所分析的数据的属性只限于数数值型数据聚类方法：所分析的数据的属性只限于数值数据。值数据。n离散型数据聚类方法：所分析的数据的属性只限于离离散型数据聚类方法：所分析的数据的属性只限于离散型数据。散型数据。n混合型数据聚类方法：能同时处理数值和离散数据。混合型数据聚类方法：能同时处理数值和离散数据。n按照聚类的尺度，聚类方法可被分为以下三种：按照聚类的尺度

9、，聚类方法可被分为以下三种： n基于距离的聚类算法：用各式各样的距离来衡量数据基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度，如对象之间的相似度，如k k-means-means、k k-medoids-medoids、BIRCHBIRCH、CURECURE等算法。等算法。n基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。基于密度的聚类方法主要是依据合适的密度函数等。n基于互连性基于互连性(Linkage-Based)(Linkage-Based)的聚类算法：通常基于的聚类算法：通常基于图

10、或超图模型。高度连通的数据聚为一类。图或超图模型。高度连通的数据聚为一类。n按照聚类聚类分析算法的主要思路，可以被归纳为如下按照聚类聚类分析算法的主要思路，可以被归纳为如下几种。几种。n划分法（划分法（Partitioning MethodsPartitioning Methods）：）：基于一定标准构基于一定标准构建数据的划分。属于该类的聚类方法有：建数据的划分。属于该类的聚类方法有：k-meansk-means、k-k-modesmodes、k-prototypesk-prototypes、k-medoidsk-medoids、PAMPAM、CLARACLARA、CLARANSCLARAN

11、S等。等。n层次法（层次法（Hierarchical MethodsHierarchical Methods）：）：对给定数据对象对给定数据对象集合进行层次的分解。集合进行层次的分解。n密度法（密度法（density-based Methodsdensity-based Methods）：）：基于数据对象基于数据对象的相连密度评价。的相连密度评价。n网格法（网格法（Grid-based MethodsGrid-based Methods）：）：将数据空间划分成将数据空间划分成为有限个单元（为有限个单元（CellCell）的网格结构，基于网格结构进的网格结构，基于网格结构进行聚类。行聚类。n模型

12、法（模型法（Model-Based MethodsModel-Based Methods）：）：给每一个簇假定给每一个簇假定一个模型，然后去寻找能够很好的满足这个模型的数一个模型，然后去寻找能够很好的满足这个模型的数据集。据集。 五、五、数据相似性的度量数据相似性的度量-距离距离l距离越大，相似性越小。距离越大，相似性越小。l点间距离点间距离与与类间距离类间距离 类间距离基于点间距离计算类间距离基于点间距离计算l距离函数应同时满足距离函数应同时满足 1. d(i,j)0 2. d(i,i)= 0 3. d(i,j)= d(j,i) 4. d(i,j)d(i,k)+ d(k,j)常用点间距离常用

13、点间距离常用点间距离常用点间距离相异度相异度相异度相异度l欧式距离欧式距离l城区距离城区距离l切比雪夫距离切比雪夫距离l明科夫斯基距离明科夫斯基距离数据矢量数据矢量x=(x1,x2,xn), y=(y1,y2,yn).常用类间距离常用类间距离常用类间距离常用类间距离l最短距离法最短距离法l最长距离法最长距离法l类平均法类平均法l重心法重心法两个聚类两个聚类p和和q.六、聚类方法六、聚类方法l划分方法划分方法：构造数据的最优划分：构造数据的最优划分l层次方法层次方法：对数据进行层次分解或合并：对数据进行层次分解或合并l基于密度的方法基于密度的方法：（：（1）基于密度连通性，如）基于密度连通性，如

14、DBSCAN, OPTICS；（；（2）基于密度分布函数，基于密度分布函数，如如DENCLUEl基于网格的方法基于网格的方法：采用多分辨率网格数据结构，：采用多分辨率网格数据结构，如如STING, BANG, CLIQUE, MAFIAl基于模型的方法基于模型的方法：SOM神经网络神经网络(1) (1) 划分方法划分方法n给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇，k n。也就是说，它将数据划分为k个簇，而且这k个划分满足下列条件：n每一个簇至少包含一个对象。n每一个对象属于且仅属于一个簇。n对于给定的k，算法首先给出一个初始的划分方法，以后通过反复迭代

15、的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。l启发式方法启发式方法: k-平均算法和平均算法和k-中心点算法中心点算法k-均值算法均值算法:每个簇用该簇中对象的平均值每个簇用该簇中对象的平均值来表示。来表示。k-中心点算法中心点算法: 每个簇用接近聚类中心的一每个簇用接近聚类中心的一个对象来表示个对象来表示nk k-means-means算法，也被称为算法，也被称为k k- -平均或平均或k k- -均值，是一种均值，是一种得到最广泛使用的聚类算法。相似度的计算根据一得到最广泛使用的聚类算法。相似度的计算根据一个簇中对象的平均值来进行。个簇中对象的平均值来进行。 首先将所有对象

16、随机分配到首先将所有对象随机分配到k个非空的簇中。个非空的簇中。 计算每个簇的平均值，并用该平均值代表相应的簇。计算每个簇的平均值，并用该平均值代表相应的簇。 根据每个对象与各个簇中心的距离，分配给最近的簇。根据每个对象与各个簇中心的距离，分配给最近的簇。 然后转第二步，重新计算每个簇的平均值。这个过程然后转第二步，重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。不断重复直到满足某个准则函数才停止。K-K-均值算法均值算法K-均值聚类示例均值聚类示例From “Data Mining: Concepts and Techniques”, J. Han and M. Kamb

17、er算法算法 k-means算法算法输入：簇的数目输入：簇的数目k和包含和包含n个对象的数据库。个对象的数据库。输出：输出：k个簇，使平方误差准则最小。个簇，使平方误差准则最小。（1)assign initial value for means; /*任意选择任意选择k个对象作为初始的簇中心个对象作为初始的簇中心*/ (2) REPEAT (3) FOR j=1 to n DO assign each xj to the closest clusters; (4) FOR i=1 to k DO / *更新簇平均值更新簇平均值*/ (5) Compute /*计算准则函数计算准则函数E*/ (

18、6) UNTIL E不再明显地发生变化。不再明显地发生变化。n算法首先随机地选择算法首先随机地选择k k个对象，每个对象初始地代表了个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。的平均值。这个过程不断重复，直到准则函数收敛。n准则函数试图使生成的结果簇尽可能地紧凑和独立。准则函数试图使生成的结果簇尽可能地紧凑和独立。样本数据样本数据序号序号 属性属性 1 属性属性 21

19、 1 12 2 13 1 24 2 25 4 36 5 37 4 48 5 4迭代次数迭代次数 平均值平均值平均值平均值 产生的新簇产生的新簇 新平均值新平均值 新平均值新平均值 （簇（簇1） （簇（簇2） （簇（簇1） （簇（簇2）1 （1，1）（1，2） 1，2，3，4，5，6，7，8 （1.5，1） （3.5，3）2 （1.5，1） （3.5，3） 1，2，3，4，5，6，7，8 （1.5，1.5） （4.5，3.5）3 （1.5，1.5）（4.5，3.5） 1，2，3，4，5，6，7，8 （1.5，1.5） （4.5，3.5）根据所给的数据通过对其实施根据所给的数据通过对其实施k-me

20、ans (设设n=8，k=2)，其主其主要执行执行步骤：要执行执行步骤：第一次迭代：假定随机选择的两个对象，如序号第一次迭代：假定随机选择的两个对象，如序号1和序号和序号3当当作初始点，分别找到离两点最近的对象，并产生两个簇作初始点，分别找到离两点最近的对象，并产生两个簇1，2和和3，4，5，6，7，8。对于产生的簇分别计算平均值，得到平均值点。对于产生的簇分别计算平均值，得到平均值点。对于对于1，2，平均值点为（，平均值点为（1.5，1）（这里的平均值是）（这里的平均值是简单的相加除简单的相加除2）；）；对于对于3，4，5，6，7，8，平均值点为（，平均值点为（3.5，3）。）。第二次迭代：

21、通过平均值调整对象的所在的簇，重新聚类，第二次迭代：通过平均值调整对象的所在的簇，重新聚类，即将所有点按离平均值点（即将所有点按离平均值点（1.5，1）、（）、（3.5，3）最近的原）最近的原则重新分配。得到两个新的簇：则重新分配。得到两个新的簇：1，2，3，4和和5，6，7，8。重新计算簇平均值点，得到新的平均值点为（。重新计算簇平均值点，得到新的平均值点为（1.5，1.5）和（和（4.5，3.5）。）。第三次迭代：将所有点按离平均值点（第三次迭代：将所有点按离平均值点（1.5，1.5）和（）和（4.5，3.5）最近的原则重新分配，调整对象，簇仍然为）最近的原则重新分配，调整对象，簇仍然为1

22、，2，3，4和和5，6，7，8，发现没有出现重新分配，而且准则函数，发现没有出现重新分配，而且准则函数收敛，程序结束。收敛，程序结束。实例实例k k-means-means算法的性能分析算法的性能分析n主要优点：主要优点：n是解决聚类问题的一种经典算法，简单、快速。是解决聚类问题的一种经典算法，简单、快速。n对处理大数据集，该算法是相对可伸缩和高效率的。对处理大数据集，该算法是相对可伸缩和高效率的。n当结果簇是密集的，它的效果较好。当结果簇是密集的，它的效果较好。n主要缺点主要缺点n在簇的平均值被定义的情况下才能使用，可能不适用于在簇的平均值被定义的情况下才能使用，可能不适用于某些应用。某些应

23、用。n必须事先给出必须事先给出k k（要生成的簇的数目），而且对初值敏要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。感，对于不同的初始值，可能会导致不同结果。n不适合于发现非凸面形状的簇或者大小差别很大的簇。不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于而且，它对于“躁声躁声”和孤立点数据是敏感的。和孤立点数据是敏感的。k k-means-means算法的几种改进方法算法的几种改进方法nk k-mode -mode 算法：实现对离散数据的快速聚类，保留算法：实现对离散数据的快速聚类，保留了了k k-means-means算法的效率同时将算法的效率同时将

24、k k-means-means的应用范围扩的应用范围扩大到离散数据。大到离散数据。nk k-prototype-prototype算法：可以对离散与数值属性两种混算法：可以对离散与数值属性两种混合的数据进行聚类，在合的数据进行聚类，在k k-prototype-prototype中定义了一个中定义了一个对数值与离散属性都计算的相异性度量标准。对数值与离散属性都计算的相异性度量标准。nk k- -中心点算法中心点算法k k -means -means算法对于孤立点是敏感的。算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照为了解决这个问题，不采用簇中的平均值作为参照点，可以选用

25、簇中位置最中心的对象，即中心点作点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。象与其参照点之间的相异度之和的原则来执行的。 k-k-中心点算法（中心点算法（k-medoidsk-medoids）l也称也称PAM算法（算法（Partitioning Around Medoids） 基于有代表性的数据（基于有代表性的数据（中心点中心点），而不是均值代），而不是均值代表每个簇。表每个簇。l思路思路 1.1.为每个簇随机选择一个代表对象为每个簇随机选择一个代表对象( (中心

26、点中心点) )； 2.2.剩余的对象根据其与代表对象的距离分配给剩余的对象根据其与代表对象的距离分配给与其最近的一个簇；与其最近的一个簇； 3.3.反复地用非代表对象来替换代表对象，以提反复地用非代表对象来替换代表对象，以提高聚类的质量，直至找到最合适的中心点。高聚类的质量，直至找到最合适的中心点。nPAM作为最早提出的作为最早提出的k-中心点算法之一，它选用簇中中心点算法之一，它选用簇中位置最中心的对象作为代表对象，试图对位置最中心的对象作为代表对象，试图对n个对象给出个对象给出k个划分。个划分。n代表对象也被称为是中心点，其他对象则被称为非代代表对象也被称为是中心点，其他对象则被称为非代表

27、对象。表对象。n最初随机选择最初随机选择k个对象作为中心点，该算法反复地用非个对象作为中心点，该算法反复地用非代表对象来代替代表对象，试图找出更好的中心点，以代表对象来代替代表对象，试图找出更好的中心点，以改进聚类的质量。改进聚类的质量。n在每次迭代中，所有可能的对象对被分析，每个对中在每次迭代中，所有可能的对象对被分析，每个对中的一个对象是中心点，而另一个是非代表对象。的一个对象是中心点，而另一个是非代表对象。n对可能的各种组合，估算聚类结果的质量。一个对象对可能的各种组合，估算聚类结果的质量。一个对象Oi被可以产生最大平方被可以产生最大平方-误差值减少的对象代替。在一次误差值减少的对象代替

28、。在一次迭代中产生的最佳对象集合成为下次迭代的中心点。迭代中产生的最佳对象集合成为下次迭代的中心点。 计算用非代计算用非代表对象表对象h替替换代表对象换代表对象i的的总代价总代价：单个数据单个数据的的替换代替换代价价：用：用h代替代替i后，后，j到中心到中心点距离的点距离的变化变化为了判定一个非代表对象为了判定一个非代表对象为了判定一个非代表对象为了判定一个非代表对象OOh h是否是当前一个代表是否是当前一个代表是否是当前一个代表是否是当前一个代表对象对象对象对象OOi i的好的替代，对于每一个非中心点对象的好的替代，对于每一个非中心点对象的好的替代，对于每一个非中心点对象的好的替代，对于每一

29、个非中心点对象OOj j，下面的四种情况被考虑下面的四种情况被考虑下面的四种情况被考虑下面的四种情况被考虑: :第一种情况：第一种情况：第一种情况：第一种情况：OOj j当前隶属于中心点对象当前隶属于中心点对象当前隶属于中心点对象当前隶属于中心点对象OOi i。如果如果如果如果OOi i被被被被OOh h所代替作为中心点，且所代替作为中心点，且所代替作为中心点，且所代替作为中心点，且OOj j离一个离一个离一个离一个OOmm最近，最近，最近，最近，i i mm，那么那么那么那么OOj j被重新分配给被重新分配给被重新分配给被重新分配给OOmm。第二种情况：第二种情况：第二种情况：第二种情况：O

30、Oj j当前隶属于中心点对象当前隶属于中心点对象当前隶属于中心点对象当前隶属于中心点对象OOi i。如果如果如果如果OOi i被被被被OOh h代替作为一个中心点，且代替作为一个中心点，且代替作为一个中心点，且代替作为一个中心点，且OOj j离离离离OOh h最近，那么最近，那么最近，那么最近，那么OOj j被重新分被重新分被重新分被重新分配给配给配给配给OOh h。第三种情况：第三种情况：第三种情况：第三种情况：OOj j当前隶属于中心点当前隶属于中心点当前隶属于中心点当前隶属于中心点OOmm，mm i i。如果如果如果如果OOi i被被被被OOh h代替作为一个中心点，而代替作为一个中心点

31、，而代替作为一个中心点，而代替作为一个中心点，而OOj j依然离依然离依然离依然离OOmm最近，那么对象最近，那么对象最近，那么对象最近，那么对象的隶属不发生变化。的隶属不发生变化。的隶属不发生变化。的隶属不发生变化。第四种情况：第四种情况：第四种情况：第四种情况：OOj j当前隶属于中心点当前隶属于中心点当前隶属于中心点当前隶属于中心点OOmm，mm i i。如果如果如果如果OOi i被被被被OOh h代替作为一个中心点，且代替作为一个中心点，且代替作为一个中心点，且代替作为一个中心点，且OOj j离离离离OOh h最近，那么最近，那么最近，那么最近，那么OOi i被重新被重新被重新被重新分

32、配给分配给分配给分配给OOh h。n每当重新分配发生时，平方每当重新分配发生时，平方-误差误差E所产生的差别对代价所产生的差别对代价函数有影响。因此，如果一个当前的中心点对象被非中心函数有影响。因此，如果一个当前的中心点对象被非中心点对象所代替，代价函数计算平方点对象所代替，代价函数计算平方-误差值所产生的差别。误差值所产生的差别。替换的总代价是所有非中心点对象所产生的代价之和。替换的总代价是所有非中心点对象所产生的代价之和。n如果总代价是负的，那么实际的平方如果总代价是负的，那么实际的平方-误差将会减小，误差将会减小，Oi可以被可以被Oh替代。替代。n如果总代价是正的，则当前的中心点如果总代

33、价是正的，则当前的中心点Oi被认为是可接被认为是可接受的，在本次迭代中没有变化。受的，在本次迭代中没有变化。 总代价定义如下：总代价定义如下： 其中，其中，Cjih表示表示Oj在在Oi被被Oh代替后产生的代价。下面介代替后产生的代价。下面介绍上面所述的四种情况中代价函数的计算公式，其中所引绍上面所述的四种情况中代价函数的计算公式，其中所引用的符号有：用的符号有：Oi和和Om是两个原中心点，是两个原中心点，Oh将替换将替换Oi作为新作为新的中心点。的中心点。第二种情况第二种情况 Oj被重新分配给Oh， Cjih =d(j, h)-d(j, i)第一种情况第一种情况 Oj被重新分配给Om，Cjih

34、 =d(j, m)-d(j, i)第三种情况第三种情况 Oj的隶属不发生变化，Cjih =0 第四种情况第四种情况 Oi被重新分配给Oh，Cjih =d(j, h)-d(j, m) 算法算法 PAM（k-中心点算法）中心点算法）输入：簇的数目输入：簇的数目k和包含和包含n个对象的数据库。个对象的数据库。输出：输出：k个簇，使得所有对象与其最近中心点的相异度总和最小。个簇，使得所有对象与其最近中心点的相异度总和最小。（1） 任意选择任意选择k个对象作为初始的簇中心点；个对象作为初始的簇中心点；（2） REPEAT（3） 指派每个剩余的对象给离它最近的中心点所代表的簇；指派每个剩余的对象给离它最近

35、的中心点所代表的簇；（4） REPEAT（5） 选择一个未被选择的中心点选择一个未被选择的中心点Oi；（6） REPEAT（7） 选择一个未被选择过的非中心点对象选择一个未被选择过的非中心点对象Oh；（8） 计算用计算用Oh代替代替Oi的总代价并记录在的总代价并记录在S中；中；（9） UNTIL 所有的非中心点都被选择过；所有的非中心点都被选择过；（10） UNTIL 所有的中心点都被选择过；所有的中心点都被选择过；（11） IF 在在S中的所有非中心点代替所有中心点后的计算出的总代中的所有非中心点代替所有中心点后的计算出的总代价有小于价有小于0的存在的存在 THEN 找出找出S中的用非中心点

36、替代中心点后代价最中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中个中心点的集合；心点的集合；（12）UNTIL 没有再发生簇的重新分配，即所有的没有再发生簇的重新分配，即所有的S都大于都大于0.实例实例假如空间中的五个点假如空间中的五个点A、如图、如图1所示，所示，各点之间的距离关系如表各点之间的距离关系如表1所示，根据所给的数据对其运所示，根据所给的数据对其运行行PAM算法实现划分聚类（设算法实现划分聚类（设k=2）。）。 样本点间距离如样本点间距离如下表所示下表所示: 样本点样本点 起始中心

37、点为起始中心点为A,BA,B 样本点样本点ABCDEA01223B10243C22015D24103E33530第一步第一步 建立阶段：假如从建立阶段：假如从5 5个对象中随机抽取的个对象中随机抽取的2 2个中心点为个中心点为AA，B,B,则样本被划分为则样本被划分为AA、C C、DD和和BB、EE，如图所示。如图所示。第二步第二步 交换阶段：假定中心点交换阶段：假定中心点A A、B B分别被非中心点分别被非中心点CC、D D、EE替替换，根据换，根据PAMPAM算法需要计算下列代价算法需要计算下列代价TCTCACAC、 TCTCADAD、 TCTCAEAE、TCTCBCBC、TCTCBDBD

38、、 TCTCBEBE。以以TCTCACAC为例说明计算过程：为例说明计算过程：a) a) 当当A A被被C C替换以后，替换以后，A A不再是一个中心点，因为不再是一个中心点，因为A A离离B B比比A A离离C C近，近，A A被分配到被分配到B B中心点代表的簇，中心点代表的簇，C CAACAAC= =d d( (A A, ,B B)-)-d d( (A A, ,A A)=1)=1。b) Bb) B是一个中心点，当是一个中心点，当A A被被C C替换以后，替换以后，B B不受影响，不受影响，C CBACBAC= =0 0。c) Cc) C原先属于原先属于A A中心点所在的簇，当中心点所在的

39、簇，当A A被被C C替换以后，替换以后，C C是新中心是新中心点，符合点，符合PAMPAM算法代价函数的第二种情况算法代价函数的第二种情况C CCACCAC= =d d( (C C, ,C C)-)-d d( (C C, ,A A)=0-2=-2)=0-2=-2。d) Dd) D原先属于原先属于A A中心点所在的簇，当中心点所在的簇，当A A被被C C替换以后，离替换以后，离D D最近的最近的中心点是中心点是C C，根据根据PAMPAM算法代价函数的第二种情况算法代价函数的第二种情况C CDACDAC= =d d( (D D, ,C C)-)-d d( (D D, ,A A)=1-2=-1)

40、=1-2=-1。e) Ee) E原先属于原先属于B B中心点所在的簇，当中心点所在的簇，当A A被被C C替换以后，离替换以后，离E E最近的最近的中心仍然是中心仍然是 B B，根据根据PAMPAM算法代价函数的第三种情况算法代价函数的第三种情况C CEACEAC=0=0。因此，因此，T TC CACAC= =C CA AACAC+ + C CB BACAC+ + CB CBACAC+ + CD CDACAC+ CE+ CEACAC=1+0-2-1+0=-2=1+0-2-1+0=-2。 在上述代价计算完毕后，我们要选取一个最小的代在上述代价计算完毕后，我们要选取一个最小的代价，显然有多种替换可

41、以选择，选择第一个最小代价的价，显然有多种替换可以选择，选择第一个最小代价的替换（也就是替换（也就是C C替换替换A A），），根据图（根据图（a a）所示，样本点被划所示，样本点被划分为分为 B B、A A、EE和和CC、DD两个簇。图（两个簇。图（b b）和图（和图（c c）分分别表示了别表示了D D替换替换A A，E E替换替换A A的情况和相应的代价的情况和相应的代价 (a) C(a) C替换替换A, A, TCTCACAC= =-2 (b) D-2 (b) D替换替换A, A, TCTCADAD= =-2 (c) E-2 (c) E替换替换A,A, TC TCAEAE= =-1-1图

42、图 替换中心点替换中心点A A图图 （a a）、（）、（b b）、（）、（c c）分别表示了用分别表示了用C C、D D、E E替换替换B B的的情况和相应的代价。情况和相应的代价。 (a)(a) C C替换替换B, B, TCTCBCBC= =-2 (b) D-2 (b) D替换替换B,B, TC TCBDBD= =-2 -2 (c) E(c) E替换替换B, B, TCTCBEBE= =-2-2图图 替换中心点替换中心点B B 通过上述计算，已经完成了通过上述计算，已经完成了PAMPAM算法的第一次迭代。算法的第一次迭代。在下一迭代中，将用其他的非中心点在下一迭代中，将用其他的非中心点AA

43、、D D、EE替换中心替换中心点点BB、CC，找出具有最小代价的替换。一直重复上述过找出具有最小代价的替换。一直重复上述过程，直到代价不再减小为止。程，直到代价不再减小为止。PAM算法特点算法特点l比比k-means健壮，但对于大数据集效率不健壮，但对于大数据集效率不高。高。l当存在当存在 “噪声噪声”和离群数据时，和离群数据时，k-中心中心点方法比点方法比k均值方法更健壮，这是因为中均值方法更健壮，这是因为中心点不像平均值那样易被极端数据影响。心点不像平均值那样易被极端数据影响。lk-中心点方法的执行代价比中心点方法的执行代价比k-平均高。平均高。改进算法改进算法lCLARA(Cluster

44、ing Large Applications),1990 用实际数据的抽样来代替整个数据，然后再在这些用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用抽样的数据上利用K-medoids算法得到最佳的中心算法得到最佳的中心点点 。 如果样本是以非随机的方式选取，它应当足以代如果样本是以非随机的方式选取，它应当足以代替原来的数据集合。从中选出的代表对象（中心替原来的数据集合。从中选出的代表对象（中心点）很可能与从整个数据集合选出的代表相似。点）很可能与从整个数据集合选出的代表相似。 改进算法改进算法CLARANS (“随机化的随机化的”CLARA)，1994 利用多次不同抽样来改进利用

45、多次不同抽样来改进CLARA。 其聚类过程可以被描述为对一个图的收索过程，图中其聚类过程可以被描述为对一个图的收索过程，图中的每一个节点都是一个潜在的解，即的每一个节点都是一个潜在的解，即k个中心点的集个中心点的集合。在替换了一个中心点后得到的聚类结果被当成是合。在替换了一个中心点后得到的聚类结果被当成是前聚类结果的邻居。如果一个更好的邻居被发现，也前聚类结果的邻居。如果一个更好的邻居被发现，也就是说它有更小的平方误差值，就是说它有更小的平方误差值，clarans移到该邻居节移到该邻居节点，处理过程重新开始，如果没有发现更好的邻居，点，处理过程重新开始，如果没有发现更好的邻居，则达到局部最优。

46、则达到局部最优。(2) (2) 层次聚类方法层次聚类方法n层次聚类方法对给定的数据集进行层次的分解，层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：直到某种条件满足为止。具体又可分为：n凝聚的层次聚类：一种自底向上的策略，首先将每凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。的簇，直到某个终结条件被满足。n分裂的层次聚类：采用自顶向下的策略，它首先将分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的所有对象

47、置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。簇，直到达到了某个终结条件。n层次凝聚的代表是层次凝聚的代表是AGNES算法。层次分裂的算法。层次分裂的代表是代表是DIANA算法。算法。 AGNESAGNES算法算法nAGNES (AGNES (AGglomerativeAGglomerative NEStingNESting) )算法最初算法最初将每个对象作为一个簇，然后这些簇根据某将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度些准则被一步步地合并。两个簇间的相似度由这两个不同簇中距离最近的数据点对的相由这两个不同簇中距离最近的数据点对的相似度

48、来确定。聚类的合并过程反复进行直到似度来确定。聚类的合并过程反复进行直到所有的对象最终满足簇数目。所有的对象最终满足簇数目。算法算法 AGNES（自底向上凝聚算法）自底向上凝聚算法）输入：包含输入：包含n个对象的数据库，终止条件簇的数目个对象的数据库，终止条件簇的数目k。输出：输出：k个簇，达到终止条件规定簇数目。个簇，达到终止条件规定簇数目。(1) 将每个对象当成一个初始簇；将每个对象当成一个初始簇；(2) REPEAT(3) 根据两个簇中最近的数据点找到最近的两个簇；根据两个簇中最近的数据点找到最近的两个簇；(4) 合并两个簇，生成新的簇的集合；合并两个簇，生成新的簇的集合；(5) UNT

49、IL 达到定义的簇的数目；达到定义的簇的数目；实例实例序号序号属性属性 1属性属性 2111212321422534635744845步骤步骤最近的簇距离最近的簇距离最近的两个簇最近的两个簇合并后的新簇合并后的新簇111，21，2，3，4，5，6，7，8213，41，2，3，4，5，6，7，8315，61，2，3，4，5，6，7，8417，81，2，3，4，5，6，7，8511，2，3，41，2，3，4，5，6，7，8615，6，7，81，2，3，4，5，6，7，8结束结束第第1步：根据初始簇计算每个簇之间的距离，随步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距

50、机找出距离最小的两个簇，进行合并，最小距离为离为1，合并后，合并后1，2点合并为一个簇。点合并为一个簇。第第2步：，对上一次合并后的簇计算簇间距离，步：，对上一次合并后的簇计算簇间距离，找出距离最近的两个簇进行合并，合并后找出距离最近的两个簇进行合并，合并后3，4点成为一簇。点成为一簇。第第3步：重复第步：重复第2步的工作，步的工作，5，6点成为一簇。点成为一簇。第第4步：重复第步：重复第2步的工作，步的工作，7，8点成为一簇。点成为一簇。第第5步：合并步：合并1，2，3，4成为一个包含四成为一个包含四个点的簇。个点的簇。第第6步：合并步：合并5，6，7，8，由于合并后的，由于合并后的簇的数目

51、已经达到了用户输入的终止条件程序簇的数目已经达到了用户输入的终止条件程序结束。结束。AGNESAGNES算法的性能分析算法的性能分析nAGNES算法比较简单，但经常会遇到合并点选择的困算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤消，聚类之间也不能交换对的簇上进行。已做处理不能撤消，聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定，可能会导象。如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果。致低质量的聚类结果。n这种聚类方法不具有很好的可伸缩性，

52、因为合并的决定这种聚类方法不具有很好的可伸缩性，因为合并的决定需要检查和估算大量的对象或簇。需要检查和估算大量的对象或簇。n假定在开始的时候有假定在开始的时候有n个簇，在结束的时候有个簇，在结束的时候有1个簇，因个簇，因此在主循环中有此在主循环中有n次迭代，在第次迭代，在第i次迭代中，我们必须在次迭代中，我们必须在n-i+1个簇中找到最靠近的两个聚类。另外算法必须计算所个簇中找到最靠近的两个聚类。另外算法必须计算所有对象两两之间的距离，因此这个算法的复杂度为有对象两两之间的距离，因此这个算法的复杂度为 O(n2)，该算法对于该算法对于n很大的情况是不适用的。很大的情况是不适用的。 DIANAD

53、IANA算法算法nDIANA (Divisive ANAlysis)算法是典型的分裂聚算法是典型的分裂聚类方法。类方法。n在聚类中，用户能定义希望得到的簇数目作为一在聚类中，用户能定义希望得到的簇数目作为一个结束条件。同时，它使用下面两种测度方法：个结束条件。同时，它使用下面两种测度方法：n簇的直径：在一个簇中的任意两个数据点的距簇的直径：在一个簇中的任意两个数据点的距离中的最大值。离中的最大值。n平均相异度（平均距离）：平均相异度（平均距离）： 算法算法 DIANA（自自顶向下分裂算法）向下分裂算法）输入：包含入：包含n个个对象的数据象的数据库，终止条件簇的数目止条件簇的数目k。输出：出：k

54、个簇，达到个簇，达到终止条件止条件规定簇数目。定簇数目。（1）将所有）将所有对象整个当成一个初始簇；象整个当成一个初始簇；（2） FOR （i=1; ik; i+) DO BEGIN（3） 在所有簇中挑出具有最大直径的簇在所有簇中挑出具有最大直径的簇C；（4） 找找出出C中中与与其其它它点点平平均均相相异异度度最最大大的的一一个个点点p并并把把p放放入入splinter group，剩余的放在剩余的放在old party中；中；（5）. REPEAT（6） 在在old party里里找找出出到到最最近近的的splinter group中中的的点点的的距距离离不不大大于于到到old party中

55、中最最近近点点的的距距离离的的点点，并并将将该点点加加入入splinter group。（7） UNTIL 没有新的没有新的old party的点被分配的点被分配给splinter group；（8） splinter group和和old party为被被选中中的的簇簇分分裂裂成成的的两两个个簇簇，与与其其它簇一起它簇一起组成新的簇集合。成新的簇集合。（9） END.实例实例序号序号属性属性 1属性属性 2111212321422534635744845步骤步骤具有最大直径的簇具有最大直径的簇splinter groupOld party11，2，3，4，5，6，7，812，3，4，5，6，

56、7，821，2，3，4，5，6，7，81，23，4，5，6，7，831，2，3，4，5，6，7，81，2，34，5，6，7，841，2，3，4，5，6，7，81，2，3，45，6，7，851，2，3，4，5，6，7，81，2，3，45，6，7，8 终止终止第第1步，找到具有最大直径的簇，对簇中的每个点计算平均相步，找到具有最大直径的簇，对簇中的每个点计算平均相异度（假定采用是欧式距离）。异度（假定采用是欧式距离）。 1的平均距离：的平均距离：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96 类似地，类似地，2的平均距离为的平均距离为2.526；3的平均距离为的平均距离为2.

57、68；4的平均距离为的平均距离为2.18；5的平均距离为的平均距离为2.18；6的平均距离的平均距离为为2.68；7的平均距离为的平均距离为2.526；8的平均距离为的平均距离为2.96。 挑出平均相异度最大的点挑出平均相异度最大的点1放到放到splinter group中，剩余点中，剩余点在在old party中。中。第第2步，在步，在old party里找出到最近的里找出到最近的splinter group中的点的中的点的距离不大于到距离不大于到old party中最近的点的距离的点，将该点中最近的点的距离的点，将该点放入放入splinter group中，该点是中，该点是2。第第3步，重

58、复第步，重复第2步的工作，步的工作，splinter group中放入点中放入点3。第第4步，重复第步，重复第2步的工作，步的工作，splinter group中放入点中放入点4。第第5步，没有在步，没有在old party中的点放入了中的点放入了splinter group中且达中且达到终止条件（到终止条件（k=2），），程序终止。如果没有到终止条件，程序终止。如果没有到终止条件，因该从分裂好的簇中选一个直径最大的簇继续分裂。因该从分裂好的簇中选一个直径最大的簇继续分裂。层次聚类方法的改进层次聚类方法的改进n层次聚类方法尽管简单，但经常会遇到合层次聚类方法尽管简单，但经常会遇到合并或分裂点的

59、选择的困难。并或分裂点的选择的困难。n改进层次方法的聚类质量的一个有希望的改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。形成多阶段聚类。n下面介绍两个改进的层次聚类方法下面介绍两个改进的层次聚类方法CURE和和BIRTH。 lBIRCH（利用层次方法的平衡迭代归约和聚类）是一利用层次方法的平衡迭代归约和聚类）是一个综合的层次聚类方法，它用聚类特征和聚类特征树个综合的层次聚类方法，它用聚类特征和聚类特征树（CF）来概括聚类描述。该算法通过聚类特征可以方来概括聚类描述。该算法通过聚类特征可以方便地进行中心、半径、

60、直径及类内、类间距离的运算。便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子树是一个具有两个参数分支因子B和阂值和阂值T的高度平的高度平衡树，存储了层次聚类的聚类特征。分支因子定义了衡树，存储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。树的叶子节点中的子聚类的最大直径。BIRCH算法主要分两个阶段进行：算法主要分两个阶段进行：l阶段一：扫描数据库，建立一个初始的阶段一：扫描数据库，建立一个初始的CF树，树，它可以它可以被被看作一个数据的多层压缩，

61、试图保留数据内在的聚看作一个数据的多层压缩，试图保留数据内在的聚类结构。当一个对象被插入到最近的叶节点（子聚类）类结构。当一个对象被插入到最近的叶节点（子聚类）中时，中时，随着对象的插入，随着对象的插入，CF树被动态地构造，不要求树被动态地构造，不要求所有的数据读入内存，而可在外存上逐个读入数据项。所有的数据读入内存，而可在外存上逐个读入数据项。因此，因此，BIRTH方法对增量或动态聚类也非常有效。方法对增量或动态聚类也非常有效。l阶段二：采用某个聚类算法对阶段二：采用某个聚类算法对CF树的叶节点进行聚类。树的叶节点进行聚类。在这个阶段可以执行任何聚类算法，例如典型的划分在这个阶段可以执行任何

62、聚类算法，例如典型的划分方法。方法。 BIRCH算法具有可伸缩性，通过对数据集的首次扫描产算法具有可伸缩性，通过对数据集的首次扫描产生一个基本聚类，二次扫描则进一步改进聚类质量并处理生一个基本聚类，二次扫描则进一步改进聚类质量并处理孤立点。孤立点。BIRCH算法处理速度较快，只是对非球形簇处算法处理速度较快，只是对非球形簇处理效果不好。理效果不好。很多聚类算法只擅长处理球形或相似大小的聚类，另很多聚类算法只擅长处理球形或相似大小的聚类，另外有些聚类算法对孤立点比较敏感。外有些聚类算法对孤立点比较敏感。CURE算法解决算法解决了上述两方面的问题，选择基于质心和基于代表对象了上述两方面的问题，选择

63、基于质心和基于代表对象方法之间的中间策略，即选择空间中固定数目的具有方法之间的中间策略，即选择空间中固定数目的具有代表性的点，而不是用单个中心或对象来代表一个簇。代表性的点，而不是用单个中心或对象来代表一个簇。该算法首先把每个数据点看成一簇，然后再以一个特该算法首先把每个数据点看成一簇，然后再以一个特定的收缩因子向簇中心定的收缩因子向簇中心“收缩收缩”它们，即合并两个距它们，即合并两个距离最近的代表点的簇。离最近的代表点的簇。CURE算法的主要步骤如下：算法的主要步骤如下： 从源数据集中抽取一个随机样本从源数据集中抽取一个随机样本S。 为了加速聚类，把样本划分成为了加速聚类，把样本划分成p份，

64、每份大小相等。份，每份大小相等。 对每个划分进行局部地聚类。对每个划分进行局部地聚类。 根据局部聚类结果，通过随机抽样剔除孤立点。主要有根据局部聚类结果，通过随机抽样剔除孤立点。主要有两种措施：如果一个簇增长得太慢，就去掉它；在聚类两种措施：如果一个簇增长得太慢，就去掉它；在聚类结束的时候，非常小的类被剔除。结束的时候，非常小的类被剔除。 对上一步中产生的局部的簇进一步聚类。落在每个新形对上一步中产生的局部的簇进一步聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子成的簇中的代表点根据用户定义的一个收缩因子 收缩收缩或向簇中心移动。这些点代表和捕捉到了簇的形状。或向簇中心移动。这些点

65、代表和捕捉到了簇的形状。 用相应的簇标签来标记数据。用相应的簇标签来标记数据。由于由于CURE回避了用所有点或单个质心来表示一个回避了用所有点或单个质心来表示一个簇的传统方法，将一个簇用多个代表点来表示，使簇的传统方法，将一个簇用多个代表点来表示，使CURE可以适应非球形的几何形状。另外，收缩因可以适应非球形的几何形状。另外，收缩因子降底了噪音对聚类的影响，从而使子降底了噪音对聚类的影响，从而使CURE对孤立对孤立点的处理更加健壮，而且能识别非球形和大小变化点的处理更加健壮，而且能识别非球形和大小变化比较大的簇。比较大的簇。CURE的复杂度是的复杂度是O(n)，n是对象的数是对象的数目，所以该

66、算法适合大型数据的聚类。目，所以该算法适合大型数据的聚类。(3) (3) 密度聚类密度聚类l密度聚类方法的指导思想是，只要一个区域中的密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的点的密度大于某个阈值，就把它加到与之相近的聚类中去。这类算法能克服基于距离的算法只能聚类中去。这类算法能克服基于距离的算法只能发现发现“类圆形类圆形”的聚类的缺点，可发现任意形状的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算的计算复杂度大，需要建立空间索引来降低计算量，且对

67、数据维数的伸缩性较差。这类方法需要量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的查询，因此当数据量大时会造成频繁的I/O操作。操作。代表算法有：代表算法有：DBSCAN、OPTICS、DENCLUE算算法等。法等。 lDBSCAN（Density-Based Spatial Clustering of Applications with Noise）一个比较有代表性的一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为

68、密度相连的点的最大集合，不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可能够把具有足够高密度的区域划分为簇，并可在有在有“噪声噪声”的空间数据库中发现任意形状的的空间数据库中发现任意形状的聚类。聚类。DBSCANl定义定义 1 对象的对象的-临域：给定对象在半径临域：给定对象在半径内的区域。内的区域。l定义定义 2 核心对象：如果一个对象的核心对象：如果一个对象的-临域至少包含最小临域至少包含最小数目数目MinPts个对象，则称该对象为核心对象。个对象，则称该对象为核心对象。 例如，在图中，例如，在图中，=1cm，MinPts=5，q是一个核心对象。是一个核心

69、对象。l定义定义 3 直接密度可达：给定一个对象集合直接密度可达：给定一个对象集合D，如果如果p是是在在q的的-邻域内，而邻域内，而q是一个核心对象，我们说对象是一个核心对象，我们说对象p从对从对象象q出发是直接密度可达的。出发是直接密度可达的。 例如，在图中，例如，在图中，=1cm，MinPts=5，q是一个核心对象，是一个核心对象，对象对象p从对象从对象q出发是直接密度可达的。出发是直接密度可达的。图图 直接密度可达直接密度可达l定义定义 4 密度可达的：如果存在一个对象链密度可达的：如果存在一个对象链p1，p2，pn，p1=q，pn=p，对，对piD，（，（1=i=n），），pi+1是从

70、是从pi关于关于和和MitPts直接密度可达的，则对象直接密度可达的，则对象p是从对象是从对象q关于关于和和MinPts密度可达的。密度可达的。 例如，在图中，例如，在图中，=1cm，MinPts=5，q是一个核心对象，是一个核心对象，p1是从是从q关于关于和和MitPts直接密度可达，直接密度可达，p是从是从p1关于关于和和MitPts直接密度可达，则对象直接密度可达，则对象p从对象从对象q关于关于和和MinPts密度可达的。密度可达的。图图 密度可达密度可达l定义定义 5 密度相连的：如果对象集合密度相连的：如果对象集合D中存在一个对象中存在一个对象o，使使得对象得对象p和和q是从是从o关

71、于关于和和MinPts密度可达的，那么对象密度可达的，那么对象p和和q是关于是关于和和MinPts密度相连的。密度相连的。l定义定义 6 噪声噪声: 一个基于密度的簇是基于密度可达性的最大一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为的密度相连对象的集合。不包含在任何簇中的对象被认为是是“噪声噪声”。 图图 密度相连密度相连图图 噪声噪声lDBSCAN通过检查数据集中每个对象的通过检查数据集中每个对象的-邻域来寻找聚邻域来寻找聚类。如果一个点类。如果一个点p的的-邻域包含多于邻域包含多于MinPts个对象，则创个对象，则创建一个建一个p作为核心对象的新

72、簇。然后，作为核心对象的新簇。然后，DBSCAN反复地反复地寻找从这些核心对象直接密度可达的对象，这个过程可寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。具体如下：加到任何簇时，该过程结束。具体如下：DBSCANDBSCAN算法描述算法描述算法算法5-5 DBSCAN 5-5 DBSCAN 输入：包含输入：包含n n个对象的数据库，半径个对象的数据库，半径，最少数目，最少数目MinPtsMinPts。输出：所有生成的簇，达到密度要求。输出：所有生成的簇，达到密度要求。1.

73、 REPEAT1. REPEAT2. 2. 从数据库中抽取一个未处理过的点；从数据库中抽取一个未处理过的点；3. IF 3. IF 抽出的点是核心点抽出的点是核心点 THENTHEN找出所有从该点密度可达的对象，找出所有从该点密度可达的对象，形成一个簇形成一个簇4. ELSE 4. ELSE 抽出的点是边缘点抽出的点是边缘点( (非核心对象非核心对象) )，跳出本次循环，寻找下，跳出本次循环，寻找下一点；一点；5. UNTIL 5. UNTIL 所有点都被处理；所有点都被处理；下面给出一个样本事务数据库（见左表），对它实施下面给出一个样本事务数据库（见左表），对它实施DBSCANDBSCAN算

74、法。算法。 根据所给的数据通过对其进行根据所给的数据通过对其进行DBSCANDBSCAN算法，以下为算法的步骤（设算法，以下为算法的步骤（设n n=12=12，用户输入，用户输入=1=1，MinPtsMinPts=4=4） 样本事务数据库样本事务数据库DBSCANDBSCAN算法执行过程示意算法执行过程示意 聚出的类为聚出的类为11，3 3，4 4，5 5，9 9，1010，1212，22，6 6，7 7，8 8，1111。序序号号属性属性 1属性属性 2110240301411521631741851902101211421213步骤步骤选择的选择的点点在在中点的个数中点的个数通过计算可达点

75、而找到的新簇通过计算可达点而找到的新簇112无无222无无333无无445簇簇C1：1，3，4，5，9，10，12553已在一个簇已在一个簇C1中中663无无775簇簇C2：2，6，7，8，11882已在一个簇已在一个簇C2中中993已在一个簇已在一个簇C1中中10104已在一个簇已在一个簇C1中，中，11112已在一个簇已在一个簇C2中中 12122已在一个簇已在一个簇C1中中算法执行过程：算法执行过程：第第1 1步，在数据库中选择一点步，在数据库中选择一点1 1，由于在以它为圆心的，以，由于在以它为圆心的，以1 1为半为半径的圆内包含径的圆内包含2 2个点（小于个点（小于4 4），因此它不

76、是核心点，选择下），因此它不是核心点，选择下一个点。一个点。第第2 2步，在数据库中选择一点步，在数据库中选择一点2 2，由于在以它为圆心的，以，由于在以它为圆心的，以1 1为半为半径的圆内包含径的圆内包含2 2个点，因此它不是核心点，选择下一个点。个点，因此它不是核心点，选择下一个点。第第3 3步，在数据库中选择一点步，在数据库中选择一点3 3，由于在以它为圆心的，以，由于在以它为圆心的，以1 1为半为半径的圆内包含径的圆内包含3 3个点，因此它不是核心点，选择下一个点。个点，因此它不是核心点，选择下一个点。第第4 4步，在数据库中选择一点步，在数据库中选择一点4 4，由于在以它为圆心的，以

77、，由于在以它为圆心的，以1 1为半为半径的圆内包含径的圆内包含5 5个点，因此它是核心点，寻找从它出发可达的个点，因此它是核心点，寻找从它出发可达的点（直接可达点（直接可达4 4个，间接可达个，间接可达3 3个），聚出的新类个），聚出的新类11，3 3，4 4，5 5，9 9，1010，1212，选择下一个点。，选择下一个点。第第5 5步，在数据库中选择一点步，在数据库中选择一点5 5，已经在簇，已经在簇1 1中，选择下一个点。中，选择下一个点。第第6 6步，在数据库中选择一点步，在数据库中选择一点6 6，由于在以它为圆心的，以，由于在以它为圆心的，以1 1为半为半径的圆内包含径的圆内包含3

78、3个点，因此它不是核心点，选择下一个点。个点，因此它不是核心点，选择下一个点。第第7 7步，在数据库中选择一点步，在数据库中选择一点7 7，由于在以它为圆心的，以，由于在以它为圆心的，以1 1为半为半径的圆内包含径的圆内包含5 5个点，因此它是核心点，寻找从它出发可达的个点，因此它是核心点，寻找从它出发可达的点，聚出的新类点，聚出的新类22，6 6，7 7，8 8，1111，选择下一个点。，选择下一个点。 第第8 8步，在数据库中选择一点步，在数据库中选择一点8 8，已经在簇，已经在簇2 2中，选择下一个点。中，选择下一个点。第第9 9步，在数据库中选择一点步，在数据库中选择一点9 9，已经在

79、簇，已经在簇1 1中，选择下一个点。中，选择下一个点。第第1010步，在数据库中选择一点步，在数据库中选择一点1010，已经在簇，已经在簇1 1中，选择下一个点。中，选择下一个点。第第1111步，在数据库中选择一点步，在数据库中选择一点1111，已经在簇，已经在簇2 2中，选择下一个点。中，选择下一个点。第第1212步，选择步，选择1212点，已经在簇点，已经在簇1 1中，由于这已经是最后一点所有中，由于这已经是最后一点所有点都点都已已处理，程序终止。处理，程序终止。步步骤骤选选择择的的点点在在中中点点的的个个数数通过计算可达点而找通过计算可达点而找到的新簇到的新簇112无无222无无333无

80、无445簇簇C1：1，3，4，5，9，10，12553已在一个簇已在一个簇C1中中663无无775簇簇C2：2，6，7，8，11882已在一个簇已在一个簇C2中中993已在一个簇已在一个簇C1中中10104已在一个簇已在一个簇C1中，中，11112已在一个簇已在一个簇C2中中 12122已在一个簇已在一个簇C1中中OPTICS算算 法法 是是 对对 DBSCAN算算 法法 的的 改改 进进 ， 因因 为为 在在DBSCAN算算法法中中需需要要用用户户设设定定-邻邻域域和和MitPts，但但是是在在实实际际应应用用中中用用户户往往往往很很难难确确定定这这些些参参数数，而而且且这这些些参参数数设设

81、置置的的不不同同往往往往会会导导致致聚聚类类结结果果有有很很大大差差别别。在在OPTICS算算法法中中认认定定对对象象应应该该以以特特定定的的顺顺序序进进行行处处理理，这这个个顺顺序序首首先先处处理理最最小小的的值值密密度度可可达达的的对对象象，这这样样可可以首先完成高密度的聚类。以首先完成高密度的聚类。DENCLUE算算法法的的依依据据是是某某个个数数据据点点在在邻邻域域内内的的影影响响可可以以用用一一个个数数学学函函数数来来形形式式化化地地模模拟拟，这这个个函函数数为为影影响响函函数数。所所聚聚类类数数据据空空间间的的整整体体密密度度看看成成是是所所有有数数据据点点影影响响函函数数的的总总

82、和和。在在聚聚类类时时就就根根据据全全局局密密度度函函数数的的局局部部最最大大，即密度吸引点来确定。即密度吸引点来确定。 l将对象空间量化为有限数目的单元，形成一个将对象空间量化为有限数目的单元，形成一个网格结构，所有的聚类都在这个网格结构中上网格结构，所有的聚类都在这个网格结构中上进行。进行。l其优点是处理速度很快，其处理时间独立于数其优点是处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元据对象的数目，只与量化空间中每一维的单元数目有关。数目有关。l在网格聚类方法中有利用存储在网格单元中的在网格聚类方法中有利用存储在网格单元中的统计信息进行聚类的统计信息进行聚类的ST

83、ING算法、用小波转换算法、用小波转换方法进行聚类的方法进行聚类的WaveCluster方法和在高维数据方法和在高维数据空间基于网格和密度的聚类方法。空间基于网格和密度的聚类方法。(4) (4) 网格聚类网格聚类lSTING(Statistaical Information Grid_based method)是是一种基于网格的多分辨率聚类技术，它将空间区域划分一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级为矩形单元。针对不同级别的分辨率，通常存在多个级别的别的矩形矩形单元，这些单元形成了一个层次结构：高层的单元，这些单元形成了一个层次结构：高

84、层的每个单元被划分为多个低一层的单元。高层单元的统计每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易的从底层单元的计算得到。这些参数包参数可以很容易的从底层单元的计算得到。这些参数包括属性无关的参数括属性无关的参数count、属性相关的参数属性相关的参数m（平均值）、平均值）、s(标准偏差标准偏差)、min(最小值最小值)、max(最大值最大值)以及该单元以及该单元中属性值遵循的分布类型。中属性值遵循的分布类型。lSTING算法采用了一种多分辨率的方法来进行聚类分算法采用了一种多分辨率的方法来进行聚类分析，该聚类算法的质量取决于网格结构最低层的粒度。析，该聚类算法的质量取决于网格

85、结构最低层的粒度。如果粒度比较细，处理的代价会显著增加；但如果粒度如果粒度比较细，处理的代价会显著增加；但如果粒度较粗，则聚类质量会受到影响。较粗，则聚类质量会受到影响。STINGSTING算法算法lSTING算法的主要优点是效率高，通过对数据算法的主要优点是效率高，通过对数据集的一次扫描来计算单元的统计信息，因此产生集的一次扫描来计算单元的统计信息，因此产生聚类的时间复杂度是聚类的时间复杂度是O(n)。在建立层次结构以后，在建立层次结构以后，查询的时间复杂度是查询的时间复杂度是O(g), g远小于远小于n。STING算法算法采用网格结构，有利于并行处理和增量更新。采用网格结构，有利于并行处理

86、和增量更新。lWaveCluster方法方法首先通过在数据空间上强加一个多维首先通过在数据空间上强加一个多维网格结构来汇总数据，每个网格单元汇总了一组映射到网格结构来汇总数据，每个网格单元汇总了一组映射到该单元中的点的信息，然后采用一种小波变换对原特征该单元中的点的信息，然后采用一种小波变换对原特征空间进行变换，汇总信息在进行小波变换时使用，接着空间进行变换，汇总信息在进行小波变换时使用，接着在变换后的空间中找到聚类区域。在变换后的空间中找到聚类区域。l小波变换的聚类小波变换的聚类是无监督聚类，不用事先假定聚类的形是无监督聚类，不用事先假定聚类的形状，可以发现任意形状的聚类，边界弱信号不会被屏

87、蔽，状，可以发现任意形状的聚类，边界弱信号不会被屏蔽，可以剔除孤立点，本身运算开销不大。可以剔除孤立点，本身运算开销不大。l基于网格和密度的聚类基于网格和密度的聚类CLIQUE算法算法主要步骤是：主要步骤是： 将数据空间划分为互不相交的长方形单元，记录每个将数据空间划分为互不相交的长方形单元，记录每个单元中的对象数。单元中的对象数。 用先验性质识别包含簇的子空间。用先验性质识别包含簇的子空间。 在符合兴趣度的子空间中先找出密集单元，再找出相在符合兴趣度的子空间中先找出密集单元，再找出相连接的密集单元，以识别簇。连接的密集单元，以识别簇。 为每个簇生成最小化的描述。为每个簇生成最小化的描述。l基

88、于模型的聚类方法为每个簇假定了一个模型，基于模型的聚类方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。寻找数据对给定模型的最佳拟合。l一个基于模型的算法可能通过构建反映数据点一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。基于模型的空间分布的密度函数来定位聚类。基于模型的聚类方法主要有统计学和神经网络两种。聚类方法主要有统计学和神经网络两种。(5) (5) 模型聚类模型聚类nSOM神经网络是一种基于模型的聚类方法。神经网络是一种基于模型的聚类方法。SOM神经网络由输入层和竞争层组成。神经网络由输入层和竞争层组成。n输入层由输入层由N个输入神经元组成，竞争层由个输

89、入神经元组成，竞争层由m m = M个输出神经元组成，且形成一个二维平面阵列。个输出神经元组成，且形成一个二维平面阵列。n输入层各神经元与竞争层各神经元之间实现全互输入层各神经元与竞争层各神经元之间实现全互连接。连接。n该网络根据其学习规则，通过对输入模式的反复学该网络根据其学习规则，通过对输入模式的反复学习，捕捉住各个输入模式中所含的模式特征，并对习，捕捉住各个输入模式中所含的模式特征，并对其进行自组织，在竞争层将聚类结果表现出来，进其进行自组织，在竞争层将聚类结果表现出来，进行自动聚类。竞争层的任何一个神经元都可以代表行自动聚类。竞争层的任何一个神经元都可以代表聚类结果。聚类结果。SOMS

90、OM神经网络神经网络l图图1给出了给出了SOM神经网络基本结构，图神经网络基本结构，图2给出了结构中各输给出了结构中各输入神经元与竞争层神经元入神经元与竞争层神经元j的连接情况。的连接情况。 图图1 SOM网络基本结构网络基本结构 图图2 输入神经元与竞争层神经元输入神经元与竞争层神经元j的连接情况的连接情况l设网络的输入模式为设网络的输入模式为 k k=1,2,=1,2, , p p；竞争层神经元向量为；竞争层神经元向量为B Bj j=(=(b bj1j1, ,b bj2j2, , ,b bjmjm) )，j j =1,2, =1,2, ,m m；其中；其中A Ak k为连续值，为连续值，B

91、 Bj j为为数字量。网络的连接权为数字量。网络的连接权为 w wijij i i=1,2,=1,2, ,N N； j j=1,2,=1,2, ,M M。lSOMSOM网络寻找与输入模式网络寻找与输入模式A Ak k最接近的连接权向量最接近的连接权向量W Wg g=(=(w wg1g1, ,w wg2g2, , ,w wgNgN) )，将该连接权向量，将该连接权向量W Wg g进一步朝与输进一步朝与输入模式入模式AkAk接近的方向调整，而且还调整邻域内的各个接近的方向调整，而且还调整邻域内的各个连接权向量连接权向量W Wj j，j j N Ng g( (t t) )。随着学习次数的增加，邻。随着学习次数的增加，邻域逐渐缩小。最终得到聚类结果。域逐渐缩小。最终得到聚类结果。lSOMSOM类似于大脑的信息处理过程，对二维或三维数据的类似于大脑的信息处理过程，对二维或三维数据的可视是非常有效的。可视是非常有效的。SOMSOM网络的最大局限性是，当学习网络的最大局限性是，当学习模式较少时，网络的聚类效果取决于输入模式的先后模式较少时，网络的聚类效果取决于输入模式的先后顺序；且网络连接权向量的初始状态对网络的收敛性顺序；且网络连接权向量的初始状态对网络的收敛性能有很大影响。能有很大影响。