资源描述
2019年6月29日星期六,DMKD Sides By MAO,1,第五章 聚类方法 内容提要,聚类方法概述
划分聚类方法
层次聚类方法
密度聚类方法
其它聚类方法,2019年6月29日星期六,DMKD Sides By MAO,2,聚类分析研究概述,聚类分析源于许多研究领域，包括数据挖掘、统计学、机器学习、模式识别等。作为一个数据挖掘中的一个功能，聚类分析能作为一个独立的工具来获得数据分布的情况，并且概括出每个簇的特点，或者集中注意力对特定的某些簇做进一步的分析。
数据挖掘技术的一个突出的特点是处理巨大的、复杂的数据集，这对聚类分析技术提出了特殊的挑战，要求算法具有可伸缩性、处理不同类型属性的能力、发现任意形状的类、处理高维数据的能力等。根据潜在的各项应用，数据挖掘对聚类分析方法提出了不同要求。,2019年6月29日星期六,DMKD Sides By MAO,3,聚类分析在数据挖掘中的应用分析,聚类在数据挖掘中的典型应用有：
聚类分析可以作为其它算法的预处理步骤：利用聚类进行数据预处理，可以获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析，以获得进一步的有用信息。
可以作为一个独立的工具来获得数据的分布情况：聚类分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步分析。这在诸如市场细分、目标顾客定位、业绩估评、生物种群划分等方面具有广阔的应用前景。
聚类分析可以完成孤立点挖掘：许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。,2019年6月29日星期六,DMKD Sides By MAO,4,聚类概念,定义 5-1 聚类分析的输入可以用一组有序对(X, s) 或(X, d)表示，这里X表示一组样本，s和d分别是度量样本间相似度或相异度（距离）的标准。聚类系统的输出是一个分区若C={C1, C2,…, Ck}，其中Ci(i=1,2….,K)是X的子集，且满足：
C1 C2,… , Ck=X
C1∩C2= Ø, ij
C中的成员C1, C2,…, Ck叫做类或簇（Cluster），每一个类或簇都是通过一些特征描述的，通常有如下几种表示方式：
通过它们的中心或类中关系远的（边界）点表示空间的一类点。
使用聚类树中的结点图形化地表示一个类。
使用样本属性的逻辑表达式表示类。
用中心表示一个类是最常见的方式，当类是紧密的或各向同性时用这种方法非常好，然而，当类是伸长的或向各向分布异性时，这种方式就不能正确地表示它们了。,2019年6月29日星期六,DMKD Sides By MAO,5,聚类分析的目标,聚类分析的目标就是形成的数据簇，并且满足下面两个条件：
一个簇内的数据尽量相似（high intra-class similarity）；
不同簇的数据尽量不相似（low inter-class similarity）。
衡量一个聚类分析算法质量，依靠：
相似度测量机制是否合适。
是否能发现数据背后潜在的、手工难以发现的类知识。,2019年6月29日星期六,DMKD Sides By MAO,6,聚类分析方法的分类,按照聚类的标准，聚类方法可分为如下两种：
统计聚类方法：这种聚类方法主要基于对象之间的几何距离的。
概念聚类方法：概念聚类方法基于对象具有的概念进行聚类。
按照聚类算法所处理的数据类型，聚类方法可分为三种：
数值型数据聚类方法：所分析的数据的属性只限于数值数据。
离散型数据聚类方法：所分析的数据的属性只限于离散型数据。
混合型数据聚类方法：能同时处理数值和离散数据。
按照聚类的尺度，聚类方法可被分为以下三种：
基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度，如k-means、k-medoids、BIRCH、CURE等算法。
基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。
基于互连性(Linkage-Based)的聚类算法：通常基于图或超图模型。高度连通的数据聚为一类。
按照聚类聚类分析算法的主要思路，可以被归纳为如下几种。
划分法（Partitioning Methods）：基于一定标准构建数据的划分。
属于该类的聚类方法有：k-means、k-modes、k-prototypes、k-medoids、PAM、CLARA、CLARANS等。
层次法（Hierarchical Methods）：对给定数据对象集合进行层次的分解。
密度法（density-based Methods）：基于数据对象的相连密度评价。
网格法（Grid-based Methods）：将数据空间划分成为有限个单元（Cell）的网格结构，基于网格结构进行聚类。
模型法（Model-Based Methods）：给每一个簇假定一个模型，然后去寻找能够很好的满足这个模型的数据集。,2019年6月29日星期六,DMKD Sides By MAO,7,常见的距离函数,按照距离公理，在定义距离测度时需要满足距离公理的四个条件自相似性、最小性、对称性以及三角不等性。常用的距离函数有如下几种：
明可夫斯基距离（Minkowski）
二次型距离（Quadratic）
余弦距离
二元特征样本的距离度量,2019年6月29日星期六,DMKD Sides By MAO,8,明可夫斯基（Minkowski）距离,假定x和y是相应的特征，n是特征的维数。 x和y的明可夫斯基距离度量的形式如下：
当取不同的值时，上述距离度量公式演化为一些特殊的距离测度:
当γ=1时，明可夫斯基距离演变为绝对值距离：
当γ=2时，明可夫斯基距离演变为欧氏距离：,,,2019年6月29日星期六,DMKD Sides By MAO,9,二次型距离,二次型距离测度的形式如下：
其中A是非负定矩阵。
当取不同的值时，上述距离度量公式演化为一些特殊的距离测度：
当A为单位矩阵时，二次型距离演变为欧氏距离。
当A为对角阵时，二次型距离演变为加权欧氏距离：
当为协方差矩阵时，二次型距离演变为马氏距离。,,,2019年6月29日星期六,DMKD Sides By MAO,10,余弦距离,余弦距离的度量形式如下：,,2019年6月29日星期六,DMKD Sides By MAO,11,二元特征样本的距离度量,对于包含一些或全部不连续特征的样本，计算样本间的距离是比较困难的。因为不同类型的特征是不可比的，只用一个标准作为度量标准是不合适的。下面我们介绍几种二元类型数据的距离度量标准。
假定x和y分别是n维特征， xi和yi分别表示每维特征，且xi和yi的取值为二元类型数值{0，1}。则x和y的距离定义的常规方法是先求出如下几个参数，然后采用SMC、Jaccard系数或Rao系数。
设a，b，c和d是样本x和y中满足xi=yi=1， xi=1且yi=0， xi=0且yi=1和xi=yi=0的二元类型属性的数量，则
简单匹配系数（Simple Match Coefficient,SMC）
Jaccard系数
Rao系数,,,,2019年6月29日星期六,DMKD Sides By MAO,12,类间距离,距离函数都是关于两个样本的距离刻画，然而在聚类应用中，最基本的方法是计算类间的距离。
设有两个类Ca和Cb，它们分别有m和h个元素，它们的中心分别为γa和γb。设元素x∈ Ca，y∈ Cb ，这两个元素间的距离通常通过类间距离来刻画，记为D(Ca, Cb)。
类间距离的度量主要有：
最短距离法：定义两个类中最靠近的两个元素间的距离为类间距离。
最长距离法：定义两个类中最远的两个元素间的距离为类间距离。
中心法：定义两类的两个中心间的距离为类间距离。
类平均法：它计算两个类中任意两个元素间的距离，并且综合他们为类间距离：
离差平方和。,,2019年6月29日星期六,DMKD Sides By MAO,13,中心法,中心法涉及到类的中心的概念。假如Ci是一个聚类，x是Ci内的一个数据点，那么类中心定义如下：
其中ni是第i个聚类中的点数。因此，两个类Ca和Cb的类间距离为：
其中γa和γb是类Ca和Cb的中心点，d是某种形式的距离公式。,,2019年6月29日星期六,DMKD Sides By MAO,14,离差平方和,离差平方和用到了类直径的概念：
类的直径反映了类中各元素间的差异，可定义为类中各元素至类中心的欧氏距离之和，其量纲为距离的平方：
根据上式得到两类Ca和Cb的直径分别为γa和γb ，类Ca +b= Ca Cb的直径为γa +b ，则可定义类间距离的平方为：,,,2019年6月29日星期六,DMKD Sides By MAO,15,第五章 聚类方法 内容提要,聚类方法概述
划分聚类方法
层次聚类方法
密度聚类方法
其它聚类方法,2019年6月29日星期六,DMKD Sides By MAO,16,划分聚类算法的主要思想,定义 5-2 给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇，k n。也就是说，它将数据划分为k个簇，而且这k个划分满足下列条件：
每一个簇至少包含一个对象。
每一个对象属于且仅属于一个簇。
对于给定的k，算法首先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。,2019年6月29日星期六,DMKD Sides By MAO,17,聚类设计的评价函数,一种直接方法就是观察聚类的类内差异（Within cluster variation）和类间差异(Between cluster variation）。
类内差异：衡量聚类的紧凑性，类内差异可以用特定的距离函数来定义，例如，
类间差异：衡量不同聚类之间的距离，类间差异定义为聚类中心间的距离，例如，
聚类的总体质量可被定义为w(c)和b(c)的一个单调组合，比如w(c) / b(c) 。,,2019年6月29日星期六,DMKD Sides By MAO,18,k-means算法,k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。相似度的计算根据一个簇中对象的平均值来进行。
算法首先随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。
准则函数试图使生成的结果簇尽可能地紧凑和独立。,算法5-1 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不再明显地发生变化。,2019年6月29日星期六,DMKD Sides By MAO,19,k-means例子,,,样本数据
序号 属性 1 属性 2
1 1 1
2 2 1
3 1 2
4 2 2
5 4 3
6 5 3
7 4 4
8 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，1）最近的原则重新分配。得到两个新的簇：{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}，发现没有出现重新分配，而且准则函数收敛，程序结束。,Copyright © 2001, 2004, Andrew W. Moore,K-means,Ask user how many clusters they’d like. (e.g. k=5),Copyright © 2001, 2004, Andrew W. Moore,K-means,Ask user how many clusters they’d like. (e.g. k=5)
Randomly guess k cluster Center locations,,,,,,Copyright © 2001, 2004, Andrew W. Moore,K-means,Ask user how many clusters they’d like. (e.g. k=5)
Randomly guess k cluster Center locations
Each datapoint finds out which Center it’s closest to. (Thus each Center “owns” a set of datapoints),Copyright © 2001, 2004, Andrew W. Moore,K-means,Ask user how many clusters they’d like. (e.g. k=5)
Randomly guess k cluster Center locations
Each datapoint finds out which Center it’s closest to.
Each Center finds the centroid of the points it owns,,,,,,,,,,,,,,,,,,,,,,,Copyright © 2001, 2004, Andrew W. Moore,K-means,Ask user how many clusters they’d like. (e.g. k=5)
Randomly guess k cluster Center locations
Each datapoint finds out which Center it’s closest to.
Each Center finds the centroid of the points it owns…
…and jumps there
…Repeat until terminated!,,,,,,,,,,,Copyright © 2001, 2004, Andrew W. Moore,K-means Start,Advance apologies: in Black and White this example will deteriorate
Example generated by Dan Pelleg’s super-duper fast K-means system:
Dan Pelleg and Andrew Moore. Accelerating Exact k-means Algorithms with Geometric Reasoning. Proc. Conference on Knowledge Discovery in Databases 1999, (KDD99) (available on www.autonlab.org/pap.html),Copyright © 2001, 2004, Andrew W. Moore,K-means continues…,Copyright © 2001, 2004, Andrew W. Moore,K-means continues…,Copyright © 2001, 2004, Andrew W. Moore,K-means continues…,Copyright © 2001, 2004, Andrew W. Moore,K-means continues…,Copyright © 2001, 2004, Andrew W. Moore,K-means continues…,Copyright © 2001, 2004, Andrew W. Moore,K-means continues…,Copyright © 2001, 2004, Andrew W. Moore,K-means continues…,Copyright © 2001, 2004, Andrew W. Moore,K-means continues…,Copyright © 2001, 2004, Andrew W. Moore,K-means terminates,2019年6月29日星期六,DMKD Sides By MAO,35,k-means算法的性能分析,主要优点：
是解决聚类问题的一种经典算法，简单、快速。
对处理大数据集，该算法是相对可伸缩和高效率的。
当结果簇是密集的，它的效果较好。
主要缺点
在簇的平均值被定义的情况下才能使用，可能不适用于某些应用。
必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。
不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。,2019年6月29日星期六,DMKD Sides By MAO,36,k-means的几种改进方法,k-mode 算法：实现对离散数据的快速聚类，保留了k-means算法的效率同时将k-means的应用范围扩大到离散数据。
k-prototype算法：可以对离散与数值属性两种混合的数据进行聚类，在k-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。
k-中心点算法k -means算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。,2019年6月29日星期六,DMKD Sides By MAO,37,PAM算法基本思想,PAM作为最早提出的k-中心点算法之一，它选用簇中位置最中心的对象作为代表对象，试图对n个对象给出k个划分。
代表对象也被称为是中心点，其他对象则被称为非代表对象。
最初随机选择k个对象作为中心点，该算法反复地用非代表对象来代替代表对象，试图找出更好的中心点，以改进聚类的质量。
在每次迭代中，所有可能的对象对被分析，每个对中的一个对象是中心点，而另一个是非代表对象。
对可能的各种组合，估算聚类结果的质量。一个对象Oi被可以产生最大平方-误差值减少的对象代替。在一次迭代中产生的最佳对象集合成为下次迭代的中心点。,2019年6月29日星期六,DMKD Sides By MAO,38,PAM算法基本思想(续),为了判定一个非代表对象Oh是否是当前一个代表对象Oi的好的替代，对于每一个非中心点对象Oj，下面的四种情况被考虑：
第一种情况：Oj当前隶属于中心点对象Oi。如果Oi被Oh所代替作为中心点，且Oj离一个Om最近，i≠m，那么Oj被重新分配给Om。
第二种情况：Oj当前隶属于中心点对象Oi。如果Oi被Oh代替作为一个中心点，且Oj离Oh最近，那么Oj被重新分配给Oh。
第三种情况：Oj当前隶属于中心点Om，m≠i。如果Oi被Oh代替作为一个中心点，而Oj依然离Om最近，那么对象的隶属不发生变化。
第四种情况：Oj当前隶属于中心点Om，m≠i。如果Oi被Oh代替作为一个中心点，且Oj离Oh最近，那么Oi被重新分配给Oh。,2019年6月29日星期六,DMKD Sides By MAO,39,PAM算法基本思想(续),每当重新分配发生时，平方-误差E所产生的差别对代价函数有影响。因此，如果一个当前的中心点对象被非中心点对象所代替，代价函数计算平方-误差值所产生的差别。替换的总代价是所有非中心点对象所产生的代价之和。
如果总代价是负的，那么实际的平方-误差将会减小，Oi可以被Oh替代。
如果总代价是正的，则当前的中心点Oi被认为是可接受的，在本次迭代中没有变化。
总代价定义如下：
其中，Cjih表示Oj在Oi被Oh代替后产生的代价。下面我们将介绍上面所述的四种情况中代价函数的计算公式，其中所引用的符号有：Oi和Om是两个原中心点，Oh将替换Oi作为新的中心点。,,2019年6月29日星期六,DMKD Sides By MAO,40,PAM算法代价函数的四种情况,,,第二种情况
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),2019年6月29日星期六,DMKD Sides By MAO,41,PAM算法基本思想(续),,,算法5-2 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.,2019年6月29日星期六,DMKD Sides By MAO,42,假如空间中的五个点｛A、Ｂ、Ｃ、Ｄ、Ｅ｝如图1所示，各点之间的距离关系如表1所示，根据所给的数据对其运行PAM算法实现划分聚类（设k=2）。 样本点间距离如下表所示:
样本点 起始中心点为A,B,PAM算法基本思想(续),,,,,,,,,,,,,,,,,,第一步 建立阶段：假如从5个对象中随机抽取的2个中心点为{A，B},则样本被划分为{A、C、D}和{B、E}，如图5-3所示。
第二步 交换阶段：假定中心点A、B分别被非中心点}和{C、D、E}替换，根据PAM算法需要计算下列代价TCAC、 TCAD、 TCAE、TCBC、TCBD、 TCBE。
我们以TCAC为例说明计算过程：
a) 当A被C替换以后，A不再是一个中心点，因为A离B比A离C近，A被分配到B中心点代表的簇，CAAC=d(A,B)-d(A,A)=1。
b) B是一个中心点，当A被C替换以后，B不受影响，CBAC=0。
c) C原先属于A中心点所在的簇，当A被C替换以后，C是新中心点，符合PAM算法代价函数的第二种情况CCAC=d(C,C)-d(C,A)=0-2=-2。
d) D原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是C，根据PAM算法代价函数的第二种情况CDAC=d(D,C)-d(D,A)=1-2=-1。
e) E原先属于B中心点所在的簇，当A被C替换以后，离E最近的中心仍然是 B，根据PAM算法代价函数的第三种情况CEAC=0。
因此，TCAC=CAAC+ CBAC+ CBAC+ CDAC+ CEAC=1+0-2-1+0=-2。,2019年6月29日星期六,DMKD Sides By MAO,43,PAM算法基本思想(续),,,,,,,,,,,,,,,,,,在上述代价计算完毕后，我们要选取一个最小的代价，显然有多种替换可以选择，我们选择第一个最小代价的替换（也就是C替换A），根据图5-4（a）所示，样本点被划分为{ B、A、E}和{C、D}两个簇。图5-4（b）和图5-4（c）分别表示了D替换A，E替换A的情况和相应的代价
(a) C替换A, TCAC=-2 (b) D替换A, TCAD=-2 (c) E替换A, TCAE=-1
图5-4 替换中心点A
图5-5（a）、（b）、（c）分别表示了用C、D、E替换B的情况和相应的代价。
C替换B, TCBC=-2 (b) D替换B, TCBD=-2 (c) E替换B, TCBE=-2
图5-5 替换中心点B
通过上述计算，已经完成了PAM算法的第一次迭代。在下一迭代中，将用其他的非中心点{A、D、E}替换中心点{B、C}，找出具有最小代价的替换。一直重复上述过程，直到代价不再减小为止。,,,,,,,2019年6月29日星期六,DMKD Sides By MAO,44,第五章 聚类方法 内容提要,聚类方法概述
划分聚类方法
层次聚类方法
密度聚类方法
其它聚类方法,2019年6月29日星期六,DMKD Sides By MAO,45,层次聚类方法概述,层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：
凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。
分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。
层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。,2019年6月29日星期六,DMKD Sides By MAO,46,AGNES算法,AGNES (AGglomerative NESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到所有的对象最终满足簇数目。,算法5-3 AGNES（自底向上凝聚算法）
输入：包含n个对象的数据库，终止条件簇的数目k。
输出：k个簇，达到终止条件规定簇数目。
(1) 将每个对象当成一个初始簇；
(2) REPEAT
(3) 根据两个簇中最近的数据点找到最近的两个簇；
(4) 合并两个簇，生成新的簇的集合；
(5) UNTIL 达到定义的簇的数目；,2019年6月29日星期六,DMKD Sides By MAO,47,AGNES算法例子,,,序号 属性 1 属性 2
1 1 1
2 1 2
3 2 1
4 2 2
5 3 4
6 3 5
7 4 4
8 4 5,,步骤 最近的簇距离 最近的两个簇 合并后的新簇
1 1 {1}，{2} {1，2}，{3}，{4}，{5}，{6}，{7}，{8}
2 1 {3}，{4} {1，2}，{3，4}，{5}，{6}，{7}，{8}
3 1 {5}，{6} {1，2}，{3，4}，{5，6}，{7}，{8}
4 1 {7}，{8} {1，2}，{3，4}，{5，6}，{7，8}
5 1 {1，2}，{3，4} {1，2，3，4}，{5，6}，{7，8}
6 1 {5，6}，{7，8} {1，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}，由于合并后的簇的数目已经达到了用户输入的终止条件程序结束。,2019年6月29日星期六,DMKD Sides By MAO,48,AGNES性能分析,AGNES算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤消，聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果。
这种聚类方法不具有很好的可伸缩性，因为合并的决定需要检查和估算大量的对象或簇。
假定在开始的时候有n个簇，在结束的时候有1个簇，因此在主循环中有n次迭代，在第i次迭代中，我们必须在n-i+1个簇中找到最靠近的两个聚类。另外算法必须计算所有对象两两之间的距离，因此这个算法的复杂度为 O(n2)，该算法对于n很大的情况是不适用的。,2019年6月29日星期六,DMKD Sides By MAO,49,DIANA算法,DIANA (Divisive ANAlysis)算法是典型的分裂聚类方法。
在聚类中，用户能定义希望得到的簇数目作为一个结束条件。同时，它使用下面两种测度方法：
簇的直径：在一个簇中的任意两个数据点的距离中的最大值。
平均相异度（平均距离）：,,算法5-4 DIANA（自顶向下分裂算法）
输入：包含n个对象的数据库，终止条件簇的数目k。
输出：k个簇，达到终止条件规定簇数目。
（1）将所有对象整个当成一个初始簇；
（2） FOR （i=1; i≠k; i++) DO BEGIN
（3） 在所有簇中挑出具有最大直径的簇C；
（4） 找出C中与其它点平均相异度最大的一个点p并把p放入splinter group，剩余的放在old party中；
（5）. REPEAT
（6） 在old party里找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点，并将该点加入splinter group。
（7） UNTIL 没有新的old party的点被分配给splinter group；
（8） splinter group和old party为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。
（9） END.,2019年6月29日星期六,DMKD Sides By MAO,50,DIANA算法例子,,,序号 属性 1 属性 2
1 1 1
2 1 2
3 2 1
4 2 2
5 3 4
6 3 5
7 4 4
8 4 5,,步骤 具有最大直径的簇 splinter group Old party
1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}
2 {1，2，3，4，5，6，7，8} {1，2} {3，4，5，6，7，8}
3 {1，2，3，4，5，6，7，8} {1，2，3} {4，5，6，7，8}
4 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8}
5 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8} 终止,第1步，找到具有最大直径的簇，对簇中的每个点计算平均相异度（假定采用是欧式距离）。
1的平均距离：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96
类似地，2的平均距离为2.526；3的平均距离为2.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步，重复第2步的工作，splinter group中放入点3。
第4步，重复第2步的工作，splinter group中放入点4。
第5步，没有在old party中的点放入了splinter group中且达到终止条件（k-2），程序终止。如果没有到终止条件，因该从分裂好的簇中选一个直径最大的簇继续分裂。,2019年6月29日星期六,DMKD Sides By MAO,51,层次聚类方法的改进,层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。
改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。
下面介绍两个改进的层次聚类方法CURE和BIRTH。,2019年6月29日星期六,DMKD Sides By MAO,52,层次聚类方法的改进--BIRCH,BIRCH（利用层次方法的平衡迭代归约和聚类）是一个综合的层次聚类方法，它用聚类特征和聚类特征树（CF）来概括聚类描述。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子B和阂值T的高度平衡树，存储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。
BIRCH算法的工作过程包括两个阶段：
阶段一：BIRCH扫描数据库，建立一个初始存放于内存的CF树，它可以被看作数据的多层压缩，试图保留数据内在的聚类结构。随着对象的插入，CF树被动态地构造，不要求所有的数据读入内存，而可在外存上逐个读入数据项。因此，BIRTH方法对增量或动态聚类也非常有效。
阶段二：BIRCH采用某个聚类算法对CF树的叶结点进行聚类。在这个阶段可以执行任何聚类算法，例如典型的划分方法。
BIRCH算法试图利用可用的资源来生成最好的聚类结果。通过一次扫描就可以进行较好的聚类，故该算法的计算复杂度是O(n)，n是对象的数目。,
展开阅读全文
相关搜索
