相似性和相異性的度量

1、相似性和相異性的度量相似性和相異性是重要的概念，因為它們被許多數(shù)據(jù)挖掘技術(shù)所使用，如聚類、最近鄰分類和異常檢測等。在許多情況下，一旦計算出相似性或相異性，就不再需要原始數(shù)據(jù)了。這種方法可以看作將數(shù)據(jù)變換到相似性（相異性）空間，然后進行分析。首先，我們討論基本要素-相-似性和相異性的高層定義，并討論它們之間的聯(lián)系。為方便起見，我們使用術(shù)語鄰近度（）表示相似性或相異性。由于兩個對象之間的鄰近度是兩個對象對應(yīng)屬性之間的鄰近度的函數(shù)，因此我們首先介紹如何度量僅包含一個簡單屬性的對象之間的鄰近度，然后考慮具有多個屬性的對象的鄰近度度量。這包括相關(guān)和歐幾里得距離度量，以及和余弦相似性度量。前二者適用于時間

2、序列這樣的稠密數(shù)據(jù)或二維點，后二者適用于像文檔這樣的稀疏數(shù)據(jù)。接下來，我們考慮與鄰近度度量相關(guān)的若干重要問題。本節(jié)最后簡略討論如何選擇正確的鄰近度度量。1）基礎(chǔ)1.定義兩個對象之間的相似度（）的非正式定義是這兩個對象相似程度的數(shù)值度量。因而，兩個對象越相似，它們的相似度就越高。通常，相似度是非負的，并常常在（不相似）和（完全相似）之間取值。兩個對象之間的相異度（）是這兩個對象差異程度的數(shù)值度量。對象越類似，它們的相異度就越低。通常，術(shù)語距離（）用作相異度的同義詞，正如我們將介紹的，距離常常用來表示特定類型的相異度。有時，相異度在區(qū)間中取值，但是相異度在和之間取值也很常見。2.變換通常使用變換把

3、相似度轉(zhuǎn)換成相異度或相反，或者把鄰近度變換到一個特定區(qū)間，如0,。例1如，我們可能有相似度，其值域從1到1，0但是我們打算使用的特定算法或軟件包只能處理相異度，或只能處理0,區(qū)1間的相似度。之所以在這里討論這些問題，是因為在稍后討論鄰近度時，我們將使用這種變換。此外，這些問題相對獨立于特定的鄰近度度量。通常，鄰近度度量（特別是相似度）被定義為或變換到區(qū)間0,中1的值。這樣做的動機是使用一種適當(dāng)?shù)某叨?，由鄰近度的值表明兩個對象之間的相似（或相異）程度。這種變換通常是比較直截了當(dāng)?shù)?。例如，如果對象之間的相似度在1（一點也不相似）和1（0完全相似）之間變化，則我們可以使用如下變換將它變換到區(qū)間：，其

4、中和分別是相似度的原值和新值。一般來說，相似度到區(qū)間的變換由如下表達式給出：，其中和分別是相似度的最大值和最小值。類似地，具有有限值域的相異度也能用映射到區(qū)間。然而，將鄰近度映射到區(qū)間可能非常復(fù)雜。例如，如果鄰近度度量原來在區(qū)間01上0取0值0，則需要使用非線性變換，并且在新的尺度上，值之間不再具有相同的聯(lián)系。對于從變化到的相異度度量，考慮變換（相異度、2、和分別被變換到、0.、607.、90.9和90.9。9在9原來相異性尺度上較大的值被壓縮到1附近，但是否希望如此則取決于應(yīng)用。另一個問題是鄰近度度量的含義可能會被改變。例如，相關(guān)性（稍后討論）是一種相似性度量，在區(qū)間上取值，通過取絕對值將這

5、些值映射到區(qū)間丟失了符號信息，而對于某些應(yīng)用，符號信息可能是重要的。將相似度變換成相異度或相反也是比較直截了當(dāng)?shù)模M管我們可能再次面臨保持度量的含義問題和將線性尺度改變成非線性尺度的問題。如果相似度（相異度）落在區(qū)間，則相異度（相似度）可以定義為（或，）相異度0,1,1分0別,被變1換0到0，它們分別被變換到）。另一種簡單的方法是定義相似度為負的相異度（或相反）。例如，相異度0，1，10和10可0以分別變換成相似度0,-1,和，）相異度0,1,1分0別,被變1換0到0，它們分別被變換到。對于變換5,0；、對0于9；對于1dmin_d，它們分別被變換到。在這里的討論中，我們關(guān)注將相異度變換到相似

6、度。一般來說，任何單調(diào)減函數(shù)都可以用來將相異度轉(zhuǎn)換到相似度（或相反）。當(dāng)然，在將相似度變換到相異度（或相反），或者在將鄰近度的值變換到新的尺度時，也必須考慮一些其他因素。我們提到過一些問題，涉及保持意義、擾亂標度和數(shù)據(jù)分析工具的需要，但是肯定還有其他問題。2）簡單屬性之間的相似度和相異度通常，具有若干屬性的對象之間的鄰近度用單個屬性的鄰近度的組合來定義，因此我們首先討論具有單個屬性的對象之間的鄰近度?？紤]由一個標稱屬性描述的對象，對于兩個這樣的對象，相似意味什么呢？由于標稱屬性只攜帶了對象的相異性信息，因此我們只能說兩個對象有相同的值，或者沒有。因而在這種情況下，如果屬性值匹配，則相似度定義為

7、1，否則為0；相異度用相反的方法定義：如果屬性值匹配，相異度為0，否則為1。對于具有單個序數(shù)屬性的對象，情況更為復(fù)雜，因為必須考慮序信息?？紤]一個在標度上測量產(chǎn)品（例如，糖塊）質(zhì)量的屬性。一個評定為的產(chǎn)品與一個評定為的產(chǎn)品應(yīng)當(dāng)比它與一個評定為的產(chǎn)品更接近。為了量化這種觀察，序數(shù)屬性的值常常映射到從或開始的相繼整數(shù)，例如，。于是，與之間的相異度1或者，如果我們希望相異度在和之間取值，；序數(shù)屬性的相似度可以定義為。序數(shù)屬性相似度（相異度）的這種定義可能使讀者感到有點擔(dān)心，因為這里我們定義了相等的區(qū)間，而事實并非如此。如果根據(jù)實際情況，我們應(yīng)該計算出區(qū)間或比率屬性。值與的差真和與的差相同嗎？可能不相

8、同，但是在實踐中，我們的選擇是有限的，并且在缺乏更多信息的情況下，這是定義序數(shù)屬性之間鄰近度的標準方法。對于區(qū)間或比率屬性，兩個對象之間的相異性的自然度量是它們的值之差的絕對值。例如，我們可能將現(xiàn)在的體重與一年前的體重相比較，說我重了磅。在這類情況下，相異度通常在和之間，而不是在和之間取值。如前所述，區(qū)間或比率屬性的相似度通常轉(zhuǎn)換成相異度。表總結(jié)了這些討論。在該表中，和是兩個對象，它們具有一個指明類型的屬性，和分別是和之間的相異度和相似度（分別用和表示）。其他方法也是可能的，但是表中的這些是最常用的。象之間的相異度；（2數(shù)）據(jù)對象之間的相似度。這樣分節(jié)可以更自然地展示使用各種鄰近度度量的基本動

9、機。然而，我們要強調(diào)的是使用上述技術(shù)，相似度可以變換成相異度，反之亦然。數(shù)據(jù)對象之間的相異度本節(jié)，我們討論各種不同類型的相異度。我們從討論距離（距離是具有特定性質(zhì)的相異度）開始，然后給出一些更一般的相異度類型的例子。距離我們首先給出一些例子，然后使用距離的常見性質(zhì)更正式地介紹距離。一維、二維、三維或高維空間中兩個點和之間的歐幾里得距離（a由如下熟悉的公式定義:是維數(shù)，而和分別是和的第個屬性值（分量）。我們用a由如下熟悉的公式定義:是維數(shù)，而和分別是和的第個屬性值（分量）。我們用公式（2-、給出的歐幾里得距離可以用公式（公式（2-、給出的歐幾里得距離可以用公式（2-2的閔可夫斯基距離（）來推廣：

10、其中是參數(shù)。下面是閔可夫斯基距離的三個最常見的例子。=城市街區(qū)（也稱曼哈頓、出租車、范數(shù)）距離。一個常見的例子是漢明距離（），它是兩個具有二元屬性的對象（即兩個二元向量）之間不同的二進制位個數(shù)。=歐幾里得距離（范數(shù)）。上確界（或范數(shù)）距離。這是對象屬性之間的最大距離。更正式地，距離由公式（）定義：注意不要將參數(shù)與維數(shù)（屬性數(shù)）混淆。歐幾里得距離、曼哈頓距離注意不要將參數(shù)與維數(shù)（屬性數(shù)）混淆。歐幾里得距離、曼哈頓距離和上確界距離是對的所有值（）和上確界距離是對的所有值（）3定,義.的.，.并且指定了將每個維（屬性）上的差的組合成總距離的不同方法。表（屬性）上的差的組合成總距離的不同方法。表2-1

11、和0表2-1分1別給出表2-數(shù)8據(jù)的陣。注意，所有的距離矩陣都是對稱的，即第距離和距離的鄰近度矩個表目與第個表目相同,鼻0僅當(dāng)時鼻0僅當(dāng)時W。）。有些人只對滿足這三個性質(zhì)的相異性度量使用術(shù)語距離，但在實踐中常常違反這一約定。這里介紹的三個性質(zhì)是有用的，數(shù)學(xué)上也是令人滿意的。此外，如果三角不等式成立，則該性質(zhì)可以用來提高依賴于距離的技術(shù)（包括聚類）的效率。盡管如此，許多相異度都不滿足一個或多個度量性質(zhì)。下面我們給出兩個這種測度的例子。距例1距非距度量的相異度：集合差。距基于集合論中定義的兩個集合差的概念舉例。設(shè)有兩個集合和，是不在中的中元素的集合。例如，如果，而，則，而空集。我們可以將兩個集合和

12、之間的距離定義為，其中是一個函數(shù)，它返回集合元素的個數(shù)。該距離測度是大于或等于零的整數(shù)值，但不滿足非負性的第二部分，也不滿足對稱性，同時還不滿足三角不等式。然而，如果將相異度修改為，則這些性質(zhì)都可以成立。例非度量的相異度：時間。這里給出一個更常見的例子，其中相異性測度并非度量，但依然是有用的。定義時間之間的距離測度如下：例如，小時，而小時。這種定義是有意義的，例如，在回答如下問題時就體現(xiàn)了這種定義的意義：如果一個事件在每天下午1點發(fā)生，現(xiàn)在是下午2點，那么我們還需要等待多長時間才能等到該事件再度發(fā)生？4）數(shù)據(jù)對象之間的相似度對于相似度，三角不等式（或類似的性質(zhì)）通常不成立，但是對稱性和非負性通

13、常成立。更明確地說，如果是數(shù)據(jù)點和之間的相似度，則相似度具有如下典型性質(zhì)。僅當(dāng)時。（WW）對于所有和，。（對稱性）對于相似度，沒有與三角不等式對應(yīng)的一般性質(zhì)。然而，有時可以將相似度簡單地變換成一種度量距離。稍后討論的余弦相似性度量和相似性度量就是兩個例子。此外，對于特定的相似性度量，還可能在兩個對象相似性上導(dǎo)出本質(zhì)上與三角不等式類似的數(shù)學(xué)約束。例非對稱相似性度量?？紤]一個實驗，實驗中要求人們對屏幕上快速閃過的一小組字符進行分類。該實驗的混淆矩陣（）記錄每個字符被分類為自己的次數(shù)和被分類為另一個字符的次數(shù)。例如，假定0出現(xiàn)了次，它被分類為次，而被分類為次。類似地，出現(xiàn)次并且分類為次，但是分類為只

14、有次。如果取這些計數(shù)作為兩個字符之間相似性的度量，則得到一種相似性度量，但這種相似性度量不是對稱的。在這種情況下，通過選取，相似性度量可以轉(zhuǎn)換成對稱的，其中是新的相似性度量。鄰近性度量的例子本節(jié)給出一些相似性和相異性度量的具體例子。1.二元數(shù)據(jù)的相似性度量兩個僅包含二元屬性的對象之間的相似性度量也稱為相似系數(shù)（）,并且通常在和之間取值，值為表明兩個對象完全相似，而值為0表明對象一點也不相似。有許多理由表明在特定情形下，一種系數(shù)為何比另一種好。設(shè)和是兩個對象，都由個二元屬性組成。這樣的兩個對象（即兩個元向量）的比較可生成如下四個量（頻率）：取并且取0的屬性個數(shù)取并且取0的屬性個數(shù)01取=并且取1

15、的屬性個數(shù)10取=并且取0的屬性個數(shù)11取=并且取1的屬性個數(shù)簡單匹配系數(shù)（）一種常用的相似性系數(shù)是簡單匹配系數(shù)，定義如下：該度量對出現(xiàn)和不出現(xiàn)都進行計數(shù)。因此，可以在一個僅包含是非題的測驗中用來發(fā)現(xiàn)回答問題相似的學(xué)生。系數(shù)（）假定和是兩個數(shù)據(jù)對象，代表一個事務(wù)矩陣的兩行（兩個事務(wù)）。如果每個非對稱的二元屬性對應(yīng)于商店的一種商品，則1表示該商品被購買，而0表示該商品未被購買。由于未被顧客購買的商品數(shù)遠大于被其購買的商品數(shù)，因而像這樣的相似性度量將會判定所有的事務(wù)都是類似的。這樣，常常使用系數(shù)來處理僅包含非對稱的二元屬性的對象。系數(shù)通常用符號表示，由如下等式定義：例和相似性系數(shù)。為了解釋這兩種相

16、似性度量之間的差別，我們對如下二元向量計算和：例和相似性系數(shù)。為了解釋這兩種相似性度量之間的差別，我們對如下二元向量計算和：取并且取的屬性個數(shù)如圖所示，余弦相似度實際上是和之間夾角（余弦）的度量。這如圖所示，余弦相似度實際上是和之間夾角（余弦）的度量。這取并且取的屬性個數(shù)取并且取的屬性個數(shù)通常，文檔用向量表示，向量的每個屬性代表一個特定的詞（術(shù)語）在文檔中出現(xiàn)的頻率。當(dāng)然，實際情況要復(fù)雜得多，因為需要忽略常用詞，并使用各種技術(shù)處理同一個詞的不同形式、不同的文檔長度以及不同的詞頻。盡管文檔具有數(shù)以百千計或數(shù)以萬計的屬性（詞），但是每個文檔向量都是稀疏的，因為它具有相對較少的非零屬性值。（文檔規(guī)范

17、化并不對零詞目創(chuàng)建非零詞目，即文檔規(guī)范化保持稀疏性。）這樣，與事務(wù)數(shù)據(jù)一樣，相似性不能依賴共享0的個數(shù)，因為任意兩個文檔多半都不會包含許多相同的詞，從而如果統(tǒng)計0-匹0配，則大多數(shù)文檔都與其他大部分文檔非常類似。因此，文檔的相似性度量不僅應(yīng)當(dāng)像度量一樣需要忽略匹配，而且還必須能夠處理非二元向量。下面定義的余弦相似度（）就是文檔相似性最常用的度量之一。如果和是兩個文檔向量，則其中，表示向量點積，即：II葢II是向量滅的長度，|x|=J工;=疋=。例5兩個文檔向量的余弦相似度。該例計算下面兩個數(shù)據(jù)對象的余弦相似如圖所示，余弦相似度實際上是和之間夾角（余弦）的度量。這如圖所示，余弦相似度實際上是和之

18、間夾角（余弦）的度量。這樣，如果余弦相似度為1則和之間夾角為，并且除大?。ㄩL度）之外，和是相同的；如果余弦相似度為樣，如果余弦相似度為1則和之間夾角為，并且除大?。ㄩL度）之外，和是相同的；如果余弦相似度為0則和之間夾角為，并且它們不包含任何相同的詞（術(shù)語）。圖余弦度量的幾何解釋公式（）可以寫成公式（）的形式：其中，而和被它們的長度除，將它們其中，而和被它們的長度除，將它們規(guī)范化成具有長度1。這意味在計算相似度時，余弦相似度不考慮兩個數(shù)據(jù)對象的量值。（當(dāng)量值是重要的時，歐幾里得距離可能是一種更好的選擇。）對于長度為1的向量，余弦度量可以通過簡單地取點積計算。從而，在需要計算大量對象之間的余弦相似

19、度時，將對象規(guī)范化，使之具有單位長度可以減少計算時間。廣義系數(shù)（系數(shù)）廣義系數(shù)可以用于文檔數(shù)據(jù)，并在二元屬性情況下歸約為系數(shù)。廣義系數(shù)又稱系數(shù)。（然而，還有一種系數(shù)也稱系數(shù)。）該系數(shù)用表示，由下式定義：相關(guān)性兩個具有二元變量或連續(xù)變量的數(shù)據(jù)對象之間的相關(guān)性是對象屬性之間線性聯(lián)系的度量。（更一般屬性之間的相關(guān)性計算可以類似地定義。）更準確地，兩個數(shù)據(jù)對象和之間的皮爾森相關(guān)（）系數(shù)由下式定義：具有完全正（負）線性關(guān)系，即，其中和是常數(shù)。下面兩個和的值集分別給出相關(guān)度為和的情況。為簡單起見，第一組中取和的均值為0例7非線性關(guān)系。如果相關(guān)度為0，則兩個數(shù)據(jù)對象的屬性之間不存在線性關(guān)系。然而，仍然可能存

20、在非線性關(guān)系。在下面的例子中，數(shù)據(jù)對象的屬性之間存在非線性關(guān)系，但是它們的相關(guān)度為0例相關(guān)性可視化。通過繪制對應(yīng)屬性值對可以很容易地判定兩個數(shù)據(jù)對象和之間的相關(guān)性。圖給出了一些這種圖，和具有個屬性，這些屬性的值隨機地產(chǎn)生（服從正態(tài)分布），使得和的相關(guān)度從到1圖中每個小圓圈代表個屬性中的一個，其坐標是的一個屬性的值，而其坐標是的相同屬性的值。關(guān)度可以通過求點積來計算。注意，這與其他情況下使用的標準化不同，在其他情況下，我們使用變換和1i散度。本節(jié)，我們簡略介紹散度（ge它是一族具有共同性質(zhì)的鄰近函數(shù)。這樣，可以構(gòu)造使用發(fā)散函數(shù)的一般數(shù)據(jù)挖掘算法，如聚類算法，具體的例子是均值聚類算法。注意，本節(jié)需

21、要向量計算方面的知識。散度是損失或失真函數(shù)。為了理解損失函數(shù)，考慮如下情況：設(shè)和是兩個點，其中是原來的點，而是它的某個失真或近似，例如，可能是由于添加了一些隨機噪聲到上而產(chǎn)生的。損失函數(shù)的目的是度量用近似導(dǎo)致的失真或損失。當(dāng)然，和越類似，失真或損失就越小，因而散度可以用作相異性函數(shù)。有如下正式定義。定義：散度給定一個嚴格凸函數(shù)（連同一些通常滿足的適度限制），由該函數(shù)生成的散度（損失函數(shù)）通過下面的公式給出：例我們使用平方歐幾里得距離給出散度的一個具體例子。為了簡化數(shù)學(xué)計算，我們僅限于一維。設(shè)和是實數(shù)，而0是實數(shù)值函數(shù)，爐=。在此情況下，梯度歸結(jié)為導(dǎo)數(shù)，而點積歸結(jié)為乘積。例如，公式（2-1）2變

22、成公式（2-1）3。該例的圖形在圖中給出，其中=在和上給出了散度。6）鄰近度計算問題本節(jié)討論與鄰近性度量有關(guān)的一些重要問題：（1當(dāng)）屬性具有不同的尺度（a或相關(guān)時如何處理；當(dāng)對象包含不同類型的屬性（例如，定量屬性和定性屬性）時如何計算對象之間的鄰近度；（3當(dāng)）屬性具有不同的權(quán)重（即并非所有的屬性都對對象的鄰近度具有相等的貢獻）時，如何處理鄰近度計算。1.距離度量的標準化和相關(guān)性距離度量的一個重要問題是當(dāng)屬性具有不同的值域時如何處理。（這種情況通常稱作變量具有不同的尺度。）前面，使用歐幾里得距離，基于年齡和收入兩個屬性來度量人之間的距離。除非這兩個屬性是標準化的，否則兩個人之間的距離將被收入所左

23、右。一個相關(guān)的問題是，除值域不同外，當(dāng)某些屬性之間還相關(guān)時，如何計算距離。當(dāng)屬性相關(guān)、具有不同的值域（不同的方差）、并且數(shù)據(jù)分布近似于高斯（正態(tài)）分布時，歐幾里得距離的拓廣，距離是有用的。具體地說，兩個對象（向量）和之間的距離定義為：其中衛(wèi)二是數(shù)據(jù)協(xié)方差矩陣的逆。注意，協(xié)方差矩陣衛(wèi)是這樣的矩陣，它的第個元素是第個和第個屬性的協(xié)方差，由公式（1定義。例在圖中有個點，其屬性和屬性的相關(guān)度為.在橢圓長軸兩端的兩個大點之間的歐幾里得距離為，但距離僅為。實踐中，計算距離的費用昂貴，但是對于其屬性相關(guān)的對象來說是值得的。如果屬性相對來說不相關(guān)，只是具有不同的值域，則只需要對變量組合異種屬性的相似度前面的相

24、似度定義所基于的方法都假定所有屬性具有相同類型。當(dāng)屬性具有不同類型時，就需要更一般的方法。直截了當(dāng)?shù)姆椒ㄊ鞘褂帽?-分7別計算出每個屬性之間的相似度，然后使用一種導(dǎo)致0和1之間相似度的方法組合這些相似度?？傁嗨贫纫话愣x為所有屬性相似度的平均值。不幸的是，如果某些屬性是非對稱屬性，這種方法效果不好。例如，如果所有的屬性都是非對稱的二元屬性，則相似性度量先歸結(jié)為簡單匹配系數(shù)-一-種對于二元非對稱屬性并不合適的度量。處理該問題的最簡單方法是：如果兩個對象在非對稱屬性上的值都是0，則在計算對象相似度時忽略它們。類似的方法也能很好地處理遺漏值。概括地說，算法可以有效地計算具有不同類型屬性的兩個對象和在前面的大部分討論中，所有的屬性在計算鄰近度時都會被同等對待。但是，當(dāng)某些屬性對鄰近度的定義比其他屬性更重要時，我們并不希望這種同等對待的方式。為了處理這種情況，可以通過對每個屬性的貢獻加權(quán)來修改鄰近度公式。如果權(quán)耳心的和為1則公式（）變成閔可夫斯基距離的定義也可以修改為：）選取正確的鄰近性度量下面是一些一般觀察，可能會對你有所幫助。首先，鄰近性度量的類型應(yīng)當(dāng)與數(shù)據(jù)類型相適應(yīng)。對于許多稠密的、連續(xù)的數(shù)據(jù)，通常使用距離度量，如歐幾里得距離等。連續(xù)屬性之間的鄰近度通常用屬性值的差