数据课设报告.doc

数据挖掘概念与技术数据挖掘概念与技术 课程设计课程设计 AprioriApriori 算法的改进研究算法的改进研究 编写人 王肖程 学号 111001114 班级 111001 日期 2014 年 6 月 26 日 引言 数据挖掘 Data Mining 就是从大量的 不完全的 有 噪声的 模糊的 随机的实际应用数据中 提取隐含在其中的 人们事先不知道的 是潜在有用的信息和知识的过程 数据挖掘算 法有决策树算法 分类算法 聚类分析算法 关联算法等 其 中 随着数据量的逐年增加和人们对各个数据项之间关系的关注 关联规则挖掘在数据挖掘中占有了重要的地位 也是数据挖掘的主 要任务之一 关联规则是由 R Agrawal 等人于 1993 年提出的 是数 据挖掘问题中的一个重要研究内容 它最典型的应用是在销售事务数 据库中发现新的有用信息 例如 85 的顾客在购买商品 A 和 B 的同 时也购买商品 C 和 D 找出所有的类似规则 对于确定销售策略是很 有帮助的 由于数据库通常是相当庞大的 因此需要高效的算法来 挖掘关联规则 Apriori 算法是最经典的挖掘关联规则的算法 1 1 AprioriApriori 算法的基本原理算法的基本原理 Apriori 是最有影响的挖掘布尔关联规则频繁项目集的经典算法 在 Apriori 算法中 通过遍历数据库得到大一项集 L1 如果 L1 非空 由 L1 产生长度为 2 的候选项集合 C2 然后对事务数据库中的每一个事 务 t 求出 t 在 C2 中的全部子集 Ct 对于 Ct 中的每一个长度为 2 的 候选项集 c 令 c 的计数加 1 当扫描事务数据库一遍后 筛选出候选 项集合 C2 中所有计数满足最小支持度的项集组成了长度为 2 的频繁 项集合 用以上步骤重复处理新得到的频繁项集合 直到没有频繁项 集合产生 其中候选项集产生的过程被分为连接与剪技两个部分 采用这种方式 使得所有的频繁项集既不会遗漏又不会重复 2 2 AprioriApriori 算法的缺陷算法的缺陷 1 如果在生成候选频繁项目集之前能判断某些候选频繁项目集 是非频繁项目集 则可以不生成这些能事先判断出的非频繁项目集 这样既可避免连接生成这些候选频繁项目集的时 间开销 又可避免在扫描数据库时的时间开销 2 连接程序中相同的项目重复比较太多 如果能避免这些重复 的比较 则可提高算法的效率 3 在每次生成候选频繁项目集后 又要回去扫描数据库来判断 这些候选频繁项目集是否是频繁项目集 在扫描数据库的过程中 有 些可以判断出不必再去扫描的项目或事务被多次扫描 如果能避免这 些不必要的扫描 则可以提高 Apriori 算法的效率 3 3 相关性质相关性质 性质 1 任何频繁项集的所有非空子集是频繁项集 非频繁项集 的超集是非频繁项集 性质 2 如果频繁 k 项集还能产生频繁 k 1 项集 则频繁 k 项集 中的项集的个数必大于 k 性质 3 支持频繁项集 Lk 的任意一条事务至少支持 Lk 1 中的 k 个 k 1 项集 4 4 AprioriApriori 改进改进 4 14 1 AprioriApriori 算法的进一步分析算法的进一步分析 设 Tmax 表示最大交易长度 N 表示事务数据库的交易数 则第一遍 数据库扫描时间为 O N Tmax 在每一步中 连接时间开销是 O Lk 1 Lk 1 剪枝时间是 O Ck 扫描计数时间是 O N Ck 由此可见 Apriori 算法的时间开销主要集中在频繁 k 项目集的生成以及候选频繁项目集 Ck 的计数过程中 因此 减少连 接次数以及扫描数据库的次数从而减少数据库扫描时间 在此过程中 同时进行事务压缩和项目压缩 即在生成候选项目集 Ck 的同时 剔除 事务数据库中的不支持 Lk 的事务 以及事务中的项目 同时在进行连 接操作时 可以优化连接策略 则算法的性能会有所提高 这是本文提 出的改进方法的基本出发点 4 24 2 优化思想优化思想 基于上述提到的三个性质 可以采用如下通过事务压缩而进行库优 化的策略 将数据库读入一个二维数组 A 其中数组的每一行只 存储一条事务记录 且每一行的第 0 个元素存储为一个标志位 M 0 或 者 1 M 0 是表示该行需要扫描 当 M 1 时 表示该行不需要再扫描了 主要基于如下 2 点 1 对已知规模的数据库 任意 k 项集的支持度与规模小于 k 的事务 无关 因此可删除规模小于 k 的事务 2 当一个事务不包含长度为 k 的频繁项集 则必然不包含长度为 k 1 的频繁项集 10 因此可以在生成 k 1 频繁项集之前先删除这 样的事务 以减少下次扫描数组的时间 Apriori 算法需要大量进行的 2 个操作是 2 个 k 项集前 k 1 项是否相同 2 个 k 项集最后一项是否不同 连接操作占了程序 运行的大部分时间 如果能减少连接执行的次数 就可以提高 Apriori 算法的运行效率 Apriori 算法中各交易记录中各项均是己 经按字典排序的 所以由 Apriori 算法可以得出生成的候选项集也是 有序的 并且等式的任意 2 个候选项集之间对位比较也是有序的 对 于生 成的频繁项集也是如此 因此在实现 Apriori 算法时可以利用项集之 间有序的特点来减少上述 2 个操作的次数 从而提高算法的运行效率 利用以上的性质 下面给出连接步骤的优化思想如下 对于 2 个 k 1 项频繁集 lx 和 ly 若 lx 不能和 ly 连接 则 lx 与 ly 之后的 所有 k 1 项集都不能满足连接条件 所以只要 lx 与 ly 不能连接 就 不需要再判断 lx 与 ly 之后的所有 k l 项集是否能连接 空间 算法 1 Create Ck for eachlxLk 1 for eachlyLk 1 if lx 1 ly 1 Clx 2 ly 2 C lx k 2 ly k 2 Clx k 1 ly k 1 c lxGly 将 2 个项集连接到一起 Ck cGCk else break ly 后面的项集都不能与 lx 合 并 returnCk 返回连接生成的项集 很显然 这样会明显减少连接比较次数 同时也避免了多个无用候 选项目集的产生 算法 2 1 for u 0 u n u A u 0 0 将二维数组的每行 的首个元素即标志位设置为 0 2 L1 find frequent 1 itemsets A u v minsupport for 每个事务 tIA do ifTi Length 1 thenA i 0 1 标志位设置为 1 下 次不再扫描该行 3 Create Ck Lk 1 调用算法 1 求出 Ck 4 for 每个事务 TiIA u v do if Ti Length minsupport Answer GkLk 下面结合一个例子来描述算法的流程 将改进的 Apriori 算法与 经典 Apriori 算法在扫描数据库规模以及连接策略上进行比较 这里 不考虑改进 Apriori 算法一次性将数据库读入内存的因素 事务数 据库如表 1 所示 设定最小支持度为 25 对于表中 8 个事务 则最小 支持事务数为 2 个事务 表 1 算法执行流程如下 1 读取数据库 将数据库存入二维数组 如表 2 所示 2 扫描数组 求出 L1 I1 I2 I3 I4 I5 I6 并且置 T6 标志位 M 为 1 如表 3 所示 下次不再扫描之 注 由于篇幅原因 以下步骤 中 M 标志位变化时不再给出新表 3 L2 I1 I2 I1 I3 I2 I3 I2 I4 I2 I5 I3 I5 I4 I 5 I5 I6 表 3 4 34 3 代码实现代码实现 int SizeStr char m int i 0 while m i 0 i return i bool OpD char x char y int i 0 if SizeStr x SizeStr y while x i y i i if x i 0 return false void LoadItemL1 char p int i j n 0 k 0 char ch char s int f memset cur 0 sizeof cur for i 0 i 20 i curL1 i 0 0 curL1 i 1 0 for j 0 j 10 j countL1 j 0 for i 0 i 10 i for j 0 j 4 j ch p i j if ch 0 break cur n 0 ch n curL1 0 0 cur 0 0 curL1 0 1 cur 0 1 k 0 for i 0 i 50 i if cur i 0 break s cur i f 1 for j 0 j k j if OpD s curL1 j f 0 break if f 1 k curL1 k 0 cur i 0 curL1 k 1 cur i 1 for i 0 i 20 i for j 0 j 50 j char m m curL1 i if m 0 break if OpD m cur j countL1 i printf L1 n printf 项集 支持度计数 n for i 0 i 2 printf I s d n curL1 i countL1 i void LoadItemL2 char p int k i j char s int f SubItem2 p curL2 0 0 cur 0 0 curL2 0 1 cur 0 1 curL2 0 2 cur 0 2 k 0 for i 0 i 50 i if cur i 0 break s cur i f 1 for j 0 j k j if OpD s curL2 j f 0 break if f 1 k curL2 k 0 cur i 0 curL2 k 1 cur i 1 curL2 k 2 cur i 2 for i 0 i 20 i for j 0 j 50 j s curL2 i if s 0 break if OpD s cur j countL2 i printf L2 n printf 项集 支持度计数 n for i 0 i 2 printf I c I c d n curL2 i 0 curL2 i 1 countL2 i void SubItem3 char p char s int i j h m int n 0 memset cur 0 sizeof cur for j 0 j 20 j curL3 j 0 0 urL3 j 1 0 curL3 j 2 0 curL3 j 3 0 for i 0 i 10 i countL3 i 0 for m 0 m 10 m s p m if SizeStr s 3 continue for i 0 i SizeStr s i for j i 1 j SizeStr s j for h j 1 h SizeStr s h if s h 0 break cur n 0 s i cur n 1 s j cur n 2 s h cur n 3 0 n void LoadItemL3 char p int k i j char s int f SubItem3 p curL3 0 0 cur 0 0 curL3 0 1 cur 0 1 curL3 0 2 cur 0 2 curL3 0 3 cur 0 3 k 0 for i 0 i 50 i if cur i 0 break s cur i f 1 for j 0 j k j if OpD s curL3 j f 0 break if f 1 k curL3 k 0 cur i 0 curL3 k 1 cur i 1 curL3 k 2 cur i 2 curL3 k 3 cur i 3 for i 0 i 20 i for j 0 j 50 j s curL3 i if s 0 break if OpD s cur j countL3 i printf L3 n printf 项集 支持度计数 n for i 0 i 2 printf I c I c I c d n curL3 i 0 curL3 i 1 curL3 i 2 countL3 i void LoadItemL4 char p int i char s int j 0 for i 0 i 10 i s p i if SizeStr s 4 j printf 四维子集出现的次数 d n j printf 没有四维的频繁子集 算法结束 n void Support char w int g printf Support n int i j k n 0 char s float c 0 8 d 0 memset cur 0 sizeof cur s w for i 0 i SizeStr s i cur n 0 s i cur 0 0 1 cur 1 0 2 cur 2 0 5 cur n 1 0 cur n 2 0 cur n 3 0 n for i 0 i SizeStr s i for j i 1 j SizeStr s j if s j 0 break cu