Lecture-14-Other-methods-机器学习概论-教学课件.ppt

《Lecture-14-Other-methods-机器学习概论-教学课件.ppt》由会员分享，可在线阅读，更多相关《Lecture-14-Other-methods-机器学习概论-教学课件.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Lecture 14:Other Methods and Evaluation25 五月 2023回顾划分聚类方法n问题描述n给定对象集合D，聚类数目k和目标函数F。划分聚类算法把D分割成k组，使得目标函数在这样的分割下达到最优。n聚类极值问题n基本算法nK-means nBisecting K-meansnFuzzy C-meansn每个样本属于所有聚类，只不过是隶属力度有所不同而已。max F回顾层次聚类方法n凝聚模式 n聚类初始时把每个点（样本）作为一个聚类，在随后的处理过程中，把最相似的两个聚类组合成一个新的聚类。n分裂模式n聚类初始时把所有点作为一个大的聚类，在随后的处理中，根据分裂

2、的准则不断地分解聚类。凝聚分裂回顾层次凝聚聚类算法(HAC)nHierarchical Agglomerative Clusteringn使用最为广泛的层次聚类算法n算法基本思想1.Compute the proximity matrix2.Let each data point be a cluster3.Repeat4.Merge the two closest clusters5.Update the proximity matrix6.Until only a single cluster remains n关键操作是计算两个聚类的相似性n不同算法采用不同的定义。基于密度的聚类方法nD

3、ensity-Based Clustering Methodsn按照密度进行聚类（如密度相连）n主要特点：n发现任意形状的聚类n能处理噪音n仅需扫描一次数据集n需要设定密度参数作为终止条件n相关算法nDBSCAN:Ester,et al.(KDD96)nOPTICS:Ankerst,et al(SIGMOD99).nDENCLUE:Hinneburg&D.Keim (KDD98)nCLIQUE:Agrawal,et al.(SIGMOD98)基于密度的方法：基本概念n两个参数nEps:邻居关系的最大半径nMinPts:以某个对象为中心，以Eps为半径的超球体中其它对象的最少数目nNEps(p)

4、:q belongs to D|dist(p,q)=Epsn核心对象（核心对象（Core ObjectCore Object）n给定Eps和MinPts，若对象p的Eps邻域NEps(p)包含的对象个数|N(p)|MinPts，则称p为核心对象n直接密度可达(Directly density-reachable)n给定的Eps和MinPts，称p是从 q直接密度可达的，如果满足：np NEps(q)nq是核心对象pqMinPts=5Eps=1 cm基于密度的方法：基本概念n密度可达(Density-reachable)n称p 是从q 密度可达的，如果存在一系列的点p1,pn,p1=q,pn=p

5、 并且pi+1 是从pi直接密度可达的。n密度相连(Density-connected)n称p 到q 是密度相连的，如果存在o，p 和q 都是从o 密度可达的。pqp2pqo核心对象、边界对象和噪音DBSCAN算法描述nArbitrary select a point pnIf p is a core point,a cluster is formed.nRetrieve all points density-connected from p w.r.t.Eps and MinPts.nIf p is not a core point,no points are density-reachab

6、le from p and DBSCAN visits the next point of the database.nContinue the process until all of the points have been processed.DBSCAN局限Original Points 密度变化很大密度变化很大 高维数据高维数据(MinPts=4,Eps=9.92)(MinPts=4,Eps=9.75).基于网格的聚类方法nGrid-Based Clustering Methodn利用multi-resolution网格数据结构n相关算法nSTING(a STatistical IN

7、formation Grid approach)by Wang,Yang and Muntz(1997)nWaveCluster by Sheikholeslami,Chatterjee,and Zhang(VLDB98)n采用了小波技术nClique:Agrawal,et al.(SIGMOD98)n能有效处理高维数据基于网格的聚类方法基本思想Clique 算法描述Salary(10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacationSalary3050Clique 算法：小结n优点 n能自动发现高维

8、空间中包含聚类（高密度的点）的子空间。n与处理数据的顺序无关，对数据不要求符合某种规范分布。n缺点n时间复杂度是维度的指数n特别是在低维空间产生“太多”的稠密单元时，算法效率将变得很差。n如果不同聚类的密度分布不同，那么聚类的效果就会差。因为采用统一的密度阈值。n设定合适的阈值和单元间隔长度是一项具有挑战性的工作。基于模型的聚类方法nModel-Based Clusteringn最优化某个数学模型，使得给定的数据能最好地与该模型相符。n基于如下假定：数据的生成是由某个混合概率分布模型所决定。n典型算法n概率统计学习方法nEM(Expectation maximization)n神经网络方法nS

9、OM(Self-Organizing Feature Map)概率统计方法：An Examplen考虑下图中数据n很像两个正态分布的组合n假定我们能估计出每个正态分布的均值和标准方差，那么：n实际上这两个正态分布函数描述了两个聚类n我们可以计算每个点属于每个聚类（正态分布）的概率。n对任意一点P，P所属于的聚类为其中概率最大的。n该正态分布模型最有可能产生点P。EM 算法 Nave Bayes EMnExpectation stepn估计对象Xi 属于聚类Ci 的概率nMaximization step:n根据E步的聚类结果估计模型参数SOM:Self-Organizing MapsnSelf

10、-organizing mapsn基于聚类中心的策略n如同 K-means，需要指定聚类的数目n同时，还要指定聚类间的空间关系 n一次处理一个对象（点）n每个对象指派到与其最近的聚类中心n其它聚类中心根据它们与上述聚类中心的远近程度进行修改。SOM：算法描述nSOM在低维度上对数据进行聚类n如果采用两维网格，SOM聚类的结果可以可视化显示n注意：一次不只修改一个聚类中心，对与该聚类中心邻近的聚类中心也要修改；并且采用增量处理的方式（一次处理一个对象）基于图的聚类方法n基本思想n用邻近图(proximity graph)来表示对象间邻近（相似）关系n每个对象（点）为图中一个结点n两个结点的边有一

11、个权值，该权值表示这两点之间的邻近程度n开始邻近图是全连接的（任何两个结点均有边相连）n设计不同方法对邻近图进行处理，获得聚类。n典型方法nCHAMELEONnSNNCHAMELEON聚类算法n基于动态模型度量相似性n合并两个聚类，如果这两个聚类的interconnectivity 和closeness(proximity)超出一定阈值 nA two-phase algorithm1.Use a graph partitioning algorithm:cluster objects into a large number of relatively small sub-clusters2.U

12、se an agglomerative hierarchical clustering algorithm:find the genuine clusters by repeatedly combining these sub-clustersFor details,Please refer toG.Karypis,E.H.Han,and V.Kumar.CHAMELEON:Hierarchical Clustering Using Dynamic Modeling.COMPUTER,32:68-75,1999 CHAMELEON聚类复杂对象ijij4SNN 方法简介n基本概念nShared

13、Nearest Neighbor(SNN)graphn边的权值为两个顶点共享邻居的数目JP(Jarvis-Patrick)聚类算法n一个简单的SNN算法nIdea:nFirst,the k-nearest neighbors of all points are found nIn graph terms this can be regarded as breaking all but the k strongest links from a point to other points in the proximity graphnA pair of points is put in the s

14、ame cluster if nany two points share more than t neighbors and nthe two points are in each others k nearest neighbor listn例如，选择 k 20 and t 10JP算法An Example原始点集原始点集JP聚类结果聚类结果其中 k 20，t 6基于密度的SNN聚类算法n合并n基于图的聚类(如JP算法，基于共享邻居来定义相似度)n基于密度的聚类(DBScan-like)nSNN密度(density)n度量一个点由相似点（按照最近邻居）包围的程度。SNN 聚类算法1.Comp

15、ute the similarity matrixThis corresponds to a similarity graph with data points for nodes and edges whose weights are the similarities between data points2.Sparsify the similarity matrix by keeping only the k most similar neighborsThis corresponds to only keeping the k strongest links of the simila

16、rity graph3.Construct the shared nearest neighbor graph from the sparsified similarity matrix.At this point,we could apply a similarity threshold and find the connected components to obtain the clusters(Jarvis-Patrick algorithm)4.Find the SNN density of each Point.Using a user specified parameters,E

17、ps,find the number points that have an SNN similarity of Eps or greater to each point.This is the SNN density of the pointSNN 聚类算法5.Find the core pointsUsing a user specified parameter,MinPts,find the core points,i.e.,all points that have an SNN density greater than MinPts6.Form clusters from the co

18、re points If two core points are within a“radius”,Eps,of each other they are place in the same cluster7.Discard all noise pointsAll non-core points that are not within a“radius”of Eps of a core point are discarded 8.Assign all non-noise,non-core points to clusters This can be done by assigning such

19、points to the nearest core point注意：48步基本上同DBSCANSNN密度设置 a)All Points b)High SNN Densityc)Medium SNN Density d)Low SNN DensitySNN聚类不同密度Original PointsSNN ClusteringSNN 聚类其它例子聚类分析总结n聚类分析受以下因素影响 n数据特性n聚类特性n聚类算法特性n维度n数据集大小n属性值的稀疏程度nNoise and Outliersn属性类型和数据类型n属性间的不同度量尺度 n数据空间特性n如何定义一个有意义的聚类中心数据n数据分布n形状

20、n大小差异度n密度差异度n可分性n聚类间关系 n子空间聚类聚类特性n顺序相关n参数选择n可扩展性（能否有效处理大数据集）n假定的模型n最优化的方法算法特性n都是对数据集进行分割。nK-means是完全分割；DBSCAN不是（噪音不属于任何聚类）。nK-means偏向球形聚类，而DBSCAN能处理不同形状和大小的聚类。nDBSCAN 能处理噪音和异常点；而K-means在出现噪音和异常点是聚类效果差。n在聚类中心有意义的情况下可应用K-means；而DBSCAN要求密度的定义要有意义。nDBSCAN在处理高维数据时，效率比较差；而对某些类型的高维数据，K-means效率很好。nDBSCAN对数据

21、分布没有任何假定；而 K-means隐含假定数据服从球状高斯分布。An Example:-DBSCAN VS K-means聚类质量评估n内在质量标准ninternal quality measuren无类别标注的测试集n典型nOS(Overall Similarity)nQE(Quantization Error)nMDE(Maximum Distance Error)n外在质量标准nexternal quality measuren有类别标注的测试集nEntropynF标准OS nj是聚类j中对象数目n是对象数目QEMDE熵(Entropy)pij是聚类j中对象属于类i的概率 nj是聚类j中对象数目n是对象数目F标准nij是既属于聚类j中又属于类i的对象数目ni是类i中对象数目nj是聚类j对象档数目n是对象数目外在质量标准计算例子n计算：熵和F标准C1 C2C3 CL11101CL21522CL32020CL40152CL52325聚类真实类下一讲nAssociation Rules AnalysisSee you next time