代价敏感属性中模拟退火算法和信息增益算法的比较

牛军霞

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

1 4个基本初等函数

1.1 测试代价敏感线性函数

线性函数的数学模型在现实生活中是最简单的，这个数学模型不仅操作简单，而且一些简单的科学决策也可以用此模型。假设用CN表示把健康人误诊为病人所付出的代价，用CP表示把病人误诊为健康人所付出的代价。其中，关于CN和CP的计算，如公式(1)和(2)。

CN(B，AF)(y，n)=β(y，n)×(AFtc(B) + |C|)

(1)

CP(B，AF)(n，y)=β(n，y)×AFtc(B)

(2)

对于任意的B⊆C，测试代价函数tc(B) = (a (Btc(a)，其中tc(a)是针对属性a的一个初始代价值。那么CN(B，AF)(y，n)表示把健康人误诊为病人所付出的代价值，其中β(n，y)是一个惩罚因子，它可以根据实际生活的不同情况，进行不断调整。

1.2 测试代价敏感指数函数

指数函数的数学模型在现实生活中应用也极其广泛，例如细胞分裂、病毒感染和计算电脑的流通速度等方面。在指数函数模型中，CN和CP如公式(3)和(4)。

CN(B，EF)(y，n)=β× ((1 + (EFtc(B))α+|C|)

(3)

CP(B，EF)(n，y)=β(n，y)×(1 + (EFtc(B))α

(4)

1.3 测试代价敏感幂函数

由于幂函数的数学模型，根据幂函数幂次的取值不同，对应的曲线不同，这更能与实际生活相联系。如果原测试代价为tc，平均增长率为β，则误分类代价用幂函数如公式(5)和(6)。

CN(B，PF)(y，n) = β(y，n)×( (PFtc(B) + |C|)

(5)

CP(B，PF)(n，y) = β(n，y)×PFtc(B)

(6)

1.4 测试代价敏感对数函数

由于对数函数其性质有多条，在实验部分，我们可以借助其性质，这样算法的复杂度将大大降低，进而可以提高算法的效率。这对处理大数据集将是一种行之有效的方法。CN和CP如公式(7)和(8)。

CN(B，LF)(y，n) = β(y，n)×((LFlog10tc(B) + |C|)

(7)

CP(B，LF)(n，y) = β(n，y)×LFlog10tc(B)

(8)

以上4个简单的初等函数的数学模型，将其引入算法流程中，将是一种新的尝试。通过一个实例来演示模拟退火算法的整个算法流程。

(1)第1阶段：初始化原子解。

在算法的初始阶段，模拟退火首先通过随机机制产生一批初始原子解，为了说明实验的整个流程，我们先假设初始有5个原子，其中用“1”表示选择的条件属性，反之用“0”。例如原子atom4表示选择属性子集为{a1，a4}。

(2)第2阶段：算法演化原子。

在算法的整个运行过程中，整个原子的演化过程的值代表属性子集的目标函数值。实验中可采用atom1′、atom2′、atom3′、atom4′以及atom5′来代表atom1、atom2、atom3、atom4和atom5的邻居解。实验中以atom1为例来演示模拟退火演化的过程。

当温度达到6时，atom1={a1，a2}，温度降到3时，atom1={a1，a2}，此时算法采用随机机制生成一个atom1的邻居解，设为{a1}，标为atom1′。由于atom1的目标函数值为fv(atom1) = 4.6。atom1′目标函数值为fv(atom1′)=3.00。由于fv(atom1) = 4.6>fv(atom1′) = 3.00，所以atom1′比atom1效果差，这时目标函数的差值为4.6-3=1.3。根据Metropolis准则，接受概率为P = exp(-1.3/(1+3)) =0.5<α，α是[0，1]之间产生的任意随机数，因此atom2′被随机概率接受。最后atom1′代替了atom1作为下一轮迭代的起点，直到温度达到0时这个过程才停止。

(3)第3阶段：根据测试代价的限制调解每个原子的大小。

当温度为6时，atom4= {a1，a4}，此时atom4邻居解为atom4′= {a1，a2，a4}。atom4′的测试代价c(atom4′) = $270> $100，这大于限制代价。因此需删除atom4′中的冗余属性，保证在预算之内。

(4)第4阶段：输出最小测试代价。

当退火过程终止时，选择总测试代价最小的原子。从实验中看出子集{a1，a2}的总代价是$90，其代价最小，因此原子解为属性子集。

2 比较模拟退火算法、信息增益算法和遗传算法的效果

本文的实验部分借助MATLAB软件，重点比较了模拟退火算法与信息增益启发式算法[1]以及遗传算法[2]的效果。在数据集Iris上，模拟退火算法与信息增益启发式算法以及遗传算法有相同的效果，在剩余的数据集上，模拟退火算法的实验效果比剩余2个算法的效果好。

由于正太分布更能说明实验的效果，因此在4个数据集上，也比较了3种算法的效果。通过实验的数据发现，无论在哪种分布上，模拟退火算法的效果都要高于其它2种算法。通过实验表明模拟退火算法在解决测试代价敏感属性选择问题方面具有很大的优势。不过在实验的部分，只比较了3种算法在3个分布上的效果，并没有比较3个算法在实验中的效率问题，所以在后续的工作中，实验会重点比较3个算法在3种分布上的效率问题。