北京大学：《模式识别》课程教学资源（参考资料）Data Clustering - 50 Years Beyond K-means

Data Clustering: 50 Years Beyond K-means Anil K.Jain Department of Computer Science Michigan State University 合

Data Clustering: 50 Years Beyond K -means Anil K. Jain Department of Computer Science Michigan State University 

King-Sun Fu King-Sun Fu(1930-1985),a professor at Purdue was instrumental in the founding of IAPR,served as its first president,and is widely recognized for his extensive contributions to pattern recognition.(Wikipedia)

King-Sun Fu King-Sun Fu (1930-1985), a professor at Purdue was instrumental in the founding instrumental in the founding of IAPR of IAPR served as its first , served as its first president, and is widely recognized for his extensive contributions to pattern recognition. (Wikipedia)

Angkor Wat,Siem Reap Angfor Wat Combodia 了rw Hindu temple built by a Khmer king ~1150 AD; Khmer kingdom declined in the 15th century; French explorers discovered the hidden ruins in 1860 (Angelina Jolie alias "Lora Croft"in Tomb Raider thriller)

Angkor Wat, Siem Reap Hindu temple built by a Khmer king ~1150 AD; Khmer kingdom declined in the 15th century; French explorers discovered the hidden ruins in 1860 (Angelina Jolie alias Angelina Jolie alias Lora Croft in “Lora Croft ” in Tomb Raider thriller)

Apsaras of Angkor Wat Angkor Wat contains the most unique gallery of over 2,000 women depicted by detailed full body portraits What facial types are represented in these portraits? Kent Davis,Biometrics of the Godesess,DatAsia,Aug 2008 S.Marchal,Costumes et Parures Khmers:D'apres les devata D'Angkor-Vat,1927

Apsaras of Angkor Wat • Angkor Wat contains the most unique gallery of over 2,000 women depicted by detailed full body portraits • What facial types are represented in these portraits? Kent Davis, Biometrics of the Godesess, DatAsia, Aug 2008 S. Marchal, Costumes et Parures Khmers: D’apres les devata D’Angkor-Vat, 1927

Clustering of Apsara Faces Single Link 370 新第部 280 9105 783 6 127 landmarks oopppp8oooo C+ s卷±56电e0b++G+年o+9+ d g 94车年+++ 9 10 3 6 8 OX Xǒ Single Link clusters b o+9 +6半e +0p How do we validate the groups? Shape alignment

Clustering of Apsara Faces Single Link 127 facial landmarks 127 landmarks 1 2 9 10 3 4 6 5 7 8 Single Link clusters Shape alignment How do we validate the groups?

Ground Truth 整盛烟 666666665-- Khmer Cultural Center

Ground Truth Khmer Cultural Center

Data Explosion The digital universe was ~281 exabytes (281 billion gigabytes)in 2007;it would grow 10 times by 2011 Images and video,captured by over one billion devices (camera phones),are the major source To archive and effectively use this data,we need tools for data categorization http://eon.businesswire.com/releases/information/digital/prweb509640.htm http://www.emc.com/collateral/analyst-reports/diverse-exploding-digital-universe.pdf 尚

Data Explosion • Th di it l i 281 b t The digital universe was ~281 exabytes (281 billion gigabytes) in 2007; it would grow 10 times by 2011 • Images and video, captured by over one billion d i ( h ) th j devices (camera phones), are the major source • To archive and effectively use this data, we need tools for data categorization http://eon.businesswire.com/releases/information/digital/prweb509640.htm http://www.emc.com/collateral/analyst-reports/diverse-exploding-digital-universe.pdf 

Data Clustering Grouping of objects into meaningful categories Classification vs.clustering Unsupervised learning,exploratory data analysis, grouping,clumping,taxonomy,typology,Q-analysis Given a representation of n objects,find K clusters based on a measure of similarity Partitional vs.hierarchical A.K.Jain and R.C.Dubes.Algorithms for Clustering Data,Prentice Hall,1988.(available for download at:http://dataclustering.cse.msu.edu/)

Data Clustering • Grouping of objects into meaningful categories • Classification vs. clustering • Unsupervised learning, exploratory data analysis, grouping clumping taxonomy typology Q grouping, clumping, taxonomy, typology, Q-analysis analysis • Given a representation of n objects, find K clusters based on a measure of based on a measure of similarity similarity • Partitional vs. hierarchical A. K. Jain and R. C. Dubes. Algorithms for Clustering Data, Prentice Hall, 1988. (available for download at: http g) ://dataclustering.cse.msu.edu/)

Why Clustering? Natural classification:degree of similarity among forms (phylogenetic relationship or taxonomy) Data exploration:discover underlying structure, generate hypotheses,detect anomalies Compression:method for organizing data Applications:any scientific field that collects data! Astronomy,biology,marketing,engineering,..... Google Scholar:~1500 clustering papers in 2007 alone!

Why Clustering? • Natural classification: degree of similarity among forms (phylogenetic relationship or taxonomy) • Data exploration: discover underlying structure, generate hypotheses, detect anomalies • Compression: method for organizing data • Applications: any scientific field that collects data! Astronomy, biology, marketing, engineering,….. Google Scholar: ~1500 clustering papers in 2007 alone!

Historical Developments Cluster analysis first appeared in the title of a 1954 article analyzing anthropological data (STOR) Hierarchical Clustering:Sneath (1957),Sorensen (1957) K-Means:independently discovered Steinhaus1(1956),Lloyd2 (1957),Cox3(1957),Bal∥&Hal(1967),MacQueen5(1967) Mixture models (Wolfe,1970) Graph-theoretic methods (Zahn,1971) .K Nearest neighbors (Jarvis Patrick,1973) Fuzzy clustering (Bezdek,1973) Self Organizing Map(Kohonen,1982) Vector Quantization (Gersho and Gray,1992) 1Acad.Polon.Sci.,2Bell Tel.Report,3JASA,4Behavioral Sci.,5Berkeley Symp.Math Stat Prob. 合口

Historical Developments • Cluster analysis first appeared in the title of a 1954 article analyzing anthropological data (JSTOR) • Hierarchical Clustering: Sneath (1957) Sorensen (1957) Sneath (1957) , Sorensen (1957) • K-Means: independently discovered Steinhaus 1 (1956), Lloyd2 (1957), Cox3 (1957), Ball & Hall4 (1967), MacQueen 5 (1967) • Mixture models (Wolfe, 1970 ) • Graph-theoretic methods (Zahn, 1971) • K Nearest neighbors (Jarvis & Patrick, 1973) • Fuzzy clustering (Bezdek, 1973) • Self Organizing Map (Kohonen, 1982) • Vector Quantization (Gersho and Gray, 1992)  1Acad. Polon. Sci., 2Bell Tel. Report, 3JASA, 4Behavioral Sci., 5Berkeley Symp. Math Stat & Prob