基于DBSCAN聚类算法java实现
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。 编写java程序对给定的25个数据点进行DBSCAN聚类，可以分出聚簇集合和噪声点，同时列出聚类的中心点。
1创建脚本文件
打开Eclipse软件，初始化界面如下所示：
进入后选择工作空间，界面如下所示：
进入软件后，初始界面如下所示
点击“Workbench”，左边为显示的当前文件夹，右边为命令行窗口和输出窗口。
点击菜单栏”File-New-Java Project”，创建一个新的java项目。
为项目命名“DBSCAN“，点击Finish完成创建。
右键点击src文件，点击New新建一个class文件
命名为“MyDBSCAN.java”
点击Finish完成创建。
2编写DBSCAN聚类算法程序
编写程序实现对25个给定点（点坐标在代码中指定）进行三个聚类的划分，最终结果展示中心点坐标，聚簇集合坐标和噪声点坐标。 聚类程序MyDBSCAN.java如下：
拷贝代码import java.util.ArrayList;
import java.util.List;
public class MyDBSCAN {
private static final double[][] points = {
{3.0, 8.04},
{4.0, 7.95},
{4.4, 8.58},
{3.6, 8.81},
{5.0, 8.33},
{6.0, 6.96},
{17.0, 4.24},
{18.0, 4.26},
{16.0, 3.84},
{17.0, 4.82},
{15.0, 5.68},
{17.0, 5.68},
{11.0, 10.68},
{13.0, 9.68},
{11.8, 10.0},
{12.0, 11.18},
{8.0, 12.0},
{9.2, 9.68},
{8.8, 11.2},
{10.0,11.4},
{7.0, 9.68},
{6.1, 10.68},
{5.70, 1.68},
{5.0, 2.68},
{12.0, 0.68}
};
private static int minpts = 6;
private static double radius = 1.3;
private static List
private static List
/**
*Euclidean distance
*/
private static double countEurDistance(double[] point1,double[] point2){
double eurDistance = 0.0;
for(int i=0;i
eurDistance += (point1[i]-point2[i])*(point1[i]-point2[i]);
}
return Math.sqrt(eurDistance);
}
/**
* find the core points
* @param points
* @param minpts
* @param radius
* @return
*/
private static List
List
for(int i = 0; i < points.length;i++){
int pts = 0;
for(int j = 0; j < points.length;j++){
for(int k = 0; k < points[i].length;k++){
if(countEurDistance(points[i], points[j])
pts++;
}
}
}
if(pts>=minpts){
cores.add(points[i]);
}
}
return cores;
}
/**
* put the core point to cluster and get the densityconnect
*/
private static void putCoreToCluster(){
clusters = new ArrayList
int clusterNum = 0;
for(int i = 0;i
clusters.add(new ArrayList
clusters.get(clusterNum).add(cores.get(i));
densityConnected(points, cores.get(i), clusterNum);
clusterNum++;
}
}
/**
*
* @param points
* @param core
* @param clusterNum
*/
private static void densityConnected(double[][] points,double[] core,int clusterNum){
boolean isputToCluster;
boolean isneighbour = false;
cores.remove(core);
for(int i = 0; i < points.length;i++){
isneighbour = false;
isputToCluster = false;
for(List
if(cluster.contains(points[i])){
isputToCluster = true;
break;
}
}
if(isputToCluster)continue;
if(countEurDistance(points[i], core)
isneighbour = true;
}
if(isneighbour){// if(cores.contains(points[i])){
cores.remove(points[i]);
densityConnected(points, points[i], clusterNum);
}
}
}
public static void main(String[] args){
cores = findCores(points, minpts, radius);
System.out.println("The number of the points:"+points.length);
System.out.println(cores.size()+" core points:");
for(double[] core:cores){
System.out.print("[");
for(int i = 0;i< core.length;i++){
System.out.print(core[i]);
if(i!=(core.length-1))
System.out.print(",");
}
System.out.print("]");
System.out.println();
}
putCoreToCluster();
int i = 0;
for(List
System.out.println("cluster "+ i++ +":");
for(double[] point:cluster){
System.out.println("["+point[0]+","+point[1]+"]");
}
}
int flag = 0;
for(int j = 0;j
flag = 0;
for(List
if(cluster.contains(points[j])){
flag = 1;
break;
}
}
if(flag==0)System.out.println("noise point:"+"["+points[j][0]+","+points[j][1]+"]");
}
}
}
3运行观察结果
右键点击左侧中文件中src文件夹，选择“Run As”-“Java Application”，运行之后得到下图中的结果。一共25个给定点，其中有13个中心点，聚成3类，另外剩下8个噪声点。
