FAFU机器学习 09-1lusteringasics中文

机器学习基础聚类基础（）2020/12/3集群第8-1课集群基础定义和动机（）数据预处理和相似度计算聚类目标聚类评价2020/12/3集群第8-2课集群基础定义和动机寻找一组对象，使得一组中的对象彼此相似（或相关），而与其他组中的对象不同（或无关）2020/12/3集群第8-3课集群基础定义和动机一个独立的工具:探索数据分发其它算法的预处理步骤模式识别，空间数据分析，图像处理，市场研究，万维网，……群集文档群集web日志数据以发现相似访问模式的组聚类共表达基因市场营销:帮助营销人员在他们的客户群中发现截然不同的群体，然后利用这些知识来制定有针对性的营销方案气候:了解地球气候，发现大气和海洋的模式2020/12/3集群第8-4课集群基础定义和动机一个独立的工具:探索数据分发其它算法的预处理步骤模式识别，空间数据分析，图像处理，市场研究，万维网，…两个重要方面输入数据的属性定义点之间的相似或相异聚类要求确定目标和方法2020/12/3集群第8-5课集群基础定义和动机数据预处理与相似性计算（）聚类目标聚类评价2020/12/3集群第8-6课数据预处理和相似度计算数据:数据对象及其属性的集合属性是一个对象的属性或特征例如:一个人的眼睛颜色，温度等属性也称为维度，变量，字段，特性或特征属性的集合描述一个对象对象也称为记录，点，事例，样本，实体或实例2020/12/3集群第8-7课数据预处理和相似度计算数据矩阵（）表示n个具有p个变量的对象2020/12/3集群第8-8课数据预处理和相似度计算相似与相异相似性两个数据对象相似程度的数值度量当物体更相似时，会更高通常落在[0，1]范围内相异两个数据对象差异的数值度量物体更相似时更低最小相异度通常为0上限各不相同2020/12/3集群第8-9课数据预处理与相似度计算DistanceMatrix（距离矩阵）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,disEuclideandistance欧几里德距离Ifq=1,disManhattandistance曼哈顿距离2023/11/4ClusteringLesson8-14DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributes

MinkowskiDistance—ContinuousAttributeStandardizationCalculatethemeanabsolutedeviationCalculatethestandardizedmeasurement(z-score)2023/11/4ClusteringLesson8-15DataPreprocessingandSimilarityComputationSimilarity/DissimilarityforSimpleAttributesMinkowskiDistance—ContinuousAttributeStandardizationMahalanobisDistance马氏距离具有相同分布的两个随机向量x和y与协方差矩阵S的相异测度。

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进行预处理，选择合适的相似性或相似性度量=>Determinetheobjectiveofclusteringandchoosetheappropriatemethod确定聚类目标，选择合适的聚类方法2023/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-24ObjectiveofClusteringConsiderationsforClusterAnalysisRequirementsofClusteringNotionofaClustercanbeAmbiguousTypesofClusters基于中心簇是一组对象，这样簇中的一个对象比任何其他簇的中心更接近（更相似）簇的“中心”星团的中心通常是一个质心，即星团中所有点的平均值，或者是一个星团中最具代表性的点2023/11/4ClusteringLesson8-25ObjectiveofClusteringConsiderationsforClusterAnalysisRequirementsofClusteringNotionofaClustercanbeAmbiguousTypesofClustersCenter-based

Density-based基于密度Aclusterisadenseregionofpoints,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-41ClusteringEvaluationComparingtoGroundTruthInternalIndexReliabilityofClustersStatisticalFrameworkforSSEDeterminetheNumberofClustersUsingSSE2023/11/4ClusteringLesson8-42sklearn.metrics.pairwiseThesklearn.metrics.pairwisesubmoduleimplementsutilitiesto