哈夫曼树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.