当前位置:文档之家› 数据挖掘实例

数据挖掘实例

(2)为发现频繁2一项集集合1, 2,算法使用 生成候选2一项集集合C2,
(3)扫面事务数据库D,计算C2中每一个候选项集的支持度,将支持度小于2的候选2一项集删除,将得到频繁2一项集L2,如表4-6所示。
(3)使用频繁2一项集Lz来求候选3一项集,从连接步开始,首先令C3={{ABC}, {ABE}, fABF}, FACE}, fACF}, {AEF}}。由Apriori反单调性质,即频繁项集子项集也是频繁集的,即任何一个k一项集,只要它其中的任何一个(k-1)一项子集不属于频繁-项集,则说明这个k一项集也不是频繁的。所以,根据Apriori算法的剪枝步操作就不需要再把这条k一项集选到候选项集k一项集中。例如:由上面我们得到的ACF项集,有三个子集:AC,AF,CF。其中CF不属于L2中的频繁2一项集,所以通过剪枝步ACF就不是候选3一项集里的项。根据该方法,可以确定5个候选不可能是频繁的,因此,把它们从C3中删除,得到如表4-7所示的候选3一项集。然后,扫描事务数据库D计算C3中每个项的候选计数,得到频繁3一项集L},如表4-8所示。
再接着,重新计算各句对顺序反序概率
P(顺序,我笑|I laugh)=P(我|I)P(笑|laugh)=1/2*1/2=1/4
P(反序,我笑|I laugh)=P(笑|I)P(我|laugh)=1/2*1/4=1/8
P(顺序,大声地笑| laugh loudly)=1/8
P(反序,大声地笑| laugh loudly)=1/4
这样
P(顺序,我笑|I laugh)=P(我|I)P(笑|laugh)=1/3*1/3=1/9
P(反序,我笑|I laugh)=P(笑|I)P(我|laugh)=1/3*1/3=1/9
规则化后,有:
P(顺序,我笑|I laugh)=1/2
P(反序,我笑|I laugh)=1/2
同理,对于第二个句子对
P(我|laugh)=1/3 P(笑|laugh)=1/3 P(大声地|laugh)=1/3
P(我|loudly)=1/3 P(笑|loudly)=1/3 P(大声地|loudly)=1/3
对于
I laugh我笑
laugh loudly大声地笑
有2种对齐方式:顺序(I对应我,laugh对应笑),反序(I对应笑,laugh对应我)
最后得到了频繁3一项集,由该频繁项集可以得到关联规则,并可对这些关联规则进行分析,得到事务数据集中相关事务间的信息。
支持度:
置信度:
最后得到关联规则:
PageRank算法
实例描述:假设有4个网页,它们相互之间有链接,其结构如图所示,为每个网页赋予的初始PR都是1。有如下公式:
PG(A)=(1-d)+d*(PR(T1)/C(T1)+....+PR(Tn)/C(Tn))
(笑|I)出现在(I laugh我笑的)的反序对齐中,而其概率为1/2
而(大声地|I)没有出现。
所以,将上述步骤所得概率归一化后,
可得:
P(我|I)=1/2 P(笑|I)=1/2 P(大声地|I)=0
P(我|laugh)=1/4 P(笑|laugh)=1/2 P(大声地|laugh)=1/4
P(我|loudly)=0 P(笑|loudly)=1/2 P(大声地|loudly)=1/2
最后将此过程反复迭代,得到正确结果。
其中,PR(A)是指网页A的PR,
T1,T2,...,Tn是指网页A的链入网页
PR(Ti)是网页Ti的PR
C(Ti)是网页Ti的链出数量
d是一个衰减因子,通常取值0.85。
先看网页A,衰减因子之后的值是1*0.85=0.85。它有两个链出网页,因此分别传递给0.425给B和C。对于网页B和C,因为只有一个链出网页,它们分别传0.85给相应的网页,
最大期望(EM)算法
实例描述:一个关于翻译的问题。
假设语料库为:
I laugh我笑
laugh loudly大声地笑
那么有英语词汇表}{I,laugh,loudly}
以及中文词汇表{我,笑,大声地}
最开始,我们并没有任何关于词汇间如何翻译的信息,
那么:
P(我|I)=1/3 P(笑|I)=1/3 P(大声地|I)=1/3
PR(A)=0.15+0.85*(2.275/1)=2.08375;
PR(B)=0.15+0.85*(1/2)=0.575;
PR(C)=0.15+0.85*(1/2+0.575/1+0.15/1)=2.275;
PR(D)=0.15;
第二次计算后,A的PR变成最高的了。随着计算的进行,网页之间不断传递PR,直到最后基本稳定。
P(顺序,大声地笑| laugh loudly)=1/2
P(反序,大声地笑| laugh loudly)=1/2
现在重新计算词汇对译概率
可得:
P(我|I)=1/2 P(笑|I)=1/2 P(大声地|I)=0
这个概率的得出步骤:
考虑(我I)这一对,他出现在(I laugh我笑)的顺序对齐中,而其概率为1/2(其实称为权重更确切)
归一后,
P(顺序,我笑|I laugh)=2/3
P(反序,我笑Biblioteka I laugh)=1/3P(顺序,大声地笑| laugh loudly)=1/3
P(反序,大声地笑| laugh loudly)=2/3
也就是说,现在计算机相信,第一个句子对更倾向于顺序对齐,第二个句子对更倾向于反序对齐,这与我们的直觉相符合。
Apriori算法:
实例描述:
以下是用户访问WEB日志的事务数,通过Apriori算法发掘其中的关联关系。
(1)算法开始时,扫描事务数据库D,对组成每个事务的所有项进行累加计数,得到候选1_项集Ci,如表4-3所示。定义min_sup=2,删除支持计数小于2的项,可以得到频繁1一项集L1,如表4-4所示。
每个网页都有0.15没有传递给任何其他网页,因此计算结果为:
PR(A)=0.15+0.85*(1/1)=1;
PR(B)=0.15+0.85*(1/2)=0.575;
PR(C)=0.15+0.85*(1/2+1/1+1/1)=2.275;
PR(D)=0.15
第一次计算显示了网页C的重要性,但是并没有结束,因为C在计算A之后又变化,所以需进一步计算。
相关主题