\chapter{Clustering}

SuperMatrix package provides several tools for clustering. They implement different kinds of algorithms, including flat, hierarchical and neural network clustering.

\label{sec:clutoformat}
\subsection*{CLUTO output format}
All clustering tools produce result as a text file in CLUTO \cite{Karypis:02} format. The number of lines in output file is strictly related to number of rows in clustered SuperMatrix. Each line contains only a number of group which the row is assigned to. Rows not assigned to any of groups (outliers) have number of cluster set to -1.

\section{KMeans}

\subsection*{Overview}
KMeans application implements flat clustering algorithm -- k-means. Its main idea is choosing random vectors as centroids and iterative assignment of each vector to most similar centroid until the stop condition is satisfied. After each iteration, centroids are set to mean of all cluster members. More information can be found HERE. The application can be found in clustering/kmeans folder. It contains library libkmeans.so and wrapper kmeans2cluto which produces clustering results in CLUTO output format, see: \ref{sec:clutoformat}.

\subsection*{Parameters description}

\begin{tabular}{lp{8.5cm}}
--help & Prints help message \\
--matrix-dir arg & Path to directory with SuperMatrix folder \\
--matrix-name arg & Name of SuperMatrix directory\\
--output-file arg & Path to clustering result file (optional) \\
--sim-fun arg & One of available similarity functions (SEE...) \\
--clusters arg & Required number of clusters \\
--seed arg & Random generator seed (optional integer) \\
--epsilon arg & Minimal difference between iterations --stop condition (optional --~default 0.001) \\
\end{tabular}

\subsection*{Usage}
To use KMeans application you require folder with supermatrix (CRS matrix only is sufficient). Clustering starts with the following sample command:

\begin{verbatim}
$ kmeans2cluto --matrix-dir /home/user/SuperMatrices
-matrix-name MySuperMatrix --sim-fun "lin_cos()" --clusters 5
\end{verbatim}

\textit{/home/user/SuperMatrices} is sample directory with SuperMatrix folder. \textit{MySuperMatrix} is name of the actual SuperMatrix folder. Please be noted, that in the following case all SuperMatrix files should be placed in \textit{/home/user/SuperMatrices/MySuperMatrix} directory.

You can also add some optional parameters. Random generator seed is used to algorithm initialization. Omitting this parameter will result in random initialization. If you want to repeat clustering with the same results, you should specify the seed as the same integer.
Epsilon number determinates number of iterations of algorithm. This number should be determined experimentally, however if the clustering works fine, you can omit this parameter leaving its default value. If you don't specify the output file parameter, the application will create one in SuperMatrix directory.

\section{KMedoids}

\subsection*{Overview}
KMedoids program is an implementation of k-medoids algorithm -- which is modification of k-means. The main difference is using medoids instead of centroids. In each iteration the most central member of each cluster is choosen for medoid. In current implementation algorithm stops when all possible medodis combination are checked. More information about this algorithm can be found HERE. Application is placed in clustering/kmedoids folder. Similar to KMeans program, it is divided into two files: library libkmedoids.so and wrapper kmedoids2cluto.

\subsection*{Parameters description}

\begin{tabular}{ll}
--help & Prints help message \\
--matrix-dir arg & Path to directory with SuperMatrix folder \\
--matrix-name arg & Name of SuperMatrix directory \\
--output-file arg & Path to clustering result file (optional) \\
--sim-fun arg & One of available similarity functions (see...) \\
--clusters arg & Required number of clusters \\
--seed arg & Random generator seed (optional integer) \\
\end{tabular}

\subsection*{Usage}
Usage is identical to KMeans application. You require only CRS matrix. Sample execution command:

\begin{verbatim}
$ kmedoids2cluto --matrix-dir /home/user/SuperMatrices
--matrix-name MySuperMatrix --sim-fun "tfidf()" --clusters 5
\end{verbatim}

All parameters are similar to mentioned in KMeans section (except epsilon). KMedoids Application has its own stop condition, so there is no need to set additional parameters. Results are saved in CLUTO output format as usual.

\section{GHSOM}

\subsection*{Overview}
GHSOM program contains an implementation of an artificial neural network proposed in \cite{ghsom}. GHSOM stands for Growing Hierarchical Self-Organizing Map. It is a kind of SOM network, learned in unsupervised way, enhanced by growing in two dimensions. Vertical expansion divides members assigned to one neuron (cluster) to several new clusters, creating new subnetwork in hierarchy. Horizontal expansion causes growing dimensions of each map and its submaps. Growing can be controlled by two real values $t_1$ and $t_2$. Application is located in clustering/som directory.

\subsection*{Parameters description}

\begin{tabular}{ll}
--help & Prints help text \\
--matrix-dir arg & Path to directory with SuperMatrix folder \\
--matrix-name arg & Name of SuperMatrix directory \\
--output-file arg & Clustering output file in local GHSOM format \\
--cluto-file arg & Clustering output file in CLUTO format \\
--cmp-fun arg & Compare function used to weight matrix \\
--t1 arg & Horizontal expansion threshold (optional) \\
--t2 arg & Vertical expansion threshold (optional) \\
--first arg & Save first layer only (optional) \\
\end{tabular}

\subsection*{Usage}
To start clustering using GHSOM you need to have SuperMatrix (at least CRS part). Specify path to the matrix using matrix dir and matrix name parameters. If you are not satisfied with the default values ($t_1 = 0.75$ and $t_2 = 0.05$), you may also try to set your own thresholds for network expansion. GHSOM program provides two ways of displaing results -- first is compliant with CLUTO output format, second is local format of GHSOM which is more human-readable. There is also an additional parameter, which allows you to save results only from first layer of network (may be useful if you need more general results).

Sample command to execute GHSOM appliaction:

\begin{verbatim}
$ som --matrix-dir /home/user/SuperMatrices --matrix-name
MySuperMatrix --cmp-fun "tfidf()" --t1 0.8 --t2 0.07
--first true --cluto-file result.txt
\end{verbatim}

\section{CBC}

\subsection*{Overview}
CBC application implements algorithm called Clustering by Committee, proposed in \cite{pantelCBC}. Its main idea is to determine a set of tight clusters, so called committees. Each of such clusters is represented by its centroid, used in further assigning vectors to cluster. 

\subsection*{Parameters description}

\begin{tabular}{ll}
Cbc options: & \\
--help                         & Prints help text \\
--config-file arg (=cbc.cfg)   & Config file path \\
--cluto-path arg               & Path to scluster executable file \\
--matrix-dir arg               & Path to supermaatrix dir \\
--matrix-name arg              & Name of the supermatrix \\
--kbest-file arg               & Path to k-best file \\
--workdir arg                  & Path to workdir \\
--k arg                        & K-best for clustering \\
--theta1 arg                   & Theta 1 \\
--theta2 arg                   & Theta 2 \\
--sigma arg                    & Sigma \\
--not-similar-treshold arg     & Not similar treshold \\
--simmatrix-top-x arg          & Sim matrix top x \\
--phase3-top-x arg             & Phase 3 top x \\
--committee-output-file arg    & Committee output file path \\
--committee-output-suffix arg  & Committee output file suffix \\
--committee-min-tf arg         & Committee min tf \\
--committee-min-nz arg         & Committee min nz \\
--committee-sum-tf-treshold arg & Committee sum tf treshold \\
--clmethod arg                 & Clmethod \\
--crfun arg                    & Crfun \\
--remove-features arg          & Removing features type \\
--cluto-file arg               & Path to cluto output file \\
\\
Output options: & \\
--verbose            & Produce lots of output for cbc \\
--cluto-verbose      & Produce lots of output for cluto \\ 
--intermediate       & Produce intermediate output for cbc \\
--cluto-intermediate & Save cluto intermediate results \\
\end{tabular}

\subsection*{Usage}
In order to use CBC application, you have to specify all paths from Cbc options section, that is: path to CLUTO scluster executable, path to super matrix directory and the folder name, path to workdir and path to output file in CLUTO format. There all also lots of additional numeric parameters, which can be leaved as default or tuned if you need. It is recommended to use config file instead of command line options (if present, program reads cbc.cfg file by default).

Sample CBC usage:

\begin{verbatim}
cbc --cluto-path /usr/local/bin/scluster --config-file
/home/user/cbc/file.cfg --k 5 --cluto-file
/home/user/cbc/output.txt --theta1 0.45
\end{verbatim}

\section{ROCK}

\subsection*{Overview}
ROCK algorithm belongs to agglomerative hierarchical clustering algorithms. It is wider described in \cite{guha00rock}. 

\subsection*{Parameters description}

\begin{tabular}{ll}
--help               & Prints help text \\
--matrix-dir arg     & Path to supermatrix \\
--matrix-name arg    & Name of supermatrix \\
--output-file arg    & Clustering output file \\
\end{tabular}

\subsection*{Usage}
ROCK application needs to work only SuperMatrix (path and folder name) and path to output file. 

Sample ROCK usage:

\begin{verbatim}
rock --matrix-dir /home/user/rock/ --matrix-name SampleMatrix
 --output-file /home/user/rock/rock.txt
\end{verbatim}

\section{Clustering evaluator}

\subsection*{Overview}
Clustering evaluator is an application used to automated evaluation of clustering processes. It has several -- currently four -- measures implemented, according to \cite{ManRagSch:08}. The application is located in tools/clustering/clustering\_evaluator directory.

\subsection*{Parameters description}

\begin{tabular}{ll}
--help & Prints help text \\
--cluto-file arg & Path to file in CLUTO output format \\
--class-file arg & Path to file containing class labels \\
\end{tabular}

\subsection*{Usage}
To use Clustering evaluator you need a text file representing results of clustering. The file has to be compliant with CLUTO output format, so you can evaluate results produced by CLUTO or any of clustering tools contained in SuperMatrix. To evaluate clustering in automatic way, you need also to provide additional information about appropriate class of each object. Since we cluster SuperMatrix rows, we need a file containing name of the class of each row in corresponding line. Both files has to have identical number of lines.

Execution of evaluation process should be started with the following command:

\begin{verbatim}
$ evaluator --cluto-file /home/user/clustering.txt
--class-file /home/user/classes.txt
\end{verbatim}

By default the results of evaluation are displayed on the screen. If you want to put them into the file, use:

\begin{verbatim}
$ evaluator --cluto-file /home/user/clustering.txt
--class-file /home/user/classes.txt > /home/user/evaluation.txt
\end{verbatim}

Results of clustering evaluation contain partial results fo each method (such as entropy for Normalized Mutual Information or True Positives for Rand Index) and the marked section with main results of each measure. There is also information about number of clusters found by the algorithm and number of non-clustered objects (outliers). 

