距离分类（共4篇）
距离分类 篇1
由于安全距离直接关系到人员、设备的安全,在防雷技术规范中要求尤为严格,不同的环境、目的、要求、途径、防护对象对防雷安全距离的要求各不相同,很容易引起混淆,判断错误,对防雷安全距离进行合理划分,既能在面对复杂情况和不同要求时迅速判定正确的安全距离,又能灵活运用规范,对规范中没有明确安全距离的情况能够综合考虑,做出合理判断。防雷安全距离根据危险源、防护对象和危害方式主要可以分为防击穿反击安全距离,防跨步电压安全距离、防雷击电磁脉冲耦合安全距离、屏蔽安全距离等4类。
1 防击穿反击安全距离
防击穿反击安全距离主要是为防止雷电流流经接闪器、引下线、接地装置或与之连接的金属物时产生的高电位对附近人员、设备、金属物或线路的闪络和反击,根据《建筑物防雷设计规范》GB50057-94(2000年版)[1](下称规范)的计算方法,安全距离Sal应大于电阻电压与电感电压与之相对应的击穿强度的比值之和。其计算公式如下:
式中:Ri为接地装置的冲击接地电阻(Ω);为雷电流陡度(kA/μs);I为雷电流幅值(kA);L0为引下线的单位长度电感(μH/m),取其等于1.5μH/m;ER为电阻电压降的空气击穿强度(k V/m),取其等于500kV/m;EL为电感电压降的空气击穿强度,取为(雷电流脉冲)波头时间(kV/m)。
带入相关数值即可得规范3.2.1条第五款一类防雷安全距离要求和计算公式,假设Ri=10Ω,则人与防雷装置的安全距离不应小于4 m,身高对安全距离的影响甚微。地中安全距离(Sel)的计算公式简化为:
该公式是用土壤的冲击击穿强度为500 kV/m(等于空气击穿强度)的平均值计算的结果,实际中土壤的冲击击穿强度因土质的不同而差异很大,主要分布在200~1 000 kV/m的大区间内,总体来说击穿强度与土壤电阻率成正比,因此在土壤电阻率很小的地方对地下安全距离的要求要远大于规范的要求值,假设Ri=10Ω,公式(1)在地中可简化为
当土壤的冲击击穿强度为200 kV/m时,Sel>10 m,当土壤的冲击击穿强度为1000 kV/m时,Sel>2 m,根据最低不得小于3 m的要求,只要达到3 m的安全距离即可,因此在具体的设计中要充分考虑土壤对地中安全距离的影响。
一类建筑物的直击雷防护是一个独立系统,必须与被保护建筑物或物体保持一定的安全距离,二、三类防雷建筑物可以通过等电位连接、共用接地有效地防止雷电反击,然而即便有等电位连接或采取共用接地的金属物之间同样可能产生反击,2条并行敷设的长金属物,在其端部通过等电位连接端子相连,当1条金属物上流过雷电流时,在两长金属距端子Lxm距离处的电位差为:
因此,当金属物或电气线路与防雷的接地装置有等电位连接时,还需要满足规范中公式3.3.8-3、3.4.8-3的距离要求。
2 防跨步电压安全距离
跨步电压是指雷电流入地点周围电位分布区行走的人,两脚间(80 cm)的电压,离落地点越远,电流越分散,地面的电势也越低,为了降低跨步电压而需要人与雷电流入地点之间保持一定的安全距离,即防跨步电压安全距离。
土壤干态下,10 kV变压器站或高压线意外漏电跨步电压安全距离为8 m,湿态下安全距离15 m,远大于规范中防直击雷的人工接地体距建筑物出入口或人行道不应小于3 m的安全距离,主要原因是变压器站或高压线意外漏电的故障点在地表面,电流主要通过地表面流散,使得地表面的跨步电压高,而接地电阻符合要求的防直击雷人工接地体:一是有良好的泄流能力,单位体积的平均电流密度小;二是根据规范要求,人工接地体埋深最少需要50 cm,使得地表面的跨步电压大大减小。
3 防雷击电磁脉冲耦合安全距离
雷电流产生的暂态脉冲磁场在导体回路中感应出过电压和过电流是通过阻性耦合、感性耦合和容性耦合实现的。其中,阻性耦合是指通过线路两端绝缘依次击穿来转移暂态高电位的一种耦合形式,阻性耦合的条件是有绝缘击穿,一般是由于等电位连接措施不当或等电位不系统而造成击穿反击。因此,防止阻性耦合,一是等电位连接措施得当,并在一个区域内等电位连接必须彻底全面;二是有良好的绝缘措施和安全距离,安全距离的计算可参考防击穿反击安全距离,但由于一个系统其线路与金属物、各线路之间很难保持足够的安全距离,因此防止阻性耦合以合理有效的等电位连接为主。感性耦合是指金属回路通过雷电流通道的感应场而感应过电压的耦合方式,容性耦合是指雷电流通道通过电容效应在附近线路或金属物上产生过电压的耦合方式,感性耦合和容性耦合一般同时存在,在不同的情况下影响有主次之分,防止感性耦合和容性耦合的方法主要是合理布线,并保持一定安全距离,以尽量减少由线缆自身形成的感应环路面积。《建筑物电子信息系统防雷技术规范》GB50343-2004[2]第5.3.3条对线路敷设距离的规定就是为了防止感性耦合和容性耦合。楼顶太阳能热水器与避雷针的安全距离在《建筑物防雷装置施工与验收规范》DB37/1228-2009[3]中仅要求50 cm,而楼顶天线与避雷针的安全距离却需要3 m,主要原因是2种情况安全距离的种类不相同,要求也就不同,太阳能热水器与避雷针之间只需要考虑防反击安全距离,在有等电位连接措施的情况下50 cm的安全距离已经足够,而天线与避雷针之间不仅要考虑防反击安全距离,还要考虑防雷击电磁脉冲的耦合干扰安全距离[4]。
4 屏蔽安全距离
屏蔽安全距离可分为屏蔽保护安全距离和屏蔽有效安全距离。屏蔽保护安全距离是指预计闪电通道(如直击雷防护装置)在格栅形屏蔽体以外附近的情况下,当格栅形屏蔽体内磁场强度要求不大于H1时,屏蔽体须与雷击通道间保持的安全距离Sal,Sal应按下式计算:
式中,i0为雷电流(A);SF为屏蔽系数(d B)。
屏蔽有效安全距离是指为了达到屏蔽的效果,需屏蔽的设备应与屏蔽格栅保持一定安全距离ds。雷击通道在屏蔽体以外时,屏蔽有效安全距离ds/1应按下式计算:
式中,W为格栅形屏蔽的网格宽(m)。
闪电直接击在格栅形屏蔽体上时,屏蔽有效安全距离ds/2应按下式计算:
很多情况下,防雷安全距离需要考虑以上2种或2种以上的安全距离,这就要求采取逐类分析,综合考虑,以4类安全距离的最大值作为安全距离的允许值。
5 结语
防雷安全距离的确定首先要分清类别,才能根据不同类别安全距离的要求和计算方法准确判定安全距离的允许值,涉及到2种或2种以上类别的应采取先分类分析,再综合考虑,多值选高的原则。运用防雷安全距离分类的方法,能够有效地避免误判,提高防雷安全距离判别的准确性和灵活性。
摘要：对防雷安全距离进行了分类,并对各类防雷安全距离的要求和计算方法进行了讨论,以期为防雷安全距离的判定提供参考。
关键词：防雷安全距离,击穿反击,跨步电压,雷击电磁脉冲,屏蔽
参考文献
[1]中华人民共和国机械工业部.GB50057-94建筑物防雷设计规范(2000年版)[S].北京:中国标准计划出版社,2001.
[2]中华人民共和国建设部.GB50343-2004建筑物电子信息系统防雷技术规范[S].北京:中国建筑工业出版社,2004.
[3]山东省质量技术监督局.DB37/1228-2009建筑物防雷装置施工与验收规范[S].济南:山东省技术监督信息研究所印刷部,2009.
[4]郑江,林苗.避雷带(短针)接闪点与防雷建筑的安全距离[J].建筑电气,2004,23(2):16-18.
距离分类 篇2
在许多分类学习中,无标记样本很容易获取,而有标记样本的获取则要难的多,因为给样本做标记通常要耗费较多的人力和时间。半监督分类的目的就在于当标记样本有限时利用大量的未标记样本来改善分类器的泛化性能,已经引起了越来越多研究者的重视[1]。
流形正则化(MR)[2]是一种颇为有效的基于流形假设[3]的半监督分类方法。流形假设是指输入空间中相互靠近的点应该有相似的分类函数值,反映了决策函数的局部平滑性。在该假设下,大量未标记样本的作用就是让数据空间变得更加稠密,从而有助于更加准确地刻画局部区域的特性,使得决策函数能够更好地进行数据拟合。流形正则化方法把邻接图的拉普拉斯矩阵[4]组织进流形正则项中,并引入到有监督分类算法中,使之既能够利用有标记样本也能够利用未标记样本,从而达到半监督分类的目的。
流形正则化方法中最有代表性的一种算法是Laplacian正则化最小二乘分类(LapRLS)[2],该算法已广泛应用于图像检索[5]、人脸识别[6]、目标识别[7]等众多领域,并取得了很好的效果。
研究表明,不同的半监督学习算法对学习性能的影响远比不上邻接图构造方法对学习性能的影响大[2]。如果邻接图的性质与数据内在规律(数据流形)相背离,无论采用何种学习算法,都难以获得满意的学习结果。因此,LapRLS算法成败的关键在于邻接图的构造是否合理。然而,当数据稀疏或存在噪音时,用欧式距离构造的邻接图可能不太准确,不能真实反映数据的内在流形结构,因此会导致LapRLS算法学习性能的下降。基于上述考虑,本文提出一种基于相对变换的RT-LapRLS算法(Relative Transformation based LapRLS)。
1 基于流形正则化的半监督分类方法La-pRLS及问题分析
1.1 LapRLS介绍
在经典的正则化分类方法中,如RLSC[8]和SVM[9],其目的在于找到一个再生核希尔伯特(RKHS)[9]空间中的光滑函数,使得该函数能够较好地把异类数据分开。任一个Mercer核[9]K:X×X→R,都有一个与之相对应的RKHSHK,该RKHS中的元素是函数f:X→R,函数的范式为‖f‖K。给定一组标记样本,则计算分类函数的标准计算公式可以表示为:
其中,V为某一种损失函数,比如RLSC中的平方损失函数[yif(xi)]2或SVM中的铰链损失函数max[0,1-yif(xi)],参数λ的作用是控制正则项的贡献度。根据表示定理,上述最小化问题的解可以写成如下形式:
式中K是样本空间中的Mercer核。由于K是事先确定的,所以分类函数的求解问题就转化为对系数αi的求解问题。
给定l个已标记样本和u个未标记样本,一般情况下u<<l,则流形正则化半监督分类方法可以表示为如下形式:
式中Wij是输入数据邻接图的边权值;F=[f(x1),…,f(xl+u)]T;L=D-W为邻接图的拉普拉斯矩阵,其中D为对角矩阵,其对角线上的元素为;γA和γ1是用来控制式中第2项和第3项贡献度的系数。式(3)的解可以表示为如下形式:
如果选择平方损失(yi-f(xi))2作为损失函数V,则目标函数可以表示如下:
然后通过求解凸可微目标函数,得到目标函数的分类函数,用于指导分类[9]。
1.2 问题分析
从式(5)可以看出,LapRLS的目标函数与拉普拉斯矩阵L有着直接的关系,而L又是由邻接矩阵W计算而来,所以邻接图构造的合理与否直接关系到LapRLS分类性能的好坏。通常,人们使用欧式距离来构造邻接图,但是在很多情况下,当数据稀疏或含有噪音时,这种方法构造的邻接图并不能反映数据的真实结构。基于这种考虑,本文提出利用相对变换距离[10,11,12]来构造数据的邻接图,以此提高LapRLS的准确率。
2 相对变换
相对变换是根据认知的相对性规律提出的一种数据处理方法,它将原始数据空间转换到相对空间,在相对空间中虽然仍采用原来的距离公式,但计算出的距离数据因为考虑了所有数据点的影响使噪声数据和孤立点远离正常点,起到抑制噪声的能力。在相对空间中测量数据的相似性或距离能够更符合人们的直觉。相对变换是非线性的放大变换,可提高数据之间的可区分性,从而提高数据分析的准确性。以原始数据空间中的每个数据点作为基向量来构造新的相对空间,这样任意点x到所有点的距离就构成该点在新空间中的坐标,这个过程称为相对变换[13]。
认知规律表明,人类的感知具有相对性,例如,在观察图1中的两个圆x和y时,通常会认为圆x比圆y要大,实际上它们是一样大的[14]。产生这种情况的原因在于,观察圆x时,与其周围的圆相比,显得很大,而观察圆y时,与其周围的圆相比,显得很小,因此这是一种相对比较的结果。
为模型化这种认知规律,构造相对变换空间,在相对变换空间中,原始样本点的坐标为该样本点到所有样本点的距离。即相对变换,因此Γ(xi)=(di1,di2,…,di|x|)=yi,其中X={x1,x2,…,x|X|},|X|为集合X的元素个数,dij=d(xi,xj)为xi与xj之间的欧式距离。
可以证明相对变换可以提高数据之间的可区分性[10,11,12]。以图2为例,从中可以看出,在原始数据空间中,d(x3,x1)=d(x3,x4),此时,x3无法判断是x1还是x4离自己更近,因此当选择x3的2-最近邻时,不能确定是{x2,x1}还是{x2,x4},对邻接图的构造产生了不利的影响。但是,在转换后的相对空间中,d(y3,y1)<d(y3,y4),很容易确定y1离y3更近,所以x3的2-最近邻是{x2,x1}。特别是这种情形也更符合人类的直觉,因此相对变换能够使在原始数据空间中不易区分的数据在相对空间中区分开来。
3 基于相对变换距离的LapRLS算法
在实际应用当中,当数据集较大时,相对变换空间的维数将会相当高,这将导致算法运行效率的下降以及存储空间的上升。为了避免这个问题,可以在原始样本相对较小的局部空间上进行相对变换,然后在这个局部相对空间中进行邻域选择。基于相对变换的LapRLS算法(RT-LapRLS)可以描述如下:
输入:标记样本,未标记样本,局部相对变换邻域r,最近邻接点个数k。
输出:分类函数f:X→R。
(1)对所有样本点,在其局部相对变换邻域r上做相对变换;
(2)对所有样本点,选择与其局部相对变换距离最小的k个点为最近邻点;
(3)利用相对变换最近邻点构造邻接图;
(4)在相对变换邻接图上利用LapRLS算法得到分类函数f。
算法通过这样的相对变换处理之后,进行非线性的放大变换,可提高数据之间的可区分性,从而提高数据分析的准确性,同时可以消除噪声数据和孤立点的影响。
4 实验及分析
在下面的实验中,将使用双月数据集,以及LIBSVM中使用的若干标准数据集来比较LapRLS和RT-LapRLS在半监督分类中的性能。
4.1 双月数据集
双月数据集如图3所示,该数据集包含2类共200个样本,表现为两个相互嵌套的月牙形,其中上半个月牙形和下半个月牙形分别属于不同的类别,如果每个月牙中只有一个样本是有标记的(图3中较大的圆点),那么这是一个典型的半监督分类问题。
为了验证相对变换最近邻对噪音的鲁棒性,本文给双月数据集加上不同强度的高斯白噪音,然后从加噪后的双月数据集中随机选择正负样本各1个,并分别利用LapRLS和RT-LapRLS学习分类函数(算法参数设置:r=14,k=7,LapRLS算法中所用的核函数为RBF核,即,令σ=0.05,γAl=0.1,),两种算法分类准确率如图4所示(100次随机正负样本选择情况下的平均值)。
从图4中可以看出,当信噪比为35dB时,两种算法的分类错误率都为0;当信噪比为30dB时,LapRLS算法的分类错误率上升到10%以上,但RT-LapRLS算法的分类错误率仍然维持在0,表明该算法对较小的噪音具有较强的鲁棒性;当信噪比继续减小,两种算法的分类错误率都有所上升,但是总体而言RT-LapRLS算法的分类错误率要小于LapRLS算法(信噪比为25dB的情况除外)。
4.2真实数据集
为了进一步研究RT-LapRLS算法的分类性能,我们将在LIBSVM中所使用的若干标准数据集(breast,ionosphere,heart,splice)上比较它与LapRLS算法的区别。这些数据集的属性如表1所示。由于这些数据集都是真实的,所以不可避免会受到噪音干扰,并且由于样本维数相对较高(如ionosphere,splice),而样本数相对较少,所以也存在数据稀疏问题。两种算法在各数据集上的分类准确率如图5所示(100次随机正负样本选择情况下的平均值),算法参数的设置见表2,如无特别说明,。
从图5中可以看出,在上述4个数据集上,RT-LapRLS算法在绝大多数最近邻接点个数k的情况下都取得了比LapRLS算法更好的分类效果。特别地,在breast和splice数据集上,在所有不同k取值的情况下,RT-LapRLS都要优于LapRLS。这说明,RT-LapRLS算法可以在一定程度上减少数据稀疏及噪音的影响,在真实数据集上也能取得较好的效果。
5 结语
本文介绍了一种基于相对变换的半监督分类算法RT-LapRLS,该算法利用相对变换距离选择样本的近邻点,实验表明相比于欧式距离,相对变换距离可以减少数据稀疏以及噪音对算法的影响,提高算法的鲁棒性。局部相对变换中有一个非常重要的参数即局部相对变换邻域r,这个参数的合适与否,也会影响到最终的结果,因此,这将是下一步需要继续研究的工作。另外,与LapRLS同理,RT-LapRLS不仅适合于二分类问题,也可以推广到多分类问题。
摘要：针对半监督分类过程中使用欧式距离选择样本的邻节点不能很好适应噪音或稀疏数据,导致算法分类精度下降问题,提出一种基于相对变换的RT-LapRLS算法。该方法利用相对变换距离对样本的近邻点进行选择,构造相对变换邻接图,在相对变换邻接图上构造流形正则项,最后用LapRLS算法得到分类函数。通过人工数据集和真实数据集上的实验验证了该算法的有效性,实验表明相比于欧式距离,相对变换距离可以减少数据稀疏以及噪音对算法的影响,提高算法的鲁棒性。
距离分类 篇3
分类是数据挖掘中的一个重要的研究课题,目前常用的分类方法有:决策树、贝叶斯分类、神经网络等,其中决策树分类方法以其理论清晰、易于理解,容易转换成分类规则等优点而被广泛地应用和研究。
决策树的基本算法是贪心算法,它采用自顶向下递归的方式来构造决策树,理想情况下,当所有树叶都是纯结点,即每个叶结点的实例都属于同一类时,决策树停止生长。但在实际应用过程中,常常无法达到这种理想结果,因为无法避免训练集中包含具有相同属性集,但属于不同类别的实例的情况。对于这种情况,由于没有剩余的属性可以用来进一步划分样本,所以决策树的这条分支无法继续生长下去产生纯的叶结点。目前针对这一情况,比较常用的处理方式就是使用多数表决方法来确定这种样本的分类,即将决策树中的该结点转换成叶结点并用样本中多数所在的类标记它[1]。多数表决的方式在一定程度上能决定样本所属的类别,但存在着两个问题,一是该方法对样本依赖过大,容易使决策树产生过拟合的现象,从而降低决策树的分类效果。二是如果样本空间中每个类别的实例数相等,不存在多数类别,将无法使用多数表决来判定样本的类别。针对这种状况,提出一种基于信息增益并结合最小距离分类的决策树改进算法。该算法首先利用信息增益进行属性空间的约简,然后针对决策树在构造过程中训练集中包含具有相同属性集,但属于不同类别的样本,利用基于信息增益的加权欧式距离公式计算这类样本的中心点与决策树中所有纯叶结点的样本中心点之间的距离,找到与其中心点距离最近的那个叶结点,并用最近的叶结点的类别来对该叶结点进行标记。
1 信息增益与ID3算法
在信息论中,信息量是指从N个相等可能事件中选出一个事件所需要的信息度量,事件ai的信息量可用-log2p(ai)来度量,其中p(ai)表示事件ai发生的概率[2]。熵的定义为[1]:,其中P1,P21…,Ps是给定概率,且,表达的是平均信息度量。
信息增益定义为
式(1)中,H(D)是原始数据集的熵,P(Di)子集Di所占整个数据集的比例,(Di)H)(Di)是分裂后所有子集的熵的加权和。式(1)表达的是样本分类前后熵值的变化差值,这一差值表明了属性对分类所提供的信息量大小。因此,可以用信息增益来量化属性与给定的类或概念的相关性,信息增益越大表明该属性与分类任务的相关性越大。
ID3算法是经典的决策树算法,其核心是以信息增益为衡量标准,它通过计算每一个属性的信息增益,并选取具有最高信息增益的属性作为分裂属性来构建决策树,这种方法将产生一棵简单的,但不必是最简单的决策树。
ID3算法思想如下:[1]
1)树以训练集中信息增益最大的属性A开始;
2)如果样本都属于同一类,则该节点成为树叶,并用该类标记;
3)否则,对属性A的每个有效值,创建一个分枝,并据此划分样本;
4)使用相同的方式,递归地产生每个划分样本上的决策树。
递归划分步骤仅当下列条件之一成立时停止:
a)给定节点的所有样本属于同一类;
b)没有剩余属性可以用来进一步划分样本,此时将该节点转换成树叶,并用多数表决法,用样本集中的多数所在的类标记它;
c)对有属性而训练集中无样本的分枝也采用多数表决法,来决定其类别。
2 基于信息增益的最小距离分类器
最小距离分类器是一种基于向量空间模型的简单而有效的分类器,其基本思想[3]是根据训练集按照算术平均生成一个代表该类的中心向量Uk(k=1,2,…,m;m是类的个数),对于每一个待分类的数据元组X,计算其与Uk之间的距离d(Uk,X),最后判定X属于与之距离最近的类。这里X=[x1,x2,…,xn,c],Uk=[μk1,μk2,…,μkn,c],c表示类别,c∈{c1,c2,…,cm}。
在实际应用中,由于各属性在分类过程中所起的作用大小不同,因此在计算最小距离时,一般采用加权的距离公式。
在式(2)中,权值wi的大小说明该属性对分类的影响的大小。
采用基于加权距离公式的最小距离分类器进行分类时,合理地对权值wi大小进行设置是至关重要的。为此,本文提出一种新型的基于信息增益的改进型最小距离分类器。该分类器基于式(2)中的权值wi用属性的信息增益值来设置。具体做法是:
1)计算属性空间中各属性的信息增益得到属性信息增益集AttrilnforGainSet;
2)将AttrilnfoGainSet中信息增益值归一化处理到[0,1]区间,并将处理的结果作为权值赋值给式(2)中相应的属性Xi的权值wi;
3)对参与分类的各属性的取值进行规范化处理,将属性值规范化在[0,1];
4)调用式(2)进行分类。
3 基于信息增益和最小距离分类的决策树改进算法
ID3算法简单、易实现,因此被广泛使用,但对于训练集中存在相同属性集,但属于不同类别的实例的情况仅简单地采用多数表决法来决定其类别,降低了决策树分类的精度。此外,ID3算法产生的决策树其结构往往过于庞大、复杂,后期的剪枝工作量比较大,这就影响了算法效率。基于信息增益和最小距离分类的决策树改进算法,在ID3算法的基础上,通过结合基于信息增益的属性约简和最小距离分类方法来改进ID3算法的性能,其中基于信息增益的属性约简[4]是根据属性增益的大小以及属性间的相关系数的大小来判断属性对分类的贡献大小,以及属性间的关联程度,从而删除对分类不相关、弱相关的属性以及冗余属性达到约简属性空间的效果。
3.1 算法描述
1)对属性空间作基于信息增益的属性约简,得到最优约简的属性集OptiAttriSet和对应的信息增益集OptiAttriGainSet。
2)用信息增益作为启发式信息来构造ID3决策树,但在构造过程中对于具有相同属性集,但属于不同类别的实例,暂时用null标识它的类别。
3)对决策树中所有类别为null的叶结点,调用基于信息增益的最小距离分类器对它们进行重新分类。
4)计算决策树所有叶结点Nk所在的子样本空间的中心结点Uk。具体操作如下:若属性i是数值类属性,中心结点Uk的属性值μki的值为样本空间中所有样本i属性的算术平均值,若属性i是标称型或字符串型属性,中心结点Uk的属性值μki取该类的所有数据元组中属性i的最频繁值[5]。
5)将决策树中每一个类别为null的叶结点Nm的中心结点Umi作为待分类样本,用基于信息增益的最小距离分类器来计算Umi与其他类别为非null的叶结点Nn的中心结点Uni之间的距离d(Umi,ni),i∈(i,…,k),并将叶结点Nm的类重新标识U为与其中心点Um距离最近的Uni所属的叶结点Nn的类标号C。
3.2 改进ID3算法实例
实例主要是针对训练集中存在相同属性集,但属于不同类别的实例的情况,说明改进后的ID3算法的分类效果优于传统ID3算法的分类效果。实例是在一个简单的气象数据集(表1所示)进行的,该数据集描述了气象因素对是否打网球这一行动的影响,表1中的weather、temperature、humidity、windy、tennis是进行了属性约简后保留的属性,其中tennis是类别属性,yes表示打网球,no表示不打网球。ID属性在这里仅用来表达记录号,不参与分类。针对表1中的数据用传统ID3算法产生的决策树如图1所示。
从图1中可以看出树叶1—6都是纯叶结点,树叶7不是纯叶结点,训练集中实例8,9属于树叶7,而实例8和实例9具有相同属性集,但属于不同类别,所以按照传统的ID3算法应该采用多数表决来决定其分类,但在该子集中不存在多数类,故无法用多数表决的方法来判定树叶7所属的类别。在改进的ID3算法中将采用基于信息增益的最小距离分类来决定树叶7的类别。
1)计算属性的信息增益并将信息增益归一化处理后结果为:InfoGain (climate)=0.56,InfoGain(temperature)=0.11,InfoGain (humidity)=0.31,InfoGain (wind)=0.02;
2)计算,树叶7与其他树叶之间的距离
a)首先计算树叶7与树叶4,5,6之间的距离,对于字符串型属性,中心结点的属性值取该类的所有数据元组中属性的最频繁值[6],因此:
树叶7的中心结点K的各属性值为:weather=rain,temperature=cool,humidity=normal,windy=yes,tennis=null;
树叶6的中心结点N6为(weather=rain,temperature=hot,humidity=high,windy=no,tennis=no);
树叶5的中心结点N5为(weather=rain,temperature=warm,humidity=high,windy=no,tennis=yes)
树叶4的中心结点N4为(weather=rain,temperature=warm,humidity=high,windy=yes,tennis=no)
调用基于信息增益的最小距离公式,计算结点K与N4-N6的距离。计算时对于字符性数据,如果两个属性值相等,则差值为0,如果不等则差值为1。点K与N4-N6的距离为D(K,N6)=0.663,D(K,N5)=0.663,D(K,N4)=0.648。
b)计算树叶7与树叶1,2,3之间的距离
树叶1,2,3的中心点N1,N2,N3的weather属性值分别为:sunny,cloudy,与树叶7的中点K的weather属性值rain不同,所以N1-N3与K的距离应该大于等于(InfoGain (weather)×1×1) 1/2=(0.56×1×1)1/2=0.748。
通过比较可知与K最近的应该是N4,因此树叶7的类别应该与树叶4一样为no。
3.3 基于信息增益和最小距离分类的决策树改进算法的性能测试
本实验在WEKA平台[7]上针对UCI数据库中的mushroom数据集进行,该数据集包含23个属性,8124条记录,类别数为2。实验时需要修改实例,使数据集中具有相同的属性取值,但属于不同的类别的记录。实验主要用来测试训练集中具有相同的属性取值,但属于不同的类别的记录数量不同的情况下传统ID3决策树和改进型ID3决策树的分类的性能。具体实验信息如表2所示。
从表2可以看出从分类效果上来看,改进型ID3决策树的分类正确率优于传统的ID3决策树分类,且随着数据集中具有相同的属性取值,但属于不同的类别记录数的增多,这种优势更明显。从算法的执行速度上来看,传统的ID3决策树的速度略高于基于信息增益和最小距离分类的决策树。这主要是因为与传统的ID3算法相比,改进型ID3决策树要多两个步骤:一是在构造决策树前对属性空间进行了基于信息增益的属性约简需要花费一些时间,二是对属于不同类别的实例要调用基于信息增益的最小距离分类器来决策其类别比用多数表决决策法判断分类花费的时间也要多一点,但改进后的ID3算法是在约简后的属性空间中构造决策树的,因此构造速度会更快,产生的决策树也会更小、更简单,同时也减少了后期为了避免过拟合而对决策树进行剪枝的时间开销,所以改进型ID3决策树与传统ID3相比速度相差不大。
4 总结
决策树是一种基于知识表示的树,它具有执行效率高,生成的规则容易理解等优点而被广泛应用,针对决策树的代表ID3算法进行改进。首先应用基于信息增益的属性约简的方法对属性空间进行约简,以加快决策树的生长、降低剪枝的工作量,并得到结构更好的决策树,接着对于训练集中具有相同的属性取值,但属于不同的类别的记录情况,不再采用多数表决法决定类别,而是采用最小距离分类方法来确定其类别,实验表明基于信息增益和最小距离分类的决策树提高了分类的准确率。
参考文献
[1] Han jiawei,Kamber M著.范明,孟小峰,等译.数据挖掘概念与技术.北京:机械工业出版社,2001:188-189
[2]魏存章,豆增发.一种基于信息增益的K-NN改进算法.计算机工程与应用,2007;43(19):188-191
[3] Jainak,Robert Pwduin,MAO J.statistical pattern recognition;a review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000;22(1):4—37
[4] Duan Wei,Lu Xiang-yang.Weighted Naive Bayesian classifier model based on information gain.Changsha,China;Intelligent System Design and Engineering Application,2010;(2);819—822
[5]任靖,李春平.最小距离分类器的改进算法——加权最小距离??分类器.计算机应用,2007;25(5):992-994
[6]邱潇钰,张化祥.基于核的最小距离分类法的参数选择方法.计算机工程,2008;34(5):188-190
[7]陈慧萍,林莉莉,王建东,等.WEKA数据挖掘平台及其二次开发.计算机工程与应用,2008;44(19):76-79
距离分类 篇4
随着大数据时代的到来,已有的数据挖掘技术面临一系列新的挑战。大数据具有数据体量巨大,数据增量快,数据结构复杂等特点[1],使得对大数据的挖掘存在许多困难。
分类是数据挖掘的重要内容之一。目前已有许多分类算法,最小距离分类算法就是其中的一种。该算法拥有计算简单,概念明晰,易于理解,速度较快等优点。该文提出了一种基于最小距离增量分类算法,与文献[14]提出的算法相比,在分类精度大致相同的情况下,算法的复杂度和存储开销均有不同程度的下降,适合于对大数据进行分类。
2相关研究的工作
目前,增量分类算法有很多。如基于RBF网络的增量分类算法[4],基于支持向量机的增量分类算法[5],基于最近邻方法的增量分类算法,基于决策树的增量分类算法[6,7,8,9]以及基于贝叶斯网络的增量分类算法[10]。这些算法主要问题是复杂度高,要求的存储空间大。而基于距离的增量分类算法则具有设计相对简单,复杂度低,存储开销小等特点,所以有很多基于距离的增量分类算法被提出。例如R.Marin等人提出的距离增量分类算法[11],该算法首次实现了基于距离的增量分类;K,yamauchi提出了一种消除训练样本间相互干扰的方法[12],它利用已训练样本进行分类训练来消除样本之间的干扰;Zhao等人提出了增量等距算法[13],通过映射新的数据点调整训练结果,用增量的方法强化分类结果,最后采用类似滑动窗口的方式约束数据的增加;桑农等提出了一种保留样本的增量分类方法(ILAMM)[14],使用马氏距离,解决了类域大小不一致影响分类正确率的问题。
基于距离的增量分类算法,不仅要能准确分类增量样本,而且要保持对已训练样本的分类性能[15,16]。ILAMM算法更加适合于训练样本和增量样本数量级接近的增量分类情况,在训练样本远大于增量样本的情况下,分类效率比较低。该文在ILAMM算法的基础上,提出了基于最小距离的多中心向量的增量分类算法(ICMCVM)。该算法通过将空间区域划分为若干区域,提高了训练样本比增量样本大很多的情况下的增量分类效率,因为算法减少了代表样本的选取数量,降低了算法的存储开销,通过设置多中心向量,实现了增量分类。
3最小距离分类算法
最小距离分类算法的基本思想[17]:设有m个类: C1,C2,...,Cm;根据训练样本实例的类别,分别使用算术平均的计算方法,计算出各个类别的中心向量Uk(k=1,2,3...m;m是样本类别数),对于每一个待分类的实例X,计算出实例X与中心向量Uk的距离d,从而找出距离最近的中心向量Uk,将实例X分给中心向量Uk代表的类别Ck,其中X =[x1,x2,...,xn,C] , UK=[Lk1,Lk2,...,Lkn,C] ,C代表所属类别,Lkn是算术平均计算求得的各属性均值。
4基于最小距离的多中心向量的增量分类算法
ICMCVM算法分两个阶段,第一个阶段通过区域划分方法,将空间划分为稳定空间区域、边界重叠区域、未知空间区域。第二个阶段,通过多中心向量,实现增量分类。
4.1区域划分算法
区域划分算法首先按照类别K-均值聚类训练样本,然后在不同类别的子集之间进行类间调整,划分空间为若干区域。
在描述详细步骤前,先描述一个量化样本属性为数值类型的方法:量化方法是给定一个数据集D[n][m],数据有n行m列,for i=0 to m,若第i列属性值为数值类型,则求出该列的最大值MAX和最小值MIN,for l=0 to n,归一化属性值E =（E - MIN）/（MAX - MIN）;若第i列属性值为字符串或者标量类型,for l=0 to n,将属性值按出现顺序,依次赋值为x(x为1,2,3....N,N为不同属性值的个数),归一化属性值E =x/NUM,根据该方法,将训练样本中字符串类型和标量类型属性量化为数值类型。
基于最小距离的多中心向量的分类算法:
步骤1数据集预处理,量化样本属性为数值类型。
步骤2根据先验知识,将训练样本F,按属性类,k-均值聚类。
步骤3聚类后的子集存在空间重叠,需要调整,调整方法如下:
Step1设一个集合
Step2对于任意两个不属于同一类的子集A和B,存在实例集属于子集A,且每一个实例X有|X,A|>|X,B|(|X,A|表示实例X到到子集A的马氏距离,马氏距离公式为 ,其中,d是子集Ω与实例x的距离,u是子集Ω的中心向量,V是该子集的协方差),或者存在实例集属于B,且实例集中的每一个实例X有|X,A|<|X,B|,若实例集的实例数大于设置的参数阀值Θ,则将A和B集合加入集合U。
Step3如果,算法结束;否则转Step4。
Step4将U集合中的子集按属性类分别k均值聚类分为2个子集,若正确分类了实例集则保留两个新子集,置集合U为空,转至Step2,若没有分类正确,跳转至step4。
Step5若类域空间中的子集Ωk∈CC,该子集所有样本的(其中n是子集的实例数,k子集数,c是样本类别数)都属于类别CC,则将该子集空间称为稳定空间域;若类域空间中的子集Ωk∈CC,该子集所有样本的属于不同的类别,则将该子集的空间称为边界重叠区域,样本空间中,除了稳定空间区域和边界重叠区域,剩下的所有空间,称为未知空间区域。
4.2不同区域样本的不同处理
因为落入不同区域的样本的价值是不等价的[18],所以处理方法也应不同。
边界重叠区域的处理方法:该方法通过统计落入各个边界重叠区域内,每一个类别的实例数,用其中最大样本实例数的类别代表该边界重叠区域的类别,这样,当有一个未知类,落入边界重叠区域中,可以快速的将该样本分类给所代表的类别,无论样本增加多少,总是用统计中落入各个边界重叠区域的样本实例数最多的类别代表该区域类别。该方法会降低了分类的正确率,但是在边界不清的区域,正确分类本身就是一件困难的事情,所以该方法依然可以获得很好的效果。
稳定空间区域的处理方法:在训练样本空间足够大的情况下,落入稳定空间区域的样本,可以直接分类给该稳定子集所代表的类域。
未知空间区域的处理方法:对于未知空间区域,该文提出了一种多中心向量的增量处理方法,用来分类落入未知空间区域的样本。
4.3增量分类的算法
定义1:在添加新中心向量时,该中心向量在现有数据集空间上的适应度,称为中心向量适应度。中心向量适应度计算方法:中心向量p为类别C的中心向量,分类器正确分类给中心向量p的代表样本集合为r1,实例个数为k1,错误分类给中心向量p的代表样本集合为r2,实例个数为k2,分类器正确分类给中心向量p的训练样本集合为w1,实例个数为k3,错误分类给中心向量p的训练样本集 合为w2,实例个数 为k4,已训练样 本总数为N,代表样本 个数为n, 中心向量 适应度计 算公式是
下面详细描述ICMCVM算法,算法有5个步骤:
步骤1按4.1量化方法,量化增量样本为数值类型。
步骤2用4.1节生成的分类器分类增量样本,增量样本将落入边界重叠区域、稳定空间区域、边界重叠区域。稳定空间区域和边界重叠区域的增量样本直接分类给区域代表类,而落入未知空间区域的的样本要进一步处理。
步骤3对于落入未知区域的样本集合S,若不是第一次处理,跳转至步骤4,若是第一次处理,则将集合S按照属性类,根据最小距离算法的中心向量计算公式,使用欧式距离作为度量方式(欧式距离公式为
其中,Uk为类Ck的中心向量,X为类Ck的实例),求出中心向量集合P,最小距离算法分类集合S,生成错误分类集合α,随机以集合α中的实例x为新增加的中心向量,再次分类集合S,若新中心向量的适应度Γ>0,则实例x为新的中心向量,加入集合P,从集合S中去除正确分类的所有实例,重复该步骤,直到找出所有的新中心向量。
步骤4判断落入未知区域空间的实例总数SUM是否达到预设的样本总数阀值Φ,若达到,落入未知空间区域的实例总数SUM=0,按ILAMM算法增量样本的分类方法,增量分类代表样本集合J,重新区域划分,结果加入分类器。若没有达到阀值Φ,重新计算落入未知空间区域的实例总数SUM,在已有的中心向量集合P基础上,分类集合L,得到错误分类集合β,将代表样本集合加入新训练集合,随机以集合β中的实例x作为新增加的中心向量,再次分类新训练样本,若实例x的中心向量适应Γ>0,则实例x作为新的中心向量加入集合P,重复该步骤,直到找出所有的新中心向量。
步骤5经过上述步骤后,落入边界重叠区域,落入稳定空间区域,落入未知空间区域的样本都可以分类,按ILAMM算法的代表样本获取方法,重新从落入未知空间区域的样本,选取代表样本,最后保留代表样本。
5实验模拟
为了验证ICMCVM算法的有效性,该文实验比较了ICMCVM算法与ILAMM算法的时间、空间开销和算法的分类精度。实验使用C++语言在编译环境VS2010下编写,在CPU为IntelT6500,2GB内存的PC机上运行。
数据1使用UCI网站上的Adult数据集,数据集拥有实例个数为48842个,有两种类别,分别为收入大于50k和收入小于等于50k,每个实例拥有14个属性,包括年龄、工种、教育、每周工作时间、种性别等,属性的数据类型有两种,连续型和离散型。实验1首先去除了Adult数据集中不完整属性值的数据实例18680个,然后将剩下的30162个数据实例分为已训练样本和增量训练样本2个部分,已训练样本的选取方法是,通过对数据集,采用未增量的分类算法分类,选取能够正确分类的20162样本为已训练样本,余下的实例作为增量训练样本,用来验证算法的增量效果。
实验1中参数的设置,k-均值聚类的簇数为5,子集分裂阀值Θ=100,样本总数阀值Φ足够大。因为中心向量的个数比较少,可以不计入。测试样本实例数为2000个。算法受k-均值聚类随机性的影响,表格中的数据为多次实验所得数据的平均值。以下表1,表2,表3列出了实验1的实验结果。
表1和表2数据表明,ICMCVM和ILAMM算法增量分类后,分类正确率提高了25%左右,表明ICMCVM和ILAMM算法具备了增量分类的性能,增量后,ICMCVM和ILAMM算法的分类正确率基本相当。分析表2的存储样本数的数据,因为ICMCVM算法减少了从稳定的数据空间和边界重叠区域选取的代表样本数量,所以选取的代表样本数量较少,ICMCVM算法存储的样本实例数要比ILAMM少2000左右。从表中存储开销比可以看出,在ICMCVM算法在最坏的情况下,随着增量样本的增多,存储开销比逐渐增长,但是ICMCVM存储开销将始终比ILAMM算法的存储开销小。
表3数据表明,ICMCVM和ILAMM算法时间开销基本相当,经过多次增量分类后,两种算法分类正确率相近。
实验模拟结果表明:ICMCVM算法与ILAMM算法相比,存储开销较小,分类正确率相当,时间开销相近。
6结束语
本文提出了一种基于最小距离的增量分类算法ICMCVM,该算法划分区域分治分类样本,设置多中心向量,实现了增量分类,与ILAMM相比,减少了代表样本的选取数量,降低了存储开销。
ICMCVM算法面对数据空间有较多边界重叠区时,分类正确率会下降,因此提高数据的边界重叠区的分类正确率将是一个研究方向,同时,标量和字符串属性的量化方法,也是进一步可以研究的内容。
摘要：分类是数据挖掘的一项重要研究内容。在分析了现有分类方法后,提出了基于最小距离的多中心向量的增量分类算法。该方法首先按照属性类聚类训练样本,通过类间调整,消除类域空间重叠。针对增量分类,提出了多中心向量的分类算法,通过空间区域划分的方法,减少增量分类选取的代表样本数量。实验结果表明,与文献[14]提出的增量分类算法相比,分类精度近似相同,但所需时间复杂度和存储空间则有不同程度的下降,这对大数据的处理是具有重要意义的。