ソースコード中の識別子に基づくカテゴリ階層構築手法大阪大学大学院情報科学研究科 ○宮崎宏海，早瀬康裕，市井誠，松下誠，井上克郎 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 背景（1/2）ソフトウェアの大規模化・複雑化品質要求の高まり開発に掛かるコストの削減ソフトウェアの高品質化ソフトウェア部品の再利用目的の機能を持つ部品を利用信頼性の高い部品を利用 2 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 背景(2/2) ソフトウェア部品の量は膨大オープンソースソフトウェアの増加社内ソフトウェア部品の蓄積ソフトウェア部品検索・管理の必要性ソフトウェア部品取得にかかるコストの削減様々なソフトウェア部品検索システムの開発 3 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ソフトウェア部品検索システムキーワード検索システム入力したキーワードに適合する部品を出力する利点：Web検索で馴染みがあり，自由度の高い検索ができる既存のソフトウェア部品検索システム例：SPARS-J，Google Code Search カテゴリ検索システムあらかじめ用意された階層状のカテゴリから目的の部品を探す利点：適当なキーワードが思いつかない場合でも，漠然とした目的から検索ができる既存のソフトウェア部品検索システム例：ソースコードの特徴語を用いたJavaソフトウェア部品の分類システム[11] [11]：仁井谷，松下，井上， “ソースコードの特徴語を用いたJavaソフトウェア部品の自動分類手法の提案 ” 情報処理学会研究報告, Vol.2005, No.75, 2005-SE-149, pp.49-56, 2005 4 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 一般的なカテゴリ検索カテゴリ検索の特徴カテゴリにはカテゴリ名に関連する文書が含まれるカテゴリには上位のカテゴリ，下位のカテゴリが存在するこの親子関係により階層構造ができている人手で維持されることが多い文書の内容を把握する必要があるため例：Yahoo, Open Directory … スポーツプロ野球プロ野球ニュースプロ野球コラム … … リーグ … … プロ野球 Jリーグ … ドラフト … 5 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ソフトウェア部品のカテゴリ検索システムの問題点部品がどのカテゴリに属するかの判断には部品に関する専門的な知識が必要部品の量が膨大カテゴリは人手による維持が困難カテゴリを自動で作成することで維持にかかるコストを削減できる 6 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 既存のカテゴリ階層の自動構築手法 Javaのソースコードから特徴語を抽出，カテゴリ名とする特徴語：クラス名，メソッド名などカテゴリに，そのカテゴリ名を特徴語に持つJavaのソースコードを割り当てるカテゴリに含まれる部品の包含関係からカテゴリの階層構造を作成カテゴリ 1 input read file 2 write file 部品（Javaソースコード） 1 1 input file read 1 2 file 2 write write read input 7 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 既存手法の問題点カテゴリ間の親子関係でカテゴリ名の意味的な繫がりを考慮していない対象：Robocode*のロボットのソースコード *Javaを使ってプログラミングしたロボット同士を戦わせるフリーソフト Mirror … Mirrorはロボットの Approachの一種 Author Approach … … カテゴリ名に意味的な繫がりがないカテゴリ名による段階的な絞り込みが出来ない 8 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 研究の目的目的カテゴリ名による段階的な絞り込みに適したカテゴリ階層の自動構築カテゴリ名の意味を考慮する必要がある →シソーラスに着目単語間の関係を記した辞書同義（類義）関係反義関係上位下位関係単語の概念による包含関係ある単語(上位語)が別の単語(下位語)を抽象的に表す上位下位関係のシソーラスを用いることでカテゴリ名の意味的な関係にもとづいたカテゴリ階層を構築する 9 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 既存のシソーラス単語間の関係を記している特定の分野について記述している例：WordNet [1]：日常的に用いられる単語について記述されている WordNetで「list」に関係する単語 listの上位語： database listの下位語： bibliography [1]：A.Miller，R.Beckwith，C.Fellbaum， D.Gros， R.Tengi，“Five Papers on WordNet” Technical Report CSL Report 43, 2005 10 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 既存のシソーラスをソフトウェア部品のカテゴリ階層作成に利用問題点ソフトウェア部品には日常語とは用途が異なる単語や複合語が多い例1：「Collection」と「List」 – 日常語：上位下位関係は存在しない – プログラミングの分野：上位下位関係が存在する例2：「LinkedList」 – WordNetに記述がない →既存のシソーラスをソフトウェア部品のカテゴリ階層に用いるのは適当ではない 11 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ソフトウェア部品に適したシソーラスベーシックアイデアソースコード上にはソフトウェア部品に適した単語・複合語である識別子がある Javaクラスの利用関係を上位下位関係に利用 Javaソースコードの集合からソフトウェア部品に適したシソーラスを自動で作成 12 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 提案手法の概要 1. Javaクラスの利用関係を用いてシソーラスを作成 2. Javaクラスの集合からJavaクラスのクラスタと特徴語の集合を作成 3. ソフトウェア部品のカテゴリ階層を構築 A 1 2 3 1 2 3 1．シソーラス作成 3．シソーラスとシソーラス 4 部品 (Javaクラス) 2．部品のクラスタ作成クラスタからカテゴリ階層を構築 1 4 特徴語1，特徴語2，．．． 2 3 特徴語3，特徴語4，．．．クラスタ B C 1 4 2 3 カテゴリ階層 13 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 1．Javaクラスの利用関係を用いたシソーラスの作成（1/2） Javaクラス間の利用関係とソースコード中の識別子を利用上位下位関係が期待できる利用関係を選択オブジェクト指向の観点から上位下位が存在すると考えられる関係以下の関係にある識別子の組を取得上位下位継承関係親クラス名実装関係親インタフェース名子インタフェース名インタフェース名クラス名フィールド変数の型と変数名型名（クラス名）子クラス名変数名例： java.util.List が java.util.Collection を継承しているので Collectionを上位，Listを下位とする 14 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 1．Javaクラスの利用関係を用いたシソーラスの作成（2/2）利用関係ごとに設定した閾値以上の出現回数のもののみ取得例：継承→1回，実装→1回，変数の型と変数名→5回作成するシソーラス取得した識別子と上位下位関係の有向グラフ頂点：識別子有向辺：上位の識別子から下位の識別子に引いた辺 Object 上位下位利用関係取得回数 Object EventObject 継承 1 Serializable EventObject 実装 1 EventObject AWTEvent 継承 1 AWTEvent ActionEvent 継承 1 AWTEvent AWTEvent ItemEvent Event 変数変数 6 3 ソースコードから取得した識別子と上位下位関係 Serializable EventObject AWTEvent ActionEvent ItemEvent 有向グラフ（シソーラス） Event 15 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 2.Javaクラスのクラスタと特徴語の作成（1/2）Ｊａｖａクラスの集合から部品のクラスタと特徴語の集合を作成出現する単語に基づく部品のクラスタを作成クラスタに定数個の特徴語を付ける部品のクラスタ 1 2 3 1 2 特徴語1，特徴語2 特徴語3 … 3 4 特徴語4，特徴語5 特徴語6 … 4 部品(Javaクラス) クラスタリング結果 16 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 2.Javaクラスのクラスタと特徴語の作成（2/2）具体的なクラスタリング手法手順1．部品×単語の行列を作成要素（i , j）の値：単語jが部品iに出現する回数手順2．手順1で作成した行列にLSAを適用する LSA（潜在的意味解析法）：類似した単語が出現する部品同士を類似したものとみなすことが出来る手順3．手順2で作成した行列から部品のクラスタとクラスタの特徴語を決定部品4 部品1 A B B G G F 部品5 部品2 A B C D E 部品1 A B 部品2 C D E 部品3 F G H H 部品4 部品6 部品3 B C C C D E G H 部品5 部品6 E F G H 17 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3．カテゴリ階層の構築（1/5）クラスタリング結果を用いてカテゴリを作成するクラスタの特徴語がシソーラス内にあればカテゴリを作成作成したカテゴリにクラスタに含まれる部品を割り当てるシソーラス内で下位に2個以上カテゴリ名に対応する頂点を持つ頂点のカテゴリを作成 A 部品 A B 1 2 E F 5 6 特徴語単語 A クラスタ A E 3 4 B 2 3 4 F 1 2 D D クラスタリング結果 1 C E B E G シソーラス 3 4 5 6 F 5 6 18 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3．カテゴリ階層の構築（2/5）カテゴリ間の親子関係の作成以下の条件を満たすカテゴリ間に親子関係を作成シソーラス内で，カテゴリ名に対応する頂点間に経路がある上記の経路に，他にカテゴリ名に対応する頂点がない親子関係にあるカテゴリ間には「（親）→（子）」の有向辺を引く A 部品 A B 1 2 E F 5 6 特徴語クラスタ A E 3 4 単語 A 1 2 3 4 1 2 B C D D E クラスタリング結果 B F G シソーラス E 3 4 5 6 F 5 6 19 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3．カテゴリ階層の構築（3/5）部品を含まないカテゴリを作成する理由選択肢が多すぎる状況を回避するため選択肢が多すぎるとどれを選んでいいか分からない A B D F A J G K C … … E H I I B … C L M N O J K L M N O … … … … … … … 20 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3．カテゴリ階層の構築（4/5）部品を含まないカテゴリを作成する理由例：カテゴリ「Closeable」の子カテゴリシソーラスには「Closeable」の下位には「Writer」「Reader」「InputStream」「OutputStream」があるが，クラスタの特徴語にはない Closeable Closeable AudioInputStream InputStream Writer … OutputStream Reader … … BufferedInputStream BufferedOutputStream BufferedReader ByteArrayOutputStream ByteArrayInputStream … CipherOutputStream CheckedInputStream CheckedOutputStream CipherInputStream DataInputStream DataOutputStream DeflaterOutputStream DigestInputStream DigestOutputStream DigestOutputStream FileInputStream JarInputStream CharArrayWriter BufferedWriter CharArrayReader FilterWriter FileOutputStream FileReader FileWriter FilterInputStream GZIPInputStream GZIPOutputStream InflaterInputStream InputStreamReader ObjectOutputStream PipedInputStream JarOutputStream LineNumberReader ObjectInputStream シソーラスカテゴリ階層 PipedOutputStream PrintStream FilterOutputStream PipedReader PrintWriter ProgressMonitorInputStream FilterReader PushbackInputStream StringBufferInputStream ZipInputStream ZipOutputStream SequenceInputStream PushbackReader StringReader StringWriter 21 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3．カテゴリ階層の構築（5/5）部品を含まないカテゴリを作成する理由「Writer」「Reader」「InputStream」「OutputStream」のカテゴリを作成，「Closeable」の子カテゴリにする Closeable InputStream AudioInputStream CheckedInputStream ByteArrayInputStream FilterInputStream FilterOutputStream OutputStream FileInputStream StringBufferInputStream InflaterInputStream DataOutputStream DigestOutputStream DeflaterOutputStream BufferedOutputStream JarOutputStream PipedOutputStream ZipOutputStream ByteArrayOutputStream FileOutputStream GZIPInputStream ProgressMonitorInputStream DataInputStream SequenceInputStream JarInputStream CipherInputStream FileReader CharArrayReader PushbackReader FilterReader Writer DigestInputStream BufferedInputStream CharArrayWriter BufferedWriter DigestOutputStream PrintWriter PushbackInputStream ObjectInputStream PipedReader LineNumberReader InputStreamReader GZIPOutputStream ZipInputStream BufferedReader StringReader CipherOutputStream PipedInputStream CheckedOutputStream Reader FilterWriter FileWriter ObjectOutputStream PrintStream StringWriter PipedWriter 22 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 適用実験実験の目的カテゴリ名による段階的な絞り込みを行うことが出来るカテゴリ階層が作成できているかを調べる実験内容入力：JDK1.4の全クラス(約11000クラス) シソーラスへの登録の閾値継承関係，実装関係：1回フィールド変数の型と変数名：10回出力結果総カテゴリ数カテゴリ間の親子関係カテゴリに割り当てられた部品数カテゴリに割り当てられた延べ部品数カテゴリに含まれる部品（平均） 1109個 2501組 6000個 18583個 16.75個 23 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価方法評価項目カテゴリ名と含まれる部品の評価カテゴリ間の親子関係の評価 24 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University カテゴリ名と含まれる部品の評価評価 1109個のカテゴリから無作為に50個選出カテゴリと部品324組カテゴリ名と含まれる部品の適合率を求める適合条件1：カテゴリ名と部品名が同じ適合条件2：カテゴリ名が部品名の｛複数形，省略語，部分語，類似語｝である適合条件3：カテゴリ名が部品の特徴の一部を表す適合例不適合例カテゴリ名 JarFile Reader 部品名 JarException Source 結果 83.6%（271組/324組） 25 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University カテゴリ間の親子関係の評価評価 2501組の親子関係から無作為に200組を選出親子関係の適合率を求める適合条件：子カテゴリが親カテゴリの一種適合例不適合例親カテゴリ JComponent ClassFile 子カテゴリ JLabel ClassReader 結果 64.0%（128組 / 200組） 26 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 考察（1/2）カテゴリ名とカテゴリに含まれる部品有効な分類が得られたカテゴリ名と部品が1つも適合しないものも存在カテゴリ名として有用でない識別子がカテゴリ名になっているクラスタに付ける特徴語を定数個にしたため – クラスタ内の部品の特徴を表していないものも特徴語に含まれる 27 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 考察（2/2）カテゴリ間の親子関係あまり高い値が得られなかった継承関係として機能を利用するためのものがみられた → より柔軟な登録条件を用いる – アクセス制御子による重みの設定 – 他のクラスからの利用頻度による重みの設定変数の型と変数名の組はシソーラスに登録されなかった閾値を下げればいくつか得られたが，省略語が多く有用なものではなかった → → より柔軟な登録条件を用いる省略語をシソーラスに登録しないようにする – 省略語の辞書を用いる 28 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University まとめと今後の課題まとめ Javaの利用関係を用いたシソーラスの作成作成したシソーラスを用いたカテゴリ階層の構築実際のソースコードを用いた実験今後の課題カテゴリ間の親子関係の精度向上より柔軟な閾値の設定新たな方法による単語の組の抽出共通する接頭語・接尾語の除去 – 例：JComponent(上位) JLabel(下位) → Component(上位) Label(下位) カテゴリ検索を行うユーザーインターフェースの開発 29 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University