330 智能系统学报 第6卷 需满足：SW=入SW.若S非奇异，则SS。W= 图4表明，输人的120幅40维向量训练样本经 AW,W每一列由SS。的前c-1个较大特征值对 LDA降维到二维空间后，分类特征明显.因此，在二维 应的特征向量构成，从而得到最佳降维向量W,图3 空间设计分类器便可对未标定路况的样本进行分类 给出了对二维样本进行LDA降维的示意图. 3基于K-近邻改进算法的分类 3.1K-近邻(K-NN)算法 K-近邻(K-nearest neighborhood)算法是分类未 最佳降维 知数据最直接的方法，其基本思想是：找到和待分类 样本最相似的k个已分类样本，根据这k个样本所 属类别判断待分类样本所属类别，如图5所示.对于 一个待分类样本，计算其与训练样本中每一样本的 欧式距离（见式(4）)，找出与待分类样本最近的k 图3二维样本LDA降维示意 个近邻，依据k个近邻在每类中所占比重，将待分类 Fig.3 Using LDA in two dimensional space 样本归入所占比重最大的类别. 2.2LDA应用设计 d,(x)=√(x-4)(x-) (4) 本文中，将路况图像的40维向量看作高维向 式中：x为待分类样本丛为训练样本中第i个样本 量，使用LDA算法对该向量进行降维.由于已知路 况类别为3类，降维后，该向量被降到二维空间.在 0.25 ,畅遇+缓行△拥堵 降维后的二维空间（图4）中，可以看到数据分布具 0.20 待分类样本 有最佳可分离性， 0.15 使用LDA算法时，训练样本个数选取不应过 0.10 少.当输入训练样本个数小于样本维数时，会使类内 0.05 离散度S,非奇异，而无法构造降维向量W;如果训 0 练样本个数过多，会增大计算复杂度，影响LDA降 -0.05 维速度，综合考虑如上问题，选取120幅典型路况图 -0.10 0. 0.1 0.2 0.3 像作为训练样本，这些路况图像为同一地点、不同时 段、不同路况的样本，并标定每幅样本的路况，即已 图5K-近邻算法示意 知样本分类信息为：畅通样本40幅，缓行样本40 Fig.5 K-NN algorithm 幅，拥堵样本40幅.将每幅样本灰度直方图的40个 本文选取与训练样本不同的120幅标定路况样 采样点作为40维向量，进行LDA降维.由已知的样 本作为待分类样本进行测试.其中，畅通样本40幅， 本分类信息为3类，构造列数为2的最佳降维向量 缓行样本40幅，拥堵样本40幅，使用传统K-近邻 W,图4给出了120幅训练样本经LDA降维到2维 算法对路况样本进行分类，比较分类结果与标定结 空间的分布情况， 果，在表1中给出统计情况。 表1K-近邻算法分类结果统计 0.25 Table 1 Results of using K-NN algorithm ·畅遇+缓行△拥堵 0.20 分类结果符合标定幅数不符合标定幅数一致率/% LDA降维空间 0.15 畅通 % 5 85.7 0.10 缓行 37 11 77.1 0.05 拥堵 31 6 83.8 0 + -0.05 3.2对K-近邻(K-NN)算法的改进 -0.10 K-近邻算法中计算了待分类样本与所有训练样 -0.1 0.1 0.20.3 本的欧式距离，事实上仅使用了其中较小的个样 本作为分类依据.为了充分利用训练样本，本文将统 图4训练样本经LDA降维后在二维空间分布 Fig.4 Train-samples in two dimensional space after LDA 计3类别内所有距离和作为分类依据，将当前样本