11

類似性に基づいてドキュメントをクラスタリングしたい。

非常に高速な ssdeep (類似性ハッシュ) を試しましたが、k-means の方が高速で、flann はすべての実装の中で最も高速であり、より正確であると言われました。テキストで実行します（数値の配列のみをサポートします）。

私はこの分野（k-means、自然言語処理）に非常に慣れていません。必要なのはスピードと正確さです。

私の質問は次のとおりです。

  1. KMeans を使用してドキュメントの類似性グループ化/クラスタリングを行うことはできますか (Flann はテキスト入力を許可していないようです)
  2. フランは正しい選択ですか？そうでない場合は、Python ラッパー/API を備えたテキスト/ドキュメント クラスタリングをサポートする高性能ライブラリを提案してください。
  3. k-means は正しいアルゴリズムですか?
4

2 に答える 2

20

ドキュメントを数値の配列 (別名、ベクトル) として表す必要があります。どれだけ洗練されたいかによって、これを行う方法はたくさんありますが、最も簡単な方法は、単語数のベクトルとして表現することです。

だからここにあなたがすることです：

  1. 各単語がドキュメントに出現する回数を数えます。

  2. ベクターに含まれる「機能」単語のセットを選択します。これは、「the」、「a」などの非常に一般的な単語 (別名「ストップワード」) を除外する必要があります。

  3. 特徴語の数に基づいて、各ドキュメントのベクトルを作成します。

これが例です。

「ドキュメント」が単一の文で、次のようになっている場合 (1 行に 1 つのドキュメント):

there is a dog who chased a cat
someone ate pizza for lunch
the dog and a cat walk down the street toward another dog

特徴語のセットが である場合、[dog, cat, street, pizza, lunch]各ドキュメントをベクトルに変換できます。

[1, 1, 0, 0, 0]  // dog 1 time, cat 1 time
[0, 0, 0, 1, 1]  // pizza 1 time, lunch 1 time
[2, 1, 1, 0, 0]  // dog 2 times, cat 1 time, street 1 time

これらのベクトルを k-means アルゴリズムで使用できます。うまくいけば、最初と 3 番目の文は類似しているためグループ化され、2 番目の文は非常に異なるため別のクラスタになります。

于 2012-09-19T14:55:13.593 に答える
14

ここで 1 つの大きな問題があります。

K-means は、ユークリッド距離用に設計されています。

重要な問題は平均関数です。平均はユークリッド距離の分散を減らしますが、別の距離関数ではそうではないかもしれません。そのため、最悪の場合、k-means はもはや収束せず、無限ループで実行されます(ただし、ほとんどの実装では最大反復数での停止がサポートされています)。

さらに、スパースデータの場合、平均値はあまり適切ではなく、テキスト ベクトルは非常にスパースになる傾向があります。大まかに言えば、問題は、多数のドキュメントの平均が実際のドキュメントのように見えなくなり、実際のドキュメントとは異なり、他の平均ベクトルに類似するようになることです。したがって、結果はある程度縮退します。

テキスト ベクトルの場合は、コサイン類似度などの別の距離関数を使用することをお勧めします。

もちろん、最初に数値ベクトルを計算する必要があります。たとえば、用語の相対頻度を使用して、TF-IDFで正規化します。

k-medoidsとして知られる k-means アイデアのバリエーションがあります。任意の距離関数で動作し、クラスターの最も中心にある実際のドキュメント (「medoid」) を使用することで、「平​​均的な」こと全体を回避します。しかし、これに対する既知のアルゴリズムは、k-means よりもはるかに低速です。

于 2012-09-19T18:04:19.690 に答える