距離和相似性度量

(2011-12-15 10:15:26)

轉載▼

标簽：  雜談

分類： 資料分析

在資料分析和資料挖掘的過程中，我們經常需要知道個體間差異的大小，進而評價個體的相似性和類别。最常見的是資料分析中的相關分析，資料挖掘中的分類和聚類算法，如K最近鄰（KNN）和K均值（K-Means）。當然衡量個體差異的方法有很多，最近查閱了相關的資料，這裡整理羅列下。

　　為了友善下面的解釋和舉例，先設定我們要比較X個體和Y個體間的差異，它們都包含了N個維的特征，即X=（x1, x2, x3, … xn），Y=（y1, y2, y3, … yn）。下面來看看主要可以用哪些方法來衡量兩者的差異，主要分為距離度量和相似度度量。

距離度量

　　距離度量（Distance）用于衡量個體在空間上存在的距離，距離越遠說明個體間的差異越大。

歐幾裡得距離(Euclidean Distance)

　　歐氏距離是最常見的距離度量，衡量的是多元空間中各個點之間的絕對距離。公式如下：

　　因為計算是基于各次元特征的絕對數值，是以歐氏度量需要保證各次元名額在相同的刻度級别，比如對身高（cm）和體重（kg）兩個機關不同的名額使用歐式距離可能使結果失效。

明可夫斯基距離(Minkowski Distance)

　　明氏距離是歐氏距離的推廣，是對多個距離度量公式的概括性的表述。公式如下：

　　這裡的p值是一個變量，當p=2的時候就得到了上面的歐氏距離。

曼哈頓距離(Manhattan Distance)

　　曼哈頓距離來源于城市區塊距離，是将多個次元上的距離進行求和後的結果，即當上面的明氏距離中p=1時得到的距離度量公式，如下：

切比雪夫距離(Chebyshev Distance)

　　切比雪夫距離起源于國際象棋中國王的走法，我們知道國際象棋國王每次隻能往周圍的8格中走一步，那麼如果要從棋盤中A格(x1, y1)走到B格(x2, y2)最少需要走幾步？擴充到多元空間，其實切比雪夫距離就是當p趨向于無窮大時的明氏距離：

　　其實上面的曼哈頓距離、歐氏距離和切比雪夫距離都是明可夫斯基距離在特殊條件下的應用。

馬哈拉諾比斯距離(Mahalanobis Distance)

　　既然歐幾裡得距離無法忽略名額度量的差異，是以在使用歐氏距離之前需要對底層名額進行資料的标準化，而基于各名額次元進行标準化後再使用歐氏距離就衍生出來另外一個距離度量——馬哈拉諾比斯距離（Mahalanobis Distance），簡稱馬氏距離。

相似度度量

　　相似度度量（Similarity），即計算個體間的相似程度，與距離度量相反，相似度度量的值越小，說明個體間相似度越小，差異越大。

向量空間餘弦相似度(Cosine Similarity)

　　餘弦相似度用向量空間中兩個向量夾角的餘弦值作為衡量兩個個體間差異的大小。相比距離度量，餘弦相似度更加注重兩個向量在方向上的差異，而非距離或長度上。公式如下：

皮爾森相關系數(Pearson Correlation Coefficient)

　　即相關分析中的相關系數r，分别對X和Y基于自身總體标準化後計算空間向量的餘弦夾角。公式如下：

Jaccard相似系數(Jaccard Coefficient)

　　Jaccard系數主要用于計算符号度量或布爾值度量的個體間的相似度，因為個體的特征屬性都是由符号度量或者布爾值辨別，是以無法衡量差異具體值的大小，隻能獲得“是否相同”這個結果，是以Jaccard系數隻關心個體間共同具有的特征是否一緻這個問題。如果比較X與Y的Jaccard相似系數，隻比較xn和yn中相同的個數，公式如下：

調整餘弦相似度(Adjusted Cosine Similarity)

　　雖然餘弦相似度對個體間存在的偏見可以進行一定的修正，但是因為隻能分辨個體在維之間的差異，沒法衡量每個維數值的差異，會導緻這樣一個情況：比如使用者對内容評分，5分制，X和Y兩個使用者對兩個内容的評分分别為(1,2)和(4,5)，使用餘弦相似度得出的結果是0.98，兩者極為相似，但從評分上看X似乎不喜歡這2個内容，而Y比較喜歡，餘弦相似度對數值的不敏感導緻了結果的誤差，需要修正這種不合理性，就出現了調整餘弦相似度，即所有次元上的數值都減去一個均值，比如X和Y的評分均值都是3，那麼調整後為(-2,-1)和(1,2)，再用餘弦相似度計算，得到-0.8，相似度為負值并且差異不小，但顯然更加符合現實。

歐氏距離與餘弦相似度

　　歐氏距離是最常見的距離度量，而餘弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基于這兩者的變形和衍生，是以下面重點比較下兩者在衡量個體差異時實作方式和應用環境上的差別。

　　借助三維坐标系來看下歐氏距離和餘弦相似度的差別：

　　從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐标（即個體特征次元的數值）直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是展現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐标軸原點，那麼這個時候餘弦相似度cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。

　　根據歐氏距離和餘弦相似度各自的計算方式和衡量特征，分别适用于不同的資料分析模型：歐氏距離能夠展現個體數值特征的絕對差異，是以更多的用于需要從次元的數值大小中展現差異的分析，如使用使用者行為名額分析使用者價值的相似度或差異；而餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用于使用使用者對内容評分來區分使用者興趣的相似度和差異，同時修正了使用者間可能存在的度量标準不統一的問題（因為餘弦相似度對絕對數值不敏感）。

　　上面都是對距離度量和相似度度量的一些整理和彙總，在現實的使用中選擇合适的距離度量或相似度度量可以完成很多的資料分析和資料挖掘的模組化，後續會有相關的介紹。