(57)【要約】【課題】ソフトウェアを扱いやすい単位に分割すること。【解決手段】ソフトウェア分割装置１００は、ソフトウェアの構成要素群であるエンティティ群から、処理対象のエンティティ集合を選択したことに応じて、処理対象のエンティティ集合を複数のクラスタに分割する。ソフトウェア分割装置１００は、分割した複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えているか否かを判断する。ソフトウェア分割装置１００は、クラスタ内のエンティティ数がエンティティ上限数を超えていることに応じて、当該クラスタ内のエンティティ集合を処理対象のエンティティ集合として選択する。【選択図】図１
2015179452.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
ソフトウェアの構成要素群であるエンティティ群から処理対象のエンティティ集合を選択したことに応じて、前記エンティティ群のエンティティ間の依存関係により特定される当該依存関係に関する重みに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、前記処理対象のエンティティ集合を複数のクラスタに分割し、
分割した前記複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えていることに応じて、前記クラスタ内のエンティティ集合を前記処理対象のエンティティ集合として選択する、
処理を実行させることを特徴とするソフトウェア分割プログラム。
【請求項２】
前記コンピュータに、
分割した前記複数のクラスタのクラスタ数が、予め記憶されたクラスタ上限数を超えていることに応じて、前記複数のクラスタに属するエンティティ間の依存関係に関する重みに基づいて、前記複数のクラスタのクラスタ間の依存関係に関する重みを算出し、
算出した前記複数のクラスタのクラスタ間の依存関係に関する重みに基づいて、前記クラスタ数よりも分割後のクラスタ数が少なくなるように、前記複数のクラスタを、同一クラスタ内のクラスタ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように複数のクラスタに分割する、
処理を実行させることを特徴とする請求項１に記載のソフトウェア分割プログラム。
【請求項３】
前記コンピュータに、
同一クラスタ内のクラスタ間の依存関係に関する重みの合計が当該合計の期待値よりも大きい場合に高くなる目的関数に含まれる、前記目的関数の値を減少させるペナルティに寄与するパラメータの値を、前記ペナルティへの寄与が減少するように変更する処理を実行させ、
前記複数のクラスタを分割する処理は、
前記複数のクラスタを、前記複数のクラスタのクラスタ間の依存関係に関する重みに基づいて、変更した前記パラメータの値を含む前記目的関数を最大化するように複数のクラスタに分割することを特徴とする請求項２に記載のソフトウェア分割プログラム。
【請求項４】
前記コンピュータに、
算出した前記複数のクラスタのクラスタ間の依存関係に関する重みを、前記複数のクラスタのうちの同一クラスタ間の依存関係に関する重みが相対的に減少するように補正し、
前記複数のクラスタを分割する処理は、
補正した前記複数のクラスタのクラスタ間の依存関係に関する重みに基づいて、前記複数のクラスタを、同一クラスタ内のクラスタ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように複数のクラスタに分割することを特徴とする請求項２に記載のソフトウェア分割プログラム。
【請求項５】
ソフトウェアの構成要素群であるエンティティ群から処理対象のエンティティ集合を選択したことに応じて、前記エンティティ群のエンティティ間の依存関係により特定される当該依存関係に関する重みに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、前記処理対象のエンティティ集合を複数のクラスタに分割し、分割した前記複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えていることに応じて、前記クラスタ内のエンティティ集合を前記処理対象のエンティティ集合として選択する制御部、
を有することを特徴とするソフトウェア分割装置。
【請求項６】
コンピュータが、
ソフトウェアの構成要素群であるエンティティ群から処理対象のエンティティ集合を選択したことに応じて、前記エンティティ群のエンティティ間の依存関係により特定される当該依存関係に関する重みに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、前記処理対象のエンティティ集合を複数のクラスタに分割し、
分割した前記複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えていることに応じて、前記クラスタ内のエンティティ集合を前記処理対象のエンティティ集合として選択する、
処理を実行することを特徴とするソフトウェア分割方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソフトウェア分割プログラム、ソフトウェア分割装置およびソフトウェア分割方法に関する。
【背景技術】
【０００２】
ソフトウェアを開発・改良・保守するためにはソフトウェアの理解が重要となる。ソフトウェアは大規模になると、その構造は複雑なものとなり、その把握は容易ではない。複雑なソフトウェアでも、ソフトウェアを小規模で扱いやすい単位に分割することができれば、ソフトウェアを直感的かつ容易に理解できるようになる。このため、ソフトウェアを理解が容易な程度に小規模な部分集合に分割することが求められる。
【０００３】
関連する先行文献としては、ソフトウェアを構成するエンティティ群を、関係元のエンティティと関係先のエンティティとを対応付けた対応情報により特定される依存関係に関する重みに基づいて、複数のクラスタに分割する技術がある。また、グラフのクラスタリングの良さを示す尺度であるモジュラリティ評価関数を用いて、モジュラリティ評価関数が最大となるクラスタリングを貪欲法にて探索する技術がある。
【０００４】
また、ソフトウェアの分割に関する技術ではないが、最上位階層でのクラスタの最大個数をユーザに設定させ、その設定に基づき、蓄積された知識群を知識クラスタに仕分ける技術がある。また、総クラスタ数が指定値となるとともに各クラスタの所属画像枚数が上限枚数以下となるように、分類対象画像をクラスタに分類する技術がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１３−１４８９８７号公報
【特許文献２】特開２００３−０４４４８５号公報
【特許文献３】特開２０１２−０４８６４１号公報
【非特許文献】
【０００６】
【非特許文献１】Ｍ．Ｅ．Ｊ．Ｎｅｗｍａｎ（２００４）  “Ｆａｓｔ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｄｅｔｅｃｔｉｎｇ  ｃｏｍｍｕｎｉｔｙ  ｓｔｒｕｃｔｕｒｅ  ｉｎ  ｎｅｔｗｏｒｋｓ”  Ｐｈｙｓｉｃａｌ  Ｒｅｖｉｅｗ  Ｅ６９（６）：０６６１３３
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来技術によれば、ソフトウェアの規模が大きくなると、ソフトウェアを扱いやすい単位に分割することが困難である。例えば、ソースファイルの数が２０００本を超えるようなソフトウェアでは、分割されるソースファイルの部分集合が５０本を超えることがあり、ソフトウェアを分割しても人間による解釈が困難な場合がある。
【０００８】
一つの側面では、本発明は、ソフトウェアを扱いやすい単位に分割することができるソフトウェア分割プログラム、ソフトウェア分割装置およびソフトウェア分割方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一側面によれば、ソフトウェアの構成要素群であるエンティティ群から処理対象のエンティティ集合を選択したことに応じて、前記エンティティ群のエンティティ間の依存関係により特定される当該依存関係に関する重みに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、前記処理対象のエンティティ集合を複数のクラスタに分割し、分割した前記複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えていることに応じて、前記クラスタ内のエンティティ集合を前記処理対象のエンティティ集合として選択するソフトウェア分割プログラム、ソフトウェア分割装置およびソフトウェア分割方法が提案される。
【発明の効果】
【００１０】
本発明の一態様によれば、ソフトウェアを扱いやすい単位に分割することができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】図１は、実施の形態１にかかるソフトウェア分割方法の一実施例を示す説明図である。
【図２】図２は、改善不能なクラスタのグラフ構造の一例を示す説明図である。
【図３】図３は、ソフトウェア分割装置１００のハードウェア構成例を示すブロック図である。
【図４】図４は、実施の形態１にかかるソフトウェア分割装置１００の機能的構成例を示すブロック図である。
【図５】図５は、クラスタ粒度基準情報４２０の具体例を示す説明図である。
【図６】図６は、ソフトウェアＳＷのグラフ表現例を示す説明図である。
【図７】図７は、ソフトウェアＳＷのソースコード例を示す説明図である。
【図８】図８は、関係グラフ情報４３０の具体例を示す説明図である。
【図９】図９は、クラスタリングの処理過程の一例を示す説明図である。
【図１０】図１０は、統合前の分割結果の具体例を示す説明図である。
【図１１】図１１は、ソフトウェアＳＷの階層構造例を示す説明図（その１）である。
【図１２】図１２は、ソフトウェアＳＷの階層構造例を示す説明図（その２）である。
【図１３】図１３は、統合後の分割結果の具体例を示す説明図である。
【図１４】図１４は、実施の形態１にかかるソフトウェア分割装置１００のソフトウェア分割処理手順の一例を示すフローチャートである。
【図１５】図１５は、関係抽出処理の具体的処理手順の一例を示すフローチャートである。
【図１６】図１６は、重み算出処理の具体的処理手順の一例を示すフローチャートである。
【図１７】図１７は、クラスタリング処理の具体的処理手順の一例を示すフローチャートである。
【図１８】図１８は、重み付き有向モジュラリティ最大化処理の具体的処理手順の一例を示すフローチャートである。
【図１９】図１９は、統合処理の具体的処理手順の一例を示すフローチャートである。
【図２０】図２０は、実施の形態２にかかるソフトウェア分割方法の一実施例を示す説明図である。
【図２１】図２１は、多階層の分割例を示す説明図である。
【図２２】図２２は、実施の形態２にかかるソフトウェア分割装置１００の機能的構成例を示すブロック図である。
【図２３】図２３は、処理対象のクラスタ集合についての関係グラフ情報Ｒの具体例を示す説明図である。
【図２４】図２４は、処理対象のクラスタ集合のグラフ表現例を示す説明図である。
【図２５】図２５は、実施の形態２にかかるソフトウェア分割装置１００のソフトウェア分割処理手順の一例を示すフローチャート（その１）である。
【図２６】図２６は、実施の形態２にかかるソフトウェア分割装置１００のソフトウェア分割処理手順の一例を示すフローチャート（その２）である。
【図２７】図２７は、関係グラフ変換処理の具体的処理手順の一例を示すフローチャート（その１）である。
【図２８】図２８は、関係グラフ変換処理の具体的処理手順の一例を示すフローチャート（その２）である。
【図２９】図２９は、第２統合処理の具体的処理手順の一例を示すフローチャートである。
【図３０】図３０は、ソフトウェア分割例を示す説明図である。
【発明を実施するための形態】
【００１２】
以下に図面を参照して、本発明にかかるソフトウェア分割プログラム、ソフトウェア分割装置およびソフトウェア分割方法の実施の形態を詳細に説明する。
【００１３】
（実施の形態１）
図１は、実施の形態１にかかるソフトウェア分割方法の一実施例を示す説明図である。図１において、ソフトウェア分割装置１００は、ソフトウェアを分割するコンピュータである。ソフトウェアは、分割対象となるコンピュータプログラムであり、コンピュータを動作させる命令、手順などをコンピュータが理解できる形式で記述したものである。
【００１４】
ソフトウェアは、例えば、ソフトウェアの構成要素であるエンティティを頂点とし、エンティティ間の依存関係を有向辺とする有向グラフ構造により表現することができる。以下の説明では、有向辺を単に「辺」と略す。また、有向グラフ構造を単に「グラフ」と略す。
【００１５】
エンティティは、例えば、コンポーネント、モジュール、ソースコード、クラス、関数、データベース、ファイルなどである。エンティティ間の依存関係は、例えば、コンポーネント、モジュール、ソースコード、クラス、関数などの呼び出し関係、継承関係、包含関係やデータアクセス関係などの関係である。
【００１６】
ソフトウェアを開発・改良・保守するためにはソフトウェアの理解が重要となる一方で、ソフトウェアが大規模になればなるほど、ソフトウェアの構造は複雑なものとなる。このため、ソフトウェアを直感的かつ容易に理解できるように、ソフトウェアを扱いやすい小規模な単位に分割することが行われる場合がある。
【００１７】
ソフトウェアの分割とは、例えば、グラフを部分グラフに分割することである。グラフから分割された各部分グラフに属する頂点のエンティティの集合はクラスタと呼ばれる。すなわち、ソフトウェアの分割とは、ソフトウェアの構成要素であるエンティティの集合に対して、それらが属するクラスタの集合を求めることである。
【００１８】
ところが、ソフトウェアの規模が大きくなると、ソフトウェアを複数のクラスタ（部分グラフ）に分割しても、クラスタ内のエンティティ数が多すぎて、人間による解釈が困難なものとなる場合がある。例えば、ソースファイル（クラス）の数が数千本を超えるような大規模ソフトウェアでは、クラスタ内のエンティティ数が５０を超えることがあり、それを人間が理解するのは困難である。
【００１９】
また、クラスタ内のエンティティ数を抑えるために、ソフトウェアを複数のクラスタに分割した後に、エンティティ数が多すぎて解釈が困難なクラスタから、エンティティ数が少ないクラスタにエンティティを移動することが考えられる。しかしながら、エンティティ数が少ないクラスタが存在しなければ、クラスタ間でエンティティを移動することができない。
【００２０】
さらに、クラスタ間でエンティティを移動するということは、ソフトウェアの分割結果を変更するものとなる。このため、たとえ最適なクラスタリングアルゴリズムでソフトウェアを分割したとしても、その分割結果を変更すると、最適ではない分割結果となり、適正な分割を得るという目的に対して著しい品質の低下を招いてしまう。
【００２１】
そこで、実施の形態１では、ソフトウェア分割装置１００は、ソフトウェアを分割して得られるクラスタ内のエンティティ数が、予め決められたエンティティ上限数以下となるまで、クラスタ内のエンティティ集合を、一つの新たなソフトウェアとみなして、ソフトウェアの分割を再帰的に繰り返す。これにより、ソフトウェアを人間が理解できる程度の小規模な部分集合に分割する。以下、ソフトウェア分割装置１００のソフトウェア分割処理例について説明する。
【００２２】
（１）ソフトウェア分割装置１００は、ソフトウェアの構成要素群であるエンティティ群から、処理対象のエンティティ集合を選択したことに応じて、処理対象のエンティティ集合を複数のクラスタに分割する。ここで、ソフトウェア分割装置１００のソフトウェア分割は、例えば、以下の性質（ｉ）〜（ｉｉｉ）を有する。
【００２３】
（ｉ）ソフトウェア分割は、エンティティの集合であるソフトウェアにおいて、ソフトウェアの処理の本筋となるエンティティや依存関係を重視してエンティティをグループ化することにより実行される。
（ｉｉ）ソフトウェア分割は、ユーティリティ関数のような本質的ではなく理解の妨げとなるエンティティや依存関係を軽視し、必要ならば分割されたグループから外すように実行される。
（ｉｉｉ）ただし、ソフトウェア分割は、一見軽視されるようなエンティティであっても、分割されたグループを特徴付けるようなエンティティならば、当該グループに包含させるように実行される。
【００２４】
具体的には、例えば、ソフトウェア分割装置１００は、エンティティ間の依存関係に関する重みに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、処理対象のエンティティ集合を複数のクラスタに分割する。
【００２５】
ここで、エンティティ間の依存関係に関する重みとは、エンティティ間の依存関係において、関係元エンティティが役割を果たすために、その依存関係がどれだけ本質的であるかを示す度合いである。役割とは、ソフトウェアが実現する機能やタスク、業務などのことである。
【００２６】
エンティティ間の依存関係に関する重みは、エンティティ群のエンティティ間の依存関係により特定され、グラフの頂点であるエンティティ間をつなぐ辺の重みとして用いられる。なお、エンティティ間の依存関係に基づく当該依存関係に関する重みの算出例については後述する。
【００２７】
すなわち、ソフトウェア分割装置１００は、上述した性質（ｉ）〜（ｉｉｉ）を満たすために、クラスタ内の辺の重みの合計がその期待値より大きくなるようにクラスタリングを行う。性質（ｉ）〜（ｉｉｉ）を満たせば、クラスタを特徴付けるエンティティは、そのクラスタ内に含まれることになる。
【００２８】
図１の例では、分割対象となるソフトウェアＳＷ（１００００本のソースコード群）が、１００個のクラスタＣ１〜Ｃ１００に分割されている。また、各クラスタＣ１〜Ｃ１００内のエンティティ数（ソースコード数）は、１００（本）である。
【００２９】
（２）ソフトウェア分割装置１００は、分割した複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えているか否かを判断する。ここで、エンティティ上限数は、予め任意に設定されてソフトウェア分割装置１００に記憶される。例えば、エンティティ上限数は、ソフトウェアを分析する者のスキルやソフトウェアの管理しやすさなどを考慮して、クラスタ内のエンティティ数がエンティティ上限数を超えると、そのクラスタについての人間による解釈が困難なものとなる値に設定される。
【００３０】
図１の例では、エンティティ上限数が「５０」に設定されている場合を想定する。この場合、ソフトウェア分割装置１００は、クラスタＣ１〜Ｃ１００のすべてがエンティティ上限数を超えていると判断する。
【００３１】
（３）ソフトウェア分割装置１００は、クラスタ内のエンティティ数がエンティティ上限数を超えていることに応じて、当該クラスタ内のエンティティ集合を処理対象のエンティティ集合として選択する。そして、ソフトウェア分割装置１００は、処理対象のエンティティ集合を複数のクラスタに分割する。
【００３２】
すなわち、ソフトウェア分割装置１００は、エンティティ上限数を超えるクラスタを、一つの新たなソフトウェアとみなして、再度クラスタリングを行う。以降、ソフトウェア分割装置１００は、例えば、エンティティ上限数を超えるクラスタがなくなるまで、上記（１）〜（３）の一連の処理を繰り返す。
【００３３】
例えば、エンティティ上限数を超えているクラスタＣ１を例に挙げると、ソフトウェア分割装置１００は、クラスタＣ１内のエンティティ集合（１００本のソースコード）を処理対象のエンティティ集合として選択する。そして、ソフトウェア分割装置１００は、クラスタＣ１内のエンティティ集合（１００本のソースコード）を複数のクラスタに分割する。
【００３４】
この結果、図１の例では、クラスタＣ１内の１００本のソースコードが、１０個のクラスタＣ１０１〜Ｃ１１０に分割されている。また、各クラスタＣ１０１〜Ｃ１１０内のエンティティ数（ソースコード数）は、１０（本）である。これにより、クラスタＣ１を親クラスタとする下位階層の分割が得られ、クラスタの階層構造が形成される。
【００３５】
このように、ソフトウェア分割装置１００によれば、ソフトウェアＳＷを分割して得られるクラスタ内のエンティティ数がエンティティ上限数以下となるまで、クラスタ内のエンティティ集合を、一つの新たなソフトウェアとみなして、ソフトウェアの分割を再帰的に繰り返すことができる。
【００３６】
これにより、ソフトウェアＳＷの分割に階層構造を導入して、ソフトウェアＳＷを人間が理解できる程度の小規模な部分集合に分割することができる。例えば、ソフトウェアＳＷがクラスタＣ１〜Ｃ１００に分割され、各クラスタＣ１〜Ｃ１００が複数の小クラスタ（例えば、クラスタＣ１０１〜Ｃ１１０）に分割され、各小クラスタがエンティティを複数個格納するといった、クラスタのレベルが多階層となるような入れ子構造でソフトウェアの分割を行うことができるようになる。また、上述した性質（ｉ）〜（ｉｉｉ）を有するクラスタリングアルゴリズムを用いて得られる分割結果を恣意的に加工したりしないため、分割結果の最適解が損なわれることを防ぐことができる。
【００３７】
なお、クラスタ内のエンティティ数がエンティティ上限数を超えていても、それ以上改善できない、すなわち、それ以上クラスタを分割できない場合には、ソフトウェア分割装置１００は、そのクラスタの分割を終了する。ここで、クラスタ内のエンティティ数がエンティティ上限数を超えていても、それ以上改善できない場合のクラスタのグラフ構造について説明する。
【００３８】
図２は、改善不能なクラスタのグラフ構造の一例を示す説明図である。図２において、エンティティＡ１〜Ａ１００は、クラスタＣに属するエンティティ集合である。また、エンティティＡ１は、９９個のエンティティＡ２〜Ａ１００からそれぞれ呼び出されるエンティティである。
【００３９】
この場合、クラスタＣ内のエンティティ数がエンティティ上限数を超えていても、これ以上クラスタＣを分割する合理的な選択が存在しない。また、エンティティＡ１がエンティティＡ２〜Ａ１００から呼び出されるという単純な構造のため、エンティティ上限数を超えていても、人間が容易に理解することができる。このため、ソフトウェア分割装置１００は、これ以上クラスタＣを分割しない。
【００４０】
（ソフトウェア分割装置１００のハードウェア構成例）
図３は、ソフトウェア分割装置１００のハードウェア構成例を示すブロック図である。図３において、ソフトウェア分割装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３０１と、メモリ３０２と、ディスクドライブ３０３と、ディスク３０４と、ディスプレイ３０５と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）３０６と、キーボード３０７と、マウス３０８と、スキャナ３０９と、プリンタ３１０と、を有する。また、各構成部はバス３００によってそれぞれ接続される。
【００４１】
ここで、ＣＰＵ３０１は、ソフトウェア分割装置１００の全体の制御を司る。メモリ３０２は、例えば、ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）およびフラッシュＲＯＭなどを有する。具体的には、例えば、フラッシュＲＯＭやＲＯＭが各種プログラムを記憶し、ＲＡＭがＣＰＵ３０１のワークエリアとして使用される。メモリ３０２に記憶されるプログラムは、ＣＰＵ３０１にロードされることで、コーディングされている処理をＣＰＵ３０１に実行させる。
【００４２】
ディスクドライブ３０３は、ＣＰＵ３０１の制御にしたがってディスク３０４に対するデータのリード／ライトを制御する。ディスク３０４は、ディスクドライブ３０３の制御で書き込まれたデータを記憶する。ディスク３０４としては、例えば、磁気ディスク、光ディスクなどが挙げられる。
【００４３】
ディスプレイ３０５は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。ディスプレイ３０５は、例えば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００４４】
Ｉ／Ｆ３０６は、通信回線を通じてネットワーク３１１に接続され、ネットワーク３１１を介して他のコンピュータに接続される。そして、Ｉ／Ｆ３０６は、ネットワーク３１１と内部のインターフェースを司り、他のコンピュータからのデータの入出力を制御する。Ｉ／Ｆ３０６には、例えば、モデムやＬＡＮアダプタなどを採用することができる。
【００４５】
キーボード３０７は、文字、数字、各種指示などの入力のためのキーを備え、データの入力を行う。キーボード３０７は、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス３０８は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などを行う。
【００４６】
スキャナ３０９は、画像を光学的に読み取り、ソフトウェア分割装置１００内に画像データを取り込む。スキャナ３０９は、ＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）機能を有していてもよい。プリンタ３１０は、画像データや文書データを印刷する。プリンタ３１０には、例えば、レーザプリンタやインクジェットプリンタを採用することができる。
【００４７】
なお、ソフトウェア分割装置１００は、上述した構成部のうち、例えば、スキャナ３０９、プリンタ３１０などを有さないことにしてもよい。
【００４８】
（ソフトウェア分割装置１００の機能的構成例）
図４は、実施の形態１にかかるソフトウェア分割装置１００の機能的構成例を示すブロック図である。図４において、ソフトウェア分割装置１００は、取得部４０１と、関係抽出部４０２と、分割制御部４０３と、出力部４０４と、を含む構成である。取得部４０１〜出力部４０４は制御部となる機能であり、具体的には、例えば、図３に示したメモリ３０２、ディスク３０４などの記憶装置に記憶されたプログラムをＣＰＵ３０１に実行させることにより、または、Ｉ／Ｆ３０６により、その機能を実現する。各機能部の処理結果は、例えば、メモリ３０２、ディスク３０４などの記憶装置に記憶される。
【００４９】
取得部４０１は、分割対象となるソフトウェアＳＷのソースコードを取得する機能を有する。具体的には、例えば、取得部４０１は、図３に示したキーボード３０７やマウス３０８を用いたユーザの操作入力により、ソフトウェアＳＷのソースコードを取得する。また、取得部４０１は、例えば、図３に示したネットワーク３１１を介して、外部のコンピュータからソフトウェアＳＷのソースコードを取得することにしてもよい。
【００５０】
取得されたソフトウェアＳＷのソースコードは、ソースコードＤＢ（Ｄａｔａ  Ｂａｓｅ）４１０に記憶される。ソースコードＤＢ４１０は、ソフトウェアＳＷのソースコード（例えば、後述の図７に示すソースコード７０１，７０２）を記憶する。ソースコードＤＢ４１０は、例えば、図３に示したメモリ３０２、ディスク３０４などの記憶装置により実現される。
【００５１】
取得部４０１は、クラスタ粒度基準情報４２０を取得する機能を有する。ここで、クラスタ粒度基準情報４２０は、クラスタ上限数とエンティティ上限数とを対応付けて示す情報である。具体的には、例えば、取得部４０１は、キーボード３０７やマウス３０８を用いたユーザの操作入力により、クラスタ粒度基準情報４２０を取得する。
【００５２】
また、取得部４０１は、例えば、ネットワーク３１１を介して、外部のコンピュータからクラスタ粒度基準情報４２０を取得することにしてもよい。取得されたクラスタ粒度基準情報４２０は、例えば、メモリ３０２、ディスク３０４などの記憶装置に記憶される。
【００５３】
ここで、クラスタ粒度基準情報４２０の具体例について説明する。
【００５４】
図５は、クラスタ粒度基準情報４２０の具体例を示す説明図である。図５において、クラスタ粒度基準情報４２０は、クラスタ上限数「３０」とエンティティ上限数「５０」とを対応付けて示す。クラスタ上限数「３０」およびエンティティ上限数「５０」は、例えば、ソフトウェアＳＷを分析する者のスキルやソフトウェアＳＷの管理しやすさなどを考慮して設定される。
【００５５】
図４の説明に戻り、関係抽出部４０２は、ソフトウェアＳＷの構成要素であるエンティティ間の依存関係を抽出する機能を有する。具体的には、例えば、関係抽出部４０２は、ソースコードＤＢ４１０からソフトウェアＳＷのソースコードを読み込み、既存の構文解析技術および静的解析技術により、ソースコードを解析する。そして、関係抽出部４０２は、解析したソースコードから関係元エンティティと関係先エンティティとの組を抽出することにより、エンティティ間の依存関係を抽出する。
【００５６】
ここで、ソフトウェアＳＷのグラフ表現について説明する。
【００５７】
図６は、ソフトウェアＳＷのグラフ表現例を示す説明図である。図６において、□の図形は、ソフトウェアＳＷの構成要素であるエンティティを示す。図６の例では、ソフトウェアＳＷの構成要素であるエンティティの数を１６個とする。エンティティ間の矢印は、依存関係を示す。矢印の始端を関係元エンティティとし、矢印の終端（矢印の先）を関係先エンティティとする。
【００５８】
例えば、依存関係が呼び出し関係を示す場合、関係元エンティティが関係先エンティティを呼び出すことになる。具体的には、例えば、各エンティティは、例えば、Ｊａｖａ（登録商標）言語のクラスを示す。エンティティの番号は、後述する図７のクラスの番号に対応する。例えば、エンティティ＃（＃は数字の意味）は、クラスＣ＃に対応する。
【００５９】
図７は、ソフトウェアＳＷのソースコード例を示す説明図である。図７の例では、Ｊａｖａ言語のソースコードを例に挙げて説明する。図７において、ソースコード７０１は、クラスＣ２がクラスＣ５，Ｃ９，Ｃ１４，Ｃ１を呼び出すことを示すソースコードである。また、ソースコード７０２は、クラスＣ５がクラスＣ１を呼び出すことを示すソースコードである。
【００６０】
例えば、関係抽出部４０２は、ソースコード７０１から、クラスＣ２を関係元エンティティとして抽出する。また、関係抽出部４０２は、ソースコード７０１から、クラスＣ２の呼び出し先となるクラスＣ５，Ｃ９，Ｃ１４，Ｃ１を、クラスＣ２の関係先エンティティとして抽出する。これにより、エンティティ間の依存関係が抽出される。ソースコード７０２についても同様に、関係抽出部４０２は、クラスＣ５を関係元エンティティとして抽出し、クラスＣ１を関係先エンティティとして抽出する。
【００６１】
関係抽出部４０２は、抽出した関係元エンティティと関係先エンティティとの組を、関係グラフ情報４３０のレコードとして格納する。関係グラフ情報４３０は、ソフトウェアＳＷの構成要素であるエンティティを頂点とし、エンティティ間（または、クラスタ間）の依存関係を辺とするグラフ構造でソフトウェアＳＷを表現する情報である。
【００６２】
例えば、ソースコード７０１の場合、関係抽出部４０２は、｛２，５｝，｛２，９｝，｛２，１４｝，｛２，１｝を関係グラフ情報４３０に格納する。｛ａ，ｂ｝は、関係元エンティティの番号ａと関係先エンティティの番号ｂとの組を示す。なお、関係グラフ情報４３０の具体例については、図８を用いて後述する。
【００６３】
関係抽出部４０２は、関係元エンティティから関係先エンティティへの本質度を算出する機能を有する。ここで、本質度とは、エンティティ間の依存関係において、関係元エンティティが役割を果たすために、その依存関係がどれだけ本質的であるかを示す度合いである。役割とは、ソフトウェアＳＷが実現する機能やタスク、業務などのことである。
【００６４】
本質度は、上述したエンティティ間の依存関係に関する重みに対応する。本質度は、エンティティ間の依存関係ごとに与えられ、依存関係に対応する辺の重みとして用いられる。例えば、本質度は、下記式（１）を用いて表現することができる。
【００６５】
【数１】
2015179452.tif 000003
【００６６】
上記式（１）において、左辺のＥ（Ａ，Ｂ）は、エンティティＡからエンティティＢへの依存関係の本質度を示す。右辺の分母のｄin（Ｂ）は、エンティティＢの入次数を意味する。入次数は、エンティティＢが関係先エンティティとなる辺の数、または、被依存関係数である。
【００６７】
なお、上記式（１）の右辺として、例えば、エンティティＢの相対サイズ値や予め与えた重要度数値などの別の形態を用いることにしてもよい。
【００６８】
また、関係抽出部４０２は、関係元エンティティと関係先エンティティとの組に対応付けて、算出した本質度を、エンティティ間の依存関係に対応する辺の重みとして関係グラフ情報４３０に格納する。これにより、ソフトウェアＳＷの関係グラフ情報４３０が生成される。関係グラフ情報４３０は、例えば、メモリ３０２、ディスク３０４などの記憶装置に記憶される。
【００６９】
ここで、関係グラフ情報４３０の具体例について説明する。
【００７０】
図８は、関係グラフ情報４３０の具体例を示す説明図である。図８において、関係グラフ情報４３０は、関係元と関係先と重みとを対応付けて示す。ここで、関係元は、関係元エンティティを示す。関係先は、関係先エンティティを示す。重みは、関係元エンティティから関係先エンティティへの本質度であり、エンティティ間の依存関係に対応する辺の重みを示す。
【００７１】
ここでは、重みは、関係先エンティティへの入次数の逆数で表現される。例えば、関係グラフ情報４３０の１行目のレコードでは、関係元エンティティが「２（Ｃ２）」、関係先エンティティが「１（Ｃ１）」である。関係先エンティティである１（Ｃ１）の入次数となる辺の数は１５本であるため（図６参照）、重みは「１／１５」となる。
【００７２】
図４の説明に戻り、分割制御部４０３は、ソフトウェアＳＷをクラスタリングする機能を有する。ここで、クラスタリングとは、ソフトウェアＳＷをグラフで表現し、当該グラフをクラスタに分割することである。クラスタは、ソフトウェアＳＷのグラフを部分グラフに分割したときの、部分グラフまたは部分グラフに属するエンティティの集合のことである。
【００７３】
具体的には、分割制御部４０３は、選択部４０５と、関係グラフ変換部４０６と、分割部４０７と、を有する。以下、分割制御部４０３が有する各機能部の具体的な処理内容について説明する。
【００７４】
選択部４０５は、ソフトウェアＳＷの構成要素群であるエンティティ群から、処理対象のエンティティ集合を選択する機能を有する。ここで、処理対象のエンティティ集合とは、クラスタ内のエンティティ数がエンティティ上限数を超えるクラスタ内のエンティティ集合である。
【００７５】
より詳細に説明すると、処理対象のエンティティ集合は、ソフトウェアＳＷをグラフで表現し、当該グラフを部分グラフに分割したときの、エンティティ上限数の基準を満たしていない部分グラフに属するエンティティの集合である。エンティティ上限数は、例えば、図５に示したクラスタ粒度基準情報４２０により特定される。
【００７６】
ただし、ソフトウェアＳＷが分割されていない未分割の状態では、選択部４０５は、例えば、ソフトウェアＳＷの構成要素群であるエンティティ群全体を処理対象のエンティティ集合として選択する。
【００７７】
関係グラフ変換部４０６は、関係抽出部４０２によって生成された関係グラフ情報４３０から、選択部４０５によって選択された処理対象のエンティティ集合のレコードを抽出することにより、新たな関係グラフ情報Ｒを生成する機能を有する。
【００７８】
具体的には、例えば、関係グラフ変換部４０６は、関係グラフ情報４３０から、処理対象となる部分グラフの各辺に対応するレコードを抽出することにより、関係グラフ情報Ｒを生成する。ただし、ソフトウェアＳＷが分割されていない未分割の状態では、例えば、関係グラフ情報４３０が関係グラフ情報Ｒとなる。
【００７９】
分割部４０７は、処理対象のエンティティ集合が選択されたことに応じて、エンティティ群のエンティティ間の依存関係により特定される当該依存関係に関する重みに基づいて、処理対象のエンティティ集合を複数のクラスタに分割する機能を有する。
【００８０】
例えば、分割部４０７は、上述した性質（ｉ）〜（ｉｉｉ）を満たすために、生成された関係グラフ情報Ｒに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、処理対象のエンティティ集合を複数のクラスタに分割する。
【００８１】
より具体的には、例えば、分割部４０７は、上述した性質（ｉ）〜（ｉｉｉ）を満たすクラスタリングアルゴリズムとして、先行技術文献として挙げた特許文献１（特開２０１３−１４８９８７号公報）の技術を用いる。特許文献１は、グラフのクラスタリングの良さを示す尺度であるモジュラリティ評価関数ＱDWを用いて、モジュラリティ評価関数ＱDWが最大となるクラスタリング（クラスタへの分割）を貪欲法にて探索する技術である。
【００８２】
モジュラリティ評価関数ＱDWは、例えば、下記式（２）で定義される。
【００８３】
【数２】
2015179452.tif 000004
【００８４】
上記式（２）において、Ａijは、グラフの隣接行列Ａの要素である。添え字のｉは、関係元エンティティ（または、関係元クラスタ）である頂点の番号を示す。添え字のｊは、関係先エンティティ（または、関係先クラスタ）である頂点の番号を示す。隣接行列Ａの要素の値は辺の重みであり、非負であり、０より大きい場合は辺有り、０の場合は辺無しを意味する。有向グラフであるため、隣接行列Ａは非対称行列である。
【００８５】
また、ｋiOUTは、頂点ｉが関係元エンティティ（または、関係元クラスタ）となる辺の重みの合計である。具体的には、ｋiOUTは、下記式（３）により表される。
【００８６】
ｋiOUT＝ΣjＡij      ・・・（３）
【００８７】
また、ｋjINは、頂点ｊが関係先エンティティ（または、関係先クラスタ）となる辺の重みの合計である。具体的には、ｋjINは、下記式（４）により表される。
【００８８】
ｋjIN＝ΣiＡij      ・・・（４）
【００８９】
また、ｍは、辺の重み（要素Ａij）の合計であり、隣接行列Ａの要素Ａijの総和である。具体的には、ｍは、下記式（５）により表される。
【００９０】
ｍ＝ΣiΣjＡij      ・・・（５）
【００９１】
また、ｃiは、頂点ｉが属するクラスタを示す。すべての頂点はいずれかのクラスタに属するものとする。Ｃは、分割を表し、ｃiの集合（Ｃ＝｛ｃi｝）である。
【００９２】
また、δ（ｃi，ｃj）は、クロネッカーのデルタ関数である。すなわち、クラスタｃiとクラスタｃjが同じならばδ（ｃi，ｃj）＝１、異なるならδ（ｃi，ｃj）＝０となる。
【００９３】
モジュラリティ評価関数ＱDWの値域は［−１，１］となり、大きいほどよいクラスタリングであることを意味し、小さいほど悪いクラスタリングであることを意味する。ただし、実際の上限値と下限値はグラフに依存し、実際には上限値が１近くになることはめったにない。
【００９４】
上記式（２）の意図を説明する。クロネッカーのデルタ関数δ（ｃi，ｃj）は、クラスタ内の辺のみを考慮しクラスタ外の辺を無視するための関数である。クロネッカーのデルタ関数δ（ｃi，ｃj）により、各クラスタ内にある辺についての式となる。すなわち、クラスタｃiとクラスタｃjが異なるならδ（ｃi，ｃj）＝０となるため、モジュラリティ評価関数ＱDWへの寄与は０となる。
【００９５】
隣接行列Ａijは頂点ｉから頂点ｊへの辺の重みである。頂点ｉから辺が出る重み付き確率の期待値はｋiOUT／ｍであり、頂点ｊへ辺が入る重み付き確率の期待値はｋjIN／ｍであるため、エンティティｉ（または、クラスタｉ）からエンティティｊ（または、クラスタｊ）への辺の重みの期待値は、下記式（６）で表される。
【００９６】
ｍ・（ｋiOUT／ｍ）・（ｋjIN／ｍ）＝ｋiOUT・ｋjIN／ｍ      ・・・（６）
【００９７】
上記式（６）の右辺は、上記式（２）の一部である。すなわち、上記式（２）のモジュラリティ評価関数ＱDWは、各クラスタに属する辺の本質度の合計とその期待値との差をクラスタについて合計したものを、値域が［１，−１］になるように正規化したものである。
【００９８】
より直観的な表現で表すと、モジュラリティ評価関数ＱDWは、クラスタ内の辺の本質度（重み）の合計がその期待値より大きい場合に高くなると言える。言い換えれば、クラスタ内の辺の本質度の密度が高い場合に高くなる、また、クラスタ外の辺の本質度の合計が少ない場合に高くなると言える。
【００９９】
分割部４０７は、関係グラフ情報Ｒに基づいて、上記式（２）を最大化するように、処理対象のエンティティ集合を複数のクラスタに分割する。ここで、本質度（重み）を用いたクラスタリングの処理過程について説明する。まず、本質度（重み）を用いたクラスタリングの処理過程で用いる記号の定義と表記法について説明する。
【０１００】
グラフのすべての頂点の集合をＶとする。頂点はエンティティ（または、クラスタ）を示す。頂点は１以上の連番の整数で表し、頂点数をｎとする。すなわち、Ｖ＝｛１，２，…，ｎ｝である。Ｖのある分割をＣで表す。Ｃは、空集合でない互いに素なＶの部分集合Ｓiを要素とする集合であり、Ｃ＝｛Ｓ1，Ｓ2，…，Ｓ|C|｝と表す。｜Ｃ｜は、分割Ｃの要素数を意味する。
【０１０１】
このとき、集合Ｖは、下記式（７）によって表される。
【０１０２】
Ｓ1∪Ｓ2∪…∪Ｓ|C|＝Ｖ      ・・・（７）
【０１０３】
頂点ｉがＳxの要素である場合、頂点ｉのクラスタｃiはｘと求まる。すなわち、分割Ｃを定めるとモジュラリティ評価関数ＱDWの値が定まる。この場合、ＱDW（Ｃ）と表す。また、分割Ｃ内の異なる２つの要素Ｓi，Ｓjを併合させたＣ［ｉ，ｊ］を下記式（８）で定義する。
【０１０４】
Ｃ［ｉ，ｊ］＝（Ｃ−｛Ｓi｝−｛Ｓj｝）∪｛Ｓi∪Ｓj｝    ・・・（８）
【０１０５】
上記式（８）中、Ａ−Ｂは集合Ａから集合Ｂの要素を除いた差集合を意味する。ある状態ｋのときの分割Ｃを、Ｃ(k)＝｛Ｓ(k)1，Ｓ(k)２，…，Ｓ(k)|C(k)|｝とする。例えば、Ｃ＝｛Ｓ1，Ｓ2，Ｓ3，Ｓ4｝において、部分集合Ｓ1，Ｓ2を併合する場合、併合後の分割Ｃ［ｉ，ｊ］は、Ｃ［ｉ，ｊ］＝Ｃ［１，２］＝｛Ｓ1∪Ｓ2，Ｓ3，Ｓ4｝となる。Ｓ1∪Ｓ2は、部分集合Ｓ1，Ｓ2の和集合である。
【０１０６】
ここで、図８に示した関係グラフ情報４３０を用いた場合の本質度（重み）を用いたクラスタリングの処理過程について説明する。
【０１０７】
図９は、クラスタリングの処理過程の一例を示す説明図である。図９において、状態ｋでの分割Ｃのモジュラリティ評価関数ＱDWをＱDW（Ｃ(k)）とする。
【０１０８】
（Ａ）は、初期状態（ｋ＝０）の分割Ｃ(0)を示している。初期状態では、１つの頂点が１つのクラスタとなる。この場合のモジュラリティ評価関数ＱDW（Ｃ(0)）は、ＱDW（Ｃ(0)）＝−０．０４５である。この状態から、総当りで２つの部分集合が併合され、併合後のＱDWが最も高くなる併合が採用され、次状態（ｋ＝１）とする。この場合、部分集合｛６｝と｛１４｝の併合が、ＱDWが最も高くなる併合である。
【０１０９】
（Ｂ）は、（Ａ）の次状態（ｋ＝１）の分割Ｃ(1)を示している。この場合のモジュラリティ評価関数ＱDW（Ｃ(1)）は、ＱDW（Ｃ(1)）＝０．０７５である。この状態から、総当りで２つの部分集合が併合され、併合後のＱDWが最も高くなる併合が採用され、次状態（ｋ＝２）とする。この場合、部分集合｛６，１４｝と｛１１｝の併合が、ＱDWが最も高くなる併合である。
【０１１０】
（Ｃ）は、（Ｂ）の次状態（ｋ＝２）の分割Ｃ(2)を示している。この場合のモジュラリティ評価関数ＱDW（Ｃ(2)）は、ＱDW（Ｃ(2)）＝０．１３８である。この状態から、総当りで２つの部分集合が併合され、併合後のＱDWが最も高くなる併合が採用され、次状態（ｋ＝３）とする。このような処理が繰り返し行われる。
【０１１１】
（Ｄ）は、初期状態から１３回反復された場合のｋ＝１３のときの状態の分割Ｃ(13)を示している。ＱDW（Ｃ(13)）＝０．４８１である。この状態から、総当りで２つの部分集合が併合される。ｋ＝１３では、部分集合｛２，５，６，１１，１４｝と｛１，７，９，１０，１５，１６｝との併合、部分集合｛２，５，６，１１，１４｝と｛３，４，８，１２，１３｝との併合、部分集合｛１，７，９，１０，１５，１６｝と｛３，４，８，１２，１３｝との併合がある。
【０１１２】
いずれの併合も、ＱDW（Ｃ(13)）＝０．４８１を下回るため、分割Ｃ(13)でクラスタリングが終了する。これにより、ソフトウェアは、３個の部分集合｛２，５，６，１１，１４｝，｛１，７，９，１０，１５，１６｝，｛３，４，８，１２，１３｝に分割されたことになる。
【０１１３】
ここで、分割部４０７の分割結果の具体例について説明する。この分割結果は、ソフトウェア分割装置１００の中間結果（統合前の分割結果）となる。
【０１１４】
図１０は、統合前の分割結果の具体例を示す説明図である。図１０において、分割結果１０００は、子エンティティ／クラスタＩＤと親クラスタＩＤとを対応付けて示す情報である。子エンティティ／クラスタＩＤは、分割されたクラスタ内のエンティティまたはクラスタを識別する識別子である。親クラスタＩＤは、分割されたクラスタを識別する識別子である。
【０１１５】
図１０の例では、ソフトウェアＳＷが、３個の部分集合に分割されている。そして、部分集合｛２，５，６，１１，１４｝には親クラスタＩＤ「１００１」、部分集合｛１，７，９，１０，１５，１６｝には親クラスタＩＤ「１００２」、部分集合｛３，４，８，１２，１３｝には親クラスタＩＤ「１００３」が割り当てられている。
【０１１６】
例えば、分割結果１０００の一行目によれば、エンティティ１がクラスタ１００２に属していることがわかる。すなわち、分割結果１０００によれば、図１１に示すようなソフトウェアＳＷの階層構造を把握することができる。
【０１１７】
図１１は、ソフトウェアＳＷの階層構造例を示す説明図（その１）である。図１１において、ソフトウェアＳＷが階層構造化されて表現されている。具体的には、ソフトウェアＳＷが３個のクラスタ１００１〜１００３に分割されている。クラスタ１００１には、５個のエンティティ２，５，６，１１，１４が属している。クラスタ１００２には、６個のエンティティ１，７，９，１０，１５，１６が属している。クラスタ１００３には、５個のエンティティ３，４，８，１２，１３が属している。
【０１１８】
図４の説明に戻り、選択部４０５は、分割された複数のクラスタのうちのいずれかのクラスタ内のエンティティ数がエンティティ上限数を超えていることに応じて、当該クラスタ内のエンティティ集合を処理対象のエンティティ集合として選択する。
【０１１９】
具体的には、例えば、選択部４０５は、分割部４０７の分割結果（例えば、分割結果１０００）を参照して、分割されたクラスタごとに、当該クラスタ内のエンティティ数がエンティティ上限数を超えているか否かを判断する。そして、選択部４０５は、エンティティ上限数を超えているクラスタ内のエンティティ集合を処理対象のエンティティ集合として選択する。
【０１２０】
この結果、エンティティ上限数を超えるクラスタが、一つの新たなソフトウェアとみなされて、関係グラフ変換部４０６により、新たな関係グラフ情報Ｒが生成される。そして、分割部４０７により、新たな関係グラフ情報Ｒに基づき当該クラスタ内のエンティティ集合が複数のクラスタに分割される。
【０１２１】
これにより、エンティティ上限数を超えるクラスタがなくなるまで、最下位階層のクラスタ内のエンティティ集合の分割が再帰的に繰り返される。ただし、選択部４０５は、クラスタ内のエンティティ数がエンティティ上限数を超えていても、図２に示したように、そのクラスタをそれ以上改善できない場合には、当該クラスタ内のエンティティ集合を処理対象のエンティティ集合として選択しない。
【０１２２】
すなわち、選択部４０５は、エンティティ上限数を超えるクラスタ内のエンティティ集合のうちのいずれかのエンティティが他のエンティティからそれぞれ呼び出される場合には、該クラスタ内のエンティティ集合を処理対象のエンティティ集合として選択しない。これにより、それ以上改善できないクラスタの分割処理を削減して、ソフトウェア分割装置１００にかかる処理負荷を抑制することができる。
【０１２３】
また、関係グラフ変換部４０６は、分割部４０７の分割結果を統合する機能を有する。具体的には、例えば、関係グラフ変換部４０６は、処理対象のエンティティ集合の分割結果を、全体の分割結果に統合する。ここで、全体の分割結果とは、ソフトウェアＳＷのエンティティ群全体を処理対象のエンティティ集合とした場合の分割結果、あるいは、統合後の分割結果である。なお、分割結果の統合例については、図１２および図１３を用いて後述する。
【０１２４】
出力部４０４は、分割制御部４０３によるソフトウェアＳＷのクラスタリング結果を分割結果４４０として出力する。クラスタリング結果は、分割結果を統合した最終的な統合結果である。出力部４０４の出力形式としては、例えば、メモリ３０２、ディスク３０４などの記憶装置への記憶、ディスプレイ３０５への表示、プリンタ３１０への印刷出力、Ｉ／Ｆ３０６による外部のコンピュータへの送信などがある。
【０１２５】
（分割結果の統合例）
つぎに、図１２および図１３を用いて分割結果の統合例について説明する。ここでは、エンティティ上限数を「３」とし、図１０および図１１に示したクラスタ１００３を、エンティティ上限数を超えているクラスタとして注目した場合を例に挙げて説明する。
【０１２６】
この場合、クラスタ１００３が、一つの新たなソフトウェアとみなされて、クラスタ１００３内のエンティティ集合｛３，４，８，１２，１３｝が、処理対象のエンティティ集合となり、複数のクラスタに分割される。ここでは、エンティティ集合｛３，４，８，１２，１３｝が、図１２に示すように、クラスタ１００４〜１００６に分割された場合を想定する。
【０１２７】
図１２は、ソフトウェアＳＷの階層構造例を示す説明図（その２）である。図１２において、ソフトウェアＳＷが階層構造化されて表現されている。具体的には、ソフトウェアＳＷが３個のクラスタ１００１〜１００３に分割されている。また、クラスタ１００３が３個のクラスタ１００４〜１００６に分割されている。
【０１２８】
クラスタ１００１には、５個のエンティティ２，５，６，１１，１４が属している。クラスタ１００２には、６個のエンティティ１，７，９，１０，１５，１６が属している。クラスタ１００４には、２個のエンティティ４，１３が属している。クラスタ１００５には、２個のエンティティ８，１２が属している。クラスタ１００６には、１個のエンティティ３が属している。
【０１２９】
以下、クラスタ１００３がクラスタ１００４〜１００６に分割された場合を想定して、関係グラフ変換部４０６の分割結果の統合処理例について説明する。
【０１３０】
この場合、まず、関係グラフ変換部４０６は、分割元のクラスタ１００３をクラスタＡとする。そして、関係グラフ変換部４０６は、クラスタ１００３内のエンティティ集合｛３，４，８，１２，１３｝を分割して得られた各部分集合に全体で未使用の親クラスタＩＤを割り当てる。
【０１３１】
例えば、関係グラフ変換部４０６は、部分集合｛４，１３｝に親クラスタＩＤ「１００４」、部分集合｛８，１２｝に親クラスタＩＤ「１００５」、部分集合｛３｝に親クラスタＩＤ「１００６」を割り当てる。つぎに、関係グラフ変換部４０６は、クラスタ１００４〜１００６のうちのいずれかのクラスタをクラスタＸとして選択する。
【０１３２】
そして、関係グラフ変換部４０６は、クラスタＸの子エンティティごとに、全体の分割結果、すなわち、図１０に示した分割結果１０００から、該当する行を抽出し、その行の親クラスタＩＤをクラスタＸのクラスタＩＤに置き換える。つぎに、関係グラフ変換部４０６は、全体の分割結果１０００に、「子エンティティ／クラスタＩＤ」がクラスタＸのクラスタＩＤ、「親クラスタＩＤ」がクラスタＡのクラスタＩＤである行を追加する。
【０１３３】
そして、関係グラフ変換部４０６は、クラスタ１００４〜１００６からクラスタＸとして選択されていない未選択のクラスタがなくなるまで同様の処理を繰り返す。これにより、全体の分割結果に新たな分割結果を統合することができる。
【０１３４】
図１３は、統合後の分割結果の具体例を示す説明図である。図１３において、統合後の分割結果１０００では、統合前の分割結果１０００（図１０参照）に対して、エンティティ３の親クラスタＩＤが「１００３」から「１００６」に置き換えられている。また、エンティティ４の親クラスタＩＤが「１００３」から「１００４」に置き換えられている。
【０１３５】
また、エンティティ８の親クラスタＩＤが「１００３」から「１００５」に置き換えられている。また、エンティティ１２の親クラスタＩＤが「１００３」から「１００５」に置き換えられている。また、エンティティ１３の親クラスタＩＤが「１００３」から「１００４」に置き換えられている。
【０１３６】
さらに、「子エンティティ／クラスタＩＤ」が「１００４」、「親クラスタＩＤ」が「１００３」である行が追加されている。また、「子エンティティ／クラスタＩＤ」が「１００５」、「親クラスタＩＤ」が「１００３」である行が追加されている。また、「子エンティティ／クラスタＩＤ」が「１００６」、「親クラスタＩＤ」が「１００３」である行が追加されている。
【０１３７】
（ソフトウェア分割装置１００のソフトウェア分割処理手順）
つぎに、実施の形態１にかかるソフトウェア分割装置１００のソフトウェア分割処理手順について説明する。
【０１３８】
図１４は、実施の形態１にかかるソフトウェア分割装置１００のソフトウェア分割処理手順の一例を示すフローチャートである。図１４のフローチャートにおいて、まず、ソフトウェア分割装置１００は、関係抽出処理を実行する（ステップＳ１４０１）。関係抽出処理は、ソフトウェアＳＷの構成要素であるエンティティ間の依存関係を抽出する処理である。関係抽出処理の具体的な処理手順については、図１５を用いて後述する。
【０１３９】
そして、ソフトウェア分割装置１００は、重み算出処理を実行する（ステップＳ１４０２）。重み算出処理は、エンティティ間の依存関係に関する重みを算出する処理である。重み算出処理の具体的な処理手順については、図１６を用いて後述する。
【０１４０】
つぎに、ソフトウェア分割装置１００は、ソフトウェアＳＷの構成要素であるすべてのエンティティが一つのクラスタに属するものとする（ステップＳ１４０３）。そして、ソフトウェア分割装置１００は、エンティティ上限数を超えるクラスタ内のエンティティ集合を処理対象のエンティティ集合として選択する（ステップＳ１４０４）。
【０１４１】
つぎに、ソフトウェア分割装置１００は、関係グラフ情報４３０から、選択した処理対象のエンティティ集合のレコードを抽出することにより、新たな関係グラフ情報Ｒを生成する（ステップＳ１４０５）。
【０１４２】
そして、ソフトウェア分割装置１００は、生成した新たな関係グラフ情報Ｒに基づいて、クラスタリング処理を実行する（ステップＳ１４０６）。クラスタリング処理は、処理対象のエンティティ集合を複数のクラスタに分割する処理である。クラスタリング処理の具体的な処理手順については、図１７を用いて後述する。
【０１４３】
つぎに、ソフトウェア分割装置１００は、統合処理を実行する（ステップＳ１４０７）。統合処理は、処理対象のエンティティ集合の分割結果を、全体の分割結果に統合する処理である。統合処理の具体的な処理手順については、図１９を用いて後述する。
【０１４４】
そして、ソフトウェア分割装置１００は、最下位階層のすべてのクラスタがエンティティ上限数の基準を満たしている、または、改善不能か否かを判断する（ステップＳ１４０８）。ここで、いずれかのクラスタがエンティティ上限数の基準を満たしておらず、かつ、そのクラスタが改善不能ではない場合（ステップＳ１４０８：Ｎｏ）、ソフトウェア分割装置１００は、ステップＳ１４０４に戻る。
【０１４５】
一方、最下位階層のすべてのクラスタがエンティティ上限数の基準を満たしている、または、改善不能である場合（ステップＳ１４０８：Ｙｅｓ）、ソフトウェア分割装置１００は、全体の分割結果を分割結果４４０として出力して（ステップＳ１４０９）、本フローチャートによる一連の処理を終了する。
【０１４６】
これにより、ソフトウェアＳＷを分割して得られるクラスタ内のエンティティ数がエンティティ上限数以下となるまで、または、改善不能となるまで、クラスタ内のエンティティ集合の分割を再帰的に繰り返すことができる。
【０１４７】
＜関係抽出処理手順＞
つぎに、図１４のステップＳ１４０１に示した関係抽出処理の具体的な処理手順について説明する。
【０１４８】
図１５は、関係抽出処理の具体的処理手順の一例を示すフローチャートである。図１５のフローチャートにおいて、まず、ソフトウェア分割装置１００は、ソフトウェアＳＷのソースコードをソースコードＤＢ４１０から読み込む（ステップＳ１５０１）。そして、ソフトウェア分割装置１００は、読み込んだソースコードを構文解析技術および静的解析技術を用いて解析する（ステップＳ１５０２）。
【０１４９】
つぎに、ソフトウェア分割装置１００は、解析されたソースコードからエンティティを抽出するとともに（ステップＳ１５０３）、エンティティ間の依存関係を抽出する（ステップＳ１５０４）。そして、ソフトウェア分割装置１００は、抽出により得られた関係元エンティティと関係先エンティティの組を関係グラフ情報４３０のレコードとして格納して（ステップＳ１５０５）、関係抽出処理を呼び出したステップに戻る。
【０１５０】
これにより、関係グラフ情報４３０を生成することができる。ただし、この時点では、関係グラフ情報４３０の各レコードの重みは未設定である。
【０１５１】
＜重み算出処理手順＞
つぎに、図１４のステップＳ１４０２に示した重み算出処理の具体的な処理手順について説明する。
【０１５２】
図１６は、重み算出処理の具体的処理手順の一例を示すフローチャートである。図１６のフローチャートにおいて、まず、ソフトウェア分割装置１００は、関係グラフ情報４３０を読み込み（ステップＳ１６０１）、未選択の関係先エンティティがあるか否かを判断する（ステップＳ１６０２）。
【０１５３】
ここで、未選択の関係先エンティティがある場合（ステップＳ１６０２：Ｙｅｓ）、ソフトウェア分割装置１００は、未選択の関係先エンティティを１つ選択する（ステップＳ１６０３）。つぎに、ソフトウェア分割装置１００は、上記式（１）を用いて、選択エンティティの辺ごとに、重みを算出する（ステップＳ１６０４）。
【０１５４】
そして、ソフトウェア分割装置１００は、辺ごとに算出された重みを、関係グラフ情報４３０の該当レコードに格納して（ステップＳ１６０５）、ステップＳ１６０２に戻る。また、ステップＳ１６０２において、未選択の関係先エンティティがない場合（ステップＳ１６０２：Ｎｏ）、ソフトウェア分割装置１００は、重み算出処理を呼び出したステップに戻る。
【０１５５】
これにより、エンティティ間の依存関係に関する重みが設定された関係グラフ情報４３０を生成することができる。
【０１５６】
＜クラスタリング処理手順＞
つぎに、図１４のステップＳ１４０６に示したクラスタリング処理の具体的な処理手順について説明する。
【０１５７】
図１７は、クラスタリング処理の具体的処理手順の一例を示すフローチャートである。図１７のフローチャートにおいて、まず、ソフトウェア分割装置１００は、図１４のステップＳ１４０５で生成された関係グラフ情報Ｒを読み込み（ステップＳ１７０１）、隣接行列Ａを生成する（ステップＳ１７０２）。
【０１５８】
つぎに、ソフトウェア分割装置１００は、隣接行列Ａの要素Ａijである辺の重みを合計することにより、モジュラリティ評価関数ＱDWのパラメータｍの値を算出する（ステップＳ１７０３）。そして、ソフトウェア分割装置１００は、モジュラリティ評価関数ＱDWのパラメータｋiOUT，ｋjINを算出する（ステップＳ１７０４）。
【０１５９】
つぎに、ソフトウェア分割装置１００は、重み付き有向モジュラリティ最大化処理を実行する（ステップＳ１７０５）。重み付き有向モジュラリティ最大化処理は、モジュラリティ評価関数ＱDWを用いてモジュラリティ評価関数ＱDWの値が最大となるように部分集合を併合していく処理である。重み付き有向モジュラリティ最大化処理の具体的な処理手順については、図１８を用いて後述する。
【０１６０】
そして、ソフトウェア分割装置１００は、重み付き有向モジュラリティ最大化処理で得られた分割結果を中間結果として出力して（ステップＳ１７０６）、クラスタリング処理を呼び出したステップに戻る。これにより、処理対象のエンティティ集合を複数のクラスタに分割することができる。
【０１６１】
＜重み付き有向モジュラリティ最大化処理手順＞
つぎに、図１７のステップＳ１７０５に示した重み付き有向モジュラリティ最大化処理の具体的な処理手順について説明する。
【０１６２】
図１８は、重み付き有向モジュラリティ最大化処理の具体的処理手順の一例を示すフローチャートである。図１８のフローチャートにおいて、まず、ソフトウェア分割装置１００は、状態ｋをｋ＝０に設定し、分割Ｃ(k)＝Ｃ(0)＝｛Ｓ(0)1，Ｓ(0)2，…，Ｓ(0)n｝を設定する（ステップＳ１８０１）。つぎに、ソフトウェア分割装置１００は、｜Ｃ(k)｜＝１であるか否かを判断する（ステップＳ１８０２）。
【０１６３】
ここで、｜Ｃ(k)｜＝１でない場合（ステップＳ１８０２：Ｎｏ）、ソフトウェア分割装置１００は、分割Ｃ(k)に対し、モジュラリティ評価関数ＱDWの値が最大となるｉとｊの組を求め、そのときの分割Ｃ(k)［ｉ，ｊ］をＣ(k+1)とする（ステップＳ１８０３）。
【０１６４】
そして、ソフトウェア分割装置１００は、ＱDW（Ｃ(k)）とＱDW（Ｃ(k+1)）とを比較する（ステップＳ１８０４）。そして、ＱDW（Ｃ(k+1)）＞ＱDW（Ｃ(k)）の場合（ステップＳ１８０４：Ｙｅｓ）、まだ、ＱDWが増加できる余地があるとして、ソフトウェア分割装置１００は、ｋをインクリメントして（ステップＳ１８０５）、ステップＳ１８０２に戻る。図９に示した内容が、ステップＳ１８０２〜Ｓ１８０５のループに相当する。
【０１６５】
そして、ステップＳ１８０２において、｜Ｃ(k)｜＝１である場合（ステップＳ１８０２：Ｙｅｓ）、これ以上分割する必要がないため、ソフトウェア分割装置１００はステップＳ１８０６に移行する。また、ステップＳ１８０４において、ＱDW（Ｃ(k+1)）＞ＱDW（Ｃ(k)）でない場合（ステップＳ１８０４：Ｎｏ）、ＱDWが増加できる余地がないとして、ソフトウェア分割装置１００はステップＳ１８０６に移行する。
【０１６６】
ステップＳ１８０６では、ソフトウェア分割装置１００は、分割Ｃ(k)による分割処理を行って（ステップＳ１８０６）、重み付き有向モジュラリティ最大化処理を呼び出したステップに戻る。例えば、ソフトウェア分割装置１００は、分割Ｃ(k)を用いて図１０に示した分割結果１０００を生成する。
【０１６７】
これにより、上述した性質（ｉ）〜（ｉｉｉ）を満たすように、処理対象のエンティティ集合を複数のクラスタに分割することができる。
【０１６８】
＜統合処理手順＞
つぎに、図１４のステップＳ１４０７に示した統合処理の具体的な処理手順について説明する。
【０１６９】
図１９は、統合処理の具体的処理手順の一例を示すフローチャートである。図１９のフローチャートにおいて、まず、ソフトウェア分割装置１００は、分割元のクラスタをクラスタＡとする（ステップＳ１９０１）。分割元のクラスタは、図１４のステップＳ１４０４において選択された処理対象のエンティティ集合を含むクラスタ、すなわち、エンティティ上限数の基準を満たしていないクラスタである。
【０１７０】
そして、ソフトウェア分割装置１００は、図１４のステップＳ１４０６において得られた分割結果の各クラスタ（部分集合）に、全体で未使用のクラスタＩＤを割り当てる（ステップＳ１９０２）。つぎに、ソフトウェア分割装置１００は、得られた分割結果のうちの未選択のクラスタをクラスタＸとして選択する（ステップＳ１９０３）。
【０１７１】
そして、ソフトウェア分割装置１００は、クラスタＸの子エンティティのうちの未選択の子エンティティを選択する（ステップＳ１９０４）。クラスタＸの子エンティティとは、クラスタＸの子となるエンティティ、すなわち、クラスタＸ内のエンティティである。
【０１７２】
つぎに、ソフトウェア分割装置１００は、全体の分割結果から、選択した子エンティティの該当する行を抽出する（ステップＳ１９０５）。そして、ソフトウェア分割装置１００は、抽出した行の親クラスタＩＤをクラスタＸのクラスタＩＤに置き換える（ステップＳ１９０６）。
【０１７３】
つぎに、ソフトウェア分割装置１００は、クラスタＸの子エンティティのうち選択されていない未選択の子エンティティがあるか否かを判断する（ステップＳ１９０７）。ここで、未選択の子エンティティがある場合（ステップＳ１９０７：Ｙｅｓ）、ソフトウェア分割装置１００は、ステップＳ１９０４に戻る。
【０１７４】
一方、未選択の子エンティティがない場合（ステップＳ１９０７：Ｎｏ）、全体の分割結果に、「子エンティティ／クラスタＩＤ」がクラスタＸのクラスタＩＤ、「親クラスタＩＤ」がクラスタＡのクラスタＩＤである行を追加する（ステップＳ１９０８）。
【０１７５】
そして、ソフトウェア分割装置１００は、得られた分割結果のうち選択されていない未選択のクラスタがあるか否かを判断する（ステップＳ１９０９）。ここで、未選択のクラスタがある場合（ステップＳ１９０９：Ｙｅｓ）、ソフトウェア分割装置１００は、ステップＳ１９０３に戻る。
【０１７６】
一方、未選択のクラスタがない場合（ステップＳ１９０９：Ｎｏ）、ソフトウェア分割装置１００は、統合処理を呼び出したステップに戻る。これにより、全体の分割結果に、処理対象のエンティティ集合の分割結果を統合することができる。
【０１７７】
以上説明したように、実施の形態１にかかるソフトウェア分割装置１００によれば、ソフトウェアＳＷのエンティティ群から処理対象のエンティティ集合を選択したことに応じて、処理対象のエンティティ集合を複数のクラスタに分割することができる。この際、ソフトウェア分割装置１００は、処理対象のエンティティ集合についての関係グラフ情報Ｒに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、処理対象のエンティティ集合を分割することができる。
【０１７８】
これにより、ソフトウェアＳＷをその構成要素であるエンティティの集合として扱い、上述した性質（ｉ）〜（ｉｉｉ）を満たすように、ソフトウェアＳＷまたは同一クラスタ内のエンティティ集合を複数のクラスタに分割することができる。
【０１７９】
また、ソフトウェア分割装置１００によれば、分割した複数のクラスタのうちのいずれかのクラスタ内のエンティティ数がエンティティ上限数を超えていることに応じて、当該クラスタ内のエンティティ集合を処理対象のエンティティ集合として選択することができる。
【０１８０】
これにより、ソフトウェアＳＷを分割して得られるクラスタ内のエンティティ数がエンティティ上限数以下となるまで、クラスタ内のエンティティ集合を、一つの新たなソフトウェアとみなして、ソフトウェアの分割を再帰的に繰り返すことができる。すなわち、ソフトウェアＳＷの分割に階層構造を導入して、ソフトウェアＳＷを人間が理解できる程度の小規模な部分集合に分割することができる。また、上述した性質（ｉ）〜（ｉｉｉ）を有するクラスタリングアルゴリズムを用いて得られる分割結果を恣意的に加工したりしないため、分割結果の最適解が損なわれることを防いで分割精度を確保することができる。
【０１８１】
また、ソフトウェア分割装置１００によれば、分割したクラスタ内のエンティティ集合のうちのいずれかのエンティティが他のエンティティからそれぞれ呼び出される場合には、当該クラスタ内のエンティティ集合を処理対象のエンティティ集合として選択しないようにすることができる。
【０１８２】
これにより、クラスタ内のエンティティ数がエンティティ上限数を超えていても、そのクラスタのグラフ構造が単純で、それ以上分割の必要がない場合には、そのクラスタの分割を終了して、ソフトウェア分割装置１００にかかる処理負荷を抑制することができる。
【０１８３】
（実施の形態２）
つぎに、実施の形態２にかかるソフトウェア分割装置１００について説明する。実施の形態２では、実施の形態１で説明したソフトウェア分割装置１００に、同一親クラスタ内のクラスタ数を調整する粒度調整機能を追加した場合について説明する。なお、実施の形態１で説明した箇所と同様の箇所については図示および説明を省略する。
【０１８４】
ソフトウェアの分割において、人間による解釈を困難なものとする要因として、実施の形態１で説明したクラスタ内のエンティティ数が多すぎることのほかに、ソフトウェアから分割されるクラスタ数が多すぎるというものがある。例えば、ソースファイル（クラス）の数が数千本を超えるような大規模ソフトウェアでは、ソフトウェアから分割されるクラスタ数が５０を超えることがあり、それを人間が理解するのは困難である。
【０１８５】
そこで、実施の形態２では、ソフトウェア分割装置１００は、分割後のクラスタ数（粒度）を調整するための粒度調整パラメータｒを導入する。そして、ソフトウェア分割装置１００は、同一親クラスタを持つクラスタ集合のクラスタ数が、予め決められたクラスタ上限数以下となるまで、粒度調整パラメータｒを変更しながら当該クラスタ集合の分割を繰り返す。これにより、同一親クラスタを持つクラスタ数を人間が理解できる程度の数に抑える。以下、図２０を用いて、ソフトウェア分割装置１００のソフトウェア分割処理例について説明する。
【０１８６】
図２０は、実施の形態２にかかるソフトウェア分割方法の一実施例を示す説明図である。図２０の例では、分割対象となるソフトウェアＳＷ（１００００本のソースコード群）が、１００個のクラスタＣ１〜Ｃ１００に分割された場合を想定する。また、各クラスタＣ１〜Ｃ１００内のエンティティ数（ソースコード数）は、１００（本）である。
【０１８７】
（１）ソフトウェア分割装置１００は、ソフトウェアから分割された複数のクラスタのクラスタ数が、予め記憶されたクラスタ上限数を超えているか否かを判断する。ここで、クラスタ上限数は、予め任意に設定されてソフトウェア分割装置１００に記憶される。例えば、クラスタ上限数は、ソフトウェアを分析する者のスキルを考慮して、同一親クラスタを持つクラスタ集合（または、ソフトウェアから分割されるクラスタ集合）のクラスタ数がクラスタ上限数を超えると、そのクラスタ集合についての人間による解釈が困難なものとなる値に設定される。
【０１８８】
図２０の例では、クラスタ上限数が「３０」に設定されている場合を想定する。この場合、ソフトウェア分割装置１００は、ソフトウェアＳＷから分割されたクラスタＣ１〜Ｃ１００のクラスタ数がクラスタ上限数を超えていると判断する。
【０１８９】
（２）ソフトウェア分割装置１００は、複数のクラスタのクラスタ数がクラスタ上限数を超えていることに応じて、複数のクラスタのクラスタ間の依存関係に関する重みを算出する。ここで、クラスタ間の依存関係に関する重みは、複数のクラスタに属するエンティティ間の依存関係により特定され、グラフの頂点であるクラスタ間をつなぐ辺の重みとして用いられる。
【０１９０】
図２０の例では、クラスタＣ１〜Ｃ１００に属するエンティティ間の依存関係に基づいて、クラスタＣ１〜Ｃ１００のクラスタ間の依存関係に関する重みが算出される。なお、クラスタ間の依存関係に関する重みの算出例については後述する。以下の説明では、同一親クラスタを持ち、クラスタ数がクラスタ上限数を超える複数のクラスタを「処理対象のクラスタ集合」と表記する場合がある。
【０１９１】
（３）ソフトウェア分割装置１００は、算出したクラスタ間の依存関係に関する重みに基づいて、分割後のクラスタ数が少なくなるように、処理対象のクラスタ集合を分割する。具体的には、例えば、ソフトウェア分割装置１００は、分割後のクラスタ数（粒度）を調整するための粒度調整パラメータｒを導入する。
【０１９２】
そして、ソフトウェア分割装置１００は、粒度調整パラメータｒの値を調整することで、分割後のクラスタ数が少なくなる、すなわち、分割後のクラスタ内のエンティティ数が増加するように、処理対象のクラスタ集合を分割する。なお、粒度調整パラメータｒについての詳細な説明は後述する。
【０１９３】
また、ソフトウェア分割装置１００は、粒度調整パラメータｒをある値に設定して分割しても、分割後のクラスタ数がクラスタ上限数を超える場合には、粒度調整パラメータｒの値を再調整して、分割後のクラスタ数がより少なくなるように、処理対象のクラスタ集合の分割をやり直す。
【０１９４】
すなわち、ソフトウェア分割装置１００は、粒度調整パラメータｒの値を変化させながら、分割後のクラスタ数がクラスタ上限数以下となる粒度調整パラメータｒの値を探索する。ただし、粒度調整パラメータｒの値を調整しても、それ以上改善できない、すなわち、それ以上クラスタ数を減少できない場合には、ソフトウェア分割装置１００は、複数のクラスタの分割を終了する。
【０１９５】
図２０の例では、クラスタＣ１〜Ｃ１００が、クラスタＣ１００１〜Ｃ１０１０に分割されて、ソフトウェアＳＷから分割されるクラスタ数が「１００」から「１０」に減少している。また、各クラスタＣ１００１〜Ｃ１０１０内のクラスタ数がそれぞれ「１０」となっている。この結果、同一親クラスタを持つクラスタ集合のクラスタ数が、すべてクラスタ上限数以下となっている。
【０１９６】
このように、ソフトウェア分割装置１００によれば、同一親クラスタを持つクラスタ集合のクラスタ数がクラスタ上限数以下となるまで、粒度調整パラメータｒを変更しながら当該クラスタ集合の分割を繰り返すことができる。これにより、同一親クラスタを持つクラスタ数を人間が理解できる程度の数に抑えることができる。
【０１９７】
ここで、多階層の分割例について説明する。
【０１９８】
図２１は、多階層の分割例を示す説明図である。図２１において、ソフトウェア分割装置１００により分割されたソフトウェアＳＷの分割結果が、３レベルの階層構造で表されている。具体的には、ソフトウェアＳＷが１０個のレベル３クラスタに分割され、各レベル３クラスタが１０個のレベル２クラスタに分割され、各レベル２クラスタが１０個のレベル１クラスタに分割されている。そして、各レベル１クラスタ内のエンティティ数が１０（本）となっている。
【０１９９】
各レベルのクラスタごとに個別に見れば、同一親クラスタ内のクラスタ数が１０個となっており、人間によって十分理解できる程度の数に抑えられている。また、最下位階層の各レベル１クラスタ内のエンティティ数が１０（本）となっており、人間によって十分理解できる程度の単位に分割されている。
【０２００】
（ソフトウェア分割装置１００の機能的構成例）
つぎに、実施の形態２にかかるソフトウェア分割装置１００の機能的構成例について説明する。ここでは、実施の形態１にかかるソフトウェア分割装置１００と異なる機能部について説明する。また、実施の形態１にかかるソフトウェア分割装置１００の機能部と同一の機能を有する機能部については同一符号を付して説明する。
【０２０１】
図２２は、実施の形態２にかかるソフトウェア分割装置１００の機能的構成例を示すブロック図である。図２２において、分割制御部４０３は、選択部４０５と、関係グラフ変換部４０６と、粒度調整機能付き分割部２２０１と、を有する。
【０２０２】
選択部４０５は、処理対象のクラスタ集合を選択する機能を有する。ここで、処理対象のクラスタ集合とは、処理対象のエンティティ集合を分割して得られた複数のクラスタのうち、クラスタ数がクラスタ上限数を超える複数のクラスタである。
【０２０３】
より詳細に説明すると、処理対象のクラスタ集合は、例えば、ソフトウェアＳＷをグラフで表現し、当該グラフを複数の部分グラフに分割したときの、クラスタ上限数の基準を満たしていない部分グラフの集合である。クラスタ上限数は、例えば、クラスタ粒度基準情報４２０により特定される。
【０２０４】
関係グラフ変換部４０６は、選択部４０５によって選択された処理対象のクラスタ集合に属するエンティティ間の依存関係に関する重みに基づいて、処理対象のクラスタ集合のクラスタ間の依存関係に関する重みを算出する機能を有する。これにより、処理対象のクラスタ集合についての新たな関係グラフ情報Ｒが生成される。なお、処理対象のクラスタ集合についての関係グラフ情報Ｒの生成例については、図２３および図２４を用いて後述する。
【０２０５】
粒度調整機能付き分割部２２０１は、算出された処理対象のクラスタ集合のクラスタ間の依存関係に関する重みに基づいて、分割後のクラスタ数が少なくなるように、処理対象のクラスタ集合を複数のクラスタに分割する機能を有する。具体的には、例えば、粒度調整機能付き分割部２２０１は、分割後のクラスタ数（粒度）を調整するための粒度調整パラメータｒを導入することにより、処理対象のクラスタ集合を、分割後のクラスタ数が少なくなるように複数のクラスタに分割する。
【０２０６】
この際、粒度調整機能付き分割部２２０１は、生成された関係グラフ情報Ｒに基づいて、同一クラスタ内のクラスタ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、処理対象のクラスタ集合を複数のクラスタに分割する。すなわち、粒度調整機能付き分割部２２０１は、上述した性質（ｉ）〜（ｉｉｉ）を満たすように、処理対象のクラスタ集合を分割する。なお、粒度調整機能付き分割部２２０１の具体的な処理内容（第１の粒度調整機能、第２の粒度調整機能）については後述する。
【０２０７】
また、詳細な説明は省略するが、粒度調整機能付き分割部２２０１は、図４に示した分割部４０７と同様の機能を有する。すなわち、粒度調整機能付き分割部２２０１は、処理対象のエンティティ集合が選択されたことに応じて、処理対象のエンティティ集合を複数のクラスタに分割する機能を有する。
【０２０８】
（関係グラフ情報Ｒの生成例）
つぎに、処理対象のクラスタ集合についての関係グラフ情報Ｒの生成例について説明する。ここでは、クラスタ上限数を「２」とし、図１２に示したクラスタ１００３を親クラスタとするクラスタ１００４〜１００６が処理対象のクラスタ集合として選択された場合を想定する。すなわち、クラスタ１００４〜１００６のクラスタ数「３」がクラスタ上限数を超えている場合を想定する。
【０２０９】
この場合、関係グラフ変換部４０６は、処理対象のクラスタ集合｛１００４，１００５，１００６｝に属するエンティティ間の依存関係に関する重みに基づいて、処理対象のクラスタ集合｛１００４，１００５，１００６｝のクラスタ間の依存関係に関する重みを算出する。
【０２１０】
具体的には、例えば、まず、関係グラフ変換部４０６は、空の行からなる関係グラフ情報Ｒを生成する。そして、関係グラフ変換部４０６は、図１３に示した分割結果１０００を参照して、クラスタ１００３のクラスタＩＤを親クラスタＩＤに持つクラスタからなる集合Ｖを特定する。ここでは、集合Ｖは、「Ｖ＝｛１００４，１００５，１００６｝」となる。
【０２１１】
つぎに、関係グラフ変換部４０６は、集合Ｖからクラスタの順序対を抽出して、ａ，ｂとする。例えば、関係グラフ変換部４０６は、集合Ｖ｛１００４，１００５，１００６｝から順序対ａ，ｂとして「ａ＝１００４，ｂ＝１００５」を抽出する。
【０２１２】
そして、関係グラフ変換部４０６は、集合Ｘをａのみを要素とする集合｛ａ｝とする。集合Ｘの要素にクラスタが含まれる場合、関係グラフ変換部４０６は、集合Ｘからその要素を削除し、その要素のすべての子エンティティまたは子クラスタを集合Ｘに追加する。関係グラフ変換部４０６は、集合Ｘからクラスタがなくなるまで、この処理を繰り返す。
【０２１３】
例えば、ａを「ａ＝１００４」とし、集合Ｘを「Ｘ＝｛１００４｝」とすると、関係グラフ変換部４０６は、分割結果１０００（図１３参照）を参照して、集合Ｘからクラスタ１００４を削除し、クラスタ１００４のすべての子エンティティ４，１３を集合Ｘに追加する。この場合、集合Ｘは「Ｘ＝｛４，１３｝」となる。
【０２１４】
また、関係グラフ変換部４０６は、集合Ｙをｂのみを要素とする集合｛ｂ｝とする。集合Ｙの要素にクラスタが含まれる場合、関係グラフ変換部４０６は、集合Ｙからその要素を削除し、その要素のすべての子エンティティまたは子クラスタを集合Ｙに追加する。関係グラフ変換部４０６は、集合Ｙからクラスタがなくなるまで、この処理を繰り返す。
【０２１５】
例えば、ｂを「ｂ＝１００５」とし、集合Ｙを「Ｙ＝｛１００５｝」とすると、関係グラフ変換部４０６は、分割結果１０００（図１３参照）を参照して、集合Ｙからクラスタ１００５を削除し、クラスタ１００５のすべての子エンティティ８，１２を集合Ｙに追加する。この場合、集合Ｙは「Ｙ＝｛８，１２｝」となる。
【０２１６】
つぎに、関係グラフ変換部４０６は、関係グラフ情報４３０（図８参照）から、関係元が集合Ｘ｛４，１３｝に含まれ、関係先が集合Ｙ｛８，１２｝に含まれる行を抽出し、抽出した行の重みの合計を算出する。この重みの合計を重みｗとする。行が抽出されなかった場合は、重みｗを「ｗ＝０」とする。ここでは、関係グラフ情報４３０（図８参照）から、関係元が「１３」であり、関係先が「１２」の行が抽出され、重みｗは「ｗ＝１／２」となる。
【０２１７】
そして、関係グラフ変換部４０６は、重みｗが「ｗ＞０」であれば、関係グラフ情報Ｒに、関係元がａのクラスタＩＤ、関係先がｂのクラスタＩＤ、重みがｗである行を追加する。以降、関係グラフ変換部４０６は、集合Ｖからすべての順序対を抽出するまで、上述した一連の処理を繰り返す。
【０２１８】
この結果、処理対象のクラスタ集合｛１００４，１００５，１００６｝についての関係グラフ情報Ｒが生成される。ここで、処理対象のクラスタ集合についての関係グラフ情報Ｒの具体例について説明する。
【０２１９】
図２３は、処理対象のクラスタ集合についての関係グラフ情報Ｒの具体例を示す説明図である。図２３において、関係グラフ情報Ｒは、関係元と関係先と重みとを対応付けて示す。例えば、関係グラフ情報Ｒの１行目のレコードでは、関係元クラスタが「１００４」、関係先クラスタが「１００４」である。この重みは、関係グラフ情報４３０（図８参照）から、関係元が「１３」であり関係先が「４」である行が１行抽出され、その重みの合計である「１／２」となる。
【０２２０】
図２４は、処理対象のクラスタ集合のグラフ表現例を示す説明図である。図２４において、楕円の図形は、クラスタを示す。ここでは、図２３に示した関係グラフ情報Ｒに対応する部分グラフが示されている。クラスタ間の矢印は、依存関係を示す。矢印の始端を関係元クラスタとし、矢印の終端（矢印の先）を関係先クラスタとする。
【０２２１】
（第１の粒度調整機能）
つぎに、粒度調整機能付き分割部２２０１の第１の粒度調整機能について説明する。第１の粒度調整機能では、粒度調整パラメータｒを含む目的関数を用いて、処理対象のクラスタ集合を複数のクラスタに分割する場合について説明する。
【０２２２】
具体的には、例えば、粒度調整機能付き分割部２２０１は、下記式（９）を用いて、処理対象のクラスタ集合を複数のクラスタに分割する。下記式（９）は、望ましいエンティティをクラスタ内に収めたときに値が増加し、望ましくないエンティティをクラスタ内に収めたときに値が減少する目的関数を拡張したものである。
【０２２３】
ｆg（Ｇ（Ｃ），Ｐ（Ｃ），ｒ）＝Ｇ（Ｃ）−ｒ・Ｐ（Ｃ）    ・・・（９）
【０２２４】
上記式（９）において、Ｃは、分割を表す。Ｇ（Ｃ）は、望ましいエンティティをクラスタ内に収めたときに値が増加するゲインを表す。Ｐ（Ｃ）は、望ましくないエンティティをクラスタ内に収めたときに値が増加するペナルティを表す。ｒは、非負実数の粒度調整パラメータを表す。粒度調整パラメータｒの初期値は、任意に設定可能であり、例えば、「１」である。
【０２２５】
ここで、上記式（９）のＧ（Ｃ）を下記式（１０）とし、上記式（９）のＰ（Ｃ）を下記式（１１）とする。
【０２２６】
【数３】
2015179452.tif 000005
【０２２７】
【数４】
2015179452.tif 000006
【０２２８】
この場合、上記式（２）は、「ＱDW（Ｃ）＝Ｇ（Ｃ）−Ｐ（Ｃ）」となり、これをｆ（Ｇ（Ｃ），Ｐ（Ｃ））と表すと、上記式（９）が導出される。すなわち、上記式（９）は、目的関数ＱDWを、粒度調整パラメータｒを持つ目的関数ｆg（Ｇ（Ｃ），Ｐ（Ｃ），ｒ）で置き換えたものである。
【０２２９】
上記式（９）は、粒度調整パラメータｒの値を１から増加させることで、ペナルティＰ（Ｃ）への寄与が増すと、クラスタにエンティティが収まり難くなり、クラスタ内のエンティティ数が減少しクラスタ数が増加するという特徴を有する。一方、上記式（９）は、粒度調整パラメータｒの値を１から減少させることで、ペナルティＰ（Ｃ）への寄与が減ると、クラスタにエンティティが収まり易くなり、クラスタ内のエンティティ数が増加しクラスタ数が減少するという特徴を有する。
【０２３０】
粒度調整機能付き分割部２２０１は、上記式（９）に含まれる粒度調整パラメータｒの値を、ペナルティＰ（Ｃ）への寄与が減少するように変更する。具体的には、例えば、粒度調整機能付き分割部２２０１は、粒度調整パラメータｒに、予め設定された減少値を減少させる。減少値は、任意に設定可能であり、例えば、「０．１」である。
【０２３１】
そして、粒度調整機能付き分割部２２０１は、処理対象のクラスタ集合についての関係グラフ情報Ｒに基づいて、粒度調整パラメータｒの値が変更された上記式（９）を最大化するように、処理対象のクラスタ集合を複数のクラスタに分割する。この際、粒度調整機能付き分割部２２０１は、処理対象のクラスタ集合の各クラスタを、処理対象のエンティティ集合の各エンティティと同様に扱う。
【０２３２】
また、粒度調整機能付き分割部２２０１は、処理対象のクラスタ集合を分割した結果、クラスタ数がクラスタ上限数を超えている場合には、再度、粒度調整パラメータｒの値を変更して、処理対象のクラスタ集合の分割を繰り返す。
【０２３３】
ただし、粒度調整パラメータｒの値を調整しても、それ以上改善できない、すなわち、それ以上クラスタ数を減少できない場合には、粒度調整機能付き分割部２２０１は、処理対象のクラスタ集合の分割を終了する。具体的には、例えば、粒度調整機能付き分割部２２０１は、粒度調整パラメータｒの値が、予め設定された上限値を超えると、それ以上改善不能と判断して、処理対象のクラスタ集合の分割を終了することにしてもよい。上限値は、任意に設定可能であり、例えば、「１０」である。
【０２３４】
また、ここでは、粒度調整パラメータｒを線形探索で求める場合について説明したが、これに限らない。例えば、粒度調整機能付き分割部２２０１は、粒度調整パラメータｒの初期値から下限値までの範囲で二分探索するなど他の探索方法を用いて粒度調整パラメータｒを求めることにしてもよい。
【０２３５】
（第２の粒度調整機能）
つぎに、粒度調整機能付き分割部２２０１の第２の粒度調整機能について説明する。第２の粒度調整機能では、粒度調整パラメータｒを用いて、処理対象のクラスタ集合についての関係グラフ情報Ｒを補正し、補正後の関係グラフ情報Ｒに基づいて、処理対象のクラスタ集合を複数のクラスタに分割する場合について説明する。
【０２３６】
粒度調整機能付き分割部２２０１は、処理対象のクラスタ集合のクラスタ間の依存関係に関する重みを、同一クラスタ間の依存関係に関する重みが相対的に減少するように補正する。具体的には、例えば、粒度調整機能付き分割部２２０１は、処理対象のクラスタ集合についての関係グラフ情報Ｒに対して、自己ループ辺（ある頂点から出て同一の頂点に戻ってくる辺）の重みに粒度調整パラメータｒを乗じる補正を行う。
【０２３７】
粒度調整パラメータｒは、非負実数である。粒度調整パラメータｒの初期値は、任意に設定可能であり、例えば、「１」である。ここで、粒度調整パラメータｒを初期値から、ある減少値分減少させると、自己ループ辺の重みが減少する。減少値は、任意に設定可能であり、例えば、「０．１」である。
【０２３８】
自己ループ辺はクラスタ内に含まれるため、異なるクラスタ間を結ぶ辺の重みは相対的に大きくなる。このため、分割後のクラスタに複数の子クラスタが収まりやすくなり、分割後のクラスタ数が減少する。この場合、粒度調整機能付き分割部２２０１は、自己ループ辺以外の辺の重みは補正しない。
【０２３９】
一例として、図２３に示した関係グラフ情報Ｒを例に挙げると、粒度調整機能付き分割部２２０１は、関係元と関係先とが同じクラスタＩＤの行の重みに対して、粒度調整パラメータｒを乗じる。例えば、粒度調整パラメータｒを、初期値「１」から減少値「０．１」減少させた「０．９」であるとする。
【０２４０】
この場合、粒度調整機能付き分割部２２０１は、関係グラフ情報Ｒの関係元と関係先とが同じクラスタＩＤの１行目の重み「１／２」に対して「ｒ＝０．９」を乗じる。また、粒度調整機能付き分割部２２０１は、関係グラフ情報Ｒの関係元と関係先とが同じクラスタＩＤの５行目の重み「１／２」に対して「ｒ＝０．９」を乗じる。
【０２４１】
そして、粒度調整機能付き分割部２２０１は、補正後の関係グラフ情報Ｒに基づいて、上記式（２）を最大化するように、処理対象のクラスタ集合を複数のクラスタに分割する。この際、粒度調整機能付き分割部２２０１は、処理対象のクラスタ集合の各クラスタを、処理対象のエンティティ集合の各エンティティと同様に扱う。
【０２４２】
また、粒度調整機能付き分割部２２０１は、処理対象のクラスタ集合を分割した結果、クラスタ数がクラスタ上限数を超えている場合には、再度、粒度調整パラメータｒの値を変更して、処理対象のクラスタ集合の分割をやり直す。
【０２４３】
ただし、粒度調整パラメータｒの値を調整しても、それ以上改善できない、すなわち、クラスタ上限数の基準を満たすことができない場合には、粒度調整機能付き分割部２２０１は、処理対象のクラスタ集合の分割を終了する。具体的には、例えば、粒度調整機能付き分割部２２０１は、粒度調整パラメータｒの値が、予め設定された下限値以下となると、それ以上改善不能と判断して、処理対象のクラスタ集合の分割を終了することにしてもよい。下限値は、任意に設定可能であり、例えば、「０」である。
【０２４４】
また、ここでは、粒度調整パラメータｒを線形探索で求める場合について説明したが、これに限らない。例えば、粒度調整機能付き分割部２２０１は、粒度調整パラメータｒの初期値から下限値までの範囲で二分探索するなど他の探索方法を用いて粒度調整パラメータｒを求めることにしてもよい。
【０２４５】
また、粒度調整機能付き分割部２２０１は、上記式（２）の換わりに、上記式（９）を用いて、処理対象のクラスタ集合を複数のクラスタに分割することにしてもよい。ただし、この場合、上記式（９）に含まれる粒度調整パラメータｒの値は固定値（例えば、１）とする。
【０２４６】
（ソフトウェア分割装置１００のソフトウェア分割処理手順）
つぎに、実施の形態２にかかるソフトウェア分割装置１００のソフトウェア分割処理手順について説明する。ここでは、上述した粒度調整機能付き分割部２２０１の第２の粒度調整機能を用いて、処理対象のクラスタ集合を複数のクラスタに分割する場合を例に挙げて説明する。
【０２４７】
図２５および図２６は、実施の形態２にかかるソフトウェア分割装置１００のソフトウェア分割処理手順の一例を示すフローチャートである。図２５のフローチャートにおいて、まず、ソフトウェア分割装置１００は、関係抽出処理を実行する（ステップＳ２５０１）。関係抽出処理の具体的な処理手順については、図１５に示した関係抽出処理の具体的処理手順と同様のため説明を省略する。
【０２４８】
そして、ソフトウェア分割装置１００は、重み算出処理を実行する（ステップＳ２５０２）。重み算出処理の具体的な処理手順については、図１６に示した重み算出処理の具体的処理手順と同様のため説明を省略する。
【０２４９】
つぎに、ソフトウェア分割装置１００は、ソフトウェアＳＷの構成要素であるすべてのエンティティが一つのクラスタに属するものとする（ステップＳ２５０３）。そして、ソフトウェア分割装置１００は、エンティティ上限数を超えるクラスタ内のエンティティ集合を処理対象のエンティティ集合として選択する（ステップＳ２５０４）。
【０２５０】
つぎに、ソフトウェア分割装置１００は、関係グラフ情報４３０から、選択した処理対象のエンティティ集合のレコードを抽出することにより、新たな関係グラフ情報Ｒを生成する（ステップＳ２５０５）。
【０２５１】
そして、ソフトウェア分割装置１００は、生成した新たな関係グラフ情報Ｒに基づいて、クラスタリング処理を実行する（ステップＳ２５０６）。クラスタリング処理の具体的な処理手順については、図１７に示したクラスタリング処理の具体的処理手順と同様のため説明を省略する。
【０２５２】
つぎに、ソフトウェア分割装置１００は、第１統合処理を実行する（ステップＳ２５０７）。第１統合処理は、処理対象のエンティティ集合の分割結果を、全体の分割結果に統合する処理である。第１統合処理の具体的な処理手順については、図１９に示した統合処理の具体的処理手順と同様のため説明を省略する。
【０２５３】
そして、ソフトウェア分割装置１００は、最下位階層のすべてのクラスタがエンティティ上限数の基準を満たしている、または、改善不能か否かを判断する（ステップＳ２５０８）。ここで、いずれかのクラスタがエンティティ上限数の基準を満たしておらず、かつ、そのクラスタが改善不能ではない場合（ステップＳ２５０８：Ｎｏ）、ソフトウェア分割装置１００は、ステップＳ２５０４に戻る。
【０２５４】
一方、最下位階層のすべてのクラスタがエンティティ上限数の基準を満たしている、または、改善不能である場合（ステップＳ２５０８：Ｙｅｓ）、ソフトウェア分割装置１００は、図２６に示すステップＳ２６０１に移行する。
【０２５５】
図２６のフローチャートにおいて、まず、ソフトウェア分割装置１００は、すべてのクラスタがクラスタ上限数の基準を満たしている、または、改善不能か否かを判断する（ステップＳ２６０１）。
【０２５６】
ここで、いずれかのクラスタがクラスタ上限数の基準を満たしておらず、かつ、そのクラスタが改善不能ではない場合（ステップＳ２６０１：Ｎｏ）、ソフトウェア分割装置１００は、クラスタ上限数を超えるクラスタ内のクラスタ集合を処理対象のクラスタ集合として選択する（ステップＳ２６０２）。
【０２５７】
そして、ソフトウェア分割装置１００は、関係グラフ変換処理を実行する（ステップＳ２６０３）。関係グラフ変換処理は、処理対象のクラスタ集合についての新たな関係グラフ情報Ｒを生成する処理である。関係グラフ変換処理の具体的な処理手順については、図２７および図２８を用いて後述する。
【０２５８】
つぎに、ソフトウェア分割装置１００は、粒度調整パラメータｒを変更する（ステップＳ２６０４）。具体的には、例えば、ソフトウェア分割装置１００は、粒度調整パラメータｒから、予め設定された減少値（例えば、０．１）を減算することにより、粒度調整パラメータｒを変更する。粒度調整パラメータｒの初期値は、例えば、「１」である。
【０２５９】
そして、ソフトウェア分割装置１００は、処理対象のクラスタ集合についての関係グラフ情報Ｒに対して、自己ループ辺の重みに粒度調整パラメータｒを乗じることにより、関係グラフ情報Ｒの補正を行う（ステップＳ２６０５）。
【０２６０】
つぎに、ソフトウェア分割装置１００は、補正後の関係グラフ情報Ｒに基づいて、処理対象のクラスタ集合を複数のクラスタに分割するクラスタリング処理を実行する（ステップＳ２６０６）。クラスタリング処理の具体的な処理手順については、図１７に示したクラスタリング処理の具体的処理手順と同様のため説明を省略する。
【０２６１】
そして、ソフトウェア分割装置１００は、分割して得られたクラスタ数がクラスタ上限数の基準を満たしている、または、改善不能か否かを判断する（ステップＳ２６０７）。ここで、クラスタ上限数の基準を満たしておらず、かつ、改善不能ではない場合（ステップＳ２６０７：Ｎｏ）、ソフトウェア分割装置１００は、ステップＳ２６０４に戻る。
【０２６２】
一方、クラスタ上限数の基準を満たしている、または、改善不能である場合（ステップＳ２６０７：Ｙｅｓ）、ソフトウェア分割装置１００は、第２統合処理を実行して（ステップＳ２６０８）、ステップＳ２６０１に戻る。第２統合処理は、処理対象のクラスタ集合の分割結果を、全体の分割結果に統合する処理である。第２統合処理の具体的な処理手順については、図２９を用いて後述する。
【０２６３】
また、ステップＳ２６０１において、すべてのクラスタがクラスタ上限数の基準を満たしている、または、改善不能である場合（ステップＳ２６０１：Ｙｅｓ）、ソフトウェア分割装置１００は、全体の分割結果を分割結果４４０として出力して（ステップＳ２６０９）、本フローチャートによる一連の処理を終了する。
【０２６４】
これにより、ソフトウェアＳＷを分割して得られるクラスタ内のエンティティ数がエンティティ上限数以下となるまで、または、改善不能となるまで、クラスタ内のエンティティ集合の分割を再帰的に繰り返すことができる。また、同一親クラスタを持つクラスタ集合のクラスタ数がクラスタ上限数以下となるまで、または、改善不能となるまで、粒度調整パラメータｒを変更しながら当該クラスタ集合の分割を繰り返すことができる。
【０２６５】
＜関係グラフ変換処理手順＞
つぎに、図２６のステップＳ２６０３に示した関係グラフ変換処理の具体的な処理手順について説明する。
【０２６６】
図２７および図２８は、関係グラフ変換処理の具体的処理手順の一例を示すフローチャートである。図２７のフローチャートにおいて、まず、ソフトウェア分割装置１００は、空の行からなる関係グラフ情報Ｒを生成する（ステップＳ２７０１）。そして、ソフトウェア分割装置１００は、処理対象のクラスタ集合からなる集合Ｖを特定する（ステップＳ２７０２）。
【０２６７】
つぎに、ソフトウェア分割装置１００は、集合Ｖからクラスタの順序対ａ，ｂを抽出する（ステップＳ２７０３）。そして、ソフトウェア分割装置１００は、集合Ｘをａのみを要素とする集合｛ａ｝として（ステップＳ２７０４）、集合Ｘの要素にクラスタが含まれるか否かを判断する（ステップＳ２７０５）。
【０２６８】
ここで、集合Ｘの要素にクラスタが含まれる場合（ステップＳ２７０５：Ｙｅｓ）、ソフトウェア分割装置１００は、集合Ｘからクラスタの要素を削除する（ステップＳ２７０６）。そして、ソフトウェア分割装置１００は、削除した要素のすべての子エンティティまたは子クラスタを要素として集合Ｘに追加して（ステップＳ２７０７）、ステップＳ２７０５に戻る。
【０２６９】
また、ステップＳ２７０５において、集合Ｘの要素にクラスタが含まれない場合（ステップＳ２７０５：Ｎｏ）、ソフトウェア分割装置１００は、集合Ｙをｂのみを要素とする集合｛ｂ｝として（ステップＳ２７０８）、集合Ｙの要素にクラスタが含まれるか否かを判断する（ステップＳ２７０９）。
【０２７０】
ここで、集合Ｙの要素にクラスタが含まれる場合（ステップＳ２７０９：Ｙｅｓ）、ソフトウェア分割装置１００は、集合Ｙからクラスタの要素を削除する（ステップＳ２７１０）。そして、ソフトウェア分割装置１００は、削除した要素のすべての子エンティティまたは子クラスタを要素として集合Ｙに追加して（ステップＳ２７１１）、ステップＳ２７０９に戻る。
【０２７１】
また、ステップＳ２７０９において、集合Ｙの要素にクラスタが含まれない場合（ステップＳ２７０９：Ｎｏ）、ソフトウェア分割装置１００は、図２８に示すステップＳ２８０１に移行する。
【０２７２】
図２８のフローチャートにおいて、まず、ソフトウェア分割装置１００は、オリジナルの関係グラフ情報４３０（図８参照）から、関係元が集合Ｘに含まれ、関係先が集合Ｙに含まれる行を抽出する（ステップＳ２８０１）。そして、ソフトウェア分割装置１００は、抽出した行の重みの合計を重みｗとして算出することにより、重みｗを算出する（ステップＳ２８０２）。行が抽出されなかった場合は、ソフトウェア分割装置１００は重みｗを「ｗ＝０」とする。
【０２７３】
つぎに、ソフトウェア分割装置１００は、算出した重みｗが「０」より大きいか否かを判断する（ステップＳ２８０３）。ここで、重みｗが「０」以下の場合（ステップＳ２８０３：Ｎｏ）、ソフトウェア分割装置１００は、ステップＳ２８０５に移行する。
【０２７４】
一方、重みｗが「０」より大きい場合（ステップＳ２８０３：Ｙｅｓ）、ソフトウェア分割装置１００は、関係グラフ情報Ｒに、関係元がａのクラスタＩＤ、関係先がｂのクラスタＩＤ、重みがｗである行を追加する（ステップＳ２８０４）。そして、ソフトウェア分割装置１００は、集合Ｖから抽出されていない未抽出のクラスタの順序対があるか否かを判断する（ステップＳ２８０５）。
【０２７５】
ここで、未抽出のクラスタの順序対がある場合（ステップＳ２８０５：Ｙｅｓ）、ソフトウェア分割装置１００は、図２７に示したステップＳ２７０３に戻る。一方、未抽出のクラスタの順序対がない場合（ステップＳ２８０５：Ｎｏ）、ソフトウェア分割装置１００は、関係グラフ変換処理を呼び出したステップに戻る。
【０２７６】
これにより、処理対象のクラスタ集合についての関係グラフ情報Ｒを生成することができる。
【０２７７】
＜第２統合処理手順＞
つぎに、図２６のステップＳ２６０８に示した第２統合処理の具体的な処理手順について説明する。
【０２７８】
図２９は、第２統合処理の具体的処理手順の一例を示すフローチャートである。図２９のフローチャートにおいて、まず、ソフトウェア分割装置１００は、分割元のクラスタをクラスタＡとする（ステップＳ２９０１）。分割元のクラスタは、図２６のステップＳ２６０２において選択された処理対象のクラスタ集合を含むクラスタ、すなわち、クラスタ上限数の基準を満たしていないクラスタである。
【０２７９】
そして、ソフトウェア分割装置１００は、図２６のステップＳ２６０６において得られた分割結果の各クラスタ（部分集合）に、全体で未使用のクラスタＩＤを割り当てる（ステップＳ２９０２）。つぎに、ソフトウェア分割装置１００は、得られた分割結果のうちの未選択のクラスタをクラスタＸとして選択する（ステップＳ２９０３）。
【０２８０】
そして、ソフトウェア分割装置１００は、クラスタＸの子クラスタのうちの未選択の子クラスタを選択する（ステップＳ２９０４）。クラスタＸの子クラスタとは、クラスタＸの子となるクラスタ、すなわち、クラスタＸ内のクラスタである。
【０２８１】
つぎに、ソフトウェア分割装置１００は、全体の分割結果から、選択した子クラスタの該当する行を抽出する（ステップＳ２９０５）。そして、ソフトウェア分割装置１００は、抽出した行の親クラスタＩＤをクラスタＸのクラスタＩＤに置き換える（ステップＳ２９０６）。
【０２８２】
つぎに、ソフトウェア分割装置１００は、クラスタＸの子クラスタのうち選択されていない未選択の子クラスタがあるか否かを判断する（ステップＳ２９０７）。ここで、未選択の子クラスタがある場合（ステップＳ２９０７：Ｙｅｓ）、ソフトウェア分割装置１００は、ステップＳ２９０４に戻る。
【０２８３】
一方、未選択の子クラスタがない場合（ステップＳ２９０７：Ｎｏ）、ソフトウェア分割装置１００は、全体の分割結果に、「子エンティティ／クラスタＩＤ」がクラスタＸのクラスタＩＤ、「親クラスタＩＤ」がクラスタＡのクラスタＩＤである行を追加する（ステップＳ２９０８）。
【０２８４】
そして、ソフトウェア分割装置１００は、得られた分割結果のうち選択されていない未選択のクラスタがあるか否かを判断する（ステップＳ２９０９）。ここで、未選択のクラスタがある場合（ステップＳ２９０９：Ｙｅｓ）、ソフトウェア分割装置１００は、ステップＳ２９０３に戻る。
【０２８５】
一方、未選択のクラスタがない場合（ステップＳ２９０９：Ｎｏ）、ソフトウェア分割装置１００は、第２統合処理を呼び出したステップに戻る。これにより、全体の分割結果に、処理対象のクラスタ集合の分割結果を統合することができる。
【０２８６】
なお、上述した説明では、粒度調整機能付き分割部２２０１の第２の粒度調整機能を用いる場合を例に挙げて説明したが、粒度調整機能付き分割部２２０１の第１の粒度調整機能を用いることにしてもよい。この場合、例えば、図２６に示したステップＳ２６０４では、ソフトウェア分割装置１００は、粒度調整パラメータｒに減少値（例えば、０．１）を減じることにより、粒度調整パラメータｒを変更する。粒度調整パラメータｒの初期値は、例えば、「１」である。また、ソフトウェア分割装置１００は、ステップＳ２６０５における関係グラフ情報Ｒの補正は行わない。
【０２８７】
また、ステップＳ２６０６では、ソフトウェア分割装置１００は、上記式（２）の換わりに、上記式（９）を用いてクラスタリング処理を行う。このため、図１８に示した重み付き有向モジュラリティ最大化処理では、モジュラリティ評価関数ＱDWの換わりに、目的関数ｆgの評価を行うことになる。
【０２８８】
以上説明したように、実施の形態２にかかるソフトウェア分割装置１００によれば、同一親クラスタを持つ複数のクラスタのクラスタ数がクラスタ上限数を超えていることに応じて、複数のクラスタを処理対象のクラスタ集合として選択することができる。また、ソフトウェア分割装置１００によれば、処理対象のクラスタ集合に属するエンティティ間の依存関係に関する重みに基づいて、処理対象のクラスタ集合のクラスタ間の依存関係に関する重みを算出することができる。これにより、処理対象のクラスタ集合についての関係グラフ情報Ｒを生成することができる。
【０２８９】
また、ソフトウェア分割装置１００によれば、分割後のクラスタ数が少なくなるように、処理対象のクラスタ集合を複数のクラスタに分割することができる。この際、ソフトウェア分割装置１００は、処理対象のクラスタ集合についての関係グラフ情報Ｒに基づいて、同一クラスタ内のクラスタ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、処理対象のクラスタ集合を分割することができる。
【０２９０】
これにより、クラスタ数がクラスタ上限数を超えるクラスタをその子クラスタの集合として扱い、上述した性質（ｉ）〜（ｉｉｉ）を満たし、かつ、分割後のクラスタ数が少なくなるように、子クラスタの集合を複数のクラスタに分割することができる。
【０２９１】
具体的には、例えば、ソフトウェア分割装置１００によれば、上記式（９）に含まれる粒度調整パラメータｒの値をペナルティＰ（Ｃ）への寄与が減少するように変更することができる。そして、ソフトウェア分割装置１００によれば、処理対象のクラスタ集合についての関係グラフ情報Ｒに基づいて、変更した粒度調整パラメータｒの値を含む上記式（９）を最大化するように、処理対象のクラスタ集合を分割することができる。
【０２９２】
これにより、処理対象のクラスタ集合のクラスタ数がクラスタ上限数以下となるまで、上記式（９）に含まれる粒度調整パラメータｒを変更しながら、処理対象のクラスタ集合の分割を繰り返すことができる。この結果、同一親クラスタを持つクラスタ集合のクラスタ数を、人間がクラスタ間の関係を理解できる程度の数に抑えることができる。
【０２９３】
また、例えば、ソフトウェア分割装置１００によれば、処理対象のクラスタ集合のうちの同一クラスタ間の依存関係に関する重みに粒度調整パラメータｒを乗じて、同一クラスタ間の依存関係に関する重みが相対的に減少するように関係グラフ情報Ｒを補正することができる。そして、ソフトウェア分割装置１００によれば、補正した関係グラフ情報Ｒに基づいて、上記式（２）を最大化するように、処理対象のクラスタ集合を分割することができる。
【０２９４】
これにより、処理対象のクラスタ集合のクラスタ数がクラスタ上限数以下となるまで、同一クラスタ間の依存関係に関する重みに乗じる粒度調整パラメータｒを変更しながら、処理対象のクラスタ集合の分割を繰り返すことができる。この結果、同一親クラスタを持つクラスタ集合のクラスタ数を、人間がクラスタ間の関係を理解できる程度の数に抑えることができる。
【０２９５】
これらのことから、ソフトウェア分割装置１００によれば、ソースファイルの数が数千本を超えるような大規模なソフトウェアであっても、人間が直感的かつ容易に理解できる程度の小規模な単位にソフトウェアを分割することができる。これにより、例えば、ソフトウェアの再構築やウェブサービス化などのために、再利用可能なソフトウェア部品として切り出す範囲を、低コストかつ低工数で決定することが可能となる。また、例えば、ソフトウェアの開発・保守の工数を割り当てる単位や、ソフトウェアの品質管理を行う単位を、低コストかつ低工数で決定することが可能となる。
【０２９６】
ここで、図３０を用いて、ソースファイル（クラス）の数が２０００本を超えるあるオープンソースソフトウェアを、ソフトウェア分割装置１００により分割した場合の実例について説明する。ここでは、クラスタ上限数は「３０」に設定され、エンティティ上限数は「５０」に設定されている。
【０２９７】
図３０は、ソフトウェア分割例を示す説明図である。図３０において、表３００１には、オープンソースソフトウェアから分割されたクラスタの内部クラスタ数が多い順に示されている。内部クラスタ数は、同一親クラスタを持つクラスタの数である。ただし、図３０では、オープンソースソフトウェアから分割された複数のクラスタのうちの内部クラスタ数が多い上位２０個を抜粋して表示している。
【０２９８】
表３００１によれば、全クラスタ数は１９６と多いが、一つのクラスタ内のクラスタ数はクラスタ上限数の３０以下となっており、クラスタ間の関係を人間が容易に把握できる程度にオープンソースソフトウェアが分割されていることがわかる。
【０２９９】
また、表３００２には、オープンソースソフトウェアから分割された複数のクラスタのうち最下位階層のクラスタの内部エンティティ数が多い順に示されている。内部エンティティ数は、クラスタ内のエンティティ数である。ただし、図３０では、最下位階層のクラスタのうち内部エンティティ数が多い上位２０個を抜粋して表示している。
【０３００】
表３００２によれば、一つのクラスタ内のエンティティ数がほぼエンティティ上限数の５０以下に収まっていることがわかる。また、上位５個のクラスタについては、図２に示したような、これ以上分割不可能な単純な構造である。このため、クラスタ内のエンティティ間の関係を人間が容易に把握できる程度にオープンソースソフトウェアが分割されていることがわかる。
【０３０１】
なお、本実施の形態で説明したソフトウェア分割方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本ソフトウェア分割プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また、本ソフトウェア分割プログラムは、インターネット等のネットワークを介して配布してもよい。
【０３０２】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０３０３】
（付記１）コンピュータに、
ソフトウェアの構成要素群であるエンティティ群から処理対象のエンティティ集合を選択したことに応じて、前記エンティティ群のエンティティ間の依存関係により特定される当該依存関係に関する重みに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、前記処理対象のエンティティ集合を複数のクラスタに分割し、
分割した前記複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えていることに応じて、前記クラスタ内のエンティティ集合を前記処理対象のエンティティ集合として選択する、
処理を実行させることを特徴とするソフトウェア分割プログラム。
【０３０４】
（付記２）前記コンピュータに、
分割した前記複数のクラスタのクラスタ数が、予め記憶されたクラスタ上限数を超えていることに応じて、前記複数のクラスタに属するエンティティ間の依存関係に関する重みに基づいて、前記複数のクラスタのクラスタ間の依存関係に関する重みを算出し、
算出した前記複数のクラスタのクラスタ間の依存関係に関する重みに基づいて、前記クラスタ数よりも分割後のクラスタ数が少なくなるように、前記複数のクラスタを、同一クラスタ内のクラスタ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように複数のクラスタに分割する、
処理を実行させることを特徴とする付記１に記載のソフトウェア分割プログラム。
【０３０５】
（付記３）前記コンピュータに、
同一クラスタ内のクラスタ間の依存関係に関する重みの合計が当該合計の期待値よりも大きい場合に高くなる目的関数に含まれる、前記目的関数の値を減少させるペナルティに寄与するパラメータの値を、前記ペナルティへの寄与が減少するように変更する処理を実行させ、
前記複数のクラスタを分割する処理は、
前記複数のクラスタを、前記複数のクラスタのクラスタ間の依存関係に関する重みに基づいて、変更した前記パラメータの値を含む前記目的関数を最大化するように複数のクラスタに分割することを特徴とする付記２に記載のソフトウェア分割プログラム。
【０３０６】
（付記４）前記コンピュータに、
算出した前記複数のクラスタのクラスタ間の依存関係に関する重みを、前記複数のクラスタのうちの同一クラスタ間の依存関係に関する重みが相対的に減少するように補正し、
前記複数のクラスタを分割する処理は、
補正した前記複数のクラスタのクラスタ間の依存関係に関する重みに基づいて、前記複数のクラスタを、同一クラスタ内のクラスタ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように複数のクラスタに分割することを特徴とする付記２に記載のソフトウェア分割プログラム。
【０３０７】
（付記５）前記処理対象のエンティティ集合を選択する処理は、
前記クラスタ内のエンティティ集合のうちのいずれかのエンティティが他のエンティティからそれぞれ呼び出される場合には、前記クラスタ内のエンティティ集合を前記処理対象のエンティティ集合として選択しないことを特徴とする付記１〜４のいずれか一つに記載のソフトウェア分割プログラム。
【０３０８】
（付記６）コンピュータに、
ソフトウェアの構成要素群であるエンティティ群から処理対象のエンティティ集合を選択したことに応じて、前記エンティティ群のエンティティ間の依存関係により特定される当該依存関係に関する重みに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、前記処理対象のエンティティ集合を複数のクラスタに分割し、
分割した前記複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えていることに応じて、前記クラスタ内のエンティティ集合を前記処理対象のエンティティ集合として選択する、
処理を実行させるソフトウェア分割プログラムを記録したことを特徴とする前記コンピュータに読み取り可能な記録媒体。
【０３０９】
（付記７）ソフトウェアの構成要素群であるエンティティ群から処理対象のエンティティ集合を選択したことに応じて、前記エンティティ群のエンティティ間の依存関係により特定される当該依存関係に関する重みに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、前記処理対象のエンティティ集合を複数のクラスタに分割し、分割した前記複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えていることに応じて、前記クラスタ内のエンティティ集合を前記処理対象のエンティティ集合として選択する制御部、
を有することを特徴とするソフトウェア分割装置。
【０３１０】
（付記８）コンピュータが、
ソフトウェアの構成要素群であるエンティティ群から処理対象のエンティティ集合を選択したことに応じて、前記エンティティ群のエンティティ間の依存関係により特定される当該依存関係に関する重みに基づいて、同一クラスタ内のエンティティ間の依存関係に関する重みの合計が当該合計の期待値よりも高くなるように、前記処理対象のエンティティ集合を複数のクラスタに分割し、
分割した前記複数のクラスタのうちのいずれかのクラスタ内のエンティティ数が、予め記憶されたエンティティ上限数を超えていることに応じて、前記クラスタ内のエンティティ集合を前記処理対象のエンティティ集合として選択する、
処理を実行することを特徴とするソフトウェア分割方法。
【符号の説明】
【０３１１】
１００  ソフトウェア分割装置
４０１  取得部
４０２  関係抽出部
４０３  分割制御部
４０４  出力部
４０５  選択部
４０６  関係グラフ変換部
４０７  分割部
４１０  ソースコードＤＢ
４２０  クラスタ粒度基準情報
４３０，Ｒ  関係グラフ情報
４４０，１０００  分割結果
【図１】
2015179452.tif 000007
【図２】
2015179452.tif 000008
【図３】
2015179452.tif 000009
【図４】
2015179452.tif 000010
【図５】
2015179452.tif 000011
【図６】
2015179452.tif 000012
【図７】
2015179452.tif 000013
【図８】
2015179452.tif 000014
【図９】
2015179452.tif 000015
【図１０】
2015179452.tif 000016
【図１１】
2015179452.tif 000017
【図１２】
2015179452.tif 000018
【図１３】
2015179452.tif 000019
【図１４】
2015179452.tif 000020
【図１５】
2015179452.tif 000021
【図１６】
2015179452.tif 000022
【図１７】
2015179452.tif 000023
【図１８】
2015179452.tif 000024
【図１９】
2015179452.tif 000025
【図２０】
2015179452.tif 000026
【図２１】
2015179452.tif 000027
【図２２】
2015179452.tif 000028
【図２３】
2015179452.tif 000029
【図２４】
2015179452.tif 000030
【図２５】
2015179452.tif 000031
【図２６】
2015179452.tif 000032
【図２７】
2015179452.tif 000033
【図２８】
2015179452.tif 000034
【図２９】
2015179452.tif 000035
【図３０】
2015179452.tif 000036