DBSCAN是一种基于密度的聚类算法它的基本原理就是给定两个参数ξ和minp其中 ξ可以理解为半径算法将在这个半径内查找样本minp是一个以ξ为半径查找到的样本个数n的限制条件只要n>=minp查找到的样本点就是核心样本点算法的具体描述见参考文件下边是这个算法的java实现
首先定义一个Point类代表样本点
<![endif]>
package comsunzhenxing;
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) {
thisisKey = isKey;
thisisClassed=true;
}
public boolean isClassed() {
return isClassed;
}
public void setClassed(boolean isClassed) {
thisisClassed = isClassed;
}
public int getX() {
return x;
}
public void setX(int x) {
thisx = x;
}
public int getY() {
return y;
}
public void setY(int y) {
thisy = y;
}
public Point(){
x=;
y=;
}
public Point(int xint y){
thisx=x;
thisy=y;
}
public Point(String str){
String[] p=strsplit();
thisx=IntegerparseInt(p[]);
thisy=IntegerparseInt(p[]);
}
public String print(){
return <+thisx++thisy+>;
}
}
然后定义一个工具类为算法的实现服务
package comsunzhenxing;
import javaioBufferedReader;
import javaioFileReader;
import javaioIOException;
import javautil*;
public class Utility {
/**
* 测试两个点之间的距离
* @param p 点
* @param q 点
* @return 返回两个点之间的距离
*/
public static double getDistance(Point pPoint q){
int dx=pgetX()qgetX();
int dy=pgetY()qgetY();
double distance=Mathsqrt(dx*dx+dy*dy);
return distance;
}
/**
* 检查给定点是不是核心点
* @param lst 存放点的链表
* @param p 待测试的点
* @param e e半径
* @param minp 密度阈值
* @return 暂时存放访问过的点
*/
public static List<Point> isKeyPoint(List<Point> lstPoint pint eint minp){
int count=;
List<Point> tmpLst=new ArrayList<Point>();
for(Iterator<Point> it=erator();ithasNext();){
Point q=itnext();
if(getDistance(pq)<=e){
++count;
if(!ntains(q)){
tmpLstadd(q);
}
}
}
if(count>=minp){
psetKey(true);
return tmpLst;
}
return null;
}
public static void setListClassed(List<Point> lst){
for(Iterator<Point> it=erator();ithasNext();){
Point p=itnext();
if(!pisClassed()){
psetClassed(true);
}
}
}
/**
* 如果b中含有a中包含的元素则把两个集合合并
* @param a
* @param b
* @return a
*/
public static boolean mergeList(List<Point> aList<Point> b){
boolean merge=false;
for(int index=;index<bsize();++index){
if(ntains(bget(index))){
merge=true;
break;
}
}
if(merge){
for(int index=;index<bsize();++index){
if(!ntains(bget(index))){
aadd(bget(index));
}
}
}
return merge;
}
/**
* 返回文本中的点集合
* @return 返回文本中点的集合
* @throws IOException
*/
public static List<Point> getPointsList() throws IOException{
List<Point> lst=new ArrayList<Point>();
String txtPath=src\\com\\sunzhenxing\\pointstxt;
BufferedReader br=new BufferedReader(new FileReader(txtPath));
String str=;
while((str=brreadLine())!=null && str!=){
lstadd(new Point(str));
}
brclose();
return lst;
}
}
最后在主程序中实现算法如下所示
package comsunzhenxing;
import javaio*;
import javautil*;
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();ithasNext();){
List<Point> lst=itnext();
if(lstisEmpty()){
continue;
}
Systemoutprintln(第+index+个聚类);
for(Iterator<Point> it=erator();ithasNext();){
Point p=itnext();
Systemoutprintln(pprint());
}
index++;
}
}
//找出所有可以直达的聚类
private static void applyDbscan(){
try {
pointsList=UtilitygetPointsList();
for(Iterator<Point> it=erator();ithasNext();){
Point p=itnext();
if(!pisClassed()){
List<Point> tmpLst=new ArrayList<Point>();
if((tmpLst=UtilityisKeyPoint(pointsList p e minp)) != null){
//为所有聚类完毕的点做标示
UtilitysetListClassed(tmpLst);
resultListadd(tmpLst);
}
}
}
} catch (IOException e) {
// TODO Autogenerated catch block
eprintStackTrace();
}
}
//对所有可以直达的聚类进行合并即找出间接可达的点并进行合并
private static List<List<Point>> getResult(){
applyDbscan();//找到所有直达的聚类
int length=resultListsize();
for(int i=;i<length;++i){
for(int j=i+;j<length;++j){
if(rgeList(resultListget(i) resultListget(j))){
resultListget(j)clear();
}
}
}
return resultList;
}
/**
* 程序主函数
* @param args
*/
public static void main(String[] args) {
getResult();
display();
//Systemoutprintln(UtilitygetDistance(new Point() new Point()));
}
}
下边是一个小测试 即使用src\\com\\sunzhenxing\\pointstxt文件的内容进行测试pointstxt的文件内容是
最后算法的结果是
第个聚类
<>
<>
<>
<>
<>
<>
<>
<>
<>
<>
<>
第个聚类
<>
<>
<>
<>
<>
<>
<>
大家画一下坐标就可以理解实验的结论了
