正确认识部门网站建设,温州网站制作网站,互联网+体育消费,wordpress缩略图解决方案机器学习笔记之谱聚类——K-Means聚类算法介绍引言回顾#xff1a;高斯混合模型聚类任务基本介绍距离计算k-Means\text{k-Means}k-Means算法介绍k-Means\text{k-Means}k-Means算法示例k-Means\text{k-Means}k-Means算法与高斯混合模型的关系k-Means\text{k-Means}k-Means算法的…
机器学习笔记之谱聚类——K-Means聚类算法介绍引言回顾高斯混合模型聚类任务基本介绍距离计算k-Means\text{k-Means}k-Means算法介绍k-Means\text{k-Means}k-Means算法示例k-Means\text{k-Means}k-Means算法与高斯混合模型的关系k-Means\text{k-Means}k-Means算法的缺陷引言
从本节开始将介绍聚类任务本节将介绍k-Means\text{k-Means}k-Means算法。
回顾高斯混合模型
高斯混合模型(Gaussian Mixture Model,GMM\text{Gaussian Mixture Model,GMM}Gaussian Mixture Model,GMM)是一种处理聚类任务的常用模型。作为一种概率生成模型它的概率图结构可表示为如下形式 其中隐变量Z\mathcal ZZ是一个离散型随机变量对应随机变量X\mathcal XX的后验结果服从高斯分布 Z∼Categorical Distribution(1,2,⋯,K)X∣Z∼N(μk,Σk)k∈{1,2,⋯,K}\begin{aligned} \mathcal Z \sim \text{Categorical Distribution}(1,2,\cdots,\mathcal K) \\ \mathcal X \mid \mathcal Z \sim \mathcal N(\mu_{k},\Sigma_{k}) \quad k \in \{1,2,\cdots,\mathcal K\} \end{aligned}ZX∼Categorical Distribution(1,2,⋯,K)∣Z∼N(μk,Σk)k∈{1,2,⋯,K} 从生成模型的角度高斯混合模型对P(X,Z)\mathcal P(\mathcal X,\mathcal Z)P(X,Z)进行建模。关于X\mathcal XX的概率密度函数P(X)\mathcal P(\mathcal X)P(X)可表示为如下形式 其中PZk\mathcal P_{\mathcal Z_k}PZk表示隐变量Z\mathcal ZZ选择离散结果kkk时的概率结果;μZk,ΣZk\mu_{\mathcal Z_k},\Sigma_{\mathcal Z_k}μZk,ΣZk表示对应X∣Zk\mathcal X \mid \mathcal Z_kX∣Zk高斯分布的均值和协方差信息。 P(X)∑ZP(X,Z)∑ZP(Z)⋅P(X∣Z)∑k1KPZk⋅N(μZk,ΣZk)\begin{aligned} \mathcal P(\mathcal X) \sum_{\mathcal Z} \mathcal P(\mathcal X,\mathcal Z) \\ \sum_{\mathcal Z} \mathcal P(\mathcal Z) \cdot \mathcal P(\mathcal X \mid \mathcal Z) \\ \sum_{k1}^{\mathcal K}\mathcal P_{\mathcal Z_k} \cdot \mathcal N(\mu_{\mathcal Z_k},\Sigma_{\mathcal Z_k}) \end{aligned}P(X)Z∑P(X,Z)Z∑P(Z)⋅P(X∣Z)k1∑KPZk⋅N(μZk,ΣZk)
聚类任务基本介绍
在生成模型综述——监督学习与无监督学习中简单介绍过聚类(Clustering\text{Clustering}Clustering)任务属于无监督学习(Unsupervised Learning\text{Unsupervised Learning}Unsupervised Learning)任务。无监督学习任务的特点是样本标签是未知的。而无监督学习的目标是通过学习无标签的样本来揭示数据的内在性质及规律。
而聚类试图将数据集内的样本划分为若干个子集每个子集称为一个簇(Cluster\text{Cluster}Cluster)。从概率/非概率模型的角度划分概率模型的典型模型是高斯混合模型而非概率的聚类模型其主要代表是 kkk均值算法(k-Means\text{k-Means}k-Means)。
距离计算
在介绍k-Means\text{k-Means}k-Means算法之前需要介绍聚类的有效性指标(Vaildity Index\text{Vaildity Index}Vaildity Index)。从直观上描述在聚类的过程我们更希望物以类聚——相同簇的样本尽可能地彼此相似不同簇的样本尽可能地不同。
对于两个样本点通常使用计算它们在样本空间中的距离 来描述两样本之间的相似性程度。样本之间距离越小样本之间的相似性程度越高反之同理。
已知两个样本x(i),x(j)x^{(i)},x^{(j)}x(i),x(j)表示如下 它们均属于ppp维特征空间即x(i),x(j)∈Rpx^{(i)},x^{(j)} \in \mathbb R^px(i),x(j)∈Rp. {x(i)(x1(i),x2(i),⋯,xp(i))Tx(j)(x1(j),x2(j),⋯,xp(j))T\begin{cases} x^{(i)} \left(x_1^{(i)},x_2^{(i)},\cdots,x_p^{(i)}\right)^T \\ x^{(j)} \left(x_1^{(j)},x_2^{(j)},\cdots,x_p^{(j)}\right)^T \end{cases}⎩⎨⎧x(i)(x1(i),x2(i),⋯,xp(i))Tx(j)(x1(j),x2(j),⋯,xp(j))T 关于描述样本x(i),x(j)x^{(i)},x^{(j)}x(i),x(j)之间的距离最常用的方法是明可夫斯基距离(Minkowski Distance\text{Minkowski Distance}Minkowski Distance) 其中参数m≥1m \geq 1m≥1. Distmk(x(i),x(j))(∑k1p∣xk(i)−xk(j)∣m)1m\text{Dist}_{\text{mk}}(x^{(i)},x^{(j)}) \left(\sum_{k1}^p \left|x_k^{(i)} - x_k^{(j)}\right|^m\right)^{\frac{1}{m}}Distmk(x(i),x(j))(k1∑pxk(i)−xk(j)m)m1 当m2m2m2时的明可夫斯基距离即欧几里得距离(Euclidean Distance\text{Euclidean Distance}Euclidean Distance)也称欧式距离 Disted(x(i),x(j))(∑k1p∣xk(i)−xk(j)∣2)12∑k1p∣xk(i)−xk(j)∣2∣∣x(i)−x(j)∣∣2\begin{aligned} \text{Dist}_{\text{ed}}(x^{(i)},x^{(j)}) \left(\sum_{k1}^p \left|x_k^{(i)} - x_k^{(j)}\right|^2\right)^{\frac{1}{2}} \\ \sqrt{\sum_{k1}^p \left|x_k^{(i)} - x_k^{(j)}\right|^2} \\ \left|\left|x^{(i)} - x^{(j)}\right|\right|_2 \end{aligned}Disted(x(i),x(j))(k1∑pxk(i)−xk(j)2)21k1∑pxk(i)−xk(j)2x(i)−x(j)2 当m1m1m1时的明可夫斯基距离即曼哈顿距离(Manhattan Distance\text{Manhattan Distance}Manhattan Distance) Distman∑k1p∣xk(i)−xk(j)∣∣∣x(i)−x(j)∣∣1\begin{aligned} \text{Dist}_{\text{man}} \sum_{k1}^p \left|x_k^{(i)} - x_k^{(j)}\right| \\ \left|\left|x^{(i)} - x^{(j)}\right|\right|_1 \end{aligned}Distmank1∑pxk(i)−xk(j)x(i)−x(j)1
k-Means\text{k-Means}k-Means算法介绍
给定一个样本集合D{x(1),x(2),⋯,x(N)}\mathcal D \{x^{(1)},x^{(2)},\cdots,x^{(N)}\}D{x(1),x(2),⋯,x(N)}并设定簇的数量C{C1,C2,⋯,CK}\mathcal C \{C_1,C_2,\cdots,C_{\mathcal K}\}C{C1,C2,⋯,CK}那么目标函数可描述成对所有的簇各簇内样本到均值向量之间的距离之和 {E∑k1K∑x∈CkDist(x,μk)μk1∣Ck∣∑x∈Ckx\begin{cases} \mathbb E \sum_{k1}^{\mathcal K} \sum_{x \in C_k} \text{Dist}(x,\mu_k) \\ \mu_{k} \frac{1}{|C_k|} \sum_{x \in C_k} x \end{cases}{E∑k1K∑x∈CkDist(x,μk)μk∣Ck∣1∑x∈Ckx 其中μk\mu_kμk表示簇CkC_kCk的均值向量。观察上式∑x∈CkDist(x,μk)\sum_{x \in C_k} \text{Dist}(x,\mu_k)∑x∈CkDist(x,μk)描述了簇CkC_kCk内样本围绕μk\mu_kμk的紧密程度
如果∑x∈CkDist(x,μk)\sum_{x \in C_k} \text{Dist}(x,\mu_k)∑x∈CkDist(x,μk)较小那么簇CkC_kCk内样本的紧密程度就高同理如果∑k1K∑x∈CkDist(x,μk)\sum_{k1}^{\mathcal K} \sum_{x \in C_k} \text{Dist}(x,\mu_k)∑k1K∑x∈CkDist(x,μk)小意味着各个簇内样本的紧密程度都较高从而达到样本分类的目的。
如果想要通过这种方式去寻找各簇对应的μk\mu_kμk这明显是一个NP-Hard\text{NP-Hard}NP-Hard问题均值向量μk\mu_kμk并不是某个真实的样本点因而它有无穷多种可能虽然在给定样本的条件下各簇对应的μk\mu_kμk是客观存在的但相应寻找的代价是极高的。 假设在当前样本条件下找到了最优的簇对应的μk\mu_kμk,但样本自身是存在噪声的如果新加入样本进来可能会使μk\mu_kμk产生变化。
那么k-Means\text{k-Means}k-Means方法采用贪心策略通过迭代的方式去近似求解E∑k1K∑x∈CkDist(x,μk)\mathbb E \sum_{k1}^{\mathcal K} \sum_{x \in C_k} \text{Dist}(x,\mu_k)E∑k1K∑x∈CkDist(x,μk)的最小值。下面通过实例使用k-Means\text{k-Means}k-Means算法进行近似求解。 示例转载自K-means 算法【基本概念篇】非常感谢侵删。
k-Means\text{k-Means}k-Means算法示例
已知包含二维特征的数据集合D\mathcal DD表示如下并针对该集合使用k-Means\text{k-Means}k-Means算法执行聚类任务 D{(2,10),(2,5),(8,4),(5,8),(7,5),(6,4),(1,2),(4,9)}\mathcal D \{(2,10),(2,5),(8,4),(5,8),(7,5),(6,4),(1,2),(4,9)\}D{(2,10),(2,5),(8,4),(5,8),(7,5),(6,4),(1,2),(4,9)} 对应二维图像表示如下
假设将上述集合内的样本点划分成三类因此需要选择三个类对应的初始中心。这里我们从集合中随机选择样本点作为初始中心(上图中的橙色样本点) 当然并不是说‘初始中心’就必须在样本中进行选择实际上只要是样本空间中任意点都可作为初始中心。 μ1(init)(2,10)μ2(init)(5,8)μ3(init)(1,2)\mu_1^{(init)} (2,10)\quad \mu_2^{(init)} (5,8)\quad \mu_3^{(init)} (1,2)μ1(init)(2,10)μ2(init)(5,8)μ3(init)(1,2)对两样本点之间的距离Dist(x(i),x(j));x(i),x(j)∈D\text{Dist}(x^{(i)},x^{(j)});x^{(i)},x^{(j)} \in \mathcal DDist(x(i),x(j));x(i),x(j)∈D进行定义。由于样本比较简单这里直接定义为曼哈顿距离 ρ[x(i),x(j)]∣x1(i)−x1(j)∣∣x2(i)−x2(j)∣{x(i)(x1(i),x2(i))Tx(j)(x1(j),x2(j))T\rho[x^{(i)},x^{(j)}] \left|x_1^{(i)} - x_1^{(j)}\right| \left|x_2^{(i)} - x_2^{(j)}\right| \quad \begin{cases} x^{(i)} (x_1^{(i)},x_2^{(i)})^T \\ x^{(j)} (x_1^{(j)},x_2^{(j)})^T \end{cases}ρ[x(i),x(j)]x1(i)−x1(j)x2(i)−x2(j){x(i)(x1(i),x2(i))Tx(j)(x1(j),x2(j))T定义完毕后将所有样本点分别与三个初始中心计算曼哈顿距离。具体结果表示如下 示例样本点(5,8)(5,8)(5,8)与初始中心(2,10)(2,10)(2,10)之间的曼哈顿距离 ρ∣5−2∣∣8−10∣5\rho |5-2| |8 - 10| 5ρ∣5−2∣∣8−10∣5 选择距离最小的初始中心并划分至该初始中心对应的簇。
SamplePoint/InitialCenter\text{SamplePoint/InitialCenter}SamplePoint/InitialCenterμ1(init):(2,10)\mu_1^{(init)}:(2,10)μ1(init):(2,10)μ2(init):(5,8)\mu_2^{(init)}:(5,8)μ2(init):(5,8)μ3(init):(1,2)\mu_3^{(init)}:(1,2)μ3(init):(1,2)ClusterResult\text{ClusterResult}ClusterResult(2,10)(2,10)(2,10)000555999111(2,5)(2,5)(2,5)555666444333(8,4)(8,4)(8,4)121212777999222(5,8)(5,8)(5,8)555000101010222(7,5)(7,5)(7,5)101010555999222(6,4)(6,4)(6,4)101010555777222(1,2)(1,2)(1,2)999101010000333(4,9)(4,9)(4,9)333222101010222
至此得到了第一次迭代产生的聚类结果表示如下 {Cluster 1: (2,10)Cluster 2: (8,4),(5,8),(7,5),(6,4),(4,9)Cluster 3: (2,5),(1,2)\begin{cases} \text{Cluster 1: }(2,10) \\ \text{Cluster 2: }(8,4),(5,8),(7,5),(6,4),(4,9) \\ \text{Cluster 3: }(2,5),(1,2) \\ \end{cases}⎩⎨⎧Cluster 1: (2,10)Cluster 2: (8,4),(5,8),(7,5),(6,4),(4,9)Cluster 3: (2,5),(1,2) 基于第一次迭代重新计算每个聚类的中心并替换初始中心 Cluster 1: \text{Cluster 1: }Cluster 1: 本次聚类中该类样本点只有1个因而新的聚类中心就是它自身Cluster 2: (6,6)⇐{xˉ1(45678)/56xˉ2(44589)/56\text{Cluster 2: } (6,6) \Leftarrow \begin{cases} \bar x_1 (45678) / 5 6 \\ \bar x_2 (44589) / 5 6\end{cases}Cluster 2: (6,6)⇐{xˉ1(45678)/56xˉ2(44589)/56Cluster 3: (1.5,3.5)⇐{(21)/21.5(52)/23.5\text{Cluster 3: }(1.5,3.5) \Leftarrow \begin{cases} (2 1)/2 1.5 \\ (5 2)/2 3.5 \end{cases}Cluster 3: (1.5,3.5)⇐{(21)/21.5(52)/23.5 此时基于替换中心的样本空间以及聚类区域表示如下(红色样本点表示第一次迭代后的新聚类中心) 重复执行上述步骤可以得到新的聚类中心以及对应的簇。直到聚类中心不再发生变化这意味着在迭代过程中通过计算聚类中心所产生的簇内部的样本点已经稳定不再发生变化。此时即可停止算法
k-Means\text{k-Means}k-Means算法与高斯混合模型的关系
从上面的迭代过程中可以发现整个计算过程与概率没有明显的关联关系。我们仅仅在迭代过程中执行了计算距离并比较大小、更新聚类中心这两种操作。
但从单个样本点的角度可以将其视作高斯混合模型的一种描述。以样本点(2,5)(2,5)(2,5)为例对该样本到各聚类中心之间的距离进行计算并将其映射至(0,1)区间 注意这里的箭头表示的是‘欧式距离’而不是曼哈顿距离。这里仅表示一个指向不要被误导。
注意距离数值越小的映射的结果越大。这意味着样本点与该聚类中心对应的簇关联更加密切。因而这里使用的标准化方法表示如下。其中NNN表示簇的个数;SumDistance\text{SumDistance}SumDistance表示样本到所有聚类中心的ManhattanDistance\text{ManhattanDistance}ManhattanDistance之和。 MappingResult1N−1(1−ManhattanDistanceSumDistance)\text{MappingResult} \frac{1}{N - 1}(1 - \frac{\text{ManhattanDistance}}{\text{SumDistance}})MappingResultN−11(1−SumDistanceManhattanDistance) 这里的标准化方法仅仅描述映射后的大小关系严格来说并不准确。这里提出一种函数Softmax(1ManhanttanDistance)\text{Softmax}(\frac{1}{\text{ManhanttanDistance}})Softmax(ManhanttanDistance1)作为参考。
ManhattanDistance\text{ManhattanDistance}ManhattanDistanceMappingResult\text{MappingResult}MappingResult(1.5,3.5)(1.5,3.5)(1.5,3.5)2220.42530.42530.4253(7,4.3)(7,4.3)(7,4.3)5.75.75.70.28680.28680.2868(3.67,9)(3.67,9)(3.67,9)5.675.675.670.28790.28790.2879
观察上述表格的MappingResult\text{MappingResult}MappingResult完全可以将这一组数值P(Z)[0.4253,0.5868,0.2879]\mathcal P(\mathcal Z) [0.4253,0.5868,0.2879]P(Z)[0.4253,0.5868,0.2879]看作是一个概率分布。该概率分布中概率值最大的是对应聚类中心(1.5,3.5)(1.5,3.5)(1.5,3.5)对应的簇结果。 另一种思路在于此时的聚类中心已经不是样本点了此时的聚类中心在样本空间中已经没有任何实际意义也符合隐变量的描述。
而样本点在给定聚类中心Z\mathcal ZZ的条件下那么样本点x(i)∣Zx^{(i)} \mid \mathcal Zx(i)∣Z服从高斯分布。因为该样本点距离聚类中心越近意味着它从该簇中生成的概率越高。因而可将k-Means\text{k-Means}k-Means视作一种基于高斯混合模型思想的硬划分模型(Hard-GMM\text{Hard-GMM}Hard-GMM)。
k-Means\text{k-Means}k-Means算法的缺陷
虽然k-Means\text{k-Means}k-Means算法简单但它同样存在缺陷
我们需要手动添加聚类数量。这需要对样本信息有一定程度的了解聚类数量的选择对聚类结果的影响是巨大的它对于聚类分布紧密(Compactness\text{Compactness}Compactness)的样本集合有不错的聚类效果如簇是凸形状(Convex\text{Convex}Convex)这种类似云团状的分布结构
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn import clustern_samples 500
colors [tab:blue,tab:orange,tab:green]
blobs datasets.make_blobs(n_samplesn_samples, random_state8)X,y blobs
KMeans cluster.MiniBatchKMeans(n_clusters3)
KMeans.fit(X)
yPred KMeans.predict(X)for _,(XElement,yPredElement) in enumerate(zip(X,yPred)):plt.scatter(XElement[0],XElement[1],colorcolors[yPredElement],s5)
plt.show()
返回结果如下 但针对连通性(Connectivity\text{Connectivity}Connectivity)簇分布它的聚类结果可能并不漂亮 我们原本希望将大圆与小圆中的样本划分开来;不仅k-Means出现这样的现象高斯混合模型同样会出现这种现象。
blobs datasets.make_circles(n_samplesn_samples, factor0.5, noise0.05)关于这种结构在核方法思想与核函数介绍中提到过使用核方法 k-Means\text{k-Means}k-Means的方式进行处理但这种方式同样因维度增加而可能出现维度诅咒/维度惩罚(Curse of Dimensionary\text{Curse of Dimensionary}Curse of Dimensionary)的风险。因此针对类似连通类型的簇分布k-Means\text{k-Means}k-Means并不可取。 下一节从k-Means\text{k-Means}k-Means的缺陷开始介绍谱聚类(Spectral Clusting\text{Spectral Clusting}Spectral Clusting)。
相关参考 机器学习-谱聚类1-背景介绍 K-means 算法【基本概念篇】 Sklearn\text{Sklearn}Sklearn中文文档——K-means 机器学习——周志华著
