中国料理店過程 (Chinese Restaurant Process)の概要とアルゴリズム及び実装例

機械学習技術 人工知能技術 デジタルトランスフォーメーション技術 確率的生成モデル スモールデータ ベイズ推論による機械学習 ノンパラメトリックベイズとガウス過程 python 経済とビジネス 物理・数学 本ブログのナビ
中国料理店過程 (Chinese Restaurant Process)の概要

中国料理店過程 (Chinese Restaurant Process, CRP) とは、”ディリクレ過程（Dirichlet Process, DP）の概要とアルゴリズム及び実装例について“でも述べているディリクレ過程 (Dirichlet Process, DP) を直感的に説明するために用いられる確率モデルとなる。特にクラスタリング問題に頻繁に使われている。

CRPのルール: 中国料理店のたとえ話として次のように説明されている。

  • 無限にテーブルがある中華料理店がある。
  • 最初のお客さんは適当に1つのテーブルに座る。
  •  2番目以降のお客さんは次のルールに従う：
    • すでに誰かが座っているテーブルに座る確率は、そのテーブルに座っている人数に比例する。
    • 新しいテーブルに座る確率は、ある定数\(\alpha\)に比例する。

これらは数式で表すと以下のようになる。

  • 既存のテーブル\(k\)に座る確率:\[P(既存のテーブルkに座る確率)=\frac{n_k}{n+\alpha}\]\(n_k\):テーブル、k:kに座っている人数、n:これまでに来店した全お客さんの数、\(\alpha\):新しいテーブルに座る確率を制御するパラメータ
  • 新しいテーブルに座る確率：\[P(新しいテーブルに座る確率)=\frac{\alpha}{n+\alpha}\]

CRPの特徴

  • リッチ・ゲット・リッチャー効果 (Rich-get-richer effect)：人が多いテーブルほど新しいお客さんが座る確率が高くなり、大きなクラスターが生まれやすい。

  • 無限次元性：テーブルの数は無限にあるため、新しいテーブル (クラスタ) を追加する可能性が常に存在する。

  • ディリクレ過程との関係：CRPはディリクレ過程による分布サンプリングを具象的に表したもの。ディリクレ過程\(DP(\alpha,H\)におけるクラスタリングの振る舞いを説明するためにCRPが利用される。

応用としては以下のようなものがある。

  • 無限混合モデル：クラスタ数が事前に決まっていない場合のデータクラスタリング
  • 自然言語処理：トピックモデル (HDP-LDA など)
  • 推薦システム：ユーザーの好みを無限のカテゴリに動的に割り当てる
  • 遺伝子解析：未知の遺伝子型を発見するモデリング
実装例

Pythonを使った中国料理店過程 (CRP) のシンプルな実装例について述べる。

import random
import matplotlib.pyplot as plt

# パラメータ α (新しいテーブルに座る確率を制御)
alpha = 1.0
n_customers = 100  # お客さんの数

# 各テーブルの人数を格納するリスト
tables = []

# CRPのシミュレーション
for i in range(n_customers):
    if random.random() < alpha / (len(tables) + alpha):
        # 新しいテーブルに座る
        tables.append(1)
    else:
        # 既存のテーブルに座る (確率に比例)
        table_probabilities = [count / (len(tables) + alpha) for count in tables]
        chosen_table = random.choices(range(len(tables)), weights=table_probabilities)[0]
        tables[chosen_table] += 1

# 結果を可視化
plt.bar(range(1, len(tables) + 1), tables)
plt.xlabel('Table (Cluster) Number')
plt.ylabel('Number of Customers')
plt.title('Chinese Restaurant Process Simulation')
plt.show()

print(f"Total tables (clusters) formed: {len(tables)}")

コードの解説

  1. パラメータ設定

    • alpha：新しいテーブルに座る確率を制御。値が大きいほど新しいテーブルができやすい。
    • n_customers：お客さんの数 (= データポイントの数)。

  2. CRPのルール

    • 新しいテーブルに座る確率：\(\frac{\alpha}{n+\alpha}\)​
    • 既存のテーブル\(k\)に座る確率:\(\frac{n_k}{n+\alpha}\)

  3. 可視化: 最終的に何個のテーブル (クラスタ) ができたかを可視化して、棒グラフで確認。

実行結果のイメージ

  • \(\alpha\)が小さい場合 → 大きなテーブルが支配的 (クラスタ数が少ない)
  • \(\alpha\)が大きい場合 → 新しいテーブルが増えやすく、クラスタ数も増加
適用事例

中国料理店過程 (CRP) の具体的な適用事例について述べる。

1. 混合モデルにおけるクラスタリング

事例：テキスト分類や画像分類

目的：事前にクラスタ数を決めずに、データから動的にクラスタを推定する。

応用：

    • テキスト分類：文章から未知のカテゴリを発見する (ニュース記事の自動分類など)
    • 画像分類：画像の特徴量をもとに、ラベルなしデータからグループ化

効果：データに応じたクラスタリングが可能になるため、新しいカテゴリ (テーブル) の追加も柔軟

2. トピックモデル (HDP-LDA)

事例：自然言語処理 (NLP)

目的：文書中のトピック数を事前に設定せず、トピックを自動的に推定する。

応用：

    • ニュース記事のトピック抽出
    • ソーシャルメディア投稿のトピック推定
    • 口コミレビューのトピック解析

効果：従来のLDA (潜在的ディリクレ配分法) ではトピック数\(k\)を手動設定する必要があったが、CRPを用いると動的にトピックが増減可能

3. 遺伝子解析

事例：バイオインフォマティクス

目的：遺伝子発現データをクラスタリングし、未知の遺伝子グループを発見する。

応用：

    • 未知の遺伝子型の発見
    • 疾患ごとの遺伝子パターンの抽出
    • DNA配列のグループ化

効果：新たな遺伝子パターンが発見されるたびに新しいクラスタ (テーブル) が追加され、柔軟なモデルが構築可能

4. 推薦システム

事例：Eコマースや動画ストリーミングサービス

目的：ユーザーの好みに応じたカテゴリ (テーブル) を動的に生成し、新たな嗜好グループを見つける。

応用：

    • 映画推薦：新作映画が登場するたびにクラスタ (ジャンルやテーマ) を増やす
    • ECサイトの推薦：ユーザー行動から新たな購買傾向を検出

効果：クラスタ数を固定しないため、ユーザーの好みが変化しても新たなグループに柔軟に対応可能

5. 異常検知 (Anomaly Detection)

事例：サイバーセキュリティ

目的：従来のパターンに属さない異常行動を、新しいクラスタ (テーブル) として動的に識別する。

応用：

    • ネットワーク異常検知
    • 不正アクセスの検出

効果：未知の攻撃手法が発生した場合でも、新しいクラスタとして即座に追加され、リアルタイム検知が可能

参考図書

中国料理店過程 (CRP) や関連するベイズ非パラメトリックモデルに関する参考図書について述べる。

1. Bayesian Nonparametric Statistics

2. Pattern Recognition and Machine Learning — Christopher M. Bishop

  • 概要：CRPやディリクレ過程を含む確率モデルとクラスタリングの基礎を網羅。グラフィカルモデルや変分推論なども学べる。
  • おすすめポイント：機械学習との関連性を理解したい方に最適。

3. Machine Learning: A Probabilistic Perspective — Kevin P. Murphy

4. Fundamentals of Nonparametric Bayesian Inference

5. Chinese Restaurant Process, Stick Breaking Process, and Dirichlet Process Mixture Model

コメント

モバイルバージョンを終了
タイトルとURLをコピーしました