\begin{kasten}
    \section*{  \hspace{0.1cm} {\color{red} 
				 \underline{SOME CLUSTERING METHODS}}}

(Ranked top to bottom, 
slowest to fastest,
most-thorough to simplest:)
~\\

{\bf K-MEANS:} This classical IR clusterer. It picks $K$ centroids at random then
partitions the input points into $k$ initial sets, each set holding
the data nearest a centroid.  The algorithm 
adjusts the centroids to the mean
position of each cluster.  Repeat partitioning and adjustment till
the centroids stop moving by a significant amount.

\begin{shortlist}
\item[] K-MEANS picks $K$ centroids at random then...
\begin{shortenum}
\item
Partitions date points into $k$ initial sets, each set holding
the data nearest a centroid;
\item  
Adjusts the centroid to the mean
position of each cluster;  
\item
Repeats partitioning and adjustment till
the centroids stop moving by a significant amount.  
\end{shortenum}
\end{shortlist}
A naive
implementation of K-MEANS needs to compute the distance between all
pairs of points and takes time $O(N^2)$.  Smarter implementation
using hierarchical partitioning methods (ball trees, KD-trees, cover
trees) to reduce that cost. Even so, the run-time costs of K-MEANS
are so prohibitively high that researchers have explored numerous alternatives.
~\\

{\bf CANOPY:} The CANOPY algorithm, developed by GOOGLE,
runs over the data in two-passes. 
In  pass one, a cheap distance measure 
is used to determine ``canopies''; i.e.
groups of approximately close items. This measure is used
to define ``inner'' points (near the canopy centroid)
and the remaining ``outer'' points. In 
pass two,  a more expensive distance measure is used, but only
for items in the same canopy. In the case of HAMLET,
pass one uses an inverted index of what terms appear in what
documents: the distance between items is number of documents
they share. 
%\begin{center}
%\begin{minipage}{2in}
%For example, here is some data sorted
%into canopies.
%The darker circle represents all points in a 
%given canopy, points in the 
%smaller circles cannot be used as a new canopy center.
%\end{minipage}
%\begin{minipage}{3in}
%~~~~~~~~\includegraphics[width=3in]{canopies.eps}
%\end{minipage}
%\end{center}
~\\

{\bf GENIC:} 
Single-pass, stochastic, stream-oriented clustering.
Initially, pick $k$ centroids at random from the instances.
At the start of each ``generation'', set the centroid weight to one.
As new datum arrive, push the nearest
centroid to that datum and increment the score for that centroid
(as scores increase, centroids become ``heavier'' and move less
and less towards new data). When the generation ends, 
replace the centroids with less
than X\% of the max weight with $N$ more random centroids. 
Repeat for several generations. Return the
centroids with highest score.
\end{kasten}


\begin{kasten}
    \section*{ \hspace{0.1cm} {\color{red} 
			    \underline{TRADE-OFFS}}}
\begin{minipage}{2.2in}
\begin{tabular}{l}
PCA ($D*T^2$)\\
\includegraphics[width=2.2in]{ap203_pca3.eps} 
\\

FASTMAP ($2N$) \\
\includegraphics[width=2.2in]{ap203_fastmap3.eps} 
\\

Tf*IDF ($t*N$) \\
\includegraphics[width=2.2in]{ap203_tfidf3.eps}
\end{tabular}
\end{minipage}
\begin{minipage}{2.75in}
Our engineering challenge 
is to  find the right combination of reduction and clustering methods.\\
%~\\

As shown at left, as methods get faster (top to bottom), they find less and less
structure in the data.\\
%~\\

On the other hand, the slower more thorough methods are much, much slower. The 
following chart shows that:
\begin{shortlist}
\item The run-time of our more rigorous reduction method (PCA)
runs orders of magnitude slower than the the other methods. 
\item  Our least-thorough method runs in nearly constant time, even if
we increase the number of words.  However, this method has the benefit 
transparency to users.  That is, the features are English words and
not synthesized mathematical representations.
\end{shortlist}

\includegraphics[width=2.2in]{step_reduction_runtimes_N.eps} 


\end{minipage}

\end{kasten}
 
