基于聚类改进的Fisher与KNN判别分类算法对比研究

朱景福 李芳 鹿保鑫

摘要大米中矿物元素种类多（38种），为了快速、准确地筛选出判别大米产地的有效指标，在分析大米矿物元素含量相关性的基础上，进行了大米产地判别分类算法对比实验。首先通过R型聚类方法将大米矿物元素样本进行分块，然后从每一类中选取数据再进行Fisher与KNN判别分类对比，这样可以改进传统算法中剪辑样本带来的判别误差，又大大降低了无效的计算量。实验表明，基于聚类选出一种元素最优组合方案，采用23种矿物元素进行Fisher判别的分类率达86.76%，此方法准确高效地降低了计算机的运算量，提高了判别分类速度。

关键词聚类;Fisher判别;KNN判别;算法对比

中图分类号S126文献标识码A

文章编号0517-6611（2019）01-0250-03

doi：10.3969/j.issn.0517-6611.2019.01.073

开放科学（资源服务）标识码（OSID）：

大米被誉为“五谷之首”，除了含有丰富的碳水化合物外，还含有维生素、蛋白质、脂肪以及多种矿物质，能为人体提供全面的营养[1]。不同产地来源的大米矿物元素含量及组成特征由于受土壤条件、气候条件等影响存在一定的差异，因此矿物元素可作为大米稳定有效的产地标记物。目前传统的分类方法主要有决策树、支持向量机（SVM）、K近邻法（KNN）、Fisher、贝叶斯（NativeBayes）[2]、Boosting、神经网络[3]等。苏毅娟等[4]针对KNN算法无训练过程的特点，提出了一种应用于大数据下的快速KNN分类算法。该算法创新性地在K最近邻算法中引入训练过程，即通过线性复杂度聚类方法对大数据样本进行分块，然后在测试过程中找出与待测样本距离最近的块，并将其作为新的训练样本进行K最近邻分类。樊存佳等[5]针对分类速度和分类精度无法同时兼顾的问题，采用改进的K-Medoids聚类算法裁剪对KNN分类贡献小的训练样本，从而减少KNN相似度的计算量，并定义代表度函数有差别地处理测试文本的K个最近邻文本，以提高KNN的分类精度。周庆平等[6]为了提高传统KNN算法在文本分类中的效率，提出一种基于聚类的改进KNN算法。温俊芹等[7]提出了一种基于线性判别分析和自适应K近邻法的手势识别方法。由于大米中矿物元素种类多（38种），为了快速、准确地筛选出判别大米产地的有效指标，笔者在分析大米矿物元素含量相关性的基础上，进行大米产地判别分类算法对比实验，提出基于聚类的Fisher与KNN判别分类算法，这样可以改进传统算法中剪辑样本带来的判别误差，又大大降低了无效的计算量。

1数据来源

大米矿物元素含量原始数据来源于黑龙江八一农垦大学食品学院，共计136组，每一组分别对38种矿物元素（钠Na、镁Mg、铝Al、钾K、钙Ca、钒V、铬Cr、锰Mn、铁Fe、钴Co、镍Ni、铜Cu、锌Zn、砷As、铷Rb、锶Sr、钌Ru、钯Pd、银Ag、镉Cd、锑Sb、碲Te、铯Cs、钡Ba、镧La、镨Pr、钕Nd、钐Sm、钆Gd、镝Dy、钬Ho、铒Er、镱Yb、铪Hf、铂Pt、铅Pb、钍Th、铀U）含量进行了测定，38种矿物元素序号记为1～38。进行矿物元素检测的大米来源于黑龙江5个不同的产地，分别为方正县、五常市、查哈阳农场、建三江农垦管理局、宁安县，并分别有28、31、32、25、20批次。部分矿物元素含量測定原始记录如表1所示。

该研究对应的实验中，训练集选取68组数据，其中方正、五常、查哈阳、建三江、响水的样本分别为14、15、16、13、10组;样本集选取68组数据，其中方正、五常、查哈阳、建三江、响水的样本分别为14、16、16、12、10组。

2矿物元素含量聚类分析

由于在大米中矿物元素含量可能具有一定的相关性，因此先采用R型聚类对原始数据进行聚类。首先对原始数据进行标准化转换，标准化方法如公式（1）所示：

Zij=Xij-jSj（1）

其中，j是Xj的均值，j=1nni=1Zij;Sj是Xj的标准差，Sj=1nni=1（Zij-j）2，该研究采用类平均法进行聚类，得到聚类结果如图1所示。

由图1可知，26、27、25、28、29号等元素首先聚为一类，即它们之间的相关性最强，而22号元素最后才聚在一起，说明其与其他元素的相关性最差，也就是最具特征表达能力。

3Fisher线性判别与KNN分类判别对比

3.1Fisher线性判别Fisher线性判别的基本思想就是把空间中的数据点投影到一条直线上去，使得不同类别的样本点在空间中能够形成互相分离的且各自内部紧凑的集合。为了达到这样的分类效果，必须选择一个合适的投影直线，以最大限度地区分各类数据点的投影方向[8]。当高维数据向该方向投影时，使样本的类间离散度Sb与类内离散度Sw的比值最大。假设共有k个类别，x（i）j表示第i类中的第j个样本，样本的类内离散度矩阵Sw表示为：

Sw=1Nki=1Nii=1〔x（i）j-x（i）〕〔x（i）j-x（i）〕T（2）

其中，x（i）表示第i类样本的均值;Ni表示第i类的样本数;N表示样本总数，即N=ki=1Ni。

对于该样本，类间离散度矩阵Sb可以表示为：

Sb=1Nki=1Ni〔x（i）-〕〔x（i）-〕T（3）

其中，类别数为k;x（i）表示第i类样本的均值;为所有样本的平均值。Fisher线性判别的准则函数定义为J（W）=|WTSbW||WTSwW|。如果类间离散度越大、类内离散度越小，则类别的可分离性越好，越容易进行分类。使函数J（W）达到最大值的向量W*，就是要求的最佳向量。W*可以通过建立拉格朗日函数进行求解。求出W*后，再计算阈值Y0，就可以确定线性判别函数f（x）。然后输入任意的高维样本X，就可以进行分类。

3.2KNN分类判别KNN（K-nearestneighbor）分类算法作为一种简单、高效和无参数的数据分类方法，由Cover等在1968年提出，这是一种理论上比较成熟的算法。KNN的核心思想是计算待分类样本与已知训练样本的欧氏距离或余弦相似度，找到与待分类样本距离最近或者相似度最大的K个最近邻样本，再根据K个最近邻样本的类别来判断待分类样本的类别[7]，简单地说，K个最近邻文本中大多数属于某个类别，则样本也属于这个类别[8]。

3.3对原始数据进行判别分析首先针对原始数据采用Fisher线性判别和KNN判别进行分类，Fisher线性判别正识率为91.78%，当N取不同值时，KNN判别正识率对比结果如表2所示。

Fisher判别的效果优于KNN判别，说明待分类样本的几类总体间的均值差异相对比较明显。KNN判别，与N的取值关系不大，因此该研究之后采用KNN判别分类时，均采用N=2。

3.4基于R型聚类的Fisher与KNN判别分析

根据前述R型聚类，当聚类成N类时，每一类内的成分之间具有较强的相关性，类间成分间相关性较弱，从每一类中选取1个作为代表进行判别分析，N取15～33时，代表性矿物元素变化见表3。

针对选取的代表性矿物元素，从原始数据中选取相应的数据进行判别分析，比如选取15类时，只选其中序号为1、2、3、7、8、11、14、17、18、19、21、22、24、25、35的矿物元素含量进行判别分析，以后逐次增加1个新类的代表，Fisher与KNN判别分类的正识率如表4所示，选取15～33类代表元素正识率变化如图2所示。

由表4和图2可知，当代表性矿物元素选取23类左右时，正识率可为80%以上，最接近于使用原始数据时的效果。

4最优元素选取研究

对于聚类成23类的分类结果，由于每一类内可能有多个相关性较强的成分，23类元素中1个元素自成1类的有5、6、13、10、21、34、3、24、36、7、17、18、19、35、14、22共16类，2成分构成1类的分别有（37、38），（11、12），（15、23），（8、20）和（2、4）共5类，3成分构成1类的有（1、9、16），其他（25、26、27、28、29、30、31、32、33）成1类。由于每一类中选取1个代表，会有多种组合，每1种组合可能在效果上还会有细微差别，因此研究如何确定一个最优成分选取方案，以使正识率达到最大。可选方案数共有864种，每种组合对应的正识率如图3所示，Fisher判别分类中达到最高识别率（86.76%，略低于直接针对原始数据的正识率91.78%）的共28组，从28组中每列选取出现次数最多的作为代表。得到选取方案按从小到大排序为3（Al）、4（K）、5（Ca）、6（V）、7（Cr）、8（Mn）、10（Co）、11（Ni）、13（Zn）、14（As）、15（Rb）、16（Sr）、17（Ru）、18（Pd）、19（Ag）、21（Sb）、22（Te）、24（Ba）、31（Ho）、34（Hf）、35（Pt）、36（Pb）、37（Th）。

5结论

该研究均采用Matlab7.1编程语言，试验结果表明，

Fisher判别的正识率要高于KNN判别，同时，基于R型聚类

从每一类中选取数据进行判别分析，选出一种最优元素组合

方案，可以只利用38种矿物元素中的23种进行判别，数据量和化验工作量都大幅度减少，正识率并没有明显降低。

参考文献

[1]付亭亭，贾健斌，尹岩，等.可追溯大米的消费行为研究[J].食品科技，2015，40（2）：360-367.

[2]杨昕薇，谭峰.基于贝叶斯分类器的水稻病害识别处理的研究[J].黑龙江八一农垦大学学报，2012，24（3）：64-67，79.

[3]仝志民，荣丽红，孟耀华，等.基于过程神经网络的农作物生长预测算法研究[J].黑龙江八一农垦大学学报，2013，25（3）：85-87，101.

[4]苏毅娟，邓振云，程德波，等.大数据下的快速KNN分类算法[J].计算机应用研究，2016，33（4）：1003-1006，1023.

[5]樊存佳，汪友生，边航.一种改进的KNN文本分类算法[J].国外电子测量技术，2015，34（12）：39-43.

[6]周庆平，谭长庚，王宏君，等.基于聚类改进的KNN文本分类算法[J].计算机应用研究，2016，33（11）：3374-3377，3382.

[7]溫俊芹，王修晖.基于线性判别分析和自适应K近邻法的手势识别[J].数据采集与处理，2017，32（3）：643-648.

[8]石欣，印爱民，张琦.基于K最近邻分类的无线传感器网络定位算法[J].仪器仪表学报，2014，35（10）：2238-2247.