clustering数据挖掘聚类算法介绍

Instructor:AssociateProf.YingLiuGraduateUniversityofChineseAcademyofSciencesFictitiousEconomyandDataScienceResearchCenterDataMining2011/10/312ReviewDatamining—coreofknowledgediscoveryprocessDataCleaningandIntegrationDatabasesDataWarehouseSelectionandTransformationDataMiningPatternEvaluationFlatfiles2011/10/313ClusterAnalysisWhatisClusterAnalysis?TypesofDatainClusterAnalysisACategorizationofMajorClusteringMethodsPartitioningMethodsHierarchicalMethodsDensity-BasedMethodsGrid-BasedMethodsOutlierAnalysisSummary2011/10/314WhatisClusterAnalysis?Cluster:acollectionofdataobjectsSimilartooneanotherwithinthesameclusterDissimilartotheobjectsinotherclustersClusteranalysisFindingsimilaritiesbetweendataaccordingtothecharacteristicsfoundinthedataandgroupingsimilardataobjectsintoclustersUnsupervisedlearning:nopredefinedclassesTypicalapplicationsAsastand-alonetooltogetinsightintodatadistributionAsapreprocessingstepforotheralgorithms2011/10/315Clustering:RichApplicationsandMultidisciplinaryEffortsPatternRecognitionGISCreatethematicmapsinGISbyclusteringfeaturespacesDetectspatialclustersorforotherspatialminingtasksImageProcessingEconomicScience(especiallymarketresearch)SoftwarepackageS-Plus,SPSS,SAS2011/10/316ExamplesofClusteringApplicationsMarketing:Helpmarketersdiscoverdistinctgroupsintheircustomerbases,andthenusethisknowledgetodeveloptargetedmarketingprogramsLanduse:IdentificationofareasofsimilarlanduseinanearthobservationdatabaseInsurance:IdentifyinggroupsofmotorinsurancepolicyholderswithahighaverageclaimcostCity-planning:Identifyinggroupsofhousesaccordingtotheirhousetype,value,andgeographicallocation2011/10/317ExamplesofClusteringApplicationsEarth-quakestudies:ObservedearthquakeepicentersshouldbeclusteredalongcontinentfaultsBiology:categorizegeneswithsimilarfunctionalityDocumentclassificationClusterWeblogdatatodiscovergroupsofsimilaraccessingpatterns2011/10/318WhatIsGoodClustering?Agoodclusteringmethodwillproducehighqualityclusterswithhighintra-classsimilaritylowinter-classsimilarityThequalityofaclusteringresultdependsonboththesimilaritymeasureusedbythemethodanditsimplementationThequalityofaclusteringmethodisalsomeasuredbyitsabilitytodiscoversomeorallofthehiddenpatterns2011/10/319RequirementsofClusteringScalabilityAbilitytodealwithdifferenttypesofattributesAbilitytohandledynamicdataDiscoveryofclusterswitharbitraryshapeMinimalrequirementsfordomainknowledgetodetermineinputparametersAbletodealwithnoiseandoutliersInsensitivetoorderofinputrecordsHighdimensionalityIncorporationofuser-specifiedconstraintsInterpretabilityandusability2011/10/3110MeasuretheQualityofClusteringDissimilarity/Similaritymetric:Similarityisexpressedintermsofadistancefunction,typicallymetric:d(i,j)Thedefinitionsofdistancefunctionsareusuallyverydifferentforinterval-scaled,boolean,categorical,ordinalratio,andvectorvariablesWeightsmaybeassignedtodifferentvariablesbasedonapplicationsanddatasemanticsItishardtodefine―similarenough‖or―goodenough‖Theansweristypicallyhighlysubjective2011/10/3111ClusterAnalysisWhatisClusterAnalysis?TypesofDatainClusterAnalysisACategorizationofMajorClusteringMethodsPartitioningMethodsHierarchicalMethodsDensity-BasedMethodsGrid-BasedMethodsOutlierAnalysisSummary2011/10/3112DataStructuresDatamatrix(twomodes)Dissimilaritymatrix(onemode)npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x0...)2,()1,(:::)2,3()...ndnd0dd(3,10d(2,1)02011/10/3113TypeofDatainClusteringAnalysisInterval-scaledvariablesBinaryvariablesNominalvariablesOrdinalvariablesratiovariablesVariablesofmixedtypes2011/10/3114Interval-valuedVariablesStandardizedataCalculatethemeanabsolutedeviation:whereCalculatethestandardizedmeasurement(z-score)Usingmeanabsolutedeviationismorerobustthanusingstandarddeviation.)...211nffffxx(xnm|)|...|||(|121fnffffffmxmxmxnsffififsmxz2011/10/3115SimilarityandDissimilarityBetweenObjectsDistancesarenormallyusedtomeasurethesimilarityordissimilaritybetweentwodataobjectsSomepopularonesinclude:Minkowskidistance:wherei=(xi1,xi2,…,xip)andj=(xj1,xj2,…,xjp)aretwop-dimensionaldataobjects,andqisapositiveintegerIfq=1,disManhattandistanceqqppqqjxixjxixjxixjid)||...|||(|),(2211||...||||),(2211ppjxixjxixjxixjid2011/10/3116SimilarityandDissimilarityBetweenObjectsIfq=2,disEuclideandistance:Properties•d(i,j)0•d(i,i)=0•d(i,j)=d(j,i)•d(i,j)d(i,k)+d(k,j)Also,onecanuseweighteddistance)||...|||(|),(2222211ppjxixjxixjxixjid2011/10/3117BinaryVariablesAcontingencytableforbinarydataDistancemeasureforsymmetricbinaryvariables:Distancemeasureforasymmetricbinaryvariables:dcbacbjid),(cbacbjid),(pdbcasumdcdcbabasum0101ObjectiObjectj2011/10/3118DissimilaritybetweenBinaryVariablesExamplegenderisasymmetricattributetheremainingattributesareasymmetricbinaryletthevaluesYandPbesetto1,andthevalueNbesetto0NameGenderFeverCoughTest-1Test-2Test-3Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN75.02112