ルール導出

 

まずは、ルール導出の手続きについて検討する実験を行った。

最初の実験は、(1)〜(4)を対象に

• ./atom 3 (空白または改行で区切られる文字列がアトム)
• ./atom 0 (1文字がアトム)

の2つの解析子、さらに一般の UNIX コマンドである file -, wc -c を用いて行った(実験

)。 対象としている文書集合のうち、(1) はファイルの種類を出力する file - によって、(2) は file - に加えて、ファイルサイズを出力する wc -c によって明確に分類ルールが表現されるように選んだ集合である。 そこで、これらの2つのコマンドも試験的に解析子として加えている。 これらは ./atom のようにアトムを返すのではないので、頻度解析は行わ ず、返されるアトムを直接扱い、被覆率と適合率を同様に計算して評価している。

この実験では、混合区間や出現区間といった、曖昧な区間をルールとして導出し ないようにしている。 また、閾値は初期値を とし、 ずつ下げていった。 但し、4つの解析子をそれぞれ適用して解析する間に、1つでもルールが導出され た場合には、同じ閾値のままで繰り返し解析を行うようにした。

この実験の結果をまとめると表 5.2のようになる。

  
表 : 実験 の結果

まず言えることは、ルールが冗長だということである。 各グループについて最適なルールが導出できる場合には、1つのグループを1つの ルールが説明できることになるため、導出されるルール数の最小値はグループ数 である。 そのため、対象としている文書集合が単純で明確な基準に基づいて分類されてい る場合には、導出されるルール数はグループとほぼ同じか、少し多いくらいにな るはずである。 特に (1) と (2) は明確に分類ルールが導出されるように故意に選んだ文書集合 であるのだが、導出されたルール数は、(2) ではグループ数の 倍にもなっ ている。 この理由の1つは、閾値の初期値を と小さくしすぎたためである。 そこで、 から ずつ小さくするようにすると、(1) は3ルール、(2) は8ルールと小さくなった。 もう1つの理由として、混合区間や出現区間を考慮していないことによって、区 間幅が小さすぎるルールが多量に導出されてしまったことが挙げられる。 つまり、図 4.5のようなケースでも3つの区間がルールとして導出 されてしまい、数が多くなってしまった。

次に実行時間を見ると、文書数の増加に伴い、およそ文書数の2乗に比例して時 間がかかっている。 これを改善するために、システムがルールを導出する様子を詳しく見てみた。 表 5.3は、(4)のルール導出をステップ毎に見たものである。 一見して、何もルールが導出できていない無駄なステップが多いことが分かる。 特に、解析子に file - や wc -c を用いた場合や、同じ閾値で2度 目、3度目の解析を行った場合に無駄が生じている。 file - や wc -c でルールが導出できないのは、対象が実際のメイ ルであるということから考えて当たり前だろう。 この2つの解析子は(1)と(2)からのルール導出をはかるべく導入したものである し、実際のメイルはそのような観点では分類していない。 一方、同じ閾値で繰り返した際には、2度目にはほとんどルールが導出できない、 ということから、ルール導出の成否によらず、閾値は下げていくべきという結論 になる。

  
表 : 実験 の(4)の途中経過

以上のことを踏まえて、同じ文書集合に対し、 度目の実験を行った(実 験 )。 今度は

• ./atom 3 (空白または改行で区切られる文字列がアトム)
• ./atom 0 (1文字がアトム)

の2つの解析子のみを用いて行った。 また、閾値の初期値を

とし、また、閾値の下げ幅を、全ての解析子につ いてルール導出を試みた結果導出されたルールと、それに応じて削除された文書 数によって、

とした。 さらに、混合区間、出現区間についても考慮するようにした。 この結果は表 5.4の通りである。 実行時間と導出されたルール数が大幅に改善されていることが分かる。

  
表 : 実験 の結果

また、(4)のルール導出をステップ毎に見ると、表 5.5のようにな る。 各ステップ毎にほとんど無駄なくルールが導出された。 尚、ステップ11以降は .mh_sequences 等の本質的でないファイルが残っ ているだけであるので、実質ステップ10(閾値40%)で解析は終了していると見る べきである。

  
表 : 実験 の(4)の途中経過

ところで、(3), (4) のように文書数が多くなってくると、閾値がだいぶ低い値 にならないとルールが導出できなくなってくる。 特にグループ内の文書数が多い場合に、この傾向が強く見られる。 それは、文書数が多いグループは分類の観点が複合的で、単純に1つのルールで は分類が説明できないためであると考えられる。 複数の観点から成るグループは、それぞれのルールの被覆率が下がってしまい、 閾値が高いと導出されない。 そこで、そのグループがいくつのルールで説明できるかによって、閾値を下げる ことにする。 もし3つのルールから成るのであれば、各ルールの被覆率は平均 に なるため、閾値を に下げれば良い。

そのため、グループ内の文書数と導出されるルール数の関係を実験で調べた(実 験 )。 (4) のうちの 10% の文書を対象に、

• ./atom 5 (一連の英数字、一連の同種日本語文字、一連の記号列)

を解析子としてルールを導出した。 その結果が図 5.1である。 横軸がグループ内の文書数、縦軸が導出されたルール数である。 グラフ中には、

の3式の曲線も描かれている。 これらの式は、文書数が100の時にルール数が6になるように係数を揃えて ある。 このグラフより、補正閾値を

と定めることにした。

  
図 5.1: グループ内の文書数と導出されるルール数

吉田 誠一のホームページ に戻る。
Sat Mar 8 05:59:11 JST 1997