《先进模式识别(ii)聚类分析和弱监督学习》由会员分享，可在线阅读，更多相关《先进模式识别(ii)聚类分析和弱监督学习（78页珍藏版）》请在金锄头文库上搜索。
1、聚类分析 聚类和聚类分析 聚类：是将数据分类到不同的类或者簇(Cluster)的过程， 使得同一个簇中的对象具有最大的相似性，不同簇间的对 象具有最大的相异性。 Connectivity based clustering Centroid-based clustering Distribution-based clustering Graph-based clustering 最小割(mincut) Normalized Cut MinCut算法在实践应用中很容易造成将单个样本划分为一 个子集的现象。 Normalized Cut Normalized Cut 相似图和邻接矩阵 相似图： 邻接
2、矩阵 ： 谱聚类算法 谱聚类示例 样本 (0,0), (0,1), (1, 0), (1,1), (0,10), (0,11), (1, 10), (1,11), (10,0), (10,1), (11, 0), (11,1), (10,10), (10,11), (11, 10), (11,11) 特征值： 最大4个特征值对应的特征矢量： 0.0000 0.0008 0.0008 0.0015 3.4477 3.4477 3.4477 3.4477 3.4481 3.4481 3.4481 3.4481 3.6201 3.6201 3.6201 3.6201 -0.2500+0.0431+0
3、.3510+0.2501 -0.2500+0.0432+0.3509+0.2500 -0.2500+0.0431+0.3509+0.2500 -0.2500+0.0431+0.3509+0.2499 -0.2500+0.3509-0.0431-0.2500 -0.2500+0.3510-0.0431-0.2501 -0.2500+0.3509-0.0431-0.2499 -0.2500+0.3509-0.0432-0.2500 -0.2500-0.3509+0.0432-0.2500 -0.2500-0.3509+0.0431-0.2499 -0.2500-0.3510+0.0431-0.25
4、01 -0.2500-0.3509+0.0431-0.2500 -0.2500-0.0431-0.3509+0.2499 -0.2500-0.0431-0.3509+0.2500 -0.2500-0.0432-0.3509+0.2500 -0.2500-0.0431-0.3510+0.2501 谱聚类示例 原样本分布 K均值聚类 特征值矩阵的行矢量 Laplacian矩阵的性质 Laplacian矩阵的性质 RatioCut的近似谱求解: k=2 RatioCut的近似谱求解: k=2 f与矢量1正交: 即: f的长度平方为n: RatioCut的优化问题 严格的优化问题: 约束: 仍然是一个
5、NP问题。 近似的RatioCut的优化问题 近似的优化问题：放松对f中元素的离散性约束 问题的解: 对应L第2小特征值的特征矢量 证明: 1.不考虑正交约束，问题变成Rayleigh商的优化，解是L的最小特征值 对应的特征矢量； 2.最小特征值对应特征矢量为1，不满足正交条件，第2小特征值对应 特征矢量满足正交条件（L为实对称矩阵）； k=2 示例 将19个样本分成2个聚类。 x1=(0,0)t, x2=(1,0)t, x3=(0,1)t, x4= (1,1)t, x5=(2,1)t, x6=(1,2)t, x7=(2,2)t, x8=(3,2)t, x9=(6,6)t, x10=(7,6)
6、t, x11=(8,6)t, x12= (7,7)t, x13=(8,7)t, x14=(9,7)t, x15=(7,8)t, x16=(8,8)t, x17=(9,8)t, x18=(8,9)t, x19=(9,9)t 特征值 特征值前2个特征值对应特征矢量 0.0000 0.0682 4.3510 5.1267 5.4904 5.9142 5.9461 6.3080 6.4175 6.4826 6.7696 6.9957 7.3704 7.6983 7.7789 7.9342 8.3716 8.6444 8.8704 -0.2294+0.2740 -0.2294+0.2728 -0.229
7、4+0.2731 -0.2294+0.2715 -0.2294+0.2694 -0.2294+0.2699 -0.2294+0.2655 -0.2294+0.2553 -0.2294-0.1838 -0.2294-0.1920 -0.2294-0.1954 -0.2294-0.1953 -0.2294-0.1968 -0.2294-0.1978 -0.2294-0.1969 -0.2294-0.1977 -0.2294-0.1984 -0.2294-0.1985 -0.2294-0.1991 聚类结果 RatioCut的近似谱求解: k2 RatioCut的优化问题 严格的优化问题： 约束：
8、仍然是NP问题。 近似的RatioCut的优化问题 近似的优化问题：放松对h中元素的离散性约束 问题的解：最小k个特征值对应特征矢量。 NCut的近似谱求解：k=2 NCut的近似谱求解：k=2 NCut的近似谱求解：k=2 NCut的优化问题 严格的优化问题： 约束： NCut的近似优化问题 NCut的近似谱求解：k2 NCut的近似谱求解：k2 NCut的优化问题：k2 严格的优化问题： 约束: NCut的近似优化问题：k2 谱聚类算法 算法的实现 算法的实现 算法的实现 弱监督学习 统计学习过程 学习的过程 统计学习过程 统计学习过程 最大似然估计： 贝叶斯估计： 统计学习过程 弱监督学
9、习过程 标签不是直接来自于Oracle，而是由Priesthood转达的 。 弱监督的风险 弱监督经验风险的优化 半监督学习 Semi-Supervised Learning Self-Training Co-Training Tri-Training Transductive SVM Transductive SVM14: 思路：让分类边界尽量远离样 本稠密区域。 方法：求解新的优化问题 其中： Graph-Based Methods 假设不同类别的样本分布在不同的流形上 图的构造：所有样本构成节点，样本之间的相似性构成节点 之间的连接； 思路：用正例节点作为源，反例节点作为汇，寻找图的最小
10、 割。 算法： 1.Mincut：直接求最小割； 2.Spectrum of Laplacian: 用谱的方法近似求解。 Label Propagation 优化问题求解 优化问题求解 对算法的理解 1.Harmonic性：可以证明优化问题的解具有Harmonic特 性 2.随机游走过程：定义节点之间的转移概率 随机游走 多示例学习 Multi-Instance Learning 问题的提出 1997年，Dietterich在分子制药预测方面提出的； 背景：药物能否有效是由药物分子与蛋白质结合的紧密性 决定的。 问题：在药物中，每个分子存在着多个低能量的形状；只 能知道哪一种药物分子有效，但无
11、法确切知道是哪个分子 形状起的作用。 问题的描述 每个分子形状表示为一个特征矢量，称为示例（Instance） ； 每个药物分子表示为一个示例包(Bag of Instances) 正例包：其中至少有一个示例是正例； 反例包：所有示例均为反例。 已知：每个示例包的标签； 未知：每个示例的标签。 图像识别 已知图像的标签，其中每个区域的标签未知。 示例包： 正例包中至少有一个示例是正例； 反例包中的示例都是反例。 问题： 判别示例包A是正例包还是反例包？ 判别示例y是正例还是反例？ 问题的表示 解决问题的思路 1.将示例包的标签传递给其中的每一个示例？ 2.将所有的示例连接成一个特征矢量？ 算法
12、的分类 Bag Based Methods：将示例包作为一个整体，看作是 空间中一个点； 将示例包空间视为度量空间，直接定义距离度量； 采用某种办法将示例包空间映射为欧氏空间，采用单示例分类器分 类； Instance Based Methods：按照MI的定义，利用示例包 学习一个示例的分类器，分类时对每个示例进行分类，然 后再判断示例包的属性。 Citation k-NN 方法：直接定义示例包之间的距离 嵌入空间算法 CCE 聚类示例，包括正例包和反例包的所有示例； 按照每个示例包中包含各个聚类的示例情况，将示例包映射为一个 矢量； 用所有示例包对应的矢量学习一个分类器； 重复聚类，映射和
13、学习分类器的过程，得到多个分类器； 组合所有分类器。 方法：将示例包空间映射为一个矢量空间 CCE：Constructive Clustering based Ensemble APR: Axis-Parallel Rectangles 思想：构造APR，寻找一个超矩形，至少包含每个正例包 中的一个示例，但不包含反例包中的任何示例。 APR 初始：计算正例包示例各维特征的最大值和最小值，构造一个包含 所有正例包示例的最小超矩形； 循环，直到APR中不包含任何反例为止： p 寻找能够排除某个反例，同时排除正例包示例数量最少的特征 ； p 在此特征维度上缩小APR。 APR: Axis-Paral
14、lel Rectangles 初始APR 收敛APR DD: Diverse Density 思想：认为在示例空间中只有一个点是正例，正例包都包 含（靠近）这一点，反例包的示例远离这一点。 DD: Diverse Density MI-SVM mi-SVM 学习：优化问题 约束： 正例包： 反例包： 分类： 其它的弱监督学习问题 Multi-Label Learning：每个示例有多个标签 Multi-Instance Multi-Label Learning：多标签、多示例 学习，每个示例包有多个类别标签 Multi-Instance Semi-Supervised Learning：半监督多示 例学习，部分示例包有标签，部分示例包无标签 Multi-Layer Multi-Instance Learning：示例包中的每个 示例还是一个示例包，构成多层结构 Imperfect Oracle：每个示例可能由多个标注者给出标签 ，而不同的标注者则对不同的示例给出标签
