潜在的意味解析法LSA を利用した ソフトウェア分類システムの試作 大阪大学大学院基礎工学研究科 博士前期課程二年 川口 真司

発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06

ソフトウェアリポジトリ ソフトウェア開発資源(ソースコード、ドキュメントなど)の保管場所を提供 リポジトリには大量のソフトウェアが存在 SourceForge(http://sourceforge.net/) Corporate Source* リポジトリには大量のソフトウェアが存在 SourceForgeには55000以上ものソフトウェアが存在(2003/03現在) *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/03/06

背景 ソフトウェアリポジトリをソフトウェアの検索に利用 分類・整理が不可欠 リポジトリ内にあるソフトウェアは手動で分類 機能要求を満たすソフトウェアを検索 現在作成中のソフトウェアに似ているソフトウェアを検索 分類・整理が不可欠 リポジトリ内にあるソフトウェアは手動で分類 リポジトリ管理者が, 階層構造を作成 分類者が, 定義された階層から, そのソフトウェアにふさわしい分類を選択 2003/03/06

問題点 画一的で排他的な分類 ソフトウェアには様々な側面 階層構造の作成には多大なコストがかかる リポジトリ管理者の負担:大 一般にはソフトウェアの用途によって分類 しかし、利用しているライブラリや依存アーキテクチャによる分類もまた有用 ソフトウェアには様々な側面 階層構造の作成には多大なコストがかかる 階層構造の作成には、さまざまなライブラリ・アーキテクチャに関する深い知識が必要 リポジトリ管理者の負担:大 単一のビューのみを提供 断定的すぎる ソフトウェアの持つ多様性を無視している ソフトウェアの特性を歪めている 2003/03/06

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

目的 ソフトウェアの自動分類 ソフトウェアが持つさまざまな側面を考慮した非排他的分類 依存ライブラリや前提とするアーキテクチャを自動的に判別し分類する 分類対象となるソフトウェアに対する 深い知識を必要としない 2003/03/06

発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06

潜在的意味解析法 LSA Latent Semantic Analysis* 自然言語で書かれた文書、単語の類似度を計測する ベクトル空間モデルに従った手法の一つ ベクトル空間モデルでは検出できない間接的な関連の抽出を可能にしている * Landauer, T. K., Foltz, P. W., & Laham, D. (1998). Introduction to Latent Semantic Analysis. 　Discourse Processes, 25, 259-284. 2003/03/06

LSA の例 単語ベクトル 文書ベクトル 文書間、単語間の類似度は ベクトル間の角度の cos に よって表す 文書1 文書4 文書2 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/03/06

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/03/06

発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06

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

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

発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06

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

提案手法(1/2) Sof1 Soft4 Soft1 Soft4 Soft2 Soft5 Soft2 Soft5 Soft3 Soft6 A B B F J G G I J Soft2 Soft5 Soft2 Soft5 1.トークン 抽出 A B C D E F G H H J Soft3 Soft6 Soft3 Soft6 B C C C D E G H J 2.共起行列の作成 1 2 3 4 5 6 A B C D E F G H I J 1 2 3 4 5 6 A B C D E F G H 3.孤立トークン, 普遍トークンの 削除 2003/03/06

提案手法(2/2) 4.LSA 5.トークン間の類似度計測、 クラスタ分析 ClusterName1 7.クラスタ 6.ソフトウェア 3 4 5 6 A B C D E F G H 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 4.LSA 5.トークン間の類似度計測、 クラスタ分析 1 2 3 1 2 3 A B C D ClusterName1 F G H 7.クラスタ タイトルの 作成 6.ソフトウェア クラスタの 作成 1 4 5 6 1 4 5 6 ClusterName2 2003/03/06

1.トークン抽出 トークン 各ソフトウェアから識別子を抽出し、これをトークンとする 各ソフトウェアを特徴づける単語の集合 Sof1 Soft4 Soft1 Soft4 A B B F J G G I J Soft2 Soft5 Soft2 Soft5 1.トークン 抽出 A B C D E F G H H J Soft3 Soft6 Soft3 Soft6 B C C C D E G H J 2003/03/06

2.共起行列の作成 共起行列 行にソフトウェア、列にトークンをとり、行列の値に各ソフトウェアでのトークン出現数が入った行列 Sof1 Soft4 1 2 3 4 5 6 A B C D E F G H I J A B B F J G G I J Soft2 Soft5 A B C D E F G H H J 2.共起行列の 作成 Soft3 Soft6 B C C C D E G H J 2003/03/06

3.孤立トークン、普遍トークンの削除 孤立トークン 普遍トークン これらのトークンは分類に役立たないため削除 ある単一のソフトウェアのみに現れるトークン 普遍トークン 半数以上のソフトウェアに現れるトークン これらのトークンは分類に役立たないため削除 1 2 3 4 5 6 A B C D E F G H I J 1 2 3 4 5 6 A B C D E F G H 3.孤立トークン, 普遍トークンの 削除 2003/03/06

4.LSA 孤立トークン、普遍トークンを除いた共起行列に対して LSA を適用 1 2 3 4 5 6 A B C D E F G H 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 4.LSA 2003/03/06

5.識別子をクラスタリング 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 5.識別子を クラスタリング A B C D F G H 2003/03/06

6.ソフトウェアクラスタの作成 各トークンクラスタごとに対応するソフトウェアクラスタを作成 トークンクラスタ内のクラスタを持っているソフトウェアの集合 Sof1 Soft4 A B B F J G G I J A B C D F G H Soft2 Soft5 6.ソフトウェアクラスタの 作成 A B C D E F G H H J Soft3 Soft6 1 2 3 1 4 5 6 B C C C D E G H J 2003/03/06

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

自動分類システム 対象: C言語で記述されたプログラム群 各ステップごとに、対応するプログラムを作成 実装言語 Perl 全部で約4000行 LSA の計算部には SVDPACKC を利用 全部で約4000行 2003/03/06

発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06

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

分類システム出力結果（一部） 新しい分類 構文解析ライブラリ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/03/06

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

考察 ライブラリやアーキテクチャによる分類を前提知識なしで発見 クラスタタイトル ソフトウェアのさまざまな側面に対応した分類 前提知識がなくとも分類が可能 クラスタタイトル 分かりやすいものもあれば、分かりにくいものもある 同じライブラリを利用しているクラスタは、比較的分かりやすいタイトルがつく傾向がある 2003/03/06

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

終 2003/03/06

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

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

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

関連研究 ある単一のソフトウェアを分割し, それらを意味のあるまとまりに再構成する試みがなされている ソフトウェアをある種の単位に分割 ファイル, 関数 それらの単位間での類似度を算出し, 類似度を元に再構成する ファイル名* 関数間の呼び出し関係(コールグラフ)** 利用している識別子*** *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/03/06

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

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