ソフトウェア部品グラフのべき乗則の 調査と部品検索への応用 井上研究室 市井 誠 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 1 背景 ソフトウェア部品検索 ソフトウェア開発のコスト削減のための，ソフトウェア部品の再利用支援手法 再利用性や目的への適合性の観点からソフトウェア部品を検索 ソフトウェア部品 (部品) C ソフトウェアの構成単位 E 互いに利用関係が存在 ソフトウェア部品グラフ (部品グラフ) A B D 部品を頂点，利用関係を有向辺としたグラフ ソフトウェア工学の様々な手法に用いられる ソフトウェア部品検索では，部品の相対的な重要度の評価に利用[1] 有用性の高い手法の研究のため，部品グラフの性質を知る必要がある [1]K. Inoue, R. Yokomori, T. Yamamoto, M. Matsushita, S. Kusumoto, “Ranking Significance of Software Components Based on Use 2015/10/1 修士論文発表会 Relations”, IEEE Transactions on Software Engineering, vol. 31, no. 3, pp.213-225, 2005 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 2 部品グラフとべき乗則 頂点の次数分布: グラフを特徴付ける重要な要素 部品グラフの次数分布に関する研究 JDKのクラス図を部品グラフを見なしたとき，次数がべき乗則に従う[2] C++のソフトウェアの部品グラフの次数がべき乗則に従う[3] べき乗則 (べき分布): 値 x をもつ要素の出現頻度が，x のべき乗に比例する p(x) = Cx-a これらの研究の特徴 単体のソフトウェアに対し，グラフとしての共通する性質を得ることに主眼がお かれた研究 クラス図などの粗い利用関係に基づく解析 ソフトウェア部品検索への応用のためには，より詳細な解析に基づく， 観点を変えた調査が必要 [2] S. Valverde, R. Ferrer-Cancho and R. V. Sole, "Scale-free Networks from Optimal Design", Europhysics Letters, 2002 [3] C. R. Myers, “Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs”, 2015/10/1 修士論文発表会 Physical Review E 68, 046116 ,2003 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3 研究の目的 ソフトウェア部品検索への応用を考慮した，べき乗則に注 目したソフトウェア部品グラフの性質の調査 部品検索で扱う部品グラフに対する調査 検索対象となるデータベース中の部品群 大規模なソフトウェア集合 部品検索により得られる部品群 大規模なソフトウェア集合 からの検索 グラフの性質とソフトウェアの性質との関連の調査 ソフトウェア間の比較 など ソフトウェア部品検索への応用 検索結果の順位付け手法の改良 2015/10/1 本発表の内容 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 4 ソフトウェア部品グラフの 性質の調査 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 5 調査対象 部品グラフの定義 頂点(部品): Java クラス (インターフェースを含む) 辺(利用関係): 全ての静的な利用関係 継承, 変数宣言, メソッド呼び出し, … 既存研究では，継承やフィールド宣言など，一部の利用関係のみ データセット JDK Javaの基本ライブラリ 頂点数: 約1万, 辺数: 約10万 ソフトウェア集合 JDKに加え， Eclipse等のオープンソースソフトウェアの集合 頂点数: 約18万, 辺数: 約180万 検索による部品群 「ソフトウェア集合」からのキーワード検索の結果で部分グラフを構成 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 6 調査結果として示す内容(1/2) 頂点の次数分布のプロット 入力次数と出力次数を個 p(x) = Cx-a 別に示す 両対数軸を用いた累積度数 プロット べき乗則に従う場合，点が 直線上にならぶ 入力次数:2 傾き: -(a-1) 傾き: -a 値の大きい部 分にばらつき 出力次数:1 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 7 調査結果として示す内容(2/2) 回帰分析により得られる値 べき乗則のパラメータ 寄与率 a p(x) = Cx-a R*2 べき乗則に従う度合い 傾き: -(a-1) 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 8 調査結果: JDK 頂点数 約1万 辺数 約10万 •入力次数はべき乗則に従う •出力次数は異なる分布に従う a 入力次数 2.1 ±8.6×10-3 出力次数 3.9±6.6×10-2 2015/10/1 R*2 0.99 0.96 •値の大きい部分のみ，べき乗則 •入力次数の上位は基礎的なクラス •java.lang.String, java.lang.Object 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 9 調査結果: ソフトウェア集合 頂点数 約18万 辺数 約180万 •JDKと同様の分布 a 入力次数 2.0 ±1.4×10-3 出力次数 4.4 ±4.3×10-2 2015/10/1 R*2 1.00 0.98 •入力次数はより理想的なべき分布 •入力次数上位はJDKの基礎的なクラス 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 10 調査結果 まとめ 1 入力次数はべき乗則に従う p(x) = Cx-2 出力次数は異なる分布 ファイルの大きさの分布に類似 傾きはデータセットにより異なる 一部のクラスに利用関係が集中 一般に，ライブラリ再利用による開発が行われている 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 11 調査結果: 検索による部品群 (1/3) ソフトウェア集合から，全文検索により部品群を抽出 検索キーワード “labels” 検索結果が約1000部品となる，ランダムに選択したキーワード “getsummary” 同様に 約100部品～約500部品となる，ランダムに選択したキーワード 抽出された部品群で部品グラフを構築し，次数を調査 以降，全文検索により抽出された部品群を「検索結果」と呼 ぶ 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 12 調査結果: 検索による部品群 (2/3) “labels” 頂点数 約1000 辺数 約1500 2015/10/1 a 入力次数 2.2 ±3.3×10-2 出力次数 3.6 ±2.0×10-1 R*2 0.98 0.93 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 13 調査結果: 検索による部品群 (3/3) “getsummary” 頂点数 約130 辺数 約120 2015/10/1 a 入力次数 2.2 ±3.3×10-2 出力次数 3.3 ±2.7×10-1 R*2 0.98 0.93 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 14 調査結果のまとめ 2 検索結果も，JDKやソフトウェア集合と同様の分布 極めて少ない部品数で成り立つ 100部品や1000部品 ランダムに部品を抽出した場合，1000部品程度ではべき乗則 は見られない 要因 関連のある部品は同じ語を含むことが多い 検索キーワードがクラス名やメソッド名にヒットした場合，その部 品を利用する部品もまたヒットする 利用関係が形成されやすい 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 15 ソフトウェア部品検索への応用 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 16 Component Rank法とべき乗則 Component Rank(CR) 法: 再利用性に基づく順位付 け手法 部品グラフを基に部品の相対的な重要度を評価 多くの部品に利用される部品は重要 重要な部品に利用される部品は重要 単なる次数では得られない，再利用性を測る評価値 重要 E 重要 D A B C 部品グラフの性質によっては有効性をもたない 全頂点間に均一に辺が存在する場合など ソフトウェアや，ソフトウェア集合にて有効性が示されている 部品グラフの入力次数がべき乗則に従う，などの性質をもつ 同様の性質が検索結果にも成り立つ 検索結果の部品グラフにもCR法が適用可能 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 17 Component Rank法を 部品検索に用いる上での問題点 ライブラリとしての部品を検索する場 合 現在は全体の部品グラフにより求め た評価値を基に順位付け :検索結果 高評価値 :適合部品 不適合部品でも評価値が高けれ ば上位に順位付け 検索結果上位の適合率の低下 検索結果の部品グラフ内では，検 索語に応じた利用関係が形成され ている 目的とする部品に利用関係が集中 関連の無い部品は孤立している傾 向 検索結果の部品グラフにCR法を 適用する 2015/10/1 1. …………………………: 2. …………………………: 3. …………………………: 4. …………………………: 5. …………………………: 6. …………………………: … × ○ ○ … … … 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 18 提案手法 検索結果を得た後で，部分グラ フに対してCR法を適用する 1. 利用者からの検索語をもとに， 部品群を得る 2. 部品群内での利用関係を求め， 部品グラフを作成する 3. 部品グラフにCR法を適用し， 評価値を得る 4. 評価値順に部品をソートし，利 用者に提示する 2015/10/1 :検索結果 :適合部品 1. …………………………: 2. …………………………: 3. …………………………: 4. …………………………: 5. …………………………: 6. …………………………: … ○ ○ ○ … … … 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 19 適用実験 従来手法と，提案手法で上位 10件の適合率を比較 一般に，利用者は10件程度 の検索結果で目的が満たされ なければそれ以上見ない 検索語: ライブラリの再利用を 目的とした語 10語 「利用例」は不適合 語 hash map perl regular expression file read string pdf ファイルから文字列を読 み込む処理を実現 ZIPアーカイブファイルを 扱う PDFフォーマットを扱う xml parse XMLファイルの解析 http connection HTTP接続をおこなう image icon swing Swing GUI上で画像ア イコンを表示 バージョン管理システム CVS を扱う グラフの描画 zip cvs 2015/10/1 目的 ハッシュマップを実現・操 作 Perl互換の正規表現 graph 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 20 結果 ほぼ全ての場合において，提案 手法が適合率で上回った 検索結果上位の適合率の向 上に対する有効性が示された 今後，再利用性の観点からの 評価が必要 2015/10/1 語 hash map 従来手法 0 提案手法 0.2 perl regular 0.7 expression file read string0.1 0.7 zip 0.2 0.6 pdf 0.2 0.7 xml parse 0.2 0.6 http connection image icon swing cvs 0.3 0.4 0.2 0.2 0.3 0.3 graph 0 0.5 0.2 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 21 まとめ べき乗則に注目した，ソフトウェア部品グラフの調査 大規模ソフトウェア部品群 および 検索結果の部品群 に対し て，入力次数にべき乗則が成り立つことが明らかになった ソフトウェア部品検索への応用として，検索結果の順位付 け手法の改良を提案 提案手法により，検索結果上位の適合率が向上 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 22 後期課程での研究 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 23 後期課程での研究(1/2) ソフトウェア部品の検索と再利用に関する研究 過去に作られた部品を再利用することで，ソフトウェア開発の コストを削減する 再利用のためにコストがかかってしまっては意味がない 部品検索システムへの要求: 手間をかけずにデータベースを構築できる 簡単に，そのまま利用できる形で部品を検索・取得できる SPARS-J: Javaを対象とした部品検索システム ディレクトリ指定により容易に部品(ソースコード)を登録 キーワード検索により，ヒットした部品の一覧を． 再利用性および適合性の観点による順位付けにより提示 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 24 後期課程での研究(2/2) システムは，順 位付けされた 個別の部品を 提示 実際には，関連を持つ いくつか org.apache.oro.text.regex.Perl5Compiler org.apache.oro.text.regex.PatternMatcher のグループに分類できる org.apache.oro.text.regex.Perl5Matcher org.apache.oro.text.regex.Perl5Pattern org.apache.oro.text.regex.OpCode org.apache.xerces.impl.xpath.regex.Token 利用者はグループ org.apache.xerces.impl.xpath.regex.RegularExpression 単位で再利用をおこ org.apache.oro.text.perl.Perl5Util org.apache.oro.text.perl.Perl5Util なう org.apache.oro.text.regex.Perl5MatchResult gnu.regexp.RESyntax gnu.regexp.REMatch org.apache.oro.text.regex.Util 再利用する部品を gnu.regexp.RE 個別に取得する手 org.apache.regexp.RE 間がかかる org.apache.oro.text.regex.PatternCompiler 再利用をおこなう単位での部品グループの検索手法の研究 検索目的に応じて部品をグループ化 グループ単位での部品利用例の提示 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 25 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 26 （参/調査) 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 27 クラスタリング係数と階層性 C(k): 次数k の頂点の平均ク ラスタリング係数 C(k)～k-1 となるとき，グラフに 階層性 E. Ravasz, A.L. Barabasi, "Hierarchical organization in complex networks",Physical Review E, vol 67, 261121, 2003. 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 29 クラスタリング係数と階層性: 本研究でのデータ JDK C(k)～k0.80 2015/10/1 ソフトウェア集合 検索結果(“labels”) C(k)～k0.93 C(k)～k0.96 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 30 検索結果のパラメータの分布 公開デモシステムでの実際の検索語(424語)をもとに，入力 次数のべき分布のパラメータの分布を調査 ヒストグラム べき分布のパラメータ a 2015/10/1 R*2 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 31 縦軸に値, 横軸に部品数 べき分布のパラメータ a 2015/10/1 R*2 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 32 クラスタリング係数の傾き 2015/10/1 C(k)～ks R*2 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 33 クラスタリング係数の傾き 2015/10/1 R*2 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 34 (参/応用) 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 35 コンポーネントランク値の計算 部品グラフをもとにした繰り返し計算 1. 2. 3. 4. 5. C1 0.334 各頂点に総和を1として適当な重みを与える 頂点の重みを，出ていく辺で分配する 入ってくる辺の重みの総和を，その頂点の重みとして再定義 頂点の重みが収束するまで，2.3.を繰り返し計算 収束した重みが部品のCR値 C1 0.334 C1v1×50% CC210.167CC21 0.333 0.333 0.333 v1×50% 0.167 v3×100% 0.333 C3 2015/10/1 0.333 C3 0.333 CC2 10.1665CC21 0.500 0.167 0.400 0.1665 v2×100% 0.500 0.333 C3 C3 0.500 C2 0.200C2 C2 0.1665 0.200 0.200 0.400 0.167 C3 C3 0.200 C3 0.3335 0.400 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 36 キーワード出現頻度に基づく順位付け Keyword Rank(KR)法 文書検索システムで用いられるTF-IDF法を改変 部品を特徴付ける索引キーに適当な重みを与える 部品に繰り返しあらわれる索引キー 希少で，特定の部品に偏ってあらわれる索引キー クラス定義名など部品を象徴するトークン種類の索引キー 重みの総和を評価値として順位付け クエリと適合する部品が上位に来る 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 37 実行時間(秒) 語 hash map ヒット数 従来手法 提案手法 差 11441 1.50 2.72 1.22 perl regular expression file read string 94 0.14 0.15 0.01 10388 9.71 10.94 1.22 zip 1524 484 4825 4364 0.08 0.03 0.85 1.60 0.19 0.07 1.26 1.95 0.11 0.05 0.41 0.35 image icon swing 1083 0.54 0.63 0.09 cvs 8561 0.34 0.96 0.62 graph 2112 0.12 0.27 0.15 pdf xml parse http connection 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 38 “graph” 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 従来手法 提案手法 java.util.regex.Pattern java.io.ObjectInputStream java.io.ObjectOutputStream javax.swing.JComponent java.awt.event.KeyEvent java.awt.event.MouseEvent java.util.regex.ASCII java.awt.event.InputEvent org.apache.tools.ant.Project java.io.Serializable java.io.ObjectInputValidation org.eclipse.core.resources.IWorkspace java.awt.datatransfer.DataFlavor org.netbeans.junit.NbTestCase org.jgraph.JGraph org.jgraph.GPGraphpad org.jgraph.pad.actions.AbstractActionDefault org.openide.util.Utilities org.jgraph.GPGraphpad com.jgraph.GPGraphpad com.jgraph.graph.AttributeMap com.jgraph.graph.Attributes org.jgraph.JGraph javax.swing.JComponent com.sun.j3d.(中略).j3d.SceneGraphObjectState org.jgraph.graph.AttributeMap java.io.ObjectInputStream com.jgraph.JGraph java.io.ObjectInputValidation com.sun.j3d.demos.utils.scenegraph.io.retained.SymbolTableData com.sun.j3d.demos.utils.scenegraph.io.retained.Controller java.awt.event.InputEvent org.jgraph.graph.CellView java.awt.event.MouseEvent org.jgraph.graph.MutableAttributeMap org.jgraph.GPGraphpad com.jgraph.graph.CellView com.jgraph.graph.MutableAttributeMap com.jgraph.GPGraphpad org.netbeans.modules.schema2beans.BaseBean 適合不適合 2015/10/1 修士論文発表会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 39
© Copyright 2024 ExpyDoc
