(57)【要約】【課題】グラフデータのクラスタリング処理時間を低減する。【解決手段】クラスタリング装置は、入力されたグラフデータから隣接ノードの集合Γを選択し、この集合Γから選択したＮ個の隣接ノードのデータを、ＳＩＭＤレジスタ上に展開し、展開したＮ個の隣接ノードのデータそれぞれに対して、ＳＩＭＤ命令を用いてクラスタリング精度向上量を計算する処理を、集合Γに含まれるすべての隣接ノードに対し実行する。但し、Ｎは、制御部のＳＩＭＤレジスタサイズＲ、前記グラフデータのデータ型のサイズＴに対し、Ｎ＝[Ｒ／Ｔ]となる値とする。【選択図】図５
2014160337.tif 000002
【特許請求の範囲】
【請求項１】
入力されたグラフデータのクラスタリング処理対象ノードのノードを任意の順番で選択し、
前記選択したノードの隣接ノードの集合Γを前記グラフデータの中から取得し、
前記取得した集合Γの隣接ノードの中から任意のＮ個の隣接ノードを選択し、
前記選択したＮ個の隣接ノードのデータを、ＳＩＭＤ（Single  Instruction  Multiple Data）レジスタ上に展開し、
前記展開したＮ個の隣接ノードのデータそれぞれに対して、ＳＩＭＤ命令を用いてクラスタリング精度向上量を計算する処理を、
前記集合Γに含まれるすべての隣接ノードに対し実行し、
前記計算したクラスタリング精度向上量が最大となった前記隣接ノードと、前記選択したノードとを同じクラスタに分類するようラベル付けを行う制御部を備えることを特徴とするクラスタリング装置。
但し、前記Ｎは、前記制御部のＳＩＭＤレジスタサイズＲ、前記グラフデータのデータ型のサイズＴに対し、Ｎ＝[Ｒ／Ｔ]となる値とする。
【請求項２】
前記展開したＮ個の隣接ノードのデータそれぞれに対して、ＳＩＭＤ命令を用いてクラスタリング精度向上量を計算する処理は、
前記制御部が、
前記ＳＩＭＤレジスタ上で、前記選択したノードと前記選択したＮ個の隣接ノードとのペアそれぞれについてのクラスタリング精度向上量を並列に計算する処理であることを特徴とする請求項１に記載のクラスタリング装置。
【請求項３】
クラスタリング装置の制御部が、
入力されたグラフデータのクラスタリング処理対象ノードのノードを任意の順番で選択するステップと、
前記選択したノードの隣接ノードの集合Γを前記グラフデータの中から取得するステップと、
前記取得した集合Γの隣接ノードの中から任意のＮ個の隣接ノードを選択するステップと、
前記選択したＮ個の隣接ノードのデータを、ＳＩＭＤレジスタ上に展開するステップと、
前記展開したＮ個の隣接ノードのデータそれぞれに対して、ＳＩＭＤ命令を用いてクラスタリング精度向上量を計算する処理ステップとを、
前記集合Γに含まれるすべての隣接ノードに対し実行するステップと、
前記計算したクラスタリング精度向上量が最大となった前記隣接ノードと、前記選択したノードとを同じクラスタに分類するようラベル付けを行うステップとを実行することを特徴とするクラスタリング処理方法。
【請求項４】
クラスタリング装置に、
入力されたグラフデータのクラスタリング処理対象ノードのノードを任意の順番で選択するステップと、
前記選択したノードの隣接ノードの集合Γを前記グラフデータの中から取得するステップと、
前記取得した集合Γの隣接ノードの中から任意のＮ個の隣接ノードを選択するステップと、
前記選択したＮ個の隣接ノードのデータを、ＳＩＭＤレジスタ上に展開するステップと、
前記展開したＮ個の隣接ノードのデータそれぞれに対して、ＳＩＭＤ命令を用いてクラスタリング精度向上量を計算する処理ステップとを、
前記集合Γに含まれるすべての隣接ノードに対し実行するステップと、
前記計算したクラスタリング精度向上量が最大となった前記隣接ノードと、前記選択したノードとを同じクラスタに分類するようラベル付けを行うステップとを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置、クラスタリング処理方法およびそのプログラムに関する。
【背景技術】
【０００２】
従来のグラフデータのクラスタリング技術として、クラスタリング装置（コンピュータ）が、入力されたグラフデータに含まれるすべてのエッジデータを用いてクラスタリング処理対象ノードを任意の順番で選択し、クラスタリングの中間結果を生成し、集約する。さらに、このクラスタリング装置が、集約されたクラスタに対して繰り返しクラスタリング処理を行うことにより、クラスタサイズの均一化および処理対象ノードの削減を行う技術がある（例えば、非特許文献１参照）。
【０００３】
図１に示すように、クラスタリング装置２１０は、入力部２１１、制御部２１２および出力部２１３から構成される。入力部２１１は、グラフデータ記憶装置２００から読み込んだグラフデータを、クラスタリング装置２１０の備える主記憶装置（図４参照）上に展開し、制御部２１２は、図２に示すフローの処理を行い、出力部２１３に渡す。出力部２１３は、制御部２１２により得られたクラスタリング結果を任意の装置、例えば、クラスタリング結果記憶装置２２０等に出力する。
【０００４】
以下に制御部２１２における処理について説明する。
【０００５】
まず、制御部２１２は、図３（Ａ）に示すようなグラフデータが入力されると、乱数を用いてグラフデータから任意のノードを１つ選択し、その選択したノードに隣接するノードの一覧を主記憶装置上の隣接ノードキューに挿入する（Ｓ１００）。
【０００６】
次に、制御部２１２は、隣接ノードキューの中から乱数を用いて隣接ノードを選択し、当該隣接ノードキューから当該ノードを削除する（Ｓ１１０）。
【０００７】
制御部２１２は、Ｓ１００で選択されたノードとＳ１１０において選択された隣接ノードの２つのノードを同じクラスタに分類した際のクラスタリング精度向上量を計算し、隣接ノードとクラスタリング精度向上量とからなる組（｛隣接ノード：クラスタリング精度向上量｝）を生成し、主記憶装置上の処理済キューに挿入する（Ｓ１２０）。クラスタリング精度向上量は、非特許文献１に示されるように、以下の式で求められる。
【０００８】
［定義１］クラスタリング精度向上量ΔＱを以下のように計算する。
【０００９】
【数１】
2014160337.tif 000003
【００１０】
ただし、ΔＱはクラスタリング精度向上量、eijはクラスタｉとクラスタjの間に存在するエッジの数、ｍはグラフ内に存在する全エッジ数、Ｃはクラスタの集合である。
【００１１】
隣接ノードキューに隣接ノードが存在する場合、つまり、ノードの持つ隣接ノードにまだ処理していないノードがあれば（Ｓ１３０のＮｏ）、Ｓ１１０の処理に戻る。一方、隣接ノードキューに隣接ノードが存在しない場合、つまり、制御部２１２が、ノードの持つ隣接ノードをすべて処理した場合（Ｓ１３０のＹｅｓ）、クラスタリング精度向上量が最大となる隣接ノードを主記憶装置上の処理済キューから選択し、ノードと隣接ノードに対して同一のクラスタラベルを付与し、主記憶装置上のクラスタ対応表に格納する。つまり、制御部２１２は、ノードを最もクラスタリング精度向上量の高い隣接ノードと同じクラスタに分類するようにラベル付けを行う（Ｓ１４０）。なお、クラスタラベル名については任意のクラスタラベルを付与するものとする。主記憶装置上のクラスタ対応表には、ノードａの隣接ノードｂであった場合は、ハッシュマップの形式で｛クラスタラベル：ノードａ，ノードｂ｝の組が格納される。
【００１２】
次に、制御部２１２は、ノード同士のペアでクラスタリング精度向上の余地があるか否かを判定する（Ｓ１５０）、つまり、まず、制御部２１２は、主記憶装置上に展開していたグラフデータを取得し、主記憶装置上のクラスタ対応表を読み込み、ノード同士のペアでグラフデータ全体のクラスタリング精度を計算する。グラフデータ全体のクラスタリング精度は、非特許文献１に示されるように、以下の式で求められる。
【００１３】
［定義２］クラスタリング精度Ｑを以下のように計算する。
【００１４】
【数２】
2014160337.tif 000004
【００１５】
そして、制御部２１２は、前回当該処理を実行したときのクラスタリング精度との差分を求める。なお、初回実行時は前回のクラスタリング精度を０とみなして判定するものとする。上記のＳ１００からＳ１５０の処理イメージを図３（Ｂ）に示す。差分がある場合、つまり、ノード同士のペアでクラスタリング精度向上の余地がある場合は（Ｓ１５０のＮｏ）、Ｓ１００に戻る。一方、当該差分がない場合、つまり、ノード同士のペアでクラスタリング精度向上の余地がない場合には（Ｓ１５０のＹｅｓ）、制御部２１２は、各クラスタに対して、図３（Ｃ）に示すように、クラスタに含まれるノードとエッジを１ノードに集約し、主記憶装置のグラフデータを更新する（Ｓ１６０）。さらに、制御部２１２は、クラスタ（つまり集約されたノード）同士のペアでグラフデータ全体のクラスタリング精度を計算し、前回の当該処理を実行した時の差分を判定する。つまり、制御部２１２は、クラスタ同士のペアでクラスタリング精度向上の余地があるか否かを判定する（Ｓ１７０）。なお、制御部２１２は、初回実行時においては前回のクラスタリング精度を０とみなして判定するものとする。差分がある場合は（Ｓ１７０のＮｏ）、Ｓ１００に戻り、差分がない場合は（Ｓ１７０のＹｅｓ）、制御部２１２は、最終的なクラスタ対応表をクラスタリング結果記憶装置２２０に出力して当該処理を終了する。
【００１６】
上記の従来の技術は、クラスタサイズの均一化と、処理に利用するエッジ数・ノード数
の削減により、中間結果の集約による処理量を削減することが可能であり、１億ノード規
模のグラフデータのクラスタリング処理を２時間半程度で実行可能である。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Louvain  method  [Vincent  D  Blondel,  Journal  of  Statistical  Mechanics:  Theory  and  Experiment,  2008年10月9日]
【発明の概要】
【発明が解決しようとする課題】
【００１８】
しかし、前記した従来技術には次のような問題点がある。すなわち、従来のクラスタリング装置は、大量のグラフデータを１つのＣＰＵ（Central  Processing  Unit）の１スレッド上の非並列環境下でクラスタリング処理を実行するため、すべてのデータを順に処理する必要がある。このため、グラフデータが増加するにつれてクラスタリング処理時間が激増する。例えば、クラスタリング処理時間は、グラフのノード数に対して指数関数的に増加し、グラフのエッジ数に対しては線形的に増加する。そこで、本発明は、前記した問題を解決し、グラフデータのクラスタリング処理時間を低減することを目的とする。
【課題を解決するための手段】
【００１９】
前記した課題を解決するため、本発明は、入力されたグラフデータのクラスタリング処理対象ノードのノードを任意の順番で選択し、前記選択したノードの隣接ノードの集合Γを前記グラフデータの中から取得し、前記取得した集合Γの隣接ノードの中から任意のＮ個の隣接ノードを選択し、前記選択したＮ個の隣接ノードのデータを、ＳＩＭＤ（Single  Instruction  Multiple  Data）レジスタ上に展開し、前記展開したＮ個の隣接ノードのデータそれぞれに対して、ＳＩＭＤ命令を用いてクラスタリング精度向上量を計算する処理を、前記集合Γに含まれるすべての隣接ノードに対し実行し、前記計算したクラスタリング精度向上量が最大となった前記隣接ノードと、前記選択したノードとを同じクラスタに分類するようラベル付けを行う制御部を備えることを特徴とするクラスタリング装置とした。但し、前記Ｎは、前記制御部のＳＩＭＤレジスタサイズＲ、前記グラフデータのデータ型のサイズＴに対し、Ｎ＝[Ｒ／Ｔ]となる値とする。このような発明によれば、クラスタリング装置がクラスタリング処理を行う際に、ＳＩＭＤ命令を用いるので、クラスタリング処理の性能を最大でＮ倍に向上させ、クラスタリング処理時間を低減することができる。なお、クラスタリング精度向上量は、[定義１]に記載した数式により計算される。
【発明の効果】
【００２０】
本発明によれば、グラフデータのクラスタリング処理時間を低減することができる。
【図面の簡単な説明】
【００２１】
【図１】図１は、従来のクラスタリング装置の構成を示す図である。
【図２】図２は、従来のクラスタリング装置におけるクラスタリングの処理手順を示すフローチャートである。
【図３】図３は、従来のクラスタリングにおける集約イメージである。
【図４】図４は、本実施の形態のクラスタリング装置のハードウェア構成図である。
【図５】図５は、図４のクラスタリング装置の処理手順を示すフローチャートである。
【図６】図６は、図５のＳ２１０の詳細を示すフローチャートである。
【発明を実施するための形態】
【００２２】
以下、図面を参照しながら、本発明の実施の形態を説明する。以下に説明する実施の形態はあくまで一例であり、本発明は、他のさまざまな形態でも実施が可能である。以下、前記した図１の構成および図２のフローチャートをベースとして説明する。
【００２３】
クラスタリング装置２１０として用いられるコンピュータは、ＣＰＵ（Central  Processing  Unit）１００、主記憶装置１１０（メモリ）、二次記憶装置１２０（ＨＤＤ（Hard  Disk  Drive）、ＳＳＤ（Solid  State  Drive）等）および入出力装置１３０から構成される。なお、図１における制御部２１２は、ＣＰＵ１００によって実現される。また、入力部２１１により入力されたグラフデータ内の隣接ノードは主記憶装置１１０上の隣接ノードキューに展開される。さらに、処理済みキューも主記憶装置１１０上に配置される。グラフデータ記憶装置２００およびクラスタリング結果記憶装置２２０は、二次記憶装置１２０に含まれるＨＤＤやＳＳＤ等の記録媒体である。また、入力部２１１および出力部２１３は、入出力装置１３０に含まれる。
【００２４】
以下の実施の形態におけるクラスタリング装置２１０の構成は、図１と同様であるが、制御部２１２に用いられるＣＰＵ１００はＳＩＭＤ（Single  Instruction  Multiple  Data）命令を実行可能なＣＰＵであることを特徴とする。
【００２５】
このクラスタリング装置２１０の機能を実現するプログラムが、入出力装置１３０から二次記憶装置１２０にインストールされ、起動されると、このプログラムは、ＣＰＵ１００によりＳＩＭＤ命令を利用し、並列に実行される。つまり、クラスタリング装置２１０は、クラスタリング処理を実行する際、主記憶装置１１０上にグラフデータを展開し、ＳＩＭＤ命令により実行する。
【００２６】
なお、クラスタリング装置２１０の機能を実現するためのプログラムに係るプログラムモジュールやプログラムデータは、プログラムに係るプログラムモジュールやプログラムデータは、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶され、ネットワークインタフェースを介してＣＰＵ１００によって読み出されてもよい。
【００２７】
以下に制御部２１２（ＣＰＵ１００）における処理について図５のフローチャートを用いて説明する。なお、以下の説明において、クラスタリング精度向上量は、前記した[定義１]で説明した計算式により計算されるものとする。
【００２８】
まず、ＣＰＵ１００は、図３（Ａ）に示すようなグラフデータが入力されると、乱数を用いてグラフデータから任意のノードｕを１つ選択する（Ｓ２００）。
【００２９】
次に、ＣＰＵ１００は、ノードｕに対しＳＩＭＤ命令を用いてクラスタリング処理を並列実行する（Ｓ２１０）。このＳ２１０の詳細は、図６を用いて後記する。
【００３０】
Ｓ２２０にて、これ以上クラスタリング精度の向上の余地がないと判定された場合、つまり、ノード同士のペア（Ｓ２１０で選択したノードとその隣接ノードとのペア）でクラスタリング精度の向上の余地がないと判定された場合（Ｓ２２０のＹｅｓ）、ＣＰＵ１００はこれらのノードを同じクラスタに属するノードを１ノードに集約する（Ｓ２３０）。最後に、クラスタ同士（つまり集約されたノード）のペアでクラスタリング精度の向上の余地がないことが確認されると（Ｓ２４０のＹｅｓ）、ＣＰＵ１００は、処理を終了する。
【００３１】
なお、Ｓ２２０およびＳ２４０において、クラスタリング精度の向上の余地がまだあると判定された場合（Ｓ２００のＮｏ、Ｓ２４０のＮｏ）、Ｓ２００へ戻る。
【００３２】
Ｓ２１０の詳細を、図６のフローチャートを用いて説明する。まず、ＣＰＵ１００は、Ｓ２１０において、入力されたグラフデータの中から、Ｓ２００で選択されたノードｕの隣接ノードの集合Γを取得する（Ｓ２１１）。
【００３３】
次に、ＣＰＵ１００は、隣接ノードの集合Γから任意のＮ個のノードを選択する（Ｓ２１２）。なお、このＮは、ＣＰＵ１００が用いるＣＰＵ性能に依存する。このＮは、ＣＰＵ１００のＳＩＭＤレジスタサイズＲ、グラフデータのデータ型のサイズＴに対して、Ｎ＝[Ｒ／Ｔ]とする。
【００３４】
その後、ＣＰＵ１００は、ＳＩＭＤレジスタ上に、Ｓ２１２で選択したＮ個の隣接ノードを展開する（Ｓ２１３）。そして、ＣＰＵ１００は、ＳＩＭＤレジスタ上のデータに対してＳＩＭＤ命令を用いてＮ個の隣接ノードに対してクラスタリング精度向上量を並列に計算する。つまり、ＣＰＵ１００は、ＳＩＭＤレジスタ上でＳ２００のノードｕとＳ２１２で選択したＮ個の隣接ノードとの間のクラスタリング精度向上量を並列に計算する（Ｓ２１４）。
【００３５】
そして、ＣＰＵ１００は、ＳＩＭＤレジスタ上から、クラスタリング精度向上量が最大の隣接ノードと、その隣接ノードとの間のクラスタリング精度向上量（向上量）を取得し（Ｓ２１５）、その取得した向上量が、集合Γに含まれるノードの中で最も大きければ、つまり、主記憶装置１１０上に保持された向上量（最大精度向上量）よりも大きければ（Ｓ２１６のＮｏ）、主記憶装置１１０上の最大精度向上量と向上量最大ノードとを更新する（Ｓ２１７）。つまり、ＣＰＵ１００は、主記憶装置１１０に記憶された最大精度向上量を、Ｓ２１５で取得した向上量の値で更新し、向上量最大ノードを、この向上量が最大である隣接ノードとして更新する。そして、Ｓ２１８へ進む。
【００３６】
一方、ＣＰＵ１００は、Ｓ２１５で取得した向上量が、主記憶装置１１０上に記憶された最大精度向上量以下であり（Ｓ２１６のＹｅｓ）、集合Γに未処理のノードがないと判定すると（Ｓ２１８のＹｅｓ）、Ｓ２００で選択したノードｕと、主記憶装置１１０上に保持された向上量最大ノードとを同じクラスタに分類するようにラベル付けを行い（Ｓ２１９）、Ｓ２１０の処理を終了する。一方、Ｓ２１８において未処理のノードがある場合（Ｓ２１８のＮｏ）、Ｓ２１３へ戻る。
【００３７】
このようにクラスタリング装置２１０はグラフデータのクラスタリング処理においてＳＩＭＤ命令を用いるので、クラスタリング処理時間を最大でＮ倍程度向上させ、クラスタリング処理時間を低減できる。
【００３８】
なお、このクラスタリング装置２１０におけるクラスタリング処理性能はＣＰＵ１００のＳＩＭＤレジスタサイズに依存するが、2012年12月現在、一般に普及しているＣＰＵ１００のＳＩＭＤレジスタサイズは128bit、グラフデータのデータ型は32bitであることから、2012年12月の時点でも４倍の性能向上が見込める。
【符号の説明】
【００３９】
１００  ＣＰＵ
１１０  主記憶装置
１２０  二次記憶装置
１３０  入出力装置
２００  グラフデータ記憶装置
２１０  クラスタリング装置
２１１  入力部
２１２  制御部
２１３  出力部
２２０  クラスタリング結果記憶装置
【図１】
2014160337.tif 000005
【図２】
2014160337.tif 000006
【図３】
2014160337.tif 000007
【図４】
2014160337.tif 000008
【図５】
2014160337.tif 000009
【図６】
2014160337.tif 000010