摘 要：数据挖掘分类算法中基于信息理论的选择策略在选择分裂属性时，只考虑最优的分裂属性，忽略其他分裂属性。改进算法考虑了与最优分裂属性分裂效果相近的其他分裂属性，将其他分裂属性连同最优分裂属性一起作为待定分裂属性，并将待定分裂属性的每一个属性进行预分裂，判断这些待定分裂属性的好坏，从中选择最好的分裂属性。
关键词：数据挖掘；分类算法；信息论；选择策略
中图分类号：TP391.41
1 问题的描述
1.1 传统的基于信息理论的分类算法选择策略才在的问题
基于信息理论的选择策略基于信息论领域中的信息熵、信息增益来实现数据的分类划分。利用这种方法，分裂后的熵越小，该分裂方法就越好。
（1）该方法根据单属性判断分裂的好坏，即只能看到一次分裂之后的分裂效果，
（2）最佳分裂属性的熵，有时与次佳分裂属性十分相近。
2 改进的算法
改进的方法在选择分裂属性时，不直接选择最佳分裂属性进行分裂，而是考虑将最佳分裂属性与若干次佳分裂属性，考察这些属性分裂后的节点的再分裂效果的好坏，从中选择最优的分裂属性。
2.1 算法描述
具体做法是：
假设该节点含有n个可分裂属性，分别为A1，A2，A3…An，对应的熵为E1，E2，E3…En
（1）确定最佳分裂属性和次佳分裂属性
令最佳分裂属性为Abest次佳分裂属性Ebest，次佳分裂属性集合为Aless_best则：
Ebest=Min（E1，E2，E3…En）Ebest所对应的属性为Abest。次佳分裂属性：E1，E2，E3…En中与Ebest相近的熵所对应的属性。可以设定门限η，集合{Ei|Ei max=Max（E1，E2，E3…En），min=Min（E1，E2，E3…En），对于所有Ei= 这样，将（E1，E2，E3…En）映射到[0，1]的区间上，并且至少有一个值为0，至少有一个值为1.给定一个门限参数η，所有小于η的Ei所对应的属性就为最佳分裂属性和次佳分裂属性。 （2）所有最佳属性和次佳属性中选择分裂属性 假定所有最佳属性和次佳属性一共有k个，它们分别称为A1，A2，A3…Ak，选择过程如下： 数组E中存储第二次预分裂后的熵，数组sum中sum[i]存放第i个备选属性的分裂评价值。 for（l=0；l { 以Al对节点进行预分裂，令Ai的属性值个数为attribute_num，则分裂出attribute_num个子节点，分别为n1，n2，….nattribute_num，N为存储这attribute_num个节点的集合。 2.2 算法示例 若一数据集包含4个属性，它们分别为A1，A2，A3，A4；属性A1可取3个值，分别为A1.1，A1.2，A1.3；属性A2可取3个值，分别为A2.1，A2.2，A2.3；属性A3可取2个值，分别为A3.1，A3.2；属性A4可取2个值，分别为A4.1，A4.2。 指定参数η=0.2，Base=0.5；初始化变量value[1，2，3，4]=NaN；//NaN表示正无穷。 第一步：分别以A1，A2，A3，A4四个属性与分裂节点，得到的4个熵分别为：0.89，0.81，.026，0.31。 第二部，将A1，A2，A3，A4的分裂熵归一化后，分别为：1，0.873，0，0.080。 第三部，确定最佳属性和次佳属性，分别为A3，A4。 第四步，考察A3的分裂情况，A3可取A3.1和A3.2连个值。A3的两个可以取到的值将节点划分为2个子节点n1和n2，包含的样本个数分别为num1=575，num2=425。对n1分别以A1，A2，A4进行第二层预分裂，分裂后的熵E[1]，E[2]，E[3]，E[4]别为0.68，0.57.Nan，0.62，以Base=0.5加权求和，value[3]=（0.57*1+0.62*0.5+0.68*0.52）*num1/（num1+num2）=1.05*575/（575+425）=0.64，再对n2分别以A1，A2，A4进行第二层预分裂，分裂后的熵E[1]，E[2]，E[3]，E[4]别为0.72，0.31.Nan，0.82，以Base=0.5加权求和和，value[3]=value[3]+（0.31*1+0.72*0.5+0.82*0.52）*num1/（num1+num2）=0.64+0.88*425/（425+675）=0.64+0.37=1.01。 第五步，考察A4的分裂情况，A4可取2个值，分别为A4.1，A4.2，A4两个可以取到的值将节点划分为2个子节点n1和n2，包含的样本个数分别为num1=550，num2=450。对n1分别以A1，A2，A3进行第二层预分裂，分裂后的熵E[1]，E[2]，E[3]，E[4]别为0.52，0.38，0.67，NaN，以Base=0.5加权求和和，value[4]=（0.38*1+0.52*0.5+0.67*0.52）*num1/（num1+num2）=0.81*550/（550+450）=0.45，再对n2分别以A1，A2，A3进行第二层预分裂，分裂后的熵E[1]，E[2]，E[3]，E[4]别为0.47，0.55，0.35，NaN，以Base=0.5加权求和和，value[4]=value[4]+（0.25*1+0.47*0.5+0.55*0.52）*num1/（num1+num2）=0.45+0.62*450/（450+550）=0.73。 第六步，此时，数组value的值分别为NaN，NaN，1.01，0.73，选在最小值value[4]=0.73所对应的属性A4作为最终确定分裂属性对节点进行分裂，对分裂出的子节点重复1-5步进行分裂。 3 实验 利用UCIRepository中的Tic-Tac-ToeEndgame数据集来检测改进的算法[2]。Tic-Tac-Toe又称作是“一字棋”或者“井字游戏”，棋盘上有3*3个格子，每个格子可以放“O”，“X”或者空（“B”）。三个“O”或者三个“X”在一条直线上，游戏结束。目标属性有2个取值，“positive”代表游戏结束，“negative”代表游戏还没结束。属性有9个，分别对应着每一个格，取值有3个，分别为“O”，“X”和“B”。数据集中共有958条不重复的记录。 实验结论： （1）改进的算法在生成的决策树平均长度上比起原始的算法有提高。 （2）η相同时，Base取值越小，决策树的平均长度往往越小。 （3）η=0，Base=0实质上就是原始的算法。 （4）η太大会造成平均长度比起原始算法还要更大。 令函数f（i）表示第i层之前（包括第i层）叶子节点的样本数总和，则 4 结束语 本文提出的基于信息理论的选择策的改进算法，参数η的取值是本改进算法的关键之一，η太小，则依然过于注重最优分裂属性，而η太大又过于重视不够优良的次优分裂属性，合理选择η是本算法效果好坏的关键。如何自动的选择最合理的参数η以及参数Base在今后的研究中有待确定。 参考文献： [1]陈安，陈宁，周龙骧.数据挖掘技术及应用[M].北京：科学出版社，2007：111-119. [2]张洪刚，文刚，郭军.一种手写汉字识别结果可信度的测定方法及应用[J].计算机学报，2003，26（5）：636-638. 作者简介：令狐红英（1982-），女，贵州师范学院教师，讲师，工学硕士学位，主要研究方向为数据库技术与软件工程。 作者单位：贵州师范学院职业技术学院，贵阳 550018