汎化を用いた構造規則の生成アルゴリズム

汎化を用いた構造規則の生成の手順を以下に示す。

1.

すべての学習データを最終的に得られる構造規則とする。

2.

それらの構造規則を少しづつ汎化して一般的な構造規則を生成していく。

ここで汎化とは、階層構造を持つ属性のあるノードをひとつ上の親ノードに変更 することにより、より抽象度の高いノードにしていく操作である。

3.

汎化の過程で、汎化の対象としている属性が以下の2つの条件のどちらかを満た した時、その属性に対する汎化を終了させる。

(a)

あるノードを汎化した時、他のクラスの領域と重複した場合（図 3.1参照）  

(b)

あるノードを汎化した時、その汎化によって新しい用例が包含されない場 合  

4.

2.と3.を繰り返し、どの属性も汎化できなくなった時、最終的に処理を終了させる。

条件 3aについては、実際にはノイズを考慮に入れ、次のように条件を緩くする のが良いと思われる。

あるノードを汎化した時、他のクラスの領域を包含する場合でも、不正解率があ る一定の閾値内であれば、他のクラスの用例をノイズとみなし、汎化していく。

これは決定木の枝刈り（pruning）に相当する。この時の最適な閾値は、学習デー タに依存するので実験的に得る必要がある。

条件 3bは、構造規則の記述は、より広い範囲をより詳細な規則で記述するとい う一般的な規則の記述の方針に従って、それ以上汎化可能であっても、汎化をス トップする。これにより、必要な範囲だけをカバーする構造規則が得られ、人間 がみて理解しやすい構造規則が得られる。なお、テストデータに構造規則を適用 する時、どの構造規則にも当てはまらない場合もあるので、デフォルトルールを 作成しておく必要がある。

  

Figure 3.1: 汎化の過程の例