第二章_距离分类器.ppt

第二章距离分类器和聚类分析 2 1距离分类器 一 模式的距离度量 距离函数应满足的条件 对称性 非负性 三角不等式 常用的距离函数 欧几里德距离 EucideanDistance 常用的距离函数 街市距离 ManhattanDistance 常用的距离函数 明氏距离 MinkowskiDistance 常用的距离函数 角度相似函数 AngleDistance 是X与Y之间的内积 为矢量X的长度 也称为范数 二 单个标准样本距离分类器 M个类别 每个类别有一个标准样本 对待识样本X进行分类 建立分类准则 如果有 则判别 距离分类器 三 多标准样本的距离分类器 M个类别 第m个类别有训练样本集合 对待识样本X进行分类 多标准样本的距离分类器 平均样本法对每一类求一个标准样本T m 使T m 到所有训练样本的平均距离最小 平均样本法的特点 算法简单存储量小计算量小效果不一定很好 平均距离法 已知 i类有训练样本集 定义待识模式X与类别 i的距离 最近邻法 待识模式X与类别 i的距离 最近邻法的改进 平均样本法 用一点代表一个类别 过于集中 最近邻法 以类内的每一点代表类别 过于分散 改进最近邻法 将每个类别的训练样本划分为几个子集 以子集的平均样本作为代表样本 K 近邻法 计算X与所有训练样本的距离 对所计算出的距离从小到大排序 统计前K个中各类样本的个数Ni 如果 则判别 2 2聚类分析 简单聚类法系统聚类法动态聚类法 简单聚类法 试探法 最近邻规则的简单试探法最大最小距离算法 最近邻规则的简单试探法 已知 N个待分类模式 X1 X2 XN 阈值T 每个样本到其聚类中心的最大距离 分类到 1 2 类别中心为Z1 Z2 最近邻规则的简单试探法 第一步 取任意的样本作为第一个聚类中心 Z1 X1 计算D21 X2 Z1 如果D21 T 则增加新类别 Z1 X1 否则 X2归入 1类 重新计算 Z1 X1 X2 2 最近邻规则的简单试探法 第二步 设已有M个类别 加入样本Xk计算Dk1 Xk Z1 Dk2 Xk Z2 如果Dki T 则增加新类别 M 1ZM 1 Xk 否则 Xk归入最近的一类 重新计算该类的聚类中心 最大最小距离算法 基本思路 以最大距离原则选取新的聚类中心 以最小距离原则进行模式归类 已知 N个待识模式 X1 X2 XN 阈值比例系数 最大最小距离算法 任选样本作为第一个聚类中心Z1 从样本集中选择距离Z1最远的样本Xi作为第二个聚类中心 Z2 Xi 设定阈值 T Z1 Z2 最大最小距离算法 计算未被作为聚类中心的各样本Xi与Z1 Z2之间的距离 以其中的最小值作为该样本的距离di 若di T 将Xi作为第3个聚类中心 Z3 Xi 转3 否则 转5按照最小距离原则 将所有样本分到各类别中 系统聚类法 基本思路 首先每一个样本自成一类 然后按照距离准则逐步合并 类别数由多到少 达到合适的类别数为止 已知 N个待识模式 X1 X2 XN 类别数M 类与类之间的距离 最短距离 最长距离 平均距离 系统聚类算法 第一步建立N个初始类别 每个样本一个类别 计算距离矩阵D Dij 第二步寻找D中的最小元素 合并相应的两个类别 建立新的分类 重新计算距离矩阵D 重复第二步 直到类别数为M为止 动态聚类法 基本思想 首先选择若干个样本点作为聚类中心 然后各样本点向各个中心聚集 得到初始分类 判断初始分类是否合理 如果不合理 则修改聚类中心 包括 K 均值算法 ISODATA算法 K 均值算法 C 均值 第一步 任选K个初始聚类中心 第二步 将每一个待分类样本分到K个类别中去 第三步 计