数据挖掘之聚类分析

LOGOClusteringOverviewPartitioningMethodsK-MeansSequentialLeaderModelBasedMethodsDensityBasedMethodsHierarchicalMethods2Whatisclusteranalysis?FindinggroupsofobjectsObjectssimilartoeachotherareinthesamegroup.Objectsaredifferentfromthoseinothergroups.UnsupervisedLearningNolabelsDatadriven3Clusters4Inter-ClusterIntra-ClusterClusters5ApplicationsofClusteringMarketingFindinggroupsofcustomerswithsimilarbehaviours.BiologyFindinggroupsofanimalsorplantswithsimilarfeatures.BioinformaticsClusteringmicroarraydata,genesandsequences.EarthquakeStudiesClusteringobservedearthquakeepicenterstoidentifydangerouszones.Clusteringweblogdatatodiscovergroupsofsimilaraccesspatterns.SocialNetworksDiscoveringgroupsofindividualswithclosefriendshipsinternally.6Earthquakes7ImageSegmentation8TheBigPicture9RequirementsScalabilityAbilitytodealwithdifferenttypesofattributesAbilitytodiscoverclusterswitharbitraryshapeMinimumrequirementsfordomainknowledgeAbilitytodealwithnoiseandoutliersInsensitivitytoorderofinputrecordsIncorporationofuser-definedconstraintsInterpretabilityandusability1001234560123456X1=0.2XY1243PracticalConsiderations1101234560123456XY134201234560123456XY1=0.2Y1243Scalingmatters!NormalizationorNot?1213Evaluation14iiDxiiciDxiexnmmxJ1,12VS.Evaluation15SilhouetteAmethodofinterpretationandvalidationofclustersofdata.Asuccinctgraphicalrepresentationofhowwelleachdatapointlieswithinitsclustercomparedtootherclusters.a(i):averagedissimilarityofiwithallotherpointsinthesameclusterb(i):thelowestaveragedissimilarityofitootherclusters16)}(),(max{)()()(iaibiaibisSilhouette17-3-2-101234-3-2-101234-0.200.20.40.60.8112SilhouetteValueClusterK-Means18K-Means19K-Means20K-MeansDeterminethevalueofK.ChooseKclustercentresrandomly.Eachdatapointisassignedtoitsclosestcentroid.Usethemeanofeachclustertoupdateeachcentroid.Repeatuntilnomorenewassignment.ReturntheKcentroids.ReferenceJ.MacQueen(1967):SomeMethodsforClassificationandAnalysisofMultivariateObservations,Proceedingsofthe5thBerkeleySymposiumonMathematicalStatisticsandProbability,vol.1,pp.281-297.21CommentsonK-MeansProsSimpleandworkswellforregulardisjointclusters.Convergesrelativelyfast.RelativelyefficientandscalableO(t·k·n)•t:iteration;k:numberofcentroids;n:numberofdatapointsConsNeedtospecifythevalueofKinadvance.•Difficultanddomainknowledgemayhelp.Mayconvergetolocaloptima.•Inpractice,trydifferentinitialcentroids.Maybesensitivetonoisydataandoutliers.•Meanofdatapoints…Notsuitableforclustersof•Non-convexshapes22TheInfluenceofInitialCentroids23TheInfluenceofInitialCentroids24SequentialLeaderClusteringAveryefficientclusteringalgorithm.NoiterationAsinglepassofthedataNoneedtospecifyKinadvance.Chooseaclusterthresholdvalue.Foreverynewdatapoint:Computethedistancebetweenthenewdatapointandeverycluster'scentre.Iftheminimumdistanceissmallerthanthechosenthreshold,assignthenewdatapointtothecorrespondingclusterandre-computeclustercentre.Otherwise,createanewclusterwiththenewdatapointasitscentre.Clusteringresultsmaybeinfluencedbythesequenceofdatapoints.2526GaussianMixture27)2/()(22221),,(xexg1&0,),,()(1iiiniiiixgxfClusteringbyMixtureModels28K-MeansRevisited29𝜃={𝑥1,𝑦1,(𝑥2,𝑦2)}𝑍={𝐶𝑙𝑢𝑠𝑡𝑒𝑟1,𝐶𝑙𝑢𝑠𝑡𝑒𝑟2}modelparameterslatentparametersExpectationMaximization3031𝑃𝐴𝐸=𝑃𝐸𝐴𝑃(𝐴)𝑃(𝐸)EM:GaussianMixture32Gaussianjthbythegeneratedisiinstancerwhethe:componentsmixtureofnumberthe:pointsdataofnumberthe:ijznmnkkxjxnkkkijjiijkijieexxpxxpzE1)(21)(2112222)|()|(][miijmiiijjzExzE11][][miijjzEm1][133DensityBasedMethodsGenerateclustersofarbitraryshapes.Robustagainstnoise.NoKvaluerequiredinadvance.Somewhatsimilartohumanvision.34DBSCANDensity-BasedSpatialClusteringofApplicationswithNoiseDensity:numberofpointswithinaspecifiedradiusCorePoint:pointswithhighdensityBorderPoint:pointswithlowdensitybutintheneighbourhoodofacorepointNoisePoint:neitheracorepointnoraborderpoint35CorePointNoisePointBorderPointDBSCAN36pqdirectlydensityreachablepqdensityreachableoqpdensityconnectedDBSCANAclusterisdefinedasthemaximalsetofdensityconnectedpoints.StartfromarandomlyselectedunseenpointP.IfPisacorepoint,buildaclusterbygraduallyaddingallpointsthataredensityreachabletothecurrentpointset.Noisepointsarediscarded(unlabelled).37HierarchicalClusteringProduceasetofnestedtree-likeclusters.Canbevisualizedasadendrogram.Clusteringisobtainedbycuttingatdesiredlevel.NoneedtospecifyKinadvance.Maycorrespondtomeaningfultaxonomies.38AgglomerativeMethodsBottom-upMethodAssigneachdatapointtoacluster.Calculatetheproximitymatrix.Mergethepairofclosestclusters.Repeatuntilonlyasingleclusterremains.Howtocalculatethedistancebetweenclusters?SingleLinkMinimumdistancebetweenpointsCompleteLinkMaximumdistancebetweenpoints39Example40BAFIMINARMTOBA0662877255412996FI6620295468268400MI8772950754564138NA2554687540219869RM4122685642190669TO9964001388696690SingleLinkExample41BAFIMI/TONARMBA0662877255412FI6620295468268MI/TO877