数据挖掘课程设计报告.docx
ID3 算法的改进摘要：本文基于 ID3 算法的原有思路，再把属性的重要性程度值纳入了属性选择的度量标准中，以期获得更适合实际应用的分类划分结果。一、ID3 算法的缺乏ID3 算法使用信息增益作为属性选择度量值，其倾向于选择具有大量值的属性，但没有考虑到属性在实际应用分类中的重要程度，由于依靠取信息熵最大的属性在现实状况中却并不那么重要，因此可能会得到不太有用的划分结果。举个简洁的例子，在对淘宝用户行为进展分析时，尽管依据用户 ID 可以得到最大的信息增益，但是这并不符合分析的要求，由于，我们需要得到的是用户的购置行为，在分析中，我们会更多的考虑用户曾经扫瞄过的商品或者已经购置了的商品。在这个情景中，依据信息熵来度量属性的选择就不太合理，所以需要对其进展改进。二、改进思路本次设计中在属性选择上参加了属性重要程度值：由于承受信息增益的方法会倾向于选择拥有较多可能属性值的属性，为了弥补这一缺陷，所以在选择时就参加了属性的重要程度值。属性重要程度值考虑了属性在分裂数据中所处的地 位。在处理数据的时候，会首先依据阅历或需要推断出数据集合里面的属性值的重要程度，例如，在上面淘宝用户行为分析中，我们可能会人为的赐予属性“扫瞄过的商品”最高重要程度值：0.8，而给属性“用户 ID”较低的重要程度值： 0.2。在明确了属性重要程度值以后，我们会在计算每个属性信息增益后将信息增益与属性重要程度值相乘，由此来推断最终属性的选择。对于 ID3 算法的其他内容不做更改。三、具体实现以课本数据挖掘中 193 页的例 6-1 为例。例 6-1 中各属性的重要程度值即权值未知，我们可先分别假设属性age 的重要程度值为 0.1，属性income 的重要程度值为 0.6，属性 student 的重要程度值为 0.2，属性 credit_rating 的重要程度值为 0.1。在引入属性重要程度值以前，每个属性的信息增益为：Gain(age)=0.246 ，Gain(income)=0.029 ，Gain(student)=0.151 ， Gain(credit_rating)=0.048。在引入属性重要程度值以后，信息增益*属性重要程度值分别为：0.246*0.1=0.02460.029*0.6=0.01740.151*0.2=0.03020.048*0.1=0.0048此时，决策树的属性分布就会和之前的不同， income 属性会成为决策树的根节点。由此可见，属性的重要程度值会对决策属性的选择有着重要影响。四、改进算法由于仅仅只是把属性的重要程度值纳入到决策属性的选择中，所以原 ID3 算 法的大局部代码都是一样的， 唯一不同的是： 转变了 makeTree 方法的impurityReduce 值。在程序中添加了属性重要程度值数组 priority，属性对应的重要程度值依次为priorityi,此处为了便利，其值直接承受Math.random随机生成， 然后将其与 computeEntropyReduce(data,data.attribute(i) 相乘， 记得到的impurityReduce 值，从而影响了决策属性的选择。更改代码局部用淡蓝色标记。private void makeTree(Instances data) throws Exception2if (data.numInstances = 0)/假设没有m_Attribute = null;m_Instances = new Instances(data); return;/ Compute attribute with maximum split value. double impurityReduce = 0;double maxValue = 0; int maxIndex = -1;int h=data.numAttributes; double priority=new doubleh; for (int i = 0; i < h; i+)priorityi=Math.random; if (i = data.classIndex)continue;impurityReduce=computeEntropyReduce(data,data.attribute(i)*priorityi;if (impurityReduce > maxValue)maxValue = impurityReduce; maxIndex = i;3/ Make leaf if information gain is zero, otherwise create successors. if (Utils.eq(maxValue, 0)m_Attribute = null;m_Instances = new Instances(data); return; elsem_Attribute = data.attribute(maxIndex);Instances splitData = splitData(data, m_Attribute); m_Successors = new MyID3m_Attribute.numValues; for (int j = 0; j < m_Attribute.numValues; j+)m_Successorsj = new MyID3; m_Successorsj.makeTree(splitDataj);验证 MyID3 算法的结果如以下图：4图 1 改进后5五、结论图 2 改进前试验证明，将属性的重要程度值纳入属性度量选择的过程中有助于弥补承受信息增益的方法会倾向于选择拥有较多可能属性值的属性这一缺陷，使得属性的选择更加合理，更加贴近实际应用。6
