(57)【特許請求の範囲】
【請求項１】
グラフデータをクラスタリングして出力するクラスタリング装置であって、
グラフデータのクラスタリング処理対象ノードを選択し、クラスタリングを行った中間結果を生成し、該中間結果を集約し、集約されたクラスタに対して繰り返しクラスタリング処理を行う制御手段と、を有し、
前記制御手段は、
前記グラフデータに含まれるクラスタ間を接続するエッジ数が少ない順にノードを選択する、または、クラスタを構成するノード数が少ない順にノードを選択し、前記クラスタリング処理対象とする処理対象選択手段を含む
ことを特徴とするクラスタリング装置。
【請求項２】
グラフデータをクラスタリングして出力するクラスタリング装置におけるクラスタリング方法であって、
前記クラスタリング装置が、
グラフデータのクラスタリング処理対象ノードを選択し、クラスタリングを行った中間結果を生成し、該中間結果を集約し、集約されたクラスタに対して繰り返しクラスタリング処理を行う際に、
前記グラフデータに含まれるクラスタ間を接続するエッジ数が少ない順にノードを選択する、または、クラスタを構成するノード数が少ない順にノードを選択し、前記クラスタリング処理対象とする処理対象選択ステップを行う
ことを特徴とするクラスタリング方法。
【請求項３】
コンピュータを、
請求項１記載のクラスタリング装置の各手段として機能させるためのクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置及び方法及びプログラムに係り、特に、グラフに含まれるエッジデータを用いてグラフに含まれるノードデータをクラスタリングするためのクラスタリング装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
グラフクラスタリング処理として、グラフデータが入力されると、グラフに含まれる全てのエッジデータを用いてクラスタリング処理対象ノードを任意の順番で選択し、クラスタリングの中間結果を生成し、集約する。さらに、集約されたクラスタに対して繰り返しクラスタリング処理を行うことにより、クラスタサイズの均一化及び処理対象ノードの削減が可能な技術がある（例えば、非特許文献1参照）。
【０００３】
図１は、クラスタリング装置の構成を示し、図２は、従来のクラスタリング装置におけるクラスタリングのフローチャートである。
【０００４】
クラスタリング装置２１０は、入力部２１１、制御部２１２、出力部２１３から構成される。入力部２１１は、グラフデータ記憶装置２００から読み込んだグラフデータを主記憶装置上に展開し、制御部２１２は、図２に示すフローの処理を行い、出力部２１３に渡す。出力部２１３は、制御部２１２により得られたクラスタリング結果を任意の装置、例えば、クラスタリング結果記憶装置２２０等に出力する。
【０００５】
以下に制御部２１２における処理について説明する。
【０００６】
まず、制御部２１２は、図３（Ａ）に示すようなグラフデータが入力されると、乱数を用いてグラフデータから任意のノードを一つ選択し、そのノードに隣接するノードの一覧を主記憶装置上の隣接ノードキューに挿入する（ステップ１００）。
【０００７】
次に、隣接ノードキューの中から乱数を用いて隣接ノードを選択し、当該隣接ノードキューから当該ノードを削除する（ステップ１１０）。
【０００８】
ステップ１００で選択されたノードとステップ１１０において選択された隣接ノードの２つのノードを同じクラスタに分類した際のクラスタリング精度向上量を算出し、隣接ノードとクラスタリング精度向上量からなる組（｛隣接ノード：クラスタリング精度向上量｝）を生成し、主記憶装置上の処理済キューに挿入する（ステップ１２０）。クラスタリング精度向上量は、非特許文献１に示されるように、以下の式で求められる。
【０００９】
［定義１］クラスタリング精度向上量ΔQを以下のように計算する。
【００１０】
【数１】
0005600693.tif 000002
ただし、ΔQはクラスタリング精度向上量、eijはクラスタｉとクラスタjの間に存在するエッジの数、ｍはグラフ内に存在する全エッジ数、Cはクラスタの集合である。
【００１１】
隣接ノードキューに隣接ノードが存在する場合はステップ１１０の処理に戻り、存在しない場合は、クラスタリング精度向上量が最大となる隣接ノードを主記憶装置上の処理済キューから選択し、ノードと隣接ノードに対して同一のクラスタラベルを付与し、主記憶装置上のクラスタ対応表に格納する。なお、クラスタラベル名については任意のクラスタラベルを付与するものとする。主記憶装置上のクラスタ対応表は、ノードａ、隣接ノードｂであった場合は、ハッシュマップの形式で｛クラスタラベル：ノードａ，ノードｂ｝の組が格納される（ステップ１４０）。
【００１２】
次に、主記憶装置上に展開していたグラフデータを取得し、主記憶装置上のクラスタ対応表を読み込み、ノード同士のペアでグラフデータ全体のクラスタリング精度を算出する。グラフデータ全体のクラスタリング精度は、非特許文献１に示されるように、以下の式で求められる。
【００１３】
［定義２］クラスタリング精度Qを以下のように算出する。
【００１４】
【数２】
0005600693.tif 000003
により求められる。
【００１５】
そして、前回当該処理を実行したときのクラスタリング精度との差分を求める。なお、初回実行時は前回のクラスタリング精度を０と見做して判定するものとする。上記のステップ１００からステップ１５０の処理イメージを図３（Ｂ）に示す。差分がある場合、つまり、ノード同士のペアでクラスタリング精度向上の余地がある場合は（ステップ１５０、No）、ステップ１００に戻る。一方、当該差分がない場合、つまり、ノード同士のペアでクラスタリング精度向上の余地がない場合には（ステップ１５０,Yes）、各クラスタに対して、図３（Ｃ）に示すように、クラスタに含まれるノードとエッジを1ノードに集約し、主記憶装置のグラフデータを更新する（ステップ１６０）。さらに、クラスタ同士のペアでグラフデータ全体のクラスタリング精度を算出し、前回の当該処理を実行した時の差分を判定する。なお、初回実行時は前回のクラスタリング精度を０と見做して判定するものとする。差分がある場合は（ステップ１７０、No）ステップ１００に戻り、差分がない場合は（ステップ１７０,Yes）最終的なクラスタ対応表をクラスタリング結果記憶装置２２０に出力して当該処理を終了する。
【００１６】
上記の従来の技術は、クラスタサイズの均一化と、処理に利用するエッジ数・ノード数の削減により、中間結果の集約による処理量を削減することが可能であり、1億ノード規模のグラフのクラスタリングを2時間半程度で処理可能である。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Louvain method [Vincent D Blondel, Journal of Statistical Mechanics: Theory and Experiment, 2008年10月9日]
【発明の概要】
【発明が解決しようとする課題】
【００１８】
しかしながら、上記従来のクラスタリング処理時におけるノードの選択順序が定義されておらず、選択順序に依存して処理時間が大幅に劣化する。そのため、不要な計算が発生し、1数億ノードを超える規模のグラフのクラスタリングを短時間で終えることができないという問題がある。
【００１９】
本発明は、上記の点に鑑みなされたもので、グラフクラスタリング処理の高速化が可能なクラスタリング装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２０】
上記の課題を解決するため、本発明（請求項１）は、グラフデータをクラスタリングして出力するクラスタリング装置であって、
グラフデータのクラスタリング処理対象ノードを選択し、クラスタリングを行った中間結果を生成し、該中間結果を集約し、集約されたクラスタに対して繰り返しクラスタリング処理を行う制御手段と、を有し、
前記制御手段は、
前記グラフデータに含まれるクラスタ間を接続するエッジ数が少ない順にノードを選択する、または、クラスタを構成するノード数が少ない順にノードを選択し、前記クラスタリング処理対象とする処理対象選択手段を含む。
【発明の効果】
【００２３】
本発明によれば、大規模なグラフデータを対象としたクラスタリングにおいて、クラスタ間を接続するエッジの本数順に従ったノード、クラスタを構成するノード数順に従ったノードを選択することにより、クラスタリング処理実行時に参照するエッジ数及びノード数を削減することができるため、クラスタリング処理の高速化が可能となる。
【図面の簡単な説明】
【００２４】
【図１】クラスタリング装置の構成図である。
【図２】従来のクラスタリング装置におけるクラスタリングのフローチャートである。
【図３】従来技術の集約イメージである。
【図４】本発明のクラスタリング装置のハードウェア構成図である。
【図５】本発明の第１の実施の形態におけるクラスタリング処理のフローチャートである。
【図６】本発明の第１の実施の形態におけるグラフデータ及びそのスパースベクトルの例である。
【図７】本発明の第２の実施の形態におけるクラスタリング処理のフローチャートである。
【図８】本発明の第２の実施の形態におけるノードとクラスタの対応表の例である。
【発明を実施するための形態】
【００２５】
以下、図面と共に本発明の実施の形態を説明する。
【００２６】
以下の実施の形態では、図１の構成及び図２のフローチャートをベースとして説明する。
【００２７】
図４は、本発明のクラスタリング装置のハードウェア構成を示す。クラスタリング装置として用いられるコンピュータは、ＣＰＵ１００，主記憶装置１１０、二次記憶装置１２０、入出力装置１３０から構成され、図１における制御部２１２は、ＣＰＵ１００によって実現される。また、入力部２１１より入力されたグラフデータは主記憶装置１１０上の隣接ノードキューに展開される。また、処理済みキューも主記憶装置１１０上に配置される。グラフデータ記憶装置２００及びクラスタリング結果記憶装置２２０は、二次記憶装置１２０に含まれるハードディスクやフラッシュメモリドライブ等の記録媒体である。また、入力部２１１、出力部２１３は、入出力装置１３０に含まれる。
【００２８】
以下の実施の形態におけるクラスタリング装置の構成は、図１と同様であるが、制御部２１２の動作が異なる。
【００２９】
［第1の実施の形態］
グラフのクラスタリング処理に必要となる処理時間はグラフに含まれる計算対象のノード数に依存するため、計算対象のノード数を削減できればグラフのクラスタリング処理を高速化できる。そのために、本実施の形態では、入力されたグラフデータのうち、クラスタリング結果が自明なノードを集約する。
【００３０】
図５は、本発明の第1の実施の形態におけるクラスタリング処理のフローチャートである。従来の図２のステップ１００の処理に代えて、本実施の形態では、ステップ２００に示すように、制御部２１２において、エッジ数の少ないノードをクラスタリング処理対象として選択する。入力されるグラフデータはノード間のエッジで表現されたものであり（図６（Ｂ））、グラフデータを主記憶装置１１０に展開する際に、スパースベクトルという形式（図６（Ｃ））で保持することにより、各ノードのエッジ数をカウントすることが可能であるので、その中からエッジ数が最小のノードをサーチして選択する。サーチ方法としては、例えば、主記憶装置１１０上のスパースベクトルを順に参照し、最もエッジ数の少ないノードを選択する、または、エッジ数を事前に算出して各種ソート手法を用いる等の方法がある。次に、選択されたノードに隣接するノードの一覧を隣接ノードキューに挿入する。ステップ２１０以降の処理は図２と同様であるので、その説明を省略する。
【００３１】
これにより、クラスタリング処理時に参照が必要となるエッジ数を減らし、処理に時間のかかるエッジ数の多いクラスタとノードの計算を省くことができるため、クラスタリング処理を高速化することができる。
【００３２】
［第２の実施の形態］
グラフのクラスタリング処理に必要となる処理時間はグラフに含まれる計算対象のノード数とエッジ数に依存するため、計算対象のノード数を削減できればグラフのクラスタリング処理を高速化できる。そのために、本実施の形態では、クラスタの持つノード数が少ない順に処理対象ノードとして選択することにより、クラスタリング処理実行時に参照するノード数を削減する。
【００３３】
図７は、本発明の第２の実施の形態におけるクラスタリング処理のフローチャートである。従来の図２のステップ１００の処理に代えて、本実施の形態では、ステップ３００において、制御部２１２は、クラスタを構成するノード数の少ないノードを計算対象として１つ選択する。具体的には、図８に示すように、主記憶装置１１０のノードとクラスタが対応付けられた対応表を任意のサーチ方法によりサーチする。サーチ方法としては、例えば、対応表を順に参照し、最もノード数の少ないクラスタを選択する方法や、ノード数を事前に算出して各種ソート手法を用いることが可能である。そして、選択されたノードに隣接するノードの一覧を主記憶装置１１０の隣接ノードキューに挿入する。以降の処理は図２と同様であるので、その説明を省略する。
【００３４】
なお、上記の第１、第２の実施の形態における図５、図７の制御部の動作をプログラムとして構築し、クラスタリング装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００３５】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００３６】
１００  ＣＰＵ
１１０  主記憶装置
１２０  二次記憶装置
１３０  入出力装置
２００  グラフデータ記憶装置
２１０  クラスタリング装置
２１１  入力部
２１２  制御部
２１３  出力部
２２０  クラスタリング結果記憶装置
【図１】
0005600693.tif 000004
【図２】
0005600693.tif 000005
【図３】
0005600693.tif 000006
【図４】
0005600693.tif 000007
【図５】
0005600693.tif 000008
【図６】
0005600693.tif 000009
【図７】
0005600693.tif 000010
【図８】
0005600693.tif 000011