数据挖掘分类方法小结_数据挖掘中的基于决策树的分类方法

数据仓库，数据库或者其它信息库中隐藏着许多可以为商业、科研等活动的决策提供所需要的知识。分类与预测是两种数据分析形式，它们可以用来抽取能够描述重要数据集合或预测未来数据趋势的模型。分类方法（Classification）用于预测数据对象的离散类别（Categorical Label）；预测方法（Prediction ）用于预测数据对象的连续取值。

分类技术在很多领域都有应用，例如可以通过客户分类构造一个分类模型来对银行贷款进行风险评估；当前的市场营销中很重要的一个特点是强调客户细分。客户类别分析的功能也在于此，采用数据挖掘中的分类技术，可以将客户分成不同的类别，比如呼叫中心设计时可以分为：呼叫频繁的客户、偶然大量呼叫的客户、稳定呼叫的客户、其他，帮助呼叫中心寻找出这些不同种类客户之间的特征，这样的分类模型可以让用户了解不同行为类别客户的分布特征；其他分类应用如文献检索和搜索引擎中的自动文本分类技术；安全领域有基于分类技术的入侵检测等等。机器学习、专家系统、统计学和神经网络等领域的研究人员已经提出了许多具体的分类预测方法。下面对分类流程作个简要描述： 

训练：训练集——>特征选取——>训练——>分类器

分类：新样本——>特征选取——>分类——>判决 

最初的数据挖掘分类应用大多都是在这些方法及基于内存基础上所构造的算法。目前数据挖掘方法都要求具有基于外存以处理大规模数据集合能力且具有可扩展能力。下面对几种主要的分类方法做个简要介绍： 

（1）决策树 

决策树归纳是经典的分类算法。它采用自顶向下递归的各个击破方式构造决策树。树的每一个结点上使用信息增益度量选择测试属性。可以从生成的决策树中提取规则。

(2) KNN法(K-Nearest Neighbor)

KNN法即K最近邻法，最初由Cover和Hart于1968年提出的，是一个理论上比较成熟的方法。该方法的思路非常简单直观：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种Reverse KNN法，能降低KNN算法的计算复杂度，提高分类的效率。

该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 

(3) SVM法

SVM法即支持向量机(Support Vector Machine)法，由Vapnik等人于1995年提出，具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习方法。通过学习算法，SVM可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分准率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果。

支持向量机算法的目的在于寻找一个超平面H(d),该超平面可以将训练集中的数据分开，且与类域边界的沿垂直于该超平面方向的距离最大，故SVM法亦被称为最大边缘(maximum margin)算法。待分样本集中的大部分样本不是支持向量，移去或者减少这些样本对分类结果没有影响，SVM法对小样本情况下的自动分类有着较好的分类结果。 

(4) VSM法

VSM法即向量空间模型(Vector Space Model)法，由Salton等人于60年代末提出。这是最早也是最出名的信息检索方面的数学模型。其基本思想是将文档表示为加权的特征向量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然后通过计算文本相似度的方法来确定待分样本的类别。当文本被表示为空间向量模型的时候，文本的相似度就可以借助特征向量之间的内积来表示。

在实际应用中，VSM法一般事先依据语料库中的训练样本和分类体系建立类别向量空间。当需要对一篇待分样本进行分类的时候，只需要计算待分样本和每一个类别向量的相似度即内积，然后选取相似度最大的类别作为该待分样本所对应的类别。

由于VSM法中需要事先计算类别的空间向量，而该空间向量的建立又很大程度的依赖于该类别向量中所包含的特征项。根据研究发现，类别中所包含的非零特征项越多，其包含的每个特征项对于类别的表达能力越弱。因此，VSM法相对其他分类方法而言，更适合于专业文献的分类。 

(5) Bayes法

Bayes法是一种在已知先验概率与类条件概率的情况下的模式分类方法，待分样本的分类结果取决于各类域中样本的全体。

设训练样本集分为M类，记为C=｛c1，…，ci，…cM}，每类的先验概率为P(ci)，i=1，2，…，M。当样本集非常大时，可以认为P(ci)=ci类样本数/总样本数。对于一个待分样本X，其归于cj类的类条件概率是P(X/ci)，则根据Bayes定理，可得到cj类的后验概率P(ci/X)：

P(ci/x)=P(x/ci)·P(ci)/P(x)(1)

若P(ci/X)=MaxjP(cj/X)，i=1，2，…，M，j=1，2，…，M，则有x∈ci(2)

式(2)是最大后验概率判决准则，将式(1)代入式(2)，则有：

若P(x/ci)P(ci)=Maxj［P(x/cj)P(cj)］，i=1，2，…，M，j=1，2，…，M，则x∈ci

这就是常用到的Bayes分类判决准则。经过长期的研究，Bayes分类方法在理论上论证得比较充分，在应用上也是非常广泛的。

Bayes方法的薄弱环节在于实际情况下，类别总体的概率分布和各类样本的概率分布函数(或密度函数)常常是不知道的。为了获得它们，就要求样本足够大。另外，Bayes法要求表达文本的主题词相互独立，这样的条件在实际文本中一般很难满足，因此该方法往往在效果上难以达到理论上的最大值。 

（6）神经网络

神经网络分类算法的重点是构造阈值逻辑单元，一个值逻辑单元是一个对象，它可以输入一组加权系数的量，对它们进行求和，如果这个和达到或者超过了某个阈值，输出一个量。如有输入值X1, X2, …, Xn 和它们的权系数：W1, W2, …, Wn，求和计算出的 Xi*Wi ，产生了激发层 a = (X1 * W1)+(X2 * W2)+…+(Xi * Wi)+…+ (Xn * Wn)，其中Xi 是各条记录出现频率或其他参数，Wi是实时特征评估模型中得到的权系数。神经网络是基于经验风险最小化原则的学习算法，有一些固有的缺陷，比如层数和神经元个数难以确定，容易陷入局部极小，还有过学习现象，这些本身的缺陷在SVM算法中可以得到很好的解决

数据挖掘中的基于决策树的分类方法

1 分类的概念及分类器的评判

分类是数据挖掘中的一个重要课题。分类的目的是学会一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。

分类可描述如下：输入数据，或称训练集（training set）是一条条记录组成的。每一条记录包含若干条属性（attribute），组成一个特征向量。训练集的每条记录还有一个特定的类标签（类标签）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：(v1,v2,…,…vn:c)。在这里vi表示字段值，c表示类别。

分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型。这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意是预测，而不能肯定。我们也可以由此对数据中的每一个类有更好的理解。也就是说：我们获得了对这个类的知识。

对分类器的好坏有三种评价或比较尺度：

预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法是10番分层交叉验证法。

计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。

模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越受欢迎；例如，采用规则表示的分类器构造法就更有用。

分类技术有很多，如决策树、贝叶斯网络、神经网络、遗传算法、关联规则等。本文重点是详细讨论决策树中相关算法。

2 基于决策树的数据分类算法及其性能

2.1 ID3和C4.5算法

决策树技术是用于分类和预测的主要技术，决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中推理除决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分支，然后进行剪枝，最后在决策树的叶节点得到结论。所以从根到叶节点就对应着一条合取规则，整棵树就对应着一组析取表达式规则。基于决策树的分类有很多实现算法。ID3和C4.5是较早提出并普遍使用的决策树算法。

Quinlan提出的著名的ID3学习算法是较早的经典算法。它通过选择窗口来形成决策树，是利用信息论中的互信息寻找训练集具有最大信息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树的分支；在每个分支子集中重复建立树的下层节点和分支过程。C4.5算法和ID3算法相似，它是对ID3算法的一种改进，它是根据信息增益（Information Gain）值选择作为分裂结点的属性及标准,按照此标准将训练集分成若干个子集。这两中种方法的优点是描述简单，分类速度快，分类较准确特别适合大规模的数据处理。但这两种算法是借用信息论中的互信息或信息增益作为单一属性能力的度量，试图减少树的平均深度，忽略了叶子数目的研究，其启发式函数并不是最优的，存在的主要问题还有：（1）抗噪性差，训练例子中正例和反例较难控制。（2）在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。（3）这两种算法只适合于能够驻留于内存的数据集使用,当训练集大得无法在内存容纳时程序无法运行。

2.2 SLIQ算法

SLIQ算法对C4.5决策树分类算法的实现方法进行了改进。

一般决策树中，使用信息量作为评价节点分裂质量的参数，SLIQ算法中使用gini指标代替信息量，gini指标比信息量性能更好，且计算方便，对数据集包含n个类的数据集S，gini(S)定义为：

gini(S) = 1 – ∑pj*pj

pj是S中第j类数据的频率gini越小，Information Gain越大。

区别于一般的决策树 SLIQ采用二分查找树结构 对每个节点都需要先计算最佳分裂方案，然后执行分裂。

对于数值型连续字段分裂的形式A<=v。所以，可以先对数值型字段排序，假设排序后的结果为v1,v2,…,…vn，因为分裂只会发生在两个节点之间，所以有n-1种可能性。通常取中点(vi + vi+1)/2作为分裂点，从小到大依次取不同的split point，取Information Gain指标最大(gini最小)的一个就是分裂点,因为每个节点都需要排序，所以这项操作的代价极大。

对于离散型字段(categorical attribute)，设S(A)为A的所有可能的值，分裂测试将要取遍S的所有子集S’。寻找当分裂成S’和S-S’两块时的gini指标，取到gini最小的时候，就是最佳分裂方法。显然，这是一个对集合S的所有子集进行遍历的过程共需要计算2|S| 次，代价也是很大的。

SLIQ算法对此采用了预排序的技术,以便能够消除在决策树的每个结点对数据集进行排序的需要。所谓预排序,就是针对每个属性的取值,把所有的记录按照从小到大的顺序进行排序。

在C4.5中,树的构造是按照深度优先策略完成的,需要对每个属性列表在每个结点处都进行一遍扫描,费时很多。SLIQ采用广度优先策略构造决策树,即在决策树的每一层只需对每个属性列表扫描一次,就可以为当前决策树中每个叶子结点找到最优分裂标准。

SLIQ的剪枝算法MDL属于迟滞剪枝(post-prunning)算法，通常的迟滞剪枝的数据源采用一个Training Set的一个子集或者与Training Set独立的数据集进行操作。

SLIQ算法具体实现

输入与输出：输入与输出采用下面的方案 输入数据 包括训练集配置信息(决策树大小) 输出数据 包括用线性方式表示的二分决策树

算法的控制：算法的控制结构是一个队列，这个队列存放当前的所有叶子节点。这是为了控制广度优先搜索的结束。当队列空时，说明所有的叶子都已经被处理过，这时建树算法结束。

（1）数据准备

系统输入是训练集，训练集是样本向量(v1,v2,…,…vn ：c)组成的集合，每个属性对应训练集的一列，训练集进入以后，分成一个一个的属性表：

(Attribute List){(vi,i)| i<=training data num && i>=0}

i是属性vi的记录索引号，将所有类标识放入类表，类表中的leaf字段指向该记录对应的决策树的叶子，初始状态下，所有记录指向树根，对属性表进行预排序，交换属性值vi，同时交换I，生成有序的属性表序列。排序完成后属性表中的i是属性值指向类表的指针。完成属性表的排序后，数据初始化工作就完成。

（2）计算最佳分裂

当完成数据预处理之后 算法进入往复的求最佳分裂指标的阶段。这一阶段 经过一次对所有属性表的遍历，可以找出所有叶子节点的最佳分裂方案，在这个阶段有一个重要的结构，类直方图(class histogram)，它位于决策树的每个顶点内，存放每个节点当前的类信息——左、右子树的每个类各拥有多少节点。

当前属性A是数值型字段时 每次作遍历时类直方图亦随之改变，随时表征以当前属性A的当前值v为阈值的节点分裂方式对叶子L的分裂状况由Class Histogram即可算出某个分裂方案的gini值，完成对A的遍历后，gini值最小既Information Gain最高的A的值就是用属性A分裂的最佳阈值。新方案可以存入决策树节点。

当前属性是离散型字段时，在遍历过程中记录下每个属性值对应的类的个数，遍历完成后，利用贪心算法得到Information Gain最高的A的子集，

即为所求的用A的分裂方案，新方案可以存入决策树节点。

对整个属性表的每个属性进行一次完全的遍历之后 对每个节点而言，最佳分裂方案包括用哪个属性进行分类以及分类的阈值是什么已经形成。并且存放在决策树的节点内。

（3）升级节点

当最佳分裂参数已经存放在节点中以后，算法的下一步是创建子节点，执行节点分裂(升级类表)。这一步的主要任务是对应该分裂的类表进行更改。

（4）结果输出

算法生成的决策树通过前序遍历的方式存入输出表。

SLIQ的优点有：（1）运算速度快，对属性值只作一次排序。（2）利用整个训练集的所有数据，不作取样处理，不丧失精确度。（3）轻松处理磁盘常驻的大型训练集，适合处理数据仓库的海量历史数据。（4）更快的更小的目标树。（5）低代价的MDL剪枝算法。

SLIQ的存在的缺点有：（1）由于需要将类别列表存放于内存,而类别列表的长度与训练集的长度是相同的,这就一定程度上限制了可以处理的数据集的大小。（2）由于采用了预排序技术,而排序算法的复杂度本身并不是与记录个数成线性关系,因此使得SLIQ算法不可能达到随记录数目增长的线性可扩展性。

2.3 SPRINT算法

为了减少数据量，SPRINT算法改进了SLIQ决策树算法实现时的数据结构，去掉驻留于内存的类别列表，将其合并到每个属性列表中。这样，在寻找当前结点的最优分裂标准时，遍历每个属性列表就不必参照其他信息。但是，对非分裂属性的属性列表进行分裂变得很困难，需要用哈希表记录下每个记录属于个孩子结点。

SPRINT串行算法

算法的基本步骤如下:

Procedure BuildTree (S , A )

(S:训练样本集，A:分类属性集合)

初始化样本集S，生成有序属性列表和直方图，创建节点队列，放人N

while队列不为空

从队列中取出第一个节点N

if N纯or为空then

标记为叶节点，continue

for N的每一个分割点F

计算该节点F上的gini值，选出最佳分割点F* ,N长出分支节点N1,N2，放人队列中.将该分割点的属性列表分割，并用该列表的rids生成记录所在节点的哈希表，用哈希表分割其他属性列表，列表分割同时生成属性直方图。

串行环境下，刚开始SPRINT比SLIQ时间消耗高一些，样本继续增加后，SLIQ时间消耗要比SPRINT高。在并行环境下采用并行算法，相同处理器时相应时间SLIQ要大于SPRINT。

SPRINT算法具备以下优点:（1）训练样本量不受内存限制。（2）具有优秀的伸缩性、加速性和扩容性。（3）并行实现容易，效率高。

SPRINT算法具备以下缺点:（1）使用属性列表，存储代价是原来的三倍。（2）节点分割要创建哈希表，加大系统负担。（3）节点分割处理相对复杂。

以上是几种常用的基于决策树的分类算法，随着算法研究的进行，出现了许多其他基于决策树的算法，它们与神经网络、遗传算法等技术结合，从不同的方面对算法进行了提高。相信以后会出现更多效率更好、准确度更高的算法。