Clustering – Partitioning Methods

4_1_Partitioning_Methods

划分方法是一种聚类算法,可以用来为大数据洞察数据的分布,做自动归类等作用。

定义

Partitioning method

给定一个n个对象的集合,划分方法(Partitioning method)将会构建数据的k个分区,其中每个分区表示一个簇(cluster),并且kn

也就是说,划分方法把数据划分成了k个组,并且使得每个组至少包含一个对象。最典型的例子是互斥的簇划分 (exclusive cluster separation)。在这种方法下,我们要求每个对象必须恰好属于一个组。

划分方法的一个准则是(或者判断一个划分是否是一个好的划分的标准是):同一个簇中的对象尽可能相关,不同簇的对象尽可能无关。

基于划分的聚类可能是效率低下的,因为遍历所有的项通常很慢。可以使用启发式算法来提升效率。

目前流行的启发式算法过程如下:

  • 给每个簇挑选k个代表,可以随机挑选或者用其他算法。

  • 递归地改善刚刚挑选到的簇:

    • 在当前的聚类(clustering)下,把每个对象分配到最合适的簇(cluster)中
    • 基于刚才的重新聚类,重新计算新的簇的代表。
    • 重复到不再改变

启发式算法会渐近地提高聚类的质量,进而逼近局部最优解。本小节介绍的k-mean算法就是一种启发式算法。

数学的定义如下:

Given a set D, a partitioning C={C1,...,Ck} of D fulfills:

  • CiD for all 1ik
  • CiCj=ij
  • Ci=D

i.e. each element of D is in exactly one set Ci.

形心 centroid of a cluster

形心是一个簇的中心点

形心点有多种形式可以定义,可以用一个簇的所有值的均值或者是一个簇的中心点。

K-mean

 

K-mean 算法的目的是:

 

Find a clustering such that the within-cluster variation of each cluster is small and use the centroid of a cluster as a representative.

找到一个聚类(clustering),使得每个簇的簇内变差是很小的,并且使用形心作为代表.[1] 簇内变差的定义见下文中的符号规定。

符号规定

  • 对象(objects) p=(p1,...,pd) 是在一个d维向量空间的点。

  • 平方距离和(用来衡量一个簇的紧凑程度(compactness))(sum of squared distances):

    (1)SSE(Cj)=pCj||pμCj||22

    其中Cj表示一个簇,μCj表示簇Cj的平均值。

  • 对于整个聚类C的紧凑程度:

    (2)SSE(C)=CjCSSE(Cj)=pD||pμCj||22

    也就是整个数据集D中所有点的SSE之和。

    有的书上也用簇内变差E来表示。假设聚类clustering C中一共有k个簇,那么

    (3)E=i=1kpCidist(p,ci)2

    其中dist(p,ci)函数表示点pci之间的欧式距离,这两个点都是多维的。这里(2)式和(3)式的意思完全一致

  • 最佳划分: argminCSSE(C) 使得整体SSE最小的聚类。

算法

目前已经证明,即使是数据的维度只有二维,簇的数量不固定,想要找到最佳划分使得SSE(C)值最小的问题是NP-hard的。对于维度不固定,簇的数量固定,找到最佳划分使得SSE(C)值最小的问题也是NP-hard的。

但是如果簇和数据的维度都给定,那么问题可以在O(n(dk+1)logn)的时间内求解,其中d是数据的维度,k是簇的数量,n是对象的个数。

k-mean算法则是利用贪心算法,将复杂度尽可能的降低。算法首先在数据集中随机选择k个对象,每个对象都代表一个簇的初始均值或者中心。对于剩下的对象,根据其与各个簇中心的欧式距离,将它分配到最相似的簇。接下来,k-mean算法迭代地改善SSE:对于每个簇,算法使用上次迭代分配到的该簇的对象,计算新的均值。然后用更新后的均值作为新的形心,重新分配所有对象。一直迭代到本轮形成的簇和上一轮一样。

具体过程如下:


输入:

  1. 给定k作为簇的数目
  2. 给定包含n个对象的数据集D

初始化:

  1. 挑选k个随机代表对象p1,p2,...pk

重复:

  1. D中每个对象分配到离之最近的代表对象pi中,i1,...,k
  2. 为每个簇重新计算形心,并把每个形心作为新的代表对象

直到:

  1. 代表对象不再改变

分析

k-mean算法复杂度是O(nkt),n是对象总数,k是簇数,t是迭代次数。通常情况下有k<<n,t<<n.所以对于大数据集这种算法非常有效。

优势:

  1. 算法复杂度通常情况下比较低
  2. 易于部署。

局限性在于:

  1. 必须给出簇的均值的定义。
  2. 要求用户事前给出k
  3. 对噪声和离群点敏感。因为少量的极值会对均值产生很大影响。
  4. 簇要求形状得是凸的
  5. 性能或者说是时间复杂度与初始化的关系很大。

k-Median

k-mean算法对离群点比较敏感。改进的一种想法是不让对象和均值比较,而是让对象和对象比较。

具体来说,我们为每一个簇挑选一个代表对象。然后让剩下的对象和这些代表对象比,找到与代表对象最相似的,将对象放入代表对象所对应的簇中。

SSE(C)类似,这里我们可以定义一个绝对误差标准(absolute-error criterion):

(4)AEC(C)=CjCAEC(Cj)=pD||poi||22

 

(5)E=i=1kpCjdist(p,oi)

其中oi是选择的代表对象。k-median算法就是要最小化AEC(C)的值。

当k=1时,找中心点的时间复杂度是O(n2),如果k>1,找中心点是NP-hard的。

k-median算法同样可以计算无法取均值的ordering数据。

k-median算法与k-mean类似,只是公式不同,在此不做赘述,有兴趣可以阅读这篇文章,介绍了k-mean,k-median,以及衍生出的PAM

Silhouette-Coefficient

如何挑选参数k呢?非常简单的想法是遍历k的大小,从2一直到n-1,n是数据的规模。然后我们挑选出最好的聚类所对应的k。

那么我们应该如何衡量一个好的聚类呢?单纯只是用SSE或者是AEC肯定是不行的,因为随着k的增加,这两个值必然会减小。

Silhouette-Coefficient可以评估一个聚类的质量。挑选它的原因也很简单,这个系数不会因为k的增加而单调。

Silhouette-Coefficient的想法是,聚类的质量好坏,对应于这个聚类是否将对象“恰当”得映射到了聚类里。所谓恰当,正如我们前面提到的,就是想让同一个簇内的对象尽可能相似,不同的簇的对象尽可能相异。那么我们就可以规定a(o)来表示代表对象o与簇内其他对象的相似性,用b(o)表示相异性。

有了这个想法,a(o)可以用从o到簇内其他对象的平均距离来表示:

(6)a(o)=1|C(o)|pC(o)dist(o,p)

|C(o)|表示代表对象o所对应簇C(o)的对象的数量。

b(o)可以用代表对象到其他簇的对象的最小距离的平均值来表示

(7)b(o)=minCiC(o){1|Ci|pCid(o,p)}

可以用下面的图片来表示上面的定义。

image-20230104141325989

Silhouette Coefficient定义如下:

(8)s(o)={0if a(o)=0,e.g.|Ci|=1b(o)a(o)max(a(o),b(o))else

可以看出s(o)的取值范围是[1,1]

通过silhouette coefficient, 我们定义一个簇Ci的silhouette是:

(9)s(Ci)=1|Ci|oCis(o)

一个聚类C=(C1,...,Ck)的silhouette是

(10)s(C)=1|D|oDs(o)

D表示整个数据集

Evaluating

对于一个簇来说,

如果b(o)>>a(o)s(o)1,则称这个簇的代表对象o很有代表性。 如果b(o)a(o)s(o)0,则可以说对象o在两个簇之间。 如果b(o)<<a(o)s(o)1,则可以说对象o距离另一个簇更近。

对于一个聚类来说,

如果0.7<s(C)1.0,则是一个好聚类。 如果0.5<s(C)0.7,则是一个中聚类(不好不坏。 如果0.25<s(C)0.5,则是一个坏聚类。 如果s(C)0.25,则就没有一个聚类结构。

Reference

[1] S.P. Lloyd: Least squares quantization in PCM. In IEEE Information Theory, 1982

2条评论

    1. 谢谢回复!

      这里写的也只是一些皮毛罢了。

      你的导航站也很棒啊,很开心能遇到这么多2022依然在坚持用博客的人:)

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据