面向不确定数据模式指标的通用界值估算方法

王 菊，刘付显，靳春杰

(1.空军工程大学 防空反导学院，西安 710051； 2. 93527部队，河北 张家口 075000)(*通信作者电子邮箱yonglingjuke@126.com)

0 引言

作为频繁模式挖掘的拓展，基于约束的模式挖掘近年来引起了越来越多的关注[1-2]。当前关于该问题的研究主要集中在如何将不同的模式指标融入到算法的执行过程中以减小搜索空间，尤其是针对难约束指标[3-5]。其中一个通用处理办法就是估计给定项集X的所有超集关于模式指标的一个上/下界。如果这个界值小于/大于一个给定的最小/最大阈值，那么X的所有超集就要从全集中被剪除[6]，因此，模式指标的界值估算是约束模式挖掘中的一个核心问题。

当前虽然在实际应用的驱动下，一些模式指标及其上界的估算方法已经被提出，如模式效用[7-8]、模式占有度[9]和有权置信度[10]等，但是这些研究的局限性在于它们不具有普遍性，即每当一个新的难约束指标被提出时，都需要花费较大代价去找到相应有效的上/下界，因此，文献[11]提出了一种基于带有权值的确定型事务数据库的通用界值估算方法，但是，该文献中所提出的方法没有指明在带有权值的不确定型事务数据库上如何进行运算。

为此，针对在带有权值的不确定型事务数据库上模式指标的界值估算问题，本文提出了一种通用的估算方法，在传统界值估算方法的基础上，增加了处理不确定性的功能。其基本思想是在给定项集满足最小支持度阈值的情况下，通过采用不考虑项标记而只考虑支持数据库中出现项的权值和存在概率的策略，使得模式指标值在相应的事务中达到最大或者最小。

1 问题阐述

1.1 数据库模型

当前关于模式指标的界值估算方法大多基于确定型数据库，少有关于该问题在不确定型数据库上的探讨。针对这一不足，本文将侧重于研究带有权值的不确定型事务数据库D={T1,T2,…,Tq,…,Tm}。其中，m表示该数据库中事务的数量；当D中包含的所有项的数量为L时，可以用有限集合I={i1,i2,…,ip,…,iL}表示该数据库中的所有项，此时该数据库中的任意一个事务Tq代表I中有限数目的项，被表示为Tq={i1,i2,…,il}(1≤l≤L)；任意一个项ip都对应于一个权值u(ip,Tq)和一个存在概率p(ip,Tq)，它们分别表示ip在事务Tq中的权值和ip存在于事务Tq中的概率。

不难发现，这种带有权值的不确定型事务数据库可以作为一般常用数据库的通用形式。例如当所有权值为1时，该数据库可以退化为一个不确定型事务数据库；当所有存在概率值都为1时，该数据库可以退化为一个带有权值的确定型事务数据库。表1是一个带有权值的不确定型事务数据库的示例。

表1 带有权值的不确定型事务数据库示例

表1中的不确定型事物数据库可以被表示为D={T1,T2,…,T8}，有限集合I={A,B,C,D,E,F,G}，各个事务所包含的项以及项中对应的权值和概率信息在表1中都有明确的表示。在实际应用中，表1中的(A,3,0.81)可以解释为购物者T1会以概率0.81购买项A，它带给零售商的利润值(权值在该应用中的实际含义)为3。在该应用中，那些购物者会以高概率购买且能带来高利润值的项或项集是零售商们所欢迎的商品或商品集。

1.2 模式指标定义

为发现在带有权值的不确定型事务数据库中以高概率出现且具有高权值的项集，本文定义了模式指标PI来综合评估项集的权值和存在概率。其主要需要三个输入：项集的支持数据库以及每个项在其出现事务上的权值与存在概率。模式指标PI的数学形式可以定义为：

(1)

其中：X表示数据库D中的任意一个项集；DX表示项集X的支持数据库；U表示DX中项到权值的映射；P表示DX中项到存在概率的映射。

根据模式指标PI对项集进行综合评估时，常采用“当模式指标PI满足一定条件时，其相应的项集为高概率出现且具有高权值的项集；否则就不是该类项集”这样的约束形式，因此本文将模式指标PI转换为约束：

(2)

这个约束可以进一步简化为：

PI(X,D,U,P)≥或≤β

(3)

其中：β∈R+。

通常不同的指标约束具有不同的性质，常用的可以用于缩减搜索空间的性质有：单调性、简洁性、可转换单调性、松散反单调性、灵活性、有界性等，但是在实际应用过程中，有很多约束不满足所有这些可缩减搜索空间的性质，这类约束被统称为难约束。为降低计算复杂度，减小搜索空间，对难约束的一个通用处理办法就是估计给定项集X的所有父项集关于给定模式指标PI的一个上/下界。如果这个界值小于/大于一个给定的最小/最大阈值，那么X的所有超集就要从全集中被剪除。当前针对某个或某几个特定的难约束，相关学者分别提出了其相应的上/下界，但是这些研究的局限性在于每当一种模式指标被提出时，都要花费较大的代价去计算其上/下界。

因此，本文通过分析带有权值的不确定型事务数据库的特点和之前关于特定难约束指标界估计方法的相同点，提出了一种面向不确定数据模式指标的通用界值估算方法。该方法可以在带有权值的不确定型事务数据库上对新的难约束指标进行高效的界值估算，其研究思路和通用估算方法将在下文中展开详细论述。

2 研究思路

给定项集X，模式指标PI的界值估算问题就是研究如何能够快速计算出所有X的超集关于PI的一个上/下界。一种非常直接但耗时的解决方案就是分别计算项集X所有超集的模式指标值，然后选择其中最大/小值作为X的超集关于PI的上/下界，这种方法的运算次数正比于2|I|-|X|，呈现出了指数增长。为提高上述界值估算方案的效率，本文通过不考虑项标记而只考虑支持数据库中出现项的权值和存在概率，设计了如2.2节中所示的基本框架。此外，由于θ=‘≤’的情况与θ=‘≥’的情况在研究方法与内容上类似，下文在不加以说明的位置都只估算了模式指标的上界，即θ=‘≥’的情况。

2.1 符号说明

由于文中涉及到的符号较多，本节就这些符号进行说明，如表2所示。

表2 符号说明

例如在表1的示例中，LT=[5,3,2,3,2,4,3,4]。当X={AC}时，DX={T1,T4,T6}，XS=[1,4,6]，LS=[3,1,2]，LSp=[3,2,1]，|X|=2，将期望支持度sX按照文献[12]中的定义进行计算后得2.204 8，此时相应的Pu和Su矩阵在采用不考虑项标记而只考虑支持数据库中出现项的权值和存在概率的策略后，如图1所示。

图1 当X={AC}时表1数据库的变形

从图1中可知，当X={AC}时，Pu(4,1)=18，Su(6,2)=4，图1中没有显示的矩阵值都为0，例如Pu(2,2)=0，Su(4,2)=0。

2.2 基本框架

针对带有权值的不确定型事务数据库D，给定项集X、模式指标PI以及最小期望支持度阈值σ，上述界值估算问题的基本研究框架如下。

输入：不确定型事务数据库D，项集X、模式指标PI以及最小期望支持度阈值σ。

输出：X的超集关于PI的一个上界。

计算项集X的期望支持度sX

IfsX<σ

Return 0;

Else

对于一组给定的α和β，提出一个函数F(α,β,sX,Pu,Su)满足条件：PI(X′,DX′,U,P)≤F(α,β,sX,Pu,Su);

Forα=1:|DX|

Forβ=0:LSp(1)

A(α,β)=F(α,β,sX,Pu,Su)；

End

End

Return max(A)

End

其中LSp(1)表示DX中相对于X的最大扩展长度。采用表2中的基本框架，只要计算|DX|×(LSp(1)+1)次函数F的值，呈现出了线性增长的方式。相比分别计算项集X所有超集的模式指标值所带来的指数级增长，缩减了计算空间。例如在表1的示例中，当X={AC}时，采用直接计算的方式，计算次数为27-2=32次，而采用表2中的方法只要计算3×(3+1)=12次函数F的值即可。

3 界值的快速估算方法

在上述基本框架中，为快速估算出X的超集关于PI的上界值，本章主要围绕两个问题展开研究：一是当给定一组α和β时，怎样高效地计算出函数F的值；二是怎样遍历α,β的取值，才能尽快得到上界值。

3.1 函数F的计算方法

针对项集X，对于一组α和β，虽然采用遍历矩阵Pu和Su的方法可以计算出函数F的值，但是需要花费较长的计算时间，进而降低了上界估算方法的效率。本节提供了一种快速计算F(α,β,sX,Pu,Su)的方法，其具体流程如下。

步骤1 当LS(i)<β(1≤i≤|LS|)时，从向量XS中剔除相应的XS(i)得到XSβ，从而确定可能包含X′的候选事务集C(由于X′相对于X的扩展长度为β，因此当X在其支持事务上的后缀长度小于β时，该事务中一定不包含X′)。

步骤2 根据候选事务集C和XSβ中存储的事务编号，将Su(XSβ(j),max(LS))(1≤j≤|XSβ|)中的元素按照由大到小的顺序需进行排序得到Sup(XSβ(j),max(LS))，进而对Sup(XSβ(j),max(LS))中前β个元素的模式指标值进行求和得到sumβ。

步骤3 对Pu(XSβ(j),max(LS))中前|X|个元素的模式指标值进行求和得到sum|X|，进而可以得到局部上界值sumβ+sum|X|。

步骤4 从步骤3中得到的所有局部上界值中选出前α个最大值，对它们进行求和后得到函数F的值。

3.2 α和β之间的关系

在3.1节所示的F函数计算方法中可以发现：X′相对于X的扩展长度β可以影响到可能包含X′的事务个数α。这意味着α和β在所提的计算方法中不是两个相互独立的参数，它们之间存在一定的关系。本节就它们之间的相互关系进行研究，主要分为两个部分：一是当α值固定时，研究β的取值范围；二是当β固定时，研究α的取值范围。

1)当α值固定时。

(4)

2)当β值固定时。

(5)

采用表2中的搜索方法，至少要计算|DX|×(LSp(1)+1)次函数F的值，但是基于α和β之间的关系后，运算次数变为(LSp(1)+1)+(LSp(2)+1)+…+(LSp(|DX|)+1)。由于LSp(1)≤LSp(2)≤…≤LSp(|DX|)，因此就有(LSp(1)+1)+(LSp(2)+1)+…+(LSp(|DX|)+1)≤(LSp(|DX|)+1)+(LSp(|DX|)+1)+…+(LSp(|DX|)+1)=|DX|×(LSp(1)+1)。也就是说基于α和β之间的关系，可以进一步减小搜索空间，降低对F函数的计算次数，进而可以提高模式指标PI上界值的估算效率。例如在表1的示例中，当X={AC}时，采用表2中的计算方法要计算3×(3+1)=12次函数F的值，而采用上述α和β之间的关系后，计算次数可以减为(3+1)+(2+1)+(1+1)=9。

除此之外，根据部分模式指标所设计的函数具有单调性、有界性等性质，基于这些性质可以进一步地缩减搜索空间，提高计算效率，但是由于本文的主要研究内容是通用模式指标的界值估算问题，关于这些具有特定性质的F函数如何进一步地减小搜索空间不在本文的研究内容之中，因此文中没有对这些性质的应用问题作详细论述。

4 举例说明

在基于约束的模式挖掘问题中，一些常用的难约束模式指标有模式效用、模式占有度、块模式指标以及有权置信度等。本章以模式效用和模式占有度为例，说明文中所提出的基本框架及方法可以应用于这些模式指标的界值估计。

模式效用是一种典型的难约束，其在带有权值的不确定型事务数据库上的计算方法如定义1所示，本章将给出其F函数的具体形式及相应的上界。

定义1 项集的效用值。针对带有权值的不确定型事务数据库D，项集X的效用值被定义为项集X在其支持事务上的效用值总和，被表示为：

(6)

例如项集{AC}，其最小期望支持度s{AC}=2.204 8，因此当σ=2时，效用值μ(AC)=3+5+18+11+25+17=79；当σ=3时，效用值μ(AC)=0。

按照2.2节中的基本框架和第3章中的估算方法，针对项集X和一组给定的α和β，可以将函数F用数学表达式(8)表示且该函数满足性质1。

F(α,β,sX,Pu,Su)=

(7)

性质1 当X′的扩展长度为β，支持事务个数为α时，该项集在带有权值的不确定型事务数据库上的模式效用满足：

μ(X′)≤F(α,β,sX,Pu,Su)

(8)

证明 当sX′<σ时，μ(X′)=F(α,β,sX,Pu,Su)=0，满足式(8)。

当sX′≥σ时，由于

因此不等式

成立。

根据性质1，可以很容易得到项集X所有父项集关于模式效用的一个上界：

(9)

例如表1中的示例，当最小期望支持度阈值σ=3时，项集{AC}的模式效用上界为0；当最小期望支持度阈值σ=2时，项集{AC}的模式效用上界为：

根据式(8)可得：

F(3,0,sX,Pu,Su)=8+29+42=79

F(3,1,sX,Pu,Su)=24+38+66=128

F(2,2,sX,Pu,Su)=36+70=106

F(1,3,sX,Pu,Su)=44

模式占有度也是一种典型的难约束，其计算方法如定义2所示。

定义2 项集的占有度。针对带有权值的不确定型事务数据库D，项集X的占有度被定义为：

(10)

同理，根据2.2节中的基本框架和第3章中的估算方法，可以得到模式占有度的F函数以及上界的表达式分别如式(11)和(12)所示：

F(α,β,sX,Pu,Su)=

(11)

(12)

5 实验结果与分析

模式效用是一种常用的模式指标，本文实验中以模式效用为例，用于验证所提通用模式指标上界估算方法在带有权值的不确定型事务数据库上的有效性。由于在带有权值的不确定型事务数据库上关于高效用模式挖掘问题的研究极少，目前只有UHUI-Apriori(High Utility Itemsets mining from Uncertain datasets based on Apriori)[13]、PHUI-UP(Potential High-Utility Itemsets UPper-bound-based mining)和PHUI-List(Potential High-Utility Itemsets PU-list-based mining)[14]算法可用于解决该问题，且都需要估算模式效用在不确定型事务数据库上的界值，因此这些算法的实验过程和结果都很相似。为了验证所提通用上界估算方法的有效性，以PHUI-UP算法为牵引，分别采用项集的事务加权效用值(Transaction Weighted Utilization, TWU)、本文方法所得的上界估算值和实际上界值来减少该算法在带有权值的不确定型事务数据库上挖掘高效用模式时所产生的候选项集。实验中，本文对比了PHUI-UP算法在上述3种界值计算方法下的运行时间和内存占用情况，实验数据集和实验结果下文分别进行介绍。

所有的算法都用Matlab实现，运行在一台装有32位Windows 7操作系统的台式计算机上。该计算机带有两个因特尔酷睿i5- 4590处理器和4 GB的RAM。

5.1 实验数据集

本节实验运行在人工数据集T10I4D100K和实际数据集mushroom、connect和accidents上。它们是关于高效用模式挖掘问题的常用数据集，其参数和特点分别如表3～4所示。

表3 所使用数据集的参数

表4 所使用数据集的特点

为满足PHUI-UP算法对数据集的要求，根据文献[15]所提出的仿真模型生成分别在区间[1,1 000]和[1,5]中的服从对数正态分布的随机数来模拟这些数据集中外部效用值和内部效用值。此外，生成(0,1)区间的均匀随机数来模拟这些数据集中的概率信息。本文方法中所采用的权值对应于PHUI-UP算法中的效用值，即数据集中每个项的内部效用与其相应外部效用的乘积。

5.2 结果分析

当给定最小期望支持度阈值σ=2时，在本节的实验中比较了PHUI-UP算法在分别采用上述3种上界值后的运行时间和内存使用情况，分别如图2～3所示。

从图2～3中可以看出，当PHUI-UP算法采用TWU时，该算法的运行时间和所占用内存都是最少的，尤其是在稀疏数据集T10I4D100K，这是因为TWU是通过事务的权值来松散地估算项集的权值，计算复杂度较小。当本文中的上界值估算方法和PHUI-UP算法相结合后，运行时间和占用内存相对于TWU都略大，造成这个结果的原因主要有两个：一是本文所提出的界值估算方法是一种通用的方法，不只是适用于高效用模式的上界估计，因此相比TWU有较大的计算复杂度；二是由于本文所提出的界值估算方法用被估算项集的权值及其后缀中项的权值来估算该项集权值的上界，因此在计算过程中需要重复的读取数据集中的数据。此外，从图2～3中还可以看出，PHUI-UP算法在采用TWU和本文方法所估算的界值后，运行时间和占用内存都比在采用实际上界值时少很多，这是由于实际上界值的计算过程中需要分别计算项集X所有超集的权值，计算复杂度非常高。

图2 不同上界值计算方法下PHUI-UP的运行时间

图3 不同上界值计算方法下PHUI-UP的内存占用情况

因此，通过上述的实验结果和分析，可以得出结论：本文所提出的上界估算方法省去了针对不同难约束模式指标都需要估算其相应上界的过程，代价是相对于这些特定的上界可能会占用较多的运行时间和内存，但是相对于计算项集的实际上界值，本文所提出的方法仍然节省了大量的运行时间和内存。

6 结语

针对约束模式挖掘中模式指标的界值估算问题，本文在带有权值的不确定型事务数据库上提出了一种通用上/下界计算方法，建立了对难约束指标进行上/下界值估算的统一框架，可以快速实现对候选项集的剪除。

本文提出了一种面向不确定数据模式指标的通用上/下界估算方法，通过对比PHUI-UP算法分别与TWU、本文方法和实际上界值相结合后的运行时间和内存占用情况，验证了本文方法的可行性和有效性。

本文所建立的通用上/下界值估算方法都是面向形如PI(X,D,U,P)≥或≤β的模式指标，在后续的研究中可以通过考虑一些其他形式的模式指标约束来改进该方法。不确定性理论、智能搜索算法与通用上/下界值估算方法的结合也将是下一步的研究内容。

References)

[1] ZHU F, ZHANG Z, QU Q. A direct mining approach to efficient constrained graph pattern discovery [C]// SIGMOD 2013: Proceedings of the 2013 Special Interest Group on Management of Data. New York: ACM, 2013: 821-832.

[2] GUNS T, NIJSSEN S, RAEDT L.K-pattern set mining under constraints [J]. IEEE Transaction on Knowledge and Data Engineering, 2013, 25(2): 402-418.

[3] ZENG X, PEI J, WANG K, et al. PADS: a simple yet effective pattern-aware dynamic search method for fast maximal frequent pattern mining [J]. Knowledge and Information Systems, 2009, 20(3): 243-252.

[4] GAO L. Domain-driven data mining: challenges and prospects [J]. IEEE Transaction on Knowledge and Data Engineering, 2010, 22(6): 755-769.

[5] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases [C]// SIGMOD’ 93: Proceedings of the 1993 ACM Special Interest Group on Management of Data. New York: ACM, 1993: 207-216.

[6] BONCHIA F, GIANNOTTIB F, LUCCHESB C, et al. A constraint-based querying system for exploratory pattern discovery [J]. Information Systems, 2009, 34(1): 3-27.

[7] YAO H, HAMMILTON H J, BUTZ C J. A foundational approach to mining itemset utilities from databases [C]// SDM 2004: Proceedings of the 2004 Siam International Conference on Data mining. New York: ACM, 2004: 482-486.

[8] WU C, SHIE B, TSENG V, et al. Mining top-Khigh utility itemsets [C]// KDD 2012: Proceedings of the 2012 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 78-86.

[9] TANG L, ZHANG L, LUO P, et al. Incorporating occupancy into frequent pattern mining for high quality pattern recommendation [C]// Proceedings of the 2013 ACM International Conference on Information and Knowledge Management. New York: ACM, 2013: 75-84.

[10] YUN U. Efficient mining of weighted interesting patterns with a strong weight and/or support affinity [J]. Information Sciences, 2007, 177(17): 213-241.

[11] 张磊.基于约束的频繁模式挖掘方法[D].合肥：中国科学技术大学，2014:73-116.(ZHANG L. Constraint-based frequent pattern mining: novel applications and new techniques [D]. Hefei: University of Science and Technology of China, 2014: 73-116.)

[12] GREEN T, TANNEN V. Models for incomplete and probabilistic information [C]// Proceedings of the 2006 IEEE International Conference on Extending Database Technology. Piscataway, NJ: IEEE, 2006: 278-296.

[13] LIN C W, HONG T P, LU W H. An effective tree structure for mining high utility itemsets [J]. Expert Systems with Applications, 2011, 38(6): 7419-7424.

[14] LIU M, QU J. Mining high utility itemsets without candidate generation [C]// KDD 2012: Proceedings of the 2012 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 78-86.

[15] LIU Y, LIAO W, CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets [C]// Proceedings of the 2005 Pacific-Asia Conference on Knowledge Discovery and Data Mining. New York: ACM, 2005: 689-695.

WANGJu, born in 1991, Ph. D. candidate. Her research interests include data mining, pattern recognition.

LUIFuxian, born in 1962, Ph. D., professor. His research interests include simulation of warfare, data mining.

JINChunjie, born in 1989, assistant engineer. His research interests include data mining, pattern recognition.