第一章 绪论
1.1选题背景与意义
互联网的日益普及导致了大量数据的爆炸性增长，为了解决信息过载的问题，能够帮助用户获取所需信息的推荐系统应运而生。协同过滤是推荐系统中使用的相对成功且广泛使用的技术[1]。对于不同的用户，协同过滤通过历史行为来找出与其有过类似行为的相似用户，来预测对未有过行为记录的项目的感兴趣程度。但是，可用于计算和比较用户之间相似度的有效评级数据通常十分稀疏，导致很难找到足够数量的类似用户来提供有效的建议。现阶段，通过降维对数据预处理，并且将信任关系融入相似用户查找中，被认为对提高推荐质量有一定的好处。
1.1选题背景与意义
互联网的日益普及导致了大量数据的爆炸性增长，为了解决信息过载的问题，能够帮助用户获取所需信息的推荐系统应运而生。协同过滤是推荐系统中使用的相对成功且广泛使用的技术[1]。对于不同的用户，协同过滤通过历史行为来找出与其有过类似行为的相似用户，来预测对未有过行为记录的项目的感兴趣程度。但是，可用于计算和比较用户之间相似度的有效评级数据通常十分稀疏，导致很难找到足够数量的类似用户来提供有效的建议。现阶段，通过降维对数据预处理，并且将信任关系融入相似用户查找中，被认为对提高推荐质量有一定的好处。
1.1.1选题背景
近年来，随着互联网，物联网，云计算和其他新兴 IT 技术的广泛使用，使得各类数据以前所未有的速度在增长，世界已经完全进入了信息时代。网上出现各类销售产品（书籍，电影，新闻，广告），特别是在线信息的数量是惊人的，用户要对这些产品比较和选择，然而事物数量的庞大使用户很难找到自己想要的东西，这些信息过载常常使用户不堪重负，做出不令人满意的决定。过多的信息虽然带来了过多的选择，但有一些并没有产生好的效益，开始降低用户的使用黏性。可以发现，虽然过多的选择一方面带来了好处，但过多的选择并不总是好的，用户希望的是能够轻松地得到自己想要的商品信息，做出满意的决定。
国内外众多科学家和研究人员提出了一些解决信息超载问题的方案，其中，分类目录和搜索引擎[2]是比较有效的解决方案。分类目录的方法通过将一些网站分门别类，把同类别的信息集合起来，使网站具备导航功能，用户可以根据自己的需求的按类别点击，即可获取信息。该技术主要以 Yahoo 和一些新闻类门户网站为代表。虽然现在仍可以在一些主流网站上看到目录导航的影子，但是随着信息的不断增长，信息的类别不断的扩大，每个分类下的数量也在逐级增加，需要一种更有效的解决方法。于是，一种依赖于用户主动提供关键词搜索的信息检索技术诞生了，主要的搜索引擎有国外的谷歌，必应以及国内的百度等。搜索引擎需要用户付出额外努力，只有当用户主动提供准确描述其需求的关键词时，才能提供有用信息。
.............................
1.2 国内外研究现状
1.2.1 推荐系统研究现状
关于协同过滤的研究论文[3-4]首次出现于 20 世纪 90 年代中期，自此推荐系统开始成为一个独立而又备受关注的研究领域。它可以被定义为试图通过用户或是项目的相关信息预测用户对项目的兴趣来尝试向个人或企业推荐最合适的项目（产品或服务）的程序[5]。开发推荐系统是为了从海量数据中检索出最相关的信息，从而提供个性化服务并解决信息过载问题。能够通过分析目标用户的行为或其他相似用户的行为，来预测用户的偏好和兴趣以生成个性化推荐是推荐系统的重要特征[6]。
推荐系统的的早期研究源于信息检索和信息过滤研究[7]，并且研究人员开始明确依赖评级信息的推荐问题[8]。常用的推荐技术包括协同过滤[9]，基于内容[10]和基于知识[11]的推荐。每种推荐方法都有局限性；如协同过滤技术具有稀疏性，可扩展性和冷启动问题[8-9]。尽管基于内容的推荐方法可以对推荐结果作出专业化的解释，但依然存在很多问题亟待解决，现阶段一些先进的方法已经被提出，例如基于社交网络的推荐系统[12]，模糊推荐系统[13-14]，基于情境感知的推荐系统[15]和组合推荐系统[16]。
推荐系统的应用研究包括电影，音乐，电视节目，书籍，文件，网站，涉及电子商务，电子学习，电子图书馆，政府电子服务等领域。无论我们是否注意到它，推荐系统在生活中都无处不在。在过去几十年里引起了广泛关注，众多相关奖项的设置也吸引了众多来自机器学习和数据挖掘研究领域的专家。
1.2.2 协同过滤研究现状
协同过滤是推荐算法中最为重要的，其基于显式或隐式信息相关性指示来识别用户之间或者项目之间的共性[17]。显式信息包括一些用户评级，标签等，隐式信息如一些点击浏览行为，下载等。协同过滤技术是最广泛实施和最成熟的技术[18]。经典的基于用户的协同过滤算法首先基于它们的重叠交互或共同项目的类似评级来识别类似用户，然后根据这些类似用户的偏好作出推荐。而经典的基于项目的推荐算法计算项目之间的相似性，然后根据这些相似项目来确定要推荐的项目集。基于内容的推荐算法忽略其他用户的贡献只是将项目描述和用户描述相匹配起来，通过特征提取的方法获得用户或项目的内容特征表示以作出预测[10]。组合推荐系统将这些推荐技术结合起来使用，以更少的缺点获得更优质的推荐效果[18]。
...........................
第二章 协同过滤及相关技术介绍
2.1 基于用户的协同过滤推荐算法
随着互联网和电子商务系统的发展，我们面临大量的信息需要处理。因此需要个性化推荐服务来向我们提供一些有用数据，而这些数据采用一些有效的信息过滤技术来获取。协同过滤（CF）已经被广泛使用，主要分为两种，一个是基于用户的协同过滤推荐，另一个则是基于物品的协同过滤推荐[37]。其基于相似用户（称为邻居）的评价信息向用户推荐项目，在理论和实现方面都是简单且实用的[38-39]。论文以基于用户的协同过滤推荐算法为原型进行改进。
传统基于用户的协同过滤推荐算法的原理是基于用户对观察项目的评分，来预测目标用户对未给出评级的目标项目的评级。算法具体步骤如图 2.1 所示：
...............................
2.2 矩阵分解模型及其在协同过滤中的应用
电子商务行业近阶段以指数速度增长，不断变化的需求和各种产品使得系统业务越来越复杂，在这种情况下，用户很难从大量信息中找到对自己有用的最佳信息，为了帮助买家提供便利，电子商务公司开发了各种不同的推荐系统，打开了双赢的局面。早期的协同过滤算法利用关联推断，时间复杂度和可伸缩性都表现的不太理想。而使用矩阵分解的方法更具可扩展性和效率，改善了需处理数据集大小的问题和评级矩阵稀疏性问题。
近年来，随着互联网，物联网，云计算和其他新兴 IT 技术的广泛使用，使得各类数据以前所未有的速度在增长，世界已经完全进入了信息时代。网上出现各类销售产品（书籍，电影，新闻，广告），特别是在线信息的数量是惊人的，用户要对这些产品比较和选择，然而事物数量的庞大使用户很难找到自己想要的东西，这些信息过载常常使用户不堪重负，做出不令人满意的决定。过多的信息虽然带来了过多的选择，但有一些并没有产生好的效益，开始降低用户的使用黏性。可以发现，虽然过多的选择一方面带来了好处，但过多的选择并不总是好的，用户希望的是能够轻松地得到自己想要的商品信息，做出满意的决定。
国内外众多科学家和研究人员提出了一些解决信息超载问题的方案，其中，分类目录和搜索引擎[2]是比较有效的解决方案。分类目录的方法通过将一些网站分门别类，把同类别的信息集合起来，使网站具备导航功能，用户可以根据自己的需求的按类别点击，即可获取信息。该技术主要以 Yahoo 和一些新闻类门户网站为代表。虽然现在仍可以在一些主流网站上看到目录导航的影子，但是随着信息的不断增长，信息的类别不断的扩大，每个分类下的数量也在逐级增加，需要一种更有效的解决方法。于是，一种依赖于用户主动提供关键词搜索的信息检索技术诞生了，主要的搜索引擎有国外的谷歌，必应以及国内的百度等。搜索引擎需要用户付出额外努力，只有当用户主动提供准确描述其需求的关键词时，才能提供有用信息。
.............................
1.2 国内外研究现状
1.2.1 推荐系统研究现状
关于协同过滤的研究论文[3-4]首次出现于 20 世纪 90 年代中期，自此推荐系统开始成为一个独立而又备受关注的研究领域。它可以被定义为试图通过用户或是项目的相关信息预测用户对项目的兴趣来尝试向个人或企业推荐最合适的项目（产品或服务）的程序[5]。开发推荐系统是为了从海量数据中检索出最相关的信息，从而提供个性化服务并解决信息过载问题。能够通过分析目标用户的行为或其他相似用户的行为，来预测用户的偏好和兴趣以生成个性化推荐是推荐系统的重要特征[6]。
推荐系统的的早期研究源于信息检索和信息过滤研究[7]，并且研究人员开始明确依赖评级信息的推荐问题[8]。常用的推荐技术包括协同过滤[9]，基于内容[10]和基于知识[11]的推荐。每种推荐方法都有局限性；如协同过滤技术具有稀疏性，可扩展性和冷启动问题[8-9]。尽管基于内容的推荐方法可以对推荐结果作出专业化的解释，但依然存在很多问题亟待解决，现阶段一些先进的方法已经被提出，例如基于社交网络的推荐系统[12]，模糊推荐系统[13-14]，基于情境感知的推荐系统[15]和组合推荐系统[16]。
推荐系统的应用研究包括电影，音乐，电视节目，书籍，文件，网站，涉及电子商务，电子学习，电子图书馆，政府电子服务等领域。无论我们是否注意到它，推荐系统在生活中都无处不在。在过去几十年里引起了广泛关注，众多相关奖项的设置也吸引了众多来自机器学习和数据挖掘研究领域的专家。
1.2.2 协同过滤研究现状
协同过滤是推荐算法中最为重要的，其基于显式或隐式信息相关性指示来识别用户之间或者项目之间的共性[17]。显式信息包括一些用户评级，标签等，隐式信息如一些点击浏览行为，下载等。协同过滤技术是最广泛实施和最成熟的技术[18]。经典的基于用户的协同过滤算法首先基于它们的重叠交互或共同项目的类似评级来识别类似用户，然后根据这些类似用户的偏好作出推荐。而经典的基于项目的推荐算法计算项目之间的相似性，然后根据这些相似项目来确定要推荐的项目集。基于内容的推荐算法忽略其他用户的贡献只是将项目描述和用户描述相匹配起来，通过特征提取的方法获得用户或项目的内容特征表示以作出预测[10]。组合推荐系统将这些推荐技术结合起来使用，以更少的缺点获得更优质的推荐效果[18]。
...........................
第二章 协同过滤及相关技术介绍
2.1 基于用户的协同过滤推荐算法
随着互联网和电子商务系统的发展，我们面临大量的信息需要处理。因此需要个性化推荐服务来向我们提供一些有用数据，而这些数据采用一些有效的信息过滤技术来获取。协同过滤（CF）已经被广泛使用，主要分为两种，一个是基于用户的协同过滤推荐，另一个则是基于物品的协同过滤推荐[37]。其基于相似用户（称为邻居）的评价信息向用户推荐项目，在理论和实现方面都是简单且实用的[38-39]。论文以基于用户的协同过滤推荐算法为原型进行改进。
传统基于用户的协同过滤推荐算法的原理是基于用户对观察项目的评分，来预测目标用户对未给出评级的目标项目的评级。算法具体步骤如图 2.1 所示：
...............................
2.2 矩阵分解模型及其在协同过滤中的应用
电子商务行业近阶段以指数速度增长，不断变化的需求和各种产品使得系统业务越来越复杂，在这种情况下，用户很难从大量信息中找到对自己有用的最佳信息，为了帮助买家提供便利，电子商务公司开发了各种不同的推荐系统，打开了双赢的局面。早期的协同过滤算法利用关联推断，时间复杂度和可伸缩性都表现的不太理想。而使用矩阵分解的方法更具可扩展性和效率，改善了需处理数据集大小的问题和评级矩阵稀疏性问题。
矩阵分解技术最近获得了越来越多研究者的关注，主要是作为潜在变量分解和降维的无监督学习方法[41]，它已经成功应用于光谱数据分析和文本挖掘。评级矩阵被建模成用户因子矩阵和项目因子矩阵的乘积。Sarwar 等人应用矩阵分解模型 SVD 来降低评级矩阵的维数[42]。 他们使用 MovieLens 数据集，选择 943 个用户组成943?1682矩阵，稀疏率为 95.4%（平均每个用户的有效评分占电影总数的 5%）。他们首先使用平均值填充缺失值，然后将 SVD 应用在基于项目的协同过滤算法中，显著提高了在线推荐的速度和质量。Goldberg 等人提出了一种在线环境中使用主成分分析（PCA）的方法[25]，该算法被称为 Eigentaste，使用通用查询在一组公共项上引出实值，确保所有用户对一组共同的 k 项进行评级。因此，得到的子矩阵将是密集的并直接计算对称相关矩阵，然后使用主成分分析（PCA）进行线性投影，PCA 是 Pearson在 1901 年首次描述的一种密切相关的因子分析技术。与 SVD 一样，PCA 降低了维数，通过沿较少数量的正交维度最佳地投射高度相关的数据来获得矩阵，有助于降低用户离线集群的维数并快速计算得出建议。Royi Ronen 等人提出了一种新的概率矩阵分解模型[43]，并可将推荐服务集成到任何网站中。 矩阵分解方法被认为是减少数据稀疏性的精确方法。下文主要介绍几种常见的矩阵分解模型。
...........................
...........................
第三章 基于预填充的 SVD 降维 ................................... 17
3.1基于预填充的 SVD 降维基本思想 ................................ 17
3.2基于项目评分预测的预填充 .................................... 18
第四章 融入信任因子的二阶段聚类推荐算法.................................. 24
4.1基于信任模糊聚类的基本思想 .............................................. 24
4.2基于模糊聚类的一阶段近邻查找 ...................................... 25
第五章 实验结果分析与应用 ..................................... 34
5.1实验数据及设计 .................................. 34
5.2 推荐结果评测指标 ................................. 34
第五章 实验结果分析与应用
5.1 实验数据及设计
本文采用 GroupLens 提供的 MovieLens 数据集评测各种算法。这些数据集是电影推荐系统中用户行为的产物，由收集的电影评级数据子集组成，有多种不同的版本，广泛用于教育和研究中，每年被下载数十万次，反应了它们在流行的编程书籍，传统和在线课程以及软件中的应用。
选用其中最小的数据集来进行评测，其中包含 943 个用户对 1682 部电影的 100000 个评分，每个用户评分至少 20 个项目。MovieLens 数据中的评级由用户明确输入，整数范围为 1到 5。包括了用户的人口统计数据（年龄，性别，职业，邮政编码），电影的属性被分为动作、冒险、战争等 19 个不同的类，评分数据密度只有 6.30%，稀疏度很高。
实验中，将 4：1 的比例分割训练集和测试集数据，随机生成 5 组数据，每组中 80%的数据用作训练数据，而另外 20%用作测试。这样可以保证训练数据与测试数据都是随机的且都来自同一数据集。重复交叉验证 5 次，得到五个结果，取平均值作为最后的实验结果。
实验设计： 第一步，在实验中确定融入信任因子的二阶段聚类推荐算法中的两个未知参数：
（1） 第三章中奇异值分解保留的维度 k 值；
（2） 第四章中聚类的用户簇个数。
第二步，通过实验说明在算法中加入聚类的过程对可扩展性有影响，最后将改进的算法分别与基于用户的、基于聚类的、基于 SVD 的协同过滤算法进行对比，验证其是否提高了推荐准确度。
...........................
第六章 总结与展望
6.1 论文总结
随着互联网的快速发展，网络信息以爆炸式地增长，导致用户无法在庞大的数据信息中筛选有价值的信息，信息过载问题亟待解决。在此背景下，个性化推荐系统应运而生。具体而言，推荐系统是基于用户的历史行为数据或物品数据，通过有效的算法，为用户推荐符合他需求的物品。协同过滤算法是广泛使用的推荐算法之一，它使用用户对项目的评级来衡量用户的兴趣偏好，并根据分数进行推荐。从算法的流程中可以观察到，数据的稀疏程度很高，即使用户非常活跃，对项目的评级数量也非常少，由于协同过滤算法主要基于在共同评定的项目集上计算相似度，大量稀疏性会导致精度降低，而且每次有新用户进来都要两两计算相似度，计算的代价很昂贵，随着用户项目数量的增长，计算代价也会呈现非线性地增长。
本文为了解决以上问题，从原始输入的数据，搜索邻居集合的计算量，寻找更优的邻居集合等方面对基础算法进行改进。首先对稀疏矩阵预填充，接着使用 SVD 降维并得到用户特征矩阵，然后在缩小的空间中引入聚类和信任关系查找近邻，提高推荐质量。最后通过仿真实验验证其有效性。主要工作可概括为以下几个方面：
6.1 论文总结
随着互联网的快速发展，网络信息以爆炸式地增长，导致用户无法在庞大的数据信息中筛选有价值的信息，信息过载问题亟待解决。在此背景下，个性化推荐系统应运而生。具体而言，推荐系统是基于用户的历史行为数据或物品数据，通过有效的算法，为用户推荐符合他需求的物品。协同过滤算法是广泛使用的推荐算法之一，它使用用户对项目的评级来衡量用户的兴趣偏好，并根据分数进行推荐。从算法的流程中可以观察到，数据的稀疏程度很高，即使用户非常活跃，对项目的评级数量也非常少，由于协同过滤算法主要基于在共同评定的项目集上计算相似度，大量稀疏性会导致精度降低，而且每次有新用户进来都要两两计算相似度，计算的代价很昂贵，随着用户项目数量的增长，计算代价也会呈现非线性地增长。
本文为了解决以上问题，从原始输入的数据，搜索邻居集合的计算量，寻找更优的邻居集合等方面对基础算法进行改进。首先对稀疏矩阵预填充，接着使用 SVD 降维并得到用户特征矩阵，然后在缩小的空间中引入聚类和信任关系查找近邻，提高推荐质量。最后通过仿真实验验证其有效性。主要工作可概括为以下几个方面：
（1）论文通过阅读大量的文献，归纳总结推荐系统的研究现状，分析了一些传统推荐算法的优缺点，着重介绍了协同过滤，以及针对其不足，研究者们提出的各种思路的解决方法。
（2）介绍了传统的基于用户的协同过滤算法及本文改进模型所涉及的相关技术基础，包括矩阵分解和聚类分析及其在协同过滤算法中的应用。关于矩阵分解，介绍了其基本思想以及两种经典的分解算法；关于聚类分析，主要对其基本方法，分类和最具代表性的基于划分的聚类算法进行了描述，并简单介绍了基于聚类的协同过滤推荐算法。
（3）研究矩阵分解模型中应用广泛的奇异值分解算法，利用 SVD 算法将原始高维矩阵降到低维空间，并且自动抽取矩阵重要特征，可以降低系统计算维度。并使用改进的 SVD 降维之前，用基于项目评分预测的评分矩阵预填充方法，解决了用平均值填充缺省值的不足，
（2）介绍了传统的基于用户的协同过滤算法及本文改进模型所涉及的相关技术基础，包括矩阵分解和聚类分析及其在协同过滤算法中的应用。关于矩阵分解，介绍了其基本思想以及两种经典的分解算法；关于聚类分析，主要对其基本方法，分类和最具代表性的基于划分的聚类算法进行了描述，并简单介绍了基于聚类的协同过滤推荐算法。
（3）研究矩阵分解模型中应用广泛的奇异值分解算法，利用 SVD 算法将原始高维矩阵降到低维空间，并且自动抽取矩阵重要特征，可以降低系统计算维度。并使用改进的 SVD 降维之前，用基于项目评分预测的评分矩阵预填充方法，解决了用平均值填充缺省值的不足，
使在用户评分数据极度稀疏的情况下，提高推荐质量。
(4)研究聚类算法中的模糊聚类，首先运用模糊聚类算法在缩小的空间中进行目标用户的一阶段近邻查找，将用户进行软分类，允许一个对象按照不同的概率属于不同的簇，每一簇中为具有相似偏好的用户。然后将信任因子融入相似度空间中，进行二阶段信任用户查找，计算信任度，选取一定数目信任度比较高的用户建立信任邻居群集合。二重聚类提高了邻居查找的准确度，减轻了数据稀疏带来的不利影响，使得预测评分更加准确。
参考文献（略）
(4)研究聚类算法中的模糊聚类，首先运用模糊聚类算法在缩小的空间中进行目标用户的一阶段近邻查找，将用户进行软分类，允许一个对象按照不同的概率属于不同的簇，每一簇中为具有相似偏好的用户。然后将信任因子融入相似度空间中，进行二阶段信任用户查找，计算信任度，选取一定数目信任度比较高的用户建立信任邻居群集合。二重聚类提高了邻居查找的准确度，减轻了数据稀疏带来的不利影响，使得预测评分更加准确。
参考文献（略）