月度归档:2011 年十月

基于KNN的相关内容推荐

  如果做网站的内容运营,相关内容推荐可以帮助用户更快地寻找和发现感兴趣的信息,从而提升网站内容浏览的流畅性,进而提升网站的价值转化。相关内容推荐最常见的两块就是“关联推荐”和“相关内容推荐”,关联推荐就是我们常说的购物篮分析,即使用购买了某商品的用户同时购买了什么这个规则来发现商品间的潜在联系,之前有相关的文章介绍——向上营销、交叉营销与关联推荐;关联推荐是基于用户行为分析的推荐,而相关内容推荐是基于内容固有特征的推荐,只与内容本身有关,与用户的行为完全无关,所以相关内容推荐的模型是一种“冷启动”的算法,不需要任何历史浏览访问数据的支持。

内容固有属性

  相关内容推荐因为完全不借助用户浏览行为的数据,所以底层数据不依赖于网站的点击流日志,唯一的基础数据就是内容的固有属性及完整信息。我们以豆瓣网的几大块内容为例来看看对于这些内容一般包含哪些固有属性:

书籍 书名、作者、出版时间、出版社、分类、标签
音乐 专辑名、歌手、发行时间、发行方、风格流派、标签
电影 电影名称、导演、演员、上映时间、制片方、类型、标签

  豆瓣很多地方都使用了“标签”这个词,用贴标签的形式来完成内容的分类和标识,但其实标签又分为很多种,有些标签是在内容生成时就被贴上的,有些可能是后续用户贴上去的,而且豆瓣一般为内容和标签定义了原始分类,如书籍分为文学、流行、文化……既然分类和标签内容源生就带有,那同样可以作为内容的固有属性。

  还需要说明的是,这里不涉及文本挖掘和字符切分模糊匹配等问题,因此内容的标题、简介和全文不参与文本相似度的分析,虽然这些可能在构建完整的相关内容模型中不可缺少,但这里只考虑一些固有属性是否相同实现简单应用。基于上述豆瓣几类内容的属性特征,选择和整理适合分析的内容属性如下:

attributes-of-content

  “作者”就是指内容的创造者,“来源”指内容的发布方或获取渠道,“分类”为内容归属的类别,“标签”可以包含对内容的各类描述信息和关键词等。这里为了能够尽可能清晰地描述整个分析模型和思路只选取了大部分内容都包含的一些属性,如果要构建更加高效的相关内容分析模型,需要更完整的内容属性,可以根据自身内容的特征进行属性的定义和选取。

KNN算法及应用

  KNN(K-Nearest Neighbor algorithm),K最近邻算法,通过计算样本个体间的距离或者相似度寻找与每个样本个体最相近的K个个体,算法的时间复杂度跟样本的个数直接相关,需要完成一次两两比较的过程。KNN一般被用于分类算法,在给定分类规则的训练集的基础上对总体的样本进行分类,是一种监督学习(Supervised learning)方法。

KNN

  这里我们不用KNN来实现分类,我们使用KNN最原始的算法思路,即为每个内容寻找K个与其最相似的内容,并推荐给用户。相当于每个内容之间都会完成一次两两比较的过程,如果你的网站有n个内容,那么算法的时间复杂度为Cn2,即n(n-1)/2。但是用内容固有属性有一个好处就是因为固有属性一旦创建后基本保持不变,因此算法输出的数据一旦计算好之后不需要重复计算去刷新,也就是对于网站内容而言,原有内容的数据在首次初始化之后可以不断重复使用,只要更新新增内容的数据就可以,数据的统计计算可以使用增量更新的形式,这样可以有效地减少服务器的计算压力。

相关内容模型

  有了基础数据和算法的支持,我们就可以创建数据模型了。先看下基础数据的类型,作者、分类、来源和标签都是字符型,其中作者、分类、来源基本可以当做是单个值的属性,标签一般包含多个值。首先由于都是字符可以确定属性之间相似性的判定只能通过“是否相同”,无法体现数值上的差异,所以对于作者、分类、来源这几个单值属性而言,比较的结果就是一个布尔型的度量,相同或者不相同;对于标签这个多值属性可以考虑使用Jaccard相关系数,但因为每个内容标签的个数存在较大差异,使用验证后的结果并不理想,所以不考虑使用(当然,如果内容的标签个数比较固定,Jaccard相关系数是有效的)。因此,直接创建加权相似度模型如下,首先是标签的相似度分值设定:

相同标签数 图书比例 相似度分值
0 70% 0
1 20% 1
2 6% 2
3 3% 4
>=4 1% 5

  再结合作者、分类和来源,通过加权设定总体的相似度分值:

属性 相同时分值 不同时分值 权重 加权分值分布
作者 1 0 25 [0,25]
分类 1 0 10 [0,10]
来源 1 0 15 [0,15]
标签 [1,5] 0 10 [0,50]

  将所有属性加权相似度分值的结果相加应该分布在[0,100],分值越高说明内容间的相似度越高。对于这种简单的加权相似度评分模型,估计又有很多人要问权重是怎么确定的,确实,这里的权重并没有通过任何定量分析模型的方法去计算,只是简单的经验估计,但估计的过程经过反复地调整和优化,也就是不断地尝试调整各属性的权重系数并输出结果,抽样检验结果是否符合预期、是否有提升优化的空间。

  基于上述内容间相似度的计算结果,套用KNN的原理实现相关内容推荐就异常简单了,只要根据每个内容与之比较的所有内容的相似度分值降序排列取前K个内容作为该内容的最相关内容推荐给用户就可以了。当然中间可能会涉及相同相似度分值的内容如何排序的问题(因为模型的关系分值分布可能不会很离散),建议如果相似度分值相同使用随机排序,以保证推荐结果有一定的变化,均匀内容的曝光。

  好了,所有的分析流程介绍完了,好像跟前一篇的距离和相似度度量完全没有关系,其实距离和相似度度量是KNN的基础算法,因为KNN的个体相似度或邻近的距离都会选择距离度量和相似度度量中的某种方法进行计算,但这里考虑到了现实的数据情况和应用环境,并不是KNN就一定要硬套欧氏距离,其实换一种简单的方法可能反而更加适合整个模型,而且模型的最终效果可能会更理想。所以一切的数据挖掘算法的选择和使用都是基于数据模型的有效性和输出结果的效果来决定的,并不是简单的算法效果就一定不好,而高级复杂的算法一定更加有效。对了,如果你已经做了相关内容推荐,那么优化相关内容推荐这篇文章里面介绍的一些方法将是检验推荐效果的一个很好的参考。

距离和相似度度量

  在数据分析和数据挖掘的过程中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如K最近邻(KNN)和K均值(K-Means)。当然衡量个体差异的方法有很多,最近查阅了相关的资料,这里整理罗列下。

  为了方便下面的解释和举例,先设定我们要比较X个体和Y个体间的差异,它们都包含了N个维的特征,即X=(x1, x2, x3, … xn),Y=(y1, y2, y3, … yn)。下面来看看主要可以用哪些方法来衡量两者的差异,主要分为距离度量和相似度度量。

距离度量

  距离度量(Distance)用于衡量个体在空间上存在的距离,距离越远说明个体间的差异越大。

欧几里得距离(Euclidean Distance)

  欧氏距离是最常见的距离度量,衡量的是多维空间中各个点之间的绝对距离。公式如下:

Euclidean Distance

  因为计算是基于各维度特征的绝对数值,所以欧氏度量需要保证各维度指标在相同的刻度级别,比如对身高(cm)和体重(kg)两个单位不同的指标使用欧式距离可能使结果失效。

明可夫斯基距离(Minkowski Distance)

  明氏距离是欧氏距离的推广,是对多个距离度量公式的概括性的表述。公式如下:

Minkowski Distance

  这里的p值是一个变量,当p=2的时候就得到了上面的欧氏距离。

曼哈顿距离(Manhattan Distance)

  曼哈顿距离来源于城市区块距离,是将多个维度上的距离进行求和后的结果,即当上面的明氏距离中p=1时得到的距离度量公式,如下:

Manhattan Distance

切比雪夫距离(Chebyshev Distance)

  切比雪夫距离起源于国际象棋中国王的走法,我们知道国际象棋国王每次只能往周围的8格中走一步,那么如果要从棋盘中A格(x1, y1)走到B格(x2, y2)最少需要走几步?扩展到多维空间,其实切比雪夫距离就是当p趋向于无穷大时的明氏距离:

Chebyshev Distance

  其实上面的曼哈顿距离、欧氏距离和切比雪夫距离都是明可夫斯基距离在特殊条件下的应用。

马哈拉诺比斯距离(Mahalanobis Distance)

  既然欧几里得距离无法忽略指标度量的差异,所以在使用欧氏距离之前需要对底层指标进行数据的标准化,而基于各指标维度进行标准化后再使用欧氏距离就衍生出来另外一个距离度量——马哈拉诺比斯距离(Mahalanobis Distance),简称马氏距离。

相似度度量

  相似度度量(Similarity),即计算个体间的相似程度,与距离度量相反,相似度度量的值越小,说明个体间相似度越小,差异越大。

向量空间余弦相似度(Cosine Similarity)

  余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量,余弦相似度更加注重两个向量在方向上的差异,而非距离或长度上。公式如下:

Cosine Similarity

皮尔森相关系数(Pearson Correlation Coefficient)

  即相关分析中的相关系数r,分别对X和Y基于自身总体标准化后计算空间向量的余弦夹角。公式如下:

Pearson Correlation Coefficient

Jaccard相似系数(Jaccard Coefficient)

  Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度,因为个体的特征属性都是由符号度量或者布尔值标识,因此无法衡量差异具体值的大小,只能获得“是否相同”这个结果,所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比较X与Y的Jaccard相似系数,只比较xn和yn中相同的个数,公式如下:

Jaccard Coefficient

调整余弦相似度(Adjusted Cosine Similarity)

  虽然余弦相似度对个体间存在的偏见可以进行一定的修正,但是因为只能分辨个体在维之间的差异,没法衡量每个维数值的差异,会导致这样一个情况:比如用户对内容评分,5分制,X和Y两个用户对两个内容的评分分别为(1,2)和(4,5),使用余弦相似度得出的结果是0.98,两者极为相似,但从评分上看X似乎不喜欢这2个内容,而Y比较喜欢,余弦相似度对数值的不敏感导致了结果的误差,需要修正这种不合理性,就出现了调整余弦相似度,即所有维度上的数值都减去一个均值,比如X和Y的评分均值都是3,那么调整后为(-2,-1)和(1,2),再用余弦相似度计算,得到-0.8,相似度为负值并且差异不小,但显然更加符合现实。

欧氏距离与余弦相似度

  欧氏距离是最常见的距离度量,而余弦相似度则是最常见的相似度度量,很多的距离度量和相似度度量都是基于这两者的变形和衍生,所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。

  借助三维坐标系来看下欧氏距离和余弦相似度的区别:

distance and similarity

  从图上可以看出距离度量衡量的是空间各点间的绝对距离,跟各个点所在的位置坐标(即个体特征维度的数值)直接相关;而余弦相似度衡量的是空间向量的夹角,更加的是体现在方向上的差异,而不是位置。如果保持A点的位置不变,B点朝原方向远离坐标轴原点,那么这个时候余弦相似度cosθ是保持不变的,因为夹角不变,而A、B两点的距离显然在发生改变,这就是欧氏距离和余弦相似度的不同之处。

  根据欧氏距离和余弦相似度各自的计算方式和衡量特征,分别适用于不同的数据分析模型:欧氏距离能够体现个体数值特征的绝对差异,所以更多的用于需要从维度的数值大小中体现差异的分析,如使用用户行为指标分析用户价值的相似度或差异;而余弦相似度更多的是从方向上区分差异,而对绝对的数值不敏感,更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异,同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。

  上面都是对距离度量和相似度度量的一些整理和汇总,在现实的使用中选择合适的距离度量或相似度度量可以完成很多的数据分析和数据挖掘的建模,后续会有相关的介绍。