模式识别第9章20151019

模式识别：非监督模式识别PatternRecognition主讲人：胡雪梅导师：黄岚指导老师：王岩时间：2015/10/19非监督模式识别引言基于模型的方法混合模型的估计动态聚类算法模糊聚类方法分级聚类方法SOM自组织神经映射网络

非监督模式识别——引言非监督学习识别/聚类通过某种算法把一组未知类别的样本划分为若干类别。事先不知道类别的定义，不知道有几类或者是否存在分类，无可参考的分类目标。分监督模式识别的分类基于样本的规律分布模型进行聚类划分。

例如：基于模型的方法根据样本间的距离或相似度进行聚类。例如：3引言2023/2/5非监督模式识别

——基于模型的方法前提条件：已经知道或者可以估计样本在特征空间的概率分布。单峰子集分离法/单峰子类分离法基本思想：假设每一个聚类的样本在特征空间里是集中在一起的，在分布的密度上形成了了一个局部的峰值。特征高维：投影。把样本按照某种准则投影到某个一维坐标上估计样本的概率密度，寻找单峰值进行聚类划分。关键问题：如何设计合适的坐标系？

一种可行答案：使待分类的样本在某个坐标轴方向具有最大的分散性。/样本分布方差最大的方向。

但不是所有的情况都适合用这种方法。

算法步骤1）主成分分析。选取投影方向。2）估计概率函数密度。如：直方图3）寻找局部极小值点。若无则1）4）对划分出来的子集重复以上步骤，直至终止条件满足4基于模型的方法2023/2/5非监督模式识别

——混合模型的估计最大似然函数：非监督的最大似然估计基本思想：当从模型总体随机抽取n组样本观测值后，最合理的参数估计量应该使得从模型中抽取该n组样本观测值的概率最大。假设条件：5混合模型的估计2023/2/5非监督模式识别

——混合模型的估计混合高斯分布

高斯混合模型是单一高斯机率密度函数的延伸，任意形状的概率分布

都可以用多个高斯分布函数去近似。

62023/2/5非监督模式识别

——动态聚类算法基于相似度度量的聚类方法。动态聚类算法的要点：1）选定某种距离度量作为样本间的相似性度量。2）确定某种评价聚类结果质量的准则函数。3）给定某个初始分类，迭代，找出使准则函数取极值的最好聚类结果。常用的聚类算法：C均值算法、ISODATA、基于样本与核的相似性度量的动态聚类算法。C均值算法基本思想：最小方差划分

通过迭代寻找c个聚类的一种划分方案，使得c个聚类的均值来代表相应的各类样本时得到的总体误差最小。准则函数Je含义是各类样本与其所属样本均值间误差平方之总和。7动态聚类算法2023/2/5非监督模式识别

——动态聚类算法C均值算法的基本步骤C均值算法的特点局部搜索算法，不能保证收敛到全局最优解。结果受初始划分和样本调整顺序的影响。样本初始划分方法：一般选择一些代表样点作为初始聚类的核心。82023/2/5非监督模式识别

——动态聚类算法代表点的选择方法凭经验选择代表点。将全部数据随机分成c类，计算每类的重心。将样本排序后用前c个点作为代表点。从（c-1）聚类划分问题中产生c聚类划分问题的代表点。初始分类方法选择一批代表点后，其余的点离那个代表点进就归入哪一类。同上，但是会立即重新计算中心代替原来的代表点。首先选择一个正数，选择，计算与间的距离如果小于，则将归于，否则建立新类，以此类推……现将数据标准化，用表示标准化后的第i个样本的第j个坐标。令

9如果计算的值最接近整数k，则将归入第k类计算关于聚类数目c拐点A处对应的类别数最优2023/2/510非监督模式识别

——动态聚类算法ISODATA方法（改进的C均值算法）与C均值算法的不同不是调整一个样本的类别就更新一次各类的均值，而是把全部样本调整完后才重新计算各类的均值。引入了对类别的评判准则，根据这些准则对某些类合并或者分裂。ISODTADA基本步骤

2023/2/511非监督模式识别

——动态聚类算法基于样本与核的相似性度量的动态算法问题引入当样本的分布偏离超球形，用均值就不能很好的代表一个类。解决办法构造基于样本与核的相似性度量的动态聚类算法。类别的核表示、类的距离度量准则函数：

算法步骤1）选择初始划分，c类，确定每一类的初始核Kj；2）若

如果样本y到核Kj的距离是y到所有核Kk中的最小者。则将y划分到第j类中；3）重新修正核Kj,若Kj保持不变，算法终止，否则转到2）；

比较C均值是基于样本与核的相似性度量的动态算法的一个特例。2023/2/512非监督模式识别

——模糊聚类方法基本知识模糊聚类基本知识Zadeh提出模糊集理论：每一个元素是以一定的程度属于某个集合，也可以以不同的程度属于几个集合。隶属度函数：一个对象x隶属于集合A的程度的函数，。支持集、支持点重要函数模糊C均值算法聚类损失函数（准则函数）：归一化条件：计算隶属度函数：更新聚类中心函数：2023/2/513算法步骤非监督模式识别

——模糊聚类方法改进的模糊C均值算法问题引入如果某个野值样本远离各类的聚类中心，原本属于各类的隶属度都很小，但归一化条件会使得它对各类都有较大的隶属度，影响迭代结果。改进策略：放松归一化条件，使得样本对各类的隶属度总和为n，即评价优点：更好的鲁棒性、对初始聚类数目不敏感；缺点：1）同C均值、模糊C均值一样，对聚类中心的初值十分敏感；2）若果某个聚类中心距离某个样本非常近，可能会得到只包含这一个样本的类别。2023/2/514非监督模式识别

——分级聚类方法引入生物学上物种的分类。分级聚类：自底向上的方法算法步骤1）初始化，每个样本形成一类；2）合并：把距离最小（或相似性最大的两类合并）；3）重复2），直到所有的样本合并到两个类中。树枝的长度反应两个节点之间的距离（相似性）算法特点局部搜索、噪音敏感；聚类数树画法不唯一；分级聚类方法2023/2/515非监督模式识别

——自组织映射神经网络SOM算法和自组织特性SOM的生物依据由芬兰人Kohonen于1981年开始研究。高等动物大脑皮层对外界的信号有规律的相应，很大部分是在不断接受外界信号刺激的的过程中形成的。特定神经元参数组织对特定外界刺激敏感，形成局部功能区域。SOM的网络拓扑结构SOM算法思想某个输出结点能对某一类刺激作出特别的反应以代表该类别；输出层上相邻的结点能对实际模式分布中相近的类别作出特别的反映；当某类数据输入时，对某一输出结点产生最大刺激的获胜结点，同时对获胜结点周围的一些结点产生较大刺激；2023/2/516非监督模式识别

——自组织映射神经网络算法步骤2023/2/517非监督模式识别

——自组织映射神经网络SOM算法图例真实聚类规则训练样本点神经元初始位置第一个训练样本获胜神经元9，邻域：5，6，8第二个训练样本获胜神经元4邻域：1，5，7第三个训练样本获胜神经元3邻域：2，5，6第一个训练样本获胜神经元9，邻域：5，6，8第二个训练样本获胜神经元4邻域：1，5，7第三个训练样本获胜神经元3邻域：2，5，6SOM的自组织现象

SOM完成的是从原样本空间到二维平面上神经元网格的映射，这种映射是拓扑保持的，即在原空间