%%\documentclass{article}
%%\usepackage{graphicx}
%
%%\newcommand{\be}{\begin{enumerate}}
%%\newcommand{\ee}{\end{enumerate}}
%%\newcommand{\bi}{\begin{itemize}}
%%\newcommand{\ei}{\end{itemize}}
%%\newcommand{\tion}[1]{\S\ref{sect:#1}}
%%\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
%%\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
%%
%
%%\bibliography{refs}
%
%%\begin{document}
%
%\section{Clustering Text Documents}
%
%\subsection{Motivation}
%
%The goal of HAMLET, as defined thus far, is to index large amounts of technical information spread
%across a variety of document types in a manner that allows us to ask the question,
% "What designs are their similar to this design?"
%In order be able to answer this question we must first find an appropriate way of 
%locating the "structure" in these collections; including (a) the
%structure that exists within each document as part of the collection, and (b) the comparative 
%structure of all the documents and how they relate to one other.
%Considering that each document type has a format that can vary from highly syntactic source code, 
%to badly formed HTML, to unstructured text, there is not much common ground between the various 
%document types.  One common theme in all of these documents is the exact thing you are 
%looking at right now, natural language.  By grouping all the natural language associated with
%a single design into one document we can solve some of the problems.  This answers (a), the question of how to define the structure 
%of each document as its own entity within the larger collection, but not (b) the question of how to
%define the comparative structure of the documents and how they relate to each other.  Enter document clustering.
%
%By clustering text documents we are able to find the inter-document structure in the collection.  This is done
%by locating groupings of documents, which can later be used to give us intelligent advice on what designs
%are similar.  In the previous report we illustrated a few common clustering methods and how they might proof useful
%in the context of HAMLET.  Two of the clusters discussed were GENIC and K-means.  In this section we describe
%empirical analysis into the trade-offs of GENIC and K-means which respect to clustering textual documents in HAMLET's domain.
%The datasets used in these trials are of specific interest to HAMLET as they are generated from collections of STEP/EXPRESS 
%source code.
%
%\subsection{Algorithms}
%
%\subsubsection{GENIC}
%
%GENIC is a generalized incremental clustering algorithm developed by Gupta and Grossman \cite{Gupta04} that 
%provides potentials for large improvements in scalability over K-Means. Since GENIC was designed with streaming 
%data in mind, it only has a single pass through the data to work with.  Because of this, it scales linearly, which 
%is a requirement when dealing with large corpora.  By using stochastic methods, GENIC can be given an initial k 
%equal to the number of items (each item is its own clusters) and prune away unlikely clusters with each generation,
%giving a realistically estimated value for k after the last generation.  Here is how GENIC works:
%
%\begin{enumerate}
%\item \textbf{Select parameters}
%\bi
%\item Fix the number of centers $k$.
%\item Fix the number of initial points $m$.
%\item Fix the size of a generation $n$.
%\ei
%
%\item \textbf{Initialize}
%\bi
%\item Select $m$ points, $c_1, ..., c_m$ to be the initial candidate centers.
%\item Assign a weight of $w_i$ = 1 to each of these candidate centers.
%\ei
%
%\item \textbf{Incremental Clustering} For each subsequent data point $p$ in the stream: do
%\bi
%\item $Count$ = $Count$ + 1
%\item Find the nearest candidate center $c_i$ to the point $p$
%\item Move the nearest candidate center using the formula \\
%\begin{equation}
%{c_i = \frac{(w_i * c_i + p}{w_i + 1} }
%\end{equation}
%\item Increment the corresponding weight \\
%\begin{equation}
%{w_i = w_i + 1}
%\end{equation}
%\item When $Count$ $mod$ $n$ = 0, goto Step 4
%\ei
%
%\item \textbf{Generational Update of Candidate Centers} \\
%When $Count$ equals $n, 2n, 3n$, ..., for every \\
%center $c_i$ in the list L of centers, do:
%\bi
%\item Calculate its probability of survival using the formula \\
%\begin{equation}
%{p_i = \frac{w_i}{\sum_{i=1}^n w_i}}
%\end{equation}
%\item Select a random number $\delta$ uniformly from [0,1]. If $p_i$ > $\delta$, retain the center $c_i$
%in the list L of centers and use it in the next generation to replace it as a center in the list L
%of centers.
%\item Set the weight $w_i$ = 1 back to one.  Although some of the points in the stream will be implicitly assigned
%to other centers now, we do not use this information to update any of the other existing weights.
%\item Goto step 3 and continue processing the input stream
%\ei
%
%\item \textbf{Calculate Final Clusters} The list L contains the $m$ centers. These $m$ centers
%can be grouped into the final $k$ centers based on their Euclidean distances.
%
%\end{enumerate}
%
%GENIC is of specific interest to HAMLET for two primary reasons, low expected run-times on large corpora and a
%potential ability at estimating the number of natural clusters in the collection.
%\bi
%\item
%Scalability:
% Since 
%GENIC was designed with streaming data in mind, it only has a single pass through the data to work with.  Because of this,
%it scales linearly, which is a requirement if HAMLET is to
%scale to large corpora.
%\item
%An likely estimate for $k$:
% Because of GENIC's stochastic based method of removing unwanted or non-useful clusters, it has potential for use in correctly
%estimating a good value for $k$.  By eliminating "bad stuff", GENIC can ideally identify the correct number of types of "good stuff".
%\ei
%
%\subsubsection{K-means}
%K-Means is a clustering algorithm that, when given a dataset of unidentified objects, it will 
%group those items into $k$ groups based on some given similarity measure. 
%The algorithm is described in \fig{kmeans}. For an example
%of the algorithm in operation, see \fig{keg}.
%
%
%\begin{figure}[!h]
%\begin{tabular}{|p{\linewidth}|}\hline
%\bi
%\item
%i=0
%\item
%Partitioning the input points into k initial sets, either at random or using some heuristic data.
%\item Repeat
%unitl ($i \le maxIterations$ or no point changes set membership)
%\bi
%\item
%\item  Calculates the mean point, or centroid, of each set or cluster.
%\item  Constructs a new partition, by associating each point with the closest centroid.
%\item  Recalculate the centroids for the newly partitioned cluster
%\item  i = i + 1
%\ei
%\ei\\
%\hline
%\end{tabular}
%\caption{K-Means algorithm. See \fig{keg} for an example of this algorithm running in
%practice.}\label{fig:kmeans}
%\end{figure}
%
%\begin{figure}\small
%Step1:
%Here, we show some initial data points and the centroids generated based on random assignment
%\begin{center}
%\includegraphics{120px-K_Means_Example_Step_1.png}
%\end{center}
%
%Step2: Points are associated with the nearest centroid:
%\begin{center}
%\includegraphics{120px-K_Means_Example_Step_2.png}
%\end{center}
%
%Step3: Next, we
%recompute centroid using new associations and update the stored centroid:
%\begin{center}
%\includegraphics{120px-K_Means_Example_Step_3.png}
%\end{center}
%
%Steps 2 \& 3 are repeated until one of the two convergences criteria are reached.
%\begin{center}
%\includegraphics{120px-K_Means_Example_Step_4.png}
%\end{center}
%\caption{Example of K-means}\label{fig:keg}
%\end{figure}
%
%While k-means may be sufficiently accurate, there are significant drawbacks.  Most notably is the speed (or lack thereof).  
%Due to the k-means algorithm having to compute distances from every item to every cluster.  In situations where the cosine 
%similarity distance measure is used, computing the distance between points can be an expensive operation (this is another place dimensionality reduction helps out).
%In recent tests comparing clustering algorithm run-times, k-means was found to be up to 500 times slower than another algorithm, 
%GENIC, which we discuss further down.
%
%Another problem with k-means is determining what value of 
%$k$ should be used.  Note the usability issues
%with requiring a user to pre-specify $k$:
%isn't this the kind of tedious detail
%that  the computer should be telling us?  
%
%There are many techniques for automatically discovering
%an approximate value of $k$,
%all of which include several rounds of initial guesses, trying
%various values around the guess, then returning the $k$ value
%that yields the best classification results.
%The problem with 
%these techniques is that K-Means is a slow
%algorithm- requiring it to run many times is impractical for
%large corpora.
%
%
\section{Clustering Experiments}\label{sec:cexpments}

In this section we describe
empirical analysis into the trade-offs of GENIC and K-means which respect to clustering textual documents in HAMLET's domain.
The datasets used in these trials are of specific interest to HAMLET as they are generated from collections of STEP/EXPRESS 
source code.  This experiment evaluates the value of the GENIC (\tion{genic}) and  K-means (\tion{kmeans})
for clustering archival data. K-means is a standard clsutering algorithm and GENIC is a novel stochastic method
that showed much promise.

After the experiments described below, we now recommend against GENIC
for the following reason. Some trade-offs are acceptable.
In some cases, we would accept that trade-off (e.g. a 10\% reduction in clustering quality in exchange for the ability to examine data sets 10 times as big). However, as reported below, the
trade-off between GENIC and K-means is unacceptable.

\subsection{Experimental Design}

In order to successfully measure the merits of GENIC and K-means, an evaluation criteria must first be defined.  
The two criteria we care most about are, "how good is the clustering result?" and "How long did it take us to come up
with?"  The second question can be answered by simply measuring the run-times of the algorithms for the same problem.
The first question however needs slightly more effort in order to come up with a good comparison mechanism.  

For analyzing clustering accuracy or validity, evaluation metrics can be grouped into two categories, external and internal \cite{Steinbach00}.
External quality is based upon how the clusters output match up with some initial correct labeling, while internal quality 
is based entirely on the clusters output with no correct results to judge against.  For the purposes of this experiment, 
we can only focus on internal cluster quality since the information needed for external quality does not exist for the 
text collections being used in this study.  To evaluate cluster accuracy,  we are using two measures of internal cluster 
validity, intra-cluster similarity and inter-cluster similarity \cite{Conrad2005}.

The intra-cluster similarity is effectively the pairwise similarity between all elements within a cluster 
If  $n_j$ is the number of elements in cluster $j$, and $N$ is the total number of elements in the corpus then
intra-cluster similarity is defined as follows:
\begin{equation}\label{eq:intraSim1}
{ISim_j = \frac{1}{n_j^2} \sum_{{d{\in}C_j}{d'{\in}C_j}} cos(d, d') }
\end{equation}
\begin{equation}\label{eq:intraSim2}
{Intra\; cluster\;  similarity = \sum_j \frac{n_j}{N} ISim_j }
\end{equation}
Using the same notation, 
the inter-cluster similarity is defined as follows:
\begin{equation}\label{eq:interSim1}
{ESim_ij =  \frac{1}{n_i n_j} \sum_{a in C_i, b in C_j} cos(a, b) }
\end{equation}
\begin{equation}\label{eq:interSim2}
{Inter\;cluster\; similarity = \sum_j \frac{n_j}{N} ISim_j }
\end{equation}

The different treatments involved in the experiment will be all pairs of levels the two independent 
factors, clusterers {GENIC, K-means} and a collection of values for 
$k \in {1, 4, 16, 32, 64, 128, 256, 512, 1024}$.  
Because both K-means and GENIC depend on stochastic methods, we have repeated the experiment 20 times for each
treatment to minimize possible glitches caused by randomness.  Furthermore, the random seed was 
based on time to ensure new random numbers were being generated for eah repeat to void seeing results that
can be attributed to the effects of a non-randomized process.

The datasets being used for the experiment are two text datasets generated from collections of STEP/EXPRESS documents.
The STEP/EXPRESS files were separated based on which AP they conform to/describe, resulting in two datasets; one from 
AP203 and the other AP214.  Further details are described in \fig{datasets}

\begin{figure}[!h]
\begin{center}
\begin{tabular}{|c|r|r|}\cline{2-3}
\multicolumn{1}{c|}{}&AP203 & AP214 \\\hline
Total Documents&484 		&1373\\
Total Terms&1103 		&3050	\\
Mean Document Length&143 		&164	\\
StdDev of Document Length&8750 &2313 \\\hline
\end{tabular}
\end{center}
\caption{Statistics on STEP/EXPRESS datasets.}\label{fig:datasets}
\end{figure}

\subsection{Previous Works}

Gupta \& Grossman compare GENIC vs. windowed K-Means in \cite{Gupta04} on metrics regarding run-time 
and cluster quality using Sum of Squares of Errors or Inter-cluster similarity as their choice for the
 quality feature.  Their results show GENIC and K-Means very close for all cases except when GENIC was given
 a very large number of centers to start with.  However, all that was given in their were a few graphs and 
subtle commentary.  No statistical analysis was done on their results of either run-time or cluster quality 
leaving room for more work to be done in this area.  Additionally, the datasets used by Gupta \& Grossman in 
this paper were all artificially created, which may raise questions about the external validity of their findings. 
 With respect to the run-time results of this study, they found GENIC running a maximum of 40 times faster than 
K-Means, however this was only a maximum value that was given with no further statistical results.  


\newpage
\subsection{Discussion of Results}

\subsubsection{Run-time}


Which respect to run-times, the results were largely as expected.  K-Means is not designed for high speed
scenarios like GENIC is, and the results show this.  What is surprising however, is that the low magnitude of
victory (see K-Means/GENIC in \fig{time_graph}).  Contrary to evidence presented by Gupta in 2004, on average GENIC's run-time 
was only 10.4 times slower than K-Means (compared to 40 times faster as presented by Gupta).  This is even
more surprising given the previous comparison was against a version of K-means which was optimized for speed.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=5in]{total_runTime.png}
\caption[Average run-times, GENIC and K-Means]{Average run-time graph of GENIC, K-Means, K-Means - GENIC, and K-Means/GENIC}
\label{fig:time_graph}
\end{center}
\end{figure}


For the analysis of run-times, Mann-Whitney U tests were used because of their 
non-parametric nature (run-times may not necessarily conform to a Gaussian distribution). 
By looking at the results from the MWU tests in \fig{time_mwu} below, you will see that GENIC 
consistently out performs K-Means with respect to run-times, 
at the 95\% confidence interval. Given the linear approach of GENIC, this is as expected.
%However, there is an interesting anomaly with K-Means at k=1.  This treatment ranks higher than
%all others with 0 losses.  This is because the K-Means algorithm is based on iteratively re-estimating
%its clusters until an optimal solution is reached, and with K=1, there isn't much room (or time) to optimize.


\begin{figure}[!h]
\noindent
{\scriptsize\begin{center}
\begin{tabular}{|r|c|c|c|c|}
    \hline
    \textbf{treatment} & \textbf{ties} & \textbf{win} & \textbf{loss} & \textbf{win-loss-at-95\%} \\ \hline \hline
%  kmeans \& k=1	&    0	&  17	&    0	&       17 \\ \hline
     genic \& k=4	&    1	&  15	&    1	&       14 \\ \hline
     genic \& k=1	&    1	&  15	&    1	&       14 \\ \hline
    genic \& k=16	&    0	&  14	&    3	&       11 \\ \hline
    genic \& k=32	&    0	&  13	&    4	&        9 \\ \hline
    genic \& k=64	&    0	&  12	&    5	&        7 \\ \hline
    kmeans \& k=4	&    1	&  10	&    6	&        4 \\ \hline
   genic \& k=128	&    1	&  10	&    6	&        4 \\ \hline
   kmeans \& k=16	&    1	&   8	&    8	&        0 \\ \hline
   genic \& k=256	&    1	&   8	&    8	&        0 \\ \hline
   kmeans \& k=32	&    1	&   6	&   10	&       -4 \\ \hline
   kmeans \& k=64	&    2	&   4	&   11	&       -7 \\ \hline
   genic \& k=512	&    4	&   3	&   10	&       -7 \\ \hline
  kmeans \& k=128	&    3	&   3	&   11	&       -8 \\ \hline
  kmeans \& k=256	&    2	&   2	&   13	&      -11 \\ \hline
  genic \& k=1024	&    2	&   2	&   13	&      -11 \\ \hline
  kmeans \& k=512	&    0	&   1	&   16	&      -15 \\ \hline
 kmeans \& k=1024	&    0	&   0	&   17	&      -17 \\ \hline
\end{tabular}
\end{center}}
\caption[Mann-Whitney U tests]{
Mann-Whitney U tests for run-time of GENIC and K-Means.  As expected, 
GENIC wins over all K-means treatments within a few steps of {\em k}.
}\label{fig:time_mwu}
\end{figure}

\begin{figure}[!h]
\noindent
{\scriptsize\begin{center}
\begin{tabular}{ rc @{} c @{} c @{}}
                             & & Run-time \\
   Treatment   & & (normalized 0..100, min..max)\\
\hline
      genic, k =   256&  & \boxplot{   0.5}{0.7}{   1.2}{97.4}{  98.6} &  \\
      genic, k =   128&  & \boxplot{   0.3}{1.3}{   1.6}{96.6}{  98.2} &  \\
      genic, k =    64&  & \boxplot{   0.8}{2.4}{   3.2}{93.8}{  97.0} &  \\
      genic, k =    32&  & \boxplot{   0.9}{5.3}{   6.2}{66.9}{  73.1} &  \\
      genic, k =     1&  & \boxplot{   0.8}{5.5}{   6.3}{70.9}{  77.2} &  \\
      genic, k =    16&  & \boxplot{   1.2}{5.5}{   6.7}{56.2}{  62.9} &  \\
     kmeans, k =   256&  & \boxplot{   1.8}{5.3}{   7.1}{49.7}{  56.8} &  \\
     kmeans, k =    16&  & \boxplot{   2.9}{4.4}{   7.3}{20.4}{  27.7} &  \\
      genic, k =     4&  & \boxplot{   2.6}{6.8}{   9.4}{47.3}{  56.7} &  \\
     kmeans, k =    64&  & \boxplot{   3.7}{8.4}{  12.1}{35.8}{  47.9} &  \\
      genic, k =   512&  & \boxplot{   4.2}{8.9}{  13.1}{9.3}{  22.4} &  \\
     kmeans, k =   128&  & \boxplot{   3.8}{9.4}{  13.2}{39.6}{  52.8} &  \\
     kmeans, k =    32&  & \boxplot{   3.6}{11.3}{  14.9}{27.7}{  42.6} &  \\
     kmeans, k =     4&  & \boxplot{   5.8}{11.6}{  17.4}{17.5}{  34.9} &  \\
     kmeans, k =     1&  & \boxplot{   0.4}{27.1}{  27.5}{48.6}{  76.1} &  \\
      genic, k =  1024&  & \boxplot{   5.3}{31.4}{  36.7}{20.6}{  57.3} &  \\
     kmeans, k =   512&  & \boxplot{  10.5}{30.3}{  40.8}{20.6}{  61.4} &  \\
     kmeans, k =  1024&  & \boxplot{  37.9}{21.5}{  59.4}{21}{  80.4} &  \\
\hline
 &  & 50\% & 
\end{tabular}
\end{center}}
\caption[Run-times for GENIC and K-Means]{
Run-times for GENIC and K-Means with different values for {\em k}
(25 to 75\% percentile range from 40 simulations;  median values shown as a dot).
As expected, GENIC outperforms K-Means in nearly all treatments.
}\label{fig:time_quarts}
\end{figure}

\newpage
\subsubsection{Cluster Validity}

When it comes to the validity of the clusters generated by GENIC and K-Means, 
the results are completely opposite from the run-time results. 
\fig{sim_mwu} shows the Mann-Whitney results for intra-cluster similarity.
 In the 
MWU tests shown in \fig{sim_mwu} GENIC does not have a single treatment
that scores more wins than losses at the 95\% significant level.  
\begin{figure}
\noindent
{\scriptsize\begin{center}
\begin{tabular}{ rc @{} c @{} c @{}}
                             & & Similarity \\
   Treatment   & & (normalized 0..100, min..max)\\
\hline
      genic, k =      4&  & \boxplot{  14.7}{1.6}{  16.3}{1.6}{  17.9} &  \\
      genic, k =    512&  & \boxplot{  17.6}{4.3}{  21.9}{4.2}{  26.1} &  \\
      genic, k =      1&  & \boxplot{   9.2}{12.9}{  22.1}{3.7}{  25.8} &  \\
      genic, k =    256&  & \boxplot{  21.2}{1.8}{  23.0}{2.1}{  25.1} &  \\
      genic, k =     16&  & \boxplot{  20.8}{2.4}{  23.2}{2.9}{  26.1} &  \\
      genic, k =    128&  & \boxplot{  21.5}{2.5}{  24.0}{2.5}{  26.5} &  \\
     kmeans, k =      4&  & \boxplot{  22.8}{1.4}{  24.2}{3}{  27.2} &  \\
      genic, k =   1024&  & \boxplot{  22.4}{2.2}{  24.6}{3.8}{  28.4} &  \\
      genic, k =     64&  & \boxplot{  21.9}{2.8}{  24.7}{1.8}{  26.5} &  \\
      genic, k =     32&  & \boxplot{  23.5}{2.3}{  25.8}{1.7}{  27.5} &  \\
     kmeans, k =     16&  & \boxplot{  44.6}{1.6}{  46.2}{1.1}{  47.3} &  \\
     kmeans, k =      1&  & \boxplot{   9.2}{38.1}{  47.3}{37}{  84.3} &  \\
     kmeans, k =     32&  & \boxplot{  58.7}{0.9}{  59.6}{1.4}{  61.0} &  \\
     kmeans, k =     64&  & \boxplot{  72.1}{1.4}{  73.5}{0.9}{  74.4} &  \\
     kmeans, k =    128&  & \boxplot{  83.3}{0.6}{  83.9}{0.5}{  84.4} &  \\
     kmeans, k =    256&  & \boxplot{  89.8}{0.7}{  90.5}{2.8}{  93.3} &  \\
     kmeans, k =    512&  & \boxplot{  94.5}{0.1}{  94.6}{0.2}{  94.8} &  \\
     kmeans, k =   1024&  & \boxplot{  98.7}{0.1}{  98.8}{0}{  98.8} &  \\
\hline
 &  & 50\% & 
\end{tabular}
\end{center}}
\caption[Cluster similarity, GENIC vs K-Means]{
Cluster similarity measures using GENIC and K-Means with different values for {\em k}
(25 to 75\% percentile range from 40 simulations;  median values shown as a dot).
Surprisingly, GENIC does not perform well at all with respect to cluster similarity.
}\label{fig:sim_quarts}
\end{figure}


This could be 
attributed to the stochastic removal of clusters done by GENIC.  However, K-Means also
uses randomness when computing its initial clusters.  One may also consider
the fact that GENIC does not retain the full number of clusters asked for a reason
for the poor performance.  \fig{kRet} lists
the actual number of clusters returned by GENIC on average.
So in all actuality, when comparing GENIC with k=1024 we shouldn't compare it against
K-Means with k=1024, but rather a K-Means treatment closer the value actually
returned by GENIC, which is approximately 316.  Though, despite this caveat GENIC still fails
to beat any K-Means treatment except when k=1.

\begin{figure}[!h]
\noindent
{\scriptsize\begin{center}
\begin{tabular}{|r|c|}
    \hline
    \textbf{Size} & \textbf{Average k actually returned} \\ \hline \hline
1	& 1 \\ \hline
4	& 3.9375 \\ \hline
16	& 11.7875 \\ \hline
32	& 20.275 \\ \hline
64	& 35.5375 \\ \hline
128	& 64.4375 \\ \hline
256	& 114.013 \\ \hline
512	& 189.15 \\ \hline
1024	& 316.775 \\ \hline
\end{tabular}
\end{center}}
\caption{Average number of clusters returned by GENIC for each K}
\label{fig:kRet}
\end{figure}

Looking at \fig{sim_graph} further
illustrates the vast differences in similarity between K-Means and GENIC.  Notice the
K-means asymptotic approach to perfect similarity while GENIC stays approximately the same
regardless of the number of clusters without ever raising over 0.5.
\fig{sim_graph} also suggests that there is a useful maximum number of clusters in this domain:
no improvement is apparent over (around) 300 clusters for either of our methods.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=4.5in]{total_sim.png}
\caption{Intra-cluster similarity graph of GENIC and K-Means on average}
\label{fig:sim_graph}
\end{center}
\end{figure}

It would not be as significant if only the average similarity of GENIC was so low.
Given the randomness of the algorithm, its reasonable to believe that a good deal
of variance could be introduced.  However, looking at the quartile charts in \fig{sim_quarts},
you can see the small variance in GENIC performance.  While it may be
a good thing that the scores are consistent despite randomness, its most certainly a bad thing that
they are so low.  Further, these results directly contradict that of the previous work on GENIC and K-Means which
states that the GENIC and K-Means similarity (sum of squared errors in their case) are comparable, granted
there was no statistical testing done to say one way over the other.

\begin{figure}[!h]
\noindent
{\scriptsize\begin{center}
\begin{tabular}{|r|c|c|c|c|}
    \hline
    \textbf{treatment} & \textbf{ties} & \textbf{win} & \textbf{loss} & \textbf{win-loss-at-95\%} \\ \hline \hline
 kmeans \& k=1024	&    0	&  17	&    0	&       17 \\ \hline
  kmeans \& k=512	&    0	&  16	&    1	&       15 \\ \hline
  kmeans \& k=256	&    0	&  15	&    2	&       13 \\ \hline
  kmeans \& k=128	&    0	&  14	&    3	&       11 \\ \hline
   kmeans \& k=64	&    0	&  13	&    4	&        9 \\ \hline
   kmeans \& k=32	&    0	&  12	&    5	&        7 \\ \hline
   kmeans \& k=16	&    0	&  11	&    6	&        5 \\ \hline
    genic \& k=32	&    4	&   6	&    7	&       -1 \\ \hline
    kmeans \& k=4	&    6	&   4	&    7	&       -3 \\ \hline
  genic \& k=1024	&    6	&   4	&    7	&       -3 \\ \hline
    genic \& k=64	&    7	&   3	&    7	&       -4 \\ \hline
   genic \& k=128	&    7	&   3	&    7	&       -4 \\ \hline
   genic \& k=256	&    6	&   3	&    8	&       -5 \\ \hline
    genic \& k=16	&    6	&   3	&    8	&       -5 \\ \hline
   genic \& k=512	&    4	&   3	&   10	&       -7 \\ \hline
     genic \& k=4	&    0	&   2	&   15	&      -13 \\ \hline
    kmeans \& k=1	&    1	&   0	&   16	&      -16 \\ \hline
     genic \& k=1	&    1	&   0	&   16	&      -16 \\ \hline

\end{tabular}
\end{center}}
\caption[Mann-Whitney U tests for intra-cluster similarity]{
Mann-Whitney U tests for intra-cluster similarity of GENIC and K-Means.
GENIC does overwhelmingly bad on on all accounts with none of its
treatments having a positive record.
}\label{fig:sim_mwu}
\end{figure}

\newpage

\subsection{Implications of Results}

Looking at the performance of K-Means as k in increased shows a direct correlation between 
the number of clusters generated and intra-cluster similarity.  While this could mean that we
should focus our efforts on generating cluster-sets with many clusters, there is also
the trade-off with respect to time.  GENIC was an attempt at leveraging the trade-offs with
no avail.  Given the similarity performance of GENIC, it has been shown to be not acceptable
for our tasks at hand.

More importantly however, when asking what a good value for {\em k} is, is what the data tells us.
How many clusters inherently exist in the data?
The basic mathematics behind similarity will usually yield sets with many clusters a higher similarity
score than those with less.  Imagine if you were to measure the differences between every person in the
US as lumped into one massive group, you would not find much similarity (the case when k = 1).  Now if
you were to continually arbitrarily split that group into sub-groups, you would eventually have a small enough population
that similarities could begin to rise.  Setting a static value for {\em k} for all datasets 
is not the answer.  Each dataset is unique.  They each have different sizes, number of variables, variable types, noise, etc.;
Given this, what is important is to determine an appropriate value for {\em k} for your
dataset.  While it may be more time efficient to produce fewer clusters and more accurate to
produce more, the best bet is to find the closest approximation to the inherent rank (number of clusters)
of the dataset, and work from there.

\subsection{Future Work}

This experiment has shown us that GENIC cannot suit our needs, and that while K-Means may do a good job, it 
will take a long time to get there, which leads us to look for other alternatives.
In our last report we mentioned an optimization step for K-Means called canopy clustering, future work
will further explore evaluate this method in the same manner that GENIC was evaluated.  

Other areas
for improvement are the data collections we have to work with.  We have in our possession, 2-3 additional
text mining dataset that we have yet to fully evaluate due to their size and the computing time needed
to run the numerous trials.  The additional benefit of these new datasets is that they are, unlike the
STEP/EXPRESS datasets, supervised, meaning each document has been pre-classified with a label that can
later be used to assess clusters using external validity measures.  Adding more, non-similarity based
measurement criteria for clustering and classification as well is another direction we are headed towards.
While cluster similarity is a useful insight into the clusters, a more practical measurement would
better suit our needs.  Currently in the works is a method for evaluating how well our algorithms
perform within HAMLET, as used by a user.

%\end{document}
