kmeans.java

用于multivariate时间序列分类

/**
  * This is a simple k means clustering algorithm.
  * Auto numclasses works out the average number of events per event vec. 
  * 
  *
  *
  * 
  * @author Waleed Kadous
  * @version $Id: KMeans.java,v 1.1.1.1 2002/06/28 07:36:16 waleed Exp $
  */

package tclass.clusteralg;   
import tclass.*; 
import tclass.util.*; 
import java.util.*; 


class KMClusterVec implements ClusterVecI {
    KMCluster[] clusters; 
    

    KMClusterVec(KMCluster[] clusters){
	this.clusters = clusters; 
    }

    
    public ClusterMem findBestLabel(EventI ev){
        return null; 
    }

    /**
     * Clone the current object. 
     *
     */ 

    public Object clone()
    {
	try {
	    return super.clone(); 
	}
	catch (CloneNotSupportedException e){
	    // Can't happen, or so the java programming book says
	    throw new InternalError(e.toString()); 
	}
    }

    public ClusterI elAt(int i){
	return (ClusterI) clusters[i]; 
    }
    
    public int size(){
	return clusters.length; 
    }
    
    public void add(ClusterI e){
	// Do nothing. 
    }

    public StreamAttValI matchAll(StreamI si, StreamEventsI sei){
        int numAtts = clusters.length; 
        // System.out.println("matchAll called"); 
        StreamAttVal sav = new StreamAttVal(numAtts); 
        for(int j=0; j < numAtts; j++){
            sav.setAtt(j, clusters[j].findMatch(si, sei)); 
        }
        // System.out.println("SAV = " + sav); 
        return sav; 
    }

}

class KMCluster implements ClusterI {
    // Ok. Each cluster consists of an eventVec 
    // which are all the objects that belong to this cluster.
    
    String myName = "unnamed-kmeans"; 
    EventVec myEvents = new EventVec(); 
    EventDescI edi; 
    Event centroid; 
    int pepIndex; 
    boolean useCentroid; 
    float[] sds; 

 

    KMCluster(EventDescI edi, int pepIndex, boolean useCentroid, float[] sds){
	this.edi = edi; 
	this.useCentroid = useCentroid; 
	this.pepIndex = pepIndex; 
	this.sds = sds; 
    }

    /**
     * Clone the current object. 
     *
     */ 
    
    public Object clone()
    {
	try {
	    return super.clone(); 
	}
	catch (CloneNotSupportedException e){
	    // Can't happen, or so the java programming book says
	    throw new InternalError(e.toString()); 
	}
    }


    public String getName(){
        return myName;
    }

    public void setName(String name){
        myName = name; 
    }
    
    public String getDescription(){
	return "Cluster centroid is: " + centroid.toString() +"\n"; 
    }
    
    public String toString(){
	return getDescription(); 
    }

    int size(){
	return myEvents.size(); 
    }

    void addEvent(EventI e){
	myEvents.add(e); 
    }
    
    void removeEvent(EventI e){
	myEvents.remove(e); 
    }
    
    EventI elAt(int pos){
	return myEvents.elAt(pos); 
    }

    void computeMean(){
	//Well, the mean is an array of floats equal in size to the 
	//eventDesc. 
	int numParams = edi.numParams();
	int numEvents = myEvents.size(); 
        // System.out.println("NumEvents = " + numEvents); 
	float[] mean = new float[edi.numParams()]; 
	for(int i=0; i < numParams; i++){
	    mean[i] = 0; 
	}
	for(int i=0; i < numEvents; i++){
	    for(int j=0; j < numParams; j++){
                // System.out.println("MyEv = " + myEvents.elAt(i) + " i=" + i + " j=" + j);
                // System.out.println("WTF?" + myEvents.elAt(i).valOf(j));
                float temp = myEvents.elAt(i).valOf(j); 
		mean[j] += temp; 
	    }
	}
	for(int i=0; i < numParams; i++){
	    mean[i] = mean[i]/numEvents; 
	}
	// And now make an event from it. 
	centroid = new Event(mean); 
    }

    // Compute the distance between two events. 

    float eventDistance(EventI a, EventI b){
    // Ok. 
    // We can get the description of these objects. 	
	int numParams = edi.numParams(); 
	float distanceSum = 0; 
	for(int i=0; i < numParams;i++){
	    distanceSum += ((a.valOf(i)-b.valOf(i))/sds[i])*((a.valOf(i)-b.valOf(i))/sds[i]); 
	}
	return (float) Math.sqrt(distanceSum); 
    }
    
    float findClosest(EventI e){
	int numEvents = myEvents.size(); 
	float minDistance = Float.MAX_VALUE; 
	for(int i=0; i < numEvents; i++){
	    float dist = eventDistance(myEvents.elAt(i), e); 
	    if(dist < minDistance){
		minDistance = dist; 
	    }
	}
	return minDistance; 	
    }
    
    float distFromCentroid(EventI e){
	return eventDistance(centroid, e); 
    }

    public float findMatch(StreamI stream, StreamEventsI streamEvents){
	// Ok ... messy! We need to know about the pep index.  
	// Get the events of relevance to us. 
	
	// First grab our data. 
	
	EventVecI events = streamEvents.getEvents(pepIndex); 
	int numEvents = events.size(); 
	float bestEventDistance = Float.MAX_VALUE; 

	if(useCentroid){		    
	    for(int i=0; i < numEvents; i++){
		float dist = distFromCentroid(events.elAt(i)); 
		if(dist < bestEventDistance){
		    bestEventDistance = dist; 
		}
	    }
	}
	else {
	   for(int i=0; i < numEvents; i++){
		float dist = findClosest(events.elAt(i)); 
		if(dist < bestEventDistance){
		    bestEventDistance = dist; 
		}
	    } 
	}
	return bestEventDistance; 
    }

}

public class KMeans implements ClusterAlgI { 

    
    private String baseName = "kmeans";
    private String description = "Implements a k-means clustering algorithm";
    private EventDescVecI edvi = null; 
    private DomDesc domDesc = null;
    private int pepIndex = 0; 
    private boolean ignoreClasses = false; 
    private boolean autoNumClusters = true; 
    private int numClusters = 0; 
    private int classToCluster = 0; 
    private boolean orderedAllocate = true; 
    private boolean useCentroid = true; 
    private float[] sds;
    //If true, use the centroid of the cluster for deciding reclustering.
    //If false, use the closest instance, not distance to centroid. 
    
    
    /**
     * Name of this clustering algorithm. 
     */ 
    
    public String name(){
	return baseName;
    }
    
    /**
     * Clone the current object. 
     *
     */ 
    
    public Object clone()
    {
	try {
	    return super.clone(); 
	}
	catch (CloneNotSupportedException e){
	    // Can't happen, or so the java programming book says
	    throw new InternalError(e.toString()); 
	}
    }
    
    public void setDomDesc(DomDesc dd){
	domDesc = dd; 
    }
    
    /**
     * Set the description of the incoming Class Stream Events Vector
     * Note that we need this first ... for the parsing of values,
     * before we do any actual processing. I expect that the
     * ClusterAlgMgr should have a copy of it and passes it through in
     * the constructor, pretty much like the Domain description for the 
     * GlobalExtrMgr
     */

    public void setEventDescVec(EventDescVecI events){
	edvi = events; 
    }
    
     /** 
     * Provides a description of the clustering algorithm.

     * This description explains what the basic idea of the clustering
     * algorihtm is (i.e. the sort of shapes it tried to find). It
     * should also explain any potential configuration options that
     * may be used to configure the object, using the configure
     * option.
     * 
     * @return The description of this class.  
     */
    
    public String description(){
	return description; 
    }

    /**
     * Configures this instance so that parameter <i>p</i> has
     * value <i>v</i>. 
     *
     * @param p the parameter to set.