汪 丽，张 露

(1.武汉理工大学统战部，湖北 武汉 430070;2.武汉理工大学计算机科学与技术学院，湖北 武汉 430070)

随着网络和计算机技术的快速发展，信息也在爆炸式地增长并呈现出海量、多样、异构、动态变化等特性[1]。分布式计算平台的出现解决了海量数据的存储和计算的瓶颈问题，使海量数据的数据挖掘成为可能。将分布式与现有数据挖掘算法相结合，已成为研究的热点[2]。

而随着信息化建设的深入发展，高校都拥有大量的教育信息，其分布范围在地理上越来越广泛，数据结构呈现多样化的趋势，使传统的数据挖掘也不再适用[3]。针对Apriori算法进行改进，提出了一种分布式的关联数据挖掘算法，利用MapReduce模型对算法进行实现，并将改进的关联规则算法应用于分布式教育决策支持系统中。

1 关联规则挖掘算法及其分布式改进

1.1 关联规则挖掘算法

从广义上讲，数据挖掘的本质即关联分析。数据挖掘的目的是挖掘出潜藏在大量数据背后的有用知识，这种知识所反映的必然是不同对象不同属性之间的关联[4－5]。

在众多的关联规则算法中，最著名的是1993年AGRAWAL等提出的Apriori算法及其改进算法[6－7]。尽管后来又有科研工作者提出了许多关联规则挖掘算法，但Apriori算法仍是许多新算法的原型，很多算法都是基于Apriori算法的改进。

可将Apriori算法描述如下:

输入为事务数据库D;最小支持度阈值Smin。

输出为D中的频繁项集L。

步骤为:①根据原事务集产生频繁1项集L1;②根据频繁k项集产生第k+1层候选集;③扫描事务集，找出第k+1层频繁集;④循环步骤②和步骤③，直到第k+1层频繁集为空。

Apriori算法的优点是结构简单，易于理解，没有复杂的推导。但同时该算法也存在两个主要缺点:①多次重复扫描数据库和产生大量候选频繁项集。在实际应用中，多次重复扫描数据库在需要挖掘很长的模式时将带来巨大开销;②在迭代过程中要在内存中产生、处理和保存候选频繁项集，这个数量有时候是非常大的，会导致算法在广度和深度上的适应性很差。

1.2 分布式Apriori算法设计

MapReduce模型是Google开发的一个针对大规模群组海量数据处理的分布式编程模型，它将运行于大规模集群上复杂的并行计算过程高度地抽象成两个函数:Map和Reduce[8]。在实现上将并行化、容错、数据分布和负载均衡等细节隐藏起来，然后把整个分布式过程看作由Map/Reduce来表达的一个类函数过程。Map阶段，Map/Re－duce模型将输入的数据集合拆分为若干数据片段，并将每一个数据片段对应分配给一个Map任务，每一个Map任务对应分配给集群中运行的某一个块服务器。每一个Map任务对其分配到的键/值对(K，V)调用用户自定义的Map函数进行计算后，生成相应的中间结果键/值对集合M{(K1，V1)，(K2，V2)，…，(Ki，Vi)}。Map/Reduce模型会将中间结果键/值对集合M{(K1，V1)，(K2，V2)，…，(Ki，Vi)}进行排序产生一个新的二元组(K'，V'*)集合，新集合中所有对应键的相同值被归类在一起，同时二元组集合也会被划分出与Reduce任务数量相同的片段数。Reduce阶段，二元组(K'，V'*)集合的片段将作为每一个Reduce任务的输入，经过一个用户定义的Reduce函数处理后生成一个输出的键/值对(K，V)。Map/Reduce框架最后会再一次将集群中所有节点上的Reduce任务生成结果进行分发处理，形成最终输出结果集合。

将原Apriori算法转换为MapReduce实现，其重点就是找出原方法中的关键数据，将这些数据映射为MapReduce的key值和value值。Apriori算法在事务集扫描的过程中，其本质是词语计数的过程，核心是对项集进行统计，故选取项集作为该阶段的key值，value为1，则把事务数据库水平均匀地分成规模相当的n个数据子集，对n个数据子集进行格式化，格式化后的记录集为＜tid1，list1＞，＜ tid2，list2＞，…，＜ tidn，listn＞，产生＜key1，value1＞对，Map函数对输入的数据子集的每个记录＜tidi，listi＞进行扫描，产生一个局部候选项集的集合C，生成并输出中间＜key2，value2＞对，每个候选项集的 value为1，故集合C记作{ ＜itemset1，1 ＞，＜ itemset2，1＞，…，＜ itemsetn，1 ＞}。

当数据库很大，划分后的每个数据子集中事务对应的列表相近时，Map函数产生的中间key2值的数据大量重复，如果将这些数据通过网络发送到指定的Reduce函数，将会耗费网络资源，增加延迟，降低I/O性能，可以在Map阶段增加一个Combine类调用的Combine()函数，这样映射过程所产生的中间结果键/值对，不会马上写到输出，而会被收集到列表中，每个键/值对对应一个列表，当缓冲区内的键/值对达到一定数量时，缓冲区内数据会被清空转移到Combine类的Reduce方法中，最后每个键与对应的值列表以键/值对的形式映射输出。以Map阶段所产生的＜key2，value2＞对作为输入，将Map函数输出进行一次合并，得到的新 ＜key2，value2＞为 ＜itemseti，S＞，其中 S表示itemseti在数据子集中的支持度计数，然后利用分区公式(1)，将Combine()函数产生的中间键/值对分成m个不同的分区，将每个分区分配给指定的Reduce函数。

其中:key为中间键值;M为分区数目;参数m1，m2，…，mn为 n项集中的项在事务数据库的项集中的序数，默认为按照字典顺序排序的。

执行Reduce函数的节点读取Combine()函数提交的数据 ＜itemseti，Si＞，同一个 Reduce函数会映射很多不同的候选项集，对itemsetikey值进行排序，将具有相同候选项集的数据聚合在一起，形成＜itemseti，list(Si)＞，遍历所有中间数据后，将 ＜itemseti，list(Si)＞传递给 Reduce函数。Reduce函数把相同itemseti的支持度进行累加，就得到该候选项集在整个事务数据库中的实际支持度计数，即S=S1+S2+…，与最小支持度计数Smin相比较，确定局部频繁项集的集合L'，比较之后的m个Reduce函数的输出项集合并就得到最终的频繁项集的集合L。

与原算法相比，改进的Apriori算法的优点在于只需要对整个数据库扫描一次，即可得到所有频繁项集的集合，可极大地提高算法的执行效率。

2 算法的仿真实验与分析

选择10台硬件配置不完全相同的PC机，使用一台服务器作为NameNode，设定为JobTracker角色，其他 9台 PC机作为 DataNode，即 Task－Tracker，实验环境架构如图1所示。

图1 实验环境架构图

运行MapReduce模型，由Master控制整个运行环境的进程调度和资源调度，将作业分配给多个相互独立的处理器进行处理，每个处理器处理数据的过程都是一样的。在算法运行的同时创建Map任务子进程和Reduce任务子进程，Map任务子进程唤醒Mapper对输入数据进行处理并唤醒Combine()函数来合成Map函数处理后的数据集，Reduce任务子进程唤醒 Reducer来执行Reduce操作。

实验数据采用IBM的奎斯特合成数据产生器产生关联规则挖掘对象实验数据，实验使用的数据库设为T30.I10.N200K.D200K，其中T30表示每个事务平均包含30项，I10表示频繁项集的平均长度为10，N200K表示项总数为200 000，D200K表示事务总数为200 000。

不同节点数目下，Apriori算法和改进的Apriori算法执行时间对比如图2所示。从图2中可以看出，当只有一个可利用节点时，两种算法的时间性能基本一样，但随着节点数目的增多，改进算法比原算法执行时间要短，并且这种优势随着节点数目的增加而扩大，说明在异构集群环境下，MapReduce模型的Apriori算法能够提高关联规则挖掘的执行效率。

图2 两种Apriori算法时间性能对比图

3 在教育决策支持系统中的应用

建立先进的教育评估系统，对发展教育，保障培养质量尤为重要[9]。随着评估工作的不断深入，目标越来越复杂，数据量越来越多，分布的范围也越来越广泛，数据结构呈现出多样化的趋势，因此研究基于分布式的关联数据挖掘算法在教育决策支持系统开发中的应用是一个很好的尝试。

从教学质量评价系统数据库中抽取基本表，如总体评价结果表、教师表、系所表;从师资管理系统数据库中抽取基本表，如教师表、职称代码表、系所表。

在教学质量评价系统和师资管理系统中均有对教师基本数据的定义，要将两个表的数据进行数据集成，集成后的表结构为教师表(教师号，教师名，性别，年龄，系所名，职称，学历)。根据学生对教师评教的数据，还需要从教师档案中获取相关教师的其他属性，在进行评价处理之前需要去掉一些孤立点数据，得到教学评价信息表(教师号，教师名，性别，年龄，系所名，职称，学历，评价分数)。

记录中的字段值采用代码表，如表1所示，并将其转换为相应的事务。

表1 代码表

使用所述的改进算法进行关联规则挖掘需要两个参数:支持度和置信度，支持度是规则X－Y在交易数据库中包含X和Y的交易数与所有交易数之比，置信度是包含X和Y的交易数与包含X的交易数之比，通过挖掘一共产生了30条关联规则，其中部分关联规则如表2所示。

第一条规则C3≥D2转换为职称=副教授≥学历=硕士，支持度22.3%表明，在教师档案数据库有22.3%的记录是职称为副教授且学历为硕士;而置信度71.7%表明，71.7%的副教授具有硕士学位，其余规则与此类似。

表2 部分关联规则表

从以上的关联规则可以得出:相关影响因素主要是学历、年龄和职称。职称是副高以上或中青年或学历硕士以上的教师其教学效果为优秀的可能性较大。年龄在30～50岁之间的中青年教师评价分数较高且支持度、置信度也较高，说明该高校实行的加强中青年教师培养和高层次人才引进的人才战略已初步取得成效，学校整体的师资结构更加合理。在教育决策支持系统的数据库中选择一组事务集，大小分别为30 kB，60 kB，120 kB，240 kB，300 kB，360 kB，400 kB 且分布在不同的主机中，使原算法和改进算法挖掘同样大小的事务集，记录运行时间，如图3所示。

图3 两种Apriori算法在实例中运行时间对比图

由图3可知，两种算法的运行时间都随着事务集增大而变长，但改进算法的运行时间要短于原算法，且随着事务集大小的增加，这种优势更加明显，说明改进的分布式数据挖掘算法更适合于数据量越来越多、分布范围在地理上越来越广泛的分布式教育决策支持系统。

4 结论

基于MapReduce模型，对Apriori算法进行改进，提出了一种分布式的关联数据挖掘算法，并对算法进行了模拟，通过仿真实验可知，MapReduce模型的Apriori算法在异构集群环境下，能够提高关联规则挖掘的执行效率，减少算法的执行时间。

[1] FU Y J.Distributed data mining:an overview[R].[S.l.]:IEEE TCDP Newsletter，2001.

[2] MARIO C，ANTONIO C，ANDREA P，et al.Distributed data mining on grids:services，tools，and applications[J].IEEE Transactions on Systems，Man，and Cybernetics:Part B，Cybernetics，2004，34(6):2451 －2465.

[3] KULKARNI U P，YARDI A R.Exploring the capabilities of mobile agents in distributed data mining[C]//Proceeding of the Tenth International Database Engineering＆ Applications Symposium.India:[s.n.]，2006:277－280.

[4] MINGSYAN C，JIAWEI H，PHILIP S Y.Data mining:an overview from a database perspective[J].IEEE Transaction on Knowledge and Data Engineering，1996，8(6):866 －883.

[5] MEHHED K.数据挖掘:概念、模型、方法和算法[M].闪四清，陈茵，程雁，等，译.北京:清华大学出版社，2003:56－121.

[6] AGRAWAL R，TOMASZ I，ARAN S.Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data.New York:ACM，1993:207－216.

[7] 钱少华，蔡勇，钱雪忠.基于数组的Apriori算法的改进[J].计算机应用与软件，2006，23(2):111 －113.

[8] DEAN J，GHEMAWAT S.Map reduce:simplified data processing on large clusters[C]//OSDI'04:Sixth Symposium on Operating System Design and Implementation.San Francisco:[s.n.]，2004:107 －113.

[9] 廖文婕.我国专业学位研究生培养模式的系统结构研究[D].广州:华南理工大学图书馆，2010.