(57)【特許請求の範囲】
【請求項１】
複数のノードを有するグラフデータの入力を受け付ける入力部と、
前記複数のノードをＮ個（Ｎは２以上の整数）の群に分割し、前記Ｎ個の群のそれぞれに、処理を実行する単位であるＮ個のスレッドの各スレッドを割り当てる割当部と、
前記各スレッドで、前記割当部によって割り当てられた群に含まれるノードから所定の順番でノードを選択する選択部と、
前記各スレッドで、前記選択部によってノードが選択されるたびに、前記選択部によって選択されたノードである選択ノードに関する情報を所定の状態に変更する変更部と、
前記各スレッドで、前記変更部によって前記選択ノードに関する情報が変更されるたびに、前記選択ノードに隣接するノードまたはクラスタの中から、前記選択ノードと同じクラスタに分類された場合にクラスタリング処理結果の精度を表すモジュラリティが最大となるノードまたはクラスタである分類先を抽出する抽出部と、
前記各スレッドで、前記抽出部によって前記分類先が抽出されるたびに、前記分類先に関する情報が他スレッドによって前記所定の状態に変更されているか否かを判定し、変更されていないと判定した場合、前記選択ノードと前記分類先を同一のクラスタに分類する分類部と、
前記各スレッドで、前記分類部によって分類されたノードのうち、クラスタが同一である複数のノードを、１つのノードに集約する集約部と、
を有することを特徴とするクラスタリング装置。 
【請求項２】
前記集約部は、前記変更部によって前記選択ノードに関する情報が変更された後、かつ前記抽出部によって前記分類先が抽出される前に、前記選択ノードと、前記選択ノードと分類されたクラスタが同一であるノードとを１つのノードに集約することを特徴とする請求項１に記載のクラスタリング装置。
【請求項３】
前記分類部は、ＣＡＳ命令によって、前記分類先に関する情報が変更されているか否かを判定し、変更されていないと判定した場合、前記選択ノードを前記分類先と同一のクラスタのメンバに追加することで分類を行うことを特徴とする請求項２に記載のクラスタリング装置。
【請求項４】
前記分類部によって前記複数のノードが分類されたクラスタを示す情報を出力する出力部をさらに有することを特徴とする請求項１から３のいずれか１項に記載のクラスタリング装置。
【請求項５】
クラスタリング装置で実行されるクラスタリング方法であって、
複数のノードを有するグラフデータの入力を受け付ける入力工程と、
前記複数のノードをＮ個の群に分割し、前記Ｎ個の群のそれぞれに、処理を実行する単位であるＮ個のスレッドの各スレッドを割り当てる割当工程と、
前記各スレッドで、前記割当工程によって割り当てられた群に含まれるノードから所定の順番でノードを選択する選択工程と、
前記各スレッドで、前記選択工程によってノードが選択されるたびに、前記選択工程によって選択されたノードである選択ノードに関する情報を所定の状態に変更する変更工程と、
前記各スレッドで、前記変更工程によって前記選択ノードに関する情報が変更されるたびに、前記選択ノードに隣接するノードまたはクラスタの中から、前記選択ノードと同じクラスタに分類された場合にクラスタリング処理結果の精度を表すモジュラリティが最大となるノードまたはクラスタである分類先を抽出する抽出工程と、
前記各スレッドで、前記抽出工程によって前記分類先が抽出されるたびに、前記分類先に関する情報が他スレッドによって前記所定の状態に変更されているか否かを判定し、変更されていないと判定した場合、前記選択ノードと前記分類先を同一のクラスタに分類する分類工程と、
前記各スレッドで、前記分類工程によって分類されたノードのうち、クラスタが同一である複数のノードを、１つのノードに集約する集約工程と、
を含んだことを特徴とするクラスタリング方法。
【請求項６】
コンピュータを、請求項１に記載のクラスタリング装置として機能させるためのクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置、クラスタリング方法およびクラスタリングプログラムに関する。
【背景技術】
【０００２】
従来、グラフのクラスタリング手法として、逐次ノード集約によるクラスタリングが知られている（例えば特許文献１参照）。このような逐次ノード集約によるクラスタリングでは、例えば、まず、グラフに含まれる全てのノードとエッジが入力される。そして、任意のノードが１つ選択され、選択されたノードは隣接するノードの１つへ集約される。このとき、集約先のノードとしては、集約によって生じるモジュラリティ向上量を最大化するものが選択される。
【０００３】
また、マルチＣＰＵまたはマルチコアＣＰＵを用いた並列計算機で行われるクラスタリング手法として、グラフ分割による並列クラスタリングが知られている（例えば特許文献２参照）。このようなグラフ分割による並列クラスタリングでは、例えば、まず、グラフは複数の部分グラフに分割される。そして、それぞれの部分グラフは、並列に動作する各スレッドへ割り当てられる。ここで、各スレッドは、割り当てられた部分グラフについてモジュラリティを最大化するような分類を行う。そして、全てのスレッドにおいて分類が完了した後、同じクラスタに分類されたノードは１つのノードに集約される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１３−１５６６９８号公報
【特許文献２】特開２０１４−１６０３３６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のクラスタリング手法には、グラフデータに対し、高速かつ処理結果のモジュラリティが大きいクラスタリングを行うことができない場合があるという問題があった。
【０００６】
例えば、逐次ノード集約によるクラスタリングは、１スレッドで行われるため、複数のスレッドでクラスタリングを行う場合と比べると、大規模グラフのクラスタリングを高速に行うことができない場合がある。
【０００７】
また、例えば、グラフ分割による並列クラスタリングは、分割された複数の部分グラフのそれぞれの中でのモジュラリティを大きくするものであるため、グラフ全体としてのモジュラリティが大きくならない場合がある。仮に、第１のノードと、第２のノードがそれぞれ異なる部分グラフへ分割されてしまった場合、第２のノードが第１のノードに集約された場合に最もモジュラリティが大きくなるとしても、第１のノードと第２のノードが集約されることはない。
【課題を解決するための手段】
【０００８】
本発明のクラスタリング装置は、複数のノードを有するグラフデータの入力を受け付ける入力部と、前記複数のノードをＮ個（Ｎは２以上の整数）の群に分割し、前記Ｎ個の群のそれぞれに、処理を実行する単位であるＮ個のスレッドの各スレッドを割り当てる割当部と、前記各スレッドで、前記割当部によって割り当てられた群に含まれるノードから所定の順番でノードを選択する選択部と、前記各スレッドで、前記選択部によってノードが選択されるたびに、前記選択部によって選択されたノードである選択ノードに関する情報を所定の状態に変更する変更部と、前記各スレッドで、前記変更部によって前記選択ノードに関する情報が変更されるたびに、前記選択ノードに隣接するノードまたはクラスタの中から、前記選択ノードと同じクラスタに分類された場合にクラスタリング処理結果の精度を表すモジュラリティが最大となるノードまたはクラスタである分類先を抽出する抽出部と、前記各スレッドで、前記抽出部によって前記分類先が抽出されるたびに、前記分類先に関する情報が他スレッドによって前記所定の状態に変更されているか否かを判定し、変更されていないと判定した場合、前記選択ノードと前記分類先を同一のクラスタに分類する分類部と、前記各スレッドで、前記分類部によって分類されたノードのうち、クラスタが同一である複数のノードを、１つのノードに集約する集約部と、を有することを特徴とする。
【０００９】
また、本発明のクラスタリング方法は、クラスタリング装置で実行されるクラスタリング方法であって、複数のノードを有するグラフデータの入力を受け付ける入力工程と、前記複数のノードをＮ個の群に分割し、前記Ｎ個の群のそれぞれに、処理を実行する単位であるＮ個のスレッドの各スレッドを割り当てる割当工程と、前記各スレッドで、前記割当工程によって割り当てられた群に含まれるノードから所定の順番でノードを選択する選択工程と、前記各スレッドで、前記選択工程によってノードが選択されるたびに、前記選択工程によって選択されたノードである選択ノードに関する情報を所定の状態に変更する変更工程と、前記各スレッドで、前記変更工程によって前記選択ノードに関する情報が変更されるたびに、前記選択ノードに隣接するノードまたはクラスタの中から、前記選択ノードと同じクラスタに分類された場合にクラスタリング処理結果の精度を表すモジュラリティが最大となるノードまたはクラスタである分類先を抽出する抽出工程と、前記各スレッドで、前記抽出工程によって前記分類先が抽出されるたびに、前記分類先に関する情報が他スレッドによって前記所定の状態に変更されているか否かを判定し、変更されていないと判定した場合、前記選択ノードと前記分類先を同一のクラスタに分類する分類工程と、前記各スレッドで、前記分類工程によって分類されたノードのうち、クラスタが同一である複数のノードを、１つのノードに集約する集約工程と、を含んだことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、グラフデータに対し、高速かつ処理結果のモジュラリティが大きいクラスタリングを行うことができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、第１の実施形態に係るクラスタリング装置の構成の一例を示す図である。
【図２】図２は、ノード群のスレッドへの割り当てについて説明するための図である。
【図３】図３は、ノードの選択およびクラスタの抽出について説明するための図である。
【図４】図４は、ノードの分類およびノードの集約について説明するための図である。
【図５】図５は、第１の実施形態に係るクラスタリング装置の処理の流れの一例を示すフローチャートである。
【図６】図６は、第１の実施形態に係るクラスタリング装置における各スレッドでの処理の流れの一例を示すフローチャートである。
【図７】図７は、クラスタのメンバリストのデータ構造の一例を示す図である。
【図８】図８は、第１の実施形態に係るクラスタリング装置における分類部の処理の流れの一例を示すフローチャートである。
【図９】図９は、モジュラリティが小さいクラスタリングが行われる場合の例について説明する図である。
【図１０】図１０は、プログラムが実行されることにより、クラスタリング装置が実現されるコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１２】
以下に、本願に係るクラスタリング装置、クラスタリング方法およびクラスタリングプログラムの実施形態を図面に基づいて詳細に説明する。なお、この実施形態は本発明を限定するものではない。
【００１３】
［第１の実施形態の構成］
まず、図１を用いて、第１の実施形態に係るクラスタリング装置の構成について説明する。図１は、第１の実施形態に係るクラスタリング装置の構成の一例を示す図である。図１に示すように、クラスタリング装置１０は、入力されたグラフデータ２０に対してクラスタリング処理を行い、クラスタリング結果２１を出力する。ここで、グラフデータ２０は、複数のノード、およびノードごとのエッジに関する情報を表すデータである。また、クラスタリング結果２１は、例えば、グラフデータ２０に含まれるノードごとの分類されたクラスタを表すデータである。また、図１に示すように、クラスタリング装置１０は、入力部１１、出力部１２、制御部１３および記憶部１４を有する。
【００１４】
入力部１１は、グラフデータ２０の入力を受け付ける。例えば、入力部１１は、外部の記憶装置に記憶されているグラフデータ２０を受信することによって入力を受け付けてもよい。この場合、入力部１１は、例えば、ＮＩＣ（Network  Interface  Card）である。また、入力部１１は、ユーザによるグラフデータ２０の入力を受け付けてもよい。この場合、入力部１１は、例えば、マウスやキーボード等の入力装置である。
【００１５】
出力部１２は、クラスタリング結果２１を出力する。出力部１２は、外部の記憶装置にクラスタリング結果２１を送信するようにしてもよい。この場合、出力部１２は、例えば、ＮＩＣである。また、出力部１２は、クラスタリング結果２１を画面に表示するようにしてもよい。この場合、出力部１２は、例えば、ディスプレイ等の表示装置である。
【００１６】
制御部１３は、クラスタリング装置１０を制御する。制御部１３は、例えば、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）等の電子回路や、ＡＳＩＣ（Application  Specific  Integrated  Circuit）、ＦＰＧＡ（Field  Programmable  Gate  Array）等の集積回路である。また、制御部１３は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、内部メモリを用いて各処理を実行する。また、制御部１３は、各種のプログラムが動作することにより各種の処理部として機能する。
【００１７】
また、本実施形態において、制御部１３は、複数のスレッドで処理を実行することで、クラスタリング装置１０を並列計算機として機能させる。例えば、制御部１３は、複数のＣＰＵで構成されるマルチＣＰＵや、複数のコアを有するマルチコアＣＰＵによって実現される。また、制御部１３は、割当部１３１、選択部１３２、変更部１３３、集約部１３４、抽出部１３５および分類部１３６を有する。
【００１８】
割当部１３１は、複数のノードをＮ個（Ｎは２以上の整数）の群に分割し、Ｎ個の群のそれぞれに、処理を実行する単位であるＮ個のスレッドの各スレッドを割り当てる。割当部１３１による処理は、処理全体に要する時間と比べて極めて短い時間で完了するため、割当部１３１は、１つのスレッドで処理を実行してもよい。
【００１９】
例えば、グラフデータ２０に含まれるノードの数がｎ個（ｎは２以上の整数）、スレッドの数がＮ個である場合、割当部１３１は、先頭のｎ／Ｎ個のノードをＶ１群、次のｎ／Ｎ個のノードをＶ２群、というようにノードを分割してもよい。さらに、この場合、割当部１３１は、例えば、Ｖ１群のノードを１個目のスレッド、Ｖ２群のノードを２個目のスレッドというように割り当てる。
【００２０】
ここで、Ｎは、この後のステップで行われる処理の並列度に相当し、一般的にはＣＰＵが持つコア数、すなわち総ハードウェアスレッド数と同一である。また、スレッドが増加するほど、各スレッドに割り当てられるノードの数は少なくなり、各スレッドおよび装置全体における処理時間が短縮される。
【００２１】
図２を用いて、割当部１３１による、ノード群のスレッドへの割り当てについて説明する。図２は、ノード群のスレッドへの割り当てについて説明するための図である。図２に示すように、グラフデータ２０は、ノード１０１〜１０３、２０１〜２０３、３０１〜３０３および４０１〜４０３を有する。また、制御部１３は、スレッドｔ１〜ｔ４の４個のスレッドで処理を行う。このとき、割当部１３１は、例えば、ノード１０１〜１０３をスレッドｔ１に割り当て、ノード２０１〜２０３をスレッドｔ２に割り当て、ノード３０１〜３０３をスレッドｔ３に割り当て、ノード４０１〜４０３をスレッドｔ４に割り当てる。なお、図２に示す通り、各ノード群のノードのそれぞれは、隣接していなくてもよい。
【００２２】
選択部１３２、変更部１３３、集約部１３４、抽出部１３５および分類部１３６は、各スレッドで並列処理を行う。すなわち、例えばスレッドｔ１で選択部１３２、変更部１３３、集約部１３４、抽出部１３５および分類部１３６による処理が行われている間に、スレッドｔ２でも選択部１３２、変更部１３３、集約部１３４、抽出部１３５および分類部１３６による処理が行われる。
【００２３】
各ノードは、分類されるクラスタを識別するラベルが付けられることによって分類される。また、割当部１３１によって各スレッドに割り当てられた時点ではクラスタへの分類は行われていないため、各ノードにはそれぞれ異なるラベルが付けられていることとする。すなわち、各ノードは、１個のノードからなるクラスタに分類されていることになる。
【００２４】
選択部１３２は、各スレッドで、割当部１３１によって割り当てられた群に含まれるノードから所定の順番でノードを選択する。割り当てられたノード群の中に、未選択のノードがある場合、選択部１３２は、ノード群からノードを選択する。選択部１３２がノードを選択する順番は、任意に設定することができる。
【００２５】
変更部１３３は、各スレッドで、選択部１３２によってノードが選択されるたびに、選択部１３２によって選択されたノードである選択ノードに関する情報を所定の状態に変更する。例えば、変更部１３３は、選択部１３２によって選択ノードが分類されているクラスタを、所定の状態、すなわち変更禁止状態にする。変更部１３３は、例えばクラスタを表すデータの所定のフラグをオンにすること等により、当該クラスタが変更禁止であることを示す変更禁止マークを付ける。
【００２６】
集約部１３４は、各スレッドで、分類部１３６によって分類されたノードのうち、クラスタが同一である複数のノードを、１つのノードに集約する。集約部１３４は、例えば、変更部１３３によって選択ノードに関する情報が変更された後、かつ抽出部１３５によって分類先が抽出される前に、選択ノードと、選択ノードと分類されたクラスタが同一であるノードとを１つのノードに集約する。
【００２７】
集約部１３４は、選択ノードが分類されているクラスタに複数のノードが含まれている場合、当該複数のノードを選択ノードに集約する。具体的に、集約部１３４は、当該クラスタの選択ノード以外のノードを削除し、削除したノードのエッジを選択ノードに付け替える。
【００２８】
抽出部１３５は、各スレッドで、変更部１３３によって選択ノードに関する情報が変更されるたびに、選択ノードに隣接するノードまたはクラスタの中から、選択ノードと同じクラスタに分類された場合にクラスタリング処理結果の精度を表すモジュラリティが最大となるノードまたはクラスタである分類先を抽出する。
【００２９】
なお、抽出部１３５は、集約部１３４による処理が行われる場合、ノードの集約が行われた後に処理を実行する。また、抽出部１３５による抽出の対象となる、選択ノードに隣接するノード、および選択ノードに隣接するクラスタに含まれるノードは、選択ノードと同じ群のノードであってもよいし、異なる群のノードであってもよい。
【００３０】
図３を用いて、ノードの選択およびクラスタの抽出について説明する。図３は、ノードの選択およびクラスタの抽出について説明するための図である。図３に示すように、選択ノードがノード１０１である場合、選択ノードに隣接するクラスタは、クラスタｃ１〜ｃ４である。なお、ノード１０２および２０３は、１つのノードから構成されるクラスタｃ３およびｃ５とみなされる。なお、図中のｕが付されたノードは、選択ノードである。
【００３１】
抽出部１３５は、クラスタｃ１〜ｃ４の中から、ノード１０１を同じクラスタとした場合に、最もモジュラリティが大きくなるクラスタを抽出する。このとき、抽出部１３５は、式（１）によって、クラスタｃ１〜ｃ４のそれぞれが１つのノードに集約された場合、当該集約されたノードと選択ノードと同じクラスタに分類された際のモジュラリティの向上量ΔＱ（ｕ，ｖ）を計算することで、結果的に最もモジュラリティが大きくなるクラスタを抽出する。
【００３２】
【数１】
0006638919.tif 000002
【００３３】
ただし、式（１）において、ｕは選択ノード、ｖは隣接するクラスタのいずれかを集約したノードである。例えば、図３の例では、ｕはノード１０１、ｖはクラスタｃ１〜ｃ４のいずれかを集約した１つのノードである。ただし、クラスタｃ３については、ｖは、ノード１０２そのものである。また、ｍは初期状態のグラフのエッジ数、ｗｕｖはノードｕ、ｖ間のエッジの重み、ｄ（ｕ）およびｄ（ｖ）はそれぞれノードｕ、ｖの重み付き次数である。
【００３４】
分類部１３６は、各スレッドで、抽出部１３５によって分類先が抽出されるたびに、分類先に関する情報が他スレッドによって所定の状態に変更されているか否かを判定し、変更されていないと判定した場合、選択ノードと分類先を同一のクラスタに分類する。
【００３５】
分類部１３６は、下記の一連の処理によって分類を行う。まず、抽出部１３５によって抽出された分類先には、他スレッドで実行される変更部１３３によって変更禁止マークが付けられている場合があるため、分類部１３６は、分類先に変更禁止マークが付けられているか否かを判定する。そして、分類部１３６は、分類先に変更禁止マークが付けられていない場合、選択ノードを当該分類先のクラスタのメンバに追加する。そして、分類部１３６は、選択ノードのラベルをメンバとして追加されたクラスタと同じラベルに変更し、分類を完了する。
【００３６】
このとき、分類部１３６は、変更禁止マークが付けられているか否かの判定、および選択ノードのクラスタのメンバへの追加をアトミックな処理によって行う。例えば、分類部１３６は、ＣＡＳ（Compare  And  Swap）命令によって、分類先に関する情報が変更されているか否かを判定し、変更されていないと判定した場合、選択ノードを分類先と同一のクラスタのメンバに追加する。
【００３７】
図４を用いて、ノードの分類およびノードの集約について説明する。図４は、ノードの分類およびノードの集約について説明するための図である。例えば、図４の（ａ）におけるノード２０２、３０１、３０２および４０１〜４０３は、既に選択部１３２によって選択ノードとして選択されたノードである。
【００３８】
図４の（ａ）に示すように、まず、選択部１３２は、ノード１０１を選択ノードとして選択する。そして、変更部１３３は、ノード１０１をクラスタとみなし、変更禁止マークを付ける。このとき、ノード１０１とクラスタが同一であるノードは、ノード１０１以外に存在しないため、集約部１３４は集約を行わない。そして、抽出部１３５は、ノード１０１に隣接するクラスタｃ１〜ｃ４の中から、ノード１０１が同じクラスタに分類された場合に、モジュラリティの向上量が最大となるクラスタを抽出する。図４の（ａ）の例では、抽出部１３５は、クラスタｃ３を抽出することとする。
【００３９】
図４の（ｂ）に示すように、分類部１３６は、クラスタｃ３に変更禁止マークが付けられていない場合、ノード１０１をクラスタｃ３に分類する。次に、図４の（ｃ）に示すように、選択部１３２は、ノード１０２を選択ノードとして選択する。そして、変更部１３３は、ノード１０２のクラスタｃ３に変更禁止マークを付ける。このとき、図４の（ｄ）に示すように、集約部１３４は、クラスタｃ３のノードをノード１０２に集約する。そして、抽出部１３５は、ノード１０２に隣接するクラスタｃ１、ｃ２、ｃ４、ｃ５の中から、ノード１０１が同じクラスタに分類された場合に、モジュラリティの向上量が最大となるクラスタを抽出する。図４の（ｄ）の例では、抽出部１３５は、クラスタｃ４を抽出することとする。
【００４０】
図４の（ｅ）に示すように、分類部１３６は、クラスタｃ４に変更禁止マークが付けられていない場合、ノード１０２をクラスタｃ４に分類する。そして、最終的に、図４の（ｆ）に示すクラスタリング結果が得られる。なお、抽出部１３５によって計算されるモジュラリティの向上量は、０以下になる場合がある。その場合、抽出部１３５は分類先の抽出を行わないため、分類部１３６による選択ノードの分類は行われない。例えば、図４の（ｆ）の例では、ノード１０３が選択された場合に、クラスタｃ４のノード、すなわちノード１０３をクラスタｃ１およびｃ２のいずれに分類したとしても、モジュラリティが向上しないことが考えられる。
【００４１】
［第１の実施形態の処理］
図５を用いて、クラスタリング装置１０の処理の流れについて説明する。図５は、第１の実施形態に係るクラスタリング装置の処理の流れの一例を示すフローチャートである。図５に示すように、クラスタリング装置１０の割当部１３１は、入力されたグラフデータ２０のノードを、Ｎ個のノード群Ｖ１、Ｖ２、…、ＶＮに分割する（ステップＳ１００）。このとき、割当部１３１は、分割したノード群をＮ個のスレッドのそれぞれに割り当てる。
【００４２】
次に、選択部１３２、変更部１３３、集約部１３４、抽出部１３５および分類部１３６は、Ｎ個のノード群の集約処理およびクラスタを示すラベル付けを各スレッドで並列に行う（ステップＳ１１０）。
【００４３】
ここで、図５のステップＳ１１０において、ｉ個目のノード群Ｖｉに対して行われる処理を図６を用いて説明する。図６は、第１の実施形態に係るクラスタリング装置における各スレッドでの処理の流れの一例を示すフローチャートである。図６に示すように、ノード群Ｖｉが空でない場合（ステップＳ２００、Ｙｅｓ）、選択部１３２は、ノード群Ｖｉから任意のノードｕを選択する（ステップＳ２１０）。また、ノード群Ｖｉが空である場合（ステップＳ２００、Ｎｏ）、クラスタリング装置１０は処理を終了する。
【００４４】
そして、変更部１３３は、ノードｕのクラスタＣｕに変更禁止マークを付ける（ステップＳ２２０）。変更禁止マークによって、ノードｕの処理中に他スレッドからクラスタＣｕが変更されてしまうことが防止される。次に、集約部１３４は、クラスタＣｕに含まれるノードをノードｕへ集約する（ステップＳ２３０）。
【００４５】
抽出部１３５は、ノードｕの隣接クラスタの中で最もモジュラリティ向上量が大きい隣接クラスタをＣｖとおく（ステップＳ２４０）。なお、本実施形態では、集約タイミングの遅延により、各ノードにクラスタを示すラベルを付けた直後にノードを集約しないため、隣接クラスタの中には、１つのノードに集約されたノードで構成されるクラスタと、集約されていない複数のノードで構成されるクラスタの両方が含まれる。また、集約されていない複数のノードで構成されるクラスタについては、１つのノードに集約されたものと仮定してモジュラリティの向上量を計算する。
【００４６】
分類部１３６は、ノードｕをクラスタＣｖへ分類したときにモジュラリティが向上するか否かを判定する（ステップＳ２５０）。分類部１３６は、モジュラリティが向上しないと判定した場合（ステップＳ２５０、Ｎｏ）、ノード群Ｖｉからノードｕを削除し（ステップＳ３００）、クラスタＣｕの変更禁止マークを除去し（ステップＳ３１０）、処理をステップＳ２００へ戻す。なお、分類部１３６は、例えば、モジュラリティの向上量が０より大きい場合、モジュラリティが向上すると判定する。
【００４７】
分類部１３６は、モジュラリティが向上すると判定した場合（ステップＳ２５０、Ｙｅｓ）、「クラスタＣｖに変更禁止マークがなければ、ノードｕをクラスタＣｖのメンバに追加」をアトミックに実行する（ステップＳ２６０）。そして、分類部１３６は、アトミックな変更に成功しなかった場合（ステップＳ２７０、Ｎｏ）、クラスタＣｕの変更禁止マークを除去し（ステップＳ３１０）、処理をステップＳ２００へ戻す。なお、アトミックな変更は、他スレッドの処理等により成功しない場合がある。
【００４８】
一方、分類部１３６は、アトミックな変更に成功した場合（ステップＳ２７０、Ｙｅｓ）、ノードｕをクラスタＣｖのノードと同じクラスタに分類するようなラベル付けを行う（ステップＳ２８０）。そして、分類部１３６は、ノード群Ｖｉからノードｕを削除し（ステップＳ２９０）、処理をステップＳ２００へ戻す。その後、ノード群Ｖｉの未選択のノードについて、さらに分類処理が行われる。
【００４９】
ここで、ＣＰＵにおいて、ＣＡＳ命令で書き換え可能なデータの量は、１６バイトまでに限られている場合がある。この場合、ロックを用いることなく、アトミックな処理をＣＡＳ命令によって実現するためには、クラスタのメンバの変更を１６バイト以下の書き換えで実行できるようなデータ構造を採用する必要がある。
【００５０】
そこで、本実施形態では、クラスタのメンバを表すためのデータ構造として、図７に示すような、アトミック操作可能な単方向リスト構造を用いる（参考文献：Timothy  L  Harris.  A  Pragmatic  Implementation  of  Non-blocking  Linked-Lists.  In  Proceedings  of  the  15th  Inter-national  Conference  on  Distributed  Computing,  DISC  '01,pages  300-314,  London,  UK,  2001.  Springer-Verlag.）。図７は、クラスタのメンバリストのデータ構造の一例を示す図である。
【００５１】
図７に示すように、単方向リストの先頭を表すダミー要素（ｈｅａｄ）は、リストの次要素へのポインタ（ｎｅｘｔ）と、変更禁止フラグ（ｉｓ＿ｒｅａｄｏｎｌｙ）とを持つ。また、後続の各リスト要素は、次要素へのポインタと、ノード識別子等任意の情報を持つ。ｈｅａｄはクラスタを表し、後続の各リスト要素は当該クラスタのメンバであるノードを表している。また、変更部１３３は、変更禁止フラグを１にすることで、クラスタに対し変更禁止マークを付ける。
【００５２】
現在、パーソナルコンピュータやサーバ装置で一般的に採用されている、インテル社のｘ８６−６４アーキテクチャを想定すれば、ポインタは８バイトであり、変更禁止フラグは０（変更可）または１（変更禁止）を表せればよいことから、次要素へのポインタと変更禁止フラグを合わせても、クラスタのメンバ変更の際に書き換えられるデータの量は、ＣＡＳで変更可能な１６バイト以下とすることができる。
【００５３】
図７のデータ構造を用いた、図６のステップＳ２６０の処理について、図８を用いて説明する。図８は、第１の実施形態に係るクラスタリング装置における分類部の処理の流れの一例を示すフローチャートである。
【００５４】
図８に示すように、分類部１３６は、ｈｅａｄのコピーを２つ作成し、それぞれを変数ｈｅａｄ＿ｏｌｄおよびｈｅａｄ＿ｎｅｗとおく（ステップＳ４００）。次に、分類部１３６は、新しいリスト要素のメモリ領域を確保し、確保したメモリ領域を変数ｅｌｅｍとおく（ステップＳ４１０）。
【００５５】
分類部１３６は、変数ｈｅａｄ＿ｏｌｄとｈｅａｄ＿ｎｅｗのｉｓ＿ｒｅａｄｏｎｌｙに０を代入し、さらに変数ｈｅａｄ＿ｎｅｗのｎｅｘｔに変数ｅｌｅｍのアドレスを代入する（ステップＳ４２０）。そして、分類部１３６は、変数ｅｌｅｍに、クラスタに追加されるノードのノード識別子等の情報を設定し、さらにｎｅｘｔに変数ｈｅａｄ＿ｏｌｄのｎｅｘｔの値を代入する（ステップＳ４３０）。
【００５６】
ここで、分類部１３６は、「もしｈｅａｄ＝ｈｅａｄ＿ｏｌｄならｈｅａｄ＿ｎｅｗを代入」をＣＡＳ命令でアトミックに実行する（ステップＳ４４０）。このとき、ｈｅａｄ＿ｏｌｄはｈｅａｄのコピーであるため、ｈｅａｄのｉｓ＿ｒｅａｄｏｎｌｙが他スレッドで実行される変更部１３３によって１にされていなければ、ｈｅａｄ＝ｈｅａｄ＿ｏｌｄが成り立つ。一方、ｈｅａｄのｉｓ＿ｒｅａｄｏｎｌｙが他スレッドで実行される変更部１３３によって１にされている場合、ｈｅａｄ＝ｈｅａｄ＿ｏｌｄは成り立たない。
【００５７】
［第１の実施形態の効果］
入力部１１は、複数のノードを有するグラフデータの入力を受け付ける。また、割当部１３１は、複数のノードをＮ個の群に分割し、Ｎ個の群のそれぞれに、処理を実行する単位であるＮ個のスレッドの各スレッドを割り当てる。また、選択部１３２は、各スレッドで、割当部１３１によって割り当てられた群に含まれるノードから所定の順番でノードを選択する。また、変更部１３３は、各スレッドで、選択部１３２によってノードが選択されるたびに、選択部１３２によって選択されたノードである選択ノードに関する情報を所定の状態に変更する。また、抽出部１３５は、各スレッドで、変更部１３３によって選択ノードに関する情報が変更されるたびに、選択ノードに隣接するノードまたはクラスタの中から、選択ノードと同じクラスタに分類された場合にクラスタリング処理結果の精度を表すモジュラリティが最大となるノードまたはクラスタである分類先を抽出する。また、分類部１３６は、各スレッドで、抽出部１３５によって分類先が抽出されるたびに、分類先に関する情報が他スレッドによって所定の状態に変更されているか否かを判定し、変更されていないと判定した場合、選択ノードと分類先を同一のクラスタに分類する。また、集約部１３４は、各スレッドで、分類部１３６によって分類されたノードのうち、クラスタが同一である複数のノードを、１つのノードに集約する。
【００５８】
これにより、グラフデータに対し、高速かつ処理結果のモジュラリティが大きいクラスタリングを行うことができる。すなわち、ノードを複数のノード群に分割し、マルチスレッドによる処理が行われるため、処理が高速になる。また、各ノードの分類先のクラスタは、同一の群のノードで構成されている必要がないため、同一の群の中でのみクラスタリングを行う場合と比べて、モジュラリティが大きくなる。
【００５９】
ここで、図９を用いて、従来のグラフ分割による並列クラスタリングの問題点について説明する。図９は、モジュラリティが小さいクラスタリングが行われる場合の例について説明する図である。図９の（ａ）に示すようなグラフに対してクラスタリングを行う場合、図９の（ｂ）のようなクラスタリング結果となった場合にモジュラリティが大きくなると考えられる。しかしながら、従来の手法により、図９の（ｃ）に示すような部分グラフに群分けがされた場合、図９の（ｄ）のようなモジュラリティの小さいクラスタリング結果が得られる。従来の手法では、例えば、同じ群に含まれるノードｕとノードｖを、他の群のクラスタに含めることができない。
【００６０】
これに対し、本実施形態の抽出部１３５は、群とは無関係に、選択ノードに隣接するノードまたはクラスタの中から分類先を抽出するため、従来の手法と比べてモジュラリティの大きいクラスタリング結果を得ることができる。
【００６１】
また、従来の逐次ノード集約によるクラスタリング、およびグラフ分割による並列クラスタリングを単純に合わせた手法、すなわち、並列処理により群ごとに逐次ノード集約によるクラスタリングを行う手法が考えられる。しかしながら、このような手法には、並列処理を行うスレッドが同じノードに対する処理を行おうとして、衝突が発生するという問題がある。この問題に対して、処理対象のノードにロックをかけておくことが考えられるが、ロックによって同時に処理を進めることができないスレッドが発生し、処理の並列度が低下してしまう。このため、ロックをかける方法は、ＣＰＵのコア数の増加に対する性能向上率、すなわちスケーラビリティが低い。
【００６２】
これに対し、本実施形態の分類部１３６は、処理対象のノードに関する情報が変更されているか否かを判定したうえで変更を確定する楽観的並列処理による処理を行っているため、ロックによる並列度の低下を発生させない。
【００６３】
また、集約部１３４は、変更部１３３によって選択ノードに関する情報が変更された後、かつ抽出部１３５によって分類先が抽出される前に、選択ノードと、選択ノードと分類されたクラスタが同一であるノードとを１つのノードに集約する。このように、集約部１３４は、分類部１３６による分類の直後ではなく、分類が行われたノードが選択ノードとして選択された際に集約を行っている。これによって、分類部１３６におけるアトミックな処理による処理量を少なくすることができる。
【００６４】
また、分類部１３６は、ＣＡＳ命令によって、分類先に関する情報が変更されているか否かを判定し、変更されていないと判定した場合、選択ノードを分類先と同一のクラスタのメンバに追加することで分類を行う。このように、分類部１３６は、ＣＡＳ命令によって、アトミックな処理を実現することができる。また、分類部１３６はノードの集約を行わないため、書き換え可能なデータが１６バイトまでに限定されているＣＡＳ命令であっても処理の実行が可能となる。
【００６５】
出力部１２は、分類部１３６によって複数のノードが分類されたクラスタを示す情報を出力する。このように、クラスタリング結果に例えばエッジ等に関する情報を含めないようにすることで、クラスタリング結果のデータ量を小さくすることができる。
【００６６】
［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００６７】
また、本実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００６８】
［プログラム］
一実施形態として、クラスタリング装置は、パッケージソフトウェアやオンラインソフトウェアとして上記のクラスタリングを実行するクラスタリングプログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記のクラスタリングプログラムを情報処理装置に実行させることにより、情報処理装置をクラスタリング装置として機能させることができる。ここで言う情報処理装置には、デスクトップ型またはノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal  Handyphone  System）等の移動体通信端末、さらには、ＰＤＡ（Personal  Digital  Assistant）等のスレート端末等がその範疇に含まれる。
【００６９】
また、クラスタリング装置は、ユーザが使用する端末装置をクライアントとし、当該クライアントに上記のクラスタリングに関するサービスを提供するサーバ装置として実装することもできる。例えば、クラスタリング装置は、グラフデータを入力とし、クラスタリング結果を出力とするクラスタリングサービスを提供するサーバ装置として実装される。この場合、クラスタリング装置は、Ｗｅｂサーバとして実装することとしてもよいし、アウトソーシングによって上記のクラスタリングに関するサービスを提供するクラウドとして実装することとしてもかまわない。
【００７０】
図１０は、プログラムが実行されることにより、クラスタリング装置が実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。また、ＣＰＵ１０２０は、複数のスレッドで処理の実行が可能なＣＰＵである。ＣＰＵ１０２０は、例えば、複数のＣＰＵで構成されるマルチＣＰＵや、複数のコアを有するマルチコアＣＰＵである。
【００７１】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【００７２】
ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、クラスタリング装置の各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、クラスタリング装置における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid  State  Drive）により代替されてもよい。
【００７３】
また、上述した実施形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【００７４】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００７５】
１０  クラスタリング装置
１１  入力部
１２  出力部
１３  制御部
１４  記憶部
２０  グラフデータ
２１  クラスタリング結果
１０１、１０２、１０３、２０１、２０２、２０３、３０１、３０２、３０３、４０１、４０２、４０３  ノード
１３１  割当部
１３２  選択部
１３３  変更部
１３４  集約部
１３５  抽出部
１３６  分類部
ｃ１、ｃ２、ｃ３、ｃ４、ｃ５  クラスタ
ｔ１、ｔ２、ｔ３、ｔ４  スレッド
【図１】
0006638919.tif 000003
【図２】
0006638919.tif 000004
【図３】
0006638919.tif 000005
【図４】
0006638919.tif 000006
【図５】
0006638919.tif 000007
【図６】
0006638919.tif 000008
【図７】
0006638919.tif 000009
【図８】
0006638919.tif 000010
【図９】
0006638919.tif 000011
【図１０】
0006638919.tif 000012