哈夫曼樹SVM在空氣質量等級分類中的應用

王琛　王云　陳麗芳　劉亞飛

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

關鍵詞：哈夫曼樹；支持向量機（SVM）；多分類；空氣質量指數（AQI）

中圖法分類號：TP311；O1 文獻標識碼：A 文章編號：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 引言

隨著社會的不斷進步、經濟的飛速發展，工業化生產排放到大氣中的眾多污染物使空氣質量明顯下降，致使人們的身體健康受到一定威脅。環境空氣質量等級的制定能夠為人們的出行提供參考，因此對空氣質量的統一、精準分類將會對人們合理規劃生產生活，以及城市決策管理層出臺治理空氣污染的有關政策法規發揮具有基礎和依據性的現實重要作用。

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

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

基于此，結合目前國內外研究現狀，本文以唐山市空氣質量為研究背景，將PM2.5、PM10、SO2、NO2、O3和CO作為評價空氣質量的指標，通過公式得到AQI；將哈夫曼樹與支持向量機相結合，構造分類模型，并對模型進行仿真驗證。首先，數據采集與整理，將唐山站點測得的2014年數據，按空氣質量類別計算其概率分布并升序排序；然后，依據排序結果構造哈夫曼樹；根據所得哈夫曼樹，建立支持向量機多分類器模型；最后利用MATLAB實現模型的設計與仿真。

1. 原理及技術

1.1 哈夫曼樹

哈夫曼樹（Huffman Tree，HT）又稱最優二叉樹，其特點是帶權路徑長度最短。因此，利用哈夫曼樹的優點，構建最優二叉樹，從根本上解決訓練樣本集分布不均等問題，提高分類效率。

構造哈夫曼樹的算法步驟如下[6]：

（1）初始化。給定n個權值{w1，w2，…，wn}構造n棵只有一個根結點的二叉樹，從而得到一個二叉樹集合F={T1，T2，…，Tn}；

（2）選取與合并。在F中選取根結點的權值最小的兩棵二叉樹分別作為左、右子樹構造一棵新的二叉樹，這棵新的二叉樹的根結點的權值則為選取的左、右子樹根結點的權值之和；

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

（4）重復（2）、（3）兩步，當集合F中只剩下一棵二叉樹時，這棵二叉樹便是哈夫曼樹。

哈夫曼樹使權值越大的葉子結點越靠近根結點，能夠在出現新樣本時做到艮為快速、準確地歸類。在實際應用中，根據領域知識確定其權重值，進而構造哈夫曼樹，如此將會有利于多分類問題的優勢高效處理解決。

2.2 支持向量機

支持向量機（SVM）[7]的基本思想為：為得到一個高維空間，使用非線性去轉化輸入的空間；進而求解最優的線性分類面，在這一個新空間中，定義合適的內積函數完成這個非線性的轉換。

已知訓練樣本集： ，則SVM就是尋找一個最優分類平面，分類平面表示為： （1）

且滿足下面條件：

（2）

式中， 為權向量； 為閾值。

在線性可分的最優分類超平面情況下論述提出的支持向量機的算法原理，是通過對樣本進行學習并建立模型，然后對測試樣本進行預測。如圖1所示，SVM就是找到一個最優超平面，使兩類間隔最大并正確分開。“Margin”為最大間隔帶，與H1，H2相交的樣本為支持向量（support vectors）。

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

2.3 空氣質量指數

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

AQI共分六級，一級優，二級良，三級輕度污染，四級中度污染，五級重度污染，六級嚴重污染。空氣污染指數劃分為0～50、51～100、101～150、151～200、201～300和大于300六檔。

其中，IAQIP表示污染物項目P的空氣質量分指數；CP表示污染物項目P的質量濃度值；BPHi表示相應地區的空氣質量分指數及對應的污染物項目濃度指數表中與CP相近的污染物濃度限值的高位值；BPLo表示相應地區的空氣質量分指數及對應的污染物項目濃度指數表中與CP相近的污染物濃度限值的低位值；IAQIHi表示相應地區的空氣質量分指數及對應的污染物項目濃度指數表中與BPHi對應的空氣質量分指數；IAQILo表示相應地區的空氣質量分指數及對應的污染物項目濃度指數表中與BPLo對應的空氣質量分指數。

空氣質量指數：

AQI={IAQI1， IAQI2，…， IAQIn}

其中，IAQI為空氣質量分指數；n為污染物項目。簡單來說，AQI就是在各IAQI中取其最大值。AQI大于50時，IAQI最大的污染物為首要污染物。若IAQI最大的污染物為兩項或兩項以上時，并列為首要污染物。IAQI大于100的污染物即為超標污染物。

2. 模型構建

2.1數據采集與預處理

收集整理2014年唐山市部分站點空氣質量采集數據，對數據進行分析整理。

通過對數據整理篩選，選擇唐山市2014年10月份雷達站子站檢測到的空氣質量樣本。將如下六項污染物：細顆粒物（PM2.5）、可吸入顆粒物（PM10）、二氧化硫（SO2）、二氧化氮（NO2）、臭氧（O3）、一氧化碳（CO）作為評價指標。

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

（6）

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

3 結束語

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

參考文獻

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

[2] 李俊飛.基于支持向量機的空氣質量預測[J].黑龍江科技信息，2015（26）：105-106.

[3] 陳祖云，金波，鄔長福.支持向量機在環境空氣質量評價中的應用[J].環境科學與技術，2012（S1）：395-398.

[4] 薛興釗.基于BP神經網絡的秦嶺北麓中部空氣質量預報研究[D]. 西安：西安建筑科技大學，2014.

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

[6] 陳源. 算法與數據結構[M].北京：清華大學出版社，2005.

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

[8] 中華人民共和國環境保護部.環境空氣質量指數（AQI）技術規定（試行）HJ633—2012[S].北京：中國環境科學出版社，2012.