(57)【要約】【課題】  ｎ個の分類対象をＫ個のクラスタに分類する分類装置等を提供する。【解決手段】  分類装置２０１の初期分割部２０２は、ｎ個の分類対象をＫ個のクラスタへ分割し、更新部２０３は、Ｋ個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイドを計算し、ｎ個の分類対象のそれぞれについて、当該分類対象を、Ｋ個のセントロイドのうち当該分類対象に最も近いもの対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ個のクラスタに再分類して、クラスタへの分割を更新し、繰返制御部２０４は、クラスタへの分割に変化がなくなるまで更新部２０３に更新を繰り返させ、出力部２０５は、クラスタへの分割に変化がなくなったら、これを出力する。【選択図】  図２
2006092504.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個の分類対象を、Ｋ個のクラスタに分類する分類装置であって、
当該ｎ個の分類対象をＫ個のクラスタへ分割する初期分割部、
Ｋ個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（ｃｅｎｔｒｏｉｄ）を計算し、ｎ個の分類対象のそれぞれについて、当該分類対象を、Ｋ個のセントロイドのうち当該分類対象に最も近いもの対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ個のクラスタに再分類して、クラスタへの分割を更新する更新部、
前記更新部により更新される前と後でクラスタへの分割に変化がある場合、前記更新部に更新を繰り返させる繰返制御部、
前記更新部により更新される前と後でクラスタへの分割に変化がない場合、当該クラスタへの分割を出力する出力部
を備え、
前記更新部は、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う
ことを特徴とする分類装置。
【請求項２】
Ｋ個のクラスタに分類されたｎ個の分類対象を、Ｋ＋１個のクラスタに分類する分類装置であって、
当該Ｋ個のクラスタのいずれか１つを、２つに分割することにより、当該ｎ個の分類対象を、Ｋ＋１個のクラスタへ分割する初期分割部、
Ｋ＋１個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（ｃｅｎｔｒｏｉｄ）を計算し、ｎ個の分類対象のそれぞれについて、当該分類対象を当該Ｋ＋１個のセントロイドのうち当該分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ＋１個のクラスタに再分類して、クラスタへの分割を更新する更新部、
前記更新部により更新される前と後でクラスタへの分割に変化がある場合、前記更新部に更新を繰り返させる繰返制御部、
前記更新部により更新される前と後でクラスタへの分割に変化がない場合、当該Ｋ＋１個のクラスタへの分割を出力する出力部
を備えることを特徴とする分類装置。
【請求項３】
Ｋ個のクラスタに分類されたｎ個の分類対象を、Ｋ＋１個のクラスタに分類する分類装置であって、
当該Ｋ個のクラスタのいずれか１つを、２つに分割することにより（以下、当該２つに分類されたクラスタのそれぞれを「特定クラスタ」と呼ぶ。）、当該ｎ個の分類対象を、Ｋ＋１個のクラスタへ分割する初期分割部、
Ｋ＋１個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（ｃｅｎｔｒｏｉｄ）を計算し、当該分類対象のそれぞれについて、当該分類対象が分類されているクラスタのセントロイドと、当該特定クラスタのセントロイドと、のうち当該特定分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ＋１個のクラスタに再分類して、クラスタへの分割を更新する更新部、
前記更新部により更新される前と後でクラスタへの分割に変化がある場合、前記更新部に更新を繰り返させる繰返制御部、
前記更新部により更新される前と後でクラスタへの分割に変化がない場合、当該Ｋ＋１個のクラスタへの分割を出力する出力部
を備え、
前記更新部は、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う
ことを特徴とする分類装置。
【請求項４】
ｎ個の分類対象を、Ｋ個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備える分類装置にて実行される分類方法であって、
前記初期分割部が、当該ｎ個の分類対象をＫ個のクラスタへ分割する初期分割工程、
前記更新部が、Ｋ個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（ｃｅｎｔｒｏｉｄ）を計算し、ｎ個の分類対象のそれぞれについて、当該分類対象を、Ｋ個のセントロイドのうち当該分類対象に最も近いもの対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ個のクラスタに再分類して、クラスタへの分割を更新する更新工程、
前記繰返制御部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がある場合、前記更新工程による更新を繰り返させる繰返制御工程、
前記出力部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がない場合、当該クラスタへの分割を出力する出力工程
を備え、
前記更新工程では、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う
ことを特徴とする分類装置。
【請求項５】
Ｋ個のクラスタに分類されたｎ個の分類対象を、Ｋ＋１個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備える分類装置にて実行される分類方法であって、
前記初期分割部が、当該Ｋ個のクラスタのいずれか１つを、２つに分割することにより、当該ｎ個の分類対象を、Ｋ＋１個のクラスタへ分割する初期分割工程、
前記更新部が、Ｋ＋１個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（ｃｅｎｔｒｏｉｄ）を計算し、ｎ個の分類対象のそれぞれについて、当該分類対象を当該Ｋ＋１個のセントロイドのうち当該分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ＋１個のクラスタに再分類して、クラスタへの分割を更新する更新工程、
前記繰返制御部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がある場合、前記更新工程による更新を繰り返させる繰返制御工程、
前記出力部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がない場合、当該Ｋ＋１個のクラスタへの分割を出力する出力工程
を備えることを特徴とする分類方法。
【請求項６】
Ｋ個のクラスタに分類されたｎ個の分類対象を、Ｋ＋１個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備える分類装置にて実行される分類方法であって、
前記初期分割部が、当該Ｋ個のクラスタのいずれか１つを、２つに分割することにより（以下、当該２つに分類されたクラスタのそれぞれを「特定クラスタ」と呼ぶ。）、当該ｎ個の分類対象を、Ｋ＋１個のクラスタへ分割する初期分割工程、
前記更新部が、Ｋ＋１個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイド（ｃｅｎｔｒｏｉｄ）を計算し、当該分類対象のそれぞれについて、当該分類対象が分類されているクラスタのセントロイドと、当該特定クラスタのセントロイドと、のうち当該特定分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ＋１個のクラスタに再分類して、クラスタへの分割を更新する更新工程、
前記繰返制御部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がある場合、前記更新工程による更新を繰り返させる繰返制御工程、
前記出力部が、前記更新工程にて更新される前と後でクラスタへの分割に変化がない場合、当該Ｋ＋１個のクラスタへの分割を出力する出力工程
を備えることを特徴とする分類方法。
【請求項７】
コンピュータを、
請求項１から３のいずれか１項に記載の分類装置の各部として機能させる
ことを特徴とするプログラム。
【請求項８】
コンピュータに、
請求項４から６のいずれか１項に記載の分類方法の各工程を実行させる
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、分類対象を複数のクラスタに分類するのに好適な分類装置、分類方法、ならびに、これらをコンピュータにて実現するためのプログラムに関する。
【背景技術】
【０００２】  従来から、分類対象を複数のクラスタに分類するクラスタリングの技術が種々提案されている。たとえば、以下の文献に、このようなクラスタリング技術が開示されている。
【非特許文献１】石川佳治、北川博之、「忘却の概念に基づく文書クラスタリング手法の改良方式について」、社団法人情報処理学会研究報告、２００３−ＦＩ−７３（１）、２００３年１１月１３日
【０００３】  ［非特許文献１］には、Ｋ−ｍｅａｎｓと呼ばれる手法が開示されている。すなわち、ｎ個の分類対象をＫ個のクラスタに分類したい場合には、
（１）Ｋ個の分類対象をランダムに選択して、Ｋ個のクラスタの代表とする。
（２）残りのｎ−Ｋ個の分類対象を、代表が最も近くにあるクラスタに分類する。
（３）分類に変化がなければ、終了する。
（４）Ｋ個のクラスタについて代表を選び直す。
（５）工程（２）へ戻る。【０００４】  一方、クラスタに関する処理には、これに属する分類対象のセントロイド（ｃｅｎｔｒｏｉｄ）を求める処理があるが、一般にセントロイドとしては、分類対象の平均や重み付き平均が用いられている。そして、セントロイドを上記の「クラスタの代表」とする手法も知られている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】  しかしながら、このようなクラスタ分類については、様々な手法が強く求められている。特に、分類対象によってクラスタ分類の収束性が異なるので、できるだけ高速に収束するような手法が望ましい。【０００６】  本発明は、上記の課題を解決するもので、分類対象を複数のクラスタに分類するのに好適な分類装置、分類方法、ならびに、これらをコンピュータにて実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】  以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。【０００８】  本発明の第１の観点に係る分類装置は、ｎ個の分類対象を、Ｋ個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備え、以下のように構成する。【０００９】  すなわち、初期分割部は、当該ｎ個の分類対象をＫ個のクラスタへ分割する。【００１０】  一方、更新部は、Ｋ個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイドを計算し、ｎ個の分類対象のそれぞれについて、当該分類対象を、Ｋ個のセントロイドのうち当該分類対象に最も近いもの対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ個のクラスタに再分類して、クラスタへの分割を更新する。【００１１】  さらに繰返制御部は、更新部により更新される前と後でクラスタへの分割に変化がある場合、更新部に更新を繰り返させる。【００１２】  そして、出力部は、更新部により更新される前と後でクラスタへの分割に変化がない場合、当該クラスタへの分割を出力する。【００１３】  特に、更新部は、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う。【００１４】  本発明のその他の観点に係る分類装置は、Ｋ個のクラスタに分類されたｎ個の分類対象を、Ｋ＋１個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備え、以下のように構成する。【００１５】  すなわち、初期分割部は、当該Ｋ個のクラスタのいずれか１つを、２つに分割することにより、当該ｎ個の分類対象を、Ｋ＋１個のクラスタへ分割する。【００１６】  一方、更新部は、Ｋ＋１個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイドを計算し、ｎ個の分類対象のそれぞれについて、当該分類対象を当該Ｋ＋１個のセントロイドのうち当該分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ＋１個のクラスタに再分類して、クラスタへの分割を更新する。【００１７】  さらに、繰返制御部は、更新部により更新される前と後でクラスタへの分割に変化がある場合、更新部に更新を繰り返させる。【００１８】  そして、出力部は、更新部により更新される前と後でクラスタへの分割に変化がない場合、当該Ｋ＋１個のクラスタへの分割を出力する。【００１９】  また、本発明の分類装置は、Ｋ個のクラスタに分類されたｎ個の分類対象を、Ｋ＋１個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備え、以下のように構成する。【００２０】  すなわち、初期分割部は、当該Ｋ個のクラスタのいずれか１つを、２つに分割することにより（以下、当該２つに分類されたクラスタのそれぞれを「特定クラスタ」と呼ぶ。）、当該ｎ個の分類対象を、Ｋ＋１個のクラスタへ分割する。【００２１】  一方、更新部は、Ｋ＋１個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイドを計算し、当該分類対象のそれぞれについて、当該分類対象が分類されているクラスタのセントロイドと、当該特定クラスタのセントロイドと、のうち当該特定分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ＋１個のクラスタに再分類して、クラスタへの分割を更新する。【００２２】  さらに、繰返制御部は、更新部により更新される前と後でクラスタへの分割に変化がある場合、更新部に更新を繰り返させる。【００２３】  そして、出力部は、更新部により更新される前と後でクラスタへの分割に変化がない場合、当該Ｋ＋１個のクラスタへの分割を出力する。【００２４】  特に、更新部は、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う。【００２５】  本発明のその他の観点に係る分類方法は、ｎ個の分類対象を、Ｋ個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備える分類装置にて実行され、初期分割工程、更新工程、繰返制御工程、出力工程を備え、以下のように構成する。【００２６】  すなわち、初期分割工程では、初期分割部が、当該ｎ個の分類対象をＫ個のクラスタへ分割する。【００２７】  一方、更新工程では、更新部が、Ｋ個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイドを計算し、ｎ個の分類対象のそれぞれについて、当該分類対象を、Ｋ個のセントロイドのうち当該分類対象に最も近いもの対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ個のクラスタに再分類して、クラスタへの分割を更新する。【００２８】  さらに、繰返制御工程では、繰返制御部が、更新工程にて更新される前と後でクラスタへの分割に変化がある場合、更新工程による更新を繰り返させる。【００２９】  そして、出力工程では、出力部が、更新工程にて更新される前と後でクラスタへの分割に変化がない場合、当該クラスタへの分割を出力する。【００３０】  特に、更新工程では、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う。【００３１】  本発明のその他の観点に係る分類方法は、Ｋ個のクラスタに分類されたｎ個の分類対象を、Ｋ＋１個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備える分類装置にて実行される分類方法であって、初期分割工程、更新工程、繰返制御工程、出力工程を備え、以下のように構成する。【００３２】  すなわち、初期分割工程では、初期分割部が、当該Ｋ個のクラスタのいずれか１つを、２つに分割することにより、当該ｎ個の分類対象を、Ｋ＋１個のクラスタへ分割する。【００３３】  一方、更新工程では、更新部が、Ｋ＋１個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイドを計算し、ｎ個の分類対象のそれぞれについて、当該分類対象を当該Ｋ＋１個のセントロイドのうち当該分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ＋１個のクラスタに再分類して、クラスタへの分割を更新する。【００３４】  さらに、繰返制御工程では、繰返制御部が、更新工程にて更新される前と後でクラスタへの分割に変化がある場合、更新工程による更新を繰り返させる。【００３５】  そして、出力��程では、出力部が、更新工程にて更新される前と後でクラスタへの分割に変化がない場合、当該Ｋ＋１個のクラスタへの分割を出力する。【００３６】  本発明のその他の観点に係る分類方法は、Ｋ個のクラスタに分類されたｎ個の分類対象を、Ｋ＋１個のクラスタに分類し、初期分割部、更新部、繰返制御部、出力部を備える分類装置にて実行され、初期分割工程、更新工程、繰返制御工程、出力工程を備え、以下のように構成する。【００３７】  すなわち、初期分割工程では、初期分割部が、当該Ｋ個のクラスタのいずれか１つを、２つに分割することにより（以下、当該２つに分類されたクラスタのそれぞれを「特定クラスタ」と呼ぶ。）、当該ｎ個の分類対象を、Ｋ＋１個のクラスタへ分割する。【００３８】  一方、更新工程では、更新部が、Ｋ＋１個のクラスタのそれぞれについて、当該クラスタに分類された分類対象のセントロイドを計算し、当該分類対象のそれぞれについて、当該分類対象が分類されているクラスタのセントロイドと、当該特定クラスタのセントロイドと、のうち当該特定分類対象に最も近いものに対応付け、同じセントロイドに対応付けられた分類対象を１つのクラスタとして、Ｋ＋１個のクラスタに再分類して、クラスタへの分割を更新する。【００３９】  さらに、制御工程では、繰返制御部が、更新工程にて更新される前と後でクラスタへの分割に変化がある場合、更新工程による更新を繰り返させる。【００４０】  そして、出力工程では、出力部が、更新工程にて更新される前と後でクラスタへの分割に変化がない場合、当該Ｋ＋１個のクラスタへの分割を出力する。【００４１】  特に、更新工程では、当該セントロイドの計算を、分類対象が、現在分類されているクラスタのセントロイド以外のセントロイドに対応付けられるごとに行う。【００４２】  本発明のその他の観点に係るプログラムは、コンピュータを、上記分類装置の各部として機能させるように構成する。【００４３】  本発明のその他の観点に係るプログラムは、コンピュータに、上記分類方法の各工程を実行させるように構成する。【００４４】  上記のプログラムは、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）などの各種の記録媒体に記録することができるほか、インターネットなどのコンピュータ通信網を介して配布することができる。
【発明の効果】
【００４５】  本発明によれば、分類対象を複数のクラスタに分類するのに好適な分類装置、分類方法、ならびに、これらをコンピュータにて実現するためのプログラムを提供することができるようになる。
【発明を実施するための最良の形態】
【００４６】  以下、添付図面を参照して、本発明の実施の形態について説明する。
【実施例１】
【００４７】  図１は、本発明の分類装置として機能しうる典型的な情報処理装置の概要構成を示す模式図である。以下、図１を参照して説明する。【００４８】  情報処理装置１０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ；中央処理ユニット）１０２によって制御される。情報処理装置１０１に電源を投入すると、ＣＰＵ  １０２は、ＲＯＭ  １０３に記憶されたＩＰＬ（Ｉｎｉｔｉａｌ  Ｐｒｏｇｒａｍ  Ｌｏａｄｅｒ；初期プログラムローダ）を実行する。【００４９】  ＩＰＬは、ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭなどの記録媒体に記憶されたＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ；オペレーティング・システム）プログラムを読み出して実行するプログラムである。【００５０】  ＯＳを起動した後、ＣＰＵ  １０２は、キーボード１０５やマウス１０６などにより入力されたユーザの指示にしたがって、あるいは、ハードディスクなどにあらかじめ記述された設定ファイルの内容にしたがって、ハードディスクなどに記憶されたアプリケーションプログラムを実行する。【００５１】  当該アプリケーションプログラムを実行することにより、情報処理装置１０１は、設計支援装置として機能することとなる。【００５２】  ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭなどの記憶媒体に、各種の情報が記録されることになる。【００５３】  ＣＰＵ  １０２は、このプログラムの実行の際に、ＲＡＭ  １０７を一時的な作業用記憶領域として用いる。このほか、一時的な作業用記憶領域として、ＣＰＵ  １０２内に設けられたレジスタやキャッシュ（図示せず）が使われる。【００５４】  プログラムの実行に伴ない、各種の情報をユーザに報告したり、途中経過を見せるため、ＣＰＵ  １０２は、液晶ディスプレイやＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）などの表示装置１０８に当該情報を表示することができる。マウス１０６による指示操作では、マウス１０６を移動することにより、画面に表示されたカーソルが移動し、マウス１０６をクリックすることにより、カーソルが指すメニュー項目を選択することができる。【００５５】  情報処理装置１０１は、ＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）やモデムなどのインターフェース１０９を介してインターネットなどのコンピュータ通信網と通信を行うことができる。インターフェース１０９を介して受信した順序木を処理の対象としたり、抽出したパターンをインターフェース１０９を介して送信したり、インターフェース１０９を介して受信したプログラムを実行したり、などができる。【００５６】  図２は、本発明の実施形態に係る分類装置の概要構成を示す模式図である。以下、本図を参照して説明する。【００５７】  本発明の分類装置２０１は、初期分割部２０２、更新部２０３、繰返制御部２０４、出力部２０５を備える。【００５８】  初期分割部２０２は、与えられたｎ個の分類対象を、所定の数のクラスタに分類するが、この分類は、いわば「初期値」に相当するものであり、ランダムに分割しても良いし、適当な領域（バケット）を���めて分割しても良いし、従来の技術のように、分類対象をランダムに選択してこれを各クラスタの代表値としても良い。【００５９】  なお、後述するように、分割には、以下のような場合がある。
（ａ）ｎ個の分類対象をＫ個のクラスタに初期分割する。
（ｂ）すでにＫ個のクラスタに分割されたｎ個の分類対象について、いずれか１個のクラスタを選択してこれを２つに分割し、全体としてＫ＋１個のクラスタに初期分割する。【００６０】  ケース（ｂ）の場合、所属する分類対象の個数が最も多いクラスタを選択してこれを２分割することが望ましい。もっとも、これに限定されるわけではない。選択されたクラスタを２分割する手法は、上記のものと同様である。【００６１】  分類対象やそれがいずれのクラスタに属するか、は、ＲＡＭ  １０７やハードディスク１０４に記憶されるので、ＣＰＵ  １０２は、これらと共働して、初期分割部２０２として機能する。【００６２】  つぎに、更新部２０３は、クラスタの分割を更新する。本実施形態では、クラスタの分割更新に、クラスタの代表値となるセントロイドの計算と、どのセントロイドへどの分類対象を再分類するのか、の選択の仕方が、従来の発明と異なる。詳細については後述する。【００６３】  したがって、ＣＰＵ  １０２は、ＲＡＭ  １０７やハードディスク１０４と共働して、更新部２０３として機能する。【００６４】  そして、繰返制御部２０４は、更新部２０３によるクラスタの分割に変化があった場合、さらに分割の更新を繰り返すよう更新部２０３を制御する。【００６５】  したがって、ＣＰＵ  １０２は、ＲＡＭ  １０７やハードディスク１０４と共働して、繰返制御部２０４として機能する。【００６６】  最後に、出力部２０５は、更新部２０３によるクラスタの分割に変化がなかった場合、現在の分割を分類結果として出力する。【００６７】  したがって、ＣＰＵ  １０２は、ＲＡＭ  １０７やハードディスク１０４と共働して、出力部２０５として機能する。【００６８】  以下、ｎ個の分類対象
ｘ１，．．．，ｘｎ
をＫ個もしくはＫ＋１個のクラスタ
Ｃ１，．．．，ＣＫ（，ＣＫ＋１）
に分割する場合を考える。それぞれのクラスタのセントロイドは、
ｐ１，．．．，ｐＫ（，ｐＫ＋１）
とする。【００６９】  また、分類対象ｘｉをクラスタＣｊに追加することを
Ｃｊ＋＝ｘｉ
と表記し、ｘｉをクラスタＣｊから削除することを
Ｃｊ−＝ｘｉ
と表記し、クラスタＣｊに分類対象ｘｉが分類されていることを
ｘｉ∈Ｃｊ
と書く。【００７０】  （Ｋ−Ｍｅａｎｓ  Ｂｉｓｅｃｔｉｏｎ）
以下では、Ｋ−Ｍｅａｎｓ  Ｂｉｓｅｃｔｉｏｎという分類手法について説明する。図３は、本手法による分類処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。【００７１】  まず、分類装置２０１は、ｎ個の分類対象の入力を受け付ける（ステップＳ３００）。【００７２】  そして、これをＫ個のクラスタに初期分割する（ステップＳ３０１）。【００７３】  さらに、クラスタＣ１，．．．，ＣＫのそれぞれについて、セントロイドｐ１，．．．，ｐＫを計算する（ステップＳ３０２）。セントロイドｐｊは、ｘｉ∈Ｃｊなるｘｉの（重み付き）平均である。【００７４】  そして、ＲＡＭ  １０７に用意された変数ｉに１を代入し（ステップＳ３０３）、ｉ≦ｎである間（ステップＳ３０４）、以下を繰り返す。【００７５】  まず、ｘｉ∈ＣｂなるクラスタＣｂを取得する（ステップＳ３０５）。【００７６】  セントロイドｐ１，．．．，ｐＫのうち、ｘｉに最も近いセントロイドｐｍを探す（ステップＳ３０６）。【００７７】  そして、ｂ＝ｍでなければ（ステップＳ３０７；Ｎｏ）、
Ｃｂ−＝ｘｉ；
Ｃｍ＋＝ｘｉ
を実行して、ｘｉが所属するクラスタを変更する（ステップＳ３０８）。【００７８】  そして、ＣｂおよびＣｍのセントロイドｐｂおよびｐｍを再計算する（ステップＳ３０９）。【００７９】  ステップＳ３０９の後、もしくは、ｂ＝ｍであれば（ステップＳ３０７；Ｙｅｓ）、ｉの値を１増やして（ステップＳ３１０）、ステップＳ３０４に戻る。【００８０】  ついで、今回のステップＳ３０４〜ステップＳ３０９で、ステップＳ３０８による更新が行われた場合（ステップＳ３１１；Ｙｅｓ）、ステップＳ３０３に戻る。【００８１】  更新が行われなかった場合（ステップＳ３１１；Ｎｏ）、現在のクラスタ分類を出力して（ステップＳ３１２）、本処理を終了する。【００８２】  なお、ステップＳ３０９においてセントロイドを再計算しているが、ここでセントロイドを計算するのではなく、ステップＳ３０３に戻る直前にセントロイドを再計算する、という手法を採用することもできる。【００８３】  （Ｋ−Ｍｅａｎｓ  Ｓｔｅｍｍｉｎｇ）
以下では、Ｋ−Ｍｅａｎｓ  Ｓｔｅｍｍｉｎｇという分類手法について説明する。図４は、本手法による分類処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。【００８４】  まず、分類装置２０１は、Ｋ個のクラスタに分類済みのｎ個の分類対象の入力を受け付ける（ステップＳ４００）。【００８５】  そして、Ｋ個のクラスタからいずれか１つを２つに分割して、ｎ個の分類対象をＫ＋１個のクラスタに初期分割する（ステップＳ４０１）。【００８６】  さらに、クラスタＣ１，．．．，ＣＫ，ＣＫ＋１のそれぞれについて、セントロイドｐ１，．．．，ｐＫ，ｐＫ＋１を計算する（ステップＳ４０２）。セントロイドｐｊは、ｘｉ∈Ｃｊなるｘｉの（重み付き）平均である。【００８７】  そして、ＲＡＭ  １０７に用意された変数ｉに１を代入し（ステップＳ４０３）、ｉ≦ｎである間（ステップＳ４０４）、以下を繰り返す。【００８８】  まず、ｘｉ∈ＣｂなるクラスタＣｂを取得する（ステップＳ４０５）。【００８９】  セントロイドｐ１，．．．，ｐＫ，ｐＫ＋１のうち、ｘｉに最も近いセントロイドｐｍを探す（ステップＳ４０６）。【００９０】  そして、ｂ＝ｍでなければ（ステップＳ４０７；Ｎｏ）、
Ｃｂ−＝ｘｉ；
Ｃｍ＋＝ｘｉ
を実行して、ｘｉが所属するクラスタを変更する（ステップＳ４０８）。【００９１】  そして、ＣｂおよびＣｍのセントロイドｐｂおよびｐｍを再計算する（ステップＳ４０９）。【００９２】  ステップＳ４０９の後、もしくは、ｂ＝ｍであれば（ステップＳ４０７；Ｙｅｓ）、ｉの値を１増やして（ステップＳ４１０）、ステップＳ４０４に戻る。【００９３】  ついで、今回のステップＳ４０４〜ステップＳ４０９で、ステップＳ４０８による更新が行われた場合（ステップＳ４１１；Ｙｅｓ）、ステップＳ４０３に戻る。【００９４】  更新が行われなかった場合（ステップＳ４１１；Ｎｏ）、現在のクラスタ分類を出力して（ステップＳ４１２）、本処理を終了する。【００９５】  なお、ステップＳ４０９においてセントロイドを再計算しているが、ここでセントロイドを計算するのではなく、ステップＳ４０３に戻る直前にセントロイドを再計算する、という手法を採用することもできる。【００９６】  本手法では、クラスタの数を１増やすことができるので、本手法を繰り返し適用することによって、所望の数への分類が可能となる。【００９７】  （Ｋ−Ｍｅａｎｓ  Ｍｏｇｕｌｉｎｇ）
以下では、Ｋ−Ｍｅａｎｓ  Ｍｏｇｕｌｉｎｇという分類手法について説明する。図５は、本手法による分類処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。【００９８】  まず、分類装置２０１は、Ｋ個のクラスタに分類済みのｎ個の分類対象の入力を受け付ける（ステップＳ５００）。【００９９】  そして、Ｋ個のクラスタからいずれか１つを２つに分割して、ｎ個の分類対象をＫ＋１個のクラスタに初期分割する（ステップＳ５０１）。ここで、２つに分割された結果をＣＫ，ＣＫ＋１とし、クラスタＣ１，・・・，ＣＫ−１については、分割されなかったものとする。【０１００】  さらに、クラスタＣ１，．．．，ＣＫ，ＣＫ＋１のそれぞれについて、セントロイドｐ１，．．．，ｐＫ，ｐＫ＋１を計算する（ステップＳ５０２）。セントロイドｐｊは、ｘｉ∈Ｃｊなるｘｉの（重み付き）平均である。【０１０１】  そして、ＲＡＭ  １０７に用意された変数ｉに１を代入し（ステップＳ５０３）、ｉ≦ｎである間（ステップＳ５０４）、以下を繰り返す。【０１０２】  まず、ｘｉ∈ＣｂなるクラスタＣｂを取得する（ステップＳ５０５）。【０１０３】  そして、セントロイドｐｂ，ｐＫ，ｐＫ＋１のうち、ｘｉに最も近いセントロイドｐｍを探す（ステップＳ５０６）。【０１０４】  そして、ｂ＝ｍでなければ（ステップＳ５０７；Ｎｏ）、
Ｃｂ−＝ｘｉ；
Ｃｍ＋＝ｘｉ
を実行して、ｘｉが所属するクラスタを変更する（ステップＳ５０８）。【０１０５】  そして、ＣｂおよびＣｍのセントロイドｐｂおよびｐｍを再計算する（ステップＳ５０９）。【０１０６】  ステップＳ５０９の後、もしくは、ｂ＝ｍであれば（ステップＳ５０７；Ｙｅｓ）、ｉの値を１増やして（ステップＳ５１０）、ステップＳ５０４に戻る。【０１０７】  ついで、今回のステップＳ５０４〜ステップＳ５０９で、ステップＳ５０８による更新が行われた場合（ステップＳ５１１；Ｙｅｓ）、ステップＳ５０３に戻る。【０１０８】  更新が行われなかった場合（ステップＳ５１１；Ｎｏ）、現在のクラスタ分類を出力して（ステップＳ５１２）、本処理を終了する。【０１０９】  なお、ステップＳ５０９においてセントロイドを再計算しているが、ここでセントロイドを計算するのではなく、ステップＳ５０３に戻る直前にセントロイドを再計算する、という手法を採用することもできる。【０１１０】  本手法では、クラスタの数を１増やすことができるので、本手法を繰り返し適用することによって、所望の数への分類が可能となる。
【産業上の利用可能性】
【０１１１】  以上説明したように、本発明によれば、分類対象を複数のクラスタに分類するのに好適な分類装置、分類方法、ならびに、これらをコンピュータにて実現するためのプログラムを提供することができるようになる。
【図面の簡単な説明】
【０１１２】
【図１】情報処理装置の概要構成を示す模式図である。
【図２】本発明の実施形態に係る分類装置の概要構成を示す模式図である。
【図３】本発明の実施形態に係る分類装置にて実行される分類処理の制御の流れを示すフローチャートである。
【図４】本発明の実施形態に係る分類装置にて実行される分類処理の制御の流れを示すフローチャートである。
【図５】本発明の実施形態に係る分類装置にて実行される分類処理の制御の流れを示すフローチャートである。
【符号の説明】
【０１１３】    １０１  情報処理装置
１０２  ＣＰＵ
１０３  ＲＯＭ
１０４  ＨＤ
１０５  キーボード
１０６  マウス
１０７  ＲＡＭ
１０８  表示装置
１０９  インターフェース
１１０  ＦＤドライブ
１１１  ＣＤ−ＲＯＭドライブ
２０１  分類装置
２０２  初期分割部
２０３  更新部
２０４  繰返制御部
２０５  出力部
【図１】
2006092504.tif 000003
【図２】
2006092504.tif 000004
【図３】
2006092504.tif 000005
【図４】
2006092504.tif 000006
【図５】
2006092504.tif 000007