K-Means聚类算法

本次学习我们将详细介绍什么是K-Means聚类算法，使用数学的方法进行描述和解释，并给出K-means算法过程。

一、K-means算法简介

k-means算法是一种聚类算法，所谓聚类，即根据相似性原则，将具有较高相似度的数据对象划分至同一类簇，将具有较高相异度的数据对象划分至不同类簇。聚类与分类最大的区别在于，聚类过程为无监督过程，即待处理数据对象没有任何先验知识，而分类过程为有监督过程，即存在有先验知识的训练数据集。   
k-means算法中的k代表类簇个数，means代表类簇内数据对象的均值（这种均值是一种对类簇中心的描述），因此，k-means算法又称为k-均值算法。k-means算法是一种基于划分的聚类算法，以距离作为数据对象间相似性度量的标准，即数据对象间的距离越小，则它们的相似性越高，则它们越有可能在同一个类簇。数据对象间距离的计算有很多种，k-means算法通常采用欧氏距离来计算数据对象间的距离。
接下来，我们通过k-means算法的三个核心过程来介绍：距离、迭代、终止条件

1、k-means算法以距离作为数据对象间相似性度量的标准

距离有很多种，度量样本之间的相似性最常用的是欧几里得距离、曼哈顿距离和闵科夫斯基距离（ps:通常使用欧几里得距离）
– $x_{id}$就标识第$i$个数据的第$d$个属性值；
– 样本与簇之间的距离可以用样本到簇中心的距离$d(e_i,x)$表示；
– 簇与簇之间的距离可以用簇中心的距离$d(e_i,e_j)$表示。
假设数据中有$p$个属性，n个样本，则矩阵形式表示如下：
$$
\begin{bmatrix}
x_{11}&\dots&x_{1p} \\
\vdots&\ddots&\vdots\\
x_{n1}&\dots&x_{np}
\end{bmatrix}
$$
（1）欧几里得距离：
$$d(i,j) = \sqrt{(x_{i1}-x_{j1})^2+(x_{i1}-x_{j2})^2+\dots+(x_{ip}-x_{jp})^2}$$
（2）曼哈顿距离：
$$d(i,j) = |{x_{i1}-x_{j1}}|+|{x_{i2}-x_{j2}}|+\dots+|{x_{ip}-x_{jp}}|$$
（3）闵科夫斯基距离：
$$d(i,j) = \sqrt[q]{|{x_{i1}-x_{j1}}|^q+|{x_{i2}-x_{j2}}|^q+\dots+|{x_{ip}-x_{jp}}|^q}$$
$q$为正整数，$q=1$时即为曼哈顿距离；$q=2$时即为欧几里得距离。

2、k-means算法聚类过程中，每次迭代，对应的类簇中心需要重新计算（更新）

对应类簇中所有数据对象的均值，即为更新后该类簇的类簇中心。定义第$k$个类簇的类簇中心为$Center_k$，则类簇中心更新方式如下：
$$Center_k = \frac{1}{|C_k|}\sum_{x_i{\in}{C_k}}x_i$$
其中，$C_k$表示第k个类簇，$|C_k|$表示第k个类簇中数据对象的个数，这里的求和是指类簇k中所有元素在每列属性上的和，因此$Center_k$也是一个含有D个属性的向量，表示为
$$Center_k = (Center_{k,1},Center_{k,2},\dots,Center_{k,D})$$

3、不断迭代更新类簇，那么终止条件是什么？

1、设定迭代次数T
2、采用误差平方和准则函数
$$J = \sum_{k=1}^K\sum_{x_i\in{C_k}}dist(x_i,Center_k)$$
$K$表示类簇个数。当两次迭代J的差值小于某一阈值时，即J<δ时，则终止迭代

二、K-Means算法过程

补充：
1、T为设定的最大迭代次数
2、迭代开始前，要初始化k个中心
3、更新类簇中心

三、k-means算法优缺点

• 优点：
    算法简单易实现；
• 缺点：
    需要用户事先指定类簇个数K；
    聚类结果对初始类簇中心的选取较为敏感；
    容易陷入局部最优；
    只能发现球型类簇；