案例推理变权值引擎模型及权值计算方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇案例推理变权值引擎模型及权值计算方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
收稿日期:2011-01-07;修回日期:2011-01-30。基金项目:国家863计划项目（2009AA01A346）。
作者简介:黄浙京（1984-），男，浙江黄岩人，硕士研究生，主要研究方向：通信与信息系统、计算机网络安全、人工智能； 汪斌强（1963-），男，安徽潜山人，教授，博士生导师，主要研究方向：宽带信息网络、高速路由器； 张建辉（1977-），男，河南叶县人，讲师，博士，主要研究方向：网络路由； 贺磊（1974-），男，河南郑州人，讲师，博士，主要研究方向：计算机网络安全。
文章编号:1001-9081（2011）07-1776-05doi:10.3724/SP.J.1087.2011.01776
（国家数字交换系统工程技术研究中心，郑州 450002）
（）
摘 要:在案例推理（CBR）案例检索匹配中，不同案例通常由不同的特征构成。而传统的CBR引擎模型大多采用固定权值模式，导致系统在匹配精度方面的性能很低。为了解决这一问题，提出一种CBR变权值引擎模型，在其特征权值计算模块引入人机互动机制，基于群决策法计算主观权值，提出依据专家个体和群体决策差异的主观权值调整方法；基于相似粗糙集法计算客观权值。最后设计了一种综合权值调整算法，通过计算主观权值和客观权值间的距离，判断两者的偏离程度，从而推导出权值调整系数，得到最终的权值调整结果。通过网络攻击案例进行的算例分析和仿真实验验证了上述方法的正确性和优越性。
关键词:案例推理；特征权值；群决策方法；相似粗糙集；综合权值
中图分类号:TP181文献标志码:A
Case-based reasoning engine model with
variable feature weights and its calculation method
HUANG Zhe-jing，WANG Bin-qiang，ZHANG Jian-hui，HE Lei
（National Digital Switch System Engineering and Technological Research and Development Center，Zhengzhou Henan 450002，China）
Abstract: In the Case-Based Reasoning （CBR） case retrieving and matching, different cases are usually composed by different features. But most of the traditional CBR engines adopt fixed feature weights mode, which makes matching rate of whole system very low. To solve this problem, this paper proposed a CBR engine model with variable feature weights and brought interactive mode into feature weights calculating module. It calculated subjective weight based on group decision-making theory and proposed an adjustment method which used differences between a single expert and his group. It used similarity rough set theory to calculate objective weight in order to make results calculating more objective and accurate. At last, it designed composite weights adjustment algorithm which calculated the distance between the subjective weight and objective weight, considered the deviation degree of those two weights, then deduced weights adjustment coefficient, and get the final weight adjustment results. The calculation example and simulation analysis of network attack cases validate the effectiveness of the proposed method and prove this method has much better performance in different performance indexes.
Key words: Case-Based Reasoning （CBR）; feature weight; group decision-making method; similarity rough set; synthetical weight
0 引言
在基于案例推理（Case-Based Reasoning，CBR）中，最重要的环节是案例的检索，即根据目标案例在案例库中寻找相似的案例进行匹配，找到与目标案例最为相似的案例。这一过程中最关键的技术是案例间的相似性度量。现有的大多数CBR模型，例如Aamodt-Plaza［2］和Leake［3］，都采用k-最近邻算法（k-Nearest Neighbor，k-NN）来计算案例间的相似度。该算法在与目标案例计算加权距离时所使用的案例特征权值都是相同的，这就为解决实际问题带来一定的误差。因为在求解实际问题时，各特征的权值直接影响着案例匹配的质量，例如在入侵检测系统中，不同攻击的案例通常由不同的特征构成，即使是相同的特征，在不同案例中的重要程度即权值也有差异。因此必须对上述问题进行两个方面的研究：1）提出一种CBR变权值引擎模型，去除k-NN算法中权值不变的设定，使各特征权值在相似度函数计算中设置为不同的值；2）设计出适合于上述模型的权值计算方法，以符合实际问题的求解，提高系统解决问题的精度。
在CBR引擎模型方面，文献［4］给出了一种经典的CBR引擎模型，但是在案例特征权值的存储和传递中依旧采用固定的特征权值工作结构，不能有效反映案例的实际特征。在特征权值计算方面，文献［5］采用主观赋权法，充分考虑了领域专家的意见，利用改进的层次分析法（Analytic Hierarchy Process,AHP），动态分析和综合各个专家的意见，构造案例特征相互重要程度的判断矩阵，最后确定各特征的权值，但是这种方法容易受到专家个人偏好影响，数据缺乏客观性。文献［6-8］采用客观赋权法，数据具有很强的客观性。其中，文献［6］采用粗糙集理论首先对连续的特征进行离散化，在得到的离散化定性特征表中进一步进行特征权值的约简与计算，但是数据离散化有可能造成特征信息丢失。文献［7］采用相似粗糙集的方法，将传统粗糙集理论中的不可分辨关系推广为相似关系，得到各特征间的相似差别矩阵，然后对该矩阵进行属性约简和权值计算以确定特征权值，从而避免了数据离散化造成的特征信息丢失。文献［8］认为在CBR案例比较中，时间因素对历史案例可采纳度有显著的影响，因此在利用粗糙集理论进行权值计算后，引入了基于时序的案例特征权值调整算法，对案例权值进行调整，但其在引入时序调整因子时没有给出一个严格的标准。上述这三种方法都完全依赖机器计算的模型，缺乏相应的灵活性，数据反映的值相对于网络现实情况有一定的滞后性，有时不能反映用户的意愿。
在CBR系统设计时，一方面要确保特征权值计算的客观性，另一方面又不能完全依赖机器的自学习。因此本文提出一种CBR变权值引擎模型，在其权值计算模块将特征权值分为主观权值和客观权值，基于群决策法计算主观权值，并提出依据专家个体和群体决策差异的调整方法；基于相似粗糙集法计算客观权值，使计算值更加客观、精确。最后，在二者的基础上设计了一种综合权值调整算法得到最终权值计算结果。
1 CBR变权值引擎模型
1.1 具有变权值计算功能的CBR引擎
CBR引擎是CBR系统的核心模块，它负责CBR系统案例搜索、案例比较、相似度计算、特征描述、特征权值计算等功能。可以说引擎性能的好坏直接影响了整个CBR系统案例推理的质量以及对实际问题求解的能力。
本文对传统的CBR引擎做了一定的改进，去掉k-NN算法中权值不变的假设，引入变权值概念。在具体实现时又将该模块分为主观权值计算模块和客观权值计算模块，以期计算结果更加符合实际，并能够对权值进行灵活地调整。改进后的模型如图1所示，其中黑色箭头表示调用关系；白色箭头表示创建关系。
图1 变权值CBR引擎结构
图1中，特征权值计算模块分为主观权值计算模块和客观权值计算模块。两个模块分别根据各自的算法计算出相应的主观和客观权值，然后送入综合权值计算模块的WeightCalculate对象中进行权值综合计算，得出最终的结果。
1.2 特征权值计算模块工作流程
CBR系统是一个具有一定推理能力和领域知识的专家系统，但专家系统学习新知识的能力和效率都要比人类专家低得多；另外，专家系统运行时和人类专家（用户）不仅是一种简单地使用与被使用的关系，而应是一种合作的关系。因此，本文在特征权值计算模块采用人机互动机制，从而使特征权值计算更加精确，并且发现和解决问题的效率得到。该模块具体工作流程如图2所示。
图2 特征权值计算模块工作流程
由图2可知，本模块在运行时有多个环节可将决定权交给用户，例如在某案例无历史特征权值时，若用户对该问题比较了解，可手动进行权值输入，无需进入专家系统计算模块以避免多次调用机器学习算法而给系统增加负荷。同时，如果用户在系统运行过程中需要调整权值，则可随时进入权值调整模块进行案例特征权值的调整。另外，客观权值是基于一系列历史数据得出的，可以在系统日常维护阶段就计算好存储在数据库中，而不必每次进行计算。若用户觉得其需要调整，则可以令其重新计算以更新其值。
2 特征权值计算方法
根据第1章提出的变权值引擎模型，本节给出适用于其中的特征权值计算方法。
2.1 主观权值计算
特征权值的主观计算可以看做一个多属性决策问题［9］，即通过专家解决具有多个属性（特征）的有限方案的排序和优选问题，所以可引入群决策理论。另外，专家决策的最终目的是各位专家的意见与群体的意见趋于一致，而以往的主观权值计算方法都忽略了专家个体与群体在决策结果上的差异。因此本文对此提出一定的修改，即通过计算专家个体决策结果与群体决策结果的偏离程度来对主观权值进行调整，使专家决策趋于一致，同时使计算结果合理。
设多属性群决策中专家群体为E{e1,e2,…，es}，专家ek的权重为λk,0≤λk≤1,1≤k≤s,λk由Delphi法确定，其值受专家的知识结构、学术水平、工作经验以及对问题的熟悉程度等方面的约束。设待评估的案例集为U{X1,X2,…,Xm}，各案例的特征属性集为Ci{ci1,ci2,…cin}，则cij表示第i个案例的第j个特征，其中1≤i≤m,1≤j≤n。
向s个专家进行的调查问卷为Q，其问卷形式为
（1）
其中：Qk表示E{e1,e2,…es}中第k个专家的调查问卷，qij表示第i个案例的第j个特征的得分，0≤qij≤10。
根据式（1）的问卷形式，得到第k个专家确定的第i个案例的第j个特征的得分为akij。由几何平均法综合上述s个专家的意见，得到s个专家确定的第i个案例的第j个特征的得分的平均值为
aij（∏sk1akij）1/s（2）
由此可得由s个专家确定的特征重要性的矩阵:
A（aij）m×n（3）
则第i个案例的第j个特征的初始主观特征权值为
ωij′； i1,2,…,m， j1,2,…n（4）
由式（4）可得各方案初始主观特征权值的向量为Wi′（ωi1′,ωi2′,…,ωin′）T，1≤i≤m。
专家群对于第i个案例的第j个特征的得分值为:
bij∑sk1akijλk（5）
定义1 专家ek对于第i个案例的第j个特征的个体打分结果与群体打分结果的偏差为:
θkijakij－bij（6）
式（6）表明专家个体和专家群体对同一个问题的认知度，其理想状态应是个体和群体打分结果趋于一致，即θkij的值为0。
定义2 专家ek对于第i个案例所有特征的个体打分结果与群体打分结果的偏差和为
pki∑nj1（θkij）2 （7）
由式（6）、（7）可得专家对于第i个案例的第j个特征个体打分结果与群体打分结果的偏差权值为:
μij∑sk1（θkij）2/∑sk1pki（8）
其中：μij表示专家对于某一案例的某特征认识的争议程度，μij越大说明专家们对于该特征分值的争议越大，相应的初始主观特征权值的调整幅度越大；反之，该特征初始主观特征权值调整的幅度越小或者不调整。
调整后的主观权值为:
ωijωij′－μij; i1,2,…,m， j1,2,…,n（9）
式（9）表明，对于值较大的μij，其对应的ωij′争议越大，公信度较低，应较大幅度地降低其权值比重，以待进一步调整；同理，对于值较小的μij，其对应的ωij′争议较小，公信力较高，其权值比重降低幅度也应越小或者不变。由式（9）可得各方案各特征的主观权值的向量为Wi（ωi1,ωi2,…,ωin）T（1≤i≤m）。
2.2 客观权值计算
本文在计算客观权值时采用相似粗糙集理论，以避免传统粗糙集方法［10］因数据的离散化处理而导致信息丢失现象，从而使计算结果具有很强的客观性。本文在此仅给出算法流程，具体步骤请参见文献［11］。
客观权值计算法流程如下所示：
输入：属性决策表，包含案例各特征属性的实际数值；
输出：案例集属性的特征权值。
第1步 计算相似度差别矩阵；
第2步 对相似差别矩阵进行属性约简；
第3步 求属性约简后的相似差别矩阵；
第4步 基于上述属性约简后的相似差别矩阵，求出其独立属性；
第5步 计算案例特征权值，并得到各方案客观特征权值的向量B（β1,β2,…,βm）T。
第2步中的特征属性约简算法可参见文献［12］。由上述算法步骤可以看出，虽然粗糙集理论计算的特征权值具有很强的客观性，但是其计算结果为某一问题案例集共有属性的特征权值，即不同案例间所有属性的权值结果相同。这不能适应不同案例具有各自特征权值的需求，因此还需结合主观权值来加以综合计算。
2.3 综合权值计算
当主观权值与客观权值分别由各自模块计算出后，送入图2所示的综合权值计算模块进行权值的综合计算与调整。以客观权值为依据，以主观权值为调整对象，通过计算二者间的距离，从而得到调整系数，最终得到综合权值。这样不仅充分利用了数据的客观性，而且使决策过程中人的作用得以凸显，有利于得到更加精确的结果。
定义3 设案例集U{X1,X2,…,Xm}，各方案共有的属性集为Ci{ci1,ci2,…cin}，cij表示第i个案例的第j个特征（1≤i≤m，1≤j≤n）。主观计算法的结果为Wi（ωi1,ωi2,…,ωin）T，客观计算法的结果为B（β1,β2,…,βm）T，则二者间的相似性度量为Si（si1,si2,…,sin）T，且有
sijβj/ωij, ωij>βi
ωij/βj, ωij≤βi （10）
以客观权值为参考，sij1表示主观和客观权值计算结果无差异；若ωij>βi表示主观计算与客观计算正相似；若ωij≤βi，表示主观和客观计算结果负相似。
定义4 设各特征权值的理想解为F*（f*1, f*2,…, f*n）T，且其相似度量为S*（s*1,s*2,…,s*n）T；设负理想解为F0（f 01, f 02,…, f 0n）T，且其相似度量为S0（s01,s02,…,s0n）T，则主和客观权值计算结果之间的相似差异与理想解的距离为
d*i（11）
同理可得其与负理想解的距离为
d0i（12）
由于本文假设以客观计算结果为参考，则可以设理想解F*B，则由式（9）得F*的相似度量为S*（1,1,…,1）T，由补集关系知负理想解F0的相似度量为S0（0,0,…,0）T，从而式（10）、（11）转化为
d*i（13）
同理可得其与负理想解的距离为
d0i（14）
将主观计算结果与理想解f*i的相似度记为τi，则其相对于负理想解的相似度为1－τi，则综合权值距离为:
D（τi）（τid*i）2 + ［（1-τi）d0i］2
τ2i∑nj0（sij-1）2 + （1-τi）2∑nj0s2ij（15）
令0，得到τi，也即主观和客观权值调整系数为
τi11+（16）
综合上述过程，调整系数τi是以客观权值为标准计算得出的，但由于客观权值是根据历史数据计算得到，虽然精确但具有滞后性；而主观权值虽然客观性较弱，却是由专家综合个人经验和现实情况得出的，更为贴近当前的真实情况。因此应以主观权值作为调整对象，以调整系数τi对其进行线性加权计算。从而得到调整后的权值为
ω*ijωijτi（17）
由式（17）可得各方案各特征的综合权值的向量为W*i（ω*i1,ω*i2,…,ω*in）T，1≤i≤m。
3 算例分析和仿真实验
3.1 算例分析
本文以KDD CUP 99中的数据集为例，结合Snort所给的规则集，并通过第2章介绍的算法进行算例分析。表1列出了几种常见的网络攻击和相应的属性特征，将每种攻击都看做一个案例，则能明显地看出相同的属性对于不同攻击的重要性不同，其中ICMP PING Attack1 与 ICMP PING Attack 2为攻击特征不相同的ICMP PING攻击。有的属性（例如内存消耗）对DoS Attack来说具有很大的标识作用，而对于其他攻击则可忽略不计。同时此表对于粗糙集算法来说亦可看成是属性决策表。
表2给出了根据2.1节介绍的方法计算的初始主观权值的结果，其中由5位专家进行决策，其权重分别为0.346，0.168，0.213，0.161，0.112。
表1 常见网络攻击案例集
表2 主观权值计算结果
根据2.2节介绍的相似粗糙集方法计算出的结果为：
B（0.2035,0,0.1861,0.2608,0.2083,0.4719,0.5376,0.3086,0.5651）T
其征c1按照其在流量中出现的统计平均值计算。
由上述结果可以看出，经过主观和客观计算的特征c2的权值都为0，说明该特征在案例比较时可以不予考虑。这也符合表1给出的实际数据，在表1中该类特征在不同案例之间的数据都相等，说明其不能起到区分不同类事物的作用,因此该类特征称为可约简特征。
以特征c1的主观和客观计算结果为例，进行综合权值的
计算。由式（9）可以得到c1的相似性度量S1为:
S1（0.7022,0.7731,0.6703,0.6919,0.6408,
0.7996）T
由式（12）,（13） 可得特征c1的相似性度量与理想解、负理想解的距离为d*10.7171，d021.7510，则根据式（15）得特征c1的调整系数τ10.8564。按照同样的方法可以得到其他特征的调整系数为:
τi（0.8564，0，0.9995，0.9677，0.9903，0.9932，
0.9991，0.8534，0.9613）T
最后，由式（16）得出调整后的权值见表3。
表3 综合计算后的权值结果
3.2 仿真实验
本文采用jCOLIBRI软件构造了一个基于CBR技术的网络入侵检测仿真平台。案例库采用XML的组织形式，而案例库中的案例是由Snort规则集转化而来。
案例匹配精度rc是衡量CBR系统的一个重要技术指标。它反映了CBR根据目标案例在案例库中寻找相似案例的能力，其计算公式如下：
rc（17）
其中：cnum表示案例库中案例的总数；ccorrect表示正确匹配案例的个数，0≤rc≤1。如图3显示了采用KDD CUP 99作为测试数据集,并用4组不同权值计算方法的精确度比较曲线。分别为：采用固定权值引擎模型（Fixed Feature Weight，FFW），单独采用主观权值计算法（Subjective Variable Weight，SVW），单独采用客观权值计算法（Objective Variable Weight，OVW），采用本文提出的综合权值计算法（Subjective/Objective Variable Weight，S/OVW）。
图3 不同权值计算方法的匹配精确度比较
由图3可以明显看出，采用变权值的三种方法的匹配精确度均比固定权值的高；单独采用主观权值计算法的精确度忽高忽低，显示出了主观计算方法的权值随专家认识的不同而有一定的波动，从而使案例匹配精度不是很稳定；单独采用客观权值计算法的精度很稳定，但总体精度仍不是很高；而采用综合变权值计算方法的精度明前高于前三种方法，且其随着案例个数的增加而提高，显示了该算法的优越性和强大的学习能力。
图4显示了4种方法在精确度、专业度、灵敏度三个指标上的柱状图，其中cnum100。精确度为如前所述的匹配精确度；专业度表示CBR系统解决问题的效果是否达到专家系统应具备的标准；灵敏度用来衡量系统对于未知问题（例如未知网络攻击）是否具有较强的发现能力。
图4 不同权值计算方法的三种指标的比较
由图4可以看出，FFW方法在综合性能方面远逊于采用变权值的三种算法。而变权值的三种方法中，S/OVW的专业性最好，OVW次之，表明S/OVW解决问题的效果最符合预期效果，而SVW虽然是各位领域专家评估的结果，但是各位专家对同一问题的认识有所偏差，因此造成了其最终结果并不如OVW依据客观数据给出的结果。就灵敏度来说，SVW的灵敏度最高，S/OVW次之，说明了主观计算在解决未知问题方面具有很高的效率，而单纯的机器学习算法OVW在这方面要略逊一筹，这也符合了客观实际，即人的认识总是超前于机器。
图3、图4是不同权值计算模型的CBR系统匹配精度的纵向比较，而图5则显示了不同的人工智能（Artificial Intelligence,AI）方法在匹配精度方面的横向比较。其中J48为一种决策树算法；RIDOR是一种基于规则的分类算法；CBR-VFW是基于本文提出的变权值CBR引擎模型。对于前两种AI方法，匹配精度理解为对于同一待解决问题，其在自己的规则库中搜索匹配的精度。综合图3和图5可以看出采用固定权值的CBR模型在精度方面甚至不如J48和RIDOR；而单独采用主观或者客观变权值方法的CBR模型性能略好于上述两种AI算法；而采用本文提出的权值计算方法的CBR模型性能则优于J48和RIDOR，说明其充分发挥了CBR的性能优势。
图5 不同人工智能方法的匹配精确度比较
4 结语
本文针对传统CBR引擎的缺点，一方面提出适用于CBR的变权值引擎模型并在特征权值模块引入人机互动机制，使CBR系统适应了不同案例不同特征的需要，更好地刻画和反映实际问题，使案例推理的结果更加精细。另一方面研究了适用于该引擎模型的特征权值计算方法，基于群决策理论，利用专家个体和群体决策结果的差异计算并调整主观权值，使主观权值结果更具合理性；基于相似粗糙集法计算客观权值，避免了数据在离散化时导致的信息丢失，使计算结果更加精确；最后通过对上述二者的综合计算与调整得出最后的特征权值。算例分析和仿真实验表明上述方法兼具了主观计算方法的灵活性和客观计算方法的准确性，并且通过不同技术指标证明了该方法的优越性。本文下一步的工作将会集中于CBR变权值引擎模型的可扩展性研究以及基于时间和空间等不同尺度的特征权值调整方法等方面。
参考文献:
［1］ KOLODNER J L. Case-based reasoning［M］. New York: Morgan Kaufmann，1993.