现代机器学习 课件 第9章 聚类方法 .pptx

第9章聚类方法;

9.1聚类方法概述;

为了更加简单地认识聚类,我们可以将聚类过程描述为:假设样本集X={x1,x2,…,xn}中包含n个未标记的样本,其中每个样本xi=(xi1,xi2,…,xim)为一个m维的特征向量,聚类方法是为了将样本集X划分为j个不相交的类{Ck|l=1,2,…,j},同时使用λk∈{1,2,…,j}表示样本xi的类标记,使用类标记向量λ=(λ1,λ2,…,λn)表示聚类的结果。;

为了完成一个聚类任务,通常需要进行以下几个步骤:

(1)选择特征。

(2)选择近邻测度。

(3)选择聚类准则。

(4)选择聚类算法。

(5)验证结果。

(6)判定结果。;

9.2K均值聚类;

K均值聚类的策略是通过最小化损失函数来找到对样本集合最好的划分(其中划分用C来表示),每个划分对应一种聚类结果。样本之间距离的计算可以采用欧氏距离,但是为了便于计算,一般会采用欧氏距离的平方,即;;

K均值聚类最终迭代得到了k个聚类中心,赋予每个样本对应的类别。四类的K均值聚类示意图如图9.1所示。;

为了优化损失函数,K均值聚类算法采用了迭代的方式,每次的迭代包含两个步骤。

第一步,选择k个聚类的中心(c1,c2,…,ck),然后将每个样本都分类到与其最近的中心对应的类中,从而得到一个聚类的划分。也就是,首先最小化每个样本到聚类中心距离的函数,即;

第二步,通过计算得到每个类的样本均值cl,将其作为新的聚类中心,即

其中,nl代表第l类包含的样本个数。

重复以上两个步骤,直到算法收敛,从而获得最终的聚类结果。;

;

从上述过程中我们不难看出,K均值聚类存在以下三个缺点:

第一,K均值聚类的类别数量k需要人为指定。在一些实际问题中,对样本集合进行聚类划分最合适的k值往往是不可知的,所以为了找到最合适的k值,通常需要通过一个一个地检验不同k值来寻找最合适的k值,这样操作会使计算成本增加。

第二,K均值聚类初始中心的位置对最终的聚类结果影响较大。初始聚类中心选取的不同,很容易导致聚类划分结果的不同。聚类中心选取不当,很有可能得到错误的聚类划

分结果??;

第三,K均值聚类属于启发式算法,所以聚类的结果不一定会收敛到全局最优解。与上一点类似,初始中心的选取会直接影响聚类划分结果是否能收敛到全局最优解。;

9.3层次聚类;

层次聚类可以分为聚合聚类和分裂聚类两种。聚合聚类是自下而上的聚类,首先将每个样本各自分为一个类,然后将距离最近的两个类合并,得到新的类,重复这样的合并操作,直到满足终止条件,就得到了聚类结果。分裂聚类是自上而下的聚类,首先将所有样本都分为一个类,然后将所有类中距离最远的样本分到两个新的类中,重复这样的分割操作,直到满足终止条件,就得到了聚类结果。因为分裂聚类的计算效率较低,所以本节只详细介绍聚合聚类。;

聚合聚类的基本原理如下:首先将样本集合内的每个样本都分为一类;然后按照规定的条件,通常是将达到类间距离最小作为条件,将满足条件的两个类进行合并;重复上述步骤,每次只减少一个类,直到满足停止条件,例如到达规定的类别数量,即可得到聚类结果。

为了完成层次聚类,在进行聚类前,要确定以下三个条件:

(1)样本之间的相似程度;

(2)类合并的规则;

(3)聚类停止的条件。;

聚合层次聚类的算法过程描述如下:

(1)设样本集合中样本的个数为n,首先将这n个样本分为n类,也就是每一类中只包含一个样本,然后计算这n个样本两两之间的距离,通常使用欧氏距离来计算。

(2)合并类间距离最小的两个类,得到一个新的类。

(3)计算新的类与其他类之间的距离,如果满足设定的聚类类别个数,那么将聚类结果进行输出,否则返回步骤(2)。;

类似于K均值聚类算法,层次聚类也具有一些缺陷:

(1)聚合或者分裂的决定需要检查和估算大量的对象或者簇。

(2)不能撤销已做的处理,聚类之间不能交换对象。如果某一步没有很好地聚合或者分裂,可能导致低质量的聚类结果。;

9.4密度聚类;

9.4.1DBSCAN算法

对于密度聚类,首先要提到的就是DBSCAN算法。在DBSCAN算法中,密度指的是样本xi周围在数据集X={x1,x2,…,xn}中估计的样本个数,通过基于“邻域”的参数ε和Q来描述样本分布的紧密程度。对于数据集X,我们需要定义以下几个概念:

(1)ε邻域。对于样本xi∈X,它的ε邻域包含了在样本集X中与样本xi之间的距离小于等于ε的样本。

(2)核心对象。如果样本xi的ε邻域中至少包含了Q个样本,那么xi