9.3 PRIM: データの中の「宝の山」を探す

データの海の中に、応答変数が特に高い「山」が隠れている—— その山だけを精密に掘り当てるアルゴリズムがあります。

PRIM（Patient Rule Induction Method）は、空間全体を分割するのではなく、「最も重要な局所領域」だけを丁寧に切り出す手法です。その名の通り、「辛抱強く」データを削り続けながら宝を探します。

なぜ「箱」を探すのか？

あなたは医療研究者で、何千人もの患者データを持っています。「どんな患者グループが特定の治療に最もよく反応するか」を見つけたい。

でも、データ全体の平均を見ても意味がありません。知りたいのは「特定の患者像」——年齢、体重、血液数値が特定の範囲に収まる患者たちだけの平均応答です。

こう考えてみてください。データ空間の中に「山（bump）」が存在します。応答変数が特に高い局所的な峰——その山を見つける旅がバンプ・ハンティング（Bump Hunting）です。

2D散布図で高応答領域（赤い点）が一角に集まり、箱がその領域を囲んでいく様子 — 全体を囲む大きな箱が、応答の高い点だけを包む小さな箱へと収縮していく

この「山」は、変数のある範囲内にある観測値が集まった領域として表せます。たとえば「年齢が40〜60歳かつ血糖値が110〜150」のような条件の組み合わせ—— これを「箱（Box）」と呼びます。

PRIMはこの箱を発見するアルゴリズムです。名前の意味は Patient Rule Induction Method——「辛抱強いルール誘導法」。なぜ「辛抱強い」のかは、アルゴリズムを見るとすぐわかります。

上のアニメーションを見てください。青い点（応答が低いデータ）が全体に散らばる中、赤い点（応答が高いデータ）は右上の一角に集まっています。 PRIMは、この「宝の山」をデータ全体の中から精密に掘り当てる手法です。

「剥ぎ取り」の直感（Peeling）

PRIMの直感的なイメージは「箱を少しずつ削る」ことです。

まず全データを一つの大きな箱に入れます。

次に、箱の一面を「少しだけ」圧縮します。たとえば、箱の右端を左に少し動かして、最も右端にいるデータを箱の外に追い出す。あるいは、箱の下端を上に少し動かして、最も下にいるデータを追い出す。

どちらの方向に圧縮するか？——答えは簡単です。圧縮後に、箱の中に残ったデータの平均応答が最も高くなる方向を選ぶ。

大きな箱から始まり、一面ずつ剥ぎ取られていく過程と、対応する箱内平均の上昇を示す2パネルアニメーション — 左：矩形が縮小されていく様子。右：箱の中のデータの平均応答が上昇していく（各ステップが連動している）

これを繰り返すと、箱はだんだんと「応答が高い点だけが残るエリア」に絞られていきます。右パネルの棒グラフが上昇し続けているのに注目してください—— 剥ぎ取るたびに、箱の中に残るデータの質が上がっていくのです。

各ステップで追い出すデータの割合を $\alpha$ と呼びます。典型的には $\alpha = 0.05$ （5%）または $\alpha = 0.10$ （10%）—— 一度に少しずつ削るのがポイントです。

\text{剥ぎ取り後の箱内平均} = \frac{1}{|B \setminus \delta B|} \sum_{x_i \in B \setminus \delta B} y_i

式の意味は単純です。箱 $$B$$ から端の部分 $\delta B$ （全データのα割合）を取り除いた後の箱の中に残るデータの平均を計算する、ということです。

そして剥ぎ取りが終わった後、今度は逆に「箱を少し広げる（Pasting）」も試みます。貪欲な剥ぎ取りで行き過ぎた部分を修正するためです。 Pasting は、Peeling によって除外されてしまった良いデータを回収するための修正ステップです。

CARTとPRIMの違い

決定木（CART）という手法をご存知ですか？データを「条件で二分割」し続けるツリー状の分類・回帰手法です。「年齢が40歳未満か以上か」で二分し、さらに「血糖値が120未満か以上か」で二分し……という具合です。

CARTとPRIMは同じ目的——「データからルールを見つける」——に向かいますが、アプローチが根本的に違います。

CARTの思想: 空間を「均等に二分割」し続ける。全体のデータを説明しようとして、すべての領域を細かく分割する。

PRIMの思想: 「応答が特に高い小さな箱」だけを丁寧に掘り出す。全体を分割するのではなく、「宝がある一角」を精密に切り出す。

左がCARTの素早い二分割、右がPRIMのゆっくりとした一方向ずつの収縮を示す並列比較アニメーション — 左（CART）: 素早い二分割が繰り返され細かいモザイク状になる。右（PRIM）: 一方向ずつゆっくりと縮小し小さな箱に収束する

この違いは哲学の違いです： CARTは「木の全体構造」を大切にし、PRIMは「最も重要な場所」を大切にする。

さらに重要な違いがあります——ステップ数です。

CARTはN個のデータから最大何回分割できるでしょうか？

\text{CARTの最大分割数} = \log_2(N) - 1

N=128なら、わずか6回の分割で終わりです。これは、二分割を繰り返すと葉の数が2倍ずつ増え、 N個のデータ点を超えるまでの回数が上限になるためです。

でもPRIMは？αで少しずつ剥ぎ取るので、ステップ数がはるかに多くなります。

\text{PRIMの最大ステップ数} \approx \frac{-\log(N)}{\log(1-\alpha)}

$\alpha = 0.10$ の N=128 データなら約46回のステップが可能です。

CARTが「大きなノコギリで6回切る」なら、PRIMは「精密なメスで46回削る」—— これがPRIMの名前の由来「辛抱強さ（Patient）」です。

項目	CART	PRIM
分割戦略	二分割（速い）	一面ずつ剥ぎ取り（丁寧）
ステップ数（N=128、α=0.10）	最大6回	最大約46回
目的	空間全体を説明する	最高応答の局所領域を発見する
結果	ツリー構造（複数ルール）	箱（シンプルなルール）

複数の「箱」を発見する

一つの箱を見つけたら終わりではありません。

PRIMの真の力は、複数の箱を順番に発見できる点にあります。

最初の箱 $$B_1$$ を見つけたら、その中のデータをすべて削除します。そして残りのデータに対して同じプロセスを繰り返します—— $$B_2$$ の発見。さらに $$B_2$$ を削除して $$B_3$$ を発見……という連鎖です。

散布図上で第1の箱（黄色）が左上の高応答点を囲み、そのデータが消えた後に第2の箱（緑）が右下を囲む2段階プロセス — 第1の箱（黄）で高応答ゾーンを発見し、そのデータを除いた後に第2の箱（緑）で次のゾーンを発見する

各箱のサイズは「どれだけのデータを含むか（Box Support）」で測ります。大きすぎる箱は不純物が多く、小さすぎる箱は統計的に不安定です。クロスバリデーション（データを複数に分割して評価する手法）で最適なサイズを選びます。

実際にスパムメール識別データにPRIMを適用した結果を見てみましょう：

箱1（Rule 1）: 8つの変数の条件を組み合わせたルール。テストデータの約15%を含み、100%がスパム
箱2（Rule 2）: remove > 0.010 かつgeorge < 0.110 というシンプルな2条件。テストデータの約11%を含み、92.6%がスパム

2つの単純なルールだけで、データの26%をカバーし97%がスパム—— 機械学習の専門知識がなくても、そのまま使えるルールが自動的に得られます。

ポイントは「発見した箱のデータを削除してから次の箱を探す」という手順です。アニメーションで確認してください——黄色い箱の点群が消えてから、緑の箱が次の高応答ゾーンを見つけに行きます。この連鎖によって、データ空間の複数の「宝の山」を一つずつ掘り当てていけるのです。

PRIMアルゴリズムの全体像

ここまでの内容を整理しましょう。PRIMの正式なアルゴリズムは次の6ステップです：

Step 1: 全訓練データを含む最大の箱からスタート
Step 2: 箱のすべての面について「α割合のデータを外に出す」圧縮を試み、圧縮後に箱内の平均が最大になる面を選択
Step 3: 最低限の観測数（例：10点）になるまでStep 2を繰り返す
Step 4: 箱の各面を拡張してみて、平均が上がるなら拡張（Pasting）
Step 5: 得られた箱の列から、クロスバリデーションで最適サイズを選択 → これを $$B_1$$ とする
Step 6: $$B_1$$ のデータを削除し、残りのデータにStep 2〜5を繰り返す → $B_2, B_3, \ldots$

上段（CART）は長いバーが6回に急速に分割される。下段（PRIM）は長いバーが多くの小さなステップでゆっくり短くなる比較アニメーション — 上（CART）：少ない回数の大きな分割。下（PRIM）：多くの小さなステップで少しずつ絞り込む

アニメーションを見れば、「辛抱強さ（Patient）」の意味がよく分かります。 CARTが6回の大きな切断で終わるのに対して、PRIMは何十もの細かいステップを丁寧に繰り返しながら、最適な箱を探し続けるのです。

箱の数学的定義

B_k = \{x : a_j \leq x_j \leq b_j, \; j \in S_k\}

$$p$$ : 特徴量（変数）の総数
$$j$$ : 各特徴量の番号（1番目, 2番目, ..., p番目）
$$a_j, b_j$$ : 特徴量 $$X_j$$ の下限と上限
$$S_k$$ : 第k箱で使われる変数の集合

つまり「使用する各変数について上限・下限を設定した直方体」が箱の正体です。年齢40〜60かつ血糖値110〜150 → これが数式で言う「箱 $$B_k$$ 」です。

PRIMの強みと弱み

強み	弱み
単純なルール（箱）で表現できる	2クラスより多いクラスへの対応が難しい
局所的な高応答域を精密に発見できる	計算コストはCARTより高い
変数の組み合わせを自動的に発見できる	バイナリ木の制約がないため解釈が複雑になることも
「辛抱強い」ので過剰分割を避けられる

冒頭の医療研究者の問いに戻ると、PRIMを使えば「45歳以上で血糖値が120以上かつ体重が70kg未満の患者」のような条件の組み合わせを自動的に発見できます。空間全体を分割する決定木と違い、最も重要な患者像だけを精密に浮かび上がらせる——それがPRIMの価値です。