This chapter describes the laboratory studies performed throughout this research.  
There are a total of three main experiments that assess the run-time and 
accuracy in the following areas: term-space reduction (section \ref{s:reduction}), 
document clustering (section \ref{s:clustering}), and 
document clustering using using all pairs of reduction methods and clusterers (section \ref{s:combinations}).  
In each experiments section we discuss the procedures used, run-time results, validity (accuracy) results, 
effects of variables, and a look at the observed trade-offs.

Section \ref{s:basics} lists the basic setup of the experiments including
the datasets and algorithms used, evaluation metrics, parameters being varied and parameters
held constant, and some initial expectations.  Section \ref{s:environment} details
the testing environment and experimental design.  Lastly, section \ref{s:findings} captures
the summary of all relevant findings of our research.



\section{Basics}
\label{s:basics}

\subsection {Datasets}
\label{s:datasets}

The datasets chosen for these experiments listed in figure \ref{tab:datasetstats}, fall into two categories: supervised and unsupervised.  
Consequently, all supervised datasets used are standard and freely available text mining 
collections primarily in the form of news articles and newsgroup posts. Our unsupervised
datasets were created in-house from collections of two STEP/EXPRESS application protocols that
are highly syntactic in nature and help fulfill our primary motivations described in section \ref{i:motivation}.
See figure \ref{tab:datasetstats} for a listing of datasets and relevant statistics.

\begin{table}[!h]{\small
\begin{center}
\begin{tabular}{|p{3.75cm}||r@{~}|r@{~}|r@{~}|r@{~}|r@{~}|r@{~}|r@{~}|r|}\hline
Documents                & AP203 & AP214 & BBC  & BBCSport  & ngBias3 & ngBias8 & ngBal3 & ngBal8 \\\hline
$D$ documents            & 484   & 1373  & 2224 & 737        & 1500    & 2395    & 1499   & 3999   \\
$T$ terms                & 1103  & 3050  & 9635 & 4613       & 8631    & 9826    & 8158   & 14984  \\
Mean document length     & 143   & 164   &  130 & 104        & 116     & 87      & 91     & 90     \\
Natural Classes			 & N/A   & N/A   & 5    & 5          & 3       & 8       & 3      & 8 \\
Stemming used            & -   & -   &  x & x        & x     & x      & x     & x     \\
Stop-words removed       & -   & -   &  x & x        & x     & x      & x     & x     \\\hline
\end{tabular}
\end{center}}
\caption{Statistics on our datasets.}\label{tab:datasetstats}
\end{table}


\begin{table}[!h]{\small
\begin{center}
\begin{tabular}{|l|p{10cm}|}\hline
{\bf Dataset}                & {\bf Natural classes} \\\hline
BBC            & business(509), entertainment(386), politics(417), sport(511), tech(302) \\\hline
BBCSport       & athletics(100), cricket(124), football(265), rugby(147), tennis(57) \\\hline
ngBias3      & graphics(136), hockey(591), windows(587) \\\hline
ngBias8		 & atheism(704), autos(202), crypt(204), hockey(205), mac(202), mideast(202), space(204), xwindows(205) \\\hline
ngBal3       &  graphics(463), hockey(459), mideast(453)\\\hline
ngBal8       &  atheism(471), autos(463), crypt(467), hockey(461), mac(466), mideast(470), space(461), xwindows(469)\\\hline
\end{tabular}
\end{center}}
\caption{Supervised datasets along with class values.}\label{tab:datasetclasses}
\end{table}

All datasets other than AP203 and AP214 (both of which were generated for this project) were 
found at the Machine Learning Group of University College Dublin website \cite{mlgUcd}.
The BBC and BBCSport datasets were first introduced in \cite{greene06icml}.  BBC is made up
news articles taken from the BBC website from 2004-2005, similarly BBCSport is made up of 
news articles from the BBCSport website during the same time period.  Each contains 5 
natural classes that identify the articles topical area.  The remaining datasets are
all subsets of the 20Newsgroups dataset introduced in \cite{Lang95} and currently
residing in the UCI KDD Archive \cite{bay00uci}.  Both ngBias3 and ngBias8 come datasets
with uneven class frequencies.  In ngBias3, two classes each represent approximately 45\% of the documents,
 while the other only represents approximately 10\%.  In ngBias8, 7 classes each represent approximately 9\%
of the documents, while the remaining class represents approximately 33\%.  In both
ngBal3 and ngBal8 the distribution of class frequencies is approximately equal.  
See figure \ref{tab:datasetclasses} for exact distributions.  All of the 
20Newsgroups subsets used in this study have well-separated classes, meaning they
were chosen in such as way as to minimize overlap between classes.

Both the 20Newsgroups and BBC datasets were chosen because of their previous use in the literature 
that allows us to draw a comparison to a known benchmark.  As of May 2009, the 20Newsgroups
introductory paper \cite{Lang95} has been cited over 200 times according to CiteSeerX.  
While such a large claim cannot be made by the BBC datasets, they have
only been around a few years and look promising for future collaboration.  While the two STEP
datasets cannot provide any external validity to our findings, they do add an additional
perspective due to their drastic differences in content.


\subsection{Considered Algorithms}
\label{s:algorithms}

Of the six different algorithms compared in this study, there are three 
dimensionality reduction methods and there are three clusterers.  Within each
category (reduction and clustering), we have one exhaustive method and two
heuristic methods.  The three reduction methods being studied are: PCA \cite{pearson1901} (exhaustive),
FastMap \cite{fastmap95} (heuristic), and TF*IDF Ranking (heuristic).  The three
clustering algorithms are: K-Means \cite{simpleKMeans00} (exhaustive), 
Canopy \cite{canopies00} (heuristic), and GenIc \cite{Gupta04} (heuristic).

The two exhaustive algorithms (PCA and K-Means) were chosen as they provide
a roughly generic representation of non-scalable clustering and dimension reduction.
The remaining four were either chosen because of a mix of their astounding run-time
advantages and non-existing prior comparisons in the literature.  

\begin{table}[!h]{\small
\begin{center}
\begin{tabular}{l|r|r}
{\bf Exhaustive/Heuristic }                & {\bf Clustering } & {\bf Dimensionality Reduction} \\\hline
Exhaustive     & K-Means & PCA \\\hline
Heuristic      & Canopy & FastMap\\
               & GenIc & TF*IDF Ranking \\
\end{tabular}
\end{center}}
\caption{Supervised datasets along with class values.}\label{tab:algsInStudy}
\end{table}


\subsection{Metrics (dependent variables)}
\label{s:metrics}

This section describes the metrics that are used to evaluate the algorithms listed above.
These values can also be considered the dependent variables of the experiments.
They were all chosen with the goal of providing a method of evaluation that is applicable
to both supervised and unsupervised datasets since the ultimate working environment 
of hamlet (section \ref{hamlet}) may be in either of these domains.  To eliminate bias from
running on different hardware, all values will be listed as ratios to the exhaustive methods.  
In addition to removing hardware bias, this will also focus on the relative values; these will
be of higher importance than the raw values since comparison between methods is what we
are most concerned with.





\subsubsection{Run-times}
For obvious reasons, run-time will be a primary metric for evaluating both the clustering and 
dimension reduction algorithms.  Run-times will be measured in seconds and then converted to
a ratio of the exhaustive methods.  

\subsubsection{Internal Similarity}
Internal similarity (equation \ref{eq:iSim}) will be used for measuring the validity of
both clustering and reduction.  A benefit of this measure is that it can be applied
to both unsupervised and supervised datasets since no information about the correct
classification is required.  This allows this measure to provide us with additional insight
into our generated datasets (see STEP datasets in section \ref{s:datasets}), allowing us
to see whether they are of any further value to the development of hamlet.  
Internal similarity is primarily used a means of assessing 
the results of a particular clustering.  We'll use it for reduction by looking at the validity
of the clusters generated using each of the reduction methods.  Essentially, internal similarity
is the measure of how similar items that belong to the same cluster are to each other.  Since
in a good clustering, we expect items in the same cluster to very similar to each other, a
good value for internal similarity is one that approaches that maximum value of 1.0.

\begin{figure}
\label{eq:iSim}
\begin{center}
\em{$iSim_i = \displaystyle\sum_{d \in C_i} \displaystyle\sum_{d'\in C_i} \frac{cos(d, d')}{n_i^2} $}
\em{$iSim = \displaystyle\sum_i \frac{n_i}{N} iSim_i $}
\end{center}
\caption{Equation for internal similarity}
\end{figure}



\subsubsection{External Similarity}
External similarity (equation \ref{eq:eSim}) will be used for measuring the validity of
both clustering and reduction.  A benefit of this measure is that it can be applied
to both unsupervised and supervised datasets since no information about the correct
classification is required.  This allows this measure to provide us with additional insight
into our generated datasets (see STEP datasets in section \ref{s:datasets}), allowing us
to see whether they are of any further value to the development of hamlet.  
External similarity is primarily used a means of assessing 
the results of a particular clustering.  We'll use it for reduction by looking at the validity
of the clusters generated using each of the reduction methods.  Essentially, external similarity
is the measure of how similar items that belong to different clusters are to each other.  Since
in a good clustering, we expect items in different clusters to not be very similar to each other, a
good value for external similarity is one that approaches that minimum value of 0.0.


\begin{figure}
\label{eq:eSim}
\begin{center}
\em{$eSim_{ij} =  \displaystyle\sum_{d \in C_i} \displaystyle\sum_{d' \in C_j} \frac{cos(d, d')}{n_i n_j}$}
\em{$eSim = \displaystyle\sum_i \frac{n_i}{N} eSim_{ij}$}
\caption{Equation for external similarity}
\end{center}
\end{figure}


\subsubsection{Similarity Loss}
$Similarity Loss$ is an original measure developed for the research.  It
is a way of combining the results of relative ratios of internal and external similarity 
for different algorithms and datasets.  After the computing the exact values of internal and external 
similarity for each of the algorithms, we express them each as a ratio of their value
to the value of most exhaustive algorithm.  The result is a value which indicates the relative
gain or loss of whatever measure the ratio is generated on.  When dealing with internal similarity, good
values are those that have relative values greater than one (meaning they out-preformed the exhaustive method).
With external similarity, a good value is one with a relative value less than one (also meaning a higher level
of performance compared to the exhaustive method).  Our studies have shown that often times a method will show
an improvement in one of the similarities with a dis-improvement in the other.  Similarity loss is a measure
of how much overall similarity (both internal and external) is lost or gained using a particular method.
It is defined below in equation \ref{eq:simLoss} as simply the difference between external similarity and
internal similarity.

\begin{figure}
\label{eq:simLoss}
\begin{center}
\em{{\bf Similarity Loss} = External Similarity - Internal Similarity}
\caption{Equation for similarity loss}
\end{center}
\end{figure}


\subsubsection{Cluster Purity}
\label{s:purity}

Cluster purity is a measure that can only be used on supervised datasets defined above in section \ref{b:purity}.
Intuitively, it is a measure of the homogeneity of class values within each cluster.  Since purity requires
an initial pairing of each item with a class label (meaning it is a supervised measure), it cannot be
used on our STEP datasets (section \ref{s:datasets}).  Using supervised datasets and not evaluating
the results using the added information of class labels would be overlooking an insightful component of
information.  Values for purity range from 0.0 - 1.0 with higher values telling of a $more pure$ 
clustering.  Like the other measures used in these experiments, purity for each dataset and 
algorithm will be scaled by the purity value of the most exhaustive method for that dataset. 

\subsection{Variables (independent variables)}

This sections describes the various variables that were either held constant, or varied with each 
creating a new treatment.  The table below (\ref{tab:variables}) lists each of these variables, their values, and rational
for the values that were chosen with the exclusion of datasets and algorithms (see sections \ref{s:datasets} and \ref{s:algorithms},
respectively, for information on these.)


\begin{center}
\begin{table}[!h]
\centering
{\scriptsize{
\begin{tabular}{|l||l|p{.15\linewidth}|c|p{.2\linewidth}|}\hline
{\bf Variable of } & {\bf Name } & {\bf Description} & {\bf Values} & {\bf Rational} \\\hline
{\bf General Reduction }  & $d$ & The number of dimensions being reduced to & 3, 15, 25, 50, 100, 200 & 
															  {\scriptsize{We reduce all the way down to 3 dimensions to examine
															 3-d visualizations of the different treatments.
															 values greater than this are used to test the run-time
															 growth of the treatments. }} \\\hline
 
{\bf General Clustering }  & $k$ & The number of clusters requested & 3, 5, 8, 15, 40, 75 &
															  {\scriptsize{The levels 3, 5, and 8 were chosen because each corresponds
 															 to the number of classes in the various supervised
															 datasets.  The others were chosen to fit our generated
															 datasets and to show run-time growth with larger $k$. }} \\\hline

{\bf KMeans Clustering}  & $max\_iterations$ &  The number of recursive step KMeans will take until
											   it accepts the current clustering & 500 & 
													{\scriptsize{ Set as recommended in the literature \cite{needRef} }} \\\hline

{\bf GenIc Clustering }  & $c$ & The number of centers or clusters & \{set to the same values of $k$ above\} &
															 {\scriptsize{ Used as a replacement for $k$ (listed above). }} \\\cline{2-5}
 & $m$ & The number of initial points & \{set to the same values of $k$ above\} & 
															{\scriptsize{ Set to the value of $c$.  To keep consistency
                                                             between all of the clusterers, this value was set to stay constant
															 with $c$ and $k$. }}   \\\cline{2-5}
 & $n$ &  The number of generations & {\small{$\frac{size(dataset)}{15}$}}  & {\scriptsize{ Set to change with whatever dataset is used.  This keeps the number
			   																 of passes constant among all treatments.  }} \\\hline 

{\bf Canopy Clustering } & $tight\_threshold$ & Using the cheap distance metric of count of similar terms.
												If two items are more similar than this
	  										    they must both be canopy centers. & 10 & {\scriptsize{ Using Early experimentation showed the number documents that have more
																						 than 10 similar terms occur infrequently enough to provide an efficient
																						 number of canopies. }} \\\cline{2-5}
 & $loose\_threshold$ & Using the cheap distance metric of count of similar terms.
						If an item is this similar or more to a canopy center,
					    it is assigned to that canopy. & 4 &  {\scriptsize{  Using Early experimentation showed the number documents that have
  															  4 or more similar terms occur at a frequency that provides an efficient
															  distribution of canopy sizes. }}\\\cline{2-5}

 & $max\_iterations$ & The number of recursive steps KMeans will take until it accepts the current clustering & 500 &
															{\scriptsize{  Set as recommended in the literature \cite{needRef} }} \\\hline
\end{tabular}
}}
\caption[Independent Variables]{Listing of independent variables and their values that were used in this study.}\label{tab:variables}
\end{table}
\end{center}



\section{Environment}
\label{s:environment}

This section describes the general experimental environment including the testing harness (hamlet) and overall experiment design.

\subsection{Textmine}

In an effort to provide a framework that better allows for full collaboration between researchers and repeatability of experiments, 
Ourmine \cite{ourmine09} was used to script the experiments.  Further information about Ourmine is available in section 
\ref{t:ourmine}.  To extend the capabilities of Ourmine into the domain of text mining, a modified version, Textmine, was created 
that adds methods for term reduction, document clustering, and evaluation of document clusters into Ourmine's toolset.  More 
specific information on Textmine and the development of the tools included with it can be found in section \ref{t:textmine}.

\subsection{Experimental Design}

This section gives a quick high-level look at the experimental design methodology used in evaluating 
our algorithms and datasets.  Strictly speaking, this experiment is of a factorial or fully-crossed design 
(a {\em 8x3x3x6x6 } factorial design).
The exact factors and their values are listed in table \ref{tab:factors}.  The product of the values 
in the last column is the total number of treatments (8x3x6x6 = 2,592).  To minimize artifacts from the random
nature of some of the algorithms, each treatment was repeated 10 times bringing the total number of passes to 
25,920 and creating a 10-fold-crossed, method of evaluation.

\begin{table}[!h]{\small
\begin{center}
\begin{tabular}{l|c|r}
{\bf Factor } & {\bf Levels } & {\bf Level count } \\\hline
dataset     & ap203, ap214, BBC, BBCSport, ngBias3, ngBias8, ngBal3, and ngBal8  & 8\\
clusterer     & KMeans, Canopy, and Genic & 3\\
reduction method             & PCA, FastMap, and TF*IDF Ranking & 3\\
$k$          & 3, 5, 8, 15, 40, and 75 & 6 \\
$d$			 & 3, 15, 25, 50, 100, 200 & 6 \\

\end{tabular}
\end{center}}
\caption[Experimental factors]{Experimental factors and their levels used for the experiment.  
A total of 2,592 (8x3x3x6x6) different treatments or combination
of factors exist in this design}\label{tab:factors}
\end{table}


\subsection{Workflow}

This section lists the steps taken in the processing and evaluating the datasets in a chronological order.

\be

\item {\bf Conversion to ARFF} \\
Convert the datasets into a congruent format.  The ARFF format described in 
section \ref{t:arff} was used for this.  The supervised datasets were converted from 
the matrix market format (MTX) \cite{mtx97} while the unsupervised, STEP datasets were
 converted from an internal XML representation used within Hamlet (section \ref{t:hamlet}).

\item {\bf Dimensionality Reduction} \\ 
At this point, each dataset was reduced 180 times (10 repeats times
3 reduction methods times 6 values for dimensionality).  These reduced datasets and a log
of the time taken to perform the reduction were archived to disk.

\item {\bf Clustering} \\
Now that the data has been reduced and run-times for the reduction have been logged,
clustering can take place.  In this step, for each dataset, one sample from each reduction treatment 
(or each combination of dimensionality and reduction method) is ran through
a clustering treatment (or each combination of number of clusters and  clustering method) and
repeated 10 times.  This gives a total of 3,240 samples for each dataset, 25,920 in all.  The resulting
clusterings and their run-times are then archived to disk for later use.

\item {\bf Analysis} \\
This step can be performed at any time after a clustering has been achieved.  This step includes
gathering evaluation statistics on each of the 25,920 samples generated in the previous step.  Here
is where the metrics described in section \ref{s:metrics} are collected.

\ee


\section{Reduction}
\label{s:reduction}

This sections discusses the effects of the choice of reduction method to
run-times and validity of generated clusters.  

\subsection{Run-times}

Unsurprisingly, run-times for dimensionality reduction were in line with each
algorithm's expectations.  Looking at the Mann-Whitney U tests in figure \ref{tab:reductionRtMWU}, 
you can see that reduction using TfIdf-Sort was by far the fastest as it wins in both comparisons.
FastMap comes in behind TfIdf-Sort while losing to it and beating PCA.  Lastly PCA brings up
the rear losing in all tests.  The MWU tests confirm that heuristic methods do have
better run-times than PCA, but at what magnitude? 
The results in figure \ref{tab:reductionRtRel}
show the run-times of each dimension reduction methods relative to
PCA.  These values were taken by summing the results from every trial
and then normalizing to a scale ranging from 0 to 100.  TfIdf-Sort shows
an amazing performance benefit over PCA with its trials taking less than
1\% of the time of PCA.  FastMap also shows substantial performance 
relative to PCA taking only 3\% of the time.  These results can also be noted
in figure \ref{fig:reductionRtAUC} where the run-times have been sorted and
plotted as a line.




\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Reduction Method & ties & wins & losses & wins-losses \\\hline
		   	TfIdf-Sort &    0 &   2 &    0 &        2 \\
		 	FastMap &    0 &   1 &    1 &        0 \\
			PCA &    0 &   0 &    2 &       -2 \\
		\end{tabular}
		\caption[Reduction MWU Results]{ Mann-Whitney U tests at 
			a 99\% confidence level.  As expected, the quick linear time method $TfIdf-Sort$ 
			performs better than both $PCA$ and $FastMap$ while $PCA$ performs the worst. }
		\label{tab:reductionRtMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Reduction Method & Run-time relative to PCA \\\hline
		 	TfIdf-Sort&  $<$1 \\
		 	FastMap&     3 \\
			PCA&     100 \\
		\end{tabular}
		\caption[Reduction run-times relative to PCA]{ The above table 
			illustrates the drastic computational requirements of 
			PCA compared to FastMap and TfIdf-Sort.  TfIdf-Sort runs in less than
			1\% of the time of PCA. }
		\label{tab:reductionRtRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/reducer_runtime_auc.pdf}
		\caption[AUC of Purity by Reduction Method]{Long Description}
		\label{fig:reductionRtAUC}
	\end{minipage}

\end{table}

\subsection{Validity}

As described in section \ref{s:metrics}, the three metrics being used to evaluate
the validity of the results are purity, internal similarity, and external
similarity.  This section will discuss each of the results of each of
these metrics.  Additionally, we'll be looking at plots of the data points
in three dimensions to get a graphical approximation of the types of
structures generated by each of the reduction methods.

\subsubsection{Reduction to three dimensions (a visualization)}

The plots in figure \ref{fig:reduction3dVis} show the visual representation
of dimensionality reduction down to three dimensions in the STEP datasets.  
One thing to remember here is the drastic change in dimensionality this represents.
The original dimensionality of these datasets can be as high as 15,000 (the
datasets shown in figure \ref{fig:reduction3dVis} have around 1,000 and 3,000),
so a drastic drop down to only 3 leaves plenty of room for data loss.  Despite this 
caveat, PCA still provides a noticeable amount of detail in its three dimensional
reduction compared to FastMap and TfIdf-Sort.  Notice the more random distribution
of points in PCA plots.  The FastMap points are limited to only
three lines within the reduced space, while nearly all of the TfIdf-Sort points
are located in the same exact point.  Realistically speaking, reduction to three
dimensions is not practical for most IR tasks in textual domains. This would 
only be possible in an extremely small dataset of trivial use.  This
explains the results of the TfIdf-Sort plots where the data is being reduced
to only three terms.  Any document that does not have those terms, will be placed
at the same point.  While this visualization does provide insight into the types
of geometric structures created by these algorithms, it is still merely a visualization.
Statistical tests are required before more concrete conclusions can be reached.



\begin{figure*}[!h]
\label{fig:reduction3dVis}
\begin{center}
\begin{tabular}{p{1in}|c|c}
PCA ($D*T^2$)& \includegraphics[width=2.2in]{figures/ap203_pca3.pdf} &
\includegraphics[width=2.2in]{figures/ap214_pca3.pdf}\\\hline
FASTMAP ($2N$) & \includegraphics[width=2.2in]{figures/ap203_fastmap3.pdf} &
\includegraphics[width=2.2in]{figures/ap214_fastmap3.pdf}\\\hline
Tf*IDF ($t*N$) & \includegraphics[width=2.5in]{figures/ap203_tfidf3.pdf} &
\includegraphics[width=2.2in]{figures/ap214_tfidf3.pdf}
\end{tabular}
\end{center}
\caption{What is lost by heuristic exploration.}
\end{figure*}


\subsubsection{Cluster Purity}

The choice of dimensionality reduction method seems to have a significant amount 
of impact on cluster purity when looking at the MWU tests \ref{tab:reductionPurityMWU}.  
Unsurprisingly, PCA, the slow but more accurate algorithm, wins over 
both FastMap and TfIdf-Sort and FastMap beats out TfIdf-Sort
which is again not a surprise.  What is a surprise is the relatively small 
amount that TfIdf-Sort and FastMap lose by.  Both of these algorithms 
tie at only 83\% of the purity of PCA, meaning that are relatively the 
same compared to PCA.  Given the run-time results 
list above, a loss of 17\% of accuracy 
is a small price to pay for a loss of 97\% of CPU cycles.  Furthermore, by 
looking the graph in \ref{fig:reductionPurityAUC}
you can see nearly identical results out of all three methods for a majority of the time.  With respect to
cluster purity, little is lost when using these less robust but much faster alternatives.


\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Reduction Method & ties & wins & losses & wins-losses \\\hline
			 PCA&    0&   2&    0&        2 \\
		 FastMap&    0&   1&    1&        0 \\
		   TfIdf-Sort&    0&   0&    2 & -2 \\
		\end{tabular}
		\caption[Reduction MWU Results for Purity]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:reductionPurityMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Reduction Method & Purity relative to PCA \\\hline
     pca& 100\\
 fastmap&  83\\
   tfidf-sort&  83\\
		\end{tabular}
		\caption[Reduction purities relative to PCA]{ }
		\label{tab:reductionPurityRel}
	\end{minipage}

	\begin{minipage}{0.4\linewidth}
		\center
		\includegraphics{figures/reducer_purity_auc.pdf}
		\caption[AUC of Purity by Reduction Method]{Long Description}
		\label{fig:reductionPurityAUC}
	\end{minipage}

\end{table}

\subsubsection{External Similarity}

The results for external similarity have an even more interesting
outcome.  We see the same pattern with the MWU results that we did with purity,
PCA winning against the tied FastMap and TfIdf-Sort.  What is interesting
about these results is the comparison to PCA.  PCA, as expected,
 performs approximately 30\% better than FastMap, however TfIdf-Sort does
even better by coming in at 6\% better than that.  This order of results 
fits somewhat in line with amount of homogeneity each algorithm introduces
into the new datasets.  With FastMap, resulting document vectors are generally very
similar, the same goes for PCA (at a lesser degree).  With TfIdf-Sort, we are actually
introducing more variance in the dataset by removing the most frequent co-occuring
terms.  



\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Reduction Method & ties & wins & losses & wins-losses \\\hline
     pca&    0&   2&    0&        2 \\
   tfidf-sort&    1&   0&    1&       -1 \\
 fastmap&    1&   0&    1&       -1 \\
		\end{tabular}
		\caption[Reduction MWU Results for external similarity]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:reductionESimMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Reduction Method & External similarity relative to PCA \\\hline
 fastmap& 148\\
     pca& 100\\
   tfidf-sort&  94\\
		\end{tabular}
		\caption[Reduction external similarity relative to PCA]{ }
		\label{tab:reductionESimRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/reducer_eSim_auc.pdf}
		\caption[AUC of External Similarity by Reduction Method]{Long Description}
		\label{fig:reductionESimAUC}
	\end{minipage}
\end{table}




\subsubsection{Internal Similarity}
isim
\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Reduction Method & ties & wins & losses & wins-losses \\\hline
			 pca&		0&	2&	0&	-2 \\
			 fastmap&	0&	1&	1&	 0 \\
			 tfidf-sort&		0&	0&	2&	 2 \\
		\end{tabular}
		\caption[Reduction MWU Results for Internal Similarity]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:reductionISimMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Reduction Method & Internal similarity relative to PCA \\\hline
			 fastmap& 118 \\
				 pca& 100 \\
			   tfidf-sort&  88 \\
		\end{tabular}
		\caption[Reduction internal similarities relative to PCA]{ }
		\label{tab:reductionISimRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/reducer_iSim_auc.pdf}
		\caption[AUC of internal similarity by Reduction Method]{Long Description}
		\label{fig:reductionISimAUC}
	\end{minipage}

\end{table}

\subsubsection{Similarity Loss}
loss


\subsection{Effect of Variables}
effects of vars

\subsubsection{Dataset Size vs. Run-time}

\subsubsection{Dataset Size vs. Validity}

\subsubsection{Number of Terms ($d$) vs. Run-time}

\subsubsection{Number of Terms ($d$) vs. Validity}

\subsubsection{Amount of Reduction ($d$) vs. Run-time}

\subsubsection{Amount of Reduction ($d$) vs. Validity}

\subsection{Trade-offs}
tradeoffs


\section{Clustering}
\label{s:clustering}
This sections discusses the effects of the choice of reduction method to
run-times and validity of generated clusters.  

\subsection{Run-times}
runtimes
\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Clustering Method & ties & wins & losses & wins-losses \\\hline
  genic&    0&   2&    0&        2\\
 kmeans&    1&   0&    1&       -1\\
 canopy&    1&   0&    1&       -1\\
		\end{tabular}
		\caption[Clustering MWU Results for Run-Time]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:clusteringRtMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Clustering Method & Run-Time Relative To KMeans\\\hline
 canopy&  52\\
  genic&   6\\
 kmeans& 100\\
		\end{tabular}
		\caption[Clustering Run-Time Relative to KMeans]{ }
		\label{tab:clusteringRtRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/clusterer_runtime_auc.pdf}
		\caption[AUC of Run-Time by Clustering Method]{Long Description}
		\label{tab:clusteringRtAUC}
	\end{minipage}

\end{table}

\subsection{Validity}
validity
\subsubsection{Cluster Purity}
purity
\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Clustering Method & ties & wins & losses & wins-losses \\\hline
 kmeans&    0&   2&    0&        2 \\
  genic&    0&   1&    1&        0 \\
 canopy&    0&   0&    2&        -2 \\
		\end{tabular}
		\caption[Clustering MWU Results for Cluster Purity]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:clusteringPurityMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Clustering Method & Cluster Purity Relative To KMeans\\\hline
 canopy&  72 \\
  genic&  64 \\
 kmeans& 100 \\
		\end{tabular}
		\caption[Clustering Purity Relative to KMeans]{ }
		\label{tab:clusteringPurityRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/clusterer_purity_auc.pdf}
		\caption[AUC of Cluster Purity by Clustering Method]{Long Description}
		\label{tab:clusteringPurityAUC}
	\end{minipage}

\end{table}


\subsubsection{External  Similarity}
esim
\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Clustering Method & ties & wins & losses & wins-losses \\\hline
  genic&    0&   2&    0&        2\\
 kmeans&    0&   1&    1&        0\\
 canopy&    0&   0&    2&       -2\\
		\end{tabular}
		\caption[Clustering MWU Results for External Similarity]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:clusteringESimMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Clustering Method & Cluster External Similarity Relative To KMeans\\\hline
 canopy&  91 \\
  genic& 113 \\
 kmeans& 100 \\
		\end{tabular}
		\caption[Clustering External Similarity Relative to KMeans]{ }
		\label{tab:clusteringESimRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/clusterer_eSim_auc.pdf}
		\caption[AUC of External Similarity by Clustering Method]{Long Description}
		\label{tab:clusteringESimAUC}
	\end{minipage}

\end{table}


\subsubsection{Internal  Similarity}
isim
\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Clustering Method & ties & wins & losses & wins-losses \\\hline
 kmeans&    0&   2&    0&        2 \\
  genic&    0&   1&    1&        0 \\
 canopy&    0&   0&    2&       -2 \\
		\end{tabular}
		\caption[Clustering MWU Results for Internal Similarity]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:clusteringISimMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Clustering Method & Cluster Internal Similarity Relative To KMeans\\\hline
 canopy&  83 \\
  genic&  91 \\
 kmeans& 100 \\
		\end{tabular}
		\caption[Clustering Internal Similarity Relative to KMeans]{ }
		\label{tab:clusteringISimRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/clusterer_iSim_auc.pdf}
		\caption[AUC of Internal Similarity by Clustering Method]{Long Description}
		\label{tab:clusteringISimAUC}
	\end{minipage}

\end{table}

\subsection{Effect of Variables}

\subsubsection{Dataset Size vs. Run-time}

\subsubsection{Dataset Size vs. Validity}

\subsubsection{Number of Terms ($d$) vs. Run-time}

\subsubsection{Number of Terms ($d$) vs. Validity}

\subsubsection{Number of Clusters ($k$) vs. Run-time}

\subsubsection{Number of Clusters ($k$) vs. Validity}

\input{tables/genicKret}

\subsection{Trade-offs}
tradeoffs




\section{Combining Methods}
\label{s:combinations}

\subsection{Run-times}

\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Clusterer-Reducer & ties & wins & losses & wins-losses \\\hline
   genic-tfidf-sort&    0&   8&    0&        8 \\
   kmeans-tfidf-sort&    0&   7&    1&        6 \\
  genic-fastmap&    0&   6&    2&        4 \\
 kmeans-fastmap&    0&   5&    3&        2 \\ 
   canopy-tfidf-sort&    0&   4&    4&        0 \\
 canopy-fastmap&    0&   3&    5&       -2 \\ 
      genic-pca&    0&   2&    6&       -4 \\
     canopy-pca&    0&   1&    7&       -6 \\
     kmeans-pca&    0&   0&    8&       -8 \\
		\end{tabular}
		\caption[Overall MWU Results for Run-time]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:reducClustRtMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Clusterer-Reducer & Run-time Relative To KMeans-PCA\\\hline
canopy-fastmap&   7 \\
     canopy-pca&  76 \\
   canopy-tfidf-sort&   5 \\
  genic-fastmap&   3 \\
      genic-pca&  71 \\
    genic-tfidf-sort&   1 \\
 kmeans-fastmap&  20 \\
     kmeans-pca& 100 \\
   kmeans-tfidf-sort&  12 \\
		\end{tabular}
		\caption[Reducer-Clusterer Run-time Relative to KMeans-PCA]{ }
		\label{tab:reducClustRtRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/clusterer_reducer_runtime_auc.pdf}
		\caption[Overall AUC of Run-time]{Long Description}
		\label{tab:reducClustRtAUC}
	\end{minipage}

\end{table}


\subsection{Validity}

\subsubsection{Cluster Purity}

\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Clusterer-Reducer & ties & wins & losses & wins-losses \\\hline
     kmeans-pca&    0&   8&    0&        8 \\
      genic-pca&    0&   7&    1&        6 \\
  genic-fastmap&    1&   5&    2&        3 \\
 canopy-fastmap&    1&   5&    2&        3 \\ 
   kmeans-tfidf-sort&    1&   3&    4&       -1 \\
 kmeans-fastmap&    1&   3&    4&       -1 \\
   canopy-tfidf-sort&    0&   2&    6&       -4 \\
    genic-tfidf-sort&    0&   1&    7&       -6 \\
     canopy-pca&    0&   0&    8&       -8 \\
		\end{tabular}
		\caption[Overall MWU Results for Purity]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:reducClustPurityMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Clusterer-Reducer & Purity Relative To KMeans-PCA\\\hline
 fastmap-canopy&  50 \\
  fastmap-genic&  68 \\
 fastmap-kmeans&  73 \\
     pca-canopy&  38 \\
      pca-genic&  95 \\
     pca-kmeans& 100 \\
   tfidf-canopy&  50 \\
    tfidf-genic&  67 \\
   tfidf-kmeans&  73 \\
		\end{tabular}
		\caption[Reducer-Clusterer Purity Relative to KMeans-PCA]{ }
		\label{tab:reducClustPurityRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/clusterer_reducer_purity_auc.pdf}
		\caption[Overall AUC of Purity]{Long Description}
		\label{tab:reducClustPurityAUC}
	\end{minipage}

\end{table}

\subsubsection{External Similarity}


\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Clusterer-Reducer & ties & wins & losses & wins-losses \\\hline
    genic-tfidf-sort&    1&   7&    0&        7 \\
     kmeans-pca&    0&   7&    1&        6 \\
  genic-fastmap&    1&   6&    1&        5 \\
      genic-pca&    0&   5&    3&        2 \\
     canopy-pca&    0&   4&    4&        0 \\
   canopy-tfidf-sort&    1&   2&    5&       -3 \\
 canopy-fastmap&    1&   2&    5&       -3 \\
   kmeans-tfidf-sort&    1&   0&    7&       -7 \\
 kmeans-fastmap&    1&   0&    7&       -7 \\
		\end{tabular}
		\caption[Overall MWU Results for External Similarity]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:reducClustESimMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Clusterer-Reducer & External Similarity Relative To KMeans-PCA\\\hline
fastmap-canopy& 134 \\
  fastmap-genic& 153 \\
 fastmap-kmeans& 149 \\
     pca-canopy&  80 \\ 
      pca-genic& 101 \\
     pca-kmeans& 100 \\
   tfidf-canopy&  83 \\
    tfidf-genic&  98 \\
   tfidf-kmeans&  85 \\
		\end{tabular}
		\caption[Reducer-Clusterer External Similarity Relative to KMeans-PCA]{ }
		\label{tab:reducClustESimRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/clusterer_reducer_eSim_auc.pdf}
		\caption[Overall AUC of External Similarity]{Long Description}
		\label{tab:reducClustESimAUC}
	\end{minipage}

\end{table}

\subsubsection{Internal Similarity}


\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|ccc|r}
			Clusterer-Reducer & ties & wins & losses & wins-losses \\\hline
     kmeans-pca&    0&   8&    0&        8 \\
      genic-pca&    0&   7&    1&        6 \\
  genic-fastmap&    1&   5&    2&        3 \\
 canopy-fastmap&    1&   5&    2&        3 \\
   kmeans-tfidf-sort&    1&   3&    4&       -1 \\
 kmeans-fastmap&    1&   3&    4&       -1 \\
   canopy-tfidf-sort&    0&   2&    6&       -4 \\
    genic-tfidf-sort&    0&   1&    7&       -6 \\
     canopy-pca&    0&   0&    8&       -8 \\
		\end{tabular}
		\caption[Overall MWU Results for Iternal Similarity]{ Mann-Whitney U tests at 
			a 95\% confidence level.  }
		\label{tab:reducClustISimMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.4\linewidth}
		\center
		\begin{tabular}{l|p{4.5cm}}
			Clusterer-Reducer & Internal Similarity Relative To KMeans-PCA\\\hline
 fastmap-canopy& 101 \\
  fastmap-genic& 102 \\
 fastmap-kmeans& 106 \\ 
     pca-canopy&  68 \\
      pca-genic&  88 \\
     pca-kmeans& 100 \\
   tfidf-canopy&  72 \\
    tfidf-genic&  73 \\
   tfidf-kmeans&  80 \\
		\end{tabular}
		\caption[Reducer-Clusterer Internal Similarity Relative to KMeans-PCA]{ }
		\label{tab:reducClustISimRel}
	\end{minipage}

	\begin{minipage}{\linewidth}
		\center
		\includegraphics{figures/clusterer_reducer_iSim_auc.pdf}
		\caption[Overall AUC of Internal Similarity]{Long Description}
		\label{tab:reducClustISimAUC}
	\end{minipage}

\end{table}


\subsection{Effect of Variables}

\subsection{Trade-offs}




\section{Summary of Findings}
\label{s:findings}

\subsection{Heuristics}

\subsection{Exhaustive}

\subsection{Optimal Combinations}


