24

かなり一般的な状況です、私は賭けます。あなたはブログやニュースサイトを持っていて、たくさんの記事やブログ、またはあなたがそれらと呼んでいるものがあり、それぞれの下部に、関連しているように見える他の人を提案したいと思います。

各アイテムに関するメタデータはほとんどないと仮定しましょう。つまり、タグやカテゴリはありません。タイトルと著者名を含む、1つの大きなテキストの塊として扱います。

関連する可能性のあるドキュメントをどのように見つけますか？

私は実際のアルゴリズムに興味があり、すぐに使えるソリューションではありませんが、rubyやpythonで実装されているものを調べたり、mysqlやpgsqlに依存したりしても大丈夫です。

編集：現在の答えはかなり良いですが、もっと見たいです。たぶん、1つか2つのもののためのいくつかの本当に裸のサンプルコード。

4

5 に答える 5

38

これはかなり大きなトピックです。人々がここで思いつく答えに加えて、いくつかの情報検索クラスのシラバスを追跡し、それらに割り当てられた教科書とレポートをチェックすることをお勧めします。とはいえ、ここに私自身の大学院時代の簡単な概要があります。

最も単純なアプローチは、bag of wordsと呼ばれます。各ドキュメントは{word: wordcount}ペアのスパース ベクトルに縮小され、ドキュメントのセットを表すベクトルのセットで NaiveBayes (またはその他の) 分類子をスローするか、各バッグと他のすべてのバッグの間の類似度スコアを計算できます (これは、 k 最近傍分類)。KNN はルックアップが高速ですが、スコア マトリックス用に O(n^2) ストレージが必要です。ただし、ブログの場合、n はそれほど大きくありません。大きな新聞のサイズの場合、KNN は急速に実用的でなくなるため、オンザフライ分類アルゴリズムの方が優れている場合があります。その場合、ランキング サポート ベクター マシンを検討できます。SVM は、線形の類似性測定に制約されないため優れており、それでも非常に高速です。

ステミングは、bag-of-words 手法の一般的な前処理ステップです。これには、"cat" と "cats"、"Bob" と "Bob's"、または "similar" と "similarly" などの形態学的に関連する単語を語根まで減らしてから、単語のバッグを計算します。世の中にはさまざまなステミング アルゴリズムがたくさんあります。ウィキペディアのページには、いくつかの実装へのリンクがあります。

bag-of-words の類似性が十分でない場合は、レイヤーを bag-of-N-grams の類似性に抽象化して、単語のペアまたはトリプルに基づいてドキュメントを表すベクトルを作成できます。(4 タプルまたはさらに大きなタプルを使用することもできますが、実際にはこれはあまり役に立ちません。)これには、はるかに大きなベクトルを生成するという欠点があり、それに応じて分類に多くの作業が必要になりますが、得られる一致ははるかに近くなります。構文的に。OTOH、セマンティックの類似性のためにこれはおそらく必要ありません。盗作の検出などには適しています。チャンキング、またはドキュメントを軽量の解析ツリーに縮小することも使用できます (ツリーには分類アルゴリズムがあります) が、これは作成者の問題 (「出所が不明なドキュメントが与えられた場合、

ユース ケースでより役立つのは、単語を概念にマッピングし ( WordNetなどのシソーラスを使用)、使用されている概念間の類似性に基づいてドキュメントを分類する概念マイニングです。単語から概念へのマッピングは還元的であるため、これは多くの場合、単語ベースの類似性分類よりも効率的になりますが、前処理ステップはかなり時間がかかる可能性があります。

最後に、談話構文解析があります。これには、文書の意味構造の構文解析が含まれます。チャンクされたドキュメントと同じように、談話ツリーで類似性分類子を実行できます。

これらはほとんどすべて、非構造化テキストからメタデータを生成することを伴います。生のテキスト ブロック間で直接比較を行うのは扱いにくいため、最初に文書をメタデータに前処理します。

于 2009-08-10T13:25:43.590 に答える
4

「Programming Collective Intelligence: Building Smart Web 2.0 Applications」(ISBN 0596529325) という本を読むべきです!

メソッドとコードの例: 最初に、単語の一致に基づいて直接的な類似性を見つけたいのか、それとも現在の記事とは直接関係ないが、記事の同じクラスターに属している類似の記事を表示したいのかを自問してください。

クラスタ分析 / パーティション クラスタリングを参照してください。

直接的な類似点を見つけるための非常に単純な (しかし理論的で遅い) 方法は次のとおりです。

前処理:

  1. 記事ごとにフラットな単語リストを保存します (重複する単語は削除しません)。
  2. 記事を「相互結合」します。記事 B の同じ単語に一致する記事 A の単語の数を数えます。これで行列ができましたint word_matches[narticles][narticles](そのように保存しないでください。A->B の類似性は B->A と同じです。そのため、疎行列はほぼ半分のスペースを節約します)。
  3. word_matches カウントを 0..1 の範囲に正規化します。（最大カウントを見つけて、これでカウントを割ります）-intではなくfloatをそこに格納する必要があります;）

類似の記事を検索:

  1. word_matches から最も一致する記事を X 個選択します
于 2009-12-11T01:47:29.080 に答える
4

これは、機械学習のあらゆるクラスで研究されている文書分類の典型的なケースです。統計、数学、コンピューター サイエンスが好きな方は、kmeans++、ベイジアン メソッド、LDAなどの教師なしメソッドをご覧になることをお勧めします。特に、ベイジアン法は探しているものに非常に適していますが、唯一の問題は遅いことです (ただし、非常に大きなサイトを実行していない限り、それほど気にする必要はありません)。

より実用的で理論的ではないアプローチについては、これと他の優れたコード例をご覧になることをお勧めします。

于 2009-12-06T05:06:11.207 に答える
3

Ruby の小さなベクトル空間モデル検索エンジン。基本的な考え方は、2 つのドキュメントに同じ単語が含まれている場合、それらは関連しているということです。そのため、各ドキュメント内の単語の出現回数をカウントし、これらのベクトル間のコサインを計算します (各用語には固定インデックスがあり、そのインデックスに 1 があるように見える場合、0 でない場合)。2 つの文書にすべての用語が共通している場合、コサインは 1.0 になり、共通の用語がない場合は 0.0 になります。それを % 値に直接変換できます。

terms = Hash.new{|h,k|h[k]=h.size}
docs = DATA.collect { |line| 
  name = line.match(/^\d+/)
  words = line.downcase.scan(/[a-z]+/)
  vector = [] 
  words.each { |word| vector[terms[word]] = 1 }
  {:name=>name,:vector=>vector}
}
current = docs.first # or any other
docs.sort_by { |doc| 
  # assume we have defined cosine on arrays
  doc[:vector].cosine(current[:vector]) 
}
related = docs[1..5].collect{|doc|doc[:name]}

puts related

__END__
0 Human machine interface for Lab ABC computer applications
1 A survey of user opinion of computer system response time
2 The EPS user interface management system
3 System and human system engineering testing of EPS
4 Relation of user-perceived response time to error measurement
5 The generation of random, binary, unordered trees
6 The intersection graph of paths in trees
7 Graph minors IV: Widths of trees and well-quasi-ordering
8 Graph minors: A survey

の定義はArray#cosine、読者への演習として残されています (nil 値と異なる長さを扱う必要がありますが、それでうまくいきましたArray#zipか?)

ところで、ドキュメントの例は、Deerwester et al による SVD 論文から取られています :)

于 2009-12-06T11:59:33.390 に答える
1

少し前に、私は似たようなものを実装しました。この考えは時代遅れかもしれませんが、お役に立てば幸いです。

私は一般的なタスクをプログラミングするために ASP 3.0 Web サイトを運営し、この原則から始めました。ユーザーは疑いを持ち、その主題に関する興味深いコンテンツを見つけることができる限り、Web サイトにとどまります。

ユーザーが到着すると、ASP 3.0Sessionオブジェクトを開始し、すべてのユーザー ナビゲーションをリンク リストのように記録しました。イベントSession.OnEndでは、最初のリンクを取得し、次のリンクを探して、次のようなカウンター列を増やしました。

<Article Title="Cookie problem A">
    <NextPage Title="Cookie problem B" Count="5" />
    <NextPage Title="Cookie problem C" Count="2" />
</Article>

したがって、関連記事を確認するには、カウンター列の降順で上位n 個 のエンティティをリストする必要がありました。NextPage

于 2009-12-05T23:22:16.183 に答える