FAFU机器学习 09-2lusteringethods中文

机器学习和聚类方法基础（）2020/12/3聚类方法第9-1课聚类方法分区方法（），基于原型的聚类（）:K-均值层次聚类（）基于密度的聚类（）2020/12/3聚类方法第9-2课K均值算法(K)以中心为基础集群是一组对象，使得集群中的一个对象比任何其他集群的中心更接近（更相似）集群的“中心”星团的中心叫做质心每个点被分配到具有最接近质心的聚类中通常应该指定群集的数量2020/12/3聚类方法第9-3课K均值算法将{x1，…，xn}划分为K个簇（K是预定义的）初始化指定初始群集中心（质心）迭代直到没有变化对于每个对象xi（群集分配）计算xi和K个质心之间的距离（重新）将xi分配给质心最接近xi的群集根据当前分配更新群集质心（更新群集质心）2020/12/3聚类方法第9-4课K均值:初始化2020/12/3聚类方法第9-5课K均值聚类:聚类分配2020/12/3聚类方法第9-6课K-means聚类:更新聚类质心2020/12/3聚类方法第9-7课误差平方和(SSE)K-均值:假设集群Ci的质心是UI对于Ci中的每个对象x，计算x和质心UI之间的平方误差求出所有对象的误差2020/12/3聚类方法第9-8课K均值2020/12/3聚类方法第9-9课关于K-均值方法的评述力量效率:O(tkn)，其中n是#个对象，k是#个簇，t是#个迭代。正常情况下，k，t<<n易于实现问题需要指定K，簇的数量局部最小值-初始化问题可能会出现空簇2020/12/3聚类方法第9-10课预处理和后处理预处理归一化数据消除异常值后处理消除可能代表离群值的小聚类拆分“松散”群集，即具有相对较高SSE的群集合并“接近”且SSE相对较低的群集2020/12/3聚类方法第9-11课K-均值法的变体K-均值的大多数变体在相异计算计算聚类均值的策略k-均值的两个重要问题对噪声数据和异常值敏感k-中间点算法只适用于连续多维空间中的物体对分类数据采用K-模式方法2020/12/3聚类方法第9-12课K-均值的局限性K-means在聚类不同时存在问题SizesDensitiesIrregularshapes2023/11/4ClusteringMethodsLesson9-13LimitationsofK-meansK-meanshasproblemswhenclustersareofdifferingSizesDensitiesIrregularshapes2023/11/4ClusteringMethodsLesson9-14LimitationsofK-meansK-meanshasproblemswhenclustersareofdifferingSizesDensitiesIrregularshapes2023/11/4ClusteringMethodsLesson9-15ClusteringBasicsPartitionalMethods（基于划分的方法），prototype-basedclustering（基于原型的聚类）：K-meansHierarchicalClustering（层次聚类）Density-basedClustering

（密度聚类）2023/11/4ClusteringMethodsLesson9-16HierarchicalClusteringAgglomerativeapproach(聚合策略)DivisiveApproaches(分拆策略)2023/11/4ClusteringMethodsLesson9-17Dendrogram（树状图）Atreethatshowshowclustersaremerged/splithierarchicallyEachnodeonthetreeisacluster;eachleafnodeisasingletoncluster2023/11/4ClusteringMethodsLesson9-18Dendrogram（树状图）Atreethatshowshowclustersaremerged/splithierarchicallyEachnodeonthetreeisacluster;eachleafnodeisasingletonclusterAclusteringofthedataobjectsisobtainedbycuttingthedendrogramatthedesiredlevel,theneachconnectedcomponentformsacluster2023/11/4ClusteringMethodsLesson9-19HierarchicalClusteringAgglomerativeapproach(聚合策略)AGNES(AGglomerativeNESting)是一种采用自底向上聚合策略的层次聚类算法AGNES工作过程：先将数据集中的每个样本看作一个初始聚类簇；然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并；步骤（2）不断重复，直至达到预设的聚类簇的个数。关键：如何计算聚类簇之间的距离最小距离，最大距离，平均距离2023/11/4ClusteringMethodsLesson9-20HierarchicalClusteringAgglomerativeapproach(聚合策略)AGNES(AGglomerativeNESting)是一种采用自底向上聚合策略的层次聚类算法计算聚类簇之间的距离最小距离最大距离平均距离2023/11/4ClusteringMethodsLesson9-21HierarchicalClusteringAgglomerativeapproach(聚合策略)AGNES(AGglomerativeNESting)是一种采用自底向上聚合策略的层次聚类算法计算聚类簇之间的距离当聚类簇距离为dmin：AGNES算法被称为单链接（single-linkage）；dmax：AGNES算法被称为全链接（complete-linkage）；davg：AGNES算法被称为均链接（average-linkage）2023/11/4ClusteringMethodsLesson9-22AGNES算法描述输入：样本集D;聚类簇距离度量函数dist；聚类簇数k。输出：簇划分

C={C1,C2,...,Ck}为每个样本创建一个簇；计算距离矩阵；开始合并簇过程，初始化聚类簇个数q=n：从距离矩阵中找出距离最近的两个聚类簇Ci和Cj，i<j；合并这两个簇（优先合并到下标较小的簇Ci=Ci⋃Cj)；将聚类簇重新编号（合并到下标较小的簇可以减少重编号的次数）；删除距离矩阵的第j行与第j列；计算新Ci与剩余其他簇之间的距离，更新距离矩阵。q=q-1。直到q==k时，退出循环。返回簇划分。2023/11/4ClusteringMethodsLesson9-23ClusteringBasicsPartitionalMethods（基于划分的方法），prototype-basedclustering（基于原型的聚类）：K-meansHierarchicalClustering（层次聚类）Density-basedClustering（密度聚类）2023/11/4ClusteringMethodsLesson9-24Density-basedClusteringBasicideaClustersaredenseregionsinthedataspace,separatedbyregionsoflowerobjectdensityAclusterisdefinedasamaximalsetofdensity-connectedpointsDiscoversclustersofarbitraryshapeMethodDBSCAN2023/11/4ClusteringMethodsLesson9-25DBSCANDBSCAN是一种著君的密度粟类算法?它基于一组“邻域”(neighborhood)参数（ε,

MinPts）来刻画样本分布的紧密程度。给定数据集D={xl,x2,..,xm}，定义下面这几个概念:ε-Neighborhood(ε-邻域)–Objectswithinaradiusofεfromanobject.Givenε

andMinPts,可以把样本中的点分成三类核心点（corepoint）:Apointisacorepointifithasmorethanaspecifiednumberofpoints(MinPts)withinitsε-Neighborhood.边缘点（borderpoint）：AborderpointhasfewerthanMinPtswithinitsε-Neighborhood,butisintheneighborhoodofacorepoint.离群点（Outlier）：既不是核心点也不是边缘点，则是不属于这一类的点2023/11/4ClusteringMethodsLesson9-26DBSCANDBSCAN是一种著君的密度粟类算法?它基于一组“邻域”(neighborhood)参数（ε,

MinPts）来刻画样本分布的紧密程度。给定数据集D={xl,x2,..,xm}，定义下面这几个概念:ε-Neighborhood(ε-邻域)–Objectswithinaradiusofεfromanobject.Givenε

andMinPts,可以把样本中的点分成核心点（corepoint）、边缘点（borderpoint）和离群点（Outlier）密度直达(directlydensity-reachable)密度可达(density-reachable)密度相连(density-connected)2023/11/4ClusteringMethodsLesson9-27Density-reachabilityDirectlydensity-reachable（密度直达）Anobjectqisdirectlydensity-reachablefromobjectpifpisacoreobjectandqisinp’sε-neighborhood.2023/11/4ClusteringMethodsLesson9-28Density-reachabilityDensity-Reachable（密度可达）(directlyandindirectly):假设存在样本序列q,p1,p2,…,pn,pApointpisdirectlydensity-reachablefrompn

pi+1

isdirectlydensity-reachablefrompip1

isdirectlydensity-reachablefromqq→p1→

p2→…→

pn→

pformachain2023/11/4ClusteringMethodsLesson9-29Density-reachability密度相连（density-connected）：对xi与xj，若存在xk使得xi与xj均由xk密度可达，则称xi与xj密度相连。密度相连关系满足对称性。2023/11/4ClusteringMethodsLesson9-30DBSCAN算法伪代码输入：数据集，邻域半径ε，邻域中数据对象数目阈值MinPts;输出：密度联通簇。从数据集中任意选取一个数据对象点p；如果对于参数ε

和MinPts，所选取的数据对象点p

为核心点，则找出所有从p

密度可达的数据对象点，形成一个簇；如果选取的数据对象点p

是边缘点，选取另一个数据对象点；重复2、3步，直到所有点被处理。DBSCAN算法的计算复杂的度为O(n²)，n为数据对象的数目。这种算法对于输入参数ε

和MinPts

是敏感的。2023/11/4ClusteringMethodsLesson9-31sklearn.cluster:Clusteringcluster.AgglomerativeClusteringAgglomerativeClusteringcluster.DBSCANPerformDBSCANclusteringfromvectorarrayordistancematrix.cluster.KMeansK-Meansclusteringcluster.MiniBatchKMeansMini-BatchK-Meansclusteringcluster.SpectralClusteringApplyclusteringtoaprojectiontothenormalizedlaplacian.cluster.WardWardhierarchicalclustering:constructsatreeandcutsit.2023/11/4ClusteringMethodsLesson9-32classsklearn.cluster.KMeans(n_clusters=8,init='k-means++',n_init=10,max_iter=300,tol=0.0001,precompute_distances=True,verbose=0,random_state=None,copy_x=True,n_jobs=1)n_clusters:int,optional,default:8Thenumberofclusterstoformaswellasthenumberofcentroidstogenerate.n_init:int,default:10Numberoftimethek-meansalgorithmwillberunwithdifferentcentroidseeds.Thefinalresultswillbethebestoutputofn_initconsecutiverunsintermsofinertia.init:{‘k-means++’,‘random’oranndarray}Methodforinitialization,defaultsto‘k-means++’:2023/11/4ClusteringMethodsLesson9-33classsklearn.cluster.AgglomerativeClustering(n_clusters=2,affinity='euclidean',memory=Memory(cachedir=None),connectivity=None,n_components=None,compute_full_tree='auto',linkage='ward',pooling_func=<functionmeanat0x2b3eef778320>)linkage:{“ward”,“complete”,“average”},optional,default:“ward”Whichlinkagecriteriontouse.Thelinkagecriteriondetermineswhichdistancetousebetweensetsofobservation.Thealgorithmwillmergethepairsofclusterthatminimizethiscriterion.wardminimizesthevarianceoftheclustersbeingmerged.averageusestheaverageofthedistancesofeachobservationofthe