dbscan.java

数据挖掘

package edu.xmu.Models.Clustering.CDBased.DBScan;

import java.util.Random;
import java.util.Vector;

import com.prudsys.pdm.Core.CategoricalAttribute;
import com.prudsys.pdm.Core.MiningException;
import com.prudsys.pdm.Core.NumericAttribute;
import com.prudsys.pdm.Input.MiningVector;
import com.prudsys.pdm.Models.Clustering.Cluster;
import com.prudsys.pdm.Models.Clustering.CDBased.CDBasedClusteringAlgorithm;

import eti.bi.exception.SysException;

public class DBScan extends CDBasedClusteringAlgorithm
{
	public static int UNVISITED = 0;
	
	public static int NOISE = 1;
	
	public static int CORE = 2;
	
	private double Eps;
	
	private int MinPts;
	
	private int numAtt;
	
	private int numVec;
	
	private int[] objectID;
	
	private int[] flags;
	
	private Vector vecQueue1 = new Vector();;
	
	private Vector vecQueue2 = new Vector();
	
	private Vector IndexQueue1 = new Vector();
	
	private Vector IndexQueue2 = new Vector();
	
	private int clusterAssignments[];

	
	
	@Override
	protected void runAlgorithm() throws MiningException
	{
	    int numbAtt = metaData.getAttributesNumber();
	    int numbVec = 0;

	    // Get minimum and maximum of attributes:
	    double[] minArr = new double[ numbAtt ];
	    double[] maxArr = new double[ numbAtt ];
	    for (int i = 0; i < numbAtt; i++) {
	      minArr[i] = 0.0;
	      maxArr[i] = 0.0;
	    };
	    while (miningInputStream.next()) {
	      MiningVector vec = miningInputStream.read();
	      for (int i = 0; i < numbAtt; i++) {
	        if (vec.getValue(i) < minArr[i])
	          minArr[i] = vec.getValue(i);
	        if (vec.getValue(i) > maxArr[i])
	          maxArr[i] = vec.getValue(i);
	      };
	      numbVec = numbVec + 1;
	    };
	    distance.setMinAtt( minArr );
	    distance.setMaxAtt( maxArr );

	    
	    
	    
		this.numAtt = metaData.getAttributesNumber();
		numVec=numbVec;
		//while (miningInputStream.next()) 
		//{
		//	numVec++;
		//}
		//if (Eps ==0) return;
		//if (numVec==0)return;
		flags = new int[numVec];
		objectID = new int [numVec];
		
		for(int current=0; current<numVec;current++)
		{
			flags[current] = UNVISITED;
			objectID[current] = 0;
		}
		
		int clusterings = 1;
		boolean isClustered = false;
		

		for(int current=0; current<numVec;current++)
		{			
		//	if(flags[current]==CORE || flags[current]==NOISE)
		//		continue;
			
			MiningVector vec = miningInputStream.read(current);
			vecQueue1.add(vec);
			IndexQueue1.add(current);
			
			while(!vecQueue1.isEmpty())
			{
				int index = Integer.parseInt(deleteQueue(IndexQueue1).toString());
				MiningVector vec1 = (MiningVector) deleteQueue(vecQueue1);
				
				if(flags[index]==CORE || flags[index]==NOISE)
					continue;
				
				for(int current1=0; current1<numVec;current1++) 
				{
					MiningVector vec2 = miningInputStream.read(current1);
					if(distance.distance(vec1, vec2) <= Eps)
					{
						vecQueue2.add(vec2);
						IndexQueue2.add(current1);
					}
				}
				
				if(vecQueue2.size() < MinPts)
					flags[index] = NOISE;
				else
				{
					flags[index] = CORE;
					isClustered = true;
					objectID[index] = clusterings;
					while(!vecQueue2.isEmpty())
					{
						int index1 = Integer.parseInt(deleteQueue(IndexQueue2).toString());
						MiningVector vec3 = (MiningVector) deleteQueue(vecQueue2);
						IndexQueue1.add(index1);
						vecQueue1.add(vec3);
						objectID[index1] = clusterings;
					}
				}
			}
			
			if(isClustered)
				clusterings++;
			isClustered = false;
		}

		clusterings++;
		
		clusters = new Cluster[clusterings];
		for (int i = 0; i < clusterings; i++) {
		      clusters[i] = new Cluster();
		      clusters[i].setName("clust" + String.valueOf(i));
		    }
		
	    for(int i =0 ; i < clusterings; i++)
	    	clusters[i].setCenterVec(miningInputStream.read(0)); 
	    
/*	    for (int i = 0; i < clusterings; i++) {
	        double[] nullVal     = new double[ numbAtt ];
	        MiningVector nullVec = new MiningVector( nullVal );
	        nullVec.setMetaData( metaData );
	        clusters[i].setCenterVec( nullVec );
	      };
	     
	    int[] cardClusters = new int[clusterings];
	    for (int i = 0; i < numbVec; i++) {
	        MiningVector vec = miningInputStream.read(i);
	        int index        = objectID[i];
	        for (int j = 0; j < numbAtt; j++) {
	          double val = clusters[index].getCenterVec().getValue(j);
	          val        = val + vec.getValue(j);
	          clusters[index].getCenterVec().setValue(j, val);
	        };
	        cardClusters[index] = cardClusters[index] + 1;
	      };
	      
	    for (int i = 0; i < clusterings; i++) {
	        for (int j = 0; j < numbAtt; j++) {
	          double val = clusters[i].getCenterVec().getValue(j);
	          int card   = cardClusters[i];
	          if (card == 0)
	            card = 1;
	          val = val / card;
	          clusters[i].getCenterVec().setValue(j, val);
	        };
	      };*/
		// -----------------------------------------------------------------------
		/**
		 * Assign containedVectors variable the appropriate value in the Cluster
		 * class. This value can be used to transform to WEKA's Istances later
		 * for easy data visualization. Similar code can be found in
		 * KLinkage.runAlgorithm() function.
		 */

			Vector[] allContainedVectors = null;
		    allContainedVectors = new Vector[clusterings];
			for (int i = 0; i < clusterings; i++) {
				allContainedVectors[i] = new Vector();
			}
/*			for (int i = 0; i < clusterings; i++) {
		        double[] nullVal     = new double[ numAtt ];
		        MiningVector nullVec = new MiningVector( nullVal );
		        nullVec.setMetaData( metaData );
		        clusters[i].setCenterVec( nullVec );
		      };*/
			for (int i = 0; i < numVec; i++) {
				MiningVector mingVec = miningInputStream.read(i);
				//if(objectID[i]!=-1)
					allContainedVectors[objectID[i]].addElement(mingVec);
			}

			 //Set the containedVectors variable 
			for (int i = 0; i < clusterings; i++) {
				clusters[i].setContainedVectors(allContainedVectors[i]);	
			//	clusters[i].setCenterVectors((Vector) allContainedVectors[i].elementAt(0));
			}


	}
	
	private Object deleteQueue(Vector Queue) 
	{
		Object index = Queue.elementAt(0);
		Queue.removeElementAt(0);
		return index;
	}



	/**
	 * gets the the index array of numric attributes in MiningVector.
	 * 
	 * @return the index array of numric attributes in MiningVector.
	 * @param numAtt,
	 *            the number of all attributes.
	 */
	public int[] getIndexOfNum(int numAtt) {
		int numberOfNumeric = 0;
		int[] indexOfNumeric;
		Vector temp = new Vector();
		for (int i = 0; i < numAtt; i++) {
			if (metaData.getMiningAttribute(i) instanceof NumericAttribute) {
				numberOfNumeric++;
				temp.addElement(new Integer(i));
			}
		}
		indexOfNumeric = new int[numberOfNumeric];
		for (int i = 0; i < numberOfNumeric; i++) {
			indexOfNumeric[i] = ((Integer) temp.elementAt(i)).intValue();
		}
		return indexOfNumeric;
	}

	public double getEps() {
		return Eps;
	}


	public void setEps(double epslion) {
		Eps = epslion;
	}


	public int getMinPts() {
		return MinPts;
	}


	public void setMinPts(int minPt) {
		MinPts = minPt;
	}

}