形式概念解析を用いた密部分抽出京都大学情報学研究科山本章博
オープン・ソフトウェア共同開発におけるメーリングリストを用いたソースファイル間の関係の抽出Dinh et al.: Discovering the Structures of Open Source Programs from Their Developer Mailing Lists, 2009 ■複雑化してしまうオープン・ソフトウェアのソースファイルを管理▪仕様書,ソースファイル間の参照関係を用いない
ソース・ファイル1055 static void obj free  ((VALUE)); static void gc_mark_children(ptr, lev) VALUE ptr; int lev;
/// #include "ruby.b" #include "rubysig.h" #include "node.h" #include "env.h" #include "resh" #include <stdio.h> #include<set #ifdef HAVE SYS TIME H 821 #include <sys/time.h> fendif !#ifdef HAVE_SYS_RESOURCE_H #include <sys/resource.h> fondif
開発者メーリングリスト
Subject [ruby-dev 23871] Re: rational, complex and mathn From: Shin-ichiro HARA <sinara blade.nagaokaut.ac.jp> Date: Wed, 20 Feb 2003 12:43:29 +0900. Refe Subject, Lruby-dev 33820  Re: rational, complex and mathn From: Shin-ichiro HARA <sinara blade.nagaoka.ut.ac.jp> Date: Sun, 17 Feb 2008 13:00:53 +0900 References: 33815 33818 33819 In-reply-to: 33819. Tada >> Subject: [ruby-dev:12000] [PATCH] error message of File.symlink() From: OHSHIMA Ryunosuke <ryu jaist.ac.jp> Date: Fri, 12 Jan 2001 22:50:37 +0000 >> | adaw >>> n 2大島です。 File.symlink()で発生するエラーのメッセージが不適当だと思います。例えば、ファイル"new"が既に存在する状態で、 "old"へのシンボリックリンクを“new”として作成しようとすると、以下のようなエラーが発生します。中% ruby -v -e 'File.symlink("old", "new")' ruby 1.6.2 (2000-12-25) [mips-irix6.5] -e:1:in `symlink': File exists - "old" (Ermo::EEXIST) from -e:1 symlink(2)では、 "old"ではなく"new"が原因のエラーが大多数だと思われますので、少なくとも以下のように変更した方が良いと思います。
関係1 :モジュール名が件名に出現関係2 :モジュール名が本体のテキスト部分に出現関係3 :モジュール名が本体のコード部分に出現関係4 :モジュールの一部が本体に引用
ソースファイル
#xyz.h void read_input_html() while(temp<size){ process_data(&input_array); count++;メールSub:ファイルxyz.hの修正点... read_input_htmlはHTMLファイルを読み込む関数である. … ' #include "xyz.h"ファイルxyz.hを次のように修正しまた. l while(temp<size){ process_data(&input_array); count++;
ソースファイルとメールの間の参照関係を2部グラフで表現メール形式概念: 2部グラフの意味での極大閉グラフ
ソースファイルメール(d 1 dշ d3 d 4 (d 12コンテクスト表
形式概念:コンテキスト表において, 行と列の順序を適当に並べ替えたとき,極大になる矩形領域
形式概念間にも包摂関係がある◾ソースファイルが多いメールが少ない
表示
■参照関係の抽出■包摂関係(Hasse図)の枝刈り
証拠kが見つかった■サポート集合R sを求める◾ R s = {(d;,m;) ∈ D × M |ヨk. ek(d;,m;)=1} ■ R sをフィルタリングし, R*を求める◾ R* = {(di,m;)∈Rs  | conf(di,m;)>0} 。ここで, e, (d, , m, ) conf(d i ,m j ) = b+ ∑ a k dと関連証拠が見つかったモジュールの数
メールd」と関連する証拠証拠1 :モジュール名が件名に出現証拠2 :モジュール名が本体のテキスト部分に出現証拠3 :モジュール名が本体のコード部分に出現証拠4 :モジュールの一部が本体に引用パラメータの値(例):
(実際には実験データから推定される)関連性の信頼度: conf(d 1 , m 1 ) = b+ a 3 = − 6 conf(d 1 , m 2 ) = b+ − − + − 4 = 8 5 conf(d 1 ,m 3 ) = b+ − 1 + − 3 + − 4 24 conf(d 1 , m 4 ) = b+ − 3 6
[1] HOS:   Hyper Operating System [2] Namazu 日本語全文検索システム[3] Rubyプログラミング言語
•約20%のメールがいずれかのモジュールと関連性を持つメールとして抽出可能• Namazuの集合R sの約10%に注釈を付加した.回帰分析によるパラメータ推定結果: a₁=0.141, a₁=0.459, a₁=0.373, a₄=0.027, b= -0.033
Lattice before pruning Constraints: - The number of its possessed attributes ≥ σ - The number of its introduced attributes≥τ
Lattice during pruning (Extracted structure) Properties of PRUNIA: The representation of super-sub 1. concept order is persevered No redundant path 2.
(σ=30,τ=15) (σ=20.τ=8)

(σ=100.τ=20)

対象(object)と属性(attribute)の関係をコンテキスト表に表示したときの極大矩形領域
■グラフ理論の用語では2部グラフの完備部分グラフ
形式概念解析(Formal Concept Analysis) ■数学者Rudolf Willeが考案■その名の通り, "概念"の形式化(数学化) ■代数学におけるGalois対応を参考にしたといわれる■ Galois対応: 5次以上の代数方程式の解の公式が四則演算とn乗根だけを使って表現できないことを示す際に用いる概念■しかし形式概念では数の演算を一切使わない■それゆえ,様々な数学理論がこの枠に入る数理論理学,形式言語理論,...数学者向けの説明■ Ä binary relation R ⊂ O×A ■ f: 0 → A and g : A → O f(S) = { a∈A | (o, a) ∈ R for some o∈S } g(T) = { o∈O | (o, a) ∈ R for some o∈T } ■ Then both h(S) = g(f(S)) and k(T) = f(g(T)) are closure operators. ■ A pair of a closed set S in O and f(S) (T in A and g(T))  is called a formal concept.データマイニング,複雑系■データマイニング(バスケット分析)において形式概念は飽和アイテム集合とよばれている▪大量に生成される頻出アイテム集合の同値類■複雑系においてはChuシステムとよばれている形式概念解析の応用例(2)形式概念解析を用いたシソーラス拡張池田et al. :クラス分類問題における形式概念解析を用いた近傍決定手法, 2013シソーラス拡張: ■既存のシソーラスに登録されていない新たな単語をどの意味に登録するか？ ■一つの単語が複数の意味を持つ可能性がある
●語の意味的な辞書–語は意味ラベルに関連付けされている–意味ラベル間には意味関係が与えられる•自然言語文の意味解析に不可欠•登録語数が限られているため，拡張が必要日本語WordNet [http://http://nlpwww.nict.go.jp/wêêja
●語の意味的な辞書–語は意味ラベルに関連付けされ，意味ラベル間には意味関係が与えられる•マルチラベルデータ•自然言語文の意味解析に不可欠•登録語数に限界があるため，拡張が必要
•シソーラス(T, L, L)の未知語布∈Tに対してL(u)を決定1.語の特徴空間上で近傍NCTを決定2.近傍Nに含まれる既知語t∈TのラベルからL(u)を推定•シソーラスを教師データとするマルチラベル分類問題特徴空間
•自然言語処理においては，自然言語文から構文解析器などの利用により得られる情報が，語の特徴として用いられる–容易に多種多様(品詞,係り受け関係,格構造, N-グラム,頻度, . . . )かつ大量のデータ(0, A, A)を収集可能–精度向上や計算量削減のため，特徴選択が必要
•自然言語処理においては，自然言語文から構文解析器などの利用により得られる情報が，語の特徴として用いられる–容易に多種多様(品詞,係り受け関係,格構造, N-グラム,頻度, . . . )かつ大量のデータ(0, A, A)を収集可能–精度向上や計算量削減のため，特徴選択が必要
•自然言語処理においては，自然言語文から構文解析器などの利用により得られる情報が，語の特徴として用いられる–容易に多種多様(品詞,係り受け関係,格構造, N-グラム,頻度, . . . )かつ大量のデータ(0, A, A)を収集可能–精度向上や計算量削減のため，特徴選択が必要
•目的・用途に応じて多種多様なシソーラスが公開されている–シソーラス(T 1, L 1, L 1), (T 2, L 2, L 2), …が存在し, T i≠T i, L i≠L i, Lj±Lj •データ(O, A, A)に対して,複数のシソーラス(T1, L1, L1), (T2, L2, Հշ), …を拡張する必要がある–シソーラスそれぞれに対して複数の特徴選択が必要•拡張すべきシソーラスの数が増えれば，より多くの時間が必要
特徴選択示の, A 1 , A 1 )—
(T3, L3, L3)
1.データから，あらかじめ語の近傍の候補を複数用意2.拡張するシソーラスについて，未知語の近傍を候補から選択
1.データから，あらかじめ語の近傍の候補を複数用意•形式文脈K=(O, A, I)の概念束B(K) – γο: ο∈Οのオブジェクト概念({ο}╨, {ο}ґ)
1.データから，あらかじめ語の近傍の候補を複数用意–データから求められる形式概念の外延を近傍の候補とする2. 拡張するシソーラス(T, L, L)について，未知語uの近傍Nを候補から選択–形式概念cにスコアσ(c)を与え，最大のスコアを持ち，かつ外延の要素数が最大である形式概念の外延に含まれる既知語の集合を近傍とする- 0 if|Ex(c)∩T|=0, 1 if|Ex(c)∩T|=1, and σ(c)= where •形式文脈K=(O, A, I)の概念束B(K) oシソーラス拡張において，未知語が含まれる外延をそれぞれ未知語の近傍の候補とする
σ(c 2 )=(sim(0 1 , 0 2 )+sim(0 1 , 0 3 )+sim(0 1 , 0 5 )+sim(0 2 , 0 3 ) +sim(0 2 , 0 4 )+sim(0 2 , 0 5 )+sim(0 3 , 0 5 )+sim(0 4 , 05))/10 =(0.25+0+0.25+0+0.2+0+0.2+0.25+0.666…)/10 =0.181… ●スコアを用いた近傍の決定は暗黙的な特徴選択といえる
38
●実験用データ–シソーラス(T, L, L) •日本語WordNet (JWN), 分類語意表(BGH) –語のデータ(O, A, A) ●京都大学格フレームコーパス(KCF) •日本語N-グラム(N=4) (J4g) • KCF • J4g混合データ•評価方法–シソーラスとデータの組み合わせ(6種)について交差検定(10-fold)を行ない適合度(precision)と再現度(recall)を計測– k近傍法(k=1, 5, 10)と比較
39
●全ての実験においてk近傍法より良い結果が得られた
■形式概念解析は二元論■ 1個の情報源だけでなく，2個の情報源の関係をみる■形式概念解析の利用者の先輩が存在◾数学,複雑系,自然言語解析■形式概念解析は対象間の演算を仮定しない■演算を導入することでより深い解析が期待される■形式概念解析は情報圧縮の一種▪プライバシー保護への展望