Spectral and Active Spectral Clustering Framework
Akshay Krishnamurthy

This package contains several algorithms for clustering and hierarchical
clustering of similarity matrices. It also contains some auxiliary routines for
conducting experiments and visualizing/plotting results of these
experiments. Typically datasets are synthetically generated. This document
contains some basic information about each of the files, describing the
available functionality.

PREREQUISITES: To use this package you will need SciPy, NumPy and
Matplotlib. All are open source and readily available online. The most recent
versions should be sufficient.

BEFORE YOU USE THIS PACKAGE: edit settings.py so that LOGDIR, OUTDIR, and FIGDIR
point to read/write-able places on your machine.

THE FILES: 

util.py -- Various utility functions. Some of these are simply shorthands for
simple operations that are used repeatedly. Others are no longer in use.

wordbag.py -- Implements a Bag of Words and a TF-IDF vector for handling text
data.

counting_matrix.py -- This defines two classes: Matrix and CountingMatrix. The
CountingMatrix is useful for keeping track of which observations were used by
any algorithm.

cluster_tree.py -- This defines a ClusterTree object, which is the result of any
clustering computation (hierarchical or non-hierarchical). It maintains various
representations of a (hierarchical) clustering along with functions for
comparing with other cluster trees.

matrices.py -- Some algorithms for generating various structured matrices that
can be fed as input to the clustering algorithms. These typically return a
CountingMatrix, a ClusterTree, and a string representing the name of the
matrix. There are a couple of exceptions so look at the source file.

cluster_alg.py -- this defines the classes ClusterAlg and HClusterAlg, which is
a hierarchical clustering algorithm. All clustering procedures should inherit
from one of these. An HClusterAlg requires a ClusterAlg as a subroutine,
although in some cases this can be overridden. A clustering algorithm should
take as input a similarity matrix along with some optional parameters and
compute a ClusterTree object (defined in cluster_tree.py) which is stored in
Alg.result.

flat_algorithms.py -- Here are implementations of various flat clustering
algorithms. Examples include Unnormalized Spectral Clustering and K-means
clustering. All of these inherit from ClusterAlg

subsample_objects.py -- The active spectral algorithm along with all of the
heuristics used. This exposes the class SOWithHeuristics, which is the flat
clustering algorithm used by HierarchicalSOWithHeuristics and HierarchicalSO
(see below).

hierarchical_algorithms.py -- Here are some implementations of hierarchical
clustering algorithms. They are: HierarchicalSpectral, SingleLinkage,
HierarchicalKmeans, HierarchicalActiveKMeans, HierarchicalSOWithHeuristics (this
is an active version of the hierarchical spectral algorithm), and HierarchicalSO
(without heuristics; again an active version of the hierarchical spectral
algorithm). All of these inherit from HClusterAlg and they return a ClusterTree.

alg_names.py -- just a list of the names of the algorithms.

experiment.py -- A framework for running experiments. Exposes an Experiment
object that is fed an algorithm and can be asked to run various experiments
using that algorithm. Experiments include measuring running time, sample
complexity, noise thresholds, and misclustering rate.

DataLoader.py -- A class for reading in the raw data files generated by the
Experiments. This raw data is fed into the plotting routines.

PlotComparison.py -- A plotting class for generating figures associated with
algorithmic comparisons. This can plot runtime curves, probing complexity
curves, and outlier fraction curves.

PlotThresholds.py -- A plotting class for generating threshold curves for a
specific algorithm.