決定木の構築とハッシュテーブルの生成

決定木の構築は次のステップにしたがって行われる。

1. 全てのトレーニングサンプル(各 LFS の分布関数)を保持した状態で、 木のルートから開始する

2. 非終端ノードにおいて、トレーニングサンプルがなるべく均等に分かれ るような分割法（test = (属性, 閾値)）によってサンプルを２分する。

3. ノードが１つの要素しか持たないか、もしくは「終了条件」によってこ れ以上分割できない場合、これを終端ノードとする。

4. 非終端ノードが残っている場合には、２へ戻る。

5. 終端ノードにクラス(LFS)のラベルを貼る。

Figure 2.7

前節で議論した通り、良いハッシュテーブルは不確かさの情報を活用するべき であるが、同じことが決定木を構築する上でも言える。MULTI-HASH では、サ ンプル点ではなく不確かさ分布を木の構築に用いる。サンプル点をそのまま用 いる欠点は、構築されたテーブルがサンプルに過適応（overfitting）してし まうことにある。特にサンプル数が少ないときに問題になり、分類時の比較回 数が多くなってしまう（木の深さが増える）。さらに木の構築時に用いる確率 の値が、木を下に下っていくに連れて、サンプル点を直接用いている場合は不 確かさ分布を用いる場合と比べてだんだん不正確になっていく。Figure 2.7 のブロックダイアグラムは、不確かさの評価を最初に行い、次にその不確かさ 分布をそのまま用いた決定木の構築処理を示す。

Figure 2.8 は決定木を構築するときの手続きを示す。最初に全てのモデルの LFS を含んだ状態でルートノードから出発し、各ノードにおいてその時存在す る LFSs を最も良く分離する分割法を探す。この時可能な限り、ある１つの属 性を用いて閾値で LFSs を分割する２分法を用いる。ノードを３つ以上に分割 することは、ここで用いるエントロピーの計算方法の下では最適な閾値を選択 するときに偏りをもたらすので、ここでは２分法が望ましい（[51]参照）。

決定木を構築する目的は、LFS を１つしか含まないノードを高速に発見するこ とであり、LFS を１つしか含まないと言うことはエントロピーが最小と言うこ とである。そのため、各ノードでは２つの子ノードに分割した時の平均エント ロピーが最小になるように分割を行う。ノード$n$ において、子ノードの平均 エントロピーは次のように表される。

$$E(n,test) = \sum^{\mbox{numberchildren}}_{i=1} P(n_{i}\vert n)H(n_{i})$$

ここで、$H(n)$ は次のように表される。

$$H(n) = -\sum^{J}_{j=1} p(\mbox{LFS}_{j}\vert n)\log{(P(\mbox{LFS}_{j}\vert n))}$$

where

$$P(\mbox{LFS}_{j}\vert n) = \frac{P(n\vert\mbox{LFS}_{j}) \times P(\mbox{LFS}_{j})}{P(n)}$$

$$P(n) = \sum^{J}_{j=1}P(n,\mbox{LFS}_{j})$$

$P(n\vert\mbox{LFS}_{j})$ は次のように与えられる。

$$P(n\vert\mbox{LFS}_{j}) = \int^{u_{1}}_{l_{1}} \dots \int^{u_... ...d^{q}_{i=1} \int^{u_{i}}_{l_{i}} f^{i}_{j}(a_{i}) \delta a_{i}$$

$A$ は全ての属性からなるベクトルであり、$f_{j}$ は $\mbox{LFS}_{j}$ に 対応する多次元確率分布である。$l_{i}$,$u_{i}$ はそれぞれルートから現ノー ドに至るまでの各属性軸での最高下限・最低上限を取る。

Figure 2.9

Figure 2.10

次に、これ以上ノードを分割しない分割停止条件について見る。ノードに１つ しか要素がない場合は当然停止する。それ以外の手続きは、Figure 2.9 に示 す通りである。停止するのは、どう分割しても子ノードの平均エントロピーが 現ノードのエントロピーより下がらない場合である。また、木の深さが増える に連れてハッシュテーブル内の領域が指数のオーダーで増えていくため、 5行 目のようにそれを抑制するためのメモリ量による拘束条件も入っている。さら に、Figure 2.10 のように現ノードの領域内で全ての LFS の分布が完全に重 なっている場合、どう分割しても子ノードで LFS の数を減らせないため、停 止する。

Figure 2.11

Figure 2.12

ここで分布が完全に重なっている場合でも、分割した結果個々の LFS の生起 確率分布が子ノード間で著しく異なるときには、さらに分割することも可能で ある（Figure 2.11）。Figure 2.12 に拡張した停止条件の手続きを示す。

Figure 2.13 参照

次にハッシュテーブルを構築するために、これまでの処理で導出された各ノー ド毎の分割法（属性：閾値のペア）を全て外部ファイルに書き出す。この時順 番は重要ではない。これに従って、多次元属性空間をパーティショニング（領 域分割）する。決定木では、現ノードに属する属性値空間を分割していたが、 ハッシュテーブルでは全体から参照される唯一の属性値空間を分割する （Figure 2.13 参照）。

ハッシュテーブルは、多次元空間で領域分割された各領域を１次元に並べた配 列で表される。これは、全ての属性で張る属性値の組を辞書順に並べた配列の 中で、対応するモデルの LFS が存在する個所にのみその LFS へのポインタを 入れていくことを行う。

Figure 2.14

属性が２つの場合の例を Figure 2.14 に示す。この時、属性値から対応する LFS （へのポインタ）を計算する式は下のようになる。

$$\begin{eqnarray*} TableIndex(a_{1},a_{2}) & = & LUT\_a_{2}(a_{2}) \times Num\_Seg\_a_{1} \\ & & + LUT\_a_{1}(a_{1}) \end{eqnarray*}$$

$a_{1}$,$a_{2}$は、Figure 2.13 で使われた属性値である。$LUT\_a_{i}$は、 属性値を対応するその属性軸上のセグメントにマップするルックアップテーブルであ る。 $Num\_Seg\_a_{i}$は、その属性軸上のセグメントの総数である。

テーブルの準備ができたら、それぞれのテーブルの領域はモデルの LFS への ポインタで満たされなければならない。あるモデルの LFS は、属性値空間上 でその不確かさ分布が重なるテーブル内の領域全てに入る。