データマイニング: 機械学習手法に基づく POI カテゴリ推奨アルゴリズム

序文

Meituan マーチャント データ センター (MDC) には、調整および監査済みの POI データが 100 万件以上あります (通常、マーチャントは POI としてマークされ、基本的な POI 情報には、店舗名、カテゴリ、電話番号、住所、座標などが含まれます)。この記事では、これらの調整された POI データを使用して貴重な情報をマイニングするいくつかの試みを行います。機械学習手法を使用して、欠落しているカテゴリを持つ POI データに自動的に注釈を付けます。たとえば、「Hao Zhai Lai Beef Ramen Restaurant」という店名の POI には、自動的に「スナック」というラベルが付けられます。

機械学習による問題解決の一般的なプロセス:

この記事は、1) 特徴表現、2) 特徴選択、3) ナイーブベイズに基づく分類モデル、4) 分類予測の 4 つの部分に分かれています。

特徴表現

まず、実際の問題をコンピューターが認識できる形式に変換する必要があります。 POI の場合、POI カテゴリを反映する重要な特徴は POI 店舗名であるため、問題は POI 店舗名に基づいて POI カテゴリを決定することに変わります。 POI名フィールドはテキスト特徴である。従来のテキスト表現方法はベクトル空間モデル（VSMモデル）[1]に基づいている。

空間ベクトル モデルには「辞書」が必要です。これはサンプル内で生成することも、外部からインポートすることもできます。上の写真の辞書は[良い、ホテル、海底、ラーメン、氷雪、……、ホール]です。キャリブレーションされたPOIについては、まずLuceneの中国語単語分割ツールSmartCn[2]を使用してPOI名を事前に分割し、特徴語を元の大まかな辞書セットとして抽出します。

辞書を使えば、テキストを定量的に表現することができます。まず、辞書と同じ長さのベクトルを定義します。ベクトル内の各位置は、辞書内の対応する位置にある単語に対応します。次に、テキストをトラバースし、テキストに出現する各単語のベクトル内の対応する位置に「特定の値」（つまり、BOOL 重み、単語頻度重み、TFIDF 重みを含む特徴語の重み）を入力します。一般的な POI 名は短いテキストであることを考慮して、この論文では BOOL 重みを使用します。

ラフ辞書セットを生成する際に、キャリブレーション POI 内の各カテゴリ (type_id) と特徴語 (term) がカテゴリ (type_id) 内に出現した回数 (文書頻度) もカウントしました。これらはそれぞれ、テーブル category_frequency と term_category_frequency に書き込まれます。テーブルの結果の一部は次のとおりです。

カテゴリ頻度テーブル:

term_category_frequency テーブル:

別途記録:

これらの統計は、後続の計算で重要な役割を果たします。

機能選択

現在、「事前入力辞書」があります。これには、「88」、「11」、「3」、「auyi」、「center」、「China」、「hotel」、「buffet」、「ramen」など、すべての調整済み POI 名フィールドの特徴語が含まれています。直感的には、「88」、「11」、「3」、「auyi」、「中国」などの単語はカテゴリの決定にはあまり役立ちませんが、「ホテル」、「ビュッフェ」、「ラーメン」は POI のカテゴリを決定する上で非常に重要な役割を果たす可能性があります。

そこで疑問になるのが、モデル予測に有益な特徴をどのように選択するかということです。これには特徴選択が含まれます。特徴選択方法は、ドメイン知識に基づくルールベースの方法と統計学習法に分けられます。この論文では、統計的機械学習手法と、ルールベースの手法で支援された特徴選択アルゴリズムを使用して、POI カテゴリの決定に役立つ特徴語を選択します。

統計学習に基づく特徴選択アルゴリズム

統計学習に基づく特徴選択アルゴリズムは、大きく分けて 2 つのタイプに分けられます。

1. 相関測定に基づく（情報理論関連）

2. 特徴空間表現（典型的にはPCA）

情報ゲイン（IG）法は、テキスト特徴量の特徴選択法としてよく用いられる[3]。ある特徴の情報ゲインとは、その特徴が知られる前と後におけるシステム全体の情報量の変化を指します。前後の情報量の変化が大きいほど、この機能の役割は大きいと考えられます。
では、情報量をどのように定義するのでしょうか?エントロピーの概念は、一般的にシステム内の情報量を測定するために使用されます。

特徴がわかれば、数学的な観点から、特徴の分布がわかり、システム内の情報量は条件付きエントロピーによって記述できます。

この機能の情報ゲインは次のように定義されます。

情報ゲインスコアは、機能の重要性を測定します。 4 つのサンプルがあり、サンプルの特徴的な単語に「鍋」、「ライスヌードル」、「レストラン」が含まれているとします。情報ゲインを使用して、さまざまな特徴が意思決定に与える影響を判断します。

システム全体の元の情報エントロピーは次のとおりです。

各特徴の条件付きエントロピーを個別に計算します。

システム全体の情報エントロピーから条件付きエントロピーを減算することで、各特徴の情報ゲインスコアランキング（「鍋」（1）>「ライスヌードル」（0.31）>「レストラン」（0））を取得し、スコアの高い順に必要な特徴語を選択できます。

この論文では、IG 特徴選択法を採用して、スコアが最も高い上位 N 個の特徴語 (上位 30%) を選択します。上位20の特徴語を抽出します：[ホテル、ゲストハウス、鍋、写真、メガネ、美容、コーヒー、KTV、スタイリング、車、レストラン、ケーキ、子供、美容、ビジネス、旅行代理店、ウェディングドレス、クラブ、映画館、バーベキュー]。これらの特徴語は明らかにカテゴリ属性と関連しており、強い相関関係があるため、カテゴリ語と呼びます。

ドメイン知識に基づく特徴選択法

ルールベースの特徴選択アルゴリズムは、ドメイン知識を使用して特徴を選択します。現在、ルールベースの特徴選択アルゴリズムが単独で使用されることはほとんどありません。多くの場合、特徴選択を支援するために、統計学習特徴選択アルゴリズムと組み合わせて使用​​されます。

この論文では、POI 名フィールド内の短いテキストの自動分類の問題を解決する必要があります。POI 名フィールドは一般に、次の規則に従います: POI 名 = 名前のコアワード + カテゴリワード。名前の中核となる単語は実際のカテゴリ予測にはほとんど影響を与えず、場合によっては「過剰学習」を引き起こして悪影響を及ぼすこともあります。例えば、「Holiland Beef Ramen Restaurant」という名前の場合、「Holiland」がその名前の核となる単語です。学習アルゴリズムを使用すると、「ケーキ」カテゴリである可能性が非常に高くなります（「Holiland」と「ケーキ」カテゴリの相関関係は非常に強いため、誤った予測結論につながります）。

この記事では、このルールを使用して、特徴を選択するときにトリックを実行します。特徴選択によって取得された特徴語 (主にカテゴリ語) を使用して POI 名フィールドをセグメント化し、前半部分 (主に名前のコア語) を破棄して、残りを保持します。現在の評価結果に基づくと、このトリックにより精度が約 5% 向上します。欠点は、アルゴリズムのカバレッジが減少することです。

分類モデル

モデリング

特徴表現と特徴選択が完了したら、次のステップは分類モデルをトレーニングすることです。機械学習分類モデルは、1) 生成モデルと 2) 識別モデルの 2 つのタイプに分けられます。 2 つの生成モデルの違いは、サンプルの結合確率分布を直接モデル化することであると簡単に考えることができます。

生成モデルの難しさは、クラス確率密度分布 p(x|y) をどのように推定するかにあります。この記事で使用されている Naive Bayes モデルは、クラス確率密度関数を単純化し、条件付き独立性を前提としている点で「Naive」です。

p(x|y)の異なるモデリング形式に応じて、ナイーブベイズモデルは主に多変量ベルヌーイモデルと多項式イベントモデルに分類されます[4]。ベルヌーイ イベントはコイントス (0 と 1 の 2 つの可能性) に相当し、マルチ イベントはサイコロトス (1 から 6 つの可能性) に相当します。従来のテキスト分類と組み合わせたこれら 2 種類のモデルについて説明します。

多項式ベルヌーイモデル<br /> 既知のカテゴリの条件下で、マルチベルヌーイ対応サンプル生成プロセス: 辞書内の各単語 (t1、t2...t|V|) を走査して、単語がサンプルに出現するかどうかを判定します。各トラバーサルはベルヌーイ実験であり、|V| トラバーサルは次のようになります。

ここで、1(条件) は条件関数であり、条件が満たされた場合は 1 に等しく、条件が満たされない場合は 0 に等しくなります。|V| は辞書の長さを表します。

マルチイベントモデル

既知のカテゴリの条件下では、マルチイベント モデルはサンプル生成プロセスを想定します。テキスト内の k 番目の位置にある単語に対して、辞書から単語が選択され、各位置 k で生成された各単語はマルチイベントに対応します。サンプルX=(w1,w2...ws)のクラス確率密度:

ベクトル空間モデルを使用してサンプルを表す場合、上記の式は次のように変換されます。

ここで、N(ti,X)はサンプルXに特徴語iが出現する回数を表します。

パラメータ推定

さて、退屈な数式をいくつも解いた後、ようやく勝利の夜明けが訪れます。それはモデルパラメータ推定です。一般的な方法には、尤度推定、事後確率推定などがあります。この記事ではマルチベルヌーイモデルを使用し、マルチベルヌーイモデルのパラメータ推定の結論を直接示します。

特徴表現セクションでカウントされた term_category_frequency と category_frequency の 2 つのテーブルを覚えていますか?今こそその役割を果たす時です!パラメータ推定を完了するには、この 2 つのテーブルをクエリするだけです。うれしいですね。プロセスは少し複雑ですが、結果は良好です。パラメータの具体的な意味については、特徴表現のセクションを参照してください。

次のコーディングでは、注意する必要がある点が 2 つあります。

• パラメータ平滑化を使用してクラス確率密度 p(X | Cj) を計算する場合、特徴 ti がクラス Cj に現れない場合、p(ti | Cj) = 0 となり、クラス確率密度の乗算も 0 になります。サンプルの場合、特定の条件下で特徴が現れない場合、その発生の可能性はゼロであると見なされます。この結論はあまりにも恣意的です。解決策は、1 つの平滑化を追加することです。
  
  このうち、|C|はサンプルのカテゴリデータを表します。

• クラス確率密度を計算する際、複数の条件付き確率（小数）を掛け合わせると、コンピュータが表現できる最小の数値を超えてしまう可能性があります。小数オーバーフローの問題を回避するために、クラス確率密度の計算は一般に対数和形式に変換されます。
  
  さらに、計算時に p(ti | Cj) が小さすぎる場合、対数を取った後に負の無限大の値が得られるため、p(ti | Cj) を切り捨てる必要があります。つまり、特定のしきい値 (1E-6 など) 未満の場合は、代わりにしきい値が使用されます。

アルゴリズム予測

このセクションでは、前の 3 つのセクションの内容を組み合わせて、アルゴリズムの具体的な計算および予測プロセスについて説明します。問題を単純化するために、辞書は[ラーメン、セブンデイズ、牛肉、レストラン]であり、カテゴリは鍋とファーストフードの2つだけであり、両方のカテゴリのサンプル数は8であると仮定します。 「Holiland Beef Ramen Restaurant」を例に挙げてみましょう。

• テストサンプルに対して中国語の単語分割を実行し、「牛肉」がカテゴリ単語に属することを決定し、カテゴリ単語「牛肉」の前の部分を破棄し、サンプルの特徴語セットを抽出して、[牛肉ラーメン店]を取得します。
• 辞書によれば、ベクトル空間モデルを確立する：x = [1, 0, 1, 1]
• 分類予測に Naive Bayes モデルを使用して、鍋料理とファーストフードのサンプルの term_category_frequency 統計を示します。

サンプルがファーストフードに属する確率は火鍋の 4 倍高く、サンプルがファーストフードに属すると予測する信頼度は火鍋よりも大幅に高くなります。

アルゴリズムは、評価のために 2000 個の未調整 POI データをランダムに選択します。アルゴリズムには、カバレッジと精度という 2 つの評価指標があります。カバレッジとは、テスト サンプル セット全体でアルゴリズムが予測できるサンプル数の割合を指します。特徴選択を採用した後、一部の POI 名は特徴語セットを含まないため予測できず、アルゴリズム評価の範囲は 84% です。アルゴリズムの精度とは、テスト サンプル セット全体で予測できる正しいサンプルの割合を指します。アルゴリズム評価の精度は 91% です。

要約する

• 機械学習で問題を解決する上で最も重要なステップは、問題を特定することです。この問題は機械学習アルゴリズムを使用して解決できますか?もっと簡単な方法は他にありますか?文字列のマッチングなどの単純な問題は正規表現を使用して簡単に解決できますが、機械学習の方法は非常に面倒で、労力に見合いません。
• 機械学習アルゴリズムを使用できる場合、この機械学習の問題をどのように表現し、どのように特徴を抽出するのでしょうか?どのような機械学習モデルに分類できますか（分類、クラスタリング、回帰？）
• 問題を特定した後、オープンソースの機械学習ツールを試して、アルゴリズムの有効性を検証できます。必要に応じて、いくつかのマシン アルゴリズムを自分で実装することも、オープン ソースの機械学習アルゴリズムを参照することもできます。