精华内容
下载资源
问答
  • 支持度和置信度

    千次阅读 2016-11-14 21:38:23
    支持度(Support)的公式是:Support(A->B)=P(A U B)。支持度揭示了A与B同时出现的概率。如果A与B同时出现的概率小,说明A与B的关系不大;如果A与B同时出现的非常频繁,则说明A与B总是相关的。  置信度(Confidence)...
    支持度(Support)的公式是:Support(A->B)=P(A U B)。支持度揭示了A与B同时出现的概率。如果A与B同时出现的概率小,说明A与B的关系不大;如果A与B同时出现的非常频繁,则说明A与B总是相关的。
        置信度(Confidence)的公式式:Confidence(A->B)=P(A | B)。置信度揭示了A出现时,B是否也会出现或有多大概率出现。如果置信度度为100%,则A和B可以捆绑销售了。如果置信度太低,则说明A的出现与B是否出现关系不大。
        示例:某销售手机的商场中,70%的手机销售中包含充电器的销售,而在所有交易中56%的销售同时包含手机和充电器。则在此例中,支持度为56%,置信度为70%。

    支持度: P(A∪B),即A和B这两个项集在事务集D中同时出现的概率。

    置信度: P(B|A),即在出现项集A的事务集D中,项集B也同时出现的概率。

    展开全文
  • 浅谈支持度与置信度

    千次阅读 2020-05-24 15:32:36
    浅谈数据挖掘支持度(support)与置信度(confidence)前言参考样本定义与理解支持度(support)支持度实际作用置信度(confidence)置信度的实际作用代码与结果参考 前言 由于本人初学数据挖掘,许多知识与见解还有...

    前言

    由于本人初学数据挖掘,许多知识与见解还有所欠缺,因为看书《python数据挖掘入门与实践》有点没能理解,所以查阅了一些资料,有一些自己的理解,若有错误,望各位海涵并指点本人的不足。

    参考样本

    由于下面的理解会讨论到相关的参考样本,所以这里先列出书上实例的参考样本节选。(1代表了购买,0代表没有购买)
    参考样本

    定义与理解

    在具体讨论支持度与置信度时,需要先讨论两个概念,规则和应验。
    规则:即给出一个前提条件,得到一个对应的结论。就好比:我如果买了苹果,那么我有可能会继续选择香蕉
    应验:即事件的发生。就好比:我买了苹果,也确实买了香蕉,那么就应验了上一条规则

    支持度(support)

    在《python数据挖掘入门与实践》一书中,对支持度(support)的定义为:
    数据集中规则应验的次数,统计起来很简单。有时候,还需要对支持度进行规范化,再除以规则有效前提下的总数量。支持度衡量的是给定规则应验的比例

    由于作为初学者没有太懂这句话的含义,所以查询了相关资料,在资料中写到,支持度即:表示同时包含A和B的事务所占所有事务的比例。用公式表示则是:
    support(A → B) = P(A ∪ B)

    支持度实际作用

    从概率上讲,支持度反映了一组事务(商品)被选择的概率,就假设一个商场从支持度推测出苹果和香蕉的支持度很高,那么就证明了苹果与香蕉这个组合更受人们的欢迎,所以商家可以将香蕉和苹果放在接近入口的地方,方便人们的购买。

    置信度(confidence)

    在《python数据挖掘入门与实践》一书中,对置信度(confidence)的定义是:
    置信度衡量的是规则准确率如何,即符合给定条件(即规则的“如果”语句所表示的前提条件)的所有规则里,跟当前规则结论一致的比例有多大。计算方法为首先统计当前规则的出现次数,再用它来除以条件(“如果”语句)相同的规则数量。

    我不确定多少人和我一样看了这句话后云里雾里的,反正我是查阅了资料,资料里写的是:表示使用包含A的事务(商品)中同时包含B事务(商品)的比例,即同时包含A和B的事务(商品)占包含A事务的比例。相应的公式为:
    Confidence(A->B)=P(A | B)

    置信度的实际作用

    置信度的实际作用是能够做到关联规则挖掘,判断用户最有可能选择哪些组合的商品,即计算用户选择了A商品(前提条件)后又选择了B商品(结论)的概率。
    就比如曾经有个案例,发现婴儿的爸爸在购买尿布时很有可能购买啤酒,于是商家就将尿布和啤酒放一起卖,增加了销售额,这就是置信度在实际生活中的一个场景。

    代码与结果

    由于书上的代码中支持度只是具体的数值而非概率,所以我进行了一定的优化,代码在书上都有,我这里截取最核心的部分:

    # 遍历所有样本
    for sample in X:
        for premise in range(n_features):
            # 如果客户没有购买,则跳过
            if sample[premise] == 0:
                continue
            num_occurances[premise] += 1
            for conclusion in range(n_features):
                # 不需要判断用户购买了A,又购买了A
                if premise == conclusion:
                    continue
                # 当前提条件与结论都应验后,有效数据 + 1,否则无效数据 + 1
                if sample[conclusion] == 1:
                    valid_rules[(premise, conclusion)] += 1
                else:
                    invalid_rules[(premise, conclusion)] += 1
    
    support = defaultdict(float)
    confidence = defaultdict(float)
    
    # 支持度
    for premise, conclusion in valid_rules.keys():
        rule = (premise, conclusion)
        support[rule] = valid_rules[rule] / n_samples
    
    # 置信度
    for premise, conclusion in valid_rules.keys():
        rule = (premise, conclusion)
        confidence[rule] = valid_rules[rule] / num_occurances[premise]
    
    for premise, conclusion in confidence:
        premise_name = features[premise]
        conclusion_name = features[conclusion]
        print("Rule: if a person buys {0} they will also buy {1}".format(premise_name, conclusion_name))
        print(" - Confidence: {0:.3f}".format(confidence[(premise, conclusion)]))
        print(" - Support: {0}".format(support[(premise, conclusion)]))
        print("")
    

    部分结果截图如下:
    部分结果图片
    说明:
    X:存放了所有的样本集合的ndarray对象
    n_features:X.shape[1],即该数组(样本)有多少列
    n_samples:X.shape[0],即该数组(样本)有多少行
    valid_rules:defaultdict(int),规则应验次数
    invalid_rules:defaultdict(int),规则无效次数

    参考

    hooly.数据挖掘关联分析中的支持度、置信度和提升度.简书,2017
    Robert Layton.python数据挖掘入门与实践〔M〕.人民邮电出版社,2016:6-10

    展开全文
  • 海量数据挖掘Mining Massive Datasets(MMDs) -Jure Leskovec courses学习笔记之关联规则Apriori算法的改进:非hash方法 - 大数据集下的频繁项集:挖掘随机采样算法、SON算法、Toivonen算法 Apriori算法

    http://blog.csdn.net/pipisorry/article/details/48914067

    海量数据挖掘Mining Massive Datasets(MMDs) -Jure Leskovec courses学习笔记之关联规则Apriori算法的改进:非hash方法 - 大数据集下的频繁项集:挖掘随机采样算法、SON算法、Toivonen算法

    Apriori算法的改进:大数据集下的频繁项集挖掘

    1. 前面所讨论的频繁项都是在一次能处理的情况。如果数据量过大超过了主存的大小,这就不可避免的得使用k步来计算频繁项集。这里有许多应用并不需要发现所有的频繁项。比方说在超市,我们只要找到大部分的销售频繁关联项就够了,而不必找出所有的频繁项。

    2. Apriori算法在计算频繁多项集时,要一步一步计算,会有相当多的频繁项集产生。这样主存可能存在不足的痛苦。An alternative is to compress all the work into one or two passes.But It may have both false positives and false negatives.But if the data cooperates there will not be too many of either.

    基于采样的方法。基于前一遍扫描得到的信息,对此仔细地作组合分析,可以得到一个改进的算法,Mannila等先考虑了这一点,他们认为采样是发现规则的一个有效途径。

    基于划分的方法。Savasere等设计了一个基于划分(partition)的算法.这个算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频集,然后把产生的频集合并,用来生成所有可能的频集,最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存,每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。

    Note: 算法可行的标准是:几乎没有false negatives(频繁项集当做非频繁项集)和false positives(非频繁项集被判为频繁项集)。

    皮皮blog



    随机采样算法(基于采样的方法)

    简单的随机采样算法

    不是使用整个文件或篮子,我们使用篮子的一个子集的集合并假装他们是整个数据集,并调整支持度的阈值来适应小篮子。

    基本思路就是:先采样部分basket,在其上运行Apriori(PCY...)算法,并调整相应支持度阈值。

      

    Note: 采样得到的子数据集直接存入主存,第一次载入主存后,之后扫描数据子集就不用再次进行I/O操作了。

    采样方式

    最安全的抽样方式是读入整个数据集,然后对于每个篮子,使用相同的概率p选择样品。假设这有m个篮子在整个文件中。在最后,我们需要选择的样品的数量接近pm个篮子的样品数。

    但是如果我们事先知道这些篮子本身在文件中就是随机放置的,那么我们就可以不用读入整个文件了,而是只接选择前面的pm个篮子作为样品就可以了。或者如果文件是分布式文件系统,我们可以选择第一个随机块作为样品。

    采样大小

    We choose some set of the baskets,not more than we'll fill perhaps half the main memory.
    支持度阈值

    我们使用篮子的一个子集并假装他们是整个数据集。我们必须调整支持度的阈值来适应我们的小篮子。例如,我们针对完整数据集的支持度阈值为s,当我们选择1%的样本时,我们可以在支持度阈值为s/100的度量上测试。

    当我们的样品选择完成,我们可以使用部分的主存来放置这些篮子。剩下的主存用来执行前面的Apriori、PCY、Multistage或Multihash算法。当然这些算法必须运行所有的样品,在每个频繁集上,直到找不到频繁集为止。这个方法在执行读取样品时不需要磁盘操作,因为它是驻留在内存的。当每个频繁项被发现,它们就可以写到磁盘上了。

    减少错误的随机采样算法

    抽样可能导致是频繁项的没有放进频繁集,也存在非频繁项的放入了频繁集。

    当样本足够大时,问题变得不是那么严重了;那些支持度远大于阈值的项集即使在样本中其支持度也会很高,所有误分的可能性不大。但是那些支持度在阈值附近的就不好说了。

    避免非频繁项集被判为频繁项集false positives

    简单的随机采样算法并不需要对完整的大数据集进行一次扫描,但是我们可以通过对整个数据集的一遍扫描,计算所有样品中频繁项集的支持度,保留那些在样品和在数据集上支持度都高于阈值的频繁项集,以此避免非频繁项集被判为频繁项集的错误。然而这种方法不能避免那些是频繁集却被当做非频繁项集的情况。

    减少频繁项集当做非频繁项集的数量false negatives

    但是我们可以减少那些是频繁项集却没有在样品中找出的数量如果内存的数量允许。我们设想如果s是支持阈值,且样品相对于整个数据集的大小为p,这样我们可以使用ps作为支持阈值。然而我们可以使用比这个值稍微小点的值作为阈值,如0.9ps。使用更低的阈值的好处是能使更多的项进入到频繁集中,这样就可以降低这种错误。The disadvantage of lowering the support threshold is that then you have to count more sets and there may not be enough main memory to do so.

    然后再到整个数据集中计算这些频繁项集的实际支持度(But then on the full pass you use the correct threshold s when counting from the entire set),除去那些非频繁项集,这样我们就可以消除非频繁项集当成频繁项集的错误,同时最大化的减少了频繁项集被当做了非频繁项集。

    皮皮blog



    SON算法(Savasere,Omiecinski, and Navathe; 基于划分的方法)

    {an improvement on the simple algorithm.SON方法能够对数据集上所有数据进行处理}

    SON算法同时避免了false negatives(频繁项集当做非频繁项集)和false positives(非频繁项集被判为频繁项集),所带来的代价是需要两个完全的步骤。

    SON基本思想

    将输入文件划分成1/p个块(chunks)。将每个文件块作为一个样本,并执行Apriori算法在其块上。同样的使用ps作为其阈值。将每个块找到的频繁项集放到磁盘上。

    第一步处理

    找到局部频繁项集:一旦所有的块按此方式被处理,将那些在一个或多个块中被选中的频繁项集收集起来作为候选频繁项集。注意,如果一个项集在所有的块中都不是频繁项集,即它在每个块中的支持度都低于ps。因为块数为1/p,所以,整体的支持度也就低于(1/p)ps=s。这样,每个频繁项集必然会出现在至少一个块的频繁项集中,于是,我们可以确定,真正的频繁项一定全在候选频繁项集中,因此这里没有false negatives。当我们读每个块并处理它们后,我们完成一次处理。


    第二步处理

    找到全局频繁项集:我们计算所有的候选频繁项集,选择那些支持度至少为s的作为频繁项集。


    分布式SON算法

    分布式算法步骤解析

    The idea is that you break the file containing the baskets into many groups,one at each processor.

    Each processor finds the local frequent item sets,then broadcast to each other processor its list of local frequent item sets.The union of all these lists is the candidate item sets.Now each processor knows the list of candidate itemvsets and counts them locally.

    Then, each processor broadcasts its counts to all the other processor.Now each processor knows the total count for each candidate set and can discover which of them are truly frequent.

    SON算法与Map-Reduce

    SON算法使得它很适合在并行计算的环境下发挥功效。每个块可以并行的处理,然后每个块的频繁集合并形成候选集。我们可以将候选分配到多个处理器上,在每个处理器上,这些处理器只需要在一个“购物篮”子集处理这些发过来的候选频繁项集,最后将这些候选集合并得到最终的在整个数据集上的支持度。这个过程不必应用map-reduce,但是,这种两步处理的过程可以表达成map-reduce的处理。

    map-reduce-map-reduce流程

    FirstMap Function:分配篮子子集,并在子集上使用Apriori算法找出每个项集的频繁度。将支持阈值降从s降低到ps,如果每个Map任务分得的部分占总文件的比例为p。map的输出为key-value对(F,1),这里F为该样本的频繁项集。值总是为1,这个值是无关紧要的。

    FirstReduce Function:每个reduce任务被分配为一组key,这组key实际就为项集,其中的value被忽略,reduce任务简单产生这些出现过一次或多次的项集,将其作为候选频繁项集作为输出。

    SecondMap Function:第二步的map任务将第一步的reduce的所有输出和输入文件的一部分作为输入,每个Map任务计算在分配的那块输入文件中每个候选频繁项集的出现次数。这步的输出为键值对(C,v),这里,C是一个候选集,v是其在该Map任务中的支持度。

    SecondReduce Function:此步的Reduce任务将在每个候选频繁项集各个Map中的候选集的支持度相加。相加的结果就为整个文件上的支持度,这些支持度若大于s,则保留在频繁项集中,否则剔除。

    皮皮blog



    Toivonen算法(随机抽样算法)

    {an entirely different approach to saving passes}

    Toivonen算法在给出足够内存的情况下,在小样本上进行一步处理,接着再整个数据上进行一步处理。这个算法不会带来false negatives,也不会带来false positives,但是这里存在一个小的概率使得算法会产生不了任何结构。这种情况下算法需要重复直至找到一个结果,虽然如此,得到最终频繁项集的处理的平均步数不会太大。

    小样本上扫描pass1:寻找候选频繁项集

    Toivonen算法由从输入数据集中选择一个小的样品开始,并从中找到候选频繁项集,找的过程同Apriori算法,不过很重要的一点不同是阈值的设置的比样品比例的阈值小。即,当整个数据集上的支持度阈值为s,该样品所占数据集的比例为p,则该阈值可以设置为0.9ps或0.8ps。越小的阈值,就意味着在处理样本时,越多的内存在计算频繁项集时需要使用;但是也就越大的可能性避免算法不能产生结果。

    构造负边界negative border

    Negative border:是样品的一个非频繁项集合,并且这些项集去掉任意一个项item后的直接子集是频繁集。

    构造Negative border示例

    考虑项为{A,B,C,D,E},而且我们找到频繁项集为{A},{B},{C},{D},{B,C},{C,D}。

    注意,只要篮子数不比阈值小,空集Φ也是频繁的,但是我们忽略它。The empty set is a subset of every basket, so the only way the empty set could not be frequent is if the support threshold is higher than the number of baskets.But that means nothing would be frequent and why are we bothering anyway.

    首先,{E}是在negative border中的,因为{E}本身不是频繁项集,但是从中去任意项后就变成Φ了,就成了频繁项集,所有包含在negative border中。

    {A,B},{A,C},{A,D}和{B,D}也在negative border中。因为它们都不是频繁项集,但是除掉一个项的子集都是频繁项集。如{A,B}的子集{A}和{B}都是频繁集。

    剩下的六个二元项集不在negative border中。{B,C}和{C,D}因为它们本身是频繁项集,所有就不是negative border的元素了,而其他四个虽然不是频繁项集,但是因为包含了项E,而子集{E}不是频繁项集。

    没有任何三元的或更大的项集在negative border中了。例如{B,C,D}不在negative border中,因为它有一个立即子集{B,D},而{B,D}不是频繁项集。

    这样,negative border由下面五个集合组成:{E},{A,B},{A,C},{A,D}和{B,D}。

    Negative border的作用及目的

    The purpose of counting the negative border is to act as canaries.None of them should be frequent in the whole data set because we picked the support threshold for the sample that is significantly below a proportional threshold.

    But if one or more of the items sets in the negative order turned out to be frequent in the hold,then we have to believe that the sample was not representative.And we need to repeat the entire process.

    Negative border图解


    Note:

    1. the vertical dimension is the size of item sets, and the horizontal dimension somehow represents all the item sets of a given size.

    2. The frequent item region is closed downwards because of monotonicity,a subset of the frequent item set is always frequent.

    3. The negative border may consist of sets of different sizes, and its items tend to have widely varying frequencies.
    大数据集上扫描pass2

    我们需要进一步在整个数据集上处理,算出所有在样品中的频繁项集或negative border中的所有项集的计数。

    这步会产生的可能输出为:

    1、  如果negative border中没有一个项集在整个数据集上计算为频繁项集。这种情况下,正确的频繁项集就为样本中的频繁项集。

    2、  某些在negative border中的项集在整个数据集中计算是频繁项集。这时,我们不能确定是否存在更大的项集,这个项集既不在样本的negative border中,也不在它的频繁项集中,但是是整个数据集的频繁项集。这样,我们在此次的抽样中得不到结果,算法只能在重新抽样,继续重复上面的步骤,直到出现满足输出情形1时停止。


    Note:如果negative border发现某个项集在整个数据集中是频繁的,那么它的super sets都可能是频繁项集,而被我们忽略了。这样的话就必须重新采样运行算法。

    尽量避免第2种情况发生的方法:Try to choose the support threshold so the probability of failure is low, while the number of itemsets checked on the second pass fits in main memory.

    Toivonen算法可行性分析

    显然 Toivonen算法不会产生false positive,因为它仅仅将在样本中是频繁项并在整个数据集上计算确实为频繁项集的项集作为频繁项集。

    讨论Toivonen算法能够不产生false negative

    如果一个项集在整个数据集上是频繁的,而在样本中不是频繁的,那么negative border中一定有一个成员是频繁的。(这样就要重新运行算法了)

    也就是说如果在negative border中没有成员在整个数据集中是频繁的,那么在整个数据集中再也不存在我们没有计数的频繁项了。if we find no members of the negative border to be frequent in the whole, then we know that there are no sets at all that are frequent in the whole but that we did not count.

    也就是说不存在一个项集在整个数据集上是频繁的,而在样本中既不出现在频繁集中,也不出现在negative border中。

    定理证明proof by contradiction

    Note:

    1. In principle, T could be S itself,if it has no proper subsets that are not frequent in the sample.All we care about is that all the subsets of T are frequent in the sample.

    2. I also claim that T is in the negative border.If it is not frequent in the sample, but it had a proper subset that was not frequent in the sample,then T would not be the smallest subset of S with that property.也就是S的比T更小的子集一定在样本频繁项集中,这样T就自然在样本的negative border上了。T就在样本的negative border上并且T是频繁的 与 2.Nothing ...矛盾!

    反例:

    假设这里有个集合S在数据集上是频繁项集,也不是样本的频繁项集。并且negative border中没有成员在整个数据集上是频繁的。

    假设T是S的一个在样本中不属于频繁项集的最小子集。

    由频繁项集的单调性知,S的所有子集都是整个数据集的频繁项集。则T是整个数据集的频繁项集。
    T一定在negative border中。因为T满足在negative border中的条件:它自己不是样本的频繁项集,而它的直接子集是样本的频繁项集,因为若它的直接子集不是,则T就不是S的在样本中不属于频繁项集的最小子集(这个直接子集才是)。
    于是我们发现T是整个数据集的频繁项集,又在样本的negative border中。与假设矛盾!

    皮皮blog



    其他的频集挖掘方法

    上面我们介绍的都是基于Apriori的频集方法。即使进行了优化,但是

    Apriori方法一些固有的缺陷无法克服

    可能产生大量的候选集。当长度为1的频集有10000个的时候,长度为2的候选集个数将会超过10M。还有就是如果要生成一个很长的规则的时候,要产生的中间元素也是巨大量的。

    无法对稀有信息进行分析。由于频集使用了参数minsup,所以就无法对小于minsup的事件进行分析;而如果将minsup设成一个很低的值,那么算法的效率就成了一个很难处理的问题。

    分别解决以上两个问题的两种方法:

    FP-树频集算法

    针对问题一,J.Han等在《数据挖掘概率与技术》中提出了不产生候选挖掘频繁项集的方法:FP-树频集算法。他们采用了分而治之的策略,在经过了第一次的扫描之后,把数据库中的频集压缩进一棵频繁模式树(FP-tree),同时依然保留其中的关联信息。随后我们再将FP-tree分化成一些条件库,每个库和一个长度为1的频集相关。然后再对这些条件库分别进行挖掘。当原始数据量很大的时候,也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明,FP-growth对不同长度的规则都有很好的适应性,同时在效率上较之apriori算法有巨大的提高。

    挖掘高可信度的规则

    第二个问题是基于这个的一个想法:apriori算法得出的关系都是频繁出现的,但是在实际的应用中,我们可能需要寻找一些高度相关的元素,即使这些元素不是频繁出现的。在apriori算法中,起决定作用的是支持度,而我们现在将把可信度放在第一位,挖掘一些具有非常高可信度的规则。Edith Cohen在"Finding Interesting Associations without Support Pruning"中介绍了对于这个问题的一个解决方法。

    整个算法基本上分成三个步骤:计算特征、生成候选集、过滤候选集。在三个步骤中,关键的地方就是在计算特征时Hash方法的使用。在考虑方法的时候,有几个衡量好坏的指数:时空效率、错误率和遗漏率。

    基本的方法有两类:Min_Hashing(MH)和Locality_Sensitive_Hashing(LSH)。

    Min_Hashing的基本想法是:将一条记录中的头k个为1的字段的位置作为一个Hash函数。Locality_Sentitive_Hashing的基本想法是:将整个数据库用一种基于概率的方法进行分类,使得相似的列在一起的可能性更大,不相似的列在一起的可能性较小。我们再对这两个方法比较一下。MH的遗漏率为零,错误率可以由k严格控制,但是时空效率相对的较差。LSH的遗漏率和错误率是无法同时降低的,但是它的时空效率却相对的好很多。所以应该视具体的情况而定。最后的实验数据也说明这种方法的确能产生一些有用的规则。

    Dic算法

    DIC 算法

    DIC算法实现(包括测试数据) 

    皮皮blog



    Reviews复习

    Toivonen算法

    Note: 频繁项集的子集也是频繁的,这样频繁项集还包含{D} 。但是不会包含{B, D}

    from:http://blog.csdn.net/pipisorry/article/details/48914067

    ref:


    展开全文
  • 所发现的联系可以用关联规则或频繁项集的形式表示。 例如,从表1中可以提取出:{尿布} ⟹ {啤酒}(该规则表明尿布和啤酒的销售之间存在着很强的联系)。 在对购物篮进行关联分析的时候,需要处理以下两个问题: ...

    关联规则及其基础:

    表1:购物篮例子的分析

     

    关联分析:用于发现隐藏在大型数据集中的有意义的联系。所发现的联系可以用关联规则或频繁项集的形式表示。

    例如,从表1中可以提取出:{尿布} ⟹ {啤酒}(该规则表明尿布和啤酒的销售之间存在着很强的联系)。

    在对购物篮进行关联分析的时候,需要处理以下两个问题:

          1、从大型事务数据集中发现模式可能在计算上要付出很高的代价;

          2、所发现的某些模式可能是虚假的,因为它们可能是偶然发生的。

     

    项集(itemset):包含0个或多个项的集合被称为项集;如果一个项集包含k个项,则称它为k项集。空集是指不包含任何项的项集。(例如,{啤酒,尿布,牛奶}是一个3项集)

    事务集:全体事务的集合T={t1,t2,…,tn },如2017.11.20日100人超市购物篮记录。其中每一个事务ti都是项的集合且具有一个相关的唯一标识符记为TID,如顾客001购买了{啤酒,尿布,面包}。

    频繁项集(Frequent Itemset):项集?的相对支持度满足预定义的最小支持度阈值。(一般来说,K项集可能产生 【2的k次方-1】个频繁项集,不包括空集在内)

    事务的宽度:事务中出现项的个数。如果项集X是事务 tj 的子集,则称事务 tj 包含项集X。

    支持度计数:包含特定项集的事务个数。

     

    关联规则:反映一个事物与其他事物之间的相互依存性和关联性。如果两个或多个事物之间存在一定的关联关系,那么,其中一个事物就能够通过其他事物预测到。

    关联规则形如 X ⟹ Y 的蕴涵表达式,其中X和Y是不相交的子集,即(X交Y = 空集)。

    关联规则的强度可以用它的支持度和置信度度量。

    支持度(suppot):确定规则可以用于给定数据集的频繁程度。

     

    置信度(confidence):确定Y在包含X的事务中出现的频繁程度。

     

    强规则:同时满足最小支持度阈值(minsup)和最小置信度阈值(minconf)的规则称为强规则。

    例如,考虑规则{牛奶,尿布} ⟹ {啤酒}。由于项集{牛奶,尿布,啤酒}的支持度计数是2,而事务的总数是5,所以规则的支持度为2/5 = 0.4;规则的置信度是项集{牛奶,尿布,啤酒}的支持度计数与项集{牛奶,尿布}支持度计数的商。由于存在3个事务同时包含牛奶和尿布,所以该规则的置信度为 2/3 = 0.67。

     

    为什么使用支持度和置信度?

    支持度是一种重要度量,因为支持度很低的规则可能只是偶然出现。从商务角度来看,低支持度的规则多半也是无意义的,因为对顾客很少同时购买的商品进行促销也是无意义的。因此,支持度通常用来删去哪些无意义的规则。此外,支持度还具有一种期望的性质,可以用于关联规则的有效发现。

    置信度通过规则进行推理具有可靠度,对于给定的规则 X ⟹ Y,置信度越高,Y包含在X的事务中出现的可能性就越大。置信度也可以估计Y在给定X下的条件概率。

    应当小心解释关联分析的结果。由关联规则作出的推论并不必然蕴涵因果关系。它只表示规则前件和后件中的项明显地同时出现。另一方面,因果关系需要关于数据中原因和结果属性的知识,并且通常涉及长期出现的关系(例如,臭氧损耗导致全球变暖)。

     

    规则剪枝:为了避免进行不必要的计算,事先对规则剪枝,而无需计算它们的支持度和置信度的值将是有益的。(因为规则 X ⟹ Y的支持度仅依赖于其对应项集 X ∪ Y的支持度)。例如,下面的规则具有相同的支持度,因为它们涉及的项都源自同一个项集{啤酒、尿布、牛奶}:

    {啤酒、尿布}⟹{牛奶},{啤酒、牛奶}⟹{尿布},

    {尿布、牛奶}⟹{啤酒},{啤酒}⟹{尿布、牛奶},

    {牛奶}⟹{尿布、啤酒},{尿布}⟹{啤酒、牛奶},

    如果项集{啤酒、尿布、牛奶}是非频繁的,则可以立即剪掉这6个候选规则,而不必计算它们的置信度值。

     

    Apriori算法:

    第一个关联规则挖掘算法,Agrawal和R.Srikant于1994年提出的,为布尔关联规则挖掘频繁项集的原创性算法。它使用一种称作逐层搜索的迭代算法,通过K项集用于搜索(K+1)项集。已经为大部分商业产品所使用。

    图1:Apriori算法

     

    步骤如下:

    1、首先,通过扫描数据集,产生一个大的候选数据项集,并计算每个候选数据项发生的次数,然后基于预先给定的最小支持度生成频繁1项集的集合,该集合记作L1;

    2、然后基于L1和数据集中的数据,产生频繁2项集L2;

    3、用同样的方法,直到生成频繁n项集,其中已不再可能生成满足最小支持度的(N+1)项集;

    4、最后,从大数据项集中导出规则。

     

    重要的特点:

    1、Apriori算法是一个逐层(level-wise)算法,即从频繁1项集到最长的频繁项集,它每次遍历项集格中的一层;

    2、Apriori算法使用产生-测试策略来发现频繁项集。在每次迭代之后,新的候选项集都由前一次迭代发现的频繁项集产生,然后对每个候选的支持度进行计数,并于最小支持度阈值进行比较。

     

    Apriori算法支持度先验性质

    先验原理:

    1、如果一个项集是频繁的,则它的所有子集一定也是频繁的;

    2、如果项集是非频繁的,则它的所有超集也一定是非频繁的。

     

    Apriori算法产生候选项集

    用图2表示上述性质,例子中有四个项目{A,B,C,D},格中的线表示子集关系,频繁项集的性质表明:

    如原来的项集是频繁的,则在路径中位于其上的任何集合也一定是频繁的。

    如其任意一个子集不是频繁的,则原来的项集也不是频繁的。

    图2

     

    Apriori算法置信度

    一条规则P➞H的可信度定义为support(P | H)/support(P),其中“|”表示P和H的并集,可信度的计算是基于项集的支持度的。

    要找到关联规则,我们首先从一个频繁项集开始。从上面的例子可以得到,如果有频繁项集{A,C},那么就可能有一条关联规则“A➞C”。这意味着如果有人购买了A,那么在统计上他会购买C的概率较大;注意这一条反过来并不总是成立,也就是说,置信度(“A➞C”)并不等于置信度(“C➞A”)。

    如果规则X->Y-X不满足置信度阈值,则形如X'->Y-X'的规则也一定不满足置信度阈值,其中X'是X的子集。

     

    Apriori算法产生关联规则

    图3给出了从项集{A,B,C,D}(假设该项集为频繁项集)产生的所有关联规则,其中蓝色线条指向的是低置信度的规则。可以发现如果{ABC}➞{D}是一条低置信度规则,那么所有其他箭头右部包含D的规则均为低置信度的。

    图3

     

    极大频繁项集和闭频繁项集

    极大频繁项集(Maximal Frequent Itemset):频繁项集X的所有真超项集都不是频繁的。

    图4

     

    如图4所示,位于边界上方的每个项集都是频繁的,而位于边界下方的项集(阴影结点)都是非频繁的。在边界附近的结点中,{a,d}、{a,c,e}和{b,c,d,e}都是极大频繁项集,因为它们的直接超集都是非频繁的。例如,项集{a,d}是极大频繁的,因为它的所有直接超集{a,b,d}、{a,c,d}和{a,d,e}都是非频繁的;相反,项集{a,c}不是极大的,因为它的一个直接超集{a,c,e}是频繁的。

    极大频繁项集有效地提供了频繁项集的紧凑表示;极大频繁项集形成了可以导出所有频繁项集的最小的项集的集合。

     

    闭频繁项集(Closed Frequent Itemset):

    闭项集(closed itemset):项集X的真超项集的支持度计数不等于它本身的支持度计数。

    Y是X的真超项集:X是Y的子集,但Y中至少有一个项不在X中(真超项集=直接超集=超集=真子集)。

    闭频繁项集(Closed Frequent Itemset):X在T中是闭的和频繁的。

    图5:闭频繁项集(最小支持度为40%)

     

    换句话说如至少存在一个X的直接超集,其支持度计数与X相同,X就不是闭的。

    如图5,格中每个结点(项集)都标出了与它相关联的事务的ID。由于结点{b,c}与事务ID{1,2,3}相关联,因为它的支持度计数为3.从图5中给定的事务可以看出,包含b的每个事务也包含c,因此,由于{b}和{b,c}的支持度是相同的,所以{b}不是闭项集。同样,由于c出现在所有包含a和d的事务中,所以项集{a,d}不是闭的。另一方面,{b,c}是闭项集,因为它的支持度计数与它的任何超集都不同。

    假设支持度阈值为40%,则项集{b,c}是闭频繁项集,因为它的支持度是60%。

     

    关联规则挖掘方法分类

    基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。

    布尔型关联规则:如果规则考虑的关联是项“在”或“不在”,则关联规则是布尔型的。例如,性别=“女”⟹职业=“秘书”。

    量化型关联规则:如果描述的是量化的项或属性之间的关联,则该规则是量化型的关联规则。

               例如,性别=“女”⟹avg(月收入)=2300。

     

    基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。

    单层的关联规则:所有的变量都不涉及不同抽象层次的项或属性。例如,buys(X, “computer”)  ⟹buys(X, “printer”),其中X为某顾客。

    多层的关联规则:变量涉及不同抽象层次的项或属性。例如:

                         age(X,“30…39”)⟹buys(X, “laptop computer”)

                         age(X,“30…39”)⟹buys(X, “computer”) 

     

    基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。

    单维关联规则:处理单个维中属性间的关系,即在单维的关联规则中,只涉及到数据的一个维。

              例如,用户购买的物品:“咖啡=>砂糖”,这条规则只涉及到用户的购买的物品。

    多维关联规则:处理多个维中属性之间的关系,即在多维的关联规则中,要处理的数据将会涉及多个维。

               例如,性别=“女”⟹职业=“秘书”,这条规则就涉及到两个维中字段的信息,是两个维上的一条关联规则。

     

    展开全文
  • 一般我们使用三个指标来度量一个关联规则,这三个指标分别是:支持度、置信度和提升度。 Support(支持度):表示同时包含A和B的事务占所有事务的比例。如果用P(A)表示使用A事务的比例,那么Support= Confidence...
  • 常见的挖掘频繁项集算法有两类,一类是Apriori算法,另一类是...FPGrowth不同于Apriori的“试探”策略,算法只需扫描原始数据两遍,通过FP-tree数据结构对原始数据进行压缩,效率较高。  FP代表频繁模式(Frequent P
  • 基于MapReduce的频繁项集挖掘方法

    千次阅读 2012-12-09 22:07:40
    云计算是分布式计算技术的一种,其最基本的概念是透过网络将庞大的...云计算具有超大规模、虚拟化、可靠性、高可扩展性、通用性等特点,在海量数据的处理中有着重要的地位和发展空间。云计算普遍采用的编程模
  • 基于Map/Reduce的频繁项集挖掘

    千次阅读 2013-03-07 22:13:56
    云计算具有超大规模、虚拟化、可靠性、高可扩展性、通用性等特点,在海量数据的处理中有着重要的地位和发展空间。云计算普遍采用的编程模式是MapReduce,它由Google提出,为编写需要大规模并行处理的代码提供了...
  • arules:频繁项集与关联规则的挖掘

    万次阅读 2015-05-24 21:45:56
    最大频繁项集的优势不仅在于它可生成所有的频繁项集,而且它们还包含了所有频繁项集支持度信息,这些信息在数据挖掘过程完成后,对计算额外的兴趣度量(interest measure)起着至关重要的作用(例如,计算所得项集...
  • 深度学习开源数据大全

    千次阅读 2019-01-01 19:48:11
    skymind.ai网站上有一份十分全面的开源数据,涵盖自然图像数据、面部数据等多个领域,为方面大家找到自己需要的数据,将skymind.ai整理的数据编译如下:     自然图像数据   MNIST: handwritten...
  • ​ 2、利用分类方法分类(支持向量机、决策树、随机森林、神经网络) ​ 缺点:这些特征提取方法需要依据先验知识手动设置,且通过设定参数提取的特征信息通常只能 ​ 用于...
  • 【积累】非常全面的开源数据

    万次阅读 2018-09-05 08:46:04
    非常全面的开源数据 由skymind.ai公布 非常全面的开源数据 最近新增数据 自然图像数据 地理空间数据 人工数据 人脸数据 视频数据 文本数据 问答数据 情感数据 推荐和排名系统 语音数据 ...
  • 机器学习——svm支持向量机的原理

    万次阅读 多人点赞 2016-05-07 14:26:22
    支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习方法,通过寻求结构化风险最小来提高学习机泛化能力,实现经验风险和置信范围的最小化,从而达到在统计样本量少的情况下,亦能获得良好统计...
  • android安卓源码海量项目合集打包-1

    万次阅读 多人点赞 2019-06-11 16:16:24
    │ │ 模仿微信联系人的字母索引ListView,拓展,维护。.zip │ │ 类似于联系人列表的那种选择国家和地区,点击右侧字母按字母查找对应的国家和地区(带有地区编码.rar │ │ 类似微信按照字母排列listview的...
  • 软件能力成熟模型(CMMI)

    万次阅读 2019-04-30 16:27:39
    转载自:... 本章内容提要CMMI概述CMMI的成熟等级及其过程域CMMI的应用PSP,TSP与CMMI第一节 CMMI概述CMMI( Capability Maturity Model Integration)即能力成熟模型集成,由CMM (Ca...
  • FreeRTOS 之三 全配置详解、裁剪(FreeRTOSConfig.h)

    万次阅读 多人点赞 2017-01-23 16:44:09
      模板中的配置还是挺多的,下面一一详细进行说明: 1. configUSE_PREEMPTION   为 1 时RTOS使用抢占式调度器,即当进程位于内核空间时,有一个更优先级的任务出现时,如果当前内核允许抢占,则可以将...
  • Image数据

    千次阅读 2019-11-23 15:36:18
    原文链接: ...一、行动数据库 20bn-Something-Something - 密集标记的视频剪辑,显示人类使用日常物品执行预定义的基本动作(Twenty Billion Neurons GmbH) 3D在线行动数据 - 有七个行动类别(微软和南...
  • 支持向量机(SVM)简介

    万次阅读 2017-10-24 10:25:29
    支持向量机(SVM)简介
  • 【导读】FAIR何恺明等人团队提出3D目标检测新框架VoteNet,直接处理原始数据,不依赖任何2D检测器。该模型设计简单,模型紧凑,效率,在两大真实3D扫描数据上实...
  • Redis是一款基于键值对的NoSQL数据库,它的值支持多种数据结构: 字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。 • Redis将所有的数据都存放在内存中,所以它的读写性能十分...
  • paviaU光谱数据降维与分类

    万次阅读 多人点赞 2018-08-12 16:30:31
    基于高光谱数据PaviaU的数据降维与分类 ...一方面高光谱图像相邻波段之间相关性较大,存在较高的信息冗余。另一方面,对高光谱图像蕴含的丰富的谱信息直接进行处理所需计算量巨大,高光谱图像中存在异物同谱及同谱...
  • 支持向量机(SVM)的分析及python实现

    万次阅读 多人点赞 2017-10-29 09:52:58
    2. 在原始的图中,红色的圆圈靠近x和y轴的原点,导致z和红色的圆圈相对低,而五角星从原点到z的值更。 在SVM中,在这两个类之间寻找一个线性的超平面是很容易的。但是,另一个问题是,我们是否应该手动添加这...
  • 随后来自哥伦比亚大学的Sal Stolfo 教授和来自北卡罗莱纳州立大学的 Wenke Lee 教授采用数据挖掘等技术对以上的数据进行特征分析和数据预处理,形成了一个新的数据。该数据用于1999年举行的KDD CUP竞赛中,...
  • 常用数据链接

    千次阅读 2019-05-19 10:57:16
    CVonline:图像数据库 ... 一般RGBD和深度数据 一般视频 手,掌握,手动和手势数据库 图像,视频和形状数据库检索 对象数据库 人(静),人体姿势 人员检测和跟踪数据库(另见监控) 遥感...
  • Chagas疾病数据(图8)再次显示,以Cohen’s kappa为最敏感的指标,DNN具有较好的训练和测试性能。 Chagas疾病数据(图8)再次显示,以Cohen’s kappa为最敏感的指标,DNN具有较好的训练和测试性能 结核病...
  • 38. 设X={1,2,3}是频繁项集,则可由X产生__(C)__个关联规则。 A、4 B、5 C、6 D、7 40. 概念分层图是__(B)__图。 A、无向无环 B、有向无环 C、有向有环 D...
  • 常用公共数据

    万次阅读 2018-01-05 19:21:18
    行动数据库属性识别自主驾驶生物/医药相机校准脸和眼/虹膜数据库指纹一般图像一般RGBD和深度数据一般视频手,掌握,手动和手势数据库图像,视频和形状数据库检索 对象数据库人(静),人体姿势人员检测和跟踪...
  • Michael Otey 和 Denielle Otey摘要Microsoft® SQL Server™ 2005 已经证明能满足客户的可用性要求,而且提供此功能的成本要比 Oracle 10g 低很多。SQL Server 2005 在 SQL Server 2005 Standard Edition 和 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 55,721
精华内容 22,288
关键字:

具有较高支持度的项集