2

テキスト ファイル (数百万単位) に URL のリストがあり、テキスト ファイルにブラックリストに登録された単語を含む別のリストがあるとします。

URLのリストに対して次の処理を実行したいと考えています。

- Parse the URLs and store them in some DS
- Process the URLs and blacklist those URLs which contain atleast one of the 
  blacklisted words.
- If there exists a URL containing 50% or more blacklisted words, add the other 
  words of that URL in the list of blacklisted words.
- Since now the blacklisted words list has been modified then it's probable 
  that the URLs which were not blacklisted earlier can get blacklisted now. So, 
  the algorithm should handle this case as well and mark the earlier whitelisted 
  URLs as blacklisted if they contain these newly added blacklisted words.

最後に、ホワイトリストに登録された URL のリストが必要です

最も効果的な時間と空間の複雑さの解決策を達成するために使用できる最良のアルゴリズムと DS は何か提案はありますか?

4

2 に答える 2

1

マトリックスを使用してURLを保存します。

  1. まず、Porter Stemmerによって各URLを単語に分割し、それらをマトリックスに配置します（1つのURLに1つの行、1つの単語に1つの項目）。

  2. 次に、TFIDFを使用してマトリックス内の各単語にスコアを付け、スコアの低い単語を削除します（これらは、スパムの判断に役立たない「a」、「the」などの人気のある単語です）。

  3. ブラックリストを手動で初期化します（いくつかの一般的なブラックワードをその中に入れます）。

  4. 指定したとおりにプロセスを実行するだけです。

于 2012-12-15T09:10:51.627 に答える
1

この問題の機械学習の部分についてだけ回答し、データ構造と効率的なテキスト マッチングについてはオープンのままにします。

まず、非決定性が問題になる場合は、更新する前に、特定のバージョンのブラックリスト/分類子を使用してデータ全体を渡すことができます。これにより、入力の順序に関係なく同じ答えが得られます。一方で、決定論を何よりも重視すべきだとは思いません。機械学習では、確率的勾配降下法は順序不変ではありませんが、実際には、特に大規模なデータ セットではうまく機能します。

第二に、提案された候補用語を手動でフィルター処理する意思がない限り (そしておそらくそれでも)、単純な確率論的アプローチを使用したい場合を除いて、おそらく真っ直ぐなブラックリストには注意する必要があります。単純ベイズは、合理的に機能する最も単純なアプローチです。これにより、バイアグラに関する医療記事をスパムではないというラベルを付けることができます。たとえば、スパムのような言葉が含まれていても、非常に信頼できるホスト (webmd など) からのものであるためです。

手動で選択したブラックリスト用語を使用して、否定的にラベル付けされた URL の初期セットを生成できます。次に、別の肯定的なラベルのセットを考え出し (おそらくコーパスからランダムに選択することもできますが、それがほとんど良いと仮定して)、それを使用して初期の単純ベイズ分類器をトレーニングします。次に、半教師あり学習を行うことで、特定のコーパスの独自の出力に基づいて分類子を変更するというアイデアを活用できます。これにより、ラベル付けされたドキュメントの小さな初期セットから優れた学習/なだれ効果が得られます。

于 2012-12-15T17:33:10.113 に答える