k-均值聚类（k-means clustering）

聚类试图将数据集中的样本划分为若干个通常是不相交的子集。

距离计算 $dist(\cdot,\cdot)$

对函数 $dist(\cdot,\cdot)$，若它是一个距离度量，则需满足：

非负性： $dist(x{i},x{j}) \geq 0$
同一性： $dist(x{i},x{j}) = 0$ 当且仅当 $x{i} = x{j}$
对称性： $dist(x{i},x{j}) = dist(x{j},x{i})$
直递性： $dist(x{i},x{j}) \leq dist(x{i},x{k}) + dist(x{k},x{j})$

给定样本 $x{i} = (x{i1},x{i2},…,x{in})$ 与 $x{j} = (x{j1},x{j2},…,x{jn})$ ，最常用的是“闵可夫斯基距离”（Minkowshki distance）

$dist_{mk}(x_{i},x_{j}) = (\sum_{u=1}^{n}|x_{iu}-x_{ju}|^{p})^{\frac{1}{p}}$

当 $p=2$ 即欧式距离（Euclidean distance）。

当 $p=1$ 即曼哈顿距离（Manhattan distance）。

上式仅适用于有序属性（ordinal attribute），针对属性定义域{飞机，轮船，火车}等则属于无序属性（non-ordinal attribute）。

对于无序属性可采用VDM（Value Difference Metric），令 $m{u,a}$ 表示在属性 $u$ 上取值为 $a$ 的样本数， $m{u,a,i}$ 表示在第 $i$ 个样本簇中在属性 $u$ 上的取值为 $a$ 的样本数， $k$ 为样本簇数，则属性 $u$ 上两个离散值 $a$ 与 $b$ 之间的VDM距离为

$VDM_{p}(a,b)=\sum_{i=1}^{k}|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}|^{p}$

假设混合属性有 $n{c}$ 个有序属性、 $n-n{c}$ 个无序属性，则

$MinkovDM_{P}(x_{i},x_{j})=(\sum_{u=1}^{n_{c}}|x_{iu}-x_{ju}|^{p}+\sum_{u=n_{c}+1}^{n}VDM_{p}(x_{iu},x_{ju}))^{\frac{1}{p}}$

当样本中属性重要性不同时，可使用“加权距离”（weighted distance）。

$dist_{wmk}(x_{i},x_{j})=(w_{1} \cdot |x_{i1}-x_{j1}|^{p} + ... + w_{n} \cdot |x_{in}-x_{jn}|^{p})^\frac{1}{p}$

通常 $\sum{i=1}^{n}w{i}=1$ 。

算法流程

给定样本集 $D = {x{1},x{2},…,x{m}}$ ，k均值聚类算法针对聚类所得簇划分 $C = {C{1},C{2},…,C{k}}$ 最小化平方误差

$min\ E = \sum_{i=1}^{k}\sum_{x \in C_{i}}\|x-\mu_{i}\|_{2}^{2}$

其中

$\mu_{i}=\frac{1}{|C_{i}|}\sum_{x \in C_{i}}x$

直接求解该式为NP hard问题，因此采用启发式迭代。

缺点

不能保证定位到聚类中心的最佳方案，但能保证收敛到某个具体方案，即局部最优点
算法无法指出类别数，在同一数据集中，选择不同类别得到的结果不同，甚至不合理

改进

多次聚类，初始化聚类中心不同，选择方差最小的结果
将类别设置为1,逐步提高类别数，一般情况下，总方差快速下降直到达到某个拐点，这意味着再加一个新的聚类中心也不会显著减少总体方差。

TODO…

python实现

参考资料

机器学习西瓜书

k均值聚类的理解和实现

K-Means聚类算法