情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

SArF：依存関係に基づいてフィーチャーを集める
ソフトウェアクラスタリング
小林 健一1,a)

松尾 昭彦1松下 誠2

井上 克郎3

受付日 2022年8月1日, 採録日 2022年10月4日

概要：ソフトウェアを複数の小単位に分割するソフトウェアクラスタリング技術は，ソフトウェアシステ
ムを理解するうえで重要な役割を果たす．本論文では，静的な依存関係情報に基づいてソフトウェアのフィーチャをクラスタに集めるソフトウェアクラスタリングアルゴリズム「SArF」を提案する．SArF の
特徴はフィーチャを集めることと，自動化である．ソフトウェアクラスタリング作業の多くは，遍在モ
ジュールの除去作業など人間の支援を必要とするが，SArF はこれら人間の作業が不要である．SArF の特徴を実現するために，依存関係に対してフィーチャを共有する確からしさを表す専念度（Dedication）ス
コアを定義し，スコアで重み付けられた依存関係グラフをクラスタリングするためにモジュラリティ最大化法と組み合わせた．ケーススタディでフィーチャが集められることを示し，公開リポジトリから利用度順に収集した 35 ソフトウェア 304 バージョンからなるデータセットを用いて SArF の評価を行い，クラスタリング品質，安定度，実行時間の面で SArF が既存のアルゴリズムに対し優れることを示した．
キーワード：ソフトウェアクラスタリング，ソフトウェアアーキテクチャ復元，プログラム理解，依存解析

SArF: Feature-gathering Dependency-based Software Clustering
Kenichi Kobayashi1,a)Akihiko Matsuo1

Makoto Matsushita2

Katsuro Inoue3

Received: August 1, 2022, Accepted: October 4, 2022

Abstract: Software clustering that decomposes a software system into plural sub-units is one of the important techniques to comprehend software systems. In this paper, we proposed a novel dependency-based
software clustering algorithm, SArF. SArF has two characteristics. First, SArF gathers relevant softwarefeatures or functionalities into a cluster. Second, SArF further automates software comprehension processes
by eliminating the need of the omnipresent-module-removing step which requires human interactions. To
achieve them, we deﬁned the Dedication score to measure the likelihood that a dependency shares the samefeatures, and we utilized modularity maximization method to cluster directed graphs weighted by the Dedication score. A case study shows that SArF could successfully gather relevant features into a cluster. Extensive
comparative evaluations using 35 popular open-source software systems (total 304 versions) show that SArF
is superior to existing dependency-based software clustering studies in terms of clustering quality, stability
and speed.
Keywords: software clustering, software architecture reconstruction, program comprehension, dependency
analysis

1
2

3

a)

富士通株式会社
Fujitsu Limited, Kawasaki, Kanagawa 211–8588, Japan
大阪大学大学院情報工学研究科
Graduate School of Information Science and Technology,
Osaka University, Suita, Osaka 565–0871, Japan
南山大学理工学部ソフトウェア工学科
Faculty of Science and Technology, Nanzan University,
Nagoya, Aichi 466–8673, Japan
kenichi@fujitsu.com

c 2023 Information Processing Society of Japan

1. はじめにソフトウェアシステムは長年の保守や機能追加を経るにつれてドキュメントの陳腐化や知識の散逸が起こる．そのため，アーキテクチャ理解はソフトウェア保守の重要な位置を占める [1]．ソフトウェアクラスタリングはソフト

831

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

ウェアの構成要素であるモジュール（ソースファイルやク

動化していることも特徴である．SArF は適用可能性を高め

ラス，メソッド，データエンティティなど）をクラスタリるために収集が容易な静的依存関係（呼出関係，参照関係，

ングすることで，ソフトウェアを複数の小単位に分割して継承関係など）のみを入力情報として用いている．依存情

その潜在構造を明らかにするアーキテクチャ理解のための報を用いるソフトウェアクラスタリングの既存のアプロー技術である．ソフトウェアクラスタリングによる分割結果

チ [2], [4], [5], [6] では，利用者が満足のいくまで精錬されは，対象ソフトウェアのアーキテクチャ知識や高レベルなた結果を得るためには，分割結果を人間が分析してフィー

抽象ビューとして利用できる．

ドバックし反復するという介入が必要である [1], [7], [8]．

ソフトウェアクラスタリングの用途の 1 つは，過去にド介入を要する大きな要因が「遍在モジュール（omnipresent

キュメント化されたアーキテクチャと現状のアーキテク

module）」[9] の存在である．遍在モジュールとは，システ

チャの乖離を把握し是正することである．たとえば，設計

ムの複数個所と接続しながら，特定の 1 サブシステムには当初のパッケージ構造（本論文での「パッケージ」は Java

属さないモジュールと定義される [2]．遍在モジュールは依言語のようなモジュールの集合体を指す）をそのままに，存情報においてノイズとして振る舞うため [9]，多くの研究

安易にクラスを追加する拡張を続けた場合，パッケージ構が結果を精錬するために遍在モジュールを除去することが造と実態が乖離していく．ソフトウェアクラスタリングの有益であるとしている [2], [10], [11], [12]．遍在モジュール

出力は実態を映すビューであり，パッケージ構造を実態にの自動除去についてはいくつかの提案 [4], [9], [13], [14] が合わせるリファクタリングを可能にする．別の用途としてあるが，遍在モジュールの除去の実施判断や自動除去ツー

は，ドキュメント化されていない観点のビューを新たなルのパラメータは人間が決定する必要があり，さらに遍在知識として加えることがあげられる．アーキテクチャのモジュール除去の妥当性の確認は手動で行う必要があるな

観点は複数あるため [1]，開発者が求める観点とは異なる

ど，実際には半自動化にとどまっていた．SArF は遍在モ

パッケージ構造がとられることがしばしばある．たとえ

ジュールの存在に影響を受けにくいよう設計されたアルゴ

ば，ウェブフレームワークによってアーキテクチャが規定

リズムであり，遍在モジュールを他のモジュールとアルゴされ，それに合わせてパッケージ構造が強制される場合な

リズム上で同等に扱えるようにすることで，除去などの特どである．このような場合，パッケージ構造から得られな

別な措置が不要になり，結果，クラスタリングに際して人い非自明な知識が抽出できるソフトウェアクラスタリング

手の除去作業やパラメータ調整がなくなり自動化が達成さが有用である．

れる．

現在までに，様々な目的を持ったソフトウェアクラスタ

SArF のフィーチャを集める特徴と，遍在モジュール除リングの研究が多く行われており，各々が目的に沿った去作業を不要にする特徴は，依存関係の重要度を表す専念

アーキテクチャビューを提供する．たとえば，モジュール度（Dedication）スコアを定義し，専念度スコアで重み付性を高めるように構造を見直す目的には，クラスタ内の凝けられた依存グラフをコミュニティ発見の研究分野で用い集性が高くクラスタ間の結合性が低い集合を探索するアルられるモジュラリティ最大化法 [15] を用いることにより実

ゴリズム [2] が向いている．このように，開発者は自らの現された．

目的に沿ったアルゴリズムを選ぶことができる．

SArF がフィーチャを集めることは，文献 [16] で開発へ

我々は依存関係に基づく新しいソフトウェアクラスタリのインタビューを含む実例で示し，複数の既存研究と比較

ングアルゴリズム「SArF」（Software Architecture Finder

して SArF が人間の介入なしで高い精度を出すことを示しの略）を提案する．SArF の目的はフィーチャを実装するた．本論文では妥当性を増すため，客観的な選択規準で十モジュールを同じクラスタに集めることである．本研究で分な数のソフトウェアを公開リポジトリから取得して実験は「フィーチャ」をフィーチャロケーション（機能捜索）の評価を行った．また，文献 [16] ではモジュラリティ最大化

研究の文脈での定義，すなわち，「システム外のユーザから法のアルゴリズムとして Newman アルゴリズム [15], [17]引き起こされうる観測可能な機能（つまり，非機能要件をを用いていたが，より優れるとされる Louvain 法 [18] に置含まない）」[3] という意味で用いる．たとえばデータ処理

き換えた．単なる置き換えでは安定度の低下を招いたが，でのフィルタリング機能や，GUI でのダイアログ機能など

Louvain 法のアルゴリズムに修正を加えることで安定度をである．フィーチャを集めることで，既存手法では得られ同等に保つことができ，クラスタリング品質の向上と実行なかった機能に基づいた分割結果のビューを得ることがで時間の短縮が実現された．

きる．出力結果の各クラスタに対して，どのようなフィー

本論文の以降の構成は次のとおりである．2 章で関連研チャであるかの解釈や，フィーチャに包含関係や重複関係究を示し，3 章でソフトウェアクラスタリングアルゴリズがある場合の対応付けなどは，結果を利用する開発者に委

ム SArF の提案を行い，4 章では実験計画について述べ，ねられる．

SArF はソフトウェアクラスタリングを高いレベルで自c 2023 Information Processing Society of Japan

5 章でケーススタディを示し，6 章で実験結果を示し，議論する．7 章で妥当性への脅威を示し，8 章で結論を述べる．

832

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

2. 関連研究2.1 ソフトウェアクラスタリングアルゴリズム

目的には依存情報を用いて凝集度を最大化する手法が向く，などである．SArF は，依存情報を用いたグラフクラス
タリングという従来の枠組みに加えて，専念度という評価

ソフトウェアクラスタリングの既存研究を，まず入力情指標を導入して依存関係に重みづけることにより，フィー報の観点で述べると，依存情報や構造情報が用いられる

チャを集めるという新しい目的を持つことが特徴である．

ことが多い．Bunch [2] は最適化によるグラフクラスタリ
ングアプローチであり，内部に高い凝集度を持ち外部と2.2 ソフトウェアクラスタリングの評価

低い結合度を持つクラスタを発見することを目的とする．

ソフトウェアクラスタリングアルゴリズムを評価するた

ACDC [4] はグラフパターンを用いるアプローチであり，クめに一般的に用いられる規準はオーソリティ準拠度（Au-

ラスタリングのために「グラフの支配ノードと被支配ノー

thoritativeness）である．これは，アルゴリズムが出力しドのモジュールをまとめる」など，複数の発見的ルールをた分割結果と，対象ソフトウェアのオーソリティ（権威者，用いる．関連する名前を持つモジュールをまとめるために熟知者）が作成したオーソリティ分割結果（Authoritative

命名規則を利用する手法もある [19]．自然言語処理により，Decomposition）との間の類似度または距離として定義さソースコード中の識別子やコメントなどの意味的情報を用れる．MoJo [26] はオーソリティ準拠度の指標で，2 つのいる手法もある [20], [21]．システムの振舞いを理解する

分割を一致させるために必要な最小の move 操作と join 操

ために，実行トレースなどの動的情報を用いてアーキテク

作（図 3）の合計数である．MoJo の欠点を改善した指標

チャを復元する手法 [22] やクラスタリングを行う手法 [12]MoJoFM が提案され [27]，階層的性質を持つ分割を評価すもある．

るため，up 操作を考慮する指標 UpMoJo [28] が提案され次に，方法論の観点で述べると，階層クラスタリングをている．

用いる手法 [10], [21], [23]，k-means などの非階層クラスタ

1 つのソフトウェアには複数の観点がありうるため，正リングを用いる手法 [20]，パターンマッチングを用いる手

解となる分割結果も複数個共存しうる．よって，アルゴリ

法 [4]，グラフクラスタリングを用いる手法 [2], [5], [7], [24]

ズムが 1 つのオーソリティ分割結果にはそれほど準拠しななどがある．Bittencourt らは 4 つのグラフクラスタリン

くても，他のオーソリティ分割結果には準拠する可能性がグ手法の比較を行っている [24]．グラフクラスタリングはある．Shtern らは目的が異なるクラスタリングアルゴリズ

辺の密度が高いサブグラフを見つけるクラスタリングであムは直接的には比較できない場合があることを指摘し [29]，り，辺として依存関係のような直接的な情報を用いるとク複数の指標を用いた評価の枠組みを提案した [30]．

ラスタの解釈が容易で結果を直接利用できる．特に初期にWu ら [23] は，ソフトウェアクラスタリングが備えるべ提案された Bunch は多くの改良が提案され，コンポーネ

き性質の規準，オーソリティ準拠度・NED・安定度（Sta-

ントの再利用性の指標を遍在モジュール除去に用いるもbility）を設定し，複数のクラスタリングアルゴリズムをの [14]，ユーザの目的により適合させるため多目的最適化

比較した．NED は極端な結果を出力しないことの指標でを用いるもの [7]，対話的遺伝アルゴリズムを用いるもの [8]あるが，定義が恣意的と指摘されている [20]．安定度は小などがある．

さな変更に対して結果が大きく変化しない性質の指標であ

近年では，生物学的ネットワークやソーシャルネット

る．Lutellier らは MoJoFM など 4 つのアーキテクチャ比

ワークの応用において，コミュニティ発見のグラフクラ較指標を用いて文献 [2]，[4]，[11]，[21] など 9 つの手法のスタリング技術が急速に発展している．Girvan-Newman

比較を行った [31]．本研究の評価はこれら既存の枠組みに（GN）アルゴリズム [25] は，高い Edge Betweenness 指標則って行う．

値を持つ辺を切断することによってグラフクラスタリング
をトップダウン的に行うアプローチである．GN アルゴリ

3. 手法

ズムは小さなソフトウェアでは良好な性能が得られたが，本章では提案手法 SArF アルゴリズムについて述べる．

大きなソフトウェアでは性能が低下したという評価が報SArF アルゴリズムは，依存関係の辺を重み付けする専念

告されている [5], [24]．モジュラリティ最大化法の発端と度スコアと，その重み付き依存グラフをモジュラリティ最なった Newman アルゴリズム [15] は，グラフのノードや大化法でクラスタリングすることの 2 点からなる．

クラスタを併合するボトムアップアプローチであり，良好な性能が得られたと報告されている [6]．

3.1 専念度（Dedication）スコア

最後に，目的の観点で述べると，各クラスタリング手法

専念度スコアは「依存するモジュールと依存されるモはその入力情報（依存情報・構造情報，意味的情報，動的ジュールが同じフィーチャを共有する確からしさ」を表す，

情報）で大まかに目的が分かれ，各々が採用した方法論に依存関係グラフの辺に与える重みである．これは，依存さよって特徴づけられる．たとえば，モジュール性を高める

れるモジュールが依存しているモジュールのフィーチャ

c 2023 Information Processing Society of Japan

833

情報処理学会論文誌

図 1

Vol.64 No.4 831–845 (Apr. 2023)

専念度スコアの計算例（単純な場合）

Fig. 1 Example of dedication score (simple case).
図 2 専念度スコアの計算例（階層関係がある場合）の実装にどれほど専念しているかを意味している．たとえば，図 1 左はモジュール A がモジュール X に依存していることを表しているが，もし X が A にのみ専念しているな
らば，X は A と同じフィーチャを共有している可能性が高い．一方，図 1 右のように，多くのモジュールがモジュー
ル Y に依存しているならば，Y は特定のモジュールに専念
しているとはいい難く，それらとフィーチャを共有している可能性は低い．
上記の考え方に基づく専念度スコアの定義を述べる．依存関係の集合を有向グラフとして扱うものとして，頂点はモジュール（ソースファイル，クラス，メソッド，データ
エンティティなど）を表す．A が B に依存するとき，有向辺 (A, B) が存在するとする．単純な場合には，辺 (A, B)の専念度スコア D(A, B) の定義は，fanin(B) を頂点 B の入次数として，次式となる．

1
D(A, B) =fanin(B)Fig. 2 Example of dedication score (multi-level case).

3.2 モジュラリティ最大化法
専念度スコアが効果を発揮するクラスタリングアルゴリ
ズムを選択する場合，その要件は，専念度スコアの高い依存関係をクラスタ内に有し，かつ，遍在モジュールのような専念度スコアの低いノイズとなる依存関係に影響を受けないことである．ここで，有意な依存関係の規準として，専念度スコアがその期待値を上回る度合いを用いる．それに適する手法としてモジュラリティ最大化法 [15] を採用する．
モジュラリティ最大化法はコミュニティ発見のアプロー
チの 1 つであり，目的関数モジュラリティ Q [32] を最大化するグラフの分割を求めるものである．モジュラリティ Q
は重み付きグラフに自然に拡張され，後に次式のとおりモ
ジュラリティ QD として有向グラフに拡張された [33], [34]．

(1)
QD =

図 1 の例の各専念度は D(A, X) = 1，D(B1 , Y ) = 1/50 となる．遍在モジュールはこの Y の形態をとるため，遍在モ
ジュールへの専念度スコアはつねに小さい．
クラスとメンバといった階層関係が利用できる場合にkiOUT kjIN
1 
Aij −
δ(ci , cj )
W
W

(3)

i,j

ここで，W はグラフ内のすべての有向辺の重みの合計であり，Aij はグラフの隣接行列の要素すなわち辺 (i, j) の重みであり，kiOUT は頂点 i から出る辺の重みの合計であは，メンバよりクラスをモジュールの単位としてクラスタ

り，kjIN は頂点 j へ入る辺の重みの合計であり，cx は頂点

リングを行う方が解釈や管理が容易である．メンバレベル

x が属するクラスタであり，δ(ci , cj ) は ci = cj の場合に 1の依存関係グラフの情報を集約してクラスレベルとする場となりそれ以外の場合に 0 となるクロネッカーのデルタ関合の専念度スコア DM (A, B) の定義は次式となる．

DM (A, B) =m∈MB←A1
faninX (m) · mX (B)

数である．式 (3) 中の項 (kiOUT kjIN/W ) は辺 (i, j) の重みの期待値であり，項 Aij は実際の重みである．専念度スコ(2)

アが辺の重みとなるので，式 (3) の括弧の中の式は前述の規準に一致している．

ここで，A と B はクラス，MB←A は B のメンバのうち A のモジュラリティ QD はクラスタ内の辺がその期待値よりメンバが依存するものの集合である．faninX (m) はメンバ

どれだけ高い密度を持っているかの程度と解釈され，高m が属するクラス以外から m に依存するメンバ数である．

い値ほど良いクラスタリング結果を意味する．モジュラ

mX (B) は B のメンバのうち B の外から依存されるものの

リティ Q の最適化は NP 困難である [35] が，良い近似を数であり，クラス全体の専念度を分け合う数となる．クラ

与える解法が存在している．我々は文献 [16] で Newman

スレベルグラフの専念度スコアは対応するメンバレベルグのアルゴリズム [15] を用いた．その計算量は，|V | をグラ

ラフと式 (2) を用いて計算される．式 (2) の例を図 2 に示

フの頂点数とすると，典型的に O(|V | log2 |V |) と高速であす．mX (X) = 3，faninX (X.init) = 1，faninX (X.set) = 1，

る [17]．本論文では Louvain 法 [18] を用いる．Louvain 法

faninX (X.use) = 3 である．クラス A からクラス X への専は非常に高速（典型的に O(|V | log |V |)），かつ，貪欲法で念度 DM (A, X) = 7/9 のうち，メソッド A.a からメソッドありながら他の計算量の大きい手法と同等以上に良質の解X.init への分は 1/3，A.a から X.set への分は 1/3，A.f かを得ることができる [36]．以降，「SArF」は Louvain 法をら X.use への分は 1/9 である．

用いた SArF を表す．比較のため，Newman アルゴリズム

c 2023 Information Processing Society of Japan

834

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)を用いた以前の SArF は「SArF(N)」と表す．
以下に，Louvain 法の手順概略を示す（詳細は文献 [18]）．

1. 各頂点を 1 つだけ含むクラスタを頂点数と同数作る．
2. すべての頂点を順に走査し，各頂点を QD の増加が最大になるクラスタへ移動する．

3. 2. の走査を QD が増加しなくなるまで繰り返す．
4. クラスタを頂点とする新しいグラフを作り，QD が増加する限り，1. に戻る．

Louvain 法はそのままソフトウェアクラスタリングに適用するのは不適である．ソフトウェアクラスタリングでは
図 3

結果は決定的かつ安定度が高いことが望まれるのだが，オmove/join 操作と MoJoFM

Fig. 3 Move/join operations and MoJoFM.

リジナルの Louvain 法は手順 2. の走査が乱数順であるため実行ごとに結果が非決定的であり，安定度も若干低くな
る．SArF では決定的な結果を得るために Louvain 法の走点からソフトウェアを精査するケーススタディを 5 章で行査順を，(1) 重み付き次数の昇順に従い，(2) 同位の場合はう．また，RQ1 と RQ2，RQ3 を検証するために，6 章で隣接頂点の重み付き次数の合計値の昇順に従う，とする固は多数の OSS を対象とした実験評価を行う．リサーチク

定順に変更する．走査順をグラフの構造に基づいて定める

エスチョンの検証を 6.4 節でまとめる．

ことで，似たアーキテクチャでは似た走査順となり安定度が高まる効果が得られる．この固定順走査への変更の影響について 6.3.6 項で調べる．

4.2 性能指標
性能評価の軸として，
「品質」
「安定度」
「実行時間」の 3軸を設定し，「品質」をさらに「オーソリティ準拠度」「適切

3.3 SArF アルゴリズム
我々が提案する SArF アルゴリズムは専念度スコアとモ
ジュラリティ最大化法の組合せである．このアルゴリズムは決定的であり，同じ入力に対して同じ結果を出力する．

なクラスタ数」の 2 つの規準で測る．広く用いられる Wuらの評価の枠組み [23] を，批判 [20] のある NED を「適切なクラスタ数」に換える形で用いた．
オーソリティ準拠度の算出に必要となるオーソリティ分

このアルゴリズムの手順は以下のとおりである．

割結果の獲得は膨大な労力を要するため，既存研究のほと1. モジュール（クラス，メンバ，その他のエンティティ）んどが対象ソフトウェアのパッケージ階層をオーソリティ間の依存関係を対象のソフトウェアから抽出する．

分割結果の代替として利用している．我々も文献 [20]，[21]2. 抽出した情報から依存関係グラフを作成する．可能なと同様に，各パッケージをクラスタとし，サイズ 5 以下

らメンバレベルのグラフを抽出する．

3. 3.1 節で述べた手順で，依存関係グラフの専念度スコアを計算する．グラフがメンバレベルならば，クラスレ
ベルグラフにまとめあげる．

のクラスタを再帰的に親クラスタに併合することにより，パッケージ階層からオーソリティ分割結果の代替物を作成した．
ここで注意すべき点は，パッケージ階層から作成した

4. 3.2 節で述べた手順で，重み付き有向グラフのモジュラ

オーソリティ分割結果は，そのパッケージ階層の設計がど

リティ最大化法によりグラフのクラスタリングを行う．

の観点によって行われたかに依存するということである．

4. 実験計画

たとえば，SArF の評価にはフィーチャの観点で分割されたオーソリティ分割結果が望ましいため，5 章のケースス

本章ではリサーチクエスチョンを設定し，それに答える

タディではそのようなオーソリティ分割結果が得られるソために必要な性能指標と性能測定の方法について説明する．

フトウェアを選んでいる．一方，6 章では無作為にソフトウェアを選ぶ大規模な評価を行っており，この場合は特定

4.1 リサーチクエスチョンの観点に片寄ることのない任意かつ多様な観点を寄せ集め

本論文では以下のリサーチクエスチョンを設ける．

た「平均的な基準」による評価となる．このような「平均• RQ1「SArF はフィーチャを集められるか?」的な基準」により複数のソフトウェアクラスタリング手法• RQ2「SArF はソフトウェアクラスタリングをより自を比較しなければならないのは，現状のソフトウェアクラ動化できたか?」• RQ3「SArF はソフトウェアクラスタリングにおいて良い特徴を備えているか?」

RQ1 と RQ2 を検証するために，フィーチャに基づく観c 2023 Information Processing Society of Japan

スタリングの研究の共通課題である．我々は評価の妥当性を増すために，「平均的な基準」による評価と，自身の観点（フィーチャ）に沿ったケーススタディをあわせた二段
構成の評価を実施している．

835

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

図 4 性能測定手順

Fig. 4 Measurement procedure.

オーソリティ準拠度の指標としては MoJoFM [27] をべて Java で記述されており，入力情報は jar ファイルの用 い た ．MoJoFM は 2 つ の 分 割 結 果 の 類 似 度 で あ り ，みを使用する．jar ファイル中の対象ソフトウェアに属さ

MoJoFM(C, A) = (1 − mno(C, A)/Nmaxops ) × 100%で定ないクラス（例：ant ならば org.apache.tools.zip パッ義される．C は出力分割結果，A はオーソリティ分割結

ケージ以下）は評価対象外とする．まず，jar ファイルか果，mno(C, A) は C を A へ変換するのに最小限必要なら Javassist *1 を基に開発されたバイトコード解析器を用

move 操作と join 操作の合計数，Nmaxops は最大操作数

いてメンバレベルとクラスレベルの依存関係グラフを抽出（= maxX mno(X, A)）である．高い MoJoFM は C が A

する．抽出する依存関係はメソッド呼出・フィールドリーに近いことを意味する．例を図 3 に示す．

ド・フィールドライト・継承・クラス型参照の 5 種であり，

MoJoFM はクラスタ数が過多の場合に過大評価を起こ

これは高いクラスタリング品質を得るうえで十分な組合せ

すバイアスがある．図 3 の例から分かるように，クラスタ

である [37]．単一のソースファイルにクラスが複数含まれを誤って 2 分した場合 join 操作 1 回分のペナルティを受ける場合，それらが同じグループに属することは自明なため，るのに対し，誤って 2 つのクラスタを併合した場合には多すべて最初のトップレベルクラスに属するものと見なす．

数の move 操作分のペナルティを受ける．ペナルティに対クラスレベルグラフはメンバレベルグラフを図 2 のように称性がないため，過多分割の傾向を持つアルゴリズムが高まとめあげることで作成する．依存関係を持たないクラス

く評価される．よって，バイアス補正のため，クラスタ数

は評価対象外とする．オーソリティ分割結果はソフトウェが適切であるかの規準を加える必要がある．

アのパッケージ階層から生成されるため，評価の公正を保適切なクラスタ数の指標として，オーソリティ分割結果

つため，パッケージ情報は依存関係グラフから除去しておを規準としたクラスタ数の相対誤差（RE, Relative Error）

く．次に，各クラスタリングアルゴリズムを実行する．比と絶対相対誤差（MRE, Magnitude of RE）を用いる．本較評価で用いたすべてのクラスタリングツールは既定値の論文を通し，K はアルゴリズムが出力した分割結果のクラパラメータで実行する．最後に，出力された分割に対し測スタ数，Ka はオーソリティ分割結果のクラスタ数を表す．

定された前述の性能指標を収集する．手順中は実行時間もMRE は RE の絶対値，RE は RE = (K − Ka)/Ka と定義測定する．

される．MRE が小さいほど，オーソリティ分割結果からみて適切なクラスタ数やクラスタ粒度といえる．

5. ケーススタディ

安定度は，対象ソフトウェアの第 i バージョンの分割

本章では，RQ1「SArF はフィーチャを集められるか?」

結果を Ci とし，その前のバージョンの分割を Ci−1 としの検証を主目的とし，2 つのソフトウェアを用いてケースたとき，Stability(Ci ) = MoJoQ(Ci−1 , Ci ) で定義される．

スタディを実施する．先述のとおり，フィーチャを集める

MoJoQ [26] はモジュール数が N のとき，MoJoQ(C, A) =ソフトウェアクラスタリングの検証にはフィーチャの観点(1 − min(mno(C, A), mno(A, C))/N ) × 100%と定義され，に基づくオーソリティ分割結果が必要となる．そのため，

MoJoFM と異なり対称な類似度である．

本ケーススタディでは既存のアーキテクチャ知識を用いて

実行時間は，図 4 に示された期間の経過時間である．すオーソリティ分割結果を作成した．また，1 番目のケース

なわち，SArF では専念度スコアの計算とクラスタリング

スタディでは，RQ2「SArF はソフトウェアクラスタリンの合計実行時間を測り，他のアルゴリズムについてはクラグをより自動化できたか?」の検証のために，遍在モジュー

スタリングの実行時間のみを測る．

ルがクラスタリング結果に及ぼす結果についても調べる．

4.3 性能測定手順
性能測定手順を図 4 に示す．評価対象ソフトウェアはすc 2023 Information Processing Society of Japan

*1

http://www.javassist.org/

836

情報処理学会論文誌

図 5

Vol.64 No.4 831–845 (Apr. 2023)

Weka 3.0 のアーキテクチャ

Fig. 5 Architecture of Weka 3.0.

図 6 Distribution Map による可視化の例

Fig. 6 Example of distribution map.

5.1 ケーススタディ 1：Weka 3.0
本節では，SArF がフィーチャを集めることができるかどうかについて直観的理解を得るため，データマイニン
グツール Weka のバージョン 3.0 を題材として可視化を用いたケーススタディを示す．Weka 3.0 はアーキテクチャが文書化されている [38] ため，既存研究でよく用いられる [6], [12]．そのほとんどのパッケージがフィーチャに一致する [12] ため，パッケージを元にしたオーソリティ分割
結果は SArF の目的に合致する．このケーススタディの目
的は，SArF と他のクラスタリングアルゴリズムの結果を比較し，SArF がフィーチャと一致する分割を出力するこ

図 7

Weka のクラスタリング結果の可視化

Fig. 7 Visualization of clustering results on Weka.

との実例を示すことである．文献 [16] により詳細な解析がある．
ここでは Weka バージョン 3.0.6 の weka パッケージ以下

した結果を可視化した例を図 7 に示す．図 7 (a) は SArFの結果である．各クラスタが core 以外のパッケージにほすべて 142 個のクラスを対象とした．図 5 は，文献 [12]，ぼ一致していることが分かる．これは，SArF が効果的に[38] と jar ファイルの情報を利用して作成した Weka のアークラスを対応するフィーチャに分割していることを意味

キテクチャを表すパッケージダイアグラムである．core

し，MoJoFM 値が 72.9%と高いことに整合する．なお，最以外のパッケージは Weka のフィーチャに対応する．

も正確な結果が得られた場合であっても，一般的にオーソ

クラスタリング結果をオーソリティ分割結果との差異とリティ準拠度は 100%より低い値になる．なぜなら，オーして可視化するため図 6 に例を示す Distribution Map [39]

ソリティ準拠度が 100%となるためには，指標の基準となの技法を用いる．オーソリティ分割結果はパッケージダイ

るオーソリティ分割結果も理想的なものが与えられる必要アグラムで表し，クラスタリング結果は各クラスの色とアがあるが，現実にはそのようなオーソリティ分割結果が得

ルファベットでクラスタを識別することで表す．オーソられることはまずないためである．すなわち，基準とする

リティ分割結果とクラスタリング出力が一致するならば，

オーソリティ分割結果ごとに上限値が存在することにな

パッケージは個別の色で占められ（パッケージ 1），異なる [16]．

るならばパッケージ内に混色が生じたり（パッケージ 3），

図 7 (a) には，クラスタの一部がパッケージと一致して同じ色（クラスタ B）が複数のパッケージにまたがったりいない箇所がある．たとえば，白「G」クラスタは複数のする．

パッケージに散逸している．この誤分類の原因は大きく

4.3 節の手順に従ってクラスタリングアルゴリズムを実行

c 2023 Information Processing Society of Japan

2 つある．1 つ目は，複数のフィーチャに関わるクラスが837情報処理学会論文誌

表 1

Vol.64 No.4 831–845 (Apr. 2023)

表 2

Weka 3.0 における性能測定結果

Table 1 Performance measurement results on Weka 3.0.

DMTool における性能測定結果

Table 2 Performance measurement results on DMTool.

90.9%であり差は少なく，両方とも高い性能が得られている．他方，ACDC では除去ありで 85.9%に対し，除去なしあるときに，どちらに分類されるかが，パッケージ設計者

で 55.6%であり，遍在モジュール除去の効果が大きいことのそれと，SArF のそれで一致しない場合である．2 つ目が分かる．Bunch では除去ありで 70.1%に対し，除去なし

は，フィーチャの中に小さなフィーチャが入れ子になってで 59.6%であり，遍在モジュール除去の効果はあることがいる場合である．この例では，classifier パッケージは認められるが，除去しても良い性能は得られていない．た「決定木以外の判別分析（回帰分析も含む）」というフィーだし，この比較では Bunch の性能が悪いのか，フィーチャ

チャに対応するが，SArF はその中から「回帰分析」といに基づく評価に向かないのかの二者を区別することはできうフィーチャを白「G」クラスタとして取り出している．

ない．

比較対象アルゴリズム ACDC と Bunch の結果を図 7 (b)と図 7 (c) に示す．また，SArF の結果とあわせて表 1 第 1

5.2 ケーススタディ 2：商用データマイニングツール

列に示す．
「Ka」列はオーソリティ分割結果のクラスタ数

本ケーススタディでは，フィーチャに基づくオーソリを表す．
「K 」列は各アルゴリズムが出力した分割のクラス

ティ分割を，対象ソフトウェアの有知識者によって作成

タ数を表す．アルゴリズム間で最良の MoJoFM 値を太字

し，SArF の効果を調べることを目的とする．対象ソフトで表す．ACDC と Bunch に共通して，少数のクラスタ（赤ウェアとして富士通で開発されたデータマイニング製品「A」と青「B」）が filters パッケージと core パッケージ（DMTool と仮称）を用い，2 つのオーソリティ分割結果をを介して複数のパッケージにまたがっている．これから両用意した．第 1 の分割 ADpackage はパッケージ階層からパッケージ中の遍在モジュールが，クラスタリングアルゴ

自動生成したものであり，第 2 の分割 ADfeature はこの製

リズムが正しく働くことを阻んでいることが観察できる．

品の開発者がフィーチャの観点で作成したものである．

これら既存のアルゴリズムでは，望ましい結果を得るため

このソフトウェアはウェブ 3 層アーキテクチャをとっておに遍在モジュールを除去する人間の介入が必要となっていり，パッケージの設計もそれに沿っているため，ADpackage

た．ACDC の結果には非常に多く（クラスタ数 16）の小と ADfeature は異なる観点に基づく分割となっている．

さなクラスタが散らばっており，一方 Bunch の結果では複アーキテクチャと 2 つの分割についてのこれ以上の詳細

数のパッケージが 1 つのクラスタに融合しており，両者ではここでは割愛するが，文献 [16] にその詳細が述べられ，クラスタ粒度の不整合が起きていることが分かる．

ケーススタディ 1 と同様の Distribution Map 技法を用い

次に，遍在モジュール除去が結果に及ぼす効果を調べる．

た可視化が示されている．

表 1 第 2 行「Weka 3.0.6（feature, OM 除去）
」は，
「Weka

この 2 つの分割を用いた性能評価結果を表 2 に示す（各3.0.6」から遍在モジュールを除去したものを対象とした列の意味は表 1 に同じ）．第 1 行（ADpackage）はクラス

クラスタリング結果である．遍在モジュール除去のためタリング結果に対し ADpackage をオーソリティ分割としに，既存研究 [6], [12] と同じくクラスタリング前に依存関て評価したものであり，第 2 行（ADfeature）は同じクラ係グラフから filters パッケージと core パッケージをスタリング結果に対し ADfeature をオーソリティ分割としすべて取り除いた．比較のため，表 1 第 3 行「Weka 3.0.6て評価したものである．

(feature)」として，第 1 行と同じ「Weka 3.0.6」を対象とし

表の第 1 行と第 2 行を比較すると，ACDC と Bunch はたクラスタリング結果に対し，filters パッケージと core

大きな性能差はないが，SArF は ADfeature において大幅パッケージを除いて MoJoFM 値を計算したものを用意しな性能向上があることが分かる．また，SArF は他のアルた（残ったパッケージはすべてフィーチャに基づくパッゴリズムに比べて性能が高い．これは，SArF の出力結果

ケージ）．第 2 行と第 3 行を比較することで，遍在モジューが開発者の作成したフィーチャに基づくオーソリティ分割

ルによってクラスタリングが阻害される様を観察できる．

に近いことを意味し，RQ1「SArF はフィーチャを集めら

まず，SArF は遍在モジュール除去を行った場合（第 2 行）

れるか?」を肯定的に支持する．また，これらの事実はオーと行わなかった場合（第 3 行）の MoJoFM 値が 97.0%とソリティ分割がどの観点に基づくかによって，クラスタリ

c 2023 Information Processing Society of Japan

838

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

ングアルゴリズムの性能評価値に差が出るという従来からの知見 [29] を補強する．

SArF のクラスタリング結果の妥当性を確認するために，
DMTool の開発者がクラスタリング結果と自身のソフト
ウェア知識と照合したところ，SArF のクラスタリング結
果と ADfeature との差異については，フィーチャの包含関係や重複関係の扱いの差とに帰結されるとし，この結果がフィーチャの観点に基づく分割として妥当であると判断を
下した．

6. 評価
この章では，リサーチクエスチョンの検証のため，クラ
図 10 実行時間測定結果

スタリングアルゴリズムの比較評価を行い，議論する．

Fig. 10 Execution time results.

比 較 す る ク ラ ス タ リ ン グ ア ル ゴ リ ズ ム は ，SArF，SArF(N)，Newman アルゴリズム [6], [15]（以後 Newmanと略），代表的な既存研究である ACDC [4]，Bunch [2] であジョンを maven から取得したが，1.9.7 のみを評価対象とる．Newman を選んだ理由は Newman と SArF の主な差した．

が専念度であることから，SArF の専念度スコアが性能に最終的に，maven リポジトリから 35 本（うち 10 本は貢献するかを調べるためである．SArF と SArF(N) との比SourceForge で上位のアプリケーション）のソフトウェア

較は Louvain 法の導入による得失を調べるためである．

が選ばれ，計 304 バージョンを評価対象とした．その内訳
を表 3 の先頭列に示す．対象ソフトウェアの規模はクラ6.1 データセット
評価用データセットのソフトウェア群はバイアスを避けるため以下に述べる客観的規準で選んだ．代表的なソフト

ス数で数十から数千まで多岐にわたり，10 倍以上に成長したソフトウェアがあるなど，多様性のあるデータセットとなった．

ウェアリポジトリの 1 つである maven リポジトリ*2 から，以下の条件を満たすものを利用数（usages）順に取得した．

6.2 測定結果

条件 1：Java 言語で記述されアーキテクチャを持つ単独

全ソフトウェア全バージョンの jar ファイルを対象にのソフトウェア．ツールのコレクションや，API，ラッ

4.3 節の手順に従って性能測定を行った．結果を表 3，

パ，プラグイン，自身のアーキテクチャを持たない一図 8，図 9，図 10 に示す．SArF(N) の結果は SArF と大部のライブラリやフレームワークは対象外とする．こ差がないため，一部を除いて略した．

の条件の判定は人間が行う．

表 3 に各ソフトウェアの基本情報および，各アルゴリズ

条件 2：クラスが複数のパッケージに分散していること．

ムのクラスタリング品質（オーソリティ準拠度とクラスタ

1 つのパッケージに大部分のクラスが属すると，オー数）の測定結果を示す．各行は各ソフトウェアの対象バー

ソリティ分割結果として適切でない [16]．

ジョンの測定値の平均（クラス数のみ最小値と最大値）で

条件 3：安定度の評価のため，評価対象となるバージョ
ン数が 2 以上．

ある．
「Ka」列はオーソリティ分割結果のクラスタ数を表す．
「クラスタ数」の列の括弧の前の値は各アルゴリズム

maven リポジトリはビルドツール向けのリポジトリであが出力した分割のクラスタ数 K を表し，括弧の中の数字

るため，その利用数はライブラリに偏り，アプリケーショ

はその K の MRE を表す．比較に意味がある測定値（表 3

ンが少なくなる．この偏りの補正のため，別の代表的なソでは MoJoFM と MRE）についてはアルゴリズム間で最良

フトウェアリポジトリである SourceForge *3 においてダウのものを太字で表す（他の表も同様）．アルゴリズムごと

ンロード数が上位かつ前記の条件を満たすアプリケーショに，全ソフトウェア全バージョンについて測定した結果を，ンを maven リポジトリから取得するものに加えた．両リ

図 8 に (a) オーソリティ準拠度，(b) クラスタ数の相対誤

ポジトリに対する参照と取得は 2017 年 8 月に行われた．

差，(c) 安定度の箱ひげ図で示す．図 9 に Ka と K の散布

評価対象とするバージョンは冗長性を省くためメンテナ

図を示す．図 10 にクラス数と実行時間の散布図を示す．

ンスバージョンが複数あるものは最新のもののみを選ぶ．
たとえば ant の 1.9.x 系列は 1.9.0 から 1.9.7 までの 8 バー

6.3 議論*2

6.3.1 クラスタリング品質*3

https://mvnrepository.com/
https://sourceforge.net/

c 2023 Information Processing Society of Japan

クラスタリングの品質をオーソリティ準拠度と適切なク

839

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

表 3

クラスタリング品質測定結果（オーソリティ準拠度とクラスタ数）

Table 3 Quality measurement results (authoritativeness and number of clusters).

図 8

測定結果の箱ひげ図

Fig. 8 Box-plot of measurement results.

図 9 オーソリティ分割のクラスタ数 Ka とアルゴリズムの出力クラスタ数 K との比較

Fig. 9 Comparisons between Ka of authoritative decomposition and K of computed
decomposition.

c 2023 Information Processing Society of Japan

840

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

表 4

品質・安定度の比較

Table 4 Quality and stability comparison.

表 5 実行時間測定結果（抜粋）

Table 5 Execution time results (excerption).

表 4 の下段にまとめた．安定度の平均は SArF が統計的ラスタ数の 2 点で評価する．まず，オーソリティ準拠度

有意に他に優れる．SArF の安定度の変動が Newman のそを見る．表 3 の MoJoFM の結果から，SArF が最良（太れに比べて小さい．これは SArF に専念度スコアを導入し字）となることが多く（35 ソフトウェア中 21），ACDC とたことでバージョン間の重要でない変更に対して重みが減

Newman が最良となるものもある．MoJoFM の最良値はり，影響を受けにくくなった結果と考えられる．

ソフトウェアによって 40〜70 の値をとるが，5.1 節に述6.3.3 実行時間

べたとおり MoJoFM には上限値が存在する [16] ため，必実 行 時 間 の 計 測 環 境 は Xeon E5-1620v3 プ ロ セ ッ サ

ずしもこれらの品質が低いことを意味するものではない．

（3.50 GHz）で，JVM1.8 である．クラスタリングツール

図 8 (a) の箱ひげ図から，SArF と ACDC は，Newman やは ACDC と Bunch が Java 言語で，SArF と Newman はBunch に比べ安定した値となることが分かる．表 4 の上

Scala 言語で記述されており，アルゴリズム部は 1 スレッ段に比較結果をまとめた．MoJoFM の平均は SArF が他ドで実行される．記述言語による実行速度の差異はほぼな

より統計的有意に優れる．有意差検定には Wilcoxon の符

いが，ランタイム初期化時間は Scala の方が数百ミリ秒程

号付き順位検定（有意水準 5%）を用いた．これ以降の検度多い．言語とツールの影響を除くため，実行時間には初定も同じ．

期化時間を含めないものとした．

次に，適切なクラスタ数かどうかをみる．表 3 のクラ全ソフトウェア全バージョンの実行時間の散布図を

スタ数 K 自身は品質に関係はなく，K と Ka との絶対相

図 10 に示す．各アルゴリズムはクラス数 400 以下ま

対誤差 MRE の値が重要である．MRE が小さいほど適切ではおおむね 1 秒以内で終了し，大きな差は見られななクラスタ数といえる．これは SArF が最良となることがい．クラス数が 400 を超えると差が目立ち始める．ク

多く（35 ソフトウェア中 23），Newman と Bunch が最良ラス数に対する実行時間のオーダをグラフの傾きととなるものもある．ACDC は他と比べて MRE の値が格して可視化するために，図は両対数軸としている．図段と大きい．表 4 の中段に比較結果をまとめた．MRE のから明らかに，各アルゴリズムの実行時間のオーダは

平均は SArF が他より統計的有意に優れる．クラスタ数にBunch > ACDC > Newman > SArF(N) > SArF と分かついて可視化したものが図 9 のバージョンごとの Ka とる．特に，Bunch・ACDC と他の差異は顕著である．

K の散布図である．斜線 K = Ka の付近に測定点が分布

表 5 は典型的な実行時間を抜粋したものである．上 4（平均 RE  0）すればクラスタ数は適切，下に分布（平均行は前記の観測に符合する．下 3 行は，高速な SArF とRE < 0）すればクラスタ数過少 = クラスタサイズ過大，上SArF(N) の差を調べるために，1 万クラス超の規模のソフに分布（平均 RE > 0）すればクラスタ数過多 = クラスタ

トウェアをデータセットとは別に 3 つ用意したものの測定

サイズ過小である．ACDC が著しくクラスタ数過多になる結果である．SArF は数万クラス規模でも実行時間は数秒傾向が見て取れる．これは前述のケーススタディでも確認であるが，SArF(N) は数十秒かかり，差は明らかといえる．

された現象である．Newman は過少，Bunch はやや過少，

実際の利用シーンにおいては，クラスタリングツールをSArF は適切なクラスタ数を出力する傾向があるといえる．

1 回実行すれば完了する用途であれば実行時間は数十秒で図 8 (b) の箱ひげ図からも同じ結果が読み取れる．

も問題ないが，多くの用途では有用な成果物を得るために以上から，オーソリティ準拠度とクラスタ数の 2 つの評

インタラクティブな理解プロセスを反復する場合が多く，価規準で SArF のクラスタリング品質が高いといえる．こ

実行時間は数秒が限度であろう．また，統合化された自動の結果は，遍在モジュール除去など人手の前処理がない条化ツールの中でクラスタリングを探索的に繰り返す用途で件下のものなので，自動化を想定したものである．

は，実行時間が短いほどより効果が大きい．遅いアルゴリ

6.3.2 安定度

ズムでも有用な用途や場面は存在する．しかし，理解対象測定された安定度の分布を図 8 (c) に示し，比較結果を

c 2023 Information Processing Society of Japan

のソフトウェアが大規模になるほど反復回数は増加する傾841

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

表 6 SArF と SArF(N) の比較な性能の良さを表しているにすぎない．フィーチャの観

Table 6 Comparison of SArF and SArF(N).

点に基づくパッケージ階層を持つソフトウェアに対して，SArF の MoJoFM 値が特に高い場合，SArF はフィーチャを集めているといえる．逆に，フィーチャの観点に基づかないパッケージを持つソフトウェアに対しては，SArF は
性能優位性を持たない．
表 7

すべての対象ソフトウェアについてパッケージ階層の観
SArF とオリジナル Louvain 版 SArF の比較

Table 7 Comparison of SArF and SArF(Lorig).

点を調べることは現実的でないため，以下の 3 ソフトウェ
アについて調べた．

• Javassist と xalan
これらは，SArF の MoJoFM 値が特に高いもののうち，アーキテクチャがドキュメント化されており，パッ向にあるので，数万クラスの規模のクラスタリングが数秒

ケージ構造が基づく観点が分かるものである．両者とで実行できる SArF の価値は高いといえる．

も，フィーチャに基づくパッケージ階層を持つ．

6.3.4 SArF の有効性

• weka 3.4-3.8

6.3.1，6.3.2，6.3.3 項の結果より，SArF はすべての指

これは，SArF の MoJoFM 値が特に高いというわけ

標で他のアルゴリズムより統計的有意に優れるといえる．

ではないもののうち，アーキテクチャがドキュメン

SArF と Newman の差は専念度スコアの導入によるため，

ト化されているものである．ケーススタディ 1 で用

この結果は専念度スコアの定義の妥当性の根拠となる．まいた weka 3.0 はフィーチャに基づくパッケージ階層

た，SArF が他のアルゴリズムより品質に優れることは，遍を持っており SArF が特に高い性能を出していたが，在モジュールの除去を不要にした SArF の狙いが達成されweka 3.4-3.8 ではウェブ 3 階層アーキテクチャに従っている証拠といえる．

たパッケージが大量に追加され，もはやフィーチャに

6.3.5 SArF と SArF(N) との比較基づくパッケージ階層ではなくなっており，性能優位

SArF が用いるモジュラリティ最大化法は Louvain 法 [18]

性を失った例となっている．

であり，Newman アルゴリズム [15] を用いる SArF(N) [16]上記より，確認した範囲では，SArF はフィーチャに基との得失を調べる．図 8 より SArF の品質と安定度はづくパッケージ階層に対して準拠度の高い分割を行ってい

SArF(N) と大差ないことが分かる．表 6 に検定による比るといえる．

較を示す．オーソリティ準拠度では SArF の方が統計的に有意に優れ，クラスタ数では差がなく，安定度では SArF(N)の方がやや（p = 0.04）優れていることが分かる．実行時間については 6.3.3 項より数千クラスを超える規模では差が現れる．以上から，基本的には Louvain 法を用いる SArF

6.4 リサーチクエスチョンの検証
4.1 節で設定したリサーチクエスチョンについて検証する．

• RQ1「SArF はフィーチャを集められるか?」を使用すればよいといえる．

5 章の 2 つのケーススタディでは，SArF のクラスタ

6.3.6 SArF とオリジナル Louvain 版 SArF との比較

リング結果がフィーチャに基づくオーソリティ分割に

3.2 節で Louvain 法を SArF に導入するにあたり，オリ対し高い準拠度を持つことが示された．一方，他のア

ジナルの Louvain 法に，内部のランダム走査を固定順走査

ルゴリズムでは準拠度が低い．また，ケーススタディに変更する修正を施した．修正後もクラスタ数は同程度

2 では，対象ソフトウェアの開発者によって，クラスであった．その修正の効果をみるため，SArF と無修正のタリング結果がフィーチャに基づくことが確認されLouvain 法を使用した SArF(Lorig) との差を調べた結果をた．6 章の評価においても，6.3.7 項で SArF のクラス

表 7 に示す．MoJoFM には有意差がなく，安定度は有意

タリング結果がパッケージ階層に準拠度が高い例をあに SArF の方が優れた．導入した固定順走査が有効であっげた．これらの結果から，RQ1 は肯定的に支持されるたといえる．

といえる．

6.3.7 SArF のフィーチャに基づく分割に対する準拠度
本評価においても，SArF がフィーチャを集めることが• RQ2「SArF はソフトウェアクラスタリングをより自動化できたか?」できているかを調べる．6.3.4 項で SArF の有効性について

5 章のケーススタディ 1 では，SArF が人手による遍在述べたが，各評価対象ソフトウェアのオーソリティ分割がモジュール除去の有無にかかわらず高い性能が得られ，フィーチャや他のどの観点に基づくかは一般的には不明で他のアルゴリズムでは遍在モジュール除去なしでは性あるため，表 3 の結果は特定の目的に限らない「平均的」能が低下することが示された．6 章の評価（6.3.1 項）

c 2023 Information Processing Society of Japan

842

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

では，遍在モジュール除去を行わない条件下で SArFン）を用いて，SArF が既存の依存関係に基づくソフ

が他より高い性能を示すことが分かった．これらから，

トウェアクラスタリングアルゴリズムに対して品質・遍在モジュール除去なしでも SArF が実用に堪え，人安定度の点で優れることを示した．

手の作業を減らしたといえる．よって，RQ2 が肯定的

• 静的な依存関係情報のみを用いてフィーチャを集めるに支持されたといえる．

• RQ3「SArF はソフトウェアクラスタリングにおいて

ソフトウェアクラスタリングに成功した．

• 依存関係に基づくソフトウェアクラスタリングにおいよい特徴を備えているか?」て，遍在モジュール除去作業を不要にした．

6.3.1 項から 6.3.4 項で述べたとおり，SArF はソフト

• 実行時間の測定を行い，SArF の優位性と，数万クラ

ウェアクラスタリングにおいて望ましい性質「クラススの大規模ソフトウェアのクラスタリングが数秒で完タリング品質」「安定性」「実行時間」において優れて了するという高いスケーラビリティを示した．

いることが示された．よって，RQ3 が肯定的に支持さ• SArF 内部のグラフクラスタリングアルゴリズムにLouvain 法を適用する方法とその有効性を示した．

れたといえる．

7. 妥当性への脅威

Wu ら [23] は，彼らの評価においてオーソリティ準拠度が低いことから，当時のソフトウェアクラスタリングアル

内的妥当性への脅威については，まず，オーソリティ分

ゴリズムがいまだ成熟していないのではないかと述べた．

割の問題があげられる．4.2 節で述べたとおり，オーソリ

しかし，ここで示したように SArF では高い（70%以上）

ティ分割結果の入手困難さは依然解決されておらず，本論

MoJoFM 値を得ることができ，実用に耐える性能を達成し文でも既存研究と同様にパッケージ構造をオーソリティ分たといえる．フィーチャを集める特徴を活かし，SArF は

割結果の代替として用いている．次にオーソリティ準拠度

たとえばレガシーシステムからマイクロサービスを抽出すの指標の問題があげられる．MoJoFM は分割過多を過大る [40] などの応用に現在利用されている．

評価する欠点があり，より望ましい指標が求められる．な

今後の課題としては，静的な依存関係を用いるアプロー

お，本論文で評価対象アルゴリズムがソースコードから抽チの欠点を補うために，意味的アプローチや動的アプロー

出される静的な依存関係に基づくものに限っているのは，

チとのハイブリッドなアプローチについて検討を始めてい動的情報や意味的情報に基づくものとの比較は文献 [16] でる．専念度の概念は静的な依存関係に限られるものではな

実施済みのためであり，その点に脅威はない．

いため，同時変更情報や開発者ネットワークなどの他のグ

外的妥当性への脅威については，評価対象ソフトウェア

ラフで表現される情報を取り込むことは検討に値する．動が Java 言語に限られていること，MoJoFM のような階層的依存関係を用いた実例としては文献 [41] がある．別の課のないフラットな分割の評価指標がどこまでの大規模ソフ

題として，単一のモジュールが複数のフィーチャを持つ場

トウェアに通用するのか明らかでないことがあげられる．

合に対応していないことがあげられる．複数クラスタへの8. 結論
我々は静的な依存関係に基づく新しいソフトウェアクラ所属を許容する「ソフトな」クラスタリングアルゴリズムを組み込むことができればこの課題の解決となる．また別の課題として，ソフトウェアクラスタリングの大規模化に

スタリング手法 SArF を提案した．SArF は 2 つの特徴を大きな関心が持たれる．1000 クラスを超えるソフトウェ

持つ．第 1 の特徴はフィーチャを実装するモジュールを同

アは，フラットな分割では人間の理解が及ばず階層的な分一クラスタ内に集めること，第 2 の特徴は人間の介入が不割が必要となるであろう．そのためのアルゴリズム，可視

可欠な遍在モジュール除去作業を不要にし，ソフトウェア

化方法，性能評価手法などが取り組むべき課題となる．

クラスタリングの作業をより自動化したことである．これ
らの特徴は専念度スコアの定義とモジュラリティ最大化法

参考文献の適用により実現された．専念度の意味付けは依存するモ[1]ジュールにとっての依存関係の重要度であり，専念度を用いることで遍在モジュールでないにもかかわらず除去する[2]

過誤や除去し損ねる過誤を避けることができる．モジュラ
リティ最大化法は専念度の定義と親和性があり，専念度付
きの依存関係グラフからクラスタを効率的に発見すること[3]を可能にした．

SArF の評価を行った結果を以下にまとめる．
• 公開リポジトリから客観規準（利用度順）で選んだ大規模なデータセット（35 ソフトウェア 304 バージョc 2023 Information Processing Society of Japan

[4]

Ducasse, S. and Pollet, D.: Software architecture reconstruction: A process-oriented taxonomy, IEEE Trans.
Softw. Eng., Vol.35, No.4, pp.573–591 (2009).
Mancoridis, S., Mitchell, B.S., Chen, Y. and Gansner,
E.R.: Bunch: A clustering tool for the recovery andmaintenance of software system structures, Proc. Int’l
Conf. Softw. Maint., ICSM, pp.50–59 (1999).
Eisenbarth, T., Koschke, R. and Simon, D.: Locating features in source code, IEEE Trans. Softw. Eng.,
Vol.29, No.3, pp.210–224 (2003).
Tzerpos, V. and Holt, R.C.C.: ACDC: An algorithm forcomprehension-driven clustering, Proc. Working Conf.
Rev. Eng., WCRE, pp.258–267 (2000).

843

情報処理学会論文誌

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

Vol.64 No.4 831–845 (Apr. 2023)

Gunqun, Q., Lin, Z. and Li, Z.: Applying complex network method to software clustering, Proc. Int’l Conf.
Computer Science and Softw. Engineering, ICCSSE,
pp.310–316 (2008).
Erdemir, U., Tekin, U. and Buzluca, F.: Object oriented software clustering based on community structure,
Proc. Asia-Pacific Softw. Eng. Conf., APSEC, pp.315–
321 (2011).
Praditwong, K., Harman, M. and Yao, X.: Software
Module Clustering as a Multi-Objective Search Problem, IEEE Trans. Softw. Eng., Vol.37, No.2, pp.264–282(2011).
Bavota, G., Carnevale, F., De Lucia, A., Di Penta,
M. and Oliveto, R.: Putting the developer in-the-loop:
An interactive GA for software re-modularization, Proc.
Sympo. Search Based Software Engineering, SSBSE,
pp.75–89 (2012).
Müller, H.A., Orgun, M.A., Tilley, S.R. and Uhl, J.S.:
A reverse-engineering approach to subsystem structure
identiﬁcation, J. Softw. Maint.: Research and Practice,Vol.5, No.4, pp.181–204 (1993).
Andritsos, P. and Tzerpos, V.: Information-theoretic
software clustering, IEEE Trans. Softw. Eng., Vol.31,
No.2, pp.150–165 (2005).
Maqbool, O. and Babri, H.: Hierarchical clustering
for software architecture recovery, IEEE Trans. Softw.
Eng., Vol.33, No.11, pp.759–780 (2007).
Patel, C., Hamou-Lhadj, A. and Rilling, J.: Software
clustering using dynamic analysis and static dependencies, Proc. Euro. Conf. Softw. Maint. and Reeng.,
CSMR, pp.27–36 (2009).
Wen, Z. and Tzerpos, V.: Software clustering based on
omnipresent object detection, Proc. Int’l Workshop on
Program Compre., IWPC, pp.269–278 (2005).
中塚 剛，松下 誠，井上克郎：コンポーネントランク
法によるソフトウェアクラスタリング結果の理解性向上，情報処理学会論文誌，Vol.48, No.9, pp.3281–3285 (2007).
Newman, M.: Fast algorithm for detecting community
structure in networks, Physical Review E, Vol.69, No.6,
pp.1–5 (2004).
Kobayashi, K., Kamimura, M., Kato, K., Yano, K. andMatsuo, A.: Feature-gathering dependency-based software clustering using dedication and modularity, Proc.
Int’l Conf. Softw. Maint., ICSM, pp.462–471 (2012).
Clauset, A., Newman, M. and Moore, C.: Finding community structure in very large networks, Physical Review
E, Vol.70, No.6 (2004).
Blondel, V.D., Guillaume, J.-L., Lambiotte, R. and
Lefebvre, E.: Fast unfolding of communities in large
networks, J. Stat. Mech. Theory Exp., Vol.2008, No.10,
p.P10008 (2008).
Anquetil, N. and Lethbridge, T.C.: Recovering software architecture from the names of source ﬁles, J.
Softw. Maint.: Research and Practice, Vol.11, pp.201–
221 (1999).
Scanniello, G., D’Amico, A., D’Amico, C. and D’Amico,
T.: Using the Kleinberg algorithm and vector spacemodel for software system clustering, Proc. Int’l Conf.
Program Compre., ICPC, pp.180–189 (2010).
Corazza, A., Di Martino, S., Maggio, V. and Scanniello,G.: Weighing lexical information for software clusteringin the context of architecture recovery, Empir. Softw.
Eng., Vol.21, No.1, pp.72–103 (2016).
Richner, T. and Ducasse, S.: Using dynamic information for the iterative recovery of collaborations and roles,

c 2023 Information Processing Society of Japan


[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

Proc. Int’l Conf. Softw. Maint., ICSM, pp.34–43 (2002).
Wu, J., Hassan, A.E. and Holt, R.C.: Comparison ofclustering algorithms in the context of software evolution, Proc. Int’l Conf. Softw. Maint., ICSM, pp.525–535(2005).
Bittencourt, R.A. and Guerrero, D.D.S.: Comparison ofgraph clustering algorithms for recovering software architecture module views, Proc. Euro. Conf. Softw. Maint.
and Reeng., CSMR, pp.251–254 (2009).
Girvan, M. and Newman, M.E.J.: Community structure in social and biological networks., Proc. National
Academy of Sciences of the United States of America,
Vol.99, No.12, pp.7821–7826 (2002).
Tzerpos, V. and Holt, R.C.: MoJo: A distance metricfor software clusterings, Proc. Working Conf. Reverse
Eng., WCRE, pp.187–193 (1999).
Wen, Z. and Tzerpos, V.: An eﬀectiveness measure forsoftware clustering algorithms, Proc. Int’l Workshop on
Prog. Compre., IWPC, pp.194–203 (2004).
Shtern, M. and Tzerpos, V.: Lossless comparison ofnested software decompositions, Proc. Working Conf.
Rev. Eng., WCRE, pp.249–258 (2007).
Shtern, M. and Tzerpos, V.: On the comparability ofsoftware clustering algorithms, Proc. Int’l Conf. Program Compre., ICPC, pp.64–67 (2010).
Shtern, M. and Tzerpos, V.: Reﬁning clustering evaluation using structure indicators, Proc. Int’l Conf. Softw.
Maint., ICSM, pp.297–305 (2009).
Lutellier, T., Chollak, D., Garcia, J., et al.: Measuring the Impact of Code Dependencies on Software Architecture Recovery Techniques, IEEE Trans. Softw. Eng.,
DOI: 10.1109/TSE.2017.2671865 (2017).
Newman, M. and Girvan, M.: Finding and evaluating
community structure in networks, Physical Review E,
Vol.69, No.2 (2004).
Leicht, E.A. and Newman, M.E.J.: Community structure in directed networks, Physical Review Letters,
Vol.100, No.11, p.118703 (2008).
Arenas, A., Duch, J., Fernández, A.A. and Gómez, S.:
Size reduction of complex networks preserving modularity, New Journal of Physics, Vol.176, No.9, pp.1–15(2007).
Brandes, U., Delling, D., Gaertler, M., et al.: On modularity clustering, IEEE Trans. Knowledge and Data Engineering, Vol.20, No.2, pp.172–188 (2008).
Lancichinetti, A. and Fortunato, S.: Community detection algorithms: A comparative analysis, Physical Review E, Vol.80, No.5 (2009).
Stavropoulou, I., Grigoriou, M. and Kontogiannis, K.:
Case study on which relations to use for clusteringbased software architecture recovery, Empir. Softw.
Eng., Vol.22, No.4, pp.1717–1762 (2017).
Witten, H. and Frank, E.: Data Mining Practical Machine Learning Tools and Techniques, Morgan
Kaufmann (2005).
Ducasse, S., Girba, T. and Kuhn, A.: Distribution
map, Proc. Int’l Conf. Softw. Maint., ICSM, pp.203–
212 (2006).
Kamimura, M., Yano, K., Hatano, T. and Matsuo, A.:
Extracting Candidates of Microservices from Monolithic
Application Code, Proc. Asia-Pacific Software Engineering Conference (APSEC ), pp.571–580 (2018).
Yano, K. and Matsuo, A.: Data Access Visualization for
Legacy Application Maintenance, Proc. Int’l Conf. Software Analysis, Evolution and Reengineering, (SANER),

844

情報処理学会論文誌

Vol.64 No.4 831–845 (Apr. 2023)

pp.546–550 (2017).

小林 健一 （正会員）
平成 6 年東京大学大学院工学系研究科修士課程修了．同年富士通研究所
入社．令和 3 年大阪大学大学院情報科学研究科後期博士課程修了．現在まで富士通株式会社勤務．博士（情報科学）．AI 品質，ソフトウェア保守，プ
ログラム理解，HPC の研究開発に従事．

松尾 昭彦 （正会員）
昭和 62 年東京理科大学理学部物理学科卒業．同年（株）富士通研究所入社．
業務アプリケーションの保守や再構築に関する研究開発に従事．令和 4 年退職．平成 26〜27 年情報処理学会理事．

松下 誠 （正会員）
平成 10 年大阪大学大学院基礎工学研
究科博士後期課程修了．同年同大学基礎工学部情報工学科助手．平成 14 年
大阪大学大学院情報科学研究科コンピュータサイエンス専攻助手．平成17 年同専攻助教授．平成 19 年同専攻准教授．博士（工学）．リポジトリマイニング，プログラム
解析の研究に従事．

井上 克郎 （正会員）
昭和 59 年大阪大学大学院基礎工学研
究科博士後期課程修了（工学博士）．
同年大阪大学基礎工学部情報工学科
助手．昭和 59〜61 年ハワイ大学マノ
ア校コンピュータサイエンス学科助教授．平成 3 年大阪大学基礎工学部助教
授．平成 7 年同学部教授．平成 14 年同大学大学院情報科
学研究科教授．令和 4 年より南山大学理工学部教授．ソフ
トウェア工学，特にコードクローンやコード検索等のプログラム分析や再利用技術の研究に従事．

c 2023 Information Processing Society of Japan

845