edu.ucla.sspace.clustering

Class SpectralClustering

java.lang.Object

edu.ucla.sspace.clustering.SpectralClustering

public class SpectralClustering
extends Object

Implementation of Spectral Clustering using divide and merge methodology. The implementation is based on two papers:

• Cheng, D., Kannan, R., Vempala, S., Wang, G. (2006). A Divide-and-Merge Methodology for Clustering. ACM Transactions on Database Systsms, 31, 1499-1525. Available here
• Kannan, R., Vempala, S., Vetta, A. (2000). On clustering: Good, bad, and spectral. FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science Available here

This class utilizes a EigenCut instance to compute a spectral partition of a dataset. Given a single data set, it will recursively partition that data set using a EigenCut instance until one of two limits: all data points are in a unique cluster, or the maximum number of partitions have been made, as set by the number of clusters. Once all paritions are made, neighboring paritions may be merged according to the objective scores returned by the EigenCut instance. If cluster(Matrix, int) is used, the requested number of clusters, or fewer, will be returned, otherwise the algorithm will decide on the correct number of clusters.

Author:

Keith Stevens

See Also:

EigenCut, BaseSpectralCut

Constructor Summary

Constructors

Constructor and Description
SpectralClustering(double alpha, Generator<EigenCut> cutterGenerator) Creates a new SpectralClustering instance.

Method Summary

Methods

Modifier and Type	Method and Description
Assignments	cluster(Matrix matrix) Returns the Cluster Assignments of each data point in matrix.
Assignments	cluster(Matrix matrix, int maxClusters, boolean useKMeans) Returns the Cluster for each data point in matrix.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SpectralClustering

public SpectralClustering(double alpha,
                  Generator<EigenCut> cutterGenerator)

Creates a new SpectralClustering instance.

Parameters:

alpha - The weight given to inter cluster similarity for the relaxed correlation objective function. beta will be set to - alpha.

cutterGenerator - A Generator of EigenCut instances.

Method Detail

cluster

public Assignments cluster(Matrix matrix)

Returns the Cluster Assignments of each data point in matrix. This method will determine a "good" number of clusters algorithmiclly. This method also uses the relaxed correlation objective function, as the k-means objective function would always keep each data point in it's own cluster.

cluster

public Assignments cluster(Matrix matrix,
                  int maxClusters,
                  boolean useKMeans)

Returns the Cluster for each data point in matrix. This method will return at most maxClusters. If useKMeans is true, the K-means objective function is used to merge clusters, otherwise the relaxed correlation function is used.