Clustering – Partitioning Methods

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

定义

Partitioning method

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

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

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

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

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

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

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

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

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

数学的定义如下：

Given a set $D$$D$, a partitioning $\mathcal{C}=\{C_1,...,C_k\}$$\mathcal{C}=\{C_1,...,C_k\}$ of $D$$D$ fulfills:

• $C_i\subseteq D$$C_i\subseteq D$ for all $1\le i\le k$$1\leq i \leq k$
• $C_i\cap C_j=\mathrm{\varnothing }\iff i\ne j$$C_i\cap C_j = \empty \Leftrightarrow i\neq j$
• $\bigcup C_i=D$$\bigcup C_i=D$

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

形心 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) $\mathbf{\text{p}}=(p_1,...,p_d)$$\textbf{p}=(p_1,...,p_d)$ 是在一个$d$$d$维向量空间的点。

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

  $$\begin{array}{}\text{(1)}& SSE(C_j)=\sum _{\mathbf{\text{p}}\in C_j}||\mathbf{\text{p}}-{\mu }_{C_j}|{|}_2^2\end{array}$$

  其中$C_j$$C_j$表示一个簇,${\mu }_{C_j}$$\mu_{C_j}$表示簇$C_j$$C_j$的平均值。

• 对于整个聚类$\mathcal{C}$$\mathcal{C}$的紧凑程度:

  $$\begin{array}{}\text{(2)}& SSE(\mathcal{C})=\sum _{C_j\in \mathcal{C}}SSE(C_j)=\sum _{\mathbf{\text{p}}\in D}||\mathbf{\text{p}}-{\mu }_{C_j}|{|}_2^2\end{array}$$

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

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

  $$\begin{array}{}\text{(3)}& E=\sum _{i=1}^k\sum _{\mathbf{\text{p}}\in C_i}dist(\mathbf{\text{p}},{\mathbf{c}}_{\mathbf{i}}{)}^2\end{array}$$

  其中$dist(p,c_i)$$dist(p,c_i)$函数表示点$\mathbf{p}$$\mathbf{p}$和${\mathbf{c}}_{\mathbf{i}}$$\mathbf{c_i}$之间的欧式距离,这两个点都是多维的。这里(2)式和(3)式的意思完全一致

• 最佳划分: $\arg \underset{\mathcal{C}}{min}SSE(\mathcal{C})$$\arg\min_{\mathcal{C}} SSE(\mathcal{C})$ 使得整体SSE最小的聚类。

算法

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

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

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

具体过程如下：

输入：

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

初始化：

1. 挑选k个随机代表对象$p_1,p_2,...p_k$$p_1,p_2,...p_k$

重复：

1. 把$D$$D$中每个对象分配到离之最近的代表对象$p_i$$p_i$中,$i\in 1,...,k$$i\in1,...,k$。
2. 为每个簇重新计算形心，并把每个形心作为新的代表对象

直到：

1. 代表对象不再改变

分析

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

优势:

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

局限性在于：

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

k-Median

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

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

与$SSE(\mathcal{C})$$SSE(\mathcal{C})$类似，这里我们可以定义一个绝对误差标准(absolute-error criterion):

其中${\mathbf{o}}_{\mathbf{i}}$$\mathbf{o_i}$是选择的代表对象。k-median算法就是要最小化$AEC(\mathcal{C})$$AEC(\mathcal{C})$的值。

当k=1时，找中心点的时间复杂度是$O(n^2)$$O(n^2)$，如果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$$SSE$或者是$AEC$$AEC$肯定是不行的，因为随着k的增加，这两个值必然会减小。

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

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

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

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

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

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

Silhouette Coefficient定义如下:

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

通过silhouette coefficient, 我们定义一个簇$C_i$$C_i$的silhouette是：

一个聚类$\mathcal{C}=(C_1,...,C_k)$$\mathcal{C}={(C_1,...,C_k)}$的silhouette是

$D$$D$表示整个数据集

Evaluating

对于一个簇来说，

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

对于一个聚类来说，

如果$0.7<s(\mathcal{C})\le 1.0$$0.7<s(\mathcal{C})\leq 1.0$，则是一个好聚类。 如果$0.5<s(\mathcal{C})\le 0.7$$0.5<s(\mathcal{C})\leq 0.7$，则是一个中聚类（不好不坏。 如果$0.25<s(\mathcal{C})\le 0.5$$0.25<s(\mathcal{C})\leq 0.5$，则是一个坏聚类。 如果$s\mathcal{(}C)\le 0.25$$s\mathcal(C)\leq 0.25$，则就没有一个聚类结构。

Reference

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