分类算法:决策树(C4.5)

C4.5是机器学习算法中的另一个分类决策树算法,它是基于ID3算法进行改进后的一种重要算法,相比于ID3算法,改进有如下几个要点: 用信息增益率来选择属性。ID3选择属性用的是子树的信息增益,这里可以用很多方法来定义信息,ID3使用的是熵(entropy, 熵是一种不纯度度量准则),也就是熵的变化值,而C4.5用的是信息增益率。 在决策树构造过程中进行剪枝,因为某些具有很少元素的结点可能会使构造的决策树过适应(Overfitting),如果不考虑这些结点可能会更好。 对非离散数据也能处理。 能够对不完整数据进行处理。 首先,说明一下如何计算信息增益率。 熟悉了ID3算法后,已经知道如何计算信息增益,计算公式如下所示(来自Wikipedia): 或者,用另一个更加直观容易理解的公式计算: 按照类标签对训练数据集D的属性集A进行划分,得到信息熵: 按照属性集A中每个属性进行划分,得到一组信息熵: 计算信息增益 然后计算信息增益,即前者对后者做差,得到属性集合A一组信息增益: 这样,信息增益就计算出来了。 计算信息增益率 下面看,计算信息增益率

分类算法:决策树(ID3)

决策树是以实例为基础的归纳学习算法。 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较,并根据不同的属性值从该结点向下分支,叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则,整个决策树就对应着一组析取表达式规则。 一棵决策树由以下3类结点构成: 根结点 内部结点(决策结点) 叶结点 其中,根结点和内部结点都对应着我们要进行分类的属性集中的一个属性,而叶结点是分类中的类标签的集合。如果一棵决策树构建起来,其分类精度满足我们的实际需要,我们就可以使用它来进行分类新的数据集。 这棵决策树就是我们根据已有的训练数据集训练出来的分类模型,可以通过使用测试数据集来对分类模型进行验证,经过调整模型直到达到我们所期望的分类精度,然后就可以使用该模型来预测实际应用中的新数据,对新的数据进行分类。 通过上面描述,我们已经能够感觉出,在构建决策树的过程中,如果选择其中的内部结点(决策结点),才能够使我们的决策树得到较高的分

使用libsvm进行分类预测

使用libsvm,首先需要将实际待分类的内容或数据(训练数据,或预测数据)进行量化,然后通过libsvm提供的功能实现分类和预测。下面介绍使用libsvm的基本步骤。 准备训练数据 数据格式: <label1> <index1>:<value11> <index2>:<value12>... <label2> <index1>:<value21> <index2>:<value22>... <label3> <index1>:<value31> <index2>:<value32>... ... 每一行,表示以已定义的类别标签,以及属于该标签的各个属性值,每个属性值以“属性索引编号:属性值”的格式。一行内容表示一个类别属性以及与该类别相关的各个属性的值。属性的值,一般可以表示为“该属性隶属于该类别的程度”,越大,表示该属性更能决定属性该类别。 上面的数据必须使用数字类型,例如类别,可以通过不同的整数来表示不同的类别。 准备的原始训练样本数据存放在文件raw_data.txt中,内容如下所示: 1 1:0.4599 2:0.8718 3:0.1987 2 1:0.9765 2:0.2398 3:0.3999 3 1:0.0988 2:0.2432 3:0