FAFU机器学习09-2 Clustering Methods课件

FoundationsofMachineLearning

ClusteringMethods（聚类方法）2023/11/4ClusteringMethodsLesson9-1ClusteringMethodsPartitionalMethods（基于划分的方法），prototype-basedclustering（基于原型的聚类）：K-meansHierarchicalClustering（层次聚类）Density-basedClustering

（密度聚类）2023/11/4ClusteringMethodsLesson9-2K-meansalgorithms（k均值算法）Center-basedAclusterisasetofobjectssuchthatanobjectinaclusteriscloser(moresimilar)tothe“center”ofacluster,thantothecenterofanyotherclusterThecenterofaclusteriscalledcentroidEachpointisassignedtotheclusterwiththeclosestcentroidThenumberofclustersusuallyshouldbespecified2023/11/4ClusteringMethodsLesson9-3K-meansalgorithms基本步骤Partition{x1,…,xn}intoK

clusters（K

ispredefined）InitializationSpecifytheinitialclustercenters(centroids)IterationuntilnochangeForeachobjectxi(ClusterAssignment)CalculatethedistancesbetweenxiandtheKcentroids(Re)assignxitotheclusterwhosecentroidistheclosesttoxiUpdatetheclustercentroidsbasedoncurrentassignment(UpdateClusterCentroid)2023/11/4ClusteringMethodsLesson9-4K-means:Initialization2023/11/4ClusteringMethodsLesson9-5K-meansClustering:ClusterAssignment2023/11/4ClusteringMethodsLesson9-6K-meansClustering:UpdateClusterCentroid2023/11/4ClusteringMethodsLesson9-7SumofSquaredError(SSE)K-means算法的优化目标：误差平方和SupposethecentroidofclusterCi

isui

ForeachobjectxinCi,computethesquarederrorbetweenxandthecentroiduiSumuptheerrorofalltheobjects2023/11/4ClusteringMethodsLesson9-8K-means算法伪代码2023/11/4ClusteringMethodsLesson9-9CommentsontheK-MeansMethodStrengthEfficient:O(tkn),wherenis#objects,kis#clusters,andtis#iterations.Normally,k,t<<nEasytoimplementIssuesNeedtospecifyK,thenumberofclustersLocalminimum–InitializationmattersEmptyclustersmayappear2023/11/4ClusteringMethodsLesson9-10Pre-processingandPost-processingPre-processingNormalizethedataEliminateoutliersPost-processingEliminatesmallclustersthatmayrepresentoutliersSplit‘loose’clusters,i.e.,clusterswithrelativelyhighSSEMergeclustersthatare‘close’andthathaverelativelylowSSE2023/11/4ClusteringMethodsLesson9-11VariationsoftheK-MeansMethodMostofthevariantsoftheK-meanswhichdifferinDissimilaritycalculationsStrategiestocalculateclustermeansTwoimportantissuesofK-meansSensitivetonoisydataandoutliersK-medoidsalgorithmApplicableonlytoobjectsinacontinuousmulti-dimensionalspaceUsingtheK-modesmethodforcategoricaldata2023/11/4ClusteringMethodsLesson9-12LimitationsofK-meansK-meanshasproblemswhenclustersareofdifferingSizesDensitiesIrregularshapes2023/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.Theal