西北农林科技大学算法实习.doc-资料库

6091e571-eb23-4927-9b44-cec9accd4446.doc.pdf-第1页.png

第1页 / 共15页

6091e571-eb23-4927-9b44-cec9accd4446.doc.pdf-第2页.png

第2页 / 共15页

6091e571-eb23-4927-9b44-cec9accd4446.doc.pdf-第3页.png

第3页 / 共15页

6091e571-eb23-4927-9b44-cec9accd4446.doc.pdf-第4页.png

第4页 / 共15页

6091e571-eb23-4927-9b44-cec9accd4446.doc.pdf-第5页.png

第5页 / 共15页

6091e571-eb23-4927-9b44-cec9accd4446.doc.pdf-第6页.png

第6页 / 共15页

6091e571-eb23-4927-9b44-cec9accd4446.doc.pdf-第7页.png

第7页 / 共15页

6091e571-eb23-4927-9b44-cec9accd4446.doc.pdf-第8页.png

第8页 / 共15页

附件二【学生用】西北农林科技大学信息工程学院算法实习报告题目：简单数据集频繁关闭模式挖掘算法设计与实现学姓号名 2015012936 吴翰专业班级软件 1502 指导教师实践日期张宏鸣 2017.1.7-2017.1.12

目录一、综合训练目的与要求......................................................................................................................1 二、综合训练任务..................................................................................................................................1 三、总体设计..........................................................................................................................................1 四、详细设计说明..................................................................................................................................3 五、调试与测试......................................................................................................................................6 六、实习日志..........................................................................................................................................9 七、实习总结........................................................................................................................................10 八、附录：核心代码清单....................................................................................................................10

一、综合训练目的与要求目的：通过此次实习，选择一道确定的题目练习本学期课程所学习的内容。我选择的题目是简单数据集频繁关闭模式挖掘算法算法设计与实现。频繁模式是指在数据集中，出现的次数大于等于给定阈值的项集。如下表所示的数据集，假设 2 。频繁模式： }{a ， }{b ， }{c , …….., ,{ }, mfca , 等对于模式 p ，如果不存在模式 'p , p  . 使得包含 p 的事物和包含 'p 的事务(TID)相同。那么 p 就 'p 是一个关闭频繁模式。目的是利用算法实现对上述的简单数据集的挖掘算的分析与实现。二、综合训练任务频繁模式是指在数据集中，出现的次数大于等于给定阈值的项集。如下表所示的数据集，假设 2 。频繁模式： }{a ， }{b ， }{c , …….., }, ,{ mfca , 等对于模式 p ，如果不存在模式 'p , p  . 使得包含 p 的事物和包含 'p 的事务(TID)相同。那么 p 就 'p 是一个关闭频繁模式。三、总体设计（1） Apriori 算法思想算法使用频繁项集性质的先验知识。Apriori 使用一种称作逐层搜索的迭代方法，k 项集用于探索（k+1）项集。首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁 1 项集的集合。该集合记作 L1.然后，L1 用于找频繁 2 项集的集合 L2，L2 用于找 L3，如此迭代，直到不能再找到频繁 k 项集。找每个 Lk 需要一次数据库全扫描。 Apriori 性质可用于压缩搜索空间，提高频繁项集逐层产生的效率。 Apriori 性质：频繁项集的所有非空子集也必是频繁的。 1

Apriori 算法主要包括连接步和剪枝步两步组成。在连接步和剪枝步中采用 Apriori 性质可以提高算法的效率。 1.连接步此步骤用于从频繁 k-1 项集集合产生候选 k 项集集合。为了计算出 Lk，根据 Apriori 性质，需要从 Lk-1 选择所有可连接的对连接产生候选 k 项集的集合，记作 Ck。假设项集中的项按字典序排序，则可连接的对是指两个频繁项集仅有最后一项不同。例如，若 Lk-1 的元素 l1 和 l2 是可连接的，则 l1 和 l2 两个项集的 k-1 个项中仅有最后一项不同，这个条件仅仅用于保证不产生重复。 2.剪枝步此步骤用于快速缩小 Ck 包含的项集数目。由 Apriori 性质可得，任何非频繁的（k-1）项集都不是频繁 k 项集的子集，因此，如果 Ck 中的一条候选 k 项集的任意一个（k-1）项子集不在 Lk-1 中，则这条候选 k 项集必定不是频繁的，从而可以从 Ck 中删除。这种子集测试可以使用当前所有频繁项集的散列树快速完成。 Ck 是 Lk 的超集，经过子集测试压缩 Ck 后，即可扫描数据库，确定 Ck 中每个候选的计数，从而确定 Lk。 (1)频繁模式树(Frequent Pattern tree)简称为 FP-tree，是满足下列条件的一个树结构：它由一个根节点(值为 null)、项前缀子树(作为子女)和一个频繁项头表组成。 (2)项前缀子树中的每个结点包括三个域：item_name、count 和 node_link，其中： item_name 记录结点表示的项的标识；count 记录到达该结点的子路径的事务数； node_link 用于连接树中相同标识的下一个结点，如果不存在相同标识下一个结点，则值为“null”。 (3)频繁项头表的表项包括一个频繁项标识域：item_name 和一个指向树中具有该项标识的第一个频繁项结点的头指针：head of node_link。对于包含在 FP-tree 中某个结点上的项α，将会有一个从根结点到达α的路径，该路径中不包含α 所在结点的部分路径称为α的前缀子路径(prefix subpath)，α称为该路径的后缀。在一个 FP-tree 中， 2

有可能有多个包含α的结点存在，它们从频繁项头表中的α项出发，通过项头表中的 head of node_link 和项前缀子树中的 node_link 连接在一起。FP-tree 中每个包含α的结点可以形成α的一个不同的前缀子路径，所有的这些路径组成α的条件模式基(conditional pattern base)。用α的条件模式基所构建的 FP-tree 称为α的条件模式树(conditional FP-tree)。 2. F-pGrwoth 算法输入：事务数据库 D 和最小支持度阈值 minσ。输出：D 所对应的 FP-tree。方法：FP-tree 是按以下步骤构造的： (1)扫描事务库 D，获得 D 中所包含的全部频繁项集 1F，及它们各自的支持度。对 1F 中的频繁项按其支持度降序排序得到 L。 (2)创建 FP-tree 的根结点 T，以“null”标记。再次扫描事务库。对于 D 中每个事务，将其中的频繁项选出并按 L 中的次序排序。设排序后的频繁项表为[p|P]，其中 p 是第一个频繁项，而 P 是剩余的频繁项。调用 insert_tree([p|P],T)。insert_tree([p|P],T)过程执行情况如下：如果 T 有子女 N 使 N .item_name=p.item_name，则 N 的计数增加 1；否则创建一个新结点 N，将其计数设置为 1，链接到它的父结点 T，并且通过 node_link 将其链接到具有相同 item_name 的结点。如果 P 非空，递归地调用 insert_tree(P，N)。FP-tree 是一个高度压缩的结构，它存储了用于挖掘频繁项集的全部信息。FP-tree 所占用的内存空间与树的深度和宽度成比例，树的深度一般是单个事务中所含项目数量的最大值；树的宽度是平均每层所含项目的数量。由于在事务处理中通常会存在着大量的共享频繁项，所以树的大小通常比原数据库小很多。频繁项集中的项以支持度降序排列，支持度越高的项与 FP-tree 的根距离越近，因此有更多的机会共享结点，这进一步保证了 FP-tree 的高度压缩。四、详细设计说明（1）Apriori 算法 Apriori 算法的基本思想是由 K 项频繁项集产生 K+1 项频繁项集，直到满足条件的频繁项集发现为止。 1.连接定理和频繁子集定理 3

连接定理：解决如何由 K 项集产生 K+1 项集问题。若有两个 K 项集，其前 K−1 个项是相同的，则这两个项集可以连接产生一个 K+1 项集。频繁子集定理：用来压缩搜索空间。若一个项集的子集不是频繁项集，则该项集也不是频繁项集。（换句话说，非频繁项集的超集也是非频繁项集；频繁项集的所有非空子集也都是频繁项集） ①② 2.Apriori 算法步骤 1. 扫描数据库，产生候选 1 项集和频繁项集。 2. 从 2 项集开始循环，由频繁 K-1 项集生成频繁 K 项集。 2.1 产生候选项集。根据连接定理，产生候选项集（有个排序的要求，加快比较）。 2.2 去掉非频繁项集。根据频繁子集定理产生频繁项集。 2.3 去掉不符合条件的项集。扫描数据库，计算支持度、置信度、兴趣度，去掉不符合条件的项集。（这地方可变） 2.4 判断迭代终止条件。 4

Database TDB C1 1st scan L1 请替换文字内容 C2 请替换文字内容 2nd scan L2 请替换文字内容 C3 3rd scan L3 Apriori 优缺点 Apriori 优点： C2 请替换文字 1）对大型数据库的处理能力，不需要将数库读入内存就可以完成频繁项集的挖掘。内容请替换文字内容 Apriori 缺点： 1）需要多次扫描数据库，效率低下。（2）.FP-Grwoth 算法输入：事务数据库 D 和最小支持度阈值 minσ。输出：D 所对应的 FP-tree。方法：FP-tree 是按以下步骤构造的： 5

(1)扫描事务库 D，获得 D 中所包含的全部频繁项集 1F，及它们各自的支持度。对 1F 中的频繁项按其支持度降序排序得到 L。 (2)创建 FP-tree 的根结点 T，以“null”标记。再次扫描事务库。对于 D 中每个事务，将其中的频繁项选出并按 L 中的次序排序。设排序后的频繁项表为[p|P]，其中 p 是第一个频繁项，而 P 是剩余的频繁项。调用 insert_tree([p|P],T)。insert_tree([p|P],T)过程执行情况如下：如果 T 有子女 N 使 N .item_name=p.item_name，则 N 的计数增加 1；否则创建一个新结点 N，将其计数设置为 1，链接到它的父结点 T，并且通过 node_link 将其链接到具有相同 item_name 的结点。如果 P 非空，递归地调用 insert_tree(P，N)。FP-tree 是一个高度压缩的结构，它存储了用于挖掘频繁项集的全部信息。FP-tree 所占用的内存空间与树的深度和宽度成比例，树的深度一般是单个事务中所含项目数量的最大值；树的宽度是平均每层所含项目的数量。由于在事务处理中通常会存在着大量的共享频繁项，所以树的大小通常比原数据库小很多。频繁项集中的项以支持度降序排列，支持度越高的项与 FP-tree 的根距离越近，因此有更多的机会共享结点，这进一步保证了 FP-tree 的高度压缩。五、调试与测试 Apriori 算法测试数据 6

资料库

西北农林科技大学算法实习.doc

相关推荐

课程资源

热门标签

最新资料