Диссертация (1137435), страница 15
Текст из файла (страница 15)
Err. Mis. Mis. #Hyp. #Hyp.3031,0 10,0 49.7 54,69,824,02010,9 12,1 44.6 45,879,7134,01012,5 10,5 34.5 45,4 265,75270,0512,8 10,4 31.9 45,8389,75393,5∙ Err. – процент ошибочной классификации при использовании устойчивых гипотез с > 0, 65∙ Err. – процент ошибочной классификации при использовании классических гипотез∙ Mis. – процент неклассифицируемых объектов при использовании устойчивых гипотезс > 0, 65∙ Mis. - процент неклассифицируемых объектов при использовании классических гипотез∙ #Hyp. – среднее количество минимальных устойчивых гипотез по 4 базам данных∙ #Hyp.
– среднее количество минимальных классических гипотез по 4 базам данныхТаблица 4.3. Результаты классификации токсичности молекул.Как видно из результатов компьютерных экспериментов, использование устойчивых гипотез повышает качество покрытия (процент примеров, которые удалось классифицировать), но немного увеличивает процентошибочной классификации (уменьшается качество классификации).
Если113сравнить результаты из таблицы 4.3 с результатами из таблицы 4.1, томожно заметить, что покрытие у распределенного обучения гипотезам значительно выше покрытия устойчивых гипотез, но немного проигрывает вкачестве классификации.1145. Комплекс программ5.1.Программный комплекс CordietПрограммный комплекс Cordiet-FCA [88] разрабатывается отделени-ем прикладной математики и информатики НИУ ВШЭ (ОПМИ).На текущий момент система Cordiet-FCA представляется локальнымприложением под операционную систему Windows.
Эта версия системы использует локальное XML-хранилище и встроенное окружение для проведения исследований с профайлером, исполнителем запросов, редакторомонтологий и множеством решателей и визуализаторов. Основные решатели могут строить решетки и подрешетки, искать ассоциативные правила иимпликации, вычислять индексы устойчивости формальных понятий, меры сходства для контекстов и понятий, и.т.д.Cordiet-FCA использовался для решения некоторых прикладных задач, связанных с медицинской информатикой и криминальными расследованиями.5.2.Программная реализация построения базисов импликацийАлгоритмы построения и тестирования базисов импликаций были ре-ализованы на языке C++ (около 1000 строк кода) в среде MS Visual Studio2010 с использованием стандартной библиотеки STL.Эти реализации вошли в комплекс программ, встроенный в программ-115ную систему Cordiet-FCA и могут быть использованы для построения приближенного базиса импликаций.Структура программы построения и тестирования базисов импликаций имеет следующий вид:1.
В файлах mset.h и mset.cpp (приложение 1.1) реализованы структурыи функции для работы с множествами, представленными спискамиэлементов.2. В файлах implications.h и implications.cpp (приложение 1.2) реализованы структуры и функции для работы с импликациями. Функцияlin_closure(const std::vector<Implication>& implications, const mset&X) вычисляет замыкание множества X в базисе implications, используя алгоритм linclosure [19]3.
В файлах context.h и context.cpp (приложение 1.3) реализован классContext для работы с формальными разреженными контекстами.4. В файлах min_transversals.h и min_transversal.cpp (приложение 1.4)реализован алгоритм поиска минимальных трансверсалей гиперграфа из работы [63], который используется для поиска минимальныхгенераторов и собственных посылок.5. Вфайлахзованangluin.hалгоритмФункцияипоискаangluin.cpp(приложениеприближенногоstd::vector<Implication>базиса1.5)реали-импликаций.get_approximate_base(constsparse_context::Context& K, int no_steps) возвращает приближенный базис импликация контекста K, после no_steps шагов.1166. В файлах proper_premise.h и proper_premise.cpp (приложение 1.6)реализован алгоритм поиска собственных посылок из работы [37].5.3.Программная реализация алгоритма вычисления оператора замыкания общих содержанийБыли реализованы две версии алгоритма вычисления оператора за-мыкания общих содержаний – для случая, когда контекст задан бинарнойматрицей и случая, когда контекст задан списками признаков.Оба алгоритма были реализованы на языке C++ (около 170 строк)в среде MS Visual Studio 2010 с использованием стандартной библиотекиSTL.Реализация вошла в комплекс программ, встроенный в программнуюсистему Cordiet-FCA и может быть использована для анализа сходствабольших динамических массивов данных.Структура программы вычисления оператора замыканий общих содержаний имеет следующий вид:1.
В файле shared_closure.cpp (приложение 2.1) функция msetclosure(const std::vector<sparse_context::Context>& K, const mset&X) вычисляет оператор замыкания общих содержаний для случая когда контексты заданы списками признаков.2. В файлах shared_closure.h и shared_closure.cpp (приложение 2.1) реализована структура данных PQ (специальная приоритетная очередь,с поддержкой дополнительный операций), используемая алгоритмом_2.1175.4.Программная реализация распределенного обучения гипотезамАлгоритм распределенного обучения гипотезам был реализован наязыке C++ (около 300 строк) в среде MS Visual Studio 2010 с использованием стандартной библиотеки STL.Реализация вошла в комплекс программ встроенный в программнуюсистему Cordiet-FCA.Структура программы распределенного обучения гипотезам имеетследующий вид:1.
В файле JSM_test.cpp (приложение 3.1) функция vector<mset>find_shared_hypotheses(constvector<Context>&pK,constvector<Context>& nK) находит все общие гипотезы наборов положительных и отрицательных контекстов pK и nK, соответственно.2. ВфайлеJSM_test.cpp(приложение3.1)функцияmsetnext_closure_JSM(const mset& X, const Context& K) возвращает следующую гипотезу в лексикографическом порядке на объемахсоответствующих формальных понятий.3. В файле JSM_test.cpp (приложение 3.1) функция int classify(constvector<mset>& pH, const vector<mset>& nH, const mset& X) возвращает результат классификации X при использовании множества положительных гипотез pH и множества отрицательных гипотез nH.Данная функция возвращает 1, если результат классификации положителен, −1, если результат классификации отрицателен, и 0, есликлассификация неопределена.118ЗаключениеВ диссертационной работе приведен обзор методов поиска строгихзависимостей в данных.
В 2006 году участниками конференции ICFCA вЛенсе (Lens, Франция) был составлен список наиболее важных открытыхзадач в АФП. Одной из них была задача о сложности распознавания псевдосодержаний, которая была решена в данной диссертационной работе иопубликована в [31] (публикации, где рассматривалась данная задача исчиталась открытой: [74, 89, 90, 91, 92, 38]). Эта задача была также представлена как открытая на Дрезденской конференции по дискретной математике в 2002 году.В отличие от классического минимального базиса импликаций, длякоторого все известные алгоритмы построения имеют экспоненциальнуюоценку сложности, среднее время работы построения приближенного базиса импликаций полиномиально и оценивается как (| || | · (||| | +| || |) · −1 ), где – минимальный базис импликаций, а – параметрточности приближенного базиса импликаций.
Проведенные на реальныхданных эксперименты показали, что размер приближенного базиса былзначительно меньше (иногда в сотни раз).В работе было доказано, что если ̸= , то невозможно найтивсе минимальные ДСМ-гипотезы за полиномиальное от размера выходавремя. Модель распределенного обучения гипотезам показала значительное сокращение количества гипотез по отношению к числу ДСМ-гипотез в119стандартной постановке. Линейный по времени алгоритм вычисления оператора замыканий системы замыканий общих содержаний позволил быстроперечислять все общие гипотезы.В данной работе была доказана трудность аппроксимации индексаклассической устойчивости формальных понятий (с полиномиально ограниченной относительной ошибкой). Была предложена модель вероятностного индекса устойчивости формальных понятий, которая соответствуетаппроксимации классического индекса устойчивости с ограниченной абсолютной ошибкой и может быть вычислена за полиномиальное время. Проведенные эксперименты показали, что применение вероятностного индексаустойчивости, при использовании ДСМ-метода, уменьшает число неклассифицируемых объектов на ≈ 43% при увеличении количества ошибок классификации на ≈ 23% (число неклассифицируемых объектов, при использовании стандартных ДСМ-гипотез ≈ 46%).Основные результаты и выводы работы:1.
Результаты, связанные с базисами импликаций:1.1 Доказана трудноразрешимость (в терминах NP- и coNP-полноты итрудности) задач, связанных с вычислением классического минимального базиса импликаций.1.2 Предложена модель приближенного базиса импликаций формальногоконтекста, эффективный алгоритм его вычисления и программнаяреализация.2. Результаты, связанные с минимальными гипотезами:2.1 Доказана трудноразрешимость вычисления минимальных гипотез в120стандартной постановке.2.2 Предложена и экспериментально проверена модель распределенногообучения гипотезам – импликативных зависимостей для задачи машинного обучения.2.3 Предложен эффективный алгоритм поиска всех гипотез по распределенной обучающей выборке и его программная реализация.3.
Результаты, связанные с индексом устойчивости формальных понятийи гипотез:3.1 Предложена и экспериментально проверена модель оценивания гипотез и формальных понятий - индекс вероятностной устойчивости.3.2 Теоретически и экспериментально исследована сложность вычисления вероятностного индекса устойчивости, предложен эффективныйалгоритм и его программная реализация.121Литература1. Бабин М.А. О приближенном базисе импликаций // Научнотехническая информация.
Серия: Информационные процессы и системы, №8, С. 20–23, 2012.2. Бабин М.А., Кузнецов С.О. О теоретико-решеточной интерпретациизадач поиска гипотез и зависимостей // Научно-техническая информация. Серия: Информационные процессы и системы, №10, С. 18–22,2011.3. Бабин М.А., Кузнецов С.О. Связи между решетками понятий и сложность их вычисления // Труды МФТИ, том 4 №2(14), С. 73–80, 2012.4. Биркгоф Г. Теория решеток // М.: Наука, 1984.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
