(57)【要約】【課題】訓練データの分布が均一でない場合にも精度よくデータを分類すること。【解決手段】従来技術のＳＶＭによる分類では、正例・負例を分割する分離超平面を一律にマージンの中央とするために、訓練データの分布が均一でない場合は、当該密度が相対的に高い分類へデータが分類されやすいという問題があった。本発明では分類対象データの近傍における局所的な正例訓練データ密度・負例訓練データ密度を算出し、当該密度に応じて、具体的には訓練データ密度のより高い側へ分離超平面の位置を補正する。これにより、補正前は密度の高い分類へ分類されていたデータが、補正後は密度の低い分類へ分類される確率が高まり、訓練データ密度の相対的に低い場所で分類精度が悪化する問題を解決できる。なお、ＳＶＭ以外の分類手法（ｋＮＮ等）で、同様に訓練データ密度により分類の閾値を補正することも可能。【選択図】      図２
2004341959.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータの存在する空間を分離面により各分類ごとの空間に分割するデータ分類装置において、
分類対象データの位置における、第１の分類に分類される訓練データの密度を算出する第１の密度算出手段と、
前記分類対象データの位置における、第２の分類に分類される訓練データの密度を算出する第２の密度算出手段と、
前記第１の密度算出手段により算出された密度および前記第２の密度算出手段により算出された密度にもとづいて前記分離面の位置を補正する分離面位置補正手段と、
を備えたことを特徴とするデータ分類装置。
【請求項２】
前記分離面位置補正手段は、前記第１の分類または前記第２の分類のうち、前記第１の密度算出手段または前記第２の密度算出手段により算出された密度が相対的に高い側へ前記分離面の位置を補正することを特徴とする前記請求項１に記載のデータ分類装置。
【請求項３】
前記第１の密度算出手段は前記第１の分類に分類されていない訓練データも含めて前記密度を算出することを特徴とする前記請求項１または請求項２に記載のデータ分類装置。
【請求項４】
前記第１の密度算出手段は前記第１の分類に分類される訓練データのうち一部の訓練データを用いて前記密度を算出することを特徴とする前記請求項１〜請求項３のいずれか一つに記載のデータ分類装置。
【請求項５】
前記一部の訓練データは前記分離面からの距離が所定の条件を満たす訓練データであることを特徴とする前記請求項４に記載のデータ分類装置。
【請求項６】
前記第１の密度算出手段は前記第１の分類に分類される訓練データを含む第１の訓練データ集合および前記第１の訓練データ集合から一部の訓練データを除外した第２の訓練データ集合を用いて前記密度を算出することを特徴とする前記請求項１〜請求項５のいずれか一つに記載のデータ分類装置。
【請求項７】
前記第１の密度算出手段は前記訓練データ間の距離にもとづいて前記密度を算出することを特徴とする前記請求項１〜請求項６のいずれか一つに記載のデータ分類装置。
【請求項８】
複数のデータの存在する空間を分離面により各分類ごとの空間に分割するデータ分類方法において、
分類対象データの位置における、第１の分類に分類される訓練データの密度を算出する第１の密度算出工程と、
前記分類対象データの位置における、第２の分類に分類される訓練データの密度を算出する第２の密度算出工程と、
前記第１の密度算出工程で算出された密度および前記第２の密度算出工程で算出された密度にもとづいて前記分離面の位置を補正する分離面位置補正工程と、
を含んだことを特徴とするデータ分類方法。
【請求項９】
前記分離面位置補正工程では、前記第１の分類または前記第２の分類のうち、前記第１の密度算出工程または前記第２の密度算出工程で算出された密度が相対的に高い側へ前記分離面の位置を補正することを特徴とする前記請求項８に記載のデータ分類方法。
【請求項１０】
前記第１の密度算出工程では前記第１の分類に分類されていない訓練データも含めて前記密度を算出することを特徴とする前記請求項８または請求項９に記載のデータ分類方法。
【請求項１１】
前記第１の密度算出工程では前記第１の分類に分類される訓練データのうち一部の訓練データを用いて前記密度を算出することを特徴とする前記請求項８〜請求項１０のいずれか一つに記載のデータ分類方法。
【請求項１２】
前記一部の訓練データは前記分離面からの距離が所定の条件を満たす訓練データであることを特徴とする前記請求項１１に記載のデータ分類方法。
【請求項１３】
前記第１の密度算出工程では前記第１の分類に分類される訓練データを含む第１の訓練データ集合および前記第１の訓練データ集合から一部の訓練データを除外した第２の訓練データ集合を用いて前記密度を算出することを特徴とする前記請求項８〜請求項１２のいずれか一つに記載のデータ分類方法。
【請求項１４】
前記第１の密度算出工程では前記訓練データ間の距離にもとづいて前記密度を算出することを特徴とする前記請求項８〜請求項１３のいずれか一つに記載のデータ分類方法。
【請求項１５】
前記請求項８〜請求項１４のいずれか一つに記載された方法をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、複数のデータの存在する空間を分離面（平面や曲面など）により各分類ごとの空間に分割するデータ分類装置、データ分類方法およびその方法をコンピュータに実行させるプログラムに関する。
【０００２】
【従来の技術】
ＳＶＭ（Ｓｕｐｐｏｒｔ  Ｖｅｃｔｏｒ  Ｍａｃｈｉｎｅ）は、２種類以上の分類のいずれかが付与されたデータの存在する空間を、各分類ごとの空間に分割する手法である。このＳＶＭでは、個々の訓練データを表すベクトルを素性空間（一般に入力空間より高次元）上に写像し、正例と負例を最も幅広く分割できるマージンを見つけ出す。そして、そのマージンの中央に、正例と負例とを切り分ける分離超平面を構築する（図１）。
【０００３】
一般に高次元空間上でデータを分類した場合、分類は容易になる一方、データに特化した過学習を起こしやすくなることが知られているが、ＳＶＭではマージン最大化という戦略により、実際にはマージンに接しているデータ（ＳＶ：Ｓｕｐｐｏｒｔ  Ｖｅｃｔｏｒ）の数に依存する次元しか、判別に利用しない。つまり、高次元上の分類に有効な軸のみ利用することで、高次元空間におけるデータの分類しやすさを維持しつつ、過学習を防止していることになる。
【０００４】
【発明が解決しようとする課題】
しかしながら、マージンの中央を分離超平面とすることの根拠については、従来ほとんど検討されてこなかった。従来技術においては、素性空間上における正例・負例の訓練データの分布は均一であることが暗黙の前提となっている。一方、実際の訓練データの分布は不均一であるため、後述のように、訓練データの密度が相対的に低い場所で分類精度が悪化してしまうという問題があった。
【０００５】
この発明は上記従来技術による問題を解決するため、計算量を抑制しつつ、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類装置、データ分類方法およびその方法をコンピュータに実行させるプログラムを提供することを目的とする。
【０００６】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、請求項１に記載の発明にかかるデータ分類装置は、複数のデータの存在する空間を分離面により各分類ごとの空間に分割するデータ分類装置において、分類対象データの位置における、第１の分類に分類される訓練データの密度を算出する第１の密度算出手段と、前記分類対象データの位置における、第２の分類に分類される訓練データの密度を算出する第２の密度算出手段と、前記第１の密度算出手段により算出された密度および前記第２の密度算出手段により算出された密度にもとづいて前記分離面の位置を補正する分離面位置補正手段と、を備えたことを特徴とする。
【０００７】
この請求項１に記載の発明によれば、第１の分類と第２の分類との境界となる分離面の位置が、上記各分類に属する訓練データの密度に応じて補正される。
【０００８】
また、請求項２に記載の発明にかかるデータ分類装置は、前記請求項１に記載の発明において、前記分離面位置補正手段が、前記第１の分類または前記第２の分類のうち、前記第１の密度算出手段または前記第２の密度算出手段により算出された密度が相対的に高い側へ前記分離面の位置を補正することを特徴とする。
【０００９】
この請求項２に記載の発明によれば、訓練データの分布が均一でない場合に、訓練データ密度の相対的に高い分類へデータが分類されやすいという特性（この特性が分類精度の悪化の原因となっている）が修正される。
【００１０】
また、請求項３に記載の発明にかかるデータ分類装置は、前記請求項１または請求項２に記載の発明において、前記第１の密度算出手段が前記第１の分類に分類されていない訓練データも含めて前記密度を算出することを特徴とする。
【００１１】
この請求項３に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度は、第１の分類が付与された訓練データのほか、正確な分類は不明であるものの、第１の分類が付与される確率の高い訓練データを含めて計算される。
【００１２】
また、請求項４に記載の発明にかかるデータ分類装置は、前記請求項１〜請求項３のいずれか一つに記載の発明において、前記第１の密度算出手段が前記第１の分類に分類される訓練データのうち一部の訓練データを用いて前記密度を算出することを特徴とする。
【００１３】
この請求項４に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度は、前記空間内に存在する一部の訓練データの密度によって近似される。
【００１４】
また、請求項５に記載の発明にかかるデータ分類装置は、前記請求項４に記載の発明において、前記一部の訓練データは前記分離面からの距離が所定の条件を満たす訓練データであることを特徴とする。
【００１５】
この請求項５に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度は、たとえば補正前の分離面からの距離が一定の訓練データの密度（補正前の分離面に対して平行な面上での訓練データ密度）によって近似される。
【００１６】
また、請求項６に記載の発明にかかるデータ分類装置は、前記請求項１〜請求項５のいずれか一つに記載の発明において、前記第１の密度算出手段が前記第１の分類に分類される訓練データを含む第１の訓練データ集合および前記第１の訓練データ集合から一部の訓練データを除外した第２の訓練データ集合を用いて前記密度を算出することを特徴とする。
【００１７】
この請求項６に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度は、補正前の分離面に対して垂直な方向での訓練データ密度によって近似される。
【００１８】
また、請求項７に記載の発明にかかるデータ分類装置は、前記請求項１〜請求項６のいずれか一つに記載の発明において、前記第１の密度算出手段が前記訓練データ間の距離にもとづいて前記密度を算出することを特徴とする。
【００１９】
この請求項７に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度の算出に複雑な計算を必要としない。
【００２０】
また、請求項８に記載の発明にかかるデータ分類方法は、複数のデータの存在する空間を分離面により各分類ごとの空間に分割するデータ分類方法において、分類対象データの位置における、第１の分類に分類される訓練データの密度を算出する第１の密度算出工程と、前記分類対象データの位置における、第２の分類に分類される訓練データの密度を算出する第２の密度算出工程と、前記第１の密度算出工程で算出された密度および前記第２の密度算出工程で算出された密度にもとづいて前記分離面の位置を補正する分離面位置補正工程と、を含んだことを特徴とする。
【００２１】
この請求項８に記載の発明によれば、第１の分類と第２の分類との境界となる分離面の位置が、上記各分類に属する訓練データの密度に応じて補正される。
【００２２】
また、請求項９に記載の発明にかかるデータ分類方法は、前記請求項８に記載の発明において、前記分離面位置補正工程では、前記第１の分類または前記第２の分類のうち、前記第１の密度算出工程または前記第２の密度算出工程で算出された密度が相対的に高い側へ前記分離面の位置を補正することを特徴とする。
【００２３】
この請求項９に記載の発明によれば、訓練データの分布が均一でない場合に、訓練データ密度の相対的に高い分類へデータが分類されやすいという特性が修正される。
【００２４】
また、請求項１０に記載の発明にかかるデータ分類方法は、前記請求項８または請求項９に記載の発明において、前記第１の密度算出工程では前記第１の分類に分類されていない訓練データも含めて前記密度を算出することを特徴とする。
【００２５】
この請求項１０に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度は、第１の分類が付与された訓練データのほか、正確な分類は不明であるものの、第１の分類が付与される確率の高い訓練データを含めて計算される。
【００２６】
また、請求項１１に記載の発明にかかるデータ分類方法は、前記請求項８〜請求項１０のいずれか一つに記載の発明において、前記第１の密度算出工程では前記第１の分類に分類される訓練データのうち一部の訓練データを用いて前記密度を算出することを特徴とする。
【００２７】
この請求項１１に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度は、前記空間内に存在する一部の訓練データの密度によって近似される。
【００２８】
また、請求項１２に記載の発明にかかるデータ分類方法は、前記請求項１１に記載の発明において、前記一部の訓練データは前記分離面からの距離が所定の条件を満たす訓練データであることを特徴とする。
【００２９】
この請求項１２に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度は、たとえば補正前の分離面からの距離が一定の訓練データの密度（補正前の分離面に対して平行な面上での訓練データ密度）によって近似される。
【００３０】
また、請求項１３に記載の発明にかかるデータ分類方法は、前記請求項８〜請求項１２のいずれか一つに記載の発明において、前記第１の密度算出工程では前記第１の分類に分類される訓練データを含む第１の訓練データ集合および前記第１の訓練データ集合から一部の訓練データを除外した第２の訓練データ集合を用いて前記密度を算出することを特徴とする。
【００３１】
この請求項１３に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度は、補正前の分離面に対して垂直な方向での訓練データ密度によって近似される。
【００３２】
また、請求項１４に記載の発明にかかるデータ分類方法は、前記請求項８〜請求項１３のいずれか一つに記載の発明において、前記第１の密度算出工程では前記訓練データ間の距離にもとづいて前記密度を算出することを特徴とする。
【００３３】
この請求項１４に記載の発明によれば、補正後の分離面の位置を決定する訓練データ密度の算出に複雑な計算を必要としない。
【００３４】
また、請求項１５に記載の発明にかかるプログラムによれば、前記請求項８〜請求項１４のいずれか一つに記載された方法がコンピュータによって実行される。
【００３５】
【発明の実施の形態】
以下に添付図面を参照して、この発明によるデータ分類装置、データ分類方法およびその方法をコンピュータに実行させるプログラムの好適な実施の形態を詳細に説明するが、その前に、本発明の骨子について簡単に説明する。
【００３６】
（発明の骨子）
上述のように、素性空間上における訓練データの分布が均一である場合には、マージンの中央を分離超平面とすることが合理的と考えられる。しかしながら、実際の訓練データの分布はしばしば不均一であり、その場合にも上記が合理的であるとは必ずしも言えない。
【００３７】
たとえば図２に示すように、同じ大きさの空間に正例訓練データ（図中「○」）は３個、負例訓練データ（同「×」）は２４個分布していたとする。このとき以下が成り立つと仮定する。
【００３８】
（ａ）正例と負例を完全に判別できる素性空間上の超平面がただ一つ存在する。
（ｂ）正例データの分布は、素性空間上の正例である場所に対して均一である。
（ｃ）正例訓練データは、正例データの中からランダムに選択される。
（ｄ）負例データの分布は、素性空間上の負例である場所に対して均一である。
（ｅ）負例訓練データは、負例データの中からランダムに選択される。
【００３９】
上記条件のもとで、素性空間上の理想的な分離超平面に垂直な軸上の分布を考えると、統計学上、最も分離超平面に近い正例訓練データ・負例訓練データの距離比も、訓練データ密度比と同じ８：１となる確率が最も高い。つまり分離超平面は、マージンを１：１に内分する位置（すなわちマージンの中央）ではなく、マージンを８：１に内分する位置にあるほうが合理的である。
【００４０】
そこで本発明では、分離超平面の位置を訓練データ密度の相対的に高い側へと補正する。そしてこの移動は、ＳＶＭの判別式を以下のように修正することで実現できる（なお、ｓｉｇｎ（ｐ）はｐの正負を返す関数である）。
（修正前）
【数式１】
2004341959.tif 000003
（修正後）
【数式２】
2004341959.tif 000004
【００４１】
問題はこのｃの値をどうやって算出するか、言い換えれば、分離超平面の移動量と方向とをどうやって決定するかであり、後述する実施の形態１および２は、いずれもこのｃ値の算出の詳細にかかるものである。
【００４２】
最も単純には、同じ大きさの空間あたりの正例訓練データの個数と負例訓練データの個数を、それぞれ正例訓練データ密度ｄｐ、負例訓練データ密度ｄｎとすればよい。たとえば図２の例では、同じ大きさの空間に正例訓練データは３個、負例訓練データは２４個分布していることから、ｋ＝１とするとｃ＝（３−２４）／（３＋２４）＝−７／９となる。
【００４３】
あるいは、正例訓練データ・負例訓練データの中でも特にマージンに接しているもの（マージンの境界面であるサポーティング・ハイパープレーン上に存在するもの）の個数、すなわち正例ＳＶの総数ＳＶｐおよび負例ＳＶの総数ＳＶｎは、それぞれ正例訓練データ密度ｄｐ・負例訓練データ密度ｄｎに比例すると仮定して、
【数式３】
2004341959.tif 000005
あるいは
【数式４】
2004341959.tif 000006
などとしてもよい。
【００４４】
なお、ソフトマージンＳＶＭを用いた場合は、ＳＶはマージン境界面上にあるとは限らないが（境界面上にあればＳＶであるが、ＳＶであれば境界面上にあるとは必ずしも言えない）、この場合はＳＶの中でも、特にマージン境界面上にあるＳＶの個数だけをＳＶｐ・ＳＶｎとしてもよい。マージン境界面に存在するＳＶとは、具体的にはその重みがＳＶＭのコスト値（訓練データの分類誤りに対するペナルティー）未満であるようなＳＶである。
【００４５】
ここまで説明してきたように、訓練データの空間あたりの個数、訓練データのうち特にＳＶであるものの個数、あるいはＳＶの中でも特にマージン境界面上のものの個数などから、正例訓練データ密度および負例訓練データ密度を推測し、この密度の相対的に高い側へ分離超平面をずらすことで、当該密度が相対的に低い側での分類精度を向上させることができる。
【００４６】
ただ、上記の計算式はいずれも、正例データ（および正例データの中からランダムに選択される正例訓練データ）は素性空間上の正例である場所に対して均一に、負例データ（および負例データの中からランダムに選択される負例訓練データ）も負例である場所に対して均一に、それぞれ分布していることを前提としている。
【００４７】
しかし実際の訓練データでは、たとえば図３に示すように、同じ負例側でもこの部分ではデータが密であり、この部分では疎であるといった分布の偏りがある。すなわち、上記で仮定した（ｂ）〜（ｅ）の条件は、実際には成立しないことが多い。
【００４８】
そこで本発明では、個々の分類対象データの近傍における訓練データの局所的密度から、分離超平面の位置を補正するようにモデルを拡張する。すなわち図３に示すように、分類対象データｘ（図中「？」）の位置における正例訓練データ・負例訓練データの密度比を算出し、この密度比に応じて分離超平面の位置を補正する。
【００４９】
そしてこの局所的密度の尺度として、本発明では
（１）分類対象データの近傍における、分離超平面に平行な方向での相対データ密度（後述する実施の形態１）
（２）分類対象データの近傍における、分離超平面に垂直な方向での相対データ密度（後述する実施の形態２）
のいずれかを利用する。
【００５０】
すなわち実施の形態１では、分類対象データｘの位置での訓練データ密度を、正例側・負例側のそれぞれのマージン境界面上で分類対象データｘに最も近い点における正例ＳＶ・負例ＳＶの密度から推定する。マージン境界面より内側の訓練データ密度を、マージン境界面上の訓練データであるＳＶの密度から推定すると言ってもよい。
【００５１】
まず、個々のＳＶの位置における相対データ密度を求める。素性空間上のベクトル間の距離は、式（１）（２）にもあるカーネル関数Ｋを用いて下記式により求められる。
【数式５】
2004341959.tif 000007
【００５２】
ここで、ｉ番目の正例ＳＶであるＳＶｐｉの位置での相対正例データ密度（ＳＶｐｉ）、およびｉ番目の負例ＳＶであるＳＶｎｉの位置での相対負例データ密度（ＳＶｎｉ）を、
【数式６】
2004341959.tif 000008
と定義する。
【００５３】
上記各式により算出される各ＳＶの相対データ密度は、当該ＳＶに近い（当該ＳＶとの距離の小さい）ＳＶが多くあるほど、すなわちＳＶがより密に分布している場所ほど高くなる。逆に言えば、ＳＶの寄り集まっている場所ほど高く、ＳＶのまばらな場所ほど低くなるように相対データ密度を算出できるのであれば、計算式は上記に限らず、どのようなものであってもよい。他の計算式の例としては、たとえば下記のようなものがある。
【数式７】
2004341959.tif 000009
【００５４】
次に、上記で算出した各ＳＶの位置における相対データ密度から、正例側マージン境界面上で分類対象データｘに最も近い点における相対正例データ密度、および負例側マージン境界面上で分類対象データｘに最も近い点における相対負例データ密度を算出する。そしてこれらを、分類対象データｘの位置における相対正例データ密度（ｘ）および相対負例データ密度（ｘ）であるとみなす。
【数式８】
2004341959.tif 000010
【００５５】
上記式から分かるように、相対正例データ密度（ｘ）はすべての正例ＳＶの位置における相対正例データ密度（ＳＶｐｉ）を、当該ＳＶから分類対象データｘまでの距離に反比例する重み（ｗｐｉ）で足し合わせたものとなっている。すなわち、分類対象データｘに近いＳＶほど大きな重み、遠いＳＶほど小さな重みで計算した、相対正例データ密度（ＳＶｐｉ）の加重平均となっている。相対負例データ密度（ｘ）も同様に、すべての負例ＳＶの位置における相対負例データ密度（ＳＶｎｉ）の加重平均である。
【００５６】
逆に言えば、近いＳＶの重みほど大きく、遠いＳＶの重みほど小さくなるのであれば、ｗｐｉやｗｎｉの計算式は上記に限らず、どのようなものであってもよい。他の計算式の例としては、たとえば下記のようなものがある。
【数式９】
2004341959.tif 000011
【００５７】
そして上記で算出した、分類対象データｘの位置での相対正例データ密度（ｘ）を式（２）のｄｐ、相対負例データ密度（ｘ）をｄｎに代入してｃ値を算出する。
【００５８】
一方、実施の形態２では分離超平面に沿う方向（平行方向）ではなく、分離超平面から離れる方向（垂直方向）での正例訓練データ・負例訓練データの密度比を求め、この密度比に応じてｃ値すなわち分離超平面の移動量と方向とを算出する。
【００５９】
すなわち、まず訓練データの全体を用いてＳＶＭを学習させ、学習後のＳＶＭを甲とする。次に訓練データの中から、ＳＶＭ甲でＳＶとなったものと同一の訓練データを取り除く（なお、ＳＶとまったく同じ訓練データが複数あった場合は、それらをすべて除いてもよいし、一つだけ除いてもよい）。そして、ＳＶと同じものを除いた残りの訓練データを用いて再度ＳＶＭを学習させ、学習後のＳＶＭを乙とする。
【００６０】
図４に示すように、ＳＶＭ乙ではＳＶＭ甲のＳＶを除いた残りの訓練データの中で最大となるマージンを採用するので、正例側・負例側のマージン境界面は、多かれ少なかれＳＶＭ甲の分離超平面から離れる方向へと後退する。
【００６１】
ただし、その後退量は正例側・負例側で同一ではない。ＳＶＭ甲の分離超平面に対して垂直な直線を考えると、この直線上における境界面の後退量は、訓練データ密度が相対的に高い側（図示する例では負例側）のほうが、当該密度の相対的に低い側（同正例側）よりも小さくなっている。すなわち、訓練データ密度が高いほど、ＳＶの除去によってもマージン境界面が後退しづらい。
【００６２】
本発明ではこの点に注目し、マージン境界面の後退量は訓練データ密度に反比例するとの前提のもとに、ＳＶを除去する前のＳＶＭ甲とＳＶを除去した後のＳＶＭ乙とを用いて、正例側・負例側でのマージン境界面の後退量の比を求め、この比から逆に正例訓練データ・負例訓練データの密度比を推定する。
【００６３】
入力空間から素性空間への写像関数をφとおく。図４に示すように、分類対象データｘに対応する素性空間上の点φ（ｘ）（図中「？」）を通り、ＳＶＭ甲の分離超平面に垂直な直線（図中「垂線Ｖ」）を考える。垂線Ｖ上のφ（ｘ）以外の点ｘ’を考えると、ｘ’は下記式により表現できる。
【数式１０】
2004341959.tif 000012
【００６４】
そして、式（２）に示したｆ（ｘ）の値をスコアと呼ぶことにすると、ＳＶＭ甲におけるｘ’のスコア甲（ｘ’）は下記のようになる。
【数式１１】
2004341959.tif 000013
なお、ＳＶＭ乙におけるｘ’のスコア乙（ｘ’）も同様に計算できる。
【００６５】
ここで、垂線Ｖと、ＳＶＭ甲の正例側マージン境界面との交点をｐ、ＳＶＭ乙の正例側マージン境界面との交点をＰとする。ＳＶＭの学習による正例側マージン境界面の後退量は、ｐからＰまでのスコアの増加分、すなわち甲（Ｐ）−甲（ｐ）により定義できる。
【００６６】
甲（ｐ）＝１であるから、後退量を求めるには甲（Ｐ）、すなわちＳＶＭ乙の正例側マージン境界面にある点Ｐのスコアが、ＳＶＭ甲で計算するといくらになるかが分かればよい。そして、求めるスコア甲（Ｐ）は下記式により算出できる。
【数式１２】
2004341959.tif 000014
【００６７】
一方、負例側マージン境界面の後退量も、垂線ＶとＳＶＭ甲の負例側マージン境界面との交点をｎ、ＳＶＭ乙の負例側マージン境界面との交点をＮとすると、甲（ｎ）−甲（Ｎ）により定義できる。そして甲（ｎ）は−１であり、甲（Ｎ）は下記式により算出できる。
【数式１３】
2004341959.tif 000015
【００６８】
これにより、正例側マージン境界面の後退量（甲（Ｐ）−甲（ｐ））と負例側マージン境界面の後退量（甲（ｎ）−甲（Ｎ））とが求められるので、それぞれの逆数をｄｐおよびｄｎとする。そして、上述の式（２）によりｃ値を算出する。
【００６９】
（実施の形態１）
図５は、本発明の実施の形態１によるデータ分類装置のハードウエア構成の一例を示す説明図である。図中、５０１は装置全体を制御するＣＰＵを、５０２は基本入出力プログラムを記憶したＲＯＭを、５０３はＣＰＵ５０１のワークエリアとして使用されるＲＡＭを、それぞれ示している。
【００７０】
また、５０４はＣＰＵ５０１の制御にしたがってＨＤ（ハードディスク）５０５に対するデータのリード／ライトを制御するＨＤＤ（ハードディスクドライブ）を、５０５はＨＤＤ５０４の制御にしたがって書き込まれたデータを記憶するＨＤを、それぞれ示している。
【００７１】
また、５０６はＣＰＵ５０１の制御にしたがってＦＤ（フレキシブルディスク）５０７に対するデータのリード／ライトを制御するＦＤＤ（フレキシブルディスクドライブ）を、５０７はＦＤＤ５０６の制御にしたがって書き込まれたデータを記憶する着脱自在のＦＤを、それぞれ示している。
【００７２】
また、５０８はＣＰＵ５０１の制御にしたがってＣＤ−ＲＷ５０９に対するデータのリード／ライトを制御するＣＤ−ＲＷドライブを、５０９はＣＤ−ＲＷドライブ５０８の制御にしたがって書き込まれたデータを記憶する着脱自在のＣＤ−ＲＷを、それぞれ示している。
【００７３】
また、５１０はカーソル、メニュー、ウィンドウ、あるいは文字や画像などの各種データを表示するディスプレイを、５１１は文字、数値、各種指示などの入力のための複数のキーを備えたキーボードを、５１２は各種指示の選択や実行、処理対象の選択、マウスポインタの移動などをおこなうマウスを、それぞれ示している。
【００７４】
また、５１３は通信ケーブル５１４を介してＬＡＮやＷＡＮなどのネットワークに接続され、当該ネットワークとＣＰＵ５０１とのインターフェースとして機能するネットワークＩ／Ｆを、５００は上記各部を接続するためのバスを、それぞれ示している。
【００７５】
次に、図６は本発明の実施の形態１によるデータ分類装置の構成を機能的に示す説明図である。また、図７は本発明の実施の形態１によるデータ分類装置における、データ分類処理の手順を示すフローチャートである。以下、図７に示す手順に沿って、図６に示す各部の機能を順次説明する。
【００７６】
なお、本フローチャートによる処理に先立って、訓練データあるいは分類対象データとして使用する入力情報および出力（分類）情報の形式を決定しておく。これらの情報の形式には本発明は関知しないので、一般的な教師あり学習方法に準じた形式を採用すればよい。また、ＳＶＭを学習させるには入力情報をベクトル化する必要があるので、その形式も決定しておく。このベクトルの形式にも本発明は関知しないので、一般的なＳＶＭの学習方法に準じた形式とすればよい。
【００７７】
まず、訓練データあるいは分類対象データとして使用される入力情報および出力情報を、データ入力部６００により装置内部に取り込み（ステップＳ７０１）、取り込んだ入力情報を、データ変換部６０１により所定の形式に変換（具体的にはベクトル化）する（ステップＳ７０２）。
【００７８】
そしてＳＶＭ学習部６０２により、あらかじめ分類が付与された訓練データを用いてＳＶＭを学習させる（ステップＳ７０３）。その学習方法は任意であり、たとえばＳＭＯ（Ｓｅｑｕｅｎｔｉａｌ  Ｍｉｎｉｍａｌ  Ｏｐｔｉｍｉｚａｔｉｏｎ：  Ａ  Ｆａｓｔ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｔｒａｉｎｉｎｇ  Ｓｕｐｐｏｒｔ  Ｖｅｃｔｏｒ  Ｍａｃｈｉｎｅｓ  （１９９８）  Ｊｏｈｎ  Ｃ．Ｐｌａｔｔ）法や、Ｋｅｒｎｅｌ−Ａｄａｔｒｏｎ（Ｔｈｅ  Ｋｅｒｎｅｌ−Ａｄａｔｒｏｎ：  ａ  ｆａｓｔ  ａｎｄ  ｓｉｍｐｌｅ  ｔｒａｉｎｉｎｇ  ｐｒｏｃｅｄｕｒｅ  ｆｏｒ  ｓｕｐｐｏｒｔ  ｖｅｃｔｏｒ  ｍａｃｈｉｎｅｓ．  （１９９８）  Ｔ．Ｆｒｉｅｓｓ，  Ｎ．Ｃｒｉｓｔｉａｎｉｎｉ  ａｎｄ  Ｃ．Ｃａｍｐｂｅｌｌ）法などを利用できる。なお、ＳＶＭのパラメータも一般的な手法（交差検定など）により最適化することで、分類精度を向上できる。ここでは、コスト値が１のソフトマージンＳＶＭで学習を行うものとする。
【００７９】
その後データを指定して、当該データの分類先を判定するようユーザから指示があると（ステップＳ７０４：Ｙｅｓ）、まずｃ値算出部６０３により、上述のｃ値すなわち分離超平面の移動量と方向とを算出する（ステップＳ７０５）。
【００８０】
図８は、本発明の実施の形態１によるデータ分類装置における、ｃ値算出処理（図７のステップＳ７０５）の手順を詳細に示すフローチャートである。ｃ値算出部６０３は、まずＳＶＭ学習部６０２による学習後のＳＶＭから、マージン境界面上に存在するＳＶを抽出する（ステップＳ８０１）。ここでは、上記ＳＶＭのＳＶが以下のようであったとする。
【００８１】
2004341959.tif 000016
【００８２】
ここで、コスト値（ここでは１）以上の重みを持つＳＶｐ４は、マージン境界面には存在しないＳＶなので、ステップＳ８０１で抽出されるのはＳＶｐ１〜ＳＶｐ３とＳＶｎ１〜ＳＶｎ４の計７つである。
【００８３】
次に、ｃ値算出部６０３は上述の式（５）により、ステップＳ８０１で抽出した各ＳＶ間の距離を算出する（ステップＳ８０２）。ここでは計算の結果、各ＳＶ間の距離が以下のようになったとする。
【００８４】
2004341959.tif 000017
【００８５】
次に、ｃ値算出部６０３は上述の式（６）により、ステップＳ８０２で算出した距離を用いて、各ＳＶの位置における相対正例データ密度（ＳＶｐｉ）および相対負例データ密度（ＳＶｎｉ）を算出する（ステップＳ８０３）。
【００８６】
ここで、式（６）のｔ＝１とすると、
相対正例データ密度（ＳＶｐ１）
＝１／距離（ＳＶｐ１〜ＳＶｐ２）＋１／距離（ＳＶｐ１〜ＳＶｐ３）
＝１／０．５＋１／０．５
＝４
である。
【００８７】
同様に、
相対正例データ密度（ＳＶｐ２）＝１／０．５＋１／０．２＝７
相対正例データ密度（ＳＶｐ３）＝１／０．５＋１／０．２＝７
相対負例データ密度（ＳＶｎ１）＝１／０．５＋１／０．５＋１／０．５＝６
相対負例データ密度（ＳＶｎ２）＝１／０．５＋１／０．２５＋１／０．２＝１１
相対負例データ密度（ＳＶｎ３）＝１／０．５＋１／０．２５＋１／０．１＝１６
相対負例データ密度（ＳＶｎ４）＝１／０．５＋１／０．２＋１／０．１＝１７である。
【００８８】
次に、ｃ値算出部６０３は上述の式（５）により、分類対象データｘからステップＳ８０１で抽出した各ＳＶまでの距離を算出する（ステップＳ８０４）。ここでは計算の結果、各ＳＶまでの距離が以下のようになったとする。
【００８９】
距離（ｘ〜ＳＶｐ１）＝０．２
距離（ｘ〜ＳＶｐ２）＝０．５
距離（ｘ〜ＳＶｐ３）＝０．５
距離（ｘ〜ＳＶｎ１）＝０．５
距離（ｘ〜ＳＶｎ２）＝０．２
距離（ｘ〜ＳＶｎ３）＝０．１
距離（ｘ〜ＳＶｎ４）＝０．１
【００９０】
次に、ｃ値算出部６０３は上述の式（８）により、ステップＳ８０３で算出した各ＳＶの位置での相対データ密度、およびステップＳ８０４で算出した各ＳＶまでの距離を用いて、分類対象データｘの位置（厳密にはその近傍のマージン境界面）における相対正例データ密度（ｘ）および相対負例データ密度（ｘ）を算出する（ステップＳ８０５）。
【００９１】
ここで、式（８）のｔ＝１とすると、ｗｐｉの分母Σ（１／距離（ｘ〜ＳＶｐｊ））＝１／０．２＋１／０．５＋１／０．５＝９であることから、
ｗｐ１＝１／０．２×１／９＝５／９
ｗｐ２＝１／０．５×１／９＝２／９
ｗｐ３＝１／０．５×１／９＝２／９
【００９２】
よって、相対正例データ密度（ｘ）
＝（５／９×４）＋（２／９×７）＋（２／９×７）
＝１６／３
＝５．３３３・・・
【００９３】
また、ｗｎｉの分母Σ（１／距離（ｘ〜ＳＶｎｊ））＝１／０．５＋１／０．２＋１／０．１＋１／０．１＝２７であることから、
ｗｎ１＝１／０．５×１／２７＝２／２７
ｗｎ２＝１／０．２×１／２７＝５／２７
ｗｎ３＝１／０．１×１／２７＝１０／２７
ｗｎ４＝１／０．１×１／２７＝１０／２７
【００９４】
よって、相対負例データ密度（ｘ）
＝（２／２７×６）＋（５／２７×１１）＋（１０／２７×１６）＋（１０／２７×１７）
＝３９７／２７
＝１４．７０３７０３・・・
【００９５】
最後に、ｃ値算出部６０３はステップＳ８０５で算出した相対正例データ密度（ｘ）をｄｐ、相対負例データ密度（ｘ）をｄｎとして、式（２）によりｃ値を算出する（ステップＳ８０６）。たとえば式（２）のｋ＝１とすると、
2004341959.tif 000018
となる。この時点で図８のフローチャートによる処理は終了し、図７のステップＳ７０６へと復帰する。
【００９６】
上記のようにしてｃ値を求めた後、実施の形態１によるデータ分類装置は、次にそのデータ分類部６０４により式（２）の結果が正負のいずれとなるか、すなわち分類対象データｘが正例・負例のいずれに該当するかを判定する（ステップＳ７０６）。
【００９７】
ここでの判定結果は、分類対象データｘのスコアｆ（ｘ）に応じて図９のようになる。正例と負例との境目となる閾値が、従来技術では０であるのに対して、本発明では−２５３／５４１に減少している（図形的には分離超平面の位置が、負例側に補正されたことを意味する）。その結果スコアが−２５３／５４１から０までの範囲で、従来技術では負例と判定されていたデータが、本発明では正例と判定されることになる。
【００９８】
図７に戻り、最後に実施の形態１によるデータ分類装置は、データ出力部６０５によりデータ分類部６０４の処理結果をファイルあるいはディスプレイなどに出力して（ステップＳ７０７）、本フローチャートによる処理を終了する。
【００９９】
なお、ここでは説明の便宜上、個々のＳＶの位置での相対データ密度ＳＶｐｉ・ＳＶｎｉはｃ値の算出の都度算出するフローとしたが（図８ステップＳ８０１〜Ｓ８０３）、これらの値は分類対象データｘには依存しないので、実際上は毎回計算し直す必要はない。たとえば、上記で算出したＳＶｐｉやＳＶｎｉの値をテーブルに格納しておき、２回目以降の分類ではこのテーブルを参照することで、ステップＳ８０１〜Ｓ８０３の処理をスキップすることができる。
【０１００】
（実施の形態２）
一方、実施の形態２によるデータ分類装置も、そのハードウエア構成、機能的構成および当該装置におけるデータ分類処理の手順については、それぞれ図５、図６および図７に示した実施の形態１のそれと同様である。ただし、図７のステップＳ７０５におけるｃ値算出の手順のみは、図８に示した実施の形態１のそれとは異なっている。
【０１０１】
図１０は、本発明の実施の形態２によるデータ分類装置における、ｃ値算出処理（図７のステップＳ７０５）の手順を詳細に示すフローチャートである。実施の形態２によるｃ値算出部６０３は、まずステップＳ７０３による学習後のＳＶＭ（このＳＶＭを甲とする）から、マージン境界面に存在するＳＶを抽出する（ステップＳ１００１）。
【０１０２】
次に、ｃ値算出部６０３はステップＳ７０３でＳＶＭ甲の学習に用いた訓練データの中から、上記で抽出したＳＶと同一のものを除去する（ステップＳ１００２）。そして、データ除去後の訓練データをＳＶＭ学習部６０２に出力するとともに、当該訓練データによるＳＶＭ甲の学習を指示し、これを受けたＳＶＭ学習部６０２により、ＳＶＭ甲が再度学習される（ステップＳ１００３）。なお、ステップＳ１００３による学習後のＳＶＭを乙とする。
【０１０３】
次に、ｃ値算出部６０３は分類対象データφ（ｘ）と、φ（ｘ）を通る垂線Ｖ上の他の点ｘ’との、ＳＶＭ甲およびＳＶＭ乙におけるスコアを算出する（ステップＳ１００４）。ここでは計算の結果、上記スコアが以下のようになったとする。
【０１０４】
甲（φ（ｘ））＝０．２
甲（ｘ’）＝２．２
乙（φ（ｘ））＝０．３
乙（ｘ’）＝１．３
【０１０５】
次に、ｃ値算出部６０３は上記で算出した４点のスコアから、ＳＶＭ乙の正例側・負例側マージン境界面と垂線Ｖとの交点である点Ｐおよび点ＮのＳＶＭ甲におけるスコアを、上述の式（１２）および式（１３）により算出する（ステップＳ１００５）。
甲（Ｐ）＝（２．２−０．２）（１−０．３）／（１．３−０．３）＋０．２＝１．６
乙（Ｎ）＝（２．２−０．２）（−１−０．３）／（１．３−０．３）＋０．２＝−２．４
【０１０６】
次に、ｃ値算出部６０３は上記で算出したスコアから、正例側・負例側マージン境界面の後退量をそれぞれ算出する（ステップＳ１００６）。上記の例では、正例側のマージン境界面は、ＳＶＭ甲の１に対してＳＶＭ乙では１．６の位置まで、すなわち０．６だけ後退したことになる。また、負例側のマージン境界面は、ＳＶＭ甲の−１に対してＳＶＭ乙では−２．４の位置まで、すなわち１．４だけ後退したことになる。
【０１０７】
最後に、ｃ値算出部６０３はステップＳ１００６で算出した正例側マージン境界面の後退量の逆数をｄｐ、負例側マージン境界面の後退量の逆数をｄｎとして、式（２）によりｃ値を算出する（ステップＳ１００７）。たとえば式（２）のｋ＝１とすると、
2004341959.tif 000019
となる。この時点で図１０のフローチャートによる処理は終了し、図７のステップＳ７０６へと復帰する。
【０１０８】
この後、図７のステップＳ７０６における判定結果は、分類対象データｘのスコアｆ（ｘ）に応じて図１１のようになる。正例と負例との境目となる閾値が、従来技術では０であるのに対して、本発明では０．４に増加している（図形的には分離超平面の位置が、正例側に補正されたことを意味する）。その結果スコアが０から０．４までの範囲で、従来技術では正例と判定されていたデータが、本発明では負例と判定されることになる。
【０１０９】
なお、ここでは説明の便宜上、ＳＶＭの再学習はｃ値の算出の都度行うフローとしたが（図１０ステップＳ１００１〜Ｓ１００３）、学習後のＳＶＭ乙は分類対象データｘには依存しないので、実際上は毎回計算し直す必要はない。たとえば、２回目以降の分類では１回目の分類で求められたＳＶＭ乙を使い回すことで、ステップＳ１００１〜Ｓ１００３の処理をスキップすることができる。
【０１１０】
以上説明した実施の形態１および２によれば、個々の分類対象データの位置における局所的な訓練データの密度比に応じて、正例と負例とを切り分ける分離超平面の位置を補正するので、素性空間上のどの場所でも、同じ量だけ同じ方向に分離超平面を移動させるよりも、より精度よくデータを分類することができる。
【０１１１】
なお、上述した実施の形態１および２では、正例訓練データ密度ｄｐの算出時には素性空間上の複数のデータのうち正例訓練データのみ（かつその一部。具体的には、実施の形態１ではマージン境界面上のＳＶ、実施の形態２では垂線Ｖ上のＳＶ）に、負例訓練データ密度ｄｎの算出時には負例訓練データのみ（同上）に、それぞれ注目したが、逆に密度の計算に用いる訓練データは上記に限定されるものではない。
【０１１２】
たとえば正例訓練データだけでなく、負例訓練データも参照して正例訓練データ密度ｄｐを算出するようにしてもよいし、負例訓練データだけでなく、正例訓練データも参照して負例訓練データ密度ｄｎを算出するようにしてもよい。また、訓練データの中に正例でも負例でもない分類不明のデータを含ませておき、ｄｐやｄｎの算出にあたって、正例・負例のほか分類不明の訓練データの分布状況も考慮するようにしてもよい。
【０１１３】
（実施の形態３）
さて、上述した実施の形態１および２はもっぱらＳＶＭについて分類精度の向上をはかったものであるが、訓練データの分布状況に応じて分類の閾値を補正する工夫は、ＳＶＭに限らず他の分類手法にも広く応用可能である。実施の形態３ではその一例として、ｋＮＮ（ｋ−Ｎｅａｒｅｓｔ  Ｎｅｉｇｈｂｏｒ）法による分類において、訓練データの密度比に応じた閾値の補正を行う。なお、簡単のためｋ＝１とする。
【０１１４】
実施の形態３によるデータ分類装置のハードウエア構成は、図５に示した実施の形態１のそれと同様であるので説明を省略する。図１２は、本発明の実施の形態３によるデータ分類装置の構成を機能的に示す説明図である。また、図１３は本発明の実施の形態３によるデータ分類装置における、データ分類処理の手順を示すフローチャートである。以下、図１３に示す手順に沿って、図１２に示す各部の機能を順次説明する。
【０１１５】
まず、訓練データあるいは分類対象データとして使用される入力情報および出力情報を、データ入力部１２００により装置内部に取り込み（ステップＳ１３０１）、取り込んだ入力情報を、データ変換部１２０１により所定の形式に変換（具体的にはベクトル化）する（ステップＳ１３０２）。
【０１１６】
なお、ベクトル化された訓練データを以下では事例という。通常は分類の判明しているデータを訓練データとして使用するが、本発明では事例の中に、分類の判明しているものとそうでないものとが混在しているものとする（すなわち、事例の一部には分類が付与されていない）。この分類不明の事例は、もっぱら以下で説明する相対データ密度の算出時に考慮される、密度補完用の事例である。なお、分類不明の事例の存在は必須ではなく、すべての事例に分類が付与されているのでももちろんよい。
【０１１７】
次に、距離算出部１２０２により、事例のうち特に分類の付与されているものについて、他のすべての事例（分類の付与の有無を問わない）との間の距離を算出する（ステップＳ１３０３）。ここでは、訓練データは事例１〜５の５つであるものとし、分類Ａまたは分類Ｂに分類される事例１〜３と他の事例との距離が、それぞれ図１４に示すようであったとする。
【０１１８】
次に、相対データ密度算出部１２０３により、事例のうち特に分類の付与されているものについて、各事例の位置における相対データ密度を算出する（ステップＳ１３０４）。
【０１１９】
この相対データ密度は上述の式（６）や式（７）と同様に求めてもよいが、ここでは簡略化して、距離が一定以内、たとえば距離４以内の範囲に存在するデータの個数により表現するものとする。なお、この距離の閾値（ここでは４）は、交差検定などによって最適な数値を求めることができる。また、これ以外の手法で密度を算出することももちろん可能である。
【０１２０】
事例１の位置での相対データ密度＝１（距離４以内には事例１しかない）
事例２の位置での相対データ密度＝４（距離４以内には事例２〜５の４つがある）
事例３の位置での相対データ密度＝３（距離４以内には事例２・３・５の３つがある）
【０１２１】
その後データを指定して、当該データの分類先を判定するようユーザから指示があると（ステップＳ１３０５：Ｙｅｓ）、再度距離算出部１２０２により、当該データと上記事例のうち特に分類が付与されているものとの距離を算出する（ステップＳ１３０６）。ここでは分類対象データと、分類の判明している事例との距離が以下のようであったとする。
【０１２２】
距離（分類対象データ〜事例１）＝６
距離（分類対象データ〜事例２）＝２
距離（分類対象データ〜事例３）＝３
【０１２３】
そして、従来技術のｋＮＮ法、ここではｋ＝１なので１ＮＮ法によれば、分類対象データからの距離が最も小さい（分類対象データに最も近い）事例の分類を当該データの分類とするので、上記距離が最も小さい事例２の分類、すなわち分類Ｂが分類結果となるところである。
【０１２４】
しかしながら本発明では、さらに距離補正部１２０４により、ステップＳ１３０６で算出した各事例までの距離（従来のｋＮＮ法で利用する距離）を、ステップＳ１３０４で算出した各事例の位置での相対データ密度により補正する（ステップ１３０７）。この補正方法にも種々のものがあるが、ここではステップＳ１３０６の距離に、ステップＳ１３０４の相対データ密度を掛け合わせたものを補正後の距離とする。
【０１２５】
補正後距離（分類対象データ〜事例１）＝６×１＝６
補正後距離（分類対象データ〜事例２）＝２×４＝８
補正後距離（分類対象データ〜事例３）＝３×３＝９
【０１２６】
そしてデータ分類部１２０５により、ステップＳ１３０７で算出した補正後の距離を用いて、ｋＮＮ法（ここではｋ＝１なので１ＮＮ法）による分類を行う（ステップＳ１３０８）。ここでは、補正後の距離が最も小さい事例１の分類、すなわち分類Ａが分類結果となる。最後にこの分類結果を、データ出力部１２０６によりファイルあるいはディスプレイなどに出力して（ステップＳ１３０９）、本フローチャートによる処理を終了する。
【０１２７】
以上説明したように実施の形態３によれば、訓練データ（分類の付与の有無を問わない）の密度が事例１付近では低く、事例２付近では高いという分布の偏りを考慮して、分類Ａと分類Ｂとの分離面を、相対的に訓練データ密度が高い分類Ｂ側に移動するため、訓練データの分布の偏りが原因で誤って分類Ｂに分類されたデータを、正しい分類Ａに分類し直せる確率が高くなる。
【０１２８】
そして、実施の形態１〜３のような分離面の位置の補正により、補正のない場合に比べて分類精度が向上することで、逆に、同じ精度を達成するための訓練データの必要数を減らせるという利点もある。さらに、訓練データの数が減ることで学習や判別の速度の向上も期待できる。
【０１２９】
なお、上述したデータ入力部６００／１２００、データ変換部６０１／１２０１、ＳＶＭ学習部６０２、ｃ値算出部６０３、データ分類部６０４／１２０５、データ出力部６０５／１２０６、距離算出部１２０２、相対データ密度算出部１２０３および距離補正部１２０４は、具体的にはＨＤ５０５からＲＡＭ５０３に読み出されたプログラムをＣＰＵ５０１が実行することにより実現される。このプログラムはＨＤ５０５のほか、ＦＤ５０７、ＣＤ−ＲＷ５０９、ＭＯなどの各種の記録媒体に格納して配布することができ、ネットワークを介して配布することも可能である。
【０１３０】
【発明の効果】
以上説明したように請求項１に記載の発明は、複数のデータの存在する空間を分離面により各分類ごとの空間に分割するデータ分類装置において、分類対象データの位置における、第１の分類に分類される訓練データの密度を算出する第１の密度算出手段と、前記分類対象データの位置における、第２の分類に分類される訓練データの密度を算出する第２の密度算出手段と、前記第１の密度算出手段により算出された密度および前記第２の密度算出手段により算出された密度にもとづいて前記分離面の位置を補正する分離面位置補正手段と、を備えたので、第１の分類と第２の分類との境界となる分離面の位置が、上記各分類に属する訓練データの密度に応じて補正され、これによって、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類装置が得られるという効果を奏する。
【０１３１】
また、請求項２に記載の発明は、前記請求項１に記載の発明において、前記分離面位置補正手段が、前記第１の分類または前記第２の分類のうち、前記第１の密度算出手段または前記第２の密度算出手段により算出された密度が相対的に高い側へ前記分離面の位置を補正するので、訓練データの分布が均一でない場合に、訓練データ密度の相対的に高い分類へデータが分類されやすいという特性が修正され、これによって、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類装置が得られるという効果を奏する。
【０１３２】
また、請求項３に記載の発明は、前記請求項１または請求項２に記載の発明において、前記第１の密度算出手段が前記第１の分類に分類されていない訓練データも含めて前記密度を算出するので、補正後の分離面の位置を決定する訓練データ密度は、第１の分類が付与された訓練データのほか、正確な分類は不明であるものの、第１の分類が付与される確率の高い訓練データを含めて計算され、これによって、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類装置が得られるという効果を奏する。
【０１３３】
また、請求項４に記載の発明は、前記請求項１〜請求項３のいずれか一つに記載の発明において、前記第１の密度算出手段が前記第１の分類に分類される訓練データのうち一部の訓練データを用いて前記密度を算出するので、補正後の分離面の位置を決定する訓練データ密度は、前記空間内に存在する一部の訓練データの密度によって近似され、これによって、計算量を抑制しつつ、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類装置が得られるという効果を奏する。
【０１３４】
また、請求項５に記載の発明は、前記請求項４に記載の発明において、前記一部の訓練データは前記分離面からの距離が所定の条件を満たす訓練データであるので、補正後の分離面の位置を決定する訓練データ密度は、たとえば補正前の分離面からの距離が一定の訓練データの密度（補正前の分離面に対して平行な面上での訓練データ密度）によって近似され、これによって、計算量を抑制しつつ、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類装置が得られるという効果を奏する。
【０１３５】
また、請求項６に記載の発明は、前記請求項１〜請求項５のいずれか一つに記載の発明において、前記第１の密度算出手段が前記第１の分類に分類される訓練データを含む第１の訓練データ集合および前記第１の訓練データ集合から一部の訓練データを除外した第２の訓練データ集合を用いて前記密度を算出するので、補正後の分離面の位置を決定する訓練データ密度は、補正前の分離面に対して垂直な方向での訓練データ密度によって近似され、これによって、計算量を抑制しつつ、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類装置が得られるという効果を奏する。
【０１３６】
また、請求項７に記載の発明は、前記請求項１〜請求項６のいずれか一つに記載の発明において、前記第１の密度算出手段が前記訓練データ間の距離にもとづいて前記密度を算出するので、補正後の分離面の位置を決定する訓練データ密度の算出に複雑な計算を必要とせず、これによって、計算量を抑制しつつ、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類装置が得られるという効果を奏する。
【０１３７】
また、請求項８に記載の発明は、複数のデータの存在する空間を分離面により各分類ごとの空間に分割するデータ分類方法において、分類対象データの位置における、第１の分類に分類される訓練データの密度を算出する第１の密度算出工程と、前記分類対象データの位置における、第２の分類に分類される訓練データの密度を算出する第２の密度算出工程と、前記第１の密度算出工程で算出された密度および前記第２の密度算出工程で算出された密度にもとづいて前記分離面の位置を補正する分離面位置補正工程と、を含んだので、第１の分類と第２の分類との境界となる分離面の位置が、上記各分類に属する訓練データの密度に応じて補正され、これによって、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類方法が得られるという効果を奏する。
【０１３８】
また、請求項９に記載の発明は、前記請求項８に記載の発明において、前記分離面位置補正工程では、前記第１の分類または前記第２の分類のうち、前記第１の密度算出工程または前記第２の密度算出工程で算出された密度が相対的に高い側へ前記分離面の位置を補正するので、訓練データの分布が均一でない場合に、訓練データ密度の相対的に高い分類へデータが分類されやすいという特性が修正され、これによって、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類方法が得られるという効果を奏する。
【０１３９】
また、請求項１０に記載の発明は、前記請求項８または請求項９に記載の発明において、前記第１の密度算出工程では前記第１の分類に分類されていない訓練データも含めて前記密度を算出するので、補正後の分離面の位置を決定する訓練データ密度は、第１の分類が付与された訓練データのほか、正確な分類は不明であるものの、第１の分類が付与される確率の高い訓練データを含めて計算され、これによって、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類方法が得られるという効果を奏する。
【０１４０】
また、請求項１１に記載の発明は、前記請求項８〜請求項１０のいずれか一つに記載の発明において、前記第１の密度算出工程では前記第１の分類に分類される訓練データのうち一部の訓練データを用いて前記密度を算出するので、補正後の分離面の位置を決定する訓練データ密度は、前記空間内に存在する一部の訓練データの密度によって近似され、これによって、計算量を抑制しつつ、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類方法が得られるという効果を奏する。
【０１４１】
また、請求項１２に記載の発明は、前記請求項１１に記載の発明において、前記一部の訓練データは前記分離面からの距離が所定の条件を満たす訓練データであるので、補正後の分離面の位置を決定する訓練データ密度は、たとえば補正前の分離面からの距離が一定の訓練データの密度（補正前の分離面に対して平行な面上での訓練データ密度）によって近似され、これによって、計算量を抑制しつつ、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類方法が得られるという効果を奏する。
【０１４２】
また、請求項１３に記載の発明は、前記請求項８〜請求項１２のいずれか一つに記載の発明において、前記第１の密度算出工程では前記第１の分類に分類される訓練データを含む第１の訓練データ集合および前記第１の訓練データ集合から一部の訓練データを除外した第２の訓練データ集合を用いて前記密度を算出するので、補正後の分離面の位置を決定する訓練データ密度は、補正前の分離面に対して垂直な方向での訓練データ密度によって近似され、これによって、計算量を抑制しつつ、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類方法が得られるという効果を奏する。
【０１４３】
また、請求項１４に記載の発明は、前記請求項８〜請求項１３のいずれか一つに記載の発明において、前記第１の密度算出工程では前記訓練データ間の距離にもとづいて前記密度を算出するので、補正後の分離面の位置を決定する訓練データ密度の算出に複雑な計算を必要とせず、これによって、計算量を抑制しつつ、訓練データの分布が均一でない場合にも精度よくデータを分類することが可能なデータ分類方法が得られるという効果を奏する。
【０１４４】
また、請求項１５に記載の発明によれば、前記請求項８〜請求項１４のいずれか一つに記載された方法をコンピュータに実行させることが可能なプログラムが得られるという効果を奏する。
【図面の簡単な説明】
【図１】従来技術のＳＶＭによる分類の原理を模式的に示す説明図である。
【図２】従来技術のＳＶＭによる分類の原理と、本発明のＳＶＭによる分類の原理とを対比して示す説明図である。
【図３】従来技術のＳＶＭによる分類の原理と、本発明のＳＶＭによる分類の原理とを対比して示す説明図である。
【図４】本発明の実施の形態２にかかるデータ分類装置における、訓練データ密度の推定の原理を示す説明図である。
【図５】本発明の実施の形態１によるデータ分類装置のハードウエア構成の一例を示す説明図である。
【図６】本発明の実施の形態１によるデータ分類装置の構成を機能的に示す説明図である。
【図７】本発明の実施の形態１によるデータ分類装置における、データ分類処理の手順を示すフローチャートである。
【図８】本発明の実施の形態１によるデータ分類装置における、ｃ値算出処理（図７のステップＳ７０５）の手順を詳細に示すフローチャートである。
【図９】本発明の実施の形態１によるデータ分類装置における、分類対象データのスコアとその分類結果との関係を示す説明図である。
【図１０】本発明の実施の形態２によるデータ分類装置における、ｃ値算出処理（図７のステップＳ７０５）の手順を詳細に示すフローチャートである。
【図１１】本発明の実施の形態２によるデータ分類装置における、分類対象データのスコアとその分類結果との関係を示す説明図である。
【図１２】本発明の実施の形態３によるデータ分類装置の構成を機能的に示す説明図である。
【図１３】本発明の実施の形態３によるデータ分類装置における、データ分類処理の手順を示すフローチャートである。
【図１４】本発明の実施の形態３によるデータ分類装置に入力される、事例（訓練データ）間の距離の一覧を示す説明図である。
【符号の説明】
５００  バス
５０１  ＣＰＵ
５０２  ＲＯＭ
５０３  ＲＡＭ
５０４  ＨＤＤ
５０５  ＨＤ
５０６  ＦＤＤ
５０７  ＦＤ
５０８  ＣＤ−ＲＷドライブ
５０９  ＣＤ−ＲＷ
５１０  ディスプレイ
５１１  キーボード
５１２  マウス
５１３  ネットワークＩ／Ｆ
５１４  通信ケーブル
６００，１２００  データ入力部
６０１，１２０１  データ変換部
６０２  ＳＶＭ学習部
６０３  ｃ値算出部
６０４，１２０５  データ分類部
６０５，１２０６  データ出力部
１２０２  距離算出部
１２０３  相対データ密度算出部
１２０４  距離補正部
【図１】
2004341959.tif 000020
【図２】
2004341959.tif 000021
【図３】
2004341959.tif 000022
【図４】
2004341959.tif 000023
【図５】
2004341959.tif 000024
【図６】
2004341959.tif 000025
【図７】
2004341959.tif 000026
【図８】
2004341959.tif 000027
【図９】
2004341959.tif 000028
【図１０】
2004341959.tif 000029
【図１１】
2004341959.tif 000030
【図１２】
2004341959.tif 000031
【図１３】
2004341959.tif 000032
【図１４】
2004341959.tif 000033