登录
首页精彩阅读数据挖掘- 分类算法比较
数据挖掘- 分类算法比较
2016-07-20
收藏

数据挖掘- 分类算法比较

随着计算能力、存储、网络的高速发展,人类积累的数据量正以指数速度增长。对于这些数据,人们迫切希望从中提取出隐藏其中的有用信息,更需要发现更深层次的规律,对决策,商务应用提供更有效的支持。为了满足这种需求,数据挖掘技术的得到了长足的发展,而分类在数据挖掘中是一项非常重要的任务,目前在商业上应用最多。本文主要侧重数据挖掘中分类算法的效果的对比,通过简单的实验(采用开源的数据挖掘工具 -Weka)来验证不同的分类算法的效果,帮助数据挖掘新手认识不同的分类算法的特点,并且掌握开源数据挖掘工具的使用。

分类算法是解决分类问题的方法,是数据挖掘机器学习和模式识别中一个重要的研究领域。分类算法通过对已知类别训练集的分析,从中发现分类规则,以此预测新数据的类别。分类算法的应用非常广泛,银行中风险评估、客户类别分类、文本检索和搜索引擎分类、安全领域中的入侵检测以及软件项目中的应用等等。

分类算法介绍

以下介绍典型的分类算法。

Bayes

贝叶斯分类器的分类原理是通过某对象的先验概率,利用贝叶斯公式计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类作为该对象所属的类。目前研究较多的贝叶斯分类器主要有四种,分别是:Naive Bayes、 TAN、BAN 和 GBN。

贝叶斯网络(BayesNet)

贝叶斯网络是一个带有概率注释的有向无环图,图中的每一个结点均表示一个随机变量 , 图中两结点间若存在着一条弧,则表示这两结点相对应的随机变量是概率相依的,反之则说明这两个随机变量是条件独立的。网络中任意一个结点 X 均有一个相应的条件概率表 Conditional Probability Table,CPT) ,用以表示结点 X 在其父结点取各可能值时的条件概率。若结点 X 无父结点 , 则 X 的 CPT 为其先验概率分布。贝叶斯网络的结构及各结点的 CPT 定义了网络中各变量的概率分布。应用贝叶斯网络分类器进行分类主要分成两阶段。第一阶段是贝叶斯网络分类器的学习,即从样本数据中构造分类器,包括结构学习和 CPT 学习;第二阶段是贝叶斯网络分类器的推理,即计算类结点的条件概率,对分类数据进行分类。这两个阶段的时间复杂性均取决于特征值间的依赖程度,甚至可以是 NP 完全问题,因而在实际应用中,往往需要对贝叶斯网络分类器进行简化。根据对特征值间不同关联程度的假设,可以得出各种贝叶斯分类器。

朴素贝叶斯(NaiveBayes)

朴素贝叶斯模型(NBC)发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率。同时,NBC 模型所需估计的参数很少,对缺失数据不太敏感,算法也比较简单。NBC 模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的,这给 NBC 模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时,NBC 模型的分类效率比不上决策树模型。而在属性相关性较小时,NBC 模型的性能最为良好。

Lazy Learning

相对其它的 Inductive Learning 的算法来说,Lazy Learning 的方法在训练是仅仅是保存样本集的信息,直到测试样本到达时才进行分类决策。也就是说这个决策模型是在测试样本到来以后才生成的。相对与其它的分类算法来说,这类的分类算法可以根据每个测试样本的样本信息来学习模型,这样的学习模型可能更好的拟 合局部的样本特性。kNN 算法的思路非常简单直观:如果一个样本在特征空间中的 k 个最相似 ( 即特征空间中最邻近 ) 的样本中的大多数属于某一个类别,则该样本也属于这个类别。其基本原理是在测试样本到达的时候寻找到测试样本的 k 临近的样本,然后选择这些邻居样本的类别最集中的一种作为测试样本的类别。在 weka 中关于 kNN 的算法有两个,分别是 IB1,IBk。

IB1 即 1 近邻

IB1 是通过它的一个邻居来判断测试样本的类别

IBk 即 K 近邻

IBk 是通过它周围的 k 个邻居来判断测试样本的类别

在样本中有比较多的噪音点是(noisy points)时,通过一个邻居的效果很显然会差一些,因为出现误差的情况会比较多。这种情况下,IBk 就成了一个较优的选项了。这个时候有出现了一个问题,k 这个值如何确定,一般来说这个 k 是通过经验来判断的。

Trees

决策树算法,决策树是对数据进行分类,以此达到预测的目的。该决策树方法先根据训练集数据形成决策树,如果该树不能对所有对象给出正确的分类,那么选择一些例外加入到训练集数据中,重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。决策树由决策结点、分支和叶子组成。决策树中最上面 的结点为根结点,每个分支是一个新的决策结点,或者是树的叶子。每个决策结点代表一个问题或决策,通常 对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。沿决策树从上到下遍历的过程中,在每个结点都会遇到一个测试,对每个结点上问题的不同的 测试输出导致不同的分支,最后会到达一个叶子结点,这个过程就是利用决策树进行分类的过程,利用若干个变量来判断所属的类别。

  1. Id3 即决策树 ID3 算法

    ID3 算法是由 Quinlan 首先提出的。该算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。

    以下是一些信息论的基本概念:

    定义 1:若存在 n 个相同概率的消息,则每个消息的概率 p 是 1/n,一个消息传递的信息量为 Log2(n)

    定义 2:若有 n 个消息,其给定概率分布为 P=(p1,p2 … pn),则由该分布传递的信息量称为 P 的熵,记为

    I (p) =-(i=1 to n 求和 ) piLog2(pi) 。

    定义 3:若一个记录集合 T 根据类别属性的值被分成互相独立的类 C1C2..Ck,则识别 T 的一个元素所属哪个类所需要的信息量为 Info (T) =I (p) ,其中 P 为 C1C2 … Ck 的概率分布,即 P= (|C1|/|T| … |Ck|/|T|)

    定义 4:若我们先根据非类别属性 X 的值将 T 分成集合 T1,T2 … Tn,则确定 T 中一个元素类的信息量可通过确定 Ti 的加权平均值来得到,即 Info(Ti) 的加权平均值为:

    Info(X, T) = (i=1 to n 求和 ) ((|Ti|/|T |) Info (Ti))

    定义 5:信息增益度是两个信息量之间的差值,其中一个信息量是需确定 T 的一个元素的信息量,另一个信息量是在已得到的属性 X 的值后需确定的 T 一个元素的信息量,信息增益度公式为:

    Gain(X, T) =Info (T)-Info(X, T)

  2. J48 即决策树 C4.5 算法

  3. C4.5 算法一种分类决策树算法 , 其核心算法是 ID3 算法。C4.5 算法继承了 ID3 算法的优点,并在以下几方面对 ID3 算法进行了改进:用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足; 在树构造过程中进行剪枝; 能够完成对连续属性的离散化处理; 能够对不完整数据进行处理。 C4.5 算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。

Rule

  1. Decision Table 即决策表

    决策表 (Decision Table),是一中使用表的结构,精确而简洁描述复杂逻辑的方式。

  2. JRip 即 RIPPER 算法

    规则归纳学习从分类实例出发能够归纳出一般的概念描述。其中重要的算法为 IREP 算法和 RIPPER 算法。重复增量修枝(RIPPER)算法生成一条规则,随机地将没有覆盖的实例分成生长集合和修剪集合,规定规则集合中的每个规则是有两个规则来生成:替代规则和修订规则。

Meta

  1. AdaBoostM1 即 AdaBoosting 算法

    Adaboost 是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器 ( 弱分类器 ) ,然后把这些弱分类器集合起来,构成一个更强的最终分类器 ( 强分类器 ) 。其算法本身是通过改变数据分布来实现的,它根据每次训练集之中每个样本的分类是否正确,以及上次的总体分类的准确率,来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练,最后将每次训练得到的分类器最后融合起来,作为最后的决策分类器。

  2. Bagging 即 Bagging 方法

    Bootstrps bagging boosting 都属于集成学习方法,将训练的学习器集成在一起。原理来源于 PAC 学习模型(Probably Approximately CorrectK)。其中的 Bagging 是 bootstrap aggregating 的缩写,是最早的 Ensemble 算法之一,它也是最直接容易实现,又具有不错的效果的算法之一。Bagging 中的多样性是由有放回抽取训练样本来实现的,用这种方式随机产生多个训练数据的子集,在每一个训练集的子集上训练一个同种分类器,最终分类结果是由多个分类器的分类结果多数投票而产生的。

Weka 中分类算法的参数解释

Correlation coefficient (= CC) : 相关系数

Root mean squared error (= RMSE) : 均方根误差

Root relative squared error (= RRSE) : 相对平方根误差

Mean absolute error (= MAE) : 平均绝对误差

Root absolute error (= RAE) : 平均绝对误差平方根

Combined: (1-abs (CC)) + RRSE + RAE: 结合的

Accuracy (= ACC) : 正确率

注意,Correction coefficient 只适用于连续值类别,Accuracy 只适用于离散类别

Kappa statistic:这个指标用于评判分类器的分类结果与随机分类的差异度。

绝对差值(Mean absolute error):这个指标用于评判预测值与实际值之间的差异度。把多次测得值之间相互接近的程度称为精密度,精密度用偏差表示,偏差指测得值与平均值之间的差值,偏差越小,精密度则越高。

中误差(Root mean square error:RMSE):带权残差平方和的平均数的平方根,作为在一定条件下衡量测量精度的一种数值指标。中误差是衡量观测精度的一种数字标准,亦称“标准差”或“均方根差”。在相同观测条件下的一组真误差平方中数的平方根。因真误差不易求得 , 所 以通常用最小二乘法求得的观测值改正数来代替真误差。它是观测值与真值偏差的平方和观测次数 n 比值的平方根。中误差不等于真误差,它仅是一组真误差的代表值。中误差的大小反映了该组观测值精度的高低,因此,通常称中误差为观测值的中误差。

分类算法的评价标准

预测的准确率:这涉及到模型正确地预测新的或先前没见过的数据的类 标号能力。

速度:涉及到产生和使用模型的计算花费。

强壮性:这涉及给定噪声数据或具有空缺值的数据,模型正确预测的能力。

可伸缩性:这涉及给定大量的数据,有效的构造模型的能力。

可解释性:这涉及学习模型提供的理解和洞察的层次。

分类算法的比较

以下主要采用两种数据集(Monk's Problems 和 Satimage)来分别运行不同的分类算法,采用的是 Weka 数据挖掘工具。

Monk's Problems 数据集特点

1. 属性全部为 nominal 类型

2. 训练样本较少

图 1. 训练数据集

3. 训练集数据的可视化图,该图根据直方图上方一栏所选择的 class 属性(attr6)来着色。

图 2. 训练数据集可视化图

各分类器初步分类效果分析

各分类器不做参数调整,使用默认参数进行得到的结果。

表 1. 分类器初步结果比较 分类器比较

预测的准确率比较

采用基于懒惰学习的 IB1、IBk 的分类器的误差率较低,采用基于概率统计的 BayesNet 分类器的误差率较高,其他的基于决策树和基于规则的分类器误差居于前两者之间,这是因为在样本较少的情况下,采用 IB1 时,生成的决策模型是在测试样本到来以后才生成,这样的学习模型可能更好的拟合局部的样本特性。采用统计学分类方法的 BayesNet 之所以准确度较低,可能是由于贝叶斯定理的成立本身需要很强的独立性假设前提,而此假设在实际情况中经常是不成立的。但是一般地,统计分类算法趋于计算量大。

进一步比较分类结果的散点图(其中正确分类的结果用叉表示,分错的结果用方框表示),发现 BayesNet 分类器针对属性 6(attr6)的预测结果分错的结果明显比 IB1 的分错结果要多些,而这些错误的散点中,又以属性 6 的取值为 2 的散点中错误的数目较多。

图 3. BayesNet 的分类结果散点图

图 3. BayesNet 的分类结果<a href='/map/sandiantu/' style='color:#000;font-size:inherit;'>散点图</a>

图 4. IB1 分类结果散点图

图 4. IB1 分类结果<a href='/map/sandiantu/' style='color:#000;font-size:inherit;'>散点图</a>

分类速度比较

Adaboost 的分类花了 0.08 秒,Bagging 的分类花了 0.03 秒,相对于其他的分类器,这两个分类器速度较慢。这是因为这两个算法采用迭代,针对同一个训练集,训练多种分类器,然后把这些分类器集合起来,所以时间消耗较长。

分类器参数调优

IBK 调优

KNN 】:6

扩大邻近学习的节点范围,降低异常点的干扰(距离较大的异常点)

 【 DistanceWeighting 】:Weight by 1/distance

通过修改距离权重,进一步降低异常点的干扰(距离较大的异常点)

图 5. IBk 分类调优

图 5. IBk 分类调优

IBk 调优结果

调优后准确率从 60.65% 上升到 63.43%。

表 2. IBk 调优结果 J48 调优


【 binarySplits 】:True

采用 2 分法,生成决策树

图 6. J48 分类调优

图 6. J48 分类调优

J48 调优结果

调优后准确率从 59.72% 上升到 64.35%,但是分类模型建立时间从 0 延长到了 0.31 秒

表 3. J48 调优结果

Salmage 数据集特点

1. 属性为 numeric 类型 , 共 37 个属性

2. 训练数据各类不平衡,测试数据各类不平衡

图 7. 训练数据集可视化图

各分类器初步分类效果分析

各分类器不做参数调整,使用默认参数得到的结果如下:

表 4. 分类器初步结果比较 分类器比较

预测的准确率比较

采用基于懒惰学习的 IB1、IBk 的分类器的准确率都较高,为 90.36%,采用 基于决策桩的 AdaBoostM 分类器的准确率较低,为 43.08%,贝叶斯分类器的准确 率较之前的数据集(Monk ’ s problem)有明显的提高,从 49% 到了 80% 左右,这主 要是因为样本空间的扩大,其他的分类器准确率也处于 80% 左右。

分类速度比较

DecisionTable 的分类花了 4.33 秒,Bagging 的分类花了 3.92 秒,J48 的分类模型建立花了 2.06 秒,相对于其他的分类器,这三个分类器速度较慢。

分类器参数调优

IBK 调优

KNN 】:6

扩大邻近学习的节点范围,降低异常点的干扰(距离较大的异常点)

 【 DistanceWeighting 】:Weight by 1/distance

通过修改距离权重,进一步降低异常点的干扰(距离较大的异常点)

IBK 调优结果

调优后准确率从 90.36% 上升到 90.98%, 准确度有略微提升,说明通过扩大邻近学习的节点范围不能明显提高分类器的性能。

表 5. IBk 调优结果

J48 调优
【 binarySplits 】:True

采用 2 分法,生成决策树

J48 调优结果

分类性能没有提升。说明采用 2 分法对分类没有影响。相反,时间比原来的算法有略微延长。

表 6. J48 调优结果

改进和建议

本文给出的调优方法只是一个简单的示例,实际上根据合理的参数调整,这些分类算法的效果还能得到更大的提升。

数据分析咨询请扫描二维码

客服在线
立即咨询