关联规则挖掘技术若干问题研究

VIP免费

3.0 牛悦 2024-11-19 4 4 3.09MB 81 页 15积分

侵权投诉

摘要

数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提

取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程，被

信息产业界认为是数据库系统最重要的前沿之一，是信息产业界最有前途的交叉

学科。

关联规则是数据挖掘中一个重要的研究内容。本文对数据挖掘技术尤其是关

联规则挖掘技术进行了系统、深入地分析和研究，并将其投入到实际应用中。主

要包括以下一些内容：

首先对数据挖掘技术进行了简要的回顾，在提出关联规则挖掘基本概念的基

础上，对关联规则挖掘进行了详细地分类、归纳和总结。另对关联规则挖掘技术

的国内外研究现状和当前的研究热点进行了归纳和总结，为本文的全面展开奠定

了基础。

接着重点讨论了关联规则挖掘算法的两个相对独立的过程：频繁项集挖掘过

程与关联规则产生过程。针对用户经过一次关联规则挖掘后对自己找出的关联规

则并不满意，转而再去进行一遍又一遍的挖掘，直到获得满意的效果的现象，本

文在 FP-Growth 算法的基础上提出了基于支持度变化的 FP-Growth 算法，算法利

用前次的挖掘结果进行再挖掘，从而节省挖掘时间。针对关联规则产生算法，本

文在 FAS 算法的基础上提出了改进算法 IFAS 算法，它通过降低访问频繁项集集合

的次数，减少 I/O 吞吐，从而提升关联规则产生的效率。

然后将数据挖掘技术应用到教学管理系统中，对现有数据库中的学生成绩数

据实施挖掘，进行课程相关性分析。适应于当前数据源的特点，在己提出的改进

算法的基础上，对算法进行形式上的改变，通过数据准备、数据挖掘、结果描述

等方面详细描述设计过程。挖掘结果可供决策者更科学的设置课程，也为教学管

理工作增加了新的内容。

最后，针对挖掘的同时如何保护学生隐私的问题，对隐私保护的量化属性关

联规则挖掘进行了研究。首先介绍了基于数据扰动技术的隐私保护的关联规则挖

掘算法，并通过试验验证了基于数据扰动技术的隐私保护的关联规则挖掘技术在

一定的条件限制下可以应用于学生成绩数据的关联规则挖掘，证明了其技术可行

性。接着提出了 VSS-MASK 算法避免了原 MASK 算中事务数据库因采用横向结

构组织数据所带来的强稀疏性、通用性差等缺点，通过采用纵向结构组织数据，

和只提交变换后为‘1’的数据组成的数据表的方法，以避免因大量 0值的存在而

造成的稀疏性，从而提升算法中数据扫描的效率。

关键词：数据挖掘关联规则增量更新隐私保护

ABSTRACT

Datamining is the process of abstraction unaware, potential and usefulin

formation and knowledge from plentiful, in complete, noisy, fuzzy and stochastic data,

which is deemed to one of a foreland of datamining system and a promising

cross-subject. Association rule is one of more important role in abstraction association

rules. This dissertation systematically and deeply studies and analyses the datamining

technique, especially the one for association rules, further more appliesit to

practice.The main contents are listed as follows.

At first, the appearance of the datamining technique is reviewed in brief. Based on

the basic concepts of datamining, this dissertation not only classifies and summarizes

the findable patterns of datamining in detail, but also studies architecture structure and

running process of datamining In succession, the dissertation summarizes and studies

the current status of the datamining technique in our native country and overseas.All of

the above become the basis for this dissertation.

Then, we discussed two relativelyin dependent processes of the Association Rule

algorithm with emphasis: the processe of generating Itemsets and the processe of

generating association rules. In view of phenomenon that users were unsatisfied with

the result of the previously datamining, we discussed the FP-Growth algorithm of

based on support changed, which carried on using the recently result to find new

itemsets, so it can saved the mining time. About the generating association rules, this

article proposed the IFAS algorithm which based on the FAS algorithm, it through

reduces the times of visiting the Itensets to reduces the I/O turnover, thus the

promotion rules production efficiency.

Then next, it applies the datamining to education management system, and

expects to derive courses correlations by analyzing the students' score database.

According to the characteristic of the data source, it changes the old format of the

algorithm and describesthe designing process detailedly from four aspects, named data

preprocessing, datamining, result description and pattern evaluation. It meets the need

of the reform of the credit system and provides a scientific basis for college

management and decision-making.

At last, in view of phenomenon that how to protect the privacy, this aticle

discussed the privacy-preserving quantitative association rule mining algorithm. This

atricle emphatically introduced the privacy-preserving quantitative association rule

mining algorithm which based on the data perturbation technology, then proved that it

could be supposed to use in the course relation minging under the certain condition

limit.

Key Word: data mining, association rule, incrematal updating

frequent itemsets, privacy-preserving

中文摘要

ABSTRACT

第一章绪论 .............................................................................................................1

§1.1 课题研究的目的和意义 .................................................................................1

§1.2 相关技术现状 .................................................................................................2

§1.3 本文的主要工作 .............................................................................................5

第二章关联规则挖掘技术简介 .................................................................................7

§2.1 关联规则的基本概念和问题描述 .................................................................7

§2.2 关联规则挖掘算法 .........................................................................................7

§2.2.1 算法分类 ........................................................................................…..8

§2.2.2 Apriori 典型算法 .................................................................................9

§2.2.3 FP-Growth 挖掘算法 .........................................................................13

§2.2.4 关联规则产生算法 ............................................................................15

§2.3 量化属性关联规则挖掘 ...............................................................................16

第三章基于支持度变化的 FP-Growth 算法 ...........................................................18

§3.1 相关概念与问题描述 ...................................................................................18

§3.2 FIUA1 算法 .................................................................................................. 20

§3.3 基于最小支持度变化的 FP-Growth 算法 ...................................................22

§3.4 算法分析与试验 ...........................................................................................25

§3.5 本章小结 .......................................................................................................29

第四章快速关联规则产生算法 ...............................................................................30

§4.1 相关概念与问题描述 ...................................................................................30

§4.2 快速关联规则产生算法 FAS...................................................................... 30

§4.3 IFAS 算法 ..................................................................................................... 32

§4.4 算法分析与试验 ...........................................................................................35

§4.5 本章小结 .......................................................................................................38

第五章关联规则挖掘在课程相关性分析中的应用研究 .......................................39

§5.1 数据挖掘系统架构 .......................................................................................39

§5.2 相关技术与工具介绍 ...................................................................................41

§5.3 关联规则挖掘系统的实现 ...........................................................................43

§5.3.1 数据准备 ............................................................................................43

§5.3.2 挖掘算法的选择 ................................................................................47

§5.3.3 挖掘结果的表述 ................................................................................49

§5.4 本章小结 .......................................................................................................51

第六章面向隐私保护的关联规则挖掘研究 ...........................................................52

§6.1 相关概念与问题描述 ...................................................................................52

§6.2 隐私保护的关联规则挖掘算法 ...................................................................53

§6.2.1 基于随机响应技术的隐私保护关联规则挖掘算法 ........................54

§6.2.2 保护隐私的量化关联规则挖掘方法 ................................................56

§6.3 试验系统与结果分析 ...................................................................................61

§6.4 本章小结 .......................................................................................................64

第七章隐私保护关联规则挖掘的一种改进方法 ...................................................65

§7.1 相关概念与问题描述 ...................................................................................65

§7.2 算法改进思路 ...............................................................................................65

§7.3 VSS-MASK 算法......................................................................................... 67

§7.4 试验与结果 ...................................................................................................68

§7.5 结论 ...............................................................................................................70

第八章结束语 ...........................................................................................................71

§8.1 总结 ...............................................................................................................71

§8.2 未来研究方向 ...............................................................................................71

参考文献 .......................................................................................................................73

在读期间公开发表的论文和承担科研项目及取得成果............................................77

致谢 .......................................................................................................................78

第一章绪论

§1.1 课题研究的目的和意义

关联规则挖掘较多地应用于商业系统，用于发现交易数据中不同商品（项）

之间的联系，这些规则找出顾客的购买行为模式，如购买了某一商品对其它商品

的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式

对用户进行分类。本文旨在对教育领域的数据挖掘进行探索性研究。

在教育系统中，特别是在各级各类学校中，学校的数据库中存贮着大量的教

育教学信息，其中一部分和教学有关：如学校的开课排课情况、任课教师情况等，

另一部分是和学生有关的信息：如学生的基本情况、家庭背景、身体状况、学生

的历年的考试、测验成绩等。特别是最近几年来随着教育信息化的推进、学校数

据库的内容大大增加，学校几乎实现了无纸化管理，所有的信息几乎都能在电脑

上找到，学校数据库的内容已经相当的完整。但是这些数据很少被开发利用，使

得隐藏着大量教育信息的历史数据没有被很好的利用。如挖掘隐藏在这些数据中

的教育规律、学生的培养模式、学生学课之间的差异性和相关性规律。另一方面，

在教育系统中存在着一些缺少依据的说法：如数学成绩好的同学物理成绩也一定

很好，或数学成绩好的同学其他的理科一定很好。如钢琴弹得很好的同学，他的

成绩一定不会差。又如父母是高学历的，孩子成绩一般不会差等。在一定的条件

下，这些说法因其基本与事实一致而被广泛接受，但这些命题缺少理论的和实验

的依据。这些说法完全可以利用现在己经拥有的大量的数据，对其进行数据挖掘，

来证实某些命题，或说明某些说法不能成立，或者更确切地说明其支持度和可信

度。

从大量的教育信息中挖掘出的正确的、可靠的、可信的关联规则对教育系统

是相当重要的，对教育教学改革具有指导性的意义。学校可以利用关联规则所揭

示的学生在学习中学科之间的相关性，适当组合学科课程，使相关学科互相促进

共同提高；利用关联规则发现的学生培养模式，合理设计课程开设的次序，符合

学生智力发展规律；利用学课的相关性、知识的相关性、学生学习兴趣的可迁移

性，在活动课中组织跨学科的活动，扩大学生在学习中学科之间的相关性和相关

程度，引导学生从强势学科入手，提高相对较弱的学科，最终使学生在学业上均

衡发展。

课题通过数据挖掘技术分析成绩数据，进行成绩关联规则分析专题相关关键

技术的研究，目的是在汲取别人经验的前提下，对数据挖掘理论尤其是关联规则

在高校教学管理系统中的应用进行研究，具有一定的理论与应用价值。

关联规则挖掘技术若干问题研究

§1.2 相关技术现状

1数据挖掘技术

KDD[1，2，3，4]一词首次出现在 1989 年8月举行的第 11 届国际联合人工智能学

术会议上。IEEE 的Knowledge and Data Engineering 会刊领先在 1993 年出版了 KDD

技术专刊，所发表的 5篇论文代表了当时 KDD 研究的最新成果和动态，较全面地

论述了 KDD 系统方法论、发现结果的评价、KDD 系统设计的逻辑方法，集中讨

论了关于数据库的动态性冗余、高噪声和不确定性、空值等问题，KDD 系统与其

它传统的机器学习、专家系统、人工神经网络、数理统计分析系统的联系和区别，

以及相应的基本对策。

不仅如此，在 Internet 上还有不少 KDD 电子出版物，其中以半月刊 Knowledge

Discovery Nuggets 最为权威，另一份在线周刊为 DS* (DS 代表决策支持)，1997 年

l0 月7日开始出版。在网上，还有一个自由论坛 DM Email Club，人们通过电子邮

件相互讨论 DMKD 的热点问题。而领导整个潮流的 DMKD 开发和研究中心，当

数设在美国 EMDEN 的IBM 公司开发部。

从总体上，国外在数据挖掘领域中的研究内容十分广泛[5]，从挖掘知识的种类

看，己经取得了明显的成果。

1）关联规则的研究[4，5，6，7，8，9]；近几年对关联规则的研究内容较多，现在，

关联规则的挖掘已经从单一概念层次关联规则的发现发展到多概念层次关联规则

的发现[5,6]，并把研究的重点放在提高算法的效率和规模可收缩性上。目前，人们

对于定量关联规则以及其他种类的关联规则的发现研究较为深入，提出了关联规

则的很多的概念。与此同时，在提高挖掘过程的效率方面也作了不少的研究。比

较著名的算法有 Apriori，CHARM，FP-Growth，MagnumOPUSS，GenMax 等。

2）数据分类技术研究；基于决策树的分类方法在大规模数据库条件下的应用

研究；在较高的抽象层次分类中，M.Mehte 等人针对大型数据库提出了一种快速

分类算法，称为 QUEST 中的超级学习算法(SLIQ)：分类与回归的管状领域研究、

最近邻分类方法的改进等等。

3）聚类规则研究；近年，聚类开始在大型数据库中得到研究，R.Ng 和J.Han

基于随机搜索以及统计学中的两个聚类算法 PAM 和CLARA，给出了一个适用于

大型应用的聚类算法：CLARANS。M.Ester 等人针对 CLARANS 算法的缺点，提

出了改进技术。通过引入更为有效的空间数据库存取算法，如 R－树，来提升

CLARANS 算法的性能。T.Zhang 等人则提出了另一种聚类算法 BIRCH 算法。

4）泛化、简约和特征提取研究；利用数据可视化大大扩展了数据的表达和

理解能力，这是数据简约的一种非常重要的技术，它正受到日益广泛的重视。

第一章绪论

与国外相比，国内对数据挖掘与知识发现(MDKD)的研究稍晚[10]，1993 年国

家自然科学基金首次支持对该领域的研究项目。目前，清华大学、中科院计算技

术研究所、空军第三研究所、海军装备论证中心等竞相开展数据挖掘的基础理论

及其应用研究。其中，北京系统工程研究所对模糊方法在知识发现中的应用进行

了较深入的研究，北京大学也在开展对数据立方体代数的研究；华中理工大学、

复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展

了对关联规则开采算法的优化和改造；南京大学、四川联合大学和上海交通大学

等单位探讨、研究了非结构化数据的知识发现以及 Web 数据挖掘。现在尽管与国

际上的进展相差并不远，一些研究成果例如：总参六十一所的李德毅教授在云模

型方面的研究；复旦大学的施伯乐教授在关系数据库中知识发现方面取得很大的

成果；南京大学开发的 KNIGHT 系统等。但在实际应用方面却鲜有所闻，成功的

例子很少，没有形成整体力量。总的说来，国内在数据挖掘方面没有大量的投入

到实际生产应用中去，还停留在实验的阶段，。

2关联规则技术

Agrawal 等人首先于 1994 年提出 Apriori 算法[1，6，7]以找出关联规则。此算法

是由单一项目集开始，逐层(level-wise)去扩展其它的相关项目集。优点是可以减少

非相关项目集的产生，节省 CPU 的时间；但缺点为需要多次扫描数据库，尤其当

数据库相当庞大且要找的项目集长度较长时，会耗费相当多 I/O 时间。

Savasere 等人在 1995 年提出了 Partition[11]算法，将数据切割成数区，第一阶

段先以较低的支持度找出该区可能的相关项目集，第二阶段再依据第一阶段找出

的相关项目集计算支持度，因此最多只需要二次扫描数据库的成本，但是因为此

方法会产生过多的非相关项目集，因此相当耗费 CPU 的时间。Toivonen 在1996

年提出 Sampling 算法只需要一次扫描数据库，但其找出的结果存在是否正确的问

题。

Brin 等人在 1997 年提出了 DIC (Dynamic Itemset Counting)[12]算法，可减少相

关项目集的计算及较少的扫描数据库的次数，但此算法效率受数据库中数据分布

的影响极大。Lin 等人以及 Bayardo 在1998 年分别提出了 Pincer-Search 算法和

Max-Miner 算法，针对当项目集的长度较长时，该算法能有较好的效率。

Cheung 等人于 1996 年提出了 FUP( Fast Update Algorithm)[13]算法，将研究方

向导向关联规则的维护，主要是针对当数据库的内容新增时，能够以较快的效率

更新关联规则，不过此一方法是以 Apriori 算法为基础，所以仍需多次重新扫描未

变动的数据库。冯玉才等[14 ]针对关联规则更新的“给定数据库 DB , 在最小支持度

和最小置信度发生变化时,如何生成数据库 DB 中的关联规则。”问题进行了研究,

关联规则挖掘技术若干问题研究

设计出了相应的 IUA 和PIUA 算法。算法 IUA 采用了一个独特的候选强项集生成

算法 IUA-GEN , 在每一次对数据库 DB 扫描之前生成较小的候选强项集,从而提

高了算法的效率。它也要求上一次对数据库进行挖掘时发现的强项集。因为人们

在发现关联规则时,常常需要不断地调整最小支持度和最小可信度来聚集到那些

真正令其感兴趣的关联规则上,因而该算法具有很重要的意义；在 IUA 算法中,将

所有的频繁 k项目集分成了互不相交的 3类,这使得 IUA 算法能够很容易实现基

于共享内存(shared-memory) 多处理机结构的并行化,即PIUA 算法。事实上,像

PIUA 这样的基于共享内存多处理机结构的并行算法特别有利于在限时应用中用

来加快单个大顺序算法的计算。

在其它相关的研究上，针对关联规则也有进一步的研究，广义的关联规则

(generalize dassociation rule)将数据做层级的规划，例如果汁和可乐都归类于冷饮的

种类，茶叶蛋和猪蹄都归类于熟食的种类等;如何去定义层级的关系以及有效地找

出这些层级之间的关联规则是一大问题。含数值属性的关联规则(quantitative

association rule)在于讨论项目属性是数字型态时，如何去划分这些数字区段以找出

较好的关联规则。例如以年龄属性而言，是要以 5岁为一区段或是以 10 岁为一区

段，甚或以 1岁为一区段等，这对于产生的关联规则将有很大的影响。有些研究

在讨论如何找出不同使用者所真正感兴趣的关联规则(constrain association rule)，通

过加入一些条件限制、设定权重、或者使用查询语言(query language)等来达到目的。

此外也有一些研究讨论不同于以往要找出支持度及置信度皆大于使用者所定的最

小限制的关联规则，而是要找出相对的出现频率较小但却对使用者来说非常重要

的关联规则。

另外有些研究是关于路径选择模式(path traversal pattern)的问题，目的在于找

出浏览者浏览网页的习惯，以设计较好的网页架构以增加商业机会；有些研究是

关于序列模式(sequential pattern)的问题，目的在于找出某些事件发生的先后关系，

如顾客购买甲商品后接着会购买乙商品，A股票股价上涨后 B股票也会跟着上涨

等。也有相关研究在于组织架构以及数据存取的问题，以较大的存储空间及新的

存取机制换取较好的执行效率。

关联规则的研究随着应用的不断深入而得到长足发展，有关关联规则最新的

发展情况是笔者一直关注的方向，并将继续关注。

3数据挖掘与教育信息系统的结合

数据挖掘最先应用于金融和商业领域，在教育层面上还只能算是新生事物，

处于发展的初级阶段。国内高校目前在校园信息网中开展数据挖掘的研究并不广

泛，浙江大学使用关联规则发现技术对高校的人事信息库进行挖掘，试图找到影

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程，被信息产业界认为是数据库系统最重要的前沿之一，是信息产业界最有前途的交叉学科。关联规则是数据挖掘中一个重要的研究内容。本文对数据挖掘技术尤其是关联规则挖掘技术进行了系统、深入地分析和研究，并将其投入到实际应用中。主要包括以下一些内容：首先对数据挖掘技术进行了简要的回顾，在提出关联规则挖掘基本概念的基础上，对关联规则挖掘进行了详细地分类、归纳和总结。另对关联规则挖掘技术的国内外研究现状和当前的研究热点进行了归纳和总结，为本文的全面展开奠定了基础。接着重点讨论了...

展开>> 收起<<

关联规则挖掘技术若干问题研究.pdf

共81页,预览9页

还剩页未读，继续阅读

关联规则挖掘技术若干问题研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: