algorithm - 単語とカテゴリ値の分類

Question

今日の授業でアルゴリズムの問題が出題されました。「解決策がわかれば、この科目はやらなくてもいい」というものでした。もちろん、私たちは皆、やってみようと思っていました。

基本的には、100 語、10 カテゴリの DB が提供されました。単語またはカテゴリ間に一致はありません。つまり、基本的には 100 個の単語と 10 個のカテゴリのリストです。

単語を正しいカテゴリに「配置」する必要があります。つまり、単語を正しいカテゴリに配置する方法を「理解」する必要があります。したがって、単語を「理解」してから、アルゴリズム的に最も適切なカテゴリに分類する必要があります。

つまり、単語の 1 つが「釣り」というカテゴリの「スポーツ」です --> したがって、これはこのカテゴリに入ります。一部の単語が複数のカテゴリに入る可能性があるように、単語とカテゴリの間には重複があります。

それが分かれば、サンプルサイズを増やす必要があり、一致率が「最高」の人が勝ちます。

このようなことを始める方法を知っている人はいますか? または任意のリソースですか？できればC＃で？

キーワードDBか何かでも役立つでしょうか？無料のものを知っている人はいますか？

score 17 · Accepted Answer

まず、単語の関係を取得するために、分析するサンプルテキストが必要です。潜在的意味分析による分類については、潜在的意味分析による分類へのアプローチで説明されています。

別のアプローチは、単純なベイズテキスト分類です。割り当てられたカテゴリのサンプルテキストが必要です。学習ステップでは、プログラムはさまざまなカテゴリと、カテゴリに割り当てられたテキストに単語が出現する可能性を学習します。ベイズスパムフィルタリングを参照してください。それが単一の単語でどれほどうまく機能するかはわかりません。

score 11 · Accepted Answer

本当に貧弱な答え (「理解」がないことを示しています) - しかし、クレイジーな刺し傷として、(コードを介して) (たとえば)「+Fishing +Sport」、「+Fishing +Cooking」などの google をヒットできます (つまり、各単語をクロス結合し、カテゴリ) - Google の戦いに勝利しましょう! つまり、「ヒット」が最も多い組み合わせが選択されます...

例 (結果が最初):

weather: fish
sport: ball
weather: hat
fashion: trousers
weather: snowball
weather: tornado

コードあり (TODO: スレッドを追加 ;-p):

static void Main() {
    string[] words = { "fish", "ball", "hat", "trousers", "snowball","tornado" };
    string[] categories = { "sport", "fashion", "weather" };

    using(WebClient client = new WebClient()){
        foreach(string word in words) {
            var bestCategory = categories.OrderByDescending(
                cat => Rank(client, word, cat)).First();
            Console.WriteLine("{0}: {1}", bestCategory, word);
        }
    }
}

static int Rank(WebClient client, string word, string category) {
    string s = client.DownloadString("http://www.google.com/search?q=%2B" +
        Uri.EscapeDataString(word) + "+%2B" +
        Uri.EscapeDataString(category));
    var match = Regex.Match(s, @"of about \<b\>([0-9,]+)\</b\>");
    int rank = match.Success ? int.Parse(match.Groups[1].Value, NumberStyles.Any) : 0;
    Debug.WriteLine(string.Format("\t{0} / {1} : {2}", word, category, rank));
    return rank;
}

score 8 · Accepted Answer

たぶん、あなたはすべてこれを難しくしすぎています。

明らかに、X がカテゴリ Y に属する確率をランク付けするには、何らかの外部参照が必要です。彼があなたの「独創的な」思考をテストしていて、あなたが外部参照になる可能性はありますか? つまり、アルゴリズムは、各カテゴリと各単語を実行し、単語 X が表示されたカテゴリ Y にあるかどうかをあなた (または端末の前に座っている人) に尋ねるという単純な問題です。このテーマにはいくつかの単純なバリエーションがありますが、すべてゴーディアンノットを単に切断するだけで吹き飛ばす必要があります。

かどうかは・・・先生次第です。

score 3 · Accepted Answer

ここにはいくつかのオプションがあるようですが、ほとんどの場合、正確なデータが必要な場合は、外部の助けを借りる必要があると思います. 私が考えることができる2つのオプションは、辞書検索またはクラウドソーシングを利用することです.

辞書検索に関しては、データベースを調べてクエリを実行し、結果を解析して、カテゴリ名のいずれかがページに表示されているかどうかを確認できます。たとえば、「赤」を検索すると、ページに「色」が表示されます。同様に、「釣り」を検索すると、ページに「スポーツ」が返されます。

もう 1 つの、もう少し独創的なオプションは、クラウドソーシングを利用することです。以下を検討してください。

名前と値のペアを多かれ少なかれランダムに割り当てることから始めます。
結果を出力します。
結果をAmazon Mechanical Turk (AMT) にロードして、ペアがどの程度うまく機能しているかについて人間からフィードバックを取得します。
AMT 評価の結果をランダムな割り当てと共にシステムに入力します。
すべてが承認されたら、完了です。
それ以外の場合は、正しいヒットを保持し、それらを処理してパターンを確立できるかどうかを確認し、名前と値のペアの新しいセットを生成します。
手順 3 に戻ります。

確かに、これにはいくらかの財政的出費が伴いますが、かなり簡単に取得しようとしているデータの最も単純で正確なバージョンの 1 つになる可能性もあります。

score 2 · Accepted Answer

これは、スパムフィルタリングで使用されるベイジアン分類のようなものを使用できるように思えます。ただし、これには、コンテキストを提供する何らかのテキストベースの形式の「外部データ」が必要です。

それがなければ、問題を解決することは不可能です。これはアルゴリズムの問題ではなく、AIの問題です。しかし、AI (さらに言えば、自然知能も) でさえ、学習するための何らかのインプットが必要です。

教授は不可能な問題を与えて、ある問題についてどのようなレベルで考えられるかを理解させようとしているのではないかと思います。

ここで重要な問題は、「正しい」分類とは何かを誰が決定するのかということです。この決定は何に基づいていますか？この決定をプログラムで再現するにはどうすればよいでしょうか? また、どのような入力データが必要になるでしょうか?

score 2 · Accepted Answer

カスタムアルゴリズムを実行して、そのデータに特化して動作させることができます。たとえば、「ing」で終わる単語は動詞 (現在分詞) であり、スポーツである可能性があります。

上記のような一連の分類ルールを作成し、どれだけ高い精度が得られるかを確認します。

編集：

ウィキペディアのデータベースを盗み (とにかく無料です)、10 のカテゴリごとに記事のリストを取得します。各カテゴリの下のすべての記事で、100 個の単語のそれぞれの出現回数を数え、その単語の「キーワード密度」が最も高いカテゴリ (例: 釣り) が勝ちます。

score 1 · Accepted Answer

この先生を解雇します。

この問題の唯一の解決策は、問題の解決策をすでに持っていることです。つまり。キーワードをカテゴリに分類するコードを作成するには、キーワードとカテゴリのテーブルが必要です。

あなたが提案するように、あなたが英語を「理解する」システムを追加しない限り。これは、コンピュータの前に座っている人、またはエキスパートシステムです。

あなたがエキスパートシステムを構築していて、それさえ知らないなら、先生は問題を与えるのが苦手です。

score 1 · Accepted Answer

Googleは禁止されていますが、ほぼ完璧な解決策があります-GoogleSets。

単語のセマンティクスを理解する必要があるため、外部データソースが必要です。WordNetを使ってみることができます。または、ウィキペディアを使用してみることもできます。すべての単語のページ（またはカテゴリのみ）を見つけて、ページまたはリンクされたページに表示されている他の単語を探します。

score 1 · Accepted Answer

問題が外部データの使用を許可していると仮定しています。そうでなければ、単語からアルゴリズム的に意味を推測する方法を思いつかないからです。

シソーラスデータベースを使用して、「単語」の単語と「カテゴリ」の単語の間の最小距離を探すことで何かできるのではないでしょうか?

score 1 · Accepted Answer

ええ、私はワードネットのアプローチに行きます。WordNet ベースのセマンティック類似度測定に関するこのチュートリアルを確認してください。princeton.edu (google it) で Wordnet をオンラインで照会できるので、問題の解決策をコーディングするのは比較的簡単です。お役に立てれば、

バツ。

score 1 · Accepted Answer

興味深い問題です。あなたが見ているのは単語の分類です。LSAやそれに基づく分類などの従来の情報検索方法を学習して使用することはできますが、それがあなたの意図であるかどうかはわかりません（そうである場合は、ぜひそうしてください! :)

あなたは外部データを使用できると言っているので、ワードネットとその単語間のリンクを使用することをお勧めします。たとえば、ワードネットを使用すると、

# S: (n) **fishing**, sportfishing (the act of someone who fishes as a diversion)
* direct hypernym / inherited hypernym / sister term
      o S: (n) **outdoor sport, field sport** (a sport that is played outdoors)
      + direct hypernym / inherited hypernym / sister term
            # S: (n) **sport**, athletics 
            (an active diversion requiring physical exertion and competition)

ここに表示されるのは、単語間の関係のリストです。釣りという用語は、スポーツに関連するアウトドアスポーツに関連しています。

ここで、ドリフトを取得すると、この関係を使用して、「釣り」を「スポーツ」に分類する確率を計算できます。たとえば、単語チェーンの直線距離、または出現回数などに基づいて計算できます。（ワードネットを使用して類似性測定を構築する方法に関するリソースを見つけるのは簡単なはずです。教授が「グーグルを使用しないでください」と言うとき、私は彼がプログラム的に意味していると思います。情報を読むための手段としてではありません！）

wordnetを使用したC＃について-http://opensource.ebswift.com/WordNet.Net/はどうですか

score 0 · Accepted Answer

WordNetデータベースを使用して、2つの単語（単語とカテゴリ）がどの程度密接にリンクされているかを判断するためのメトリックを作成し、単語を配置するのに最適なカテゴリを選択できる場合があります。

score 0 · Accepted Answer

私の素朴なアプローチ：

このような巨大なテキストファイルを作成します(記事を読んでインスピレーションを得てください) 。
すべての単語について、テキストをスキャンし、その単語に一致するたびに、その左右の N (最大、別名ラジオ) 位置に表示される「カテゴリ」を数えます。
この単語は、最大のカウンターを持つカテゴリに属している可能性があります。

score 0 · Accepted Answer

私の試みは、CRM114のツールセットを使用して、大量のテキストコーパスを分析する方法を提供することです。次に、そこからのマッチングを利用して推測できます。

score 0 · Accepted Answer

RCV1などの既存の分類された大規模なデータセットを使用して、選択したシステムをトレーニングします。既存の研究やベンチマークを読み始めると、さらに悪い結果になる可能性があります。

Google 以外にも、作成できる「百科事典」データセットが他にもあります。そのうちのいくつかは、英語版ウィキペディアの完全なスナップショットなど、アマゾンウェブサービスで公開データセットとしてホストされています。

クリエイティブに。Google以外にもデータがあります。

score 0 · Accepted Answer

Google は使えませんが、Yahoo、Ask、Bing、Ding、Dong、Kong は使えます。最初に 2 ～ 3 の検索エンジンに対して 100 語のクエリを実行し、結果として得られた最初の y 個の記事を取得し (y は実験のしきい値です。最初は 5 が良いと思います)、テキストをスキャンします。具体的には、10 のカテゴリを検索します。カテゴリが x 回 (x は、実験する必要のあるしきい値です) 以上表示された場合、一致します。その x しきい値に基づいて (つまり、カテゴリが単語とカテゴリのペアに重みを割り当てることができます。精度を上げるために、単語とカテゴリのペアを使用して、Google 以外の検索エンジンで別のパスを実行できます ( AND 関係) を作成し、結果のページ数をそのペアの重みに適用します。彼らは、重みが最も高い単語とカテゴリのペアが正しいものであると単純に想定しています (複数の選択肢があると仮定して)。重みが十分に近い場合は、単語を複数のカテゴリに複数割り当てることもできます (おそらく z しきい値)。それに基づいて、任意の数の単語と任意の数のカテゴリを導入できます。そして、あなたはあなたの挑戦に勝つでしょう。また、この方法は、広告における潜在的なアドワーズ広告の重みを評価するのにも適していると思います. しかし、それは別のトピックです.... また、この方法は、広告における潜在的なアドワーズ広告の重みを評価するのにも適していると思います. しかし、それは別のトピックです.... また、この方法は、広告における潜在的なアドワーズ広告の重みを評価するのにも適していると思います. しかし、それは別のトピックです....

幸運を

ハレル

score 0 · Accepted Answer

(オンラインまたはダウンロードのいずれかで) WordNetを使用し、単語と各カテゴリの間で従わなければならない関係の数を見つけます。

score 0 · Accepted Answer

私が最初に考えたのは、外部データを活用することです。各単語をグーグル検索し、検索結果の最初/最上位に表示される「カテゴリ」を取得するプログラムを作成します:)

しかし、それは不正行為と見なされる可能性があります。

score 0 · Accepted Answer

この「なぞなぞ」を解く際にその科目に参加する必要はないので、簡単なことではないと思います。それにもかかわらず、私はこのようなことをします（非常に単純化した方法で言います）

いくつかの入力を与える神経ネットワークを構築します（（電子）本、いくつかの（電子）本）=>グーグルは必要ありません

このネットワークは単語を分類します (ニューラルネットワークは「不確かな」分類に最適です)。テキスト内の出現により、どの単語がどのカテゴリに属しているかを簡単に知ることができると思います. （「釣り」は「スポーツ」の近くで言及される可能性が高い）。ニューラルネットワークのトレーニングが完了すると、単語がカテゴリに「リンク」されるはずです。

score 0 · Accepted Answer

おいしい.comをかき集めて単語ごとに検索し、まとめてタグ数を調べるなど。

これについてはこれ以上言えませんが、delicious は古く、巨大で、信じられないほど多くのタグが付けられており、現在関連するセマンティック情報を豊富に含んでいます。スクレイピングのベースとして単語リストを使用して、この方法でセマンティクスデータベースを構築するのは非常に簡単です。

知識はタグにあります。

algorithm - 単語とカテゴリ値の分類

21 に答える 21

Related

Reference