第二章_距离分类器.ppt

第二章 距离分类器和 聚类分析 2.1 距离分类器 一、模式的距离度量 距离函数应满足的条件 对称性： 常用的距离函数 欧几里德距离：(Eucidean Distance) 常用的距离函数 街市距离：(Manhattan Distance) 常用的距离函数 明氏距离：(Minkowski Distance) 常用的距离函数 角度相似函数：(Angle Distance) 二、单个标准样本距离分类器 M个类别： 建立分类准则 如果有： 距离分类器 三、多标准样本的距离分类器 M个类别： 多标准样本的距离分类器 平均样本法 对每一类求一个标准样本T(m)，使T(m)到所有训练样本的平均距离最小： 平均样本法的特点 算法简单 存储量小 计算量小 效果不一定很好 平均距离法 已知Ω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+1 ZM+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个类别中去； 第三步：计算各类的聚类中心； 第四步：检验新的聚类中心与旧的聚类中心是否相等，相等则算法结束；否则转第二步。 2.3 聚类结果评价 类内距离方差 ： * * 非负性： 三角不等式： 是X与Y之间的内积 为矢量X的长度，也称为范数 每个类别有一个标准样本： 对待识样本X进行分类。 则判别： 第m个类别有训练样本集合： 对待识样本X进行分类。 定义待识模式X与类别Ωi的距离： 最长距离： 平均距离：