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

关联规则挖掘在分类数据领域的扩展性研究

作　者: 毛宇星
导　师: 施伯乐
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 关联规则多层关联规则概化关联规则分类数据相关性函数集合枚举树前缀树增量挖掘
分类号: TP311.13
类　型: 博士论文
年　份: 2010年
下　载: 344次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机技术在社会各个领域的广泛应用,人们对信息系统的依赖程度越来越高。面对数据丰富而信息匮乏的困境,在统计学、数据库技术、机器学习、人工智能、模式识别和可视化技术等相关领域发展的基础上,以发现有用知识为目的的新兴交叉学科-数据挖掘技术应运而生。关联规则挖掘作为数据挖掘领域重要的研究方向之一,由于其在零售交易分析、客户关系管理、网络入侵检测、设备故障诊断、天文光谱分析、蛋白质结构分析和软件缺陷发现等应用领域的广泛适用性和特有价值,尽管历经二十多年的发展,仍然备受企业和学术界的高度关注,且正在向着新兴的研究领域扩展。本文通过对关联规则发展现状的系统性研究,选择了分类数据(Taxonomy)这一特殊领域作为扩展研究对象。这是因为分类数据作为一种结构化的数据不仅普遍存在,而且基于分类数据挖掘产生的关联规则蕴含更丰富、更灵活、更具参考价值的信息,因此该领域的扩展性研究对于实际应用和学术理论都具有非常特殊且重要的意义。本文的主要研究内容如下：首先,本文研究了分类数据关联规则挖掘的特殊情形——多层关联规则挖掘问题,这是基于分类数据扩展性研究的基础。本文根据挖掘遍历策略的不同,提出了两种新颖高效的多层关联规则挖掘方法TD-CBP-MLARM和BU-CBP-MLARM。其基本思想在于,首先利用分类数据所属领域的先验知识对通用的相关性度量函数进行有效修正,使之更加适合于分类数据项之间相关性的度量；然后基于修正后的相关性函数对分类数据各层次上的项依次进行聚类,根据各层项的层次聚类结果对事务数据库进行约简划分,从而缩小了事务数据库的规模,节省了挖掘算法扫描事务数据库的I/O操作时间,达到了提高算法挖掘效率的目的。其次,本文针对多层关联规则挖掘的一般情形——概化关联规则挖掘问题进行了研究。本文首先基于有候选项集方法的思想,提出了一种基于集合枚举树的概化频繁项集宽度优先挖掘方法SET-BFS。该方法可以确保所有k-项集产生之前,其所有的(k-1)-子项集已经产生,进而可以确保Apriori性质在分类数据领域的有效运用,实现对非频繁项集的高效剪枝,不仅避免了大量非频繁项集的计数和判定操作,还减少项集扩展空间的规模,从而提升此类算法的执行效率。进而结合最新的无候选项集方法的思想,提出了一种高效的概化关联规则挖掘方法GEAOT-tax。该方法引入了一种新颖的扩展升序前缀树GEAOT,采用自上而下、深度优先的遍历策略,结合双头表辅助结构以及合并、剪枝等一系列优化操作,进一步减少了算法的遍历开销,从而提升了算法整体效率。最后,本文将研究视角从静态分类数据进一步扩展至动态变化环境下,对概化关联规则更新保持问题进行了研究,并提出了一种基于概化扩展自然序树的增量挖掘方法GECT-IM。该方法只需扫描一次原始分类事务数据库,就可以将所有交易中的叶子项及其概化项映射至一棵压缩格式的自然序前缀树GECT,并通过引入更新头表来实现只对GECT中更新项集计数,然后结合相关性质及运算就能发现大部分更新后的频繁项集,而只对部分原来非频繁的项集才需重新遍历初始GECT树来得到,从而有效提升了挖掘效率。针对GECT规模较大以及GECT-IM算法在部分情况下仍需遍历初始GECT树的局限性,本文进一步提出了一种基于准频繁概化扩展自然序树的增量挖掘方法PGECT-IM。该方法通过准最小支持度阈值的引入,结合对数据库变化范围的判定,只利用符合准最小支持度的项集来构建PGECT,不仅可以减小树的规模,还可以有效避免GECT-IM方法在部分情况下仍需要遍历初始GECT树的局限性,进一步提升了增量挖掘的性能。

全文目录

摘要  6-8
Abstract  8-10
第一章绪论  10-22
  1.1 引言  10
  1.2 研究背景  10-18
    1.2.1 数据挖掘与知识发现  10-14
    1.2.2 关联规则挖掘及其在分类数据的研究  14-18
  1.3 存在问题及研究方向  18-19
  1.4 论文的主要贡献  19-21
  1.5 论文的组织结构  21-22
第二章问题描述及相关工作概述  22-37
  2.1 问题描述  22-24
  2.2 关联规则挖掘相关工作概述  24-27
    2.2.1 完整频繁模式挖掘  24-25
    2.2.2 封闭和最大频繁模式挖掘  25-26
    2.2.3 频繁模式扩展挖掘  26-27
  2.3 基于分类数据的关联规则挖掘相关工作概述  27-30
    2.3.1 多层关联规则挖掘  27-28
    2.3.2 概化关联规则挖掘  28-29
    2.3.3 概化关联规则增量挖掘  29-30
  2.4 主要算法介绍  30-36
    2.4.1 有候选项集代表算法—Apriori算法  31-33
    2.4.2 无候选项集代表算法—FP-Growth算法  33-36
  2.5 本章小结  36-37
第三章基于领域知识相关性划分的多层关联规则挖掘算法  37-55
  3.1 引言  37-39
    3.1.1 现有工作的局限性  37-38
    3.1.2 本章贡献  38
    3.1.3 本章安排  38-39
  3.2 基于相关性划分的多层关联规则挖掘算法  39-46
    3.2.1 基本思想  39-40
    3.2.2 基于领域知识的项相关性模型的构建  40-43
    3.2.3 基于项相关性函数的聚类方法  43-45
    3.2.4 基于聚类结果的事务数据库约简划分方法  45-46
  3.3 算法总结与分析  46-50
  3.4 实验分析  50-54
    3.4.1 实验数据及设置  50-51
    3.4.2 基于人工随机数据集的算法性能比较结果  51-53
    3.4.3 基于实际数据集的算法性能比较结果  53-54
  3.5 本章小结  54-55
第四章基于集合枚举树的概化关联规则挖掘算法  55-68
  4.1 引言  55-58
    4.1.1 现有工作的局限性  55-57
    4.1.2 本章贡献  57-58
    4.1.3 本章安排  58
  4.2 概化频繁项集宽度优先挖掘算法SET-BFS  58-61
    4.2.1 算法思想  58-59
    4.2.2 算法实现过程  59-61
  4.3 算法总结  61-64
  4.4 实验分析  64-67
    4.4.1 实验数据及设置  64-65
    4.4.2 算法性能比较结果  65-67
  4.5 本章小结  67-68
第五章基于GEAOT树的概化关联规则挖掘算法  68-82
  5.1 引言  68-71
    5.1.1 现有工作的局限性  68-71
    5.1.2 本章贡献  71
    5.1.3 本章安排  71
  5.2 概化关联规则挖掘算法GEAOT-tax  71-76
    5.2.1 主要思想  71-73
    5.2.2 算法实现过程  73-76
  5.3 算法总结  76-78
  5.4 实验分析  78-80
    5.4.1 实验数据及设置  78
    5.4.2 人工随机生成数据性能比较  78-80
    5.4.3 实际应用数据性能比较  80
  5.5 本章小结  80-82
第六章基于扩展自然序树的概化关联规则增量挖掘算法  82-103
  6.1 引言  82-84
    6.1.1 现有工作的局限性  82-83
    6.1.2 本章贡献  83-84
    6.1.3 本章安排  84
  6.2 基于扩展自然序树的增量挖掘算法GECT-IM  84-90
    6.2.1 基本思想  84-86
    6.2.2 算法实现过程  86-90
  6.3 基于准频繁扩展自然序树的增量挖掘算法PGECT-IM  90-94
    6.3.1 基本思想  90-92
    6.3.2 算法实现过程  92-94
  6.4 算法总结  94-96
  6.5 实验分析  96-102
    6.5.1 实验数据及设置  96-97
    6.5.2 GECT-IM算法与同类挖掘算法的性能比较  97-99
    6.5.3 GECT-IM算法与重执行算法的性能比较  99-100
    6.5.4 改进算法PGECT-IM与GECT-IM的性能比较  100-102
  6.6 本章小结  102-103
第七章总结和展望  103-105
  7.1 全文总结  103-104
  7.2 今后工作展望  104-105
参考文献  105-119
攻读学位期间作者的研究成果  119-120
致谢  120-121

关联规则挖掘在分类数据领域的扩展性研究

内容摘要

全文目录

相似论文