【BI学习第二次学习笔记】

1. 背景故事

美国明尼苏达州一家Target被客户投诉，一位中年男子指控Target将婴儿产品优惠券寄给他的女儿（高中生）。但没多久他却来电道歉，因为女儿经他逼问后坦承自己真的怀孕了。

开始看到这个故事的时候，有点吃惊，高中少女在搜索信息时，输入了相关信息，Target推荐系统捕捉到这个信息，向这个少女发放优惠券。首先，我觉得信息的收集渠道变得很多，很多APP会让你填写个人信息，不知道什么时候，就会有人找上你，给你打电话，发短信。但不得不说，推荐系统的好处之一就是过滤信息，精准推荐。从公司角度出发这是对的，我给用户推荐合适的商品和服务；对用户来说，信息冗余，我们的时间被瓜分了。很多时候，没做什么事情，时间就过去，回过神，时间都去哪了？任何东西，有利有弊，不能一概而论，我们要看到好的地方。说了这么多，今天的主角，推荐系统该登场了。

上面案例提到的推荐是怎么回事？为什么能够给用户推荐好的商品？我们先来说一下，关联规则。所谓关联规则就是如果一个消费者购买了产品A，那么他有多大几率会购买产品B?为了更好地理解这个概念，我们再来看一个故事：啤酒和尿布。

沃尔玛在分析销售记录时，发现啤酒和尿布经常一起被购买，于是他们调整了货架，把两者放在一起，结果真的提升了啤酒的销量。

原因的解释是爸爸在给宝宝买尿布的时候，会顺便给自己买点啤酒？沃尔玛是最早通过大数据分析而受益的传统零售企业，对消费者购物行为进行跟踪和分析。

2. 支持度、置信度和提升度

了解了关联规则，我们再来看一看，几个关键的概念：支持度、置信度和提升度。

支持度，是个百分比，指的是某个商品组合出现的次数与总次数之间的比例。支持度越高，代表这个组合出现的频率越大。计算上图中每个词语，在五次中出现了几次。牛奶出现三次，“牛奶”的支持度 4 5 = 0.8 \frac{4}{5}=0.8 54​=0.8。出现牛奶后，同时出现面包的次数有三次，“牛奶+面包”的支持度 3 5 = 0.6 \frac{3}{5}=0.6 53​=0.6。

置信度，是个条件概念，指的是当你购买了商品A，会有多大的概率购买商品B。

牛奶在五次中出现4次，在牛奶出现的时候啤酒出现2次，购买了牛奶后，再去买啤酒的概率（牛奶→啤酒） 2 4 = 0.5 \frac{2}{4}=0.5 42​=0.5

啤酒在五次中出现3次，在啤酒出现的时候牛奶出现2次，购买了啤酒后，再去买牛奶的概率（啤酒→牛奶） 2 3 = 0.67 \frac{2}{3}=0.67 32​=0.67

提升度：是商品A的出现，对商品B的出现概率提升的程度。 ( A → B ) = 置 信 度 ( A → B ) 支 持 度 ( B ) (A→B)=\frac{置信度(A→B)}{支持度(B)} (A→B)=支持度(B)置信度(A→B)​
置信度（牛奶→啤酒） = 2 4 = 0.5 =\frac{2}{4}=0.5 =42​=0.5, 支持度（啤酒） = 3 = 3 =3
提升度(A→B) = 0.5 3 = 1 6 < 1 =\frac{0.5}{3}=\frac{1}{6} <1 =30.5​=61​<1，牛奶对啤酒的提升度下降
提升度的三种可能：

1. 提升度(A→B)>1：代表有提升
2. 提升度(A→B)=1：代表有没有提升，也没有下降
3. 提升度(A→B)<1：代表有下降

3. 关联分析算法过程

纯粹的项集是一个指数级的排列组合过程，每个数据集都可以得到一个天文数字的项集，而其实大多数的项集都是我们不感兴趣的，因此，分析的过程需要加入阈值判断，对搜索进行剪枝，具体来说：

• 频繁项集发现阶段：按照“support ≥ minsup threshold”的标准筛选满足最小支持度的频繁项集（frequent itemset）。
• 关联规则发现阶段：按照“confidence ≥ minconf threshold”的标准筛选满足最小置信度的强规则（strong rule）。
  满足最小支持度和最小置信度的关联规则，即待挖掘的最终关联规则。也是我们期望模型产出的业务结果。

这实际上是在工程化项目中需要关心的，因为我们在一个庞大的数据集中，频繁项集合关联规则是非常多的，我们不可能采纳所有的这些关系，特别是在入侵检测中，我们往往需要提取TOP N的关联，并将其转化为规则，这个过程也可以自动化完成。

4. Apriori算法

4.1 Apriori算法中对频繁项集的层级迭代搜索思想

A p r i o r i 定 律 1 ： 如 果 一 个 集 合 是 频 繁 项 集 ， 则 它 的 所 有 子 集 都 是 频 繁 项 集 \color{red}Apriori定律1：如果一个集合是频繁项集，则它的所有子集都是频繁项集 Apriori定律1：如果一个集合是频繁项集，则它的所有子集都是频繁项集

假设一个集合{A,B}是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集{A},{B}出现次数必定大于等于min_support，即它的子集都是频繁项集。

A p r i o r i 定 律 2 ： 如 果 一 个 集 合 不 是 频 繁 项 集 ， 则 它 的 所 有 超 集 都 不 是 频 繁 项 集 \color{red}Apriori定律2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集 Apriori定律2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集

假设集合{A}不是频繁项集，即A出现的次数小于 min_support，则它的任何超集如{A,B}出现的次数必定小于min_support，因此其超集必定也不是频繁项集
下图表示当我们发现{A，B}是非频繁集时，就代表所有包含它的超集也是非频繁的，即可以将它们都剪除（剪纸）

1. 找出所有的频繁项集
2. 由频繁项集产生强关联规则

4.2 挖掘频繁项集

1. 伪 码 描 述 \color{red}1. 伪码描述 1.伪码描述

• Let k
• • Generate frequent itemsets of length k, and Prune candidate itemsets that are ：计算C1每个1-项集的频率，在第一步就要根据支持度阈值对不满足阈值的项集进行剪枝，得到第一层的频繁项
• Repeat until no new frequent itemsets are identified：迭代过程
• • Generate length (
• • Prune candidate itemsets containing subsets of length k
• the finnal k-items：因为Apriori每一步都在通过项集之间的并集操作，以此来获得新的候选项集，如果在某一轮迭代中，候选项集没有新增，则可以停止迭代。因为这说明了在这轮迭代中，通过支持度阈值的剪枝，非频繁项集已经全部被剪枝完毕了，则根据Apriori先验定理2，迭代没有必要再进行下去了。
  

下面是一个具体的例子，最开始数据库里有4条交易，{A、C、D}，{B、C、E}，{A、B、C、E}，{B、E}，使用min_support=2作为支持度阈值，最后我们筛选出来的频繁集为{B、C、E}。

2. 一 个 频 繁 项 集 生 成 的 p y t h o n 代 码 示 例 \color{red}2. 一个频繁项集生成的python代码示例 2.一个频繁项集生成的python代码示例

# coding=utf-8
from numpy import *


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

def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    return map(frozenset, C1)


# 其中D为全部数据集，
# # Ck为大小为k（包含k个元素）的候选项集，
# # minSupport为设定的最小支持度。
# # 返回值中retList为在Ck中找出的频繁项集（支持度大于minSupport的），
# # supportData记录各频繁项集的支持度
def scanD(D, Ck, minSupport):
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                ssCnt[can] = ssCnt.get(can, 0) + 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key] / numItems     # 计算频数
        if support >= minSupport:
            retList.insert(0, key)
        supportData[key] = support
    return retList, supportData


# 生成 k+1 项集的候选项集
# 注意其生成的过程中，首选对每个项集按元素排序，然后每次比较两个项集，只有在前k-1项相同时才将这两项合并。
# # 这样做是因为函数并非要两两合并各个集合，那样生成的集合并非都是k+1项的。在限制项数为k+1的前提下，只有在前k-1项相同、最后一项不相同的情况下合并才为所需要的新候选项集。
def aprioriGen(Lk, k):
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i + 1, lenLk):
            # 前k-2项相同时，将两个集合合并
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()
            if L1 == L2:
                retList.append(Lk[i] | Lk[j])
    return retList


def apriori(dataSet, minSupport=0.5):
    C1 = createC1(dataSet)
    D = map(set, dataSet)
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData


dataSet = loadDataSet()
D = map(set, dataSet)
print dataSet
print D

C1 = createC1(dataSet)
print C1    # 其中C1即为元素个数为1的项集（非频繁项集，因为还没有同最小支持度比较）

L1, suppDat = scanD(D, C1, 0.5)
print "L1: ", L1
print "suppDat: ", suppDat


# 完整的频繁项集生成全过程
L, suppData = apriori(dataSet)
print "L: ",L
print "suppData:", suppData

最后生成的频繁项集为：

suppData: 
frozenset([5]): 0.75, 
frozenset([3]): 0.75, 
frozenset([2, 3, 5]): 0.5,
frozenset([1, 2]): 0.25,
frozenset([1, 5]): 0.25,
frozenset([3, 5]): 0.5,
frozenset([4]): 0.25, 
frozenset([2, 3]): 0.5, 
frozenset([2, 5]): 0.75, 
frozenset([1]): 0.5, 
frozenset([1, 3]): 0.5, 
frozenset([2]): 0.75 

需要注意，阈值设置的越小，整体算法的运行时间就越短，因为阈值设置的越小，剪枝会更早介入。

4.3 从频繁集中挖掘关联规则

解决了频繁项集问题，下一步就可以解决相关规则问题。

1. 关 联 规 则 来 源 自 所 有 频 繁 项 集 \color{red}1. 关联规则来源自所有频繁项集 1.关联规则来源自所有频繁项集

从前面对置信度的形式化描述我们知道，关联规则来源于每一轮迭代中产生的频繁项集（从C1开始，因为空集对单项集的支持推导是没有意义的）
c o n f i d e n c e ( A = > B ) = ( B ∣ A ) = s u p p o r t ( A U B ) s u p p o r t ( A ) = s u p p o r t ( A U B ) s u p p o r t − c o u n t ( A ) confidence(A=>B)=(B|A)=\frac{support(AUB)}{support(A)}=\frac{support(AUB)}{support-count(A)} confidence(A=>B)=(B∣A)=support(A)support(AUB)​=support−count(A)support(AUB)​
从公式中可以看到，计算关联规则置信度的分子和分母我们都有了，就是上一步计算得到的频繁项集。所以，关联规则的搜索就是围绕频繁项集展开的。

一条规则 S➞H 的可信度定义为：
P （ H ∣ S ） = s u p p o r t ( P U S ) / s u p p o r t ( S ) P（H | S）= support(P U S) / support(S) P（H∣S）=support(PUS)/support(S)
可见，可信度的计算是基于项集的支持度的。

2. 关 联 规 则 的 搜 索 过 程 \color{red}2. 关联规则的搜索过程 2.关联规则的搜索过程

既然关联规则来源于所有频繁项集 ，那要怎么搜索呢？所有的组合都暴力穷举尝试一遍吗？
显然不是的，关联规则的搜索一样可以遵循频繁项集的层次迭代搜索方法，即按照频繁项集的层次结构，进行逐层搜索

3. 关 联 规 则 搜 索 中 的 剪 枝 策 略 \color{red}3. 关联规则搜索中的剪枝策略 3.关联规则搜索中的剪枝策略
下图给出了从项集{0,1,2,3}产生的所有关联规则，其中阴影区域给出的是低可信度的规则。可以发现：
如果{0,1,2}➞{3}是一条低可信度规则，那么所有其他以3作为后件（箭头右部包含3）的规则均为低可信度的。即如果某条规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。

反之，如果{0，1，3}->{2}，则说明{2}这个频繁项作为后件，可以进入到下一轮的迭代层次搜索中，继续和本轮得到的规则列表的右部进行组合。直到搜索一停止为止

可以利用关联规则的上述性质属性来减少需要测试的规则数目，类似于Apriori算法求解频繁项集的剪枝策略。

4. 从 频 繁 项 集 中 寻 找 关 联 规 则 的 p y t h o n 示 例 代 码 \color{red}4. 从频繁项集中寻找关联规则的python示例代码 4.从频繁项集中寻找关联规则的python示例代码

# coding=utf-8
from numpy import *

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

def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    return map(frozenset, C1)


# 其中D为全部数据集，
# # Ck为大小为k（包含k个元素）的候选项集，
# # minSupport为设定的最小支持度。
# # 返回值中retList为在Ck中找出的频繁项集（支持度大于minSupport的），
# # supportData记录各频繁项集的支持度
def scanD(D, Ck, minSupport):
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                ssCnt[can] = ssCnt.get(can, 0) + 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key] / numItems     # 计算频数
        if support >= minSupport:
            retList.insert(0, key)
        supportData[key] = support
    return retList, supportData


# 生成 k+1 项集的候选项集
# 注意其生成的过程中，首选对每个项集按元素排序，然后每次比较两个项集，只有在前k-1项相同时才将这两项合并。
# # 这样做是因为函数并非要两两合并各个集合，那样生成的集合并非都是k+1项的。在限制项数为k+1的前提下，只有在前k-1项相同、最后一项不相同的情况下合并才为所需要的新候选项集。
def aprioriGen(Lk, k):
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i + 1, lenLk):
            # 前k-2项相同时，将两个集合合并
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()
            if L1 == L2:
                retList.append(Lk[i] | Lk[j])
    return retList


def apriori(dataSet, minSupport=0.5):
    C1 = createC1(dataSet)
    D = map(set, dataSet)
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData


# 频繁项集列表L
# 包含那些频繁项集支持数据的字典supportData
# 最小可信度阈值minConf
def generateRules(L, supportData, minConf=0.7):
    bigRuleList = []
    # 频繁项集是按照层次搜索得到的, 每一层都是把具有相同元素个数的频繁项集组织成列表，再将各个列表组成一个大列表，所以需要遍历Len(L)次, 即逐层搜索
    for i in range(1, len(L)):
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]    # 对每个频繁项集构建只包含单个元素集合的列表H1
            print "\nfreqSet: ", freqSet
            print "H1: ", H1
            rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)     # 根据当前候选规则集H生成下一层候选规则集
    return bigRuleList


# 根据当前候选规则集H生成下一层候选规则集
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
    m = len(H[0])
    while (len(freqSet) > m):  # 判断长度 > m，这时即可求H的可信度
        H = calcConf(freqSet, H, supportData, brl, minConf)     # 返回值prunedH保存规则列表的右部，这部分频繁项将进入下一轮搜索
        if (len(H) > 1):  # 判断求完可信度后是否还有可信度大于阈值的项用来生成下一层H
            H = aprioriGen(H, m + 1)
            print "H = aprioriGen(H, m + 1): ", H
            m += 1
        else:  # 不能继续生成下一层候选关联规则，提前退出循环
            break

# 计算规则的可信度，并过滤出满足最小可信度要求的规则
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
    ''' 对候选规则集进行评估 '''
    prunedH = []
    for conseq in H:
        print "conseq: ", conseq
        print "supportData[freqSet]: ", supportData[freqSet]
        print "supportData[freqSet - conseq]: ", supportData[freqSet - conseq]
        conf = supportData[freqSet] / supportData[freqSet - conseq]
        if conf >= minConf:
            print freqSet - conseq, '-->', conseq, 'conf:', conf
            brl.append((freqSet - conseq, conseq, conf))
            prunedH.append(conseq)
            print "prunedH: ", prunedH
    return prunedH





dataSet = loadDataSet()
L, suppData = apriori(dataSet, minSupport=0.5)      # 得到频繁项集列表L，以及每个频繁项的支持度
print "频繁项集L: "
for i in L:
    print i
print "频繁项集L的支持度列表suppData: "
for key in suppData:
    print key, suppData[key]

# 基于频繁项集生成满足置信度阈值的关联规则
rules = generateRules(L, suppData, minConf=0.7)
print "rules = generateRules(L, suppData, minConf=0.7)"
print "rules: ", rules


rules = generateRules(L, suppData, minConf=0.5)
#print
#print "rules = generateRules(L, suppData, minConf=0.5)"
#print "rules: ", rules

5. FP-growth算法

FP-growth算法基于Apriori构建，但采用了高级的数据结构减少扫描次数，大大加快了算法速度。FP-growth算法只需要对数据库进行两次扫描，而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori算法快。

FP-growth算法发现频繁项集的基本过程如下：

1. 构建FP树
2. 从FP树中挖掘频繁项集

5.1 FP树数据结构 - 用于编码数据集的有效方式

在讨论FP-growth算法之前，我们先来讨论FP树的数据结构，可以这么说，FP-growth算法的高效很大程度来源组FP树的功劳。

FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式（Frequent Pattern）。FP树通过链接（link）来连接相似元素，被连起来的元素项可以看成一个链表。下图给出了FP树的一个例子。

与搜索树不同的是，一个元素项可以在一棵FP树种出现多次。FP树辉存储项集的出现频率，而每个项集会以路径的方式存储在树中。

存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时，树才会分叉。

树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。

相似项之间的链接称为节点链接（node link），用于快速发现相似项的位置。

为了更好说明，我们来看用于生成上图的原始事务数据集：

上图中：

元素项z出现了5次，集合{r, z}出现了1次。于是可以得出结论：z一定是自己本身或者和其他符号一起出现了4次。

集合{t, s, y, x, z}出现了2次，集合{t, r, y, x, z}出现了1次，z本身单独出现1次。

就像这样，FP树的解读方式是：读取某个节点开始到根节点的路径。路径上的元素构成一个频繁项集，开始节点的值表示这个项集的支持度。

根据上图，我们可以快速读出：

• 项集{z}的支持度为5；
• 项集{t, s, y, x, z}的支持度为2；
• 项集{r, y, x, z}的支持度为1；
• 项集{r, s,x}的支持度为1。

FP树中会多次出现相同的元素项，也是因为同一个元素项会存在于多条路径，构成多个频繁项集。但是频繁项集的共享路径是会合并的，如图中的{t, s, y, x, z}和{t, r, y, x, z}

和Apriori一样，我们需要设定一个最小阈值，出现次数低于最小阈值的元素项将被直接忽略（提前剪枝）。上图中将最小支持度设为3，所以q和p没有在FP中出现。

5.2 构建FP树过程

1. 创 建 F P 树 的 数 据 结 构 \color{red}1. 创建FP树的数据结构 1.创建FP树的数据结构

我们使用一个类表示树结构

# coding=utf-8

class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue       # 节点元素名称
        self.count = numOccur       # 出现次数
        self.nodeLink = None        # 指向下一个相似节点的指针
        self.parent = parentNode    # 指向父节点的指针
        self.children = {}          # 指向子节点的字典，以子节点的元素名称为键，指向子节点的指针为值

    def inc(self, numOccur):
        self.count += numOccur

    def disp(self, ind=1):
        print ' ' * ind, self.name, ' ', self.count
        for child in self.children.values():
            child.disp(ind + 1)


rootNode = treeNode('pyramid', 9, None)
rootNode.children['eye'] = treeNode('eye', 13, None)
rootNode.children['phoenix'] = treeNode('phoenix', 3, None)
rootNode.disp()

2. 构 建 F P 树 \color{red}2. 构建FP树 2.构建FP树
（1）头指针表
FP-growth算法需要一个称为头指针表的数据结构，就是用来记录各个元素项的总出现次数的数组，再附带一个指针指向FP树中该元素项的第一个节点。这样每个元素项都构成一条单链表。图示说明：

这里使用Python字典作为数据结构，来保存头指针表。以元素项名称为键，保存出现的总次数和一个指向第一个相似元素项的指针。

第一次遍历数据集会获得每个元素项的出现频率，去掉不满足最小支持度的元素项，生成这个头指针表。这个过程相当于Apriori里的1-频繁项集的生成过程。

（2）元素项排序
上文提到过，FP树会合并相同的频繁项集（或相同的部分）。因此为判断两个项集的相似程度需要对项集中的元素进行排序。排序基于元素项的绝对出现频率（总的出现次数）来进行。在第二次遍历数据集时，会读入每个项集（读取），去掉不满足最小支持度的元素项（过滤），然后对元素进行排序（重排序）。

对示例数据集进行过滤和重排序的结果如下：

（3）构建FP树
在对事务记录过滤和排序之后，就可以构建FP树了。从空集开始，将过滤和重排序后的频繁项集一次添加到树中。
如果树中已存在现有元素，则增加现有元素的值；
如果现有元素不存在，则向树添加一个分支。

对前两条事务进行添加的过程：

整体算法过程描述如下：

输入：数据集、最小值尺度
输出：FP树、头指针表
1. 遍历数据集，统计各元素项出现次数，创建头指针表
2. 移除头指针表中不满足最小值尺度的元素项
3. 第二次遍历数据集，创建FP树。对每个数据集中的项集：
    3.1 初始化空FP树
    3.2 对每个项集进行过滤和重排序
    3.3 使用这个项集更新FP树，从FP树的根节点开始：
        3.3.1 如果当前项集的第一个元素项存在于FP树当前节点的子节点中，则更新这个子节点的计数值
        3.3.2 否则，创建新的子节点，更新头指针表
        3.3.3 对当前项集的其余元素项和当前元素项的对应子节点递归3.3的过程

实现以上逻辑的py代码逻辑如下：

# coding=utf-8

class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue       # 节点元素名称
        self.count = numOccur       # 出现次数
        self.nodeLink = None        # 指向下一个相似节点的指针
        self.parent = parentNode    # 指向父节点的指针
        self.children = {}          # 指向子节点的字典，以子节点的元素名称为键，指向子节点的指针为值

    def inc(self, numOccur):
        self.count += numOccur

    def disp(self, ind=1):
        print ' ' * ind, self.name, ' ', self.count
        for child in self.children.values():
            child.disp(ind + 1)


def loadSimpDat():
    simpDat = [['r', 'z', 'h', 'j', 'p'],
               ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
               ['z'],
               ['r', 'x', 'n', 'o', 's'],
               ['y', 'r', 'x', 'z', 'q', 't', 'p'],
               ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
    return simpDat


def createInitSet(dataSet):
    retDict = {}
    for trans in dataSet:
        retDict[frozenset(trans)] = 1
    return retDict



''' 创建FP树 '''
def createTree(dataSet, minSup=1):
    headerTable = {}            # 第一次遍历数据集，创建头指针表
    for trans in dataSet:
        for item in trans:      # 遍历数据集，统计各元素项出现次数，创建头指针表
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]

    for k in headerTable.keys():
        if headerTable[k] < minSup: # 移除不满足最小支持度的元素项
            del(headerTable[k])

    freqItemSet = set(headerTable.keys())
    if len(freqItemSet) == 0:   # 空元素集，返回空
        return None, None

    # 增加一个数据项，用于存放指向相似元素项指针
    for k in headerTable:
        headerTable[k] = [headerTable[k], None]
    retTree = treeNode('Null Set', 1, None) # 根节点

    print dataSet.items()
    for tranSet, count in dataSet.items():  # 第二次遍历数据集，创建FP树
        localD = {} # 对一个项集tranSet，记录其中每个元素项的全局频率，用于排序
        for item in tranSet:
            if item in freqItemSet:
                localD[item] = headerTable[item][0] # 注意这个[0]，因为之前加过一个数据项
        if len(localD) > 0:
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 排序
            updateTree(orderedItems, retTree, headerTable, count) # 更新FP树
    return retTree, headerTable


def updateTree(items, inTree, headerTable, count):
    if items[0] in inTree.children:
        # 有该元素项时计数值+1
        inTree.children[items[0]].inc(count)
    else:
        # 没有这个元素项时创建一个新节点
        inTree.children[items[0]] = treeNode(items[0], count, inTree)
        # 更新头指针表或前一个相似元素项节点的指针指向新节点
        if headerTable[items[0]][1] == None:
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])

    if len(items) > 1:
        # 对剩下的元素项迭代调用updateTree函数
        updateTree(items[1::], inTree.children[items[0]], headerTable, count)


def updateHeader(nodeToTest, targetNode):
    while (nodeToTest.nodeLink != None):
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode



simpDat = loadSimpDat()
initSet = createInitSet(simpDat)
myFPtree, myHeaderTab = createTree(initSet, 3)
myFPtree.disp()

5.3 从一棵FP树种挖掘频繁项集

有了FP树之后，接下来可以抽取频繁项集了。这里的思路与Apriori算法大致类似，首先从单元素项集合开始，然后在此基础上逐步构建更大的集合。

从FP树中抽取频繁项集的三个基本步骤如下：

1. 从FP树中获得条件模式基；
2. 利用条件模式基，构建一个条件FP树；
3. 迭代重复步骤1步骤2，直到树包含一个元素项为止。

1. 抽 取 条 件 模 式 基 \color{red}1. 抽取条件模式基 1.抽取条件模式基
首先从头指针表中的每个频繁元素项开始，对每个元素项，获得其对应的条件模式基（conditional pattern base）。

条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径（prefix path）。简而言之，一条前缀路径是介于所查找元素项与树根节点之间的所有内容。

则每一个频繁元素项的所有前缀路径（条件模式基）为：

z存在于路径{z}中，因此前缀路径为空，另添加一项该路径中z节点的计数值5构成其条件模式基；

r存在于路径{r, z}、{r, y, x, z}、{r, s, x}中，分别获得前缀路径{z}、{y, x, z}、{s, x}，另添加对应路径中r节点的计数值（均为1）构成r的条件模式基；

以此类推。

2. 创 建 条 件 F P 树 \color{red}2. 创建条件FP树 2.创建条件FP树

对于每一个频繁项，都要创建一棵条件FP树。可以使用刚才发现的条件模式基作为输入数据，并通过相同的建树代码来构建这些树。

例如，对于r，即以“{x, s}: 1, {z, x, y}: 1, {z}: 1”为输入，调用函数createTree()获得r的条件FP树；

对于t，输入是对应的条件模式基“{z, x, y, s}: 2, {z, x, y, r}: 1”。

3. 递 归 查 找 频 繁 项 集 \color{red}3. 递归查找频繁项集 3.递归查找频繁项集
有了FP树和条件FP树，我们就可以在前两步的基础上递归得查找频繁项集。

递归的过程是这样的：

输入：我们有当前数据集的FP树（inTree，headerTable）
1. 初始化一个空列表preFix表示前缀
2. 初始化一个空列表freqItemList接收生成的频繁项集（作为输出）
3. 对headerTable中的每个元素basePat（按计数值由小到大），递归：
        3.1 记basePat + preFix为当前频繁项集newFreqSet
        3.2 将newFreqSet添加到freqItemList中
        3.3 计算t的条件FP树（myCondTree、myHead）
        3.4 当条件FP树不为空时，继续下一步；否则退出递归
        3.4 以myCondTree、myHead为新的输入，以newFreqSet为新的preFix，外加freqItemList，递归这个过程

4. 完 整 F P 频 繁 项 集 挖 掘 过 程 p y 代 码 \color{red}4. 完整FP频繁项集挖掘过程py代码 4.完整FP频繁项集挖掘过程py代码

# coding=utf-8

class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue       # 节点元素名称
        self.count = numOccur       # 出现次数
        self.nodeLink = None        # 指向下一个相似节点的指针
        self.parent = parentNode    # 指向父节点的指针
        self.children = {}          # 指向子节点的字典，以子节点的元素名称为键，指向子节点的指针为值

    def inc(self, numOccur):
        self.count += numOccur

    def disp(self, ind=1):
        print ' ' * ind, self.name, ' ', self.count
        for child in self.children.values():
            child.disp(ind + 1)


def loadSimpDat():
    simpDat = [['r', 'z', 'h', 'j', 'p'],
               ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
               ['z'],
               ['r', 'x', 'n', 'o', 's'],
               ['y', 'r', 'x', 'z', 'q', 't', 'p'],
               ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
    return simpDat


def createInitSet(dataSet):
    retDict = {}
    for trans in dataSet:
        retDict[frozenset(trans)] = 1
    return retDict



''' 创建FP树 '''
def createTree(dataSet, minSup=1):
    headerTable = {}            # 第一次遍历数据集，创建头指针表
    for trans in dataSet:
        for item in trans:      # 遍历数据集，统计各元素项出现次数，创建头指针表
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]

    for k in headerTable.keys():
        if headerTable[k] < minSup: # 移除不满足最小支持度的元素项
            del(headerTable[k])

    freqItemSet = set(headerTable.keys())
    if len(freqItemSet) == 0:   # 空元素集，返回空
        return None, None

    # 增加一个数据项，用于存放指向相似元素项指针
    for k in headerTable:
        headerTable[k] = [headerTable[k], None]
    retTree = treeNode('Null Set', 1, None) # 根节点

    print dataSet.items()
    for tranSet, count in dataSet.items():  # 第二次遍历数据集，创建FP树
        localD = {} # 对一个项集tranSet，记录其中每个元素项的全局频率，用于排序
        for item in tranSet:
            if item in freqItemSet:
                localD[item] = headerTable[item][0] # 注意这个[0]，因为之前加过一个数据项
        if len(localD) > 0:
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 排序
            updateTree(orderedItems, retTree, headerTable, count) # 更新FP树
    return retTree, headerTable


def updateTree(items, inTree, headerTable, count):
    if items[0] in inTree.children:
        # 有该元素项时计数值+1
        inTree.children[items[0]].inc(count)
    else:
        # 没有这个元素项时创建一个新节点
        inTree.children[items[0]] = treeNode(items[0], count, inTree)
        # 更新头指针表或前一个相似元素项节点的指针指向新节点
        if headerTable[items[0]][1] == None:
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])

    if len(items) > 1:
        # 对剩下的元素项迭代调用updateTree函数
        updateTree(items[1::], inTree.children[items[0]], headerTable, count)


def updateHeader(nodeToTest, targetNode):
    while (nodeToTest.nodeLink != None):
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode


def findPrefixPath(basePat, treeNode):
    ''' 创建前缀路径 '''
    condPats = {}
    while treeNode != None:
        prefixPath = []
        ascendTree(treeNode, prefixPath)
        if len(prefixPath) > 1:
            condPats[frozenset(prefixPath[1:])] = treeNode.count
        treeNode = treeNode.nodeLink
    return condPats


def ascendTree(leafNode, prefixPath):
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)


def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
    bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])]
    for basePat in bigL:
        newFreqSet = preFix.copy()
        newFreqSet.add(basePat)
        freqItemList.append(newFreqSet)
        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
        myCondTree, myHead = createTree(condPattBases, minSup)

        if myHead != None:
            # 用于测试
            print 'conditional tree for:', newFreqSet
            myCondTree.disp()

            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)


def fpGrowth(dataSet, minSup=3):
    initSet = createInitSet(dataSet)
    myFPtree, myHeaderTab = createTree(initSet, minSup)
    freqItems = []
    mineTree(myFPtree, myHeaderTab, minSup, set([]), freqItems)
    return freqItems


dataSet = loadSimpDat()
freqItems = fpGrowth(dataSet)
print freqItems

FP-growth算法是一种用于发现数据集中频繁模式的有效方法。FP-growth算法利用Apriori原则，执行更快。Apriori算法产生候选项集，然后扫描数据集来检查它们是否频繁。由于只对数据集扫描两次，因此FP-growth算法执行更快。在FP-growth算法中，数据集存储在一个称为FP树的结构中。FP树构建完成后，可以通过查找元素项的条件基及构建条件FP树来发现频繁项集。该过程不断以更多元素作为条件重复进行，直到FP树只包含一个元素为止。

6. 关联规则和协同过滤的区别

• 关联规则是基于transaction，而协同过滤基于用户偏好（评分）
• 商品组合使用的是购物篮分析，也就是Apriori算法，协同过滤计算的是相似度
• 关联规则没有利用“用户偏好”，而是基于购物订单进行的频繁项集挖掘

关联规则不需要考虑用户一定时期内的偏好，而是基于Transaction
只要能将数据转换成Transaction，就可以做购物篮分析：

• Step1、把数据整理成id=>item形式，转换成transaction
• Step2、设定关联规则的参数（support、confident）挖掘关联规则
• Step3、按某个指标（lift、support等）对以关联规则排序
  在很多实际情况中，我们需要根据公司的业务去设计和使用推荐算法，单一的算法并不能解决复杂问题。

7. 关联规则中的最小支持度、最小置信度该如何确定

• 最小支持度，最小置信度是实验出来的
• 最小支持度：
  不同的数据集，最小值支持度差别较大。可能是0.01到0.5之间，可以从高到低输出前20个项集的支持度作为参考
• 最小置信度：可能是0.5到1之间
• 提升度：表示使用关联规则可以提升的倍数，是置信度与期望置信度的比值，提升度至少要大于1

8. 相关性分析

如果各自变量x跟因变量y之间没有相关性，还需要做回归分析么？

• 如果有一定的相关性了，然后再通过回归分析进一步验证他们之间的准确关系
• 通过相关分析求得相关系数没有回归分析的准确
• 相关分析是一种描述性的分析，而回归分析得到的结果更为重要和准确

1. 相 关 性 分 析 指 标 \color{red}1. 相关性分析指标 1.相关性分析指标
pearson，衡量两个数据集合是否在一条线上面，针对线性数据的相关系数计算，对于非线性数据有误差

kendall，反映分类变量相关性的指标，通常用于评分数据一致性水平研究，比如评委打分，数据排名等

spearman：非线性的，非正太分布的数据的相关系数

pearson系数，使用最广泛的相关性统计量，用于测量两组连续变量之间的线性关联程度

2. 相 关 性 分 析 使 用 \color{red}2. 相关性分析使用 2.相关性分析使用

 # 构造一元二次方程，y=2x*x+1 非线性关系
def compute(x):
    return 2*x*x+1
x=[i for i in range(100)]
y=[compute(i) for i in x]
data = pd.DataFrame({'x':x,'y':y})
# 查看pearson系数
print(data.corr())
print(data.corr(method='spearman'))
print(data.corr(method='kendall'))

9. 回归分析（Regression）

• 确定两种或两种以上变量之间相互依赖的定量关系的统计方法，使用非常广泛
• 按照涉及的变量的多少，分为一元分析和多元回归分析
• 按照因变量的多少，分为简单回归分析和多重回归分析
• 按照自变量和因变量之间的关系类型，分为线性回归分析和非线性回归分析
  
  1. 常 用 损 失 函 数 \color{red}1. 常用损失函数 1.常用损失函数
  损失函数作用：损失函数可以衡量模型的好坏
  MSE，均方误差，是在回归问题中比较常用的损失函数

2. 导 入 相 关 包 \color{red}2. 导入相关包 2.导入相关包

from sklearn.linear_model import LinearRegression
from sklearn.preprocessing import PolynomialFeatures

clf = linear_model.LinearRegression()
fit(X,y)，训练，拟合参数
predict(X) ，预测
coef_ ，存放回归系数
intercept_，存放截距
score(X,y)， 得到评分结果，R方（确定系数）

注意：在进行多项式回归之前，需要对数据进行变换，因为模型里包含 x²等变量，所以在创建数据之后要将x转换为 x²

3. R 方 （ r − s q u a r e d ） \color{red}3. R方（r-squared） 3.R方（r−squared）

R方也叫确定系数（coefficient of determination），表示模型对现实数据拟合的程度，评估预测效果

• R方计算，等于1减去y对回归方程的方差（未解释离差）与y的总方差的比值
• 一元线性回归中R方等于皮尔逊积矩相关系。比如，R平方=0.8，表示回归关系可以解释因变量80%的变异。换句话说，如果我们能控制自变量x不变，那么因变量y的变异程度会减少80%。
  注意：在sklearn计算中，相关系数有正负

4. 一 元 回 归 与 多 元 回 归 \color{red}4. 一元回归与多元回归 4.一元回归与多元回归

TO DO：一元线性回归
x = np.array([5, 15, 25, 35, 45, 55]).reshape((-1, 1))
y = np.array([5, 20, 14, 32, 22, 38])
多元线性回归
x = [[0, 1], [5, 1], [15, 2], [25, 5], [35, 11], [45, 15], [55, 34], [60, 35]]
y = [4, 5, 20, 14, 32, 22, 38, 43]
多项式回归
x = np.array([5, 15, 25, 35, 45, 55]).reshape((-1, 1))
y = np.array([15, 11, 2, 8, 25, 32])

参考资料

1.关联分析算法（Association Analysis）Apriori算法和FP-growth算法初探