1 推荐系统的基本概念

推荐算法经典应用

亚马逊把推荐成功地应用到购物网站，如买了X的人还买了Y，亚马逊有**20%-30%**的销售来自推荐。

推荐算法经典应用-网易云音乐推荐歌单

推荐算法经典应用-豆瓣猜

2 什么是推荐系统

信息时代产品和服务的提供正经历第二次理念上的变革。

推荐系统是根据用户历史行为和当前所处的环境，根据信息的特点来决定推荐最合适的内容和商品

推荐系统本质是为了帮助人们解决信息过载问题的一项工具互联网时代信息的爆炸带来了信息过载的问题，为了解决信息过载问题，人们经历了分类目录、搜索引擎、推荐系统三个阶段

推荐系统和搜索引擎一样可以看作是一个信息检索的系统。区别是搜索是主动式的，而推荐系统，在大多数情况下是没有主动输入的，是被动出现的

搜索vs推荐 从搜索到推荐是大势所趋，个性化成为潮流

推荐系统分类

推荐算法分类

推荐系统的评价指标

第一层次:基于数据的指标
预测评分准确度、预测评分关联、分类准确度、排序准确度 准确率、召回率、准确率提高率、召回率提高率、F1指标和AUC值
第二层次：商业应用上的关键表现指标，用户受推荐影响后的转化率、客单价、购买品类数和活跃
度等的变化
第三层次：用户真实的体验


由此可见，正确率是评估捕获的成果中目标成果所占得比例；召回率，顾名思义，就是从关注领域中，召回目标类别的比例；而F值，则是综合这二者指标的评估指标，用于综合反映整体的指标。

当然希望检索结果Precision越高越好，同时Recall也越高越好，但事实上这两者在某些情况下有矛盾的。比如极端情况下，我们只搜索出了一个结果，且是准确的，那么Precision就是100%，但是Recall就很低；而如果我们把所有结果都返回，那么比如Recall是100%，但是Precision就会很低。因此在不同的场合中需要自己判断希望
Precision比较高或是Recall比较高。

3 购物篮分析与关联规则

定义
• 单个客户一次购买商品的总和称为一个购物篮

思想
• 分析商品与商品之间的关联（啤酒和尿布）
算法
• 不考虑购物顺序：关联规则
• 考虑购物顺序：序贯模型‘

应用
• 超市货架布局：互补品与互斥品
• 套餐设计和捆绑销售

关联规则：概念

I={i1,i2,…,in}是n个不同项目的集合， ik(k = 1,2 … n)称为一个项目(item)
项目的集合称为项目集合(Itemset)，简称为项集。其元素个数称为项集的长度，长度为k的项集称为k-项集(k-Itemset)
每笔交易T(Transaction)是项集I上的一个子集,即T ⊆ 交易的全体构成了交易记录集D，简称交易集D,交易集D中
包含交易的个数记为|D|
设A,B为两个项集，则关联规则是如下蕴涵式：
，其中A ⊆ 𝐼, B ⊆ 𝐼,且A ∩ 𝐵 = Φ

计算支持度和置信度

理解支持度与置信度

食堂卖饭，1000份打饭记录中，买米饭的有800人次，买牛肉的有600人次，两个共同买的有400人次。
那么可以得出对于规则(牛肉->米饭)

支持度=P(牛肉&米饭)=400/1000=0.40

置信度=P(米饭|牛肉)=400/600=0.67

置信度和支持度都很高，但是给买牛肉的人推荐米饭有意义吗？

如果直接计算无任何条件下用户购买米饭的概率:

P(米饭)=800/1000=0.8

定义：提升度=置信度/无条件概率=0.67/0.8

提升度小于1 意义不是很大

关联规则：提升度

提升度表示 先购买A对购买B的概率的提升作用
提升度是两种可能性的比较，一种是在已知购买了左边商品情况下购买右边商品的可能性，另一种是任意情况下购买右边商品的可能性
只有提升度大于1才说明关联规则真正有效
A ⇒ B和B⇒ A的提升度是一样的

关联规则挖掘

关联规则挖掘的定义：给定一个交易数据集T，找出其中所有支持度和置信度满足一定条件的关联规则

• 最简单的方法是穷举项集的所有组合，并计算和判断每个组合是否满足条件，一个长度为n的项集的组合个数
是？

• 怎样快速挖出满足条件的关联规则是关联挖掘的需要解决的主要问题

• Apriori算法是解决这一问题的最流行的算法发现关联规则要求项集必须满足的最小支持阈值，称为项集的最小支持度(Minimum Support)，记为supmin

• 支持度大于或等于supmin的项集称为频繁项集，简称频繁集，反之则称为非频繁集

• 通常k-项集如果满足supmin，称为k-频繁集，记作𝐿𝑘 • 关联规则的最小支持度(Minimum Support)也就是衡量频繁集的最小支持度，记为supmin，它用于衡量规则需要满足的最低重要性

• 关联规则的最小置信度(Minimum Confidence)记为confmin，它表示关联规则需要满足的最低可靠性

• 如果关联规则满足支持度大于最小支持度，置信度大于最小置信度，则称为强关联规则，否则称为弱关联规则。

4 关联规则挖掘：Apriori算法

1生成频繁项集这一阶段找出所有满足最小支持度的项集，找出的这些项集称为频繁项集

2生成规则在上一步产生的频繁项集的基础上生成满足最小置信度的规则，产生的规则称为强规则关联规则挖掘所花费的时间主要是在生成频繁项集上，因为找出的频繁项集往往不会很多，利用频繁项集生成规则也就不会花太多的时间

Apriori基于以下两条核心原理生成频繁项集

1 如果某个项集是频繁的，那么它的所有子集也是频繁的

2若子集不是频繁的，则所有包含它的项集都是不频繁的

第一步:所有单独的项都是候选项集 C1，任何支持度比给定的最小支持度小的项都将从候选项集 C1中剔除，形成
频繁 1-项集 L1

2. 连接步： 两个 L1通过自连接形成具有 2 个项的候选项集C2

3. 剪枝步：通过再次扫描交易集决定这些候选项的支持度，保留比预先给定的最小支持度大的候选项，形成频繁 2-项 集L2

4. 下一步形成含有 3 个项的候选项集 C3，重复上述步骤，
   直到找到所有的频繁项集为止

Apriori算法步骤：举例

Apriori算法优缺点

1 Apriori算法利用频繁集的两个特性，过滤了很多无关的集合，效率提高不少

2. Apriori算法是一个候选消除算法，每一次消除都需要扫描一次所有数据记录，造成整个算法在面临大数据集时显得无能为力。每次生成频繁项集时都要进行全表扫描

5 FpGrowth算法步骤：举例

取第一组数据，从根节点开始依次按顺序向下排列，并且记录出现次数。


取第二组数据，从根节点开始依次按顺序向下排列，并且记录出现次数。

取第三组数据，从根节点开始依次按顺序向下排列，并且记录出现次数。此时应该单独为E产品从根节点延
伸出一条路径

取第四组数据，从根节点开始依次按顺序向下排列，并且记录出现次数。此时应该单独为G产品从E节点延
伸出一条路径

直至FP树完全构建完成

FP Growth的最终目的是找频繁项集，在得到了FP树和项头表以及节点链表之后，我们首先要从项头表的底部
项依次向上挖掘。

对于项头表对应于FP树的每一项，我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。

得到这个FP子树，我们将子树中每个节点的的计数设置为叶子节点的计数，并删除计数低于支持度的节点。从这个条件模式基，我们就可以递归挖掘得到频繁项集了。

我们看看先从最底下的F节点开始，我们先来寻找F节点的条件模式基，由于F在FP树中只有一个节点，因此候选就只有下图左所示的一条路径，对应{A:8,C:8,E:6,B:2, F:2}。我们接着将所有的祖先节点计数设置为叶子节点的计数，即FP子树变成{A:2,C:2,E:2,B:2, F:2}。一般我们的条件模式基可以不写叶子节点，因此最终的F的条件模式基如下图右所示。

F挖掘完了，我们开始挖掘D节点。D节点比F节点复杂一些，因为它有两个叶子节点，因此首先得到的FP子
树如下图左。
我们接着将所有的祖先节点计数设置为叶子节点的计数，即变成{A:2, C:2,E:1 G:1,D:1, D:1}此时E节点和G节点由于在条件模式基里面的支持度低于阈值，被我们删除，最终在去除低支持度节点并不包括

叶子节点后D的条件模式基为{A:2, C:2}。通过它，我们很容易得到F的频繁2项集为{A:2,D:2},{C:2,D:2}。递归
合并二项集，得到频繁三项集为{A:2,C:2,D:2}。D对应的最大的频繁项集为频繁3项集。

同样的方法可以得到B的条件模式基如下图右边，递归挖掘到B的最大频繁项集为频繁4项集{A:2, C:2, E:2,B:2}。

继续挖掘G的频繁项集，挖掘到的G的条件模式基如下图右边，递归挖掘到G的最大频繁项集为频繁4项集{A:5, C:5, E:4,G:4}。

E的条件模式基如下图右边，递归挖掘到E的最大频繁项集为频繁3项集{A:6, C:6, E:6}。

C的条件模式基如下图右边，递归挖掘到C的最大频繁项集为频繁2项集{A:8, C:8}。

至于A，由于它的条件模式基为空，因此可以不用去挖掘了。
至此我们得到了所有的频繁项集，如果我们只是要最大的频繁K项集，从上面的分析可以看到，
最大的频繁项集为4项集。包括{A:2, C:2, E:2,B:2}和{A:5, C:5, E:4,G:4}。

6 关联规则的优缺点

优点
原理易于理解，比较容易解释提炼的规则相对稳定，不需要频繁更新
缺点
并不是真正的个性化推荐，不同用户的推荐结果相同面对稀疏数据效果不佳

7 案例：家居用品商店

已知用户的历史购买记录，如何推荐产品？

扩展包arulesViz的介绍