mdistance.java

聚类算法：最短距离算法。对给定的数据集进行自底向上的层次的分解

import java.lang.*;
import java.io.*;



class Points{
	int x,y,N;
	Points next;
	void append(Points p){
		Points p2=this;
		while(p2.next!=null) p2=p2.next;
		p2.next=p;
	}
	void remove(Points p){
		p.next=null;
	}
}




public class MDistance {
	Points[] Elements=new Points[7];
	double[][]DistanMatrix=new double[7][7];
	
	double Distance(Points Cluster1,Points Cluster2){
		Points S1=new Points();Points S2=new Points();int k1=0;int k2=0;
		Points P1=Cluster1;Points P2=Cluster2;
		while(P1!=null){
			S1.x+=P1.x;S1.y+=P1.y;
			P1=P1.next;
			k1++;
		}
		double MeanX1=S1.x/k1;double MeanY1=S1.y/k1;
		while(P2!=null){
			S2.x+=P2.x;S2.y+=P2.y;
			P2=P2.next;
			k2++;
		}
		double MeanX2=S2.x/k2;double MeanY2=S2.y/k2;
		return Math.sqrt(Math.pow(MeanX1-MeanX2,2)+Math.pow(MeanY1-MeanY2,2));
	}
	
	public static void main(String[] args){
		String Datafile=args[0];
		int numberOfClusters=Integer.parseInt(args[1]);
		MDistance Cluster=new MDistance();
		try{
			File Fin=new File(Datafile);
			RandomAccessFile in=new RandomAccessFile(Fin,"r");
		    String X=in.readLine();
	        X=in.readLine();
	        int i=1;
	      while(X!=null){
	       	Cluster.Elements[i]=new Points();
	       	Cluster.Elements[i].N=Integer.parseInt(X.substring(0,1));
	       	Cluster.Elements[i].x=Integer.parseInt(X.substring(2,3));
	       	Cluster.Elements[i].y=Integer.parseInt(X.substring(4,5));
		   // System.out.println(Cluster.Elements[i].N+","+Cluster.Elements[i].x+","+Cluster.Elements[i].y);
	        i++;
	        X=in.readLine();}
			in.close();
			
		
	 }
	  catch(FileNotFoundException e1){
		System.err.println("File not found!");
	} catch(IOException e2){
		e2.printStackTrace();
	}
 for(int i=1;i<=6;i++) System.out.println("Cluster"+i);
 for(int numberOfPoints=6;numberOfPoints>numberOfClusters;numberOfPoints--){
     for(int i=1;i<=numberOfPoints;i++){
			for(int j=i+1;j<=numberOfPoints;j++){
				Cluster.DistanMatrix[j][i]=Cluster.Distance(Cluster.Elements[i],Cluster.Elements[j]);
				 //System.out.println(Cluster.DistanMatrix[j][i]);		
			}
		}
	/*for(int i=1;i<=numberOfPoints;i++){
		for(int j=1;j<=numberOfPoints;j++){
			System.out.print("("+i+","+j+")"+"-"+"["+Cluster.DistanMatrix[i][j]+"]"+"	");
			if(j%numberOfPoints==0)System.out.println();
			
		}
	}	
	System.out.println();*/	
	int k=2,l=1;
	for(int i=2;i<=numberOfPoints;i++){
		for(int j=1;j<=i-1;j++){
			
			if(Cluster.DistanMatrix[i][j]<Cluster.DistanMatrix[k][l]){
				k=i;l=j;
				
	        }
	    }
    }
    
    if(k<l){
    	System.out.println("----------------");
    	System.out.println("Cluster"+k+"+"+"Cluster"+l+"->"+"Cluster"+k+":"+"Distance="+
    						Cluster.DistanMatrix[k][l]);
		Cluster.Elements[k].append(Cluster.Elements[l]);
		for(int i=l;i<numberOfPoints;i++) Cluster.Elements[i]=Cluster.Elements[i+1];
		for(int i=1;i<numberOfPoints;i++){
			Points p=Cluster.Elements[i];
			while(p!=null){
				System.out.print(p.N);
				p=p.next;
			}
			System.out.println();
			}
			}
	 else{  
	 		System.out.println("----------------");
	 		System.out.println("Cluster"+k+"+"+"Cluster"+l+"->"+"Cluster"+k+":"+"Distance="+
    						Cluster.DistanMatrix[k][l]);
	 		
	 		Cluster.Elements[l].append(Cluster.Elements[k]);
	        for(int i=k;i<numberOfPoints;i++)Cluster.Elements[i]=Cluster.Elements[i+1];
	        for(int i=1;i<numberOfPoints;i++){
				System.out.print("Cluster"+i+":");
				Points p=Cluster.Elements[i];
				while(p!=null){
				System.out.print(p.N);
				p=p.next;
				}
			System.out.println();
			}
	}
	}
	}
   /*for(int i=1;i<=numberOfClusters;i++){
		System.out.print(i+":");
		Points p=Cluster.Elements[i];
		while(p!=null){
			System.out.print(p.N);
			p=p.next;
		}
		System.out.println();*/
	}