Discriminant Analysis cluster analysis basic algorithms参考.ppt

Ahmed Rebai Bioinformatics and Comparative Genome Analysis March 2007 K-Means Clustering: Lloyd Algorithm Lloyd Algorithm Arbitrarily assign the k cluster centers while the cluster centers keep changing Assign each data point to the cluster Ci corresponding to the closest cluster representative (center) xi (1 ≤ i ≤ k) After the assignment of all n data points, compute new cluster representatives according to the center of gravity of each existing cluster, that is, the new cluster representative is *This may lead to merely a locally optimal clustering. Ahmed Rebai Bioinformatics and Comparative Genome Analysis March 2007 k1 k2 k3 Ahmed Rebai Bioinformatics and Comparative Genome Analysis March 2007 k1 k2 k3 Ahmed Rebai Bioinformatics and Comparative Genome Analysis March 2007 k1 k2 k3 Ahmed Rebai Bioinformatics and Comparative Genome Analysis March 2007 k1 k2 k3 Ahmed Rebai Bioinformatics and Comparative Genome Analysis March 2007 The problem is You get what you asked for: the number of final clusters is the number you choose at the beginning One solution is to try different choices of the number of cluster Can use other techniques (PCA) to get an idea on the number of ‘major’ clusters Ahmed Rebai Bioinformatics and Comparative Genome Analysis March 2007 K-means vs hierarchical clustering This method differs from the hierarchical clustering in many ways. In particular, - There is no hierarchy, the data are partitioned. You will be presented only with the final cluster membership for each case. - There is no role for the dendrogram in k-means clustering. - You must supply the number of clusters (k) into which the data are to be grouped. Cluster analysis in microarray data Ahmed Rebai Bioinformatics and Comparative Genome Analysis March 2007 Inferring Gene Functionality Researchers want to know the functions of new genes Simply comparing the new gene sequences to known DNA sequences often does not give away the ac