空間、距離和相似度

文章目錄

• • 空間
  • 相似度度量
  • • 距離度量
    • • 闵可夫斯基距離
      • 歐幾裡得距離
      • 歐幾裡得标準距離
      • 曼哈頓距離
      • 切比雪夫距離
      • 馬氏距離
      • 漢明距離(分類樣本點之間的距離)
      • 編輯距離(DP求解)
    • 相似系數
    • • 餘弦相似度
      • 皮爾遜相關系數(相關系數)
      • 傑卡德相似系數
    • 機率分布相似度
    • • 相對熵(KL散度)
      • • 資訊熵、交叉熵、相對熵(KL散度)
        • • 熵
          • 資訊熵
          • 交叉熵
          • 相對熵(KL散度)
        • 聯合資訊熵、條件資訊熵、互資訊（資訊增益）
        • • 聯合資訊熵
          • 條件資訊熵
          • 互資訊(資訊增益)
      • 卡方檢驗

空間

• 距離空間/度量空間：定義兩個點之間的距離【未定義點的長度，因為沒有零點】
• 賦範空間：定義了範數的空間【範數定義距離+長度；範數空間一定是距離空間】
• 線性空間：定義了加法和數乘的空間【當知道空間所有基，便可以用加法和數乘表示該空間的所有元素】
• 線性賦範空間：賦範空間+線性結構
• 線性度量空間：線性結構+距離空間/度量空間
• 内積空間=線性賦範空間+内積：定義了内積計算的空間（投影）【内積在範數基礎上定義了角度；内積空間一定為賦範空間】
• 歐幾裡得空間=内積空間+有限維
• 希爾伯特空間=内積空間+完備性【完備性：空間中的元素求極限之後仍在空間裡】
• 巴拿赫空間=賦範空間+完備性
• 拓撲：弱化距離的定義，但仍然保留極限和連續的機率

相似度度量

距離度量

闵可夫斯基距離

• 公式

  P = ( x 1 , x 2 , . . . . . . x n ) , Q = ( y 1 , y 2 , . . . . . . y n ) P ∈ R n , Q ∈ R n P=(x_1,x_2,......x_n), Q=(y_1,y_2,......y_n) \quad P\isin \mathbb{R^n} , Q\isin \mathbb{R^n} P=(x1​,x2​,......xn​),Q=(y1​,y2​,......yn​)P∈Rn,Q∈Rn

  d i s t a n c e ( P , Q ) = ( ∑ i = 1 n ∣ x i − y i ∣ p ) 1 p distance(P,Q)=(\sum_{i=1}^{n}|x_i-y_i|^p)^{\frac{1}{p}} distance(P,Q)=(i=1∑n​∣xi​−yi​∣p)p1​

• 優點：直覺
• 缺點：與資料的分布無關，具有一定的局限性
  • 如，x方向上的幅值遠大于y，會過于放大x次元的作用
    • 解決：（1）資料各個次元 x 1 , x 2 , . . . . . . x n x_1,x_2,......x_n x1​,x2​,......xn​不相關，但幅度相差大，采用z-transform，即減均值除方差
    • （2）資料次元互相之間相關(如身高體重)，用馬氏距離

歐幾裡得距離

闵可夫斯基距離中的 p = 2 p=2 p=2，定義在歐幾裡得空間裡。

d i s t a n c e ( P , Q ) = ( ∑ i = 1 n ∣ x i − y i ∣ 2 ) 1 2 = ∑ i = 1 n ( x i − y i ) 2 distance(P,Q)=(\sum_{i=1}^{n}|x_i-y_i|^2)^{\frac{1}{2}}=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2} distance(P,Q)=(i=1∑n​∣xi​−yi​∣2)21​=i=1∑n​(xi​−yi​)2

​

歐幾裡得标準距離

• 去掉歐幾裡得距離裡量綱影響

• 權重歐式距離

  d i s t a n c e ( P , Q ) = ∑ i = 1 n ( x i − y i s i ) 2 distance(P,Q)=\sqrt{\sum_{i=1}^{n}(\frac{x_i-y_i}{s_i})^2} distance(P,Q)=i=1∑n​(si​xi​−yi​​)2

  ​

曼哈頓距離

闵可夫斯基距離中的 p = 1 p=1 p=1，又稱 L 1 − L_1- L1​−距離/街道距離。

d i s t a n c e ( P , Q ) = ∑ i = 1 n ∣ x i − y i ∣ distance(P,Q)= \sum_{i=1}^{n}|x_i-y_i| distance(P,Q)=i=1∑n​∣xi​−yi​∣

切比雪夫距離

闵可夫斯基距離中的 p = ∞ p=\infty p=∞，國王走一步能夠移動到相鄰的8個方格中的任意一個。那麼國王從格子 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​)走到格子 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​)最少需要多少步

d i s t a n c e ( P , Q ) = max ⁡ i = 1 n ∣ x i − y i ∣ distance(P,Q)=\max_{i=1}^n|x_i-y_i| distance(P,Q)=i=1maxn​∣xi​−yi​∣

馬氏距離

• 原理：利用cholesky分解原理消除次元之間的相關性和尺度不同的性質。假設樣本點(列向量)之間的協方差矩陣為 ∑ \sum ∑ ,通過cholesky分解(因為協方差矩陣對稱且正定)可以得到 ∑ = L L T \sum=LL^T ∑=LLT。
• 通過對單個樣本點做如下處理： z = L − 1 ( x − u ) z=L^{-1}(x-u) z=L−1(x−u)，處理之後的歐幾裡得距離就是原樣本的馬氏距離。

• 假設有m個樣本，記為 x 1 , x 2 , . . . x m x_1,x_2,...x_m x1​,x2​,...xm​，協方差記為 ∑ \sum ∑ (對稱正定)，均值向量記為 u u u，則樣本x到u的馬氏距離的平方為：

  ( d i s t a n c e ( P , Q ) ) 2 = z T z = ( L − 1 ( x − u ) ) T ( L − 1 ( x − u ) ) = ( x − u ) T ( L L T ) − 1 ( x − u ) = ( x − u ) T ∑ − 1 ( x − u ) (distance(P,Q))^2=z^Tz=(L^{-1}(x-u))^T(L^{-1}(x-u))=(x-u)^T(LL^T)^{-1}(x-u)=(x-u)^T{\sum}^{-1}(x-u) (distance(P,Q))2=zTz=(L−1(x−u))T(L−1(x−u))=(x−u)T(LLT)−1(x−u)=(x−u)T∑−1(x−u)

• 樣本 x i x_i xi​和樣本 x j x_j xj​的距離為：

  ( d i s t a n c e ( x i , x j ) ) 2 = ( x i − x j ) T ∑ − 1 ( x i − x j ) (distance(x_i,x_j))^2=(x_i-x_j)^T{\sum}^{-1}(x_i-x_j) (distance(xi​,xj​))2=(xi​−xj​)T∑−1(xi​−xj​)

• 若協方差矩陣為機關陣【歐式距離】

  ( d i s t a n c e ( x i , x j ) ) 2 = ( x i − x j ) T ( x i − x j ) (distance(x_i,x_j))^2=(x_i-x_j)^T(x_i-x_j) (distance(xi​,xj​))2=(xi​−xj​)T(xi​−xj​)

• 若協方差矩陣為對角陣【标準歐式距離】
• 優點：排除量綱和變量相關性的幹擾

漢明距離(分類樣本點之間的距離)

• 兩個等長字元串s1與s2之間的漢明距離定義為将其中一個變為另外一個所需要作的最小替換次數。衡量字元串的相似度。
• 應用：資訊編碼（為了增強容錯性，應使得編碼間的最小漢明距離盡可能大)

編輯距離(DP求解)

• 編輯距離是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。許可的編輯操作包括将一個字元替換成另一個字元，插入一個字元，删除一個字元。編輯距離求的是最少編輯次數。

相似系數

餘弦相似度

• 幾何中夾角餘弦可用來衡量兩個向量方向(夾角)的差異，機器學習中借用這一概念來衡量樣本向量之間的差異，與向量的幅值無關，隻與向量方向相關。

• 兩樣本 x = ( x 1 , x 2 , . . . . . . x n ) , y = ( y 1 , y 2 , . . . . . . y n ) x ∈ R n , y ∈ R n x=(x_1,x_2,......x_n), y=(y_1,y_2,......y_n) \quad x\isin \mathbb{R^n} ,y\isin \mathbb{R^n} x=(x1​,x2​,......xn​),y=(y1​,y2​,......yn​)x∈Rn,y∈Rn的餘弦相似度為

  C o s S i m ( x , y ) = ∑ i x i y i ∑ i ( x i ) 2 ∑ i ( y i ) 2 = x T y ∣ ∣ x ∣ ∣ ∣ ∣ y ∣ ∣ CosSim(x,y)=\frac{\sum_ix_iy_i}{\sqrt{\sum_i(x_i)^2}\sqrt{\sum_i(y_i)^2}}=\frac{x^Ty}{||x||||y||} CosSim(x,y)=∑i​(xi​)2

  ​∑i​(yi​)2

  ​∑i​xi​yi​​=∣∣x∣∣∣∣y∣∣xTy​

• 應用：文檔相似度(TF-IDF)和圖檔相似度(histogram)，詞向量計算詞語相似度
• 受到向量平移的影響，如将x平移到x+1

皮爾遜相關系數(相關系數)

• 皮爾遜相關系數具有平移不變性和尺度不變性質，度量兩個向量（次元）的相關性。

• 對于兩個樣本 x , y x,y x,y而言，則度量了樣本點分布的相關性。

  C o r r ( x , y ) = ∑ i ( x i − x ˉ ) ( y i − y ˉ ) ∑ i ( x i − x ˉ ) 2 ∑ i ( y i − y ˉ ) 2 = < x − x ˉ , y − y ˉ > ∣ ∣ x − x ˉ ∣ ∣ ∣ ∣ y i − y ˉ ∣ ∣ = C o s S i m ( x − x ˉ ) ( y − y ˉ ) Corr(x,y)=\frac{\sum_i(x_i-\bar x)(y_i-\bar y)}{\sqrt{\sum_i(x_i-\bar x)^2}\sqrt{\sum_i(y_i-\bar y)^2}}=\frac{<x-\bar x, y-\bar y>}{||x-\bar x||||y_i-\bar y||}=CosSim(x-\bar x)(y-\bar y) Corr(x,y)=∑i​(xi​−xˉ)2

  ​∑i​(yi​−yˉ​)2

  ​∑i​(xi​−xˉ)(yi​−yˉ​)​=∣∣x−xˉ∣∣∣∣yi​−yˉ​∣∣<x−xˉ,y−yˉ​>​=CosSim(x−xˉ)(y−yˉ​)

• 适用範圍：(1)兩個變量之間是線性關系，且連續；(2)兩個變量的總體是正态分布，或接近正态的單峰分布;(3)兩個變量的觀測值是成對的，每對觀測值之間互相獨立。
• 應用：推薦系統中根據為某一使用者查找喜好相似的使用者，進而推薦。優點：可以不受每個使用者評分标準和觀看數量不一樣的影響。

傑卡德相似系數

• 在一些情況下，某些特定的值相等并不能代表什麼(對比漢明距離)。比如，用 1 表示使用者看過該電影，用 0 表示使用者沒有看過，那麼使用者看電影的的資訊就可用 0,1 表示成一個序列。電影基數非常龐大，使用者看過的電影隻占其中非常小的一部分，如果兩個使用者都沒有看過某一部電影（兩個都是 0），并不能說明兩者相似。如果兩個使用者都看過某一部電影（序列中都是 1），則說明使用者有很大的相似度。在這個例子中，序列中等于 1 所占的權重應該遠遠大于 0 的權重，這就引出下面要說的傑卡德相似系數。

• 傑卡德相似度用于衡量兩個集合A,B的相似度

  J ( A , B ) = A ∪ B A ∩ B J(A,B)=\frac{A \cup B}{A\cap B} J(A,B)=A∩BA∪B​

• 應用：

  • 推薦系統中用 M11 表示兩個使用者都看過的電影數目，M10 表示使用者 A 看過，使用者 B 沒看過的電影數目，M01 表示使用者 A 沒看過，使用者 B 看過的電影數目，M00 表示兩個使用者都沒有看過的電影數目。Jaccard 相似性系數可以表示為：

    J ( A , B ) = M 11 M 11 + M 10 + M 01 J(A,B) = \frac{M11}{M11+M10+M01} J(A,B)=M11+M10+M01M11​

  • 分類資料點的距離。如果分類數值點是用樹形結構來表示的，它們的相似性可以用相同路徑的長度來表示，比如，“/product/spot/ballgame/basketball” 離“product/spot/ballgame/soccer/shoes” 的距離小于到 “/product/luxury/handbags” 的距離，以為前者相同父節點路徑更長。

機率分布相似度

相對熵(KL散度)

資訊熵、交叉熵、相對熵(KL散度)

熵

• 衡量無序性，越無序，熵越大

資訊熵

• 自資訊:事件$ {X=x} $所攜帶的資訊量，與頻率成反比，獨立可加。

  I ( X = x ) = − l o g ( p ( x ) ) I(X=x)=-log(p(x)) I(X=x)=−log(p(x))

• 香農熵(資訊熵):事件自資訊隻是處理單個輸出，用香農熵(Shannon entropy)來衡量整個機率分布P的不确定性總量進行量化,，一個分布的香農熵是指遵循這個分布的事件所産生的期望資訊總量(衡量分布所攜帶的資訊量):

  H ( Q ) = − E x ∼ P [ l o g Q ( x ) ] = − ∑ i q ( x ) l o g ( q ( x ) ) H(Q)=-E_{x\sim P}[logQ(x)]=-\sum_iq(x)log(q(x)) H(Q)=−Ex∼P​[logQ(x)]=−i∑​q(x)log(q(x))

交叉熵

• 交叉熵：用猜測的分布P描述真實分布Q時的資訊量

  H P ( Q ) = − ∑ i q ( x ) l o g ( p ( x ) ) H_P(Q)=-\sum_iq(x)log(p(x)) HP​(Q)=−i∑​q(x)log(p(x))

相對熵(KL散度)

• KL散度衡量兩個分布的距離,KL(P||Q)衡量分布P和分布Q的不同。KL（P||Q)散度也是用P衡量Q時的相對熵

  K L ( P ∣ ∣ Q ) = H P Q − H ( Q ) KL(P||Q)=H_PQ-H(Q) KL(P∣∣Q)=HP​Q−H(Q)

  K L ( P ∣ ∣ Q ) = H P Q − H ( Q ) KL(P||Q)=H_PQ-H(Q) KL(P∣∣Q)=HP​Q−H(Q)

  K L ( Q ∣ ∣ P ) = H Q P − H ( P ) KL(Q||P)=H_QP-H(P) KL(Q∣∣P)=HQ​P−H(P)

K L ( P ∣ ∣ Q ) ≠ K L ( P ∣ ∣ Q ) KL(P||Q) \ne KL(P||Q) KL(P∣∣Q)̸​=KL(P∣∣Q)

聯合資訊熵、條件資訊熵、互資訊（資訊增益）

• 交叉熵、KL散度都是衡量一個随機變量不同分布；聯合資訊熵和條件資訊熵是衡量兩個随機變量聯合分布【一個分布】互相影響的關系。

  H ( X ) = ∑ − p ( x ) l o g ( p ( x ) ) H(X)=\sum-p(x)log(p(x)) H(X)=∑−p(x)log(p(x))

  H ( Y ) = ∑ − p ( y ) l o g ( p ( y ) ) H(Y)=\sum-p(y)log(p(y)) H(Y)=∑−p(y)log(p(y))

聯合資訊熵

​ H ( X , Y ) = ∑ − p ( x , y ) l o g ( p ( x , y ) ) H(X,Y)=\sum -p(x,y)log(p(x,y)) H(X,Y)=∑−p(x,y)log(p(x,y))

條件資訊熵

​ H ( X ∣ Y ) = ∑ p ( y ) ∑ − p ( x ∣ y ) l o g ( p ( x ∣ y ) ) = ∑ − p ( x , y ) l o g ( p ( x ∣ y ) ) H(X|Y)=\sum p(y) \sum -p(x|y)log(p(x|y))=\sum -p(x,y)log(p(x|y)) H(X∣Y)=∑p(y)∑−p(x∣y)log(p(x∣y))=∑−p(x,y)log(p(x∣y))

條 件 信 息 熵 = 聯 合 信 息 熵 − 信 息 熵 條件資訊熵=聯合資訊熵-資訊熵 條件資訊熵=聯合資訊熵−資訊熵

H ( X ∣ Y ) = H ( X , Y ) − H ( Y ) H(X|Y)=H(X,Y)-H(Y) H(X∣Y)=H(X,Y)−H(Y)

H ( Y ∣ X ) = H ( X , Y ) − H ( X ) H(Y|X)=H(X,Y)-H(X) H(Y∣X)=H(X,Y)−H(X)

互資訊(資訊增益)

• 一個聯合分布中兩個資訊互相影響的那部分資訊量

  I ( X , Y ) = H ( X ) + H ( Y ) − H ( X , Y ) I(X,Y)=H(X)+H(Y)-H(X,Y) I(X,Y)=H(X)+H(Y)−H(X,Y)

卡方檢驗

• H 0 H_0 H0​：總體X的分布函數為 F ( x ) F(x) F(x).如果總體分布為離散型，則假設具體為 H 0 H_0 H0​：總體X的分布律為$