\section{Specific Findings}

\label{s:findings}


\begin{table}[!h]
	\scriptsize
	\begin{minipage}[t]{0.5\linewidth}
		\center
		\begin{tabular}{|r|r|c||r|c||r|c|}
			\hline
			& \multicolumn{2}{c||}{\bf Reduction} & \multicolumn{2}{c||}{\bf Clustering} & \multicolumn{2}{c|}{\bf Combined} \\ \hline 
			& treatment & w-l &  treatment & w-l & treatment & w-l \\\hline
						 				 & 		 	& 	 	& 		 &  	& &  \\
			{\bf Purity} 				 & PCA 		& 2  	& kmeans & 2  	& pca-kmeans 	& 8 \\ 	
										 & tfidf 	& 0  	& genic  & 0  	& pca-genic 	& 6 \\
										 & fastmap 	& -2 	& canopy & -2 	& fastmap-genic	& 3 \\ 
										 & 		 	& 	 	& 		 &  	& fastmap-canopy& 3 \\ 
										 & 		 	& 	 	& 		 &  	& tfidf-kmeans	& -1 \\ 
										 & 		 	& 	 	& 		 &  	& fastmap-kmeans& -1 \\ 
										 & 		 	& 	 	& 		 &  	& tfidf-canopy	& -4 \\ 
										 & 		 	& 	 	& 		 &  	& tfdidf-genic	& -6 \\ 
										 & 		 	& 	 	& 		 &  	& pca-canopy	& -8 \\
										 & 		 	& 	 	& 		 &  	& &  \\ \hline
										 & 		 	& 	 	& 		 &  	& &  \\

			{\bf External Similarity}	 & PCA 		& 2		& genic  & 2 	& pca-kmeans 	& 8\\
										 & tfidf 	& -1  	& kmeans & 0 	& tfidf-genic 	& 6\\
										 & fastmap 	& -1 	& canopy & -2 	& pca-genic 	& 4\\ 
							 			 & 		 	& 	 	& 		 &  	& tfidf-kmeans 	& 1\\ 
							 			 & 		 	& 	 	& 		 &  	& pca-canopy 	& 0\\ 
							 			 & 		 	& 	 	& 		 &  	& tfidf-canopy 	& -1  \\ 
							 			 & 		 	& 	 	& 		 &  	& fastmap-genic & -4  \\ 
							 			 & 		 	& 	 	& 		 &  	& fastmap-kmeans& -6  \\ 
							 			 & 		 	& 	 	& 		 &  	& fastmap-canopy& -8  \\ 
										 & 		 	& 	 	& 		 &  	& &  \\ \hline 
										 & 		 	& 	 	& 		 &  	& &  \\

			{\bf Internal Similarity} 	 & PCA 	  	& 2  	& kmeans & 2 	& pca-kmeans 	& 8\\ 
						 				 & fastmap  & 0  	& genic  & 0 	& pca-genic 	& 6\\
										 & tfidf 	& -2 	& canopy & -2 	& fastmap-genic	& 3\\ 
										 & 		 	& 	 	& 		 &  	& fastmap-canopy& 3\\
										 & 		 	& 	 	& 		 &  	& tfidf-kmeans	& -1\\
										 & 		 	& 	 	& 		 &  	& fastmap-kmeans& -1 \\
										 & 		 	& 	 	& 		 &  	& tfidf-canopy	& -4 \\
										 & 		 	& 	 	& 		 &  	& tfidf-genic	& -6 \\
										 & 		 	& 	 	& 		 &  	& pca-canopy	& -8 \\
										 & 		 	& 	 	& 		 &  	& &  \\ \hline 
										 & 		 	& 	 	& 		 &  	& &  \\

			{\bf Run-time}			 	 & tfidf 	& 2  	& genic	 &  2 	& tfidf-genic 	& 8 \\ 
						 				 & fastmap 	& 0  	& kmeans & -1 	& tfidf-kmeans 	& 6\\
										 & PCA	 	& -2 	& canopy & -1 	& fastmap-genic	& 4\\ 
										 & 		 	& 	 	& 		 &  	& fastmap-kmeans& 2\\
										 & 		 	& 	 	& 		 &  	& tfidf-canopy	& 0\\
										 & 		 	& 	 	& 		 &  	& fastmap-canopy& -2 \\
										 & 		 	& 	 	& 		 &  	& pca-genic		& -4 \\
										 & 		 	& 	 	& 		 &  	& pca-canopy	& -6 \\
										 & 		 	& 	 	& 		 &  	& pca-kmeans	& -8 \\
										 & 		 	& 	 	& 		 &  	& &  \\\hline
		\end{tabular}
		\caption[All MWU Scores]{An aggregate look at all MWU results broken down by category}
		\label{tab:highLevelMWU}
	\end{minipage}\hfill
	\begin{minipage}[t]{0.3\linewidth}
		\center
		\begin{tabular}{|r|r||c|c|}
			\hline
			{\bf Reducer} & {\bf Clusterer} & {\bf Relative Run-time} \\ \hline
			tfidf 	& * 	& $<$1\% \\
			fastmap & * 	 	& 3\% \\
			PCA 	& * 	 	& 100\% \\\hline
			*		& genic	 	& 6\% \\
			*		& kmeans	& 52\% \\
			*		& canopy& 100\% \\ \hline
			tfidf	& genic	& 1\% \\
			tfidf	& kmeans& 12\% \\
			fastmap	& genic	& 3\% \\
			fastmap	& kmeans& 20\% \\
			tfidf	& canopy& 5\% \\
			fastmap	& canopy& 7\% \\
			pca		& genic & 71\% \\
			pca		& canopy& 76\% \\
			pca		& kmeans& 100\% \\\hline

		\end{tabular}
		\caption[All relative run-times]{An aggregate look at all AUC sums relative to PCA, Kmeans, or PCA-Kmeans}
		\label{tab:highLevelRuntime}
	\end{minipage}
\end{table}

\subsection{Dimension Reduction}

When looking the validity of the dimensionality reduction algorithms examined
in this study, its easily seen that our rigorous algorithm, PCA, wins in all metrics, hands down.  Not one of
the heuristic approaches beats the purity, external similarity, and internal
similarity of the PCA results.  However, this does not mean that they are far off
the from PCA results.  While Fastmap does perform worst in terms of the MWU of
the solo purity measure, it beats TfIdf in internal similarity and ties in external
similarity.  What is most important for Fastmap though, is its performance in the combined
results.  With the exception of external similarity, Fastmap outperforms TfIdf and comes close
to the baseline set by PCA.  Because of all this, in situations where external similarity is 
not as important as purity or internal similarity, that is, situations that require
items within the same clustering to be of higher similarity, Fastmap is our recommended approach.
This of course is assuming that the run-time of the given system is priority and 
the long run-times of PCA are not acceptable.  That being said, the TfIdf results were
quite impressive given its naivety and the fact that it was created in-house as a straw man
benchmark.  Owing to  naivety, TfIdf's run-times are nearly linear at $d*log(d)$ (with $d$ 
equal to the number of dimensions before reduction).  In addition to this, its validity
scores are not far off from Fastmap.  Even TfIdf may prove acceptable if the system
finds that the Fastmap run-times leave a little more to be desired.


\subsection{Clustering}

Our clustering conclusions are similar to our dimensionality reduction results in 
that the rigorous approach outperformed the alternatives in most measurements of
validity.  However, the clustering results differ from the dimensionality reduction results in
that there is a clear leader among the two heuristic approaches.  Genic beats Canopy in every 
validity measure and even outperforms {\em Kmeans} when it comes to external similarity.  This
says quite a lot for an algorithm that is not nearly as well known in the program comprehension
arena.  Canopy on the other hand, is at the very bottom of the spectrum.  
  This is likely one of the most surprising conclusions of the study
given the close relationship of Canopy and KMeans.  These results were verified by several
people on several occasions given that Canopy clustering is generally expected to perform close
to, or at the same level of KMeans in terms of the validity of its resulting clusters and that
these results clearly contradict that.  Because of all of the above factors, the conclusion of this study
with respect to clustering is that while Genic is not at the level of KMeans, it can be close enough
when the run-time of KMeans is too much to bear.


\subsection{Effective Combinations}

Drawing from the conclusions listed in the two sections above, we have found that
using Fastmap for dimensionality reduction combined with Genic for clustering
can produce effective results in a fraction of the time.  That being said, even more
potent clusters can be achieved by simply replacing only PCA.  The TfIdf and KMeans
combination shows astounding performance in validity at only 12\% of the base line
run-time.  The Fastmap and KMeans combination also shows solid performance at only
20\% of the PCA and KMeans run-time.  


\section{Summary}

To summarize the entirety of this work in one statement; heuristic methods 
are worth it.  That being said, there are a few caveats that exist and this
section aims to identify those.  One thing that was learned in this study
is that a complete replacement of a combined PCA and KMeans solution with
an entirely heuristic solution shows incredible benefits to performance.
However, using a solely heuristic approach may lead to sacrifices in validity.
Although these sacrifices are minimal compared to the increased performance,
they might not be acceptable in every application. 
In order to fully optimize the speed/accuracy ratio, 
you must consider your run-time constraints as well as how much inaccuracy 
your application can tolerate.  It is my opinion though that using the
right combinations or heuristic and rigorous clusterers and reducers can lead
to acceptable losses in validity in most situations.

\section{Future Work}


\begin{itemize}
\item Include more experiments that more closely mimic the in-use applications of program comprehension
\item Perform more in-depth analysis on the effect of the different parameters of each of the algorithms
\item Incorporate more current algorithms such as Latent Semantic Indexing to give the study more
breadth over what is happening in the industry
\item Explorations into domains where Genic could potentially provide run-times
not before seen of clustering algorithms.
\item A look into different approaches of determining the inherent dimensionality of 
datasets and how this can affect clustering performance
\end{itemize}

