package jsat.clustering;

import java.util.*;
import java.util.concurrent.atomic.DoubleAdder;

import jsat.DataSet;
import jsat.exceptions.FailedToFitException;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.TrainableDistanceMetric;
import jsat.linear.vectorcollection.DefaultVectorCollection;
import jsat.linear.vectorcollection.VectorCollection;
import jsat.linear.vectorcollection.VectorCollectionUtils;
import jsat.math.OnLineStatistics;
import jsat.parameters.Parameterized;
import jsat.utils.IntSet;
import jsat.utils.concurrent.ParallelUtils;

/**
 * Provides an implementation of the FLAME clustering algorithm. The original 
 * FLAME paper does not describe all necessary details for an implementation, so 
 * results may differ between implementations. 

* FLAME is highly sensitive to the number of neighbors chosen. Increasing the * neighbors tends to reduce the number of clusters formed. *

* See: Fu, L.,&Medico, E. (2007). FLAME, a novel fuzzy clustering method * for the analysis of DNA microarray data. BMC Bioinformatics, 8(1), 3. * Retrieved from here * * @author Edward Raff */ public class FLAME extends ClustererBase implements Parameterized { private static final long serialVersionUID = 2393091020100706517L; private DistanceMetric dm; private int k; private int maxIterations; private VectorCollection> vc = new DefaultVectorCollection<>(); private double stndDevs = 2.5; private double eps = 1e-6; /** * Creates a new FLAME clustering object * @param dm the distance metric to use * @param k the number of neighbors to consider * @param maxIterations the maximum number of iterations to perform */ public FLAME(DistanceMetric dm, int k, int maxIterations) { setDistanceMetric(dm); setK(k); setMaxIterations(maxIterations); } /** * Copy constructor * @param toCopy the object to copy */ public FLAME(FLAME toCopy) { this.dm = toCopy.dm.clone(); this.maxIterations = toCopy.maxIterations; this.vc = toCopy.vc.clone(); this.k = toCopy.k; this.stndDevs = toCopy.stndDevs; this.eps = toCopy.eps; } /** * Sets the maximum number of iterations to perform. FLAME can require far * more iterations to converge than necessary to get the same hard * clustering result. * * @param maxIterations the maximum number of iterations to perform */ public void setMaxIterations(int maxIterations) { if(maxIterations < 1) throw new IllegalArgumentException("Must perform a positive number of iterations, not " + maxIterations); this.maxIterations = maxIterations; } /** * Returns the maximum number of iterations to perform * @return the maximum number of iterations to perform */ public int getMaxIterations() { return maxIterations; } /** * Sets the number of neighbors that will be considered in determining * Cluster Supporting Points and assignment contributions. * @param k the number of neighbors to consider */ public void setK(int k) { this.k = k; } /** * Returns the number of neighbors used * @return the number of neighbors used */ public int getK() { return k; } /** * Sets the convergence goal for the minimum difference in score between * rounds. Negative values are allowed to force all iterations to occur * @param eps the minimum difference in scores for convergence */ public void setEps(double eps) { if(Double.isNaN(eps)) throw new IllegalArgumentException("Eps can not be NaN"); this.eps = eps; } /** * Returns the minimum difference in scores to consider FLAME converged * @return the minimum difference in scores to consider FLAMe converged */ public double getEps() { return eps; } /** * Sets the number of standard deviations away from the mean density a * candidate outlier must be to be confirmed as an outlier. * @param stndDevs the number of standard deviations away from the mean * density an outlier must be */ public void setStndDevs(double stndDevs) { if(stndDevs < 0 || Double.isInfinite(stndDevs) || Double.isNaN(stndDevs)) throw new IllegalArgumentException("Standard Deviations must be non negative"); this.stndDevs = stndDevs; } /** * Returns the number of standard deviations away from the mean * density an outlier must be * @return the number of standard deviations away from the mean * density an outlier must be */ public double getStndDevs() { return stndDevs; } /** * Sets the distance metric to use for the nearest neighbor search * @param dm the distance metric to use */ public void setDistanceMetric(DistanceMetric dm) { this.dm = dm; } /** * Returns the distance metric to use for the nearest neighbor search * @return the distance metric to use */ public DistanceMetric getDistanceMetric() { return dm; } /** * Sets the vector collection used to accelerate the nearest * neighbor search. The nearest neighbor only needs to be done once for each * point, so the collection should be faster than the naive method when * considering both construction and search time. * * @param vc the vector collection to use */ public void setVectorCollectionFactory(VectorCollection> vc) { this.vc = vc; } @Override public int[] cluster(DataSet dataSet, boolean parallel, int[] designations) { if(k >= dataSet.getSampleSize()) throw new FailedToFitException("Number of k-neighbors (" + k + ") can not be larger than the number of datapoints (" + dataSet.getSampleSize() + ")"); final int n = dataSet.getSampleSize(); if (designations == null || designations.length < dataSet.getSampleSize()) designations = new int[n]; List> vecs = new ArrayList<>(n); for (int i = 0; i < dataSet.getSampleSize(); i++) vecs.add(new VecPaired<>(dataSet.getDataPoint(i).getNumericalValues(), i)); TrainableDistanceMetric.trainIfNeeded(dm, dataSet, parallel); final List, Double>>> allNNs; vc.build(parallel, vecs, dm); allNNs = VectorCollectionUtils.allNearestNeighbors(vc, vecs, k + 1, parallel); //NOTE: Density is done in reverse, so large values indicate low density, small values indiciate high density. //mark density as the sum of distances final double[] density = new double[vecs.size()]; final double[][] weights = new double[n][k]; OnLineStatistics densityStats = new OnLineStatistics(); for (int i = 0; i < density.length; i++) { List, Double>> knns = allNNs.get(i); for (int j = 1; j < knns.size(); j++) density[i] += (weights[i][j - 1] = knns.get(j).getPair()); densityStats.add(density[i]); double sum = 0; for (int j = 0; j < k; j++) sum += (weights[i][j] = Math.min(1.0 / Math.pow(weights[i][j], 2), Double.MAX_VALUE / (k + 1))); for (int j = 0; j < k; j++) weights[i][j] /= sum; } final Map CSOs = new HashMap<>(); final Set outliers = new IntSet(); Arrays.fill(designations, -1); final double threshold = densityStats.getMean() + densityStats.getStandardDeviation() * stndDevs; for (int i = 0; i < density.length; i++) { List, Double>> knns = allNNs.get(i); boolean lowest = true;//if my density score is lower then all neighbors, then i am a CSO boolean highest = true;//if heigher, then I am an outlier for (int j = 1; j < knns.size() && (highest || lowest); j++) { int jNN = knns.get(j).getVector().getPair(); if (density[i] > density[jNN]) lowest = false; else highest = false; } if (lowest) CSOs.put(i, CSOs.size()); else if (highest && density[i] > threshold) outliers.add(i); } //remove CSO that occur near outliers { int origSize = CSOs.size(); Iterator iter = CSOs.keySet().iterator(); while (iter.hasNext()) { int i = iter.next(); List, Double>> knns = allNNs.get(i); for (int j = 1; j < knns.size(); j++) if (outliers.contains(knns.get(j).getVector().getPair())) { iter.remove(); break; } } if(origSize != CSOs.size())//we did a removal, re-order clusters { Set keys = new IntSet(CSOs.keySet()); CSOs.clear(); for(int i : keys) CSOs.put(i, CSOs.size()); } //May have gaps, will be fixed in final step for (int i : CSOs.keySet()) designations[i] = CSOs.get(i); } //outlier is implicit extra term double[][] fuzzy = new double[n][CSOs.size() + 1]; for (int i = 0; i < n; i++) if (CSOs.containsKey(i)) fuzzy[i][CSOs.get(i)] = 1.0;//each CSO is full it itself else if (outliers.contains(i)) fuzzy[i][CSOs.size()] = 1.0; else Arrays.fill(fuzzy[i], 1.0 / (CSOs.size() + 1)); //iterate double[][] fuzzy2 = new double[n][CSOs.size() + 1]; double prevScore = Double.POSITIVE_INFINITY; for (int iter = 0; iter < maxIterations; iter++) { final double[][] FROM = fuzzy, TO = fuzzy2; final DoubleAdder score = new DoubleAdder(); //Single index loop b/c of uneven workloads ParallelUtils.run(parallel, FROM.length, (i)-> { if (outliers.contains(i) || CSOs.containsKey(i)) return; final double[] fuzzy2_i = TO[i]; Arrays.fill(fuzzy2_i, 0); List, Double>> knns = allNNs.get(i); double sum = 0; for (int j = 1; j < weights[i].length; j++) { int jNN = knns.get(j).getVector().getPair(); final double[] fuzzy_jNN = FROM[jNN]; double weight = weights[i][j - 1]; for (int z = 0; z < FROM[jNN].length; z++) fuzzy2_i[z] += weight * fuzzy_jNN[z]; } for (int z = 0; z < fuzzy2_i.length; z++) sum += fuzzy2_i[z]; double localScore = 0; for (int z = 0; z < fuzzy2_i.length; z++) { fuzzy2_i[z] /= sum + 1e-6; localScore += Math.abs(FROM[i][z] - fuzzy2_i[z]); } score.add(localScore); }); if (Math.abs(prevScore - score.doubleValue()) < eps) break; prevScore = score.doubleValue(); double[][] tmp = fuzzy; fuzzy = fuzzy2; fuzzy2 = tmp; } //Figure out final clsutering int[] clusterCounts = new int[n]; for (int i = 0; i < fuzzy.length; i++) { int pos = -1; double maxVal = 0; for (int j = 0; j < fuzzy[i].length; j++) { if (fuzzy[i][j] > maxVal) { maxVal = fuzzy[i][j]; pos = j; } } if(pos == -1)//TODO how di this happen? Mark it as an outlier. Somehow your whole row became zeros to cause this pos = CSOs.size(); clusterCounts[pos]++; if (pos == CSOs.size())//outlier pos = -1; designations[i] = pos; } /* Transform clusterCOunts to indicate the new cluster ID. If * everyone gets there own id, no clusters removed. Else, people * with a negative value know they need to remove themsleves */ int newCCount = 0; for(int i = 0; i < clusterCounts.length; i++) if(clusterCounts[i] > 1) clusterCounts[i] = newCCount++; else clusterCounts[i] = -1; //Go through and remove clusters with a count of 1 if(newCCount != clusterCounts.length) { double[] tmp = new double[CSOs.size()+1]; for (int i = 0; i < fuzzy.length; i++) { int d = designations[i]; if(d > 0)//not outlier { if (clusterCounts[d] == -1)//remove self { List, Double>> knns = allNNs.get(i); for (int j = 1; j < weights[i].length; j++) { int jNN = knns.get(j).getVector().getPair(); final double[] fuzzy_jNN = fuzzy[jNN]; double weight = weights[i][j - 1]; for (int z = 0; z < fuzzy[jNN].length; z++) tmp[z] += weight * fuzzy_jNN[z]; } double maxVal = -1; int maxIndx = -1; for(int z = 0; z < tmp.length; z++) if(tmp[z] > maxVal) { maxVal =tmp[z]; maxIndx = z; } if(maxIndx == CSOs.size()) designations[i] = -1; else designations[i] = clusterCounts[maxIndx]; } else { designations[i] = clusterCounts[d]; } } } } return designations; } @Override public FLAME clone() { return new FLAME(this); } }

Ads help maintain this website.