数据挖掘导论第7章.ppt

关联分析: 高级概念
第7章
关联分析: 高级概念
关联分析处理事务数据
Rules Discovered:
{Diaper} --> {Beer}
处理分类属性
我们可能发现关于因特网用户特征的有趣信息下层的项（如：AC适配器）可能没有足够的支持度，但是，作为概念分层结构中它们的父母结点（如：便携机配件）具有较高支持度。
（2）在较低层发现的规则倾向于过于特殊，可能不如较高层的规则令人感兴趣。（如：脱脂牛奶普通面包，脱脂牛奶白面包，等过于特殊）
实现概念分层的方法
每个事务t用它的扩展事务t’取代，其中，t’包含t中所有项和它们的对应祖先。如：事务{DVD，普通面包}可以扩展为{DVD，普通面包，家电，电子产品，面包，食品}
然后对扩展的数据库使用如Apriori等已有的算法来发现跨越多个概念层的规则。
概念分层主要缺点
（1）处于较高层的项比处于较低层的项趋向于具有较高的支持度计数。
（2）概念分层的引入增加了关联分析的计算时间。
（3）概念分层的引入可能产生冗余规则。规则X Y是冗余的，如果存在一个更一般的规则X’ Y’，其中X‘是X的祖先，Y’是Y的祖先，并且两个规则具有非常相似的置信度。例如：{面包} {牛奶}，{白面包} {脱脂牛奶}
序列模式
购物篮数据常常包含关于商品何时被顾客购买的时间信息。可以使用这种信息，将顾客在一段时间内的购物拼接成事务序列。
然而，迄今为止所讨论的关联模式概念都只强调同时出现关系，而忽略数据中的序列信息。
对于识别动态系统的重现特征，或预测特定事件的未来发生，序列信息可能是非常有价值的。
序列模式
将与对象A有关的所有事件按时间增序排列，就得到A的一个序列（sequence）
Object
Timestamp
Events
A
10
2, 3, 5
A
20
6, 1
A
23
1
B
11
4, 5, 6
B
17
2
B
21
7, 8, 1, 2
B
28
1, 6
C
14
1, 8, 7
Sequence Database:
一般地，序列是元素（element）的有序列表，可以记作s=<e1e2e3,…,en>, 其中每个ej是一个或多个事件的集族，即ej={i1，i2，…，ik}。
Sequence
E1E2
E1E3
E2
E3E4
E2
Element (Transaction)
Event (Item)
序列数据的例子
子序列（ Subsequence）
序列t是另一个序列s的子序列（subsequence），如果t中每个有序元素都是s中一个有序元素的子集。
Data sequence
Subsequence
Contain?
< {2,4} {3,5,6} {8} >
< {2} {3,5} >
Yes
< {1,2} {3,4} >
< {1} {2} >
No
< {2,4} {2,4} {2,5} >
< {2} {4} >
Yes
序列模式发现（Sequential Pattern Mining）
设D是包含一个或多个数据序列的数据集:
序列s的支持度是包含s的所有数据序列所占的比例。如果序列s的支持度大于或等于用户指定的阈值minsup，则称s是一个序列模式（或频繁序列）。
序列模式发现:
给定序列数据库D和用户指定的最小支持度阈值minsup，序列模式发现的任务是找出支持度大于或等于minsup的所有序列 。
例子
Minsup = 50%
Examples of Frequent
Subsequences:
< {1,2} > s=60%
< {2,3} > s=60%
< {2,4}> s=80%
< {3} {5}> s=80%
< {1} {2} > s=80%
< {2} {2} > s=60%
< {1} {2,3} > s=60%
< {2} {2,3} > s=60%
< {1,2} {2,3} > s=60%
提取序列模式：蛮力方法
给定n个事件的集族: i1, i2, i3, …, in
候选 1-序列:
<{i1}>, <{i2}>, <{i3}>, …, <{in}>
候选 2-序列:
<{i1, i2}>, <{i1, i3}>, …, <{in-1} {in}>, <{i1} {i1}>, <{i1} {i2}>, …, <{in-1} {in}>
候选 3-序列:
<{i1, i2 , i3}>, <{i