Войти
Формальный концептуальный анализ (FCA ) - это принципиальный способ получения иерархии понятий или формальной онтологии из набора объектов и их свойств. Каждое понятие в иерархии представляет объекты, разделяющие некоторый набор свойств; и каждая подконцепция в иерархии представляет собой подмножество объектов (а также надмножество свойств) в концепциях над ним. Термин был введен Рудольфом Вилле в 1981 году и основан на математической теории решеток и упорядоченных множеств, разработанной Гарретом Биркгофом и другие в 1930-е гг.
Анализ формальных концепций находит практическое применение в таких областях, как интеллектуальный анализ данных, интеллектуальный анализ текста, машинное обучение, управление знаниями, семантическая сеть, разработка программного обеспечения, химия и биология.
Первоначальной мотивацией формального анализа концепций был поиск реального мира мне Основы математической теории порядка. Одна такая возможность очень общего характера заключается в том, что таблицы данных могут быть преобразованы в алгебраические структуры, называемые полными решетками, и что их можно использовать для визуализации и интерпретации данных. Таблица данных, которая представляет гетерогенное отношение между объектами и атрибутами, табулирующая пары в форме «объект g имеет атрибут m», считается базовым типом данных. Это называется формальным контекстом. В этой теории формальное понятие определяется как пара (A, B), где A - это набор объектов (называемый экстентом), а B - набор атрибутов (намерение), таких что
Таким образом, формальный анализ концепций формализует семантику понятия расширения и содержания.
Формальные концепции любого формального контекста могут - как объяснено ниже - быть упорядочены в иерархии, более формально называемой концепцией контекста решетка ". Решетка понятий может быть графически визуализирована как «линейная диаграмма», которая затем может быть полезна для понимания данных. Однако часто эти решетки становятся слишком большими для визуализации. Тогда математическая теория анализа формальных понятий может оказаться полезной, например, для разложения решетки на более мелкие части без потери информации или для встраивания ее в другую структуру, которую легче интерпретировать.
Теория в ее нынешнем виде восходит к началу 1980-х, и исследовательская группа под руководством Рудольфа Вилле, Бернхарда Гантера и Питера Бурмейстера из Technische Universität Darmstadt. Однако его основные математические определения были введены еще в 1930-х годах Гарретом Биркгофом как часть общей теории решеток. Другие предыдущие подходы к той же идее возникли у различных французских исследовательских групп, но группа Дармштадта нормализовала эту область и систематически разработала как ее математическую теорию, так и ее философские основы. Последние относятся, в частности, к Чарльзу С. Пирсу, но также и к логике Порт-Рояля.
В его статье «Теория реструктуризации решетки» ( 1982), положив начало анализу формальных понятий как математической дисциплине, Вилле начинает с недовольства современной теорией решеток и чистой математикой в целом: получение теоретических результатов - часто достигаемых с помощью «сложной умственной гимнастики» - было впечатляющим, но взаимосвязь между ними соседние области, даже части теории становились слабее.
Теория реструктуризации решетки - это попытка активизировать связи с нашей общей культурой путем максимально конкретной интерпретации теории и, таким образом, способствовать лучшему общению между теоретиками решетки и потенциальными пользователями теории решеток
— Рудольф Вилле, <285 Эта цель восходит к педагогу Хартмуту фон Хентигу, который в 1972 г. выступал за реструктуризацию наук с целью улучшения преподавания и для того, чтобы сделать науки взаимно доступными и в более общем плане (то есть также без специальных знаний) критичными. Следовательно, по своему происхождению анализ формальных понятий направлен на междисциплинарность и демократический контроль над исследованиями.Он исправляет отправную точку теории решеток во время развития формальной логики в XIX веке. Затем - и позже в теории моделей - понятие унарного предиката было сокращено до его степени. Опять же, философия понятий должна стать менее абстрактной, если принять во внимание цель. Следовательно, формальный анализ концептов ориентирован на категории расширение и содержание в лингвистике и классической концептуальной логике.
Формальный анализ концептов направлен на ясность концепций согласно прагматической максиме Чарльза С. Пирса путем раскрытия наблюдаемых, элементарных свойств включенных объектов. В своей поздней философии Пирс предположил, что логическое мышление направлено на восприятие реальности с помощью концепции триады, суждения и заключения. Математика - это абстракция логики, она вырабатывает модели возможных реальностей и, следовательно, может поддерживать рациональное общение. На этом фоне Вилле определяет:
Цель и смысл анализа формальных понятий как математической теории понятий и иерархий понятий состоит в том, чтобы поддерживать рациональное общение людей путем математической разработки соответствующих концептуальных структур, которые могут быть логически активированы.
— Рудольф Вилле,Данные в примере взяты из семантического полевого исследования, в котором различные виды водоемов систематически классифицировались по их атрибутам. Для этого здесь он был упрощен.
Таблица данных представляет формальный контекст, линейная диаграмма рядом с ней показывает ее концептуальную решетку. Формальные определения приведены ниже.
| водоемы | атрибуты | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| временные | текущие | естественные | застойный | постоянный | морской | ||||
| объекты | канал | X | X | ||||||
| канал | X | X | |||||||
| лагуна | X | X | X | X | |||||
| озеро | X | X | X | ||||||
| маар | X | X | X | ||||||
| лужа | X | X | X | ||||||
| водоем | X | X | X | ||||||
| бассейн | X | X | X | ||||||
| водохранилище | X | X | |||||||
| река | X | X | X | ||||||
| ручей | X | X | X | ||||||
| русло | X | X | X | ||||||
| море | X | X | X | X | |||||
| поток | X | X | X | ||||||
| карьер | X | X | X | ||||||
| поток | X | X | X | ||||||
| ручей | X | X | X | ||||||
Линейная диаграмма, соответствующая формальным телам контекста вода слева Приведенная выше линейная диаграмма состоит из кругов, соединяющих отрезков линий и меток. Круги представляют собой формальные понятия. Строки позволяют считывать иерархию подконцептов-суперконцептов. Каждый объект и имя атрибута используется в качестве метки на схеме ровно один раз, с объектами ниже и атрибутами выше концептуальных кругов. Это делается таким образом, что к атрибуту можно получить доступ из объекта по восходящему пути тогда и только тогда, когда объект имеет атрибут.
На показанной диаграмме, например, объект-резервуар имеет атрибуты неизменный и постоянный, но не имеет атрибутов временный, текущий, естественный, морской. Соответственно, лужа имеет характеристики временное, застойное и естественное.
Исходный формальный контекст может быть восстановлен на основе помеченной диаграммы, а также формальных концепций. Объем концепции состоит из тех объектов, от которых восходящий путь ведет к кругу, представляющему концепцию. Намерение состоит из тех атрибутов, к которым есть восходящий путь от этого концептуального круга (на схеме). На этой диаграмме концепция непосредственно слева от метки резервуара имеет намерение застойное и естественное, а также представляет собой лужу, маар, озеро, пруд, каровое озеро, бассейн, лагуну и море.
Формальный контекст - это тройка K = (G, M, I), где G - это набор объектов, M - это набор атрибутов, а I G × M - это бинарное отношение, называемое инцидентностью, которое выражает, какие объекты имеют какие атрибуты. Для подмножеств A ⊆ G объектов и подмножеств B ⊆ M атрибутов определяется два оператора вывода следующим образом:
A '= {m ∈ M | (g, m) ∈ I для всех g ∈ A}, т.е. набор из всех атрибутов, общих для всех объектов из A, и двойственно
B '= {g ∈ G | (g, m) ∈ I для всех m ∈ B}, т. е. набор из всех объектов, имеющих все атрибуты из B.
Применение одного оператора вывода, а затем другого составляет два операторы закрытия :
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) является формальным понятием именно тогда, когда:
Для вычислительных целей формальный контекст может быть естественным образом представлен как (0,1) -матрица K, в которой строки соответствуют объектам, столбцы соответствуют атрибутам, и каждая запись k i, j равна 1, если «объект i имеет атрибут j». В этом матричном представлении каждое формальное понятие соответствует максимальной подматрице (не обязательно смежной), все элементы которой равны 1. Однако ошибочно рассматривать формальный контекст как логический, потому что отрицание инцидентности ("объект g имеет, а не имеет атрибута m ") концепт не формируется таким же образом, как определено выше. По этой причине значения 1 и 0 или ИСТИНА и ЛОЖЬ обычно избегают при представлении формальных контекстов, а для выражения инцидентности используется такой символ, как 
Концепты (A i, B i) контекста K могут быть (частично) упорядоченный включением экстентов или, что то же самое, двойным включением намерений. Порядок ≤ концептов определяется следующим образом: для любых двух концептов (A 1, B 1) и (A 2, B 2) из K, мы говорим, что (A 1, B 1) ≤ (A 2, B 2) точно когда A 1 ⊆ A 2. Эквивалентно (A 1, B 1) ≤ (A 2, B 2) всякий раз, когда B 1 ⊇ B 2.
В этом порядке каждый набор формальных понятий имеет наибольшее общее подконцепт или встречается. Его экстент состоит из тех объектов, которые являются общими для всех экстентов набора. По сути,, каждый набор формальных концепций имеет наименее общий суперконцепт, цель которого включает в себя все атрибуты, присущие всем объектам этого набора концептов.
Эти операции встречи и соединения удовлетворяют аксиомам, определяющим решетку, фактически полную решетку. Наоборот, можно показать, что всякая полная решетка является решеткой понятий некоторого формального контекста (с точностью до изоморфизма).
Реальные данные часто даются в форме таблицы атрибутов объекта, где атрибуты имеют «значения». Формальный концептуальный анализ обрабатывает такие данные, преобразовывая их в основной тип («однозначного») формального контекста. Метод называется концептуальным масштабированием.
Отрицание атрибута m - это атрибут ¬m, протяженность которого является просто дополнением экстента m, то есть с (¬m) '= G \ m'. Как правило, не предполагается, что отрицательные атрибуты доступны для формирования концепции. Но пары атрибутов, которые являются отрицанием друг друга, часто встречаются естественным образом, например, в контекстах, полученных из концептуального масштабирования.
Для возможных отрицаний формальных понятий см. Раздел алгебры понятий ниже.
Следствие A → B связывает два набора атрибутов A и B и выражает, что каждый объект, обладающий каждым атрибутом из A, также имеет каждый атрибут из B. (G, M, I) - формальный контекст, а A, B - подмножества множества атрибутов M (т. Е. A, B ⊆ M), то импликация A → B верна, если A ′ ⊆ B ′. Для каждого конечного формального контекста набор всех допустимых импликаций имеет каноническую основу, неизбыточный набор импликаций, из которого можно вывести все валидные импликации путем естественного вывода (правила Армстронга ). Это используется в исследовании атрибутов, методе получения знаний, основанном на значениях.
Формальный концептуальный анализ имеет сложные математические основы, что делает эту область универсальной. В качестве базового примера мы упоминаем отношения стрелок, которые просты и легко вычисляются, но очень полезны. Они определяются следующим образом: для 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.
Поскольку могут быть связаны только неинцидентные пары объект-атрибут, эти отношения могут быть удобно записаны в таблице, представляющей формальный контекст. Многие свойства решетки можно определить по стрелочным соотношениям, включая дистрибутивность и некоторые ее обобщения. Они также раскрывают структурную информацию и могут использоваться для определения, например, отношений конгруэнтности решетки.
Анализ временных понятий (TCA) является расширением анализа формальных понятий (FCA), направленным на концептуальное описание временных явлений. Он обеспечивает анимацию в решетках понятий, полученных из данных об изменяющихся объектах. Он предлагает общий способ понимания изменения конкретных или абстрактных объектов в непрерывном, дискретном или гибридном пространстве и времени. TCA применяет концептуальное масштабирование к временным базам данных.
В простейшем случае TCA рассматривает объекты, которые изменяются во времени, как частица в физике, которая каждый раз находится точно в одном месте. Это происходит в тех временных данных, где атрибуты «временной объект» и «время» вместе образуют ключ базы данных. Затем состояние (временного объекта в определенный момент времени в представлении) формализуется как некое объектное понятие формального контекста, описывающего выбранный вид. В этом простом случае типичная визуализация временной системы - это линейная диаграмма решетки понятий представления, в которую встроены траектории временных объектов.
TCA обобщает вышеупомянутый случай, рассматривая временные базы данных с произвольным ключом. Это приводит к представлению о распределенных объектах, которые в любой момент времени находятся, возможно, во многих местах, например, в зоне высокого давления на карте погоды. Понятия «временные объекты», «время» и «место» представлены как формальные понятия в масштабах. Состояние формализуется как набор объектных понятий. Это приводит к концептуальной интерпретации идей частиц и волн в физике.
Существует ряд простых и быстрых алгоритмов для генерации формальных концепций, а также для построения концепций и навигации по ним. решетки. Для обзора см. Кузнецов и Обьедков или книгу Гантера и Обьедкова, где также можно найти некоторый псевдокод. Поскольку количество формальных концепций может быть экспоненциальным по отношению к размеру формального контекста, сложность алгоритмов обычно указывается в зависимости от размера вывода. С концептуальными решетками из нескольких миллионов элементов можно без проблем обращаться.
Многие программные приложения FCA доступны сегодня. Основное назначение этих инструментов варьируется от создания формального контекста до формального интеллектуального анализа и создания решетки понятий данного формального контекста и соответствующих импликаций и правил ассоциации. Большинство этих инструментов представляют собой академические приложения с открытым исходным кодом, например:
Формальный контекст естественным образом можно интерпретировать как двудольный граф. Формальные понятия тогда соответствуют максимальным бикликам в этом графе. Таким образом, математические и алгоритмические результаты анализа формальных понятий могут быть использованы в теории максимальных биклик. Понятие двудольной размерности (дополненного двудольного графа) переводится в понятие размерности Феррерса (формального контекста) и размерности порядка (решетки понятий) и имеет приложения, например, для логической матричной факторизации.
Учитывая числовую таблицу данных атрибутов объекта, цель бикластеризации состоит в том, чтобы сгруппировать вместе некоторые объекты, имеющие похожие значения некоторых атрибутов. Например, в данных об экспрессии генов известно, что гены (объекты) могут иметь общее поведение только для подмножества биологических ситуаций (атрибутов): нужно соответственно создавать локальные паттерны для характеристики биологических процессов, последние, возможно, должны перекрываться, поскольку ген может участвовать в нескольких процессах. То же самое относится и к рекомендательным системам, в которых интересуются локальными шаблонами, характеризующими группы пользователей, которые в значительной степени разделяют почти одинаковые вкусы для подмножества элементов.
Бикластер в двоичной таблице данных атрибутов объекта - это пара (A, B), состоящая из максимального по включению набора объектов A и максимального по включению набора атрибутов B, такая что почти все объекты из A имеют почти все атрибуты из B, и наоборот.
Конечно, формальные концепции можно рассматривать как «жесткие» бикластеры, где все объекты имеют все атрибуты, и наоборот. Следовательно, неудивительно, что некоторые определения бикластера, взятые из практики, являются просто определениями формального понятия.
Бикластер схожих значений в числовой таблице данных атрибута объекта обычно определяется как пара, состоящая из набор объектов с максимальным включением и набор атрибутов с максимальным включением, имеющие аналогичные значения для объектов. Такая пара может быть представлена в виде прямоугольника максимального включения в числовой таблице с перестановками строк и столбцов по модулю. В нем было показано, что бикластеры одинаковых значений соответствуют триконцептам триадного контекста, где третье измерение задается шкалой, которая представляет числовые значения атрибутов двоичными атрибутами.
Этот факт можно обобщить на n-мерный случай, когда n-мерные кластеры схожих значений в n-мерных данных представлены n + 1-мерными концепциями. Это сокращение позволяет использовать стандартные определения и алгоритмы из многомерного анализа концепций для вычисления многомерных кластеров.
В теории пространств знаний предполагается, что в любом пространстве знаний семейство состояний знаний замкнуто на объединение. Таким образом, дополнения состояний знаний образуют закрывающую систему и могут быть представлены как экстенты некоторого формального контекста.
Анализ формальных понятий можно использовать как качественный метод анализа данных. С самого начала FBA в начале 1980-х исследовательская группа FBA в Техническом университете Дармштадта приобрела опыт более чем в 200 проектах с использованием FBA (по состоянию на 2005 г.). Включая области: медицина и клеточная биология, генетика, экология, программная инженерия, онтология, информация и библиотечные науки, офисное администрирование, право, лингвистика, политология.
Многие другие примеры, например, описано в: Анализ формальной концепции. Основы и приложения, доклады на регулярных конференциях, таких как: Международная конференция по анализу формальных понятий (ICFCA), Концептуальные решетки и их приложения (CLA) или Международная конференция по концептуальным структурам (ICCS).
