学位论文 > 优秀研究生学位论文题录展示

基于投影数组和加权FP-tree的频繁项集挖掘算法研究

作　者: 曹海燕
导　师: 何海涛
学　校: 燕山大学
专　业: 计算机软件与理论
关键词: 频繁项集频繁闭项集投影数组长度递减支持度约束权值约束深度优先搜索
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 10次
引　用: 0次
阅　读: 论文下载

内容摘要

频繁项集挖掘是数据挖掘领域中一个比较关键的问题。然而,从大型稠密数据集中挖掘频繁项集存在三个主要的瓶颈问题:第一,算法的挖掘效率不是很高;第二,产生的频繁项集的数量太多;第三,没有采用合理的约束思想,不能有效的挖掘用户兴趣模式。本文针对这些问题,将研究重点放在频繁项集挖掘算法上,其研究成果可广泛应用于客户购买行为模式预测、序列分析和软件安全分析等领域。首先,本文提出了基于投影数组的频繁项集挖掘算法MFIPA。基于垂直和水平混合数据格式,通过交集操作找到与单个频繁项共同发生的项集,产生投影数组PArray;然后,通过单个频繁项与其投影的非空子集合并及深度优先搜索策略的使用,挖掘所有的频繁项集。其次,为了减少频繁项集的数量,设计了一个新颖的频繁闭项集挖掘算法FCIL-Mine。基于投影数组,首先提出了频繁闭项集框架数据结构FCIL,该框架主要是用来存储频繁闭项集的一些信息。然后,通过哈希检测和包含检测剪枝策略的使用,进而挖掘所有的频繁闭项集。最后,提出了一个基于加权FP-tree及长度递减支持度约束的加权频繁项集挖掘算法LWFI-Mine。该算法可以有效的挖掘满足用户兴趣的项集。首先通过扫描数据库,构造数据结构加权FP-tree。然后提出加权最小有效扩展性质WSVE及基于此性质的三种剪枝策略:事务剪枝、结点剪枝和路径剪枝,缩小了FP-tree的搜索空间,进而挖掘所有满足约束的频繁项集。本文使用C++语言对上述算法进行实现,采用稀疏的人工数据集T40I10D100K和稠密的真实数据集Connect进行频繁项集挖掘实验研究。

全文目录

摘要  5-6
Abstract  6-10
第1章绪论  10-17
  1.1 频繁项集挖掘技术  10-15
    1.1.1 频繁项集挖掘的研究背景及意义  10-11
    1.1.2 频繁项集挖掘的国内外研究现状  11-14
    1.1.3 频繁项集挖掘存在的问题  14-15
  1.2 课题的主要研究内容  15-16
  1.3 本文的结构内容安排  16-17
第2章基于投影数组的频繁项集挖掘算法  17-28
  2.1 引言  17-18
  2.2 问题描述  18-19
  2.3 投影数组的设计与构造  19-22
    2.3.1 投影数组的设计  19
    2.3.2 投影数组的构造算法  19-20
    2.3.3 算法应用实例  20-22
  2.4 频繁项集挖掘算法MFIPA 的设计  22-26
    2.4.1 扩展定理  22-23
    2.4.2 MFIPA 算法  23-25
    2.4.3 算法实例分析  25-26
  2.5 算法分析  26
  2.6 本章小结  26-28
第3章基于投影数组和闭项集框架的频繁闭项集挖掘算法  28-39
  3.1 引言  28-29
  3.2 问题描述  29-30
  3.3 投影数组的产生  30-31
  3.4 FCIL-Mine 算法  31-37
    3.4.1 频繁闭项集框架FCIL 的设计  31-32
    3.4.2 剪枝策略  32-33
    3.4.3 频繁闭项集挖掘算法FCIL-Mine 的设计  33-35
    3.4.4 算法应用实例  35-37
  3.5 算法分析  37-38
  3.6 本章小结  38-39
第4章基于加权FP-tree 与约束条件的频繁项集挖掘算法  39-51
  4.1 引言  39-40
  4.2 问题定义与描述  40-41
  4.3 加权FP-tree 数据结构的设计  41-44
  4.4 基于加权最小有效扩展性质的剪枝策略  44-46
    4.4.1 基于WSVE 性质的事务剪枝  45
    4.4.2 基于WSVE 性质的结点剪枝  45
    4.4.3 基于WSVE 性质的路径剪枝  45-46
  4.5 基于约束的频繁项集挖掘算法LWFI-Mine  46-49
    4.5.1 算法LWFI-Mine 的设计  46-48
    4.5.2 算法应用实例  48-49
  4.6 算法分析  49-50
  4.7 本章小结  50-51
第5章算法实现及实验分析  51-60
  5.1 数据集的来源  51-52
  5.2 实验环境及配置  52
  5.3 MFIPA 算法的性能分析  52-53
    5.3.1 在稀疏数据集上比较  52
    5.3.2 在稠密数据集上比较  52-53
  5.4 FCIL-Mine 算法的测试  53-55
    5.4.1 在稀疏数据集上比较  54
    5.4.2 在稠密数据集上比较  54-55
  5.5 LWFI-Mine 算法的性能分析  55-59
    5.5.1 产生的频繁项集数量  56-57
    5.5.2 运行效率  57-59
  5.6 本章小结  59-60
结论  60-62
参考文献  62-67
攻读硕士学位期间承担的科研任务与主要成果  67-68
致谢  68-69
作者简介  69

基于投影数组和加权FP-tree的频繁项集挖掘算法研究

内容摘要

全文目录

相似论文