      \begin{kasten}

        \section*{\hspace{0.1cm} {\color{red} \underline{IR = COMPRESSION}}}
Any real-world collection of documents many contain 10,000 to 1000,000 of terms and documents. The art of IR is throwing away the irrelevancies.
HAMLET has two such ``compression'' operators:\\

\begin{minipage}{.35\linewidth}
\bi
\item {\bf Reduction:} discard irrelevant terms
\item {\bf Cluster:} group documents together
effectively replacing multiple documents 
with a single meta-document
\ei

For example, the adjacent diagram groups 
terms by their information content and
the documents by their distance to each other:
\bi
\item We can now discard low information terms (those low in the term tree)
\item We can now group together similar documents (those close to each other)
\ei

\end{minipage}
\begin{minipage}{.5\linewidth}
%\begin{center}
\reflectbox{\includegraphics[height=3.3in,angle=270]{clusterbig.eps}}
%\end{center}
\end{minipage}


\end{kasten}


\begin{kasten}
        \section*{\hspace{0.1cm} {\color{red} \underline{SOME REDUCTION METHODS}}}
(Ranked top to bottom, 
slowest to fastest,
most-thorough to simplest:)
~\\

{\bf PCA:}  PCA (principal components analysis) treats every
row in $T*D$ as a point in N-dimensional space. PCA seeks new
dimensions that are better fits to those points.
For example,
the data shown below in two dimensions 
could be approximated in a single new dimension feature
(shown as a dashed lined).
\begin{center}
\includegraphics[width=2in]{pca.eps}
\end{center}
{\bf FASTMAP:} FASTMAP is a heuristic data reduction method
that uses a heuristic trick to find a line between
the two
points that could be furthest apart. A plane is added at right angles
to the end of
this line. The line is then pushed into the plane, mapping points in
$N$ dimensions to $N-1$. This process repeats until, say, $N=50$ and
the resulting points can be handled with more efficiency or even plotted in a 
visualization if $N$ is low enough.
~\\

{\bf TF*IDF:} (term frequency times inverse document
frequency). Zipf's Law tells us that the words that matter
appear a lot, but this is only useful if the words don't occur
in the majority of documents (think words like "with", "does", or "their").
Calculating Tf*Idf is a relatively simple and linear matter.
Let there be a set of documents $D$ (where each document is itself
a set) along with a set of terms $T$. Term frequency, $tf(t_i,D_j)$ is the
 number of times the word $t_i$ occurs in document $D_j$.  Document frequency, 
$df(t_i)$ is the total number of documents the term appears in (helps
prune out our "with", "does", etc. words).  Specifically,
\begin{center}
 $Tf*Idf(t,D_j) = \frac{tf(t_i,D_j)}{|D_j|}log(\frac{|D|}{df(t_i)})$
\end{center}

Which can be used for term reduction by creating

\begin{center}
$Tf*Ifd_{sum}(t)=\displaystyle\sum_{D_j \in D} Tf*Idf(t, D_j)$
\end{center}
for each term, sorting the terms on this value,
and returning the top $N$.

\end{kasten}


