基于密度的聚类算法优化

基于密度的聚类方法的开发目的是发现任意形状的簇。它把簇看作是数据空间中的稠密对象区域，这些稠密的区域被低密度区域（即噪声数据）隔开了，该方法对于含有噪声的数据对象集合的聚类效果相对较好。其基本思想是：依据密度实现对聚类。如果某邻近区域的数据对象的数目即区域密度大于给定阀值，就继续聚类。

基于密度的聚类方法包含一些定义，定义如下：

（1）邻域。给定数据对象半径ε内的邻域称为其ε邻域。

（2）核心对象。当某个数据对象的ε邻域中包含的数据对象的数量大于或等于最小数目Minpts时，称这个数据对象为核心对象。

（3）直接密度可达。在一个数据对象集合D中，如果数据对象p在数据对象q的邻域中，且数据对象q为核心对象，则称由q出发的p是直接密度可达的。

（4）如果存在一个对象链p1，p2，…，pn，p1＝q，pn＝p，对于数据对象pi∈D（1≤i≤n），pi＋1是从p直接密度可达的，则称数据对象p是从q关于邻域ε和最小数目Min pts密度可达的。

常用的此类方法有DBSCAN算法，其聚类过程如下：(www.xing528.com)

（1）计算数据对象集合D中的每一对象p的s邻域内对象的数目；

（2）若数据对象p的ε邻域中包含的数据对象的数目大于或等于Min pts，则建立一个以p为核心对象的簇M，簇中包含对象p的邻域内所有对象；

（3）寻找出核心对象的密度可达的对象，并把它包含到簇M中；

（4）转（3），直至再没有新的数据对象可被添加到簇中。

该算法的优缺点如表12－1所列。

表12-1　DBSCAN算法的优缺点