毕业论文数据挖掘中的关联规则和序列模式(编辑修改稿)

毕业论文数据挖掘中的关联规则和序列模式(编辑修改稿)内容摘要：

70，但仍然支持这个模式，因为 (40,70)是(40,60,70)的一个子集。 序列 (10,20) (30) 是一个不具备最小支持的 例子，它只被客户 2所支持。 而序列 (30)， (40) ， (70) ， (90) ， (30) (40) ， (30) (70) 以及 (40,70) 虽然具有 最小支持度(minimum support)，但并不是答案，因为它们不是 最大 (maximal)的。 最后我们得到图 _3 的结果。 Sequential Pattern with support 25% (30) (90) (30) (40,70) 图 c.) 实现算法的讨论 我们分五 个具体阶段来找出所有的序列模式。 分别是 ⅰ ）排序阶段， ⅱ ）大项集阶段 ⅲ ）转换阶段， ⅳ ）序列阶段，以及 ⅴ ）选最大阶段  涉及的术语 一个序列的 长度 (length)是它所包含的 项集 (itemset)的总数。 具有 k长度的序列称为 k序列。 有两个序列 x和 y， x∙y 表示 x和 y 经过连接运算形成的新的序列。 一个项集 i 的 支持 (support)是指那一部分在单次交易中买了项集 i 中的项的那一部分客户。 于是项集 i 和 1序列 i具有相同的 支持。 具有 最小支持 (minimum support)的项集称为 大项集 (large itemset or litemset)。 注意 ：大序列中的每一个项集都必须具有最小支持。 由此，任何大序列都是大项集的列表所组成。  步骤 数数 据据 挖挖 掘掘 中中 的的 关关 联联 规规 则则 和和 序序 列列 模模 式式 11 1) 排序阶段 (Sort Phase) 数据库（ D）以客户号 (customerid)为主键 (major key)，交易时间 (transactiontime)为次键 (minor key)进行排序。 实际上这个阶段将原来的事务数据库 (transaction database)转换成由客户序列组成的数据库。 2) 大项集阶段 (Litemset Phase) 在这个阶段我们找出所有大项集组成的集合 L。 我们也同步得到所有大 1序列组成的集合。 因为这个集合就是 {l | l L}。 大项集被映射成连续的整数。 在图 ，大项集分别是 (30)， (40)，(70)， (40， 70)和 (90)。 图。 Large Itemsets Mapped To (30) (40) (70) (40,70) (90) 1 2 3 4 5 图 这样映射的好处在于，将大项集按一个实体 (entity)的形式进行处理，可以带来比较和处理上的方便和高效，提供了一个统一的格式。 3) 转换阶段 (Transformation Phase) 在找序列模式的过程中，我们要不断地进行检测一个给定的大序列集合是否包含于一个客户序列中。 为了使这个过程尽量的快，我们用另一种形式来替换每一个客户序列。 在转换完成的客户序列中，每条交易 (transaction)被其所包含的所有大项集所取代。 如果一条交易不包含任何大项集，在转换完成的序列中它将不被保留。 而如果一个客户序列不包含任何的大项 集，在转换好的数据库中这个序列也将不复存在。 但是，在计算客户总数的时候，它仍将被计算在内。 现在，一个客户序列被一列由大项集组成的集合所取代，每个大项集的集合表示为 {l 1,l 2,… ,l n}， l i表示一个大项集。 这样的一个转换好的数据库被称为 D。 图 的图。 比如，在对 ID 号为 2 的客户序列进行转换的时候，交易（ 10，20）被剔除了，因为它并没有包含任何大项集；交易（ 40， 60， 70）则被大项集的集合{（ 40），（ 70），（ 40， 70） }代替。 Customer Id Original Customer Sequence Transformed Customer Sequence After Mapping 数数 据据 挖挖 掘掘 中中 的的 关关 联联 规规 则则 和和 序序 列列 模模 式式 12 1 2 3 4 5 (30)(90) (10,20)(30)(40,60,70) (30,50,70) (30)(40,70)(90) (90) {(30)}{(90)} {(30)}{(40),(70),(40,70)} {(30),(70)} {(30)}{(40),(70),(40,70)}{(90)} {(90)} {1}{5} {1}{2,3,4} {1,3} {1}{2,3,4}{5} {5} 图 4) 序列阶段 (Sequence Phase) 利用已知的大项集的集合来找到所需的序列。 在下一部分我们将讨论这个阶段的算法。 5) 选最大阶段 (Maximal Phase) 在大序列集中找出最大序列 (maximal sequences)。 在序列阶段找到所有的大序列之后，下述算法可以用来找出最大序列。 定义最长序列的长度为 n，则： for ( k = n。 k 1。 k ) do foreach ksequence sk do Delete from S all subsequences of sk 附图  序列阶段的算法讨论 序列阶段算法的基本结构是对数据进行多次遍历。 在每次遍历中，我们从一个由大序列 (large sequence)组成的种子集 (seed set)开始，利用这个种子集 ，可以产生新的潜在的大序列。 在遍历数据的过程中，我们计算出这些候选序列的支持度 (support)，这样在一次遍历的最后，我们就可以决定哪些候选序列是真正的大序列，这些序列构成下一次遍历的种子集。 在第一次遍历前，所有在大项集阶段得到的具有最小支持度 (minimum support)的大 1序列 (large 1sequence)组成了种子集。 这里提出两种算法，分别称为 countall 和 countsome。 countall 累计所有大序 列，包括非最大序 列 (nonmaximal sequence)，在找最大阶段 (maximal phase)，这些非最大序列必须被删除。 给出一个 countall 算法，称为 AprioriAll，给出一个 countsome 算法，称为 AprioriSome。 countsome 算法有一个 前推阶段 (forward phase)，这个阶段中我们找出具有一定长度的所有的大序列。 接下来是一个 回溯阶段 (backward phase)，我们找出所有剩余的大序列。  AprioriAll 算法 L1 = {large 1sequences}。 // 大项集阶段得到的结果 for(k = 2。 Lk1  。 k++) do 数数 据据 挖挖 掘掘 中中 的的 关关 联联 规规 则则 和和 序序 列列 模模 式式 13 begin Ck = New candidates generated from Lk1 // 见下附图 _2. foreach customersequence c in the database do Increment the count of all candidates in Ck that are contained in c. Lk = Candidates in Ck with minimum support. end Answer = Maximal Sequences in ∪ k Lk。 图 算法 注 ：所有算法表示中， Lk代表所有 k序列组成的集合， Ck 代表候选 k序列组成的集合。 图。 在每一次遍历 (pass)中，我们利用上一次遍历产生的大序列来产生候选序列，并在一次遍历中计算它们的支持度 (support)。 在遍历的最后，候选序列的支持度用来决定大序列 (剔除不足支持度的候选序列 )。 在第一次遍历时，大项集阶段的输出被用来初始化大 1序列的集合。  Apriori Candidate Generation(候选的产生 ) 函数 apriorigenerate 以 Lk1，所 有大 (k1)序列的集合为 输入参数。 该函数实现步骤如下： 第一步，联合 insert into Ck select ,… , from Lk1p,Lk1q where = ,… , =。 第二步，如果存在 c 的 (k1)子序列不包含于 Lk1 之中，则删除所有序列cCk。 附图 函数 Large 3Sequence Candidate 4Sequence (after join) Candidate 4Sequence (after pruning) 1 2 3 1 2 4 1 3 4 1 3 5 2 3 4 1 2 3 4 1 2 4 3 1 3 4 5 1 3 5 4 1 2 3 4 图 选序列的产生 在图 ，考察第一列中显示的 L3(the set of 3sequence)。 当它最为输入参数进入到 apriorigenerate 函数，在联合结束后，我们得到了第二列所示的结果，数数 据据 挖挖 掘掘 中中 的的 关关 联联 规规 则则 和和 序序 列列 模模 式式 14 进一步剔除那些子序列不在 L3 中的序列，第三列显示的序列将被保留。 比如，序列 1 2 4 3 由于它有一个子序列 2 4 3 不在 L3 中，所以被剔除了。  例子 {1 5}{2}{3}{4} {1}{3}{4}{3 5} {1}{2}{3}{4} {1}{3}{5} {4}{5} 图 考察图 ，在这里我们没有给出源数据库的形式。 客户序列已经以转换的形式出现了，每一条交易都被包含其中的大项集取代，大项集则由整数代替。 最小支持度定义为 40%(也就是至少两个客户序列 )。 对于数据的第一次遍历是在大项集阶段进行的。 图 1序列，第二次遍历，第三次遍历以及第四次遍历最后阶段所得到的大序列和它们的支持度。 L1 L2 L4 L3 图 1Sequences Support 1 4 2 2 3 4 4 4 5 4 2Sequences Support 1 2 2 1 3 4 1 4 3 1 5 3 2 3 2 2 4 2 3 4 3 3 5 2 4 5 2 3Sequences Support 1 2 3 2 1 2 4 2 1 3 4 3 1 3 5 2 2 3 4 2 4Sequences Support 1 2 3 4 2 数数 据据。