姜丽莉 黄承宁

摘要：该文将关联规则挖掘算法应用于某煤矿的考勤数据的分析。针对关系数据库的特点，对传统的关联规则挖掘算法进行了优化。算法借鉴元组ID传播思想，将关系图进行切分，对每一部分建立了全局的键值映射哈希表，通过哈希表，将单表挖掘出的项集进行连接，从而得到多关系间的频繁项集。最后设计并实现了一个多关系的关联规则挖掘系统，对考勤数据进行分析。

关键词：关联规则;数据挖掘;多关系

中图分类号：TP393        文献标识码：A       文章编号：1009-3044（2018）36-0003-02

关联规则挖掘是数据挖掘的重要研究领域之一。传统算法是将多个关系连接成一个泛关系表。这种算法存在着性能较低、统计偏斜和信息丢失等问题。针对性能问题，许多学者根据元组传播的思想，提出了一些避免多表间直接连接的算法。但是，这些算法一般都是针对星型模式或者雪花模式的数据库，不可以直接应用于更加广泛的实体联系模式的数据库。另外，这些算法存在着统计偏斜问题。基于ILP（归纳逻辑程序设计）技术的关联规则挖掘算法可以避免统计偏斜问题，但是存在着效率低、可扩展性差等问题。

本文旨在分析某煤矿的考勤数据，数据存放在关系数据库SQL Server中。为了避免统计偏斜、信息丢失等问题，需要在传统算法的基础之上，利用关系数据库的特点，对算法进行优化。

1 关系数据库中项集特点

1.1 关系图

在关系数据库中，关系模式是有概念模式生成的。概念模式的表示方法一般为E-R图。在E-R图中，包括实体和联系两个元素，实体与实体之间的联系类型有“1对1”、“1对多”和 “多对多”三种，根据一定的规则和规范化要求，可以导出由实体和联系生成的关系模式。因此，关系模式可以分为实体关系模式（实体表）和联系关系（联系表）模式两类。根据关系数据模型的参照完整性要求，关系表之间存在主外键的约束关系，形成了关系图。

1.2 关系项集

关系表的属性都具有多值特点，故跟事务数据库不同，关系数据库的项集中，每一项都是一个属性-值对。多关系项集是项的集合，同一项集的不同项可以来自数据库中的不同关系。而为了使不同关系的项出现在同一项集中，需要对关系进行连接操作。

若一个项集中包含多个关系的项，其频数的定义一般会被定义为项集在连接后的查询表中的出现次数。这种定义方式很容易导致统计偏斜问题。

1.3 强语义项集

在关系数据库中，随着关系表间连接路径的增长，项集间的语义关系越弱，实际意义也越小[1]。

为了挖掘强语义的关联规则，将E-R图进行切分。每一部分包括中心位置的联系表，包含联系表中的外键的实体表（主实体表），和包含这些实体表的外键的实体表（附属实体表）。针对每一部分包含的关系表进行多关系关联规则挖掘。某一实体可能会同时属于不同的部分，但无须重复对该实体进行单表的挖掘。算法可以只考虑其中的一个部分，例如图1所示。

2 改进算法的描述

2.1 挖掘频繁项集

根据上述分析，在关系数据库中，为了挖掘强语义的频繁项集，需要将关系图进行切分。对一个切分后的关系图，包含如下三类表：主实体表、附属实体表和联系表。

基于这些关系表的频繁挖掘方法可以采用直接连接的方法，形成一张大表。但是这种方法会导致性能低下、统计偏斜等问题。故本文利用关系数据库的特点对传统方法进行改进。算法主要包括如下4个步骤。

1） 挖掘单表频繁项集

挖掘单表的频繁项集可以采用现有的经典关联规则挖掘算法Apriori算法、Fp-Growth算法，或者使用一些基于经典算法的改进算法。但是本文对挖掘出的频繁相项集的格式做如下规定。频繁项集包括键链表、频繁项集、支持计数三个域，如图2所示。其中键链表指的是包含该项集的键的链表，用于实现项集的虚拟连接。支持计数为键链表中结点的个数。

2） 构建元组ID映射哈希表

一般认为，在关系数据库中，如果将多张表进行连接操作，形成的临时表中包含某个项集，则可以认为该项集在数据库中是存在的，是待挖掘的对象。而如果该项集中的项存在于不同的关系表中，则可以认为这些不同的项是可以连接的。借鉴元组ID传播方法，可以将多个项集通过项集对应的键进行连接，进而实现关系表的虚拟连接。通过该方法，可以通过项集的连接，挖掘存在于多个关系表中的频繁项集。

在关系数据库中，附属实体表与主实体表的联系类型为“1对多”，每一个附属实体的键对应若干个主实体表的键。而主实体表与联系表之间的联系类型也是“1对多”，每一个主实体表的键，对应多个联系表的键。对于“多”方的多个键可以通过链表的方式连起来。而对于联系类型“1对多”，可以创建一个哈希表，实现从“1”方到“多”方的映射。该哈希表的键为“1”方的键，哈希表的值为与“1”方对应的“多”方的键的链表。因此，可以采用如下方法，构建全局的元组ID传播哈希表，将多个关系实现虚拟连接。

（1） 创建附属实体与主实体的哈希表

遍历每个主实体表，对每个元组中的每个外键，创建该外键与实体表主键的映射，实现附属实体与主实体键的哈希表，其键为该外键（对应附属实体的主键），其值为该外键在该元组中对应的主键。

（2） 創建主实体表与联系表的哈希表

遍历每个联系表，对每个元组中的每个外键，创建该外键与联系表主键的映射，实现主实体表与联系表的键的哈希表，其键为该外键（对应主实体的主键），其值为该外键在该元组中对应的主键。

3） 计算主实体表与附属实体表频繁项集

设由第（1）步得到的某一实体[Ei]的所有频繁项集的集合为[MSi]，频繁项集数为[m]，附属实体个数为[n]，每个附属实体[Eij][（0≤j≤n）]的所有频繁项集的集合为[ASj]，频繁项集数为[aj];由第（2）步得到的[Eij]与[Ei]的ID传播哈希表为[Hashij]，则连接算法描述如下。

输入：[MSi]，[m]，对应[n]个[Eij][（0≤j≤n）]的[ASj]，[aj]，[Hashij]

输出：存在于主实体[Ei]和[n]个附属实体[Eij][（0≤j≤n）]间的所有频繁项集[MASi]。

算法：

（1） MASi：=[?]

（2） 计算[Ei]与[n]个[Eij]的所有组合。

（3） For 每一个组合

（3-1）利用Hash表表组合内项集进行连接

（3-2）利用Hash表及实体的键链表，求连接后项集对于主实体[Ei]的支持计数。

（3-3）若项集支持计数大于最小支持度，指定其键为对应主实体[Ei]的键，并入[MASi]。

由于实际数据库中，一张主实体表中包含的外键个数一般不会太多，故步骤2）中组合数不会太大。步骤（3-1）中，包含外键的项集不参与连接，该类频繁项集实际意义为该外键对应的实体与主实体属性的联系。

4） 计算主实体表与联系表的频繁项集

主实体表与联系表的关系与附属实体表与主实体表的关系类似，都是“1对多”的关系，故可以参照步骤3），将每个联系表的频繁项集与其对应的主实体表的频繁项集进行连接。

2.2 关联规则的提取

关联规则的提取方法与传统算法是一致。

根据2.1可以，挖掘出的每个频繁项集都有一个键链表，规则前件与规则后件的键链表相同，同一张表的关联规则，其置信度计算是针对单张表的，多表见的关联规则，其置信度的计算是针对多张表的连接的。因此，可以最大限度地避免统计偏斜。

3 基于改进算法的挖掘系统

本文待分析的数据涉及员工基本信息表、工种表、部门表、出勤表和勤種表五张表。其中主关系表有5000条记录，联系表有44万条记录。系统的开发环境为Visual C++2010，后台数据库为SQL Server 2008。系统主要包括数据导入、数据预处理、系统配置、频繁项集挖掘和关联规则导出五个功能模块。

通过菜单项“数据导入”，导入需要分析的数据（可以选择指定的时间段），再通过菜单项“数据预处理”对所选择的数据进行数据清洗、格式转换等操作，然后通过菜单项“系统配置”设置本系统的最小支持度和最小置信度，最后通过菜单项“频繁属性集挖掘”，挖掘出所选数据的频繁项集。

得到频繁项集以后，通过菜单项“关联规则导出”，即可导出关联规则，对导出的关联规则，进行进一步分析，找到有意义的规则，对公司的决策提供支持。

本文旨在对某煤矿的考勤数据进行关联规则挖掘。在借鉴前人研究的基础上，充分研究并利用了关系数据库的特点，对传统的关联规则进行了优化，避免了统计偏斜和信息丢失的现象，优化了性能，实现了一个简单的关联规则挖掘系统，供该煤矿的考勤数据分析使用。

参考文献：

[1] 何军，刘红岩，杜小勇.挖掘多关系关联规则[J].软件学报，2007，18（11）：2752-2765.

[2] 崔妍，包志强.关联规则挖掘综述[J].计算机应用研究，2016，33（2）：330-334.

[3] 王英博，马菁，柴佳佳，等.基于Hadoop平台的改进关联规则挖掘算法[J].计算机工程，2016，42（10）：69-74，79.

[通联编辑：光文玲]