1.類似度に基づく分類

現在の問題を解くために、過去の類似した出来事（事例）を参考にする方法があります。 これを「類似度に基づく方法」といいます。 人工知能の分野では、「事例に基づく方法（Instance based method）」とも呼ばれます。

この方法では、問題領域における「類似度」が非常に重要です。 まず例として座標空間に点がいくつかおいてある状況を考えます。 この場合、おかれた点が過去の出来事、つまり過去の事例です。 それに対して、新しく点が置かれたとします。これが現在の問題です。 座標空間上ではユークリッド距離が定義されるので、これを用いて類似度を算出することができます。

では、現実の世界ではどうでしょうか。 実際に分類したい問題を、座標空間で表現するのには限界があるでしょう。 確かに、特徴を軸で表現し、値を割り当てれば表現することが可能です。 しかし、数字で表されないような事例を表現するのは困難です。

この研究は、事例の表現に依存しない定義を持つ類似度を用いて、分類をしようという研究です。

分類問題

事例の分類を予測する問題を「分類問題」と呼びます。 これは、各事例を識別するための要素である、 「分類（クラス）」という値を予測する問題です。

例をあげて考えてみましょう。 ここでは「テニスができるか、できないか」という分類について考えてみます。 この場合、過去の事例とは、今までテニスをした、あるいはできなかった日の状況です。 天気に関する情報や、人数が集まったか、などさまざまです。 分類は言うまでもなく「今日、テニスができるか」です。 今日の状況を過去の事例と比較します。そこで、今日の状況が、 どちらの分類に対して似ているのかを類似度を用いて比較します。 その結果を用いて、「今日、テニスができるか」を予測します。

このように、過去の事例との類似を参考にして、現在の問題を解くわけです。 過去の事例は、整理されているとは限らず、さまざまな形式を持っています。 そのため、これらを統一的に扱うことのできる手法が必要となります。

データ形式に依存しない類似度

データ形式に依存しない類似度として、山田による類似度が提案されています。 これは確率の言葉を用いて定義される類似度です。 式で表すと以下のようになります。

類似度(事例X，事例Y)　＝　P(２つの事例のクラスが一致｜２つの事例が与えられた)

つまり事例が２つ与えられ、その分類が一致する確率で、類似度が与えられます。

類似度算出の方法

それでは具体的に類似度を算出する方法について説明します。上記の通り、類似度は「２つの事例が与えられた条件の下で」クラスが一致する確率で与えられます。つまり、まず２つの事例を得ます。ここで、２つの事例を結合することによって得られるものを持つことで、２つの事例を得ることとします。この２つの事例の関係を情報として持つ事例、「結合事例」を用いて類似度を算出します。この結合事例は、事例として２つの事例の関係、分類が一致するかどうかをクラスとして持ちます。この事例結合がこの手法では重要です。

この分類手法は最初にも述べたように、「事例に基づく方法」ですから、今まで起こったこと（過去の事例）を用いて分類します。従って類似度も過去の事例を用いて算出します。そのために、前処理をしておく必要があります。前に述べたような事例の結合を、過去の事例データベースにおいて行います。ここでは、可能な組み合わせだけ実行します。これによって結合事例集合が生成されます。

それではいよいよ類似度を算出します。分類したい未分類事例と過去の事例の１つを結合します。未分類事例はクラスがわからないので、生成される結合事例は分類の一致に関する記述は持ちません。これと結合事例集合を用いてこの２つの事例間の類似度を求めることができます。結合事例集合から事例の記述が一致しかつ分類の記述が一致となっている事例の数を数えます。これを結合事例集合のもつ事例数で割った値が類似度となります。

理論的には上記の通りですが、過去の事例というものにある程度制限がある場合、ナイーブベイズの仮定を用いて存在確率を高める操作を行います。この類似度を使った重み付け多数決を用いて未分類事例のクラスを推測します。

現在の状況と今後の課題

現段階では事例が属性表現されていれば、分類が可能となっています。分類方法を変化させ、分類対象にあった方法を見つけることは可能ですが、これを静的に決定することはできていません。実際に分類をしたい状況では、さまざまな手法より、もっとも適した唯一の方法があればいいわけなので、その枠組みについて考える必要があります。

結合事例集合は、訓練事例集合に対して事例数が大きくなるため、時間計算量と空間計算量の改善が必要です。明日の天気を知りたいのに結果が出るのが明後日では意味がありません。

ここではあまり細かくは述べませんが、まだまだ実験をするというレベルであるということです。分類器は実際に分類したい状況で分類ができなければ意味がないので、そのような場面を想定した改良というのが今後の大きな課題であると思います。

参考文献

Tom m. Michell. Machine Learning. McFraw-Hill Companies,Inc,1997.

Yasuhiro Yamada, Nobuhiro Inuzuka, and Hirohisa Seki. Map classification with a similarity measure. In Proceedings of The IASTED International Conferernce on Artificial and Computational Intelligence,pp155-200,2002.

山田泰大.確率論を用いた類似性尺度による事例分類に関する研究.修士論文、名古屋工業大学、2003

Sahibsingh A. Dudani. The distance-weighted k-nearest-neighbor rule. IEEE Transactions on System, Man and Cybernetics,2003

D.Randall Wilson and Tony R.Martinez. Improved heterogeneous distance functions. Jounal of Artificial Intelligence Research,1997

C.L.Blake and J Merz,C. Uci repository of machine learning databases.

J.Ross Quinlan. C4.5:Programs for Machine Learning.Morgan Kaufmann Publishers,Inc,1993.