相似性概念与聚类分析.ppt

相似性，概念与聚类分析,于剑 北京交通大学计算机学院.Email:,机器学习的目的之一：概念,人们学习的目的是学习知识,因此,机器学习的一个自然期望是：从数据中学习到知识什么是知识的最基本单位：概念,Concepts are the glue that holds our mental world together。Cited from page 1 in the book entiled“The big book of concepts”,written by M.L.Murphy,2002,MIT,经典概念的定义：（Plato and Aristotle）概念的内涵：必要而且充分条件（命题描述,命题可以是复合命题）概念的外延：给出论域中符合该概念的所有样例符合排中率（law of the excluded middle）要么符合这个概念，要么不符合这个概念这种经典的概念形式称为定义法,什么是概念？,概念与数据分析,数据分析的一个重要的应用就是从数据中学习到概念(语义).,Cited from C.Rother,V.Kolmogorov,and A.Blake,GrabCut:Interactive foreground extraction using iterated graph cuts,ACM Trans.Graph.,vol.23,pp.309314,2004,相应的机器学习问题(I),已知:既定概念和该既定概念外延的一个有限子集(即:标定样本)期望:学习既定概念的内涵定义机器学习:分类,回归等技术可以归为此类问题,即所谓的有监督学习,相应的机器学习问题(II),已知:样本集,但其中的样本属于哪一个概念未知(未标定样本)期望:学习出与人类认知相符的概念.最好得到概念的内涵表示,否则,也希望得到概念的外延子集.机器学习:聚类分析可以归为此类问题,无监督学习,本次演讲的重点,如何从未标定的数据集中提取概念,即聚类分析,Outline,概念的形成（Gestalt Theory）概念的非经典定义聚类分析类的复杂性讨论未来展望,概念的形成,可分为实体类别(natural kinds)与抽象类别(abstract kinds)Max Wertheimer(1923)说:“我站在窗前,看到的是房屋,树,天空.”不可能认到一个一个的像素点这种程度.提出了实体类别的组织原则,概念的形成格式塔理论与样本的概念归属,格式塔学派整体上认识视觉,提供了根据二维数据形成概念的基本依据邻近律相似律连续律封闭律对称律,概念的形成相似律 Law of Similarity,概念的形成Law of proximity邻近律,概念的形成Gestalt 准则的推广性,封闭律,连续律,对称律在高维空间的推广挑战性高,比如对称性:二维与三维不同.相似律和近邻律的推广性受数据空间维数的影响相对较小,因此对于概念的研究来说,似更为重要.另外，封闭律,连续律在概念不重叠和相切的情形下可以由相似律和近邻律来反映,概念“游戏”内包含的对象不包含共有的特性马术，游泳，下棋，网球等都属于游戏,概念的非经典定义经典概念的颠覆,Wittgenstein,L.(1958).Philosophical Investigations(G.E.M.Anscombe,Trans.).USA:Blackwell Publishing.,Ludwig Wittgenstein,概念的非经典定义Eleanor Roschs 的发现,上个世纪70年代,Eleanor Rosch 的工作在认知科学领域彻底终结了经典概念的定义-“The big book of concepts”,written by M.L.Murphy,2002,MIT典型样本与非典型样本,概念的非经典定义Examples of items studied by Rosch&Mervis(1975),ordered by typicality,Fruit:orange,apple,banana,peach,pear,apricot,plum,grapes,strawberry,grapefruit,pineapple,blueberry,lemon,watermelon,honeydew,pomegranate,date,coconut,tomato,oliveFurniture:chair,sofa,table,dresser,desk,bed,bookcase,footstool,lamp,piano,cushion,mirror,rug,radio,stove,clock,picture,closet,vase,telephone,概念的非经典定义Prototype view of concepts,A single prototype as a category representation It avoids the contradictable features A feature list as a category representationIt is not popular as computational complexity,概念的非经典定义Exemplar view of concepts(Medin and Schaffer,1978),Concepts by represented by exemplars,概念的非经典定义Knowledge approach of concepts,Concepts can be considered a part of general knowledgegoal-derived categories(Barsalou,1985)things to eat on a diet,things to take from ones house during a fireIts limitation:Much of a concept cannot be based on previous knowledge,概念的非经典定义样本如何归属于某个特定概念,样本归入与之最相似的特定概念,概念，相似性与聚类分析,聚类形成的划分子集内样本具有相当的同质性，即类内的样本是相似的，不同类之间的样本是不相似如果借用经典概念，聚类分析得到的是概念的一个外延子集由于聚类分析可以发现数据的内蕴结构，即数据自身蕴含的概念，近年来，聚类分析的应用日益增广,聚类分析聚类算法与使用的概念定义,类原型聚类算法：紧致型的类样例型聚类算法：连通型的类经典概念对应的聚类算法,聚类分析Prototype based clustering:C(K)-MEANS,Remark:The essence of K-means is the same as that of C-means.LBG or GLA also has almost the same meaning as K-means,聚类分析K-means and its extensions,Fuzzy C-means EM type clustering Deterministic annealing clusteringFuzzy c-shellsK-modePCMConditional fuzzy c-meansGCM(Yu Jian,2005),聚类分析Prototype based clustering,Usually use dissimilarity to represent similarity,therefore ignore the step of computing similarityTheir advantages are as follows:fast speed,and good interpretation,can easily deal with touching clusters or overlapping clusters when prototypes are proper,聚类分析Exemplar based clustering,Additive clusteringAffinity PropagationMinimum cut and Spectral clusteringHierarchical clusteringMinimum Spanning treeDBSCANQT(Quality Threshold）,聚类分析Affinity Propagation(Frey&Dueck,2007),聚类分析Minimum cut,聚类分析Normalized Cut(Shi and Malik,2000),Subject to the constraints:y(i)1,-bytD1=0,聚类分析Minimum Cut,最小切聚类算法（minimum cut），,Ahmed Elgammal,Graph Cuts and Image Segmentation,Rutgers University,Jianbo Shi and Jitendra Malik“Normalized Cuts and ImageSegmetnation”IEEE Transactions on Pattern Analysis and MachineIntelligence,Vol 22 No.0,August 2000,聚类分析Single Linkage,聚类分析Single linkage的优缺点,优点：Single Linkage:J.Haritgan(1981,JASA,76(374)证明了只有Single linkage 可以统计一致的发现发现高密度类，average linkage和complete linkage 不具有此性质缺点：不能发现不同密度的类受噪音影响特别厉害难点：有一个很难确定的参数，聚类数或者阈值,聚类分析DBSCAN 算法,算法的思想是寻找具有足够高密度的连通区域划分作为类，而低密度区域的点则作为孤立点。一个点的密度可以看作所有样本点与此点的相似度之和优点：可以发现任意形状类缺点：两个参数（密度水平参数，近邻参数），难以选择,聚类分析,DBSCAN等算法,(DBSCAN)M.Ester,H.-P.Kriegel,J.Sander,and X.Xu.1996.A density-based algorithm for discovering clusters in large spatial databases.KDD96,聚类分析QT clustering,QT(Quality Threshold)聚类算法是通过限定类的直径来聚类的。主要思想是：如果定义了相异矩阵对应的图，类的直径应该不大于给定的阈值。因此，其流程如下：选定一个样本，逐渐合并与其最相似的样本，直到再增加样本将导致类的直径超过给定的阈值为止，然后选定下一个样本，重新聚类。,Heyer,L.J.,et al.“Exploring Expression Data:Identification and Analysis of Coexpressed Genes”.Genome Research,9:1106-1115(1999),聚类分析现存样例型聚类算法的不足,The predefined parameters such as the number of clusters for additive clustering,the preference value and the damping factor for the affinity propagation,the number of clusters for spectral clustering,Threshold for cluster diameterHigh complexity of additive clustering,quality thresholdNo convergence proof of Affinity propagationNo calculation results for Spectral clustering if similarity matrix is not proper,聚类分析对应经典概念的聚类算法,如果经典概念的外延来表示划分，即可以用划分矩阵来表示这样发展出来的算法可以称为划分矩阵型聚类算法。主要有三种技术,聚类分析基于矩阵分解技术,算法的输入是相似矩阵，计算的主要依据是可将相似矩阵分解成划分矩阵的乘积这样的形式，这样的聚类算法有基于非负矩阵分解的聚类算法，以及异质聚类算法中的矩阵分解聚类算法，可加性聚类算法(additive clustering)也可以勉强归为这样的算法,聚类分析基于信息论,算法的输入是概率分布矩阵，文献中的算法有信息瓶颈（information bottleneck）聚类算法，以及异质聚类算法的互信息联合聚类算法等等,聚类分析基于margin 理论,现有的方法有支持向量机聚类算法（support vector clustering）和最大margin聚类算法（maximum margin clustering）,类的复杂性讨论,概念的定义是一个非常难的问题类是什么也一直是聚类分析研究者面对的核心难题,任意形状类(I),任意形状类（II),非同质类,相切类,重叠类,重叠类在图像中的表现,混合类,Cited from Jain,A.:Data clustering:50 years beyond k-means.Pattern Recognition Letters(Available on line 9 Sept.2009),现存聚类算法的优缺点,类原型聚类算法可以处理相切类，重叠类，条件是类原型合适。但是对于任意形状类处理不好连通类聚类算法能够处理弱相切类（但是比较复杂），一般的相切类和重叠类处理不了.,Essentially,all models are wrong,but some are useful.Cited from Box,George E.P.;Norman R.Draper(1987).Empirical Model-Building and Response Surfaces.Wiley.pp.p.424.ISBN 0471810339“there is no single clustering algorithm that has been shown to dominate other algorithms across all application domains”A.K.Jain,2009,PRL,2009,相似性的二值表示,一个是在得到相似性得到以后，如何判断对象与类别之间的关系。一般假设相似性与一个理想相似性是一一对应的.所谓的理想相似性是指其值与0或者1很接近s(i,k)=e(i,k)+(i,k),其中，e(i,k)取值为0或者1,相似性的二值表示定理,Texas clustering(Yu,Hao and Zhou),由此而来,我们得到新的基于 相似度的聚类算法,未来展望,类的表示（概念的表示）数据的表示（特征空间）如何结合领域知识聚类算法：semi-supervised clustering 现有算法的性能客观评估,谢谢.,