K-means聚类算法

参考文献链接：

KMeans 算法（一）_在屋顶听歌的博客

基本概念

聚类（Clustering）：

样本集$D=\left\{x^{(1)}, x^{(2)}, \ldots, x^{(m)}\right\} $，包含$m$个无标记样本，每个样本$x^{(i)}=\left[x_{1}^{(i)}, x_{2}^{(i)}, \ldots, x_{n}^{(i)}\right]^{T} $是一个n维特征向量，则聚类算法将样本集$D$划分为$k$个不相交的簇$\left\{C^{(l)} \mid l=1,2, \ldots, k\right\}$

K-means算法

k-means（k均值）聚类属于原型聚类，无监督学习

算法思想

概括：随机地从数据集中选取K个点作为聚类中心，计算各个样本到聚类中心的距离，把样本归到离它最近的那个聚类中心所在的类；计算新形成的每一个聚类的数据对象的平均值，得到新的聚类中心，然后再迭代地分配点和更新据诶中心，直到聚类中心变化很小，或达到指定迭代次数。

▶ Input：

训练集Traning set ：$\{x_1,x_2,\dots,x_n\}$
聚类数量K：number of clusters

▶ Step-1：

Randomly initialize K cluster centroids ${c_1,c_2,\dots,c_k}$（随机初始化K个聚类中心）

▶ Step-2：

Repeat until convergence

for each point $x_i$：（为点赋类）
- find the nearest centroid $c_j$ （nearest度量准则：距离、相似度）
- assign the point $x_i$ to cluster $j$
for each cluster $j\in[1,K]$：（调整中心）
- new centroid $c_j$ = mean of all point $x_i$ assgined to cluster $j$
stop when the assignments no longer change.

需要考虑的几点：

K值的选择： k 值对最终结果的影响至关重要，而它却要预先给定。给定合适的 k 值，需要先验知识，凭空估计很困难，或者可能导致效果很差。
异常点的存在：在迭代的过程中使用所有点的均值作为新的质点(中心点)，如果簇中存在异常点，将导致均值偏差比较严重。

比如一个簇中有2、4、6、8、100五个数据，则新的质点为24，显然这个质点离绝大多数点都较远；当前情况下，使用中位数6可能比使用均值更好，使用中位数的聚类方式叫做K-Mediods聚类(K中值聚类)。
初值敏感：选择不同的初始值可能导致不同的簇划分规则。为避免这种敏感性导致的最终结果异常性，可以采用初始化多套初始节点构造不同的分类规则，然后选择最优的构造规则。

针对这点后面因此衍生了：二分K-Means算法、K-Means++算法、K-Means||算法、Canopy算法等。

详见：KMeans 算法（一）_在屋顶听歌的博客

优化目标

使目标函数极小化

选取欧式距离作为相似度指标，聚类目标是使得各类的距离平方和最小，定义样本点与所属聚类中心之间的距离总和为损失函数

$W(C)=\sum_{k=1}^{K} \sum_{x \in C_{k}}\left\|x-\mu_{k}\right\|^{2}$

其中，$K$是聚类个数，$\mu _k$ 是第$k$个类的均值。因此，目标函数为：

$C^*=\mathop{\arg\min}\limits_{C}W(C)$

优缺点

优点

原理简单、实现容易，收敛速度快
适用于高维数据

缺点

初始聚类中心不好把握
迭代→局部最优
对噪音和异常点敏感
不能处理非球形簇的聚类问题

距离和相似度

闵可夫斯基距离（Minkowski distance）

给定样本集合$X$，$X$是n维实数向量空间$R^n$中点的集合，其中

$x^{(i)}=\left[\begin{array}{llllll} x_{1}^{(i)}, & x_{2}^{(i)}, & \cdots & x_{n}^{(i)} \end{array}\right]^{T} \quad x^{(j)}=\left[\begin{array}{llll} x_{1}^{(j)}, & x_{2}^{(j)}, & \cdots & x_{n}^{(j)} \end{array}\right]^{T} \in R^{n}$

样本$x^{(i)}$和样本$x^{j}$的闵可夫斯基距离定义为：

$\operatorname{dis}\left(x^{(i)}, x^{(j)}\right)=\left(\sum_{k=1}^{n}\left|x_{k}^{(i)}-x_{k}^{(j)}\right|^{p}\right)^{\frac{1}{p}} \quad p \geq 1$

$p=1$：曼哈顿距离：$\operatorname{dis}\left(x^{(i)}, x^{(j)}\right)=\sum_{k=1}^{n}\left|x_{k}^{(i)}-x_{k}^{(j)}\right|$
$p=2$：欧氏距离：$\operatorname{dis}\left(x^{(i)}, x^{(j)}\right)=\left(\sum_{k=1}^{n}\left|x_{k}^{(i)}-x_{k}^{(j)}\right|^{2}\right)^{\frac{1}{2}}$
$p=\infty$：切比雪夫距离：$\operatorname{dis}\left(x^{(i)}, x^{(j)}\right)=\max _{k}\left|x_{k}^{(i)}-x_{k}^{(j)}\right|$

马氏距离（Mahalanobis distance)

夹角余弦相似度

余弦相似度的绝对值越接近于1，样本越相似，越接近0，越不相似

余弦相似度定义：

$\cos \left(x^{(i)}, x^{(j)}\right)=\frac{\left(x^{(i)}\right)^{T} x^{(j)}}{\left|x^{(i)}\right|\left|x^{(j)}\right|} \quad \in[-1,1]$

归一化的余弦相似度：

$\operatorname{sim}_{\cos }=1-\left(\frac{\cos ^{-1}\left(x^{(i)}, x^{(j)}\right)}{\pi}\right) \in[0,1]$

LiaN

【机器学习】k-means聚类算法