《統計學習方法》學習筆記(4)–k近鄰法及常用的距離(or 相似度)度量

《統計學習方法》學習筆記(4)–k近鄰法及常用的距離(or 相似度)度量

一、k近鄰法基礎知識
1. 特徵空間中兩個例項點的距離反應了兩個例項點的相似程度。
2. k近鄰模型三要素 = 距離度量(有不同的距離度量所確定的最鄰近點不同) k值的選擇(應用中,k值一般取一個比較小的值,通常採用交叉驗證法來確定最優k值) 分類決策規則(往往是多數表決規則(majority voting rule),此規則等價於經驗風險最小化)
3. 在訓練資料量太大或者是維數很高時,顯然線性掃描(linear scan)耗時太大,不可取。其中一個辦法就是構建kd樹(空間劃分樹,實際上是一種平衡二叉樹)實現對訓練資料的快速k近鄰搜尋。
二、距離度量相關

Note:根據資料特性的不同,可以採用不同的度量方法。一般而言,定義一個距離函式 d(x,y), 需要滿足下面幾個準則:
1) d(x,x) = 0 // 到自己的距離為0
2) d(x,y) >= 0 // 距離非負
3) d(x,y) = d(y,x) // 對稱性: 如果 A 到 B 距離是 a,那麼 B 到 A 的距離也應該是 a
4) d(x,k) d(k,y) >= d(x,y) // 三角形法則: (兩邊之和大於第三邊)

  1. 閔可夫斯基距離(Minkowski Distance)又稱Lp距離,閔氏距離不是一種距離,而是一組距離的定義。
    兩個n維變數a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的閔可夫斯基距離定義為:
    這裡寫圖片描述
    其中p是一個變引數,根據變引數的不同,閔氏距離可以表示一類的距離。
    當p=1時,就是曼哈頓距離,又稱L1距離或者是程式區塊距離(city block distance)等。
    當p=2時,就是歐氏距離,又稱L2距離,是直線距離。
    當p→∞時,就是切比雪夫距離
    這裡寫圖片描述
    閔氏距離,包括曼哈頓距離、歐氏距離和切比雪夫距離都存在明顯的缺點。
      舉個例子:二維樣本(身高,體重),其中身高範圍是150~190,體重範圍是50~60,有三個樣本:a(180,50),b(190,50),c(180,60)。那麼a與b之間的閔氏距離(無論是曼哈頓距離、歐氏距離或切比雪夫距離)等於a與c之間的閔氏距離,但是身高的10cm真的等價於體重的10kg麼?因此用閔氏距離來衡量這些樣本間的相似度很有問題。
    簡單說來,閔氏距離的缺點主要有兩個:(1)將各個分量的量綱(scale),也就是“單位”當作相同的看待了。(2)沒有考慮各個分量的分佈(期望,方差等)可能是不同的。
  2. 歐式距離
    兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的歐氏距離:
    這裡寫圖片描述
      也可以用表示成向量運算的形式:
    這裡寫圖片描述
  3. 標準化歐氏距離(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)間的標準化歐氏距離的公式:  
    這裡寫圖片描述
    如果將方差的倒數看成是一個權重,這個公式可以看成是一種加權歐氏距離(Weighted Euclidean distance)。
  4. 夾角餘弦(Cosine) ,幾何中夾角餘弦可用來衡量兩個向量方向的差異,機器學習中借用這一概念來衡量樣本向量之間的差異。
    (1)在二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角餘弦公式:
    這裡寫圖片描述
    (2) 兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夾角餘弦
    類似的,對於兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n),可以使用類似於夾角餘弦的概念來衡量它們間的相似程度。  
    這裡寫圖片描述
    即:
    這裡寫圖片描述
    夾角餘弦取值範圍為[-1,1]。夾角餘弦越大表示兩個向量的夾角越小,夾角餘弦越小表示兩向量的夾角越大。當兩個向量的方向重合時夾角餘弦取最大值1,當兩個向量的方向完全相反夾角餘弦取最小值-1。
    舉一個具體的例子,假如新聞X和新聞Y對應向量分別是: x1, x2, …, x6400 和 y1, y2, …, y6400。則,它們之間的餘弦距離可以用它們之間夾角的餘弦值來表示:
    這裡寫圖片描述
    當兩條新聞向量夾角餘弦等於1時,這兩條新聞完全重複(用這個辦法可以刪除爬蟲所收集網頁中的重複網頁);當夾角的餘弦值接近於1時,兩條新聞相似(可以用作文字分類);夾角的餘弦越小,兩條新聞越不相關。
  5. 餘弦距離與歐式距離對比

    餘弦距離使用兩個向量夾角的餘弦值作為衡量兩個個體間差異的大小。
    相比歐氏距離,餘弦距離更加註重兩個向量在方向上的差異。

    藉助三維座標系來看下歐氏距離和餘弦距離的區別:
    這裡寫圖片描述
    從上圖可以看出,歐氏距離衡量的是空間各點的絕對距離,跟各個點所在的位置座標直接相關;而餘弦距離衡量的是空間向量的夾角,更加體現在方向上的差異,而不是位置。

    如果保持A點位置不變,B點朝原方向遠離座標軸原點,那麼這個時候餘弦距離cosθ是保持不變的(因為夾角沒有發生變化),而A、B兩點的距離顯然在發生改變,這就是歐氏距離和餘弦距離之間的不同之處。
    歐氏距離和餘弦距離各自有不同的計算方式和衡量特徵,因此它們適用於不同的資料分析模型:
    歐氏距離能夠體現個體數值特徵的絕對差異,所以更多的用於需要從維度的數值大小中體現差異的分析,如使用使用者行為指標分析使用者價值的相似度或差異。
    餘弦距離更多的是從方向上區分差異,而對絕對的數值不敏感,更多的用於使用使用者對內容評分來區分興趣的相似度和差異,同時修正了使用者間可能存在的度量標準不統一的問題(因為餘弦距離對絕對數值不敏感)。

  6. 調整餘弦相似度演算法(Adjusted Cosine Similarity)
    餘弦相似度更多的是從方向上區分差異,而對絕對的數值不敏感,因此沒法衡量每個維度上數值的差異,會導致這樣一種情況:
    使用者對內容評分,按5分制,X和Y兩個使用者對兩個內容的評分分別為(1,2)和(4,5),使用餘弦相似度得到的結果是0.98,兩者極為相似。但從評分上看X似乎不喜歡2這個 內容,而Y則比較喜歡,餘弦相似度對數值的不敏感導致了結果的誤差,需要修正這種不合理性就出現了調整餘弦相似度,即所有維度上的數值都減去一個均值,比如X和Y的評分均值都是3,那麼調整後為(-2,-1)和(1,2),再用餘弦相似度計算,得到-0.8,相似度為負值並且差異不小,但顯然更加符合現實。

  7. 傑卡德相似係數(Jaccard similarity coefficient)
    廣義Jaccard相似度可參考,此處略:http://blog.csdn.net/xceman1997/article/details/8600277
    1) 傑卡德相似係數
    兩個集合A和B的交集元素在A,B的並集中所佔的比例,稱為兩個集合的傑卡德相似係數,用符號J(A,B)表示。 
    這裡寫圖片描述
    傑卡德相似係數是衡量兩個集合的相似度一種指標。
    2)傑卡德距離
    與傑卡德相似係數相反的概念是傑卡德距離(Jaccard distance)。
    傑卡德距離可用如下公式表示:  
    這裡寫圖片描述
    傑卡德距離用兩個集合中不同元素佔所有元素的比例來衡量兩個集合的區分度。
    3) 傑卡德相似係數與傑卡德距離的應用
    可將傑卡德相似係數用在衡量樣本的相似度上。
    樣本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的維度的個數
    那麼樣本A與B的傑卡德相似係數可以表示為:這裡p q r可理解為A與B的並集的元素個數,而p是A與B的交集的元素個數。而樣本A與B的傑卡德距離表示為:
    這裡寫圖片描述
    這裡p q r可理解為A與B的並集的元素個數,而p是A與B的交集的元素個數。
    4)傑卡德相似度演算法分析
    傑卡德相似度演算法沒有考慮向量中潛在數值的大小,而是簡單的處理為0和1,不過,做了這樣的處理之後,傑卡德方法的計算效率肯定是比較高的,畢竟只需要做集合操作。

參考:
餘弦距離、歐氏距離和傑卡德相似性度量的對比分http://www.cnblogs.com/chaosimple/archive/2013/06/28/3160839.html
不同相關性度量方法的線上效果對比與分析 http://blog.sina.com.cn/s/blog_4b59de07010166z9.html
從K近鄰演算法、距離度量談到KD樹、SIFT BBF演算法http://blog.csdn.net/v_july_v/article/details/8203674
機器學習中的相似性度量http://www.cnblogs.com/heaad/archive/2011/03/08/1977733.html
漫談:機器學習中距離和相似性度量方法http://www.cnblogs.com/daniel-D/p/3244718.html