模式识别第9章20151019.pptx

模式识别：非监督模式识别Pattern Recognition主讲人：胡雪梅导师：黄岚指导老师：王岩时间：2015/10/19非监督模式识别引言基于模型的方法混合模型的估计动态聚类算法模糊聚类方法分级聚类方法SOM自组织神经映射网络 非监督模式识别——引言引言非监督学习识别/聚类通过某种算法把一组未知类别的样本划分为若干类别。事先不知道类别的定义，不知道有几类或者是否存在分类，无可参考的分类目标。分监督模式识别的分类基于样本的规律分布模型进行聚类划分。 例如：基于模型的方法根据样本间的距离或相似度进行聚类。例如：非监督模式识别 ——基于模型的方法基于模型的方法前提条件：已经知道或者可以估计样本在特征空间的概率分布。单峰子集分离法/单峰子类分离法基本思想：假设每一个聚类的样本在特征空间里是集中在一起的，在分布的密度上形成了了一个局部的峰值。特征高维：投影。把样本按照某种准则投影到某个一维坐标上估计样本的概率密度，寻找单峰值进行聚类划分。关键问题：如何设计合适的坐标系？ 一种可行答案：使待分类的样本在某个坐标轴方向具有最大的分散性。/样本分布方差最大的方向。 但不是所有的情况都适合用这种方法。 算法步骤1）主成分分析。选取投影方向。2）估计概率函数密度。如：直方图3）寻找局部极小值点。若无则 1）4）对划分出来的子集重复以上步骤，直至终止条件满足非监督模式识别 ——混合模型的估计混合模型的估计非监督的最大似然估计基本思想：当从模型总体随机抽取n组样本观测值后，最合理的参数估计量应该使得从模型中抽取该n组样本观测值的概率最大。假设条件：最大似然函数：非监督模式识别 ——混合模型的估计混合高斯分布 高斯混合模型是单一高斯机率密度函数的延伸，任意形状的概率分布 都可以用多个高斯分布函数去近似。 非监督模式识别 ——动态聚类算法动态聚类算法基于相似度度量的聚类方法。动态聚类算法的要点：1）选定某种距离度量作为样本间的相似性度量。2）确定某种评价聚类结果质量的准则函数。3）给定某个初始分类，迭代，找出使准则函数取极值的最好聚类结果。常用的聚类算法：C均值算法、ISODATA、基于样本与核的相似性度量的动态聚类算法。C均值算法基本思想：最小方差划分 通过迭代寻找c个聚类的一种划分方案，使得c个聚类的均值来代表相应的各类样本时得到的总体误差最小。准则函数 Je 含义是各类样本与其所属样本均值间误差平方之总和。非监督模式识别 ——动态聚类算法C均值算法的基本步骤C均值算法的特点局部有哪些信誉好的足球投注网站算法，不能保证收敛到全局最优解。结果受初始划分和样本调整顺序的影响。样本初始划分方法：一般选择一些代表样点作为初始聚类的核心。非监督模式识别 ——动态聚类算法代表点的选择方法凭经验选择代表点。将全部数据随机分成c类，计算每类的重心。将样本排序后用前c个点作为代表点。从（c-1）聚类划分问题中产生c聚类划分问题的代表点。初始分类方法选择一批代表点后，其余的点离那个代表点进就归入哪一类。同上，但是会立即重新计算中心代替原来的代表点。首先选择一个正数 ，选择 ，计算 与 间的距离如果小于 ，则将 归于 ，否则建立新类 ，以此类推……现将数据标准化，用 表示标准化后的第 i 个样本的第 j 个坐标。令 计算如果计算的值最接近整数k，则将 归入第k类关于聚类数目c拐点A处对应的类别数最优非监督模式识别 ——动态聚类算法ISODATA方法（改进的C均值算法）与C均值算法的不同不是调整一个样本的类别就更新一次各类的均值，而是把全部样本调整完后才重新计算各类的均值。引入了对类别的评判准则，根据这些准则对某些类合并或者分裂。ISODTADA基本步骤?1）初始化，确定c个初始中心；2）把样本分到距离中心最近的类中；3）若某一类样本数目过少，去掉该类，c--；4）重新计算某类的均值；5）计算每一类样本与其中心的平均距离和总的平均距离（分裂和合并的时候会用到）；6）c K/2 ,转 7）；c，转 8）；//K为期望得到的聚类数7）（分裂），c++;8）（合并），c--;9）最后一次迭代？是，终止；否，转 2）非监督模式识别 ——动态聚类算法基于样本与核的相似性度量的动态算法问题引入当样本的分布偏离超球形，用均值就不能很好的代表一个类。解决办法构造基于样本与核的相似性度量的动态聚类算法。类别的核表示、类的距离度量准则函数： 算法步骤1）选择初始划分，c类，确定每一类的初始核 Kj；2）若 如果样本 y 到核Kj的距离是y到所有核Kk中的最小者。则将 y 划分到第 j类中；3）重新修正核 Kj ,若 Kj 保持不变，算法终止，否则转到 2）； 比较C均值是