6

一連のユーザー、一連の曲、および各曲に対する一連の投票があるとしましょう:

=========== =========== =======
User        Song        Vote
=========== =========== =======
user1       song1       [score]
user1       song2       [score]
user1       song3       [score]
user2       song1       [score]
user2       song2       [score]
user2       song3       [score]
user3       song1       [score]
user3       song2       [score]
user3       song3       [score]
user-n      song-n      [score]
=========== =========== =======

歌の投票に基づいてユーザーの類似性を計算する最も効率的な方法は何ですか? すべてのユーザーとすべての曲のすべての投票を繰り返すよりも良い方法はありますか?

4

7 に答える 7

11

ユーザー間の類似性を見つけるために使用できる一般的な指標が 2 つあります。

  1. ユークリッド距離、それはまさにあなたが考えていることです: 各軸に 2 人の関係ユーザー ( u1と *u2) がレビューする曲を持ち、その軸の値がスコアである n 次元グラフを想像してください。次の式を使用して、類似度を簡単に計算できます。

    u1 と u2 がレビューしたすべての曲について、計算pow(u1.song.score - u2.song.score, 2)してすべてを に加算しsum_of_powersます。類似係数は で与えられ1 / 1 + (sqrt(sum_of_powers))ます。

  2. ピアソン相関(または相関係数): 2 つのデータセットが互いにどの程度関連しているかを調べるより良いアプローチです。このアプローチでは、より複雑な数式と統計の背景を少し使用します。ここで確認してください: wiki . ユーザーのカップルごとにグラフを作成し、スコアに従ってポイントをプロットします。たとえば、u1 とu2 からaSong投票された場合、ポイントがプロットされます(user1 が x 軸で u2 が y 軸であると仮定します)。 ）。24(2,4)

明確にするために、線形回帰を使用して、グラフのすべての点からの距離を最小化する線を表すAとの2 つの係数を見つけます。Bこの行の式は次のとおりy = Ax + Bです。2 つのセットが類似している場合、ポイントは主対角線の近くにあるA必要があるため、1 になり、0 になる傾向があります。Bこの説明は、健全性と典型的な数学形式に欠けているため、完全または参照として想定しないでください。アイデアを提供するだけです。 .

編集: 他の人が書いたように、k-means のように、データをクラスター化するためのより複雑なアルゴリズムが存在しますが、簡単なものから始めることをお勧めします (実際には、結果が十分ではないことに気付いたときに、もっと難しいものが必要になるはずです)。

于 2009-12-02T22:49:31.733 に答える
5

Toby Segaranの本Programming Collective Intelligenceをお勧めします。第 3 章では、階層型クラスタリングやK-means クラスタリングなどのさまざまなクラスタリング方法について説明します。

サンプルのソースコードはこちらから入手できます

于 2009-12-02T22:47:55.043 に答える
3

最も正確な結果が必要な場合は、いいえ、すべてを反復する必要があります。

データベースが十分に大きい場合は、1,000 ～ 10,000 人のユーザーを抽出してそれに対して照合するなど、統計的なサンプリングを行うことができます。

また、その場で計算するのではなく、データベースにさらにいくつかのテーブルを追加し、結果を保存し、時々更新するだけのほうがよいでしょう。

于 2009-12-02T22:51:12.060 に答える
1

すべてのレコードにアクセスせずにおおよその方法でそれを実行したい場合は、Jaccard係数を使用できます。スコアを検討したい場合は、おそらくいくつかの適応が必要です。ただし、システムが大きすぎて、すべてのレコードをチェックする時間がない場合は、これが最善の解決策だと思います。

于 2009-12-03T00:55:20.153 に答える
1

Ilya Grigorik は、Ruby に焦点を当てていましたが、レコメンデーション アルゴリズムに関するシリーズを作成しました。彼のアーカイブの機械学習セクションの下にあるようですが、セクションへの直接リンクはありません。

于 2009-12-02T22:57:04.570 に答える
1

ここにいる多くの人は、質問の単純さを見逃していると思います。彼は、評価予測システムの作成については何も言いませんでした。彼は、各ユーザーの曲の評価行動と他の各ユーザーの曲の評価行動との類似性を計算したいだけです。ピアソンの相関係数はまさにそれを示しています。はい、すべてのユーザー/ユーザーのペアを反復処理する必要があります。

編集：

これについてもう少し考えた後：

Pearson は、2 人のユーザーの好みの類似性を求める場合に優れていますが、彼らの「こだわり」のレベルは求めません...一連の曲 4、5、および 6 を評価する 1 人のユーザーは、同じ曲を評価する別のユーザーと完全に相関します。 3、6、および 9. 言い換えれば、彼らは同じ「好み」を持っています (彼らは同じ順序で曲をランク付けします) が、2 番目のユーザーははるかに独断的です。つまり、相関係数は、線形関係を持つ任意の 2 つの評価ベクトルを等しいものとして扱います。

ただし、ユーザーが各曲に付けた実際の評価の類似性が必要な場合は、2 つの評価ベクトル間の二乗平均平方根誤差を使用する必要があります。これは純粋に距離ベースのメトリックです (線形関係は類似度スコアに反映されません)。そのため、4、5、6 および 3、6、9 のユーザーは完全な類似度スコアを持ちません。

決定は、「類似」の意味に帰着します...

それだけです。

于 2009-12-02T23:14:54.957 に答える
0

この本で良いアルゴリズムを見つけることができるはずです: Steven Skiena によるThe Algorithm Design Manual 。

この本には、さまざまな目的のためのアルゴリズムがたくさんあります。グラフ クラスタリング アルゴリズムが必要だと思います。私はその本を手元に持っていないので、あなたに代わって調べることができません。

Google で簡単に検索すると、ウィキペディアのページが見つかりました 。

于 2009-12-02T22:41:39.517 に答える