<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">今天继续和小伙伴们分享聚类算法和R语言的实现，上篇和大家分享了聚类中的距离、类间距离和最古典的层次聚类法，今天和大家分享几个动态聚类算法。</span>

首先和大家分享被评为十大数据挖掘算法之一的K-means 算法（K为分类的个数，mean为平均值，该算法的难点即为K的指点）

Step1：选择K个点作为初始质心；
Step2：将剩余每个点指派到最近的质心，形成K个簇（聚类）；
Step3：重新计算簇的质心（坐标平均值）；
Step4：重复2-3直至质心不发生变化；

接下来看看R语言如何实现K-means:

X=iris[,1:4]
km=kmeans(X,3)#数据库+分类数

可见R语言的强大性，但是K的指定确实很有技巧，可以先做一次层次聚类法，得出K取多少会相对合适；

K-means优点：

有效率，且不容易受初始值选择的影响；

缺点：

1、  不能处理非球形的簇；

2、  不能处理不同尺度，不同密度的簇（聚类的球大小层次不齐）；

3、  离群值可能会有较大的干扰（因此要先剔除）

基于密度的方法：DBSCAN（Density-Based Spatial Clustering of Applications with Noise）

前面提到的K-means比较适合球形分布的案例，对于下图所示的点群则效果不好，接下来引入另一种聚类方法来解决这类问题。

首先解释下基本的概念：

r-邻域：给定点半径r内的区域

核心点：如果一个点的r-邻域至少包含最少数目M个点，则称该点为核心点

直接密度可达：如果点p在核心点q的r-邻域内，则称p是从q出发可以直接密度可达

如果存在点链p1,p2, …, pn，p1=q，pn=p，pi+1是从pi关于r和M直接密度可达，则称点p是从q关于r和M密度可达的（见下图）,注意密度可达是单向的。

Ps:密度可达即可以纳入同一类；

如果样本集D中存在点o，使得点p、q是从o关于 r和M密度可达的，那么点p、q是关于r和M密度相连（见下图）

DBSCAN基本算法：

Step1：指定合适的 r 和 M；
Step2： 计算所有的样本点，如果点p的r邻域里有超过M个点，则创建一个以p为核心点的新簇；
Step3： 反复寻找这些核心点直接密度可达（之后可能是密度可达）的点，将其加入到相应的簇，对于核心点发生“密度相连”状况的簇，给予合并
Step4 ：当没有新的点可以被添加到任何簇时，算法结束
Ps：DBSCAN对用户定义的参数很敏感，细微的不同都可能导致差别很大的结果，而参数的选定无规律可循，只能靠经验确定。

install.packages(fpc)
library(fpc)
iris.data<-iris[,-5]
ds<-dbscan(iris.data,1.5,MinPts=30,scale=TRUE,showplot=TRUE,method="raw")

结果如下图：

R语言与数据分析之四：聚类算法2