【教学课件】第二章距离分类器和聚类分析.ppt

《【教学课件】第二章距离分类器和聚类分析.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章距离分类器和聚类分析.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、4.如果：5.则判别：2.2 聚类分析聚类分析n简单聚类法 n系统聚类法 n动态聚类法 简单聚类法（试探法）1.最近邻规则的简单试探法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

4、|；如果Dki T，则增加新类别M+1 ZM+1=Xk；否则，Xk归入最近的一类，重新计算该类的聚类中心：最大最小距离算法n基本思路基本思路：以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类；n已知已知：N个待识模式X1，X2，XN，阈值比例系数。最大最小距离算法1.任选样本作为第一个聚类中心Z1；2.从样本集中选择距离Z1最远的样本Xi作为第二个聚类中心，Z2=Xi，设定阈值：T=|Z1-Z2|；最大最小距离算法3.计算未被作为聚类中心的各样本Xi与Z1，Z2之间的距离，以其中的最小值作为该样本的距离di；4.若di T，将Xi作为第3个聚类中心，Z3=Xi，转3；否则，转55.按

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