モジュラリティを基準とした関係データに対する特徴選択

モジュラリティを基準とした関係データに対する特徴選択

A Feature Selection Method for Relational Data Based on

Modularity

紫藤 佑介

1∗

_{山本 章博}

2

_{小林 靖明}

2

_{久保山 哲二}

3

Yusuke Shido

1

Akihiro Yamamoto

2

Yasuaki Kobayashi

2

Tetsuji Kuboyama

3

1

_{京都大学工学部情報学科}

1

_{School of Informatics and Mathematical Science, Faculty of Engineering, Kyoto University}

2

_{京都大学大学院情報学研究科}

2

_{Graduate School of Informatics, Kyoto University}

3

_{学習院大学 計算機センター}

3

_{Computer Center, Gakushuin University}

Abstract: In this work, we propose a feature selection method for unsupervised relational data based on modularity, which is a measure for evaluating the quality of splitting of graphs, and conduct an evaluation experiment on the feature set obtained by this method. In the method proposed in this work, features are selected with the aim at not eliminating the unity of instances. This method aims at high speed feature selection by assigning ranking to features and works in polynomial time. By the proposed method, we can shorten the time required for clustering almost without changing purity.

1

はじめに

特徴選択は教師あり学習であるクラス分類問題にお いて，頑健で汎化性能の高い学習モデルを構築するた めに重要な役割を果たす処理である．しかし教師なし 学習においても特徴選択を行うことで学習の高速化な どの利得を得ることが出来る．本稿では，コンピュー タネットワークやソーシャルネットワークなどのネット ワークやグラフに対して質の評価とクラスタリングを 行うための指標であるモジュラリティ(modularity)[4] を利用し，代表的な教師なし学習であるクラスタリン グの高速化を目的として特徴選択を行う． 現在に至るまで，教師あり学習のための特徴選択ア ルゴリズムには様々な手法が提案されているが，これ らはフィルター (filter)，ラッパー (wrapper)，埋め込 み (embedded) の 3 種類の方針から成ると考えること ができる [3]．フィルターは各インスタンスの特徴と教 師ラベルから計算できる基準を設定し，その基準を基 に特徴にスコアを与え，このスコアが上位の特徴を選 択するという方針である．ラッパーは識別能力の評価 を特徴集合に対して与えるもので，特徴が多いときに ∗_{連絡先： 京都市左京区吉田本町京都大学情報学研究科知能情報} 学専攻山本研究室 〒 606-8501 京都市左京区吉田本町 36-1 E-mail: [email protected] はうまく戦略を取らなければ組み合わせの数が膨大と なってしまう．埋め込みはクラス分類の学習モデルによ り固有の方法でクラス分類のルールを発見すると同時 に特徴を選択していく方針である．ランダムフォレス トや CART 法等による決定木の生成がこれにあたる． 本稿において提案する手法はこの 3 つの方針のうち フィルターに分類される．一般的に特徴そのものに評 価を与えランキングを付ける手法は，特徴の組み合わ せを考慮する必要が無く，計算を特徴数の多項式時間 で行うことができるため高速である．通常このように 特徴に評価を与えるための指標には教師ラベルとの相 関や相互情報量が用いられる [6][7]．しかし当然ではあ るがこれらの指標は教師ラベルが存在しない教師なし データに対して適用することはできない．そこで本稿 では教師なしデータに対しても与えることができるモ ジュラリティに基づいた特徴の重要度を示す指標を提 案する．この指標により特徴に順位を付けることで，関 係データの情報量が損なわれないような特徴の部分集 合を求める手法を提案し，実装と実験を行う．実験で は，提案する手法により選択した特徴のみを用いてク ラスタリングを行い，性能を落とすこと無く高速化が 行えることを示す． 本稿で提案する手法は，教師なし関係データに対し クラスタリングの結果が変化しないように次のように 人工知能学会研究会資料 SIG-FPAI-B506-17

特徴選択を行う．まず特徴選択を行いたいデータをグ ラフで表現する．各インスタンスを頂点とし，これら の頂点間に対応するインスタンス同士の類似度を重み として枝を張ることでこれを実現する．本稿では実験 においてこの類似度にコサイン類似度を用いた．次に， 全特徴についてその特徴がどれだけデータの中で重要 であるのかを示す値を与える．ここでこの値を，特徴 が持つ頂点を全て同じクラスターとしたときに増加す るモジュラリティとする．最後に，この値が上位の特 徴を選択する．このようにまとまり具合を示す指標で あるモジュラリティを利用して特徴を選択することで， より少ない特徴数でもともとのデータに存在するまと まりを表現することが可能であるため，クラスタリン グを行う際に有用に働く． 本稿は以下のように構成される．第 2 節において，提 案する手法で使用するモジュラリティについての導入 を行う．第 3 節において，提案する特徴選択の手法に ついて述べる．第 4 節で提案する手法を実データに適 用し，その前後でクラスタリングの性能や学習速度が どのように変化したかを確認する．最後に，第 5 節で 本稿のまとめを行う．

2

モジュラリティ

本節では，グラフに対するクラスタリングの質を評 価する指標であるモジュラリティ(modularity)[4] とそ の増分の計算について述べる． モジュラリティはソーシャルネットワークからコミュ ニティを検出する目的で提案された指標であり，各頂 点にクラスラベルが付けられたグラフに対して与える ことのできる値である．頂点集合が Nc個の互いに素 なクラスター g1, g2, . . . , gNcに分けられた枝の本数 M ， 隣接行列が A で表されるグラフに対して，モジュラリ ティ Q は (1) のように与えることができる． Q = Nc ∑ i (eii− ( ∑ j eij)2) = Nc ∑ i (eii− a2i) (1) ここで eij, aiはそれぞれ (2),(3) で与えられる． eij = ∑ r∈gi ∑ s∈gj Ars 2M (2) ai = ∑ j eij (3) このとき eii, eij, aiはそれぞれ，クラスター i の内部 に伸びる手の総数，クラスター i のノードとクラスター j のノード間に伸びる手の総数，クラスター i に含まれ るノードが持つ手の総数の，グラフ全体が持つ手の総 数に対する割合を表している．また，手とは頂点間の 枝を切断したときに 2 頂点に残るもので，頂点間の手 が結ばれることによって枝になる． 図 1 は同じグラフに対してクラスター数 2 の異なる 2 種類のクラスタリングを行った様子である．クラス タリング (A) よりもクラスタリング (B) の方がクラス ター内部に密な枝を持ち，クラスター間に渡る枝が少 なく，グラフとクラスターが含む頂点の数は同じであ るがクラスタリング (B) の方が高いモジュラリティ Q を持つ． 図 1: 同じグラフに異なるモジュラリティを持つような 2 種類のクラスタリングを行った例．QA=10₃₆− (₁₆ 36 )2 + 10 36− (₁₆ 36 )2 ≃ 0.16，QB= 16₃₆− (₁₈ 36 )2 +16₃₆−(18₃₆)2≃ 0.39 となり B の方が A よりも高いモジュラリティを 持つ． モジュラリティが最大となるようなクラスタリングの 厳密解を求める問題は NP 困難であることが知られて おり [2]，近似解を求める手法が用いられる．Newman アルゴリズム [5] は全頂点が個々に別々のクラスターで ある状態から，クラスターと別のクラスターを併合し ていく貪欲法であり，併合するクラスターを選択する 基準に，モジュラリティの増分を用いる．モジュラリ ティの増分とは，あるクラスタリングとそのクラスタ リングに含まれるふたつのクラスタを併合することで 得られるクラスタリングに対して，その併合前と併合 後のモジュラリティの差 ∆Q を指す． クラスター i とクラスター j を併合した時，増加す るクラスター内部の手はクラスター i のノードとクラ スター j のノード間に伸びる手であり，増加するモジュ ラリティは eij+ eji= 2eijで表される．このとき，ク ラスター外部への手の割合は変化しないが，ランダム に枝を張ったときにクラスター i の内部に伸びる手の

割合の期待値は a2 i で表されるため，減少するモジュラ リティは (ai+ aj)2− (ai2+ a2j) = 2aiajで表される． 以上より，クラスター i とクラスター j を併合したと きの ∆Qijは次の (4) で計算できる． ∆Qij = eij+ eji− 2aiaj= 2(eij− aiaj) (4) このように，グラフ全体のモジュラリティを再計算 することなく，併合するクラスターに含まれる頂点の 枝数のみを考えることで，任意の 2 つのクラスターを 追加した際に増加するモジュラリティを計算する事が できるため，頂点の数を n，枝の本数を m とするとき， 1 回の併合にかかる計算量は O(n + m) となる．した がって，Newman アルゴリズムに必要な計算量は全体 で O((n + m)n) となり，多項式時間で動作する．図 2 は個々に別々のノードからなるクラスターである状態 から，隣接する 2 つの頂点を選択し，その 2 つの頂点を 1 つのクラスターとした ∆Q が異なる 2 つの例である． 図 2: (A)，(B) それぞれの ∆Q を求めると ∆QA = 2(₁₆2 −₁₆3 ·₁₆3)≃ 0.18, ∆QB= 2(₁₆2 −₁₆3 ·₁₆1)≃ 0.23 となり，(A) より (B) のようにクラスターを併合した 方がモジュラリティの増分が大きいことが分かる． 本研究において提案する手法は，Newman アルゴリ ズムで使用されるモジュラリティの増分 ∆Q から着想 を得ており，モジュラリティの増分という考え方は特 徴へランキングを与える際そのためのスコア計算にお いて重要な役割を果たす．

3

モジュラリティに基づく関係デー

タに対する特徴選択

本節では，関係データに対してモジュラリティに基 いて特徴選択を行う方法について述べる．1 節に述べた ように，本研究において提案する手法は，特徴同士の 相互作用を考慮した，モジュラリティ(modularity) に 基づいた特徴選択手法である．具体的手順を示す． 1. 各インスタンスを頂点とし，同じ特徴を持つイン スタンス間に枝を張ることでデータをグラフで表 現する． 2. 各頂点を単一のノードからなるクラスターとした 状態から，各特徴に，その特徴を持つインスタン スを同じクラスターとした時のモジュラリティの 増分をスコアとして与える． 3. スコアが上位の特徴を選択する． 本節では，この手順に沿いその詳細について述べる．

3.1

データのグラフ表現

本節では関係データに対しモジュラリティの概念を 適用できるようにするためにデータをグラフで表現す る方法について述べる． 目的のグラフは，インスタンスを頂点とし，似てい る頂点間に枝を張ったグラフである．重み付きグラフ においてもモジュラリティを考えることが可能である ため [1]，この枝にどの程度インスタンスが似ているか という値を重みとして与える．本稿においては，この 指標としてコサイン類似度を重みとして与えるが，他 の距離関数を適用することも可能である． インスタンス i を表すベクトルを I(i)_{とすると，目} 的のグラフを表現する隣接行列 A は (8) で表される． 目的の隣接行列において自己ループが不要であるため 対角成分を全て 0 にする必要がある． I(i)_j = {

1 if instance i has feature j, 0 otherwise. (5) D = ( I(1) |I(1)_| I(2) |I(2)_| · · · I(NI) |I(NI)| )T (6) A′ = DDT (7) A = A′◦    0

1

. ._.

1

0    (8)

3.2

特徴へのスコアの付与

本節では特徴へ付与するスコアとその計算方法につ いて述べる．先述したとおり本研究では特徴 i のスコア を，個々のインスタンスそれぞれが単独のクラスター を形成する状態から，特徴 i を持つインスタンスをま

とめて 1 つのクラスターとしたときのモジュラリティ の増分をスコアとする． 第 2 節では 2 つのクラスターを併合したときに上昇 するモジュラリティについて述べた．(4) は任意の状態 から 2 つのクラスターを併合した場合のモジュラリティ の変化を表しているが，ある特徴を持つインスタンス は 3 つ以上である場合がある．∆Q を計算する前の状態 が初期状態，つまりインスタンス数 Ni個の単一ノード からなるクラスターが存在する状態であるならば，特 徴 Fkを持つノードの集合 gkを 1 つのクラスターとし た時に上昇するモジュラリティ∆Qkは次のように計算 できる． ∆Qk= ∑ i∈gk ∑ j∈gk eij−     ∑ i∈gk ai   2 −∑ i∈gk a2_i    (9) クラスター内に伸びる手については，クラスターを 併合する前には存在しないため考慮すべき増分 ∑ i_∈gk ∑ j_∈gkeijを考えればよい．これは (8) の隣接行 列 A と (10) で定義される F(k)_{を用いて，(12) のよう} に計算できる．ここで∑ ∑B とは行列 B の成分の総 和を表す．t_F(k) F(k)は NI× NIの行列であり，i 番目 のインスタンス Ii と j 番目のインスタンス Ijが両方 特徴 k を持つ場合に i 行 j 列の成分が 1 となり，それ 以外は 0 である行列である．この NI× NI行列と A の アダマール積を計算することで∑_i∈g k ∑ j∈gkeij が計 算できる． また，隣接行列が重み付きであることから，新たに M を枝数の総和の 2 倍から，枝の重みの総和の 2 倍 (11) と定義する．次に，クラスターに属するノードが持つ 手の総和であるが，これはインスタンスに固有の値で ある aiが (13) のように計算できる． F(k)_j = { 1 (j∈ gk) 0 otherwise (10) M = 1 2 ∑ r ∑ s Ars (11) ∑ i∈gk ∑ j∈gk eij = ∑ ∑ A ◦ t_F(k) F(k) 2M (12) ai = ∑ j Aij (13)

3.3

計算量について

本節では，前節までに述べた特徴にランキングを与 える過程において必要な計算量について述べる． まずデータをグラフで表現する際に，(7) における NI×NF行列と NF×NI行列の計算に O(NI2NF)，(8) におけるアダマール積に全要素を走査するため O(N2 I) の計算量がかかる． 各特徴についてスコアを与える際には，特徴 1 つにつ いてスコア ∆Q を計算するために (9) を計算する必要 がある．(12) は，特徴を持つインスタンス同士の枝を列 挙するための NI× NI行列tF(k)F(k)の計算に O(NI2) 必要で，アダマール積も同様に O(N2 I) 必要である．ま た，ai = ∑ jAijについては各インスタンスに O(NI) 必要で全インスタンスに O(N2 I) かかり，一度計算する ことで(∑_i∈g kai )2 −∑i∈gka 2 i は O(NI) で計算でき る．以上より特徴 1 つについて O(N2 I) の計算量が必要 となる．したがって，全ての特徴にスコアを与えるの に O(N2 INF) の計算量が必要となる． 以上より，本研究で提案する特徴選択手法の計算量 は O(N2 INF) となる．これは階層的クラスタリング法 のひとつである最近隣法にかかる計算量と同等であり， 代表的な非階層型クラスタリングアルゴリズムである k 平均法が定数回で収束したと過程した時にかかる計 算量 O(kNINF) に比べると低速であるが，特徴間での 相互作用を考慮しているにもかかわらず NFについて 線形時間で計算できる．このことを利用して NIよりも 少ないインスタンスで元のインスタンス数の時と近い グラフが表されるならば，インスタンスをランダムに サンプリングすることで近い結果をより少ない計算量 で計算することが可能になる．例えば元の NI個のイ ンスタンスのうち，ランダムに選んだ NI′ = √ NI個の インスタンスのみを用いてこのアルゴリズムを適用す れば，計算量は O(NINF) となる．第 4 節ではこのよ うにサンプリングを行った場合についても実験を行う．

4

実験

本節では前節で述べた特徴選択アルゴリズムを実際 のデータに対して適用し，選択された特徴が代表的な 教師なし学習であるクラスタリングに有用であること を実験的に示す．

4.1

準備

本節では選択した特徴を用いて代表的な教師なし学 習であるクラスタリングを行った際の評価についてと， 実験に使用するデータセットについて述べる．本研究 における実験は全て，3.7GHz で動作する Quad-core Xeon E5 と 12GB のメモリを搭載する Mac Pro を用 いて，シングルスレッドで行う．

特徴を選択したことで選択後の処理においてメモリ 量，計算量が減少することに加え，本研究では選択し た特徴集合がどの位良いかを評価する方法の 1 つとし

て，選択した特徴集合のみを用いて教師ラベルを隠し たクラスタリングを行った際の純度 (purity) を用いる． 純度はクラスター内に含まれる教師ラベルの内，最も クラスター内に多くのインスタンス数を持つものの割 合の重み付き和で，(14) で与えられる． purity =∑ i |Ci| NI max j P (i, j) (14) ここで P (i, j) はクラスター i に占める教師ラベル j のインスタンスの割合を指す．クラスタリングには python のパッケージ sklearn.cluster.KMeans1_を利用 し，初期中心点の決定に kmeans++法を用いる． 本節ではライブドアニュースコーパスス2_に含まれ る 9 種類の記事のうち，「MOVIE ENTER」(映画記 事)「Sports Watch」(スポーツ記事) を使用し，実験を 行った． データセットは JUMAN3_{により形態素解析を行い，} 得られた単語を特徴量とする．本研究では情報量が小 さい特徴が自動的に選択されないことを期待するため， 形態素解析を行う際にストップワードは用いていない． また，名詞の他に形容詞，動詞などについても同様に 特徴量としている．

図 3: MOVIE ENTER，Sports Watch．各 400 インス タンス，14919 特徴

4.2

特徴の出現回数とモジュラリティの増分

本節ではデータセット内における単語の出現回数と， 本稿において提案する手法で特徴に与えるスコア ∆Q との関係について述べる． 図 4 は各データセット内で特徴が現れるインスタン スの割合を横軸とし，特徴に付与されるスコアを縦軸 1_{http://scikit-learn.org/stable/modules/generated/} sklearn.cluster.KMeans.html 2_{http://www.rondhuit.com/download.html#ldcc} 3_{http://nlp.ist.i.kyoto-u.ac.jp/index.php?JUMAN} として全特徴をプロットしたグラフである．「する」，「な る」という動詞のようにどのインスタンスにも含まれ ているような出現回数が多い特徴や，ごく一部のイン スタンスにしか含まれないような出現回数が小さい特 徴は，他と比べモジュラリティの増分が小さい．また 出現するインスタンス数が同じ特徴のなかでも，他の 特徴との相互作用によりスコアが大きい特徴と小さい 特徴が存在していることがわかる． 図 4: データセットにおける特徴の出現回数とそのスコ ア ∆Q

4.3

選択した特徴を利用したクラスタリング

本節では提案する手法により選択した特徴を用いて クラスタリングを行う．図 5 は特徴にランキングをつ けた後に上位 x 個の特徴のみを用いてクラスタリング を行った場合の純度を示したグラフである．横軸を使 用した特徴の数，縦軸をその特徴集合を用いて k 平均 法でクラスタリングを行った場合の純度としている．ま た特徴集合の数，選択に使用した手法にのみよる変化 を見るために最初の中心点を決定する乱数のシードを 固定している． 比較のため，図 5 では次の 5 種類の方法で特徴を選択 してクラスタリングを行った場合を同時に示している． A は，NI個全てのインスタンスを用いて 3 節で提案し た方法で特徴にスコアを与え，スコアが高い特徴から 選択した場合を表す．B は，ランダムに√NIlog NI個 のインスタンスを選んで A と同様に選択した場合を表 す．C は，ランダムに√NI個のインスタンスを選んで A と同様に選択した場合を表す．D は，使用されてい るインスタンス数が多い特徴から選択した場合を表す． E は，特徴にランダムに数値を与え大きいものから選 択した場合を表す． 図 5 より，本研究で提案する手法を用いた場合，数 個のみの特徴からなる集合を用いるだけで，全特徴を

図 5: 各特徴選択手法によって選択した特徴集合の大 きさと，その部分集合でクラスタリングを行った際の 純度 使用してクラスタリングを行ったときにきわめて近い 純度のクラスタリングを行えていることがわかる． 第 3 節で述べたとおり，A では計算量が O(N2 INF) となるが，B,C のようにサンプリングを行った場合は 計算量がそれぞれ O(NI(log NI)2NF), O(NINF) とな

り，k 平均法を使用してクラスタリングを行う際の前 処理としても少ない計算量でスコアの近似値を得るこ とができる． 図 6 に本稿において提案する手法を用いてクラスタ リングを行った場合の処理時間を示す．図 5 に使用し た A∼E と同じ選択方法をとる．また処理時間とは，本 稿で提案する手法による処理にかかる時間とクラスタ リングにかかる時間の合計とする． 図 6: 選択する特徴集合の大きさと，選択とクラスタリ ングにかかる時間 図 5 から，本稿において提案する手法で選択した 10 個 の特徴を選択してクラスタリングを行うことで，全ての 特徴を使用してクラスタリングを行ったときの 98.4%と 極めて近い純度でクラスタリングすることができると いうことが分かる．図 6 より，特徴を選択せずに全て の特徴を用いてクラスタリングするときと，本手法を 適用し特徴数を 10 に削減した後にクラスタリングする ときの処理時間について比較すると，後者のほうが約 7 倍高速に計算できていることが分かるが，図 5 から分 かるようにクラスタリングの純度は全特徴を使用した 場合と 10 個の特徴を使用した場合に大きい差は無い． このように，NI = 800 のデータでは，k 近傍法のため の前処理として利用することで学習を高速化できてい ることが分かる．

謝辞

本研究は JST，CREST および，JSPS 科研費 26280085， 26280090 の助成を受けたものです．

参考文献

[1] Blondel, V. D., et al.: Fast unfolding of com-munities in large networks, Journal of

statisti-cal mechanics, theory and experiment, Vol. 2008,

P.10008 (2008).

[2] Brandes, Ulrik, et al. :On modularity cluster-ing.IEEE transactions on knowledge and data

en-gineering 20.2 pp.172-188 (2008).

[3] Guyon, I. and Elisseeff, A. : An introduction to variable and feature selection. Journal of

ma-chine learning research, Volume 3, pp.1157-1182.

(2003).

[4] Newman, M. E. J. and Girvan, M. : Finding and evaluating community structure in networks,

Physical review, E 69.2, P.026113. (2004).

[5] Newman, M. E. J. : Fast algorithm for detect-ing community structure in networks, Physical

review, E 69.6, P.066133. (2004).

[6] Peng, H., Long, F. and Ding, C. : Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy, IEEE Transactions on pattern

anal-ysis and machine intelligence, 27.8, pp.226-1238,

(2005).

[7] Shin, K., Kuboyama, T., Hashimoto, T. and Shepard, D. :Super-CWC and super-LCC: Super fast feature selection algorithms, IEEE