数据挖掘常用算法总结

您所在的位置：网站首页 › 数据库的知识发现 › 数据挖掘常用算法总结

数据挖掘常用算法总结

2024-05-29 19:16| 来源: 网络整理| 查看: 265

算法总结

个人博客：www.xiaobeigua.icu

第一章 (1)数据挖掘概念。

数据挖掘是在大型数据库中自动发现有用信息的过程

数据挖掘是数据库中知识发现（kdd）必不可少的部分

(2)数据库技术自然的演化, 有巨大的需求和广阔的应用。

知识发现的过程包含了数据清洗, 数据集成, 数据选择, 数据转换, 数据挖掘, 模式评估和知识表现。

数据挖掘功能: 特征, 区别, 关联, 分类, 聚类, 孤立点和趋势分析等.

(3)数据挖掘系统和体系架构：

(4)数据挖掘主要问题 1、分类问题

分类问题属于预测性的问题，但是它跟普通预测问题的区别在于其预测的结果是类别（如A、B、C三类）而不是一个具体的数值（如55、65、75……）。

方法：决策树、Logistic回归、判别分析、神经网络、Chi-square、Gini等相关知识

2、聚类问题

聚类问题不属于预测性的问题，它主要解决的是把一群对象划分成若干个组的问题。划分的依据是聚类问题的核心。所谓“物以类聚，人以群分”，故得名聚类。

方法：聚类分析、系统聚类、K-means聚类、欧氏距离、马氏距离等知识。

3、关联问题

说起关联问题，可能要从“啤酒和尿布”说起了。有人说啤酒和尿布是沃尔玛超市的一个经典案例，也有人说，是为了宣传数据挖掘/数据仓库而编造出来的虚构的“托”。不管如何，“啤酒和尿布”给了我们一个启示：世界上的万事万物都有着千丝万缕的联系，我们要善于发现这种关联。

方法：关联规则、apriror算法中等相关知识

4、预测问题

a此处说的预测问题指的是狭义的预测，并不包含前面阐述的分类问题，因为分类问题也属于预测。一般来说我们谈预测问题主要指预测变量的取值为连续数值型的情况。

例如天气预报预测明天的气温、国家预测下一年度的GDP增长率、电信运营商预测下一年的收入、用户数等？

方法：一元线性回归分析、多元线性回归分析、最小二乘法等相关知识。

第二章

数据预处理对数据仓库和数据挖掘来说都是大问题。

描述性数据汇总是预处理对数据质量的要求。

数据预处理：数据清洗、数据集成、数据规约、特征提取、离散化处理

第三章 (1)关联规则挖掘相关基本概念和路线图

关联规则挖掘（Association rule mining）是数据挖掘中最活跃的研究方法之一，可以用来发现事情之间的联系，最早是为了发现超市交易数据库中不同的商品之间的关系。

关联规则挖掘的定义：给定一个交易数据集T，找出其中所有支持度support >= min_support、自信度confidence >= min_confidence的关联规则。

(2)有效的和可伸缩的频繁项集挖掘方法

FP-growth算法

(3)Apriori算法思想、步骤、优缺点

Apriori 算法是一种最有影响力的挖掘布尔关联规则的频繁项集的算法，它是由Rakesh Agrawal 和RamakrishnanSkrikant 提出的。它使用一种称作逐层搜索的迭代方法，k- 项集用于探索（k+1）- 项集。首先，找出频繁 1- 项集的集合。该集合记作L1。L1 用于找频繁2- 项集的集合 L2，而L2 用于找L2，如此下去，直到不能找到 k- 项集。每找一个 Lk 需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori 性质的重要性质用于压缩搜索空间。其运行定理在于一是频繁项集的所有非空子集都必须也是频繁的，二是非频繁项集的所有父集都是非频繁的。

Apriori算法过程分为两个步骤：

第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；

第二步利用频繁项集构造出满足用户最小信任度的规则。

具体做法就是：

首先找出频繁1-项集，记为L1；然后利用L1来产生候选项集C2，对C2中的项进行判定挖掘出L2，即频繁2-项集；不断如此循环下去直到无法发现更多的频繁k-项集为止。每挖掘一层Lk就需要扫描整个数据库一遍。

Apriori算法的优点：简单、易理解、数据要求低，

Apriori算法的缺点：

(1)在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;

(2)每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法。

第四章 (1)分类和预测概念

分类是用于预测数据对象的离散类别的，需要预测的属性值是离散的、无序的。

预测则是用于预测数据对象的连续取值的，需要预测的属性值是连续的、有序的。

(2)基于决策树归纳的分类，ID3，C4.5算法思想、步骤、优缺点 1(决策树归纳算法)

决策树（Decision Tree，DT）分类法是一个简单且广泛使用的分类技术。决策树是一个树状预测模型，它是由结点和有向边组成的层次结构。树中包含3种结点：根结点、内部结点和叶子结点。决策树只有一个根结点，是全体训练数据的集合。树中的一个内部结点表示一个特征属性上的测试，对应的分支表示这个特征属性在某个值域上的输出。一个叶子结点存放一个类别，也就是说，带有分类标签的数据集合即为实例所属的分类。ID）

2（ID3算法）

ID3基本思想：

ID3算法需要解决的问题是如何选择特征作为划分数据集的标准。在ID3算法中，选择信息增益最大的属性作为当前的特征对数据集分类。信息增益的概念将在下面介绍，通过不断的选择特征对数据集不断划分；

Id3基本步骤：

1. 计算类别信息熵

类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概念，熵越大，不确定性就越大，把事情搞清楚所需要的信息量就越多。

2. 计算每个属性的信息熵

每个属性的信息熵相当于一种条件熵。他表示的是在某种属性的条件下，各种类别出现的不确定性之和。属性的信息熵越大，表示这个属性中拥有的样本类别越不“纯”。

3. 计算信息增益

信息增益的 = 熵 - 条件熵，在这里就是类别信息熵 - 属性信息熵，它表示的是信息不确定性减少的程度。如果一个属性的信息增益越大，就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性，当然，选择该属性就可以更快更好地完成我们的分类目标。

信息增益就是ID3算法的特征选择指标。

ID3算法优缺点：

优点：

1.假设空间包含所有的决策树，搜索空间完整。

2.健壮性好，不受噪声影响。

3.可以训练缺少属性值的实例。

缺点:

1.ID3只考虑分类型的特征，没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。

2.ID3算法对于缺失值没有进行考虑。

3.没有考虑过拟合的问题。

ID3例子：

1.系统信息熵：（是，否为好瓜的两个属性）

2.每个特征的信息熵：（以色泽为例）（先计算出3 个属性的信息熵，依次为：青绿，乌黑，浅白）

然后，结合3 个属性，计算出特征为色泽的信息熵:

信息增益大，代表着熵小，所以确定性较高。

3得出决策结果

但是，当我们使用ID编号作为一个特征量的时候

´得到信息熵：

´信息增益为：

所以需要使用编号作为根节点吗？显然不可能。

3（C45算法）

C45主要思想：

用信息增益比来选择属性，克服了用信息增益选择属性是偏向选择去之多的属性的不足

在数的构造过程中进行剪枝

能够对连续的属性进行离散化处理

能够对不完整的数据进行处理

C45算法步骤(比id3多两步)

计算类别信息熵计算每个属性的信息熵计算信息增益计算属性信息分裂度量计算信息增益率

C4.5优点与缺点:

优点：产生的分类规则易于理解，准确率较高。缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

C4.5例子

1 计算类别信息熵

类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概念，熵越大，不确定性就越大，把事情搞清楚所需要的信息量就越多。

2. 计算每个属性的信息熵

3. 计算信息增益

信息增益就是ID3算法的特征选择指标。

但是我们假设这样的情况，每个属性中每种类别都只有一个样本，那这样属性信息熵就等于零，根据信息增益就无法选择出有效分类特征。所以，C4.5选择使用信息增益率对ID3进行改进。

4.计算属性分裂信息度量

用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息，我们把这些信息称为属性的内在信息（instrisic information）。信息增益率用信息增益 / 内在信息，会导致属性的重要性随着内在信息的增大而减小（也就是说，如果这个属性本身不确定性就很大，那我就越不倾向于选取它），这样算是对单纯用信息增益有所补偿。