kmlocal-doc.tex

高效的k-means算法实现

%----------------------------------------------------------------------
% File:				kmlocal-doc.tex
% By:				David Mount
% Last modified:	08/10/05
% Description:		User manual for KMlocal
%----------------------------------------------------------------------
% Copyright (c) 2005 University of Maryland and David Mount.  All
% Rights Reserved.
%
% Permission to use, copy, and distribute this software and its
% documentation is hereby granted free of charge, provided that
% (1) it is not a component of a commercial product, and
% (2) this notice appears in all copies of the software and
%     related documentation.
%
% The University of Maryland (U.M.) and the authors make no represen-
% tations about the suitability or fitness of this software for any
% purpose.  It is provided "as is" without express or implied warranty.
%----------------------------------------------------------------------
% History
% -------
% Version: 1.0  04/29/2002
%		Initial release
% Version: 1.1  04/08/2003
%		Added EZ_Hybrid and dampening.
% Version: 1.2  09/13/2003
%		Created documention directory.  Added sample programs,
%		kmlsample.cpp and kmlminimal.cpp.
% Version: 1.7  08/10/2005
%		Fixed errors in kms_run documentation.  Added capability for
%		reporting final assignment to clusters and validation.
%----------------------------------------------------------------------
%  Typical page setup for a latex2e document.
%  Uncomment the desired style from the following options.
%-----------------------------------------------------------------------
\documentclass[11pt]{article}		% plain manuscript (11pt)
%-----------------------------------------------------------------------
%  Margin sizes (for plain manuscript style and letter-sized paper)
%
%  Note that the top and left margins include a 1 inch automatic offset.
%  For A4 paper, change the \textwidth and \textheight below.
%-----------------------------------------------------------------------
\setlength{\evensidemargin}{0in}	% 1 inch margin on left
\setlength{\oddsidemargin}{0in}
\setlength{\headsep}{0pt}		% no header line
\setlength{\topmargin}{0in}		% 1 inch margin on top
\setlength{\headheight}{0pt}
\setlength{\textwidth}{6.5in}		% text size for letter paper
\setlength{\textheight}{8.5in}
%   \setlength{\textwidth}{6.25in}	% text size for A4 paper
%   \setlength{\textheight}{9in}
\setlength{\parskip}{3pt plus 1.5pt minus 1.5pt}	% paragraph skip
%-----------------------------------------------------------------------
%  Special math symbols 
%       floor, ceiling, angled brackets
%-----------------------------------------------------------------------
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\newcommand{\ang}[1]{\langle #1\rangle}
%-----------------------------------------------------------------------
%  Tighter lists
%-----------------------------------------------------------------------
\newenvironment{enumerate*}%            % Tighter enumerated list
  {\begin{enumerate}%
    \setlength{\itemsep}{-0.5ex}%
    \setlength{\parsep}{0pt}}%
  {\end{enumerate}}
\newenvironment{itemize*}%              % Tighter itemized list
  {\begin{itemize}%
    \setlength{\itemsep}{-0.5ex}%
    \setlength{\parsep}{0pt}}%
  {\end{itemize}}
\newenvironment{description*}%          % Tighter decsription list
  {\begin{description}%
    \setlength{\itemsep}{-0.5ex}%
    \setlength{\parsep}{0pt}}%
  {\end{description}}
%-----------------------------------------------------------------------
%  Title
%-----------------------------------------------------------------------
\begin{document}

\title{KMlocal: A Testbed for $k$-means Clustering Algorithms}
\author{David M. Mount\thanks{Copyright (c) 2002--2005 University of
	Maryland and David Mount. All Rights Reserved.  Partially
	supported by the National Science Foundation under
	grant CCR-0098151.} \\
	Department of Computer Science and \\
	Institute for Advanced Computer Studies \\
	University of Maryland \\
	College Park, Maryland 20742 \\
        Email: [e-mail].}

\date{Version: 1.7 \\
	August 10, 2005}

\maketitle

\section{Introduction}

This is a collection of programs for performing k-means clustering based
on local search.  In $k$-means clustering we are given a set of $n$ data
points in $d$-dimensional space and an integer $k$, and the problem is
to determine a set of $k$ points, called centers, so as to minimize the
mean squared distance from each data point to its nearest center, called
the \emph{average distortion}.

A popular algorithm for doing $k$-means clustering is called the
\emph{$k$-means algorith}, or \emph{Lloyd's algorithm}. Lloyd's
algorithm is based on the simple observation that the optimal placement
of a center is at the centroid of the associated cluster.  Given any set
of $k$ centers $Z$, for each center $z \in Z$, let $V(z)$ denote its
\emph{neighborhood}, that is, the set of data points for which $z$ is the
nearest neighbor.  Each stage of Lloyd's algorithm moves every center
point $z$ to the centroid of $V(z)$ and then updates $V(z)$ by
recomputing the distance from each point to its nearest center.  These
steps are repeated until some convergence condition is met.

However, Lloyd's algorithm can get stuck in locally minimal solutions
that are far from the optimal.  For this reason it is common to consider
heuristics based on \emph{local search}, in which centers are swapped in
and out of an existing solution (typically at random).  Such a swap is
accepted if it decreases the average distortion, and otherwise it is
ignored.  It is also possible to combine these two approaches (Lloyd's
algorithm and local search), producing a type of hybrid solution.  There
are many variants on these themes.

This program provides a number of different algorithms for doing $k$-means
clustering based on these ideas and combinations.  Further information
can be found in the following paper.

\begin{quotation}
T. Kanungo, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A.
Y. Wu, ``A Local Search Approximation Algorithm for k-Means Clustering''
\emph{Proc. of the 18th ACM Symp. on Computational Geometry}, 2002,
10--18.
\end{quotation}

It is also available from

\centerline{\textsf{http://www.cs.umd.edu/\~{}mount/pubs.html}}

\section{Compilation}

Let us assume that you are in the kmlocal root directory, from which the
subdirectories \textsf{src}, \textsf{bin}, and \textsf{test} branch off.
To start, you can compile the kmltest program by entering (from the root
directory) ``\textsf{make}''.  This is set up for the g++ compiler,
version 2.7.2 or higher on Solaris.  It will probably generate a number
of error messages if you try it from another compiler or platform.  The
executable binary will be left in the file \textsf{bin/kmltest}.

\section{Overview of the Algorithms} \label{algo.sec}

There are three different procedures for performing k-means, which have
been implemented here.  The main issue is how the neighbors are computed
for each center.

\begin{description}
\item[Lloyd's:] Repeatedly applies Lloyd's algorithm with randomly
	sampled starting points.
\item[Swap:] A local search heuristic, which works by performing swaps
	between existing centers and a set of candidate centers.
\item[Hybrid:] A more complex hybrid of Lloyd's and Swap, which performs
	some number of swaps followed by some number of iterations of
	Lloyd's algorithm.  To avoid getting trapped in local minima,
	an approach similar to simulated annealing is included as well.
\item[EZ\_Hybrid:] A simple hybrid algorithm, which does one swap
	followed by some number of iterations of Lloyd's.
\end{description}

All the algorithms are based around a generic local search structure.
The generic algorithm begins by generating an initial solution curr and
saving it in best.  These objects are local to the KMlocal structure.
The value of curr reflects the current solution and best reflects the
best solution seen so far.  The generic algorithm consists of some
number of basic iterations, called stages.  Each stage involves the
execution of one step of either the swap heuristic or Lloyd's algorithm.
Each of the algorithms differ in how they apply these stages.

Stages are grouped into runs.  Intuitively, a run involves a (small)
number of stages in search of a better solution.  A run might end, say,
because a better solution was found or a fixed number of stages have
been performed without any improvement.  After a run is finished, we
check to see whether we want to accept the solution.  Presumably this
happens if the cost is lower, but it may happen even if the cost is
inferior in other circumstances (e.g., as part of a simulated annealing
approach).  Accepting a solution means copying the current solution to
the saved solution.  In some cases, the acceptance may involve reseting
the current solution to a random solution.

There are some concepts that are important to run/phase transitions.
One is the maximum number of stages.  Most algorithms provide some sort
of parameter that limits the number of stages that the algorithm can
spend in a particular run (before giving up).  The second is the
relative distortion loss, or \emph{RDL}. (See also KMterm.h.) The RDL is
defined:
\[
    \mbox{RDL} =  \frac{\mbox{initDistortion} - \mbox{currDistortion}}%
                   {\mbox{initDistortion}}.
\]
Note that a positive value indicates that the distortion has decreased.
The definition of ``initDistortion'' depends on the algorithm.  It may
be the distortion of the previous stage (RDL = consecutive RDL), or it
may be the distortion at the beginning of the run (RDL = accumulated
RDL).

\subsection{Lloyds}

This is Lloyd's algorithm with random restarts The algorithm is broken
into phases, and each phase is broken into runs.  Each phase starts by
sampling center points at random.  Each run is provided two parameters,
a maximum number of runs per stage (max\_run\_stage) and a minimum
accumulated relative distortion loss (min\_accum\_rdl).  If the
accumulated RDL for the run exceeds this value, then the run ends in
success.  If the number of stages is exceeded before this happens, the
run ends in failure.  The phase ends with the first failed run.

\subsection{Swap}

This algorithm iteratively changes centers by performing swaps.  Each
run consists of a given number (max\_swaps) executions of the swap
heuristic.

\subsection{EZ\_Hybrid}

This implements a simple hybrid algorithm (compared to the full hybrid).
The algorithm performs only one swap, followed by some number of
iterations of Lloyd's algorithm.  Lloyd's algorithm is repeated until
the consecutive RDL falls below a given threshold.

A stage constitutes one invocation of the Swap or Lloyd's algorithm.  A
run consists of a single swap followed by a consecutive sequence of
Lloyd's steps.  A graphical representation of one run is presented
below.  The decision to make another pass through Lloyd's is based on
whether the relative improvement since the last stage (consecutive
relative distortion loss) is above a certain fixed threshold
(min\_consec\_rdl).

\subsection{Hybrid}

This implements a more complex hybrid algorithm, which combines both of
swapping and Lloyd's algorithm with a variant of simulated annealing.
The algorithm's execution is broken into the following different
processes: one swap, a consecutive sequence of Lloyd's steps, and an
acceptance test.  If we pass the acceptance test, we take the resulting
solution, and otherwise we restore the old solution.

The decision to perform another Lloyd's step or go on to acceptance is
based on whether the relative improvement since the last stage
(consecutive relative distortion loss) is above a certain fixed
threshold (min\_consec\_rdl).  If the resulting solution is better than
the saved solution, then we accept it.  Otherwise, we use the simulated
annealing decision choice (described below) to decide whether to accept
it.  The choice to accept a poorer solution occurs with probability
\[
	\exp \left( \frac{\mbox{RDL}}{T} \right),
\]
where RDL is the relative distortion loss (relative to the saved
solution), and T is the current temperature.  Note that if $\mbox{RDL} >
0$ (improvement) then this quantity is $> 1$, and so we always accept.
The temperature value $T$ is a decreasing function of the number of the
number of stages.  It starts at some initial value $T_0$ and decreases
slowly over time.  Rather than using the standard (slow) Boltzman
annealing schedule, we use the following fast annealing schedule, every
$L$ stages we set $T = T_F \cdot T$, where:
\begin{description}
\item[$L$ (temp\_run\_length):] is an integer parameter set by the
	user.  (Presumably it depends on the number of centers and
	the dimension of the space.)
\item[$T_F$ (temp\_reduc\_factor):] is a real number of the form
	$1-x$, for some small $x$.
\end{description}

The initial temperature $T_0$ is a tricky parameter to set.  The user
supplies a parameter $p_0$ (init\_prob\_accept), the initial probability
of accepting a random swap.  However, the probability of acceting a swap
depends on the given RDL value.  To estimate this, for the first $L$
runs we use $p_0$ as the probability.  Over these runs we compute the
average rdl value.  Once the first $L$ runs have completed, we set $T_0$
so that:
\[
	\exp \left( -\frac{\mbox{avgRDL}}{T_0} \right) = p_0.
\]
or equivalently
\[
	T_0 = -\frac{\mbox{avgRDL}}{\ln p_0}.
\]