Автореферат (1137434), страница 3
Текст из файла (страница 3)
В работе [В.Финн 1991] эти объекты называются неопределенными примерами, они могут12быть заданы контекстом K := ( , , ), соответствующий оператор Галуаобозначается через (·) .Гипотезы могут быть использованы для классификации неопределенныхпримеров: если содержание := { ∈ | (, ) ∈ }объекта ∈ содержит положительную и ни одной отрицательной гипотезы, то классифицируется положительно. Отрицательные классификацииопределяются аналогично. Если содержит гипотезы обоих знаков, то классификация противоречива. Если вообще не содержит гипотез, то классификация не определена. В этом случае можно применять методы другого типа,например, основанные на статистических подходах.В работе [С.
Кузнецов и Б. Гантер, 2000] отмечалось, что для классификации можно ограничиться только минимальными (по вложению ⊆) гипотезами, положительными и отрицательными, поскольку объектное содержаниесодержит положительную (отрицательную) гипотезу тогда и только тогда, когда оно содержит некоторую минимальную гипотезу.В разделах 4.1-4.2 приводится теоретико-решеточная интерпретация гипотез и показывается эквивалентность задач поиска минимальных гипотез идуализации монотонной булевой функции на решетке. Также, показываетсятрудноразрешимость задачи поиска минимальных гипотез.Задача 2. Перечисление минимальных гипотез (MHE)ВХОД: Положительные и отрицательные контексты K+=(+ , , ℐ+ ), K− = (− , , ℐ− )ВЫХОД: Все минимальные гипотезы контекста K± .Теорема 5.
Минимальные гипотезы не могут быть перечислены за полиномиальное от выхода время, если ̸= В разделе 4.3 описывается метод распределенного обучения гипотезам.Часто бывает ситуация, когда ДСМ-гипотез слишком много (даже минимальных), что затрудняет обучение гипотезам и последующую классификацию. Пусть есть несколько обучающих контекстов с одинаковым множествомпризнаков: K1± , . . .
, K± . В качестве гипотез будем использовать только те гипотезы, которые являются гипотезами в каждом из контекстов. Формально:SharedHypotheses(K± 1 , K± 2 , . . . , K± )123412C ← AllIntents(GetClosure(·), K+ , K+ , . . . , K+ )12H ← { | ∈ C , * ∀ ∈ K− ∪ K− ∪ . . .
∪ K− }Minimize(H )return HГде – оператор замыкания общих содержаний, а – любой алгоритм АФП поиска всех замкнутых множеств, использующий оператор замыканий (например Next Closure)Условиями применения данной модели обучения могут служить следующие ситуации:131. Несколько исследовательских групп проводят один и тот же эксперимент2. Несколько наборов данных с одинаковым набором признаков описываютодну и ту же задачу, но объекты отличаются по своей природе.3. Общих содержаний намного меньше, чем содержаний в каждом из положительных контекстов.Ниже приводятся результаты экспериментов по классификации токсичности химических соединений ДСМ-методом с использованием общих гипотез: .*304,62012,71014,6516,0.
.* . #.* #.10,0 65,9 54,61324,012,1 35,6 45,852134,010,5 18,3 45,4104270,010,4 15,1 45,8151389,75∙ .* – процент ошибочной классификации при использовании общихгипотез∙ . – процент ошибочной классификации при использовании классических гипотез∙ .* – процент неклассифицируемых объктов при использовании общих гипотез∙ . - процент неклассифицируемых объктов при использовании классических гипотез∙ #.* – количество минимальных общих гипотез∙ . – среднее количество минимальных классических гипотез по 4базам данных.Таблица 0.2.
Результаты классификации токсичности молекул.В разделе 4.4 даются основные определения устойчивости формальныхпонятий и гипотез.Определение 4. Пусть K = (, , ) – формальный контекст и (, )– формальное понятие контекста K. Индекс (интенсиональной) устойчивости (, ), или (), определяется следующим образом:| ⊆ | ′ = | (, ) =2||Индекс экстенсиональной устойчивости определяется двойственным об′′=|разом: (, ) = () = |⊆|. Обычно, когда это не приводит к2||неправильному пониманию, индексы и опускаются.В разделе 4.5 исследуются задачи приближенного подсчета числа замкнутых и незамкнутых множеств.
В частности рассматривается задача:14Задача 3. Количество незамкнутых множеств (#NC)ВХОД: A Формальный контекст K = (, , )ВЫХОД: Количество множеств ⊂ таких, что ′′ ̸= Доказывается, что эта задача не может быть решена за полиномиальное время, если ̸= . Простым следствием этого результата являетсяфакт, что, если ̸= , то не существует полиномиального алгоритма дляприближенного вычисления устойчивости формального понятия с полиномиально ограниченной относительной ошибкой.В разделе 4.6 описывается вероятностная модель устойчивости формального понятия.Определим модель вероятностной устойчивости формального понятия,следующим образом:Определение∑︀5(Вероятностный индекс устойчивости).
()==1 (), где () – независимые и одинаково распределенные случайныевеличины, определяемые как:{︂1, если ′′ = ; (замыкание случайного подмножества совпало с ) () =0, если ′′ ̸= ; (замыкание случайного подмножества не совпало с )когда ⊆ выбрано случайно и равномерноВероятностный индекс устойчивости можно вычислять методом МонтеКарло.Утверждение 1. Метод Монте-Карло аппроксимирует () с вероятностью не меньше 1 − и абсолютной погрешностью при условии, что12 > 2 ln2В разделе 4.7 приводится анализ вычисления вероятностной устойчивости. Топ устойчивых понятий находится, используюя следующий несложныйалгоритм:TopStableConcepts(K, 0 )1 answer ← ∅2 for каждого понятия = (, ′ ) контекста K3do if approxStability() > 4then answer ← answer ∪{(, ′ )}5 return answerВ разделе 4.8 приводятся результаты экспериментов с данными по токсичности химических соединений, используя устойчивые гипотезы.
В данномтестировании для классификации выбирались только устойчивые гипотезы.Гипотеза считалась устойчивой, если ее индекс вероятностной устойчивости50 в соответствующем контексте (положительном, для положительной гипотезы и отрицательном, для отрицательной гипотезы) больше заданного порога0.65.15 .*3031,02010,91012,5512,8. .* . #.* #.10,0 49.7 54,69,824,012,1 44.6 45,879,7134,010,5 34.5 45,4 265,75270,010,4 31.9 45,8393,5389,75∙ .* – процент ошибочной классификации при использовании устойчивых гипотез с > 0, 65∙ . – процент ошибочной классификации при использовании классических гипотез∙ .* - процент неклассифицируемых объектов при использованииустойчивых гипотез с > 0, 65∙ . – процент неклассифицируемых объектов при использовании классических гипотез∙ #.* – среднее количество минимальных устойчивых гипотез по 4базам данных∙ #.
– среднее количество минимальных классических гипотез по 4базам данныхТаблица 0.3. Результаты классификации токсичности молекул.В пятой главе приводится описание системы Cordiet-FCA и вошедшего внее комплекса программ, реализующего алгоритмы, описанные в диссертации.Система Cordiet-FCA разрабатывается отделением прикладной математики иинформатики НИУ ВШЭ (ОПМИ).
На основе предложенных моделей и алгоритмов, описанных в разделах 2.8, 3.4, 4.3 и 4.6, был разработан комплекспрограмм вошедший в систему Cordiet-FCA.В разделе 5.2 описывается структура программы построения и тестирования базисов импликаций:Алгоритмы построения и тестирования базисов импликаций были реализованы на языке C++ (около 1000 строк кода).Эти реализации вошли в комплекс программ, встроенный в программную систему Cordiet-FCA и могут быть использованы для построения приближенного базиса импликаций.Структура программы построения и тестирования базисов импликацийимеет следующий вид:1.
В файлах mset.h и mset.cpp (приложение 1.1) реализованы структуры ифункции для работы с множествами, представленными списками элементов.162. В файлах implications.h и implications.cpp (приложение 1.2) реализованы структуры и функции для работы с импликациями. Функцияlin_closure(const std::vector<Implication>& implications, const mset& X)вычисляет замыкание множества X в базисе implications, используя алгоритм linclosure [Д. Мейер 1987]3.
В файлах context.h и context.cpp (приложение 1.3) реализован классContext для работы с формальными разреженными контекстами.4. В файлах min_transversals.h и min_transversal.cpp (приложение 1.4) реализован алгоритм поиска минимальных трансверсалей гиперграфа изработы [Д. Каввадиас и др. 2005], который используется для поискаминимальных генераторов и собственных посылок.5. В файлах angluin.h и angluin.cpp (приложение 1.5) реализован алгоритм поиска приближенного базиса импликаций.Функцияstd::vector<Implication>get_approximate_base(constsparse_context::Context& K, int no_steps) возвращает приближенный базис импликация контекста K, после no_steps шагов.6. В файлах proper_premise.h и proper_premise.cpp (приложение 1.6) реализован алгоритм поиска собственных посылок из работы [Д.
Боркманни др. 2011].В разделе 5.3 описывается программная реализация алгоритма вычисления оператора замыкания общих содержанийБыли реализованы две версии алгоритма вычисления оператора замыкания общих содержаний: для случая, когда контекст задан бинарной матрицейи случая, когда контекст задан списками признаков.Оба алгоритма были реализованы на языке C++ (около 170 строк) всреде MS Visual Studio 2010 с использованием стандартной библиотеки STL.Реализация вошла в комплекс программ, встроенный в программную систему Cordiet-FCA и может быть использована для анализа сходства большихдинамических массивов данных.Структура программы вычисления оператора замыканий общих содержаний имеет следующий вид:1. В файле shared_closure.cpp (приложение 2.1) функция mset closure(conststd::vector<sparse_context::Context>& K, const mset& X) вычисляет оператор замыкания общих содержаний для случая когда контексты заданысписками признаков.2.
В файлах shared_closure.h и shared_closure.cpp (приложение 2.1) реализована структура данных PQ (специальная приоритетная очередьс поддержкой дополнительный операций), используемая алгоритмом_2.В разделе 5.4 описывается программная реализация распределенногообучения гипотезам.17Алгоритм распределенного обучения гипотезам был реализован на языке C++ (около 300 строк) в среде MS Visual Studio 2010 с использованиемстандартной библиотеки STL.Реализация вошла в комплекс программ, встроенный в программнуюсистему Cordiet-FCA.Структура программы распределенного обучения гипотезам имеет следующий вид:1. В файле JSM_test.cpp (приложение 2.1) функция vector<mset>find_shared_hypotheses(constvector<Context>&pK,constvector<Context>& nK) находит все общие гипотезы наборов положительных и отрицательных контекстов pK и nK, соответственно.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
