第一篇：基于DV―Hop定位算法的改进
基于DV―Hop定位算法的改进
摘要：针对DV-Hop算法采用跳数乘以平均每跳跳距估算节点间的跳距，利用三边测量法或极大似然估计法估算节点坐标信息，算法过程存在缺陷从而造成定位误差过高的问题。为此提出一种基于节点密度区域划分的DVHop改进算法（DZDVHop），依据网络的连通度和节点密度限制参与估算的信标节点的跳数，采用加权质心法估算定位坐标。Matlab仿真测试结果表明，在相同的网络硬件和拓扑结构环境下，改进后的算法能有效地减少节点通信量，且平均定位误差率比传统的DVHop算法减少了13.6%左右，提高了定位精度。〖BP）〗
针对DVHop算法采用跳数乘以平均每跳跳距估算节点间的跳距，利用三边测量法或极大似然估计法估算节点坐标信息，算法过程存在缺陷从而造成定位误差过高的问题。为此提出一种基于节点密度区域划分的DVHop改进算法（DZDVHop），依据网络的连通度和节点密度限制参与估算的信标节点的跳数，采用加权质心法估算定位坐标。Matlab仿真测试结果表明，在相同的网络硬件和拓扑结构环境下，改进后的算法能有效地减少节点通信量，且平均定位误差率比传统的DVHop算法减少了13.6%左右，提高了定位精度。
关键词：
无线传感器网络；密度区域划分；节点定位；限跳机制
中图分类号：TP393
文献标志码：A
0引言
现代电子技术、检测技术和信号处理等技术的进步，促进了低功耗、多功能智能传感器的快速发展[1]。无线传感器网络（Wireless Sensor Network，WSN）是指由大量成本低廉的具有智能感知能力、计算能力、无线通信能力的传感器节点组成的网络，它可以感知、采集和处理网络覆盖区域内目标对象的信息[2-3]。作为一种新型信息获取的系统，WSN广泛应用于军事、环境监测、城市交通、灾难防控等众多领域[4]。节点定位问题是传感器网络进行目标识别、监控、定位等应用的前提，也是传感器网络应用的关键技术之一[5-7]。研究节点定位算法的意义主要体现在两方面：一是，WSN中的多数应用都依赖于传感器节点或者被检测目标的地理位置信息，不知检测目标位置而获取的任何信息都是没有意义的[8]；二是，WSN网络的运行和管理需要节点位置信息的支持。因此，准确估算节点位置，在传感器网络的应用中起着至关重要的作用。
节点定位技术分为基于测距（Range Based）的定位算法和无需测距（Range Free）的定位算法两类[3]1283，[5]39，[8]3。基于测距的定位算法原理是：通过测量节点与节点间的直线距离或角度信息估算未知节点的坐标位置，目前这类测距技术主要有RSSI（Received Signal Strength Indicator）、TOA（Time of Arrival）、TDOA（Time Difference on Arrival）和AOA（Angle of Arrival）等[1]77，[5]40。基于测距定位算法的优点是定位精度较高，缺点是网络中的节点需要增加特殊的测距设备，从而导致节点成本较高。而无需测距的定位算法原理是：不需要测量节点间的实际距离以及节点间的方位角，只根据网络中节点间的连通性、同向性等信息，就可以估算出未知节点的坐标位置，常用的无需测距技术有：APIT（Approximate PointinTriangulation test）、质心算法、DVHop（Distance VectorHop）和Amorphous等算法[5]40，[9]。无需测距定位算法的优点是：组网成本低、网络资源开销少，缺点是定位误差率稍高。实践证明无需测距定位技术更能适合多数WSN的应用，而在众多无需测距的定位算法中，DVHop算法以其算法过程的简单性和实效性成为目前应用较多的种类之一[7]2468。WSN中的节点分为两类：一类是预先已知自身位置信息的传感器节点，称之为信标节点（或“锚节点”），信标节点的坐标信息既可以通过全球定位系统（Global Positioning System，GPS）等技术自动获得，也可以在部署网络时靠人工设置[8]6；第二类节点是预先并不知道自身的位置，通常称之为待定位节点或者未知节点。这些未知节点的位置信息就需要利用本文和相关研究所探讨的相关定位算法进行估算。
1经典DVHop算法描述
美国Rutgers University的〖BP（〗Dragos 〖BP）〗Niculescu等将距离矢量路由与GPS原理相结合提出了一系列分布式定位算法（Ad Hoc Positioning System，APS）[10]。APS共包括DVHop、DV Distance、Euclidean、DV Coordinate、DV Bearing和DV Radial等6种类型。其中应用较多的是DVHop，DVHop的执行过程可归纳为以下3个阶段[1]77，[5]40，[11]。首先，接收并存储未知节点与它邻近的每个信标节点间最小跳数；信标节点向邻居节点广播包含自身地理位置信息的分组，这样网络中的所有节点都能记录下自己到每个信标节点的最小跳数。其次，计算未知节点与信标节点的跳距；每个信标节点根据上述第一个阶段的操作，记录下了自己与其他信标节点的坐标值以及它们间的跳数。最后利用式（1），就可以估算出自己的平均每跳跳距。其中：（xi，yi）、（xj，yj）是信标节点i和j的坐标，hj是信标节点i与j之间的跳数。
平均每跳跳距：
第二篇：基于RSSI测距的改进加权质心定位算法
基于RSSI测距的改进加权质心定位算法
王振朝1,2，张琦1，张峰1
（1.河北大学 电子信息工程学院，河北 保定 071002；
2.河北大学 河北省数字医疗工程重点实验室，河北 保定 071002）
摘要：基于RSSI（Received Signal Strength Indication）的三角形加权质心定位算法在测距和定位中存在较大误差，针对这一缺点提出一种改进的加权算法。在该算法中采用节点距离倒数之和代替距离和的倒数作为权值，并且根据节点距离给出加权因子作为修正，以充分利用节点信息。仿真结果验证了该算法的有效性，与原有定位算法比较其定位精度得到提升，最高可达50%。关键词：定位；RSSI；加权；修正系数
中图分类号：TM933 文献标识码：A
文章编号：1001-1390(2014)21-0000-00
*Improved Weighted Centroid Positioning Algorithm based on RSSI Ranging
WANG Zhen-chao1,2, ZHANG Qi1, ZHANG Feng1
(1.College of Electronic and Information Engineering, Hebei University, Baoding 071002, China.2.Key Laboratory of Digital Medical Engineering of Hebei Province, Hebei University, Baoding 071002, Hebei, China)Abstract：Aiming at the error existing in triangular weighted centroid positioning algorithm based on RSSI(Received Signal Strength Indication)ranging, an improved weighted algorithm is put forward in this paper.The sum of reciprocal of distance between nodes instead of the reciprocal of sum of distance has been taken as the weighted value.To make full use of the node information, the algorithm has been corrected according to the weighted factors.The simulation results verify the effectiveness of the proposed algorithm and show that the improved weighted centroid positioning algorithm can provide an additional maximum precision gain of 50%.Key words: positioning, RSSI, weighted, modified coefficient
0 引 言 1 算法模型
无线传感器网络[1-2]是面向应用的，贴近客观世
1.1 无线信号传播模型
界的网络系统。在大多数的传感器网络实际应用中，准确知道节点的方位是至关重要的。在无线传感网无线信号常用的传播路径损耗模型有:自由空络的定位机制中，需要测量节点间的实际距离或方间传播模型，对数距离路径损耗模型，Hata模型，位时经常采用的方法主要有TOA(Time of Arrival)，对数-常态分布模型等[5]。在这些理论模型中最常用TDOA（Time Difference of Arrival），RSSI和AOA的是对数-常态分布模型：（Angle of Arrival）等。但TOA需要精确的时钟同假设节点A发射信号到节点B，损耗的功率为步，TDOA同样需要比较准确的时钟，AOA需要专PAB，传播的距离为dAB，则路径损耗计算公式如下： 门的天线阵列来测量特定信号的来源方向，而RSSI
P（1）ABP(d0)10klog10(dAB/d0)x测距是一种廉价的测距技术，不需要额外的硬件支持，RADAR[3]是一个经典的基于RSSI的室内定位系整理可得：
[4-5]统,基于RSSI的定位算法是目前研究的热点。(P(PtPxxP(d0))/10kABxP(d0))/10k（2）d1010AB 本文对文献[5]中提出的基于RSSI的无线传感器网络加权质心定位算法进行了研究，对其算法进式中 Pt是节点A的信号发射功率，Px是节点B接收行了分析和讨论，并且在此基础上提出了更为合理到的信号功率。是平均xσ值为0的高斯分布随机变的加权方法，使得定位更加精确。数，其标准差范围为4～10；系数k根据传输位置的不同取值也不一样，其范围在2～5之间；d0典型取 值为1m。考虑RSSI理想模型，k=2，忽略xσ的影响，*基金项目：国家自然科学基金资助项目（61074175:61203160）；河北省自然科学基金(F2014201168)代入上式，整理(2)式可得：
dAB10(PtPxP(d0))/20（3）同时可以得到，B接收A信号时的信号强度为：
RSSI=发射功率+天线增益-路径损耗（PAB）
在实际的应用中，可以通过多次测量得到接收功率的平均值来有效的降低RSSI的系统误差。
1.2 三角形加权质心定位算法
基于RSSI的三角形质心定位算法是将RSSI测量与三角形质心定位法相结合的新型定位算法。该算法是利用各个已知节点的发射信号强度，根据未知节点接收到的每个已知节点的信号强度，计算出各条路径的信号传播损耗。在众多路径中选取其中三个信号传播损耗较小的，利用理论模型和经验模型[5-6]将传输损耗转化为距离，分别以传输距离为半径，已知节点为圆心画圆，如图1所示，计算出三个圆的交点坐标，以这三个点为顶点能够组成一个三角形，三角形的质心坐标即为未知节点的坐标[6]。
但是以上定位算法并没有考虑未知节点与已知节点距离的远近对定位的影响，而将三个参与定位的节点的作用等同，造成较大的定位误差。文献[5]提出了一种改进的定位算法，为参与定位的节点增加了权值，以体现不同顶点的贡献值。根据对数-常态分布模型绘制的RSSI曲线分析图[5]可知，已知节点到未知节点的距离越近，由RSSI值的偏差产生的绝对距离误差越小。因此，距离越近的节点权重越大，距离远近与权重大小呈反比的关系[7]。而三角形的每个顶点由两个距离确定，故权值选择为
1dAdB（假设圆A与圆B相交，圆心距交点的距离分别为dA和dB，如图1），故将算法的公式修正为：
xAxBxCddAdBdBCdAdCx1d11AdBdBdCdAdC（4）
yAyyCyddBABdBdCdAdC1dd11ABdBdCdAdCdAhdBdC 图1 加权质心算法原理图
Fig.1 Schematic of triangular weighted centroid
positioning algorithm 改进的三角形加权质心定位算法
上述的加权算法虽然考虑到了距离的不同对定
位造成的不同影响，提出加权因子
1d，进而提
AdB高了定位精度，然而在权值[8]的选择上依然存在一些不合理的地方。两个已知节点的半径和的倒数这个因子的选取，使得dA和dB成为决定未知节点位置的关键。然而dA和dB中数值较大的一个会在这个因子中起到更大的作用，使得较小的数值对应的节点所发挥的作用弱化，造成定位误差。在本论文的算法中，对权值的选择上进行了修正。首先是改变权重
中dA和dB地位上的主导关系，将1d变为AdB1d1，充分利用了节点测量数据的信息；其次为AdB了进一步改善权值的决定权，防止修正过度，采取增加幂值的方法：
111nm
dAdBdAdB这个修正方法起到了避免次要数据起主要作用的情况发生，并且可以有效地防止修正过度。例如，dA>dB时，与dA相关的已知节点和未知节点的距离更远，在公式中应该起次要作用，而对于修正前的系数1dd来说，dA
却起到了主要作用，淹没了应
AB该起主要作用的dB。而本文给出的修正系数可以使较小的数起主要作用，即距离未知节点较近的已知节点有较大权重，并通过调整n、m的值调整修正的程度。
修正程度n、m的研究较为繁琐，由于n、m是与距离dA、dB有关的两个变量，（1）式中参数的变化会影响dA、dB与n、m的取值，所以如果直接研究dA、dB与n、m关系会比较复杂。为了计算方便同时提高定位精度，这里采用比值的方法，利用两者的比值dA作为dB的幂值。考虑到应用实际，我dB们这里主要讨论已知节点与未知节点间的距离都大于1的情况。
在dA和dB都大于1的条件下，假设n=1，mdA。例如当d>d时，m>1，这时因子1的AB
dBmdB存在使得在系数
11中原本起主要作用的dB所dAdB起作用稍微弱化，以防止过度修正，这样可以进一步充分利用数据信息。修正以后的算法公式为：
111111x()x()x()ABCdAdAdAdAdAdAdBdBdBdBdCdCdCdCx1112()dAdAdAdBdBdCdC
（5）111111yA()yB(dA))yC()dAdAdAdAdAdBdBdBdBdCdCdCdCy1112()dAdAdAdBdBdCdC3 改进后的定位算法实现步骤
改进后的三角形质心算法定位的实现过程：
(1)将已知节点命名为锚节点[9-10]，锚节点周期性地向周围广播信息，信息中包括自身节点ID号及其坐标。
(2)未知节点根据接收到的信息，只记录同一个锚节点的RSSI值，当接收到一定数量的RSSI值后，对多个RSSI数据取均值，作为接收到的这个锚节点的RSSI值；
(3)当未知节点收到一定数量的锚节点信息后，停止接收信息，将RSSI从强到弱对锚节点排序，建立2个集合。锚节点集合：
(6)定义定位误差为Er，其真实位置为(x0 , y0)，则定位误差Er为：
Er(xhx0)2(y ny0)2f{(a1,x1,y1),(a2,x2,y2),(a3,x3,y3),(a4,x4,y4),...,(an,xn,yn)}
锚节点依据RSSI从大到小排列的集合： 仿真
利用Matlab对算法进行仿真实验以验证该算法的有效性，并与加权的三角形质心定位算法进行对比。假设在100m×100m的正方形区域内，均匀地放置锚节点的数量分别为25、36、64、81，节点的无线射程距离相同，通信半径为30m，且为圆形区域，能够保证各个节点都可以正常接收RSSI信息，然后在该区域内随机放置一个节点进行定位，试验进行100次，得到定位误差数据如下所示：
表1 两种算法的误差对比数据 Tab.1 Data contrast of the two algorithms
锚节点数量 加权的三角形质心改进的加权三角形质误差下降比
/个 25 36
算法(误差/m)
3.4 2.9 1.1 0.8
心算法（误差/m）
2.4 1.8 0.6 0.4
例（%）29 38 45 50 d{a1,a2,a3,a4,...,an}
(4)选取RSSI值大的前三个并利用理论模型和经验模型将其转化为锚节点与未知节点之间的距离，即：
{a1,d1},{a2,d2},{a3,d3}。
(5)利用本文的算法，能够得出未知节点的估计位置(xh , yh)。
81
3.53加权算法改进的加权算法---米2.5/离距2差误1.510.***090锚节点个数/个
图2 两种算法的误差分析对比
Fig.2 Error analysis contrast of the two algorithms 从表1以及图2中可以看出：本文提出的改进后的三角形加权质心定位算法对于未知节点的定位精度较文献[5]中的算法有了较大程度的提高；随着锚节点数量的增多，定位精度也随之提高，这是因为当未知节点距离锚节点距离相对较远时，利用RSSI测距技术定位会存在较大的干扰，造成定位有较大的误差。本文的算法是在RSSI的基础上对三角形质心定位算法的改进，故修正的精度会跟锚节点的数量有一定的关系，在一定范围内，锚节点数量越多，定位的精度也越高。5 结束语
基于RSSI测距的三角形加权质心算法在实际的定位应用中误差较大，这是由于在权值的选择上存在一些问题。本文在文献[5]的基础上采用测试距离倒数之和代替距离和的倒数作为权值，同时根据测试距离给出了修正因子，这样可以防止修正过度和信息淹没，以提高定位精度。在相同条件下，仿真效果明显优于文献[5]中的三角形加权质心算法，定位精度最高可提高50%。
参 考 文 献
[1] 李晓维.无线传感器网络技术[M].北京: 北京理工大学出版社, 2007.[2] 孙利民, 李建中, 陈渝, 等.无线传感器网络[M].北京: 清华大学出版社, 2005.[3] Bahl P, Padmanabhan VN.RADAR: An In-building RF-based User Location and Tracking System[C].//Proc.of the IEEE INFOCOM 2000, Tel Aviv: [s.n.].2000, 2: 775-784.[4] ALIREZAN, JACEKI.A Testbed for Localizing Wireless LAN Devices Using Received Signal Strength[C].//Proceedings of 6th Annual Communication Networks and Services Research Conference
(CNSR2008).Halifax, Canada, 2008: 481-487.[5] 陈维克, 李文锋, 首珩, 等.基于RSSI的无线传感器网络加权质心定
位算法[J].武汉理工大学学报, 2006, 20(12): 2695-2700.CHEN Wei-ke, LI Wen-feng, SHOU Heng, et al.Weighted Centroid Localization Algorithm Based on RSSI for Wireless Sensor Networks[J].Journal of Wuhan University of Technology, 2006, 20(12): 2695-2700.[6] 林 玮, 陈传峰.基于RSSI的无线传感器网络三角形质心定位算法[J].现代电子技术, 2009, 32(2): 180-182.LIN Wei, CHEN Chuan-feng.RSSI-based Triangle and Centroid
Location in Wireless Sensor Network[J].Modern Electronics Technique, 2009, 32(2): 180-182.[7] 刘运杰, 金明录, 崔承毅.基于RSSI的无线传感器网络修正加权质心
定位算法[J].传感技术学报, 2010, 23(5): 716-721.LIU Yun-jie, JIN Ming-lu, CUI Cheng-yi.Modified Weighted Centroid
Localization Algorithm Based on RSSI for WSN[J].Chinese Journal of Sensors and Actuators, 2010, 23(5): 716-721.[8] 朱博, 陈曙.一种无线传感器网络质心定位改进算法[J].传感技术学
报, 2010, 23(6): 868-872.ZHU Bo, CHEN Shu.An Improved Centroid Localization Algorithm for Wireless Sensor Network[J].Chinese Journal of Sensors and Actuators, 2010, 23(6): 868-872.[9] 神显豪, 杨小平.基于RSSI的WSN节点改进质心定位算法[J].微计
算机信息(测控自动化), 2010, 26(11-1): 213-214.SHEN Xian-hao, YANG Xiao-ping.Improved RSSI-based Centroid
Localization Algorithm for Wireless Sensor Networks[J].Control and Automation Publication Group.2010, 26(11-1): 213-214.[10] 李娟, 王珂, 李莉.基于锚圆交点加权质心的无线传感器网络定位算
法[J].吉林大学学报(工学版), 2009, 39(6): 1649-1653.LI Juan, WANG Ke, LI li.Weighted Centroid Localization Algorithm
Based on Intersection of Anchor Circle for Wireless Sensor Network[J].Journal of Jilin University(Engineering and Technology Edition), 2009, 39(6): 1649-1653.作者简介:
王振朝（1958—），男，山东鄄城人，河北大学电子信息工程学
院教授，博士，主要从事工业数据通信及控制网络，电力线载波通信技术及其应用，电磁场的生物效应等研究方向。
张琦(1986—)，男，硕士研究生，主要研究方向为无线自组网。张峰(1987—)，男，硕士研究生，主要研究方向为无线自组网。
收稿日期：2012-09-12;修回日期：2012-09-12
（田春雨
编发）
第三篇：新课程算法初步的教学定位探讨
新课程算法初步的教学定位探讨
内容摘要：“算法初步”是高中数学课程中全新的内容，算法思想已成为现代人应具备的一种数学素养。由于算法初步的新生性,目前我们对它的定位把握不够，有很多老师把算法课上成了计算机课，甚至于有些学校干脆请计算机老师来教数学课中的算法.本文将从新课程标准对算法的要求、学生认知能力及各地的高考要求这三个方面对算法的教学定位做进一步探讨研究,并提出了相应的教学建议。
关键词：数学课程标准；算法初步；教学定位
一
问题的提出
《普通高中数学课程标准（实验）》（以下简称《标准》）确定了高中数学课程的总目标：“使学生在九年义务教育基础上，进一步提高作为未来公民所必要的数学素养，以满足个人发展与社会进步的需要。”在具体目标中指出：使学生“获得必要的数学基础知识和基本技能，理解基本的数学概念、数学结论的本质，了解概念、结论产生的背景、应用，体会其中所蕴含的数学思想和方法，以及它们在后续学习中的作用，通过不同形式的自主学习、探究活动、体验数学发展和创造的历程。”
算法初步在新课标中是必修模块数学3中的内容之一。算法思想源远流长，中国古代数学中就蕴涵了丰富的算法思想。由于西方演绎数学的常足进步，算法数学曾一度被人们所忽略。但随着现代信息技术的飞速发展，算法重新焕发出了前所未与的活力，在科学技术、社会发展中发挥着越来越大的作用，并且日益融入社会生活的许多方面，算法思想已成为现代人应具备的一种数学素养。
算法作为新名称，在以前的数学教材中没有出现，但算法本身，学生并不陌生，小学中的加减乘除四则运算，初中的解方程的算法，解不等式的算法，因式分解的算法等等，都是同学们思想的内容。由于算法初步是新课程中新增内容，所以目前我们对它的定位把握不够，有很多老师把算法课上成了计算机课，甚至于有些学校干脆请计算机老师来教数学课中的算法，所以我们有必要对算法的教学定位做进一步探讨研究。二 “算法”内容的定位分析
2.1从新课程标准对算法的要求中研究算法教学定位
《高中数学课程标准》中指出：“算法是数学及其应用的重要组成部分，是计算科学的重要基础，算法思想已成为现代人应具备的一种数学素养。在本模块中，学生将在义务教育阶段初步感受算法思想的基础上，结合对具体教学实例的分析，体验程序框图在解决问题中的作用；通过模仿，操作，探索，学习设计程序框图表达解决问题的过程，体会算法的基本思想及算法的重要性和有效性，发展有条理地思考与表达的能力，提高逻辑思维能力”。《标准》中特别强调：“不要将此部分内容觉得处理成程序语言的学习和程序设计”。
《高中信息技术课程标准》中指出：“本模块旨在使学生进一步体验算法思想，了解算法和程序设计在解决问题过程中的地位和作用；能从简单问题出发，设计解决问题的算法，并能初步使用一种程序设计语言编制程序实现算法解决问题。本模块为选修模块。本模块的教学，应注意与数学课程中有关内容的衔接，要强调理论与实践的结合，引导学生注意寻找、发现身边的实际问题，进而设计出算法和计算机程序去解决这些问题。教师要注意发现对程序设计有特殊才能的学生，根据具体情况为他们提供充分的发展空间。本模块强调的是通过算法与程序设计解决实际问题的方法，对程序设计语言的选择不作具体规定”。
从这两门课程的课程标准的对比中可以看出，两门课程的主要区别在于：数学课程中算法教学的主要目的是使学生体会算法的思想，提高逻辑思维能力；信息技术课程的主要目的是设计解决问题的算法，并能初步使用一种程序设计语言编制程序实现算法解决问题，在程序设计语言的要求上技术课比数学课的要求高很多。两门课程的联系在于：所设计的算法正确与否要通过遍程并且运行程序进行验证，借助于程序语言可以使算法得以实现；反之要设计程序就必须弄清算法原理，从这一点上，可以说，算法教学是程序语言教学的基础，程序语言教学是算法教学必要的延续，两者相辅相成。
2.2从学生认知能力来研究算法教学定位
与以往的课程目标相比，新的课程目标着眼于人终身学习和个性发展，目标中除规定了外显行为外，更加注重对学习者的内部心理过程的描述，因此，“算法初步”课程目标需要心理学的角度加以理解。例如，对大部分的学生来说。从“算法初步”课中能学到哪些“有用”的知识？在计算机技术日新月异的今天，还有 必要学习“算法初步”？短短十二个学时能学会算法吗？“算法初步”课的基础教育性质体现在哪里？它是如何支撑学生的进一步发展的？等等。
在高中阶段，“算法初步”课程应该是让学生学习那些具有广泛意义的知识和方法，是“为迁移而教”，其实质是塑造学生良好的认知结构。
何为认知结构？奥苏伯尔（D.P.Ausubel）认为,所谓认识结构，就是学习者头脑里的知识结构。广义地说，它是学习者的观念的全部内容和组织；狭义地说，它是学习者在某一特殊知识领域内的观念的内容和组织。学习者学习时，新旧知识通过反复同化，最后形成一个综合贯通的网络结构。从认识心理学的这一基本理论来看，学习者认识结构的建立是一个长期的过程，教学的意义在于尽可能帮助学生建立一个合理的认识结构。一般而言，认识结构建立得越合理，有效学习发生的可能性就越大；认识结构越完善，复杂程序越高，学习者的外显能力就越强。从这方面看，“算法初步”课程目标就是要学生已有的适当观念上，帮助他们建立尽可能合理的算法初步认识结构，学习用算法初步的思想方法解决问题，培养学习算法初步的兴趣爱好，为学生将来的发展提供该领域的知识与能力准备。
那么，什么样的算法初步认识结构才是合理的呢？合理的算法初步认识结构应该是算法初步的一般规律及其基本思想方法的学习者认识结构中的合理映射，是利用算法初步解决问题的能力的合理映射，是利用算法初步解决问题的能力的合理映射，同时还是乐于此道的态度的合理映射（延伸、收获、体验），它是一个系统结构，而不是程序框图、方法技巧的简单堆砌，知识、技能、能力间的联系是非人为的和实质性的。对于高中生来说，这一认识结构所映射的是算法的最具普遍意义的知识体系，是灵活运用习得的知识改造旧有观念，以及解决基本问题的能力，并形成积极主动的探究态度，在此基础上，学生可以通过继续学习逐步完善这一认识结构。
学生这一阶段的认知结构特点表现为：易于接受具体的、特殊的、有趣的数学知识，难以接受抽象的、一般的、枯燥乏味的数学知识。所以在教材的安排中体现了一种从特殊到一般的思想。教材中也是从具体实例出发引出这一类问题的通法。考虑到这一认知特点，我们提出以下教学建议
2.3 从各地的高考要求中研究算法教学定位
1．（07．海南、宁夏卷.5）如果执行 如图的程序框图,那么输出的S等于()A.2450 B.2500 C.2550 D.2652
2.(07.山东卷.10)阅读如右图所示的程序
框图,若输出的 n是100,则输出的 变量S和T的值依次是()A 2550,2500 B 2550,2550 C 2500,2500 D 2500,2550 以上两道高考题都在考查学生的识图能力和程序框图的应用，以及学生对条件语句和循环语句的理解。
纵观海南，山东，宁夏等省市算法中的高考题可以发现，循环结构是考试的重点，所以它也是我们教学的重点和难点。这也提醒我们教师在教学中要准确定位，不要把难度拔得太高。
三 对算法内容的教学建议
(1)在教学中要时时联系新课标,注意突出算法思想，使学生经历通过模仿、探索、操作、设计程序框图表达解决问题等的过程，而不应在将算法内容单纯处理成程序语言的学习和程序设计,但在教学中要能借信息技术之东风助算法扬帆起航。(2)在教学中要多从学生的认知情况出发, 重视从特殊到一般的教学思想,多选择实例进行教学.在选取实例教学时要注意：
① 选取的实例是具体的、鲜活的、是学生能够感受到的或是他们已经积累的知识。如我国古代数学著作《九章算术》中有一个著名的“鸡兔同笼”问题：“今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何?”利用此例引入算法含义能够提升学生的学习兴趣。
② 所选的例子不要太难,例子太难容易是学生产生厌学心理。所选取的例子要有一定的基础性要蕴涵丰富的算法思想，能够让学生从中学习算法的“三基”————基本思想、基本结构以及基本语句。例如：在讲解选择结构时，可以选取比较基础且具有代表意义的分段函数的例子，这样既能帮助学生理解选择结构的基本思想，又能帮助学生更好地掌握分段函数。(3)在教学中要多注意对高考题的积累和对高考要求的准确把握,注意循序渐进，逐层深入，分散难点。多重视条件语句和循环语句的教学.参考文献: [1] 中学数学课程教材研究开发中心.普通高中课程标准实验教科书·数学3.人民教育出版社，2004.[2] 中华人民共和国教育部.普通高中数学课程标准.北京.人民教育出版社,2003 [3] 中华人民共和国教育部.普通高中技术课程标准.北京.人民教育出版社,2003 [4] 皮连生.教育心理学.上海.上海教育出版社,2004 [5] 容德基教育研究中心.2007年高考卷汇编数学(文科).内蒙古少年儿童出版社 [6] 王建国、刘彬.高中数学算法教学内容难度的比较与研究.北京教育学院学报第一卷第六期
[7] 熊芹.对高中必修课“算法初步”教学策略的探讨.中国数学教学,2006年第4期
第四篇：机器学习算法优缺点改进总结
Lecture 1 Introduction to Supervised Learning（1）Expectatin Maximization(EM)Algorithm(期望值最大)（2）Linear Regression Algorithm(线性回归)（3）Local Weighted Regression(局部加权回归)（4）k-Nearest Neighbor Algorithm for Regression(回归k近邻)（5）Linear Classifier(线性分类)（6）Perceptron Algorithm(线性分类)（7）Fisher Discriminant Analysis or Linear Discriminant Analysis(LDA)（8）k-NN Algorithm for Classifier(分类k近邻)（9）Bayesian Decision Method(贝叶斯决策方法)Lecture 2 Feed-forward Neural Networks and BP Algorithm（1）Multilayer Perceptron(多层感知器)（2）BP Algorithm
Lecture 3 Rudiments of Support Vector Machine（1）Support Vector Machine(支持向量机)（此算法是重点，必考题）此处有一道必考题
Lecture 4 Introduction to Decision Rule Mining（1）Decision Tree Algorithm（2）ID3 Algorithm（3）C4.5 Algorithm（4）粗糙集……
Lecture 5 Classifier Assessment and Ensemble Methods（1）Bagging（2）Booting（3）Adaboosting Lecture 6 Introduction to Association Rule Mining（1）Apriori Algorithms（2）FP-tree Algorithms Lecture 7 Introduction to Custering Analysis（1）k-means Algorithms（2）fuzzy c-means Algorithms（3）k-mode Algorithms（4）DBSCAN Algorithms Lecture 8 Basics of Feature Selection（1）Relief Algorithms（2）ReliefF Algorithms（3）mRMR Algorithms最小冗余最大相关算法（4）attribute reduction Algorithms
比较了几种分类算法性质。（以下两个表格来自两篇该领域经典论文）
Lecture 1 Introduction to Supervised Learning（1）Expectatin Maximization(EM)Algorithm(期望值最大)①算法思想：
EM算法又称期望最大化算法，是对参数极大似然估计的一种迭代优化策略，它是一种可以从非完整的数据集中对参数进行极大似然估计的算法,应用于缺损数据，截尾数据，带有噪声的非完整数据。
最大期望算法经过两个步骤交替进行计算：
第一步计算期望（E）：也就是将隐藏的变量对象能够观察到的一样包含在内，从而计算最大似然的期望值；
另外一步是最大化（M），也就是最大化在E步上找到的最大似然期望值，从而计算参数的似然估计。M步上找到的参数然后用于另一个E步计算。
重复上面2步直至收敛。
②优点：1）Ｍ步仅涉及完全数据极大似然，通常计算比较简单
2）收敛是稳定的，因为每次迭代的似然函数是不断增加的。
③缺点：1）表现在对缺失数据较多或是多维高斯分布的情形下，计算量大，收敛速度较慢。
2）对于某些特殊的模型，要计算算法中的M步，即完成对似然函数的估计是比较困难的。
3）在某些情况下，要获得EM算法中E步的期望显式是非常困难的。
4）EM算法的收敛速度，非常依赖初始值的设置，设置不当，计算代价相当大。
5）EM算法中的M-Step依然是采用求导函数的方法,所以它找到的是极值点,即局
部最优解,而不一定是全局最优解。④改进：针对1）改进：扩大参数空间来加快收敛
针对2）改进：ECM算法，该算法通过在Ｍ步构建计算比较简单的小循环对EM
算法进行了改进，从而使期望函数极大化更加容易和有效，从而解决这一问题。
针对3）改进：MCEM算法，将E步积分求期望用蒙特卡洛模拟方法来实现，使
得E步求期望更容易实现。
针对4）初始值的获取可以通过k-means算法，层次聚类算法或是数据数据进行随
机分割，然后重复EM效果进行初始点选择。
针对5）结合遗传算法的全局搜索能力，扩大EM算法的搜索空间，有效降低EM
算法对初始值的依赖度，改善局部最优值的缺陷。
（2）Linear Regression Algorithm(线性回归)①算法思想：
线性回归(Linear Regression)是利用称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。这种函数是一个或多个称为回归系数的模型参数的线性组合。只有一个自变量的情况称为简单回归,大于一个自变量情况的叫做多元回归。
回归模型：
i
其中 和C是未知参数，对于每个训练样本(xi，yi)可得到h(xi)，用来预测真实值y。损失函数：
即误差值的平方。
1：对于训练集，求取θ，使得损失函数最小。（使用最小二乘法，梯度下降法）2：对于新输入x，其预测输出为θTx ②优点：结果易于理解，实现简单，计算简单
③缺点：1）对于非线性的数据拟合效果不好（原因：因为线性回归将数据视为线性的，可能出现欠拟合现象，导致结果不能取得最好的预测效果）
2）如果训练数据如果有些数据偏差特别大，这回造成最后训练的模型可能对整体
具备很好的准确性
④改进：针对2）改进 ：局部加权回归
数据都不（3）Local Weighted Regression(局部加权回归)①算法思想：
给每个待预测点周围的点赋予一定的权重,越近的点权重越高,以此来选出该预测点对应的数据子集,然后在此数据子集上基于最小均方差进行普通的回归.局部加权回归实质上是对于需要预测的点，只是根据其附近的点进行训练，其他的没有改变。
对于局部线性加权算法：
1：对于输入x，找到训练集中与x邻域的训练样本
2：对于其邻域的训练样本，求取θ，使得其
∈x的邻域）最小。其中w(i)为权重值。
3.预测输出为θTx
4.对于新输入，重复1-3过程。
其中
τ 为带宽(bandwidth)常量，距离输入越远，权重越小，反之越大。
②优点：1）局部加权回归还是对训练数据拟合的比较好
2）不太依赖特征的选择，而且只需要用线性模型就能够训练出不错的拟合模型、③缺点：1）计算量较大。（因为局部加权回归的损失数随着预测值的不同而不同，这样θ
就无法事先确定，每次预测时都需要扫描所有的数据并重新计算θ）
2）局部加权回归容易出现过拟合现象，过拟合现象很明显
3）关注局部的训练数据，忽略了全局数据，如果预测点在出现偏差的训练数据附
近，那么预测值会偏差很大。
④改进：
（4）k-Nearest Neighbor Algorithm for Regression(回归k近邻)①算法思想：
通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。②优点：
1）简单、有效。
2）重新训练的代价较低（类别体系的变化和训练集的变化，在Web环境和电子商务应用中是很常见的）。3）计算时间和空间线性于训练集的规模（在一些场合不算太大）。
4）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
5）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。③缺点：
（1）KNN在对属性较多的训练样本进行分类时，由于计算量大而使其效率大大降低，效果不是很理想。
（2）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。
（3）对数据的局部结构比较敏感。如果查询点是位于训练集较密集的区域，那预测相对比其他稀疏集来说更准确。（4）对k值敏感。
（5）维数灾难：临近距离可能被不相干属性主导（因此特征选择问题）④改进：
（1）分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。（2）分类效果：采用权值的方法（和该样本距离小的邻居权值大）来改进，Han等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN(weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。
（3）该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。（4）K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。
（5）该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
（5）Linear Classifier(线性分类器)①算法思想：线性分类器使用线性判别函数，实现线性判别函数分类的方法有感知器算法、LMSE分类算法和Fisher分类。
在分类问题中，因变量Y可以看做是数据的label，属于分类变量。所谓分类问题，就是能够在数据的自变量X空间内找到一些决策边界，把label不同的数据分开，如果某种方法所找出的这些决策边界在自变量X空间内是线性的，这时就说这种方法是一种线性分类器。
C1和C2是要区分的两个类别，在二维平面中它们的样本如上图所示。中间的直线就是一个分类函数，它可以将两类样本完全分开。
线性分类器在数学上被理解为线性判别函数(Linear Discriminant Functions)，在几何上可以理解为决策超平面(Decision Hyperplanes)。②优点：算法简单
③缺点：只能处理线性问题
④改进：要处理其他非线性问题，可以向高维转化，例如用SVM方法。线性分类器是分类方法，不是具体算法。
（6）Perceptron Algorithm(感知器算法)①算法思想：
感知机（Perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。②优点：
（1）感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。算法简单且易于实现；
（2）它提出了自组织自学习的思想。对能够解决的问题有一个收敛的算法，并从数学上给出了严格的证明。（3）当样本线性可分情况下，学习率 合适时，算法具有收敛性。③缺点：
（1）即感知机无法找到一个线性模型对异或问题进行划分。
（2）其实不光感知机无法处理异或问题，所有的线性分类模型都无法处理异或分类问题。（3）收敛速度慢；当样本线性不可分情况下，算法不收敛，且无法判断样本是否线性可分。
④改进：单个感知器虽然无法解决异或问题，但却可以通过将多个感知器组合，实现复杂空间的分割。（7）线性判别分析（LDA，Linear Discriminant Analysis）①基础概念
（1）判别分析概念
根据已知对象的某些观测指标和所属类别来判断未知对象所属类别的统计方法。利用已知类别的样本信息求判别函数，根据判别函数对未知样本所属类别进行判别。（2）判别分析分类
按判别组数来分，有两组判别分析和多组判别分析
按数学模型（函数形式）来分，有线性判别分析和非线性判别分析
按判别方法来分，有Fisher判别分析、Bayes判别分析和距离判别（K-NN）注:线性判别分析就是一般化的Fisher判别分析（3）Fisher判别分析与Bayes判别分析优缺点比较
Fisher判别方法对总体分布没有特殊要求，但是Fisher判别法未考虑各总体出现概率的大小，不能给出后验概率以及错判造成的损失。
Bayes判别法可以给出后验概率以及错判造成的损失。但是要求即各种变量必须服从多元正态分布、各组协方差矩阵必须相等、各组变量均值均有显著性差异。②LDA缺点
LDA有两个突出缺点:（1）处理高维图像时容易产生“小样本问题”, 即样本维数大大超过训练图像个数的问题；（2）由此引发的边缘类主导特征空间分解的问题。（3）LDA的其余缺点（限制）：
LDA至多可生成C-1维子空间。
LDA不适合对非高斯分布的样本进行降维。
LDA在样本分类信息依赖方差而不是均值时，效果不好。
LDA可能过度拟合数据。
③针对“小样本问题”的改进方法
可以利用本文设计的改进PCA 算法与LDA 算法相结合来解决小样本问题，即将结合了基于标准差和局部均值的图像增强处理算法的PCA 算法与LDA 算法相结合。具体的应用过程即为: 先采用改进的PCA 算法对样本进行降维处理，以便确保样本的类内离散度矩阵为非奇异的，利用改进的PCA 算法将原始样本图像往一个特征子空间中投影，从而使得样本的类内离散度矩阵是非奇异的。再利用LDA 算法在次特征子空间中求得最优变换。
LDA与PCA的比较
两者都是为了在对原始数据降维之后进行分类。PCA（Principal Component Analysis，主成分分析）是无监督的方式，它没有分类标签，降维之后需要采用K-Means或自组织映射网络等无监督的算法进行分类。LDA是有监督的方式，它先对训练数据进行降维，然后找出一个线性判别函数。（8）k-NN(k-Nearest Neighbor for classifier,分类最近邻估计)①算法思想：（1）k-NN介绍
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。（2）k-NN概念
k-NN算法通常以“欧氏距离(Euclidean Distance)”为其分类模型, 欧氏距离公式的定义如下: 设在n 维空间中有两个点X =(x1,x2,„,xn)和Y =(y1,y2,„,yn), 它们之间的欧氏距离定义为:
其中, n是维数, Xi和Yi分别是X和Y的第k个属性值。②优点
（1）简单，易于理解，易于实现，无需估计参数，无需训练
（2）适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型）
（3）特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好.③缺点
（1）计算量大，由于要逐个计算到每条记录的欧氏距离, 对于海量数据, 该算法时间效率非常低。它在对每一个查询实例(Query Instance)进行分类时, 都需要搜索整个训练集来寻找最近邻, 所以它的运算开销巨大, 时间代价高昂, 这导致了它的运行速度非常低下。
（2）可解释性较差，无法给出决策树那样的规则。
（3）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。（4）由于所有属性均等地参与计算, 没有突出属性的重要程度, 分类结果易受单个属性的影响;④改进
缺点1：目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。缺点4：利用信息增益来衡量属性的重要程度(即属性权重系数),将属性划分为关键属性、次要属性及无关属性, 解决属性均等用力的问题;缺点3，可考虑从K值设定回答
1、k值设定为多大？
k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响）
k值通常是采用交叉检验来确定（以k=1为基准）经验规则：k一般低于训练样本数的平方根
补充去年相关习题：
请阐述 kNN近邻分类算法的基本思想，并分析它的主要优缺点。关于 k 的取值，你有什么合理的建议（至少 1 条）。优点
(1)简单，易于理解，易于实现，无需估计参数，无需训练
(2)适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型）(3)特别适合于多分类问题，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好 缺点
(1)懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢
(2)当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有 可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数；
(3)可解释性较差，无法给出决策树那样的规则。k值设定
k值选择过小，得到的近邻数过少，会降低分类精度，同时也会放大噪声数据的干扰；而如果k值选择过大，并且待分类样本属于训练集中包含数据数较少的类，那么在选择k个近邻的时候，实际上并不相似的数据亦被包含进来，造成噪声增加而导致分类效果的降低。
k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响）K值设定的建议
k值通常是采用交叉检验来确定（以k=1为基准）k一般低于训练样本数的平方根
（9）贝叶斯决策方法（Bayesian Decision Method）①贝叶斯决策概念
贝叶斯决策（Bayesian Decision Theory）就是在不完全情报下，对部分未知的状态用主观概率估计，然后用贝叶斯公式对发生概率进行修正，最后再利用期望值和修正概率做出最优决策。贝叶斯决策属于风险型决策，决策者虽不能控制客观因素的变化，但却掌握其变化的可能状况及各状况的分布概率，并利用期望值即未来可能出现的平均状况作为决策准则。
贝叶斯决策理论方法是统计模型决策中的一个基本方法，其基本思想是：
已知类条件概率密度参数表达式和先验概率。
利用贝叶斯公式转换成后验概率。
根据后验概率大小进行决策分类。②贝叶斯决策方法优缺点 优点：
贝叶斯决策能对信息的价值或是否需要采集新的信息做出科学的判断
它能对调查结果的可能性加以数量化的评价,而不是像一般的决策方法那样,对调查结果或者是完全相信,或者是 完全不相信
如果说任何调查结果都不可能完全准确,先验知识或主观概率也不是完全可以相信的,那么贝叶斯决策则巧妙地将这两种信息有机地结合起来了
它可以在决策过程中根据具体情况下不断地使用,使决策逐步完善和更加科学 缺点：
它需要的数据多,分析计算比较复杂,特别在解决复杂问题时,这个矛盾就更为突出
有些数据必须使用主观概率,有些人不太相信,这也妨碍了贝叶斯决策方法的推广使用 ③贝叶斯决策改进方法
将决策问题转化成收益矩阵,通过对收益矩阵的分析,得出各行动方案的期望值,按照一定的准则选出最优方案。
以各状况下最大收益值或效用值为基础,求出MaxE(x),以此作为完全确定情况下的收益值,用该值减去最优方案的期望值得出完全信息价值(EVPⅠ),根据完全信息期望值判断是否需要补充信息量。
在第2步得到肯定回答后,首先在预先后验分析中从理论上把各种可能的抽样方案及结果列举出来,计算各种抽样方案的抽样信息期望值EVSI=EVPI-R(n),其中R(n)为抽样风险,其大小是样本大小的函数。
以EVSI-C(其中C为抽样成本)作为标准选取最大值对应的抽样方案为最优抽样方案。
按照理论上得出的最优抽样方案进行抽样,然后,根据贝叶斯理论公式推导出后验概率分布的数字描述,最后,以此为依据按照贝叶斯决策准则选出最优方案。补充朴素贝叶斯
朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。
同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。
补充朴素贝叶斯优点：
1）朴素贝叶斯算法是基于贝叶斯理论，逻辑清楚明了
2）本算法进行分类是，时间快，在内存上需要的也不大
3）本算法鲁棒性高，即使数据包含的噪声点，无关属性和缺失值的属性，分类性能不好又 太大的变化，健壮性好
补充朴素贝叶斯算法缺点：
1）朴素贝叶斯算法要求样本各属性直接是独立的，而真实的数据符合这个条件很少。
2）当样本数据少时，分类器可能会无法正确分类
Lecture 2 Feed-forward Neural Networks and BP Algorithm（1）Multilayer Perceptron(多层感知器)①算法思想
多层感知器（Multilayer Perceptron,缩写MLP）是一种前向结构的人工神经网络。MLP算法一般包括三层，分别是一个输入层，一个输出层和一个或多个隐藏层的神经网络组成。一个“神经元”的输出就可以是另一个“神经元”的输入。MLP可以被看作是一个有向图，由多个的节点层所组成，每一层都全连接到下一层。除了输入节点，每个神经元都有几个输入和输出神经元，每个神经元通过输入权重加上偏置计算输出值，并选择一种激活函数进行转换。一种被称为反向传播算法(BP)的监督学习方法常被用来训练MLP。MLP是感知器的推广，克服了感知器不能对线性不可分数据进行识别的弱点。
激活函数
若每个神经元的激活函数都是线性函数，那么，任意层数的MLP都可被约简成一个等价的单层感知器。实际上，MLP本身可以使用任何形式的激活函数，但为了使用反向传播算法进行有效学习，激活函数必须限制为可微函数。由于具有良好可微性，很多乙形函数，尤其是双曲正切函数（Hyperbolic tangent）及逻辑乙形函数（logistic sigmoid function），被采用为激活函数。激活函数常见的有三种，分别是恒等函数，Sigmoid函数和高斯函数。
②优点：
（1）高度的并行性
人工神经网络是由许多相同的简单处理单元并联组合而成，虽然每个单元的功能简单，但大量简单单元的并行活动，使其对信息的处理能力与效果惊人。（2）高度的非线性全局作用
神经网络系统是由大量简单神经元构成的，每个神经元接受大量其他神经元的输入，通过非线性输入、输出关系，产生输出影响其它神经元。网络就是这样互相制约相互影响，实现从输入状态空间到输出状态空间非线性映射的。网络的演化遵从全局性作用原则，从输入状态演化到终态而输出。从全局观点来看，网络整体性能不是网络局部性能的简单迭加，而表现某种集体性行为；而电脑遵从串行式局域性操作原则，每一步计算与上一步计算紧密相关，并对下一步产生影响，问题是通过算法逐步进行处理的。（3）良好的容错性与联想记忆功能
人工神经网络通过自身的网络结构能够实现对信息的记忆，而所记忆的信息是存储在神经元之间的权值中。从单个权值中看不出所储存的信息内容，因而是分布式的存储方式。这使得网络具有良好的容错性，并能进行聚类分析、特征提取、缺损模式复原等模式信息处理工作。
（4）十分强的自适应、自学习功能人工神经网络可以通过训练和学习来获得网络的权值与结构，呈现出很强的自学习能力和对环境的自适应能力。③缺点
（1）网络的隐含节点个数选取问题至今仍是一个 世界难题；
（2）停止阈值、学习率、动量常数需要采用”trial-and-error”法，极其耗时（动手实验）；（3）学习速度慢；
（4）容易陷入局部极值，学习不够充分。④改进
（1）改进BP算法（见bp）（2）权值初始化
在初始化权值的时候，我们一般需要它们在0附近，要足够小（在激活函数的近似线性区域可以获得最大的梯度）。另一个特性，尤其对深度网络而言，是可以减小层与层之间的激活函数的方差和反向传导梯度的方差。这就可以让信息更好的向下和向上的传导，减少层间差异。（3）学习率
随着时间的推移减小学习速率有时候也是一个好主意。一个简单的方法是使用这个公式：u/(1+d*t)，u是初始速率（可以使用上面讲的网格搜索选择），d是减小常量，用以控制学习速率，可以设为0.001或者更小，t是迭代次数或者时间。可以基于分类错误率自适应的选择学习率。（4）隐藏节点数 这个参数是非常基于数据集的。模糊的来说就是，输入分布越复杂，去模拟它的网络就需要更大的容量，那么隐藏单元的数目就要更大。（5）正则化参数
典型的方法是使用L1/L2正则化。
L2正则化就是在代价函数后面再加上一个正则化项：
C0代表原始的代价函数，后面那一项就是L2正则化项，它是这样来的：所有参数w的平方的和，除以训练集的样本大小n。λ就是正则项系数，权衡正则项与C0项的比重。另外还有一个系数1/2，1/2经常会看到，主要是为了后面求导的结果方便，后面那一项求导会产生一个2，与1/2相乘刚好凑整。
过拟合，就是拟合函数需要顾忌每一个点，最终形成的拟合函数波动很大。在某些很小的区间里，函数值的变化很剧烈。这就意味着函数在某些小区间里的导数值（绝对值）非常大，由于自变量值可大可小，所以只有系数足够大，才能保证导数值很大。而正则化是通过约束参数的范数使其不要太大，所以可以在一定程度上减少过拟合情况。
L1正则化项就是在原始的代价函数后面加上一个正则化项，即所有权重w的绝对值的和，乘以λ/n（这里不像L2正则化项那样）：
比原始的更新规则多出了η * λ * sgn(w)/n这一项。当w为正时，更新后的w变小。当w为负时，更新后的w变大——因此它的效果就是让w往0靠，使网络中的权重尽可能为0，也就相当于减小了网络复杂度，防止过拟合。
（2）BP Algorithm ①算法思想
BP算法是一种有监督式的学习算法，其主要思想是：输入学习样本，使用反向传播算法对网络的权值和偏差进行反复的调整训练，使输出的向量与期望向量尽可能地接近，当网络输出层的误差平方和小于指定的误差时训练完成，保存网络的权值和偏差。②优点：
（1）网络实质上实现了一个从输入到输出的映射功能，而数学理论已证明它具有实现任何复杂非线性映射的功能。这使得它特别适合于求解内部机制复杂的问题；
（2）网络能通过学习带正确答案的实例集自动提取“合理的”求解规则，即具有自学习能力；（3）网络具有一定的推广、概括能力。③缺点
主要包括以下几个方面的问题。
（1）由于学习速率是固定的，因此网络的收敛速度慢，需要较长的训练时间。对于一些复杂问题，BP算法需要的训练时间可能非常长，这主要是由于学习速率太小造成的。
（2）BP算法可以使权值收敛到某个值，但并不保证其为误差平面的全局最小值，这是因为采用梯度下降法可能产生一个局部最小值
（3）网络隐含层的层数和单元数的选择尚无理论上的指导，一般是根据经验或者通过反复实验确定。因此，网络往往存在很大的冗余性，在一定程度上也增加了网络学习的负担。
（4）网络的学习和记忆具有不稳定性。也就是说，如果增加了学习样本，训练好的网络就需要从头开始训练，对于以前的权值和阈值是没有记忆的。但是可以将预测、分类或聚类做的比较好的权值保存。
（5）网络的预测能力（也称泛化能力、推广能力）与训练能力（也称逼近能力、学习能力）的矛盾。一般情况下，训练能力差时，预测能力也差，并且一定程度上，随训练能力地提高，预测能力也提高。但这种趋势有一个极限，当达到此极限时，随训练能力的提高，预测能力反而下降，即出现所谓“过拟合”现象。此时，网络学习了过多的样本细节，而不能反映样本内含的规律。（6）网络训练失败的可能性较大，其原因有：
a 从数学角度看，BP算法为一种局部搜索的优化方法，但它要解决的问题为求解复杂非线性函数的全局极值，因此，算法很有可能陷入局部极值，使训练失败；
b 网络的逼近、推广能力同学习样本的典型性密切相关，而从问题中选取典型样本实例组成训练集是一个很困难的问题。④改进.变步长法
BP算法的有效性和收敛性在很大程度上取决于学习步长η的值。采用一般的固定长梯度下降法求解时,起码可能导致两个主要问题:局部极小解;收敛速度慢。所以,一般要求是,当训练到误差曲面的平坦区时,梯度较小,为加快收敛应使η增大;当训练到深而窄的误差曲面时,应使η减小,以免因步长过大而出现振荡现象。为加快收敛,应使η合理化,可采用变步长算法。变步长算法的基本思想是,先设一个初始步长η,若一次迭代后误差增大,则将步长乘以β(<1),沿原方向重新计算该迭代点;若一次迭代后误差减小,则将步长乘以α(>1),计算下一个迭代点,以缩短学习时间。2.加动量项法
为了加速BP算法的收敛,可考虑在权值调整算式中加入动量项,即
式中,α为动量因子,一般取0.1～0.8。这时权值修正量加上了有关上一时刻权值修改方向的记忆,加速了网络的收敛。加动量项法的具体原理:若相邻两次迭代点处的梯度方向是一致的,引入动量项可使权值的调整量增大,从而加速收敛;若相邻两次迭代点处的梯度方向相反,引入动量项可使权值的调整量减小,避免了来回振荡,加快了收敛。3.串连法
BP算法的收敛速度主要取决于输入-输出模式间非线性映射的复杂程度。显然,这种非线性映射关系越复杂,收敛时间越长。因此,对那些高度复杂的非线性问题,用两个串连的BP网络代替一个BP网络,能够有效地缩短训练时间。4.利用遗传算法优化BP算法
BP算法的优点是寻优具有精确性,但它易陷入局部极小、收敛速度慢,而遗传算法(GeneticAlgorithm,GA)是基于自然选择和遗传规律的全局优化搜索算法,具有很强的宏观搜索能力和寻优全局性。因此,在BP神经网络理论中引入遗传算法的思想,则可以很好地达到全局寻优和快速高效的目的。
Lecture 3 Rudiments of Support Vector Machine（1）Support Vector Machine(支持向量机)（此算法是重点，必考题）
①算法思想
SVM的主要思想是针对两类分类问题，寻找一个超平面作为两类训练样本点的分割，以保证最小的分类错误率。在线性可分的情况下，存在一个或多个超平面使得训练样本完全分开，SVM的目标是找到其中的最优超平面，最优超平面是使得每一类数据与超平面距离最近的向量与超平面之间的距离最大的这样的平面，对于线性不可分的情况，通过使用核函数（一种非线性映射算法）将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分。②优点
（1）小样本，并不是说样本的绝对数量少（实际上，对任何算法来说，更多的样本几乎总是能带来更好的效果），而是说与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。
（2）非线性，是指SVM擅长应付样本数据线性不可分的情况，主要通过松弛变量（也有人叫惩罚变量）和核函数技术来实现，（3）高维模式识别是指样本维数很高，例如文本的向量表示，如果没有经过降维处理，出现几万维的情况很正常，其他算法基本就没有能力应付了，SVM却可以，主要是因为SVM 产生的分类器很简洁，用到的样本信息很少（仅仅用到那些称之为“支持向量”的样本，此为后话），使得即使样本维数很高，也不会给存储和计算带来大麻烦（相对照而言，kNN算法在分类时就要用到所有样本，样本数巨大，每个样本维数再一高，这日子就没法过了„„）。③缺点
（1）SVM算法对大规模训练样本难以实施 由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。（2）用SVM解决多分类问题存在困难 ④改进：
经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有
一对多组合模式、一对一组合模式和SVM决策树； 再就是通过构造多个分类器的组合来解决。
主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：
与粗集理论结合，形成一种优势互补的多类问题的组合分类器。此处有一道必考题
Lecture 4 Introduction to Decision Rule Mining（1）ID3 Algorithm ①算法思想：
补充：
ID3算法（Iterative Dichotomiser 3 迭代二叉树3代）是一个由Ross Quinlan发明的用于决策树的算法。这个算法便是：
从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。
所以，ID3的思想便是：
自顶向下的贪婪搜索遍历可能的决策树空间构造决策树(此方法是ID3算法和C4.5算法的基础)； 从“哪一个属性将在树的根节点被测试”开始；
使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试(如何定义或者评判一个属性是分类能力最好的呢？这便是下文将要介绍的信息增益，or 信息增益率)。
然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。
②优点：
（1）分类精度高；
（2）实现比较简单，产生的规则如果用图表示出来的话，清晰易懂；
优点补充：
（4）ID3算法的假设空间包含了所有的决策树，不存在无解风险
（5）ID3算法非常适合处理离散样本数据，利用属性结果提取分类规则，且容易理解（6）引进了信息论的中的熵，使得算法得到结点最少的决策树 ③缺点：
（1）ID3算法往往偏向于选择取值较多的属性，而在很多情况下取值较多的属性并不总是最重要的属性，即按照使熵值最小的原则被ID3算法列为应该首先判断的属性在现实情况中却并不一定非常重要。例如：在银行客户分析中，姓名属性取值多，却不能从中得到任何信息。（简略写：由于使用信息增益，会在属性选择时偏向选择取值多的属性）
（2）ID3算法对于噪声数据敏感，ID3算法不能处理具有连续值的属性，也不能处理具有缺失数据的属性。
（3）用互信息作为选择属性的标准存在一个假设，即训练子集中的正、反例的比例应与实际问题领域中正、反例的比例一致。一般情况很难保证这两者的比例一致，这样计算训练集的互信息就会存在偏差。
（4）在建造决策树时，每个结点仅含一个属性，是一种单变元的算法，致使生成的决策树结点之间的相关性不够强。虽然在一棵树上连在一起，但联系还是松散的。
（5）ID3算法虽然理论清晰，但计算比较复杂，在学习和训练数据集的过程中机器内存占用率比较大，耗费资源。（计算复杂，有很多对数计算）
（6）ID3不够健壮，当有一个项数据有改变时，整棵树的结构可能改变很大。
改进：用R-C4.5的思想，在进行测试属性选择时，合并分类贡献小的分支，避免出现过细的分枝，提高树的健壮性。补充：
（7）当训练集增加或减少的时候，决策树都会随之改变，对渐进学习不方便。
④改进：（1）对决策树进行剪枝。可以采用交叉验证法和加入正则化的方法。
（2）使用基于决策树的combination算法，如bagging算法，randomforest算法，可以解决过拟合的问题（3）引入用户兴趣度
给定a(0≤a≤1)为用户对不确定知识的兴趣度，a的大小由决策者根据先验知识或领域知识来确定。它是一个模糊的概念，通常指关于某一事务的先验知识，包括领域知识和专家建议，具体到决策树学习中则是指在决策树训练过程中除了用于生成和修改决策树的实例集之外的所有影响决策树规则生成和选择的因素。
（2）C4.5 Algorithm 补充：
既然说C4.5算法是ID3的改进算法，那么C4.5相比于ID3改进的地方有哪些呢？
用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵(entropy，熵是一种不纯度度量准则),也就是熵的变化值，而C4.5用的是信息增益率。对，区别就在于一个是信息增益，一个是信息增益率。（因此，C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。）在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致overfitting。对非离散数据也能处理。能够对不完整数据进行处理 ①算法思想：
②优点：
（1）产生的分类规则易于理解，准确率较高。（2）对非离散数据也能处理。
C4.5既可以处理离散型描述属性，也可以处理连续性描述属性。在选择某节点上的分枝属性时，对于离散型描述属性，C4.5的处理方法与ID3相同，按照该属性本身的取值个数进行计算；对于某个连续性描述属性Ac，假设在某个结点上的数据集的样本数量为total，C4.5将作以下处理。
1）将该结点上的所有数据样本按照连续型描述属性的具体数值，由小到大进行排序，得到属性值的取值序列{A1c，A2c，„„Atotalc}。
2）在取值序列中生成total-1个分割点。第i（0 3）从total-1个分割点中选择最佳分割点。对于每一个分割点划分数据集的方式，C4.5计算它的信息增益比，并且从中选择信息增益比最大的分割点来划分数据集。（3）能够对不完整数据进行处理。 在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x，c(x)〉是样本集S中的一个训练实例，但是其属 性A的值A(x)未知。处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。这些片断样例（fractional examples）的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。C4.5就是使用这种方法处理缺少的属性值。（4）克服了用信息增益来选择属性时偏向选择值多的属性的不足。（5）采用了一种后剪枝方法 避免树的高度无节制的增长，避免过度拟合数据，该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下： 其中N是实例的数量，f=E/N为观察到的误差率（其中E为N个实例中分类错误的个数），q为真实的误差率，c为置信度（C4.5算法的一个输入参数，默认值为0.25），z为对应于置信度c的标准差，其值可根据c的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个悲观的估计： 通过判断剪枝前后e的大小，从而决定是否需要剪枝。 树剪枝 在决策树的创建时，由于数据中的噪声和离群点，许多分枝反映的是训练数据中的异常。剪枝方法是用来处理这种过分拟合数据的问题。通常剪枝方法都是使用统计度量，剪去最不可靠的分枝。 剪枝一般分两种方法：先剪枝和后剪枝。 先剪枝方法中通过提前停止树的构造（比如决定在某个节点不再分裂或划分训练元组的子集）而对树剪枝。一旦停止，这个节点就变成树叶，该树叶可能取它持有的子集最频繁的类作为自己的类。先剪枝有很多方法，比如（1）当决策树达到一定的高度就停止决策树的生长；（2）到达此节点的实例具有相同的特征向量，而不必一定属于同一类，也可以停止生长（3）到达此节点的实例个数小于某个阈值的时候也可以停止树的生长，不足之处是不能处理那些数据量比较小的特殊情况（4）计算每次扩展对系统性能的增益，如果小于某个阈值就可以让它停止生长。先剪枝有个缺点就是视野效果问题，也就是说在相同的标准下，也许当前扩展不能满足要求，但更进一步扩展又能满足要求。这样会过早停止决策树的生长。 另一种更常用的方法是后剪枝，它由完全成长的树剪去子树而形成。通过删除节点的分枝并用树叶来替换它。树叶一般用子树中最频繁的类别来标记。 C4.5采用悲观剪枝法，它使用训练集生成决策树又用它来进行剪枝，不需要独立的剪枝集。 悲观剪枝法的基本思路是：设训练集生成的决策树是T，用T来分类训练集中的N的元组，设K为到达某个叶子节点的元组个数，其中分类错误地个数为J。由于树T是由训练集生成的，是适合训练集的，因此J/K不能可信地估计错误率。所以用(J+0.5)/K来表示。设S为T的子树，其叶节点个数为L(s)，个数总和，为到达此子树的叶节点的元组 为此子树中被错误分类的元组个数之和。在分类新的元组时，则其错误分类个数为，其标准错误表示为：。当用此树分类训练集时，设E为分类错误个数，当下面的式子成立时，则删掉子树S，用叶节点代替，且S的子树不必再计算。 ③缺点： （1）构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 （2）C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。（3）在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。④改进： （1）SLIQ算法 SLIQ算法对C4.5决策树分类算法的实现方法进行了改进，在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。 1)预排序。对于连续属性在每个内部结点寻找其最优分裂标准时，都需要对训练集按照该属性的取值进行排序，而排序是很浪费时间的操作。为此，SLIQ算法 采用了预排序技术。所谓预排序，就是针对每个属性的取值，把所有的记录按照从小到大的顺序进行排序，以消除在决策树的每个结点对数据集进行的排序。具体实 现时，需要为训练数据集的每个属性创建一个属性列表，为类别属性创建一个类别列表。 2)广度优先策略。在C4.5算法中，树的构造是按照深度优先策略完成的，需要对每个属性列表在每个结点处都进行一遍扫描，费时很多，为此，SLIQ采用 广度优先策略构造决策树，即在决策树的每一层只需对每个属性列表扫描一次，就可以为当前决策树中每个叶子结点找到最优分裂标准。 SLIQ算法由于采用了上述两种技术，使得该算法能够处理比C4.5大得多的训练集，在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。 然而它仍然存在如下缺点： 1)由于需要将类别列表存放于内存,而类别列表的元组数与训练集的元组数是相同的,这就一定程度上限制了可以处理的数据集的大小。 2)由于采用了预排序技术，而排序算法的复杂度本身并不是与记录个数成线性关系，因此，使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。（2）SPRINT算法 为了减少驻留于内存的数据量，SPRINT算法进一步改进了决策树算法的数据结构，去掉了在SLIQ中需要驻留于内存的类别列表，将它的类别列合并到每个 属性列表中。这样，在遍历每个属性列表寻找当前结点的最优分裂标准时，不必参照其他信息，将对结点的分裂表现在对属性列表的分裂，即将每个属性列表分成两 个，分别存放属于各个结点的记录。 SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进行分 裂时用哈希表记录下每个记录属于哪个孩子结点，若内存能够容纳下整个哈希表，其他属性列表的分裂只需参照该哈希表即可。由于哈希表的大小与训练集的大小成 正比，当训练集很大时，哈希表可能无法在内存容纳，此时分裂只能分批执行，这使得SPRINT算法的可伸缩性仍然不是很好。 （3）随机森林(Random Forest)（对C4.5,ID3改进，提高准确率） 随机森林是一个最近比较火的算法，它有很多的优点： 在数据集上表现良好 在当前的很多数据集上，相对其他算法有着很大的优势 它能够处理很高维度（feature很多）的数据，并且不用做特征选择 在训练完后，它能够给出哪些feature比较重要 在创建随机森林的时候，对generlization error使用的是无偏估计 训练速度快 在训练过程中，能够检测到feature间的互相影响 容易做成并行化方法 实现比较简单 随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。在建立每一棵决策树的过程中，有两点需要注意 – 采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m << M)。之后就 是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 – 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。 按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。随机森林的过程请参考Mahout的random forest。这个页面上写的比较清楚了，其中可能不明白的就是Information Gain，可以看看之前推荐过的Moore的页面。 Lecture 5 Classifier Assessment and Ensemble Methods 1、bagging bagging是一种用来提高学习算法准确度的方法，这种方法通过构造一个预测函数系列，然后以一定的方式将它们组合成一个预测函数。• 基本思想 1.给定一个弱学习算法,和一个训练集;2.单个弱学习算法准确率不高;3.将该学习算法使用多次,得出预测函数序列,进行投票;4.最后结果准确率将得到提高.Bagging要求“不稳定”（不稳定是指数据集的小的变动能够使得分类结果的显著的变动）的分类方法。比如：决策树，神经网络算法 2、Booting Boosting方法是一种用来提高弱分类算法准确度的方法,这种方法通过构造一个预测函数系列,然后以一定的方式将他们组合成一个预测函数。Boosting是一种提高任意给定学习算法准确度的方法。他是一种框架算法,主要是通过对样本集的操作获得样本子集,然后用弱分类算法在样本子集上训练生成一系列的基分类器。可以用来提高其他弱分类算法的识别率。 Bagging与Boosting的区别 二者的主要区别是取样方式不同。Bagging采用均匀取样，而Boosting根据错误率来取样，因此Boosting的分类精度要优于Bagging。Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boostlng的各轮训练集的选择与前面各轮的学习结果有关；Bagging的各个预测函数没有权重，而Boosting是有权重的；Bagging的各个预测函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于象神经网络这样极为耗时的学习方法。Bagging可通过并行训练节省大量时间开销。 bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化---Overfit。 Boosting思想的一种改进型AdaBoost方法在邮件过滤、文本分类方面都有很好的性能。 3、Adaboost(Adaptive Boosting) 算法简介 Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用adaboost分类器可以排除一些不必要的训练数据特征，并放在关键的训练数据上面。 算法分析 该算法其实是一个简单的弱分类算法提升过程，这个过程通过不断的训练，可以提高对数据的分类能力。整个过程如下所示： 1.先通过对N个训练样本的学习得到第一个弱分类器； 2.将分错的样本和其他的新数据一起构成一个新的N个的训练样本，通过对这个样本的学习得到第二个弱分类器 ； 3.将1和2都分错了的样本加上其他的新样本构成另一个新的N个的训练样本，通过对这个样本的学习得到第三个弱分类器； 4.最终经过提升的强分类器。即某个数据被分为哪一类要由各分类器权值决定。 算法优点： 高精度；简单，无需做特征筛选；可以使用各种方法构建子分类器，Adaboost算法提供的是框架；当使用简单分类器时，计算出的结果是可以理解的，而且弱分类器构造极其简单；不会过度拟合。 对于boosting算法，存在两个问题： 1.如何调整训练集，使得在训练集上训练的弱分类器得以进行； 2.如何将训练得到的各个弱分类器联合起来形成强分类器。针对以上两个问题，Adaboost算法进行了调整： 1.使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上； 2.将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。 与Boosting算法不同的是，Adaboost算法不需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，并且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，这样可以深入挖掘弱分类器算法的能力。 算法缺点： 训练时间过长，执行效果依赖于弱分类器的选择。对噪声数据和离群值敏感。 改进：限制样本权重的调整在各目标类内部进行 1、权值更新方法的改进 Allende等人提出了RADA算法，该算法是对原算法中误分类样本权值抑制的方法。算法最突出的贡献有三点：第一点是对的抑制，第二点，用当前层分类器来判断样本是否分类正 确，而非原算法中的当前弱分类器，第三点，增加 age变量记录误分类情况，并作了阈值限制，这里有效缓解了过拟合的问题。RADA 比传统 AdaBoost 算法更加稳定，有效解决了误分类样本权值偏高的问题。 2、训练方法的改进 Merler等人提出了AdaBoost的并行计算方法P-AdaBoost算法。其主要思想是，将AdaBoost训练过程分为两个阶段，第一阶段和原算法一样，经过多轮训练，获得一个较为可靠的样本分布ωi(s)，第二阶段采用并行方法提高训练效率，训练中不再对样本权值进行更新，而统一采用ωi(s)，最后输出为。 采用这种方法能大大减少训练成本，与原算法相比，多了S 轮的样本分布初始化工作，并且避免了差样本因多次分类而造成权值过大的问题。 3、多算法结合的改进 Yunlong提出了EAdaBoost算法，是AdaBoost结合k近邻算法的产物。AdaBoost算法具有高度拟合的特点，噪声会对训练产生很大的影响，Yunlong等人在AdaBoost算法的基础之上加入了kNN算法，对噪声样本进行了有效处理，提高了算法的精确度。EAdaBoost算法的主要过程如下： (a)准备训练样本，对样本权值进行初始化。(b)计算训练误差，并挑选最优的弱分类器。(c)更新样本权值。 (d)用 KNN 算法排除噪声样本，将权值设为 0。 该算法中有两个非常关键的问题，什么样的样本称为噪声样本和每次要处理多少个噪声样本的问题，原文中称之为 suspect sample，算法中取的是那种难于学习、让分类器出错过多的样本。 4、综合方法的改进 Rong Xiao等人提出了Boosting Chain算法，用链表的方式来组织分类器，算法先用boosting特征快速排除 大量非人脸窗口，再用boosting chain和SVM分类器进行再判别，实验效果相比FloatBoost还要略好。 Adaboosting Lecture 6 Introduction to Association Rule Mining（1）Apriori Algorithms ①算法思想：Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”。首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。 一、挖掘步骤： 1.依据支持度找出所有频繁项集（频度）2.依据置信度产生关联规则（强度）二、一些定义： 对于A->B ①支持度：P(A∩B)，既有A又有B的概率 ②置信度：P(B|A)，在A发生的事件中同时发生B的概率p(AB)/P(A)③如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。⑤候选集：通过向下合并得出的项集。 ⑥频繁集：支持度大于等于特定的最小支持度（Minimum Support/minsup）的项集。注意，频繁集的子集一定是频繁集。核心思想：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。简单的讲，1、发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集，重复步骤（1）~（5）直到不能发现更大的频集 2、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果 P（L）/P（S）≧minsup 则输出规则“SàL-S” 注：L-S表示在项集L中除去S子集的项集 ②优点： Apriori（先验的，推测的）算法应用广泛，可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。 ③缺点：此算法的的应用非常广泛，但是他在运算的过程中会产生大量的侯选集，而且在匹配的时候要进行整个数据库的扫描（重复扫描），因为要做支持度计数的统计操作，在小规模的数据上操作还不会有大问题，如果是大型的数据库上呢，他的效率还是有待提高的。④改进： 方法 一、Apriori优化：Fp-tree 算法 关键点：以树形的形式来展示、表达数据的形态；可以理解为水在不同河流分支的流动过程； 生成Fp-tree的几个点： 1.扫描原始项目集； 2.排列数据； 3.创建ROOT节点； 4.按照排列的数据进行元素的流动； 5.节点+1； 方法 二、Apriori优化：垂直数据分布 关键点：相当于把原始数据进行行转列的操作，并且记录每个元素的个数 Lecture 6有5种改进方法： 1.基于哈希的项集数：小于阈值的哈希桶数的k项集不是频繁的 2.缩减事务：在子频繁集中扫描时，不包含任何k项频繁集的事务是无用的 3.划分DB：DB中的任何频繁项集在部分DB中也一定是频繁的 4.采样：用一个小的支持阈值和方法挖掘给定数据的子集 5.动态规划项集数：只有当他们的所有子集预计为频繁时才添加一个新的候选项（1）基于hash的方法。基于哈希的算法仍是将所有所有数据放入内存的方法。只要在计算的过程中能够满足算法对内存的大量需求，针对C2候选项对过大，一些算法提出用来减少C2的大小。这里我们首先考虑PCY算法，这个算法使用了在Apriori算法的第一步里大量没使用的内存。接着，我们考虑Multistage（多步哈希）算法，这个算法使用PCY的技巧，但插入了额外的步骤来更多的减少C2的大小。类似的还有Multihash。 （2）基于划分的方法。Savasere等设计了一个基于划分(partition)的算法.这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。 （3）基于采样的方法。基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进的算法，Mannila等先考虑了这一点，他们认为采样是发现规则的一个有效途径。 （2）FP-tree Algorithms ①算法思想： 参考http://blog.csdn.net/sealyao/article/details/6460578 FP-tree 在不生成候选项的情况下，完成Apriori算法的功能。通过合并一些重复路径，实现了数据的压缩，从而使得将频繁项集加载到内存中成为可能。之后以树遍历的操作，替代了 Apriori 算法中最耗费时间的事务记录遍历，从而大大提高了运算效率。算法步骤如下： 1.扫描一遍数据库，删除频率小于最小支持度的项，并降序排列。并将每个事务中的项都要按照这个顺序进行排列。处理后的数据库记录为： 2.构建 FP-Tree，把每个事务中的数据项按降序依次插入到一棵以NULL为根结点的树中，同时在每个结点处记录该结点出现的支持度。如果插入时频繁项节点已经存在了，则把该频繁项节点支持度加1；如果该节点不存在，则创建支持度为1的节点，并把该节点链接到项头表中。 3.求出每个节点的条件模式基 4.为每个节点建立FP-Tree 5.递归 调用FP-growth(Tree，null)开始进行挖掘。伪代码如下： procedure FP_growth(Tree, a)if Tree 含单个路径P then{ for 路径P中结点的每个组合（记作b） 产生模式b U a，其支持度support = b 中结点的最小支持度； } else { for each a i 在Tree的头部(按照支持度由低到高顺序进行扫描){ 产生一个模式b = a i U a，其支持度support = a i-support； 构造b的条件模式基，然后构造b的条件FP-树Treeb； if Treeb 不为空 then 调用 FP_growth(Treeb, b)； } } FP-growth的执行过程： 1）在FP-growth递归调用的第一层，模式前后a=NULL，得到的其实就是频繁1-项集。2）对每一个频繁1-项，进行递归调用FP-growth()获得多元频繁项集。②优点： （ppt翻译） 1.算法结构拥有完整性： 1）没有破坏事务的长模式； 2）能保留频繁模式挖掘的完整信息。2.算法结构拥有紧凑性： 1）不相关的项被删除； 2）事务项按照频率降序排列，因为更频繁的项更可能被找到； 3）如果不计算链接和节点数目，存储空间小于原始数据库。 3.FP算法的效率比Apriori算法快一个数量级,效率快的原因有以下4个： 1）没有候选集，没有候选测试 2）有紧凑的数据结构 3）消除重复的数据库遍历 4）基础操作是计数和FP-Tree的建立 ③缺点： （参考http://www.xiexiebang.com/wiki/Covariance_matrix 我们认为bi代表B的第i行，那么由协方差矩阵 推知 <>表示向量的内积，也就是每一项的积之和。⑤ 计算协方差矩阵C的特征值和特征向量 若XA=aA,其中A为一列向量，a为一实数。那么a就被称为矩阵X的特征值，而A则是特征值a对应的特征向量。 顺便扯一下，在matlab里面，求解上述A以及a，使用eig函数。如[D,V] = eig(C)，那么D就是n个列特征向量，而V是对角矩阵，对角线上的元素就是特征值。⑥ 排序 将特征值按从大到小的顺序排列，并根据特征值调整特征向量的排布。 D'=sort(D);V'=sort(V); ⑦ 计算总能量并选取其中的较大值 若V'为C的对角阵，那么总能量为对角线所有特征值之和S。 由于在步骤⑥里面已对V进行了重新排序，所以当v'前几个特征值之和大于等于S的90%时，可以认为这几个特征值可以用来“表征”当前矩阵。 假设这样的特征值有L个。⑧ 计算基向量矩阵W 实际上，W是V矩阵的前L列，所以W的大小就是 MxL。⑨ 计算z-分数（这一步可选可不选） Z[i,j]=B[i,j]/sqrt(D[i,i])⑩ 计算降维后的新样本矩阵 W*表示W的转置的共轭矩阵，大小为 LxM , 而Z的大小为 MxN , 所以Y的大小为 LxN , 即降维为 N 个 L 维向量。 ②优点： 该算法可以消除数据间的冗余，以简化数据，提高计算效率。③缺点：缺乏主成分的物理解释，也就是缺乏有效的语义解释。 PCA假设数据各主特征是分布在正交方向上，如果在非正交方向上存在几个方差较大的方向，PCA的效果就大打折扣了。 PCA技术的一个很大的优点是，它是完全无参数限制的。在PCA的计算过程中完全不需要人为的设定参数或是根据任何经验模型对计算进行干预，最后的结果只与数据相关，与用户是独立的。 但是，这一点同时也可以看作是缺点。如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高 PCA也存在一些限制，例如它可以很好的解除线性相关，但是对于高阶相关性就没有办法了，对于存在高阶相关性的数据，可以考虑Kernel PCA，通过Kernel函数将非线性相关转为线性相关 ④改进： 龙源期刊网 http://.cn 一种改进的基于SNMP的网络拓扑发现算法 作者：王淅娜 喻建鹏 来源：《软件》2013年第03期 摘要：通过对网络拓扑发现算法的研究，提出了改进的SNMP的网络拓扑发现算法，并对改进算法的流程进行了描述。该算法具有交换机的发现完备性，并且能对哑设备进行处理。关键词：网络拓扑；拓扑发现；哑设备；SNMP 中图分类号：文献标识码：A DOI：10.3969/j.issn.1003-6970.2013.03.020第五篇：一种改进的基于SNMP的网络拓扑发现算法
点击咨询 