二部グラフにおける(k; l)-Plex のための形式概念解析の拡張

二部グラフにおける

(k, l)-Plex

のための形式概念解析の拡張

Extension of Formal Concept Analysis

for (k, l)-Plex in Bipartite Graphs

小島 健介

1∗

_{呉 可天}

1

Kensuke Kojima

1

Ketian Wu

1

1

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

1

_{Graduate School of Informatics, Kyoto University}

Abstract: Aiming at establishing a theoretical foundation of biclustering, we consider an ex-tension of formal concept analysis (FCA) that can be applied to a wider class of biclusters. This class is determined by the notion of (k, l)-plex in bipartite graphs, which is an analogue of k-plex in general graphs. We introduce a pair of operators similar to those used in FCA that take intent and extent of sets of objects (items) and attributes (transactions), respectively. We examine their relationship to (k, l)-plexes, and discuss whether results similar to those of FCA still hold for the extended setting. The pair of operators is not as well-behaved as in FCA, but we can show that the iterated application of these operators converges to a fixed point, which is a maximal (k, l)-plex. Moreover, we give an upper bound of the number of iterations needed to reach the fixed point.

1

はじめに

本稿では，双クラスタリング (biclustering) の理論的 な基礎付けについて議論する．双クラスタリングは，関 係データから強く結び付いたクラスタを抽出する技術 である．応用としては，同時に購入されることの多い 商品の組合せ見つけるバスケット解析 [2] や，遺伝子発 現データからのマイニング [3] などがあり，また金融分 野への応用も存在する [4]． クラスタとは，直感的には密に関連し合う部分集合 のことであるといえるだろう．それでは，密であるとい うことを数学的に定式化するとどのようになるだろう か．いくつか可能な定式化が考えられそうだが，その 中で振る舞いのよいものはどれだろうか．本稿は，こ のような問いに（部分的な）答を与えようとするもの である． まず，関係データを二部グラフとみることにすると， 一番わかりやすいのは二部クリークである．これは最も 厳密な意味での双クラスタともいえる．これに関する理 論は形式概念解析 (Formal Concept Analysis; FCA)[1] によってよく整理されている（FCA では二部グラフ・ 極大二部クラスタのことをそれぞれ形式文脈・形式概 念と呼ぶが，名前が異なるだけで数学的には同じもの である）． ∗_{連絡先： 京都大学大学院情報学研究科}        〒 606-8501 京都市左京区吉田本町        E-mail: [email protected] ところが，実データにおいては必ずしも二部クリー クのような厳密な構造が見られるとは限らない．現実 のデータにはノイズが含まれることも多い．大多数に おいて関係が成り立っていて，クラスタらしく見えて も，一部には関係が成立していない組が存在すること がある．このような場合にも，それらはクラスタを形 成しているとみなしたい．ところが，二部クリークし か考えないとすると，そのようなものは排除されてし まう． そこでいくらかの空白があることも許容する形に条 件を緩めたい．本稿では，そのような変更を施した場 合に，対応する FCA の理論はどのように変更されるか を調べる． 具体的には，まず「大多数において関係が成り立っ ている双クラスタ」の定義として，(k, l)-plex という概 念を導入する．これは一般のグラフの k-plex に相当す る概念を二部グラフで考えたものである．これに対応 する形で，FCA における演算子↑↓（定義は 2 節を参 照）の類似を定義する．この操作は FCA における↑↓ が持っているよい性質を必ずしも受け継いでいないが， いくつかの好ましい性質を持つことを示すことができ る．特に，任意の点から始めて繰り返し適用すれば極 大 (k, l)-plex に収束することが示せる（定理 4）．また， 収束までの繰り返し回数の上界の評価も与えることが できる（定理 5）． 次節以降の構成は次の通りである．まず 2 節で FCA の基本事項をまとめ，それらを二部グラフと二部クリー 人工知能学会研究会資料 SIG-FPAI-B802-08

クの言葉で言い直すとどうなるかを述べる．3 節で (k, l)-plex を定義し，FCA に現れるいくつかの概念や演算を それに対応する形で拡張する．また，それらの基本的 性質をいくつか挙げる．そのうち特に非自明なものに ついては 4 節で証明を与える．最後に 5 節で本稿の主 な結果をまとめ，本論で触れなかった話題について簡 単に述べる．

2

準備

2.1

形式概念解析

二つの集合 U, V とその間の二項関係 E⊆ U × V の 組 (U, V, E) のことを形式文脈という（通常は (G, M, I) などの文字を使うことが多いが，本稿では後で述べるよ うに二部グラフと同一視するので (U, V, E) と書くこと にする）．形式文脈 (U, V, E) が与えられたとき，A⊆ U と B⊆ V の組で A × B ⊆ E となるもののうち，極大 なものを形式概念という． 写像_{↓: P(U) → P(V ), ↑: P(V ) → P(U) は次のよ} うに定義される（記号には陽に表れていないが，これ らは E に依存して決まる）． ↓A = {v ∈ V | N(v) ⊆ A} ↑B = {u ∈ U | N(u) ⊆ B} ↑, ↓ は他の文献では (−)′_{または (−)}E_{と書かれること} が多いが，本稿では上記の記号を使う． 次のことはよく知られている事実である [1]． 定理 1. 1. ↑↓ は閉包演算子になる．すなわち A ⊆

↑↓A, ↑↓↑↓A = ↑↓A を満たし，A ⊆ B ならば ↑↓A ⊆ ↑↓B である． 2. (A, B) が形式概念であることは，↓A = B かつ ↑B = A であることと同値である． 3. 任意の形式概念は (A,↓A) の形で書ける．逆にこ の形の組は A が↑↓ の不動点ならば形式概念にな る．よって，形式概念と_{↑↓ の不動点は一対一に} 対応する．

2.2

二部クリークと形式概念の対応

形式文脈 (U, V, E) は，E を辺の集合とみなすと二部 グラフとみることができる．二部グラフ (U, V, E) の二 部クリークとは A⊆ U と B ⊆ V の組で A × B ⊆ E を満たすもののことであるから，形式文脈と二部グラ フを同一視すれば，形式概念と極大二部クリークは同 じ概念であるということができる． 我々は（極大）二部クリークの条件を緩めることに 興味があり，それは形式概念の条件を緩めるというこ とと同じである．次節以降では，そのような緩和を行っ たときに上記の演算子_{↑↓ がどの程度よい性質を維持す} るかを主に議論する．

3

(k, l)-plex

の定義と性質

本節以降，特に断らなければ (U, V, E) は二部グラフ とする．また，頂点 u∈ U ∪ V に対し，その隣接点の 集合を N (u) で表す． (V, E) を無向グラフ（二部グラフとは限らない）と するとき，X ⊆ V が k-plex であるとは，各頂点 v ∈ X に対し，それに隣接しない頂点が X の中に k 個以下し かないもののことをいう．これはクリーク（すべての 二点間に辺があるような頂点の集合）の条件を弱めた ものになっている（k = 1 の場合がクリークである）． このことに着目し，k-plex の二部グラフにおける類似 概念として (k, l)-plex を定義する． 定義 2. A⊆ U と B ⊆ V の組 (A, B) が (k, l)-plex で あるとは，各 u∈ A に対して |B \ N(u)| ≤ k（つまり u に隣接しない頂点は B の中に k 個以下しかない）か つ各 v∈ B に対して |A \ N(v)| ≤ l であるようなもの のことをいう． 定義から直ちにわかるように，二部クリークは (0, 0)-plex に一致する．この意味で (k, l)-0)-plex は二部クリー クの一般化である． ↓, ↑ の類似である ↓k:P(U) → P(V ), ↑l:P(V ) → P(U) を，次を満たすものと定義する． v∈ ↓kA ⇐⇒ |A \ N(v)| ≤ k, u∈ ↑_lB ⇐⇒ |B \ N(u)| ≤ l. この二つの演算の合成として_↑l↓k:P(U) → P(U) が 定義できる．A が↑l↓kの不動点であるとき，(A,↓kA) は極大 (k, l)-plex になることが容易に確かめられる．こ のことは_{↑↓A が極大二部クリークの片側であるという} 事実（定理 1 の 3 を二部グラフの言葉で言い換えたも の）の一般化になっている．実際，k = l = 0 とすれば ↑l↓kは FCA における↑↓ と一致し，定理 1 と同じ主張 になる．しかし，逆は k = l = 0 の場合を除いて成立 しない．すなわち，一般には極大 (k, l)-plex は↑l↓kの 不動点であるとは限らない．これは，k = l = 0 のとき には_↑l↓kが閉包演算子になるが，一般の場合にはそう ではないということと関係している． このように，_↑l↓kの振る舞いは FCA の↑↓ に比べる と性質がよくないが，次のことは一般に成り立つ．

補題 3. 1. ↓_k は順序を反転させる，すなわち A⊆ A′⊆ U のとき ↓_kA′ ⊆ ↓_kA である．↑_lについて も同様のことが成り立つ． 2. ↑l↓kは順序を保存する，すなわち A ⊆ A′ ⊆ U のとき_↑l↓kA⊆ ↑_l↓_kA′である． また，_↑l↓k は閉包演算子にはならないが，「繰り返 し適用すれば，どんな集合から始めてもいつかは極大 (k, l)-plex にたどり着く」という形にすれば一般に成立 する．このことを定理の形で述べると次のようになる （後の定理 5 と合わせて次節で証明する）． 定理 4. A0⊆ U とする．Bi⊆ V および Ai+1⊆ U を， Bi =↓kAi, Ai+1=↑lBiによって定義する．このとき， ある n が存在して An= An+1となる． したがって，任意の A0から始めて有限回の反復によ り極大 (k, l)-plex が得られることになる．ただし，FCA と異なり，A⊆ U から始めて得られる不動点が A を含 むとは限らない．また，既に述べたようにすべての極 大 (k, l)-plex が不動点になるわけではない． 上の定理における繰り返し回数は次のように上から 評価することができる． 定理 5. 定理 4 の n は，n≤ l 2|U|+ k 2|V |+min(|U|, |V |)+ 1 となるようにとれる． これが実際の n の上限にどの程度近いかは本稿執筆 の時点では詳しくはわかっていないが，n が少なくと も O(min(|U|, |V |)) になる場合があることは次の例に よって示される． 例 6. p, q は十分大きい正の整数とする．U ={1, 2, . . . , p}, V ={1, 2, . . . , q} とし，E を (i, j)∈ E ⇐⇒ ⌈i 2⌉ ≤ j ≤ 2i で定義する．p = 12, q = 16 の場合の隣接行列を図 1 に 示した．r =⌊1 2min(p, q)⌋ とすると，一般に x ≤ y < r に対し ↓1[x, y] =↑1[x, y] = [⌊ y 2⌋, 2x + 2] となる．このことを用いて A0 ={1, 2}, k = l = 1 の ときの Ai, Biを計算すれば，i < r について Ai= [i + 1, 2(i + 1)] が成り立つことが再帰的に確かめられる．よって Ar−2 ̸= Ar−1となるから，An = An+1が成り立つ最小の n は 少なくとも r− 1 ∈ O(min(|U|, |V |)) 以上であることが わかる． 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 図 1: 例 6 で p = 12, q = 16 とした場合の隣接行列

4

収束性の証明

定理 4 と 5 を証明する．以下，Ai, Biは定理 4 の通 りとする．定理 5 の不等式を満たす n で An = An+1 が成り立つものが存在することを示せばよい． 次のように定義する．

zi=|((Ai\ Ai+1)× Bi)\ E|,

z_i′=|((Ai+1\ Ai)× Bi)\ E|,

wi=|(Ai+1× (Bi\ Bi+1))\ E|,

w′i=|(Ai+1× (Bi+1\ Bi))\ E|.

補題 7. zi, zi′, wi, w′iについて，次の不等式が成り立つ． (l + 1)· |Ai\ Ai+1| ≤ zi, z′i≤ l · |Ai+1\ Ai|, (k + 1)· |Bi\ Bi+1| ≤ wi, w′i≤ k · |Bi+1\ Bi|. Proof. いずれも同様の方法で証明できるので，最初の 不等式のみ示す．ziの定義から，各 u∈ Ai\ Ai+1に ついて |{v ∈ Bi| (u, v) /∈ E}| ≥ l + 1 を示せば十分である．N (u) ={v | (u, v) ∈ E} だから， これは_{|Bi\ N(u)| ≥ l + 1 と同値であり，この不等式} は u /∈ Ai+1 =↑lBiと↑lの定義から導かれる． 補題 8. X0, X1, . . . , Xmが有限集合の列なら m∑−1 i=0 |Xi\ Xi+1| + |Xm|. = m∑−1 i=0 |Xi+1\ Xi| + |X0| Proof. |X \ Y | = |X| − |X ∩ Y | を用いて書き直すとわ かる． 補題 9. n_∑−1 i=0 (zi+ wi) +|(An× Bn)\ E| = n₋₁ ∑ i=0 (z_i′+ w′_i) +|(A0× B0)\ E|

Proof. ((Ai\Ai+1)×Bi)\E = ((Ai×Bi)\E)\((Ai+1×

Bi)\ E) などが成り立つことに注意し，補題 8 を集合

の列 (A0×B0)\E, (A1×B0)\E, (A1×B1)\E, (A2×

B1)\ E, . . . , (An× Bn)\ E に適用する．

これらの補題を用いると

n−1

∑

i=0

(|Ai\ Ai+1| + |Bi\ Bi+1|) ≤ l|U| + k|V | (1)

であることがわかる（詳細は図 2）．この不等式を用い て定理 5 を証明する． まず，ある i≤ l 2|U|+ k 2|V | に対して Ai⊆ Ai+1また は Bi⊆ Bi+1が成り立つことを示す．いま，ある正整数 N 以前ではいずれの包含関係も成り立たないと仮定す る．すなわちすべての i < N について Ai̸⊆ Ai+1かつ Bi ̸⊆ Bi+1であるような N を考える．すると各 i < N について 1≤ |Ai\ Ai+1| かつ 1 ≤ |Bi\ Bi+1| だから， 不等式 (1) より，このような N は 2N≤ l|U| + k|V | を 満たす．したがって対偶をとれば，2N > l|U| + k|V | となる N に対してはある i < N でいずれかの包含関係 が成り立つことがわかる．特に N = 1 +⌊l 2|U| + k 2|V |⌋ の場合を考えれば，i≤ l 2|U| + k 2|V | となるように i を とれることがわかる．

次に，Ai⊆ Ai+1または Bi⊆ Bi+1が成り立つよう

な i が見つかったとして，ある j≤ min(|U|, |V |)+1 に

ついて Ai+j = Ai+j+1であることを示す．Ai ⊆ Ai+1

のとき，Ai⊆ Ai+1 ⊆ Ai+2⊆ . . . であるから，Ai+j =

Ai+j+1となる最小の j をとると|U| ≥ |Ai+j| ≥ |Ai|+j

である．よって_{|U| ≥ j となる．またこのとき B}i ⊇

Bi+1 ⊇ . . . であり，この列は少なくとも Bi+j₋₁までは

狭義単調に減少するから，同様の評価により_{|V | ≥ j−1} も成り立つ．よってある j ≤ min(|U|, |V |) + 1 につい

て Ai+j = Ai+j+1であることがわかった．Bi ⊆ Bi+1

のときも同様である． 以上の議論における i + j を定理 5 の n としてとれ ば，定理の主張が成り立つ．

5

まとめと今後の課題

本稿では，二部クリークの条件を緩和した概念とし て (k, l)-plex を定義し，それに対応する FCA の類似物 を調べた．特に，_{↑↓ に対応する演算の性質を調べた．} その結果，条件を緩和した場合には FCA の場合と違っ て閉包演算子にならないが，高々O(l|U| + k|V |) 回の 繰り返しの後に不動点に到達することがわかった． 本稿では扱わなかったが，_↑l↓kの不動点の列挙アルゴ リズムについても考察を行っているところである．_↑l↓k の不動点は飽和アイテム集合の類似と考えることがで きるが，飽和アイテム集合については，閉包演算子_↑↓ の性質を用いた高速な列挙アルゴリズムが知られてい る [5]．一方，本稿で定義した↑l↓kは閉包演算子では なく，また_↑l↓kを繰り返し適用して不動点を得る操作 を考えても，やはり閉包演算子にはならない．しかし， ↑l↓kに少し変更を加えたものを考えれば閉包演算子が 得られることがわかっており，この事実を用いて列挙 アルゴリズムが構築できると考えられる．詳細は，本 稿執筆時点では準備中である．

謝辞

本研究は CREST, JST, JPMJCR1401 の支援を受け たものです．

参考文献

[1] Bemhard Ganter and Rudolf Wille. Formal

Con-cept Analysis. Springer, 1999.

[2] Jiawei Han, Micheline Kamber, and Jian Pei. Data

Mining: Concepts and Techniques. The Morgan

Kaufmann Series in Data Management Systems. Morgan Kaufmann Publishers, third edition edi-tion, 2011.

[3] Beatriz Pontes, Ra´ul Gir´aldez, and Jes´us S. Aguilar-Ruiz. Biclustering on expression data. J.

of Biomedical Informatics, Vol. 57, No. C, pp.

163–180, October 2015.

[4] Kelvin Sim, Jinyan Li, Vivekanand Gopalkrish-nan, and Guimei Liu. Mining maximal quasi-bicliques to co-cluster stocks and financial ratios for value investment. In Proceedings of the Sixth

International Conference on Data Mining, ICDM

’06, pp. 1059–1063, Washington, DC, USA, 2006. IEEE Computer Society.

[5] Takeaki Uno, Tatsuya Asai, Yuzo Uchida, and Hi-roki Arimura. LCM: an efficient algorithm for enumerating frequent closed item sets. In Bart Goethals and Mohammed Javeed Zaki, editors,

FIMI ’03, Frequent Itemset Mining Implementa-tions, Proceedings of the ICDM 2003 Workshop on Frequent Itemset Mining Implementations, 19 December 2003, Melbourne, Florida, USA, Vol. 90

of CEUR Workshop Proceedings. CEUR-WS.org, 2003.

n_∑−1 i=0 (|Ai\ Ai+1| + |Bi\ Bi+1|) ≤ n_∑−1 i=0 (zi+ wi)− l n−1 ∑ i=0 |Ai\ Ai+1| − k n_∑−1 i=0 |Bi\ Bi+1| (補題 7) = n_∑−1 i=0 (z′_i+ w′_i) +|(A0× B0)\ E| − |(An× Bn)\ E| − l n−1 ∑ i=0 |Ai\ Ai+1| − k n−1 ∑ i=0 |Bi\ Bi+1| (補題 9) ≤ l n_∑−1 i=0 (|Ai+1\ Ai| − |Ai\ Ai+1|) + k n_∑−1 i=0

(|Bi+1\ Bi| − |Bi\ Bi+1|) + |(A0× B0)\ E| − |(An× Bn)\ E|

(補題 7) = l(|An| − |A0|) + k(|Bn| − |B0|) + |(A0× B0)\ E| − |(An× Bn)\ E| (補題 8)

≤ l|An| + k|Bn| − l|A0| − |(An× Bn)\ E| (補題 7 と同様にして|(A0× B0)\ E| ≤ k|B0|)

≤ l|An| + k|Bn|

≤ l|U| + k|V |.