(57)【要約】      （修正有）【課題】疎データを効率的にクラスタリングする装置、方法、プログラム及びデータ構造を提供する。【解決手段】クラスタリング処理により、スパース表現のオブジェクト特徴ベクトルｘｉをクラスタリングする。このとき、オブジェクト特徴ベクトルｘｉをスパース表現にすることで、メモリ使用量を抑制すると共に、内積計算における乗算回数を削減する。【選択図】図１３
2019204436.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトの特徴を表すオブジェクト特徴ベクトルを複数のクラスタにクラスタリングするクラスタリング装置であって、
前記特徴を識別する特徴識別子毎に、前記クラスタを識別するクラスタ識別子と該クラスタに属するオブジェクト特徴ベクトルの平均を表すｍｅａｎ特徴ベクトルの第１の非零特徴量とを対応付けた組を格納する配列要素で構成された転置ファイルを記憶部に記憶させる記憶手段と、
前記オブジェクト特徴ベクトルの第２の非零特徴量と該第２の非零特徴量の特徴識別子とを対応付けた組で前記オブジェクト特徴ベクトルを表したスパース表現のオブジェクト特徴ベクトルと、各クラスタの前記ｍｅａｎ特徴ベクトルとの距離を計算する計算手段と、
前記計算手段により計算された距離に基づいて前記オブジェクト特徴ベクトルを、前記複数のクラスタのうちの一のクラスタに割り当てる割当手段と、
を有し、
前記計算手段は、
前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量と、前記転置ファイルを構成する配列要素のうち、前記第２の非零特徴量に対応する特徴識別子に基づくインデックスの配列要素に格納されている第１の非零特徴量と積を計算することで、前記距離の計算に必要な内積を計算する、
ことを特徴とするクラスタリング装置。
【請求項２】
前記計算手段は、
前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量と、前記転置ファイルを構成する配列要素のうち、前記第２の非零特徴量に対応する特徴識別子から１を減じた値のインデックスの配列要素に格納されている第１の非零特徴量と積を計算することで、前記距離の計算に必要な内積を計算する、
ことを特徴とする請求項１に記載のクラスタリング装置。
【請求項３】
前記転置ファイルは、
前記特徴識別子毎の配列要素において、前記割当手段による割り当ての前後でクラスタに属するオブジェクト特徴ベクトルに変更あったクラスタを示す変更クラスタに対応するｍｅａｎ特徴ベクトルの第１の非零要素が含まれる組が格納される第１の配列要素が、前記割当手段による割り当ての前後でクラスタに属するオブジェクト特徴ベクトルが不変であったクラスタを示す不変クラスタに対応するｍｅａｎ特徴ベクトルの第１の非零要素が含まれる組が格納される第２の配列要素よりも前に存在し、
前記計算手段は、
前記スパース表現のオブジェクト特徴ベクトルが属するクラスタが不変クラスタであるか否かに応じて、前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量と、前記転置ファイルを構成する配列要素のうち、前記第２の非零特徴量に対応する特徴識別子に基づくインデックスの配列要素又は該配列要素に含まれる前記第１の配列要素のいずれかに格納されている第１の非零特徴量と積を計算することで、前記距離の計算に必要な内積を計算する、ことを特徴とする請求項１又は２に記載のクラスタリング装置。
【請求項４】
前記記憶手段は、
更に、前記割当手段による割り当ての前後でクラスタに属するオブジェクト特徴ベクトルが不変であったクラスタを示す不変クラスタに対応するｍｅａｎ特徴ベクトルの第１の非零要素が含まれる組を前記転置ファイルから除いた変動転置ファイルを前記記憶部に記憶させ、
前記計算手段は、
前記スパース表現のオブジェクト特徴ベクトルが属するクラスタが不変クラスタであるか否かに応じて、前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量と、前記転置ファイル又は前記変動転置ファイルを構成する配列要素のうち、前記第２の非零特徴量に対応する特徴識別子に基づくインデックスの配列要素に格納されている第１の非零特徴量と積を計算することで、前記距離の計算に必要な内積を計算する、ことを特徴とする請求項１又は２に記載のクラスタリング装置。
【請求項５】
前記計算手段は、
前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量と、前記転置ファイルを構成する配列要素のうち、前記第２の非零特徴量に対応する特徴識別子に基づくインデックスの配列要素に格納されている第１の非零特徴量と積を計算する場合に、前記第１の非零特徴量のうち、前記割当手段による割り当ての前後でクラスタに属するオブジェクト特徴ベクトルに変更あったクラスタを示す変更クラスタのクラスタ識別子に対応付けられている第１の非特徴量との積を計算することで、前記距離の計算に必要な内積を計算する、
ことを特徴とする請求項１又は２に記載のクラスタリング装置。
【請求項６】
オブジェクトの特徴を表すオブジェクト特徴ベクトルを複数のクラスタにクラスタリングするクラスタリング装置が、
前記特徴を識別する特徴識別子毎に、前記クラスタを識別するクラスタ識別子と該クラスタに属するオブジェクト特徴ベクトルの平均を表すｍｅａｎ特徴ベクトルの第１の非零特徴量とを対応付けた組を格納する配列要素で構成された転置ファイルを記憶部に記憶させる記憶手順と、
前記オブジェクト特徴ベクトルの第２の非零特徴量と該第２の非零特徴量の特徴識別子とを対応付けた組で前記オブジェクト特徴ベクトルを表したスパース表現のオブジェクト特徴ベクトルと、各クラスタの前記ｍｅａｎ特徴ベクトルとの距離を計算する計算手順と、
前記計算手順により計算された距離に基づいて前記オブジェクト特徴ベクトルを、前記複数のクラスタのうちの一のクラスタに割り当てる割当手順と、
を実行し、
前記計算手順は、
前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量と、前記転置ファイルを構成する配列要素のうち、前記第２の非零特徴量に対応する特徴識別子に基づくインデックスの配列要素に格納されている第１の非零特徴量と積を計算することで、前記距離の計算に必要な内積を計算する、
ことを特徴とするクラスタリング方法。
【請求項７】
コンピュータを、請求項１乃至５の何れか一項に記載のクラスタリング装置における各手段として機能させるためのプログラム。
【請求項８】
オブジェクトの特徴を表すオブジェクト特徴ベクトルを複数のクラスタにクラスタリングするクラスタリング装置が実行するクラスタリング処理の距離計算に用いられる転置ファイルのデータ構造であって、
前記転置ファイルは、
前記特徴を識別する特徴識別子毎に、前記クラスタを識別するクラスタ識別子と該クラスタに属するオブジェクト特徴ベクトルの平均を表すｍｅａｎ特徴ベクトルの第１の非零特徴量とを対応付けた組を格納する配列要素で構成され、
前記クラスタリング装置が、
前記オブジェクト特徴ベクトルの第２の非零特徴量と該第２の非零特徴量の特徴識別子とを対応付けた組で前記オブジェクト特徴ベクトルを表したスパース表現のオブジェクト特徴ベクトルを用いて、前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量と、前記転置ファイルを構成する配列要素のうち、前記第２の非零特徴量に対応する特徴識別子に基づくインデックスの配列要素に格納されている第１の非零特徴量と積を計算することで、前記距離計算に必要な内積を計算する、処理に用いられるデータ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置、クラスタリング方法、プログラム及びデータ構造に関する。
【背景技術】
【０００２】
膨大な量の情報（オブジェクト）をクラスタリングする手法として、ｋ−ｍｅａｎｓ法が知られている。ｋ−ｍｅａｎｓ法は、例えば、オブジェクトの特徴を表すベクトルデータ（以降、「オブジェクト特徴ベクトル」と表す。）をｘｉとして、データ集合Ｘ＝｛ｘ１，ｘ２，・・・，ｘｎ｝と、クラスタ数Ｋとが与えられた場合に、データ集合ＸをＫ個のクラスタに分割する手法である。このｋ−ｍｅａｎｓ法では、クラスタＣｊに属する各ｘｉの平均を表すベクトルμｊ（以降、「ｍｅａｎ特徴ベクトル」と表す。）と、オブジェクト特徴ベクトルｘｉとの距離が最小になるように、各ｘｉが属するクラスタＣｊが決定される。
【０００３】
ｋ−ｍｅａｎｓ法の厳密解を計算するには多くの計算量を要するため、Ｌｌｏｙｄ法と呼ばれる発見的手法がよく用いられる（非特許文献１）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】S. P. Lloyd, Least squares quantization in PCM, IEEE Trans. Inf. Theory, vol. 28, no. 2 (1982), pp. 129-137.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、Ｌｌｏｙｄ法では、各オブジェクト特徴ベクトルｘｉと各ｍｅａｎ特徴ベクトルμｊとの距離を算出するために、これらのベクトルの内積を計算する必要がある。この内積計算では、オブジェクト特徴ベクトルｘｉとｍｅａｎ特徴ベクトルμｊとがどのようなデータ構造で表現されているかによって、必要となるメモリ容量や計算時間等が異なる。
【０００６】
上述したような膨大な量のオブジェクトをクラスタリングする問題においては、オブジェクト特徴ベクトルは疎（スパース）なデータになることが多く、結果として大規模な疎データのクラスタリングを行うことになる場合が多い。これに対して、上記の非特許文献１等の従来技術では、Ｌｌｏｙｄ法を疎データのクラスタリングに適用した場合に、内積計算に必要なメモリ容量や計算時間等の効率化を図ることができなかった。
【０００７】
本発明の実施の形態は、上記の点に鑑みてなされたもので、疎データを効率的にクラスタリングすることを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明の実施の形態では、オブジェクトの特徴を表すオブジェクト特徴ベクトルを複数のクラスタにクラスタリングするクラスタリング装置であって、前記特徴を識別する特徴識別子毎に、前記クラスタを識別するクラスタ識別子と該クラスタに属するオブジェクト特徴ベクトルの平均を表すｍｅａｎ特徴ベクトルの第１の非零特徴量とを対応付けた組を格納する配列要素で構成された転置ファイルを記憶部に記憶させる記憶手段と、前記オブジェクト特徴ベクトルの第２の非零特徴量と該第２の非零特徴量の特徴識別子とを対応付けた組で前記オブジェクト特徴ベクトルを表したスパース表現のオブジェクト特徴ベクトルと、各クラスタの前記ｍｅａｎ特徴ベクトルとの距離を計算する計算手段と、前記計算手段により計算された距離に基づいて前記オブジェクト特徴ベクトルを、前記複数のクラスタのうちの一のクラスタに割り当てる割当手段と、を有し、前記計算手段は、前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量と、前記転置ファイルを構成する配列要素のうち、前記第２の非零特徴量に対応する特徴識別子に基づくインデックスの配列要素に格納されている第１の非零特徴量と積を計算することで、前記距離の計算に必要な内積を計算する、ことを特徴とする。
【発明の効果】
【０００９】
本発明の実施の形態によれば、疎データを効率的にクラスタリングすることができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態におけるクラスタリング装置の機能構成の一例を示す図である。
【図２】本発明の実施の形態におけるクラスタリング装置のハードウェア構成の一例を示す図である。
【図３】本発明の実施の形態における前処理の一例を示すフローチャートである。
【図４】スパース表現のオブジェクト特徴ベクトルの一例を示す図である。
【図５】本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例１）である。
【図６】完全表現のｍｅａｎ特徴ベクトルの一例を示す図である。
【図７】Ｋ個の完全表現のｍｅａｎ特徴ベクトルの一例を示す図である。
【図８】スパース表現のオブジェクト特徴ベクトルと、完全表現のｍｅａｎ特徴ベクトルとの内積計算の一例を示す図（実施例１）である。
【図９】スパース表現のオブジェクト特徴ベクトルと、Ｋ個の完全表現のｍｅａｎ特徴ベクトルとの内積計算の一例を示す図（実施例１）である。
【図１０】本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例２）である。
【図１１】スパース表現のｍｅａｎ特徴ベクトルの一例を示す図である。
【図１２】本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例３）である。
【図１３】ｍｅａｎ転置ファイルの一例を示す図である。
【図１４】スパース表現のオブジェクト特徴ベクトルと、転置ファイル表現のｍｅａｎ特徴ベクトルとの内積計算の一例を示す図（実施例３）である。
【図１５】本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例４）である。
【図１６】本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例５）である。
【図１７】本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例６）である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。本発明の実施の形態では、疎データを効率的にクラスタリングすることが可能なクラスタリング装置１０について説明する。
【００１２】
＜準備＞
まず、本発明の実施の形態の準備として、クラスタリングの対象となるデータとＬｌｏｙｄ法とについて説明する。
【００１３】
（１）クラスタリングの対象となるデータ
本発明の実施の形態では、大規模な疎データをクラスタリングの対象とする。このようなデータの一例としては、文書をオブジェクトとして、大量の文書をクラスタリングする場合に、文書の特徴を表すオブジェクト特徴ベクトル等が挙げられる。
【００１４】
オブジェクトが文書である場合は、ｂａｇ−ｏｆ−ｗｏｒｄｓモデル（以降、「ＢｏＷ」と表す。）を用いて、オブジェクトを特徴空間であるユークリッド空間における点として扱うことがよく行われている。なお、文書はテキストやドキュメント等とも称されるが、これらを総称して「文書」と表す。
【００１５】
ＢｏＷでは、文書をその中に出現する単語（word）に代表される一塊の文字列に分割し、各々の単語を文書の特徴の１つとする。そして、特徴に対応する或る量を特徴量として、文書をこれらの特徴量を要素するベクトルで表現する。なお、単語は語彙（vocabulary）やターム（term）等とも称されるが、以降では、単語、語彙及びタームを総称して、「単語」と表す。
【００１６】
ここで、特徴量は、文書中に或る単語が出現する頻度（term frequency）と、オブジェクト集合（文書集合）の各文書に当該単語が出現する頻度（document frequency）とを入力変数とする関数の値で表される。当該関数としては、例えば、ｔｆ−ｉｄｆ（term-frequency-inverse document frequency）であることが多く、一般的な関数は以下である。
【００１７】
ｔｆ（ｔｈ，ｘｉ；Ｘ）：Ｘが与えられた場合に、ｘｉに出現するｔｈの頻度
ｄｆ（ｔｈ，Ｘ）：Ｘが与えられた場合に、ｔｈを含む文書（オブジェクト）の数ｎｈ
ｉｄｆ（ｔｈ；Ｘ）＝ｌｏｇ（ｎ／ｎｈ）
ｔｆ−ｉｄｆ（ｔｈ，ｘｉ；Ｘ）＝ｔｆ（ｔｈ，ｘｉ；Ｘ）×ｉｄｆ（ｔｈ；Ｘ）
ここで、Ｘはオブジェクト集合（文書集合）に対応するオブジェクト特徴ベクトル集合Ｘ＝｛ｘ１，ｘ２，・・・，ｘｎ｝であり、ｘｉ（ｉ＝１，２，・・・，ｎ）はオブジェクト特徴ベクトルである。また、オブジェクト数｜Ｘ｜は｜Ｘ｜＝ｎであり、ｎｈは単語ｔｈを含む文書の数である。なお、ｉｄｆを表す関数のｌｏｇの底は限定されない。
【００１８】
この場合、特徴空間の次元数は、文書集合に含まれる全文書の異なり単語数であり、非常に大きくなる。すなわち、特徴空間は高次元空間となる。
【００１９】
一方で、或るオブジェクト（文書）に出現する単語数が限られているため、オブジェクト特徴ベクトルｘｉは、疎（スパース）なベクトルとなる。すなわち、オブジェクト特徴ベクトルｘｉは、非零要素の数が非常に少ないベクトルとなる。
【００２０】
このように、大量の文書をクラスタリングする場合、クラスタリング対象のデータ（オブジェクト特徴ベクトル）集合は大規模な集合となり、かつ、各オブジェクト特徴ベクトルは高次元で疎なベクトルとなる。以降では、このような高次元かつ疎なデータを「高次元疎データ」、これらの高次元疎データの大規模な集合を「大規模高次元疎データ集合」とも表す。本発明の実施の形態では、このような大規模高次元疎データ集合をクラスタリングの対象とする。
【００２１】
なお、上記以外にも、例えば、購入者（又はユーザ）と購入品（又はアイテム）との関係を表す購買履歴、抽出される特徴がｂａｇ−ｏｆ−ｖｉｓｕａｌ  ｗｏｒｄｓで表される画像等もオブジェクトとして、上記の文書と同様に扱うことができる。すなわち、大量の購買履歴の特徴ベクトルやｂａｇ−ｏｆ−ｖｉｓｕａｌ  ｗｏｒｄｓで表される大量の画像の特徴ベクトル等も大規模高次元疎データ集合となる。
【００２２】
（２）Ｌｌｏｙｄ法
Ｌｌｏｙｄ法の概略は以下の通りである。なお、Ｋは、与えられたクラスタ数である。
【００２３】
Ｓ１：（初期状態設定ステップ）：Ｋ個のｍｅａｎ特徴ベクトルμｊ（ｊ＝１，２，・・・，Ｋ）を適当な値に初期化する。
【００２４】
Ｓ２：（割当ステップ）オブジェクト特徴ベクトルｘｉの各々について、現在のイテレーションのｍｅａｎ特徴ベクトルμｊと、当該オブジェクト特徴ベクトルｘｉとの距離（又はその二乗）を計算し、最も距離が近いｍｅａｎ特徴ベクトルμｊに対応するクラスタＣｊに当該オブジェクト特徴ベクトルｘｉを割り当てる。なお、イテレーションとは、後述するように、Ｓ２及びＳ３の繰り返し回数（又は反復回数）のことである。
【００２５】
ｍｅａｎ特徴ベクトルμｊとオブジェクト特徴ベクトルｘｉとの距離は、例えば、以下の式（１）により計算される。
【００２６】
【数１】
2019204436.tif 000003
ここで、Ｔは転置を表す。上記式（１）の右辺における第１項及び第２項はそれぞれｘｉ及びμｊのノルムの二乗であり、第３項のｘｉＴμｊは内積（dot product又はinner-product）を表す。
【００２７】
Ｓ３：（更新ステップ）全てのオブジェクト特徴ベクトルｘｉの割り当てが終了した後、各クラスタＣｊに属するオブジェクト特徴ベクトルｘｉによりｍｅａｎ特徴ベクトルμｊを計算及び更新する。
【００２８】
Ｓ４：（終了判定ステップ）所定の終了条件を満たすか否かを判定し、所定の終了条件を満たすと判定された場合は処理を終了する一方で、所定の終了条件を満たさないと判定された場合は上記のＳ２の割当ステップに戻る。これにより、所定の終了条件を満たすまで、Ｓ２及びＳ３が繰り返し実行される。この繰り返しはイテレーションとも称され、現在実行中の繰り返しを「現在のイテレーション」、現在のイテレーションの１つ前に実行した繰り返しを「１つ前のイテレーション」と表す。なお、所定の終了条件としては、例えば、全てのオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変になった場合等が挙げられる。
【００２９】
ここで、Ｌｌｏｙｄ法は、上記のＳ２の割当ステップに多くの時間計算量を要する。このため、Ｌｌｏｙｄ法の高速化を図るためには、割当ステップに要する時間、すなわち、全てのオブジェクト特徴ベクトルｘｉと全てのｍｅａｎ特徴ベクトルμｊとの距離計算に要する時間を低減することが必要となる。上述したように、距離計算では、ｘｉ及びμｊのノルムの二乗と、ｘｉＴμｊの内積とを計算する必要がある。ノルムの二乗は予め計算することが可能であるため、距離計算に要する時間を低減するためには、内積計算に要する時間を低減することが重要となる。
【００３０】
そこで、本発明の実施の形態では、少なくともオブジェクト特徴ベクトルｘｉを所定のデータ構造で表現することにより、内積計算に要する時間を低減する方法について説明する。また、本発明の実施の形態では、少なくともオブジェクト特徴ベクトルｘｉを所定のデータ構造で表現することにより、内積計算に必要なメモリ容量を削減する方法についても説明する。これらの方法により、本発明の実施の形態におけるクラスタリング装置１０は、大規模高次元疎データ集合を効率的にクラスタリングすることが可能となる。
【００３１】
＜機能構成＞
次に、本発明の実施の形態におけるクラスタリング装置１０の機能構成について、図１を参照しながら説明する。図１は、本発明の実施の形態におけるクラスタリング装置１０の機能構成の一例を示す図である。
【００３２】
図１に示すように、本発明の実施の形態におけるクラスタリング装置１０は、前処理部１１０と、クラスタリング処理部１２０とを有する。前処理部１１０とクラスタリング処理部１２０とは、クラスタリング装置１０にインストールされた１以上のプログラムがＣＰＵ（Central Processing Unit）に実行させる処理により実現される。なお、前処理部１１０とクラスタリング処理部１２０とは、異なるプログラムがＣＰＵに実行させる処理により実現されていても良い。
【００３３】
また、本発明の実施の形態におけるクラスタリング装置１０は、記憶部１３０を有する。記憶部１３０は、例えば、補助記憶装置やＲＡＭ（Random Access Memory）等を用いて実現可能である。
【００３４】
前処理部１１０は、入力されたオブジェクト特徴ベクトル集合Ｘ＝｛ｘ１，ｘ２，・・・，ｘｎ｝の各オブジェクト特徴ベクトルｘｉを、非零要素の位置（例えば、オブジェクトが文書の場合は異なり単語の各々を一意に識別する特徴ＩＤ（又は特徴識別子））と、非零要素の値（例えば、オブジェクトが文書の場合はｔｆ−ｉｄｆ値で表される特徴量）との組（タプル）の列で構成したデータ構造で表現する。なお、入力されたオブジェクト特徴ベクトル集合Ｘが大規模高次元疎データ集合である。
【００３５】
上記のデータ構造で表現されたオブジェクト特徴ベクトルを「スパース表現のオブジェクト特徴ベクトル」と表す。一方で、スパース表現ではなく、オブジェクト特徴ベクトル集合Ｘに出現する全ての特徴ＩＤを次元とするオブジェクト特徴ベクトル（すなわち、高次元であるオブジェクト特徴ベクトル）を「完全表現のオブジェクト特徴ベクトル」と表す。以降では、スパース表現のオブジェクト特徴ベクトルもｘｉ（ｉ＝１，２，・・・，ｎ）と表す。スパース表現のオブジェクト特徴ベクトルｘｉの集合Ｘは、例えば、記憶部１３０に格納される。
【００３６】
クラスタリング処理部１２０は、スパース表現のオブジェクト特徴ベクトルｘｉの集合Ｘと、クラスタ数Ｋとを入力として、スパース表現のオブジェクト特徴ベクトルｘｉをＫ個のクラスタにクラスタリング（又は分割）する。ここで、クラスタリング処理部１２０には、入力部１２１と、初期設定部１２２と、割当部１２３と、更新部１２４と、終了判定部１２５と、出力部１２６とが含まれる。
【００３７】
入力部１２１は、スパース表現のオブジェクト特徴ベクトルｘｉの集合Ｘと、クラスタ数Ｋとを入力する。なお、入力部１２１は、例えば、記憶部１３０から集合Ｘ及びクラスタ数Ｋを入力する。ただし、入力部１２１は、例えば、他の装置や他のプログラム等から出力された集合Ｘやクラスタ数Ｋを入力しても良い。
【００３８】
初期設定部１２２は、上述した初期状態設定ステップに相当する処理を行う。割当部１２３は、上述した割当ステップに相当する処理を行う。更新部１２４は、上述した更新ステップに相当する処理を行う。終了判定部１２５は、上述した終了判定ステップに相当する処理を行う。
【００３９】
出力部１２６は、例えば、スパース表現のオブジェクト特徴ベクトルｘｉのクラスタＣｊへの割当結果（これは、オブジェクトのクラスタリング結果と同一視できる。）を出力する。なお、出力部１２６は、各クラスタＣｊのｍｅａｎ特徴ベクトルμｊを出力しても良い。また、出力部１２６による出力先は、限定されない。出力先の具体例としては、例えば、ディスプレイ、補助記憶装置、外部記録媒体、ネットワークを介して接続される他の装置等が挙げられる。
【００４０】
なお、図１では、一例として、クラスタリング装置１０が前処理部１１０を有している場合を示したが、これに限られない。例えば、クラスタリング装置１０が前処理部１１０を有さずに、他の装置が前処理部１１０を有していても良い。この場合、クラスタリング装置１０のクラスタリング処理部１２０は、当該他の装置の前処理部１１０によって作成されたスパース表現のオブジェクトベクトルｘｉの集合Ｘを入力すれば良い。
【００４１】
＜ハードウェア構成＞
次に、本発明の実施の形態におけるクラスタリング装置１０のハードウェア構成について、図２を参照しながら説明する。図２は、本発明の実施の形態におけるクラスタリング装置１０のハードウェア構成の一例を示す図である。
【００４２】
図２に示すように、本発明の実施の形態におけるクラスタリング装置１０は、入力装置２０１と、表示装置２０２と、外部Ｉ／Ｆ２０３と、ＲＡＭ２０４と、ＲＯＭ（Read Only Memory）２０５と、ＣＰＵ２０６と、通信Ｉ／Ｆ２０７と、補助記憶装置２０８とを有する。これら各ハードウェアは、それぞれがバス２０９を介して通信可能に接続されている。
【００４３】
入力装置２０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種装置を入力するのに用いられる。表示装置２０２は、例えばディスプレイ等であり、クラスタリング装置１０の処理結果等を表示する。なお、クラスタリング装置１０は、入力装置２０１及び表示装置２０２のうちの少なくとも一方を有していなくても良い。
【００４４】
外部Ｉ／Ｆ２０３は、外部装置とのインタフェースである。外部装置には、記録媒体２０３ａ等がある。クラスタリング装置１０は、外部Ｉ／Ｆ２０３を介して、記録媒体２０３ａの読み取りや書き込み等を行うことができる。記録媒体２０３ａには、例えば、本発明の実施の形態におけるクラスタリング装置１０が有する各機能部を実現する１以上のプログラムが格納されていても良い。
【００４５】
記録媒体２０３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【００４６】
ＲＡＭ２０４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ２０５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ２０５には、例えば、ＯＳ（Operating System）設定やネットワーク設定等が格納されている。ＣＰＵ２０６は、ＲＯＭ２０５や補助記憶装置２０８等からプログラムやデータをＲＡＭ２０４上に読み出して処理を実行する演算装置である。
【００４７】
通信Ｉ／Ｆ２０７は、クラスタリング装置１０が他の装置と通信を行うためのインタフェースである。本発明の実施の形態におけるクラスタリング装置１０が有する各機能部を実現する１以上のプログラムは、例えば、通信Ｉ／Ｆ２０７を介して、所定のサーバ等から取得（ダウンロード）されても良い。また、本発明の実施の形態におけるクラスタリング装置１０は、例えば、通信Ｉ／Ｆ２０７を介して、これらの各機能部を実現する１以上のプログラムを他の装置に提供しても良い。
【００４８】
補助記憶装置２０８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置２０８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上で各種機能を実現するアプリケーションプログラム、本発明の実施の形態におけるクラスタリング装置１０が有する各機能部を実現する１以上のプログラム等がある。
【００４９】
本発明の実施の形態におけるクラスタリング装置１０は、図２に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。
【００５０】
＜前処理＞
まず、完全表現のオブジェクト特徴ベクトルｘｉを、スパース表現のオブジェクト特徴ベクトルｘｉに変換する前処理について、図３を参照しながら説明する。図３は、本発明の実施の形態における前処理の一例を示すフローチャートである。
【００５１】
ステップＳ１０１：まず、前処理部１１０は、完全表現のオブジェクト特徴ベクトルｘｉの集合Ｘ＝｛ｘ１，ｘ２，・・・，ｘｎ｝を入力する。なお、オブジェクト特徴ベクトル集合Ｘは、大規模高次元疎データ集合である。
【００５２】
ステップＳ１０２：次に、前処理部１１０は、完全表現の各オブジェクト特徴ベクトルｘｉをスパース表現に変換する。ただし、入力データが予めスパース表現されている場合は、この変換を行うことなく、当該スパース表現を利用する。
【００５３】
ここで、スパース表現のオブジェクト特徴ベクトルｘｉの一例について、図４を参照しながら説明する。図４は、スパース表現のオブジェクト特徴ベクトルｘｉの一例を示す図である。
【００５４】
図４に示すように、スパース表現のオブジェクト特徴ベクトルｘｉは、非零要素の位置を示す特徴ＩＤと、非零要素の値を示す特徴量との組（タプル）の列で構成される。図４では、完全表現のオブジェクト特徴ベクトルｘｉの非零要素がｍ個である場合に、ｈ＝１，２，・・・，ｍとして、これらの非零要素の特徴ＩＤ「ｔｈ」と、当該特徴ＩＤの特徴量「ｖｈ」との組（タプル）の列で構成されたスパース表現を表している。なお、各特徴ＩＤ「ｔｈ」及び特徴量「ｖｈ」は、オブジェクト特徴ベクトルｘｉのインデックスｉに依存するため、正確にはそれぞれ「ｔｉｈ」及び「ｖｉｈ」と表されるが、本発明の実施の形態では、特に断らない限り、「ｔｈ」及び「ｖｈ」とインデックスｉを省略して表す。
【００５５】
ここで、特徴ＩＤは、例えば、１≦ｔ１＜ｔ２＜・・・＜ｔｈ＜・・・＜ｔｍ≦Ｄのように昇順にソートされていることが好ましい。Ｄは、各オブジェクト特徴ベクトルｘｉが存在する特徴空間の次元数（すなわち、例えば、オブジェクトが文書である場合、文書集合に含まれる異なり単語数）である。このようにソートされていることで、後述する内積計算の計算量を小さくすることができる。以降では、スパース表現のオブジェクト特徴ベクトルｘｉの各特徴ＩＤは、上述のように昇順にソートされているものとする。
【００５６】
スパース表現のオブジェクト特徴ベクトルｘｉを用いることで、スパース表現のオブジェクト特徴ベクトルｘｉの集合Ｘが使用するメモリサイズ（すなわち、記憶部１３０の記憶容量）を抑制することができる。例えば、オブジェクト数をｎ、各オブジェクト特徴ベクトルｘｉが存在する特徴空間の次元数をＤ、オブジェクト特徴ベクトルｘｉの疎性（スパーシティ：sparsity）をＳｘ（ｉ）、（０≦Ｓｘ（ｉ）≦１）、オブジェクト特徴ベクトルｘｉの要素番号を整数で表現（すなわち、整数型ｉｎｔサイズメモリ容量を使用して表現）し、特徴量を倍精度浮動小数点で表現（すなわち、倍精度浮動小数点型ｄｏｕｂｌｅサイズのメモリ容量を使用して表現）する場合、完全表現とスパース表現とのメモリ使用量は以下の通りである。
【００５７】
【数２】
2019204436.tif 000004
ここで、ｓｉｚｅｏｆは引数として渡された型のメモリサイズを返す関数である。
【００５８】
具体的には、計算機システムに依存するが、一例として、ｓｉｚｅｏｆ（ｉｎｔ）＝４  ｂｙｔｅｓ、ｓｉｚｅｏｆ（ｄｏｕｂｌｅ）＝８  ｂｙｔｅｓであり、全オブジェクト特徴ベクトルｘｉの平均疎性Ｓｘが
【００５９】
【数３】
2019204436.tif 000005
である場合、完全表現のメモリ使用量は８×ｎ×Ｄ  ｂｙｔｅｓであり、スパース表現のメモリ使用量は１．２×ｎ×Ｄ  ｂｙｔｅｓである。ただし、タプルの要素を各々１つの配列に保持する。
【００６０】
このため、各オブジェクト特徴ベクトルｘｉをスパース表現とすることで、メモリ使用量を約１／７に抑制することができる。
【００６１】
なお、完全表現の場合は、オブジェクト特徴ベクトルｘｉの各要素を格納する配列のインデックスと、オブジェクトを一意に識別する識別子（この識別子は、「オブジェクトＩＤ」とも称される。）とが一致しているものと仮定している。すなわち、オブジェクトＩＤ「ｋ」のオブジェクトに対応するオブジェクト特徴ベクトルｘｋの各要素（特徴量）は、要素数がＤ個であるｋ番目の配列（具体的には、配列ｖｋ［ｄ］，０≦ｄ≦Ｄ−１）に格納されているものと仮定している。また、オブジェクト特徴ベクトルｘｉの疎性Ｓｘ（ｉ）は、Ｓｘ（ｉ）＝１．０−（ｎｎｚｉ）／Ｄで定義される。ここで、ｎｎｚｉは、オブジェクト特徴ベクトルｘｉの非零要素の数（the number of non-zero elements）である。
【００６２】
例えば、大量の文書がオブジェクトである場合、平均疎性Ｓｘは非常に大きくなることが一般的であり、０．９９を超えることもある。例えば、文書数が１００万、異なり単語数が５０万であって、１つの文書中に平均２００単語程度が出現する場合、平均疎性Ｓｘ＝１−２００／５×１０６＝０，９９９９５である。このときのメモリ使用量は６×１０−４×ｎ×Ｄ  ｂｙｔｅｓである。このように、スパース表現を用いることで、メモリを効率的に使用することができる。特に、大規模高次元疎データをクラスタリングの対象とする場合、ｎ及びＤが共に非常に大きいため、完全表現の各オブジェクト特徴ベクトルｘｉをスパース表現にすることは空間計算量に相当するメモリの効率的利用の観点から特に効果的である。
【００６３】
ステップＳ１０３：次に、前処理部１１０は、上記のステップＳ１０２でスパース表現に変換された各オブジェクト特徴ベクトルｘｉを記憶部１３０に格納する。
【００６４】
以上のように、本発明の実施の形態におけるクラスタリング装置１０は、前処理として、スパース表現のオブジェクト特徴ベクトルｘｉを作成する。これにより、上述したように、オブジェクト特徴ベクトルｘｉに必要なメモリ使用量（すなわち、記憶部１３０の記憶容量）を抑制することができる。
【００６５】
なお、本発明の実施の形態では、クラスタリング装置１０が前処理として完全表現の各オブジェクト特徴ベクトルｘｉをスパース表現に変換、又はスパース表現のオブジェクト特徴ベクトルｘｉを作成したが、これに限られない。例えば、クラスタリング装置１０とは異なる他の装置が上記のステップＳ１０１及びステップＳ１０２を行った上で、クラスタリング装置１０は、上記のステップＳ１０３のみを行っても良い。
【００６６】
＜クラスタリング処理＞
以降では、本発明の実施の形態におけるクラスタリング処理について説明する。
【００６７】
（実施例１）
まず、クラスタリング処理の実施例１として、スパース表現のオブジェクト特徴ベクトルｘｉをクラスタリングする場合について、図５を参照しながら説明する。図５は、本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例１）である。
【００６８】
ステップＳ２０１：まず、クラスタリング処理部１２０の入力部１２１は、スパース表現のオブジェクト特徴ベクトルｘｉの集合Ｘと、クラスタ数Ｋとを入力する。なお、｜Ｘ｜＝ｎ、Ｋは整数かつ１＜Ｋ＜ｎであるものとする。
【００６９】
ステップＳ２０２：次に、クラスタリング処理部１２０の初期設定部１２２は、各ｍｅａｎ特徴ベクトルμｊ（ｊ＝１，２，・・・，Ｋ）を適当な値に初期化する。初期化の方法としては、任意の方法を用いて良い。例えば、各ｍｅａｎ特徴ベクトルμｊをランダムな値に初期化しても良いし、互いに異なる任意のＫ個のオブジェクト特徴ベクトルｘｉをそれぞれｍｅａｎ特徴ベクトルμｊとしても良いし、スパース表現の各オブジェクト特徴ベクトルｘｉをランダムにクラスタＣｊに割り当てた上で、各クラスタＣｊに属するｘｉからｍｅａｎ特徴ベクトルμｊを計算することで初期化しても良い。なお、初期化されたｍｅａｎ特徴ベクトルμｊは、例えば、記憶部１３０に格納される。
【００７０】
ここで、実施例１では、各ｍｅａｎ特徴ベクトルμｊは完全表現であるものとする。完全表現のｍｅａｎ特徴ベクトルμｊの一例について、図６を参照しながら説明する。図６は、完全表現のｍｅａｎ特徴ベクトルμｊの一例を示す図である。
【００７１】
図６に示すように、完全表現のｍｅａｎ特徴ベクトルμｊは、特徴量が零である要素ｕｄ（ｄ＝１，２，・・・，Ｄ）も含めて、Ｄ次元のベクトルで表現されたデータ（高次元データ）である。
【００７２】
完全表現のｍｅａｎ特徴ベクトルμｊでは、配列のｄ番目の要素（すなわち、配列インデックスがｄである配列の要素）に、特徴ＩＤがｄ＋１である特徴量ｕｄ＋１が格納されているものとする。以降では、ベクトルの要素と区別するため、配列の要素を「配列要素」と表す。
【００７３】
具体的には、例えば、完全表現のｍｅａｎ特徴ベクトルμｊを配列ｗｊ［ｄ］、０≦ｄ≦Ｄ−１で実現する場合、ｄ´番目の配列要素ｗｊ［ｄ´］には、特徴ＩＤがｄ´＋１の特徴量ｕｄ´＋１が格納されている。なお、各特徴量「ｕｄ」は、ｍｅａｎ特徴ベクトルμｊのインデックスｊに依存するため、正確には「ｕｊｄ」と表されるが、本発明の実施の形態では、特に断らない限り、「ｕｄ」とインデックスｊを省略して表す。
【００７４】
ここで、Ｋ個の完全表現のｍｅａｎ特徴ベクトルμｊ（ｊ＝１，２，・・・，Ｋ）はＫ×Ｄの行列Ａで表現することもできる。Ｋ個の完全表現のｍｅａｎ特徴ベクトルμｊをＫ×Ｄの行列Ａで表現した場合の一例を図７に示す。図７に示すように、行列Ａは、ｊ行目を完全表現のｍｅａｎ特徴ベクトルμｊとする行列である。
【００７５】
完全表現のｍｅａｎ特徴ベクトルμｊは、特徴量が零である要素も配列に格納されるためメモリ使用量は大きいものの、後述する内積計算で簡便な計算方法が適用することができ、時間計算量の増大を抑制することができる。なお、この計算方法は、以下の参考文献１に記載されているＳｐａｒｓｅ  ＢＬＡＳ（Basic Linear Algebra Subprograms）  Ｌｉｂｒａｒｙのｌｅｖｅｌ１のｄｏｔ  ｐｒｏｄｕｃｔの表現と同一であり、Ｓｐａｒｓｅ  ＢＬＡＳのｄｏｔ  ｐｒｏｄｕｃｔの疎表現の引数をオブジェクト特徴ベクトルｘｉとし、完全表現の引数としてｍｅａｎ特徴ベクトルμｊを用いた場合に相当する。
【００７６】
［参考文献１］
D. S. Dodson, R. G. Grimes, and J. G. Lewis, "Sparse extensions to the FORTRAN Basic Linear Algebra Subprograms," ACM Trans. Mathematical Software, vol. 17, no. 2, pp. 253-263, June 1991.
以降のステップＳ２０３〜ステップＳ２０６は、クラスタリング処理部１２０により所定の終了条件を満たすまで繰り返し実行される。
【００７７】
ステップＳ２０３：クラスタリング処理部１２０の割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉの各々について、現在のイテレーションの完全表現のｍｅａｎ特徴ベクトルμｊとの距離を計算する。ここで、距離の定義は上記の式（１）の通りである。上述したように、ノルムの二乗は予め計算することが可能であるため、以降では、内積計算について説明する。
【００７８】
従来法では、オブジェクト特徴ベクトルｘｉが完全表現（すなわち、零要素も含めた、Ｄ次元のベクトル）であるため、内積計算において、オブジェクト特徴ベクトルｘｉと、ｍｅａｎ特徴ベクトルμｊとの同一インデックス（同一の要素インデックス）の要素同士の乗算値を求めている。すなわち、オブジェクト特徴ベクトルｘｉの要素インデックスと、ｍｅａｎ特徴ベクトルμｊの要素インデックスとが一致している。一方で、実施例１では、オブジェクト特徴ベクトルｘｉが非零要素を含まない形に圧縮表現（スパース表現）されているため、スパース表現のオブジェクト特徴ベクトルｘｉの要素インデックスと、完全表現のｍｅａｎ特徴ベクトルμｊの要素インデックスとは一致しない。しかしながら、図６に示すように、完全表現のｍｅａｎ特徴ベクトルμｊの配列インデックスと特徴ＩＤとの対応関係が固定されている（図６に示す例では、特徴ＩＤから１を減じた値が配列インデックスとなる。）。このため、スパース表現のオブジェクト特徴ベクトルｘｉの特徴ＩＤの値から、乗算対象となるｍｅａｎ特徴ベクトルμｊの要素インデックスを一意に特定することができる。
【００７９】
そこで、実施例１では、次のようにして内積を計算する。以降では、一例として、図８に示すスパース表現のオブジェクト特徴ベクトルｘｉと、完全表現のｍｅａｎ特徴ベクトルμｊとの内積を計算する場合について説明する。
【００８０】
ステップＳ２０３−１：割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉの特徴量ｖｈに対応する特徴ＩＤ「ｔｈ」を用いて、完全表現のｍｅａｎ特徴ベクトルμｊのｔｈ−１番目の配列要素にアクセスする。
【００８１】
ステップＳ２０３−２：割当部１２３は、上記のステップＳ２０３−１でアクセスした配列要素に格納されている特徴量ｕｔｈが零であるか否かを判定する。
【００８２】
ステップＳ２０３−３：特徴量ｕｔｈが零でないと判定した場合、割当部１２３は、特徴量ｕｔｈと特徴量ｖｈとの乗算を計算する。一方で、特徴量ｕｔｈが零であると判定した場合、割当部１２３は、何もしない。
【００８３】
割当部１２３は、各ｈ＝１，２，・・・，ｍに対して、上記のステップＳ２０３−１〜ステップＳ２０３−３を繰り返し実行する。
【００８４】
ステップＳ２０３−４：割当部１２３は、上記のステップＳ２０３−３で各ｈに対して計算された乗算結果を加算する。これにより、スパース表現のオブジェクト特徴ベクトルｘｉと、完全表現のｍｅａｎ特徴ベクトルμｊとの内積が計算される。
【００８５】
以上のステップＳ２０３−１〜ステップＳ２０３−４で説明した内積計算により、実施例１では、内積計算における乗算回数を削減することができ、内積計算を効率的に行うことができるようになる。例えば、図８に示す例では、完全表現のｍｅａｎ特徴ベクトルμｊの配列要素にアクセスする回数はｍ回（スパース表現のオブジェクト特徴ベクトルｘｉの要素数）であり、乗算回数は、完全表現のｍｅａｎ特徴ベクトルμｊのアクセスされた要素のうちの非零の要素数α（≦ｍ）となる。
【００８６】
なお、ＣＰＵのアーキテクチャ等によっては、上記のステップＳ２０３−２で特徴量ｕｔｈが零であるか否かを判定するよりも乗算処理を行った方が、計算速度が速い場合もある。このような場合、割当部１２３は、上記のステップＳ２０３−２の判定を行わずに（すなわち、特徴量ｕｔｈが零であるか否かに関わらずに）、上記のステップＳ２０３−３で特徴量ｕｔｈと特徴量ｖｈとの乗算を計算すれば良い。
【００８７】
以上で説明した内積計算は、スパース表現のオブジェクト特徴ベクトルｘｉの各々について、Ｋ個の完全表現のｍｅａｎ特徴ベクトルμｊを対象として行われる。或る１つのスパース表現のオブジェクト特徴ベクトルｘｉと、Ｋ個の完全表現のｍｅａｎ特徴ベクトルμｊとの内積計算を図９に示す。図９に示すように、ｊ＝１，２，・・・，Ｋに対して、スパース表現のオブジェクト特徴ベクトルｘｉと、完全表現の各ｍｅａｎ特徴ベクトルμｊとの内積を繰り返し計算する。このとき、Ｋ個の完全表現のｍｅａｎ特徴ベクトルμｊの配列要素にアクセスする回数はｍ×Ｋ回であり、乗算回数は、
【００８８】
【数４】
2019204436.tif 000006
となる。ここで、αｊ（ｍ）は、完全表現のｍｅａｎ特徴ベクトルμｊのアクセスされた要素のうちの非零の要素数である。言い換えれば、αｊ（ｍ）は、集合｛ｔ１，・・・，ｔｍ｝と、完全表現のｍｅａｎ特徴ベクトルμｊの特徴ＩＤの集合｛１，・・・，Ｄ｝との共通集合の要素のうち、ｍｅａｎ特徴ベクトルμｊの特徴量が非零の要素数である。
【００８９】
ステップＳ２０４：クラスタリング処理部１２０の割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉの各々について、上記のステップＳ２０３で計算した距離が最小である完全表現のｍｅａｎ特徴ベクトルμｊに対応するクラスタＣｊに当該オブジェクト特徴ベクトルｘｉを割り当てる。なお、スパース表現の各オブジェクト特徴ベクトルｘｉのクラスタＣｊへの割当結果は、例えば、記憶部１３０に格納される。
【００９０】
ステップＳ２０５：クラスタリング処理部１２０の更新部１２４は、各クラスタＣｊに属するスパース表現のオブジェクト特徴ベクトルｘｉにより、完全表現のｍｅａｎ特徴ベクトルμｊを計算及び更新する。
【００９１】
例えば、更新部１２４は、クラスタＣｊの各々について、当該クラスタＣｊに属するスパース表現のオブジェクト特徴ベクトルｘｉの平均を計算し、この平均をｍｅａｎ特徴ベクトルμｊとすれば良い。ここで、スパース表現のオブジェクト特徴ベクトルｘｉの平均とは、同一のクラスタＣｊに属するスパース表現のオブジェクト特徴ベクトルｘｉについての特徴ＩＤ毎の特徴量の平均値のことである。なお、ｍｅａｎ特徴ベクトルμｊの要素のうち、平均値が算出されなかった特徴ＩＤに対応する要素の特徴量は零とすれば良い。
【００９２】
ステップＳ２０６：クラスタリング処理部１２０の終了判定部１２５は、所定の終了条件を満たすか否かを判定する。そして、所定の終了条件を満たすと判定した場合、クラスタリング処理部１２０は、ステップＳ２０７に進む。一方で、所定の終了条件を満たさないと判定された場合、クラスタリング処理部１２０は、イテレーションに１を加算した上で、ステップＳ２０３に戻る。
【００９３】
ステップＳ２０７：クラスタリング処理部１２０の出力部１２６は、例えば、スパース表現のオブジェクト特徴ベクトルｘｉのクラスタＣｊへの割当結果等を出力する。
【００９４】
以上のように、本発明の実施の形態におけるクラスタリング装置１０は、実施例１のクラスタリング処理により、スパース表現のオブジェクト特徴ベクトルｘｉをクラスタリングすることができる。このとき、上述したように、オブジェクト特徴ベクトルｘｉをスパース表現にすることで、メモリ使用量を抑制することができると共に、内積計算における乗算回数を削減することができるため、効率的なクラスタリングが可能となる。
【００９５】
（実施例２）
次に、クラスタリング処理の実施例２として、ｍｅａｎ特徴ベクトルμｊもスパース表現である場合について、図１０を参照しながら説明する。図１０は、本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例２）である。なお、図１０のステップＳ２０１、ステップＳ２０４及びステップＳ２０６〜ステップＳ２０７は、実施例１と同様であるため、その説明を省略する。
【００９６】
ステップＳ３０１：クラスタリング処理部１２０の初期設定部１２２は、スパース表現の各ｍｅａｎ特徴ベクトルμｊ（ｊ＝１，２，・・・，Ｋ）を適当な値に初期化する。初期化の方法としては、実施例１と同様の方法を用いれば良い。なお、初期化されたスパース表現のｍｅａｎ特徴ベクトルμｊは、例えば、記憶部１３０に格納される。
【００９７】
ここで、スパース表現のｍｅａｎ特徴ベクトルμｊの一例について、図１１を参照しながら説明する。図１１は、スパース表現のｍｅａｎ特徴ベクトルμｊの一例を示す図である。
【００９８】
図１１に示すように、スパース表現のｍｅａｎ特徴ベクトルμｊは、非零要素の位置を示す特徴ＩＤと、非零要素の値を示す特徴量との組（タプル）の列で構成される。図１１では、完全表現のｍｅａｎ特徴ベクトルμｊの非零要素がｓｊ個である場合に、ｐ＝１，２，・・・，ｓｊとして、これらの非零要素の特徴ＩＤ「ｚｐ」と、当該特徴ＩＤの特徴量「ｕｐ」との組（タプル）の列で構成されたスパース表現を表している。なお、各特徴ＩＤ「ｚｐ」及び特徴量「ｕｈ」は、ｍｅａｎ特徴ベクトルμｊのインデックスｊに依存するため、正確にはそれぞれ「ｚｊｐ」及び「ｕｊｐ」と表されるが、本発明の実施の形態では、特に断らない限り、「ｚｊｐ」及び「ｕｊｐ」とインデックスｊを省略して表す。なお、特徴ＩＤは、例えば、１≦ｚ１＜ｚ２＜・・・＜ｚｐ＜・・・＜ｚｓｊ≦Ｄのように昇順にソートされていることが好ましい。以降では、スパース表現のｍｅａｎ特徴ベクトルμｊの各特徴ＩＤは、上述のように昇順にソートされているものとする。
【００９９】
スパース表現のｍｅａｎ特徴ベクトルμｊを用いることで、スパース表現のｍｅａｎ特徴ベクトルμｊが使用するメモリサイズ（すなわち、記憶部１３０の記憶容量）を抑制することができる。
【０１００】
ステップＳ３０２：クラスタリング処理部１２０の割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉの各々について、現在のイテレーションのスパース表現のｍｅａｎ特徴ベクトルμｊとの距離を計算する。ここで、距離の定義は上記の式（１）の通りである。上述したように、ノルムの二乗は予め計算することが可能であるため、以降では、内積計算について説明する。
【０１０１】
実施例２では、オブジェクト特徴ベクトルｘｉとｍｅａｎ特徴ベクトルμｊとが共にスパース表現であるため、同じ非零要素位置を探索し、各々の非零要素位置に対する特徴量を乗算することで内積を計算する。以降では、一例として、図４に示すオブジェクト特徴ベクトルｘｉと、図１１に示すｍｅａｎ特徴ベクトルμｊとの内積を計算する場合について説明する。また、スパース表現のオブジェクト特徴ベクトルｘｉの各タプルが配列ｖｉ［ｈ］，０≦ｈ≦ｍ−１に格納されており、スパース表現のｍｅａｎ特徴ベクトルμｊの各タプルは配列ｗｊ［ｐ］，０≦ｐ≦ｓｊ−１に格納されているものとする。このとき、ｈ及びｐが配列インデックスである。
【０１０２】
ステップＳ３０２−１：割当部１２３は、内積値ｓｕｍを０に初期化する。また、割当部１２３は、ｈ＝１及びｐ＝１に初期化する。
【０１０３】
ステップＳ３０２−２：割当部１２３は、ｘｉの配列インデックスｈ−１の配列要素ｖｉ［ｈ−１］と、μｊの配列インデックスｐ−１の配列要素ｗｊ［ｐ−１］とにアクセスし、配列要素ｖｉ［ｈ−１］に格納されているｔｈと、配列要素ｗｊ［ｐ−１］に格納されているｚｐとの大小を比較する。
【０１０４】
ステップＳ３０２−３：割当部１２３は、上記のステップＳ３０２−２の比較結果に応じて、以下の（１）〜（３）のいずれかを行う。
【０１０５】
（１）ｔｈ＝ｚｐである場合、
割当部１２３は、ｓｕｍ←ｓｕｍ＋ｖｈ×ｕｐとする。また、割当部１２３は、ｐ←ｐ＋１又はｈ←ｈ＋１の何れか一方を行う。このとき、好ましくは、ｍ＜ｓｊならばｐを更新する。なお、「←」は、左辺を右辺で更新することを表す。
【０１０６】
（２）ｔｈ＞ｚｐである場合
割当部１２３は、ｐ←ｐ＋１とする。
【０１０７】
（３）ｔｈ＜ｚｐである場合
割当部１２３は、ｈ←ｈ＋１とする。
【０１０８】
ステップＳ３０２−４：割当部１２３は、「ｔｍ＝ｚｓｊ」、「ｈ＞ｍ」及び「ｐ＞ｓｊ」のいずれも満たさない場合、ステップＳ３０２−２に戻る。一方で、割当部１２３は、「ｔｍ＝ｚｓｊ」、「ｈ＞ｍ又は（ｈ＝ｍかつｔｈ＜ｚｓ＋１）」、又は「ｐ＞ｓｊ又は（ｐ＝ｓｊかつｚｐ＜ｔｈ＋１）」のいずれかを満たす場合、処理を終了する。
【０１０９】
以上のステップＳ３０２−１〜ステップＳ３０２−４によって最終的に得られたｓｕｍが内積値となる。この内積計算では、スパース表現のｍｅａｎ特徴ベクトルμｊの配列要素へのアクセス回数は、最悪の場合（worst case）でｍ＋ｓｊ−１回（すなわち、Ｏ（ｍ＋ｓｊ））である。また、乗算回数は、スパース表現のオブジェクト特徴ベクトルｘｉの特徴ＩＤの集合｛ｔ１，・・・，ｔｍ｝と、スパース表現のｍｅａｎ特徴ベクトルμｊの特徴ＩＤの集合｛ｚ１，・・・，ｚｓｊ｝との共通集合の要素数α´ｊ（ｍ）≦ｍとなる。このため、実施例１と比べて、多少計算量は増える。
【０１１０】
以上で説明した内積計算は、スパース表現のオブジェクト特徴ベクトルｘｉの各々について、Ｋ個のスパース表現のｍｅａｎ特徴ベクトルμｊを対象として行われる。したがって、Ｋ個のスパース表現のｍｅａｎ特徴ベクトルμｊの配列要素へのアクセス回数は、最悪の場合で
【０１１１】
【数５】
2019204436.tif 000007
である。また、乗算回数は、スパース表現のオブジェクト特徴ベクトルｘｉの特徴ＩＤの集合｛ｔ１，・・・，ｔｍ｝と、スパース表現のｍｅａｎ特徴ベクトルμｊの特徴ＩＤの集合｛ｚｊ１，・・・，ｚｊ（ｓｊ）｝と共通集合の要素数のｊ＝１，２，・・・，Ｋに関する和である
【０１１２】
【数６】
2019204436.tif 000008
となる。
【０１１３】
なお、上述したような同じ非零要素位置を探索する問題は、複数の集合の共通集合を求める問題（set intersection problem）と同じである。この問題の解法として、分割統治法であるマージソート（merge sort）のマージ部分で使用されている並列走査法（parallel scan）が知られている。この方法を上記のステップＳ３０２−１〜ステップＳ３０２−４の内積計算に応用することもできる。
【０１１４】
ステップＳ３０３：クラスタリング処理部１２０の更新部１２４は、各クラスタＣｊに属するスパース表現のオブジェクト特徴ベクトルｘｉにより、スパース表現のｍｅａｎ特徴ベクトルμｊを計算及び更新する。
【０１１５】
例えば、更新部１２４は、クラスタＣｊの各々について、当該クラスタＣｊに属するスパース表現のオブジェクト特徴ベクトルｘｉの平均を計算し、この平均をｍｅａｎ特徴ベクトルμｊとすれば良い。
【０１１６】
以上のように、本発明の実施の形態におけるクラスタリング装置１０は、実施例２のクラスタリング処理により、スパース表現のオブジェクト特徴ベクトルｘｉをクラスタリングすることができる。このとき、実施例２では、ｍｅａｎ特徴ベクトルμｊもスパース表現とすることで、実施例１と比べて多少計算量が増えるものの、メモリ使用量を更に抑制することができため、効率的なクラスタリングが可能となる。
【０１１７】
（実施例３）
次に、クラスタリング処理の実施例３として、転置ファイルのデータ構造で表現したｍｅａｎ特徴ベクトルμｊ（転置ファイルのデータ構造で表現したｍｅａｎ特徴ベクトルを「転置ファイル表現のｍｅａｎ特徴ベクトル」と表す。）を用いる場合について、図１２を参照しながら説明する。図１２は、本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例３）である。なお、図１２のステップＳ２０１、ステップＳ２０４及びステップＳ２０６〜ステップＳ２０７は、実施例１と同様であるため、その説明を省略する。
【０１１８】
ステップＳ４０１：クラスタリング処理部１２０の初期設定部１２２は、ｍｅａｎ転置ファイルを初期化する。ｍｅａｎ転置ファイルとは、転置ファイル表現のｍｅａｎ特徴ベクトルμｊ（ｊ＝１，２，・・・，Ｋ）が格納されている転置ファイルのことである。なお、初期化されたｍｅａｎ転置ファイルは、例えば、記憶部１３０に格納される。
【０１１９】
ここで、ｍｅａｎ転置ファイルの一例について、図１３を参照しながら説明する。図１３は、ｍｅａｎ転置ファイルの一例を示す図である。
【０１２０】
図１３に示すように、ｍｅａｎ転置ファイルは、特徴ＩＤ「ｈ」の非零特徴量を含むｍｅａｎ特徴ベクトルμｊのインデックスｊを表すｍｅａｎＩＤ「ｋｈｒ」と、当該非零特徴量ｗｈｒとの組（タプル）の列で構成される。ただし、各タプル列では、各タプルがｋｈｒの昇順にソートされているものとする。ここで、１≦ｒ≦ｑｈ、ｑｈは特徴量ＩＤ「ｈ」の特徴量が非零であるｍｅａｎ特徴ベクトルμｊの個数である。また、１≦ｈ≦Ｄである。なお、ｍｅａｎＩＤ「ｋｈｒ」は、クラスタＩＤとも呼ばれる。
【０１２１】
このようなデータ構造のｍｅａｎ転置ファイルでは、各タプル列それぞれで同一のｍｅａｎＩＤ「ｋｈｒ」のタプル群によって１つのｍｅａｎ特徴ベクトルμｊが表現される。具体的には、図１３に示す例で、ｊ＝ｋ１３＝ｋ２２＝ｋｈ４＝ｋＤ１である場合、｛（ｋ１３，ｗ１３），（ｋ２２，ｗ２２），（ｋｈ４，ｗｈ４），（ｋＤ１，ｗＤ１）｝によって１つのｍｅａｎ特徴ベクトルμｊが表現される。このように、ｍｅａｎ転置ファイルによりｍｅａｎ特徴ベクトルμｊを表現することで、各ｍｅａｎ特徴ベクトルμｊは、スパース表現と同様に非零要素を含まない形に圧縮されるため、メモリ使用量を抑制することができる。
【０１２２】
ステップＳ４０２：クラスタリング処理部１２０の割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉの各々について、現在のイテレーションの転置ファイル表現のｍｅａｎ特徴ベクトルμｊとの距離を計算する。ここで、距離の定義は上記の式（１）の通りである。上述したように、ノルムの二乗は予め計算することが可能であるため、以降では、内積計算について説明する。
【０１２３】
以降では、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現の各ｍｅａｎ特徴ベクトルμｊとの内積を計算する場合について、図１４を参照しながら説明する。図１４は、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現のｍｅａｎ特徴ベクトルμｊとの内積計算の一例を示す図（実施例３）である。なお、スパース表現のオブジェクト特徴ベクトルｘｉの各タプルが配列ｖｉ［ｈ］，０≦ｈ≦ｍ−１に格納されており、全てのｍｅａｎ特徴ベクトルμｊを含む転置ファイル表現では、特徴量は二次元配列ｗ［ｈ］［ｒ］，０≦ｈ≦Ｄ−１，０≦ｒ≦ｑｈ−１に格納されているものとする。
【０１２４】
ステップＳ４０２−１：割当部１２３は、各内積値ｓｕｍ（ｊ）を０に初期化する。また、割当部１２３は、ｈ＝１に初期化する。なお、ｓｕｍ（ｊ）は、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現のｍｅａｎ特徴ベクトルμｊとの内積値が格納される変数である。
【０１２５】
ステップＳ４０２−２：割当部１２３は、ｘｉの配列インデックスｈ−１の配列要素ｖｉ［ｈ−１］に格納されている特徴ＩＤ「ｔｈ」を用いて、各配列要素ｗ［ｔｈ−１］［ｒ］，０≦ｒ≦ｑｔｈ−１（なお、この「ｔｈ」のｈは、正確にはｔの下付き表記（すなわち、ｔｈ）である。以降も同様である。）にアクセスし、各配列要素ｗ［ｔｈ−１］［ｒ］にそれぞれ格納されている特徴量ｗｔｈｒ（０≦ｒ≦ｑｔｈ−１）と、配列要素ｖｉ［ｈ−１］に格納されている特徴量ｖｈとの積をそれぞれ計算し、該当のｓｕｍ（ｊ）に加算する。すなわち、割当部１２３は、以下の計算を行う。
【０１２６】
【数７】
2019204436.tif 000009
ステップＳ４０２−３：割当部１２３は、「ｈ＞ｍ」を満たすか否かを判定する。そして、割当部１２３は、「ｈ＞ｍ」を満たさないと判定した場合、ｈ←ｈ＋１として、ステップＳ４０２−２に戻る。一方で、割当部１２３は、「ｈ＞ｍ」を満たすと判定した場合、処理を終了する。
【０１２７】
以上のステップＳ４０２−１〜ステップＳ４０２−３によって最終的に得られたｓｕｍ（ｊ）が、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現のｍｅａｎ特徴ベクトルμｊとの内積値となる。この内積計算では、ｍｅａｎ転置ファイルの該当の特徴ＩＤのタプルへのアクセス回数は、
【０１２８】
【数８】
2019204436.tif 000010
である。すなわち、スパース表現のオブジェクト特徴ベクトルｘｉの特徴ＩＤの集合｛ｔ１，・・・，ｔｍ｝と、転置ファイル表現のｍｅａｎ特徴ベクトルμｊの特徴ＩＤの集合との共通集合のｊ＝１，２，・・・，Ｋに関する和である。なお、乗算回数はアクセス回数と一致する。このように、実施例３では、内積計算における乗算回数が実施例１と同様であり、内積計算を効率的に行うことができる。なお、図１４に示す例では、説明の便宜上、記載を省略しているが、配列インデックスの最大値はＤ−１である。
【０１２９】
ステップＳ４０３：クラスタリング処理部１２０の更新部１２４は、各クラスタＣｊに属するスパース表現のオブジェクト特徴ベクトルｘｉにより、ｍｅａｎ転置ファイルを更新する。これにより、転置ファイル表現のｍｅａｎ特徴ベクトルμｊが更新される。
【０１３０】
更新部１２４は、例えば、ｍｅａｎ転置ファイル用のメモリ（例えば、記憶部１３０の記憶領域）を確保した上で、クラスタＣｊの各々について、当該クラスタＣｊに属するスパース表現のオブジェクト特徴ベクトルｘｉの平均を計算し、この平均をｍｅａｎ特徴ベクトルμｊとしてｍｅａｎ転置ファイルに格納すれば良い。なお、ｍｅａｎ転置ファイル用のメモリの確保としては、例えば、各クラスタＣｊに属するオブジェクト特徴ベクトルｘｉの異なり単語数（異なる特徴ＩＤ数）と、当該特徴ＩＤを使用しているクラスタＣｊの数とを特定した上で、当該特徴ＩＤを使用しているクラスタＣｊのクラスタＩＤと、当該特徴ＩＤの特徴量とを保持するためのメモリを確保すれば良い。
【０１３１】
以上のように、本発明の実施の形態におけるクラスタリング装置１０は、実施例３のクラスタリング処理により、スパース表現のオブジェクト特徴ベクトルｘｉをクラスタリングすることができる。このとき、実施例３では、ｍｅａｎ特徴ベクトルμｊを転置ファイル表現とすることで、メモリ使用量を実施例２と同等にしつつ、内積計算における乗算回数を実施例１と同等とすることができ、効率的なクラスタリングが可能となる。
【０１３２】
（実施例４）
次に、クラスタリング処理の実施例４として、ｍｅａｎ特徴ベクトルμｊの更新を効率化した場合について、図１５を参照しながら説明する。図１５は、本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例４）である。なお、図１５のステップＳ２０１、ステップＳ２０４、ステップＳ２０６〜ステップＳ２０７及びステップＳ４０３は、実施例３と同様であるため、その説明を省略する。
【０１３３】
ステップＳ５０１：クラスタリング処理部１２０の初期設定部１２２は、ｍｅａｎ転置ファイルと、クラスタＣｊが不変クラスタであるか否かを示すフラグｆｊとを初期化する。なお、初期化されたｍｅａｎ転置ファイル及びフラグｆｊは、例えば、記憶部１３０に格納される。
【０１３４】
ここで、不変クラスタとは、１つ前のイテレーションでクラスタに属するメンバ（オブジェクト特徴ベクトルｘｉ）に変更がなかったクラスタＣｊのことである。言い換えれば、２つ前のイテレーションにおけるクラスタＣｊに属するメンバと、１つ前のイテレーションにおけるクラスタＣｊに属するメンバとが同一である場合、当該クラスタＣｊは不変クラスタである。以降では、例えば、フラグｆｊ＝１である場合、クラスタＣｊは不変クラスタであり、フラグｆｊ＝０である場合、クラスタＣｊは不変クラスタでないものとする。なお、各フラグｆｊの初期値としては、例えば、全て０とすれば良い。
【０１３５】
ステップＳ５０２：クラスタリング処理部１２０の割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉの各々について、現在のイテレーションの転置ファイル表現のｍｅａｎ特徴ベクトルμｊとの距離を計算する。ここで、距離の定義は上記の式（１）の通りである。上述したように、ノルムの二乗は予め計算することが可能であるため、以降では、内積計算について説明する。
【０１３６】
ところで、或るオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタである場合、現在のイテレーションで、当該オブジェクト特徴ベクトルｘｉが他の不変クラスタＣｊ´（ｊ´≠ｊ）に新たに属することはない。したがって、Ｃｊ及びＣｊ´が不変クラスタである場合に、（ｘｉ∈Ｃｊ）∧（Ｃｊ≠Ｃｊ´）であるならば、オブジェクト特徴ベクトルｘｉと、ｍｅａｎ特徴ベクトルμｊ´との距離計算は不要である。このことは、ＩＣＰ（Invariant Centroid-Pair skipping filter）とも称される。
【０１３７】
そこで、実施例４では、以下のステップＳ５０２−１〜ステップＳ５０２−６により、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現の各ｍｅａｎ特徴ベクトルμｊとの内積を計算する。なお、実施例３と同様に、スパース表現のオブジェクト特徴ベクトルｘｉの各タプルが配列ｖｉ［ｈ］，０≦ｈ≦ｍ−１に格納されており、全てのｍｅａｎ特徴ベクトルμｊを含む転置ファイル表現では、特徴量は二次元配列ｗ［ｈ］［ｒ］，０≦ｈ≦Ｄ−１，０≦ｒ≦ｑｈ−１に格納されているものとする。
【０１３８】
ステップＳ５０２−１：割当部１２３は、各内積値ｓｕｍ（ｊ）を０に初期化する。また、割当部１２３は、ｈ＝１に初期化する。
【０１３９】
ステップＳ５０２−２：割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタであるか否かを判定する。これは、当該オブジェクト特徴ベクトルｘｉが属するクラスタＣｊに対応するフラグｆｊの値を参照することで判定すれば良い。
【０１４０】
ステップＳ５０２−３：割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタでないと判定した場合、実施例３と同様に、ステップＳ４０２−２〜ステップＳ４０２−３により、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現の各ｍｅａｎ特徴ベクトルμｊとの内積を計算する。
【０１４１】
一方で、割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタであると判定した場合、以降のステップＳ５０２−４に進む。
【０１４２】
ステップＳ５０２−４：割当部１２３は、ｘｉの配列インデックスｈ−１の配列要素ｖｉ［ｈ−１］に格納されている特徴ＩＤ「ｔｈ」を用いて、各配列要素［ｔｈ−１］［ｒ］，０≦ｒ≦ｑｔｈ−１（なお、この「ｔｈ」のｈは、正確にはｔの下付き表記（すなわち、ｔｈ）である。以降も同様である。）にアクセスし、各配列要素ｗ［ｔｈ−１］［ｒ］にそれぞれ格納されているｍｅａｎＩＤ（クラスタＩＤ）「ｋｔｈｒ」（０≦ｒ≦ｑｔｈ−１）に対応するクラスタが不変クラスタであるか否かを判定する。すなわち、割当部１２３は、クラスタＣｊ（ただし、ｊ＝ｋｔｈｒ，０≦ｒ≦ｑｔｈ−１）がそれぞれ不変クラスタであるか否かを判定する。これは、上記と同様に、クラスタＣｊに対応するフラグｆｊの値を参照することで判定すれば良い。
【０１４３】
ステップＳ５０２−５：割当部１２３は、各配列要素ｗ［ｔｈ−１］［ｒ］のうち、上記のステップＳ５０２−４で不変クラスタと判定されたクラスタＣｊのクラスタＩＤ「ｊ＝ｋｔｈｒ」が格納されている配列要素を除く配列要素ｗに格納されている特徴量と、配列要素ｖｉ［ｈ−１］に格納されている特徴量ｖｈとの積をそれぞれ計算し、該当のｓｕｍ（ｊ）に加算する。言い換えれば、上記の数７において、不変クラスタＣｊに関するタプルを用いたｓｕｍ（ｊ）の更新をスキップする。
【０１４４】
ステップＳ５０２−６：割当部１２３は、「ｈ＞ｍ」を満たすか否かを判定する。そして、割当部１２３は、「ｈ＞ｍ」を満たさないと判定した場合、ｈ←ｈ＋１として、ステップＳ５０２−４に戻る。一方で、割当部１２３は、「ｈ＞ｍ」を満たすと判定した場合、処理を終了する。
【０１４５】
以上のステップＳ５０２−１〜ステップＳ５０２−６によって最終的に得られたｓｕｍ（ｊ）が、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現のｍｅａｎ特徴ベクトルμｊとの内積値となる。このように、実施例３では、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現のｍｅａｎ特徴ベクトルμｊとがそれぞれ異なる不変クラスタＣｊに属する場合には、これらｘｉとμｊとの内積計算を省略する。これにより、内積計算の回数を削減し、計算量を更に削減することができる。
【０１４６】
ステップＳ５０３：クラスタリング処理部１２０の更新部１２４は、ステップＳ２０４における割当結果に応じて、フラグｆｊを更新する。すなわち、更新部１２４は、上記のステップＳ２０４において、１つ前のイテレーションからクラスタＣｊのメンバが不変である場合はフラグｆｊを１に更新し、１つ前のイテレーションからクラスタＣｊのメンバが変更になった場合はフラグｆｊを０に更新する。
【０１４７】
以上のように、本発明の実施の形態におけるクラスタリング装置１０は、実施例４のクラスタリング処理により、スパース表現のオブジェクト特徴ベクトルｘｉをクラスタリングすることができる。このとき、実施例４では、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現のｍｅａｎ特徴ベクトルμｊとがそれぞれ異なる不変クラスタＣｊに属する場合には、これらｘｉとμｊとの内積計算を省略する。これにより、実施例３と比較して、内積計算における乗算回数を削減することができ、より効率的なクラスタリングが可能となる。
【０１４８】
（実施例５）
次に、クラスタリング処理の実施例５として、２種類のｍｅａｎ転置ファイル（すなわち、「全ｍｅａｎ転置ファイル」及び「変動ｍｅａｎ転置ファイル」）を用いる場合について、図１６を参照しながら説明する。図１６は、本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例５）である。なお、図１６のステップＳ２０１、ステップＳ２０４、ステップＳ２０６〜ステップＳ２０７及びステップＳ５０３は、実施例４と同様であるため、その説明を省略する。
【０１４９】
ステップＳ６０１：クラスタリング処理部１２０の初期設定部１２２は、全ｍｅａｎ転置ファイルと、変動ｍｅａｎ転置ファイルと、クラスタＣｊが不変クラスタであるか否かを示すフラグｆｊとを初期化する。なお、初期化された全ｍｅａｎ転置ファイルと変動ｍｅａｎ転置ファイルとフラグｆｊとは、例えば、記憶部１３０に格納される。
【０１５０】
ここで、全ｍｅａｎ転置ファイルとは、実施例３及び実施例４におけるｍｅａｎ転置ファイルのことである。一方で、変動ｍｅａｎ転置ファイルとは、全ｍｅａｎ転置ファイルから、不変クラスタＣｊに属するｍｅａｎ特徴ベクトルμｊを除いたものである。なお、全ｍｅａｎ転置ファイル及び変動ｍｅａｎ転置ファイルは同じ内容に初期化される。
【０１５１】
ステップＳ６０２：クラスタリング処理部１２０の割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉの各々について、現在のイテレーションの転置ファイル表現のｍｅａｎ特徴ベクトルμｊとの距離を計算する。ここで、距離の定義は上記の式（１）の通りである。上述したように、ノルムの二乗は予め計算することが可能であるため、以降では、内積計算について説明する。
【０１５２】
実施例５では、以下のステップＳ６０２−１〜ステップＳ６０２−３により内積計算を行う。
【０１５３】
ステップＳ６０２−１：割当部１２３は、各内積値ｓｕｍ（ｊ）を０に初期化する。また、割当部１２３は、ｈ＝１に初期化する。
【０１５４】
ステップＳ６０２−２：割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタであるか否かを判定する。これは、当該オブジェクト特徴ベクトルｘｉが属するクラスタＣｊに対応するフラグｆｊの値を参照することで判定すれば良い。
【０１５５】
ステップＳ６０２−３：割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタでないと判定した場合、全ｍｅａｎ転置ファイルを用いて、上記のステップＳ４０２−２〜ステップＳ４０２−３により、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現の各ｍｅａｎ特徴ベクトルμｊとの内積を計算する。
【０１５６】
一方で、割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタであると判定した場合、変動ｍｅａｎ転置ファイルを用いて、上記のステップＳ４０２−２〜ステップＳ４０２−３により、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現の各ｍｅａｎ特徴ベクトルμｊとの内積を計算する。
【０１５７】
このように、実施例５では、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタであるか否かに応じて、全ｍｅａｎ転置ファイル又は変動ｍｅａｎ転置ファイルのいずれかを用いて、転置ファイル表現のｍｅａｎ特徴ベクトルμｊとの内積計算を計算する。
【０１５８】
ステップＳ６０３：クラスタリング処理部１２０の更新部１２４は、各クラスタＣｊに属するスパース表現のオブジェクト特徴ベクトルｘｉにより、全ｍｅａｎ転置ファイル及び変動ｍｅａｎ転置ファイルを更新する。ここで、更新部１２４は、ｍｅａｎ特徴ベクトルμｊが不変クラスタＣｊに属する場合、このｍｅａｎ特徴ベクトルμｊを全ｍｅａｎ転置ファイルのみに格納する。一方で、更新部１２４は、ｍｅａｎ特徴ベクトルμｊが不変クラスタＣｊに属しない場合、このｍｅａｎ特徴ベクトルμｊを全ｍｅａｎ転置ファイル及び変動ｍｅａｎ転置ファイルの両方に格納する。これにより、全ｍｅａｎ転置ファイル及び変動ｍｅａｎ転置ファイルが更新される。
【０１５９】
以上のように、本発明の実施の形態におけるクラスタリング装置１０は、実施例５のクラスタリング処理により、スパース表現のオブジェクト特徴ベクトルｘｉをクラスタリングすることができる。このとき、実施例５では、全ｍｅａｎ転置ファイルと変動ｍｅａｎ転置ファイルとを用いることで、実施例４のステップＳ５０２−４の判定（ｍｅａｎ特徴ベクトルμｊが不変クラスタＣｊに属するか否かの判定）が不要となり、内積計算を高速に行うことができるようになる。ただし、実施例５では、全ｍｅａｎ転置ファイルと変動ｍｅａｎ転置ファイルとを用いるため、実施例３及び４と比べて、メモリ容量（記憶部１３０の記憶容量）が多く必要となる。
【０１６０】
なお、Ｌｌｏｙｄ法のイテレーション開始時から変動ｍｅａｎ転置ファイルを用いた場合、最悪のケースでは全ｍｅａｎ転置ファイルの２倍のメモリ容量が必要となる。このため、例えば、所定の或る条件を満たすまでは実施例４のクラスタリング処理を実行し、当該条件を満たした後は実施例５のクラスタリング処理を実行する等、実施例４と実施例５との併用も可能である。所定の或る条件とは、例えば、イテレーション回数が所定の回数以上となったこと、不変クラスタの割合が所定の割合以上となったこと、不変クラスタの数が所定の数以上となったこと等が挙げられる。
【０１６１】
（実施例６）
次に、クラスタリング処理の実施例６として、境界インデックス付きｍｅａｎ転置ファイルを用いる場合について、図１７を参照しながら説明する。図１７は、本発明の実施の形態におけるクラスタリング処理の一例を示すフローチャート（実施例６）である。なお、図１７のステップＳ２０１、ステップＳ２０４、ステップＳ２０６〜ステップＳ２０７及びステップＳ５０３は、実施例４と同様であるため、その説明を省略する。
【０１６２】
ステップＳ７０１：クラスタリング処理部１２０の初期設定部１２２は、境界インデックス付きｍｅａｎ転置ファイルと、クラスタＣｊが不変クラスタであるか否かを示すフラグｆｊとを初期化する。なお、初期化された境界インデックス付きｍｅａｎ転置ファイルとフラグｆｊとは、例えば、記憶部１３０に格納される。
【０１６３】
ここで、境界インデックス付きｍｅａｎ転置ファイルとは、不変クラスタＣｊに属しないｍｅａｎ特徴ベクトルμｊが前半部分に、不変クラスタＣｊに属するｍｅａｎ特徴ベクトルμｊが後半部分に格納され、前半部分と後半部分との境界を示す境界インデックスが付与された転置ファイルのことである。境界インデックスとしては、例えば、前半部分の最後に格納されているｍｅａｎ特徴ベクトルμｊのインデックスｊとすれば良い。なお、必須の要件ではないが、ｍｅａｎ転置ファイルの各タプル列では、各タプルがｍｅａｎＩＤ「ｊ」（クラスタＩＤ）の昇順にソートされていても良い。
【０１６４】
ここで、境界インデックスの初期値としては、例えば、境界インデックス付きｍｅａｎ転置ファイルに格納されているｍｅａｎ特徴ベクトルμｊの最大値（すなわち、最後に格納されているｍｅａｎ特徴ベクトルμｊのインデックスｊ）とすれば良い。
【０１６５】
ステップＳ７０２：クラスタリング処理部１２０の割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉの各々について、現在のイテレーションの転置ファイル表現のｍｅａｎ特徴ベクトルμｊとの距離を計算する。ここで、距離の定義は上記の式（１）の通りである。上述したように、ノルムの二乗は予め計算することが可能であるため、以降では、内積計算について説明する。
【０１６６】
実施例６では、以下のステップＳ７０２−１〜ステップＳ７０２−３により内積計算を行う。
【０１６７】
ステップＳ７０２−１：割当部１２３は、各内積値ｓｕｍ（ｊ）を０に初期化する。また、割当部１２３は、ｈ＝１に初期化する。
【０１６８】
ステップＳ７０２−２：割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタであるか否かを判定する。これは、当該オブジェクト特徴ベクトルｘｉが属するクラスタＣｊに対応するフラグｆｊの値を参照することで判定すれば良い。
【０１６９】
ステップＳ７０２−３：割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタでないと判定した場合、境界インデックス付きｍｅａｎ転置ファイルに格納されている全てのｍｅａｎ特徴ベクトルμｊを用いて、上記のステップＳ４０２−２〜ステップＳ４０２−３により、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現の各ｍｅａｎ特徴ベクトルμｊとの内積を計算する。
【０１７０】
一方で、割当部１２３は、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタであると判定した場合、境界インデックス付きｍｅａｎ転置ファイルに格納されているｍｅａｎ特徴ベクトルμｊのうち、先頭から境界インデックスまでのｍｅａｎ特徴ベクトルμｊを用いて、上記のステップＳ４０２−２〜ステップＳ４０２−３により、スパース表現のオブジェクト特徴ベクトルｘｉと、転置ファイル表現の各ｍｅａｎ特徴ベクトルμｊとの内積を計算する。
【０１７１】
このように、実施例６では、スパース表現のオブジェクト特徴ベクトルｘｉが属するクラスタＣｊが不変クラスタである場合、境界インデックス付きｍｅａｎ転置ファイルの前半部分に格納されているｍｅａｎ特徴ベクトルμｊとの内積を計算する。これにより、実施例４のステップＳ５０２−４の判定（ｍｅａｎ特徴ベクトルμｊが不変クラスタＣｊに属するか否かの判定）が不要になると共に、境界インデックス付きｍｅａｎ転置ファイルに必要なメモリ容量を抑えることができる。
【０１７２】
ステップＳ７０３：クラスタリング処理部１２０の更新部１２４は、各クラスタＣｊに属するスパース表現のオブジェクト特徴ベクトルｘｉにより、境界インデックス付きｍｅａｎ転置ファイルを更新する。ここで、更新部１２４は、ｍｅａｎ特徴ベクトルμｊが不変クラスタＣｊに属しない場合、このｍｅａｎ特徴ベクトルμｊを境界インデックス付きｍｅａｎ転置ファイルの前半部分に格納し、ｍｅａｎ特徴ベクトルμｊが不変クラスタＣｊに属する場合、このｍｅａｎ特徴ベクトルμｊを境界インデックス付きｍｅａｎ転置ファイルの後半部分に格納する。また、更新部１２４は、例えば、前半部分の最後に格納されているｍｅａｎ特徴ベクトルμｊのインデックスｊを境界インデックスとする。
【０１７３】
以上のように、本発明の実施の形態におけるクラスタリング装置１０は、実施例６のクラスタリング処理により、スパース表現のオブジェクト特徴ベクトルｘｉをクラスタリングすることができる。このとき、実施例６では、境界インデックス付きｍｅａｎ転置ファイルを用いることで、実施例４のステップＳ５０２−４の判定（ｍｅａｎ特徴ベクトルμｊが不変クラスタＣｊに属するか否かの判定）が不要となり、内積計算を高速に行うことができるようになる。しかも、実施例６では、実施例５と比べて、より少ないメモリ容量（記憶部１３０の記憶容量）で効率的にクラスタリングを行うことができるようになる。
【０１７４】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１７５】
１０        クラスタリング装置
１１０      前処理部
１２０      クラスタリング処理部
１２１      入力部
１２２      初期設定部
１２３      割当部
１２４      更新部
１２５      終了判定部
１２６      出力部
１３０      記憶部
【図１】
2019204436.tif 000011
【図２】
2019204436.tif 000012
【図３】
2019204436.tif 000013
【図４】
2019204436.tif 000014
【図５】
2019204436.tif 000015
【図６】
2019204436.tif 000016
【図７】
2019204436.tif 000017
【図８】
2019204436.tif 000018
【図９】
2019204436.tif 000019
【図１０】
2019204436.tif 000020
【図１１】
2019204436.tif 000021
【図１２】
2019204436.tif 000022
【図１３】
2019204436.tif 000023
【図１４】
2019204436.tif 000024
【図１５】
2019204436.tif 000025
【図１６】
2019204436.tif 000026
【図１７】
2019204436.tif 000027