Amazon.com Recommendations Item to Item Collaborative Filtering (2003)
August 16, 2025IEEE Internet Computingは、創刊20周年を記念し、時の試練を越えた論文にAmazon.com Recommendations Item to Item Collaborative Filteringを選んだ。 文献では、古典的な協調フィルタリングを、アイテム数次元\(N\)のベクトルでユーザーを表現し、類似するユーザーが選んだアイテムのうち、ユーザーが未選択のアイテムを推薦対象に選ぶ手法とみなされている。 提案されたItem to Item Collaborative Filteringは、アイテム同士の類似度を示す\(N\)x\(N\)次元の行列をオフラインで構築し、\(N\)や全ユーザー数に依存しないオンラインの計算量で、ユーザーが過去に選んだアイテムに類似するアイテムを推薦できる。
\(N\)x\(N\)次元のアイテムの類似度行列は、各ユーザーが購入したアイテムの集合からできるペアに基づいて計算される。 文献では, 以下の擬似コードがアルゴリズムとして説明されている。
For each item in product catalog, I1
For each customer C who purchased I1
For each item I2 purchased by customer C
Record that a customer purchased I1 and I2
For each item I2
Compute the similarity between I1 and I2
similarityの尺度に、たとえばコサイン類似度を使うことができる。 アイテム数を\(M\)とすると、最悪計算量は\(O(N^2M)\)になるが、現実的には、ユーザーが選ぶアイテム数は少ないため、計算量は\(O(NM)\)に収まる。