法及其衍生方法

8.4.1　KNN法及其衍生方法

KNN（KNearest Neighbor）法，亦称K最近邻法，是模式识别有监督分类方法的标准算法之一。其基本思想是先将已分好类别的训练样本点“记入”多维空间中，然后将待分类的未知样本亦记入空间。考察未知样本点的K个近邻（K为单整数），若近邻某一类样本最多，则可将未知样本判为该类。其基本假设是“同类样本在模式空间中相互较靠近”。在多维空间中，各类间的距离通常规定为欧氏距离。

为了进行定量判别，可先找出待分类样本的最近邻，并事先约定最近邻区域中的训练集样本数。如果只取一个最近邻样本点，即样本数为1，则称1 NN法；如果取3个最近邻样本点，即样本数为3，则称3 NN法；如果样本数为K，则称K近邻法，简称KNN法。为了找到这个含有K个训练集中的样本的最近邻，需要计算该未知样本点和所有训练集样本点之间的距离。然后从最小距离开始计样本数，一直计到有K个样本数为止，此时所对应的距离就为最近邻的最小距离。如果在这个最小距离中，距某一类训练集中的样本数多，距离又小，则可将待分类样本划到该类中。

此法对数据结构无特殊要求，简单易行，不需要训练过程，但未对训练点进行信息压缩，因此每判断一个点都要将其对所有已知点的距离全部算一遍，计算工作量较大。

一种简化的算法称为类重心法，即将训练集中每类样本点的重心求出，然后判别未知样本点与各类重心的距离。未知样本点距哪一类重心距离最近，未知样本就属于哪一类。这一方法有时可使结果可靠性降低。

若用几个特征对模式进行分类，则对一个g类问题，第j类模式的重心为c_j（c_j1，c_j2，…，c_jp）

其中i是特征序号，j为类序号，n_j是第j类模式的样本数目。

例8－6　有两种地层，用7种指标的分析数据判别，先从已经准确判断的地层中各取9个样本，测得的数据见表8－3（a）。

表8－3（a）　不同地层的样本的原始分析数据

由于表8－3（a）中各变量的量级相差10²，对表中变量求自然对数后得下列数据矩阵

表8－3（b）　求自然对数后的不同地层样本数据

续表

然后计算两类的重心得

地层Ⅰ、Ⅱ的每一个矢量与C₁和C₂的欧氏距离分别如表8－4（a）和表8－4（b）所示。

表8－4（a）　地层Ⅰ的样本到两个地层类重心的欧氏距离

表8－4（b）　地层Ⅱ的样本到两个地层类重心的欧氏距离

从上面两个表中可以看出，1～9号样本距C₁的距离均小于距C₂的距离，应属于地层Ⅰ；而10～18号样本除样本11外，其余样本距C₂的距离均小于距C₁的距离，应属于地层Ⅱ。因此，本例采用简化的KNN方法类重心法对绝大部分样本均能正确分类。

将表8－3（a）的数据导入矩阵X中，本例的MATLAB命令如下

XG＝log（X）

%对X中的数据求自然对数，XG即为表8－3（b）

C1＝mean（XG（1：9，：））

%求地层Ⅰ中各列的均值并赋给向量C1，C1即地层Ⅰ的类重心

C2＝mean（XG（10：18，：））

%求地层Ⅱ中各列的均值并赋给向量C2，C2即地层Ⅱ的类重心

%求每个样本到地层Ⅰ类重心C1的欧氏距离并赋给d1，d1即为表8－4（a）与表8－4（b）的第1行

%求每个样本到地层Ⅱ类重心C2的欧氏距离并赋给d2，d2即为表8－4（a）与表8－4（b）的第2行

例8－7　以表8－3（b）为基础，采用马氏距离分析18个样本到两个地层重心的距离。

解：根据式（8－9）可知求马氏距离需要求数据矩阵XG的协方差矩阵Z的逆矩阵Z－1，有必要先考察一下矩阵Z是否奇异。在MATLAB下输入命令

＞＞Z＝cov（XG）；%求XG中的7个变量的协方差矩阵Z，Z是一个7×7的矩阵

＞＞det（Z）%求Z的行列式值

可得

ans＝5.8095e－008

显然，Z是一个奇异矩阵，求表8－3（b）中的7个变量间的相关系数，在MATLAB下输入

r＝corrcoef（XG）

可得

从上面矩阵可知，变量x₇与变量x₁之间有很强的相关性，其相关系数r（1，7）＝r（7，1）＝0.906；而r（1，6）＝r（6，1）＝0.704，说明变量x₁与变量x₆间也有较强的相关性。这3个变量间存在的强线性相关及较强的线性相关使得XG的协方差矩阵Z是个奇异矩阵。

在模式识别时，所选的模式特征应该是独立的，即各模式特征之间应当互不相关。变量间的强相关会导致马氏距离的计算不准确或无法进行。本例采用第6章介绍的主成分分析方法对表8－3（b）中的数据进行信息压缩，采用独立的主成分替代表8－3（b）中的7个变量后再计算各样本到两个地层中心的距离。

MATLAB命令如下

［pc，sc，lm］＝princomp（XG）；

%对XG进行主成分分析，sc为主成分得分矩阵，lm为XG的协方差矩阵的特征值，即对应主成分得分的方差

yt＝cumsum（lm）./sum（lm）

%求累积贡献率向量yt，yt的第j个元素为第j个主成分的累计贡献率，yt为含有7个元素的列向量

T＝sc（：，1：6）；

%将前6个主成分得分赋给矩阵T，T为一18×6的矩阵

lmd＝lm（1：6）

%将前6个主成分得分的方差赋给向量lmd，lmd为一行向量

T1＝mean（T（1：9，：））

%求地层Ⅰ的前6个主成分得分的平均值T1，T1为含有6个变量的行向量

T2＝mean（T（10：18，：））

%求地层Ⅱ的前6个主成分得分的平均值T2，T2为含有6个变量的行向量

md1＝sqrt（sum（（T－repmat（T1，18，1））.2./repmat（lmd，18，1），2））

%求18个样本到地层Ⅰ类重心的马氏距离md1，md1为含有18个变量的行向量

md2＝sqrt（sum（（T－repmat（T2，18，1））.2./repmat（lmd，18，1），2））

%求18个样本到地层Ⅱ类重心的马氏距离md2，md2为含有18个变量的行向量

上述MATLAB命令运行结果如下

yt＝

0.43502

0.68107

0.82906

0.95432

0.98752

0.9999

1

由此可以确定取6个主成分即可反映99.99%矩阵XG的信息。

lmd＝

T1、T2即为地层Ⅰ、Ⅱ用主成分得分表示的类重心坐标。

打开向量md1与md2可得下表所示的18个样本到地层Ⅰ、Ⅱ类中心的马氏距离。表8－5（a）中的9个样本到地层Ⅰ类重心的马氏距离均小于到地层Ⅱ类中心的马氏距离；表8－5（b）的9个样本到地层Ⅰ类重心的马氏距离均大于到地层Ⅱ类中心的马氏距离。

表8－5（a）　地层Ⅰ的样本到两个地层重心的马氏距离

表8－5（b）　地层Ⅱ的样本到两个地层重心的马氏距离

由此可看出，采用主成分分析消除原始数据矩阵［表8－3（b）］中变量间的相关性后，以主成分得分为基础所求各样本到各地层类重心的马氏距离与个样本自身所属的地层情况相符。

简化的KNN算法的通用和完整的M文件及其应用本例数据运算例子见附录3，读者可以采用本例命令或附录3中的M文件验证本例。