模式识别第二章-距离分类器

章距离分类器和

聚类分析

2021/5/912.1距离分类器一、模式的距离度量2021/5/92距离函数应满足的条件对称性：非负性：三角不等式：2021/5/93常用的距离函数欧几里德距离：(EucideanDistance)2021/5/94常用的距离函数街市距离：(ManhattanDistance)2021/5/95常用的距离函数明氏距离：(MinkowskiDistance)2021/5/96常用的距离函数角度相似函数：(AngleDistance)是X与Y之间的内积为矢量X的长度，也称为范数

2021/5/97二、单个标准样本距离分类器M个类别：每个类别有一个标准样本：对待识样本X进行分类。2021/5/98建立分类准则如果有：则判别：2021/5/99距离分类器2021/5/910三、多标准样本的距离分类器M个类别：第m个类别有训练样本集合：对待识样本X进行分类。2021/5/911多标准样本的距离分类器平均样本法 对每一类求一个标准样本T(m)，使T(m)到所有训练样本的平均距离最小：2021/5/912平均样本法的特点算法简单存储量小计算量小效果不一定很好2021/5/913平均距离法

已知Ωi类有训练样本集：

定义待识模式X与类别Ωi的距离：2021/5/914最近邻法

待识模式X与类别Ωi的距离：2021/5/915最近邻法的改进平均样本法：用一点代表一个类别，过于集中；最近邻法：以类内的每一点代表类别，过于分散；改进最近邻法：将每个类别的训练样本划分为几个子集，以子集的平均样本作为代表样本。2021/5/916K-近邻法计算X与所有训练样本的距离；对所计算出的距离从小到大排序；统计前K个中各类样本的个数Ni；如果： 则判别：2021/5/9172.2聚类分析简单聚类法系统聚类法动态聚类法2021/5/918简单聚类法（试探法）最近邻规则的简单试探法最大最小距离算法2021/5/919最近邻规则的简单试探法

已知：N个待分类模式{X1，X2，…，XN}，阈值T(每个样本到其聚类中心的最大距离)，分类到Ω1，Ω2，…，类别中心为Z1，Z2，…2021/5/920最近邻规则的简单试探法第一步：取任意的样本作为第一个聚类中 心，Z1=X1； 计算D21=||X2-Z1||； 如果D21>T，则增加新类别：Z1=X1； 否则，X2归入Ω1类，重新计算：

Z1=(X1+X2)/22021/5/921最近邻规则的简单试探法第二步：设已有M个类别，加入样本Xk

计算Dk1=||Xk-Z1||，Dk2=||Xk-Z2||…； 如果Dki>T，则增加新类别ΩM+1 ZM+1=Xk； 否则，Xk归入最近的一类，重新计算该 类的聚类中心：2021/5/922最大最小距离算法基本思路：以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类；已知：N个待识模式{X1，X2，…，XN}，阈值比例系数θ。2021/5/923最大最小距离算法任选样本作为第一个聚类中心Z1；从样本集中选择距离Z1最远的样本Xi作为第二个聚类中心，Z2=Xi，设定阈值：T=θ||Z1-Z2||；2021/5/924最大最小距离算法计算未被作为聚类中心的各样本Xi与Z1，Z2之间的距离，以其中的最小值作为该样本的距离di；若di>T，将Xi作为第3个聚类中心，Z3=Xi，转3；否则，转5按照最小距离原则，将所有样本分到各类别中。

2021/5/925系统聚类法基本思路：首先每一个样本自成一类，然后按照距离准则逐步合并，类别数由多到少，达到合适的类别数为止。已知：N个待识模式{X1，X2，…，XN}，类别数M。2021/5/926类与类之间的距离最短距离：最长距离：平均距离：2021/5/927系统聚类算法第一步建立N个初始类别，每个样本一个类别，计算距离矩阵D=(Dij)；第二步寻找D中的最小元素，合并相应的两个类别，建立新的分类，重新计算距离矩阵D；重复第二步，直到类别数为M为止。2021/5/928动态聚类法基本思想：首先选择若干个样本点作为聚类中心，然后各样本点向各个中心聚集，得到初始分类；判断初始分类是否合理，如果不合理，则修改聚类中心。包括：K-均值算法，ISODATA算法。2021/5/929K-均值算法(C-均值)第一步：任选K个初始聚类中心；第二步：将每一个待分类样本分到K个类别