EigenCut (S-Space Package 2.0.1 API)

All Known Implementing Classes:

BaseSpectralCut, CKVWSpectralClustering03.SpectralCut, CKVWSpectralClustering06.SuperSpectralCut
```
public interface EigenCut
```
An interface for computing the spectral cut of a Matrix. This interface is based on the spectral clustering algorithm described in the following 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
To briefly summarize, these algorithms take in a data matrix and attempt to recursively split the matrix using a spectral cut accross the according to the link structure of the data points. The algorithm assumes that the data matrix is sparse and uses several optimizations to avoid computing the full affinity matrix in memory, which would be both large and dense. Instead, the algorithm computes the dot product between each data point and the centroid of all data points. These values are then used to scale the data matrix and compute the second eigen vector of the affinity matrix. The second eigen vector is used to find an optimal cut accross the affinity matrix. The "left" side of the cut should be made accessible by getLeftCut and the "right" side of the cut should be made accessible by getRightCut.
Once the data matrix has been split until every data point is in it's own partition, the algorithm merges portions of the tree using one of two objective functions. The first, and most often used, is a relaxed correlation objective function. This method balances inter cluster similarity and intra cluster dissimilarity, with a varying weight between the two scores. getMergedObjective(double, double) and getSplitObjective(double, double, int, int[], int, int[]) compute this objective function, with the first method computing the score when the full data matrix is used and the second method computing the score accross a given set of paritions. The second objective function is the standard k-means objective function. getKMeansObjective() computes this, with one method computing the objective of the data set as a single cluster and the other method computing the objective over a given set of clusters.
Author:

Keith Stevens

See Also:
BaseSpectralCut

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`computeCut(Matrix matrix)` Compute the cut with the lowest conductance for the data set.
`DoubleVector`	`computeRhoSum(Matrix matrix)` Computes the similarity between each data point and centroid of the data set.
`double`	`getKMeansObjective()` Returns the K-Means objective score of the entire data set, i.e.
`double`	`getKMeansObjective(double alpha, double beta, int leftNumClusters, int[] leftAssignments, int rightNumClusters, int[] rightAssignments)` Returns the K-Means objective computed over the two regions computed over the data set.
`Matrix`	`getLeftCut()` Returns the data set in the first (left) region.
`int[]`	`getLeftReordering()` Return the ordering of the first region with respect to the original data set.
`double`	`getMergedObjective(double alpha, double beta)` Returns the score for the relaxed correlation objective over the entire data set, undivided.
`Matrix`	`getRightCut()` Returns the data set in the second (right) region.
`int[]`	`getRightReordering()` Return the ordering of the second region with respect to the original data set.
`double`	`getSplitObjective(double alpha, double beta, int leftNumClusters, int[] leftAssignments, int rightNumClusters, int[] rightAssignments)` Returns the score for the relaxed correlation objective when the data matrix is divided into multiple clusters.
`double`	`rhoSum()` Returns the sum of values in `rho`.

- Method Detail
  - rhoSum
```
double rhoSum()
```
    Returns the sum of values in rho. This is equivalent to sum(matrix * matrix').
  - computeRhoSum
```
DoubleVector computeRhoSum(Matrix matrix)
```
    Computes the similarity between each data point and centroid of the data set. This is essentially the row sums of the affinity matrix for matrix.
  - computeCut
```
void computeCut(Matrix matrix)
```
    Compute the cut with the lowest conductance for the data set. This involves the following main steps:
    1. Computing the second eigen vector of the data set.
    2. Sorting both the eigen vector, and each dimensions corresponding data point, based on the eigen values.
    The resulting regions are accessible by in getLeftCut() and getRightCut().
  - getLeftReordering
```
int[] getLeftReordering()
```
    Return the ordering of the first region with respect to the original data set.
  - getLeftCut
```
Matrix getLeftCut()
```
    Returns the data set in the first (left) region.
  - getRightCut
```
Matrix getRightCut()
```
    Returns the data set in the second (right) region.
  - getRightReordering
```
int[] getRightReordering()
```
    Return the ordering of the second region with respect to the original data set.
  - getKMeansObjective
```
double getKMeansObjective()
```
    Returns the K-Means objective score of the entire data set, i.e. the sum of the similarity between each dataset and the centroid.
  - getKMeansObjective
```
double getKMeansObjective(double alpha,
                        double beta,
                        int leftNumClusters,
                        int[] leftAssignments,
                        int rightNumClusters,
                        int[] rightAssignments)
```
    Returns the K-Means objective computed over the two regions computed over the data set.
  - getSplitObjective
```
double getSplitObjective(double alpha,
                       double beta,
                       int leftNumClusters,
                       int[] leftAssignments,
                       int rightNumClusters,
                       int[] rightAssignments)
```
    Returns the score for the relaxed correlation objective when the data matrix is divided into multiple clusters. The relaxed correlation objective measures both inter-cluster similarity and intra-cluster dissimilarity. A high score means that values with in a cluster are highly similar and each cluster is highly distinct. This is to be used after clustering values in each sub region.
    
    Parameters:
    alpha - The weight given to the inter-cluster similarity.
    beta - The weight given to the intra-cluster similarity.
    leftNumClusters - The number of clusters found in the left split
    leftAssignments - The assignments for data points in the left region
    rightNumClusters - The number of clusters found in the right split
    rightAssignments - The assignments for data points in the right region
  - getMergedObjective
```
double getMergedObjective(double alpha,
                        double beta)
```
    Returns the score for the relaxed correlation objective over the entire data set, undivided.

Interface EigenCut

Method Summary

Method Detail

rhoSum

computeRhoSum

computeCut

getLeftReordering

getLeftCut

getRightCut

getRightReordering

getKMeansObjective

getKMeansObjective

getSplitObjective

getMergedObjective