ch8 聚类数据挖掘技术.ppt

第八章第八章 聚类数据挖掘技术聚类数据挖掘技术，一、聚类一、聚类:l按照数据之间的按照数据之间的相似性相似性，对数据集进行分组或分类，对数据集进行分组或分类（簇（簇,cluster）的过程，试图使类内差距最小化，的过程，试图使类内差距最小化，类间差距最大化。类间差距最大化。l利用聚类结果，可以提取数据集中隐藏的信息，对利用聚类结果，可以提取数据集中隐藏的信息，对未来数据进行未来数据进行预测和分类预测和分类。应用于数据挖掘、模式。应用于数据挖掘、模式识别、图像处理、经济学识别、图像处理、经济学“物以类聚，人以群分物以类聚，人以群分”l聚类分析源于许多研究领域，包括数据挖掘、聚类分析源于许多研究领域，包括数据挖掘、统计学、机器学习、模式识别等。作为一个数统计学、机器学习、模式识别等。作为一个数据挖掘中的一个功能，聚类分析能作为一个独据挖掘中的一个功能，聚类分析能作为一个独立的工具来获得数据分布的情况，并且概括出立的工具来获得数据分布的情况，并且概括出每个簇的特点，或者集中注意力对特定的某些每个簇的特点，或者集中注意力对特定的某些簇做进一步的分析。簇做进一步的分析。l数据挖掘技术的一个突出的特点是处理巨大数据挖掘技术的一个突出的特点是处理巨大的、复杂的数据集，这对聚类分析技术提出了的、复杂的数据集，这对聚类分析技术提出了特殊的挑战，要求算法具有可伸缩性、处理不特殊的挑战，要求算法具有可伸缩性、处理不同类型属性的能力、发现任意形状的类、处理同类型属性的能力、发现任意形状的类、处理高维数据的能力等。根据潜在的各项应用，数高维数据的能力等。根据潜在的各项应用，数据挖掘对聚类分析方法提出了不同要求。据挖掘对聚类分析方法提出了不同要求。二、聚类在数据挖掘中的典型应用：二、聚类在数据挖掘中的典型应用：n聚类分析可以作为其它算法的预处理步骤聚类分析可以作为其它算法的预处理步骤：利用聚类进：利用聚类进行数据预处理，可以获得数据的基本概况，在此基础上行数据预处理，可以获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析，以获得进一步的有可将聚类结果用于进一步关联分析，以获得进一步的有用信息。用信息。n可以作为一个独立的工具来获得数据的分布情况可以作为一个独立的工具来获得数据的分布情况：聚类：聚类分析是获得数据分布情况的有效方法。通过观察聚类得分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步到的每个簇的特点，可以集中对特定的某些簇作进一步分析。这在诸如市场细分、目标顾客定位、业绩估评、分析。这在诸如市场细分、目标顾客定位、业绩估评、生物种群划分等方面具有广阔的应用前景。生物种群划分等方面具有广阔的应用前景。n聚类分析可以完成孤立点挖掘聚类分析可以完成孤立点挖掘：许多数据挖掘算法试图：许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。然而孤立点本身使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。着欺诈行为的存在。广泛的应用领域广泛的应用领域l商务：商务：帮助市场分析人员从客户信息库中发现不同的帮助市场分析人员从客户信息库中发现不同的客户群客户群，用购买模式来刻画不同的客户群的特征用购买模式来刻画不同的客户群的特征l土地使用：土地使用：在地球观测数据库中识别土地使用情况相在地球观测数据库中识别土地使用情况相似的地区似的地区l保险业：保险业：汽车保险单持有者的分组汽车保险单持有者的分组l城市规划：城市规划：根据根据房子的类型，价值和地理分布对房子房子的类型，价值和地理分布对房子分组分组l生物学：生物学：推导植物和动物的分类，对基因进行分类推导植物和动物的分类，对基因进行分类n聚类分析的目标就是形成的数据簇，并且满足聚类分析的目标就是形成的数据簇，并且满足下面两个条件：下面两个条件：n一个簇内的数据尽量相似（一个簇内的数据尽量相似（high high intra-classintra-class similaritysimilarity）；）；n不同簇的数据尽量不相似（不同簇的数据尽量不相似（low low inter-classinter-class similaritysimilarity）。）。n衡量一个聚类分析算法质量，依靠：衡量一个聚类分析算法质量，依靠：n相似度测量机制是否合适。相似度测量机制是否合适。n是否能发现数据背后潜在的、手工难以发现的类知识。是否能发现数据背后潜在的、手工难以发现的类知识。三、聚类分析的目标三、聚类分析的目标:四、聚类分析方法的分类四、聚类分析方法的分类:n按照聚类的标准，聚类方法可分为如下两种：按照聚类的标准，聚类方法可分为如下两种：n统计聚类方法：这种聚类方法主要基于对象之间的几统计聚类方法：这种聚类方法主要基于对象之间的几何距离的。何距离的。n概念聚类方法：概念聚类方法基于对象具有的概念进概念聚类方法：概念聚类方法基于对象具有的概念进行聚类。行聚类。n按照聚类算法所处理的数据类型，聚类方法可分为三种：按照聚类算法所处理的数据类型，聚类方法可分为三种：n数值型数据聚类方法：所分析的数据的属性只限于数数值型数据聚类方法：所分析的数据的属性只限于数值数据。值数据。n离散型数据聚类方法：所分析的数据的属性只限于离离散型数据聚类方法：所分析的数据的属性只限于离散型数据。散型数据。n混合型数据聚类方法：能同时处理数值和离散数据。混合型数据聚类方法：能同时处理数值和离散数据。n按照聚类的尺度，聚类方法可被分为以下三种：按照聚类的尺度，聚类方法可被分为以下三种：n基于距离的聚类算法：用各式各样的距离来衡量数据基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度，如对象之间的相似度，如k k-means-means、k k-medoids-medoids、BIRCHBIRCH、CURECURE等算法。等算法。n基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。基于密度的聚类方法主要是依据合适的密度函数等。n基于互连性基于互连性(Linkage-Based)(Linkage-Based)的聚类算法：通常基于的聚类算法：通常基于图或超图模型。高度连通的数据聚为一类。图或超图模型。高度连通的数据聚为一类。n按照聚类聚类分析算法的主要思路，可以被归纳为如下按照聚类聚类分析算法的主要思路，可以被归纳为如下几种。几种。n划分法（划分法（Partitioning MethodsPartitioning Methods）：）：基于一定标准构基于一定标准构建数据的划分。属于该类的聚类方法有：建数据的划分。属于该类的聚类方法有：k-meansk-means、k-k-modesmodes、k-prototypesk-prototypes、k-medoidsk-medoids、PAMPAM、CLARACLARA、CLARANSCLARANS等。等。n层次法（层次法（Hierarchical MethodsHierarchical Methods）：）：对给定数据对象对给定数据对象集合进行层次的分解。集合进行层次的分解。n密度法（密度法（density-based Methodsdensity-based Methods）：）：基于数据对象基于数据对象的相连密度评价。的相连密度评价。n网格法（网格法（Grid-based MethodsGrid-based Methods）：）：将数据空间划分成将数据空间划分成为有限个单元（为有限个单元（CellCell）的网格结构，基于网格结构进的网格结构，基于网格结构进行聚类。行聚类。n模型法（模型法（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)常用点间距离常用点间距离常用点间距离常用点间距离相异度相异度相异度相异度l欧式距离欧式距离l城区距离城区距离l切比雪夫距离切比雪夫距离l明科夫斯基距离明科夫斯基距离数据矢量数据矢量x=(x1,x2,xn),y=(y1,y2,yn).常用类间距离常用类间距离常用类间距离常用类间距离l最短距离法最短距离法l最长距离法最长距离法l类平均法类平均法l重心法重心法两个聚类两个聚类p和和q.六、聚类方法六、聚类方法l划分方法划分方法：构造数据的最优划分：构造数据的最优划分l层次方法层次方法：对数据进行层次分解或合并：对数据进行层次分解或合并l基于密度的方法基于密度的方法：（：（1）基于密度连通性，如）基于密度连通性，如DBSCAN,OPTICS；（；（2）基于密度分布函数，基于密度分布函数，如如DENCLUEl基于网格的方法基于网格的方法：采用多分辨率网格数据结构，：采用多分辨率网格数据结构，如如STING,BANG,CLIQUE,MAFIAl基于模型的方法基于模型的方法：SOM神经网络神经网络(1)(1)划分方法划分方法n给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇，k n。也就是说，它将数据划分为k个簇，而且这k个划分满足下列条件：n每一个簇至少包含一个对象。n每一个对象属于且仅属于一个簇。n对于给定的k，算法首先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。l启发式方法启发式方法:k-平均算法和平均算法和k-中心点算法中心点算法k-均值算法均值算法:每个簇用该簇中对象的平均值每个簇用该簇中对象的平均值来表示。来表示。k-中心点算法中心点算法:每个簇用接近聚类中心的一每个簇用接近聚类中心的一个对象来表示个对象来表示nk k-means-means算法，也被称为算法，也被称为k k-平均或平均或k k-均值，是一种均值，是一种得到最广泛使用的聚类算法。相似度的计算根据一得到最广泛使用的聚类算法。相似度的计算根据一个簇中对象的平均值来进行。个簇中对象的平均值来进行。首先将所有对象随机分配到首先将所有对象随机分配到k个非空的簇中。个非空的簇中。计算每个簇的平均值，并用该平均值代表相应的簇。计算每个簇的平均值，并用该平均值代表相应的簇。根据每个对象与各个簇中心的距离，分配给最近的簇。根据每个对象与各个簇中心的距离，分配给最近的簇。然后转第二步，重新计算每个簇的平均值。这个过程然后转第二步，重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。不断重复直到满足某个准则函数才停止。K-K-均值算法均值算法K-均值聚类示例均值聚类示例From“Data Mining:Concepts and Techniques”,J.Han and M.Kamber算法算法 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*/(6)UNTIL E不再明显地发生变化。不再明显地发生变化。n算法首先随机地选择算法首先随机地选择k k个对象，每个对象初始地代表了个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。的平均值。这个过程不断重复，直到准则函数收敛。n准则函数试图使生成的结果簇尽可能地紧凑和独立。准则函数试图使生成的结果簇尽可能地紧凑和独立。样本数据样本数据序号序号 属性属性 1 属性属性 21 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-means(设设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）。）。第二次迭代：通过平均值调整对象的所在的簇，重新聚类，第二次迭代：通过平均值调整对象的所在的簇，重新聚类，即将所有点按离平均值点（即将所有点按离平均值点（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，2，3，4和和5，6，7，8，发现没有出现重新分配，而且准则函数，发现没有出现重新分配，而且准则函数收敛，程序结束。收敛，程序结束。实例实例k k-means-means算法的性能分析算法的性能分析n主要优点：主要优点：n是解决聚类问题的一种经典算法，简单、快速。是解决聚类问题的一种经典算法，简单、快速。n对处理大数据集，该算法是相对可伸缩和高效率的。对处理大数据集，该算法是相对可伸缩和高效率的。n当结果簇是密集的，它的效果较好。当结果簇是密集的，它的效果较好。n主要缺点主要缺点n在簇的平均值被定义的情况下才能使用，可能不适用于在簇的平均值被定义的情况下才能使用，可能不适用于某些应用。某些应用。n必须事先给出必须事先给出k k（要生成的簇的数目），而且对初值敏要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。感，对于不同的初始值，可能会导致不同结果。n不适合于发现非凸面形状的簇或者大小差别很大的簇。不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于而且，它对于“躁声躁声”和孤立点数据是敏感的。和孤立点数据是敏感的。k k-means-means算法的几种改进方法算法的几种改进方法nk k-mode-mode 算法：实现对离散数据的快速聚类，保留算法：实现对离散数据的快速聚类，保留了了k k-means-means算法的效率同时将算法的效率同时将k k-means-means的应用范围扩的应用范围扩大到离散数据。大到离散数据。nk k-prototype-prototype算法：可以对离散与数值属性两种混算法：可以对离散与数值属性两种混合的数据进行聚类，在合的数据进行聚类，在k k-prototype-prototype中定义了一个中定义了一个对数值与离散属性都计算的相异性度量标准。对数值与离散属性都计算的相异性度量标准。nk k-中心点算法中心点算法k k-means-means算法对于孤立点是敏感的。算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。象与其参照点之间的相异度之和的原则来执行的。k-k-中心点算法（中心点算法（k-medoidsk-medoids）l也称也称PAM算法（算法（Partitioning Around Medoids）基于有代表性的数据（基于有代表性的数据（中心点中心点），而不是均值代），而不是均值代表每个簇。表每个簇。l思路思路 1.1.为每个簇随机选择一个代表对象为每个簇随机选择一个代表对象(中心点中心点)；2.2.剩余的对象根据其与代表对象的距离分配给剩余的对象根据其与代表对象的距离分配给与其最近的一个簇；与其最近的一个簇；3.3.反复地用非代表对象来替换代表对象，以提反复地用非代表对象来替换代表对象，以提高聚类的质量，直至找到最合适的中心点。高聚类的质量，直至找到最合适的中心点。nPAM作为最早提出的作为最早提出的k-中心点算法之一，它选用簇中中心点算法之一，它选用簇中位置最中心的对象作为代表对象，试图对位置最中心的对象作为代表对象，试图对n个对象给出个对象给出k个划分。个划分。n代表对象也被称为是中心点，其他对象则被称为非代代表对象也被称为是中心点，其他对象则被称为非代表对象。表对象。n最初随机选择最初随机选择k个对象作为中心点，该算法反复地用非个对象作为中心点，该算法反复地用非代表对象来代替代表对象，试图找出更好的中心点，以代表对象来代替代表对象，试图找出更好的中心点，以改进聚类的质量。改进聚类的质量。n在每次迭代中，所有可能的对象对被分析，每个对中在每次迭代中，所有可能的对象对被分析，每个对中的一个对象是中心点，而另一个是非代表对象。的一个对象是中心点，而另一个是非代表对象。n对可能的各种组合，估算聚类结果的质量。一个对象对可能的各种组合，估算聚类结果的质量。一个对象Oi被可以产生最大平方被可以产生最大平方-误差值减少的对象代替。在一次误差值减少的对象代替。在一次迭代中产生的最佳对象集合成为下次迭代的中心点。迭代中产生的最佳对象集合成为下次迭代的中心点。计算用非代计算用非代表对象表对象h替替换代表对象换代表对象i的的总代价总代价：单个数据单个数据的的替换代替换代价价：用：用h代替代替i后，后，j到中心到中心点距离的点距离的变化变化为了判定一个非代表对象为了判定一个非代表对象为了判定一个非代表对象为了判定一个非代表对象OOh h是否是当前一个代表是否是当前一个代表是否是当前一个代表是否是当前一个代表对象对象对象对象OOi i的好的替代，对于每一个非中心点对象的好的替代，对于每一个非中心点对象的好的替代，对于每一个非中心点对象的好的替代，对于每一个非中心点对象OOj j，下面的四种情况被考虑下面的四种情况被考虑下面的四种情况被考虑下面的四种情况被考虑:第一种情况：第一种情况：第一种情况：第一种情况：OOj j当前隶属于中心点对象当前隶属于中心点对象当前隶属于中心点对象当前隶属于中心点对象OOi i。如果如果如果如果OOi i被被被被OOh h所代替作为中心点，且所代替作为中心点，且所代替作为中心点，且所代替作为中心点，且OOj j离一个离一个离一个离一个OOmm最近，最近，最近，最近，i i mm，那么那么那么那么OOj j被重新分配给被重新分配给被重新分配给被重新分配给OOmm。第二种情况：第二种情况：第二种情况：第二种情况：OOj 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代替作为一个中心点，而代替作为一个中心点，而代替作为一个中心点，而代替作为一个中心点，而OOj j依然离依然离依然离依然离OOmm最近，那么对象最近，那么对象最近，那么对象最近，那么对象的隶属不发生变化。的隶属不发生变化。的隶属不发生变化。的隶属不发生变化。第四种情况：第四种情况：第四种情况：第四种情况：OOj j当前隶属于中心点当前隶属于中心点当前隶属于中心点当前隶属于中心点OOmm，mm i i。如果如果如果如果OOi i被被被被OOh h代替作为一个中心点，且代替作为一个中心点，且代替作为一个中心点，且代替作为一个中心点，且OOj j离离离离OOh h最近，那么最近，那么最近，那么最近，那么OOi i被重新被重新被重新被重新分配给分配给分配给分配给OOh h。n每当重新分配发生时，平方每当重新分配发生时，平方-误差误差E所产生的差别对代价所产生的差别对代价函数有影响。因此，如果一个当前的中心点对象被非中心函数有影响。因此，如果一个当前的中心点对象被非中心点对象所代替，代价函数计算平方点对象所代替，代价函数计算平方-误差值所产生的差别。误差值所产生的差别。替换的总代价是所有非中心点对象所产生的代价之和。替换的总代价是所有非中心点对象所产生的代价之和。n如果总代价是负的，那么实际的平方如果总代价是负的，那么实际的平方-误差将会减小，误差将会减小，Oi可以被可以被Oh替代。替代。n如果总代价是正的，则当前的中心点如果总代价是正的，则当前的中心点Oi被认为是可接被认为是可接受的，在本次迭代中没有变化。受的，在本次迭代中没有变化。总代价定义如下：总代价定义如下：其中，其中，Cjih表示表示Oj在在Oi被被Oh代替后产生的代价。下面介代替后产生的代价。下面介绍上面所述的四种情况中代价函数的计算公式，其中所引绍上面所述的四种情况中代价函数的计算公式，其中所引用的符号有：用的符号有：Oi和和Om是两个原中心点，是两个原中心点，Oh将替换将替换Oi作为新作为新的中心点。的中心点。第二种情况第二种情况 Oj被重新分配给Oh，Cjih=d(j,h)-d(j,i)第一种情况第一种情况 Oj被重新分配给Om，Cjih=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）指派每个剩余的对象给离它最近的中心点所代表的簇；指派每个剩余的对象给离它最近的中心点所代表的簇；（4）REPEAT（5）选择一个未被选择的中心点选择一个未被选择的中心点Oi；（6）REPEAT（7）选择一个未被选择过的非中心点对象选择一个未被选择过的非中心点对象Oh；（8）计算用计算用Oh代替代替Oi的总代价并记录在的总代价并记录在S中；中；（9）UNTIL 所有的非中心点都被选择过；所有的非中心点都被选择过；（10）UNTIL 所有的中心点都被选择过；所有的中心点都被选择过；（11）IF 在在S中的所有非中心点代替所有中心点后的计算出的总代中的所有非中心点代替所有中心点后的计算出的总代价有小于价有小于0的存在的存在 THEN 找出找出S中的用非中心点替代中心点后代价最中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中个中心点的集合；心点的集合；（12）UNTIL 没有再发生簇的重新分配，即所有的没有再发生簇的重新分配，即所有的S都大于都大于0.实例实例假如空间中的五个点假如空间中的五个点A、如图、如图1所示，所示，各点之间的距离关系如表各点之间的距离关系如表1所示，根据所给的数据对其运所示，根据所给的数据对其运行行PAM算法实现划分聚类（设算法实现划分聚类（设k=2）。）。样本点间距离如样本点间距离如下表所示下表所示:样本点样本点 起始中心点为起始中心点为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、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中心点所在的簇，当中心点所在的簇，当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)=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。在上述代价计算完毕后，我们要选取一个最小的代在上述代价计算完毕后，我们要选取一个最小的代价，显然有多种替换可以选择，选择第一个最小代价的价，显然有多种替换可以选择，选择第一个最小代价的替换（也就是替换（也就是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图图 替换中心点替换中心点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 (c)E-2 (c)E替换替换B,B,TCTCBEBE=-2-2图图 替换中心点替换中心点B B 通过上述计算，已经完成了通过上述计算，已经完成了PAMPAM算法的第一次迭代。算法的第一次迭代。在下一迭代中，将用其他的非中心点在下一迭代中，将用其他的非中心点AA、D D、EE替换中心替换中心点点BB、CC，找出具有最小代价的替换。一直重复上述过找出具有最小代价的替换。一直重复上述过程，直到代价不再减小为止。程，直到代价不再减小为止。PAM算法特点算法特点l比比k-means健壮，但对于大数据集效率不健壮，但对于大数据集效率不高。高。l当存在当存在“噪声噪声”和离群数据时，和离群数据时，k-中心中心点方法比点方法比k均值方法更健壮，这是因为中均值方法更健壮，这是因为中心点不像平均值那样易被极端数据影响。心点不像平均值那样易被极端数据影响。lk-中心点方法的执行代价比中心点方法的执行代价比k-平均高。平均高。改进算法改进算法lCLARA(Clustering Large Applications),1990 用实际数据的抽样来代替整个数据，然后再在这些用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用抽样的数据上利用K-medoids算法得到最佳的中心算法得到最佳的中心点点。如果样本是以非随机的方式选取，它应当足以代如果样本是以非随机的方式选取，它应当足以代替原来的数据集合。从中选出的代表对象（中心替原来的数据集合。从中选出的代表对象（中心点）很可能与从整个数据集合选出的代表相似。点）很可能与从整个数据集合选出的代表相似。改进算法改进算法CLARANS(“随机化的随机化的”CLARA)，1994 利用多次不同抽样来改进利用多次不同抽样来改进CLARA。其聚类过程可以被描述为对一个图的收索过程，图中其聚类过程可以被描述为对一个图的收索过程，图中的每一个节点都是一个潜在的解，即的每一个节点都是一个潜在的解，即k个中心点的集个中心点的集合。在替换了一个中心点后得到的聚类结果被当成是合。在替换了一个中心点后得到的聚类结果被当成是前聚类结果的邻居。如果一个更好的邻居被发现，也前聚类结果的邻居。如果一个更好的邻居被发现，也就是说它有更小的平方误差值，就是说它有更小的平方误差值，clarans移到该邻居节移到该邻居节点，处理过程重新开始，如果没有发现更好的邻居，点，处理过程重新开始，如果没有发现更好的邻居，则达到局部最优。则达到局部最优。(2)(2)层次聚类方法层次聚类方法n层次聚类方法对给定的数据集进行层次的分解，层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：直到某种条件满足为止。具体又可分为：n凝聚的层次聚类：一种自底向上的策略，首先将每凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。的簇，直到某个终结条件被满足。n分裂的层次聚类：采用自顶向下的策略，它首先将分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。簇，直到达到了某个终结条件。n层次凝聚的代表是层次凝聚的代表是AGNES算法。层次分裂的算法。层次分裂的代表是代表是DIANA算法。算法。AGNESAGNES算法算法nAGNES(AGNES(AGglomerativeAGglomerative NEStingNESting)算法最初算法最初将每个对象作为一个簇，然后这些簇根据某将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度些准则被一步步地合并。两个簇间的相似度由这两个不同簇中距离最近的数据点对的相由这两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到似度来确定。聚类的合并过程反复进行直到所有的对象最终满足簇数目。所有的对象最终满足簇数目。算法算法 AGNES（自底向上凝聚算法）自底向上凝聚算法）输入：包含输入：包含n个对象的数据库，终止条件簇的数目个对象的数据库，终止条件簇的数目k。输出：输出：k个簇，达到终止条件规定簇数目。个簇，达到终止条件规定簇数目。(1)将每个对象当成一个初始簇；将每个对象当成一个初始簇；(2)REPEAT(3)根据两个簇中最近的数据点找到最近的两个簇；根据两个簇中最近的数据点找到最近的两个簇；(4)合并两个簇，生成新的簇的集合；合并两个簇，生成新的簇的集合；(5)UNTIL 达到定义的簇的数目；达到定义的簇的数目；实例实例序号序号属性属性 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步：根据初始簇计算每个簇之间的距离，随步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距机找出距离最小的两个簇，进行合并，最小距离为离为1，合并后，合并后1，2点合并为一个簇。点合并为一个簇。第第2步：，对上一次合并后的簇计算簇间距离，步：，对上一次合并后的簇计算簇间距离，找出距离最近的两个簇进行合并，合并后找出距离最近的两个簇进行合并，合并后3，4点成为一簇。点成为一簇。第第3步：重复第步：重复第2步的工作，步的工作，5，6点成为一簇。点成为一簇。第第4步：重复第步：重复第2步的工作，步的工作，7，8点成为一簇。点成为一簇。第第5步：合并步：合并1，2，3，4成为一个包含四成为一个包含四个点的簇。个点的簇。第第6步：合并步：合并5，6，7，8，由于合并后的，由于合并后的簇的数目已经达到了用户输入的终止条件程序簇的数目已经达到了用户输入的终止条件程序结束。结束。AGNESAGNES算法的性能分析算法的性能分析nAGNES算法比较简单，但经常会遇到合并点选择的困算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤消，聚类之间也不能交换对的簇上进行。已做处理不能撤消，聚类之间也不能交换对象。如果在某