冯 锋, 张珑耀, 张 青

(西安邮电大学 理学院, 西安 710121)

近年来, 随着物联网、云计算、移动互联网等技术的广泛应用, 人们正在不知不觉中构建一个包罗万象的数据自然界[1]. 与此同时, 各种纷繁复杂的大数据中所蕴含的巨大商业及社会价值受到前所未有的关注和重视, 使得数据挖掘和知识发现等领域内的前沿研究变得炙手可热[2]. Agrawal等[3]提出的Apriori算法被认为是数据挖掘方面最具代表性的成果之一. 该算法将提取关联规则分为两步: 首先, 识别所有的频繁项集, 即支持不低于预先设定的最低支持项集; 其次, 从频繁项集中构造出置信度不低于预先设定最低置信度的有效关联规则. 常规关联规则的挖掘算法主要包括: 1) 经典的Apriori算法; 2) 不产生候选集的FP-growth算法[4]; 3) 基于概念格的Eclat算法[5]; 4) CD (count distribution),DD (data distribution) 和CaD (candidate distribution) 为代表的并行算法[6]. 目前, 关于常规关联规则的研究已取得了一些成果. Barati等[7]研究了在RDF数据中自动挖掘关联规则的SWARM算法; Mai等[8]将格理论应用于挖掘关联规则; Song等[9]提出了一种判断关联规则置信度的新方法; Kim[10]引入了结构化关联映射图的概念. 但常规关联规则的定义中并未涉及项域的划分, 且在计算支持时仅考虑了包含关系, 这在实际应用中会影响数据挖掘的精准性, 并降低规则生成的效率. 为了解决上述问题, Amir等[11]引入了一种极大关联规则. 极大关联规则可用于搜寻通常关联规则挖掘中常被忽略的一些特异性内在关联, 且挖掘出的规则数量相对较少, 有利于提高数据挖掘过程的效率. 一个极大关联规则表示: 若前件在交易中恰为其所属范畴中独自出现的项集, 则后件必将以一定的置信度出现在该交易中. 极大关联规则既不是Agrawal经典关联规则的一种特化, 更不是为了扩展或取代常规关联规则, 而是常规关联规则不可或缺的有益补充.

软集理论[12]是从参数化的角度处理不确定性的新构架. 软集定义中既涉及对象论域, 同时也引入了与论域有关的参数空间, 相对于模糊集或粗糙集等不确定计算理论, 软集可进行更灵活多样的信息描述和数学处理. 文献[13]首次从软集的角度探讨了交易数据库中关联规则和极大关联规则的挖掘问题; 冯锋等[14]指出了文献[13]中一些已有概念存在的缺陷, 并给出了修正方法, 提升了相关概念的准确性和适用性; 文献[15]首次引入了软集上的逻辑公式及其软真度等概念, 用于研究基于软集的近似推理理论; 在此基础上, 文献[16]基于软集理论构建了一种不确定计算和决策的逻辑框架, 并将其成功应用于研究信息系统中的决策规则提取和属性分析等问题; 文献[17]利用软真度给出了关联规则的挖掘方法. 本文考虑如何借助软集逻辑公式给出常规关联规则和极大关联规则的统一数学刻画.

1 软集与软集逻辑公式

设U是论域,E是与U内对象相关全体参数构成的集合, 称为参数空间. 记U的幂集为P(U), (U,E)称为软论域.

定义1[12]二元组P =(F,A)称为U上的一个软集, 其中A⊆E称为P的参数集, 集值映射F:A→P(U)称为P的近似函数.

定义2[14]设(F,A)∈SA(U), 且T是参数集A的一个划分, 则称三元组P =(F,A,T)为U上的一个参数类化软集.

定义3[15]设P =(F,A)∈SA(U), 构造集合F(P )如下:

1)A⊆F(P );

2) 若φ∈F(P ), 则φ∈F(P );

3) 若φ,ψ∈F(P ), 则(φ∧ψ)∈F(P ), (φ∨ψ)∈F(P );

4) 当且仅当有限次应用2)和3)所得的字符串是F(P )中的元素.

F(P )中元素称为软集P上的逻辑公式. 特别地, 称A中的元素为原子公式.

定义4[15]设P =(F,A)∈SA(U)且X={a1,a2,…,as}⊆A, 则公式φX⟺a1∧a2∧…∧as称为X在P中对应的满合取公式.

定义5[15]设P =(F,A)∈SA(U), 定义φ∈F(P )的基本软真度为

2 关联规则与极大关联规则

假设I={i1,i2,…,i|I|}是给定交易数据中涉及的全体项目集, 称为项域. 每条交易记录t都是I的一个非空子集, 并被赋予唯一的交易标识符TID与之对应. 集合D={t1,t2,…,t|D|}包含所有给定的交易, 称为交易数据集. 由I中若干项目构成的非空集合X称为项集, 包含k个项目的项集称为k-项集. 如果X⊆t, 则称交易t在D内支持X.ΔD(X)={t∈D:X⊆t}称为项集X在D内的实现集, 其基数称为X在D内的支持, 记为SD(X).

定义6[3]给定两个不相交的项集X,Y⊆I, 形式表达式X⟹Y称为一个关联规则. 项集X,Y分别称为规则的前件和后件. 关联规则X⟹Y在D内的实现集ΔD(X⟹Y)定义为

ΔD(X⟹Y)=ΔD(X∪Y).

X⟹Y在D内的支持SD(X⟹Y)定义为

SD(X⟹Y)=SD(X∪Y)=card(ΔD(X⟹Y)).

定义7[3]关联规则X⟹Y在D内的置信度CD(X⟹Y)定义为

此外, 若SD(X)=0, 则令CD(X⟹Y)=0.

为了在交易数据集中挖掘有用的关联规则, 需预先设定最小支持(minsupp)和最小置信度(minconf). 如果SD(X)≥minsupp, 则称X为频繁项集. 此外, 当SD(X⟹Y)≥minsupp且CD(X⟹Y)≥minconf时, 则称X⟹Y是一条强关联规则. 在交易数据库的数据挖掘和知识发现研究中, 如何在预先设定好最小支持和最小置信度的前提下, 从交易数据集中提取出频繁项集和强关联规则是一个热点问题.

为了挖掘交易数据集中隐藏的极大关联规则, 需考虑项域I={i1,i2,…,i|I|}的划分T, 也称为I的分类, 分类T中的子块称为范畴. 由定义知, 对任意的ik∈I,T中包含ik的范畴是唯一的, 记为C(ik). 当项集X取自范畴Ci(即X⊆Ci∈T)时, 可将Ci记为CX.

定义8[11]设t∈D是数据集中的一条交易记录,X⊆CX是一个项集. 若t∩CX=X, 则称X在t中是独自的, 也称t在D内M-支持X.

(Y⊆t)}.

其中

D(X,Y)={t∈D: (t∩CX=X)∧(t∩CY≠Ø)}.

3 极大关联规则的软集逻辑公式描述

设D={t1,t2,…,t|D|}是项域I={i1,i2,…,i|I|}上的交易数据集. 取论域U=D, 参数集A=I, ∀ik∈I, 令F(ik)=ΔD(ik)={t∈D:ik∈t}. 从而可得D上的软集P =(F,I), 称为由交易数据集D诱导的软集. 此外, 如果T={C1,C2,…,C|T|}是I的分类, 则P =(F,I,T)是D上的参数类化软集.

ΔD(X⟹Y)=‖φX∧φY‖P.

进而有

SD(X⟹Y)=|D|·βP(φX∧φY).

此外,

命题1设X⊆CX∈T且X≠Ø, 则

此外, 对任意的t∈D, 有

因此,

命题1表明, 项集X的M-实现集可通过φX∧在软集P中的实现集计算. 类似地, 可证明如下结果.

命题2设X和Y是分别来自两个不同范畴CX和CY的项集, 则

(Y⊆t)}=‖φX∧φY∧

命题3设X和Y是分别来自两个不同范畴CX和CY的项集, 则

利用上述已证命题, 可得下列结果:

推论1设X⊆CX∈T且X≠Ø, 则

推论2设X⊆CX∈T且X≠Ø, 则

推论3设X和Y是分别来自两个不同范畴CX和CY的项集, 则

推论4设X和Y是分别来自两个不同范畴CX和CY的项集, 则

推论5设X和Y是分别来自两个不同范畴CX和CY的项集, 则

上述结果表明, 利用满合取及其对偶公式, 能方便地描述极大关联规则挖掘中涉及的全部核心概念.

4 实例分析

设某医院记录的临床诊断数据集D={t1,t2,…,t200}的项域I={A,B,x,y,z}, 其中:x,y,z表示3种“症状”;A,B表示两种“疾病”. 共计200条数据记录, 结果列于表1. 为了分析症状和疾病之间的内在关联, 考虑项域I={A,B,x,y,z}的划分T={C1,C2}, 其中范畴C1={A,B}和C2={x,y,z}分别表示“疾病”和“症状”. 由临床诊断数据集D诱导的参数类化软集P =(F,I,T)列于表2.

在此基础上, 利用软集逻辑公式等概念设计相关算法, 并在MATLAB8.5中编程挖掘数据集D中的极大关联规则. 当设定最小M-支持α=20和最小M-置信度β=75%时, 同时在相同阈值下利用经典的Apriori算法挖掘常规关联规则进行对照, 部分结果列于表3.

表1 临床诊断数据集D

表2 数据集D诱导的参数类化软集

表3 常规与极大关联规则的对比

考虑表3中的常规关联规则{x,y,z}⟹A, 令X={x,y,z},Y={A}, 则X对应的满合取公式为φX⟺x∧y∧z. 进而知规则{x,y,z}⟹A对应的软集逻辑公式为

φX∧φY⟺x∧y∧z∧A.

该常规关联规则在D内的实现集可利用对应公式在软集P中的实现集‖x∧y∧z∧A‖P计算, 即

ΔD({x,y,z}⟹A)=‖x∧y∧z∧A‖P={t35,…,t139}.

此外,

进一步, 有

φX1∧φY∧⟺x∧y∧A∧z.

根据该公式在软集P中的实现集‖x∧y∧A∧z‖P可计算出对应极大关联规则在D内的实现集, 即

此外,

且

于是,

上述实例说明了如何利用软集逻辑公式描述挖掘关联规则时涉及的核心概念.

当设定最小支持α=20和最小置信度β=75%时, 利用Apriori算法挖掘出41条常规强关联规则, 如z⟹x,x⟹A, {x,y}⟹A和{x,y,z}⟹A等. 分析表明, 虽然规则z⟹x的支持为120且置信度为87.6%, 远高于所设的阈值, 但该强关联规则的前件和后件均为症状, 在临床诊断中无实际意义. 此外, 常规关联规则x⟹A和{x,y}⟹A的支持分别为135和123, 置信度分别为83.3%和98.4%. 虽然这两条强关联规则都具有很高的支持和置信度, 但其是由更精准的规则{x,y,z}⟹A衍生出来的“副产品”. 实际上, 置信度为100%的规则{x,y,z}⟹A真正反映了临床诊断中的客观规律, 而其他“副产品”的大量输出增加了常规挖掘的冗余性, 为识别真正有价值的规则带来了困难.

综上可见, 虽然常规挖掘中获得的强规则通常数量惊人, 但却包含了大量无意义及冗余规则, 并有可能忽略一些具有实际意义的重要规则. 因此, 基于软集逻辑公式的极大关联规则挖掘不仅对解决常规挖掘中的“规则爆炸”等问题有益, 更是对经典关联规则挖掘方法的补充.