基于划分的Apriori改进算法在电子商务中的应用

宋 磊

（福建江夏学院，福建 福州350108）

0 前言

随着互联网的迅猛发展，数据挖掘在电子商务中得到广泛的应用.运用分类、关联等技术，从数据库中提取出有效数据的过程称为数据挖掘[1].关联规则是在复杂的数据库中找出满足给定条件的多个域之间的相互关系，它是数据挖掘的一个重要方面[2].电子商务系统中数据和信息关系是客户与企业都不可或缺的资源，如何让电子商务企业在这激烈的商业竞争中获取和保持这种高流动性、高效率、高准确度的这种资源成为各电子商务企业关注的焦点.目前电子商务系统中普遍存在着各种信息服务不能够主动满足客户需求，是一种被动的信息获取方式.而当今电子商务发展要求用户主动地、动态地改进服务模式，提供个性化需求的界面.因此本文有针对性地在关联规则技术之Apriori算法研究的基础上，针对算法本身的不足，提出了一种基于划分的改进算法，并将此算法应用于电子商务系统.

1 关联规则与Apriori算法简介

1.1 关联规则

关联规则是用于挖掘数据库中属性或项目间的未知或隐藏的关系准则.其中它的两个重要属性是支持度（support）和置信度（confidence）.关联规则用事物数据库来定义，a，b分别为项目集，且a⊂C1，b⊂1，并且a∩b＝Ø，a，b分别称为关联规则a＝＞b的前提和结论.一般情况下，可以把关联规则划分为两个子问题:1）由频繁项目集产生的强关联规则，即找出频繁项目集中置信度大于等于用户所给的最小置信度的规则；2）找出所有的频繁项目集，即所给的最小支持度的项目集小于所有支持度的规则.其中，第二个子问题是关联规则挖掘算法的核心问题.

1.2 Apriori算法

Apriori算法是最具影响的一种原创性布尔关联规则挖掘频繁项集的算法，该算法核心是逐层搜索的迭代[3].Apriori算法的描述如下:假设数据库D、最小支持度为min＿sup、频繁项集为L，首先产生频繁项目集L；其次由频繁k－1项集连接成的k项集，检测L是否包含k项集的所有的k－1子集，D对每个候选k项集为min＿sup的k项成为频繁k项集，如此下去，直到找不到更高的频繁项集为止.

2 基于划分的Apriori改进算法

2.1 Apriori算法的主要问题

Apriori算法优点是大大缩减了需检查的候选规模，提高了算法效率[4].该算法的基本思想是利用一个循环顺序搜索的方法来完成频繁项集的挖掘关联工作，也就是利用k项集来产生k＋1项集.然而，Apriori算法还不完善，主要存在以下几个问题:

1）候选项集太多.Apriori算法在运算过程中会生成大量的候选频繁项集，导致算法在一定程度上适应性很差.

2）重复扫描数据库.每一次迭代的时候Apriori算法会扫描一次数据库，频繁项集如果最大长度为X，就需扫描X次数据库，而这样的多次重复扫描会降低整个的效率.

3）支持度唯一.通常，一些事务经常性的发生，一些事务偶尔的发生，这样对挖掘和关联而言就有问题:如果最小支持度阈值比较高，挖掘是快了，但是整个关联中无效的应用得不到排除反而会大大降低了挖掘关联的效率和规则的实用性.

4）Apriori算法扩展性瓶颈.由于Apriori算法是单维布尔关联规则挖掘，然而在运用过程中经常出现多维的、多数的和多层的关联规则，所以该算法就需要进行改进或者重新设计.

2.2 基于划分的Apriori改进算法

所谓划分也就是分段，是指把来自事务数据库中的所有项分成N份，然后对每个单独部分生成频繁项目集L.从数据库中计算出候选频繁项目的实际支持度，确定最后的频繁项目集.该算法改进的宗旨首先是把数据库分成N份，整个数据库上的频繁目集至少在数据库的一个分段上是频繁的；其次每个分段上的频繁项目集集合的并集就是整个数据库上潜在的频繁项目集的集合.因此基于划分的改进算法可以部分描述为:

通过以上改进算法的分析，在关联规则挖掘方面大大提高了效率.1）候选项集减小了.通过算法改进，扫描数据库计算每个候选项的支持计数之前，会先判断Ck中Lk－1是否包含每一元素X的k－1项子集.实验证明，大大减少了候选项集Ck规模.2）减少了扫描数据库的的次数.在候选项目集Ck确定频繁项目集Lk时，T既不包含Ck中的任一元素，也必不包含Ck＋1的任一元素.3）通过程序改进解除了瓶颈.所以良好的数据结构、程序优化等对算法的效率和可扩展性是具有很深影响的.

3 Apriori改进算法在电子商务中的应用

3.1 电子商务推荐

在新的电子商务模式下，电子商务系统中信息越来越多的积累，信息量过大的问题也越来越严重，怎么能使用户能快速、顺利地选择到自己所需的商品.电子商务推荐系统机制的引进很好地解决了上述问题.电子商务推荐系统能很好地向用户推荐一些合适的商品，有效节约用户购物的时间，使购物过程变得轻松便利，在用户得到满意的同时，网上企业也能赢得好评和丰厚的利润.电子商务推荐与传统商业不同，它是让电子商务网站主动适应每个客户的特定需求，为每个客户提供各异的个性化购物环境.一般情况下，推荐问题往往被认为是用户未见到的预测问题.如果我们要求向系统进行评价和预测，此系统就可以向客户推荐获得最为匹配的项目.随着Apriori算法引入，电子商务推荐系统就能有针对性地为客户进行推荐，使其能够方便地购买相关商品[5].

3.2 Apriori改进算法应用

改进优化的Apriori划分算法，首先对商品进行划分，根据客户需求让客户所需的产品先从数据库中分离出来，优先推荐此类商品到客户.此改进算法有利地提升了电子商务网站的推荐效率.下面以某商务网站客户信息数据样本为例（如表1），将改进的Apriori划分算法与传统的Apriori算法进行比较.

实际商务过程中，顾客在购买了a产品系列后会一起选购其他相关联的产品比如b产品系列.由此我们可以比较，传统的Apriori算法推荐商品如表2.

引入Apriori划分算法后，商务网站得到的推荐商品如表3.

表1 样本数据库

表2 传统Apriori算法推荐的商品

表3 改进的Apriori算法推荐的商品

实验数据表明，当支持度阈值越小时，改进的划分算法推荐商品的效率越高.电子商务网站数据信息非常多，而且品类和属性相对比较复杂，通过数据挖掘中关联规则的应用及Apriori算法的改进，优化确保了电子商务网站在推荐商品时的效率和准确度.再加上其对路径进行细化分类，把出现频率较高的商品通过关联技术，关联出最适合客户的有效商品.所以引入基于划分的Apriori改进算法会最大程度地为客户优先推荐商品，也将在电子商务应用方面表现出最优化.

4 结论

随着电子商务的迅猛发展，个性化的推荐服务和数据挖掘技术的运用越来越突显重要.怎么能有效地留住网上的用户，从而有效地增强电子商务企业在市场上的竞争力，将是未来电商企业竞争的主要问题.本文在关联规则挖掘算法的基础上，针对电子商务系统的具体应用，采用改进的基于划分的Apriori算法挖掘出客户需求的关联规则，实现了客户群体的个性化推荐，并应用实际电子商务推荐的数据进行实验，验证了该方法具有对算法路径进行细化分类，并可通过关联技术为最合适客户关联出有效商品的优点.这些内容的讨论对于数据挖掘方法的改进具有一定意义.

[1]Wu Yongbin，Zhang Yitang，Liu Shuangshuang.3Dvisualized geologic modeling technique based on petrel[J].Drilling ＆ Production Technology，2007，30（5）:65－67

[2]陈江平，傅中良，徐志红.一种 Apriori的改进算法 [J].武汉大学学报（信息科学版），2003，28（1）:94－99

[3]徐章艳，张师超，区玉明，等.挖掘关联规则中的一种优化的 Apriori算法[J].计算机工程，2003，29（19）:83－84，87

[4]吴 林.基于数据仓库的数据挖掘技术的研究与实现数据分类的研究与实现[D].成都:电子科技大学.2001

[5]张 诤，王惠文.一种高效的并行频繁集挖掘算法[J].计算机工程，2008，34（11）:55－57