【机器学习300问】38、什么是K-means算法？

在实际工作中，我们经常会遇到这样一类问题：给机器输入大量的特征数据，并期望机器通过学习找出数据存在的某种共性特征、结构或关联。这类问题被称为“非监督学习”问题。这篇文章我就来聚焦非监督学习中的其中一个任务——聚类

例如在数字营销中，可以基于用户在线浏览习惯、点击历史、社交媒体行为等多维度数据进行聚类分析。发现几个主要的用户群体，比如“科技发烧友”、“健身爱好者”和“亲子家庭”等。对于每一个细分群体，企业可以设计并推送定制化的广告内容，从而提高广告效果和转化率。

一、聚类是什么？

我之前的文章中提到的支持向量机SVM、逻辑回归和决策树机器学习算法都是用于分类问题。即更具一些已经给定类别标签的样本，训练某种分类器，使得他们能够对类别未知的样本进行分类。与分类问题不同，聚类是在事先不知道任何样本的类别标签的情况下，通过数据之间的内在关系把样本划分为若干类别，使得同类样本之间相似度高，不同类之间相似度低。

总结起来对聚类下个定义：聚类是机器学习中的一种无监督学习方法，它旨在通过相似性或距离度量将物理或抽象对象的集合自动划分为多个类别或簇。

二、什么K-means算法？

K-means算法又叫做K均值算法，他是一种迭代的无监督聚类方法，通过将数据集中的样本点划分到不同的K个簇中，来寻找数据的内在关联。

（1）K-means算法的目标

将数据集划分为K个簇，使得每个簇内的数据点彼此相似度较高，而不同的簇之间的数据点差异较大。
簇内的相似性通常基于欧式距离，即簇内所有数据点与该簇中心点的距离之和尽可能的小。

（2）如何判断两个样本相似？

通过两点之间的欧式空间中的距离，公式如下：

$dis(a,b)=\left \| a,b \right \|=\sqrt{(a_1-b_1)^2+(a_2-b_2)^2}$

三、简述K-means算法的具体步骤

（1）初始化

将数据样本先进行预处理（归一化、离群点处理等等），然后随机选取K个质心（簇中心），记为 $\mu _{1}^{(0)},\mu _{2}^{(0)}\mu _{3}^{(0)}...\mu _{K}^{(0)}$

定义代价函数，常用的代价函数是各个样本距离所属簇中心点的误差平方和：

$J(c,\mu)=\sum_{i=1}^{m}\left \| x_i-\mu_{c_i} \right \|^2$

符号	解释
J	代价函数
$x_i$	指第 $i$ 个样本
$c_i$	指 $x_i$ 所属的簇
$\mu_{c_i}$	指 $c_i$ 簇对应的中心点
m	是样本总数
$\mu_{k}$	第k个簇的中心点（质心）

（2）分配阶段

计算数据集中每个数据点到K个质心的距离，并将每个数据点分配给最近的质心所在的簇。

每个样本 $x_{i}$ 将其分配的距离最近的簇，公式如下：

$c_{i}^{(t)}\leftarrow \underset{k}{argmin}\left \| x_i-\mu_{k}^{(t)} \right \|^2$

（3）更新阶段

根据每个簇中新分配的数据点重新计算簇的质心，通常是取簇内所有数据点坐标的平均值作为新的质心。

每个类簇k，重新计算该类簇的中心，公式如下：

$\mu_{k}^{(t+1)}\leftarrow \underset{\mu}{argmin}\sum_{i:c_{i}^{(t)}=k}^{}\left \| x_i-\mu \right \|^2$

举例说明：比如有4个样本 $x_i$ 他们的坐标是 $(a_i,b_i)$ ，他们的质心计算可以拆解为，先计算x轴的平均值 $a_{\mu}=\frac{1}{4}(a_1+a_2+a_3+a_4)$ ，再计算y轴的平均值 $b_{\mu}=\frac{1}{4}(b_1+b_2+b_3+b_4)$ ，新质点 $\mu$ 的位置就是 $(a_{\mu},b_{\mu})$