第14章 聚类方法.pptx

,第十四章聚类方法,相似度或距离,假设有n个样本，每个样本由m个属性的特征向量组成，样本合集可以用矩阵X表示聚类的核心概念是相似度（similarity)或距离（distance)，有多种相似度或距离定义。因为相似度直接影响聚类的结果，所以其选择是聚类的根本问题。,闵可夫斯基距离,闵可夫斯基距离越大相似度越小，距离越小相似度越大。给定样本集合X,X是m维实数向量空间Rm中点的集合，其中样本xi与样本xj 的闵可夫斯基距离（Minkowski distance）定义为,闵可夫斯基距离,当p=2时称为欧氏距离（Euclidean distance)当p=1时称为曼哈顿距离（Manhattan distance)当p=时称为切比雪夫距离（Chebyshev distance）,马哈拉诺比斯距离,马哈拉诺比斯距离（Mahalanobis distance)，简称马氏距离，也是另一种常用的相似度，考虑各个分量（特征）之间的相关性并与各个分量的尺度无关。马哈拉诺比斯距离越大相似度越小，距离越小相似度越大。给定一个样本集合X,X=，其协方差矩阵记作S。样本xi 与样本xj之间的马哈拉诺比斯距离dij定义为,相关系数,样本之间的相似度也可以用相关系数（correlation coefficient）来表示。相关系数的绝对值越接近于1，表示样本越相似越接近于0，表示样本越不相似。样本xi与样本xj之间的相关系数定义为,夹角余弦,样本之间的相似度也可以用夹角余弦（cosine）来表示。夹角余弦越接近于1，表示样本越相似越接近于0，表示样本越不相似。样本xi与样本xj之间的夹角余弦定义为,相似度,用距离度量相似度时，距离越小样本越相似用相关系数时，相关系数越大样本越相似注意不同相似度度量得到的结果并不一定一致。从右图可以看出，如果从距离的角度看，A和B比A和C更相似但从相关系数的角度看，A和C比A和B更相似。,类或簇,通过聚类得到的类或簇，本质是样本的子集。如果一个聚类方法假定一个样本只能属于一个类，或类的交集为空集，那么该方法称为硬聚类（hard clustering）方法。如果一个样本可以属于多个类，或类的交集不为空集，那么该方法称为软聚类（soft clustering）方法。,类或簇,用G表示类或簇（cluster)，用xi,xj表示类中的样本，用nG表示G中样本的个数，用dij表示样本xi与样本xj之间的距离。类或簇有多种定义，下面给出几个常见的定义。,类或簇,类或簇,类或簇,类或簇,类或簇,类的特征可以通过不同角度来刻画，常用的特征有下面三种：,类或簇,类的特征可以通过不同角度来刻画，常用的特征有下面三种：,类或簇,类的特征可以通过不同角度来刻画，常用的特征有下面三种：,类与类之间的距离,下面考虑类Gp与类Gq之间的距离D(p,q)，也称为连接（linkage)。类与类之间的距离也有多种定义。设类Gp包含 np个样本，Gq包含 nq个样本，分别用 和 表示Gp和Gq的均值，即类的中心。,类与类之间的距离,最短距离或单连接（single linkage)定义类Gp的样本与Gq的样本之间的最短距离为两类之间的距离,类与类之间的距离,最长距离或完全连接（complete linkage)定义类Gp的样本与Gq的样本之间的最长距离为两类之间的距离,类与类之间的距离,中心距离定义类Gp与Gq的中心 与 之间的距离为两类之间的距离,类与类之间的距离,平均距离 定义类Gp与Gq任意两个样本之间距离的平均值为两类之间的距离,层次聚类,层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。层次聚类又有聚合（agglomerative）或自下而上（bottom-up）聚类、分裂（divisive）或自上而下（top-down）聚类两种方法。因为每个样本只属于一个类，所以层次聚类属于硬聚类,层次聚类,聚合聚类开始将每个样本各自分到一个类之后将相距最近的两类合并，建立一个新的类重复此操作直到满足停止条件得到层次化的类别分裂聚类开始将所有样本分到一个类之后将已有类中相距最远的样本分到两个新的类重复此操作直到满足停止条件得到层次化的类别,聚合聚类的具体过程,对于给定的样本集合，开始将每个样本分到一个类然后按照一定规则，例如类间距离最小，将最满足规则条件的两个类进行合并如此反复进行，每次减少一个类，直到满足停止条件，如所有样本聚为一类。,聚合聚类,聚合聚类需要预先确定下面三个要素距离或相似度闵可夫斯基距离马哈拉诺比斯距离相关系数夹角余弦合并规则类间距离最小类间距离可以是最短距离、最长距离、中心距离、平均距离 停止条件停止条件可以是类的个数达到闭值（极端情况类的个数是1)类的直径超过阂值,聚合聚类算法,例,给定5个样本的集合，样本之间的欧氏距离由如下矩阵D表示 其中dij表示第i个样本与第j个样本之间的欧氏距离。显然D为对称矩阵。应用聚合层次聚类法对这5个样本进行聚类。,例,（1）首先用5个样本构建5个类，这样，样本之间的距离也就变成类之间的距离，所以5个类之间的距离矩阵亦为D（2）由矩阵D可以看出，为最小，所以把G3和G5合并为一 个新类，记作,例,（3）计算G6与G1,G2,G4之间的最短距离，有又注意到其余两类之间的距离是显然，D61=2最小，所以将G1与G6合并成一个新类，记作,例,（4）计算G7与G2,G4之间的最短距离，又注意到显然，其中D24=4最小，所以将G2与G4合并成一个新类，记作,例,（5）将G7与G8合并成一个新类，记作即将全部样本聚成1类，聚类终止,k均值聚类,k均值聚类是基于样本集合划分的聚类算法。k均值聚类将样本集合划分为k个子集，构成k个类，将n个样本分到k个类中，每个样本到其所属类的中心的距离最小。每个样本只能属于一个类，所以k均值聚类是硬聚类。,模型,给定n个样本的集合每个样本由一个特征向量表示，特征向量的维数是m。k均值聚类的目标是将n个样本分到k个不同的类或簇中，这里假设kn。k个类G1,G2,Gk形成对样本集合X的划分，其中用C表示划分，一个划分对应着一个聚类结果。,模型,划分C是一个多对一的函数k均值聚类的模型是一个从样本到类的函数。划分或者聚类可以用函数表示，其中样本用一个整数 表示，类用一个整数 表示,策略,k均值聚类归结为样本集合X的划分，或者从样本到类的函数的选择问题。k均值聚类的策略是通过损失函数的最小化选取最优的划分或函数C*,策略,首先，采用欧氏距离平方（squared Euclidean distance）作为样本之间的距离 d(xi,xj),策略,然后，定义样本与其所属类的中心之间的距离的总和为损失函数，即 是第l个类的均值或中心，是指示函数，取值1或0函数W(C也称为能量，表示相同类中的样 本相似的程度。,策略,k均值聚类就是求解最优化问题：相似的样本被聚到同类时，损失函数值最小，这个目标函数的最优化能达到聚类的目的。,策略,但是，这是一个组合优化问题，n个样本分到k类，所有可能分法的数目是：事实上，k均值聚类的最优解求解问题是NP困难问题。现实中采用迭代的方法求解。,算法,k均值聚类的算法是一个迭代的过程，每次迭代包括两个步骤。首先选择k个类的中心，将样本逐个指派到与其最近的中心的类中，得到一个聚类结果然后更新每个类的样本的均值，作为类的新的中心重复以上步骤，直到收敛为止。,算法,首先，对于给定的中心值（m1,m2,mk)，求一个划分C，使得目标函数极小化：就是说在类中心确定的情况下，将每个样本分到一个类中，使样本和其所属类的中心之间的距离总和最小。求解结果，将每个样本指派到与其最近的中心ml的类Gl中。,算法,然后，对给定的划分C，再求各个类的中心（m1,m2,mk)，使得目标函数极小化：就是说在划分确定的情况下，使样本和其所属类的中心之间的距离总和最小求解结果，对于每个包含nl个样本的类Gl，更新其均值ml重复以上两个步骤，直到划分不再改变，得到聚类结果,k均值聚类算法,例,给定含有5个样本的集合试用k均值聚类算法将样本聚到2个类中。,例,例,算法特性,总体特点基于划分的聚类方法类别数k事先指定以欧氏距离平方表示样本之间的距离，以中心或样本的均值表示类别以样本和其所属类的中心之间的距离的总和为最优化的目标函数得到的类别是平坦的、非层次化的算法是迭代算法，不能保证得到全局最优。,算法特性,收敛性k均值聚类属于启发式方法，不能保证收敛到全局最优，初始中心的选择会直接影响聚类结果。注意，类中心在聚类的过程中会发生移动，但是往往不会移动太大，因为在每一步，样本被分到与其最近的中心的类中。,算法特性,初始类的选择选择不同的初始中心，会得到不同的聚类结果。初始中心的选择，比如可以用层次聚类对样本进行聚类，得到k个类时停止。然后从每个类中选取一个与中心距离最近的点。,算法特性,类别数k的选择k均值聚类中的类别数k值需要预先指定，而在实际应用中最优的k值是不知道的。尝试用不同的k值聚类，检验得到聚类结果的质量，推测最优的k值。聚类结果的质量可以用类的平均直径来衡量。一般地，类别数变小时，平均直径会增加类别数变大超过某个值以后，平均直径会不变，而这个值正是最优的k值。实验时，可以采用二分查找，快速找到最优的k值。,算法特性,