next up previous
次へ: 実際のデ―タによる実験 上へ: 日程表作成実験 戻る: 日程表作成実験

人工的に作ったデ―タによる実験


表 5.1: 人工的に作った相伴表
\begin{table}\begin{center}
\psfig{file=images/table-5.1.eps, width=140mm}\end{center}\end{table}


まず、全ての場合を調べ上げることが可能な比較的小さなデータを人工的に作り、提 案手法で得られた結果と最適解を比較した。表5.1が項目と関係者の 相反表である。この表をもとに、1日の許容会議数を4とし、4日間の日程表を作る とする。表 5.2および表5.3が最適解および各手法の結果である。


表 5.2: 人工データに対するクラスタリングの結果
\begin{table}\begin{center}
\psfig{file=images/table-5.2.eps, width=140mm}\end{center}\end{table}



表 5.3: 人工データに対して作られた日程表
\begin{table}\begin{center}
\psfig{file=images/table-5.3.eps, width=140mm}\end{center}\end{table}


K-L展開による手法および数量化3類による手法は、表5.2では全く同 じ結果になっている。実際の分割は、表5.3 a) および b) のように 多少異なっているが、両者はかなり似た傾向にある。

タイの処理をしない測度 $m$ を用いる手法は、K-L展開による手法および数量化3類 による手法よりも良い日程表を作っている。タイの処理をすることによって、結果が さらに改善され、最適解が得られている。また、Jaccard の Matching Coefficientを 用いる手法も最適解を与えている。

図 5.1: 延べ出席日数と可能な日程表の個数の関係
\begin{figure}\begin{center}
\psfig{file=images/fig-5.1.eps, width=140mm}\end{center}\end{figure}

5.1は延べ出席日数と可能な日程表の個数の関係を示したヒストグラ ムである。ただし、日程表の個数は、各クラスターを第何日に割り当てるかによって 生じる日程表の差を区別して数えている。この図から分かるように、延べ出席日数の 期待値は、約32日である。つまり、いい加減に作っても延べ出席日数がほぼこの程 度の日程表ができることになる。

図ではほとんど読み取れないが、最適解(タイの処理をした測度mを用いる手法、 JaccardのMatching Coefficientを用いる手法によって得られた日程表)と同等な日 程表の個数は24個である。つまり、各クラスターを第何日に割り当てるかによって生 じる日程表の差を無視すると、最適解は一通りである。タイの処理をしない測度mを 用いる手法により得られた日程表と同等な日程表の個数は4152個であり、K-L展開 による手法および数量化3類による手法で得られた日程表と同等な日程表の個数は 66648個である。これに対して、延べ出席日数32日の日程表の個数は3241512個であ る。これらの結果から、タイの処理をした測度mを用いる手法およびJaccardの Matching Coefficientを用いる手法は、非常に優れた手法であることが分かる。また、 K-L展開による手法あるいは数量化3類による手法で作られた日程表もまずまずの 日程表であることが分かる。

さらに、計算時間の点でも、直接最適解を求めるために、VAX-11/780で18時間近く の計算が必要であるのに比べ、ここで述べた手法の計算時間は2秒以下であった。



Takio Kurita 平成14年7月3日