《无监督学习的定义、背景及意义》由会员分享，可在线阅读，更多相关《无监督学习的定义、背景及意义（23页珍藏版）》请在金锄头文库上搜索。
1、Nature Inspired Computation and Applications Laboratory School of Computer Science and Technology University of Science and Technology of China Pattern Recognition Lecture 12 Unsupervised Learning and Clustering Nature Inspired Computation and Applications Laboratory 主要内容 无监督学习的定义、背景及意义 聚类的一些根本问题 几种
2、聚类算法 Nature Inspired Computation and Applications Laboratory 无监督学习 根据类别未知（没有被标记）的训练样本 解决模式识别中的各种问题，例如： 聚类（clustering） 特征分析 Nature Inspired Computation and Applications Laboratory 无监督学习的背景与意义 现实生活中常常会有这样的问题： 缺乏足够的先验知识，因此难以人工标注类别； 进行人工类别标注的成本太高。 很自然地，我们希望计算机能代我们（部分）完 成这些工作，或至少提供一些帮助。 常见的应用背景包括： 从庞大的样本
3、集合中选出一些具有代表性的加以标注， 用于分类器的训练。 先将所有样本自动分为不同的类别，再由人类对这些 类别进行标注。 在无类别信息情况下，寻找好的特征。 Nature Inspired Computation and Applications Laboratory 聚类（clustering） 定义： 在一堆数据中寻找一种“自然分组”（C组）。我 们希望同组（类别）的样本较为相似，而不同组 的样本间有明显不同。 一个简单的例子 Nature Inspired Computation and Applications Laboratory 聚类（clustering） 聚类是一个难以被严格定
4、义的问题，因为“自然 分组”本身就很抽象，且可能因人而异。 尽管如此，既然需要这样一种技术来解决人类难 以解决的问题，则必须首先由人来对问题进行定 义。具体来说，需要回答两个问题： 怎样度量样本之间的相似性相似性？ 怎样衡量某一种分组的好坏衡量某一种分组的好坏？（目标函数是什么？） 即使有了上述定义，要找到“最优分组”的计算 复杂度也高得难以承受，例如将100个样本聚集为 5类需要考虑超过1067种可能的划分（5100/5！）， 所以一般的聚类算法都是近似算法近似算法。 Nature Inspired Computation and Applications Laboratory 聚类（clu
5、stering） 相似性度量 Minkowski度量： 归一化内积： 也可以自行定义其他的相似性度量，没有统一的标 准，只能根据人类的经验。 1/ 1( ,)qdqii idxxx x ( ,)T sx xx xx xNature Inspired Computation and Applications Laboratory 聚类（clustering） 聚类的目标函数 误差平方和：各类样本到该类均值向量的距离之和 相关的最小方差准则： 也可以根据散度矩阵来定义各种目标函数。 21iCi iDJ xxm211 2iiCi iDDJn xxxxNature Inspired Computati
6、on and Applications Laboratory 聚类（clustering） 一旦确定了目标函数，则聚类又变为了一个优优 化问题化问题：寻找一种对样本集的分组方式，使得 目标函数取极值。 一些基本的聚类方法 K-means算法 Fuzzy K-means算法（ K-means 变体1） 迭代型K-means算法（ K-means 变体2） 合并法（又称系统聚类） 分裂法（又称分解聚类） Nature Inspired Computation and Applications Laboratory K-means算法 K-means算法 Nature Inspired Comput
7、ation and Applications Laboratory Fuzzy K-means算法 Fuzzy K-means算法： 是K-means算法的一种推广形式，关键在于定义 了一个隶属度函数 ，使得在求解过程中每 一个样本点可以被视为以一定的概率同时属于 多个类别。 目标函数： 在求解过程中，每一轮更新都需涉及两种变量， 即类别均值与隶属度 Nature Inspired Computation and Applications Laboratory Fuzzy K-means算法 均值更新策略： 隶属度更新策略 Nature Inspired Computation and App
8、lications Laboratory Fuzzy K-means算法 11,., (), =1,. ; =1,.,2()34()5cijijiijkn,c,bP w |ic jnP w |P w |2 -begin initializexxdox算法（模糊均值聚类算法）归一化重新计算重新计算1()6,7iijcP w |untilxreturn . end在和变化很小Nature Inspired Computation and Applications Laboratory 迭代型K-means算法 基本思路：K-means算法每一轮更新都对所有样本所有样本重新 归类，而迭代型K-mea
9、ns则只涉及一个样本一个样本的重新归类。 相比之下，更容易陷入局部最优，但适合于在线学习。 Nature Inspired Computation and Applications Laboratory 合并法 基本思路：先把每个样本作为一类，然后根据 它们间的相似性聚合。 显然，需要进一步定义不同类别间的相似性： Nature Inspired Computation and Applications Laboratory 合并法 Nature Inspired Computation and Applications Laboratory 分裂法 基本思路：把全部样本作为一类，然后根据相
10、似性分解。 例子：每次将现有的类别进行对分，令目标函 数最小，直至算法终止。 由于难以确定每次“分裂”出去多少样本数目 为最佳，对分法显然是一种粗糙的，不得已而 为之的策略。 Nature Inspired Computation and Applications Laboratory 谱聚类 对于一组模式x1, x2, , xn，谱聚类： 基于无向加权图G=(V,E)，其中每个顶点vi对应 一个xi，顶点vi和vj间的边有权值wij0 聚类问题就是要求G的连通子图 顶点vi的度为 相应的，定义邻接矩阵W和度矩阵D(对角阵) 邻接矩阵W可根据模式间的相似度s(xi, xj)获得 niij id
11、wNature Inspired Computation and Applications Laboratory 谱聚类 无向图G=(V,E)的拉普拉斯矩阵(Laplacian matrix) 拉普拉斯矩阵有以下特性 对任意n维向量f，有 L为半正定矩阵为半正定矩阵 L存在0特征值，且对应的特征向量所有元素均相等 LDW2,11()2n T ijij i jwfff LfNature Inspired Computation and Applications Laboratory 谱聚类 理想情况下，若G能被分为若干个互不联通的连 通子图，则可获得“完美”的聚类结果。 在上述情况下，L的0特征
12、值个数即为类别数，且 对于第k个0特征值，对应的特征向量e满足 尽管完美的聚类往往难以实现，我们仍可认为： 若若L的某些特征向量对应的特征值较小，则该特征的某些特征向量对应的特征值较小，则该特征 向量给出了对聚类有用的信息向量给出了对聚类有用的信息 1, if 0, otherwise iikieCluster e xNature Inspired Computation and Applications Laboratory 谱聚类 算法流程算法流程： 定义相似性度量s并计算相似性矩阵，设定聚类的 类别数k 根据相似性矩阵S计算邻接矩阵W 计算拉普拉斯矩阵L 计算L的k个最小特征值对应的特征
13、向量e1, ek 基于所求得的特征向量，定义一个k维空间，模式 xi在该空间中表示为e1i, eki 利用任意现有的聚类算法，如k-means，在新空间 中进行聚类。 Nature Inspired Computation and Applications Laboratory 谱聚类 谱聚类的本质实际就是先将模式映射到一个新的 空间，再以传统方式聚类。 使用谱聚类须首先回答的一些问题使用谱聚类须首先回答的一些问题 给定相似度矩阵S，怎样获得邻接矩阵W？ 若s(xi, xj)小于某一阈值，令wij= s(xi, xj)，否则为0 当xi, xj互为对方的k近邻时，令wij= s(xi, xj) 直接令wij= s(xi, xj)，这时G成为一个全连通图 Nature Inspired Computation and Applications Laboratory 谱聚类 如何确定类别数目？ 将所有特征值由小到大排序，若第k个特征值与第k+1 个特征值差别较大，则取k为类别数 对于L，要计算对应k个最小特征值的特征向量，并 不需要做完全的特征值分解，可以用一些经典的迭 代法，比如Krylov subspace方法
