9

これは宿題の質問です。私は言葉でいっぱいの巨大な文書を持っています。私の課題は、これらの単語を適切に表すさまざまなグループ/クラスターに分類することです。これに対処するための私の戦略は、K-Means アルゴリズムを使用することです。ご存知のように、次の手順を実行します。

  1. グループ全体の k 個のランダム平均を生成する
  2. 各単語を最も近い平均値に関連付けて K 個のクラスターを作成する
  3. 各クラスターの重心を計算します。これが新しい平均になります
  4. 特定のベンチマーク/収束に達するまで、ステップ 2 とステップ 3 を繰り返します。

理論的には、私はそれを理解していますが、完全ではありません。各ステップで、それに対応する質問があると思います。これらは次のとおりです。

  1. k 個のランダム手段を決定するにはどうすればよいですか。技術的には 5 と言えますが、それは必ずしも適切な乱数であるとは限りません。この k は純粋に乱数なのか、それともデータセットのサイズや含まれる単語数などのヒューリスティックによって実際に駆動されるのか

  2. 各単語を最も近い平均値とどのように関連付けますか? 理論的には、各単語は最も近い平均までの距離によって関連付けられていると結論付けることができます。したがって、3 つの平均がある場合、特定のクラスターに属する単語は、どの平均までの距離が最も短いかに依存します。しかし、これは実際にどのように計算されるのでしょうか? 「group」、「textword」という 2 つの単語の間に、「pencil」という意味の単語を想定すると、どのように類似度マトリックスを作成できますか。

  3. セントロイドはどのように計算しますか？

  4. ステップ 2 とステップ 3 を繰り返すとき、前の各クラスターを新しいデータ セットと想定しているのでしょうか。

たくさんの質問があり、私は明らかにはっきりしていません。私が読むことができるリソースがあれば、それは素晴らしいことです. ウィキペディアでは十分ではありませんでした:(

4

3 に答える 3

12

クラスターの正確な数がわからないため、一種の階層的クラスタリングを使用することをお勧めします。

  1. すべての単語が非ユークリッド空間のポイントにすぎないと想像してください。レーベンシュタイン距離を使用して単語間の距離を計算します (辞書編集的に類似した単語のクラスターを検出する場合に最適です) 。
  2. すべての単語を含む最小全域木を構築する
  3. 長さがしきい値を超えているリンクを削除します
  4. リンクされた単語のグループは、類似した単語のクラスターです

ここに小さなイラストがあります：

ここに画像の説明を入力

PS最小スパニング ツリーの構築に基づくクラスタリングについて説明している Web で多くの論文を見つけることができます。

PPS意味的に類似した単語のクラスターを検出したい場合は、自動シソーラス構築のアルゴリズムが必要です

于 2012-12-08T12:06:28.493 に答える
0

k-means に "k" を選択する必要があることは、k-means の最大の欠点の 1 つです。ただし、ここで検索機能を使用すると、k を選択するための既知のヒューリスティックなアプローチを扱う多くの問題が見つかります。主に、アルゴリズムを複数回実行した結果を比較します。

「最寄り」について。K-means は実際にはdistancesを使用しません。ユークリッドを使用していると信じている人もいれば、二乗ユークリッドだと言う人もいます。技術的には、k-means が関心を持っているのは分散です。分散が最小になるように各オブジェクトをクラスターに割り当てることで、全体の分散を最小にします。偶然にも、すべての次元での二乗偏差の合計 (全分散に対する 1 つのオブジェクトの寄与) は、二乗ユークリッド距離の定義とまったく同じです。また、平方根は単調なので、代わりにユークリッド距離を使用することもできます。

いずれにせよ、単語で k-means を使用する場合は、最初に単語をベクトルとして表現する必要があります。ここで、2 乗ユークリッド距離が意味を持ちます。これは簡単なことではないし、おそらく不可能だとも思います。

于 2012-12-08T09:32:44.937 に答える