精华内容
下载资源
问答
  • 关联规则学习

    2014-01-03 16:23:14
    对于一个二项规则例如“A→B”,支持度是指A与B同时出现的概率,即P(A B);置信度是B关于A的条件概率,即P(B | A);提升度是B的概率的提升,即P(B | A) / P(B)。 频繁项集: 闭集 极大频繁项集 apriori算法:

    主要的指标包括:支持度support,置信度confidence,提升度lift。对于一个二项规则例如“A→B”,支持度是指A与B同时出现的概率,即P(A B);置信度是B关于A的条件概率,即P(B | A);提升度是B的概率的提升,即P(B | A) / P(B)。

    频繁项集:

    闭集

    极大频繁项集

    apriori算法:

    1. fp-growth 为什么是从支持度从小到大分配(想出来好几次都忘了,次哦):
      原因1: 支持度小的相比一定长,这样能很好的分离出闭集,也就是绝对不会产生重复的频繁项集.
      原因2:支持度大的,还分配多的,容易reduce端倾斜,而且分离效果没那么好
      举例: 1234 123 12 :
      从多到少:
      1234  123  12 
      234    23
      34 
      从少到多:
      4321  
      321     321
      21        21       21


    展开全文
  • 关联规则来源自所有频繁项集 从前面对置信度的形式化描述我们知道,关联规则来源于每一轮迭代中产生的频繁项集(从C1开始,因为空集对单项集的支持推导是没有意义的) confidence(A=>B)=(B∣A)=support(AUB)support...


    ## 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)} (AB)=(B)(AB)

    置信度(牛奶→啤酒) = 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:如果一个集合是频繁项集,则它的所有子集都是频繁项集 Apriori1

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

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

    假设集合{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)=(BA)=support(A)support(AUB)=supportcount(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) PHS=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.FPpy

    # 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. 关联规则和协同过滤的区别

    协同过滤(collaborative filtering)按维基百科的说法,是一种在推荐系统中广泛应用的技术。该技术通过分析用户或者事物之间的相似性(“协同”),来预测用户可能感兴趣的内容并将此内容推荐给用户。这里的相似性可以是人口特征(性别、年龄、居住地等)的相似性,也可以是历史浏览内容的相似性(比如都关注过和中餐相关的内容),还可以是个人通过一定机制给予某个事物的回应(比如一些教学网站会让用户对授课人进行评分)。比如,用户A和B都是居住在北京的年龄在20-30岁的女性,并且都关注过化妆品和衣物相关的内容。这种情况下,协同过滤可能会认为,A和B相似程度很高。于是可能会把A关注B没有关注的内容推荐给B,反之亦然。

    协同过滤基于如下基本假设:如果一个人A在一个问题上和另一个人B持相同观点,那么对于另外一个问题,比起随机选择的一个路人甲,A更有可能同B持相同观点。

    协同过滤依赖用户偏好信息,偏好又称为用户评分(rating),分为主动评分和被动评分。自动评分指用户使用系统提供的方式进行评分或者评价; 被动评分则根据使用者的行为模式由系统代替使用者完成评价,行为模式包括用户的浏览行为、购买行为等等。

    User-based 的协同过滤和 Item-based 的协同过滤是两个最常用的技术,它俩统称为Memory based的协同过滤技术,他们共有的缺点是数据稀疏,难以处理大数据量给出即时结果(item-based的协同过滤比user-based的协同过滤稍好一些),因此发展出以模型为基础的协同过滤技术。 以模型为基础的协同过滤(Model-based Collaborative Filtering)是先用历史资料得到一个模型,再用此模型进行预测。以模型为基础的协同过滤广泛使用的技术包括Latent Semantic Indexing、Bayesian Networks等等。

    User-based的协同过滤用相似统计的方法得到具有相似爱好或者兴趣的相邻使用者,以下是它的详细步骤:

    1. 收集用户信息:收集可以代表用户兴趣的信息。一般的网站系统使用评分的方式或是给予评价,这种方式被称为“主动评分”。另外一种是“被动评分”,是根据用户的行为模式由系统代替用户完成评价,不需要用户直接打分或输入评价资料。电子商务网站在被动评分的资料获取上有其优势,用户购买的商品记录是相当有用的资料。
    2. 最近邻搜索(Nearest neighbor search, NNS):以用户为基础(User-based)的协同过滤的出发点是与用户兴趣爱好相同的另一组用户,就是计算两个用户的相似度。寻找n个和A有相似兴趣用户,然后把他们对M的评分作为A对M的评分预测。
    3. 产生推荐结果 有了最近邻集合,就可以对目标用户的兴趣进行预测,产生推荐结果。依据推荐目的的不同进行不同形式的推荐, 较常见的推荐算法有Top-N 推荐和关联推荐。Top-N 推荐是针对个体用户产生,对每个人产生不一样的结果,例如:透过对A使用者的最近邻使用者进行统计,选择出现频率高且在A使用者的评分项目中不存在的,作为推荐结果。关联推荐是对最近邻使用者的记录进行关联规则(association rules)挖掘。

    Item-based的协同过滤技术实现方式同 User-based的协同过滤类似,只是分析目标由用户变成了Item。

    关联规则分析 (Association Rules,又称 Basket Analysis) 用于从大量数据中挖掘出有价值的数据项之间的相关关系。关联规则解决的常见问题如:“如果一个消费者购买了产品A,那么他有多大机会购买产品B?”以及“如果他购买了产品C和D,那么他还将购买什么产品?”所以 关联规则最经典的应用就是做购物篮分析:

    • Step1、把数据整理成id=>item形式,转换成transaction
    • Step2、设定关联规则的参数(support、confident)挖掘关联规则
    • Step3、按某个指标(lift、support等)对以关联规则排序

    总结来说,协同过滤是推荐系统中采用的名称,理论基础之一是数据挖掘中的关联规则。两者的区别比较明显,

    1. 关联规则面向的是 transaction,而协同过滤面向的是用户偏好(评分)
    2. 协同过滤在计算相似商品的过程中可以使用关联规则分析,但是在有用户评分的情况下(非1/0),协同过滤算法应该比传统的关联规则更能产生精准的推荐。
    3. 协同过滤的约束条件没有关联规则强,或者说更为灵活,可以考虑更多的商业实施运算和特殊的商业规则。

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

    • 关联规则中的最小支持度、最小置信度,可以从0.01,0.5很小的数开始试,是可以实验出来的。
    • 最小支持度:
      不同的数据集,最小值支持度差别较大。可能是0.01到0.5之间,可以从高到低输出前20个项集的支持度作为参考
    • 最小置信度:可能是0.5到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.Rrsquared

    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算法初探

    展开全文
  • 关联规则学习-笔记

    千次阅读 2012-10-16 21:07:38
    第二步由频繁项集合,得出关联规则。对于长度为k的频繁项,其可能产生的规则一共为2的k次方个。简单分析可以得到,对于两个规则:A1->B1和A2->B2,如果A1是A2的子集合(自然B2也是B1的子集了),则可以得出,如果A1-...

    第一步是要产生所有的频繁项集合,即满足一定支持度的项的集合。

    依次递归产生1项,2项,...,n-1项,n项。所有的k项由k-1项得到,并不需要列举所有的k项可能的组合,由于如果某k项为频繁项,则其所有的一个k个子k-1项必为频繁项。可按k-1项排序,只对相邻的两项做处理。如果相邻两项的前k-2项都相等,只有第k-1项不相等,则合并两项,得到新的k项为候选k项。如果相邻两k-1项的前k-2项不相同,即便此两个k-1项仍然有相同的k-2个元素,两者合并得到一个新的k项,则可以证明一定存在新k项的某一个子k-1项不是频繁集,或者此k项已经加入了候选k项集合中。

    得到候选k项,如果满足支持度并且其所有一个k个k-1子项都是频繁项,则此k项也是频繁项。

    第二步由频繁项集合,得出关联规则。对于长度为k的频繁项,其可能产生的规则一共为2的k次方个。简单分析可以得到,对于两个规则:A1->B1和A2->B2,如果A1是A2的子集合(自然B2也是B1的子集了),则可以得出,如果A1->B1成立,则A2->B2也成立。

    对每一个频繁项,首先产生1项规则,即规则的后置条件的长度为1。所有的m项规则由所有的m-1项规则得到。把频繁项看成整个商品集合,把m-1项规则看成是m-1项频繁项,把最小置信度看成是最小支持度,把本频繁项的数量与m项规则的前置条件项的数量看做是支持度,这个算法雷同于第一步的算法了。

    注:对于频繁项挖掘,需要满足最小支持度,不过有一些冷门商品,由于销量很小,不能满足最小支持度,但是利润很大,仍然需要发现可以与之搭配出卖的商品。这就需要引入可变的最小支持度,即对于不同的频繁项,要求满足不同的最小支持度。可对每一个商品定义最小支持度,频繁项的最小支持度即为各个商品最小支持度的最小值。但是这又引入了新的问题,因为有可能存在子项不是频繁项而父项是频繁项,不满足上面算法的闭包规则。解决本问题的方法是所有商品按照满足的最小支持度升序排列,这样能够保证频繁项A是频繁项B的子项,则二者的最小支持度一样的,都是最开始的商品的最小支持度。

    展开全文
  • 关联规则简介数据挖掘是⼀项从⼤量的记录数据中提取有价值的、⼈们感兴趣的知识,这些知识是隐含的、事先未知的有⽤信息,提取的知识⼀般可表⽰为概念(Concepts)、规则(Rules)、规律(Regular ides)、模式(Patterns)...

    add1bcb30dde1a625c13f3baaf89254b.png

    关联规则简介

    数据挖掘是⼀项从⼤量的记录数据中提取有价值的、⼈们感兴趣的知识,这些知识是隐含的、事先未知的有⽤信息,提取的知识⼀般可表⽰为概念(Concepts)、规则(Rules)、规律(Regular ides)、模式(Patterns)等形式。

    关联规则是当前数据挖掘研究的主要⽅法之⼀,它反映⼀个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在⼀定的关联关系,那么,其中⼀个事物就能够通过其他事物预测到。

    典型的关联规则发现问题是对超市中的货篮数据(Market Basket)进行分析。通过发现顾客放⼊货篮中的不同商品之间的关系来分析顾客的购买习惯。

    关联规则的基本概念

    设I={i1, i2,…, im}为所有项的集合,D为事务数据库,事务T是⼀个项目子集(T⊆I)。设A是⼀个由项目构成的集合,称为项集。事务T包含项集A,当且仅当A⊆T。如果项集A中包含k个项目,则称其为k项集

    项集A在事务数据库D中出现的次数占D中总事务的百分⽐叫做项集的支持度。如果项集的⽀持度超过用户给定的最小支持度阈值,就称该项集是频繁项集

    关联规则是形如X⇒Y的逻辑蕴含式,其中X⊂I,Y⊂I,且X∩Y=∅。

    如果事务数据库D中有s%的事务包含X∪Y,则称关联规则X⇒Y的支持度为s%。

    关联规则的信任度为support (X∪Y)/support (X)。

    通俗的讲,就是项集A在所有数据库中所占的百分比即为A的支持度

    项集A和项集B同时发生的概率比上项集A发生的概率称之为项集A的信任度

    我们在实际运用当中,往往会给予支持度和信任度一定的阈值,是否满足这一阈值我们称之为强关联规则,强关联规则就是⽀持度和信任度分别满足用户给定阈值的规则。

    接下来,我们要介绍一种用于挖掘出数据关联规则的常用算法--Apriori算法。它用来找出数据值中频繁出现的数据集合,找出这些集合的模式有助于我们做一些决策。比如在常见的超市购物数据集,或者电商的网购数据集,如果我们找到了频繁出现的数据集,那么对于超市,我们可以优化产品的位置摆放,对于电商,我们可以优化商品所在的仓库位置,达到节约成本,增加经济效益的目的。


    Apriori算法

    Apriori算法将发现关联规则的过程分为两个步骤

    1. 通过迭代,检索出事务数据库中的所有频繁项集,即⽀持度不低于⽤户设定的阈值的项集。
    2. 利⽤频繁项集构造出满足用户最小信任度的规则

    挖掘或识别出所有频繁项集是该算法的核心,占整个计算量的⼤部分。

    Apriori的两条重要性质:

    性质1:频繁项集的所有非空子集必为频繁项集。

    性质2:非频繁项集的超集⼀定是⾮频繁的。

    Apriori的具体步骤:

    连接步:为找Lk ,通过将Lk-1与⾃⾝连接产⽣候选k项集的集合Ck

    剪枝步:Ck是Lk 的超集,也就是说,Ck的成员可以是也可以不是频繁的,但所有的频繁k项集都包含在Ck中。任何非频繁的(k-1)项集都不是频繁k项集的⼦集。

    依靠之前的两条性质,我们可以在实际应用当中省去很多资源,比如在电商里面有百万级别的商品上新,两两组合后的维度是很惊人的,所以我们可以用到上面的方法,重复Apriori的步骤,在集合Ck中先行过滤掉支持度低的项集(性质2:非频繁项集的超集⼀定是⾮频繁的),在多次重复后,可以大大降低统计的量。

    Apriori算法的不足

    1. Ck中的每个元素需在交易数据库中进⾏验证来决定其是否加入Lk,频繁的扫描调用是对数据库和服务器造成很大的压力
    2. 验证过程是性能瓶颈
    3. 交易数据库可能⾮常⼤
    4. 比如频集最多包含10个项,那么就需要扫描交易数据库10遍
    5. 需要很⼤的I/O负载

    因为Apriori算法本质是时间换空间的,换句话说就是利用多次的读取来利用有限的空间来完成计算,但是随着摩尔定律,我们的空间不在像之前那样宝贵和捉襟见肘了,所以,我们开始思考能不能有一种算法,利用空间,来换取时间,一次获得更快的速度

    如下个算法,只扫描一两次数据库,同时利用这两次扫描的来存储下的关键数据来获得相应的规则。

    FP-tree算法

    2000年,Han等提出了⼀个称为FP-tree的算法。FP-tree算法特点是只进⾏2次数据库扫描。

    1. no候选集
    2. 直接压缩数据库成⼀个频繁模式树
    3. 通过这棵树⽣成关联规则

    FP-tree两个主要步骤

    1. 利用事务数据库中的数据构造FP-tree
    2. 从FP-tree中挖掘频繁模式

    步骤1:构造 FP-tree树

    具体过程:

    1. 扫描数据库⼀次,得到频繁1-项集
    2. 把项按⽀持度递减排
    3. 再⼀次扫描数据库,建⽴FP-tree

    步骤2:频繁模式的挖掘

    具体过程:

    根据事务数据库D 和最⼩⽀持度min_sup, 调⽤建树过程建⽴FP-tree;

    if (FP-tree 为简单路径):

    将路径上⽀持度计数⼤于等于min_sup 的节点任意组合,得到所需

    的频繁模式;

    else:

    初始化最⼤频繁模式集合为空;

    按照⽀持频率升序,以每个1- 频繁项为后缀,调用挖掘算法挖掘最大频繁模式集。

    根据最⼤频繁模式集合中最⼤频繁模式,输出全部的频繁模式。

    FP - tree 算法的优缺点

    优点

    FP-tree 算法只需对事务数据库进⾏⼆次扫描。

    避免产⽣的⼤量候选集。

    缺点

    要递归⽣成条件数据库和条件FP-tree,所以内存开销⼤。

    只能用于挖掘单维的布尔关联规则。

    不多就这样了,希望本文能够帮到你!~!

    最后打个小广告,我的公众号,喜欢写点学习中的小心得,不介意可以关注下!~!

    cc679fc919b2430f58a4acc7fddfb596.png
    展开全文
  • 学习笔记28-关联规则

    2017-09-06 16:28:18
    关联规则关联规则是数据挖掘常用的算法,目的是学习不同变量之间的相互关系。比如电商平台中,我们知道经常同时被购买的货物,这就可以当成一种关联规则。项集这些频繁地被同时购买的货物项,称为项集(Item set),也...
  • 文章目录C++primer-学习心得-第11章-关联容器11.1 使用关联容器练习11.411.2 关联容器概述1. 定义关联容器练习11.7练习11.82. 关键字类型的要求3.pair类型练习11.12练习11.13练习11.1411.3 关联容器操作1.关联容器...
  • less学习心得

    2017-07-12 15:55:14
    下面是我学习less的一些心得,大多数都是直接粘贴官网的,不过也加上了自己的一些理解,晚些时候再一个个做demo出来。
  • Hibernate学习心得

    2021-03-31 09:25:29
    Hibernate学习心得 1.hibernate的简介: Hibernate 是一款免费开源的 持久层的 ORM 框架 ,它对 JDBC 进行了轻量级的对象封装,将对象与数据库表建立了映射关系,使 Java 编程人员可以随心所欲地使用面向对象的编程...
  • Java学习心得

    千次阅读 2011-07-19 10:24:39
    java心得!--很好的java学习历程(转自张国宝) 1. 数组有没有length()这个方法? String有没有length()这个方法?  答:数组没有length()这个方法,有length的属性。
  • 学习心得

    2017-12-25 17:56:52
    Socket IO是比较重要的一块,要搞懂的是阻塞/非阻塞的区别、同步/异步的区别,借此理解阻塞IO、非阻塞IO、多路复用IO、异步IO这四种IO模型,Socket IO如何和这四种模型相关联。这是基本一些的,深入一些的话,就会问...
  • 恳请博主不要误会,若是给你造成麻烦立即删除,后面开始学习心得和笔记的记载。希望大家能一起成功! “啤酒与尿布”故事: 这是一个几乎被举烂的例子,“啤酒与尿布”的故事产生于20世纪90年代的美国沃尔玛超市...
  • 计算机网络学习心得—概述

    千次阅读 2019-07-10 21:32:26
    “知识的输出对于自身的成长其实非常重要”,这句话让我决定用写博客的方式记录下自己学习心得。目录结构就决定用谢希仁第五版《计算机网络》中的架构,只是细节上会修改一点。文中的词句,决定想到什么写什么,可能...
  • 机器学习贝叶斯学习心得Update: This post is part of a blog series on Meta-Learning that I’m working on. Check out part 1 and part 2. 更新 :这篇文章是我正在从事的有关元学习的博客系列的一部分。 检出 第...
  • windows类书的学习心得

    万次阅读 2014-07-30 13:11:46
    windows类书的学习心得 这篇文章应该是凑的,不够很长,还是值得读的,转发来。下满是原网址: http://www.blogjava.net/sound/archive/2008/08/21/40499.html 创建人: paul 现在的计算机图书发展的可真快,很久...
  • Assembly学习心得

    千次阅读 2004-10-27 18:56:00
    http://blog.csdn.net/etmonitor/Assembly学习心得说明:最近开始准备把学到的.NET知识重新整理一遍,眼过千遍不如手过一遍,所以我准备记下我的学习心得,已备参考。J各位都是大虾了,如果有哪些错误或者不完整的...
  • 最近在学习《Python数据分析与挖掘实战》中的案例,写写自己的心得。...应用Apriori关联规则挖掘规律 1.聚类部分函数分析: def programmer_1(): datafile = "C:/Users/longming/Desktop/chapter8...
  • awk数组学习心得

    2013-12-05 18:25:35
    awk数组的学习心得 http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=2312439&fromuid=29322176 在文本处理的工作中,awk的数组是必不可少的工具,在这里,同样以总结经验和教训的方式和大家分享下我的一些...
  • Python前奏: 第一章对其语法、程序的框架、保留字的学习 #注释(内容不被翻译) print(“字符串”) 关联标识符的过程: 命名规则:大小写字母、数字、下划线和汉字等字符及组织 TempStr、Python_Great、这是们...
  • STL学习心得

    2020-04-28 22:51:41
    关联式容器必须定义出排序准则,默认情况是重载operator (对于基本数据类型(int,long,char,double,…)而言,以上条件总是满足) STL容器的共同操作 初始化 1.产生一个空容器 std::list l; 2.以另一个容器元素为...
  • 英语学习心得总结

    2019-08-07 14:12:40
    心得仅供参考,如果能帮到你就太好了。 学习误区: 误区1:我一天背10个,10天就能背100个,100天就能背1000个了,很轻松。 纠正: 放心,你一定做不到,因为一定会在某一天会因为事情特别多或者心情怠惰而...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,620
精华内容 2,248
关键字:

关联规则学习心得