模式识别导论 二.pptVIP

模式识别 Pattern Recognition 江南大学通信与控制工程学院 3. 聚类准则 ① 阈值准则 根据规定的距离阈值教学分类的准则 ②函数准则 聚类中表示模式类间相似性或差异性的函数称为聚类准则函数。利用准则函数可将聚类问题转化成准则函数的最优化问题。 误差平方和准则　　以计算各类均值 ??，与计算各类样本到其所属类均值点误差平方和为准则，若各类均值表示成　　 ???????????? 其中第i类集合为 ??，其样本数目为 ??。 上图的样本分布，共有3个类型，各个类型的样本数目相差不多（10个左右）。类内较密集，误差平方和很小，类别之间距离远。 采用误差平方和准则，有可能把样本数目多的类型分开，以便达到总的 最小。 加权平均平方距离和准则 2.3 基于距离阈值的聚类算法 1．最近邻决策规则 假设有c个类别 的模式识别问 题，每一类有标明类别的样本 个。 此时决策函数为： 决策规则为： 若 ， 则： 2．采用最近邻规则的聚类算法 假设已有混合样本集 ，按照最近邻原则进行聚类，算法如下： ① 选取距离阈值 ，并且任取一个样本 作为第一个聚合中心 ，如： 。 ② 计算样本 到 的距离 ： 若 ，则 ，否则令 为第二个聚合中心， 。 设 ，计算 到 和 的距离 和 若 和 ，则建立第三个聚合中心 。否则把 归于最近邻的聚合中心。依此类推，直到把所有的 个样本都进行分类。 ③ 按照某种聚类准则考察聚类结果，若不满意，则重新选取距离阈值 、第一个聚合中心 ，返回②，直到满意，算法结束。 在样本分布一定时，该算法的结果在很大程度上取决于第一个聚合中心的选取和距离阈值的大小。 该算法的优点是简单，如果有样本分布的先验知识用于指导阈值和起始点的选取，则可较快得到合理结果。对于高维的样本集来说，则只有经过多次试探，并对聚类结果进行验算，从而选择最优的聚类结果。 3.错误率分析 设N个样本的平均错误率为 。定义最近邻法的渐近平均错误率P为当 时， 的极限，记作： 可以证明存在如下关系： 2.3.2 k-近邻法 1． k-近邻决策规则 假设有c个类别 的模式识别问 题，每一类有标明类别的样本 个。设样 本的k个近邻中属于 类的样本数 分别为： 此时决策函数为： 决策规则为： 若 ，则： 显然，k-近邻法是最近邻法的推广。但 是k-近邻法不一定优于最近邻法。其错误率 也为 ，由于 比较小，所 以可粗略认为错误率是： 近邻法存在的问题 计算量大，存储量大 解决的方法 寻找快速算法，约减存储量 现有的方法在整个模式上实现操作，这会 引起计算的指数增长，故考虑在模式子集 上操作，即随机子空间方法。 2.3.3 最大最小距离聚类算法 该算法以欧氏距离为基础，除首先辨识最远的聚类中心外，与上述算法相似。用一个例子说明该算法。 例：样本分布如图所示。 RSM 假设模式为 ，算法如下： 随机地从x中抽取d个特征，构成d维子 空间。 将x投影到该子空间，即对样本集 可 得到一个子空间样本集 。 重复N次得到 ～ 子空间样本集。 N一般取10（依赖于具体问题） 用已有的方法对各个子空间分类，纪录每个子空间的允许类号 对N个子空间的允许类号进行表决 优点：子空间分类器的增加（复杂性增 加）推广能力也同时增加。 2.5.1 C-均值聚类算法 C-均值聚类算法使用的聚类准则函数是误差平方 和准则： 为了使聚类结果优化，应该使准则最小化。 2.4