朱景福 李芳 鹿保鑫

摘要大米中礦物元素種類多（38種），為了快速、準(zhǔn)確地篩選出判別大米產(chǎn)地的有效指標(biāo)，在分析大米礦物元素含量相關(guān)性的基礎(chǔ)上，進(jìn)行了大米產(chǎn)地判別分類算法對(duì)比實(shí)驗(yàn)。首先通過R型聚類方法將大米礦物元素樣本進(jìn)行分塊，然后從每一類中選取數(shù)據(jù)再進(jìn)行Fisher與KNN判別分類對(duì)比，這樣可以改進(jìn)傳統(tǒng)算法中剪輯樣本帶來的判別誤差，又大大降低了無效的計(jì)算量。實(shí)驗(yàn)表明，基于聚類選出一種元素最優(yōu)組合方案，采用23種礦物元素進(jìn)行Fisher判別的分類率達(dá)86.76%，此方法準(zhǔn)確高效地降低了計(jì)算機(jī)的運(yùn)算量，提高了判別分類速度。

關(guān)鍵詞聚類;Fisher判別;KNN判別;算法對(duì)比

中圖分類號(hào)S126文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)0517-6611（2019）01-0250-03

doi：10.3969/j.issn.0517-6611.2019.01.073

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

大米被譽(yù)為“五谷之首”，除了含有豐富的碳水化合物外，還含有維生素、蛋白質(zhì)、脂肪以及多種礦物質(zhì)，能為人體提供全面的營養(yǎng)[1]。不同產(chǎn)地來源的大米礦物元素含量及組成特征由于受土壤條件、氣候條件等影響存在一定的差異，因此礦物元素可作為大米穩(wěn)定有效的產(chǎn)地標(biāo)記物。目前傳統(tǒng)的分類方法主要有決策樹、支持向量機(jī)（SVM）、K近鄰法（KNN）、Fisher、貝葉斯（NativeBayes）[2]、Boosting、神經(jīng)網(wǎng)絡(luò)[3]等。蘇毅娟等[4]針對(duì)KNN算法無訓(xùn)練過程的特點(diǎn)，提出了一種應(yīng)用于大數(shù)據(jù)下的快速KNN分類算法。該算法創(chuàng)新性地在K最近鄰算法中引入訓(xùn)練過程，即通過線性復(fù)雜度聚類方法對(duì)大數(shù)據(jù)樣本進(jìn)行分塊，然后在測(cè)試過程中找出與待測(cè)樣本距離最近的塊，并將其作為新的訓(xùn)練樣本進(jìn)行K最近鄰分類。樊存佳等[5]針對(duì)分類速度和分類精度無法同時(shí)兼顧的問題，采用改進(jìn)的K-Medoids聚類算法裁剪對(duì)KNN分類貢獻(xiàn)小的訓(xùn)練樣本，從而減少KNN相似度的計(jì)算量，并定義代表度函數(shù)有差別地處理測(cè)試文本的K個(gè)最近鄰文本，以提高KNN的分類精度。周慶平等[6]為了提高傳統(tǒng)KNN算法在文本分類中的效率，提出一種基于聚類的改進(jìn)KNN算法。溫俊芹等[7]提出了一種基于線性判別分析和自適應(yīng)K近鄰法的手勢(shì)識(shí)別方法。由于大米中礦物元素種類多（38種），為了快速、準(zhǔn)確地篩選出判別大米產(chǎn)地的有效指標(biāo)，筆者在分析大米礦物元素含量相關(guān)性的基礎(chǔ)上，進(jìn)行大米產(chǎn)地判別分類算法對(duì)比實(shí)驗(yàn)，提出基于聚類的Fisher與KNN判別分類算法，這樣可以改進(jìn)傳統(tǒng)算法中剪輯樣本帶來的判別誤差，又大大降低了無效的計(jì)算量。

1數(shù)據(jù)來源

大米礦物元素含量原始數(shù)據(jù)來源于黑龍江八一農(nóng)墾大學(xué)食品學(xué)院，共計(jì)136組，每一組分別對(duì)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）含量進(jìn)行了測(cè)定，38種礦物元素序號(hào)記為1～38。進(jìn)行礦物元素檢測(cè)的大米來源于黑龍江5個(gè)不同的產(chǎn)地，分別為方正縣、五常市、查哈陽農(nóng)場(chǎng)、建三江農(nóng)墾管理局、寧安縣，并分別有28、31、32、25、20批次。部分礦物元素含量測(cè)定原始記錄如表1所示。

該研究對(duì)應(yīng)的實(shí)驗(yàn)中，訓(xùn)練集選取68組數(shù)據(jù)，其中方正、五常、查哈陽、建三江、響水的樣本分別為14、15、16、13、10組;樣本集選取68組數(shù)據(jù)，其中方正、五常、查哈陽、建三江、響水的樣本分別為14、16、16、12、10組。

2礦物元素含量聚類分析

由于在大米中礦物元素含量可能具有一定的相關(guān)性，因此先采用R型聚類對(duì)原始數(shù)據(jù)進(jìn)行聚類。首先對(duì)原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化轉(zhuǎn)換，標(biāo)準(zhǔn)化方法如公式（1）所示：

Zij=Xij-jSj（1）

其中，j是Xj的均值，j=1nni=1Zij;Sj是Xj的標(biāo)準(zhǔn)差，Sj=1nni=1（Zij-j）2，該研究采用類平均法進(jìn)行聚類，得到聚類結(jié)果如圖1所示。

由圖1可知，26、27、25、28、29號(hào)等元素首先聚為一類，即它們之間的相關(guān)性最強(qiáng)，而22號(hào)元素最后才聚在一起，說明其與其他元素的相關(guān)性最差，也就是最具特征表達(dá)能力。

3Fisher線性判別與KNN分類判別對(duì)比

3.1Fisher線性判別Fisher線性判別的基本思想就是把空間中的數(shù)據(jù)點(diǎn)投影到一條直線上去，使得不同類別的樣本點(diǎn)在空間中能夠形成互相分離的且各自內(nèi)部緊湊的集合。為了達(dá)到這樣的分類效果，必須選擇一個(gè)合適的投影直線，以最大限度地區(qū)分各類數(shù)據(jù)點(diǎn)的投影方向[8]。當(dāng)高維數(shù)據(jù)向該方向投影時(shí)，使樣本的類間離散度Sb與類內(nèi)離散度Sw的比值最大。假設(shè)共有k個(gè)類別，x（i）j表示第i類中的第j個(gè)樣本，樣本的類內(nèi)離散度矩陣Sw表示為：

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

其中，x（i）表示第i類樣本的均值;Ni表示第i類的樣本數(shù);N表示樣本總數(shù)，即N=ki=1Ni。

對(duì)于該樣本，類間離散度矩陣Sb可以表示為：

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

其中，類別數(shù)為k;x（i）表示第i類樣本的均值;為所有樣本的平均值。Fisher線性判別的準(zhǔn)則函數(shù)定義為J（W）=|WTSbW||WTSwW|。如果類間離散度越大、類內(nèi)離散度越小，則類別的可分離性越好，越容易進(jìn)行分類。使函數(shù)J（W）達(dá)到最大值的向量W*，就是要求的最佳向量。W*可以通過建立拉格朗日函數(shù)進(jìn)行求解。求出W*后，再計(jì)算閾值Y0，就可以確定線性判別函數(shù)f（x）。然后輸入任意的高維樣本X，就可以進(jìn)行分類。

3.2KNN分類判別KNN（K-nearestneighbor）分類算法作為一種簡(jiǎn)單、高效和無參數(shù)的數(shù)據(jù)分類方法，由Cover等在1968年提出，這是一種理論上比較成熟的算法。KNN的核心思想是計(jì)算待分類樣本與已知訓(xùn)練樣本的歐氏距離或余弦相似度，找到與待分類樣本距離最近或者相似度最大的K個(gè)最近鄰樣本，再根據(jù)K個(gè)最近鄰樣本的類別來判斷待分類樣本的類別[7]，簡(jiǎn)單地說，K個(gè)最近鄰文本中大多數(shù)屬于某個(gè)類別，則樣本也屬于這個(gè)類別[8]。

3.3對(duì)原始數(shù)據(jù)進(jìn)行判別分析首先針對(duì)原始數(shù)據(jù)采用Fisher線性判別和KNN判別進(jìn)行分類，F(xiàn)isher線性判別正識(shí)率為91.78%，當(dāng)N取不同值時(shí)，KNN判別正識(shí)率對(duì)比結(jié)果如表2所示。

Fisher判別的效果優(yōu)于KNN判別，說明待分類樣本的幾類總體間的均值差異相對(duì)比較明顯。KNN判別，與N的取值關(guān)系不大，因此該研究之后采用KNN判別分類時(shí)，均采用N=2。

3.4基于R型聚類的Fisher與KNN判別分析

根據(jù)前述R型聚類，當(dāng)聚類成N類時(shí)，每一類內(nèi)的成分之間具有較強(qiáng)的相關(guān)性，類間成分間相關(guān)性較弱，從每一類中選取1個(gè)作為代表進(jìn)行判別分析，N取15～33時(shí)，代表性礦物元素變化見表3。

針對(duì)選取的代表性礦物元素，從原始數(shù)據(jù)中選取相應(yīng)的數(shù)據(jù)進(jìn)行判別分析，比如選取15類時(shí)，只選其中序號(hào)為1、2、3、7、8、11、14、17、18、19、21、22、24、25、35的礦物元素含量進(jìn)行判別分析，以后逐次增加1個(gè)新類的代表，F(xiàn)isher與KNN判別分類的正識(shí)率如表4所示，選取15～33類代表元素正識(shí)率變化如圖2所示。

由表4和圖2可知，當(dāng)代表性礦物元素選取23類左右時(shí)，正識(shí)率可為80%以上，最接近于使用原始數(shù)據(jù)時(shí)的效果。

4最優(yōu)元素選取研究

對(duì)于聚類成23類的分類結(jié)果，由于每一類內(nèi)可能有多個(gè)相關(guān)性較強(qiáng)的成分，23類元素中1個(gè)元素自成1類的有5、6、13、10、21、34、3、24、36、7、17、18、19、35、14、22共16類，2成分構(gòu)成1類的分別有（37、38），（11、12），（15、23），（8、20）和（2、4）共5類，3成分構(gòu)成1類的有（1、9、16），其他（25、26、27、28、29、30、31、32、33）成1類。由于每一類中選取1個(gè)代表，會(huì)有多種組合，每1種組合可能在效果上還會(huì)有細(xì)微差別，因此研究如何確定一個(gè)最優(yōu)成分選取方案，以使正識(shí)率達(dá)到最大?？蛇x方案數(shù)共有864種，每種組合對(duì)應(yīng)的正識(shí)率如圖3所示，F(xiàn)isher判別分類中達(dá)到最高識(shí)別率（86.76%，略低于直接針對(duì)原始數(shù)據(jù)的正識(shí)率91.78%）的共28組，從28組中每列選取出現(xiàn)次數(shù)最多的作為代表。得到選取方案按從小到大排序?yàn)?（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結(jié)論

該研究均采用Matlab7.1編程語言，試驗(yàn)結(jié)果表明，

Fisher判別的正識(shí)率要高于KNN判別，同時(shí)，基于R型聚類

從每一類中選取數(shù)據(jù)進(jìn)行判別分析，選出一種最優(yōu)元素組合

方案，可以只利用38種礦物元素中的23種進(jìn)行判別，數(shù)據(jù)量和化驗(yàn)工作量都大幅度減少，正識(shí)率并沒有明顯降低。

參考文獻(xiàn)

[1]付亭亭，賈健斌，尹巖，等.可追溯大米的消費(fèi)行為研究[J].食品科技，2015，40（2）：360-367.

[2]楊昕薇，譚峰.基于貝葉斯分類器的水稻病害識(shí)別處理的研究[J].黑龍江八一農(nóng)墾大學(xué)學(xué)報(bào)，2012，24（3）：64-67，79.

[3]仝志民，榮麗紅，孟耀華，等.基于過程神經(jīng)網(wǎng)絡(luò)的農(nóng)作物生長(zhǎng)預(yù)測(cè)算法研究[J].黑龍江八一農(nóng)墾大學(xué)學(xué)報(bào)，2013，25（3）：85-87，101.

[4]蘇毅娟，鄧振云，程德波，等.大數(shù)據(jù)下的快速KNN分類算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33（4）：1003-1006，1023.

[5]樊存佳，汪友生，邊航.一種改進(jìn)的KNN文本分類算法[J].國外電子測(cè)量技術(shù)，2015，34（12）：39-43.

[6]周慶平，譚長(zhǎng)庚，王宏君，等.基于聚類改進(jìn)的KNN文本分類算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33（11）：3374-3377，3382.

[7]溫俊芹，王修暉.基于線性判別分析和自適應(yīng)K近鄰法的手勢(shì)識(shí)別[J].數(shù)據(jù)采集與處理，2017，32（3）：643-648.

[8]石欣，印愛民，張琦.基于K最近鄰分類的無線傳感器網(wǎng)絡(luò)定位算法[J].儀器儀表學(xué)報(bào)，2014，35（10）：2238-2247.