Clustering is concerned with grouping together objects that are similar to each other and dissimilar to the objects belonging to other clusters. Clustered is used to group items that seem to fall naturally together. Various type of clustering: hierarchical (nested) versus partitioned (un-nested), exclusive versus overlapping versus fuzzy, and complete versus partial. Clustering is an unsupervised learning process that partitions data such that similar data items grouped together in sets referred to as clusters, this activity is important for condensing and identifying patterns in data .
Clustering techniques apply when there is no class to predict but rather when the instances divide into natural groups. These clusters presumably reflect some mechanism at work in the domain from which instances are drawn a mechanism that causes some instances to bear a stronger resemblance to each other than they do to the remaining instances. Clustering naturally requires different techniques to the classification and association learning methods we have considered so far.
Hierarchical Clustering is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types:
Agglomerative: This is a "bottom up" approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.
Divisive: This is a "top down" approach: all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.
In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering are usually presented in a dendrogram.
Clustering Method
Specifies the method used to measure the distance between two clusters as the hierarchical tree is constructed. In each, the distance from each point in one cluster to each point in a second cluster is calculated, giving a set of pair wise distances. The methods differ in how the overall distance between the clusters is measured:
• Single Linkage
The smallest pair wise distance found between the two clusters is used. This method often leads to a "chaining" effect and is usually not recommended.
• Average Linkage
The average of all the pair wise distances between the two clusters is used.
• Total Linkage
The largest pair wise distance found between the two clusters is used.
Clustering Dimension
• Marker
Cluster the selected markers (genes) only based on the similarity across selected microarrays.
• Microarray
Cluster the selected microarrays only based on the similarity across selected markers.
• Both
Cluster both markers and microarrays.
Clustering Metric
The values being clustered, whether markers or microarrays, can each be represented by vectors of numbers, essentially either rows (markers) or columns (microarrays) taken from a spreadsheet view of all expression values. Several methods by which to calculate the distance between any two vectors are offered:
• Euclidean
The direct, point-to-point distance is calculated (square root of the sum of square differences).
• Pearson's
Pearson's correlation coefficient for two vectors is calculated.
• Spearman's
Spearman's rank correlation coefficient for two vectors is calculated.
Set Selection
Most analysis components provide the "All Arrays" and "All Markers" check-boxes to allow any activated sets of arrays or markers to be overridden. Normally, activating one or more sets of markers or arrays limits an analysis to those items in the active set(s).
• All Arrays
Use all arrays in the dataset.
• All Markers
Use all markers in the dataset.
Hierarchical clustering creates a hierarchy of clusters, which may represent in a tree structure called a dendrogram. The root of the tree consists of a single cluster containing all observations, and the leaves correspond to individual observations. Algorithms for hierarchical clustering are generally either agglomerative, in which one starts at the leaves and successively merges clusters together; or divisive, in which one starts at the root and recursively splits the clusters. Any valid metric use as a measure of similarity between pairs of observations. The choice of which clusters to merge or split is determined by a linkage criterion, which is a function of the pair wise distances between observations.
An Example
Let’s now see a simple example: a hierarchical clustering of distances in kilometers between some Italian cities. The method used is single-linkage.
Input distance matrix (L = 0 for all the clusters):
BA FI MI NA RM TO
BA 0 662 877 255 412 996
FI 662 0 295 468 268 400
MI 877 295 0 754 564 138
NA 255 468 754 0 219 869
RM 412 268 564 219 0 669
TO 996 400 138 869 669 0
The nearest pair of cities is MI and TO, at distance 138. These are merged into a single cluster called "MI/TO". The level of the new cluster is L(MI/TO) = 138 and the new sequence number is m = 1.
Then we compute the distance from this new compound object to all other objects. In single link clustering the rule is that the distance from the compound object to another object is equal to the shortest distance from any member of the cluster to the outside object. So the distance from "MI/TO" to RM is chosen to be 564, which is the distance from MI to RM, and so on.
After merging MI with TO we obtain the following matrix:
BA FI MI/TO NA RM
BA 0 662 877 255 412
FI 662 0 295 468 268
MI/TO 877 295 0 754 564
NA 255 468 754 0 219
RM 412 268 564 219 0
min d(i,j) = d(NA,RM) = 219 => merge NA and RM into a new cluster called NA/RM
L(NA/RM) = 219
m = 2
BA FI MI/TO NA/RM
BA 0 662 877 255
FI 662 0 295 268
MI/TO 877 295 0 564
NA/RM 255 268 564 0
min d(i,j) = d(BA,NA/RM) = 255 => merge BA and NA/RM into a new cluster called BA/NA/RM
L(BA/NA/RM) = 255
m = 3
BA/NA/RM FI MI/TO
BA/NA/RM 0 268 564
FI 268 0 295
MI/TO 564 295 0
min d(i,j) = d(BA/NA/RM,FI) = 268 => merge BA/NA/RM and FI into a new cluster called BA/FI/NA/RM
L(BA/FI/NA/RM) = 268
m = 4
BA/FI/NA/RM MI/TO
BA/FI/NA/RM 0 295
MI/TO 295 0
Finally, we merge the last two clusters at level 295.
The process is summarized by the following hierarchical tree:
Problems
The main weaknesses of agglomerative clustering methods are:
• they do not scale well: time complexity of at least O(n2), where n is the number of total objects;
• they can never undo what was done previously.
Source: http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html
Author: Vishal Malhotra
Roll Number: 12112
No comments:
Post a Comment