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

基于时序和极大团的关联规则数据挖掘方法的研究

作　者: 王宁
导　师: 夏幼明
学　校: 云南师范大学
专　业: 计算机软件与理论
关键词: 数据挖掘关联规则时序逻辑极大团黄金时间段概率空间数据挖掘分类聚类 KDD
分类号: TP311.13
类　型: 硕士论文
年　份: 2006年
下　载: 306次
引　用: 0次
阅　读: 论文下载

内容摘要

关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由Agrawal等人提出的（1993年）。最初提出的动机是针对购物篮分析（Basket Analysis）问题提出的，其目的是为了发现交易数据库（Transaction Database）中不同商品之间的联系规则。交易数据库可以把顾客的相关交易（如所购物品项目等）存储下来。通过对这些数据的智能分析，可以获得有关顾客购买模式的一般性规则。这些规则刻画了顾客的购买行为模式，可以用来指导商家科学地安排进货、库存以及货架设计等。关联规则在其它领域也可以得到广泛讨论，如目录设计、商品广告邮寄分析、追加销售、仓库规划、网络故障分析、市场规则、广告策划、分类设计等。关联知识（Association）反映一个事件和其它事件之间的依赖或关联，关联可分为简单关联、时序（Time Series）关联、因果关联、数量关联等。这些关联并不总是事先知道的，而是通过数据库中数据的关联分析得到的，因而对商业决策具有新价值。大多数算法得到的关联规则事实上假设其是永远有效的，但是时间是现实世界的重要属性，大容量数据集中的时间属性对用户来说可能是很关键的。用户关心的往往是某一时间区域的数据而不是整个数据，而特定时间区域的数据又可能导致特定的数据间的关联规则。解决这一问题的方法就是在算法中考虑时间因素，因此，数据库中表的字段要至少包括事务号、时态区间和项目序列三个字段。这里的时态区间反映了对应的项目序列发生或被收集的时间范围。关联规则的挖掘可以利用时态约束来进行预处理等工作，可以过滤掉用户不关心的时段上的数据。过滤数据库以减少扫描空间、降低输入输出代价、减少内存需求进而提高挖掘效率的关键。如果数据库中的每个元组均有其时态约束的规则，那么就可以更好的描述客观情况，因而更有价值。目前，大部分的工作都集中在时间并∪_T的范围内进行考虑的，显然和时间并∪_T相关的所有事务中的所有项目在时间并∪_T中都是必然发生的，但在时间交∩_T中却不一定，换言之，在时间并∪_T中，如果事务中某些项目的组合构成了频繁项目集，但在时间交∩_T中至少包含该频繁项目集的概率和P却不同。根据专家知识给此概率和一个阈值θ_gt，当P＞=θ_gt时，其P所在的时间交∩_T就称为黄金时间段。假设把黄金时间段的思想应用到超市的话，那么在时间交∩_T这些黄金时间段内，商家应根据不同的黄金时间段内出现的极大的频繁商品的不同而有的放矢的更准确的准备充足的货源，以供顾客购买。很显然，对于黄金时间段的研究也是一个很有意义的课题。由于计算机在处理海量的数据项的过程中，将是对内存的极大考验，而通过已经学过的极大团的特点，将关联性最强、项目之间最容易产生极大有序频繁项目集的项生成一个极大团，这样就可以把原来海量的数据项进行了有效的划分，缓解了内存不足的问题。本研究是将时序逻辑、极大团和数据挖掘的知识有效的结合在一起，针对上述问题提出了9个算法，并给出了算法复杂度的分析。主要成果与创新：①在时间并∪_T内求极大有序频繁项目集；②求至少包含出现在时间并∪_T内的那些极人有序频繁项目集同时发生在相应的时间交∩_T的概率

全文目录

1.基于时序和极大团的关联规则数据挖掘方法的研究  4-51
  第一章概述  8-11
    1.1 KDD的简介  8
    1.2 关联知识挖掘  8-11
      1.2.1 基本概念和问题描述  9
      1.2.2 关联规则挖掘的一般过程  9
      1.2.3 关联规则的技术标准  9-11
  第二章时序逻辑及其模式  11-17
    2.1 数据库的预处理  11
    2.2 基本概念和描述  11-16
    2.3 本章小结  16-17
  第三章极大团及其算法研究  17-24
    3.1 极大团的基本概念及其算法  17-22
    3.2 本章小结  22-24
  第四章基于时序逻辑的概率理论研究  24-38
    4.1 有关概率方面的基本概念  24-25
    4.2 等概率的数学模型  25-32
    4.3 不等概率的数学模型  32-37
    4.4 本章小结  37-38
  第五章基于极大频繁项目集的关联规则的生成算法  38-40
    5.1 关联规则算法  38-39
    5.2 本章小结  39-40
  第六章实验分析  40-46
  第七章结束语  46-47
  【参考文献】  47-51
2.数据挖掘的主要技术及其应用的研究  51-111
  第一章数据挖掘概述  56-59
    1.1 KDD的简介  56
    1.2 KDD过程如图1-1所示,由以下步骤组成  56-57
    1.3 数据挖掘定义  57
    1.4 数据挖掘的发展趋势  57-59
  第二章数据挖掘技术的研究  59-82
    2.1 数据挖掘的基本过程  59
    2.2 数据挖掘的主要任务  59
    2.3 典型的数据挖掘系统具有以下重要成分,见图2-1：  59-61
    2.4 数据挖掘技术分类问题  61-82
      2.4.1 分类  63-72
        2.4.1.1 决策树  63-65
        2.4.1.2 神经网络  65-68
        2.4.1.3 遗传算法与进化理论  68-69
        2.4.1.4 贝叶斯分类  69-71
        2.4.1.5 类比学习  71
        2.4.1.6 粗糙集方法  71-72
        2.4.1.7 模糊集方法  72
      2.4.2 聚类  72-82
        2.4.2.1 基于划分(Partitioning)的聚类方法  73-75
          2.4.2.1.1 k-平均算法  73-74
          2.4.2.1.2 PAM(Partitioning around Medoid,围绕中心点的划分)算法  74-75
        2.4.2.2 基于层次的聚类方法(hierarchical method)  75-76
          2.4.2.2.1 AGNES算法  75-76
          2.4.2.2.2 DIANA(Divisive ANAlysis)算法  76
        2.4.2.3 基于密度的方法(density-based method)  76-78
          2.4.2.3.1 OPTICS算法  78
        2.4.2.4 基于网格的方法(grid-basedmethod)  78-80
          2.4.2.4.1 STING(Statistical Information Grid,统计信息网格)  78-79
          2.4.2.4.2 WaveCluster(采用小波变化聚类)算法  79
          2.4.2.4.3 CLIQUE(聚类高维空间)算法  79-80
        2.4.2.5 基于模型的聚类方法  80-82
          2.4.2.5.1 COBWEB算法  80-82
  第三章知识发现及其技术  82-103
    3.1 关联知识挖掘  82-94
      3.1.1 基本概念和问题描述  82-83
      3.1.2 关联规则挖掘的一般过程：  83
      3.1.3 关联规则的技术标准  83-85
      3.1.4 关联规则的算法  85-94
        3.1.4.1 Apriori算法  85-87
        3.1.4.2 Apriori算法的改进  87-88
          3.1.4.2.1 基于数据分割(Partition)的方法  87
          3.1.4.2.2 基于散列(Hash)的方法  87
          3.1.4.2.3 基于采样(Sample)的方法  87-88
          3.1.4.2.4 基于事务压缩的方法：  88
          3.1.4.2.5 基于动态项集计数的方法：  88
        3.1.4.3 FP-tree算法  88-91
        3.1.4.4 增量式更新算法  91-92
        3.1.4.5 并行发现算法  92
        3.1.4.6 带有约束的数据挖掘算法  92-93
        3.1.4.7 时态约束的关联规则挖掘算法  93-94
        3.1.4.8 多层次关联规则挖掘算法  94
    3.2 预测型知识挖掘  94-95
      3.2.1 时序(Time Series)数据和序列(Sequence)数据的挖掘  94-95
    3.3 特异型知识挖掘  95-97
      3.3.1 孤立点分析  95-97
        3.3.1.1 基于统计的孤立点检测  96
        3.3.1.2 基于距离的孤立点检测  96-97
        3.3.1.3 基于偏离的孤立点检测  97
    3.4 空间数据挖掘  97-103
      3.4.1 空间数据挖掘的基础  98-99
      3.4.2 空间数据挖掘方法  99-100
        3.4.2.1 统计空间分析方法  100
      3.4.3 规则归纳  100-101
      3.4.4 聚类方法  101
      3.4.5 模糊集  101-102
      3.4.6 分类法  102-103
        3.4.6.1 空间决策树  102-103
  第四章数据挖掘应用的成功案例分析  103-105
    4.1 数据挖掘在体育竞技中的应用  103
    4.2 数据挖掘在科学探索中的应用  103
    4.3 数据挖掘在金融方面的应用  103-104
    4.4 数据挖掘在零售业中的应用  104
    4.5 数据挖掘在电信中的应用  104-105
  [参考文献]  105-111
3. The Research Based on Time Series and Maximum Clique for Data Mining of Association Rules  111-166
  CHAPTER 1 INTRODUCTION  119-123
    1.1 KDD INTRODUCTION  119-120
    1.2 THE MINING OF ASSOCIATION KNOWLEDGE  120-123
      1.2.1 Basic Concepts and Question Descriptions  120-121
      1.2.2 the General Process of Association Rule Data Mining  121
      1.2.3 Technical Standard of Association Rules  121-123
  CHAPTER 2 THE KNOWLEDGE OF TIME SERIES LOGIC  123-130
    2.1 PRETREATMENTS OF DATABASES  124
    2.2 BASIC CONCEPTS AND DESCRIPTION  124-129
    2.3 THE CHAPTER SUBTOTAL  129-130
  CHAPTER 3 THE RESEARCH OF MAXIMUM CLIQUE AND ITS ALGORITHM  130-138
    3.1 THE MAXIMUM CLIQUE'S BASIC CONCEPT AND ITS ALGORITHMS  130-137
    3.2 THE CHAPTER SUBTOTAL  137-138
  CHAPTER 4 THE RESEARCH BASED ON TIME SERIES LOGIC PROBABILITY THEORY  138-154
    4.1 THE KNOWLEDGE OF PROBABILITY  138-139
    4.2 THE PROBABILITY MATHEMATICAL MODEL IN EQUAL PROBABILITY SITUATION  139-147
    4.3 THE PROBABILITY MATHEMATICAL MODEL IN UNEQUAL PROBABILITY SITUATION  147-152
    4.4 THE CHAPTER SUBTOTAL  152-154
  CHAPTER 5 PRODUCING ALGORITHM OF THE ASSOCIATION RULE BASED ON THE MAXIMUM FREQUENT ITEM SET  154-157
    5.1 ASSOCIATION RULE ALGORITHM  154-156
    5.2 THE CHAFFER SUBTOTAL  156-157
  CHAPTER 6 THE EXPERIMENT AND THE ANALYSIS  157-164
  CHAPTER 7 THE CONCLUDING REMARK  164-166
4. The Research of Data Mining Main Technology and its Application  166-241
  CHAFFER 1 DATA MINING SUMMARY  172-175
    1.1 KDD INTRODUCTION  172
    1.2 KDD PROCESS IS COMPOSED BYTHE STEP LIKE CHART 1-1 SHOWING THAT:  172-173
    1.3 THE DEFINITION OF DATA MINING  173-174
    1.4 THE DEVELOPMENT TENDENCY OF DATA MINING  174-175
  ChAPTER 2 DATA MINING TECHNOLOGY RESEARCH  175-208
    2.1 THE PROCESS OF DATA MINING:  175-176
    2.2 PRIMARY MISSION OF DATA MINING  176
    2.3 MODEL OF DATA MINING SYSTEMS HAS THE IMPORTANT INGREDIENT, SEEING THE FIG. 2-1  176-177
    2.4 DATA MINING'S TECHNICAL CLASSIFICATION QUESTION  177-208
      2.4.1 Classifications  180-194
        2.4.1.1 Decision tree  180-184
        2.4.1.2 Nerve Networks  184-188
        2.4.1.3 Genetic Algorithms and Evolution Theory  188-189
        2.4.1.4 Baye Classifies  189-192
        2.4.1.5 Analogy Studies  192-193
        2.4.1.6 Rough Volume of Methods  193-194
        2.4.1.7 Fuzzy Sets Methods  194
      2.4.2 Cluster  194-208
        2.4.2.1 Based on Division (Partitioning) Gathers a Kind of Method  195-198
          2.4.2.1.1 k-average Algorithm  196-197
          2.4.2.1.2 PAM (Partitioning around Medoid, Revolves the central point the division) the Algorithm  197-198
        2.4.2.2 Gathers a Kind of Method Based on the Level (Hierarchical Method)  198-200
          2.4.2.2.1 AGNES Algorithm  199-200
          2.4.2.2.2 DIANA(Divisive ANAlysis)algorithm  200
        2.4.2.3 Based on Density Method (Density-Based Method)  200-203
          2.4.2.3.1 OPTICS Algorithm  203
        2.4.2.4 Based on Grid Method (Grid-Based Method)  203-206
          2.4.2.4.1 STING (Statistical Information Grid, Counts Information Grid)  204
          2.4.2.4.2 WaveCluster Algorithm (Uses Wavelet Change to Gather Kind)  204-205
          2.4.2.4.3 CLIOUE (Gathers the Kind of High Uygur Space) the Algorithm  205-206
        2.4.2.5 a Kind of Gathered Method Based on the Model  206-208
          2.4.2.5.1 COBWEB Algorithm  206-208
  CHAPTER 3 KNOWLEDGE DISCOVERYAND ITS TECHNOLOGY  208-238
    3.1 MINING OF ASSOCIATION KNOWLEDGE  208-225
      3.1.1 Basic Concepts and Question Description  208-209
      3.1.2 the General Process of Association Rule Data Mining:  209
      3.1.3 Technical Standard of Association Rules  209-212
      3.1.4 the Association Rule Algorithm  212-225
        3.1.4.1 Apriori Algorithm  212-214
        3.1.4.2 the Improvement of Apriori Algorithm  214-216
          3.1.4.2.1 the Method Basing on Data Partition (Partition)  214-215
          3.1.4.2.2 the Method Basing on Hash (Hash)  215
          3.1.4.2.3 the Method Based on Sample (Sample)  215-216
          3.1.4.2.4 the Methods Which Based on Transaction Compression:  216
          3.1.4.2.5 the Method Which Based on the Dynamic Counting of Item Set:  216
        3.1.4.3 FP-tree Algorithm  216-220
        3.1.4.4 Increasing Type Renewal Algorithm  220-222
        3.1.4.5 the Algorithms of Parallel Discoveries  222
        3.1.4.6 the Data Mining Algorithm with the Restraint  222-224
        3.1.4.7 Association Rule Mining Algorithm with Tense Restraints  224-225
        3.1.4.8 Multi-level Association Rules Mining Algorithm  225
    3.2 THE PREDICTING KNOWLEDGE MINING  225-227
      3.2.1 The Mining of the Time Series Data (Time Series) and Sequence Data (Sequence)  226-227
    3.3 THE EXCEPTION KNOWLEDGE MINING  227-229
      3.3.1 the Analyses of the Outlier Points  227-229
        3.3.1.1 Outlier Point Examination Basing on Statistic  227-228
        3.3.1.2 the Outlier Point Examination Basing on Distance  228-229
        3.3.1.3 Deviation-based Outlier Detection  229
    3.4 THE SPATIAL DATA MINING  229-238
      3.4.1 the Foundation of the Spatial Data Mining  231-233
      3.4.2 the Method of the Spatial Data Mining  233-234
        3.4.2.1 The Statistical Spatial Analysis Method  233-234
      3.4.3 Rule's Induction  234-235
      3.4.4 Cluster Method  235-236
      3.4.5 Fuzzy Sets  236
      3.4.6 Classification Method  236-238
        3.4.6.1 Spatial Decision Tree  237-238
  CHAPTER 4 TRE SUCCESSFUL CASE ANALYSIS OF DATA MININGAPPLICATION  238-241
    4.1 THE APPLICATION OF DATA MINING IN SPORTS ATHLETICS  238
    4.2 THE APPLICATION OF DATA MINING IN SCIENCE EXPLORATION  238-239
    4.3 THE APPLICATION OF DATA MINING IN FINANCIAL  239
    4.4 THE APPLICATION OF DATAMINING IN RETAIL TRADE  239-240
    4.5 THE APPLICATION OF DATA MINING  240-241
致谢  241

相似论文

基于贝叶斯网络的入侵检测,TP393.08
基于KDD的销售数据预处理管理系统,TP311.13
分布式教务管理系统,TP315
分布式关联规则挖掘的方法研究,TP311.13
KDD中的几个关键问题研究,TP311.13
数据库中的知识发现及其应用研究,TP311.13
隐式用户兴趣挖掘的研究与实现,TP311.13
图像分割中阴影去除算法的研究,TP391.41
基于图分割的文本提取方法研究,TP391.41
牡丹EST-SSR引物开发及其亲缘关系分析,S685.11
高血压前期证候特征研究,R259
高忠英学术思想与经验总结及运用补肺汤加减治疗呼吸系统常见病用药规律研究,R249.2
K-均值聚类算法的研究与改进,TP311.13
大学生综合素质测评研究,G645.5
大豆品种对腐竹品质的影响及其品质评价体系的初步构建,TS214.2
基于聚类分析的P2P流量识别算法的研究,TP393.02
基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
土壤环境功能区划研究,X321
象草自交后代无性系的饲用价值及生物质能特性初步评价,S543.9
K-means聚类优化算法的研究,TP311.13