TIP

本文主要是介绍 数据挖掘-十大经典算法 。

• 数据挖掘的十大经典算法 简介
• 一、C4.5
• 二、The k-means algorithm 即K-Means算法
• 三、 Support vector machines
• 四、The Apriori algorithm
• 五、最大期望(EM)算法
• 六、 PageRank
• 七、AdaBoost
• 八、 kNN: k-nearest neighbor classification
• 九、 Naive Bayes
• 十、 CART: 分类与回归树
• 【----------------------------】
• 从小白视角理解 数据挖掘十大算法
• 算法分类
• 一、PageRank
  • 原理
  • 比喻说明
• 二、Apriori（关联分析）
  • 原理
  • 1.支持度
  • 2.置信度
  • 3.提升度
  • 4.频繁项集
  • 计算过程
  • 扩展：FP-Growth 算法
  • 比喻说明
• 三、AdaBoost
  • 原理
  • 计算过程
  • 比喻说明
• 四、C4.5（决策树）
  • 原理
  • 比喻说明
• 五、CART（决策树）
  • 什么是分类树、回归树？
  • 原理
  • 比喻说明
• 六、朴素贝叶斯（条件概率）
  • 原理
  • 比喻说明
• 七、SVM
  • 原理
  • 比喻说明
• 八、KNN（聚类）
  • 原理
  • 计算步骤
  • 比喻说明
• 九、K-Means（聚类）
  • 原理
  • 比喻说明
  • 1.选老大
  • 2.Kmeans和Knn的区别
• 十、EM（聚类）
  • EM和K-Means的区别：
  • 原理
  • 比喻说明
• 参考文章

数据挖掘的十大经典算法 简介

一、C4.5

C4.5，是机器学习算法中的一个分类决策树算法，它是决策树(决策树也就是做决策的节点间的组织方式像一棵树，其实是一个倒树)核心算法ID3的改进算法，所以基本上了解了一半决策树构造方法就能构造它。决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的分类条件。

二、The k-means algorithm 即K-Means算法

k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割(k < n)。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。

三、 Support vector machines

支持向量机，英文为Support Vector Machine，简称SV机。它是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。

四、The Apriori algorithm

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。

其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

五、最大期望(EM)算法

在统计计算中，最大期望 （EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。

六、 PageRank

PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里?佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。PageRank根据网站的外部链接和内部链接的数量和质量，衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票， 被链接的越多，就意味着被其他网站投票越多。

七、AdaBoost

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

八、 kNN: k-nearest neighbor classification

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

九、 Naive Bayes

在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。

朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。

但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。

十、 CART: 分类与回归树

CART, Classification and Regression Trees。 在分类树下面有两个关键的思想：第一个是关于递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。

【----------------------------】

从小白视角理解 数据挖掘十大算法 (opens new window)

算法分类

• 连接分析：PageRank
• 关联分析：Apriori
• 分类算法：C4.5，朴素贝叶斯，SVM，KNN，Adaboost，CART 聚类算法：K-Means，EM

一、PageRank

当一篇论文被引用的次数越多，证明这篇论文的影响力越大。

一个网页的入链越多，入链越优质，网页的质量越高

原理

网页影响力=阻尼影响力+所有入链集合页面的加权影响力之和

• 一个网页的影响力：所有入链的页面的加权影响力之和
• 一个网页对其他网页的影响力贡献为：自身影响力/出链数量
• 用户并不都是按照跳转链接的方式来上网，还有其他的方式，比如直接输入网址访问， 所以需要设定阻尼因子，代表了用户按照跳转链接来上网的概率

比喻说明

1. 微博 一个人的微博粉丝数不一定等于他的实际影响力，还需要看粉丝的质量如何。 如果是僵尸粉没什么用，但如果是很多大V或者明星关注，影响力很高。
2. 店铺的经营 顾客比较多的店铺质量比较好，但是要看看顾客是不是托。
3. 兴趣 在感兴趣的人或事身上投入了相对多的时间，对其相关的人事物也会投入一定的时间。 那个人或事，被关注的越多，它的影响力/受众也就越大。

关于阻尼因子

• 1. 通过你的邻居的影响力来评判你的影响力，但是如果不能通过邻居来访问你，并不代表你没有影响力，因为可以直接访问你，所以引入阻尼因子的概念
• 2. 海洋除了有河流流经，还有雨水，但是下雨是随机的
• 3. 提出阻尼系数，还是为了解决某些网站明明存在大量出链（入链），但是影响力却非常大的情形。 出链例子：hao123导航网页，出链极多入链极少 入链例子：百度谷歌等搜索引擎，入链极多出链极少。

二、Apriori（关联分析）

关联关系挖掘，从消费者交易记录中发掘商品与商品之间的关联关系

原理

1.支持度

某个商品组合出现的次数与总次数之间的比例

5次购买，4次买了牛奶，牛奶的支持度为4/5=0.8

5次购买，3次买了牛奶+面包，牛奶+面包的支持度为3/5=0.6

2.置信度

购买了商品A，有多大概率购买商品B，A发生的情况下B发生的概率是多少

买了4次牛奶，其中2次买了啤酒，(牛奶->啤酒)的置信度为2/4=0.5

买了3次啤酒，其中2次买了牛奶，(啤酒->牛奶)的置信度为2/3-0.67

3.提升度

衡量商品A的出现，对商品B的出现 概率提升的程度

提升度(A->B)=置信度(A->B)/支持度(B)

提升度>1，有提升； 提升度=1，无变化； 提升度<1，下降

4.频繁项集

• 项集：可以是单个商品，也可以是商品组合
• 频繁项集是支持度大于最小支持度（Min Support）的项集

计算过程

-1. 从K=1开始，筛选频繁项集。 -2. 在结果中，组合K+1项集，再次筛选 -3. 循环1、2步。直到找不到结果为止，K-1项集的结果就是最终结果。

扩展：FP-Growth 算法

Apriori 算法需要多次扫描数据库，性能低下，不适合大数据量

FP-growth算法，通过构建 FP 树的数据结构，将数据存储在 FP 树中，只需要在构建 FP 树时扫描数据库两次，后续处理就不需要再访问数据库了。

比喻说明

• 啤酒和尿不湿摆在一起销售
• 沃尔玛通过数据分析发现，美国有婴儿的家庭中，一般是母亲在家照顾孩子，父亲去超市买尿不湿。
• 父亲在购买尿不湿时，常常会顺便搭配几瓶啤酒来犒劳自己，于是，
• 超市尝试推出了将啤酒和尿不湿摆在一起的促销手段，这个举措居然使尿不湿和啤酒的销量都大幅增加。

三、AdaBoost

原理

简单的说，多个弱分类器训练成为一个强分类器。

将一系列的弱分类器以不同的权重比组合作为最终分类选择

计算过程

• 1. 初始化基础权重
• 2. 奖权重矩阵，通过已的分类器计算错误率，选择错误率最低的为最优分类器
• 3. 通过分类器权重公式，减少正确样本分布，增加错误样本分布，得到新的权重矩阵和当前k轮的分类器权重
• 4. 将新的权重矩阵，带入上面的步骤2和3，重新计算权重矩阵
• 5. 迭代N轮，记录每一轮的最终分类器权重，得到强分类器

比喻说明

1. 利用错题提升学习效率

• 做正确的题，下次少做点，反正都会了
• 做错的题，下次多做点，集中在错题上
• 随着学习的深入，做错的题会越来越少

2. 合理跨界提高盈利

• 苹果公司，软硬结合，占据了大部分的手机市场利润，两个领域的知识结合起来产生新收益

四、C4.5（决策树）

决策就是对于一个问题，有多个答案，选择答案的过程就是决策。 C4.5算法是用于产生决策树的算法，主要用于分类 C4.5使用信息增益率做计算（ID3算法使用信息增益做计算）

原理

C4.5选择最有效地方式对样本集进行分裂，分裂规则是分析所有属性的信息增益率 信息增益率越大，意味着这个特征分类的能力越强，我们就要优先选择这个特征做分类

比喻说明

挑西瓜

拿到一个西瓜，先判断它的纹路，如果很模糊，就认为这不是好瓜，如果它清晰，就认为它是一个好瓜，如果它稍稍模糊，就考虑它的密度，密度大于某个值，就认为它是好瓜，否则就是坏瓜。

五、CART（决策树）

CART：Classification And Regression Tree，中文叫分类回归树，即可以做分类也可以做回归。

什么是分类树、回归树？

• 分类树：处理离散数据，也就是数据种类有限的数据，输出的是样本的类别 。
• 回归树：可以对连续型的数值进行预测，输出的是一个数值，数值在某个区间内都有取值的可能。
• 回归问题和分类问题的本质一样，都是针对一个输入做出一个输出预测，其区别在于输出变量的类型

原理

• CART分类树 与C4.5算法类似，只是属性选择的指标是基尼系数。 基尼系数反应了样本的不确定度，基尼系数越小，说明样本之间的差异性小，不确定程度低。 分类是一个不确定度降低的过程，CART在构造分类树的时候会选择基尼系数最小的属性作为属性的划分。
• CART 回归树 采用均方误差或绝对值误差为标准，选取均方误差或绝对值误差最小的特征

比喻说明

• 分类：预测明天是阴、晴还是雨
• 回归：预测明天的气温是多少度

六、朴素贝叶斯（条件概率）

朴素贝叶斯是一种简单有效的常用分类算法，计算未知物体出现的条件下各个类别出现的概率，取概率最大的分类

原理

假设输入的不同特征之间是独立的，基于概率论原理，通过先验概率P(A)、P(B)和条件概率推算出后概率出P(A|B)

• P(A)：先验概率，即在B事件发生之前，对A事件概率的一个判断。
• P(B|A)：条件概率，事件 B 在另外一个事件 A 已经发生条件下的发生概率
• P(A|B)：后验概率，即在B事件发生之后，对A事件概率的重新评估。

比喻说明

给病人分类

症状	职业	疾病
打喷嚏	护士	感冒
打喷嚏	农夫	过敏
头痛	建筑工人	脑震荡
头痛	建筑工人	感冒
打喷嚏	教师	感冒
头痛	教师	脑震荡

给定一个新病人，是一个打喷嚏的建筑工人，计算他患感冒的概率

七、SVM

SVM： Support Vector Machine，中文名为支持向量机，是常见的一种分类方法，最初是为二分类问题设计的，在机器学习中，SVM 是有监督的学习模型。

• 什么是有监督学习和无监督学习 ？
• 有监督学习：即在已有类别标签的情况下，将样本数据进行分类。
• 无监督学习：即在无类别标签的情况下，样本数据根据一定的方法进行分类，即聚类，分类好的类别需要进一步分析后，从而得知每个类别的特点。

原理

找到具有最小间隔的样本点，然后拟合出一个到这些样本点距离和最大的线段/平面。

• 硬间隔：数据是线性分布的情况，直接给出分类
• 软间隔：允许一定量的样本分类错误。
• 核函数：非线性分布的数据映射为线性分布的数据。

比喻说明

• 1.分隔桌上一堆红球和篮球

用一根线将桌上的红球和蓝球分成两部分

• 2.分隔箱子里一堆红球和篮球

用一个平面将箱子里的红球和蓝球分成两部分

八、KNN（聚类）

机器学习算法中最基础、最简单的算法之一，既能分类也能回归，通过测量不同特征值之间的距离来进行分类。

原理

计算待分类物体与其他物体之间的距离，对于K个最近的邻居，所占数量最多的类别，预测为该分类对象的类别

计算步骤

• 1. 根据场景，选取距离计算方式，计算待分类物体与其他物体之间的距离
• 2. 统计距离最近的K个邻居
• 3. 对于K个最近的邻居，所占数量最多的类别，预测为该分类对象的类别

比喻说明

近朱者赤，近墨者黑

九、K-Means（聚类）

K-means是一个聚类算法，是无监督学习，生成指定K个类，把每个对象分配给距离最近的聚类中心

原理

• 1.随机选取K个点为分类中心点
• 2.将每个点分配到最近的类，这样形成了K个类
• 3.重新计算每个类的中心点。比如都属于同一个类别里面有10个点，那么新的中心点就是这10个点的中心点，一种简单的方式就是取平均值。

比喻说明

1.选老大

• 大家随机选K个老大，谁离得近，就是那个队列的人（计算距离，距离近的人聚合在一起）
• 随着时间的推移，老大的位置在变化（根据算法，重新计算中心点），直到选出真正的中心老大（重复，直到准确率最高）

2.Kmeans和Knn的区别

• Kmeans开班选老大，风水轮流转，直到选出最佳中心老大
• Knn小弟加队伍，离那个班相对近，就是那个班的

十、EM（聚类）

EM 的英文是 Expectation Maximization，所以 EM 算法也叫最大期望算法，也是聚类算法的一种。

EM和K-Means的区别：

• 1. EM是计算概率，KMeans是计算距离。
• 2. EM属于软聚类，同一样本可能属于多个类别；而K-Means属于硬聚类，一个样本只能属于一个类别。所以前者能够发现一些隐藏的数据。

原理

先估计一个大概率的可能参数，然后再根据数据不断地进行调整，直到找到最终的确认参数

比喻说明

菜称重。

很少有人用称对菜进行称重，再计算一半的分量进行平分。

大部分人的方法是：

• 1. 先分一部分到碟子 A 中，再把剩余的分到碟子 B 中
• 2. 观察碟子 A 和 B 里的菜是否一样多，哪个多就匀一些到少的那个碟子里
• 3. 然后再观察碟子 A 和 B 里的是否一样多，重复下去，直到份量不发生变化为止。

到这里，10大算法都已经说完了，其实一般来说，常用算法都已经被封装到库中了，只要new出相应的模型即可。

参考文章

• https://zhuanlan.zhihu.com/p/69106308
• https://www.cnblogs.com/chenqionghe/p/12301905.html