/*
* Copyright (C) 2016 Edward Raff
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
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.utils.FibHeap;
import static java.lang.Math.max;
import jsat.exceptions.FailedToFitException;
import jsat.parameters.Parameterized;
import jsat.utils.*;
/**
* HDBSCAN is a density based clustering algorithm that is an improvement over
* {@link DBSCAN}. Unlike its predecessor, HDBSCAN works with variable density
* datasets and does not need a search radius to be specified. The original
* paper presents HDBSCAN with two parameters
* {@link #setMinPoints(int) mpts} and
* {@link #setMinClusterSize(int) mclSize}, but recomends that they
* can be set to the same value and effectively behave as if only one parameter
* exists. This implementation allows for setting both independtly, but the
* single parameter constructors will use the same value for both parameters.
*
* NOTE: The current implementation has O(N2) run time, though
* this may be improved in the future with more advanced algorithms.
*
* See: Campello, R. J. G. B., Moulavi, D., & Sander, J. (2013). Density-Based
* Clustering Based on Hierarchical Density Estimates. In J. Pei, V. Tseng, L.
* Cao, H. Motoda, & G. Xu (Eds.), Advances in Knowledge Discovery and Data
* Mining (pp. 160–172). Springer Berlin Heidelberg.
* doi:10.1007/978-3-642-37456-2_14
* @author Edward Raff
*/
public class HDBSCAN implements Clusterer, Parameterized
{
private DistanceMetric dm;
/**
* minimium number of points
*/
private int m_pts;
private int m_clSize;
private VectorCollection vc;
/**
* Creates a new HDBSCAN object using a threshold of 15 points to form a
* cluster.
*/
public HDBSCAN()
{
this(15);
}
/**
* Creates a new HDBSCAN using the simplified form, where the only parameter
* is a single value.
*
* @param m_pts the minimum number of points needed to form a cluster and
* the number of neighbors to consider
*/
public HDBSCAN(int m_pts)
{
this(new EuclideanDistance(), m_pts);
}
/**
* Creates a new HDBSCAN using the simplified form, where the only parameter
* is a single value.
*
* @param dm the distance metric to use for finding nearest neighbors
* @param m_pts the minimum number of points needed to form a cluster and
* the number of neighbors to consider
*/
public HDBSCAN(DistanceMetric dm, int m_pts)
{
this(dm, m_pts, m_pts, new DefaultVectorCollection<>());
}
/**
* Creates a new HDBSCAN using the simplified form, where the only parameter
* is a single value.
*
* @param dm the distance metric to use for finding nearest neighbors
* @param m_pts the minimum number of points needed to form a cluster and
* the number of neighbors to consider
* @param vcf the vector collection to use for accelerating nearest neighbor
* queries
*/
public HDBSCAN(DistanceMetric dm, int m_pts, VectorCollection vcf)
{
this(dm, m_pts, m_pts, vcf);
}
/**
* Creates a new HDBSCAN using the full specification of the algorithm,
* where two parameters may be altered. In the simplified version both
* parameters always have the same value.
*
* @param dm the distance metric to use for finding nearest neighbors
* @param m_pts the number of neighbors to consider, acts as a smoothing
* over the density estimate
* @param m_clSize the minimum number of data points needed to form a
* cluster
* @param vc the vector collection to use for accelerating nearest neighbor
* queries
*/
public HDBSCAN(DistanceMetric dm, int m_pts, int m_clSize, VectorCollection vc)
{
this.dm = dm;
this.m_pts = m_pts;
this.m_clSize = m_clSize;
this.vc = vc;
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public HDBSCAN(HDBSCAN toCopy)
{
this.dm = dm.clone();
this.m_pts = toCopy.m_pts;
this.m_clSize = toCopy.m_clSize;
this.vc = toCopy.vc.clone();
}
/**
*
* @param m_clSize the minimum number of data points needed to form a
* cluster
*/
public void setMinClusterSize(int m_clSize)
{
this.m_clSize = m_clSize;
}
/**
*
* @return the minimum number of data points needed to form a
* cluster
*/
public int getMinClusterSize()
{
return m_clSize;
}
/**
* Sets the distance metric to use for determining closeness between data points
* @param dm the distance metric to determine nearest neighbors with
*/
public void setDistanceMetrics(DistanceMetric dm)
{
this.dm = dm;
}
/**
*
* @return the distance metric to determine nearest neighbors with
*/
public DistanceMetric getDistanceMetrics()
{
return dm;
}
/**
*
* @param m_pts the number of neighbors to consider, acts as a smoothing
* over the density estimate
*/
public void setMinPoints(int m_pts)
{
this.m_pts = m_pts;
}
/**
*
* @return the number of neighbors to consider, acts as a smoothing
* over the density estimate
*/
public int getMinPoints()
{
return m_pts;
}
@Override
public HDBSCAN clone()
{
return new HDBSCAN(this);
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
if(designations == null)
designations = new int[dataSet.getSampleSize()];
@SuppressWarnings("unchecked")
final List X = dataSet.getDataVectors();
final int N = X.size();
List cache = dm.getAccelerationCache(X, parallel);
VectorCollection X_vc = vc.clone();
X_vc.build(parallel, X, dm);
//1. Compute the core distance w.r.t. m_pts for all data objects in X.
/*
* (Core Distance): The core distance of an object x_p ∈ X w.r.t. m_pts,
* d_core(x_p), is the distance from x_p to its m_pts-nearest neighbor (incl. x_p)
*/
List>> allNearestNeighbors = VectorCollectionUtils.allNearestNeighbors(X_vc, X, m_pts, parallel);
double[] core = new double[N];
for(int i = 0; i < N; i++)
core[i] = allNearestNeighbors.get(i).get(m_pts-1).getPair();
//2. Compute an MST of G_{m_pts}, the Mutual Reachability Graph.
//prims algorithm from Wikipedia
double[] C = new double[N];
Arrays.fill(C, Double.MAX_VALUE);
int[] E = new int[N];
Arrays.fill(E, -1);//-1 "a special flag value indicating that there is no edge connecting v to earlier vertices"
FibHeap Q = new FibHeap<>();
List> q_nodes = new ArrayList<>(N);
for(int i = 0; i < N; i++)
q_nodes.add(Q.insert(i, C[i]));
Set F = new HashSet<>();
/**
* First 2 indicate the edges, 3d value is the weight
*/
List> mst_edges = new ArrayList<>(N*2);
while(Q.size() > 0)
{
//a. Find and remove a vertex v from Q having the minimum possible value of C[v]
FibHeap.FibNode node = Q.removeMin();
int v = node.getValue();
q_nodes.set(v, null);
//b. Add v to F and, if E[v] is not the special flag value, also add E[v] to F
F.add(v);
if(E[v] >= 0)
mst_edges.add(new Tuple3<>(v, E[v], C[v]));
/*
* c. Loop over the edges vw connecting v to other vertices w. For
* each such edge, if w still belongs to Q and vw has smaller weight
* than C[w]:
* Set C[w] to the cost of edge vw
* Set E[w] to point to edge vw.
*/
for(int w = 0; w < N; w++)
{
FibHeap.FibNode w_node = q_nodes.get(w);
if (w_node == null)//this node is already in F
continue;
double mutual_reach_dist_vw = max(core[v], max(core[w], dm.dist(v, w, X, cache)));
if (mutual_reach_dist_vw < C[w])
{
Q.decreaseKey(w_node, mutual_reach_dist_vw);
C[w] = mutual_reach_dist_vw;
E[w] = v;
}
}
}
//prim is done, we have the MST!
/*
* 3. Extend the MST to obtain MSText, by adding for each vertex a “self
* edge” with the core distance of the corresponding object as weight
*/
for(int i = 0; i < N; i++)
mst_edges.add(new Tuple3<>(i, i, core[i]));
//4. Extract the HDBSCAN hierarchy as a dendrogram from MSText:
List> ufs = new ArrayList<>(N);
for(int i = 0; i < N; i++)
ufs.add(new UnionFind<>(i));
//sort edges from smallest weight to largest
PriorityQueue> edgeQ = new PriorityQueue<>(2*N,
(o1, o2) -> o1.getZ().compareTo(o2.getZ())
);
edgeQ.addAll(mst_edges);
//everyone starts in their own cluster!
List> currentGroups = new ArrayList<>();
for(int i = 0; i < N; i++)
{
IntList il = new IntList(1);
il.add(i);
currentGroups.add(il);
}
int next_cluster_label = 0;
/**
* List of all the cluster options we have found
*/
List> cluster_options = new ArrayList<>();
/**
* Stores a list for each cluster. Each value in the sub list is the
* weight at which that data point was added to the cluster
*/
List entry_size = new ArrayList<>();
DoubleList birthSize = new DoubleList();
DoubleList deathSize = new DoubleList();
List> children = new ArrayList<>();
int[] map_to_cluster_label = new int[N];
Arrays.fill(map_to_cluster_label, -1);
while(!edgeQ.isEmpty())
{
Tuple3 edge = edgeQ.poll();
double weight = edge.getZ();
int from = edge.getX();
int to = edge.getY();
if(to == from)
continue;
UnionFind union_from = ufs.get(from);
UnionFind union_to = ufs.get(to);
int clust_A = union_from.find().getItem();
int clust_B = union_to.find().getItem();
UnionFind clust_A_tmp = union_from.find();
UnionFind clust_B_tmp = union_to.find();
union_from.union(union_to);
int a_size = currentGroups.get(clust_A).size();
int b_size = currentGroups.get(clust_B).size();
int new_size = a_size+b_size;
int mergedClust;
int otherClust;
if(union_from.find().getItem() == clust_A)
{
mergedClust = clust_A;
otherClust = clust_B;
}
else//other way around
{
mergedClust = clust_B;
otherClust = clust_A;
}
if(new_size >= m_clSize && a_size < m_clSize && b_size < m_clSize)
{//birth of a new cluster!
cluster_options.add(currentGroups.get(mergedClust));
DoubleList dl = new DoubleList(new_size);
for(int i = 0; i < new_size; i++)
dl.add(weight);
entry_size.add(dl);
children.add(null);//we have not children!
birthSize.add(weight);
deathSize.add(Double.MAX_VALUE);//we don't know yet
map_to_cluster_label[mergedClust] = next_cluster_label;
next_cluster_label++;
}
else if(new_size >= m_clSize && a_size >= m_clSize && b_size >= m_clSize)
{//birth of a new cluster from the death of two others!
//record the weight that the other two died at
deathSize.set(map_to_cluster_label[mergedClust], weight);
deathSize.set(map_to_cluster_label[otherClust], weight);
//replace with new object so that old references in cluster_options are not altered further
currentGroups.set(mergedClust, new IntList(currentGroups.get(mergedClust)));
cluster_options.add(currentGroups.get(mergedClust));
DoubleList dl = new DoubleList(new_size);
for(int i = 0; i < new_size; i++)
dl.add(weight);
entry_size.add(dl);
children.add(new Pair<>(map_to_cluster_label[mergedClust], map_to_cluster_label[otherClust]));
birthSize.add(weight);
deathSize.add(Double.MAX_VALUE);//we don't know yet
map_to_cluster_label[mergedClust] = next_cluster_label;
next_cluster_label++;
}
else if(new_size >= m_clSize)
{//existing cluster has grown in size, so add the points and record their weight for use later
//index may change, so book keeping update
if(map_to_cluster_label[mergedClust] == -1)//the people being added are the new owners
{
//set to avoid index out of boudns bellow
int c = map_to_cluster_label[mergedClust] = map_to_cluster_label[otherClust];
//make sure we keep track of the correct list
cluster_options.set(c, currentGroups.get(mergedClust));
map_to_cluster_label[otherClust] = -1;
}
for(int indx : currentGroups.get(otherClust))
try
{
entry_size.get(map_to_cluster_label[mergedClust]).add(weight);
}
catch(IndexOutOfBoundsException ex)
{
ex.printStackTrace();
throw new FailedToFitException(ex);
}
}
currentGroups.get(mergedClust).addAll(currentGroups.get(otherClust));
currentGroups.set(otherClust, null);
}
//Remove the last "cluster" because its the dumb one of everything
cluster_options.remove(cluster_options.size()-1);
entry_size.remove(entry_size.size()-1);
birthSize.remove(birthSize.size()-1);
deathSize.remove(deathSize.size()-1);
children.remove(children.size()-1);
/**
* See equation (3) in paper
*/
double[] S = new double[cluster_options.size()];
for(int c = 0; c < S.length; c++)
{
double lambda_min = birthSize.getD(c);
double lambda_max = deathSize.getD(c);
double s = 0;
for(double f_x : entry_size.get(c))
s += Math.min(f_x, lambda_max) - lambda_min;
S[c] = s;
}
boolean[] toKeep = new boolean[S.length];
double[] S_hat = new double[cluster_options.size()];
Arrays.fill(toKeep, true);
Queue notKeeping = new ArrayDeque<>();
for(int i = 0; i < S.length; i++)
{
Pair child = children.get(i);
if(child == null)//I'm a leaf!
{
//for all leaf nodes, set ˆS(C_h)= S(C_h)
S_hat[i] = S[i];
continue;
}
int il = child.getFirstItem();
int ir = child.getSecondItem();
//If S(C_i) < ˆS(C_il)+ ˆ S(C_ir ), set ˆS(C_i)= ˆS(C_il)+ ˆS(C_ir )and set δi =0.
if(S[i] < S_hat[il] + S_hat[ir])
{
S_hat[i] = S_hat[il] + S_hat[ir];
toKeep[i] = false;
}
else//Else: set ˆS(C_i)= S(C_i)and set δ(·) = 0 for all clusters in C_i’s subtrees.
{
S_hat[i] = S[i];
//place children in q to process and set all sub children as not keeping
notKeeping.add(il);
notKeeping.add(ir);
while(!notKeeping.isEmpty())
{
int c = notKeeping.poll();
toKeep[c] = false;
Pair c_children = children.get(c);
if(c_children == null)
continue;
notKeeping.add(c_children.getFirstItem());
notKeeping.add(c_children.getSecondItem());
}
}
}
//initially fill with -1 indicating it was noise
Arrays.fill(designations, 0, N, -1);
int clusters = 0;
for(int c = 0; c < toKeep.length; c++)
if(toKeep[c])
{
for(int indx : cluster_options.get(c))
designations[indx] = clusters;
clusters++;
}
return designations;
}
}
Ads help maintain this website.