\section{Analyzing the Scalability of Clustering Text Documents}

As stated above, the purpose of this experiment conducted for this thesis is to verify if lightweight data mining
methods perform worse than more thorough and rigorous ones.

The data sets used in this experiment are:

\begin{itemize}
\item EXPRESS schemas: AP-203, AP-214
\item Text mining datasets: BBC, Reuters, The Guardian (multi-view text datasets), 20 Newsgroup subsets:
sb-3-2, sb-8-2, ss-3-2, sl-8-2%\footnotetext[1]{\url{http://mlg.ucd.ie/datasets}}.
\end{itemize}

\subsubsection{Classes of Methods }

This experiment compares different {\em row} and {\em column} reduction methods. Given a table of data where
each row is one example and each columns counts different features, then:
\bi
\item
Row reduction methods {\em cluster} related rows into the same group;
\item
Column reduction methods remove columns with little information.
\ei

Reduction methods are essential in text mining. For example:
\bi
\item
 A standard text mining corpus may store information
in tens of thousands of columns. For such data sets, column reduction is an essential first step before any other
algorithm can execute

%\begin{quote}
%  One of the problems with high-dimensional datasets is that, in many cases, 
%not all the measured variables are ``important'' for understanding the underlying 
%phenomena of interest.
%\end{quote}
\item
The process of clustering data into similar groups can be used in a wide variety of applications, such as:
\begin{itemize}
  \item Marketing: finding groups of customers with similar behaviors given a large database of customer data
  \item Biology: classification of plants and animals given their features
  \item WWW: document classification and clustering weblog data to discover groups of similar access patterns\footnotetext[2]{\url{http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/}}.
\end{itemize}
\ei

%Thus the purpose of clustering is to ``determine the intrinsic grouping in a set of unlabeled data'' 
%XXXX adam. what does this do? \footnotemark[\value{footnote}]. 

%XXXX adam remove the following?
%Data can sometimes be overwhelmingly large, containing a great number of attributes, or dimensions. In order to reduce this vast multidimensional space, there exist dimensionality reduction methods. Dimensionality reduction filters the attributes, and attempts to select the most valid ones. In ``A Survey of Dimension Reduction Techniques'' \footnotetext[3]{\url{https://e-reports-ext.llnl.gov/pdf/240921.pdf}} by I.K. Fodor, Fodor writes:
%XXX make it a reference


\subsubsection{The Algorithms}

While there are many clustering algorithms used today, this experiment focused on three: a naive K-Means implementation, GenIc~\cite{genic04}, and clustering using canopies~\cite{canopies00}:
\be
\item
K-means, a special case of a class of EM algorithms, works as follows:
\begin{enumerate}
\item{Select initial {\em K} centroids at random;}
\item{Assign each incoming point to its nearest centroid;}
\item{Adjusts each cluster's centroid to the mean of each cluster;}
\item{Repeat steps 2 and 3 until the centroids in all clusters stop moving by a noteworthy amount}
\end{enumerate}
Here we use a naive implementation of K-means, requiring {\em K}*{\em N }*{\em I} comparisons, where {\em N} and {\em I} represent the total number of points and maximum iterations respectively.
\item
GenIc is a single-pass, stochastic clustering algorithm. It begins by initially selecting {\em K} centroids at random from all instances in the data. At the beginning of each generation, set the centroid weight to one. When new instances arrive, nudge the nearest centroid to that instance and increase the score for that centroid. In this process, centroids become ``fatter'' and slow down the rate at which they move toward newer examples. When a generation ends, replace the centroids with less than {\em X} percent of the max weight with {\em N} more random centroids. Genic
repeats for many generations, then returns the highest scoring centroids.
\item
Canopy clustering, developed by Google, reduces the need for comparing all items in the data using an expensive distance measure, by first partitioning the data into overlapping subsets called {\em canopies}. Canopies are first built using a cheap, approximate distance measure. Then, more expensive distance measures are used inside of each canopy to cluster the data. 
\ee
As to column reduction, I will focus on two methods:

\be
\item
PCA, or Principal Components Analysis, is a reduction method that
treats every instance in a dataset as a point in N-dimensional
space. PCA looks for new dimensions that better fit these points-- by mapping data points to these new dimensions where the variance is found to be maximized. Mathematically, this is conducted by utilizing eigenvalue decompositions of a
data covariance matrix or singular value decomposition of a data
matrix.
\fig{pca} shows an example of PCA.  Before, on the left-hand-side, the data exists in a two-dimensional
space, neither of which captures the distribution of the data. Afterwards, on the right-hand-side, a new dimension
has been synthesized that is more relevant to the data distribution.
\begin{figure}
\begin{center}
\includegraphics[width=2.25in]{figures/cs-pca.pdf}
\end{center}
\caption{A PCA dimension feature.}\label{fig:pca}
\end{figure}
\item
TF-IDF, or term frequency times inverse document frequency, reduces the number of terms (dimensions) by describing how important a term is in a document (or collection of documents) by incrementing its importance according to how many times the term appears in a document. However, this importance is also offset by the frequency of the term in the entire corpus. Thus, we are concerned with only terms that occur frequently in a small set of documents, and very infrequently everywhere else. To calculate the Tf*IDF value for each term in a document, I use the following equation:
\begin{equation} 
Tf*df(t,D_j) = \frac{tf(t_i,D_j)}{|D_j|}log(\frac{|D|}{df(t_i)})
\end{equation}

where $tf(t_i,D_j)$ denotes the frequency of term $i$ in document $j$, and $df(t_i)$ represents the number of documents containing term $i$. Here, $|D|$ denotes the number of documents in the corpus. To reduce all terms (and thus, dimensions), we must find the sum of the above
\begin{equation}
Tf*Ifd_{sum}(t) = \sum_{D_j\epsilon D}Tf*Idf(t,D_j)
\end{equation}
\ee

In theory, TF*IDF and GenIc should perform worse than K-Means, canopy clustering and PCA:
\bi
\item
Any single-pass algorithm  like GenIc
can be confused by ``order effects''; i.e. if the data arrives in some confusing order then the
single-pass algorithm can perform worse than other algorithms that are allowed to examine all the data. 
\item
TF*IDF is a heuristic method while PCA is a well-founded mathematical technique
\ei
On the other hand, the more rigorous methods are slower to compute:
\bi
\item Computing the correlation matrix used by PCA requires at least a $O(N^2)$ calculation.
\item As shown below, K-means is much slower than the other methods studied here.
\ei

\subsubsection{Building the Experiment}

This experiment was conducted entirely with OURMINE using a collection of BASH scripts, as well as custom Java code. The framework was built as follows:

\begin{enumerate}
\item{A command-line API was developed in Java for parsing the data, reducing/clustering the data, and outputting the data. Java was chosen due to its preferred speed for the execution of computationally expensive instructions.}
\item{The data was then iteratively loaded into this Java code via shell scripting. This provides many freedoms, such as allowing parameters to be altered as desired, as well as outputting any experimental results in any manner seen fit.}
\end{enumerate}


\fig{clusterworker} shows the OURMINE code for clustering data using the K-means algorithm. Shell scripting provides us with much leverage in this example. For instance, by looking at Lines 2-5, we can see that by passing the function four parameters, we can cluster data in the range from {\em minK} to {\em maxK} on all data in {\em dataDir}. This was a powerful feature used in this experiment, because it provides the opportunity to run the clusterer across multiple machines simultaneously. As a small example, suppose we wish to run K-means across three different machines with a minimum {\em K} of 2 and a maximum {\em K} of 256. Since larger values of {\em K} generally yield longer runtimes, we may wish to distribute the execution as follows:

\begin{verbatim}
Machine 1: clusterKmeansWorker 256 256 0 dataDir
Machine 2: clusterKmeansWorker 64 128 2 dataDir
Machine 3: clusterKmeansWorker 2 32 2 dataDir
\end{verbatim}

Lines 9-13 of \fig{clusterworker} load the data from {\em dataDir} for every {\em k}, and formats the name of the output file. Then, lines 15-19 begin the timer, cluster the data, and output statistical information such as {\em k}, the dataset, and runtime of the clusterer on that data set. This file will then be used later in the analysis of these clusters.

\begin{figure}
{\scriptsize\begin{verbatim}
1 clusterKmeansWorker(){
2     local minK=$1
3     local maxK=$2
4     local incVal=$3
5     local dataDir=$4
6     local stats="clusterer,k,dataset,time(seconds)"
7     local statsfile=$Save/kmeans_runtimes
8     echo $stats >> $statsfile
9     for((k=$minK;k<=$maxK;k*=$incVal)); do
10         for file in $dataDir/*.arff; do
11             filename=`basename $file`
12             filename=${filename%.*}
13             out=kmeans_k="$k"_$filename.arff 
14             echo $out
15             start=$(date +%s.%N)
16             $Clusterers -k $k $file $Save/$out
17             end=$(date +%s.%N)
18             time=$(echo "$end - $start" | bc)
19             echo "kmeans,$k,$filename,$time" >> $statsfile
20         done
21     done
22 }\end{verbatim}}
\caption{An OURMINE worker function to cluster data using the K-means algorithm. Note that experiments using other clustering methods (such as GenIc and Canopy), could be conducted by calling line 16 above in much the same way, but with varying flags to represent the clusterer.}\label{fig:clusterworker}
\end{figure}

Similarly, the flags in line 16 can be changed to perform a different action, such as clustering using GenIc or Canopy, by changing {\em -k} to {\em -g} or {\em -c} respectively, as well as finding cluster similarities (as described below) and purities, by using {\em -sim} and {\em -purity} as inputs. 


Since any number of variables can be set to represent different libraries elsewhere in OURMINE, the variable \begin{verbatim} $Reducers \end{verbatim} is used for the dimensionality reduction of the raw dataset, as seen in \fig{tfidfworker}, whose overall structure is very similar to \fig{clusterworker}.

\begin{figure}
{\scriptsize\begin{verbatim}
1 reduceWorkerTfidf(){
2     local datadir=$1
3     local minN=$2
4     local maxN=$3
5     local incVal=$4
6     local outdir=$5
7     local runtimes=$outdir/tfidf_runtimes

8    for((n=$minN;n<=$maxN;n+=$incVal)); do
9        for file in $datadir/*.arff; do
10            out=`basename $file`
11            out=${out%.*}
12            dataset=$out
13            out=tfidf_n="$n"_$out.arff
14            echo $out
15            start=$(date +%s)
16            $Reducers -tfidf $file $n $outdir/$out
17            end=$(date +%s)
18            time=$((end - start))
19            echo "tfidf,$n,$dataset,$time" >> $runtimes
20        done
21    done
22 }\end{verbatim}}
\caption{An OURMINE worker function to reduce the data using TF-IDF.}\label{fig:tfidfworker}
\end{figure}

\subsection{Results}   

To determine the overall benefits of each clustering method, this experiment used both cluster similarities, as well as the runtimes of each method.

%\subsubsection{Purities}
%When we cluster data that already has classes available to us, we can determine cluster purity. A cluster is considered relatively ``pure'' if it contains a high percentage of points that share the same class. Thus, we can say that this is a measure of the ``{\em quality} of a clustering solution''\footnotetext[1]{\url{http://www.cse.iitm.ac.in/~cs672/purity.pdf}}. 
%To determine the purity of individual clusters, the equation
%\begin{equation}
%purity(C_a)=\frac{1}{|C_a|}*max(|C_a|_{cl=b})
%\end{equation}
%was used, where a cluster $C_a$  contains $|C_a|_{cl=b}$ number of points assigned to class $b$. However, a high purity using this equation always is easy to obtain. For instance, if a cluster contains only one instance from the dataset, the purity of that cluster is always 1. Therefore, this study uses a weighted sum of these purities
%\begin{equation}
%purity=\sum_{a=1}^k\frac{|C_a|}{|D|}*purity(C_a)
%\end{equation}
%where $|D|$ denotes the number of documents in the dataset.

%To determine cluster purities, the following text datasets were used in conjunction with their natural classes:
%\begin{itemize}
%\item BBC: 5 natural classes (business, entertainment, politics, sport, tech);
%\item BBCSPORT: 5 natural classes (athletics, cricket, football, rugby, tennis\footnotetext[1]{\url{http://mlg.ucd.ie/datasets/bbc.html}};
%\end{itemize}
%The results of the cluster purity experiments are shown in \fig{pur1} and \fig{pur2}. By examining these results, we can see that the more complete methods (in this case K-means) yields the highest weighted purity. However, since each data set and its class distribution can drastically alter the outcome of these values, it is sometimes beneficial to use fast heuristic methods, as seen in the results for the BBC data set.    

%XXX more discussion

%\begin{figure}
%\begin{center}
%\includegraphics[width=5.50in]{bbc_purities}
%\end{center}
%\caption{Normalized weighted purity sums of clusters on the BBC data set.}\label{fig:pur1}

%\end{figure}

%\begin{figure}
%\begin{center}
%\includegraphics[width=5.50in]{bbcsport_purities}
%\end{center}
%\caption{Normalized weighted purity sums of clusters on the BBCSport data set.}
%\label{fig:pur2}
%\end{figure}

\subsubsection{Similarities}

Cluster similarities tell us how similar points are, either within a cluster ({\em Intra}-similarity), or with members of other clusters ({\em Inter}-similarity). The idea here is simple: gauge how well a clustering algorithm groups similar documents, and how well it separates different documents. Therefore, intra-cluster similarity values should be maximized, while minimizing inter-cluster similarities. 

Similarities are obtained by using the cosine similarity between two documents. The cosine similarity measure defines the cosine of the angle between two documents, each containing vectors of terms. The similarity measure is represented as

\begin{equation}
sim(D_i,D_j) = \frac{D_i \cdot D_j}{||D_i|| ||D_j||} = cos(\theta)
\end{equation}

where $D_i$ and $D_j$ denote two term frequency vectors for documents $i$ and $j$, and where the denominator contains magnitudes of these vectors. 

 Cluster similarities are determined as follows:

\begin{itemize}
\item{Cluster intra-similarity: For each document $d$ in cluster $C_i$, find the cosine similarity between $d$ and all documents belonging to $C_i$}
\item{Cluster inter-similarity: For each document $d$ in cluster $C_i$, find the cosine similarity between $d$ and all documents belonging to all other clusters}
\end{itemize}

Thus the resulting sum of these values represents the overall similarities of a clustering solution. \fig{sims} shows the results from the similarity tests conducted in this experiment. The slowest clustering and reduction methods were set as a baseline, because it was assumed that these methods would perform the best. With intra-similarity and inter-similarity values normalized to 100 and 0 respectively, we can see that surprisingly, faster heuristic clustering and reduction methods perform just as well or better than more rigorous methods. $Gain$ represents the overall score used in the assessment of each method, and is computed as a method's cluster $intra$-similarity value minus its $inter$-similarity value. Thus, the conclusions from this experiment shows that fast heuristic methods are sufficient for large data sets due to their scalability and performance.   

\begin{figure}
\centering
\small
\begin{tabular}{| c | c | c | c | c |}
\hline
Reducer and Clusterer & Time & InterSim & IntraSim & Gain \\ \hline
TF-IDF*K-means & 17.52 & -0.085 & 141.73 & 141.82 \\ \hline
TF-IDF*GenIc & 3.75 & -0.14 & 141.22 & 141.36 \\ \hline
PCA*K-means & 100.0 & 0.0 & 100.0 & 100.0 \\ \hline
PCA*Canopy & 117.49 & 0.00 & 99.87 & 99.87 \\ \hline
PCA*GenIc & 11.71 & -0.07 & 99.74 & 99.81 \\ \hline
TF-IDF*Canopy & 6.58 & 5.02 & 93.42 & 88.4 \\ \hline
\end{tabular}
\caption{Experiment \#3 (Text mining). Similarity values normalized according to the combination of most rigorous reducer and clusterer. Note that $Gain$ is a value representing the difference in cluster intrasimilarity and intersimilarity.} 
\label{fig:sims}
\end{figure}

