DBSCAN算法的Java實現

　　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的文件內容是

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　最後算法的結果是

　　第個聚類

　　<>

　　<>

　　<>

　　<>

　　<>

　　<>

　　<>

　　<>

　　<>

　　<>

　　<>

　　第個聚類

　　<>

　　<>

　　<>

　　<>

　　<>

　　<>

　　<>

　　大家畫一下坐標就可以理解實驗的結論了

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26957.html