哈夫曼樹SVM在空氣質(zhì)量等級(jí)分類中的應(yīng)用

王琛　王云　陳麗芳　劉亞飛

摘 要： 針對(duì)空氣質(zhì)量等級(jí)問題，應(yīng)用哈夫曼樹和SVM構(gòu)建了空氣質(zhì)量等級(jí)多分類模型。首先，數(shù)據(jù)采集與整理，采集2014年十月份數(shù)據(jù)，按空氣質(zhì)量類別計(jì)算其概率分布并升序排序；然后，依據(jù)排序結(jié)果構(gòu)造哈夫曼樹；根據(jù)所得哈夫曼樹，建立支持向量機(jī)多分類器模型；最后利用MATLAB實(shí)現(xiàn)模型的設(shè)計(jì)與仿真。結(jié)果分析表明，該方法加快了支持向量機(jī)的分類速度和精度，減少了分類錯(cuò)誤率，為多分類問題的處理提供了一個(gè)新的研究思路。

關(guān)鍵詞：哈夫曼樹；支持向量機(jī)（SVM）；多分類；空氣質(zhì)量指數(shù)（AQI）

中圖法分類號(hào)：TP311；O1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-2163（2016）01-

Abstract： For the problem of air quality level， the classification model of air quality level based on Huffman tree and SVM are constructed. Through collection the data of air influence factors in October 2014， the probability is calculated and ordered ascending by the air quality category. Then according to the results of sorting， the Huffman tree is also constructed. And on the basis of Huffman tree， the support vector machine classifier model is established. Finally， the model is design and simulation by MATLAB. The result shows that the new model improve the efficiency of classification， meanwhile， reduces the classification error rate. It provides a new idea and a perfect method for multi classification problem.

Keywords： Huffman Tree； Support Vector Machine； Multi Classification； Air Quality Index

0 引言

隨著社會(huì)的不斷進(jìn)步、經(jīng)濟(jì)的飛速發(fā)展，工業(yè)化生產(chǎn)排放到大氣中的眾多污染物使空氣質(zhì)量明顯下降，致使人們的身體健康受到一定威脅。環(huán)境空氣質(zhì)量等級(jí)的制定能夠?yàn)槿藗兊某鲂刑峁﹨⒖?，因此?duì)空氣質(zhì)量的統(tǒng)一、精準(zhǔn)分類將會(huì)對(duì)人們合理規(guī)劃生產(chǎn)生活，以及城市決策管理層出臺(tái)治理空氣污染的有關(guān)政策法規(guī)發(fā)揮具有基礎(chǔ)和依據(jù)性的現(xiàn)實(shí)重要作用。

張麗[1]等選取影響空氣質(zhì)量最重要的三個(gè)指標(biāo)PM10、SO2、NO2的濃度值，說明了支持向量機(jī)分類預(yù)測(cè)模型在城市空氣質(zhì)量級(jí)別預(yù)測(cè)中是有效的。李俊飛[2]用支持向量機(jī)分別進(jìn)行訓(xùn)練和預(yù)測(cè)，最后合成得到預(yù)測(cè)結(jié)果，實(shí)驗(yàn)結(jié)果表明該方法的預(yù)測(cè)效果較好。陳祖云等[3]環(huán)境空氣質(zhì)量評(píng)價(jià)的特征向量選擇為SO2、NO2、TSP（總懸浮顆粒物）和降塵。我國(guó)現(xiàn)在以環(huán)境空氣質(zhì)量指數(shù)AQI（Air Quality Index）為空氣質(zhì)量評(píng)價(jià)方法，該方法將PM10、PM2.5、CO、SO2、NO2、O3等幾種主要的空氣污染項(xiàng)目的濃度簡(jiǎn)化成指數(shù)數(shù)值形式，通過劃分不同的級(jí)別來表示環(huán)境空氣質(zhì)量情況。[4] 滕少華等[5]提出了基于哈夫曼樹的支持向量機(jī)多分類方法，然后根據(jù)相異度來決策分類的優(yōu)先順序，構(gòu)建基于哈夫曼樹的支持向量機(jī)多分類模型，實(shí)驗(yàn)結(jié)果表明：新的方法在分類速度和分類精度上較傳統(tǒng)的支持向量機(jī)多分類方法都要更顯優(yōu)越。

通過對(duì)文獻(xiàn)的分析可以看出，大多研究者選取了PM10、SO2、NO2作為主要影響指標(biāo)來解析建模，卻并未將PM2.5這一對(duì)人體健康影響較大的因素考慮在內(nèi)，而其研究則是更多地著重于理論方面的演進(jìn)和探討，對(duì)將其進(jìn)行設(shè)計(jì)與仿真方面卻仍未見到顯著進(jìn)展和標(biāo)志性技術(shù)實(shí)現(xiàn)。

基于此，結(jié)合目前國(guó)內(nèi)外研究現(xiàn)狀，本文以唐山市空氣質(zhì)量為研究背景，將PM2.5、PM10、SO2、NO2、O3和CO作為評(píng)價(jià)空氣質(zhì)量的指標(biāo)，通過公式得到AQI；將哈夫曼樹與支持向量機(jī)相結(jié)合，構(gòu)造分類模型，并對(duì)模型進(jìn)行仿真驗(yàn)證。首先，數(shù)據(jù)采集與整理，將唐山站點(diǎn)測(cè)得的2014年數(shù)據(jù)，按空氣質(zhì)量類別計(jì)算其概率分布并升序排序；然后，依據(jù)排序結(jié)果構(gòu)造哈夫曼樹；根據(jù)所得哈夫曼樹，建立支持向量機(jī)多分類器模型；最后利用MATLAB實(shí)現(xiàn)模型的設(shè)計(jì)與仿真。

1. 原理及技術(shù)

1.1 哈夫曼樹

哈夫曼樹（Huffman Tree，HT）又稱最優(yōu)二叉樹，其特點(diǎn)是帶權(quán)路徑長(zhǎng)度最短。因此，利用哈夫曼樹的優(yōu)點(diǎn)，構(gòu)建最優(yōu)二叉樹，從根本上解決訓(xùn)練樣本集分布不均等問題，提高分類效率。

構(gòu)造哈夫曼樹的算法步驟如下[6]：

（1）初始化。給定n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹集合F={T1，T2，…，Tn}；

（2）選取與合并。在F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹的根結(jié)點(diǎn)的權(quán)值則為選取的左、右子樹根結(jié)點(diǎn)的權(quán)值之和；

（3）刪除與并入。在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新的二叉樹加入到集合F中；

（4）重復(fù)（2）、（3）兩步，當(dāng)集合F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是哈夫曼樹。

哈夫曼樹使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，能夠在出現(xiàn)新樣本時(shí)做到艮為快速、準(zhǔn)確地歸類。在實(shí)際應(yīng)用中，根據(jù)領(lǐng)域知識(shí)確定其權(quán)重值，進(jìn)而構(gòu)造哈夫曼樹，如此將會(huì)有利于多分類問題的優(yōu)勢(shì)高效處理解決。

2.2 支持向量機(jī)

支持向量機(jī)（SVM）[7]的基本思想為：為得到一個(gè)高維空間，使用非線性去轉(zhuǎn)化輸入的空間；進(jìn)而求解最優(yōu)的線性分類面，在這一個(gè)新空間中，定義合適的內(nèi)積函數(shù)完成這個(gè)非線性的轉(zhuǎn)換。

已知訓(xùn)練樣本集： ，則SVM就是尋找一個(gè)最優(yōu)分類平面，分類平面表示為： （1）

且滿足下面條件：

（2）

式中， 為權(quán)向量； 為閾值。

在線性可分的最優(yōu)分類超平面情況下論述提出的支持向量機(jī)的算法原理，是通過對(duì)樣本進(jìn)行學(xué)習(xí)并建立模型，然后對(duì)測(cè)試樣本進(jìn)行預(yù)測(cè)。如圖1所示，SVM就是找到一個(gè)最優(yōu)超平面，使兩類間隔最大并正確分開?！癕argin”為最大間隔帶，與H1，H2相交的樣本為支持向量（support vectors）。

支持向量機(jī)是用來處理模式識(shí)別和回歸等多類問題的一種數(shù)據(jù)分析方法，在實(shí)際問題中，常常用來預(yù)測(cè)結(jié)果或者對(duì)樣本數(shù)據(jù)進(jìn)行綜合評(píng)價(jià)。找到一個(gè)最優(yōu)超平面是SVM的理論追求目的，就是在某一分類情景下不僅確保精度最高，同時(shí)也要使分類結(jié)果各類之間的間隔最大。

2.3 空氣質(zhì)量指數(shù)

空氣質(zhì)量指數(shù)[8]（Air Quality Index，簡(jiǎn)稱AQI），是用來定量描述空氣質(zhì)量水平的一個(gè)標(biāo)志數(shù)據(jù)。AQI的取值范圍位于0～500之間。環(huán)境空氣污染物的種類有很多，常見的有二氧化硫（SO2）、二氧化氮（NO2）、一氧化碳（CO）、臭氧（O3）和懸浮顆粒物。懸浮顆粒物中，直徑小于等于10μm的稱為PM10，直徑小于等于2.5μm的稱為PM2.5。

AQI共分六級(jí)，一級(jí)優(yōu)，二級(jí)良，三級(jí)輕度污染，四級(jí)中度污染，五級(jí)重度污染，六級(jí)嚴(yán)重污染。空氣污染指數(shù)劃分為0～50、51～100、101～150、151～200、201～300和大于300六檔。

其中，IAQIP表示污染物項(xiàng)目P的空氣質(zhì)量分指數(shù)；CP表示污染物項(xiàng)目P的質(zhì)量濃度值；BPHi表示相應(yīng)地區(qū)的空氣質(zhì)量分指數(shù)及對(duì)應(yīng)的污染物項(xiàng)目濃度指數(shù)表中與CP相近的污染物濃度限值的高位值；BPLo表示相應(yīng)地區(qū)的空氣質(zhì)量分指數(shù)及對(duì)應(yīng)的污染物項(xiàng)目濃度指數(shù)表中與CP相近的污染物濃度限值的低位值；IAQIHi表示相應(yīng)地區(qū)的空氣質(zhì)量分指數(shù)及對(duì)應(yīng)的污染物項(xiàng)目濃度指數(shù)表中與BPHi對(duì)應(yīng)的空氣質(zhì)量分指數(shù)；IAQILo表示相應(yīng)地區(qū)的空氣質(zhì)量分指數(shù)及對(duì)應(yīng)的污染物項(xiàng)目濃度指數(shù)表中與BPLo對(duì)應(yīng)的空氣質(zhì)量分指數(shù)。

空氣質(zhì)量指數(shù)：

AQI={IAQI1， IAQI2，…， IAQIn}

其中，IAQI為空氣質(zhì)量分指數(shù)；n為污染物項(xiàng)目。簡(jiǎn)單來說，AQI就是在各IAQI中取其最大值。AQI大于50時(shí)，IAQI最大的污染物為首要污染物。若IAQI最大的污染物為兩項(xiàng)或兩項(xiàng)以上時(shí)，并列為首要污染物。IAQI大于100的污染物即為超標(biāo)污染物。

2. 模型構(gòu)建

2.1數(shù)據(jù)采集與預(yù)處理

收集整理2014年唐山市部分站點(diǎn)空氣質(zhì)量采集數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行分析整理。

通過對(duì)數(shù)據(jù)整理篩選，選擇唐山市2014年10月份雷達(dá)站子站檢測(cè)到的空氣質(zhì)量樣本。將如下六項(xiàng)污染物：細(xì)顆粒物（PM2.5）、可吸入顆粒物（PM10）、二氧化硫（SO2）、二氧化氮（NO2）、臭氧（O3）、一氧化碳（CO）作為評(píng)價(jià)指標(biāo)。

對(duì)照各項(xiàng)污染物的分級(jí)濃度限值，以細(xì)顆粒物（PM2.5）、可吸入顆粒物（PM10）、二氧化硫（SO2）、二氧化氮（NO2）、臭氧（O3）、一氧化碳（CO）等各項(xiàng)污染物的實(shí)測(cè)濃度值（其中PM2.5、PM10為24小時(shí)平均濃度）分別計(jì)算得出空氣質(zhì)量分指數(shù)。對(duì)應(yīng)公式為：

（6）

然后再根據(jù)空氣質(zhì)量分指數(shù)（IAQI）得到2014年唐山市10月空氣質(zhì)量指數(shù)（AQI）和主要污染物。

3 結(jié)束語(yǔ)

本文提出利用哈夫曼樹SVM實(shí)現(xiàn)多類別問題的分類模型，可在解決問題時(shí)保證效率和準(zhǔn)確性，避免了局部最優(yōu)解的產(chǎn)生并削弱了錯(cuò)誤累積的影響，同時(shí)也提升了對(duì)空氣質(zhì)量等級(jí)的分類速度。由于在構(gòu)建支持向量機(jī)之前，根據(jù)數(shù)據(jù)樣本中的類別計(jì)算了概率，并構(gòu)建了最優(yōu)二叉樹（哈夫曼樹），從而使得概率最高的類別最先獲得了分離，最終保障了執(zhí)行速度和分類精度。從結(jié)果中可以得出如下結(jié)論，將哈夫曼樹作為決策樹的SVM多分類技術(shù)既獲得了高效，又可達(dá)到較為出眾的準(zhǔn)確性的實(shí)施目標(biāo)。因此，如何進(jìn)一步優(yōu)化基于哈夫曼樹的SVM分類技術(shù)以及將這一方法廣泛應(yīng)用到社會(huì)的各個(gè)領(lǐng)域中需要在后續(xù)的研究工作中進(jìn)行深入的后續(xù)探討。

參考文獻(xiàn)

[1] 張麗，李靜，葛汝冰.全國(guó)主要城市空氣質(zhì)量級(jí)別的分類預(yù)測(cè)——基于支持向量機(jī)的視角[J].管理工程師，2013（1）：55-57，75.

[2] 李俊飛.基于支持向量機(jī)的空氣質(zhì)量預(yù)測(cè)[J].黑龍江科技信息，2015（26）：105-106.

[3] 陳祖云，金波，鄔長(zhǎng)福.支持向量機(jī)在環(huán)境空氣質(zhì)量評(píng)價(jià)中的應(yīng)用[J].環(huán)境科學(xué)與技術(shù)，2012（S1）：395-398.

[4] 薛興釗.基于BP神經(jīng)網(wǎng)絡(luò)的秦嶺北麓中部空氣質(zhì)量預(yù)報(bào)研究[D]. 西安：西安建筑科技大學(xué)，2014.

[5] 滕少華，胡俊，張巍，劉冬寧.支持向量機(jī)與哈夫曼樹實(shí)現(xiàn)多分類的研究[J].江西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2014（4）：383-389.

[6] 陳源. 算法與數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2005.

[7] 丁世飛，齊丙娟，譚紅艷. 支持向量機(jī)理論與算法研究綜述[J]. 電子科技大學(xué)學(xué)報(bào)，2011，40（1）：2-10.

[8] 中華人民共和國(guó)環(huán)境保護(hù)部.環(huán)境空氣質(zhì)量指數(shù)（AQI）技術(shù)規(guī)定（試行）HJ633—2012[S].北京：中國(guó)環(huán)境科學(xué)出版社，2012.