FAFU机器学习09-1 Clustering Basics课件

FoundationsofMachineLearning

ClusteringBasics(聚类基础)2023/11/4ClusteringLesson8-1ClusteringBasicsDefinitionandMotivation（定义与动机）DataPreprocessingandSimilarityComputationObjectiveofClusteringClusteringEvaluation

2023/11/4ClusteringLesson8-2ClusteringBasicsDefinitionandMotivationFindinggroupsofobjectssuchthattheobjectsinagroupwillbesimilar(orrelated)tooneanotheranddifferentfrom(orunrelatedto)theobjectsinothergroups.2023/11/4ClusteringLesson8-3ClusteringBasicsDefinitionandMotivation

Astand-alonetool:exploredatadistributionApreprocessingstepforotheralgorithmsPatternrecognition,spatialdataanalysis,imageprocessing,marketresearch,WWW,…ClusterdocumentsClusterweblogdatatodiscovergroupsofsimilaraccesspatternsClusteringCo-expressedGenesMarketing:Helpmarketersdiscoverdistinctgroupsintheircustomerbases,andthenusethisknowledgetodeveloptargetedmarketingprogramsClimate:understandingearthclimate,findpatternsofatmosphericandocean

2023/11/4ClusteringLesson8-4ClusteringBasicsDefinitionandMotivationAstand-alonetool:exploredatadistributionApreprocessingstepforotheralgorithmsPatternrecognition,spatialdataanalysis,imageprocessing,marketresearch,WWW,…TwoImportantAspectsPropertiesofinputdataDefinethesimilarityordissimilaritybetweenpointsRequirementofclusteringDefinetheobjectiveandmethodology

2023/11/4ClusteringLesson8-5ClusteringBasicsDefinitionandMotivationDataPreprocessingandSimilarityComputation（数据预处理和相似性计算）

ObjectiveofClusteringClusteringEvaluation

2023/11/4ClusteringLesson8-6DataPreprocessingandSimilarityComputationData:CollectionofdataobjectsandtheirattributesAnattributeisapropertyorcharacteristicofanobjectExamples:eyecolorofaperson,temperature,etc.Attributeisalsoknownasdimension,variable,field,characteristic,orfeatureAcollectionofattributesdescribeanobjectObjectisalsoknownasrecord,point,case,sample,entity,orinstance2023/11/4ClusteringLesson8-7DataPreprocessingandSimilarityComputationDataMatrix（数据矩阵）Representsnobjectswithpvariables

2023/11/4ClusteringLesson8-8DataPreprocessingandSimilarityComputationSimilarityandDissimilaritySimilarityNumericalmeasureofhowaliketwodataobjectsareIshigherwhenobjectsaremorealikeOftenfallsintherange[0,1]DissimilarityNumericalmeasureofhowdifferentaretwodataobjectsLowerwhenobjectsaremorealikeMinimumdissimilarityisoften0Upperlimitvaries2023/11/4ClusteringLesson8-9DataPreprocessingandSimilarityComputationDistanceMatrix（距离矩阵）Representspairwisedistanceinnobjects

Annbynmatrixd(i,j):

distanceordissimilaritybetweenobjectsiandjNonnegativeCloseto0:similar

2023/11/4ClusteringLesson8-10DataPreprocessingandSimilarityComputationDataMatrix->DistanceMatrix2023/11/4ClusteringLesson8-11DataPreprocessingandSimilarityComputationTypesofAttributes（属性的类型）Discrete（离散）HasonlyafiniteorcountablyinfinitesetofvaluesExamples:zipcodes,counts,orthesetofwordsinacollectionofdocumentsNote:binaryattributesareaspecialcaseofdiscreteattributesOrdinal（定序）HasonlyafiniteorcountablyinfinitesetofvaluesOrderofvaluesisimportantExamples:rankings(e.g.,painlevel1-10),grades(A,B,C,D)Continuous（连续）HasrealnumbersasattributevaluesExamples:temperature,height,orweightContinuousattributesaretypicallyrepresentedasfloating-pointvariables2023/11/4ClusteringLesson8-12DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributes

2023/11/4ClusteringLesson8-13DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributesMinkowskiDistance—ContinuousAttributeMinkowskidistance:ageneralizationIfq=2,disEuclideandistanceIfq=1,disManhattandistance2023/11/4ClusteringLesson8-14DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributes

MinkowskiDistance—ContinuousAttributeStandardizationCalculatethemeanabsolutedeviationCalculatethestandardizedmeasurement(z-score)2023/11/4ClusteringLesson8-15DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributesMinkowskiDistance—ContinuousAttributeStandardizationMahalanobisDistance

Adissimilaritymeasurebetweentwo

randomvectorsxandyofthesame

distributionwiththe

covariancematrix

S.2023/11/4ClusteringLesson8-16DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributesMinkowskiDistance—ContinuousAttributeStandardizationMahalanobisDistanceCommonPropertiesofaDistanceDistances,suchastheEuclideandistance,havesomewellknownproperties1.d(p,q)>=0forallpandqandd(p,q)=0onlyifp=q.(Positivedefiniteness)2.d(p,q)=d(q,p)forallpandq.(Symmetry)3.d(p,r)<=d(p,q)+d(q,r)forallpointsp,q,andr.(TriangleInequality)2023/11/4ClusteringLesson8-17DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributesMinkowskiDistance—ContinuousAttributeMahalanobisDistanceSimilarityforBinaryAttributesComputesimilaritiesusingthefollowingquantitiesM01=thenumberofattributeswherepwas0andqwas1M10=thenumberofattributeswherepwas1andqwas0M00=thenumberofattributeswherepwas0andqwas0M11=thenumberofattributeswherepwas1andqwas1SimpleMatchingandJaccardCoefficients2023/11/4ClusteringLesson8-18DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributesMinkowskiDistance—ContinuousAttributeMahalanobisDistanceSimilarityforBinaryAttributesCommonPropertiesofaSimilaritys(p,q)=1(ormaximumsimilarity)onlyifp=q.s(p,q)=s(q,p)forallpandq.(Symmetry)wheres(p,q)is

thesimilaritybetweenpoints(dataobjects),pandq.2023/11/4ClusteringLesson8-19DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributesMinkowskiDistance—ContinuousAttributeMahalanobisDistanceSimilarityforBinaryAttributesCommonPropertiesofaSimilarityCharacteristicsoftheInputDataAreImportantSparseness,Attributetype,TypeofData,Dimensionality,NoiseandOutliers,TypeofDistribution=>Conductpreprocessingandselecttheappropriatedissimilarityorsimilaritymeasure=>Determinetheobjectiveofclusteringandchoosetheappropriatemethod2023/11/4ClusteringLesson8-20ClusteringBasicsDefinitionandMotivationDataPreprocessingandSimilarityComputationObjectiveofClustering（聚类目标）ClusteringEvaluation2023/11/4ClusteringLesson8-21ObjectiveofClusteringConsiderationsforClusterAnalysisPartitioningcriteriaSinglelevelvs.hierarchicalpartitioning(often,multi-levelhierarchicalpartitioningisdesirable)SeparationofclustersExclusive(e.g.,onecustomerbelongstoonlyoneregion)vs.overlapping(e.g.,onedocumentmaybelongtomorethanonetopic)HardversusfuzzyInfuzzyclustering,apointbelongstoeveryclusterwithsomeweightbetween0and1Weightsmustsumto1Probabilisticclusteringhassimilarcharacteristics

2023/11/4ClusteringLesson8-22ObjectiveofClusteringConsiderationsforClusterAnalysisRequirementsofClusteringScalabilityAbilitytodealwithdifferenttypesofattributesMinimalrequirementsfordomainknowledgetodetermineinputparametersAbletodealwithnoiseandoutliersDiscoveryofclusterswitharbitraryshapeInsensitivetoorderofinputrecordsHighdimensionalityIncorporationofuser-specifiedconstraintsInterpretabilityandusability

2023/11/4ClusteringLesson8-23ObjectiveofClusteringConsiderationsforClusterAnalysisRequirementsofClusteringNotionofaClustercanbeAmbiguous

2023/11/4ClusteringLesson8-24ObjectiveofClusteringConsiderationsforClusterAnalysisRequirementsofClusteringNotionofaClustercanbeAmbiguousTypesofClustersCenter-based

Aclusterisasetofobjectssuchthatanobjectinaclusteriscloser(moresimilar)tothe“center”ofacluster,thantothecenterofanyotherclusterThecenterofaclusterisoftenacentroid,theaverageofallthepointsinthecluster,oramedoid,themost“representative”pointofacluster2023/11/4ClusteringLesson8-25ObjectiveofClusteringConsiderationsforClusterAnalysisRequirementsofClusteringNotionofaClustercanbeAmbiguousTypesofClustersCenter-based

Density-basedAclusterisadenseregionofpoints,whichisseparatedbylow-densityregions,fromotherregionsofhighdensity.Usedwhentheclustersareirregularorintertwined,andwhennoiseandoutliersarepresent.2023/11/4ClusteringLesson8-26ClusteringBasicsDefinitionandMotivationDataPreprocessingandSimilarityComputationObjectiveofClusteringClusteringEvaluation（聚类评价）2023/11/4ClusteringLesson8-27ClusteringEvaluationClustervalidationQuality:“goodness”ofclustersAssessthequalityandreliabilityofclusteringresultsWhyvalidation?ToavoidfindingclustersformedbychanceTocompareclusteringalgorithmsTochooseclusteringparameterse.g.,thenumberofclusters2023/11/4ClusteringLesson8-28ClusteringEvaluationAspectsofClusterValidation

Comparingtheclusteringresultstogroundtruth(externallyknownresults)–ExternalIndex（外部指标）Evaluatingthequalityofclusterswithoutreferencetoexternalinformation–Useonlythedata–InternalIndex（内部指标）Determiningthereliabilityofclusters–Towhatconfidencelevel,theclustersarenotformedbychance–Statisticalframework2023/11/4ClusteringLesson8-29ClusteringEvaluationComparingtoGroundTruth（与真值比较）NotationN:numberofobjectsinthedatasetP={P1,…,Ps}:thesetof“groundtruth”clustersC={C1,…,Ct}:thesetofclustersreportedbyaclusteringalgorithmThe“incidencematrix”(关联矩阵)NbyN(bothrowsandcolumnscorrespondtoobjects)Pij=1

ifOiandOjbelongtothesame“groundtruth”clusterinP;Pij=0otherwise

Cij=1ifOiandOjbelongtothesameclusterinC;Cij=0otherwise2023/11/4ClusteringLesson8-30ClusteringEvaluationComparingtoGroundTruthNotationThe“incidencematrix”(关联矩阵)RandIndexandJaccardCoefficientApairofdataobject(Oi,Oj)fallsintooneofthefollowingcategoriesSS:Cij=1andPij=1;(agree)DD:Cij=0andPij=0;(agree)SD:Cij=1andPij=0;(disagree)DS:Cij=0andPij=1;(disagree)2023/11/4ClusteringLesson8-31ClusteringEvaluationComparingtoGroundTruthNotationThe“incidencematrix”(关联矩阵)RandIndexandJaccardCoefficientEntropyandPuritythenumberofobjectsinboththek-thclusteroftheclusteringsolutionandj-thclusterofthegroundtruththenumberofobjectsinthek-thclusteroftheclusteringsolutionthenumberofobjectsinthej-thclusterofthegroundtruth2023/11/4ClusteringLesson8-32ClusteringEvaluationComparingtoGroundTruthInternalIndex（内部指标）UseonlythedatatomeasureclusterqualityMeasurethe“cohesion”and“separation”ofclustersCalculatethecorrelationbetweenclusteringresultsanddistancematrix2023/11/4ClusteringLesson8-33ClusteringEvaluationComparingtoGroundTruthInternalIndexCohesionandSeparationCohesionismeasuredbythewithinclustersumofsquaresSeparationismeasuredbythebetweenclustersumofsquares2023/11/4ClusteringLesson8-34ClusteringEvaluationComparingtoGroundTruthInternalIndexCohesionandSeparationCohesionismeasuredbythewithinclustersumofsquaresSeparationismeasuredbythebetweenclustersumofsquaresBSS+WSS=constantWSS(Cohesion)measureiscalledSumofSquaredError(SSE)—acommonlyusedmeasureAlargernumberofclusterstendtoresultinsmallerSSE2023/11/4ClusteringLesson8-35ClusteringEvaluationComparingtoGroundTruthInternalIndexCohesionandSeparationSilhouetteCoefficient(轮廓系数)SilhouetteCoefficientcombinesideasofbothcohesionandseparation.Foranindividualpoint,iCalculatea=averagedistanceofitothepointsinitsclusterCalculateb=min(averagedistanceofitopointsinanothercluster)Thesilhouettecoefficientforapointisthengivenbys=1–a/bifa<b,(s=b/a-1ifa>b,nottheusualcase)Typicallybetween0and1Thecloserto1thebetterCancalculatetheAverageSilhouettewidthforaclusteroraclustering2023/11/4ClusteringLesson8-36ClusteringEvaluationComparingtoGroundTruthInternalIndex（内部指标）CohesionandSeparation

SilhouetteCoefficient(轮廓系数)CorrelationwithDistanceMatrixDistanceMatrixDijisthesimilaritybetweenobjectOiandOjIncidenceMatrixCij=1ifOiandOjbelongtothesamecluster,Cij=0otherwise

ComputethecorrelationbetweenthetwomatricesOnlyn(n-1)/2entriesneedstobecalculatedHighcorrelationindicatesgoodclustering2023/11/4ClusteringLesson8-37ClusteringEvaluationComparingtoGroundTruthInternalIndexCohesionandSeparation

SilhouetteCoefficient(轮廓系数)CorrelationwithDistanceMatrixGivenDistanceMatrixD={d11,d12,…,dnn}andIncidenceMatrixC={c11,c12,…,cnn}.CorrelationrbetweenDandCisgivenby2023/11/4ClusteringLesson8-38ClusteringEvaluationComparingtoGroundTruthInternalIndexCohesionandSeparation

SilhouetteCoefficient(轮廓系数)CorrelationwithDistanceMatrixUsingSimilarityMatrixforClusterValidation

Orderthesimilaritymatrixwithrespecttoclusterlabelsandinspectvisually.2023/11/4ClusteringLesson8-39ClusteringEvaluationComparingtoGroundTruthInternalIndexReliabilityofClustersNeedaframeworktointerpretanymeasure–Forexample,ifourmeasureofevaluationhasthevalue,10,isthatgood,fair,orpoor?StatisticsprovideaframeworkforclustervalidityThemore“atypical”aclusteringresultis,themorelikelyitrepresentsvalidstructureinthedata

2023/11/4ClusteringLesson8-40ClusteringEvaluationComparingtoGroundTruthInternalIndexReliabilityofClustersStatisticalFrameworkforSSEExampleCompareSSEof0.005againstthreeclustersinrandomdataSSEHistogramof500setsofrandomdatapointsofsize100—lowestSSEis0.01732023/11/4ClusteringLesson8-41ClusteringEvaluationComparingtoGroundTruthInternalIndexReliabil