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

机器学习及其应用2009, 南京大学 相似性，概念与聚类分析 于剑 北京交通大学计算机学院. Email: 机器学习的目的之一：概念 o人们学习的目的是学习知识, 因此, 机器学 习的一个自然期望是： 从数据中学习到知 识 o什么是知识的最基本单位： 概念 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 o经典概念的定义：（Plato and Aristotle） o概念的内涵： 必要而且充分条件（命题描述, 命题 可以是复合命题） o概念的外延： 给出论域中符合该概念的所有样例 o符合排中率（law of the excluded middle） o要么符合这个概念，要么不符合这个概念 o这种经典的概念形式称为定义法 什么是概念？ 概念与数据分析 o数据分析的一个重要的应用就是 从数据中学习到概念(语义). 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) o已知:既定概念和该既定概念外延的一 个有限子集(即: 标定样本) o期望: 学习既定概念的内涵定义 o机器学习:分类, 回归等技术可以归为 此类问题, 即所谓的有监督学习 相应的机器学习问题(II) o已知: 样本集, 但其中的样本属于哪一个概 念未知 (未标定样本) o期望:学习出与人类认知相符的概念.最好得 到概念的内涵表示, 否则,也希望得到概念的 外延子集. o机器学习: 聚类分析可以归为此类问题, 无 监督学习 本次演讲的重点 o如何从未标定的数据集中提取概 念, 即聚类分析 Outline o概念的形成（Gestalt Theory） o概念的非经典定义 o聚类分析 o类的复杂性讨论 o未来展望 概念的形成 o可分为实体类别(natural kinds) 与抽象类别( abstract kinds) oMax Wertheimer (1923)说: o“我站在窗前, 看到的是房屋,树, 天空.” 不可能认到一个一个的 像素点这种程度. o提出了实体类别的组织原则 概念的形成 格式塔理论与样本的概念归属 o格式塔学派整体上认识视觉,提供了根 据二维数据形成概念的基本依据 n邻近律 n相似律 n连续律 n封闭律 n对称律 概念的形成 相似律 Law of Similarity 概念的形成 Law of proximity邻近律 概念的形成 Gestalt 准则的推广性 o封闭律, 连续律, 对称律在高维空间的推广 挑战性高, 比如对称性:二维与三维不同. o相似律和近邻律的推广性受数据空间维数的 影响相对较小,因此对于概念的研究来说, 似 更为重要. o另外，封闭律, 连续律在概念不重叠和相切 的情形下可以由相似律和近邻律来反映 o概念“游戏”内包含的对象 不包含共有的特性 马术， 游泳， 下棋，网球等 都属于游戏 概念的非经典定义 经典概念的颠覆 Wittgenstein, L. (1958). Philosophical Investigations (G. E. M. Anscombe, Trans.). USA: Blackwell Publishing. Ludwig Wittgenstein 概念的非经典定义 Eleanor Roschs 的发现 o上个世纪70年代,Eleanor Rosch 的工作在 认知科学领域彻底终结了经典概念的定义- “The big book of concepts”, written by M.L. Murphy, 2002, MIT o典型样本与非典型样本 概念的非经典定义 Examples of items studied by Rosch Norman R. Draper (1987). Empirical Model-Building and Response Surfaces. Wiley. pp. p. 424. ISBN 0471810339 o“there is no single clustering algorithm that has been shown to dominate other algorithms across all application domains” A.K. Jain, 2009, PRL, 2009 相似性的二值表示 o一个是在得到相似性得到以后，如何判断对 象与类别之间的关系。 o一般假设相似性与一个理想相似性是一一对 应的. o所谓的理想相似性是指其值与0或者1很接近 os(i,k)=e(i,k)+(i,k), 其中， e(i,k)取值 为0或者1 相似性的二值表示定理 Texas clustering(Yu, Hao and Zhou)