基于关联规则与相似度的数据挖掘算法研究

李 英， 汤 庸

(华南师范大学计算机学院, 广州 510631)

数据挖掘作为全球范围内快速兴起的一门交叉学科，结合了多个领域技术，包括数理统计、数据库技术、人工智能和机器学习等领域的理论和技术. 一般意义上，数据挖掘的分析方法主要有人工神经网络法、决策树法、分类分析法、聚类分析法、关联规则分析法和序列模式分析法等，针对不同领域的具体业务问题，选择合适的分析方法可以得到更加有效的结果.

关联规则分析是在数据集中找出各项之间的关联关系的分析方法[1]，是数据挖掘中最活跃的研究方法之一. 1994年，AGRAWAL和SRIKANT[2]提出了基于频繁集模式生成关联规则的Apriori算法. 由于Apriori算法存在反复扫描数据库的缺点, 许多学者在提升关联规则算法效率以及不同应用领域进行了大量研究. 如：提出了对比规则集模式的SCR-Apriori算法，通过将模式结构的知识引入Apriori算法，显著地缩减了待分析频繁项集的搜索空间[3]；在传统关联规则支持度和置信度的基础上，在领域数据中增加效用度和有趣度来消除关联冗余，有助于挖掘出有效的关联规则[4]；提出基于项权值排序的加权关联规则挖掘算法，可用于各种语言的信息检索，以改善检索性能[5]；提出了基于权值向量矩阵约简的Apriori算法，通过不断约简矩阵结构、降低源数据和候选项集规模，提高了运算效率[6]；对基于MapReduce模型的Apriori算法进行了改进，减少了数据库扫描次数，且并行计算频繁项集，提高了算法的效率[7]；综合利用Word2Vec和K-means算法等技术，提出了一种无监督Apriori学习算法来分析和挖掘地质大数据中的关联规则，有效地挖掘矿床数据中的潜在关系和规律[8]；提出了基于层次分析法(AHP)和混合 Apriori-Genetic 的模型挖掘交通事故成因，提高挖掘的准确性[9]；提出一种具备自适应能力的规则生成框架来自动生成关联规则，从而更好地识别未知网络攻击[10].

随着教育信息化不断发展，教育领域数据爆炸式增长，针对教育领域的数据挖掘也成为当前数据挖掘研究的一个新热点. 应用不同的数据挖掘方法，可以更好地辅助学校进行合理的决策. 如：采用改进关联规则挖掘算法，设计融合关联规则挖掘算法的信息化教学管理系统，从系统数据库内挖掘用户各方面教育信息关联数据[11]；利用Apriori算法挖掘出来的规则，结合最近邻居算法，有效地预测学生学业的成功程度[12]；在排课过程中应用关联规则，对高校排课进行优化[13]；提出了一种基于决策树的分类算法，为推荐系统模型选择出最有价值的特征，有效提高了潜在好友推荐准确率[14]. 为了挖掘用户感兴趣的规则，提高挖掘的效率，本文提出了基于关联规则和相似度的数据挖掘算法(U-APR)：首先，为解决Apriori算法频繁扫描数据库问题，一次性读入数据并构建矩阵，并利用关联规则支持度度量的特性来增加判断属性，以加快结束搜索过程；然后，对于初步挖掘的关联规则，使用Jaccard相似度算法融合领域专家关注的信息去除冗余规则；最后，结合支持度、置信度和文本匹配度计算每一条规则推荐值，按推荐值由高到低输出关联规则. 并采用U-APR算法和目前常用的2种关联规则算法，对某高校2016—2019级学生在2019年的缴费和学生奖助学金等财务数据进行挖掘.

1 预备知识

1.1 关联规则挖掘

关联规则挖掘是以某种方式分析数据源，并从数据集中发现有趣的关联或相关关系，即从数据集中找出高频出现的项目集，也称为频繁项集(简称频繁集)，然后再利用这些频繁集产生关联规则的过程[15].

设I={i1,i2,…,in}是数据中所有项的集合，ik(k=1,2,…,n)称为1个项，包含0个或多个项的集合称为项集. 如果一个项集包含K个项，则称其为K-项集. 满足定义的最小支持度阈值的所有项集，称作频繁项集. 设D是任务相关的数据库事务的集合，其中每个事务T是项的集合，是I的非空子集. 设X和Y是事务T中包含的2个项集，即X⊆T，Y⊆T. 若X≠∅，Y≠∅且X∩Y=∅，则构成事务集D的关联规则T：X⟹Y.

一般使用支持度和置信度2个重要的度量值来评价关联规则的价值. 在关联规则中，将X和Y同时出现的概率定义为关联规则的支持度，即：

(1)

其中，P(X∪Y)表示同时包含项集X和项集Y的事务个数，|D|为事务数据库记录总数．

置信度是项集X发生的前提下，项集Y发生的概率，表示了这条规则有多大程度上值得可信，即：

(2)

通常用户更关注的是支持度和置信度都高的强关联规则. 为了对关联规则进行量化和评估，需要设置最小支持度(min_sup)和最小置信度(min_conf)2个阈值，其中，0

项集的一个最重要的性质是它的支持度计数[16]，也就是包含特定项集的事务个数. 定义项集X的最小支持度计数为δ(X)=min_sup×|D|.

先验性质的定义为：如果项集X是频繁项集，则X的子集Y必为频繁项集；如果项集Y是非频繁项集，则Y的超集X一定为非频繁项集. 一个项集X的支持度绝不会超过它的子集的支持度，称为支持度度量的反单调性[16]. 关联规则算法利用先验性质和支持度度量的反单调性进行剪枝优化，可以减少不必要的运算，提高算法效率.

1.2 基于相似度的关联规则挖掘

基于相似性度量的算法种类繁多，不同领域、不同类型的数据适用于不同的相似性算法[17]. 其中，Jaccard相似系数[18]主要应用于计算文本相似度. 对于给定的集合A和集合B，Jaccard相似系数定义为

(3)

其取值范围为[0,1]. 2个样本点愈相似，则相似系数值愈接近1，反之则愈接近0. 由于最终挖掘的规则前件和后件都是文本的集合，为了量化规则与用户目标的相关性，本文应用Jaccard相似系数来计算关联规则与用户目标文本的匹配度.

1.3 Apriori算法

Apriori算法[2]是关联规则挖掘的经典算法，采用逐层搜索迭代的方法：首先，扫描数据库产生候选集，利用最小支持度度量对候选集进行剪枝，得到新的频繁项集，再由频繁项集连接成新的候选集；不断重复连接和剪枝过程，直到最终频繁集为空时，结束迭代过程. 从算法的过程可以看出，在每次迭代过程中计算支持度时，都需要重复扫描数据库，每次迭代过程中频繁项集两两联接生成新候选集，都会耗费大量的系统资源.

2 U-APR算法

2.1 对Apriori算法的改进

首先，一次性扫描数据库，并将其表示为对应的矩阵，为减小矩阵规模，将重复事务压缩为1行，增加权值向量；其次，利用支持度度量的反单调性，在剪枝过程中，每个候选集项集的支持度分别与最小支持度对比，删减小于最小支持度的项集，减少新的候选集的生成数量. 算法增加了对候选集事务项个数与支持度计数大小的比较，加快结束算法迭代过程. 下面举例说明改进算法的思想.

事务数据库D={t1,t2,t3,t4,t5}中，每一组事务ti表示不同的顾客在商场一次购买商品的集合.D中所有T包含的项目的集合I={i1,i2,i3,i4,i5}. 事务集t1={i1,i2,i3,i5}、t2={i2,i3,i5}、t3={i1,i3,i4}、t4={i1,i3,i4}、t5={i2,i5}. 假设最小支持度min_sup=0.4，则最小支持度计数为min_sup×|D|=0.4×5=2.

改进算法的步骤如下：

步骤1：扫描数据库，生成二进制矩阵M：

因为事务t3和事务t4包含相同的项集，按算法规则对M中相同行进行压缩，得到矩阵M′和权值向量w：

w中的每一个数值表示相同事务的数量；对M中列、行合计，分别得到向量s=(3,3,4,2,3)、r=(4,3,3,2).

步骤2：删除小于最小支持度计数2的i4列后，得到频繁1-项集L1={i1,i2,i3,i5}. 连接1-项集得候选集{i1,i2}、{i1,i3}、{i1,i5}、{i2,i3}、{i2,i5}、{i3,i5}.

步骤3：事务项大于等于2的项集个数为6，大于最小支持度计数2. 经计算得到候选集的支持度计数分别为2、3、1、3、3、2，其中候选集{i1,i5}的支持度计数为1，小于最小支持度计数. 去除{i1,i5}后得到频繁2-项集L2={{i1,i2},{i1,i3},{i2,i3},{i2,i5},{i3,i5}}.

步骤4：连接频繁2-项集L2，得候选集{i1,i2,i3}、{i1,i2,i5}、{i1,i3,i5}、{i2,i3,i5},事务项大于等于3的项集个数为4. 根据支持度度量的反单调性，直接去除包含{i1,i5}的候选集{i1,i2,i5}和{i1,i3,i5}，对其余候选集进行逻辑与运算，经计算得到支持度计数均为2，从而得到频繁3-项集L3={{i1,i2,i3},{i2,i3,i5}}.

步骤5：连接频繁3-项集L3,得候选集{i1,i2,i3,i5}，事务项大于等于4的项集个数为1，小于最小支持度计数2，算法终止.

因此，事务数据库D的频繁项集L1、L2、L3分别为:

L1={i1,i2,i3,i5}；L2={{i1,i2},{i1,i3},{i2,i3},

{i2,i5},{i3,i5}}；L3={{i1,i2,i3},{i2,i3,i5}}.

2.2 结合用户目标的关联规则推荐

考虑到关联规则挖掘应用在具体领域时，可能挖掘到的结果虽然是符合频繁项集条件的强规则，但可能是用户毫无兴趣或者对解决实际问题帮助不大的规则. 为了量化关联规则与用户挖掘目标的相关性，本文利用Jaccard算法计算用户目标字段与所挖掘的关联规则的相似度，以衡量规则与用户目标之间的相似性. 因此，本文在支持度、置信度这2个指标的基础上增加目标文本匹配度指标match. 通过计算项集与用户关注内容的文本的匹配指标，动态指定3个指标参数权重及阈值，计算每一条规则的推荐值，最终按推荐值由高到低输出关联规则结果.

首先，计算用户目标文本与每条强关联规则的文本匹配度，将匹配度为0的规则设为无效规则，再根据下式计算有效规则的推荐值：

value=λ1*Support(X,Y)+λ2*Confidence(X=>Y)+

λ3*match，

(4)

其中:Support(X,Y)为规则的支持度;Confidence(X=>Y)为规则的置信度;match=J(A,B)为目标文本的匹配度;λi为对应比重，由用户指定. 根据计算出来的每一条规则的推荐值，由大到小排序，并按排序将挖掘的规则推荐给用户.

3 数据挖掘实践

实验首先对广东某高校学生缴费数据集进行了采集及预处理，然后采用U-APR算法对该数据集进行挖掘，最后与传统Apriori算法、文献[6]的算法进行了对比实验.

3.1 数据采集

考虑到学校学生学费管理系统信息的不断改革和升级，较早时期的学生相关数据存在不完善和信息缺失，因此，采集目前在校学生的基础信息、学费收缴情况及学生补助发放情况的学生财务信息. 本文对广东某高校在校学生学费管理系统数据进行采集，并选取其中的2016—2019级全体学生的2019年度学费缴费数据和补助发放数据作为研究数据，以学号为标识符，采集到的缴费信息为35 969条，主要有3类信息：学生的基本情况信息、学生缴费数据、学生奖/助学金发放数据. 包含的数据属性为：姓名-学号-年级-学院-专业、收费年度-收费项目-应交学费-已缴学费、学号-奖学金发放金额-助学金发放金额-发放说明.

3.2 数据预处理

首先对采集到的样本数据按以下步骤进行预处理：(1)由于学生的“姓名”“学号”属于敏感信息，因此删除学生“姓名”与“学号”这2项数据，随机生成学生编号作为学生唯一识别码；(2)因为系统收费过程中的数据可能存在学生因金额不足将一年学费拆分多次缴费、多缴费退费等问题，所以，针对不同情况，对数据进行分析后根据不同数据项进行不同形式的处理，最后得到真实缴费数据；(3)由于在实际高校收费情况中，学生根据文、理、艺术和体育等不同类别，按不同标准收费，与学生具体专业不直接相关，因此剔除“专业”属性，保留“专业类型”属性；(4)根据学生奖学金发放情况，将获得国家奖学金、学业奖学金和优秀学生奖学金等奖励的学生设置为优秀学生，其余学生设置为普通学生；(5)因为是对年度数据做关联规则分析，所以将一年内分多次发放的补助进行合并，并按实际发放补助金额进行离散化处理，数据进行离散化后结果如表1所示；(6)因为本课题关注学生是否欠费，数据表增加字段“是否欠费”，用应缴学费减已缴学费，以生成学费是否欠费的属性作为研究属性. 按上述步骤处理完后，对学生缴费相关信息按照相应规则进行变量的离散化处理，结果见表2.

表1 学生补助离散化处理Table 1 The discretization of student allowance

表2 全部属性的离散化整理分析Table 2 The discretization analysis of all attributes

3.3 采用U-APR算法的挖掘结果

程序对已做预处理的35 969条学生信息数据进行挖掘,其中包括本科生25 501人、硕士生9 690人、博士生778人. 设置了4组实验参数进行最小支持度、最小置信度与关联规则数量的相关性测试. 由4组实验参数的结果(表3)可知：规则数与最小支持度、最小置信度负相关，随着最小支持度和最小置信度的不断增大，规则数相应减少，过大的阈值可能会将一些有趣的规则筛选掉，过小的阈值则可能产生太多的无用规则. 一般根据经验值设置阈值可以得到适当数量的关联规则，有利于提高分析效率.

表3 4组实验参数下的关联规则数

在能体现算法有效性的情况下，为了减少分析的复杂程度，本实验选择对最小支持度为0.4、最小置信度为0.9时产生的关联规则(表4)做进一步去除冗余规则实验：第一步，用户选择录入目标文本“交费”时，系统根据式(3)计算规则的匹配度；第二步，设置权重系数λ1=0.3，λ2=0.4，λ3=0.3，按式(4)计算每一条关联规则的推荐值；第三步，根据推荐值得到规则的结果. 由结果(表5)可知：在选定的阈值条件下，最终去除了18.75%的冗余规则.

表4 关联规则结果Table 4 The mining results with the association rules

表5 基于用户目标的推荐挖掘结果

3.4 对比实验结果与分析

为了评估U-APR算法的性能，利用上述已预处理的学生数据集与Apriori算法、文献[6]的算法进行了对比实验，根据实验结果对U-APR算法进行时间性能评估,同时进行冗余规则消除前后的规则数对比实验.

实验环境为: CPU为Intel Core(TM)i5-8265，主频为1.80 GHz，内存为8 GB. 算法采用Python语言进行编写，在Anaconda环境下进行编译与运行.

由不同最小支持度下的3种算法的运行时间(图1)可知：3种算法的运行时间均随着最小支持度的增大快速减少，但当最小支持度为0.05时，U-APR算法的挖掘效率明显高于其他2种算法. 究其原因为：U-APR算法采用一次性扫描数据库，并利用支持度度量的反单调性不断删减非频繁项集，加快了搜索过程，减少了存储空间的占用；从时间复杂度方面来看，通过增加行和列判断属性，节约了剪枝步骤中频繁项集的比较次数，减少了程序运行时间，提升了效率.

图1 不同最小支持度下的运行时间

由最终输出关联规则数(图2)可知：随着最小支持度增大，3种算法挖掘的关联规则数均明显减少；在相同的最小支持度下，U-APR算法减少的冗余规则明显多于另2个算法，究其原因为：U-APR算法按照用户目标对关联规则进行二次挖掘，有效去除冗余规则，减少最终挖掘的规则数量，可以有效提高用户对挖掘结果分析的效率.

图2 不同最小支持度下的关联规则数

4 结语

本文提出基于关联规则和相似度的数据挖掘算法(U-APR),该算法一次性读入数据并构建矩阵，并利用关联规则支持度度量的特性增加判断属性，以加快结束搜索迭代过程；然后，融合领域专家关注的目标，使用相似度算法去除冗余的关联规则；最后，结合置信度、支持度和用户目标匹配度生成推荐值，按推荐值大小对挖掘的规则排序输出. 以高校学生实际缴费信息为样本，U-APR算法与2种常用的关联规则算法的对比实验结果表明：U-APR算法减少了用户不感兴趣的冗余规则，提高了挖掘效率和减少存储空间的占用.

本文通过对学生财务数据的挖掘，找出学生属性与缴费、补助发放等行为之间的关联性，可为高校科学决策和管理提供有效支持. 学校管理部门可根据挖掘到的关联规则，完善学费管理办法，如结合学校收费标准，对于在学校获得高额(超过学费标准)补助和奖学金，但在没有提出申请免交学费的情况下不按时缴纳学费的同学给予诚信预警.

U-APR算法具有一般性，也适用于其他领域具有相似结构的数据研究. 在未来的工作中，将研究如何进一步提高大数据环境下关联规则算法的效率.