相似性和相異性的度量

如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!2/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!相似性和相異性的度量相似性和相異性是重要的概念，因?yàn)樗鼈儽辉S多數(shù)據(jù)挖掘技術(shù)所使用，如聚類、最近鄰分類和異常檢測(cè)等。在許多情況下，一旦計(jì)算出相似性或相異性，就不再需要原始數(shù)據(jù)了。這種方法可以看作將數(shù)據(jù)變換到相似性（相異性）空間，然后進(jìn)行分析。首先，我們討論基本要素--相似性和相異性的高層定義，并討論它們之間的聯(lián)系。為方便起見(jiàn)，我們使用術(shù)語(yǔ)鄰近度（proximity）表示相似性或相異性。由于兩個(gè)對(duì)象之間的鄰近度是兩個(gè)對(duì)象對(duì)應(yīng)屬性之間的鄰近度的函數(shù)，因此我們首先介紹如何度量?jī)H包含一個(gè)簡(jiǎn)單屬性的對(duì)象之間的鄰近度，然后考慮具有多個(gè)屬性的對(duì)象的鄰近度度量。這包括相關(guān)和歐幾里得距離度量，以及Jaccard和余弦相似性度量。前二者適用于時(shí)間序列這樣的稠密數(shù)據(jù)或二維點(diǎn)，后二者適用于像文檔這樣的稀疏數(shù)據(jù)。接下來(lái)，我們考慮與鄰近度度量相關(guān)的若干重要問(wèn)題。本節(jié)最后簡(jiǎn)略討論如何選擇正確的鄰近度度量。1)基礎(chǔ)1.定義兩個(gè)對(duì)象之間的相似度（similarity）的非正式定義是這兩個(gè)對(duì)象相似程度的數(shù)值度量。因而，兩個(gè)對(duì)象越相似，它們的相似度就越高。通常，相似度是非負(fù)的，并常常在0（不相似）和1（完全相似）之間取值。兩個(gè)對(duì)象之間的相異度（dissimilarity）是這兩個(gè)對(duì)象差異程度的數(shù)值度量。對(duì)象越類似，它們的相異度就越低。通常，術(shù)語(yǔ)距離（distance）用作相異度的同義詞，正如我們將介紹的，距離常常用來(lái)表示特定類型的相異度。有時(shí)，相異度在區(qū)間[0,1]中取值，但是相異度在0和之間取值也很常見(jiàn)。2.變換通常使用變換把相似度轉(zhuǎn)換成相異度或相反，或者把鄰近度變換到一個(gè)特定區(qū)間，如[0,1]。例如，我們可能有相似度，其值域從1到10，但是我們打算使用的特定算法或軟件包只能處理相異度，或只能處理[0,1]區(qū)間的相似度。之所以在這里討論這些問(wèn)題，是因?yàn)樵谏院笥懻撪徑葧r(shí)，我們將使用這種變換。此外，這些問(wèn)題相對(duì)獨(dú)立于特定的鄰近度度量。通常，鄰近度度量（特別是相似度）被定義為或變換到區(qū)間[0,1]中的值。這樣做的動(dòng)機(jī)是使用一種適當(dāng)?shù)某叨龋舌徑鹊闹当砻鲀蓚€(gè)對(duì)象之間的相似（或相異）程度。這種變換通常是比較直截了當(dāng)?shù)?。例如，如果?duì)象之間的相似度在1（一點(diǎn)也不相似）和10（完全相似）之間變化，則我們可以使用如下變換將它變換到[0,1]區(qū)間：s'=(s-1)/9，其中s和s'分別是相似度的原值和新值。一般來(lái)說(shuō)，相似度到[0,1]區(qū)間的變換由如下表達(dá)式給出：s'=(s-min_s)/(max_s-min_s)，其中max_s和min_s分別是相似度的最大值和最小值。類似地，具有有限值域的相異度也能用d'=(d如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!3/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!-min_d)/(max_d

-min_d)映射到[0,1]區(qū)間。然而，將鄰近度映射到[0,1]區(qū)間可能非常復(fù)雜。例如，如果鄰近度度量原來(lái)在區(qū)間[0

1000]上取值，則需要使用非線性變換，并且在新的尺度上，值之間不再具有相同的聯(lián)系。對(duì)于從0變化到1000的相異度度量，考慮變換d'=d/(1+d)，相異度0、0.5、2、10、100和1000分別被變換到0、0.33、0.67、0.90、0.99和0.999。在原來(lái)相異性尺度上較大的值被壓縮到1附近，但是否希望如此則取決于應(yīng)用。另一個(gè)問(wèn)題是鄰近度度量的含義可能會(huì)被改變。例如，相關(guān)性（稍后討論）是一種相似性度量，在區(qū)間[-1,1]上取值，通過(guò)取絕對(duì)值將這些值映射到[0,1]區(qū)間丟失了符號(hào)信息，而對(duì)于某些應(yīng)用，符號(hào)信息可能是重要的。將相似度變換成相異度或相反也是比較直截了當(dāng)?shù)?，盡管我們可能再次面臨保持度量的含義問(wèn)題和將線性尺度改變成非線性尺度的問(wèn)題。如果相似度（相異度）落在[0,1]區(qū)間，則相異度（相似度）可以定義為d=1-s（或s=1-d）。另一種簡(jiǎn)單的方法是定義相似度為負(fù)的相異度（或相反）。例如，相異度0，1，10和100可以分別變換成相似度0,-1,-10和-100。負(fù)變換產(chǎn)生的相似度結(jié)果不必局限于[0,1]區(qū)間，但是，如果希望的話，則可以使用變換s=1/(d+1)，。對(duì)于變換s=1/(d+1)，相異度0,1,10,100分別被變換到1,0.5,0.09,0.01；對(duì)于，它們分別被變換到1.00,0.37,0.00,0.00；對(duì)于s=，它們分別被變換到1.00,0.99,0.00,0.00。在這里的討論中，我們關(guān)注將相異度變換到相似度。一般來(lái)說(shuō)，任何單調(diào)減函數(shù)都可以用來(lái)將相異度轉(zhuǎn)換到相似度（或相反）。當(dāng)然，在將相似度變換到相異度（或相反），或者在將鄰近度的值變換到新的尺度時(shí)，也必須考慮一些其他因素。我們提到過(guò)一些問(wèn)題，涉及保持意義、擾亂標(biāo)度和數(shù)據(jù)分析工具的需要，但是肯定還有其他問(wèn)題。2)

簡(jiǎn)單屬性之間的相似度和相異度通常，具有若干屬性的對(duì)象之間的鄰近度用單個(gè)屬性的鄰近度的組合來(lái)定義，因此我們首先討論具有單個(gè)屬性的對(duì)象之間的鄰近度?？紤]由一個(gè)標(biāo)稱屬性描述的對(duì)象，對(duì)于兩個(gè)這樣的對(duì)象，相似意味什么呢？由于標(biāo)稱屬性只攜帶了對(duì)象的相異性信息，因此我們只能說(shuō)兩個(gè)對(duì)象有相同的值，或者沒(méi)有。因而在這種情況下，如果屬性值匹配，則相似度定義為1，否則為0；相異度用相反的方法定義：如果屬性值匹配，相異度為0，否則為1。如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!3/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!對(duì)于具有單個(gè)序數(shù)屬性的對(duì)象，情況更為復(fù)雜，因?yàn)楸仨毧紤]序信息?？紤]一個(gè)在標(biāo)度{poor,fair,OK,good,wonderful}上測(cè)量產(chǎn)品（例如，糖塊）質(zhì)量的屬性。一個(gè)評(píng)定為wonderful的產(chǎn)品P1與一個(gè)評(píng)定為good的產(chǎn)品P2應(yīng)當(dāng)比它與一個(gè)評(píng)定為OK的產(chǎn)品P3更接近。為了量化這種觀察，序數(shù)屬性的值常常映射到從0或1開(kāi)始的相繼整數(shù)，例如，{poor=0,fair=1,OK=2,good=3,wonderful=4}。于是，P1與P2之間的相異度d(P1,P2)=3-2=1，或者，如果我們希望相異度在0和1之間取值，d(P1,P2)=(3-2)/4=0.25；序數(shù)屬性的相似度可以定義為s=1-d。序數(shù)屬性相似度（相異度）的這種定義可能使讀者感到有點(diǎn)擔(dān)心，因?yàn)檫@里我們定義了相等的區(qū)間，而事實(shí)并非如此。如果根據(jù)實(shí)際情況，我們應(yīng)該計(jì)算出區(qū)間或比率屬性。值fair與good的差真和OK與wonderful的差相同嗎？可能不相同，但是在實(shí)踐中，我們的選擇是有限的，并且在缺乏更多信息的情況下，這是定義序數(shù)屬性之間鄰近度的標(biāo)準(zhǔn)方法。對(duì)于區(qū)間或比率屬性，兩個(gè)對(duì)象之間的相異性的自然度量是它們的值之差的絕對(duì)值。例如，我們可能將現(xiàn)在的體重與一年前的體重相比較，說(shuō)"我重了10磅。"在這類情況下，相異度通常在0和x之間，而不是在0和1之間取值。如前所述，區(qū)間或比率屬性的相似度通常轉(zhuǎn)換成相異度。表2-7總結(jié)了這些討論。在該表中，x和y是兩個(gè)對(duì)象，它們具有一個(gè)指明類型的屬性，d(x,y)和s(x,y)分別是x和y之間的相異度和相似度（分別用d和s表示）。其他方法也是可能的，但是表中的這些是最常用的。表2-7

簡(jiǎn)單屬性的相似度和相異度

下面兩節(jié)介紹更復(fù)雜的涉及多個(gè)屬性的對(duì)象之間的鄰近性度量：(1)數(shù)據(jù)對(duì)象之間的相異度；(2)數(shù)據(jù)對(duì)象之間的相似度。這樣分節(jié)可以更自然地展示使用各種鄰近度度量的基本動(dòng)機(jī)。然而，我們要強(qiáng)調(diào)的是使用上述技術(shù)，相似度可以變換成相異度，反之亦然。如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!4/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!3)

數(shù)據(jù)對(duì)象之間的相異度本節(jié)，我們討論各種不同類型的相異度。我們從討論距離（距離是具有特定性質(zhì)的相異度）開(kāi)始，然后給出一些更一般的相異度類型的例子。距離我們首先給出一些例子，然后使用距離的常見(jiàn)性質(zhì)更正式地介紹距離。一維、二維、三維或高維空間中兩個(gè)點(diǎn)x和y之間的歐幾里得距離（Euclideandistance）d由如下熟悉的公式定義：

其中，n是維數(shù)，而xk和yk分別是x和y的第k個(gè)屬性值（分量）。我們用圖2-15、表2-8和表2-9解釋該公式，它們展示了這個(gè)點(diǎn)集、這些點(diǎn)的x和y坐標(biāo)以及包含這些點(diǎn)之間距離的距離矩陣（distancematrix）。

公式（2-1）給出的歐幾里得距離可以用公式（2-2）的閔可夫斯基距離（Minkowskidistance）來(lái)推廣：

如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!6/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!其中r是參數(shù)。下面是閔可夫斯基距離的三個(gè)最常見(jiàn)的例子。r=1，城市街區(qū)（也稱曼哈頓、出租車、L1范數(shù)）距離。一個(gè)常見(jiàn)的例子是漢明距離（Hammingdistance），它是兩個(gè)具有二元屬性的對(duì)象（即兩個(gè)二元向量）之間不同的二進(jìn)制位個(gè)數(shù)。r=2，歐幾里得距離（L2范數(shù)）。r=，上確界（Lmax或L范數(shù)）距離。這是對(duì)象屬性之間的最大距離。更正式地，L距離由公式（2-3）定義：

注意不要將參數(shù)r與維數(shù)（屬性數(shù)）n混淆。歐幾里得距離、曼哈頓距離和上確界距離是對(duì)n的所有值（1,2,3,...）定義的，并且指定了將每個(gè)維（屬性）上的差的組合成總距離的不同方法。表2-10和表2-11分別給出表2-8數(shù)據(jù)的L1距離和L距離的鄰近度矩陣。注意，所有的距離矩陣都是對(duì)稱的，即第ij個(gè)表目與第ji個(gè)表目相同，例如，在表2-9中，第4行第1列和第1行第4列都包含值5.1。

距離（如歐幾里得距離）具有一些眾所周知的性質(zhì)。如果d(x,y)是兩個(gè)點(diǎn)x和y之間的距離，則如下性質(zhì)成立。(1)非負(fù)性。(a)對(duì)于所有x和y，d(x,y)≥0，(b)僅當(dāng)x=y時(shí)d(x,y)=0。(2)對(duì)稱性。對(duì)于所有x和y，d(x,y)=d(y,x)。(3)三角不等式。對(duì)于所有x，y和z，d(x,z)≤d(x,y)+d(y,z)。滿足以上三個(gè)性質(zhì)的測(cè)度稱為度量（metric）。有些人只對(duì)滿足這三個(gè)性質(zhì)的相異性度量使用術(shù)語(yǔ)距離，但在實(shí)踐中常常違反這一約定。這里介紹的三個(gè)性質(zhì)是有用的，數(shù)學(xué)上也是令人滿意的。此外，如果三角不等式成立，則該性質(zhì)可以用來(lái)提高依賴于距離的技術(shù)（包括聚類）的效率。盡管如此，許多相異度都不滿足一個(gè)或多個(gè)度量性質(zhì)。下面我們給出兩個(gè)這種測(cè)度的例子。例1

非度量的相異度：集合差?；诩险撝卸x的兩個(gè)集合差的概念舉例。設(shè)有兩個(gè)集合A和B，A-B是不在B中的A中元素的集合。例如，如果A={1,2,3,4}，而B={2,3,4}，則A如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!6/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!-B={1}，而B-A=空集。我們可以將兩個(gè)集合A和B之間的距離定義為d(A,B)=size(A-B)，其中size是一個(gè)函數(shù)，它返回集合元素的個(gè)數(shù)。該距離測(cè)度是大于或等于零的整數(shù)值，但不滿足非負(fù)性的第二部分，也不滿足對(duì)稱性，同時(shí)還不滿足三角不等式。然而，如果將相異度修改為d(A,B)=size(A-B)+size(B-A)，則這些性質(zhì)都可以成立。例2

非度量的相異度：時(shí)間。這里給出一個(gè)更常見(jiàn)的例子，其中相異性測(cè)度并非度量，但依然是有用的。定義時(shí)間之間的距離測(cè)度如下：

例如，d(1PM,2PM)=1小時(shí)，而d(2PM,1PM)=23小時(shí)。這種定義是有意義的，例如，在回答如下問(wèn)題時(shí)就體現(xiàn)了這種定義的意義："如果一個(gè)事件在每天下午1點(diǎn)發(fā)生，現(xiàn)在是下午2點(diǎn)，那么我們還需要等待多長(zhǎng)時(shí)間才能等到該事件再度發(fā)生？"4）數(shù)據(jù)對(duì)象之間的相似度對(duì)于相似度，三角不等式（或類似的性質(zhì)）通常不成立，但是對(duì)稱性和非負(fù)性通常成立。更明確地說(shuō)，如果s(x,y)是數(shù)據(jù)點(diǎn)x和y之間的相似度，則相似度具有如下典型性質(zhì)。(1)僅當(dāng)x=y時(shí)s(x,y)=1。（0≤s≤1）(2)對(duì)于所有x和y，s(x,y)=s(y,x)。（對(duì)稱性）對(duì)于相似度，沒(méi)有與三角不等式對(duì)應(yīng)的一般性質(zhì)。然而，有時(shí)可以將相似度簡(jiǎn)單地變換成一種度量距離。稍后討論的余弦相似性度量和Jaccard相似性度量就是兩個(gè)例子。此外，對(duì)于特定的相似性度量，還可能在兩個(gè)對(duì)象相似性上導(dǎo)出本質(zhì)上與三角不等式類似的數(shù)學(xué)約束。例3

非對(duì)稱相似性度量?？紤]一個(gè)實(shí)驗(yàn)，實(shí)驗(yàn)中要求人們對(duì)屏幕上快速閃過(guò)的一小組字符進(jìn)行分類。該實(shí)驗(yàn)的混淆矩陣（confusionmatrix）記錄每個(gè)字符被分類為自己的次數(shù)和被分類為另一個(gè)字符的次數(shù)。例如，假定"0"出現(xiàn)了200次，它被分類為"0"160次，而被分類為"o"40次。類似地，"o"出現(xiàn)200次并且分類為"o"170次，但是分類為"0"只有30次。如果取這些計(jì)數(shù)作為兩個(gè)字符之間相似性的度量，則得到一種相似性度量，但這種相似性度量不是對(duì)稱的。在這種情況下，通過(guò)選取s'(x,y)=s'(y,x)=(s(x,y)+s(y,x))/2，相似性度量可以轉(zhuǎn)換成對(duì)稱的，其中s'是新的相似性度量。如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!7/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!5)

鄰近性度量的例子本節(jié)給出一些相似性和相異性度量的具體例子。1.二元數(shù)據(jù)的相似性度量?jī)蓚€(gè)僅包含二元屬性的對(duì)象之間的相似性度量也稱為相似系數(shù)（similaritycoefficient），并且通常在0和1之間取值，值為1表明兩個(gè)對(duì)象完全相似，而值為0表明對(duì)象一點(diǎn)也不相似。有許多理由表明在特定情形下，一種系數(shù)為何比另一種好。設(shè)x和y是兩個(gè)對(duì)象，都由n個(gè)二元屬性組成。這樣的兩個(gè)對(duì)象（即兩個(gè)二元向量）的比較可生成如下四個(gè)量（頻率）：f00=x取0并且y取0的屬性個(gè)數(shù)f01=x取0并且y取1的屬性個(gè)數(shù)f10=x取1并且y取0的屬性個(gè)數(shù)f11=x取1并且y取1的屬性個(gè)數(shù)簡(jiǎn)單匹配系數(shù)（SimpleMatchingCoefficient,SMC）,一種常用的相似性系數(shù)是簡(jiǎn)單匹配系數(shù)，定義如下：

該度量對(duì)出現(xiàn)和不出現(xiàn)都進(jìn)行計(jì)數(shù)。因此，SMC可以在一個(gè)僅包含是非題的測(cè)驗(yàn)中用來(lái)發(fā)現(xiàn)回答問(wèn)題相似的學(xué)生。Jaccard系數(shù)（JaccardCoefficient）,假定x和y是兩個(gè)數(shù)據(jù)對(duì)象，代表一個(gè)事務(wù)矩陣的兩行（兩個(gè)事務(wù)）。如果每個(gè)非對(duì)稱的二元屬性對(duì)應(yīng)于商店的一種商品，則1表示該商品被購(gòu)買，而0表示該商品未被購(gòu)買。由于未被顧客購(gòu)買的商品數(shù)遠(yuǎn)大于被其購(gòu)買的商品數(shù)，因而像SMC這樣的相似性度量將會(huì)判定所有的事務(wù)都是類似的。這樣，常常使用Jaccard系數(shù)來(lái)處理僅包含非對(duì)稱的二元屬性的對(duì)象。Jaccard系數(shù)通常用符號(hào)J表示，由如下等式定義：

如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!8/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!例4

SMC和Jaccard相似性系數(shù)。為了解釋這兩種相似性度量之間的差別，我們對(duì)如下二元向量計(jì)算SMC和J：x=(1,0,0,0,0,0,0,0,0,0)y=(0,0,0,0,0,0,1,0,0,1)f01=2

x取0并且y取1的屬性個(gè)數(shù)f10=1

x取1并且y取0的屬性個(gè)數(shù)f00=7

x取0并且y取0的屬性個(gè)數(shù)f11=0

x取1并且y取1的屬性個(gè)數(shù)

2.余弦相似度通常，文檔用向量表示，向量的每個(gè)屬性代表一個(gè)特定的詞（術(shù)語(yǔ)）在文檔中出現(xiàn)的頻率。當(dāng)然，實(shí)際情況要復(fù)雜得多，因?yàn)樾枰雎猿Ｓ迷~，并使用各種技術(shù)處理同一個(gè)詞的不同形式、不同的文檔長(zhǎng)度以及不同的詞頻。盡管文檔具有數(shù)以百千計(jì)或數(shù)以萬(wàn)計(jì)的屬性（詞），但是每個(gè)文檔向量都是稀疏的，因?yàn)樗哂邢鄬?duì)較少的非零屬性值。（文檔規(guī)范化并不對(duì)零詞目創(chuàng)建非零詞目，即文檔規(guī)范化保持稀疏性。）這樣，與事務(wù)數(shù)據(jù)一樣，相似性不能依賴共享0的個(gè)數(shù)，因?yàn)槿我鈨蓚€(gè)文檔多半都不會(huì)包含許多相同的詞，從而如果統(tǒng)計(jì)0-0匹配，則大多數(shù)文檔都與其他大部分文檔非常類似。因此，文檔的相似性度量不僅應(yīng)當(dāng)像Jaccard度量一樣需要忽略0-0匹配，而且還必須能夠處理非二元向量。下面定義的余弦相似度（cosinesimilarity）就是文檔相似性最常用的度量之一。如果x和y是兩個(gè)文檔向量，則

其中，"."表示向量點(diǎn)積，即：。例5

兩個(gè)文檔向量的余弦相似度。該例計(jì)算下面兩個(gè)數(shù)據(jù)對(duì)象的余弦相似度，這些數(shù)據(jù)對(duì)象可能代表文檔向量：如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!9/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如圖2-16所示，余弦相似度實(shí)際上是x和y之間夾角（余弦）的度量。這樣，如果余弦相似度為1，則x和y之間夾角為0，并且除大?。ㄩL(zhǎng)度）之外，x和y是相同的；如果余弦相似度為0，則x和y之間夾角為90，并且它們不包含任何相同的詞（術(shù)語(yǔ)）。

圖2-16

余弦度量的幾何解釋公式（2-7）可以寫成公式（2-8）的形式：

其中，=x/||x||，而=y/||y||。x和y被它們的長(zhǎng)度除，將它們規(guī)范化成具有長(zhǎng)度1。這意味在計(jì)算相似度時(shí)，余弦相似度不考慮兩個(gè)數(shù)據(jù)對(duì)象的量值。（當(dāng)量值是重要的時(shí)，歐幾里得距離可能是一種更好的選擇。）對(duì)于長(zhǎng)度為1的向量，余弦度量可以通過(guò)簡(jiǎn)單地取點(diǎn)積計(jì)算。從而，在需要計(jì)算大量對(duì)象之間的余弦相似度時(shí)，將對(duì)象規(guī)范化，使之具有單位長(zhǎng)度可以減少計(jì)算時(shí)間。3.廣義Jaccard系數(shù)（Tanimoto系數(shù)）廣義Jaccard系數(shù)可以用于文檔數(shù)據(jù)，并在二元屬性情況下歸約為Jaccard系數(shù)。廣義Jaccard系數(shù)又稱Tanimoto系數(shù)。（然而，還有一種系數(shù)也稱Tanimoto系數(shù)。）該系數(shù)用EJ表示，由下式定義：

如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!10/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!

4.相關(guān)性兩個(gè)具有二元變量或連續(xù)變量的數(shù)據(jù)對(duì)象之間的相關(guān)性是對(duì)象屬性之間線性聯(lián)系的度量。（更一般屬性之間的相關(guān)性計(jì)算可以類似地定義。）更準(zhǔn)確地，兩個(gè)數(shù)據(jù)對(duì)象x和y之間的皮爾森相關(guān)（Pearson'scorrelation）系數(shù)由下式定義：

這里我們使用標(biāo)準(zhǔn)的統(tǒng)計(jì)學(xué)記號(hào)和定義：

例6

完全相關(guān)。相關(guān)度總是在-1到1之間取值。相關(guān)度為1（-1）意味x和y具有完全正（負(fù)）線性關(guān)系，即Xk=aYk+b，其中a和b是常數(shù)。下面兩個(gè)x和y的值集分別給出相關(guān)度為-1和+1的情況。為簡(jiǎn)單起見(jiàn)，第一組中取x和y的均值為0。x=(-3,6,0,3,-6)y=(1,-2,0,-1,2)x=(3,6,0,3,6)y=(1,2,0,1,2)例7非線性關(guān)系。如果相關(guān)度為0，則兩個(gè)數(shù)據(jù)對(duì)象的屬性之間不存在線性關(guān)系。然而，仍然可能存在非線性關(guān)系。在下面的例子中，數(shù)據(jù)對(duì)象的屬性之間存在非線性關(guān)系yk=xk^2，但是它們的相關(guān)度為0。x=(3,-2,-1,0,1,2,3)如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!12/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!y=(9,4,1,0,1,4,9)例8

相關(guān)性可視化。通過(guò)繪制對(duì)應(yīng)屬性值對(duì)可以很容易地判定兩個(gè)數(shù)據(jù)對(duì)象x和y之間的相關(guān)性。圖2-17給出了一些這種圖，x和y具有30個(gè)屬性，這些屬性的值隨機(jī)地產(chǎn)生（服從正態(tài)分布），使得x和y的相關(guān)度從-1到1。圖中每個(gè)小圓圈代表30個(gè)屬性中的一個(gè)，其x坐標(biāo)是x的一個(gè)屬性的值，而其y坐標(biāo)是y的相同屬性的值。

圖2-17

解釋相關(guān)度從-1到1的散布圖如果通過(guò)減去均值，然后規(guī)范化使其長(zhǎng)度為1來(lái)變換x和y，則它們的相關(guān)度可以通過(guò)求點(diǎn)積來(lái)計(jì)算。注意，這與其他情況下使用的標(biāo)準(zhǔn)化不同，在其他情況下，我們使用變換和。Bregman散度。本節(jié)，我們簡(jiǎn)略介紹Bregman散度（Bregmandivergence），它是一族具有共同性質(zhì)的鄰近函數(shù)。這樣，可以構(gòu)造使用Bregman發(fā)散函數(shù)的一般數(shù)據(jù)挖掘算法，如聚類算法，具體的例子是K均值聚類算法。注意，本節(jié)需要向量計(jì)算方面的知識(shí)。如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!12/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!Bregman散度是損失或失真函數(shù)。為了理解損失函數(shù)，考慮如下情況：設(shè)x和y是兩個(gè)點(diǎn)，其中y是原來(lái)的點(diǎn)，而x是它的某個(gè)失真或近似，例如，x可能是由于添加了一些隨機(jī)噪聲到y(tǒng)上而產(chǎn)生的。損失函數(shù)的目的是度量用x近似y導(dǎo)致的失真或損失。當(dāng)然，x和y越類似，失真或損失就越小，因而Bregman散度可以用作相異性函數(shù)。有如下正式定義。定義：Bregman散度

給定一個(gè)嚴(yán)格凸函數(shù)（連同一些通常滿足的適度限制），由該函數(shù)生成的Bregman散度（損失函數(shù)）D(x,y)通過(guò)下面的公式給出：

例

我們使用平方歐幾里得距離給出Bregman散度的一個(gè)具體例子。為了簡(jiǎn)化數(shù)學(xué)計(jì)算，我們僅限于一維。設(shè)x和y是實(shí)數(shù)，而(t)是實(shí)數(shù)值函數(shù)，。在此情況下，梯度歸結(jié)為導(dǎo)數(shù)，而點(diǎn)積歸結(jié)為乘積。例如，公式（2-12）變成公式（2-13）。

該例的圖形在圖2-18中給出，其中y=1。在x=2和x=3上給出了Bregman散度。

如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!13/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!

圖2-18

圖示Bregman散度6）

鄰近度計(jì)算問(wèn)題本節(jié)討論與鄰近性度量有關(guān)的一些重要問(wèn)題：(1)當(dāng)屬性具有不同的尺度（scale）或相關(guān)時(shí)如何處理；(2)當(dāng)對(duì)象包含不同類型的屬性（例如，定量屬性和定性屬性）時(shí)如何計(jì)算對(duì)象之間的鄰近度；(3)當(dāng)屬性具有不同的權(quán)重（即并非所有的屬性都對(duì)對(duì)象的鄰近度具有相等的貢獻(xiàn)）時(shí)，如何處理鄰近度計(jì)算。1.距離度量的標(biāo)準(zhǔn)化和相關(guān)性距離度量的一個(gè)重要問(wèn)題是當(dāng)屬性具有不同的值域時(shí)如何處理。（這種情況通常稱作"變量具有不同的尺度。"）前面，使用歐幾里得距離，基于年齡和收入兩個(gè)屬性來(lái)度量人之間的距離。除非這兩個(gè)屬性是標(biāo)準(zhǔn)化的，否則兩個(gè)人之間的距離將被收入所左右。一個(gè)相關(guān)的問(wèn)題是，除值域不同外，當(dāng)某些屬性之間還相關(guān)時(shí)，如何計(jì)算距離。當(dāng)屬性相關(guān)、具有不同的值域（不同的方差）、并且數(shù)據(jù)分布近似于高斯（正態(tài)）分布時(shí)，歐幾里得距離的拓廣，Mahalanobis距離是有用的。具體地說(shuō)，兩個(gè)對(duì)象（向量）x和y之間的Mahalanobis距離定義為：

如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!14/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!其中是數(shù)據(jù)協(xié)方差矩陣的逆。注意，協(xié)方差矩陣是這樣的矩陣，它的第ij個(gè)元素是第i個(gè)和第j個(gè)屬性的協(xié)方差，由公式（2-11）定義。例

在圖2-19中有1000個(gè)點(diǎn)，其x屬性和y屬性的相關(guān)度為0.6。在橢圓長(zhǎng)軸兩端的兩個(gè)大點(diǎn)之間的歐幾里得距離為14.7，但Mahalanobis距離僅為6。實(shí)踐中，計(jì)算Mahalanobis距離的費(fèi)用昂貴，但是對(duì)于其屬性相關(guān)的對(duì)象來(lái)說(shuō)是值得的。如果屬性相對(duì)來(lái)說(shuō)不相關(guān)，只是具有不同的值域，則只需要對(duì)變量進(jìn)行標(biāo)準(zhǔn)化就足夠了。

圖2-19

二維點(diǎn)的集合。兩個(gè)大點(diǎn)代表的點(diǎn)之間的Mahalanobis距

離為6，它們的歐幾里得距離為14.7

2.組合異種屬性的相似度前面的相似度定義所基于的方法都假定所有屬性具有相同類型。當(dāng)屬性具有不同類型時(shí)，就需要更一般的方法。直截了當(dāng)?shù)姆椒ㄊ鞘褂帽?-7分別計(jì)算出每個(gè)屬性之間的相似度，然后使用一種導(dǎo)致0和1之間相似度的方法組合這些相似度?？傁嗨贫纫话愣x為所有屬性相似度的平均值。不幸的是，如果某些屬性是非對(duì)稱屬性，這種方法效果不好。例如，如果所有的屬性都是非對(duì)稱的二元屬性，則相似性度量先歸結(jié)為簡(jiǎn)單匹配系數(shù)--一種對(duì)于二元非對(duì)稱屬性并不合適的度量。處理該問(wèn)題的最簡(jiǎn)單方法是：如果兩個(gè)對(duì)象在非對(duì)稱屬性上的值都是0，則在計(jì)算對(duì)象相似度時(shí)忽略它們。類似的方法也能很好地處理遺漏值。如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!16/21如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!概括地說(shuō)，算法2.1可以有效地計(jì)算具有不同類型屬性的兩個(gè)對(duì)象x和y之間的相似度。修改該過(guò)程可以很輕松地處理相異度。

3.使用權(quán)值在前面的大部分討論中，所有的屬性在計(jì)算鄰近度時(shí)都會(huì)被同等對(duì)待。但是，當(dāng)