《相似性概念与聚类分析》由会员分享，可在线阅读，更多相关《相似性概念与聚类分析（56页珍藏版）》请在金锄头文库上搜索。
1、相似性，概念与聚类分析,于剑 北京交通大学计算机学院.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） 概念的内涵
2、： 必要而且充分条件（命题描述, 命题可以是复合命题）概念的外延： 给出论域中符合该概念的所有样例符合排中率（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., v
3、ol. 23, pp. 309314, 2004,相应的机器学习问题(I),已知:既定概念和该既定概念外延的一个有限子集(即: 标定样本)期望: 学习既定概念的内涵定义机器学习:分类, 回归等技术可以归为此类问题, 即所谓的有监督学习,相应的机器学习问题(II),已知: 样本集, 但其中的样本属于哪一个概念未知 (未标定样本)期望:学习出与人类认知相符的概念.最好得到概念的内涵表示, 否则,也希望得到概念的外延子集.机器学习: 聚类分析可以归为此类问题, 无监督学习,本次演讲的重点,如何从未标定的数据集中提取概念, 即聚类分析,Outline,概念的形成（Gestalt Theory）概念的非
4、经典定义聚类分析类的复杂性讨论未来展望,概念的形成,可分为实体类别(natural kinds)与抽象类别( abstract kinds)Max Wertheimer (1923)说: “我站在窗前, 看到的是房屋,树, 天空.” 不可能认到一个一个的像素点这种程度.提出了实体类别的组织原则,概念的形成格式塔理论与样本的概念归属,格式塔学派整体上认识视觉,提供了根据二维数据形成概念的基本依据邻近律相似律连续律封闭律对称律,概念的形成相似律 Law of Similarity,概念的形成Law of proximity邻近律,概念的形成Gestalt 准则的推广性,封闭律, 连续律, 对称律在
5、高维空间的推广挑战性高, 比如对称性:二维与三维不同.相似律和近邻律的推广性受数据空间维数的影响相对较小,因此对于概念的研究来说, 似更为重要. 另外，封闭律, 连续律在概念不重叠和相切的情形下可以由相似律和近邻律来反映,概念“游戏”内包含的对象不包含共有的特性马术， 游泳， 下棋，网球等都属于游戏,概念的非经典定义经典概念的颠覆,Wittgenstein, L. (1958). Philosophical Investigations (G. E. M. Anscombe, Trans.). USA: Blackwell Publishing.,Ludwig Wittgenstein,概念的
6、非经典定义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
7、, 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 concept
8、s,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 approac
9、h 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,概念的非经典定义样本如何归属于某个特定概念,样本归入与之最相似的特定概念,概念，相似性与聚类分析,聚类形
10、成的划分子集内样本具有相当的同质性， 即类内的样本是相似的，不同类之间的样本是不相似如果借用经典概念，聚类分析得到的是概念的一个外延子集由于聚类分析可以发现数据的内蕴结构，即数据自身蕴含的概念， 近年来，聚类分析的应用日益增广,聚类分析聚类算法与使用的概念定义,类原型聚类算法： 紧致型的类样例型聚类算法： 连通型的类经典概念对应的聚类算法,聚类分析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 almo
11、st 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
12、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 clusteringHierarch
13、ical 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, Ru
14、tgers 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 可以统计一致的发现发
15、现高密度类， average linkage和complete linkage 不具有此性质缺点：不能发现不同密度的类受噪音影响特别厉害难点：有一个很难确定的参数， 聚类数或者阈值,聚类分析DBSCAN 算法,算法的思想是寻找具有足够高密度的连通区域划分作为类，而低密度区域的点则作为孤立点。 一个点的密度可以看作所有样本点与此点的相似度之和优点：可以发现任意形状类缺点： 两个参数（密度水平参数，近邻参数）， 难以选择,聚类分析,DBSCAN等算法,(DBSCAN) M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. 1996. A density-ba
16、sed 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),
