Теория машинного обучения в решетках формальных понятий

• Автор: Кузнецов, Сергей Олегович
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 147 с. : ил

Введение. Анчнз формальных понятий АФП. Машинное обучение. Гипотгаы и классификации теоретике решеточная и теоретикографовая интерпретации, связь с родственными понятиями. Теоретикографовая интерпретация гипотся. Гипотезы и импликации в АФП. Гипотезы, решетки понятий и деревья решений. Число всех формальных ионятий. Число минимальных гипотез. Сложность классификации и проверки критерия достаточного основания. Алгоритм порождения решетки понятий. Вычисление классификаций и проверка критерия достаточного основания. Мотивация и прецеденты. Изменение устойчивости с ростом числа примеров. Узорные структуры и их проекции. Вычисления в узорных структурах. Проекции узорных структур. Приложения в области графов. Список литературы. Отметим сшс одно родственное направление в области формализации понятий с помощью решеток. В работе Чечкин вводит определение сведения как обобщенного признака объектов. В отличии от анализа формальных понятий, здесь рассматриваются не только замкнутые множества признаков и объектов, в результате чего совокупность возможных сведений образует булевую решетку понятий относительно операций пересечения, объединения и разности на множествах объектов, соответствующих признакам.


Порядковым фильтром идеалом решетки Ь называется подмножество X С такое, что если а X, Ъ Ь и Ь а, то Ь Л соответственно, а 6 А, Ь Ь и Ь а, то Ь X. Л х V у х V х Л у х поглощение. В полурешетках выполняются свойства для соответствующих операций, т. Л идемиотентна, ассоциативна и коммутативна в нижней полурешетке, а операция V идемпотентна, ассоциативна и коммутативна б верхней полурешетке. Решетка называется полной, если у каждого подмножества его элементов есть супремум и инфимум. Очевидно, что всякая конечная решетка является полной. Следующие понятия играют ключевую роль для связи теории решеток и анализа формальных понятий. Элемент решетки а называется Лнераэложимым или неразложимым о пересечение если из а ЬЛс следует а Ь или а с. Ь V с следует а Ь гои а с. Подмножество И полной решетки Ь называется инфимумплотным супремумплотным, если Ь ЛеХ С соответственно, Ь УххХ С . Следующие определения можно найти, например, в 2, гои . Пусть Р, и , частично упорядоченные множества. Пара таких отображений называется соответствием Галуа между частично упорядоченными множества. Пусть 7 и М множества, называемые соответственно множествами объектов и признаков, а С С х М отношение. Это отношение интерпретируется следующим образом для д 6 О, т 6 М тяеет место дт если объект д обладает признаком т. Тройка К 6 М, I называется формалънш контекстом. А щ А дт для всех д 6 . В1 д 7 дт для всех т В. Нетрудпо видеть, что эта пара отображений задает соответствие Галуа между частично упорядоченными множествами 2е. С и 2м, С см. А дизъюнктнохс объединении 7 и А, т. А . А С С, то А С С иэотонность. Множество А такое, что А А называется замкнутым 2. Л называется формальным понятие контекста К с ДОор. Ку содержанием В. Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами. Заметим, что определение понятия в виде такой пары находится в соответствии с логикофилософской традицией, например очень близко к представлению о понятии в логике ПорРояля XVII век. Как было показано в 2, подмножества произвольного множества, замкнутые относительно заданной па нем операции замыкания, образуют полную решетку. К. Болес того, верно н обратное утверждение Если Ь полная решетка, Г 2А для некоторого контекста К , М, тогда и только тогда, когда существуют отображения у. С и р М Ь такие, что множество уС супремумплотно в Ь, р инфимумпдотно в Ь, а д1т эквивалентно уд рт для всех д С и т М. В частности. Объектным понятием называется понятие вида ,, где д С. Аналогичным образом, признаковм. П, где т М. Строчноприведенным называется такой формальный контекст, в котором всякое объектное понятие является Унераэложимым. Ттолбцевопривеенньш называется такой формальный контекст, в котором всякое признаковое понятие является Лнеразложимым. Следующий круг определений и свойств связан с имплккапиями на множествах признаков. Для А, В С М имеет место имтмыкацыл на признаках А В, если А С В или В С А, т. В. Аналогичным образом определяются импликации на объектах. Там, где специально не оговорепо противного, под импликациями будут пониматься импликации на признаках. Наличие импликации А В в контексте К соответствует тому, что в диаграмме решетки К формальное понятие Л, ,4 находится ниже форматного понятия В В4. Импликации формального контекста удовлетворяют следующим аксиомам Армстронга первое упоминание этих аксиом можно найти в , см. X, У, 2
2. Если X У и У и 2 4 IV то X и 2 IV. Помимо формальных контекстов, определенных выше двузначных контекстов в АФИ используются т. Представление многозначных контекстов двузначными называется школнробамнеж. Возможные виды шкалирования рассмотрены в . Заметим, что в середине х годов О. М. Поляковым и В. В. Дунаевым , ,, была предложена модель таксономической я мерономической иерархии, математически эквивалентная модели, основанной на формальных понятиях. Был доказан ряд результатов, аналогичных доказанным несколько ранее в сообществе АФП, папример, представимость произвольной полной решетки решеткой таксономий т. АФП, теоремы о произведениях решеток и соответствующих разложениях.