\documentclass[prodmode,acmcsur]{acmsmall} 


%%% from the ACM example:
\usepackage[ruled]{algorithm2e}
\renewcommand{\algorithmcfname}{ALGORITHM}
\SetAlFnt{\small}
\SetAlCapFnt{\small}
%%% *** broken: ***
%\SetAlCapNameFnt{\small}
%\SetAlCapHSkip{0pt}
%\IncMargin{-\parindent}

% Metadata Information
\acmVolume{1}
\acmNumber{1}
\acmArticle{1}
\acmYear{1111}
\acmMonth{1}

% Copyright
%\setcopyright{acmcopyright}
%\setcopyright{acmlicensed}
%\setcopyright{rightsretained}
%\setcopyright{usgov}
%\setcopyright{usgovmixed}
%\setcopyright{cagov}
%\setcopyright{cagovmixed}

% DOI
\doi{0000001.0000001}

%ISSN
\issn{1234-56789}


%%% from Yan's original:
\usepackage{amsmath}
\newcommand{\BigO}[1]{\ensuremath{\operatorname{O}\bigl(#1\bigr)}}

\usepackage{url}
\urlstyle{same}

\hyphenation{com-bi-na-tion al-go-ri-thms straight-for-ward Ap-pli-ca-tions RE-pre-sen-ta-tives cal-cu-late pro-cess clus-ter-ing com-pu-ta-tion-al}

\newcommand{\fixme}{\textbf{***fixme***}}


%===============================================================================
\begin{document}

% Page heads
\markboth{Yan Yan et al.}{Data Clustering Technologies In Cancer Subtyping}

% Title portion
\title{Data Clustering Technologies In Cancer Subtyping}
\author{
YAN YAN,
BOBBY D. BRYANT, and
FREDERICK C. HARRIS, JR. \affil{University of Nevada, Reno}
}
% NOTE! Affiliations placed here should be for the institution where the
%       BULK of the research was done. If the author has gone to a new
%       institution, before publication, the (above) affiliation should NOT be changed.
%       The authors 'current' address may be given in the "Author's addresses:" block (below).
%       So for example, Mr. Abdelzaher, the bulk of the research was done at UIUC, and he is
%       currently affiliated with NASA.

\begin{abstract}
Cancer subtyping remains a challenging task in microarray data analysis.
The major goals of a successful cancer subtyping system are accuracy and reliability.
Cluster analysis techniques have proven to be effective in this area.
To facilitate further development in cancer subtyping based on microarray data, we provide a comprehensive review of the major cluster analysis algorithms from the clinical and computational domains that have been applied on microarray mRNA expression data and miRNA expression data for cancer subtyping, as well as other clustering algorithms with potential application in cancer subtyping. 
\end{abstract}

%
% The code below should be generated by the tool at
% http://dl.acm.org/ccs.cfm
\begin{CCSXML}
<ccs2012>
<concept>
<concept_id>10010147.10010257.10010258.10010260.10003697</concept_id>
<concept_desc>Computing methodologies~Cluster analysis</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10010147.10010257.10010258.10010260</concept_id>
<concept_desc>Computing methodologies~Unsupervised learning</concept_desc>
<concept_significance>300</concept_significance>
</concept>
<concept>
<concept_id>10010147.10010257</concept_id>
<concept_desc>Computing methodologies~Machine learning</concept_desc>
<concept_significance>100</concept_significance>
</concept>
<concept>
<concept_id>10010147.10010257.10010258</concept_id>
<concept_desc>Computing methodologies~Learning paradigms</concept_desc>
<concept_significance>100</concept_significance>
</concept>
<concept>
<concept_id>10010405.10010444.10010449</concept_id>
<concept_desc>Applied computing~Health informatics</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10010405.10010444</concept_id>
<concept_desc>Applied computing~Life and medical sciences</concept_desc>
<concept_significance>300</concept_significance>
</concept>
</ccs2012>
\end{CCSXML}
%
\ccsdesc[500]{Computing methodologies~Cluster analysis}
\ccsdesc[300]{Computing methodologies~Unsupervised learning}
\ccsdesc[100]{Computing methodologies~Machine learning}
\ccsdesc[100]{Computing methodologies~Learning paradigms}
\ccsdesc[500]{Applied computing~Health informatics}
\ccsdesc[300]{Applied computing~Life and medical sciences}
%
% End generated code
%

% We no longer use \terms command
%\terms{Design, Algorithms, Performance}

\keywords{algorithms, cancer subtype detection, data clustering, microarrays}

\acmformat{
Yan Yan, Bobby D. Bryant, and Frederick C. Harris, Jr. 2016.
Data Clustering Technologies In Cancer Subtyping.}
% At a minimum you need to supply the author names, year and a title.
% IMPORTANT:
% Full first names whenever they are known, surname last, followed by a period.
% In the case of two authors, 'and' is placed between them.
% In the case of three or more authors, the serial comma is used, that is, all author names
% except the last one but including the penultimate author's name are followed by a comma,
% and then 'and' is placed before the final author's name.
% If only first and middle initials are known, then each initial
% is followed by a period and they are separated by a space.
% The remaining information (journal title, volume, article number, date, etc.) is 'auto-generated'.

\begin{bottomstuff}
Author's addresses: Y. Yan, B. D. Bryant, {and} F. C. Harris, Jr., Department of Computer Science and Engineering, University of Nevada, Reno;
emails: yyan66@yahoo.com, bdbryant@cse.unr.edu, and Fred.Harris@cse.unr.edu.
\end{bottomstuff}

\maketitle




\section{Introduction}\label{secIntro} 

%overview
Clustering microarray gene expression data has been used to improve cancer subtyping \cite{Alon1999,Golub1999,Slonim2000} over traditional clinical methods based on morphological appearances. Its aim is to find groups of patients sharing similar expression patterns or biological attributes. Due to the amount of data (\textit{e.g.} large number of dimensions or gene expressions) produced by microarray technology, manual analysis is not possible. Automatic analyzing tools are needed to discover underlying patterns within the data. Clustering approaches are suitable to accomplish this goal and have shown promising progress \cite{Slonim2000} and possibilities for more accurate and reliable results. %such that patients are correctly divided into reproducible groups or subtypes.

%clustering vs. classification
In this review, we focus on the application of clustering techniques. It is important to understand the difference between clustering (unsupervised learning) and classification (supervised learning). In contrast to classification techniques, clustering techniques do not require labels which may not be accurate or available. Clustering results are obtained solely from data. This advantage also enables clustering algorithms to avoid over-fitting, a potential problem in classification techniques.

%clustering overview
In order to develop clinically successful clustering-based cancer subtyping tools for microarray data, a solid understanding of clustering and the available clustering methods is essential. Clustering is the task of assigning a set of objects into groups or clusters, so that the objects in the same cluster are more similar to each other than to those in other clusters \cite{Guha1998}. Clustering has a long history, tracing back to Aristotle, and has been studied extensively since the 18th century \cite{Hansen1997}. It has a wide range of applications in natural sciences, engineering, economics, marketing, medicine, psychology, and many other fields. As a consequence, the cluster analysis literature is vast and heterogeneous with hundreds of papers and books published each year from various communities \cite{Hansen1997}. 

Cluster analysis algorithms draw upon statistics, mathematics, and computer science \cite{Hansen1997}. Closely related fields are machine learning, pattern recognition, computer vision, image analysis, information retrieval, and bioinformatics. 
The k-means algorithm, first published in 1955 \cite{Steinhaus1956}, is one of the most simple and popular clustering algorithms. 
Thousands of clustering algorithms in various fields have been published since then. Due to the ill-posed nature of clustering, \textit{i.e.} lack of external objective criteria to validate clustering results, it is difficult to design a general purpose clustering algorithm. Different clustering algorithms or even the same algorithm with different parameters often produce different results on the same data set. There is no single clustering algorithm that performs best for all data sets \cite{Kuncheva2004-2}, and discovering all cluster structures in a data set is impossible for any known clustering algorithm \cite{Duda2001,Handl2005}. 

%molecular cancer subtyping overview
In order for computational communities to contribute to the cancer subtyping field, the background and an updated knowledge of cancer subtyping are necessary. Cancer remains a leading cause of death worldwide largely due to lack of effective treatment. Personalized treatment based on cancer subtypes improves patient survival. The goal of cancer subtyping is to identify subtypes within a cancer type, where patients within a subtype are more similar than patients in other subtypes. The advent of microarray technology in the 1990s made it possible to assess the expression of tens of thousands of genes in a single experiment. Microarray gene expression data has been used for cancer subtyping \cite{Alon1999,Golub1999,Slonim2000}, and the results are promising with improved accuracy over traditional methods \cite{Slonim2000}. 
This kind of analysis was first employed in \cite{Golub1999} and \cite{Alizadeh2000}. Since then, clinical decision support in the form of cancer subtype diagnosis based on microarray data analysis has become an important emerging medical application, and has attracted great attention \cite{Dhaeseleer2005}.

%related literatures overview 
The high dimensional and noisy nature of gene expression data has given rise to a wealth of clustering techniques being presented. Much of the early work used methods developed originally for other domains \cite{Alizadeh2000,Bhattacharjee2001,Bittner2000,Bredel2005,Chen2002,Chowdary2006,Dyrskjot2003,Golub1999,Laiho2007,Lapointe2004,Liang2005,Risinger2003,Singh2002,Yeoh2002}. Novel algorithms specifically targeting gene expression data and taking its intrinsic characteristics into account were presented to improve the clustering results \cite{Brunet2004,Liu2003,McLachlan2002}. 

%goal of this paper
The main goal of this review is to provide a background of cluster analysis� application in cancer subtyping, as well as an overview of its current state. 
Audiences in the medical community may find that the overview of clustering and literature review in the computational communities will broaden their experimental possibilities, while the audience in the computational communities may find the cancer subtyping background and literature review in the clinical community an entry point for them to start contributing to this application area.     

%paper limitations 
Since clustering is a vast and ever changing field, it is impossible to cover all approaches in a single paper. This review paper focuses on key clustering algorithms and their novelties. It also covers important developments applying clustering techniques to cancer subtyping. 
   
%paper organization   
The organization of the paper is as follows: Section~\ref{secSubtyping} provides a historic background on cancer subtyping that includes very different subtyping techniques in the medical field. Section~\ref{secClustering} presents a general overview of clustering, including discussions about issues such as the curse of dimensionality, feature selection, and cluster validity. It then reviews literature regarding different types of clustering across several disciplines including their variety, uses, strengths, and limitations. Section~\ref{secClusteringSubtyping} provides a literature review of clustering applications on microarray-data-based cancer subtyping. It includes literature in both the clinical community and the computational community. For each community, the section discusses literature in two categories: mRNA experiments and miRNA experiments. 
Section~\ref{secChallenges} examines challenges in microarray-data-based cancer subtyping. Finally, Section~\ref{secConclusion} concludes the review and points out future directions.

\section{Cancer Subtyping Techniques}\label{secSubtyping} 
Many diseases, including cancers, have multiple subtypes. For example, leukemia has four main subtypes: acute lymphoblastic leukemia (ALL), acute myelogenous leukemia (AML), chronic lymphocytic leukemia, and chronic myelogenous leukemia \cite{NCI2013-2}. Each of these main subtypes can have several subsubtypes as well. For example, ALL has six subsubtypes \cite{LLS2013}. 
Accurate subtyping can identify the most appropriate treatments to target specific disease subtypes, thus improving treatment results. 

%cancer overview?
%...

%cancer subtype
Given the tremendous complexity of various types and subtypes of cancers, it is believed that the single most important factor for surviving or managing cancers is and will be early detection and treatment \cite{Xu2008}. Early cancer diagnosis requires accurately identifying the type as well as the subtype of a tumor. Tumors with similar appearances under microscope may have quite different origins and may therefore respond differently to the same treatment therapy. For example, DLBCL, the most common type of lymphoma in adults, can be cured by chemotherapy in only 35-40 percent of patients due to the existence of unknown subtypes that cannot be discriminated based only on their morphological parameters \cite{Alizadeh2000}. 

%cancer subtyping & personalized therapy
The conventional approach to cancer therapy has been to provide treatment according to the organ or tissue in which the cancer originates. In the past two to three decades, however, the genetic events that lead to cancer have been dissected, and it has become clear that cancer develops as a result of multiple genetic defects and that individuals with the same type of cancer often have dissimilar genetic defects in their tumors. This finding explains why patients who seem to have similar cancer respond in a heterogeneous manner to anticancer agents and shows clearly the huge obstacle to providing effective treatments for cancer \cite{Veer2008}. New approaches to cancer therapy are shifting to a more personalized approach in which each patient is treated according to the specific genetic defects in the tumor.

%traditional cancer subtyping -> microarray -> molecular cancer subtyping 
Traditional cancer subtyping methods are largely dependent on the morphological appearance of tumors and parameters derived from clinical observations including histology, histopathology, and immunohistochemistry. The advent of DNA-microarray technology in the 1990s and the systematic analysis of the gene-expression patterns of tumor samples enabled researchers to investigate a new class of molecular diagnostic test for cancer \cite{Veer2008}. The gene expression profiles from particular microarray experiments have been recently used for cancer classification \cite{Alon1999,Golub1999,Slonim2000}. This approach promises to give a better therapeutic measurement to cancer patients by diagnosing cancer types with improved accuracy \cite{Slonim2000}. This section provides brief summaries of traditional subtyping methods, and focuses on the newer method of molecular diagnosis subtyping and applying clustering to molecular diagnosis subtyping. 

\subsection{Histology and Histopathology} 
%Histology
Histology studies the microscopic anatomy of cells and tissues of plants and animals. It is commonly performed by sectioning and staining cells and tissues, then examining such cells and tissues with a light microscope or electron microscope \cite{Martini2012}. 
Marcello Malpighi (1628-1694), an Italian anatomist, conducted work that laid the foundation of histology. He used a rudimentary microscope to examine tissues and was the first to observe capillaries \cite{Didio1994}. 
Marie Fran\c{c}ois Xavier Bichat (1771-1802), a French anatomist, is generally regarded as the 'father of histology'. He suggested that body organs are composed of various tissues or membranes and introduced 21 such tissues \cite{Roeckelein1998}. 
In the early 19th century, histologist Camillo Golgi invented the tissue staining technique to enhance the contrast between cellular components \cite{Nobelprize2013}. 
Histology is an essential tool in the fields of biology and medicine.

%Histopathology
Histopathology studies the microscopic anatomy of diseased tissues in order to examine the manifestations of disease. Specifically, in clinical medicine, histopathology refers to the examination of a surgical specimen or biopsy by a pathologist after the specimen has been processed and placed onto glass slides \cite{Allen2013}. It is an important tool in anatomical pathology, and accurate diagnosis of cancer and other diseases usually requires histopathological examination of tissues.

\subsection{Immunohistochemistry}
Immunohistochemistry (IHC) refers to the process of identifying antigens (\textit{e.g.} proteins) in cells of tissues. \textit{`Immuno'} means antibodies, and \textit{`histo'} means tissue. It is based on the principle that antibodies bind specifically to antigens in biological tissues. In an IHC process, antibodies are tagged with a visible label. IHC uses anatomical, immunological and biochemical techniques to visualize specific cellular components' distribution and localization within cells and tissues \cite{Piercenet2013}.   

%%History. 
As early as the 1930s, the principle of IHC was known \cite{Duraiyan2012}. In 1942, Coons reported the first IHC study that identifies pneumococcal antigens in infected tissue using FITC-labeled antibodies \cite{Coons1942}. Since then, improvements have been made in IHC, and IHC has become a routine and essential tool in laboratories for diagnosis and research purposes.
	
%%Applications. 
IHC can be used for disease diagnosis, drug development, and biological research. For example, physicians use IHC and specific tumor markers to diagnose a cancer as benign or malignant, as well as the tumor stage and grade, cell type and origin (site of the primary tumor) \cite{Duraiyan2012}. 

\subsection{Molecular Diagnosis} 
%%problem  
Conventional diagnosis of cancer type and subtype has been based on examination of the morphological appearance of stained tissue specimens under the light microscope, which is subjective and depends on pathologists' experiences. Diagnosis of cancer based on microarray data gives hope that cancer classification can be objective and highly accurate, which could provide clinicians enough information to choose the most appropriate treatment.
The accuracy of morphological and immunohistochemistry diagnosis is insufficient in many diseases (including cancers) to identify diagnostic subtypes. Research has shown that a genomic method using gene expression in diseases can increase the clarity of previously obscure diagnostics. The molecular classification of diseases on the basis of gene expression can discover previously undetected but clinically significant subtypes of diseases \cite{Alizadeh2000}.

%%history
In 1949, Pauling et al. introduced the term `molecular disease', which is based on their discovery that a single amino acid molecule change at the b-globin chain leads to the disease of sickle cell anemia \cite{Pauling1949}. The foundation of molecular diagnostics was laid by scientists from various disciplines working on recombinant DNA technology in the 1970s \cite{Chehab1993}. 
In the 1980s, molecular diagnostics started to become popular with the discovery of the powerful molecular biology tool, Polymerase Chain Reaction \cite{Bartlett2003}. In 1996, the application of microarray technology made it possible to simultaneously monitor thousands of genes in one experiment. Molecular diagnostics has been implemented not only in research laboratories but also in clinics on individual patients due to reduced complexities, costs, and time requirements involved in the process.    

%%what is molecular diagnostics
Molecular diagnosis of human diseases is nucleic acid based. It detects various pathogenic mutations in nucleic acid (\textit{i.e.} DNA and/or RNA samples) in order to facilitate detection, diagnosis, subtyping (or subclassification), prognosis of diseases, and monitoring response to therapy \cite{Chehab1993}.   
Molecular diagnostics uses technologies such as mass spectrometry and gene chips from the fields of genomics and proteomics to classify cancers and other diseases. 
Molecular diagnostics studies how the genes and proteins interact in a cell and discovers their activity patterns by examining the expression patterns of genes. For example, in different types of cancerous or precancerous cells, molecular diagnostics uncovers differences in gene expression patterns that can be used to improve cancer diagnosis \cite{NCI2013}.

%%Gene Expression and their measurements
Ideally, measurement of gene expression is done on the final gene product, the protein for many genes. However it is often easier to use one of the precursors, typically mRNA (messenger RNA), to infer gene expression level \cite{Xu2011}. 
There are different technologies to measure gene expression including reporter gene \cite{Koo2007}, northern blotting \cite{Alberts2008,Kevil1997}, western blotting \cite{Song2009}, RT-qPCR \cite{Taylor2010}, SAGE \cite{Velculescu1995}, and DNA microarray \cite{Schena1995}.

%%Using DNA Microarrays to Measure Gene Expression. 
DNA Microarrays, also called `gene chips', are an efficient way to measure gene expression, allowing researchers to obtain the expression of thousands of genes at once. When active genes assemble proteins, they produce mRNA molecules. The mRNA molecules' strands are then copied to cDNAs (complementary DNAs) using the DNA base-pairing rules. The resulting cDNAs are then attached to fluorescent dye.  %using the DNA rule?
When the fluorescent cDNAs are put into a DNA microarray, each cDNA molecule will bind to the microarray spot containing pieces of its specific matching gene by base-pairing. This way, each microarray spot corresponds to a gene which was actively being transcribed into mRNA in the original cell.
The intensity and color of the fluorescence of each microarray spot are measured and analyzed by a computer program to make precise measurements of genes expressed at different levels. Further information about microarray technology can be found in \cite{Muller2005}.  

%%Gene Expression/Microarrays/molecular diagnosis and Cancer diagnosis 
%Cancer-Specific Gene Expression. 
Microarrays and molecular diagnosis have been used in cancer research and have produced very promising results. For example, researchers used microarrays to compare gene expression patterns in normal vs.\ cancerous stomach tissues and found that the PLA2G2A gene is expressed in the cancerous stomach tissue only. The researchers also found that stomach cancer patients with high expression levels of PLA2G2A had better 5-year survival prognosis than those with low expression levels \cite{NCI2013}.   
%Subtyping Cancer. 
Researchers also use microarrays to detect the differences in gene expression patterns within the same cancer type. In many cases, researchers have found that a single type of cancer based on microscope observations contains several subtypes based on their different gene expression patterns. For example, researchers have identified several subtypes of leukemia and four subtypes of lung adenocarcinoma, the most common type of lung cancer.

%%Molecular Diagnostics Has Many Uses. 
Besides being used for screening and diagnosing diseases, molecular diagnostics has many other uses. For example, expression patterns can provide information for new treatment design, treatment effectiveness evaluation, and patient response prediction. 

\section{Data Clustering}\label{secClustering}
%clustering overview
Clustering is an interdisciplinary research topic and is also known by researchers in different fields as unsupervised learning, exploratory data analysis, grouping, clumping, taxonomy, typology, and Q-analysis \cite{Jain2009}. Cluster analysis is defined as `a statistical classification technique for discovering whether the individuals of a population fall into different groups by making quantitative comparisons of multiple characteristics' and its first known use was in 1948 (Merriam-Webster Online Dictionary, 2013). 
The clustering algorithm was first developed by biologists in numerical taxonomy study in 1963 before being utilized by statisticians \cite{Ilango2011}. 
Clustering is used for class discovery, \textit{i.e.} exploration or discovery of the underlying patterns of a dataset by separating the dataset into groups, with little or no prior knowledge \cite{Everitt2001,Jain1988,Xu2005,Xu2009}. Clustering is also used for natural classification, \textit{i.e.} identifying the degree of similarity among organisms,
and compression, \textit{i.e.} organizing and summarizing data using cluster prototypes \cite{Jain2009}.  
Clustering has become increasingly popular as society increasingly generates an overwhelming amount of data, and it is often used as the first step in data analysis or as a preparation step for experimental work \cite{Linden2009,Xu2010}.

%similarity measure
There is no universally agreed upon definition of clusters \cite{Everitt2001}. A cluster is a set of objects that are compact (or similar to each other) and isolated (or dissimilar) from other clusters.
In reality, cluster definition is subjective, and its significance and interpretation requires related domain knowledge \cite{Jain2009}. Similarity measure is used by clustering methods to calculate the similarity between two objects. Different similarity measures will have different clustering results, as some objects may be similar to one another using one measure but dissimilar using another. Similarity between two objects can be measured in different ways, and the three dominant methods are distance measures, correlation measures, and association measures \cite{Ilango2011}. 
Common similarity measures include Euclidean distance, Manhattan distance, Maximum norm, Mahalanobis distance, Pearson coefficient, Spearman's rank correlation coefficient, angle between two vectors, and the Hamming distance.

%cluster validity
Since the process of clustering is subjective, judging the relative efficacy of clustering methods is difficult \cite{Baraldi2002,Jain1999}. Cluster validity is used to assess clustering results and can be classified into three categories: a) Internal validities formulate quality as a function of the given data set \cite{Hu2004}. Examples include Dunn's Validity Index, Silhouette Value, Hubert Gamma Statistic, Entropy, Xie-Beni, Normalized Mutual Information. b) External validities assess quality by additional external information such as category labels \cite{Hu2004}. Examples include Jaccard Index, Rand Index, Adjusted Rand Index, Variation of Information, Kappa Statistic, CA. c) Relative validities evaluate a clustering result by comparing it to results from other clustering methods.

%four steps 
The procedure of cluster analysis includes four steps \cite{Xu2005}: 
a) Step one is feature selection or extraction. Feature selection selects a subset of all features, and feature extraction generates novel features from the original ones by using some transformations \cite{Bishop1995,Jain1999,Jain2000,Xu2005}. 
b) Step two is clustering algorithm design or selection. Since clustering algorithms group objects based on some proximity measure, this step usually includes choosing an appropriate proximity measure and construction of a clustering criterion function, creating an optimization problem that has been well studied in the literature. 
c) Step three is cluster validation. This step calculates a confidence level for the clustering results. 
d) Step four is results interpretation. This step provides meaningful insights from the data. 

%limitation
There is no single clustering algorithm that performs best across all problems or data sets \cite{Kleinberg2002,Xu2005}. Therefore, it is important to study the characteristics of the problem and use an appropriate clustering strategy \cite{Xu2005}.  

%Properties
Properties to be considered in choosing a clustering algorithm include \cite{Berkhin2002}:
 a) feature type (numeric and non-numeric), 
 b) scalability (large datasets),
 c) handling high dimensional data,
 d) finding clusters of irregular shape,
 e) handling outliers,
 f) time complexity of the algorithm,
 g) data order dependency,
 h) assignment type (hard or strict vs.\ soft or fuzzy),
 i) prior knowledge and user defined parameters dependency, and
 j) interpretability and visulization of results.

%challenges
Despite many examples of successful applications of cluster analysis, there still remain many challenges due to the existence of many inherent uncertain factors \cite{Xu2005}. 
The following fundamental challenges in clustering \cite{Jain1988,Jain2009} are relevant even today \cite{Jain2009}: 
 a) definition of a cluster, %`What is a cluster?' %
 b) selection of features, %`What features should be used?' %
 c) normalization of the data, %`Should the data be normalized?' %
 d) outlier detection, %`Does the data contain any outliers?' %
 e) definition of pair-wise similarity, %`How do we define the pair-wise similarity?' %
 f) number of clusters, %`How many clusters are present in the data?'
 g) selection of clustering method, %`Which clustering method should be used?'
 h) existence of clustering tendency, and %`Does the data have any clustering tendency?'
 i) validity of the clusters. %`Are the discovered clusters and partition valid?'

%trends
Some recent trends in clustering include \cite{Jain2009}: semi-supervised clustering utilizing external or side information; interactive clustering, where a user can specify or change program parameters based on domain knowledge or results from previous clustering iterations; clustering ensembles, where the partitions resulting from different algorithms (or the same algorithm with different parameters) are combined; multi-objective clustering, where the clustering algorithm optimizes multiple specific objectives; large-scale clustering, which handles very large databases; multi-way clustering, which extends the bi-clustering framework and simultaneously clusters heterogeneous components of the data objects \cite{Bekkerman2005}; 
and heterogeneous data clustering for data comprising multiple types, such as rank data, dynamic data, graph data, and relational data \cite{Ilango2011}.

%The reason why cluster analysis program is needed? 

%taxonomy
Clustering techniques can be organized into categories. Different criteria may result in different categories of clustering algorithms \cite{Xu2005}. Furthermore, categorization of clustering algorithms is not straightforward or canonical, and categories can overlap \cite{Berkhin2002}. For convenience, in this review we use the following taxonomy, which is also widely used in the literature: hierarchical clustering (Section~\ref{subsecHierarchicalClustering}), partitioning clustering (Section ~\ref{subsecPartitioningClustering}), graph-based Clustering (Section~\ref{subsecGraphClustering}), distribution-based clustering (Section~\ref{subsecDistributionClustering}), density-based clustering (Section~\ref{subsecDensityClustering}), grid-based clustering (Section~\ref{subsecGridClustering}), clustering big data (Section~\ref{subsecBigDataClustering}), clustering high dimensional data (Section~\ref{subsecHighDimensionalClustering}), and other clustering techniques (Section~\ref{subsecOtherClustering}).
    

\subsection{Hierarchical Clustering} \label{subsecHierarchicalClustering} 

%what is, features, procedure, categories,  
Hierarchical clustering algorithms organize a data set into a hierarchical structure according to a similarity measure \cite{Xu2005}. It is based on the belief that nearby objects are more related than objects that are farther away \cite{Nangia2012}. 
These algorithms connect objects based on their similarity to form clusters, which is usually represented using a dendrogram. Hierarchical clustering algorithms differ in the choice of similarity measures, the linkage criterion (distance between clusters), and whether the process is agglomerative (bottom-up) or divisive (top-down). Agglomerative hierarchical clustering starts with singleton clusters and then recursively merges appropriate clusters, and divisive hierarchical clustering starts with one cluster containing all objects and recursively splits appropriate clusters \cite{Berkhin2002}.

Divisive clustering is very expensive in computation \cite{Everitt2001} and is not commonly used in practice \cite{Xu2005}. We focus on the agglomerative clustering first and then mention two divisive clustering algorithms named MONA and DIANA \cite{Kaufman2009,Xu2005}.  

%classic agglomerative examples
There are many agglomerative hierarchical clustering algorithms based on different linkage criterion.
 The single linkage method or nearest neighbor method \cite{Gower1969,Jain1988,Sibson1973,Sneath1973,Sneath1957,Xu2005} uses the distance between two closest objects in different clusters, and the shortest distance determines the merge of two clusters.  
 The complete linkage method or farthest neighbor method \cite{Defays1977,King1967,Sorensen1948,Xu2005} uses the distance between two farthest objects in different clusters, and the shortest distance determines the merge of two clusters. 
 These two methods are the simplest and most popular \cite{Xu2005}. 
 Average linkage methods include UPGMA (Unweighted Pair-Group Method using Arithmetic averages), WPGMA (Weighted Pair-Group Method using Arithmetic averages), UPGMC (Unweighted Pair Group Method using Centroids), and WPGMC (Weighted Pair Group Method using Centroids). UPGMA and UPGMC use a simple average, while WPGMA and WPGMC use a weighted average where the weight is the inverse of cluster size.   
 UPGMA \cite{Andrade1978,Everitt1980,Jain1988,Sneath1973,Sokal1958} uses average distance between two objects in different clusters, and the shortest average distance determines the merge of two clusters. 
 WPGMA or weighted average linkage method \cite{Murtagh1983} uses weighted average distance between two objects in different clusters, and the shortest average distance determines the merge of two clusters. 
 UPGMC or centroid linkage method \cite{Sneath1973} uses Euclidean distance between unweighted centroids (calculated by arithmetic mean) of different clusters, and the shortest distance determines the merge of two clusters. 
 WPGMC or median linkage method \cite{Sneath1973} uses Euclidean distance between weighted centroids of different clusters, and the shortest distance determines the merge of two clusters. 
 Minimum-variance method or Ward's method \cite{Ward1963} considers the relationship of all objects in a cluster. Its objective is to form clusters such that the increase of variance within each group is minimized \cite{Wildi2010}.  Further readings about these methods include \cite{Everitt2001,Xu2005,Yager2000}.

%divisive examples
What follows are examples of divisive hierarchical clustering algorithms.
DIANA \cite{Kaufman2009} (DIvisive ANAlysis Clustering) selects in each dividing step the cluster with the largest diameter and divides it into two new clusters. 
MONA \cite{Kaufman2009} (MONothetic Analysis Clustering of Binary Variables) divides clusters based a single well-chosen variable (or feature), whereas most other hierarchical methods use all variables (or features).  

%Advantages/strenthes
Advantages of hierarchical clustering are 
a) Good visualization with dendrogram representation \cite{Xu2005,Xu2010,Jain1988,Theodoridis2006}, 
b) Very informative descriptions with dendrogram representation \cite{Jain1988,Theodoridis2006,Xu2005,Xu2010}, and
c) Flexibility regarding the number of clusters, since the clustering results can be obtained by cutting the dendrogram at different levels.   

%Disadvantages/weaknesses
Disadvantages of hierarchical clustering are \cite{Xu2005,Xu2010}: 
a) Lacking of robustness and sensitivity to noise and outliers.
b) High computational complexity, which limit their application on large scale data.
c) Tendency to form clusters with spherical shapes instead of natural shapes.  
d) Prone to reversal phenomenon \cite{Okabe2012}.

%new/other development 
 BIRCH \cite{Zhang1996} (Balanced Iterative Reducing and Clustering using Hierarchies) clusters incoming data objects incrementally and dynamically. It first builds a CF (Clustering Feature) tree dynamically as new data objects are inserted and then applies an agglomerative hierarchical clustering algorithm to the nodes represented by their CF vectors. After obtaining a centroid for each cluster, it assigns each data object to its nearest centroid. 
 CURE \cite{Guha1998} (Clustering Using REpresentatives) uses a number of representative data points in a cluster to evaluate the distance between clusters. Closest cluster pair are merged at each step of its hierarchical clustering process. 
 ROCK \cite{Guha2000} (RObust Clustering using linKs) uses links and not distances when merging clusters for boolean and categorical data.  
 DISMEA \cite{Spath1980} uses the k-means algorithm to divide a cluster into two clusters.
 The Edwards and Cavalli-Sforza Method \cite{Edwards1963} divides all available clusters at each step. 
 Minimum Spanning Tree-based clustering algorithms \cite{Eldershaw1997,Paivinen2005,Zahn1971} construct an MST (Minimum Spanning Tree) \cite{Kruskal1956,Nesetril2001,Prim1957} from a data set and produce a group of clusters by removing selected edges. 

Figure ~\ref{fig:HierarchicalClustering} shows an example of hierarchical clustering.

\begin{figure}[t]
	\centering
		\includegraphics[width=0.8\textwidth]{images/HierarchicalClustering.png}
	\caption{Hierarchical Clustering \cite{Ho2012}}
	\label{fig:HierarchicalClustering}
\end{figure}


\subsection{Partitioning Clustering} \label{subsecPartitioningClustering} 

%what is, features, procedure, categories,
Partitioning clustering algorithms divide objects into clusters without hierarchical structure. Clusters are represented by a central vector. Given the number of clusters, partitioning clustering assigns the objects to the closest cluster center. Partitioning algorithms can be grouped into k-means methods and k-medoids methods. k-means methods use the centroid of objects within a cluster as center. k-medoids methods use the most appropriate object within a cluster as center. 

%k-means
k-means clustering \cite{Berkhin2002,Forgy1965,Hartigan1975,Hartigan1979,MacQueen1967,Steinhaus1956,Xu2005,Xu2010} is very simple, but one of the best known and popular clustering algorithms. 
There are many variations of the basic k-means clustering. 
 Classic k-means reassigns data objects based on optimization of the objective function. If a reassigning has positive effect, the data object is reassigned and the cluster centers are updated.  
 ISODATA \cite{Ball1965} (Iterative Self-Organizing Data Analysis Technique) splits and merges intermediate clusters based on a user-defined threshold and iterates until the threshold is reached.  
 FORGY \cite{Forgy1965} reassigns objects to nearest centroids and recomputes centroids. It iterates until a stopping criterion is achieved.
 Fuzzy c-means \cite{Bezdek1981,Dunn1973} assigns fuzzy cluster membership to each data object, and updates cluster centers and membership after each iteration.  
 Methods to speed up k-means and fuzzy C-means such as brFCM (bit reduction by Fuzzy C-Means) \cite{Eschrich2003} replace similar data objects with their centroid before clustering. 

%k-medoid
Variations of k-medoid \cite{Kaufman2009} methods are as follows. 
 PAM (Partitioning Around Medoids) assigns each data object to the closest medoid and iteratively reassigns objects and updates medoids to optimize the objective function.  
 CLARA (Clustering LARge Applications) \cite{Kaufman2009} applies PAM on multiple subsets or samples of the data set, and selects the best clustering as output. 
 CLARANS (Clustering Large Applications based upon RANdomized Search) \cite{Ng1994} searches a graph where each node is a set of medoids. It selects a node randomly in search for a local minimum among its neighbor nodes through iterations and outputs the best node to form clustering results.  

%advantages
Advantages of partitioning clustering are a) simple, straightforward and easy implementation, b) fast execution with computation complexity of \BigO{n}, c) very suitable for compact and hyperspherical clusters, d) computational rigor (firm foundation of analysis of variances).   

%disadvantages
Disadvantages of partitioning clustering are 
a) they are still subjective processes that are sensitive to assumptions, b) they require the number of clusters to be specified in advance, c) they prefer clusters of approximately similar size, as they will always assign an object to the nearest center, often leading to incorrectly cut borders in between of clusters, d) they are subject to easy trapping in local minima and sensitivity to the initial partition (hill-climbing optimization method).

%other developments
Other developments are as follows. 
 Bisecting k-means \cite{Steinbach2000} recursively partitions a cluster into two. 
 KD-trees k-means \cite{Pelleg1999} uses the KD-Tree data structure to speed up the assignment of data objects to their closest cluster by reducing the number of nearest-neighbor queries in the traditional algorithm.
 Scaling k-means \cite{Bradley1998} retains important data objects and summarizes or discards other objects. Centroids of the resulting data set are then used on the whole data set. 
 X-means \cite{Pelleg2000} finds the number of clusters K automatically by optimizing a criterion function such as AIC (Akaike Information Criterion) or BIC (Bayesian Information Criterion). 
 Kernel k-means \cite{Scholkopf1998} enhances k-means by using a kernel function that nonlinearly maps the original feature space to a higher dimensional one, where clusters are more separable. 
 Weighted kernel k-means \cite{Dhillon2004} further extends kernel k-means by assigning a weight for each cluster. The weight is defined as the reciprocal of the number of data objects in the cluster.
 GA k-means \cite{Babu1993} applies a genetic algorithm to improve cluster centers initialization for k-means.
 Simulated annealing \cite{Al-Sultan1993,Brown1991,Klein1989,Selim1991} uses simulated annealing optimization to avoid local optima and find the global minimum solution.  
 Soft assignment \cite{Zhang2001} assigns data objects to different clusters with appropriate weights to improve the optimization process. It uses Harmonic Averages of the distances from the data object to all the centers. 
 Mahalanobis distance \cite{Mao1996} is used to detect clusters with hyperellipsoidal shapes.
 Maximum of intra-cluster variances \cite{Gonzales1985} can be used as the objective function instead of the sum to obtain good clustering results. 
 k-prototypes \cite{Huang1998} incorporates categorical data as a generalization approach.
 Accelerated k-means by triangle inequality \cite{Elkan2003} avoids unnecessary distance calculations by using the triangle inequality and keeping track of lower and upper bounds for distances between data objects and cluster centers. 
 k-means++ \cite{Arthur2007} improves the speed and the accuracy of k-means by using a simple randomized seeding technique. 

Figure ~\ref{fig:PartitioningClustering} shows an example of partitioning clustering.

\begin{figure}[t]
	\centering
		\includegraphics[width=0.8\textwidth]{images/PartitioningClustering.png}
	\caption{Partitioning Clustering \cite{Chire2011-1}}
	\label{fig:PartitioningClustering}
\end{figure}


\subsection{Graph-based Clustering} \label{subsecGraphClustering}

%what is, features, procedure, categories 
Graph-based clustering algorithms construct a graph/hypergraph from the data and then partition the graph/hypergraph into subgraphs/subhypergraphs or clusters. Each vertex represents a data object, and the edge weight represents the similarity of two vertices \cite{Chen2010}. The edges in the same subgraph/subhypergraph should have high weights, and the edges between different subgraphs/subhypergraph should have low weights \cite{Chen2010}. It is also called spectral clustering \cite{Jain2009}.

%typical algorithms? 
Representative algorithms are as follows.
 Chameleon \cite{Karypis1999} uses a connectivity graph and graph partitioning to build small clusters, followed by the agglomerative hierarchical clustering process. Its key feature is that it considers both interconnectivity and closeness when merging clusters.
 CACTUS (Clustering Categorical Data Using Summaries) \cite{Ganti1999} detects candidate clusters based on the summary of the data set and determines the actual clusters through a validation process against the candidate clusters. It uses a similarity graph to represent the inter-attribute and intra-attribute summaries \cite{Gan2011}.      
 A Dynamic System-based Approach or STIRR (Sieving Through Iterated Relational Reinforcement) \cite{Gibson2000} represents each attribute value as a weighted vertex in a graph. It iteratively assigns and propagates weights until a fixed point is reached. Different weight groups correspond to different clusters on the attribute.
 ROCK (Robust Clustering algorithm for Categorical Data) \cite{Guha2000} repeatedly merges two clusters until the specified number of clusters is reached, and it uses data sampling to improve complexity. It uses a connectivity graph to calculate the similarities between data objects \cite{Gan2011}. 

%advantages
The advantages of graph-based clustering are \cite{Chen2010}: a) A graph is an elegant data structure that can
model many real applications. b) It is based on solid mathematical foundations, including spectral
theory and Markov stochastic process. c) It produces optimal clustering (optimizing a quality measure instead of acting greedily toward the final clustering).

%disadvantages
The major disadvantage of graph-based clustering is that it may be slow when working on large scale graphs \cite{Chen2010}.

%other developments? 
Other developments are as follows.
 The Ratio Cut algorithm \cite{Hagen1992} adopts a cluster size constraint, which is the number of data points in a cluster.     
 The Normalized Cut (NCut) algorithm \cite{Shi2000} is an approximate graph-cut based clustering algorithm with a cluster size constraint, which is the volume of the cluster or sum of edge weights within a cluster. 
It also has a multiclass version \cite{Yu2003}.
 The MNCut (Modified Normalized Cut) algorithm \cite{Meila2001} gives a new interpretation to the NCut algorithm in the framework of a Markov Random Walk. 
 Ng's method \cite{Ng2001} derives a new data representation from normalized eigenvectors of a kernel matrix simultaneously and in a particular manner.
 Laplacian Eigenmap \cite{Belkin2003} uses the eigenvectors of the graph Laplacian to represent data.
 Pairwise Data Clustering by Deterministic Annealing \cite{Hofmann1997} uses proximity measures between the data objects to represent data. 
 Dominant Sets Pairwise Clustering \cite{Pavan2007} relates clusters to maximal dominant sets \cite{Motzkin1965} in pair-wise clustering.
 Fast approximate spectral clustering \cite{Yan2009} applies a distortion-minimizing local transformation to the data to speed up conventional spectral clustering. 
Active spectral clustering \cite{Wang2010} follows the concept of constrained clustering and uses pairwise relations. Its constraints are specified in a incremental manner.
Locally-scaled spectral clustering using empty region graphs \cite{Correa2012} employs $\beta$-skeleton (a subset of empty region graphs) and non-linear diffusion to define a locally adapted affinity matrix which defines the similarity of two data objects.

Figure ~\ref{fig:GraphClustering} shows an example of graph-based clustering.

\begin{figure}[t]
	\centering
		\includegraphics[width=0.8\textwidth]{images/GraphClustering.png}
	\caption{Graph-based Clustering \cite{Netplexity2014}}
	\label{fig:GraphClustering}
\end{figure}

\subsection{Distribution-based Clustering} \label{subsecDistributionClustering} 

%what is, features, procedure?, categories?
Distribution-based clustering views or assumes that the data are generated by a mixture of probability distributions, each of which represents a different cluster \cite{Gan2007,McLachlan1988}. This way, a cluster can be seen as objects generated by the same distribution. Thus, a particular clustering method can be expected to produce good results when the data conform to the method's distribution model \cite{Gan2007}. It is also called model-based clustering. There are usually two approaches to form the model: the classification likelihood approach and the mixture likelihood approach \cite{Gan2007}.

%history and earlier work
Distribution-based clustering has a long history. Early works include 
\cite{Binder1978,Day1969,Scott1971b,Wolfe1970}. A survey of cluster analysis in a probabilistic and inferential framework is presented in \cite{Bock1996}.  

%typical methods 
Representative algorithms are as follows. 
 The EM (Expectation-Maximization) clustering algorithm \cite{Dempster1977} is the most popular method in distribution-based clustering. It tries to fit the data set into the assumed number of Gaussian distributions by moving the means of Gaussian distributions toward the cluster centers. 
 COOLCAT (reducing the entropy, or �COOLing� of the CATegorical data clusters)\cite{Barbara2002} uses entropy to cluster categorical data. It consists of data sampling and incremental assignment. 
 STUCCO (Search and Testing for Understandable Consistent Contrasts) \cite{Bay1999} uses tree searching and significant contrast-sets to find clusters.
 GMDD (Gaussian Mixture Density Decomposition) \cite{Zhuang1996} uses a recursive approach and identifies each Gaussian component in the mixture successively.
 Autoclass \cite{Cheeseman1996} is based on the classic distribution-based approach and uses a Bayesian method to determine the optimal clusters.  
 P-AutoClass \cite{Pizzuti2003} is a parallel version of Autoclass and can be used on large data sets. 

%advantages
The advantages of distribution-based clustering are as follows: a) It can be modified to handle complex data \cite{Berkhin2002}, b) It has a solid theoretical foundation, c) Its results are easily interpretable \cite{Berkhin2002}, d) It not only provides clusters, but also produce complex models that capture relationships among attributes, e) Results are independent of the timing of consecutive batches of data \cite{Berkhin2002}, f) It is good for online learning since the intermediate mixture model can be used to cluster objects \cite{Berkhin2002}, g) the Mixture model can be naturally generalized to cluster heterogeneous data \cite{Berkhin2002}.

%disadvantages
The disadvantage of distribution-based clustering is the
difficulty in choosing the appropriate model complexity (since a more complex model will usually be able to explain the data better but may cause an overfitting problem from excessive parameter set). 

%new developments
Other developments are as follows. 
 Latent Dirichlet Allocation (LDA) \cite{Blei2003} uses a hierarchical Bayesian model that has three levels. Each data object is modeled as a finite mixture over an underlying set of groups (or clusters) of objects. Each group (or cluster) is modeled as an infinite mixture over a set of group (or cluster) probabilities. 
 Pachinko Allocation Model (PAM) \cite{Li2006} uses a Directed Acyclic Graph (DAG) to model cluster correlations. The leaves of the DAG represent data objects, and the interior nodes represent correlations.
 Undirected graphical model for data clustering \cite{Welling2005} is based on exponential family distributions and the semantics of undirected graphical models. It uses the technique of minimizing contrastive divergence to speed up the process.
 Robust cluster analysis via mixture models method \cite{Mclachlan2006} uses the mixtures of multivariate t distributions approach to the clustering. It also uses the t distribution to cluster high-dimensional data via mixtures of factor analyzers.
 Online learning for LDA method \cite{Hoffman2010} is an online Variational Bayes (VB) algorithm for LDA. It uses natural gradient step in online stochastic optimization, which converges to a local optimum of the VB objective function. 

Figure ~\ref{fig:DistributionClustering} shows an example of distribution-based clustering.

\begin{figure}[t]
	\centering
		\includegraphics[width=0.8\textwidth]{images/DistributionClustering.png}
	\caption{Distribution-based Clustering \cite{Chire2011-2}}
	\label{fig:DistributionClustering}
\end{figure}

\subsection{Density-based Clustering} \label{subsecDensityClustering}

%what is, features, procedure?, categories?
Density-based clustering defines clusters as dense regions of data objects separated by low-density regions. A cluster is a connected dense component and grows in any direction that density leads \cite{Gan2007}. Objects in low-density areas which separate clusters are usually considered to be noise and border points. There are two major approaches for density-based clustering \cite{Berkhin2002}: the connectivity approach pins density to a training data point; the density function approach pins density to a point in the attribute space. 

%representative algorithms
Representative algorithms for the connectivity approach are as follows.  
 DBSCAN (Density-Based Spatial Clustering of Applications with Noise) \cite{Ester1996} starts by selecting a data object and tries to find all data objects density-reachable from it to form a cluster. If none are found, the algorithm selects a new data point and repeats.  
 GDBSCAN (Generalized DBSCAN) \cite{Sander1998} generalizes the concept of neighborhood by permitting the use of any distance function besides Euclidian distance and allows other measures besides simply counting the objects to define the cardinality of that neighborhood.
 OPTICS (Ordering Points To Identify the Clustering Structure) \cite{Ankerst1999} is like an extended DBSCAN algorithm. It does not assign cluster memberships but stores the order in which the data objects are processed as well as the core-distance and a reachability-distance for each data object. An extended DBSCAN is used to assign cluster memberships. 
 DBCLASD (Distribution Based Clustering of LArge Spatial Databases) \cite{Xu1998} uses the notion of clusters based on the distance distribution and incrementally augments an initial cluster by its neighboring points as long as the nearest neighbor distance set of the resulting cluster still fits the expected distance distribution.

Representative algorithms for the density function approach are as follows. 
 DENCLUE (DENsity-based CLUstEring) \cite{Hinneburg1998} calculates the impact of each data object within its neighborhood (\textit{i.e.} influence function) and determines clusters mathematically by identifying local maxima of the overall density function (\textit{i.e.} density-attractors).

%advantages
The advantages of density-based clustering are as follows: a) They can find clusters of arbitrary shapes, in contrast to many other methods. b) Time complexity is low (linear or \BigO{n}). c) It is deterministic for core and noise points (but not for border points), therefore there is no need to run it multiple times. d) It can handle noise well \cite{Gan2007}. e) The number of clusters is not required, since it finds clusters and the number of clusters automatically \cite{Gan2007}. f) Results are independent of data ordering \cite{Berkhin2002}. g) There are no limitations on the dimension or attribute types \cite{Berkhin2002}.

%disadvantages
The disadvantages of density-based clustering are as follows: a) It is often difficult to detect cluster boarders when the cluster density decreases continuously (\textit{i.e.} arbitrary borders). b) For a mixtures of Gaussians data set, distribution-based clustering (\textit{e.g.} EM) usually outperforms density-based clustering. c) Limitations in processing high-dimensional data, since it is difficult to distinguish high-density regions from low-density regions when the data is high-dimensional \cite{Jain2009}. d) Most density-based clustering algorithms were developed for spatial data \cite{Gan2007}.

%new developments
Other developments are as follows. 
 BRIDGE \cite{Dash2001} integrates the k-means algorithm and the DBSCAN algorithm. k-means is first performed, and then DBSCAN is used on each partition. Finally, results are improved by removing the noise found by DBSCAN.
 Jarvis�Patrick algorithm \cite{Frank1994} partitions the data set into clusters based on the number of shared nearest neighbors. It first identifies the k nearest neighbors of each data object and then merges two data objects at a time.  
 C-DBSCAN (Constrained-DBSCAN) \cite{Ruiz2007} enhances the DBSCAN algorithm with pairwise constraints.  
 SCAN (Structural Clustering Algorithm for Networks) \cite{Xu2007-2} can detect hubs and outliers, in addition to clusters in networks (or graphs). It uses a structural similarity measure to cluster vertices. 

Figure ~\ref{fig:DensityClustering} shows an example of density-based clustering.

\begin{figure}[t]
	\centering
		\includegraphics[width=0.8\textwidth]{images/DensityClustering.png}
	\caption{Density-based Clustering \cite{Chire2011-3}}
	\label{fig:DensityClustering}
\end{figure}


\subsection{Grid-based Clustering} \label{subsecGridClustering} 

%what is, features, procedure, categories?
Grid-based clustering operates on space partitioning instead of data partitioning to produce clusters \cite{Berkhin2002}. It first creates the grid structure by partitioning the data space into cells (or cubes) and then clusters the cells based on their densities.

Representative algorithms are as follows. 
 BANG-clustering \cite{Berkhin2002,Schikuta1997} uses a multi-dimensional grid data structure to organize or partition the data. It uses the cell information in the grid and clusters the cells.    
 STING (A STatistical INformation Grid approach) \cite{Wang1997} uses a hierarchical structure of grid cells with a top-down approach. It labels a cell to be relevant or not at a specified confidence level. Then, it finds all the regions formed by relevant cells. 
 STING+ \cite{Berkhin2002,Wang1999} uses a similar hierarchical cell structure as STING and introduces an active spatial data mining approach. 
 OptiGrid (Optimal Grid) \cite{Hinneburg1999} constructs an optimal grid partitioning of the data by finding the best partitioning hyperplanes for each dimension with projections of the data.   
 GRIDCLUS (GRID-CLUStering) \cite{Schikuta1996} organizes the space surrounding the clusters with a grid data structure. It uses a topological neighbor search to cluster the grid cells.
 GDILC (Grid-based Density-IsoLine Clustering) \cite{Zhao2001} is based on the idea that the density-isoline figure reflects the distribution of data. It uses a grid-based approach to calculate the density and finds dense regions.   
 WaveCluster (Wavelet-based clustering) \cite{Sheikholeslami1998} transforms the original feature space by applying wavelet transform and then finds the dense regions in the new space. It yields sets of clusters at different resolutions and scales, which can be chosen based on the user's needs.
 FC (Fractal Clustering) \cite{Barbara2000} adds one data object at a time to one cluster in such a way that the fractal dimension changes the least after adding the data object. 

%advantages: 
The advantages of grid-based clustering are as follows:
a) It is fast and works well with large data sets (since speed is independent of the number of objects in the data) \cite{Berkhin2002,Gan2007}.   
b) It handles noise well \cite{Berkhin2002}. 
c) It is independent of data ordering \cite{Berkhin2002}.
d) It can handle attributes of different types \cite{Berkhin2002}.
e) It can be used as an intermediate step in many other algorithms such as CLIQUE and MAFIA \cite{Berkhin2002}. 

%disadvantages
The disadvantages of grid-based clustering are as follows:
a) Most algorithms need the user to specify grid size or density thresholds, which can be difficult (fine grid sizes result in high computational time, while coarse grid sizes result in low quality of clusters) \cite{Gan2007}. 
b) Some grid-based clustering algorithms (\textit{e.g.} STING, WaveCluster) are not good at high dimensional data \cite{Gan2007}.  

%New/other developments: 
Other developments are as follows.  
 AMR (Adaptive Mesh Refinement clustering) \cite{Liao2004} creates grids at multiple resolutions where higher resolution grids are applied to the localized denser regions.
 O-Cluster (Orthogonal partitioning CLUSTERing) \cite{Milenova2002} is a variant of OptiGrid. It creates a hierarchical grid-based structure by making axis-parallel (orthogonal) partitions on the input data. It operates recursively, and the final irregular grid frames the data into clusters. 
 CBF (Cell-Based Filtering) \cite{Chang2002} splits each dimension into a set of partitions using a filtering-based index. It then creates cells based on the overlapping regions of the partitions.
 PGMCLU (Parallel Grid-based CLUstering algorithm for Multi-density datasets) \cite{Chen2009} consists of parallel data partitioning, local clustering, and merging local clusters. It introduces a new measure called grid compactness for the degree of tightness between data objects within the grid, and the notion of grid feature for summarizing the information about a grid.

Figure \ref{fig:GridClustering} shows an example of grid-based clustering.

\begin{figure}[t]
	\centering
		\includegraphics[width=0.8\textwidth]{images/GridClustering.png}
	\caption{Grid-based Clustering \cite{Yolkowski2014}}
	\label{fig:GridClustering}
\end{figure}


\subsection{Clustering Big Data} \label{subsecBigDataClustering}
Big data clustering refers to clustering on millions of data objects \cite{Jain2009}. These algorithms need to have good scalability and process big data within reasonable computing time and memory space \cite{Berkhin2002}. 
A high computational complexity would dramatically limit an algorithm's application to big data. The strategies used for big data clustering can be categorized into sampling, data summarization, distributed computing, and incremental learning.   

\subsubsection{Sampling:}
Sampling methods select a sample of the original large data set and perform clustering over the sample data. Old-fashioned sampling methods may or may not use rigorous statistical reasoning \cite{Berkhin2002}. Newer sampling methods use special uniform checks to control their adequacy \cite{Berkhin2002}. Advantages are that it is simple to implement and can screen out most outliers. However, small clusters may be missed. 

Examples are as follows. 
CURE (Clustering using REpresentatives) \cite{Guha1998} and 
ROCK (RObust Clustering using linKs) \cite{Guha2000} were covered in Section~\ref{subsecHierarchicalClustering}. 
CLARA (Clustering LARge Applications) \cite{Kaufman1987} draws several samples from the data set, runs PAM on each of them, and selects the best result.
CLARANS (Clustering Large Applications based on RANdomized Search) \cite{Ng1994} starts with a new randomly-selected node (a set of k potential medoids) in the graph in search of the local optimum. It repeats if a local optimum is found. 

\subsubsection{Data Summarization:}
Data summarization methods calculate data summary statistics and perform clustering on the summaries instead of the original data. The advantage is that the requirement for the storage of and frequent operations on the large amount of data are greatly reduced, saving both computational time and storage space. The disadvantage is reduced cluster quality. 

Examples are as follows.
 BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) was covered in Section~\ref{subsecHierarchicalClustering}. 
 BUBBLE \cite{Ganti1999-2} instantiates generalized BIRCH for data in a distance space.   
 BUBBLE-FM (BUBBLE-FastMap) \cite{Ganti1999-2} improves upon BUBBLE by reducing the computation time using FastMap \cite{Faloutsos1995}. 
 EMADS (EM Algorithm for Data Summaries) \cite{Jin2002} directly generates a Gaussian mixture model from simplified data summaries. 
 bEMADS (BIRCH's EMADS) \cite{Jin2002} uses data summarization procedures in the BIRCH algorithm. 
   
\subsubsection{Distributed Computing:}
Distributed computing methods divide a large data set into smaller data sets and perform clustering on each smaller data set. 
The advantage is that clusterings on each smaller data set can be done in parallel to reduce the overall computation time \cite{Jain2009}.
The disadvantage is the overhead and complexities due to the dividing and combining steps. 

Examples are as follows. 
Parallel k-means \cite{Dhillon1999} is a parallel implementation of the k-means clustering algorithm.
DBDC (Density Based Distributed Clustering) \cite{Januzaj2004} clusters distributed data locally and extracts suitable representatives from these local clusters to send to a global site where the complete clusters are restored based on the local representatives. It uses a density-based clustering algorithm for both local and global clustering.
Parallel spectral clustering in distributed systems \cite{Chen2011} makes the dense similarity matrix sparse by retaining nearest neighbors using a parallel approach. 

\subsubsection{Incremental Learning:} \label{subSubSecIncrementalLearning} 
Incremental learning methods process one data object at a time and may discard it. They require only one single pass over all data objects, in contrast to most clustering methods that require multiple passes over data objects before identifying the cluster centers \cite{Jain2009}. Advantages are: improved clustering efficiency in terms of data storage and processing time (they can admit new data objects without learning from scratch \cite{Xu2010}); handling outliers well \cite{Berkhin2002}; resumable processing which makes it very suitable for dynamic big data sets \cite{Berkhin2002}. Disadvantages are that results depend on data order and may not be stable \cite{Carpenter1987,Moore1989,Xu2010}, and can result in lower quality clusters \cite{Berkhin2002}.  

Examples are as follows. 
DIGNET \cite{Thomopoulos1995,Wann1997} moves cluster centers toward a new data point with each new addition.
Hartigan's leader algorithm \cite{Hartigan1975} uses a distance/similarity threshold to decide if a data point should be added to the cluster or used for a new cluster center.
ART (Adaptive Resonance Theory) family \cite{Carpenter1987-2,Xu2010} simulates neural circuits that are believed to trigger fast learning. It includes a large family of neural network variants such as 
ART1 \cite{Carpenter1987}, ART2 \cite{Carpenter1987-2}, Gaussian ART \cite{Williamson1996}, Bayesian ART \cite{Vigdor2007}, Ellipsoid ART \cite{Anagnostopoulos2001}, ART tree \cite{Wunsch1991,Wunsch1993}, ARTMAP \cite{Carpenter1991}, Q-learning ART \cite{Brannon2009}, Fuzzy ART \cite{Carpenter1992}. 
Charikar's incremental clustering \cite{Charikar1997} maintains a clustering of the data objects so that the maximum cluster diameter is minimized as new data objects are added.
GenIC (Generalized Incremental algorithm for Clustering) \cite{Gupta2004} divides the data stream into chunks or windows, updating each cluster center with each new data object addition and merging clusters at the end of a window of data.
Cobweb \cite{Fisher1987} is an incremental system for hierarchical clustering, which enables bi-directional hill-climbing search through the space of hierarchical schemes. 


\subsection{Clustering High Dimensional Data} \label{subsecHighDimensionalClustering} 
High Dimensional Data clustering refers to clustering on data objects that represent from a few dozen to thousands or more features. Such high dimensional data are often seen in areas such as medicine (\textit{e.g.} microarray experiments), and text documents (\textit{e.g.} word-frequency vector methods \cite{Chakrabarti2003}).  
Clustering high dimensional data is tremendously difficult. One problem is that increased irrelevant features eliminate the likelihood of clustering tendency \cite{Berkhin2002}. Another problem is the `curse of dimensionality', or lack of data separation, in high dimensional space (the problem becomes severe for dimensions greater than 15) \cite{Berkhin2002}. 
Performing feature selection before applying clustering can improve the first problem. Principal Component Analysis (PCA) \cite{Pearson1901} is commonly used. However, the dimension may still be high after feature selection. In this review, we discuss techniques that have been developed to address such situations: projected clustering, subspace clustering, bi-clustering (or co-clustering), tri-clustering, hybrid approaches, and correlation clustering.   

\subsubsection{Projected Clustering:}
Projection techniques map data objects from a high dimensional space to a low dimensional space, while maintaining some of the original data's characteristics \cite{Avogadri2009}.

Examples are as follows.
PreDeCon  \cite{Bohm2004} finds subsets of feature vectors that have low variance along subsets of attributes. 
PROCLUS \cite{Aggarwal1999} finds the candidate clusters and dimensions by using medoids. For each medoid, the subspace is determined based on attributes with low variance. 
Random projections for k-means clustering \cite{Boutsidis2010} implements a dimensionality reduction technique for k-means clustering based on random projections. 

\subsubsection{Subspace Clustering:}
Subspace clustering algorithms identify clusters in appropriate subspaces of the original data space. 

Examples are as follows.   
 CLIQUE (CLustering In QUEst) \cite{Agrawal1998} partitions the data space into units and then finds the maximum sets of connected dense units. 
 SUBCLU (density-connected Subspace Clustering) \cite{Kailing2004} adopts the notion of density-connectivity introduced in DBSCAN (Section~\ref{subsecDensityClustering}) and uses the monotonicity of density-connectivity to prune subspaces.
 CACTUS (Clustering Categorical Data Using Summaries) is covered in Section~\ref{subsecGraphClustering}.  
 ENCLUS (ENtropy-based CLUStering) \cite{Cheng1999} finds clusters in subspaces based on entropy values of subspaces. Subspaces with lower entropy values typically have clusters. It then applies CLIQUE or other clustering algorithms to such subspaces.
 MAFIA (Merging of Adaptive Finite Intervals) \cite{Goil1999} uses adaptive grids in each dimension and then merges them to find clusters in higher dimensions. 
 OptiGrid (Optimal Grid) is covered in Section~\ref{subsecGridClustering}. 
 MrCC (Multi-resolution Correlation Cluster detection) \cite{Cordeiro2010} constructs a novel data structure based on multi-resolution and detects correlation clusters by identifying initial clusters as axis-parallel hyper-rectangles with
high data densities, followed by merging overlapping initial clusters. 

Figure ~\ref{fig:SubspaceClustering} shows an example of subspace clustering.

\begin{figure}[t]
	\centering
		\includegraphics[width=0.8\textwidth]{images/SubspaceClustering.png}
	\caption{Subspace Clustering \cite{Slowmo2010}}
	\label{fig:SubspaceClustering}
\end{figure}

\subsubsection{Hybrid Approaches:} 
Hybrid approaches find overlapping clusters. 
Some of them find only potentially interesting subspaces and use full-dimensional clustering algorithms to obtain the final clusters.  

Examples are as follows. 
DOC (Density-based Optimal projective Clustering) \cite{Procopiuc2002} uses a global density threshold to compute an approximation of an optimal projective cluster.
FIRES (FIlter REfinement Subspace clustering) \cite{Kriegel2005} first computes one-dimensional clusters and then merges them by applying `clustering of clusters' based on the number of intersecting points between clusters. 
P3C (Projected Clustering via Cluster Cores) \cite{Moise2006,Moise2008} first computes intervals matching or approximating higher-dimensional subspace clusters on every dimension and then aggregates those intervals into cluster cores. The cluster cores are refined and used to assign data objects.

\subsubsection{Bi-clustering:}\label{subsubsecBiClustering}
Bi-clustering is also called bi-dimensional clustering \cite{Cheng2000}, co-clustering, coupled clustering, or bimodal clustering. Bi-clustering is popular in bioinformatics research, especially in gene or sample clustering. 
For gene expression data, there are experimental conditions in which the activity of genes is uncorrelated. This causes limitations for results obtained by standard clustering methods. So bi-clustering algorithms that can perform simultaneous clustering on the genes and conditions are developed to find subgroups of genes and subgroups of conditions in which the genes exhibit highly correlated activities for every condition \cite{Madeira2004}.

Examples are as follows. 
 CTWC (Coupled Two-Way Clustering) \cite{Getz2000} generates submatrices by an iterative process and considers only those submatrices whose rows and columns belong to genes and samples/conditions that were in a stable cluster in a previous iteration. 
 ITWC (Interrelated Two-Way Clustering) \cite{Tang2001} clusters the rows and then clusters the columns, based on each row cluster. It keeps the cluster pairs that are most dissimilar. 
 Block Clustering \cite{Hartigan1975} sorts the data by row mean or column mean and splits the rows or columns such that the variance within each `block' is reduced. It then repeats and splits rows or columns differently. 
 $\delta$-biclusters \cite{Cheng2000} or CC algorithm (Cheng and Church's) finds biclusters whose rows and conditions show coherent values, using mean-squared residue.
 SAMBA (Statistical-Algorithmic Method for Bicluster Analysis) \cite{Tanay2004} uses probabilistic modeling and graph theoretic techniques to find subsets of rows whose values are very different in a subset of columns. 
 Plaid Models \cite{Lazzeroni2000} allows biclusters to overlap, \textit{i.e.} a gene or a sample/condition can belong to more than one cluster.  
 Information-theoretic co-clustering \cite{Dhillon2003} intertwines the row and column clusterings to increase mutual information.

\subsubsection{Correlation Clustering:}
Correlation clustering uses the correlations among attributes to guide the clustering process. These correlations may be different and exist in different clusters and cannot be reduced to uncorrelated ones by traditional global decorrelation techniques. Such correlations create clusters with different spatial shapes, and local correlation patterns are used to define the similarity between data objects. Correlation clustering is closely related to biclustering. 

Examples are as follows. 
ORCLUS (ORiented projected CLUSter generation) \cite{Aggarwal2000} is similar to k-means but uses a distance function based on an eigensystem, \textit{i.e.} the distance in the projected subspace. The eigensystem is adapted during iterations and close pairs of clusters are merged.   
4C (Computing Correlation Connected Clusters) \cite{Bohm2004} takes a density-based approach and uses a density criterion to grow clusters. The density criterion is the minimal number of data objects within the neighborhood of a data object. The neighborhood is based on distance between two data objects in the eigensystems.  
HiCO (Hierarchical COrrelation clustering) \cite{Achtert2006} defines the similarity between two data objects based on their local correlation dimensionality and subspace orientation. It takes a hierarchical density-based approach to obtain correlation clusters. 
CASH (Clustering in Arbitrary Subspaces based on the Hough transform) \cite{Achtert2008} is based on the Hough transform \cite{Hough1962}, which maps the data space into parameter space. It then uses a grid-based approach to find dense regions in the parameter space and corresponding data subsets in the original data space. It recursively applies itself on such corresponding data subsets.

\subsection{Other Clustering Techniques} \label{subsecOtherClustering}
\subsubsection{Neural Network-Based Clustering:}
The neural network approach has been studied intensively by mathematicians, statisticians, physicists, engineers, and computer scientists \cite{Kumar2007}.
A neural network is an interconnected group of artificial neurons and an adaptive system for information processing. Neural-network-based clustering is competitive-learning-based clustering, not statistical model-identification based clustering. For competitive-learning-based clustering, the first phase is learning where the algorithmic parameters are adjusted, and the second phase is generalization \cite{Du2010}. Competitive learning can be implemented using a two-layer neural network: the input layer and the output layer \cite{Du2010}.  

Examples are as follows. 
 A SOM (Self-Organizing Map) \cite{Kohonen1982} consists of nodes or neurons, each of which is associated with a weight vector and a position in the map space. It creates a mapping from a higher dimensional input space to a lower dimensional output space. SOM clustering computes the distance of the input pattern to each neuron and finds the winning neuron. 
 LVQ (Learning Vector Quantization) or VQ (Vector Quantization) \cite{Burton1983,Gersho1982} is a classical quantization technique for signal processing. It models the probability density functions by using the distribution of prototype vectors. 
It divides a set of vectors into groups that have approximately the same number of vectors closest to them.  
Basic VQ is k-means clustering, and LVQ is a precursor to self-organizing maps (SOM) \cite{Gersho1982}. 
 Neural gas \cite{Martinetz1991} is inspired by SOM. It is a simple algorithm and finds optimal data representations based on feature vectors. During the adaptation process, the feature vectors distribute themselves dynamically like a gas within the data space. 
 ART model is covered in Section~\ref{subSubSecIncrementalLearning}. 

\subsubsection{Evolutionary Clustering:}
Evolutionary computation has many applications in computer science, bioinformatics, pharmacometrics, engineering, physics, and economics.
Evolutionary computation is inspired by the biological mechanisms of evolution, and uses iterative processes such as growth or development followed by selection in a population of candidate solutions. 
Clustering methods that use local search techniques including hill-climbing approach-based k-means suffer from local minima problems. The recent advancements in evolutionary computational technologies \cite{Fogel2006} provide an alternate and effective way to find the global or approximately global optimum \cite{Xu2010}. 
PSO (Particle Swarm Optimization) simulates social behavior in nature, such as bird flocking or fish schooling \cite{Kennedy2001}.
ACO (Ant Colony Optimization) algorithms model the behaviors of ants in nature \cite{Dorigo2003}.
GAs (Genetic Algorithms) \cite{Holland1975} mimic natural selection and use evolutional mechanisms such as crossover, mutation and selection to generate solutions. 

Examples are as follows. 
 PPO (Particle-Pair Optimizer) \cite{Du2008} is a modification of the Particle Swarm Optimizer. It uses two particle pairs to search for the global optima in parallel and uses k-means for efficient clustering. 
 Niching genetic k-means \cite{Sheng2004} modifies Deterministic Crowding \cite{Mahfoud1995}, one of the niching genetic algorithms, and incorporates one step of k-means into its regeneration steps \cite{Sheng2004}.  
 EvoCluster algorithm \cite{Ma2006} encodes cluster structure in a chromosome, in which one gene represents one cluster or the objects belonging to one cluster. Reproduction operators are used between chromosomes.
 GenClust \cite{Gesu2005} is a simple algorithm and proceeds in stages. It uses genetic operators and a fitness function to compute partitions in a new stage based on partitions in the previous stage.

\subsubsection{Kernel Clustering:}
Kernel-based learning such as Support Vector Machines (SVMs) \cite{Cortes1995,Scholkopf1996,Scholkopf1999} has had successful applications in pattern recognition and machine learning and is becoming increasingly important \cite{Scholkopf1999}.
Kernel methods \cite{Cristianini2000} perform a nonliner mapping of the low dimensional input data into a high dimensional space, which becomes linearly separable. To improve efficiency, they avoid explicitly defining the nonlinear mapping by using kernel functions, such as polynomial kernels, sigmoid kernels, and Gaussian radial basis function (RBF) kernels. This is the known as the \textit{kernel trick}. 

Examples are as follows.
 SVC (Support Vector Clustering) \cite{Wang2007,Zafeiriou2008} uses SVM training to find the cluster boundaries and an adjacency matrix to assign a cluster label to each data object \cite{Xu2010}. Variations of SVC include Iterative One-Class SVC \cite{Camastra2005}, and rough Set SVC \cite{Pawlak1991}. 
 Kernel k-means \cite{Girolami2002} uses a kernel method to calculate the distance between items in a data set, instead of using the Euclidean distance as in regular k-means. Variations include Incremental Kernel-k-means \cite{Scholkopf1998}. 
 Kernel deterministic annealing clustering \cite{Yang2006} uses an adaptively selected Gaussian parameter and a Gaussian kernel to determine the nonlinear mapping. 
 Kernel fuzzy clustering \cite{Liu2008,Zhang2004,Zhou2004} applies kernel techniques to fuzzy clustering algorithms by replacing the original Euclidean distance with a kernel-induced distance.
 Kernel Self-Organizing Maps \cite{Andras2002,Boulet2008,Lau2006} perform self-organizing between an input data object and the corresponding prototype in the mapped high dimensional feature space or in the mapped space completely.  

\subsubsection{Sequential Data Clustering:} 
Sequential data are sequences of numerical data or non-numerical symbols and can be generated from speech processing, video analysis, text mining, gene sequencing, and medical diagnosis. Time series data or temporal data are a type of sequential data, which, unlike static data, contain feature values that change over time. 
Since sequential data usually have variable length, dynamic behaviors, and time constraints \cite{Gusfield1997,Sun2001}, they cannot be represented as points in the multi-dimensional feature space and thus cannot be analyzed using any of the clustering techniques we have mentioned thus far \cite{Xu2010}.   
Clustering techniques targeting sequential data have been developed, and they commonly use three strategies: proximity-based approaches, feature-based approaches, and model-based approaches.  

%Commonly, there are three strategies for sequential data clustering: 
Proximity-based approaches use proximity information such as the distance or similarity between pairs of sequences. They then use hierarchical or partitional clustering algorithms to group the sequences into clusters \cite{Xu2010}. 
Examples are as follows. 
 The Needleman-Wunsch algorithm \cite{Durbin1998,Needleman1970} uses basic dynamic programming and is a global optimal alignment algorithm. 
 The Smith-Waterman algorithm \cite{Durbin1998,Smith1980} is based on Needleman-Wunsch algorithm, and also uses dynamic programming. It compares multi-lengthed sequence segments using character-to-character pair-wise comparisons. 
 FASTA (FAST-All) \cite{Pearson1988} 
first finds segments of the two sequences that have some degree of similarity and marks these potential matches. It then performs a more time-consuming optimized search approach such as the Smith-Waterman algorithm.
 BLAST (Basic Local Alignment Search Tool) \cite{Altschul1990} searches for short alignment matches between two sequences using a heuristic approach, which approximates the Smith-Waterman algorithm.  
 GeneRage \cite{Enright2000} automatically clusters sequence datasets by using Smith-Waterman dynamic programming alignment and single-linkage clustering. 
 SEQOPTICS (SEQuence clustering with OPTICS) \cite{Chen2006} implements Smith-Waterman algorithms as the distance measurement and uses OPTICS \cite{Ankerst1999} to perform sequence clustering.  

Feature-based approaches map sequences onto multi-dimensional data points using feature extraction methods and then use vector-based clustering algorithms on the data points \cite{Xu2010}.
Examples are as follows. 
 Scalable sequential data clustering \cite{Guralnik2001} uses a k-means based clustering algorithm which has near-linear time complexity to improve the scalability problem.  
 Pattern-oriented hierarchical clustering \cite{Morzy1999} uses a hierarchical algorithm, which can generate the clusters as well as the clustering models based on sequential patterns found in the database.
 The wavelet-based anytime algorithm \cite{Vlachos2003} combines a novel k-means based clustering algorithm and the multi-resolution property of wavelets. It repeatedly uses coarse clustering to obtain a clustering at a slightly finer level of approximation.  

Model-based approaches assume sequences that belong to one cluster are generated from one probabilistic model \cite{Xu2010}. 
Examples are as follows.  
 Autoregressive moving average (ARMA) models \cite{Bagnall2004,Xiong2004} derive an EM algorithm to learn the mixing coefficients and the parameters of the component ARMA models. They use the Bayesian information criterion (BIC) to determine the number of clusters.   
 The Markov chain approach \cite{Ramoni2002,Smyth1999} models dynamics as Markov chains and then applies an agglomerative clustering procedure to discover a set of clusters that best capture different dynamics. 
 The Polynomial models approach \cite{Bagnall2003,Gaffney1999} assumes the underlying model is a mixture of polynomial functions. It uses an EM algorithm to estimate the cluster membership probabilities, using weighted least squares to fit the models.  
 The Hidden Markov Model (HMM) \cite{Oates2001,Smyth1996} is a probabilistic model-based approach. It uses HMMs, which have shown capabilities in modeling the structure of the generative processes underlying real-world time series data. 

\subsubsection{Ensemble Clustering:}
Clustering ensembles have emerged to improve robustness, stability and accuracy of clustering results \cite{Ghaemi2009}. A cluster ensemble combines the results of multiple clustering algorithms to obtain a consensus result \cite{Pirim2011}. It can produce better average performance and avoid worst case results. Other usages of clustering ensembles include improving scalability by performing clustering on subsets of data in parallel and then combining the results, and data integration when data is distributed across multiple sources \cite{Jain2007}.   

There are two main steps in a clustering ensemble: generation and consensus.
In the generation step, several approaches are used \cite{Vega-Pons2011}: 
different clustering algorithms, 
a single algorithm with different parameter initializations, 
different object representations, 
different object projections, 
and different subsets of objects.

In the consensus step, several approaches are used: 
relabeling and voting, 
Mutual Information (MI), 
co-association based functions, 
finite mixture models,  
a graph/hypergraph partitioning approach,  
and others. 

%Relabeling and voting approach
The relabeling and voting approach is also called the direct approach. It finds the correspondence of the cluster labels among different clustering results and then uses a voting method to determine the final cluster label for a data object.
Examples are as follows. 
 BagClust1 \cite{Dudoit2003} applies a clustering procedure to each bootstrap sample and obtains the final partition by plurality voting so that the majority cluster label for each data object determines the final cluster membership.  
 BagClust2 \cite{Dudoit2003} introduces a new dissimilarity matrix which contains the proportion of time each pair of data objects were clustered together in the bootstrap clusters. It then performs clustering on the dissimilarity matrix to obtain the final partition.

%Mutual Information
The MI approach uses MI to measure and quantify the statistical information shared between a pair of clusterings. It can automatically select the best clustering method from several algorithms. 
Examples are as follows. 
 A Genetic Algorithm (GA) clustering ensemble \cite{Azimi2007} uses a GA to obtain the best partition and the co-association function as the consensus function. It determines fitness function parameters based on co-association function values. 
 The information theory based GA clustering ensemble \cite{Luo2006} uses a GA to find a combined clustering by minimizing an information-theoretical criterion function. 
 The generalized MI clustering ensemble \cite{Topchy2003} introduces a new consensus function using a generalized mutual information definition. The consensus function is related to the classical intraclass variance criterion. 

%Co-association based functions
The co-association based functions approach is also called the pair-wise approach. It uses a co-association matrix in the consensus step. 
Examples are as follows. 
 Clusterfusion \cite{Kellam2001} first generates an agreement matrix with each cell containing the number of agreements amongst clustering methods and then uses the matrix to cluster data objects. 
 Voting-k-Means \cite{Fred2001} transforms data partitions into a co-association matrix with coherent association mappings. It then extracts underlying clusters from this matrix.
 Evidence accumulation-based clustering \cite{Fred2002} maps data partitions created by each individual clustering into a new similarity matrix, based on voting. It then uses the single link algorithm to extract clusters from this matrix. 

%Finite Mixture Model
Finite mixture model approach assumes that the probability of assigning a label to a data object is based on a finite mixture model or that the labels are `modeled as random variables drawn from a probability distribution described as a mixture of multivariate component densities' \cite{Vega-Pons2011}. It obtains the consensus clustering result by solving a maximum likelihood estimation problem. 
 Mixture model clustering ensemble \cite{Topchy2004} uses a probabilistic model of consensus based on a finite mixture of multinomial distributions in a space of clusterings. It finds a combined partition by solving the corresponding maximum likelihood problem with the EM algorithm.

The graph/hypergraph partitioning approach considers the combination problem as a graph or hypergraph partitioning problem. Methods taking this approach differ in how they build a (hyper)graph from the clusterings, as well as how they define the cuts on the graph to obtain the consensus partition \cite{Vega-Pons2011}. 
Examples are as follows. 
 METIS \cite{Karypis1998} is a multi-level graph partitioning system. It collapses vertices and edges of the graph, partitions the resulting coarsened graph, and then refines the partitions.
 SPEC (spectral graph partitioning algorithm) \cite{Ng2001} tries to optimize the normalized cut criterion. It treats the rows of the largest eigenvalues matrix as multiple dimensional embeddings of the vertices of the graph and then uses k-means to cluster the embedded points.  
 CSPA (Cluster based Similarity Partitioning Algorithm) \cite{Strehl2002} first creates a graph based on a co-association matrix, and then performs METIS clustering on the graph. 
 HGPA (Hypergraph Partitioning Algorithm) \cite{Strehl2002} uses a hyperedge in a graph to represent each cluster. It then uses minimal cut algorithms such as HMETIS \cite{Karypis1999-2} to find good hypergraph partitions. 
 MCLA (Meta Clustering Algorithm) \cite{Strehl2002} determines soft cluster membership values for each data object by using hyperedge collapsing operations. 
 HBGF (Hybrid Bipartite Graph Formulation) \cite{Fern2003} constructs a bipartite graph where data objects and clusters are both modeled as vertices. It later partitions the bipartite graph with an appropriate graph partitioning method.    

Other approaches are as follows. 
 The cumulative voting consensus method \cite{Ayad2008} solves the cluster label alignment problem by using cumulative voting, where a probabilistic mapping between labels is computed. 
 Bipartite Merger and Metis merger \cite{Hore2009} are approaches for merging an ensemble of clustering solutions using sets of cluster centers. They are highly scalable and provide competitive results.  
 Weighted consensus clustering \cite{Li2008} weights each input clustering. It determines weights in a way so that the clusters are better separated.
 Bayesian Cluster Ensembles \cite{Wang2011} takes a Bayesian approach to combine clusterings. It uses a variational approximation based algorithm for learning. This way, it is able to avoid the cluster label correspondence problems. 

Figure ~\ref{fig:EnsembleClustering} shows an example of ensemble clustering.

\begin{figure}[t]
	\centering
		\includegraphics[width=0.8\textwidth]{images/EnsembleClustering.png}
	\caption{Ensemble Clustering \cite{Iam-On2012}}
	\label{fig:EnsembleClustering}
\end{figure}

\subsubsection{Multi-objective Clustering:}
Conventional clustering algorithms use a single clustering objective function only, which may not be appropriate for the diversities of the underlying data structures. Multi-objective clustering uses multiple clustering objective functions simultaneously. 
Such methods consider clustering as a multi-objective optimization problem \cite{Ferligoj1992}. 

Examples are as follows.
 FCPSO (Fuzzy Clustering-based Particle Swarm Optimization) \cite{Agrawal2008} uses an external repository to save nondominated particles during the search process and a fuzzy clustering technique to manage the size of the repository. 
It also uses a fuzzy-based iterative feedback mechanism to determine the compromised solution among conflicting objectives.
 Evolutionary Multiobjective Clustering \cite{Handl2004} and MOCK (MultiObjective Clustering with automatic k-determination) \cite{Handl2007} use an evolutionary approach to solve the multi-objective problem in clustering. They are based on a multi-objective evolutionary algorithm named PESA-II (Pareto Envelope-based Selection Algorithm version 2) \cite{Corne2001} to optimize two complementary clustering objectives.
 Multi-objective real coded genetic fuzzy clustering \cite{Mukhopadhyay2011} aims to optimize multiple validity measures simultaneously. It encodes the cluster centers in its chromosomes while optimizing the fuzzy compactness within a cluster and fuzzy separation among clusters. 
 EMO-CC (Evolutionary MultiObjective Conceptual Clustering) \cite{Romero-Zaliz2008} combines evolutionary algorithms with multi-objective optimization techniques and relies on the NSGA-II multi-objective genetic algorithm \cite{Deb2002}. It can discover less obvious but informative data associations.

\subsubsection{Semi-supervised Clustering:}
Semi-supervised clustering provides limited supervision to unsupervised clustering. There are many cases when some knowledge about the data is available such as the constraints between data objects or cluster labels for some data objects. Such knowledge can be used to guide the clustering process.  
There are several approaches for semi-supervised clustering: similarity-adapting methods, search-based methods, and other methods.

%Similarity-adapting methods
Similarity-adapting methods use a similarity measure which is adapted to make the available constraints more easily satisfied \cite{Grira2005}. 
Examples are as follows. 
 Distance metric learning based clustering \cite{Xing2003} learns a distance metric based on examples of similar pairs of data objects in the input space using convex optimization.
 Space-level constraints based clustering \cite{Klein2002} exploits space-level implications based on instance-level constraints. It uses an all-pairs-shortest-paths algorithm to adjust the distance metric.

%Search-based methods,
Search-based methods modify the clustering algorithm itself to use the available constraints or labels to guide the search for an appropriate clustering \cite{Grira2005}. 
Examples are as follows.
 Seeded-K Means and Constrained-K Means \cite{Basu2002} generate initial seed clusters based on labeled data. The latter also generates constraints from labeled data and guides the clustering process using those constraints.     
 Semi-Supervised Clustering Using Genetic Algorithms \cite{Demiriz1999} modifies k-means clustering to minimize within-cluster variance and a measure of cluster impurity. 
 Clustering with Instance-level Constraints \cite{Wagstaff2000} incorporates hard constraints using a modified version of Cobweb (covered in Section~\ref{subSubSecIncrementalLearning}) which partitions the data.

Other methods include 
the probabilistic semi-supervised clustering with constraints method \cite{Basu2006}, which derives an objective function from the joint probability defined over the Hidden Markov Random Field model and performs semi-supervised clustering by minimizing this object function. 


\section{Applications of Clustering in Cancer Subtyping}\label{secClusteringSubtyping} 

%microarray tech. & cancer subtyping
The recently-developed DNA microarray technologies \cite{Eisen1999,Lipshutz1999}, which can measure the expression levels of tens of thousands of genes simultaneously, offer cancer researchers a novel method to investigate the pathology of cancers from a molecular angle. Under such a systematic framework, cancer types or subtypes can be identified through the corresponding gene expression profiles. Research on gene expression profile-based cancer type recognition has already attracted numerous efforts from a wide variety of research communities \cite{McLachlan2005,Xu2005}. Investigations on leukemia \cite{Golub1999}, lymphoma \cite{Alizadeh2000}, colon cancer \cite{Alon1999}, cutaneous melanoma \cite{Bittner2000}, bladder cancer \cite{Dyrskjot2003}, breast cancer \cite{Perou2000}, lung cancer \cite{Garber2001}, and others show very promising results. Supervised computational methods, such as multi-layer perceptrons \cite{Khan2001}, naive Bayes \cite{Li2004}, support vector machines \cite{Li2004-2,Statnikov2005}, semi-supervised Ellipsoid ARTMAP \cite{Xu2007}, and k-Top Scoring Paris \cite{Tan15102005}, have already been used in cancer diagnosis-oriented gene expression data analysis.
%latest: copy/paste and need to rewrite; 'pathologiof cancers'

%clustering for cancer subtyping 
In this section, we consider the situation in which we do not have labels for the cancer samples. This assumption is reasonable with the requirement for discovering unknown and novel cancer types or subtypes. In this case unsupervised learning or cluster analysis \cite{Xu2005} is required in order to explore the underlying structure of the obtained data and provide cancer researchers with meaningful insights into the possible partitions of the samples.

%microarray dataset types (Affymetrix vs. cDNA and mRNA vs. miRNA)
Microarray data sets are generally generated from two types of platforms, single-channel microarrays (\textit{e.g.} Affymetrix) or double-channel microarrays (\textit{e.g.} cDNA) \cite{Quackenbush2001,Monti2003,Slonim2002}.
Measurements of Affymetrix arrays are based on the number of RNA copies found in the cell sample, and measurements of cDNA microarrays are based on the ratios of the number of copies in relation to a control cell sample \cite{Souto2008}.
Microarray data include mRNA gene expression data and miRNA gene expression data.

Subtyping by microarrays is challenging due to the following reasons: 
a) There are a large number of genes, but a relatively small number of samples.   
One of the major challenges of microarray data analysis is the overwhelming number of measures of gene expression levels compared with the small number of samples, which is caused by factors such as sample collection and experiment cost. 
The number of genes are usually in the thousands range, while the sample sizes are usually in the tens range.
This problem is well known as the `curse of dimensionality' in machine learning, which refers to the lack of data separation in high dimensional data space. When the dimensions are high, the distance from a data object to the nearest neighbor data object becomes indistinguishable compared with the majority of data objects \cite{Berkhin2002,Beyer1999}. This effect becomes much worse when dimensions are greater than 15, and proximity based clustering becomes unreliable \cite{Berkhin2002}.
b) It is important to identify the most relevant genes. 
%Noise challenges:
There are multiple steps to obtain microarray data, due to several system or design issues, and each step may introduce noise. Noise can obscure or mislead the underlying biological meanings, which is an important reason why statistical tools are used to analyze microarray data, since they can take the noise or variations into account. The noise can come from five phases of data acquisition: microarray manufacturing, preparation of mRNA from biological samples, hybridization, scanning, and imaging \cite{Parmigiani2003}. And they can be classified into three major categories: biological - cells from different populations, tissues, conditions, etc. experimental - defects of the spotting equipment, different hybridization conditions and dyes, different methods to make the arrays, to culture the cells, to extract mRNA, etc. processing - errors related to numerical values collection such as fluorescence scanning, image analysis, and intensity readout \cite{Zhou2003}.

%mRNA profiling vs miRNA profiling
mRNA profiling has demonstrated its effectiveness at subtyping various cancers. miRNA (short for MicroRNAs) profiling can be more accurate. Researchers have found links between misregulated miRNAs and the genes that are affected in various cancer subtypes \cite{ODay2010}. miRNAs are small non-protein coding RNAs found in animals and plants. The first miRNAs were discovered and characterized in the early 1990s \cite{Lee1993}. Since the early 2000s, miRNAs have been found to play multiple roles in negative regulation in cells. The first cancer found to be associated with miRNA deregulation and deletion was chronic lymphocytic leukemia \cite{Calin2002}. Later on many miRNAs have been found to be related to more types of cancer \cite{Bottoni2005,Chan2005,Ciafre2005,Iorio2005,Johnson2005,Karube2005,Metzler2004,Michael2003,Yanaihara2006}.
Since multiple subtypes of a disease may have similar patterns within a single data type (\textit{i.e.}, mRNA or miRNA), both data types can be used together to improve the accuracy of subtyping.  

\subsection{Clinical Applications}

\subsubsection{mRNA-based Applications}

%researcher, #genes, #samples, clustering method, #subtypes, their names and clinical significance, meanfullness of the discovery etc.

Golub used mRNA profiling of the expression of 6,817 genes in 72 leukemia samples as a test case for subtyping \cite{Golub1999}. Using self-organizing maps (SOMs), leukemia samples were successfully grouped into the known subtypes of acute myelogenous leukemia (AML) and acute lymphocytic leukemia (ALL) without previous knowledge of these subtypes. The results showed the feasibility of using gene expression alone to classify cancer and suggested a general approach of classification for other types of cancer without using previous biological knowledge. 

Alizadeh used mRNA profiling to study 128 microarray analyses that contain 1.8 million measurements of gene expression from 96 samples of normal and malignant lymphocytes \cite{Alizadeh2000}.
Using the hierarchical clustering approach, two subtypes of diffuse large B-cell lymphoma (DLBCL) were identified: germinal center B-like DLBCL, which is diverse in gene expression patterns, and activated B-like DLBCL, which is distinct at the molecular level. 
Patients with germinal centre B-like DLBCL had a significantly better response to current therapy and overall survival than those with activated B-like DLBCL, which reflects tumor proliferation rate, different state of the tumor, and different host/patient response.   

Armstrong applied clustering technique of PCA on mRNA profiling of 8700 genes from 72 leukemia samples and discovered mixed-lineage leukemia (MLL), a leukemia subtype that is distinct from both AML and conventional ALL \cite{Armstrong2002}. MLL is characterized by the mixed-lineage leukemia gene's chromosomal translocation,
and such patients have a decidedly poor prognosis and often have early relapse after chemotherapy. The discovery of MLL as a distinct subtype is important to therapeutic success as well, since molecular markers differentially expressed by MLL compared with both ALL and AML immediately suggest new and different molecularly targeted treatment strategies for this treatment-resistant cancer subtype.  
      
Bittner studied mRNA profiling of 6971 genes from 31 patients with malignant melanoma, for which there were no accepted histopathological, molecular, or immunohistochemical-marker defined subtypes \cite{Bittner2000}. Hierarchical clustering (agglomerative, average linkage) with Pearson correlation coefficients discovered two potential subtypes. With in vitro assay experiments, the subtypes were associated with different disease tissue invasion potential \cite{Maniotis1999}. However, the patients in this study had uniformly poor prognosis, and future work is needed to analyze the clinical relevance of observed subtypes.    

Perou analyzed mRNA profiles of 8102 genes of 65 breast tumor specimens using a hierarchical clustering approach \cite{Perou2000}. Three subtypes were discovered in this clinically highly heterogeneous tumor: the previously known Erb-B2, and two others previously unknown, namely ER+(estrogen receptor�positive)/luminal-like and basal-like. Due to the limited number of tumor specimens in this study, statistically significant relationships between the discovered subtypes and clinical data are still to be uncovered.

Lapointe profiled mRNA gene expression of 26,260 genes in 62 primary prostate tumors and 9 lymph node metastases and identified three robust subtypes of prostate tumors using a two-way hierarchical clustering technique on 5153 genes based on distinct gene expression patterns \cite{Lapointe2004}. Subtype I is the clinically least aggressive subgroup, subtype II is the second clinically aggressive subgroup, and subtype III is the most clinically aggressive subgroup, including most of the metastasis cases in this study. These tumor subtypes may provide a basis for improved prognostication and treatment decision. 

Liang performed agglomerative hierarchical clustering on mRNA profiles of 1800 genes from 32 samples including Glioblastoma multiforme (GBM) and normal brain \cite{Liang2005}. Two molecularly distinct subtypes of GBM were identified, and their expression showed an obvious difference in a group of genes correlated with survival.  
Such finding may improve the accuracy of prognostic predictions and facilitate the development of optimized therapies for each subtype.

Laiho showed that mRNA profiling of 7928 genes from 37 colorectal carcinoma (CRC) samples separated serrated CRCs and conventional CRCs using hierarchical clustering \cite{Laiho2007}. This study was able to provide firm molecular evidence for a previously underrecognized route leading to CRC, which is a serrated neoplasia pathway. Much clinical and pathological evidence suggested that serrated CRCs may be more aggressive than conventional CRCs. Establishing serrated CRCs as a biologically distinct CRC subtype represents further discovering of the molecular subtypes of CRCs. In the long term, understanding the molecular basis of serrated CRCs may contribute to the development of treatment options specifically for this tumor subtype. 

Wilkerson detected four lung squamous cell carcinoma (SCC) subtypes from mRNA expression data totaling 2307 genes from 382 SCC patients using Consensus Clustering in the ConsensusClusterPlus software package by Bioconductor \cite{Monti2003,Wilkerson2010,Wilkerson2010-2}. The four lung SCC subtypes are: primitive, classical, secretory, and basal. These subtypes were associated with tumor differentiation as well as patient gender. The primitive subtype had the shortest survival and can be used as an independent predictor for survival outcome. The expression profiles of the four subtypes showed different biological processes which may suggest different pharmacologic interventions.

Lei identified 3 major subtypes among mRNA expression data of 35 genes from 248 gastric tumors using a robust method of unsupervised clustering, consensus hierarchical clustering with iterative feature selection \cite{Lei2013}. The 3 subtypes of gastric adenocarcinoma are: proliferative, metabolic, and mesenchymal. These subtypes have differences in molecular and genetic features, and respond differently to therapy. Thus, such subtyping may be helpful in selecting specific and appropriate treatment approaches for patients.  

\subsubsection{microRNA-based Applications} 

Lu performed computational analyses on 217 miRNAs from 334 mammalian samples, including multiple human cancers \cite{Lu2005}. Hierarchical clustering with average linkage and Pearson correlation was performed. Over miRNA profiles of 73 ALL samples, three groups were separated: BCR/ABL-positive samples and TEL/AML1 samples; T-cell ALL samples; and MLL samples. Subtyping results based on miRNA profiles on ALL samples and other tumor samples showed higher accuracy when compared with mRNA profiles. 
These discoveries demonstrate that using miRNA profiling for cancer diagnosis is very promising. 

Blenkiron reported the clustering analysis of miRNA expression in primary human breast tumors \cite{Blenkiron2007}. Hierarchical clustering with average linkage and Pearson correlation were used: ER- and ER+ tumors were recovered in over 137 miRNAs in 93 primary tumors samples; basal-like, HER2+, luminal A, luminal B or normal-like were recovered in over 38 miRNAs in 51 tumor samples; luminal A or luminal B tumors were recovered in over 9 miRNAs in 24 tumor samples. 
This study is among the first integrated analysis using miRNA expression, mRNA expression and genomic changes in human breast cancer. Furthermore, it demonstrates that miRNA expression profiling has the potential to effectively classify breast cancer into prognostic molecular subtypes. 

Mattie analyzed miRNA profiling of 20 different breast cancer samples in three common subtypes: ErbB2+/
ER-, ErbB2+/ER+, and ErbB2-/ER+ \cite{Mattie2006}. Hierarchical clustering identified these clinically relevant subtypes based on their miRNA expression patterns. The ErbB2+/ER+ subtype is a clinically troublesome subtype and appears to be more resistant to all kinds of endocrine therapy \cite{DeLaurentiis2005}.
Successfully identifying the ErbB2+/ER+ subtype based on miRNA profiling is of substantial interest since mRNA profiling studies had not previously been able to identify it.  

Porkka studied the expression of 319 human miRNAs in samples from prostate cancer cell lines, prostate cancer xenografts and clinical prostate tissues \cite{Porkka2007}. Hierarchical clustering with average linkage separated the 9 prostate carcinoma tissue samples into two groups that quite accurately correspond to clinical stage based subtypes: hormone-naive subtype and hormone-refractory subtype. Such results indicate that miRNAs profiling has the potential to become a novel diagnostic and prognostic tool for prostate cancer.

Oberg examined the expression of 735 miRNAs in 52 normal and 263 colon tumor samples \cite{Oberg2011}. There were three clinical subtypes in the tumor samples: 41 adenomas, 158 pMMR carcinomas and 64 dMMR carcinomas. Hierarchical clustering with average linkage and Pearson's dissimilarity matrix demonstrated that normal colon tissue and the three tumor subtypes were all clearly separable. It is the first report to show global miRNA (instead of only a few selected miRNAs) expression differences can be used for colon tumor subtype diagnosis.

Yang analyzed 219 miRNA-associated genes from 459 ovarian carcinoma (OvCa) samples \cite{Yang2013}. Consensus k-means clustering identified two clusters. One of the two clusters contained 172 OvCa cases and formed a tight cluster with higher expression values of the miRNA-associated genes. The majority of patients in this cluster had advanced stage OvCa and significantly shorter overall survival durations than patients the other cluster. 


\subsection{Computational Experiments}

\subsubsection{mRNA-based Experiments}
Xing and Karp presented CLIFF (CLustering via Iterative Feature Filtering) \cite{Xing2001} and tested it with mRNA profiles of 72 leukemia samples and 7130 genes \cite{Golub1999}. CLIFF is based on the `normalized cut' concept and iterates between sample partitioning and feature filtering until converging into an appropriate partition of the leukemia samples and a set of informative genes.
The result produced by CLIFF had high agreement to the original expert labeling of the leukemia data set. Its final partition had two clusters. One of the clusters contains 44 ALL samples, and the other cluster contains 25 AML samples and 3 ALL samples.

Tang and Zhang proposed IPD (Iterative Pattern-Discovery) based on iterative sample clustering and irrelevant gene pruning \cite{Tang2002}, and tested it on mRNA profiles of over 7129 genes in 72 leukemia patient samples \cite{Golub1999}. During the initial partition phase, conventional clustering methods k-means or SOM was used to group samples and genes into exclusive smaller groups. 
Based on Rand Index values, the clustering results obtained by IPD approaches are consistently better than the results obtained by applying k-means or SOM directly. 

Getz {\it et al.} proposed CTWC \cite{Getz2000} (covered in Section~\ref{subsubsecBiClustering}) and applied it to a leukemia mRNA data set \cite{Golub1999} and a colon cancer mRNA data set \cite{Alon1999}. 
The leukemia data set contains 72 samples; 47 samples are ALL, and the other 25 samples are AML. The original set contained 6,817 genes. 1,753 genes were selected for the CTWC experiment. In two iterations, 49 stable gene clusters and 35 stable sample clusters were obtained. One of the gene clusters contained 60 genes, and when used as the feature set CTWC was able to separate the samples into AML/ALL clusters. 
The colon cancer data set contained 40 tumor samples and 22 normal samples. The original set contained 6,500 genes. 2,000 genes were chosen for CTWC experiment. In two iterations, 97 stable gene clusters and 76 stable sample clusters were obtained by CTWC. Four of the gene clusters can partition the samples into normal/tumor clusters.   

Cheng and Church proposed an efficient biclustering algorithm \cite{Cheng2000} and applied it to diffuse large B-cell lymphoma mRNA profiles containing 4026 genes and 96 conditions \cite{Alizadeh2000}. The algorithm is based on multiple row/column addition/deletions and successively extracts biclusters from the raw data matrix until a pre-specified number of clusters has been reached.
In comparison with the results from hierarchical clustering used by Alizadeh et al., the first 100 biclusters discovered by Cheng's biclustering had only 10 conditions/genes exclusively from one or the other primary cluster from hierarchical clustering.    

Iam-on {\it et al.} presented LCE (Link-based Cluster Ensemble) \cite{Iam-on2010} and applied it to several mRNA profile data sets including: leukemia1 \cite{Golub1999} (1,877 genes and 72 samples), leukemia2 \cite{Golub1999} (1,877 genes and 72 samples), leukemia3 \cite{Armstrong2002} (2,194 genes and 72 samples), brain tumor \cite{Nutt2003} (1,377 genes and 50 samples), central nervous system (CNS) \cite{Pomeroy2002} (1,379 genes and 42 samples), and hepatocellular carcinoma (HCC) \cite{Chen2002} (85 genes and 180 samples). LCE incorporates relations within an ensemble and associations among clusters to improve clustering results. 
Based on average validity measure over three validity indices (Classification Accuracy (CA), Normalized Mutual Information, and Adjusted Rand Index) on the clustering results, LCE regularly performs better than other clustering methods including MULTI-K \cite{Kim2009}, consensus clustering with hierarchical clustering \cite{Monti2003}, graph-based consensus clustering \cite{Yu2007}, Cluster based Similarity Partitioning Algorithm \cite{Strehl2002}, Hyper-Graph Partitioning Algorithm \cite{Strehl2002}, Meta-Clustering Algorithm \cite{Strehl2002}, Hybrid Bipartite Graph Formulation \cite{Fern2004}, k-means, single-linkage, complete-linkage, and average-linkage. 
Based on the CA validity index, LCE achieved over 74\% accuracy on leukemia1, over 70\% accuracy on leukemia2, over 83\% accuracy on leukemia3, over 61\% accuracy on brain tumor, over 63\% accuracy on CNS, and over 84\% accuracy on HCC. 

\subsubsection{microRNA-based Experiments}

Lock and Dunson proposed Bayesian Consensus Clustering (BCC) \cite{Lock2013} and tested it with miRNA profiles of 348 breast cancer samples and 423 miRNAs \cite{CGAN2012}. This approach is a flexible and computationally scalable Bayesian framework, which estimates the consensus clustering and the base clusterings at the same time. 
BCC clustering results vs.\ TCGA identified comprehensive subtypes matching matrix show that the two partitions have a significant but weak association. 

Li {\it et al.} proposed a subtyping method using the CTWC algorithm and Super-Paramagnetic Clustering (SPC) \cite{Li2014} and tested it with the miRNA profiles of 71 breast cancer patients and 13 miRNAs \cite{Blenkiron2007}. This method iteratively partitioned the sample and feature space using the two-way super-paramagnetic clustering technique and identifies the final optimal miRNA clusters. 
Using a subset of the miRNAs as the feature set, the five subtypes previously classified by mRNA expression profiling \cite{Blenkiron2007} were identified successfully by CTWC. The clinical significance of the identified subtypes were verified using Kaplan-Meier survival analysis \cite{Kopycka2004}.


\section{Challenges}\label{secChallenges}

Advances in microarray technology and decreasing costs are making gene expression data increasingly available and affordable. Research has shown that classifying cancers using gene expression can discover previously undetected and clinically significant subtypes of cancer \cite{Veer2008}.
However, there are still many challenges. 

%Challenges facing oncologists/pathologists/biologists
\subsection{Clinical Challenges}
{\bf Complexities in cancers and cancer subtypes} Cancers and cancer subtypes are complicated diseases. Especially for most solid tumors, many different cell types are involved in a tumor, and tumor cells themselves are morphologically and genetically diverse \cite{Perou1999}. These features may make the conventional clustering approaches problematic or inadequate, so novel clustering approaches are needed to address such complexities. 

{\bf Experimental issues} Gene expression studies require careful experimental design to avoid experimental errors. This is especially important for studying solid tumors. For example, biopsy specimens might have different proportions of surrounding stromal cells, which may cause clustering results reflecting the stromal contamination, rather than the underlying tumor. So, additional techniques are needed to improve such problems. Microscopic examination of tumor samples to make sure that the tumor cells are comparable and purified is helpful, as well as computational analysis methods that can exclude surrounding stromal cells. 

%Challenges facing computational researchers
\subsection{Computational Challenges}

{\bf Curse of Dimensionality} Gene expression data sets generally contain small numbers of samples (in tens) and large numbers of genes (in hundreds or thousands). Most conventional clustering techniques need a large number of samples and a small number of variables to achieve robust performance. 
Approaches are needed to improve the clustering results on such sparse data sets. %todo: such as

{\bf Noise} There are multiple sources of noise introduced in microarray experiments, including varying cellular composition among tumors, genetic heterogeneity within tumors due to selection and genomic instability, differences in sample preparation, nonspecific cross-hybridization of probes, and differences between individual microarrays. In general, biologic variation is the major source of variation in gene expression experiments. The noise may obscure clustering results, especially in those approaches based on distance functions. Techniques are needed to improve clustering approaches so that they are more robust to noise. 

%#clusters
%Estimating the 
{\bf Number of subtypes} For subtyping in clinical studies, the number of subtypes are unknown or uncertain. However, in many clustering algorithms this number needs to be specified by the user, so techniques are needed to estimate or infer the number from the data. 

{\bf Clinical or biologic meanings} Gene expression data sets are complex and may contain hundreds or thousands genes. In a complex data set, many different relationships and patterns are possible \cite{Ramaswamy2002}. The patterns discovered by clustering may not necessarily be clinically or biologically meaningful.  
Techniques are needed to uncover and identify clusters of clinical or biologic interest.  

{\bf Statistical significance} An important issue with any analytic approach is the statistical significance of observed correlations. A typical microarray experiment produces expression data for thousands of genes from a relatively small number of samples, thus gene-cluster correlations can be identified by chance alone \cite{Ramaswamy2002}. 
Techniques are needed to determine the statistical significance, such as permutation testing.

{\bf Knowledge integration} Knowledge is obtained from multiple test techniques: some from conventional tests and some from molecular diagnostic tests. However a single recommendation is needed for the oncologist to treat the patient. Approaches are needed to integrate these knowledge items to produce an improved single recommendation. %todo: such as    
{\bf Algorithm selection} There are a large number of clustering algorithms available that may be used for clustering gene expression data, however there is no single best algorithm that performs best in all aspects. Selecting the most appropriate algorithm for a given gene expression data set and a given analysis goal is critical in success application. Without automatic selection of the most appropriate algorithm, researchers usually select a few promising clustering algorithms and compare their results.  
Approaches are needed to improve algorithm selection. 

{\bf Other challenges} 
Besides the above challenges, researchers are also facing the following challenges: 
time variation during specimen preparation, %??? need to verify
integration of data sets created by different laboratories using different technologies,
overlapping clusters, 
presence of irrelevant attributes, 
and lack of prior knowledge.

\section{Conclusions and Future Perspectives}\label{secConclusion} 

\subsection{Conclusions}

In this paper we reviewed classical and state of the art clustering algorithms in the communities of computer science, machine learning, statistics, etc. We also reviewed historic and state of the art cancer subtyping techniques. Clustering algorithms that have been applied to mRNA or miRNA expression data based cancer subtyping with promising results, and challenges associated with molecular cancer subtyping were presented as well.

However, given the many choices of available clustering algorithms, there is no single algorithm that performs best in every validation matrix \cite{Kuncheva2004-2}. The performance of a given clustering algorithm and a validation matrix is dependent on data characteristics and the application \cite{Jiang2004}. 

\subsection{Future Perspectives} 

{\bf Different granularities} Users often desire different cluster granularity for different subsets of data. For example, users may prefer small and tight clusters for some genes but need only coarse data structure for other genes. However, most existing clustering algorithms provide the same cluster granularity for all genes. 
It would be more helpful for them to provide a flexible representation of the data cluster structure and let the user to find the answer based on several different granularity requirements.  

{\bf Interactive semi-supervised feature} Prior to clustering, much information about the data set is unknown, but some knowledge is often available. For example, some experimental conditions are known to be correlated. If a clustering algorithm can provide the options to interactively integrate such partially available knowledge into the clustering process, it may produce more biologically meaningful results \cite{Pirim2012}.      

{\bf Handling high dimensional / low sample data} Although many clustering techniques have been used for gene expression data, most of these techniques perform well only on data with a large number of samples and a small number of dimensions. Cancer gene expression data sets generally contain a small number of samples with a large number of dimensions or genes, since many human cancer studies use costly or rare clinical specimens and are difficult to repeat.
Future advances will require improved clustering techniques better adapting to this type of data.

{\bf Easy to use software} In order to make routine clinical use of clustering tools a reality among medical and biological professionals, the software needs to be easy to use. For example, the software should be able to determine the number of clusters automatically based on the data properties; the software should avoid needing other user-specific parameters or should provide effective guidance to determine those parameters; the software should provide good visualization and domain-specific interpretation for the clustering results; the software should be able to extract useful and relevant information from the data to solve users' problems.    

{\bf Robustness} Noise can be introduced in every step of the microarray experiments due to the nature of microarray technology. It is not realistic to count on the data to be `pure and uncontaminated'. Noise and outliers can be present in the data during measurement, storage, and processing. The clustering algorithm should be able to better detect and remove noise and outliers, or not be affected by them.

{\bf Arbitrary cluster shapes} Many existing clustering algorithms form clusters with regular shapes, such as hyperspheres or hyper-rectangles. Gene expression data generally have complex underlying data structures and are not always regular cluster shapes. Cluster algorithms should be able to better detect arbitrary natural cluster shapes rather than confine the clusters to some particular shape. 

\bibliographystyle{ACM-Reference-Format-Journals}
\bibliography{yan-survey-2016}

\received{May 1111}{May 1111}{May 1111}

\end{document}

