1. 简介
聚类是针对给定的样本,依据它们特征的相似度或距离,将其归并到若干个「类」或「簇」的数据分析问题。一个类是样本的一个子集,直观上,相似的样本聚集在相同的类,不相似的样本分散在不同的类。
聚类的目的是通过得到的类或和入在来发现数据的特和点或对数据进行处理,在数据挖掘、模式识别等领域有着广泛的应用。聚类属于无监督学习,因为只是根据样本的相似度或距离将其进行归类,而类或簇事先并不知道。
常用的聚类算法有:层次聚类和 K 均值聚类。层次聚类又有聚合(自下而上)和裂(自上而下)两种方法。
聚合法 :开始将每个样本各自分到一个类,之后将相距最近的两类合并,建立一个新的类,重复此操作直到满足停止条件,得到层次化的类别。
分裂法 :开始将所有样本分到一个类,之后将已有类中相距最远的样分到到两个新的类,重复此操作直到满足停止条件,得到层次化的类别。
K K K 均值聚类是基于中心的聚类方法,通过迭代,将样本分到 K K K 个类中,使得每个样本与其所属类的中心或均值最近,最后得到 K K K 个平坦的、非层次化的类别,构成对空间的划分。
2. 基本概念
聚类的基本概念,主要包括样本之间的距离或相似度、类或簇、类与类之间的距离。
2.1 相似度或距离
聚类的对象是观测数据,或样本集合。假设有 n n n 个样本,每个样本由 m m m 个属性的特征向量组成。样本集合可以用矩阵 X X X 表示
X = [ x i j ] m × n = [ x 11 x 12 ⋯ x 1 n x 21 x 22 ⋯ x 2 n ⋮ ⋮ ⋱ ⋮ x m 1 x m 2 ⋯ x m n ] X = [x_{ij}]_{m \times n} = \left[
\begin{matrix}
x_{11} & x_{12} & \cdots & x_{1n} \\
x_{21} & x_{22} & \cdots & x_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
x_{m1} & x_{m2} & \cdots & x_{mn}
\end{matrix}
\right]
X = [ x ij ] m × n = ⎣ ⎡ x 11 x 21 ⋮ x m 1 x 12 x 22 ⋮ x m 2 ⋯ ⋯ ⋱ ⋯ x 1 n x 2 n ⋮ x mn ⎦ ⎤
矩阵 X X X 的第 j j j 列表示第 j j j 个样本,j = 1 , 2 , ⋯ , n j = 1, 2, \cdots, n j = 1 , 2 , ⋯ , n ;第 i i i 行表示第 i i i 个属性,i = 1 , 2 , ⋯ , m i = 1, 2, \cdots, m i = 1 , 2 , ⋯ , m ;矩阵元素 x i j x_{ij} x ij 表示第 j j j 个样本的第 i i i 个属性值。聚类的核心概念是相似度或距离,有多种相似度或距离的定义。由于相似度直接影响聚类的结果,所以其选择是聚类的根本问题。具体哪种相似度更合适取决于应用问题的特性。
闵可夫斯基距离 :给定样本集合 X X X ,X X X 是 m m m 维实数向量空间 R m \mathbf{R}^m R m 中点的集合,其中 x i , x j ∈ X x_i, x_j \in X x i , x j ∈ X ,x i = ( x 1 i , x 2 i , ⋯ , x m i ) ⊤ x_i = (x_{1i}, x_{2i}, \cdots, x_{mi})^\top x i = ( x 1 i , x 2 i , ⋯ , x mi ) ⊤ ,x j = ( x 1 j , x 2 j , ⋯ , x n j ) ⊤ x_j = (x_{1j}, x_{2j}, \cdots, x_{nj})^\top x j = ( x 1 j , x 2 j , ⋯ , x nj ) ⊤ ,样本 x i x_i x i 与样本 x j x_j x j 的闵可夫斯基距离定义为
d i j = ( ∑ k = 1 m ∣ x k i − x k j ∣ p ) 1 p d_{ij} = \left( \sum_{k=1}^m \lvert x_{ki} - x_{kj} \rvert^p \right)^{\frac{1}{p}}
d ij = ( k = 1 ∑ m ∣ x ki − x kj ∣ p ) p 1
其中,p ≥ 1 p \geq 1 p ≥ 1 。当 p = 2 p = 2 p = 2 时称为欧氏距离,当 p = 1 p = 1 p = 1 称为曼哈顿距离,当 p = ∞ p = \infty p = ∞ 时称为切比雪夫距离,此时即为取各个坐标数值差的绝对值的最大值:d i j = max k ∣ x k i − x k j ∣ d_{ij} = \max_k \lvert x_{ki} - x_{kj} \rvert d ij = max k ∣ x ki − x kj ∣ 。
马哈拉诺比斯距离 :给定样本集合 X X X ,X = ( x i j ) m × n X = (x_{ij})_{m \times n} X = ( x ij ) m × n ,其协方差矩阵记作 S S S 。样本 x i x_i x i 与样本 x j x_j x j 之间的马哈拉诺比斯距离 d i j d_{ij} d ij 定义为
d i j = [ ( x i − x j ) ⊤ S − 1 ( x i − x j ) ] 1 2 d_{ij} = \left[ (x_i - x_j)^\top S^{-1} (x_i - x_j) \right]^{\frac{1}{2}}
d ij = [ ( x i − x j ) ⊤ S − 1 ( x i − x j ) ] 2 1
其中,x i = ( x 1 i , x 2 i , ⋯ , x m i ) ⊤ x_i = (x_{1i}, x_{2i}, \cdots, x_{mi})^\top x i = ( x 1 i , x 2 i , ⋯ , x mi ) ⊤ ,x j = ( x 1 j , x 2 j , ⋯ , x m j ) ⊤ x_j = (x_{1j}, x_{2j}, \cdots, x_{mj})^\top x j = ( x 1 j , x 2 j , ⋯ , x mj ) ⊤ 。当 S S S 为单位矩阵时,即样本数据的各个分量互相独立且各个分量的方差为 1 1 1 时,马哈拉诺斯比距离就是闵可夫斯基距离。
马哈拉诺比斯距离简称马氏距离,其考虑各个分量之间的相关性并与各个分量的尺度无关。马氏距离越大相似度越小,距离越小相似度越大。
相关系数 :样本之间的相似度也可以用相关系数来表示,相关系数的绝对值越接近 1 1 1 ,表示样本越相似;越接近 0 0 0 ,表示样本越不相似。样本 x i x_i x i 与样本 x j x_j x j 之间的相关系数定义为
r i j = ∑ k = 1 m ( x k i − x ˉ i ) ( x k j − x ˉ j ) [ ∑ k = 1 m ( x k i − x ˉ i ) 2 ∑ k = 1 m ( x k j − x ˉ j ) 2 ] 1 2 r_{ij} = \frac{\sum_{k=1}^m (x_{ki} - \bar{x}_i)(x_{kj} - \bar{x}_j)}{\left[ \sum_{k=1}^m (x_{ki} - \bar{x}_i)^2 \sum_{k=1}^m (x_{kj} - \bar{x}_j)^2 \right]^{\frac{1}{2}}}
r ij = [ ∑ k = 1 m ( x ki − x ˉ i ) 2 ∑ k = 1 m ( x kj − x ˉ j ) 2 ] 2 1 ∑ k = 1 m ( x ki − x ˉ i ) ( x kj − x ˉ j )
其中,x ˉ i = 1 m ∑ k = 1 m x k i , x ˉ j = 1 m ∑ k = 1 m x k j \bar{x}_i = \frac{1}{m} \sum_{k=1}^m x_{ki}, \bar{x}_j = \frac{1}{m} \sum_{k=1}^m x_{kj} x ˉ i = m 1 ∑ k = 1 m x ki , x ˉ j = m 1 ∑ k = 1 m x kj 。
夹角余弦 :样本之间的相似度也可以用夹角余弦来表示,夹角余弦越接近 1 1 1 ,表示样本越相似;越接近 0 0 0 ,表示越不相似。样本 x i x_i x i 与样本 x j x_j x j 之间的夹角余弦定义为
s i j = ∑ k = 1 m x k i x k j [ ∑ k = 1 m x k i 2 ∑ k = 1 m x k j 2 ] 1 2 s_{ij} = \frac{\sum_{k=1}^m x_{ki} x_{kj}}{\left[ \sum_{k=1}^m x_{ki}^2 \sum_{k=1}^m x_{kj}^2 \right]^{\frac{1}{2}}}
s ij = [ ∑ k = 1 m x ki 2 ∑ k = 1 m x kj 2 ] 2 1 ∑ k = 1 m x ki x kj
由以上几种相似度量的定义来看,使用距离度量相似度时,距离越小样本越相似;使用相关系数度量相似度时,相关系数越大样本越相似。注意不同相似度度量得到的结果并不一定一致,因此选择合适的距离或相似度非常重要。
2.2 类或簇
通过聚类得到的类或簇,本质是样本的子集。如果一个聚类方法假定一个样本只能属于一个类,或类的交集的空集,那么该方法称为硬聚类 方法;否则,如果一个样本可以属于多个类,或类的交集不同空集,那么该方法称为软聚类 方法。一般只考虑硬聚类方法。
用 G G G 表示类或簇,用 x i , x j x_i, x_j x i , x j 表示类中的样本,用 n G n_G n G 表示 G G G 中样本的个数,用 d i j d_{ij} d ij 表示样本 x i x_i x i 与样本 x j x_j x j 之间的距离。类或簇有多种定义,常见的有以下几种:
定义一 :设 T T T 为给定的正数,若集合 G G G 中任意两个样本 x i , x j x_i, x_j x i , x j 有 d i j ≤ T d_{ij} \leq T d ij ≤ T ,则称 G G G 为一个类或簇。
定义二 :设 T T T 为给定的正数,若对集合 G G G 中任意样本 x i x_i x i ,一定存在 G G G 中的另一个样本 x j x_j x j ,使得 d i j ≤ T d_{ij} \leq T d ij ≤ T ,则称 G G G 为一个类或簇。
定义三 :设 T T T 为给定的正数,若对集合 G G G 中任意一个样本 x i x_i x i ,满足 1 n G − 1 ∑ x j ∈ G d i j ≤ T \frac{1}{n_G - 1} \sum_{x_j \in G} d_{ij} \leq T n G − 1 1 ∑ x j ∈ G d ij ≤ T ,其中 n G n_G n G 为 G G G 中样本的个数,则称 G G G 为一个类或簇。
定义四 :设 T T T 和 V V V 为给定的两个正数,如果集合 G G G 中任意两个样本 x i , x j x_i, x_j x i , x j 的距离 d i j d_{ij} d ij 满足
1 n G ( n G − 1 ) ∑ x i ∈ G ∑ x j ∈ G d i j ≤ T d i j ≤ V \frac{1}{n_G(n_G - 1)} \sum_{x_i \in G} \sum_{x_j \in G} d_{ij} \leq T \\
d_{ij} \leq V
n G ( n G − 1 ) 1 x i ∈ G ∑ x j ∈ G ∑ d ij ≤ T d ij ≤ V
则称 G G G 为一个类或簇。
以下四个定义,第一个定义最常用,且可以推出其他三个定义。
类的特征可以通过不同角度来刻画,常用的特征有下面三种:
类的均值 :又称类的中心,记为 x ˉ G \bar{x}_G x ˉ G :
x ˉ G = 1 n G ∑ i = 1 n G x i \bar{x}_G = \frac{1}{n_G} \sum_{i=1}^{n_G} x_i
x ˉ G = n G 1 i = 1 ∑ n G x i
式中 n G n_G n G 是类 G G G 的样本个数。
类的直径 :类的直径是类中任意两个样本之间的最大距离,记为 D G D_G D G :
D G = max x i , x j ∈ G d i j D_G = \max_{x_i, x_j \in G} d_{ij}
D G = x i , x j ∈ G max d ij
类的样本散布矩阵 :类的样本散布矩阵 A G A_G A G 定义为
A G = ∑ i = 1 n G ( x i − x ˉ G ) ( x i − x ˉ G ) ⊤ A_G = \sum_{i=1}^{n_G} (x_i - \bar{x}_G) (x_i - \bar{x}_G)^\top
A G = i = 1 ∑ n G ( x i − x ˉ G ) ( x i − x ˉ G ) ⊤
类的样本协方差矩阵 :类的样本协方差矩阵 S G S_G S G 定义为
S G = 1 m − 1 A G = 1 m − 1 ∑ i = 1 n G ( x i − x ˉ G ) ( x i − x ˉ G ) ⊤ S_G = \frac{1}{m-1} A_G = \frac{1}{m-1} \sum_{i=1}^{n_G} (x_i - \bar{x}_G)(x_i - \bar{x}_G)^\top
S G = m − 1 1 A G = m − 1 1 i = 1 ∑ n G ( x i − x ˉ G ) ( x i − x ˉ G ) ⊤
其中,m m m 为样本的维数,也即样本属性的个数。
2.3 类与类之间的距离
下面考虑类 G p G_p G p 与类 G q G_q G q 之间的距离 D ( p , q ) D(p, q) D ( p , q ) ,也称为连接 。类与类之间的距离也有多种定义。设类 G p G_p G p 包含 n p n_p n p 个样本,G q G_q G q 包含 n q n_q n q 个样本,分别用 x ˉ p \bar{x}_p x ˉ p 和 x ˉ q \bar{x}_q x ˉ q 表示 G p G_p G p 和 G p G_p G p 的均值,即类的中心。
最短距离 :也称单连接 ,定义类 G p G_p G p 的样本与 G q G_q G q 的样本之间的最短距离为两类之间的距离:
D p q = min { d i j ∣ x i ∈ G p , x j ∈ G q } D_{pq} = \min\{ d_{ij} | x_i \in G_p, x_j \in G_q \}
D pq = min { d ij ∣ x i ∈ G p , x j ∈ G q }
最长距离 :也称完全连接 ,定义类 G p G_p G p 的样本与 G q G_q G q 的样本之间的最长距离为两类之间的距离:
D p q = max { d i j ∣ x i ∈ G p , x j ∈ G q } D_{pq} = \max\{ d_{ij} | x_i \in G_p, x_j \in G_q \}
D pq = max { d ij ∣ x i ∈ G p , x j ∈ G q }
中心距离 :定义类 G p G_p G p 与类 G q G_q G q 的中心 x ˉ p \bar{x}_p x ˉ p 与 x ˉ q \bar{x}_q x ˉ q 之间的距离为两类之间的距离:
D p q = d x ˉ p x ˉ q D_{pq} = d_{\bar{x}_p \bar{x}_q}
D pq = d x ˉ p x ˉ q
平均距离 :定义类 G p G_p G p 与类 G q G_q G q 任意两个样本之间距离的平均值为两类之间的距离:
D p q = 1 n p n q ∑ x i ∈ G p ∑ x j ∈ G q d i j D_{pq} = \frac{1}{n_p n_q} \sum_{x_i \in G_p} \sum_{x_j \in G_q} d_{ij}
D pq = n p n q 1 x i ∈ G p ∑ x j ∈ G q ∑ d ij
3. 层次聚类
层次聚类假设类别之间存在层次结构,将样本聚类到层次化的类中。层次聚类又有聚合或自下而上聚类 、分裂或自上而下聚类 两种方法。由于每个样本只属于一个类,所以层次聚类属于硬聚类。
以聚合聚类为例,聚合聚类的具体过程如下:对于给定的样本集合,开始将每个样本分到一个类;然后按照一定规则,例如类间距离最小,将最满足规则条件的两个类进行合并;如此反复进行,每次减少一个类,直到满足停止条件。由此可知,聚合聚类需要预先确定下面三个要素:
根据这些要素的不同组合,就可以构成不同的聚类方法。距离或相似度可以是闵可夫斯基距离、马哈拉诺比斯距离、相关系数、夹角余弦。合并规则一般是类间距离最小,类间距离可以是最短距离、最长距离、中心距离、平均距离。停止条件可以是类的个类达到某个阈值、类的直径超过阈值。
4. K 均值聚类
K K K 均值聚类是基于样本集合划分的聚类算法。K K K 均值聚类将样本集合划分为 K K K 个子集,构成 K K K 个类,将 n n n 个样本分到 K K K 个类中,每个样本到其所属类的中心的距离最小。每个样本只能属于一个类,所以 K K K 均值聚类是硬聚类。
4.1 模型
给定 n n n 个样本的集合 X = { x 1 , x 2 , ⋯ , x n } X = \{x_1, x_2, \cdots, x_n\} X = { x 1 , x 2 , ⋯ , x n } ,每个样本由一个特征向量表示,特征向量的维数是 m m m 。K K K 均值聚类的目标是将 n n n 个样本分到 K 个不同的类或簇中,这里假设 K < n K < n K < n 。K K K 个类 G 1 , G 2 , ⋯ , G K G_1, G_2, \cdots, G_K G 1 , G 2 , ⋯ , G K 形成对样本集合 X X X 的划分,其中
G i ∩ G j = ∅ , ⋃ i = 1 k G i = X G_i \cap G_j = \varnothing, \bigcup_{i=1}^k G_i = X
G i ∩ G j = ∅ , i = 1 ⋃ k G i = X
用 C C C 表示划分,一个划分对应着一个聚类结果。划分 C C C 是一个多对一的函数,如果把每个样本用一个整数 i ∈ { 1 , 2 , ⋯ , n } i \in \{1, 2, \cdots, n\} i ∈ { 1 , 2 , ⋯ , n } 表示,每个类也用一个整数 l ∈ { 1 , 2 , ⋯ , K } l \in \{1, 2, \cdots, K\} l ∈ { 1 , 2 , ⋯ , K } 表示,那么划分或者聚类可以用函数 l = C ( i ) l = C(i) l = C ( i ) 表示,其中 i ∈ { 1 , 2 , ⋯ , n } , l ∈ { 1 , 2 , ⋯ , K } i \in \{1, 2, \cdots, n\}, l \in \{1, 2, \cdots, K\} i ∈ { 1 , 2 , ⋯ , n } , l ∈ { 1 , 2 , ⋯ , K } 。故 K K K 均值聚类的模型是一个从样本到类的函数。
4.2 策略
K K K 均值聚类归结为样本集合 X X X 的划分,或者从样本到类的函数的选择问题。K K K 均值聚类的策略是通过损失函数的最小化选取最优的划分或函数 C ∗ C^{*} C ∗ 。
首先,采用欧氏距离平方作为样本之间的距离 d ( x i , x j ) d(x_i, x_j) d ( x i , x j ) ,然后定样本与其所属类的中心之间的距离的总和为损失函数,即
W ( C ) = ∑ l = 1 K ∑ C ( i ) = l ∥ x i − x ˉ l ∥ 2 W(C) = \sum_{l=1}^K \sum_{C(i) = l} \lVert x_i - \bar{x}_l \rVert^2
W ( C ) = l = 1 ∑ K C ( i ) = l ∑ ∥ x i − x ˉ l ∥ 2
式中 x ˉ l = ( x ˉ 1 l , x ˉ 2 l , ⋯ , x ˉ m l ) ⊤ \bar{x}_l = (\bar{x}_{1l}, \bar{x}_{2l}, \cdots, \bar{x}_{ml})^\top x ˉ l = ( x ˉ 1 l , x ˉ 2 l , ⋯ , x ˉ m l ) ⊤ 是第 l l l 个类的均值或中心,n l = ∑ i = 1 n I [ C ( i ) = l ] n_l = \sum_{i=1}^n I[C(i) = l] n l = ∑ i = 1 n I [ C ( i ) = l ] ,I [ C ( i ) = l ] I[C(i) = l] I [ C ( i ) = l ] 是指示函数,取值为 1 1 1 或 0 0 0 。函数 W ( C ) W(C) W ( C ) 也称为能量,表示相同类中的样本相似的程度。
K K K 均值聚类就是求解最优化问题:
C ∗ = arg min C W ( C ) = arg min C ∑ l = 1 K ∑ C ( i ) = l ∥ x i − x ˉ l ∥ 2 \begin{aligned}
C^* & = \arg\min_C W(C) \\
& = \arg\min_C \sum_{l=1}^K \sum_{C(i)=l} \lVert x_i - \bar{x}_l \rVert^2
\end{aligned}
C ∗ = arg C min W ( C ) = arg C min l = 1 ∑ K C ( i ) = l ∑ ∥ x i − x ˉ l ∥ 2
相似的样本被聚到同类时,损失函数值最小,这个目标函数的最优化能达到聚类的目的。但这是一个 NP 困难的组合优化问题,现实中采用迭代的方法求解。
4.3 算法
K K K 均值聚类的算法是一个迭代的过程,每次迭代包括两个步骤:
首先选择 K K K 个类的中心,将样本逐个指派到与其最近的中心的类中,得到一个聚类结果;
然后更新每个类的样本的均值,作为类的新的中心。
重复以上步骤,直到收敛为止。具体过程为:
首先,对于给定的中心值 ( m 1 , m 2 , ⋯ , m k ) (m_1, m_2, \cdots, m_k) ( m 1 , m 2 , ⋯ , m k ) ,求一个划分 C C C ,使得目标函数极小化:
min C ∑ l = 1 K ∑ C ( i ) = l ∥ x i − m l ∥ 2 \min_C \sum_{l=1}^K \sum_{C(i) = l} \lVert x_i - m_l \rVert^2
C min l = 1 ∑ K C ( i ) = l ∑ ∥ x i − m l ∥ 2
即在类中心确实的情况下,将每个样本分到一个类中,使样本和其所属类的中心之间的距离总和最小,即将每个样本指派到与其最近的中心 m l m_l m l 的类 G l G_l G l 中。
然后,对给定的划分 C C C ,再求各个类的中心 ( m 1 , m 2 , ⋯ , m K ) (m_1, m_2, \cdots, m_K) ( m 1 , m 2 , ⋯ , m K ) ,使得目标函数极小化:
min m 1 , ⋯ , m K ∑ l = 1 K ∑ C ( i ) = l ∥ x i − m l ∥ 2 \min_{m_1, \cdots, m_K} \sum_{l=1}^K \sum_{C(i) = l} \lVert x_i - m_l \rVert ^2
m 1 , ⋯ , m K min l = 1 ∑ K C ( i ) = l ∑ ∥ x i − m l ∥ 2
即在划分确实的情况下,使样本和其所属类的中心之间的距离总和最小。求解结果,对于每个包含 n l n_l n l 个样本的类 G l G_l G l ,更新其均值 m l m_l m l :
m l = 1 n l ∑ C ( i ) = l x i , l = 1 , ⋯ , K m_l = \frac{1}{n_l} \sum_{C(i) = l} x_i, l = 1, \cdots, K
m l = n l 1 C ( i ) = l ∑ x i , l = 1 , ⋯ , K
重复以上两个步骤,直到划分不再改变,得到聚类结果。
4.4 算法特性
总体特点 :K K K 均值聚类有以下特点:基于划分的聚类方法;类别数 K K K 事先指定;以欧氏距离平方表示样本之间的距离,以中心或样本的均值表示类别;以样本和其所属类的中心之间的距离的总和为最优化的目标函数;得到的类别是平坦的、非层次化的;算法是迭代算法,不能保证得到全局最优。
收敛性 :K K K 均值聚类属于启发式方法,不能保证收敛到全局最优,初始中心的选择会直接影响到聚类结果。
初始类的选择 :初始中心的选择,比如可以用层次聚类对样本进行聚类,得到 K K K 个类时停止。然后从每个类中选取一个与中心距离最近的点。
类别数的选择 :K K K 均值聚类中的类别数 K K K 需要预先指定,而在实际应用中最优的 K K K 值是不知道的。解决这个问题的一个方法是尝试用不同的 K K K 值聚类,检验各自得到聚类结果的质量,推测最优的 K K K 值。聚类结果的质量可以用类的平均直径来衡量。一般地,类别数变小时,平均直径会增加;类别数变大超过某个值后,平均直径会不变,这个值正是最优的 K K K 值。实际中,可以采用二分查找,快速找到最优的 K K K 值。
附录