《非监督聚类(精)》由会员分享,可在线阅读,更多相关《非监督聚类(精)(30页珍藏版)》请在金锄头文库上搜索。
1、模式识别与神经网络 Pattern Recognition and Neural Network,武汉大学电子信息学院,IPL,第七章 非监督学习方法,内容目录,IPL,第七章 非监督学习方法,7.1 引言,3,2,4,5,7.2 单峰子集的分离方法,7.3 类别分离的间接方法,7.4 分级聚类方法,7.5 聚类中的问题,1,第七章 非监督学习方法,3,7.1 引言,有监督学习(supervised learning):用已知类别的样本训练分类器,以求对训练集的数据达到某种最优,并能推广到对新数据的分类 非监督学习(unsupervised learning) :样本数据类别未知,需要根据样本
2、间的相似性对样本集进行分类(聚类,clustering) 非监督学习方法大致分为两大类: 基于概率密度函数估计的方法 基于样本间相似性度量的方法,第七章 非监督学习方法,4,方案对比,第七章 非监督学习方法,5,7.2 单峰子集的分离方法,思想:把特征空间分为若干个区域,在每个区域上混合概率密度函数是单峰的,每个单峰区域对应一个类 一维空间中的单峰分离: 对样本集KN=xi应用直方图方法估计概率密度函数,找到概率密度函数的峰以及峰之间的谷底,以谷底为阈值对数据进行分割,第七章 非监督学习方法,6,一维空间中的单峰子集分离,概率密度分析,第七章 非监督学习方法,7,多维空间投影方法,多维空间y中
3、直接划分成单峰区域比较困难,把它投影到一维空间x中简化问题。 确定合适的投影方向u: 使投影x=uTy的方差最大,方差越大,类之间分离的程度也可能越大 样本协方差矩阵的最大特征值对应的特征向量满足这样的要求 存在问题:这样投影有时并不能产生多峰的边缘密度函数,概率密度分析,第七章 非监督学习方法,8,投影方法举例,第七章 非监督学习方法,9,投影方法算法步骤,计算样本y协方差矩阵的最大特征值对应的特征向量u,把样本数据投影到u上,得到v=uTy 用直方图法求边缘概率密度函数p(v) 找到边缘概率密度函数的各个谷点,在这些谷点上作垂直于u的超平面把数据划分成几个子集 如果没有谷点,则用下一个最大
4、的特征值代替 对所得到的各个子集进行同样的过程,直至每个子集都是单峰为止,概率密度分析,第七章 非监督学习方法,10,灰度图像二值化算法,灰度图像阈值:,概率密度分析,第七章 非监督学习方法,11,单峰子集分离的迭代算法,概率密度分析,把样本集KN=xi分成c个不相交子集Ki。用这样的一个划分可用Parzon方法估计各类的概率密度函数:,聚类准则:即理想的划分应使下式最大,第七章 非监督学习方法,12,迭代算法步骤,概率密度分析,对数据集进行初始划分:K1, K2, ,Kc 用Parzon方法估计各聚类的概率密度函数 按照最大似然概率逐个对样本xk进行分类: 若没有数据点发生类别迁移变化,则停
5、止。否则转2,第七章 非监督学习方法,13,7.3 类别分离的间接方法,两个要点:相似性度量,准则函数 相似性度量 样本间相似性度量: 特征空间的某种距离度量 样本与样本聚类间相似性度量,第七章 非监督学习方法,14,准则函数,准则函数:聚类质量的判别标准,常用的最小误差平方和准则,目标: 类内元素相似性高,类间元素相似性低,第七章 非监督学习方法,15,C-均值算法(k-Means, k-均值),对样本集KN=xi尚不知每个样本的类别,但可假设所有样本可分为c类,各类样本在特征空间依类聚集,且近似球形分布 用一代表点(prototype)来表示一个聚类,如类内均值mi来代表聚类Ki 聚类准则
6、:误差平方和J,相似性分析,第七章 非监督学习方法,16,C-均值算法的训练,初始化:选择c个代表点p1, p2, ,pc 建立c个空聚类列表: K1, K2, ,Kc 按照最小距离法则逐个对样本x进行分类: 计算J及用各聚类列表计算聚类均值,并用来作为各聚类新的代表点(更新代表点) 若J不变或代表点未发生变化,则停止。否则转2。,相似性分析,第七章 非监督学习方法,18,C-均值算法举例,彩色图像分割:,第七章 非监督学习方法,19,C-均值算法的其他考虑,按照与c个代表点的最小距离法对新样本y进行分类,即: 初始划分的方法 更新均值的时机:逐个样本修正法与成批样本修正法 聚类数目的动态决定
7、,相似性分析,第七章 非监督学习方法,20,样本与聚类间相似性度量,样本x与聚类Ki间相似性度量: 聚类的表示: 样本集Ki =xj(i) 用一个所谓的“核函数”Ki,如样本集的某种统计量,相似性分析,第七章 非监督学习方法,21,样本与聚类间相似性度量,基于样本与聚类间相似性度量的动态聚类算法 初始化:选择c个初始聚类K1, K2, , Kc 建立c个空聚类列表: L1, L2, , Lc 按照最相似法则逐个对样本进行分类: 计算J 并用Li 更新各聚类核函数Ki 若J不变则停止。否则转2,相似性分析,第七章 非监督学习方法,22,正态核函数的聚类算法,正态核函数,适用于各类为正态分布,相似
8、性分析,参数集Vi=mi,i为各类样本统计参数 相似性度量:,第七章 非监督学习方法,23,近邻函数准则算法,近邻函数:样本间相似性的度量 如果yi是yj的第I个近邻, yj是yi的第K个近邻 aij = I + K 2 , ij 近邻函数使得密度相近的点容易聚成一类 同一类中的点之间存在“连接”。连接损失就定义为两点之间的近邻函数aij 一个点和其自身的连接损失aii=2N,以惩罚只有一个点的聚类 不同类的点不存在连接,连接损失aii=0 总类内损失:,相似性分析,第七章 非监督学习方法,24,两类间最小近邻函数值,第i类和第j类间最小近邻函数值定义为:,相似性分析,第i类内最大连接损失记为
9、: aimax 第i类与第j类之间的连接损失定义为bij,它的设计目标是:如果两类间的最小近邻值大于任何一方的类内的最大连接损失时,损失代价就是正的,从而应该考虑把这两类合并,第七章 非监督学习方法,25,近邻函数准则,总类间损失:,相似性分析,准则函数: 算法步骤: 计算距离矩阵 用距离矩阵计算近邻矩阵 计算近邻函数矩阵 在L 中,每个点与其最近邻连接,形成初始的划分 对每两个类计算rij 和aimax,ajmax ,只要rij 小于aimax、ajmax中的任何一个,就合并两类(建立连接)。重复至没有新的连接发生为止,第七章 非监督学习方法,26,7.4 分级聚类方法,划分序列:N个样本自
10、底向上逐步合并一类: 每个样本自成一类(划分水平1) K水平划分的进行:计算已有的c=N-K+2个类的类间距离矩阵D(K-1)=dij(K-1),其最小元素记作d(K-1),相应的两个类合并成一类 重复第2步,直至形成包含所有样本的类(划分水平N) 划分处于K水平时,类数c=N-K+1,类间距离矩阵D(K)=dij(K),其最小元素记作d(K) 如果d(K) 阈值dT,则说明此水平上的聚类是适宜的,第七章 非监督学习方法,27,分级聚类树表示方法,分级 聚类,第七章 非监督学习方法,28,两聚类间的距离度量,聚类Ki与Kj间的距离度量,最近距离:,最远距离:,均值距离:,分级 聚类,第七章 非监督学习方法,29,7.5 聚类中的问题,非监督模式识别问题存在更大的不确定性: 可利用信息少 相似性度量一般对数据尺度(scale)较敏感 影响聚类结果的因素:样本的分布,样本数量,聚类准则,相似性度量,预分类数等 针对不同数据,不同目标选择不同的聚类算法 动态聚类算法计算效率高,实际应用多,第七章 非监督学习方法,30,习题,习题10.2 习题10.5 试用流程图描述C-Means算法 试小结下列相似性度量: 样本x与样本y间的相似性度量 样本x与聚类K间的相似性度量 聚类Ki与聚类Kj间的相似性度量,