Data Pattern，datapattern


    • What are patterns
    • Pattern Discovery
    • Computation
    • Uncover what Pattern

What are patterns?

Pattern Discovery

Pattern discovery: Uncovering patterns from massive data sets.
模式发现是数据挖掘中最基础的一项工作,后续的分析研究几乎都基于模式发现.

Computation

既然是要”挖掘”,就要有所标准来决定哪些是重点,哪些可以忽略.
要有所标准,就需要有计算,计算什么呢?
首先是数据集的子集的support,理解为在数据集中所占的权重就好了.
1. Absolute support, 绝对的support, 比如关于一个数据集,现在获取到的数据有十条记录,{banana}在其中出现了3次,那么3就是{banana}这个模式的absolute support,即它的count.
2. Relative support, 相对的support, 还是上面的例子,{banana}这个模式的relative support就是30%, 即它的比重,很容易理解吧?

其实在运用中用相对的比较多.
值得注意的是,这里的banana都是加了花括号的,为什么?因为我们研究的不是单一的元素,而是一个集合的子集,所以即使是单一元素的子集,也应该放在花括号中表示.

好的 ,继续. 知道了support之后, 而且回顾一下,pattern是频繁出现的子集,但如何来衡量频繁与否?
这个是相对的,需要定制一个界限,高于这个界限的就说它是frequent的!所以minsup(意思是minimum support, 注意它是用Relative support)的定义就出来啦.
a)比如再上面的例子中定义minsup=25%,那么就可以说{banana}在这个数据集中是frequent的,所以此时{banana}是这个数据集的一个pattern.
b)但如果我们把minsup定为40%,那么{banana}这个子集就不是frequent的了,那它也就不是这个数据集的一个pattern了.

最后再说一个计算相关的概念:Accosiation Rule[关联规则]可以参考ta
考察一些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出现了物品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相互之间是否有规律可循呢？
在数据库的知识发现中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的影响。
至于具体的计算,看下图:
关联规则

先解释一下transaction(事务),直观的,它对应图中表格的一行,每一行都是一个transaction.但是要注意了,关联规则研究的对象不是transaction,而是两个物品,事务中的物品,物品也就是数据集的一个元素,而事务就是数据集的一个子集啦!
对于物品X和Y,还是定个界限,不过这里不止一个了,我们关心的有两个,一个是集合{X,Y}出现的support,也就是这个集合在事物中出现的频率,还有一个是可信度confidence, c = sup({X,Y}) / sup(X),这个式子的意思应该很直观吧?很明显是XY一起出现占X出现的support的权重,在这个方面上可以表明X和Y的关联性.那为什么是除以sup(X)而不是除以sup(Y)呢?呵呵,因为定义的是X到Y的关联性(从概率论的条件概率的角度来看,可以看成在发生X的前提下出现Y的概率),就要看对于X,它们一起出现的权重,而不是看对于Y的.
定义一个minsup和一个minconf,如果同时满足对应地大于这两个值,那么就可以说X->Y是一个关联规则.

Uncover what Pattern?

很简单的举个例子,一个含有n个元素的集合,它的子集就有2n−1个,正如我们前面说到的,模式就是数据集的子集,那么有这么多的模式,我们应该研究那些呢?全部研究???不可能!!!也不科学!!!
首先应该明确一种想法,比如{1}包含在{1,2}中,那么如果这两个集合在某个角度来看是一致的,那么我们只需要取”大的”那一个集合就好了,在这里就是取{1, 2}.
那么从是否关心support的角度来看,可以有两种典型的pattern:
1. close pattern(封闭的模式): 在support相同的pattern(pattern的前提是frequent)中,取”最大”的那个(或那些)pattern.可以简单推导,close pattern是”无损的”,也就是所有的子集及其support信息都包含在所有的close patterns中.
2. max pattern(最大的模式):不关心support是否相同,只看所有”最大集”.最大化模式则是”有损的”, 因为它经过压缩后失去了support的信息,下面举例说明.
上面说得太抽象了,举个简单的例子, 比如对于事务们:{a}(s=20), {a, b}(s=10), {a, b, c}(s=10),{a, d}(s=20),这些transaction中:
max pattern是{a, b, c}和{a, d}为什么?因为{a}, {a, b}都是{a, b, c}的子集(注意是不看support的大小的).
close pattern是{a, b, c}(s=10)和{a, d}(s=20),注意这里是根据support来看的,这里只有两种support,s=10时,”最大集”是{a, b, c},那么就取{a, b, c},s=20时,”最大集”是{a, d}(因为{a, d}包含{a}),那么就取{a, d}.
关于有无损,很明显close pattern保留了原来的support信息,但是对于max pattern,你只知道{a, b, c}(s=10),但不知道它的子集{a}(s=20), {a, b}(s=10), 这下该清楚了吧?

相关内容