基于R语言的数据挖掘之聚类算法--划分方法

丶梦中人的梦中

当前聚类算法主要分为四类，包括划分方法、层次方法、基于密度的方法和基于网格的方法。本文主要是探讨一下划分方法下的聚类算法，其他的方法将在后期一一讲解。

本文的理论部分主要参考韩家炜的《数据挖掘：概念与技术》书中的内容。下面简单介绍一下四大类聚类方法：

划分方法：划分方法对n个观测的对象构建k个分区，其中每个分区表示一个簇。大部分划分方法是基于距离计算的，需要给定一个分区数k。比较常用的划分方法有k-均值和k-中心点算法，但这两种聚类方法合适中小规模的数据球形簇。

层次方法：该方法可以分为凝聚法和分裂法，凝聚法为自下而上的方法，期初将每个对象看做单独的组，然后依次合并相近的对象或组，直到所有组合并为一个大组；分裂法是自上而下的方法，开始将所有对象看做一个组，在每次迭代中，一个簇被划分为多个簇，直到每一个对象单独成为一个簇。但该方法的缺点是，一旦合并或分裂的步骤完成，就无法撤销，即不能更正错误的决定，有点类似于向前回归和向后回归。

基于密度的方法：由于大部分划分方法都是基于距离进行聚类，而这样聚类只能发现球状簇，对于非球形的簇则很难识别。密度方法可以解决这样的问题，该方法的思想是：只要“领域”中的密度(对象或数据点的个数)超过某个阈值，就继续增长给定的簇。这样的方法可以过滤噪声或离群点，发现任意形状的簇。

基于网格的方法：把对象空间量化为有限个单元，形成一个网格结构，所有的操作都在这个网格结构中进行。该方法的优点是处理速度快。

这里截一张《数据挖掘：概念与技术》中的四大类方法的概览图：

下面介绍一下划分方法中的k-menas(k均值算法)和k-medoids(k中心点算法)：

k-均值算法
该算法的目标就是使簇内高度相似，簇间低度相似。一般通过构建误差平方和函数实现这样的目标，如下为该函数的定义：


k-均值算法的步骤：
1）在n个观测中随机挑选k个观测，每个观测代表一个簇；
2）计算剩余的每个对象到各个簇的欧式距离，将他们分配到最相似的簇中，并计算新簇的均值；
3）使用新的均值作为新簇的中心，再重新分配所有对象，计算簇均值
4）重复2）和3）,直到分配稳定，形成最终的k个类。

这样的过程可以使用下图直观的表示：

k-均值算法存在的缺陷：
1）需要事先指定即将生成的k个簇，前提是比较熟悉所分析的数据对象。一般可以通过多个k值的尝试，最终选择比较合理的k值；
2）不适合发现非球形状的簇或大小差别很大的簇；
3）对噪声数据或离群点数据敏感，因为少量的异常数据对均值的产生极大的影响。

k-中心点算法
由于k-均值算法易受离群点的影响，而k-中心点算法则可以避免这样的问题，因为该方法是挑选实际对象作为簇。跟k-均值算法类似，它也挑选了一个函数(绝度误差标准)来度量聚类的质量，该函数是基于最小化所有对象到代表对象之间的相异度来进行划分。 该函数定义如下：


k-中心算法的步骤：
1）随机选择k个对象作为初始的中心点或簇；
2）将剩余的n-k个对象按照最近距离分配到各个簇中；
3）随机选择一个非代表对象y；
4）计算非代表对象y代替代表对象的总代价S(非代表对象计算出来的绝对误差总和-代表对象计算出来的绝对误差总和)；
5）如果S<0，则用非代表对象y替换代表对象，形成新的k个代表对象的集合；
6）重复2）3）4）5），直到分配稳定，形成最终的k个簇。

k-中心算法的不足：
1）仍然需要事先指定即将生成的k个簇；
2）不适合发现非球形状的簇或大小差别很大的簇；
3）不能很好的运用于大数据集。（当前解决的办法是：使用一种CLARA的基于抽样的方法，该方法并不考虑整个数据集，而是使用数据集的一个随机样本，然后再使用PAM方法计算最佳中心点。）

应用：k-均值聚类
R中自带的stats包中就有k-均值聚类的算法，实现算法的函数为kmeans。这里我们使用iris数据集检测k均值算法。
首选看一下k均值算法的kmeans函数语法：
kmeans(x, centers, iter.max = 10, nstart = 1,
algorithm = c("Hartigan-Wong", "Lloyd", "Forgy",
"MacQueen"), trace=FALSE)

x为数值矩阵或数据框
centers为指定的聚类个数k
iter.max最大迭代次数
algorithm指定k均值的算法
trance指定是否生成迭代过程

由于k均值聚类算法需要指定聚类簇的个数k，一般将k指定为多个数据，然后挑选出比较理想的k值。这里我们使用循环，将k值取在2到15之间,通过比较总的组内平方和变化，确定最佳的k值(一般选择波动比较大的组)。

循环脚本如下：

由于iris数据集不受量纲的影响，这里暂不对原始数据做标准化处理。

绘制各种组数下的总的组内平方和图：

从图的结果可知，在1,2,3类，总的组内平方和波动非常大，第4类及以后波动就非常小了，故可以考虑选择聚为3类。

验证聚为3类的效果：

从图中可以看到第三类的聚类效果不太理想。

最后看一下3个类下的变量均值


上文中k值的确定是通过循环比较而得，也可以考虑使用NbClust包中的NbClust函数确定最佳的聚类个数。



同样显示适合将数据聚为3类

应用：k-中心点聚类

k-中心点算法的实现可以使用fpc包中的pamk函数，也可以使用cluster包中的pam函数。当然k均值算法也可以使用fpc包中的kmeansruns函数。

pamk函数语法：
pamk(data,krange=2:10,criterion="asw", usepam=TRUE,
scaling=FALSE, alpha=0.001, diss=inherits(data, "dist"),
critout=FALSE, ns=10, seed=NULL, ...)

data指定要分析的数据；
krange指定聚类的个数，这是一个向量，相当于上文k均值聚类中的for循环，实现不同聚类个数的比较；
criterion指定聚类标准；
usepam为逻辑参数，为TRUE时，采用围绕中心的划分方法，为FALSE时采用上文提到的CLARA方法实现中心聚类。

下面看一看pamk函数的应用：
指定聚类标准为Calinski-Harabasz时，自动将数据集聚为了3类：

从上图可知8号、79号和113号样本成为了簇的中心点。

最后看一下分类效果是否与实际情况相符：

虽然k中心点算法可以解决k均值算法中对异常值敏感的问题，从上图的返回结果看，k中心点算法的聚类结果与k均值算法的聚类结果一致，这可能说明iris数据集不存在异常值。

总结：文中所涉及到的R包和函数
stats包
kmeans(）
NbClust包
NbClust()
cluster包
pam()
fpc包
pamk()