算法 自动采集列表(本文微言导论：探索推荐引擎内部的秘密(组图))

　　算法 自动采集列表(本文微言导论：探索推荐引擎内部的秘密(组图))

　　来源：结构与算法之道

　　介绍

　　昨天看了几个关键词：语义分析、协同过滤、智能推荐，想想就兴奋。于是从昨天下午到今天凌晨3点，我研究了推荐引擎，做了一个初步的了解。以后我会慢慢深入的仔细研究（以后的工作也跟这个有关）。当然，这篇文章会逐渐增加和完善。

　　本文是推荐引擎初步介绍的入门文章，将省略大部分具体细节，重点用最简单的语言简单介绍推荐引擎的工作原理及其相关算法思想，并为了强调通俗易懂，部分引述来自我1月7日在微博上发表的文字（特地整理一下，方便以后随时阅读），尽量让这篇文章尽量简短. 不过，恰恰相反，文章后续的补充和改进，越写越长。

　　同时，本文所有相关算法，后续会一一详述文章。本文只求简要介绍，以后力求具体。如果您有任何问题，请随时给我任何建议或批评。谢谢。

　　1、推荐引擎原理

　　推荐引擎尽最大努力采集尽可能多的用户信息和行为。所谓广布网，勤钓，再“特爱一个特别的你”，最后在相似的基础上继续“强大”。原理如下图所示（该图引自本文的参考资料之一：Exploring the secrets inside the Recommendation engine）：

　　

　　2、推荐引擎的分类

　　推荐引擎根据不同的标准分类如下：

　　根据是否为不同用户推荐不同的数据，根据公众行为划分热门项目（网站管理员自己推荐，或者根据系统所有用户的反馈统计，计算当前热门项目） ，以及个性化的推荐引擎（帮助你找到志同道合的朋友，然后在此基础上实施推荐）；物品具有相同的关键词和Tag，不考虑人为因素），以及基于协同过滤的推荐（寻找物品、内容或用户的相关推荐，分为三个子类，下文解释）；根据构建方式，分为物品和用户本身（user-item二维矩阵描述用户偏好，聚类算法），

　　关于上面第二类基于协同过滤的推荐（2、根据其数据来源）：随着Web2.0的发展，网站更加促进用户参与和用户贡献，所以基于关于协同过滤的过滤推荐机制应运而生。它的原理很简单，就是根据用户对物品或信息的偏好，找到物品或内容本身的相关性，或者发现用户的相关性，然后根据这些相关性进行推荐。

　　基于协同过滤的推荐分为三个子类：

　　基于用户的推荐（通过共同的品味和喜好找到相似的邻居用户，K-nei*敏*感*词*or算法，你的朋友喜欢，你可能喜欢），基于物品的推荐（找到物品之间的相似性，推荐相似的物品，你喜欢） Item A 和 C 与 A 类似，也可能像 C)，基于模型的推荐（基于样本用户偏好信息构建推荐模型，然后根据实时用户偏好信息预测推荐）。

　　我们看到这种协同过滤算法最大限度地利用了用户之间或物品之间的相似相关性，然后根据这些信息实现推荐。这种协同过滤也在下面详细描述。

　　但是，在一般实践中，我们通常将推荐引擎分为两类：

　　3、新浪微博推荐机制

　　新浪微博推荐好友机制中：1、我和A不是朋友，但是我的很多朋友都是A的朋友，也就是说我和A有很多共同的朋友，那么系统会推荐A给我（新浪称其为共同的朋友）；2、我关注的很多人​​都关注了B，所以系统推测我可能喜欢B，所以也会推荐B给我（新浪称其为间接关注）。

　　但在新浪的实际运营中，这两种方式会混用。比如我关注的人中，关注B的人很多，但其实关注B的一些人也是我的朋友。以上推荐方法统称为基于相似用户的协同过滤推荐（无非是发现：用户之间的密不可分的联系，要么来自你的朋友，要么来自你关注的人）。

　　当然，还有另外一种推荐，比如热门用户推荐，就是上面提到的基于热门行为的推荐，也就是听从别人的意见。系统推测每个人都喜欢它，也许你也会喜欢。如果大家都知道姚晨的新浪微博粉丝数第一，就会争先恐后地关注，最终粉丝数会越来越多。推荐的两种方法如下图所示：

　　

　　然而，上述的推荐方法，无论是基于用户还是基于流行行为，都没有真正找到用户之间的共同兴趣、喜好和品味，因为很多情况下，朋友的朋友可能不是你自己。朋友，有些人凌驾于世界之上，你们都追求什么，我不屑一顾。因此，从分析用户发布的微博内容入手，找到他们共同的关注点和兴趣点才是王道。当然，新浪微博最近让用户选择给自己的微博内容打标签，以帮助日后在微博内容中找到相关用户的常用标签，关键词，这种推荐方式是基于微博内容分析'的推荐。如下所示：

　　

　　唯一的问题是，谁会不遗余力地发一条微博，它会添加什么标签？因此，新浪微博不得不努力寻找另一种方式来更好地分析微博的内容。否则，系统会彻底扫描海量用户的微博内容，恐怕承受不起，也承受不起。

　　不过我个人认为可以从微博关键词（标签标签云）和每个用户自己标签的标签入手（标签越常见，可以定义的相似用户越多），如图下图左右部分：

　　

　　

　　也就是说，通过普通朋友和间接关注的人来定义相似用户是不可靠的。只有通过微博内容分析，才能找到相似的用户。经过对标签云的分析，无疑比现有的推荐朋友的方法（通过普通朋友和间接关注者定义相似用户）找到相同或相似的标签云找到相似用户更可靠。

　　3.1、多种推荐方式组合

　　当前网站的推荐往往不是简单地使用某种推荐机制和策略，而是往往结合多种方法来达到更好的推荐效果。

　　例如，亚马逊除了基于用户的推荐外，还使用基于内容的推荐（关键词和Tag相同的商品）：比如新品推荐；基于项目的协同过滤推荐（喜欢）。A、C 与 A 类似，也可能与 C) 类似：如捆绑销售和他人购买/浏览的商品。

　　简而言之，多种推荐方法和权重的组合（使用线性公式）根据一定的权重组合了几种不同的推荐。具体权重的值需要在测试数据集上反复测试，才能达到最好的推荐效果。)、切换、分区、分层等。但是，无论采用哪种推荐方法，一般都被上述推荐方法所覆盖。

　　4、协同过滤推荐

　　协同过滤是利用集体智慧的典型方式。要了解什么是协同过滤 (CF)，首先要考虑一个简单的问题。如果你现在想看电影，但不知道该看哪一部，你会怎么做？大多数人会问广义的朋友或邻居，看看最近推荐了哪些好电影，而我们一般更喜欢从口味相似的朋友那里获得推荐。这就是协同过滤的核心思想。从下图中你能看出多少信息？

　　

　　4.1、 协同过滤推荐步骤

　　做协同过滤推荐，一般做以下步骤：

　　1）要进行协同过滤，采集用户偏好是关键。可以通过评分等用户行为判断为相似用户（比如不同用户对不同作品的评分不同，评分接近意味着品味和品味相近，可以判断为相似用户）、投票、转发、采集、书签、标签、评论、点击流、页面停留时间、是否购买等。如下面第2点所述：所有这些信息都可以数字化并表示为二维矩阵。

　　2）采集到用户行为数据后，接下来需要对数据进行去噪和归一化处理（得到用户偏好的二维矩阵，一维是用户列表，另一维是物品列表，该值是用户对项目的偏好，通常是 [0,1] 或 [-1,1] 的浮点值）。下面简单介绍降噪和归一化操作：

　　3）如何找到相似的用户和物品？就是计算相似用户或相似物品的相似度。

　　4）计算相似度的方法有很多种，但都是基于向量Vector。其实就是计算两个向量之间的距离。距离越近，相似度越大。在推荐中，在user-item偏好的二维矩阵下，我们以一个或多个用户对两个item的偏好为向量，计算两个item之间的相似度，或者两个用户对一个或多个的偏好几个项目被用作一个向量来计算两个用户之间的相似度。

　　相似度计算算法可用于计算用户或物品的相似度。以物品相似度计算（Item Similarity Computation）为列，共同点是从打分矩阵中为两个物品i和j选取共同打分用户，然后对这个共同用户的打分向量进行相似度计算. si,j，如下图，行代表用户，列代表物品（注意从i,j向量中抽取常用评论，形成一对向量计算相似度） ：

　　

　　因此，很简单的找到物品之间的相似度，用户不变，找到多个用户对物品的评分；求用户之间的相似度，item不变，求用户对某些item的评分。

　　5）计算出来的两个相似度将作为两个基于用户和物品的协同过滤推荐。

　　计算相似度的常用方法有：欧式距离、皮尔逊相关系数（比如两个用户对多部电影的评分，使用皮尔逊相关系数等相关计算方法，可以判断他们的口味和喜好是否一致）、余弦相似度，谷本系数。下面简单介绍一下欧几里得距离和皮尔逊相关系数：

　　

　　可以看出，当n=2时，欧几里得距离就是平面上两点之间的距离。当用欧式距离表示相似度时，一般采用如下公式进行转换：距离越小，相似度越大（同时避免除数为0）：

　　

　　

　　其中，Ru,i 是用户 u 对 item i 的评分，对应的带有横条的 item 是这个用户集 U 对 item i 的评分。

　　6）类似的邻居计算。邻居分为两类： 1、 固定数量的邻居K-nei*敏*感*词*orhoods（或Fix-sizenei*敏*感*词*orhoods），不管邻居的“距离”如何，只取最近的K作为他们的邻居，如部分所示下图A；2、基于相似度阈值的邻居，以当前点为中心，距离为K的区域内的所有点都被视为当前点的邻居，如下图B部分所示。

　　

　　让我们介绍一下 K-Nearest Nei*敏*感*词*or (KNN) 分类算法：这是一种理论上成熟的方法，也是最简单的机器学习算法之一。该方法的思想是：如果特征空间中k个最相似的样本（即特征空间中的最近邻）中的大部分属于某个类别，则该样本也属于该类别。

　　7）4)计算的基于用户的CF（基于用户推荐：通过共同的品味和喜好找到相似的邻居用户，K-nei*敏*感*词*or算法，如果你的朋友喜欢，你可能也会喜欢），基于item的CF（基于item的推荐：查找item之间的相似度，推荐相似的item，如果你喜欢item A，如果C和A相似，那么你可能也喜欢C）。

　　4.2、基于用户相似度和物品相似度

　　上一节3.1中的三个相似度公式都是基于物品相似度的场景，但实际上用户相似度和物品相似度计算的一个基本区别是，用户相似度是基于评分矩阵中的行向量相似度求解，项目相似度计算公式是根据评分矩阵中的列向量相似度计算的。那么这三个公式就可以分别套用了，如下图所示：

　　

　　（其中，0表示未评级）

　　一千字不如一个例子。我们来看一个基于用户相似度计算的具体例子。

　　假设我们有一组用户，他们表现出对一组书籍的偏好。用户对一本书的偏好越高，它的评分就越高。让我们将其表示为一个矩阵，其中行代表用户，列代表书籍。

　　如下图所示，所有评分的范围从 1 到 5，其中 5 是最喜欢的。第一个用户（行 1） 为第一本书评分（列 1） 为 4，空单元格表示用户没有对该书评分。

　　

　　使用基于用户的协同过滤方法，我们首先要做的是根据用户对图书的评价来计算用户之间的相似度。

　　让我们从单个用户的角度考虑这一点，查看图 1 中的第一行。为此，通常将每个用户表示为收录用户偏好的向量（或数组）。它比使用不同的相似性度量更直接。

　　在这个例子中，我们将使用余弦相似度来计算用户之间的相似度。

　　当我们将第一个用户与其他五个用户进行比较时，我们可以直观地看到他与其他用户的相似程度。

　　对于大多数相似度度量，向量之间的相似度越高，它们之间的相似度就越高。在这个例子中，第一个用户二、，第三个用户非常相似，有两本书相同，和第五个用户四、相似度较低，只有一本书相同，并且完全与上一个用户不同，因为没有共同的书。

　　

　　更一般地，我们可以计算每个用户的相似度，并在相似度矩阵中表示它们。这是一个对称矩阵，单元格的背景颜色表示用户的相似程度，较深的红色表示他们之间的相似程度更高。

　　

　　因此，我们找到与第一个用户最相似的第二个用户，删除该用户已经评分的书籍，对最相似的用户正在阅读的书籍进行加权，并计算总和。

　　在这种情况下，我们计算n=2，也就是说为了生成推荐，我们需要找到与目标用户最相似的两个用户，这两个用户分别是第二个和第三个用户，然后是第一个用户已经给第一和第五本书评分了，所以推荐的书是第三本书（4.5分），第四本书（3分）。

　　

　　此外，何时使用 item-base 以及何时使用 user-base： ?

　　一般来说，如果item的数量不大，比如不超过100,000，并且没有明显增长，那么就使用item-based。为什么？正如@wuzh670所说，如果item数量少+没有明显增加，说明item之间的关系在一段时间内比较稳定（相对于用户之间的关系），对实时更新item的需求- 相似度低很多，降低了推荐系统的效率。改进很多，所以使用基于项目会更明智。

　　反之，当item数量较多时，推荐使用user-base。当然，在实践中的具体情况将根据具体情况进行分析。如下图所示（摘自向亮的《推荐系统实践》一书）：

　　

　　5、聚类算法

　　聚类 聚类，通俗地说，就是所谓的“物聚在一起，人分群”。聚类是数据挖掘的经典问题。其目的是将数据划分为多个簇，同一簇中的对象具有高度的相似性，而不同簇中的对象则不同。较大。

　　5.1、K-Means 聚类算法

　　K-Means 聚类算法与处理混合正态分布的期望最大化算法非常相似，因为它们都试图在数据中找到自然聚类的中心。该算法假设对象属性来自空间向量，目标是最小化每个组内的均方误差之和。

　　K-means 聚类算法首先随机确定 K 个中心位置（空间中代表聚类中心的点），然后将每个数据项分配到最近的中心点。分配完成后，集群中心将移动到分配给集群的所有节点的平均位置，然后整个分配过程重新开始。重复这个过程，直到分配过程不再改变。下图是一个有两个聚类的 K-means 聚类过程：

　　

　　以下代码显示了此 K-means 聚类算法的 python 实现：

　　//K-均值聚类算法

import random

def kcluster(rows,distance=pearson,k=4):

# 确定每个点的最小值和最大值

ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows]))

for i in range(len(rows[0]))]

# 随机创建k个中心点

clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0]

for i in range(len(rows[0]))] for j in range(k)]

lastmatches=None

for t in range(100):

print 'Iteration %d' % t

bestmatches=[[] for i in range(k)]

# 在每一行中寻找距离最近的中心点

for j in range(len(rows)):

row=rows[j]

bestmatch=0

for i in range(k):

d=distance(clusters[i],row)

if d0:

for rowid in bestmatches[i]:

for m in range(len(rows[rowid])):

avgs[m]+=rows[rowid][m]

for j in range(len(avgs)):

avgs[j]/=len(bestmatches[i])

clusters[i]=avgs

# 返回k组序列，其中每个序列代表一个聚类

return bestmatches

　　k-Means 是机器学习领域的一种无监督学习。下面简单介绍监督学习和无监督学习：

　　5.2、冠层聚类算法

　　Canopy聚类算法的基本原理是：首先，利用低成本的近似距离计算方法将数据高效地划分为多个组，这里称为Canopy，我们将其翻译为“canopy”。重叠部分；然后使用严格的距离计算方法，准确计算出同一个 Canopy 中的点，并将它们分配到最合适的簇中。Canopy聚类算法常用于K-means聚类算法的预处理，寻找合适的k值和聚类中心。

　　5.3、模糊K-Means聚类算法

　　模糊 K-means 聚类算法是 K-means 聚类的扩展。它的基本原理和K-means一样，只是它的聚类结果允许对象属于多个聚类，也就是说：属于我们前面介绍过的重叠。聚类算法。为了深入理解Fuzzy K-means和K-means的区别，这里我们得花点时间来理解一个概念：Fuzzziness Factor。

　　与K-means聚类原理类似，模糊K-means也在待聚类对象的向量集上循环，但它并不将向量分配给最近的簇，而是计算向量与每个簇的相关性（协会）。假设有一个向量v，有k个簇，v到k个簇中心的距离分别为d1，d2...dk，那么V到第一个簇的相关性u1可以通过下式计算：

　　

　　计算 v 与其他集群的相关性只需将 d1 替换为相应的距离。由上式可知，当m近似为2时，相关性近似为1；当m近似为1时，相关性近似为到簇的距离，所以m的取值为(1,2）区间内，m越大，模糊程度越大，m为模糊我们刚才提到的参数。

　　其余的聚类算法本文将不做介绍。冷启动、数据稀疏性、可扩展性、可移植性、可解释性、多样性以及推荐信息的价值等问题将在后面讨论。

　　6、分类算法

　　其次，还有很多分类算法。本文介绍了决策树学习和贝叶斯定理。

　　6.1、决策树学习

　　让我们直奔主题。所谓决策树，顾名思义，就是一种树，是建立在战略选择基础上的树。

　　在机器学习中，决策树是一种预测模型；它表示对象属性和对象值之间的映射关系。树中的每个节点代表一个对象，每个分支路径代表一个可能的属性值，每个叶节点对应于从根节点到叶节点的路径所代表的对象。价值。决策树只有一个输出。如果你想有多个输出，你可以建立一个独立的决策树来处理不同的输出。

　　从数据中生成决策树的机器学习技术称为决策树学习，通常称为决策树。

　　理论太抽象了。这里有两个容易理解的例子：

　　第一个例子：通俗地说，决策树分类的思想类似于找对象。现在想象一个女孩的妈妈想给女孩介绍一个男朋友，于是就有了如下对话：

　　女儿：你几岁？

　　母亲：26。

　　女儿：帅吗？

　　妈妈：很帅。

　　女儿：收入高吗？

　　妈妈：不是很高，中等状态。

　　女儿：是*敏*感*词*吗？

　　妈妈：是的，我在*敏*感*词*工作。

　　女儿：好的，我去看你。

　　这个女孩的决策过程是典型的分类树决策。相当于把男人按年龄、外貌、收入和是否*敏*感*词*分为两类：看和看。假设女孩对男人的要求是：30岁以下，中等相貌，高收入人士或中等收入以上的*敏*感*词*，那么女孩的决策逻辑可以表示为：数字：

　　

　　也就是说，决策树的简单策略就是，就像在公司招聘面试的过程中筛选一个人的简历，如果你的条件比较好，比如清华大学的博士，那么事不宜迟，直接致电面试，如果你毕业于非重点大学，但实际项目经验丰富，那么你也应该考虑要求面试，也就是所谓的具体分析和决策。

　　第二个例子来自 Tom M. Mitchell 的《机器学习》一书：

　　王的目的是通过下周的天气预报了解人们什么时候打高尔夫球。他明白人们决定是否参加比赛的原因取决于天气。天气条件晴朗、多云和下雨；华氏气温；相对湿度百分比；有风或缺席。这样，我们就可以构造如下决策树（根据天气的分类判断今天是否适合打网球）：

　　

　　上面的决策树对应如下表达式：(Outlook=Sunny ^Humiditywind gain 0.048。说白了，在周六早上是否适合打网球的问题上，最好取湿度而不是风作为分类属性，决策树来自哪里。

　　ID3算法决策树的形成

　　OK，下图是ID3算法第一步之后形成的部分决策树。综合起来，比较容易理解。1、阴的例子一定是正的，所以是叶子节点，永远是；2、ID3没有回溯，局部最优，不是全局最优，还有一个post-tree pruning决策树。下图是经过ID3算法第一步后形成的部分决策树：

　　

　　6.2、贝叶斯分类基础：贝叶斯定理

　　贝叶斯定理：知道一个条件概率，如何得到两个事件交换的概率，即在已知P(A|B)的情况下如何得到P(B|A)。以下是条件概率的解释：

　　

　　在事件 B 已经发生的前提下，事件 A 发生的概率称为事件 B 发生下事件 A 的条件概率。其基本解公式为：

　　

　　.

　　贝叶斯定理之所以有用，是因为我们在生活中经常会遇到这样的情况：我们可以很容易地直接得到 P(A|B)，P(B|A) 很难直接得到，但是我们更关心 P(B|A) , 贝叶斯定理为我们从 P(A|B) 得到 P(B|A) 开辟了道路。

　　下面直接给出贝叶斯定理，无需证明（公式已被网友指出，待后续验证修正）：

　　

　　7、推荐的实例扩展

　　7.1、阅读推荐