一种基于不确定数据的频繁模式分布式挖掘算法研究

李 峰

（湖南工程学院 计算机与通信学院，湘潭 411104）

0 引言

现实世界数据分为两类：精确数据和不确定数据.在精确数据中人们必须精确知道相互作用数据的质量，而在不确定数据中，由于人们无法精确确定数据的质量，数据质量常常用概率来表示.

数据采掘就是从真实世界数据中提取知识.因为人类对现实世界认识的局限性，造成不确定数据在数据挖掘中普遍存在.人们越来越关注从不确定数据中挖掘频繁模式.

频繁模式（frequent pattern），是指频繁地出现在数据集中的模式，譬如项集、子序列或子结构.在数据集中挖掘频繁模式称为频繁模式挖掘.

1 相关工作

1.1 频繁模式挖掘概述

一般频繁模式挖掘算法都只是处理确定数据.但是越来越多的人们关注从不确定数据中挖掘交易决策树 .Chui［1］，韩［2］，Leung［3］都研究过不确定数据，并开发出相应算法，从不确定数据中挖掘知识在现实生活非常重要［4］.Chui提出 U-Apriori算法，该算法根据范式产生并检测候选集.Leung提出挖掘不确定数据的树型结构算法并在文献［4］中提出改进过的UF-tree and UF-growth算法.因为不确定数据的复杂性，在单机上处理分析很单薄，这时采用分布式处理就会相对容易.本文提出一种基于交易决策树的分布式处理策略，完善了Leung在文献［3］中提出的在分布式环境中处理交易决策树的算法——PUF-Tree，能快速挖掘出频繁模式.文献［1］Chui的U-Apriori算法是基于不确定数据的算法，但其需要多次遍历搜索.随后文献［3］Leung提出了UF-growth算法，减少了对不确定数据的扫描次数.UF-growth算法分为2步：UF Tree的建立和UF Tree的挖掘，但是在UF Tree中规定只有相同概率的节点才会被共享访问，这样降低了执行效率 .为了解决这个问题，Aggarwal［5］提出了 UFP-Growth算法，算法中有相同概率的节点被分组，从而能快速挖掘频繁模式.

Leung提出基于前缀上界的不确定数据频繁模式挖掘树结UFP-Tree，该树具有和FP-Tree相同的压缩结构.郝天鹏［6］提出基于同类项的最小支持度和并行计算的频繁模式挖掘算法，对UFP-Tree提出两种改进算法.

1.2 改进算法

本文改进了UFP-Tree算法，主要改进如下：

（1）改变了存在概率的表示.在交易数据t中的不确定项目x的存在概率表示为p(x∈t)∈(0,1).

（2）改进了期望支持度的表示，定义如下：

（3）改进了I(xt,tj)的表示，定义如下：

2 PUF-Tree的重建

在表1的不确定交易数据库（DB）［7］中，a、b、c、d、e、f是交易事务，minsup＝0.9，m＝6；t1、t2、t3、t4是不确定数据库中4个交易集.每个t都包含a、b、c、d、e、f中一个或几个.重建PUF-Tree分为2步：首先，遍历DB并计算出每一项的expSup.其次，遍历t并插入树中.

表1 不确定交易数据库

下面公式计算出表1交易数据a的期望支持度.

这样，我们可以计算出所有交易事物的expSup如表2所示.

表2 不确定交易数据库

因为约定minsup＝0.9，所以表2中b、d不符合要求，删去后就得到表3.

表3 修改后的不确定交易数据库

3 分布式压缩、并行重构PUF-Tree

3.1 分布式压缩PUF-Tree

现实中由于交易数据量巨大，PUF-Tree的重构耗时巨大，所以采用分布式计算，大大减少时耗.可以在局域数据中获取频繁模式，然后整合它们以实现全局模式.为了克服现有的不足，修改了Leung的PUF-Tree，得出压缩PUF-Tree压缩算法.具体步骤如下：

第一步：分离数据库同时部署到不同节点.

第二步：和中心服务机同步并行计算每一个节点中不同项目的expSup.

第三步：中心服务机编译并计算不同节点的expSup，并行计算每一个节点不同项目的expSup，并部署到局域节点.

第四步：每一局域节点从中心机接收expSup，然后并行建立压缩PUF-Tree，并传回中心机.

第五步：中心机整合局域PUF-Tree，由此获得全局PUF-Tree.

3.2 全局压缩PUF-Tree，生成GPUF-Tree

在此构建GPUF-Tree的过程包括2个阶段：第一阶段是以中心机为基础分布式构建LPUF-Treei；第二阶段是合并分布式计算结果MPUFi，生成GPUF-Tree.算法如下：

上述算法提出一种获取GPUF-Tree的模型，此模型通过获取局域或全局节点来深层次挖掘多种信息，最后在分布式环境中挖掘出频繁模式.

4 实验分析

为了比较现有算法和本文算法，实验采用Intel（R）Core（TM）i5-5200 CPU 3.00 GHz，内存为 3 GB，Windows 10操作系统.

采用合成数据库，基础数据库来自癌症基因组图谱（TCGA）.癌症基因组图谱（TCGA）是国家癌症研究所（NCI）和国家人类基因组研究所（NHGRI）之间的合作成果，已经生成33种癌症关键基因组变化的全面、多维地图.在此基础上采用不确定函数f（0，1）合成了基因组之间的相关作用强弱，从而得到不确定数据.

4.1 在不同的支持度条件下的GPUF重建实验

实验中的2000交易数据被分为五个部分，分别部署到5个不同的节点，用5个不同的处理器并行处理.交易树采用OpenMP重构.处理器间的同步由OpenMP实现.表4表示在不同阈值下重构GPUF-Tree的执行时间.图1显示GPUF-Tree的执行时间随着阈值的增加单调递减.

表4 不同阈值下重构GPUF-Tree的执行时间

图1 GPUF-Tree的执行时间随着阈值的增加单调递减

4.2 在不同的支持度条件下的GPUF重建实验

下面是在顺序和并行环境下GPUF-Tree的执行情况表.表5显示在顺序执行和并行执行环境下分别构建GPUF-Tree所用时间.

表5 顺序执行和并行执行环境下分别构建GPUF-Tree所用时间

从表5可知，计算时间随交易时间的增加而增加.

在顺序执行模式中，时间以指数形式增加，而在并行执行模式中，时间是逐渐缓慢增加的.耗时并不和计算的节点成正相关，而是与在中心机处理的节点数量成正相关.

由此可以得出顺序执行和并行执行所用总时间，如表6所示.图2显示并行执行环境下构建所用总时间优于顺序环境下构建所用总时间.

表6 顺序执行和并行执行环境下构建所用总时间

图2 顺序执行和并行执行环境下构建所用总时间对比图

5 结论

本文提出一种基于不确定交易数据的频繁模式挖掘算法，该算法能在分布式并行环境中挖掘基于树形结构的不确定数据.通过快速在分布式环境中构建树形结构，该算法给出了一种全局压缩PUF-Tree方法，并讨论了从局域或全局数据中获取局域或全局频繁模式，从而提供可靠的辅助决策信息.