\section{Clustering Methods}

\subsection{Motivation}

The previous section discussed various sampling methods for choosing the most useful queries in an active learning system and their strengths (situations in which they might excel) and weaknesses (queries required for a proper analysis.)  We would clearly benefit from using clustering techniques to identify areas of interest and ensure that we further achieve the goal of balancing exploration and exploitation.  Our ideal clustering algorithm would have low asymptotic complexity while providing a optimal grouping of similar data points. 

\subsection{k-means}

\begin{figure}[htb]
\caption{Pseudo-code for K-means Algorithm}
\label{algorithm:Kmeans}
\includegraphics[scale=0.6]{KmeansAlgorithm.eps}
%\input{KmeansAlgorithm}
\end{figure}

K-means is a clustering algorithm that seeks to partition points into k clusters with the nearest mean point.  The k-means algorithm has an asymptotic complexity of O(kN) where k is the number of clusters and N is the number of data points in the input set.  K-means has an attractive complexity, but it is important to note that the algorithm may have to be executed multiple times to find the best value of k for the given data.

\subsection{GenIc}

\begin{figure}[h!]
\caption{Pseudo-code for GenIc Algorithm \cite{Gupta04}}
\label{algorithm:GenIc}
\includegraphics[scale=0.6]{GenIcAlgorithm.eps}
%\input{GenIcAlgorithm}
\end{figure}

GenIc (GENeralized Incremental Algorithm for Clustering) is a clustering algorithm developed specifically to analyze streaming data.  The assumption is that streaming data (data that is arriving in real time) can only be analyzed once, so GenIc has a low time complexity of $O(n)$ where n  is the number of input data records\cite{Gupta04}  GenIc is also an incremental algorithm meaning that the clusters can be updated as sets of data points referred to as \textbf{generations} arrive over time.

GenIc computes the "fitness" of each each center as a function of the number of points assigned to the center.  The algorithm computes the probability of the center's survival\ref{algorithm:GenIc} and randomly selects a value between 0 and 1 from a uniform distribution to determine if a center is removed.  The fittest generally survive to the next generation, but old centers are occasionally replaced with new centers.

\subsection{Canopy}

\begin{figure}[htb]
\caption{An example of five canopies \cite{McCallum00}}
\label{fig:Canopies}
\includegraphics[scale=0.6]{canopies.eps}
\end{figure}

The canopy clustering technique is a technique that addresses situations where there can be a large number of points in the data set, each point can have many features, and there can be many clusters to discover in the data set.  The canopy seeks to solve all three problems by dividing the clustering into a two stage process.  

The first stage uses some cheap distance or similarity measure to create overlapping subsets called "canopies."  Canopies are defined to be a subset of points that are calculated by some estimated distance or similarity measure to be within some distance threshold from a central point \cite{McCallum00}.  Points may reside in multiple canopies (canopies may overlap), but all points must reside in at least one canopy. An assumption is made that points that are not in the same canopy can not be in the same cluster.  

Figure \ref{fig:Canopies} illustrates an example provided by McCullen et. al. \cite{McCullen00} of five clusters and their canopies. A solid circle indicates the outer thresholds of the canopy. Points labeled A, B, C, D, and E are the center points of the canopies.  The doted circles within each canopy designate an area is excluded for consideration to be the center of a new canopy.  

The second stage uses a traditional clustering algorithm such as K-means using an accurate distance or similarity measure with the restriction that we only measure distances between points that reside in the same canopy (and assume points of different canopies to have an infinite distance).  

McCullen states that the canopy technique requires at most $O(\frac{f^2n^2}{c})$ distance measures where $n$ is the number of data points, $f$ is the average number of canopies in which each data point resides, and  $c$ is the number of canopies in use.  McCullen also states that $f$ will generally be much less than $c$.  Canopy with K-means as the second stage clustering technique requires $O(\frac{n*k*f^2}{c})$ per iteration \cite{McCullen00}.

\subsection{Compass}

\begin{figure}[htb]
\caption{Pseudo-code for Compass Clustering Algorithm}
\label{algorithm:Compass}
\includegraphics[scale=0.6]{CompassAlgorithm.eps}
%\input{CompassAlgorithm}
\end{figure}

Compass is a clustering algorithm that works by finding two points with a maximum distance from the other in the data set and build a tree structure by pulling data to each of the two extreme points to form two sets. We then recurse on each set until the variance between the layers is less than a determined threshold. The Compass algorithm is very simple, and thus is very quick.  The algorithm's complexity is O(3LN) where L is the number of layers and N is the number of input points.  Further research is in progress to investigate the inclusion of early stopping rules in the algorithm to reduce the number of layers of the tree.

\subsection{Comparison of Clustering Techniques}

A fast clustering algorithm has several advantages over a slower clustering algorithm such as Greedy Agglomerative Clustering (GAC) which promises a computational complexity of $O(n^2)$.   GAC and other clustering algorithms with large computational complexities do not scale well to large data sets. We attempt to investigate clustering algorithms that minimize the computational complexity while still providing an acceptable clustering of the data set.
 
k-Means can provide a more reasonable time investment for a single execution of the  algorithm, but the algorithm may be ran multiple times in order to find the best number of k clusters to fit the data set.  The worst case time of O(3LN) and ability to be updated incrementally makes Compass a strong candidate with respect to computational complexity.

\begin{table}[h!]
	\begin{center}
		\begin{tabular}{| c | c | c | c | c |}
		\hline
		Reducer and Clusterer & Time & InterSim & IntraSim & Gain \\
		\hline
		TF-IDF*K-means & 17.52 & -0.085 & 141.73 & 141.82 \\
		\hline
		TF-IDF*GenIc & 3.75 & -0.14 & 141.22 & 141.36 \\
		\hline
		PCA*K-means & 100.0 & 0.0 & 100.0 & 100.0 \\
		\hline
		PCA*Canopy & 117.49 & 0.0 & 99.87 & 99.87 \\
		\hline
		PCA*GenIc & 11.71 & -0.07 & 99.74 & 99.81 \\
		\hline
		TF-IDF*Canopy & 6.58 & 5.02 & 93.42 & 88.4 \\
		\hline
		\end{tabular}
	\end{center}
	\caption{Results from a text mining experiment comparing combinations of  feature subset reduction and clustering algorithms to more sophisticated methods.}
	\label{tab:ReducerCluster}
	\end{table} 

\begin{table}[h!]
	\begin{center}
		\begin{tabular}{| c | c | c | c|}
		\hline
		Method & Win & Loss & Tie \\
		\hline
		COMPASS & 180 & 0 & 0 \\
BestK & 100 & 46 & 34 \\                                                                                                                                                                          
K=16 & 157 & 20 & 3 \\                                                                                                                                                                            
K=8 & 142 & 25 & 13 \\                                                                                                                                                                            
K=4 & 115 & 40 & 25 \\                                                                                                                                                                             
K=2 & 71 & 70 & 39     \\                                                                                                                                                                         
K=1 & 62 & 82 & 36 \\                                                                                                                                                                              
BISECT4 & 1 & 76 & 103 \\                                                                                                                                                               
BISECT6 & 30 & 44 & 106 \\                                                                                                                                                                    
BISECT8 & 36 & 39 & 105 \\
		\hline
		\end{tabular}
	\end{center}
	\caption{Win-Loss-Tie Results for the COCOMO81 Data Set}
	\label{tab:COCOMO81}
\end{table}

\begin{table}[h!]
\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
Method & Win & Loss & Tie \\
\hline                                                                                                                                                                                                   
COMPASS & 171 & 8 & 1  \\                                                                                                                                                             
BestK & 109 & 7 & 64\\                                                                                                                                                                  
K=16 & 125 & 1 & 54\\                                                                                                                                                                
K=8 & 113 & 6 & 61\\                                                                                                                                                           
K=4 & 77 & 13 & 90\\                                                                                                                                                       
K=2 & 162 & 0 & 18\\                                                                                                                                                   
K=1 & 79 & 10 & 91\\                                                                                                                                               
BISECT4 & 0 & 178 & 2 \\                                                                                                                                            
BISECT6 & 31 & 85 & 64\\                                                                                                                                         
BISECT8 & 29 & 86 & 65 \\
\hline
\end{tabular}
\end{center}
\caption{Win-Loss-Tie Results for the Maxwell Data Set}
\label{tab:Maxwell}
\end{table}		

We find in our studies that the Compass clustering algorithm performs significantly better in most cases than k-means and bisection methods. \ref{tab:COCOMO81} and \ref{tab:Maxwell} provide a Win-Tie-Loss (\ref{WinTieLoss}) comparison of three clustering methods with varying $k$ clusters based on the magnitude of the relative error (MRE)\cite{Foss}:   
\begin{quotation}
$MRE = \frac{|actual_i - predicted_i|}{actual_i}$ 
\end{quotation}
Foss et al. has demonstrated that using only MRE can lead to an incorrect evaluation of the results in certain situations \cite{Foss}. Wilcoxon statistics were applied to ensure that these results do not fall into the limitations of MRE.
Compass performs significantly better than K-means and bisecting K-means on both data sets. Compass is a very promising algorithm that can provide a small computational complexity while delivering high quality clusters. 

\begin{figure}
\caption{Pseudo-code for Win-Tie-Loss calculation between variants $i$ and $j$}
\label{WinTieLoss}
\includegraphics[scale=0.6]{WinLossTie.eps}
%\input{winLossTie}
\end{figure}