模式识别聚类算法ppt课件.ppt

《模式识别聚类算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模式识别PatternRecognitionChapter10(III)HIERARCHICALCLUSTERINGALGORITHMS9/26/20211HIERARCHICALCLUSTERINGALGORITHMSTheyproduceahierarchyof(hard)clusteringsinsteadofasingleclustering.Applicationsin:SocialsciencesBiologicaltaxonomyModernbiologyMedicineArchaeologyComputersciencea

2、ndengineering2LetX={x1,…,xN},xi=[xi1,…,xil]T.Recallthat:Inhardclusteringeachvectorbelongsexclusivelytoasinglecluster.Anm-(hard)clusteringofX,,isapartitionofXintomsets(clusters)C1,…,Cm,sothat:Bythedefinition:={Cj,j=1,…m}Definition:Aclustering1containingkclustersissaidto

3、benestedintheclustering2containingr(

4、teringalgorithmsproduceahierarchyofnestedclusterings.TheyinvolveNstepsatthemost.Ateachstept,theclusteringtisproducedbyt-1.Maincategories:Agglomerativeclusteringalgorithms:Here0={{x1},…,{xN}},N-1={{x1,…,xN}}and0…N-1.Divisiveclusteringalgorithms:Here0={{x1,…,xN}},

5、N-1={{x1},…,{xN}}andN-1…0.4AGGLOMERATIVEALGORITHMSLetg(Ci,Cj)aproximityfunctionbetweentwoclustersofX.GeneralizedAgglomerativeScheme(GAS)InitializationChoose0={{x1},…,{xN}}t=0Repeatt=t+1Choose(Ci,Cj)int-1suchthatDefineCq=CiCjandproducet=(t-1-{Ci,Cj}){Cq}Untilallv

6、ectorslieinasinglecluster.5Remarks:Iftwovectorscometogetherintoasingleclusteratleveltofthehierarchy,theywillremaininthesameclusterforallsubsequentclusterings.Asaconsequence,thereisnowaytorecovera“poor”clusteringthatmayhaveoccurredinanearlierlevelofhierarchy.Numberofoperat

7、ions:O(N3)6Definitionsofsomeusefulquantities:LetX={x1,x2,…,xN},withxi=[xi1,xi2,…,xil]T.Patternmatrix(D(X)):AnNxlmatrixwhosei-throwisxi(transposed).Proximity(similarityordissimilarity)matrix(P(X)):AnNxNmatrixwhose(i,j)elementequalstheproximity(xi,xj)(similaritys(xi,xj),di

8、ssimilarityd(xi,xj)).Example1:LetX={x1,x2,x3,x4,x5},withx1=[1,1]T,x2=[2,1]T,x3=[5,4]T,x4=[6,5]T,