随着高校选课信息系统的规模化运行，系统中存储了大量的数据，而这些数据中隐藏着无法辨别的、可以提供决策支持的信息，但是传统查询、报表工具无法满足挖掘这些信息的需要。

利用数据挖掘技术，挖掘选课系统中积累的有用信息，可以使学校的相关部门有弹性地调节所开的课程，调整热门课程和冷门课程的人数，调节相关课程的学分，通过选课率及相关信息做出正确决策，鼓励和引导学生选择互补的课程，这有利于学生整体素质的提高，也有利于教师、教室等资源的合理分配。

确定数据仓库和OLAP模型

通常要先分析原有业务数据库，确定待建的数据仓库主题。再根据用户的需求来确定各个级别数据仓库的存储主题。这里选取学生选课管理这一典型业务为主题。

为了保证数据的正确性和一致性，还要确保这些数据是按同样的方法记录的同一件事情，需要对选课的原始数据进行预处理，转换成适合数据挖掘的数据。数据预处理（Data preprocessing）包括三个步骤：数据清理（Data cleaning）、数据集成（Data integration）和数据变换（Data transformation）。

完成数据的预处理之后，便可确定待建的数据仓库模型。在选课系统中，我们选取“学生选课表”为基本事实表，度量值为“选课数目”、“选课学分”、“选课率”，选取“学生信息表”、“专业信息表”、“课程信息表”和“教师信息表”四个维度。为了减少数据冗余，这里决定建立“雪花型”数据模型，即该数据仓库以学生选课事实表为中心，学生信息维表、课程信息维表直接与学生选课事实表产生关系，而专业信息维表、教师信息维表则分别与学生信息维表、课程信息维表相关联。

识别了事实数据与维度数据，也设计了雪花结构，接下来就可实现OLAP建模，生成多维数据集（CUBE）。可以建立以ROLAP方式存储的选课数目分析多维数据集（以时间维、学号维、院系专业维为维度，选课数目为度量值）、选课学分分析多维数据集（以课程类别维、课程开课部门维、学号学历维为维度，学分为度量值）等许多个不同的多维数据立方体。

数据挖掘关联算法的实现

关于关联规则的挖掘算法主要有循环式扫描算法、增量式更新算法、并行挖掘算法、元模式制导、基于约束挖掘等等。目前大多数研究集中在频繁数据项的挖掘方法上。其中比较典型的关联规则挖掘算法有Apriori算法和FP-growth算法。

Apriori算法

Apriori算法最早出现，也是使用最广泛的关联规则挖掘算法之一。Apriori算法使用一种称作逐层搜索的迭代方法，k-项集用于搜索(k+l)-项集。首先找出频繁1-项集的集合，记为L1。Ll用于寻找频繁2-项集的集合L2，而L2用于寻找L3，如此下去，直到不能找到频繁k-项集合。找每个Lk都需要扫描数据库一遍。利用Apriori性质（即频繁项集的所有非空子集都必须是频繁的）有助于提高Apriori算法中频繁项集逐层产生的效率。

Apriori算法可以产生相对较小的候选项目集，扫描数据库的次数由最大频繁项目集的项目数决定。因此，该算法适合于最大频繁项目集相对较小的数据集中的关联规则挖掘问题。

FP-growth算法

针对Apriori算法框架的缺陷，Han.JW（韩家炜）等人提出了FP-tree结构和相应的FP-growth算法。FP-growth算法采用的是分而治之的策略，即在经过了第一次扫描之后，把数据库中的频繁集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息。随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关；然后再对这些条件库分别进行挖掘。当原始数据量很大时，也可以结合划分的方法，使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。由于高校多年来存储的选课数据量较大，故选用FP-growth方法实现高校选课系统的关联规则挖掘较合适。

FP-growth算法的实现过程

为了说明FP-growth算法的基本原理和实现过程，我们以“选课率分析多维数据集”为例，选取一些简单的选课事务作为样本进行挖掘，参见表1。其中的每条选课条目记录了电信学院的本科生“某年级、某专业、选的课程名称”。记录中的数据来源于“学生信息维表”中的“年级”属性；“课程信息维表”中的“课程名称”属性；“专业信息维表”中的“专业名称”属性。为了挖掘出强关联规则，进行挖掘之前，需要对属性进行提升，如“年级”中“02”表示本科02级，“03”表示本科03级；“专业名称”中“011”表示“自动化专业”，“013”表示“电信专业”，“015”表示“计算机专业”；“ 课程名称”中“0301”表示“数据挖掘”，“0302”表示“多媒体技术”，“0303”表示“Java程序设计”，“0304”表示“自动化监控”，“0305”表示“计算机网络”。

数据库的第一次扫描与Apriori相同，得到选课频繁1-项集，并得到它们的支持度计数（频繁性）。设最小支持度计数为2。把频繁项的集合按支持度计数的递减顺序排序，结果集记作L，L=[02: 8, 03: 7, 011: 6, 0301: 6, 015: 5, 0303: 5, 0305: 5, 013: 4, 0304: 4, 0302: 3]。

再一次扫描数据库，建立FP-tree。FP-tree的构造如下：创建树的根节点，用“Null”标记。第二次扫描数据库D。每个事务中的项按L中的次序处理（即按递减支持度计数排序），并对每个事务创建一个分枝。例如：第一个事务“001：02，011，0301”按L的次序处理包含三个项{02，011，0301}（恰巧与原次序一致），导致构造树的第一个分枝<（02:1）,（001:1）,（0301:1）>。该分枝有三个节点，其中，02作为根的子女链接，001链接到02，0301链接到001。第二个事务002按L的次序{02，011，0303，0304}，它导致一个分枝，其中，02链接到根，001链接到02，0303链接到001，0304链接到0303。然而该分枝应当与001已存在的路径共享前缀<02>和<011>。这样，我们将节点02的计数增加1、011的计数增加1，即（02:2）、（001:2）。并创建一个新节点（0303:1），链接到（001:2）；再创建一个新节点（0304:1），链接到（0303:1）。

图1 存放在压缩的频繁模式信息的FP-TREE

为了方便树的遍历，创建一个项目表，使得每个项通过一个节点链指向它在树中的出现。扫描所有的事务之后得到的树展示如图1所示，带有相关的节点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP-tree的问题。

使用FP-tree进行挖掘。由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”，由FP-tree中与后缀模式一起出现的前缀路径集组成）。然后，构造它的（条件）FP-tree，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP-tree产生的频繁模式连接实现。具体实现过程如下：

首先考虑0302，它是L中的最后一项，而不是第一项。0302出现在图的FP-tree的三个分枝。（0302的出现容易通过沿它的节点链找到）这些路径由分枝<（02.015.0305.0302:1）>、<（03.011.0304.0302:1）>和<（03.0303.013.0302:1）>形成。这样，考虑0302为后缀，它的三个对应前缀路径是<（02.015.0305:1）>、<（03.011.0304:1）>和<（03.0303.013:1）>，它们形成了0302的条件模式基。它的条件FP-tree只包含单个路径<（03:2）>，不包含其他项，是因为它们的支持度计数为1，小于最小支持度计数2。该路径产生的频繁模式的组合只有一个：（03.0302:2）。

然后考虑L中的倒数第二项0304，它的四个前缀形成条件模式基{（03.011:1）、（02.015:1）、（02.011.0303:1）、（02.011.0301:1）}，产生一个条件FP-tree<02.011:2>，并导出一个频繁模式02.011.0304:2。虽然0302跟在第一个分枝中的011之后，也没有必要在此分析中包含0302，因为涉及0302的频繁模式在0302的考察时已经分析过了。

与以上分析类似，得出其他项中的条件模式基、条件FP-tree和产生的频繁模式。挖掘的过程总结在表2中。

根据以上产生的频繁模式很容易推导出有用的关联规则。表3采用表格的表示方式将数据挖掘的关联规则及相关结果用可视化的形式表示出来。

注释如下（仅限于考察样本——事务数据库D）：

规则A：电信学院的本科“自动化专业”、“02级”学生中50%选“自动化监控”。

规则B：电信学院的本科“计算机专业”、“02级”学生中66.7%选“计算机网络”。

规则C：电信学院的本科“计算机专业”、“03级”学生100%选“数据挖掘”。

（作者单位为东北财经大学职业技术学院计算机教研室）

〉〉〉相关知识介绍

数据挖掘及关联规则挖掘

数据挖掘，又称为数据库中的知识发现（Knowledge Discovery in Database，简称KDD），是指从大型数据库中提取人们感兴趣的信息，提取的知识表示为概念（Concepts）、规则（Rules）、规律（Regularities）、模式（Pattems）等形式。

数据挖掘可以应用于各个领域，包括商务管理、生产控制、市场分析、工程设计和科学探索等。利用数据挖掘可以发现事物发展的趋势，揭示已知的事实，预测未知的结果，并帮助分析完成任务所需的关键因素等。

数据挖掘的目标是寻找模式，根据挖掘模式的类型，目前数据挖掘的研究和应用主要划分为以下几个分支：特征与区分、关联分析、分类与预测、聚类分析、孤立点分析及演变分析等。其中关联分析又称关联规则挖掘，由于其在市场营销、事务分析等领域的成功应用，成为数据挖掘中最重要、最活跃的研究内容。关联规则挖掘可以发现大型数据库或交易数据集中频繁发生的项目子集，并且提取一个项目子集会如何影响已存在的另一个项目子集的规则。

基于数据仓库和OLAP技术的数据挖掘

数据仓库（Data Warehouse，简称DW）之父W.H.Inmon指出数据仓库是面向主题的、集成的、随时间变化的、稳定的数据集合，用于支持管理层的决策制定。而OLAP是基于数据仓库的信息分析处理过程，其基本特点是能够从多种角度对从原始数据中转化出来的信息进行快速、一致、交互地处理，从中获得对数据更深入地了解。数据挖掘和OLAP都属于建立在大型数据库上的数据分析工具，但不一定要在数据仓库的基础上进行。

数据挖掘需要的数据是一些经过净化、集成处理的数据，通常这种预处理过程也是昂贵的，而数据仓库（Data Warehouse）作为OLAP（Online Analytical Process）的数据源，存储的就是这样的数据。它能为OLAP提供数据，当然也可以为数据挖掘提供数据。OLAM（Online Analytical Mining或OLAP Mining）将二者结合起来，发展一种建立在OLAP和数据仓库基础上的新的挖掘技术，它兼有OLAP多维分析的在线性、灵活性和数据挖掘对数据处理的深入性，是数据库应用工具未来发展的方向之一。