基于网格的分布式Apriori和经典Apriori算法的知识挖掘
摘 要：提出了使用网格技术的关联规则数据挖掘及实施，并分析、比较了经典Apriori算法和分布式Apriori算法的实施结果。通过WEKA工具对预评估系统的效率评估，和中心数据库上的Apriori和先验Apriori算法性能分析。在网格环境下可以通过减少数据处理时间、资源优化、负载分担来提高计算网络的效率并减少成本，从而使用户得到计算量更大、成本更低、速度更快的计算结果。还介绍了基于网格环境的分布式Apriori关联规则算法，并解释了如何获取知识。 关键词：分布式数据挖掘；关联规则；网格；算法；频繁项集；先验Apriori
0 引言
近年来，由于数据量越来越大，其用途越来越广，并且人们急需将这些数据量转换成为有用的信息和知识，数据挖掘，在信息产业，甚至整个社会都给予了高度的重视。数据挖掘是指从海量的数据中提取或“挖掘”知识。分布式数据挖掘（DDM），即从分布在各个独立网站的数据和计算中进行数据挖掘。每个站点都有其自己的数据源和由数据挖掘算法生产的本地模型。随之而来的是具有整个网络意义的知识。
网格，是指在动态组织内部协调、共享资源的一种分布式计算结构。关联规则是用来表示数据项之间的相互支持和依赖程度的。 在处理单独的方案时，WEKA实验环境使用户能够更加方便地创建，
运行，修改，并分析实验。例如，用户可以创建多个单独方案，而不是一系列数据集的实验，然后通过统计，分析结果，以确定此方案是否比其他方案更好。
1 频繁模式挖掘
频繁模式在数据经常发生。频繁模式有许多种，包括项目集，子序列和子结构。假设你作为某电子公司的营销经理，想确定在同一交易中哪些项目被经常购买。从公司的交易数据库中，挖掘到一个这样的规则：购买（X，“计算机”）=>购买（X，“软件”）[支持度= 1％，依赖度= 50％]，其中X是一个代表客户的变量。依赖度50%，或者说50％的可能性，意味着如果一个客户购买一台电脑，有50％的可能会买软件。1％的支持度，表示所分析的所有交易中的%1同时购买了计算机和软件。上述规则可以简单地写为“电脑=>软件[1％，50％]”。
1.1 Apriori 算法
Apriori是一个开创性的算法。1994年，R.Agrawal和R.Srikant在布尔关联规则频繁项集特性的挖掘中，使用了先验的（prior）知识，基于此，提出了Apriori算法。Apriori采用了迭代的方法，也就是平行搜索，即用K项集是用来探索（K +1）项集。首先，通过扫描数据库，积累每个项的计数，找出满足最小支持的项集作为
L\\-1，再
用L\\-1找出频繁2项集的集合L\\-2，而L\\-2用于找出L\\-3，如此下去，直到没有更频繁K项集可以发现。每个L
的寻找过程都需要
一次数据库的完整扫描。为了提高水平频繁项集寻找的效率，引入了
一个重要的特性，也就是Apriori特性（频繁项集的所有非空子集也必须是频繁的），有效的减少了搜索空间。接着进行连接和枝剪。 为了减少Ck的大小，使用的Apriori性质如下：任何(k-1)的不频繁项目集都不能作为频繁k项集的子集。另外，如果任何一个候选K项目集(k-1)的子集不在L\\-\\{k-1\\}，该候选项目集也不能是频繁的，从而可以从Ck中删除。 1.2 预测Apriori算法
先验Apriori算法返回基于关联规则{a\\-1,?,a\\-k},x\\-i∩y\\-i=
[x\\-i
y\\-i](x\\-i,y\\-i＜不在最优数组
)的一个最优数组[1?N]，
中的规则，就没有最优数组中的准确。或者说，跟最优数组中一样准确的规则，都应该包含在最优数组中。 1.3 网格结构的DDM
文本假定了一个基于网格技术的虚拟组织：该公司的结构分为一个公司总部和四个地方分子公司。每个公司都由数个网格结构的网格节点组成。
在本文的案例研究中，网格结构是基于Globus工具组件构造的，而数据挖掘的任务是在子公司数据库中发现关联规则。在OGSA环境下，发现的关联规则以网格服务的形式表现出来。Apriori网格服务必须符合OGSA的规则，约束，标准接口和行为。
从公司总部中发现关联规则的分布式框架实现VO结构，VO结构使用的数据挖掘方法技巧和技术类似网格，Java和关系数据库。用户客户端允许用户发送参数和命令给其余的组件。该框架的配置参
基于网格的分布式Apriori和经典Apriori算法的知识挖掘
