距离向量算法（精选7篇）
距离向量算法 篇1
0 引言
由于电网故障或设备检修经常会造成一些负荷的停电,其中包括一些重要的负荷,如何为停电的负荷搜索其他可用的供电恢复路径,以快速恢复供电是调度人员工作中经常遇到的问题,即供电路径搜索的问题[1]。因此,有必要针对失电负荷恢复供电路径搜索算法进行研究。
与失电负荷恢复供电研究相关的是配电网故障恢复控制,目前有很多关于配电网故障恢复研究的文献。文献[2]指出地区电网的故障恢复问题是一个多目标、多约束、复杂的优化问题。目前研究故障恢复的方法较多,人工智能技术得到了广泛关注,如专家系统[3,4]、遗传算法[5,6,7,8]、蚁群算法[9]、Petri网[10]、多代理系统[11,12]和差分进化算法[13,14]等。然而上述方法针对特定网络结构分析各有其特点,但不能有效适应地区电网故障在线快速恢复,难以为调度员提供实时、合理的故障恢复控制策略。文献[1]提出电气岛划分的概念,通过拓扑分析将电网分解为若干电气岛,利用“电气岛+边界条件”的概念搜索失电孤岛的供电路径,基于树搜索法中的宽度优先搜索法进行分层搜索。但对于环形网络,这种搜索方法容易漏掉潜在的供电路径;而且由于是从失电孤岛出发去搜索带电岛,这样搜索到的供电路径顺序不符合调度操作规程,即送电时应从电源侧逐级向负荷侧闭合开关。为解决这一问题,文献[1]对电气岛增加了两个新的属性,来记录由带电岛返回失电孤岛的路径,但这样处理增加了内存开销,不利于程序处理的简洁与快速。电气岛划分的概念可以避免在为失电孤岛寻找电源时大量搜索节点链接支路,而是采用直接搜索对侧电气岛的带电性质,因而大大提高了搜索速度。为此针对失电孤岛供电路径搜索算法的研究还有进一步的发展空间。
本文在文献[1]的基础上,受因特网路由选择协议的启发,利用电气岛之间的边界联系,提出一种基于距离向量的供电路径搜索算法。通过建立各个电气岛之间的路由表,将失电孤岛的供电路径搜索问题转换为路由表更新问题,利用各个电气岛最终的路由表项目便可以直观、快速地找到失电孤岛的最短供电路径,并且供电路径的顺序满足调度操作规程。
1 距离向量算法
在信息通信领域,路由器作为网络拓扑中的一种中间结点,在推动计算机网络互联方面扮演了重要角色。路由选择算法分为交互协议和本地计算,其本质是在交互协议的基础上,通过选择适当的标准和有效的选择策略进行本地计算,最终获得最优路由。路由选择定义为把消息从信息源经过网络传送到目的地的行为,主要进行协议交互和本地计算两个基本动作。其中协议交互主要完成网络中距离向量、路径向量和链路状态的查找和传送;本地计算则是根据协议交互获得的距离向量、路径向量和链路状态进行路由表的更新处理,确定数据发送的最优路径[15]。
路由选择协议中的内部网关协议RIP(routing information protocol)是一种基于距离向量的分布式路由选择协议,根据RIP,网络中每一个路由器都要维护从它本身到达其他任意一个目标网络的路由信息。定义路由器到达直接相连的网络的距离为1;定义路由器到达非直接相连的网络的距离为路径上所经过的路由器数加1。RIP中的“距离”也被称为“跳数”(hop count),把信息的传递比作在路由器之间的跳跃,规定每经过一个路由器,跳数就加1。这里的“距离”实际上指的是“最短距离”。RIP中将从源头到达目的地所经过的路由器数目最少的路由定义为最优路由,即跳数最少。
更新路由表时,每个路由器只与相邻的路由器进行协议交互,也就是交换各自的路由信息,交换的路由信息是本路由器当前所知道的所有路由信息[16]。初始化的路由器仅仅知道与其直接相连的网络的距离,将这个距离定义为1。在此之后,每一个路由器只和数目有限的相邻的路由器进行协议交互,并更新各自的路由表项目。经过若干次的更新之后,网络中的每一个路由器最终都会知道从它本身到达本网络中任意一个网络的最短距离和下一跳的路由器地址。RIP的收敛过程较快,即在自治系统中所有结点都得到正确的路由选择信息的过程。RIP令互联网中的所有路由器都与自己的相邻路由器不断交换路由信息,并不断更新其路由表,使得从每一个路由器到每一个目的网络的路由都是最短的。虽然所有的路由器最终都拥有了整个自治系统的全局路由信息,但由于每一个路由器的位置不同,它们的路由表自然也不同。本文按照该协议的思路,提出一种基于距离向量的失电孤岛搜索算法。
2 供电路径搜索
根据文献[17-20]中的拓扑分析方法,相互连接的无阻抗设备汇聚成一个等值节点,通过等值节点相连的有阻抗设备汇聚成一个电气岛。电气岛内部设备彼此连通,即内部各处带电状态一致;电气岛之间彼此不连通。当系统发生负荷失电时,利用拓扑分析程序,将电网划分为若干彼此不连通的电气岛,通过判断岛内设备带电状态,将全部电气岛分为带电岛和不带电岛两大类。根据电气岛划分规则可见,带电岛内部有电源,可作为失电负荷恢复供电的电源。对于不带电岛,有3 种情况:第1 种是故障岛,这种电气岛由于岛内设备故障或检修致使设备不可用;第2种是无源岛,这种电气岛内既无电源又无失电负荷,但其岛内设备正常,可以通过投入运行来为失电负荷供电,如备用设备可划归并入这种电气岛;第3种是失电孤岛,这种岛内无电源,但有失电负荷,需要为其恢复供电。某地区电网经过拓扑分析之后形成的电气岛之间的联系图如图1所示。
定义电气岛边界为不同电气岛之间呈断开状态的无阻抗设备,相当于电气岛间的备用通路,边界一经操作合上,两电气岛即合并形成同一个电气岛。需要说明的是,并不是呈断开状态的无阻抗设备就是边界,只有两端是不同电气岛的无阻抗设备才是边界。
为了说明本文的搜索算法,将故障岛之外的每个电气岛看成一个路由器,各自有一张初始路由表,表示该电气岛与相邻电气岛之间的连接关系,然后根据距离向量算法进行路由表更新,最终获得所有电气岛的全网路由表,进而从中选出失电孤岛的供电路径。路由表结构分为目标岛、距离和路径,以孤岛1的路由表为例,路由表信息如表1所示。
路由表中第1行表示:失电孤岛1 至带电岛2距离为1的路径A;路由表中第2 行表示,失电孤岛1至无源岛3距离为1的路径C。
2.1 初始路由表形成规则
电气岛的初始路由表表示该电气岛与相邻电气岛之间的联系,初始路由表的形成可以根据电气岛边界来确定。依次处理电气岛的边界,按照路由表的结构形成初始路由表的项目。在处理边界的过程中需要注意,若一个电气岛仅和故障岛相连,或者一个电气岛所有的边界只和故障岛相连,则该岛不会在恢复路径中体现,于是将该岛排除在更新列表之外,更新列表中的所有电气岛均要进行下一步路由表更新处理。将所有除故障岛以外的电气岛处理完毕后,各个电气岛的初始路由表也就最终形成。
初始路由表的具体形成流程如图2所示。
2.2 路由表更新规则
路由表的更新处理是为了获取每个电气岛到网络中任意一个电气岛的最短路径,当然从中可以获取失电孤岛到达各个带电岛的最短路径,即为失电孤岛搜索若干条恢复供电的最短路径。更新过程中,每一个电气岛只和数目有限的相邻电气岛交换并更新路由信息。当电气岛获取到相邻电气岛的路由表信息后,根据距离向量算法,在原来的距离上加1,路径之前加上相应的边界。若本电气岛的路由表中没有目标岛,会将新的目标岛加入本路由表项目中;若目标岛在本岛路由表中,则判断距离是否更短,如果比本岛路由表项目中的距离更短,则更新距离和相应的路径,如果相等则把该条路由信息加入路由表,原路由信息不变,否则返回处理下一条路由信息。经过若干次更新后,所有的电气岛最终都会知道到达本电网系统中任何一个电气岛的最短距离和相应的最短路径。
路由表更新的具体流程如图3所示。所有电气岛路由表更新结束后,失电孤岛的路径就可以直接从孤岛路由表中查找,查找方法为:在孤岛路由表项目中查找目标岛为带电岛的路由表项目,其路径即为该失电孤岛的供电路径。在调度操作规程中规定,送电时从电源侧逐级向负荷侧闭合开关,则可以通过从带电岛的路由表中查找失电孤岛,方法同上。然后再根据约束潮流模型针对所有供电路径进行筛选,并计算网损,根据网损和操作步骤进行恢复方案排序,为调度员恢复操作提供辅助决策功能。
针对配电网中多为树状的结构,部分会采用“手拉手”多电源的方式。本文算法基于对网络进行拓扑分析结果进行处理,经过网络拓扑分析,无阻抗设备汇聚为等值节点,由等值节点连接的有阻抗设备汇聚为一个电气岛,拓扑分析方法不仅适用于链式网络和环网,而且对于“手拉手”多电源供电方式的环网同样适用,避免了在为失电孤岛寻找电源时大量搜索节点链接支路,然后根据本文搜索算法进行处理。如果和分布式电源(DG)带电源孤岛电源之间多电源连接,存在不同电源之间的联系,则必须要考虑同期,本文方法在给出的恢复方案中检测到多电源连接时,会生成同期检查报告提示调度员。本文的搜索算法给出的是恢复策略,具体实现由现场操作人员在操作时进行同期检查。
3 恢复方案校验
针对搜索得到的失电孤岛供电方案,首先进行校验排序,每个负荷属性都有对应的等级和大小。等级较高的负荷对应的恢复方案优先校验,相同等级的负荷按其负荷大小进行排序校验。之后依次检验岛内功率平衡和最优潮流。
3.1 电源配置校验
边界合上后会出现电气岛合并,此时无需再重新对全网进行拓扑分析,而是进行动态拓扑分析,即直接修改恢复方案中所涉及的电气岛内设备属性。对新形成的电气岛首先进行电源配置校验,即有功功率配置和无功问题。按式(1)和式(2)进行校验,对恢复方案进行初筛,并生成相应问题报告。
式中:PGmax为岛内有功电源容量;QGmax为岛内无功电源总容量;PD为岛内有功负荷;QD为岛内无功负荷;K1为有功平衡可靠系数;K2为无功平衡可靠系数。
对满足功率配置要求的恢复方案再进行最优潮流计算,校验其电压质量和线路传输容量是否满足规定要求。不满足的不再进行最优潮流校验。
3.2 最优潮流校验
由于常规的潮流计算只是完成某一种具体运行方式下的计算功能,并不能有效验证供电方案是否合理,因此采用最优潮流验证方案的可行性。一种供电方案可理解为一种网络拓扑结构,在给定机组出力约束和负荷条件下,利用最优潮流可以验证某一种供电方案是否满足设备安全运行,这是常规潮流计算无法达到的功能。
本文以系统网损最小为目标函数,所采用的最优潮流数学模型如下所示:
式中:nbr为支路数;SB为系统所有节点集合;SG为发电机节点集合;SC为无功补偿节点集合;SL为支路集合;Gij和Bij为节点导纳矩阵中的元素,Yij=Gij+Bij;θij为节点i,j之间的相角差;Pi和Qi分别为节点有功和无功注入;PGi,PmaxGi,PminGi分别为发电机有功出力及其上、下限;QGi,QmaxGi,QminGi分别为发电机无功出力及其上、下限;QCi,QmaxCi,QminCi分别为无功补偿装置出力及其容量限制;Pl和Pmaxl分别为支路有功功率及其传输上限;Vi,Vmaxi,Vmini分别为节点电压及其上、下限。
内点法在收敛性、计算速度等方面具有无可替代的优势,已广泛应用于研究各种大规模、复杂的线性规划问题,以及各种二次规划和非线性规划问题。原对偶内点法是按照目标函数的导数信息确定搜索方向的,因此收敛速度较快。该算法较为成熟,应用广泛,解析过程清晰,结果的可信度高,并且这种算法对初始点的选择不敏感,可以直接采用非内点来启动算法。原对偶内点法虽然其方法本身需要大量的求导、求逆运算,但是采用导纳稀疏阵进行存储,对计算机的存储量要求降低,可以大大提高程序运行的效率。考虑原对偶内点法所具有的以上特点,本文在计算最优潮流问题上选择原对偶内点法。
其基本思想是:引入松弛变量将函数不等式约束转化为等式约束及变量不等式约束,用拉格朗日乘子法处理等式约束条件,用内点障碍函数法及制约步长法处理变量不等式约束条件,导出引入障碍函数后的库恩—图克最优化条件,并用牛顿—拉夫逊法对其进行求解。
4 算例分析
采用IEEE 14节点标准测试系统对本文算法进行验证测试。将线路6-12和线路13-14设置为热备用。本文对IEEE 14节点标准测试系统的可调措施选择为发电机有功、无功出力和无功补偿装置,基准功率为100MVA,其中发电机有功、无功出力数据如表2所示,无功补偿装置所在节点为节点9,最大补偿容量为0.5(标幺值)。表中:Gi为发电机序号;Bus为发电机所在母线号;Pmax和Pmin分别为发电机有功出力上、下限(标幺值);Qmax和Qmin分别为发电机无功出力上、下限(标幺值)。
在线路6-13故障情况下进行拓扑分析,得到如图4所示的电气岛联系图。
采用本文算法,故障岛不会出现在恢复方案,所以故障岛不在初始化列表内。初始化后各电气岛路由表如表3所示。
所有电气岛经过一次路由表更新,便可以得到各个电气岛最终的路由表信息,可见距离向量算法收敛较快,如表4所示。
由电气岛最终路由表可以得到失电孤岛4的供电方案由两个:方案1,由带电岛1经过开关A和D获得供电;方案2,由带电岛1经过开关C和F获得供电。而采用深度优先树形搜索,如果先从失电孤岛1经无源岛2搜索,则搜索到带电岛1停止,带电岛1标记为已处理,之后在经由无源岛3搜索时不会再搜索带电岛1,这样就漏掉了可能的供电路径CF,反之亦然。
之后分别对两种供电方案进行最优潮流验证,采用MATLAB编程,平均值启动,最大迭代次数为50,结果用标幺值表示,如表5所示。
根据最优潮流结果,选择方案2,依次合上开关C和开关F,由备用线路6-12向负荷节点12和13进行供电。
5 结语
本文受因特网路由选择协议算法的启发,提出一种基于距离向量的失电孤岛供电路径搜索算法。该算法与其他基于图论的搜索算法不同,更侧重于各电气岛之间的联系,通过路由表的更新,找到失电孤岛恢复供电的多种可能路径。
经IEEE 14节点标准测试系统验证分析,该方法高效可行,编程简单,而且针对环形结构的网络收敛速度更快。在路由表的更新过程中即可判断各个路径的长短,供电路径与树形搜索相比更加完整,可直接得到符合调度规程的供电方案,缩短了恢复供电时间。该算法可以应用在目前的操作票系统上,为调度员执行事故或检修后恢复操作提供辅助决策功能。
摘要：由于电网故障或设备检修造成负荷失电,为失电负荷寻找供电路径成为目前许多电网分析软件的必备功能。通过拓扑分析程序将电网划分为若干电气岛,传统的根据树搜索法的孤岛恢复供电路径搜索算法,在路径的搜索上存在不足。文中受因特网路由选择协议算法的启发,将各类电气岛看成路由器,提出一种基于距离向量的搜索算法,通过对各电气岛初始路由表的形成和对路由表的更新处理,最终获得电气岛的全网路由表,通过该路由表可以得到所有可能并且符合调度规程的失电孤岛供电路径。利用内点法最优潮流对搜索得到的供电方案进行可行性验证。以IEEE 14节点标准测试系统为例,验证了该算法的可行性。
关键词：失电孤岛,距离向量,路由选择,供电路径,最优潮流
距离向量算法 篇2
随着大数据时代的到来,已有的数据挖掘技术面临一系列新的挑战。大数据具有数据体量巨大,数据增量快,数据结构复杂等特点[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]提出的增量分类算法相比,分类精度近似相同,但所需时间复杂度和存储空间则有不同程度的下降,这对大数据的处理是具有重要意义的。
用平面法向量求空间距离和夹角 篇3
空间向量是数学的一个新工具, 利用它处理立体几何问题往往可以省去许多麻烦, 其突出的特点是以算代证. 求空间角和距离时, 并不用知道垂线在哪里, 也不必作出要求的角, 只要按固定的方法一步一步地算下去, 就能得出你所要的结论. 本文结合具体案例, 介绍用平面的法向量来求解这类问题.
一、求点到平面的距离
例1在单位正 方体ABCD A1B1C1D1中, E, F分别是AB, BC的中点. 求点D到平面B1EF的距离.
评析解这类问题的基本思路是:
如图2, 点B到平面α的距离
在 Rt△ABC 中,
二、求平行平面之间的距离
例2在长方体ABCD - A1B1C1D1中, 已知AB = a, BC = b, CC1= c, 求平面A1BD和平面B1D1C的距离.
解如图3, 建立空间直角坐标系, 则D (0, 0, 0) , A1 (b, 0, c) , B (b, a, 0) , C (0, a, 0) .
令 x = ac, 则 y = - bc, z = - ab.
所以, n = (ac, - bc, - ab) .
要求平面A1BD和平面B1D1C的距离, 只需求点C到平面A1BD的距离, 则
评析解这类问题的基本思路是:
若平面α∥平面β, 求平面α和平面β 之间的距离可转化为平面α内的任一点到平面β 的距离.
三、求异面直线的距离
例3在单位正方体ABCD - A1B1C1D1中, 已知M, N分别是BB1, B1C1的中点, P是线段MN的中点. 求DP与AC1的距离.
解如图4, 建立空间直角坐标系, 则B1 (0, 0, 0) , A (0, 1, 1) , C1 (1, 0, 0) , D (1, 1, 1) , P (1/4, 0, 1/4) .
设过DP且平行于AC1的平面α的方程为A2x + B2y + C2z + e = 0.
因为DP∈α, 所以A2+ B2+ C2+ e = 0,
评析解这类问题的基本思路是:
求异面直线l1, l2的距离, 只需过直线l2作平面α∥l1, 则可转化为求直线l1上任一点到平面α的距离.
四、求直线与平面的距离
例4在直四棱柱ABCD - A1B1C1D1中, 底面为直角梯形ABCD, CD⊥AD, AB = 2, AD = 3, DC = 6, AA1= 6, M, N分别是C1D1, CC1的中点. 求MN与平面AD1C的距离.
解如图5, 建立空间直角坐标系, 则D (0, 0, 0) , A (3, 0, 0) , C (0, 6, 0) , D1 (0, 0, 6) , M (0, 3, 6) , N (0, 6, 3) .
令 x = 2, 则 y = z = 1.
要求MN与平面AD1C之间的距离, 只需求点N与平面AD1C的距离.
评析解这类问题的基本思路是:
求直线l与平行平面α的距离, 可转化为求直线l上一点到平面α的距离.
五、求直线和平面所成的角
例5在长方体ABCD - A1B1C1D1中, AB = 2, AA1=AD = 1, 求AB与平面AB1C所成的角.
解如图6, 建立空间直角坐标系, 则D (0, 0, 0) , A (1, 0, 0) , C (0, 2, 0) , B1 (1, 2, 1) .
设平面AB1C的法向量为n = (x, y, z) .
故AB与平面AB1C所成的角为arcsin1/3.
评析解这类问题的基本思路是:
如图2, 直线l∩平面α = A, B是直线l上的一点, BC⊥α于点C, 则∠BAC为直线l与平面α所成的角.
设平面法向量为n, 则
六、求二面角
例6在正方体ABCD - A1B1C1D1中, 求二面角A BD1- A1的度数.
解设正方体为单位正方体. 如图7, 建立空间直角坐标系, 则D (0, 0, 0) , A (1, 0, 0) , D1 (0, 0, 1) , B (1, 1, 0) , A1 (1, 0, 1) .
所以α = 60°.
又易知二面角A - BD1- A1的平面角为α, 因此, 二面角A - BD1- A1为60°.
距离向量算法 篇4
由于互联网的蓬勃发展, 促使知识经济时代的来临, 企业对网络的依赖程度也是与日俱增的。其中ISP扮演着不可或缺的角色, 除了提供基本网络服务外, 它也能够确保企业的设备文档且持续性地正常运作。骨干网络大多数会构建一条1对1的后备线路, 一方面避免故障造成服务中断的难题;另一方面当线路状况稳定时可以整合所有可用的网络连线做负责平衡, 充分利用可用的带宽。本文的目的是设计一个故障网管系统, 只被动的监测骨干网络中的路由器, 便能够快速的侦测故障的发生, 并正确的诊断出故障的位置, 及时的提供给网络管理人员, 从而排除故障使得企业的损失降为最低。本文利用EIGRP作为骨干网络的故障管理系统, 采用了事件与故障相关联的思想作为系统管理的方法, 由于当网络发生变化时, 路由表也会随之发生变化, 不同的故障会导致路由表有不同的变化。利用路由表变化与故障关联的概念分析可以得到故障发生的位置。此外, 系统利用距离向量路由协议的封包作为侦测故障的工具, 并根据封包的类型作为事件依据以决定系统的决策[1]。
1 本文方法
本文提出的网络故障管理系统提供了两方面的功能, 分别是故障侦测以及故障诊断。其中故障侦测是利用路由封包作为侦测故障发生与否的依据;而故障诊断则是利用故障发生前后路由拓扑的对比来对故障的位置进行定位。
流程是由故障侦测发现有报警开始, 将过去一段时间内收集到的报警进行故障的分析, 根据关联结果判断故障可能位于网络上的哪一个设备上。一旦找到真正的故障位置后便能够进行故障的排除工作, 如此便完成故障管理步骤的一个循环。整个系统由五个功能部件组成, 分别是网络资源搜索、网络拓扑搜索、拓扑数据库、故障侦测和故障诊断, 最后由图形界面进行整合。
当网络拓扑发送变化时, 路由器会广播EIGRP封包到整个网络上, 被监测路由器收到EIGRP封包后会计算新路由, 本文将这一过程记录成日志的形式并以trap的方式传送给故障管理系统, 该日志被定义为报警。系统的故障过滤功能所可能处理到的报警有两种:主要报警 (日志中有直接诊断出故障的位置) 和次要报警 (日志中无法诊断出故障位置, 只能够过滤出含有什么类型的EIGRP封包) 。次要报警可以通过故障与路由表变化的报警关联的过程定位出故障的位置。
路由表代表了整个网络拓扑的状态, 因此当网络发生变化时, 路由表也会随之变化, 本文根据路由表的变化完成对故障的定位。本文根据EIGRP封包来侦测故障的发生, 当侦测到故障发生时, 系统会收集故障后被监测路由器的路由表, 并与故障发生前的路由拓扑进行比较即可得出路由表变化的信息, 并根据变化信息进行分类即可得到准确的故障发生位置[2]。
在进行网络故障诊断时, 本文首先基于广度优先搜索方法对相邻串列拓扑信息库进行排列。故障发生时, 系统会收集被监测路由器的路由表, 然后进行故障前后路由拓扑的对比即可完成故障的诊断。
2 实验结果与分析
本文选择了五种常见的EIGRP故障对本文方法进行了验证, 分别是: (1) 可直接根据系统日志诊断出故障位置的路由器或介面故障、 (2) 故障位置与交换机相连、 (3) 故障位置未连接交换机、 (4) 单一路由的路由表丢失以及 (5) 故障位置在负载平衡时, 网络无法正常运作。
本文以诊断准确率作为评价指标对方法进行了验证, 当故障发生时, 最理想的情形是所有的故障都会被系统诊断出, 但是由于故障是特定范围设备等造成的将可能导致故障无法被准确诊断。诊断准确率的定义如式1所示。
针对上述的五种故障, 本文提出的方法的诊断准确率如表1所示。
由表1可知, 本文方法对于正常的单一设备导致的网络故障具有较好的诊断准确率, 对于特定范围的设备同时故障的情况, 方法的诊断准确率仍然有待提高。
3 结论
本文针对基于距离向量路由协议的网络故障管理展开了研究, 提出了一种适用于网络故障管理的系统, 该系统包括了两方面的功能, 分别是故障侦测以及故障诊断。其中故障侦测是利用路由封包作为侦测故障发生与否的依据;而故障诊断则是利用故障发生前后路由拓扑的对比来对故障的位置进行定位。本文以五种常见的EIGRP故障对本文方法进行了验证, 实验结果表明, 对于正常的单一设备导致的网络故障, 本文方法具有良好的故障诊断准确率。
摘要：随着信息时代的进步, 网络环境也随之日益复杂化, 为了确保网络中服务器和应用的高可靠性, 现在的网络骨干网中都设置了后备线路, 一方面能够有效避免由于上层服务中断所造成的运营损失;另一方面能够在网络流量过大时对流量的负载平衡进行整合。当网络发生故障或问题时, 将对企业客户造成无法估量的损失, 因此, 本文提出了一种基于距离向量路由协议的网络故障管理系统, 以确保骨干网络的高可靠性和高可用性, 为了提高系统的可扩展性与实用性, 本文基于plug-and-play的思想, 使得该系统只需被动监控骨干网络中的任一路由器即可实现对故障发生的可疑位置的定位。
关键词：距离向量路由协议,网络管理,故障管理
参考文献
[1]R.Hao, D.Lee, J.Ma, and J.Yang, “Fault management for networks with link state routing protocols, ”Proccedings of IEEE/IFIP NOMS, Vol.1, pp.103-116, April 2004, Soul Korea.
距离向量算法 篇5
一、利用法向量求点到平面的距离
若 A∈α,n是平面α的法向量,点P到平面α的距离:
例1 在长方体A1B1C1D1- ABCD中,AB = 4,AD = AA1= 2,求点D到平面AD1B1的距离.
解 建立如图所示的空间直角坐标系D1- xyz,则D1( 0,0,0) ,A( 2,0,2) ,B1( 2,4,0) ,D( 0,0,2) ,设平面AD1B1的法向量为n = ( x,y,z) ,则:
令 y = 1,则 x = -2,z = 2,故 n = ( -2,1,2) .
而 所以点D到平面AD1B1的距离为
二、利用法向量求直线到与它平行的平面的距离
例2在长方体A1B1C1D1- ABCD中,AB = 4,AD = AA1= 2,求DC1到平面AD1B1的距离.
解∵DC1∥AB1,
∴DC1∥平面D1AB1.
由DC1上的任意一点到平面D1AB1的距离就是直线DC1与平面D1AB1的距离.
∴D点到平面AD1B1的距离就是直线DC1与平面D1AB1的距离.
由例1解题过程可知直线DC1与平面AD1B1的距离为4 /3.
三、利用法向量求两平行平面的距离
例3在长方体A1B1C1D1- ABCD中,AB = 4,AD = AA1= 2,求平面D1AB1与平面DBC1的距离.
解在两个平行平面中,其中一个平面内任意取一点到另一个平面的距离等于这两个平行平面的距离. 显然平面DBC1内的一点D到平面AD1B1的距离. 于是问题就转化为先求平面AD1B1的法向量,再利用法向量求D点到平面AD1B1的距离. 解题过程与例1相同,故平面AD1B1和平面DBC1的距离为4 /3.
四、利用法向量求两异面直线的距离
例4在长方体A1B1C1D1- ABCD中,AB = 4,AD = AA1= 2,求异面直线AD1与C1D的距离.
距离向量算法 篇6
高分辨雷达接收的目标回波占据多个距离分辨单元,形成目标的一维高分辨距离像,反映了目标散射点在雷达视线上的分布情况,为物理特性相似的复杂目标分类提供了必要的信息来源[1]。但是,一维距离像敏感于目标姿态角的变化。因此,采用合适的特征提取和分类方法,是正确识别目标的关键。
支持向量机(SVM)最早由Vapnik提出,是结构风险最小化(SRM)思想的具体实现,其结构简单且具有全局最优性能[2,3]。故应用SVM可设计高性能的一维距离像分类器。
此外,在模式识别领域得到成功应用的还有零空间(null-space)方法[4],零空间方法主要是利用类内散布矩阵的零空间特性结合Fisher准则求解最优的线性子空间。
本文结合上述方法,提出了一种新的方案:用SVM方法计算不同类别的支持向量集(SVs),通过SVs估算类间散布矩阵Sb及类内散布矩阵Sw,再由Sb,Sw构建的Fisher判别式分析中应用其零空间特性,建立一个最优变换矩阵,对每类目标进行特征提取。
2 支持向量集
2.1 两类目标的支持向量集
对非线性可分的训练样本集:
undefined
可以通过非线性变换转化为某个高维空间中的线性问题,即xi→Φ(xi),Φ(xi)是xi的高维空间表示,Φ是隐函数,无需知道函数的具体形式。于是训练样本集变为:
undefined
在高维特征空间中利用SVM方法求支持向量集,方法如下:
SVM分类面函数表示为:
undefined
最大化分类间隔等价于如下优化问题:
undefined
约束条件:
undefined
其中:undefined。
若Φ(xi)不是支持向量,则αi=0,否则αi≠0,且式(3)的等号成立,即:
undefined
定义支持向量集[5]:
undefined
SV1表示正例支持向量集,SV2表示反例支持向量集。
2.2 多类支持向量集
对多类问题,本文选用相对简单且有效的一对多方法。假设训练样本集一共有C个类别,该方法需要构造C个SVM分类器,第i(i=1…C)个分类器将第i类与其余的类别分开。
在构建第i个分类器时,设第i类为正例集合,即yj=1,Φ(xj)∈i,其余类别为反例集合,即yj=-1,Φ(xundefined)∉i。根据式(5)的定义得到属于第i类的正例支持向量集,在此定义为SVi。同理,可得到总共C个类别的支持向量集,记为:
undefined
3 最优变换矩阵
3.1 利用支持向量构造Fisher判别式
设Φ(xij)∈SVi(j=1,2,…,Ni)为第i类目标的第j个支持向量,其中Ni为第i类目标支持向量的个数。计算类间散布矩阵Sb和类内散布矩阵Sw:
undefined
其中:undefined表示第i类支持向量的均值向量。构造Fisher判别式:
undefined
w是整个支持向量空间(设所有支持向量个数为N)的线性组合:
undefined
因此,Fisher优化准则变成如下形式:
undefined
其中Kb,Kw为核矩阵,定义为[6]:
undefined
其中:
undefined
K(·)为核函数,本文选用高斯核函数。
undefined
3.2 利用零空间特性求解最优变换矩阵
为使式(12)取最大,传统的方法是通过对KundefinedKb进行主成分分析,求解较大特征值对应的特征向量构造变换矩阵,忽略了类内散布矩阵Kw的零空间特性。零空间是由特征值为零的特征向量构成的矩阵,使得式(12)的分母为零,此时若分子>0,必然有最好的可分性。研究表明零空间方法求变换矩阵优于其他的子空间方法[4]。
下面给出一种有效的零空间方法,并用其求解最优变换矩阵。
令Kt=Kw+Kb,可以证明:
undefined
其中n为支持向量维数,N为支持向量集的样本个数,C为类别数。由于支持向量的数量通常都比较少,因此n>N,rank(Kb)=C-1。
求解变换矩阵步骤如下:
(1) 去除Kt的零空间
对Kt进行特征分析,得到投影空间P,P由Kt的非零特征值对应的特征向量构成。其后,用P修正类内散度矩阵Kw,得到K′w。
undefined
(2) 求K′w的零空间
对K′w特征分解,去掉大于零的特征值对应的特征向量,通常保留C-1个特征向量,并构造矩阵Y:
undefined
(3) 最优变换矩阵
undefined
W由具有最优可分性的C-1个向量构成。同时,可以证明式(12)中分子K″b=WTKbW是非奇异的[4]。
4 基于最优变换矩阵的目标识别
将式(16)中的第i(i=1,…,C)类目标的均值向量mi向最优变换矩阵W投影[4]:
undefined
投影矢量yi作为第i类目标的库模板矢量。则总的库模板矢量为:
undefined
设待测样本作非线性变换后向最优变换矩阵投影得到yt,计算欧式距离:
undefined
若:
undefined
则判定目标属于第k类。
5 实验结果
本文采用的实测数据是ISAR雷达对空中3种飞机(安-26,奖状,雅克-42)所成的距离像。采样点数为256。试验数据为3种飞机任取一段的260幅距离像,用隔一取一方法将距离像分为训练样本集和测试样本集。
识别前做如下处理:
归一化:将每幅距离像用总能量归一。
距离对准:利用Fourier变换的平移不变性,将一维距离像做Fourier变换即可对齐。
实验:对训练和测试数据应用本文方法(SVN),基于所有训练样本的核 Fisher方法(转换矩阵求解采用零空间方法,KFN),基于所有训练样本的核Fisher方法(转换矩阵求解用传统的主成分分析方法,KFP)和基于一对多方法的多类支持向量机方法 (MSVM)进行识别实验 。结果列于表1中。
从表1可以看出,对于几种基于核函数的分类识别方法,本文提出的方法(SVN)好于其他三种。SVN利用SVM方法求解属于不同类别的支持向量,进而对支持向量进行Fisher判别分析,将两类问题扩展到多类,同时结合了零空间方法求解最优变换矩阵,使得识别性能得到改善。
6 结 语
本文通过对核支持向量的Fisher分析,结合零空间方法,获取最优变换矩阵,对雷达目标目标一维距离像进行识别实验。实验结果表明:仅利用支持向量集训练分类器,就能取得与基于全部训练样本得到的分类器略好的性能;零空间方法求解变换矩阵优于其他子空间方法。因此SVN方法能改善对雷达目标的识别性能。
参考文献
[1]周代英.雷达目标一维距离像识别研究[D].成都:电子科技大学,2001.
[2]边肇褀,张学工.模式识别[M].2版.北京:清华大学出版社,2000.
[3]Vapnik N.The Nature of Statistical Learning Theory[J].New York:Springer Verlag,1995:1-188.
[4]Liu Wei,Wang Yun-hong.Null Space-based Kernel FisherDiscriminant Analysis for Face Recognition[C].(In):Pro-ceedings of the 6th International Conference on AutomaticFace and Gesture Recognition,Seoul,Korea,2004:369-374.
[5]张宝昌.基于支持向量的kernel判别分析[J].计算机学报,2006,29(12):85-92.
常用支持向量机算法分析 篇7
支持向量机 (Support Vector Machines简称S V M) 追求的是在有限样本情况下的最优解而不仅仅是样本数趋于无穷时的最优解, 它具有很好的推广性能, 对未知样本的预测有较高的准确率, 因此得到广泛应用, 目前SVM已成为国际上机器学习领域的研究热点。
1 分块算法
“块算法”基于的是这样的事实, 即去掉Lagrange乘子等于零的训练样本不会影响原问题的解。对于给定的训练样本集, 如果其中的支持向量是已知的, 寻优算法就可以排除非支持向量, 只需要对支持向量计算权值 (即Lagrange乘子) 即可。实际上支持向量是未知的, 因此“块算法”的目标就是通过某种迭代方式逐步排除非支持向量。具体的作法是, 选择一部分样本构成工作样本集进行训练, 剔除其中的非支持向量。并用训练结果对剩余样本进行检验, 将不符合训练结果 (一般是指违反KKT条件) 的样本 (或其中的一部分) 与本次结果的支持向量合并成为一个新的工作样本集, 然后重新训练。如此重复下去直到获得最优结果, 其收敛性在文献中得到了证明, 同时在文献中也对分解算法的收敛性进行了研究。这种方法当支持向量的数目远远小于训练样本数目时, “块算法”显然能够大大提高运算速度。
2 子集选择算法
把问题分解成为固定样本数的子问题:工作样本集的大小固定在算法速度可以容忍的限度内, 迭代过程中只是将剩余样本中部分情况最糟的样本与工作样本集中的样本进行等量交换, 即使支持向量的个数超过工作样本集的大小, 也不改变工作集的规模, 而只对支持向量中的一部分进行优化。
这个思想最早由Osuna等人提出来的。在Osuna算法中, 首先建立一个工作集, 保持其大小不变, 在解决每个二次规划子问题时, 先从工作集中移走一个样本, 并加入一个不满足KKT条件的样本, 再进行优化。固定工作样本集的方法和块算法的主要区别在于:块算法的目标中仅包含当前工作样本集中的样本, 而固定工作样本集方法虽然优化变量仅包含工作样本, 其目标函数却包含整个训练样本集, 即工作样本集之外的样本的Lagrange乘子固定为前一次迭代的结果, 而不是像块算法那样设为0。而且固定工作样本集方法还涉及到一个确定换出样本的问题 (因为换出的样本可能是支持向量) 。这样, 这一类算法的关键就在于找到一种合适的迭代策略使得算法最终能收敛并且较快地收敛到最优结果。
3 序列最小优化算法
Platt在中提出SMO (Sequential Minimal Optimization或SMO) 算法。将工作样本集的规模减到最小 (两个样本) 。之所以需要两个样本是因为等式线性约束的存在使得同时至少有两个Lagrange乘子发生变化。由于只有两个变量, 而且应用等式约束可以将其中一个用另一个表示出来, 所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来。这样, 算法避开了复杂的数值求解优化问题的过程, 此外, Platt还设计了一个两层嵌套循环分别选择进入工作样本集的样本, 这种启发式策略大大加快了算法的收敛速度。
对Platt的SMO算法, Keerthi等通过对S V M算法的分析在文献中提出了重大改进, 即在判别最优条件时用两个阈值代替一个阈值, 从而使算法更合理, 更快。其收敛证明在文献中。并通过实际数据的对比, 证明确实比传统SMO快。同时也指出S M O算法应用于回归等类似的问题。Ronan将考虑了上述改进的SMO算法应用于分类和回归问题, 实现了比SVMlight更强的软件包。Pavlov提出了速度快于SMO方法的Boost-SMO方法。为了弥补SMO在求解线性支持向量机当中的不足, K a iMin Chung提出了线性支持向量机的分解算法。
4 增量式算法
文献提出一种增量式学习方法, 其将增量集合作为测试集合, 将所有违反K K T条件的样本与原先的支持向量集合作为新的训练集合, 而将所有正确分类的样本抛弃, 然而对于新的分类器的偏转和移动, 这些样本也有可能成为违反K K T条件的样本, 所以如果将这些样本抛弃, 有可能会丢失有用信息, 影响分类器的精度。
文献[1]提出一种在线训练支持向量机的方法, 其从实验结果证明了其学习速度快于S M O方法, 但其是从两个样本开始, 新的样本是一个一个地增加的, 每检测到一个违反KKT条件的样本, 都要进行一系列的循环训练, 直到全部被正确分类为止, 这样当支持向量的数量较少时, 求解二次规划的规模较小, 速度可以较快, 但当支持向量数量较多时, 每新增一个违反K K T条件的样本都求解一次大规模二次规划问题, 支持向量机的训练速度会大大降低, 这时其在线学习的时间会明显增加, 其效率明显降低。
5 SVM多类分类方法方面的研究
支持向量机最初是为两类分类问题而设计的, 如何有效地将其应用到多类分类问题, 是当前支持向量机研究的一个重要方面。目前, 构造S V M多值分类器的方法主要有两类, 一类是同时考虑多类的分类方法:V.Vapnik[2], Weston[3]在1999所提出的多值分类算法, 与前面方法对等的还有文献中所提出的方法。C r a m m e ra n d Singer在2000年提出的多类分类算法。
另一类算法的基本思想是通过组合多个二值子分类器实现对多类分类器的构造。
1-a-r (1-against-rest) 方法, 对于N类问题, 构造N个分类器, 第i个SVM用第i类中的训练样本作为正的训练样本, 而将其它的样本作为负的训练样本。最后的输出是两类分类器输出最大的那一类, 其缺点是它的泛化误差无界。
1-a-1 (1-against-1) 方法, 该算法在N类训练样本中构造所有可能的两类分类器, 每类仅仅在N类中的2类训练样本上训练, 结果共构造K=N (N-1) /2个分类器。
Platt等提出了一个新的学习架构:决策导向的循环图 (Decision Directed Acyclic Graph, DDAG) , 将多个两类分类器组合成多类分类器。对于N类问题, DDAG含有N (N-1) /2个分类器, 每个分类器对应两类, 其优点是泛化误差只取决于类数N, 和节点上的类间间隙 (Margin) , 而与输入空间的维数无关, 根据D D A G提出算法D A G S V M, D D A G的每个节点和一个1-a-1分类器相关, 其速度显著比标准算法 (1-a-r) 或最大值算法 (Max Wins) 快。
摘要：支持向量机是在统计学习理论的VC维理论和结构风险最小化原则的基础上提出的一种新的模式识别技术, 本文对于当前常用支持向量机的几种算法进行了总结和分析, 对于今后提出更精确的方法做了充分的准备。
关键词：支持向量机,机器学习,模式识别
参考文献
[1]Lau K W, Wu Q H.Online Train-ing of Support Vector Classifier[J].Pat-tern Recognition, 2003, 36:1913～1920.
[2]Vapnik V.Statistical LearningTheory[M].New York:Wiley, 1998.