close

Вход

Забыли?

вход по аккаунту

?

Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств

код для вставкиСкачать
ФИО соискателя: Бабин Михаил Александрович Шифр научной специальности: 05.13.18 - математическое моделирование, численные методы и комплексы программ Шифр диссертационного совета: Д 212.048.09 Название организации: Национальный исследовательский уни
На правах рукописи
Бабин Михаил Александрович
Модели, методы и комплексы программ построения зависимостей,
основанные на решетках замкнутых множеств
Специальность 05.13.18
Математическое моделирование, численные методы и комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание уч¨еной степени
кандидата физико-математических наук
Москва — 2012
Работа выполнена в Национальном исследовательском университете «Высшая школа экономики» (НИУ ВШЭ).
Научный руководитель:
доктор физико-математических наук
Кузнецов Сергей Олегович
Официальные оппоненты:
доктор физико-математических наук, профессор,
профессор кафедры математики, логики и интеллектуальных систем Института лингвистики РГГУ
Аншаков Олег Михайлович
кандидат физико-математических наук,
старший научный сотрудник отдела теоретических и прикладных проблем информатики
ВИНИТИ РАН
Виноградов Дмитрий Вячеславович
Ведущая организация:
Институт проблем передачи информации им. А.А. Харкевича
(ИППИ) РАН
Защита состоится “29” октября 2012 г. в 14.00 на заседании диссертационного совета Д 212.048.09 в Национальном исследовательском университете
«Высшая школа экономики» (НИУ ВШЭ) по адресу: 105187, Москва, ул. Кирпичная, д. 33., ауд. 505
С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики».
Автореферат разослан “19” сентября 2012 г.
Уч¨еный секретарь
диссертационного совета
доктор технических наук
В.А. Фомичев
3
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Стремительный рост объема данных разной природы, наблюдающийся в последние десятилетия, приводит к необходимости
разработки эффективных методов их автоматического и интерактивного анализа. Одной из распространенных математических моделей, позволяющих
описывать методы и алгоритмы анализа данных, является анализ формальных понятий.
Анализ формальных понятий (АФП) является ветвью прикладной алгебраической теории решеток, широко используемой для описания методов
анализа данных. АФП предлагает средства моделирования онтологий и таксономий предметных областей на основе решеток понятий, а также модели
точных и приближенных зависимостей в данных.
Для многих ключевых задач анализа формальных понятий до сих пор
неизвестны эффективные алгоритмы и какие-либо теоретические оценки их
сложности. Основной целью большинства существующих исследований является анализ данных на основе методов АФП, в то время как эффективные
алгоритмы и вычислительная сложность этих методов уходит на второй план.
Примерами актуальных задач являются:
∙ Модели импликативных зависимостей, позволяющие более сжатое представление и эффективную алгоритмическую реализацию
∙ Эффективные алгоритмы порождения приближенных базисов импликаций, множества минимальных ДСМ-гипотез
∙ Эффективные алгоритмы распознавания псевдосодержаний, задающих
оптимальный базис импликаций
∙ Модели оценивания импликативных зависимостей и эффективное вычисление оценок этих зависимостей
Так например, эффективные алгоритмы порождения и сложность распознавания псевдосодержаний, задающих оптимальный базис зависимостей
(импликаций) была одной из основных открытых задач АФП на протяжении
многих лет (список открытых задач АФП [U. Priss 2006] задачи 2,8,9).
Объектом исследования являются модели импликативных зависимостей
в данных и их эффективная алгоритмическая реализация.
Целью исследования является разработка моделей импликативных зависимостей в данных, для которых существуют более быстрые алгоритмы, а
также решение связанных с ними вычислительных задач и разработка комплекса программ, реализующего предложенные алгоритмы.
Методы исследования. В диссертации применяются методы анализа
формальных понятий, дискретной оптимизации, вероятностных алгоритмов
и теории вычислительной сложности алгоритмов.
Научная новизна. В диссертации получены следующие основные новые
научные результаты, которые выносятся на защиту:
4
1. Доказана трудноразрешимость задач, связанных с вычислением классического минимального базиса импликаций.
2. Предложена новая модель приближенного базиса импликаций формального контекста, алгоритм его вычисления и эффективная программная
реализация.
3. Доказана трудноразрешимость вычисления минимальных гипотез в
стандартной постановке
4. Предложена и экспериментально проверена модель распределенного
обучения гипотезам – импликативным зависимостям для задачи машинного обучения.
5. Предложен линейный по времени алгоритм поиска всех гипотез по распределенной обучающей выборке и его программная реализация.
6. Предложена и экспериментально проверена модель оценивания гипотез
и формальных понятий – вероятностный индекс устойчивости.
7. Теоретически и экспериментально исследована сложность вычисления
вероятностного индекса устойчивости, предложен эффективный алгоритм и его программная реализация.
8. Решены давно сформулированные и остававшиеся открытыми задачи
создания эффективных алгоритмов и оценки вычислительной сложности распознавания псевдосодержаний и существенных содержаний.
9. Показана полиномиальная эквивалентность задачи перечисления минимальных гипотез и задачи дуализации монотонной булевой функции на
решетке.
10. Разработан комплекс программ, реализующий предложенные алгоритмы, который был встроен в коллективно разрабатываемый в Отделении
прикладной математики и информатики НИУ ВШЭ комплекс программ.
Теоретическая значимость подтверждается тем, что были предложены
новые модели импликативных зависимостей, а также средства их оценивания,
показана их адекватность практическим задачам и возможность эффективной
алгоритмической реализации. Были решены открытые теоретические задачи
прикладной теории решеток и анализа данных.
Практическая значимость подтверждена экспериментами по построению
приближенного базиса импликаций, распределенному обучению гипотезам и
вычислению вероятностной устойчивости. Эти эксперименты показали значительные улучшения во времени вычисления и в качестве полученных результатов. Был разработан комплекс программ, в который вошли алгоритмы,
опубликованные в данной работе.
Достоверность результатов подтверждена строгими математическими
доказательствами теоретических утверждений, экспериментальной проверкой
5
результатов численных расчетов и практической эффективности программных реализаций.
АПРОБАЦИЯ РАБОТЫ
Основные результаты работы докладывались и обсуждались на следующих научных конференциях:
1. 8-ой международной конференции по анализу формальных понятий (8th
International Conference on Formal Concept Analysis), Агадир, Марокко,
2010.
2. 7-ой международной конференции по решеткам понятий и их приложениям (7th International Confere6nce on Concept Lattices and Their
Applications), Севилья, Испания, 2010. [Награда за лучшую статью]
3. 9-ой международной конференции по анализу формальных понятий (9th
International Conference on Formal Concept Analysis), Никосия, Кипр,
2011.
4. 10-ой международной конференции по анализу формальных понятий
(8th International Conference on Formal Concept Analysis), Лёвен, Бельгия,
2012.
Публикации. Основные результаты работы изложены в 6 научных статьях из которых 4 опубликованы в рецензируемых трудах международных конференций (индексируемыми системами Web of Science и Scopus) и 2 опубликованы в журналах из списка ВАК.
Структура и объем диссертации. Диссертация состоит из пяти глав, заключения, списка литературы и приложений. Общий объем основного текста
работы — 133 страницы. Список литературы включает 100 наименований.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы, сформулированы цели и
задачи исследования, научная новизна, теоретическая и практическая значимость полученных результатов, основные положения, выносимые на защиту,
а также приведены данные о структуре и объеме диссертации.
В первой главе описываются основные результаты и определения используемые в диссертации.
Ниже приводятся основные определения анализа формальных понятий,
используемые в диссертационной работе.
Пусть  и  - конечные множества, называющиеся множествами объектов и признаков соответственно. Пусть  - бинарное отношение  ⊆  × 
между объектами и признаками: для  ∈ ,  ∈ ,  выполнено тогда и
только тогда, когда объект  обладает признаком . Тройка K = (, , )
6
называется (формальным) контекстом. Если  ⊆ ,  ⊆  - произвольные подмножества, то следующая пара операторов, называемых операторами
Галуа,
′ = { ∈  |  ∀ ∈ }
 ′ = { ∈  |  ∀ ∈ }
задает соответствие Галуа между частично упорядоченными множествами
(2 , ⊆) и (2 , ⊆).
Пара (, ), где  ⊆ ,  ⊆  , ′ = , и  ′ =  (следовательно,
′′ =  и  ′′ = ), называется (формальным) понятием (контекста K) с
объемом  и содержанием .
Оператор (·)′′ является оператором замыкания, т.е. он идемпотентен
( ′′′′ =  ′′ ), экстенсивен ( ⊆  ′′ ) и монотонен ( ⊆  ⇒  ′′ ⊆  ′′ ).
Множества  ⊆ ,  ⊆  называются замкнутыми если ′′ =  и  ′′ = .
Очевидно, объемы и содержания (и только они) замкнуты. Множество всех
замкнутых множеств относительно данного оператора замыкания называется
системой замыканий.
Основная теорема анализа формальных понятий (см. [Ganter B., Wille
R., 1999]) говорит, что множество понятий контекста K = (, , ) образует
полную решетку со следующими операциями инфинума (inf) и супремума
(sup) соответственно:
(︃
(︃
)︃′′ )︃
⋀︁
⋂︁
⋃︁
( ,  ) =
 ,

∈
∈
∈
)︃′′
(︃(︃
⋁︁
∈
( ,  ) =
⋃︁
∈

)︃
,
⋂︁

∈
Понятие (, ) называется супремум-неразложимым, если оно не может
быть представлено как супремум каких-то других понятий.
Множество признаков  следует из множества признаков , или выполнена импликация  → , если все объекты из , которые обладают всеми
признаками из , также обладают всеми признаками из , т.е. ′ ⊆  ′ .
Импликации подчиняются правилам Армстронга:
→
 → ,  ∪  → 
,
.
→
∪ →
∪ →
Во второй главе приводятся основные результаты диссертации, связанные с оптимальными базисами импликаций формального контекста.
В разделе 2.1 приводятся основные определения, связанные с минимальными базисами импликаций, такие как определения псевдосодержаний, существенных содержаний и квазизамкнутых множеств.
Подмножество  ⊆  удовлетворяет импликации  → , если из
 ⊆  следует  ⊆ . Любое множество импликаций J на множестве 
определяет оператор замыкания (·)J на  , где подмножество  замкнуто
,
7
тогда и только тогда, когда это множество удовлетворяет всем импликациям из J. Набор импликаций, из которого все остальные импликации могут
быть выведены по правилам Армстронга, называется базисом импликаций.
Другое, эквивалентное определение базиса импликаций это совпадение операторов замыкания (·)′′ и (·)J . Одним из минимальных базисов импликаций
является базис Дюкена-Гига (канонический базис). Множество посылок импликаций в каноническом базисе является в точности множеством псевдосодержаний. Множество  ⊆  называется псевдосодержанием, если  ̸=  ′′
и ′′ ⊂  для любого псевдосодержания  ⊂  . Подмножество  ⊆  квазизамкнуто, если его пересечение с любым замкнутым множеством замкнуто.
Множество квазизамкнутых множеств образует систему замыканий. Множество  ⊆  называется существенным содержанием (существенно замкнутое
подмножество признаков), если существует псевдосодержание  ⊆  такое, что  ′′ = . Множество существенных содержаний является множеством
заключений импликаций из минимального базиса импликаций (любого минимального базиса импликаций).
В разделе 2.2 описывается структура минимальных базисов импликаций. Базис импликаций J минимален тогда и только тогда, когда для любой
импликации  →  ∈ J квазизамыкание посылки  является псевдосодержанием и у различных импликаций квазизамыкания посылок различны.
В разделе 2.3 приводится ранее известный результат о полиномиальной
эквивалентности задачи поиска минимального базиса импликаций формального контекста и задачи поиска минимального покрытия функциональных зависимостей реляционной базы данных.
В разделе 2.4 рассматривается задача:
Задача 1. Распознавание псевдосодержания (PI)
ВХОД: Формальный контекст K = (, , ) и подмножество признаков
 ⊆ .
ВОПРОС: Является ли  псевдосодержанием контекста K?
и доказывается
Теорема 1. Задача PI co  -трудна.
В разделах 2.5 и 2.6 приводятся несколько простых следствий Теоремы 1. В частности доказывается, что посылки минимального базиса импликаций не могут быть перечислены в обратном лектическом порядке (лексикографическом порядке на характеристических векторах множеств) с полиномиальной задержкой, если  ̸=   . Также доказывается, что задача
распознавания существенных содержаний NP-полна.
В разделе 2.7 рассматривается задача эквивалентности систем замыканий заданных контекстом и набором импликаций, в котором у всех импликаций посылки по мощности не больше 2. Доказывается, что такая задача не
проще задачи, в которой нет ограничения на мощности посылок.
В разделе 2.8 рассматривается новая модель импликативных зависимостей – приближенный базис импликаций:
8
Определение 1. Набор импликаций  называется приближенным базисом формального контекста K = (, , ), если для случайно и равномерно выбранного подмножества  ⊆  выполняется условие
 ( ′′ =   ) > 1 − , 0 <  < 1.
Таким образом 1 −  соответствует точности приближения.
Преимущества, предложенной модели по сравнению с точным базисом:
∙ Существенно меньшее количество импликаций
∙ Существенно более быстрое время построения, которое линейно от −1
∙ Высокая точность приближения (1 − )
Приведем псевдокод алгоритма построения приближенного базиса импликаций формального контекста K = (, , ), основанного на результатах
[Д. Англуин и др. 1992] об обучении Хорновской Конъюнктивной Нормальной
Формы (КНФ) при помощи двух оракулов.
UpdateBase(K, , )
1 for each  →  ∈ 
2
do if   And ( ∩ )′′ ̸=  ∩ 
3
then заменить в  импликацию  → 
4
на  ∩  → ( ∩ )′′
5
return J
6  ←  ∪ { ←  ′′ }
7 return J
ApproximateImplicationBase(K,  )
1 J ←∅
2 for  ← 1 to 
3
do выбрать случайное замкнутое множество  базиса 
4
if  ′′ ̸= 
5
then J ← UpdateBase(K, , )
6 return J
Данный алгоритм использует следующий метод генерации случайного
множества, замкнутого в базисе :
GenerateRandomClosedSet()
1 X ← random subset of 
2 X ← (, )
3 return X
Здесь LinClosure – линейный алгоритм вычисления замыкания в базисе импликаций [Д. Мейер 1987]. Доказывается теорема:
9
Теорема 2. Математическое ожидание времени работы алгоритма
, до достижения точности 1− (0 <  < 1)
для контекста K = (, , ), равно (| || | · (||| | + | || |) · −1 ),
где  – минимальный базис импликаций.
В разделе 2.8.1 приводятся результаты компьютерных экспериментов
приближенного базиса импликаций на реальных данных.

̂︁
база данных || | | | | ||| |


Chess
3197 39 76 43,1 0,9988 595
Zoo
101 28 43
3,3 0,9999 1,853
P.-Op. P.
90
25 85
5,0 0,9989 2,06
Grav
707 473 53 233,4 0,9999 3129
Grav_a
707 156 39 286,6 0,9999 92,05
Таблица 0.1. Результаты вычисления приближенного базиса.
∙  – приближенный базис импликаций
∙  – точный базис импликаций
̂︁ – оценка вероятности  ( ′′ =   ) того, что для случайного под∙ 
множества  ⊆  замыкания совпадают
∙  – время построения точного базиса алгоритмом Гантера
∙  – время построения приближенного базиса
В третьей главе приводятся результаты связанные с общими содержаниями формальных контекстов.
В разделах 3.1–3.3 показывается связь базиса импликаций с общими
содержаниями и приводится общий алгоритм поиска минимального базиса
импликаций. Пусть даны два формальных контекста с общим множеством
признаков: K1 = (1 , , 1 ) с базисом импликаций (не обязательно минимальным) J1 и контекст K2 = (2 , , 2 ) с базисом импликаций J2 . Очевидно, что множество их общих содержаний является системой замыканий.
Поэтому мы можем рассмотреть контекст K = (, , ), объектные содержания, которого будут неразложимыми элементами системы замыканий общих содержаний. Будем называть контекст K, контекстом общих содержаний.
Можно предложить следующий общий алгоритм построения минимального
базиса импликаций:
FindMinBase(K = (, , ))
1 Представить контекст K множеством контекстов K1 , K2 , . . . , K ,
для которых K будет являться контекстом общих содержаний
2 Для каждого контекста K найти минимальный базис импликаций J .
3 J ← J1 ∪ J2 ∪ . . . ∪ J
4 J ←  ()
5 return J
10
В разделе 3.4 показывается, что описанный в статье [Ф. Дистель и др.
2011] алгоритм поиска собственных посылок, является частным случаем приведенного общего алгоритма поиска базиса импликаций.
В разделе 3.5 описывается модель сходства формальных понятий - интенсиональная связность.
В разделе 3.6 исследуются задачи, связанные с общими содержаниями формальных контекстов. Предлагается алгоритм вычисления оператора
замыканий общих содержаний (·) контекстов K1 = (1 , , 1 ), . . . , K =
( , ,  ):
GetClosure()
1 answer ← 
2 for  ← 1 to 
3
do remove all rows from [] that do not contain 
4 for  ← 1 to 
5
do for  ← 1 to | |
6
do if not answer [m]
7
then if [][][] = true for all 1 ≤  ≤ | |
8
then answer [] ← true
9
push  in shared -attributes
10
else for each 1 ≤  ≤ | | such that not [][][]
11
do push (, ) in not-in[]
12
counter [][] ← counter [][] + 1
13 while shared -attributes not empty
14
do pop  from shared -attributes
15
while not-in[] not empty
16
do pop (object-index , context-index ) from not-in[]
17
for  ← 1 to | |
18
do if not [][context-index ][object-index ]
19
then counter [context-index ][i ] ←
← counter [context-index ][i ] −1
20
if counter [context-index ][i ] ≤ 0
and not answer [i ]
21
then answer [i ] = true
22
push  in shared -attributes
23 return answer
Здесь [] - это бинарная матрица, задающая отношение  , counter [][]
равно количеству объектов  из  для которых   не выполнено, sharedattributes и not-in[] могут быть реализованы как стеки или как любые другие
структуры данных, поддерживающие операции “вытащить"(pop) любой объект и “вставить"(push) любой объект за время (1).
Доказывается, что время работы этого алгоритма линейно от размера
входа:
11
Теорема 3. Алгоритм () вычисляет   для произвольного подмножества признаков  ⊆ ∑︀ и контекстов K1 =
(1 , , 1 ), . . . , K = ( , ,  ) за время (| | 1≤≤ | |).
Также рассматривается случай, когда все контексты заданы списками
признаков своих объектов (а не матрицами, как в предыдущем алгоритме) и
приводится алгоритм вычисления оператора замыканий общих содержаний за
линейное от входа время.
Теорема 4. Алгоритм _2() вычисляет   для произвольного подмножества признаков  ⊆∑︀  и контекстов K1 =
(1 , , 1 ), . . . , K = ( , ,  ) за время ( 1≤≤ | |).
Используя алгоритм (·) (_2(·)) в качестве оракула, можно перечислять все общие содержания с полиномиальной задержкой, применяя стандартные алгоритмы АФП (такие как Norris, Next Closure,
Close-by-One).
В разделе 3.8 показывается как сцепления формальных контекстов могут
быть представлены через общие содержания.
В четвертой главе рассматриваются вопросы связанные с обучением гипотезам.
Пусть признаки из  описывают "структуру"объектов, а  - целевой
признак, отличный от всех признаков из  . Например, в фармакологических
приложениях структурные признаки могут соответствовать подграфам молекулярных графов химических соединений, а целевой признак - биологическим
свойствам этих соединений.
Входные данные для контекста обучения могут быть представлены множествами положительных, отрицательных и неопределенных примеров. Положительные примеры (или (+)-примеры) – это объекты, о которых известно,
что они обладают признаком , а отрицательные примеры (или (−)-примеры)
– это объекты, о которых известно, что они не обладают признаком 
Определение 2. Рассмотрим положительный контекст K+ =
(+ , , ℐ+ ) и отрицательный контекст K− = (− , , ℐ− ). Контекст
K± = (+ ∪ − ,  ∪ {}, ℐ+ ∪ ℐ− ∪ + × {}) называется контекстом
обучения. Оператор Галуа для этого контекста обозначается как ±.
Определение 3. Подмножество  ⊆  называется положительной
гипотезой (или (+)-гипотезой) контекста обучения K± если  - содержание контекста K+ и  не является подмножеством ни одного содержания контекста K− .
Аналогично определяются отрицательные гипотезы (или (-)-гипотезы).
Содержание контекста K+ , которое принадлежит хотя бы одному отрицательному примеру, называется фальсифицированным (+)-обобщением.
Помимо положительных и отрицательных примеров обычно имеются
объекты, для которых значение целевого признака неизвестно. В работе [В.
Финн 1991] эти объекты называются неопределенными примерами, они могут
12
быть заданы контекстом K := ( , ,  ), соответствующий оператор Галуа
обозначается через (·) .
Гипотезы могут быть использованы для классификации неопределенных
примеров: если содержание
  := { ∈  | (, ) ∈  }
объекта  ∈  содержит положительную и ни одной отрицательной гипотезы, то   классифицируется положительно. Отрицательные классификации
определяются аналогично. Если   содержит гипотезы обоих знаков, то классификация противоречива. Если   вообще не содержит гипотез, то классификация не определена. В этом случае можно применять методы другого типа,
например, основанные на статистических подходах.
В работе [С. Кузнецов и Б. Гантер, 2000] отмечалось, что для классификации можно ограничиться только минимальными (по вложению ⊆) гипотезами, положительными и отрицательными, поскольку объектное содержание
содержит положительную (отрицательную) гипотезу тогда и только тогда, когда оно содержит некоторую минимальную гипотезу.
В разделах 4.1-4.2 приводится теоретико-решеточная интерпретация гипотез и показывается эквивалентность задач поиска минимальных гипотез и
дуализации монотонной булевой функции на решетке. Также, показывается
трудноразрешимость задачи поиска минимальных гипотез.
Задача 2. Перечисление минимальных гипотез (MHE)
ВХОД: Положительные и отрицательные контексты K+
=
(+ , , ℐ+ ), K− = (− , , ℐ− )
ВЫХОД: Все минимальные гипотезы контекста K± .
Теорема 5. Минимальные гипотезы не могут быть перечислены за полиномиальное от выхода время, если  ̸=  
В разделе 4.3 описывается метод распределенного обучения гипотезам.
Часто бывает ситуация, когда ДСМ-гипотез слишком много (даже минимальных), что затрудняет обучение гипотезам и последующую классификацию. Пусть есть несколько обучающих контекстов с одинаковым множеством
признаков: K1± , . . . , K± . В качестве гипотез будем использовать только те гипотезы, которые являются гипотезами в каждом из контекстов. Формально:
SharedHypotheses(K± 1 , K± 2 , . . . , K±  )
1
2
3
4
1
2

C ← AllIntents(GetClosure(·), K+ , K+ , . . . , K+ )
1
2

H ← { |  ∈ C ,   ∀ ∈ K− ∪ K− ∪ . . . ∪ K− }
Minimize(H )
return H
Где  – оператор замыкания общих содержаний, а 
– любой алгоритм АФП поиска всех замкнутых множеств, использующий оператор замыканий (например Next Closure)
Условиями применения данной модели обучения могут служить следующие ситуации:
13
1. Несколько исследовательских групп проводят один и тот же эксперимент
2. Несколько наборов данных с одинаковым набором признаков описывают
одну и ту же задачу, но объекты отличаются по своей природе.
3. Общих содержаний намного меньше, чем содержаний в каждом из положительных контекстов.
Ниже приводятся результаты экспериментов по классификации токсичности химических соединений ДСМ-методом с использованием общих гипотез:
 .*
30
4,6
20
12,7
10
14,6
5
16,0
.  .*  . #.* #.
10,0 65,9 54,6
13
24,0
12,1 35,6 45,8
52
134,0
10,5 18,3 45,4
104
270,0
10,4 15,1 45,8
151
389,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 −  и абсолютной погрешностью  при условии, что
1
2
 > 2 ln
2

В разделе 4.7 приводится анализ вычисления вероятностной устойчивости. Топ устойчивых понятий находится, используюя следующий несложный
алгоритм:
TopStableConcepts(K, 0 )
1 answer ← ∅
2 for каждого понятия  = (, ′ ) контекста K
3
do if approxStability() > 
4
then answer ← answer ∪{(, ′ )}
5 return answer
В разделе 4.8 приводятся результаты экспериментов с данными по токсичности химических соединений, используя устойчивые гипотезы. В данном
тестировании для классификации выбирались только устойчивые гипотезы.
Гипотеза считалась устойчивой, если ее индекс вероятностной устойчивости
50 в соответствующем контексте (положительном, для положительной гипотезы и отрицательном, для отрицательной гипотезы) больше заданного порога
0.65.
15
 .*
30
31,0
20
10,9
10
12,5
5
12,8
.  .*  . #.* #.
10,0 49.7 54,6
9,8
24,0
12,1 44.6 45,8
79,7
134,0
10,5 34.5 45,4 265,75
270,0
10,4 31.9 45,8
393,5
389,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) реализованы структуры и
функции для работы с множествами, представленными списками элементов.
16
2. В файлах 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(const
sparse_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(const
std::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(const
vector<Context>&
pK,
const
vector<Context>& nK) находит все общие гипотезы наборов положительных и отрицательных контекстов pK и nK, соответственно.
2. В файле JSM_test.cpp (приложение 2.1) функция mset
next_closure_JSM(const mset& X, const Context& K) возвращает
следующую гипотезу в лексикографическом порядке на объемах
соответствующих формальных понятий.
3. В файле JSM_test.cpp (приложение 2.1) функция int classify(const
vector<mset>& pH, const vector<mset>& nH, const mset& X) возвращает результат классификации X при использовании множества положительных гипотез pH и множества отрицательных гипотез nH. Данная функция возвращает 1, если результат классификации положителен,
−1, если результат классификации отрицателен, и 0, если классификация неопределена.
В заключении приведены основные результаты и выводы диссертации.
В отличие от классического минимального базиса импликаций, для которого все известные алгоритмы построения имеют экспоненциальную оценку
сложности, среднее время работы построения приближенного базиса импликаций полиномиально и оценивается как (| || | · (||| | + | || |) · −1 ),
где  – минимальный базис импликаций, а  – параметр точности приближенного базиса импликаций. Проведенные на реальных данных эксперименты
показали, что размер приближенного базиса был значительно меньше (иногда
в сотни раз).
В работе было доказано, что если  ̸=   , то невозможно найти все
минимальные ДСМ-гипотезы за полиномиальное от размера выхода время.
Модель распределенного обучения гипотезам показала значительное сокращение количества гипотез по отношению к числу ДСМ-гипотез в стандартной
постановке. Линейный по времени алгоритм вычисления оператора замыканий системы замыканий общих содержаний позволил быстро перечислять все
общие гипотезы.
В данной работе была доказана трудность аппроксимации индекса классической устойчивости формальных понятий (с полиномиально ограниченной относительной ошибкой). Была предложена модель вероятностного индекса устойчивости формальных понятий, которая соответствует аппроксимации классического индекса устойчивости с ограниченной абсолютной ошибкой
18
и может быть вычислена за полиномиальное время. Проведенные эксперименты показали, что применение вероятностного индекса устойчивости, при
использовании ДСМ-метода, уменьшает число неклассифицируемых объектов на ≈ 43% при увеличении количества ошибок классификации на ≈ 23%
(число неклассифицируемых объектов, при использовании стандартных ДСМгипотез ≈ 46%).
19
Основное содержание диссертационной работы изложено в
следующих публикациях:
Публикации в журналах, входящих в перечень ВАК
1. Бабин М.А. и Кузнецов С.О. О теоретико-решеточной интерпретации
задач поиска гипотез и зависимостей //Научно-техническая информация. Серия: Информационные процессы и системы, №10, 2011, С. 18–22,
0.72 п.л. (вклад автора 0,6 п.л.)
2. Бабин М.А. и Кузнецов С.О. Связи между решетками понятий и сложность их вычисления // Труды МФТИ, том 4 №2(14), 2012, С. 73–80,
0.7 п.л (вклад автора 0,6 п.л.)
Другие публикации в рецензируемых научных изданиях и журналах
1. Babin M. A. and Kuznetsov S.O. On Links between Concept Lattices and
Related Complexity Problems // Lecture Notes in Artificial Intelligence, №
5986, 2010, C. 138–144, Springer 0.54 п.л. (вклад автора 0,4 п.л.)
2. Babin M. A. and Kuznetsov S.O. Recognizing Pseudo-Intent is coNPcomplete // CLA 2010: Proceedings of the 7th International Conference
on Concept Lattices and Their Applications, C. 294–301, 0.6 п.л. (вклад
автора 0,5 п.л.)
3. Babin M. A. and Kuznetsov S.O. Enumerating Minimal Hypotheses and
Dualizing Monotone Boolean Functions on Lattices // Lecture Notes in
Artificial Intelligence, № 6628, 2011, C. 42–48, Springer 0.51 п.л. (вклад
автора 0,4 п.л.)
4. Babin M. A. and Kuznetsov S.O. Approximating Concept Stability // Lecture
Notes in Artificial Intelligence, № 7278, 2012, C. 7–15, Springer 0.62 п.л.
(вклад автора 0,5 п.л.)
Лицензия ЛР № 020832 от 15 октября 1993 г.
Подписано в печать 18 сентября 2012 г.
Формат 60 х 84/16
Бумага офсетная.
Печать офсетная.
Усл. печ. л. 1
Тираж 100 экз. Заказ № 55
Типография издательства
Национального исследовательского университета «Высшая школа
экономики»,
125319, г. Москва, Кочновский проезд, д.3
Документ
Категория
Физико-математические науки
Просмотров
27
Размер файла
366 Кб
Теги
кандидатская
1/--страниц
Пожаловаться на содержимое документа