第5章 聚类分析第5章 聚类分析5.1 聚类分析的相关概念5.2 模式相似性的测度和聚类准则5.3 基于试探的聚类搜索算法5.4 系统聚类法5.5 动态聚类法5.6 聚类结果的评价5.1 聚类分析的相关概念定义对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。5.1 聚类分析的相关概念模式相似/分类的依据把整个模式样本集的特征向量看成是分布在特征空间中的一些点，点与点之间的距离即可作为模式相似性的测量依据。 聚类分析是按不同对象之间的差异，根据距离函数的规律（大小）进行模式分类的。5.1 聚类分析的相关概念聚类分析的有效性 聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。若向量点的分布是一群一群的，同一群样本密集（距离很近），不同群样本距离很远，则很容易聚类；若样本集的向量分布聚成一团，不同群的样本混在一起，则很难分类；对具体对象做聚类分析的关键是选取合适的特征。特征选取得好，向量分布容易区分，选取得不好，向量分布很难分开。5.1 聚类分析的相关概念两类模式分类的实例：一摊黑白围棋子选颜色颜色作为特征进行分类，用“1”代表白，“0”代表黑，则很容易分类；选大小大小作为特征进行分类，则白子和黑子的特征相同，不能分类（把白子和黑子分开）。5.1 聚类分析的相关概念特征选择的维数在特征选择中往往会选择一些多余的特征，它增加了维数，从而增加了聚类分析的复杂度，但对模式分类却没有提供多少有用的信息。在这种情况下，需要去掉相关程度过高的特征（进行降维处理）。降维方法结论：若rij1，则表明第i维特征与第j维特征所反映的特征规律接近，因此可以略去其中的一个特征，或将它们合并为一个特征，从而使维数降低一维。5.1 聚类分析的相关概念模式对象特征测量的数字化计算机只能处理离散的数值，因此根据识别对象的不同，要进行不同的数据化处理。连续量的量化：用连续量来度量的特性，如长度、重量、面积等等，仅需取其量化值；量级的数量化：度量时不需要详尽的数值，而是相应地划分成一些有次序的量化等级的值。名义尺度：指定性的指标，即特征度量时没有数量关系，也没有明显的次序关系，如黑色和白色的关系，男性和女性的关系等，都可将它们分别用“0”和“1”来表示。5.2 模式相似性的测度和聚类准则5.2.1 相似性测度目的：为了能将模式集划分成不同的类别，必须定义一种相似性的测度，来度量同一类样本间的类似性和不属于同一类样本间的差异性。欧氏距离量纲对分类的影响（下页图例）马氏距离特点：排除了模式样本之间的相关性问题：协方差矩阵在实际应用中难以计算一般化的明氏距离角度相似性函数特点：反映了几何上相似形的特征，对于坐标系的旋转、放大和缩小等变化是不变的。当特征的取值仅为(0,1)两个值时的特例量纲对分类的影响（图例）5.2 模式相似性的测度和聚类准则5.2.2 聚类准则有了模式的相似性测度，还需要一种基于数值的聚类准则，能将相似的模式样本分在同一类，相异的模式样本分在不同的类。试探方法聚类准则函数法5.2 模式相似性的测度和聚类准则5.2.2 聚类准则试探方法凭直观感觉，针对实际问题定义一种相似性测度的阈值，然后按最近邻规则指定某些模式样本属于某一个聚类类别。例如对欧氏距离，它反映了样本间的近邻性，但将一个样本分到不同类别中的哪一个时，还必须规定一个距离测度的阈值作为聚类的判别准则。5.2 模式相似性的测度和聚类准则5.2.2 聚类准则聚类准则函数法依据：由于聚类是将样本进行分类以使类别间可分离性为最大，因此聚类准则应是反映类别间相似性或分离性的函数；由于类别是由一个个样本组成的，因此一般来说类别的可分离性和样本的可分离性是直接相关的；可以定义聚类准则函数为模式样本集x和模式类别Sj, j=1,2,c的函数，从而使聚类分析转化为寻找准则函数极值的最优化问题。5.2 模式相似性的测度和聚类准则5.2.2 聚类准则聚类准则函数法一种聚类准则函数J的定义J代表了属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。对于不同的聚类形式，J值是不同的。目的：求取使J值达到最小的聚类形式。5.3 基于试探的聚类搜索算法5.3.1 按最近邻规则的简单试探法算法讨论这种方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可获得较好的聚类结果。5.3 基于试探的聚类搜索算法5.3.1 按最近邻规则的简单试探法讨论（续）在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，因此这种方法在很大程度上依赖于以下因素：第一个聚类中心的位置待分类模式样本的排列次序距离阈值T的大小样本分布的几何性质5.3 基于试探的聚类搜索算法2.3.1 按最近邻规则的简单试探法讨论（续）距离阈值T对聚类结果的影响5.3 基于试探的聚类搜索算法5.3.2 最大最小距离算法基本思想：以试探类间欧氏距离为最大作为预选出聚类中心的条件。5.3 基于试探的聚类搜索算法2.3.2 最大最小距离算法算法（实例）5.4 系统聚类法基本思想将模式样本按距离准则逐步分类，类别由多到少，直到获得合适的分类要求为止。算法系统聚类也称为Hierarchical ClusteringMany times, clusters are not disjoint, but a cluster may have subclusters, in turn having sub-subclusters, etc.Consider a sequence of partitions of the n samples into c clustersThe first is a partition into n cluster, each one containing exactly one sampleThe second is a partition into n-1 clusters, the third into n-2, and so on, until the n-th in which there is only one cluster containing all of the samplesAt the level k in the sequence, c = n-k+1.Hierarchical clustering tree representation called dendrogramAnother representation is based on set, e.g., on the Venn diagramsAgglomerative hierarchical clusteringThe procedure terminates when the specified number of cluster has been obtained, and returns the cluster as sets of points, rather than the mean or a representative vector for each cluster距离准则函数进行聚类合并的一个关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，采用不同的距离函数会得到不同的计算结果。主要的距离计算准则：最短距离法最长距离法中间距离法重心法类平均距离法距离准则函数距离准则函数To find the nearest clusters, one can use which behave quite similar of the clusters are hyperspherical and well separated.最短距离法(Nearest-neighbor algorithm)When dmin is used, the algorithm is called the neirest neighbor algorithmIf data points are thought as nodes of a graph with edges forming a path between the nodes in the same subset Di, the merging of Di and Dj corresponds to adding an edge between the neirest pair of node in Di and DjThe resulting graph has any closed loop and it is a tree, if all subsets are linked we have a spanning tree 最长距离法( The farthest neighbor algorithm)When dmax is used, the algorithm is called the farthest neighbor algorithmIf it is terminated when the distance between nearest clusters exceeds an arbitrary threshold, it is called complete-linkage algorithm举例设有6个五维模式样本如下，按最小距离准则进行聚类分析：x1: 0, 3, 1, 2, 0x2: 1, 3, 0, 1, 0x3: 3, 3, 0, 0, 1x4: 1, 1, 0, 2, 0x5: 3, 2, 1, 2, 1x6: 4, 1, 1, 1, 05.4 系统聚类法举例系统聚类的树状表示作业画出给定迭代次数为n的系统聚类法的算法流程框图对如下5个6维模式样本，用最小聚类准则进行系统聚类分析：x1: 0, 1, 3, 1, 3, 4x2: 3, 3, 3, 1, 2, 1x3: 1, 0, 0, 0, 1, 1x4: 2, 1, 0, 2, 2, 1x5: 0, 0, 1, 0, 1, 05.4 系统聚类法练习对如下6个五维模式样本，按最大距离准则进行聚类分析（直到分成三个类别为止）：x1: 0, 3, 1, 2, 0x2: 1, 3, 0, 1, 0x3: 3, 3, 0, 0, 1x4: 1, 1, 0, 2, 0x5: 3, 2, 1, 2, 1x6: 4, 1, 1, 1, 05.5 动态聚类法基本思想首先选择若干个样本点作为聚类中心，再按某种聚类准则（通常采用最小距离准则）使样本点向各中心聚集，从而得到初始聚类；然后判断初始分类是否合理，若不合理，则修改分类；如此反复进行修改聚类的迭代算法，直至合理为止。5.5.1 K-均值算法5.5.2 ISODATA算法（迭代自组织数据分析算法）5.5.1 K-均值算法思想：基于使聚类性能指标最小化，所用的聚类准则函数是聚类集中每一个样本点到该类中心的距离平方之和，并使其最小化。算法If n is the known number of patterns and c the desired number of clusters, the k-means algorithm is:Begininitialize n, c, 1, 2, , c(randomly selected)do classify n samples according to nearest i recompute iuntil no change in ireturn 1, 2, , cEndExercise 2 p.594 (Textbook)5.5.1 K-均值算法举例对如图模式样本用K-均值算法进行分类5.5.1 K-均值算法讨论K-均值算法的结果受如下选择的影响：所选聚类的数目聚类中心的初始分布模式样本的几何性质读入次序在实际应用中，需要试探不同的K值和选择不同的聚类中心的起始值。如果模式样本可以形成若干个相距较远的孤立的区域分布，一般都能得到较好的收敛效果。K-均值算法比较适合于分类数目已知的情况。5.5.1 K-均值算法作业/练习 （选k=2,z1(1)=x1,z2(1)=x10,用K-均值算法进行聚类分析）计算机编程编写K-均值聚类算法程序，对下图所示数据进行聚类分析(选k=2)：5.5.2 ISODATA算法与K-均值算法的比较K-均值算法通常适合于分类数目已知的聚类，而ISODATA算法则更加灵活；从算法角度看， ISODATA算法与K-均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的；ISODATA算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。5.5.2 ISODATA算法基本步骤和思路（1） 选择某些初始值。可选不同的指标，也可在迭代过程中人为修改，以将N个模式样本按指标分配到各个聚类中心中去。（2） 计算各类中诸样本的距离指标函数。（3）（5）按给定的要求，将前一次获得的聚类集进行分裂和合并处理（4）为分裂处理，（5）为合并处理），从而获得新的聚类中心。（6） 重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。5.5.2 ISODATA算法算法举例对如图模式样本用ISODATA算法进行分类作业试用ISODATA算法对如下模式分布进行聚类分析：x1(0, 0), x2(3,8), x3(2,2), x4(1,1), x5(5,3), x6(4,8), x7(6,3), x8(5,4), x9(6,4), x10(7,5)