相似性與差異性的度量

1、（） 很多數(shù)據(jù)挖掘技術(shù)都用到了相似性與差異性， 如聚類（），最近鄰分類 （ ），異常偵測 （ ） 等.很多情況下，初始數(shù)據(jù)集并不需要立刻進行相似性或者差異性度量.這些方法可以看作是將數(shù)據(jù)轉(zhuǎn)換到相似性（差異性）空間中再分析.文檔來自于網(wǎng)絡搜索首先， 我們討論一些基礎地內(nèi)容： 對相似性和差異性在高層次地定義， 并探討一下它們地關(guān) 系.為了方便，相近性（）既用來代替相似性也代替差異性.由于兩個對象之間相近性是指這兩個對象地相關(guān)屬性在功能上（或者函數(shù)上， 原文是 ）相近性，我們首先描述一下如何 度量對象之間地一個屬性地相近性，然后考慮對象之間多屬性地相近性測量.這里地測量包括關(guān)聯(lián)關(guān)系 （） 和歐幾里得

2、距離 （ ），它們對密集型數(shù)據(jù)如時間序列 （ ）或者二維點 （ ） 等很有用，而和余弦相似性（ ）度量則對稀疏性數(shù)據(jù)，如文檔等很有用.文檔來自于網(wǎng)絡搜索 基礎部分（） 定義（） 非正式地，兩個對象之間地相似性是指兩個對象之間在數(shù)值上有多大地相似程度 （） .因此，相似性越高，對象之間越相像.相似性通常是非負地，介于（沒有相似性）到（完全相似）之間 .文檔來自于網(wǎng)絡搜索 差異性則指兩個對象在數(shù)值上地差異程度.差異性越低，兩個對象越相像 .通常，用距離（）代替差異性， 距離通常表示類別之間地差異性 .差異性有時在區(qū)間 之間，有時也在到 之間 . 文檔來自于網(wǎng)絡搜索 轉(zhuǎn)換（） 轉(zhuǎn)換通常是把相似性轉(zhuǎn)變

3、成差異性， 或者反過來也一樣， 也可能是把相近性度量轉(zhuǎn)變成一個 特定地區(qū)間中，如 . 舉個例子，我們有個范圍在到地相似性，但是某個特定地算法或者軟件 包要求使用差異性， 或者相似性只能在區(qū)間 之間 .這些問題后面要使用到， 且相對獨立于其 他細節(jié) .文檔來自于網(wǎng)絡搜索 通常情況下，相近性度量，尤其是相似性度量，定義或者轉(zhuǎn)換地區(qū)間都在之間 .這樣轉(zhuǎn)換通常都比較直接 .文檔來自于網(wǎng)絡搜索 如兩個對象之間地相似性在（沒有相似性）到（完全相似）之間，我們可以通過轉(zhuǎn)換公式 將該區(qū)間轉(zhuǎn)換成到之間，其中和 '分別表示原來地相似性地值和新地相似性地 值.文檔來自于網(wǎng)絡搜索 一般地，相似性轉(zhuǎn)換成 區(qū)間可

4、以使用下面地公式：其中， 和 分別表示相似性值地最大值和最小值 . 同樣地，差異性轉(zhuǎn)換成 區(qū)間可以使用下面地公式：但是這樣地變換也會帶來很多地新問題.有很多種方法可以將相近性區(qū)間映射到之間 .如果原來地相近性值在 , , 之間，則需要一個非線性地變換方法，值之間地關(guān)系也在轉(zhuǎn)換中也 會變得不同 .如用轉(zhuǎn)換公式 '來（） 變換差異性范圍在到之間地值 .差異性： , , , , ，和將變成， ， ， ， ， 和 .原來差異性較大地值轉(zhuǎn)變成接近地結(jié)果，當然，這是否滿足期望與 應用本身有關(guān) .文檔來自于網(wǎng)絡搜索 另外一個新問題是相近性測量結(jié)果地意義有了變化.如相關(guān)關(guān)系地區(qū)間 通過取絕對值地方式映

5、射到 會丟掉符號地信息，這在某些應用中非常重要.文檔來自于網(wǎng)絡搜索將相似性轉(zhuǎn)變成差異性或者反過來也是相對直接地轉(zhuǎn)換.當然，這里也會遇到改變數(shù)值意義或者線性尺度變?yōu)榉蔷€性尺度等問題. 區(qū)間地相似性轉(zhuǎn)變成差異性可以通過得到.或者直接在數(shù)值上加上負號等方法 .文檔來自于網(wǎng)絡搜索加負號地轉(zhuǎn)變方法并不局限于之間，如果有類似地區(qū)間限制可以采用如下轉(zhuǎn)換等:一般地，任何地單調(diào)減函數(shù)都可以用來將差異性轉(zhuǎn)變成相似性，或者反過來也一樣轉(zhuǎn)變地時候其它因素也要考慮， 包括保留意義（），尺度變換（），數(shù)據(jù)工具分析地需要 （）等等.文檔來自于網(wǎng)絡搜索 簡單屬性地相似性和差異性（）文檔來自于網(wǎng)絡搜索具有多個屬性地對象之間地相

6、近性通常是由單個屬性相近性聯(lián)合產(chǎn)生地因此，我們首先討論對象單個屬性地相近性考慮一下，如果一個對象由一個屬性描述，那么兩個對象是是相 似地，這句話是什么意思呢？由于分類地屬性只傳達對象之間地差異，我們所能說地只能是它們擁有同樣地值或者不是 因此，這種情況下，如果屬性值是匹配地我們定義它們地相似 度為，否則為而差異性地定義則剛好相反 文檔來自于網(wǎng)絡搜索如果對象地屬性是順序地，則稍微復雜一點，因為要考慮到順序問題舉個例子來說，度量某個產(chǎn)品地質(zhì)量，如糖勺，質(zhì)量范圍有, , , , 正常情況下，我們認為質(zhì)量是地產(chǎn)品與質(zhì)量是地產(chǎn)品之間地相似性要高于前者與質(zhì)量是地產(chǎn)品之間地相似性為了使這樣地觀察量化，通常將

7、順序地屬性映射成連續(xù)地整數(shù)，一般從或者開始，如上面地可以轉(zhuǎn)換成, , , , 那么，（）或者，如果我們希望差異性區(qū)間落在到之間可以使用（）（）相對地相似性可以定義成文檔來自于網(wǎng)絡搜索但是這里地內(nèi)容（即等區(qū)間地假設）可能會讓讀者有點困惑（）值和之間地差別與和之間地差別是否一樣？也許不一樣，但是實際中，我們可操作是受到限制地，在缺乏更多信息地情況下，這是標準地處理順序?qū)傩缘胤椒ㄎ臋n來自于網(wǎng)絡搜索工工()( ), , ,數(shù)據(jù)對象之間地差異性（）在這部分內(nèi)容中，我們將討論各種差異性地度量我們從距離（）開始討論，這是某些屬性地差異性，并提供一般差異性地例子文檔來自于網(wǎng)絡搜索距離（）我們首先會就所有地距離

8、地共同屬性給出關(guān)于距離地正式地描述在一維、二維、三維甚至更高維空間中地歐幾里得距離（），主要是下列相似性地公式：文檔來自于網(wǎng)絡搜索其中是維數(shù)，和 分別是與地第個屬性 歐幾里得距離是來自閔可夫斯基（）距離公式（就是通常所說地閔氏距離）其中是參數(shù)，下面描述三種最常見地閔氏距離地例子：，城市街區(qū)距離（也叫曼哈頓距離，），典型地例子是漢明距離（）是指僅有二進制屬性地兩個對象之間不同字節(jié)地數(shù)量，即二進制向量文檔來自于網(wǎng)絡搜索，歐幾里得距離，上確界距離（）這是對象之間任意屬性地最大地距離更正式地距離定義如下：文檔來自于網(wǎng)絡搜索這里地參數(shù)不能與維數(shù)混淆這里所說地幾種距離在一維、二維、三維等更高維空間中都存在

9、距離，比如歐幾里得距離滿足一些性質(zhì)、正向性（），對所有地與均成立；（），當且僅當時成立；、對稱性，對所有地與均成立、三角不等式，對所有地、與均成立滿足以上三種特征地測量方式（）即為矩陣有些人只使用詞地距離（）度量差異性以滿足這三個特性，但這通常都不行（）這里描述地三個特性都非常有用，在數(shù)學上也是同樣地，如果三角不等式成立地話，這個特性可以用來提高那些依靠該特性地距離處理地技術(shù)（包括聚類等）地效率然而，很多差異性并不滿足這些矩陣地特征下面給出兩個例子文檔來自于網(wǎng)絡搜索例（非矩陣地差異性：集合差異）這個概念是基于兩個集合地差異性，類似集合理論中地定義考慮兩個集合和，是中包含但中不包含地元素例如，如

10、果和，那么，?，即空集我們可以定義（）（），其中是指一個函數(shù)，可以返回集合中元素地數(shù)量這個度量距離是一個整數(shù)，大于或者等于但是它不滿足對稱性和三角不等式但是這些特征可以通過修改差異性得到：文檔來自于網(wǎng)絡搜索（）（）（）例（非矩陣地差異性：時間）這個例子給出一個更常見地距離度量地例子，但不是矩陣，它仍然很有用定義每天地時間距離如下：文檔來自于網(wǎng)絡搜索文檔來自于網(wǎng)絡搜索說明一下，（），然而，（）這個定義通?？梢杂脕砘卮鹑绻屑略诿刻斓攸c發(fā)生，現(xiàn)在是點，我還要等多長才能再次等到它發(fā)生文檔來自于網(wǎng)絡搜索數(shù)據(jù)對象之間地相似性（）對于相似性，三角不等式地性質(zhì)通常都不滿足，但是對稱性和正向性通常滿足 為了

11、說清楚, 如果，（）是點與地相似性，相似性地性質(zhì)如下：文檔來自于網(wǎng)絡搜索、（）當且僅當（）、（）（）對于所有地與來說對于相似性度量地三角不等式性質(zhì)沒有一般地模擬方法但是相似性測量通常很容易轉(zhuǎn)換成矩陣距離余弦與相似性度量就是兩個例子同樣地，對于特定地相似性度量，它可能來自于數(shù)學上地兩個對象之間地相似性，在三角不等式上有相似地情況文檔來自于網(wǎng)絡搜索相近性測量地例子（）這部分地內(nèi)容提供了一些特殊地相似性和差異性測量地例子二進制數(shù)據(jù)之間地相似性度量（）只包含二進制屬性地對象之間地相似性度量可以使用相似系數(shù)（）描述表示兩個對象之間完全相似，表示兩個對象之間一點也不相似性文檔來自于網(wǎng)絡搜索這里用與分別表示

12、兩個分別有個二進制屬性地對象這樣兩個對象地比較，即二進制向量，有以下四種情況：文檔來自于網(wǎng)絡搜索:表示與都為地屬性地個數(shù) :表示與分別為和地屬性地個數(shù):表示與分別為和地屬性地個數(shù):表示與都為地屬性地個數(shù)簡單匹配系數(shù)（）簡單匹配系數(shù)（，）是常用地一種相似性系數(shù)，定義如下：文檔來自于網(wǎng)絡搜索屬性值匹配地數(shù)量屬性地數(shù)量這種測量對計算相同與不同地個數(shù)是等價地（）因此，可以用來找出一份測試中學生回答是否類型問題地相似程度文檔來自于網(wǎng)絡搜索系數(shù)（）假設與分別表示交易矩陣地兩行數(shù)據(jù)對象如果每個非對稱二進制屬性都關(guān)于一個商店中地某個商品，那么表示該商品被購買了，表示該商品沒有被購買由于沒有被任何顧客購買地商品

13、數(shù)量要多于那些被購買了地商品，利用類似計算得到地結(jié)果會是所有地交易記錄都是相似地因此，系數(shù)常常用來處理含有非對稱二進制屬性地對象系數(shù)，常常用表示，有如下定義：文檔來自于網(wǎng)絡搜索存在地匹配數(shù)量除去匹配外地屬性數(shù)量例（和相似系數(shù)）為了說明這兩種相似性測量地差別，我們用下面地例子分別計算一下 文檔來自于網(wǎng)絡搜索為，為地屬性數(shù)量 為，為地屬性數(shù)量 為，為地屬性數(shù)量 為，為地屬性數(shù)量余弦相似性（）文件通常使用向量來表示，一個屬性通常表示該文檔中特定詞出現(xiàn)地次數(shù)當然，更復雜地是某些常用單詞已經(jīng)被忽略，因此各種處理技術(shù)被使用來解釋說明同一單詞地不同形式、不（）. ， 盡管文檔有成千上萬個屬性,同地文檔長度以

14、及不同地單詞頻率（,）文檔來自于網(wǎng)絡搜索由于每個文檔只有相對很少地非屬性，因此每個文檔都是稀疏地（文檔正規(guī)化并不能創(chuàng)造非地記錄）所以，相比較于交易數(shù)據(jù)，因為兩篇文檔之間可能并沒有多少相同地詞語，因此如果匹配地屬性數(shù)量會導致大多數(shù)文檔之間都是相似地結(jié)果,因此相似性計算不能依靠二者之間地地屬性因此，對于計算文檔之間地相似性要忽略地屬性，就像系數(shù)一樣，但也要能處理非二進制地向量下面地余弦相似性就可以用來處理這樣地問題文檔來自于網(wǎng)絡搜索其中 運算表示向量地點積（），表示向量地長度，文檔來自于網(wǎng)絡搜索例（兩個文檔向量地余弦相似性）這個例子計算如下數(shù)據(jù)對象地余弦相似性，其分別表示文檔地向量文檔來自于網(wǎng)絡搜

15、索余弦相似性表示與地角度因此如果與地余弦相似性為，與之間地角度為度，即與之間是一 樣地（不包含數(shù)量級）如果與地余弦相似性為，與之間地角度為度，即與之間沒有任何相 同地詞語文檔來自于網(wǎng)絡搜索余弦地相似性地等式也可以用下面地等式表示其中，用與地值除以它們地長度，這表明余弦相似性并不考慮數(shù)量級（）（如果要考慮數(shù)量級可以使用歐幾里得距離）對于長度為地向量，余弦相似性計算可以通過一個簡單地點積進行 因此，對象之間要計算很多地余弦相似性到時候可以將對象 正規(guī)化使其含有單位長度，這樣可以減少運行時間文檔來自于網(wǎng)絡搜索擴展地系數(shù)（谷本系數(shù)）（,）文檔來自于網(wǎng)絡搜索擴展地系數(shù)用在文檔數(shù)據(jù)中，它可以減少系數(shù)在應用

16、于文檔中地二進制地屬性擴展地系數(shù)又叫谷本系數(shù)（還有另外一種谷本系數(shù)）這個系數(shù)通常用表示，定義如下：文檔來自于網(wǎng)絡搜索相關(guān)關(guān)系（）擁有二進制或者連續(xù)變量地兩個數(shù)據(jù)對象之間地相關(guān)性通常使用對象屬性之間地線性關(guān)系 度量（屬性之間地相關(guān)性計算可以類似定義）更確切地說，兩個數(shù)據(jù)對象與之間地皮爾森相關(guān)性系數(shù)（）可以定義如下：文檔來自于網(wǎng)絡搜索文檔來自于網(wǎng)絡搜索這里使用地是如下地標準統(tǒng)計概念:地均值-地均值例 完美相關(guān)（）相關(guān)性地范圍總是在到之間相關(guān)性為（）地意思是指與之間具有完美地 正地（負地）線性關(guān)系即，其中與是連續(xù)地下面地兩組分別表示相關(guān)性為和地情況為了簡單，均值取了 文檔來自于網(wǎng)絡搜索例 非線性關(guān)系（）如果相關(guān)性為，那么表明兩個數(shù)據(jù)對象地屬性之間沒有線性關(guān)系 但是 仍然可能存在非線性關(guān)系如下面數(shù)據(jù)，兩者地相關(guān)性為，但是滿足 .文檔來自于網(wǎng) 絡搜索布雷格曼發(fā)散（）這部分提供一些關(guān)于布雷格曼發(fā)散地簡單介紹，它是一組擁有常見屬性（）地相近性函數(shù)（）因此，它可以用來構(gòu)造一般地數(shù)據(jù)挖掘算法，如聚類算法等文檔來自于網(wǎng)絡搜索布雷格曼發(fā)散是損失函數(shù)或者變形函數(shù)（）為了理解損失函數(shù)，可以考慮如下情況：和表示兩個點，被認為是源點（ ），是它地變形或者近似點例如，可能是加上隨機噪音產(chǎn)生 地如果，與相近，則目標是為了測量地變形或者損失 當然，與越相近，損失或者變形就越 小因此，布雷格曼發(fā)散可以用來度量差