(57)【特許請求の範囲】
【請求項１】
グラフデータをクラスタリングして出力するクラスタリング装置であって、
前記グラフデータのクラスタリング処理対象ノードを任意の順番で選択し、クラスタリングを行った中間結果を生成し、該中間結果を集約し、集約されたクラスタに対して繰り返しクラスタリング処理を行う制御手段を有し、
前記制御手段は、
グラフデータに含まれるエッジを１本しか持たないノードを、該ノードと隣接するノードと同一のクラスタとみなし、１つのノードに集約する第１の集約手段と、
前記クラスタリング処理において、複数のノードが同一のクラスタとなることが決定した時点で、同一クラスタとなる全てのノードを１つのノードに集約する第２の集約手段と、
前記第１の集約手段と前記第２の集約手段を繰り返し行う第３の集約手段と、
を含むことを特徴とするクラスタリング装置。
【請求項２】
前記同一クラスタに含まれるノードを１つのノードに集約する際に、ノード同士のペアのみを利用してクラスタリング精度が更に向上するか否かを判定する手段を含む
請求項１記載のクラスタリング装置。
【請求項３】
グラフデータをクラスタリングして出力するクラスタリング装置におけるクラスタリング方法であって、
前記クラスタリング装置が、
前記グラフデータのクラスタリング処理対象ノードを任意の順番で選択し、クラスタリングを行った中間結果を生成し、該中間結果を集約し、集約されたクラスタに対して繰り返しクラスタリング処理を行う際に、
グラフデータに含まれるエッジを１本しか持たないノードを、該ノードと隣接するノードと同一のクラスタとみなし、１つのノードに集約する第１の集約ステップと、
前記クラスタリング処理において、複数のノードが同一のクラスタとなることが決定した時点で、同一クラスタとなる全てのノードを１つのノードに集約する第２の集約ステップと、
前記第１の集約ステップと前記第２の集約ステップを繰り返し行う第３の集約ステップと、
を行うことを特徴とするクラスタリング方法。
【請求項４】
前記同一クラスタに含まれるノードを１つのノードに集約する際に、ノード同士のペアのみを利用してクラスタリング精度が更に向上するか否かを判定する
請求項３記載のクラスタリング方法。
【請求項５】
コンピュータを、
請求項１または２に記載のクラスタリング装置の各手段として機能させるためのクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置及び方法及びプログラムに係り、特に、グラフに含まれるエッジデータを用いてグラフに含まれるノードデータをクラスタリングするためのクラスタリング装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
グラフクラスタリング処理として、グラフデータが入力されると、グラフに含まれる全てのエッジデータを用いてクラスタリング処理対象ノードを任意の順番で選択し、クラスタリングの中間結果を生成し、集約する。さらに、集約されたクラスタに対して繰り返しクラスタリング処理を行うことにより、クラスタサイズの均一化及び処理対象ノードの削減が可能な技術がある（例えば、非特許文献1参照）。
【０００３】
図１は、クラスタリング装置の構成を示し、図２は、従来のクラスタリング装置におけるクラスタリングのフローチャートである。
【０００４】
クラスタリング装置２１０は、入力部２１１、制御部２１２、出力部２１３から構成される。入力部２１１は、グラフデータ記憶装置２００から読み込んだグラフデータを主記憶装置上に展開し、制御部２１２は、図２に示すフローの処理を行い、出力部２１３に渡す。出力部２１３は、制御部２１２により得られたクラスタリング結果を任意の装置、例えば、クラスタリング結果記憶装置２２０等に出力する。
【０００５】
以下に制御部２１２における処理について説明する。
【０００６】
まず、制御部２１２は、図３（Ａ）に示すようなグラフデータが入力されると、乱数を用いてグラフデータから任意のノードを一つ選択し、そのノードに隣接するノードの一覧を主記憶装置上の隣接ノードキューに挿入する（ステップ１００）。
【０００７】
次に、隣接ノードキューの中から乱数を用いて隣接ノードを選択し、当該隣接ノードキューから当該ノードを削除する（ステップ１１０）。
【０００８】
ステップ１００で選択されたノードとステップ１１０において選択された隣接ノードの２つのノードを同じクラスタに分類した際のクラスタリング精度向上量を算出し、隣接ノードとクラスタリング精度向上量からなる組（｛隣接ノード：クラスタリング精度向上量｝）を生成し、主記憶装置上の処理済キューに挿入する（ステップ１２０）。クラスタリング精度向上量は、非特許文献１に示されるように、以下の式で求められる。
【０００９】
［定義１］クラスタリング精度向上量ΔQを以下のように計算する。
【００１０】
【数１】
0005600694.tif 000002
ただし、ΔQはクラスタリング精度向上量、eijはクラスタｉとクラスタjの間に存在するエッジの数、ｍはグラフ内に存在する全エッジ数、Cはクラスタの集合である。
【００１１】
隣接ノードキューに隣接ノードが存在する場合はステップ１１０の処理に戻り、存在しない場合は、クラスタリング精度向上量が最大となる隣接ノードを主記憶装置上の処理済キューから選択し、ノードと隣接ノードに対して同一のクラスタラベルを付与し、主記憶装置上のクラスタ対応表に格納する。なお、クラスタラベル名については任意のクラスタラベルを付与するものとする。主記憶装置上のクラスタ対応表には、ノードａ、隣接ノードｂであった場合は、ハッシュマップの形式で｛クラスタラベル：ノードａ，ノードｂ｝の組が格納される（ステップ１４０）。
【００１２】
次に、主記憶装置上に展開していたグラフデータを取得し、主記憶装置上のクラスタ対応表を読み込み、ノード同士のペアでグラフデータ全体のクラスタリング精度を算出する。グラフデータ全体のクラスタリング精度は、非特許文献１に示されるように、以下の式で求められる。
【００１３】
［定義２］クラスタリング精度Qを以下のように算出する。
【００１４】
【数２】
0005600694.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の実施の形態におけるクラスタリング処理のフローチャートであり、図７は、当該フローチャートの処理を適用した場合の集約イメージを示す。図２のフローチャートに、図２のステップ１００の前に、ステップ２００として、制御部２１２において、上記のようにクラスタリング結果が自明となるノードに隣接ノードと同じクラスタラベルを付与し、主記憶装置１１０上のクラスタ対応表に格納する。当該ステップ２００を実行した時点で図７（Ｂ）に示すように集約される。当該処理以外は、図２と同様の処理であるので、その説明を省略する。エッジ数が１のノードと隣接ノードを１ノードに集約することで、最終的に図７（Ｄ）に示すように計算対象のノード数を削減することができる。
【００３４】
［第２の実施の形態］
グラフのクラスタリング処理に必要となる処理時間は、グラフに含まれる計算対象のノード数に依存するため、計算対象のノード数を削減できればグラフのクラスタリング処理を高速化できる。
【００３５】
本実施の形態では、従来技術においてグラフに含まれる全ノードのクラスタリングが終了した後に実行されていた同じクラスタに含まれるノードの集約処理を、図８に示すように、２つのノードが同じクラスタに分類するようにラベル付けされた時点で、ノードを逐次的に1つのノードに集約し、クラスタリング処理の最中にグラフに含まれる計算対象のノード数を削減することにより、処理が経過するにつれて参照するノード数を減らすことができるため、クラスタリング処理を高速化することができる。
【００３６】
本実施の形態におけるクラスタリング装置の構成は、従来の図1の構成と同様であるが、制御部２１２の処理が異なる。
【００３７】
図９は、本発明の第２の実施の形態におけるクラスタリング処理のフローチャートであり、図１０は、当該フローチャートの処理を適用した場合の集約イメージを示す。
【００３８】
本実施の形態では、図２のステップ１６０の代わりに、ステップ３４０において、前述の図２のステップ１２０と同様の方法でクラスタリング精度向上量を算出し、クラスタリング精度向上量が最大となる隣接ノードを選択し、当該ノードと隣接ノードに対して同一のクラスタラベルを付与し、主記憶装置１１０上のクラスタ対応表（ハッシュマップ｛クラスタラベル：ノードａ，ノードｂ｝）に格納する。
【００３９】
クラスタ対応表を参照し、同じクラスタにラベル付けされた２つのノードを１つのノードに集約することで、計算対象のノード数を削減する。これにより、クラスタ同士のペアでクラスタリング精度向上の余地がないかを判定するのではなく、ノード同士のペアで判定を行うことになるため、図２のステップ１７０の処理は不要となる。その他の処理は図２の処理と同様であるので、その説明を省略する。
【００４０】
［第３の実施の形態］
本実施の形態におけるクラスタリング装置は、前述の第１の実施の形態と第２の実施の形態を複合させた処理を行う。
【００４１】
第１の実施の形態と同様に、グラフのクラスタリング処理に必要となる処理時間はグラフに含まれる計算対象のノード数に依存するため、計算対象のノード数を削減できればグラフのクラスタリング処理を高速化できる。
【００４２】
図１１は、本発明の第３の実施の形態におけるクラスタリング処理のフローチャートであり、図１２は、当該フローチャートの処理を適用した場合の集約イメージを示す。。
【００４３】
第１の実施の形態と同様に、制御部２１２は、ステップ４００により、グラフに含まれるエッジ数が１本のノードに隣接ノードと同じクラスタラベルを付与し、クラスタ対応表（ハッシュマップ｛クラスタラベル：ノードａ，ノードｂ｝）に格納する。エッジ数が１本のノードと隣接するノードを１つのノードに集約し、グラフに含まれる計算対象のノード数を削減する。以降、第１の実施の形態と同様にステップ４５０までの処理を行い、ステップ４６０において、第２の実施の形態のステップ３４０と同様に、同一クラスタにラベル付けされたノードを逐次的に１ノードに集約し、グラフに含まれる計算対象のノード数を削減する。当該ステップ４６０におけるノード数の集約及び削減により、グラフ中のエッジ数が１本のノードが存在するようになるため、ステップ４００の処理を再び適用可能となり、グラフに含まれる計算対象のノード数を削減できる。これは、図１３に示すように、あるノードＡの隣接ノードが全て同一クラスタへと含まれている場合、当該ステップ４６０におけるノード数の集約を行うことにより、隣接ノードは全て１ノードへ集約される。したがって、集約されたノードからはノードＡに対してのみエッジが張られることとなるため、エッジ数が１本のノードが存在することになる。
【００４４】
以上のように、ステップ４００とステップ４６０を併用することにより、ステップ４００の処理を繰り返し適用することが可能となり、グラフに含まれる計算対象のノード数が減り、クラスタリング処理を高速化することができる。
【００４５】
なお、本実施の形態においても同一クラスタと見做される２つのノードを１つのノードに集約することで、グラフ中に複数ノードから構成されるクラスタが含まれなくなるため、クラスタ同士のペアでクラスタリング精度向上の余地を判断する必要がなくなり、図２のステップ１７０の処理を削除することができる。
【００４６】
なお、上記の第１〜第３の実施の形態における図６、図９、図１１の制御部の動作をプログラムとして構築し、クラスタリング装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００４７】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００４８】
１００  ＣＰＵ
１１０  主記憶装置
１２０  二次記憶装置
１３０  入出力装置
２００  グラフデータ記憶装置
２１０  クラスタリング装置
２１１  入力部
２１２  制御部
２１３  出力部
２２０  クラスタリング結果記憶装置
【図１】
0005600694.tif 000004
【図２】
0005600694.tif 000005
【図３】
0005600694.tif 000006
【図４】
0005600694.tif 000007
【図５】
0005600694.tif 000008
【図６】
0005600694.tif 000009
【図７】
0005600694.tif 000010
【図８】
0005600694.tif 000011
【図９】
0005600694.tif 000012
【図１０】
0005600694.tif 000013
【図１１】
0005600694.tif 000014
【図１２】
0005600694.tif 000015
【図１３】
0005600694.tif 000016