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

% Version started on 2/6/2004. MFJ
% Taken from varnew1.tex. Corrected addresses. 

\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{\pinch}{\vspace{-9pt}}

\begin{document}
\pagenumbering{roman}
\begin{publicity}{}

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

\vspace{.7in}

{\Large \bf MODULE 03-7}\\
{\Large \bf A Gentle Introduction to Mathematical Cluster Analysis}\\
{\large \bf September, 2003}

\vspace{.3in}

{\bf Harel Barzilai}\\
{\bf Department of Mathematics and Computer Science}\\
{\bf Salisbury University}\\
{\bf Salisbury MD 21801}\\
{\bf phone: 410-543-6472}\\
{\bf email: hxbarzilai@salisbury.edu}\\
{\bf harel@barzilai.org}

\vspace{.15in}

{\bf Alexander Kheyfits}\\
{\bf Depatment of Mathematics and Computer Science}\\
{\bf Bronx Community College (CUNY)}\\
{\bf University Avenue at W. 181st Street}\\
{\bf Bronx, NY 10453}\\
{\bf phone: 718-289-5616}\\
{\bf email: alexander.kheyfits@bcc.cuny.edu}

\vspace{.15in}

{\bf Kathy Andrews}\\
{\bf Hillsdale College}\\
{\bf Department of Mathematics}\\
{\bf 33 E. College}\\
{\bf Hillsdale, MI 49242}\\
{\bf email: kjandrews42@comcast.net} 

\end{center}
\vfill

\end{publicity}

\newpage

\begin{center}
{\large \bf Module Description Information}
\end{center}

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

A Gentle Introduction to Mathematical Cluster Analysis

\item {\bf Author(s):}

Harel Barzilai, Department of Mathematics and Computer Science, Salisbury University

Alexander Kheyfits, Department of Mathematics and Computer Science,
Bronx Community College (CUNY)

Kathy Andrews, Department of Mathematics, Hillsdale College

\item {\bf Abstract:}

Mathematical Clustering or Cluster Analysis is a field which endeavors
to "classify". More precisely, given a discrete data set, this set is
classified into groupings, or clusters. The criteria for what makes a
"good" set of such clusters vary, however in general we want similar
data points to be made part of the same cluster, and data points
assigned to different clusters should have some important
features distinguishing them.

The basics notions and definitions of clustering are introduced, as
well as key algorithms used in the field, including the notion of a
"hierarchical" algorithm. The first chapter provides an overview of
the field as well as an introduction to "Agglomerative" hierarchical
algorithms; the second chapter describes "Divisive" hierarchical
algorithms; and the third chapter introduces Sequential clustering
algorithms.

A section of print References is provided for further exploration, as
well as as a section of Web References Cited (with full URLs), and
additionally an online page, "Online Resources for Further
Exploration" is available from the DIMACS page with sections on
Tutorials, Sample Applications, Researchers with Expertise,  and 
Software.

\item {\bf Informal Description:}

The types of algorithms surveyed in this module are listed in the
Abstract.

Prospective readers may be interested to note that the wide variety of
areas of application of this field include: business planning as well
as public, city and regional planning such as choosing the
locations for hospitals; taxonomic classification of species;
classification of chemical molecules into types; and even web pages
classified together as being of similar relevance to a search, or of
similar interest to a reader.

Students who complete this module will have been introduced to the
fundamentals of clustering through an informal and intuitive approach
which takes the reader gradually into the full formal definitions and
algorithms. They will also glimpse some of the applications of this
area, and will be provided with ample references for further study of
both applications, and the mathematical field of cluster analysis
itself.

\item {\bf Target Audience:}

This module is meant to be an "entry level" introduction for freshmen
and sophomore students. It can be used in Finite Mathematics, Discrete
Mathematics and Applied Mathematics courses, as well as in "Survey of
Mathematics" courses for strongly motivated liberal arts students. It
can also serve for guided self-study by mathematically inclined high
school students. The module may also be of interest in beginning
computer science courses, particularly courses with sections which
focus on algorithms

\item {\bf Prerequisites:}

The formal prerequisites include only high school mathematics through
algebra and functions or precalculus. Graph theory is not assumed,
and all but he most basic set-theoretic notation is defined within the
module itself.

\item {\bf Mathematical Field:}

Cluster analysis; Classification theory; Graph theory

\item {\bf Applications Areas:}

Classification theory; Biological, Chemical, and Ecological taxonomy
and classification; Data Mining; Internet analysis and search engine
algorithms.

\item {\bf Mathematics Subject Classification:}

Primary 91C20

Secondary 05C90, 90B80,92B10

\item {\bf Contact Information:}

Harel Barzilai\\Department of Mathematics and Computer Science\\Salisbury University\\
Salisbury MD 21801\\410-543-6472\\hxbarzilai@salisbury.edu, harel@barzilai.org

Alexander Kheyfits\\Department of Mathematics and Computer Science\\
Bronx Community College (CUNY)\\University Avenue at W. 181st Street\\
Bronx, NY 10453\\718-289-5616\\alexander.kheyfits@bcc.cuny.edu

Kathy Andrews\\Hillsdale College\\Department of Mathematics\\33 E. College\\
Hillsdale, MI 49242\\301-552-6429\\keandrews@dmci.net

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

Module 03-1 by Alex Kheyfits.

(There may be others of which we are not yet aware)

\end{itemize}
\newpage

\setcounter{page}{0}
\pagenumbering{arabic}
\tableofcontents

\newpage
\section*{ABSTRACT}
\addcontentsline{toc}{section}{Abstract}
Mathematical Clustering or Cluster Analysis is a field which endeavors
to "classify". More precisely, given a discrete data set, this set is
classified into groupings, or clusters. The criteria for what makes a
"good" set of such clusters vary, however in general we want similar
data points to be made part of the same cluster, and data points
assigned to different clusters should have some important
features distinguishing them.

The basics notions and definitions of clustering are introduced, as
well as key algorithms used in the field, including the notion of a
"hierarchical" algorithm. The first chapter provides an overview of
the field as well as an introduction to "Agglomerative" hierarchical
algorithms; the second chapter describes "Divisive" hierarchical
algorithms; and the third chapter introduces Sequential clustering
algorithms.

A section of print References is provided for further exploration, as
well as as a section of Web References Cited (with full URLs), and
additionally an online page, "Online Resources for Further
Exploration" is available from the DIMACS page with sections on
Tutorials, Sample Applications, Researchers with Expertise,  and 
Software.

\newpage
\setcounter{section}{-1}
\section{Preface}
Our intended audience for this module are students at the freshman and
sophomore level taking a General Education or Liberal Arts mathematics
class. Accordingly, only a minimal, high-school background in
mathematics is assumed. It is likewise assumed that most of these
students will not major in the mathematical sciences, while
recognizing that a many will enter fields which utilize mathematical
thinking and tools.

Hence, our dual goals are that the minority which may enter a field in
the mathematical sciences will be encouraged by this module to explore
clustering beyond this initial introduction, and that all students
expand their mathematical and analytical thinking skills, and
appreciation for the usefulness and relevance of mathematics --
particularly mathematical modeling.

Philosophically and pedagogically our aims are to foster through
examples, applications, and references an appreciation that
mathematics

\begin{list}
{\roman{enumi}}{\usecounter{enumi}}
\item is \emph{alive}: that there is active, current research going on 

\item is \emph{useful}: that this research concerns questions that
people, including non-mathematicians, very much care about

\item is \emph{interesting} (as suggested by the gallery of examples) and 

\item is a \emph{creative process} that non-specialists, including
non-mathematicians, can engage in, and gain an appreciation for.
\end{list}

The intent is also to motivate and possibly entice the more
mathematically inclined minority of Liberal Arts students (after
having us whet their appetites with this module) to consider further
mathematical explorations, be they in clustering, or in the broader
world of mathematics. May you find mathematical adventure for your
classroom in the pages that follow!

\section{Overview and Agglomerative Clustering} 
\subsection{Introduction}

Suppose you are taking a university class which includes a long-term project 
as an assignment. You are to work in small groups on this project, and most of 
your group meetings will be held outside of class. Your professor, being 
kindhearted and thoughtful, wishes to choose group assignments in a fair way 
which will help you be successful. 

\textbf{\flushleft Pause for reflection:}
At a non-residential university, what factors should the professor consider? \\
(before reading on, stop here and take a moment to make up your own list of important factors). 

\medskip
One of the most natural criteria your instructor might use is geography, 
namely where you and your classmates live, and more precisely, how far apart 
you live from one another. By ``far apart'' we mean something more involved 
than distance, however. For example, it takes more time to travel 5 miles on 
a small road than on a fast highway. Other complicating issues are that parking
costs may vary, and that the time spent waiting to switch from one bus or 
subway line to another depends on how many such switches are required. For 
our purposes, we will assume overall \emph{travel costs}
have been determined for getting from one student's home to that of a 
classmate's. 

\begin{quote}
[Comment: some students may be familiar with the Triangle Inequality for 
distances: that the sum of the lengths of two sides of a triangle is greater 
than or equal to the length of the third side. It must be cautioned however 
that in this example, the Triangle Inequality does not hold since you will be 
using travel costs rather than simply physical distances. The general case in 
'clustering problems' discussed in this module is that the Triangle Inequality
will not hold; it will hold only in special cases of clustering]. 
\end{quote}


Since your groups will need to meet many times outside of class, it would be a
good idea to choose project groups (or 'clusters') in such a way that students
who are in the same group live relatively ``close'' together (or at least not 
too ``far'' apart) in terms of the overall travel costs between pairs of 
students in the same group. 


Now let's consider how your instructor might go about selecting project groups
according to this criterion. Put yourself in the role of the instructor and 
think about how you might best accomplish the task of selecting the groups. 


To be concrete, let us suppose that five students in class have chosen the 
same topic, but that project groups can only have two or three members each. 
Let's say that the five students are named Anna, Brian, Chris, Deborah, and 
Ethan, to whom we will refer by their first initials: A, B, C, D, and E. 


Your task is to divide this set of five students into two project groups. 
Since groups with more than three or fewer than two members are not allowed, 
it follows that you need to create, out of the initial set of five students, 
two project groups: one group with two members, and one with three members.  


\subsubsection {Matrix Matters: Visualizing our data}

Suppose now that the travel costs between the respective dorm rooms or 
apartments of our five students are as indicated in the following chart 
(Table 1): 


\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline 
Student & & & & &\\
\hline
A &0 &1 &8 &5 &4 \\
B &1 &0 &10 &6 &7 \\
C &8 &10 &0 &2 &9 \\
D &5 &6 &2 &0 &3 \\
E &4 &7 &9 &3 &0 \\
\hline
\textbf{Travel cost to:} &A &B &C &D &E  \\
 \hline 
\end{tabular}
\end{center}
\caption{Travel costs between pairs of students}
\end{table}


Notice the diagonal line of zeros in our chart: this is because the travel 
cost from A to A (that is, our ``travel cost'' if we start at Anna's place 
and our intended destination is also Anna's place) is zero: clearly, we don't 
need to travel at all in this case! Similarly, the table has a 0 for the travel
cost from B to B, C to C, and so on. Notice that rows are listed in the same 
order as columns, and that this natural ordering is the reason behind the zeros
always lying on a diagonal as we've noticed. In fact, there are other patterns 
in the above chart. 


\textbf{\flushleft Pause for reflection:}
Before reading on, can you describe in writing what other patterns you see? 


An important feature in the chart is its symmetry. Notice that there is a 
mirror-like aspect to the arrangement of numbers in our chart: it has two 
symmetric halves, separated by the diagonal of zeros we've observed. Do you 
see it? Furthermore, can you say and then write down in precise terms what 
this symmetry is, explaining in precise terms \emph{why}
this symmetry is present? Before reading on, take a moment or two to carefully
describe this symmetry (\emph{Suggestion: } 
thinking in terms of rows versus columns may help). 


What we've found in the chart is more than just a visually pleasing pattern 
however; just as there was a reason and interpretation behind the diagonal 
of zeros (the travel cost incurred if your starting point and destination are 
the same, is zero), likewise there is a reason and a physical interpretation 
behind the symmetry of two complementary halves in our table of travel costs. 


\textbf{\flushleft Pause for reflection:}
What interpretation of the table of travel costs explains specifically this symmetry? 


Suppose we use the notation $d_{CD}$ to represent the travel cost from Chris' 
place to Deborah's. According to our chart, $d_{CD}$=2. Making the reasonable 
assumption that in our case travel routes and their associated costs are the 
same in both directions, the travel costs from Chris' place to Deborah's place
is equal to that from Deborah's place to Chris' place. It follows that in our 
notation, $d_{CD} = d_{DC}$

\begin{quote}
[Comment: to avoid unnecessary complications at this point, we assume travel 
distances are equal in both directions. For towns with one-way streets one 
would have often had $d_{xy} \not = d_{yx}$ where $d_{xy}$ is the driving 
distance from x to y ]. 
\end{quote}



Similarly, we know that $d_{AB} = d_{BA}$ and so forth. If you look at how 
the rows and columns are arranged and find the pair $d_{AB}$ and $d_{BA}$ 
on the chart, and similarly locate the spots where the pair $d_{CD}$ and 
$d_{DC}$ are located, you will have found the pattern behind the mirror 
symmetry. What is the general rule for this pattern?  


\subsubsection{Noticing more general patterns}

To see more general patterns, we need to be able to talk about an arbitrary 
pair of students. To do this, let's suppose our five students are numbered 1, 
2, 3, 4, and 5 in some ordering, so that if i and \emph{j}
 are any two of these five integers, then we can speak of ``student \emph{i}
 and student j'' without having to choose specifically to refer to ``students A and B'' or ``students D and C'' for example. In other words, while symbols such as ``A'' and ``B'' were just \emph{abbreviations}
 for names (Anna, Brian, etc), the \emph{indexes}
 like \emph{i}
 and \emph{j}
 are variables: they can vary over ranges of numerical values capable of representing any student. This way we can look for patterns that exist between an arbitrary collection of students. In fact, we can say the following. 


 Given that $d_{ij}$ is the travel cost of going from the ith student's 
home to the home of the jth student (here \emph{i} and \emph{j} represent the 
indexes of two students among \emph{any} group of students -- not necessarily 
a group of exactly five students), then the symmetry we have noticed can be 
expressed by the equation $d_{ij} = d_{ji}$. Furthermore, we have one such 
equation for each pair of different indexes \emph{i} and j (we already 
separated off the case when i = j). 


Similarly, we can express the pattern of zeros along the diagonal by the set 
of equations $d_{ii}=0$; there is one such equation for each \emph{i}
, that is, one such equation for each student in the group. 


Since $d_{ij} = d_{ji}$ for each pair of indexes \emph{i} and \emph{j}, 
and since $d_{ii} = 0$ for each \emph{i}, we can streamline our chart: 
no essential information will be missed if we 
omit the diagonal entries (we know those must be zero), nor if we include 
only one of the chart's two symmetric halves. This leaves us with the 
following simplified chart of travel costs between students (we keep the 
blank A-row and E-column to maintain symmetry and readability): 

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline 
Student & & & & &\\
\hline
A & & & & & \\
B &1 & & & & \\
C &8 &10 & & & \\
D &5 &6 &2 & & \\
E &4 &7 &9 &3 & \\
\hline
\textbf{Travel cost to:} &A &B &C &D &E  \\
 \hline 
\end{tabular}
\end{center}
\caption{Travel costs between pairs of students}
\end{table}


\subsubsection{Forming Student Groups: who goes with whom?}


Now let's return to our original question: what is the best way for breaking up this collection of five students into two separate project groups, one having two members, and the other with three? Since we're now back to dealing with exactly five students rather than attempting to understand the general case, we can again represent the students by their first initials (A, B, C, D, and E). As you will see below, we will use brackets to denote groupings of students together. We will proceed to group the students together into ``clusters'' -- tentative candidate groupings for what the project groups \emph{might be}
 -- in a series of steps. 


 Initially, no student is assigned to be ``in the same group as'' any other student. Therefore, initially we start with five individual students, each grouped (with brackets) as a single-person ``cluster'': [A], [B], [C], [D], and [E]. This initial set of five students, each belonging to their own one-person cluster is represented in set notation as: \{[A], [B], [C], [D], [E]\}. Our goal is to end up with two project groups, one with two students, and one with three. For example, we might end up with project groups represented by [A,D] and [B,C,E], which would be the set of two clusters: \{[A,D], [B,C,E]\}. 


 Since the only criterion we have to work with at this time is travel cost, we would like to group students together who live \emph{close}
 to each other in the sense of their being a lower travel cost between such students. If you look at the chart you will notice that Anna and Brian live 1 travel cost unit apart, and also that no other pair of students have a lower mutual travel cost. 

So one reasonable first grouping (or clustering) of students would look like this: 

\begin{center}
First Clustering: \{ [AB], [C], [D], [E] \} \\ 
A set of four tentative clusters make up this clustering. 
\end{center}

This means that Anna and Brian are to be in the same group, and that the other students are not yet presently assigned to be ``together with'' anyone else. Until we further examine the chart for more information, it's not clear what the final project groups -- that is, what the final clustering -- might be. We could end up with \{[AB], [CDE]\}, but the final clustering might also be \{[ABC], [DE]\} or \{[ABE], [CD]\}, or \{[ABD], [CE]\} 

\textbf{\flushleft Pause for reflection:}
Are there any other possibilities? How can you tell? How hard would it be to answer questions of this sort if instead of dealing with five students, we had 10? 30? In other words, given a larger initial set of students, and supposing two students are grouped together, with the rest being as yet ungrouped, can you see that the number of choices for final project groups (even restricting each final project group to 2 or 3 members, say) becomes rather large? Chose a size of initial number of students (e.g. 6, 7, or larger) and try to answer, or estimate, how many possible choices there would be for final project groups. 

Now examine the chart again, and notice that the next smallest travel cost between two students is 2, which is the travel cost between C and D. Our eagerness to find pairs of students such that the travel costs between them is as small as possible suggests we may want to adopt the following reasonable \emph{method}
: we will ``cluster together,'' at each step, those two students who are closest in travel costs. 


Notice that what we are actually combining are the \emph{groups}
of these two students, since each student is technically a one-person group. This is an observation we will shortly use when we need to generalize our rule to a method of combining a student with a ``cluster'' (grouping) of other students. In any case, if we adopt our rule as it stands, then our next clustering will be: 

\begin{center}
\{[AB], [CD], [E]\}.
\end{center}

Since single-member groups are not allowed, we are not done yet. Ethan (student E) needs to be placed into one of the two other groups: either together with Anna and Brian (the [AB] group or \emph{cluster}) or together with Chris and Deborah (the [CD] cluster). 

Since the rule defined by our method only tells us which \emph{students}
to put together, we need to expand it in order to decide where to place Ethan. Expanding on our observation above, we can expand our rule to be: ``find the two students (not in the same cluster) such that the travel cost between them is least, and combine the \emph{groups}
 to which these students belong''.  


After all, we started by finding the smallest two numbers in the chart (the ``1'' and ``2''), so it's reasonable to look for the next smallest travel cost, which is 3. This is the value of dDE, which is the travel cost between Deborah and Ethan. Thus, if we put Ethan into the [CD] cluster, that is, into the same group with Chris and Deborah, then at least one of Ethan's groupmates (Deborah), will have travel costs to Ethan as small as possible. Thus, we have now arrived at the following clustering of students into two project groups: 


\begin{center}
\{[AB], [CDE]\}
\end{center}

According to this method we've created, the teacher would have Anna and Brian form one project group, and would declare Chris, Deborah, and Ethan to be a second group. We can now draw the following diagrammatic sequence to represent the stages of the process we used to arrive at the final project groups: 


 \begin{center}
\{ [A], [B], [C], [D], [E]\} $\rightarrow$ 
\{[AB], [C], [D], [E] \} $\rightarrow$ 
\{ [AB], [CD], [E] \} $\rightarrow$ 
\{ [AB], [CDE] \} 
\end{center}



 Is there more to this story? Should we now, pleased with this result, march into our professor's office and declare that we have solved all of their problems of assigning student project groups? 


One point to notice is that sequence in the diagram above is not be the only 
possible order in which the groups can be formed. Had we a tie, say, 
$d_{AB} = d_{CD} = 1.5$, then the second stage would have been either as 
above, or \{[A], [B], [CD], [E]\} (the first stage would still be 
\{[A], [B], [C], [D], [E]\}). 


\textbf{\flushleft Exercise:}
Had the chart of travel costs been the same as above except that 
$d_{AB} = d_{CD} = 1.5$, draw a complete diagram for the rest of the process 
for each of the two possible ``second steps''. Would they both end with the 
same final choice for groups? 


\textbf{\flushleft Note:}
It turns out that for algorithms different than the one just used, one does not always arrive at the same final choices for groups, when ties create several avenues for the ``next step.'' There are many ways to handle ``ties'' of this type. One possibility would be to simply arbitrarily choose one of the tied values and treat it as the larger of the two (by flipping a coin, for example). For simplicity, in this module we will, from this point on, always assume that all of the travel costs between pairs of students are different from one another, and thus avoid this complication in our overview of examples and methods. See the list of references for more general treatments of clustering which include such situations. In particular, see section 3.2.6 in [JD]. 


 As we see next, even with this simplification, there are other questions and doubts that arise upon closer consideration of the methods we have used so far for choosing project groups.  


\subsubsection{Did we choose wisely? A Second Look}

Our stepwise \emph{agglomeration}
, that is gathering together, of the initial set of five separate students into larger clusters, was a step-by-step process which created partitions of the five-student set with fewer and fewer ``pieces''. That is, there were fewer clusters at each step (at each successive cluster\emph{ing}
) as the size of some of the clusters increased, and this process certainly ended as it was supposed to: our final clustering consisted of exactly two clusters, one having two students, and other having three students. 


 If this were the \emph{only}
 requirement, there would be no room for improvement. Recall however that we were also interested in the travel costs between the students, which we wished to minimize in some reasonable sense. Since the meetings of the project groups take place outside of class, at student homes, we wanted to spare our students from having to make ``expensive'' trips -- in terms of time, money, and other factors measured by the travel costs -- as they went about having their frequent meetings with fellow project group members. 


 With regard to this criterion, our method certainly yielded in some sense a \emph{reasonable}
 answer: Anna and Brian, who have the lowest mutual travel cost, are in the same group, and furthermore, Chris and Deborah, who have lower mutual travel costs than any other pair other than Anna and Brian, are also clustered into the same project group. Finally, we put Ethan in Chris' and Deborah's project group, because the travel costs between Ethan and Deborah is less than for any other pair besides Anna and Brian, and Chris and Deborah. What could be better? But wait! Why does Ethan have a frown on his face? And Chris doesn't look too happy either. 


 \textbf{\flushleft Pause for reflection:}
 Why the frowns? Consider carefully the information we have. What do you think the problem might be? 


The travel cost between Chris' place and Ethan's is 9, the second highest 
pairwise travel cost of \emph{all} the travel costs between pairs of 
students(*). Thus when meetings are held at Chris' house, Ethan has a 
difficult trek to make, and similarly when meetings are held at Ethan's, 
the travel cost for Chris is equally large! 

\begin{quote}
[Comment: Notice that the travel costs from Chris to Ethan (9) is greater 
than the sum of the travel costs from Chris to Deborah (2) plus the travel 
costs from Deborah to Ethan (3). This might happen, for example, if there is 
a time cost such as switching between two modes or lines of public 
transportation when one tries to get from Chris to Ethan via an intermediate 
stop at Deborah. Thus it is now clear that the Triangle Inequality does not 
hold for this example since, as you may recall from Euclidean geometry, the 
\emph{triangle inequality} states that given three points A, B, and C, then 
dist(A,C) $\leq$ dist(A,B) + dist(B,C). That is, the distance from A to C is 
less than or equal to the sum of the distance from A to B, plus the distance 
from B to C. When dissimilarities \emph{do} represent distances, then the set 
of dissimilarities have this additional, ``triangle inequality'' property: 
$d_{i,k} \leq d_{i,j} + d_{j,k}$, that is, the dissimilarity between $O_i$ 
and $O_k$ is less than or equal to the sum of the dissimilarity between $O_i$ 
and $O_j$ added to the dissimilarity between $O_j$ and $O_k$. In general, 
however, the matrix of dissimilarities need not have this property, because 
underlying dissimilarities need not represent distances. For example, 
molecules A and B might be judged by chemists to have dissimilarity 5, 
and molecules B and C might be judged to have dissimilarity 1, but the 
dissimilarity between molecules A and C might be 8 -- greater than 5+1] 
\end{quote}



This does not mean that we should automatically throw out all of the preceding work. Nor that we should throw out the informal \emph{algorithm}
, or procedure, which we used to guide our stepwise formation of clusterings of students. 


 But let's think about the problems created for Chris and Ethan which arose from our above algorithm, which we came up with ``on the fly.''$<$ Do these problems suggest alternative criteria we might use in our clustering procedure? For example, why not try to minimize how ``bad'' a trip between \emph{any}
 two members of the candidate project group would be, when we consider lumping students together to form larger project groups? Might this be a goal worth adopting? \begin{quote}
[Comment: in general, when solving a problem, we might get different solutions or answers -- different final clustings in this case -- depending on the goal(s) or objective(s) we adopt]
\end{quote}



 If we proceed with this modified goal in mind, some interesting differences arise in how our ultimate clusters (project groups) turn out: we get a different sequence of clusterings, and more precisely, we get a different final clustering of the 5 students. 


 To see this, we follow this new criterion and observe what happens. Initially, we would still cluster Anna and Brian together: 


 \begin{center}
\{ [A], [B], [C], [D], [E]\} $\rightarrow$ \{[AB], [C], [D], [E] \} 
\end{center}



 This is due to ``1'' being the cost of the least costly trip between any two students. Next, we still cluster Chris and Deborah together since ``2'' is the next least costly trip. So, as before, we have the following sequence of clusterings: 


 \begin{center}
\{ [A], [B], [C], [D], [E]\} $\rightarrow$ \{[AB], [C], [D], [E] \} $\rightarrow$ \{ [AB], [CD], [E] \}
\end{center}



 Now things become more interesting. The next smallest travel cost is ``3'' and is between Deborah and Ethan. However as we saw, the travel cost between Chris and Ethan is 9 -- pretty bad. Can we do better? With so many possible combinations, where do we even begin? How might we proceed? 


 Our idea is to try to make the ``worst'' trip be the least costly one we can manage -- to see how low a travel cost we can arrange for such a worst trip, while still finding ourselves able to arrive at a final clustering. Under our rules, this means being able to arrive at one cluster (project group) with three students, and another with two. 


 So far we have Anna and Brian assigned to be in the same group, and Chris and Deborah are assigned to be in the same group. Suppose we wish to require that the ``worst'' trip have travel cost no more than 3. Would this work? Clearly not, since adding Ethan to Chris and Deborah's group would fail to meet this requirement (Ethan and Chris are 9 travel cost units apart), nor could we add Ethan to Anna and Brian's group (Ethan is 4 and 7 units away from them, respectively). And since four member groups are not allowed, we don't need to consider the possibility of merging [AB] with [CD]. 


 Next, rather than giving up, we relax our requirement a bit. Suppose we try to require that the ``worst'' trip be no more than 4 travel cost units. We still can't add Ethan to either of the two member groups -- can you explain why not? Next, we try 5 for the ``worst allowable trip''. Why doesn't this work? And why does 6 not work either? 


 Not giving up, we now try to make 7 the ``worst allowable trip''. Now, we \emph{can}
 add Ethan to Anna and Brian's group, since Ethan lives 4 units away from Anna, and 7 units -- just barely fitting within our requirement -- from Brian. Thus the worst travel cost for any member of this proposed group would be 7. 


 Notice that under our new criterion, deciding whether to have Ethan join Anna and Brian's group, or to have him join Chris and Deborah's group is not a difficult choice -- we would not be tempted to add Ethan to Chris and Deborah's since as we noticed earlier, Ethan and Chris live 9 travel cost units apart, so the ``worst trip'' for a proposed group of [CDE] would not be 7 units or less. 


 Thus our new clustering criterion is this: ``at each step, minimize how bad [in travel cost] the 'worst possible trip' is within a proposed project group''. As we just saw, under this second clustering procedure we get a different sequence of clusterings than the one created by our first method; namely, we get the following sequence of clusterings: 


 \begin{center}
\{ [A], [B], [C], [D], [E]\} $\rightarrow$ \{[AB], [C], [D], [E] \} $\rightarrow$ \{ [AB], [CD], [E] \} $\rightarrow$ \{ [ABE], [CD] \} 
\end{center}



 Thus we have ended up with a different final set of clusters (final clustering): [ABE] and [CD]. We are now better able to provide our instructor with algorithms for creating project groups, depending on what goals are considered most important. We have two methods or algorithms, which we created using \emph{ad hoc}
 methods -- in other words, by ``following our noses'' and intuition rather than by using a systematic approach and analysis. Our two methods seem decent, however we would certainly feel more confident in them if we had a better sense of what other types of clustering outcomes are possible, and if we had a better feel for ``the lay of the land'' for methods of clustering. Is there are more careful, systematic way to think about it? 


 In the following sections, we will give more formal, that is more careful and precise definitions of the concepts we've already encountered, and of algorithms for clustering an initial set of elements, such as students, into a collection of groups, called clusters, such as project groups for students. But first, let's slow down for a moment to take a brief first look at the overall enterprise we have embarked on: the field of cluster analysis.  

\subsubsection{Is there Method in our Madness?}

The attentive student might wonder at this point which of the above two methods of clustering the five students is the ``right'' one. Unfortunately there is no single, simple answer to this question. In fact, you might start to wonder just how many possible methods there are besides the two we stumbled upon. When looking at a clustering problem, do we just try to discover (make up?) new criteria for each new application that arises, with each criterion or method leading to a different solution? And in our opening example, should we search for a third method, a fourth, and so on, leading to a large number of possible clusterings, none of which we can say with any confidence is ``the right one''? 


 These questions are indeed fundamental to understanding the field of clustering. While we cannot answer all of them in full detail here(*), several general remarks can be made at this point. 


 \begin{quote}
[Comment: we encourage interested readers to further investigate these issues. For suggested reading, see the References.] 
\end{quote}



 First, the reader should understand that researchers in the field of cluster analysis do \emph{not}
 proceed by means of random, \emph{ad hoc}
 methods invented on the spot. How then are methods chosen? Part of the answer is that, as we shall see, one can approach the question of ``what criteria are important?'' in a more systematic and precise manner. This more precise notion of ``what is important'' in terms of criteria can then aid in selecting an appropriate method of clustering. For example, the teacher might decide that, in the interest of fairness, the ``average ability'' (suitably defined) of any one group should not differ too sharply from that of another project group. Or, a professor might want diversity of student backgrounds within each group. Any criterion, that is, any given and carefully defined choice of desired properties of the clustering, can serve as an aid for choosing among different possible clustering methods, and even for identifying new clustering algorithms. 


 Different applications and contexts, in which we are clustering things other than students, lead to other natural criteria. For example, suppose that a country, state, or province has enough funds in its budget to build 10 new hospitals in a given region. Where should the hospitals be located? One can obtain data as to where people live, including the population densities in different areas. And one can make an assessment of the degree of need in any one area (perhaps with a greater percentage of older citizens) versus another. These and similar data then form the basis from which more mathematically precise clustering criteria, and ultimately, clustering algorithms, can be created by researchers. 


 Still other applications arise in industry (where should factories
 and outlets be built, given consumer preferences and population
 concentrations?), psychology (given a set of a dozen ``scores'' from
 different personality tests, which individuals should be clustered as
 being of similar ``type''? or which sets of personality tests should
 be clustered as ``measuring similar qualities''?), transportation
 (where should airports be located? How do we ``cluster'' customer
 transportation demands into a manageable number of flights and
 connecting flights?), sociology (who tends to mingle with whom during
 a social gathering, in a cafeteria, or other location or event?),
 chemistry (e.g. molecular classification into clusters of ``similar''
 molecules, see references in [1], biology (see [2] and [3] for
 clustering in the taxonomic classification of species as well as
 genetics [4], ecology [5], phylogenetic algorithms [6], and
 even the internet [7]. For example, how can a software program
 ``cluster together'' web sites into groupings so that two web sites
 in the same group (cluster) are likely to be equally interesting and
 useful -- or likely to be equally uninteresting -- to the user? (see
 [CP] in references section). For additional applications, such as
 image processing, see chapter 5 of [JD].


 With this overview in mind, we are now ready to delve more deeply
 into the world of clustering. As promised, we begin by making our
 definitions more precise.


\subsubsection{Defining our Terms}



 To be able to sharpen our analysis, we need to be able to put the objects and relations we have been studying into clearer focus, and this is why we need more precise definitions. In the following collection of definitions, modeled after [HJ], each newly defined term is put in \emph{italics}
. 


 First, we need to know what we wish to ``cluster''. Thus, we need to start with some underlying set; for example, the underlying set in the prelude's opening example was the initial set of 5 students. Such an underlying set in a clustering problem is called the \emph{sample}
. Since the elements of the set are quite often objects rather than people, we will usually use the capital letter O for the sample set, and its elements or objects will be denoted with subscripts, for example: 


 \begin{center}
O = \{O$_1$, O$_2$, O$_3$, O$_4$, O$_5$\} 
\end{center}

might denote the underlying set (or sample) in our opening example. In general,
we may have in the sample O any number of objects (also called \emph{entities}
), and if there are N objects, then we write: 


\begin{center}
O = \{O$_1$, O$_2$, O$_3$, ... , O$_{N-1}$, O$_N$\}. 
\end{center}


Here O$_1$ is the ``first object,'' O$_2$ the ``second,'' and so forth, 
while O$_{N-1}$ is the ``second to last,'' and O$_N$ is the last of the 
N objects in the sample being considered. However, the ordering itself is 
generally unimportant. Its usefulness is simply to allow us to give different 
names to the different objects, so we can speak unambiguously about which 
object is clustered together with which: for example, O$_2$ being clustered 
together with O$_8$ rather than O$_3$ with O$_5$. 


In order for the clustering of the objects in our underling sample to be performed in a way that is not arbitrary, this sample must also come with some way of measuring how ``alike'' or else, how ``dissimilar'' any two objects are. When our ``objects'' were the students in the opening example, the dissimilarity between two objects (students) which we used was the travel cost between their homes. 


 In other applications, the numerical dissimilarities between objects can have a different meaning. An example is when we are trying to cluster communities into sub-regions or districts, so that one clinic may be built for each district, with each one being considered a cluster. For such an application, dissimilarities might be travel costs in dollars, or in time, between the communities, or actual distances between the communities needing medical care, or some other numerical measure of how different the communities are from one another. Or perhaps a complex measure is created by doctors, statisticians and others, taking into account age distributions, income distributions, the effect of the number of high-speed highways on getting an ambulance to and from a community, and so forth. 


 One important thing to keep in mind is that dissimilarities need not be distances in the usual sense of distance between geographical places (think of the phrase ``distant relatives'' for some of your cousins). As we have seen, they come from a wide variety of ``measures'' which are used when experts in a given field have solid evidence suggesting the measure reasonably captures critical differences between objects in the sample. Other examples of measures of similarity/dissimilarity between elements of a set include the differences in base pairs between strands of DNA , measures of ``closeness'' between species and their anatomy, and differences between the chemical properties of molecules. In general however, regardless of the application, when we speak of the dissimilarity between two objects, we are speaking of a positive \emph{number}
, for dissimilarities are represented as numerical values. 


The set of dissimilarities between all possible pairs of objects in a sample 
is normally given in the form of a matrix. This is just a two-dimensional 
table whose rows correspond to the elements of O, and whose columns likewise 
index the elements of O. This table or chart is then filled with numbers: 
the number in the 2nd row and 3rd column is labeled \emph{$d_{2,3}$}
 and represents the \emph{dissimilarity}  between the 2nd and 3rd objects in O.
That is, the dissimilarity between O$_2$ and O$_3$ is \emph{$d_{2,3}$} and 
generally, the dissimilarity between O$_i$ and O$_j$ is written 
\emph{$d_{i,j}$} . This matrix of dissimilarities taken as a whole is called 
the \emph{dissimilarity matrix} for the sample O. 


 All of this should have a rather familiar ring to it: the chart in our five-student opening example was nothing but a dissimilarity matrix for our (rather small) sample set of five elements of O, and the ``objects'' in O were just the students (and as before, we will assume that our dissimilarity matrix contains \emph{no ties}
). 


 Furthermore, from our opening example it's clear that the matrix of 
dissimilarities will have two crucial properties: $d_{i,i} = 0$ for any 
\emph{i} (the dissimilarity when we compare O$_i$ with itself is zero), 
and for any pair of indexes \emph{i} and \emph{j}, $d_{i,j} = d_{j,i}$ (the 
dissimilarity between O$_i$ and O$_j$ is identical to the dissimilarity 
between O$_j$ and O$_i$). Finally, we also require in our definition of a 
proper dissimilarity matrix that $d_{i,j} \geq 0$. This means that 
dissimilarities cannot be negative. After all, the dissimilarity, that is 
the degree of difference between two objects cannot be less than ``nothing'' 
--''nothing'' meaning that no differences exist-- and so cannot be less than 
zero. Note that if our sample space O has \emph{n} elements, then our 
dissimilarity matrix will be an \emph{n} by \emph{n} matrix. 


 The reader should note that all clustering methods depend critically on the matrix of dissimilarities. Such dissimilarities are based either on distances, or on non-distance ``proximities,'' meaning degrees of qualitative closeness or similarity between objects. It is emphasized in [JD] for example that ``unless a meaningful measure of..proximity, between pairs of objects has been established, \emph{no meaningful cluster analysis}
 is possible. The proximity matrix is the \emph{one and only}
 input to a clustering algorithm'' (emphasis added. Note that, whether we think of the entries of the matrix as expressing levels of ``dissimilarity'' or levels of ``similarity''/''proximity,'' are two sides of the same coin, just as ``how big is it?'' or ``how small it is?'' are two ways of looking at a measurement like ``size is 4 feet''). 


The next logical step, with our underlying sample set O and the matrix of 
dissimilarities now fleshed out, is to give a precise definition of clusters. 
A \emph{cluster} C is just a subset of O. For example, if O = \{O$_1$, 
O$_2$, O$_3$, O$_4$, O$_5$\}, then C = \{O$_3$, O$_5$\} might be a cluster. 


Thus $C_1$ = \{O$_1$, O$_2$, O$_3$\} and $C_2$ = \{O$_4$, O$_5$\} can correspond to 
the two clusters (project groups) into which the five students were divided 
in our first attempt, each $C_i$ being a cluster. Notice however that when we 
started with the original set O of five students, what we were after, and 
what we desired as ``the answer'' was neither the cluster $C_1$ nor the 
cluster $C_2$. Rather, it was the collection of these two clusters, which 
together told us how the original group of students was to be divided, which 
we were after. 


A \emph{clustering} (used synonymously with \emph{partition}, see [JD]) is a 
collection of disjoint subsets (that is, a collection of disjoint clusters) into which the given set O can be divided. More precisely, we have the following definition. 


A \emph{partition} of a given set O is a collection of (nonempty) 
subsets $\{C_1, C_2,... C_M\}$ such that:
\begin{enumerate}
\item If \emph{i} does not equal \emph{j}, then $C_i$ and $C_j$ are disjoint; 
that is, they do not have any elements of O in common. In mathematical 
notation, we write $C_i \bigcap C_j = \Theta$, where $\Theta$ denotes the 
empty set. 

and such that also: 

\item Every element in O belongs to one (and by the preceding property, necessary to only one) of the clusters. In terms of sets, this means that O is equal to the union of the all the clusters in the partition. In mathematical notation this is written: 

 


\end{enumerate}

$$O = C_1\bigcup C_2 \bigcup... \bigcup C_M$$




A \emph{clustering method} is then a rule which, given any initial sample set 
O along with an associated matrix of dissimilarities $\{d_{i,j}\}$, tells us 
how to produce, perhaps through a sequence of steps, a clustering 
$\{C_1, C_2, ... C_M\}$ as its final output. Here, the number of clusters 
in the ultimate clustering, M, depends both on the sample O, and on the 
dissimilarity matrix we are given in each instance. 


Finally, a \emph{clustering algorithm} is a mathematically precise 
step-by-step procedure for implementing a clustering method. It is written 
as if in a hypothetical programming language (that is, it's written in what 
computer scientists call \emph{pseudo-code}), such that were it run on a 
computer, and given the set O and the matrix $\{d_{i,j}\}$ as inputs, it would 
produce the clustering determined by the method as its output. In practice, 
the pseudo-codes given for various clustering algorithms in research articles 
are used as guides for writing actual computer programs (written in a variety 
of existing computer languages) which implement the algorithm. 


At last we have at set of specific and precise definitions! Still, you may wonder what lies inside the ``black box'' of such clustering algorithms. In the next section, we will look at the inside workings of two of the most common clustering algorithms. In fact, as we will see, these precise algorithms will put our first two ``ad hoc'' methods in a new light. 


\subsection{The Missing Links:}
 
\textbf{Introducing two common clustering algorithms}

It is important to observe that the process of applying our first informal, ad-hoc algorithm to the five-student example produced more than a single, final clustering. Rather, it produced a \emph{sequence}
 of clusterings, culminating only in the last step with the clustering which determined a possible set of students project groups: 

 \begin{center}
\{ [A], [B], [C], [D], [E] \} $\rightarrow$ \{ [AB], [C], [D], [E] \} $\rightarrow$ \{ [AB], [CD], [E] \} $\rightarrow$ \{ [AB], [CDE] \}
\end{center}

We can view this process as a sequence of four partitions (four clusterings) of O: 
$$P_1\rightarrow P_2\rightarrow P_3\rightarrow P_4$$

Furthermore, notice that there is a definite relationship among these four successive clusterings; at each clustering, the \emph{clusters}
 it consists of are ``the same as or bigger than'' those making up the preceding clustering. More precisely, the clusters in succeeding clusterings (partitions) are gotten by taking the set-theoretical unions of clusters which had made up preceding clusterings. A sequence of clusterings having this property is said to be a sequence of \emph{nested}
 clusterings. 


Clustering algorithms which produce not merely a final clustering from the initial set O, but a sequence of nested clusterings are, in fact, quite natural, since we might be interested in more than just ``the last'' clustering such an algorithm produces. For example, if the professor in the five-student example later decides that one and two member groups are acceptable, the second to last clustering, \{ [AB], [CD], [E] \}, might be the best choice for assigning student project groups. Therefore, the entire four-step output $P_1\rightarrow P_2\rightarrow P_3\rightarrow P_4$ is useful, and it's up to the professor to decide which of the four P$_i$ -- that is, which of the four clusterings -- is the one to be used for assigning project groups. 


 In general, a clustering algorithm which produces a nested sequence of clusterings is called a \emph{hierarchical}
 clustering algorithm. This is because it produces a ``hierarchy'' of possible clusterings: a sequence is produced, starting with clusterings which have a large number of clusters (each containing a relatively small number of objects), and proceeding to clusterings which are made up of a small number of clusters (each of which contains relatively many objects). Hierarchical algorithms which proceed in this order, i.e., which proceed from a large number of 'small' clusters, to a small number of 'large' clusters, as opposed to the opposite order, are called \emph{agglomerative}
 (In Chapter 2 we will introduce the ``other kind'' of hierarchical clustering algorithms, called \emph{divisive}). 


 Both of the algorithms which we'll consider in this section are hierarchical; in fact, they will both be agglomerative. Informally speaking, such agglomerative algorithms proceed by building the clusters ``from the ground up'' with set-theoretical unions. 


 More precisely, in such algorithms one first starts with one extreme clustering (partition of O), namely the clustering in which each object forms its own one-object cluster. Then, as the algorithm proceeds, clusters are merged to form larger clusters, until the last clustering (the final partition of O) is reached. This last clustering is the other extreme; it is the single-cluster clustering in which all objects are placed into one cluster. Of course, this cluster is necessarily the cluster which contains all the objects: O itself. Giving a precise definition of such an agglomerative clustering algorithm turns out to be rather straightforward, as we are about to see.  


\subsection{Single and Complete Linkage: the Inside Scoop}

\subsubsection{Single Linkage}

As we have just seen, an agglomerative hierarchical clustering method begins 
with the partition (clustering) $P_1 = \{ \{O_1\}, \{O_2\}, ... , \{O_N\} \}$.
Thus, $P_1 = \{ C_1, C_2, ... , C_N \}$, where $C_1$ is the single object 
cluster $\{O_1\}$, $C_2$ is the single object cluster $\{O_2\}$, and in 
general $C_i = \{O_i\}$. 


The single linkage algorithm defined in this section, and the complete 
linkage method discussed in the next section, are agglomerative hierarchical 
methods of clustering (henceforth referred to more briefly as 
\emph{agglomerative algorithms} or \emph{agglomerative methods}). Therefore, 
under these algorithms we start with $P_1 = \{ C_1, C_2, ... , C_N \}$, where 
$C_i = \{O_i\}$. In successive steps, each of these algorithms merges clusters
together, until the last clustering $P_q$ is arrived at, namely $P_q = \{C_1\}$
where $C_1 = O = \{O_1, O_2, ... , O_N\}$, the single cluster containing all 
objects. 


 An agglomerative algorithm is determined by its method of joining or agglomerating clusters together. Put differently, the differences between \emph{any}
 two agglomerative methods, and in particular between the single and complete linkage methods, lie in the different criteria which specify which clusters are to be merged at each step. 


 Before describing the criteria used for these two algorithms, it is important to note that the contents of the ith cluster Ci are not fixed, but depend on the \emph{stage}
 of the clustering algorithm. For example, if A, B, C, D, and E correspond respectively to $O_1, O_2, O_3, O_4$, and $O_5$, then we may view the now familiar sequence of four clusterings: 



$$\{ [A], [B], [C], [D], [E] \} \rightarrow \{ [AB], [C], [D], [E] \} 
\rightarrow \{ [AB], [CD], [E] \} \rightarrow \{ [AB], [CDE] \}$$



 As our sequence of clusterings 
$P_1\rightarrow  P_2\rightarrow  P_3\rightarrow  P_4$ and we may write them 
in the notation: 


$$\{ C_1, C_2, C_3, C_4, C_5\}\rightarrow  \{ C_1, C_3, C_4, C_5\} \rightarrow 
\{ C_1, C_3, C_5\} \rightarrow \{ C_1, C_3 \} $$

For example, at the first stage, in $P_1$, we have $C_1$=[A] and $C_2$=[B], 
but in the second stage the (single member) clusters [A] and [B] are merged 
together to form the new cluster $C_1$=[AB] in $P_2$ (we have chosen an 
obvious renaming scheme for the $C_i$ to minimize relabeling of indexes). 

In the implicit but omitted last step, $P_5$=\{[ABCDE]\} and we have a single 
cluster, $C_1$=[ABCDE]. In the above, it was our knowledge of this particular 
case -- knowing that we seek student project groups having either two or three
members -- and not a formal ``rule for stopping'' which made it clear that P4 
was the cluster to examine. The general algorithm, as noted, produces a full 
spectrum of clusterings, one for each stage: from the fine extreme where 
$C_i = \{ O_i \}$ to the coarse extreme with just one $C_1 = \{ O_1, ... O_N\}$
.  

\begin{quote}
[Comment: A somewhat more complex and more general notation is often used, 
in which $C_{ij}$ is the jth cluster in the ith clustering, as in [JD]. In 
such cases commas are added when necessary to avoid ambiguity: since $C_{112}$ 
could mean the 12th cluster in the first clustering or the 2nd cluster in the 
11th, one adds a comma and writes either $C_{1,12}$ or $C_{11,2}$. We will 
maintain the simpler notation $C_i$ in this exposition, with the understanding
that the \emph{i}th cluster this represents will depend on which clustering, 
that is, on which step in the clustering algorithm we are]. 
\end{quote}



Now, what criterion does the single linkage method use for merging two 
clusters together? Actually, both the single linkage and complete linkage 
methods progress from the clustering $P_i$ to the clustering $P_{i+1}$ by 
merging together those two clusters which are ``closest together''; the 
difference between the two algorithms is in how the term ``closest clusters'' 
is defined. More precisely, the key is how the ``dissimilarity'' between two 
\emph{clusters} (not merely between two objects) is defined. 


Under the single linkage procedure, the dissimilarity between two clusters 
$C_i$ and $C_j$ is defined to be the \emph{smallest} dissimilarity between 
any two objects, one of which must lie in $C_i$, and the other in $C_j$ (as 
before, we assume there are no ``ties'' in the dissimilarity matrix). This 
measure of dissimilarity between $C_i$ and $C_j$ can be computed as follows: 
\begin{enumerate}
\item First, consider all pairs of objects, one of which lies in $C_i$ (call 
it $O_k$), and the other lies in $C_j$ (call it $O_l$) 
\item Second, look up the dissimilarity between the two objects in \emph{each}
such pair (if the two objects are $O_k$ and $O_l$ then this dissimilarity is 
the number $d_{k,l}$), and lastly 
\item Find the \emph{smallest} of all of the dissimilarities found in step 2, 
and declare this number to be the dissimilarity between $C_i$ and $C_j$. 

\end{enumerate}


Hence we are taking the minimum of all the possible dissimilarities (numbers) 
$d_{k,l}$ as k and l range over all possible indexes for which it holds that 
$O_k\in C_i$ and $O_l\in C_j$. Using ``SL'' to denote ``single linkage,'' in 
mathematical notation we have the SL-dissimilarity between clusters $C_i$ and 
$C_j$, written dissimilarity$_{SL}(C_i, C_j)$ or $d_{SL}(C_i, C_j)$ which is 
defined by: 


$$d_{SL}(C_i, C_j) = minimum \{ d_{k,l} \}$$


where the minimum runs over all indexes k and l such that $O_k\in C_i$ and 
$O_l\in C_j$. In explicit mathematical notation, this is: 


$$d_{SL}(C_i, C_j) = \mbox{minimum} \{ d_{k,l} \}\: \mbox{over all k,l
such that}\, O_k\in C_i, O_l\in C_j$$  


 or more concisely: 


$$d_{SL}(C_i, C_j) = \min_{O_k \in C_i, O_l \in C_j} \{d_{k,l} \}$$



Our definition can be rewritten in set-builder notation since the set of 
values in whose minimum we are interested is $\{ d_{k,l} | O_k\in C_i, 
O_l\in C_j\}$ 

\begin{quote}
[Comment: Recall that if A is a set and P is a condition which might be 
satisfied by some of the elements of A, then $S =\{ x\in A | P\}$ stands for 
a subset of A, namely, for the set of all elements in A to which condition P 
applies. For example, if \textbf{Z} represents the integers, then 
$S=\{ n\in \textbf{Z} | 2n+3=5\}$ is the set of all integers which satisfy 
the given equation, while the set of all integers which are multiples of 3 
may be written as $S=\{ n\in\textbf{Z} | n = 3k\: \mbox{for some}\, k \in\textbf{Z}\}$ 
that is, the set of all integers which can be written as three times some 
other integer]. 
\end{quote}


Thus we have: 
$$d_{SL}(C_i, C_j) = \mbox{Min} \{ d_{k,l} | O_k\in C_i, O_l\in C_j\}$$



A pseudo-code algorithm implementing single linkage is therefore: 

\begin{enumerate}

\item Initialization: begin with $P_1 = \{ \{O_1\}, \{O_2\}, ... , \{O_N\} \}$.
This defines $P_n$ when n=1.

\item To obtain $P_{n+1}$ from $P_n$, merge $C_i$ and $C_j$ together for the 
pair of indexes \emph{i} and \emph{j} for which $d_{SL}(C_i, C_j)$ is 
\emph{smallest}. 

\item If the resulting partition (i.e., cluster\emph{ing}) is 
$P_{n+1} = \{ O \}$, then stop. Otherwise, increase \emph{n} by 1 and then 
return to step 2. 

\end{enumerate}

\textbf{\flushleft Exercise:}
Convince yourself that the single linkage method applied to the opening example of the five students yields precisely the clustering hierarchy we initially obtained, 


 \begin{center}
\{ [A], [B], [C], [D], [E]\} $\rightarrow$ \{[AB], [C], [D], [E] \} $\rightarrow$ \{ [AB], [CD], [E] \} $\rightarrow$ \{ [AB], [CDE] \} 
\end{center}



 At which stage, having the desired groupings, we could have the algorithm halt; if allowed to complete the algorithm would end with \{ [AB], [CDE] \} $\rightarrow$ \{ [ABCDE] \}. After you've convinced yourself, write a clear explanation showing why this is so. Your exposition should be one which a sceptical but fair fellow student would fully understand and be convinced by, and should include explicit computations with dSL.  


\subsubsection{Complete Linkage}

We proceed exactly as above, the only distinction being how the difference or 
``dissimilarity'' between two clusters $C_i$ and $C_j$ is defined. For the 
complete linkage (CL) method, this is defined to be not the minimum but the 
\emph{maximum} of the dissimilarities between pairs of objects, one of which 
belongs to each of the two clusters under consideration. That is, we define 


$$d_{CL}(C_i, C_j) = \,\mbox{maximum} \{ d_{k,l} \}\: \mbox{over all k,l  
such that}\,O_k\in C_i, O_l\in C_j$$

Or more concisely: 
$$d_{CL}(C_i, C_j) = \max_{O_k \in C_i, O_l \in C_j} \{ d_{k,l} \}$$

In set-builder notation this becomes just: 
$$d_{CL}(C_i, C_j) = \mbox{Max} \{ d_{k,l} | O_k\in C_i, O_l\in C_j\}$$



A pseudo-code algorithm implementing complete linkage is therefore: 

\begin{enumerate}

\item Initialization: begin with $P_1 = \{ \{O_1\}, \{O_2\}, ... , \{O_N\} \}$.This defines $P_n$ when n=1. 

\item To obtain $P_{n+1}$ from $P_n$, merge $C_i$ together with $C_j$ for the 
pair \emph{i} and \emph{j} for which $d_{CL}(C_i, C_j)$ is \emph{smallest}
(notice that what we are doing is taking the \emph{minimum} among those 
``maximum values'' which go into the definition of $d_{CL}$-- make sure you 
understand this!) 

\item If the resulting partition (clustering) is $P_{n+1}= \{ O \}$, then 
stop. Otherwise, increase \emph{n} by 1 and then return to step 2. 

\end{enumerate}

\textbf{\flushleft Exercise:}
Convince yourself that the complete linkage method applied to the opening example of the five students yields precisely the clustering hierarchy we obtained in our second attempt (with our second \emph{ad hoc}
 method), namely, that it would result in the sequence we obtained: 


\begin{center}
\{ [A], [B], [C], [D], [E]\} $\rightarrow$ \{[AB], [C], [D], [E] \} $\rightarrow$ \{ [AB], [CD], [E] \} $\rightarrow$ \{ [ABE], [CD] \} 
\end{center}


followed by a final step, \{ [ABCDE] \}. (We had halted before this final 
step during our second \emph{ad hoc} attempt, since we were initially merely 
exploring how to obtain 2- or 3- member project groups). As in the preceding 
exercise, after you've convinced yourself, give a clear and rigorous 
demonstration (including computations with $d_{CL}$) which would convince a 
skeptical but fair fellow student that the complete linkage algorithm would 
yield precisely this second clustering if applied to the initial group of 
five students and matrix of dissimilarities. Note the parallel structure 
between the Single Linkage and Complete Linkage algorithms above. See 
Algorithm 1 in [M] for a way of informally describing a general agglomerative 
algorithm.  


\subsection{Getting Visual: Dendrograms}

A \emph{threshold dendrogram} is a way of depicting the clusterings in the order in which they are formed. For example, if we represent 


 \begin{center}
\{ [A], [B], [C], [D], [E]\} $\rightarrow$ \{[AB], [C], [D], [E] \} $\rightarrow$ \{ [AB], [CD], [E] \} $\rightarrow$ \{ [AB], [CDE] \} $\rightarrow$\{[ABCDE]\} 
\end{center}

by 

$$P_1\rightarrow  P_2\rightarrow  P_3\rightarrow  P_4\rightarrow  P_5$$

when the associated threshold dendrogram would look as shown in Figure 1: 

\begin{figure}[h]
\begin{center}
\includegraphics{fig1_0.eps}
\end{center}
\caption{\,}
\end{figure}

Here we have included together with the threshold dendrogram a
vertical axis depicting each level $P_i$.

\begin{quote}
[Comment: Although we shall not use this concept, a \emph{proximity
 dendrogram} would label the vertical axis according to the
 dissimilarity level at which the clustering first occurs. For
 example, at a proximity of ``1'' only the [A] and [B] clusters merge
 in the SL algorithm, so the location of $P_1$ on the vertical axis could
 be labeled ``1'' since allowing only mergings of clusters having
 distance less than or equal to 1 would result in only [A] and [B]
 being merged. At higher levels, more clusters will have been merged,
 and at a sufficiently high level, one is at the ``top'' of the
 dendrogram. For us, the threshold dendrogram suffices, since in this,
 our basic example, the threshold levels are just consecutive
 integers. The student interested in learning more about dendrograms
 may consult some of the suggested readings in the references provided
 at the end]
\end{quote}

\textbf{\flushleft Exercise:}
Draw a threshold dendrogram for: 

\begin{center}
\{ [A], [B], [C], [D], [E] \} $\rightarrow$ \{ [AB], [C], [D], [E] \} $\rightarrow$ \{ [AB], [CD], [E] \} $\rightarrow$ 

\{ [ABE], [CD] \} $\rightarrow$ \{ [ABCDE] \} 
\end{center}



Note: you will want to re-order the students and use an ``E, A, B, C, D'' ordering instead of ``A, B, C, D, E'' so that the lines of your diagram will not cross. 


\textbf{\flushleft Exercise:}
Create your own dendrogram on a five (or more, if you wish) element set. Then convert it into the equivalent sequence of clusterings.  


\subsection{Getting Graphical}



 It turns out that there are useful connections between clustering and a branch of mathematics called \emph{graph theory}
. You may recall that in mathematics the term \emph{graph}
 refers to an object which can be represented as a set of points together with a set of line segments between some of these points. \begin{quote}
[Comment: A graph in this sense is, of course, \emph{not}
 the same as the notion in algebra of the \emph{graph of a function}
 which visually represents a relationship of the form y=f(x)] 
\end{quote}

 In a graph, the points are called \emph{vertices}
 while the line segments are called \emph{edges}
. The set of vertices together with the set of edges which connect some of 
them, jointly constitute the graph. Just as the sample set is often given a 
label ``O'' similarly a graph as a whole is often labeled with a capital 
letter such as ``G'' (if there are two or more graphs, then ``G'' and ``H'' 
may be used to label them, or else, ``$G_1$`` and ``$G_2$`` etc). The vertices
of the graph are typically depicted as points, or as circular \emph{nodes}
. For example, a graph G might look like the image shown in Figure 2:

\begin{figure}[h]
\begin{center}
\includegraphics[scale=1]{fig1_1.eps} 
\end{center}
\caption{\,}
\end{figure}

Note that the edges which are depicted as dashed lines are regular edges, and 
the dashed-line style is merely used to visually indicate one straight line 
segment (i.e., edge) being ``behind'' another edge without the two edges crossing or ``touching''. 


Often there are names or \emph{labels}
which we wish to associate with the vertices, with the edges, or with both. Take our opening example and our five students Anna, Brian, Chris, Deborah, and Ethan, to whom we usually refer by their abbreviations A, B, C, D, and E. We might schematically represent these five students, and the travel costs between any pair of them, by using figure 3: 

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{fig1_2.eps} 
\end{center}
\caption{\,}
\end{figure}

\textbf{\flushleft Note of caution:}
the edges in this graph are abstract representations of \emph{relationships between vertices}
, e.g. of the travel costs between pairs of students, as given by their respective labels. Thus the \emph{visual}
 length of the edges as they are 'drawn', and whether they are drawn straight or curved (or ``crossing''), etc, \emph{do not}
 represent any meaningful features of the situation we are modeling, any more than does the geometrical arrangement of \emph{where}
 each vertex in the graph is placed when we draw the graph -- we could have depicted vertices B and C on the right instead of on the left, for example. The graph only tells us: ``there are five vertices with these labels, and there are the following edges between vertices, coming with their corresponding labels as marked''. (In the rare situations in mathematics when a readers needs the lengths of edges to perfectly equal their labels in the drawn graph, a special note to the reader would indicate that this was done). 


In the graph above, non-mathematical information could have been used to label edges, e.g., ``Bus route \#2'' or the like. A graph such as this one, in which mathematical quantities are used to label the edges -- in our case, these mathematical quantities are the travel costs between two students -- are sometimes called \emph{weighted graphs}
 since each edge's label can then be thought of as a ``weight''. 

\subsubsection{At the Threshold of Something New}

Now suppose you are considering a clustering problem having elements labeled 
$O_k$ for k between 1 and N, and with dissimilarity indexes $d_{i,j}$ for the 
dissimilarity between $O_i$ and $O_j$. A \emph{threshold graph} associated 
with a clustering problem is a weighted graph whose vertices are the objects 
and whose edges represent all the dissimilarities that are less than or equal 
to some fixed level. For example, a threshold graph with \emph{threshold}
5 would have one vertex for each object, and its edges would correspond 
exactly to those dissimilarities that are less than or equal to 5. A notation 
often used for the threshold graph with threshold \emph{v} is G(v). Figure 4
depicts in six parts the threshold graphs for our opening five student example,
as v ranges from 1 to 6:

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{fig1_3.eps}
\end{center}
\caption{\,}
\end{figure}

\textbf{\flushleft Exercise: }
Draw G(v) for v = 7, 8, 9, and 10. What is G(11)? What does G(0) look like? G(-1)? Can G(v+1) differ from G(v) by more than one edge? For example, under what circumstances, if any, would two or more edges to be needed to augment G(1) into the larger G(2)? Can you give an example? (Remember: even though we are assuming ``no ties,'' the values of the dissimilarity matrix, and thus the labels of the threshold graph, need not be integers!) 


\subsubsection{Some More Graphical Terminology}

We are almost ready to put this framework from graph theory into use: we will be able to create algorithms which use graphs and which turn out to correspond to methods of clustering. In order to define these algorithms however, we need to review just a few more definitions from graph theory. \begin{quote}
[Comment: these properties of graphs can describe \emph{arbitrary}
 graphs without any clustering context; their applicability is not restricted to threshold graphs]. 
\end{quote}

The \emph{connected components}
of a graph G may be defined as the ``islands'' (or ``pieces'') G is composed of, where two vertices are part of the same island (piece) if one can walk from one to the other using edges. Thus imagining the threshold graphs above to be bird-eye views, we see that G(1) has four connected components: each of C, D, and E are components, while the segment between A and B forms a single, fourth component. G(2) has three components, G(3) has two components, while G(v) for any \emph{v}
 greater than or equal to 4 has just one component. 


A graph is \emph{complete} if an edge exists between \emph{every} pair of 
vertices. For example, each of the two graphs in Figure 5 represent
a complete graph with four vertices:

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{fig1_4.eps} 
\end{center}
\caption{\,}
\end{figure}

Here as previously, one of a pair of crossing edges is depicted as a dashed line to aid in telling apart the edges, though this is of course not strictly necessary. 

A complete graph with three vertices looks like a ``triangle'' while a 
complete graph with two vertices is just an edge between two vertices. A 
complete graph with five vertices is a ``pentagram'', as depicted in Figure 6. 

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{fig1_5.eps} 
\end{center}
\caption{\,}
\end{figure}

Finally, let H be a \emph{subgraph} of G, that is, a subset of G -- a 
sub-collection of vertices and edges -- which itself is a graph, so that if 
e is any edge of G included in H, then the endpoints of e must be in H as 
well. Then a \emph{clique} in a graph G is a subgraph H which is 
\emph{complete}; that is, such that any two vertices in the subgraph are 
connected by an edge which is included in that subgraph, i.e., by an edge which has been declared as belonging to H in the definition of H. For example, any two vertices joined by an edge define a two-element clique, while in the graph 
show in Figure 7 the vertices B, C and D along with the three edges connecting
them constitute a clique, and similarly with vertices C, D and E as a set.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{fig1_6.eps} 
\end{center}
\caption{\,}
\end{figure}

A clique with four elements can also be found in Figure 7, and its vertices 
are C, D, E, and F.

\begin{quote}
[Comment: those interested in a good source of more definitions and examples may want to explore [8] and [9]]. 
\end{quote}



\subsection{Clustering Algorithms Revisited: Graphical Versions}

With these definitions, it's now surprisingly easy to define the following two algorithms which use graphs, and which turn out -- as you will verify -- to give us precisely the single linkage and complete linkage clustering algorithms we have discovered and found useful under our original framework for looking at clustering problems. 

\begin{description}

\item \textbf{Graph-theoretic Single Linkage algorithm (GSL)}

\textbf{Step 1:} Begin with the disjoint clustering which places every 
object in its own separate cluster, i.e., for each $O_i\in O$, one forms the 
cluster $C_i =\{O_i\}$. Define the variable \emph{k} and initialize its value 
to zero. [Notice that the clustering defined in step 1 can be arrived at by 
defining the connected components of G(k) -- that is of G(0) since currently 
\emph{k} =0 -- to be the clusters].

\textbf{Step 2:} Increase the value of \emph{k} by 1. 

\textbf{Step 3:}
Using the threshold graph G(k), redefine the current clustering by letting 
each component of G(k) represent a cluster. If there is only one cluster, 
then stop. Otherwise, go to step 2. 

\item \textbf{Graph-theoretic Complete Linkage algorithm (GCL)}

\textbf{Step 1:} As before, let \emph{k} =0 and let the initial clustering be 
the one implied by the threshold graph G(0). 

\textbf{Step 2:}
Increase the value of \emph{k} by 1. 

\textbf{Step 3:}
Using the threshold graph G(k), redefine the current clustering to correspond 
to the cliques in G(k). That is, whenever two clusters from the previous stage
clustering, form a clique in G(k), they are merged into a single cluster. If 
there is only one cluster, then stop. Otherwise, go to step 2. 

\end{description}

To better understand the workings of Step 3, consider the threshold diagrams 
G(i) in the subsection, ``At the Threshold of Something New'' above. Starting 
at stage G(2) one has the clustering \{[AB], [CD], [E]\}, and this clustering 
remains the same through G(3) and G(4). 

Even when the algorithm looks at G(5) in Step 3, this same clustering is 
maintained. This is because although the nodes for [A], [D], and [E] can be 
seen as a ``clique,'' the algorithm \emph{only} tests whether the 
set-theoretic unions (combinations) \emph{of existing clusters }
are cliques in the new G(k). Yet clearly while one cannot obtain [ADE] by 
combining existing clusters. Similarly, the algorithm maintains the same 
clustering \{[AB], [CD], [E]\} even after examining G(6). However, upon 
looking at G(7), Step 3 of this algorithm would merge [AB] and [E] to obtain, 
\{[ABE], [CD]\}. \begin{center}

\begin{quote}
[Comment: See [JD] for more details on these graph-theoretical algorithms] 
\end{quote}

\end{center}



Recall that we are excluding ``ties'' in the dissimilarity matrix. With the dissimilarities being distinct, nothing is changed by assuming further that the values are all integers. Thus, only a single edge is added each time k is increased by 1. 


\textbf{\flushleft Exercise:}
Perform the algorithm GSL on the opening example of our five students and show that the resulting final clustering is the same as that given by the single linkage algorithm. In fact, show more: show that the entire series of nested clusterings is the same as for the single linkage hierarchical clustering algorithm. Do this by including and referring to each of the threshold graphs and indicating at each step (in writing or pictorially) what the connected components are, and what the resulting clusters are for each level of clustering (that is, at each threshold level). 


\textbf{\flushleft Exercise:}
You have just shown that GSL gives the same results as the original single linkage method in one particular case, namely for the opening example of five students. Now give a rigorous argument indicating why GSL will give a nested series of clusterings which is \emph{always}
 identical to that given by the single linkage algorithm. As always, your logical argument should be precise and detailed enough to convince a skeptical (but fair minded) fellow student. \emph{Suggestion:}
 Think about what the connected components are, and what their role in GSL corresponds to in the original algorithm. Then construct and spell out a detailed argument. 


\textbf{\flushleft Exercise:}
Perform GCL, the second of the two graphical algorithms above, on the opening example of our five students and show this time that the resulting final clustering is the same as that given by the complete linkage algorithm. Now prove more: that the entire series of nested clusterings is the same as for the complete linkage hierarchical clustering algorithm. Do this by including and referring to each of the threshold graphs and indicating at each step (in writing or pictorially) what the cliques are, and what the resulting clusters are for each level of clustering. 


\textbf{\flushleft Exercise:}
You have just shown that GCL gives the same results as the original complete linkage method in one particular case: for the opening example of five students. Now give a rigorous argument indicating why GCL will give a nested series of clusterings which is \emph{always}
 identical to that given by the complete linkage algorithm. \emph{Suggestion:}
 Think about what the cliques are, and what their role in GCL corresponds to in the original algorithm. Then write out your detailed argument which would convince a skeptical but fair-minded fellow student. 


\textbf{\flushleft Question:}
Can you suggest a reason why the complete linkage method is appropriately named? (\emph{Suggestion: }
review the definition of a clique). 


\textbf{\flushleft Remark:}
If one changes the specific numbers in the dissimilarity matrix, one says that the \emph{rank order}
 is unchanged if the relative sizes of pairs of entries remain unchanged (e.g., if the original number in the third row, second column, is bigger than the original number in the fourth row, first column, this remains true for the new numbers). You may have noticed that only the ``rank order'' the entries (numbers) in the dissimilarity matrix matters. Keeping the rank order, while modifying the specific numbers will produce the same output by SL and by CL, in other words. You may wish to prove that the output of SL (and likewise of CL) is invariant under an ``order preserving bijection'' changing the entries of the dissimilarity matrix. Consult with your instructor if you need help in defining an ``order preserving bijection''. \begin{verbatim}
\end{verbatim}























\section{Divisive Clustering}

Suppose that a group of 15 boys is to be separated into three groups to 
work on a certain project.  The person in charge of doing this has 
decided to simply group the boys based on where they live so that their 
parents can carpool.  Following the basic methods examined before we 
would have to go through many steps in order to get down to only three 
groups.

\textbf{\flushleft Exercise 1} 
Using an agglomerative method each step combines two previous clusters so
that there is now one fewer cluster than before.  If you start with 15 
boys and want to have three clusters, how many steps will it take using 
an agglomerative method?

In light of the amount of work needed to use these old methods for this 
problem it might be easier to use a method called divisive clustering.  
In agglomerative methods we start with each object in a separate cluster 
and combine clusters at each step.  Divisive clustering will do the 
opposite -- start with all the objects in one cluster and divide a 
cluster into two smaller clusters at each step.  Thus, in this particular
example we would start with all 15 boys in one cluster, split this 
cluster into two sub-clusters, and then split one of those sub-clusters 
again to form three total sub-clusters.  This requires only a two step 
process.

Let us actually demonstrate using a smaller example, where our goal is 
to form two clusters.

{\flushleft\textbf{Example 1} Suppose that five boys have measured how 
far it is between their houses and the results are listed below:}

\begin{table}[h]
\begin{center}
\begin{tabular}{c|ccccc}
Student: & & & & & \\
Bob & & & & & \\
Jim & 1.3 & & & & \\
John & 3.2 & 2.5 & && \\
Matt & 2.9 & 2.7 & 0.7 && \\
Steve & 3.5 & 4 & 2.2 & 1.6 & \\
\hline
distance to: & Bob & Jim & John & Matt & Steve \\
\end{tabular}
\end{center}
\end{table}

If we would like the maximum distance between any two boys in the same 
group to be as small as possible, and we don't wish to use an 
agglomerative method, then we see that we would like Jim and Steve to be 
in different groups because they live the farthest away from one another.
We will follow this type of reasoning to build up the two groups.  Once 
we have finished, we will have divided the entire group into two smaller 
groups. So, since we wanted Jim and Steve in different groups, we start 
with

\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
Group 1 \{Jim\} \> Group 2 \{Steve\}
\end{tabbing}

The next largest distance is between Bob and Steve, so we would also 
like them to be in different groups.  This means that Bob and Jim should 
be in the same group.

\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{Jim, Bob\} \> \{Steve\}
\end{tabbing}

Continuing on in this way we see that John and Bob are the next farthest 
apart.  So, we should put John in the group with Steve.

\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{Jim, Bob\} \> \{Steve, John\}
\end{tabbing}

Next, Bob and Matt should be in different groups, so we also put Matt in the group with Steve and John.

\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{Jim, Bob\} \> \{Steve, John, Matt\}
\end{tabbing}


Everyone is now in a group so we are done.  We have formed two groups with Matt, Steve, and John in one group and Bob and Jim in the other.  The largest distance between any two boys in the same group is 2.2 miles between John and Steve.

We can see from this example a method that we might follow to form groups of this kind.  However, there are some potential difficulties that did not arise in this example.  Let us examine a similar situation.  This time we will simply refer to the boys by the letters \textit{A} to \textit{E}.

{\flushleft\textbf{Example 2}}
\begin{table}[h]
\begin{center}
\begin{tabular}{c|ccccc}
\textit{A}\\
\textit{B} & 8\\
\textit{C} & 7 & 1\\
\textit{D} & 5 & 3 & 10\\
\textit{E} & 2 & 4 & 6 & 9\\
\hline
& \textit{A} & \textit{B} & \textit{C} & \textit{D} & \textit{E}\\
\end{tabular}
\end{center}
\end{table}


Starting as before, \textit{{C}}{ and }\textit{{D}}{ are the farthest apart so we should put them in different groups.  }

\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{\textit{C}\} \> \{\textit{D}\}
\end{tabbing}

{The next farthest apart are }\textit{{D}}{ and }\textit{{E}}{.  If we also put them in different groups this means that }\textit{{C}}{ and }\textit{{E}}{ must be in the same group.  }


\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{\textit{C, E}\} \> \{\textit{D}\}
\end{tabbing}

{Next, }\textit{{A}}{ and }\textit{{B}}{ should be in different groups.  However, it is not clear how to decide which group to put }\textit{{A}}{ in.  So, we will wait, and simply keep in mind that we plan to put these two in separate groups.  }

\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{\textit{C, E, A} or \textit{B}\} \> \{\textit{D, B} or \textit{A}\}
\end{tabbing}

{Here we write }\textit{{A }}{or }\textit{{B}}{ in one group and }\textit{{B}}{ or }\textit{{A}}{ in the other to indicate that we will either choose the first option both times (}\textit{{A}}{ in the first group and }\textit{{B}}{ in the second) or the second option both times (}\textit{{B}}{ in the first group and }\textit{{A}}{ in the second).}

{Next }\textit{{A}}{ and }\textit{{C}}{ should be separated so this tells us that we should choose the second option listed above.  Thus, the two groups are \{}\textit{{C}}{, }\textit{{E,}}{ }\textit{{B}}{\} and \{}\textit{{D, A}}{\}.  So, we see that sometimes we must wait to determine exactly which group to put certain elements in.  In a larger example, this type of problem may happen several times and be very difficult to keep track of.  }

{Another potential difficulty arises in the following example, which is quite similar to the last example.}

{\flushleft\textbf{{Example 3}}}
\begin{table}[h]
\begin{center}
\begin{tabular}{c|ccccc}
\textit{A}\\
\textit{B} & 5 \\
\textit{C} & 6 & 1 \\
\textit{D} & 8 & 3 & 10 \\
\textit{E} & 2 & 4 & 7 & 9 \\
\hline
& \textit{A} & \textit{B} & \textit{C} & \textit{D} & \textit{E} \\
\end{tabular}
\end{center}
\end{table}


{Again we start by placing }\textit{{C}}{ and }\textit{{D}}{ in separate groups.  }

\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{\textit{C}\} \> \{\textit{D}\}
\end{tabbing}

{Also, we need }\textit{{D}}{ and }\textit{{E}}{ in different groups so that once again }\textit{{C}}{ and }\textit{{E}}{ are together.  }

\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{\textit{C, E}\} \> \{\textit{D}\}
\end{tabbing}

{This time the next largest distance is between }\textit{{A}}{ and }\textit{{D}}{.  So, we put }\textit{{A}}{ in the group with }\textit{{C}}{ and }\textit{{E}}{.  }

\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{\textit{C, E, A}\} \> \{\textit{D}\}
\end{tabbing}

{Now comes the interesting step.  According to the pattern we have followed we should next put }\textit{{C}}{ and }\textit{{E}}{ in separate groups.  This is not possible unless we change the work done so far.  In a situation like this, we leave the groups as previously determined.  (In fact, we can conclude at this point that the largest difference between members of the same group will be 7, the distance between }\textit{{C}}{ and }\textit{{E}}{.)  We then continue on as before.  We would like }\textit{{A}}{ and }\textit{{C}}{ to be in different groups.  This is again not possible, so we skip to the next pair to be considered.  We would like }\textit{{A}}{ and }\textit{{B}}{ to be in different groups.  This works if }\textit{{B}}{ is put in the group with }\textit{{D}}{.  }


\begin{tabbing}
WWWWWWWWWWWWW \= aaaaaaaaaaaaaa \kill
\{\textit{C, E, A}\} \> \{\textit{D, B}\}
\end{tabbing}

{Note that we quit as soon as all five elements are assigned to groups.  So, our final groups are }\textit{{A, C, E}}{ and }\textit{{B, D}}{.}

{	Sometimes we will want to have more than two groups.  If this is the case we can repeat the procedure described above a second time on one of the newly formed groups.  }

{\flushleft\textbf{{Example 4 }}}{ Let us consider our original example of 15 boys.  Suppose the distances between their houses are given below.}

\begin{table}[h]
\begin{center}
\begin{tabular}{c|ccccccccccccccc}
A &&&&&&&&&&&&&&& \\
B& .6 &&&&&&&&&&&&&&\\
C& .6& 4.0 &&&&&&&&&&&&&\\
D& 5.5& .1& .5 &&&&&&&&&&&&\\
E& .8& 9.2& 8.0& .0 &&&&&&&&&&&\\
F& .7& 7.4& .2& .3& 6.4 &&&&&&&&&&\\
G& 5.3& .1& .0& 6.2& .5& .4 &&&&&&&&&\\
H& .5& 5.4& 5.1& .7& 8.3& 6.5& .2 &&&&&&&&\\
I& .0& 8.1& 7.5& .8& 4.1& 5.6& .4& 8.4 &&&&&&&\\
J& 6.0& .8& .0& 4.9& .0& .3& 4.2& .3& .9 &&&&&&\\
K& .7& 6.9& 7.3& .8& .4& 9.5& .2& 5.7& .7& .7 &&&&&\\
L& 6.1& .5& .9& 4.3& .8& .2& 3.0& .9& .1& 5.0& .6 &&&&\\
M& .9& 6.3& 4.4& .3& 7.2& 6.6& .9& 7.0& 9.0& .0& 8.6& .4 &&&\\
N& .2& .0& 8.7& .5& 4.5& 5.8& .7& 7.6& 4.7& .0& .9& .6& 7.1 &&\\
O& .6& 7.7& 6.8& .6& 4.8& 4.6& .9& 6.7& 5.2& .7& .8& .5& 8.9& 5.9 &\\
\hline
& A& B& C& D& E& F& G& H& I& J& K& L& M& N& O \\
\end{tabular}
\end{center}
\end{table}

{After going through the process described above once, we have the groups \{}\textit{{A, D, G, J, L}}{\} and \{}\textit{{B, C, E, F, H, I, K, M, N, O}}{\}.  Since we wish to have three groups we will now divide one of the groups again.  As we are trying to minimize the distances within groups we look at the largest distance between two boys in the same group.  Boys }\textit{{E}}{ and }\textit{{K}}{ live 14.4 miles apart and are in the same group.  So, we will split the second group into two by following the same procedure as before.  The result of this process is the groups \{}\textit{{B, C, H, K, M}}{\} and \{}\textit{{E, F, I, N, O}}{\}.  Putting these two groups with our other group from the first step we see that we have successfully separated the boys into three groups:  \{}\textit{{A, D, G, J, L}}{\}, \{}\textit{{B, C, H, K, M}}{\} and \{}\textit{{E, F, I, N, O}}{\}.  The largest distance between any two boys in the same group is now 8.6 miles.  (Note:  We were very lucky that the groups ended up equal in size.  There is nothing about this process that will guarantee this sort of result.)}





















\section{Divisive Clustering - Theory  (Optional)}
{In order to give a specific algorithm for the method used in the previous section we need several facts from graph theory.  Hence, we will begin this section with a brief introduction to the necessary concepts from graph theory.  Recall from the introductory section on agglomerative methods the definition of a graph, which we formalize here via set theory.}

{\flushleft\textbf{Definition}} A \textit{{graph}}{ is a pair  where }\textit{{V}}{ is a set and }\textit{{E}}{ is a set of pairs of elements of }\textit{{V}}{.  The elements of }\textit{{V}}{ are called }\textit{{vertices}}{ and the elements of }\textit{{E}}{ (which are pairs of vertices) are called }\textit{{edges}}{.  If a pair of vertices forms an edge, those two vertices are said to be }\textit{{adjacent.}}{ }

{\flushleft\textbf{Example 1}} If \textit{V} = \{\textit{A, B, C, D, E}\} and
\textit{E} = \{\{\textit{A, B}\}, \{\textit{A, C}\}, \{\textit{B, D}\}, 
\{\textit{C, D}\}, \{\textit{D, E}\}\}
then \textit{G} = (\textit{V, E}) is a graph that can be represented by dots and line segments, as in Figure 8:

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{fig2_1.eps}
\end{center}
\caption{\,}
\end{figure}

{\flushleft\textbf{Definition}}
A graph is said to be \textit{{connected}}{ if 
for any two vertices, }\textit{{v}}{ and }\textit{{w}}{, there is a 
sequence of vertices $v = v_1, v_2, \ldots, v_n = w$ such that each is 
an edge.  In other words, a graph is connected if there is a path through
the graph which passes through all its vertices.}

{\flushleft\textbf{Example 2}}
The graph in example 1 is connected (e.g. E, D, B, A, 
C is an appropriate path) but the graph in Figure 9 is not.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{fig2_2.eps}
\end{center}
\caption{\,}
\end{figure}

{\flushleft\textbf{{Definition}}}
{  A }\textit{{cycle}}{ is a sequence of vertices
\{$v_1, v_2, \ldots, v_n$\} 
such that each  
\{$v_i, v_{i+1}$\}
is an edge and also \{$v_1, v_n$\}  is an edge.}

{\flushleft\textbf{Example 3}} In the graph in example 1 the vertices 
\textit{{A, B, D, C}} form a cycle.

{\flushleft\textbf{{Definition}}}
{  A }\textit{{tree}}{ is a connected graph with no 
cycles.}

{\flushleft\textbf{{Example 4}}}
{ The graph in example 1 is not a tree because it contains
a cycle.  The graph in example 2 is not a tree because it is not connected.  
The graph in Figure 10 is a tree.}

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{fig2_3.eps}
\end{center}
\caption{\,}
\end{figure}

{\flushleft\textbf{{Definition}}} A 
\textit{{weighted graph}}{ is a graph together 
with a weight function which associates to each edge a real-valued weight.}

{\flushleft\textbf{{Example 5}}}
The graph in Figure 11 is the graph from example 1 with a weight function 
shown to make it a weighted graph.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{fig2_4.eps}
\end{center}
\caption{\,}
\end{figure}

{\flushleft\textbf{{Definition}}}{ Let $G = (V, E)$ be a weighted graph.  A }\textit{{
maximal weight spanning tree}}{ of }\textit{{G}}{ is a tree  on the same 
set of vertices as }\textit{{G}}{ with $E' \subseteq E$ such that the sum of 
the weights of the edges in $E'$ is as large as possible.}

{\flushleft\textbf{Example 6}}
In Figure 12 we show the maximal weight spanning tree of the weighted graph 
in example 5.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{fig2_5.eps}
\end{center}
\caption{\,}
\end{figure}

{Maximal weight spanning trees can be found by a fairly simple algorithm.  
Let }\textit{{G}}{ be the initial graph and }\textit{{H}}{ be the graph that 
is being constructed.}

\begin{enumerate}
\item Begin \textit{{H}}{ with all vertices of }\textit{{G}}{ and no edges}.
\item Let\{$u, v$\} be the edge of \textit{{G}}{ with the largest weight 
that has not been considered.}
\item If adding the edge \{$u, v$\} to \textit{{H}}{ will not complete a 
cycle, add that edge to }\textit{{H}}{.}
\item Repeat steps 2 and 3 until \textit{{H}}{ is connected.}
\end{enumerate}

{We give now a brief informal proof that this algorithm does what it claims 
to:  We can see that our tree is maximal weight by noting that at each step 
we add the edge with the largest weight that will not complete a cycle.  If a 
different edge were added, we would have to delete an edge that has a larger 
weight.  This would only reduce the total of the weights.  Further, we note 
that if }\textit{{H}}{ is not yet connected it must be possible to add and 
edge without completing a cycle.  This is true because if the }\textit{{H}}
{ is not connected there must be two vertices, say }\textit{{u}}{ and }
\textit{{v,}}{ that are not connected.  Adding edge \{$u, v$\} would 
therefore not complete a cycle.}

{\flushleft\textbf{Example 7}} 
Consider the weighted graph \textit{{G}} in Figure 13.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=1]{fig2_6.eps}
\end{center}
\caption{\,}
\end{figure}

The maximal weight spanning tree will be built up as in Figure 14.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{fig2_7.eps}
\end{center}
\caption{\,}
\end{figure}

{Next the side weighted 5 must be skipped because it would cause a cycle 
through }\textit{{B, C}}{, and }\textit{{E}}. So the final maximal spanning 
tree is as shown in Figure 15.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{fig2_8.eps}
\end{center}
\caption{\,}
\end{figure}


{To wrap up our excursion into graph theory, we also need the concept of a graph coloring.  To color a graph we assign a color to each vertex in such a way that if two vertices are adjacent, then they are assigned different colors.  It is easy to see that a tree will require only two colors.  To color a tree we simply start at any vertex and assign it a color.  All vertices adjacent to this vertex are assigned the second color.  All vertices adjacent to these are given the first color again.  We continue this pattern until all vertices are colored.  We can never ``come back'' to a vertex already colored and require it to be a different color because there are no cycles in a tree.}

{\flushleft\textbf{Example 8}}
The tree from example 4 can be colored as shown in Figure 16.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{fig2_9.eps}
\end{center}
\caption{\,}
\end{figure}

{Now, recall that we began all of this graph theory as an aid to understanding the algorithm for divisive clustering illustrated in the previous section.  Let us now give that algorithm.}

\medskip

\begin{large}
\flushleft
Algorithm for divisive clustering:
\end{large}
\begin{enumerate}
\item {Given a set of elements with a dissimilarity (or ``distance'') 
function, form a complete, weighted graph as described below:}
\begin{enumerate}
\item {Consider each of the original elements as a vertex}
\item {Include all possible edges (so the graph is complete)}
\item {Define the weight of an edge to be the dissimilarity of the vertices}
\end{enumerate}
\item {Find a maximal spanning tree of the weighted graph.}
\item {Color the maximal spanning tree.}
\item {Divide the original set so that all vertices of the same color are in 
the same part.}
\end{enumerate}

{Note that with this algorithm we do not have partial, or tentative, groups along the way as we did when following our intuitive idea of divisive clustering in the previous section.  At step 4 above the entire group is divided into two groups all in one step.}

{\flushleft\textbf{Example 9 }}
Using the same data as from example 2 in the previous section we have

\begin{table}[h]
\begin{center}
\begin{tabular}{c|ccccc}
\textit{A} \\
\textit{B} & 8 \\
\textit{C} & 7 & 1 \\
\textit{D} & 5 & 3 & 10 \\
\textit{E} & 2 & 4 & 6 & 9 \\
\hline
& \textit{A} & \textit{B} & \textit{C} & \textit{D} & \textit{E} \\
\end{tabular}
\end{center}
\end{table}

Applying the algorithm, we build the maximal spanning tree as show in figure 17. (Note that, in practice, we need not actually draw the original weighted graph, or even use all of the vertices at the start.)

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{fig2_10.eps}
\end{center}
\caption{\,}
\end{figure}

{Then coloring the tree gives the final tree as in Figure 18}

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{fig2_11.eps}
\end{center}
\caption{\,}
\end{figure}


{Hence, the two groups are \{}\textit{{A, D}}{\} and \{}\textit{{B, C, E}}{\} as we saw before.}

\section{Sequential Clustering}

The clustering procedures described above assign all the given entities to 
clusters. This completeness is necessary in many applications -- see, for 
example, [JD]. However, there are a lot of problems where we do not have to 
build a complete partition of a given set \textit{O}. Thus, in problems of 
image recognition we are to single out only \textit{some} images-clusters off 
the background. For instance, let a space shuttle rotate around Mars and look 
for an invisible (``sleeping'') landing device. A radar is scanning the 
surface and a computer program analyses this picture, pixel by pixel, and 
tries to combine raw elements in meaningful \textit{clusters}, using the 
algorithm prescribed. After discovering a possibly human-made structure of 
straight lines and circles, the computer can quit its search over the 
surrounding area, at least temporarily.

In this section, following P. Hansen, B. Jaumard, and N. Mladenovic [HJM], we 
consider a corresponding paradigm of cluster analysis, called \textit{sequential 
clustering.} In sequential clustering we do not initially assign all the objects 
to single-element clusters as in agglomerative clustering, and we do not initially
split \textit{O }in two clusters as in divisive clustering. Rather, we look for a
most naturally separated (in a precisely defined sense) subset of the initially 
given set \textit{O}, and designate it as the first cluster C$_1$. Then we remove
\textit{C}$_1$ from \textit{O} and repeat this procedure starting with the 
\textit{set-difference}\footnote{Here "$\backslash$" denotes the set-difference, 
that is, 
A$\backslash$B  is the set of all objects which are in  A but do not 
belong to B.} 
\textit{O}\ensuremath{\backslash}\textit{C}$_{\rm{}1}$. The algorithm stops when 
the last set-difference exhibits no relevant internal structure (or it is empty).
This approach is useful in many instances, for example, in image recognition 
[MAM]. Moreover, unlike the hierarchical clustering, this approach does not 
\textit{a priori }impose a definite structure, such as a hierarchy of partitions,
on the clustering being constructed.

First, we derive an algorithm of sequential clustering in a naive way, applying it to the very first example from another module in this series [K].   

{\flushleft\textbf{Example 1.}} Consider\textbf{ }a set of eight entities O = \{\textit{O}$_1$,\textit{ O}$_2$, \textit{O}$_3$ \textit{O}$_4$, \textit{O}$_5$, \textit{O}$_6$, \textit{O}$_7$, \textit{O}$_8$\} and their dissimilarity table:

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
& $O_1$& $O_2$& $O_3$& $O_4$& $O_5$& $O_6$ & $O_7$ & $O_8$\\
\hline
$O_1$ & 0 &&&&&&&\\
\hline
$O_2$ & 5 & 0 &&&&&&\\
\hline
$O_3$ & 10 & 8 &0 &&&&&\\					
\hline
$O_4$ & 7 & 12 & 1 & 0 &&&&\\
\hline
$O_5$ & 22 & 28 & 9 & 4 & 0 &&&\\
\hline
$O_6$ & 27 & 23 & 19 & 14 & 11 & 0 &&\\
\hline
$O_7$ & 25 & 17 & 3 & 2 & 16 & 15 & 0 &\\
\hline
$O_8$ & 13 & 6 & 26 & 21 & 18 & 20 & 24 & 0\\
\hline
\end{tabular}
\end{center}
\caption{The dissimilarity table for the model example}
\end{table}



The graph in Figure 19 gives a partial representation of this example. The vertices here correspond to the entities and the weights of the edges (not all of them are shown) are the dissimilarities between the entities. Certainly, there are many ways to draw these graphs manually. However, algorithm, presented later on, eliminates this arbitrariness. Here, we have tried to draw the edges shorter if they carry smaller dissimilarities. This allows us to inspect the initial configuration visually:

\begin{figure}[h]
\begin{center}
\includegraphics{fig3_1.eps}
\end{center}
\caption{Initial configuration. Some of larger dissimilarities ($>$ 6) 
are not shown.}
\end{figure}

We immediately observe three nearby vertices \textit{O}\textit{$_{\rm{}3}$}$_{
\rm{},}$ \textit{O}\textit{$_{\rm{}4}$}, and \textit{O}\textit{$_{\rm{}7 }$} and 
separate them in the cluster \textit{C}\textit{$_{\rm{}1}$} =\{
\textit{O}\textit{$_{\rm{}3}$}$_{\rm{},}$ \textit{O}\textit{$_{\rm{}4}$}, 
\textit{O}\textit{$_{\rm{}7}$}\}. We do not include the vertex \textit{O}$_5$ 
in this cluster, since its distances from \textit{O}\textit{$_{\rm{}3}$} 
and O\textit{$_{\rm{}7}$} are considerably larger than 
those within \textit{C}\textit{$_{\rm{}1}$}. We will return to this issue later. 
Removing \textit{C}\textit{$_{\rm{}1 }$} from this graph, we get a configuration 
in Figure 20, where a few more edges are shown.

\begin{figure}[h]
\begin{center}
\includegraphics{fig3_2.eps}
\end{center}
\caption{Configuration after removing the cluster \textit{C}$_1$}
\end{figure}

Observing the proximity of \textit{O}\textit{$_{\rm{}1}$},\textit{ O}\textit{$_{\rm{}2}$}, and O\textit{$_{\rm{}8}$}$_{\rm{} }$\textit{$_{\rm{} }$}to each 
other, we may form another cluster 
\textit{C}\textit{$_{\rm{}2}$} = \{\textit{O}\textit{$_{\rm{}1}$},\textit{ O}\textit{$_{\rm{}2}$}, \textit{O}\textit{$_{\rm{}8}$}\}.  Removing it, we arrive 
at Figure 21.

\begin{figure}
\begin{center}
\includegraphics{fig3_3.eps}
\end{center}
\caption{Configuration after removing the clusters \textit{C}$_1$ and 
\textit{C}$_2$}
\end{figure}

Finally, we can either combine the two remaining entities O\textit{$_{\rm{}5}$}and \textit{O}\textit{$_{\rm{}6  }$} in a cluster \textit{C}\textit{$_{\rm{}3}$}, or we can leave them unassigned. It is interesting to compare our ``naive'' approach with other clustering algorithms. For example, when the Single Link Algorithm is applied to the same example (see [K]), the cluster \textit{C}\textit{$_{\rm{}1 }$} emerges at the second level of clustering, the cluster \textit{C}\textit{$_{\rm{}2 }$} appears at the fifth level, and the entities \textit{O}\textit{$_{\rm{}5}$} and \textit{O}\textit{$_{\rm{}6 }$} meet one another only at the last, seventh step, in the \textit{conjoint} clustering, when all entities are in one cluster.

Obviously, in this example we have made some ``arbitrary'' decisions. For example,
at the very first step we could have immediately removed a cluster  
$\hat{C}_1$ = \{
\textit{O}\textit{$_{\rm{}3}$}$_{\rm{},}$ \textit{O}\textit{$_{\rm{}4}$}, 
\textit{O}\textit{$_{\rm{}5}$},\textit{ O}\textit{$_{\rm{}7}$}\} instead of 
\textit{C}\textit{$_{\rm{}1}$}. To avoid this arbitrariness, our decisions must 
be based on clearly stated criteria regarding the proximity of entities. Such 
criteria may change from step to step, that is, the criterion we use to choose the first cluster \textit{C}\textit{$_{\rm{}1}$},\textit{$_{\rm{} }$} may differ from the criterion we use to find \textit{C}\textit{$_{\rm{}2}$}, etc.; these criteria are called \textit{local} \textit{algorithms} and are denoted by \textit{A}\textit{$_{\rm{}k}$}\textit{, k }= 1, 2,\ldots . The following examples will show why we may prefer using different local algorithms at consecutive steps in the same clustering problem.



Even if we separate just a one-element cluster at each step, the maximum number, 
\textit{s}, of steps can not exceed the number of objects in \textit{O} less one, 
in symbols, $s\leq |O| - 1$. Hereafter, the notation $|X|$ stands for the number 
of elements in a set \textit{X}. This number is also called the \emph{cardinal 
number} or cardinality of X.  For example, the cardinal number of the set of all 
characters in the English alphabet is 26, that is, $|$\{a, b, c,\ldots, x, y, 
z\}$|$ = 26. Hereafter, we denote by \emph{N} the \emph{cardinal number} of a 
sample  \textit{O}, $N = |O|$, and by \textit{K } the number of entities in a 
cluster \textit{C}, $K = |C|$.

We also use the following standard notation. The writing a:= \textit{b }means 
that a variable a is \textit{assigned} a value b.  For example, if  \textit{b} = 
3, then after executing the command \textit{a} := \textit{b} the new value of  
\textit{a} is 3, and this value does not depend upon the preceding value of  
\textit{a}. Furthermore, we recall that the notation 
max$\{d_l | l \in L\}\equiv \mbox{max}_{i \in l}\ d_l$, 
where a dummy index $l$ runs over the index set \textit{L}, and similarly 
min$\{d_l | l \in L\}$ or min$_{i \in l}\ d_l$, 
were introduced in the subsection \textit{Single and Complete Linkage: the Inside 
Scoop. }Thus, max$_l\,d_l$  means that among several given quantities $d_l$ with 
different subscripts l, we look for (one of) the largest $d_l$ and denote it by  
max\{$d_l | l \in L$\}
or just
max$_l\ d_l$.
There may be \textit{several equal largest} $d_l$. If l stands for the indexes of 
elements $O_l \in C$ of a set \textit{C}, we denote this maximum by 
max\{$d_l | O_l \in C$\} and read this expression as ``\textit{The maximum of all 
of the quantities $d_l$ over all subscripts l such that $O_l \in C$.}''



Formalizing our considerations, we arrive at the following formal procedure called a \textit{sequential clustering algorithm. }It is written in a so-called \textit{pseudocode }format. In the following algorithm, we gradually remove some entities from the original set \textit{O}. At every step, \textit{S} contains unassigned entities, and \textit{C}\textit{$_{\rm{}k }$}is the cluster we remove from the set of remaining objects. The set R contains the unassigned entities when the algorithm halts. 



{\flushleft\textbf{Sequential Clustering Algorithm.}} Given a finite sample \textit{O}, its dissimilarity table, and a set of local algorithms \textit{A}\textit{$_{\rm{}k}$}\textit{, k }= 1...$|O|$ -  1. 

\begin{enumerate}
\item Initialization. Set  \textit{k} := 0, \textit{S} := \textit{O}, and 
\textit{R} := \textit{O}.
\item Loop.  Set \textit{k} := \textit{k} + 1.
\begin{description}
\item [] Apply a local algorithm \textit{A}\textit{$_{\rm{}k }$}to the set Sto find$_{\rm{} }$\textit{C}\textit{$_{\rm{}k}$}$_{\rm{}.}$
\begin{description}
\item [] If \textit{A}\textit{$_{\rm{}k}$} fails, update\textit{R}:=\textit{S and} End.
\item [] Else: record C\textit{$_{\rm{}k}$} and update \textit{S}:= \textit{S}
\ensuremath{\backslash}\textit{C}$_{\rm{} }$\textit{$_{\rm{}k}$}.
\item [] End If
\end{description}
\item [] End Loop.
\end{description}
\item End.
\end{enumerate}


{\flushleft\textbf{Remark.}} We may need fewer than $|O| - 1$ local algorithms.



To apply this algorithm, we must specify local algorithms \textit{A}\textit{$_{\rm{}k}$}. To this end, we have to take into account both the specifics of the problem under consideration and the general philosophy of cluster analysis, that is, getting reasonably homogeneous and wellseparated clusters. Here, a cluster is said to be homogeneous if the dissimilarities between its elements are close to each other --- of course, the latter is not a precise definition of the homogeneity. In the same style, two clusters are said to be well separated, if the dissimilarity for each pair of elements within either of these clusters is less than any dissimilarity between an element in one cluster and an element in another cluster. Appropriate local algorithms are often based on the concepts such as the \textit{diameter}, \textit{radius}, and \textit{split} of a set $C \subset O$.  The diameter and the radius estimate homogeneity of clusters.  



{\flushleft\textbf{Definition 1.}} The \textit{diameter}, $d(C)$, of a set 
$C \subset O$ is the largest dissimilarity between a pair of entities of 
\textit{C}, that is,  
$$d(c) = \max \{\{\max\ d_{kl} | O_l \in C\} | O_k \in C\}$$
or, which is the same,
$$d(C) = \max \{d_{kl} | O_k \in C, O_l \in C\}.$$

Before considering examples, let us note that the latter expression may look simpler, 
but the former is simpler in calculations. The first formula defines the diameter as 
the reiterated maximum of all the dissimilarities between pairs of objects in \textit{C}. That means that initially we fix (``freeze'') the first subscript k and calculate 
$\max\{d_{kl} | O_l \in C\}$ with this fixed k; here $O_l$ runs over all possible 
subsets of $C$. For example, if k=1, we calculate $\max\{d_{1l} | O_l \in C\}$. Then we 
fix next k and calculate $\max\{d_{kl} | O_l \in C\}$ with this new fixed k. Thus, if 
k=2, we look for $\max\{d_{2l} | O_l \in C\}$. This way, we find as many numbers 
$\max\{d_{kl} | O_l \in C\}$ as there are various values of the parameter k and then we 
select the largest among these numbers $\max\{d_{kl} |O_l \in C\}$. Precisely this 
largest quantity is denoted by $d(C) = \max \{\{\max d_{kl} | O_l \in C\} | O_k \in C\}$.



{\flushleft\textbf{Example 2.}} The graph in Figure 22 
represents the very first 
example in our module --- the five students A, B, C, D, and E, denoted here by
\textit{o}\textit{$_{\rm{}1}$}, \textit{o}\textit{$_{\rm{}2}$},
\textit{o}\textit{$_{\rm{}3}$}, \textit{o}\textit{$_{\rm{}4}$},
\textit{o}\textit{$_{\rm{}5}$}, and the distances between their residences:

\begin{figure}[h]
\begin{center}
\includegraphics{fig3_4.eps}
\end{center}
\caption{Graph corresponding to the initial example.}
\end{figure}

Again, we can visually observe in the set \textit{O =} 
\{\textit{O}\textit{$_{\rm{}1}$},\textit{ O}\textit{$_{\rm{}2}$},
\textit{ O}\textit{$_{\rm{}3}$},\textit{ O}\textit{$_{\rm{}4}$},
\textit{ O}\textit{$_{\rm{}5}$}\} two clusters:  
\textit{C}\textit{$_{\rm{}1}$}= \{\textit{O}\textit{$_{\rm{}1}$},
\textit{ O}\textit{$_{\rm{}2}$}\} and \textit{C}\textit{$_{\rm{}2}$}= 
\{\textit{O}\textit{$_{\rm{}3}$},\textit{ O}\textit{$_{\rm{}4}$},
\textit{ O}\textit{$_{\rm{}5}$}\}. It should be noted that this clustering 
results also from the single linkage clustering algorithm applied to 
\textit{O} --- see \textit{The Missing Links} Section. But now we want to 
proceed in a more systematic way using the sequential clustering paradigm. 
To this end, next we calculate the diameters of these clusters. The set 
\textit{C}\textit{$_{\rm{}1 }$} contains only two elements, therefore, for 
both \textit{k} = 1 and \textit{k} = 2, $\max \{ d_{1l} | O_l \in C\}$
= $\max \{ d_{2l} | O_l \in C\}$ = 1 and 
$d(C_1) = \max \{\{\max d_{kl} | O_l \in C_1\} | O_k \in C1\} = 
\max\{l,l\} = 1$.
Further, for \textit{C}\textit{$_{\rm{}2}$} we calculate 
$\max \{ d_{3l} | O_l \in C_2\} = \max \{ d_{3,4}, d_{3,5}\}
= max \{ 2, 9\} = 9$,
$\max \{ d_{4l} | O_l \in C_2\} = \max \{2,3\} = 3$,
$\max \{ d_{5l} | O_l \in C_2\} = \max \{3,9\} = 9$,
and finally 
$d(C_2) = \max \{3,9,9\} = 9$.
In Section 1, we arrived at the same clustering and calculated the same 
quantities in a quite different way, by making use of the Single Link 
Algorithm. To avoid misunderstanding, it should be said that, unlike the 
definition of dissimilarity between two clusters involving the repeated 
minimum, the definition of the diameter of a subset involves only 
\textit{one} set and uses the repeated maximum.

\textbf{\flushleft Pause for thought. }Try to describe the Single Link Algorithm in terms of the diameters of clusters.

It should be said again that Definition 1 can be written using one maximum: 
$d(C) = \max \{ d_{kl} | O_k \in C, O_l \in C\}$,
which makes apparent the choice of the term \textit{diameter}. However, we 
often prefer the first formula, since we cannot avoid repeating symbols of 
maximum and minimum in the two following definitions. The radius is the 
smallest maximum among all the dissimilarities between pairs of objects in 
\textit{C}. 

\textbf{\flushleft Definition 2.} The \textit{radius} of a set $C \subset O$
is
$$r(C) = \min \{ \max \{ d_{kl} | O_l \in C\} | O_k \in C\}.$$
\textbf{\flushleft Exercise 1.} Prove or disprove that $\min\{\max d_{kl}\}
= \max \{ \min d_{kl}\}$ for any rectangular table $[d_{kl}]$.

Let us reconsider Example 2 (Figure 22). For the same 
\textit{C}\textit{$_{\rm{}1}$} we again have 
$\max \{ d_{1l} | O_l \in C_1\} = 
\max \{ d_{2l} | O_l \in C_2\} = 1$.
Thus, $r(C_1) = \min \{ \max \{ d_{kl} | O_l \in C1\} |O_k \in C_l\}
= \min \{1,1\} = 1$. It is worth noting that in our usual plane geometry the 
diameter of a circle is twice the radius. However, it is not always the case 
in our current ``discrete world'' under exploration. It might even happen that
the radius and the diameter of a set coincide. Thus, the diameter of 
$C_2$ (see above) is three times its radius: $r(C_2) = \min \{3,9,9\} = 3$. 
Comparing this calculation with Figure 4, we get a clearer understanding why 
this quantity is called the radius of a set. Obviously, the vertex 
\textit{O}\textit{$_{\rm{}4}$} can be viewed as the center of the set 
\textit{C}\textit{$_{\rm{}2}$} and all the other vertices in 
\textit{C}\textit{$_{\rm{}2}$} are apart from 
\textit{O}\textit{$_{\rm{}4}$} for at most 3 units.



The last definition of this section concerns the separation of a subset from 
other subsets --- the quantity to be defined measures how far a set 
\textit{C }is `split off' from the rest of the sample.


\textbf{\flushleft Definition 3.} The \textit{split},$s(C)$, of a set 
$C \subset O$ is the smallest dissimilarity between a pair of entities, 
one in \textit{C} and another in O\ensuremath{\backslash}\textit{C}, that is,  
$$s(C) = \min \{ \min \{ d_{kl} | O_l \not \in C\} | O_k \in C\}.$$

It is worth repeating: the outer minimum is taken over all subsets belonging
\emph{to C}, while the inner minimum is taken over all subsets that \textit{do not belong} to \emph{C}. 


We continue studying the same example (Figure 22). For 
\textit{C}\textit{$_{\rm{}1}$},  
$\min \{ d{1l} | O_l \not \in C\} = 
\min \{4,5,8\} = 4$
and 
$\min \{ d_{2l} | O_l \not \in C_l\} = 
\min \{10, 6, 7\} = 6$.
Therefore,  
$s(C_l) = \min \{ \min \{ d_{kl} | O_l \not \in C_1\} | O_k \in C_1\}
= min \{4, 6\} = 4$.
For \textit{C}\textit{$_{\rm{}2}$}, we have   
$\min \{ d_{3l} | O_l \not \in C_2\} = 
\min \{8, 10\} = 8$,
$\min \{d_{4l} | O_l \not \in C_2\} =
\min \{5, 8\} = 5$,
$\min \{ d_{5l} | O_l \not \in C_2\} =
\min \{4, 7\} = 4$,
and finally
$s(C_2) = \min \{8, 5, 4\} = 4$.
In this example, since we have exactly two clusters, 
$s(C_1) = s(C_2)$.

\textbf{\flushleft Exercise 2.} Suppose, in a problem we have exactly two 
clusters, \textit{C}\textit{$_{\rm{}1}$} and \textit{C}\textit{$_{\rm{}2}$}. 
Is it always the case that their splits are equal, $s(C_1) = s(C_2)$?

These three concepts --- the diameter, radius, and split give rise to the 
following commonly used local algorithms. We define three quantities, the 
\textit{minimum diameter}, the \textit{minimum radius}, and the 
\textit{maximum split}. In these definitions maximum or minimum is taken over 
all subsets $C \subset O$ containing exactly \textit{K} entities, where a 
number \textit{K} is to be the size of a cluster we desire to have:

\begin{center}
\begin{tabular}{lll}
A) & Minimum diameter: & $d_{\mbox{min}}(O,K) = \min \{d(C) | C \subset O, |C| = K\}$ \\
B) & Minimum radius: & $r_{\mbox{min}}(O,K) = \min \{r(C) | C \subset O, |C| = K\}$ \\
C) & Maximum split: & $s_{\mbox{max}}(O,K) = \max \{s(C) | C \subset O, |C| = K\}$. \\
\end{tabular}
\end{center}

We repeat that in each of these three definitions the extremum is taken over all 
\textit{K}--element subsets $C \subset O$, $|C| = K$, and only the specifics of a 
problem dictate our choice of \textit{K}.

To illustrate these local criteria, we apply them to our Example 1.  We start with the 
case A), i.e., we want to minimize the diameters of removed clusters.

A) If we want to separate firstly only \textit{two} entities in a cluster, we set  
$K = |C| = 2$. Obviously, the smallest  diameter  among  all  2--element  subsets  of 
\textit{O} is 1,  that is, $d_{\mbox{min}}(O,2) = 1$,  and this value is attained if 
\textit{C} = \{\textit{O}\textit{$_{\rm{}3}$}, \textit{O}\textit{$_{\rm{}4}$}\}. 
However, if at the very first step we want to remove \textit{three} entities, that is, 
if we consider initially $K = |C| = 3$, then $d_{\mbox{min}}(O,3) = 3$ and this value 
is attained if C = \textit{C}\textit{$_{\rm{}1}$}\textit{ = }
\{\textit{O}\textit{$_{\rm{}3}$}, 
\textit{O}\textit{$_{\rm{}4}$},
\textit{ O}\textit{$_{\rm{}7}$}\}. 
Suppose, to proceed faster, we wish to start with K = 3.

After removing this \textit{C}\textit{$_{\rm{}1}$}\textit{ = }\{
\textit{O}\textit{$_{\rm{}3}$}, \textit{O}\textit{$_{\rm{}4}$},
\textit{ O}\textit{$_{\rm{}7}$}\} from \textit{O}, if we apply the same algorithm 
with \textit{K} = 3 to the set  
\textit{O}\ensuremath{\backslash}\textit{C}\textit{$_{\rm{}1}$}, 
we obtain a cluster \textit{C}\textit{$_{\rm{}2}$} = \{\textit{O}\textit{$_{\rm{}1}$},
\textit{ O}\textit{$_{\rm{}2}$}, \textit{O}\textit{$_{\rm{}8}$}\}, that is, 
we repeat the results of our intuitive approach (see above). Suppose, however, 
that at the second step we realize that the next three objects are not close enough 
for our purpose and we decide to change a local criterion. Let us choose now 
\textit{K} = 2. Then, since the object \textit{O}\textit{$_{\rm{}4}$} was removed 
in a previous step,the recalculated (with this new \textit{K}) minimal diameter is 
$d(C_2) = 5$, where C`$_{\rm{}2}$\textit{ = }\{\textit{O}\textit{$_{\rm{}1}$}, 
\textit{O}\textit{$_{\rm{}2}$}\}.  The configuration after removing \textit{this} 
\textit{= }\{\textit{O}\textit{$_{\rm{}1}$}, \textit{O}\textit{$_{\rm{}2}$}\} from 
\textit{O}\textit{$_{\rm{}new}$} = 
\textit{O}\ensuremath{\backslash}\textit{C}\textit{$_{\rm{}1}$} is shown in Figure 23.

\begin{figure}[h]
\begin{center}
\includegraphics{fig3_5.eps}
\end{center}
\caption{Configuration after removing the cluster $C`_2$.}
\end{figure}

Now we can either repeat a similar step with \textit{K} = 2, or we can again 
change a local criterion to \textit{K} = 3, or we can leave the three remaining 
entities \textit{O}\textit{$_{\rm{}5}$},\textit{ O}\textit{$_{\rm{}6}$}, 
\textit{O}\textit{$_{\rm{}8}$} unclustered.  The decision, what local algorithm 
to choose during the run of the sequential clustering algorithm, can be made only 
after a consultation with an expert in the field where the problem arose. In the 
end of this section we consider again Example 2, using sequential clustering, and 
we shall see why it may be useful to change the value of Kas part of solving the 
same problem.

\textbf{\flushleft Exercise 3.} Describe all clusters in this example, when we 
use all possible combinations of local criteria based on the minimal diameter 
with  \textit{K} = 2, \textit{K} = 3, and \textit{K} = 4. That is, give an answer 
consisting of the entire collection of clusters corresponding to each possible 
series of choices of \textit{K}.

B) Let us now work the same example, using the minimum radius as a local criterion. 
If  \textit{K} = 2, then clearly $r_{min}(O,2) = 1$ and this value is attained at 
\textit{C} = \{\textit{O}\textit{$_{\rm{}3}$}, \textit{O}\textit{$_{\rm{}4}$}\}. 
On the other hand, if at the very first step we want to remove three entities,  
that is, we set $K = |C| = 3$, then, attained at \textit{C}$_{\rm{}1}$ =
\{\textit{O}\textit{$_{\rm{}3}$}, \textit{O}\textit{$_{\rm{}4}$},
\textit{ O}\textit{$_{\rm{}7}$}\}, since
$$\min\{
\max\{d_{3,l}|O_l\in C_1\}, 
\max\{d_{4,l}|O_l\in C_1\},
\max\{d_{7,l}|O_l\in C_1\}\}
=\min\{3;2;3\} = 2$$

and no other three-element subset has the radius 2 or less. If we continue to 
use the criterion with  $K = |C| = 3$, then the next three-element cluster to 
be removed is \textit{C}\textit{$_{\rm{}2}$} = \{\textit{O}\textit{$_{\rm{}1}$},
\textit{ O}\textit{$_{\rm{}2}$}, \textit{O}\textit{$_{\rm{}8}$}\} with the 
minimal radius $r_min(O\setminus C_1, 3) = r(C_2) = 6$.  Therefore, we arrive 
at the same clustering as in A).


\textbf{\flushleft Exercise 4.} Describe all clusterings in this example, that 
is, give an answer consisting of the entire collection of clusters, when we use 
all possible combinations of local criteria based on the minimal radius with  
\textit{K} = 2, \textit{K} = 3, and \textit{K} = 4.

C) We now apply the maximum split as a local criterion. Unlike the cases A) and B), 
where we looked for densely tied clusters, here we look for relatively disengaged 
clusters. If $K$ = 2, there are two twoelement subsets with the same maximal split, 
$s_{max}(O,2) = 6$. One of these two clusters is $\{O_1, O_2\}$.

\textbf{\flushleft Exercise 5.} Verify that $s(\{O_1, O_2\}) = 6$ and find another 
cluster with the same maximal split $s = 6$.

Removal of either such cluster leads to different clusterings and only by knowing 
the specifics of the problem, can we decide which cluster is to be removed first. 
For instance, if we remove \textit{C}\textit{$_{\rm{}1}$}\textit{ = }
\{\textit{O}\textit{$_{\rm{}1}$}, \textit{O}\textit{$_{\rm{}2}$}\}, we get the 
configuration in Figure 24.

\begin{figure}[h]
\begin{center}
\includegraphics{fig3_6.eps}
\end{center}
\caption{Configuration after removing \textit{C}\textit{$_{\rm{}1}$}\textit{ =}\{\textit{O}\textit{$_{\rm{}1}$}, \textit{O}\textit{$_{\rm{}2}$}\}. Not all edges are shown}
\end{figure}

The next maximum split with \textit{K} = 2 is  $s(C_2) = 11$, where again 
\textit{C}\textit{$_{\rm{}2}$} = \{\textit{O}\textit{$_{\rm{}6}$},
\textit{ O}\textit{$_{\rm{}8}$}\}.  Removing \textit{C}\textit{$_{\rm{}2}$}, 
we arrive at the configuration in Figure 25.

\begin{figure}[h]
\begin{center}
\includegraphics{fig3_7.eps}
\end{center}
\caption{Configuration after removing \textit{C}\textit{$_{\rm{}2}$}\textit{ = }\{\textit{O}\textit{$_{\rm{}6}$}, \textit{O}\textit{$_{\rm{}8}$}\}}
\end{figure}

Here, the maximum split with \textit{K} = 2 is 
$s_{max}(O`\setminus C_2) = s(C_3) = 3$, where $O` = O\setminus C_1$ and  
\textit{C}\textit{$_{\rm{}3}$} = \{\textit{O}\textit{$_{\rm{}3}$},
\textit{ O}\textit{$_{\rm{}4}$}\}. Removing \textit{C}\textit{$_{\rm{}3}$}, we 
arrive at the final configuration (Figure 26) that can be viewed as a cluster 
\textit{C}\textit{$_{\rm{}4}$} = \{\textit{O}\textit{$_{\rm{}5}$},
\textit{ O}\textit{$_{\rm{}7}$}\}. Otherwise, we can leave these two entities 
unassigned to any cluster, if these entities are irrelevant for our analysis. We 
see that using a local criterion based on the maximum split leads to a clustering 
completely different from the cases A) or B).


\begin{figure}[h]
\begin{center}
\includegraphics{fig3_8.eps}
\end{center}
\caption{Configuration after removing $C_3 = \{O_3, O_4\}$.}
\end{figure}

\textbf{\flushleft Exercise 6.} Describe all clusterings in this example, that is, 
give an answer consisting of the entire collection of clusters, when we use all 
possible combinations of local criteria based on the maximum split with 
\textit{K} = 2, \textit{K} = 3,  and  \textit{K} = 4. 

\textbf{\flushleft Example 2 Revisited.} We discuss Example 2 again using now the 
local criterion A), that is, we strive to minimize the diameters of the clusters. 
Since in this problem only two-element and three-element clusters are acceptable, 
we start with the value \textit{K} = 2. So the very first cluster is anew 
\textit{C}\textit{$_{\rm{}1}$}= \{\textit{O}\textit{$_{\rm{}1}$},
\textit{ O}\textit{$_{\rm{}2}$}\} with $d(C_1) = 1$. In the set 
\textit{O}\ensuremath{\backslash}\textit{C}\textit{$_{\rm{}1}$}= 
\{\textit{O}\textit{$_{\rm{}3}$}\textit{, O}\textit{$_{\rm{}4}$}\textit{, 
O}\textit{$_{\rm{}5}$}\}, a twoelement cluster with the smallest diameter is 
\textit{C}\textit{$_{\rm{}2}$}= \{\textit{O}\textit{$_{\rm{}3}$},
\textit{ O}\textit{$_{\rm{}4}$}\} with.  Again, since only two-element and 
three-element clusters are acceptable, we must assign now the fifth element  
\textit{O}\textit{$_{\rm{}5  }$} to either \textit{C}\textit{$_{\rm{}1 }$} or 
\textit{C}\textit{$_{\rm{}2}$}. Thus, we have to reconsider a local algorithm. 
We apply now the same criterion A) but with the value \textit{K }= 3, that is, 
we have to calculate the diameters of two possible threeelement subsets: 
\textit{C`}\textit{$_{\rm{}1}$}= \{\textit{O}\textit{$_{\rm{}1}$},
\textit{ O}\textit{$_{\rm{}2}$}, \textit{O}\textit{$_{\rm{}5}$}\} or 
\textit{C}`\textit{$_{\rm{}2}$}= \{\textit{O}\textit{$_{\rm{}3}$},
\textit{ O}\textit{$_{\rm{}4}$}, \textit{O}\textit{$_{\rm{}5}$}\}.  
Since $d(C`_1) = 7$ is less than $d(C_2) = 9$, the resulting clustering is 
\{\textit{ C}`\textit{$_{\rm{}1}$},\textit{ C}\textit{$_{\rm{}2}$}\}, where 
\textit{C}`\textit{$_{\rm{}1}$}= \{\textit{O}\textit{$_{\rm{}1}$},
\textit{ O}\textit{$_{\rm{}2}$}, \textit{O}\textit{$_{\rm{}5 }$}\}, 
\textit{C}\textit{$_{\rm{}2}$}= \{\textit{O}\textit{$_{\rm{}3}$},
\textit{ O}\textit{$_{\rm{}4}$}\}, and we arrive at the same clustering as before.

In practice, it makes sense to calculate the minimum diameter or radius or the 
maximum split for \textit{K} = 2, 3, \ldots, until an increase of \textit{K} 
results in an increase of the diameter or radius, or in a decrease of the split. 

\begin{flushleft}
\textbf{{\large{}Answers to Exercises}}

\textbf{Exercise 1.} Yes, the statement is true.

\textbf{Exercise 2.} Yes, the statement is true.

\textbf{Exercise 3.} We consider only the case when at the first step $K = 4$ 
and at the second step $K = 2$. Then $d_{min}(O, 4) = 12$, with the corresponding 
cluster $C_1 = \{O_1, O_2, O_3, O_4\}$.  Next, $d_{min}(O\setminus C_1, 2) = 11$, 
with $C_2 = \{O_5, O_6\}$ and $C_3 = \{O_7, O_8\}$, $d(C_3) = 24$.

\textbf{Exercise 4.} With the same values of $K = 4$ at the first step and $K = 2$ 
at the second step, we have $r_{min}(O,4) = 4$ with $C_1 = \{O_3, O_4, O_5, O_7\}$, 
next, $r_{min}(O\setminus C_1, 2) = 5$ with $C_2 = \{O_1, O_2\}$, and finally, 
$r(\{O_6, O_8\}) = 20$.

\textbf{Exercise 5.} Another cluster is $\{O_6, O_8\}$, with $s(\{O_6, O_8\}) = 6$.

\textbf{Exercise 6.} Again, with the same parameters $K = 4$ at the first step and 
$K = 2$ at the second step, we have $s_{min}(O,4) = 7$ with $C_1 = \{O_1, O_2, O_6,
O_8\}$, $s_{min}(O\setminus C_1, 2) = 2$ with $C_2 = \{O_3, O_4\}$  and  
$C_3 = \{O_5, O_7\}$; or (see Exercise 2) $C_2 = \{O_5, O_7\}$ and $C_3 = \{O_3, O_4\}$.

\end{flushleft}

\section*{References}
\addcontentsline{toc}{section}{References}
\begin{itemize}
\item[{[CP]}] Hypersearching the Web, by members of the \emph{Clever} Project, 
\emph{Scientific American}, June 1999, pp. 54-60.
\item[{[HJ]}] P. Hansen, B. Jaumard 
\emph{Cluster Analysis and mathematical 
programming}. Mathematical Programming, Vol. 79 (1997) 191-215. 
\item[{[HJM]}] P. Hansen, B. Jaumard, N. Mladenovich, 
\emph{How to choose K entities among N}, DIMACS Series in Discrete 
Mathematics and Theoretical 
Computer Science, Vol. 19 (1995), 105-116. 
\item[{[JD]}] A. K. Jain, R. C. Dubes, 
\emph{Algorithms for clustering data}.
Prentice Hall, 1988. 
\item[{[Khey]}] A. I. Kheyfits, 
\emph{Introduction to clustering algorithms}. 
\emph{DIMACS series of educational modules}, No. 03-01, 2003. 
\item[{[MA-M]}] R. L\'{o}pez de M\`{a}ntaras, J. Aguilar-Mart\'{\i}n,
\emph{Self-learning pattern classification using a sequential clustering
technique}, Pattern Recognition, Vol. 18 (1985), No. 3/4, 271-277. 
\item[{[Murt]}] F. Murtagh, 
\emph{A Survey of Recent Advances in Hierarchical 
Clustering Algorithms}. 
The Computer Journal, Volume 26 Number 4 (1983). 
\end{itemize}

\section*{Web references cited}
\addcontentsline{toc}{section}{Web references cited}
\begin{itemize}
\item [{[1]}] http://obelia.jde.aca.mmu.ac.uk/multivar/ca.htm


\item [{[2]}] http://grain.jouy.inra.fr/ggpages/DEM/Polymorphism/Waite/Barley\_dend.gif


\item[{[3]}]
http://taxonomy.zoology.gla.ac.uk/rod/posters/images/dendrogram.gif


\item[{[4]}]
http://216.239.57.100/search?q=cache:w91ypUXPCXoC:www.nature.com/cgi-taf/DynaPage.taf%3Ffile%3D/tpj/journal/v1/n4/full/6500067a.html+molecular+classification+molecules++dendrogram+cluster+OR+clustering&hl=en&ie=UTF-8


\item[{[5]}] http://www.findarticles.com/cf\_dls/m2120/8qy\_80/58517866/p1/article.jhtml


\item[{[6]}] http://www.biotech.unl.edu/oldroot/biocomp/gcghelp/growtree.html


\item[{[7]}]
http://www.isse.gmu.edu/~snoel/First%20IEEE%20Data%20Minining%20Conference.htm


\item[{[8]}]
http://dmoz.org/Science/Math/Combinatorics/Graph\_Theory/References/


\item[{[9]}]
http://directory.google.com/Top/Science/Math/Combinatorics/Graph\_Theory/References/

\end{itemize}


\end{document}