

\section{Text Mining}

\subsection{Overview}

Generally speaking, text mining is the process of extracting interesting and usable information 
from bodies of text, stored in an unstructured format.  It has been estimated that
approximately 80\% of information is stored as unstructured text \cite{grimes80rule08} which, if  
examined properly, could yield new patterns of data previously unknown.
  The basic process typically calls for taking
as input, a collection of text documents, effectively processing these documents into a storage mechanism
(data structures, databases, file structures, etc.), examining the stored documents computationally, and
lastly outputting some new information previously unknown about the set of documents. The field has a basis
ranging from machine learning, 
data mining, artificial intelligence, information retrieval, statistics, natural language processing
 and linguistics but does not necessarily
have to employ all of these sub-fields at once.  Common tasks used construct this new information include
document clustering and term/dimensionality reduction which are examined in this thesis, but can also
include, concept location \cite{saggion00}, text categorization \cite{sebastiani02}, 
part-of-speech tagging \cite{halterenPosTagging01}, and text summarization \cite{Ahmad.etal.03}.

\subsection{Fundamental Concepts}

\subsubsection{Documents and Terms}

At the core of any text mining task is the notion of documents and their terms.  
Documents, in this case, are the set of all term collections in a given corpus.
A document can represent numerous types of unstructured text such as company 
memos, emails, news articles, source code, legal documents, etc.  
The terms are then the set of all unique words that appear in these documents.
Heaps' Law tells us that the growth rate of the term space, or vocabulary, is approximately
equivalent to the square root of the total number of words in the document set \cite{grootjenHeapsLaw03}.
While this does mean that vocabulary grows a sub-linear rate with respect to the number
of occurrences, the size of the vocabulary is still large enough to cause scalability
concerns.

\subsubsection{The Vector Space Model}

The vector space model (VSM) is a algebraic construct used for nearly 
every text mining algorithm.  It was first introduced by Gerald Salton
at Cornell University in the 1960s \cite{salton.SMART.91} and has been a cornerstone
of IR in text (and later text mining) ever since.  The VSM defines each document as a vector
in the space of all terms where each dimension refers to a specific term.
Each value stored in the document vector represents the rate of occurrence
of the corresponding term, commonly referred to as the term weight.
  While a number of computations can be used
for the term weight the most common
is the term frequency-inverse document frequency model 
(see section \ref{b:tfidf} below).  

This approach allows the ability
to produce similarity scores of the likeness of one document to another using
common vector difference/similarity functions such as cosine similarity.  
Additionally, it provides a framework for more advanced methods such as
latent semantic indexing (LSI) and principal component analysis (PCA).
However, there are drawbacks to the VSM such as high dimensionality
of the term space, the loss of word ordering, and no representation
of the similarity between words with similar meanings but different
words.




\subsubsection{TF*IDF}
\label{b:tfidf}
In order to perform mathematical operations and algorithms on documents 
and the text that they contain, we must first transform them into a 
representative mathematical object.  The standard representation of a 
document is a vector in the space of all available terms.  For example, the phrase:

\begin{equation}\label{eq:latent}
{\scriptsize
\begin{array}{r@{}c@{~}l}
The\: quick\: brown\: dog\: was\: very\: \\
quick,\: very\: brown,\: and\: very\: dog\: like.\\
\end{array}}
\end{equation}
Will be turned into a vector which looks something like this:
\begin{equation}\label{eq:latent1}
{\scriptsize
\begin{array}{r@{}c@{~}l}
Phrase = [1\:2\:2\:2\:1\:3\:1\:1]
\end{array}}
\end{equation}
with each index of the above vector corresponding the a dimension which comes from the term list (in this case, 
the dimensions are {the, quick, brown, dog, was, very, like})

Tf*Idf is shorthand for ``term frequency times inverse document
frequency.'' This calculation models the intuition that jargon
usually contains technical words that appear a lot, but only in a
small number of paragraphs.  For example, in a document describing
a space craft, the terminology relating to the power supply may 
appear frequently in the sections relating to power, but nowhere
else in the document.

Calculating Tf*Idf is a relatively simple matter:
\bi
\item
Let there be $Words$ number of documents;
\item
Let some word $I$ appear $Word[I]$ number of times inside a set of $Documents$; 
\item
Let $Document[I]$ be the documents containing $I$.
\ei
Then:
\[
Tf*Id = Word[i]/Words*log(Documents/Document[i])
\]


\subsection{Linear Preprocessing Tricks}
\label{b:preprocessing}

Aside from the more intensive and complex reduction methods described later on,
there are also several known preprocessing tricks that can reduce the size of
the set of all possible terms.  Three of these are listed below.


\subsubsection{Tokenization}
In HAMLET's parser,
words are reduced to simple tokens via (e.g.) removing all punctuation remarks, then sending all upper case to lower.


\subsubsection{Stop lists}
Another way to reduce dimensionality is to remove ``dull'' words via a 
{\em stop list}
of ``dull'' words. \fig{stop} shows a sample of the stop list used in HAMLET.
\fig{stop} shows code for a stop-list function.
\begin{figure}[!h]
\begin{alltt}\scriptsize
a           about    across   again      against
almost      alone    along    already    also
although    always   am       among      amongst
amongst     amount   an       and        another
any         anyhow   anyone   anything   anyway
anywhere    are      around   as         at
...         ...      ...      ...        ...  
\end{alltt}
\caption[Stop words]{24 of the 262 stop words used in this study.}\label{fig:stop}
\end{figure}

\subsubsection{Stemming}
Terms with a common stem will
usually have similar meanings. For example, all these words relate to the same concept.
\bi
\item
        CONNECT
    \item    CONNECTED
     \item   CONNECTING
     \item   CONNECTION
     \item   CONNECTIONS
\ei
Porter's stemming algorithm~\cite{porter80}
 is the standard stemming tool. It repeatedly replies a set of pruning rules to the end of words until
the surviving words are unchanged. The pruning rules ignore the semantics of a word and just perform syntactic pruning (e.g. \fig{stem1}).

\input{figures/stemming}


Porter's stemming algorithm has been coded in any 
number of languages\footnote{\url{http://www.tartarus.org/martin/PorterStemmer}} such as the Perl {\em stemming.pl}
used in this study.


\section{Technical Document Comprehension}

\subsection{Overview}
Technical document comprehension (also referred to as program comprehension)
 focuses on learning patterns and hidden details in 
collections of technical documents.  While the majority of work being done in technical 
document comprehension is based on evaluating source code, other types of documents
can be explored as well.  Legal documents \cite{rose89}, UML \cite{hayes03}, and even HTML \cite{nie99}
have all been explored using standard IR and text mining techniques.  The potential benefit
of focusing on technical documents is utilizing the inherent structure that is found in them
to build previously unknown relationships.  Ideally, once these new relationships are combined
with existing knowledge gained through text mining, results can greatly improve.  In the
next few sections I will examine a few existing tools for technical document comprehension
in the realm of software engineering.


\subsection{HIPIKAT}
Hipikat \cite{hipikat} by Cubranic and Murphy is an attempt at a
collective project memory, developed as plug-in for the Eclipse
development environment.  It works by bringing in textual information from 
CVS repositories, change requests (issue reports, feature requests, etc),
communication channels (forum posts, emails, etc.), design documents, 
and other software engineering artifacts found on the projects website.
Hipikat analyses these documents and can infer links between artifacts
pertaining to a similar subject.  For instance, if a bug was marked as
fixed in the issue tracker and within a given time-frame, a CVS check-in
was submitted, a possible link can exist between these two
artifacts.  As new artifacts are submitted to Hipikat, they are
examined for potential links and the entire collection is updated.
What is created is a network of linked artifacts which, when combined
with a similarity analysis of the text in each node, can be used
to provide fine-tuned artifact recommendations.  When using the
tool, a developer can either perform a keyword search through the
Hipikat database or query Hipikat by selecting an artifact in the IDE,
such as a source code file, CVS submission, or bug report.  In
both instances, a list of suggested articles is presented which
can then be used for further Hipikat queries, or opened for viewing.
While Hipikat has been shown to aid newcomers to a project with
grasping a general understanding of a codebase, its downfall is
the scalability issue.  Hipikat uses LSI (section \ref{b:LSI}) to perform
similarity tests between documents which is costly in both
space and time.  In addition to performance issues when working
with larger collections, there are also concerns with the quality
of the recommendations as larger collections tend to be more
heterogeneous in nature.


\subsection{Dora the Program Explorer}
Dora is, like Hipikat, also an Eclipse plug-in that tackles the same
problem of finding similar code artifacts based on an initial artifact.
Unlike Hipikat which uses communication channels, issue reports, etc. to 
build its searchable repository, Dora only uses Java methods.  As a result
of only using methods, the relationships between nodes in Dora is of a more
syntactic nature since they are generated from call graphs, where a relationship
exists between two methods if one calls the other. Using only call graphs
in large software projects is not the most effective approach given that
there are many neighboring functions and many of those that are of little reference
to the seed method.  This is where the term similarity between methods is used 
to help trim down the neighborhood.  Dora uses a series of similarity comparisons
including TFIDF \ref{b:tfidf} that is then
 combined using a linear model to generate a similarity measure between
methods that is then used to build a relevant neighborhood.  When computing
a similarity measure between two methods, Dora will consider if the method
is a binary method taken from a library combined with TFIDF similarity 
between method names, identifiers used in the method body, and the
natural language in code comments.  To help reduce these term sets
even further, Dora employs some of the preprocessing tricks mentioned
in section \ref{b:preprocessing} such as stemming.



\subsection{STEP/EXPRESS}
\label{b:step}

STEP (Standard for the Exchange of Product model data) is an ISO specified \cite{ISO10303}
 language used to represent product manufacturing
information.  The goal a mechanism capable of describing 
production data from the entire life-cycle of a product.
independent of any specific system or methods the product employs.  This yields
transferability between existing software and machine systems. 
By nature, this makes it useful not only for 
a neutral file format, but also as a starting point for creating 
and sharing product databases and archiving. All STEP files must conform to a
 schema defined in the EXPRESS language.  Essentially, EXPRESS is
a data modeling language that defines the structure of STEP documents and
STEP documents are EXPRESS schemas instantiated.  The ISO has defined a number
of these schemas, known as {\em application protocols}.  See \fig{aps} for the list
of currently defined APs.


In theory, there is nothing stopping STEP/EXPRESS from
recording and storing
all aspects of a project.  In many ways, STEP/EXPRESS is
as expressive as other technical document standards (e.g. UML).
STEP/EXPRESS offers a generic method for storing part-of and is-a
information, constraints, types, and the rules associated with a
technical document.
However,
in practice, the theoretical potential of STEP/EXPRESS is not realized for
the following reasons.
 
\subsubsection{Heterogeneity}

The reality of archival
systems is that  STEP/EXPRESS documents
are stored {\em along side} a much larger set of supporting documents in multiple formats.
Given this, if we can learn how to understand large heterogeneous collections
that include
STEP/EXPRESS knowledge as well as numerous other products
in a wide
variety of formats,
it would be possible to reason and learn from a very wide range of
data.

A majority of the work has focused on the creation
of cached sets of EXPRESS schemas. Forty such {\em application protocols} (AP) have been defined~\cite{jardim06}
including 
AP-203 (for geometry)
and AP-213 (for numerical control).  The list of currently defined application protocols
is very extensive (see \fig{aps}).
These APs are the cornerstone of STEP tools: the tools offer specialized support and screen
 import/export facilities for the APs.
While much effort went into their creation of these APs, very few have been stress-tested
in the information systems field. That is, the majority of these APs have 
been {\em written} more than they have
been {\em read} (exceptions:  the above-mentioned AP-203 and AP-213 are frequently used and reused in 
$21^{st}$ century CAD/CAM manufacturing processes),


Perhaps because of the relative immaturity of the APs, current
CAD/CAM tools offer limited support for the STEP APs. While most tools support geometry (AP-203), the
support for the other  APs in \fig{aps} is minimal.
 

\subsubsection{Limited Historical Use}
For all the above reasons, highly structured technical documents in formats like STEP/EXPRESS
are in the minority in the archival systems
we have examined.  We are aware of large STEP/EXPRESS repositories
but these are often inaccessible for a variety
of reasons.

While this situation might change in the future (e.g. if
all the above issues were suddenly fixed and all organizations switch to using highly
structured technical documentation), the historical record would still be starved
for large numbers of examples.

\begin{figure}
\begin{center}
\begin{tabular}{ll}
AP & area\\\hline
201  &   	Explicit Drafting\\
202  &   	Associative Drafting\\
203  &   	Configuration Controlled Design\\
204  &   	Mechanical Design Using Boundary Representation\\
205  &   	Mechanical Design Using Surface Representation\\
206  &   	Mechanical Design Using Wireframe Representation\\
207  &   	Sheet Metal Dies and Blocks\\
208  &   	Life Cycle Product Change Process\\
209  &   	Design Through Analysis of Composite and Metallic Structures\\
210  &   	Electronic Printed Circuit Assembly, Design and Manufacturing\\
211  &   	Electronics Test Diagnostics and Remanufacture\\
212  &   	Electrotechnical Plants\\
213  &   	Numerical Control Process Plans for Machined Parts\\
214  &   	Core Data for Automotive Mechanical Design Processes\\
215  &   	Ship Arrangement\\
216  &   	Ship Molded Forms\\
217  &   	Ship Piping\\
218  &   	Ship Structures\\
219  &   	Dimensional Inspection Process Planning for CMMs\\
220  &   	Printed Circuit Assembly Manufacturing Planning\\
221  &   	Functional Data and Schematic Representation for Process Plans\\
222  &   	Design Engineering to Manufacturing for Composite Structures\\
223  &   	Exchange of Design and Manufacturing DPD for Composites\\
224  &   	Mechanical Product Definition for Process Planning\\
225  &   	Structural Building Elements Using Explicit Shape Rep\\
226  &   	Shipbuilding Mechanical Systems\\
227  &   	Plant Spatial Configuration\\
228  &   	Building Services\\
229  &   	Design and Manufacturing Information for Forged Parts\\
230  &   	Building Structure frame steelwork\\
231  &   	Process Engineering Data\\
232  &   	Technical Data Packaging\\
233  &   	Systems Engineering Data Representation\\
234  &   	Ship Operational logs, records and messages\\
235  &   	Materials Information for products\\
236  &   	Furniture product and project\\
237  &   	Computational Fluid Dynamics\\
238  &   	Integrated CNC Machining\\
239  &   	Product Life Cycle Support\\
240  &   	Process Planning\\
\end{tabular}
\end{center}
\caption{STEP Application Protocols.}\label{fig:aps} 
\end{figure}


\section{Term Reduction}


\subsection{Principal Component Analysis (PCA)}
Principal component analysis (PCA) is a mathematical method rooted
in the singular value decomposition of a matrix to infer
correlation from a large set of previously uncorrelated variables \cite{jolliffe}.
The  new set of variables is of a much smaller size which could prove useful for
reducing run-times of complex and time-demanding computations.  PCA is
is distinct in that is the optimal linear transformation for keeping
the subspace which has the largest variance.   For example,
in figure \ref{fig:pca}, PCA is performed on the two dimensional plot on the
left and the result shows the new one dimensional plot which best diplays
the variance in the data.

\begin{figure}[!b]
\label{fig:pca}
\begin{center}
\includegraphics[angle=270,width=2in]{figures/pca.pdf}
\end{center}
\caption[PCA: example]{The two features in the left plot can be transferred to the right plot via one latent feature.}
\end{figure}


The resulting subspace
has been shown to be highly beneficial when clustering with K-Means due
to the fact that it is identical to the cluster centroid subspace specified
by the between-class scatter matrix, which is where the global solution of K-Means 
lies \cite{ding04}.  Despite this, PCA is the most computationally complex
reduction algorithm being tested in this study and is not usable in most
applications due to its non-scalability.

\subsection{Latent Semantic Indexing (LSI)}
\label{b:LSI}

Latent semantic indexing (LSI) is a dimensionality reduction method that has been in use for text mining 
purposes since the early 1980s and was first introduced
at Bell laboratories \cite{lsi90}.
LSI is similar to PCA in that they both have a basis in the 
singular value decomposition (SVD) of a matrix.  The main difference between LSI and PCA is that
PCA performs SVD on a covariance matrix, while LSI performs SVD on a term-document matrix.
LSI has the benefit of being independent of language because of its purely
mathematical nature. 
This allows LSI to use the co-occurrence of terms to identify topics and concepts
without the use of the semantic interpretations of these words.

Like PCA however, LSI's downfall is in its exponential run-time.  Despite its
ability to provide very useful results in text-mining, it is still unusable in
most applications due to its issue with scalability.  Although Tang, Dwarkadas, and Xu 
\cite{tang04} have demonstrated a method of improving scalability
with LSI.

\subsection{FastMap}

The general goal of FASTMAP is to project items in a $n$ dimensional to a $d$ dimensional space,
with $n$ $>$ $d$.  
The basis of each reduction is using the cosine law on the triangle formed by
an object in the feature space and the two objects that are furthest apart in
the current (pre-reduction) space (see~\fig{fm1}).  These two objects are referred to as the pivot
objects of that step in the reduction phase ($n$ - $d$ total pivot object sets).  Finding
the optimal solution of the problem of finding the two furthest apart points is a $N^2$ problem 
(where $N$ is the total number of objects), but this is where the heuristic nature of FASTMAP comes
into play.  

Instead of finding the absolute furthest apart points, \newline
FASTMAP takes a shortcut by first randomly
selecting an object from the set, and then finding the object that is furthest from it and setting
this object as the first pivot point.  After the first pivot point is selected, FASTMAP finds the 
points farthest from this and uses it as the second pivot point.  The line formed by these two
points becomes the line that all of the other points will be mapped to in the new $n$ - 1 dimension
space. 

\begin{figure}
\begin{center}
\includegraphics[width=200pt]{figures/fastmap1.png}
\end{center}
\caption{Example of using the cosine law to find the position of $Oi$ in
the dimension $k$}
\label{fig:fm1}
\end{figure}


\begin{figure}
\begin{center}
\includegraphics[width=200pt]{figures/fastmap2.png}
\end{center}
\caption{Projects of points $O_i$ and $O_j$ onto the hyper-plane perpendicular to the line $O_a$$O_b$}
\label{fig:fm2}
\end{figure}


\subsection{TF*IDF Term Ranking}

TF*IDF term ranking is linear time approach to reducing dimensionality in text
mining datasets.  It is a simple algorithm created to benchmark the results of 
PCA and FastMap for the purposes of the study.  Its basis is the idea that the
TF*IDF value of a word represents that words importance in the context of the dataset.
The algorithm work by summing the TF*IDF scores of each term across all documents and then
returning the $n$ terms with the highest summed values.  See figure \ref{fig:tfidfTerms} for 
a sample of key terms returned by TF*IDF term raking on one of our STEP datasets.  

\begin{figure}[!h]
\begin{alltt}\scriptsize
cartesian_point   type        oriented_edge   subtype         entity
label             sizeof      self            query           select
name              direction   edge_curve      where           wr1
text              real        set             not             description
for               rule        items           typeof          supertype
...               ...         ...             ...             ...  
\end{alltt}
\caption[Key Terms]{30 of the 100 key terms found in a STEP dataset using TF*IDF ranking}\label{fig:tfidfTerms}
\end{figure}

One drawback to this method 
is that it requires a much larger value for $n$ to be used effectively.  The value
for $n$ must be large enough to encompass any term which later will be used to query 
the dataset later.  Also, as the value of $n$ decreases, the dataset will become 
increasingly homogeneous and many documents will be represented as nearly identical to
completely different documents within the collection.  However, the drastic
difference in run-time of this method is very appealing, especially given the
non-scalable nature of PCA and LSI.  


\section{Document Clustering}

\subsection{Hierarchical vs. Well-Separated}

\subsection{K-Means (elementary)}

K-Means is a clustering algorithm that, when given a dataset of unidentified objects, it will 
group those items into $k$ groups based on some given similarity measure. 
The algorithm is described in \fig{kmeans}. For an example
of the algorithm in operation, see \fig{keg}.

\begin{figure}[!h]
\begin{tabular}{|p{\linewidth}|}\hline
\bi
\item
i=0
\item
Partitioning the input points into k initial sets, either at random or using some heuristic data.
\item Repeat
unitl ($i \le maxIterations$ or no point changes set membership)
\bi
\item  Calculates the mean point, or centroid, of each set or cluster.
\item  Constructs a new partition, by associating each point with the closest centroid.
\item  Recalculate the centroids for the newly partitioned cluster
\item  i = i + 1
\ei
\ei
\\\hline
\end{tabular}
\caption[The K-means algorithm]{K-Means algorithm. See \fig{keg} for an example of this algorithm running in
practice.}\label{fig:kmeans}
\end{figure}

\begin{figure}
\centering
{\scriptsize{
\begin{tabular}{|p{0.3\linewidth}|p{0.3\linewidth}|} 
\hline
	\subfloat[Randomly select cluster centroids ]{
		\includegraphics{figures/120px-K_Means_Example_Step_1.png}
	} & 

	\subfloat[Assign each object to it's nearest centroid]{
		\includegraphics{figures/120px-K_Means_Example_Step_2.png}
	} \\\hline

	\subfloat[ Compute new centroids by using the mean value from 
			the centroids picked in step (b)]{
		\includegraphics{figures/120px-K_Means_Example_Step_3.png}
	} & 
	\subfloat[Repeat steps (b) and (c) until the convergence 
			criteria has been reached]{
		\includegraphics{figures/120px-K_Means_Example_Step_4.png}
	} \\\hline
\end{tabular}
}}
\caption[Steps of KMeans Illustrated]{ Figures (a) through () above illustrate the
	major steps of the  kmeans algorithm}
\label{fig:kmeansSteps}
\end{figure}

While k-means may be sufficiently accurate, there are significant drawbacks.  Most notably is the speed (or lack thereof).  
Due to the k-means algorithm having to compute distances from every item to every cluster.  In situations where the cosine 
similarity distance measure is used, computing the distance between points can be an expensive operation (this is another place dimensionality reduction helps out).
In recent tests comparing clustering algorithm run-times, k-means was found to be up to 500 times slower than another algorithm, 
GENIC, which we discuss further down.

Another problem with k-means is determining what value of 
$k$ should be used.  Note the usability issues
with requiring a user to pre-specify $k$:
isn't this the kind of tedious detail
that  the computer should be telling us?  



\subsection{K-Means (canopied)}

The canopy clustering algorithm is an unsupervised clustering algorithm built on top of K-Means.  Its primary claim is the increased speed when working with large datasets.  With large enough datasets K-Means can be utterly useless.  Canopy clustering allows us to use these algorithms with a marginal loss of accuracy for magnitudes of improvements in run time.  Its processes is based on two key steps.  First, in a preprocessing step partition items into canopies based on similarity.  This first step has to be done with a minimalist approach in order to keep the operation lightweight.  To facilitate this, a very cheap distance measure is used.  Typically this distance metric is tied to the domain.  In this study, our cheap distance metric was number of similar words in two documents.  After this set of canopies is generated, K-Means continues as normal with one exception, only use the more expensive similarity measure on items belonging to the same canopy.  The basic steps of the algorithm are listed below.

\input{figures/canopies}


\bi
\item Begin with a set of points and remove one at random. Create a Canopy containing this point and iterate through the remainder of the point set.
\item At each point, if its distance from the first point is < T1, then add the point to the cluster. If, in addition, the distance is < T2, then remove the point from the set. This way points that are very close to the original will avoid all further processing. The algorithm loops until the initial set is empty, accumulating a set of Canopies, each containing one or more points.

\ei

 


\subsection{Genic}

GENIC is a generalized incremental clustering algorithm developed by Gupta and Grossman \cite{Gupta04} that 
provides potentials for large improvements in scalability over K-Means. Since GENIC was designed with streaming 
data in mind, it only has a single pass through the data to work with.  Because of this, it scales linearly, which 
is a requirement when dealing with large corpora.  By using stochastic methods, GENIC can be given an initial k 
equal to the number of items (each item is its own clusters) and prune away unlikely clusters with each generation,
giving a realistically estimated value for k after the last generation.  Here is how GENIC works:

\begin{enumerate}
\item \textbf{Select parameters}
\bi
\item Fix the number of centers $k$.
\item Fix the number of initial points $m$.
\item Fix the size of a generation $n$.
\ei

\item \textbf{Initialize}
\bi
\item Select $m$ points, $c_1, ..., c_m$ to be the initial candidate centers.
\item Assign a weight of $w_i$ = 1 to each of these candidate centers.
\ei

\item \textbf{Incremental Clustering} For each subsequent data point $p$ in the stream: do
\bi
\item $Count$ = $Count$ + 1
\item Find the nearest candidate center $c_i$ to the point $p$
\item Move the nearest candidate center using the formula \\
\begin{equation}
{c_i = \frac{(w_i * c_i + p}{w_i + 1} }
\end{equation}
\item Increment the corresponding weight \\
\begin{equation}
{w_i = w_i + 1}
\end{equation}
\item When $Count$ $mod$ $n$ = 0, goto Step 4
\ei

\item \textbf{Generational Update of Candidate Centers} \\
When $Count$ equals $n, 2n, 3n$, ..., for every \\
center $c_i$ in the list L of centers, do:
\bi
\item Calculate its probability of survival using the formula \\
\begin{equation}
{p_i = \frac{w_i}{\sum_{i=1}^n w_i}}
\end{equation}
\item Select a random number $\delta$ uniformly from [0,1]. If $p_i$ > $\delta$, retain the center $c_i$
in the list L of centers and use it in the next generation to replace it as a center in the list L
of centers.
\item Set the weight $w_i$ = 1 back to one.  Although some of the points in the stream will be implicitly assigned
to other centers now, we do not use this information to update any of the other existing weights.
\item Goto step 3 and continue processing the input stream
\ei

\item \textbf{Calculate Final Clusters} The list L contains the $m$ centers. These $m$ centers
can be grouped into the final $k$ centers based on their Euclidean distances.

\end{enumerate}

GENIC is of specific interest to HAMLET for two primary reasons, low expected run-times on large corpora and a
potential ability at estimating the number of natural clusters in the collection.
\bi
\item
Scalability:
 Since 
GENIC was designed with streaming data in mind, it only has a single pass through the data to work with.  Because of this,
it scales linearly, which is a requirement if HAMLET is to
scale to large corpora.
\item
An likely estimate for $k$:
 Because of GENIC's stochastic based method of removing unwanted or non-useful clusters, it has potential for use in correctly
estimating a good value for $k$.  By eliminating "bad stuff", GENIC can ideally identify the correct number of types of "good stuff".
\ei


\subsection{Computing the number of clusters}

\section{Distance Metrics}

\subsection{Euclidean}

\subsection{Manhattan}

\subsection{Cosine}

\section{Opportunities for Improvements}

