数据挖掘技术与网上购物推荐系统

薛洁 刘希玉

山东师范大学管理与经济学院 山东 250014

0 引言

随着信息时代的到来，网上购物也已经成为人们主要的购物方式之一。我们只需联网操作不出家门即可获得较为满意的商品。然而，随着信息数量的激增，使得网上购物变得复杂，耗时。那么消费者如何才能更便捷更满意地从海量推销产品中买到所需商品；销售者如何才能吸引更多的客户前来购买自家产品，已成为一个亟待解决的问题。本文介绍了网上购物推荐技术以及构成此技术的数据挖掘相关内容，可以有效地帮助供需双方更好地进行网上商品交易。

1 网上购物推荐系统

网上购物推荐系统(ReComnlendatinoSystem)就是通过分析用户浏览过的网页、网购过的商品等来得出其喜好、习惯的结论，然后向其推荐信息、商品的程序。网上购物推荐系统能够很好地向用户推荐所需产品，帮助用户方便准确地买到物美价廉的商品，也能够帮助销售商促进产品的销售量以及商品货架的安排，进货的配比等。

2 数据挖掘

（1）数据挖掘的概念

数据挖掘就是从海量数据中提取或“挖掘”有用信息，也就是从大量信息中找到那些有用的，自己所需的信息。也有人将数据挖掘看做数据中的知识发现或是从存放在数据库、数据仓库等信息库中的大量书籍中发现有趣知识的过程。

（2）数据挖掘的任务

数据挖掘涵盖范围很广的数据分析和知识发现任务，包括：数据特征化、区分、关联、相关分析、分类、预测、聚类、离群点分析、演变分析等。

3 数据挖掘在网上购物推荐系统中的主要应用

网上购物推荐系统主要用到数据挖掘中的数据预处理技术，关联规则挖掘，分类分析，聚类分析等技术，本文主要介绍关联规则挖掘技术与聚类分析技术的应用。

3.1 挖掘关联规则的应用

挖掘关联规则应用于网上购物推荐系统可以：(1)向用户推荐相关产品，提高相关产品的销售额，即促进产品的捆绑销售；(2)安排商品销售的搭配；(3)准确进行进货配比；(4)根据购买模式对用户进行分类。从而动态调整网页，给各类用户提供更为满意的购物选择。

例 1：在图书网站上，消费者想购买数据挖掘概念与技术丛书。

商家根据对关联规则的挖掘结果将数据挖掘概念与技术丛书与数据仓库丛书放到一起销售的策略，通过向客户推荐额外的商品来提高交叉销售量。

根据商家进行数据挖掘得到的信息：购买数据挖掘概念与技术的用户有69%还购买了数据仓库。经调查许多顾客都会受到这种导向的影响，已经购买数据挖掘概念与技术的顾客很有可能向购买此书的前辈一样也随之购买其本不打算买的数据仓库。

例2：更进一步，根据对若干个例1中购买数据挖掘概念与技术的顾客进行关联规则挖掘，便可得到购买数据挖掘概念与技术的顾客也同时购买了DW2.0：下一代数据仓库的构造与数据仓库生命周期工具箱。这样可增加顾客对于此类丛书的购买欲望；也使得商家在进书时，可以更好地配比有关数据挖掘类丛书。但是较之例1，例2没有列出数据的支持，可信度较低。

例3：为某个用户推荐N种商品通过关联规则来实现。首先为每个用户产生一条记录，包括该用户所有曾经购买过的商品，运用关联规则的挖掘算法从这个数据库中找出所有满足最小支持度阈值和最小置信度阈值的关联规则。然后从这些规则中找出被目标用户支持的那些(即用户购买了所有出现在规则左边的商品)，列出用户尚未购买的产品，根据规则的置信度对产品进行排序，向用户推荐前N种。

1993年Agrawal首先提出关联规则概念，关联规则挖掘的对象是事务数据库。关联规则挖掘是指从数据集中识别出频繁项集，再利用频繁项集创建描述关联关系的规则的过程。

设I={I1，I2，…,Im}是项的集合。D是由若干条事务记录构成的事务数据库，其中每个事物T是项的集合，使得TI，对应每一个事务T有惟一的标识，记作TID。设A是一个项集，事务T包含A当且仅当AI。关联规则的一般形式为:A=＞B的蕴涵式，其中AI,BI，AB=。

规则通过置信度与支持度来衡量其确定性和可用性，典型情况下，如果同时满足最小置信度与支持度，则规则是有用的Support(A=＞B)=P(AυB);confidence(A=＞B)=P(BIA)

因为如果项集满足最小支持度阈值，则称项集为频繁项集，又因为confidence(A=＞B)=P(BIA)= Support(AB)/Support(A)，所以置信度可以轻易从支持度中求出，进而挖掘关联规则的问题就变为挖掘频繁项集的问题。

两种经典的频繁项集挖掘算法：

目前，已经有许多种对于频繁项集的挖掘算法，如Apriori，FP T ree，使用垂直数据格式挖掘，挖掘闭频繁项集等，本文只简单介绍两种最经典的频繁项集挖掘算法。

使用候选产生频繁项集-----Apriori

Apriori算法整个过程基于其频繁项集的所有非空子集也必须是频繁的这一性质，按以下步骤进行：

（1）选定最小支持度阈值min_support。

（2）初始扫描事物数据库一次，对每项即 L1(为候选项集C1的成员)的出现次数计数，将计数小于min_support的项进行剪枝。

（3）使用留下的L1∞L1自连接产生候选项集L2，扫描数据库，对L2的出现次数计数，将计数小于min_support的项进行剪枝。

（4）重复上述操作，直至找出所有的频繁项集，算法结束。

其实Apriori算法只进行连接和剪枝两个步骤，操作简单易懂，但是由于算法的每次迭代都需扫描数据库一次，致使时间复杂度极大，且对于大型数据库也不易操作。

不候选产生频繁项集----FP Tree

FP Tree是一种树形结构，FP Tree算法过程如下：

（1）初始扫描事物数据库一次，对每项的出现次数计数，频繁项按降序排列，结果记为L。

（2）构造FP Tree首先，创建树的根节点，用“null”标记；第二次扫描数据库，每个事务的项按L中的次序处理并对每个事务创建一个分枝。

（3）为tree创建一个项表头，使每项通过一个节点链指向它在树中的位置，此举可方便树的遍历。

（4）挖掘FP Tree，由每个长度为1的频繁模式开始，构造它的条件模式基，然后构造其FP Tree。

（5）递归地进行e过程，FP Tree算法较之Apriori算法而言，其只需扫描事务数据库两次，大量减少了扫描数据库所需的时间，简化了操作过程，但是若数据库很大，构造FP Tree也是不现实的。

3.2 聚类分析的应用

通过用户浏览过的网页或消费记录，对用户进行聚类分析，可将具有相同喜好，相似习惯的用户划分到同一个簇中，然后根据同一个簇中用户的意见向其更好更准确到位地推荐商品，也可动态地进行某类产品销售网页的调整，从而提供更合适，更令顾客满意的服务。对于商家，可根据不同簇中用户的特征，制作不同的销售网页，制定不同的销售策略，例如自动给一个特定的顾客聚类发送销售邮件，为一个顾客聚类动态地改变一个特殊的站点等，便于开发和执行未来的市场战略。

例：顾客A先前在网上购买了数据挖掘概念与技术和算法分析两本书，同时浏览了一些关于计算机类的商品，当A再次打开商品网页时，页面下方提示与A兴趣相似的顾客所关注的产品。这就是商家进行聚类分析的结果，通过A的浏览与购买记录，将与A有相似行为的顾客群分到同一个簇中，当满足此簇特征的用户进入网站时，站点便会动态给出其感兴趣的相关产品。用户必定受到这个提示的影响，浏览-＞购买此类产品。

将物理或抽象对象的集合分成相似的对象类的过程称为聚类。簇是数据对象的集合，同一个簇中的对象彼此相似，而与其他簇中的对象相异。

聚类方法主要有：划分方法(k均值，k中心点)，层次方法(凝聚，分裂)，基于密度的方法(DBSCAN,OPTICS)，基于网格的方法(STING)，基于模糊的方法(EM)等。本文简单介绍两种较为常用的聚类方法。

划分方法中的k均值方法：

K均值算法以k为输入参数，把n个对象的集合分为k个簇，使得簇内的相似度高，簇间的相似度低，簇的相似度是根据簇中对象的均值度量，可以看作簇的质心。

K均值算法的过程如下：

（1）随机地选择k个对象，每个对象代表一个簇的初始均值。

（2）根据剩余对象与各个簇均值的距离，将它们指派到与各自最相似的簇中。

（3）重复上述过程，直至准则函数收敛，通常选择平方误差准则：

其中，E是所有对象的平方误差和，p是空间中的点，表示给定对象，Mi是簇Ci的均值。此算法的时间复杂度是O(nkt)。

K均值法对于处理结果紧凑，并且簇与簇之间分离明显的对象集合时效果较好，但是这种聚类方法必须事先给出要生成的簇的数目，在多数情况下，面对庞大的用户对象的消费记录和浏览过的网页的Web日志，销售商很难判定到底将它们分成几个簇较好，所以k均值算法在此有一定的局限性。

基于密度的DBSCAN算法：

DBSCAN是一种基于高密度连通区域的基于密度的聚类方法，它将具有足够高密度的区域划分为簇，将簇定义为密度相连的点的最大集合。

DBSCAN的操作过程：

（1）确定对象半径ε和对象的ε邻域内至少包含的对象的最小数目MinPts。

（2）检查数据库中每个点的ε领域。

（3）如果点p的ε领域包含的点多于MinPts个，则创建一个以p为核心对象的新簇。

（4）迭代聚集从上述核心对象直接密度可达(给定一个对象集合D，如果p在q的ε领域内，同时q是一个核心对象，则我们说对象p从对象q出发是直接密度可达的)的对象。

（5）至没有新的点添加，操作结束。

DBSCAN算法的时间复杂度是O(n2)。

此算法需要用户给出ε和MinPts，无需给出所划分簇的数目，只要ε和MinPt s得当，便可有效找出任意形状的簇。

当然，还有许多其他聚类算法，如贝叶斯聚类算法，WaveCluster算法，遗传算法等，也有许多学者致力于新的聚类算法的研究，相信聚类技术会更加快速，有效。

4 总结

网上购物推荐系统现已在卓越亚马逊，当当等多个购物网站成功使用。当然其所包含与使用的技术并不仅仅包括文中所述的关联规则与聚类分析技术，还需对不同数据进行预处理，协同过滤等相关操作。本文仅简单介绍其中的关联规则挖掘与聚类分析的几种方法。网上购物推荐系统虽然应用广泛，能够使用户和商家产生双赢局面，但是它也存在许多不足，此为未来需要研究的主要方向。随着网络与电子商务的普及，相信网上购物推荐系统也会越来越完善！

[1]JiaWei Han.数据挖掘概念与技术(原书第二版).机械工业出版社.2010.

[2]刘旭东.B2C网上购物推荐系统的设计与实现.烟台:计算机应用于软件.2009.

[3]宋红芳.Web数据挖掘在电子商务中的应用研究.山东科技大学.2005.

[4]耿晓中.超市管理系统及数据挖掘技术在其上的应用.吉林大学.2004.

[5]张晶.基于 FP 关联规则的购物推荐系统的开发.复旦大学. 2009.