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

1、第二章 距离分类器和 聚类分析,2.1 距离分类器,一、模式的距离度量,距离函数应满足的条件,对称性：,非负性：,三角不等式：,常用的距离函数,欧几里德距离：(Eucidean Distance),常用的距离函数,街市距离：(Manhattan Distance),常用的距离函数,明氏距离：(Minkowski Distance),常用的距离函数,角度相似函数：(Angle Distance),是X与Y之间的内积,为矢量X的长度，也称为范数,二、单个标准样本距离分类器,M个类别：,每个类别有一个标准样本：,对待识样本X进行分类。,建立分类准则,如果有：,则判别：,距离分类器,三、多标准样本的距

2、离分类器,M个类别：,第m个类别有训练样本集合：,对待识样本X进行分类。,多标准样本的距离分类器,平均样本法 对每一类求一个标准样本T(m)，使T(m)到所有训练样本的平均距离最小：,平均样本法的特点,算法简单 存储量小 计算量小 效果不一定很好,平均距离法,已知i类有训练样本集：,定义待识模式X与类别i的距离：,最近邻法,待识模式X与类别i的距离：,最近邻法的改进,平均样本法：用一点代表一个类别，过于集中； 最近邻法：以类内的每一点代表类别，过于分散； 改进最近邻法：将每个类别的训练样本划分为几个子集，以子集的平均样本作为代表样本。,K-近邻法,计算X与所有训练样本的距离； 对所计算出的距离

3、从小到大排序； 统计前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个类别，加入样

4、本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，将

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