regular.tex

聚类算法全集以及内附数据集

\documentclass{article}
\pagestyle{empty}
\oddsidemargin 2.1mm
\textwidth     155mm
\topmargin     -12mm
\textheight    230mm

\def\IR{\mbox{I\kern-0.22em R}}

\def\genlistlabel#1{#1\hfill}
\newenvironment{genlist}[1]{\begin{list}{}{%
\topsep2pt plus1pt minus1pt\itemsep\topsep\advance\topsep\parsep
\settowidth\labelwidth{#1}\settowidth\labelsep{.~}%
\leftmargin\labelwidth\advance\leftmargin\labelsep
\let\makelabel\genlistlabel}
}{\end{list}}

\begin{document}

%-----------------------------------------------------------------------

\subsection*{Regularization}

Regularizing the shape of a cluster or the sizes of the clusters means
to modify the shape or the sizes in such a way that certain conditions
are satisfied or at least a tendency (of varying strength, as specified
by a user) towards satisfying these conditions is introduced.

%-----------------------------------------------------------------------

\subsubsection*{Shape Regularization}

The shape of a cluster is represented by its covariance matrix
$\mathbf{\Sigma}$. Intuitively, $\mathbf{\Sigma}$ describes a general
ellipsoidal shape, which can be obtained, for example, by computing the
Cholesky decomposition of~$\mathbf{\Sigma}$ and mapping the unit sphere
with it. Shape regularization means to modify the covariance matrix,
so that a certain relation of the lengths of the major axes of the
represented ellipsoid is obtained or that at least a tendency towards
this relation is introduced. Since the lengths of the major axes are
the roots of the eigenvalues of the covariance matrix, regularizing it
means shifting the eigenvalues of~$\mathbf{\Sigma}$. Note that such a
shift leaves the eigenvectors unchanged, i.e., the orientation of the
represented ellipsoid is preserved. The clustering programs support two
version of shape regularization:
\begin{genlist}{\tt -H-$h$}
\item[\tt -H\,$h$] {\bf Standard Version} \\
     Adapt the covariance matrices~$\mathbf{\Sigma}_i$,
     $i = 1, \ldots, c$ (where $c$ is the number of clusters),
     according to
     \[ \mathbf{\Sigma}_i^{\rm (adap)}
        = \sigma_i^2 \cdot
          \frac{\mathbf{S}_i +h^2 \mathbf{E}}
               {\sqrt[m]{|\mathbf{S}_i +h^2 \mathbf{E}|}}
        = \sigma_i^2 \cdot
          \frac{\mathbf{\Sigma}_i +\sigma_i^2 h^2 \mathbf{E}}
               {\sqrt[m]{|\mathbf{\Sigma}_i
                         +\sigma_i^2 h^2 \mathbf{E}|}}, \]
     where $m$ is the dimension of the data space (i.e.,
     the $\mathbf{\Sigma}_i$ are $m \times m$ matrices,
     $\mathbf{E}$ is the $m \times m$ unit matrix),
     $\sigma_i^2 = \sqrt[m]{|\mathbf{\Sigma}_i|}$
     is the equivalent isotropic variance, and
     $\mathbf{S}_i = \sigma_i^{-2} \mathbf{\Sigma}_i$
     is the covariance matrix scaled to unit determinant.
     This regularization shifts all eigenvalues up by the value
     of~$\sigma^2 h^2$ and then renormalizes the resulting matrix so
     that the determinant of the old covariance matrix is preserved
     (the cluster size is kept constant). This regularization tends
     to equalize the lengths of the axes of the ellipsoid and thus
     introduces a tendency towards spherical clusters. This tendency
     is the stronger, the greater the value of~$h$. In the limit, for
     $h \to \infty$, the clusters are forced to be exactly spherical.
     On the other hand, for $h = 0$ the shape is left unchanged.
\item[\tt -H-$r$] {\bf Alternative Version} \\
     The standard version always changes the relation of the lengths
     of the major axes and thus introduces a general tendency towards
     spherical clusters. In the alternative version a limit~$r$,
     $r > 1$, for the length ratio of the longest to the shortest major
     axis of the (hyper-)ellipsoid is used and only if this limit is
     exceeded, the eigenvalues are shifted in such a way that the limit
     is satisfied. Formally: let $\lambda_k$, $k = 1, \ldots m$, be the
     eigenvalues of the matrix~$\mathbf{\Sigma}_i$. Set
     \[ h^2 = \left\{\begin{array}{ll}
              0, & \mbox{if~~}\displaystyle
                   \frac{\max{}_{k=1}^m \lambda_k}
                        {\min{}_{k=1}^m \lambda_k} \le r^2, \\
              \displaystyle
              \frac{     \max{}_{k=1}^m \lambda_k
                    -r^2 \min{}_{k=1}^m \lambda_k}
                   {\sigma_i^2 (r^2 -1)},
                 & \mbox{otherwise,}
              \end{array}\right. \]
     and execute the standard version with this value of~$h^2$.
\end{genlist}

%-----------------------------------------------------------------------

\subsubsection*{Size Regularization}

The size of a cluster can be described in different ways, for example,
by the determinant of its covariance matrix~$\mathbf{\Sigma}_i$,
$i = 1, \ldots, c$ ($c$ is the number of clusters), which is a
measure of the clusters squared (hyper-)volume, an equivalent isotropic
variance~$\sigma_i^2$ or an equivalent isotropic radius (standard
deviation)~$\sigma_i$ (equivalent in the sense that they lead to the
same (hyper-)volume). The latter two measures are defined as
\[ \sigma_i^2 = \sqrt[m]{|\mathbf{\Sigma}_i|} \qquad\mbox{and}\qquad
   \sigma_i = \sqrt{\sigma_i^2} = \sqrt[2m]{|\mathbf{\Sigma}_i|} \]
and thus the (hyper-)volume can also be written as
$\sigma_i^m = \sqrt{|\mathbf{\Sigma}_i|}$. Size regularization means
to ensure a certain relation between the cluster sizes or at least to
introduce a tendency into this direction. The clustering programs
support different versions of size regularization, in which the
measure that is used to describe the cluster size is specified
by an exponent~$a$ of the equivalent isotropic radius~$\sigma_i$:
\begin{center}
\begin{tabular}{ll}
$a = 1:$ & size is measured by equivalent isotropic radius, \\
$a = 2:$ & size is measured by equivalent isotropic variance, \\
$a = m:$ & size is measured by (hyper-)volume.
\end{tabular}
\end{center}
The supported size regularization versions are:
\begin{genlist}{\tt -R-$b$:$a$:[-]$s$}
\item[\tt -R\,$b$:$a$:$s$] {\bf Standard Version} \\
     The equivalent isotropic radius~$\sigma_i$ is adapted according to
     \[ \sigma_i^{\rm (adap)}
        = \sqrt[a]{s \cdot \frac{\sum_{k=1}^c \sigma_k^a}
                                {\sum_{k=1}^c (\sigma_k^a +b)}
                     \cdot (\sigma_i^a + b)}
        = \sqrt[a]{s \cdot \frac{\sum_{k=1}^c \sigma_k^a}
                                {c b +\sum_{k=1}^c \sigma_k^a}
                     \cdot (\sigma_i^a + b)}. \]
     That is, each size is increased by the value of~$b$ and then the
     sizes are renormalized so that the sum of the cluster sizes is
     preserved. However, the parameter~$s$ can be used to scale the
     sum of the sizes up or down.
\item[\tt -R\,$b$:$a$:-$s$] {\bf Simplified Version} \\
     The simplified version does not renormalize the sizes. However,
     this missing normalization may be mitigated to some degree by
     specifying a value of $s$ that is smaller than 1.
     The equivalent isotropic radius~$\sigma_i$ is adapted according to
     \[ \sigma_i^{\rm (adap)} = \sqrt[a]{s \cdot (\sigma_i^a + b)}. \]
     Note that, with $b = 0$, this version can be used to simple scale
     the clusters.
\item[\tt -R-$b$:$a$:$s$] {\bf Full Size Equalization} \\
     In the limit, for $b \to \infty$, the standard version leads to
     a full equalization of the cluster sizes. This can be achieved
     by specifying a negative first parameter, $b \le 1$. In this case
     the equivalent isotropic radius~$\sigma_i$ is adapted according to
     \[ \sigma_i^{\rm (adap)}
        = \sqrt[a]{\frac{s}{c}\sum_{k=1}^c \sigma_k^a}. \]
     That is, all clusters are set to the same size.
\item[\tt -R-$r$:$a$:[-]$s$] {\bf Alternative Version} \\
     The standard version always changes the relation of the cluster
     sizes and thus introduces a general tendency towards clusters of
     equal size. In the alternative version a limit~$r$, $r > 1$, for
     the size ratio of the largest to the smallest cluster is used and
     only if this limit is exceeded, the sizes are changed in such a
     way that the limit is satisfied. To achieve this, $b$ is set
     according to
     \[ b = \left\{\begin{array}{ll}
            0, & \mbox{if }\displaystyle
                 \frac{\max{}_{k=1}^c \sigma_k^a}
                 {\min{}_{k=1}^c \sigma_k^a} \le r, \\
            \displaystyle
            \frac{   \max{}_{k=1}^c \sigma_k^a
                  -r \min{}_{k=1}^c \sigma_k^a}
                 {r -1},
               & \mbox{otherwise,}
            \end{array}\right. \] 
     and the standard or simplified version (depending on the sign of
     the third parameter) is executed with this value of~$b$ and the
     values of $a$ and $s$ as given on the command line.
\end{genlist}

%-----------------------------------------------------------------------

\end{document}