哈夫曼树实验报告（通用2篇）
篇1：哈夫曼树实验报告
常熟理工学院微课教学比赛教学设计
1、课程基本信息
课程名称：哈夫曼树及应用
所属课程：数据结构与算法 课程所属专业：软件工程
适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林
时长：15分钟 所属学校：常熟理工学院
所属院系：计算机科学与工程学院
2.教学背景
《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。2.1《数据结构与算法》课程简介及特点
《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。
《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。2.2本节微课课程特点
“树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。
本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。
3.教学设计
3.1教学目的
通过本节微课的学习，培养学生以下几个方面的能力：（1）理解哈夫曼树的应用范围和场景，并能灵活运用；
（2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫曼编码；
（3）掌握哈夫曼树的存储结构，理解静态三叉链表结构；
（4）掌握哈夫曼树及编码的求解算法，并能在实验中实现并验证算法（难点）；
根据学生理论基础及程序编码能力，本微课教学目标分为三个水平：合格、中等、优秀，具体标准如下：
合格水平：熟练掌握哈夫曼树及编码的基本概念，能构造哈夫曼树，求解哈夫曼编码。中等水平：掌握概念和算法思想的基础上，能上机实现验证哈夫曼树及编码的求解过程。优秀水平：在上机实现算法的基础上，能理论联系实际，利用算法解决实际问题。3.2教学内容
树与二叉树中哈夫曼树的构造和哈夫曼编码的求解。（1）问题引入；
（2）哈夫曼树的定义；（3）哈夫曼树的构造；（4）哈夫曼编码的定义；（5）算法实现。3.3教学重点及难点
教学重点：哈夫曼树及编码求解的算法思想。教学难点：哈夫曼树的存储结构，算法的实现。3.4教学方法
本微课内容在算法思想上较为容易，但在具体实现上具有一定难度，因此采用启发式教学和案例驱动式教学相结合的方法，提出问题引入课题，通过实例求解哈夫曼树，循序渐进求解哈夫曼编码，通过多次提问的方式充分调动学生的学习积极性，使用动画的形式演示实例的求解过程，增强课堂的形象性及趣味性，增加课堂容量。
课程设置由问题引入、哈夫曼树的概念、哈夫曼树的构造、哈夫曼编码、算法的实现共同组成，由浅入深，由理论到实践，实现微课课堂的完整性和连贯性。
（1）问题引入
由报文传送问题引入，如何来构建传送效率高，即报文长度最短的二进制编码。哈夫曼编码也常用在数据压缩中，是一种非常有效的压缩方法。
问题：如何使报文长度最短？（2）哈夫曼树的定义
针对给出的二叉树实例T，回顾二叉树的基本概念，树的根节点、叶子结点，同时引入新的概念，结点的权值、路径长度、结点的带权路径长度，树的带权路径长度WPL。
分析实例，相同叶子结点权值，不同树的组成形态，WPL权值不一定，引出哈夫曼树的定义：带权路径长度最小的二叉树。
问题：如何构造哈夫曼树？（3）哈夫曼树的构造
通过二叉树的实例引出哈夫曼树的构造原则和哈夫曼树的构造思想。
通过流程图的方式逐步介绍哈夫曼树的构造方法，利用标注给出每步详细事项。通过动画的方式，逐步介绍以7、9、5、6、2为叶子结点的哈夫曼树构造过程。问题：哈夫曼树是否唯一？（4）哈夫曼编码
问题：哈夫曼树中是否存在度为1的结点？ 分析二进制编码和哈夫曼树的特点，讲解哈夫曼编码的求解过程。通过动画演示哈夫曼树进行“0”“1”编码的过程从而求解出哈夫曼编码。问题：n个叶子结点的哈夫曼树总共有多少结点？引导出哈夫曼树的存储结构。
（5）算法实现
分析：在哈夫曼树的构造过程中，需要用到孩子和双亲的信息，因此存储结构中需要保存双亲及左右孩子的信息，采用三叉链表来表示，同时在求解编码过程需要从根到叶子结点，因此采用静态链表作为存储结构。
具体实现分以下部分进行：
a：根据叶子结点给静态三叉链表赋初值；
b：在静态三叉链表中依次构造根权值为7、13、16、29的节点，删除所选两棵树的操作为修改该结点双亲的值；
c：产生哈夫曼编码，针对静态三叉链表的存储结构内容，从叶子结点a开始，依次找到双亲信息，并获得哈夫曼编码的逆序序列。
提炼出哈夫曼编码的产生方法，结合程序代码进行详细讲解。总结本次课程主要内容，提出课后思考题。
4、教学总结
本次微课由报文传送引出主题，由理论到实现，结合形象的动画演示循序渐进的描述了哈夫曼树和编码的定义与实现。通过问题导入和案例驱动式教学方法的使用，使学生难以理解的二叉树结构与算法形象化、趣味化。通过实例的讲解，使学生快速掌握了哈夫曼树及哈夫曼编码的算法思想，再由实例结合存储结构的方式，让学生理解哈夫曼树的相关程序设计，提升学生的学习兴趣，增强学生逻辑结构分析能力和程序设计能力。
篇2：哈夫曼树实验报告
关键词：哈夫曼树,支持向量机(SVM),多分类,空气质量指数(AQI)
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中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树。
哈夫曼树使权值越大的叶子结点越靠近根结点,能够在出现新样本时做到更为快速、准确地归类。在实际应用中,根据领域知识确定其权重值,进而构造哈夫曼树,如此将会有利于多分类问题的优势高效处理解决。
1.2 支持向量机
支持向量机( SVM)[7]的基本思想: 为得到一个高维空间,使用非线性去转化输入的空间; 进而求解最优的线性分类面,在这一个新空间中,定义合适的内积函数完成这个非线性的转换。
已知训练样本集( xi,yi) ,yi= ± 1,i = 1,2,…,n,则SVM就是寻找一个最优分类平面,分类平面表示为:
且满足下面条件:
式中,ω 为权向量,b为阈值。
在线性可分的最优分类超平面情况下论述提出的支持向量机的算法原理,是通过对样本进行学习并建立模型,然后对测试样本进行预测。如图1 所示,SVM就是找到一个最优超平面,使两类间隔最大并正确分开。“Margin”为最大间隔带,与H1,H2 相交的样本为支持向量( support vectors) 。
H1 与H2 之间的间隔为类间隔,大小为:
因为要寻找最优超平面,则表示为:
支持向量机是用来处理模式识别和回归等多类问题的一种数据分析方法,在实际问题中,常常用来预测结果或者对样本数据进行综合评价。找到一个最优超平面是SVM的理论追求目的,就是在某一分类情景下不仅确保精度最高,同时也要使分类结果中各类之间的间隔最大。
1.3 空气质量指数
空气质量指数[8]( Air Quality Index,简称AQI) ,是用来定量描述空气质量水平的一个标志数据。AQI的取值范围位于0 ~ 500 之间。环境空气污染物的种类有很多,常见的有二氧化硫( SO2) 、二氧化氮( NO2) 、一氧化碳( CO) 、臭氧( O3) 和悬浮颗粒物。悬浮颗粒物中,直径小于等于10 μm的称为PM10,直径小于等于2.5 μm的称为PM2.5。
AQI共分6 级,一级优、二级良、三级轻度污染、四级中度污染、五级重度污染、六级严重污染。空气污染指数划分为0~ 50、51 ~ 100、101 ~ 150、151 ~ 200、201 ~ 300 和大于300 六档。
空气质量分指数的计算公式为:
其中,IAQIP表示污染物项目P的空气质量分指数; CP表示污染物项目P的质量浓度值; BPHi表示相应地区的空气质量分指数及对应的污染物项目浓度指数表中与CP相近的污染物浓度限值的高位值; BPLo表示相应地区的空气质量分指数及对应的污染物项目浓度指数表中与CP相近的污染物浓度限值的低位值; IAQIHi表示相应地区的空气质量分指数及对应的污染物项目浓度指数表中与BPHi对应的空气质量分指数; IAQILo表示相应地区的空气质量分指数及对应的污染物项目浓度指数表中与BPLo对应的空气质量分指数。
空气质量指数:
其中,IAQI为空气质量分指数; n为污染物项目。简单来说,AQI就是在各IAQI中取其最大值。AQI > 50 时,IAQI最大的污染物为首要污染物。若IAQI最大的污染物为两项或两项以上时,则并列为首要污染物。IAQI > 100 的污染物即为超标污染物。
2 模型构建
2.1 数据采集与预处理
收集整理2014 年唐山市部分站点空气质量采集数据,对数据进行分析整理。
通过对数据整理筛选,选择唐山市2014 年10 月份雷达站子站检测到的空气质量样本。将如下6 项污染物: 细颗粒物( PM2.5) 、可吸入颗粒物( PM10) 、二氧化硫( SO2) 、二氧化氮( NO2) 、臭氧( O3) 、一氧化碳( CO) 作为评价指标。
对照各项污染物的分级浓度限值,以细颗粒物( PM2.5) 、可吸入颗粒物( PM10) 、二氧化硫( SO2) 、二氧化氮( NO2) 、臭氧( O3) 、一氧化碳( CO) 等各项污染物的实测浓度值( 其中PM2.5、PM10 为24 小时平均浓度) 分别计算得出空气质量分指数对应公式为:
然后再根据空气质量分指数( IAQI) 得到唐山市2014 年10 月空气质量指数( AQI) 和主要污染物。如表1 所示。
接下来,由表1 计算得出6 类空气质量( 优、良、轻度污染、中度污染、重度污染、严重污染) 在总数据中所占百分比,按从小到大顺序执行排序。如表2 所示。
2.2 构造最优二叉树
根据6 类空气质量百分比排序结果,构造最优二叉树,过程如下:
1) 将6 类空气质量百分比作为权值的叶子节点按照从小到大的顺序排成一个有序序列: 六级( 3) 、一级( 7) 、四级( 19) 、五级( 19) 、三级( 23) 、二级( 29) ;
2) 取前两个权值最小六级( 3) 和一级( 7) 作为新节点N1,其中六级( 3) 为左子树,一级( 7) 为右子树,新节点N1 的权值为两个叶子的权值之和3+7= 10,即N1( 10) ;
3) 将N1 代替六级和一级,插入序列,保持从小到大依次排序;
4) 重复操作,直到6 类空气质量只含一棵树为止,该树就是哈夫曼树。最终结果如图2 所示。
2.3 模型构建
依据前述构造的哈夫曼树,设计支持向量机多分类模型。全局建模流程如图3 所示。
由图3 可知,建模流程可完整概述为: 数据样本收集处理、计算概率、排序后建立哈夫曼树、设计5 个支持向量机、实现多类划分。
2.4 模型仿真
综上可知,空气质量等级分类问题需要设计5 个SVM分类器,分别对应为N1、N2、N3、N4、T。
下面以N3 为例,设计SVM分类器,实现五级( 严重污染) 和三级( 轻度污染) 的划分。将五级和三级的数据放入文本文件air.txt,并对数据进行离散化处理,五级为1,三级为-1,编写支持向量机源码,用MATLAB实现等级划分,划分结果如图4 所示。其余4 个支持向量机的设计方法与其类似,在此不再赘述。
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.