特許ウォッチ

公開番号2025030976
公報種別公開特許公報(A)
公開日2025-03-07
出願番号2023136888
出願日2023-08-25
発明の名称データ処理システム、プログラム及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06F 18/231 20230101AFI20250228BHJP(計算;計数)
要約【課題】階層クラスタリングの実行時間を短縮する。
【解決手段】イジング装置11は、複数のノードを含む第1クラスタを、第2クラスタと第3クラスタに分割するときの第1分割候補を算出する。情報処理装置12は、イジング装置11から、複数の第1分割パターンのそれぞれに対する第1分割候補を表す分割候補情報を取得し、第1分割候補の評価関数の値に基づいて、複数の第1分割パターンのそれぞれに対する第1分割候補のうちの1つを選択して、第1クラスタを第2クラスタと第3クラスタに分割し、非選択の第1分割候補の分割候補情報を記憶部12aに記憶し、その分割候補情報に基づいて、第2クラスタの第2分割パターンに対応する非選択の第1分割候補の有無を判定し、その第1分割候補があると判定した場合、その第1分割候補を含む、第2クラスタの第2分割候補のうちの1つを選択して第2クラスタを第4クラスタと第5クラスタに分割する。
【選択図】図1
特許請求の範囲【請求項１】
複数のノードを含む第１クラスタを、第２クラスタと第３クラスタに分割するときの第１分割候補を、前記複数のノード間の重み値を含むイジング型の評価関数に基づいて算出するイジング装置と、
前記イジング装置から、前記第１クラスタに含まれるノード数によって決まる複数の第１分割パターンのそれぞれに対する複数の前記第１分割候補を表す分割候補情報を取得し、
複数の前記第１分割候補の前記評価関数の値に基づいて、前記複数の第１分割パターンのそれぞれに対する複数の前記第１分割候補のうちの１つを選択して、前記第１クラスタを前記第２クラスタと前記第３クラスタに分割し、
複数の前記第１分割候補のうち非選択の前記第１分割候補の前記分割候補情報を記憶部に記憶し、
前記記憶部に記憶した前記分割候補情報に基づいて、前記第２クラスタの第２分割パターンに対応する非選択の前記第１分割候補の有無を判定し、
前記第２分割パターンに対応する非選択の前記第１分割候補があると判定した場合、前記第２分割パターンに対応する非選択の前記第１分割候補を含む、前記第２クラスタの第２分割候補のうちの１つを選択して前記第２クラスタを第４クラスタと第５クラスタに分割する、
情報処理装置と、
を有するデータ処理システム。
続きを表示（約 1,500 文字）【請求項２】
非選択の前記第１分割候補の前記分割候補情報は、前記第２クラスタの分割に用いられる第２分割候補情報と、前記第３クラスタの分割に用いられる第３分割候補情報とを含み、
前記情報処理装置は、前記第２クラスタに含まれるノードの情報に基づいて、前記第２分割候補情報を生成し、前記第３クラスタに含まれるノードの情報に基づいて、前記第３分割候補情報を生成する、
請求項１に記載のデータ処理システム。
【請求項３】
前記第２分割候補情報は、前記第２分割パターンと、前記第２クラスタに含まれるノードの番号を含み、
前記第３分割候補情報は、前記第３クラスタの第３分割パターンと、前記第３クラスタに含まれるノードの番号を含む、
請求項２に記載のデータ処理システム。
【請求項４】
イジング装置に、複数のノードを含む第１クラスタを、第２クラスタと第３クラスタに分割するときの第１分割候補を、前記複数のノード間の重み値を含むイジング型の評価関数に基づいて算出させ、
前記イジング装置から、前記第１クラスタに含まれるノード数によって決まる複数の第１分割パターンのそれぞれに対する複数の前記第１分割候補を表す分割候補情報を取得し、
複数の前記第１分割候補の前記評価関数の値に基づいて、前記複数の第１分割パターンのそれぞれに対する複数の前記第１分割候補のうちの１つを選択して、前記第１クラスタを前記第２クラスタと前記第３クラスタに分割し、
複数の前記第１分割候補のうち非選択の前記第１分割候補の前記分割候補情報をメモリに記憶し、
前記メモリに記憶した前記分割候補情報に基づいて、前記第２クラスタの第２分割パターンに対応する非選択の前記第１分割候補の有無を判定し、
前記第２分割パターンに対応する非選択の前記第１分割候補があると判定した場合、前記第２分割パターンに対応する非選択の前記第１分割候補を含む、前記第２クラスタの第２分割候補のうちの１つを選択して前記第２クラスタを第４クラスタと第５クラスタに分割する、
処理をコンピュータに実行させるプログラム。
【請求項５】
イジング装置が、複数のノードを含む第１クラスタを、第２クラスタと第３クラスタに分割するときの第１分割候補を、前記複数のノード間の重み値を含むイジング型の評価関数に基づいて算出し、
情報処理装置が、
前記イジング装置から、前記第１クラスタに含まれるノード数によって決まる複数の第１分割パターンのそれぞれに対する複数の前記第１分割候補を表す分割候補情報を取得し、
複数の前記第１分割候補の前記評価関数の値に基づいて、前記複数の第１分割パターンのそれぞれに対する複数の前記第１分割候補のうちの１つを選択して、前記第１クラスタを前記第２クラスタと前記第３クラスタに分割し、
複数の前記第１分割候補のうち非選択の前記第１分割候補の前記分割候補情報を記憶部に記憶し、
前記記憶部に記憶した前記分割候補情報に基づいて、前記第２クラスタの第２分割パターンに対応する非選択の前記第１分割候補の有無を判定し、
前記第２分割パターンに対応する非選択の前記第１分割候補があると判定した場合、前記第２分割パターンに対応する非選択の前記第１分割候補を含む、前記第２クラスタの第２分割候補のうちの１つを選択して前記第２クラスタを第４クラスタと第５クラスタに分割する、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、データ処理システム、プログラム及びデータ処理方法に関する。
続きを表示（約 1,700 文字）【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする大規模な離散最適化問題を計算する装置として、イジング型の評価関数（エネルギー関数などとも呼ばれる）を用いたイジング装置（ボルツマンマシンとも呼ばれる）がある。イジング装置による計算では、計算対象の問題は磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えられる。そして、マルコフ連鎖モンテカルロ法により、イジング型の評価関数の値（イジングモデルのエネルギーに相当する）が極小になるイジングモデルの状態の探索が行われる。評価関数の極小値のうちの最小値になる状態が最適解となる。
【０００３】
ところで、データ同士の相関を可視化するためのデータ分析手法の１つとして、分割型の階層クラスタリングがある。分割型の階層クラスタリングは、それぞれがデータを表す全ノードが１つのクラスタの状態から、ノード間の重み値（たとえば、類似度）に基づいて、順次クラスタを分割していく手法である。
【０００４】
なお、ブロックストレージに書き込まれるデータの圧縮において、一括圧縮の対象となるブロックを決定する際に、階層クラスタリングを用いることが提案されている（たとえば、特許文献１参照）。また、従来、ニューラルネットのパラメータ更新を誤差逆伝搬により行う際に、各レイヤにおける誤差の最小化するために、イジング装置の一種である量子アニーリング装置を用いる手法が提案されている（たとえば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００５】
特開２０１９－４６０２３号公報
国際公開第２０２０－２５５６３４号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
分割型の階層クラスタリングの実行時間の短縮のため、各ノードを分割後の２つのクラスタの何れに分類するかを、各クラスタのノード数の分割パターンごとにイジング装置に算出させることができる。しかし、ノード数が増えてくると分割パターンが増える。これに伴いイジング装置における求解回数が増え、階層クラスタリングの実行時間が長くなってしまう。
【０００７】
１つの側面では、本発明は、階層クラスタリングの実行時間を短縮することを目的とする。
【課題を解決するための手段】
【０００８】
１つの実施態様では、複数のノードを含む第１クラスタを、第２クラスタと第３クラスタに分割するときの第１分割候補を、前記複数のノード間の重み値を含むイジング型の評価関数に基づいて算出するイジング装置と、前記イジング装置から、前記第１クラスタに含まれるノード数によって決まる複数の第１分割パターンのそれぞれに対する複数の前記第１分割候補を表す分割候補情報を取得し、複数の前記第１分割候補の前記評価関数の値に基づいて、前記複数の第１分割パターンのそれぞれに対する複数の前記第１分割候補のうちの１つを選択して、前記第１クラスタを前記第２クラスタと前記第３クラスタに分割し、複数の前記第１分割候補のうち非選択の前記第１分割候補の前記分割候補情報を記憶部に記憶し、前記記憶部に記憶した前記分割候補情報に基づいて、前記第２クラスタの第２分割パターンに対応する非選択の前記第１分割候補の有無を判定し、前記第２分割パターンに対応する非選択の前記第１分割候補があると判定した場合、前記第２分割パターンに対応する非選択の前記第１分割候補を含む、前記第２クラスタの第２分割候補のうちの１つを選択して前記第２クラスタを第４クラスタと第５クラスタに分割する、情報処理装置と、を有するデータ処理システムが提供される。
【０００９】
また、１つの実施態様では、プログラムが提供される。
また、１つの実施態様では、データ処理方法が提供される。
【発明の効果】
【００１０】
１つの側面では、本発明は、階層クラスタリングの実行時間を短縮できる。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許