concept latticeについて - ashiato45の日記

杉山麿人先生のデータマイニングについての講義を受けていて、concept latticeのところ~~が講義の最後のほうTwitterしてたら分からなくなったので~~の理解を深めるためにぽちぽち調べたり考えたりした記録です。とはいえそんなにちゃんとは調べていないので定義とか間違ってたらごめんなさい。

定義は曖昧さがないように真面目にやっていますが、まあ例だけ拾っていけば読めると思います。

やりたいこと

データがこんな感じで(いまは8つ)与えられたとき、
f:id:sle:20191025172146p:plain:w100
X⊂{A,B,C,D}*1を含む行がいくつあるかを{A,B,C,D}の(包含で順序を入れた)ハッセ図に書き込むことにする。この数をfrequencyとよぶことにする。例えば、ABDのfrequencyは3*2。こんなかんじ:
f:id:sle:20191025172325p:plain:w300
あたりまえだが、書き込まれた数はハッセ図の上にいくにつれ小さくなっていくことになる(順序に関する反対向きの準同型)。この書き込まれた数の情報を保つようなコンパクトな表現がほしいし、またそれにまつわる数学的な構造を知りたい。

closed pattern

[定義: closed pattern]集合S(上の例だと{A,B,C,D}に関する部分集合全体のなすハッセ図とその上に書きこまれた頻度が与えられたときに、P(S)の部分集合Xが頻度nのclosed patternであるとは、Xが頻度nを持つハッセ図上のノード(その頻度が与えられたSの部分集合)の極大元集合のこと((これ別に講義で言われたことではないのだけれど定義が簡単になるので…)。適当な頻度nがあり、Xが頻度nのclosed patternのとき、単にXをclosed patternとよぶ。

例えば、頻度3を持つノードは上図でABD,AB,BD,B,Cがあるが、このうち上限をあつめると{ABD,C}になるので、頻度3のclosed patternは{ABD, C}である。上図ではclosed patternの元たちすべてが赤く記されている。

どの2つのclosed patternを取ってもそれらがdisjointであることは定義より明らか。

このclosed pattern全体とその頻度だけ覚えておけば、(closed patternに載っていないものを含む)どのノードについてもそこに書かれていた頻度を復元することができる。これは、大きい頻度nのclosed patternからすでに数が書き込まれているノードに出会うまで下がっていって、途中で出会ったすべてのノードにnを書き込んでいけばよいからである。例えば:
f:id:sle:20191025173917p:plain:w300
頻度7,5,4はすべて書き込まれているとして頻度3のノードを復元したいとする。Cから下がるともう{}なのでCに3を書き込んでCについては終了。ABDからスタートすると、AB,AD,BDが子となるが、ADには4が書き込まれているのでAB,BDが残りとなり、この2つに3を書き込む。AB,BDから同様に続ける…となる。

そういうわけで、closed patternの性質を調べてみたい。

contextとその演算

唐突に関係ない数学っぽい話になる。

[定義: context, object, attribute] 集合G,Mとその2項関係I⊂G×Mについて、(G,M,I)のことをcontextとよび、Gのことをobject、Mのことをattributeとよぶ。

例えば、*3 *4Gを男性の集合、Mを女性の集合とし、Iを「カップルになれる男性と女性とのペア全体のなす集合」とすれば、これはcontextになっている。

今回重要な例は、Gをデータのなす集合{ID1,…,ID8}とし、Mを{A,B,C,D}とし、Iを「ID gではmのビットが立っている」で定まる関係としたcontextである。例えば、ID3はAのビットが立っているので(ID3, A)∈Iである。

[定義: derivation] (G,M,I)をcontextとしたとき、A⊂Gのderivationとは{m∈M; 任意のa∈Aについて、(a,m)∈I}となるもののこと。B⊂Mのderivationとは{g∈G; 任意のb∈Bについて、(g, b)∈I}となるもののこと。
A⊂Gのderivation A'はMのsubsetだし、B⊂Mのderivation B'はGのsubsetなことに注意。反対側に行く感じ。

例えば上の男女の例で、A⊂Gを「男子サッカー部員全員」とするなら、A'⊂Gは「男子サッカー部の人なら誰とでもカップルになれる女子全体」となる。「男子サッカー部のカップルになれる人がいる女子全体」ではないことに注意する。

上のハッセ図の例なら、X={A,B}⊂G*5とするならX'は「AもBも1が立っているようなデータ全体」となり、X'={ID1, ID5, ID8}となる。反対に、Y={ID1, ID2}とするならY'は「ID1でもID2でもビットが立っているような要素全体」となり、これはAのみなのでY'={A}となる。

concept

[定義: concept] (G,M,I)をcontextとする。A⊂GとB⊂Mについて、A'=BとB'=Aがなりたつとき、(A,B)をconecptという。

まず定義についてだが、A'=BのA'⊃Bのほうは「任意のb∈Bについて、さらに任意のa∈Aについて(a,b)∈I」となり、A'⊂Bのほうは「任意のa∈Aについて(a, m)∈Iとなるようなどんなm∈Mについても、m∈Bとなる」である。反対側のB'=Aもまとめると、(A,B)がconceptとは

任意のa∈A,b∈Bについて(a,b)∈I
任意のa∈Aについて(a, m)∈Iとなるようなどんなm∈Mについても、m∈Bとなる
任意のb∈Bについて(g, b)∈Iとなるようなどんなg∈Gについても、g∈Aとなる

となる。

例えば上の男女の例なら、({男子サッカー部員全員}, {女子バレー部員全員})がconceptであるとする。上の条件を順に確認するなら

どの男子サッカー部員とどの女子バレー部員もカップルになれる
どの男子サッカー部員ともカップルになれるような女子は全員女子バレー部にいる
どの女子バレー部員ともカップルになれるような男子は全員男子サッカー部にいる

ということになる。(2)を反対向きに読んでみるなら「『こいつとカップルになれ』と言われたら絶対嫌だ、というような男子サッカー部員が一人でもいるような女子は女子バレー部員ではない」ということになる。単に男子サッカー部と女子バレー部はどのペアでもカップルになれて相性が良い(1の意味)というだけではなく、男子サッカー部も女子バレー部もそういう人たちを全員漏れ無く集めたような組織になっているという点ですごく相性が良くぴったりということになる。

上のハッセ図では、({ID1, ID5, ID8}, {A, B, D})はconceptになっている。確認すると

ID1はA,B,D全部が立っており、ID5もID8もそう。
ID1,ID5,ID8全部で立ってるビットを集めるとA,B,Dが全てで、これは{A,B,D}にちゃんと含まれている
A,B,D全部が立っているようなデータを集めるとID1,ID5,ID8が全てで、これは{ID1, ID5, ID8}にちゃんと含まれている

となり、ぴったりである。

性質として、定義からほぼあたり前だが次の一意性を確認する: (A1,B)がconceptで、(A2,B)もconceptなら、A1=A2である。(証明)(A1,B)がconceptなのでA1=B'であり、(A2,B)がconceptなのでA2=B'である。よって、A1=A2。(証明おわり)

ただし、「じゃあderivationとればいつでもconcept作れるじゃん、(B', B)はいつでもconceptじゃん」というのは嘘である。{B}'={ID1, ID5, ID8}だが、ID1,ID5,ID8で立っているビットを全部集めると{A,B,D}となり3番の性質に反する。ぴったりな相方組織が作れないような組織もあるのである。

conceptとclosed patternの関係

直前の例で出た{A,B,D}はたまたまclosed patternになっているが、実はこれは偶然ではない。また「ぴったりな相方組織が作れる」ということがclosed patternと関係している。次の関係がなりたつ:
[性質] (G,M,I)を(有限)ハッセ図のcontextとし、B⊂Mとする。(A,B)がconceptとなるA⊂Gが存在する<==>Bがclosed patternとなる。
(略証)(→)存在するとすれば上の性質からA=B'なので、(B',B)がconceptであるという意味になる。Bがclosed patternでないとしよう。Bより真に大きいビットの集合B2で、B2すべてが立っているようなデータの集合の大きさが|B'|であるものがあることになる。B2のビット全てが立っているようなデータはBのビットも全て立っているのだから、結局B2=B'ということになるが、これはB2がBより真に大きいということに矛盾する。(←)*6Bはclosed patternとする。この頻度はderivationの定義より|B'|である。(B',B)がconceptであることを示そう。片方は自明なので、B''=Bであることを示せばよい。つまり、「Bのビットが全て立っているようなデータ全てで立っているビット全体」がBと等しいことを言えばよい。このカギカッコ内の記述から、B⊂B''は明らかである。仮に等号がなりたたないとすると、B''はBより真に大きいことになる。B'''は「Bのビットが全て立っているようなデータ全てで立っているビット全体が立っているようなデータ全体」なので結局B'で、(B', B'')=(B''',B'')はconceptなのでこの証明の前半よりB''は頻度|B'|のclosed patternである。B''はBより真に大きく、頻度は同じ|B'|なのだから、これはclosed patternの極大性に反する。(証明おわり)

conecptとderivationでclosed patternを作る

concept (A,B)のBについて、B''はBより膨らみ、さらにB''''、B''''''とやってもB''と等しくなることが先の証明をヒントにするとわかり、つまりderivationを2回あてることでBを含む最小のconcept(の片割れ)、即ちclosed patternを計算することができる。これを使えば、下から順にclosed patternを作っていくことができ、closed patternの列挙ができることになる。うれしい。