k-means 聚类算法

《机器学习》周志华 k均值算法学习笔记

聚类

无监督学习中的研究最多的应用最广的算法。
通过对无标记训练样本的学习来获得数据内在的规律。

簇

“聚类将能够像数据集中的样本划分为通常不相交的子集，每一个子集称为簇。”——《机器学习》周志华

性能度量

我们希望“物以类聚”，同一簇的样本尽可能相似，不同簇的样本尽量不同。性能度量就是评估聚类结果的好坏。
聚类的性能度量的两个指标：外部指标和内部指标。两者的区别在于有没有外界参考模型提供参考。

常用的聚类性能度量外部指标

Jaccard系数：
FM 指数：
Rand指数：
这些性能度量结果值在[0,1]且越大约好。

常用的聚类性能度量内部指标

DB指数：
DB指数越小越好。
Dunn指数：
Dunn指数越大越好。

距离计算

距离度量的函数需要满足4个基本性质：非负性，同一性，对称性，直递性。直递性不好理解，可以理解为三角形两边之和大于第三边。
非直递性的例子：人马例子。
假如人与人马的相似距离为1，马与人马的相似距离也为1，但是人与马的不相似，距离为5。1+1<5,这里不满足直递性，不能作为度量距离。所以要基于具体的数据来决定合适的距离计算式。
给定两个样本 $x_{i}$ , $x_{j}$ ,每个样本具有n个特征，计算这两个样本特征的距离（相似度）常用闵可夫斯基距离（Minkowski distance）

d i s t_{m} b (x_{i}, x_{j}) = (\sum_{u = 1}^{n} | x_{i u} - x_{j u} |^{p})^{\frac{1}{p}}

p = 1时称为曼哈顿距离；p = 2时称为欧氏距离。
把直接能在属性上计算距离的属性，如{1, 2, 3}，1与2近离3远，称为有序属性
闵可夫斯基距离用于计算有序属性。
不能直接在属性上计算距离的属性，如{人，马，鸟}，称为无序属性
无序属性用VDM (Value Difference Metric) 计算，

m_{u, a}

表示在属性u上取值为a的样本数，

m_{u, a, i}

表示在第i个样本簇中在属性u上取值为a的样本簇数，k为样本簇数，属性u上的两个离散值a，b之间的VDM距离为

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

不同的聚类方法

原型聚类。假设聚类结构可以通过一组原型刻画。
密度聚类。聚类结构可以通过样本分布的紧密程度确定。
层次聚类。在不同层次生对数据进行划分。

原型聚类

假设聚类结构能够通过一组原型刻画，不同的原型表示、求解方法会产生不同算法，常用的有：

k均值算法
学习向量量化
高斯混合聚类

k均值算法

给定样本集 $D = {x_{1}, x_{2}, . . ., x_{m}}$ ,k均值算法针对聚类所的簇 $C = {C_{1}, C_{2}, . ., C_{k}}$ 划分最小平方误差

E = \sum_{i = 1}^{k} \sum_{x \in C_{i}} ‖ x - u_{i} ‖_{2}^{2},

其中

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

是Ci的均值向量。
E很难求，实际上式通过迭代优化求解。

算法流程：
输入：样本集和簇数k
过程：
（1）随机选择k个样本组成初始均值向量（簇均值）；
（2）计算每一个样本与初始均值向量的距离；
（3）根据最近原则把样品划入相应的簇；
（4）计算新的簇均值并更新当前簇均值；
（5）重复（2）-（5），若迭代更新后聚类结果不变，返回簇分类结果。
输出：簇划分 $C = {C_{1}, C_{2}, . ., C_{k}}$