基于关联规则的推荐系统(推荐系统常用算法介绍)
导语：机器学习：推荐系统常用的关联规则算法——Eclat算法
上次分享时用Apriori算法去做关联规则和推荐实践应用，这次想通过用不同的算法学习关联规则，且更加容易理解。
关联分析是一种在大规模数据集中寻找有趣关系的任务，经常在推荐系统中有一些简单的推送服务会使用到。这些任务有两种形式：频繁项集和关联规则。
频繁项集是经常出现在一块的物品的集合；关联规则暗示的是两种物品之间可能存在很强的关系。可以结合某家店的交易清单来说明这两个概念：
频繁集指的就是数据集中经常一起出现的组合，比如{啤酒、尿布、饼干}就是频繁集中的一个例子，而根据上表也可以找到尿布—>啤酒的关联规则。而我们要通过关联分析大规模数据来发现数据之间的关系，如何定义关系的强弱呢？这时候我们用支持度(Support)和置信度(Confidence)来定义。
支持度和置信度支持度：数据集中包含该项集记录所占的比例，上例中{豆奶}的支持度=2/5，{啤酒，尿布}的支持度=3/5。
置信度：针对像频繁集数量>=2的情况，例如{啤酒，尿布}，那么可信度=支持度({尿布，啤酒})/支持度(尿布)。
关联规则的一般步骤找到频繁集；
在频繁集中通过可信度筛选获得关联规则。
ECLAT算法不同于Apriori和FP算法所采用的按照交易事务来水平划分项集的数据挖掘方式，把数据集中的项划归到每个事务下，ECLAT算法采用了另一种思路：把数据集中的事务划归到每个项下。
通过加入倒排的思想，具体就是将事务数据中的项作为key，每个项对应的事务ID作为value，利用转换后的倒排表可以加快频繁集生成速度。简单来说就是反过来想事情，有物品A，A被[a,b,c]这三个人买了，那么可以构建{A:[a,b,c]}的这样一种字典。
算法思路：
由频繁k项集求交集，生成候选k+1项集 。对候选k+1项集做裁剪，生成频繁k+1项集，再求交集生成候选k+2项集，不断迭代直至生成的频繁项次数为1或无频繁项生成，输出频繁集。
一个简单的例子上图简单地演示了Eclat算法的运算流程(从左往右)，原始数据(图1)转换后得到Tidset(图2)。
计算频繁集计算频繁1项集(图3)，由频繁1项集生成频繁2项集，{A},{B},{C}两两组合形成不重复的集合，得到{A,B}，{A,C}，{B,C}，搜索倒排表对应新生成的候选频繁集是否符合>2的条件，若不符合过滤。
接着由频繁2项集生成频繁3项集(图5)，由于{A,B,C}的出现次数=1且tid的个数为1，停止迭代，最后得到的全部频繁集为图6.
总的来说，由于生成了原始数据的倒排表，在整个频繁集的搜索过程中比Apriori更流畅和更快。
计算置信度通过上述得到的频繁集再次计算得到关联规则，计算方式如下：
同理，
需要注意的是，b和a的位置不同代表着的意思不一样，就像是你买一次啤酒同时去买了十次尿布，和买了十次尿布只买了一次啤酒的感觉时很不同的。
所以利用置信度阈值(Confidence Threshold)，将不满足的置信度(Confidence)都过滤掉，剩下的就是该数据集的强关联规则。
总结在Eclat算法中，它可以由n个集合的并集产生新的候选集,通过计算这n个项集的Tidset的交集快速得到候选集的支持度。所以ECLAT算法较Apriori相比较，优化了其搜索流程，可以基于集合运算更简便地得到频繁集。
但是，当Tidset的规模庞大时将出现求Tidset的交集的操作将消耗大量时间，影响了算法的效率，而且存储Tidset需要消耗系统大量的内存。
本文内容由小春整理编辑！