
\chapter{Clustering - Unsupervised Learning\label{chapK:Clustering}}

\index{clustering|(}Clustering (\index{unsupervised learning}unsupervised
learning in the terminology of Chapter \ref{chapJ:Classification})
is a broadly useful data analytic operation for many purposes. The
main idea is to highlight cohesive subsets of the data that in some
sense belong together. Major practical successes of clustering\index{cluster analysis}
methods include the discovery of cancer subtypes, such as in \citet{perou2000molecular},
which was a precursor to the currently very active research area of
precision medicine\index{precision medicine}. Clustering shares the
idea of grouping data with classification as discussed in Chapter
\ref{chapJ:Classification}, with the big difference that here the
goal is to determine the class labels. Hence clustering is also called
unsupervised learning, as noted in Section \ref{secB4:Further-Statistical-Tasks}
and this chapter title.

As noted in Section \ref{secB4:Further-Statistical-Tasks}, good overviews
of clustering are provided in \citet{Hartigan1975Clustering} and
\citet{KaufmanRousseeuw2009Cluster}. There are very many clustering
methods and variations, some of which are discussed in the following
sections. These include the k-means approach in Section \ref{secK-A:KMeansClust},
hierarchical clustering in Section \ref{secK-B:HierarchicalClust}
and simple visualization based methods in Section \ref{secK-C:VisualClust}.
An important method not further discussed here is called \emph{model-based
clustering}\index{model-based clustering}, which mainly uses \index{Gaussian mixture models}Gaussian
mixture models to identify clusters, see \citet{BouveyronRaftery2019MClust}.

Key concepts are illustrated using the Four Cluster \index{Four Cluster data|(}
toy data set in the left panel of Figure \ref{figK-A:ClusterToyData}.
This data set has already been used in Figure \ref{figJ.K:KernelPCA}.
It features several important issues to keep in mind when choosing
a clustering method. One of these is the elongated cluster of green
plus signs, which could reasonably be considered one or more clusters.
In particular its points are spread over a wider range than the distance\index{distance|(}
between the round clusters of blue circles and the cyan squares, which
can be reasonably treated as two separate clusters. The red x signs
raise another relevant point. If there were only one it would usually
be called an outlier. But can two such points be considered a cluster?
What if there were more? It is useful to be aware of the conceptual
fuzziness of the boundary that exists between sets of outliers and
clusters. 

\begin{figure}[H]
\includegraphics{ChapterK/OODAbookChpKFigAClustersToy}\qquad{}\includegraphics{ChapterK/OODAbookChpKFigAIllustrateCI}

\caption{Left Panel: Four Cluster data set for the illustration of the conceptual
fuzziness and potential pitfalls of clustering. Right Panel: Another
toy data set (shown twice: in the top and also in the bottom) providing
insight into the \index{Cluster Index|(}Cluster Index introduced
in (\ref{eqK-A:ClusterIndex}). Sum of squared lengths of line segments
in the top of the right panel are the Within Cluster Sum of Squares,
$WCSS$. The bottom of the right panel similarly demonstrates the
corresponding Total Sum of Squares, $TSS$. Their ratio forms the
Cluster Index ($CI$). \label{figK-A:ClusterToyData} }
\end{figure}

\section{K-Means Clustering\label{secK-A:KMeansClust}}

An intuitively appealing approach to clustering, named \emph{\index{k-means|(}k-means}
by \citet{Macqueen1967kmeans}, was proposed by \citet{Steinhaus1956Kmeans}.
Given a set of (random as denoted by tildes) data $\widetilde{\boldsymbol{x}}_{1},\cdots,\widetilde{\boldsymbol{x}}_{n}$
in $\mathbb{R}^{d}$, the main idea is to choose cluster index sets
$C_{1},\cdots,C_{k}$ that \emph{\index{partition|(}partition} the
full index set $\left\{ 1,\cdots,n\right\} $ (i.e. each full index
is contained in exactly one of the $C_{j}$), in a way that minimizes
the \emph{Within Cluster Sum of Squares\index{Within Cluster Sum of Squares}}
\[
WCSS=\sum_{j=1}^{k}\sum_{i\in C_{j}}\left\Vert \widetilde{\boldsymbol{x}}_{i}-\overline{\boldsymbol{x}}_{j}\right\Vert ^{2},
\]
where each within cluster mean is denoted $\overline{\boldsymbol{x}}_{j}=\frac{1}{\#\left(C_{j}\right)}\sum_{i\in C_{j}}\widetilde{\boldsymbol{x}}_{i}$.
The $WCSS$ is illustrated in the top of the right panel of Figure
\ref{figK-A:ClusterToyData}, as the sum of the squared lengths of
the line segments, with the colored dots showing the within cluster
means. It can be conveniently rescaled by dividing by the total squared
overall residuals from the mean, 
\[
TSS=\sum_{i=1}^{n}\left\Vert \widetilde{\boldsymbol{x}}_{i}-\overline{\boldsymbol{x}}\right\Vert ^{2},
\]
where $\overline{\boldsymbol{x}}$ is the conventional overall mean
of the full data set. The $TSS$ is usefully contrasted with the $WCSS$
in the bottom of the right panel of Figure \ref{figK-A:ClusterToyData}
(again the black dot shows the overall mean). That rescaling results
in the \emph{Cluster Index\index{Cluster Index}}
\begin{equation}
CI=\frac{WCSS}{TSS}.\label{eqK-A:ClusterIndex}
\end{equation}
Careful consideration of the right side of Figure \ref{figK-A:ClusterToyData}
reveals that $CI=0$ when each data point lies at its cluster mean,
and $CI=1$ (largest possible value) when all cluster means are the
same as the overall mean. In between smaller values of $CI$ tend
to indicate tighter clusters.

Some properties of $CI$ are illustrated in Figure \ref{figK.I:ToyData1dCI},
using just a toy data set in one dimension. The toy data consist of
four Gaussian clusters, two of which have 5 points centered at $\pm20$
respectively, and two of which have 1000 points centered at $\pm2$
shown as black asterisks. The black curve is a kernel density estimate
as discussed in Section \ref{secN-A:NoHisto}. The behavior of $CI$
is shown by the red curve, whose height is the value of $CI$ for
the clustering of the data set determined by the horizontal coordinate.
For example, at the coordinate shown by the vertical dashed blue line,
the first cluster is the set of points to the left, while second is
those to the right. The $CI$ for that clustering is about 0.84, indicated
by the height of the blue circle. As the blue line is horizontally
shifted, the circle traces out the red curve. Note that $CI=1$ at
either end, because $WCSS=TSS$ when one of the two clusters is empty.
As the blue line moves through the leftmost small cluster, the red
line comes down. It stays flat in regions where there are no data
points. There are two peaks near $\pm2$ as the $CI$ goes up in the
middle of a cluster (because the points in the cluster contribute
to both terms of $WCSS$ which has a major impact on both cluster
means). In the center region, both cluster means are essentially in
the middle of the respective clusters resulting in both terms of the
$WCSS$ being much smaller. This shows both how $CI$ can easily have
multiple local minima, and also the potential for many search methods
to get stuck in a quite poor (in terms of the resulting $CI$ being
far from the optimum value) local minimum. Note this happens even
in the simplest case of one dimension. It is natural to expect far
more treacherous behavior in higher dimensions.

\begin{figure}[H]
\includegraphics[scale=0.7]{ChapterK/OODAbookChpKFigIToyData1dCI}

\caption{One dimensional example, highlighting local minima challenges faced
by $CI$. Many random starts can be stuck in a local minimum whose
$CI$ is far from the global minimum $CI$. \label{figK.I:ToyData1dCI}}
\end{figure}
The standard k-means algorithm starts with some (perhaps random) set
of candidate cluster means. The algorithm iterates through assignment
of each data point to the closest mean followed by re-computation
of the cluster means. This iterative process tends to converge to
local optima, so sometimes several random restarts are used. There
is a large literature on choosing initial values and restart methods.
A faster algorithm has also been proposed in \citet{PellegMoore2000Kmeans}.

The Four Cluster toy data set from Figure \ref{figK-A:ClusterToyData}
is used to illustrate some of the properties of k-means clustering
in Figure \ref{figK.B:KMeans}. These graphics were created using
the Matlab function $\mathtt{kmeans}$ with default parameter choices.
The upper left panel shows the case $k=2.$ The optimal 2-means partition\index{partition|)}
puts the green plus signs into one cluster (still colored with the
same green), and all the other points into the other cluster (colored
a common pink chosen as between the blue, cyan and red colors). It
is useful to imagine analogs of the right side of Figure \ref{figK-A:ClusterToyData}
while interpreting these plots. 

\begin{figure}[H]
\includegraphics[scale=0.9]{ChapterK/OODAbookChpKFigBkMeans}

\caption{Demonstration of k-means clustering, using the Four Cluster data,
for $k=2,3,4,5$. Shows care needs to be taken in interpretation.
\label{figK.B:KMeans} }
\end{figure}
The $k=3$ panel in the upper right shows a reasonable 3 cluster labeling
of this data set, which nicely separates the 3 biggest clusters that
were shown as green plusses, cyan squares and blue circles in the
left panel of Figure \ref{figK-A:ClusterToyData}. The latter cluster
is now colored magenta to reflect the union of the blue circles and
the red x signs. 

One might hope that the lower left $k=4$ clustering would yield the
original clusters as colored in Figure \ref{figK-A:ClusterToyData}.
However the stretch of the green plus signs is such that the $CI$
is made smaller by splitting that (note the darker and lighter shades
of green) while keeping the blue circles and red x signs in the same
cluster. 

The red x signs finally become their own small cluster in the case
$k=5$ shown in the lower right panel, however the blue circles and
cyan squares have now been labeled as a single cluster colored an
intermediate shade of blue, while the green plusses are now split
into three clusters indicated with different shades of green. Deeper
investigation showed that this is a local minimum of $CI$. Different
starting values gave a smaller $CI$, which gives the 4 colored clusters
shown in the left of Figure \ref{figK-A:ClusterToyData}, with the
green cluster split into two. This reveals an important aspect of
k-means clustering: care is needed about local minima, and the results
can be intuitively slippery, not always giving expected results. Hence
it is best used in situations where visual confirmation (e.g. with
PCA or CVA\index{Canonical Variate Analysis}, as illustrated in Figure
\ref{figJ.O:CVA}, scores distribution plots\index{scores!distribution plot})
can be done.

\citet{Cabanski2010SWISS} proposed the \emph{SWISS score} (a renaming
of the $CI$) for comparison of various preprocessing\index{preprocessing}
methods in bio-informatics settings. It essentially rates different
approaches on how distinctly they allow a data set to be clustered.
A perhaps surprising finding is that when $k>2$ clusters are of interest,
instead of using the k-means version of $CI$, it is better to use
the average of the pairwise $CI$s. This seems be related to the observation
of \citet{Friedman1996PolyClass}, discussed in Section \ref{secJ-C:SVM},
that when extending a binary classification\index{binary classification}\index{classification!binary}
approach to a multi-class context, a vote among pairwise classifications
is better than the one class versus the union of others approach.
Permutation based inference for SWISS, in the spirit of that described
in Section \ref{secL1:DiProPerm}, for assessing the statistical significance
of differences between preprocessing methods was also developed in
\citet{Cabanski2010SWISS}.\index{Cluster Index|)}

The SigClust\index{SigClust} approach to confirming the presence
of a cluster, described in Section \ref{secL2:SigClust}, uses k-means
clustering in a direct and natural way. SigClust also provides useful
information when facing the challenging problem of choosing the number
of clusters $k$. A natural approach is to try several values of $k$.
A drawback of k-means clustering is that the clusters are not \emph{nested\index{nested analyses|(}},
i.e. there need not be any relationship (such as inclusion or overlap)
between clusters for a given $k$ and $k+1$. An approach which does
give a nested sequence of clusters is hierarchical clustering\index{hierarchical clustering|(}
discussed in Section \ref{secK-B:HierarchicalClust}.

\section{Hierarchical Clustering\label{secK-B:HierarchicalClust}}

Hierarchical clustering gives a full \emph{dendrogram} (i.e. nested
set) of clusterings. An example, again using the Four Cluster toy
data set is shown in Figure \ref{figK-E:DendorEucSing}. This can
be thought of in two equivalent ways. 

One way of thinking, called \emph{\index{clustering!divisive}divisive}
or \emph{top-down}\index{clustering!top-down}, is to start with the
entire data set in one cluster, followed by a nested series of binary
\emph{splits}, until only singletons (clusters with just one member)
are left. Such splits are represented as horizontal line segments
in Figure \ref{figK-E:DendorEucSing}, where the vertical line segments
represent clusters. Colored lines are used for those clusters which
contain only points with that color in the left of Figure \ref{figK-A:ClusterToyData}.
The length of each vertical segment indicates strength of the cluster.
The first split near the top separates the two red points from the
rest. The remainder is then split between the green cluster and the
union of the blue and cyan. Next, the blues and cyans are split. Vertical
line segments above this split are relatively long because the blues
and cyans are closer together than the other colored clusters. Remaining
splits all happen within the colored clusters. The corresponding vertical
segments are relatively shorter because these smaller clusters are
much less distinct.

The other way to think of the dendrogram, called \emph{\index{clustering!agglomerative}agglomerative}
or \emph{bottom-up}\index{clustering!bottom-up}, is to start with
all singletons (shown as the bottom of the dendrogram), and then sequentially
combine pairs of clusters until only the full data set in one big
cluster is left. As one moves up the dendrogram, first the points
with common colors are combined, and then finally those clusters get
merged, with the blue-cyan and green merge happening late which reflects
the big distances between those. 

As both ways of thinking result in the same dendrogram, either is
fine for understanding the nested set of clusters. However, the difference
becomes important when considering computational issues.

\begin{figure}[H]
\includegraphics[scale=0.8]{ChapterK/OODAbookChpKFigEDendroEucSing}

\caption{A dendrogram for the Four Cluster data, based on Euclidean distance
and single linkage\index{linkage|(}. Reveals full nested\index{nested analyses|)}
series of clusters from one large cluster at the top to singleton
clusters at the bottom. \label{figK-E:DendorEucSing}}
\end{figure}
There are many ways to construct hierarchical dendrograms, most of
which are indexed by a \emph{\index{clustering!distance}distance}
(between data objects) and by a \emph{linkage\index{clustering!linkage}}
(which basically gives a notion of cluster separation). Several linkage
functions are studied for the Euclidean distance in Figure \ref{figK.C:HierEuc},
for the same Four Cluster data set from the left of Figure \ref{figK-A:ClusterToyData}.
In each case, the dendrogram has been cut at a level that mostly results
in four clusters (five in the lower right). 

The upper left panel shows the results from \emph{Ward's} linkage\index{linkage!Ward's}
(\citet{Ward1963Linkage}), which tends to target roughly equal splits.
Hence the relatively large green cluster is split (quite similar to
the $k=4$ results of k-means in Figure \ref{figK.B:KMeans}), and
the red and blue clusters are treated as just one. This is accomplished
by minimizing the within cluster $WCSS$ as done by k-means\index{k-means|)}.
The results are generally different (despite being similar in the
bottom left of Figure \ref{figK.B:KMeans} and the top left of Figure
\ref{figK.C:HierEuc}) because hierarchical clustering imposes nesting
on the overall set of clusters, minimizing $WCSS$ only at each split. 

The upper right panel shows \emph{average} linkage\index{linkage| average},
where the round but nearby cyan and blue clusters are combined. The
red points become their own small cluster, because average linkage
does not prioritize similar cluster size. Finally because of its length
the long green cluster is split. 

The lower left panel shows the result of \emph{single} linkage\index{linkage!single}.
Single linkage essentially takes the distance between clusters to
be the minimum pairwise distance between points, which gives the perhaps
intuitively expected result in this two dimensional case. 

Single linkage is explored a little further in the lower right panel,
where the five cluster version is shown (corresponding to a lower
cut in Figure \ref{figK-E:DendorEucSing}). Note that the fifth cluster
comes from splitting the long green cluster. It is worth noting that
split is not near the center of the cluster as for some of the other
linkages, but instead happens at the biggest gap between green points
as expected.

\begin{figure}[H]
\includegraphics[scale=0.9]{ChapterK/OODAbookChpKFigCHierEuc}

\caption{Exploration of several common linkages in hierarchical clustering
for the Four Cluster data, all based on Euclidean distance. Shows
single linkage gives perhaps the most intuitive clustering in this
2-d case. \label{figK.C:HierEuc}}
\end{figure}
The distance measure also has a large impact on the clustering result,
as shown in Figure \ref{figK.D:HierCos}, for the same toy data set.
All panels are again based on dendrograms (all using single linkage)
cut at a level that results in four clusters. The lower right panel
shows the result using the Spearman distance\index{Spearman distance}
(one minus the Pearson correlation between the vectors of the ranks),
which is particularly unappealing, but makes the point that choice
of distance measure can have a very large impact on the result. The
remaining panels are variations on cosine distance, defined at (\ref{eqChpE.G:CosDist}).
This is useful in situations where it is desirable to ignore scaling.
This distance is essentially based on angles (ignoring radii) in a
polar coordinate representation. The three panels make the point that
choice of \emph{center} (shown in each case as the large black dot)
of the analysis is critical to the result when using this cosine \index{distance!cosine}distance.
In the upper left panel the center is taken as the overall sample
mean, which results in a fairly good clustering, that is very close
to the average linkage result in the upper right of Figure \ref{figK.C:HierEuc}.
A deliberately poor choice of center appears in the upper right panel
of Figure \ref{figK.D:HierCos}, which results in combining the blue
and cyan clusters with most of the green, while pulling off small
bits of the greens and the reds as separate clusters. A better choice
of centerpoint appears in the lower left panel, resulting in the perhaps
intuitively expected result. This behavior is intuitively understood
as dividing the data set into sectors whose boundaries are determined
by rays coming out of the centerpoint. The upper left sample mean
combined the blue and cyan clusters, as they must lie within the same
sector. The good clustering in the lower left used a center that exploits
the large gaps in angle (as targeted by single linkage) between the
desired clusters.

\begin{figure}[H]
\includegraphics[scale=0.9]{ChapterK/OODAbookChpKFigDHierCos} 

\caption{Study, based on the \index{Four Cluster data|)}Four Cluster data,
of cosine distance with different choices of center point, shown as
a black dot. Mostly shows choice of centerpoint has a major impact
on the quality of the result. In addition the lower right panel demonstrates
very poor performance of the Spearman \index{distance!Spearman}distance.
\label{figK.D:HierCos}}
\end{figure}
In summary, for this two dimensional toy data set, single linkage
seemed to give the most intuitively expected result, while Ward's
tendency to give even splits was less useful. Other linkages such
as average and complete (not shown here, but is fairly similar to
Ward's) tend to lie between these extremes.

But this relative relationship between linkages changes markedly in
higher dimensions, as shown using the \index{High Dimensional Gaussian data|(}High
Dimensional Gaussian data in Figure \ref{figK.F:HierHiDDendros}.
That data set is $n=30$ vectors of dimension $d=500$ simulated from
the standard normal distribution. The clustering in both panels is
based on Euclidean distance, with single linkage used in the left
panel, and Ward's linkage in the right. Both dendrograms are most
easily interpreted from the viewpoint of starting at the top and considering
consecutive splits. 

The single linkage (left) analysis starts by splitting off a singleton
(one point cluster), with all other points forming the remaining cluster.
This pattern continues through most of the dendrogram. Because many
such singletons is not a typical goal of a cluster analysis, single
linkage tends to be less appealing in higher dimensions (despite the
intuitively sensible 2-d performance in Figure \ref{figK.C:HierEuc}).

On the other hand Ward's linkage (right panel of Figure \ref{figK.F:HierHiDDendros})
shows a far different behavior. This analysis favors splits which
are relatively balanced, which may be more useful, depending on the
application. As for the 2-d examples considered in Figure \ref{figK.C:HierEuc},
other linkages (such as average and complete) tend to give results
that lie in between single and Ward's linkage. It usually makes sense
to try several linkages, and ultimately use the one giving the most
useful visual results for each given situation.

\begin{figure}[H]
\includegraphics[scale=0.8]{ChapterK/OODAbookChpKFigFHierHiDDendro}

\caption{Dendrograms for the High Dimensional Gaussian data set ($d=500$),
using Euclidean distance\index{distance|)}. Contrasts single linkage
(left), which sequentially separates individuals, with Ward's linkage
(right), which tends to give more balanced splits. Colors highlight
important aspects in other plots. \label{figK.F:HierHiDDendros}}
\end{figure}
Further insights into this clustering behavior comes from the scatterplot
matrix\index{scatterplot matrix}\index{scores!scatterplot} view
of the High Dimensional Gaussian data set shown in Figure \ref{figK.G:HierHiDSingView}.
Instead of being based on PC directions as has been done in many other
scatterplot matrices, now the directions are chosen to highlight the
first two singleton clusters corresponding to the black vertical line
segments in the left panel of Figure \ref{figK.F:HierHiDDendros}.
This is done using axes which are simply unit vectors pointing in
the direction of each of the two data points (shown as black circles
in all panels), i.e. vectors of the form $\frac{\widetilde{\boldsymbol{x}}_{i}}{\left\Vert \widetilde{\boldsymbol{x}}_{i}\right\Vert }$.
These points may seem surprisingly far from the rest (shown as red
circles in all panels) for Gaussian data. Also perhaps surprising
is the orthogonality of these outlier directions. However as shown
in Section \ref{secM-B:HDLSS} this is actually quite natural behavior
for high dimensional Gaussian data. For contrast the third axis shows
the PC1 scores, i.e. the projections onto the PC1 eigenvector. Note
that the sample standard deviation of these scores is clearly larger
than in the singleton directions, which is why this is the PC1 direction.
That sample standard deviation of these PC1 scores may also appear
to be surprisingly large for projections of standard normal data.
This also turns out to be a natural aspect of high dimensional data,
as discussed in Section \ref{secM-A:RandomMatrix}.

\begin{figure}[H]
\includegraphics[scale=0.8]{ChapterK/OODAbookChpKFigGHierHiDSingView}

\caption{Scatterplot matrix view of the ($d=500$) High Dimensional Gaussian
data in Figure \ref{figK.F:HierHiDDendros}, using single linkage
colors from the left panel. The first two axes show how well the first
two singleton clusters are separated from the rest of the data, which
is why they were chosen by single linkage clustering. The third axis
is in the PC1 direction, for contrast.\label{figK.G:HierHiDSingView}}
\end{figure}
A quite different scatterplot matrix view of this same data set is
shown in Figure \ref{figK.H:HierHiDSWardView}, this time aimed at
revealing the performance of the Ward's linkage clustering in the
right panel of Figure \ref{figK.F:HierHiDDendros}. Colors come from
the dendrogram in the right panel of Figure \ref{figK.F:HierHiDDendros},
which was cut at a level resulting in four clusters. These clusters
are usefully visualized using \index{Mean Difference}Mean Difference
directions as axes. The first contrasts the Cyan vs. Blue clusters,
and the second the Green vs. Red. Again it is useful to compare with
the PC1 scores shown as the third axis. As above, the standard deviation
in the PC1 direction is larger than for either of these two cluster
differences. In parallel to the above discussion, the gap between
these clusters may appear to be quite large for standard normal data,
but this turns out to be quite natural using calculations as in Section
\ref{secM-B:HDLSS}.

\begin{figure}[H]
\includegraphics[scale=0.8]{ChapterK/OODAbookChpKFigHHierHiDWardView}

\caption{Another scatterplot matrix view of the High Dimensional Gaussian data\index{High Dimensional Gaussian data|)}
as Figure \ref{figK.G:HierHiDSingView}, this time illustrating the
Ward's linkage\index{linkage|)} analysis, with colors from the right
panel of Figure \ref{figK.F:HierHiDDendros}. First two axes are based
on colored cluster Mean Differences, Cyan - Blue in the first direction,
and Green - Red in the second. Third axis again shows the PC1 scores.\label{figK.H:HierHiDSWardView}}
\end{figure}
In summary, hierarchical clustering\index{hierarchical clustering|)}
is a very flexible set of methods with great potential for discovering
interesting and important clusters in data. However, because there
is no uniformly best clustering method (once again the ``every dog
has its day'' concept applies here), substantial prior knowledge
is essential to use it effectively. Also because there are so many
choices and options available, confirmatory analysis\index{confirmatory analysis!clusters}
becomes very important. The SigClust\index{SigClust} approach discussed
in Section \ref{secL2:SigClust} is useful for this.

\section{Visualization Based Methods\label{secK-C:VisualClust}}

While formal clustering methods such as those described in Sections
\ref{secK-A:KMeansClust} and \ref{secK-B:HierarchicalClust}, are
useful and direct ways to target clusters, the latter often appear
naturally in various data \index{visualization|(}visualizations.
Examples of this include the toy data set in Figures \ref{fig:50d-ToyPCA}
and \ref{fig:50d-ToyPCAScatMat}, as well as the Pan Can RNAseq data\index{RNAseq data}
in Figure \ref{fig:LungCancerPCABrushed}. Another example of this
is the \emph{\index{Mass Flux data}Mass Flux} data shown in Figure
\ref{figK.J:MassFluxPCA}. This functional data set (curves as data
objects\index{data objects!curves}) was provided by Enrica Bellone
of the National Center for Atmospheric Research. Each curve is a characterization
of an atmospheric cloud. The top row shows the initial object centering
operation, with the input curves shown in the top left panel, the
mean curve in the top center, and the recentered data (the mean residuals)
in the top right. The first mode of variation (best rank one approximation
of the centered data matrix) appears in the bottom left panel, showing
strong vertical variation mostly on the left side. The bottom center
plot shows the mean plus the largest (dashed) and smallest (dotted)
of the curves in the bottom left. Because of the sloping nature of
the mean, this view reveals that this mode of variation\index{mode of variation}
is actually about both the curve heights and also the location of
the peaks. The bottom right focuses on the scores (the coefficients
of the curves shown in the bottom left). The smooth histogram (kernel
density estimate, Section \ref{secN-A:NoHisto}) provides a strong
indication of 3 bumps, suggesting clustering in this data set. An
important issue is whether or not these clusters represent important
and reproducible structure in the data, or are spurious sampling artifacts.
This question is addressed for this data set using the SiZer\index{SiZer}
method in Section \ref{subsecN-D.C:SiZerMassFlux}, where it is seen
that these three peaks are statistically significant in some sense.
This turned out to be consistent with three known important cloud
types.

\begin{figure}[H]
\includegraphics[scale=0.9]{ChapterK/OODAbookChpKFigJMassFluxPCAp1}

\includegraphics[scale=0.9]{ChapterK/OODAbookChpKFigJMassFluxPCAp2}

\caption{PCA of the Mass Flux data. Top row shows impact of object mean centering
(raw data, mean and residuals). Bottom left shows the first mode of
variation, center shows relationship with mean, and bottom right shows
the scores. Note smooth histogram indicates 3 clusters in the PC1
scores. \label{figK.J:MassFluxPCA}}
\end{figure}
Other visualization\index{visualization|)} methods are also often
used to discover clusters. In bioinformatics this is commonly done
with t-SNE\index{t-SNE} as illustrated in Figure \ref{figJ.L:tSNE},
or with UMAP as discussed in Section \ref{secJ-B:KernelMethods}. 

With any visual method for finding clusters, there are limits to how
many clusters can be perceived. In complicated situations, it can
be useful to \emph{drill down}\index{drill down}. That means to take
each cluster found in an earlier step, and to separately visualize
that (e.g. using a new PCA on just the data in that cluster). \citet{Vidal2016GeneralizedPCA}
have proposed an automated version of this called \emph{\index{Generalized PCA}Generalized
PCA}. 

A quite different approach to finding clusters is based on the \index{Maximal Data Piling}Maximal
Data Piling (recall the acronym MDP) idea discussed in Figure \ref{figJ.D:MDPIntro}
in Section \ref{secJ-A:ClassicalMethods}. Note that (with probability
one for data from a distribution that is absolutely continuous with
respect to Lebesgue measure) every binary partition\index{partition}
of the data set admits the MDP direction $\widehat{\boldsymbol{w}}_{MDP}$
(as defined at (\ref{eqJ.D:MDPdirn})). The relative clustering strength
of each candidate partition is directly measured as the difference
between the two projection points of each class onto the $\widehat{\boldsymbol{w}}_{MDP}$
vector, and the partition that maximizes this can be regarded as the
best partition in high dimensions. A computational benefit to such
an approach is that each $\widehat{\boldsymbol{w}}_{MDP}$ can be
computed relatively quickly, because the inverse of the sample covariance
matrix, $\left(\widehat{\boldsymbol{\varSigma}}\right)^{-1}$, only
needs to be computed once. A major hurdle is that there are $2^{n-1}$
such binary partitions. An interesting open problem is to develop
a heuristic to make this approach computationally tractable.

\subsection{Hybrid Clustering Methods\label{subsecK-D:HybridClust}}

Clustering, i.e. \index{unsupervised learning}unsupervised learning,
has also been combined with other methods in several interesting ways
including
\begin{itemize}
\item \index{Semisupervised Learning}Semisupervised Learning, see \citet{Chapelle2006SemisupervisedLearning}.
The idea here is that some but not all of the class labels are known,
which gives a methodology which is somewhat between classification
and clustering.
\item Combining clustering with curve registration\index{curve registration!combined with clustering}
(as studied in Chapter \ref{chapH:FDA-Curve-Registration}), see \citet{Bernardi2014Proteomics,Bernardi2014Juggling}.
\item Combining \index{clustering|)}clustering with data integration\index{data integration}
(as studied in Section \ref{subsecP-B-C:JIVE}), see \citet{HelltonThoresen2014IntegrativeClusters}.
\end{itemize}

