ソースコードの特徴語を用いた Javaソフトウェア部品の

ソースコードの特徴語を用いた
Javaソフトウェア部品の
自動分類システム
井上研究室
仁井谷竜介
背景

ソフトウェア部品検索システムの必要性


ソフトウェア開発の大規模化・複雑化
ソフトウェアを再利用したり，管理する機会が増えた
様々なソフトウェア部品検索システム
2005/02/24
平成16年度特別研究報告
2
検索システム

クエリ検索システム



クエリ（検索語・検索文）を入力として与える
適切なクエリを与えれば意図通りのものが得られる
カテゴリ検索システム

あらかじめ用意されたカテゴリから文書を探す



カテゴリはツリー状に構成されていることが多い
クエリを入力しなくてよい
段階的に絞り込むことができる

コンピュータ → ソフトウェア → 表計算
本研究ではこちらに着目
2005/02/24
平成16年度特別研究報告
3
カテゴリ検索を部品に適用したときの問題点

部品をカテゴリに分類する必要がある


追加・更新する部品をどのカテゴリに入れるか判断し
なければいけない
対象数が多い

カテゴリを再構成・維持する必要がある

分類・カテゴリ維持は人手では困難
自動化が不可欠

2005/02/24
平成16年度特別研究報告
4
研究の目的


ソフトウェア部品を対象としたカテゴリ検索用の自動分類
カテゴリのツリー(カテゴリ間の関係)を自動作成



Javaのクラスをソフトウェア部品とみなす
入力としてソースコードを用いる
低コストでカテゴリ検索の利点が得られる


2005/02/24
クエリを入力しなくてよい
段階的に絞り込むことができる
平成16年度特別研究報告
5
提案手法

ソースコードの特徴語に着目した分類
ソースコードを入力として部品をカテゴリに分類
カテゴリ間にツリー状の関係を作成


この発表では分類までを説明
特徴語の決定
特徴語=カテゴリ
として部品を分類
input
input
read
file
read
write
file
file
部品(=Javaクラス)
のソースコード
2005/02/24
カテゴリ間の関係を作成
file
write
input
read
write
平成16年度特別研究報告
6
分類の手順
(2)
(1)
単語の出現情報
解析
(2.1)
出現重み
計算
(2.2)
重み
利用関係
計算
(2.3)
LSA
計算
重み
単語
重み
(3)
単語一覧（特徴語の候補）
特徴語
決定
1. ソースコードを解析
2. 単語重み計算
部品と特徴語の組
1. 出現重み計算
2. 利用関係による重み加算
(4)
3. LSA（潜在的意味解析法）
部品と
カテゴリ
3. 単語重みの高い上位10個の語を特徴語とする
カテゴリの組
生成
4. 1つの特徴語をそれぞれ1つのカテゴリとして部品を分類
2005/02/24
平成16年度特別研究報告
7
単語重み計算
1.
ソースコードの出現場所による重み計算

2.
利用関係による重み加算


3.
出現した場所（クラス定義など）を考慮した重要度
利用している部品中の語の重みを加算する
例：継承，メソッド呼び出し，インスタンス化
LSA*（潜在的意味解析法）

出現の類似度で重みを補正
語 file read binary
親クラス 5 3
0
子クラス 1 0
2
子クラス
* Landauer, T. K., Foltz, P. W., & Laham, D. (1998). Introduction to Latent Semantic Analysis.
Discourse Processes, 25, 259-284.
2005/02/24
平成16年度特別研究報告
3.5 1.5
2
2.の継承関係での例
8
特徴語の決定


部品のソースコードから単語重みを求める
ここでは上位10語を部品の特徴語とする
全ソースコードから得られた語（特徴語の候補）
単語の出現情報
input
output
read
write
get
なし
なし
メソッド定義3
メソッド呼出2
なし
メソッド定義7
メソッド呼出8
set
メソッド定義2
メソッド呼出10
file
クラス定義 1
メソッド定義 2
…
対象部品ソースコード中に出現する単語の出現箇所と出現回数
部品と関連が強いと
ソースコードに出現しない語も特徴語になり得る
単語重み
特徴語
2005/02/24
62.1
○
0
90.7
0
○
平成16年度特別研究報告
35.6
18.1
113.9
○
9
実装
ソースコード
分類部
検索部
カテゴリ名
クラス名
検索部
単語重み計算部
利用関係
計算部
入力
読込
SPARS-J
出現重み
計算部
LSA
計算部
2005/02/24
検索
検索結果
カテゴリ
DB
登録
SPARS 読込 SPARS-DB 特徴語
読込部
決定部
DB
部品情報
表示部
カテゴリ
生成部
登録
平成16年度特別研究報告
カテゴリ情報
表示部
カテゴリ木
表示部
10
評価

実際に分類を行い，検索結果を評価する


入力はロボットシステム部品254クラス(35システム)
カテゴリと部品の間の適合率を求める
各カテゴリに属する部品の適合率
 各部品が属するカテゴリの適合率


適合の判断はソースコードを見て行った
適合率＝
2005/02/24
|検索結果 ∩ 適合部品|
|検索結果|
平成16年度特別研究報告
11
分類結果の一例

カテゴリに属する部品の例


Pointに属する部品（実際は108クラス）
適合率 0.93
部品
適合

部品が属するカテゴリの例


riu.parts.EnemyStatusが属するカテゴリ
適合率 0.7
理由
カテゴリ
適合
理由
teamZero.Point
○
座標を扱う
Point
○
座標を扱う
mirror.Calc
○
座標計算クラス
EnemyStatus
○
敵の状態を表す
mirror.posPredict.WaveEstim
ation
○
位置予測
Get
○
状態取得メソッドが多い
kuro.Point
○
座標を扱う
Time
○
時間を扱う
riu.parts.EnemyStatus
○
座標を扱う
Riu
○
パッケージ名
riu.Geometry.Geometry
○
座標計算クラス
Set
×
状態設定は行わない
mt.GravPoint
○
座標を扱う
Distance
○
距離を扱う
heg.Vector2D
○
座標クラス
This
×
Java予約語
pbl3.BulletData
○
座標を扱う
Param
×
Javadocタグ(@param)
riu.NotSerializable
×
空のクラス
Move
○
移動に関わる情報を持つ
...
2005/02/24
平成16年度特別研究報告
12
分類結果の適合率

各カテゴリに属する部品の適合率(左)


各部品が属するカテゴリの適合率(右)


avg. 0.85
カテゴリ
部品
avg. 0.86
縦棒が適合率
適合率0のカテゴリも存在した
高い適合率が得られた
2005/02/24
平成16年度特別研究報告
13
考察


有効な分類が得られた
不適当な特徴語がある




2005/02/24
Javadocタグ(@param, @returnなど)
HTMLタグ(br, li)
前置詞，助詞，代名詞(to, in, this)
Javaの予約語(this)
平成16年度特別研究報告
14
まとめと今後の課題

まとめ



ソースコードの特徴語に着目した分類手法
提案手法による分類の有効性を確認
今後の課題


2005/02/24
部品ごとの適切な特徴語の数の調査
特徴語として適さない語の排除方法の考案
平成16年度特別研究報告
15
2005/02/24
平成16年度特別研究報告
質問をどうぞ
終
16
クエリ入力を必要としない検索システムの例

SPARS-J パッケージブラウザ


パッケージ構造に従った検索
異なるパッケージ内のものを検索できない
パッケージブラウザ
サブパッケージ一覧
クラス一覧
2005/02/24
平成16年度特別研究報告
17
潜在的意味解析法 LSA




Latent Semantic Analysis
自然言語で書かれた文書、単語の類似度を計
測する
ベクトル空間モデルに従った手法の一つ
ベクトル空間モデルでは検出できない間接的な
関連の抽出を可能にしている
2005/02/24
平成16年度特別研究報告
18
LSA の例
文書1
文書4
A B B F
文書2
B
G G
文書ベクトル
文書5
A B C D E
文書3
単語ベクトル
F G H H
単語頻度行列を
文書間、単語間の類似度は
文書6
作成
Cベクトル間の角度によって
C C D
E G H
表す
2005/02/24
A
B
C
D
E
F
G H
1
1
2
0
0
0
1
0
0
2
1
1
1
1
1
0
0
0
3
0
1
3
1
0
0
0
0
4
0
0
0
0
0
0
2
0
5
0
0
0
0
0
1
1
2
6
0
0
0
0
1
0
1
1
LSA
A
B
C
D
E
F
G
H
1
0.3
0.7
0.9
0.4
0.3
0.2
0.3
0.3
2
0.4
1.0
1.4
0.6
0.3
0.2
0.1
0.1
3
0.6
1.5
2.3
1.0
0.4
0.2
-0.2
-0.2
4
0.1
0.1
-0.2
0.0
0.2
0.4
0.9
0.9
5
0.1
0.2
-0.2
0.0
0.4
0.6
1.5
1.4
6
0.1
0.2
-0.1
0.0
0.3
0.4
1.0
0.9
平成16年度特別研究報告
19
LSA の効果


間接的に関連している文書間の類似度も高い
文書間の類似度がより鮮明になる
文書間の類似度行列
1
2
3
4
5
6
1
1.0
2
1
2
3
4
5
6
0.2
-0.1
-0.3
-0.3
-0.5
1
1.0
1.0
0.9
-0.6
-0.6
-0.5
0.2
1.0
0.5
-0.5
-0.9
-0.5
2
1.0
1.0
1.0
-0.8
-0.8
-0.7
3
-0.1
0.5
1.0
-0.2
-0.4
-0.5
3
0.9
1.0
1.0
-0.8
-0.8
-0.8
4
-0.3
-0.5
-0.2
1.0
0.3
0.5
4
-0.6
-0.8
-0.8
1.0
1.0
1.0
5
-0.3
-0.9
-0.4
0.3
1.0
0.5
5
-0.6
-0.8
-0.8
1.0
1.0
1.0
6
-0.5
-0.5
-0.5
0.5
0.5
1.0
6
-0.5
-0.7
-0.8
1.0
1.0
1.0
LSA適用前
2005/02/24
LSA適用後
平成16年度特別研究報告
20
ソースコードを入力とする理由

ドキュメントの内容は有用であることは確かだが，
問題点も多い



ファイル形式がさまざま
記述のフォーマットもまちまち
内容は自然言語なので意味の理解は自動化する上
で困難

2005/02/24
どの部品を表すドキュメントか，すらわからない可能性が
ある
平成16年度特別研究報告
21
カテゴリ間の関係

親子関係（カテゴリ木）

カテゴリを部品の集合としてみたときの包含関係
A⊂B なら Bが親 Aが子
 誤差を認める


集合類似関係


カテゴリを部品の集合としてみたとき類似
類似関係

2005/02/24
カテゴリに対応する特徴語間の類似度が高い
平成16年度特別研究報告
22
評価実験


実際に分類を行い，検索結果を評価する
分類対象はRobocodeのロボット35体




2005/02/24
小規模のソースコード集合を作れる
出現する単語にある程度偏りが見られる
作者が独立して複数いるソースコード集合を作れる
適合しているかどうかの判断がしやすい
平成16年度特別研究報告
23
得られたカテゴリの一部









Get
Point
Enemy
Time
Orbit
This
Target
Param
Br
2005/02/24
平成16年度特別研究報告
24
適合条件

適合する


親クラスの特徴語
適合しない



2005/02/24
そのカテゴリに含まれる部品の集合が同様のもので
あるが，そのうちのどれかを表すだけの特徴語がそ
のカテゴリに対応している
ソースコード中に現れるがあまり特徴を表さない
自身の特徴を表さないような子クラスの特徴語
平成16年度特別研究報告
25
適合率の低いカテゴリ


英語ドキュメントコメント中の前置詞（toなど)
ドキュメントコメント中に出現するタグ




@paramなど
HTML
this
IDE（Eclipse)によって生成されているコメント中
の語
2005/02/24
平成16年度特別研究報告
26
再現率


再現率を求めるには，部品ごとに「特徴語である
べき語」の一覧を作らなければいけない
作業量が多く困難
2005/02/24
平成16年度特別研究報告
27
特徴語の数

10個に根拠はない


複雑な部品は10個では足らないはず


ソースコードの語数や，重みに合わせて部品ごとに特
徴語の数を決めるとしても，その指標がわからないの
で10語で評価してみた
再現率は低いに違いない
再現率が高くなるような数は今後の課題
2005/02/24
平成16年度特別研究報告
28
以降ゴミ箱
2005/02/24
平成16年度特別研究報告
29
実験に使用した適合率
（式の貼り付け)
2005/02/24
平成16年度特別研究報告
30
背景

ソフトウェア開発の大規模化・複雑化

生成されたソフトウェアを再利用したり，管理する機
会が増えた
ソフトウェア部品検索システムの必要性

様々なソフトウェア部品検索システム

2005/02/24
多くがクエリとの適合度の高い部品を表示
平成16年度特別研究報告
31
背景

ソフトウェア部品検索システムの必要性



ソフトウェア開発の大規模化・複雑化
ソフトウェアを再利用したり，管理する機会が増えた
様々なソフトウェア部品検索システム

多くがクエリとの適合度が高い部品を表示
多くの検索システムはクエリを入力する必要がある
2005/02/24
平成16年度特別研究報告
32
クエリ入力の問題点

意図したものが得られない



検索されない
不要な情報の中に埋もれる
検索者が適切なクエリを入力する必要がある

2005/02/24
常に適切なクエリを知っているわけではない
平成16年度特別研究報告
33
カテゴリ検索システム

カテゴリ検索システムとは


自然言語，Webページ検索などに用いられる
あらかじめ用意されたカテゴリから文書を探す



カテゴリはツリー状に構成されていることが多い
文書は手動でカテゴリに分類されることが多い
利点


クエリを入力しなくてよい
段階的に絞り込むことができる

2005/02/24
コンピュータ → ソフトウェア → セキュリティ
平成16年度特別研究報告
34
自然言語を対象とする手法の適用
2005/02/24
平成16年度特別研究報告
35
SPARS-J

ソフトウェア部品検索システム


キーワード検索
 クエリを入力する必要がある
パッケージ構造に従った検索
 異なるパッケージ内のものを検索できない
クエリを入力
パッケージブラウザ
サブパッケージ一覧
クラス一覧
2005/02/24
平成16年度特別研究報告
36
分類の手順
(2)
(1)
解析
単語の
出現情報
(2.1)
(2.2)
出現重み
計算
重み
複合語
計算
(2.3)
重み
利用関係
計算
(2.4)
LSA
計算
重み
特徴語
重み
(3)
単語一覧
単語一覧
特徴語
決定
1. ソースコードを解析
2. 単語重み計算
部品と特徴語の組
1. 出現重み計算
2. 語の記法統一・複合語分割による重み再計算
(4)
3. 利用関係による重み加算
部品と
カテゴリ
4. LSA（潜在的意味解析法）
カテゴリの組
生成
3. 部品ごとに単語重みの高い上位10個の語を特徴語に
4. 1つの特徴語をそれぞれ1つのカテゴリとして部品を分類
2005/02/24
平成16年度特別研究報告
37
単語重み計算
1.
ソースコードの出現場所による重み計算

2.
語の記法統一・複合語分割による重み再計算

3.
XML_Parser→ Xml, Parser, XmlParser
利用関係による重み加算


4.
出現した場所（クラス定義など）を考慮した重要度
利用している部品中の語の重みを加算する
例：継承，メソッド呼び出し，インスタンス化
LSA（潜在的意味解析法）

2005/02/24
類似語を求める統計的手法
平成16年度特別研究報告
38
適合率

検索結果がどれだけ正しいかを表す値
適合率＝
|検索結果 ∩ 適合文書|
|検索結果|
検索結果
2005/02/24
平成16年度特別研究報告
適合
不適合
39
評価する値

カテゴリと部品の間の適合率を求める



各カテゴリに属する部品の適合率
各部品が属するカテゴリの適合率
SPARS-J （全文検索)との検索結果の比較


SPARS-Jで検索されず本システムで検索されたもの
の中での適合率
SPARS-Jで検索されず本システムで上位10件以内
の中での適合率
適合率＝
2005/02/24
|検索結果 ∩ 適合文書|
|検索結果|
平成16年度特別研究報告
40
評価

実際に分類を行い，検索結果を評価する


入力はRobocodeのロボット35体
カテゴリと部品の間の適合率を求める
各カテゴリに属する部品の適合率
 各部品が属するカテゴリの適合率


SPARS-J （全文検索)との検索結果の比較

SPARS-Jで検索されず本システムで検索されたものの
中での適合率
適合率＝
2005/02/24
|検索結果 ∩ 適合文書|
|検索結果|
平成16年度特別研究報告
41
SPARS-Jとの比較

SPARS-Jで検索されず本システムで検索されたものの中での適合率(左)


avg. 0.4933
SPARS-Jで検索されず本システムで上位10件以内の中での適合率(右)

avg. 0.5111
検索結果がSPARSの検索
結果に含まれたカテゴリ
2005/02/24
平成16年度特別研究報告
42
SPARS-Jとの比較

SPARS-Jで検索されず本システムで検索された
ものの中での適合率

avg. 0.4933
本システム
SPARS-J
この部分での適合率
検索結果がSPARS-Jの検索
結果に含まれたカテゴリの場合
適合率が計算できない
適合率が計算できない
2005/02/24
平成16年度特別研究報告
43
カテゴリ間の関係の評価
(UNDONE)
(適合率っぽい評価値を出す予定)
2005/02/24
平成16年度特別研究報告
44
没の図
2005/02/24
平成16年度特別研究報告
45
考察

カテゴリと部品の間では高い適合率が得られたのに対し，
SPARS-Jとの比較では低い適合率となった

特徴語が部品につき10個固定なのが問題
 10個では足りないような複雑な部品



10個では多すぎるような単純な部品



高い適合率
特徴語のほとんどあるいは全てがソースコード中に出現するため，
SPARS-Jで検索可能
低い適合率
無関係な特徴語が幾つも含まれる
適合率の平均は高いが，属する部品の適合率が0のカ
テゴリが存在する

2005/02/24
特徴語として適さないが重みが高い特徴語がある
平成16年度特別研究報告
46
没アニメーション
2005/02/24
平成16年度特別研究報告
47
背景

ソフトウェア開発の大規模化・複雑化

生成されたソフトウェアを再利用したり，管理する機
会が増えた
ソフトウェア部品検索システムの必要性

様々なソフトウェア部品検索システム

2005/02/24
多くがクエリとの適合度の高い部品を表示
平成16年度特別研究報告
48
カテゴリ検索システム

カテゴリ検索システムとは


自然言語，Webページ検索などに用いられる
あらかじめ用意されたカテゴリから文書を探す


カテゴリはツリー状に構成されていることが多い
利点



段階的に絞り込むことができる
文書中に含まれない単語による検索ができる
クエリ（検索語）を入力しなくてよい
ただし分類の手間が必要
2005/02/24
平成16年度特別研究報告
49
研究の目的


カテゴリ検索用の分類を自動で行う
カテゴリのツリー(カテゴリ間の関係)を自動作成
低コストでカテゴリ検索の利点が得られる
2005/02/24
平成16年度特別研究報告
50

Download Report