Построение импликативных зависимостей для аналитического описания предметных областей и обнаружения ошибок в данных тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Ревенко, Артем Викторович

• Ревенко, Артем Викторович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Ревенко, Артем Викторович

Оглавление

1 Введение

1.1 Анализ формальных понятий

1.2 Обнаружение зависимостей в данных

1.2.1 Предметные области

1.3 Общее описание работы

1.3.1 Актуальность

1.3.2 Цели работы

1.3.3 Основные результаты

1.3.4 Научная новизна

1.3.5 Практическая ценность

1.3.6 Апробация

1.4 Содержание

2 Теоретические положения

2.1 Основы теории решёток

2.2 Анализ формальных понятий

2.2.1 Исследование признаков

2.2.2 Диаграммы решеток

3 Исследование импликативной теории свойств функций на конечных множествах

3.1 Функции и свойства функций

3.1.1 Интерес к изучению свойств функций на конечных множествах

3.2 Изменение вида базисов

3.3 Базисы импликаций

3.3.1 Различия в базисах импликаций для функций

на множествах размера 2 и размера 3

3.3.2 Доказательства импликаций

3.3.3 Недоказанные импликации

3.4 Обобщение свойств функций

3.5 Выводы

4 Исследование импликативной теории алгебраических тождеств

4.1 Многообразия алгебр

4.2 Алгебраические тождества

4.3 Алгебры

4.3.1 Порождение алгебр на конечном носителе

4.3.2 Необходимость порождения алгебр на бесконечном носителе

4.3.3 Порождение алгебр на бесконечном носителе

4.4 Выводы

5 Нахождение ошибок в содержаниях формальных объектов

5.1 Методы нахождение ошибок в различных областях знаний

5.2 Нахождение ошибок в содержаниях формальных объектов

5.2.1 Классификация ошибок

5.2.2 Нахождение ошибок

5.2.3 Пример

5.2.4 Доказательство корректности и улучшения

5.2.5 Результаты поиска ошибок

5.3 Другое представление метода нахождения ошибок

5.4 Нахождение ошибок в исходном коде программы

5.4.1 Ошибки в исходном программном коде

5.4.2 Отладка с помощью методов АФП

5.4.3 Выводы

Заключение

Литература

Приложение

Список иллюстраций

1.1 Дерево принятия решения играть ли на улице в теннис

2.1 Контекст выпуклых четырехугольников Kq

2.2 Контекст выпуклых четырехугольников Кц, дополненный прямоугольным четырехугольником

2.3 Контекст выпуклых четырехугольников Кц, дополненный прямоугольным четырехугольником и прямоугольной равнобедренной трапецией

2.4 Диаграмма решетки контекста функций на множестве

М2

3.1 Исходный контекст из примера 3.2.2

3.2 Контекст с добавлением контрпримера из примера 3.2.2

3.3 Редуцированный контекст функций на множестве

3.4 Редуцированный контекст функций на множествах

М2, М3 и М4

3.5 Диаграмма решетки контекста функций на множествах М2, М3 и М4

5.1 Расширенный контекст выпуклых четырехугольников

Ко

5.2 Контекст ошибок Ке

5.3 Сравнение времен работы реализаций методов inspect_direct и inspect_dg на случайных контекстах

5.4 Поиск ближайших соседей в решетке понятий

5.5 Контекст с успешными запусками функции remove_html_markup

Контекст с неуспешными запусками функции гетоуе_11"Ьт1_тагкир

Список таблиц

1.1 Таблица истинности материальной импликации в

классической двузначной логике

5.1 Сравнение времен работы реализаций методов з.11зрес1;_с1:1ге^ и 1пзрес1:_с^ на реальных данных из хранилища 11С1

Список листингов

5.1 Функция remove_html_markup

Список алгоритмов

4.1 check_ identity

4.2 find_algebra

5.1 inspect_direct

Введение диссертации (часть автореферата) на тему «Построение импликативных зависимостей для аналитического описания предметных областей и обнаружения ошибок в данных»

1 Введение

Историческую основу современной логики образуют две теории дедукции, созданные в 4 в. до н. э. древнегреческими мыслителями: одна — Аристотелем, другая — его современниками и философскими противниками, диалектиками мегарской школы. Преследуя одну цель — найти "общезначимые" законы логоса, о которых говорил Платон, они двигались разными путями к этой цели. Аристотель [67] на своем пути создал весьма ограниченную по своим возможностям, но зато законченную теорию - силлогистику. Силлогистика (от греч. "выводящий умозаключение") - теория логического вывода, исследующая умозаключения, состоящие из так называемых категорических высказываний (суждений). Высказывание, в котором утверждается, что все предметы класса обладают или не обладают определенным свойством, называется общим (соответственно, общеутвердительным или общеотрицательным). Высказывание, в котором утверждается, что некоторые предметы класса обладают или не обладают определенным свойством, называется частным (соответственно частноутвердительным или частноотрица-тельным). По Аристотелю, все простые высказывания делятся на следующие шесть типов: единичноутвердительные; единичноотри-цательные; общеутвердительные; общеотрицательные: частноутвер-дительные; частноотрицательные. Аристотелев силлогизм - это схема для логического вывода, состоящая из трех простых высказываний, каждое из которых принадлежит одному из определенных выше типов. Первые два высказывания называются основаниями, третье - выводом.

Задача аристотелевой силлогистики, блестяще решенная самим Аристотелем, состоит в том, чтобы обнаружить все те силлогизмы

(схемы умозаключений), которые справедливы, то есть представляют собой логические следования. Таких силлогизмов, как установил Аристотель, имеется ровно 19, остальные — неверны. При этом 4 из 19 правильных силлогизмов оказываются условно правильными. В рамках силлогистики впервые была реализована идея алгоритмизации вывода заключений. В качестве доказывающего правила в верных силлогизмах применяется введенное Аристотелем основное правило вывода в исчислении высказываний "отделение вывода" (разрешающее при истинности высказываний "А" и "если А, то В" "отделить" высказывание "В", modus ponens в современной нотации). Разберем пример.

Пример 1.0.1.

Каждый человек смертен.

Сократ человек.

Сократ смертен.

Первое основание силлогизма ("Каждый человек смертен.") представляет собой общеутвердительное высказывание. Чтобы непосредственно применить правило отделения вывода, первое высказывание можно переформулировать таким образом: "Если (кто-то) человек, то (он) смертен." Второе высказывание - единичноутверди-тельное, устанавливает факт того, что Сократ является человеком. Из этих двух оснований можно "отделить" единичноутвердительный вывод о том, что Сократ смертен.

Несмотря на значимость доказывающего правила, в настоящей работе ключевую роль играет понятие условного высказывания ("если А, то В"), или, в терминах Аристотеля, общеутвердительное высказывание. Условное высказывание тесно связано с законом отделения вывода, однако не следует их путать. Условное высказывание, как логическое выражение, может само принимать значения истины или лжи. Отделение вывода (правило вывода) утверждает, что во всех случаях, когда исходные основания верны ("А" и "если А. то В"), вывод также будет верным ("Б"). Вернемся к Примеру 1.0.1, выводящему смертность Сократа. Из двух оснований: смертности л ro-

дей и того, что Сократ является человеком, устанавливается факт, что Сократ смертен. Для установления этого факта было использовано правило отделения вывода. Истинность вывода зависит лишь от истинности условий, но не от самого правила. В этом примере, как упомянуто выше, присутствует и условное высказывание "Если человек, то смертен". В отличие от правила отделения вывода, можно говорить об истинности или ложности условного высказывания. В данном случае, исходя из всех имеющихся сведений, условное высказывание является истинным.

Разберем другой пример, где в качестве одного из оснований выступает неверное утверждение.

Пример 1.0.2.

Все лебеди белые.

Сигнус Атратус лебедь.

Сигнус Атратус белый.

В данном случае устанавливается факт того, что Сигнус Атратус имеет белый окрас. Однако, данный факт не является верным (Сигнус Атратус - вид лебедей, обладающих черным окрасом). Хотя правило отделения вывода и применено корректно, условное высказывание, лежащее в основе правила, является ложным (не все лебеди белые).

Обратимся теперь к философским оппонентам Аристотеля -философам из Мегары. Известно, что основатель мегарской философской школы Евклид из Мегары широко использовал доказательства от противного и аргументы, по форме близкие к силлогическим, и таковы многие дошедшие до нас софизмы мегариков, например, софизм Евбулида из Милета "Рогатый":

Что ты не потерял, ты имеешь. Рогов ты не терял. Стало быть, ты рогат.

Последователи Евклида Диодор Крон из Иаса и его ученик Филон из Мегары [75, 74], считая, что заключения "о присущем", выражаемые фигурами силлогизма, нуждаются в более общей осно-

ве, впервые в истории обратились к детальному анализу условных высказываний. Уже при первом рассмотрении были отмечены некоторые спорные аспекты этого понятия. В частности, соглашаясь в том, что условное высказывание истинно, когда заключение следует из посылки, Диодор Крон и Филон расходились, однако, в толковании понятия "следует". Филон полагал, что условное высказывание "если А, то В" полностью определяется сводом истинностных значений. Таблица истинности материальной импликации задается следующим образом ("И" - истинно, "Л" - ложно):

Ж # а - я мЛ -ИД !

и ч И

л

?и1 # * и

м * * и

Таблица 1.1: Таблица истинности материальной импликации в классической двузначной логике.

В современной науке редко используют термин "условное высказывание". Чаще используют более поздний термин "импликация", который берет начало в латинском языке от слова "¡трНса^о", означающего "связь"; импликация обозначает конкретный тип связи, по своему применению приближенного к условному высказыванию "если А, то В"; А называют посылкой импликации. В - заключением. Определенное Филоном условное высказывание носит название "материальной импликации". Как следует из Таблицы 1.1, материальная импликация является ложной только в том случае, если А истинно, а В ложно. Следует отметить, что таким образом определенная материальная импликация не лишена парадоксов. В частности, выделяют следующие парадоксы (в данной работе для обозначения

логического отрицания используется горизонтальная черта над символом, например, а):

1. а —У (а —Ь), из ложной посылки следует любое утверждение;

2. а —> (Ь —> а), верное заключение следует из любой посылки;

3. (а —6) V (6 —> с), в некотором смысле, этот пункт является комбинацией двух предыдущих, ведь если Ь истинно, то оно следует из любого а (по 2), а если Ь ложно, то из него следует любое с (по 1);

4. (а —)■ Ь) —>■ (аЛб), если одно утверждение не является следствием другого, то первое обязательно истинно, а второе ложно.

Данные парадоксы являются следствием строгого функционального определения импликации, не учитывающего содержания утверждений. Данный аспект был отмечен еще учителем Филона Диодором, который утверждал, что В следует из А, когда условное высказывание "если А, то В" необходимо, так что нельзя утверждать в зависимости от случая, что иной раз оно истинно, а иной раз нет, если А и В одни и те же высказывания. Хотя и другие авторы предлагали другие виды импликаций (например, "строгая импликация" [17] или "релевантная импликация" [6]), позволяющие избежать описанных выше парадоксов, материальная импликация остается наиболее популярной трактовкой импликации. Это связано прежде всего с простотой ее определения (таблица истинности) и интерпретации.

Рассматриваемые в рамках данной работы импликации имеют строго определенную структуру. В них не встречаются дизъюнкции импликаций (как в Парадоксе 3) или отрицание импликации в посылке (как в Парадоксе 4). Парадокс 2 не доставляет затруднений, ведь импликации с безусловно верными утверждениями редко представляют интерес. Затруднения возникают лишь с Парадоксом 1, учет которого требует в некоторых случаях дополнительного рассмотрения (см. раздел 5.2.4).

Для обозначения импликации используются разные символы,

например: Э,—(стрелки могут быть направлены и в другую сторону). Далее в данной работе, за исключением специально оговоренных случаев, используется термин "импликация" в значении именно материальной импликации, а для обозначения импликации используется символ "—>■".

Таким образом импликации являются удобной формой для описания логических взаимосвязей между исследуемыми сущностями. Интересно, что в рамках классической двузначной логики, используя только две логические связки: импликацию и отрицание - можно выразить любое логическое утверждение. Более привычным является, однако, описание объектов через присущие им черты, чем через перечисление тех черт, которыми они не обладают. Поэтому, хотя большинство методов, используемых в данной работе, могут быть тривиально адаптированы для работы и с отрицаниями, с целью сохранения простоты и интуитивности интерпретации преимущественно рассматриваются импликации без отрицания. Исключение составляет методы нахождения ошибок (глава 5), в которых для полноты нахождения ошибок рассматриваются импликации с отрицаниями в заключении.

Еще перед выбором сущностей для изучения выбирают некоторую предметную область - область знаний, в рамках которых предполагается описывать изучаемые сущности и их признаки. В данной работе изучаются методы построения взаимосвязей в предметной области для ее структуризации и нахождения внутренних закономерностей. С этой целью ищется множество всех верных им-пликативных зависимостей между изучаемыми признаками сущностей предметной области. Как уже отмечалось ранее, рассматриваются импликации без отрицания, хотя обобщение тривиально, но нецелесообразно. Описанное множество всех истинных в предметной области импликаций обозначается в настоящей работе термином "импликативная теория". В импликативной теории предметной области содержатся все истинные импликации и не содержится ни одной ложной импликации.

Важность и общность такого подхода видны на примере био-

логической систематики - научной дисциплины, в задачи которой входит разработка принципов классификации живых организмов и практическое приложение этих принципов к построению системы. Построение импликативной теории биологических видов - основная задача биологической систематики. Пример импликации, входящей в импликативную теорию биологических видов:

{жилкование сетчатое, две семядоли, количество частей

цветка кратно четырем, корневая система стержневая}

—У класс: двудольные.

1.1 Анализ формальных понятий

В последнее время широкое распространение получили различные инструменты для автоматического доказательства и проверки им-пликативных (и не только) связей в предметных областях [20, 47, 11]. Однако до начала нахождения доказательств теорем и до проверки их правильности необходимо породить гипотезы. Выдвижение гипотез является наиболее творческой частью построения теории и потому наиболее трудно алгоритмизируемой. От содержания этих гипотез зависит, насколько "интересной" будет разработанная теория, от "полноты" множества доказанных теорем зависит степень разработанности теории. Эту задачу позволяет решить Анализ Формальных Понятий (АФП) - область на стыке математики, информатики и философии [31]. Стандартным представлением данных в АФП является бинарная таблица (формальный контекст), содержащая отношения между множеством (формальных) объектов и (формальных) признаков. Отношение формализует наличие или отсутствие у объекта соответствующего признака. Далее по этому отношению строится алгебраическая решетка, называемая "решеткой понятий".

Интересно отметить общий философский подтекст, присущий как материальной импликации, так и АФП. В случае работы с материальной импликацией, нет необходимости учитывать внутреннюю природу или структуру исследуемой сущности, ведь материальная

>

импликация определяется чисто функционально. В АФП используются схожие идеи, ведь сущности - объекты и признаки - описываются только внешним образом, через их взаимосвязь с другими сущностями. Оба подхода находятся в строгом соответствии с традициями философии прагматизма, в основе которой лежит идея описания сущностей через их взаимодействие с окружающим миром. Основатель этого философского течения Чарльз Сандерс Пирс так описывал его суть [54]:

Примем во внимание, какой практический эффект может быть связан с данным объектом, и наше понимание этого объекта будет состоять в совокупности наших знаний о его практических приложениях.

Основатель АФП Рудольф Вилле отмечал в своих работах влияние философии прагматизма. Рудольф Вилле следующими словами описывал АФП [71]1:

Цель и значение АФП как математической теории понятий и понятийных иерархий заключается в поддержке рациональной коммуникации между людьми посредством математической разработки подходящих понятийных структур, которые могут быть логически активированы.

Разработанная в рамках АФП методология позволяет компактно представить импликативную теорию исследуемой области в виде базиса импликаций, из которого будут следовать все верные импликации. Значимость такого представления трудно переоценить, ведь базис позволяет выделить наиболее "важные" взаимосвязи и спрятать те, которые являются их следствием. Это свойство крайне полезно при анализе импликативной теории. Кроме того, базисная форма записи обладает еще одним преимуществом. Пусть дано некоторое множество признаков из предметной области. Тогда, с использованием базиса импликаций, все возможные следствия из данного множества признаков можно найти за время, линейное относительно

1 Перевод автора.

размера входного множества признаков.

Методы АФП полезны в самых различных областях науки и техники, в задачах, где интерес представляют строгие логические связи между признаками [86, 68, 32, 19]. Импликативные зависимости, получаемые при таком исследовании, обычно представляют самостоятельный интерес. Известно применение методов АФП для решения задач в токсикологии [15], в химии [44], в интернет-рекламе [35]. Обзор методов АФП для анализа данных можно найти в [43]. В работах [68, 32] АФП применялся для построение иерархии классов в программировании, а в работе [19] с помощью методов АФП решался задач локализации ошибки в программном коде.

Однако существующие методы не являются достаточно гибкими для применения, и процесс автоматизации такого исследования недостаточно хорошо изучен и проиллюстрирован, что препятствует дальнейшему распространению методологии. Например, хорошо известно, что получаемая импликативная теория будет верной только в том случае, если при задании или нахождении отношения между объектами и признаками не были допущены ошибки. Методы АФП являются очень чувствительными к ошибкам. В том случае, если данные поступают из разных источников и не являются надежными, исключать наличие ошибок нельзя. Для расширения области применения методов в этой работе будет разработан инструментарий для нахождения ошибок.

Ограничения для применения АФП видны при описании в терминах теории слабо формальных систем. "Предметная область -некоторые объекты и отношения между ними" [85]. Такой подход описания внешнего мира находится в полном соответствии с позициями философии прагматизма. В рамках АФП из всех возможных отношений предметной области рассматриваются только бинарные отношения. В связи с этим возникает и ограничение для применения рассматриваемой методологии: необходимо, чтобы описание предметной области моделью, учитывающей только бинарные отношения из предметной области, было оправдано с точки зрения адекватности модели и поставленных задач. Так, например,

для изучения демократических институтов и прав человека в обществе использование модели, учитывающей только бинарные отношения между "демократическими системами" и их признаками, нельзя считать оправданными. Однако для выделения новых типов демократических систем и систематизации изучения предметной области использование такой модели оправдано [86]. В терминах теории слабо формальных систем метод исследования признаков может рассматриваться как некоторый радикал, предназначенный для решения задачи построения импликативной теории предметной области или отдельных подзадач, которые при этом появляются. К их числу относятся, например, такие как пополнения локальной базы данных новыми объектами, систематизации нахождений имплика-тивных взаимосвязей в предметной области, построения базиса импликаций.

Схожим примером применения решеток для решения прикладных задач является теория LP-структур (Lattice-Production Structure). Разница двух подходов отмечается в работе [79].

• В LP-структуре бинарное отношение задается на единственном общем множестве - абстрактной решетке. В теории АФП оно действует из одного множества в другое, причем эти два множества имеют различное происхождение (множество объектов и множество признаков). По этой причине в АФП не может идти речь о транзитивном или логическом замыкании заданного отношения. При таком подходе рассматриваются лишь замыкания множеств объектов и признаков.

• В LP-структуре имеется произвольная решетка элементов, на которой задано еще одно отношение. В АФП элементами рассматриваемой решетки являются пары отношения, что, тем не менее, сводится к решетке множеств на первом универсуме (сопряженно - на втором).

• АФП рассматривает одно единственное отношение. Импликация генерируется самим отношением, порождающим решетку, и в конечном счете сводится к вложению множеств (объектов или признаков). Данная импликация, как и сама решетка понятий, ациклична, что используется соответствующими алгоритмами. В ЬР-структуре импликация заменена вторым независимым отношением произвольной структуры.

• АФП имеет собственную обширную и менее абстрактную терминологию («объекты», «признаки», «понятия» и другие).

Из изложенного выше и анализа публикаций следует, что общих приложений у этих двух теорий практически нет, несмотря на иногда похожие формулировки решаемых в их рамках задач.

Обзор других методов использования решеток для представления знаний можно найти в [52, 70].

1.2 Обнаружение зависимостей в данных

Практически во всех областях науки обнаружение зависимостей в данных явно или неявно играет важную роль. Даже в таких далеких от математики и информатики областях науки, как история, главные цели состоят "... в том, чтобы попытаться дать рациональное объяснение прошлому, установить причинно-следственные связи в последовательности событий, понять мотивы действий исторических личностей, соотнести закономерность и случайность исторических эпизодов, структурировать историческое время" [84]. В естественных науках, таких как физика, химия, биология, основным объектом исследования являются законы природы, создаются ме-

тоды по получению и обработки данных для выявления и анализа этих законов. Например, одни из первых физических законов, записанных в математической форме, были перечисленные далее законы Кеплера.

1. Планеты движутся вокруг Солнца по вытянутым эллиптическим орбитам, причем Солнце находится в одной из двух фокальных точек эллипса.

2. Отрезок прямой, соединяющий Солнце и планету, отсекает равные площади за равные промежутки времени.

3. Квадраты периодов обращения планет вокруг Солнца относятся как кубы больших полуосей их орбит.

Открытие этих законов было результатом анализа астрономических наблюдений Тихо Браге [77]. Таким образом, Иоганн Кеплер один из первых раз в истории человечества решил задачу извлечения численных зависимостей из экспериментальных данных.

В решенной Кеплером задаче, как и в большинстве исследований социальных, экономических и природных законов часто необходимо определить количественные характеристики зависимостей. Кроме количественной оценки параметров взаимосвязей в ряде практических задач возникают задачи поиска качественных и логических взаимосвязей. Раздел наук, изучающий методы нахождения взаимосвязей, называется data mining. "Data Mining - это процесс обнаружения в сырых данных ранее неизвестных, нетривиальных, практически полезных, доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности" [16].

Для целей нахождения количественных параметров взаимосвязи используются методы регрессионного анализа, такие как метод наименьших квадратов или метод максимального правдоподобия [26]. В постановках задаче для обоих методов некоторые необходимые параметры предполагаются данными, поэтому для использования методов пользователю необходимо некоторое дополнительное априорное знание о предметной области. Такое требование вообще

характерно для задач оценки количественных взаимосвязей. Применяемые в настоящей работе методы не предполагают никаких априорных знаний об исследуемой предметной области, а потому находят применения в таких задачах, где не могут быть использованы методы регрессионного анализа.

Важным примером задачи поиска качественных зависимостей является задача классификации. Пусть имеется множество объектов, разделённых некоторым образом на классы, и множество новых объектов, класс которых неизвестен. Требуется научиться классифицировать новые объекты. Деревья решений [56] и метод ближайших соседей [36] являются примерами методов решения задач классификации, наиболее близкими к методам, используемым в настоящей работе.

Деревья решений. Дерево состоит из листьев и веток. На ветках дерева решения записаны атрибуты, от которых зависит класс объекта, в листьях записаны классы. Чтобы классифицировать новый объект, надо спуститься по дереву до листа и выдать соответствующее значение.

Методы анализа формальных понятий тоже можно использовать для решения задачи классификации. Для этого один из признаков обозначают как целевой, он определяет принадлежит ли новый объект к интересующему классу. Затем используют множество всех найденных импликаций контекста для того, чтобы по имеющимся в наличии нецелевым признакам выяснить значение целевого признака. В том случае, если у объекта неизвестны и другие признаки, кроме целевого, то дерево решений может не дать никакого решения, если на ветке или в корне дерева встретился отсутствующий признак. Множество импликаций является в этом смысле более гибким инструментом для классификации, так как позволяет классифицировать, используя только имеющиеся признаки.

Метод ближайших соседей. Объекты помещаются в пространство признаков, где их положении определяется наличием или отсутствием соответствующих признаков. Основным принципом ме-

тода ближайших соседей является то, что объект присваивается тому классу, который является наиболее распространённым среди соседей данного элемента. Соседи берутся исходя из множества объектов, классы которых уже известны. Типично использование метода ближайших соседей не для задач, рассматриваемых в настоящей работе, а для задач с числовыми значениями признаков. Однако в главе 5 рассмотрены некоторые сходства разработанных в рамках данного исследования методов с методом ближайших соседей.

Другим примером качественного выделения зависимостей является задача кластеризации. Под кластером обычно понимается часть данных (в типичном случае - подмножество объектов или подмножество переменных, или подмножество объектов, характеризуемых подмножеством переменных), которая выделяется из остальной части наличием некоторой однородности ее элементов [80, 48]. Необходимо выделить кластеры в имеющихся данных. Типично применение методов кластеризации для структуризация данных или визуализация структуры системы, хотя есть другие применения, напри-

мер, выявление связей между такими аспектами развития системы, как вход/выход, структура/функция, мотивация/действие и пр.

Однако в настоящей работе рассматриваются другая задача, а именно - поиск ассоциаций в данных. Под ассоциациями понимаются зависимости на признаках объектов. Типичным примером таких ассоциаций являются ассоциативные правила [1]. Такие правила показывают количественные зависимости между подмножествами признаков.

Ассоциативные правила. Пусть / = {¿i, ¿2, • ••, in} ~ множество признаков, D — {ti,t2,... ,tm} - множество записей из базы данных. Каждая запись D содержит подмножество признаков из I (запись соответствует формальному объекту, глава 2.2). Ассоциативное правило записывается как X => Y, где X, Y С I и X П Y = 0. Поддержкой ассоциативного правила называют количество записей, содержащих X. Достоверность ассоциативного правила определяется как отношение количества записей, в которых встречается X U Y, к количеству записей, в которых встречается только X. Таким образом, импликации - это частный случай ассоциативных правил, достоверностью которых равна 1. На практике, однако, ассоциативные правила применяются в задачах, где не подразумевается строгая логическая связь, в отличие от исследований из настоящей работы.

Список литературы диссертационного исследования кандидат наук Ревенко, Артем Викторович, 2013 год

Литература

[1] R. Agrawal, R. Srikant, et al. Fast algorithms for mining association rules. Proc. 20th Int. Conf. Very Large Data Bases, VLDB, 1215:487-499, 1994.

[2] M. Aigner. Combinatorial Theory. Springer-Verlag, Berlin, 1997.

[3] M.A. Aizerman and F.T. Aleskerov. Theory of Choice. North-Holland/Elsevier, Amsterdam, 1995.

[4] M.A. Aizerman and A.V. Malishevskiy. General theory of best variants choice. IEEE Trans. Automatic Control, AC-26(5):1030-1040, 1981.

[5] A. Albano and A. P. do Lago. A convexity upper bound for the number of maximal bicliques of a bipartite graph. Discrete Applied Mathematics, 2013.

[6] A.R. Anderson, N.D. Belnap Jr, J.M. Dunn, et al. Entailment: The logic of relevance and necessity, vol. II. Princeton University Press, Princeton, 1992.

[7] M.A. Babin and S.O. Kuznetsov. Computing premises of a minimal cover of functional dependencies is intractable. Discrete Applied Mathematics, 161(6):742-749, 2013.

[8] K. A. Baker, P. C. Fishburn, and F. S. Roberts. Partial orders of dimension 2. Networks, 2(l):ll-28, 1972.

[9] V.I. Balakshii and A.Revenko. Acousto-optic interaction in cells with wedge-shaped transducers excited at high harmonics. Acta Acustica united with Acustica, 96(5):837—842, 2010, 0.8 п. л. (личный вклад 0.6 п. л.).

[10] V.I. Balakshii and A. Revenko. Acoustooptic cells with wedge-shaped piezoelectric transducers excited at high-order harmonics. Journal of Communications Technology and Electronics, 55:831837, 2010. 10.1134/S1064226910070132.

[11] P. Baumgartner, A. Fuchs, H. de Nivelle, and C. Tinelli. Computing finite models by reduction to function-free clause logic. Journal of Applied Logic. 2007.

[12] K. Beck. Test-driven development: by example. Addison-Wesley Professional, 2003.

[13] G. Birkhoff. On the structure of abstract algebras. In Mathematical Proceedings of the Cambridge Philosophical Society; volume 31, pages 433-454. Cambridge Univ Press, 1935.

[14] G. Birkhoff. Lattice Theory. Am. Math. Soc., Providence, RI, 3rd edition, 1967.

[15] V.G. Blinova, D.A. Bobrynin, V.K. Finn, S.O. Kuznetsov, and E.S. Pankratova. Toxicology analysis by means of jsm-method. Bioinformatics, 19:1201-1207, 2003.

[16] P. Cabena, P. Hadjinian, R. Stadler, J. Verhees, A. Zanasi, California). International Business Machines Corporation (San Jose, and California). International Technical Support Organization (San Jose. Discovering data mining: from concept to implementation, volume 1. Prentice Hall Upper Saddle River, NJ, 1998.

[17] L. Carroll. Symbolic Logic: The Game of Logic, volume 1. DoverPublications. com, 1958.

[18] N. Caspard and B. Monjardet. The lattice of closed systems, closure operators and implicational systems on a finite set: survey. Discrete and Applied Mathematics, 127 (2):241-269, 2003.

[19] P. Cellier, M. Ducassé, S. Ferré, and O. Ridoux. Formal concept analysis enhances fault localization in software. In R. Medina and S. Obiedkov, editors, ICFCA, volume 4933 of Lecture Notes in Computer Science, pages 273-288. Springer, 2008.

[20] K. Claessen and N. Sorensson. Paradox 1.0. http: //www.cs.miami.edu/~tptp/CASC/19/SystemDescriptions. html#Paradox---1.0.

[21] H. Cleve and A. Zeller. Locating causes of program failures. In G.-C. Roman. W.G. Griswold, and B. Nuseibeh, editors. ICSE, pages 342-351. ACM, 2005.

[22] V. Danilov and G. Koshevoy. A new characterization of the path independent choice functions. Mathematical Social Sciences, 51:238-245, 2006.

[23] V. Danilov and G. Koshevoy. Choice functions and extensive operators. Order, 26:69-94, 2009.

[24] F. Dau. Implications of properties concerning complementation in finite lattices. In: Contributions to General Algebra 12 (D. Dorninger et al, eds.), Proceedings of the 58th workshop on general algebra "58. Arbeitstagung Allgemeine Algebra", Vienna, Austria, June 3-6, 1999, Verlag Johannes Heyn, Klagenfurt, pages 145-154, 2000.

[25] F. Distel and B. Sertkaya. On the complexity of enumerating pseudo-intents. Discrete Applied Mathematics, 159(6):450-466, 2011.

[26] N.R. Draper, H. Smith, and E. Pownell. Applied regression analysis, volume 3. Wiley New York, 1966.

[27] W. Fan, J. Li, S. Ma, N. Tang, and W. Yu. Towards certain fixes with editing rules and master data. Proceedings of the VLDB Endowment, 3(1):173-184, 2010.

[28] A. Frank and A. Asuncion. UCI machine learning repository http: //archive. ics. uci . edu/ml, 2010.

[29] B. Ganter. Two basic algorithms in concept analysis. Preprint-Nr. 831, 1984.

[30] B. Ganter, G. Stumme, and R. Wille, editors. Formal Concept Analysis, Foundations and Applications, volume 3626 of Lecture

Notes in Computer Science. Springer, 2005.

B. Ganter and R. Wille. Formal Concept Analysis: Mathematical Foundations. Springer, 1999.

R. Godin and P. Valtchev. Formal concept analysis-based class hierarchy design in object-oriented software development. In Ganter et al. [30], pages 304-323.

J.-L. Guigues and V. Duquenne. Families minimales d'implications informatives resultant d'un tableau de donnees binaires. Math. Sei. Hum, 24(95):5—18, 1986.

W.C. Huffman and V.S. Pless. Fundamentals of Error-Correcting Codes. Cambridge, Ma University Press, 2003.

D.I. Ignatov and S.O. Kuznetsov. Concept-based recommendations for internet advertisement. In: Belohlavek R., Kuznetsov S.O., Eds., Proc. 6th International Conference on Concept Lattices and Their Applications (CLA 2008), pages 157-167, 2008.

Y.K. Jain and V. Suryawanshi. A New Approach for Handling Null Values in Web Log Using KNN and Tabu Search KNN. International Journal of Data Mining & Knowledge Management Process, 1 (5):9—19, September 2011.

R. Jäschke and S. Rudolph. Attribute exploration on the web. ICFCA 2013, pages 19-35, 2013.

M.R. Johnson and R.A. Dean. Locally complete path independent choice funtions and their lattices. Mathematical Social Sciences, 42:53-87, 2001.

H.A. Kautz, M.J. Kearns, and Bart Selman. Reasoning with characteristic models. In the Eleventh National Conference on Artificial Intelligence (AAAI-93), pages 1-14, 1993.

P. Kestler. Strukturelle Untersuchungen eines Varietätenverbandes von Gruppoiden mit unärer Operation und ausgezeichnetem Element. PhD thesis, TU Bergakademie, Freiberg, 2013.

G.A. Koshevoy. Choice functions and abstract convex geometries.

Mathematical Social Sciences, 38(5):35-44, 1999.

[42] S.O. Kuznetsov and S. Obiedkov. Some decision and counting problems of the duquenne-guigues basis of implications. Discrete Applied Mathematics, 156(ll):1994-2003, 2008.

[43] S.O. Kuznetsov and J. Poelmans. Knowledge representation and processing with formal concept analysis. In: Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 3:200-215, 2013.

[44] S.O. Kuznetsov and M.V. Samokhin. Learning closed sets of labeled graphs for chemical applications. In: Proc. 15th Conference on Inductive Logic Programming (ILP 2005), Lecture Notes in Artificial Intelligence (Springer), 2635:190-208, 2005.

[45] L., C. Pech, and H. Reppe. Generalizations of boolean algebras, an attribute exploration. Mathematica Slovaca, 56(2): 145-165, 2006.

[46] S.A. Maguire. Writing solid code: Microsoft's techniques for developing bug-free с programs. Redmond, Wash.: Microsoft Press,! cl993, 1, 1993.

[47] W. McCune. Prover9 and mace4. http://www.cs.unm.edu/~mccune/prover9/, 2005-2010.

[48] B. Mirkin. Mathematical Classification and Clustering. Kluwer Academic Publisher, 1996.

[49] B. Monjardet and V. Raderanirina. The duality between the anti-exchange closure operators and the path independent choice operators on a finite set. Mathematical Social Sciences, 41:131— 150, 2000.

[50] H. Moulin. Choice functions over finite sets: a summary. Soc. Choice Welfi, 2:147-160, 1985.

[51] S. Obiedkov and V. Duquenne. Attribute-incremental construction of the canonical implication basis. Annals of Mathematics and Artificial Intelligence, 49(1-4):77-99, April 2007.

[52] F.J. Oles. An application of lattice theory to knowledge representation. Theor. Comput. Sci., 249:163-196, 2000.

[53] J.G. Oxley. Matroid Theory. Oxford University Press, New York, 1992.

[54] C.S. Peirce. Collected papers of charles sanders peirce, volume 3. Harvard University Press, 1974.

[55] C.R. Plott. Path independence, rationality and social choice. Econometrica, 41:1075-1091, 1973.

[56] J.R. Quinlan. Induction of decision trees. Machine learning, - 1(1) :81—106, 1986.

[57] A. Revenko. Detecting mistakes in binary data tables. Automatic Documentation and Mathematical Linguistics, 47(3):102-110, 2013.

[58] A. Revenko. Debugging programs using formal concept analysis. In FCAIR 2013, pages 105-112. CEUR, 2013, 0.8 п. л. (личный вклад 0.8 п. л.).

[59] A. Revenko. Debugging program code using implicative. In FCA4AI 2013, pages 27-39. CEUR, 2013, 1 п.л. (личный вклад 1 п. л.).

[60] A. Revenko and S.O. Kuznetsov. Attribute exploration of properties of functions on ordered sets. In Proc. 7th International Conference on Concept Lattices and Their Applications, University of Sevilla pages 311-324, 2010, 0.9 п. л. (личный вклад 0.6 п. л.).

[61] A. Revenko and S.O. Kuznetsov. Finding errors in new object intents. In CLA 2012, pages 151-162. CEUR, 2012, 1 п.л. (личный вклад 0.8 п. л.).

[62] A. Revenko and S.O. Kuznetsov. Attribute exploration of properties of functions on sets. Fundamenta Informaticae, 115(4):377-394, 2012, 1.2 п. л. (личный вклад 0.7 п. л.).

[63] N. Romashkin. Python package for formal concept analysis, https: / / github. com/ j upp/f ca.

[64] U. Ryssel, F. Distel, and D. Borchmann. Fast computation of proper premises. In Amedeo Napoli and Vilem Vychodil, editors, International Conference on Concept Lattices and Their

Applications, pages 101-113. INRIA Nancy - Grand Est and LORIA, 2011.

[65] A.K. Sen. Choice functions and revealed preference. Review of Economics Studies, 38:307-313, 1971.

[66] E.-L. Silva-Ramirez, R. Pino-Mejias, M. Lopez-Coello, and M.-D. Cubiles-de-la Vega. Missing value imputation on missing completely at random data using multilayer perceptrons. Neural networks : the official journal of the International Neural Network Society.; 24(1):121—129, January 2011.

[67] R. Smith. Aristotle, Topics: Books I and VIII with Excerpts from Related Texts. Oxford University Press on Demand, 1997.

[68] G. Snelting and F. Tip. Reengineering class hierarchies using concept analysis. SIGSOFT Softw. Eng. Notes, 23(6):99-110, November 1998.

[69] Q. Song and M. Shepperd. A new imputation method for small software project data sets. Journal of Systems and Software, pages 1-24, 2007.

[70] J. F. Sowa. Knowledge Representation: Logical, Philosophical and Computational Foundations. Brooks Cole Publishing Co., 2000.

[71] R. Wille. Formal concept analysis as mathematical theory of concepts and concept hierarchies. In Ganter et al. [30], pages 1-33.

[72] A. Zeller. Software debugging course, https: //www. udacity. com/ course/cs259.

[73] A. Zeller and R. Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Trans. Software Eng., 28(2): 183-200, 2002.

[74] A.C. Богомолов. Становление античной диалектики Москва Мысль, 1982.

[75] В.В. Воробьев. Импликация и модальность у Диодора Крона. М., 1976.

[76] П. Кон, Т.М. Баранович, and А.Г. Курош. Универсальная алгебра: Пер. с англ. Мир, 1968.

[77] П.С. Кудрявцев. Курс истории физики: Учеб. пособие для студентов пед. ин-тов по физ. спец. Просвещение, 1982.

[78] А.И. Мальцев. Алгебраические системы. Москва, 1970.

[79] С.Д. Махортов. Теория LP-структур для построения и исследования моделей знаний продукционного типа PhD thesis, Воронежский государственный университет, 2009.

[80] Б.Г. Миркин. Методы кластер-анализа для поддержки принятия решений: обзор. Закон, 3:99-107, 2011.

[81] П.С. Новиков. Об алгоритмической неразрешимости проблемы тождества слов в теории групп. Труды Математического института им. В А Стеклова, 44(0):3-143, 1955.

[82] А. Ревенко. Нахождение ошибок в бинарных таблицах данных. Научно-техническая информация. Серия 2. «Информационные процессы и системы», 6:10-18, 2013, 1 п.л. (личный вклад 1 п.л.).

[83] В. В. Рыбаков. Независимые базисы для правил, допустимых в предтабличных логиках. Алгебра и логика., 39:206-226, 2000.

[84] И.М. Савельева and A.B. Полетаев. Становление исторического метода: Ранке, Маркс, Дройзен. Диалог со временем, 18:70-96, 2007.

[85] А. В. Чечкин. Математическая информатика. Наука, Гл. ред. физ.-мат. лит., 1991.

[86] С.А. Объедков и др. Разработка дискретных математических моделей для политического анализа в области изучения демократических институтов и прав человека, http://www.hse.ru/ science/scifund/proekt_ts/dis_mat/.

Автор выражает глубокую благодарность научному руководителю, доктору физико-математических наук Кузнецову Сергею Олеговичу за постановку задач, постоянное внимание и помощь в работе. Автор выражает глубокую благодарность профессору Васенину Валерию Александровичу за плодотворные обсуждения, критические замечания и помощь в работе. Автор выражает глубокую благодарность профессору Бернарду Гантеру за плодотворное обсуждение и внимание к работе.

Посвящаю эту работу моей маме, Оксане Всеволодовне Федоровой и благодарю ее за неустанную поддержку на протяжении многих лет, без которой ни эта, ни многие другие работы никогда бы не были написаны.