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

第二章距离分类器和聚类分析2.1距离分类器一、模式的距离度量距离函数应满足的条件对称性：,,ddXYYX,0dXY,,,dddXYXZYZ非负性：三角不等式：常用的距离函数欧几里德距离：(EucideanDistance)1221,niiidxyXY常用的距离函数街市距离：(ManhattanDistance)1,niiidxyXY常用的距离函数明氏距离：(MinkowskiDistance)11,mnmiiidxyXY常用的距离函数角度相似函数：(AngleDistance),TdXYXYXY1nTiiixyXY是X与Y之间的内积X为矢量X的长度，也称为范数二、单个标准样本距离分类器M个类别：12,,,M每个类别有一个标准样本：12MT,T,,T对待识样本X进行分类。建立分类准则如果有：0argmin,iiidXT则判别：0iX距离分类器类别1距离类别2距离类别M距离...最小值选择器待识模式识别结果三、多标准样本的距离分类器M个类别：12,,,M第m个类别有训练样本集合：对待识样本X进行分类。12,,,mmmmKXXX多标准样本的距离分类器平均样本法对每一类求一个标准样本T(m)，使T(m)到所有训练样本的平均距离最小：11mKmmiimKTX平均样本法的特点算法简单存储量小计算量小效果不一定很好平均距离法已知Ωi类有训练样本集：定义待识模式X与类别Ωi的距离：12,,,iiiiKTTT11,,iKiijjiddKXXT最近邻法待识模式X与类别Ωi的距离：1,min,iiijjKddXXT最近邻法的改进平均样本法：用一点代表一个类别，过于集中；最近邻法：以类内的每一点代表类别，过于分散；改进最近邻法：将每个类别的训练样本划分为几个子集，以子集的平均样本作为代表样本。K-近邻法1.计算X与所有训练样本的距离；2.对所计算出的距离从小到大排序；3.统计前K个中各类样本的个数Ni；4.如果：则判别：01argmaxiiMiN0iX2.2聚类分析简单聚类法系统聚类法动态聚类法简单聚类法（试探法）1.最近邻规则的简单试探法2.最大最小距离算法最近邻规则的简单试探法已知：N个待分类模式{X1，X2，…，XN}，阈值T(每个样本到其聚类中心的最大距离)，分类到Ω1，Ω2，…，类别中心为Z1，Z2，…最近邻规则的简单试探法第一步：取任意的样本作为第一个聚类中心，Z1=X1；计算D21=||X2-Z1||；如果D21T，则增加新类别：Z1=X1；否则，X2归入Ω1类，重新计算：Z1=(X1+X2)/2最近邻规则的简单试探法第二步：设已有M个类别，加入样本Xk计算Dk1=||Xk-Z1||，Dk2=||Xk-Z2||…；如果DkiT，则增加新类别ΩM+1ZM+1=Xk；否则，Xk归入最近的一类，重新计算该类的聚类中心：最大最小距离算法基本思路：以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类；已知：N个待识模式{X1，X2，…，XN}，阈值比例系数θ。最大最小距离算法1.任选样本作为第一个聚类中心Z1；2.从样本集中选择距离Z1最远的样本Xi作为第二个聚类中心，Z2=Xi，设定阈值：T=θ||Z1-Z2||；最大最小距离算法3.计算未被作为聚类中心的各样本Xi与Z1，Z2之间的距离，以其中的最小值作为该样本的距离di；4.若diT，将Xi作为第3个聚类中心，Z3=Xi，转3；否则，转55.按照最小距离原则，将所有样本分到各类别中。系统聚类法基本思路：首先每一个样本自成一类，然后按照距离准则逐步合并，类别数由多到少，达到合适的类别数为止。已知：N个待识模式{X1，X2，…，XN}，类别数M。类与类之间的距离最短距离：min,ijijlkDdXX最长距离：max,ijijlkDdXX平均距离：21,ijijlkijDdNNXX系统聚类算法第一步建立N个初始类别，每个样本一个类别，计算距离矩阵D=(Dij)；第二步寻找D中的最小元素，合并相应的两个类别，建立新的分类，重新计算距离矩阵D；重复第二步，直到类别数为M为止。动态聚类法基本思想：首先选择若干个样本点作为聚类中心，然后各样本点向各个中心聚集，得到初始分类；判断初始分类是否合理，如果不合理，则修改聚类中心。包括：K-均值算法，ISODATA算法。K-均值算法(C-均值)第一步：任选K个初始聚类中心；第二步：将每一个待分类样本分到K个类别中去；第三步：计算各类的聚类中心；第四步：检验新的聚类中心与旧的聚类中心是否相等，相等则算法结束；否则转第二步。2.3聚类结果评价类内距离方差：21iMWiiJXXZ类间距离方差：21MBiiJZZ11MiiMZZ各类的样本数