Нахождение замыкания признаков как одна из наиболее часто возникающих задач во время построения базисов импликаций. Сравнительный анализ показателей времени работы трансверсального алгоритма при использовании различных методов минимизации базиса.
Аннотация к работе
Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Высшая школа экономики» Выполнил студент группы 123, 4 курса, Белов Павел ДмитриевичАнализ формальных понятий позволяет выявлять закономерности в данных и находить взаимоотношения между признаками объектов. Более формально, контекст K представляет собой тройку (G, M, I), где G - множество объектов, M - множество признаков, I GXM - бинарное отношение между объектами и признаками. Все признаки в данной модели бинарные, то есть ?обладает ли объект данным свойством?. Другими словами, данная запись означает следующее: ?Для всех объектов из множества выполняется, что если в объекте присутствуют все признаки из Однако, количество импликаций в данных может быть очень большим, поэтому появляется задача - найти множество, эквивалентное всем импликациям, выполняющимся в данном контексте.В ходе данной работы были реализованы и протестированы два алгоритма - Closure и LINCLOSURE. Основная идея Closure заключается в том, что мы проходим по базису и пытаемся расширить текущее множество с помощью каждой импликации. Теоретическая сложность данного алгоритма квадратичная, так как в худшем случае мы на каждом шаге будем использовать только одну импликацию. A Алгоритм LINCLOSURE обладает линейной от количества импликаций в базисе сложностью. 6 импликации мы храним количество ссылок, и расширяя постепенно на-ше множество, применяем новые импликации, который стали доступны после предыдущих.В самом деле, иногда можно быстро построить базис импликаций, но с большим числом импликаций, чем базис Дюкенна-Гига. В таком случае можно применить алгоритм минимизации базиса и получить базис Дюкенна-Гига. В алгоритме мы перебираем все импликации из L и каждую импликацию сначала стараемся расширить с помощью других импликаций из базиса, после чего удаляем из L импликации, не добавляющие новой информации. Данный алгоритм обладает сложностью O(JLJ3), так как он проходит один раз по всем импликациям из L и на каждом шаге вызывает Closure(), который обладает сложностью O(JLJ2). Алгоритм рассматривает импликации одну за одной и пробует построить контр-пример к каждой из них.Для ускорения работы алгоритмов было принято решение использовалать библиотеку Boost ([10]) и, в частности, контейнер Boost::dynamic bitset. По результатам профилирования удалось оптимизировать работу с памятью в алгоритмах и ускорить их засчет этого. Было проведено тестирование всех алгоритмов по скорости работы на реальных данных. 6.3: Время работы инкрементального алгоритма на различных наборах данных. трансверсалям в данном алгоритме, растет очень быстро с увеличением размера формального контекста. 6.6: Время работы трансверсального алгоритма на основе минимального покрытия при множественной минимизации. рования программы, реализующей данный алгоритм, выяснилось, что около 90% времени работы уходило на минимизацию базиса.В ходе выпускной квалификационной работы были исследованы различные алгоритмы для построения базиса импликаций Дюкенна-Гига и связанных с этим подзадач. На языке C мною были написаны эффективные реализации алгоритмов построения замыкания признаков, минимизации базиса и непосредственно построения базиса. Кроме того, были разработаны и проделаны многочисленные оптимизации как на техническом (работа с памятью, эффективное использование особенностей С ), так и на алгоритмическом уровнях. Babin, M.A., Kuznetsov, S.O.: Recognizing pseudo-intents is CONP-complete. Beeri, C., Bernstein, P.: Computational problems related to the design of normal form relational schemas.