數(shù)據(jù)挖掘：如何尋找相關(guān)項(xiàng)

數(shù)據(jù)科學(xué)家需要具備專業(yè)領(lǐng)域知識(shí)并研究相應(yīng)的算法以分析對(duì)應(yīng)的問題，而數(shù)據(jù)挖掘是其必須掌握的重要技術(shù)。以幫助創(chuàng)建推動(dòng)業(yè)務(wù)發(fā)展的相應(yīng)大數(shù)據(jù)產(chǎn)品和大數(shù)據(jù)解決方案。EMC最近的一項(xiàng)調(diào)查也證實(shí)了這點(diǎn)。調(diào)查結(jié)果顯示83%的人認(rèn)為大數(shù)據(jù)浪潮所催生的新技術(shù)增加了數(shù)據(jù)科學(xué)家的需求。本文將為您展示如何基于一個(gè)簡單的公式查找相關(guān)的項(xiàng)目。請(qǐng)注意，此項(xiàng)技術(shù)適用于所有的網(wǎng)站（如亞馬遜），以個(gè)性化用戶體驗(yàn)、提高轉(zhuǎn)換效率。

查找相關(guān)項(xiàng)問題

要想為一個(gè)特定的項(xiàng)目查找相關(guān)項(xiàng)，就必須首先為這兩個(gè)項(xiàng)目定義相關(guān)之處。而這些也正是你要解決的問題：

在博客上，你可能想以標(biāo)簽的形式分享文章，或者對(duì)比查看同一個(gè)人閱讀過的文章

亞馬遜站點(diǎn)被稱為“購買此商品的客戶還購買了”的部分

一個(gè)類似于IMDB（Internet Movie Database）的服務(wù)，可以根據(jù)用戶的評(píng)級(jí)，給出觀影指南建議

不論是標(biāo)簽、購買的商品還是觀看的電影，我們都要對(duì)其進(jìn)行分門別類。這里我們將采用標(biāo)簽的形式，因?yàn)樗芎唵?，而且其公式也適用于更復(fù)雜的情形。

以幾何關(guān)系重定義問題

現(xiàn)在以我的博客為例，來列舉一些標(biāo)簽：

1. [“API”, “Algorithms”, “Amazon”, “Android”, “Books”, “Browser”]

好，我們來看看在歐式空間幾何學(xué)中如何表示這些標(biāo)簽。

我們要排序或比較的每個(gè)項(xiàng)目在空間中以點(diǎn)表示，坐標(biāo)值（代表一個(gè)標(biāo)簽）為1（標(biāo)記）或者0（未標(biāo)記）。

因此，如果我們已經(jīng)獲取了一篇標(biāo)簽為“API”和“Browser”的文章，那么其關(guān)聯(lián)點(diǎn)是：

1. [ 1, 0, 0, 0, 0, 1 ]

現(xiàn)在這些坐標(biāo)可以表示其它含義。例如，他們可以代表用戶。如果在你的系統(tǒng)中有6個(gè)用戶，其中2個(gè)用戶對(duì)一篇文章分別評(píng)了3星和5星，那么你就可以針對(duì)此文章查看相關(guān)聯(lián)的點(diǎn)（請(qǐng)注意順序）：

1. [ 0, 3, 0, 0, 5, 0 ]

現(xiàn)在我們可以計(jì)算出相關(guān)矢量之間的夾角，以及這些點(diǎn)之間的距離。下面是它們?cè)诙S空間中的圖像：

歐式幾何空間距離

計(jì)算歐式幾何空間兩點(diǎn)之間距離的數(shù)學(xué)公式非常簡單。考慮相關(guān)兩點(diǎn)A、B之間的距離：

兩點(diǎn)之間的距離越近，它們的相關(guān)性越大。下面是Ruby代碼：

1. # Returns the Euclidean distance between 2 points
2. #
3. # Params:
4. #  – a, b: list of coordinates (float or integer)
5. #
6. def euclidean_distance(a, b)
7.   sq = a.zip(b).map{|a,b| (a – b) ** 2}
8.   Math.sqrt(sq.inject(0) {|s,c| s + c})
9. end
10. # Returns the associated point of our tags_set, relative to our
11. # tags_space.
12. #
13. # Params:
14. #  – tags_set: list of tags
15. #  – tags_space: _ordered_ list of tags
16. def tags_to_point(tags_set, tags_space)
17.   tags_space.map{|c| tags_set.member?(c) ? 1 : 0}
18. end
19. # Returns other_items sorted by similarity to this_item 
20. # (most relevant are first in the returned list)
21. #
22. # Params:
23. #  – items: list of hashes that have [:tags]
24. #  – by_these_tags: list of tags to compare with
25. def sort_by_similarity(items, by_these_tags)
26.   tags_space = by_these_tags + items.map{|x| x[:tags]}
27.   tags_space.flatten!.sort!.uniq!
28.   this_point = tags_to_point(by_these_tags, tags_space)
29.   other_points = items.map{|i|
30.     [i, tags_to_point(i[:tags], tags_space)]
31.   }
33.   similarities = other_points.map{|item, that_point|
34.     [item, euclidean_distance(this_point, that_point)]
35.   }
36.   sorted = similarities.sort {|a,b| a[1] <=> b[1]}
37.   return sorted.map{|point,s| point}
38. End

這是一些示例代碼，你可以直接復(fù)制運(yùn)行：

1. # SAMPLE DATA
3. all_articles = [
4.   {
5.    :article => “Data Mining: Finding Similar Items”,
6.    :tags => [“Algorithms”, “Programming”, “Mining”,
7.      “Python”, “Ruby”]
8.   },
9.   {
10.    :article => “Blogging Platform for Hackers”,
11.    :tags => [“Publishing”, “Server”, “Cloud”, “Heroku”,
12.      “Jekyll”, “GAE”]
13.   },
14.   {
15.    :article => “UX Tip: Don’t Hurt Me On Sign-Up”,
16.    :tags => [“Web”, “Design”, “UX”]
17.   },
18.   {
19.    :article => “Crawling the Android Marketplace”,
20.    :tags => [“Python”, “Android”, “Mining”,
21.      “Web”, “API”]
22.   }
23. ]
25. # SORTING these articles by similarity with an article 
26. # tagged with Publishing + Web + API
27. #
28. #
29. # The list is returned in this order:
30. #
31. # 1. article: Crawling the Android Marketplace
32. #    similarity: 2.0
33. #
34. # 2. article: “UX Tip: Don’t Hurt Me On Sign-Up”
35. #    similarity: 2.0
36. #
37. # 3. article: Blogging Platform for Hackers
38. #    similarity: 2.645751
39. #
40. # 4. article: “Data Mining: Finding Similar Items”
41. #    similarity: 2.828427
42. #
44. sorted = sort_by_similarity(
45.     all_articles, [‘Publishing’, ‘Web’, ‘API’])
47. require ‘yaml’
48. puts YAML.dump(sorted)

你是否留意到我們之前選擇的數(shù)據(jù)存在一個(gè)缺陷？前兩篇文章對(duì)于標(biāo)簽“[“Publishing”, “Web”, “API”]”有著相同的歐氏幾何空間距離。

為了更加形象化，我們來看看計(jì)算第一篇文章所用到的點(diǎn)：

1. [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
2. [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1]

只有四個(gè)坐標(biāo)值不同，我們?cè)賮砜纯吹诙恼滤玫降狞c(diǎn)：

1. [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
2. [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

與第一篇文章相同，也只有4個(gè)坐標(biāo)值不同。歐氏空間距離的度量取決于點(diǎn)之間的差異。這也許不太好，因?yàn)橄鄬?duì)平均值而言，有更多或更少標(biāo)簽的文章會(huì)處于不利地位。

余弦相似度

這種方法與之前的方法類似，但更關(guān)注相似性。下面是公式：

下面是Ruby代碼：

1. def dot_product(a, b)
2.   products = a.zip(b).map{|a, b| a * b}
3.   products.inject(0) {|s,p| s + p}
4. end
6. def magnitude(point)
7.   squares = point.map{|x| x ** 2}
8.   Math.sqrt(squares.inject(0) {|s, c| s + c})
9. end
11. # Returns the cosine of the angle between the vectors 
12. #associated with 2 points
13. #
14. # Params:
15. #  – a, b: list of coordinates (float or integer)
16. #
17. def cosine_similarity(a, b)
18.   dot_product(a, b) / (magnitude(a) * magnitude(b))
19. end

對(duì)于以上示例，我們對(duì)文章進(jìn)行分類得到：

1. – article: Crawling the Android Marketplace
2.   similarity: 0.5163977794943222
3. – article: “UX Tip: Don’t Hurt Me On Sign-Up”
4.   similarity: 0.33333333333333337
5. – article: Blogging Platform for Hackers
6.   similarity: 0.23570226039551587
7. – article: “Data Mining: Finding Similar Items”
8.   similarity: 0.0

這種方法有了很大改善，我們的代碼可以很好地運(yùn)行，但它依然存在問題。

示例中的問題：Tf-ldf權(quán)重

我們的數(shù)據(jù)很簡單，可以輕松地計(jì)算并作為衡量的依據(jù)。如果不采用余弦相似度，很可能會(huì)出現(xiàn)相同的結(jié)果。

Tf-ldf權(quán)重是一種解決方案。Tf-ldf是一個(gè)靜態(tài)統(tǒng)計(jì)量，用于權(quán)衡文本集合中的一個(gè)詞在一個(gè)文檔中的重要性。

根據(jù)Tf-ldff，我們可以為坐標(biāo)值賦予獨(dú)特的值，而并非局限于0和1.

對(duì)于我們剛才示例中的簡單數(shù)據(jù)集，也許更簡單的度量方法更適合，比如Jaccard index也許會(huì)更好。

皮爾遜相關(guān)系數(shù)（Pearson Correlation Coefficient）

使用皮爾遜相關(guān)系數(shù)（Pearson Correlation Coefficient）尋找兩個(gè)項(xiàng)目之間的相似性略顯復(fù)雜，也并不是非常適用于我們的數(shù)據(jù)集合。

例如，我們?cè)贗MDB中有2個(gè)用戶。其中一個(gè)用戶名為John，對(duì)五部電影做了評(píng)級(jí)：[1,2,3,4,5]。另一個(gè)用戶名為Mary，對(duì)這五部電影也給出了評(píng)級(jí)：[4, 5, 6, 7, 8]。這兩個(gè)用戶非常相似，他們之間有一個(gè)完美的線性關(guān)系，Mary的評(píng)級(jí)都是在John的基礎(chǔ)上加3。

計(jì)算公式如下：

代碼如下：

1. def pearson_score(a, b)
2.   n = a.length
3.   return 0 unless n > 0
4.   # summing the preferences
5.   sum1 = a.inject(0) {|sum, c| sum + c}
6.   sum2 = b.inject(0) {|sum, c| sum + c}
7.   # summing up the squares
8.   sum1_sq = a.inject(0) {|sum, c| sum + c ** 2}
9.   sum2_sq = b.inject(0) {|sum, c| sum + c ** 2}
10.   # summing up the product
11.   prod_sum = a.zip(b).inject(0) {|sum, ab| sum + ab[0] * ab[1]}
12.   # calculating the Pearson score
13.   num = prod_sum – (sum1 *sum2 / n)
14.   den = Math.sqrt((sum1_sq – (sum1 ** 2) / n) * (sum2_sq – (sum2 ** 2) / n))
15.   return 0 if den == 0
16.   return num / den
17. end
18. puts pearson_score([1,2,3,4,5], [4,5,6,7,8])
19. # => 1.0
20. puts pearson_score([1,2,3,4,5], [4,5,0,7,8])
21. # => 0.5063696835418333
22. puts pearson_score([1,2,3,4,5], [4,5,0,7,7])
23. # => 0.4338609156373132
24. puts pearson_score([1,2,3,4,5], [8,7,6,5,4])
25. # => -1

曼哈頓距離算法

沒有放之四海而皆準(zhǔn)的真理，我們所使用的公式取決于要處理的數(shù)據(jù)。下面我們簡要介紹一下曼哈頓距離算法。

曼哈頓距離算法計(jì)算兩點(diǎn)之間的網(wǎng)格距離，維基百科中的圖形完美詮釋了它與歐氏幾何距離的不同：

紅線、黃線和藍(lán)線是具有相同長度的曼哈頓距離，綠線代表歐氏幾何空間距離。