Vol. 48

情報処理学会論文誌

No. 9Sep. 2007

テクニカルノート

コンポーネントランク法によるソフトウェアクラスタリング結果の理解性向上
中 塚 剛†

誠†松 下井 上 克 郎†

巨大なシステムを複数のサブシステムに分解するソフトウェアクラスタリング手法は，大規模なソフトウェアを理解するために有用である．しかし，システム内には，特定のサブシステムに属すべきでないライブラリのような部品も存在する．そのような部品を事前に特定することにより，クラスタリング結果が理解しやすくなると期待できる．本稿では，ソフトウェア部品の重要度を測定するコンポーネントランク法を用いることにより，特定のサブシステムに属すべきではない部品を特定する手法の提案を行う．提案する手法を用いたクラスタリングツールを用いて実験を行い，得られた結果に対する考察を行った．その結果，従来手法よりも優れたクラスタリング結果を得られることがわかった．

Improvement in Understandability of the Software Clustering Resultsby Component Rank Model
Gou Nakatsuka,† Makoto Matsushita† and Katsuro Inoue†
Decomposing a large software system into some subsystems helps us understand its structure and functions. In the system, however, there are special modules such as libraries thatshould not belong to a certain subsystem, and pre-detecting such modules can make the clustering results more understandable. This paper proposes a new method of detecting such
modules by Component Rank Model, that is used to measure mutual signiﬁcance of softwaremodules. We performed experiments with a new clustering tool combined with our detecting
method and investigated the clustring results. As a result, our method turned out better thanan existent method.

は多くのモジュールから直接的あるいは間接的に依存

1. は じ め にされているモジュールである．遍在モジュールは特定仕様書等が十分でないソフトウェアシステム（以降，のサブシステムに属するべきでないため3) ，適切に特システム）の構造や機能の理解を助ける手法の一つと定してクラスタリング対象から除去する必要がある．

して強凝集かつ低結合の原則に基づくソフトウェアク

しかし従来手法では，依存関係を持つモジュールの数ラスタリングが研究されている1)∼2) ．これらの研究でが閾値以上のモジュールを遍在モジュールとするといは，システムは多くのモジュール（例えば Java の場

う単純な手法で特定しており1),3) ，遍在モジュールに合，クラスやインターフェース）から構成されると仮関して詳細な考察は行われていない．

定し，密に依存しあっているモジュールをクラスタと一方，Java ソフトウェア部品検索システム SPARS-することによってサブシステムを構築し，サブシステ

J4) では，コンポーネントランク法と呼ばれる手法がム間の依存関係をできるだけ少なくするという手法が用いられている．この手法は，あるシステム内のソフ用いられている．

トウェア部品の相互利用関係を解析することによって，このようなソフトウェアクラスタリングにおいて問各ソフトウェア部品の重要度を計算する．ここで上位題となるのは，システム中に存在する遍在モジュールにランク付けされたクラスは，ソフトウェア中の多く（omnipresent module）である3) ．遍在モジュールとから利用される重要な部品であるが5) ，これは遍在モジュールの満たすべき性質と似ている．

† 大阪大学 大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka University

そこで本稿では，コンポーネントランク法を利用して遍在モジュールを特定する手法を，実験によって評1

2

情報処理学会論文誌

価，決定する．その結果，本手法が従来のソフトウェアクラスタリングアルゴリズムを改良することを示す．
以降，2 節にて本研究に関連する 2 つの手法について説明し，3 節で，コンポーネントランク法を用いた遍在モジュール特定手法を決定するための実験と結果について説明する．最後に，4 節でまとめと今後の課題について述べる．

2. 関 連 研 究
2.1 ソフトウェアクラスタリングシステム BunchBunch1) は，強凝集・低結合の原則に基づいたクラスタリングを実装したシステムで，NP 困難であるクラスタリングを，局所探索法を用いることで現実的な実行時間で解く．Bunch では，4 種類の遍在モジュールを定めており，それぞれ以下のような特定条件を与えている．

• supplier：入次数が平均次数の 3 倍以上• client：出次数が平均次数の 3 倍以上• central：supplier かつ client• library：出次数が 0本研究は，Bunch におけるこれら 4 種の遍在モジュールを特定するための適切な条件を定めること

Sep. 2007

表 1 遍在モジュール特定条件（数字は平均からの倍率）
Table 1 Conditions for omnipresent modules
No.
C1C2C3C4C5C6C7C8C9C10C11C12C13C14C15C16C17C18C19C20
C21C22
C23
C24
C25
C26
C27
C28
C29
C30
C31
C32
C33
C34
C35
C36
C37
C38
C39
C40

supplierin CVR
3clientout
32
2.5
3.5
3

2
2.5
3.5
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3

1
1
1
1
1
1
1.5
1.5
1.5
1.5
1.5
1.5
2
2
2
2
2
2
2.5
2.5
2.5
2.5
2.5
2.5
3
3
3
3
3

1
1
1111
1111111111111111111111111111in
322.5
3.5
33111131.5
1.5
1.5
1.5
3222232.5
2.5
2.5
2.5
33333

centralout CVR
322.5
3.5
3333
333333333333333
333
333333333333
3

inlibraryout CVR
00001111111111111111111111111111111111011000011111100000111111100000111111100000111111100000111100011111で，Bunch の出力する解を改良することを目指す．

2.2 コンポーネントランク法

果を導くかを比較するために 2 種類の実験を行い，最Java ソフトウェア部品の再利用を助けるために，部適な条件を決定する．

品検索システム SPARS-J が開発されている4) ．この3.1 実験対象となる特定条件

システムは，与えられた検索単語に対して関連する

本実験では，表 1 に示すように C1∼C40 の特定条

Java ソフトウェア部品を提示する．その際，ソフト件を実験対象として定めた．ここで in，out，CRV のウェア部品を提示する順番を決定する手法として，コ列はそれぞれ入次数，出次数，CRV の条件を表し，数ンポーネントランク法が用いられる．

字は平均値からの倍率を表している．数字が正の場合，コンポーネントランク法では，各モジュールの直接例えば 3 の場合は平均値の 3 倍以上ならば該当とす的あるいは間接的な利用関係に基づいて，総和が 1 とる．ただし，数字が 0 の場合は，値が 0 の時のみ該当なるようにコンポーネントランク値（CRV）を振り分とする．

ける．この際，たくさんの部品から使用されている部

C1 は Bunch で用いられている条件であり，C2 は遍品の CRV は高くなり，また，CRV の高い部品から使在モジュールを考慮していない．C3∼C6 は，CRV を用されている部品の CRV も高くなる．

用いておらず，C7 以降は，supplier，central，library

本稿では，「CRV の高い部品は，多くの部品に直接の条件に CRV を使用している．この際，CRV が平的あるいは間接的に使用されている部品であり，遍在均を超えるモジュールは全体の約 20%と少ないため，モジュールの候補ではないか」，という点に注目して，CRV の条件としては平均以上のみを考慮して，次数CRV を用いた遍在モジュール特定手法を提案する．

条件を組み合わせることで条件を厳しくしている．各3. 遍在モジュール特定手法
Bunch で定義されている 4 種類の遍在モジュールを遍在モジュールに対して条件を定め，その直積の一部を条件とした．

3.2 実験 1：結果の理解しやすさによる評価

CRV，次数によって特定するために，どのような条件

Bunch では，各クラスタの凝集度と結合度のトレーを用いれば解を改良できるか，検証実験を行う．ここドオフを CF （Cluster Factor）という関数で表してでは 40 の特定条件を定義し，各条件がどのような結いる．CF は，各クラスタに関連する辺のうち，クラVol. 48

No. 9コンポーネントランク法によるソフトウェアクラスタリング結果の理解性向上

3

スタ内部にある辺の割合を表し，0∼1 の値を取る．つマークとして作成して結果と比較するという手法があまり，CF 値が高いほどクラスタ間に辺が少なくなり，る6)∼7) ．本実験では，実験 1 で用いたシステムの一結果が理解しやすいものとなる．すなわち，平均 CFつである GNUJpdf（25 モジュール）に対してベンチ値（全クラスタの CF 値の平均値）が高い方が全体のマークを作成し，結果と比較を行った．

結果が理解しやすいといえる．

ここでは，ベンチマークと解を比較するために，Ed-一般的に，遍在モジュールを多く特定するほど，平geSim と MeCl という 2 種類のメトリクス7) を用い均 CF 値が高くなりやすい．この場合，クラスタリンた．EdgeSim は，辺の類似度を測定するメトリクス

グされたモジュールは理解しやすいといえるが，遍在で，MeCl は，片方のグラフを分割した後マージするモジュールの数が増えるため，個別に理解する必要がことで，もう片方のグラフと一致させるために必要なあるモジュール数が増加することになる．この結果，コストを測定するメトリクスである．共にパーセント全体として理解にかかるコストが増加してしまう場合

尺度で，値が高いほど 2 つのグラフが類似しているこがある．よって，平均 CF 値よりも，クラスタリングとを意味する．ただし，これらは遍在モジュールを考対象モジュール数（遍在モジュールではないモジュー慮しないため，正しい評価が行えない場合がある．そルの数）を重視し，2 つの値が共に高い条件が優れてのため，目視評価によってその点を補う必要がある．

いるとする．

結果と考察

本実験では，15 種類の Java で書かれたオープン実験 2 の結果を図 2 に示す．横軸は，40 の条件をソースシステムに対して 40 の特定条件を適用した．

表している．横軸の値の一部に付けられた下線は，遍結果と考察在モジュールの選び方によって Bunch の解に一部の15 システムに適用した結果の平均値を図 1 に示す．

モジュールが存在しないというバグのため，解を一部横軸は 40 の条件を表し，縦軸は，クラスタリング対書き換えて測定したことを表している．縦軸は，Ed-象モジュール数の全モジュール数に対する割合，平均geSim，MeCl を表している．両メトリクスの相関係

CF 値と両者の調和平均値を示している（一部，記号数は 0.88 と非常に高い．

が重なっている）．

この結果から，EdgeSim，MeCl 共に値が改善して左端の C1 の結果が Bunch オリジナル条件での結いる条件が多数存在することがわかる．実験 1 で結果果であり，C2 と比べると，平均 CF 値が約 2 倍に増の良かった C27∼C29 は，実験 2 でも非常に良い結果加した一方，遍在モジュール数が多過ぎることがわかを示している．ただし，C29 は，前述の Bunch のバグる．なお，この結果が比較の基準となるため，横軸にのため，正しい解を出力していない．なお，GNUJpdf対して平行に破線で示している．

はモジュール数が少ないため，同じクラスタリング結C1，C3∼C5 の結果を見ると，クラスタリング対象モジュール数と平均 CF 値がトレードオフの関係と果を出力する条件があり，図 2 で同じ値を示しているものが見られる．

なっていることがわかる．また，C6 の結果は，出次

3.4 実験のまとめ数が 0 という条件によって library がいかに多く選ば

GNUJpdf では C27，C28 が優れた結果を示していれていることを示している．

るが，central の条件が supplier かつ client でない場

C7 以降の結果は，C1 に比べて，2 つの評価値が共合に不適切な結果を出力し得ることがあった．そこで，に増加している条件が多数存在している．supplier にC28 は不適切となる．よって，定義した 40 の条件の対する条件が厳しくなるにつれ，クラスタリング対象

中では，以下に示す C27 が，最も Bunch のアルゴリ

モジュール数は増加し，逆に平均 CF 値が減少していズムを改善することがわかった．

る．つまり，トレードオフとなっているが，調和平均値が改善していることがわかる．クラスタリング対象• supplier：入次数が平均次数の 2 倍以上，かつCRV 平均以上

モジュール数，平均 CF 値がともに C1 の結果より高• client：出次数が平均次数の 3 倍以上い結果の中で，前述のように，クラスタリング対象モ• central：supplier かつ client

ジュール数を重視すると，C27∼C29 の条件が優れて• library：入次数が平均以上，かつ出次数が 0，かいるといえる．

3.3 実験 2：ベンチマークによる評価
クラスタリング結果構造を評価するためによく用いられる手法として，適切と考えられる解をベンチ

つ CRV 平均以上

4. む す び
本稿では，コンポーネントランク法によって測定さ情報処理学会論文誌

4Sep. 2007

10.8
0.6
0.4
0.2
0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
クラスタリング対象モジュール数（割合）

平均CF値

調和平均値

図 1 実験 1 の結果
Fig. 1 Result for experiment 1(%)
10080601 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
EdgeSimMeCl

図 2 実験 2 の結果
Fig. 2 Result for experiment 2れるコンポーネントランク値を用いて遍在モジュールを特定し，高凝集・低結合の原則に基づくソフトウェ
アクラスタリングを改良できることを確認した．
今後の課題としては，より大規模なシステムでのベンチマーク実験による評価が挙げられる．

参 考 文 献1) Mitchell, B.S. and Mancoridis, S.: On the Automatic Modularization of Software Systems
Using the Bunch Tool, IEEE Transaction on
Softw. Eng., Vol.32, No.3, pp.193–208 (2006).
2) Schwanke, R.W.: An Intelligent Tool For Reengineering Software Modularity, Proc. of Int’l
Conf. on Softw. Eng., pp.83–92 (1991).
3) Müller, H.A., Orgun, M.A., Tilley, S.R. andUhl, J. S.: A Reverse Engineering Approach
To Subsystem Structure Identiﬁcation, Journalof Softw. Maintenance: Research and Practice,Vol.5, No.4, pp.181–204 (1993).
4) Inoue, K., Yokomori, R., Yamamoto, T., Matsushita, M. and Kusumoto, S.: Ranking Significance of Software Components Based on Use

Relations, IEEE Transactions on Softw. Eng.,
Vol.31, No.3, pp.213–225 (2005).
5) 市井誠，横森励士，松下誠，井上克郎：コンポーネントランクを用いたソフトウェアのクラス設計に関する分析手法の提案，電子情報通信学会技術研
究報告，SS2005-37，Vol.105, No.229, pp.25–30(2005).
6) Wen, Z. and Tzerpos, V.: An eﬀectivenessmeasure for software clustering algorithms,Proc. of the Int’l Workshop on Program Comprehension (IWPC ’04), pp.194–203 (2004).
7) Mitchell, B. S. and Mancoridis, S.: Comparing the Decompositions Produced by Software
Clustering Algorithms using Similarity Measurements, Proc. of Int’l Conf. on Softw. Maintenance, pp.744–753 (2001).
(平成 19 年 4 月 4 日受付)
(平成 19 年 6 月 6 日採録)

Vol. 48

No. 9コンポーネントランク法によるソフトウェアクラスタリング結果の理解性向上

中塚剛

5井上 克郎（正会員）

平 19 阪大・情報科学・コンピュー昭 54 阪大・基礎工・情報卒．昭 59

タサイエンス卒．在学中，ソフトウェ

同大大学院博士過程了．同年同大・アクラスタリングの研究に従事．修

基礎工・情報・助手．昭 59-61 ハワ士（情報科学）．

イ大マノア校・情報工学科・助教授．
平 1 阪大・基礎工・情報・講師．平3 同学科・助教授．平 7 同学科・教授．平 14 阪大・情松下誠（正会員）

平 5 阪大・基礎工・情報卒．平 10
同大大学院博士過程了．同年同大・基礎工・情報・助手．平 14 阪大・情報科学・コンピュータサイエンス・助手．平 17 同専攻助教授，平 19 同専攻准教授．博士（工学）．

報・コンピュータサイエンス・教授．工学博士．