OPTICS is a very popular density-based clustering algorithm. Therefore it clusters all the data based on the density of records, creating clusters with that information. One of the special features is that OPTICS uses a specific ordering of the points to perform this partitioning.
In order to provide you a broader knowledge of OPTICS, we decided to publish our Java implementation of it. On the following code boxes, we provide the our complete Java code to program the OPTICS algorithm.
This is a simple implementation which can be optimized and you can use or modify as you wish.
Algorithm.java
1 2 3 4 5 6 7 8 9 10 11 12 13 |
package com.dataonfocus.clustering; import java.util.List; import com.dataonfocus.clustering.structures.DataPoint; public interface Algorithm { public void setPoints(List points); public void cluster(); } |
DataPoint.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
package com.dataonfocus.clustering.structures; public interface DataPoint { public double distance(DataPoint datapoint); public void setCluster(int id); public int getCluster(); public int getX(); public int getY(); } |
Pair.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
package com.dataonfocus.clustering.structures; import java.util.Objects; public class Pair<P, S> { private P first; private S second; public Pair(P first, S second) { this.first = first; this.second = second; } public void setFirst(P first) { this.first = first; } public void setSecond(S second) { this.second = second; } public P getFirst() { return first; } public S getSecond() { return second; } public String toString() { return "<"+first+","+second+">"; } public boolean equals(Object o) { if (!(o instanceof Pair)) { return false; } Pair<!--?,? > p = (Pair<?,?-->) o; return Objects.equals(p.first, first) && Objects.equals(p.second, second); } public int hashCode() { return (first == null ? 0 : first.hashCode()) ^ (second == null ? 0 : second.hashCode()); } } |
OPTICS.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 |
package com.dataonfocus.clustering.density; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import com.dataonfocus.clustering.structures.DataPoint; import com.dataonfocus.clustering.structures.Pair; public class OPTICS { public List points; private List order; public double max_distance; public int min_points; public boolean[] processed; private double[] reachability; private double[] core_distance; private double[][] distances; public OPTICS(double max_distance, int min_points) { this.points = new ArrayList(); this.order = new ArrayList(); this.max_distance = max_distance; this.min_points = min_points; } public void cluster() { calculateDistances(); Iterator it = points.iterator(); int n = 0; while(it.hasNext()) { DataPoint point = it.next(); if(!processed[n]) { processed[n] = true; List neighbors = getNeighbors(point,n); order.add(point); if(core_distance[n] != -1) { List<Pair<Integer,Double>> seeds = new ArrayList<Pair<Integer,Double>>(); update(point,seeds, neighbors, n); for(Pair<Integer,Double> seed : seeds) { int node = seed.getFirst(); processed[node] = true; DataPoint seedPoint = points.get(node); List seedNeighbors = getNeighbors(seedPoint,node); order.add(seedPoint); if(core_distance[node] != -1) { update(seedPoint,seeds,seedNeighbors,node); } } } } } } private void update(DataPoint point, List<Pair<Integer, Double>> seeds, List neighbors, int node) { for(int i = 0; i <; neighbors.size(); i++) { int index = neighbors.get(i); if(!processed[index]) { double max = Math.max(core_distance[node],distances[node][index]); if(reachability[index] == -1) { reachability[index] = max; insertSeed(seeds,new Pair<Integer,Double>(index,max),false); } else if (max < reachability[index]) { reachability[index] = max; insertSeed(seeds,new Pair<Integer,Double>(index,max),true); } } } } public void insertSeed(List<Pair<Integer,Double>> seeds, Pair<Integer,Double> seed, boolean remove) { int index = seeds.size() +1; int node = seed.getFirst(); double distance = seed.getSecond(); boolean done = false; for(int i = 0; i < seeds.size(); i++) { Pair<Integer,Double> aux = seeds.get(i); double aux_distance = aux.getSecond(); if(distance < aux_distance) { seeds.add(i,seed); done = true; if(remove) { index = i + 1; } break; } } for(int i = index; i < seeds.size() ; i++) { Pair<Integer,Double> aux = seeds.get(i); int aux_index = aux.getFirst(); if(node == aux_index) { seeds.remove(i); break; } } if(!done) { seeds.add(seeds.size(),seed); } } private List getNeighbors(DataPoint d, int index) { List neighbors = new ArrayList(); int i = 0; for (Iterator iterator = points.iterator(); iterator .hasNext();) { iterator.next(); double distance = distances[index][i]; if(distance <= max_distance) { neighbors.add(i); if(i == min_points-1) { core_distance[index] = distance; } } i++; } return neighbors; } public void setPoints(List points) { this.points = points; this.processed = new boolean[points.size()]; this.reachability = new double[points.size()]; this.core_distance = new double[points.size()]; for(int i = 0; i < reachability.length; i++) { reachability[i] = -1; core_distance[i] = -1; } } private void calculateDistances() { System.out.println("Calculation distances between " + points.size() + " points..."); int size = points.size(); this.distances = new double[size][size]; for(int i = 0; i < size; i++) { DataPoint p1 = points.get(i); for(int j = i + 1; j < size; j++) { DataPoint p2 = points.get(j); double distance = p1.distance(p2); distances[i][j] = distance; distances[j][i] = distance; } } } } |
Feel free to use and adapt our solution to this problem. We will love to know what you are working on and how we helped you with this piece of code. So, if you want to make some suggestion or comment, just contact us!