上篇传送门：https://wenku.my7c.com/article/296322476823114240?productLineId=1

一、朴素贝叶斯算法

朴素贝叶斯算法依据概率论中贝叶斯定理建立模型，前提假设各个特征之间相互独立（这也是正式“朴素”的含义），这个假设非常极端，因为实际场景中多个特征一般存在相关性，特征相对独立的假设使得算法变得简单，因此在特征值有强相关性的场景中容易出现分类不准的问题。

三、数据探索

四、建立模型

一、算法描述

所谓物以类聚-人以群分，“类”指的是具有相似性的集合，聚类是指将数据集划分为若干类，使得各个类之内的数据最为相似，而各个类之间的数据相似度差别尽可能的大。聚类分析就是以相似性为基础，在一个聚类中的模式之间比不在同一个聚类中的模式之间具有更多的相似性。对数据集进行聚类划分，属于无监督学习。

K-Means是最常用且简单的聚类算法，最大特点是好理解，运算速度快，时间复杂度近于线性，适合挖掘大规模数据集。但是只能应用于连续型的数据，并且一定要在聚类前需要手工指定要分成几类；

K-Means采用距离作为相似性指标，从而发现给定数据集中的K个类，且每个类的中心是根据类中所有数值的均值得到的，每个类的中心用聚类中心来描述。对于给定的一个（包含n个一维以及一维以上的数据点的）数据集X以及要得到的类别数量K，选取欧式距离作为相似度指标，聚类目标是使得类的聚类平方和最小，即最小化：

二、K-Means算法流程：

1. 随机选取K个样本作为聚类中心；

2. 计算各样本与各个聚类中心的距离；

3. 将各样本回归于与之距离最近的聚类中心；

4. 求各个类的样本的均值，作为新的聚类中心；

5. 判定：若类中心不再发生变动或者达到迭代次数，算法结束，否则回到第二步。

n_clusters：整型，缺省值=8 ，生成的聚类数。

max_iter：整型，缺省值=300 ，执行一次k-means算法所进行的最大迭代数。

n_init：整型，缺省值=10 ，用不同的聚类中心初始化值运行算法的次数，最终解是在inertia意义下选出的最优结果。

init：有三个可选值：’k-means++’， ‘random’，或者传递一个ndarray向量，此参数指定初始化方法，默认值为 ‘k-means++’。（１）‘k-means++’ 用一种特殊的方法选定初始聚类，可加速迭代过程的收敛（２）‘random’ 随机从训练数据中选取初始质心。（３）如果传递的是一个ndarray，则应该形如 (n_clusters, n_features) 并给出初始质心。

precompute_distances：三个可选值，‘auto’，True 或者 False，预计算距离，计算速度更快但占用更多内存。（１）‘auto’：如果 样本数乘以聚类数大于 12million 的话则不预计算距离。（２）True：总是预先计算距离。（３）False：永远不预先计算距离。

tol：float类型，默认值= 1e-4　与inertia结合来确定收敛条件。

n_jobs：整形数。　指定计算所用的进程数。内部原理是同时进行n_init指定次数的计算。（１）若值为 -1，则用所有的CPU进行运算。若值为1，则不进行并行运算。（２）若值小于-1，则用到的CPU数为(n_cpus + 1 + n_jobs)。因此如果 n_jobs值为-2，则用到的CPU数为总CPU数减1。

random_state：整型或 numpy.RandomState 类型，可选，用于初始化质心的生成器（generator）。如果值为一个整数，则确定一个seed。此参数默认值为numpy的随机数生成器。

copy_x：布尔型，默认值=True 　　，当我们precomputing distances时，将数据中心化会得到更准确的结果。如果把此参数值设为True，则原始数据不会被改变。如果是False，则会直接在原始数据上做修改并在函数返回值时将其还原。但是在计算过程中由于有对数据均值的加减运算，所以数据返回后，原始数据和计算前可能会有细小差别。

一、关联规则简介

关联规则挖掘可以让我们从数据集中发现项与项之间的关系，它在我们的生活中有很多应用场景，“购物篮分析”就是一个常见的场景，这个场景可以从消费者交易记录中发掘商品与商品之间的关联关系，进而通过商品捆绑销售或者相关推荐的方式带来更多的销售量。

1. 搞懂关联规则中的几个重要概念：支持度、置信度、提升度

2. Apriori 算法的工作原理

3. 在实际工作中，我们该如何进行关联规则挖掘

二、关联规则中重要的概念

我举一个超市购物的例子，下面是几名客户购买的商品列表：

支持度

支持度是个百分比，它指的是某个商品组合出现的次数与总次数之间的比例。支持度越高，代表这个组合出现的频率越大。

我们看啤酒出现了3次，那么5笔订单中啤酒的支持度是3/5=0.6。同理，尿布出现了5次，那么尿布的支持度是5/5=1。尿布和啤酒同时出现的支持度是3/6=0.6。

置信度

它指的就是当你购买了商品 A，会有多大的概率购买商品 B。

我们可以看上面的商品，购买尿布的同时又购买啤酒的订单数是3，购买啤酒的订单数是3，那么（尿布->啤酒）置信度= 3/3=1。

再看购买了啤酒同时购买尿布的订单数是3，购买尿布的订单数是5，那么（啤酒->尿布）置信度=3/5=0.6。

提升度

提升度代表的是“商品 A 的出现，对商品 B 的出现概率提升的”程度。所以我们在做商品推荐的时候，重点考虑的是提升度。

我们来看提升度公式：

怎么解读1.67这个数值呢？

1. 提升度 (A→B)>1：代表有提升

2. 提升度 (A→B)=1：代表有没有提升，也没有下降

3. 提升度 (A→B)<1：代表有下降。

其实看上面提升度的公式，我们就可以理解，也就是AB同时出现的次数越多，单独出现B的次数越少，那么支持度也就越大也就是B的出现总是伴随着A的出现，那么A对B出现的概率就越有提升！

三、Apriori 的工作原理

我们一起来看下经典的关联规则 Apriori 算法是如何工作的。

Apriori 算法其实就是查找频繁项集 (frequent itemset) 的过程，所以我们需要先了解是频繁项集。

频繁项集就是支持度大于等于最小支持度阈值的项集，所以小于最小值支持度的项目就是非频繁项集，而大于等于最小支持度的项集就是频繁项集。

下面我们来举个栗子：

假设我随机指定最小支持度是0.2。首先，我们先计算单个商品的支持度：

因为最小支持度是 0.2，所以你能看到商品 鸡蛋 是不符合最小支持度的，不属于频繁项集，于是经过筛选商品的频繁项集如下：

在这个基础上，我们将商品两两组合，得到两个商品的支持度：

筛选大于最小支持度（0.2）的数据后

在这个基础上，我们再将商品三个组合，得到三个商品的支持度：

筛选大于最小支持度（0.2）的数据后

在这个基础上，我们将商品四个组合，得到四个商品的支持度：

再次筛选大于最小支持度（0.2）数据的话，就全删除了，那么，此时算法结束，上一次的结果就是我们要找的频繁项，也就是{牛奶、面包、尿布}、{面包、尿布、啤酒}。

我们来总结一下上述Apriori算法过程：

1. K=1，计算 K 项集的支持度

2. 筛选掉小于最小支持度的项集

3. 如果项集为空，则对应 K-1 项集的结果为最终结果

4. 否则 K=K+1，重复 1-3 步

我们可以看到 Apriori 在计算的过程中有以下几个缺点：

1. 可能产生大量的候选集。因为采用排列组合的方式，把可能的项集都组合出来了

2. 每次计算都需要重新扫描数据集，来计算每个项集的支持度

这就好比我们数据库中的“全表扫描”查询一样，非常浪费IO和时间。在数据库中我们都知道使用索引来快速检索数据，那Apriori 能优化吗？

四、Apriori 的改进算法：FP-Growth 算法

FP-growth算法是基于Apriori原理的，通过将数据集存储在FP树上发现频繁项集，但不能发现数据之间的关联规则。FP-growth算法只需要对数据库进行两次扫描，而Apriori算法在求每个潜在的频繁项集时都需要扫描一次数据集，所以说Apriori算法是高效的。其中算法发现频繁项集的过程是：(1)构建FP树；(2)从FP树中挖掘频繁项集。

创建项头表

概念知识不在这凑字数了，我们直接来干货！假设我们从以下数据中来挖掘频繁项。

首先创建，项头表，这一步的流程是先扫描一遍数据集，对于满足最小支持度的单个项按照支持度从高到低进行排序，这个过程中删除了不满足最小支持度的项（假设最小支持度是0.2）。

构建FP树

整个流程是需要再次扫描数据集，对于每一条数据，按照支持度从高到低的顺序进行创建节点（也就是第一步中项头表中的排序结果），节点如果存在就将计数 count+1，如果不存在就进行创建。同时在创建的过程中，需要更新项头表的链表。

先把原始数据按照支持度排序，那么原始数据变化如下：

下面我们把以上每行数据，按照顺序插入到FP树中，注意FP树的根节点记为 NULL 节点。

接下来插入第二行数据，由于第二行数据第一个数据也是B，和已有的树结构重合，那么我们保持原来树结构中的B位置不变，同时计数加1，C、D是新增数据，那么就会有新的树分叉，结果如下图：

以此类推，读取下面的三行数据到FP树中

最后生成的FP数如下：

根据FP数挖掘频繁项

我们终于把FP树建立好了，那么如何去看这颗树呢？得到 FP 树后，需要对每一个频繁项，逐个挖掘频繁项集。具体过程为：首先获得频繁项的前缀路径，然后将前缀路径作为新的数据集，以此构建前缀路径的条件 FP 树。然后对条件 FP 树中的每个频繁项，获得前缀路径并以此构建新的条件 FP 树。不断迭代，直到条件 FP 树中只包含一个频繁项为止（反正我第一次看完这句话是没理解）。

FP树是从下往上看了，也就是根据子节点找父节点，接下来还是来图解~

首先，我们看包含A的频繁项：

我们可以看到包含A的树有两个，我们先看树2，可以得到路径{B:2,C:2}，此处的2是根据A出现的次数定的。接着我们创建FP树，具体的创建过程和上面创建 FP 树的过程一样，如下图：

注意此时头指针表中包含两个元素，所以对每个元素，需要获得前缀路径，并将前缀路径创建成条件 FP 树，直到条件 FP 树中只包含一个元素时返回。

• 对元素 B，获得前缀路径为{}，则频繁项集返回{A:2,B:2};

• 对元素 C，获得前缀路径{B:2}，则将前缀路径创建成条件 FP 树，如下图  所示。

  注意此时条件 FP 树中只包含一个元素，故返回频繁项集{A:2,C:2,B:2}。由于元素 C 也是频繁项，所以{A:2,C:2}也是频繁项集。

再加上{A:2}本身就是频繁项集，所以 A 对应的频繁项集有：{A:2},{A:2,C:2} ,{A:2,B:2},{A:2,C:2,B:2}。

同理，我们来看树1，树1比较简单，就一个路径{B:1}，根据上述方法我们得到此分支频繁项为{A:1,B:1},{A:1}。

综上，我们可以看到两个分支都包含频繁项{A,B},{A}的，此时我们进行合并两个分支，得到包含A的频繁项：{A:3},{A:3,B:3},{A:2,C:2} ,{A:2,C:2,B:2}，我们用出现的次数转换下，即 (A,): 3, (A, B): 3, (A, C): 2, (A, B, C): 2。

同理，按照上述方法，我们可以依次找到包含B的频繁项是(D): 2, (C, D): 2, (B, D): 2, (B, C, D): 2,  (C): 4, (B, C): 4, (B): 5。

五、实践总结

经典的算法，很多大神已经实现，我们直接拿来用就行了，比如上面的FP-GROWTH算法，介绍一款专门的包pyfpgrowth。

代码：

文章来源：微信公众号【数据社】

非常专业