潜在的意味解析法LSA を利用した ソフトウェア分類システムの試作 大阪大学大学院基礎工学研究科 博士前期課程二年 川口 真司 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 2 ソフトウェアリポジトリ ソフトウェア開発資源(ソースコード、ドキュメントなど) の保管場所を提供 SourceForge(http://sourceforge.net/) Corporate Source* リポジトリには大量のソフトウェアが存在 SourceForgeには55000以上ものソフトウェアが存在 (2003/03現在) 2003/03/06 *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. Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3 背景 ソフトウェアリポジトリをソフトウェアの検索に利用 機能要求を満たすソフトウェアを検索 現在作成中のソフトウェアに似ているソフトウェアを検索 分類・整理が不可欠 リポジトリ内にあるソフトウェアは手動で分類 リポジトリ管理者が, 階層構造を作成 分類者が, 定義された階層から, そのソフトウェアにふさわ しい分類を選択 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 4 問題点 画一的で排他的な分類 一般にはソフトウェアの用途によって分類 しかし、利用しているライブラリや依存アーキテクチャによる 分類もまた有用 ソフトウェアには様々な側面 階層構造の作成には多大なコストがかかる 階層構造の作成には、さまざまなライブラリ・アーキテク チャに関する深い知識が必要 リポジトリ管理者の負担:大 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 5 非排他的分類 regexp エディタ 表計算 GUI (MFC) GUI (MFC) 正規表現サポート (regexp) 正規表現サポート (regexp) ソフトウェア3 ソフトウェア1 これらライブラリや アーキテクチャに対する エディタ 知識がなければ、 GUI (GTK) 正規表現サポート このような分類を準備 (regexp) できない ソフトウェア2 MFC 表計算 GUI (GTK) ソフトウェア4 GTK 2003/03/06 エディタ 表計算 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 6 目的 ソフトウェアの自動分類 ソフトウェアが持つさまざまな側面を考慮した非排他的分 類 依存ライブラリや前提とするアーキテクチャを自動的に判 別し分類する 分類対象となるソフトウェアに対する 深い知識を必要としない 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 7 発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 8 潜在的意味解析法 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 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 9 LSA の例 文書1 文書4 A B B F 文書2 B 文書ベクトル 文書5 A B C D E 文書3 G G F G H H 単語頻度行列を 文書間、単語間の類似度は 文書6 Cベクトル間の角度の C C D E G H cos作成 に よって表す 単語ベクトル 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 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 10 LSA の効果 間接的に関連している文書間の類似度も高い 文書間の類似度がより鮮明になる 文書間の類似度行列 1 2 3 4 5 6 1 2 3 4 5 6 1 1.0 0.2 -0.1 -0.3 -0.3 -0.5 1 1.0 1.0 0.9 -0.6 -0.6 -0.5 2 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適用前 LSA適用後 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 11 発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 12 LSAによるソフトウェア類似度測定 ソフトウェアに対して LSA を適用 文書 ⇒ ソフトウェア 単語 ⇒ 識別子(変数名、関数名、型名) LSAを適用した結果からソフトウェアの類似度を測 定 測定した類似度からクラスタ分析ができるのでは クラスタ分析・・・類似度の高いもの同士をグループ化する 手法 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 13 ソフトウェア類似度の傾向 類似度を手がかりに分類を行っても適正な分類が得られな い 類似度が高い理由がソフトウェアによって異なる 2003/03/06 エディタ 表計算 GUI (MFC) GUI (MFC) 正規表現サポート (regexp) ソフトウェア1 正規表現サポート (regexp) ソフトウェア3 エディタ 表計算 GUI (GTK) GUI (GTK) 正規表現サポート (regexp) ソフトウェア2 ソフトウェア4 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 14 発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 15 識別子による分類 ソースコード中の識別子は、その動作を表している window という識別子があるプログラム文の周辺は、なんらかの GUI に関する操作を行っている 識別子のうち特に類似しているものを結びつけて、それらをひ とつのグループとみなして分類を行う エディタ window cmdButton 2003/03/06 表計算 menuBar window GUI (MFC) GUI (MFC) ソフトウェア1 ソフトウェア3 MFC Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 16 提案手法(1/2) Sof1 Soft1 Soft4 A B B F Soft2 Soft5 J Soft2 1.トークン 抽出 Soft3 Soft6 Soft4 G G J Soft5 A B C D E Soft3 I F G H H J Soft6 B C C C D E G H J 2.共起行列の作成 I J 0 0 1 0 0 0 0 0 0 0 0 2 0 0 1 0 1 0 A B C D E F G H A B C D E F G H 1 1 2 0 0 0 1 0 1 1 2 0 0 0 1 0 0 2 1 1 1 1 1 0 0 2 1 1 1 1 1 0 0 0 3 0 1 3 1 0 0 0 3 0 1 3 1 0 0 0 0 4 0 0 0 0 0 1 1 4 0 0 0 0 0 0 2 0 5 0 0 0 1 2 0 1 5 0 0 0 0 0 1 1 2 6 0 0 0 1 1 0 1 6 0 0 0 0 1 0 1 1 3.孤立トークン, 普遍トークンの 削除 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 17 提案手法(2/2) 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 4 0 0 0 0 0 0 5 0 0 0 0 0 6 0 0 0 0 1 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 0 3 0.6 1.5 2.3 1.0 0.4 0.2 -0.2 -0.2 2 0 4 0.1 0.1 -0.2 0.0 0.2 0.4 0.9 0.9 1 1 2 5 0.1 0.2 -0.2 0.0 0.4 0.6 1.5 1.4 0 1 1 6 0.1 0.2 -0.1 0.0 0.3 0.4 1.0 0.9 1 2 3 4.LSA 5.トークン間の類似度計測、 クラスタ分析 D A B C F G 1 H 2 3 ClusterName1 6.ソフトウェア クラスタの 作成 1 4 5 6 7.クラスタ タイトルの 作成 1 4 5 6 ClusterName2 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 18 1.トークン抽出 トークン 各ソフトウェアを特徴づける単語の集合 各ソフトウェアから識別子を抽出し、これをトークンと する Sof1 Soft1 Soft4 Soft2 Soft5 Soft3 Soft6 A B B F 1.トークン 抽出 Soft4 J Soft2 A B C D E Soft3 B C C C D G G I J Soft5 F G H H J Soft6 E G H J 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 19 2.共起行列の作成 共起行列 行にソフトウェア、列にトークンをとり、行列の値に各ソフト ウェアでのトークン出現数が入った行列 Sof1 Soft4 A B B F J Soft2 G G I J Soft5 A B C D E Soft3 F G H H 2.共起行列の 作成 Soft6 B C C C D E G H J J I J 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 1 1 0 0 1 1 2 0 1 0 1 0 1 1 0 1 A B C D E F G H 1 1 2 0 0 0 1 0 2 1 1 1 1 1 0 3 0 1 3 1 0 4 0 0 0 0 5 0 0 0 6 0 0 0 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 20 3.孤立トークン、普遍トークンの削除 孤立トークン ある単一のソフトウェアのみに現れるトークン 普遍トークン 半数以上のソフトウェアに現れるトークン これらのトークンは分類に役立たないため削除 I J 0 0 1 0 0 0 0 0 0 0 0 2 0 0 1 0 1 0 A B C D E F G H A B C D E F G H 1 1 2 0 0 0 1 0 1 1 2 0 0 0 1 0 0 2 1 1 1 1 1 0 0 2 1 1 1 1 1 0 0 0 3 0 1 3 1 0 0 0 3 0 1 3 1 0 0 0 0 4 0 0 0 0 0 1 1 4 0 0 0 0 0 0 2 0 5 0 0 0 1 2 0 1 5 0 0 0 0 0 1 1 2 6 0 0 0 1 1 0 1 6 0 0 0 0 1 0 1 1 3.孤立トークン, 普遍トークンの 削除 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 21 4.LSA 孤立トークン、普遍トークンを除いた共起行列に対 して LSA を適用 LSA を適用することにより、間接的関連しかもたな いトークン間も高い類似度を持つようになる 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 4 0 0 0 0 0 0 5 0 0 0 0 0 6 0 0 0 0 1 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 0 3 0.6 1.5 2.3 1.0 0.4 0.2 -0.2 -0.2 2 0 4 0.1 0.1 -0.2 0.0 0.2 0.4 0.9 0.9 1 1 2 5 0.1 0.2 -0.2 0.0 0.4 0.6 1.5 1.4 0 1 1 6 0.1 0.2 -0.1 0.0 0.3 0.4 1.0 0.9 4.LSA 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 22 5.識別子をクラスタリング 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 5.識別子を クラスタリング A B C D F G 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University H 23 6.ソフトウェアクラスタの作成 各トークンクラスタごとに対応するソフトウェアクラスタ を作成 トークンクラスタ内のクラスタを持っているソフトウェアの 集合 Sof1 Soft4 A B B F J Soft2 G G I J Soft5 A B C D E Soft3 F G H H Soft6 B C C C D E G H J D A B C F G H 6.ソフトウェアクラスタの 作成 J 1 2 3 1 4 5 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 6 24 7.クラスタタイトルの作成 クラスタを短く表現するタイトルを作成する 1. LSA を行った後の行列からソフトウェアベクトルを取得 2. クラスタに含まれるソフトウェアベクトルを合計する 3. そのベクトルの中で値の大きい部分に対応するトークンを 数個選び出し、これをタイトルとする 7.クラスタタイトルの作成 1 2 3 1 4 5 6 1 2 3 ClusterName1 1 4 5 6 ClusterName2 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 25 自動分類システム 対象: C言語で記述されたプログラム群 各ステップごとに、対応するプログラムを作成 実装言語 Perl ただしトークン抽出部は C で実装 LSA の計算部には SVDPACKC を利用 全部で約4000行 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 26 発表の流れ 背景・研究の目的 潜在的意味解析法 LSA について LSAの単純な応用とその問題点 提案手法 適用実験 考察・まとめ 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 27 実験 提案手法でどのような分類が抽出できるのかを実験 分類対象 SourceForge から無作為に 6 つのジャンルを選択 boardgames, compilers, database, editor, videoconversion, xterm その中から C 言語で書かれたプログラムをテストデータとして選択 全部で 41 個のソフトウェア 合計 164102個の識別子が存在 そのうち単一のソフトウェアにのみ現れるトークンを除いた残り 22048 個を利 用 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 28 分類システム出力結果(一部) タイトル AOP, emitcode, IC_RESULT, IC_LEFT, aop, aopGet, IC_RIGHT, pic14_emitcode, iCode, etype 新しい分類 ソフトウェア クラスタ数 compilers/gbdk, compilers/sdcc 8597 構文解析ライブラリyaccを利用し ているソフトウェアの集合 xterm/R6.3, xterm/R6.4 2160 CASE_IGNORE, CASE_GROUND_STATE, screen, CASE_PRINT, CASE_BYP_STATE, Widget, TScreen, CASE_IGNORE_STATE, CASE_PLT_VEC, CASE_PT_POINT 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 white_to_move, move_s, promoted boardgame/cinag-1.1.4, boardgame/faile_1_4_4 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 GTK ライブラリを利用してい boardgame/Sjeng-10.0, るソフトウェアの集合 board, num_moves, ply, pawn_file, npiece, pawns, moves, 既存の(SourceForgeの)分類と同じ分類 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 154 104 29 実験結果 合計40個のクラスタ 新しいクラスタ 既存の分類と同一のクラスタ 8 18 新しい分類によるクラスタの内訳 GTK(2クラスタ) yacc(2クラスタ) regexp getopt JNI Python/C GUI ライブラリ 構文解析ライブラリ 正規表現解釈ライブラリ 引数解釈用ライブラリ Java のネイティブメソッドを実現するアーキテクチャ Python インタプリタ拡張アーキテクチャ 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 30 考察 ライブラリやアーキテクチャによる分類を前提知識なし で発見 ソフトウェアのさまざまな側面に対応した分類 前提知識がなくとも分類が可能 クラスタタイトル 分かりやすいものもあれば、分かりにくいものもある 同じライブラリを利用しているクラスタは、比較的分かりや すいタイトルがつく傾向がある 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 31 まとめと今後の課題 ソフトウェアを自動分類する手法を提案した 本手法により、ソフトウェア集合やそこに含まれるライ ブラリについての知識がなくとも、新たな分類を発見 できることを示した 今後の課題 クラスタタイトルのよりよい作成方法の考案 大規模な実験 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 32 終 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 33 考察 従来の分類では注目してない観点では ライブラリによる新しい分類を発見 前提知識なしで発見することができた 従来の分類という観点からは 適合率は高い 再現率は低い クラスタタイトル 適切についているものもあるが、そうでないものもある ライブラリを抽出したクラスタはわかりやすい名前がつく傾 向がある 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 34 実験結果 40個のクラスタ 既存の分類に従うクラスタ 既存の分類とは異なる、新しいクラスタ 18 8 (GTK(2クラスタ), yacc(2クラスタ), regexp, JNI, getopt, Python/C) その他 14 トークン数上位 20 個のクラスタ 既存の分類に従うクラスタ 既存の分類とは異なる、新しいクラスタ 14 3 (GTK(2クラスタ), yacc) その他 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3 35 適合率・再現率 適合率(precision) 得られたクラスタのうち、正しい分類となっているクラスタの割合 再現率(recall) 想定される正しい分類が、得られたクラスタにどれだけ含まれている か ここでは、既存の分類のみを想定される正しい分類とする 適合率 再現率 全クラスタ 0.65 0.16 上位20クラスタ 0.85 0.13 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 36 関連研究 ある単一のソフトウェアを分割し, それらを意味のある まとまりに再構成する試みがなされている ソフトウェアをある種の単位に分割 ファイル, 関数 それらの単位間での類似度を算出し, 類似度を元に再 構成する ファイル名* 関数間の呼び出し関係(コールグラフ)** 利用している識別子*** *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 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 37 既存の手法の問題点 単一のソフトウェアが対象 区分の単位であるファイルや関数は、単一の機能のみ果 たしていると仮定できる 呼び出し関係などの構造的情報が利用できる 複数のソフトウェアを対象にした場合, これらの仮定 が当てはまらない ソフトウェアは単一の機能のみでは構成されていない 構造的情報を利用している手法は利用できない 2003/03/06 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 38 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 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 39
© Copyright 2025 ExpyDoc