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

1、第二章 距离分类器和 聚类分析2.1 距离分类器n一、模式的距离度量距离函数应满足的条件 n对称性： ,ddX YY X,0dX Y,dddX YX ZY Zn非负性： n三角不等式： 常用的距离函数n欧几里德距离：(Eucidean Distance) 1221,niiidxyX Y常用的距离函数n街市距离：(Manhattan Distance)1,niiidxyX Y常用的距离函数n明氏距离：(Minkowski Distance) 11,mnmiiidxyX Y常用的距离函数n角度相似函数：(Angle Distance) ,TdXYX YXY1nTiiix yXY是X与Y之间的内积X

2、为矢量X的长度，也称为范数 二、单个标准样本距离分类器M个类别：12,M 每个类别有一个标准样本：12MT,T ,T对待识样本X进行分类。建立分类准则如果有：0argmin,iiidX T则判别：0iX距离分类器三、多标准样本的距离分类器 M个类别：12,M 第m个类别有训练样本集合：对待识样本X进行分类。 12,mmmmKXXX多标准样本的距离分类器n平均样本法对每一类求一个标准样本T(m)，使T(m)到所有训练样本的平均距离最小： 11mKmmiimKTX平均样本法的特点n算法简单n存储量小n计算量小n效果不一定很好平均距离法已知i类有训练样本集：定义待识模式X与类别i的距离： 12,ii

3、iiKTTT 11,iKiijjiddKXX T最近邻法待识模式X与类别i的距离： 1,min,iiijj Kdd XX T最近邻法的改进n平均样本法：用一点代表一个类别，过于集中； n最近邻法：以类内的每一点代表类别，过于分散；n改进最近邻法：将每个类别的训练样本划分为几个子集，以子集的平均样本作为代表样本。 K-近邻法n计算X与所有训练样本的距离；n对所计算出的距离从小到大排序；n统计前K个中各类样本的个数Ni；n如果：n则判别：01argmaxii MiN 0iX2.2 聚类分析聚类分析n简单聚类法 n系统聚类法 n动态聚类法 简单聚类法（试探法） n最近邻规则的简单试探法n最大最小距离

4、算法最近邻规则的简单试探法已知：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基本思路

5、基本思路：以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类；n已知已知：N个待识模式X1，X2，XN，阈值比例系数。最大最小距离算法n任选样本作为第一个聚类中心Z1；n从样本集中选择距离Z1最远的样本Xi作为第二个聚类中心， Z2= Xi，设定阈值：T= |Z1- Z2|；最大最小距离算法n计算未被作为聚类中心的各样本Xi与Z1， Z2之间的距离，以其中的最小值作为该样本的距离di；n若di T，将Xi作为第3个聚类中心， Z3= Xi，转3；否则，转5n按照最小距离原则，将所有样本分到各类别中。 系统聚类法n基本思路基本思路：首先每一个样本自成一类，然后按照距离准则逐步合并，类别数

6、由多到少，达到合适的类别数为止。n已知已知：N个待识模式X1，X2，XN，类别数M。类与类之间的距离n最短距离： min,ijijlkDdXXn最长距离： max,ijijlkDdXXn平均距离： 21,ijijlkijDdN NXX系统聚类算法n第一步 建立N个初始类别，每个样本一个类别，计算距离矩阵D=(Dij)；n第二步 寻找D中的最小元素，合并相应的两个类别，建立新的分类，重新计算距离矩阵D；n重复第二步，直到类别数为M为止。动态聚类法n基本思想基本思想：首先选择若干个样本点作为聚类中心，然后各样本点向各个中心聚集，得到初始分类；判断初始分类是否合理，如果不合理，则修改聚类中心。n包括包括：K-均值算法，ISODATA算法。K-均值算法(C-均值)n第一步：任选K个初始聚类中心；n第二步：将每一个待分类样本分到K个类别中去；n第三步：计算各类的聚类中心；n第四步：检验新的聚类