Overview of Clustering Rong Jin Outline K means for clustering Expectation Maximization algorithm for clustering Spectrum clustering if time is permitted Clustering Find out the underlying structure for given data points age Application I Search Result Clustering Application II Navigation Application III Google News Application III Visualization Islands of music Pampalk et al KDD 03 Application IV Image Compression http www ece neu edu groups rpl kmeans How to Find good Clustering Minimize the sum of distance within clusters 6 n arg min mi j r C m j mi j 6 i j 1 0 mi j j 1 j 1 i 1 r r xi C j r xi the j th cluster r xi the j th cluster 1 r any xi a single cluster C1 2 C2 C4 C5 C3 How to Efficiently Clustering Data 6 n arg min mi j r C m j i j j 1 i 1 r r xi C j 2 Memberships mi j and centers C j are correlated 1 r Given centers C j mi j 0 Given memberships mi j r r 2 j arg min xi C j k otherwise n r mi j xi r C j i 1n mi j i 1 K means for Clustering K means Start with a random guess of cluster centers Determine the membership of each data points Adjust the cluster centers K means for Clustering K means Start with a random guess of cluster centers Determine the membership of each data points Adjust the cluster centers K means for Clustering K means Start with a random guess of cluster centers Determine the membership of each data points Adjust the cluster centers K means 1 Ask user how many clusters they d like e g k 5 K means 1 Ask user how many clusters they d like e g k 5 2 Randomly guess k cluster Center locations K means 1 Ask user how many clusters they d like e g k 5 2 Randomly guess k cluster Center locations 3 Each datapoint finds out which Center it s closest to Thus each Center owns a set of datapoints K means 1 Ask user how many clusters they d like e g k 5 2 Randomly guess k cluster Center locations 3 Each datapoint finds out which Center it s closest to 4 Each Center finds the centroid of the points it owns K means 1 Ask user how many Computational O N clusters Complexity they d like e g where N is the number of points k 5 2 Randomly guess k cluster Center locations 3 Each datapoint finds out which Center it s closest to 4 Each Center finds the centroid of the points it Any owns Computational Problem Improve K means Group points by region KD tree SR tree Key difference Find the closest center for each rectangle Assign all the points within a rectangle to one cluster Improved K means Find the closest center for each rectangle Assign all the points within a rectangle to one cluster Improved K means Improved K means Improved K means Improved K means Improved K means Improved K means Improved K means Improved K means Improved K means A Gaussian Mixture Model for Clustering Assume that data are generated from a mixture of Gaussian distributions For each Gaussian distribution Center i Variance i ignore For each data point Determine membership zij if xi belongs to j th cluster Learning a Gaussian Mixture with known covariance Probability p x xi p x xi p x xi m mj p m mj p x xi m mj mj p m mj mj mj 1 2ps 2 d 2 xi mj exp 2s 2 2 Learning a Gaussian Mixture with known covariance Probability p x xi p x xi p x xi m mj p m mj p x xi m mj mj p m mj mj mj 1 2ps 2 d 2 xi mj exp 2s 2 2 Log likelihood of data 1 log p x x log p m m i j i i mj 2ps 2 d 2 Apply MLE to find optimal parameters xi mj exp 2s 2 2 p m mj mj j Learning a Gaussian Mixture with known covariance E Step E zij p m mj x xi p x xi m mj p m mj k p x xi m mn p m mj n 1 e k 1 2s e n 1 2 x m i j 2 p m mj 1 xi mn 2 2 2s p m mn Learning a Gaussian Mixture with known covariance M Step mj 1 m m E zij xi i 1 E z ij i 1 1 m p m mj E zij m i 1 Gaussian Mixture Example Start After First Iteration After 2nd Iteration After 3rd Iteration After 4th Iteration After 5th Iteration After 6th Iteration After 20th Iteration Mixture Model for Doc Clustering Q q1 q2 qK qi p w1 qi p w2 qi p wV qi A set of language models Mixture Model for Doc Clustering Q q1 q2 qK qi p w1 qi p w2 qi p wV qi A set of language models Probability p d di p d di p d di q q j qj p q q j p d di q q j qj V tf wk di p q q j p wk q j qj k 1 Mixture Model for Doc Clustering Q q1 q2 qK qi p w1 qi p w2 qi p wV qi A set of language models Probability p d di p d di p d di q q j qj p q q j p d di q q j qj V tf wk di p q q j p wk q j qj k 1 Mixture Model for Doc Clustering A set of language models Introduce Q q1 q2 qK hidden variable zij qi p w1 qi p w2 qi p wV qi zij document di is generated by the j th language model j Probability p d di p d di p d di q q j qj p q q j p d di q q j qj V tf wk di p q q j p wk q j qj k 1 Learning a Mixture Model E Step E zij p q q j d di p d di q q j p q q j K p d di q qn p q qn n 1 V tf wk di p wm q j m 1 K V p wm qn n 1 m 1 K number of language models p q q j tf wk di p q qn Learning a Mixture Model N E zij tf wi d k M Step p wi q j k 1 N E zij k 1 1 p q q j N N number of documents N dk E zij i 1 Examples of Mixture Models Other Mixture Models Probabilistic latent semantic index PLSI Latent Dirichlet Allocation LDA Problems I Both k means and mixture models need to compute centers of clusters and explicit distance measurement …