相似度的計(jì)算

1、相似度計(jì)算1 相似度的計(jì)算簡(jiǎn)介 關(guān)于相似度的計(jì)算，現(xiàn)有的幾種基本方法都是基于向量（Vector）的，其實(shí)也就是計(jì)算兩個(gè)向量的距離，距離越近相似度越大。在推薦的場(chǎng)景中，在用戶-物品偏好的二維矩陣中，我們可以將一個(gè)用戶對(duì)所有物品的偏好作為一個(gè)向量來計(jì)算用戶之間的相似度，或者將所有用戶對(duì)某個(gè)物品的偏好作為一個(gè)向量來計(jì)算物品 之間的相似度。下面我們?cè)敿?xì)介紹幾種常用的相似度計(jì)算方法：1.1 皮爾遜相關(guān)系數(shù)（Pearson Correlation Coefficient）皮爾遜相關(guān)系數(shù)一般用于計(jì)算兩個(gè)定距變量間聯(lián)系的緊密程度，它的取值在 -1，+1 之間。sx, sy是 x 和 y 的樣品標(biāo)準(zhǔn)偏差。類名：

2、PearsonCorrelationSimilarity 原理：用來反映兩個(gè)變量線性相關(guān)程度的統(tǒng)計(jì)量 范圍：-1,1，絕對(duì)值越大，說明相關(guān)性越強(qiáng)，負(fù)相關(guān)對(duì)于推薦的意義小。 說明：1、 不考慮重疊的數(shù)量；2、 如果只有一項(xiàng)重疊，無法計(jì)算相似性（計(jì)算過程被除數(shù)有n-1）；3、 如果重疊的值都相等，也無法計(jì)算相似性（標(biāo)準(zhǔn)差為0，做除數(shù)）。 該相似度并不是最好的選擇，也不是最壞的選擇，只是因?yàn)槠淙菀桌斫?，在早期研究中?jīng)常被提起。使用Pearson線性相關(guān)系數(shù)必須假設(shè)數(shù)據(jù)是成對(duì)地從正態(tài)分布中取得的，并且數(shù)據(jù)至少在邏輯范疇內(nèi)必須是等間距的數(shù)據(jù)。Mahout中，為皮爾森相關(guān)計(jì)算提供了一個(gè)擴(kuò)展，通過增加一個(gè)枚

3、舉類型（Weighting）的參數(shù)來使得重疊數(shù)也成為計(jì)算相似度的影響因子。1.2 歐幾里德距離（Euclidean Distance）最初用于計(jì)算歐幾里德空間中兩個(gè)點(diǎn)的距離，假設(shè) x，y 是 n 維空間的兩個(gè)點(diǎn)，它們之間的歐幾里德距離是：可以看出，當(dāng) n=2 時(shí)，歐幾里德距離就是平面上兩個(gè)點(diǎn)的距離。當(dāng)用歐幾里德距離表示相似度，一般采用以下公式進(jìn)行轉(zhuǎn)換：距離越小，相似度越大。類名：EuclideanDistanceSimilarity 原理：利用歐式距離d定義的相似度s，s=1 / (1+d)。 范圍：0,1，值越大，說明d越小，也就是距離越近，則相似度越大。 說明：同皮爾森相似度一樣，該相似度

4、也沒有考慮重疊數(shù)對(duì)結(jié)果的影響，同樣地，Mahout通過增加一個(gè)枚舉類型（Weighting）的參數(shù)來使得重疊數(shù)也成為計(jì)算相似度的影響因子。1.3 Cosine 相似度（Cosine Similarity）Cosine 相似度被廣泛應(yīng)用于計(jì)算文檔數(shù)據(jù)的相似度：類名： UncenteredCosineSimilarity 原理：多維空間兩點(diǎn)與所設(shè)定的點(diǎn)形成夾角的余弦值。 范圍：-1,1，值越大，說明夾角越大，兩點(diǎn)相距就越遠(yuǎn)，相似度就越小。 說明：在數(shù)學(xué)表達(dá)中，如果對(duì)兩個(gè)項(xiàng)的屬性進(jìn)行了數(shù)據(jù)中心化，計(jì)算出來的余弦相似度和皮爾森相似度是一樣的，在mahout中，實(shí)現(xiàn)了數(shù)據(jù)中心化的過程，所以皮爾森相似度值

5、也是數(shù)據(jù)中心化后的余弦相似度。另外在新版本中，Mahout提供了UncenteredCosineSimilarity類作為計(jì)算非中心化數(shù)據(jù)的余弦相似度。1.4 Spearman秩相關(guān)系數(shù)-Spearman Correlation類名：SpearmanCorrelationSimilarity 原理：Spearman秩相關(guān)系數(shù)通常被認(rèn)為是排列后的變量之間的Pearson線性相關(guān)系數(shù)。 范圍：-1.0,1.0，當(dāng)一致時(shí)為1.0，不一致時(shí)為-1.0。 說明：計(jì)算非常慢，有大量排序。針對(duì)推薦系統(tǒng)中的數(shù)據(jù)集來講，用Spearman秩相關(guān)系數(shù)作為相似度量是不合適的。1.5 Tanimoto 系數(shù)（Tani

6、moto Coefficient）Tanimoto 系數(shù)也稱為 Jaccard 系數(shù)，是 Cosine 相似度的擴(kuò)展，也多用于計(jì)算文檔數(shù)據(jù)的相似度：類名：TanimotoCoefficientSimilarity 原理：又名廣義Jaccard系數(shù)，是對(duì)Jaccard系數(shù)的擴(kuò)展，等式為 范圍：0,1，完全重疊時(shí)為1，無重疊項(xiàng)時(shí)為0，越接近1說明越相似。 說明：處理無打分的偏好數(shù)據(jù)。1.6 對(duì)數(shù)似然相似度類名：LogLikelihoodSimilarity 原理：重疊的個(gè)數(shù)，不重疊的個(gè)數(shù)，都沒有的個(gè)數(shù) 說明：處理無打分的偏好數(shù)據(jù)，比Tanimoto系數(shù)的計(jì)算方法更為智能。1.7 曼哈頓距離類名：C

7、ityBlockSimilarity 原理：曼哈頓距離的實(shí)現(xiàn)，同歐式距離相似，都是用于多維數(shù)據(jù)空間距離的測(cè)度 范圍：0,1，同歐式距離一致，值越小，說明距離值越大，相似度越大。 說明：比歐式距離計(jì)算量少，性能相對(duì)高。2 各相似度計(jì)算方法優(yōu)缺點(diǎn)分析2.1 基于皮爾森相關(guān)性的相似度 Pearson correlation-based similarity皮爾森相關(guān)系數(shù)反應(yīng)了兩個(gè)變量之間的線性相關(guān)程度，它的取值在-1, 1之間。當(dāng)兩個(gè)變量的線性關(guān)系增強(qiáng)時(shí)，相關(guān)系數(shù)趨于1或-1；當(dāng)一個(gè)變量增大，另一個(gè)變量也增大時(shí)，表明它們之間是正相關(guān)的，相關(guān)系數(shù)大于0；如果一個(gè)變量增大，另一個(gè)變量卻減小，表明它們之間

8、是負(fù)相關(guān)的，相關(guān)系數(shù)小于0；如果相關(guān)系數(shù)等于0，表明它們之間不存在線性相關(guān)關(guān)系。用數(shù)學(xué)公式表示，皮爾森相關(guān)系數(shù)等于兩個(gè)變量的協(xié)方差除于兩個(gè)變量的標(biāo)準(zhǔn)差。協(xié)方差（Covariance）：在概率論和統(tǒng)計(jì)學(xué)中用于衡量?jī)蓚€(gè)變量的總體誤差。如果兩個(gè)變量的變化趨于一致，也就是說如果其中一個(gè)大于自身的期望值，另一個(gè)也大于自身的期望值，那么兩個(gè)變量之間的協(xié)方差就是正值；如果兩個(gè)變量的變化趨勢(shì)相反，則協(xié)方差為負(fù)值。其中u表示X的期望E(X), v表示Y的期望E(Y)。標(biāo)準(zhǔn)差（Standard Deviation）：方差(Variance)：在概率論和統(tǒng)計(jì)學(xué)中，一個(gè)隨機(jī)變量的方差表述的是它的離散程度，也就是該變量

9、與期望值的距離即方差等于誤差的平方和的期望，基于皮爾森相關(guān)系數(shù)的相似度有兩個(gè)缺點(diǎn)：(1) 沒有考慮用戶間重疊的評(píng)分項(xiàng)數(shù)量對(duì)相似度的影響；(2) 如果兩個(gè)用戶之間只有一個(gè)共同的評(píng)分項(xiàng)，相似度也不能被計(jì)算。上表中，行表示用戶（15）對(duì)項(xiàng)目（101103）的一些評(píng)分值。直觀來看，User1和User5用3個(gè)共同的評(píng)分項(xiàng)，并且給出的評(píng)分值差也不大，按理他們之間的相似度應(yīng)該比User1和User4之間的相似度要高，可是User1和User4有一個(gè)更高的相似度1。例子：同樣的場(chǎng)景在現(xiàn)實(shí)生活中也經(jīng)常發(fā)生，比如兩個(gè)用戶共同觀看了200部電影，雖然不一定給出相同或完全相近的評(píng)分，他們之間的相似度也應(yīng)該比另一位只

10、觀看了2部相同電影的相似度高吧！但事實(shí)并不如此，如果對(duì)這兩部電影，兩個(gè)用戶給出的相似度相同或很相近，通過皮爾森相關(guān)性計(jì)算出的相似度會(huì)明顯大于觀看了相同的200部電影的用戶之間的相似度。Mahout對(duì)基于皮爾森相關(guān)系數(shù)的相似度給出了實(shí)現(xiàn)，它依賴一個(gè)DataModel作為輸入。同時(shí)，Mahout還針對(duì)缺點(diǎn)(1)進(jìn)行了優(yōu)化，只需要在構(gòu)造PearsonCorrelationSimilarity時(shí)多傳入一個(gè)Weighting.WEIGHTED參數(shù)，就能使有更多相同評(píng)分項(xiàng)目的用戶之間的相似度更趨近于1或-1。java ：1. UserSimilarity similarity1 = new Pearson

11、CorrelationSimilarity(model); 2. double value1 = similarity1.userSimilarity(1, 4);3.double value2= similarity1.userSimilarity(1, 5); 4.UserSimilarity similarity2 = new PearsonCorrelationSimilarity(model, Weighting.WEIGHTED); 5. double value3 = similarity1.userSimilarity(1, 4);6.double value4 = simil

12、arity2.userSimilarity(1, 5); 結(jié)果：Similarity of User1 and User4:0.9999999999999998Similarity of User1 and User5: Similarity of User1 and User4 with weighting: 0.9999999999999999Similarity of User1 and User5 with weighting: 0.9862277956307672.2 基于歐幾里德距離的相似度 Euclidean Distance-based Similarity歐幾里德距離計(jì)算相似

13、度是所有相似度計(jì)算里面最簡(jiǎn)單、最易理解的方法。它以經(jīng)過人們一致評(píng)價(jià)的物品為坐標(biāo)軸，然后將參與評(píng)價(jià)的人繪制到坐標(biāo)系上，并計(jì)算他們彼此之間的直線距離。圖中用戶A和用戶B分別對(duì)項(xiàng)目X、Y進(jìn)行了評(píng)分。用戶A對(duì)項(xiàng)目X的評(píng)分為1.8，對(duì)項(xiàng)目Y的評(píng)分為4，表示到坐標(biāo)系中為坐標(biāo)點(diǎn)A(1.8, 4)；同樣用戶B對(duì)項(xiàng)目X、Y的評(píng)分表示為坐標(biāo)點(diǎn)B(4.5, 2.5)，因此他們之間的歐幾里德距離（直線距離）為：計(jì)算出來的歐幾里德距離是一個(gè)大于0的數(shù)，為了使其更能體現(xiàn)用戶之間的相似度，可以把它規(guī)約到(0, 1之間，具體做法為：1 / (1 + d)。參見上表。只要至少有一個(gè)共同評(píng)分項(xiàng)，就能用歐幾里德距離計(jì)算相似度；如果

14、沒有共同評(píng)分項(xiàng)，那么歐幾里德距離也就失去了作用。其實(shí)照常理理解，如果沒有共同評(píng)分項(xiàng)，那么意味著這兩個(gè)用戶或物品根本不相似。2.3 余弦相似度 Cosine Similarity余弦相似度用向量空間中兩個(gè)向量夾角的余弦值作為衡量?jī)蓚€(gè)個(gè)體間差異的大小。相比距離度量，余弦相似度更加注重兩個(gè)向量在方向上的差異，而非距離或長(zhǎng)度上。與歐幾里德距離類似，基于余弦相似度的計(jì)算方法也是把用戶的喜好作為n-維坐標(biāo)系中的一個(gè)點(diǎn)，通過連接這個(gè)點(diǎn)與坐標(biāo)系的原點(diǎn)構(gòu)成一條直線（向量），兩個(gè)用戶之間的相似度值就是兩條直線（向量）間夾角的余弦值。因?yàn)檫B接代表用戶評(píng)分的點(diǎn)與原點(diǎn)的直線都會(huì)相交于原點(diǎn)，夾角越小代表兩個(gè)用戶越相似，夾

15、角越大代表兩個(gè)用戶的相似度越小。同時(shí)在三角系數(shù)中，角的余弦值是在-1, 1之間的，0度角的余弦值是1，180角的余弦值是-1。借助三維坐標(biāo)系來看下歐氏距離和余弦相似度的區(qū)別：從圖上可以看出距離度量衡量的是空間各點(diǎn)間的絕對(duì)距離，跟各個(gè)點(diǎn)所在的位置坐標(biāo)（即個(gè)體特征維度的數(shù)值）直接相關(guān)；而余弦相似度衡量的是空間向量的夾角，更加的是體現(xiàn)在方向上的差異，而不是位置。如果保持A點(diǎn)的位置不變，B點(diǎn)朝原方向遠(yuǎn)離坐標(biāo)軸原點(diǎn)，那么這個(gè)時(shí)候余弦相似度cos是保持不變的，因?yàn)閵A角不變，而A、B兩點(diǎn)的距離顯然在發(fā)生改變，這就是歐氏距離和余弦相似度的不同之處。余弦相似度的特點(diǎn)：1. 對(duì)用戶的絕對(duì)的數(shù)值不敏感2. 計(jì)算時(shí)不

16、考慮用戶之間的共同評(píng)分項(xiàng)數(shù)量，即使僅僅有極少相同評(píng)分項(xiàng)，也有可能獲得很大的相似度結(jié)果，例如上表中的uer3與user1.3. 只要各個(gè)評(píng)分項(xiàng)之間越趨向于對(duì)應(yīng)成比例，而不論數(shù)值差異如何，則相似度越趨近于1.000.根據(jù)歐氏距離和余弦相似度各自的計(jì)算方式和衡量特征，分別適用于不同的數(shù)據(jù)分析模型：歐氏距離能夠體現(xiàn)個(gè)體數(shù)值特征的絕對(duì)差異，所以更多的用于需要從維度的數(shù)值大小中體現(xiàn)差異的分析，如使用用戶行為指標(biāo)分析用戶價(jià)值的相似度或差異；而余弦相似度更多的是從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏感，更多的用于使用用戶對(duì)內(nèi)容評(píng)分來區(qū)分用興趣的相似度和差異，同時(shí)修正了用戶間可能存在的度量標(biāo)準(zhǔn)不統(tǒng)一的問題（因?yàn)橛?/p>

17、弦相似度對(duì)絕對(duì)數(shù)值不敏感）。注：根據(jù)以上的分析，余弦相似度更適合于這樣一類數(shù)據(jù)的挖掘工作：1. 計(jì)算結(jié)果對(duì)用戶數(shù)據(jù)絕對(duì)值不敏感，例如在描述用戶的興趣、喜好、或用于情感分析時(shí)。2. 用戶數(shù)據(jù)中的評(píng)分值其實(shí)是用戶主觀的評(píng)分結(jié)果，換言之，每個(gè)用戶的評(píng)價(jià)標(biāo)準(zhǔn)是不一致的，有一些對(duì)于“好的”界定標(biāo)準(zhǔn)更為苛刻，而另一些則對(duì)于“好”、“不好”的界定則更為寬容。這種情況下，用余弦相似度來計(jì)算用戶之間的相似度或差異，可以弱化度量標(biāo)準(zhǔn)不統(tǒng)一這一因素。Eg:模糊度量標(biāo)準(zhǔn)“很不好”“不好”“較好”“很好”User1的評(píng)價(jià)標(biāo)準(zhǔn)1.02.03.54.0User2的評(píng)價(jià)標(biāo)準(zhǔn)2.03.04.05.0User3的評(píng)價(jià)標(biāo)準(zhǔn)1.02

18、.03.04.0上表中user1和user3的評(píng)價(jià)標(biāo)準(zhǔn)很相似，都是較為“苛刻的”，user2，相比之下顯得更為“寬容”。ItemItem001Item002Item003User1的評(píng)價(jià)2.04.03.5User2的評(píng)價(jià)3.55.04.5User3的評(píng)價(jià)2.03.54.0從數(shù)值上看，顯然user1和user3的評(píng)分值更為接近，似乎相似度更高；而user2的評(píng)分值相較user1差異較大。 java:1. UserSimilarity similarity1 = new UncenteredCosineSimilarity (model); 2. double value1 = similarit

19、y1.userSimilarity(1, 2);3. double value2= similarity1.userSimilarity(1, 3);4.UserSimilarity similarity2= new EuclideanDistanceSimilarity (model); 5. double value3 = similarity2.userSimilarity(1, 2);6. double value4= similarity2.userSimilarity(1, 3);計(jì)算結(jié)果：Similarity of User1 and User2 using cos: 0.992

20、7441515592047Similarity of User1 and User3 using cos:Similarity of User1 and User2 using Euc：Similarity of User1 and User3 using Euc：但是，余弦相似度的計(jì)算則揭示了：User2 與user1之間的相似度 > User3與user1之間的相似度。但如果用歐氏距離想速度則：User2 與user1之間的相似度 < User3與user1。2.4 調(diào)整余弦相似度 Adjusted Cosine Similarity在余弦相似度的介紹中說到：余弦相似度更多的是

21、從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏感。因此沒法衡量每個(gè)維數(shù)值的差異，會(huì)導(dǎo)致這樣一個(gè)情況：比如用戶對(duì)內(nèi)容評(píng)分，5分制，X和Y兩個(gè)用戶對(duì)兩個(gè)內(nèi)容的評(píng)分分別為(1,2)和(4,5)，使用余弦相似度得出的結(jié)果是0.98，兩者極為相似，但從評(píng)分上看X似乎不喜歡這兩個(gè)內(nèi)容，而Y比較喜歡，余弦相似度對(duì)數(shù)值的不敏感導(dǎo)致了結(jié)果的誤差，需要修正這種不合理性，就出現(xiàn)了調(diào)整余弦相似度，即所有維度上的數(shù)值都減去一個(gè)均值，比如X和Y的評(píng)分均值都是3，那么調(diào)整后為(-2,-1)和(1,2)，再用余弦相似度計(jì)算，得到-0.8，相似度為負(fù)值并且差異不小，但顯然更加符合現(xiàn)實(shí)。2.5 斯皮爾曼相關(guān) Spearman Correl

22、ation斯皮爾曼相關(guān)性可以理解為是排列后（Rank）用戶喜好值之間的Pearson相關(guān)度。Mahout in Action中有這樣的解釋：假設(shè)對(duì)于每個(gè)用戶，我們找到他最不喜歡的物品，重寫他的評(píng)分值為“1”；然后找到下一個(gè)最不喜歡的物品，重寫評(píng)分值為“2”，依此類推。然后我們對(duì)這些轉(zhuǎn)換后的值求Pearson相關(guān)系數(shù)，這就是Spearman相關(guān)系數(shù)。斯皮爾曼相關(guān)度的計(jì)算舍棄了一些重要信息，即真實(shí)的評(píng)分值。但它保留了用戶喜好值的本質(zhì)特性排序（ordering），它是建立在排序（或等級(jí)，Rank）的基礎(chǔ)上計(jì)算的?；仡櫱懊姹碇蠻ser15對(duì)Item101103的喜好（評(píng)分）值，通過斯皮爾曼相關(guān)系數(shù)計(jì)算

23、出的相似度為：我們發(fā)現(xiàn)，計(jì)算出來的相似度值要么是1，要么是-1，因?yàn)檫@依賴于用戶的喜好值和User1的喜好值是否趨于“一致變化”還是呈“相反趨勢(shì)變化"。Mahout對(duì)斯皮爾曼相關(guān)系數(shù)給出了實(shí)現(xiàn)，具體可參考SpearmanCorrelationSimilarity，它的執(zhí)行效率不是非常高，因?yàn)樗蛊柭嚓P(guān)性的計(jì)算需要花時(shí)間計(jì)算并存儲(chǔ)喜好值的一個(gè)排序（Ranks），具體時(shí)間取決于數(shù)據(jù)的數(shù)量級(jí)大小。正因?yàn)檫@樣，斯皮爾曼相關(guān)系數(shù)一般用于學(xué)術(shù)研究或者是小規(guī)模的計(jì)算。java :UserSimilarity similarity1 = new SpearmanCorrelationSimilar

24、ity(model); / construct a Spearman Correlation-based Similarity 結(jié)果：User1 to User1 : 1.0User2 to User1 : -1.0User3 to User1 : NaNUser4 to User1 : 1.0User4 to User1 : 1.0考慮到Spearman Correlation的效率，可以把SpearmanCorrelationSimilarity包裝一層Cache，具體做法為：java:UserSimilarity similarity2 = new CachingUserSimilari

25、ty (new SpearmanCorrelationSimilarity (model), model); 這樣，每次計(jì)算的結(jié)果會(huì)直接放入Cache，下一次計(jì)算的時(shí)候可以立即得到結(jié)果，而不是重新再計(jì)算一次。Spearman相關(guān)系數(shù)的特點(diǎn)：1. Spearman相關(guān)是根據(jù)等級(jí)資料研究?jī)蓚€(gè)變量間相關(guān)關(guān)系的方法。它是依據(jù)兩列成對(duì)等級(jí)的各對(duì)等級(jí)數(shù)之差來進(jìn)行計(jì)算的，所以又稱為“等級(jí)差數(shù)法”2. Spearman相關(guān)系數(shù)對(duì)原始變量的分布不做要求，屬于非參數(shù)統(tǒng)計(jì)方法。因此它的適用范圍比Pearson相關(guān)系數(shù)要廣的多。即使原始數(shù)據(jù)是等級(jí)資料也可以計(jì)算Spearman相關(guān)系數(shù)。對(duì)于服從Pearson相關(guān)系數(shù)的數(shù)據(jù)也可以計(jì)算Spearman相關(guān)系數(shù)，3. 統(tǒng)計(jì)效能比Pearson相關(guān)系數(shù)要低一些（不容易檢測(cè)出兩者事實(shí)上存在的相關(guān)關(guān)系）。4. spearman只要兩個(gè)變量的觀測(cè)值是成對(duì)的等級(jí)評(píng)定資料，