OPTICS Java Code - DataOnFocus

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

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();

}

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

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();
}

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

package com.dataonfocus.clustering.structures;

import java.util.Objects;

public class Pair&lt;P, S&gt; {
	
    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 "&lt;"+first+","+second+"&gt;";
    }
    
    public boolean equals(Object o) {
        if (!(o instanceof Pair)) {
            return false;
        }
        Pair<!--?,? &gt; p = (Pair&lt;?,?-->) o;
        return Objects.equals(p.first, first) &amp;&amp; Objects.equals(p.second, second);
    }

    public int hashCode() {
        return (first == null ? 0 : first.hashCode()) ^ (second == null ? 0 : second.hashCode());
    }
}

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) 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

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&lt;Pair&lt;Integer,Double&gt;&gt; seeds = new ArrayList&lt;Pair&lt;Integer,Double&gt;&gt;();
					update(point,seeds, neighbors, n);
					
					for(Pair&lt;Integer,Double&gt; 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&lt;Pair&lt;Integer, Double&gt;&gt; seeds,
			List neighbors, int node) {
		
		for(int i = 0; i &lt;; 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&lt;Integer,Double&gt;(index,max),false);
				}
				else if (max &lt; reachability[index]) {
					reachability[index] = max;
					insertSeed(seeds,new Pair&lt;Integer,Double&gt;(index,max),true);
				}
			}
		}
	}
	
	public void insertSeed(List&lt;Pair&lt;Integer,Double&gt;&gt; seeds, Pair&lt;Integer,Double&gt; seed, boolean remove) {
		int index = seeds.size() +1;
		
		int node = seed.getFirst();
		double distance = seed.getSecond();
		
		boolean done = false;
		
		for(int i = 0; i &lt; seeds.size(); i++) {
			Pair&lt;Integer,Double&gt; aux = seeds.get(i);
			double aux_distance = aux.getSecond();
			if(distance &lt; aux_distance) {
				seeds.add(i,seed);
				done = true;
				if(remove) {
					index = i + 1;
				}
				break;
			}
		}
		for(int i = index; i &lt; seeds.size() ; i++) {
			Pair&lt;Integer,Double&gt; 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 &lt;= 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 &lt; 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 &lt; size; i++) {
			
			DataPoint p1 = points.get(i);
			
			for(int j = i + 1; j &lt; size; j++) {
				DataPoint p2 = points.get(j);
				
				double distance = p1.distance(p2);
				
				distances[i][j] = distance;
				distances[j][i] = distance;
			}
		}
		
	}
}

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!