随着大数据时代的来临，利用数据挖掘技术进行数据分析以辅助决策成为大势所趋。低质量的数据会导致错误的决策。据有关统计，美国企业每年因错误和不一致数据导致的损失高达数千亿美元[1]。因此，数据质量控制如数据一致性的保证逐步成为数据科学领域研究的重要课题。
传统的函数依赖(functional dependency,FD)是为了保证业务信息系统中数据的一致性而提出的。但是，标准函数依赖在全面反映数据的一致性和表达多样的依赖规则时有很大的局限性[2]。近年来，通过将反映关系数据具体语义的常量模式加入到标准函数依赖中，由此扩展而来的条件函数依赖(conditional functional dependency,CFD)在针对关系数据的一致性检测中取得了很好的效果[3, 4]。
在数据清洗中，一般都是由领域专家根据领域知识指定相应的依赖规则如FD、CFD等。但是随着数据库规模的不断增大、不同数据源之间的关系复杂化以及对数据实时性的不断提高，人工指定依赖规则的方法已无法满足数据质量管理的需求[5]。
CFD挖掘算法已经有相关的研究[1, 6]，例如常量条件函数依赖挖掘算法CFDMiner、变量条件函数依赖挖掘算法CTANE、深度优先条件函数依赖挖掘算法FastCFD等。其中对常量条件函数依赖(constant conditional functional dependency,CCFD)进行高效挖掘应用最为广泛的算法为CFDMiner[7, 8, 9]。
CFDMiner能够从开项集和相应的闭项集中高效地计算数据中的CCFD。挖掘开项集和闭项集的算法很多[10, 11, 12, 13, 14, 15, 16, 17, 18]，一般采用能够同时挖掘开项集和闭项集的算法如GcGrowth[10]。
过去对CCFD挖掘算法和CFDMiner优化的研究并不多，一方面是由于CFDMiner算法本身已经有很高的效率，通过其他方式(如通过关联规则挖掘[2])挖掘CCFD的算法很难超越CFDMiner； 另一方面，对于CFDMiner算法优化通常都集中在对候选开项集的研究[19]。但是GcGrowth挖掘全部开项集和闭项集已经非常高效，因此通过只产生有效的候选开项集的方式提高CCFD挖掘效率的效果非常有限。
CFDMiner的输入为数据的全部开项集和闭项集，本文首先证明了搜索全部开项集对于产生有效的CCFD存在大量的无效和冗余搜索，通过合理剪枝可以避免进行这些搜索，并且产生与原算法一致的CCFD正则覆盖集。实验证明： 提出的剪枝策略能缩小搜索空间，提高算法效率，使算法性能得到显著改善。
1 条件函数依赖的基本概念及依赖挖掘假设关系R建立在一组属性{A1,A2,…,Am}上，记作Attr(R)={A1,A2,…,Am}。I为R上的一个实例集，记作I|=R，t为I上的元组，即t∈I。Dorm(Ai)为属性Ai(i=1,2,…,m)的值域； t[Ai]为元组t在属性Ai上的取值。
定义1 满足I的一个FD记作： X→Y。其中属性子集X，Y⊂Attr(R),“→”表示“决定”关系，即当任意的元组ti,tj∈I,ti[X]=tj[X]时，都有 ti[Y]=tj[Y]。实例I满足φ: X→Y记作I|=φ。
定义2 满足I的一个CFD记作： (X→Y,tp[X‖Y])。其中：
1) 属性子集X,Y⊂Attr(R)，X→Y是标准函数依赖，“→”表示“决定”关系；
2) tp为X∪Y上的某个具体的取值模式(pattern)，即对于A∈X∪Y，tp[A]为变量值或者 Dom(A)中某个特定的常量值，“决定模式”X和“被决定模式”Y一般分别称为CFD的LHS(left hand side)和RHS(right hand side)。“‖”为LHS和RHS的分隔符。
定义3 满足I的一个CCFD记作： (X→Y,tpc[X‖Y])。其中：
1) 属性子集X,Y⊂Attr(R)，X→Y是标准函数依赖，“→”表示“决定”关系；
2) tpc为X∪Y上的某个具体的取值模式，即对于A∈X∪Y，tpc[A]为Dom(A)中某个特定的常量值。
表1为FD、CFD和CCFD的举例。根据上述定义，φ0~φ2分别为FD、CFD和CCFD。其中，φ1说明只有在指定的国家(数据中满足相应条件的记录)，地区码能够唯一地决定城市名(可能在其他国家不是这样)。φ2说明在指定的国家，某些城市(数据中满足相应条件的记录)和地区码有确定的一一对应关系(可能其他城市没有这样关系)，由此可以看出，FD和CCFD实际上是CFD的2个特例(FD的模式全部为变量，CFD的模式全部为常量)。
| 表达式 | 含义 |
| φ0:[CC,AC]→CT | FD： 国家码(CC)与地区码(AC)能够唯一地决定城市(CT)。 |
| φ1:([CC,AC]→CT,01_‖_) | CFD： 在美国(CC=01)，地区码(AC)能够唯一地决定城市。 |
| φ2:([CC,AC]→CT,01 908‖MH) | CCFD： 在美国(CC=01)，地区码(AC)为908，则城市一定为MH。 |
本文只关心RHS为单属性的CFD，这是因为对于(X→[A,B],tpc[X‖［A,B]］)形式的CFD，显然有(X→A,tpc[X‖A])和(X→B,tpc[X‖B])。
在数据质量研究中常量条件函数依赖CCFD受关注度最高，主要是因为： 1) CCFD是最底层模式的表达，不仅可以检查数据的一致性，同时可以检查一般条件函数依赖的一致性； 2) 利用CCFD可以产生一般条件函数依赖CFD[3]； 3) 数据清洗中，使用CCFD检查数据一致性简单可行，应用广泛[1]。因此，本文主要研究CCFD。
定义4 对于某一个实例I上的CCFD： φ=(X→A,tpc[X]‖a)，a∈DOm(A),1) 若A∉X，则φ为非平凡的CCFD； 反之，φ为平凡的CCFD； 2) 若 
Y⊂X，使得φ′=(Y→A,tpc[Y]‖a)成立，即B∈X，使得tpc[B]升级为变量之后的φ依然成立，则φ为非冗余的CCFD； 反之，φ为冗余的CCFD； 3) 将实例I上所有匹配φ的元组的集合记作supp(φ,I)，若此集合的元组数目
supp(φ,I)≥k，则φ为k-频繁的CCFD。
非冗余的CCFD又称为左极简(left-reduced)CCFD。对于CCFD而言，若φ1=([X,Y]→A,xy‖a)与φ2=(X→A,x‖a)同时成立，则φ1为冗余的CCFD。
显然，本文关心的是非平凡、非冗余、k-频繁的CCFD。
定义5 若Σ为CCFD集合，∀φ∈Σ都有(X→A,tpc[X]‖a)的形式，且是非平凡、非冗余的CCFD，则Σ是最小的CCFD。
定义6 若Σ是最小的CCFD集，且Σ包含了实例I上所有的k-频繁的CCFD，则Σ为I(k-频繁)的CCFD正则覆盖集。
定义7 挖掘一个实例I的CCFD正则覆盖集，称为该实例I的CCFD挖掘问题。
图1是由文[7]提出，应用最为广泛的挖掘CCFD的CFDMiner算法。
|
| 图1 常量条件函数依赖挖掘算法CFDMiner |
本文在分析CFDMiner的基础上，给出了算法优化策略。
2 算法分析与优化(剪枝)策略 2.1 CFDMiner算法分析首先介绍算法相关关键概念的定义：
定义8 形式如(X,tpc[X])的称为项集(itemset)，简写作(X,tpc)。其中属性子集X⊂Attr(R)，tpc为X上的某个具体的取值模式，即对于A∈X∪Y，tpc[A]为Dom(A)中某个特定的常量模式，或者记作tpc[X]⊂Dom(X)。实例I上匹配(X,tpc[X])的所有元组构成的集合，记为supp((X,tpc),I)，即为该项集的支持。集合内元组的数目为项集的支持度，记作|supp((X,tpc),I)|。
定义9 对于某个项集(X,tpc[X])，若存在项集(Y,spc[Y]),Y⊂X,spc[Y]=tpc[Y]，其中tpc[X]和spc[Y]分别是X和Y上具体的取值模式，则称(X,tpc[X])比(Y,spc[Y])更加具体(specific)，或者(Y,spc[Y])比(X,tpc[X])更加一般化(general)，记作(X,tpc[X])$ \prec $(Y,spc[Y])或者(Y,spc[Y])$ \succ $(X,tpc[X])。显然，supp((Y,spc[Y]),I)⊇supp((X,tpc[X]),I)。
1) 若(Y,spc)$ \succ $(X,tpc)，使得supp((Y,spc),I)=supp((X,tpc),I)，则(X,tpc)为开项集(free itemset)； 开项集在文[17, 18, 20]中也被称为生成器(generator)。
2) 若(Z,upc)$ \prec $(X,tpc)，使得supp((Z,upc),I)=supp((X,tpc),I)，则(X,tpc)为闭项集(closed itemset)；
3) 若存在一个开项集(Y,spc)和闭项集(Z,upc)，(Y,spc)$ \succ $(X,tpc)$ \succ $(Z,upc)，且
supp((Y,spc),I)=
supp((X,tpc),I)=supp((Z,upc),I),
GcGrowth算法输出的开项集、闭项集以及配对关系作为CFDMiner算法的输入(见图1第1行)。
根据图1第4-6行，首先按照配对关系，生成初始化的CCFD，假设算法的输入中有一初始的CCFD为(a,b)→(d,e)，初始的CCFD为非平凡但可能冗余的CCFD。
根据图1第8-10行，将初始CCFD中的冗余元素删去，则需要找出其LHS所有的非空真子集(如a→d,b→d)，并将其RHS中的元素减去，获得最终的CCFD(如(a,b)→e)即为CFDMiner的输出。
2.2 算法剪枝与优化对于CFDMiner，本节给出2个剪枝策略。
2.2.1 剪枝策略1定义10 若∃开项集(X,tpc)，其相应的闭项集clo(X,tpc)=(X,tpc)，则称(X,tpc)为平凡项集。
引理1 平凡项集不产生有意义的CCFD。
证明 根据CFDMiner(见图1第4-6行)，对于平凡项集产生的φ，有
LHS(φ)=(X,tpc),
RHS(φ)=(Y＼X,spc[Y＼X])=
(X＼X,spc[X＼X])=∅.
(1)
显然，由于平凡项集产生的φ的RHS(φ)=∅，因此对于LHS(φ)的任意超集 super(LHS(φ))，RHS(φ)不可能包含RHS(super(LHS(φ)))中的任意(冗余)元素。因此，计算CCFD不需要考虑平凡项集。
策略1 删除CFDMiner输入中所有的平凡项集。
2.2.2 剪枝策略2在下文的叙述中，(X,tpc[X])将简记作(X,tp[X])。
引理2 对于一个开项集(X,tp[X])与其对应的闭项集clo(X,tp[X])=(Y,sp[Y])，若存在该开项集的超集 X′⊇X0(X′,tp′[X′])，则对于其对应的闭项集clo(X′,lp′[X′])=(Y′,sp′[Y′])，有sp′[Y′＼X′]⊇sp[Y＼X]。
证明 假设sp′[Y′＼X′]
sp[Y＼X]，分2种情况讨论： 1) ∃A∈Y＼X且A∉Y′＼X′，sp[A]∉
sp′[Y′]； 2) ∃A∈Y＼X且A∈Y′＼X′，sp[A]≠sp′[A]。
对于假设1，因为X′⊇X，且(Y′,sp′[Y′])是(X′,lp′[X′])的闭项集，所以
supp(Y′,sp′[Y′])=supp(X′,lp′[X′])⊆
supp(X,tp[X])=supp(Y,sp[Y]),
t∈supp(Y′∪A,(sp′[Y′],sp[A])),
supp(Y′,sp′[Y′])⊆
supp(Y′∪A,(sp′[Y′],sp[A])).
supp(Y′,sp′[Y′])⊇
supp(Y′∪A,(sp′[Y′],sp[A])),
supp(Y′,sp′[Y′])=
supp(Y′∪A,(sp′[Y′],sp[A])).
对于假设2，因为X′⊇X，且(Y′,sp′[Y′])是(X′,lp′[X′])的闭项集，所以
supp(Y′,sp′[Y′])=supp(X′,tp′[X′])⊆
supp(X,tp[X])=supp(Y,sp[Y]),
综上，引理2得证。
定义11 对于某开项集(X,lp[X])，|X|=n，若其子集(Y,lp[Y])，|Y|=n-p(0＜p＜n)，则称(Y,lp[Y])为 (X,tp[X])的-p阶子集。
求某个开项集的-p阶全部子集记作 sub-p(X,lp[X])。若-p＞-q(p＜q)，则称为sub-p(X,lp[X])是比sub-q(X,tp[X])高阶的子集，记作
sub-p(X,lp[X])$\succcurlyeq$sub-q(X,lp[X]).
例如，开项集(a,b,c,d)的全部-2阶子集为sub-2(a,b,c,d)= {(a,b)(a,c)(a,d)(b,c)(b,d)(c,d)},-2阶子集合的第2和3个子集分别为sub-2(a,b,c,d)2=(a,c)和sub-2(a,b,c,d)3=(a,d)。
定义12 某开项集(X,tp[X])，|X|=n，其所有不包括空集的真子集按从高阶到低阶的顺序形成的集合树，称为子集全局树，简称子集树。子集树相邻层按隶属关系连线。
图2为开项集的子集树。
显然，对于(X,tp[X])树中的sub-k层中每个子集的-1阶子集的并集为sub-(k+1)层，即 sub-(k+1)(X,tp[X])= $\mathop \cup \limits_{j = 1}^{{C_k}^{n - k}} $sub-1(sub-k(X,tp[X])j),例如 sub-3(a,b,c,d)=∪6j=1sub-1(sub-2(a,b,c,d)j)。
|
| 图2 开项集(a,b,c,d)的子集树 |
引理3 开项集的-1阶子集模式必然是开项集。
证明 假设(X,tp[X])是开项集，存在一个(X1,tp[X1])∈sub-1(X,tp[X])不是开项集。
匹配(X,tp[X])的元组(即项集的支持)记为 T1=supp((X,tp[X]),T),T1⊆T, 因为(X,tp[X])是开项集，所以有： 1) T,T1的记录中不包含(X,tp[X])； 2) T,T1的记录中有包含(X1,tp[X1])的记录(否则(X,tp[X])不是开项集)。
不妨设T＼T1中匹配(X1,tp[X1])且不匹配(X＼X1,tp[X＼X1])的记录为T2，所以T中匹配(X1,tp[X1])的记录 supp((X1,tp[X1]),T)=T1∪T2, 且T＼(T1∪T2)的记录不匹配(X1,tp[X1])。
因为(X1,tp[X1])不是开项集，至少存在一个该项集的子集(X2,tp[X2])满足 supp((Xp,tp[X1]),T)=supp((X1,tp[X1]),T),所以T＼(T1∪T2)不匹配(X2,tp[X2])，T中匹配(X2,tp[X2])的记录也为T1∪T2。分2种情况讨论：
1) 假设T＼(T1∪T2)中有匹配(X＼X1,tp[X＼X1])的记录集T3，则T中匹配(X＼X1,tp[X＼X1])的记录为 T1∪T3，包含(Xp,tp[X2])的记录为 T1∪T2，匹配((X＼X1,X2),tp[X＼X1,X2])的记录 supp(((X＼X1,X2),tp[X＼X1,X2]),T)= supp((X,tp[X]),T), 而((X＼X1,X2),tp[X＼X1,X2])⊂(X,tp[X])， 所以(X,tp[X])不是开项集，与题设矛盾；
2) 假设T＼(T1∪T2)中没有匹配(X＼X1,tp[X＼X1])的记录集，则T中匹配(X＼X1,tp[X＼X1])的记录为T1，包含 (X2,tp[X2])的记录为T1∪T2，匹配((X＼X1,X2),tp[X＼X1,X2]的记录 supp(((X＼X1,X2),tp[X＼X1,X2]),T)=T1, 即 supp(((X＼X1,X2),tp[X＼X1,X2]),T)= supp((X,tp[X]),T),((X＼X1,X2),tp[X＼X1,X2])⊂(X,tp[X]), 所以(X,tp[X])不是开项集，与题设矛盾。
因此，假设均不成立，即若(X,tp[X])是开项集，则任意的(X1,tp[X1])∈sub-1(X,tp[X])都是开项集。
推论1 开项集的所有子集都是开项集。
证明 开项集(X,tp[X])的-(k+1)阶子集与-k阶子集的关系为
sub-(k+1)(X,tp[X])=∪Cnkj=1sub-1(sub-k(X,tp[X])j),
sub-2(X,tp[X])=∪Cn1j=1sub-1(sub-1(X,tp[X])j),
sub-3(X,tp[X])=∪Cn2j=1sub-1(sub-2(X,tp[X])j),…，
推论2 对于开项集(X,tp[X])，其-1阶子开项集为sub-1(X,tp[X])，-1 阶子集所对应的闭项集记作 clo(sub-1(X,tp[X]))= ∪Cnn-1j=1clo(sub-1(X,tp[X])j), 则有： clo(sub-1(X,tp[X]))⊇ ∪n-1k=1clo(sub-k(X,tp[X]))。
证明 根据引理2，对于一个开项集(X,tp[X])与其对应的闭项集clo(X,tp[X])，若存在该开项集的超集 (X′,tp[X′]),X′⊇X，则其对应的闭项集 clo(X′,tp[X′])⊇clo(X,tp[X])。
因为 sub-1(X,tp[X])⊇ sub-k(X,tp[X]) (k=1,2,…,n-1), clo(sub-1(X,tp[X]))⊇ clo(sub-k(X,tp[X])), 所以 clo(sub-1(X,tp[X]))⊇ ∪n-1k=1clo(sub-k(X,tp[X]))。
策略2 CFDMiner算法中(图1第8行)只需要搜索该开项集的-1阶子集即可。
根据引理3，开项集的子集必然是开项集。因此，GcGrowth输出的开项集能够覆盖全部开项集的子集。
根据推论2，开项集的全部-1阶子集对应的闭项集，包含了所有非空真子集对应的闭项集的元素。因此只需搜索此开项集的-1阶子集，即能获得全部子集对应的闭项集模式。
2.2.3 优化算法prCFDMiner根据上述的剪枝策略，对CFDMiner进行优化，图3是剪枝后的prCFDMiner算法：
|
| 图3 基于剪枝策略的优化算法prCFDMiner 基于剪枝策略的优化算法prCFDMiner |
由图3的第5-7行和10-12行可见，prCFDMiner主要是根据策略1和2分别对CFDMiner进行了优化。
3 算法复杂度分析对比由对CFDMiner的分析可见，算法分为3步：
步骤1根据配对关系，计算初始化的CCFD，其复杂度为O(n)，n为输入开项集数目，见图1第4-6行；
步骤2对于每一个开项集，搜索其在列表中的子集，见图1第8行，有2种搜索策略：
1) 将n个开项集以列表形式存储，对于每一个开项集，在整个列表中搜索非空真子集，则每一个开项集的搜索空间为(n-1)，所有开项集的搜索空间为n(n-1)；
2) 将n个开项集以哈希映射(HashMap)的形式存储，对于每一个开项集(假设项集的平均长度为l)，首先计算其所有的非空真子集，假设计算和搜索一个真子集均需要1个时间单位，则所有开项集的计算和搜索时间为2n(2l-2)。
当数据集的属性值固定，支持度变化时，挖掘出的开项集的平均长度通常是固定的(一般小于属性个数的50%)。但是随着支持度的降低，前者的搜索策略的时间复杂度为O(n2)，而后者为O(n)。因此，通常采用后者的搜索策略。
步骤3 对于每一个开项集(假设平均长度为l)，假设在整个列表中找到的真子集数目为(2l-2)，计算最终的CCFD的时间为(2l-2)，所有n个开项集的计算时间为n(2l-2)；
由以上分析可知，通过合理的选择存储方式和搜索策略，CFDMiner算法对于输入开项集的复杂度为O(n)。
本文给出的优化和剪枝策略主要是针对CFDMiner算法的步骤1和步骤2。
在步骤1中剪去了无意义的输入(即不会产生有效CCFD的开项集)，见图3第5-7行。假设全部开项集的数目为n，其中平凡项集的数目为 n1(n1＜n)，则在步骤1中节省了n1个时间单位。
在步骤2中，CFDMiner算法需要搜索全部的真子集，在所有开项集的平均长度为l的情况下，计算和搜索全部真子集需2n(2l-2)个时间单位。经过剪枝后的prCFDMiner算法，只需搜索每个开项集的-1阶真子集，所以计算和搜索全部-1阶真子集需2nl个时间单位，两者时间比为(2l-2)/l。可见，若开项集的平均长度为5和10，则理论效率分别约提高6和100倍。
4 实验验证与结果分析 4.1 实验数据集与配置为了验证优化后的算法prCFDMiner是否与CFDMiner得到一致的结果以及是否在效率上有所提升，选取了3个UCI公共数据集(http://archive.ics.uci.edu/ml/)进行测试。由于算法的输入是由GcGrowth算法根据预设的支持度输出的开项集和闭项集的配对，因此表2列出了数据集的相关属性，以及不同支持度下输出的开项集和闭项集的配对数目。
| 数据集 | 属性个数 | 记录条数 | 开项集和闭项集配对数 | |||||||
| 支持度/%=50 | 30 | 10 | 5 | 1 | 0.5 | 0.3 | 0.1 | |||
| Adult | 12 | 32 561 | 18 | 72 | 725 | 2 360 | 24 260 | 57 869 | 101 990 | 296 250 |
| Mushroom | 23 | 8 124 | 51 | 558 | 7 631 | 21 160 | 103 517 | 164 526 | 235 013 | 360 166 |
| Chess | 7 | 28 076 | 1 | 5 | 47 | 122 | 1 210 | 2 997 | 4 955 | 18 908 |
对于Mushroom和Chess数据集，在预处理时只需根据GcGrowth算法要求对数据进行数字化即可； 对于Adult数据集，首先删去了3个连续型属性，对剩下的属性进行数字化。实验代码使用Java编写，在JVM上运行。硬件平台为Intel Xeon 处理器(频率为2.5 GHz)，内存为64 GB。
4.2 实验结果经验证，prCFDMiner与CFDMiner得到结果是一致的，即输出的CCFD相同，表3列出了不同支持度下输出的CCFD数目。
| 数据集 | 输出CCFD的数目 | |||||||
| 支持度/%=50 | 30 | 10 | 5 | 1 | 0.5 | 0.3 | 0.1 | |
| Adult | 0 | 2 | 7 | 27 | 288 | 692 | 1 324 | 7 700 |
| Mushroom | 27 | 95 | 2 774 | 7 510 | 26 029 | 37 040 | 46 498 | 60 886 |
| Chess | 0 | 0 | 0 | 2 | 7 | 15 | 36 | 327 |
为了比较策略1和2对算法优化的影响，本文分别对原算法CFDMiner、经策略1优化后的算法CFDMinerS、经策略1和2结合优化后的算法prCFDMiner的搜索空间和搜索时间等指标进行测试，实验结果如图4所示。可以看出：
|
| 图4 不同优化策略在搜索空间、平均存储空间和搜索时间上的性能对比 |
1) 随着支持度的降低，输入的开闭项集对的增多，算法的搜索空间和搜索时间逐渐增大，表3也同时说明了挖掘出的CCFD逐渐增多；
2) 同一支持度下，prCFDMiner算法搜索开项集的数目和搜索时间总是要明显少于CFDMiner； CFDMinerS算法在Adult和Chess数据集上的性能有明显的提升，而在Mushroom数据集上性能几乎没有改善，因为Mushroom不产生“平凡项集”；
3) 图4d-4f的平均存储空间实际上反映的是项集的平均长度，即对于每一个开项集平均所需计算的子集的数目。例如在图4d中，0.5%的支持度下，CFDMiner算法的平均存储空间多于30个开项集，而prCFDMiner算法的为4~5个。这与理论分析基本一致： CFDMiner的对于每个项集需计算(2l-2)个项集，而prCFDMiner算法只需要计算l个项集；
4) 由上可知，prCFDMiner算法与CFDMiner的搜索时间比约为l/(2l-2)，这在图4g-4i中也得到了相应的验证。
需要说明的是，文[2, 19]是直接在数据集上挖掘CCFD，而CFDMiner则是在已挖掘出的开闭项集上计算CCFD(prCFDMiner在此基础上剪枝)，因此prCFDMiner与文[2, 19]可比性不强。CFDMiner和prCFDMiner的优点在于借助了已有丰富的挖掘开闭项集的算法成果，使得CCFD的挖掘更加简便。文[19]中FACD算法仍然是通过从数据中直接限制产生冗余的候选项集的方式计算CCFD，但FACD会随着数据集属性的增多，算法性能下降。而CFDMiner算法是在开闭项集基础上搜索CCFD，其计算能力受属性个数影响不大(从本文实验选取的不同数目属性的数据集的实验中可得到验证)。
5 结 论本文对常量条件函数依赖的常用算法CFDMiner进行了剪枝和优化，通过比较搜索策略的复杂度，证明了可以在O(n)的复杂度下完成CFDMiner的运算，这也是实施优化策略的基础； 证明了剪枝优化策略能够得到与原算法一致的结果，并通过实验得到了相应的验证； 优化后的算法在搜索空间、平均存储空间和搜索时间上的性能都得到了明显的提升； 实验证明了不同策略在不同的数据集下对算法优化的影响程度，策略2具有普适性即总是会提升算法效率，而策略1对数据集的特点有一定要求即数据集需要存在“平凡项集”。
| [1] | Fei C, Miller R J. Discovering data quality rules[C]//Proceedings of 34th International Conference on Very Large Data Bases. Auckland, New Zealand:VLDB Endowment, ACM, 2008:1166-1177. |
| [2] | Diallo T, Novelli N, Petit J M. Discovering (frequent) constant conditional functional dependencies[J]. International Journal of Data Mining, Modelling and Management, 2012, 4(3):205-223. |
| [3] | Fan W, Geerts F, Jia X, et al. Conditional functional dependencies for capturing data inconsistencies[J]. ACM Transactions on Database Systems, 2008, 33(2):1-48. |
| [4] | Fan W. Dependencies revisited for improving data quality[C]//Proceedings of 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008. Vancouver, BC, Canada:ACM, 2008:159-170. |
| [5] | 刘波, 耿寅荣. 数据质量检测规则挖掘方法[J]. 模式识别与人工智能, 2012, 25(5):835-844. LIU Bo, GENG Yinrong. Mining method for data quality detection rules[J]. Pattern Recognition and Artificial Intelligence, 2012, 25(5):835-844. (in Chinese) |
| [6] | Golab L, Karloff H, Korn F, et al. On generating near-optimal tableaux for conditional functional dependencies[C]//Proceedings of 34th International Conference on Very Large Data Bases. Auckland, New Zealand:VLDB Endowment, ACM, 2008:376-390. |
| [7] | Fan W, Geerts F, Lakshmanan L V S, et al. Discovering conditional functional dependencies[C]//Proceedings of the 25th International Conference on Data Engineering (ICDE). Shanghai, China:IEEE, 2009:1231-1234. |
| [8] | Fan W, Geerts F, Li J, et al. Discovering conditional functional dependencies[J]. IEEE Transactions on Knowledge & Data Engineering, 2011, 23(5):683-698. |
| [9] | Fan W, Geerts F. Foundations of data quality management[M]. San Rafael, CA, USA. Morgan & Claypool, 2012. |
| [10] | Li H, Li J, Wong L, et al. Relative risk and odds ratio:A data mining perspective[C]//Proceedings of 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2005. Baltimore, MA, USA:ACM, 2005:368-377. |
| [11] | Agrawal R. Fast algorithms for mining association rules[C]//Proceedings of 20th International Conference on Very Large Data Bases. Santiago, Chile:ACM, 1994:487-499. |
| [12] | Goethals B, Zaki M J. Frequent itemset mining implementations[C]//Proceedings of the ICDM 2003 Workshop on Frequent Itemset Mining Implementations. Melbourne, FL, USA:IEEE, 2003:1-13. |
| [13] | Pasquier N, Pasquier N, Bastide Y. Discovering frequent closed itemsets for association rules[J]. Lecture Notes in Computer Science, 2000,1540:398-416. |
| [14] | Wang J, Han J, Pei J. CLOSET+:Searching for the best strategies for mining frequent closed itemsets[C]//Proceedings of 9th International Conference on Knowledge Discovery and Data Mining. Washington, DC, USA:ACM, 2003:236-245. |
| [15] | Zaki M J. Mining Non-redundant association rules[J]. Data Mining & Knowledge Discovery, 2004, 9(3):223-248. |
| [16] | Calders T, Goethals B. Non-derivable Itemset Mining[J]. Data Mining & Knowledge Discovery, 2007, 14(1):171-206. |
| [17] | Li J, Li H, Wong L, et al. Minimum description length principle:generators are preferable to closed patterns[C]//Proceedings of 21st AAAI Conference on Artificial Intelligence and 18th Innovative Applications of Artificial Intelligence Conference. Las Vegas, NE, USA, 2006:409-414. |
| [18] | Li J, Liu G, Wong L. Mining statistically important equivalence classes and delta-discriminative emerging patterns[C]//Proceedings of 13th SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose, CA, USA:ACM, 2007:430-439. |
| [19] | Li J, Liu J, Toivonen H, et al. Effective pruning for the discovery of conditional functional dependencies[J]. The Computer Journal, 2013, 56(3):378-392. |
| [20] | Tran A, Truong T, Le B. Simultaneous mining of frequent closed itemsets and their generators:Foundation and algorithm[J]. Engineering Applications of Artificial Intelligence, 2014, 36:64-80. |