相關度演算法

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種相關分析方法都已介紹完，每種方法各有特點。其中圖表方法最為直觀，相關系數方法可以看到變數間兩兩的相關性，回歸方程可以對相關關系進行提煉，並生成模型用於預測，互信息可以對文本類特徵間的相關關系進行度量。