开发者学堂课程【高校精品课-北京大学 -推荐系统 ：Lec3 基于模型的 CF】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/122/detail/3972
Lec3 基于模型的 CF
内容介绍：
一、协同过滤算法分类
二、基于关联规则的协同过滤
一、协同过滤算法分类
基于领域的方法 vs. 基于模型的方法
基本思想是利用局部(邻域)信息阐述结果VS.忽略基于全局有价值信息，在内存中存储(记忆)整个数据集vs.训练出抽象模型，导致成本比较高，针对问题可以采用基于模型的方法，基本思想是挖掘并利用全局信息阐述结果，并且通过离线训练得到抽象结果，进而在执行过程中只需要存储抽象模型的阐述结果即可，以此降低难度，常见基于模型的形成过滤方法，矩阵分解，关联规则，机器学习。
二、基于关联规则的协同过滤
在电商中常见的项目组合推荐和相关商品推荐都是关联规则产生的推荐结果。
1、关联
自然界中两个事件同时或先后发生的一种联系
可分为:简单关联、时序关联、因果关联
2、关联规则
描述在交易中项目之间同时出现的规律的知识模式。
通过量化的数字描述项目4的出现对项目B的出现有多大的影响。
形如 A=B 的蕴合式，和 B 为不相交的项集，例:{尿布}→{啤酒}
3、基本概念
项目简称为项目，项目的集合简称为项集，并将所有包含项目的集合，成为全项集，事务描述的是用户的一次购买行为，具体在业务系统中对应的是一条交易记录，每一条事务都有唯一标识，事务标识简称 tid，事务本质上是全项集的子集，表示具体详情，关联规则是通过蕴涵式表达，即 a 蕴涵 b 表示可以通过项集 a 推荐项集 b，项集 ab 都是全项集i的子集，并且它们的交集为空。
4、关联规则度量
a 蕴涵 b，可以从不同角度进行度量，常见的度量指标有置信度，A出现的前提下，B出现的概，支持度，A、B同时出现的概率，期望可信度，B出现的概率，改善度率，置信度对期望可信度的比值。记录除以期望可信度得到改善度。
置信度: confidence(A => B)
交易数据集D中同时包含项集A和B的事务数与包含项集A的事务数的比值。
置信度是对关联规则准确度的衡量，度量关联规则的强度。
支持度: support(A=> B)
交易数据集D中同时包含项集A和B的事务数与总的事务数的比值。
支持度是对关联规则重要性的衡量，反映关联是否是普遍存在的规律。
5、示例
TID |
Items |
1 |
Bread, Milk |
2 |
Bread, Diaper, Beer, Eggs |
3 |
Milk, Diaper, Beer, Coke |
4 |
Bread, Milk, Diaper, Beer |
5 |
Bread, Milk, Diaper, Coke |
假设给定数据中包含五条事务，浏览和调度蕴涵啤酒，基于给出的公式，可以相应的算出它的支持度和置信度分别为0.4和0.67，支持度分子描述的是同时包含浏览，调度和啤酒三个项目，在表格中包含浏览，调度和啤酒三个项目的只有3和4，分子是2，分母是总事务数5，支持度是0.4，同理可以根据公式计算出它的置信度，也可以计算出其它的关联规则，比如调度和啤酒之间的规则。
6、关联规则挖掘
目标：给定一个交易数据集D
产生支持度和置信度分别大于给定阀值的关联规则
两个参数:最小支持度阀值: min_support; 最小置信度度阈值: min _conf
两个基本步骤
找出频繁项集:
支持度( S(I))大于最小支持度阀值的所有项集。
分母描述的是给定数据集d中的总事务数，对于所有的关联规则，分母都是相同数字，所以为了减少相同度通常会忽略分母的常量，用分子集同时包含搜索集和频率作为支持度，同时也会根据对应频率设定最小支持度阈值。
找出强关联规则
由频繁项集生成关联规则，根据置信度排除关联较小的，保留置信度大于最小置信度阀值的关联规则。
7、生成频繁项集
搜索频繁项集，最直接的方法可以使用暴力手段。
Naive algorithm: Brute-force approach
计算每个可能项集的支持度: O(n·2m)是子数集的复杂度，在实际的业务需求中，方法并不可行，复杂度太高，需要用更为高效的频繁项集的方法。
把格结构中每个项集作为候选项集:O(2m)， m表示总项数。针对每个候选项集，和每个事务比较以确定支持度计数: O(n)，n表示总事务数。
8、Apriori 算法
（1）基本思想:
利用先验(Apriori)原理减少候选项集的数量。
迭代搜索:由频繁(k-1)-项集构建候选 k- 项集。
（2）先验原理( Apriori Principle)
若A是一个频繁项集，则A的每一个子集都是一个频繁项集。若A是非频繁项集，则A的所有超集都是非频繁项集。
方法：逐层(level-wise ) 搜索
初始化:找到所有的频繁1-项集，只包含一个项目的频繁项集。根据基本思想进行注册迭代搜索。
迭代:
扩展频繁(k-1)-项集得到候选 k- 项集。
剪枝:剪除不满足最小支持度的候选项集
9、基于支持度的剪枝：示例
操作可以极大的降低复杂度，假设包含 abcde 五个项目的数据集，在初始化阶段，发现包含a的，1项集是非频繁项集，即a出现的频率较低，对应的支持度较小，可以得出项集a的所有超集都是非频繁项集，可以将项集截取出，减少风险，通过示例可以看出仅依赖于 a 项集，就可以将整个搜索空间减少接近一半，这就是剪枝的效果，它可以极大的降低复杂度。
10、Apriori 算法：示例
事务数据集
TID |
项目 |
1 |
b，d |
2 |
a，b，c |
3 |
a，b，d |
4 |
a，e |
假设给定包含四条事务的数据集，在触发阶段可以通过扫描数据集计算候选项集的支持度。
项集 |
支持度 |
{a} |
3 |
{b} |
3 |
{c} |
1 |
{d} |
2 |
{e} |
1 |
假设最小支持阈值为2，通过比较可以得出候选项目c和e小于最小支持阈值，所以将其剪出，得到频繁的项集。
项集 |
支持度 |
{a} |
3 |
{b} |
3 |
{d} |
2 |
基于频繁项集扩展生成候选项集。
项集 |
{a,b} |
{a,d} |
{b,d} |
可以再次扫描数据集计算支持度
项集 |
支持度 |
{a,b} |
2 |
{a,d} |
1 |
{b,d} |
2 |
可以看到{a,d}小于阈值，所以将其进行剪枝，得到频繁项集。
项集 |
支持度 |
{a,b} |
2 |
{b,d} |
2 |
基于频繁项集扩展得到候选项集。
项集 |
{a,b,d} |
通过扫描数据集得到其支持度为1，不符合最小阈值的要求，所以也将其剪枝，进而完成整个搜索过程。
项集 |
支持度 |
{a,b,d} |
1 |
最后可以得到三个频繁项集和两个频繁项集，由于两个频繁项集无法产生关联规则，所以将其忽略，进而得到可用的两个频繁项集，基于两个频繁项集，可以生成对应的四条关联规则，a 蕴涵 b，b 蕴涵 a，b 蕴涵 d，d 蕴涵 b，四条关联规则是否都有价值，可以利用 b 蕴涵 a 进行分析。
11、关联规则的相关分析
候选规则：
{b}=>{a}
通过计算可以得到支持度= 50%，置信度≈67% =>强关联规则。
规则的误导:
整体购买{a}的可能性是75% (期望可信度)，比67%还大。整体的数据集中有75%的事务包含项集，它比置信度在购买项集b的条件下面，购买项集a的概率67%还要大，可以看出强关联规则并没有价值，因为项集b和项集a，是负相关的。
事实：{b}和{a}是负相关的。
利用规则推荐反而会降低推荐效果。
候选规则可以通过支持度和置信度算出强度，但是在此之上还需要通过改善度，也称为提升度，或者相关度判断是否有意义或者更有价值，当一条候选的关联规则，它的改善度小于1时，关联规则无意义，当它等于1时，意味着两个项集是独立的，只有当提升度或者相关度大于1时，关联规则才是有意义的，一个项目的出现会蕴涵另外一个项目出现，最终希望找到有价值的关联规则是强关联并且有意义。
12、基于关联规则的推荐
（1）寻找有效的强关联规则: (离线)
依据支持度寻找频繁项集(Apriori 算法)，并生成候选关联规则。
依据置信度和提升度过滤弱的或无效的关联规则，保留有效强关联规则。
（2）确定候选项目集: (在线)
基于目标用户刚加购物车或刚购买的项目集合。
依据有效的强关联规则，确定候选项目集。
（3）排序推荐:
根据规则的置信度 (加和)对候选项目进行排序，并生成推荐列表。
