摘 要：对大型数据库中海量数据进行数据挖掘的方法进行研究，提出一种对海量数据进行数据挖掘的有效方法,该方法实现了如何采用粒子群优化算法对海量数据进行优化划分，并且采用改进的Apriori算法解决Apriori算法产生大量候选项集和多次扫描数据库的缺点。从而解决海量数据挖掘的时间和空间复杂度过高的难点。
关键词：数据挖掘；PSO算法；关联规则
中图分类号：TP301.6 文献标识码：A
An availability measure of data mining on mass data
Chen Jian-guo
（College of Computer Science South-central University for Nationalities Wuhan 430074,China)
【Abstract】Through researching the measure of data mining on mass data in large database， this paper proposed an availability measure of data mining on mass data，this measure have achieved how to adopt the particle swarm optimization algorithm to partition the mass data optimization，and adopt an improved Apriori algorithm which resolve the shortcomings of Apriori algorithm, including generating a large number of candidate itemsets and scanning the database many times，so the new algorithm improves the speed and efficiency of data mining on mass data.
【Key words】data mining; Particle Swarm Optimization algorithm; association rule;
当今世界数据信息急剧膨胀，大型数据库和对大型数据库中海量数据进行挖掘越来越成为数据库领域研究人员面对的更现实的问题。基于海量的数据挖掘正在兴起，现在面对海量的数据，一般的挖掘软件或者算法往往采用数据抽样的方式进行处理，这样误差不会很高，可以大大提高数据挖掘的处理的效率和处理的成功率，但在采样时要注意数据的完整性和防止过大的偏差[1]。这种方法对数据采样要求比较高，而且可能出现在采样率不很高的情况下丢失一些很重要的潜在信息。这样就产生了一种对海量数据进行全盘分析的方法。将海量数据进行划分，划分为多个小的子数据库，对每个子数据库进行数据挖掘，再合并各子数据库的挖掘信息[2]。如何对海量数据进行划分，且要使这些数据得到最优划分，即每个数据划分到其最理想的子数据库里面，这样就联系到了另一个重要的研究领域――多目标优化，在多目标优化领域中粒子群优化算法Particle Swarm Optimization(PSO)是其中一个解决多目标问题的非常优秀的算法[3]。
关联规则是数据挖掘的重要研究方向之一，目前基于关联规则的数据挖掘算法在处理小型数据库时还可以表现较好的性能，然而在处理海量数据时随着数据量的增加效率直线下降。Apriori算法是利用关联规则进行数据挖掘中的一个最经典的算法，对Apriori算法进行研究分析，发现该算法具有产生大量候选项集和多次扫描数据库的缺点，且该算法在对海量数据进行挖掘具有非常低的效率，甚至不切实际，但对其进行改进后在对小数据库进行数据挖掘时可以表现很好的性能。本文拟采用粒子群优化算法对大型数据库进行优化划分，形成多个子数据库，再在子数据库基础上采用改进后的Apriori算法进行局部挖掘，最后合并各个局部频繁项集并生成关联规则。
1. 算法介绍
1.1. 粒子群优化算法
粒子群优化算法是一种基于群智能的演化计算技术，该算法于1995年由Eberhart博士和kennedy博士提出[4][5]，是当前比较流行的仿生类算法。
PSO算法的基本思想：初始化一群随机解作为随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己，第一个是粒子本身所找到的最优解，称为个体极值pBest，另一个极值是整个种群目前找到的最优解，称为全局极值gBest。在已知pBest和gBest的情况下，粒子根据以下公式来更新自己的速度和位置。
v[i]是粒子i的速度，w是惯性权重，present[i]是当前粒子i的位置，rand()是介于（0，1）之间的随机数，c1，c2是学习因子。
粒子群优化算法的优势在于概念简单，收敛速度较快，所需调整的参数较少。它可直接采用实数编码，算法结构简单，容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。因此，粒子群优化算法一经提出便立刻引起了信息和进化计算科学等领域学者们的广泛关注和重视，并在短短的几年时间里出现大量的研究成果，形成了一个新的理论研究热点，已被用于多种工程领域。该算法在函数寻优、聚类、人侵检测和人工智能等领域具有很好的应用前景．
1.2. 改进型的Apriori算法
关联规则挖掘是发现大型事务或关系数据集中项之间的关联或相关。关联规则挖掘由于它应用的领域广泛从而得到了数据库从业人员和研究人员的特别关注。最重要的关联规则挖掘算法――Apriori算法由R . Agrawal和R . Srikant于1994年提出[6]，它是一个基于频繁项集挖掘的经典算法。Apriori算法的核心方法是基于频繁项集理论的逐层搜索的迭代方法，但其具有产生大量候选项集和扫描数据库的次数太多的缺点。本文采用基于矩阵按位存储的Apriori算法[7]，该算法只扫描一次数据库，且操作的效率非常高。
设I={I1,I2,…,In}是1项的集合，任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得T⊆I。每个事务有一个标识符，称作TID。
定义1：每个项Ij的向量定义为：
1. 频繁项集的生成
具体步骤如下：
(1) 根据定义1扫描数据库生成矩阵D。
(2) 根据矩阵D生成1项候选集矩阵，扫描矩阵对所有1项候选集计数，生成频繁1项集并用矩阵存储，保存频繁1项集的计数。
(3) 利用频繁1项集矩阵生成候选2项集矩阵，对候选2项集计数，生成的频繁2项集也用矩阵存储，并保存频繁2项集的计数。
(4) 频繁k-1项集生成候选k项集时按照候选K项集生成规则生成，并用矩阵存储候选k项集，按定义3对候选k项集进行计数，判断其是否频繁，生成频繁k项集，用矩阵存储频繁k项集，并保存各频繁k项集的计数。
(5) 如果频繁k项集为空，则算法结束，否则，重复执行步骤4，。
2. 关联规则的生成
对于每个频繁项集L，产生L的所有非空子集，对于L的每个非空子集S，如果S的支持数与L的支持数之比大于最小置信度，则输出规则“S=>L � S”。
2. PSO算法实现的数据库划分
基本关联规则挖掘算法虽然都不适合大型数据库中海量数据的挖掘，但是在数据库较小的情况下可以具有很好的效率．因此，本文考虑利用粒子群算法对大型数据库进行划分，再在子数据库的基础上应用改进的Apriori算法进行关联规则挖掘，提高挖掘效率．在利用粒子群算法进行数据库划分的时，本文引人了K―均值聚类的思想．以下是对数据库进行划分的步骤：
对粒子的位置采用一维16位二进制编码，“1”代表了该位记录属性为真，“0”代表了该位记录属性为假．
1)随机初始化K个聚类中心Z0，将事务按最小距离原则分配给k个聚类中心，以Z0作为粒子的初始位置．根据当前位置，利用适用度函数计算公式计算适应值F0(X)，设置当前适应值为个体极值Pi，当前位置为个体极值位置Xi，根据当前各个粒子的个体极值Pi和个体极值位置Xi ，找出全局极值Pg和全局极值位置GX，且Pg=min（Pi）；
2)按照公式(1)和公式(2)，更新粒子的速度和位置，并把粒子的速度限制在Vmax内；
3)计算适应值F，并根据F得到当前各个粒子的个体极值Pi 和个体极值位置Xi。如果当前迭代次数n
推荐访问:海量 数据挖掘 方法 一种海量数据挖掘的有效方法 海量数据挖掘技术研究 一种数据挖掘的方法