聚类方法_ 字节宝

1. 简介

聚类是针对给定的样本，依据它们特征的相似度或距离，将其归并到若干个「类」或「簇」的数据分析问题。一个类是样本的一个子集，直观上，相似的样本聚集在相同的类，不相似的样本分散在不同的类。

聚类的目的是通过得到的类或和入在来发现数据的特和点或对数据进行处理，在数据挖掘、模式识别等领域有着广泛的应用。聚类属于无监督学习，因为只是根据样本的相似度或距离将其进行归类，而类或簇事先并不知道。

常用的聚类算法有：层次聚类和 K 均值聚类。层次聚类又有聚合（自下而上）和裂（自上而下）两种方法。

聚合法：开始将每个样本各自分到一个类，之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件，得到层次化的类别。
分裂法：开始将所有样本分到一个类，之后将已有类中相距最远的样分到到两个新的类，重复此操作直到满足停止条件，得到层次化的类别。

KKK 均值聚类是基于中心的聚类方法，通过迭代，将样本分到 KKK 个类中，使得每个样本与其所属类的中心或均值最近，最后得到 KKK 个平坦的、非层次化的类别，构成对空间的划分。

2. 基本概念

聚类的基本概念，主要包括样本之间的距离或相似度、类或簇、类与类之间的距离。

2.1 相似度或距离

聚类的对象是观测数据，或样本集合。假设有 nnn 个样本，每个样本由 mmm 个属性的特征向量组成。样本集合可以用矩阵 XXX 表示

X=[xij]m×n=[x11x12⋯x1nx21x22⋯x2n⋮⋮⋱⋮xm1xm2⋯xmn]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=[xij]m×n=⎣⎡x11x21⋮xm1x12x22⋮xm2⋯⋯⋱⋯x1nx2n⋮xmn⎦⎤

矩阵 XXX 的第 jjj 列表示第 jjj 个样本，j=1,2,⋯ ,nj = 1, 2, cdots, nj=1,2,⋯,n；第 iii 行表示第 iii 个属性，i=1,2,⋯ ,mi = 1, 2, cdots, mi=1,2,⋯,m；矩阵元素 xijx_{ij}xij 表示第 jjj 个样本的第 iii 个属性值。聚类的核心概念是相似度或距离，有多种相似度或距离的定义。由于相似度直接影响聚类的结果，所以其选择是聚类的根本问题。具体哪种相似度更合适取决于应用问题的特性。

闵可夫斯基距离：给定样本集合 XXX，XXX 是 mmm 维实数向量空间 Rmmathbf{R}^mRm 中点的集合，其中 xi,xj∈Xx_i, x_j in Xxi,xj∈X，xi=(x1i,x2i,⋯ ,xmi)⊤x_i = (x_{1i}, x_{2i}, cdots, x_{mi})^topxi=(x1i,x2i,⋯,xmi)⊤，xj=(x1j,x2j,⋯ ,xnj)⊤x_j = (x_{1j}, x_{2j}, cdots, x_{nj})^topxj=(x1j,x2j,⋯,xnj)⊤，样本 xix_ixi 与样本 xjx_jxj 的闵可夫斯基距离定义为 dij=(∑k=1m∣xki−xkj∣p)1pd_{ij} = left( sum_{k=1}^m lvert x_{ki} - x_{kj} rvert^p right)^{frac{1}{p}} dij=(k=1∑m∣xki−xkj∣p)p1 其中，p≥1p geq 1p≥1。当 p=2p = 2p=2 时称为欧氏距离，当 p=1p = 1p=1 称为曼哈顿距离，当 p=∞p = inftyp=∞ 时称为切比雪夫距离，此时即为取各个坐标数值差的绝对值的最大值：dij=max⁡k∣xki−xkj∣d_{ij} = max_k lvert x_{ki} - x_{kj} rvertdij=maxk∣xki−xkj∣。
马哈拉诺比斯距离：给定样本集合 XXX，X=(xij)m×nX = (x_{ij})_{m times n}X=(xij)m×n，其协方差矩阵记作 SSS。样本 xix_ixi 与样本 xjx_jxj 之间的马哈拉诺比斯距离 dijd_{ij}dij 定义为 dij=[(xi−xj)⊤S−1(xi−xj)]12d_{ij} = left[ (x_i - x_j)^top S^{-1} (x_i - x_j) right]^{frac{1}{2}} dij=[(xi−xj)⊤S−1(xi−xj)]21 其中，xi=(x1i,x2i,⋯ ,xmi)⊤x_i = (x_{1i}, x_{2i}, cdots, x_{mi})^topxi=(x1i,x2i,⋯,xmi)⊤，xj=(x1j,x2j,⋯ ,xmj)⊤x_j = (x_{1j}, x_{2j}, cdots, x_{mj})^topxj=(x1j,x2j,⋯,xmj)⊤。当 SSS 为单位矩阵时，即样本数据的各个分量互相独立且各个分量的方差为 111 时，马哈拉诺斯比距离就是闵可夫斯基距离。马哈拉诺比斯距离简称马氏距离，其考虑各个分量之间的相关性并与各个分量的尺度无关。马氏距离越大相似度越小，距离越小相似度越大。
相关系数：样本之间的相似度也可以用相关系数来表示，相关系数的绝对值越接近 111，表示样本越相似；越接近 000，表示样本越不相似。样本 xix_ixi 与样本 xjx_jxj 之间的相关系数定义为 rij=∑k=1m(xki−xˉi)(xkj−xˉj)[∑k=1m(xki−xˉi)2∑k=1m(xkj−xˉj)2]12r_{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}}} rij=[∑k=1m(xki−xˉi)2∑k=1m(xkj−xˉj)2]21∑k=1m(xki−xˉi)(xkj−xˉj) 其中，xˉi=1m∑k=1mxki,xˉj=1m∑k=1mxkjbar{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=m1∑k=1mxki,xˉj=m1∑k=1mxkj。
夹角余弦：样本之间的相似度也可以用夹角余弦来表示，夹角余弦越接近 111，表示样本越相似；越接近 000，表示越不相似。样本 xix_ixi 与样本 xjx_jxj 之间的夹角余弦定义为 sij=∑k=1mxkixkj[∑k=1mxki2∑k=1mxkj2]12s_{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}}} sij=[∑k=1mxki2∑k=1mxkj2]21∑k=1mxkixkj

由以上几种相似度量的定义来看，使用距离度量相似度时，距离越小样本越相似；使用相关系数度量相似度时，相关系数越大样本越相似。注意不同相似度度量得到的结果并不一定一致，因此选择合适的距离或相似度非常重要。

2.2 类或簇

通过聚类得到的类或簇，本质是样本的子集。如果一个聚类方法假定一个样本只能属于一个类，或类的交集的空集，那么该方法称为硬聚类方法；否则，如果一个样本可以属于多个类，或类的交集不同空集，那么该方法称为软聚类方法。一般只考虑硬聚类方法。

用 GGG 表示类或簇，用 xi,xjx_i, x_jxi,xj 表示类中的样本，用 nGn_GnG 表示 GGG 中样本的个数，用 dijd_{ij}dij 表示样本 xix_ixi 与样本 xjx_jxj 之间的距离。类或簇有多种定义，常见的有以下几种：

定义一：设 TTT 为给定的正数，若集合 GGG 中任意两个样本 xi,xjx_i, x_jxi,xj 有 dij≤Td_{ij} leq Tdij≤T，则称 GGG 为一个类或簇。
定义二：设 TTT 为给定的正数，若对集合 GGG 中任意样本 xix_ixi，一定存在 GGG 中的另一个样本 xjx_jxj，使得 dij≤Td_{ij} leq Tdij≤T，则称 GGG 为一个类或簇。
定义三：设 TTT 为给定的正数，若对集合 GGG 中任意一个样本 xix_ixi，满足 1nG−1∑xj∈Gdij≤Tfrac{1}{n_G - 1} sum_{x_j in G} d_{ij} leq TnG−11∑xj∈Gdij≤T，其中 nGn_GnG 为 GGG 中样本的个数，则称 GGG 为一个类或簇。
定义四：设 TTT 和 VVV 为给定的两个正数，如果集合 GGG 中任意两个样本 xi,xjx_i, x_jxi,xj 的距离 dijd_{ij}dij 满足 1nG(nG−1)∑xi∈G∑xj∈Gdij≤Tdij≤Vfrac{1}{n_G(n_G - 1)} sum_{x_i in G} sum_{x_j in G} d_{ij} leq T \ d_{ij} leq V nG(nG−1)1xi∈G∑xj∈G∑dij≤Tdij≤V 则称 GGG 为一个类或簇。

以下四个定义，第一个定义最常用，且可以推出其他三个定义。

类的特征可以通过不同角度来刻画，常用的特征有下面三种：

类的均值：又称类的中心，记为 xˉGbar{x}_GxˉG： xˉG=1nG∑i=1nGxibar{x}_G = frac{1}{n_G} sum_{i=1}^{n_G} x_i xˉG=nG1i=1∑nGxi 式中 nGn_GnG 是类 GGG 的样本个数。
类的直径：类的直径是类中任意两个样本之间的最大距离，记为 DGD_GDG： DG=max⁡xi,xj∈GdijD_G = max_{x_i, x_j in G} d_{ij} DG=xi,xj∈Gmaxdij
类的样本散布矩阵：类的样本散布矩阵 AGA_GAG 定义为 AG=∑i=1nG(xi−xˉG)(xi−xˉG)⊤A_G = sum_{i=1}^{n_G} (x_i - bar{x}_G) (x_i - bar{x}_G)^top AG=i=1∑nG(xi−xˉG)(xi−xˉG)⊤
类的样本协方差矩阵：类的样本协方差矩阵 SGS_GSG 定义为 SG=1m−1AG=1m−1∑i=1nG(xi−xˉG)(xi−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 SG=m−11AG=m−11i=1∑nG(xi−xˉG)(xi−xˉG)⊤ 其中，mmm 为样本的维数，也即样本属性的个数。

2.3 类与类之间的距离

下面考虑类 GpG_pGp 与类 GqG_qGq 之间的距离 D(p,q)D(p, q)D(p,q)，也称为连接。类与类之间的距离也有多种定义。设类 GpG_pGp 包含 npn_pnp 个样本，GqG_qGq 包含 nqn_qnq 个样本，分别用 xˉpbar{x}_pxˉp 和 xˉqbar{x}_qxˉq 表示 GpG_pGp 和 GpG_pGp 的均值，即类的中心。

最短距离：也称单连接，定义类 GpG_pGp 的样本与 GqG_qGq 的样本之间的最短距离为两类之间的距离： Dpq=min⁡{dij∣xi∈Gp,xj∈Gq}D_{pq} = min{ d_{ij} | x_i in G_p, x_j in G_q } Dpq=min{dij∣xi∈Gp,xj∈Gq}
最长距离：也称完全连接，定义类 GpG_pGp 的样本与 GqG_qGq 的样本之间的最长距离为两类之间的距离： Dpq=max⁡{dij∣xi∈Gp,xj∈Gq}D_{pq} = max{ d_{ij} | x_i in G_p, x_j in G_q } Dpq=max{dij∣xi∈Gp,xj∈Gq}
中心距离：定义类 GpG_pGp 与类 GqG_qGq 的中心 xˉpbar{x}_pxˉp 与 xˉqbar{x}_qxˉq 之间的距离为两类之间的距离： Dpq=dxˉpxˉqD_{pq} = d_{bar{x}_p bar{x}_q} Dpq=dxˉpxˉq
平均距离：定义类 GpG_pGp 与类 GqG_qGq 任意两个样本之间距离的平均值为两类之间的距离： Dpq=1npnq∑xi∈Gp∑xj∈GqdijD_{pq} = frac{1}{n_p n_q} sum_{x_i in G_p} sum_{x_j in G_q} d_{ij} Dpq=npnq1xi∈Gp∑xj∈Gq∑dij

3. 层次聚类

层次聚类假设类别之间存在层次结构，将样本聚类到层次化的类中。层次聚类又有聚合或自下而上聚类、分裂或自上而下聚类两种方法。由于每个样本只属于一个类，所以层次聚类属于硬聚类。

聚合聚类开始将每个样本各自分到一个类；之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件；得到层次化的类别。
分裂聚类开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件；得到层次化的类别。

以聚合聚类为例，聚合聚类的具体过程如下：对于给定的样本集合，开始将每个样本分到一个类；然后按照一定规则，例如类间距离最小，将最满足规则条件的两个类进行合并；如此反复进行，每次减少一个类，直到满足停止条件。由此可知，聚合聚类需要预先确定下面三个要素：

距离或相似度；
合并规则；
停止条件。

根据这些要素的不同组合，就可以构成不同的聚类方法。距离或相似度可以是闵可夫斯基距离、马哈拉诺比斯距离、相关系数、夹角余弦。合并规则一般是类间距离最小，类间距离可以是最短距离、最长距离、中心距离、平均距离。停止条件可以是类的个类达到某个阈值、类的直径超过阈值。

4. K 均值聚类

KKK 均值聚类是基于样本集合划分的聚类算法。KKK 均值聚类将样本集合划分为 KKK 个子集，构成 KKK 个类，将 nnn 个样本分到 KKK 个类中，每个样本到其所属类的中心的距离最小。每个样本只能属于一个类，所以 KKK 均值聚类是硬聚类。

4.1 模型

给定 nnn 个样本的集合 X={x1,x2,⋯ ,xn}X = {x_1, x_2, cdots, x_n}X={x1,x2,⋯,xn}，每个样本由一个特征向量表示，特征向量的维数是 mmm。KKK 均值聚类的目标是将 nnn 个样本分到 K 个不同的类或簇中，这里假设 K<nK < nK<n。KKK 个类 G1,G2,⋯ ,GKG_1, G_2, cdots, G_KG1,G2,⋯,GK 形成对样本集合 XXX 的划分，其中

Gi∩Gj=∅,⋃i=1kGi=XG_i cap G_j = varnothing, bigcup_{i=1}^k G_i = X Gi∩Gj=∅,i=1⋃kGi=X

用 CCC 表示划分，一个划分对应着一个聚类结果。划分 CCC 是一个多对一的函数，如果把每个样本用一个整数 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}。故 KKK 均值聚类的模型是一个从样本到类的函数。

4.2 策略

KKK 均值聚类归结为样本集合 XXX 的划分，或者从样本到类的函数的选择问题。KKK 均值聚类的策略是通过损失函数的最小化选取最优的划分或函数 C∗C^{*}C∗。

首先，采用欧氏距离平方作为样本之间的距离 d(xi,xj)d(x_i, x_j)d(xi,xj)，然后定样本与其所属类的中心之间的距离的总和为损失函数，即

W(C)=∑l=1K∑C(i)=l∥xi−xˉl∥2W(C) = sum_{l=1}^K sum_{C(i) = l} lVert x_i - bar{x}_l rVert^2 W(C)=l=1∑KC(i)=l∑∥xi−xˉl∥2

式中 xˉl=(xˉ1l,xˉ2l,⋯ ,xˉml)⊤bar{x}_l = (bar{x}_{1l}, bar{x}_{2l}, cdots, bar{x}_{ml})^topxˉl=(xˉ1l,xˉ2l,⋯,xˉml)⊤ 是第 lll 个类的均值或中心，nl=∑i=1nI[C(i)=l]n_l = sum_{i=1}^n I[C(i) = l]nl=∑i=1nI[C(i)=l]，I[C(i)=l]I[C(i) = l]I[C(i)=l] 是指示函数，取值为 111 或 000。函数 W(C)W(C)W(C) 也称为能量，表示相同类中的样本相似的程度。

KKK 均值聚类就是求解最优化问题：

C∗=arg⁡min⁡CW(C)=arg⁡min⁡C∑l=1K∑C(i)=l∥xi−xˉl∥2begin{aligned} C^* & = argmin_C W(C) \ & = argmin_C sum_{l=1}^K sum_{C(i)=l} lVert x_i - bar{x}_l rVert^2 end{aligned} C∗=argCminW(C)=argCminl=1∑KC(i)=l∑∥xi−xˉl∥2

相似的样本被聚到同类时，损失函数值最小，这个目标函数的最优化能达到聚类的目的。但这是一个 NP 困难的组合优化问题，现实中采用迭代的方法求解。

4.3 算法

KKK 均值聚类的算法是一个迭代的过程，每次迭代包括两个步骤：

首先选择 KKK 个类的中心，将样本逐个指派到与其最近的中心的类中，得到一个聚类结果；
然后更新每个类的样本的均值，作为类的新的中心。

重复以上步骤，直到收敛为止。具体过程为：

首先，对于给定的中心值 (m1,m2,⋯ ,mk)(m_1, m_2, cdots, m_k)(m1,m2,⋯,mk)，求一个划分 CCC，使得目标函数极小化： min⁡C∑l=1K∑C(i)=l∥xi−ml∥2min_C sum_{l=1}^K sum_{C(i) = l} lVert x_i - m_l rVert^2 Cminl=1∑KC(i)=l∑∥xi−ml∥2 即在类中心确实的情况下，将每个样本分到一个类中，使样本和其所属类的中心之间的距离总和最小，即将每个样本指派到与其最近的中心 mlm_lml 的类 GlG_lGl 中。
然后，对给定的划分 CCC，再求各个类的中心 (m1,m2,⋯ ,mK)(m_1, m_2, cdots, m_K)(m1,m2,⋯,mK)，使得目标函数极小化： min⁡m1,⋯ ,mK∑l=1K∑C(i)=l∥xi−ml∥2min_{m_1, cdots, m_K} sum_{l=1}^K sum_{C(i) = l} lVert x_i - m_l rVert ^2 m1,⋯,mKminl=1∑KC(i)=l∑∥xi−ml∥2 即在划分确实的情况下，使样本和其所属类的中心之间的距离总和最小。求解结果，对于每个包含 nln_lnl 个样本的类 GlG_lGl，更新其均值 mlm_lml： ml=1nl∑C(i)=lxi,l=1,⋯ ,Km_l = frac{1}{n_l} sum_{C(i) = l} x_i, l = 1, cdots, K ml=nl1C(i)=l∑xi,l=1,⋯,K
重复以上两个步骤，直到划分不再改变，得到聚类结果。

4.4 算法特性

总体特点：KKK 均值聚类有以下特点：基于划分的聚类方法；类别数 KKK 事先指定；以欧氏距离平方表示样本之间的距离，以中心或样本的均值表示类别；以样本和其所属类的中心之间的距离的总和为最优化的目标函数；得到的类别是平坦的、非层次化的；算法是迭代算法，不能保证得到全局最优。
收敛性：KKK 均值聚类属于启发式方法，不能保证收敛到全局最优，初始中心的选择会直接影响到聚类结果。
初始类的选择：初始中心的选择，比如可以用层次聚类对样本进行聚类，得到 KKK 个类时停止。然后从每个类中选取一个与中心距离最近的点。
类别数的选择：KKK 均值聚类中的类别数 KKK 需要预先指定，而在实际应用中最优的 KKK 值是不知道的。解决这个问题的一个方法是尝试用不同的 KKK 值聚类，检验各自得到聚类结果的质量，推测最优的 KKK 值。聚类结果的质量可以用类的平均直径来衡量。一般地，类别数变小时，平均直径会增加；类别数变大超过某个值后，平均直径会不变，这个值正是最优的 KKK 值。实际中，可以采用二分查找，快速找到最优的 KKK 值。

附录

《统计学习方法》by 李航

聚类算法网络安全

0 人点赞