形式概念分析

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

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

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

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

このようにして、形式概念分析は、外延と内包という意味論的概念を形式化する。

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

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

形式概念分析を数学の一分野として提唱した論文「格子理論の再構築」（1982年）^{[ 1 ]}の中で、ウィレは現在の格子理論と純粋数学全般に対する不満から出発している。理論的成果の創出（しばしば「精緻な精神的体操」によって達成される）は印象的であったが、隣接する領域間、さらには理論の一部間のつながりは弱くなっていた。

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

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

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

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

概念および概念階層の数学理論としての形式概念分析の目的と意義は、論理的に活性化可能な適切な概念構造を数学的に開発することによって、人間の合理的なコミュニケーションを支援することにある。

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

データ表は形式的なコンテキストを表し、その隣の線図はその概念格子を示しています。形式的な定義は以下に続きます。

上記の線図は、円、接続線、およびラベルで構成されています。円は形式的な概念を表します。線は、下位概念と上位概念の階層構造を読み取るためのものです。各オブジェクト名と属性名は、図の中でラベルとして一度だけ使用され、オブジェクトは概念円の下に、属性は概念円の上に配置されます。これは、オブジェクトがその属性を持っている場合に限り、オブジェクトから上位のパスを経由して属性に到達できるようにするためです。

図に示すように、例えば、貯水池というオブジェクトは「静止」と「一定」という属性を持ちますが、「一時的」、「流動的」、「自然」、「海洋性」という属性は持ちません。したがって、水たまりはまさに「一時的」、「静止」、そして「自然」という特性を持ちます。

ラベル付きの図と形式概念から、元の形式的文脈を再構築できます。概念の範囲は、概念を表す円に上昇する経路が存在するオブジェクトで構成されます。意図は、その概念の円（図中）から上昇する経路が存在する属性で構成されます。この図では、ラベル「貯水池」のすぐ左にある概念の意図は「停滞した自然」であり、範囲は「水たまり、マール、湖、池、小湖、プール、ラグーン、海」です。

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

A ′ = { m ∈ M | ∀ g ∈ A . ( g,m ) ∈ I } 、つまり、 A のすべてのオブジェクトが共有するすべての属性の集合であり

B ′ = { g ∈ G | ∀ m ∈ B . ( g,m ) ∈ I } 、つまり、 B のすべての属性を共有するすべてのオブジェクトの集合。

いずれかの導出演算子を適用してからもう一方の導出演算子を適用すると、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 1 ⊆ A _{2の場合に限り (} A ₁ , B ₁ ) ≤ ( A ₂ , B ₂ )であると言います。同等に、 B ₁ ⊇ B ₂の場合に限り( A ₁ , B ₁ ) ≤ ( A ₂ , B ₂ )です_。

この順序で、形式概念のあらゆる集合には、最大共通部分概念、すなわち共通部分概念が存在する。その範囲は、集合のすべての範囲に共通する対象から構成される。同様に、形式概念のあらゆる集合には、最小共通上位概念が存在する。その上位概念の内包は、その概念集合のすべての対象が持つすべての属性から構成される。

これらの結合操作は、束を定義する公理を満たし、実際には完全束を定義します。逆に、すべての完全束は、（同型を除いて）何らかの形式的文脈の概念束であることが示せます。

現実世界のデータは、多くの場合、属性に「値」を持つオブジェクト属性表の形式で与えられます。形式概念分析は、このようなデータを（「一値」の）形式コンテキストの基本型に変換することで処理します。この手法は概念スケーリングと呼ばれます。

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

g ↗ m ⇔ ( g, m ) ∉ Iかつ、 m ′ ⊆ n ′かつm ′ ≠ n ′の場合、( g, n ) ∈ I、

そして二重に

g ↙ m ⇔ ( g, m ) ∉ Iかつg ′ ⊆ h ′かつg ′ ≠ h ′ならば ( h, m ) ∈ I。

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

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

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

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

• ConExp ^{[ 19 ]}
• ToscanaJ ^{[ 20 ]}
• ラティスマイナー^{[ 21 ]}
• コロン^{[ 22 ]}
• FcaBedrock ^{[ 23 ]}
• 銀河系^{[ 24 ]}

形式概念分析は、データ分析の定性的方法として使用できます。1980年代初頭のFCAの初期から、ダルムシュタット工科大学のFCA研究グループは、FCAを使用した200以上のプロジェクトから経験を積んできました（2005年現在）。^{[ 34 ]}これには、医学と細胞生物学、^{[ 35 ] [ 36 ]}遺伝学、^{[ 37 ] [ 38 ]}生態学、^{[ 39 ]}ソフトウェア工学、^{[ 40 ]}オントロジー、^{[ 41 ]}情報学と図書館学、^{[ 42 ] [ 43 ] [ 44 ]}事務管理、^{[ 45 ]}法学、^{[ 46 ] [ 47 ]}言語学、^{[ 48 ]}政治学^{[ 49 ]}などの分野が含まれます。

さらに多くの例は、例えば「形式概念分析の基礎と応用」^{[ 34 ]}、国際形式概念分析会議（ICFCA）^{[ 50 ]} 、概念格子とその応用（CLA） [ ^{51 ]}、国際概念構造会議（ICCS）[52]などの定期的な会議の^{会議論文に記載されて}います。

• 形式概念分析ホームページ
• デモは2013年7月25日にWayback Machineにアーカイブされました
• 形式概念分析。ICFCA国際会議議事録
  • 土井: 10.1007/978-3-540-70901-5 2007 5th
  • 土井: 10.1007/978-3-540-78137-0 2008 6th
  • 土井: 10.1007/978-3-642-01815-2 2009 7th
  • 土井: 10.1007/978-3-642-11928-6 2010 8th
  • 土井：10.1007/978-3-642-20514-9 2011年第9回
  • 土井: 10.1007/978-3-642-29892-9 2012 10th
  • 土井: 10.1007/978-3-642-38317-5 2013 11th
  • doi : 10.1007/978-3-319-07248-7 2014年12月
  • 土井: 10.1007/978-3-319-19545-2 2015 13th
  • doi : 10.1007/978-3-319-59271-8 2017年14日
  • 土井: 10.1007/978-3-030-21462-3 2019 15th
  • 土井：10.1007/978-3-030-77867-5 2021年16日