LBS推荐系统的设计方法

在《程序员》12月刊A中，我们介绍了POI（兴趣点）的设计及其搜索。由于推荐系统是兴趣点系统的核心，所以接下来，我们将介绍推荐系统。推荐系统是一个很庞大的课题，将分成两期予以介绍：本期讲述推荐系统的设计方法，包含推荐系统的数学基础和设计原理。

关于推荐系统有很多经典的应用，比如：淘宝/天猫/亚马逊上的商品都是通过推荐系统来排列的；各种音乐应用（比如网易云音乐或者虾米音乐）都是按照推荐系统的原理来向用户推荐音乐的；今日头条等新闻推荐应用已经充分说明了新闻推荐的力量；Netflix的电影推荐技术也为优酷/搜狐等视频应用指明了道路。LBS应用的推荐系统的原理与这些典型的推荐系统应用的基本原理相同，比如：美团/糯米的兴趣点推荐，淘宝/支付宝口碑的兴趣点推荐。

希望通过这两期的介绍，读者可以明白一个推荐系统的设计原理，以及如何应用。在本期中我们将首先讲述推荐系统的前世今生，之后讲述推荐系统的数学基础，最后讲述推荐系统的设计原理。

推荐系统的前世今生

随着互联网的发展，人们正处于一个信息爆炸的时代。相比于过去的信息匮乏，面对现阶段海量的信息数据，对信息的筛选和过滤成为了衡量一个系统好坏的重要指标。一个具有良好用户体验的系统，会将海量信息进行筛选、过滤，将用户最关注最感兴趣的信息展现在用户面前。这大大增加了系统工作的效率，也节省了用户筛选信息的时间。

搜索引擎的出现在一定程度上解决了信息筛选问题，但还远远不够。搜索引擎需要用户主动提供关键词来对海量信息进行筛选。当用户无法准确描述自己的需求时，搜索引擎的筛选效果将大打折扣，而用户将自己的需求和意图转化成关键词的过程本身就是一个并不轻松的过程。

在此背景下，推荐系统出现了，推荐系统是一种利用历史数据的关联分析，是一种通过对用户的行为数据进行挖掘，从而向用户推荐有用的信息技术。推荐系统是最典型的数据挖掘应用，也是知名度最高的数据挖掘应用。 推荐系统的任务就是解决上述的问题，联系用户和信息，一方面帮助用户发现对自己有价值的信息，另一方面让信息能够展现在对他感兴趣的人群中，从而实现信息提供商与用户的双赢。

推荐系统的数学基础

推荐系同的数学基础是距离，和相关系数。距离和相关系数的本质都是相似度。距离用来表示两个（组）散乱数据间的相似度；而相关系数用来表示两组近似线性的数据的相似度。相似度计算是各种数据挖掘算法的主要数学基础。比如：聚类算法中往往是利用数据间的彼此距离或者相关系数进行计算的。基于实例的学习中的K近邻算法，及关联分析也是利用距离或相关系数作为数据基础的。各种推荐算法在本质上只是某一种计算相关系数的方法而已。限于篇幅，以下仅介绍几种常见距离和相关系数，其他详细内容，可参见我撰写的《LBS核心技术揭秘》一书。

距离

距离是聚类的基础 ,是最重要的数据挖掘中最重要的概念之一，也是衡量相似度的主要指标之一。距离有很多种，各种距离的应用场景可以简单概括为：

• 空间：欧氏距离；
• 路径：曼哈顿距离；
• 国际象棋国王：切比雪夫距离；
• 欧氏距离、曼哈顿距离、切比雪夫距离三种距离的统一形式：闵可夫斯基距离；
• 加权：标准化欧氏距离；
• 排除量纲和依存：马氏距离；
• 编码差别：汉明距离。

在各种距离中，闵可夫斯基距离是最常见的一种距离。

1.闵可夫斯基距离

两个n维变量a(x11，x12，…，x1n)与b(x21，x22，…，x2n)间的闵可夫斯基距离(Minkowski Distance)定义为：

其中p是一个变参数。

当p=1时，就是曼哈顿距离

当p=2时，就是欧氏距离

当p→∞时，就是切比雪夫距离

根据变参数的不同，闵氏距离可以表示一类的距离。

（1）欧氏距离。 最常见的两点之间或多点之间的距离表示法又称之为欧几里得度量，它定义于欧几里得空间中，如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为：

• 二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：

• 三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：

两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：

也可以用表示成向量运算的形式：

标准化欧氏距离 (Standardized Euclidean distance)是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。

假设样本集X的数学期望或均值(mean)为m，标准差(standard deviation，方差开根)为s，那么X的“标准化变量”X*表示为：(X-m）/s，而且标准化变量的数学期望为0，方差为1。

即样本集的标准化过程(standardization)用公式描述就是：

标准化后的值=(标准化前的值－分量的均值) /分量的标准差

经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式：

（2）曼哈顿距离。 曼哈顿距离的正式意义为L1-距离或城市区块距离(City Block distance)，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对坐标轴产生的投影的距离总和。例如在平面上，坐标（x1,y1）的点P1与坐标（x2,y2）的点P2的曼哈顿距离为： ，要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。

• 二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离：

• 两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的曼哈顿距离：

（3）切比雪夫距离。 若二个向量或二个点p、q，其座标分别为 及 ，则两者之间的切比雪夫距离定义如下：

这也等于以下Lp度量的极值： 因此切比雪夫距离也称为L∞度量。

以数学的观点来看，切比雪夫距离是由一致范数（uniform norm）（或称为上确界范数）所衍生的度量，也是超凸度量（injective metric space）的一种。

在平面几何中，若二点p及q的直角坐标系坐标为 及 ，则切比雪夫距离为： 。

在国际象棋中，国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要的步数总是max(|x2-x1|,|y2-y1|)步。有一种类似的一种距离度量方法叫切比雪夫距离。

• 二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离：

• 两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的切比雪夫距离：

这个公式的另一种等价形式是

在闵可夫斯基距离中，最常用的是欧氏距离，它的主要优点是当坐标轴进行正交旋转时，欧氏距离是保持不变的。因此，如果对原坐标系进行平移和旋转变换，则变换后样本点间的距离和变换前完全相同。

值得注意的是，在采用闵可夫斯基距离时，一定要采用相同量纲的变量。如果变量的量纲不同，测量值变异范围相差悬殊时，建议首先进行数据的标准化处理，然后再计算距离。在采用闵可夫斯基距离时，还应尽可能地避免变量的多重相关性（multi-collinearity）。多重相关性所造成的信息重叠，会片面强调某些变量的重要性。

由于闵可夫斯基距离的这些缺点，一种改进的距离就是马氏距离。

 相关系数

由于习惯的原因，我们把两组样本近似线性的数据的距离称之为：相关系数。相关系数是衡量相似度的主要指标之一。

相关系数属于最重要的数据挖掘的概念之一。有两种重要的相关系数：夹角余弦（又称为：皮尔逊积矩相关系数）；杰卡德相似系数。其中夹角余弦是在LBS中应用最普遍的相关系数。

1.夹角余弦

在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式：

如果是对于两组样本数据来说，两组n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦

相类似，对于两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)，可以使用类似于夹角余弦的概念来衡量它们间的相似程度，即

夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。

如果将夹角余弦的概念再引申一下，引申到两组数据的回归直线的夹角的余弦，则得到了皮尔逊积矩相关系数（又称作PPMCC或PCC，一般简称为相关系数），用于度量两个变量X和Y之间的相关（线性相关）。在LBS中，该系数广泛用于度量两个变量之间的相关程度。如图1所示。

图1回归直线

回归直线： y=f(x)和 x=f(y)。其中：ax、bx与ay、by属于线性回归方程的系数。

相关系数是两组数据的中心化后的夹角的余弦值，即：等于两条回归线y=f(x) 和 x=f(y) 夹角的余弦值。

具体地说，相关系数等于两个变量之间的协方差和标准差的商：

相关距离的定义是：

以上方程定义了总体相关系数, 一般表示成希腊字母ρ(rho)。基于样本对协方差和方差进行估计时, 一般表示成r：

一种等价表达式的是表示成标准分的均值。基于(Xi, Yi)的样本点，样本皮尔逊系数是

其中 、 及 分别是标准分、样本平均值和样本标准差。

（1）相关系数的适用范围。

当两个变量的标准差都不为零时，相关系数才有定义，皮尔逊相关系数适用于：

1.两个变量之间是线性关系，都是连续数据。

2.两个变量的总体是正态分布，或接近正态的单峰分布。

3.两个变量的观测值是成对的，每对观测值之间相互独立。

（2）相关系数的应用。

比如：有5个国家的储蓄分别为 1, 2, 3, 5 和 8 亿元。 假设这5个国家的贫困百分比分别为 11%, 12%, 13%, 15%, 和18% 。

令 x 和 y 分别为包含上述5个数据的向量: x = (1, 2, 3, 5, 8) 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。

利用通常的方法计算两个向量之间的夹角, 未中心化的相关系数是:

将数据中心化 ，即：通过E(x) = 3.8移动 x 和通过 E(y) = 0.138 移动 y ，得到：

x = (−2.8, −1.8, −0.8, 1.2, 4.2) ；

y = (−0.028, −0.018, −0.008, 0.012, 0.042)。

从而：

推荐系统的设计

推荐引擎分以下两类。

第一类称为协同过滤，即基于相似用户的协同过滤推荐（尽最大可能发现用户间的相似度），以及基于相似物品的协同过滤推荐（尽最大可能发现物品间的相似度）。

第二类是基于内容分析的推荐（调查问卷、电子邮件，或者其他基于内容特征的分析）。

协同过滤

基于协同过滤的推荐在本质上仍是计算相关系数。在小规模实现时，考虑计算其相关系数；在大规模的实现时，考虑使用逻辑回归算法（这也是淘宝/亚马逊/非死book所采用的算法，本质上属于单层采用Sigmoid型激发函数的神经网络，训练数据时，输出可以是推荐的商品，输入最好是比商品更多的特征维度，比如十亿以上的维度）。

（1）协同过滤的种类

协同过滤可分为以下三个子类。

• 基于用户（user）的推荐：这种推荐是通过共同口味与偏好找相似邻居用户，常使用K-近邻算法。要达到的效果是：因为你的朋友喜欢，所以推测你可能也喜欢；
• 基于物品（item）的推荐：这种推荐是要发现物品之间的相似度，从而推荐类似的物品。要达到的效果是：因为你喜欢物品A，又因为C与A相似，所以推测你可能也喜欢C；
• 基于模型的推荐：这种推荐是要基于样本的用户喜好信息构造一个推荐模型，然后根据实时的用户喜好信息预测推荐。

（2）做协同过滤推荐应考虑的因素

上述几种推荐在使用时，要考虑以下因素。 精确度（Accuracy）：选择基于数量较少的因子来建立推荐算法；

• 效率（Efficiency）：效率；
• 稳定性（Stability）：选择基于变动频度较低的因子来建立推荐算法。例如，如果商品基本固定，用户不断变化，则选择基于item的算法；
• 说服力（Justifiability）：如果要考虑说服力，则优先选择基于item的算法，因为比较容易理解；例如，因为你喜欢三星Galaxy，所以给你推荐HTC One；

• 惊喜度（Serendipity）：如果要考虑惊喜度，则优先选择基于用户的推荐。

在工业界，通常采用的推荐算法如下：

• 多种算法融合+ 统一模型（Model）→划分等级（Ranking/Filtering）；
• 通过不同的输出来决定使用不同的算法。

（3）做协同过滤推荐的步骤

1）若要做协同过滤，那么收集用户偏好则是关键。可以通过用户的行为诸如评分（如不同的用户对不同的作品有不同的评分，而评分接近则意味着喜好口味相近，便可判定为相似用户）、投票、转发、保存、书签、标记、评论、点击流、页面停留时间、是否购买等获得。

2）收集用户行为数据之后，接下来便要对数据进行减噪与归一化操作（得到一个用户偏好的二维矩阵，一维是用户列表，另一维是物品列表，值是用户对物品的偏好，一般是 [0,1] 或者[1, 1]的浮点数值）。

3）计算相似用户或相似物品的相似度。

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

基于内容的推荐

所谓内容（Content），是指能够描述用户/物品的特征，比如：

对于物品来说，要考虑的内容特征有以下三项。

（1）电影

对电影来说，需要考虑的特征如下。

• 电影：红番区；
• 类型：动作/冒险；
• 演员：成龙；
• 年份：1997。

（2）文本

对文本来说，需要考虑的特征如下。

• 词性；
• 单词转化为向量（Word2vec）；
• 主题。

（3）多媒体

对多媒体来说，需要考虑的特征如下。

• Audio；
• 图片像素。

总的来说，对用户特征来说，要考虑的内容特征如图2所示。

图2  用户特征

将用户或物品的特征进行统一表示（例如表示成特征向量），即可利用相似度来进行等级（ranking）划分，从而推荐。

总的来说，协同过滤往往没有考虑用户或物品本身的特征，但能保证有一定的惊喜度。而基于内容的推荐能够充分应用物品（item）和用户自身的特征信息，且能够提供明确的推荐理由，但是容易推荐过于一致的结果。

综上所述，我们已经把推荐系统的数学基础和设计原理讲完了。为了读者能深入了解推荐系统的设计，我们可访问《 推荐系统的应用案例剖析 》一文，了解更多推荐系统应用案例。

作者简介

贾双成，阿里巴巴资深工程师，擅长于数据编译、数据挖掘的系统分析和架构设计，主持研发过多个高端车载导航及adas数据编译器。曾发表发明专利、论文四十余篇，著有《LBS核心技术揭秘》、《数据挖掘核心技术揭秘》。