基于聚类的协同过滤推荐：信息推荐系统第二版效果

在一个用户和信息资源均数以万计的系统中，同时为数以万计的用户提供实时的推荐服务越来越困难。特别是随着电子商务的发展，商务信息资源呈几何指数增长的情况下，协同过滤推荐算法的实时性要求遇到了更大的挑战。据此，基于聚类(Custer-based)的协同过滤推荐被提出。将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类(Clustering)。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。在许多应用中，可以将一个簇中的数据对象作为一个整体来对待。在商务信息领域，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。

基于聚类的协同过滤推荐算法可以分为如下三步:

①聚类:根据用户的购买习惯和评分特点将整个用户空间划分为若干个不同的聚类，从而使得聚类内部用户对项的评分尽可能相似，而不同聚类间用户对商品的评分尽可能不同。

②虚拟用户集生成:根据每个聚类中用户对商品的评分信息生成一个虚拟用户，虚拟用户代表了该聚类中用户对商品的典型评分，将所有虚拟用户对商品的评分作为新的搜索空间。相对于原始的用户空间而言，虚拟的用户空间要小得多，因此最近邻查询的效率也高得多，可以有效提高推荐算法的实时响应速度。

③推荐产生:在虚拟的用户集合上使用各种相似性度量方法搜索当前用户的若干最近邻居，然后根据这些最近邻居对商品的评分信息产生对应的推荐结果。

目前的聚类方法有很多，这里我们采用k-means算法的思想对用户进行聚类。k-means聚类算法，也称为k-均值算法，是一种在信息系统领域广泛使用的算法。在信息协同推荐中，基于k-means聚类算法通过用户对资源项目评分的相似性来对用户进行聚类，并生成相应的聚类中心，然后计算目标用户与各聚类中心的相似度，选出与目标用户相似度最高的k个聚类中心对应的聚类，在这k个聚类中搜索目标用户的最近邻居，从而达到在尽量少的用户空间中找到目标用户的大部分最近邻居。图4-5描述了基于k-means聚类对用户进行聚类的算法[17]。

图4-5　基于k-means聚类的用户聚类算法(www.xing528.com)

该算法通过预处理产生k个用户聚类，具体过程是:在数据集中，计算所有用户两两之间的用户相似性，将相似性大于一定阈值的用户归于同一初始的聚类中。然后选取包含用户数量最多的前k个初始用户聚类作为初始聚类集C＝{c1，c2，…，ck}，并在每个聚类中随机选取一个用户对象ui，将其对资源项目的平均评分wi(1≤i≤k)作为每个聚类的聚类中心。在初始聚类形成的基础上，计算每个用户与k个聚类中心的相似度，并将该用户分配到与其相似度值最大的聚类中ci；　由于新用户加入该聚类，重新计算该聚类的聚类中心，直到所有的聚类中心不再发生变化或变化不显著为止。在图4-5中，表示用户ui对资源项目的平均评分，Ici表示用户聚类ci(1≤i≤k)中所有用户共同评分过的资源项目集，Ru，i表示用户ui对资源i的评分，表示用户聚类ci中用户的数量。通过用户聚类算法，使得聚类数目能够远远小于用户的数量，即k＜m，即将数据集中的不同用户根据对资源的偏好实现“人以群分”。同一聚类中的用户拥有最大相似程度的偏好，而不同聚类中的用户偏好尽量不同。

由于用户聚类算法中，用户之间的相似度计算所需计算量很大。如果将基于k-means的用户聚类算法放在实际推荐过程中进行，会严重影响实时推荐的效率，由此会延长人机交互时间，极大地降低信息推荐服务的质量。因此，为了减少实时推荐的计算量，我们可以将用户聚类过程放在离线阶段进行，通过对数据集中的测试用户进行聚类，将对资源具有相似偏好的用户归入同一聚类中，构建用户聚类模型。在线推荐阶段中，当目标用户达到时，首先计算目标用户与各个聚类中心的距离，判断他所归属的用户聚类，然后再在这个聚类中搜索目标用户的最近邻居，从而在尽量少的用户空间中执行基于用户的信息协同推荐算法。当产生目标用户u的最近邻居NNu后，就可以将最近邻居对候选资源的评分作为目标用户对候选资源的预测评分，目标用户u对候选资源cj的预测评分Ru，j为:

其中，用户a是目标用户u在所属聚类中的最近邻，和分别表示用户u和用户a对资源的平均评分。这里，基于用户聚类的协同推荐技术向用户推荐可能感兴趣的信息资源，该推荐系统的体系结构分为两个部分，如图4-6所示。第一部分是离线处理部分，主要完成测试数据集中的数据预处理，用户初始聚类以及聚类中心的更新等步骤；第二部分为实际的在线推荐部分，利用离线阶段构建的用户聚类模型，将目标用户归入某一用户聚类，在该聚类中产生相似用户，并根据前面基于用户的协同推荐算法生成Top-N个推荐资源，将其主动推送给目标用户查看。

图4-6　基于用户聚类的信息协同推荐系统体系结构