Machine Learning 1010 701 15701 15 781 Spring 2008 Clustering Eric Xing Lecture 15 March 17 2008 Reading Chap 9 C B book Eric Xing 1 What is clustering z Clustering the process of grouping a set of objects into classes of similar objects z high intra class similarity z low inter class similarity z It is the commonest form of unsupervised learning z Unsupervised learning learning from raw unlabeled unannotated etc data as opposed to supervised data where a classification of examples is given z A common and important task that finds many applications in Science Engineering information Science and other places Eric Xing z Group genes that perform the same function z Group individuals that has similar political view z Categorize documents of similar topics z Ideality similar objects from pictures 2 1 Examples z People z Images z Language z species Eric Xing 3 Issues for clustering z What is a natural grouping among these objects z z What makes objects related z z Definition of similarity distance Representation for objects z z Definition of groupness Vector space Normalization How many clusters z Fixed a priori z Completely data driven z z z Avoid trivial clusters too large or small Clustering Algorithms z Partitional algorithms z Hierarchical algorithms Formal foundation and convergence Eric Xing 4 2 What is a natural grouping among these objects Eric Xing 5 What is Similarity Hard to define But we know it when we see it z The real meaning of similarity is a philosophical question We will take a more pragmatic approach z Depends on representation and algorithm For many rep alg easier to think in terms of a distance rather than similarity between vectors Eric Xing 6 3 What properties should a distance measure have z D A B D B A Symmetry z D A A 0 Constancy of Self Similarity z D A B 0 IIf A B Positivity Separation z D A B D A C D B C Triangular Inequality Eric Xing 7 Intuitions behind desirable distance measure properties z D A B D B A z z D A A 0 z z z Eric Xing Positivity Separation Otherwise there are objects in your world that are different but you cannot tell apart D A B D A C D B C z Constancy of Self Similarity Otherwise you could claim Alex looks more like Bob than Bob does D A B 0 IIf A B z Symmetry Otherwise you could claim Alex looks like Bob but Bob looks nothing like Alex Triangular Inequality Otherwise you could claim Alex is very like Bob and Alex is very like Carl but Bob is very unlike Carl 8 4 Distance Measures Minkowski Metric z Suppose two object x and y both have p features x x1 x2 L x p y y1 y2 L y p z The Minkowski metric is defined by r d x y p x y i i r i 1 z Most Common Minkowski Metrics 1 r 2 Euclidean distance d x y 2 p x y i i 2 i 1 p d x y xi yi 2 r 1 Manhattan distance i 1 3 r sup distance d x y max xi yi 1 i p Eric Xing 9 An Example x 3 y 4 1 Euclidean distance 2 42 32 5 2 Manhattan distance 4 3 7 3 sup distance Eric Xing max 4 3 4 10 5 Hamming distance z Manhattan distance is called Hamming distance when all features are binary z Gene Expression Levels Under 17 Conditions 1 High 0 Low 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 GeneA 0 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 1 GeneB 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 Hamming Distance 01 10 4 1 5 Eric Xing 11 Similarity Measures Correlation Coefficient z Pearson correlation coefficient p s x y x x y y i i 1 p i p x x y 2 i i 1 where x 1 p i 1 p x i 1 i and y 1 p i y 2 p y i 1 i s x y 1 z Special case cosine distance r r x y s x y r r x y Eric Xing 12 6 Similarity Measures Correlation Coefficient Expression Level Expression Level Gene A Gene B Gene B Gene A Time Time Expression Level Gene B Gene A Time Eric Xing 13 A generic technique for measuring similarity z To measure the similarity between two objects transform one of the objects into the other and measure how much effort it took The measure of effort becomes the distance measure The distance between Patty and Selma Change dress color 1 point Change earring shape 1 point Change hair part 1 point D Patty Selma 3 The distance between Marge and Selma Change dress color 1 point Add earrings 1 point Decrease height 1 point Take up smoking 1 point Lose weight 1 point DPMarge Selma 5 Eric Xing This is called the Edit distance or the Transformation distance 14 7 Clustering Algorithms z z Partitional algorithms z Usually start with a random partial partitioning z Refine it iteratively z K means clustering z Mixture Model based clustering Hierarchical algorithms z Bottom up agglomerative z Top down divisive Eric Xing 15 Hierarchical Clustering z Build a tree based hierarchical taxonomy dendrogram from a set of documents z Note that hierarchies are commonly used to organize information for example in a web portal z Eric Xing Yahoo is hierarchy is manually created we will focus on automatic creation of hierarchies in data mining 16 8 Dendogram z A Useful Tool for Summarizing Similarity Measurement z z The similarity between two objects in a dendrogram is represented as the height of the lowest internal node they share Clustering obtained by cutting the dendrogram at a desired level each connected component forms a cluster Eric Xing 17 Hierarchical Clustering z Bottom Up Agglomerative Clustering z Starts with each obj in a separate cluster z then repeatedly joins the closest pair of clusters z until there is only one cluster The history of merging forms a binary tree or hierarchy z Top Down divisive z Starting with all the data in a single cluster z Consider every possible way to divide the cluster into two Choose the best division z And recursively operate on both sides Eric Xing 18 9 Closest pair of clusters The distance between two clusters is defined as the distance between z Single Link z z Complete Link z z Furthest Neighbor their furthest members Centroid z z Nearest Neighbor their closest members Clusters whose centroids centers of gravity are the most cosine similar Average z average of all cross cluster pairs Eric Xing 19 Single Link Method Euclidean Distance a b c a b d b c d a 2 5 6 b 3 5 c 4 a b c c d 1 b c d a 2 5 6 b 3 …
View Full Document
Unlocking...