特許ウォッチ

公開番号2023183848
公報種別公開特許公報(A)
公開日2023-12-28
出願番号2022097621
出願日2022-06-16
発明の名称クラスタリング装置、クラスタリング方法及びプログラム
出願人日本電信電話株式会社,学校法人神奈川大学
代理人個人,個人,個人
主分類G06F 17/16 20060101AFI20231221BHJP(計算;計数)
要約【課題】疎データを効率的にクラスタリングする装置、方法及びプログラムを提供する。
【解決手段】オブジェクトを表す1以上の特徴とその特徴量で構成されるオブジェクト特徴ベクトルを複数のクラスタにクラスタリングするクラスタリング装置は、特徴を識別する特徴識別子毎に、クラスタを識別するクラスタ識別子と該クラスタに属するオブジェクト特徴ベクトルの平均を表すmean特徴ベクトルの特徴識別子に関する第1の非零特徴量とを対応付けた組を格納する配列要素で構成されるデータを記憶し、データに基づいて、オブジェクト特徴ベクトルの第2の非零特徴量と第2の非零特徴量の特徴識別子とを対応付けた組でオブジェクト特徴ベクトルを表したスパース表現のオブジェクト特徴ベクトルと、各クラスタのmean特徴ベクトルとの類似度を計算し、類似度に基づいて、オブジェクト特徴ベクトルを、複数のクラスタのうちの一のクラスタに割り当てる。
【選択図】図7
特許請求の範囲【請求項１】
オブジェクトを表す１以上の特徴と前記１以上の特徴の各々の値である１以上の特徴量とで構成されるオブジェクト特徴ベクトルを複数のクラスタにクラスタリングするクラスタリング装置であって、
前記特徴を識別する特徴識別子毎に、前記クラスタを識別するクラスタ識別子と該クラスタに属するオブジェクト特徴ベクトルの平均を表すｍｅａｎ特徴ベクトルの前記特徴識別子に関する第１の非零特徴量とを対応付けた組を格納する配列要素で構成されたデータを記憶部に記憶させるように構成されている記憶制御部と、
前記データに基づいて、前記オブジェクト特徴ベクトルの第２の非零特徴量と該第２の非零特徴量の特徴識別子とを対応付けた組で前記オブジェクト特徴ベクトルを表したスパース表現のオブジェクト特徴ベクトルと、各クラスタの前記ｍｅａｎ特徴ベクトルとの類似度を計算するように構成されている類似度計算部と、
前記類似度に基づいて、前記オブジェクト特徴ベクトルを、前記複数のクラスタのうちの一のクラスタに割り当てるように構成されている割当部と、
を有し、
前記データは、
前記特徴識別子が第１の閾値未満の前記配列要素を表す第１の配列要素と、前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値以上の前記配列要素を表す第２の配列要素と、前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値未満の前記配列要素を表す第３の配列要素とで構成されている、クラスタリング装置。
続きを表示（約 2,300 文字）【請求項２】
前記データは、
前記特徴識別子が第１の閾値未満の前記配列要素を表す第１の配列要素と、前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値以上の前記配列要素を表す第２の配列要素と、前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値未満の前記配列要素を表す第３の配列要素とが転置ファイルで構成されている、請求項１に記載のクラスタリング装置。
【請求項３】
前記データは、
前記特徴識別子が第１の閾値未満の前記配列要素を表す第１の配列要素と、前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値以上の前記配列要素を表す第２の配列要素とが転置ファイルで構成されており、
前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値未満の前記配列要素を表す第３の配列要素が標準的な転置ファイルで構成されている、請求項１に記載のクラスタリング装置。
【請求項４】
前記類似度計算部は、
前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量の特徴識別子が前記第１の閾値未満である場合、前記第２の非零特徴量と、前記データを構成する配列要素のうち、前記特徴識別子に対応する配列要素に格納されている第１の非零特徴量と積を計算することで、前記類似度を計算し、
前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量の特徴識別子が前記第１の閾値以上、かつ、前記第２の非零特徴量との類似度の計算対象となる第１の非零特徴量が前記第２の閾値以上である場合、前記第２の非零特徴量と前記第１の非零特徴量との積を計算することで、前記類似度を計算すると共に、前記スパース表現のオブジェクト特徴ベクトルの部分的なノルムを計算し、
前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量の特徴識別子が前記第１の閾値以上、かつ、前記第２の非零特徴量との類似度の計算対象となる第１の非零特徴量が前記第２の閾値未満である場合、前記スパース表現のオブジェクト特徴ベクトルと該オブジェクト特徴ベクトルが現在属しているクラスタのｍｅａｎ特徴ベクトルとの類似度が、前記ノルムから計算される類似度上限値以下であるときに、前記第２の非零特徴量と前記第１の非零特徴量との積を計算することで、前記類似度を計算するように構成されている、請求項１に記載のクラスタリング装置。
【請求項５】
前記データは、
前記第１の配列要素及び前記第２の配列要素のそれぞれにおいて、前記割当部による割り当ての前後でクラスタに属するオブジェクト特徴ベクトルに変更あったクラスタを示す変更クラスタに対応するｍｅａｎ特徴ベクトルの第１の非零要素が含まれる組が格納される配列要素と、前記割当部による割り当ての前後でクラスタに属するオブジェクト特徴ベクトルが不変であったクラスタを示す不変クラスタに対応するｍｅａｎ特徴ベクトルの第１の非零要素が含まれる組が格納される配列要素とが区別可能に存在し、
前記類似度計算部は、
前記スパース表現のオブジェクト特徴ベクトルが属するクラスタが不変クラスタである場合、前記スパース表現のオブジェクト特徴ベクトルに含まれる第２の非零特徴量と、前記変更クラスタに対応するｍｅａｎ特徴ベクトルの第１の非零要素との積を計算することで、前記類似度を計算するように構成されている、請求項１乃至３の何れか一項に記載のクラスタリング装置。
【請求項６】
１つ前のイテレーションにおける前記類似度計算部による類似度の計算結果と前記割当部による割当結果とに基づいて、前記第２の閾値を最適化するように構成されている最適化部を更に有する請求項１に記載のクラスタリング装置。
【請求項７】
オブジェクトを表す１以上の特徴と前記１以上の特徴の各々の値である１以上の特徴量とで構成されるオブジェクト特徴ベクトルを複数のクラスタにクラスタリングするクラスタリング装置が、
前記特徴を識別する特徴識別子毎に、前記クラスタを識別するクラスタ識別子と該クラスタに属するオブジェクト特徴ベクトルの平均を表すｍｅａｎ特徴ベクトルの前記特徴識別子に関する第１の非零特徴量とを対応付けた組を格納する配列要素で構成されたデータを記憶部に記憶させる記憶制御手順と、
前記データに基づいて、前記オブジェクト特徴ベクトルの第２の非零特徴量と該第２の非零特徴量の特徴識別子とを対応付けた組で前記オブジェクト特徴ベクトルを表したスパース表現のオブジェクト特徴ベクトルと、各クラスタの前記ｍｅａｎ特徴ベクトルとの類似度を計算する類似度計算手順と、
前記類似度に基づいて、前記オブジェクト特徴ベクトルを、前記複数のクラスタのうちの一のクラスタに割り当てる割当手順と、
を実行し、
前記データは、
前記特徴識別子が第１の閾値未満の前記配列要素を表す第１の配列要素と、前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値以上の前記配列要素を表す第２の配列要素と、前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値未満の前記配列要素を表す第３の配列要素とで構成されている、クラスタリング方法。
【請求項８】
コンピュータを、請求項１に記載のクラスタリング装置として機能させるプログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、クラスタリング装置、クラスタリング方法及びプログラムに関する。
続きを表示（約 3,100 文字）【背景技術】
【０００２】
膨大な量の情報を効率的に処理するための方法の１つとして、ｋ－ｍｅａｎｓ法に代表されるクラスタリング手法が知られている。クラスタリング手法では、各々の情報の間の関係性（類似度、非類似度、距離等）を表す尺度により、複数の情報を１つにまとめたり、与えられた情報群を複数の集合に分割したりできる。以下、クラスタリングの対象となる「情報」を「オブジェクト」と呼ぶ。
【０００３】
ｋ－ｍｅａｎｓ法は、例えば、オブジェクトの特徴を表すベクトルデータ（以下、オブジェクト特徴ベクトルという。）をｘ
ｉ
として、データ集合Ｘ＝｛ｘ
０
，ｘ
１
，・・・，ｘ
Ｎ－１
｝とクラスタ数Ｋとが与えられたときに、データ集合ＸをＫ個のクラスタに分割する手法である。ｋ－ｍｅａｎｓ法では、例えば、クラスタＣ
ｊ
に属する各オブジェクト特徴ベクトルｘ
ｉ
の平均を表すベクトルμ
ｊ
（以下、ｍｅａｎ特徴ベクトルという。）との内積を目的関数として、その目的関数を最大化するように、各オブジェクト特徴ベクトルｘ
ｉ
が割り当てられるクラスタＣ
ｊ
が決定される。一方で、ｋ－ｍｅａｎｓ法の厳密解を計算するには多くの計算量を要するため、Ｌｌｏｙｄ法と呼ばれる発見的手法が良く用いられる。
【０００４】
ところで、近年では、オブジェクト特徴ベクトルが高次元かつ疎（スパース）なデータで表されることが多い。例えば、文書、購入者（又はユーザ）と購入品（又はアイテム）との関係を表す購買履歴、ｂａｇ－ｏｆ－ｖｉｓｕａｌｗｏｒｄｓで表される画像等をオブジェクトとした場合、これらのオブジェクトは高次元かつ疎なオブジェクト特徴ベクトルで表現されることが多い。以下、大量の高次元かつ疎なデータの集合を大規模高次元疎データ集合と呼ぶ。
【０００５】
Ｌｌｏｙｄ法は初期状態設定ステップ、割当ステップ、更新ステップ及び終了判定ステップで構成されるが、割当ステップでは各オブジェクト特徴ベクトルｘ
ｉ
と各ｍｅａｎ特徴ベクトルμ
ｊ
との内積を計算する必要があるため、割当ステップの時間計算量が支配的である。このため、割当ステップの時間計算量を削減することが求められている。
【０００６】
Ｌｌｏｙｄ法の割当ステップは、オブジェクト特徴ベクトルの集合をクエリオブジェクト集合、ｍｅａｎ特徴ベクトルの集合を被探索データオブジェクト集合と見做せば、最類似探索問題と等価である。大規模高次元疎データ集合の最類似探索問題を高速に解くことが可能な代表的な手法の１つに、データ構造として転置ファイル（inverted file）（又は、転置インデックス（inverted index）とも呼ばれる。）を使用する方法が知られている。例えば、非特許文献１及び２では、転置ファイルを効率的に利用した高速化手法が提案されている。また、非特許文献３では、ｍｅａｎ特徴ベクトル集合の転置ファイルで表現した高速化手法が提案されている。なお、転置ファイルを利用した手法ではないが、非特許文献４では、類似度の上限値（又は、距離の下限値）を用いて、Ｌｌｏｙｄ法を加速する手法（Ｄｉｎｇ法と呼ぶ。）が提案されている。
【先行技術文献】
【非特許文献】
【０００７】
M. Fontoura, V. Josifovski, J. Liu, S. Venkatesan, X. Zhu, and J. Zien, "Evaluation strategies for top-k queries over memory-resident inverted indexes," Proc. VLDB Endowment, vol. 5, no. 12, 2011.
Y. Li, J. Wang, B. Pullman, N. Bandeira, and Y. Papakonstantinou, "Index-based, high-dimensional, cosine threshold querying with optimality guarantees," Proc. Int. Conf. Database Theory (ICDT), 2019.
Kazuo Aoyama and Kazumi Saito, "Structured inverted-file k-means clustering for high-dimensional sparse data," arXiv: 2103.16141, https://arxiv.org/abs/2103.16141.
Y. Ding, Y. Zhao, X. Shen, M. Musuvathi, and T. Mykowicz, "Yinyang K-means: A drop-in replacement of the classic K-means with consistent speedup," Proc. Int. Conf. Machine Learning (ICML), 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、大規模高次元疎データ集合に対するクラスタリング手法の更なる高速化が望まれている。
【０００９】
本開示は、上記の点に鑑みてなされたもので、疎データを効率的にクラスタリングする技術を提供する。
【課題を解決するための手段】
【００１０】
本開示の一態様によるクラスタリング装置は、オブジェクトを表す１以上の特徴と前記１以上の特徴の各々の値である１以上の特徴量とで構成されるオブジェクト特徴ベクトルを複数のクラスタにクラスタリングするクラスタリング装置であって、前記特徴を識別する特徴識別子毎に、前記クラスタを識別するクラスタ識別子と該クラスタに属するオブジェクト特徴ベクトルの平均を表すｍｅａｎ特徴ベクトルの前記特徴識別子に関する第１の非零特徴量とを対応付けた組を格納する配列要素で構成されたデータを記憶部に記憶させるように構成されている記憶制御部と、前記データに基づいて、前記オブジェクト特徴ベクトルの第２の非零特徴量と該第２の非零特徴量の特徴識別子とを対応付けた組で前記オブジェクト特徴ベクトルを表したスパース表現のオブジェクト特徴ベクトルと、各クラスタの前記ｍｅａｎ特徴ベクトルとの類似度を計算するように構成されている類似度計算部と、前記類似度に基づいて、前記オブジェクト特徴ベクトルを、前記複数のクラスタのうちの一のクラスタに割り当てるように構成されている割当部と、を有し、前記データは、前記特徴識別子が第１の閾値未満の前記配列要素を表す第１の配列要素と、前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値以上の前記配列要素を表す第２の配列要素と、前記特徴識別子が前記第１の閾値以上かつ前記第１の非零特徴量が第２の閾値未満の前記配列要素を表す第３の配列要素とで構成されている。
【発明の効果】
（【００１１】以降は省略されています）

関連特許