查找圖中最接近匹配的高效算法

編輯：包括我的問題的具體解釋（如Billiska正確推導的）：「Set A是用戶集合，set B是產品集合，每個用戶的價格一個或多個產品，評分爲1至10.您想爲每個用戶推斷，誰是與他口味最相似的其他用戶。「查找圖中最接近匹配的高效算法

「另一半是選擇你想如何排列A元素的相似度。」 - 這也是我的問題的一部分。我覺得那些在大多數產品中評價相似的用戶都有親密的關係，但同時我想避免user1和user2與許多平庸的匹配在user1和user3之前匹配，他們只有幾個非常好的匹配（可能我需要一個非線性評分）。

聲明：我從來沒有使用圖形數據庫。

我有兩組數據A和B.A與零到許多Bs有關係。每個關係都有固定的價值。

例如

A1--5 - > B10

A1--1 - > B1000

所以，我最初的想法！「耶，那是一個曲線圖，時間來了解圖形數據庫」但之前，我得到太過分了...這樣做的唯一原因，以便我可以回答這個問題....

對於每一個找到的基於他們的權重最相似的一組，我想接受考慮

權重的差異（假設1到10），以便10和10的得分高於10和1;但後來我有如何處理這種情況是一個問題沒有配對（或做我 - 我只是不知道）
頂點的數量（忽略加權）以兩套的共同點。意圖是將兩個頂點排列成兩個頂點相同的兩個頂點，因爲只有一個匹配的頂點。

這樣做最好的方法是什麼？

（補充 - 因爲我意識到這可能算第二個問題）：如何將這種方法的變化，如果集合A的是在100千百萬，B和我需要實時的答案？

來源

2014-06-23 user2195559

恐怕我不能遵循這些規範。邊緣是否加權，如果是的話，如何確定它們的權重？這個圖形是直接的還是不直接的？頂點是否加權，如果是，如何確定權重？這可能與[加權二分法]（http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#In_weighted_bipartite_graphs）有關？ –

類似的含義是什麼？也許你可以定義A的兩個元素之間的距離（重量差異的平方和？）？ – user189

現在最重要的事情可能是更準確清晰地指定問題。（1）據我所知，「B10」和「B1000」只是B中2個元素的名稱（ID），對嗎？（2）如用戶189所述，以數學方式指定2個A元素之間的距離。 – Billiska

不完整的答案。我也不完全理解這種技術。但我知道這非常相關。

如果將數據視爲矩陣。例如將行對應於集合A，將列對應於集合B，並且條目是權重。然後它是一個有一些缺失值的矩陣。

recommender system（協同過濾類別下）使用的一種技術是低秩近似。

它是基於這樣的假設說，用戶產品評價矩陣通常具有較低的排名。在有粗糙感，則表示矩陣具有低級別如果許多用戶的行可以表示爲其他用戶這一行的線性組合。

我希望這將給出進一步的閱讀開始。

是的，你可以在low-rank approximation wiki page看出，該技術可以用來猜測缺少的條目（丟失的等級）。我知道這是一個不同的問題，但相關。

來源

2014-06-23 18:48:05 Billiska

對於相關答案以及努力解決我不明白的問題的答覆都有點贊成。 –

Billiska，我試圖給予好評，但我卻沒有足夠的代表... – user2195559

@ user2195559非常感謝你：d – Billiska

查找圖中最接近匹配的高效算法

回答

相關問題