基于多数据库的模糊元关联规则挖掘方法

刘小燕 王 健

1(河南理工大学计算机科学与技术学院 河南 焦作 454000)2(河南理工大学安全科学与工程学院 河南 焦作 454000)

0 引 言

关联规则挖掘算法是数据挖掘算法的一种，对于分布式数据，主要考虑算法的效率。不同站点的数据，事务分布在不同的站点，而垂直分布中，项集在站点之间被分割。基于Apriori的FDM算法(快速分布式挖掘)，主要致力于减少计算项目支持度时的通信交换[1]。CDA(计数分布算法)提出，对于每个可用的处理器，将分区挖掘过程并行化，从分布式数据中提取规则[3]。ODAM算法主要针对地理上分布的数据集，尽量减少交换信息的数量[4]。并行关联规则挖掘算法在不同的站点之间划分数据，而分布式关联规则挖掘算法每个站点单独执行任务但需要访问整个数据集。分布式关联规则挖掘主要目的是减少通信成本。

元规则是一个模板，用于指导关联规则提取过程[5]。临时元规则指的是第2次推理过程中发现的临时规则(一阶规则)[2]，表示形式为(A→B)。有些工作是从关联规则中挖掘模糊规则，在不同的时间段为每个关联规则赋一系列支持度和置信度值[6]。模糊元规则用于捕获随着时间的推移关联规则的变化，从而得到模糊元规则的类型：t1时段支持度变化=相对降低→下一时段支持度变化=高度降低，使用模糊集手工定义适当的语言标签。

传统的挖掘算法，对规模较大的数据进行整体决策时较困难，因此，本文提出了一种二阶挖掘方法，两步使用关联规则来获取元关联规则。元规则的前件或后件是关联规则，不考虑支持度/置信度值序列。和先前工作相比，本文提出的方法有如下好处：由于能从多个数据集中提取规则，并进行二次挖掘，使元规则能表达新的普通规则不能表达的相关信息；该算法产生一组更易于人工检查管理的规则集；允许将上下文信息以更人性化的方式合并到挖掘过程。

1 基于层次理论的模糊关联规则

模糊集应用于关联分析有两种方法：(1) 从清晰关系数据库或量化数据集提取模糊关联；(2) 分析模糊事务。一般来说，方法1中模糊集允许通过语言标签定义属性值的软区间边界，这种方法可用不同的粒度级别表示规则。方法2中，数据以模糊事务数据库的形式提供，即事务项目在一定程度上满足。本文主要考虑方法2，数据以模糊事务数据库的形式表示，即事务中的项目在一定程度上满足。

层次理论模型[6]认为，项i∈I，项目集A⊂I，基于模糊数据库的层次理论表示(∧A,ρA)。其中，∧A={α1,α2,…,αm},1=α1>α2>…>αm>0，是预先定义的层次集，ρA(α)={τ∈：τ(A)≥α}是一个将每个层次应用于清晰的实现中的函数。

MαiB┐BAaibi┐Acidi

其中，ai,bi,ci和di为非负整数，ai=|ρA∧B(αi)|，bi=|ρA∧┐B(αi)|，ci和di类似。为了评价模糊关联规则的有效性，可以使用基本的概率分布概括每一个兴趣度度量，基本的概率分布定义如下：

Y必须是至少一个a∈∧的原象。支持度、置信度和确定性因素分别都是方程。∧等于1可以得到清晰方法的值。

FCF(A→B)=

当|ρA(αi)|=0时，置信度的计算可能有不确定的形式“0/0”，若不存在满足前件的事务时这种情况便会发生。为保持模糊规则的定义，给不确定性赋值。对于确定性因素FCF，层次理论的项目集都需要标准化，即A或B必须满足在层次a=1至少有一个事务，如果不，它们的满足程度应当用A或B达到的最大值来标准化。

2 基于元关联规则挖掘信息

使用元关联规则的目的是将地理上分布或者因为存储、安全或其他原因而水平分区的数据库中的信息进行融合。在这两种情况下，我们想要发现从单个主要的数据集中提取的关联规则之间的关联。当数据集非常大、复杂且异质的情况下这非常有用。比如，数据集类型，数据库收集不同来源的传感器数据(如灯光、移动传感器、视频)，数据被划分在不同的采集或存储区。为了得到有意义的相同类型项目的元规则，主要的数据集必须有相似的结构和语义，但它们的结构不需要完全相同。

下面举例说明这个问题。假设有一个多分支组织，如银行，全国有几个分行。数据存储在各自的分行，这些分行有相似的结构。组织感兴趣的是根据客户的数据分析其利润。有两种选择：(1) 对数据进行全局分析，即合并所有的局部数据，编译成一个大的数据集，分析整个数据；(2) 对从各个分部的数据获取的局部模式进行分析获取相关信息。若用第2种方法，检查的规则数量将会非常多。为此，本文提出了元规则以便于第2种情况下进行分析。通过元规则进行挖掘有以下优点：不需要处理整个数据集，可以提高效率；可以使用从单个数据库获取的模式，减少规则挖掘过程的时间，在多数情况下，可以获取一个较小的、便于检查的规则集；所有数据源不需要有完全一致的结构；元规则便于在更加抽象的层次上分析，因为我们研究的是规则之间的不同而不是数据之间的不同；元规则便于将上下文知识合并到挖掘过程，例如部门选址时关于地方的人口结构或经济数据。但是，因为元规则分析是基于已有的摘要数据(关联规则形式)进行的，所以难免会丢失一些信息。

2.1 元关联规则挖掘过程

图1 原始数据集到最终的元关联规则挖掘过程

Step1{D1,D2,…,Dk}是数据库集，共享部分属性。将规则提取过程应用到每个数据库后，可以获取每个数据库Di的关联规则Ri。然后，在关联规则R1,R2,…,Rk中就可以得到信息和它们的评价值。R1,R2,…,Rk规则的数量可以不同，每个规则的前件或后件中的项目数也可以不同。值得注意的是，Ri可能会有共同的规则。不失一般性，假定处理每个数据集时，使用相同的最小支持度和确定性因素值。

2.2 清晰元关联规则

表1 布尔数据库的例子

得到3种类型的元关联规则：(1)ari=>arj,ari和arj是规则的合取(或一个规则，当ar只涉及一个规则时)。例如，若ari=r1∧r3，arj=r2，则r1∧r3=>r2是个元关联规则。(2)atsi=>atsj,atsi和atsj是属性的合取(或一个属性，当ats只包含一个属性时)。(3)ari=>atsj∧ark或者atsj∧ark=>ari，ari和ark是规则的合取，atsj是属性的合取，它们可以混合。例如，我们可以发现一个形式为r1∧at2=>r3∧at4的元关联规则。

此过程有一定的局限性，因为不收集所有可用信息(即规则的支持度和有效性)，只考虑规则先前是否从数据库中挖掘，这意味着不同强度的普通规则(CF(ri)>>CF(rj))在布尔元数据库中重要性相同。为了解决这个问题，可使用区间将评估测试合并到元数据库，得到的项目形式为。例如，若使用CF，区间为[minCF,1]的子集，项目形式为，其中CFj∈[minCF, 1]，j=1，2。然而，由于清晰的区间边界，这种方法是有问题的。例如，若CF(ri)=0.75，CF(rj)=0.76，区间为(0.5,0.75]和(0.75,1]，则CF值将落在不同的区间尽管它们非常接近。为此，我们考虑将模糊事务作为元规则提取过程的输入，使用层次理论框架管理。

2.3 使用层次理论的模糊元关联规则

模糊事务包括项目的模糊子集，每个项目的度被解释为其对事务的隶属度[8]。在模糊元数据库中，事务是初始数据库Di，项目是发现的规则rj∈Ri。这样，一致使用评价值，确定性因素作为数据集中规则的可满足度。表2描述了模糊元数据库的一般形式。(i,j)处的值，即第Di行第rj列为数据库Di中规则rj的确定性因素。与清晰情况相比，模糊元数据库的取值在单位区间，更具体地说，在区间[minCF, 1]。清晰和模糊属性可提供额外的信息，描述原始数据库的一些特征信息。模糊集适合表示不精确的性质。

表2 模糊数据库的例子

模糊元数据库一旦建立，就可以使用模糊关联规则挖掘算法获取模糊元规则。本文使用层次理论框架，考虑支持度(FSupp)和确定性因素(FCF)措施。与清晰情况相似，模糊元规则也分为3种不同的类型：只与规则或规则的合取相关的模糊元规则；只与属性或属性的合取相关的模糊元规则；与规则和属性的合取相关的模糊元规则。

模糊元规则和清晰元规则相比，它们的发现方式不同，采用了不同的信息(数据库的规则评价度)和合适的评价措施(FSupp、FCF)。需要注意的是，提取的模糊元规则表示的关联在原始数据库中具有很高的可信度，而使用清晰方法只表示该规则存在[9]。

3 算 法

文献[10]中可以找到一些方法发现清晰或模糊关联规则。大多数算法分为两步：第1步，计算频繁项集或候选项集。第2步，提取超过用户定义的精度阈值的规则。第1步计算代价太高，已经提出了很多不同的策略和启发法来减少挖掘过程中的时间消耗。有些文献使用二进制形式表示项目来加速合取的计算。使用二进制表示，内存占用不高，减少了系统的内存需求。

图2 元关联规则挖掘算法的盒图表示

图3 基于层次理论的模糊关联规则挖掘算法

4 实 验

实验环境为：奔腾双核处理器2.5 GHz，3 GB内存，Windows 7，Java 8。为了获得可读的规则，在第1步中限制前件有一个项，后件有一个项。对于元关联规则，允许前件和后件最多有两个项。本文所用实验数据为：(1) 合成数据集：规模小，包含人工数据，划分为8个数据库，每个数据库包含15个事务和6个属性，每个属性有6个不同的可能取值，从而可以得到36个形式为<属性，值>的项。这主要用来区分传统关联规则挖掘算法和本文提出的元关联规则挖掘算法的不同。(2) 真实数据集：包含南京市警区2010年的犯罪记录以及犯罪事件发生时附近街坊的社交经济数据。选择了6个属性：季度、日期、犯罪描述、位置、逮捕、家庭犯罪。数据集由23个数据库组成，每个数据库包含一个警区的事务。元数据库增加了警区范围内学校的一些属性，如学生数、违纪数、安全系数(见表3)。(3)合成数据集用于可扩展：从南京市数据集(见表4)随机生成10个合成数据库，命名为1X-合成、2X-合成、3X-合成、4X-合成、5X-合成、6X-合成、7X-合成、8X-合成、9X-合成、10X-合成。2X-合成数据库包含的事务数是1X-合成数据库的两倍，3X-合成数据库包含的事务数是1X-合成数据库的3倍，其他合成数据库包含的事务数以此递推。

表3 增加的额外属性描述

表4 南京市数据集

通过实验发现，实验1发现的某些规则和单独从8个数据集中的每2个数据集发现的规则相同，它们也在实验2发现的某些元关联规则中出现。如，规则r1(i1->i2)为实验1发现的规则，r1有可能出现在实验2发现的元关联规则的前件或后件中，如r1∧at1=>r2。这种现象很容易理解，因为一个规则若在大多数数据库中被发现，那么在合成数据库中也很容易被发现。

然而，从实验1中获取的许多规则没有出现在实验2的任何元规则中。原因是在合成数据库中，总的支持度和确定值较高超过了阈值，而在分离的数据集中，事务只在某些分离的数据集中满足规则，所以它们没有出现在实验2的任何元规则中。此外，有许多规则出现在实验2的元规则中但是并未出现在实验1中，这也是合理的，因为不同的数据集中获取的规则其支持度和确定值可能低于合成数据库规定的阈值。

2) 真实数据结果 通过合并所有分区数据，构建了几个实验。问题是如何合并表3中的额外属性信息，这些信息已经被分区数据合并，若把它们作为新事务添加到合成数据库中没有多大意义，因此可以作为新项目添加。由于每个区只有一个值，所以相同分区的所有事务重复相同值。比较了合并额外属性和不合并额外属性两种情形下合成数据库中获取的规则。图4显示了支持度和确定值取不同阈值时的结果，从图中可以发现，添加额外属性可以发现更多的关联规则。

图4 minCF不同时合成数据库获取的规则数

第二组实验主要分析清晰和模糊元规则挖掘方法的性能。将支持度阈值分别设为0.1和0.05，图5和图6显示了当确定性因素的阈值取为{0.2,0.3，…，0.9}时发现的元规则数。图5中，清晰方法获取的元规则数大于模糊方法获取的元规则数，尤其是当确定性因素阈值较小时区别非常明显。此外，清晰方法和模糊方法两者最大的不同是，当确定性因素阈值缓慢变大时，清晰元规则数急速下降，而模糊元规则数缓慢下降。由此可见，模糊元规则比清晰元规则更加合适，因为规则数量变化小而且便于观察。图6显示了执行时间和支持度阈值有很大关系，支持度阈值决定了获取的普通关联规则的数量。从图中可以发现，清晰方法受元规则数的影响，而模糊方法有相同的曲线不受元规则数的影响。

图5 支持度阈值取不同值时发现的 清晰和模糊元关联规则

图6 支持度阈值取不同值时挖掘清晰和 模糊元关联规则所耗时间

5 结 语

本文阐述了元关联规则的概念，将从不同的数据集中挖掘的关联规则进行融合。分别基于生成的清晰和模糊元数据库，提出了两个不同的过程以挖掘元关联规则。模糊方法对第一阶段获取的精度措施适当地处理，可以更友好地表示额外的模糊属性；获得了一套简化的元规则，可以方便用户更快的检索。

未来工作需要解决的问题有：很多情况下，属性描述不完全适合于所有数据集，尽管它们含义相似。研究如何在元关联规则挖掘过程中融合信息，一个可能的解决方案是利用知识库，通过匹配类似项目协助挖掘元规则。此外，对于使用大数据集的大数据库，需要进一步验证本文算法的适用性。

参 考 文 献

[1] Cheung D W,Ng V T,Fu A W,et al.Efficient Mining of Association Rules in Distributed Databases[J].Knowledge & Data Engineering IEEE Transactions on,1996,8(6):911-922.

[2] Delado M,Ruiz M D,Sánchez D.New Approaches for Discovering Exception and Anomalous Rules[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2011,19(2):361-399.

[3] 李其轩,路艳丽.直觉模糊信息系统的规则提取方法[J].计算机应用与软件,2015,32(1):251-254.

[4] Saxena N,Arora R,Sikarwar R,et al.An Efficient Approach of Association Rule Mining on Distributed Database Algorithm[J].International Journal of Computer Applications,2014,81(3):12-16.

[5] 翟悦,秦放.基于概念格的无冗余关联规则提取算法[J].计算机应用与软件,2015,32(4):46-49,66.[6]刘玉龙,吴卫荣,王燕.多维信息融合方法及技术研究[J].计算机应用与软件,2017,34(6):101-105.

[7] 周越.多域分布式网络中告警模糊关联规则挖掘的研究[D].成都:电子科技大学,2016.

[8] 丁三军,薛宇,王朝霞,等.基于模糊数据挖掘的虚拟环境主机故障预测[J].计算机工程,2015,41(11):202-206.

[9] 丁建立,王曼.基于关联规则挖掘的航班协同保障数据知识发现研究[J].计算机应用与软件,2016,33(11):21-23,61.

[10] 段功豪.基于多结构数据挖掘的滑坡灾害预测模型研究[D].武汉:中国地质大学,2016.