DBSCAN算法的Java实现

DBSCAN是一种基于密度的聚类算法 它的基本原理就是给定两个参数 ξ和minp 其中 ξ可以理解为半径 算法将在这个半径内查找样本 minp是一个以ξ为半径查找到的样本个数n的限制条件 只要n>=minp 查找到的样本点就是核心样本点 算法的具体描述见参考文件 下边是这个算法的java实现

首先定义一个Point类 代表样本点

<! [endif] >

package sunzhenxing

public class Point {

private int x

private int y

private boolean isKey

private boolean isClassed

public boolean isKey() {

return isKey

}

public void setKey(boolean isKey) {

this isKey = isKey

this isClassed=true

}

public boolean isClassed() {

return isClassed

}

public void setClassed(boolean isClassed) {

this isClassed = isClassed

}

public int getX() {

return x

}

public void setX(int x) {

this x = x

}

public int getY() {

return y

}

public void setY(int y) {

this y = y

}

public Point(){

x=

y=

}

public Point(int x int y){

this x=x

this y=y

}

public Point(String str){

String[] p=str split( )

this x=Integer parseInt(p[ ])

this y=Integer parseInt(p[ ])

}

public String print(){

return <+this x+ +this y+ >

}

}

然后定义一个工具类 为算法的实现服务

package sunzhenxing

import java io BufferedReader

import java io FileReader

import java io IOException

import java util *

public class Utility {

/**

* 测试两个点之间的距离

* @param p 点

* @param q 点

* @return 返回两个点之间的距离

*/

public static double getDistance(Point p Point q){

int dx=p getX() q getX()

int dy=p getY() q getY()

double distance=Math sqrt(dx*dx+dy*dy)

return distance

}

/**

* 检查给定点是不是核心点

* @param lst 存放点的链表

* @param p 待测试的点

* @param e e半径

* @param minp 密度阈值

* @return 暂时存放访问过的点

*/

public static List<Point>isKeyPoint(List<Point>lst Point p int e int minp){

int count=

List<Point>tmpLst=new ArrayList<Point>()

for(Iterator<Point>it=erator()it hasNext()){

Point q=it next()

if(getDistance(p q)<=e){

++count

if(!ntains(q)){

tmpLst add(q)

}

}

}

if(count>=minp){

p setKey(true)

return tmpLst

}

return null

}

public static void setListClassed(List<Point>lst){

for(Iterator<Point>it=erator()it hasNext()){

Point p=it next()

if(!p isClassed()){

p setClassed(true)

}

}

}

/**

* 如果b中含有a中包含的元素 则把两个集合合并

* @param a

* @param b

* @return a

*/

public static boolean mergeList(List<Point>a List<Point>b){

boolean merge=false

for(int index= index<b size()++index){

if(ntains(b get(index))){

merge=true

break

}

}

if(merge){

for(int index= index<b size()++index){

if(!ntains(b get(index))){

a add(b get(index))

}

}

}

return merge

}

/**

* 返回文本中的点集合

* @return 返回文本中点的集合

* @throws IOException

*/

public static List<Point>getPointsList() throws IOException{

List<Point>lst=new ArrayList<Point>()

String txtPath= src\\\\sunzhenxing\\points txt

BufferedReader br=new BufferedReader(new FileReader(txtPath))

String str=

while((str=br readLine())!=null &&str!= ){

lst add(new Point(str))

}

br close()

return lst

}

}

最后在主程序中实现算法 如下所示

package sunzhenxing

import java io *

import java util *

public class Dbscan {

private static List<Point>pointsList=new ArrayList<Point>()//存储所有点的集合

private static List<List<Point>>resultList=new ArrayList<List<Point>>()//存储DBSCAN算法返回的结果集

private static int e= //e半径

private static int minp= //密度阈值

/**

* 提取文本中的的所有点并存储在pointsList中

* @throws IOException

*/

private static void display(){

int index=

for(Iterator<List<Point>>it=erator()it hasNext()){

List<Point>lst=it next()

if(lst isEmpty()){

continue

}

System out println( 第 +index+ 个聚类 )

for(Iterator<Point>it =erator()it hasNext()){

Point p=it next()

System out println(p print())

}

index++

}

}

//找出所有可以直达的聚类

private static void applyDbscan(){

try {

pointsList=Utility getPointsList()

for(Iterator<Point>it=erator()it hasNext()){

Point p=it next()

if(!p isClassed()){

List<Point>tmpLst=new ArrayList<Point>()

if((tmpLst=Utility isKeyPoint(pointsList p e minp)) != null){

//为所有聚类完毕的点做标示

Utility setListClassed(tmpLst)

resultList add(tmpLst)

}

}

}

} catch (IOException e) {

// TODO Auto generated catch block

e printStackTrace()

}

}

//对所有可以直达的聚类进行合并 即找出间接可达的点并进行合并

private static List<List<Point>>getResult(){

applyDbscan()//找到所有直达的聚类

int length=resultList size()

for(int i= i<length++i){

for(int j=i+ j<length++j){

if(rgeList(resultList get(i) resultList get(j))){

resultList get(j) clear()

}

}

}

return resultList

}

/**

* 程序主函数

* @param args

*/

public static void main(String[] args) {

getResult()

display()

//System out println(Utility getDistance(new Point( ) new Point( )))

}

}

下边是一个小测试 即使用src\\\\sunzhenxing\\points txt文件的内容进行测试 points txt的文件内容是

最后算法的结果是

第 个聚类

<>

<>

<>

<>

<>

<>

<>

<>

<>

<>

<>

第 个聚类

<>

<>

<>

<>

<>

<>

<>

lishixinzhi/Article/program/Java/hx/201311/26957

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法将簇看做高密度区域以从低密度区域中区分开。由于这个算法的一般性，DBSCAN建立的簇可以是任何形状的。相对的，K-means则假设簇是凸的。核样本的概念是DBSCAN的重要成分，核样本是指高密度区域的样本。一个簇是由互相靠近的核样本的集合以及靠近核样本的非核样本组成的集合组成的。这个算法有两个参数，

min_samples 和 eps ，这两个参数表示数据的稠密性。当 min_samples 增加 或者 eps 减小的时候，意味着一个簇分类有更大的密度要求。

若样本在数据集中存在 eps 距离内有至少 min_samples ，则该样本可以成为核样本。也用来定义边缘样本。核样本是向量空间的高密度区域。通过找到一个核样本，找到其附近的核样本，再找到附近核样本的附近的核样本递归地建立由核样本组成的簇。一个簇也包含邻居是核样本的非核样本。

根据定义，任何核样本是簇的一部分。任何距离核样本至少 eps 距离非核样本是异常值。

从下图中可以看到，不同的颜色表示不同的簇。大圈圈表示算法定义的核样本，小圈圈表示仍是簇的组成部分的非核样本。黑色点表示异常值。

这个算法是有随机性的，虽然标签会变化，但是核样本始终属于同一个簇。非确定性主要来自非核样本的归属。一个非核样本可能距离两个簇的非核样本都小于 eps 。根据三角不等式，这两个核样本之间的距离大于 eps ，否则他们会属于同一个簇。非核样本将会属于先产生的簇，而簇产生的先后顺序是随机的。不考虑数据集的顺序，算法是确定性的，相同数据上的 结果也会相对稳定。

当先实现是使用球树和线段树来计算点的邻居，这避免了计算时全距离矩阵。可以使用一般的距离度量方法。

当前实现不是一个节约内存的算法，因为它建立了kd-tree和ball-tree不能使用的成对的相似矩阵。可以绕过这个的方法如下：

class sklearn.cluster.DBSCAN( eps=0.5 , min_samples=5 , metric='euclidean' , algorithm='auto' , leaf_size=30 , p=None , n_jobs=1 )

程序地址： http://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html#sphx-glr-auto-examples-cluster-plot-dbscan-py

关键在于调节前面提到的两个参数，需要不断修正。如果需要测试数据，可以留言。

---