ソースコード中の識別子に基づく
カテゴリ階層構築手法
大阪大学 大学院情報科学研究科
○宮崎 宏海,早瀬 康裕,市井 誠,
松下 誠,井上 克郎
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)
Javaクラスの集合から部品のクラスタと特徴語の集
合を作成
出現する単語に基づく部品のクラスタを作成
クラスタに定数個の特徴語を付ける
部品のクラスタ
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
ダウンロード

2 - Software Engineering Laboratory