黑马程序员技术交流社区

标题: 【上海校区】机器学习算法（10）之数据挖掘算法之Apriori... [打印本页]

作者: 不二晨 时间: 2018-10-19 09:49
标题: 【上海校区】机器学习算法（10）之数据挖掘算法之Apriori...
前言：数据挖掘与机器学习

      有时候，人们会对机器学习与数据挖掘这两个名词感到困惑。如果你翻开一本冠以机器学习之名的教科书，再同时翻开一本名叫数据挖掘的教材，你会发现二者之间有相当多重合的内容。比如机器学习中也会讲到决策树和支持向量机，而数据挖掘的书里也必然要在决策树和支持向量机上花费相当的篇幅。可见二者确有相当大的重合面，但如果细研究起来，二者也的确是各自不同的领域。

   大体上看，数据挖掘可以视为数据库、机器学习和统计学三者的交叉。简单来说，对数据挖掘而言，数据库提供了数据管理技术，而机器学习和统计学则提供了数据分析技术。所以你可以认为数据挖掘包含了机器学习，或者说机器学习是数据挖掘的弹药库中一类相当庞大的弹药集。既然是一类弹药，其实也就是在说数据挖掘中肯定还有其他非机器学习范畴的技术存在。Apriori算法就属于一种非机器学习的数据挖掘技术。

   我们都知道数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。而机器学习是以数据为基础，设法构建或训练出一个模型，进而利用这个模型来实现数据分析的一类技术。这个被训练出来的机器学习模型当然也可以认为是我们从数据中挖掘出来的那些潜在的、有意义的信息和知识。在非机器学习的数据挖掘技术中，我们并不会去建立这样一个模型，而是直接从原数据集入手，设法分析出隐匿在数据背后的某些信息或知识。

关联规则的故事背景

在描述有关关联规则的一些细节之前，先来看一个有趣的故事： "尿布与啤酒"的故事。

   在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是："跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在"尿布与啤酒"背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。

1、什么是关联规则挖掘？

关联规则挖掘：从交易数据中发现“买了X还会同时买Y”这样的规则的分析方法
关联规则挖掘又称为“购物篮分析”，Market Basket Analysis (MBA)
关联规则挖掘属于非监督学习算法
   许多商业企业在日复一日的运营中积聚了大量的交易数据。例如，超市的收银台每天都收集大量的顾客购物数据。例如，下表给出了一个这种数据集的例子，我们通常称其为购物篮交易（market basket transaction)。表中每一行对应一个交易，包含一个唯一标识TID和特定顾客购买的商品集合。零售商对分析这些数据很感兴趣，以便了解其顾客的购买行为。可以使用这种有价值的信息来支持各种商业中的实际应用，如市场促销，库存管理和顾客关系管理等等。例如对于超市，我们可以优化产品的位置摆放，对于电商，我们可以优化商品所在的仓库位置，达到节约成本，增加经济效益的目的。

2、Apriori基本概念

      Apriori算法是常用的用于挖掘出数据关联规则的算法，它用来找出数据值中频繁出现的数据集合，找出这些集合的模式有助于我们做一些决策。

      什么样的数据才是频繁项集呢？也许你会说，这还不简单，肉眼一扫，一起出现次数多的数据集就是频繁项集吗！的确，这也没有说错，但是有两个问题，第一是当数据量非常大的时候，我们没法直接肉眼发现频繁项集，这催生了关联规则挖掘的算法，比如Apriori, PrefixSpan, CBA。第二是我们缺乏一个频繁项集的标准。比如10条记录，里面A和B同时出现了三次，那么我们能不能说A和B一起构成频繁项集呢？因此我们需要一个评估频繁项集的标准。

项集：在关联分析中，包含0个或多个项的集合被称为项集（itemset）。如果一个项集包含k个项，则称它为k-项集。例如:{啤酒，尿布，牛奶，花生} 是一个4-项集。空集是指不包含任何项的项集。

关联规则（association rule）：是形如 X → Y 的蕴含表达式，其中X和Y是不相交的项集，即：X∩Y=∅。关联规则的强度可以用它的支持度（support）和置信度（confidence）来度量。

支持度(Support)
   设W 中有s％的事务同时支持物品集A 和B，s ％称为关联规则A→B 的支持度。支持度描述了A 和B 这两个物品集的并集C 在所有的事务中出现的概率有多大。如果某天共有1000 个顾客到商场购买物品，其中有100 个顾客同时购买了铁锤和铁钉，那么上述的关联规则的支持度就是10 ％。

   支持度就是几个关联的数据在数据集中出现的次数占总数据集的比重。或者说几个数据关联出现的概率。如果我们有两个想分析关联性的数据X和Y，则对应的支持度为：

  通俗解释：简单地说，X==>Y的支持度就是指物品集X和物品集Y同时出现的概率。

一般来说，支持度高的数据不一定构成频繁项集，但是支持度太低的数据肯定不构成频繁项集。

置信度：置信度体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。如果我们有两个想分析关联性的数据X和Y，X对Y的置信度为：

   举个例子，在购物数据中，纸巾对应鸡爪的置信度为40%，支持度为1%。则意味着在购物数据中，总共有1%的用户既买鸡爪又买纸巾;同时买鸡爪的用户中有40%的用户购买纸巾。

该关联规则的可信度就回答了这样一个问题：如果一个顾客购买了铁锤，那么他也购买铁钉的可能性有多大呢？假设购买铁锤的顾客中有70％的人购买了铁钉, 所以可信度是70％。

关联规则挖掘一般需要定义最小的support和confidence，否则关联规则数量会过大

support ≥ minsup （support最小阈值）
confidence ≥ minconf（confidence最小阈值）
频繁项集：支持度support 大于最小支持度(minsup)的项集合

期望置信度（Expected confidence）

设W 中有e ％的事务支持物品集B，e ％称为关联规则A→B 的期望可信度度。期望可信度描述了在没有任何条件影响时，物品集B 在所有事务中出现的概率有多大。如果某天共有1000 个顾客到商场购买物品，其中有200 个顾客购买了铁钉，则上述的关联规则的期望可信度就是20％。

提升度（lift）

定义：提升度是可信度与期望可信度的比值

   提升度是可信度与期望可信度的比值。提升度描述物品集A的出现对物品集B的出现有多大的影响。因为物品集B在所有事务中出现的概率是期望可信度；而物品集B在有物品集A出现的事务中出现的概率是可信度，通过可信度对期望可信度的比值反映了在加入“物品集A 出现”的这个条件后，物品集B 的出现概率发生了多大的变化。在上例中作用度就是70％/20％=3.5。

理解：

   提升度大于1，意味着P(XY)大于P(X)P(Y)，也就是X和Y的联合概率大于各自独立出现的概率，意味着X和Y的关联效应比较强。至于“强关联规则”，一般是指满足支持度，置信度或提升度要求的规则。对于提升度来说大于1就可以理解为强关联规则，而对于支持度，置信度来说，一般需要超过一个自己设定的阈值才能说是“强关联规则”

3、关联规则挖掘的过程

  大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务。

频繁项集产生：其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集（frequent itemset）。
规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。
3.1 频繁项集复杂度

d 个item会产生个可能的候选项集

最容易想到、也最直接的进行关联关系挖掘的方法或许就是暴力搜索（Brute-force）的方法：

List all possible association rules
Compute the support and confidence for each rule
Prune rules that fail the minsup and minconf thresholds

   很自然，当我们数据量极其庞大时，数量会成指数级的增长，频繁项集产生的计算开销太过于庞大，在实际应用过程中极其的不方便。于是就有了下面两条先验原理：

Apriori定律1：如果一个集合是频繁项集，则它的所有子集都是频繁项集。
Apriori定律2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。
下图表示当我们发现{A,B}是非频繁集时，就代表所有包含它的超级也是非频繁的，即可以将它们都剪除。

   Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。

3.2 Aprior算法流程

   输入：数据集合D，支持度阈值αα

　输出：最大的频繁k项集

　　　1）扫描整个数据集，得到所有出现过的数据，作为候选频繁1项集。k=1，频繁0项集为空集。

　　　2）挖掘频繁k项集

　　　　 a) 扫描数据计算候选频繁k项集的支持度

　　　　　b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。

　　　　　c) 基于频繁k项集，连接生成候选频繁k+1项集。

　　　3）令k=k+1，转入步骤2。

　　从算法的步骤可以看出，Aprior算法每轮迭代都要扫描数据集，因此在数据集很大，数据种类很多的时候，算法效率很低。

      Aprior算法是一个非常经典的频繁项集的挖掘算法，很多算法都是基于Aprior算法而产生的，包括FP-Tree,GSP, CBA等。这些算法利用了Aprior算法的思想，但是对算法做了改进，数据挖掘效率更好一些，因此现在一般很少直接用Aprior算法来挖掘数据了，但是理解Aprior算法是理解其它Aprior类算法的前提。
---------------------
【转载】
作者：不曾走远~
原文：https://blog.csdn.net/qq_20412595/article/details/82284035

作者: 不二晨 时间: 2018-10-25 10:46

作者: 魔都黑马少年梦 时间: 2018-11-1 16:21

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2