形式概念分析(formal concept analysis)とは、対象の集合、属性の集合と「対象が属性をもつ」関係の組である形式文脈から、共通の属性で過不足なく決まる対象と属性の組(形式概念)を取り出し、その全体のなす完備束(概念束)を調べる理論である。完備束が概念束と同型になるのは、対象と属性をそれぞれ上限稠密・下限稠密な部分集合に送り、関係を順序に移す写像があるときで、とくに有限束は既約元の文脈から復元される。成り立つ属性の含意は、擬内包から作る Guigues–Duquenne の基底によって最少の個数で生成される。
形式概念分析(formal concept analysis)とは、対象の集合 $G$、属性の集合 $M$、「対象 $g$ が属性 $m$ をもつ」という関係 $I\subseteq G\times M$ の 3 つ組(形式文脈)から、「共通の属性で過不足なく決まる対象のまとまり」である 形式概念 を取り出し、その全体を束として調べる理論である。Wille が 1982 年に束論を概念の階層として読み直す試みとして始めた(Wil82)。
形式概念の全体は包含で 完備束 をなす(Galois接続 の定理「概念束の基本定理」)。この記事の主定理は 2 つある。1 つは、完備束がある形式文脈の概念束と同型になるための必要十分条件である(thm-fca-basic)。とくに有限束は、結び既約元と交わり既約元のなす文脈から復元される(cor-fca-finite)。もう 1 つは、文脈で成り立つ含意の全体を最少の個数で生成する集合が、擬内包から作られる Guigues–Duquenne の基底であること(thm-fca-dg)である。
集合 $G,M$ と関係 $I\subseteq G\times M$ の組 $(G,M,I)$ を 形式文脈 といい、$G$ の元を 対象、$M$ の元を 属性 とよぶ。$(g,m)\in I$ を $g\,I\,m$ と書く。$A\subseteq G$、$B\subseteq M$ について
$$
A':=\{m\in M\mid\text{すべての }g\in A\text{ で }g\,I\,m\},\qquad B':=\{g\in G\mid\text{すべての }m\in B\text{ で }g\,I\,m\}
$$
とおく(導出作用素)。$g\in G$ について $g':=\{g\}'$、$m\in M$ について $m':=\{m\}'$ と書く。
$A'$ は $A$ の対象が共通にもつ属性の全体、$B'$ は $B$ の属性をすべてもつ対象の全体である。2 つの導出作用素は Galois接続 の「関係の極」であり、そこで示された通り、$A\subseteq B'\iff B\subseteq A'$、$A\subseteq A''$、$A'''=A'$ が成り立つ。とくに $A\mapsto A''$、$B\mapsto B''$ は 閉包作用素 である。
$A\subseteq G$、$B\subseteq M$ の組 $(A,B)$ が $A'=B$ かつ $B'=A$ を満たすとき、形式概念 という。$A$ をその 外延、$B$ を 内包 とよぶ。形式概念の全体を $\mathfrak B(G,M,I)$ と書き、$(A_1,B_1)\le(A_2,B_2)$ を $A_1\subseteq A_2$(同値なことに $B_2\subseteq B_1$)で定める。$(\mathfrak B(G,M,I),\le)$ を 概念束 という。
外延は $A=A''$ となる $A$、内包は $B=B''$ となる $B$ にほかならず、$(A,B)$ は外延 $A$ だけで($B=A'$)、また内包 $B$ だけで決まる。外延が大きいほど内包は小さい。$\mathfrak B(G,M,I)$ は完備束で、概念の族 $(A_t,B_t)_{t\in T}$ の下限と上限は
$$
\bigwedge_t(A_t,B_t)=\Bigl(\bigcap_tA_t,\ \bigl(\textstyle\bigcup_tB_t\bigr)''\Bigr),\qquad\bigvee_t(A_t,B_t)=\Bigl(\bigl(\textstyle\bigcup_tA_t\bigr)'',\ \bigcap_tB_t\Bigr)
$$
で与えられる(Galois接続 の定理「概念束の基本定理」の 1)。
$g\in G$ について $\gamma g:=(g'',g')$ を 対象概念、$m\in M$ について $\mu m:=(m',m'')$ を 属性概念 という。$\gamma g$ は $g$ を外延に含む最小の概念、$\mu m$ は $m$ を内包に含む最大の概念である。
$G=\{1,2,3,4,5,6\}$、$M=\{e,o,p,s\}$(偶数、奇数、素数、平方数)とし、$I$ を「$g$ がその性質をもつ」とする。対象ごとの属性は
$$
1':\{o,s\},\quad2':\{e,p\},\quad3':\{o,p\},\quad4':\{e,s\},\quad5':\{o,p\},\quad6':\{e\}
$$
である。内包は対象の属性の集合のいくつかの共通部分($0$ 個の共通部分は $M$)として得られ、形式概念は次の $10$ 個である(外延、内包の順)。
$$
\begin{aligned}
&(\emptyset,M),\ (\{1\},\{o,s\}),\ (\{2\},\{e,p\}),\ (\{4\},\{e,s\}),\ (\{3,5\},\{o,p\}),\\
&(\{1,4\},\{s\}),\ (\{1,3,5\},\{o\}),\ (\{2,3,5\},\{p\}),\ (\{2,4,6\},\{e\}),\ (G,\emptyset).
\end{aligned}
$$
$3$ と $5$ は同じ属性をもつので、どの外延でも一緒に現れる。$\gamma6=(\{2,4,6\},\{e\})=\mu e$ である。
対象の属性の集合 $\{o,s\},\{e,p\},\{o,p\},\{e,s\},\{e\}$ の 2 つずつの共通部分は $\emptyset,\{o\},\{s\},\{p\},\{e\}$ で、それ以上の共通部分から新しいものは出ない。これに $M$ を加えた $10$ 個が内包であり、各内包 $B$ の外延 $B'$ を計算すると上の表になる。
完備束 $L$ の部分集合 $X$ が 上限稠密 であるとは、$L$ のすべての元が $X$ のある部分集合の上限になることをいう。下限稠密 も同様に定める。$X$ が上限稠密なら、各 $x\in L$ は $x=\bigvee\{y\in X\mid y\le x\}$ を満たす($x$ を上限にもつ部分集合は右辺の集合に含まれ、右辺は $x$ 以下だから)。
完備束 $L$ と形式文脈 $(G,M,I)$ について、次は同値である。
1⇒2. $L=\mathfrak B(G,M,I)$ としてよい。$\tilde\gamma:=\gamma$、$\tilde\mu:=\mu$ とおく。概念 $(A,B)$ について、上限の式から $\bigvee_{g\in A}\gamma g=\bigl((\bigcup_{g\in A}g'')'',\ \cdot\ \bigr)$ で、$g\in g''\subseteq A''=A$ なので $\bigcup_{g\in A}g''=A$、外延は $A''=A$ である。従って $(A,B)=\bigvee\gamma(A)$ で、$\gamma(G)$ は上限稠密である。同様に $(A,B)=\bigwedge\mu(B)$ で、$\mu(M)$ は下限稠密である。$g\,I\,m$ なら $g\in m'$ で、$m'$ は外延なので $g''\subseteq m'$、すなわち $\gamma g\le\mu m$ である。逆に $\gamma g\le\mu m$ なら $g\in g''\subseteq m'$ で $g\,I\,m$ である。
2⇒1. $x\in L$ について
$$
\psi(x):=\bigl(A_x,B_x\bigr),\qquad A_x:=\{g\mid\tilde\gamma(g)\le x\},\quad B_x:=\{m\mid x\le\tilde\mu(m)\}
$$
とおく。$A_x'=\{m\mid\text{すべての }g\in A_x\text{ で }\tilde\gamma(g)\le\tilde\mu(m)\}=\{m\mid\bigvee\tilde\gamma(A_x)\le\tilde\mu(m)\}$ であり、上限稠密性から $\bigvee\tilde\gamma(A_x)=x$ なので $A_x'=B_x$ である。下限稠密性から同様に $B_x'=A_x$ である。従って $\psi(x)\in\mathfrak B(G,M,I)$ で、$\psi$ は順序を保つ。
逆向きに $\varphi(A,B):=\bigvee\tilde\gamma(A)$ とおくと、$\varphi$ も順序を保つ。$\varphi(\psi(x))=\bigvee\tilde\gamma(A_x)=x$ である。概念 $(A,B)$ について $x:=\varphi(A,B)$ とおくと、
$$
B_x=\{m\mid\text{すべての }g\in A\text{ で }\tilde\gamma(g)\le\tilde\mu(m)\}=\{m\mid\text{すべての }g\in A\text{ で }g\,I\,m\}=A'=B
$$
なので $\psi(x)=(B',B)=(A,B)$ である。よって $\psi$ と $\varphi$ は互いに逆な順序同型である。$\bigwedge\tilde\mu(B)=\bigwedge\tilde\mu(B_x)=x$ も下限稠密性から従う。$\psi(\tilde\gamma(g))$ の外延 $E:=\{h\mid\tilde\gamma(h)\le\tilde\gamma(g)\}$ は $g$ を含む外延なので $g''\subseteq E$ であり、$h\in E$、$m\in g'$ なら $\tilde\gamma(h)\le\tilde\gamma(g)\le\tilde\mu(m)$ から $h\,I\,m$ なので $E\subseteq g''$ である。よって $\psi(\tilde\gamma(g))=\gamma g$ である($\mu$ も同様)。$\square$
$L$ 自身を対象と属性にとり、$\tilde\gamma,\tilde\mu$ を恒等写像とすると、$L\cong\mathfrak B(L,L,\le)$ が得られる。これは Galois接続 の定理「概念束の基本定理」の 2 である。thm-fca-basic は、対象と属性をずっと少なくとれることを述べている。
有限の束 $L$ の元 $x$ が 結び既約 であるとは、$x$ が最小元でなく、$x=y\lor z$ なら $x=y$ または $x=z$ となることをいう。交わり既約 も双対的に定める。結び既約元の全体を $J(L)$、交わり既約元の全体を $M(L)$ と書く。
有限の束 $L$ について $L\cong\mathfrak B(J(L),M(L),\le)$ である。ここで $\le$ は $L$ の順序を $J(L)\times M(L)$ に制限した関係である。
有限の束は完備である。$J(L)$ が上限稠密であることを、$x$ より小さい元の個数に関する帰納法で示す。$x$ が最小元なら空集合の上限である。$x$ が結び既約ならそれ自身の上限である。そうでなければ $x=y\lor z$、$y,z< x$ と書け、帰納法の仮定で $y,z$ は $J(L)$ の元の上限なので $x$ もそうである。双対的に $M(L)$ は下限稠密である。包含写像を $\tilde\gamma,\tilde\mu$ として thm-fca-basic を当てはめる。$\square$
既約元は上限稠密・下限稠密な集合の中で最小である(結び既約元は自分より小さい元の上限にならない)ので、この文脈は $L$ を表す文脈の中で最も小さいものの 1 つである。たとえば $12$ の約数の束(整除の順序)では $J(L)=\{2,3,4\}$、$M(L)=\{3,4,6\}$ で、$3\times3$ の文脈から $6$ 元の束が復元される。
$n\ge2$ と $G=M=\{1,\dots,n\}$ について次が成り立つ。
以下この節では $M$ は有限とする。
$X,Y\subseteq M$ の組を 含意 といい、$X\to Y$ と書く。$X$ の属性をすべてもつ対象が $Y$ の属性もすべてもつとき、すなわち $X'\subseteq Y'$ のとき、含意 $X\to Y$ は文脈で 成り立つ という。これは $Y\subseteq X''$ と同値である。
含意の集合 $\mathcal L$ について、$Z\subseteq M$ が $\mathcal L$ で閉じている とは、$(X\to Y)\in\mathcal L$ で $X\subseteq Z$ ならつねに $Y\subseteq Z$ となることをいう。$Z$ を含む $\mathcal L$ で閉じた最小の集合を $\mathcal L(Z)$ と書く(閉じた集合の共通部分は閉じている)。文脈で成り立つ含意の集合 $\mathcal L$ が 完全 であるとは、すべての $Z\subseteq M$ で $\mathcal L(Z)=Z''$ となることをいう。
$Z''$ は $Z$ を含む最小の内包で、内包は成り立つ含意で閉じているので、成り立つ含意の集合 $\mathcal L$ についてつねに $\mathcal L(Z)\subseteq Z''$ である。完全性は等号を求める。$\mathcal L$ が完全なら、含意 $X\to Y$ が成り立つことは $Y\subseteq\mathcal L(X)$、すなわち $X\to Y$ が $\mathcal L$ の含意を繰り返し当てて導かれることと同値になる。成り立つ含意の全体はもちろん完全だが、$2^{|M|}$ 個の左辺をもち冗長である。
$P\subseteq M$ が 擬内包 であるとは、$P\ne P''$ であり、$P$ に真に含まれるすべての擬内包 $Q$ について $Q''\subseteq P$ となることをいう($P$ の元の個数に関する帰納的な定義)。擬内包 $P$ ごとの含意 $P\to P''$ の集合 $\mathcal L_{\mathrm{DG}}$ を Guigues–Duquenne の基底 という。
$P,Q$ を擬内包とし、$P\not\subseteq Q$、$Q\not\subseteq P$ とする。このとき $P\cap Q$ は内包である。
$R:=P\cap Q$ とおく。$R$ に真に含まれる擬内包 $S$ は $P,Q$ に真に含まれるので、$S''\subseteq P$ かつ $S''\subseteq Q$、すなわち $S''\subseteq R$ である。$R\ne R''$ と仮定すると、$R$ は擬内包の定義を満たす。$R\subsetneq P$ なので $R''\subseteq P$、同様に $R''\subseteq Q$ で、$R''\subseteq R$ となり $R\ne R''$ に反する。$\square$
$M$ が有限の形式文脈について、次が成り立つ。
1. $\mathcal L_{\mathrm{DG}}$ の含意は成り立つので、$Y:=\mathcal L_{\mathrm{DG}}(Z)$ について $Y\subseteq Z''$ である。$Y\ne Y''$ と仮定する。$Y$ は $\mathcal L_{\mathrm{DG}}$ で閉じているので、$Y$ に真に含まれる擬内包 $Q$ について $Q''\subseteq Y$ であり、$Y$ は擬内包の定義を満たす。すると $Y\to Y''$ が $\mathcal L_{\mathrm{DG}}$ に入り、$Y$ が閉じていることから $Y''\subseteq Y$ となって矛盾する。従って $Y=Y''$ で、$Z\subseteq Y$ から $Z''\subseteq Y''=Y$ である。よって $Y=Z''$ である。
2. 擬内包 $P$ について $\mathcal L(P)=P''\ne P$ なので、$P$ は $\mathcal L$ で閉じていない。そこで $(X_P\to Y_P)\in\mathcal L$ で $X_P\subseteq P$、$Y_P\not\subseteq P$ となるものを 1 つ選ぶ。$P\mapsto(X_P\to Y_P)$ が単射であることを示せばよい。
異なる擬内包 $P,Q$ で同じ含意 $X\to Y$ が選ばれたとする。$X\subseteq P\cap Q$ で、$Y\not\subseteq P$、$Y\not\subseteq Q$ である。
この基底は Guigues と Duquenne による(GD86、p. 16 の定理。そこでは擬内包に当たる集合を「非冗長の節(noeud de non-redondance)のうち極小なもの」として別の形で定義し、極小な含意の族の含意の個数がその個数に等しいことを示している)。thm-fca-dg の 2 の証明は、擬内包ごとに「それを閉じさせない含意」を割り当てるという考え方による。
ex-fca-numbers の文脈の擬内包は $\{e,o\}$ と $\{p,s\}$ の 2 つで、基底は
$$
\{e,o\}\to M,\qquad\{p,s\}\to M
$$
である。「偶数かつ奇数の数はない」「平方数の素数はない」の 2 つから、この文脈で成り立つ含意がすべて導かれる。
内包でない集合は、内包の一覧にない $\{e,o\},\{p,s\}$ と、それらを含む $\{e,o,p\},\{e,o,s\},\{e,p,s\},\{o,p,s\}$ である。$\{e,o\}$、$\{p,s\}$ は真に含む擬内包がない(1 元の集合と $\emptyset$ はすべて内包である)ので擬内包である。3 元の集合はどれも $\{e,o\}$ か $\{p,s\}$ を真に含み、その閉包 $M$ を含まないので擬内包でない。
$G=\{g\}$、$M=\{a,b,c\}$、$I=\emptyset$ とする。内包は $\emptyset=g'$ と $M=\emptyset'$ の 2 つだけである。擬内包は $\{a\},\{b\},\{c\}$ の 3 つで、閉包はどれも $M$ である(2 元の集合は閉包 $M$ を含まない擬内包を真に含むので擬内包でない)。thm-fca-dg により、成り立つ含意の完全な集合は少なくとも 3 個の含意を含む。
文脈が有限なら、内包は 閉包作用素 $B\mapsto B''$ の閉集合なので、$M$ の部分集合をある全順序(lectic 順序)で調べ、次の内包を直接求めていく Ganter の NextClosure 算法で列挙できる(Gan10)。同じ算法は、閉包作用素を「真に含まれる擬内包 $P$ の含意 $P\to P''$ だけで閉じる」操作に替えると、内包と擬内包をまとめて列挙するのに使える(この操作で閉じた集合はちょうど内包と擬内包である)。概念束は小さな文脈でも大きくなりうる。ex-fca-boolean の 1 では $n$ 個の対象から $2^n$ 個の概念が生じる。
形式文脈は $G\sqcup M$ を頂点とし $I$ を辺とする 二部グラフ とみることもでき、$A,B$ がともに空でない形式概念 $(A,B)$ は、$A\times B\subseteq I$ となる組 $(A,B)$ のうち包含で極大なもの(極大な完全二部部分グラフ)に当たる。$A\times B\subseteq I$ は $B\subseteq A'$ と同値で、極大性は $B=A'$、$A=B'$ と同値だからである。
形式概念分析は、データの表(対象と二値の属性)から概念の階層と属性の依存関係を取り出す方法として、データ解析や知識表現に用いられる。ex-fca-numbers-dg のように、基底は表に潜む規則を最も短く要約する。
| 主張 | 反例 | 満たされない条件 |
|---|---|---|
| 完備束 $L$ の部分集合 $G,M$ と順序の制限から、$L$ は概念束として復元される | $L=\{0< 1< 2\}$、$G=\{2\}$、$M=L$:外延は $\emptyset,\{2\}$ だけで、概念束は 2 元 | $G$ の上限稠密性($1$ は $G$ の部分集合の上限でない) |
| 閉包が等しい擬内包は 1 つの含意にまとめられる | ex-fca-same-closure | 擬内包から閉包への対応が単射であること(3 つの擬内包の閉包がどれも $M$) |
| 概念の個数は対象と属性の個数の多項式で抑えられる | ex-fca-boolean の 1 | 各対象のもつ属性が定数 $k$ 個以下であること(そのとき概念は $\lvert G\rvert\,2^k+1$ 個以下。$(G,M,\ne)$ では各対象が $n-1$ 個の属性をもつ) |
ex-fca-same-closure では $\{a\}\cap\{b\}=\emptyset$ が内包であり、lem-fca-pseudo-meet の通り、どの含意も 2 つの擬内包を同時には閉じさせない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する