. 第二章 聚类分析2.1 聚类分析的相关概念定义 对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。模式相似/分类的依据 把整个模式样本集的特征向量看成是分布在特征空间中的一些点，点与点之间的距离即可作为模式相似性的测量依据。聚类分析是按不同对象之间的差异，根据距离函数的规律（大小）进行模式分类的。聚类分析的有效性 聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。若向量点的分布是一群一群的，同一群样本密集（距离很近），不同群样本距离很远，则很容易聚类；若样本集的向量分布聚成一团，不同群的样本混在一起，则很难分类；对具体对象做聚类分析的关键是选取合适的特征。特征选取得好，向量分布容易区分，选取得不好，向量分布很难分开。两类模式分类的实例：一摊黑白围棋子 选颜色作为特征进行分类，用“1”代表白，“0”代表黑，则很容易分类；选大小作为特征进行分类，则白子和黑子的特征相同，不能分类（把白子和黑子分开）。特征选择的维数在特征选择中往往会选择一些多余的特征，它增加了维数，从而增加了聚类分析的复杂度，但对模式分类却没有提供多少有用的信息。在这种情况下，需要去掉相关程度过高的特征（进行降维处理）。降维方法设有N个样本，它们的特征维数是n，则有n*n维的相关矩阵R = rij nxn 其中，rij是第i维与第j维特征之间的相关系数： 这里：ii和jj分别是第i个和第j个分量的标准差，ij是第i个和第j个分量的协方差。分析：（1）根据相关系数的性质：（利用柯西不等式证明）（2）rij=0：表示两个分量完全不相关（3）rij=1：表示两个分量完全相关结论：若rij-1，则表明第i维特征与第j维特征所反映的特征规律接近，因此可以略去其中的一个特征，或将它们合并为一个特征，从而使维数降低一维。模式对象特征测量的数字化计算机只能处理离散的数值，因此根据识别对象的不同，要进行不同的数据化处理。连续量的量化：用连续量来度量的特性，如长度、重量、面积等等，仅需取其量化值；量级的数量化：度量时不需要详尽的数值，而是相应地划分成一些有次序的量化等级的值。l 病人的病程 0 代表病程 = 1个月 1 代表1个月 病程 = 6个月2 代表6个月 病程 12个月名义尺度：指定性的指标，即特征度量时没有数量关系，也没有明显的次序关系，如黑色和白色的关系，男性和女性的关系等，都可将它们分别用“0”和“1”来表示。超过2个状态时，可用多个数值表示。2.2 模式相似性的测度和聚类准则2.2.1 相似性测度目的：为了能将模式集划分成不同的类别，必须定义一种相似性的测度，来度量同一类样本间的类似性和不属于同一类样本间的差异性。欧氏距离设x和z为两个模式样本，其欧氏距离定义为：D = | x - z | 例：x = (x1, x2)，z = (z1, z2)，则 显然，模式x和z之间的距离越小，它们越相似。欧氏距离的概念和习惯上距离的概念是一致的。马氏距离设x是模式向量，m是均值向量，C为模式总体的协方差矩阵，则马氏距离的表达式： 特点：排除了模式样本之间的相关性问题：协方差矩阵在实际应用中难以计算。一般化的明氏距离模式样本向量xi和xj之间的明氏距离表示为：其中xik和xjk分别表示xi和xj的第k各分量。显然，当m=2时，明氏距离即为欧氏距离。特例：当m=1时，亦称为街坊距离。角度相似性函数表达式：，它表示模式向量x和z之间夹角的余弦，也称为x的单位向量与z的单位向量之间的点积。特点：反映了几何上相似形的特征，对于坐标系的旋转、放大和缩小等变化是不变的。当特征的取值仅为(0,1)两个值时的特例特例：当特征的取值仅为(0, 1)两个值时，夹角余弦度量具有特别的含义，即当模式的第i个分量为1时，认为该模式具有第i个特征；当模式的第i个分量为0时，认为该模式无此特征。这时，xTz的值就等于x和z这两个向量共同具有的特征数目。同时，= x中具有的特征数目和z中具有的特征数目的几何平均因此，在特征取值为0和1的二值情况下，S(x, z)等于x和z中具有的共同特征数目的相似性测度。2.2.2 聚类准则有了模式的相似性测度，还需要一种基于数值的聚类准则，能将相似的模式样本分在同一类，相异的模式样本分在不同的类。试探方法凭直观感觉或经验，针对实际问题定义一种相似性测度的阈值，然后按最近邻规则指定某些模式样本属于某一个聚类类别。例如对欧氏距离，它反映了样本间的近邻性，但将一个样本分到不同类别中的哪一个时，还必须规定一个距离测度的阈值作为聚类的判别准则。聚类准则函数法依据：由于聚类是将样本进行分类以使类别间可分离性为最大，因此聚类准则应是反映类别间相似性或分离性的函数；由于类别是由一个个样本组成的，因此一般来说类别的可分离性和样本的可分离性是直接相关的；可以定义聚类准则函数为模式样本集x和模式类别Sj, j=1,2,c的函数，从而使聚类分析转化为寻找准则函数极值的最优化问题。一种聚类准则函数J的定义其中，c为聚类类别的数目，Sj为第j个类别的样本集合，为属于Sj集合的样本均值向量，Nj为Sj中的样本数目。这里，以均值向量mj为Sj中样本的代表。J代表了属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。对于不同的聚类形式，J值是不同的。目的：求取使J值达到最小的聚类形式。2.3 基于试探的聚类搜索算法2.3.1 按最近邻规则的简单试探法算法 给定N个待分类的模式样本x1, x2, , xN，要求按距离阈值T，将它们分类到聚类中心z1, z2, 。第一步：任取一样本xi作为一个聚类中心的初始值，例如令z1 = x1，计算D21 = | x2 - z1 |，若D21 T，则确定一个新的聚类中心z2 = x2，否则x2属于以z1为中心的聚类；第二步：假设已有聚类中心z1、z2，计算 D31 = | x3 - z1 |，D32 = | x3 - z2 |，若D31 T且D32 T，则得一个新的聚类中心z3 = x3，否则x3属于离z1和z2中的最近者如此重复下去，直至将N个模式样本分类完毕。讨论 这种方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可通过选取正确的阈值和起始点，以及确定样本的选取次序等获得较好的聚类结果。在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，所以这种方法在很大程度上依赖于以下因素：第一个聚类中心的位置；待分类模式样本的排列次序；距离阈值T的大小；样本分布的几何性质。2.3.2 最大最小距离算法基本思想：以试探类间欧氏距离为最大作为预选出聚类中心的条件。10个模式样本点：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)第一步：选任意一个模式样本作为第一个聚类中心，如z1 = x1；第二步：选距离z1最远的样本作为第二个聚类中心。经计算，| x6 - z1 |最大，所以z2 = x6第三步：逐个计算各模式样本xi, i = 1,2,N与 z1, z2之间的距离，即Di1 = | xi - z1 |，Di2 = | xi z2 |并选出其中的最小距离min(Di1, Di2)，i = 1,2,N第四步：在所有模式样本的最小值中选出最大距离，若该最大值达到|z1 - z2 |的一定比例以上，则相应的样本点取为第三个聚类中心z3，即若maxmin(Di1, Di2), i = 1,2,N |z1 - z2 |，则z3 = xi否则，若找不到适合要求的样本作为新的聚类中心，则找聚类中心的过程结束。这里，可用试探法取一固定分数，如1/2。在此例中，当i=7时，符合上述条件，故z3 = x7第五步： 若有z3存在，则计算maxmin(Di1, Di2, Di3), i = 1,2,N。若该值超过|z1 - z2 |的一定比例，则存在z4，否则找聚类中心的过程结束。在此例中，无z4满足条件。第六步：将模式样本xi, i = 1,2,N按最近距离分到最近的聚类中心：z1 = x1：x1, x3, x4为第一类z2 = x6：x2, x6为第二类z3 = x7：x5, x7, x8, x9, x10为第三类，最后，还可在每一类中计算个样本的均值，得到更具代表性的聚类中心。2.4 系统聚类法基本思想：将模式样本按距离准则逐步分类，类别由多到少，直到获得合适的分类要求为止。算法：第一步：设初始模式样本共有N个，每个样本自成一类，即建立N类，。计算各类之间的距离（初始时即为各样本间的距离），得到一个N*N维的距离矩阵D(0)。这里，标号(0)表示聚类开始运算前的状态。第二步：假设前一步聚类运算中已求得距离矩阵D(n)，n为逐次聚类合并的次数，则求D(n)中的最小元素。如果它是Gi(n)和Gj(n)两类之间的距离，则将Gi(n)和Gj(n)两类合并为一类，由此建立新的分类：。第三步：计算合并后新类别之间的距离，得D(n+1)。计算与其它没有发生合并的之间的距离，可采用多种不同的距离计算准则进行计算。第四步：返回第二步，重复计算及合并，直到得到满意的分类结果。（如：达到所需的聚类数目，或D(n)中的最小分量超过给定阈值D等。）距离准则函数进行聚类合并的一个关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，采用不同的距离函数会得到不同的计算结果。主要的距离计算准则：聚类准则函数1.最短距离法：设H和K是两个聚类，则两类间的最短距离定义为：其中，du,v表示H类中的样本xu和K类中的样本xv之间的距离，DH,K表示H类中的所有样本和K类中的所有样本之间的最小距离。递推运算：假若K类是由I和J两类合并而成，则2.最长距离法：设H和K是两个聚类，则两类间的最长距离定义为：其中du,v的含义与上面相同。递推运算：假若K类是由I和J两类合并而成，则3.中间距离法：设K类是由I和J两类合并而成，则H和K类之间的距离为：它介于最长距离和最短距离之间。4.重心法：假设I类中有nI个样本，J类中有nJ个样本，则I和J合并后共有nI+nJ个样本。用nI/(nI+nJ)和nJ/(nI+nJ)代替中间距离法中的系数，得到重心法的类间距离计算公式：5.类平均距离法：若采用样本间所有距离的平均距离，则有：递推运算公式：举例设有6个五维模式样本如下，按最小距离准则进行聚类分析：x1: 0, 3, 1, 2, 0；x2: 1, 3, 0, 1, 0；x3: 3, 3, 0, 0, 1；x4: 1, 1, 0, 2, 0；x5: 3, 2, 1, 2, 1；x6: 4, 1, 1, 1, 0作业1.画出给定迭代次数为n的系统聚类法的算法流程框图2.对如下5个6维模式样本，用最小聚类准则进行系统聚类分析：x1: 0, 1, 3, 1, 3, 4；x2: 3, 3, 3, 1, 2, 1；x3: 1, 0, 0, 0, 1, 1；x