Диссертация (1137435), страница 5
Текст из файла (страница 5)
Такая информация может быть использована, как базис для различной маркетинговой деятельности, например скидочные акции или выборспособа расположения продуктов в магазине. В дополнение к описанному примеру анализа рыночной корзины, в настоящее время ассоциативныеправила используются и во многих других прикладных областях таких,как анализ пользования вебом и обнаружение взломов. Ассоциативныеправила определяются как пара непересекающихся множеств признаков(, ), ∩ = ∅ и записывается как → . Для того, чтобы выбрать интересные ассоциативные правила из всего множества ассоциативных правил, используются различные меры важности и интересности. Наиболееизвестные из них это достоверность и поддержка.
Поддержка ()множества признаков определяется, как доля транзакций(объектов) базы данных которые содержат . Достоверность ассоциативного правила → определяется, как ( → ) = ( ∪ )/(). Обычно ищутся только те ассоциативные правила, которые обладают заданнойподдержкой и достоверностью (заданными пользователем). Для поиска ассоциативных правил было предложено множество алгоритмов. Некоторыеиз самых известных – Apriori [27], Eclat [82], FP-Growth [60].В этой работе нас будут интересовать строгие правила, называемыеимпликациями. Импликацией можно считать ассоциативное правило с достоверностью 1 (100%).
В отличие от ассоциативных правил для импликаций существует каноническое сжатое представление – минимальный набор32импликаций (по количеству импликаций), из которого следуют все остальные импликации (см. аксиомы Армстронга). Такой называют минимальным базисом импликаций. Строгие правила интересны для аналитическихобластей, таких как профилирование данных, а также в тех областях анализа реляционных баз данных, где имеют значение функциональные зависимости.1.3.Минимальная модель знаний о предметной области: минимальный базис импликацийИмпликативные зависимости на признаках в объектно-признаковомпредставлении данных помогают эксперту лучше понимать суть скрытыхв данных закономерностей. Методы анализа формальных понятий (АФП)[54] предлагают вместо всех возможных импликаций рассматривать только минимальное подмножество импликаций, из которого все остальные импликации могут быть выведены по правилам вывода Армстронга (см. Раздел 2.1).
Это минимальное подмножество импликаций называется каноническим базисом импликаций (или базис Дюкена-Гига) [42, 54].Для поиска базиса импликаций существует множество алгоритмов изразличных научных сообществ. В сообществе АФП существует несколькоалгоритмов для построения базисов импликаций. Алгоритм Гантера [50]основан на том, что множество псевдосодержаний вместе с множествомсодержаний образуют систему замыканий поэтому, если научиться вычислять оператор замыкания, то можно породить все множество псевдосодержаний вместе с множеством содержаний. Время работы этого алгоритма(| |(||+||)(||+|B(, , )|)), где || – размер минимального базиса,33а |B(, , )| – количество замкнутых множеств.
Поскольку количествосодержаний может быть больше в экспоненциальное число раз чем количество псевдосодержаний[70], то время работы этого алгоритма в худшемслучае экспоненциально от размера выхода.Алгоритм Объедкова-Дюкена [42] основан на той же идее, что и алгоритм Гантера, но за счет более быстрого способа вычисления оператора насыщаения на практике их алгоритм может работать намного быстрее.
Этоталгоритм начиная с пустого множества признаков добавляет новые признаки по одному и пересчитывает текущее множество псевдосодержанийвместе с множеством содержаний. Оценка времени работы этого алгоритматакая же, как и у алгоритма Гантера – (| |(||+||)(||+|B(, , )|)).Алгоритм Рисселя-Дистеля-Брокмана [37] ищет все собственные посылки формального контекста за квазиполиномиальное от выхода время,используя алгоритм генерации минимальных трансверсалей гиперграфа.Отметим, что для задачи поиска минимальных трансверсалей гиперграфасуществует квазиполиномиальный от размера выхода алгоритм[49]. Собственные посылки задают базис импликаций (левые части импликаций),но не обязательно минимальный. Существуют примеры контекстов, когдаразмер минимального базиса импликаций в экспоненциальное число разменьше, чем число собственных посылок [37].
В экспериментах на некоторых реальных данных этот алгоритм показал лучшие результаты чемалгоритм Гантера [37].В сообществе реляционных баз данных импликации соответствуютфункциональным зависимостям, минимальные базисы импликаций называют минимальными покрытиями функциональных зависимостей, а вместо34формального контекста выступает реляционное отношение ([18, 69]). Отметим, что в данном случае число объектов в соответствующем формальном контексте будет квадратичным по отношению к количеству кортежей(строчек) в реляционной таблице.В отличие от случая, когда система замыканий задана формальнымконтекстом в случае, когда система замыканий задана набором импликаций(не минимальным) для поиска минимального базиса импликаций известны полиномиальные от выхода алгоритмы.
Так например в [19] был представлен квадратичный алгоритм (от размера входа) для построения минимального покрытия функциональных зависимостей для данного множества функциональных зависимостей. Похожий алгоритм в терминах АФПбыл предложен в [90].Другой взгляд на ту же проблему предлагает теория хорновских моделей.
Хорновской моделью называют булев вектор, который выполняетданную хорновскую КНФ. Хорновские модели образуют системы замыканий в том смысле, что булев вектор полученной покомпонентной операцией конъюнкции (называют пересечением) также является моделью. В терминах АФП хорновские модели соответствуют содержаниям формальногоконтекста. Характеристической моделью называют такую модель, котораяне может быть получения пересечением других моделей, в терминах АФПэто соответствует строчке редуцированного контекста(содержание супремум неразложимого элемента решетки).В статье Англуин-Фрейзер-Питт [28] был предожен алгоритм, который при наличии двух оракулов первый из которых может проверять эквивалентность хорновских КНФ и выдавать контрпример (булев набор на35котором первая КНФ не равна второй КНФ) в случае неэквивалентности, авторой оракул проверяет выполняется ли обучаемая(скрытая) хорновскаяКНФ на данном булевом наборе, может получить эквивалентную хорновскую КНФ за полиномиальное от выхода время.Позже, Хардон в статье [64] исследовал задачу поиска характеристических моделей по хорновской КНФ и задачу получения хорновскойКНФ по заданным характеристическим моделям.
Ссылаясь на результатАнгулин-Фрейзера-Питта, Хардон доказал, что эти задачи полиномиальноэквивалентны, в том смысле, что, если одна(любая) из них может бытьрешена за полиномиальное время, то и другая тоже. Более того, Хардонпоказал, что эти задачи полиномиально эквивалентны задаче разрешения –по данной хорновской КНФ и набору характеристических моделей(данномукак набор булевых векторов) нужно проверить задают ли они одну и туже модель или нет. На языке АФП это означает, что задача поиска минимального базиса импликаций (или базиса который в полиномиальное числораз больше минимального) формального контекста полиномиально эквивалентна задаче построения нередуцируемого контекста (супреумум неразложимые элементы решетки понятий) по набору импликаций. И что обе этизадачи полиномиально эквиваленты задаче разрешения – по данному формальному контексту и данному набору импликаций определить задают лиони одну и ту же систему замыканий или нет.
Также, Хардон показал,что эти задачи не проще, чем задача поиска минимальных трансверсалейпростого гиперграфа (эквивалентно монотонной булевой дуализации).Существует несколько работ связанных с приближенном поискомстрогих зависимостей в данных. В [65] Кивинен и Маннила рассмотрели36несколько мер ошибок функциональных зависимостей.К сожалению все известные алгоритмы для поиска минимального базиса импликаций в худшем случае работают экспоненциальное от размеравыхода время.1.4.Задачи и алгоритмы построения гипотезПервая версия ДСМ-метода автоматического порождения гипотезбыла описана в работе [20].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
