关联规则挖掘在学生成绩管理中的应用论文.doc

关联规则挖掘在学生成绩管理中的应用

摘 要

关联规则挖掘用于发现隐藏在大型数据集中的有意义的联系，所发现的联系可以用关联规则或频繁项集的形式表示。目前，关联规则挖掘已经得到了广泛的研究和应用，其中算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。本文针对算法的不足，提出了一种改进算法，并将其应用于挖掘学生成绩，从而对优化课程设置起到一定的指导作用。
论文的主要内容如下：
(1) 对数据挖掘技术进行了概述和归纳，重点介绍了关联规则的基本理论、思想及产生频繁项集和关联规则的相关技术。
(2) 深入研究了算法，并针对该算法的缺陷，提出了一种改进算法。改进算法利用了完美哈希函数，优化的事务压缩技术，分组查询计数和不利用剪枝直接产生候选项集等技术，在一定程度上提升了挖掘频繁项集的效率。同时，通过理论和实验对两种算法进行了性能比较，验证了改进算法的优越性。
(3) 将关联规则挖掘应用于学生成绩管理。在原有的教务管理系统学生成绩管理模块的基础上，应用改进算法，采用作为系统开发工具，设计了一个数据挖掘系统用于挖掘学生成绩中的关联规则。该系统包括获取数据，数据预处理，关联规则挖掘和规则结果分析四个模块。通过挖掘学生成绩，进一步证实了改进算法的有效性和可行性，也为教学管理人员进行课程合理设置提供了决策支持。系统试运行后，优化的课程设置使得教师的教学过程有了明显的改善，教学效果有所提高，学生的课程通过率有所上升。

关键词: 数据挖掘；关联规则；频繁项集；算法；学生成绩

The Application of Association Rules Mining in
Students' Performance Management
Abstract
Association rule mining is used to find the meaningful connections hidden in large data set, and the connections can be expressed by association rules or frequent itemsets. Currently, the association rule mining has been widely studied and applied, of which Apriori algorithm is one of the most influential mining Boolean association rule algorithms of frequent itemsets. Aiming at the shortcomings of Apriori algorithm, this thesis proposes an improved algorithm and applies it to mine student performances, thus plays a certain guiding role in curriculum optimization.
The main contents of this thesis are as follows:
(1)Firstly, it discusses and summaries the data mining technology, and emphasizes the basic concepts and ideas of association rules, and related techniques about frequent itemsets and association rules.
(2)Secondly, it studies the Apriori algorithm thoroughly. And present an improved algorithm aiming at the flaws. The algorithm uses the perfect hash function, optimized affairs compression technology, the grouping inquiry counting and not using the pruning directly to produce candidate k itemsets technology and so on. The improved algorithm enhances the efficiency of mining frequent itemsets to a certain extent. At the same time, it confirms the superiority of the improved algorithm by comparing the two algorithms from theory and experiment aspect.
(3)Finally, it applies the association rules mining to the student performance management. On the foundation of student performance administration module in the original educational administration management system, by applying the improved Apriori algorithm and VB 2010, it designs a data mining system to mine association rule in the student performance. This system includes four modules: the data gain, the data pretreatment, the association rule mining, and the regular result analyzing. Through mining the student performance, it further confirms the validity and the feasibility of improved Apriori algorithm, and also provides decision support for the teaching management to Optimize curriculum. After the operation of the system, the teaching process was improved, the teaching effect was enhanced and the pass rate was increased.
Key words: Data Mining; Association Rules; Frequent Itemsets; Apriori Algorithm; student performance

目 录
第一章 绪论 1
1.1 研究背景 1
1.2 选题的依据和意义 1
1.3 本文的主要内容 2
1.4 本文的组织结构 3
第二章 数据挖掘技术 4
2.1 数据挖掘的起源 4
2.2 数据挖掘的概念 4
2.3 数据挖掘的任务 5
2.4 数据挖掘的过程 5
2.5 数据挖掘的方法 6
2.6 数据挖掘的发展趋势 8
2.7 本章小结 9
第三章 关联规则挖掘技术 10
3.1 关联规则的相关定义和性质 10
3.2 关联规则挖掘问题的形式描述 11
3.3 产生频繁项集和规则的相关技术 11
3.3.1 频繁项集的产生策略 11
3.3.2 规则的产生 18
3.4 关联规则挖掘的方法 18
3.5 关联规则挖掘的研究方向 19
3.6 本章小结 20
第四章 Apriori算法及其改进设计 21
4.1 经典的Apriori算法 21
4.1.1 Apriori算法的基本思想 21
4.1.2 Apriori算法的核心描述和分析 21
4.1.3 Apriori算法中规则的产生 23
4.1.4 Apriori算法的举例演示 24
4.1.5 Apriori算法的特点和缺陷 26
4.1.6 Apriori算法的现有改进技术 26
4.2 一种新的Apriori算法改进设计 27
4.2.1 改进思路 27
4.2.2 Apriori改进算法的描述和实例分析 28
4.2.3 Apriori改进算法的特点和不足 33
4.3 Apriori算法和Apriori改进算法的性能比较 34
4.3.1 性能分析 34
4.3.2 实验分析 35
4.4 本章小结 36
第五章 Apriori改进算法在学生成绩管理中的应用 37
5.1 关联规则挖掘过程 37
5.2 关联规则挖掘在学生成绩管理中的应用 38
5.2.1 问题定义 38
5.2.2 数据准备 38
5.2.3 建立数据挖掘模型 40
5.2.4 关联规则的解释和评估 45
5.3 本章小结 45
第六章 总结与展望 46
6.1 论文总结 46
6.2 展望 46
参考文献 48
攻读硕士学位期间公开发表的论文 51

插图清单
图3- 1费力策略示意图 12
图3- 2基于支持度的剪枝策略的实例 13
图3- 3 FP-growth算法伪代码 14
图3- 4 FP-growth算法挖掘流程第一步 15
图3- 5根据表3-1构建的FP-tree 16
图4- 1利用Apriori算法产生频繁项集的伪代码 22
图4- 2 apriori-gen()函数产生候选项集的伪代码 23
图4- 3 Apriori算法中规则产生的伪代码 24
图4- 4 Apriori算法寻找D中频繁项集的过程 25
图4- 5利用完美哈希函数挖掘L2 30
图4- 6利用L2压缩原始数据库D 31
图4- 7 Apriori改进算法的数据流程图 33
图4- 8不同支持度下的两种算法效率比较(5000条样本数据） 35
图4- 9不同样本数据下的两种算法效率比较(min_sup=0.3%） 36
图5- 1关联规则挖掘过程示意图 37
图5- 2学生成绩数据挖掘系统模型 41
图5- 3学生成绩数据挖掘系统挖掘流程图 41
图5- 4学生成绩数据挖掘系统主界面 42
图5- 5获取数据模块界面 42
图5- 6获取挖掘数据成功的界面 43
图5- 7关联规则挖掘模块的界面 43
图5- 8规则结果分析模块的界面 44
图5- 9学生成绩数据挖掘系统应用前后效果对比图 45

表格清单
表3- 1 事务数据库D 15
表3- 2 按结果集L中的次序处理D中的每个事务的项 15
表3- 3 挖掘图3-4的FP-tree的结果 17
表4- 1 原始事务数据库D 24
表4- 2 中所有2-项集对应的地址表 29
表4- 3 分组表(3) 32
表4- 4 分组表(4) 32
表5- 1 学生成绩表表结构 39
表5- 2 预处理后的学生成绩表表结构 40

第一章 绪论
1.1 研究背景
面临着社会各个领域积累的大量数据，如何从中获取有价值的新发现，目前已成为不同学科的研究者的主要研究方向。虽然录入、查询和统计数据都通过数据库管理系统完成，但是数据中存在的关系和规则却不能发现，也没办法预测未来的发展趋势。在这样的情况下，一个多学科交叉的学问产生了，它就是数据挖掘，它是一个从数据源中找到有用的、有潜在价值知识的过程。
关联规则是数据挖掘领域中被广泛研究的比较重要的模型，对它的挖掘是为了找到数据中蕴涵的重要规律。最早应用于解决销售交易数据库中数据项之间联系的发现问题，也就是从大量收集和存储的消费者消费行为的信息中发现有趣的关联关系，从而了解消费者的购买行为，然后利用这个宝贵的信息优势，支持多种业务应用，市场营销成本大幅节省，营销效率明显提高，又带来了丰厚的利润，进一步促使许多业界人士对其产生极大的兴趣和研究热情。目前，关联规则挖掘不但在关联分析的概念上得到了深入研究，而且在实现和应用问题上也取得了长足的发展。
教育信息的挖掘很少应用，特别是挖掘学生的成绩来获得教学策略的支持。面对日益增加的学生人数，用于管理学生信息的教务管理系统中积累了大量的学生信息，而这些信息我们却只是进行简单的查询和报表统计输出，因此如何从这些数据中获取隐藏其中的规律或规则，并利用其进行教学策略支持，就很重要了。
1.2 选题的依据和意义
关联规则挖掘首先是由等人提出，用来发现购物篮数据事务中各项之间的有趣联系，并且提出了挖掘关联规则的算法。[1]从此以后，对关联规则的理论、实现和应用问题的研究就更加广泛了。理论上，大多数关联规则挖掘任务被分解为产生频繁项集和强规则两个子任务，而频繁项集产生的计算开销远大于强规则的产生，所以提高频繁项集的产生效率关系着关联规则算法的总体性能。[12]目前，已经研究了很多提高算法效率的技术，目的主要是解决算法存在的不足。例如，等提出的算法、等提出的划分算法、提出的基于抽样的频繁项集产生算法和等人提出的动态项集计数算法等。另外，等还提出了一种不同于以上改进技术的算法，它是一种不产生候选从而挖掘全部频繁项集的方法。
本文在以上改进技术的基础上提出了一种改进算法。该算法利用完美哈希函数，优化的事务压缩技术，分组查询计数和不利用剪枝直接产生候选项集等技术，一定程度上提高了挖掘频繁项集的效率。对于两种算法，利用同一个实例，从理论和实验两个方面比较它们的性能，发现了改进算法的优越性。
目前关联规则挖掘已经应用到了各个领域，比如生物信息学、地球科学、文档分析、通信警告分析和挖掘等领域，同时也应用于分类、回归和聚类等其他学习问题。但是在教育信息领域却需要更进一步的探索和研究，将数据挖掘技术应用于教育信息领域，从大量的教育信息数据中发现隐藏的、有用的知识，进而促进教育的改革和发展。
随着数据库技术的发展，国内很多学校在处理日益增长的数据时，都选择了教务管理系统，但仅限于将纸质信息输入到计算机中，计算机进行统计查询等日常管理工作，所以急需利用数据挖掘技术从这些数据中获取隐藏其中的规律或规则，从而帮助人们做出决策和研究。目前，笔者所在学校淮北广播电视大学正是利用教务管理系统进行学生信息的管理，可以处理学籍、成绩和考务等方面的数据。以成绩管理模块为例，教务管理系统仅提供简单的数据查询和报表输出的功能，基本上没有智能分析的功能，因此需要在此系统的基础上添加智能分析的功能。本文应用改进算法，采用作为系统开发工具，作为数据库服务器设计开发了一个简单的数据挖掘系统用于挖掘学生成绩中的关联规则，以后再考虑添加其他模块。通过挖掘学生成绩，进一步证实了改进算法的有效性和可行性，也为教学管理人员优化课程设置提供了决策支持。系统试运行后，优化的课程设置使得教师的教学过程有了明显的改善，教学效果明显提高，学生的课程通过率有所上升。
1.3 本文的主要内容
本文从理论上研究了数据挖掘和关联规则挖掘，深入分析了算法，并在此基础上，提出了一种改进算法，最后将其应用于数据挖掘系统挖掘学生成绩数据。
本文的主要内容如下：
(1) 对数据挖掘和关联规则挖掘进行理论研究。数据挖掘是知识发现过程不可或缺的一部份，而关联规则挖掘是数据挖掘中的重要研究领域。因此，本文着重研究和探索了关联规则挖掘的过程，并详细介绍了频繁项集的产生技术。
(2) 研究分析了算法。主要介绍了算法的基本思想，描述和分析了算法的核心，即通过连接和剪枝产生频繁项集，并简要介绍了关联规则的产生。通过实例演示了算法产生频繁项集的整个过程，分析了算法的特点和不足，同时介绍了现有的改进技术。
(3) 算法的改进设计。基于算法的缺陷，改进算法利用完美哈希函数，优化的事务压缩技术，分组查询计数和不利用剪枝直接产生候选项集等技术，一定程度上提升了挖掘频繁项集的效率。同时，通过理论和实验对两种算法进行了产生频繁项集的时间效率比较，验证了改进算法的优越性。
(4) 学生成绩数据挖掘系统的设计与实现。目前，教务管理系统中的学生成绩管理模块无法进行智能分析处理，所以利用改进算法开发一个简单的学生成绩数据挖掘系统用于挖掘学生成绩数据。将挖掘结果提供给教学管理人员进行课程合理设置，改善了教学过程和教学效果。
1.4 本文的组织结构
本文共分六个章节，以基本理论为基础，进行算法改进，并设计实现了数据挖掘系统应用于学生成绩管理。本文的组织结构安排如下：
第一章 绪论。先后介绍了论文研究的背景、选题的依据及意义以及本文的主要内容和组织结构。
第二章 数据挖掘技术。先后介绍了数据挖掘的起源、基本概念、任务、过程和方法以及研究的发展趋势。
第三章 关联规则挖掘技术。主要介绍了关联规则的相关定义和性质，并形式化描述了关联规则的挖掘问题，包括频繁项集和强规则的产生。然后详细介绍了产生频繁项集的相关技术，简要介绍了规则的产生技术。最后，对于关联规则挖掘的方法做了简单介绍并提出研究方向。
第四章算法及其改进设计。首先分析了经典的算法，包括算法的基本思想和核心，并通过实例分析了算法的特点和不足，同时介绍了现有的改进技术。接着提出了一种改进的算法，并详细的介绍了改进算法的思路、描述和实例分析，总结出了改进算法的特点和不足。最后，在性能和实验分析方面，对两种算法进行了算法效率比较。
第五章改进算法在学生成绩管理中的应用。介绍了关联规则挖掘的基本流程，接着将关联规则挖掘应用于学生成绩管理。首先进行了问题定义，数据准备，然后应用改进算法实现了一个简单的学生成绩数据挖掘系统。介绍了该系统获取数据，数据预处理，关联规则挖掘和规则结果分析四个模块的设计与实现，最后对系统挖掘结果进行了解释和评估。
第六章 本文的总结与展望。对本文所做的工作进行总结，并对今后的工作提出了研究方向。

第二章 数据挖掘技术
目前，人们面临着这样一个巨大的挑战，那就是怎样从海量的数据中提取有用的信息，而这些信息来自于社会各个单位部门长年累月积累下来的数据。日益收集和存储下来的数据各具特点，坚持用传统的数据分析工具和技术已解决不了问题，而急需一种新的技术能够将处理海量数据的复杂算法融合到已有技术当中，而这种技术就是数据挖掘。
2.1 数据挖掘的起源
面临着来自商务管理、医学、分子生物学、科学与工程技术界等方面积累的大量数据，如何从中获取有价值的新发现，目前已成为不同学科的研究者迎接的一项新挑战。数据挖掘恰恰提供了这样的机会，它可以更有效地处理不同的数据类型，无论是探查分析新的数据类型，还是利用新方法分析旧有的数据类型，都是建立在研究者先前使用的算法和方法学的基础上。
数据挖掘是信息产业最有前途的交叉学科，它将信息论、可视化、信息检索和进化计算等各个领域的思想融合其中，应用于模式识别、人工智能和机器学习的建模技术和搜索算法等学习理论。同时，数据挖掘在一些领域起到至关重要的作用，比如，需要数据库系统提供有效的存储、索引和查询处理支持的领域，利用分布式技术处理不能在一起集中处理的数据的领域等。正是由于传统的数据分析技术在面临新的数据集带来的可伸缩性、高维性、异种数据和复杂数据、数据的所有权与分布以及非传统分析等方面的问题，才有数据挖掘的出现。
2.2 数据挖掘的概念
数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。[1]广义上，数据挖掘是在大量数据中挖掘有用信息的过程，但并非所有的信息发现过程都视为数据挖掘，比如，通过数据库管理系统进行简单的查询、调用和即时遍历或通过的搜索引擎查找网页等，这些信息检索的方式主要是依赖数据的显著特征来创建索引结构，只能是信息检索领域的工作。
知识发现是将未加工的数据转换为有用信息的整个过程，包括数据预处理 (包括特征选择、维规约、规范化、选择数据子集)到数据挖掘，再到数据挖掘结果的后处理 (包括模式过滤、可视化和模式表示)，而数据挖掘只是其中的一个步骤，但却不可或缺。[2]
2.3 数据挖掘的任务
预测和描述是数据挖掘的两大任务，前者根据其他属性的值来预测特定属性的值，而后者是导出概括数据中潜在联系的模式。
下面简单地介绍四种主要的数据挖掘任务：
(1) 预测建模
预测建模通过说明变量函数的方式，决定目标变量属于哪种类别，如果预测的目标变量是离散的，这种就归为分类；若预测的变量是连续的，这种就归为回归，但是相同的目标是使预测值与实际值之间的误差达到最小。决策树、基于统计学的贝叶斯方法和神经网络方法是预测建模的主要方法。
(2) 关联分析
关联分析是这样一种方法，它的目的是发现数据中强关联特征的模式，从而得到有实用价值的信息。[13]它主要应用于购物篮分析得到新的交叉销售商机，除此之外，还被应用于科学数据分析、生物信息学和医疗诊断等领域。
(3) 聚类分析
俗话说物以类聚，聚类用于发现数据库中紧密相关的数据并组成不同的组，使得同一簇中的数据相互之间尽可能的相似。它主要应用于对相关的顾客分组、压缩数据等。
(4) 异常检测
识别数据的特征明显不同于其他数据的观测值是异常检测的目的，同时要避免标注正常的数据为异常点，这种检测手段经常被应用于避免网络被攻击、检测是否是欺诈行为和生态系统扰动等。
2.4 数据挖掘的过程
数据挖掘的过程大致可以用定义问题、数据的准备、建模和解释、评估结果来概括。
(1)定义问题。 主要是熟悉实际的业务背景情况，确定要挖掘什么和要得到什么结果。在开始数据挖掘之前，需要弄清用户需求，明确挖掘对象和目标，从而为挖掘准备优质的数据，才能够正确的解释和评估结果，进而挖掘出有价值的信息。
(2)准备数据。确定了要挖掘的对象，还需要进行数据预处理。原始数据必须加以处理才能提高数据的质量并且更好的适应特定的数据挖掘技术或工具，即数据预处理。
(3)建模即执行挖掘算法并建立模型。在前两步的基础上，我们要选择合适的挖掘算法。在选择时要考虑到用户的需求，是要得到描述型而又容易理解的准确概要性的知识，还是要满足预测率高的分类规则，却不在乎是否容易接受等各种各样的要求，所以算法选的合不合适，关系到分析数据的结果是否满足要求。
(4) 解释和评估结果。对挖掘得到的关联规则进行解释和评估，并将分析得到的有用知识应用到实际应用中，以便做出决策。
可见，数据挖掘的过程需要反复进行，使得挖掘出的信息不断接近问题的本质，从而做出更加正确的决策。
2.5 数据挖掘的方法
面对不同的数据挖掘任务，一种方法往往不能全部解决，而需要将多种方法相结合，取长补短。常用的主要有以下几种：
(1) 关联分析方法
关联分析方法主要用于发现隐藏在大型数据集中的不同事件之间的有意义的关联性，即一个事件发生的同时，另一个事件也经常发生。它的主要依据是事件发生的概率和条件概率应符合一定的统计意义，重点在于快速发现那些有实用价值的关联发生的事件。通过关联分析所得到的结果，仅仅是一种可能的因果关系，它能够协助业务专家分析事物的本质，深化对事物关系的认识，但需要业务专家加以确认，并予以合理的解释，才能够成为对决策进行指导的规律。挖掘频繁项集经常被使用的是算法和算法，其他还包括、、、等算法以及树投影算法和。另外还有基于约束的关联规则算法，挖掘关联模式的并行算法，基于模式定秩、汇总和模式过滤方法以及主观度量在关联分析中的应用等。
(2) 分类分析方法
① 有这样一种分类法，在选择划分数据的属性时，它采取一系列局部最优决策来构造决策树，从而能够在合理的时间内构造出具有一定准确率的次最优决策树。决策树归纳算法主要有以下特点，它是一种构造分类模型的非参数方法，即使训练集非常大，也可以快速建立模型，对于噪声的干扰具有较好的鲁棒性等。一些著名的决策树算法包括都采用熵度量作为划分函数的和算法以及使用指标作为划分函数的算法，还有在决策树生长过程中使用统计检验确定最佳的划分点的算法。斜决策树和构造归纳方法是用来提高决策树表达能力的。除自顶向下方法外，其他生长决策树的策略还有自底向上的方法和双向的方法。另外还有开发决策树归纳算法的并行和可伸缩算法，包括等的、等的等。
② 基于规则分类器分类方法是从包含多个类的数据集中一次提取一个类的规则，归纳分类规则采用顺序覆盖算法，其他算法还有、等。
③ 人工神经网络是由一组相互连接的结点和有向链构成，用来解决分类问题。它的特点是至少含有一个隐藏层的多层神经网络是可以用来近似任何目标函数，可以处理冗余特征，对训练数据中的噪声很敏感，权值学习使用的梯度下降方法经常会收敛到局部极小值，并且训练是一个很耗时的过程，尤其当隐藏结点数量很大的情况下。
④ 支持向量机是使用训练实例的一个子集来表示决策边界并且具有坚实的统计学理论基础和应用性的一种分类技术。
⑤ 贝叶斯分类器：通过朴素贝叶斯和贝叶斯信念网络实现，前者面对孤立的噪声点和无关属性时是健壮的，并且相关属性可能会降低朴素贝叶斯分类器的性能，因为对于这些属性，条件独立的假设已不成立，但它在文本分类等应用领域的性能相当好。对于后者，用图形表示一组随机变量之间的概率关系，不要求给定类的所有属性都条件独立，而是允许指定哪些属性条件独立。
除了以上分类方法以外，还有由训练数据构建一组基分类器，然后通过对每个基分类器的预测进行投票来进行分类的组合方法，代表算法有、自适应再抽样和组合算法等。当然还有遗传算法、基于案例的推理分类法、粗糙集和模糊集等很多其他的分类方法。
(3) 聚类分析方法
人们已经在各个领域开发了大量聚类算法以解决不同的应用类型的需求。
① 基于原型的聚类：在簇中的任何对象离定义该簇的原型比离定义其他簇的原型更近。使用簇中对象的质心作为簇的原型的均值算法是最常用的。另外还有三种聚类算法是对基于原型的聚类的扩展，它们分别是模糊均值算法，它采用模糊逻辑和模糊集合论的概念提出聚类策略；混合模型聚类即簇集合可以用一个混合分布建模，每个分布对应一个簇，代表算法是期望最大化算法；基于自组织映射的聚类方法是在一个要求簇具有预先指定的相互关系的框架内进行聚类，代表的算法是算法。
② 基于密度的聚类：最常见的是寻找高密度区域，并且是被低密度区域分离的算法。为解决有效性、发现子空间中的簇和更准确的密度建模等问题，三种基于密度的聚类算法被提出，第一种是将数据空间划分为网格单元，再由足够稠密的网格单元形成簇的基于网格的聚类，代表算法有、和等。第二种是子空间聚类，它是在所有维的子空间中寻找簇（稠密区域），算法是系统地发现子空间簇的基于网格的聚类算法。第三种是使用核密度函数用个体数据对象影响之和对密度建模的聚类技术，如算法。
③ 基于图的聚类算法。代表算法是和算法，它们都是基于邻近度图的稀疏化进行聚类的算法。另外还有算法，它是一种使用自相似性概念确定簇是否应当合并的层次聚类算法；基于共享的最近邻相似性度量的聚类算法和基于密度的聚类算法。
④ 可伸缩的聚类算法。代表算法是，它能够处理大型数据、离群点和具有非球形和非均匀大小的簇的数据。算法用于欧几里得向量空间数据，即平均值有意义的数据。
确定合适的聚类算法，需要考虑很多因素，比如聚类的类型、簇的类型和特性、簇描述、数据集和属性的特性、噪声和离群点、数据对象的个数、属性的个数和算法的考虑等，但是没有一种算法能够适应所有的数据类型、簇和应用，所以进一步开发的空间很大。
2.6 数据挖掘的发展趋势
由于数据挖掘任务和数据挖掘方法的多样性，以及数据挖掘新的应用的不断出现，数据挖掘面临着更多更新的挑战。面对这些挑战，我们将如何应对，这也是我们研究数据挖掘的焦点问题。
(1) 保护隐私的数据挖掘，即为挖掘加密数据或随机数据而开发的技术。在电子商务和卫生保健领域，人们越来越关注数据挖掘破坏隐私的问题，导致人们对研究保护用户隐私的数据挖掘算法的兴趣膨胀。
(2) 流数据挖掘。随着快速产生连续的数据流的应用的逐步增加，比如，网络通信流、多媒体流和股票价格等的应用，流数据挖掘必须考虑一些因素，如可用内存有限、需要联机分析和数据随时间改变等因素。
(3) 数据挖掘语言的标准化。在改进多个数据挖掘系统和功能间的互操作、数据挖掘的系统化开发以及数据挖掘系统在社会和企业中的教育和使用等方面，标准化的数据挖掘语言起到极大的促进作用。
(4) 可视化数据挖掘。[2]它使用户充分理解知识发现的过程，从而有助于数据挖掘作为数据分析的基本工具，更加有利于人机交互。
(5) 可伸缩的数据挖掘方法，主要用于解决单独的和集成的数据挖掘功能。
(6) 复杂数据类型挖掘的新方法。对非结构化数据的研究处理，如多媒体数据、视频图像数据以及文本数据等，需要我们将现存的数据分析技术和数据挖掘方法集成起来研究新的方法。
(7) 挖掘。由于上不断更新和增加的信息，有关内容挖掘、结构挖掘、日志挖掘以及因特网上个性化的数据挖掘服务，将成为一个日益重要的研究领域。
2.7 本章小结
本章主要介绍了数据挖掘的起源，数据挖掘的基本概念，数据挖掘的任务、过程和方法，并简要介绍了数据挖掘研究的发展趋势。

第三章 关联规则挖掘技术
关联规则挖掘解决的典型问题是发现销售交易的数据库中数据项之间的重要关联性，即在一个交易中出现某些数据项蕴涵着在同一交易中可能也会出现其他一些数据项。以前，销售者不区分消费者的特征，直接进行营销，现在可以利用收集和存储的消费信息进行挖掘，从而得到支持各种商务应用的实用信息，达到节约营销成本，提高销售效果，取得高额利润的目的,因此许多业界人士对关联规则的挖掘产生了极大的兴趣和研究的热情。
3.1 关联规则的相关定义和性质
定义3.1：令是所有项的集合，而是所有事务的集合。用标识每个事务，事务的宽度定义为事务中出现项的个数。每个事务包含的项集都是的子集。项集被定义为含个项或不含项的集合，分别称项集或空集。
定义3.2：包含特定项集的事务个数，被称为支持度计数。数学上用表示项集X的支持度计数，其中，符号|•|表示集合中元素的个数。那么。
定义 3.3：用 ()表示关联规则,用它的支持度和置信度来度量其强度。[15]
定义3.4：数据集的频繁程度用支持度度量，对于，。数据集需满足的最小支持度阈值被称为最小支持度，简记为。
定义3.5：在包含的事务中出现的频繁程度用置信度度量，对于，。关联规则必须满足的最小可信度被称为最小置信度，简记为。
我们通常在表示支持度和置信度时，不用0到1之间的值，而是用0%到100%之间的值。
定义3.6：强关联规则必须同时满足和。
定义3.7：给定，如果项集为频繁项集，则需满足。
性质 3.1： 已知数据集D中两个不同的项集X和Y，如果，那么。
性质 3.2： 频繁项目集的子集也是频繁的。[14]
证明：已知频繁项目集Y，即，对于，由性质3.1，可知，可得项目集X也是频繁的。
性质 3.3：非频繁项目集的超集也一定是非频繁的。[14]
证明：已知非频繁项目集X，即，对于X的每个超集Y，由性质3.1，可知，可得项目集Y也是非频繁的。
3.2 关联规则挖掘问题的形式描述
对于给定事务T，找到其强规则的过程被称为关联规则挖掘。对于每个可能的规则，我们都计算它的支持度和置信度，显然这个做法十分费力且代价大，毕竟规则是呈指数级从数据集中提取出来。如果规则是从包含m个项的数据集中提取，那总数将达到，当时，R=。使用和，80%以上的规则将被丢弃，显然大部分的计算是无用的开销，所以我们有必要事先对规则进行剪枝。
第一步就是拆分支持度和置信度要求来提高性能。由支持度(s)的公式可得出，规则的支持度仅依赖于其对应项集。例如，有下面6个规则：，，，，，，它们涉及的项都源自同一个项集，所以它们有相同的支持度，假如是非频繁的，那么就可以立即剪掉这6个候选规则，而没有必要计算它们的置信度值。
大多数关联规则挖掘任务被分解为产生频繁项集和强规则两个子任务，前者就是发现满足的所有项集，后者则是在前者的基础上提取所有高置信度的规则。前者计算开销远大于后者，所以提高频繁项集的产生效率关系着关联规则算法的总体性能。
3.3 产生频繁项集和规则的相关技术
3.3.1 频繁项集的产生策略
(1) 费力策略
费力策略是指对于格结构中每个候选项集的支持度进行计数。其中，格结构常用来枚举所有可能的项集，通常一个项集可能产生个频繁项集，不包括空集在内。通常值非常大，也就是说将面临呈指数增长的项集搜索空间。
这种费力策略体现在必须比较每个候选项集与每个事务，遇到候选项集包含在事务中，就增加它的支持度计数。[16]
例 3.1 已知事务数据库，，并按字典次序存放事务中的项。
使用费力策略寻找中的频繁项集，将需要进行次比较来产生候选项集的支持度，其中，代表事务数，是事务的最大宽度，是候选项集数。从图3-1中可以看到，对于项集，它在事务1，4，5中都出现了，意味着其支持度计数要增加3次。解决费力策略计算复杂度高的问题，可以采用减少候选项集的数目和减少比较次数的方法。

图3- 1费力策略示意图

(2) 基于支持度的剪枝(support-based pruning)策略
这个策略主要帮助减少频繁项集产生时需要探查的候选项集个数，主要使用支持度度量对候选项集进行有效地剪枝，主要依据的是性质3.1,3.2和3.3。
对于图 3-1所示的事务，假定最小支持度计数是3，应用算法来验证基于支持度的剪枝策略大大降低了产生频繁项集的计算复杂度。
图3-2给出了算法产生频繁项集的一个高层实例。假设=60%。初始时每个项都被看作是候选项集，当给每个项计数支持度时，发现和的支持度计数均小于3，故被删除。算法在只有4个频繁项集的情况下，产生了个候选项集。对其进行计数后发现和均小于3，因此被删除。然后在仅有4个频繁项集的情况下，产生了1个候选项集，其计数是3，因此保留。
通过实例，降低产生频繁项集计算复杂度具体表现在，在枚举所有项集到项集的方法中将产生个候选，而使用时，将减少为个候选，数目降低了68.29%。实际应用中数据集将更大，那么利用剪枝策略的有效性将更显著。

扫描D，对每个候选计数
项集
{ I1 ,I2 }
{ I1 ,I3 }
{ I1 ,I4 }
{ I2, I3 }
{ I2 ,I4 }
{ I3 ,I4 }
支持度计 数
4
4
5
3
1
2
删除候选支持度计数小于最小支持度计数的项集
C1
项集
I1
I2
I3
I4
支持度计 数
4
4
5
3
L1
由L1 产生候选C2 ，并对每个候选计数
项集
I1
I2
I3
I4
I5
I6
C2
支持度计 数
3
4
2
4
2
3
删除候选支持度计数小于最小支持度计数的项集
项集
{ I1 ,I2 }
{ I1 ,I3 }
{ I2, I3 }
{ I3 ,I4 }
支持度计 数
3
4
4
3
L2
由L2 产生候选C3 ，并对每个候选计数
项集
{ I1 ,I2,I3 }
支持度计 数
3
C3
项集
{ I1 ,I2,I3 }
支持度计 数
3
L3