\documentclass[11pt]{article}
\usepackage{dimacsmodules}

\setlength{\topmargin}{0in}     % top of paper to head (less one inch)
\setlength{\headheight}{0in}    % height of the head
\setlength{\headsep}{0in}       % head to the top of the body
\setlength{\textheight}{9.00in} % height of the body
\setlength{\oddsidemargin}{0mm} % left edge of paper to body (less one inch)
\setlength{\evensidemargin}{0mm} % ditto, even pages
\setlength{\textwidth}{6.5in}   % width of body
\setlength{\topskip}{0in}       % top of body to bottom of first line of text
%\setlength{\footheight}{0.25in} % height of footer
%\setlength{\footskip}{0.50in}   % bottom of text to bottom of foot


\newtheorem{them}{Theorem}[section]
\newtheorem{lem}[them]{Lemma}
\newtheorem{cor}[them]{Corollary}
\newtheorem{prop}[them]{Proposition}
\newtheorem{ex}{Example}[section]
\newtheorem{remark}{Remark}[section]

\newcommand{\sk}{\medskip}
\newcommand{\pinch}{\vspace{-9pt}}

\begin{document}

\begin{publicity}{}

\begin{center}
\vspace{.4in}
{\Large \bf DIMACS EDUCATIONAL MODULE SERIES}

\vspace{1.0in}

{\Large \bf MODULE 03-1}\\
{\Large \bf Introduction to Clustering Algorithms:}\\
{\large \bf Hierarchical Clustering}\\
{\large \bf Date prepared: March 17, 2003}

\vspace{.5in}

{\bf Alexander Kheyfits} \footnote{Supported by the National Science Foundation (Grant DUE 9752776)} \\
{\bf Bronx Community College of the City University of New York}\\
{\bf University Avenue at 181st Street, Bronx, NY 10453}\\
{\bf email: alexander.kheyfits@bcc.cuny.edu}\\
%\vspace{.15in}

\end{center}
\vfill

\end{publicity}

\newpage

\begin{center}
{\Large \bf DIMACS EDUCATIONAL MODULE SERIES\\ [2mm]
Description of Module 03-1}
\end{center}

\begin{itemize}
\item[] {\bf Title:}

{\large \textbf{Introduction to Clustering Algorithms:
 Hierarchical Clustering}}


\item[] {\bf Author:}

Alexander Kheyfits

\item[]

{\bf Abstract:} Clustering algorithms separate (partition)
discrete data sets into disjoint groups-clusters, such that every
cluster contains only the elements close to each other in a
precisely defined sense. These procedures are widely used in
mathematical taxonomy, management, and many other applications of
mathematics. In this module we discuss the simplest and commonly
used hierarchical algorithms for clustering --- Hubert's
single-link and complete-link algorithms. These algorithms are
called hierarchical because they build up an hierarchy of larger
and larger clusters. The algorithms are based on the properties of
a graph describing an initial collection of objects, and the terms
{\em single-link}, {\em complete-link} refer to the methods of
combining two subgraphs in one larger subgraph.

\sk The module is aimed at freshman and sophomore students
studying finite mathematics, introductory discrete mathematics, or
statistics. So, only a minimal, high-school background in
mathematics is assumed. In particular, we do not expect any
knowledge of graph theory or probability theory. All relevant
graph-theoretical definitions (like spanning trees, etc.) are
discussed and illustrated by examples. The algorithms considered
are simple and can be examined in an introductory computer science
course. We do not perform any
formal analysis of the algorithms, however we present them in a
pseudocode form. The module can be used in the classroom
and for the students' projects.

\sk
It is supposed that after active studying the module and
working the included exercises, the reader

%\sk
\begin{itemize}
\item[$\bullet$] will learn some basic concepts of graph theory together
with their simple applications,

\sk
\item[$\bullet$] will learn basic concepts of cluster theory and clustering
algorithms,

\sk
\item[$\bullet$] will be able to apply these algorithms for clustering small
(since we do not discuss any software issues) arrays of data,

\sk
\item[$\bullet$] will have enough background to learn and apply computer software for
clustering real data,

\sk
\item[$\bullet$] will be able to study more advanced literature on classification and
clustering.
\end{itemize}


\item[] {\bf Informal Description:}

In this module we discuss how to split a set of different objects
into several groups of more or less similar entities. For example,
when a manager of a big supermarket decides where to place various
goods, she has to solve a problem of cluster analysis. Cluster analysis
is used in any field concerned with classification of data. Examples are
numerical taxonomy, design of the Internet, classification of natural
languages, or image processing, to name just a few. The readers
of the module will learn how to form clusters step by step, first in
an informal way,
considering a model example, and then using some simple graph
theory. These necessary concepts of the graph theory are also
introduced in the module. In the last section a real case study is
considered.

\item[] {\bf Target Audience:}

The module is aimed at freshman and sophomore students studying
finite mathematics, introductory discrete mathematics, or
statistics. It may be used by well-motivated high-school students.


\item[] {\bf Prerequisites:}

Only a minimal, high school background in mathematics is assumed.
In particular, we do not expect any knowledge of graph theory or
probability theory. All relevant graph-theoretical concepts, such
as spanning trees, are discussed and illustrated by examples. The
algorithms considered are simple and can be examined in an
introductory computer science course.  We do no formal analysis
of the algorithms, however we
present them in a standard pseudocode form.

\item[] {\bf Mathematical Field:}

Graph theory; Classification theory; Cluster analysis.


\item []{\bf Applications Areas:}

Classification theory; Mathematical and biological taxonomy.

\item[] {\bf Mathematics Subject Classification:}

 MSC (2000) Primary 91C20; Secondary 05C90, 90B80, 92B10.

\item[] {\bf Contact Information:}

  Alexander Kheyfits \\
 Dept. of Math. and Computer Science \\
  Bronx Community College/CUNY \\
 University Avenue at W. 181st Street \\
  Bronx, NY 10453

  Tel.: (718) 289-5616 \\
 E-mail:  alexander.kheyfits@bcc.cuny.edu


\item[] {\bf Other DIMACS modules related to this module:}

None as of this writing.

\end{itemize}


\end{document}
