推荐算法之模型协同过滤（1）-关联规则

一、概念

1、关联规则

关联规则是数据挖掘中的典型问题之一，又被称为购物篮分析，这是因为传统的关联规则案例大多发生在超市中，例如所谓的啤酒与尿布传说。事实上，“购物篮”这个词也揭示了关联规则挖掘的一个重要特点：以交易记录为研究对象，每一个购物篮（transaction）就是一条记录。关联规则希望挖掘的规则就是：哪些商品会经常在同一个购物篮中出现，其中有没有因果关系。为了描述这种“经常性”及“因果关系”，分析者定义了几个指标，基于这些指标来筛选关联规则，从而得到那些不平凡的规律。

2、关联规则的计算

名词解释
事务：每一条交易称为一个事务
项：交易的每一个物品称为一个项，例如Cola、Egg等。
项集：包含零个或多个项的集合叫做项集，例如{Cola, Egg, Ham}。
k−项集：包含k个项的项集叫做k-项集，例如{Cola}叫做1-项集，{Cola, Egg}叫做2-项集。
频繁项集：支持度大于或等于某个阈值的项集就叫做频繁项集。例如阈值设为50%时，因为{Diaper, Beer}的支持度是75%，所以它是频繁项集。

（1）计算支持度
支持度计数：一个项集出现在几个事务当中，它的支持度计数就是几。例如{Diaper, Beer}出现在事务 002、003和004中，所以它的支持度计数是3
支持度：支持度计数除于总的事务数。例如上例中总的事务数为4，{Diaper, Beer}的支持度计数为3，所以它的支持度是3÷4=75%，说明有75%的人同时买了Diaper和Beer。

（2）计算置信度
置信度：对于规则{Diaper}→{Beer}，{Diaper, Beer}的支持度计数除于{Diaper}的支持度计数，为这个规则的置信度。例如规则{Diaper}→{Beer}的置信度为3÷3=100%。说明买了Diaper的人100%也买了Beer。

3、关联规则与物品协同过滤

一般地，关联规则被划分为动态推荐，而协同过滤则更多地被视为静态推荐。
所谓动态推荐，就是推荐的基础是且只是当前一次（最近一次）的购买或者点击。譬如用户在网站上看了一个啤酒，系统就找到与这个啤酒相关的关联规则，然后根据这个规则向用户进行推荐。而静态推荐则是在对用户进行了一定分析的基础上，建立了这个用户在一定时期内的偏好排序，然后在这段时期内持续地按照这个排序来进行推荐。由此可见，关联规则与协同过滤的策略思路是完全不同的类型。
事实上，即便在当下很多能够拿到用户ID的场景，使用动态的关联规则推荐仍然是值得考虑的一种方法（尤其是我们经常把很多推荐方法的结果综合起来做一个混合的推荐），因为这种方法的逻辑思路跟协同过滤有着本质的不同，问题似乎仅仅在于：个人的偏好到底有多稳定，推荐到底是要迎合用户的长期偏好还是用户的当下需求。

二、实现关联规则推荐

挖掘关联规则主要有Apriori算法和FP-Growth算法。后者解决了前者由于频繁的扫描数据集造成的效率低下缺点。以下按照Apriori算法来讲解。

1、执行步骤

step 1：扫描数据集生成满足最小支持度的频繁项集。
step 2：计算规则的置信度，返回满足最小置信度的规则。

2、代码实现

# coding=utf-8
'''
基于Apriori算法的关联规则推荐
'''
import numpy as np

#========================================================
#  测试数据
#========================================================

def loadDataSet():
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5], [1, 2, 3, 5], [1, 2, 3, 5]]

#========================================================
#  生成候选1项集、候选k项集
#========================================================

def createC1(dataSet):
    '''
    生成候选1项集
    INPUT -> 事务集(购物篮)
    '''
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    # 这里的排序是为了在生成新的候选集时可以直接认为两个n项候选集前面的部分相同
    C1.sort()  
    return list(map(frozenset, C1))   # map(frozenset, C1)的语义是将C1由Python列表转换为不变集合

def createCk(C1, L_temp, k):
    '''
    由k-1项频繁集生成候选k项集
    INPUT -> 候选1项集, 当前的频繁项集, 目标项数
    '''
    Ck = []
    lenLt = len(L_temp)
    for i in range(lenLt):
        for j in C1:
            LL = L_temp[i]|j
            if LL not in Ck and len(LL)==k:
                Ck.append(LL)
    return Ck

#========================================================
#  发现频繁项集
#========================================================

def supportCount(dataSet, Ck):
    '''
    计算支持度计数
    INPUT -> 事务集(购物篮), 候选项集
    '''
    sCount = {}    # 支持度计数
    for transaction in dataSet:
        for candidate_items in Ck:
            if candidate_items.issubset(transaction):
                sCount[candidate_items] = sCount.get(candidate_items, 0) + 1
    return sCount

def scanD(dataSet, Ck, minSup):
    '''
    从候选项集Ck中发现频繁项集Lk
    INPUT -> 事务集(购物篮), 候选项集, 最小支持度
    '''
    sCount = supportCount(dataSet, Ck)

    Lk = []
    supportData = {}
    for candidate_items in sCount:
        support = sCount[candidate_items] / float(len(dataSet))  # 支持度 = 某项集的支持度计数/总记录数
        if support >= minSup:
            Lk.insert(0, candidate_items)  # 将频繁项集插入返回列表的首部
        supportData[candidate_items] = support

    return Lk, supportData   # Lk为在Ck中找出的频繁项集（支持度大于minSupport的），supportData记录各频繁项集的支持度

#========================================================
#  得到满足最小支持度的规则
#========================================================

def calcSupport(dataSet, minSup=0.5, k=2):
    '''
    获取事务集中的所有的频繁项集
    INPUT -> 事务集(购物篮), 最小支持度, 频繁项集大小
    '''
    # 初始项数
    n = 1
    # 从事务集中获取候选1项集
    C1 = createC1(dataSet)
    # 获取频繁1项集和对应的支持度
    F1, supportData = scanD(dataSet, C1, minSup)

    # 符合条件的频繁集和其支持度
    output = []
    output_supportData = {}

    F_temp = F1
    while (n <= k):
        # 根据频繁项集生成新的候选项集。Ck表示项数为k的候选项集
        Ck = createCk(C1, F_temp, n+1)
        F_temp = []

        Fk, supK = scanD(dataSet, Ck, minSup)
        if Fk == []:
            break
        else:
            for i in range(len(Fk)):
                F_temp.append(Fk[i])
                if len(Fk[i]) == k:   # 符合长度要求
                    output.append(Fk[i])
                    output_supportData[Fk[i]] = supK[Fk[i]]
            n += 1
    return output, output_supportData

#========================================================
#  得到满足最小置信度的规则
#========================================================

def calcConfidence(dataSet, Fk, minConf=0.5):
    '''
    计算规则的置信度，返回满足最小置信度的规则
    INPUT -> 事务集(购物篮), 频繁k项集, 最小置信度
    '''
    C1 = createC1(dataSet)
    C1_sCount = supportCount(dataSet, C1)  # 频繁项集中每一个元素的支持度计数
    Fk_sCount = supportCount(dataSet, Fk)  # 频繁项集中每一个项集的支持度计数

    TrustedR = {}
    for freq_items in Fk:
        for item in freq_items:
            conf = Fk_sCount[freq_items] / C1_sCount[frozenset({item})]
            if conf >= minConf:
                TrustedR[item] = [x for x in freq_items if x != item]
    return TrustedR

#========================================================
#  Apriori算法
#========================================================

def Apriori(dataSet, k=2, minSup=0.5, minConf=0.5):
    '''
    Apriori算法，先挖掘频繁集再用置信度过滤
    INPUT -> 数据集, 项数, 最小支持度, 最小置信度
    '''
    Fk, suppData = calcSupport(dataSet, minSup=minSup, k=k)
    TrustedR = calcConfidence(dataSet, Fk, minConf=0.5)
    return TrustedR

#========================================================
#  主程序
#========================================================

if __name__=='__main__':
    dataSet = loadDataSet()  # 获取事务集。每个元素都是列表
    TrustedR = Apriori(dataSet, k=3, minSup=0.5, minConf=0.5)
    print(TrustedR)

如下所示，当用户购买1商品时推荐2、3商品