数据挖掘实例

Apriori算法：实例描述：以下是用户访问WEB日志的事务数，通过Apriori算法发掘其中的关联关系。(1)算法开始时，扫描事务数据库D,对组成每个事务的所有项进行累加计数，得到候选1_项集Ci，如表4-3所示。定义min_sup=2，删除支持计数小于2的项，可以得到频繁1一项集L1，如表4-4所示。(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所示。最后得到了频繁3一项集，由该频繁项集可以得到关联规则，并可对这些关联规则进行分析，得到事务数据集中相关事务间的信息。支持度：置信度：最后得到关联规则：PageRank算法实例描述：假设有4个网页，它们相互之间有链接，其结构如图所示，为每个网页赋予的初始PR都是1。有如下公式：PG（A）=（1-d）+d*（PR（T1）/C（T1）+....+PR（Tn）/C（Tn））其中，PR（A）是指网页A的PR，T1，T2，...，Tn是指网页A的链入网页PR（Ti）是网页Ti的PRC（Ti）是网页Ti的链出数量d是一个衰减因子，通常取值0.85。先看网页A，衰减因子之后的值是1*0.85=0.85。它有两个链出网页，因此分别传递给0.425给B和C。对于网页Ｂ和C，因为只有一个链出网页，它们分别传0.85给相应的网页，每个网页都有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之后又变化，所以需进一步计算。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，直到最后基本稳定。最大期望（EM）算法实例描述：一个关于翻译的问题。假设语料库为：Ilaugh我笑laughloudly大声地笑那么有英语词汇表}{I,laugh,loudly}以及中文词汇表{我，笑，大声地}最开始，我们并没有任何关于词汇间如何翻译的信息，那么：P(我|I）=1/3P(笑|I）=1/3P(大声地|I）=1/3P(我|laugh）=1/3P(笑|laugh）=1/3P(大声地|laugh）=1/3P(我|loudly）=1/3P(笑|loudly）=1/3P(大声地|loudly）=1/3对于Ilaugh我笑laughloudly大声地笑有2种对齐方式：顺序（I对应我，laugh对应笑），反序（I对应笑，laugh对应我）这样P(顺序，我笑|Ilaugh）=P(我|I）P(笑|laugh）=1/3*1/3=1/9P(反序，我笑|Ilaugh）=P(笑|I）P(我|laugh）=1/3*1/3=1/9规则化后，有：P(顺序，我笑|Ilaugh）=1/2网页A1网页B0.575网页C2.275网页D0.15P(反序，我笑|Ilaugh）=1/2同理，对于第二个句子对P(顺序，大声地笑|laughloudly）=1/2P(反序，大声地笑|laughloudly）=1/2现在重新计算词汇对译概率可得：P(我|I）=1/2P(笑|I）=1/2P(大声地|I）=0这个概率的得出步骤：考虑（我I）这一对，他出现在（Ilaugh我笑）的顺序对齐中，而其概率为1/2（其实称为权重更确切）(笑|I）出现在（Ilaugh我笑的）的反序对齐中，而其概率为1/2而(大声地|I）没有出现。所以，将上述步骤所得概率归一化后，可得：P(我|I）=1/2P(笑|I）=1/2P(大声地|I）=0P(我|laugh）=1/4P(笑|laugh）=1/2P(大声地|laugh）=1/4P(我|loudly）=0P(笑|loudly）=1/2P(大声地|loudly）=1/2再接着，重新计算各句对顺序反序概率P(顺序，我笑|Ilaugh）=P(我|I）P(笑|laugh）=1/2*1/2=1/4P(反序，我笑|Ilaugh）=P(笑|I）P(我|laugh）=1/2*1/4=1/8P(顺序，大声地笑|laughloudly）=1/8P(反序，大声地笑|laughloudly）=1/4归一后，P(顺序，我笑|Ilaugh）=2/3P(反序，我笑|Ilaugh）=1/3P(顺序，大声地笑|laughloudly）=1/3P(反序，大声地笑|laughloudly）=2/3也就是说，现在计算机相信，第一个句子对更倾向于顺序对齐，第二个句子对更倾向于反序对齐，这与我们的直觉相符合。最后将此过程反复迭代，得到正确结果。