最小决策算法

最小决策算法（精选7篇）

最小决策算法 篇1

一、引言

入侵响应系统(Intrusion Response System,IRS)是对入侵检测系统检测出的安全事件进行响应,阻止攻击行为和降低损失的系统。入侵响应决策是指对攻击选择适当的响应方式的过程,是自动入侵响应系统的核心技术,是网络安全研究的热点问题。目前对于自动入侵响应决策模型的研究,大部分采用的是基于分类的入侵响应决策模型[1],2002年Wenke Lee[2]提出了成本敏感模型,以代价作为入侵响应策略的依据,Balepin等人在其研发的自动入侵响应原型系统ARB中提出了类似的思想方法[3],但是该模型没有考虑入侵检测系统所产生的误报和漏报等因素,且仅用于决策是否要进行响应,没有将代价应用到响应方式的决策中,过于简单实际应用效果并不理想。基于成本敏感模型,提出一种最小代价的入侵响应决策算法,并对攻击和响应相关的因素的代价进行了量化,测试结果表明,取得良好的效果。

二、成本敏感模型

成本敏感模型以代价作为入侵响应决策的基础,将入侵检测与入侵响应所涉及的代价分为检测代价(Operational Cost,Op Cost)、损失代价(Damage Cost,DCost)和响应代价(Response Cost,RCost)等三种。对于入侵检测系统检测到的攻击行为,计算其损失代价和响应代价,如果其损失代价大于响应代价,即DCost>RCost,则采取响应措施;反之,如果DCost

三、基于最小代价的响应决策算法[4]

入侵检测系统不能消除误报和漏报,建立在误报基础上的入侵响应就会导致系统的损失和资源的浪费。对于IRS如果响应代价大于损失代价,就没有必要响应,同时当响应措施实施后,如果还不能有效地阻止攻击进行,就要采取更加严厉的响应措施。

对于n种攻击类型,对应n种响应方式,假设用i表示攻击类型;j表示IDS的报警类型,αij表示第i种的攻击触发j类报警的次数。IDS报警可分为成功检测区、错报区、漏报区和误报区等四个区域,入侵检测相关的属性定义如下:

为了解决入侵检测系统报警的不确定性,IRS应根据入侵检测系统的报警可信度采取不同的响应措施。设IRS共支持n种响应方式,定义一个集合R=(r0,r1……,rn)表示系统支持的响应方式,其中r0表示空响应。对IDS的任意安全事件报告aj,响应决策模型要从R中挑选出有效且代价最小的响应方式。

用e=(a,r)表示实际发生的攻击类型为a,IDS检测出的类型为e,采取的响应方式为r。则IRS的总损失代价(Consequential Cost,记为CC)是响应操作代价(Response Cost,记为RC)与残留损失代价(Reside Damage Cost,记为RDC)之和。

(1)响应操作代价表示执行入侵响应方式所耗费的代价,如执行主动报文所耗费的计算资源等。

(2)残留损失代价是响应执行前系统已经造成的损失和响应方式不当给系统造成的损失。残留损失代价计算与四个因素有关:攻击损失代价(DCost)、攻击目标的重要性(criticality)、攻击目标对特定攻击的免疫力(immunity)、响应方式的负面效应(side Cost)。

基于代价响应决策模型对各种代价的量化,因为不是所有代价都能以特定量化形式表示,因此采用定性分析以测量其相对大小。根据攻击的分类定义攻击损失代价的量化如下表1所示。

攻击目标的重要性指受攻击目标在网络中的重要程度,依据重要程度讲攻击目标分为四类:防火墙和路由器、DNS服务器、Web服务器和Mail服务器、Unix和Windows工作站,各类攻击目标的重要程度量化值如表2所示:

响应目标的免疫力指目标系统对某些攻击的免疫能力,如Sadmind Ping攻击和Sadmind BOF攻击仅针对Solaris系统,对Unix和Windows工作站无效。免疫力用数值0和1表示,0表示系统对该攻击无免疫力,1表示对该攻击具有免疫力。

响应方式的负面效应表示响应执行后给合法用户带来的影响和损失,负面代价用DOS攻击代价进行量化,如关闭主机响应方式对合法用户相当于遭受DOS攻击,其负面代价等于DOS攻击损失代价。

根据IDS检测结果CC的计算分为四类,如下表3所示。

对于i类型攻击,IDS报告的攻击类型为j,定义响应系统的期望累积代价为ECC。ECC计算方式如下:

为支持自适应性,为每种攻击类型对应的响应方式定义一个成功率suc(a,r),表示对攻击类型a执行响应方式r的成功率,suc(a,r)计算公式如下:

响应决策的目标是为攻击a从响应方式集合R中找出最有效的响应方式r*,且使得系统的期望总代价最小。即:

ECC+=(公式3)

响应决策算法流程如下:

(1)通过机器学习的方式对IDS进行训练,为A,Q,mi,sj,pii,qj(1<=i,j<=n)置初值;

(2)设当前收到的报警为ha*,对响应方式集合R=(r0,r1……,rn)中每个响应方式ri利用公式1分别计算其期望累计代价ECC(ha*,ri);

(3)根据公式3计算最优响应方式r*,发送命令至响应执行模块以发起响应;

(4)更新A,Q,以及相应mi,sj,pii,qj的值,在响应执行后根据公式2更新suc(ha*,r*)的值。

四、入侵响应决策算法测试

以DDOS攻击和Port Scan端口扫描攻击为例,测试最小代价入侵响应决策算法的合理性和有效性。典型入侵响应及其响应操作代价、残留损失因子以及负面代价如下表4所示。

假设有两个攻击目标h1(131.83.1.31,遭受DDOS攻击)和h2(172.16.112.50,遭受Port Scan攻击),它们的属性如下:

由表1可知,DCost(DDOS)=30,DCost(Port Scan)=2。

对于正确报警,ECC的计算简化为ECC(a,r)=RC(a,r)+RDC(a,r)。各种代价以及总代价计算如表5和表6所示,其中表5对应h1遭受DDOS攻击,表6对应h2遭受Port Scan攻击。

可见对于DDOS攻击,最有效的响应方式为隔离服务,隔离受害主机的相关服务;对于Port Scan攻击,最有效的响应方式为阻止入侵者IP,对于一对一或一对多的Port Scan攻击,隔离攻击源是最为合理的响应方式。

五、结束语

针对成本敏感模型入侵响应决策存在的问题,综合考虑攻击和响应以及攻击目标等各方面的因素,以系统期望代价最低为目标,重新构建入侵响应总体损失代价算法,并对攻击和响应相关的因素进行了量化,系统对DDOS攻击和Port Scan端口扫描攻击的测试结果表明达到良好响应效果。如果需要增加新的响应方式,只需要提供关于该响应方式的几个参数,比如响应操作代价等,与基于分类的响应决策算法相比,该算法具有更高的有效性和扩展性。

摘要：借鉴成本敏感模型,综合考虑攻击和响应以及攻击目标等各方面的因素,提出基于最小代价响应决策算法,并对攻击和响应相关的因素进行了量化,与基于分类的响应决策算法相比,该算法具有更高的有效性、成功率和扩展性。

关键词：入侵响应决策,入侵检测,成本敏感,最小代价

参考文献

[1]Curtis A Carver.Adaptive-based intrusion response[D].College Station:Texas A&M University,2001.

[2]Wenke Lee,Wei Fan,Matthew Miller,et al.“TowardCost-Sensitive Modeling for Intrusion Detection and Response”[J].Journal of Computer Security,2002,10(1):318-336.

[3]Balepin I,Maltsev S,Rowe J,et al.Using specificationbased intrusion detection for automated response[C]//Proc of the 6thInt’l Symp on R ecent Advances in Intrusion Detection.Berlin:Springer,2003.

[4]游凤芹.基于主动网的自适应入侵响应系统的研究和实现[D].东南大学,2006.

多目标最小生成树的竞争决策算法 篇2

最小生成树(Minimum Spanning Tree,简记MST)[1,2]问题是一个经典的组合优化问题,许多工程问题,如管道铺设、电路设计、交通网络等,通常都可转化为最小生成树问题。最小生成树是构造一个带权图的最小代价生成树, 而在实际工程中,由于图的每条边定义了多个属性,因此在决策最小生成树问题时需要同时考虑多个目标。这种同时考虑多个目标的最小生成树问题即为多目标最小生成树问题(multi-criteria MST,简记mc-MST)[3,4],它是NP完全问题[4]。

这类同时优化多个目标的问题为多目标优化问题。在大多数情况下多个目标本质上是相互冲突的,一个目标的改善可能引起其他目标性能的降低,不存在单目标优化问题的全局唯一最优解。在多目标优化问题中存在一组相互之间无法区分优劣的均衡解,即Pareto最优解或非支配解,Pareto最优解只是一个可以接受的非劣解,并且大多数的Pareto解的个数很多,甚至是无穷大[5]。对于多目标的组合优化问题,国内外的有关研究较少,尤其缺乏实用算法。本文将对此作一些探索性的研究,为这类离散型的多目标优化难题提供若干解决手段,对这些模型的实际应用奠定方法和技术上的基础。

竞争决策算法(Competitive Decision Algorithm,简记为CDA)是一种能广泛应用于各类组合优化问题的新型寻优算法[6,7,8,9,10]。CDA算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上, 利用竞争造就优化和决策左右结果的特性而得出的一种寻优算法。在理论方面, 现在已给出了竞争决策算法的通用流程、 特点、 分类、 主要概念及其数学描述、 常用的竞争力函数、 常用的决策函数、 常用的初始状态以及常用的资源交换规则等。在应用方面,已利用其通用流程实现了车辆路径问题、 度约束最小生成树、 旅行商问题、 最小比率旅行商问题、 瓶颈旅行商问题、 背包问题等NP难题的算法并编程实现。

本文拟以CDA算法求解mc-MST问题,在基本CDA算法基础上扩展其求解多目标的能力。

2 mc-MST的CDA算法

2.1 问题介绍

考虑一个连通的无向简单图(无环无多重边的图即为简单图)G=(V,E,W), 其中, V={1,2,…,n}为顶点集, E={e1,e2,…,em}为边集, 若边ek的的顶点为i和j, 则边ek可记为(i,j)。各顶点间的权值wrij已知(wrij>0, wrii=∞, i,j∈V, r=1,2,…,L, L为目标的个数)。设

$x{}_{ij}=\{\begin{array}{l}1,(i,j)\text{选}\text{中}\\ 0,\text{否}\text{则}\end{array}$

,则mc-MST问题的数学模型可以写成:

$\begin{array}{l}\min {\rm Z}=\{{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{n}w}}{}_{ij}^{1}x{}_{ij},{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{n}w}}{}_{ij}^{2}x{}_{ij},\cdots ,{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{n}w}}{}_{ij}^{L}x{}_{ij}\}\\ \text{s}.\text{t}.\{\begin{array}{l}{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{n}x}}{}_{ij}=n-1\\ {\displaystyle \sum _{i\in S}{\displaystyle \sum _{j\in S}x}}{}_{ij}\le |S|-1,\forall S\in V,S\ne \varnothing \\ x{}_{ij}\in \{0,1\}\end{array}\end{array}$

2.2 算法原理

n个顶点的最小生成树共有n-1条边,因此可以把求解多目标最小生成树问题看作是按照竞争力和决策规则把n-1条边依次加入到初始无边且包含n个顶点的图中,在边加入的过程中必须保证不形成任何子回路。本算法只有一个竞争者,即初始无边且包含n个结点的图,被竞争的资源为所有边资源,初始格局是竞争者没有占有边资源,竞争结束时竞争者应占有n-1条边。

2.3 基本符号及含义

为了方便描述,本文采用如下符号来表示:

T:mc-MST问题;

n:mc-MST问题的顶点个数;

L:目标个数;

w[i,j,o]:权值矩阵,表明顶点i与j连线的第o个目标的权值;

sumw[i,j]:sum$w[i,j]={\displaystyle \sum _{o=1}^{L}w}[i,j,o];$

arrivew[i,j]:邻接矩阵,表明顶点i与j是否直接相邻;

tarrivew[i,j]: arrivew[i,j]的传递对称闭包[2],表明顶点i与j是否能够到达(包含通过其它结点中转到达);

Allline[i]:这是一个边的集合,即图中所有与顶点i关联的边;

Line[i]:Allline[i]的子集,边的一个顶点为i,设边的另一个顶点编号为k,则满足tarrivew[i,k]=0,即结点k在当前图中不能到达(含传递到达)结点i;

sumdw[i,k]: Line[i]中sumw[i,j]值第k小边的权值(其中1≤k≤2);

dwj[i,k]:Line[i]中sumw[i,j]值第k小边的另一个顶点的编号(一个顶点编号为i,其中1≤k≤2);

power[i]: 图对顶点i的竞争力函数值, 即把边(i, dwj[i,1])加入到图中的能力;

maxpowerid:当前决策函数选中顶点的编号,即按照当前竞争力和决策函数,下一次加入到图中的边为(maxpowerid, dwj [maxpowerid,1]);

2.4 Pareto解集过滤器

用来存放运行时产生的Pareto解。对于不违反约束的解,若该解支配过滤器中某个解,则将该解加入过滤器同时删除受支配解;若过滤器中某个解支配该解,则放弃该解,否则将该解加入到过滤器中。过滤器的大小可以事先设定。

2.5 初始状态、竞争力函数、决策函数、资源交换规则

(1)初始状态

初始状态只有一个,即所有边资源全部为虚拟竞争者N占有,竞争者A没有任何边资源。

(2)竞争力函数

本算法所采用的竞争力函数的基本思想可描述如下:最小生成树中与每一顶点相连的边至少有一条在树中,因此把权值为sumdw[i,1]的边称为基本边,而把权值为sumdmin[i,2]称为候补边。为了取得好的效果,应该把候补边与基本边差距最大的边优先加入到图中以减少因为基本边不能加入到图中而造成较大的损失。

本算法采用以下三个竞争力函数:

$①power[i]=\frac{1}{sum-dw[i,1]}$,满足条件的边中权值最小的竞争力最大;

② power[i]=sumdmin[i,2]-sumdw[i,1],候选边与基本边权值差距最大的边竞争力最大;

③ power[i]=(sumdmin[i,2]-sumdw[i,1])-(sumdw[i,1]-sumdw[k,1])(k=dwj[i,1]),它在竞争力函数②的基础上,考虑边(i,k)加入到图中对顶点k的基本边造成的损失值(sumdw[i,1]-sumdw[k,1])。

(3)决策函数

本文只采用一个决策函数,在满足条件的顶点中选择power[i]值最大的。若两个顶点的power[i]值相同时,则选择编号小的顶点。

(4) 资源交换规则

对于已经求得的生成树采用边交换作为资源交换规则。若断开其中一条边(i,j)的连线,换成其他一条边(该边的一个顶点为i,j中的一个,另一个顶点为不同于i,j的顶点,且要保证不形成回路),计算边交换后生成树的各个目标的值,使用Pareto解集过滤器进行检查新解的优劣性。

2.6 全局经验指导寻优

为了提高多目标解的分布性与多样性,本文提出一种全局经验指导的寻优方法。在算法中,对于找到的所有Pareto最优解集,寻找解集中散布稀疏的解,在稀疏的解附近采用资源交换规则进行领域搜索并应用Pareto解集过滤器进行更新。

(1) 解之间距离的定义

假设当前解集中有p个Pareto解x=(x1,x2,…,xp),则每个解到所有其他解的距离定义为:

$\begin{array}{l}d{}_i=\underset{j}{{\displaystyle \max }}\left(\sqrt{{\displaystyle \sum _{o=1}^L(}f{}^o(x{}_i)-f{}^o(x{}_j)}\right){}^2,\\ i=1,2,\cdots ,p;j=1,2,\cdots ,p;j\ne i\end{array}$

(2)共享函数的定义

共享函数值

$s{}_i=\{\begin{array}{l}1-d{}_i/\sigma {}_s,\\ 0,\end{array}\begin{array}{l}d{}_i<\sigma {}_s\\ \text{否}\text{则}\end{array}$

,式中σs表示小生境半径,在本文给出的算法中σs取30。

将共享函数值最小的解作为继续寻优的方向。

2.7 算法流程

多目标最小生成树的竞争决策算法流程如下:

步骤1 初始化

最大的竞争步数=n;

pcount=3;dcount=1;lacount=1

//此三项分别为竞争力函数、决策函数

//和初始格局的个数

步骤2 竞争、决策及资源交换

for p=1 to pcount//竞争力函数个数循环

for d=1 to dcount//决策函数个数循环

for la=1 to lacount//初始格局个数循环

{ arrivew和tarrivew矩阵全为0;

计算每个顶点的sumdw[i,1],

sumdwj[i,1],sumdw[i,2],

sumdwj[i,2];

根据第p个竞争力函数计算power[i];

根据power[i]计算maxpowerid;

竞争步数=0;linecount=0;//图中边的个数

步骤2.1 本轮竞争阶段1:资源分配阶段

repeat

dot1=maxpowerid;

//要加入点的一个端点编号

dot2= sumdwj[dot1,1];

//要加入点的另一个端点编号

竞争步数=竞争步数+1;

linecount=linecount+1;

arrivew[dot1,dot2]=true;

arrivew[dot2,dot1]=true;//修改可达矩阵

for i=1 to n

//当在图上添加一条边(dot1,dot2)时

//更新tarrivew[ ]矩阵

if (tarrivew[i,dot1]=true) or (i=dot1)

then//与结点dot1关连的点i,

for j=1 to n

if (tarrivew[j,dot2]=true)

or (j=dot2) then

//与结点dot2关连的点j

if (i<>j) then

{ tarrivew[i,j]=true;

tarrivew[j,i]=true}

重新计算一部分结点的sumdw[i,k],sumdwj[i,k](这里只重新计算因为边(dot1, dot2)加入到图中而发生变化的点,其中1≤k≤2);

根据第p个竞争力函数重新计算一部分由于边(dot1,dot2)加入到图中而发生变化点的power[i];

根据决策函数计算maxpowerid;

until (linecount=n-1 or 竞争步数>=最大的竞争步数)

根据矩阵arrivew和矩阵W求解最小生成树的路径和各目标的权值。

应用Pareto解集过滤器进行Pareto解集更新。

步骤2.2 本轮竞争阶段2:资源交换阶段

对求得的生成树调用edgeexchange操作进行边交换;

使用全局经验指导方式计算每个保存解的距离及保留函数值;

对共享函数值最小的解调用edgeexchange操作进行边交换;

}

步骤3 输出保存的所有Pareto解

子程序:edgeexchange操作

对生成树中的每条边(i,j), 假如剥夺该边资源的话更新相关顶点墩的但递闭包集;

对一个不同于i,j的顶点k

①若arrivew[i,k]=false且tarrivew[j,k]=true,即边(i,k)不在生成树上,且顶点对j和k能够到达(包括直接到达和传递到达),则将边(i,j)替换为边(i,k);

②若arrivew[j,k]=false且tarrivew[i,k]=true,即边(j,k)不在生成树上,且顶点对i和k能够到达(包括直接到达和传递到达),则将边(i,j)替换为边(j,k);

计算交换后各目标的值,使用Pareto解集过滤器比较新解与保存的最优解的占优情况,替换当前Pareto解集或添加新的Pareto解。

不难估算,本算法的时间复杂度为O(3n3)。

3 数值算例

为了验证算法的有效性,采用Delphi 7.0在一台配置为Celeron(R) 2.4GHz的PC机上实现了该算法,并做了大量的数值测试。利用该算法求解文[5]中的5个顶点完全图,求得了其用枚举方法找到的全部12个Pareto最优解。下面给出其中的两个算例,随机生成顶点为9和20的完全图,权重矩阵在[1,100]服从均匀分布。

算例1 n=9,L=2,权值矩阵为对称矩阵故仅列出上三角部分。目标1的权值矩阵w1:

$w{}_1=\left[\begin{array}{ccccccccc}\infty & 10& 79& 41& 39& 54& 31& 46& 53\\ & \infty & 31& 11& 30& 6& 89& 9& 26\\ & & \infty & 86& 5& 84& 84& 26& 75\\ & & & \infty & 47& 46& 1& 17& 96\\ & & & & \infty & 28& 94& 71& 2\\ & & & & & \infty & 78& 42& 55\\ & & & & & & \infty & 3& 41\\ & & & & & & & \infty & 91\\ & & & & & & & & \infty \end{array}\right]$

目标2的权值矩阵w2:

$w{}_2=\left[\begin{array}{ccccccccc}\infty & 62& 76& 95& 50& 62& 10& 13& 37\\ & \infty & 89& 77& 65& 71& 70& 67& 17\\ & & \infty & 100& 95& 23& 10& 92& 79\\ & & & \infty & 7& 12& 11& 84& 23\\ & & & & \infty & 89& 39& 39& 38\\ & & & & & \infty & 84& 93& 62\\ & & & & & & \infty & 33& 88\\ & & & & & & & \infty & 68\\ & & & & & & & & \infty \end{array}\right]$

共求得28个Pareto非劣解,解的详情见表1。

算例2 n=20,L=2,权值矩阵限于篇幅不列出,共求得153个非劣解。其所求解集如图1所示。

通过测试发现,对于较小规模的问题,可以求出全部Pareto最优解,对于较大规模的问题,Pareto最优解分布比较稠密,而且形成了一个明显的Pareto前沿。

4 结束语

竞争决策算法是一种能广泛应用于求解各类组合优化难题的新型寻优算法,其通用性和实用性都比较强,在离散空间问题求解中,表现出其优越性。在处理多目标优化问题中,为了提高多目标优化问题Pareto解集的分布性以及多样性,计算Pareto解集中稀疏的解并在稀疏解附近进行领域搜索,整个算法操作简单,具有较好的通用性。试验结果表明,算法不仅能找到数量较多的Pareto解,且形成明显的Pareto前沿。

参考文献

[1]Ahuja R K,Magnanti T L,Orlin J B.Network flows:theory,algorithms,and applications[M].Beijing:Mechanical Industry Press,2005:510~536.

[2]Syslo M M,Deo N,Kowalik J S.Discreteoptimization algorithms[M].Englewood Cliffs,New Jersey:Prentice-Hall,Inc.,1983:370~373.

[3]Fernandez F R,Hinojosa M A,Puerto J.Multi-criteriaminimum cost spanning tree games[J].EuropeanJournal of Operational Research,2004,158(2):399~408.

[4]Chen G L,etal.The multi-criteria minimum spanningtree problem based genetic algorithm[J].InformationSciences,2007,177(22):5050~5063.

[5]雷德明,严新平.多目标智能优化算法[M].北京:科学出版社,2009.

[6]宁爱兵,马良.竞争决策算法及其在车辆路径问题中的应用[J].管理科学学报,2005,8(6):10~18.

[7]宁爱兵,马良.度约束最小生成树(DCMST)的竞争决策算法[J].系统工程学报,2005,20(6):630~634.

[8]宁爱兵,马良,熊小华.竞争决策算法原理及其应用[J].上海理工大学学报,2008,30(4):369~373.

[9]熊小华,郭文夷,宁爱兵.具有偏好选择的多目标TSP竞争决策算法[J].上海第二工业大学学报,2005,22(1):6~12.

最小决策算法 篇3

分类是数据挖掘和机器学习中的一个重要研究课题。它的目标是构造一个分类器, 对由属性集描述的实例指定适合的类标签。许多分类方法和技术用于构造分类模型, 例如决策树、贝叶斯方法以及支持向量机等。而决策树首先选择最大信息量的属性, 建立决策树的根结点, 然后再根据该属性的不同取值建立树的分枝结点。国际上最有影响和最早的决策树方法是ID3, 在此方法的基础上, 后人又发展了现在非常流行的C4.5、CART算法等, 本文将从一个新的思路对基于最小Gini指标的决策树分类算法进行进行设计与研究。

1 CART算法设计

CART是Classification and Regression Trees的简称。CART模型最早由Breiman等人提出并已在统计学领域普遍应用。它选择具有最小Gini系数值的属性作为测试属性, 当Gini值越小, 样本的纯净度越高, 划分效果也就越好。

假设S是用来划分的样本集合, 选择的划分方法必须使S的子集比它本身更“纯”, 可以用一个不纯函数x来评估各种划分方法的好坏。

如果用x (t) 表示任意叶节点t的不纯度, 那么x (t) 可以表示为:

其中, p (cit) 表示类ci在数据集t中的概率。

根据这个定义, 分支方案s的好坏度可以用不纯度的减小量△xs (t) 来定义。如果测试s将样本集合t分为n个子集t1, t2, …, tn, 那么分支好坏度可以定义为:

如果用Gini指标, 那么函数的定义为:

这时, 在测试s下Gini (s) 可以用不纯度的减小量△xs (t) 表示为:

如果某个测试s使Gini (s) 最大, 那么表示在s测试下不纯度的减小量最大, 则s就是最优的分支方案。

2 SLIQ和SPRINT算法设计

SLIQ分类器是一个基于决策树分类器算法的分类器, 它能够处理数值属性和分类属性, 同普通的决策树分类器不同的是, SLIQ不仅能对内存数据进行分类, 还能够将驻留在磁盘上的数据集分类, 也就是说它是可扩展的。同时, SLIQ还通过采用一定的算法, 改进决策树生成速度, 并且产生结构紧凑而精确的决策树。

在SLIQ算法中, 在树的构建阶段之前还有一个预处理阶段, 通过预处理, 对数值属性进行排序, 这样可以减少根据数值属性计算分支方案时的代价。这种预排序同构建阶段的宽度优先增长策略结合起来, 使SLIQ分类器能够分类驻留在磁盘上的数据集。在根据分类属性计算分支选择的时候, SLIQ使用了一种快速分割子集算法以确定分类属性的分支。在树的修剪阶段, SLIQ采用基于最小描述长度原理的修剪算法。这些技术的组合使得SLIQ能够扩展到大数据集上, 对有很多类、属性和样本的数据集, 具有很强的分类能力。

SLIQ算法不要求所有的训练数据都驻留在内存, 这对因为属性数目非常多而不能常驻内存的训练集非常有效。但是, SLIQ算法在运行过程中要频繁地访问和更新类表, 为了提高效率, 必须使类表驻留在内存中。类表的规模随着训练样本的个数的增加而线性增长, 这就限制了SLIQ的扩展能力:当没有足够的内存保存类表时, SLIQ就失效了。

而SPRINT算法是对SLIQ算法的改进, 它与SLIQ有很多相同的地方, 比如对数值属性的预排序, 选用gini指标作分支指标, 采用基于MDL原理的修剪算法等。但SPRINT消除了所有的内存限制, 即理论上它可以处理任何规模的训练数据集, 并且易于并行化, 即允许多处理器并行工作, 构造同一个模型。为了达到这个目的, SPRINT采用了与SLIQ不同的数据结构, 相应地, 在根据分支方案划分属性表的时候也使用了不同于SLIQ的策略。

3 SLIQ算法时间复杂性分析

SLIQ算法使用的改善程序运行效率策略, 主要有树的宽度优先增长策略和与之结合的数值属性的预排序技术, 以及使用贪心法计算分类属性的最优分割集。决策树算法的时间复杂性主要体现在树的构建阶段。不需要对数值属性进行重排序, 这是因为SLIQ采用的特殊的数据结构使得预排序成为可能, 而不需要在每个叶节点处对样本进行重排序。另外SLIQ并不考察分类属性的全部取值构成的集合S的所有子集, 而是采用一种贪心算法来计算分割子集S`, 贪心算法并不保证最终得到的子集是最优的, 但是经验证明它所得到的结果往往与最优结果相差无几。

将数据分解为属性表和类表、并对数值属性表进行排序的时间复杂性为O (nlogn) , 初始化根节点时的时间复杂性为O (1) 。

根据贪心算法, 可以得出计算最优分支方案时的时间复杂性Te (n) 在O (n) 。

构建SLIQ的决策树算法的时间复杂性T (n) 为:

4 SLIQ和SPRINT内存管理分析与性能比较

SLIQ分类器所采用的技术解决了对磁盘驻留大数据集的分类, 它可以使用其它的决策树分类算法来处理训练数据, 而精确度与所使用的算法相同, 但执行速度更快而且生成的树也更小。另外, SLIQ也不限制训练数据的数量及属性的数量。因此, 通过对其他分类方法处理不了的大数据集的分类, SLIQ实际上提高了分类精度。

SLIQ分类算法对建立一个快速的可扩展分类其存在的问题作了有益的探讨, 很好地解决了磁盘驻留数据太大以至于无法被内存容纳带来的问题。它没有采纳利用抽样或划分来获得可容纳与内存的小数据的处理方法, 而是直接在整个数据集上建立一棵决策树。然而, SLIQ仍要求每条记录的某些子段必须长期驻留于内存中。由于内存驻留数据的大小会随着输入记录数线形正比增大, 这显然限制了SLIQ分类训练的数据量。

而SPRINT作为一种可扩展的、可并行的归纳决策树, 它完全不受内存的限制, 而且处理速度很快, 且可扩展。该算法在设计中兼顾了并行处理, 允许多个处理器相互合作生成一致的模型。所给出的并行算法同样显示了极好的可扩展性。所有这些优点都使得该算法成为数据挖掘处理的理想工具。

我们以列表的方式简单地分析两种非常相似的决策树分类算法SPRINT与SLIQ的异同。

因为SLIQ和SPRINT的分支方案计算策略以及修剪算法完全相同, 所以二者的分类精度是完全一样的。实验表明, 在串行情况下, SLIQ算法的时间性能略优于SPRINT, 因为SLIQ不需要为新的属性表创建文件, 也不需要生成rid的散列表;在并行情况下, SPRINT算法要明显优于SLIQ的两种并行算法。

摘要：从一个新的思路对基于最小Gini指标的决策树分类算法进行了讨论。简单介绍了CART算法和Gini指标的定义, 并且对SLIQ和SPRINT决策树分类技术进行深入的分析。同时对SLIQ算法的时间复杂性和这两种算法的内存管理和性能方面进行了比较和分析。

关键词：分类,决策树,GINI指标

参考文献

[1]TOM M, MITCHELL.机器学习[M].北京:机械工业出版社, 2003.

[2]IAN H.WITTEN, EIBE FRANK.数据挖掘实用机器学习技术[M].北京:机械工业出版社, 2005.

[3]田盛丰, 黄厚宽.人工智能与知识工程[M].北京:中国铁道出版社, 1999.

[4]梁循.数据挖掘算法与应用[M].北京:北京大学出版社, 2006.

[5]MARY CAMPIONE et al.Java语言导学[M].北京:机械工业出版社, 2003.

[6]HAN J, KAMBER M.Data mining concepts and techniques[M].San Francisco:Morgan Kaufmann Publishers, 2001:185-219.

[7]USAMA M FAYYAD, GREGORY PIATETSDY-SHAPIRO et al.Advances in knowledge discovery and data mining[J].California:AAAI/MIT Press, 1996.

[8]FRIDMAN N, GEIGER D, GOLDSZMIDT M.Bayesian network classifiers[J].Machine Learning, 1997, 29 (2) :131-163.

[9]QUINLAN JR.Induction of decision trees.Machine Learning, 1986 (1) :81-106.

最小决策算法 篇4

层次分析法 (AHP) 是一种将定性因素与定量因素相结合的数学方法, 它已经成功地应用于经济、管理、社会等领域的战略研究与系统分析, 具有系统性、实用性、简洁性等优点, 所以层次分析法在那些还不能用绝对标度度量的复杂的经济社会系统中仍然拥有巨大的生命力。可是AHP方法在应用上还有很多缺陷, 其中有个最主要的缺点是专家矩阵不满足一致性检验的可能性[1], 随着经济社会的快速发展, 所面临的要解决问题也越来越复杂[2], 判断矩阵的阶数也随之越来越大, 一致性检验问题就是一个更加棘手的问题。

1.1 一致性检验面临的问题

在多属性决策问题中, 通常都涉及到经济、社会、人文等方面的因素, 这些因素中很大一部分没有标准的度量尺度, 在作比较、判断、评价、决策时这些因素的重要性、影响力或者优先程度往往难以量化[2]。人的主观选择和偏好会起到相当重要的作用, 这就给一般的数学方法解决问题带来了麻烦。随着问题越来越复杂, 层次也越来越多, 与此同时涉及的因素也越来越多, 这给层次分析法解决这类决策问题带来了很大的不可靠性, 因为层次分析法在解决此类问题时要求必须具有满意的一致性, 只有一致性通过检验, 得出的排序权重才会对实际决策问题提供有益的参考[3]。在目前的实际应用中, 1～9标度给出的判断矩阵通常很难达到一致。这样就会导致判断矩阵与实际的判断思维不一致的情况, 带来相对权重的计算失真。这给我们应用层次分析法解决多属性决策问题带来了挑战。虽然也出现了不少新的方法来解决这一问题, 例如群组决策特征根法 (GEM) [4]、标度区间分析法[5]等, 但这些方法随着面临的问题的越来越复杂, 效率很难得到保证。这就需要我们建立一个合理的模型来对判断矩阵进行调整以达到在满意一致性条件下的排序权重结果, 正确指导实际的决策行为。

1.2 基于PSO求解非线性模型算法

要用一般方法对一个较大的判断矩阵作通过一致性的调整并得到决策问题的权重是相当困难的, 甚至是难以实现的。所以为了更好地解决问题就有必要找到一种克服用特征根法求解带来的一致性检验难题的方法。本文通过构建一个非线性优化模型对专家判断矩阵进行调整并同时可以求解决策中的权重。该模型的求解有一定的困难, 鉴于此, 本文选用了PSO (粒子群算法) [6], 因为PSO算法求解非线性优化问题简单易行, 收敛速度较快, 鲁棒性较好。此模型可以有效地克服多属性决策问题中用AHP方法带来的难题, 本文最后通过在应急物流预案评价中的应用阐明该模型的有效性和合理性, 并对应急物流预案评价给出一个科学合理的参考权重。

2 一致性修正模型构建

2.1 一致性条件

在一个多属性决策的问题中, 先假设各属性的权值为wk (k=1～n) 。如果满足一致性, 那必然有:

$A=\left[\begin{array}{cccc}\frac{w{}_1}{w{}_1}& \frac{w{}_1}{w{}_2}& \cdots & \frac{w{}_1}{w{}_n}\\ \frac{w{}_2}{w{}_1}& \frac{w{}_2}{w{}_2}& \cdots & \frac{w{}_2}{w{}_n}\\ \cdots & \cdots & \cdots & \cdots \\ \frac{w{}_n}{w{}_1}& \frac{w{}_n}{w{}_2}& \cdots & \frac{w{}_n}{w{}_n}\end{array}\right](1)$

且${\displaystyle \sum _{i=1}^{n}w}{}_i=1$, 很显然A的各个列向量与权向量w仅仅相差一个比例因子。

再假设根据实际情况和专家经验得到的初始专家判断矩阵为:

$A^{\prime }=\left[\begin{array}{cccc}a{}_{11}& a{}_{12}& \cdots & a{}_{1n}\\ a{}_{21}& a{}_{22}& \cdots & a{}_{2n}\\ \cdots & \cdots & \cdots & \cdots \\ a{}_{n1}& a{}_{n2}& \cdots & a{}_{nn}\end{array}\right](2)$

一般地, 如果一个正互反矩阵满足一致性条件[7]:

$a{}_{ij}\cdot a{}_{jk}=a{}_{ik},i,j,k=1,2,\cdots ,n(3)$

则称其为完全一致性矩阵, 并且一定有:

$a{}_{ij}=\frac{w{}_i}{w{}_j}(4)$

2.2 基于一致性条件下的模型构建

那么当A′不是一致阵时, 权向量w的选择应使得aij与$\frac{w{}_i}{w{}_j}$相差尽量地小[8], 这样如果从拟合的角度看, 确定w可以化为如下的最小二乘问题:

$\min {\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n\left(a{}_{ij}-\frac{w{}_i}{w{}_j}\right)}}{}^2(5)$

假设调整后的矩阵为Xij=[xij]n×n, 并且xij∈[ (1-θ) aij, (1+θ) aij] (i, j=1～n) , 那么调整的目标是使下式取得最小:

$\begin{array}{l}\min {\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n\left(x{}_{ij}-\frac{w{}_i}{w{}_j}\right)}}{}^2(6)\\ \text{s}.\text{t}.w{}_i>0,{\displaystyle \sum _{i=1}^{n}w}{}_i=1\\ x{}_{ij}=\frac{1}{x{}_{ji}}\end{array}$

可是仅仅使式 (6) 达到最小还不满足在应用中的要求, 因为实际中不仅要让一致性达到满意, 还需要尊重专家的经验, 即判断矩阵的调整幅度要尽可能的小, 解决这一问题就必须使下式也尽可能地小:

$\begin{array}{l}\min {\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n(}}x{}_{ij}-a{}_{ij}){}^2(7)\\ \text{s}.\text{t}.x{}_{ij}\in [(1-\theta )a{}_{ij},(1+\theta )a{}_{ij}],i,j=1\sim n\\ x{}_{ij}=\frac{1}{x{}_{ji}}\end{array}$

由此可以得出这是一个双目标的模型, 在求解双目标的问题时, 我们很难找出一个唯一的最优解, 这就需要将求解多目标问题转化为求解单目标问题, 不过在应用中可加以权重进行调节, 由此可以将上述问题转化为:

$\begin{array}{l}\min Y={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n\left[\lambda {}_1(x{}_{ij}-a{}_{ij}){}^2+\lambda {}_2\left(x{}_{ij}-\frac{w{}_i}{w{}_j}\right){}^2\right]}}(8)\\ \text{s}.\text{t}.\lambda {}_1+\lambda {}_2=1‚\lambda {}_1,\lambda {}_2\ge 0；\\ w{}_i>0,{\displaystyle \sum _{i=1}^{n}w}{}_i=1\\ x{}_{ij}\in [(1-\theta )a{}_{ij},(1+\theta )a{}_{ij}],i,j=1\sim n\\ x{}_{ij}=\frac{1}{x{}_{ji}}\end{array}$

目标函数中的Y越小越好, ${\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n(}}x{}_{ij}-a{}_{ij}){}^2$是对专家判断矩阵调整的幅度, ${\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n\left(x{}_{ij}-\frac{w{}_i}{w{}_j}\right)}}{}^2$是对趋于一致性的调控幅度。λ1、λ2是调控因子, 看实际情况中对专家矩阵的遵循程度以及满意一致性的要求来进行赋值。Y值越小代表判断矩阵Xij是越接近一致性矩阵。θ是对专家判断矩阵的单个元素进行调整的幅度, 越小越好。

2.3 模型的求解方法

式 (8) 是一个非线性的优化问题, 对于一个n阶矩阵来说, 矩阵Xij中有n×n个优化变量, 但是只有n (n-1) /2个独立变量, 再加上n个权值优化变量, 一共有n (n+1) /2个独立变量, 对于这一非线性优化问题, 传统算法计算复杂, 且不能保证得到全局最优解。PSO算法是近年来求解非线性最优化问题的一个十分有效的启发式智能算法。利用PSO算法, 可以使式 (8) 的求解简单易行[9], 只要当Y小于一个阈值时, 就可以得到我们所需要的满意解, 至于这个Y值要满足什么样的条件时才可以通过一致性检验, 可以通过大量数值试验并与特征根法做比较, 然后得出一个适当的值。

最后将调整后的专家判断矩阵Xij与初始的专家判断矩阵A′进行比较, 检验调整后的专家判断矩阵是否在可接受的范围内, 当调整后的判断矩阵在这一范围内, 就可以接受这一判断矩阵, 并接受由这一判断矩阵所得到的排序权重向量w作为要求解的多属性决策问题的权值。否则说明初始判断矩阵就存在问题, 就有必要重新获取初始判断矩阵, 再调整上述优化问题中θ、λ1、λ2等参数和Y的阈值, 求得一个合理的排序权重。

3 标准PSO算法求解非线性优化问题

3.1 PSO算法数学描述

粒子群算法用无质量无体积的粒子作为个体, 每个粒子代表一个解, 由一个向量表示, 并为每个粒子规定简单的行为准则, 从而使整个粒子群呈现出复杂的特性, 可用来求解复杂的非线性优化问题。在一个n维搜索空间S∈Rn (可行解空间) 和由m个粒子组成的种群中, 第i个粒子的位置是用一个n维向量表示的, 即xi= (xi1, xi2, …, xin) , 每个粒子的位置都代表所求问题的一个候选解。这些解的好坏由适应度函数值决定, 适应度函数值越好则与之相关联的解就越好。粒子的飞行速度也是一个n维向量, 即vi= (vi1, vi2, vi3, …vin) 。第i个粒子飞行过程中所遇到的最好位置是S空间的一个点, 可以表示为pi= (pi1, pi2, …, pin) 。用g表示粒子群在前面飞行过程中获得的种群最好位置的粒子, pg= (pg1, pg2, …, pgn) 表示种群的最好粒子的位置。

标准粒子群算法粒子群中每个粒子飞行的速度和下一次的位置分别由式 (9) 与式 (10) 决定[9]:

$\begin{array}{l}\begin{array}{l}v{}_{id}(t+1)\\ =w{}^{*}v{}_{id}(t)+c{}_1\cdot rand1()\cdot (p{}_{id}(t)-x{}_{id}(t))\\ +c{}_2\cdot rand2()\cdot (p{}_{gd}(t)-x{}_{id}(t))\end{array}(9)\\ x{}_{id}(t+1)=x{}_{id}(t)+v{}_{id}(t+1)(10)\end{array}$

其中, d表示粒子的第d维 (1≤d≤D) , i=1, 2, …, m, c1是自身加速的常数, c2是全局加速的常数, c1和c2代表将每个粒子推向pi和pg位置加速项的权重, 根据经验, 将c1和c2取值为2, t表示此时的循环次数, rand1 () 和rand2 () 表示两个互相独立的随机产生一个[0, 1]之间实数的函数。w*为惯性权重, 文献[6]、[9]、[10]表明w*取值为0.9～1.2的固定值时, 粒子群算法能够获得较好的优化结果。w*可以使粒子保持运动惯性, 使其有扩展搜索空间的趋势。

3.2 PSO算法步骤

Step1 选取初始种群[11], 包括m个粒子, 每个粒子代表一个解, 是一个n (n+1) /2维的向量, 它们都被随机给定起始位置xi和速度vi;

Step2 计算每个粒子的适应值, 这个适应值函数可以就是目标函数;

Step3 对每个粒子, 将当前适应值与其自身经历过的最好适应值做比较, 如果好于后者, 则以当前的pi覆盖自身经历过的最好位置, 否则pi不变;

Step4 把这一循环中得到的种群最好适应值的位置与pg比较, 如果好于后者, 则重新记录pg的值, 否则pg不变;

Step5 利用进化公式 (9) 、 (10) 分别重新计算每个粒子的速度和位置;

Step6 如未达到终止条件 (通常为达到预先给定的最大迭代次数或足够好的适应值) , 则返回步骤Stept2, 达到终止条件则可以停止计算;

经过上述步骤求解构建的非线性优化模型, 即可以得到一个调整后的专家判断矩阵和一组权重向量, 这就有效地解决了层次分析法在解决多属性决策问题时专家判断矩阵不一致的难题, 并且可以方便地应用推广, 具有很强的实用性。

4 算法实例

4.1 建立多属性决策指标体系

以城市的物流应急预案为研究对象, 设计相关问卷, 并对相应的应急办公室、民政局救灾救济处、交通部门、救济物资生产商以及高校应急管理研究机构等单位进行调研, 并对收集的数据进行处理[12]。在专家经验的基础上, 遵循系统性、可比性、科学性和实用性原则的基础上, 得出了应急物流预案的诸多属性, 即评价指标体系。

政府物流应急预案评价初步指标体系中的属性包括时间、成本、有效性、合理性等, 综合整理如表1所示。

4.2 指标体系权重的确定

根据层次分析法最小二乘拟合模型求解权重的步骤, 首先构造专家判断矩阵, 由于篇幅限制, 在此直接给出经过处理后得到的专家判断矩阵:

$\left[\begin{array}{ccccccccccccccc}1& 4& 4& 2& 3& 5& 9& 2& 5& 9& 2& 1& 3& 4& 1\\ 1/4& 1& 1& 1/3& 1& 1& 1& 1/3& 2& 2& 1/2& 1/3& 1& 1& 1/3\\ 1/4& 1& 1& 1/3& 1/2& 1& 2& 1/2& 1& 2& 1/2& 1/2& 1/2& 1& 1/3\\ 1/2& 3& 3& 1& 2& 4& 7& 1& 4& 7& 1& 2& 1& 2& 1\\ 1/3& 1& 2& 1/2& 1& 2& 3& 1& 2& 3& 1/2& 1/2& 1& 2& 1/2\\ 1/5& 1& 1& 1/4& 1/2& 1& 1& 1/3& 1& 1& 1& 1/3& 1/4& 1/2& 1/4\\ 1/9& 1& 1/2& 1/7& 1/3& 1& 1& 1/4& 1& 1& 1/3& 1/6& 1/3& 1/2& 1/5\\ 1/2& 3& 2& 1& 1& 3& 4& 1& 3& 5& 1& 1& 2& 2& 1\\ 1/5& 1/2& 1& 1/4& 1/2& 1& 1& 1/3& 1& 1& 1/3& 1/5& 1/2& 1& 1/4\\ 1/9& 1/2& 1/2& 1/7& 1/3& 1& 1& 1/5& 1& 1& 1/4& 1/6& 1/3& 1/2& 1/5\\ 1/2& 2& 2& 1& 2& 1& 3& 1& 3& 4& 1& 1& 2& 2& 1\\ 1& 3& 2& 1/2& 2& 3& 6& 1& 5& 6& 1& 1& 3& 3& 1\\ 1/3& 1& 2& 1& 1& 4& 3& 1/2& 2& 3& 1/2& 1/3& 1& 2& 1/2\\ 1/4& 1& 1& 1/2& 1/2& 2& 2& 1/2& 1& 2& 1/2& 1/3& 1/2& 1& 1/3\\ 1& 3& 3& 1& 2& 4& 5& 1& 4& 5& 1& 1& 2& 3& 1\end{array}\right]$

得出了专家判断矩阵之后, 代入优化模型, 赋予λ1=0.4, λ2=0.6, θ=0.3;这样就得出了一个最小二乘拟合的优化模型。

然后根据粒子群算法的步骤, 先给定粒子群算法的参数设置:c1=c2=2, w*=1, 种群的规模m=40, 迭代次数为2000 (也可以用最小阈值替代迭代次数作为终止条件) 。随机给定初始位置与初始速度, 算法流程如图1所示。

用MATLAB 6.5软件编程求解可以得到调整后的专家判断矩阵与一组权重向量为:

由此可以得出应急预案评价指标体系的一个相对权重, 为决策问题提供一个科学的有价值的参考。

4.3 评价结果分析

将调整后的专家判断矩阵与原先的专家矩阵比较, 并由专家进行比较验证, 基本符合要求, 在可以接受的范围之内。用特征根法求解原专家判断矩阵得出的权重向量与一致性比率为0.0342, 权重指标为W=[0.1576, 0.0392, 0.0372, 0.1102, 0.0587, 0.0314, 0.0223, 0.0903, 0.0275, 0.0202, 0.0849, 0.1097, 0.0618, 0.0391, 0.1095], 再用特征根法求解调整后的专家判断矩阵得到的一致性比率为0.00012, 可以看出由此模型改进后的判断矩阵得到的一致性检验系数明显要优于原先的专家判断矩阵, 经比较可以得出基于PSO算法的层次分析法最小二乘模型能够很好的解决多属性决策中的权重计算问题, 并可以较快的对专家矩阵进行调整。

5 结语

本文构建了基于PSO算法的层次分析法最小二乘模型, 此方法可以快速有效地解决层次分析法传统解法的缺陷, 并且克服了传统算法效率不高的缺陷, 从而提高的求解结果的准确性与合理性, 对实际的多属性决策问题具有很好的实用性, 求解结果更加具有参考价值。最后通过一个应急物流方面的多属性决策问题对该方法进行检验, 实践证明该方法简明有效, 能够很好的解决实际问题。

目前最大的困难就是初始专家矩阵的获取比较困难, 该方法中调整后的判断矩阵任然需要与原专家判断矩阵进行比较, 给予取舍。所以初始专家矩阵的科学合理与否制约着该方法的应用效果, 但是同等情况下, 相比较其他方法, 该方法具有一定的先进性, 对应用层次分析法解决多属性问题具有较好的应用价值, 并且操作简单, 具有广泛的实用空间。

摘要：针对AHP分析法的一致性检验的不确定性, 建立了最小二乘拟合的非线性优化模型, 并结合使用PSO智能优化算法求解这一非线性优化问题, 使求得的结果更加合理, 得到的权重指标更加具有参考价值。在算法实例中运用上述模型对应急预案指标体系进行权重求解, 结果证明该模型简明有效, PSO算法能够很好地求解这一问题。

关键词：粒子群算法,非线性优化,AHP,多属性决策,一致性检验,应急预案

参考文献

[1]王莲芬, 许树柏.层次分析法引论[M].北京:中国人民大学出版社, 1990.

[2]王莲芬.层次分析法中排序权数的计算方法[J].系统工程理论与实践, 1987, 4 (2) :31~37.

[3]Saaty T L.The analytical hierarchy process[M].New York:McGraw-Hill Inc, 1980.

[4]洪源源, 邱菀华.AHP、GEM及其综合算法[J].中国管理科学, 2000, 8 (4) :36~42.

[5]AHP中判断矩阵的区间权重及其一致性检验[J].系统工程理论方法应用, 2004, 13 (6) :530~533.

[6]Shi Y H, et al.Parameter selection in particleswarm optimization[C]//Proceedings of the 7thAnnual Conference on Evolutionary Programming.Washington D C:Springer-Verlag, 1998:591~600.

[7]王国华, 梁.专家判断矩阵的一种调整方法[J].系统工程, 2001, 19 (4) :90~96.

[8]姜启源, 谢金星, 叶俊.数学模型[M].北京:高等教育出版社, 2003.

[9]Shi Y H, Eberhart R C.Empirical study of particleswarm optimization[C]//Proceedings of 1999 Con-gress on Evolutionary Computation.WashingtonDC:IEEE, 1999:1945~1949.

[10]EI-Gallad A, et al.Enhancing the particle swarmoptimizer via proper parameters selection[C]//Proceedings of the 2002 IEEE CanadianConference on Electrical&Computer Engineering.Winnipeg:IEEE, 2002:792~797.

[11]Kennedy J.The particle swarm:social adaptationof knowledge[C]//IEEE International Conferenceon Evolutionary Computation.Indianapolis:IEEE, 1997:303~308.

最小决策算法 篇5

一个好的决策支持系统的目标就是通过分析相应的源数据后, 为高层领导决策者提供必要的、准确的数据依据。实际的决策系统功能可以用于企业管理的方方面面, 具体目标包括如下几个方面[3]:

(1) 决策支持系统要有良好的交互界面, 一方面要能为用户展示决策时要参考的内容, 另一方面要具有很好的可操作性。

(2) 数据库生成, 对数据的处理要尽可能地融合, 提高数据质量以达到用户的要求。现实分析中, 数据质量不高一方面原因是由于数据库中的数据源各异;另一方面是数据生成的方式不尽相同, 生成这些数据出现不统一、不完整、不规范均为正常现象。在这种情况下, 为了避免结果的不统一和错误, 必须采取一定的技术处理, 实现对各类数据的有效归并。

(3) 决策支持, 在决策支持系统中运用数据库和多维线性分析技术, 可以实现货运量管理中货运量的大小与哪些数据相关联。

2 关键技术分析

目标系统所采用的数据挖掘方法主要涉及回归方法以及最小二乘法, 系统拟将两种技术有效地融合, 能在一定程度上解决传统决策支持系统中存在的不足, 这一节将对拟开发的原型系统中应用到最小二乘法及回归方法两种相关技术中的关键技术进行深入探讨。

2.1 最小二乘法

最小二乘法是一种数据优化技术, 又可称为最小平方法或曲线拟合法。对于寻找数据的最佳函数匹配问题, 最小二乘法是通过最小化误差的平方和来解决的, 可以简单地求得未知的数据, 并使得实际数据与这些分析数据之间误差的平方和达到最小[4]。最小二乘法误差分析的研究促进了线性模型理论的发展, 如今, 线性模型已经成为理论结果最丰富、应用最广泛的一类回归模型, 这也是本文采用两种技术融合研究决策支持系统的关键所在。

2.1.1 最小二乘法的原理

最小二乘法通过处理一组数据, 在这组数据中发现变量之间的依赖关系, 这种函数关系称为经验公式。

其基本原理为:成对等精度地测得一组数据xi, yi (i=1, 2, …, n) , 试图从中找到一条最佳的拟合曲线, 这条曲线满足在曲线上的各点的值与测量值差的平方和在所有拟合曲线中最小[5]。

设变量y与某一个变量x1, x2, …, xi之间存在如下依赖关系:y=f (x1, x2, …, xi;a0, a1…, an) , 其中a0, a1…, an是n+1个待定参数, 可以记为, 其中yi是测量值, y′i是由已求得的a0, a1…, an以及实验点 (xi1, xi2, …, xit;yi) (i=1, 2, …, m) 得出的函数值y′i=f (xi1, xi2, …, xit;a0, a1…, an) 。

在进行具体的应用实验中, 为了提高分析的准确性, 常常人为地进行多点测量, 其目的是使方程式个数大于特定参数的个数, 此时构成的方程组称为矛盾方程组, 可通过最小二乘法将其转化为正规方程组 (此时方程式的个数与待定参数的个数相等) 然后通过正规方程组求出a0, a1…, an。

2.1.2 常规最小二乘法形式分析

前述介绍最小二乘法又可称为曲线拟合, 即所求曲线不指望所作曲线完全通过所有的数据点, 只是希望能反映数据的基本趋势。

曲线拟合根据参数的多少可以分为一元线性拟合、多元线性拟合、多项式拟合、指数函数拟合四种[40], 下面重点分析一元线性拟合和多元线性拟合。

(1) 一元线性拟合。设变量y与x成线性关系y=a0+a1x, 已知m个实验数据点xi, yi (i=1, 2…, m) , 现求两个未知参数a0, a1。

令, 则a0, a1应满足, i=0, 1。

通过化简可得

从中得出解为:

(2) 多元线性拟合。设变量y与n个变量x1, x2, …, xn (n>1) 的内在联系是线性的, 即有下式成立, 设xi是第i次测量值, 对应的函数值为yi (i=1, 2…, m) , 则偏差平方和为, 为使得s取最小值得正规方程组如下:

通过该方程组可得下式:

正规方程式得出后, 只需将实验数据 (xij, yi) 代入即可得到a0, a1…, an的值。

2.2 回归分析法

回归分析法是数据挖掘最重要的挖掘工具之一, 针对当前网络技术中数据量的复杂性和多样性问题, 这种方法是在掌握大量观察数据的基础上, 利用数理统计方法建立相应变量 (因变量与自变量) 之间的回归关系函数表达式, 这种表达式又可称回归模型。

2.2.1 线性回归分析模型分类

线性回归分析模型一般有一元线性回归、可转为线性回归的曲线回归、多元线性回归三类[6], 下面分析探讨各种回归分析的建模过程。

(1) 一元线性回归模型。在线性回归中, 最简单的模型就是一元线性回归。我们对于x取定一组不完全相同的值x1, x2, …, xn, 设Y1, Y2, …, Yn分别是在x1, x2, …, xn处对Y的独立观察结果, 称 (x1, Y1) , (x2, Y2) , …, (xn, Yn) 是一个样本, 对应的样本值记为 (x1, y1) , (x2, y2) , …, (xn, yn) 。其总体模型可以表示为:Yi=β0+β1xi+εi。其中, εi是“噪音”变量, 是均值为0, 标准差为σ的正态分布随机变量。设b0和b1是对β0和β1的估计, 由统计学知识不难得出, 在xi处对Y的回归估计为, 残差 (误差) 为, 根据最小二乘法基本原理可知, 最好的回归直线是选择b0和b1使得总的误差 (残差平方和SSR) 最小:, 根据极值原理可推导出b0和b1的值。

(2) 可转化为线性回归的曲线回归模型。在实际中, 常会遇到更为复杂的回归问题, 而不仅仅是简单的一元线性回归, 但在某些情形下, 可以通过适当的变量转换, 将其化为一元线性回归来处理。

以下是几种常见的可转化为一元线性回归的模型 (其中α, β, σ2是与x无关的未知参数) :

第一种情形:Y=αeβx·ε, lnε~N (0, σ2) , 将本式两边取对数得lnY=lnα+βx+lnε, 令lnY=Y′, lnα=a, β=b, x=x′, lnε=ε′可转化为一元线性模型:Y′=a+bx′+ε′, ε′~N (0, σ2) ;

第二种情形:Y=αxβ·ε, lnε~N (0, σ2) , 将原式两边取对数得lnY=lnα+lnβx+lnε, 令lnY=Y′, lnα=a, β=b, lnx=x′, lnε=ε′, 可转化为一元线性模型:Y′=a+bx′+ε′, ε′~N (0, σ2) ;

第三种情形:Y=α+βh (x) +ε, ε~N (0, σ2) , h (x) 是x的已知函数, 令α=a, β=b, h (x) =x′, 可转化为一元线性模型:Y=a+bx′+ε, ε~N (0, σ2) 。

(3) 多元线性回归模型。与一元线性回归模型类似, 假设自变量为x1, x2, …, xp (p>1) , 对应的样本值记为 (x11, x21, …xp1, y1) , (x12, x22, …, xp2, y2) , …, (x1n, x2n, xpn, yn) 。则多元线性回归模型可表示为:Y=β0+β1x1+β2x2+…+βpxp+ε, ε~N (0, σ2) , 设b0, b1, …, bp是对β0, β1, …, βp的估计, 则在xi处对Y的回归估计为^yi=b0+b1x1i+…+bpxpi。

根据最小二乘法和极值原理可得:

此式为正规方程组, 为了求解的方便, 可将上式写成矩阵的形式, 为此, 引入矩阵:

因此上述方程组可以写成:XTXB=XTY, 其中XT为X的转置矩阵。假设X为可逆且 (XTX) -1存在, 可得

即可得回归方程:

2.2.2 线性回归预测步骤

下面探讨运用二元线性回归方程对目标数据源进行预测的步骤。

二元线性回归分析法, 可以称为一种预测法, 这种方法是指运用影响一个因变量的两个自变量进行回归分析。其关键技术是通过因变量和两个自变量的因果关系进行回归分析技术求解回归方程, 对回归方程进行验证得出预测值[7]。

二元线性回归方程分析预测法的回归方程为:, 此方程式中x1, x2为自变量, 为因变量, 即线性回归分析预测值;b0, b1, b2为待定回归方程参数。在预测模型的检验方法中, 若采用二元线性回归分析预测法, 则比一元线性回归预测要复杂得多。

二元线性回归分析步骤有6步, 分别是经济意义检验、回归标准差检验、相关系数检验、F检验、t检验、预测并确定置信区[8, 下面作简单分析。

(1) 经济意义检验:通过参数的符号来鉴别模型的真实性, 其依据是常规的经济规律, 而对于其他检验则要求根据统计分析的方法来判定数据是否能够通过检验。

(2) 回归标准差检验:回归标准差的计算公式通常为:

在 (8) 式中:yi为因变量第i (i=1, 2, 3, …, n) 期的观察值;为因变量第i期的估计值;n为观察期的个数;k为自由度, 为变量的个数 (包括因变量和自变量) 。

(3) 相关系数检验:这是一种指标检验方式, 由于在多元回归分析中需要计算两个系数:正相关和偏相关系数。所以, 这种系统检验是用于考核各参与变量间存在线性关系的紧密程度。

(4) 显著性检验, 也称F检验, 是用来检验当自变量作为一个整体来进行检验时, 对因变量的影响是否呈显性关系。F检验的计算公式为:

其中:yi为因变量的观察值;n为观察期的个数;k为自由度, 主要是指因变量和自变量的个数。

(5) 回归系统检验, 有些资料上称为t检验, 用于检验某个自变量对因变量的影响程度, 同时这种影响是否是没必要的, 所以要对自变量逐个检验其对因变量的影响。若某个自变量对因变量的影响不明显, 则应当将其从预测模型中去除, 逐步精华回归模型, 甚至可以考虑更换自变量, 其目的是用于提高预测精度。

(6) 预测并确定置信区间。在上述检验都通过以后, 接下来的工作就是将确定的两个自变量的值代入预测模型, 通过模型分析最终得到结果, 将这个结果用于预测分析。

3 结语

基于最小二乘法的决策支持系统建设, 主要是依据最小二乘与线性回归分析模型的有机结合, 用来对线性关系进行的最佳直线拟合, 通过模型的参数估计和显著性检验对其线性关系进行分析评价。本文介绍了传统的Web技术系统结构, 分析了其中存在的问题, 然后介绍了一种新的决策支持系统中应用到的关键技术, 重点探讨了最小二乘法以及线性回归方法, 并对二元线性回归方程预测的步骤作了详细阐述。

参考文献

[1]陈文伟.决策支持系统及其开发[M].北京:清华大学出版社, 2004.

[2]张新香.综合数据仓库的新型决策支持系统[J].现代计算机, 2004 (2) :65-66.

[3]姚艳雪.基于数据挖掘的进销存决策支持系统的研究与设计[D].哈尔滨:哈尔滨工程大学, 2011.

[4]孙凤林.偏最小二乘回归法非线性建模及其递推算法的研究[D].广州:华南理工大学, 2010.

[5]贾小勇, 徐传胜, 白欣.最小二乘法的创立及其思想方法[J].西北大学学报:自然科学版, 2006, 6 (3) :507-510.

[6]陆健.最小二乘法及其应用[J].中国西部科技, 2007 (12) :19-21.

[7]邵鸿翔.线性回归方法在数据挖掘中的应用和改进[J].统计与决策, 2012 (14) :76-80.

最简多元最小上界算法研究 篇6

1 最小上近似

令Q1,Q2为本体,C为Q1中概念,T是Q2中所有概念的集合且|T|=n。称T中i个概念的集合为T中i-概念集。Q1中概念C在T中可能有多个不同的上近似,它们的质量是不一样的。通过比较其查准率和查全率,可以找到C的最小上近似。可以用查询间的蕴涵关系[4,5]定义它们,并通过比较查全率和查准率说明它们确实是最佳的。

因为上近似的查全率都是1,所以只需比较它们的查准率。

定义1:令R1,R2是C在T中的上近似,如果⊆R1⊆2,则有precision(C,R1)≥precision(C,R2),所以R1的质量好于R2,称R1比R2更接近C。如果R是C在T中的一个上近似,而且对于任何C在T中的上近似Ri,都有C哿R哿Ri,则称R为C在T中的最小上近似。

2 概念的多元最小上界

定义2:令mlub(C,T)是T中概念析取的集合,如果满足:

1)对于∀Ĕ∈mlub(C,T),有C⊆Ĕ;

2)对于∀ĔT且C⊆Ň,都存在Ĕ∈mlub(C,T)满足Ĕ⊆Ň

则称mlub(C,T)是C在T中的多元最小上界。

下面约定概念C在Q2中的上近似也称为C在T中的上近似。令

由mlub(C,T)中的成员都蕴涵C,可知C⊆mua(C,T),所以mua(C,T)是C在T中的上近似。可以证明mua(C,T)是C在T中的最小上近似[6]。

定理1:对Q1中任何概念C,mua(C,T)是C在T中的最小上近似[7]。

定义3:令slub(C,T)是C在T中的多元最小上界,如果对于∀Ĕ∈slub(C,T)都有:

则称slub(C,T)为最简多元最小上界。

这三个条件去除了多元最小上界中的冗余:第一个条件说明slub(C,T)只包含蕴涵C的最小概念析取,第二、三个条件说明多个等价的概念析取中,slub(C,T)只保留包含概念最少的一个。

3 概念最简多元最小上界

3.1 算法思路

概念C在T中可能存在多个合法的最简多元最小上界,约定slub(C,T)是由算法1找到的最简多元最小上界。令概念集集合ps={E|E姚∈slub(C,T)},psi为ps中的i-概念集的集合。算法的目标就是在T中的所有概念集中找到ps的所有成员。

实际上,部分概念集存在这样的特性:它的所有超集都不在ps中,这些概念集组成的集合记为ns,即。因此只要证明一个概念集属于ns,那么它的所有超集就不再需要检查,即这些概念集一定不属于ps。这样可大大减少蕴涵检查的次数,比如只要证明概念集{D}属于ns,则需要进行检查的概念集就只剩下2n-1个,减少了一半。

图1算法采用迭代递增的过程生成概念集并测试它们是否属于ps。在第一步,处理1-概念集;在第二步,处理2-概念集;……。在第i步,生成的i-概念集的集合称为i-候选集,记作ci;然后测试ci中的成员,判断是否属于psi或ns。所有可能属于psi的放到一个集合中等待进一步验证,称为i-待验集,记作vi;一部分成员可以确定属于ns,从ci中删除

这些成员后构成的集合为ri。在第i+1步,ci+1由ri生成。算法提高效率的关键是在每一步最小化i-待验集和i-剩余集。在算法的每一步,i-待验集越小,最后的验证工作量越少;i-剩余集越小,由它生成的(i+1)-候选集就越小,相应地减少了后续步骤的搜索空间。

为了了解算法主框架的基本思想,下面分析如何从第一步过渡到第二步。令c1={{D}|D∈T}为第一步开始时生成的1-候选集。通过测试c1中的成员,可以得到关于它们属于ps1或ns的性质。一部分成员可能属于ps1,就把它们放到v1中;一部分成员可以确定属于ns,从c1中删除这些成员后构成的集合为r1。第二步的2-候选集c2只需包含所有1-子集都在r1中的2-概念集。因为如果一个2-概念集E,它存在1-子集不在r1中,由r1定义,则该1-子集必属于ns;由ns定义,E?ps2,且E∈ns。由此可知E本身及其超集都不可能属于ps,而算法的目标是求ps,所以E不需要放入c2中进行测试。以上讨论也适用于从第i步过渡到第i+1步。一般地,ci为所有(i-1)-子集都在ri-1中的i-概念集的集合。

3.2 函数find1()

在介绍第一步的测试函数find1()之前,先引入一个可以消去冗余概念的定理[8]。

定理2.如果有概念A,B T,满足A⊆B⊆C或A≡B,令T’=T-{A},则有C在T’中的最简多元最小上界也是C在T中的最简多元最小上界,即对求C在T中的最简多元最小上界来说,概念A是冗余的。

图2中的函数find1()通过测试c1中的成员找到v1,r1。

3.3 函数validate()

当生成和测试阶段完成后,有两种可能:一是已经找到了和C等价的查询并赋给了ps,这时无需验证,算法可以结束;如果没有找到和C等价的查询,由定理3,所有vi的并集v必然包含ps的所有成员。函数validate()根据定义9中最简多元最小上界的条件,除去v中的冗余成员,得到正确且完备的ps。验证函数validate()见图3。

3.4 算法分析

整个算法的主要运算是检查两个概念或概念析取之间的蕴涵关系,即执行check()函数。在第一步find1()中,要求出所有T中概念间蕴涵关系,并以此排序,然后从c1中求得v1和r1,时间复杂度为O(n2),其中n是T中概念总数。算法将T中所有冗余的等价概念,和C不相交的概念,C的子类,以及C的间接超类都从c1中删除,只有很少的概念留在r1中,不妨设其数量为m,有m远小于n。这样即使是在最坏情况下,之后寻找vi的时间复杂度也不会超过O(2m)。假设找到的待验概念集数目为l,validate()的最坏时间复杂度为O(l2);因为在算法中对vi有严格的定义,最终的l不会大。这样算法总的时间复杂度不会超过O(n2+2m+l2)。以上是最坏情况下的分析,实际上由于算法的每一步都尽可能的缩减搜索空间,通常只需检查其中的很少一部分。

由于算法1采用了迭代递增的过程,算法执行中随时可以停机并给出一个近似的结果。如仅执行一次迭代,得到的就是现有方法中使用的概念最小上界。随着迭代次数的增多,结果越来越接近概念的多元最小上界。通过这些近似结果求得的概念上近似也越来越接近概念的最小上近似。这个性质说明,即使在极少数较坏情况下,算法1也能够在可接受的时间内得到较好的近似结果。

4 结束语

通过把最小上近似转化为最简多元最小上界问题研究,可以大大提高最小上近似的质量和消除多元界中的冗余。基于本体的查询中除了概念,还有一个重要的关系元素[9]。因此要实现近似查询,除了求概念的近似,还需要求关系的近似,基于本体的关系查询是困难的,现有方法主要是把关系查询转化为概念查询,如果确保高质量转化还有待于研究。

参考文献

[1]袁洋,李善平.基于语义Web的本体映射方法综述[J].重庆:计算机科学,2004,31(5):5-8.

[2]张蓉,申德荣,于戈等.基于本体的Web服务查找和合成技术研究[J].北京:计算机集成制造系统,2003,9(10):921-925.

[3]高军,王腾蛟,杨冬青,等.基于Ontology的Web内容二阶段半自动提取方法[J].北京:计算机学报,2004,27(3):310-318.

[4]王洪伟,吴家春,蒋馥.基于本体模型的信息检索机制研究[J].北京:情报学报,2004,23(1):3-9.

[5]董慧.基于本体论和数字图书馆的信息检索[J].北京:情报学报,2003,22(6):648-652.

[6]Chang K C-C,Garcia-Molina H.Mind Your Vocabulary:Query Mapping across Heterogeneous Information Sources[C]//Proceedings of the1999ACM SIGMOD Conference.New York:ACM Press,1999.335–346.

[7]Preece A,Hui K,Gray P.Kraft:An Agent Architecture for Knowledge Fusion[J].International Journal of Cooperative Information Sys-tems,1999,10(1-2):171-195.

[8]Mena E,Illarramendi A,Kashyap V,et al.OBSERVER:An Approach for Query Processing in Global Information Systems based on Interoperation across Preexisting Ontologies[J].International journal on Distributed and Parallel Databases,2000,8(2):223-271.

一种新的最小生成树算法 篇7

最小生成树的应用相当广泛,其中一个典型应用就是基于最小生成树算法的网架规划[1,2]。目前,求最小生成树的算法已经相当成熟。常用的算法有Kruskal算法(又叫避圈法)、Prim算法(又叫边割法)、破圈法,但这三种算法需要判断圈或者构造边割。这些算法的优点是简单明了,通俗易懂;缺点是通常用来直接在图上作业[3,4,5,6,7,8,9,10,11];此外,还有基于Dijkstra算法的矩阵法、基于破圈法的完全关联矩阵法等;这些算法的优点是可用于求取大规模网络的最小生成树,缺点是计算过程复杂,效率低[12,13,14,15,16,17]。

本文结合最小生成树的定义及其性质,提出了一种基于权矩阵的最小生成树算法。将它用来求配电网架规划中的最小生成树,会使整个网架规划算法的计算效率得到明显的提高[18]。

1 算法思想与步骤

1.1 算法思想

设图G是一个连通的无向带权图。如果G0是一个包含G中所有顶点且无回路的连通子图,则G0是G的一棵生成树。若G有n个顶点,那么它的生成树有n个顶点,n-1条边。一个图可以有很多不同的生成树。其中,各条边权值之和最小的生成树即为最小生成树。

根据最小生成树的定义及性质可以得到如下几个结论(设图G1是图G的最小生成树):

(1)G1中的各条边权值之和最小。

(2)G1中有n个顶点n-1条边。

(3)G1必须是连通的且无回路。

因此,只要在一个连通带权图里找到一个同时满足上述三个条件的图,也就找到了该图的最小生成树。

图G中各条边的权值已知,由此可以形成一个n×n的权矩阵A。元素Aij表示第i个顶点到第j个顶点的边的权值。规定:若顶点i与顶点j不直接相连,则Aij=0。对角线元素Aii=0。

从理论上来讲,由与各顶点相连的最短边构成的生成树,其各边的权值和必定最小。所以,首先找出与各个顶点相连的权值最小的边。即在权矩阵A中按行找出非零最小元。若一行中同时出现两个非零最小元,表示离该点有两个最近点,即与该点相连的所有边里有两条权值最小的边,可任取其一。如果找出的所有非零最小元中同时出现Aij与Aji,表示离顶点i最近的是点j,而离点j最近的是点i。则任意去掉Aij、Aji中的一个。然后统计非零最小元的个数k。至此可以得到这样几个结论:(1)这k个非零最小元的脚标的并集必然包括了1,2,,n,即由这k个非零最小元分别对应的边构成的图有n个顶点;(2)k≦n-1;(3)构成的图没有回路。

证明(1):非零最小元是按行找出来的,所以理论上每行都有最小值。有可能非零最小元中同时出现了Aij与Aji,从而第j行的非零最小元Aji被去掉了,但其对应的Aij的脚标包括了j。故最后统计的k个非零最小元的脚标的并集必然包括了1,2,…,n,即由这些非零最小元分别对应的边构成的图有n个顶点。

证明(2):假设图G是如图1所示的含有4个顶点的连通图。

假设与各个顶点相连的最短边互不重合,即在形成的权矩阵中按行寻找到的非零最小元个数为4。我们假定与点1相连的所有边中a13最小;与点2相连的所有边中a23最小;与点3相连的所有边中a34最小;与点4相连的所有边中a41最小。从而有

a13

a23

a34

a41

根据aij=aji以及上述关系式中的(1B)(4B)(3B),可以得出a13

因为a13=a31,故上式不成立。所以在形成的权矩阵中按行寻找到的非零元个数不可能为4(更不可能比4大,因为矩阵是4行4列的),只能小于等于3。

同理,在有n个顶点的带权无向连通图中,它所对应的权矩阵按行搜索到的非零最小元个数k必然小于等于n-1。

证明(3):由于这k个非零最小元对应的k条边构成的图有n个顶点且k≦n-1,所以不会形成回路。

在前面我们已经知道了非零最小元的个数k,接下来判断k是否等于n-1。若k=n-1,则这k条边一定可以构成一个含有n个顶点的无回路连通图。而且这k个元素分别是权矩阵每行中值最小的,所以它们的和也最小。至此,由这k个非零最小元对应的k条边构成的图满足了n个顶点、n-1条边、权值和最小、连通且无回路的条件,此即为图G的最小生成树。

如果k﹤n-1,说明由这k条边构成的图没有连通。在图中,如果边aij(顶点i与顶点j之间的边)与amn(顶点m与顶点n之间的边)相连,那它们必然共用一个顶点,即脚标ij、mn必然有交集,否则这两条边就不连通。因此,要判断一条边或一个边的集合(这里把连通的几条边称为边的集合,一个边的集合至少包含两条边,如{a12,a13,a34}与图中其他边是否相连,只需看这条边的脚标或这个边集合中所有边的脚标的并集与图中其他边的脚标是否有交集。有交集,则说明连通;否则就没有连通。n-1条边可将n个顶点连通,所以根据n-1-k的值,可以判断还需几条边才能将k条边构成的图连通。由此也限定了我们应该找到与图中其他边未连通的边(或边的集合)的数目为n-1-k。

找到未连通的边aij(或边的集合)后,下一步就应设法找到能将边aij(或边的集合)与图中其他边连接起来并且权值最小的边。也就是在权矩阵里分别找出未连通边aij的脚标i和j对应的行的次非零最小元(前面已经找过每行的非零最小元了),然后进行比较,选取值较小的元素。该元素所对应的边就是我们要寻找的边。如果是边的集合没有连通,则先将这些边的脚标取并集,然后在权矩阵分别找出该并集中每个脚标所对应行的次非零最小元,比较,取值最小的元素。该元素所对应的边就是满足条件的边。这样,找到的边与前面k个非零最小元对应的k条边构成的图就是所求的最小生成树。

1.2 算法步骤

Step1:根据图的顶点数n及相应顶点间边的权值形成权矩阵A。其中主对角线元素Aii=0;若顶点i与顶点j不直接相连,Aij=0。若原图未对节点编号,则应先编号。

Step2:在权矩阵A中,按行搜索非零最小元。若某行中有几个非零最小元,则任取其一。记录各行的非零最小元及其脚标,并将权矩阵中对应的该元素赋值为0,其关于对角线对称的元素也应为0,得到新的权矩阵B(这样后面寻找行的次非零最小元就转换成寻找该行的非零最小元了)。比较找到的所有非零最小元,如果同时存在Aij、Aji,则去掉其中一个。统计此时非零最小元的个数k。

Step3:比较k与n-1的大小。若k=n-1,则由这k个元素对应的k条边构成的图即为所求最小生成树。结束。若k﹤n-1,说明这k条边构成的图没有连通,转Step4。

Step4:在剩下的边中寻找权值最小的(n-1-k)条边使k个非零最小元对应的k条边构成的图连通。

首先,判断第一个非零最小元的脚标与其余非零最小元的脚标是否有交集。若没有交集,则说明第一个非零最小元所对应的边与其他边没有连通。若有交集,则将与之有交集的所有元素的脚标和第一个非零最小元的脚标取并集,然后再判断此并集与剩余元素的脚标是否有交集。直到发现没有交集,从而找出未连通的边(或边的集合)。每找到一条未连通的边或一个未连通的边的集合,z+1(z的初值为0)。若z﹤n-1-k,在剩下的非零最小元里继续寻找未连通的边(或边的集合),直到z=n-1-k停止寻找。找到未连通的边(或边的集合)后,在权矩阵里分别找出该边的横、纵脚标所对应的行的非零最小元(如果是边的集合,可将所有边的脚标取并集,然后找出并集中每个元素对应的行的非零最小元),然后进行比较,选取值最小的元素(若出现两个及以上最小值,则任取其一)。此元素所对应的边即为要寻找的边。由寻找到的边与之前k个非零最小元对应的k条边构成的图即为所求的最小生成树。

以上即是本文提出的最小生成树算法步骤,下面将通过具体的例子来说明此算法的优越性。

2 应用举例

2.1 辐射网网架优化

用最小生成树算法对大庆油田电网进行网架优化,首要工作就是求最小生成树。大庆油田电网是全国最大的企业电网。为了简化计算,将大庆油田电网分区。分区原则是:选取220 k V变电站或者发电厂作为电源点,根据负荷的流向整理其他变电站,经过化简以及去除备用线后发现有10个电源点。从而将大庆油田电网分为10个区,即:春蕾变区,庆北变区,火炬变区,让变区,油田热电厂区,先锋变区,红旗变区,新华热电厂区,丰乐变区,宏伟热电厂区。现选择春蕾变区进行最小生成树研究。

春蕾变区包括1座220 k V春蕾变;3座110 k V变电所,分别是:丰收变,高家变,庆新变;15座35 k V变电所,分别是:喇三变,喇八变,喇十二变,喇十三变,喇十四变,喇十六变,喇Ⅲ-1变,喇水所用变,聚喇400变,北八变,北十二变,北十四变,北Ⅱ-1变,北Ⅱ-2变,北Ⅱ-4变。春蕾变区供电示意图如图2所示。现要设计合理的供电路线,使得110 k V变电所能将电能输送到各个35 k V变电所并且总的建设费用最小。图中顶点代表各级变电所,实线代表必须架设的线路,虚线代表可架设的线路,各条边的权值代表修建该线路所需的费用(如表1所示)。这样就构成了一个赋权连通图,从而将问题转化为求连通图的最小生成树。

首先,对各变电所进行编号:1-丰收变;2-高家变;3-庆新变;4-喇三变;5-喇八变;6-喇十二变;7-喇十三变;8-喇十四变;9-喇十六变;10-喇Ⅲ-1变;11-喇水所用变;12-聚喇400变;13-北八变;14-北十二变;15-北十四变;16-北Ⅱ-1变;17-北Ⅱ-2变;18-北Ⅱ-4变;19-春蕾变。

Step1:由赋权图形成权矩阵A。春蕾变-丰收变、春蕾变-高家变、春蕾变-庆新变三条线路必须架设,所以在形成权矩阵时暂时不考虑这三条线路,仅考虑110 k V变电所和35 k V变电所。

Step2:在权矩阵A中,按行搜索非零最小元。记录各行的非零最小元及其脚标。按行找到的非零最小元依次是:A1-15,A2-10,A3-7,A4-2,A5-3,A6-2,A7-3,A8-2,A9-2,A10-2,A11-2,A12-3,A13-1,A14-1,A15-1,A16-1,A17-1,A18-1。所有非零最小元中同时出现了A1-15和A15-1;A2-10和A10-2;A3-7和A7-3,所以去掉A15-1,A10-2和A7-3。剩下的非零最小元个数k=15。加上必须架设的春蕾变-丰收变、春蕾变-高家变、春蕾变-庆新变三条线路,k=18。

Step3:比较k与n-1的大小。因k=18,n-1=19-1=18,所以k=n-1。从而由这18个元素对应的18条边构成的图即为所求最小生成树。如图3所示。即按照图3所示架设线路可使总建设费用最低。最低费用为:143+90+68+27+27+41+16+85+55+46+15+9+17+75+27=824(万)。

从以上可知,应用本文的算法可以简单快速地求出最小生成树。由于大庆油田电网属于辐射网,故在求解过程中直接搜索权矩阵各行的非零最小元即可得到最小生成树。

2.2 网格状网架优化

某市区有8个住宅小区需要铺设电网网架,各个小区的位置及它们之间可修建的网架路线与费用如图4所示。现要设计一个网架铺设路线,要求电网能输送到各个小区并且修建的总费用为最小。图中顶点代表各小区,边代表可以修建的网架路线,边上的数字代表修建该网架所需的费用。这样就构成了一个赋权连通图,从而问题就转化为求赋权连通图的最小生成树。

Step1:由赋权图形成权矩阵A。

Step2:在权矩阵A中,按行搜索最小非零元。记录各行的最小非零元及其脚标。按行找到的非零最小元依次是:A12,A21,A32,A45,A54,A61,A78,A87。将A中这些元素所对应的值全部变为0。在找出的所有非零最小元中同时出现了A12和A21;A78和A87;A45和A54,故可去掉A21,A54和A87。剩下的最小非零元为A12,A32,A45,A61,A78;个数k=5。

Step3:比较k与n-1的大小。k=5,n-1=8-1=7,所以k﹤n-1。转Step4。

Step4:寻找权值最小的(n-1-k)条边使k个最小非零元对应的边构成的图连通。

n-1-k=8-1-5=2,说明还需要两条边才能使已有边构成的图连通。

第一个最小非零元A12的脚标12分别与A32,A61的脚标有交集,说明这三个元素对应的边是连通的。将脚标12,32,61取并集,再判断此并集与剩余元素A45、A78的脚标是否有交集。很明显,并集(1236)与45、78都没有交集,且45与78之间也没有交集。因此我们知道A45与A78所对应的边互不相连,并且和其他三条边也没有连通。在Step2中已经将A45和A54的值变为0了,所以只需在现有权矩阵A的第4行和第5行中分别找出一个非零最小元,二者取小,从而得到A56。在现有权矩阵A的第7行和第8行中分别找出一个非零最小元,二者取小。第7行和第8行的非零最小元A71=A86,可任取其一。这里取A86。A56和A86分别对应的边就是我们要寻找的两条边。

这样,由A12,A32,A45,A56,A61,A78,A86分别对应的边构成的图即为所求的最小生成树。如图5所示。

3 结束语