ソースコードの特徴語を用いた Javaソフトウェア部品の 自動分類システム

Presentation on theme: "ソースコードの特徴語を用いた Javaソフトウェア部品の 自動分類システム"— Presentation transcript:

1 ソースコードの特徴語を用いた Javaソフトウェア部品の 自動分類システム
井上研究室の仁井谷です． ソースコードの特徴語に着目して，Javaソフトウェア部品を 自動分類し，カテゴリ検索に利用する手法を考案しましたので， それについて発表をさせていただきます． # 「本日は」などはタブーみたいです # タイトルの繰り返しは能なしらしいです 井上研究室 仁井谷 竜介

2 背景 ソフトウェア部品検索システムの必要性 様々なソフトウェア部品検索システム ソフトウェア開発の大規模化・複雑化
ソフトウェアを再利用したり，管理する機会が増えた 様々なソフトウェア部品検索システム まず，背景ですが， 現在ソフトウェア部品検索システムの必要性が言われています． その背景として，ソフトウェア開発の大規模化・複雑化や， ソフトウェアを再利用したり，管理する機会が増えた， ということがあります． そして実際に，様々なソフトウェア部品検索システムが提案・実現されています． # 以降メモ その多くは検索者にクエリを入力させ，そのクエリとの適合度の高い部品を表示する形式をとっています． 言い換えれば，多くの検索システムはクエリを入力する必要があります． 2005/02/24 平成16年度 特別研究報告

3 検索システム クエリ検索システム カテゴリ検索システム クエリ（検索語・検索文）を入力として与える
適切なクエリを与えれば意図通りのものが得られる カテゴリ検索システム あらかじめ用意されたカテゴリから文書を探す カテゴリはツリー状に構成されていることが多い クエリを入力しなくてよい 段階的に絞り込むことができる コンピュータ → ソフトウェア → 表計算 ソフトウェア部品に限らず検索システムを大きく分けたとき， クエリ検索システムと，カテゴリ検索システムに分けられます． クエリ検索システムは，検索語あるいは検索文を与えることにより，それに適合するもの検索するシステムです． その利点としては，適切なクエリを与えれば，意図通りの検索結果が得られる点です． また，カテゴリ検索システムは，あらかじめ用意されたカテゴリの中から文書を探す，というシステムです． 用意されたカテゴリは，大抵はツリー状に構成されており，検索者は段階的に自分の意図するものにカテゴリを絞り込んでいけます． 例えば，ここにあるように，コンピュータからソフトウェア，ソフトウェアからセキュリティ， というような絞り込みができます． 本研究では，カテゴリ検索に着目したいと思います． # 以降メモ 他の利点としては，文書中に出現する単語の中から検索する，全文検索のようなものと異なり， 文書中の単語に頼らない検索ができます 本研究では，カテゴリ検索に着目し， ソフトウェア部品検索システムに適用するとどうなるかについて考えたいと思います． 本研究ではこちらに着目 2005/02/24 平成16年度 特別研究報告

4 カテゴリ検索を部品に適用したときの問題点
部品をカテゴリに分類する必要がある 追加・更新する部品をどのカテゴリに入れるか判断しなければいけない 対象数が多い カテゴリを再構成・維持する必要がある 分類・カテゴリ維持は人手では困難 自動化が不可欠 カテゴリ検索システムの問題点として，分類する作業が必要となります． そのためには，追加あるいは更新される部品が，どのカテゴリに入れるのが適切か判断しなければいけません さらに，対象数が多いのでそのための手間は非常に大きなものとなります． また，今までにない機能の部品の追加や，カテゴリ内の部品数の増加などが起こった場合に， 新しいカテゴリの追加や，巨大なカテゴリの分割といった，カテゴリの再構成・維持作業も必要となります． 従って，これらの分類に関わる作業は人手では困難であるといえ， 実際にソフトウェア部品にカテゴリ検索システムを適用するには自動化は不可欠だといえます． # 以降メモ 自動化したい 低コスト 検索を必要とするぐらいは対象数があるはず 開発者が分類 追加時にどのカテゴリにするか決める必要がある 更新する度にカテゴリを見直すコストがある 検索システム管理者が分類 追加・更新するソースコードを理解しないといけない 対象数が多い 人手では困難 ソースコードに対する理解が必要 そして，カテゴリ検索をするための準備作業も自然言語などの場合と同様にあると言えます． その一番の（他には収集とか）問題となるのが，検索対象となるソフトウェア部品の分類作業です． 部品数が少なくても困難な作業ではありますが，検索システムを必要とするぐらいは部品が数あるはずなので， その作業量は非常に大きくなります． そのためには，追加あるいは更新される部品の内容について理解していないといけません． 2005/02/24 平成16年度 特別研究報告

5 研究の目的 ソフトウェア部品を対象としたカテゴリ検索用の自動分類 カテゴリのツリー(カテゴリ間の関係)を自動作成
Javaのクラスをソフトウェア部品とみなす 入力としてソースコードを用いる 低コストでカテゴリ検索の利点が得られる クエリを入力しなくてよい 段階的に絞り込むことができる そこで，本研究ではJavaソフトウェア部品を対象としたカテゴリ検索を行うための 分類とカテゴリのツリーの生成を，ソースコードを入力として自動で行いたいと思います． それにより，人手に比べ低いコストで先ほど挙げたカテゴリ検索の利点が得られると考えられます． # 以降メモ なお，対象言語はJavaにしたいと思います． 2005/02/24 平成16年度 特別研究報告

6 提案手法 ソースコードの特徴語に着目した分類 ソースコードを入力として部品をカテゴリに分類 カテゴリ間にツリー状の関係を作成
以上の目的を達成するため，ソースコードの特徴語に着目し， ソフトウェア部品を分類する手法を提案します． ↓クリック まず，部品のソースコードを入力として与えます． このソースコードの特徴語を決定します． この例では，input, read, fileがこのソースコードの特徴語となります． 次に，先ほど決定した特徴語をそれぞれ1つのカテゴリとして部品を分類します． この部品は，input, read, fileの3つのカテゴリに分類されます． このままではカテゴリがたくさん並ぶだけになるので， カテゴリ間に関係を与え，このようにツリーのような関係を作成します． この発表では分類のところを説明します． # 以降メモ 特徴語は，ソースコードを特徴づける重要な語 →後で説明する（特徴語決定のページで） 特徴語を元にカテゴリを決定 inputを特徴語とする部品の集合をカテゴリinputとする *処理の流れ ソースコード 特徴語決定 カテゴリ カテゴリ木 *処理の流れのうちのどこか重要なところをこの後説明 この発表では分類までを説明 特徴語=カテゴリ として部品を分類 特徴語の決定 カテゴリ間の関係を作成 input read file write input read file write read file input 部品(=Javaクラス) のソースコード write file 2005/02/24 平成16年度 特別研究報告

7 分類の手順 解析 出現重み 計算 利用関係 計算 LSA 計算 単語一覧（特徴語の候補） 特徴語 決定 ソースコードを解析 単語重み計算
(2) (1) (2.1) (2.2) (2.3) 単語の出現情報 解析 出現重み 計算 利用関係 計算 LSA 計算 では，分類の流れについて説明したいと思います ↓クリック ソースコードを解析し，単語一覧の取得と単語の出現情報を取得します． 次に，単語の出現情報を用いて特徴語を決定するための重みである「単語重み」を求めます． 中で4つの手法を用いて，重みの計算をしていますが，後で説明するのでここでは省きます． 次に，部品ごとに単語を重みでソートし，それぞれ上位10個の語を特徴語と決定します． 最後に，特徴語をそれぞれ1つのカテゴリとして部品を分類します． 最終的には，部品とカテゴリの組が得られます． 重み 重み 単語 重み (3) 単語一覧（特徴語の候補） 特徴語 決定 ソースコードを解析 単語重み計算 出現重み計算 利用関係による重み加算 LSA（潜在的意味解析法） 単語重みの高い上位10個の語を特徴語とする 1つの特徴語をそれぞれ1つのカテゴリとして部品を分類 部品と特徴語の組 (4) カテゴリ 生成 部品と カテゴリの組 2005/02/24 平成16年度 特別研究報告

8 単語重み計算 ソースコードの出現場所による重み計算 利用関係による重み加算 LSA*（潜在的意味解析法）
出現した場所（クラス定義など）を考慮した重要度 利用関係による重み加算 利用している部品中の語の重みを加算する 例：継承，メソッド呼び出し，インスタンス化 LSA*（潜在的意味解析法） 出現の類似度で重みを補正 先ほど省略した特徴語を決定するときの重み計算の説明を行いたいと思います． まず，1番ですが，これは単語が出現した場所が クラス定義か，変数名かという情報を考慮した重要度の計算を行います． 次に，2番ですが， まず，利用関係とは，継承や・・・を指します． この計算は，利用している部品に存在する語の重みを，対象の部品の語の重みに加算します． これにより，差分しかかかれていない子クラスに親クラスの語の重みが加えられる，などの変化があります． 最後にLSAですが，これは出現の傾向が類似する語には似たような重みがつくような補正をかけます． # 以降メモ 次に2番ですが， ここでは，大文字小文字の使い方や，アンダースコアを挟む，挟まないなどの記法の統一と， 複数の語が組み合わさってできている語から，その一部あるいは全部で構成される語を切り出しを行います． 単語の一覧が処理前と変化するので，それにあわせた重みの再計算を行います． 対象語の削減 分類に影響のない語を削除 最後にLSAですが，これは統計的な処理により，先ほどの「fileとreadに関係するinputの重みが高くなる」 というような変化が得られます． 語 file read binary 親クラス 子クラス 子クラス 2.の継承関係での例 * Landauer, T. K., Foltz, P. W., & Laham, D. (1998). Introduction to Latent Semantic Analysis. 　Discourse Processes, 25, 2005/02/24 平成16年度 特別研究報告

9 特徴語の決定 … 部品のソースコードから単語重みを求める ここでは上位10語を部品の特徴語とする
次に，ソースコードの特徴語決定，について説明したいと思います． ↓クリック まず，ソースコードに出現する単語について調べます． ↓クリック（上段四角） 上の語の一覧ですが，これは全ソースコードの語を表しています． この例では，input, output, writeという語はこの部品のソースコード中には出現していませんが， 別の部品のソースコード中には出現しています． ↓クリック（下段四角） 下の情報ですが，ソースコード中にreadという語がメソッド定義で3回出現し，メソッド呼出で2回出現した， というような情報を表しています． この情報を元に ↓クリック（なし） 　クリック（出現重み） 　クリック（・・・） 　クリック（単語重み） 　クリック（省略部分消去） 単語重みを求めます． 次に，この単語重みから特徴語を決定します． ↓クリック（特徴語） 実際は，上位10個の語ですが この例では，重みが上からfile, read, inputの3語がこのソースコードの特徴語と決定されました． ↓クリック（input） ここで注目していただきたいのは，ソースコード中に出現しないinputが特徴語になっている点です． この手法ではソースコードに出現しない語も， 部品との関連が強いと特徴語になり得ます． # 以降メモ 10個に根拠はない が，ソースコードの語数や，重みに合わせて部品ごとに特徴語の数を決める としても，その指標がわからないので10語で評価してみた まず，このソースコードの情報から，ソースコード中の出現重みを求めます． ↓クリック（出現重み） これは，この（ソースコードの行を指して）情報を実数の重みに変えたものです． ↓クリック（・・・） その後途中の計算は（時間の都合で）省きますが，いくつかの計算を経て特徴語を決定する重みを求めます ↓クリック（単語重み） 省略した計算も含めて，ここまでの流れで，ソースコードから特徴語を決定するための単語重みを求める計算が終わります． この手法ではソースコードに出現しない語も特徴語になり得ます． readやfileに高い重みがあることから，この部品はinputにも関連深いと考えられますが， この手法はその関連深い語を特徴語とすることを実現します． 全ソースコードから得られた語（特徴語の候補） input output read write get set file 単語の出現情報 なし なし なし クラス定義 1 メソッド定義 2 メソッド定義2 メソッド呼出10 メソッド定義7 メソッド呼出8 メソッド定義3 メソッド呼出2 対象部品ソースコード中に出現する単語の出現箇所と出現回数 部品と関連が強いと ソースコードに出現しない語も特徴語になり得る … 単語重み 特徴語 ○ ○ ○ 2005/02/24 平成16年度 特別研究報告

10 実装 分類部 検索部 単語重み計算部 カテゴリ名 クラス名 検索部 利用関係 計算部 部品情報 表示部 SPARS-J 出現重み 計算部
ソースコード 次に，実現したシステムについて説明したいと思います． 本システムは，大きく分類部，検索部の2に分かれており，先ほど説明した手法は， （指し示して）単語重み計算部と特徴語決定部で実現されています． また，特徴語をカテゴリとしてみなしてDBに登録する部分はカテゴリ生成部の一部として実現されています． # 以降メモ 説明してない部分ばっさり切った方がいいかも（でも説明付け足したし 単語重み計算部 カテゴリ名 クラス名 検索部 利用関係 計算部 入力 部品情報 表示部 検索 SPARS-J 読込 出現重み 計算部 LSA 計算部 検索結果 カテゴリ DB カテゴリ情報 表示部 登録 カテゴリ木 表示部 SPARS DB SPARS-DB 読込部 特徴語 決定部 カテゴリ 生成部 登録 読込 2005/02/24 平成16年度 特別研究報告

11 評価 実際に分類を行い，検索結果を評価する 適合率 ＝ 入力はロボットシステム部品254クラス(35システム)
カテゴリと部品の間の適合率を求める 各カテゴリに属する部品の適合率 各部品が属するカテゴリの適合率 適合の判断はソースコードを見て行った 次に実際に分類を行い，検索結果を評価した結果について説明したいと思います． 入力はRobocodeのロボット35体としました． 検索結果の評価として，今回は適合率を用いました． 適合率はこの式で与えられる，検索結果にどれだけ適合部品が含まれているかの割合です． 本発表では，この2つの適合率について述べたいと思います． # 以降メモ カテゴリ間の関係の評価 については省略 |検索結果 ∩ 適合部品| |検索結果| 適合率 ＝ 2005/02/24 平成16年度 特別研究報告

12 分類結果の一例 カテゴリに属する部品の例 部品が属するカテゴリの例 Pointに属する部品（実際は108クラス）
適合率 0.93 部品が属するカテゴリの例 riu.parts.EnemyStatusが属するカテゴリ 適合率 0.7 ではここで，分類結果の一例を示したいと思います 左はPointというカテゴリに属する部品の一部． 右はEnemyStatusという部品の属するカテゴリの一覧です． 適合率はPointはここにあるものだけだと9/10で0.9ですが 全て合わせると0.93 EnemyStatusは7/10で0.7です 部品 適合 理由 teamZero.Point ○ 座標を扱う mirror.Calc 座標計算クラス mirror.posPredict.WaveEstimation 位置予測 kuro.Point riu.parts.EnemyStatus riu.Geometry.Geometry mt.GravPoint heg.Vector2D 座標クラス pbl3.BulletData riu.NotSerializable × 空のクラス カテゴリ 適合 理由 Point ○ 座標を扱う EnemyStatus 敵の状態を表す Get 状態取得メソッドが多い Time 時間を扱う Riu パッケージ名 Set × 状態設定は行わない Distance 距離を扱う This Java予約語 Param Move 移動に関わる情報を持つ 2005/02/24 平成16年度 特別研究報告 ...

13 分類結果の適合率 適合率0のカテゴリも存在した 高い適合率が得られた 各カテゴリに属する部品の適合率(左)
avg. 0.85 各部品が属するカテゴリの適合率(右) avg. 0.86 縦棒が適合率 カテゴリ これは，分類結果の全体です 左の図はカテゴリの中に属している部品がどれだけ適切なものかを表しています． 横の例ではオレンジが適合として， 4/7です． 右の図は部品がどれだけ適切なカテゴリに属しているかを表しています． 横の例では，2/3です． 縦棒がそれぞれの適合率になっています． ↓クリック 適合率はそれぞれ0.85と0.86と高い値が得られましたが， このようにいくつか適合率が0のカテゴリがあることも確認されました． # 以降メモ より正確な適合率 0.8460 0.8633 下のグラフは，縦軸が適合率を表し，縦線の1つ1つが1つの（左を指して）カテゴリと （右を指して）部品に対応します． 横軸はカテゴリと部品をそれぞれ適合率でソートして並べています． 横軸の数はカテゴリの数． 0から10手前の空白は適合率0のカテゴリである． 横軸に平行な点線は適合率の平均． がありました． 部品 適合率0のカテゴリも存在した 高い適合率が得られた 2005/02/24 平成16年度 特別研究報告

14 考察 有効な分類が得られた 不適当な特徴語がある Javadocタグ(@param, @returnなど) HTMLタグ(br, li)
前置詞，助詞，代名詞(to, in, this) Javaの予約語(this) 以上の結果から得られた考察として， まずは，高い適合率から有効な分類が得られたと言えます． 特徴語として適さないが,重みが高い特徴語がある,と言う問題点が確認されました． それは，ドキュメントコメント中で頻繁に出る内容を表さないような語や， Thisといったものです． # 以降メモ 次に，特徴語が部品につき10個固定なのが問題であることがわかりました． 複雑な部品だと，特徴語が10個では足りず，その部品が属しているカテゴリに対し高い適合率を出しているものの， 特徴語のほとんどあるいは全てがソースコード中に出現しているため， SPARS-Jで検索ができていました． 逆に単純な部品だと，特徴語は10個では多すぎ，無関係な特徴語が含まれていました． そのため適合率は低くなっています． paramやbrやthisといった特徴語として適さないが重みが高く，特徴語になってしまうものがあることも確認されました． 2005/02/24 平成16年度 特別研究報告

15 まとめと今後の課題 まとめ 今後の課題 ソースコードの特徴語に着目した分類手法 提案手法による分類の有効性を確認
部品ごとの適切な特徴語の数の調査 特徴語として適さない語の排除方法の考案 本研究では，ソースコードの特徴語に着目した分類手法を提案・実現し， 有効な分類が可能であることを確認しました． また，今後の課題としては，部品ごとの適切な特徴語の数の調査， 特徴語として適さない語の排除方法の考案が考えられます． 2005/02/24 平成16年度 特別研究報告

16 以上で発表を終わります． 質問をどうぞ 終 2005/02/24 平成16年度 特別研究報告

17 クエリ入力を必要としない検索システムの例
SPARS-J パッケージブラウザ パッケージ構造に従った検索 異なるパッケージ内のものを検索できない パッケージブラウザ サブパッケージ一覧 クラス一覧 2005/02/24 平成16年度 特別研究報告

18 潜在的意味解析法 LSA Latent Semantic Analysis 自然言語で書かれた文書、単語の類似度を計測する
ベクトル空間モデルに従った手法の一つ ベクトル空間モデルでは検出できない間接的な関連の抽出を可能にしている 2005/02/24 平成16年度 特別研究報告

19 LSA の例 単語ベクトル 文書ベクトル 文書間、単語間の類似度は ベクトル間の角度によって 表す 文書1 文書4 文書2 文書5
3 4 5 6 A B C D E F G H A B B F G G 文書2 文書5 A B C D E F G H H 単語頻度行列を 作成 文書3 文書6 B C C C D E G H LSA 1 0.3 0.7 0.9 0.4 0.2 2 1.0 1.4 0.6 0.1 3 1.5 2.3 -0.2 4 0.0 5 6 -0.1 A B C D E F G H 2005/02/24 平成16年度 特別研究報告

20 LSA の効果 間接的に関連している文書間の類似度も高い 文書間の類似度がより鮮明になる 文書間の類似度行列 LSA適用前 LSA適用後
1 2 3 4 5 6 1.0 0.2 -0.1 -0.3 -0.5 0.5 -0.9 -0.2 -0.4 0.3 1 2 3 4 5 6 1.0 0.9 -0.6 -0.5 -0.8 -0.7 LSA適用前 LSA適用後 2005/02/24 平成16年度 特別研究報告

21 ソースコードを入力とする理由 ドキュメントの内容は有用であることは確かだが，問題点も多い ファイル形式がさまざま
記述のフォーマットもまちまち 内容は自然言語なので意味の理解は自動化する上で困難 どの部品を表すドキュメントか，すらわからない可能性がある 2005/02/24 平成16年度 特別研究報告

22 カテゴリ間の関係 親子関係（カテゴリ木） 集合類似関係 類似関係 カテゴリを部品の集合としてみたときの包含関係
A⊂B なら Bが親 Aが子 誤差を認める 集合類似関係 カテゴリを部品の集合としてみたとき類似 類似関係 カテゴリに対応する特徴語間の類似度が高い 類似度はコサイン尺度で求める 2005/02/24 平成16年度 特別研究報告

23 評価実験 実際に分類を行い，検索結果を評価する 分類対象はRobocodeのロボット35体 小規模のソースコード集合を作れる
出現する単語にある程度偏りが見られる 作者が独立して複数いるソースコード集合を作れる 適合しているかどうかの判断がしやすい 2005/02/24 平成16年度 特別研究報告

24 得られたカテゴリの一部 Get Point Enemy Time Orbit This Target Param Br 2005/02/24
平成16年度 特別研究報告

25 適合条件 適合する 適合しない 親クラスの特徴語
そのカテゴリに含まれる部品の集合が同様のものであるが，そのうちのどれかを表すだけの特徴語がそのカテゴリに対応している ソースコード中に現れるがあまり特徴を表さない 自身の特徴を表さないような子クラスの特徴語 2005/02/24 平成16年度 特別研究報告

26 適合率の低いカテゴリ 英語ドキュメントコメント中の前置詞（toなど) ドキュメントコメント中に出現するタグ this
@paramなど HTML this IDE（Eclipse)によって生成されているコメント中の語 2005/02/24 平成16年度 特別研究報告

27 再現率 再現率を求めるには，部品ごとに「特徴語であるべき語」の一覧を作らなければいけない 作業量が多く困難 2005/02/24
平成16年度 特別研究報告

28 特徴語の数 10個に根拠はない 複雑な部品は10個では足らないはず 再現率が高くなるような数は今後の課題
ソースコードの語数や，重みに合わせて部品ごとに特徴語の数を決めるとしても，その指標がわからないので10語で評価してみた 複雑な部品は10個では足らないはず 再現率は低いに違いない 再現率が高くなるような数は今後の課題 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 クエリ入力の問題点 意図したものが得られない 検索者が適切なクエリを入力する必要がある 検索されない 不要な情報の中に埋もれる
常に適切なクエリを知っているわけではない クエリ入力は，適切なクエリを検索者が知っていれば非常に強力な検索方法ですが， 問題点もあります． それは，適切なクエリを入力しないと，意図したものが検索されなかったり， 不要な情報によって意図していたものが埋もれてしまったりする， という点です． つまり，意図した検索結果を得ようとすれば，検索者が適切なクエリを入力 しなければいけない，ということになります． しかし，検索者は常に適切なクエリを知っているわけではありません． # 以降メモ 直感的なクエリは適切なクエリとは限らない → カテゴリ検索でもいえるのかどうか疑問 # ↓の話は言っていいものやら？ # 未知のものに対しても有効な検索ができる，と言いきれるほどのシステムじゃないし 特に，未知の分野に対する調べ物をしようとしているときは， 多くの適切でないクエリを入力してしまいがちです． 2005/02/24 平成16年度 特別研究報告

34 カテゴリ検索システム カテゴリ検索システムとは 利点 自然言語，Webページ検索などに用いられる あらかじめ用意されたカテゴリから文書を探す
カテゴリはツリー状に構成されていることが多い 文書は手動でカテゴリに分類されることが多い 利点 クエリを入力しなくてよい 段階的に絞り込むことができる コンピュータ → ソフトウェア → セキュリティ 一方，クエリを入力しない検索システムとして，（ソフトウェア部品検索ではなく） 自然言語やWeb検索などに用いられるカテゴリ検索システムがあります． カテゴリ検索システムとは，あらかじめ主に人の手で分類されたカテゴリの中から文書を探す，というシステムです． 用意されたカテゴリは，大抵はツリー状に構成されており，検索者は段階的に自分の意図するものにカテゴリを絞り込んでいけます． 例えば，ここにあるように，コンピュータからソフトウェア，ソフトウェアからセキュリティ， というような絞り込みができます． →次のスライドへの前振り では，このような利点があるカテゴリ検索を， ソフトウェア部品検索システムに適用するとどうなるかについて考えたいと思います． # 以降メモ 他の利点としては，文書中に出現する単語の中から検索する，全文検索のようなものと異なり， 文書中の単語に頼らない検索ができます 2005/02/24 平成16年度 特別研究報告

35 自然言語を対象とする手法の適用 2005/02/24 平成16年度 特別研究報告

36 SPARS-J ソフトウェア部品検索システム キーワード検索 パッケージ構造に従った検索 クエリを入力する必要がある
異なるパッケージ内のものを検索できない 利用関係がどうかは本題と関係ない クエリを入力 パッケージブラウザ サブパッケージ一覧 クラス一覧 2005/02/24 平成16年度 特別研究報告

37 分類の手順 解析 出現重み 計算 複合語 計算 利用関係 計算 LSA 計算 単語一覧 単語一覧 特徴語 決定 ソースコードを解析
(2) (1) (2.1) (2.2) (2.3) (2.4) 単語の 出現情報 解析 出現重み 計算 複合語 計算 利用関係 計算 LSA 計算 では，分類の流れについて説明したいと思います ↓クリック ソースコードを解析し，単語一覧の取得と単語の出現情報を取得します． 次に，単語の出現情報を用いて特徴語を決定するための重みである「単語重み」を求めます． 中で4つの手法を用いて，重みの計算をしていますが，後で説明するのでここでは省きます． 次に，部品ごとに単語を重みでソートし，それぞれ上位10個の語を特徴語と決定します． 最後に，特徴語をそれぞれ1つのカテゴリとして部品を分類します． 最終的には，部品とカテゴリの組が得られます． 重み 重み 重み 特徴語 重み (3) 単語一覧 単語一覧 特徴語 決定 ソースコードを解析 単語重み計算 出現重み計算 語の記法統一・複合語分割による重み再計算 利用関係による重み加算 LSA（潜在的意味解析法） 部品ごとに単語重みの高い上位10個の語を特徴語に 1つの特徴語をそれぞれ1つのカテゴリとして部品を分類 部品と特徴語の組 (4) カテゴリ 生成 部品と カテゴリの組 2005/02/24 平成16年度 特別研究報告

38 単語重み計算 ソースコードの出現場所による重み計算 語の記法統一・複合語分割による重み再計算 利用関係による重み加算
出現した場所（クラス定義など）を考慮した重要度 語の記法統一・複合語分割による重み再計算 XML_Parser→ Xml, Parser, XmlParser 利用関係による重み加算 利用している部品中の語の重みを加算する 例：継承，メソッド呼び出し，インスタンス化 LSA（潜在的意味解析法） 類似語を求める統計的手法 先ほど省略した特徴語を決定するときの重み計算の説明を行いたいと思います． まず，1番ですが，これは単語が出現した場所が クラス定義か，変数名かという情報を考慮した重要度の計算を行います． 次に2番ですが， ここでは，大文字小文字の使い方や，アンダースコアを挟む，挟まないなどの記法の統一と， 複数の語が組み合わさってできている語から，その一部あるいは全部で構成される語を切り出しを行います． 単語の一覧が処理前と変化するので，それにあわせた重みの再計算を行います． 次に，3番ですが， まず，利用関係とは，継承や・・・を指します． この計算は，利用している部品に存在する語の重みを，対象の部品の語の重みに加算します． これにより，差分しかかかれていない子クラスに親クラスの語の重みが加えられる，などの変化があります． 最後にLSAですが，これは統計的に類似する語を求めるために用いています． # 以降メモ 対象語の削減 分類に影響のない語を削除 最後にLSAですが，これは統計的な処理により，先ほどの「fileとreadに関係するinputの重みが高くなる」 というような変化が得られます． 2005/02/24 平成16年度 特別研究報告

39 適合率 検索結果がどれだけ正しいかを表す値 適合率 ＝ |検索結果 ∩ 適合文書| |検索結果| 検索結果 2005/02/24
平成16年度 特別研究報告

40 評価する値 カテゴリと部品の間の適合率を求める SPARS-J （全文検索)との検索結果の比較 適合率 ＝ 各カテゴリに属する部品の適合率
各部品が属するカテゴリの適合率 SPARS-J （全文検索)との検索結果の比較 SPARS-Jで検索されず本システムで検索されたものの中での適合率 SPARS-Jで検索されず本システムで上位10件以内の中での適合率 |検索結果 ∩ 適合文書| |検索結果| 適合率 ＝ 2005/02/24 平成16年度 特別研究報告

41 評価 実際に分類を行い，検索結果を評価する 適合率 ＝ 入力はRobocodeのロボット35体 カテゴリと部品の間の適合率を求める
各カテゴリに属する部品の適合率 各部品が属するカテゴリの適合率 SPARS-J （全文検索)との検索結果の比較 SPARS-Jで検索されず本システムで検索されたものの中での適合率 次に実際に分類を行い，検索結果を評価した結果について説明したいと思います． 入力はRobocodeのロボット35体としました． 検索結果の評価として，今回は適合率を用いました． 適合率は以下の式で与えられる，検索結果にどれだけ適合文書が含まれているかの割合です． 本発表では，カテゴリと部品間の適合率の双方向と， SPARS-Jと比較した時の適合率の3つの評価について述べたいと思います． # 以降メモ カテゴリ間の関係の評価 については省略 |検索結果 ∩ 適合文書| |検索結果| 適合率 ＝ 2005/02/24 平成16年度 特別研究報告

42 SPARS-Jとの比較 SPARS-Jで検索されず本システムで検索されたものの中での適合率(左)
avg SPARS-Jで検索されず本システムで上位10件以内の中での適合率(右) avg 検索結果がSPARSの検索 結果に含まれたカテゴリ 2005/02/24 平成16年度 特別研究報告

43 SPARS-Jとの比較 SPARS-Jで検索されず本システムで検索されたものの中での適合率 avg. 0.4933 本システム
本システムで検索される部分をこのオレンジの○ SPARS-Jで検索される部分をこの青の○として， この薄いオレンジで塗られている部分の中での適合率を求めました． 検索結果によっては，このように本システムでの検索結果が SPARS-Jによる検索結果に含まれる場合があります． この場合は適合率は計算できません． それが適合率がマイナスでかかれている，この赤枠の部分です． 適合率が0のカテゴリや，適合率が計算できないカテゴリが多くありました． 本システム SPARS-J この部分での適合率 検索結果がSPARS-Jの検索 結果に含まれたカテゴリの場合 適合率が計算できない 適合率が計算できない 2005/02/24 平成16年度 特別研究報告

44 カテゴリ間の関係の評価 (UNDONE) (適合率っぽい評価値を出す予定) 2005/02/24 平成16年度 特別研究報告

45 没の図 2005/02/24 平成16年度 特別研究報告

46 考察 カテゴリと部品の間では高い適合率が得られたのに対し，SPARS-Jとの比較では低い適合率となった
特徴語が部品につき10個固定なのが問題 10個では足りないような複雑な部品 高い適合率 特徴語のほとんどあるいは全てがソースコード中に出現するため，SPARS-Jで検索可能 10個では多すぎるような単純な部品 低い適合率 無関係な特徴語が幾つも含まれる 適合率の平均は高いが，属する部品の適合率が0のカテゴリが存在する 特徴語として適さないが重みが高い特徴語がある ごちゃごちゃしすぎ 10固定なのが問題 2005/02/24 平成16年度 特別研究報告

47 没アニメーション 2005/02/24 平成16年度 特別研究報告

48 背景 ソフトウェア開発の大規模化・複雑化 様々なソフトウェア部品検索システム ソフトウェア部品検索システムの必要性
生成されたソフトウェアを再利用したり，管理する機会が増えた 様々なソフトウェア部品検索システム 多くがクエリとの適合度の高い部品を表示 クエリを入力する必要がある ソフトウェア部品検索システムの必要性 2005/02/24 平成16年度 特別研究報告

49 カテゴリ検索システム ただし分類の手間が必要 カテゴリ検索システムとは 利点 自然言語，Webページ検索などに用いられる
あらかじめ用意されたカテゴリから文書を探す カテゴリはツリー状に構成されていることが多い 利点 段階的に絞り込むことができる 文書中に含まれない単語による検索ができる クエリ（検索語）を入力しなくてよい 一方，ソフトウェア部品検索ではなく 自然言語やWeb検索などに用いられる検索システムとして カテゴリ検索システムがあります． カテゴリ検索システムとは・・・ ただし分類の手間が必要 2005/02/24 平成16年度 特別研究報告

50 研究の目的 カテゴリ検索用の分類を自動で行う カテゴリのツリー(カテゴリ間の関係)を自動作成 低コストでカテゴリ検索の利点が得られる
2005/02/24 平成16年度 特別研究報告