package jsat.clustering;

import java.util.*;

import jsat.DataSet;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.vectorcollection.*;
import jsat.math.OnLineStatistics;
import jsat.parameters.*;
import jsat.utils.IntList;
import jsat.utils.IntSet;

/**
 * An Implementation of the OPTICS algorithm, which is a generalization of 
 * {@link DBSCAN}. OPTICS creates an ordering of the ports, and then clusters 
 * can be extracted from this ordering in numerous different ways. 
 * 
* NOTE: The original clustering method proposed in the paper is fairly * complicated, and its implementation is not yet complete. Though it does * perform some amount of clustering, it may not return the expected results. *

* See original paper
* Ankerst, M., Breunig, M., Kriegel, H.-P.,&Sander, J. (1999). * OPTICS: ordering points * to identify the clustering structure. Proceedings of the * 1999 ACM SIGMOD international conference on Management of data * (Vol. 28, pp. 49–60). Philadelphia, Pennsylvania: ACM. * * @author Edward Raff */ public class OPTICS extends ClustererBase implements Parameterized { private static final long serialVersionUID = -1093772096278544211L; private static final int NOISE = -1; private static double UNDEFINED = Double.POSITIVE_INFINITY; /** * The default value for xi is {@value #DEFAULT_XI} */ public static final double DEFAULT_XI = 0.005; /** * The default number of points to consider is {@value #DEFAULT_MIN_POINTS}. */ public static final int DEFAULT_MIN_POINTS = 10; /** * The default method used to extract clusters in OPTICS */ public static final ExtractionMethod DEFAULT_EXTRACTION_METHOD = ExtractionMethod.THRESHHOLD_FIXUP; private DistanceMetric dm; private VectorCollection> vc = new DefaultVectorCollection<>(); private double radius = 1; private int minPts; private double[] core_distance; /** * Stores the reachability distance of each point in the order they were * first observed in the data set. After clustering is finished, it is * altered to be in the reachability order used in clustering */ private double[] reach_d; /** * Whether or not the given data point has been processed */ private boolean[] processed; private Vec[] allVecs; private double xi; //XXX useless assignment private double one_min_xi;// = 1.0-xi; private ExtractionMethod extractionMethod = DEFAULT_EXTRACTION_METHOD; /** * The objects contained in OrderSeeds are sorted by their * reachability-distance to the closest core object from which they have * been directly density reachable. * * The paired double is their distance, the paired integer the the vector's * index in the data set * * This is only used during building. We should probably refactor this out */ private PriorityQueue orderdSeeds; @Override public OPTICS clone() { return new OPTICS(this); } /** * Enum to indicate which method of extracting clusters should be used on * the reachability plot. * */ public enum ExtractionMethod { /** * Uses the original clustering method proposed in the OPTICS paper.
* NOTE: Implementation not yet complete */ XI_STEEP_ORIGINAL, /** * Forms clusters in the reachability plot by drawing a line across it, * and using the separations to mark clusters */ THRESHHOLD, /** * Forms clusters in the reachability plot by drawing a line across it, * and using the separations to mark clusters. It then de-noises points * by checking their nearest neighbors for consensus */ THRESHHOLD_FIXUP } /** * Creates a new OPTICS cluster object. Because the radius of OPTICS is not * sensitive, it is estimated from the data and set to a sufficiently large * value. The {@link EuclideanDistance} will be used as the metric. */ public OPTICS() { this(DEFAULT_MIN_POINTS); } /** * Creates a new OPTICS cluster object. Because the radius of OPTICS is not * sensitive, it is estimated from the data and set to a sufficiently large * value. The {@link EuclideanDistance} will be used as the metric. * * @param minPts the minimum number of points for reachability */ public OPTICS(int minPts) { this(new EuclideanDistance(), minPts); } /** * Creates a new OPTICS cluster object. Because the radius of OPTICS is not * sensitive, it is estimated from the data and set to a sufficiently large * value. * * @param dm the distance metric to use * @param minPts the minimum number of points for reachability */ public OPTICS(DistanceMetric dm, int minPts) { this(dm, minPts, DEFAULT_XI); } /** * Creates a new OPTICS cluster object. Because the radius of OPTICS is not * sensitive, it is estimated from the data and set to a sufficiently large * value. * * @param dm the distance metric to use * @param minPts the minimum number of points for reachability * @param xi the xi value */ public OPTICS(DistanceMetric dm, int minPts, double xi) { setDistanceMetric(dm); setMinPts(minPts); setXi(xi); } public OPTICS(OPTICS toCopy) { this.dm = toCopy.dm.clone(); this.vc = toCopy.vc.clone(); this.minPts = toCopy.minPts; if(toCopy.core_distance != null ) this.core_distance = Arrays.copyOf(toCopy.core_distance, toCopy.core_distance.length); if(toCopy.reach_d != null ) this.reach_d = Arrays.copyOf(toCopy.reach_d, toCopy.reach_d.length); if(toCopy.processed != null ) this.processed = Arrays.copyOf(toCopy.processed, toCopy.processed.length); if(toCopy.allVecs != null ) { this.allVecs = new Vec[toCopy.allVecs.length]; for(int i = 0; i < toCopy.allVecs.length; i++) this.allVecs[i] = toCopy.allVecs[i].clone(); } this.xi = toCopy.xi; this.orderdSeeds = toCopy.orderdSeeds; this.radius = toCopy.radius; } /** * Sets the distance metric used to compute distances in the algorithm. * * @param dm the distance metric to use */ public void setDistanceMetric(DistanceMetric dm) { this.dm = dm; } /** * Returns the distance metric used to compute distances in the algorithm. * @return the distance metric used */ public DistanceMetric getDistanceMetric() { return dm; } /** * Sets the xi value used in {@link ExtractionMethod#XI_STEEP_ORIGINAL} to * produce cluster results. * * @param xi the value in the range (0, 1) * @throws ArithmeticException if the value is not in the appropriate range */ public void setXi(double xi) { if(xi <= 0 || xi >= 1 || Double.isNaN(xi)) throw new ArithmeticException("xi must be in the range (0, 1) not " + xi); this.xi = xi; this.one_min_xi = 1.0 - xi; } /** * Returns the xi value used in {@link ExtractionMethod#XI_STEEP_ORIGINAL} to * produce cluster results. * * @return the xi value used */ public double getXi() { return xi; } /** * Sets the method used to extract clusters from the reachability plot. * * @param extractionMethod the clustering method */ public void setExtractionMethod(ExtractionMethod extractionMethod) { this.extractionMethod = extractionMethod; } /** * Returns the method used to extract clusters from the reachability plot. * * @return the clustering method used */ public ExtractionMethod getExtractionMethod() { return extractionMethod; } /** * Sets the minimum number of points needed to compute the core distance. * Higher values tend to smooth out the reachability plot. * * @param minPts the number of points to compute reachability and core distance */ public void setMinPts(int minPts) { this.minPts = minPts; } /** * Sets the minimum number of points needed to compute the core distance. * * @return the number of points to compute reachability and core distance */ public int getMinPts() { return minPts; } /** * Sets the {@link VectorCollection} used to produce acceleration * structures for the OPTICS computation. * * @param vc the vector collection to use */ public void setVCF(VectorCollection> vc) { this.vc = vc; } private int threshHoldFixExtractCluster(List orderedFile, int[] designations) { int clustersFound = threshHoldExtractCluster(orderedFile, designations); for(int i = 0; i < orderedFile.size(); i++) { if(designations[i] != NOISE) continue; //Check if all the neighbors have a consensus on the cluster class (ignoring noise) List, Double>> neighbors = vc.search(allVecs[i], minPts/2+1); int CLASS = -1;//-1 for not set, -2 for conflic for(VecPaired, Double> v : neighbors) { int subC = designations[v.getVector().getPair()]; if(subC == NOISE)//ignore continue; else if(CLASS == -1)//First class set CLASS = subC; else if (CLASS != subC)//Conflict CLASS = -2;//No consensus, we wont change the noise label } if(CLASS != -2) designations[i]= CLASS; } return clustersFound; } /** * Finds clusters by segmenting the reachability plot witha line that is the mean reachability distance times * @param orderedFile the ordering of the data points * @param designations the storage array for their cluster assignment * @return the number of clusters found */ private int threshHoldExtractCluster(List orderedFile, int[] designations) { int clustersFound = 0; OnLineStatistics stats = new OnLineStatistics(); for(double r : reach_d) if(!Double.isInfinite(r)) stats.add(r); double thresh = stats.getMean()+stats.getStandardDeviation(); for(int i = 0; i < orderedFile.size(); i++) { if(reach_d[orderedFile.get(i)] >= thresh) continue; //Everything in between is part of the cluster while(i < orderedFile.size() && reach_d[orderedFile.get(i)] < thresh) designations[i++] = clustersFound; //Climb up to the top of the hill, everything we climbed over is part of the cluster while(i+1 < orderedFile.size() && reach_d[orderedFile.get(i)] < reach_d[orderedFile.get(i+1)]) designations[i++] = clustersFound; clustersFound++; } return clustersFound; } /** * Extracts clusters using the original xi steep algorithm from the OPTICS paper * @param n original number of data points * @param orderedFile the correct order of the points in the reachability plot * @param designations the array to store the final class designations * @return the number of clusters found */ private int xiSteepClusterExtract(final int n, List orderedFile, int[] designations) { ///Now obtain clustering ///Extract CLustering int clustersFound = 0; Set sdaSet = new IntSet(); int orderIndex = 0; double mib = 0; double[] mibVals = new double[n]; List clusters = new ArrayList(); List allSteepUp = new IntList(); List allSDA = new IntList(); /* * Ugly else if to increment orderIndex counter and avoid geting stuck * in infinite loops. * Can I write that a better way? */ while(orderIndex < orderedFile.size()-1) { int curIndex = orderedFile.get(orderIndex); mib = Math.max(mib, reach_d[curIndex]); if(orderIndex +1 < orderedFile.size()) { int nextIndex = orderedFile.get(orderIndex+1); if(!downPoint(curIndex, nextIndex))//IF(start of a steep down area D at index) { filterSDASet(sdaSet, mib, mibVals, orderedFile); sdaSet.add(orderIndex); allSDA.add(orderIndex); while(orderIndex+1 < orderedFile.size()) { orderIndex++; curIndex = nextIndex; if(orderIndex+1 >= orderedFile.size()) break; nextIndex = orderedFile.get(orderIndex+1); if(downPoint(curIndex, nextIndex)) break; } mib = reach_d[curIndex]; } else if(!upPoint(curIndex, nextIndex))//ELSE IF(start of steep up area U at index) { filterSDASet(sdaSet, mib, mibVals, orderedFile); if(!sdaSet.isEmpty()) allSteepUp.add(orderIndex); while(orderIndex+1 < orderedFile.size()) { orderIndex++; curIndex = nextIndex; if(orderIndex+1 >= orderedFile.size()) break; nextIndex = orderedFile.get(orderIndex+1); if(upPoint(curIndex, nextIndex)) break; } mib = reach_d[curIndex]; for(Iterator iter = sdaSet.iterator(); iter.hasNext(); ) { int sdaOrdered = iter.next(); int sdaIndx = orderedFile.get(sdaOrdered); if(!(orderIndex-sdaOrdered >= minPts))//Fail 3a continue; else if(mib * one_min_xi < mibVals[sdaIndx]) { continue; } if(sdaOrdered > orderIndex) continue; OPTICSCluster newClust = new OPTICSCluster(sdaOrdered, orderIndex+1); OPTICSCluster tmp; for(Iterator clustIter = clusters.iterator(); clustIter.hasNext();) { if(newClust.contains((tmp = clustIter.next()))) { clustIter.remove(); newClust.subClusters.add(tmp); } } clusters.add(newClust); } } else orderIndex++; } else orderIndex++; } for(OPTICSCluster oc : clusters) { for(int i : orderedFile.subList(oc.start, oc.end)) if(designations[i] < 0) designations[i] = clustersFound; clustersFound++; } return clustersFound; } /** * Private class for keeping track of heiarchies of clusters */ private class OPTICSCluster { int start, end; List subClusters; public OPTICSCluster(int start, int end) { this.start = start; this.end = end; this.subClusters = new ArrayList(5); } /** * * @param other * @return */ public boolean contains(OPTICSCluster other) { return this.start <= other.start && other.end <= this.end; } @Override public String toString() { return "{" + start + "," + end + "}"; } } @Override public int[] cluster(DataSet dataSet, int[] designations) { if(dataSet.getNumNumericalVars() < 1) throw new ClusterFailureException("OPTICS requires numeric features, and non are present."); final int n = dataSet.getSampleSize(); if(designations == null) designations = new int[n]; Arrays.fill(designations, NOISE); orderdSeeds = new PriorityQueue<>(n, (Integer o1, Integer o2) -> Double.compare(reach_d[o1], reach_d[o2])); core_distance = new double[n]; reach_d = new double[n]; Arrays.fill(reach_d, UNDEFINED); processed = new boolean[n]; allVecs = new Vec[n]; List> pairedVecs = new ArrayList<>(n); for(int i = 0; i < allVecs.length; i++) { allVecs[i] = dataSet.getDataPoint(i).getNumericalValues(); pairedVecs.add(new VecPaired<>(allVecs[i], i)); } vc.build(false, pairedVecs, dm); //Estimate radius value OnLineStatistics stats = VectorCollectionUtils.getKthNeighborStats(vc, allVecs, minPts+1); radius = stats.getMean() + stats.getStandardDeviation() * 3; List orderedFile = new IntList(n); //Main clustering loop for(int i = 0; i < dataSet.getSampleSize(); i++) { if(processed[i]) continue; Vec vec = dataSet.getDataPoint(i).getNumericalValues(); expandClusterOrder(i, vec, orderedFile); } int clustersFound; if(extractionMethod == ExtractionMethod.THRESHHOLD) clustersFound = threshHoldExtractCluster(orderedFile, designations); else if(extractionMethod == ExtractionMethod.THRESHHOLD_FIXUP) clustersFound = threshHoldFixExtractCluster(orderedFile, designations); else if(extractionMethod == ExtractionMethod.XI_STEEP_ORIGINAL) clustersFound = xiSteepClusterExtract(n, orderedFile, designations); //Sort reachability values double[] newReach = new double[reach_d.length]; Arrays.fill(newReach, Double.POSITIVE_INFINITY); for(int i = 0; i < orderedFile.size(); i++) newReach[i] = reach_d[orderedFile.get(i)]; reach_d = newReach; return designations; } private void filterSDASet(Set sdaSet, double mib, double[] mibVals, List orderedFile) { for(Iterator iter = sdaSet.iterator(); iter.hasNext(); ) { int sdaIndx = orderedFile.get(iter.next()); if(reach_d[sdaIndx]*one_min_xi <= mib) iter.remove(); else mibVals[sdaIndx] = Math.max(mib, mibVals[sdaIndx]);//TODO mibFill? } } private boolean upPoint(int index1, int index2) { return reach_d[index1] <= reach_d[index2]*one_min_xi; } private boolean downPoint(int index1, int index2) { return reach_d[index1]*one_min_xi <= reach_d[index2]; } @Override public int[] cluster(DataSet dataSet, boolean parallel, int[] designations) { return cluster(dataSet, designations); } private void expandClusterOrder(int curIndex, Vec vec, List orderedFile) { List, Double>> neighbors = vc.search(vec, radius); VecPaired object = new VecPaired<>(vec, curIndex); reach_d[curIndex] = UNDEFINED;//NaN used for undefined processed[curIndex] = true; setCoreDistance(neighbors, curIndex); orderedFile.add(curIndex); if(!Double.isInfinite(core_distance[curIndex])) { orderedSeedsUpdate(neighbors, curIndex); while(!orderdSeeds.isEmpty()) { int curObjectIndex = orderdSeeds.poll(); neighbors = vc.search(allVecs[curObjectIndex], radius); processed[curObjectIndex] = true; setCoreDistance(neighbors, curObjectIndex); orderedFile.add(curObjectIndex); if(!Double.isInfinite(core_distance[curObjectIndex])) orderedSeedsUpdate(neighbors, curObjectIndex); } } } private void setCoreDistance(List, Double>> neighbors, int curIndex) { if(neighbors.size() < minPts+1)//+1 b/c we dont count oursleves, which will get returned core_distance[curIndex] = UNDEFINED; else//0 is us, 1 is the nearest neighbor core_distance[curIndex] = neighbors.get(minPts).getPair(); } private void orderedSeedsUpdate(List, Double>> neighbors, int centerObjectIndex) { double c_dist = core_distance[centerObjectIndex]; for(int i = 1; i < neighbors.size(); i++)//'0' index is a self reference, skip it { VecPaired, Double> neighbor = neighbors.get(i); int objIndex = neighbor.getVector().getPair(); if(processed[objIndex]) continue; double new_r_dist = Math.max(c_dist, neighbor.getPair()); if(Double.isInfinite(reach_d[objIndex])) { reach_d[objIndex] = new_r_dist; // r_dists[objIndex] = new_r_dist; orderdSeeds.add(objIndex); } else if(new_r_dist < reach_d[objIndex])// Object already in OrderSeeds, but we can do better { reach_d[objIndex] = new_r_dist; // r_dists[objIndex] = new_r_dist; orderdSeeds.remove(objIndex); orderdSeeds.add(objIndex); } } } @SuppressWarnings("unused") private void extractClusteringDBSCAN(List orderedFile, double e, int[] designations) { int clusterID = NOISE; for(int i = 0; i < orderedFile.size(); i++) { int trueObjIndex = orderedFile.get(i); if( Double.isInfinite(reach_d[trueObjIndex]) || reach_d[trueObjIndex] > e) { if(core_distance[trueObjIndex] <= e) { clusterID++; designations[trueObjIndex] = clusterID; } else designations[trueObjIndex] = NOISE; } else designations[trueObjIndex] = clusterID; } throw new UnsupportedOperationException("Not yet implemented"); } /** * Returns a copy of the reachability array in correct reachability order. * Some values that are not density reachability could have a value of * {@link Double#POSITIVE_INFINITY}. * * @return an array of the reachability values */ public double[] getReachabilityArray() { return Arrays.copyOf(reach_d, reach_d.length); } }

Ads help maintain this website.