, V> {
/**
* The logger for this class.
*/
private static final Logging logger = Logging.getLogger(PROCLUS.class);
/**
* Parameter to specify the multiplier for the initial number of medoids, must
* be an integer greater than 0.
*
* Default value: {@code 10}
*
*
* Key: {@code -proclus.mi}
*
*/
public static final OptionID M_I_ID = OptionID.getOrCreateOptionID("proclus.mi", "The multiplier for the initial number of medoids.");
/**
* Parameter to specify the random generator seed.
*/
public static final OptionID SEED_ID = OptionID.getOrCreateOptionID("proclus.seed", "The random number generator seed.");
/**
* Holds the value of {@link #M_I_ID}.
*/
private int m_i;
/**
* Holds the value of {@link #SEED_ID}.
*/
private Long seed;
/**
* Java constructor.
*
* @param k k Parameter
* @param k_i k_i Parameter
* @param l l Parameter
* @param m_i m_i Parameter
* @param seed Random generator seed
*/
public PROCLUS(int k, int k_i, int l, int m_i, Long seed) {
super(k, k_i, l);
this.m_i = m_i;
this.seed = seed;
}
/**
* Performs the PROCLUS algorithm on the given database.
*/
public Clustering run(Database database, Relation relation) throws IllegalStateException {
DistanceQuery distFunc = this.getDistanceQuery(database);
RangeQuery rangeQuery = database.getRangeQuery(distFunc);
final Random random = new Random();
if(seed != null) {
random.setSeed(seed);
}
if(DatabaseUtil.dimensionality(relation) < l) {
throw new IllegalStateException("Dimensionality of data < parameter l! " + "(" + DatabaseUtil.dimensionality(relation) + " < " + l + ")");
}
// TODO: use a StepProgress!
// initialization phase
if(logger.isVerbose()) {
logger.verbose("1. Initialization phase...");
}
int sampleSize = Math.min(relation.size(), k_i * k);
DBIDs sampleSet = DBIDUtil.randomSample(relation.getDBIDs(), sampleSize, random.nextLong());
int medoidSize = Math.min(relation.size(), m_i * k);
DBIDs medoids = greedy(distFunc, sampleSet, medoidSize, random);
if(logger.isDebugging()) {
StringBuffer msg = new StringBuffer();
msg.append("\n");
msg.append("sampleSize ").append(sampleSize).append("\n");
msg.append("sampleSet ").append(sampleSet).append("\n");
msg.append("medoidSize ").append(medoidSize).append("\n");
msg.append("m ").append(medoids).append("\n");
logger.debugFine(msg.toString());
}
// iterative phase
if(logger.isVerbose()) {
logger.verbose("2. Iterative phase...");
}
double bestObjective = Double.POSITIVE_INFINITY;
ModifiableDBIDs m_best = null;
ModifiableDBIDs m_bad = null;
ModifiableDBIDs m_current = initialSet(medoids, k, random);
if(logger.isDebugging()) {
StringBuffer msg = new StringBuffer();
msg.append("\n");
msg.append("m_c ").append(m_current).append("\n");
logger.debugFine(msg.toString());
}
IndefiniteProgress cprogress = logger.isVerbose() ? new IndefiniteProgress("Current number of clusters:", logger) : null;
Map clusters = null;
int loops = 0;
while(loops < 10) {
Map> dimensions = findDimensions(m_current, relation, distFunc, rangeQuery);
clusters = assignPoints(dimensions, relation);
double objectiveFunction = evaluateClusters(clusters, dimensions, relation);
if(objectiveFunction < bestObjective) {
// restart counting loops
loops = 0;
bestObjective = objectiveFunction;
m_best = m_current;
m_bad = computeBadMedoids(clusters, (int) (relation.size() * 0.1 / k));
}
m_current = computeM_current(medoids, m_best, m_bad, random);
loops++;
if(cprogress != null) {
cprogress.setProcessed(clusters.size(), logger);
}
}
if(cprogress != null) {
cprogress.setCompleted(logger);
}
// refinement phase
if(logger.isVerbose()) {
logger.verbose("3. Refinement phase...");
}
List>> dimensions = findDimensions(new ArrayList(clusters.values()), relation);
List finalClusters = finalAssignment(dimensions, relation);
// build result
int numClusters = 1;
Clustering result = new Clustering("ProClus clustering", "proclus-clustering");
for(PROCLUSCluster c : finalClusters) {
Cluster cluster = new Cluster(c.objectIDs);
cluster.setModel(new SubspaceModel(new Subspace(c.getDimensions()), c.centroid));
cluster.setName("cluster_" + numClusters++);
result.addCluster(cluster);
}
return result;
}
/**
* Returns a piercing set of k medoids from the specified sample set.
*
* @param distFunc the distance function
* @param sampleSet the sample set
* @param m the number of medoids to be returned
* @param random random number generator
* @return a piercing set of m medoids from the specified sample set
*/
private ModifiableDBIDs greedy(DistanceQuery distFunc, DBIDs sampleSet, int m, Random random) {
ArrayModifiableDBIDs s = DBIDUtil.newArray(sampleSet);
ModifiableDBIDs medoids = DBIDUtil.newHashSet();
// m_1 is random point of S
DBID m_i = s.remove(random.nextInt(s.size()));
medoids.add(m_i);
if(logger.isDebugging()) {
logger.debugFiner("medoids " + medoids);
}
// compute distances between each point in S and m_i
Map> distances = new HashMap>();
for(DBID id : s) {
DoubleDistance dist = distFunc.distance(id, m_i);
distances.put(id, new GenericDistanceResultPair(dist, id));
}
for(int i = 1; i < m; i++) {
// choose medoid m_i to be far from prevois medoids
List> d = new ArrayList>(distances.values());
Collections.sort(d);
m_i = d.get(d.size() - 1).getDBID();
medoids.add(m_i);
s.remove(m_i);
distances.remove(m_i);
// compute distances of each point to closest medoid
for(DBID id : s) {
DoubleDistance dist_new = distFunc.distance(id, m_i);
DoubleDistance dist_old = distances.get(id).getDistance();
DoubleDistance dist = dist_new.compareTo(dist_old) < 0 ? dist_new : dist_old;
distances.put(id, new GenericDistanceResultPair(dist, id));
}
if(logger.isDebugging()) {
logger.debugFiner("medoids " + medoids);
}
}
return medoids;
}
/**
* Returns a set of k elements from the specified sample set.
*
* @param sampleSet the sample set
* @param k the number of samples to be returned
* @param random random number generator
* @return a set of k elements from the specified sample set
*/
private ModifiableDBIDs initialSet(DBIDs sampleSet, int k, Random random) {
ArrayModifiableDBIDs s = DBIDUtil.newArray(sampleSet);
ModifiableDBIDs initialSet = DBIDUtil.newHashSet();
while(initialSet.size() < k) {
DBID next = s.remove(random.nextInt(s.size()));
initialSet.add(next);
}
return initialSet;
}
/**
* Computes the set of medoids in current iteration.
*
* @param m the medoids
* @param m_best the best set of medoids found so far
* @param m_bad the bad medoids
* @param random random number generator
* @return m_current, the set of medoids in current iteration
*/
private ModifiableDBIDs computeM_current(DBIDs m, DBIDs m_best, DBIDs m_bad, Random random) {
ArrayModifiableDBIDs m_list = DBIDUtil.newArray(m);
for(DBID m_i : m_best) {
m_list.remove(m_i);
}
ModifiableDBIDs m_current = DBIDUtil.newHashSet();
for(DBID m_i : m_best) {
if(m_bad.contains(m_i)) {
int currentSize = m_current.size();
while(m_current.size() == currentSize) {
DBID next = m_list.remove(random.nextInt(m_list.size()));
m_current.add(next);
}
}
else {
m_current.add(m_i);
}
}
return m_current;
}
/**
* Computes the localities of the specified medoids: for each medoid m the
* objects in the sphere centered at m with radius minDist are determined,
* where minDist is the minimum distance between medoid m and any other medoid
* m_i.
*
* @param medoids the ids of the medoids
* @param database the database holding the objects
* @param distFunc the distance function
* @return a mapping of the medoid's id to its locality
*/
private Map>> getLocalities(DBIDs medoids, Relation database, DistanceQuery distFunc, RangeQuery rangeQuery) {
Map>> result = new HashMap>>();
for(DBID m : medoids) {
// determine minimum distance between current medoid m and any other
// medoid m_i
DoubleDistance minDist = null;
for(DBID m_i : medoids) {
if(m_i == m) {
continue;
}
DoubleDistance currentDist = distFunc.distance(m, m_i);
if(minDist == null || currentDist.compareTo(minDist) < 0) {
minDist = currentDist;
}
}
// determine points in sphere centered at m with radius minDist
assert minDist != null;
List> qr = rangeQuery.getRangeForDBID(m, minDist);
result.put(m, qr);
}
return result;
}
/**
* Determines the set of correlated dimensions for each medoid in the
* specified medoid set.
*
* @param medoids the set of medoids
* @param database the database containing the objects
* @param distFunc the distance function
* @return the set of correlated dimensions for each medoid in the specified
* medoid set
*/
private Map> findDimensions(DBIDs medoids, Relation database, DistanceQuery distFunc, RangeQuery rangeQuery) {
// get localities
Map>> localities = getLocalities(medoids, database, distFunc, rangeQuery);
// compute x_ij = avg distance from points in l_i to medoid m_i
int dim = DatabaseUtil.dimensionality(database);
Map averageDistances = new HashMap();
for(DBID m_i : medoids) {
V medoid_i = database.get(m_i);
List> l_i = localities.get(m_i);
double[] x_i = new double[dim];
for(DistanceResultPair qr : l_i) {
V o = database.get(qr.getDBID());
for(int d = 0; d < dim; d++) {
x_i[d] += Math.abs(medoid_i.doubleValue(d + 1) - o.doubleValue(d + 1));
}
}
for(int d = 0; d < dim; d++) {
x_i[d] /= l_i.size();
}
averageDistances.put(m_i, x_i);
}
Map> dimensionMap = new HashMap>();
List> z_ijs = new ArrayList>();
for(DBID m_i : medoids) {
Set dims_i = new HashSet();
dimensionMap.put(m_i, dims_i);
double[] x_i = averageDistances.get(m_i);
// y_i
double y_i = 0;
for(int j = 0; j < dim; j++) {
y_i += x_i[j];
}
y_i /= dim;
// sigma_i
double sigma_i = 0;
for(int j = 0; j < dim; j++) {
double diff = x_i[j] - y_i;
sigma_i += diff * diff;
}
sigma_i /= (dim - 1);
sigma_i = Math.sqrt(sigma_i);
for(int j = 0; j < dim; j++) {
z_ijs.add(new CTriple((x_i[j] - y_i) / sigma_i, m_i, j + 1));
}
}
Collections.sort(z_ijs);
int max = Math.max(k * l, 2);
for(int m = 0; m < max; m++) {
CTriple z_ij = z_ijs.get(m);
Set dims_i = dimensionMap.get(z_ij.getSecond());
dims_i.add(z_ij.getThird());
if(logger.isDebugging()) {
StringBuffer msg = new StringBuffer();
msg.append("\n");
msg.append("z_ij ").append(z_ij).append("\n");
msg.append("D_i ").append(dims_i).append("\n");
logger.debugFiner(msg.toString());
}
}
return dimensionMap;
}
/**
* Refinement step that determines the set of correlated dimensions for each
* cluster centroid.
*
* @param clusters the list of clusters
* @param database the database containing the objects
* @return the set of correlated dimensions for each specified cluster
* centroid
*/
private List>> findDimensions(List clusters, Relation database) {
// compute x_ij = avg distance from points in c_i to c_i.centroid
int dim = DatabaseUtil.dimensionality(database);
Map averageDistances = new HashMap();
for(int i = 0; i < clusters.size(); i++) {
PROCLUSCluster c_i = clusters.get(i);
double[] x_i = new double[dim];
for(DBID id : c_i.objectIDs) {
V o = database.get(id);
for(int d = 0; d < dim; d++) {
x_i[d] += Math.abs(c_i.centroid.doubleValue(d + 1) - o.doubleValue(d + 1));
}
}
for(int d = 0; d < dim; d++) {
x_i[d] /= c_i.objectIDs.size();
}
averageDistances.put(i, x_i);
}
List> z_ijs = new ArrayList>();
for(int i = 0; i < clusters.size(); i++) {
double[] x_i = averageDistances.get(i);
// y_i
double y_i = 0;
for(int j = 0; j < dim; j++) {
y_i += x_i[j];
}
y_i /= dim;
// sigma_i
double sigma_i = 0;
for(int j = 0; j < dim; j++) {
double diff = x_i[j] - y_i;
sigma_i += diff * diff;
}
sigma_i /= (dim - 1);
sigma_i = Math.sqrt(sigma_i);
for(int j = 0; j < dim; j++) {
z_ijs.add(new CTriple((x_i[j] - y_i) / sigma_i, i, j + 1));
}
}
Collections.sort(z_ijs);
// mapping cluster index -> dimensions
Map> dimensionMap = new HashMap>();
int max = Math.max(k * l, 2);
for(int m = 0; m < max; m++) {
CTriple z_ij = z_ijs.get(m);
Set dims_i = dimensionMap.get(z_ij.getSecond());
if(dims_i == null) {
dims_i = new HashSet();
dimensionMap.put(z_ij.getSecond(), dims_i);
}
dims_i.add(z_ij.getThird());
if(logger.isDebugging()) {
StringBuffer msg = new StringBuffer();
msg.append("\n");
msg.append("z_ij ").append(z_ij).append("\n");
msg.append("D_i ").append(dims_i).append("\n");
logger.debugFiner(msg.toString());
}
}
// mapping cluster -> dimensions
List>> result = new ArrayList>>();
for(int i : dimensionMap.keySet()) {
Set dims_i = dimensionMap.get(i);
PROCLUSCluster c_i = clusters.get(i);
result.add(new Pair>(c_i.centroid, dims_i));
}
return result;
}
/**
* Assigns the objects to the clusters.
*
* @param dimensions set of correlated dimensions for each medoid of the
* cluster
* @param database the database containing the objects
* @return the assignments of the object to the clusters
*/
private Map assignPoints(Map> dimensions, Relation database) {
Map clusterIDs = new HashMap();
for(DBID m_i : dimensions.keySet()) {
clusterIDs.put(m_i, DBIDUtil.newHashSet());
}
for(Iterator it = database.iterDBIDs(); it.hasNext();) {
DBID p_id = it.next();
V p = database.get(p_id);
DistanceResultPair minDist = null;
for(DBID m_i : dimensions.keySet()) {
V m = database.get(m_i);
DistanceResultPair currentDist = new GenericDistanceResultPair(manhattanSegmentalDistance(p, m, dimensions.get(m_i)), m_i);
if(minDist == null || currentDist.compareTo(minDist) < 0) {
minDist = currentDist;
}
}
// add p to cluster with mindist
assert minDist != null;
ModifiableDBIDs ids = clusterIDs.get(minDist.getDBID());
ids.add(p_id);
}
Map clusters = new HashMap();
for(DBID m_i : dimensions.keySet()) {
ModifiableDBIDs objectIDs = clusterIDs.get(m_i);
if(!objectIDs.isEmpty()) {
Set clusterDimensions = dimensions.get(m_i);
V centroid = DatabaseUtil.centroid(database, objectIDs);
clusters.put(m_i, new PROCLUSCluster(objectIDs, clusterDimensions, centroid));
}
}
if(logger.isDebugging()) {
StringBuffer msg = new StringBuffer();
msg.append("\n");
msg.append("clusters ").append(clusters).append("\n");
logger.debugFine(msg.toString());
}
return clusters;
}
/**
* Refinement step to assign the objects to the final clusters.
*
* @param dimensions pair containing the centroid and the set of correlated
* dimensions for the centroid
* @param database the database containing the objects
* @return the assignments of the object to the clusters
*/
private List finalAssignment(List>> dimensions, Relation database) {
Map clusterIDs = new HashMap();
for(int i = 0; i < dimensions.size(); i++) {
clusterIDs.put(i, DBIDUtil.newHashSet());
}
for(Iterator it = database.iterDBIDs(); it.hasNext();) {
DBID p_id = it.next();
V p = database.get(p_id);
Pair minDist = null;
for(int i = 0; i < dimensions.size(); i++) {
Pair> pair_i = dimensions.get(i);
V c_i = pair_i.first;
Set dimensions_i = pair_i.second;
DoubleDistance currentDist = manhattanSegmentalDistance(p, c_i, dimensions_i);
if(minDist == null || currentDist.compareTo(minDist.first) < 0) {
minDist = new Pair(currentDist, i);
}
}
// add p to cluster with mindist
assert minDist != null;
ModifiableDBIDs ids = clusterIDs.get(minDist.second);
ids.add(p_id);
}
List clusters = new ArrayList();
for(int i = 0; i < dimensions.size(); i++) {
ModifiableDBIDs objectIDs = clusterIDs.get(i);
if(!objectIDs.isEmpty()) {
Set clusterDimensions = dimensions.get(i).second;
V centroid = DatabaseUtil.centroid(database, objectIDs);
clusters.add(new PROCLUSCluster(objectIDs, clusterDimensions, centroid));
}
}
if(logger.isDebugging()) {
StringBuffer msg = new StringBuffer();
msg.append("\n");
msg.append("clusters ").append(clusters).append("\n");
logger.debugFine(msg.toString());
}
return clusters;
}
/**
* Returns the Manhattan segmental distance between o1 and o2 relative to the
* specified dimensions.
*
* @param o1 the first object
* @param o2 the second object
* @param dimensions the dimensions to be considered
* @return the Manhattan segmental distance between o1 and o2 relative to the
* specified dimensions
*/
private DoubleDistance manhattanSegmentalDistance(V o1, V o2, Set dimensions) {
double result = 0;
for(Integer d : dimensions) {
result += Math.abs(o1.doubleValue(d) - o2.doubleValue(d));
}
result /= dimensions.size();
return new DoubleDistance(result);
}
/**
* Evaluates the quality of the clusters.
*
* @param clusters the clusters to be evaluated
* @param dimensions the dimensions associated with each cluster
* @param database the database holding the objects
* @return a measure for the cluster quality
*/
private double evaluateClusters(Map clusters, Map> dimensions, Relation database) {
double result = 0;
for(DBID m_i : clusters.keySet()) {
PROCLUSCluster c_i = clusters.get(m_i);
V centroid_i = c_i.centroid;
Set dims_i = dimensions.get(m_i);
double w_i = 0;
for(Integer j : dims_i) {
w_i += avgDistance(centroid_i, c_i.objectIDs, database, j);
}
w_i /= dimensions.keySet().size();
result += c_i.objectIDs.size() * w_i;
}
return result / database.size();
}
/**
* Computes the average distance of the objects to the centroid along the
* specified dimension.
*
* @param centroid the centroid
* @param objectIDs the set of objects ids
* @param database the database holding the objects
* @param dimension the dimension for which the average distance is computed
* @return the average distance of the objects to the centroid along the
* specified dimension
*/
private double avgDistance(V centroid, DBIDs objectIDs, Relation database, int dimension) {
double avg = 0;
for(DBID objectID : objectIDs) {
V o = database.get(objectID);
avg += Math.abs(centroid.doubleValue(dimension) - o.doubleValue(dimension));
}
return avg / objectIDs.size();
}
/**
* Computes the bad medoids, where the medoid of a cluster with less than the
* specified threshold of objects is bad.
*
* @param clusters the clusters
* @param threshold the threshold
* @return the bad medoids
*/
private ModifiableDBIDs computeBadMedoids(Map clusters, int threshold) {
ModifiableDBIDs badMedoids = DBIDUtil.newHashSet();
for(DBID m_i : clusters.keySet()) {
PROCLUSCluster c_i = clusters.get(m_i);
if(c_i.objectIDs.size() < threshold) {
badMedoids.add(m_i);
}
}
return badMedoids;
}
@Override
public TypeInformation[] getInputTypeRestriction() {
return TypeUtil.array(TypeUtil.NUMBER_VECTOR_FIELD);
}
@Override
protected Logging getLogger() {
return logger;
}
/**
* Encapsulates the attributes of a cluster.
*
* @apiviz.exclude
*/
private class PROCLUSCluster {
/**
* The ids of the objects belonging to this cluster.
*/
ModifiableDBIDs objectIDs;
/**
* The correlated dimensions of this cluster.
*/
Set dimensions;
/**
* The centroids of this cluster along each dimension.
*/
V centroid;
/**
* Provides a new cluster with the specified parameters.
*
* @param objectIDs the ids of the objects belonging to this cluster
* @param dimensions the correlated dimensions of this cluster
* @param centroid the centroid of this cluster
*/
public PROCLUSCluster(ModifiableDBIDs objectIDs, Set dimensions, V centroid) {
this.objectIDs = objectIDs;
this.dimensions = dimensions;
this.centroid = centroid;
}
@Override
public String toString() {
StringBuffer result = new StringBuffer();
result.append("Dimensions: [");
boolean notFirst = false;
for(Integer d : dimensions) {
if(notFirst) {
result.append(",");
}
else {
notFirst = true;
}
result.append(d);
}
result.append("]");
result.append("\nCentroid: ").append(centroid);
return result.toString();
}
/**
* Returns the correlated dimensions of this cluster as BitSet.
*
* @return the correlated dimensions of this cluster as BitSet
*/
public BitSet getDimensions() {
BitSet result = new BitSet();
for(int d : dimensions) {
result.set(d - 1);
}
return result;
}
}
/**
* Parameterization class.
*
* @author Erich Schubert
*
* @apiviz.exclude
*/
public static class Parameterizer> extends AbstractProjectedClustering.Parameterizer {
protected int m_i = -1;
protected Long seed = null;
@Override
protected void makeOptions(Parameterization config) {
super.makeOptions(config);
configK(config);
configKI(config);
configL(config);
IntParameter m_iP = new IntParameter(M_I_ID, 10);
m_iP.addConstraint(new GreaterConstraint(0));
if(config.grab(m_iP)) {
m_i = m_iP.getValue();
}
LongParameter seedP = new LongParameter(SEED_ID, true);
if(config.grab(seedP)) {
seed = seedP.getValue();
}
}
@Override
protected PROCLUS makeInstance() {
return new PROCLUS(k, k_i, l, m_i, seed);
}
}
}