形式概念分析

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

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

概要と歴史

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

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

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

形式コンテキストの形式概念は、以下で説明するように、より正式にはコンテキストの「概念格子」と呼ばれる階層構造で順序付けることができます。概念格子は「線図」としてグラフィカルに視覚化することができ、データの理解に役立ちます。ただし、これらの格子は視覚化するには大きすぎることがよくあります。その場合、形式概念分析の数学的理論が役立つ場合があります。たとえば、情報を失うことなく格子をより小さな部分に分解したり、より解釈しやすい別の構造に格子を埋め込んだりできます。

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

動機と哲学的背景

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

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

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

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

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

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

例

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

データテーブルは正式なコンテキストを表し、その横の線図はその概念格子を示しています。正式な定義は以下のとおりです。

上記の線図は、円、接続線分、およびラベルで構成されています。円は正式な概念を表します。線により、サブコンセプトとスーパーコンセプトの階層を読み取ることができます。各オブジェクトと属性名は、図の中でラベルとして 1 回だけ使用され、オブジェクトは概念円の下に、属性は概念円の上にあります。これは、オブジェクトに属性がある場合に限り、オブジェクトから昇順パスを介して属性に到達できるように行われます。

示されている図では、たとえば、オブジェクト「貯水池」には属性「停滞」および「一定」がありますが、属性「一時的」、「実行中」、「自然」、「海上」はありません。したがって、水たまりには特性「一時的」、「停滞」および「自然」が正確に存在します。

ラベル付けされた図や形式概念から、元の形式コンテキストを再構築できます。概念の範囲は、概念を表す円に上昇するパスがつながるオブジェクトで構成されます。意図は、その概念円 (図内) から上昇するパスがある属性で構成されます。この図では、ラベル「貯水池」のすぐ左にある概念には、意図「淀んだ、自然」と範囲「水たまり、マール、湖、池、タルン、プール、ラグーン、海」があります。

正式な文脈と概念

形式コンテキストは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 | (g,m) \in I for all g \in A} 、つまり、Aのすべてのオブジェクトに共有される

すべての属性の集合であり、双対的に

B' = {g \in G | (g,m) \in I for all m \in B}

、つまり、 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内にはその属性を持たないオブジェクトが存在します。

計算の目的では、形式コンテキストは、行がオブジェクトに対応し、列が属性に対応し、各エントリk _i_,_jが「オブジェクト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 _{2のときに、 (}A ₁、B ₁ ) ≤ ( A ₂、B ₂ ) であると言います。同様に、B ₁ ⊇ B _{2のときはいつでも、 (}A ₁、B ₁ ) ≤ ( A ₂、B ₂ ) です。

この順序で、すべての形式的概念セットには最大共通サブコンセプト、つまり集合があります。その範囲は、セットのすべての範囲に共通するオブジェクトで構成されます。双対的に、すべての形式的概念セットには最小共通スーパーコンセプトがあり、その意図は、その概念セットのすべてのオブジェクトが持つすべての属性で構成されます。

これらの meet および join 操作は、束、つまり完全束を定義する公理を満たします。逆に、すべての完全束は、何らかの形式コンテキストの概念束であることが示されます (同型性まで)。

属性値と否定

現実世界のデータは、多くの場合、オブジェクト属性テーブルの形式で提供され、属性には「値」があります。形式概念分析では、このようなデータを（「1 つの値」の）形式コンテキストの基本型に変換して処理します。この方法は、概念スケーリングと呼ばれます。

属性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 $\in$ $G$ および $m \in M$ に対して、

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

そして二重に

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

非インシデントオブジェクトと属性のペアのみを関連付けることができるため、これらの関係は形式的なコンテキストを表すテーブルに簡単に記録できます。矢印関係からは、分配性やその一般化など、多くの格子特性を読み取ることができます。また、矢印関係は構造情報も明らかにし、格子の合同関係などを決定するために使用できます。

理論の拡張

三項概念分析は、オブジェクトと属性の間の二項関係を、オブジェクト、属性、条件の間の三項関係に置き換えます。すると、発生は、オブジェクト $(g,m,c)$ g $が$ 条件 $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上の弱い否定は弱い相補、つまり、公理 $x$ $ΔΔ$ $\leq$ $x$ $と ($ $x$ $⋀$ $y$ $) ⋁ ($ $x$ $⋀$ $y$ $Δ$ $) =$ $x$ を満たす順序反転マップ $Δ:$ $L$ $\to$ $L$ です。弱い反対は双対の弱い相補です。概念代数のような、弱補集合と双対弱補集合を備えた（有界）格子は、弱二補集合と呼ばれる。弱二補集合は、分配的正補集合、すなわちブール代数を一般化する。^[12]^[13]

時間概念分析

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

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

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

アルゴリズムとツール

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

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

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