\documentclass[]{article}
\usepackage{xspace,myart2e}
\setstretch{1.1}

\def\cluto{{\sf\scshape Cluto}\xspace}
\def\vcluster{{\sf vcluster}\xspace}
\def\scluster{{\sf scluster}\xspace}
\def\clutolib{{\sf\scshape Cluto}lib\xspace}
\def\chameleon{{\sc Chameleon}\xspace}
\def\metis{{\sf\scshape {M}\kern-.1em{e}\kern-.25em{T}\kern-.25em{i}\kern-.05em{S}}\xspace}
\def\hmetis{{\sf h}\kern-.1em\metis}



\def\ione{{\mbox{$\cal{I}_1$}}\xspace}
\def\itwo{{\mbox{$\cal{I}_2$}}\xspace}
\def\eone{{\mbox{$\cal{E}_1$}}\xspace}
\def\hone{{\mbox{$\cal{H}_1$}}\xspace}
\def\htwo{{\mbox{$\cal{H}_2$}}\xspace}
\def\gone{{\mbox{$\cal{G}_1$}}\xspace}
\def\goneprime{{\mbox{$\cal{G}'_1$}}\xspace}
\def\sign{{\mbox{sign}}\xspace}
\def\nrm#1{\mbox{$\|#1\|$}}
\def\dotp#1#2{{#1}^{t}{#2}}


\def\titlefont{\fontencoding{T1}\fontfamily{pag}\fontseries{b}\fontshape{n}\fontsize{42}{46pt}\selectfont}
\def\subtitlefont{\fontencoding{T1}\fontfamily{pag}\fontseries{b}\fontshape{n}\fontsize{28}{32pt}\selectfont}


\def\checkmark{\ding{53}}
\def\checkmarkno{\ding{54}}

\renewcommand{\topfraction}{.95}
\renewcommand{\bottomfraction}{.95}

\title{\titlefont \cluto\thanks{%
\cluto is copyrighted by the regents of the University of Minnesota.
This work was supported by NSF CCR-9972519, EIA-9986042, ACI-9982274, 
by Army Research Office contract DA/DAAG55-98-1-0441, by the DOE ASCI 
program, and by Army High Performance Computing Research Center contract 
number DAAH04-95-C-0008. Related papers are available via WWW at 
URL: {\bf\sf http://www.cs.umn.edu/\~{}karypis}. 
The name \cluto is derived from CLUstering TOolkit.}}
\subtitle{{\subtitlefont A Clustering Toolkit}\\
          {\Large Release 2.1}}
\author{George Karypis}
\email{karypis@cs.umn.edu}
\address{University of Minnesota, Department of Computer Science \\ Minneapolis, MN 55455\\
         Technical Report: \#02-017}
\date\today


\setcounter{tocdepth}{3}

\begin{document}
\maketitle
\clearpage

\tableofcontents
\clearpage



%*************************************************************************
\section{Introduction}

Clustering algorithms divide data into meaningful or useful groups, called
{\em clusters}, such that the intra-cluster similarity is maximized and the 
inter-cluster similarity is minimized. These discovered clusters can be used 
to explain the characteristics of the underlying data distribution and thus 
serve as the foundation for various data mining and analysis techniques. 
The applications of clustering include characterization of different customer 
groups based upon purchasing patterns, categorization of documents on the 
World Wide Web, grouping of genes and proteins that have similar functionality, 
grouping of spatial locations prone to earth quakes from seismological data, 
\etc.




%=========================================================================
\subsection{What is \cluto}
\label{sec:about}

\cluto is a software package for clustering low and high dimensional 
datasets and for analyzing the characteristics of the various clusters. 

\cluto provides three different classes of clustering algorithms that
operate either directly in the object's feature space or in the object's
similarity space. These algorithms are based on the partitional, 
agglomerative, and graph-partitioning paradigms. A key feature in most 
of \cluto's clustering algorithms is that they treat the clustering 
problem as an optimization process which seeks to maximize or minimize 
a particular {\be clustering criterion function} defined either globally 
or locally over the entire clustering solution space. \cluto provides 
a total of seven different criterion functions that can be used to drive 
both partitional and agglomerative clustering algorithms, that are described 
and analyzed in \cite{zhao01tr-vpcluster, zhao02cikm}. Most of 
these criterion functions have been shown to produce high quality clustering 
solutions in high dimensional datasets, especially those arising in document 
clustering.  In addition to these criterion functions, \cluto provides some 
of the more traditional local criteria (\eg., single-link, complete-link, 
and UPGMA) that can be used in the context of agglomerative clustering. 
Furthermore, \cluto provides graph-partitioning-based clustering algorithms 
that are well-suited for finding clusters that form contiguous regions 
that span different dimensions of the underlying feature space.

An important aspect of partitional-based criterion-driven clustering 
algorithms is the method used to optimize this criterion function. 
\cluto uses a randomized incremental optimization algorithm that is 
greedy in nature, has low computational requirements, and has been shown 
to produce high-quality clustering solutions \cite{zhao01tr-vpcluster}.
\cluto's graph-partitioning-based clustering algorithms utilize 
high-quality and efficient multilevel graph partitioning algorithms
derived from the \metis and \hmetis graph and hypergraph partitioning
algorithms \cite{karypis98metis,karypis98hmetis}.

\cluto also provides tools for analyzing the discovered clusters to understand 
the relations between the objects assigned to each cluster and the relations 
between the different clusters, and tools for visualizing the discovered 
clustering solutions. \cluto can identify the features that best describe 
and/or discriminate each cluster. These set of features can be used to gain 
a better understanding of the set of objects assigned to each cluster and 
to provide concise summaries about the cluster's contents. Moreover, 
\cluto provides visualization capabilities that can be used to see the 
relationships between the clusters, objects, and features.

\cluto's algorithms have been optimized for operating on very large datasets
both in terms of the number of objects as well as the number of dimensions.
This is especially true for \cluto's algorithms for partitional clustering.
These algorithms can quickly cluster datasets with several tens of thousands 
objects and several thousands of dimensions. Moreover, since most high-dimensional 
datasets are very sparse, \cluto directly takes into account this sparsity and 
requires memory that is roughly linear on the input size.

\cluto's distribution consists of both stand-alone programs (\vcluster and
\scluster) for clustering and analyzing these clusters, as well as, a library 
via which an application program can access directly the various clustering 
and analysis algorithms implemented in \cluto.


%=========================================================================
\subsection{Outline of \cluto's Manual}
\label{sec:intro:outline}

\cluto's manual is organized as follows. 
\secref{sec:usage} describes the stand-alone programs provided by \cluto, 
and discusses its various options and analysis capabilities.
\secref{sec:clmethod} describes the type of clusters that \cluto's 
algorithms can find, and discusses their scalability.
\secref{sec:library} describes the application programming interface 
(API) of the stand-alone library that implements the various algorithms 
implemented in \cluto. 
Finally, \secref{sec:epiloge} describes the system requirements for the 
\cluto package.


%*************************************************************************
\section{Major Changes From Release 2.0}
\label{sec:whatsnew}

The latest release of \cluto contains a number of changes and additions over 
its earlier release. The major changes are the following:

\begin{enumerate}
\item
  \cluto provides a new class of {\be biased agglomerative} clustering algorithms 
  that use a partitional clustering solution to bias the agglomeration process.
  The key motivation behind these algorithms is to use a partitional clustering
  solution that optimizes a global criterion function to limit the number of
  errors performed during the early stages of the agglomerative algorithms.
  Extensive experiments with these algorithms on document datasets show that
  they lead to superior clustering solutions \cite{zhao02cikm}.
  
\item  
  \cluto provides a new method for analyzing the discovered clusters and identify 
  the set of features that co-occur within the objects of each cluster.
  This functionality is provided via the new {\em -showsummaries} parameter.

\item
  \cluto provides a new method for selecting the cluster to be bisected next
  in the context of partitional clustering algorithms based on repeated bisectioning.
  This method that is specified by selecting {\em -cstype=largess} is based
  on analyzing the set of dimensions ({\ie., subspace}) that account for the bulk 
  of the similarity of each cluster, and selecting the cluster that leads to 
  the largest decrease of these dimensions. This approach was motivated by
  the observation that in high-dimensional datasets, good clusters are embedded
  in low-dimensional subspaces.
  
\item
  \cluto's graph partitioning algorithms can now compute the similarity between
  objects using the extended Jaccard coefficient that takes into account both the
  direction and the magnitude of the object vectors. Experiments with high-dimensional
  datasets arising in commercial and document domains showed that this similarity 
  function is better than cosine-based similarity.

\end{enumerate}


\newpage
%*************************************************************************
\section{Using \cluto via its Stand-Alone Program}
\label{sec:usage}

\cluto provides access to its various clustering and analysis algorithms via the 
\vcluster and \scluster stand-alone programs. The key difference between 
these programs is that \vcluster takes as input the actual multi-dimensional 
representation of the objects that need to be clustered (\ie., ``v'' comes 
from {\em vector}), whereas \scluster takes as input the similarity matrix 
(or graph) between these objects (\ie., ``s'' comes from {\em similarity}). 
Besides this difference, both programs provide similar functionality.

The rest of this section describes how to use these programs, how to interpret 
their output, the format of the various input files they require, and the format 
of the output files they produce. 



%=========================================================================
\subsection{The \vcluster and \scluster Clustering Programs}
\label{sec:usage:vcluster}

The \vcluster and \scluster programs are used to cluster a collection of 
objects into a predetermined number of clusters $k$. The \vcluster program 
treats each object as a vector in a high-dimensional space, and it computes 
the clustering solution using one of five different approaches. Four of 
these approaches are {\em partitional} in nature, whereas the fifth approach
is {\em agglomerative}. On the other hand, the \scluster program operates on 
the similarity space between the objects and can compute the overall clustering
solution using the same set of five different approaches.

Both the \vcluster and \scluster programs are invoked by providing two required 
parameters on the command line along with a number of optional parameters. 
Their overall calling sequence is as follows:
%
\begin{tabbing}
  \hspace{1cm} \= {\bf \vcluster} \hspace{10pt} \= [optional parameters] \hspace{10pt} {\em MatrixFile} \hspace{10pt} \= {\em NClusters}\\
  \hspace{1cm} \> {\bf \scluster} \hspace{10pt} \> [optional parameters] \hspace{10pt} {\em GraphFile} \hspace{10pt} \> {\em NClusters}
\end{tabbing}
%
{\em MatrixFile\/} is the name of the file that stores the $n$ objects to be 
clustered. In \vcluster, each one of these objects is considered to 
be a vector in an $m$-dimensional space. The collection of these objects is 
treated as an $n\times m$ matrix, whose rows correspond to the objects, and 
whose columns correspond to the dimensions of the feature space. The exact 
format of the matrix-file is described in \secref{sec:usage:iformat:matrix}. 
Similarly, {\em GraphFile\/}, is the name of the file that stores the adjacency 
matrix of the similarity graph between the $n$ objects to be clustered. 
The exact format of the graph-file is described in \secref{sec:usage:iformat:graph}. 
The second argument for both programs, {\em NClusters}, is the number of clusters 
that is desired.  

Upon successful execution, \vcluster and \scluster display statistics regarding 
the quality of the computed clustering solution and the amount of time taken to 
perform the clustering. The actual clustering solution is stored in a file named 
{\be MatrixFile.clustering.NClusters\/} (or {\be GraphFile.clustering.NClusters\/}), 
whose format is described in \secref{sec:usage:oformat:clustering}.

The behavior of \vcluster and \scluster can be controlled by specifying a number 
of different optional parameters (described in subsequent sections). These parameters 
can be broadly categorized into three groups. The first group controls various 
aspects of the clustering algorithm, the second group controls the type of analysis 
and reporting that is performed on the computed clusters, and the third set controls the 
visualization of the clusters. The optional parameters are specified using the standard 
{\tt -paramname} or {\tt -paramname=value} formats, where the name of the optional 
parameter {\tt paramname} can be truncated to a unique prefix of the parameter name.


%--------------------------------------------------------------------------
\paragraph{Examples of Using \vcluster and \scluster}

\figref{fig:sample-vcluster} shows the output of \vcluster for clustering a 
matrix into 10 clusters. From this figure we see that \vcluster initially prints 
information about the matrix, such as its name, the number of rows ({\em \#Rows}),
the number of columns ({\em \#Columns}), and the number of non-zeros in the 
matrix ({\em \#NonZeros}). Next it prints information about the values of the
various options that it used to compute the clustering (we will discuss the 
various options in the subsequent sections), and the number of 
desired clusters ({\em \#Clusters}). Once it computes the clustering solution, 
it displays information regarding the quality of the overall clustering solution 
and the quality of each cluster. The meaning of the various measures that are 
reported will be discussed in \secref{sec:usage:vcluster:stats}.
Finally, \vcluster reports the time taken by the various phases of the program.
For this particular example, \vcluster required 0.950 seconds to read the input
file and write the clustering solution, 9.060 seconds to compute the actual
clustering solution, and 0.240 seconds to compute statistics on the quality of
the clustering. 


\begin{figure}[htb]
\centerline{\input{./examples/example1.tex}}
\caption{Output of \vcluster for matrix {\em sports.mat\/} and a 10-way clustering.}
\label{fig:sample-vcluster}
\end{figure}

Similarly, \figref{fig:sample-scluster} shows the output of \scluster for 
clustering a different dataset into 10 clusters. In this example the 
similarity between the objects was computed as the cosine between the object 
vectors.  From this figure we see that \scluster initially prints information 
about the graph, such as its name, the number of vertices ({\em \#vtxs}), and 
the number of edges in the graph ({\em \#Edges}). Next it prints information 
about the values of the various options that it used to compute the clustering, 
and the number of desired clusters ({\em \#Clusters}). Once it computes the 
clustering solution, it displays information regarding the quality of the 
overall clustering solution and the quality of each cluster. 
Finally, \scluster reports the time taken by the various phases of the program.
For this particular example, \scluster required 12.930 seconds to read the 
input file and write the clustering solution, 34.730 seconds to compute the 
actual clustering solution, and 0.610 seconds to compute statistics on the 
quality of the clustering. Note that even though the dataset used by
\scluster contained only 3204 objects, it took almost $3\times$ more
time than that required by \vcluster to cluster a dataset with 8580
objects. The performance difference between these two approaches is due 
to the fact that \scluster operates on the graph that in this example 
contains almost $3204^2$ edges.


\begin{figure}[htb]
\centerline{\input{./examples/example2.tex}}
\caption{Output of \scluster for graph {\em la1.graph\/} and a 10-way clustering.}
\label{fig:sample-scluster}
\end{figure}





%=========================================================================
\subsubsection{Clustering Algorithm Parameters}
\label{sec:usage:vcluster:clparams}

There are a total of 18 different optional parameters that control how \vcluster 
and \scluster compute the clustering solution. The name and function of these 
parameters is described in the rest of this section. Note for each parameter
we also list the program(s) for which they are applicable.


\begin{Lentry}
  \item[\mbox{\makebox[6.5in]{-clmethod=string \hfill \vcluster \& \scluster}}]
       This parameter selects the method to be used for clustering the objects.
       The possible values are:
       \begin{Ventry}{directXX}{\bf}
         \item[rb]  
             In this method, the desired $k$-way clustering solution is computed
             by performing a sequence of $k-1$ {\be repeated bisections}. 
             In this approach, the matrix is first clustered into two groups, 
             then one of these groups is selected and bisected further. This process 
             continuous until the desired number of clusters is found. During each 
             step, the cluster is bisected so that the resulting 2-way clustering 
             solution optimizes a particular clustering criterion function (which 
             is selected using the {\em -crfun} parameter). Note that this approach 
             ensures that the criterion function is locally optimized within each 
             bisection, but in general is not globally optimized. The cluster that 
             is selected for further partitioning is controlled by the {\em -cstype} 
             parameter. By default, \vcluster uses this approach to find the $k$-way 
             clustering solution.

         \item[rbr]
             In this method the desired $k$-way clustering solution is computed 
             in a fashion similar to the repeated-bisecting method but at the end,
             the overall solution is globally optimized. Essentially, \vcluster 
             uses the solution obtained by {\em -clmethod=rb} as the initial 
             clustering solution and tries to further optimize the clustering 
             criterion function.
       
         \item[direct]  
             In this method, the desired $k$-way clustering solution is computed
             by simultaneously finding all $k$ clusters. In general, computing a 
             $k$-way clustering directly is slower than clustering via repeated 
             bisections. In terms of quality, for reasonably small values of $k$ 
             (usually less than 10--20), the direct approach leads to better 
             clusters than those obtained via repeated bisections. However, as 
             $k$ increases, the repeated-bisecting approach tends to be better 
             than direct clustering. 
             
         \item[agglo]  
             In this method, the desired $k$-way clustering solution is computed
             using the {\be agglomerative} paradigm whose goal is to locally 
             optimize (minimize or maximize) a particular clustering criterion
             function (which is selected using the {\em -crfun} parameter).
             The solution is obtained by stopping the agglomeration process when
             $k$ clusters are left.

         \item[graph]  
             In this method, the desired $k$-way clustering solution is computed
             by first modeling the objects using a nearest-neighbor graph (each 
             object becomes a vertex, and each object is connected to its most 
             similar other objects), and then splitting the graph into $k$-clusters
             using a min-cut graph partitioning algorithm. {\bf Note that if the graph
             contains more than one connected component, then \vcluster and \scluster 
             return a $(k+m)$-way clustering solution, where $m$ is the number 
             of connected components in the graph.} 

         \item[bagglo]  
             In this method, the desired $k$-way clustering solution is computed
             in a fashion similar to the {\em agglo} method; however, the 
             agglomeration process is biased by a partitional clustering solution 
             that is initially computed on the dataset. When {\em bagglo} is used,
             \cluto first computes a $\sqrt{n}$-way clustering solution using the
             {\em rb} method, where $n$ is the number of objects to be clustered.
             Then, it augments the original feature space by adding $\sqrt{n}$ new
             dimensions, one for each cluster. Each object is then assigned a value 
             to the dimension corresponding to its own cluster, and this value
             is proportional to the similarity between that object and its 
             cluster-centroid. Now, given this augmented representation, the 
             overall clustering solution is obtained by using the traditional
             agglomerative paradigm and the clustering criterion function selected 
             using the {\em -crfun} parameter. The solution is obtained by stopping 
             the agglomeration process when $k$ clusters are left. Our experiments
             on document datasets, showed that this {\em biased} agglomerative
             approach always outperformed the traditional agglomerative algorithms
             \cite{zhao02cikm}.

       \end{Ventry}

       The suitability of these clustering methods are in general domain and application
       dependent. \secref{sec:clmethod} discusses relative merits of the various 
       methods and their scalability characteristics. Also, you can refer to
       \cite{zhao01tr-vpcluster,zhao02cikm} (which are included with \cluto' 
       distribution) for a detailed comparisons of the {\em rb}, {\em rbr}, 
       {\em direct}, {\em agglo}, and {\em bagglo}  approaches in the context of 
       clustering document datasets. 
       


  \item[\mbox{\makebox[6.5in]{-sim=string \hfill \vcluster}}]
       Selects the similarity function to be used for clustering. The possible values are:
       \begin{Ventry}{corre}{\bf}
         \item[cos]  The similarity between objects is computed using the cosine function.
                     This is the default setting.
         \item[corr] The similarity between objects is computed using the correlation 
                     coefficient.
         \item[dist] The similarity between objects is computed to be inversely
                     proportional to the Euclidean distance between the objects.
                     This similarity function is only applicable when {\em -clmethod=graph}.
         \item[jacc] The similarity between objects is computed using the extended Jaccard
                     coefficient.  This similarity function is only applicable when 
                     {\em -clmethod=graph}.
       \end{Ventry}

       The runtime of \vcluster may increase for {\em -sim=corr}, as it needs to store 
       and operate on the dense $n\times m$ matrix. 
       

  \item[\mbox{\makebox[6.5in]{-crfun=string \hfill \vcluster \& \scluster}}]
       This parameter selects the particular clustering criterion function to be used in
       finding the clusters. A total of seven different clustering criterion functions are 
       provided that are selected by specifying the appropriate integer value. The
       possible values for {\em -crfun} are: 
       \begin{Ventry}{wclink}{\bf}
         \item[i1]     Selects the I1 criterion function.
         \item[i2]     Selects the I2 criterion function.
                       This is the default setting for the {\em rb}, {\em rbr}, and 
                       {\em direct} clustering methods. 
         \item[e1]     Selects the E1 criterion function. 
         \item[g1]     Selects the G1 criterion function. 
         \item[g1p]    Selects the G1$'$ criterion function. 
         \item[h1]     Selects the H1 criterion function.
         \item[h2]     Selects the H2 criterion function.
         \item[slink]  Selects the traditional single-link criterion function.
         \item[wslink] Selects a cluster-weighted single-link criterion function.
         \item[clink]  Selects the traditional complete-link criterion function.
         \item[wclink] Selects a cluster-weighted complete-link criterion function.
         \item[upgma]  Selects the traditional UPGMA criterion function.
                       This is the default setting for the {\em agglo} and {\em bagglo}
                       clustering methods. 
       \end{Ventry}

       The precise mathematical definition of the first seven functions is shown in
       \tblref{tbl:crfundef}. The reader is referred to \cite{zhao01tr-vpcluster} for
       both a detailed description and evaluation of the various criterion functions.
       The {\em slink}, {\em wslink}, {\em clink}, {\em wclink}, and {\em upgma} 
       criterion functions can only be used within the context of agglomerative 
       clustering, and cannot be used for partitional clustering. 
       
       The {\em wslink} and {\em wclink} criterion function were designed for building 
       an agglomerative solution on top of an existing clustering solution (see {\em 
       -agglofrom}, or {\em -showtree} options). In this context, the weight of the 
       ``link'' between two clusters $S_i$ and $S_j$ is set equal to the aggregate 
       similarity between the objects of $S_i$ to the objects in $S_j$ divided by 
       the total similarity between the objects in $S_i \bigcup S_j$.

       The various criterion functions can sometimes lead to significantly
       different clustering solutions. In general, the \itwo and \htwo criterion
       functions lead to very good clustering solutions, whereas the \eone and
       \goneprime criterion functions leads to solutions that contain clusters
       that are of comparable size. However, the choice of the {\em right}
       criterion function depends on the underlying application area, and the 
       user should perform some experimentation before selecting one appropriate
       for his/her needs.

       Note that the computational complexity of the agglomerative clustering
       algorithms (\ie., {\em -clmethod=agglo} or {\em -clmethod=bagglo}) depend 
       on the criterion function that is selected. In particular, if $n$ is the 
       number of objects, the complexity for \hone and \htwo criterion functions 
       is $O(n^3)$, whereas the complexity of the remaining criterion functions 
       is $O(n^2\log n)$. The higher complexity for \hone and \htwo is due to 
       the fact that these two criterion functions are defined globally over the 
       entire solution and they cannot be accurately evaluated based on the local 
       combination of two clusters.

\begin{table}[htb]
\begin{center}
\input{formula.tbl}
\end{center}
\caption{The mathematical definition of \cluto's clustering criterion functions.
         The notation in these equations are as follows: $k$ is the total number
         of clusters, $S$ is the total objects to be clustered, $S_i$ is the set
         of objects assigned to the $i$th cluster, $n_i$ is the number of objects
         in the $i$th cluster, $v$ and $u$ represent two objects, and $\mbox{sim}(v,u)$
         is the similarity between two objects.}
\label{tbl:crfundef}
\end{table}

  \item[\mbox{\makebox[6.5in]{-agglofrom=int \hfill \vcluster \& \scluster}}]
       This parameter instructs the clustering programs to compute a clustering
       by combining both the partitional and agglomerative methods. In this
       approach, the desired $k$-way clustering solution is computed by first
       clustering the dataset into $m$ clusters ($m > k$), and then the final
       $k$-way clustering solution is obtained by merging some of these clusters
       using an agglomerative algorithm. The number of clusters $m$ is the 
       input to this parameter. The method used to obtained the agglomerative 
       solution is controlled by the {\em -agglocrfun} parameter.
       
       This approach was motivated by the two-phase clustering approach of the 
       \chameleon algorithm \cite{karypis99ieeecomputer}, and was designed to 
       allow the user to compute a clustering solution that uses a different
       clustering criterion function for the partitioning phase from that used
       for the agglomeration phase. An application of such an approach is to
       allow the clustering algorithm to find non-globular clusters. In this
       case, the partitional clustering solution can be computed using a
       criterion function that favors globular clusters (\eg., `i2'), and 
       then combine these clusters using a single-link approach (\eg., `wslink')
       to find non-globular but well-connected clusters.  \figref{fig:spatial} 
       shows two such examples for two 2D point datasets. 

\begin{figure}[tb]
\centerline{\psfig{figure=./figures/tfig1.eps,width=6in}}
\caption{Examples of using the {\em -agglofrom} option for two spatial datasets.
         The result in (a) was obtained by running `\vcluster t4.mat 6 -clmethod=graph
         -sim=dist -agglofrom=30' and the results in (b) was obtained by running
         `\vcluster t7.mat 9 -clmethod=graph -sim=dist -agglofrom=30'.}
\label{fig:spatial}
\end{figure}

       
  \item[\mbox{\makebox[6.5in]{-agglocrfun=string \hfill \vcluster \& \scluster}}]
       This parameter controls the criterion function that is used during the
       agglomeration when the {\em -agglofrom} or the {\em -fulltree} option was 
       specified. The values that this parameter can take are identical to those 
       used by the {\em -crfun} parameter. If {\em -agglocrfun} is not specified, 
       then for the partitional clustering methods it uses the same criterion 
       function as that used to find the clusters, for the agglomerative methods 
       it uses UPGMA, and for the graph-partitioning-based clustering methods, 
       it uses the ``wslink'' criterion function.


  \item[\mbox{\makebox[6.5in]{-cstype=string \hfill \vcluster \& \scluster}}]
       This parameter selects the method that is used to select the cluster
       to be bisected next when {\em -clmethod} is equal to ``rb'', ``rbr'', 
       or ``graph''. The possible values are:
       \begin{Ventry}{largexxx}{\bf}
         \item[large]   Selects the largest cluster to be bisected next.
         \item[best]    Selects the cluster whose bisection will optimize the
                        value of the overall clustering criterion function the
                        most. This is the default option.
                       
                        Note that in the case of graph-partitioning based clustering, 
                        the overall criterion function is evaluated in terms of the 
                        ratio cut, as to prevent (up to a point) the creation of 
                        very small clusters. However, this method is not 100\% 
                        robust, so if you notice that in your dataset you are 
                        getting a clustering solution that contains very large 
                        and very small clusters, you should use ``large'' 
                        instead.
         \item[largess] Selects the cluster that will lead to the larger reduction
                        on the number of dimensions of the feature-space that account
                        for the majority of the within-cluster similarity of the 
                        objects. This reduction in the {\em subspace-size} is weighted
                        by the size of each cluster, as well. This method is applicable
                        only to \vcluster, and it should be used mostly with sparse
                        and high dimensional datasets.
       \end{Ventry}


  \item[\mbox{\makebox[6.5in]{-fulltree \hfill \vcluster \& \scluster}}]
       Builds a complete hierarchical tree that preserves the clustering solution 
       that was computed. In this hierarchical clustering solution, the objects of 
       each cluster form a subtree, and the different subtrees are merged to get 
       an all inclusive cluster at the end. The hierarchical agglomerative clustering 
       is computed so that it optimizes the selected clustering criterion function
       (specified by {\em -agglocrfun}). This option should be used to obtain a hierarchical 
       agglomerative clustering solution for very large data sets, and for re-ordering 
       the rows of the matrix when {\em -plotmatrix} is specified. Note that this
       option can only be used with the ``rb'', ``rbr'', and ``direct'' clustering
       methods.


  \item[\mbox{\makebox[6.5in]{-rowmodel=string \hfill \vcluster}}]
       Selects the model to be used to scale the various columns of each row. 
       The possible values are:
       \begin{Ventry}{MAXTF}{\bf}
         \item[none]  The columns of each row are not scaled and used as they are provided
                      in the input file. This is the default setting.

         \item[maxtf] The columns of each row are scaled so that their values are between 
                      0.5 and 1.0. In particular, the $j$th column of the $i$th row of
                      the matrix ($r_{i,j}$) is scaled to be equal to
                      \[
                        r'_{i,j} = 0.5 + 0.5\frac{r_{i,j}}{max_l (r_{i,l})}.
                      \]
                      This scaling was motivated by a similar scaling of document vectors in
                      information retrieval, and it is referred to as the {\em MAXTF} scaling 
                      scheme.

         \item[sqrt]  The columns of each row are scaled to be equal to the square-root of
                      their actual values. That is, $r'_{i,j} = \sign(r_{i,j}) \sqrt{|r_{i,j}|}$,
                      where $\sign(r_{i,j})$ is 1.0 or -1.0, depending on whether or not
                      $r_{i,j}$ is positive or negative. This scaling is referred to as 
                      the {\em SQRT} scaling scheme. 
         \item[log]   The columns of each row are scaled to be equal to the log of their 
                      actual values. That is, $r'_{i,j} = \sign(r_{i,j}) \log_2{|r_{i,j}|}$.
                      This scaling is referred to as the {\em LOG} scaling scheme.
       \end{Ventry}

       The last three scaling schemes are primarily used to smooth large values in 
       certain columns (\ie., dimensions) of each vector.


  \item[\mbox{\makebox[6.5in]{-colmodel=string \hfill \vcluster}}]
       Selects the model to be used to scale the various columns globally across all the 
       rows. The possible values are:
       \begin{Ventry}{NONE}{\bf}
         \item[none]  The columns of the matrix are not globally scaled, and they are 
                      used as is. This is the default setting used by \vcluster when 
                      the correlation coefficient-based similarity function is used.
         \item[idf]   The columns of the matrix are scaled according to the 
                      {\em inverse-document-frequency} (IDF) paradigm, used in information
                      retrieval. In particular, if $\mbox{\em rf}_i$ is the number of rows
                      that the $i$th column belongs to, then each entry of the $i$th column
                      is scaled by $-\log_2(\mbox{\em rf}_i/n)$. The effect of this scaling 
                      is to de-emphasize columns that appear in many rows.
                      This is the default setting used by \vcluster when the cosine
                      similarity function is used.
       \end{Ventry}

       The global scaling of the columns occurs after the per-row column scaling selected
       by the {\em -rowmodel} parameter has been performed.

       The choice of the options for both {\em -rowmodel} and {\em -colmodel} were
       motivated by the clustering requirements of high-dimensional datasets arising 
       in document and commercial datasets. However, for other domains the provided
       options may not be sufficient. In such domains, the data should be pre-processed
       to apply the desired row/column model before supplying them to \cluto. In that
       case {\em -rowmodel=none} and {\em -colmodel=none} should probably be used.


  \item[\mbox{\makebox[6.5in]{-colprune=float \hfill \vcluster}}]
        Selects the factor by which \vcluster will prune the columns before performing
        the clustering. This is a number $p$ between 0.0 and 1.0 and indicates the
        fraction of the overall similarity that the retained columns must account for.
        For example, if $p=0.9$, \vcluster first determines how much each column
        contributes to the overall pairwise similarity between the rows, and then 
        selects as many of the highest contributing columns as required to account 
        for 90\% of the similarity. Reasonable values are within the range of 
        $(0.8 \cdots 1.0)$, and the default value used by \vcluster is 1.0, indicating 
        that no columns will be pruned. In general, this parameter leads to a substantial 
        reduction of the number of columns (\ie., dimensions) without seriously affecting 
        the overall clustering quality.
        

  \item[\mbox{\makebox[6.5in]{-nnbrs=int \hfill \vcluster \& \scluster}}]
        This parameter specifies the number of nearest neighbors of each object 
        that will be used in creating the nearest neighbor graph that is used by the 
        graph-partitioning based clustering algorithm. The exact approach of
        combining these nearest-neighbors to create the graph is controlled
        by the {\em -grmodel} parameter. The default value for this parameter
        is set to 40.


  \item[\mbox{\makebox[6.5in]{-grmodel=string \hfill \vcluster \& \scluster}}]
        This parameter controls the type of nearest-neighbor graph that will be 
        constructed on the fly and supplied to the graph-partitioning based 
        clustering algorithm. The possible values are:
       \begin{Ventry}{NONE}{\bf}
         \item[sd]    {\em Symmetric-Direct}\\
                      A graph is constructed so that there will be an edge between
                      two objects $u$ and $v$ if and only if both of them are in the
                      nearest-neighbor lists of each other. That is, $v$ is one of the
                      {\em nnbr}s of $u$ and vice versa. The weight of this edge is
                      set equal to the similarity of the objects (or inversely related
                      to their distance). This is the default option used by both 
                      \vcluster and \scluster.

         \item[ad]    {\em Asymmetric-Direct}\\
                      A graph is constructed so that there will be an edge between
                      two objects $u$ and $v$ as long as one of them is in the 
                      nearest-neighbor lists of the other. That is, $v$ is one of the
                      {\em nnbr}s of $u$ and/or $u$ is one of the {\em nnbr}s of $v$.
                      The weight of this edge is set equal to the similarity of the 
                      objects (or inversely related to their distance). 
                      
         \item[sl]    {\em Symmetric-Link}\\
                      A graph is constructed that has exactly the same adjacency 
                      structure as that of the ``sd'' option. However, the weight 
                      of each edge $(u, v)$ is set equal to the number of vertices 
                      that are in common in the adjacency lists of $u$ and $v$ (\ie.,
                      is equal to the number of shared nearest neighbors). We will
                      refer to this as the {\em link}$(u, v)$ count between $u$ and 
                      $v$. This option was motivated by the {\em link} graph used by 
                      the CURE clustering algorithm \cite{guha98}.

         \item[al]    {\em Asymmetric-Link}\\
                      A graph is constructed that has exactly the same adjacency 
                      structure as that of the ``ad'' option. However, the weight 
                      of each edge $(u, v)$ is set in a fashion similar to ``sl''.

         \item[none]  This option is used only by \scluster and indicates that the
                      input graph will be used as is.
       \end{Ventry}


  \item[\mbox{\makebox[6.5in]{-edgeprune=float \hfill \vcluster \& \scluster}}]
       This parameter can be used to eliminate certain edges from the nearest-neighbor
       graph that will tend to connect vertices belonging to different clusters. 
       In particular, if $x$ is the supplied parameter, then an edge $(u, v)$ will 
       be eliminated if and only if 
       \[
         \mbox{\em link}(u, v) < x*\mbox{\em nnbrs},
       \]
       where {\em link}$(u, v)$ is as defined in {\em -grmodel=sl}, and {\em nnbrs} 
       is the number of nearest neighbors used in creating the graph.

       The basic motivation behind this pruning method is that if two vertices
       are part of the same cluster they should be part of a well-connected 
       subgraph (\ie., be part of a sufficiently large clique-like subgraph). 
       Consequently, their adjacency lists must have many common vertices. 
       If that does not happen, then that edge may have been created because
       these objects matched in non-relevant aspects of their feature vectors,
       or it may be an edge {\em bridging} separate clusters. In either case,
       it can potentially be eliminated.

       The default value of this parameter is set to -1, indicating no edge-pruning.
       Reasonable values for this parameter are within $[0.0, 0.5]$ when {\em -grmodel}
       is `sd' or `sl', and $[1.0, 1.5]$ when {\em -grmodel} is `ad' or `al'.

       Note that this parameter is used only by the graph-partitioning based clustering
       algorithm.
       

  \item[\mbox{\makebox[6.5in]{-vtxprune=float \hfill \vcluster \& \scluster}}]
       This parameter is used to eliminate certain vertices from the nearest-neighbor
       graph that tend to be outliers. In particular, if $x$ is the supplied parameter, 
       then a vertex $u$ will be eliminated if its degree is less than $x*\mbox{\em nnbrs}$.
       The key idea behind this method, especially when the {\em symmetric} graph 
       models are used, is that if a particular vertex $u$ is not in the the 
       nearest-neighbor list of its nearest-neighbors, then it will most likely be an
       outlier.
       
       The default value of this parameter is set to -1, indicating no vertex-pruning. 
       Reasonable values for this parameter are within $[0.0, 0.5]$ when {\em -grmodel}
       is `sd' or `sl', and $[1.0, 1.5]$ when {\em -grmodel} is `ad' or `al'.
       Note that by using relatively large values for {\em -edgeprune} and {\em -vtxprune} 
       you can obtain a graph that contains many small connected components. 
       Such components often correspond to tight clusters in the dataset. This is 
       illustrated in \figref{fig:components}. Note that the clustering solution 
       in this example has 48 connected components larger than five vertices, containing 
       only 1345 out of the 8580 objects (please refer to \secref{sec:usage:vcluster:stats} 
       to find out how to interpret these results).

\begin{figure}[htbp]
\centerline{\input{./examples/example3.tex}}
\caption{Output of \vcluster for matrix {\em sports.mat\/} using 0.4 for edge- and vertex-prune.}
\label{fig:components}
\end{figure}

       The vertex-pruning is applied after the edge-pruning has been done.

       Note that this parameter is used only by the graph-partitioning based clustering
       algorithm.


  \item[\mbox{\makebox[6.5in]{-mincomponent=int \hfill \vcluster \& \scluster}}]
       This parameter is used to eliminate small connected components from the
       nearest-neighbor graph prior to clustering. In general, if the edge- and 
       vertex-pruning options are used, the resulting graph may have a large
       number of small connect components (in addition to larger ones). 
       By eliminating (\ie., not clustering) the smaller components eliminates
       some of the clutter in the resulting clustering solution, and it removes
       some additional outliers. The default value for this parameter is set to 
       five.

       Note that this parameter is used only by the graph-partitioning based clustering
       algorithm.

  \item[\mbox{\makebox[6.5in]{-ntrials=int \hfill \vcluster \& \scluster}}]
        Selects the number of different clustering solutions to be computed by the
        various partitional algorithms. If $l$ is the supplied number, then 
        \vcluster and \scluster computes a total of $l$ clustering solutions
        (each one of them starting with a different set of seed objects), and 
        then selects the solution that has the best value of the criterion 
        function that was used. The default value for \vcluster is 10.


  \item[\mbox{\makebox[6.5in]{-niter=int \hfill \vcluster \& \scluster}}]
        Selects the maximum number of refinement iterations to be performed, 
        within each clustering step. Reasonable values for this parameter are 
        usually in the range of 5--20. This parameter applies only to the
        partitional clustering algorithms. The default value is set to 10. 


  \item[\mbox{\makebox[6.5in]{-seed=int \hfill \vcluster \& \scluster}}]
        Selects the seed of the random number generator to be used by \vcluster
        and \scluster.

\end{Lentry}





%=========================================================================
\subsubsection{Reporting and Analysis Parameters}
\label{sec:usage:vcluster:reportparams}

There are a total of 14 different optional parameters that control the amount 
of information that \vcluster and \scluster report about the clusters, as well 
as, the analysis that they perform on the discovered clusters. The name and 
function of these parameters is as follows:


\begin{Lentry}
  \item[\mbox{\makebox[6.5in]{-nooutput  \hfill \vcluster \& \scluster}}]
     Specifies that \vcluster and \scluster should not write the clustering 
     vector and/or agglomerative trees onto the disk.


  \item[\mbox{\makebox[6.5in]{-clustfile=string  \hfill \vcluster \& \scluster}}]
     Specifies the name of the file onto which the clustering vector should be 
     written. The format of this file is described in \secref{sec:usage:oformat:clustering}
     If this parameter is not specified, then the clustering vector is written 
     to the {\em MatrixFile.clustering.NClusters\/} ({\em GraphFile.clustering.NClusters\/}) 
     file, where {\em MatrixFile} ({\em GraphFile}) is the name of the file that 
     stores the matrix (graph) to be clustered, and {\em NClusters} is the number 
     of desired clusters.
     

  \item[\mbox{\makebox[6.5in]{-treefile=string  \hfill \vcluster \& \scluster}}]
     Specifies the name of the file onto which the hierarchical agglomerative
     tree should be written. This tree is created either when {\em -clmethod=agglo},
     or when {\em -fulltree} was specified. The format of this file is described 
     in \secref{sec:usage:oformat:tree}. By default, the tree is written in the 
     file {\em MatrixFile.tree} ({\em GraphFile.tree}), where {\em MatrixFile} 
     ({\em GraphFile}) is the name of the file storing the input matrix (graph).


  \item[\mbox{\makebox[6.5in]{-cltreefile=string  \hfill \vcluster \& \scluster}}]
     Specifies the name of the file onto which the hierarchical agglomerative
     tree build on top of the clustering solution should be written. This tree 
     is created either when {\em -showtree}, was specified. The format of this 
     file is described in \secref{sec:usage:oformat:tree}. By default, the tree 
     is written in the file {\em MatrixFile.cltree.NClusters} ({\em
     GraphFile.cltree.NClusters}) , where {\em MatrixFile} ({\em GraphFile})
     is the name of the file storing the input matrix (graph), and {\em NClusters} 
     is the number of desired clusters.


  \item[\mbox{\makebox[6.5in]{-clabelfile=string  \hfill \vcluster}}]
     Specifies the name of the file that stores the labels of the columns. 
     The labels of the columns are used for reporting purposes when the 
     {\em -showfeatures}, {\em -showsummaries}, or the {\em -labeltree} 
     options are specified. The format of this file is described in 
     \secref{sec:usage:iformat:clabel}. If this parameter is not specified, 
     \vcluster looks to see if a file called {\em MatrixFile.clabel} exists, 
     and if it does, reads this file, instead. If no file is provided or 
     the default file does not exist, then the label of the $j$th column 
     becomes ``colj'' (\ie., it is labeled by its corresponding column-id).


  \item[\mbox{\makebox[6.5in]{-rlabelfile=string  \hfill \vcluster \& \scluster}}]
     Specifies the name of the file that stores the labels of the rows (vertices). 
     The labels of the rows (vertices) are used for reporting purposes when the 
     {\em -plotmatrix} or the {\em -plotsmatrix} options are specified.
     The format of this file is described in \secref{sec:usage:iformat:rlabel}. 
     If this parameter is not specified, \vcluster (\scluster) looks to see if 
     a file called {\em MatrixFile.rlabel} ({\em GraphFile.rlabel}) exists, 
     and if it does, reads this file, instead. If no file is provided or the 
     default file does not exist, then the label of the $j$th row or vertex 
     becomes ``rowj'' (\ie., it is labeled by its corresponding row-id).


  \item[\mbox{\makebox[6.5in]{-rclassfile=string  \hfill \vcluster \& \scluster}}]
     Specifies the name of the file that stores the class-labels of the rows
     (vertices) (\ie., the objects to be clustered). This is used by \vcluster 
     (\scluster) to compute the quality of the clustering solution using external 
     quality measures and to output how the objects of different classes are 
     distributed among clusters. The format of this file is described in 
     \secref{sec:usage:iformat:rclass}. If this parameter is not specified, 
     \vcluster (\scluster) looks to see if a file called {\be MatrixFile.rlabel} 
     ({\em GraphFile.rlabel}) exists, and if it does, reads this file, instead. 
     If no file is provided or the default file does not exist, \vcluster and \scluster 
     assume that the class labels of the objects are not known and do not perform 
     any cluster-quality analysis based on external measures.


  \item[\mbox{\makebox[6.5in]{-showfeatures \hfill \vcluster}}]
     This parameter instructs \vcluster to analyze the discovered clusters and 
     identify the set of features (\ie., columns of the matrix) that are most 
     descriptive of each cluster and the set of features that best 
     discriminate each cluster from the rest of the objects. The set of 
     {\em descriptive} features is determined by selecting the columns that 
     contribute the most to the average similarity between the objects of each 
     cluster. On the other hand, the set of {\em discriminating} features is 
     determined by selecting the columns that are more prevalent in the cluster 
     compared to the rest of the objects. In general, there will be a large 
     overlap between the descriptive and discriminating features. However, in 
     some cases there may be certain differences, especially when {\em -colmodel=none}.
     This analysis can only be performed when the similarity between objects is
     computed using the cosine or correlation coefficient.

  \item[\mbox{\makebox[6.5in]{-showsummaries=string \hfill \vcluster}}]
     This parameter instructs \vcluster to analyze the discovered clusters and 
     identify relations among the set of most descriptive features of each cluster.
     The key motivation behind this option is that some of the discovered clusters 
     may contain within them smaller sub-clusters. As a result, by simply looking
     at the output of {\em -showfeatures} it may be hard to identify which features 
     go together in these sub-clusters (if they exist). To overcome this problem, 
     {\em -showsummaries} analyzes the most descriptive features of each cluster 
     and finds subsets of these features that tend to occur together in the objects.
     
     \cluto provides two different methods for determining which features ``go together''.
     These methods are selected by providing the appropriate method-name as an option
     for this parameter. The possible values are:
       \begin{Ventry}{itemsetsxxx}{\bf}
         \item[cliques]   Represents the most descriptive features via a graph in which
                          to features are connected via an edge if and only if their 
                          co-occurrence frequency within the cluster is greater than 
                          their expected co-occurrence. Now given this graph, \cluto 
                          decomposes it into maximal cliques, and uses these cliques
                          as the summaries.

         \item[itemsets]  It mines the objects of each cluster and identifies: (i) maximal
                          frequent itemsets, and (ii) non-maximal itemsets whose support
                          is much higher than that of its maximal supersets.
                          These itemsets are returned as the summaries.
         
       \end{Ventry}


  \item[\mbox{\makebox[6.5in]{-nfeatures=int \hfill \vcluster}}]
     Specifies the number of descriptive and discriminating features to display
     for each cluster when the \mbox{\hspace{1cm}} {\em \mbox{-showfeatures}} 
     or {\em -labeltree} options are used. The default value for this parameter 
     is five (5).


  \item[\mbox{\makebox[6.5in]{-showtree \hfill \vcluster \& \scluster}}]
     This parameter instructs \vcluster and \scluster to build and display
     a hierarchical agglomerative tree on top of the clustering solution that 
     was obtained. This tree will have {\em NClusters} leaves, each one 
     corresponding to one of the discovered clusters, and provides a way 
     of visualizing how the different clusters are related to each other. 
     The criterion function used in building this tree is controlled by 
     the {\em -agglocrfun} parameter. If this parameter is not specified 
     then the criterion function used to build the clustering solution 
     is used for all method except {\em -clmethod=graph}, for which
     the {\em wslink} is used.


  \item[\mbox{\makebox[6.5in]{-labeltree \hfill \vcluster \& \scluster}}]
     This parameter instructs \vcluster and \scluster to label the nodes of 
     the tree with the set of features that best describe the corresponding 
     clusters. The method used for determining these features is identical 
     to that used in {\em -showfeatures}. Note that the descriptive features 
     for both the leaves (\ie., original clusters), as well as, the internal 
     nodes of the tree are displayed. The number of features that is displayed 
     is controlled by the {\em -nfeatures} parameter.
     This analysis can only be performed when the similarity between objects is
     computed using the cosine or correlation coefficient.


  \item[\mbox{\makebox[6.5in]{-zscores \hfill \vcluster \& \scluster}}]
     This parameter instructs \vcluster and \scluster to analyze each cluster 
     and for each object to output the $z$-score of its similarity to the 
     other objects in its own cluster (internal $z$-score), as well as, the 
     objects of the different clusters (external $z$-score). The various 
     $z$-score values are stored in the clustering file whose format 
     is described in \secref{sec:usage:oformat:clustering}.
     
     The internal $z$-score of an object $j$ that is part of the $l$th cluster is 
     given by $(s^I_j - \mu^I_l)/\sigma^I_l$, where $s^I_j$ is the average similarity 
     between the $j$th object and the rest of the objects in its cluster, $\mu^I_l$ 
     is the average of the various $s^I_j$ values over all the objects in the $l$th,
     and $\sigma^I_l$ is the standard deviation of these similarities.
     
     The external $z$-score of an object $j$ that is part of the $l$th cluster 
     is given by $(s^E_j - \mu^E_l)/\sigma^E_l$, where $s^E_j$ is the average 
     similarity between the $j$th object and the objects in the other clusters, 
     $\mu^E_l$ is the average of the various $s^E_j$ values over all the objects 
     in the $l$th cluster, and $\sigma^E_l$ is the standard deviation of these 
     similarities.
       
     Objects that have large values of the internal $z$-score and small values
     of the external $z$-score will tend to form the {\em core} of their clusters.
     

  \item[\mbox{\makebox[6.5in]{-help \hfill \vcluster \& \scluster}}]
     This options instructs \vcluster to print a short description of the
     various command line parameters.

\end{Lentry}



%=========================================================================
\subsubsection{Cluster Visualization Parameters}
\label{sec:usage:vcluster:visparams}

The \vcluster and \scluster clustering programs can also produce visualizations 
of the computed clustering solutions. These visualizations are relatively simple
plots of the original input matrix that show how the different objects (\ie.,
rows) and features (\ie., columns) are clustered together. 

There are a total of nine optional parameters that control the type of visualization 
that \vcluster performs. The name and function of these parameters is as follows:


\begin{Lentry}
  \item[\mbox{\makebox[6.5in]{-plotformat=string \hfill \vcluster \& \scluster}}]
     Selects the format of the graphics files produced by the visualizations.
     The possible values for this option are:
     \begin{Ventry}{XXXX}{\bf}
       \item[ps]  Outputs an encapsulated postscript\footnote{Sometimes, while
                  trying to convert the postscript files generated by \cluto 
                  into PDF format using Adobe's distiller you may notice that 
                  the text is not included in the PDF file. To correct this
                  problem reconfigure your distiller not to include {\em truetype}
                  fonts when the required text font is part of the standard
                  postscript fonts.} file. This is the default option. 
       \item[fig] Outputs the visualization in a format that is compatible with
                  the Unix XFig program. This file can then be edited with XFig.
       \item[ai]  Outputs the visualization in a format that is compatible with
                  the Adobe Illustrator program. This file can then be edited 
                  with Illustrator or other programs that understand this format
                  (\eg., Visio).
       \item[svg] Outputs the visualization in the XML-based Scalable Vector 
                  Format that can be viewed by modern web-browsers (if the 
                  appropriate plug-in is installed).
       \item[cgm] Outputs the visualization in the WebCGM format.
       \item[pcl] Outputs the visualization in HP's PCL~5 format used by many
                  laserjet or compatible printers.
       \item[gif] Outputs the visualization in widely used GIF bitmap format.
     \end{Ventry}

  \item[\mbox{\makebox[6.5in]{-plottree=string \hfill \vcluster \& \scluster}}]
     Produces a graphic representation of the entire hierarchical tree produced 
     when {\em -clmethod=agglo} or when the {\em -fulltree} option was specified.  
     The leaves of this tree are labeled based on the supplied row labels 
     (\ie., via the {\em -rlabelfile} parameter). 


  \item[\mbox{\makebox[6.5in]{-plotmatrix=string \hfill \vcluster}}]
     Produces a visualization that shows how the rows of the original matrix 
     are clustered together. This is done by showing an appropriate row- 
     and possibly a column-permutation of the original matrix, along with 
     a color-intensity plot of the various values of the matrix. The actual 
     visualization is stored in the file whose name is supplied as an 
     option to {\em -plotmatrix}.
     
     In this matrix permutation, the rows of the matrix assigned to the same 
     cluster are re-ordered to be at consecutive rows, followed by a reordering
     of the clusters. The actual ordering of the rows and clusters depends
     on whether the {\em -fulltree} parameter was specified. If it was not
     specified, then the clusters are ordered according to their cluster-id
     number, and within each cluster the rows are numbered according to the
     row-id number. However, if {\em -fulltree} was specified, both the rows
     and the clusters are re-ordered according the hierarchical tree computed
     by {\em -fulltree}. In addition to that, the actual tree is drawn along the
     side of the matrix.
     
     If the input matrix is in dense format, then {\em -plotmatrix} displays 
     the columns, in column-id order. If the {\em -clustercolumns} option 
     was specified, then the columns are re-ordered according to a hierarchical
     clustering solution of the columns.

     If the matrix is sparse, only a subset of the columns is displayed, that
     corresponds to the union of the descriptive and discriminating features 
     of each cluster computed by {\em -showfeatures}. The number of features 
     from each cluster that is included in that union can be controlled by the
     {\em -nfeatures} parameter. Again, the columns can be displayed in either
     the column-id order or if the {\em -clustercolumns} option was specified, 
     then the columns are re-ordered according to a hierarchical clustering 
     solution of the columns.

     The labels printed along each row and column of the matrix can be specified
     by using the {\em -rlabelfile} and {\em -clabelfile}, respectively.

     The plot uses red to denote positive values and green to denote negative
     values. Bright red/green indicate large positive/negative values, whereas
     colors close to white indicate values close to zero.
      
       
  \item[\mbox{\makebox[6.5in]{-plotsmatrix=string \hfill \vcluster \& \scluster}}]
     This visualization is similar to that produced by {\em -plotmatrix} but was
     designed to visualize the similarity graph. In this plot, both the rows
     and columns of the displayed visualization correspond to the vertices of
     the graph.


  \item[\mbox{\makebox[6.5in]{-plotclusters=string \hfill \vcluster}}]
     Produces a visualization that shows how the clusters are related to each
     other, by showing a color-intensity plot of the various values in the various 
     cluster centroid vectors. The actual visualization is stored in the file 
     whose name is supplied as an option to {\em -plotclusters}.

     The produced visualization is similar to that produced by {\em -plotmatrix},
     but now only {\em NClusters} rows are shown, one for each cluster. The
     height of each row is proportional to the log of the corresponding cluster's
     size. The ordering of the clusters is determined by computing a hierarchical 
     clustering (similar to that produced via {\em -showtree}), and the ordering 
     of the columns is controlled by the {\em -clustercolumns} parameter. 

     The column selection mechanism and color-scheme are identical to that used 
     by {\em -plotmatrix}.

     
  \item[\mbox{\makebox[6.5in]{-plotsclusters=string \hfill \vcluster \& \scluster}}]
     This visualization is similar to that produced by {\em -plotclusters} but was
     designed to visualize the similarity between the clusters. In this plot, both 
     the rows and columns of the displayed visualization correspond to the graph 
     clusters.


  \item[\mbox{\makebox[6.5in]{-clustercolumns \hfill \vcluster}}]
     Instructs \vcluster to compute a hierarchical clustering of the columns
     and to reorder them when {\em -plotmatrix} and {\em -plotclusters} is 
     specified. This can be used to generate a visualization in which the 
     features are clustered together.


  \item[\mbox{\makebox[6.5in]{-noreorder \hfill \vcluster \& \scluster}}]
     Instructs \vcluster and \scluster not to try to produce a visually 
     pleasing reordering of the various hierarchical trees that is drawing. 
     This option is turned off by default if the number of objects that 
     are clustered is greater than 4000.
     
  \item[\mbox{\makebox[6.5in]{-zeroblack \hfill \vcluster \& \scluster}}]
     Instructs \vcluster and \scluster to use black color for denoting zero 
     (or small values) in the matrix.

\end{Lentry}






%=========================================================================
\subsection{Understanding the Information Produced by \cluto's Clustering Programs}
\label{sec:usage:vcluster:stats}

>From the description of \vcluster's and \scluster's parameters we can see 
that they can output a wide-range of information and statistics about the 
clusters that they find. In the rest of this section we describe the format 
and meaning of these statistics. Most of our discussion will focus on 
\vcluster's output, since it is similar to that produced by \scluster.


%-------------------------------------------------------------------------
\subsubsection{Internal Cluster Quality Statistics}

The simpler statistics reported by \vcluster \& \scluster have to do with 
the quality of each cluster as measured by the criterion function that it uses 
and the similarity between the objects in each cluster. In particular, as the 
example in \figref{fig:sample-vcluster} shows, the ``{\em Solution}'' section of 
\vcluster's output displays information about the clustering solution.

The first statistic that it reports is the overall value of the criterion
function for the computed clustering solution. In our example, this is reported 
as ``{\tt I2=2.29e+03}'', which is the value of the \itwo criterion function
of the resulting solution. If a different criterion function is specified
(by using the {\em -crfun} option), then the overall cluster quality information
will be displayed with respect to that criterion function. In the same line,
both programs also display how many of the original objects they were able
to cluster (\ie., ``{\tt [8204 of 8204]}''). In general, both \vcluster
and \scluster try to cluster all objects. However, when some of the objects 
(vertices) do not share any dimensions (edges) with the rest of the objects,
or when the various edge- and vertex-pruning parameters are used, both
programs may end up clustering fewer than the total number of input
objects.

After that, \vcluster then displays a table in which each row contains various 
statistics for each one of the clusters. The meaning of the columns 
of this table is as follows. The column labeled ``cid'' corresponds to the 
cluster number (or cluster id). The column labeled ``Size'' displays the 
number of objects that belongs to each cluster. The column labeled ``ISim''
displays the average similarity between the objects of each cluster (\ie.,
internal similarities). The column labeled ``ISdev'' displays the standard 
deviation of these average internal similarities (\ie., internal standard
deviations). The column labeled ``ESim'' displays the average similarity 
of the objects of each cluster and the rest of the objects (\ie., external
similarities). Finally, the column labeled ``ESdev'' display the standard
deviation of the external similarities (\ie., external standard deviations).

Note that the discovered clusters are ordered in increasing (ISIM-ESIM) order. 
In other words, clusters that are {\em tight} and far away from the rest 
of the objects have smaller cid values.



%-------------------------------------------------------------------------
\subsubsection{External Cluster Quality Statistics}

In addition to the internal cluster quality measures, \vcluster \& 
\scluster can also take into account information about the classes that the 
various objects belong to (via the {\em -rclassfile} option) and compute 
various statistics that determine the quality of the clusters using that 
information. These statistics are usually referred to as {\em external 
quality measures} as the quality is determined by looking at information 
that was not used while finding the clustering solution.

\figref{fig:vcluster-rclass} shows the output of \vcluster when such a 
class file is provided for our example {\em sports.mat} dataset. This dataset
contains various documents that talk about seven different sports (baseball,
basketball, football, hockey, boxing, bicycling, and golfing), and each
document (\ie., object to be clustered) belongs to one of these topics.
Once \vcluster finds the 10-way clustering solution, it then uses this
class information to analyze both the quality of the overall clustering 
solution as well as the quality of each cluster. 

\begin{figure}[htb]
\centerline{\input{./examples/example4.tex}}
\caption{Output of \vcluster for matrix {\em sports.mat\/} and a 10-way clustering 
         that uses external quality measures.}
\label{fig:vcluster-rclass}
\end{figure}


Looking at \figref{fig:vcluster-rclass} we can see that \vcluster, in addition
to the overall value of the criterion function, now prints the {\be entropy}
and the {\be purity} of the clustering solution. For the exact formula of how
the entropy and purity of the clustering solution is computed, please refer to
\cite{zhao01tr-vpcluster}. Small entropy values and large purity values indicate 
good clustering solutions. 

In addition to these measures, the cluster information table now contains two 
additional sets of information. The first set is the entropy and purity of each 
cluster and is displayed in the columns labeled ``Entpy'' and ``Purty'', respectively. 
The second set is information about how the different classes are distributed in 
each one of the clusters.  
This information is displayed in the last seven columns of this table, whose
column labels are derived from the first four characters if the class names.
That is ``base'' corresponds to baseball, ``bask'' corresponds to basketball, 
and so on. Each column shows the number of documents of this class that are 
in each cluster. For example, the first cluster contains 360 documents about 
basketball, and two documents about football. Looking at this class-distribution 
table, we can easily determine the quality of the different clusters.




%-------------------------------------------------------------------------
\subsubsection{Looking at each Cluster's Features}

By specifying the {\em -showfeatures} option, \vcluster will analyze 
each one of the clusters and determine the set of features (\ie., columns 
of the matrix) that best describe and discriminate each one of the clusters. 
\figref{fig:vcluster-features} shows the output produced by \vcluster 
when {\em -showfeatures} was specified and when a file was provided with the 
labels of each one of the columns (via the {\em -clabelfile} option).

Looking at this figure, we can see that the set of descriptive and discriminating 
features are displayed right after the table that provides statistics for the 
various clusters. For each cluster, \vcluster displays three lines of
information. The first line contains some basic statistics for each cluster 
(\eg., cid, Size, ISim, ESim), whose meaning is identical to those displayed 
in the earlier table. The second line contains the five most descriptive
features, whereas the third line contains the five most discriminating 
features. The features in these lists are sorted in decreasing descriptive or 
discriminating order. The reason that five features are printed is because this
is the default value for the {\em -nfeatures} parameter; fewer or more
features can be displayed by setting this parameter appropriately.


\begin{figure}[htbp]
\centerline{\input{./examples/example5.tex}}
\caption{Output of \vcluster for matrix {\em sports.mat\/} and a 10-way clustering 
         that shows the descriptive and discriminating features of each cluster.}
\label{fig:vcluster-features}
\end{figure}

Right next to each feature, \vcluster displays a number that in the case of the
descriptive features is the percentage of the within cluster similarity that this 
particular feature can explain. For example, for the 0th cluster, the feature 
``warrior'' explains 38.4\% of the average similarity between the objects of the 
0th cluster. A similar quantity is displayed for each one of the discriminating 
features, and is the percentage of the dissimilarity between the cluster and the 
rest of the objects which this feature can explain. In general there is a large 
overlap between descriptive and discriminating features, with the only difference 
being that the percentages associated with the discriminating features are
typically smaller than the corresponding percentages of the descriptive features. 
This is because some of the descriptive features of a cluster may also be present 
in a small fraction of the objects that do not belong to this cluster.

If no labels for the different columns are provided, \vcluster outputs the 
column number of each feature instead of its label. This is illustrated in 
\figref{fig:vcluster-featuresa} for the same problem in which {\em -clabelfile}
was not specified. Note that the columns are numbered from one.


\begin{figure}[htbp]
\centerline{\input{./examples/example6.tex}}
\caption{Output of \vcluster for matrix {\em sports.mat\/} and a 10-way clustering 
         that shows the descriptive and discriminating features of each cluster.}
\label{fig:vcluster-featuresa}
\end{figure}


By specifying the {\em -showsummaries} option, \vcluster will further analyze 
the most descriptive features of each cluster and try to identify the set of
features that co-occur in the objects. \figref{fig:showsummaries} shows the 
output produced by \vcluster when {\em -showsummaries=cliques} was specified 
and when a file was provided with the labels of each one of the columns 
(via the {\em -clabelfile} option). Note that some clusters contain only 
a single summary; however, many clusters have more than one summary associated
with them. In many cases there is a large overlap between the features of
the various summaries of the same cluster, but the unique features of each
summary does provide some clues on particular subsets of objects within each
cluster. 

\begin{figure}[htbp]
\centerline{\input{./examples/showsummaries-ex1.tex}}
\caption{Output of \vcluster for matrix {\em sports.mat\/} and a 10-way clustering 
         that shows the summaries using maximal cliques.}
\label{fig:showsummaries}
\end{figure}



%-------------------------------------------------------------------------
\subsubsection{Looking at the Hierarchical Agglomerative Tree}

The \vcluster \& \scluster programs can also produce a hierarchical agglomerative 
tree in which the discovered clusters form the leaf nodes of this tree. This is 
done by specifying the {\em -showtree} parameter. In constructing this tree,
the algorithms repeatedly merge a particular pair of clusters, and the pair of 
clusters to be merged is selected so that the resulting clustering solution
at that point optimizes the specified clustering criterion function.

The format of the produced tree for the {\em sports.mat} data set is shown 
in \figref{fig:vcluster-tree}. This result was obtained by specifying both 
{\em -showtree} as well as the {\em -rclassfile} parameter that provides the
class labels for each object in the matrix.


\begin{figure}[htb]
\centerline{\input{./examples/example7.tex}}
\caption{Output of \vcluster for matrix {\em sports.mat\/} that also shows the
         hierarchical tree built on top of the discovered clusters.}
\label{fig:vcluster-tree}
\end{figure}


Looking at this figure we can see that \vcluster displays the tree in a rotated
fashion, \ie., the root of the tree is at the first column, and the tree grows
from left to right. The leaves of this tree are numbered from 0 to {\em NClusters}-1,
and each one represents the corresponding cluster discovered by \vcluster. 
The internal nodes are numbered from {\em NClusters} to 2*{\em NClusters}-2,
with the root being the highest numbered node. The numbering of the internal
nodes is done so that nodes that were obtained by merging a pair of clusters at
an earlier stage of the agglomerative process have lower numbers compared to
nodes obtained at later stages. For example, in \figref{fig:vcluster-tree} the
node numbered 10 represents the first pair of clusters (9 and 7) that were
merged, the node numbered 11 represents the second pair of clusters (0 and 5)
that were merged, and so on. 

In addition to the tree itself, \vcluster also prints information about how the
objects of the various classes are distributed in each cluster. This information
is identical to that presented in the earlier table, and are replicated here to
provide a better understanding on the content of the clusters that are merged 
together. Thus, looking at the tree we can see that the subtree rooted at node
14, contains clusters that primarily contain documents about baseball, whereas
the subtree rooted at 12 primarily contain clusters whose documents are about 
football. If the {\em -rclassfile} was not specified, this information is omitted.



\begin{figure}[htb]
\centerline{\input{./examples/example8.tex}}
\caption{Output of \vcluster for matrix {\em sports.mat\/} that shows the
         hierarchical tree built on top of the discovered clusters as well 
         as the descriptive features of each cluster.}
\label{fig:vcluster-treefeatures}
\end{figure}

Besides showing the agglomerative tree, \vcluster can also analyze each of the 
clusters produced during this agglomerative process, displaying statistics 
regarding their quality and a set of descriptive features. This is done by 
specifying the {\em -labeltree} option. The output of \vcluster in this 
case is shown in \figref{fig:vcluster-treefeatures}. 

Looking at this figure we can see that in addition to the tree itself, \vcluster
prints a number of statistics for each cluster. In particular, it displays the
cluster's ``Size'' which is the number of objects in that cluster, the cluster's 
``ISim'' which is the average similarity between the objects of each cluster, 
the cluster's ``XSim'' which is the average similarity between the objects 
of each pair of clusters that are the children of the same node of the tree,
and the ``Gain'' which is the change in the value of the particular clustering
criterion function as a result of combining the two child clusters. 
For example, the cluster corresponding to node~13, contains 1473 documents, 
whose average similarity is 6.80e-02, the average similarity between the 
documents in this cluster and the documents in the cluster corresponding to 
node~10 is 3.60e-02, and as the result of this merging, the value of the
criterion function (\ie., \itwo in this example) was decreased by 8.10e+01.
Note that since in case of \itwo the goal is to maximize its value, the
fact that the gain is negative means that with respect to the criterion
function the resulting clustering solution is worse (which was expected).

Next to these statistics, it prints the set of features that best describe each
cluster. The method used to derive these features and the information that is 
displayed are identical to those used by the {\em -showfeatures} option.



%-------------------------------------------------------------------------
\subsubsection{Looking at the Visualizations}

As discussed in \secref{sec:usage:vcluster} both \vcluster and \scluster can 
produce a number of graphical visualizations showing the relation between 
the different objects, features, and clusters.  Our goal in this section is 
to provide some illustrative examples of what the various {\em -plotXXX} 
commands can do.

\figref{fig:plotmatrixsparse} shows the type of visualizations that can be
produced when {\em -plotmatrix} is specified for a sparse matrix. In particular,
\figref{fig:plotmatrixsparse}(a) shows the visualization produced by executing
the following command: 
\begin{verse}
\footnotesize
  {\tt vcluster -plotmatrix=fig1.ps tr23.mat 10}.
\end{verse}
As we can see from that plot, \vcluster shows the rows of the input matrix 
re-ordered in such a way so that the rows assigned to each one of the ten 
clusters are numbered consecutively. The columns of the displayed matrix
are selected to be the union of the {\em nfeatures} most descriptive and
discriminating features of each cluster, and are ordered according their
column-id. Also, at the top of each column, the label of each feature
is shown (if you enlarge the postscript or PDF file of the manual you will
be able to see the names of the words that these columns correspond to).
Each non-zero positive element of the matrix is displayed by a different 
shade of red. Entries that are bright red correspond to large values and
the brightness of the entries decreases as their value decrease. The values
that are plotted correspond to the values obtained after applying the
particular {\em -rowmodel} and {\em -colmodel}, and normalizing each row
to be of unit length. \figref{fig:plotmatrixsparse}(b) shows a visualization 
of the same clustering solution in which the rows and the columns are also 
re-ordered according to a hierarchical clustering solution. In particular, 
this plot was obtained by executing the following command: 
\begin{verse}
\footnotesize
  {\tt vcluster -fulltree -clustercolumns -plotmatrix=fig2.ps tr23.mat 10}.
\end{verse}
As we can see from this plot, \vcluster now re-orders the rows and the 
columns so that rows/columns that are part of the same subtree are closer 
to each other in the final output. Also, along the rows and the columns
of the displayed matrix, \vcluster draws the actual hierarchical tree
that was computed. Finally, \figref{fig:plotmatrixsparse}(c) shows a 
visualization of the 10-way clustering solution obtained by \scluster. 
In particular, this plot was obtained by executing the following command: 
\begin{verse}
\footnotesize
  {\tt vcluster -clmethod=agglo -clustercolumns -plotmatrix=fig3.ps tr23.mat 10}.
\end{verse}


\begin{figure}[p]
\centerline{\psfig{figure=./figures/fig1.eps,width=6in}}
\caption{Various visualizations generated by the {\em -plotmatrix} parameter.
         (a) Shows the clustering solution produced by \vcluster;
         (b) Shows the same clustering solution but the rows and columns have been 
             re-ordered.
         (c) Shows the clustering solution produced by \scluster.}
\label{fig:plotmatrixsparse}
\end{figure}


\figref{fig:plotmatrixdense} shows the type of visualizations that can be
produced when {\em -plotmatrix} is specified for a dense matrix, for a particular
micro-array gene expression data set. The three different visualizations were 
produced by executing the following commands, respectively:
\begin{verse}
\footnotesize
  {\tt vcluster -sim=corr -plotmatrix=fig4.ps genes1.mat 5}\\
  {\tt vcluster -sim=corr -fulltree -clustercolumns -plotmatrix=fig5.ps genes1.mat 5}\\
  {\tt vcluster -sim=corr -clmethod=agglo -clustercolumns -plotmatrix=fig6.ps genes1.mat 5}
\end{verse}
These plots are similar in nature to those produced for sparse matrices and the
only difference is that they show all the columns (and not just the union of the
descriptive and discriminating features). Also note that each row now has a label
(corresponding to the name of the particular gene) that is read by default from
the file name {\em ``genes.mat.rlabel''}. Finally, note that the plots contain 
both red and green boxes, representing positive and negative values, respectively. 
The values used to derive the colors correspond to those used internally by 
\cluto. In this particular example, since the clusters were obtained using the 
correlation coefficient, the values correspond to the mean-subtracted original 
row vectors, normalized to be of unit length.


\begin{figure}[htb]
\centerline{\psfig{figure=./figures/fig2.eps,width=5in}}
\caption{Various visualizations generated by the {\em -plotmatrix} parameter.
         (a) Shows the clustering solution produced by the ``rb'' method of \vcluster;
         (b) Shows the same clustering solution but the rows and columns have been 
             re-ordered.
         (c) Shows the clustering solution produced by the agglomerative method for \vcluster.}
\label{fig:plotmatrixdense}
\end{figure}

A similar dense-matrix visualization is shown in \figref{fig:plotmatrixdense2} 
for another micro-array gene expression data set. The different visualizations were 
produced by executing the following commands:
\begin{verse}
\footnotesize
  {\tt vcluster -clmethod=agglo -plotmatrix=fig7.ps genes2.mat 1}\\
  {\tt vcluster -clmethod=agglo -zeroblack -plotmatrix=fig8.ps genes2.mat 1}\\
\end{verse}

\begin{figure}[htb]
\centerline{\psfig{figure=./figures/fig3.eps,angle=-90,width=5in}}
\caption{Various visualizations generated by the {\em -plotmatrix} parameter.
         (a) Shows the clustering solution produced by the agglomerative method of \vcluster;
         (b) Shows the same clustering solution but the color scheme has been changed.}
\label{fig:plotmatrixdense2}
\end{figure}


\figref{fig:plotcluster} shows the type of visualization that can be produced 
when {\em -plotcluster} is specified for a sparse matrix. This plot was obtained
by executing the following command: 
\begin{verse}
\footnotesize
  {\tt vcluster -clustercolumns -plotclusters=fig9.ps tr23.mat 10}\\
  {\tt vcluster -clustercolumns -plotclusters=fig10.ps -nfeatures=10 sports.mat 20}\\
\end{verse}
This plot shows the clustering solution shown at \figref{fig:plotmatrixsparse}(b) 
by replacing the set of rows in each cluster by a single row that corresponds to 
the centroid vector of the cluster. The {\em -plotcluster} option is particularly
useful for displaying very large data sets, as the number of rows in the plot
is only equal to the number of clusters.

\begin{figure}[p]
\centerline{\psfig{figure=./figures/fig4.eps,height=8.5in}}
\caption{Various visualizations generated by the {\em -plotcluster} parameter.}
\label{fig:plotcluster}
\end{figure}


Finally, \figref{fig:plottree} shows the type of visualization that can be produced 
when {\em -plottree} is specified. This plot was obtained by executing the following 
command: 
\begin{verse}
\footnotesize
  {\tt vcluster -clmethod=agglo -plottree=fig11.ps tr23.mat 10}.
\end{verse}
This plot shows the entire hierarchical tree for the {\em tr23.mat} data set. The 
leaves of the tree are labeled with the particular row-id (or row label if
available). You can see the labels by properly magnifying the figure. 

\begin{figure}[p]
\centerline{\psfig{figure=./figures/fig11.ps,width=6in}}
\caption{Various visualizations generated by the {\em -plottree} parameter.}
\label{fig:plottree}
\end{figure}



%=========================================================================
\subsection{Input File Formats}
\label{sec:usage:iformat}

The \vcluster and \scluster programs require an input file that stores the 
objects to be clustered in a matrix or graph format, as well as, various 
optional files containing the column labels and the class labels of the 
various objects. The format of these files are described in the following 
sections.


%=========================================================================
\subsubsection{Matrix File}
\label{sec:usage:iformat:matrix}

The primary input of \cluto's \vcluster program is a matrix storing the 
objects to be clustered. Each row of this matrix represent a single object, 
and its various columns correspond to the dimensions (\ie., features) of 
the objects.  This matrix is stored in a file and is supplied to the 
various programs as one of the command line parameters. 

\cluto understands two different input matrix formats. The first format
is suitable for sparse matrices and the second format is suitable for 
storing dense matrices. Note that \cluto, automatically detects the 
format of the input file based on the first line of the file (\ie., the 
sparse matrix format has three numbers whereas the dense matrix format 
has two numbers).



%-------------------------------------------------------------------------
\paragraph{Sparse Matrix Format}

A sparse matrix $A$ with $n$ rows and $m$ columns is stored in a plain text 
file that contains $n+1$ lines. The first line contains information about the 
size of the matrix, while the remaining $n$ lines contain information for 
each row of $A$. In \cluto's sparse matrix format only the non-zero entries 
of the matrix are stored.

The first line of the matrix file contains exactly three numbers, all of which
are integers. The first integer is the number of rows in the matrix ($n$), the
second integer is the number of columns in the matrix ($m$), and the third
integer is the total number of non-zeros entries in the $n\times m$ matrix.

The remaining $n$ lines store information about the actual non-zero structure 
of the matrix. In particular, the $(i+1)$st line of the file contains information
about the non-zero entries of the $i$th row of the matrix. Since the $i$th row
corresponds to the $i$th object to be clustered, this is nothing more than the
non-zero entries of the $i$th object's feature vector. The non-zero entries 
of each row are specified as a space-separated list of pairs. Each pair contains
the column number followed by the value for that particular column (\ie., feature).
The column numbers are assumed to be integers and their corresponding values
are assumed to be floating point numbers. The meaning of the values associated
with each entry of the object's vector is problem dependent. 

Note that the columns are numbered starting from~1 (not from~0 as is often done 
in C). Furthermore, \cluto's matrix format does not require the column-pairs
(column-number --- column-value) to be sorted in any order. 

An example of \cluto's matrix format is shown in \figref{fig:matrixfile}. 
This figure shows an example $7\times 8$ matrix and its corresponding 
representation in \cluto's matrix format.

\begin{figure}[htb]
\centerline{\psfig{figure=./figures/matrixfile.eps,width=4.5in}}
\caption{Storage format of a sample matrix.}
\label{fig:matrixfile}
\end{figure}


%-------------------------------------------------------------------------
\paragraph{Dense Matrix Format}

A dense matrix $A$ with $n$ rows and $m$ columns is stored in a plain text file 
that contains $n+1$ lines. The first line stores information about the size 
of the matrix, while the remaining $n$ lines contain information for each row 
of $A$. The first line of the matrix file contains exactly two numbers, all 
of which are integers. The first integer is the number of rows in the matrix 
($n$) and the second integer is the number of columns in the matrix ($m$). 
The remaining $n$ lines store the values of the $m$ columns for each one
of the rows. In particular, each line contains exactly $m$ space-separated
floating point values, such that the $i$th value corresponds to the $i$th 
column of $A$.


%=========================================================================
\subsubsection{Graph File}
\label{sec:usage:iformat:graph}

The primary input of \cluto's \scluster program is the adjacency matrix 
of the graph that specifies the similarity between the objects to be 
clustered. Each row/column of this matrix represents a single object, 
and a value at the $(i,j)$ location of this matrix indicates the similarity
between the $i$th and the $j$th object. 

\cluto understands two different input graph formats. The first format
is suitable for sparse graphs and the second format is suitable for storing 
dense graphs (\ie., graphs whose adjacency matrix contain mostly non-zeros).
The format of these files are very similar to the corresponding formats
for matrices, and the only difference is that they now store adjacency
matrices which are square.

Note that \cluto, automatically detects the format of the input file 
based on the first line of the file (\ie., the sparse graph format has 
two numbers whereas the dense graph format has one number).



%-------------------------------------------------------------------------
\paragraph{Sparse Graph Format}

The adjacency matrix $A$ of a sparse graph with $n$ vertices is stored in 
a plain text file that contains $n+1$ lines. The first line contains 
information about the size of the graph, while the remaining $n$ lines 
contain information for each row of $A$ (\ie., adjacency structure of the 
corresponding vertex). In \cluto's sparse graph format only the non-zero 
entries of the adjacency matrix are stored.

The first line of the file contains exactly two numbers, all of which
are integers. The first integer is the number of vertices in the graph 
($n$) and the second integer is the number of edges in the graph (\ie., 
the total number of non-zeros entries in $A$).

The remaining $n$ lines store information about the actual non-zero structure 
of $A$. In particular, the $(i+1)$st line of the file contains information
about the adjacency structure of the $i$th vertex (\ie., the non-zero entries 
of the $i$th row of the adjacency matrix). 
The adjacency structure of each vertex is specified as a space-separated list 
of pairs. Each pair contains the number of the adjacent vertex followed by the 
similarity of the corresponding edge. The vertex numbers are assumed to be 
integers and their similarity values are assumed to be floating point numbers. 

Note that the vertices are numbered starting from~1 (not from~0 as is often done 
in C). Furthermore, \cluto's graph format does not require the vertex-pairs
(vertex-number --- similarity-value) to be sorted in any order. 



%-------------------------------------------------------------------------
\paragraph{Dense Graph Format}

The adjacency matrix of a dense graph with $n$ vertices is stored in a plain 
text file that contains $n+1$ lines.  The first line stores information about 
the size of the graph, while the remaining $n$ lines contain information for 
each row of the adjacency matrix. The first line of the file contains exactly 
one number, which is the number of vertices $n$ of the graph.
The remaining $n$ lines store the values of the $n$ columns of the adjacency
matrix for each one of the vertices. In particular, each line contains exactly 
$n$ space-separated floating point values, such that the $i$th value corresponds 
to the similarity to the $i$th vertex of the graph.




%=========================================================================
\subsubsection{Row Label File}
\label{sec:usage:iformat:rlabel}

As discussed in \secref{sec:usage}, when the {\em -rlabelfile} parameter
is used, \cluto's stand-alone programs read a file that stores the label 
for each one of the rows (\ie., objects ) of the matrix. The format of this 
file is as follows. If $n$ is the total number of rows in the matrix, then 
the row-label file contains exactly $n$ lines. The information stored in 
each line is treated as a string and becomes the label of the corresponding 
row of the matrix. That is, the $i$th line of this file contains the label 
of the $i$th row of the matrix.


%=========================================================================
\subsubsection{Column Label File}
\label{sec:usage:iformat:clabel}

As discussed in \secref{sec:usage:vcluster}, when the {\em -clabelfile} parameter
is used, the \vcluster program reads a file that stores the label for each one
of the columns (\ie., features) of the matrix. The format of this file is as
follows. If $m$ is the total number of columns in the matrix, then the column-label
file contains exactly $m$ lines. The information stored in each line is treated as
a string and becomes the label of the corresponding column of the matrix. That is,
the $i$th line of this file contains the label of the $i$th column of the matrix.


%=========================================================================
\subsubsection{Row Class Label File}
\label{sec:usage:iformat:rclass}

As discussed in \secref{sec:usage:vcluster}, when the {\em -rclassfile} parameter
is used, the \vcluster program reads a file that stores the class labels for
each one of the rows (\ie., objects) of the matrix. The format of this file is as
follows. If $n$ is the total number of rows in the matrix, then the class-label
file contains exactly $n$ lines. The information stored in each line is treated as
a string and becomes the class-label of the corresponding object of the matrix. 
That is, the $i$th line of this file contains the label of the $i$th row of the 
matrix. In order to ensure that a set of objects belong to the same class,
their corresponding rows in the class-label file must contain identical 
strings.




%=========================================================================
\subsection{Output File Formats}
\label{sec:usage:oformat}

\cluto's clustering programs can generate two different types of output files 
that store information about the clustering solution they have computed. 
The first file contains the clustering vector and the internal and external 
$z$-scores for each object (when the {\em -zscores} option was specified),
whereas the second file contains the entire hierarchical agglomerative tree 
(when {\em -clmethod=agglo} or when the {\em -fulltree} option was specified(,
or the agglomerative tree that was built on top of the computed clustering 
solution (when the {\em -showtree} option was specified). The format of these 
files is described in the following sections.


%=========================================================================
\subsubsection{Clustering Solution File}
\label{sec:usage:oformat:clustering}

The clustering file of a matrix with $n$ rows consists of $n$ lines with a
single number per line. The $i$th line of the file contains the cluster 
number that the $i$th object/row/vertex belongs to. Cluster numbers run 
from zero to the number of clusters minus one. 

In this case, \cluto's clustering algorithms will not be able to assign all
the objects to any of the clusters. In this case, the cluster number for 
that particular row/vertex will be set to -1. This usually happens for
two reasons. First, \cluto's \vcluster program removes all the columns 
that occur in fewer than three rows before computing the clustering solution. 
This is for performance reasons, and it does not affect the quality of the 
computed clustering solution. However, as a result of this pruning step, 
some objects may loose all of their features, in which case they will not
be clustered. Second, in the case of the graph-partitioning-based clustering 
algorithm, certain vertices of the graph may be pruned prior to clustering 
by using a combination of the {\em -edgeprune}, {\em -vtxprune}, or 
{\em -mincomponent} parameters.

If the {\em -zscores} is specified, each line of this file also contains two 
additional numbers right after the cluster number. The first number is its 
internal $z$-score, and the second number is its external $z$-score.


%=========================================================================
\subsubsection{Tree File}
\label{sec:usage:oformat:tree}

The tree produced by performing a hierarchical agglomerative clustering on top
of the $k$-way clustering solution produced by \vcluster is stored in a file
in the form of a {\em parent} array. In particular, if $k$ is the number
of clusters, then the {\em tree} file contains $2k-1$ lines, such that the 
$i$th line contains the parent of the $i$th node of the tree. In the
case of the root node, that is stored in the last line of the file, the
parent is set to -1. For example, the tree file for the tree shown 
in \figref{fig:vcluster-treefeatures} will contain 19 lines, and each line
will store the following numbers (one number per line): 16, 12, 13, 16, 13, 
10, 11, 12, 11, 10, 14, 15, 15, 14, 18, 17, 17, 18, -1.

In addition to the parent of each node, \cluto's tree file also outputs
two numbers for each internal node the tree. The first number is the
average similarity between the siblings of each tree node. Since this 
quantity is not defined for the leaves, only the rows of the file 
corresponding to the interior nodes of the tree contain meaningful numbers.
The second number is the change in the value of the criterion function
achieved by combining the particular pair of clusters. Note that in the
case of the traditional single-link, complete-link, and UPGMA agglomerative
methods, the {\em gain} of the agglomeration is considered to be the
weight of the {\em link} used in making the merging decisions.

If for some reason, \cluto's clustering programs cannot produce an entire
single hierarchical tree, then the parent array will contain multiple
subtrees. The subtrees can be re-constructed by traversing the parent array 
from the leaves toward the root. When a ``-1'' is encountered as the parent
of a node other than the root's, then this particular subtree ends.



%*************************************************************************
\section{Which Clustering Algorithm Should I Use?}
\label{sec:clmethod}

If you have read \cluto's manual up to this point you may start to wondering
about which clustering algorithm to use for your application. Well, there is
no correct answer, as it highly depends on the nature of your datasets and
what constitutes meaningful clusters in your application. Nevertheless, this
section attempts to clarify some of the ``sweet spots'' of \cluto's various 
clustering algorithms and provide some general usage guidelines.


%========================================================================
\subsection{Cluster Types}
\label{sec:clmethod:nature}

We start our discussion by describing two different types of clusters 
that often arise in different application domains. What differentiates 
them is the relationship between the cluster's objects and the dimensions 
of their feature space. Note that this is by no means an exhaustive 
list of cluster types.

The first type of clusters contains objects that exhibit a strong pattern 
of conservation along a subset of their dimensions. That is, there is a 
subset of the original dimensions in which a large fraction of the objects 
agree. For example, if the dimensions correspond to words (or products),
what that means is that a collection of documents (or customers) will 
form a cluster, if there exist a subset of terms (or products) that are 
present (or purchased) in a large fraction of the documents (or customers).
You can actually see this type of clusters by looking at the visualization
examples shown in \figref{fig:plotmatrixsparse}, as well as, the weights
associated with the descriptive features that were output using the
{\em -showfeatures} option in \figref{fig:vcluster-features}.
In the case of the visualizations, you can clearly see some of the 
dimensions (\ie., columns) that are conserved in each cluster,
and in the case of {\em -showfeatures} you can see that the top-5
terms in each cluster accounts for a large fraction of the similarity
between the objects of each cluster. 

This subset of dimensions is often referred to as a {\em subspace}, and 
the above stated property can be viewed as the cluster's objects and its
associated dimensions forming a {\em dense subspace}. Of course, the 
number of dimensions in these dense subspaces, as well as, the density 
(\ie., how large is the {\em fraction} of the objects that share the 
same dimensions) will be different from cluster to cluster. Exactly 
this variation in subspace size and density (and the fact that an 
object can be part of multiple disjoint or overlapping dense subspaces)
is what complicates the problem of discovering this type of clusters.
There are a number of application areas in which this type of clusters
give rise to meaningful grouping of the objects (\ie., domain experts
will tend to agree that the clusters are correct). Such areas includes
clustering documents based on the terms they contain, clustering
customers based on the products they purchase, clustering genes based
on their expression levels, clustering proteins based on the motifs
they contain, \etc.

The second type of clusters contains objects in which again there exist
a subspace associated with that cluster. However, unlike the earlier 
case, in these clusters there will be sub-clusters that share a very small 
number of the subspace's dimension, but there will be {\em a strong path} 
within that cluster that will connect them.  
By ``strong path'' we mean that if $A$ and $B$ are two sub-clusters that
share only a few dimensions, then there will be another set of sub-clusters 
$X_1, X_2, \ldots, X_k$, that belong to the cluster, such that each 
of the sub-cluster pairs $(A, X_1), (X_1, X_2), \ldots, (X_k, B)$ will 
share many of the subspace's dimensions. What complicates cluster discovery
in this setting is that the connections (\ie., shared subspace dimensions)
between sub-clusters within a particular cluster will tend to be of 
different strength. Examples of such clusters are the spatial clusters 
present in the two-dimensional datasets of \figref{fig:spatial}. 
In this case, the dimensions in our definition correspond to small 
ranges of the $x$ and $y$-axis. With this in mind, we see that there 
are groups of points in the $\Pi$-shaped clusters that do not share 
either of the $x$ or $y$ ranges, However, there is a spatially 
contiguous set of points that connect them. 

Our discussion so far focused on the relationship between the objects and
their feature space. However, these two classes of clusters can also be
understood in terms of the the object-to-object similarity graph. The
first type of clusters will tend to contain objects in which the similarity
between all pairs of objects will be high. On the other hand, in the
second type of clusters there will be a lot of objects whose direct
pairwise similarity will be quite low, but these objects will be connected
by many paths that stay within the cluster that traverse high similarity
edges. The names of these two cluster types were inspired by this
similarity-based view, and they are referred to as {\em globular} and
{\em transitive} clusters, respectively.


%========================================================================
\paragraph{Matching Algorithms to Cluster Types}
\label{sec:clmethod:algorithm}

\cluto provides clustering algorithms for finding both of these types
of clusters. In particular, the partitional clustering algorithms
corresponding to ``rb'', ``rbr'', and ``direct'', and the agglomerative 
algorithms ``agglo'' and ``bagglo'' that do not use the single-link 
criterion tend to find globular clusters. On the other hand, the 
agglomerative scheme with the single-link criterion and the 
graph-partitioning-based clustering algorithms tend to find transitive 
clusters. It should be noted that any of the algorithms can find either 
globular or transitive clusters provided that these clusters are 
sufficiently far away from each other.

The different clustering criterion functions used by the partitional and 
agglomerative clustering algorithms impact the extent to which the individual 
instance of the clustering algorithm is capable of finding globular clusters 
that contain clusters with different size consensus, or clusters whose 
average pair-wise similarity is different, as well as, the extent to which 
clusters can be of dramatically different sizes. The reader is referred to 
\cite{zhao01tr-vpcluster} for an analysis of these criterion functions.


%========================================================================
\subsection{Similarity Measures Between Objects}
\label{sec:clmethod:similarity}

\cluto's clustering algorithms implemented by \vcluster treat the objects 
to be clustered as vectors in a high-dimensional space and measure the degree 
of similarity between these objects using either the cosine function, the 
Pearson's correlation coefficient, extended Jaccard coefficient, or a similarity 
derived from the Euclidean distance of these vectors. By using the cosine 
and correlation coefficient measures, then two objects are similar if their 
corresponding vectors\footnote%
{
  In the case of Pearson's correlation coefficient the vectors are obtained
  by first subtracting their average value.
}
point in the same direction (\ie., they have roughly the same set of features 
and in the same proportion), regardless of their actual length. On the other 
hand, the Euclidean distance does take into account both direction and magnitude.
Finally, similarity based on extended Jaccard coefficient account both for
angle, as well as, magnitude.

These cosine- and correlation-based similarity measures are well-suited for 
clustering high-dimensional (as well as low-dimensional) datasets arising in 
many diverse applications areas, including information retrieval, customer 
purchasing transactions, science, and biology. Moreover, for many criterion 
functions, clustering algorithms based on the cosine similarity measure are 
equivalent with algorithms that use the Euclidean distance measure on vectors
that are scaled to be of unit-length \cite{zhao01tr-vpcluster}. On the other
hand, the Euclidean distance based similarity function is well-suited for 
finding clusters in the original feature space, as it is the case for the 
spatial clusters shown in \figref{fig:spatial}.

There are applications in which the provided similarity measures are not
sufficient (\eg., clustering sequence dataset). In such cases you have to use
the \scluster program in which you provide the pairwise similarities between
the objects (you need to provide only the non-zero similarities). It is 
critical to ensure that the supplied similarities are reasonable, especially
in the case of criterion driven partitional clustering (\ie., for ``rb'', ``rbr'', 
and ``direct''), as these approaches try to optimize the clustering criterion
function, based only on these similarities. Some examples of bad similarity 
functions will be the ones in which there is a wide-range between the various 
similarity values, with some pairwise similarities being extremely large.
In such cases, the optimal clustering solution (in terms of the criterion
function) may just contain individual clusters for each such highly-similar
pair of objects, with the rest of the objects assigned to one cluster. 





%========================================================================
\subsection{Scalability of \cluto's Clustering Algorithms}
\label{sec:clmethod:scalability}

The various clustering algorithms provided with \cluto have different scalability
characteristics. \tblref{tbl:scalability} summarizes the time- and space-complexity
of some of the clustering algorithms.


\begin{table}[htb]
\small
\begin{center}
\begin{tabular}{|l|c|c|}
\multicolumn{3}{c}{\vcluster}\\\hline
Algorithm          & Time Complexity    & Space Complexity \\\hline
-clmethod=rb, -sim=cos       & $O(\mbox{\em NNZ}*\log(k))$   & $O(\mbox{\em NNZ})$ \\\hline
-clmethod=rb, -sim=corr      & $O(n*m*\log(k))$   & $O(n*m)$ \\\hline
-clmethod=direct, -sim=cos   & $O(\mbox{\em NNZ}*k+m*k)$   & $O(\mbox{\em NNZ}+m*k)$ \\\hline
-clmethod=direct, -sim=corr  & $O(n*m*k)$   & $O(n*m+m*k)$ \\\hline
-clmethod=agglo,             & $O(n^2*\log(n))$   & $O(n^2)$ \\\hline
-clmethod=agglo, -crfun=[\ione,\itwo] & $O(n^3)$   & $O(n^2)$ \\\hline
-clmethod=graph,             & $O(n^2+n*\mbox{\em NNbrs}*\log(k))$   & $O(n\mbox{\em NNbrs})$ \\\hline
\multicolumn{3}{c}{\hspace{1cm}}\\
\multicolumn{3}{c}{\scluster}\\\hline
Algorithm          & Time Complexity    & Space Complexity \\\hline
-clmethod=rb, -sim=cos       & $O(\mbox{\em NNZ}*\log(k))$   & $O(\mbox{\em NNZ})$ \\\hline
-clmethod=rb, -sim=corr      & $O(n*m*\log(k))$   & $O(n*m)$ \\\hline
-clmethod=direct, -sim=cos   & $O(\mbox{\em NNZ}*k+m*k)$   & $O(\mbox{\em NNZ}+m*k)$ \\\hline
-clmethod=direct, -sim=corr  & $O(n*m*k)$   & $O(n*m+m*k)$ \\\hline
-clmethod=agglo,             & $O(n^2*\log(n))$   & $O(n^2)$ \\\hline
-clmethod=agglo, -crfun=[\ione,\itwo] & $O(n^3)$   & $O(n^2)$ \\\hline
-clmethod=graph,             & $O(n*\mbox{\em NNbrs}*\log(k))$   & $O(n\mbox{\em NNbrs})$ \\\hline
\end{tabular}
\end{center}
\caption{The complexity of \cluto's clustering algorithms. The meaning of the various
quantities are as follows: $n$ is the number of objects to be clustered, $m$ is the 
number of dimensions, {\em NNZ} is the number of non-zeros in the input matrix or 
similarity matrix, {\em NNbrs} is the number of neighbors in the nearest-neighbor graph.}
\label{tbl:scalability}
\end{table}

Looking at these results we can see that in terms of time and memory, the most scalable
method is \vcluster's repeated-bisecting algorithm that uses the cosine similarity 
function (\ie., {\em -clmethod=rb}, {\em -sim=cos}). Our experiments showed that it 
can compute a 10-way partitioning of a dataset with 140K documents and 83K terms
in less than five minutes on a Intel Xeon based workstation. The least scalable
of the algorithms are the ones based on hierarchical agglomerative clustering.
The critical aspect of these algorithms is that their memory requirements scale
quadratic on the number of objects, and they cannot be used to cluster more than
5K-10K objects. However, if you do want to obtain a tree for a large dataset you
should then use the {\em -fulltree} option that combines partitional and agglomerative 
clustering. 



\newpage
%*************************************************************************
\section{\cluto's Library Interface}
\label{sec:library}

The functionality provided by \cluto's \vcluster and \scluster programs can 
also be accessed directly from a C or C++ program by using the provided 
stand-alone library. In the rest of this section we provide information 
about how to link your program with \cluto's library, describe the data 
structures used to pass information into the routines and give a detailed 
description of the calling sequence of the various routines.


%=========================================================================
\subsection{Using \cluto's Library}
\label{sec:library:usage}

In order to use \cluto's stand-alone library you must link your program
with \cluto's pre-compiled library that is provide in the software
distribution. For Unix-based distributions, the name of the library is
{\tt libcluto.a}, and for the Windows~32 distribution, the name of the 
library file is {\tt libcluto.lib}. At this point no dynamic link 
libraries are provided for either Unix- or Windows-based distributions;
however, such libraries may be provided in the future.

The method by which an external library is linked to your program varies
from system to system. In most Unix-based systems you can link it by just
specifying {\tt -lcluto} at the end of ``cc'' or ``ld'' command line.
Care must be taken that \cluto's library is in the default library search
path. In most cases this can be modified by using the ``-L'' option to
specify the directory where {\tt libcluto.a} is stored. For Windows-based
systems, the linking method depends on the particular development environment,
and you should consult its documentation.

Any program that uses \cluto's library must include the {\tt cluto.h} header
file that is provided with \cluto's distribution. This file contains various
constant definitions as well as function prototypes and allows C and C++ 
programs to access \cluto's functions. 



%=========================================================================
\subsection{Matrix and Graph Data Structure}
\label{sec:library:csr}


Most of the routines in \cluto's library take, as input, the objects 
to be clustered in the form of a matrix. For some routines this matrix 
corresponds to the feature-space representation of the objects, that
is, the rows are the objects and the columns are the features (just 
like the matrix-file for the \vcluster program). Whereas for some
other routines, this matrix corresponds to the adjacency matrix of the 
similarity graph between the objects, that is, both the rows and
the columns of the matrix correspond to the vertices in the graph
(just like the graph-file for the \scluster program). 

Even though these two type of matrices represent entirely different 
information, they are provided to \cluto's routines using the same 
data structure. This is primarily because the adjacency matrix of 
a graph is, after all, a matrix which just happens to have the 
same number of rows and columns.

\cluto's routines support both sparse and dense matrices using the same 
set of data structures. 



%-------------------------------------------------------------------------
\paragraph{Sparse Matrix and Graph Data Structure}

A sparse matrix is supplied to \cluto's routines using a row-based compressed 
storage format (CSR). The CSR format is a widely used scheme for storing 
sparse matrices. In this format a matrix with $n$ rows, $m$ columns, and 
{\em nnz} non-zero entries is represented using three arrays that are called 
{\tt rowptr}, {\tt rowind}, and {\tt rowval}. The array {\tt rowptr} is of 
size $n+1$ whereas the arrays {\tt rowind} and {\tt rowval} are of size 
{\em nnz}.

The array {\tt rowind} stores the column-indices of the non-zero entries in
the matrix, and the array {\tt rowval} stores their corresponding values.
In particular, the array {\tt rowind} stores the column-indices of the first
row, followed by the column-indices of the second row, and so on. Similarly, 
the array {\tt rowval} stores the corresponding values of the non-zero entries 
of the first row, followed by the corresponding values of the non-zero entries 
of the second row, and so on. The array {\tt rowptr} is used to determine where 
the storage of a row starts and ends in the arrays, {\tt rowind} and {\tt rowval}. 
In particular, the column-indices of the $i$th row are stored starting at 
{\tt rowind[rowptr[i]]} and ending at (but not including) {\tt rowind[rowptr[i+1]]}. 
Similarly, the values of the non-zero entries of the $i$th row are stored 
starting at {\tt rowval[rowptr[i]]} and ending at (but not including) 
{\tt rowval[rowptr[i+1]]}. Also note that the number of non-zero entries of 
the $i$th row is simply {\tt rowptr[i+1]-rowptr[i]}.

\begin{figure}[htb]
\centerline{\psfig{figure=./figures/matrixcsr.eps,width=6in}}
\caption{An example of the CSR format for storing sparse matrices.}
\label{fig:csr}
\end{figure}

\figref{fig:csr} illustrates the CSR format for the sparse matrix used earlier
to illustrated the format of the matrix file used by \vcluster. Note,
that the numbering of the columns in the CSR format starts from zero and 
not from one.


%-------------------------------------------------------------------------
\paragraph{Dense Matrix Data Structure}

A dense matrix is supplied to \cluto's routines by using only the {\tt rowval}
array and setting the {\tt rowptr} and {\tt rowind} arrays to NULL. In fact,
\cluto's routines determine the input matrix format by checking to see if {\tt
rowptr} is NULL or not. A dense matrix with $n$ rows and $m$ columns is 
passed to \cluto by supplying in {\tt rowval} the $n\times m$ values of the
matrix, in row-major order format. That is, the $m$ values of the $i$th
row (where $i$ takes values from $0 \ldots n-1$) is stored starting at 
location {\tt rowval[i*m]} and ending at (but not including) 
{\tt rowval[(i+1)*m]}. 




%=========================================================================
\subsection{Clustering Parameters}
\label{sec:library:clparams}

Most of \cluto's routines take, as input, two parameters that control the 
similarity function to be used while clustering the objects and the
clustering criterion function to be optimized in the process of clustering.
These two parameters are called {\em simfun} and {\em crfun}, respectively.

%---------------------------------------------------------------------
\subsubsection{The {\em simfun} Parameter}
\label{sec:library:clparams:simfun}

This parameter specified the similarity function to be used for clustering 
the objects. This parameter is similar to the {\em -sim} option of \vcluster.
The possible values for the {\em simfun} parameter are the following:

\begin{quote}
\begin{Ventry}{CLUTO\_SIM\_CORRCOEFX}{\bf}
  \item[CLUTO\_SIM\_COSINE]  
     The similarity between the objects is computed using the cosine 
     function of their vectors. This is the similarity function used
     by the default settings of \vcluster and \scluster.

  \item[CLUTO\_SIM\_CORRCOEF] 
     The similarity between the objects is computed using the correlation
     coefficient of their vectors.

  \item[CLUTO\_SIM\_EDISTANCE] 
     The similarity between the objects is computed to be inversely related
     to their Euclidean distance. In particular, if $d_{i,j}$ is the distance
     between two objects, and $d_{\max}$ is the maximum distance between any two
     objects in the dataset, the similarity between these objects is set to be
     \[ \mbox{sim}(i,j) = 1 - \frac{d_{i,j}}{1.0+d_{\max}}. \]

  \item[CLUTO\_SIM\_EJACCARD] 
     The similarity between the objects is computed using the extended Jaccard
     coefficient of their vectors. If $u$ and $v$ are the vectors of two objects, 
     their extended Jaccard coefficient is:
     \[ \mbox{sim}_{ejacc}(u,v) = \frac{\dotp{u}{v}}{\nrm{u}+\nrm{v} - \dotp{u}{v}}.\]
\end{Ventry}
\end{quote}

%---------------------------------------------------------------------
\subsubsection{The {\em crfun} Parameter}
\label{sec:library:clparams:crfun}

This parameter specifies the clustering criterion function to be used in 
finding the clusters. This parameter is similar to the {\em -crfun}
option of \vcluster and \scluster. The possible values for the 
{\em crfun} parameter are the following:

\begin{quote}
\begin{Ventry}{CLUTO\_CLFUN\_UPGMA\_WXX}{\bf}
  \item[CLUTO\_CLFUN\_I1]  
      Selects the I1 (\ione) criterion function.

  \item[CLUTO\_CLFUN\_I2]  
      Selects the I2 (\itwo) criterion function.

  \item[CLUTO\_CLFUN\_E1]  
      Selects the E1 (\eone) criterion function.

  \item[CLUTO\_CLFUN\_G1]  
      Selects the G1 (\gone) criterion function.

  \item[CLUTO\_CLFUN\_G1P] 
      Selects the G1' (\goneprime) criterion function.

  \item[CLUTO\_CLFUN\_H1]  
      Selects the H1 (\hone) criterion function.

  \item[CLUTO\_CLFUN\_H2]  
      Selects the H2 (\htwo) criterion function.

  \item[CLUTO\_CLFUN\_SLINK]  
      Selects the traditional single-link merging criterion.

  \item[CLUTO\_CLFUN\_SLINK\_W]  
      Selects the weighted single-link merging criterion, in which the initial
      similarity between two clusters is scaled by the sum of the similarities
      between the objects of the cluster.

  \item[CLUTO\_CLFUN\_CLINK]  
      Selects the traditional complete-link merging criterion.

  \item[CLUTO\_CLFUN\_CLINK\_W]  
      Selects the weighted complete-link merging criterion, in which the initial
      similarity between two clusters is scaled by the sum of the similarities
      between the objects of the cluster.

  \item[CLUTO\_CLFUN\_UPGMA]  
      Selects the traditional UPGMA merging criterion.
\end{Ventry}
\end{quote}



%---------------------------------------------------------------------
\subsubsection{The {\em cstype} Parameter}
\label{sec:library:clparams:cstype}

This parameter specifies the method to be used for selecting the next cluster 
to be bisected by \cluto's repeated-bisecting- and graph-partitioning-based
clustering algorithms. This parameter is similar to the {\em -cstype}
option of \vcluster and \scluster. The possible values for the 
{\em cstype} parameter are the following:

\begin{quote}
\begin{Ventry}{CLUTO\_CSTYPE\_LARGESUBSPACEFIRST}{\bf}
  \item[CLUTO\_CSTYPE\_LARGEFIRST]  
      Selects to bisect the largest cluster from the current clustering
      solution.

  \item[CLUTO\_CSTYPE\_BESTFIRST]  
      Selects to bisect the cluster that will lead to the best value of the
      clustering criterion function that is guides the clustering process.

  \item[CLUTO\_CSTYPE\_LARGESUBSPACEFIRST]  
      Selects to bisect the cluster that will lead to the largest reduction 
      on the number of the subspace dimensions of this cluster.

\end{Ventry}
\end{quote}



%=========================================================================
\subsection{Object Modeling Parameters}
\label{sec:library:objectmodel}

Most of \cluto's routines take as input three parameters that control how
the rows and columns of the input matrix will be modeled. These parameters 
are called {\em rowmodel}, {\em colmodel}, and {\em colprune}.


%---------------------------------------------------------------------
\subsubsection{The {\em rowmodel} Parameter}
\label{sec:library:objectmodel:rowmodel}

This parameter specifies the model to be used for scaling the various 
columns of each row. This parameter is similar to the {\em -rowmodel} 
option of \vcluster. The possible values for this parameter are:

\begin{quote}
\begin{Ventry}{CLUTO\_ROWMODEL\_MAXTF}{\bf}
   \item[CLUTO\_ROWMODEL\_NONE]  
         The columns of each row are not scaled and used as supplied in the 
         {\tt rowval} array. 

   \item[CLUTO\_ROWMODEL\_MAXTF] 
         The columns of each row are scaled so their values are between 0.5 
         and 1.0. 

   \item[CLUTO\_ROWMODEL\_SQRT] 
         The columns of each row are scaled to be equal to the square 
         root of their actual values. 
         
   \item[CLUTO\_ROWMODEL\_LOG] 
         The columns of each row are scaled to be equal to the log of their 
         actual values. 
\end{Ventry}
\end{quote}


%---------------------------------------------------------------------
\subsubsection{The {\em colmodel} Parameter}
\label{sec:library:objectmodel:colmodel}

This parameter specifies the model to be used for scaling the various columns 
globally across all the rows of the matrix. This parameter is similar to the 
{\em -colmodel} option of \vcluster. The possible values for this parameter 
are:

\begin{quote}
\begin{Ventry}{CLUTO\_COLMODEL\_NONE}{\bf}
  \item[CLUTO\_COLMODEL\_NONE]  
        The columns of the matrix are not globally scaled and they are
        used as is.

  \item[CLUTO\_COLMODEL\_IDF] 
        The columns of the matrix are scaled according to the inverse
        document frequency paradigm (IDF), that was described in
        \vcluster's section. 
\end{Ventry}
\end{quote}


%---------------------------------------------------------------------
\subsubsection{The {\em grmodel} Parameter}
\label{sec:library:objectmodel:grmodel}

This parameter specifies the type of $k$-nearest neighbor graph that 
will be built by \cluto's graph-partitioning based clustering algorithms.
This parameter is similar to the {\em -grmodel} option of \vcluster 
and \scluster. The possible values for this parameter are:

\begin{quote}
\begin{Ventry}{CLUTO\_GRMODEL\_ASYMETRIC\_DIRECTXXX}{\bf}
  \item[CLUTO\_GRMODEL\_SYMETRIC\_DIRECT]
        An edge between two vertices $u$ and $v$ is included if and only if
        they are in the nearest-neighbor list of each other. The weight of
        this edge is set equal to the similarity of the objects.

  \item[CLUTO\_GRMODEL\_ASSYMETRIC\_DIRECT]
        An edge between two vertices $u$ and $v$ is included as long as 
        one of them is in the nearest-neighbor list of the other. The 
        weight of this edge is set equal to the similarity of the objects.

  \item[CLUTO\_GRMODEL\_SYMETRIC\_LINK]
        An edge between two vertices $u$ and $v$ is included if and only if
        they are in the nearest-neighbor list of each other. The weight of
        this edge was set equal to the number of neighbors that vertices
        $u$ and $v$ have in common.

  \item[CLUTO\_GRMODEL\_ASSYMETRIC\_LINK]
        An edge between two vertices $u$ and $v$ is included as long as 
        one of them is in the nearest-neighbor list of the other. The 
        weight of this edge was set equal to the number of neighbors 
        that vertices $u$ and $v$ have in common.

  \item[CLUTO\_GRMODEL\_NONE]
        The supplied graph is used as is.
\end{Ventry}
\end{quote}

%---------------------------------------------------------------------
\subsubsection{The {\em colprune} Parameter}
\label{sec:library:objectmodel:colprune}

This parameter specifies the factor by which the columns of the matrix will 
be pruned before performing the clustering. Valid range of values are from 
$(0.0, 1.0]$.  A value of 1.0 indicates no pruning and is the default setting 
for \vcluster.


%---------------------------------------------------------------------
\subsubsection{The {\em edgeprune} Parameter}
\label{sec:library:objectmodel:edgeprune}

This parameter controls how the edges in the graph-partitioning clustering
algorithms will be pruned based on the link-connectivity of their incident
vertices. Please refer to the discussion of \cluto's {\em -edgeprune} for further
details. A value of -1 suppresses edge-pruning.


%---------------------------------------------------------------------
\subsubsection{The {\em vtxprune} Parameter}
\label{sec:library:objectmodel:vtxprune}

This parameter controls how outlier vertices in the graph-partitioning 
clustering algorithms will be pruned based on their degree. Please refer 
to the discussion of \cluto's {\em -vtxprune} for further details. 
A value of -1 suppresses vertex-pruning.



%=========================================================================
\subsection{Debugging Parameter}
\label{sec:library:debug}

Most of \cluto's routines take as input a parameter called {\em dbglvl}
that controls the amount of information to be printed. This is used for 
internal purposes and should be set to  0, which suppresses any debugging 
output.




\clearpage
%=========================================================================
\subsection{Clustering Routines}
\label{sec:library:clustering}


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_VP\_ClusterDirect}

\begin{tabbing}
void {\sf\bf CLUTO\_VP\_ClusterDirect} \= 
             (int nrows, int ncols, int *rowptr, int *rowind, float *rowval, int simfun, \\
	  \> int crfun, int rowmodel, int colmodel, float colprune, int ntrials, int niter, \\
	  \> int seed, int dbglvl, int nclusters, int *part)
\end{tabbing}

\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to cluster a matrix into a specified ($k$) number of clusters using a 
   partitional clustering algorithm that computes the $k$-way clustering directly. 
   Provides the functionality of the {\em -clmethod=direct} clustering method
   of the \vcluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the objects to
       be clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun, crfun]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       
    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[ntrials]
       Specifies the number of different clustering solutions to be computed. 
       The solution that achieves the best value of the criterion function is 
       the one that is returned. The value for {\em ntrials} must be greater 
       than zero, and \vcluster's default setting is 10.


    \item[niter]
       Specifies the maximum number of iterations that are performed during each 
       refinement cycle. The value for {\em niter} has to be greater than zero. 


    \item[seed]
       The seed to be used by the random number generator. 


    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.


    \item[nclusters]
       The number of desired clusters.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[part]
       This is an array of size {\em nrows} that upon successful completion stores 
       the clustering vector of the matrix. The $i$th entry of this array stores
       the cluster number that the $i$th row of the matrix belongs to. Note that
       the numbering of the clusters starts from zero.
       The application is responsible for allocating the memory for this array.
       
       Under certain circumstances, \cluto may not be able to assign a particular 
       row to a cluster. In this case, the {\em part[]} entry of that particular 
       row will be set to -1. 
       
  \end{Lentry}

\item[{\bf\sf Note}]\mbox{}\\

\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_VP\_ClusterRB}
\begin{tabbing}
void {\sf\bf CLUTO\_VP\_ClusterRB} 
       \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval,\\
       \> int simfun, int crfun, int rowmodel, int colmodel, float colprune, \\
       \> int ntrials, int niter, int seed, int cstype, int kwayrefine, \\
       \> int dbglvl, int nclusters, int *part)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to cluster a matrix into a specified ($k$) number of clusters using 
   a partitional clustering algorithm that computes the $k$-way by performing a
   sequence of repeated bisections. Provides the functionality of the 
   {\em -clmethod=rb} and {\em -clmethod=rbr} clustering methods of the 
   \vcluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects to be clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun, crfun, cstype]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       
    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are 
       described in \secref{sec:library:objectmodel}.

    \item[ntrials]
       Specifies the number of different clustering solutions to be computed. 
       The solution that achieves the best value of the criterion function is 
       the one that is returned. The value for {\em ntrials} must be greater 
       than zero. 

    \item[niter]
       Specifies the maximum number of iterations that are performed during each 
       refinement cycle. The value for {\em niter} has to be greater than zero. 

    \item[seed]
       The seed to be used by the random number generator. 

    \item[kwayrefine]
       This parameter controls whether or not the clustering solution will be 
       globally optimized at the end by performing a series of $k$-way refinement 
       iterations. The possible values for this parameter are:

       \begin{Ventry}{99}{\bf}
         \item[0]  Does not optimize the clustering solution globally.
         \item[1]  Optimizes the clustering solution globally.
       \end{Ventry}

       The global optimization of the clustering solution can significantly
       increase the amount of time required to perform the clustering.

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

    \item[nclusters]
       The number of desired clusters.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[part]
       This is an array of size {\em nrows} that upon successful completion stores 
       the clustering vector of the matrix. The $i$th entry of this array stores
       the cluster number that the $i$th row of the matrix belongs to. Note that
       the numbering of the clusters starts from zero.
       The application is responsible for allocating the memory for this array.
       
       Under certain circumstances, \cluto may not be able to assign a particular 
       row to a cluster. In this case, the {\em part[]} entry of that particular 
       row will be set to -1. 
       
  \end{Lentry}

\item[{\bf\sf Note}]\mbox{}\\
   CLUTO\_VP\_ClusterRB is considerably faster than CLUTO\_VP\_ClusterDirect and
   it should be preferred if the number of desired clusters is quite large (\eg.,
   greater than 20--30).

\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_VP\_GraphClusterRB}
\begin{tabbing}
int {\sf\bf CLUTO\_VP\_GraphClusterRB} 
       \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval,\\
       \> int simfun, int rowmodel, int colmodel, float colprune, int grmodel, \\
       \> int nnbrs, float edgeprune, float vtxprune, int mincmp, \\
       \> int ntrials, int seed, int cstype, int dbglvl, int nclusters, \\
       \> int *part, float *crvalue)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to cluster a matrix into a specified ($k$) number of clusters using 
   a graph-partitioning-based clustering algorithm that computes the $k$-way 
   by performing a sequence of repeated min-cut bisections. Provides the 
   functionality of the {\em -clmethod=graph} clustering method of the 
   \vcluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects to be clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun, crfun, cstype]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       
    \item[rowmodel, colmodel, colprune, vtxprune, edgeprune]
       The object modeling parameters whose meaning and possible values are 
       described in \secref{sec:library:objectmodel}.

    \item[nnbrs]
       The number of neighbors of each object that will be used to create the
       nearest neighbor graph.

    \item[mincmp]
       The size of the minimum connect component that will be pruned prior
       to clustering.

    \item[ntrials]
       Specifies the number of different clustering solutions to be computed. 
       The solution that achieves the best value of the criterion function is 
       the one that is returned. The value for {\em ntrials} must be greater 
       than zero. 

    \item[seed]
       The seed to be used by the random number generator. 

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

    \item[nclusters]
       The number of desired clusters.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[part]
       This is an array of size {\em nrows} that upon successful completion stores 
       the clustering vector of the matrix. The $i$th entry of this array stores
       the cluster number that the $i$th row of the matrix belongs to. Note that
       the numbering of the clusters starts from zero.
       The application is responsible for allocating the memory for this array.
       
       Under certain circumstances, \cluto may not be able to assign a particular 
       row to a cluster. In this case, the {\em part[]} entry of that particular 
       row will be set to -1. 
       
    \item[crvalue]
       This is a variable that upon returns stores the edge-cut of the clustering
       solution.
  \end{Lentry}

\item[{\bf\sf Returned Value}]\mbox{}\\
  Returns the number of clusters that it found. This number will be equal to 
  the number of desired clusters plus the number of connected components in
  the graph.
   

\item[{\bf\sf Note}]\mbox{}\\

\end{description}
\clearpage



%------------------------------------------------------------------------------
\subsubsection{CLUTO\_VA\_Cluster}
\begin{tabbing}
void {\sf\bf CLUTO\_VA\_Cluster} 
    \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval,\\
    \> int simfun, int crfun, int rowmodel, int colmodel, float colprune, \\
    \> int dbglvl, int nclusters, int *part, int *ptree, float *tsims, float *gains)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to cluster a matrix into a specified ($k$) number of clusters using 
   a hierarchical agglomerative clustering algorithm. Provides the functionality 
   of the {\em -clmethod=agglo} clustering method of the \vcluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the objects to
       be clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun, crfun]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       
    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

    \item[nclusters]
       The number of desired clusters.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[part]
       This is an array of size {\em nrows} that upon successful completion stores 
       the clustering vector of the matrix. The $i$th entry of this array stores
       the cluster number that the $i$th row of the matrix belongs to. Note that
       the numbering of the clusters starts from zero.
       The application is responsible for allocating the memory for this array.
       
       Under certain circumstances, \cluto may not be able to assign a particular 
       row to a cluster. In this case, the {\em part[]} entry of that particular 
       row will be set to -1. 
       
    \item[ptree]
       This is an array of size {\em 2*nrows} that upon successful completion 
       stores the parent array of the binary hierarchical tree.  In this tree,
       each node corresponds to a cluster. The leaf nodes are the original {\em
       nrows} objects, and they are numbered from 0~to~{\em nrows}-1. The internal 
       nodes of the tree are numbered from {\em nrows} to 2*{\em nrows}-2. 
       The numbering of the internal nodes is performed so that smaller numbers 
       correspond to clusters obtained by merging a pair of 
       clusters earlier during the agglomeration process. The root of the tree 
       is numbered 2*{\em nrows}-2.

       The $i$th entry of the {\em ptree} array stores the parent node of the $i$
       node of the tree. The {\em ptree} entry for the root is set to -1.

       The application is responsible for allocating the memory for this array.
       
    \item[tsims]
       This is an array of size {\em 2*nrows} that upon successful completion 
       stores the average similarity between every pair of siblings in the induced 
       tree. In particular, {\em tsims[$i$]} stores the average pairwise
       similarity between the pair of clusters that are the children of the $i$th
       node of the tree. Note that the first {\em nrows} entries of this vector
       are not defined and are set to 0.0.

       The application is responsible for allocating the memory for this array.

    \item[gains]
       This is an array of size {\em 2*nrows} that upon successful completion 
       stores the gains in the value of the criterion function resulted by
       the merging pairs of clusters. In particular, {\em gains[$i$]} stores 
       the gain achieved by merging the clusters that are the children of the 
       $i$th node of the tree. Note that the first {\em nrows} entries of this 
       vector are not defined and are set to 0.0.

       The application is responsible for allocating the memory for this array.
  \end{Lentry}

\item[{\bf\sf Note}]\mbox{}\\
   Due to the high computational requirements of CLUTO\_VA\_Cluster, it should only 
   be used to cluster matrices that have fewer than 3,000--6,000 rows.

\end{description}
\clearpage



%------------------------------------------------------------------------------
\subsubsection{CLUTO\_VA\_ClusterBiased}
\begin{tabbing}
void {\sf\bf CLUTO\_VA\_ClusterBiased} 
    \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval, int simfun,\\
    \> int crfun, int rowmodel, int colmodel, float colprune, int dbglvl,\\
    \> int npclusters, int nclusters, int *part, int *ptree, float *tsims, float *gains)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to cluster a matrix into a specified ($k$) number of clusters using 
   a hierarchical agglomerative clustering algorithm that is biased by a partitionally
   computed clustering solution. Provides the functionality of the {\em -clmethod=bagglo} 
   clustering method of the \vcluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the objects to
       be clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun, crfun]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       
    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

    \item[npclusters]
       The number of clusters for which the partitional clustering solution will be
       computed. In the case of the {\em -clmethod=bagglo} this is set automatically
       to $\sqrt{\mbox{nrows}}$.

    \item[nclusters]
       The number of desired clusters.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[part]
       This is an array of size {\em nrows} that upon successful completion stores 
       the clustering vector of the matrix. The $i$th entry of this array stores
       the cluster number that the $i$th row of the matrix belongs to. Note that
       the numbering of the clusters starts from zero.
       The application is responsible for allocating the memory for this array.
       
       Under certain circumstances, \cluto may not be able to assign a particular 
       row to a cluster. In this case, the {\em part[]} entry of that particular 
       row will be set to -1. 
       
    \item[ptree]
       This is an array of size {\em 2*nrows} that upon successful completion 
       stores the parent array of the binary hierarchical tree.  In this tree,
       each node corresponds to a cluster. The leaf nodes are the original {\em
       nrows} objects, and they are numbered from 0~to~{\em nrows}-1. The internal 
       nodes of the tree are numbered from {\em nrows} to 2*{\em nrows}-2. 
       The numbering of the internal nodes is performed so that smaller numbers 
       correspond to clusters obtained by merging a pair of 
       clusters earlier during the agglomeration process. The root of the tree 
       is numbered 2*{\em nrows}-2.

       The $i$th entry of the {\em ptree} array stores the parent node of the $i$
       node of the tree. The {\em ptree} entry for the root is set to -1.

       The application is responsible for allocating the memory for this array.
       
    \item[tsims]
       This is an array of size {\em 2*nrows} that upon successful completion 
       stores the average similarity between every pair of siblings in the induced 
       tree. In particular, {\em tsims[$i$]} stores the average pairwise
       similarity between the pair of clusters that are the children of the $i$th
       node of the tree. Note that the first {\em nrows} entries of this vector
       are not defined and are set to 0.0.

       The application is responsible for allocating the memory for this array.

    \item[gains]
       This is an array of size {\em 2*nrows} that upon successful completion 
       stores the gains in the value of the criterion function resulted by
       the merging pairs of clusters. In particular, {\em gains[$i$]} stores 
       the gain achieved by merging the clusters that are the children of the 
       $i$th node of the tree. Note that the first {\em nrows} entries of this 
       vector are not defined and are set to 0.0.

       The application is responsible for allocating the memory for this array.
  \end{Lentry}

\item[{\bf\sf Note}]\mbox{}\\
   Due to the high computational requirements of CLUTO\_VA\_ClusterBiased, it should 
   only be used to cluster matrices that have fewer than 3,000--6,000 rows.

\end{description}
\clearpage



%------------------------------------------------------------------------------
\subsubsection{CLUTO\_SP\_ClusterDirect}
\begin{tabbing}
void {\sf\bf CLUTO\_SP\_ClusterDirect} \= 
             (int nrows, int *rowptr, int *rowind, float *rowval, int crfun, \\
	  \> int ntrials, int niter, int seed, int dbglvl, int nclusters, int *part)
\end{tabbing}

\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to cluster a graph into a specified ($k$) number of clusters using a 
   partitional clustering algorithm that computes the $k$-way clustering 
   directly. Provides the functionality of the {\em -clmethod=direct} clustering 
   method of the \scluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows]
       The number of rows of the input adjacency matrix whose rows store the 
       adjacency structure of the between object similarity graph.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[crfun]
       The clustering criterion function whose meaning and possible values are 
       described in \secref{sec:library:clparams}.
       

    \item[ntrials]
       Specifies the number of different clustering solutions to be computed. 
       The solution that achieves the best value of the criterion function is 
       the one that is returned. The value for {\em ntrials} must be greater 
       than zero, and \vcluster's default setting is 10.


    \item[niter]
       Specifies the maximum number of iterations that are performed during each 
       refinement cycle. The value for {\em niter} has to be greater than zero. 


    \item[seed]
       The seed to be used by the random number generator. 


    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.


    \item[nclusters]
       The number of desired clusters.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[part]
       This is an array of size {\em nrows} that upon successful completion stores 
       the clustering vector of the matrix. The $i$th entry of this array stores
       the cluster number that the $i$th row of the matrix belongs to. Note that
       the numbering of the clusters starts from zero.
       The application is responsible for allocating the memory for this array.
       
       Under certain circumstances, \cluto may not be able to assign a particular 
       row to a cluster. In this case, the {\em part[]} entry of that particular 
       row will be set to -1. 
       
  \end{Lentry}

\item[{\bf\sf Note}]\mbox{}\\

\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_SP\_ClusterRB}
\begin{tabbing}
void {\sf\bf CLUTO\_SP\_ClusterRB} 
       \= (int nrows, int *rowptr, int *rowind, float *rowval, int crfun\\
       \> int ntrials, int niter, int seed, int cstype, int kwayrefine, \\
       \> int dbglvl, int nclusters, int *part)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to cluster a matrix into a specified ($k$) number of clusters using 
   a partitional clustering algorithm that computes the $k$-way by performing a
   sequence of repeated bisections. Provides the functionality of the 
   {\em -clmethod=rb} and {\em -clmethod=rbr} clustering methods of the 
   \scluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows]
       The number of rows of the input adjacency matrix whose rows store the 
       adjacency structure of the between-object similarity graph.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[crfun, cstype]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       

    \item[ntrials]
       Specifies the number of different clustering solutions to be computed. 
       The solution that achieves the best value of the criterion function is 
       the one that is returned. The value for {\em ntrials} must be greater 
       than zero. 

    \item[niter]
       Specifies the maximum number of iterations that are performed during each 
       refinement cycle. The value for {\em niter} has to be greater than zero. 

    \item[seed]
       The seed to be used by the random number generator. 


    \item[kwayrefine]
       This parameter controls whether or not the clustering solution will be 
       globally optimized at the end by performing a series of $k$-way refinement 
       iterations. The possible values for this parameter are:

       \begin{Ventry}{99}{\bf}
         \item[0]  Does not optimize the clustering solution globally.
         \item[1]  Optimizes the clustering solution globally.
       \end{Ventry}

       The global optimization of the clustering solution can significantly
       increase the amount of time required to perform the clustering.

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

    \item[nclusters]
       The number of desired clusters.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[part]
       This is an array of size {\em nrows} that upon successful completion stores 
       the clustering vector of the matrix. The $i$th entry of this array stores
       the cluster number that the $i$th row of the matrix belongs to. Note that
       the numbering of the clusters starts from zero.
       The application is responsible for allocating the memory for this array.
       
       Under certain circumstances, \cluto may not be able to assign a particular 
       row to a cluster. In this case, the {\em part[]} entry of that particular 
       row will be set to -1. 
       
  \end{Lentry}

\item[{\bf\sf Note}]\mbox{}\\
   CLUTO\_SP\_ClusterRB is considerably faster than CLUTO\_SP\_ClusterDirect and
   it should be preferred if the number of desired clusters is quite large (\eg.,
   greater than 20--30).

\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_SP\_GraphClusterRB}
\begin{tabbing}
int {\sf\bf CLUTO\_SP\_GraphClusterRB} 
       \= (int nrows, int *rowptr, int *rowind, float *rowval, int nnbrs, \\
       \> float edgeprune, float vtxprune, int mincmp, int ntrials, int seed,\\
       \> int cstype, int dbglvl, int nclusters, int *part, float *crvalue)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to cluster a matrix into a specified ($k$) number of clusters using 
   a graph-partitioning-based clustering algorithm that computes the $k$-way 
   by performing a sequence of repeated min-cut bisections. Provides the 
   functionality of the {\em -clmethod=graph} clustering method of the 
   \scluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows]
       The number of rows of the input adjacency matrix whose rows store the 
       adjacency structure of the between-object similarity graph.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[cstype]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       
    \item[vtxprune, edgeprune]
       The object modeling parameters whose meaning and possible values are 
       described in \secref{sec:library:objectmodel}.

    \item[nnbrs]
       The number of neighbors used in the edge- and vertex-pruning calculations.
       Note that in this routine, this variable does not control the number of
       neighbors in the graph.

    \item[mincmp]
       The size of the minimum connect component that will be pruned prior
       to clustering.

    \item[ntrials]
       Specifies the number of different clustering solutions to be computed. 
       The solution that achieves the best value of the criterion function is 
       the one that is returned. The value for {\em ntrials} must be greater 
       than zero. 

    \item[seed]
       The seed to be used by the random number generator. 

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

    \item[nclusters]
       The number of desired clusters.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[part]
       This is an array of size {\em nrows} that upon successful completion stores 
       the clustering vector of the matrix. The $i$th entry of this array stores
       the cluster number that the $i$th row of the matrix belongs to. Note that
       the numbering of the clusters starts from zero.
       The application is responsible for allocating the memory for this array.
       
       Under certain circumstances, \cluto may not be able to assign a particular 
       row to a cluster. In this case, the {\em part[]} entry of that particular 
       row will be set to -1. 
       
    \item[crvalue]
       This is a variable that upon returns stores the edge-cut of the clustering
       solution.
  \end{Lentry}

\item[{\bf\sf Returned Value}]\mbox{}\\
  Returns the number of clusters that it found. This number will be equal to 
  the number of desired clusters plus the number of connected components in
  the graph.
   

\item[{\bf\sf Note}]\mbox{}\\

\end{description}
\clearpage



%------------------------------------------------------------------------------
\subsubsection{CLUTO\_SA\_Cluster}
\begin{tabbing}
void {\sf\bf CLUTO\_SA\_Cluster} 
    \= (int nrows, int *rowptr, int *rowind, float *rowval, int crfun,\\
    \> int dbglvl, int nclusters, int *part, int *ptree, float *tsims, float *gains)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to cluster a matrix into a specified ($k$) number of clusters using 
   a hierarchical agglomerative clustering algorithm. Provides the functionality 
   of the {\em -clmethod=agglo} clustering method of the \scluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows]
       The number of rows of the input adjacency matrix whose rows store the 
       adjacency structure of the between-object similarity graph.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[crfun]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       
    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

    \item[nclusters]
       The number of desired clusters.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[part]
       This is an array of size {\em nrows} that upon successful completion stores 
       the clustering vector of the matrix. The $i$th entry of this array stores
       the cluster number that the $i$th row of the matrix belongs to. Note that
       the numbering of the clusters starts from zero.
       The application is responsible for allocating the memory for this array.
       
       Under certain circumstances, \cluto may not be able to assign a particular 
       row to a cluster. In this case, the {\em part[]} entry of that particular 
       row will be set to -1. 
       
    \item[ptree]
       This is an array of size {\em 2*nrows} that upon successful completion 
       stores the parent array of the binary hierarchical tree.  In this tree,
       each node corresponds to a cluster. The leaf nodes are the original {\em
       nrows} objects, and they are numbered from 0~to~{\em nrows}-1. The internal 
       nodes of the tree are numbered from {\em nrows} to 2*{\em nrows}-2. 
       The numbering of the internal nodes is performed so that smaller numbers 
       correspond to clusters obtained by merging a pair of 
       clusters earlier during the agglomeration process. The root of the tree 
       is numbered 2*{\em nrows}-2.

       The $i$th entry of the {\em ptree} array stores the parent node of the $i$
       node of the tree. The {\em ptree} entry for the root is set to -1.

       The application is responsible for allocating the memory for this array.
       
    \item[tsims]
       This is an array of size {\em 2*nrows} that upon successful completion 
       stores the average similarity between every pair of siblings in the induced 
       tree. In particular, {\em tsims[$i$]} stores the average pairwise
       similarity between the pair of clusters that are the children of the $i$th
       node of the tree. Note that the first {\em nrows} entries of this vector
       are not defined and are set to 0.0.

       The application is responsible for allocating the memory for this array.

    \item[gains]
       This is an array of size {\em 2*nrows} that upon successful completion 
       stores the gains in the value of the criterion function resulted by
       the merging pairs of clusters. In particular, {\em gains[$i$]} stores 
       the gain achieved by merging the clusters that are the children of the 
       $i$th node of the tree. Note that the first {\em nrows} entries of this 
       vector are not defined and are set to 0.0.

       The application is responsible for allocating the memory for this array.
  \end{Lentry}

\item[{\bf\sf Note}]\mbox{}\\
   Due to the high computational requirements of CLUTO\_SA\_Cluster, it should 
   only be used to cluster matrices that have fewer than 3,000--6,000 rows.

\end{description}
\clearpage




%------------------------------------------------------------------------------
\subsubsection{CLUTO\_V\_BuildTree}
\begin{tabbing}
void {\sf\bf CLUTO\_V\_BuildTree} 
           \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval, int simfun\\
           \> int crfun, int rowmodel, int colmodel, float colprune, int treetype,\\
           \> int dbglvl, int nclusters, int *part, int *ptree, float *tsims, float *gains)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Builds a hierarchical agglomerative tree that preserves the clustering
   solution supplied in the {\em part} array. It can build two types of trees. 
   The first type is a tree built on top of a particular clustering solution, 
   such that the leaves of the tree correspond to the different clusters. 
   This is the type of tree used when the {\em -showtree} option of \vcluster 
   is specified. The second type of tree is a complete agglomerative tree that 
   preserves the clustering. This is the type of tree used when the {\em -fulltree} 
   option of \vcluster is specified. The hierarchical agglomerative tree is 
   build so that it optimizes a particular clustering criterion function. 

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects to be clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun, crfun]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.

    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[treetype\hspace{10pt}]
       Specifies the type of tree that needs to be built. The possible values 
       for this parameter are:

       \begin{Ventry}{CLUTO\_TREE\_FULLX}{\bf}
         \item[CLUTO\_TREE\_TOP]  
               Builds a tree whose leaves correspond to the different clusters.

         \item[CLUTO\_TREE\_FULL] 
               Builds a complete tree that preserves the clustering solution.
       \end{Ventry}

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.


    \item[nclusters]
       The number of clusters in the supplied clustering solution.


    \item[part]
       An array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering 
       solution returned by \cluto's clustering routines. Note that the numbering 
       of the clusters starts from zero.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[ptree]
       An array whose size depends on the type of tree that is requested.

       If {\em treetype==CLUTO\_TREE\_TOP}, then it is of size {\em 2*nclusters} 
       that upon successful completion stores the parent array of the binary 
       hierarchical tree. In this tree, each node corresponds to a cluster. 
       The leaf nodes are the original {\em nclusters} clusters supplied via 
       the {\em part} array, and they are numbered from 0~to~{\em nclusters}-1. 
       The internal nodes of the tree are numbered from {\em nclusters} to 
       2*{\em nclusters}-2. The root of the tree is numbered 2*{\em nclusters}-2.

       If {\em treetype==CLUTO\_TREE\_FULL}, then it is of size {\em 2*nrows} 
       that upon successful completion stores the parent array of the binary 
       hierarchical tree. In this tree, each node corresponds to a cluster. 
       The leaf nodes are the original rows of the matrix, and they are numbered 
       from 0~to~{\em nrows}-1.  The internal nodes of the tree are numbered 
       from {\em nrows} to 2*{\em nrows}-2. The root of the tree is numbered 
       2*{\em nrows}-2.

       The numbering of the internal nodes is done in 
       such a fashion so that smaller numbers correspond to clusters obtained 
       by merging a pair of clusters earlier during the agglomeration process. 

       The $i$th entry of the {\em ptree} array stores the parent node of the $i$
       node of the tree. The {\em ptree} entry for the root is set to -1.

       The application is responsible for allocating the memory for this array.
       
    \item[tsims]
       An array whose size depends on the type of tree that is requested.
       If {\em treetype==CLUTO\_TREE\_TOP}, then it is of size {\em 2*nclusters} 
       and if {\em treetype==CLUTO\_TREE\_FULL} then it is of size {\em 2*nrows}.

       Upon successful completion stores the average similarity between every 
       pair of siblings in the induced tree. In particular, {\em tsims[$i$]} stores 
       the average pairwise similarity between the pair of clusters that are the 
       children of the $i$th node of the tree. Note that the first {\em nclusters} 
       or {\em nrows} entries of this vector are not defined and are set to 0.0.
       
       The application is responsible for allocating the memory for this array.

    \item[gains]
       An array whose size depends on the type of tree that is requested.
       If {\em treetype==CLUTO\_TREE\_TOP}, then it is of size {\em 2*nclusters}
       and if {\em treetype==CLUTO\_TREE\_FULL} then it is of size {\em 2*nrows}.

       Upon successful completion stores the gains in the value of the criterion 
       function resulted by the merging pairs of clusters. In particular, 
       {\em gains[$i$]} stores the gain achieved by merging the clusters that 
       are the children of the $i$th node of the tree. Note that the first 
       {\em nclusters} or {\em nrows} entries of this vector are not defined and 
       are set to 0.0.

       The application is responsible for allocating the memory for this array.
  \end{Lentry}

\item[{\bf\sf Note}]\mbox{}\\
   In order for this routine to build the accurate tree for a particular 
   clustering solution, the values for the {\em rowmodel}, {\em colmodel}, and 
   {\em colprune} parameters should be identical to those used to compute the 
   clustering solution.

   This routine can be used to build the hierarchical agglomerative tree with
   respect to any clustering criterion function regardless of the criterion 
   function used to compute the clustering solution.

\end{description}
\clearpage



%------------------------------------------------------------------------------
\subsubsection{CLUTO\_S\_BuildTree}
\begin{tabbing}
void {\sf\bf CLUTO\_S\_BuildTree} 
           \= (int nrows, int *rowptr, int *rowind, float *rowval, int crfun, int treetype, \\
           \> int dbglvl, int nclusters, int *part, int *ptree, float *tsims, float *gains)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Builds a hierarchical agglomerative tree that preserves the clustering
   solution supplied in the {\em part} array. It can build two types of trees. 
   The first type is a tree built on top of a particular clustering solution, 
   such that the leaves of the tree correspond to the different clusters. 
   This is the type of tree used when the {\em -showtree} option of \scluster 
   is specified. The second type of tree is a complete agglomerative tree that 
   preserves the clustering. This is the type of tree used when the {\em -fulltree} 
   option of \scluster is specified. The hierarchical agglomerative tree is 
   build so that it optimizes a particular clustering criterion function. 

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows]
       The number of rows of the input adjacency matrix whose rows store the 
       adjacency structure of the between-object similarity graph.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[crfun]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.

    \item[treetype\hspace{10pt}]
       Specifies the type of tree that needs to be built. The possible values 
       for this parameter are:

       \begin{Ventry}{CLUTO\_TREE\_FULLX}{\bf}
         \item[CLUTO\_TREE\_TOP]  
               Builds a tree whose leaves correspond to the different clusters.

         \item[CLUTO\_TREE\_FULL] 
               Builds a complete tree that preserves the clustering solution.
       \end{Ventry}

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

    \item[nclusters]
       The number of clusters in the supplied clustering solution.

    \item[part]
       An array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering 
       solution returned by \cluto's clustering routines. Note that the numbering 
       of the clusters starts from zero.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[ptree]
       An array whose size depends on the type of tree that is requested.

       If {\em treetype==CLUTO\_TREE\_TOP}, then it is of size {\em 2*nclusters} 
       that upon successful completion stores the parent array of the binary 
       hierarchical tree. In this tree, each node corresponds to a cluster. 
       The leaf nodes are the original {\em nclusters} clusters supplied via 
       the {\em part} array, and they are numbered from 0~to~{\em nclusters}-1. 
       The internal nodes of the tree are numbered from {\em nclusters} to 
       2*{\em nclusters}-2. The root of the tree is numbered 2*{\em nclusters}-2.

       If {\em treetype==CLUTO\_TREE\_FULL}, then it is of size {\em 2*nrows} 
       that upon successful completion stores the parent array of the binary 
       hierarchical tree. In this tree, each node corresponds to a cluster. 
       The leaf nodes are the original rows of the matrix, and they are numbered 
       from 0~to~{\em nrows}-1.  The internal nodes of the tree are numbered 
       from {\em nrows} to 2*{\em nrows}-2. The root of the tree is numbered 
       2*{\em nrows}-2.

       The numbering of the internal nodes is done in 
       such a fashion so that smaller numbers correspond to clusters obtained 
       by merging a pair of clusters earlier during the agglomeration process. 

       The $i$th entry of the {\em ptree} array stores the parent node of the $i$
       node of the tree. The {\em ptree} entry for the root is set to -1.

       The application is responsible for allocating the memory for this array.
       
    \item[tsims]
       An array whose size depends on the type of tree that is requested.
       If {\em treetype==CLUTO\_TREE\_TOP}, then it is of size {\em 2*nclusters} 
       and if {\em treetype==CLUTO\_TREE\_FULL} then it is of size {\em 2*nrows}.

       Upon successful completion stores the average similarity between every 
       pair of siblings in the induced tree. In particular, {\em tsims[$i$]} stores 
       the average pairwise similarity between the pair of clusters that are the 
       children of the $i$th node of the tree. Note that the first {\em nclusters} 
       or {\em nrows} entries of this vector are not defined and are set to 0.0.
       
       The application is responsible for allocating the memory for this array.

    \item[gains]
       An array whose size depends on the type of tree that is requested.
       If {\em treetype==CLUTO\_TREE\_TOP}, then it is of size {\em 2*nclusters}
       and if {\em treetype==CLUTO\_TREE\_FULL} then it is of size {\em 2*nrows}.

       Upon successful completion stores the gains in the value of the criterion 
       function resulted by the merging pairs of clusters. In particular, 
       {\em gains[$i$]} stores the gain achieved by merging the clusters that 
       are the children of the $i$th node of the tree. Note that the first 
       {\em nclusters} or {\em nrows} entries of this vector are not defined and 
       are set to 0.0.

       The application is responsible for allocating the memory for this array.
  \end{Lentry}

\item[{\bf\sf Note}]\mbox{}\\
   In order for this routine to build the accurate tree for a particular 
   clustering solution, the values for the {\em rowmodel}, {\em colmodel}, and 
   {\em colprune} parameters should be identical to those used to compute the 
   clustering solution.

   This routine can be used to build the hierarchical agglomerative tree with
   respect to any clustering criterion function regardless of the criterion 
   function used to compute the clustering solution.

\end{description}
\clearpage


%=========================================================================
\subsection{Graph Creation Routines}
\label{sec:library:graphs}

%------------------------------------------------------------------------------
\subsubsection{CLUTO\_V\_GetGraph}
\begin{tabbing}
int {\sf\bf CLUTO\_V\_GetGraph} 
       \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval,\\
       \> int simfun, int rowmodel, int colmodel, float colprune, int grmodel, \\
       \> int nnbrs, int dbglvl, int **growptr, int **growind, float **growval)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to create a nearest-neighbor graph of the set of objects. This is graph
   can be used as input to the graph-partitioning based clustering algorithm
   (CLUTO\_SP\_GraphClusterRB).

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects to be clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun]
       The method used to compute the similarity between objects, whose meaning 
       and possible values are described in \secref{sec:library:clparams:simfun}.
       
    \item[rowmodel, colmodel, grmodel, colprune]
       The object modeling parameters whose meaning and possible values are 
       described in \secref{sec:library:objectmodel}.

    \item[nnbrs]
       The number of neighbors of each object that will be used to create the
       nearest neighbor graph.

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[growptr, growind, growval]
       These are three arrays storing the computed graph in the CSR matrix
       format. Memory for these arrays are allocated within \cluto's library.
       However, the application is responsible for freeing this memory.
  \end{Lentry}


\item[{\bf\sf Note}]\mbox{}\\

\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_S\_GetGraph}
\begin{tabbing}
int {\sf\bf CLUTO\_S\_GetGraph} 
       \= (int nrows, int *rowptr, int *rowind, float *rowval, int grmodel, \\
       \> int nnbrs, int dbglvl, int **growptr, int **growind, float **growval)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Used to create a nearest-neighbor graph of the set of objects. This is graph
   can be used as input to the graph-partitioning based clustering algorithm
   (CLUTO\_SP\_GraphClusterRB).

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows]
       The number of rows of the adjacency matrix (\ie., the number of vertices in
       the graph).

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[grmodel]
       The type of graph to be constructed. The meaning and possible values 
       are described in \secref{sec:library:objectmodel}.
       
    \item[nnbrs]
       The number of neighbors of each object that will be used to create the
       nearest neighbor graph.

    \item[dbglvl]
       The debugging parameter whose meaning and possible values are described
       in \secref{sec:library:debug}.

  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[growptr, growind, growval]
       These are three arrays storing the computed {\em nrows}-vertex graph in 
       the CSR matrix format. Memory for these arrays are allocated within 
       \cluto's library. However, the application is responsible for freeing 
       this memory.
  \end{Lentry}


\item[{\bf\sf Note}]\mbox{}\\

\end{description}
\clearpage


%=========================================================================
\subsection{Cluster Statistics Routines}
\label{sec:library:stats}

%------------------------------------------------------------------------------
\subsubsection{CLUTO\_V\_GetSolutionQuality}
\begin{tabbing}
float {\sf\bf CLUTO\_V\_GetSolutionQuality} 
          \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval, int simfun,\\
          \> int crfun, int rowmodel, int colmodel, float colprune, int nclusters, int *part)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Returns the value of a particular criterion function for a given clustering solution. 

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects that were clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun, crfun]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       
    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[nclusters]
       The number of clusters in the supplied clustering solution.

    \item[part]
       An array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering solution
       returned by \cluto's clustering routines. Note that the numbering of the 
       clusters starts from zero.
       
  \end{Lentry}

\item[{\bf\sf Returned Value}]\mbox{}\\
   This function returns the value of the clustering criterion function of the 
   supplied clustering solution. Please refer to \cite{zhao01tr-vpcluster} for 
   the exact definitions of these criterion functions.

\item[{\bf\sf Note}]\mbox{}\\
   This routine can be used to find the value of any clustering criterion function
   regardless of the criterion function used to compute the clustering solution.
   

\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_S\_GetSolutionQuality}
\begin{tabbing}
float {\sf\bf CLUTO\_S\_GetSolutionQuality} 
          \= (int nrows, int *rowptr, int *rowind, float *rowval, int crfun, \\
          \> int nclusters, int *part)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Returns the value of a particular criterion function for a given clustering solution. 

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows]
       The number of rows and columns of the input matrix whose rows store the 
       objects that were clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[crfun]
       The clustering parameters whose meaning and possible values are described
       in \secref{sec:library:clparams}.
       
    \item[nclusters]
       The number of clusters in the supplied clustering solution.

    \item[part]
       An array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering solution
       returned by \cluto's clustering routines. Note that the numbering of the 
       clusters starts from zero.
       
  \end{Lentry}

\item[{\bf\sf Returned Value}]\mbox{}\\
   This function returns the value of the clustering criterion function of the 
   supplied clustering solution. Please refer to \cite{zhao01tr-vpcluster} for 
   the exact definitions of these criterion functions.

\item[{\bf\sf Note}]\mbox{}\\
   This routine can be used to find the value of any clustering criterion function
   regardless of the criterion function used to compute the clustering solution.
   

\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_V\_GetClusterStats}
\begin{tabbing}
void {\sf\bf CLUTO\_V\_GetClusterStats} \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval,\\
                                         \> int simfun, int rowmodel, int colmodel, float colprune, int nclusters, \\
                                         \> int *part, int *pwgts, float *cintsim, float *cintsdev, float *izscores, \\
                                         \> float *cextsim, float *cextsdev, float *ezscores)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Returns a number of statistics about a given clustering solution.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects that were clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun]
       The clustering similarity function whose meaning and possible values are 
       described in \secref{sec:library:clparams:simfun}.
       
    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[nclusters]
       The number of clusters in the supplied clustering solution.

    \item[part]
       An array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering 
       solution returned by \cluto's clustering routines. Note that the numbering 
       of the clusters starts from zero.
       
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[pwgts]
       An array of size {\em nclusters} that returns the sizes of the different 
       clusters. In particular, the size of the $i$th cluster is returned in pwgts[$i$].
       The application is responsible for allocating the memory for this array.

    \item[cintsim]
       An array of size {\em nclusters} that returns the average similarity between
       the objects assigned to each cluster. In particular, the average similarity between 
       the objects of the $i$th cluster is returned in cintsim[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[cintsdev]
       An array of size {\em nclusters} that returns the standard deviation of the
       average similarity between each object and the other objects in its own cluster.
       In particular, the standard deviation of the $i$th cluster is returned in cintsdev[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[izscores]
       An array of size {\em nrows} that returns the internal $z$-scores of each
       object. The internal $z$-score of the $i$th object is returned in izscores[$i$]. 
       The internal $z$-score of each object is described in the discussion of the
       {\em -zscores} option of \vcluster.
       The application is responsible for allocating the memory for this array.

    \item[cextsim]
       An array of size {\em nclusters} that returns the average similarity 
       between the objects of each cluster and the remaining objects. In particular, 
       the average {\em external} similarity of the objects of the $i$th cluster is 
       returned in cextsim[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[cextsdev]
       An array of size {\em nclusters} that returns the standard deviation
       of the average external similarities of each object. In particular, the 
       {\em external} standard deviation of the objects of the $i$th cluster is 
       returned in cextsdev[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[ezscores]
       An array of size {\em nrows} that returns the external $z$-scores 
       of each object. The external $z$-score of the $i$th object is returned in 
       ezscores[$i$].  The external $z$-score of each object is described in the 
       discussion of the {\em -zscores} option of \vcluster.
       The application is responsible for allocating the memory for this array.

  \end{Lentry}


\item[{\bf\sf Note}]\mbox{}\\
   The various values for the {\em simfun}, {\em rowmodel}, and {\em colmodel} 
   parameters are defined in {\tt cluto.h}, and this header file must be included 
   in all programs that use \cluto's library. 

   In order for this routine to get the accurate statistics for a particular 
   clustering solution, the values for the {\em rowmodel}, {\em colmodel}, and 
   {\em colprune} parameters should be identical to those used to compute the 
   clustering solution.
   
\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_S\_GetClusterStats}
\begin{tabbing}
void {\sf\bf CLUTO\_S\_GetClusterStats} 
       \= (int nrows, int *rowptr, int *rowind, float *rowval, int nclusters, \\
       \> int *part, int *pwgts, float *cintsim, float *cintsdev, float *izscores, \\
       \> float *cextsim, float *cextsdev, float *ezscores)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Returns a number of statistics about a given clustering solution.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows]
       The number of rows and columns of the input matrix whose rows store the 
       objects that were clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[nclusters]
       The number of clusters in the supplied clustering solution.

    \item[part]
       An array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering 
       solution returned by \cluto's clustering routines. Note that the numbering 
       of the clusters starts from zero.
       
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[pwgts]
       An array of size {\em nclusters} that returns the sizes of the different 
       clusters. In particular, the size of the $i$th cluster is returned in pwgts[$i$].
       The application is responsible for allocating the memory for this array.

    \item[cintsim]
       An array of size {\em nclusters} that returns the average similarity between
       the objects assigned to each cluster. In particular, the average similarity between 
       the objects of the $i$th cluster is returned in cintsim[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[cintsdev]
       An array of size {\em nclusters} that returns the standard deviation of the
       average similarity between each object and the other objects in its own cluster.
       In particular, the standard deviation of the $i$th cluster is returned in cintsdev[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[izscores]
       An array of size {\em nrows} that returns the internal $z$-scores of each
       object. The internal $z$-score of the $i$th object is returned in izscores[$i$]. 
       The internal $z$-score of each object is described in the discussion of the
       {\em -zscores} option of \vcluster.
       The application is responsible for allocating the memory for this array.

    \item[cextsim]
       An array of size {\em nclusters} that returns the average similarity 
       between the objects of each cluster and the remaining objects. In particular, 
       the average {\em external} similarity of the objects of the $i$th cluster is 
       returned in cextsim[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[cextsdev]
       An array of size {\em nclusters} that returns the standard deviation
       of the average external similarities of each object. In particular, the 
       {\em external} standard deviation of the objects of the $i$th cluster is 
       returned in cextsdev[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[ezscores]
       An array of size {\em nrows} that returns the external $z$-scores 
       of each object. The external $z$-score of the $i$th object is returned in 
       ezscores[$i$].  The external $z$-score of each object is described in the 
       discussion of the {\em -zscores} option of \vcluster.
       The application is responsible for allocating the memory for this array.

  \end{Lentry}


\item[{\bf\sf Note}]\mbox{}\\
   
\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_V\_GetClusterFeatures}
\begin{tabbing}
void {\sf\bf CLUTO\_V\_GetClusterFeatures} 
              \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval,\\
              \> int simfun, int rowmodel, int colmodel, float colprune, int nclusters, \\
              \> int *part, int nfeatures, int *internalids, float *internalwgts, \\
              \> int *externalids, float *externalwgts)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Returns the set of features that best describe and discriminate
   each one of the clusters of a given clustering solution.
   It provides the functionality of the {\em -showfeatures} option of the 
   \vcluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects that were clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun]
       The clustering similarity function whose meaning and possible values are 
       described in \secref{sec:library:clparams:simfun}.

    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[nclusters]
       The number of clusters in the supplied clustering solution.

    \item[part]
       This is an array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering 
       solution returned by \cluto's clustering routines. Note that the numbering 
       of the clusters starts from zero.
       
    \item[nfeatures]
       The number of descriptive and discriminating features that is desired.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[internalids]
       An array of size {\em nclusters*nfeatures} that returns the column
       numbers of the {\be descriptive} features. The set of features of the $i$th 
       cluster are stored in the {\em internalids} array starting at location 
       $i*\mbox{\em nfeatures}$ up to location (but excluding) 
       $(i+1)*\mbox{\em nfeatures}$. The set of features for each cluster are
       returned in decreasing importance order. The numbering of the returned 
       columns starts from zero. 
       The application is responsible for allocating the memory for this array.

    \item[internalwgts]
       An array of size {\em nclusters*nfeatures} that returns the weight
       of each one of the descriptive features returned in the {\em internalids}
       array. The weight of the features stored in the $i$th location of the
       {\em internalids} array is returned in the $i$th location of the {\em
       internalwgts} array. The weights are numbers between 0.0 and 1.0 and 
       represent the fraction of the within cluster similarity that each
       particular feature is responsible for. 
       The application is responsible for allocating the memory for this array.

    \item[externalids]
       This is an array of size {\em nclusters*nfeatures} that returns the column
       numbers of the {\be discriminating} features. The set of features of the 
       $i$th cluster are stored in the {\em externalids} array starting at location 
       $i*\mbox{\em nfeatures}$ up to location (but excluding) 
       $(i+1)*\mbox{\em nfeatures}$. The set of features for each cluster are
       returned in decreasing importance order. The numbering of the returned 
       columns starts from zero.
       The application is responsible for allocating the memory for this array.

    \item[externalwgts]
       This is an array of size {\em nclusters*nfeatures} that returns the weight
       of each one of the discriminating features returned in the {\em externalids}
       array. The weight of the features stored in the $i$th location of the
       {\em externalids} array is returned in the $i$th location of the {\em
       externalwgts} array. The weights are numbers between 0.0 and 1.0 and 
       represent the fraction of the  dissimilarity between the cluster and the
       rest of the objects that each particular feature is responsible for. 
       The application is responsible for allocating the memory for this array.


  \end{Lentry}


\item[{\bf\sf Note}]\mbox{}\\
   The various values for the {\em simfun}, {\em rowmodel}, and {\em colmodel} 
   parameters are defined in {\tt cluto.h}, and this header file must be included 
   in all programs that use \cluto's library. 

   In order for this routine to get the accurate set of features for a particular 
   clustering solution, the values for the {\em rowmodel}, {\em colmodel}, and 
   {\em colprune} parameters should be identical to those used to compute the 
   clustering solution.
   
\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_V\_GetClusterSummaries}
\begin{tabbing}
void {\sf\bf CLUTO\_V\_GetClusterSummaries} 
              \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval,\\
              \> int simfun, int rowmodel, int colmodel, float colprune, int nclusters, \\
              \> int *part, int sumtype, int nfeatures, int *r\_nsum, int **r\_spid, \\
              \> float **r\_swgt, int **r\_sumptr, int **r\_sumind)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Returns sets of features that frequently co-occur within the objects of each cluster.
   It provides the functionality of the {\em -showsummaries} option of the \vcluster 
   program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects that were clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun]
       The clustering similarity function whose meaning and possible values are 
       described in \secref{sec:library:clparams:simfun}.

    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[nclusters]
       The number of clusters in the supplied clustering solution.

    \item[part]
       This is an array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering 
       solution returned by \cluto's clustering routines. Note that the numbering 
       of the clusters starts from zero.
       
    \item[sumtype\hspace{10pt}]
       Specifies the type of summaries that needs to be computed. The possible values 
       for this parameter are:

       \begin{Ventry}{CLUTO\_SUMTYPE\_MAXITEMSETSXX}{\bf}
         \item[CLUTO\_SUMTYPE\_MAXCLIQUES]  
               Returns the features that form maximal cliques in the feature-to-feature
               co-occurrence graph.

         \item[CLUTO\_SUMTYPE\_MAXITEMSETS]  
               Returns the features that occur frequently in the objects of each cluster.
               A frequent itemset is returned if it is maximal or if its frequency is 
               much higher than the frequency of its maximal itemsets.
       \end{Ventry}

    \item[nfeatures]
       The number of the most descriptive features for which the summarization will be performed.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[r\_nsum]
       This is the number of discovered summaries.

    \item[r\_spid, r\_swgt, r\_sumptr, r\_sumind]
       This is a set of four arrays that store information about the discovered summaries.
       Since the number of summaries is dataset and clustering-solution dependent, \cluto
       allocates memory for these arrays internally, and returns them to the application.
       This is why all of these arrays are ``**''. The application is responsible for
       deallocating the memory for these arrays.

       The {\em r\_spid} and {\em r\_swgt} arrays are of size {\em r\_nsum} and each 
       entry of these arrays is associated with the $i$th summary. In particular,
       {\em r\_spid[i]} stores the cluster number that the $i$th summary belongs too,
       and {\em r\_swgt[i]} stores a weight associated with that summary. If the
       summaries were computed using the {\em maxcliques} option, this weight represents
       the density of the features in the clique. If the summaries were computed using
       the {\em maxitemsets} option, this weight represents the support of the corresponding
       itemset.

       The arrays {\em r\_sumptr} and {\em r\_sumind} store the actual features of the
       various summaries. The {\em r\_sumptr} array is of size {\em r\_nsum+1} and the
       features of the $i$th summary is stored in {\em r\_sumind} starting at location
       {\em r\_sumptr[i]} up to (but not including) location {\em r\_sumptr[i+1]}.

  \end{Lentry}


\item[{\bf\sf Note}]\mbox{}\\
   The various values for the {\em simfun}, {\em rowmodel}, and {\em colmodel} 
   parameters are defined in {\tt cluto.h}, and this header file must be included 
   in all programs that use \cluto's library. 

   This routine will produce meaningful results only for sparse and high-dimensional
   datasets.
   
\end{description}
\clearpage




%------------------------------------------------------------------------------
\subsubsection{CLUTO\_V\_GetTreeStats}
\begin{tabbing}
void {\sf\bf CLUTO\_V\_GetTreeStats} 
                    \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval,\\
                    \> int simfun, int rowmodel, int colmodel, float colprune, int nclusters,\\
                    \> int *part, int *ptree, int *pwgts, float *cintsim, float *cextsim)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Returns a number of statistics about the clusters corresponding to
   the different nodes of the hierarchical agglomerative tree.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects that were clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun]
       The clustering similarity function whose meaning and possible values are 
       described in \secref{sec:library:clparams:simfun}.

    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[nclusters]
       The number of clusters in the supplied clustering solution.

    \item[part]
       An array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering 
       solution returned by \cluto's clustering routines. Note that the numbering 
       of the clusters starts from zero.
       
    \item[ptree]
       An array of size {\em 2*nclusters} that was populated by the 
       CLUTO\_V\_BuildTree routine.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[pwgts]
       An array of size {\em 2*nclusters} that returns the sizes of the clusters
       corresponding to the various nodes of the tree. In particular, the size of the cluster
       corresponding to the $i$th tree-node is returned in pwgts[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[cintsim]
       An array of size {\em 2*nclusters} that returns the average similarity between
       the objects assigned to each cluster. In particular, the average similarity between 
       the objects of the cluster corresponding to the $i$th tree-node is returned in cintsim[$i$]. 
       The application is responsible for allocating the memory for this array.

    \item[cextsim]
       An array of size {\em 2*nclusters} that returns the average similarity 
       between the objects of each cluster and their sibling cluster in the tree. 
       In particular, the average {\em external} similarity of the objects of the 
       $i$th cluster is returned in cextsim[$i$]. Note that each pair of sibling
       clusters will have the same {\em cextsim} value.
       The application is responsible for allocating the memory for this array.

  \end{Lentry}


\item[{\bf\sf Note}]\mbox{}\\
   The various values for the {\em simfun}, {\em rowmodel}, and {\em colmodel} 
   parameters are defined in {\tt cluto.h}, and this header file must be included 
   in all programs that use \cluto's library. 

   In order for this routine to get the accurate statistics for a particular 
   clustering solution, the values for the {\em rowmodel}, {\em colmodel}, and 
   {\em colprune}, {\em nclusters}, {\em part}, and {\em ptree} parameters should 
   be identical to those used to compute the clustering solution and build the
   hierarchical agglomerative tree.
   
\end{description}
\clearpage


%------------------------------------------------------------------------------
\subsubsection{CLUTO\_V\_GetTreeFeatures}
\begin{tabbing}
void {\sf\bf CLUTO\_V\_GetTreeFeatures} 
              \= (int nrows, int ncols, int *rowptr, int *rowind, float *rowval,\\
              \> int simfun, int rowmodel, int colmodel, float colprune, int nclusters, \\
              \> int *part, int *ptree, int nfeatures, int *internalids, float *internalwgts, \\
              \> int *externalids, float *externalwgts)
\end{tabbing}


\noindent
\begin{description}
\item[{\bf\sf Description}]\mbox{}\\
   Returns the set of features that best describe and discriminate
   each one of the clusters corresponding to the various nodes of the hierarchical 
   agglomerative tree that was built on top of the clustering solution. It provides 
   the functionality of the {\em -labeltree} option of the \vcluster program.

\item[{\bf\sf Input Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[nrows, ncols]
       The number of rows and columns of the input matrix whose rows store the 
       objects that were clustered.

    \item[rowptr, rowind, rowval]
       The matrix itself in the format described in \secref{sec:library:csr}.

    \item[simfun]
       The clustering similarity function whose meaning and possible values are 
       described in \secref{sec:library:clparams:simfun}.

    \item[rowmodel, colmodel, colprune]
       The object modeling parameters whose meaning and possible values are described
       in \secref{sec:library:objectmodel}.

    \item[nclusters]
       The number of clusters in the supplied clustering solution.

    \item[part]
       An array of size {\em nrows} that stores the clustering solution.
       The $i$th entry of this array stores the cluster number that the $i$th row 
       of the matrix belongs to. This array should correspond to a clustering 
       solution returned by \cluto's clustering routines. Note that the numbering 
       of the clusters starts from zero.
       
    \item[ptree]
       An array of size {\em 2*nclusters} that was populated by the 
       CLUTO\_V\_BuildTree routine.

    \item[nfeatures]
       The number of descriptive and discriminating features that is desired.
  \end{Lentry}

\item[{\bf\sf Output Parameters}]\mbox{}\\
  \vspace{-20pt} 
  \begin{Lentry}
    \item[internalids]
       An array of size {\em 2*nclusters*nfeatures} that returns the column
       numbers of the {\be descriptive} features. The set of features of the cluster
       corresponding to the $i$th tree node are stored in the {\em internalids} array 
       starting at location $i*\mbox{\em nfeatures}$ up to location (but excluding) 
       $(i+1)*\mbox{\em nfeatures}$. The set of features for each cluster are
       returned in decreasing importance order. The numbering of the returned 
       columns starts from zero.
       The application is responsible for allocating the memory for this array.

    \item[internalwgts]
       An array of size {\em 2*nclusters*nfeatures} that returns the weight
       of each one of the descriptive features returned in the {\em internalids}
       array. The weight of the features stored in the $i$th location of the
       {\em internalids} array is returned in the $i$th location of the {\em
       internalwgts} array. The weights are numbers between 0.0 and 1.0 and 
       represent the fraction of the within cluster similarity that each
       particular feature is responsible for. 
       The application is responsible for allocating the memory for this array.

    \item[externalids]
       An array of size {\em 2*nclusters*nfeatures} that returns the column
       numbers of the {\be discriminating} features. The discriminating features
       are defined within the context of the pair of clusters that are the children
       of the same tree node. Consequently, there are no discriminating features
       for the root node of the tree. The set of features of the cluster corresponding 
       to the $i$th tree node are stored in the {\em externalids} array starting at 
       location $i*\mbox{\em nfeatures}$ up to location (but excluding) 
       $(i+1)*\mbox{\em nfeatures}$. The set of features for each cluster are returned 
       in decreasing importance order. The numbering of the returned columns starts 
       from zero.
       The application is responsible for allocating the memory for this array.

    \item[externalwgts]
       An array of size {\em 2*nclusters*nfeatures} that returns the weight
       of each one of the discriminating features returned in the {\em externalids}
       array. The weight of the features stored in the $i$th location of the
       {\em externalids} array is returned in the $i$th location of the {\em
       externalwgts} array. The weights are numbers between 0.0 and 1.0 and 
       represent the fraction of the  dissimilarity between the cluster and the
       rest of the objects that each particular feature is responsible for. 
       The application is responsible for allocating the memory for this array.


  \end{Lentry}


\item[{\bf\sf Note}]\mbox{}\\
   The various values for the {\em simfun}, {\em rowmodel}, and {\em colmodel} 
   parameters are defined in {\tt cluto.h}, and this header file must be included 
   in all programs that use \cluto's library. 

   In order for this routine to get the accurate set of features for a particular 
   clustering solution, the values for the {\em rowmodel}, {\em colmodel}, and 
   {\em colprune}, {\em nclusters}, {\em part}, and {\em ptree} parameters should 
   be identical to those used to compute the clustering solution and build the
   hierarchical agglomerative tree.
   
\end{description}
\clearpage









%*************************************************************************
\section{System Requirements and Contact Information}
\label{sec:epiloge}

\cluto is written in ANSI~C and has been extensively tested under Linux,
Solaris, and Windows. At this point \cluto's distribution is only in a 
binary format, as it is actively under development. However, we expect
to make the source code available in future releases.

Even though, \cluto contains no known bugs, it does not mean that all of 
its bugs have been found and fixed. If you find any problems, please send 
email to {\em karypis@cs.umn.edu\/}, with a brief description of the problem 
you have found.  Also, any future updates to \cluto will be made available 
on WWW at {\em http://www.cs.umn.edu/\~{}karypis/cluto\/}.


%*************************************************************************
\section{Copyright Notice and Usage Terms}
\label{sec:copyright}

The \cluto package is copyrighted by the Regents of the University of
Minnesota. It can be freely used for educational and research purposes
by non-profit institutions and US government agencies only. Other
organizations are allowed to use \cluto only for evaluation purposes,
and any further uses will require prior approval. The software
may not be sold or redistributed without prior approval. One may
make copies of the software for their use provided that the copies,
are not sold or distributed, are used under the same terms and
conditions.

As unestablished research software, this code is provided on an
``as is'' basis without warranty of any kind, either expressed or
implied. The downloading, or executing any part of this software
constitutes an implicit agreement to these terms. These terms and
conditions are subject to change at any time without prior notice.



%*************************************************************************
{
\small
\bibliographystyle{plain}
\bibliography{/home/fac05/karypis/work/bibliography/all}
}



\end{document}
