形式概念分析

情報科学において、形式概念分析（FCA）は、オブジェクトとそのプロパティの集合から概念階層または形式オントロジーを導出する原理的な方法である。階層内の各概念は、いくつかのプロパティセットを共有するオブジェクトを表し、階層内の各サブ概念は、その上位概念におけるオブジェクトのサブセット（およびプロパティのスーパーセット）を表す。この用語は1981年にルドルフ・ヴィレによって導入され、 1930年代にギャレット・バーコフらによって開発された格子と順序集合の数学的理論に基づいている。

形式概念分析は、データマイニング、テキストマイニング、機械学習、知識管理、セマンティックウェブ、ソフトウェア開発、化学、生物学などの分野で実際に応用されています。

概要と歴史

形式概念分析の本来の動機は、数学的順序理論の現実世界における意味の探求でした。そのような非常に一般的な可能性の一つは、データテーブルを完全格子と呼ばれる代数構造に変換し、データの視覚化と解釈に利用できることです。「オブジェクトgは属性mを持つ」という形式のペアを表にした、オブジェクトと属性間の異種関係を表すデータテーブルは、基本データ型とみなされます。これは形式コンテキストと呼ばれます。この理論では、形式概念はペア ( A , B )として定義されます。ここで、 Aはオブジェクトの集合 (範囲と呼ばれる)、Bは属性の集合 (意図) であり、

範囲AはBの属性を共有するすべてのオブジェクトから構成され、
インテントBは、 A内のオブジェクトによって共有されるすべての属性で構成されます。

このように、形式概念分析は拡張と内包の意味概念を形式化します。

あらゆる形式的文脈における形式的概念は、後述するように、より正式には文脈の「概念格子」と呼ばれる階層構造に整理することができます。概念格子は「線分図」として視覚的に表現することができ、データの理解に役立ちます。しかしながら、これらの格子は視覚化するには大きすぎる場合が多くあります。そのような場合、形式的概念分析の数学的理論が役立つことがあります。例えば、情報の損失なく格子をより小さな部分に分解したり、より解釈しやすい別の構造に埋め込んだりすることができます。

この理論の現在の形は、1980年代初頭、ダルムシュタット工科大学のルドルフ・ヴィレ、ベルンハルト・ガンター、ペーター・ブルマイスターらの研究グループによって確立されました。しかしながら、その基本的な数学的定義は、1930年代にギャレット・バーコフによって一般格子理論の一部として既に導入されていました。これ以前にも、同じ概念に対する様々なフランスの研究グループによるアプローチがありましたが、ダルムシュタットのグループはこの分野を標準化し、その数学的理論と哲学的基礎の両方を体系的に解明しました。後者は、特にチャールズ・S・パースを参照していますが、ポール＝ロイヤル論理学にも言及しています。

動機と哲学的背景

ウィレは、数学の分野として形式的な概念分析を始めた論文「格子理論の再構築」（1982年）^[1]で、当時の格子理論と純粋数学全般に対する不満から始めています。理論的結果の生成（多くの場合「精巧な頭脳運動」によって達成されます）は印象的でしたが、隣接する領域間のつながり、さらには理論の部分間のつながりが弱くなっていました。

格子理論の再構築は、理論を可能な限り具体的に解釈することで私たちの一般文化とのつながりを再活性化し、格子理論家と格子理論の潜在的なユーザーとの間のより良いコミュニケーションを促進する試みである。

— ルドルフ・ヴィレ^[1]

この目的は、教育学者ハルトムート・フォン・ヘンティヒに遡ります。彼は1972年、より良い教育を目指し、科学を相互に利用可能にし、より一般的に（つまり専門知識がなくても）批判できるようにするために、科学の再構築を訴えました。^[2]したがって、形式概念分析は、その起源において、学際性と研究の民主的な管理を目指しています。^[3]

これは、 19世紀における形式論理の発展における束理論の出発点を修正するものである。当時、そして後のモデル理論においても、単項述語としての概念はその範囲にまで縮小されていた。今や概念の哲学は、意図を考慮することによってより抽象度を下げるべきである。したがって、形式概念分析は、言語学と古典的概念論理における範疇の拡張と内包に向けられている。 ^[4]

形式概念分析は、チャールズ・S・パースのプラグマティックな格言に従い、包含される対象の観察可能な基本的性質を明らかにすることで概念の明確化を目指す。^[3]パースは晩年の哲学において、論理的思考は判断と結論という三位一体の概念によって現実を認識することを目指すと仮定した。数学は論理の抽象化であり、あり得る現実のパターンを展開し、したがって合理的なコミュニケーションを支える可能性がある。こうした背景から、ウィレは次のように定義している。

概念と概念階層の数学的理論としての形式概念分析の目的と意味は、論理的に活性化できる適切な概念構造を数学的に開発することによって、人間の合理的なコミュニケーションをサポートすることです。

— ルドルフ・ヴィレ^[5]

例

この例のデータは、意味論的フィールドスタディから得られたもので、異なる種類の水域がその属性によって体系的に分類されています。^[6]ここでは目的のために簡略化されています。

データ表は形式的な文脈を表し、その隣にある線図はその概念格子を示しています。形式的な定義は以下に続きます。

正式な文脈の例:「水域」
水域		属性
水域		一時的	ランニング	自然	停滞した	絶え間ない	海事
オブジェクト	運河
	チャネル
	ラグーン
	湖
	マール
	水たまり
	池
	プール
	貯水池
	川
	細流
	溝
	海
	ストリーム
	ターン
	急流
	細流

上記の線分図は、円、接続線、そしてラベルで構成されています。円は形式的な概念を表します。線は、下位概念と上位概念の階層構造を読み取ることができます。各オブジェクト名と属性名は、図の中でラベルとして一度だけ使用され、オブジェクトは概念の円の下に、属性は概念の円の上に配置されます。これは、オブジェクトが属性を持つ場合にのみ、オブジェクトから属性へ昇順で到達できるように設計されています。

例えば、図中のオブジェクト「貯水池」は「停滞」と「一定」の属性を持ちますが、「一時的」、「流動」、「自然」、「海上」の属性は持ちません。したがって、「水たまり」は「一時的」、「停滞」、および「自然」の属性を持ちます。

ラベル付けされた図と形式概念から、元の形式的文脈を再構築することができます。概念の範囲は、概念を表す円へと上昇する経路が導くオブジェクトで構成されます。意図は、図中のその概念円から上昇する経路が導く属性で構成されます。この図では、ラベル「貯水池」のすぐ左にある概念は、意図として「淀んだ」「自然」、範囲として「水たまり」「マール」「湖」「池」「タルン」「プール」「ラグーン」「海」を持っています。

正式な文脈と概念

正式なコンテキストは3つの要素 $K = (G, M, I)$ であり、ここでGはオブジェクトの集合、Mは属性の集合、 $I \subseteq G \times M$ はどのオブジェクトがどの属性を持つかを表すインシデンスと呼ばれる2項関係である。^{[4]オブジェクトのサブセット} $A$ $\subseteq$ $G$ と属性のサブセット $B$ $\subseteq$ $M$ に対して、次の 2つの導出演算子を定義する。

A' = {m \in M | \forall g \in A . (g,m) \in I} 、つまり、Aの

すべてのオブジェクトに共有されるすべての属性の集合であり、双対的に

B' = {g \in G | چ m \in B . (g,m) \in I}

、つまり、 Bのすべての属性を共有するすべてのオブジェクトのセット。

いずれかの導出演算子を適用してからもう 1 つを適用すると、2 つの閉包演算子が構成されます。

A ↦ A ′ ′ = ( A ′ ) ′ （ A ⊆ G （閉包範囲））であり、

B ↦ B ′ ′ = ( B ′ ) ′ 、B ⊆ M（意図的閉鎖）。

導出演算子は、オブジェクト集合と属性集合の間のガロア接続を定義します。そのため、フランス語では概念格子はガロア格子（treillis de Galois）と呼ばれることがあります。

これらの導出演算子を使用して、ウィレは形式概念のエレガントな定義を与えました。次の条件を満たす場合、ペア ( A、B ) はコンテキスト $($ $G$ $、$ $M$ $、$ $I$ $)の$ 形式概念です。

A ⊆ G、 B ⊆ M、 A ′ = B、B ′ = A です。

同様に、より直感的に言えば、( A、B ) が正式な概念となるのは次のような場合です。

AのすべてのオブジェクトはBのすべての属性を持ちます。
GにあるがAにはないすべてのオブジェクトに対して、そのオブジェクトにはない属性がBにはある。
M内の属性のうちBにはないものごとに、 A内にはその属性を持たないオブジェクトが存在します。

計算目的では、形式コンテキストは、行がオブジェクト、列が属性に対応し、「オブジェクトiは属性jを持つ」場合、各エントリk _i_,_jは 1 に等しい(0,1) 行列 Kとして自然に表現できます。この行列表現では、各形式概念は、すべての要素が 1 に等しい最大部分行列 (必ずしも連続している必要はありません) に対応します。ただし、形式コンテキストをブール値と見なすのは誤解を招きます。なぜなら、否定された発生率 (「オブジェクトg は属性mを持たない」) は、上で定義したのと同じように概念を形成するものではないからです。このため、形式コンテキストを表すときは、値 1 と 0 または TRUE と FALSE は通常避けられ、発生率を表すには × のような記号が使用されます。

形式的文脈の概念格子

文脈Kの概念 ( A _i , B _i ) は、範囲の包含によって（部分的に）順序付けることができます。あるいは、同様に、意図の二重の包含によって順序付けることができます。概念の順序 ≤ は次のように定義されます。 Kの任意の2つの概念 ( A ₁ , B ₁ ) と ( A ₂ , B ₂ )について、A ₁ ⊆ A ₂のときに ( A 1 , B 1 ) ≤ ( A ₂ , B ₂ )が成り立ちます。同様に、 B ₁ ⊇ B ₂のときはいつでも( A ₁ , B ₁ ) ≤ ( A ₂ , B ₂ )が_成り立ちます_。

この順序で、あらゆる形式概念の集合は最大公約数的な部分概念、すなわち「会合」を持つ。その範囲は、集合のすべての範囲に共通するオブジェクトから構成される。双対的に、あらゆる形式概念の集合は最小公約数的な上位概念を持ち、その意図は、その概念集合のすべてのオブジェクトが持つすべての属性から構成される。

これらのmeetとjoin演算は、束（lattice）、つまり完全束（complete lattice）を定義する公理を満たします。逆に、すべての完全束は、何らかの形式的文脈（同型性を除く）の概念束であることが示されます。

属性値と否定

実世界のデータは、多くの場合、オブジェクト属性表の形で与えられ、属性は「値」を持ちます。形式概念分析では、このようなデータを（「一価」の）形式的文脈の基本型に変換することで扱います。この手法は概念尺度と呼ばれます。

属性mの否定は属性 ¬ mであり、その範囲はmの範囲の補集合、すなわち (¬ m ) ′ = G \ m ′となる。一般に、否定された属性が概念形成に利用可能であるとは想定されていない。しかし、互いに否定し合う属性のペアは、例えば概念尺度から導かれる文脈において、自然に生じることが多い。

形式概念の可能な否定については、以下の概念代数のセクションを参照してください。

意味合い

含意A → B は、 2つの属性の集合AとBを関連付け、 Aの各属性を持つすべてのオブジェクトはBの各属性も持つことを表します。 $($ $G$ $,$ $M$ $,$ $I$ $)$ が形式コンテキストで、A、B が属性の集合Mの部分集合(つまり、A,B ⊆ M ) のとき、含意A → BはA ′ ⊆ B ′のときに有効です。有限の形式コンテキストごとに、すべての有効な含意の集合には標準的な基底^[7]、つまり自然な推論 (アームストロングの規則) によってすべての有効な含意を導き出すことができる冗長性のない含意の集合があります。これは、含意に基づく知識獲得方法である属性探索で使用されます。 ^[8]

矢印関係

形式概念分析は精緻な数学的基礎を持ち、^[4]この分野は多方面にわたります。基本的な例として、単純で計算も容易ですが、非常に有用な矢印関係を挙げます $。$ これ $は$ 以下のように定義され $ます$ $。g\inG$ および $m\inM$ に対して $、$

g ↗ m \Leftrightarrow (g, m) \notin I であり、 m' \subseteq n' かつ m' \neq n' ならば (g, n) \in I であり、

そして二重に

g ↙ m \Leftrightarrow (g, m) \notin I であり、 g' \subseteq h' かつ g' \neq h' ならば (h, m) \in I である。

非偶発的なオブジェクトと属性のペアのみが関連付けられるため、これらの関係は形式的な文脈を表す表に記録するのが便利です。矢印関係からは、分配性やその一般化を含む、多くの格子特性を読み取ることができます。また、それらは構造情報も明らかにし、例えば格子の合同関係を決定するために使用できます。

理論の拡張

三項概念分析は、オブジェクトと属性の間の二項関係である発生関係を、オブジェクト、属性、条件の間の三項関係に置き換えます。発生は、オブジェクトg $(g,m,c)$ が $条件$ cの下で $属性$ mを持つ $こと$ を表します。三項概念は上記の形式概念に類似して定義できますが、それによって形成される三項格子の理論は概念格子の理論よりもはるかに発展が遅れており、難解であるように思われます。^[9] Voutsadakisはn項の場合を研究しました。^[10]
ファジィ概念分析：形式概念分析のファジィバージョンに関する広範な研究が行われてきた。^[11]
概念代数: 形式概念の否定をモデル化することは、形式概念 ( A、 B ) の補集合 $( G \ A、M \ B )$ は一般に概念ではないため、多少問題があります。しかし、概念束は完全であるため、 $C$ $\subseteq$ $G$ $\$ $A$ を満たすすべての概念 ( C、 D )の結合 ( A、 B )^{Δ を考えることができます。あるいは、双対的に、} $D$ $\subseteq$ $M$ $\$ $B$ を満たすすべての概念の会合 ( A、 B )^{𝛁 を考えることができます。これらの2つの演算は、それぞれ}弱否定と弱反対と呼ばれます。これは、導出演算子で表現できます。弱否定は $($ $A$ $,$ $B$ $)$ $Δ$ $= (($ $G$ $\$ $A$ $)″, ($ $G$ $\$ $A$ $)')$ と書くことができ、弱反対は $($ $A$ $,$ $B$ $)$ $𝛁$ $= (($ $M$ $\$ $B$ $)', ($ $M$ $\$ $B$ $)″)$ と書くことができます。 2つの追加演算 Δ と 𝛁 を備えた概念束は、コンテキストの概念代数として知られています。概念代数はべき集合を一般化します。概念束L上の弱否定は弱相補、つまり順序反転マップ $Δ:$ $L$ $\to$ $L$ であり、公理 $x$ $ΔΔ$ $\leq$ $x$ $と ($ $x$ $⋀$ $y$ $) ⋁ ($ $x$ $⋀$ $y$ $Δ$ $) =$ $x$ を満たします。弱反対は双対の弱相補です。概念代数のような（有界）格子は、弱補集合と双対弱補集合を備えており、弱二補集合格子と呼ばれる。弱二補集合格子は、分配的直交補集合格子、すなわちブール代数を一般化する。^[12]^[13]

時間概念分析

時間概念分析（TCA）は、形式概念分析（FCA）の拡張であり、時間的現象の概念的記述を目的としています。TCAは、変化するオブジェクトに関するデータから得られた概念格子にアニメーションを提供します。TCAは、連続、離散、またはハイブリッドな空間と時間における具体的または抽象的なオブジェクトの変化を理解するための一般的な方法を提供します。TCAは、概念的スケーリングを時間データベースに適用します。^[14]

最も単純なケースでは、TCAは、物理学における粒子のように、時間とともに変化するオブジェクトを考察します。粒子は、各時点で正確に1つの場所に存在します。これは、「時間オブジェクト」と「時間」という属性がデータベースのキーを形成するような時間データにおいて起こります。そして、（あるビューにおけるある時点における時間オブジェクトの）状態は、選択されたビューを記述する形式的コンテキストの特定のオブジェクト概念として形式化されます。この単純なケースでは、時間システムの典型的な視覚化は、時間オブジェクトの軌跡が埋め込まれたビューの概念格子の線図です。 ^[15]

TCAは、任意のキーを持つ時間データベースを考察することで、上記のケースを一般化します。これは、例えば天気図上の高気圧帯のように、任意の時点で複数の場所に存在する可能性のある分散オブジェクトの概念につながります。「時間オブジェクト」「時間」「場所」という概念は、スケール内の形式概念として表現されます。状態はオブジェクト概念の集合として形式化されます。これは、物理学における粒子と波の概念の概念的解釈につながります。^[16]

アルゴリズムとツール

形式概念を生成し、概念束を構築・操作するための、単純かつ高速なアルゴリズムが数多く存在します。概要については、KuznetsovとObiedkov ^[17]、またはGanterとObiedkovの著書^[8]を参照してください。これらの著書には擬似コードも掲載されています。形式概念の数は形式コンテキストのサイズに対して指数関数的に増加する可能性があるため、アルゴリズムの複雑さは通常、出力サイズに応じて与えられます。数百万要素の概念束も問題なく処理できます。

現在、多くのFCAソフトウェアアプリケーションが利用可能です。^[18]これらのツールの主な目的は、形式的コンテキストの作成から形式的概念マイニング、そして与えられた形式的コンテキストの概念格子とそれに対応する含意および相関ルールの生成まで多岐にわたります。これらのツールのほとんどは、以下のような学術的なオープンソースアプリケーションです。

コンエクスプ^[19]
トスカーナJ ^[20]
ラティスマイナー^[21]
コロン^[22]
FcaBedrock ^[23]
ギャラクティック^[24]