在前面介绍的算法中，我们给定的数据集都是包含标签的，如 { ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , ⋯ , ( x ( m ) , y ( m ) ) } {(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),cdots,(x^{(m)},y^{(m)})} {(x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))}，其中的标签表明了数据的类别，算法可以根据标签得到数据的模型。
但是有一种没有标签的数据，如 { x ( 1 ) , x ( 2 ) , ⋯ , x ( m ) } {x^{(1)},x^{(2)},cdots,x^{(m)}} {x(1),x(2),⋯,x(m)}，其中的每个样本点没有固定的标签，聚类算法要做的就是根据这些无标签的数据，找到隐含在其中的结构信息。如下图所示，对于图中数据点，可以根据数据的特征将数据分为两个簇（cluster）。对无标签的数据进行学习的算法称为无监督学习（unsupervised learning）。
K-Means 算法将一组没有标签的数据分为 K 个相关的子集或簇，即簇的数量 K 是事先指定的。为了将如下的数据分为两类，使用 K-Means 算法的步骤如下：
随机生成如下两个点，称为 聚类中心（Cluster Centroids）。选择两个点的原因是因为想把这些数据聚为两类。
、
簇分配。遍历数据集中的每个样本，计算样本和每个聚类中心的距离，并选择距离最近的样本中心作为自己所属的类别，下图中将所有样本点分为红色和蓝色两类。
移动聚类中心。计算同一类数据点的均值，并将聚类中心移动到均值处。在上图中，首先计算所有红色点的均值，然后将红色的聚类中心移动到均值处；再计算蓝色点的均值，并移动蓝色的聚类中心，得到下图。
得到新的聚类中心后，我们对所有的样本点都重新分类，即重复第二步和第三步，直到聚类中心不再发生变化。如下所示
最终，所有样本被分为两类。
所以，整个 K-Means 算法可以总结如下：
输入：
quad 1. 聚类的类别数 K K K
quad 2. 训练集 { x ( 1 ) , x ( 2 ) , ⋯ , x ( m ) } {x^{(1)},x^{(2)},cdots,x^{(m)}} {x(1),x(2),⋯,x(m)}
随机初始化 K 个聚类中心： μ 1 , μ 2 , ⋯ , μ K ∈ R n mu_1,mu_2,cdots,mu_K in mathbb{R}^n μ1,μ2,⋯,μK∈Rn
do{
f o r i = 1 t o m quad for i=1 to m for i=1 to m
c ( i ) = i n d e x o f c l u s e t e r c e n t r o i d c l o s e s t t o x ( i ) quad quad c^{(i)} = index of cluseter centroid closest to x^{(i)} c(i)=index of cluseter centroid closest to x(i) (根据 x ( i ) x^{(i)} x(i) 与每个聚类中心的距离将其分类为 c ( i ) c^{(i)} c(i))
f o r k = 1 t o K quad for k=1 to K for k=1 to K
μ k = a v e r a g e o f p o i n t s a s s i g n e d t o c l u s t e r k quad quad mu_k = average of points assigned to cluster k μk=average of points assigned to cluster k (根据第 k 类的所有数据点更新聚类中心)
}while(!convergence)
如果使用 c ( i ) c^{(i)} c(i) 表示样本 x ( i ) x^{(i)} x(i) 所属的分类， μ k mu_k μk 表示第 k k k 类的聚类中心， μ c ( i ) mu_{c^{(i)}} μc(i) 表示类别为 c ( i ) c^{(i)} c(i) 的聚类中心（即，若样本 x ( i ) x^{(i)} x(i) 被划分为第五类，那么 c ( i ) = 5 c^{(i)}=5 c(i)=5， μ c ( i ) = μ 5 mu_{c^{(i)}}=mu_5 μc(i)=μ5 ）。则K-Means 算法中的代价函数可以表示如下，该代价函数也称为 失真函数（distortion function）：
J ( c ( 1 ) , ⋯ , c ( m ) , μ 1 , ⋯ , μ K ) = 1 m ∑ i = 1 m ∥ x ( i ) − μ c ( i ) ∥ 2 J(c^{(1)},cdots,c^{(m)},mu_1,cdots,mu_K)=frac{1}{m}sum_{i=1}^m|x^{(i)}-mu_{c^{(i)}}|^2 J(c(1),⋯,c(m),μ1,⋯,μK)=m1i=1∑m∥x(i)−μc(i)∥2
其中 ∥ x ( i ) − μ c ( i ) ∥ 2 |x^{(i)}-mu_{c^{(i)}}|^2 ∥x(i)−μc(i)∥2 表示样本 x ( i ) x^{(i)} x(i) 与聚类中心 μ c ( i ) mu_{c^{(i)}} μc(i) 距离的平方。
K-Means 的优化目标就是找到能使 J J J 最小的参数 c ( 1 ) , ⋯ , c ( m ) , μ 1 , ⋯ , μ K c^{(1)},cdots,c^{(m)},mu_1,cdots,mu_K c(1),⋯,c(m),μ1,⋯,μK，即：
min c ( 1 ) , ⋯ , c ( m ) , μ 1 , ⋯ , μ K J ( c ( 1 ) , ⋯ , c ( m ) , μ 1 , ⋯ , μ K ) min_{c^{(1)},cdots,c^{(m)}, atop mu_1,cdots,mu_K } J(c^{(1)},cdots,c^{(m)},mu_1,cdots,mu_K) μ1,⋯,μKc(1),⋯,c(m),minJ(c(1),⋯,c(m),μ1,⋯,μK)
在 K-Means 算法中， f o r i = 1 t o m for i=1 to m for i=1 to m是簇分配的过程，其对应为找到使代价函数最小的参数 c ( 1 ) , ⋯ , c ( m ) c^{(1)},cdots,c^{(m)} c(1),⋯,c(m)； f o r k = 1 t o K for k=1 to K for k=1 to K 是移动簇中心的操作，对应为找到使代价函数最小的参数 μ 1 , ⋯ , μ K mu_1,cdots,mu_K μ1,⋯,μK。
K-Means 的第一步是随机选择一些点作为聚类中心，但是随机选择的点最终得到的结果可能只是局部最优点，如下图所示，左边表示我们期望得到的聚类结果，但是右边两幅图都是局部最优的聚类结果。为了避免局部最优的情况，可以通过如下的方式来解决。
对于一些未知的数据，我们事先是不知道可以将其聚类为多少类的，如下所示，对于同样的数据集，可能会有不同的聚类数目，对于给定的数据集，我们怎么才能正确的选择合适的聚类数目呢？
肘部法则（Elbow Method）
依次选择不同个数的聚类数目，根据不同的聚类数目进行聚类，并计算该聚类数目下的损失函数 J J J，就可以得到如下的损失函数曲线，对于如下的曲线，存在一个拐点，经过该拐点之后，损失函数并没有再次快速下降，所以我们就可以把聚类数目选为拐点对应的 K K K。
但是通过这种方式可能得到的曲线并不存在拐点，如下所示，这时我们就不能根据该曲线确定聚类数目了。
根据最终目的选择聚类数目
很多时候我们并不直到到底哪个聚类数目更合适，这个时候我们可以根据我们想要达成的目的来对聚类结果进行评估，找到满足需求的聚类数目。
例如，对于 T-shirt 的尺寸分类，我们可以为不同身高和体重的人设置不同大小的 T-shirt，但是我们是选择 S、M 和 L ，或者选择 XS、S、M、L、XL 是根据顾客的需求设置的，我们应该选择更能满足客户需求的情况进行聚类。
本文发布于:2024-01-29 04:14:40，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170647288312620.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
