基于WEKA平台的决策树算法设计与实现

发布时间：2017-01-01 17:39

本文关键词：基于WEKA平台的决策树算法设计与实现，由笔耕文化传播整理发布。

硕士学位论文第二章ＷＥＫＡ平台下的决策树算法性能；分类的核心过程就是为数据集构造一个合适的分类器，；（１）预测准确度预测准确度是用得最多的一种比较尺；型分类任务，目前公认的方法是ｌＯ遍分层交叉验证法；（２）计算复杂度计算复杂度依赖于具体的实现细节和；掘中，由于操作对象是巨量的数据库，因此空间和时间；（３）模型描述的简洁度对于描述型的分类任务，模型；例如，采用

硕士学位论文第二章ＷＥＫＡ平台下的决策树算法性能分析测，这样就可以从历史数据记录中自动推导出给定数据的推广描述，从而能对未来数据进行预测。

分类的核心过程就是为数据集构造一个合适的分类器，分类器能把数据库中数据项映射到某一个给定的类别。构造分类器需要对输入数据进行分析，一般用一个训练样本数据集作为输入数据，训练集（ＴｒａｉｎｉｎｇＳｅｔ）是一条条的数据库记录（Ｒｅｃｏｒｄ）或元组构成的，每一条记录包含若干条属性（Ａｔｔｒｉｂｕｔｅ），组成一个特征向量ｔ．训练集的每条记录还有一个特定的类别标记（ＣｌａｓｓＬａｂｅｌ）与之对应。该类别标记是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：（ｖｌ，ｖ２…．，ｒｅ；ｃ）。在这里ｖｉ表示字段值，ｃ表示类别【ｌｓｌ。目前构造分类器的方法主要有决策树法、神经网络方法、近邻学习，贝叶斯法、基于事例的学习等方法等。这些不同的分类器各有优缺点，有三种分类器评价或比较尺度“９１：

（１）预测准确度预测准确度是用得最多的一种比较尺度，特别是对于预测

型分类任务，目前公认的方法是ｌＯ遍分层交叉验证法。

（２）计算复杂度计算复杂度依赖于具体的实现细节和硬件环境，在数据挖

掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。

（３）模型描述的简洁度对于描述型的分类任务，模型描述越简洁越受欢迎，

例如，采用规则表示的分类器构造法就更有用，而神经网络方法产生的结果就难以理解。

数据挖掘的分类技术可以从大量数据中提取出感兴趣的数据模型，并能够对数据未来的发展趋势进行预测，已经广泛应用在疾病诊断、机器学习、模式识别、客户分类、金融服务等领域，目前来说还不存在一种放之四海皆准的分类方法，根据应用背景及相关数据特征的不同需要针对性的采用不同的分类方法。当前研究的主流是将多种分类方法进行融合，最常用的方法有组合方法和选择方法两类。

２．１．２决策树

决策树（ＤｅｃｉｓｉｏｎＴｒｅｅ）又称为判定树，是一种具有二个以上分支的流程图状树结构，除根节点不存在入边外，其他所有节点都有一条入边、零条或者一条出边。决策树的每个内部结点就是一个决策属性，代表训练样本集中一个非类别属性的测试，且每个结点都与训练样本集的一个子集相关．每个分枝代表一个测试的输出结果。每个叶子结点用一个类属性来标记，代表某种条件下的一个多维数据集，也称为一个类或类分布网。

决策树由下列元素构成：一个非根结点ｎ；与ｎ相关的训练样本子集Ｆ（ｎ）；７

硕士学位论文第二章ＷＥＫＡ平台下的决策树算法性能分析从根结点ｒ到ｎ的路径ｒ（ｎｌ，１１２，．．．ｎｉ＇１１）。其中Ｆ（ｎ）就是训练样本集中满足ｒ（ｎｌ，ｎ２，．．．ｎｉ，ｎ）结点的测试的输出结果。使用决策树进行分类的过程就是从这棵树的根结点开始，不断测试各个结点的特定属性，然后按照给定实例的该属性值对应的树枝向下移动，当找到一个新结点作为下级子树的根时，再从此新的根结点不断的用测试节点代替叶结点，这样不断循环递归，直至达到特定的终止条件为止，最后各级子树上重复执行产生的树型结构共同构成了决策树。因此，一旦生成了一棵判定树，很容易根据根节点到叶子节点的路径，得到ＩＦ．ＴＨＥＮ形式的分类规则。路径上每个内部节点的测试条件的合取形成规则的前件ｆＩＦ部分），用类属性标记的叶子节点形成规则的后件（傩Ｎ部分）瞰１，２２１。决策树的构建一般分为成两个阶段：

（１）生成决策树

决策树生成的过程中，输入为训练样本数据集，决策树为最终输出结果。决策树的每一个决策结点对应元组进行分类的一个决策属性（测试属性），分枝对应着元组按该属性进一步划分的取值特征，叶子代表类或类的分布。首先，根据用户的实际需要选择类别标识属性和决策树的决策属性集，决策属性集是指在候选属性（除了类别标识属性之外的所有属性）中选择的属性集，然后开始构造决策树。决策树归纳的基本算法是贪心算法，是以自顶向下递归的各个击破的方式决策树。

（２）对决策树剪枝

先利用训练数据生成一个测试函数，根据不同取值建立树的各个分支和子树。然后对决策树进行剪枝处理，最后为各个节点建立分类或决策规则，利用这些规则数据进行分类。基于决策树的分类方法与其它分类方法比较起来，具有速度较快、容易转化成简单且便于理解的分类规则、容易转换成数据库查询语句等优点，尤其在问题维数高的情况可以得到很好的分类结果ｆ１，卯。

数据挖掘中的决策树是一种应用广泛的技术，它可以很方便地转化为分类规则，是一种非常直观的分类模式表示形式，故决策树经常被用于分类数据和归纳决策规则，根据应用背景的不同它能够针对性的对大量数据进行分类，从中挖掘出潜在的、有价值的信息，并且在处理非数值型数据方面优势明显。

２．＇．３决策树算法

决策树算法是一种应用比较广泛的归纳推理分类方法，它采用自顶向下的方式将从一组训练数据中学习到的函数表示为一棵分类决策树，适用于分类数据和归纳决策规则，其处理流程简单，算法复杂度低，特别适合处理较大规模的数据。

决策树算法先根据训练子集（Ａ称为窗口）形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些实例（Ｅｘａｍｐｌｅ）加入到窗口（Ｗｉｎｄｏｗ）８

硕士学位论文第二章ＷＥＫＡ平台下的决策树算法性能分析中，重复该过程一直到形成正确的决策集，最终得到一棵树【加’捌．最有影响和最早的决策树方法是由Ｑｔｌｉｎ］ａｌｌａ提出的基于信息熵的ＩＤ３算法，但］Ｄ３决策树是一种单变量决策树，存在概念复杂难以表达、抗噪性差等缺陷圈。

大多数的判定树算法都包括两个阶段：构造树阶段和树剪枝阶段。在构造树阶段，通过对分类算法的递归调用，产生一棵完全生长的判定树。构造树的通用算法描述如下嗍；

ＭａｋｃＤｅｃｉｓｉｏｎＴｒｅｅ（ＴｒａｉｎｉｎｇＤａｍｓｅｔｎ

Ｉｆ口满足某个中止条件）ｎ肌ｒｃｍｍ；

Ｆｏｒ（ｉ＝ｌ；ｉ＜＝Ｔ中属性的个数；ｉ＋＋）

评估每个属性关于给定的属性选择度量的分裂特征：

找出最佳的测试属性并据此将Ｔ划分为Ｔｌ和Ｔ２；

Ｍａｌ【ｃＤｌｃｃｉｓｉｏｎＴｒ∞ｃｌｒｌ）；

ＭａｋｅＤｅｃｉｓｉｏｎＴｒｅｅ（他）；

ＥｎｄＩｆ

算法的终止条件一般有三种情况：

１．Ｔ中的所有训练样本都属于同一个类，则将此节点作为一个叶子节点，并以该类标记该节点：

２．没有属性可以用做测试属性；

３．训练样本的数量太少（少于用户提供的某个阈值）。

后两种情况通常以训练样本中占优势的类标记该叶子节点。属性选择度量有信息增益（ｉｎｆｏｒｍａｔｉｏｎｇａｉｎ）（如ＩＤ３，Ｃ４．５等算法），Ｏｉｎｉ指数（如ＳＬＩＱ，ＳＰＲＩＮＴ算法），Ｇ－统计等。

通常情况下，一棵能够完美地分类训练样本集的判定树并不是一棵最精确的判定树，因为这样的一棵树对训练样本集过分敏感，而训练样本集无可避免的存在噪声和孤立点。树剪枝阶段的目的就是要剪去过分适应训练样本集的枝条．较为常见的剪枝算法主要有悲观错误率剪枝算法，最小描述长度（ＭＤＬ）剪枝算法等随２５】．

２．２ＷＥＫＡ平台的介绍

ｗｅｋａ是Ｗａｉｋａｔｏ大学开发的全面的数据挖掘系统，它用ｊａｖａ语言实现并提供了适用于任意数据集的数据预处理以及算法性能评估的方法，具有很强的扩展性和兼容性，用户可以根据具体需要将个性化的算法封装进系统，达到数据处理及算法性能评估的目的【１４，２０１．９

硕士学位论文第二章ＷＥＫＡ平台下的决策树算法性能分析２．２．１ＡＲＦＦ文件结构

Ｆｉｌｅ一个ＡＲＦＦ（Ａｔｔｒｉｂｕｔｅ．Ｒｅｌａｔｉｏｎ

进行数据读入的。Ｆｏｒｍａｔ）文件㈣是一个ＡＳＣＩＩ的文本文件，用来记录一个有很多属性的记录项列表。这个文件是专门用来提供给ＷＥＫＡ

ＡＲＦＦ文件有两个明显的部分，一个是头信息，一个是数据信息。

头信息当中包含了关系的名称，一个属性列表（也就是数据中的列），以及他们的类型。一个ｗｅａｔｈｅｒ数据集的头信息就像这样：

＠．ｒｅｌａｔｉｏｎｗｅａｔｈｅｒ

＠ａｔｔｒｉｂｕｔｅｏｕｔｌｏｏｋ｛ｓｕｎｎｙ，ｏｖｅｒｃａｓｔ，ｒａｉｎｙ｝

＠ａｔｔｒｉｂｕｔｅ

＠，ａｔｔｒｉｂｕｔｅｔｅｍｐｅｒａｔｕｒｅｒｅａｌｈｕｍｉｄｉｔｙｒｅａｌ

＠ａｔｔｄｂｕｔｅｗｉｎｄｙ｛ＴＲＵＥ，ＦＡＬＳＥ｝

＠．ａｔｔｒｉｂｕｔｅｐｌａｙ｛ｙｅｓ，ｎｏ｝

棚文件的数据部分就像这样：

＠ｄａｔａ

ｓｕｎｎｙ，８５，８５，，ＦＡＬＳＥ，ｎｏ

ｓｕｎｎｙ，８０，９０，ＴＲＵＥ，ｎｏ

ｏｖｅｒｃａｓｔ，８３，８６，ＦＡＬＳＥ，ｙｅｓ

ｒａｉｎｙ，７０，９６，ｎ地ＳＥ，ｙｅｓ

ｒａｉｎｙ，６８，８０，ｎＵ，ＳＥ，ｙｅｓ

ｒａｉｎｙ，６５，７０，ＴＲＵＥ，ｎｏ

ｏｖｅｒｃａｓｔ６４，６５，ＴＲＵＥ，ｙｅｓ

ｓｕｎｎｙ，７２，９５，ＦＡＬＳＥ，ｎｏｓｕｎｎｙ，６９，７０眦ＳＥ，ｙｅｓ

ｒａｉｎｙ，７５，８０孓战ＳＥ，ｙｅｓ

ｓｕｎｎｙ，７５，７０，ＴＲＵＥ，ｙｅｓ

ｏｖｅｒｃａｓｔ，７２，９０，ＴＲＩ『Ｅ，ｙｅｓ

ｏｖｅｒｇａｓｔ，８１，７５，ＦＡＬＳＥ，ｙｅｓ

ｒａｉｎｙ，７１，９１，ＴＲＵＥ，ｎｏ

一行的起始如果是以百分号％开始的，那么这一行就是注释。＠ＲＥＬＡＴＩＯＮ，＠．ＡＹｒＲｍＵＴＥ和＠ＤＡＴＡ是特殊的标识。１０

硕士学位论文第二章ＷＥＫＡ平台下的决策树算法性能分析

ＡＲＦＦ文件的头部分：

ＡＲＦＦ文件的头部分包含关系声明以及属性声明。

＠ＲＥＬＡＴＩＯＮ声明：关系名是在脚文件的开头定义的。

格式是：＠ｒｅｌａｔｉｏｎ＜ｒｅｌａｔｉｏｎ－ｎａｍｅ＞

ｒｅｌａｔｉｏｎ－ｎａｍｅ必须是字符串，当一个名字中间有空格时，它必须用引号括起来。

＠，ＡＴＴＲＩＢＵＴＥ声明：

属性声明是以文本中个属性描述的先后顺序捧列的。在数据集中的每一个属性都有一个唯－－的＠．Ａ＇ｒｒＲｍＵＴＥ声明，用来反应其对应的数据类型。属性声明的顺序就是数据集中列的先后顺序。例如，如果一个属性是第三个声明的，那么使用者将在文本文件的第三个逗号那里找到它。

＠ＡＴｒＲｊＢｕＴＥ声明的格式是：＠ａｔｔｒｉｂｕｔｅ＜ａｔｔｒｉｂｕｔｅ－ｎａｍｅ＞＜ｄａｔｍｙｐｅ＞

属性名必须以字母开始。同样，如果命名中间有空格，就必须用引号括起来。ＡＲＦＦ文件的数据部分：

ＡＲＦＦ文件的数据部分包含数据声明行和实际的数据项。

＠ｄａｔｅ声明：

有＠ｄａｔｅ的这一行就意味着它是文件数据区的开始。

数据实例：

每一行代表一个数据实例，换行表示下一个数据实例的开始。

每一个数据实例的各个属性值都由逗号分隔开来。而且属性值的出现顺序必须与ＡＲＦＦ文件的头部分定义的顺序一致（例如：第ｎ个数据声明的数据值总是第ｎ个属性域中的值）．

这里，空值直接由一个问号来表示，就像：

＠ｄａｔａ

４．４，？，１．５，？，Ｉｒｉｓ－ｓｅｔｏｓａ

对于字符串和离散属性就有些麻烦，当他们的值中间由空格的时候，就必须用引号来括起来，如下所示：

下载地址：基于WEKA平台的决策树算法设计与实现_图文63.Doc

　　【】