【手続補正書】
【提出日】平成19年9月14日(2007.9.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
n個の分類対象を、K個のクラスタに分類する分類装置であって、
当該n個の分類対象をK個のクラスタへ分割する初期分割部、
K個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（centroid）を計算し、n個の分類対象のそれぞれについて、当該分類対象を、K個のセントロイドのうち当該分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、K個のクラスタに再分類して、クラスタへの分割を更新する更新部、
前記更新部により更新される前と後でクラスタへの分割に変化がある場合、前記更新部に更新を繰り返させる繰返制御部、
前記更新部により更新される前と後でクラスタへの分割に変化がない場合、当該クラスタへの分割を出力する出力部
を備え、
前記更新部は、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う
ことを特徴とする分類装置。
【請求項２】
K個のクラスタに分類されたn個の分類対象を、K+1個のクラスタに分類する分類装置であって、
当該K個のクラスタのいずれか１つを、２つに分割することにより、当該n個の分類対象を、K+1個のクラスタへ分割する初期分割部、
K+1個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（centroid）を計算し、n個の分類対象のそれぞれについて、当該分類対象を当該K+1個のセントロイドのうち当該分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、K+1個のクラスタに再分類して、クラスタへの分割を更新する更新部、
前記更新部により更新される前と後でクラスタへの分割に変化がある場合、前記更新部に更新を繰り返させる繰返制御部、
前記更新部により更新される前と後でクラスタへの分割に変化がない場合、当該K+1個のクラスタへの分割を出力する出力部
を備えることを特徴とする分類装置。
【請求項３】
K個のクラスタに分類されたn個の分類対象を、K+1個のクラスタに分類する分類装置であって、
当該K個のクラスタのいずれか１つを、２つに分割することにより（以下、当該２つに分類されたクラスタのそれぞれを「特定クラスタ」と呼ぶ。）、当該n個の分類対象を、K+1個のクラスタへ分割する初期分割部、
K+1個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（centroid）を計算し、当該分類対象のそれぞれについて、当該分類対象が分類されているクラスタのセントロイドと、当該特定クラスタのセントロイドのうち当該特定分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、K+1個のクラスタに再分類して、クラスタへの分割を更新する更新部、
前記更新部により更新される前と後でクラスタへの分割に変化がある場合、前記更新部に更新を繰り返させる繰返制御部、
前記更新部により更新される前と後でクラスタへの分割に変化がない場合、当該K+1個のクラスタへの分割を出力する出力部
を備え、
前記更新部は、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う
ことを特徴とする分類装置。
【請求項４】
n個の分類対象を、K個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備える分類装置にて実行される分類方法であって、
前記初期分割部が、当該n個の分類対象をK個のクラスタへ分割する初期分割工程、
前記更新部が、K個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（centroid）を計算し、n個の分類対象のそれぞれについて、当該分類対象を、K個のセントロイドのうち当該分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、K個のクラスタに再分類して、クラスタへの分割を更新する更新工程、
前記繰返制御部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がある場合、前記更新工程による更新を繰り返させる繰返制御工程、
前記出力部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がない場合、当該クラスタへの分割を出力する出力工程
を備え、
前記更新工程では、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う
ことを特徴とする分類装置。
【請求項５】
K個のクラスタに分類されたn個の分類対象を、K+1個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備える分類装置にて実行される分類方法であって、
前記初期分割部が、当該K個のクラスタのいずれか１つを、２つに分割することにより、当該n個の分類対象を、K+1個のクラスタへ分割する初期分割工程、
前記更新部が、K+1個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（centroid）を計算し、n個の分類対象のそれぞれについて、当該分類対象を当該K+1個のセントロイドのうち当該分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、K+1個のクラスタに再分類して、クラスタへの分割を更新する更新工程、
前記繰返制御部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がある場合、前記更新工程による更新を繰り返させる繰返制御工程、
前記出力部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がない場合、当該K+1個のクラスタへの分割を出力する出力工程
を備えることを特徴とする分類方法。
【請求項６】
K個のクラスタに分類されたn個の分類対象を、K+1個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備える分類装置にて実行される分類方法であって、
前記初期分割部が、当該K個のクラスタのいずれか１つを、２つに分割することにより（以下、当該２つに分類されたクラスタのそれぞれを「特定クラスタ」と呼ぶ。）、当該n個の分類対象を、K+1個のクラスタへ分割する初期分割工程、
前記更新部が、K+1個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（centroid）を計算し、当該分類対象のそれぞれについて、当該分類対象が分類されているクラスタのセントロイドと、当該特定クラスタのセントロイドのうち当該特定分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、K+1個のクラスタに再分類して、クラスタへの分割を更新する更新工程、
前記繰返制御部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がある場合、前記更新工程による更新を繰り返させる繰返制御工程、
前記出力部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がない場合、当該K+1個のクラスタへの分割を出力する出力工程
を備えることを特徴とする分類方法。
【請求項７】
コンピュータを、
請求項１から３のいずれか１項に記載の分類装置の各部として機能させる
ことを特徴とするプログラム。
【請求項８】
コンピュータに、
請求項４から６のいずれか１項に記載の分類方法の各工程を実行させる
ことを特徴とするプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
一方、更新部は、K+1個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイドを計算し、当該分類対象のそれぞれについて、当該分類対象が分類されているクラスタのセントロイドと、当該特定クラスタのセントロイドのうち当該特定分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、K+1個のクラスタに再分類して、クラスタへの分割を更新する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
一方、更新工程では、更新部が、K+1個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイドを計算し、当該分類対象のそれぞれについて、当該分類対象が分類されているクラスタのセントロイドと、当該特定クラスタのセントロイドのうち当該特定分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、K+1個のクラスタに再分類して、クラスタへの分割を更新する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
ケース（ｂ）の場合、所属する分類対象の個数が最も多いクラスタを選択してこれを２分割すればよい。もっとも、これに限定されるわけではない。選択されたクラスタを２分割する手法は、上記のものと同様である。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
（K-Means Bisection）
以下では、K-Means Bisectionという分類手法について説明する。この手法は、K-Means Curvingとも呼ばれる。図３は、本手法による分類処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１０３
【補正方法】変更
【補正の内容】
【０１０３】
そして、Cb = pKもしくはCb = pK+1のとき、セントロイドpK，pK+1のうち、xiに最も近いセントロイドpmを探す（ステップＳ５０６）。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１１０
【補正方法】変更
【補正の内容】
【０１１０】
本手法では、クラスタの数を１増やすことができるので、本手法を繰り返し適用することによって、所望の数への分類が可能となる。なお、段落００５８〜００６０でも述べた通り、本手法ならびに上記の手法において、所望の数のクラスタに分類対象を初期分割してから処理を開始することとすれば、クラスタの数を１増やすのではなく、任意の個数のクラスタに分類を行うことができる。
【手続補正８】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2006092504.tif 000001
【手続補正９】
【補正対象書類名】図面
【補正対象項目名】図４
【補正方法】変更
【補正の内容】
【図４】
2006092504.tif 000002
【手続補正１０】
【補正対象書類名】図面
【補正対象項目名】図５
【補正方法】変更
【補正の内容】
【図５】
2006092504.tif 000003