论文部分内容阅读
摘 要：网络销售是电子商务的一种重要的形式，而组合营销是提升网络销售业绩的一种重要手段。针对目前我国网络销售的基本模式，在已发现的组合营销策略特点的基础上，提出了一种基于约束的关联规则挖掘新算法。
关键词：组合营销策略；数据挖掘；关联规则
中图分类号：TP311
文献标识码：A
文章编号：1009-3044(2007)01-10010-01
1 引言
随着全球化浪潮的推进，电子商务正不断发展壮大。网络销售作为电子商务的一种重要组成形式为企业寻求更大的市场空间提供了一种新的有益尝试。我国目前网络销售的主流模式为：“订单一物流”模式。即用户下订单后，企业通过物流将商品交付给客户。由于物流费用一般由客户承担，客户为减少购物的物流成本，往往会在购买主目标商品的同时，搭配几件价格不高的次目标商品。这就为企业实施商品的组合营销策略提供了机遇。
2 问题描述
组合营销是指企业通过对不同类别、不同价格的商品的合理组合，向客户一次提供多种商品的营销方式。数据挖掘中的关联规则分析方法，通过挖掘出以往销售数据中哪些商品频繁的被顾客同时购买，形成关于商品间搭配的知识，从而指导今后销售的商品组合。但经典的关联规则挖掘方法由于缺乏用户控制，导致产生的规则过多，且部分规则对用户毫无意义。为了解决该问题，人们引入了基于约束的关联规则挖掘方法。R．T．NG等学者提出了受约束的关联查询概念R．Srikant等人研究了项集受约束的关联规则挖掘，挖掘出了包含某布尔表达式的频繁项集Robert J．Ba-yardo Jr等人研究了稠密数据库的特点，并提出了改进度的概念
本文首先介绍了关联规则的基本概念，在指出传统关联规则挖掘方法缺陷的基础上，提出了一种受用户指定数据约束的关联规则挖掘算法(UD-Apriori)。实验分析表明，该算法能在短时间内找到用户感兴趣的规则，算法效率有明显提高。
3 关联规则的基本概念
3．1关联规则的描述
设I={i1i2，im}是项的集合，其中的元素称为项(item)。记D为交易T的集合，这里交易T是项的集合，并且T I。设X是I中项的一个集合，如果X T．那么称交易T3X。一个关联规则是形如“X Y的蕴含式，这里X I，Y I，并且X Y= 。
规则“XjY”在事务数据库中的支持度(support)是事务集中包含X和Y的事务数与所有事务数之比，记为suppog(X Y)，即：
suooort(X Y)：l{T,X Y T，T D}|/|D|
对项目集I和事务数据库D，T中所有满足用户指定的最小支持度(minsupportl的项目集，称为频繁项目集。
规则X Y在事务集中的置信度(confidence)是指包含X和Y的事务数与包含X的事务数之比，记为confidence(X Y)，即：
Confidence(X Y)=|{T，X Y T，T D，T D}|/|T:X T，T D}|
3．2经典关联规则挖掘算法及其缺陷
经典的关联规则挖掘算法分两个阶段：首先，产生达到指定最小支持度的项集(即频繁项集)，然后从每个频繁项集中找出能够达到指定最小置信度的规则。其中，第一步生成满足最小支持度的项集是关键。1994年Agrawal等人在提出了著名的Apfiofi算法此算法使用递归方法生成所有的频繁项集。首先生成频繁1-项集L1，然后生成频繁2-项集L2，…，一直到某个r使得Lr为空，算法结束。当求Lk时，首先通过Lk-1的自连接生成候选项集Ck；检验Ck中的每个元素，满足用户指定的最小支持度的元素就是Lk中的元素。从以上算法描述可看出由于Lk-1候选集Ck是呈指数增长的，例如104个1-频繁项集就有可能产生接近107个元素的2-候选项集。如此大的候选项集对时间和主存空间是一种巨大的挑战。另外，由于基于“支持度一置信度”的关联规则挖掘度量框架本身不具有关联规则生成的先决指导性，导致产生的部分规则对最终用户毫无意义，而一些较长的规则又难于理解。这些都导致算法效率的低下。
4 受用户指定数据约束的关联规则挖掘算法
4．1算法的提出背景
在企业实施商品的组合营销策略过程中，往往以利润为先导，把关注焦点集中在那些销售情况较好而价格又相对比较高的商品上面。因此，企业销售策略可以是：针对具有上述特征的商品，找出和这类商品一起被频繁购买的其它价格比较低的商品，以便在今后的销售中对这些商品进行捆绑销售。
4．2受用户指定数据约束的关联规则挖掘算法(UD-Apfiofi)的基本思想
基于上述销售策略，我们提出一种受用户指定数据约束的关联规则挖掘算法。其中。用户需要提供两个约束信息：畅销商品A以及与A关联的商品价格总和的最大值(max_sumprice)。
该算法的基本思想是：首先利用用户指定商品A为约束条件对事务数据库D进行扫描，包含A的实例加入到实例集Dt中，其余被过滤掉。然后在经典Apfiofi算法的频繁项集生成过程中应用受max_sumprice参数约束的剪枝策略，生成符合约束条件的频繁K-项集，最后由频繁项集生成受约束的关联规则。
4．3剪枝策略
定义1
约束Ca是反单调的是指对于任意给定的不满足Ca的项目集S，不存在S的超集能够满足Ca。
下面给出了与A相关联商品的反单调性约束表达式：
sum_price(Bl，B2，…，Bn)≤max_sumprice。
其中，sum_price(B1，B2，…，Bn)为在频繁项集的项(item)中与A相关联的商品价格的总和。
证明：反证法。假设sum_price(B1，B2，…，Bn)>max_sumprice，且有sum_price(B1，B2，…，BnBn+1)≤max_sumprice，其中Bi>0。则有sum_price(B1，B2，…，Bn)>sum_price(B1，B2，…，BnBn+1)，即：Bn+1+l<0，与假 设Bi>0矛盾，故sum_price(B1，B2，…，Bn)≤max_sumprice为反单调性约束条件。由定义1可以确定，如果在Apriofi算法中生成的任何一个频繁项集不满足反单调约束条件，则它的任何超集都不满足此约束条件。因此，在经典的apriori算法产生K-1-频繁项集后，我们可以直接将不满足约束的频繁项集剔除掉。这样从客观上，减少了频繁项集生成所需要的候选项集的数目，成功地对候选项集进行了剪枝。
4．4 UD-Apriori算法描述
输入：事务数据库D，A(用户指定的商品)，min_sup(最小支持度)，min_conf(最小置信度)，max_sumprice(频繁项集的项中与A关联的商品之和的最大值)。
输出：满足min_sup，min_conf，A，max_sumprice约束的关联规则。
Begin
If A is unfrequent then
return；
Filter(A)；
L1=L1+find_frequent_l-itemsets(D’)//产生频繁1项集
Delete T where not contain L1；
Gen_rules(1，L1)；//产生频繁1项集规则
For(k=2；Lk-1≠φ；k++)
{Ck：apriori_gen Lk-1,min_sup，max_sumprice)；//产生K-项集
Lk=subset (Ck,D’)；//产生频繁K-项集
Gen_rules(K，Lk)：//产生频繁K-项集的规则
end；procedure filter(A)//过滤事务数据库
For all trasactions t D：
Ift contain A then
Write to D′return；
5 试验结果分析
本试验采用IBM数据生成器生成记录型测试数据进行算法测试，同时将每个项目元素进行价格赋值。实验环境基于winxp平台，计算机内存256MB，主频2．8GHZ，测试数据各项参数如表2。
在数据库291个项目元素中，元素最高价格为4995。在频繁1项集中项集最高价格为4425。因此，将价格为4425的项i4425定为指定约束元素。基于此事务数据库对经典的Apriori算法及受用户指定数据约束算法的对比测试结果如表3。
实验结果表明，由于受项i4425的约束，算法的运行时间和生成的规则数大为减少。且由于指定了约束条件项i4425，使挖掘过程的指向性得到明显提高。很好的控制了挖掘的数据规模，从而保证了在生成的关联规则数目减少的同时更加契合用户的意愿。
6 结论
本文根据网络电子商务的特点，结合组合营销策略实施中客户的具体购买模式，提出了一种基于约束的关联规则挖掘算法。试验结果表明，这种算法由于引入了更多的用户控制，相比经典的关联规则挖掘算法效率更高。挖掘结果表明，挖掘生成的关联规则大为减少，信息指向性也更加明确，为企业实施组合营销策略提供了科学的依据。
关键词：组合营销策略；数据挖掘；关联规则
中图分类号：TP311
文献标识码：A
文章编号：1009-3044(2007)01-10010-01
1 引言
随着全球化浪潮的推进，电子商务正不断发展壮大。网络销售作为电子商务的一种重要组成形式为企业寻求更大的市场空间提供了一种新的有益尝试。我国目前网络销售的主流模式为：“订单一物流”模式。即用户下订单后，企业通过物流将商品交付给客户。由于物流费用一般由客户承担，客户为减少购物的物流成本，往往会在购买主目标商品的同时，搭配几件价格不高的次目标商品。这就为企业实施商品的组合营销策略提供了机遇。
2 问题描述
组合营销是指企业通过对不同类别、不同价格的商品的合理组合，向客户一次提供多种商品的营销方式。数据挖掘中的关联规则分析方法，通过挖掘出以往销售数据中哪些商品频繁的被顾客同时购买，形成关于商品间搭配的知识，从而指导今后销售的商品组合。但经典的关联规则挖掘方法由于缺乏用户控制，导致产生的规则过多，且部分规则对用户毫无意义。为了解决该问题，人们引入了基于约束的关联规则挖掘方法。R．T．NG等学者提出了受约束的关联查询概念R．Srikant等人研究了项集受约束的关联规则挖掘，挖掘出了包含某布尔表达式的频繁项集Robert J．Ba-yardo Jr等人研究了稠密数据库的特点，并提出了改进度的概念
本文首先介绍了关联规则的基本概念，在指出传统关联规则挖掘方法缺陷的基础上，提出了一种受用户指定数据约束的关联规则挖掘算法(UD-Apriori)。实验分析表明，该算法能在短时间内找到用户感兴趣的规则，算法效率有明显提高。
3 关联规则的基本概念
3．1关联规则的描述
设I={i1i2，im}是项的集合，其中的元素称为项(item)。记D为交易T的集合，这里交易T是项的集合，并且T I。设X是I中项的一个集合，如果X T．那么称交易T3X。一个关联规则是形如“X Y的蕴含式，这里X I，Y I，并且X Y= 。
规则“XjY”在事务数据库中的支持度(support)是事务集中包含X和Y的事务数与所有事务数之比，记为suppog(X Y)，即：
suooort(X Y)：l{T,X Y T，T D}|/|D|
对项目集I和事务数据库D，T中所有满足用户指定的最小支持度(minsupportl的项目集，称为频繁项目集。
规则X Y在事务集中的置信度(confidence)是指包含X和Y的事务数与包含X的事务数之比，记为confidence(X Y)，即：
Confidence(X Y)=|{T，X Y T，T D，T D}|/|T:X T，T D}|
3．2经典关联规则挖掘算法及其缺陷
经典的关联规则挖掘算法分两个阶段：首先，产生达到指定最小支持度的项集(即频繁项集)，然后从每个频繁项集中找出能够达到指定最小置信度的规则。其中，第一步生成满足最小支持度的项集是关键。1994年Agrawal等人在提出了著名的Apfiofi算法此算法使用递归方法生成所有的频繁项集。首先生成频繁1-项集L1，然后生成频繁2-项集L2，…，一直到某个r使得Lr为空，算法结束。当求Lk时，首先通过Lk-1的自连接生成候选项集Ck；检验Ck中的每个元素，满足用户指定的最小支持度的元素就是Lk中的元素。从以上算法描述可看出由于Lk-1候选集Ck是呈指数增长的，例如104个1-频繁项集就有可能产生接近107个元素的2-候选项集。如此大的候选项集对时间和主存空间是一种巨大的挑战。另外，由于基于“支持度一置信度”的关联规则挖掘度量框架本身不具有关联规则生成的先决指导性，导致产生的部分规则对最终用户毫无意义，而一些较长的规则又难于理解。这些都导致算法效率的低下。
4 受用户指定数据约束的关联规则挖掘算法
4．1算法的提出背景
在企业实施商品的组合营销策略过程中，往往以利润为先导，把关注焦点集中在那些销售情况较好而价格又相对比较高的商品上面。因此，企业销售策略可以是：针对具有上述特征的商品，找出和这类商品一起被频繁购买的其它价格比较低的商品，以便在今后的销售中对这些商品进行捆绑销售。
4．2受用户指定数据约束的关联规则挖掘算法(UD-Apfiofi)的基本思想
基于上述销售策略，我们提出一种受用户指定数据约束的关联规则挖掘算法。其中。用户需要提供两个约束信息：畅销商品A以及与A关联的商品价格总和的最大值(max_sumprice)。
该算法的基本思想是：首先利用用户指定商品A为约束条件对事务数据库D进行扫描，包含A的实例加入到实例集Dt中，其余被过滤掉。然后在经典Apfiofi算法的频繁项集生成过程中应用受max_sumprice参数约束的剪枝策略，生成符合约束条件的频繁K-项集，最后由频繁项集生成受约束的关联规则。
4．3剪枝策略
定义1
约束Ca是反单调的是指对于任意给定的不满足Ca的项目集S，不存在S的超集能够满足Ca。
下面给出了与A相关联商品的反单调性约束表达式：
sum_price(Bl，B2，…，Bn)≤max_sumprice。
其中，sum_price(B1，B2，…，Bn)为在频繁项集的项(item)中与A相关联的商品价格的总和。
证明：反证法。假设sum_price(B1，B2，…，Bn)>max_sumprice，且有sum_price(B1，B2，…，BnBn+1)≤max_sumprice，其中Bi>0。则有sum_price(B1，B2，…，Bn)>sum_price(B1，B2，…，BnBn+1)，即：Bn+1+l<0，与假 设Bi>0矛盾，故sum_price(B1，B2，…，Bn)≤max_sumprice为反单调性约束条件。由定义1可以确定，如果在Apriofi算法中生成的任何一个频繁项集不满足反单调约束条件，则它的任何超集都不满足此约束条件。因此，在经典的apriori算法产生K-1-频繁项集后，我们可以直接将不满足约束的频繁项集剔除掉。这样从客观上，减少了频繁项集生成所需要的候选项集的数目，成功地对候选项集进行了剪枝。
4．4 UD-Apriori算法描述
输入：事务数据库D，A(用户指定的商品)，min_sup(最小支持度)，min_conf(最小置信度)，max_sumprice(频繁项集的项中与A关联的商品之和的最大值)。
输出：满足min_sup，min_conf，A，max_sumprice约束的关联规则。
Begin
If A is unfrequent then
return；
Filter(A)；
L1=L1+find_frequent_l-itemsets(D’)//产生频繁1项集
Delete T where not contain L1；
Gen_rules(1，L1)；//产生频繁1项集规则
For(k=2；Lk-1≠φ；k++)
{Ck：apriori_gen Lk-1,min_sup，max_sumprice)；//产生K-项集
Lk=subset (Ck,D’)；//产生频繁K-项集
Gen_rules(K，Lk)：//产生频繁K-项集的规则
end；procedure filter(A)//过滤事务数据库
For all trasactions t D：
Ift contain A then
Write to D′return；
5 试验结果分析
本试验采用IBM数据生成器生成记录型测试数据进行算法测试，同时将每个项目元素进行价格赋值。实验环境基于winxp平台，计算机内存256MB，主频2．8GHZ，测试数据各项参数如表2。
在数据库291个项目元素中，元素最高价格为4995。在频繁1项集中项集最高价格为4425。因此，将价格为4425的项i4425定为指定约束元素。基于此事务数据库对经典的Apriori算法及受用户指定数据约束算法的对比测试结果如表3。
实验结果表明，由于受项i4425的约束，算法的运行时间和生成的规则数大为减少。且由于指定了约束条件项i4425，使挖掘过程的指向性得到明显提高。很好的控制了挖掘的数据规模，从而保证了在生成的关联规则数目减少的同时更加契合用户的意愿。
6 结论
本文根据网络电子商务的特点，结合组合营销策略实施中客户的具体购买模式，提出了一种基于约束的关联规则挖掘算法。试验结果表明，这种算法由于引入了更多的用户控制，相比经典的关联规则挖掘算法效率更高。挖掘结果表明，挖掘生成的关联规则大为减少，信息指向性也更加明确，为企业实施组合营销策略提供了科学的依据。