dbscan.java

用java写的DBscan算法

package DBscan;
import java.io.*;
import java.util.*;
import java.awt.*;
import javax.swing.*;


 

	
public class DBscan extends JFrame{
	
	private int MinPts;//密度阈值
    private double Eps;//区域半径
    private int patternnum;//对象的个数
	private int featurenum;//属性的个数
	private double [][] pattern;//
	private double [][] dis;
	private int [] number;//用于记录每个对象在Eps内核心点的个数
	private int [][] pos;//用于记录核心点的位置
	private int [] classname;//记录每个记录的类标号
	private int classnumber;//分好的类的个数
	

	
	//计算两个样本的距离,采用欧式距离
	public double getEucDistance(double [] a,double [] b)
	{
		double d=0.0;
		for(int i=0;i<featurenum;i++)
		{
			d+=((a[i]-b[i])*(a[i]-b[i]));
		}
		d=Math.sqrt(d);
		return d;
		  
	}
	
	
	
	//计算距离矩阵
	public void computeDis()
	{
		dis=new double[patternnum][patternnum];
		for(int i=0;i<patternnum;i++)
		  for(int j=0;j<patternnum;j++)
		      dis[i][j]=getEucDistance(pattern[i],pattern[j]);
	}
	
	
	
    
    public DBscan(int M,double r)
    {
    	this.MinPts=M;
    	this.Eps=r;
    	
    	
    	try {
           FileInputStream fis = new FileInputStream("d2.txt");
           InputStreamReader isr = new InputStreamReader(fis);
           LineNumberReader lnr = new LineNumberReader(isr);
           
           
          
           String s = null;
           s=lnr.readLine();
           patternnum=Integer.parseInt(s);
           s=lnr.readLine();
           featurenum=Integer.parseInt(s);
           pattern=new double[patternnum][featurenum];
           
        
           String [] str=new String[featurenum];
           for(int i=0;i<patternnum;i++)
           {
           	 s=lnr.readLine();
           	 int l=s.split(" ").length;
           	 String [] st=new String[l];
           	 st=s.split(" ");
           	 int k=0;
           	 for(int j=0;j<l;j++)
           	 {
           	   	if(!st[j].equals(""))
           	   	 str[k++]=st[j];
           	 }
           	 
           	 for(int j=0;j<featurenum;j++)
           	 {
           	 	pattern[i][j]=Double.parseDouble(str[j]);
           	 }
           }
           
           }catch(Exception e){
         	System.out.println(e.getMessage());
         } 
         
         
         /*for(int i=0;i<patternnum;i++)
          {for(int j=0;j<featurenum;j++)
            System.out.print(pattern[i][j]+" ");
           System.out.println(); 
           
          }*/
         setSize(400,300);
		 setVisible(true);
             
           
    	}
    
    
    
    
    
    
    
    
    //聚类函数
    public void cluster()
    {
    	computeDis();
    	number=new int[patternnum];
    	classname=new int[patternnum];
    	for(int i=0;i<patternnum;i++)
    	     classname[i]=0;
    	
    	int d;//记录密度可达的点
    	boolean isDealed[]=new boolean[patternnum];// 记录每个点是否被处理过
    	for(int i=0;i<patternnum;i++)
    	       isDealed[i]=false;
    	
    	for(int i=0;i<patternnum;i++)
    	{   
    	    d=0;
    		for(int j=0;j<patternnum;j++)
    		 if(dis[i][j]<=Eps)
    		   d++;
    		number[i]=d;   
    		
    	}
    	
    	pos=new int[patternnum][];
    	for(int i=0;i<patternnum;i++)
    	{
    		pos[i]=new int[number[i]];
    	}
    	
    	
    	
        //记录每个点的直接密度可达点的位置	
    	int k;
    	for(int i=0;i<patternnum;i++)
    	{   
    	    k=0;
    		for(int j=0;j<patternnum;j++)
    		  if(dis[i][j]<=Eps)
    		     pos[i][k++]=j;
    	}
    	
    	
    Queue<Integer> q=new LinkedList<Integer>();
    
    int  t;
    classnumber=1;//类标号从1开始
    for(int i=0;i<patternnum;i++)
    {
    	if(!isDealed[i]&&number[i]>=MinPts)
    	{
        	q.clear();
        	isDealed[i]=true;
        	System.out.print("cluster"+classnumber+": ");
        	System.out.print((i+1)+" ");
        	classname[i]=classnumber;
        	for(int j=0;j<number[i];j++)
        	  {
        	  	
        	  	if(!isDealed[pos[i][j]])
        	  	{
        	  		q.offer(pos[i][j]);
        	  	    isDealed[pos[i][j]]=true;
        	  	}    
        	  }
        	while(!q.isEmpty())
        	{
        		// System.out.print("@@@@@@");
        	     t=q.poll();//出队列
        	     System.out.print((t+1)+" ");
        	     classname[t]=classnumber;
        	     for(int j=0;j<number[t];j++)
        	     {
        	     	if(!isDealed[pos[t][j]])
        	     	  {
        	     		q.offer(pos[t][j]);
        	     	    isDealed[pos[t][j]]=true;
        	     	   } 
        	     }	
        	}
         System.out.println();
         classnumber+=1;	
    		
    	}//if
    	
    	
    }//for	
    	
    	
   /*for(int i=0;i<patternnum;i++)
    	  System.out.print(classname[i]+" "); */	
    	
    }
    
    
    
    
    
   
 public void paint(Graphics g)
	{
	if(featurenum==2)
	{
		super.paint(g);
	//	MyColor mc=0;
		for(int i=0;i<patternnum;i++)
		{ switch(classname[i])
		  {
		        case 0:
		        {
			       g.setColor(Color.BLACK);
			       g.fillOval((int)(pattern[i][0]),(int)pattern[i][1],6,6);
			       break;
			    }  
			    case 1:
			    {
			    	 g.setColor(Color.red);
			         g.fillOval((int)(pattern[i][0]),(int)pattern[i][1],6,6);
			         break;
			    } 
			    case 2:
			    {
			    	 g.setColor(Color.green);
			         g.fillOval((int)(pattern[i][0]),(int)pattern[i][1],6,6);
			         break;
			    } 
			    case 3:
			    {
			    	 g.setColor(Color.BLUE);
			         g.fillOval((int)pattern[i][0],(int)pattern[i][1],6,6);
			         break;
			    } 
			    case 4:
			    {
			         g.setColor(Color.darkGray);
			         g.fillOval((int)pattern[i][0],(int)pattern[i][1],6,6);
			         break;	
			    }
		}//switch
	 }//for	
	
	}//if

 }   
    
    
    
    
    
	/**
	 * Method main
	 *
	 *
	 * @param args
	 *
	 */
	 
	public static void main(String[] args) {
		// TODO: Add your code here
	//	DBscan db=new DBscan(4,1.4142135623);
	DBscan db=new DBscan(3,17);
	//   DBscan db=new DBscan(4,14);
		db.cluster();
	}	
}