Анализ формальных понятий

Анализ формальных понятий (АФП) (англ. Formal Concept Analysis, FCA) — ветвь прикладной алгебраической теории решёток. Традиционно АФП относят к области концептуальных структур в искусственном интеллекте.

Анализ формальных понятий является методом анализа данных. С помощью этого метода анализа могут быть визуализированы объектно-признаковые зависимости. Это достигается построением диаграммы решётки формальных понятий. Основная математическая идея анализа формальных понятий — возможность построения полной решётки по любому бинарному отношению и формализация описания понятия в виде пары (объём, содержание).

В основе решеток формальных понятий лежит так называемое соответствие Галуа, задаваемое на множестве объектов и признаков и обладающее известным из философского определения понятий свойством уменьшения объёма с ростом содержания.

Основные определения

Контекстом в АФП называют тройку K = (G, M, I), где G — множество объектов, M — множество признаков, а отношение I ⊆ G × M говорит о том, какие объекты какими признаками обладают. Для произвольных A ⊆ G и B ⊆ M определены операторы Галуа:

A' = {m ∈ M | ∀ g ∈ A (g I m)},

B' = {g ∈ G | ∀ m ∈ B (g I m)}.

Оператор ″ (двукратное применение оператора ′ ) является оператором замыкания: он идемпотентен (A″″ =A″ ), монотонен (A ⊆ B влечет A″ ⊆ B″ ) и экстенсивен (A ⊆ A″ ). Множество объектов A ⊆ G, такое, что A″ = A, называется замкнутым. Аналогично для замкнутых множеств признаков — подмножеств множества M. Пара множеств (A, B), таких, что A ⊆ G, B ⊆ M, A′ = B и B′ = A, называется формальным понятием контекста K. Множества A и B замкнуты и называются объемом и содержанием формального понятия (A, B) соответственно. Для множества объектов A множество их общих признаков A' служит описанием сходства объектов из множества A, а замкнутое множество A″ является кластером сходных объектов (с множеством общих признаков A′ ). Отношение ″быть более общим понятием″ задается следующим образом: (A, B) ≥ (C, D) тогда и только тогда, когда A ⊇ C.

Понятия формального контекста K = (G, M, I), упорядоченные по вложению объемов образуют решетку B(G, M, I), называемую решеткой понятий. Для визуализации решеток понятий используют так называемые диаграммы Хассе, т.е. граф покрытия отношения "быть более общим понятием".

История

Анализ формальных понятий (англ. Formal Concept Analysis, FCA) был предложен Вилле (нем. Wille) в 1981 году (сама работа вышла в 1982 году, также указывается и 1984 год), хотя есть более ранние работы французских исследователей Барбю и Монжарде, которые использовали соответствие Галуа и получали то, что называется Galois Lattice или решёткой формальных понятий. Методы Анализа Формальных Понятий востребованы и активно развиваются сегодня.

Ссылки

• [conexp.sourceforge.net/DrawingLineDiagrams-ICAI2001.pdf С. А. Евтушенко Алгоритмы рисования линейных диаграмм]
• [www.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7_%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D0%BF%D0%BE%D0%BD%D1%8F%D1%82%D0%B8%D0%B9 Анализ формальных понятий на сайте machinelearning.ru]

Отрывок, характеризующий Анализ формальных понятий

– Ну что же? – сказал он.
– Ей рассказывали, что Москва вся сгорела, совершенно, что будто бы…
Наташа остановилась: нельзя было говорить. Он, очевидно, делал усилия, чтобы слушать, и все таки не мог.
– Да, сгорела, говорят, – сказал он. – Это очень жалко, – и он стал смотреть вперед, пальцами рассеянно расправляя усы.
– А ты встретилась с графом Николаем, Мари? – сказал вдруг князь Андрей, видимо желая сделать им приятное. – Он писал сюда, что ты ему очень полюбилась, – продолжал он просто, спокойно, видимо не в силах понимать всего того сложного значения, которое имели его слова для живых людей. – Ежели бы ты его полюбила тоже, то было бы очень хорошо… чтобы вы женились, – прибавил он несколько скорее, как бы обрадованный словами, которые он долго искал и нашел наконец. Княжна Марья слышала его слова, но они не имели для нее никакого другого значения, кроме того, что они доказывали то, как страшно далек он был теперь от всего живого.
– Что обо мне говорить! – сказала она спокойно и взглянула на Наташу. Наташа, чувствуя на себе ее взгляд, не смотрела на нее. Опять все молчали.
– Andre, ты хоч… – вдруг сказала княжна Марья содрогнувшимся голосом, – ты хочешь видеть Николушку? Он все время вспоминал о тебе.
Князь Андрей чуть заметно улыбнулся в первый раз, но княжна Марья, так знавшая его лицо, с ужасом поняла, что это была улыбка не радости, не нежности к сыну, но тихой, кроткой насмешки над тем, что княжна Марья употребляла, по ее мнению, последнее средство для приведения его в чувства.
– Да, я очень рад Николушке. Он здоров?

Когда привели к князю Андрею Николушку, испуганно смотревшего на отца, но не плакавшего, потому что никто не плакал, князь Андрей поцеловал его и, очевидно, не знал, что говорить с ним.
Когда Николушку уводили, княжна Марья подошла еще раз к брату, поцеловала его и, не в силах удерживаться более, заплакала.
Он пристально посмотрел на нее.
– Ты об Николушке? – сказал он.
Княжна Марья, плача, утвердительно нагнула голову.
– Мари, ты знаешь Еван… – но он вдруг замолчал.
– Что ты говоришь?
– Ничего. Не надо плакать здесь, – сказал он, тем же холодным взглядом глядя на нее.

Когда княжна Марья заплакала, он понял, что она плакала о том, что Николушка останется без отца. С большим усилием над собой он постарался вернуться назад в жизнь и перенесся на их точку зрения.
«Да, им это должно казаться жалко! – подумал он. – А как это просто!»
«Птицы небесные ни сеют, ни жнут, но отец ваш питает их», – сказал он сам себе и хотел то же сказать княжне. «Но нет, они поймут это по своему, они не поймут! Этого они не могут понимать, что все эти чувства, которыми они дорожат, все наши, все эти мысли, которые кажутся нам так важны, что они – не нужны. Мы не можем понимать друг друга». – И он замолчал.

Маленькому сыну князя Андрея было семь лет. Он едва умел читать, он ничего не знал. Он многое пережил после этого дня, приобретая знания, наблюдательность, опытность; но ежели бы он владел тогда всеми этими после приобретенными способностями, он не мог бы лучше, глубже понять все значение той сцены, которую он видел между отцом, княжной Марьей и Наташей, чем он ее понял теперь. Он все понял и, не плача, вышел из комнаты, молча подошел к Наташе, вышедшей за ним, застенчиво взглянул на нее задумчивыми прекрасными глазами; приподнятая румяная верхняя губа его дрогнула, он прислонился к ней головой и заплакал.