4

私はデータマイニングに関するプロジェクトに取り組んでいます。私の会社は、Facebook の 600 万のダミーの顧客情報を私に提供してくれました。私は、任意の 2 人のユーザーの類似点を見つけるように割り当てられました。大規模なコミュニティ データを処理する方法を誰か教えてもらえますか? 前もって感謝します ：）

問題 : 2 人の異なるユーザー間の類似性を測定する 2 つの基準として、ステータス情報とハッシュタグ情報 (ハッシュタグはユーザーによって強調表示された単語) を使用します。ユーザー数が多いため、特に各ユーザーの数百万のハッシュタグとステータスが存在する可能性があります。2 人のユーザー間の類似性をすばやく計算する良い方法を誰か教えてもらえますか? TF-IDF を使用して 2 人の異なるユーザー間の類似度を計算しようとしましたが、実行不可能なようです。ユーザー間のすべての類似点をすばやく見つけることができる非常に優れたアルゴリズムまたは優れたアイデアを持っている人はいますか?

例えば：

user A's hashtag = `{cat, bull, cow, chicken, duck}`
user B's hashtag =`{cat, chicken, cloth}` 
user C's hashtag = `{lenovo, Hp, Sony}`

明らかに、C は A と関係がないため、時間を無駄にするために類似性を計算する必要はありません。類似性を計算する前に、関係のないすべてのユーザーを最初に除外することができます。実際、全ユーザーの 90% 以上が特定のユーザーとは無関係です。ハッシュタグを条件として使用して、A の潜在的な類似ユーザー グループをすばやく見つける方法は? これは良い考えですか？それとも、A と他のすべてのユーザーとの相対的な類似性を直接計算するだけですか? 問題に対して最も高速でカスタマイズされたアルゴリズムはどれですか?

4

1 に答える 1

13

ユーザーのベクトル表現

定義したものを使用しても問題ありません。likesユーザーの関心をよく表しているfacebook を含めることもできます。

類似度関数

コサイン距離またはジャカード類似度のいずれかがケースに適しています。

付与ユーザーの類似ユーザーの検索

Kd ツリーアプローチ

最初に kd ツリーを構築し、次に任意のユーザーに対して、そのユーザーのクエリを起動できます。kd ツリーは、類似関数に基づいて k 最近傍を返すことができます。C++ での適切な実装はこちらです。

locality-sensitive-hashingアプローチ

ユーザーを異なるバケットにハッシュします。同様のユーザーは、一緒にハッシュされる可能性が高くなります。したがって、類似ユーザー検索では、同じバケット内のユーザーのみを比較します。例については、これを確認してください: Locality Sensitive Hashing を理解する方法?

clusteringアプローチ

k-meansなどのクラスタリング アルゴリズムを試してください。これは、ユーザーを少数のクラスターにグループ化するための最初のステップであり、その後O(n^2)、グループ内のすべてのユーザーのペア間で比較を行うことができます。

collaborative-filteringアプローチ。

それらのいいねやハッシュタグは、ユーザーが気に入ったアイテムとして扱います。次に、協調フィルタリング アプローチを試すことができます。何百万ものユーザーの場合、mahoutなどの map-reduce ベースの実装を使用したい場合があります。

于 2012-12-04T22:37:07.440 に答える