(57)【要約】【課題】多次元データをそのまま扱って決定木を作成する方法では、データの次元数が増えてくると計算量が著しく増大する。計算量の減少を図り、分類に有効な属性に絞り込んだり、主成分分析を応用して次元数を減らという方法も提案されているが、属性の性質が不明な場合や有効な属性の数が多い場合には適用が困難である。【解決手段】各データ間の類似度指数をデータをベクトルとみなしたときのなす角度で定義して、各データが正負それぞれのクラスにどの程度従属しているかを、各データと正あるいは負に属するデータ群との類似度指数の平均値として定義する。元データの参照は１回だけであるので計算量が低減できる。【選択図】図９
2004126831.tif 000002
【特許請求の範囲】
【請求項１】
実数を属性値とする正規化されたｎ次元の各データが正クラスまたは負クラスいずれかのクラスに分類されるとき、各データ間の類似度指数をベクトルのなす角度で定義する手段と、
各データの正負それぞれのクラスへの従属度を各データと正クラスあるいは負クラスに属するデータ群との類似度指数の平均値として定義して２次元データを得る手段と、
２次元平面上に配置された前記データ点群を分割する直線の線形式を得る手段と、
このデータ群の分割操作と同値になるようにｎ次元のデータを分割する超平面を導出する手段、
とを構成要素とする決定木作成プログラム。
【請求項２】
実数を属性値とするｎ次元の各データが正クラスまたは負クラスいずれかのクラスに分類されるとき、データ点（ｘ１，ｘ２，．．．，ｘｎ）が原点以外の場合は（ｘ１２＋ｘ２２＋，．．．，＋ｘｎ２＋ｃ２）−１／２（ｘ１，ｘ２，．．．，ｘｎ，ｃ）へ、原点の場合は（０，．．．，０）を（０，．．．，０，ｃ）（ｃは実数）へとｎ＋１次元空間へ移すデータ変換手段と、
このｎ＋１次元の各データに対して、各データ間の類似度指数をベクトルのなす角度で定義する手段と、
各データの正負それぞれのクラスへの従属度を各データと正あるいは負に属するデータ群との類似度指数の平均値として定義して２次元データを得る手段と、
２次元平面上に配置された前記データ点群を分割する直線の線形式を得る手段と、
このデータ群の分割操作と同値になるようにｎ次元のデータを分割する超平面を導出する手段、
とを構成要素とする決定木作成プログラム。
【請求項３】
ｎ次元データの各属性値に重みづけをする手段を有することを特徴とする請求項１、２に記載の決定木作成プログラム。
【請求項４】
前記各属性値への重みづけが、多次元空間内でクラスの距離が離れるように正負クラスに属するデータの属性値の平均値と分散から算出されることを特徴とする請求項１から３に記載の決定木作成プログラム。
【発明の詳細な説明】
【０００１】
【発明が属する技術分野】
本発明はデータ分類に関するものであり、より詳細には、実数値データを対象とする２クラス分類用の決定木を作成するプログラムに関する。
【０００２】
【従来の技術】
２クラス分類のための学習データが与えられたとき、これを分類するモデルを構築し、新たな入力データに対していずれのクラスに属するかを予測するための手法は種々提案されてきている。決定木もそのひとつである。
【０００３】
本発明は多次元データを２次元データとして扱うことが肝要であり、本発明と技術的思想を同じくするものではないが、多次元データを超平面で分割する決定木の例として、特開２００２−１４８１６、特開２００２−１３３４１１を挙げておく。
【０００４】
また、本発明においては、データ間の類似度指数を用いて学習データの参照を１回で済ましているが、ニューラルネットの分野において同様の考え方が「動的類似度を用いたワンショット学習則」（日本神経回路学会誌，　Ｖｏｌ．２，　Ｎｏ．１，　ｐｐ．４−１０，　１９９５）等で提案されている。
【０００５】
【発明が解決しようとする課題】
多次元データをそのまま扱って決定木を作成する方法では、データの次元数が増えてくると計算量が著しく増大する。これは従来手法においては、多次元データを再帰的に参照することに起因する。計算量の減少を目的とし、分類に有効な属性に絞り込んで計算する方法や、主成分分析を応用して次元数を減らという方法も提案されているが、属性の性質が不明な場合や分類に寄与する属性の数が多い場合には適用が困難である。
【０００６】
【課題を解決するための手段】
本発明では元の多次元データを再帰的に参照することは行わない。
各データ間の類似度指数をデータをベクトルとみなしたときのなす角度で定義する。そして、各データが正負それぞれのクラスにどの程度従属しているかを、各データと正あるいは負に属するデータ群との類似度指数の平均値として定義する。
【０００７】
正規化された任意の二つのデータｘｉ＝（ｘｉ１，ｘｉ２，．．．，ｘｉｎ）、ｘｊ＝（ｘｊ１，ｘｊ２，．．．，ｘｊｎ）間の類似度指数
2004126831.tif 000003
をなす角度で定義して
【数１】
2004126831.tif 000004
とする。
【０００８】
ｐ個の学習データ
2004126831.tif 000005
の各々について
2004126831.tif 000006
を求め、類似度指数の行列Ｓ
【数２】
2004126831.tif 000007
を求めておく。
【０００９】
この結果については、後の処理において参照する必要があるため、メモリ空間上またはハードディスク等の記録媒体に保存しておく。
2004126831.tif 000008
2004126831.tif 000009
であり、Ｓは対角成分が１の対角行列であるので、実質的な保存データは半分の容量になる。
【００１０】
この類似度指数により、各データと正クラス、負クラスへの従属度を計算する。データｘ
の正負クラスの集合
2004126831.tif 000010
、
2004126831.tif 000011
への従属度を
【数３】
2004126831.tif 000012
【数４】
2004126831.tif 000013
とする。Ｎ＋は
2004126831.tif 000014
の要素数、Ｎ−は
2004126831.tif 000015
の要素数である。
【００１１】
2004126831.tif 000016
として２次元平面上にプロットする。
【００１２】
次いで、この平面上の点を２分割する直線を決定する。この直線で分割された領域Ａ、Ｂに属する点は、ある超平面で元データのｎ次元空間を２分割すると、Ａに属する点は一方の超空間に、Ｂに属する点はもう一方の超空間に集まるように、２次元平面での分割と同値に分割することができる。後に説明するが、この超平面は２次元平面での直線の線形式から導出される。
【００１３】
分割された領域毎に、その領域に含まれるデータの
2004126831.tif 000017
を用いて
2004126831.tif 000018
を計算し、
2004126831.tif 000019
をプロットし、２次元平面上で直線による分割を逐次繰り返してゆく。この分割が可能な状態を決定木でのノードに、分割された領域に正または負の一方のみとなった状態を決定木でのリーフに対応させて決定木を構築する。
【００１４】
本発明では、再帰的に参照するのは計算済みの類似度指数
2004126831.tif 000020
のみのため、多次元データの属性値を再帰的に参照する場合と比べて、計算量を大幅に減少させることが可能である。
【００１５】
２次元平面にプロットされた点をクラス分類する効率的な方法には、マハラノビスの距離、フィッシャーの方向、情報量エントロピーなどを使う方法などがある。特開２００２−１４８１６、特開２００２−１３３４１１にもこれらを応用した方法が提案されている。
【００１６】
ただし、本発明に於いては、ベクトルのなす角度で定義された類似度指数を用いてさえいれば、２次元平面を分割する直線は何でもよく、その方法は限定されない。
【００１７】
ここで上記の分割直線の線形式から元の多次元空間での分割超平面を導出する方法について説明する。
【００１８】
縦軸にＧ＋、横軸にＧ−をとり、分離直線ａＧ＋＋ｂＧ−＋ｃ＝０（ａ，ｂは係数項、ｃは定数項）が決定できたとする。
【数５】
2004126831.tif 000021
とおくと、
2004126831.tif 000022
は、それぞれ分割された領域を表す。式３、４を代入すると、
【数６】
2004126831.tif 000023
となり、これはｎ次元の超平面で分割することと同値である。
【００１９】
この分割により、片側の超空間に属するデータ点が一方のクラスのみになれば、それをリーフに、クラスが混合している場合はノードにそれぞれ対応させることにより、分割を再帰的に実行することで決定木が構成されてゆく。
【００２０】
ここまで、正規化されたデータについて説明してきたが、一般的には正規化されていないデータを取り扱うことが多い。実数値を属性値とするｎ次元データの類似度指数を角度で定義する場合には、原点を通る直線上に並ぶデータの類似度指数は同じになってしまう。これを避けるためには、請求項２にあるように、ｎ次元データをｎ＋１次元のデータへ変換する。
【００２１】
ｃを定数、ｏｎをｎ次元空間での原点として変換Ｔを次のように定める。
【数７】
2004126831.tif 000024
（ｃは実数）ここに、変換Ｔはｎ次元空間の点をｎ＋１次元において連続に移す。
【００２２】
Ｔがどのような変換であるかを簡単に説明する。簡単のため入力データは２次元とする。平面内の点（ｘ１，ｘ２）に対して３次元空間の点（ｘ１，ｘ２，ｃ）を与える。この点と原点を通る直線が、原点を中心とする半径１の球と交わる点が（ｘ１２＋ｘ２２＋ｃ２）−１／２（ｘ１，ｘ２，ｃ）であり、変換Ｔにより移される先である。
【００２３】
また、請求項３にあるように、ｎ次元データの各属性値に対して、予め重みづけをすることで、より効率良く分類することが可能な
2004126831.tif 000025
が与えられる。
【００２４】
例えば、データの特性が既知であり、属性値ｘｉに対して適当な重みａｉを乗じることが合理的であれば、ｘｉの代わりにａｉｘｉとすればよい。
【００２５】
適切な重みづけは分類能力を高めるので、データの特性が自明でない場合でも、請求項４にあるように、属性値の平均値と分散から算出される重みａｉを導入することが好ましい。以下にその方法について述べる。
【００２６】
ｎ次元のデータをｘ＝（ｘ１，ｘ２，．．．，ｘｎ）、正クラスを
2004126831.tif 000026
、負クラスを
2004126831.tif 000027
、
2004126831.tif 000028
の要素数をＮ＋、
2004126831.tif 000029
の要素数をＮ−とし、以下のように統計データ
2004126831.tif 000030
を求める。
【数８】
2004126831.tif 000031
【数９】
2004126831.tif 000032
【数１０】
2004126831.tif 000033
【数１１】
2004126831.tif 000034
【００２７】
また、区間［ｅｉ，ｆｉ］、［ｇｉ，ｈｉ］を
【数１２】
2004126831.tif 000035
【数１３】
2004126831.tif 000036
とする。Ａｉを区間［ｅｉ，ｆｉ］、［ｇｉ，ｈｉ］の交わりの区間の長さとし、次のようにａｉ（ｉ＝１，２，．．．，ｎ）を定める。
【数１４】
2004126831.tif 000037
【数１５】
2004126831.tif 000038
【数１６】
2004126831.tif 000039
ただし、区間［ｅｉ，ｆｉ］、［ｇｉ，ｈｉ］のいずれかが一方に包括される場合は、含まれた区間をＡｉとする。
【００２８】
以上の方法では、類似度指数を計算に用いることにより、多次元データの属性値を再帰的に参照しなくて済んでいる。つまり、学習データの参照は最初に類似度指数を計算するときの１回だけである。したがって、従来の多次元データの属性値を再帰的に計算に用いる方法と比べて、計算量を減少することができる。
【００２９】
【発明の実施の形態】
以下に実数を属性値とするデータを例に説明する。簡単のためデータは２次元とする。このデータは二つの入力と１または０のクラスのどちらに属しているかの組になっている。データの分布については図１、図２に示してあるように、クラス０（負クラス）の中で、クラス１（正クラス）が二つの領域に分かれた分布をしている。
【００３０】
このような分布をしている場合、１本の直線（多次元であれば超平面）で領域を分割し、片側にはクラス０のみ、逆側にはクラス１のみというようにはクラスを分割することはできない。現実の問題では多次元のデータであることが多く、分割はより困難になる。
【００３１】
このデータの特性が分かっており、クラス判別に対する各属性の寄与が明らかである場合には、属性値に対して適当な重みづけを行うことで、分類はより効率化される。
【００３２】
本発明では、データの特性が自明でない場合でも、統計データを用いた重みづけを行うことで分類能力を高めている。式８から式１６を図１のデータに適用すると、ｘに対して０．３７００２６、ｙに対して０．２７７４９６を重みとして乗じることになる。
【００３３】
本実施例では属性値が正規化されていないので、上記の重みづけを行って後、前述した変換Ｔをｃ＝１として
【数１７】
2004126831.tif 000040
を施す。ここまでの結果を図３に示す。図４は図３のデータをプロットしてあり、白丸がクラス０、黒丸がクラス１に対応する。
【００３４】
次いで、式１から式４を用いて、各データのクラスに対する従属度を求める。本例では図表示を分かりやすくするため、類似度指数を
【数１８】
2004126831.tif 000041
と定義した。この場合、式６は若干変化し、
【数１９】
2004126831.tif 000042
となるが、なんら一般性は失わない。
【００３５】
図５に計算結果を示す。図中ｓｉｍ−０、ｓｉｍ−１の項目が、それぞれクラス０、クラス１に対する従属度になっている。図６は横軸（Ｇ−）がクラス０に対する従属度、縦軸（Ｇ＋）にクラス１への従属度をとってプロットしてある。
【００３６】
次に、課題を解決する手段のところで述べたように、このＧ＋−Ｇ−平面で領域を分割する直線を定める。直線の取り方には限定がない。例えば、Ｇ−＝０．３やＧ＋＋Ｇ――０．５＝０といった分割直線をとれば、白点のみの領域と白黒混合の領域がとれるので、リーフとノードが生成することに対応する。あるいは、情報量エントロピーを利用した分割も適用できる。
【００３７】
本実施例では一般に広く知られるフィッシャーの方法で説明する。図６中の直線は、０．０５２５０５Ｇ＋＋０．０３１６４２Ｇ−−０．０１４５８４＝０である。この分割では、両方の領域が混合領域であり、ノードに対応することになる。
【００３８】
式１９においてＮ＋＝２３、Ｎ−＝７５、ａ＝０．０５２５０５、ｂ＝０．０３１６４２、ｃ＝−０．０１４５８４と、図５の従属度のデータを代入すると、
【数２０】
2004126831.tif 000043
となる。これは式１７の変換Ｔ後の３次元空間に分布するデータ点を分割する平面式であり、Ｇ＋−Ｇ−平面でのデータ点の分割と同値である。
【００３９】
次に、図６の直線の上側のデータに対して同じことを繰り返した結果を図７、図８に示す。図８でもフィッシャーの方法で分割を行っているが、これもノードに対応することになる。
【００４０】
一方のクラスに属するデータのみの領域が得られたら、それ以上の分割は不要であり、どちらかのクラスを表すリーフに対応することになる。
【００４１】
図６の直線の下側にも同じ操作が行える。これらを再帰的に行うと、図９のように展開する。最終的には、全てのデータ点をいずれかのクラスに分類することになる。
【００４２】
決定木は、図９との対応でリーフとノードを生成して構成される。図１０はこの対応の模式図である。データの特性、あるいは、Ｇ＋−Ｇ−平面での分割直線の取り方により適時リーフが生成されるので、階層の深さは一律ではない。
【００４３】
図１０の各分岐に対して、式２０のような判別式Ｆ（ｘ、ｙ、ｚ）がそれぞれ与えられる。したがって、未分類のデータが与えられたときは、変換Ｔを施して後、Ｆ（ｘ、ｙ、ｚ）＞０かＦ（ｘ、ｙ、ｚ）≦０の判別によって分岐を辿り、いずれかのリーフに落とし込まれ、クラスの予測が可能になる。
【００４４】
【発明の効果】
本発明では、データ間の類似度指数を計算するために多次元データの参照を１回行えばよい。したがって、多次元データを再帰的に計算に用いる判別分析の方法と比べて計算量を大幅に低減できる。また、クラスに対する従属度を座標とする２次元平面の点を分割するという方法の導入により、クラス分類可能な決定木を作成することができる。
【図面の簡単な説明】
【図１】実施例に用いたデータ
【図２】図１のデータをプロット
【図３】属性に重みを掛けて変換Ｔを施した結果
【図４】図３のプロット
【図５】クラスに対する従属度の計算結果
【図６】図５のプロットと分割直線
【図７】図６上部に対する計算結果
【図８】図７のプロットと分割直線
【図９】クラス分類の展開図
【図１０】クラス分類に対応する決定木の模式図
【図１】
2004126831.tif 000044
【図２】
2004126831.tif 000045
【図３】
2004126831.tif 000046
【図４】
2004126831.tif 000047
【図５】
2004126831.tif 000048
【図６】
2004126831.tif 000049
【図７】
2004126831.tif 000050
【図８】
2004126831.tif 000051
【図９】
2004126831.tif 000052
【図１０】
2004126831.tif 000053