# On the Role of Clustering and Visualization Techniques in Gene Microarray Data
## 2 Clustering for Microarray Gene Expression Data
### Partitive Clustering Algorithms  
In this form of clustering [28], the aim is to find a partition in a data set that groups the samples into \(K\) non-overlapping sets such that all samples belonging to the same set are as \"similar\" as possible, that is, given the set of \(N\) data points \(S=\{\mathbf{t}_{1},\mathbf{t}_{2},\ldots,\mathbf{t}_{N}\}\), with \(\mathbf{t}_{i}\in\mathbb{R}^{D}\), for \(i=1,2,\ldots,N\), the algorithm task is to find \(K\) clusters \(C=\{C_{1},C_{2},\ldots,C_{K}\}\) such that each data point \(\mathbf{t}_{i}\) is assigned to a cluster \(C_{k}\). An appropriate objective function, such as minimizing the distance between each point and the centroid \(\mathbf{v}_{i}\in\mathbb{R}^{D}\), of the cluster to which it is assigned, captures similarity. Very often, a sum of variance criterion of the following form  
\[J=\sum_{i=1}^{K}\sum_{j=1}^{N}u_{ij}^{m}\|\mathbf{t}_{j}-\mathbf{v}_{i}\|^{2}= \sum_{i=1}^{K}\sum_{j=1}^{N}u_{ij}^{m}d_{ij}^{2} \tag{1}\]  
is adopted, where \(d_{ij}\) is any distance measure, e.g., Euclidean distance. The partition matrix \(U=[u_{ij}]\) is used to store all results of clustering (partitioning) the points into clusters. The partition matrix meets the following requirements, depending on whether we are interested in set-oriented or fuzzy set-oriented partitioning:  
* for set-oriented clustering, \(u_{ij}\in\{0,1\}\), \(0<\sum_{j=1}^{N}u_{ij}<N\), for \(i=1,2,\ldots,K\), \(\sum_{i=1}^{K}u_{ij}=1\), for \(j=1,2,\ldots,N\),
* for fuzzy-oriented clustering, we get \(u_{ij}\in[0,1]\) with the same two requirements as stated above. The above requirements suppose an intuitive and simple interpretation:
* each cluster is nonempty;
* each point belongs exactly to one cluster (set-oriented clustering) or might belong to more than one cluster simultaneously, i.e., the sum of its membership values for all clusters is 1 (fuzzy set-oriented clustering).  
The optimization is carried out through an iterative process in which the objective is to calculate the prototypes (\(\mathbf{v}_{i}\)) and update the partition matrix (\(U\)) on the basis of the minimized objective function, \(J\), first-order conditions. The entire process will be ended when a stopping condition is met.  
K-means algorithm [29] is a typical partitive clustering technique. Given an a priori fixed value of \(K\), K-means divides the data set into \(K\) disjoint clusters which minimize the objective function of Equation (1), where \(m=1\) and \(u_{ij}\in\{0,1\}\). K-means algorithm is simple and fast, converging in just a few iteration steps.  
Unfortunately, when used as a gene-based clustering algorithm, it exhibits several shortcomings. To begin with, in a collection of gene expressions, the number of gene groupings is generally unknown beforehand. Users generally perform the algorithms several times, each time with a different value for \(K\), and compare the clustering outcomes to find the optimum cluster number.  
This comprehensive fine-tuning procedure may not be practical for a gene expression data set containing thousands of genes. Moreover, gene expression data typically involve an enormous quantity of noise; nonetheless, K-means forces each gene into a cluster that can lead the algorithm to be noise prone [30; 31].  
In the past, several clustering algorithms [31; 32; 33] were suggested to solve the disadvantages of the K-means algorithm. These techniques certain global parameters to regulate the performance of the resulting clusters (e.g., the maximum radius of a cluster and/or the minimum distance between clusters), therefore clustering consists of extracting only the adequate clusters from the data set. In so doing, the number of clusters can be determined automatically and samples not belonging to any adequate cluster are considered outliers. However, the quality of each cluster in gene data may differ extensively. Thus, choosing suitable global constraining parameters is often a challenging issue.