MOA 12.03
Real Time Analytics for Data Streams
RandomRBFGeneratorEvents.java
Go to the documentation of this file.
00001 
00029 package moa.streams.clustering;
00030 
00031 import java.util.ArrayList;
00032 import java.util.Arrays;
00033 import java.util.Enumeration;
00034 import java.util.LinkedList;
00035 import java.util.Random;
00036 import java.util.Vector;
00037 import moa.cluster.Clustering;
00038 import moa.cluster.SphereCluster;
00039 import moa.core.AutoExpandVector;
00040 import moa.core.InstancesHeader;
00041 import moa.core.ObjectRepository;
00042 import moa.gui.visualization.DataPoint;
00043 import moa.options.FlagOption;
00044 import moa.options.FloatOption;
00045 import moa.options.IntOption;
00046 import moa.streams.InstanceStream;
00047 import moa.tasks.TaskMonitor;
00048 import weka.core.Attribute;
00049 import weka.core.DenseInstance;
00050 import weka.core.FastVector;
00051 import weka.core.Instance;
00052 import weka.core.Instances;
00053 
00054 
00055 public class RandomRBFGeneratorEvents extends ClusteringStream {
00056     private transient Vector listeners;
00057 
00058     private static final long serialVersionUID = 1L;
00059 
00060     public IntOption modelRandomSeedOption = new IntOption("modelRandomSeed",
00061                     'm', "Seed for random generation of model.", 1);
00062 
00063     public IntOption instanceRandomSeedOption = new IntOption(
00064                     "instanceRandomSeed", 'i',
00065                     "Seed for random generation of instances.", 5);
00066 
00067     public IntOption numClusterOption = new IntOption("numCluster", 'K',
00068                     "The average number of centroids in the model.", 5, 1, Integer.MAX_VALUE);
00069 
00070     public IntOption numClusterRangeOption = new IntOption("numClusterRange", 'k',
00071                     "Deviation of the number of centroids in the model.", 3, 0, Integer.MAX_VALUE);
00072 
00073     public FloatOption kernelRadiiOption = new FloatOption("kernelRadius", 'R',
00074                     "The average radii of the centroids in the model.", 0.07, 0, 1);
00075 
00076     public FloatOption kernelRadiiRangeOption = new FloatOption("kernelRadiusRange", 'r',
00077                     "Deviation of average radii of the centroids in the model.", 0, 0, 1);
00078 
00079     public FloatOption densityRangeOption = new FloatOption("densityRange", 'd',
00080                     "Offset of the average weight a cluster has. Value of 0 means all cluster " +
00081                     "contain the same amount of points.", 0, 0, 1);
00082 
00083     public IntOption speedOption = new IntOption("speed", 'V',
00084                     "Kernels move a predefined distance of 0.01 every X points", 500, 1, Integer.MAX_VALUE);
00085 
00086     public IntOption speedRangeOption = new IntOption("speedRange", 'v',
00087                     "Speed/Velocity point offset", 0, 0, Integer.MAX_VALUE);
00088 
00089     public FloatOption noiseLevelOption = new FloatOption("noiseLevel", 'N',
00090                     "Noise level", 0.1, 0, 1);
00091 
00092     public FlagOption noiseInClusterOption = new FlagOption("noiseInCluster", 'n',
00093                     "Allow noise to be placed within a cluster");
00094 
00095     public IntOption eventFrequencyOption = new IntOption("eventFrequency", 'E',
00096                     "Event frequency. Enable at least one of the events below and set numClusterRange!", 30000, 0, Integer.MAX_VALUE);
00097 
00098     public FlagOption eventMergeSplitOption = new FlagOption("eventMergeSplitOption", 'M',
00099                     "Enable merging and splitting of clusters. Set eventFrequency and numClusterRange!");
00100 
00101     public FlagOption eventDeleteCreateOption = new FlagOption("eventDeleteCreate", 'C',
00102                                 "Enable emering and disapperaing of clusters. Set eventFrequency and numClusterRange!");
00103 
00104     
00105     private double merge_threshold = 0.7;
00106     private int kernelMovePointFrequency = 10;
00107     private double maxDistanceMoveThresholdByStep = 0.01;
00108     private int maxOverlapFitRuns = 50;
00109     private double eventFrequencyRange = 0;
00110 
00111     private boolean debug = false;
00112 
00113     private AutoExpandVector<GeneratorCluster> kernels;
00114     protected Random instanceRandom;
00115     protected InstancesHeader streamHeader;
00116     private int numGeneratedInstances;
00117     private int numActiveKernels;
00118     private int nextEventCounter;
00119     private int nextEventChoice = -1;
00120     private int clusterIdCounter;
00121     private GeneratorCluster mergeClusterA;
00122     private GeneratorCluster mergeClusterB;
00123     private boolean mergeKernelsOverlapping = false;
00124 
00125 
00126 
00127     private class GeneratorCluster{
00128         //TODO: points is redundant to microclusterpoints, we need to come 
00129         //up with a good strategy that microclusters get updated and 
00130         //rebuild if needed. Idea: Sort microclusterpoints by timestamp and let 
00131         // microclusterdecay hold the timestamp for when the last point in a 
00132         //microcluster gets kicked, then we rebuild... or maybe not... could be
00133         //same as searching for point to be kicked. more likely is we rebuild 
00134         //fewer times then insert.
00135         
00136         SphereCluster generator;
00137         int kill = -1;
00138         boolean merging = false;
00139         double[] moveVector;
00140         int totalMovementSteps;
00141         int currentMovementSteps;
00142         boolean isSplitting = false;
00143 
00144         LinkedList<DataPoint> points = new LinkedList<DataPoint>();
00145         ArrayList<SphereCluster> microClusters = new ArrayList<SphereCluster>();
00146         ArrayList<ArrayList<DataPoint>> microClustersPoints = new ArrayList();
00147         ArrayList<Integer> microClustersDecay = new ArrayList();
00148 
00149 
00150         public GeneratorCluster(int label) {
00151             boolean outofbounds = true;
00152             int tryCounter = 0;
00153             while(outofbounds && tryCounter < maxOverlapFitRuns){
00154                 tryCounter++;
00155                 outofbounds = false;
00156                 double[] center = new double [numAttsOption.getValue()];
00157                 double radius = kernelRadiiOption.getValue()+(instanceRandom.nextBoolean()?-1:1)*kernelRadiiRangeOption.getValue()*instanceRandom.nextDouble();
00158                 while(radius <= 0){
00159                     radius = kernelRadiiOption.getValue()+(instanceRandom.nextBoolean()?-1:1)*kernelRadiiRangeOption.getValue()*instanceRandom.nextDouble();
00160                 }
00161                 for (int j = 0; j < numAttsOption.getValue(); j++) {
00162                      center[j] = instanceRandom.nextDouble();
00163                      if(center[j]- radius < 0 || center[j] + radius > 1){
00164                         outofbounds = true;
00165                         break;
00166                      }
00167                 }
00168                 generator = new SphereCluster(center, radius);
00169             }
00170             if(tryCounter < maxOverlapFitRuns){
00171                 generator.setId(label);
00172                 double avgWeight = 1.0/numClusterOption.getValue();
00173                 double weight = avgWeight + (instanceRandom.nextBoolean()?-1:1)*avgWeight*densityRangeOption.getValue()*instanceRandom.nextDouble();
00174                 generator.setWeight(weight);
00175                 setDesitnation(null);
00176             }
00177             else{
00178                 generator = null;
00179                 kill = 0;
00180                 System.out.println("Tried "+maxOverlapFitRuns+" times to create kernel. Reduce average radii." );
00181             }
00182         }
00183 
00184         public GeneratorCluster(int label, SphereCluster cluster) {
00185             this.generator = cluster;
00186             cluster.setId(label);
00187             setDesitnation(null);
00188         }
00189 
00190         public int getWorkID(){
00191             for(int c = 0; c < kernels.size(); c++){
00192                 if(kernels.get(c).equals(this))
00193                     return c;
00194             }
00195             return -1;
00196         }
00197 
00198         private void updateKernel(){
00199             if(kill == 0){
00200                 kernels.remove(this);
00201             }
00202             if(kill > 0){
00203                 kill--;
00204             }
00205             //we could be lot more precise if we would keep track of timestamps of points
00206             //then we could remove all old points and rebuild the cluster on up to date point base
00207             //BUT worse the effort??? so far we just want to avoid overlap with this, so its more
00208             //konservative as needed. Only needs to change when we need a thighter representation
00209             for (int m = 0; m < microClusters.size(); m++) {
00210                 if(numGeneratedInstances-microClustersDecay.get(m) > decayHorizonOption.getValue()){
00211                     microClusters.remove(m);
00212                     microClustersPoints.remove(m);
00213                     microClustersDecay.remove(m);
00214                 }
00215             }
00216 
00217             if(!points.isEmpty() && numGeneratedInstances-points.getFirst().getTimestamp() >= decayHorizonOption.getValue()){
00218 //                if(debug)
00219 //                    System.out.println("Cleaning up macro cluster "+generator.getId());
00220                 points.removeFirst();
00221             }
00222 
00223         }
00224 
00225         private void addInstance(Instance instance){
00226             DataPoint point = new DataPoint(instance, numGeneratedInstances);
00227             points.add(point);
00228             
00229             int minMicroIndex = -1;
00230             double minHullDist = Double.MAX_VALUE;
00231             boolean inserted = false;
00232             //we favour more recently build clusters so we can remove earlier cluster sooner
00233             for (int m = microClusters.size()-1; m >=0 ; m--) {
00234                 SphereCluster micro = microClusters.get(m);
00235                 double hulldist = micro.getCenterDistance(point)-micro.getRadius();
00236                 //point fits into existing cluster
00237                 if(hulldist <= 0){
00238                     microClustersPoints.get(m).add(point);
00239                     microClustersDecay.set(m, numGeneratedInstances);
00240                     inserted = true;
00241                     break;
00242                 }
00243                 //if not, check if its at least the closest cluster
00244                 else{
00245                     if(hulldist < minHullDist){
00246                         minMicroIndex = m;
00247                         minHullDist = hulldist;
00248                     }
00249                 }
00250             }
00251             //Reseting index choice for alternative cluster building
00252             int alt = 1;
00253             if(alt == 1)
00254                 minMicroIndex = -1;
00255             if(!inserted){
00256                 //add to closest cluster and expand cluster
00257                 if(minMicroIndex!=-1){
00258                     microClustersPoints.get(minMicroIndex).add(point);
00259                     //we should keep the miniball instances and just check in
00260                     //new points instead of rebuilding the whole thing
00261                     SphereCluster s = new SphereCluster(microClustersPoints.get(minMicroIndex),numAttsOption.getValue());
00262                     //check if current microcluster is bigger then generating cluster
00263                     if(s.getRadius() > generator.getRadius()){
00264                         //remove previously added point
00265                         microClustersPoints.get(minMicroIndex).remove(microClustersPoints.get(minMicroIndex).size()-1);
00266                         minMicroIndex = -1;
00267                     }
00268                     else{
00269                         microClusters.set(minMicroIndex, s);
00270                         microClustersDecay.set(minMicroIndex, numGeneratedInstances);
00271                     }
00272                 }
00273                 //minMicroIndex might have been reset above
00274                 //create new micro cluster
00275                 if(minMicroIndex == -1){
00276                     ArrayList<DataPoint> microPoints = new ArrayList<DataPoint>();
00277                     microPoints.add(point);
00278                     SphereCluster s;
00279                     if(alt == 0)
00280                         s = new SphereCluster(microPoints,numAttsOption.getValue());
00281                     else
00282                         s = new SphereCluster(generator.getCenter(),generator.getRadius(),1);
00283 
00284                     microClusters.add(s);
00285                     microClustersPoints.add(microPoints);
00286                     microClustersDecay.add(numGeneratedInstances);
00287                     int id = 0;
00288                     while(id < kernels.size()){
00289                         if(kernels.get(id) == this)
00290                             break;
00291                         id++;
00292                     }
00293                     s.setGroundTruth(id);
00294                 }
00295             }
00296 
00297         }
00298 
00299 
00300         private void move(){
00301             if(currentMovementSteps < totalMovementSteps){
00302                 currentMovementSteps++;
00303                 if( moveVector == null){
00304                     return;
00305                 }
00306                 else{
00307                     double[] center = generator.getCenter();
00308                     boolean outofbounds = true;
00309                     while(outofbounds){
00310                         double radius = generator.getRadius();
00311                         outofbounds = false;
00312                         center = generator.getCenter();
00313                         for ( int d = 0; d < center.length; d++ ) {
00314                             center[d]+= moveVector[d];
00315                             if(center[d]- radius < 0 || center[d] + radius > 1){
00316                                 outofbounds = true;
00317                                 setDesitnation(null);
00318                                 break;
00319                             }
00320                         }
00321                     }
00322                     generator.setCenter(center);
00323                 }
00324             }
00325             else{
00326                 if(!merging){
00327                     setDesitnation(null);
00328                     isSplitting = false;
00329                 }
00330             }
00331         }
00332 
00333         void setDesitnation(double[] destination){
00334 
00335             if(destination == null){
00336                 destination = new double [numAttsOption.getValue()];
00337                 for (int j = 0; j < numAttsOption.getValue(); j++) {
00338                      destination[j] = instanceRandom.nextDouble();
00339                 }
00340             }
00341             double[] center = generator.getCenter();
00342             int dim = center.length;
00343 
00344             double[] v = new double[dim];
00345 
00346             for ( int d = 0; d < dim; d++ ) {
00347                 v[d]=destination[d]-center[d];
00348             }
00349             setMoveVector(v);
00350         }
00351 
00352         void setMoveVector(double[] vector){
00353                 //we are ignoring the steps, otherwise we have to change 
00354                 //speed of the kernels, do we want that?
00355             moveVector = vector;
00356             int speedInPoints  = speedOption.getValue();
00357             if(speedRangeOption.getValue() > 0)
00358                     speedInPoints +=(instanceRandom.nextBoolean()?-1:1)*instanceRandom.nextInt(speedRangeOption.getValue());
00359             if(speedInPoints  < 1) speedInPoints  = speedOption.getValue();
00360 
00361 
00362             double length = 0;
00363             for ( int d = 0; d < moveVector.length; d++ ) {
00364                 length+=Math.pow(vector[d],2);
00365             }
00366             length = Math.sqrt(length);
00367 
00368             totalMovementSteps = (int)(length/(maxDistanceMoveThresholdByStep*kernelMovePointFrequency)*speedInPoints);
00369             for ( int d = 0; d < moveVector.length; d++ ) {
00370                 moveVector[d]/=(double)totalMovementSteps;
00371             }
00372 
00373 
00374             currentMovementSteps = 0;
00375 //            if(debug){
00376 //                System.out.println("Setting new direction for C"+generator.getId()+": distance "
00377 //                        +length+" in "+totalMovementSteps+" steps");
00378 //            }
00379         }
00380 
00381         private String tryMerging(GeneratorCluster merge){
00382            String message = "";
00383            double overlapDegree = generator.overlapRadiusDegree(merge.generator);
00384            if(overlapDegree > merge_threshold){
00385                 SphereCluster mcluster = merge.generator;
00386                 double radius = Math.max(generator.getRadius(), mcluster.getRadius());
00387                 generator.combine(mcluster);
00388 
00389 //                //adjust radius, get bigger and bigger with high dim data
00390                 generator.setRadius(radius);
00391 //                double[] center = generator.getCenter();
00392 //                double[] mcenter = mcluster.getCenter();
00393 //                double weight = generator.getWeight();
00394 //                double mweight = generator.getWeight();
00398 //                generator.setWeight(weight + mweight);
00399                 message  = "Clusters merging: "+mergeClusterB.generator.getId()+" into "+mergeClusterA.generator.getId();
00400 
00401                 //clean up and restet merging stuff
00402                 //mark kernel so it gets killed when it doesn't contain any more instances
00403                 merge.kill = decayHorizonOption.getValue();
00404                 //set weight to 0 so no new instances will be created in the cluster
00405                 mcluster.setWeight(0.0);
00406                 normalizeWeights();
00407                 numActiveKernels--;
00408                 mergeClusterB = mergeClusterA = null;
00409                 merging = false;
00410                 mergeKernelsOverlapping = false;
00411             }
00412            else{
00413                    if(overlapDegree > 0 && !mergeKernelsOverlapping){
00414                            mergeKernelsOverlapping = true;
00415                            message = "Merge overlapping started";
00416                    }
00417            }
00418            return message;
00419         }
00420 
00421         private String splitKernel(){
00422             isSplitting = true;
00423             //todo radius range
00424             double radius = kernelRadiiOption.getValue();
00425             double avgWeight = 1.0/numClusterOption.getValue();
00426             double weight = avgWeight + avgWeight*densityRangeOption.getValue()*instanceRandom.nextDouble();
00427             SphereCluster spcluster = null;
00428 
00429             double[] center = generator.getCenter();
00430             spcluster = new SphereCluster(center, radius, weight);
00431 
00432             if(spcluster !=null){
00433                 GeneratorCluster gc = new GeneratorCluster(clusterIdCounter++, spcluster);
00434                 gc.isSplitting = true;
00435                 kernels.add(gc);
00436                 normalizeWeights();
00437                 numActiveKernels++;
00438                 return "Split from Kernel "+generator.getId();
00439             }
00440             else{
00441                 System.out.println("Tried to split new kernel from C"+generator.getId()+
00442                         ". Not enough room for new cluster, decrease average radii, number of clusters or enable overlap.");
00443                 return "";
00444             }
00445         }
00446         
00447         private String fadeOut(){
00448                 kill = decayHorizonOption.getValue();
00449                 generator.setWeight(0.0);
00450                 numActiveKernels--;
00451                 normalizeWeights();
00452                 return "Fading out C"+generator.getId();
00453         }
00454         
00455         
00456     }
00457 
00458     public RandomRBFGeneratorEvents() {
00459         noiseInClusterOption.set();
00460 //        eventDeleteCreateOption.set();
00461 //        eventMergeSplitOption.set();
00462     }
00463 
00464     public InstancesHeader getHeader() {
00465             return streamHeader;
00466     }
00467 
00468     public long estimatedRemainingInstances() {
00469             return -1;
00470     }
00471 
00472     public boolean hasMoreInstances() {
00473             return true;
00474     }
00475 
00476     public boolean isRestartable() {
00477             return true;
00478     }
00479 
00480     @Override
00481     public void prepareForUseImpl(TaskMonitor monitor, ObjectRepository repository) {
00482         monitor.setCurrentActivity("Preparing random RBF...", -1.0);
00483         generateHeader();
00484         restart();
00485     }
00486 
00487     public void restart() {
00488             instanceRandom = new Random(instanceRandomSeedOption.getValue());
00489             nextEventCounter = eventFrequencyOption.getValue();
00490             nextEventChoice = getNextEvent();
00491             numActiveKernels = 0;
00492             numGeneratedInstances = 0;
00493             clusterIdCounter = 0;
00494             mergeClusterA = mergeClusterB = null;
00495             kernels = new AutoExpandVector<GeneratorCluster>();
00496 
00497             initKernels();
00498     }
00499         
00500     protected void generateHeader() {
00501             FastVector attributes = new FastVector();
00502             for (int i = 0; i < this.numAttsOption.getValue(); i++) {
00503                     attributes.addElement(new Attribute("att" + (i + 1)));
00504             }
00505             FastVector classLabels = new FastVector();
00506             for (int i = 0; i < this.numClusterOption.getValue(); i++) {
00507                     classLabels.addElement("class" + (i + 1));
00508             }
00509             attributes.addElement(new Attribute("class", classLabels));
00510             streamHeader = new InstancesHeader(new Instances(
00511                             getCLICreationString(InstanceStream.class), attributes, 0));
00512             streamHeader.setClassIndex(streamHeader.numAttributes()-1);
00513     }
00514 
00515         
00516     protected void initKernels() {
00517         for (int i = 0; i < numClusterOption.getValue(); i++) {
00518             kernels.add(new GeneratorCluster(clusterIdCounter));
00519             numActiveKernels++;
00520             clusterIdCounter++;
00521         }
00522         normalizeWeights();
00523     }
00524 
00525     public Instance nextInstance() {
00526         numGeneratedInstances++;
00527         eventScheduler();
00528 
00529         //make room for the classlabel
00530         double[] values_new = new double [numAttsOption.getValue()+1];
00531         double[] values = null;
00532         int clusterChoice = -1;
00533 
00534         if(instanceRandom.nextDouble() > noiseLevelOption.getValue()){
00535             clusterChoice = chooseWeightedElement();
00536             values = kernels.get(clusterChoice).generator.sample(instanceRandom).toDoubleArray();
00537         }
00538         else{
00539             //get ranodm noise point
00540             values = getNoisePoint();
00541         }
00542 
00543         if(Double.isNaN(values[0])){
00544             System.out.println("Instance corrupted:"+numGeneratedInstances);
00545         }
00546         System.arraycopy(values, 0, values_new, 0, values.length);
00547 
00548         Instance inst = new DenseInstance(1.0, values_new);
00549         inst.setDataset(getHeader());
00550         if(clusterChoice == -1){
00551             inst.setClassValue(-1);
00552         }
00553         else{
00554             inst.setClassValue(kernels.get(clusterChoice).generator.getId());
00555             //Do we need micro cluster representation if have overlapping clusters?
00556             //if(!overlappingOption.isSet())
00557                 kernels.get(clusterChoice).addInstance(inst);
00558         }
00559 //        System.out.println(numGeneratedInstances+": Overlap is"+updateOverlaps());
00560         
00561         return inst;
00562     }
00563 
00564 
00565     public Clustering getGeneratingClusters(){
00566         Clustering clustering = new Clustering();
00567         for (int c = 0; c < kernels.size(); c++) {
00568             clustering.add(kernels.get(c).generator);
00569         }
00570         return clustering;
00571     }
00572 
00573     public Clustering getMicroClustering(){
00574         Clustering clustering = new Clustering();
00575         int id = 0;
00576 
00577             for (int c = 0; c < kernels.size(); c++) {
00578                 for (int m = 0; m < kernels.get(c).microClusters.size(); m++) {
00579                     kernels.get(c).microClusters.get(m).setId(id);
00580                     kernels.get(c).microClusters.get(m).setGroundTruth(kernels.get(c).generator.getId());
00581                     clustering.add(kernels.get(c).microClusters.get(m));
00582                     id++;
00583                 }
00584             }
00585 
00586         //System.out.println("numMicroKernels "+clustering.size());
00587         return clustering;
00588     }
00589 
00590 /**************************** EVENTS ******************************************/
00591     private void eventScheduler(){
00592 
00593         for ( int i = 0; i < kernels.size(); i++ ) {
00594             kernels.get(i).updateKernel();
00595         }
00596         
00597         nextEventCounter--;
00598         //only move kernels every 10 points, performance reasons????
00599         //should this be randomized as well???
00600         if(nextEventCounter%kernelMovePointFrequency == 0){
00601             //move kernels
00602             for ( int i = 0; i < kernels.size(); i++ ) {
00603                 kernels.get(i).move();
00604                 //overlapControl();
00605             }
00606         }
00607 
00608 
00609         if(eventFrequencyOption.getValue() == 0){
00610             return;
00611         }
00612 
00613         String type ="";
00614         String message ="";
00615         boolean eventFinished = false;
00616         switch(nextEventChoice){
00617             case 0:
00618                 if(numActiveKernels > 1 && numActiveKernels > numClusterOption.getValue() - numClusterRangeOption.getValue()){
00619                     message = mergeKernels(nextEventCounter);
00620                     type = "Merge";
00621                 }
00622                 if(mergeClusterA==null && mergeClusterB==null && message.startsWith("Clusters merging")){
00623                         eventFinished = true;
00624                 }                
00625             break;
00626             case 1:
00627                 if(nextEventCounter<=0){
00628                     if(numActiveKernels < numClusterOption.getValue() + numClusterRangeOption.getValue()){
00629                         type = "Split";
00630                         message = splitKernel();
00631                     }
00632                     eventFinished = true;
00633                 }
00634             break;
00635             case 2:
00636                 if(nextEventCounter<=0){
00637                         if(numActiveKernels > 1 && numActiveKernels > numClusterOption.getValue() - numClusterRangeOption.getValue()){
00638                         message = fadeOut();
00639                         type = "Delete";
00640                     }
00641                         eventFinished = true;
00642                 }
00643             break;
00644             case 3:
00645                 if(nextEventCounter<=0){
00646                         if(numActiveKernels < numClusterOption.getValue() + numClusterRangeOption.getValue()){
00647                             message = fadeIn();
00648                             type = "Create";
00649                         }
00650                         eventFinished = true;           
00651                 }
00652             break;
00653 
00654         }
00655         if (eventFinished){
00656                 nextEventCounter = (int)(eventFrequencyOption.getValue()+(instanceRandom.nextBoolean()?-1:1)*eventFrequencyOption.getValue()*eventFrequencyRange*instanceRandom.nextDouble());
00657                 nextEventChoice = getNextEvent();
00658                 //System.out.println("Next event choice: "+nextEventChoice);
00659         }
00660         if(!message.isEmpty()){
00661                 message+=" (numKernels = "+numActiveKernels+" at "+numGeneratedInstances+")";
00662                 if(!type.equals("Merge") || message.startsWith("Clusters merging"))
00663                         fireClusterChange(numGeneratedInstances, type, message);
00664         }
00665     }
00666     
00667     private int getNextEvent() {
00668         int choice = -1;
00669         boolean lowerLimit = numActiveKernels <= numClusterOption.getValue() - numClusterRangeOption.getValue();
00670         boolean upperLimit = numActiveKernels >= numClusterOption.getValue() + numClusterRangeOption.getValue();
00671 
00672         if(!lowerLimit || !upperLimit){
00673                 int mode = -1;
00674                 if(eventDeleteCreateOption.isSet() && eventMergeSplitOption.isSet()){
00675                         mode = instanceRandom.nextInt(2);
00676                 }
00677                 
00678                         if(mode==0 || (mode==-1 && eventMergeSplitOption.isSet())){
00679                                 //have we reached a limit? if not free choice
00680                                 if(!lowerLimit && !upperLimit) 
00681                                         choice = instanceRandom.nextInt(2);
00682                                 else
00683                                         //we have a limit. if lower limit, choose split
00684                                         if(lowerLimit)
00685                                                 choice = 1;
00686                                         //otherwise we reached upper level, choose merge
00687                                         else
00688                                                 choice = 0;
00689                         }
00690                         
00691                         if(mode==1 || (mode==-1 && eventDeleteCreateOption.isSet())){
00692                                 //have we reached a limit? if not free choice
00693                                 if(!lowerLimit && !upperLimit) 
00694                                         choice = instanceRandom.nextInt(2)+2;
00695                                 else
00696                                         //we have a limit. if lower limit, choose create
00697                                         if(lowerLimit)
00698                                                 choice = 3;
00699                                         //otherwise we reached upper level, choose delete
00700                                         else
00701                                                 choice = 2;
00702                         }
00703         }
00704 
00705         
00706         return choice;
00707     }
00708 
00709         private String fadeOut(){
00710             int id = instanceRandom.nextInt(kernels.size());
00711             while(kernels.get(id).kill!=-1)
00712                 id = instanceRandom.nextInt(kernels.size());
00713         
00714             String message = kernels.get(id).fadeOut();
00715             return message;
00716     }
00717     
00718     private String fadeIn(){
00719                 GeneratorCluster gc = new GeneratorCluster(clusterIdCounter++);
00720                 kernels.add(gc);
00721                 numActiveKernels++;
00722                 normalizeWeights();
00723         return "Creating new cluster";
00724     }
00725     
00726     
00727     private String changeWeight(boolean increase){
00728         double changeRate = 0.1;
00729         int id = instanceRandom.nextInt(kernels.size());
00730         while(kernels.get(id).kill!=-1)
00731             id = instanceRandom.nextInt(kernels.size());
00732 
00733         int sign = 1;
00734         if(!increase)
00735             sign = -1;
00736         double weight_old = kernels.get(id).generator.getWeight();
00737         double delta = sign*numActiveKernels*instanceRandom.nextDouble()*changeRate;
00738         kernels.get(id).generator.setWeight(weight_old+delta);
00739 
00740         normalizeWeights();
00741 
00742         String message;
00743         if(increase)
00744             message = "Increase ";
00745         else
00746             message = "Decrease ";
00747         message+=" weight on Cluster "+id+" from "+weight_old+" to "+(weight_old+delta);
00748         return message;
00749 
00750 
00751     }
00752 
00753     private String changeRadius(boolean increase){
00754         double maxChangeRate = 0.1;
00755         int id = instanceRandom.nextInt(kernels.size());
00756         while(kernels.get(id).kill!=-1)
00757             id = instanceRandom.nextInt(kernels.size());
00758 
00759         int sign = 1;
00760         if(!increase)
00761             sign = -1;
00762 
00763         double r_old = kernels.get(id).generator.getRadius();
00764         double r_new =r_old+sign*r_old*instanceRandom.nextDouble()*maxChangeRate;
00765         if(r_new >= 0.5) return "Radius to big";
00766         kernels.get(id).generator.setRadius(r_new);
00767         
00768         String message;
00769         if(increase)
00770             message = "Increase ";
00771         else
00772             message = "Decrease ";
00773         message+=" radius on Cluster "+id+" from "+r_old+" to "+r_new;
00774         return message;
00775     }
00776 
00777     private String splitKernel(){
00778         int id = instanceRandom.nextInt(kernels.size());
00779         while(kernels.get(id).kill!=-1)
00780             id = instanceRandom.nextInt(kernels.size());
00781 
00782         String message = kernels.get(id).splitKernel();
00783 
00784         return message;
00785         //TODO generateHeader(); does that do anything? Ref on dataset in instances?
00786     }
00787 
00788     private String mergeKernels(int steps){
00789         if(numActiveKernels >1 && ((mergeClusterA == null && mergeClusterB == null))){
00790 
00791                 //choose clusters to merge
00792                 double diseredDist = steps / speedOption.getValue() * maxDistanceMoveThresholdByStep;
00793                 double minDist = Double.MAX_VALUE;
00794 //              System.out.println("DisredDist:"+(2*diseredDist));
00795                 for(int i = 0; i < kernels.size(); i++){
00796                         for(int j = 0; j < i; j++){
00797                         if(kernels.get(i).kill!=-1 || kernels.get(j).kill!=-1){
00798                                 continue;
00799                         }
00800                         else{
00801                                 double kernelDist = kernels.get(i).generator.getCenterDistance(kernels.get(j).generator);
00802                                 double d = kernelDist-2*diseredDist;
00803 //                              System.out.println("Dist:"+i+" / "+j+" "+d);
00804                                 if(Math.abs(d) < minDist && 
00805                                                 (minDist != Double.MAX_VALUE || d>0 || Math.abs(d) < 0.001)){
00806                                         minDist = Math.abs(d);
00807                                         mergeClusterA = kernels.get(i);
00808                                         mergeClusterB = kernels.get(j);
00809                                 }
00810                         }
00811                         }
00812                 }
00813                 
00814                 if(mergeClusterA!=null && mergeClusterB!=null){
00815                         double[] merge_point = mergeClusterA.generator.getCenter();
00816                         double[] v = mergeClusterA.generator.getDistanceVector(mergeClusterB.generator);
00817                         for (int i = 0; i < v.length; i++) {
00818                                 merge_point[i]= merge_point[i]+v[i]*0.5;
00819                                 }
00820         
00821                     mergeClusterA.merging = true;
00822                     mergeClusterB.merging = true;
00823                     mergeClusterA.setDesitnation(merge_point);
00824                     mergeClusterB.setDesitnation(merge_point);
00825                     
00826                     if(debug){
00827                         System.out.println("Center1"+Arrays.toString(mergeClusterA.generator.getCenter()));
00828                                 System.out.println("Center2"+Arrays.toString(mergeClusterB.generator.getCenter()));
00829                             System.out.println("Vector"+Arrays.toString(v));            
00830                         
00831                         System.out.println("Try to merge cluster "+mergeClusterA.generator.getId()+
00832                                 " into "+mergeClusterB.generator.getId()+
00833                                 " at "+Arrays.toString(merge_point)+
00834                                 " time "+numGeneratedInstances);
00835                     }
00836                     return "Init merge";
00837                 }
00838         }
00839 
00840         if(mergeClusterA != null && mergeClusterB != null){
00841 
00842             //movekernels will move the kernels close to each other,
00843             //we just need to check and merge here if they are close enough
00844             return mergeClusterA.tryMerging(mergeClusterB);
00845         }
00846 
00847         return "";
00848     }
00849 
00850 
00851 
00852 
00853 /************************* TOOLS **************************************/
00854 
00855     public void getDescription(StringBuilder sb, int indent) {
00856 
00857     }
00858 
00859     private double[] getNoisePoint(){
00860         double [] sample = new double [numAttsOption.getValue()];
00861         boolean incluster = true;
00862         int counter = 20;
00863         while(incluster){
00864             for (int j = 0; j < numAttsOption.getValue(); j++) {
00865                  sample[j] = instanceRandom.nextDouble();
00866             }
00867             incluster = false;
00868             if(!noiseInClusterOption.isSet() && counter > 0){
00869                 counter--;
00870                 for(int c = 0; c < kernels.size(); c++){
00871                     for(int m = 0; m < kernels.get(c).microClusters.size(); m++){
00872                         Instance inst = new DenseInstance(1, sample);
00873                         if(kernels.get(c).microClusters.get(m).getInclusionProbability(inst) > 0){
00874                             incluster = true;
00875                             break;
00876                         }
00877                     }
00878                     if(incluster)
00879                         break;
00880                 }
00881             }
00882         }
00883 
00884 //        double [] sample = new double [numAttsOption.getValue()];
00885 //        for (int j = 0; j < numAttsOption.getValue(); j++) {
00886 //             sample[j] = instanceRandom.nextDouble();
00887 //        }
00888              
00889         return sample;
00890     }
00891 
00892      private int chooseWeightedElement() {
00893         double r = instanceRandom.nextDouble();
00894 
00895         // Determine index of choosen element
00896         int i = 0;
00897         while (r > 0.0) {
00898             r -= kernels.get(i).generator.getWeight();
00899             i++;
00900         }
00901         --i;    // Overcounted once
00902         //System.out.println(i);
00903         return i;
00904     }
00905 
00906     private void normalizeWeights(){
00907         double sumWeights = 0.0;
00908         for (int i = 0; i < kernels.size(); i++) {
00909             sumWeights+=kernels.get(i).generator.getWeight();
00910         }
00911         for (int i = 0; i < kernels.size(); i++) {
00912             kernels.get(i).generator.setWeight(kernels.get(i).generator.getWeight()/sumWeights);
00913         }
00914     }
00915 
00916 
00917 
00918  /*************** EVENT Listener *********************/
00919  // should go into the superclass of the generator, create new one for cluster streams?
00920   
00922   synchronized public void addClusterChangeListener(ClusterEventListener l) {
00923     if (listeners == null)
00924       listeners = new Vector();
00925     listeners.addElement(l);
00926   }
00927 
00929   synchronized public void removeClusterChangeListener(ClusterEventListener l) {
00930     if (listeners == null)
00931       listeners = new Vector();
00932     listeners.removeElement(l);
00933   }
00934 
00936   protected void fireClusterChange(long timestamp, String type, String message) {
00937     // if we have no listeners, do nothing...
00938     if (listeners != null && !listeners.isEmpty()) {
00939       // create the event object to send
00940       ClusterEvent event =
00941         new ClusterEvent(this, timestamp, type , message);
00942 
00943       // make a copy of the listener list in case
00944       //   anyone adds/removes listeners
00945       Vector targets;
00946       synchronized (this) {
00947         targets = (Vector) listeners.clone();
00948       }
00949 
00950       // walk through the listener list and
00951       //   call the sunMoved method in each
00952       Enumeration e = targets.elements();
00953       while (e.hasMoreElements()) {
00954         ClusterEventListener l = (ClusterEventListener) e.nextElement();
00955         l.changeCluster(event);
00956 
00957       }
00958     }
00959   }
00960 
00961     @Override
00962     public String getPurposeString() {
00963             return "Generates a random radial basis function stream.";
00964     }
00965 
00966 
00967     public String getParameterString(){
00968         return "";
00969     }
00970 
00971 
00972 
00973 
00974 }
 All Classes Namespaces Files Functions Variables Enumerations