相关度算法

A. 常见的相似度度量算法

本文目录：

  定义在两个向量（两个点）上：点x和点y的欧式距离为：

  常利用欧几里得距离描述相似度时，需要取倒数归一化，sim = 1.0/(1.0+distance)，利用numpy实现如下：

python实现欧式距离

  从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源， 曼哈顿距离也称为城市街区距离(City Block distance)。

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

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

   python实现曼哈顿距离：

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

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

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

   python实现切比雪夫距离：

  闵氏距离不是一种距离，而是一组距离的定义。

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

  其中p是一个变参数。

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

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

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

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

  闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。

  举个例子：二维样本(身高,体重)，其中身高范围是150 190，体重范围是50 60，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离，但是身高的10cm真的等价于体重的10kg么？因此用闵氏距离来衡量这些样本间的相似度很有问题。

  简单说来，闵氏距离的缺点主要有两个：

  (1)将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。

  (2)没有考虑各个分量的分布（期望，方差等)可能是不同的。

  标准欧氏距离的定义

  标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，好吧！那我先将各个分量都“标准化”到均值、方差相等吧。均值和方差标准化到多少呢？这里先复习点统计学知识吧，假设样本集X的均值(mean)为m，标准差(standard deviation)为s，那么X的“标准化变量”表示为：

  而且标准化变量的数学期望为0，方差为1。因此样本集的标准化过程(standardization)用公式描述就是：

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

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

  如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。

  有M个样本向量X1~Xm，协方差矩阵记为S，均值记为向量μ，则其中样本向量X到u的马氏距离表示为：

  而其中向量Xi与Xj之间的马氏距离定义为：

  若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：

  也就是欧氏距离了。

  若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。

  马氏距离的优缺点：量纲无关，排除变量之间的相关性的干扰。

  几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。

  在二维空间中向量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。

python实现余弦相似度：

  两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。

  应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。

python实现汉明距离：

  两个集合A和B的交集元素在A，B的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示。

  杰卡德相似系数是衡量两个集合的相似度一种指标。

  与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。杰卡德距离可用如下公式表示：

  杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

  可将杰卡德相似系数用在衡量样本的相似度上。

  样本A与样本B是两个n维向量，而且所有维度的取值都是0或1。例如：A(0111)和B(1011)。我们将样本看成是一个集合，1表示集合包含该元素，0表示集合不包含该元素。

  p ：样本A与B都是1的维度的个数

  q ：样本A是1，样本B是0的维度的个数

  r ：样本A是0，样本B是1的维度的个数

  s ：样本A与B都是0的维度的个数

  这里p+q+r可理解为A与B的并集的元素个数，而p是A与B的交集的元素个数。

  而样本A与B的杰卡德距离表示为：

  皮尔逊相关系数即为相关系数 ( Correlation coefficient )与相关距离(Correlation distance)

  相关系数的定义

  相关系数是衡量随机变量X与Y相关程度的一种方法，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明X与Y相关度越高。当X与Y线性相关时，相关系数取值为1（正线性相关）或-1（负线性相关）。

1. 机器学习中的相似性度量

2. 推荐算法入门（1）相似度计算方法大全

3. Python Numpy计算各类距离

4. 皮尔逊积矩相关系数

B. 5种相关分析方法

相关分析（Analysis of Correlation）是网站分析中经常使用的分析方法之一。通过对不同特征或数据间的关系进行分析，发现业务运营中的关键影响及驱动因素。并对业务的发展进行预测。本篇文章将介绍5种常用的分析方法。在开始介绍相关分析之前，需要特别说明的是相关关系不等于因果关系。

相关分析的方法很多，初级的方法可以快速发现数据之间的关系，如正相关，负相关或不相关。中级的方法可以对数据间关系的强弱进行度量，如完全相关，不完全相关等。高级的方法可以将数据间的关系转化为模型，并通过模型对未来的业务发展进行预测。下面我们以一组广告的成本数据和曝光量数据对每一种相关分析方法进行介绍。

以下是每日广告曝光量和费用成本的数据，每一行代表一天中的花费和获得的广告曝光数量。凭经验判断，这两组数据间应该存在联系，但仅通过这两组数据我们无法证明这种关系真实存在，也无法对这种关系的强度进行度量。因此我们希望通过相关分析来找出这两组数据之间的关系，并对这种关系进度度量。

1，图表相关分析（折线图及散点图）

第一种相关分析方法是将数据进行可视化处理，简单的说就是绘制图表。单纯从数据的角度很难发现其中的趋势和联系，而将数据点绘制成图表后趋势和联系就会变的清晰起来。对于有明显时间维度的数据，我们选择使用折线图。

为了更清晰的对比这两组数据的变化和趋势，我们使用双坐标轴折线图，其中主坐标轴用来绘制广告曝光量数据，次坐标轴用来绘制费用成本的数据。通过折线图可以发现，费用成本和广告曝光量两组数据的变化和趋势大致相同，从整体的大趋势来看，费用成本和广告曝光量两组数据都呈现增长趋势。从规律性来看费用成本和广告曝光量数据每次的最低点都出现在同一天。从细节来看，两组数据的短期趋势的变化也基本一致。

经过以上这些对比，我们可以说广告曝光量和费用成本之间有一些相关关系，但这种方法在整个分析过程和解释上过于复杂，如果换成复杂一点的数据或者相关度较低的数据就会出现很多问题。

比折线图更直观的是散点图。散点图去除了时间维度的影响，只关注广告曝光量和费用成本这里两组数据间的关系。在绘制散点图之前，我们将费用成本标识为X，也就是自变量，将广告曝光量标识为y，也就是因变量。下面是一张根据每一天中广告曝光量和费用成本数据绘制的散点图，X轴是自变量费用成本数据，Y轴是因变量广告曝光量数据。从数据点的分布情况可以发现，自变量x和因变量y有着相同的变化趋势，当费用成本的增加后，广告曝光量也随之增加。

折线图和散点图都清晰的表示了广告曝光量和费用成本两组数据间的相关关系，优点是对相关关系的展现清晰，缺点是无法对相关关系进行准确的度量，缺乏说服力。并且当数据超过两组时也无法完成各组数据间的相关分析。若要通过具体数字来度量两组或两组以上数据间的相关关系，需要使用第二种方法：协方差。

2，协方差及协方差矩阵

第二种相关分析方法是计算协方差。协方差用来衡量两个变量的总体误差，如果两个变量的变化趋势一致，协方差就是正值，说明两个变量正相关。如果两个变量的变化趋势相反，协方差就是负值，说明两个变量负相关。如果两个变量相互独立，那么协方差就是0，说明两个变量不相关。以下是协方差的计算公式：

下面是广告曝光量和费用成本间协方差的计算过程和结果，经过计算，我们得到了一个很大的正值，因此可以说明两组数据间是正相关的。广告曝光量随着费用成本的增长而增长。在实际工作中不需要按下面的方法来计算，可以通过Excel中COVAR()函数直接获得两组数据的协方差值。

协方差只能对两组数据进行相关性分析，当有两组以上数据时就需要使用协方差矩阵。下面是三组数据x，y，z，的协方差矩阵计算公式。

协方差通过数字衡量变量间的相关性，正值表示正相关，负值表示负相关。但无法对相关的密切程度进行度量。当我们面对多个变量时，无法通过协方差来说明那两组数据的相关性最高。要衡量和对比相关性的密切程度，就需要使用下一个方法：相关系数。,

3，相关系数

第三个相关分析方法是相关系数。相关系数(Correlation coefficient)是反应变量之间关系密切程度的统计指标，相关系数的取值区间在1到-1之间。1表示两个变量完全线性相关，-1表示两个变量完全负相关，0表示两个变量不相关。数据越趋近于0表示相关关系越弱。以下是相关系数的计算公式。

其中rxy表示样本相关系数，Sxy表示样本协方差，Sx表示X的样本标准差，Sy表示y的样本标准差。下面分别是Sxy协方差和Sx和Sy标准差的计算公式。由于是样本协方差和样本标准差，因此分母使用的是n-1。

Sxy样本协方差计算公式：

Sx样本标准差计算公式：

Sy样本标准差计算公式：

下面是计算相关系数的过程，在表中我们分别计算了x，y变量的协方差以及各自的标准差，并求得相关系数值为0.93。0.93大于0说明两个变量间正相关，同时0.93非常接近于1，说明两个变量间高度相关。

在实际工作中，不需要上面这么复杂的计算过程，在Excel的数据分析模块中选择相关系数功能，设置好x，y变量后可以自动求得相关系数的值。在下面的结果中可以看到，广告曝光量和费用成本的相关系数与我们手动求的结果一致。

相关系数的优点是可以通过数字对变量的关系进行度量，并且带有方向性，1表示正相关，-1表示负相关，可以对变量关系的强弱进行度量，越靠近0相关性越弱。缺点是无法利用这种关系对数据进行预测，简单的说就是没有对变量间的关系进行提炼和固化，形成模型。要利用变量间的关系进行预测，需要使用到下一种相关分析方法，回归分析。,

4，一元回归及多元回归

第四种相关分析方法是回归分析。回归分析（regression analysis)是确定两组或两组以上变量间关系的统计方法。回归分析按照变量的数量分为一元回归和多元回归。两个变量使用一元回归，两个以上变量使用多元回归。进行回归分析之前有两个准备工作，第一确定变量的数量。第二确定自变量和因变量。我们的数据中只包含广告曝光量和费用成本两个变量，因此使用一元回归。根据经验广告曝光量是随着费用成本的变化而改变的，因此将费用成本设置为自变量x，广告曝光量设置为因变量y。

以下是一元回归方程，其中y表示广告曝光量，x表示费用成本。b0为方程的截距，b1为斜率，同时也表示了两个变量间的关系。我们的目标就是b0和b1的值，知道了这两个值也就知道了变量间的关系。并且可以通过这个关系在已知成本费用的情况下预测广告曝光量。

这是b1的计算公式，我们通过已知的费用成本x和广告曝光量y来计算b1的值。

以下是通过最小二乘法计算b1值的具体计算过程和结果，经计算，b1的值为5.84。同时我们也获得了自变量和因变量的均值。通过这三个值可以计算出b0的值。

以下是b0的计算公式，在已知b1和自变量与因变量均值的情况下，b0的值很容易计算。

将自变量和因变量的均值以及斜率b1代入到公式中，求出一元回归方程截距b0的值为374。这里b1我们保留两位小数，取值5.84。

在实际的工作中不需要进行如此繁琐的计算，Excel可以帮我们自动完成并给出结果。在Excel中使用数据分析中的回归功能，输入自变量和因变量的范围后可以自动获得b0（Intercept）的值362.15和b1的值5.84。这里的b0和之前手动计算获得的值有一些差异，因为前面用于计算的b1值只保留了两位小数。

这里还要单独说明下R Square的值0.87。这个值叫做判定系数，用来度量回归方程的拟合优度。这个值越大，说明回归方程越有意义，自变量对因变量的解释度越高。

将截距b0和斜率b1代入到一元回归方程中就获得了自变量与因变量的关系。费用成本每增加1元，广告曝光量会增加379.84次。通过这个关系我们可以根据成本预测广告曝光量数据。也可以根据转化所需的广告曝光量来反推投入的费用成本。获得这个方程还有一个更简单的方法，就是在Excel中对自变量和因变量生成散点图，然后选择添加趋势线，在添加趋势线的菜单中选中显示公式和显示R平方值即可。

以上介绍的是两个变量的一元回归方法，如果有两个以上的变量使用Excel中的回归分析，选中相应的自变量和因变量范围即可。下面是多元回归方程。

5，信息熵及互信息

最后一种相关分析方法是信息熵与互信息。前面我们一直在围绕消费成本和广告曝光量两组数据展开分析。实际工作中影响最终效果的因素可能有很多，并且不一定都是数值形式。比如我们站在更高的维度来看之前的数据。广告曝光量只是一个过程指标，最终要分析和关注的是用户是否购买的状态。而影响这个结果的因素也不仅仅是消费成本或其他数值化指标。可能是一些特征值。例如用户所在的城市，用户的性别，年龄区间分布，以及是否第一次到访网站等等。这些都不能通过数字进行度量。

度量这些文本特征值之间相关关系的方法就是互信息。通过这种方法我们可以发现哪一类特征与最终的结果关系密切。下面是我们模拟的一些用户特征和数据。在这些数据中我们忽略之前的消费成本和广告曝光量数据，只关注特征与状态的关系。

对于信息熵和互信息具体的计算过程请参考我前面的文章《 决策树分类和预测算法的原理及实现 》，这里直接给出每个特征的互信息值以及排名结果。经过计算城市与购买状态的相关性最高，所在城市为北京的用户购买率较高。

到此为止5种相关分析方法都已介绍完，每种方法各有特点。其中图表方法最为直观，相关系数方法可以看到变量间两两的相关性，回归方程可以对相关关系进行提炼，并生成模型用于预测，互信息可以对文本类特征间的相关关系进行度量。