k-modes聚类算法介绍

为什么要用k-modes算法

k-means算法是一种简单且实用的聚类算法，但是传统的k-means算法只适用于连续属性的数据集，而对于离散属性的数据集，计算簇的均值以及点之间的欧式距离就变得不合适了。k-modes作为k-means的一种扩展，适用于离散属性的数据集。

k-modes算法介绍

假设有N个样本，M个属性且全是离散的，簇的个数为k
步骤一：随机确定k个聚类中心$C_1,C_2...C_k$，$C_i$是长度为M的向量，$C_i=[C_i^1,C_i^2,...,C_i^M]$

步骤二：对于样本$x_j(j =1,2,...,N)$，分别比较其与k个中心之间的距离（这里的距离为不同属性值的个数，假如$x_1=[1,2,1,3],C_1=[1,2,3,4]$，那么$x_1$与$C_1$之间的距离为2）

步骤三：将$x_j$划分到距离最小的簇，在全部的样本都被划分完毕之后，重新确定簇中心，向量$C_i$中的每一个分量都更新为簇$i$中的众数

步骤四：重复步骤二和三，直到总距离（各个簇中样本与各自簇中心距离之和）不再降低，返回最后的聚类结果。

算例

假设有7个样本，每个样本有4个属性，表示为矩阵X

$$X=\left\{ \begin{matrix} 1 & 5 & 0 & 3 \\ 1 & 6 & 1 & 3 \\ 3 & 6 & 0 & 3 \\ 2 & 7 & 0 & 4\\ 1 & 5 & 1 & 4\\ 2 & 5 & 1 & 2\\ \end{matrix} \right\} \tag{1}$$
随机确定2个聚类中心$C_1 = [1,5,1,3],C_2=[2,5,1,2]$
划分结果用Y表示

$$Y=\left\{ \begin{matrix} 1 & 0 \\ 1 & 0 \\ 1 & 0 \\ 0 & 1\\ 1 & 0\\ 0 & 1\\ \end{matrix} \right\} \tag{2}$$
即第1、2、3、5个样本被划分到 $C_1$，即第4、6个样本被划分到 $C_2$
接下来更新 $C_1和C_2$
$C_1=[1,6,0,3],C_2=[2,7,0,4]$（有多个众数就随机取一个，例子不好举，就这样吧）
后面的步骤就是不断重复步骤二和三了