数据挖掘基本概念

[TOC]

Basic Concepts

基本概念 Frequent itemsets(patterns)

  • Itemset : 在表中 每一行就是一个itemset
  • k-itemset : 每一个itemset中有几个元素就叫几-itemset，例如图中第一行是3-itemset,第5行是5-itemset
  • （absolute)support(count) of X : 对beer来说， 在表中，how many times beer happens? 答案是3，所以support(beer) = 3;
  • (relative) support,s : 图中总共有5个transactions，3个含有beer，所以 relative support of beer is 3/5;
  • frequent itemset : 如果item set X的support不小于一个minsup threshold （最小支持阈值），X 就是一个frequent support;

关联规则

  • 关联规则 : X->Y(s,c)
    关联规则就是说，如果客户买了X，那么客户也购买了Y的support 和confidence是什么

    • support，s ：一笔交易同时包含X和Y的概率
    • confidence,c: 一笔交易同时包含X和Y的条件概率

  • 关联规则挖掘 ：找到所有满足最小support和confidence的规则X->Y;

  • 关联规则
    • let minsup = 50%
    • Beer->Diaper (support(beer)/total,support(beer,diaper)/support(diaper))
    • diaper->beer (support(diaper)/total,support(beer,diaper)/support(beer))

问题：这是所有的满足minsup = 50%的规则吗？
答案是否定的！
我们可以注意到后面两行中 {nuts,eggs} {eggs,milk} 都出现了；

  • support(nuts,eggs) = 2; support(eggs,milk) = 2;
  • support(nuts) = 3; support(eggs) = 3; support(milk) = 2;
  • nuts->eggs(40%,60%)
  • eggs->nuts(40%,60%)
  • milk->eggs(40%,60%)
  • eggs->milk(40%,100%)

##compressed representation: closed patternsand max-patterns

3

如果我们用frequent pattern的话，我们会遇到一个挑战，那就是有太多太多的frequent pattern了。
比如说：

  • 一个长的pattern里面包含了组合数级别的子pattern

  • 假如我们有一个transaction database: $\mathbb{tdb_1}$:
    $t_1$:{$a1$,…,$a{50}$} ; $t_2$:{$a1$,…,$a{100}$}

    • 假设 absolute(就是count) minsup = 1 就是说every thing is frequent
    • 那么 1-itemsets 有100个
    • 2-itemsets 有$c^2{50}$+$c^2{100}$个
    • …..
    • 最终，总共有 $c^1{100}+c^2{100}+….+c^100_{100} = 2^{100}-1$ 个子模式！！！天啊，这也太多了！

所以我们需要一个简洁紧凑的表示方法

4
第一种解决办法是：

Closed patterns : 只有一个pattern 既frequent，并且不存在一个包含了这个pattern且和这个pattern 有相同的support 的父pattern,才是一个Closed Pattern

继续以上面的transaction database: $tdb_1$: $t_1$:{$a1$,…,$a{50}$} ; $t_2$:{$a1$,…,$a{100}$}为例：
假设minsupport(absolute) = 1,那么有多少个Closed Pattern?
答案是2个：

  • “$p_1$:{$a1$,…,$a{50}$}:support=2“
  • “$p_2$:{$a1$,…,$a{100}$}:support=1“;

因为 {$a1$,…,$a{51}$}虽然多了一个$a_{51}$,但是它的support=1，小于2，所以找不出一个super-pattern和$p_1$的 support相同；所以$p_1$是一个Closed Pattern;$p_2$证明相同；

那么这样表示的好处是什么呢？

我们注意到，对于$p_1$的 sub-pattern {$a1$,…,$a{49}$} 来说，它的support也是2， 对于$p_2$的 sub-pattern {$a1$,…,$a{99}$} 来说，它的support也是1。所以closed pattern包含了它的所有sub-pattern的support信息，我们用这种紧凑简洁的表示方法并没有损失任何信息。
用closed pattern可以用2个pattern表示原来$2^{100}$-1个pattern可以表示的信息。这就是这种表示法的好处。

我们再看看另一个表示方法叫做:Compressed Pattern
5

Comments

⬆︎TOP