計算數百萬個文檔之間的相似性度量

Question

我擁有數百萬個文檔（接近1億個），每個文檔都有諸如skills,hobbies，certification和education的字段。我想找出每個文檔與評分之間的相似度。

下面是一個數據的例子。

skills hobbies  certification education 
Java fishing  PMP    MS 
Python reading novel SCM    BS 
C#  video game  PMP    B.Tech. 
C++  fishing  PMP    MS 

所以我想要的是第一行和所有其他行之間的相似性，第二行和所有其他行之間的相似性等等。所以，每一份文件都應該與其他所有文件進行比較。得到相似度分數。

目的是我查詢我的數據庫以獲取基於技能的人。除此之外，我現在想要那些雖然沒有技能，但與具有特定技能的人有點匹配的人。例如，如果我想爲具有JAVA技能的人員獲取數據，則會出現第一行，並且再次顯示最後一行，因爲它與基於相似性得分的第一行相同。

挑戰：我的主要挑戰是要計算一些相似性得分爲每個文件對所有其他文件，你可以從下面的僞代碼見。我該如何更快地做到這一點？有沒有什麼不同的方式來做到這一點，或者有沒有其他的計算（硬件/算法）方法可以更快地做到這一點？

document = all_document_in_db 
For i in document: 
    for j in document: 
     if i != j : 
     compute_similarity(i,j) 

Answer 1

加速的一種方法是確保您不會同時計算相似度。您當前的僞代碼將比較i到j和j到i。而不是在整個文檔上迭代j，迭代document[i+1:]，即僅在i之後的條目。這樣可以將您撥打的號碼減少一半到compute_similarity。

這種比較最合適的數據結構是一個鄰接矩陣。這將是n * n矩陣（n是數據集中的成員數），其中matrix[i][j]是成員i和j之間的相似度。您可以完全填充此矩陣，同時仍然只通過j的一半迭代，只需同時將matrix[i][j]和matrix[j][i]分配給compute_similarity一次。

除此之外，我想不出有什麼辦法來加速這個過程;您至少需要致電compute_similarity撥打n * (n - 1)/2。把它看作握手問題;如果每個成員必須至少與其他成員進行比較（與'握手'）至少一次，則下限爲n * (n - 1)/2。但我歡迎其他意見！

Answer 2

我想你想要的是某種聚類算法。您將每行數據視爲在多維空間中給出一個點。然後你想要尋找附近的其他「點」。並非數據的所有維度都會生成良好的集羣，因此您想分析哪些維度對於生成集羣非常重要，並通過映射到較低維度的數據來降低查找類似記錄的複雜性。 scikit-learn有一些用於維度分析和聚類的良好例程，以及一些幫助您決定應用於數據的例程的最佳文檔。對於實際進行分析，我認爲您可以通過AWS或Google AppEngine購買雲時間。我相信這兩者都可以讓您訪問節點上提供的帶有Anaconda（其中包括scikit-learn）的Hadoop集羣。關於這些主題（集羣，雲計算）的詳細說明都不是簡單的答案。當你在另一個問題後卡住了。

Answer 3

隨着100萬份文件，你需要500,000億比較。不，你不能用Python做到這一點。

最可行的解決方案（除使用超級計算機外）是計算C/C++中的相似度分數。

1. 閱讀整個數據庫並列舉每項技能，愛好，認證和教育。假設您的索引查找是「智能」並且需要不變的時間，此操作需要線性時間。
2. 用四個數字字段創建一個C/C++ struct：技能，愛好，認證和教育。
3. 運行一個嵌套循環，它從所有其他structs中逐個減去每個struct，並使用位級算術來評估相似性。
4. 將結果保存到文件中，並在必要時使它們可供Python程序使用。