数据挖掘之经典算法（非常实用）资源-CSDN文库

数据挖掘

经典算法

需积分: 9 155 浏览量 2010-09-23 11:14:36 上传评论收藏 896KB DOC 举报

资源推荐

资源详情

资源评论

数据挖掘之经典算法

1 决策树算法

机器学习中，决策树是一个预测模型；它代表的是对象属性值与对象值之间的一种映

射关系。树中每个节点表示某个对象，每个分叉路径则代表的某个可能的属性值，而每个

叶结点则对应具有上述属性值的子对象。决策树仅有单一输出；若需要多个输出，可以建

立独立的决策树以处理不同输出。

从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

决策树学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型

结构，它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据

库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个

单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决

策树结合起来以提升分类的正确率。

决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取

得更加理想的效果。

1.1 决策树的工作原理

决策树一般都是自上而下的来生成的。

选择分割的方法有多种，但是目的都是一致的，即对目标类尝试进行最佳的分割。

从根节点到叶子节点都有一条路径，这条路径就是一条“规则”。

决策树可以是二叉的，也可以是多叉的。

对每个节点的衡量：

1) 通过该节点的记录数；

2) 如果是叶子节点的话，分类的路径；

3) 对叶子节点正确分类的比例。

有些规则的效果可以比其他的一些规则要好。

1.2 ID3 算法

x≥0

x≥0 w

x≥0

二叉决策树框图

1.2.1 概念提取算法 CLS

1) 初始化参数 C={E}，E 包括所有的例子，为根；

2) 如果 C 中的任一元素 e 同属于同一个决策类则创建一个叶子节点 YES 终止；否则依

启发式标准，选择特征 F

={V

, V

,, V

}并创建判定节点，划分 C 为互不相交的 N 个

集合 C

，C

，……，C

；

3) 对任一个 C

递归。

1.2.2 ID3 算法

1) 随机选择 C 的一个子集 W (窗口)；

2) 调用 CLS 生成 W 的分类树 DT(强调的启发式标准在后)；

3) 顺序扫描 C 搜集 DT 的意外(即由 DT 无法确定的例子)；

4) 组合 W 与已发现的意外，形成新的 W；

5) 重复 2)到 4)，直到无例外为止。

启发式标准：

只跟本身与其子树有关，采取信息理论用熵来量度。

熵是选择事件时选择自由度的量度，其计算方法为： P=freq(C

,S)/|S|；INFO(S)=-

SUM(P*LOG(P)) ； SUM() 函数是求 j 从 1 到 n 的和。 Gain(X)=Info(X)-Infox(X) ；

Infox(X)=SUM( (|T

|/|T|)*Info(X)；

为保证生成的决策树最小， ID3 算法在生成子树时，选取使生成的子树的熵 (即

Gain(S))最小的特征来生成子树。

ID3 算法对数据的要求：

1) 所有属性必须为离散量；

2) 所有的训练例的所有属性必须有一个明确的值；

3) 相同的因素必须得到相同的结论且训练例必须唯一。

1.3 C4.5 算法

由于 ID3 算法在实际应用中存在一些问题，于是 Quilan 提出了 C4.5 算法，严格上说

C4.5 只能是 ID3 的一个改进算法。

C4.5 算法继承了 ID3 算法的优点，并在以下几方面对 ID3 算法进行了改进：

1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的

不足；

2) 在树构造过程中进行剪枝；

3) 能够完成对连续属性的离散化处理；

4) 能够对不完整数据进行处理。

C4.5 算法有如下优点：

产生的分类规则易于理解，准确率较高。

C4.5 算法有如下缺点：

在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

此外，C4.5 只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法

运行。

分类决策树算法：

C4.5 算法是机器学习算法中的一种分类决策树算法，其核心算法是 ID3 算法。

分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树。

决策树的各部分是：

根：学习的事例集；

枝：分类的判定条件；

叶：分好的各个类。

1.3.1 C4.5 对 ID3 算法的改进

1) 熵的改进，加上了子树的信息。

Split_Infox(X)= -SUM( (|T|/|T

|)*LOG(|T

|/|T|))；

Gain ratio(X)= Gain(X)/Split_Infox(X);

2) 在输入数据上的改进

因素属性的值可以是连续量，C4.5 对其排序并分成不同的集合后按照 ID3 算法当作

离散量进行处理，但结论属性的值必须是离散值。

训练例的因素属性值可以是不确定的，以?表示，但结论必须是确定的。

3) 对已生成的决策树进行裁剪，减小生成树的规模。

2 The k-means algorithm（k 平均算法）

k-means algorithm 是一个聚类算法，把 n 个对象根据它们的属性分为 k 个分割，k <

n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的

中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。

假设有 k 个群组 S

, i=1,2,...,k。μ

是群组 S

内所有元素 x

的重心，或叫中心点。

k 平均聚类发明于 1956 年，该算法最常见的形式是采用被称为劳埃德算法 (Lloyd

algorithm)的迭代式改进探索法。劳埃德算法首先把输入点分成 k 个初始化分组，可以是随

机的或者使用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离

它最近的中心，重新确定分组。继续重复不断地计算中心并重新分组，直到收敛，即对象

不再改变分组（中心点位置不再改变）。

劳埃德算法和 k 平均通常是紧密联系的，但是在实际应用中，劳埃德算法是解决 k 平

均问题的启发式法则，对于某些起始点和重心的组合，劳埃德算法可能实际上收敛于错误

的结果。（上面函数中存在的不同的最优解）

虽然存在变异，但是劳埃德算法仍旧保持流行，因为它在实际中收敛非常快。实际上，

观察发现迭代次数远远少于点的数量。然而最近， David Arthur 和 Sergei Vassilvitskii 提出

存在特定的点集使得 k 平均算法花费超多项式时间达到收敛。

近似的 k 平均算法已经被设计用于原始数据子集的计算。

从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取

决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行 k 平均算法，

选择最优解。

k 平均算法的一个缺点是，分组的数目 k 是一个输入参数，不合适的 k 可能返回较差的

结果。另外，算法还假设均方误差是计算群组分散度的最佳参数。

3 SVM（支持向量机）

支持向量机，英文为 Support Vector Machine，简称 SV 机（论文中一般简称 SVM）。

它是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。

支持向量机属于一般化线性分类器。它们也可以被认为是提克洛夫规范化（Tikhonov

Regularization）方法的一个特例。这种分类器的特点是他们能够同时最小化经验误差与最

大化几何边缘区。因此支持向量机也被称为最大边缘区分类器。

在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似

然估计的算法，其中概率模型依赖于无法观测的隐藏变量（ Latent Variable）。最大期望经

常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。最大期望算法经过两个

步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量像能够观测到的一样包

含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找

到的最大似然的期望值从而计算参数的最大似然估计。M 步上找到的参数然后用于另外一

个 E 步计算，这个过程不断交替进行。

Vapnik 等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。

其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中

去，这种分类器被称为支持向量机(Support Vector Machine，简称 SVM)。支持向量机的提

出有很深的理论背景。支持向量机方法是在近年来提出的一种新方法，但是进展很快，已

经被广泛应用在各个领域之中。

SVM 的主要思想可以概括为两点：(1) 它是针对线性可分情况进行分析，对于线性不

可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征

空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分

析成为可能；(2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得

学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。

在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最

简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支

持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多

数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作

为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。

支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超

平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超

平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极

好的指南是 C.J.C Burges 的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持

向量机和其他分类器进行了比较。

有很多个分类器(超平面）可以把数据分开，但是只有一个能够达到最大分割。

我们通常希望分类的过程是一个机器学习的过程。这些数据点并不需要是中的点，

而可以是任意 (统计学符号)中或者 (计算机科学符号) 的点。我们希望能够把这些点

通过一个 n-1 维的超平面分开，通常这个被称为线性分类器。有很多分类器都符合这个要

求，但是我们还希望找到分类最佳的平面，即使得属于两个不同类的数据点间隔最大的那

个面，该面亦称为最大间隔超平面。如果我们能够找到这个面，那么这个分类器就称为最

大间隔分类器。

设样本属于两个类，用该样本训练 SVM 得到的最大间隔超平面。在超平面上的样本

点也称为支持向量。

SVM 的优势：

由于支持向量机方法是建立在统计学习理论的 VC 维理论和结构风险最小原理基础上

的，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习

能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力

(Generalizatin Ability)。支持向量机方法的几个主要优点是：

 可以解决小样本情况下的机器学习问题；

 可以提高泛化性能；

 可以解决高维问题；

 可以解决非线性问题；

 可以避免神经网络结构选择和局部极小点问题。

4 贝叶斯（Bayes）分类器

贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概

率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。目前

研究较多的贝叶斯分类器主要有四种，分别是：Naive Bayes、TAN、BAN 和 GBN。

贝叶斯网络是一个带有概率注释的有向无环图，图中的每一个结点均表示一个随机变

量，图中两结点间若存在着一条弧，则表示这两结点相对应的随机变量是概率相依的，反

之则说明这两个随机变量是条件独立的。网络中任意一个结点 X 均有一个相应的条件概率

表(Conditional Probability Table，CPT)，用以表示结点 X 在其父结点取各可能值时的条件

概率。若结点 X 无父结点，则 X 的 CPT 为其先验概率分布。贝叶斯网络的结构及各结点

的 CPT 定义了网络中各变量的概率分布。

贝叶斯分类器是用于分类的贝叶斯网络。该网络中应包含类结点 C，其中 C 的取值来

自于类集合( c

, c

, ... , c

)，还包含一组结点 X = ( X

, X

, ... , X

)，表示用于分类的特征。

对于贝叶斯网络分类器，若某一待分类的样本 D，其分类特征向量为 x = ( x

, x

, ... , x

) ，

则样本 D 属于类别 c

的概率为 P( C = c

| X = x) = P( C = c

| X

= x

, X

= x

, ... , X

= x

) ，(

i = 1 ,2 , ... , m) 。

而由贝叶斯公式可得：P( C = c

| X = x) = P( X = x | C = c

) P( C = c

) / P( X = x)

其中，P( C = c

) 可由领域专家的经验得到，称为先验概率；而 P( X = x | C = c

) 和 P( X

= x) 的计算则较困难；P( C = c

| X = x)称为后验概率。

应用贝叶斯网络分类器进行分类主要分成两阶段。第一阶段是贝叶斯网络分类器的学

习，即从样本数据中构造分类器；第二阶段是贝叶斯网络分类器的推理，即计算类结点的

条件概率，对分类数据进行分类。这两个阶段的时间复杂性均取决于特征值间的依赖程度

甚至可以是 NP 完全问题（世界七大数学难题之一），因而在实际应用中，往往需要对贝

叶斯网络分类器进行简化。根据对特征值间不同关联程度的假设，可以得出各种贝叶斯分

类器，Naive Bayes、TAN、BAN、GBN 就是其中较典型、研究较深入的贝叶斯分类器。

4.1 朴素贝叶斯（Naive Bayes）分类器

分类是将一个未知样本分到几个预先已知类的过程。数据分类问题的解决是一个两步

过程：第一步，建立模型，描述预先的数据集或概念集。通过分析由属性/特征描述的样本

（或实例，对象等）来构造模型。假定每一个样本都有一个预先定义的类，由一个被称为

类标签的属性确定。为建立模型而被分析的数据元组形成训练数据集，该步也称作有指导

的学习。

剩余44页未读，继续阅读

评论收藏

内容反馈

l546753716

粉丝: 0
资源: 9

数据挖掘之经典算法（非常实用）

数据挖掘原理与算法

数据挖掘与算法

数据挖掘原理与算法（邵峰晶 于忠清）

数据挖掘原理与算法part1

数据挖掘原理与算法part2

数据挖掘原理与算法（书籍）

数据仓库与数据挖掘技术

数据挖掘算法,随便看看

数据挖掘试题

写给程序员的数据挖掘实践指南

数据挖掘技术在Web 中的应用

数据挖掘的基础使用教程

C4_5数据挖掘算法的改进及其应用.caj

论文研究-聚类后的关联规则快速更新算法研究.pdf

数据挖掘概念与技术中文版 韩家炜

MATLAB数据挖掘与数据分析技术系列培训课件 第1讲_MATLAB快速入门 共38页.pdf

Python基于机器学习实现的股票价格预测、股票预测源码+数据集，机器学习大作业

身份证前6位对应的省市区代码（超详细）

两阶段鲁棒优化/综合能源系统/需求响应/微电网/多目标优化/优化调度matlab-yalmip-cplex/gurobi文章复现

SPSS中介效应分析插件（Process和mediate插件）

2022年mathercup数学建模比赛d题题解

2001-2021中国城市统计年鉴数据（EXCEL数据面板）

2017-2021年全国10m精度土地利用分类数据集

新闻数据集（对应新闻文本分类案例）

新出血性脑卒中临床智能诊疗建模.md

R语言期末大作业（全面带报告，带数据集）

中国城市统计年鉴面板数据 来源：各城市面板数据

小O地图EXE版0.9.4.0

5-8抖音数据分析数据集

最新资源

数据挖掘原理与算法（邵峰晶于忠清）

数据挖掘概念与技术中文版韩家炜

MATLAB数据挖掘与数据分析技术系列培训课件第1讲_MATLAB快速入门共38页.pdf

中国城市统计年鉴面板数据来源：各城市面板数据