潜在的意味解析法LSAに基づく ソフトウェアシステム分類法の提案 井上研究室 川口 真司

背景 多数のソフトウェアを集積する「ソフトウェアリポジトリ」が幅広く利用されている リポジトリには大量のソフトウェアが存在 SourceForge(http://sourceforge.net/) Corporate Source* リポジトリには大量のソフトウェアが存在 SourceForgeには55000以上ものソフトウェアが存在(2003/02現在) 分類・整理することが必要不可欠 リポジトリ内にあるソフトウェアは手動で分類 リポジトリ管理者が, 階層構造を作成 分類者が, 定義された階層から, そのソフトウェアにふさわしい分類を選択 *Jamie Dinkelacker and Pankaj K. Garg Corporate Source: Applying Open Source Concepts to a Corporate Environment (Position Paper) 1st ICSE International Workshop on Open Source Software Engineering, May 15, 2001, Toronto, Canada. 2003/02/17 修士学位論文発表会

問題点 階層構造をもって排他的にソフトウェアを分類することは適切か ソフトウェアはさまざまな側面を持っている 一般にはソフトウェアの用途によって分類 しかし、利用しているライブラリや依存アーキテクチャによる分類もまた有用 　　　　　　　ソフトウェアはさまざまな側面を持っている 2003/02/17 修士学位論文発表会

非排他的分類 これらライブラリや アーキテクチャに対する 知識がなければ、 このような分類を準備 できない regexp エディタ 表計算 MFC GTK ソフトウェア1 ソフトウェア3 これらライブラリや アーキテクチャに対する 知識がなければ、 このような分類を準備 できない エディタ 表計算 GUI (MFC) GUI (MFC) 正規表現サポート (regexp) 正規表現サポート (regexp) ソフトウェア2 ソフトウェア4 エディタ 表計算 GUI (GTK) GUI (GTK) 正規表現サポート (regexp) 2003/02/17 修士学位論文発表会

目的 ソフトウェアの自動分類 ソフトウェアが持つさまざまな側面を考慮した非排他的分類 依存ライブラリや前提とするアーキテクチャを自動的に判別し分類する ソースコードから自動的に分類 分類対象となるソフトウェアに対する深い知識が必要ない 2003/02/17 修士学位論文発表会

潜在的意味解析法 LSA Latent Semantic Analysis 自然言語で書かれた文書、単語の類似度を計測する ベクトル空間モデルに従った手法の一つ ベクトル空間モデルでは検出できない間接的な関連の抽出を可能にしている 2003/02/17 修士学位論文発表会

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 2003/02/17 修士学位論文発表会

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適用後 2003/02/17 修士学位論文発表会

LSAによるソフトウェア類似度測定 ソフトウェアに対して LSA を適用 LSAを適用した結果からソフトウェアの類似度を測定 文書 ⇒ ソフトウェア 単語 ⇒ 識別子（変数名、関数名、型名） LSAを適用した結果からソフトウェアの類似度を測定 測定した類似度からクラスタ分析ができるのでは クラスタ分析・・・類似度の高いもの同士をグループ化する手法 2003/02/17 修士学位論文発表会

ソフトウェア類似度の傾向 類似度を手がかりに分類を行っても適正な分類が得られない 類似度が高い理由がソフトウェアによって異なる ソフトウェア1 ソフトウェア3 エディタ 表計算 GUI (MFC) GUI (MFC) 正規表現サポート (regexp) 正規表現サポート (regexp) ソフトウェア2 ソフトウェア4 エディタ 表計算 GUI (GTK) GUI (GTK) 正規表現サポート (regexp) 2003/02/17 修士学位論文発表会

識別子による分類 ソースコード中の識別子は、その動作を表している window という識別子があるプログラム文の周辺は、なんらかの GUI に関する操作を行っている 識別子のうち特に類似しているものを結びつけて、それらをひとつのグループとみなして分類を行う ソフトウェア1 ソフトウェア3 エディタ 表計算 GUI (MFC) GUI (MFC) window menuBar cmdButton window MFC 2003/02/17 修士学位論文発表会

提案手法 Sof1 Soft4 Soft2 Soft5 Soft3 Soft6 1.識別子を クラスタリング 2.ソフトウェアクラスタの作成 A B B F G G A B C D F G H Soft2 Soft5 A B C D E F G H H 2.ソフトウェアクラスタの作成 Soft3 Soft6 B C C C D E G H 1 2 3 1 4 5 6 3.クラスタタイトルの作成 1 2 3 1 4 5 6 ClusterName1 ClusterName2 2003/02/17 修士学位論文発表会

1.識別子をクラスタリング LSA の結果を元に識別子間の類似度計測 類似度を利用してクラスタ分析 得られたクラスタを「トークンクラスタ」と呼ぶ Sof1 Soft4 A B B F G G 1.識別子を クラスタリング Soft2 Soft5 A B C D E F G H H A B C D F G H Soft3 Soft6 B C C C D E G H 2003/02/17 修士学位論文発表会

2.ソフトウェアクラスタの作成 各トークンクラスタごとに対応するソフトウェアクラスタを作成 トークンクラスタ内のクラスタを持っているソフトウェアの集合 Sof1 Soft4 A B B F G G A B C D F G H Soft2 Soft5 2.ソフトウェアクラスタの 作成 A B C D E F G H H Soft3 Soft6 1 2 3 1 4 5 6 B C C C D E G H 2003/02/17 修士学位論文発表会

3.クラスタタイトルの作成 クラスタを短く表現するタイトルを作成する LSA を行った後の行列からソフトウェアベクトルを取得 クラスタに含まれるソフトウェアベクトルを合計する そのベクトルの中で値の大きい部分に対応するトークンを数個選び出し、これをタイトルとする 3.クラスタタイトルの作成 1 2 3 1 4 5 6 1 2 3 1 4 5 6 ClusterName1 ClusterName2 2003/02/17 修士学位論文発表会

実験 提案手法でどのような分類が抽出できるのかを実験 分類対象 提案手法を実現するシステムを実装 分類対象として C 言語で記述されたソフトウェアに対応 分類対象 SourceForge から無作為に 6 つのジャンルを選択 　boardgames, compilers, database, editor, videoconversion, xterm その中から C 言語で書かれたプログラムをテストデータとして選択 全部で 41 個のソフトウェア 合計 164102個の識別子が存在 そのうち単一のソフトウェアにのみ現れるトークンを除いた残り 22048 個を利用 2003/02/17 修士学位論文発表会

分類システム出力結果（一部） 新しい分類 構文解析ライブラリyaccを利用しているソフトウェアの集合 タイトル ソフトウェア クラスタ数 AOP, emitcode, IC_RESULT, IC_LEFT, aop, aopGet, IC_RIGHT, pic14_emitcode, iCode, etype compilers/gbdk, compilers/sdcc 8597 CASE_IGNORE, CASE_GROUND_STATE, screen, CASE_PRINT, CASE_BYP_STATE, Widget, TScreen, CASE_IGNORE_STATE, CASE_PLT_VEC, CASE_PT_POINT xterm/R6.3, xterm/R6.4 2160 YY_BREAK, yyvsp, yyval, DATA, yy_current_buffer, tuple, yy_current_state, yy_c_buf_p, yy_cp, uint32 compilers/gbdk, database/mysql-3.23.49, database/postgresql-7.2.1 223 AVI, cinfo, OUTLONG, avi_t, AVI_errno, hdrl_data, OUT4CC, nhb, ERR_EXIT, str2ulong videoconversion/dv2jpg-1.1, videoconversion/libcu30-1.0, videoconversion/mjpgTools 177 board, num_moves, ply, pawn_file, npiece, pawns, moves, white_to_move, move_s, promoted boardgame/Sjeng-10.0, boardgame/cinag-1.1.4, boardgame/faile_1_4_4 154 GtkWidget, gchar, gpointer, gint, widget, gtk_widget_show, N_, g_free, dialog, g_return_if_fail boardgame/gbatnav-1.0.4, editor/gedit-1.120.0, editor/gmas-1.1.0, editor/gnotepad+-1.3.3, editor/peacock-0.4 104 既存の(SourceForgeの)分類と同じ分類 GTK ライブラリを利用しているソフトウェアの集合 構文解析ライブラリyaccを利用しているソフトウェアの集合 新しい分類 2003/02/17 修士学位論文発表会

実験結果 合計40個のクラスタ 新しい分類によるクラスタの内訳 新しいクラスタ 8 既存の分類と同一のクラスタ 18 GTK(2クラスタ) GUI ライブラリ yacc(2クラスタ) 構文解析ライブラリ regexp 正規表現解釈ライブラリ getopt 引数解釈用ライブラリ JNI Java のネイティブメソッドを実現するアーキテクチャ Python/C Python インタプリタ拡張アーキテクチャ 新しいクラスタ 8 既存の分類と同一のクラスタ 18 2003/02/17 修士学位論文発表会

考察 ライブラリやアーキテクチャによる分類を前提知識なしで発見 クラスタタイトル 分かりやすいものもあれば、分かりにくいものもある 同じライブラリを利用しているクラスタは、比較的分かりやすいタイトルがつく傾向がある 2003/02/17 修士学位論文発表会

まとめと今後の課題 ソフトウェアを自動分類する手法を提案した 本手法により、ソフトウェア集合やそこに含まれるライブラリについての知識がなくとも、新たな分類を発見できることを示した 今後の課題 クラスタタイトルのよりよい作成方法の考案 大規模な実験 2003/02/17 修士学位論文発表会

終 2003/02/17 修士学位論文発表会

考察 従来の分類では注目してない観点では 従来の分類という観点からは クラスタタイトル ライブラリによる新しい分類を発見 前提知識なしで発見することができた 従来の分類という観点からは 適合率は高い 再現率は低い クラスタタイトル 適切についているものもあるが、そうでないものもある ライブラリを抽出したクラスタはわかりやすい名前がつく傾向がある 2003/02/17 修士学位論文発表会

実験結果 40個のクラスタ トークン数上位 20 個のクラスタ 既存の分類に従うクラスタ 18 既存の分類とは異なる、新しいクラスタ 8 (GTK(2クラスタ), yacc(2クラスタ), regexp, JNI, getopt, Python/C) 8 その他 14 既存の分類に従うクラスタ 14 既存の分類とは異なる、新しいクラスタ (GTK(2クラスタ), yacc) 3 その他 2003/02/17 修士学位論文発表会

適合率・再現率 適合率(precision) 再現率(recall) 全クラスタ 上位20クラスタ 適合率 0.65 0.85 再現率 得られたクラスタのうち、正しい分類となっているクラスタの割合 再現率(recall) 想定される正しい分類が、得られたクラスタにどれだけ含まれているか ここでは、既存の分類のみを想定される正しい分類とする 全クラスタ 上位20クラスタ 適合率 0.65 0.85 再現率 0.16 0.13 2003/02/17 修士学位論文発表会

関連研究 ある単一のソフトウェアを分割し, それらを意味のあるまとまりに再構成する試みがなされている ソフトウェアをある種の単位に分割 ファイル, 関数 それらの単位間での類似度を算出し, 類似度を元に再構成する ファイル名* 関数間の呼び出し関係(コールグラフ)** 利用している識別子*** *N. Anquetil and T. Lethbridge. Extracting concepts from file names; a new file clustering criterion. In Proc. 20th Intl. Conf. Software Engineering, May 1998. **G. A.  Di Lucca, A. R.  Fasolino, F.  Pace, P.  Tramontana, U.  De Carlini, Comprehending Web Applications by a Clustering Based Approach 10th International Workshop on Program Comprehension (IWPC'02) ***Jonathan I. Maletic and Andrian Marcus, Supporting Program Comprehension Using Semantic and Structural Information in Proceedings of the 23rd IEEE International Conference on Software Engineering (ICSE 2001) 2003/02/17 修士学位論文発表会

既存の手法の問題点 単一のソフトウェアが対象 複数のソフトウェアを対象にした場合, これらの仮定が当てはまらない 区分の単位であるファイルや関数は、単一の機能のみ果たしていると仮定できる 呼び出し関係などの構造的情報が利用できる 複数のソフトウェアを対象にした場合, これらの仮定が当てはまらない ソフトウェアは単一の機能のみでは構成されていない 構造的情報を利用している手法は利用できない 2003/02/17 修士学位論文発表会

LSA (Latent Semantic Analysis)* 潜在的意味解析 自然言語で記述された文書・単語の類似度を計測する手法 ドキュメントを単語頻度表のベクトルであらわす 単語間の間接的関係を抽出できる * Landauer, T. K., Foltz, P. W., & Laham, D. (1998). Introduction to Latent Semantic Analysis. 　Discourse Processes, 25, 259-284. 2003/02/17 修士学位論文発表会