私が取り組んでいるサイトのユーザーのために「隣人」(似たような趣味を持つ人々) を生成するテクニックを探しています。last.fm の動作に似たもの。
現在、私はユーザー向けの互換性機能を持っています。1) 同様のアイテムを評価したこと、2) 同様にアイテムを評価したことでユーザーをランク付けします。この関数の重みは 2 倍高くなります。これは、「近隣」を生成するときにこれらの要因の 1 つだけを使用する必要がある場合に最も重要になります。
私が持っていた 1 つのアイデアは、ユーザーのすべての組み合わせの互換性を計算し、最も評価の高いユーザーをそのユーザーの隣人として選択することです。これの欠点は、ユーザー数が増えると、このプロセスに非常に長い時間がかかる可能性があることです. ちょうど 1000 人のユーザーの場合、1000C2 (0.5 * 1000 * 999 = = 499 500) の互換性関数呼び出しが必要で、サーバーにも非常に負担がかかる可能性があります。
ですから、このようなシステムを実現するための最善の方法について、アドバイスや記事へのリンクなどを探しています。
本のプログラミング集団知能
http://oreilly.com/catalog/9780596529321
第 2 章「レコメンデーションの作成」では、ユーザー間の類似性に基づいて人々にアイテムをレコメンデーションする方法を概説しています。類似性アルゴリズムを使用して、探している「隣人」を見つけることができます。この章は、Google ブック検索で入手できます:
http://books.google.com/books?id=fEsZ3Ey-Hq4C&printsec=frontcover
Collaborative Filteringを必ず確認してください。多くのレコメンデーション システムは、コラボレーション フィルタリングを使用してアイテムをユーザーに提案します。彼らは「隣人」を見つけて、あなたの隣人が高く評価しているがあなたが評価していないアイテムを提案することによってそれを行います. あなたは隣人を見つけることまで行くことができます、そして誰が知っているか、おそらくあなたは将来の推薦を必要とするでしょう.
GroupLensは、ミネソタ大学の研究所で、協調フィルタリング技術を研究しています。彼らは、多数の公開された研究といくつかのサンプル データセットを持っています。
Netflix Prizeは、この種の問題を最も効果的に解決できる人を決定するコンテストです。LeaderBoardのリンクをたどってください。いくつかの競合他社がソリューションを共有しています。
計算上安価な解決策として、これを試すことができます：
この方法はそれほど正確ではありませんが、高速です。
乾杯。
必要なのは、似たようなユーザーを自動的にグループ化するクラスタリング アルゴリズムです。直面している最初の問題は、ほとんどのクラスタリング アルゴリズムが、クラスタリングする項目がユークリッド空間の点として表現されることを期待していることです。あなたの場合、ポイントの座標がありません。代わりに、それらのペア間の「類似度」関数の値を計算できます。
ここでの 1 つの良い可能性は、スペクトル クラスタリングを使用することです。これには、類似度行列が必要です。欠点は、ポイントのペアごとに互換性関数を計算する必要があることです。つまり、アルゴリズムは O(n^2) です。
O(n^2) よりも高速なアルゴリズムが絶対に必要な場合は、非類似度スペースと呼ばれるアプローチを試すことができます。アイデアはとてもシンプルです。互換性関数を逆数にして (逆数をとることにより)、非類似度または距離の尺度に変換します。次に、すべてのアイテム (あなたの場合はユーザー) を一連のプロトタイプ アイテムと比較し、結果の距離を空間内の座標として扱います。たとえば、100 個のプロトタイプがある場合、各ユーザーは 100 要素のベクトル、つまり 100 次元空間内の点で表されます。次に、 K-meansなどの標準的なクラスタリング アルゴリズムを使用できます。
ここでの問題は、プロトタイプをどのように選択するか、および必要な数です。さまざまなヒューリスティックが試みられましたが、ここに論文がありますこれは、プロトタイプをランダムに選択するだけで十分であると主張しています。これは、ランダムに選択された 100 個または 200 個のプロトタイプを使用した実験で、良好な結果が得られたことを示しています。あなたの場合、1000 人のユーザーがいて、そのうちの 200 人をプロトタイプとして選択した場合、互換性関数を 200,000 回評価する必要があります。これは、すべてのペアを比較するよりも 2.5 倍の改善です。ただし、実際の利点は、1,000,000 ユーザーの場合、200 のプロトタイプで十分であり、2500 倍の改善である 5 億回ではなく、2 億回の比較を行う必要があることです。得られるのは O(n) アルゴリズムです。潜在的に大きな定数係数にもかかわらず、O(n^2) よりも優れています。
kohonen ネットワークについて聞いたことがありますか?
同様の変数を同様のスロットにクラスター化する自己組織化学習アルゴリズムです。リンク先のサイトのようなほとんどのサイトではネットが 2 次元として表示されますが、アルゴリズムを多次元ハイパーキューブに拡張することはほとんどありません。
このようなデータ構造では、似たようなユーザーは似たような場所に格納される必要があるため (逆ハッシュ コードのように)、好みが似ている隣人を見つけて格納するのは簡単です。
これにより、類似性を定義する変数を見つけ、可能な列挙値間の距離を確立するという問題に問題が軽減されます。たとえば、クラシックとアコースティックは近くにあり、デスメタルとレゲエはかなり離れています（少なくとも私の意見では）。
ところで、適切な分割変数を見つけるための最良のアルゴリズムは決定木です。ルートに近いノードは、「近さ」を確立するための最も重要な変数になります。
クラスタリング アルゴリズムについて読む必要があるようです。一般的な考え方は、すべてのポイントを他のすべてのポイントと比較するのではなく、それらを類似したポイントのクラスターに分割することです。その場合、近傍は同じクラスター内のすべてのポイントである可能性があります。クラスターの数/サイズは通常、クラスター化アルゴリズムのパラメーターです。
クラスタ コンピューティングと mapreduceに関する Google のシリーズで、クラスタリングに関するビデオを見つけることができます。
問題は「分類問題」のようです。はい、非常に多くのソリューションとアプローチがあります。
探索を開始するには、http: //en.wikipedia.org/wiki/Statistical_classificationを確認してください。
これをリアルタイム クエリではなくビルド/バッチの問題と見なすと、パフォーマンスに関する懸念を大幅に軽減できます。
グラフは静的に計算され、潜在的に毎時間、毎日など更新され、ランタイム クエリ用に最適化されたエッジとストレージが生成されます (各ユーザーの上位 10 人の類似ユーザーなど)。
集団知能のプログラミングにも+1 - それは非常に有益です - それがPython指向ではなかった(または私がそうであった!)ことを望みますが、それでも良いです。