数据挖掘第3章关联规则挖掘要点.ppt

（4）频繁序列挖掘 在映射后的序列数据库TN中挖掘出所有序列模式：首先得到候选频繁1-序列模式集CS1，扫描序列数据库TN，从CS1中删除支持度低于最小支持MinS的序列，得到频繁1-序列模式集FS1。 然后循环由频繁k-序列集FSk，生成候选频繁(k+1)-序列集CSk+1，再利用定理8-5对CSk+1进行剪枝，并从CSk+1中删除支持度低于最小支持度MinS的序列，得到频繁(k+1)-序列集FSk+1，直到FSk+1=?为止。 例题12 设有频繁3-序列集FS3={{1},{2},{3}, {1},{2},{4},{1},{3},{4},{1},{3},{5},{2},{3},{4}} 解：先利用频繁3-序列集FS3连接生成候选4-序列集，即 将序列{1},{2},{3}和{1},{2},{4}连接生成 {1},{2},{3},{4}和{1},{2},{4},{3}， 将序列{1},{3},{4}和{1},{3},{5}连接生成 {1},{3},{4},{5}和{1},{3},{5},{4} 因此，得到候选4-序列集CS4={{1},{2},{3},{4}，{1},{2},{4},{3}， {1},{3},{4},{5}，{1},{3},{5},{4}} 根据频繁序列的性质（定理3-5），对C4进行剪枝操作。 首先将4-序列{1},{2},{4},{3}从C4中删除，因为它存在一个3-序列{2},{4},{3}不在FS3之中，即它不会是频繁4-序列。 类似地可以将{1},{3},{4},{5}，{1},{3},{5},{4}从CS4中删除。 因此，得到最终的候选频繁4-序列集CS4={{1},{2},{3},{4}}。 例题13 设最小支持数为2，对于表8-16转换映射后的序列数据库TN挖掘出所有的序列模式。 解：在序列数据库的转换和映射过程中已得到频繁1-序列 FS1={ {l}，{2}，{3}，{4}，{5}}。 利用频繁1-序列集FS1生成候选频繁2-序列集 CS2={{1},{2},{2}, {1},{1},{3},{3},{1},{1},{4}, {4},{1},{1},{5},{5},{1},{2},{3},{3},{2},{2},{4}, {4},{2},{2},{5},{5},{2},{3},{4},{4},{3},{3},{5}, {5},{3},{4},{5},{5},{4}}。 共有20个候选频繁2-序列。 扫描序列数据库TN并对候选频繁2-序列计算支持数，如{1},{2}的支持数为2，{2}, {1}的支持数为0，{1},{5}支持数为3等，取支持数不低于2的序列组成频繁2-序列集 FS2={{1},{2}，{1},{3}，{1},{4}，{1},{5}，{2},{3}，{2},{4}，{2},{5}，{3},{4}，{3},{5}，{4},{5}} 对频繁2-序列集FS2进行自身连接并剪枝后得到候选3-序列集 CS3={{1},{2},{3}，{1},{2},{4}，{1},{2},{5}，{1},{3},{4}，{1},{3},{5}，{1},{4},{5}，{2},{3},{4}，{2},{3},{5}， {2},{4},{5}，{3},{4},{5}} 说明：频繁2-序列连接生成20个候选频繁3-序列，其中10个候选频繁3-序列被剪枝，如{1},{3},{2}被剪枝是因其子序列{3},{2}不是频繁2-序列。 对候选频繁3-序列集CS3中每个序列计算支持数，保留支持数不小于2的序列形成频繁3-序列集 FS3={{1},{2},{5}，{1},{3},{5}，{1},{4},{5}}。 由于FS3不能再产生候选频繁4-序列，故最后得到频繁序列模式集 FS=FS2?FS3={{1},{2}，{1},{3}，{1},{4}，{1},{5}，{2},{3}，{2},{4}，{2},{5}，{3},{4}，{3},{5}，{4},{5}， {1},{2},{5}，{1},{3},{5} } 根据需要，将FS中的序列模式转换为真实商品编号的序列模式。比如序列模式{1},{2}对应于{30},{40}， {1},{3},{5}对应于{30},{70},{90}，