模式識(shí)別聚類分析

模式識(shí)別聚類分析第1頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/122ClusterAnalysis(聚類分析）Findinggroupsofobjectssuchthattheobjectsinagroupwillbesimilar(orrelated)tooneanotheranddifferentfrom(orunrelatedto)theobjectsinothergroupsInter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized第2頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/123ApplicationsofClusterAnalysisUnderstandingGrouprelateddocumentsforbrowsing,groupgenesandproteinsthathavesimilarfunctionality,orgroupstockswithsimilarpricefluctuationsSummarizationReducethesizeoflargedatasetsClusteringprecipitationinAustralia第3頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/124WhatisNOTClusterAnalysis?SupervisedclassificationHaveclasslabelinformationSimplesegmentationDividingstudentsintodifferentregistrationgroupsalphabetically,bylastnameResultsofaqueryGroupingsarearesultofanexternalspecificationGraphpartitioningSomemutualrelevanceandsynergy,butareasarenotidentical第4頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/125NotionofaClustercanbeAmbiguousHowmanyclusters?FourClusters

TwoClusters

SixClusters

第5頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/126TypesofClusteringsAclusteringisasetofclustersImportantdistinctionbetweenhierarchicalandpartitional

setsofclustersPartitionalClustering(flat)Adivisiondataobjectsintonon-overlappingsubsets(clusters)suchthateachdataobjectisinexactlyonesubsetHierarchicalclusteringAsetofnestedclustersorganizedasahierarchicaltree第6頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/127PartitionalClusteringOriginalPointsAPartitionalClustering第7頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/128HierarchicalClusteringTraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram第8頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/129TypesofClusters:Well-SeparatedWell-SeparatedClusters:Aclusterisasetofpointssuchthatanypointinaclusteriscloser(ormoresimilar)toeveryotherpointintheclusterthantoanypointnotinthecluster.3well-separatedclusters第9頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1210TypesofClusters:Center-BasedCenter-basedAclusterisasetofobjectssuchthatanobjectinaclusteriscloser(moresimilar)tothe“center”ofacluster,thantothecenterofanyotherclusterThecenterofaclusterisoftenacentroid,theaverageofallthepointsinthecluster,oramedoid,themost“representative”pointofacluster4center-basedclusters第10頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1211k-means算法step1.任意選擇k個(gè)對(duì)象作為初始的類的中心step2.repeatstep3.若文檔d與中心x比其他中心點(diǎn)都近，則把d賦給x所代表的類step4.計(jì)算每個(gè)類的特征的平均值，并以這些特征的平均值產(chǎn)生一個(gè)新的中心。step5.until類不再發(fā)生變化,即沒有對(duì)象進(jìn)行被重新分配時(shí)過程結(jié)束。

第11頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1212K-meansClusteringPartitionalclusteringapproachEachclusterisassociatedwithacentroid(centerpoint)EachpointisassignedtotheclusterwiththeclosestcentroidNumberofclusters,K,mustbespecifiedThebasicalgorithmisverysimple第12頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1213K-meansClustering–DetailsInitialcentroidsareoftenchosenrandomly.Clustersproducedvaryfromoneruntoanother.Thecentroidis(typically)themean(期望,平均值）ofthepointsinthecluster.‘Closeness’ismeasuredbyEuclideandistance,cosinesimilarity,correlation,etc.K-meanswillconvergeforcommonsimilaritymeasuresmentionedabove.Mostoftheconvergence（收斂）happensinthefirstfewiterations.Oftenthestoppingconditionischangedto‘Untilrelativelyfewpointschangeclusters’ComplexityisO(n*K*I*d)n=numberofpoints,K=numberofclusters,

I=numberofiterations,d=numberofattributes第13頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1214TheK-MeansClusteringMethod

Example012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassign第14頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1215TwodifferentK-meansClusteringsSub-optimalClusteringOptimalClusteringOriginalPoints第15頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1216ImportanceofChoosingInitialCentroids第16頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1217ImportanceofChoosingInitialCentroids第17頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1218EvaluatingK-meansClustersMostcommonmeasureisSumofSquaredError(SSE)Foreachpoint,theerroristhedistancetothenearestclusterTogetSSE,wesquaretheseerrorsandsumthem.xisadatapointinclusterCiandmiistherepresentativepointforclusterCi

canshowthatmi

correspondstothecenter(mean)oftheclusterGiventwoclusters,wecanchoosetheonewiththesmallesterror.第18頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1219ImportanceofChoosingInitialCentroids…第19頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1220ImportanceofChoosingInitialCentroids…第20頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1221ProblemswithSelectingInitialPointsIfthereareK‘real’clustersthenthechanceofselectingonecentroidfromeachclusterissmall.ChanceisrelativelysmallwhenKislargeIfclustersarethesamesize,n,then

Forexample,ifK=10,thenprobability=10!/1010=0.00036Sometimestheinitialcentroidswillreadjustthemselvesin‘right’way,andsometimestheydon’tConsideranexampleoffivepairsofclusters第21頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1222SolutionstoInitialCentroidsProblemMultipleruns,choosetheonewithminimunSSEHelps,butprobabilityisnotonyoursideSampleandusehierarchicalclusteringtodetermineinitialcentroidsSelectmorethankinitialcentroidsandthenselectamongtheseinitialcentroidsSelectmostwidelyseparatedPostprocessing第22頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1223HandlingEmptyClustersBasicK-meansalgorithmcanyieldemptyclustersSeveralstrategiesChoosethepointthatcontributesmosttoSSEChooseapointfromtheclusterwiththehighestSSEIfthereareseveralemptyclusters,theabovecanberepeatedseveraltimes.第23頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1224UpdatingCentersIncrementallyInthebasicK-meansalgorithm,centroidsareupdatedafterallpointsareassignedtoacentroidAnalternativeistoupdatethecentroidsaftereachassignment(incrementalapproach)EachassignmentupdateszeroortwocentroidsMoreexpensiveIntroducesanorderdependencyNevergetanemptyclusterCanuse“weights”tochangetheimpact第24頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1225Pre-processingandPost-processingPre-processingNormalizethedataEliminateoutliersPost-processingEliminatesmallclustersthatmayrepresentoutliersSplit‘loose’clusters,i.e.,clusterswithrelativelyhighSSEMergeclustersthatare‘close’andthathaverelativelylowSSECanusethesestepsduringtheclusteringprocessISODATA第25頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1226LimitationsofK-meansK-meanshasproblemswhenclustersareofdifferingSizesDensitiesNon-globularshapesK-meanshasproblemswhenthedatacontainsoutliers.第26頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1227LimitationsofK-means:DifferingSizesOriginalPointsK-means(3Clusters)第27頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1228LimitationsofK-means:DifferingDensityOriginalPointsK-means(3Clusters)第28頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1229LimitationsofK-means:Non-globularShapesOriginalPointsK-means(2Clusters)第29頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1230OvercomingK-meansLimitationsOriginalPoints K-meansClustersOnesolutionistousemanyclusters.Findpartsofclusters,butneedtoputtogether.第30頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1231OvercomingK-meansLimitationsOriginalPoints K-meansClusters第31頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1232OvercomingK-meansLimitationsOriginalPoints K-meansClusters第32頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1233Fuzzyc-meansclustering

Infuzzyclustering,eachpointhasadegreeofbelongingtoclusters,ratherthanbelongingcompletelytojustonecluster.Thus,pointsontheedgeofacluster,maybeintheclustertoalesserdegreethanpointsinthecenterofcluster.Foreachpointxwehaveacoefficientgivingthedegreeofbeinginthekthclusteruk(x).Usually,thesumofthosecoefficientsforanygivenxisdefinedtobe

1:第33頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1234:

Withfuzzyc-means,thecentroidofaclusteristhemeanofallpoints,weightedbytheirdegreeofbelongingtothecluster:第34頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1235Thedegreeofbelongingisrelatedtotheinverseofthedistancetotheclustercenter:第35頁(yè)，共39頁(yè)，2023年，2月20日，星期五2011/5/1236thenthecoefficientsarenormalizedandfuzzyfiedwitharealparameterm

>

1sothattheirsumis

1.So第36頁(yè)，共39頁(yè)，2023年，2月2