孫逸，安博文，朱昌明

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

隨著全世界物流的快速發(fā)展，我國的航運(yùn)物流業(yè)也得到了迅速發(fā)展，繁忙的航運(yùn)物流帶來了大量的空氣污染。在我國港口船舶碼頭，船舶尾氣排放污染愈加嚴(yán)重，而大型港口大多集中在人口密集的發(fā)達(dá)城市和沿江城市，如長江三角洲，長江沿岸重慶和武漢等地區(qū)和城市。船舶排放的廢氣籠罩港口城市對(duì)人類帶來巨大危害，加大航運(yùn)污染治理刻不容緩[1]。近年來，雖然我國的海事局危管防污處、船舶安全檢查處和各辦事處加強(qiáng)了現(xiàn)場(chǎng)執(zhí)法過程中的對(duì)燃油質(zhì)量、供受油單證、記錄文書等控制區(qū)相關(guān)要求內(nèi)容的檢查，并視情況進(jìn)行燃油取樣。但是，抽取燃油樣品后送交第三方檢驗(yàn)部門進(jìn)行化驗(yàn)分析，以油樣的相關(guān)指標(biāo)參數(shù)（主要是SO2和NOx的濃度）作為船舶是否排放超標(biāo)的依據(jù)，獲得檢查結(jié)果一般需要兩天以上，檢查目標(biāo)比較隨機(jī)，針對(duì)性不強(qiáng)，效率相對(duì)較低。所以海事執(zhí)法部門為了快速檢測(cè)油品，從船舶尾氣作為切入點(diǎn)，采用搭載氣體傳感器的無人機(jī)檢測(cè)船舶尾氣中的硫化物和氮化物的濃度。因此，氣體傳感器對(duì)檢測(cè)氣體的準(zhǔn)確率和速率尤為的重要。近靠單一的氣體傳感器對(duì)船舶尾氣中含有的多種混合氣體的選擇性的效果是十分差的，為了解決這個(gè)困難，采用多傳感器對(duì)氣體信息進(jìn)行模式識(shí)別處理，以此提高對(duì)船舶尾氣中的污染氣體的識(shí)別的準(zhǔn)確性。

目前，用于氣體的模式識(shí)別有很多種。主要有聚類分析法[2]（Cluster Analysis，CA）、判別分析法[3]（Dis?criminant Analysis，DA）、最 近領(lǐng) 域 法[3]（K-Nearest Neighbour，KNN）以及人工神經(jīng)網(wǎng)絡(luò)[5]算法等。其最終的目標(biāo)都是通過信息的處理來更加準(zhǔn)確的對(duì)氣體進(jìn)行分類。但是通常傳感器檢測(cè)的數(shù)據(jù)緯度很高，數(shù)據(jù)量又很大。普通的KNN算法計(jì)算量很大，人工神經(jīng)網(wǎng)絡(luò)計(jì)算時(shí)間又很長，無法兼顧高效率和準(zhǔn)確率。通過理論研究，本文提出利用主成分分析法（Principal Compo?nent Analysis,PAC）可以對(duì)氣體數(shù)據(jù)先進(jìn)行降維，然后對(duì)降維后的氣體數(shù)據(jù)再進(jìn)行C-均值聚類[4]，減少訓(xùn)練樣本的存儲(chǔ)空間，再采用傳統(tǒng)的KNN算法將待檢測(cè)的船舶尾氣進(jìn)行識(shí)別。通過實(shí)驗(yàn)驗(yàn)證發(fā)現(xiàn)，該算法對(duì)船舶尾氣的分類具有很好的準(zhǔn)確性的同時(shí)，減少了算法的計(jì)算時(shí)間，提高了船舶尾氣識(shí)別工作效率。

1 算法理論

1.1 KNN算法

KNN算法是基于統(tǒng)計(jì)的分類算法[7]。在氣體傳感器中也有廣泛的應(yīng)用。KNN算法基本思想：在樣本中分為兩類，其中一類為訓(xùn)練樣本，另一類為測(cè)試樣本。計(jì)算未知?dú)怏w樣本與已知?dú)怏w樣本之間的距離，得到K個(gè)近鄰，根據(jù)已知?dú)怏w樣本所屬的類別來判斷測(cè)試氣體樣本所屬的類別。產(chǎn)生兩種結(jié)果：（1）K個(gè)近鄰屬于已經(jīng)分類號(hào)的某個(gè)氣體，那么待分類的氣體屬于那個(gè)氣體類別[8]；（2）氣體分類結(jié)果屬于多個(gè)氣體類別，那么以K個(gè)近鄰中占多數(shù)的氣體類別作為帶分類氣體的類別，即少數(shù)服從多數(shù)原則。

對(duì)于船舶尾氣中的SO2和NOx分類問題，使用KNN算法分類可分為以下幾個(gè)步驟：

（1）帶標(biāo)簽類別的樣本訓(xùn)練集可以表示為：其中m表示屬于m維空間，樣本標(biāo)簽Yj∈{+1,-1}。對(duì)于無標(biāo)簽類別的未知?dú)怏w樣本可以表示為：

（2）一般參數(shù)設(shè)置為K，可根據(jù)試驗(yàn)結(jié)果反復(fù)調(diào)整至最優(yōu)K值。

（3）計(jì)算訓(xùn)練氣體樣本和測(cè)試氣體樣本的距離，對(duì)于實(shí)際船舶尾氣問題，可以采用歐氏距離,公式如下：

其中分別表示已知?dú)怏w訓(xùn)練樣本和未知?dú)怏w樣本的第d個(gè)屬性值。

（4）計(jì)算訓(xùn)練氣體樣本與每個(gè)測(cè)試氣體樣本的歐氏距離dist，并計(jì)算得到K最近鄰的最大距離maxdist。比較dist與maxdist大小，如果小于最大距離，則被判為K最近鄰的類別。

（5）重復(fù)迭代，計(jì)算所有待測(cè)試氣體樣本。

（6）根據(jù)K個(gè)近鄰的類別以及少數(shù)服從多數(shù)的原則，從未知?dú)怏w樣本txn中選擇數(shù)量最多所在的類別作為測(cè)試氣體所屬類別。

KNN算法作為一種有監(jiān)督的經(jīng)典分類算法，理論成熟，較容易理解，在船舶尾氣分類上有很好的效果和應(yīng)用，且時(shí)間復(fù)雜度為O(n)。但KNN算法也有其缺點(diǎn)：當(dāng)樣本數(shù)量過大或者是分類高維度數(shù)據(jù)時(shí)，需要進(jìn)行繁重的的距離計(jì)算量，相應(yīng)的硬件內(nèi)存需求變高，計(jì)算時(shí)間也變長，效率會(huì)變得很低下。

1.2 PCA 算法

主成分分析法（PCA）是一種最常用的數(shù)據(jù)降維算法[9]。主要對(duì)高維數(shù)據(jù)進(jìn)行的加工處理、壓縮，減少了原本復(fù)雜的數(shù)據(jù)的特征度，減少了原本數(shù)據(jù)中的噪音數(shù)據(jù)，提高了數(shù)據(jù)的信噪比，同時(shí)還減少過度擬合的可能性。其基本思想：將原本的數(shù)組進(jìn)行重新組合，通過正交變換，將N維特征映射到M維上（N＜M），產(chǎn)生全新的N維特征。這N維特征就是主成分。主成分之間是互補(bǔ)相關(guān)的，且是原始變量的線性組合[10]。

圖1 待測(cè)樣本O的最近鄰

主成分分析法的計(jì)算步驟如下：

（1）獲取樣本特征矩陣X:

將式（2）轉(zhuǎn)換為線性組合：

其中y1,y2,…,ym(m＜p)是按從大到小線性變換后的互不相關(guān)的數(shù)值，且因此y1,y2,…,ym表示X中的主成分，lmp為主成分系數(shù)。

為了保持量綱一致性，可以采用式（3）原始化采集樣本。

其中i表示第i個(gè)數(shù)據(jù)，E(Xi)表示樣本的均值，D(Xi)表示樣本的方差。

（2）計(jì)算Xi的協(xié)方差矩陣S。

其相關(guān)系數(shù)矩陣R可表示為：

（3）計(jì)算R的特征值λ和特征向量e。

由特征方程（7）計(jì)算得到特征值λi(1,2,…p)。將特征值從大道小的順利排列，將特征值代入（8）中，求解得到特征向量 ai(1,2,…p)，將其單位化為 ei(1,2,…p)。

（4）選擇主成分。

通過計(jì)算累計(jì)貢獻(xiàn)率G(m)確定：

一般認(rèn)為當(dāng)G(m)大于85%時(shí)，就可以認(rèn)為這M個(gè)主成分代替了原始樣本的信息內(nèi)容和結(jié)構(gòu)[11]。

（5）得出主成分荷載

代入式（3）中，得到主成分Y=(y1,y2,…,ym)T。

1.3 基于PCA的KNN 算法改進(jìn)

通過采用PCA算法對(duì)訓(xùn)練樣本的數(shù)據(jù)降維，提高了樣本數(shù)據(jù)的可計(jì)算性，減少了計(jì)算時(shí)間。但是樣本數(shù)目巨大，傳統(tǒng)的KNN算法需要大量的存儲(chǔ)空間對(duì)訓(xùn)練樣本進(jìn)行存儲(chǔ)，而且測(cè)試樣本需要與每一個(gè)訓(xùn)練樣本進(jìn)行計(jì)算距離，通過排序找到前K個(gè)最近鄰。本文針對(duì)傳統(tǒng)KNN算法的不足，對(duì)進(jìn)行過PCA降維的數(shù)據(jù)用C均值聚類算法（C-means），C均值聚類算法也被稱為K-均值聚類方法[12]。C均值聚類算法的核心思想是,通過迭代尋找C個(gè)聚類的一種分類方案，用這C個(gè)聚類的均值來代表相應(yīng)的各類樣本，使樣本的總體誤差達(dá)到最小[13]。在大數(shù)據(jù)樣本的情況下，就不用對(duì)所有氣體樣本都進(jìn)行繁重的距離計(jì)算，縮短了計(jì)算量和減少了計(jì)算時(shí)間。

C均值聚類算法的基礎(chǔ)是最小誤差平方和準(zhǔn)則[14]。如果Qi是第i個(gè)聚類Γi中的樣本數(shù)量，得下式，

把Γi中的每個(gè)樣本y和均值mi間的誤差平方和與全部氣體訓(xùn)練樣本的類累加后，得到：

其中Je是誤差平方和，Y是氣體訓(xùn)練樣本集，mi是樣本的均值。

這里有一個(gè)把樣本y劃分到Γk中的聚類例子，以下是C均值聚類算法的步驟。

（1）開始可以把訓(xùn)練樣本集Y劃分為c個(gè)聚類，Γi，i=1,2,…c，代入式（11）和式（12）中。計(jì)算得到mi，i=1,2,…c和 Je；

（2）從訓(xùn)練樣本集Y中任意取一樣本 y，假設(shè) y∈Γi；

（3）如果Qi=1則重新進(jìn)行步驟（2），否則就進(jìn)行下一步；

（4）計(jì)算 ρj

（5）計(jì)算得到樣本中 ρmin，如果 ρmin＜ρi，則將樣本y從Γi合并到Γk中；

（6）重復(fù)計(jì)算 mi，i=1,2,…c和 Je直到 Je不在改變，就對(duì)訓(xùn)練樣本完成了分類。

這里C均值聚類算法中的聚類數(shù)目C由（Je-C曲線）得到。圖1給出了一個(gè)Je-C曲線的例子。曲線的拐點(diǎn)處對(duì)應(yīng)的聚類數(shù)目C一般就是最優(yōu)值[15]。

2 實(shí)驗(yàn)仿真

2.1 實(shí)驗(yàn)流程

對(duì)獲得的訓(xùn)練樣本數(shù)據(jù)預(yù)處理，然后進(jìn)行PCA處理，然后將訓(xùn)練樣本做C均值的聚類算法，減少訓(xùn)練樣本所占用的空間。同樣對(duì)測(cè)試樣本進(jìn)行數(shù)據(jù)預(yù)處理，進(jìn)行PCA降維處理，在本文設(shè)計(jì)的分類器中將訓(xùn)練樣本劃分到氣體所屬類別。氣體識(shí)別算法流程如圖2所示。

圖2 確定聚類數(shù)目的Je-C曲線

圖3 氣體識(shí)別流程

2.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)平臺(tái):Intel Core i7 4470四核八線程;主頻3.4GHz處理器;16GB內(nèi)存;在軟件MATLAB R2014a下進(jìn)行仿真實(shí)驗(yàn)。

2.3 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)中將氣體傳感陣列輸出的穩(wěn)態(tài)值作為氣體的特征值，每進(jìn)行一次氣體采樣都可以得到一個(gè)1×30的向量，對(duì)SO2和NOx兩類氣體進(jìn)行重復(fù)采樣，避免出現(xiàn)單次測(cè)量不準(zhǔn)的情況。經(jīng)過200次采樣可以組成200×30的訓(xùn)練樣本矩陣。同樣進(jìn)行1500次采樣組成1500×30的測(cè)試樣本矩陣。分別如式（15）和式（16）所示。

其中n等于200，m等于1500，維度 p等于30。

2.4 實(shí)驗(yàn)結(jié)果分析

在實(shí)驗(yàn)過程中，本文采用傳統(tǒng)的KNN算法，經(jīng)過PCA處理的KNN算法（簡(jiǎn)稱PCA-KNN算法）以及經(jīng)過PCA處理C均值聚類的KNN算法（PCA-CKNN算法）這三種不同的算法在不同維度下的分類時(shí)間，分類準(zhǔn)確性進(jìn)行比較。結(jié)果如表1和圖所示。

表1 KNN，PCA-KNN與PCA-CKNN算法的分類時(shí)間

從三種不同的算法中發(fā)現(xiàn)本文提出的PCA-CKNN算法在分類時(shí)間上占明顯的優(yōu)勢(shì)。

評(píng)價(jià)分類的性能指標(biāo)還有準(zhǔn)確率[16]:

結(jié)果如圖4所示。

根據(jù)圖4可以得到傳統(tǒng)KNN算法的識(shí)別率最好，其他兩種算法分類結(jié)果稍差些。

通過表1和圖4綜合分析可以得出，雖然在準(zhǔn)確率上文本提出的PCA-CKNN算法不如傳統(tǒng)的KNN算法，但是只相差1%值2%左右，但是分類速度提高了大約10倍左右。雖然PCA-KNN算法分類效果稍微好于PCA-CKNN，但是分類速度慢了一半不止。通過上述的實(shí)驗(yàn)可以得到一個(gè)結(jié)論：基于主成分分析和C均值聚類的改進(jìn)K-近鄰算法能夠在保證識(shí)別船舶尾氣準(zhǔn)確的基礎(chǔ)上，縮短了算法分類氣體的時(shí)間。

圖4 三種算法準(zhǔn)確率對(duì)比

3 結(jié)語

在海事執(zhí)法部門采用搭載氣體傳感器的無人機(jī)檢測(cè)船舶尾氣對(duì)SO2和NOx進(jìn)行識(shí)別，利用K近鄰的分類思想，針對(duì)算法中計(jì)算量大、樣本數(shù)較多，樣本數(shù)據(jù)維度高等會(huì)使分類產(chǎn)生誤判的情況，提出基于PCA降維和C均值聚類的KNN算法。最后對(duì)算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，并與傳統(tǒng)的KNN算法和只進(jìn)行PCA降維的KNN算法進(jìn)行了比較分析，本文所提出的算法在保證氣體分類的準(zhǔn)確性上，還縮短了分類的時(shí)間。研究表明，本文的算法在船舶尾氣識(shí)別中比傳統(tǒng)的KNN算法更加適用。但本文提出的算法也仍有一些可以改進(jìn)的地方，如果聚類的效果提高，那么分類的準(zhǔn)確率可以再提高，甚至超過傳統(tǒng)的KNN算法。

[1]馮璐.王厚啟船舶治污瓶頸待破除[N].中國水運(yùn)報(bào)，2015.

[2]鹿文靜.基于OTG協(xié)議的氣體數(shù)據(jù)采集與識(shí)別算法的研究[D].上海應(yīng)用技術(shù)大學(xué),2016.

[3]尹洪濤,付平,沙學(xué)軍.基于DCT和線性判別分析的人臉識(shí)別[J].電子學(xué)報(bào),2009,37（10）:2211-2214.

[4]Subhash Ajmani?,Kamalakar Jadhav A,Kulkarni S A.Three-Dimensional QSAR Using the k-Nearest Neighbor Method and Its Interpretation[J].Journal of Chemical Information&Modeling,2006,46（1）:24.

[5]Subirats J L,Franco L,Jerez J M.C-Mantec:a Novel Constructive Neural Network Algorithm Incorporating Competition Between Neurons[J].Neural Networks,2012,26（2）:130-140.

[6]關(guān)慶,鄧趙紅,王士同.改進(jìn)的模糊C-均值聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47（10）:27-29.

[7]王增民,王開玨.基于熵權(quán)的K最臨近算法改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2009,45（30）:129-131.

[8]陳佩.主成分分析法研究及其在特征提取中的應(yīng)用[D].陜西師范大學(xué),2014.

[9]史淼,劉鋒.基于PCA和kNN混合算法的文本分類方法[J].電腦知識(shí)與技術(shù),2015（4）:169-171.

[10]李容.協(xié)同過濾推薦系統(tǒng)中稀疏性數(shù)據(jù)的算法研究[D].電子科技大學(xué),2016.

[11]荀燁,龍綿偉,陳民.基于主成分分析法的軍事物流基地中心倉庫遴選[J].軍事交通學(xué)院學(xué)報(bào),2015,17（1）:61-65.

[12]賈璦瑋.基于劃分的聚類算法研究綜述[J].電子設(shè)計(jì)工程,2014（23）:38-41.

[13]柯尊海,劉勇,徐義春,等.基于改進(jìn)K均值的運(yùn)動(dòng)目標(biāo)檢測(cè)算法研究[J].三峽大學(xué)學(xué)報(bào)（自然科學(xué)版）,2012,34（6）:98-102.

[14]王超,姜威.基于K近鄰加權(quán)的混合C均值聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,2006,42（30）:84-87.

[15]許崝,施澤生,蔡洪濱,等.一種基于多模板匹配的在線手寫簽名認(rèn)證方法[J].計(jì)算機(jī)應(yīng)用,2004,24（s1）:165-167.

[16]劉龍海.基于成對(duì)約束的半監(jiān)督文本聚類算法研究[D].重慶大學(xué),2011.