基于聚类的协同过滤电子商务个性推荐系统的研

摘　要：根据目前电子商务网站中商品个性化推荐的现状, 重点分析了比较常用的一种推荐方法--协同过滤推荐方法，发现了目前协同过滤算法在应用中所面临的挑战和问题，主要包括：推荐质量低、推荐效率低、数据稀疏性、冷启动等问题。针对这些问题本文提出了一种基于用户兴趣度的聚类分析协同过滤算法，有效的解决了目前算法中存在的数据稀疏性等问题，通过实验数据的分析对比，证明了算法的合理性和有效性。

关键词：电子商务；聚类； 协同过滤； 个性化推荐

1.引言

　　近年来，电子商务得到了飞速的发展。目前国内大多数电子商务网站的商品推荐通常是推荐畅销产品，推荐相关产品，根据用户浏览历史的推荐。前两种推荐未考虑用户的个性特点,第三种推荐有一定的个性化成份,但多数网站还仅仅停留在仅针对该用户一个人的购买历史。只是为每个用户建立了一个个人购买档案,没有横向进行信息综合,因此没有协作推荐价值,所以也无法实现商品的实时综合推荐。

　　协同过滤算法的推荐结果比较准确，能够挖掘目标用户潜在的兴趣，但协同过滤算法也存在数据稀疏性、可扩展性和冷开始等问题，这些问题的存在无疑影响了推荐算法的效率和准确性。本文主要针对电子商务推荐系统中的数据稀疏性问题和在线执行效率低的问题，提出了基于用户兴趣度的聚类分析协同过滤算法，有效提高了推荐系统的实时响应速度。

2.基于K-means聚类协同过滤的个性推荐过程

2.1  聚类算法

　　聚类分析是将一组对象划分成簇，使簇类对象相似性尽量大，而簇间对象相似性尽量小。它是数据挖掘领域中的一个重要分支，不仅可以作为数据挖掘中的一个模块，也可以作为其他分析算法的一个预处理步骤。用途非常广泛。在商业上，聚类可以划分消费群体帮助市场分析人员总结不同消费者的行为模式，进行有针对性的促销；在网络挖掘中，可用来对万维网上不同类型文档进行分类等。在本文中，存在具有相似审美情趣和修养的用户，对这些商品的喜爱程度会具有很大的趋同性，可比较不同用户间商品的购买倾向，即按所购买商品的相似性来进行用户聚类，从而作出后继推荐。

2.2 协同过滤的优点

　　协同过滤不仅考虑了活动用户的信息，还利用了其他用户的信息，从而大大增加了被有效利用的信息总量，提高了推荐的效率与表现。协同过滤所考虑的是用户对项的评价、而不是项的本身属性。也就是要为用户提供那些可能完全没有见过的项的推荐，只有这样，才能真正增加用户利用新项的机会。协同过滤还可以对图型、图像、音频、视频等非文本信息有效地做出推荐。

2.3  商品个性化推荐的流程

　　对于用户评分的商品推荐，具体实现时通常都可分为以下三个基本过程：

1） 客户对其感兴趣的商品进行描述。这种信息可能是该客户的购买信息，也可能是对商品的评价信息等。

2） 根据某相似性进行聚类。这种聚类既可以针对客户进行，即进行客户聚类，也可以针对商品进行商品聚类。

3） 协作过滤与商品推荐。根据目标商品或目标用户所在的聚类，提供相应的商品推荐。

基于B/S体系结构的商品个性化推荐系统的功能流程如图1所示：

3.基于聚类协作过滤的商品个性推荐系统的设计

　　协同过滤存在数据稀疏性问题。这个问题是指多数用户所评价过的项目数目并不很多，用户--项评价矩阵通常都非常稀疏。因此要找到一组评价非常相似的用户经常是很困难的。如果两个用户没有对相同的项目进行打分，即使这两个用户的兴趣爱好都相同，系统也无法得出他们之间的相似度。此外，随着电子商务网站规模的扩大，用户数据量成指数增长，对于协同过滤推荐，其完成目标用户邻居（或最相似用户）的识别非常耗时，实时响应推荐效果较差。

3.1系统实现过程

　　通过对传统协同过滤算法的分析，发现了其存在的问题，如在线执行效率低的问题以及数据稀疏性问题，针对这些问题，本文提出了一些改进的措施，具体的思路如下：

1） 将用户购买过某种商品所表现出的兴趣度的隐性信息转化为用户对该商品的显性评分数值，具体方法为：评分数值根据用户购买的商品数量设定。如无购物则记为0。

2） 将所有用户利用 k-Means 算法进行离线聚类，得到聚类中心评分数据矩阵如表 1和用户聚类程度矩阵如表2所示：

其中 k 行代表 k 个用户聚类中心，n 列代表 n 个商品，第 i 行第 j 列的元素 R_ij代表用户聚类中心 i 对商品 j 的评分，代表用户聚类 i 中所有用户对商品 j 评分的均值。

　　m 行代表 m 个用户，k 列代表 k 个用户聚类，第 i 行第 j 列的元素 Vij代表用户 i 与聚类中心 j 的相似性，即用户 i 和第 j 个用户聚类中心之间的Pearson相关相似性度量。

3.2  主要算法设计

3.2.1 离线用户聚类算法

　　算法对基本用户进行聚类的目的是产生基本用户的类别所属程度矩阵，即基本用户与各聚类中心之间的相似性矩阵，使得系统能够在线时通过类别所属程度矩阵快速搜索到目标用户的最近邻居。

　　目前的聚类方法有很多，本文采用 k-Means 算法的思想对基本用户进行聚类k-Means 算法的思想如下：

1）随机选择 k个用户作为初始的簇中心，将k个用户对项的评分作为初始的聚类中心。

2）对剩余的所有户集合，计算每个用户与k个聚类中心的相似性，将每个用户分配到相似性最高的聚类中。

3）对新生成的聚类，计算聚类中所有用户对项的平均评分，生成新的聚类中心。

4）重复以上 2 到 3 步，直到聚类不再发生改变为止。

　　由于在使用 k- Means 算法时需要事先给出聚类数目，因而本文首先采用对基本用户进行预处理用以确定聚类数目，在此过程中，首先计算基本用户两两之间的相似性，将相似性大于一定阈值的基本用户归于同一原始类别中然后选取包含用户数量最多的前k个原始类别作为初始条件，通过它们计算出k个初始聚类中心，进而进一步聚类。具体实现如下算法所示：

算法  基本用户聚类算法

输入：用户聚类的数目 K 和数据源 D=（U，I，R）

输出：用户聚类中心评分数据矩阵 C (k,n)，用户聚类程度矩阵 V（m,k）

方法：

1）从数据源 D 中读取所有m个用户，记为集合 U={u1,u2,......,um}；

2）从数据源 D 中读取所有n个项目，记为集合 I={i1,i2,......,in}；

3） 经过预处理计算产生的k个原始类别,每个原始类别中任选一个对象作为初始的聚类中心,记为集合 C={c1,c2,......,ck}；

4)  repeat

5)  for计算集合 U 中每一个用户 uj与各个聚类中心之 间的相似性 Vj1,Vj2,...,Vjk；取出这些相似性中最大值 Vjx；

6） if(该最大值>相似性阈值)，将用户 uj所属类别定为该聚类 cx；

7）同一聚类的所有用户评分的平均值作为该聚类的聚类中心的值，重新计算每个聚类中心的值；

8）until 聚类中心不再发生变化。

　　由算法可获得用户聚类中心评分数据矩阵 C(k,n)（表1所示）以及类别所属程度矩阵 V(m,k)（表2所示）。经过聚类，聚类中心数目能够远远小于基本用户的数目，即 k<<m。同时，在实际系统中，聚类中心数目能够远远小于项目的数目，即 k<<n 一般总会成立。

3.2.2 在线搜索最近邻居并产生推荐

　　本文提出的算法在上述离线处理结果的基础上，首先计算目标用户与各个聚类中心之间的相似性，获得目标用户与各个聚类之间相似程度的向量，然后搜索类别所属程度矩阵，确定目标用户的最近邻居。在线搜索近邻算法如下。

输入：用户聚类中心评分数据矩阵 C(k,n)，目标用户评分向量，用户聚类程度矩阵 V（m,k）。

输出：目标用户的 L 个最近邻居。

方法：

1）计算目标用户与 k 个聚类中心之间的相似性，获得 1*k 的向量（v1,v2,...,vk）；

2）计算向量（v1,v2,...,vk）与用户聚类程度矩阵 V（m,k）各行之间的欧氏距离；

3) 上述欧氏距离最小的前 L 个基本用户视为目标用户的最近邻居；

通过算法分析，我们得到目标用户的最近邻居后，下一步可以直接根据公式（2）产生对目标用户的推荐。

　　电子商务系统中的数据库记录了每个客户的交易数据，每笔数据记载了客户在交易中购买的商品，利用这些数据可以将客户划分到不同的簇中，同一簇中客户具有相同的购买模式。例如：某个簇中的客户主要是已婚有孩子的女士，她购买的商品主要是玩具、儿童食品等；另一簇中的客户主要是高收入者，他购买的商品主要是昂贵的进口商品。

4.实验结果分析

　　设目标用户为a，整个用户空间为P，首先在整个用户空间上作最近邻查找，选择最近邻居数目为10，查询结果为Pa；然后在与目标用户a最相似的前k个聚类（记为 c1,c2,...,ck）中作最近邻查询，最近邻居数目也选择为10，查询结果记为Pk，则本算法的有效性可以表示为只需要扫描原始数据集的（c1+c2+...+ck）/p（其中ck代表聚类ck中用户的数量，p代表整个用户空间中用户的数量）就能找到目标用户a在全部用户空间上Pk/Pa(百分比)的邻居，为了达到统计上的显著性，我们将在整个用户空间上1890个用户统计上述指标。

　　我们分别以 60、80、100 作为聚类数目对进行聚类，其最近邻居查询效率的实验结果如图2所示：

　　以上实验结果显示，在指定最近邻居数目为10的情况下，当聚类数目为60时，只需要扫描整个用户空间的40%就可以找到项集上82%的最近邻居，只需要扫描整个用户空间上 50%就可以找到整个用户集上 90%的最近邻居；当聚类数目为80时，只需要扫描整个用户空间的30%就可以找到项集上85%的最近邻居，只需要扫描整个用户空间的40%就可以找到项集上约90%的最近邻居；当聚类数目为100时，只需要扫描整个用户空间的23%就可以找到项集上85%的最近邻居，只需要扫描整个用户空间的30%就可以找到项集上90%的最近邻居。

　　从实验结果可以发现，聚类数目越大，查找目标用户的最近邻居越快，因此，基于用户兴趣度聚类的协同过滤算法可以有效提高推荐系统的实时响应速度。

5.结束语

　　针对传统协同过滤算法存在的问题，本文提出了一种基于用户兴趣度的K-means聚类协同过滤算法，其目的在于解决目前算法中存在的推荐质量低和数据稀疏性等问题。属于同一簇中的客户，他们感兴趣的商品的交集往往很大，因此，在同一簇中寻找符合要求的评价信息表会有很高的效率，即在同一簇中寻找某一目标客户的邻居也会有很高的效率，从而避免了传统协同过滤算法中在海量客户数据中寻找某一目标客户的邻居非常费时的问题；此外，由于本文采用的聚类算法分为离线和在线两部分，离线时，算法首先对基本用户聚类，在线时，算法仅仅计算目标用户与各个聚类中心的相似性，搜索目标用户的最近邻居，并产生推荐，因而在线查找目标用户的最近邻居所需时间也将大大缩短。从结果分析看，改进后的算法能够提高算法推荐的效率，从而证明了改进算法的合理性和有效性。

参考文献：

[1] 孙多. 基于兴趣度的聚类协同过滤推荐系统的设计[J]. 安徽大学学报，2007，31（5）：19~21

[2] 张志付,姜志英.一种基于聚类技术的数字图书馆个性推荐算法［J］.计算机应用与软件, 2008,25(7):84- 99

[3] 杨焱，孙铁利，邱春艳．个性化推荐技术的研究[J]．信息工程大学学报，2005，6(2)．

[4] 李宇澄．协同过滤算法研究[D]．复旦大学，2005，6

[5] 游文, 叶水生. 电子商务推荐系统中的协同过滤推荐[ J] . 计算机技术与发展, 2006( 9) : 70- 72.

[6] 王宏超, 陈未如, 刘俊. 基于客户聚类的商品推荐方法的研究[ J] . 计算机技术与发展, 2008, 18( 7) : 212- 214.