数据挖掘决策树算法ID3和C4.5

.决策树诊断树、数据挖掘、学习数据挖掘的工具-weka、 weka是以Java语言写成的完整软件资源Explorer，weka的主要图形用户界面weka存储数据的原始方法是ARFF或CSV文件格式ARFF文件由一系列实例组成，每个实例的属性值为(属性类别)、 天气数据outlooktemperaturehumidititywindyplay1sunnyhothighfalseno2sunnyhothightrueno3overcasthothighfalseyes4rainymildhighfalseyes rainyc toolnormalltrueno7overcastcoolnormaltrueyes8sunnymildhighfalseno9sunnycoolnormalseyes 10 rainymildnormaleyes 11 sunnymildnory dhi lightrueyes 13 overcasthotnormalseyes 14 rainymildhighetrueno，我们希望从上面的示例中找到一些规则以确定这些示例的类(理想情况下)(示例) if outlook=sunny and=highethenplay=noifhumidity=normanhenplay=yes的第二个规则错误事例样本的决策节点：1.最上面的节点称为根节点，是整个决策树的开始。 2 .每个节点的子节点数与决策树使用的算法有关。 (二叉树，多叉树)分支：决策过程是新的决策节点或叶：树的结尾，每个叶代表一个类别，根节点、叶节点、决策节点、叶节点、叶节点. 过程：1.决策树的生成：训练样本数据集(从历史数据中生成， 2 .从一定程度的综合数据分析处理的数据集)中删除决策树：使用新的样本数据集(测试数据集或训练数据删除集)验证决策树生成过程中发生的初步规则，进行影响预测准确性的删除。ID3决策树算法的记述、1 .试探性地选择配置在根节点上的属性，针对该属性的每个值生成分支。 2 .分割根节点上的数据集合，移动到子节点以生成本地树。 3 .计算该分区的信息增益。 4 .对其他属性重复此步骤。 5 .为用于分类的每个属性生成本地树。 6 .根据局部树的信息增益值，选择增益最大的属性的局部树。 7 .对选定本地树的每个子节点重复上述步骤1-6。 8 .这是一个递归过程。 如果节点上的所有实例都具有相同的类，则本地树将停止生长。根据选择属性，生成分支，计算信息增益，选择max增益，数据进一步分裂吗？ 分数p1、p2、pn的对数使用负号，结束，或算法的流程图、信息值(熵)、信息增益的概念、熵： entropy(p1、p2、pn)=-p1logp1-p2logp2-pnlogpn 熵是以比特为单位的，并且表达式中p1、p2、以及pn的和为1。 entropy(p，q，r)=entropy(p，q r ) (q-r ) *表示entropy (q/(q-r )，r/(q r ) )节点纯度的度量是必需的，其指示基于变量属性值将不纯节点的数据分割为子节点之后，纯度提高了多少。 最广泛使用的测量值是信息值(熵)。(以天气数据为例)、outlook属性桩、yesyesnononono、yesyesyes、yesyesnono、outlook、sunny、overcast、rainy、叶节点上的yes类和no类的实例数这些节点上的信息值分别是info ( 2，3 )=entropy (2/5，3/5 )=0. 971比特info ( 4，0 )=entropy (1，0 )=0比特info ( 3，2 )=entropy (3/5， 2/5 )=0. 971比特，计算这些叶节点的平均信息值，考虑到到达各节点的实例数： 5个实例到达第一节点和第三节点的4个实例到达第二节点时，平均信息值info ( 2，3 、 4，0 、3， 2 )=(5/14 ) *0. 971 (4/14 ) *0. 971=0. 693比特在创建初始树之前，根节点处的训练样本包括9个是和5个否，相应信息值： info ( 95 =0. 940比特，因此，桩为gain 5 )-info ( 2，3 、 4，0 、 3，2 )=0. 940-0.693=0. 247比特，模型，混合，窗口属性桩，是否是是是是否是，是否是，是否是cool分别是gain (temperature )=0. 029比特，yesyesyesnoono，yesyesyesyesno，humidity，high，normal，yesyesyesnoono，yesyesnono gain (humidity )=0. 152比特，gain (wind )=0. 048比特，若比较这些属性的信息增益的值，则信息增益最大的属性节点成为决策树的根节点。 选择outlook属性作为根节点是获得完整子节点的唯一方式，它比所有其他属性都具有更大的优势。 湿度属性是第二个最佳选择，因为它会生成几乎完整的大子节点。 根节点决定后，继续此递归进程。 outlook属性值为sunny时的节点可能会进一步分支： outlook、sunny、humidity、nonono、yes、high、normal、outlook、sunny、wind、yesnono、yesno、false、translate 是sunny，temperature，nono，yesno，yes，hot，mild，cool，他们的信息增益分别是gain (temperature )=0.571比特，gain (humidity )=0.971比特， 因此，在该节点选择湿度属性作为分裂属性，与此相伴的子节点不需要进一步分裂，叶节点是完整的子节点，因此该分支结束。 如果继续应用这种想法，关于天气数据的决策树将如下图所示生成。 理想的停止条件是所有的叶节点都是纯的，即包含在该叶节点中的实例具有相同的类别。 然而，无法实现这一理想状态，因为在训练集合中包含具有相同属性值的两个样本，但属于不同类别的样本无法阻止递归过程。 因此，停止条件仅限于数据不再分裂的情况。outlook、sunny，rainy，overcast，humidity，wind，yes，no，yes，yes，normal，high，false，true，天气数据决策树，ID3算法的不足和改进可能具有某些属性极端示例显示了一个标志代码属性，例如，如果数据集的属性对于每个实例都有不同的属性值。标志代码outlooktemperaturehumiditywindyplayasunnyhothighfalsenobsunnyhhhightrucovercasthothighfalseyesdrainymildhighfalseyeserai oolnormaltruenogovercastcoolnormaltrueyeshsunnymildhighfalsenoisuncolnormalseyesjrainymildnormaleyesksunnymildnormaltrueyeslove smovercasthotnormalseyesnrainymildhighetruneno.该属性值的类别所需的信息量是info ( 0，1 ) info ( 1，0 ).info ( 10 info ( 0，1 )=0比特，标志代码，和是，a，n，b，c，m，标志代码属性的信息增益，作为根节点处的信息量的gain (标志代码)=info ( 9，5 )=0. 940比特，比用其他属性得到的信息增益值大，标志代码是被选择为分裂属性的这一情况是不错的，但是在标志代码属性中当信息增益的测量方法被采用时，选择属性的可能属性值可能较大。 为了弥补这种缺陷，被称为增益率(gainratio )的主要校正量被广泛采用。 另外，由于上述例子的计数值都是1，因此分割后的消息的值在info(1，1 )=-1/14 xlog (1/14 ) x 14=logl4(3. 807比特)的分支越多时越大。 得分较高的属性其固有信息值较高。 增益率是通过将信息增益除以其固有信息而得到的。 示例：返回到先前天气数据桩：属性outlook将数据集合划分成三个子集，并且规模分别为5，4，5，因此不考虑子集中包括的类别，可以返回到内在信息值： info ( info ) 4 )在=1. 577比特处获得的outlook属性的增益可以如同(0.940-0.693)/1.577=0.157一样计算其它属性的桩的增益： temperature属性的增益可以是(0.940-0.911)/info(4， 6 4)=0.019humidity属性的增益率为(0. 940-0.788 )/info (7，7 )=0. 152 wind属性的增益率为(0.940-0.693)/1.577=0.049.上述四个属性中outlook属性的结果依然居第一位在此实例中，标志码属性的增益比(0.247 )尽管最高，但是增益被显着降低。 ID3算法的初始定义假设属性值为离散值，但实际环境中具有许多连续属性，并且不能按照特定的标准进行划分。 使用C4.5次的一系列处理顺序，将连续的属性分割为离散的属性，制作决策树。 C4.5对ID3进行了一系列改进。 这些改进包括处理数值属性、缺失值和后剪枝的方法。 (