分类算法中基于信息理论的选择策略改进

《分类算法中基于信息理论的选择策略改进》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分类算法中基于信息理论的选择策略改进摘要：数据挖掘分类算法屮基于信息理论的选择策略在选择分裂属性时，只考虑最优的分裂属性，忽略其他分裂属性。改进算法考虑了与最优分裂属性分裂效果相近的其他分裂属性，将其他分裂属性连同最优分裂属性一起作为待定分裂属性，并将待定分裂属性的每一个属性进行预分裂，判断这些待定分裂属性的好坏，从中选择最好的分裂属性。关键词：数据挖掘；分类算法；信息论；选择策略中图分类号:TP391.411问题的描述1.1传统的基于信息理论的分类算法选择策略才在的问题基于信息理论的选择策略基于信息论领域中的信息爛、信息增益来实现数据的分类划分。利用这种方法，分裂后的

2、爛越小，该分裂方法就越好。（1）该方法根据单属性判断分裂的好坏，即只能看到一次分裂Z后的分裂效果，（2）最佳分裂属性的爛，有时与次佳分裂属性十分相近。2改进的算法改进的方法在选择分裂属性时，不直接选择最佳分裂属性进行分裂，而是考虑将最佳分裂属性与若丁次佳分裂属性，考察这些属性分裂后的节点的再分裂效果的好坏，从中选择最优的分裂属性。2.1算法描述具体做法是：假设该节点含有n个可分裂属性，分别为Al,A2,A3・・・An,对应的爛为El,E2,E3・・・En(1)确定最佳分裂属性和次佳分裂属性令最住分裂属性为Abest次住分裂属性Ebest,次佳分裂属性集合为Aless_b

3、est则:Ebest二Min(El,E2,E3・・・En)Ebest所对应的属性为Abest。次佳分裂属性:El,E2,E3・・・En中与Ebcst相近的爛所对应的属性。可以设定门限几，集合｛Ei

4、Ei

5、,E2,E3・・・En)映射到［0,1］的区间上，并且至少有一个值为0,至少有一个值为1.给定一个门限参数n,所有小于H的Ei所对应的属性就为最佳分裂属性和次佳分裂属性。(2)所冇最佳属性和次佳属性屮选择分裂属性假定所有最佳属性和次佳属性一共有k个，它们分别称为Al,A2,A3…Ak,选择过程如下：数组E中存储第二次预分裂后的爛，数组sum中sum［i］存放第i个备选属性的分裂评价值。for(1=0；l

6、butenum,N为存储这attribute_num个节点的集合。2.2算法示例若一数据集包含4个属性，它们分别为Al,A2,A3,A4；属性A1可取3个值，分别为Al.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[l,2,3,4]=NaN；//NaN表示正无穷。第一步：分别以Al,A2,A3,A4四个属性与分裂节点，得到的4个嫡分别为：0.89,0.81,.026,0.31o第二部，将

7、Al,A2,A3,A4的分裂燔归一化后，分别为：1,0.873,0,0.080o第三部，确定最佳属性和次佳属性，分别为A3,A4O第四步，考察A3的分裂情况，A3可取A3.1和A3.2连个值。A3的两个可以取到的值将节点划分为2个子节点nl和n2,包含的样本个数分别为numl=575,num2=425o对nl分别以Al,A2,A4进行笫二层预分裂，分裂后的爛E[l],E[2],E[3],E⑷别为0.68,0.57.Nan,0.62,以Base二0・5加权求和，value[3]=(0.57*1+0.62*0.5+0.68*0.52)*numl/(numl+num2)二1.

8、05*575/(575+425)=0.64,再对n2分别以Al,A2,A4进行第二层预分裂，分裂后的爛E[l],E⑵,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)*numl/(numl+num2)=0.64+0.88*425/(425+675)=0.64+0.37=1.01o第五步，考察A4的分裂情况，A4可取2个值，分别为A4.1,A4.2,A4两个可以取到的值将节点划分为2个子节点nl和n2,包含的样