一 什么是基于密度的聚类算法
由于层次聚类算法和划分式聚类算往往只能发现凸形的聚类簇。为了弥补这一缺陷,发现各种任意形状的聚类簇,开发出基于密度的聚类算法。这类算法认为,在整个样本空间点中,各目标类簇是由一群的稠密样本点组成的,而这些稠密样本点被低密度区域(噪声)分割,而算法的目的就是要过滤低密度区域,发现稠密样本点。
二 DBSCAN(Density-based Spatial Clustering of Applications with Noise)
是一种基于高密度联通区域的聚类算法,它将类簇定义为高密度相连点的最大集合。它本身对噪声不敏感,并且能发现任意形状的类簇。
DBSCAN中的的几个定义:
Ε领域:给定对象半径为Ε内的区域称为该对象的Ε领域
核心对象:如果给定对象Ε领域内的样本点数大于等于MinPts,则称该对象为核心对象。
直接密度可达:对于样本集合D,如果样本点q在p的Ε领域内,并且p为核心对象,那么对象q从对象p直接密度可达。
密度可达:对于样本集合D,给定一串样本点p1,p2….pn,p=
p1,q= pn,假如对象pi从pi-1直接密度可达,那么对象q从对象p密度可达。
密度相连:对于样本集合D中的任意一点O,如果存在对象p到对象o密度可达,并且对象q到对象o密度可达,那么对象q到对象p密度相连。
可以发现,密度可达是直接密度可达的传递闭包,并且这种关系是非对称的。密度相连是对称关系。DBSCAN目的是找到密度相连对象的最大集合。
Eg: 假设半径Ε=3,MinPts=3,点p的E领域中有点{m,p,p1,p2,o}, 点m的E领域中有点{m,q,p,m1,m2},点q的E领域中有点{q,m},点o的E领域中有点{o,p,s},点s的E领域中有点{o,s,s1}.
那么核心对象有p,m,o,s(q不是核心对象,因为它对应的E领域中点数量等于2,小于MinPts=3);
点m从点p直接密度可达,因为m在p的E领域内,并且p为核心对象;
点q从点p密度可达,因为点q从点m直接密度可达,并且点m从点p直接密度可达;
点q到点s密度相连,因为点q从点p密度可达,并且s从点p密度可达。
三 算法描述
算法:DBSCAN
输入:E — 半径
MinPts — 给定点在E领域内成为核心对象的最小领域点数
D — 集合
输出:目标类簇集合
方法:repeat
1) 判断输入点是否为核心对象
2) 找出核心对象的E领域中的所有直接密度可达点
util 所有输入点都判断完毕
repeat
针对所有核心对象的E领域所有直接密度可达点找到最大密度相连对象集合,
中间涉及到一些密度可达对象的合并。
Util 所有核心对象的E领域都遍历完毕
算法:DBSCAN
输入:E — 半径
MinPts — 给定点在E领域内成为核心对象的最小领域点数
D — 集合
输出:目标类簇集合
方法:repeat
1) 判断输入点是否为核心对象
2) 找出核心对象的E领域中的所有直接密度可达点
util 所有输入点都判断完毕
repeat
针对所有核心对象的E领域所有直接密度可达点找到最大密度相连对象集合,
中间涉及到一些密度可达对象的合并。
Util 所有核心对象的E领域都遍历完毕
四 算法实现
package com.dbscan;
public class DataPoint {
private String dataPointName; // 样本点名
private double dimensioin[]; // 样本点的维度
private boolean isKey; //是否是核心对象
public DataPoint(){
}
public DataPoint(double[] dimensioin,String dataPointName,boolean isKey){
this.dataPointName=dataPointName;
this.dimensioin=dimensioin;
this.isKey=isKey;
}
}
------------
package com.dbscan;
import java.util.ArrayList;
import java.util.List;
public class Cluster {
private List<DataPoint> dataPoints = new ArrayList<DataPoint>(); // 类簇中的样本点
private String clusterName; //簇名
public List<DataPoint> getDataPoints() {
return dataPoints;
}
public void setDataPoints(List<DataPoint> dataPoints) {
this.dataPoints = dataPoints;
}
public String getClusterName() {
return clusterName;
}
public void setClusterName(String clusterName) {
this.clusterName = clusterName;
}
}
------------
package com.dbscan;
import java.util.ArrayList;
import java.util.List;
public class ClusterAnalysis {
public List<Cluster> doDbscanAnalysis(List<DataPoint> dataPoints,
double radius, int ObjectNum) {
List<Cluster> clusterList=new ArrayList<Cluster>();
for(int i=0; i<dataPoints.size();i++){
DataPoint dp=dataPoints.get(i);
List<DataPoint> arrivableObjects=isKeyAndReturnObjects(dp,dataPoints,radius,ObjectNum);
if(arrivableObjects!=null){
Cluster tempCluster=new Cluster();
tempCluster.setClusterName("Cluster "+i);
tempCluster.setDataPoints(arrivableObjects);
clusterList.add(tempCluster);
}
}
for(int i=0;i<clusterList.size();i++){
for(int j=0;j<clusterList.size();j++){
if(i!=j){
Cluster clusterA=clusterList.get(i);
Cluster clusterB=clusterList.get(j);