ПРОГРАММИРОВАНИЕ, 2012, No 5, с. 18-34
= ВОСЬМАЯ ЕРШОВСКАЯ КОНФЕРЕНЦИЯ ПО ИНФОРМАТИКЕ (ПСИ'11) -
УДК 681.3.06
ВЕРОЯТНОСТНОЕ ОБОБЩЕНИЕ ФОРМАЛЬНЫХ ПОНЯТИЙ
© 2012 г. Е.Е. Витяев*, А.В. Демин**, Д.К. Пономарев**
*Институт математики им. С.Л.Соболева СО РАН 630090 Новосибирск, пр. Академика Коптюга, 4 **Институт систем информатики им. А.П.Ершова СО РАН 630090 Новосибирск, пр. Академика Лаврентьева, 6 E-mail: vityaev@math.nsc.ru, alexandredemin@yandex.ru, ponom@iis.nsk.su
Поступила в редакцию 14.12.2011
В работе предлагается индуктивный вероятностный подход к «анализу формальных понятий» (англ. Formal Concept Analysis), в котором рассматривается вероятность на «формальных контекстах»; определяются вероятностные формальные понятия, обладающие прогностической силой - неклассифицированные объекты возможно отнести к ранее обнаруженным вероятностным формальным понятиям; из вероятностных формальных понятий исключаются случайные признаки; вероятностные формальные понятия устойчивы к шумам в данных. Приведен результат машинного эксперимента, в котором формальные понятия (в их стандартном определении из «анализа формальных понятий») были искажены наложением случайного шума, а затем восстановлены с помощью обнаружения вероятностных формальных понятий.
1. ВВЕДЕНИЕ
В «анализе формальных понятий» [1, 2] (Formal Concept Analysis, в дальнейшем сокращенно FCA) «формальные понятия» являются классификационными единицами, возникающими в процессе анализа реляционных данных. Такого рода данные рассматриваются в виде таблицы («формального контекста») над множествами объектов G и признаков M, в которой строки именованы названиями объектов из G, а столбцы - названиями признаков из M. При этом каждая клетка (i, j) таблицы содержит значение 1 в том и только том случае, если i-й объект имеет признак j. В процессе анализа объекты группируются в классы таким образом, чтобы в один класс попали объекты, имеющие некоторый общий набор признаков, и чтобы это множество объектов было максимально, т.е. никакой другой объект вне этого класса ровно этим же набором признаков не обладал. Известно, что получаемые таким образом пары <группа объектов, набор признаков> можно естественным образом упорядочить и представить в виде полной решетки.
Анализ формальных понятий тесно связан с исследованиями по ассоциативным правилам (Association Rules), которые интенсивно изучаются в направлении Data Mining. Например, известно [3], что, имея множество всех формальных понятий заданного контекста, можно построить базис для нахождения ассоциативных правил в данном контексте.
Цель ассоциативных правил - обнаружить все взаимоотношения между признаками в реляционных данных. Изначально эта задача возникла из рассмотрения покупательской корзины и проблемы обнаружения взаимосвязей продаж различных групп товаров. Размерность реальных баз данных может быть очень велика, поэтому и количество обнаруживаемых правил может быть потенциально очень велико и является таковым на практике. Отбор «значимых» ассоциативных правил - довольно нетривиальная задача, в связи с которой возникает проблема оценки «качества» правил [4]. Один из подходов к решению этой проблемы состоит в определении статистических оценок ассоциативных правил [4, 5].
Если мы хотим, кроме того, чтобы правила имели прогностическую силу, то мы попадаем в другую парадигму методов Data Mining -в парадигму индуктивного вывода правил. Как отмечается в работе [6], у этих двух подходов (обнаружения ассоциативных правил и индуктивного вывода правил) разные задачи. Задача индуктивного вывода правил состоит в обеспечении предсказаний, а ассоциативных правил - в предоставлении обзора данных для пользователя.
Парадигма «анализа формальных понятий» родственна ассоциативным правилам и заключается в обнаружении на реляционных данных полного множества классификационных единиц и их взаимосвязей. При этом не рассматриваются вопросы, которые могут возникнуть в индуктивной парадигме, а именно:
1. предсказательной способности этих понятий - возможности отнесения нового объекта к данному понятию;
2. устойчивости понятия относительно возможных ошибок в данных;
3. минимальности описания понятий - исключения из описания понятия случайных признаков.
Индуктивной парадигмы для «анализа формальных понятий» в настоящее время не существует. Отметим близкую работу [7], в которой основные объекты FCA переформулируются в терминах вероятностной логики и используются для формулировки новых паттернов. Однако при этом само их определение в рамках FCA не изменяется.
Задача данной работы - предложить индуктивное обобщение «анализа формальных понятий» и дать ответы на вопросы 1-3, сформулированные для индуктивной парадигмы. С этой целью мы рассматриваем два варианта введения вероятности: на семействах формальных контекстов, как множестве возможных миров (раздел 3), а также на множестве объектов одного контекста, как генеральной совокупности (раздел 4). Известно, что в рамках формальной логики вероятность может быть введена двумя этими способами: на множестве возможных
миров (моделей) и на области (основном множестве конкретной модели) [8]. Чтобы перейти к предсказательному определению формального понятия, мы берем за основу его определение в РСЛ через неподвижные точки импликаций, истинных на данных. Мы обобщаем стандартное используемое в РСЛ понятие истинности импликации на данных с помощью некоторой оценки истинности, основанной на вероятностной мере, но так, чтобы, во-первых, сохранилась преемственность с исходным определением формального понятия, а, во-вторых, чтобы эти импликации следовали не идее ассоциативных правил (найти все возможные ассоциации), а следовали идее индуктивных правил - минимизации содержания понятий и исключения случайных признаков. После этого, по аналогии с определением формального понятия в РСЛ, мы определяем вероятностное формальное понятие через неподвижные точки вероятностных импликаций.
В результате мы получаем индуктивное вероятностное определение формального понятия, которое:
• относится к объектам некоторой генеральной совокупности;
• в стандартных ограничениях совпадает с исходным определением формального понятия в РСЛ;
• обладает прогностической силой - новые объекты возможно отнести к ранее обнаруженным вероятностным формальным понятиям;
• минимизирует описание формального понятия путём исключения из импликаций случайных признаков;
• устойчиво к определенным шумам в данных.
В разделе 2 приводятся все необходимые определения и результаты «анализа формальных понятий» для прочтения данной статьи. Для демонстрации вводимых нами определений в конце раздела 4 приводятся примеры машинных экспериментов по обнаружению вероятностных формальных понятий на данных.
2. ПРЕДВАРИТЕЛЬНЫЕ ОПРЕДЕЛЕНИЯ
Начнем с основных определений и результатов «анализа формальных понятий».
Определение 1. Формальным контекстом называется тройка (С,М,1), где О и М
- некоторые множества, а I С О х М -некоторое отношение между элементами О и М. Элементы О называются объектами контекста, а элементы М - атрибутами контекста. Формальный контекст назовем конечным, если О и М являются конечными множествами.
Далее для краткости мы опускаем слово «формальный» и будем называть тройки (О,М,1), указанные в определении, контекстами. Любой контекст можно представить в виде таблицы, аналогично тому, как было замечено во введении. Если (О, М, I) - контекст, то на подмножествах А С О, В С М определим операцию ' следующим образом:
А = {т е М IV д е А (д,т) е I},
В' = {д е О IV т е В (д,т) е I}.
Если д е О, то обозначение д' будет служить сокращением для множества {д}'.
Определение 2. Понятием в контексте (О,М, I) называется пара (А, В), где А С О, В С М, А' = В и В' = А. При этом множество А называется объемом, а В
- содержанием понятия (А, В).
Фактически «понятие» является классификационной единицей, группирующей объекты и атрибуты контекста.
Следующий простой факт будет многократно использоваться в доказательствах основных утверждений статьи:
Лемма 1. Для любого контекста (О,МД) и множеств Вг,В2 С М верно:
1. Вх С В2 =
2. Вг С В'(.
В2 С В'г
Определение 3. Определим (частичное) упорядочение ^ понятий контекста следующим образом: если (А1,В1) и (А2,В2) - понятия в некотором контексте, то полагаем (А1,В1) ^ (А2,В2), если Аг С А2 (или, что эквивалентно по лемме 1, если В2 С Вг).
Теорема. Отношение ^ порождает на множестве понятий контекста полную решетку, в которой инфимум и супремум подмножеств определяются, соответственно, следующим образом:
Л (А
з ,В,) = ( П А,, ( и В,)'')
V (Аз ,Вз) = ((иАз)'', П Вз).
Пример 1. Рассмотрим конечный контекст К = ({д1,д2,дз,д4}, {тьт2,тз,т4},!), представленный в табличном виде на рис. 1. Решетка всех понятий в контексте К представлена на этом же рисунке, каждый элемент решетки помечен множеством объектов и атрибутов, являющихся, соответственно, объемом и содержанием понятия.
Процедуры вычисления полной решетки понятий по заданному конечному контексту [9, 10] являются одними из ключевых алгоритмов в методе РСЛ. Фактически, они производят построение классификации объектов контекста в соответствии с указанными для них атрибутами и позволяют найти все существующие классы.
Если задан некоторый контекст К = (О, М, I), то можно говорить об истинности на К утверждений следующего вида: «все объекты, обладающие атрибутами В1 С М, имеют также множество атрибутов В2 С М». Поскольку все свойства контекста в определенном смысле симметричны относительно множеств О и М, то аналогичные утверждения можно сформулировать о подмножествах О: «все атрибуты, имеющие своими объектами А1 С О, также имеют своими объектами и А2 С О». Без ограничения общности мы будем рассматривать утверждения лишь первого
ложна на К, если не существует д £ С такого, что А С д. Назовем импликацию А ^ В тавтологией, если В С А.
Для контекста К = (С, М, I) будем обозначать множество всех импликаций на М, которые истинны на контексте К, через 1тр(К). Легко проверить, что подмножеством 1тр(К) является множество тавтологий, а также множе
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.