代价敏感属性中对数加权算法和信息增益算法的比较

牛军霞

(陕西服装工程学院，陕西 咸阳 712000)

1 最小测试代价的属性选择

定义1(最小测试代价的属性选择问题)[1-2]设测试代价独立的决策系统为S，其中，相对约简所构成的集合为Red(S)∈S。对于∀R∈Red(S)，有c(R)=min{c(R′)|R′∈ Red(S)}，称R为最小测试代价属性约简(Minimal test cost reduct，MTR)，其中R(MTR(R)。

2 最小测试代价属性选择的对数加权算法

为了解决最小测试代价属性选择的问题，关于整个对数加权启发式算法的流程，本文采用了3个阶段加以说明。

算法的初始化阶段称之为第1阶段，其中的伪代码是下面算法框架中的第1行。

算法的核心阶段为第2阶段，其中的伪代码是算法框架的3到9行，在算法第2阶段中，我们可以发现在已经设定好的启发式函数基础上算法把最好的属性逐步添加给属性集B，直到B为超约简。关于整个算法的详细流程如下所示。

算法：最小测试代价的对数加权启发式算法

输入代价敏感决策系统：其中S=(U，C，D，V，I，c)

输出最后的属性约简集合：B使用的方法：对数加权法

(1)首先输入集合B=Ø。

(2) CA=C； //将原始属性集合赋值给集合CA。

(3)while ((POSB(D) ( POSC(D)) do//如果逐个添加的属性正域集合不等于整个属性的条件正域集合。

(4)for (α∈CA) do。

(5)Compute f(Bi，α，c(αi)，)。

(6) end for。

(9)end while //删除属性，主要根据信息熵的变化删除冗余属性。

(13)end if。

(14)end for。

(15)Return B。

算法的删除阶段为第3阶段，其中包含算法流程的10到15行，在删除阶段中的属性集B，算法在运行过程如果任意删除某一个属性α后，而整个算法在整体上能够有效地剔除多余的属性，以及不会带来代价的增长时候，正域就保持不变。

通过以上算法的3个阶段的运行，一个满足具有最小代价的属性子集最终就可以输出。

关于算法在实验的操作部分，几个名词性UCI数据集引入到本文的算法中：包括Tic-tac-toe，Mushroom，Voting和Zoo[2]。

算法评价指标

一个有效的评价指标才可以更有效地评价算法的效果。本文中采用文献[2]提出的评价指标。分别是最优因子(Finding optimal factor，FOF)、最大超出因子(Maximum exceeding factor，MEF)和平均超出因子(Average exceeding factor，AEF)来评价算法的效果。

3 分析算法的效果与效率

为了测试算法在整个实验中的效果，参数的取值需要在实验中不断调整。最优参数的取值往往可以通过不断竞争的方法来选择。当然在比较小的数据集为了提高算法的效率，人为设定的参数取值也是可行的。更进一步地，为了保证算法的可信度，在本篇论文中我们采用3种评价因子2-3]来比较算法的优劣。在Voting数据集上当δ=1时可观察到算法效果最佳，在Mushroom，Tic-tac-toe，Zoo数据集上，算法的效果不是很好。通过分析可知这与参数的设置有关，因为(参数的设置会影响到主函数。当δ=1，启发式函数为

f(B，αi，c(αi)，()=fe(B，αi)× (1 + lgc(αi)× lg101)=fe(B，αi))

通过启发式函数在整个实验中的运行分析可知，算法的主要函数考虑了属性的信息熵，测试代价在启发式函数并没有考虑，因此得到的是最小属性，不是最小测试代价属性。

4 比较已有的启发式算法

在本文中，我们引入了对数加权算法求解最小测试代价的属性选择问题，为了表明算法在实验中的有效性，本文中引入信息增益λ-weighted算法[4]与对数加权算法作比较。最终用数据表示两个算法在正态分布上竞争的结果，通过实验可知：算法在Voting数据集上，对数加权算法和增益λ-weighted算法效果相同。但是在Mushroom，Tic-tac-toe，Zoo数据集上，对数加权算法的效果都比信息增益λ-weighted算法的效果好。通过实验分析可知，数据集越大对数加权算法的效果比信息增益λ-weighted算法更显著。比如对数加权算法分别在Uniform和Normal上与信息增益λ-weighted算法在4个数据集上的优劣的比较，通过实验分析可知，对数加权算法比信息增益λ-weighted算法的提升率都高，提升率在个别数据集上可以达到57%和2%，通过以上分析可知，对数加权算法比信息增益λ-weighted算法在整个数据集上述更有效。

以上在算法的比较中，只比较了FOF的效果，并没有涉及MEF和AEF的比较，在后续的文章中，会进一步比较信息增益λ-weighted算法和对数加权算法的MEF和AEF。