авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 |

«ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ...»

-- [ Страница 2 ] --

GenerateRandomClosedSet() 1 X random subset of 2 X (, ) 3 return X Здесь LinClosure – линейный алгоритм вычисления замыкания в базисе импликаций (см. [19, 90]).

Для того, чтобы оценить время работы алгоритма допустим, что операторы замыкания приближенного базиса и формального контекста K при выборе случай ного подмножества не совпадают с вероятностью как минимум (т.е. ( = ) ). Тогда в среднем придется сделать не более (математическое ожидание геометрической случайной величины) шагов, пока не встретится подмножество, на котором операторы замыка ния не совпадают. Последнее означает, что, если операторы замыкания не совпадают с вероятностью больше, то математическое ожидание коли чества последовательных шагов алгоритма между вызовами функции не больше 1. Таким образом, мы получили:

Теорема 3. Математическое ожидание времени работы алгоритма, до достижения точности 1 для контекста K = (,, ), равно (| || | · (||| | + | || |) · 1 ), где – минималь ный базис импликаций.

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

2.8.1. Результаты экспериментов Приведем результаты экспериментов вычисления приближенного ба зиса на реальных данных: базы данных Chess, Zoo и P.-Op. P (Post operative Patients) взяты с хранилища данных UCI [100]. База данных Grav. пред ставляет описание британских гравюр из коллекции ГМИИ им. А.С. Пуш кина. База данных Grav_a состоит из описаний гравюр для каждого кон кретного автора и получена из базы данных Grav.

|| || | | | | база данных | | Chess 3197 39 76 43,1 0,9988 Zoo 101 28 43 3,3 0,9999 1, P.-Op. P. 90 25 85 5,0 0,9989 2, Grav 707 473 53 233,4 0,9999 Grav_a 707 156 39 286,6 0,9999 92, Таблица 2.2. Результаты вычисления приближенного базиса.

– приближенный базис импликаций – точный базис импликаций – оценка вероятности ( = ) того, что для случайного подмножества замыкания совпадают – время построения точного базиса алгоритмом Гантера – время построения приближенного базиса Как видно на практических данных приближенный базис дает на много более сжатое представление данных и требует меньшее время по строения, чем минимальный базис импликаций. Несмотря на это оценка вероятности совпадения операторов замыкания приближенного базиса и формального контекста остается очень высокой.

3. Базисы импликаций и общие содержания 3.1. Связь базиса импликаций с общими содержаниями Пусть даны два формальных контекста с общим множеством призна ков: K1 = (1,, 1 ) с базисом импликаций (не обязательно минималь ным) J1 и контекст K2 = (2,, 2 ) с базисом импликаций J2. Очевидно, что множество их общих содержаний является системой замыканий [54].

Поэтому мы можем рассмотреть контекст K = (,, ), объектные со держания, которого будут неразложимыми элементами системы замыка ний общих содержаний. Будем называть контекст K, контекстом общих содержаний. Рассмотрим набор импликаций J = J1 J2. Ясно, что, если какое-то подмножество замкнуто в контексте K1, то оно удовлетворяет всем импликациям из J1, аналогично для K2 и J2. Таким образом, любое общее содержание будет удовлетворять всем импликациям из J. В обратную сто рону – пусть какое-то множество удовлетворяет всем импликациям из J, тогда оно будет замкнуто в базисе J1 и замкнуто в базисе J2 и следователь но будет общим содержанием. Такие же рассуждения можно обобщить на случай нескольких контекстов, получая следующий важный результат:

Теорема 4. Пусть даны контексты K1, K2,..., K с общим множеством при знаков и с базисами импликаций J1, J2,..., J, соответственно. Тогда множество импликаций J1 J2... J будет базисом импликаций контек ста общих содержаний.

3.2. Общий метод поиска минимального базиса импликаций че­ рез общие содержания Используя теорему 4, можно предложить следующий общий алгоритм построения минимального базиса импликаций.

FindMinBase(K = (,, )) 1 Представить контекст K множеством контекстов K1, K2,..., K, для которых K будет являться контекстом общих содержаний 2 Для каждого контекста K найти минимальный базис импликаций J.

3 J J1 J2... J 4 J () 5 return J Заметим, что шаг 1, является ключевым шагом этого алгоритма. Же лательно реализовать этот шаг так, чтобы:

1. Для каждого из контекстов K существует эффективный алгоритм поиска минимального базиса.

2. Суммарный размер базисов контекстов K не сильно больше (напри мер в полиномиальное число раз) размера базиса контекста K.

3.2.1. Поиск собственных посылок через общие содержания В статье [37] был предложен квазиполиномиальный алгоритм для по иска всех собственных посылок формального контекста. Собственные по сылки задают базис импликаций (левые части импликаций будут собствен ными посылками, а правые их замыканиями). Предложенный алгоритм ос нован на лемме из [54] о том, что множество является посылкой контек ста K = (,, ) тогда и только тогда, когда найдется признак такой, что ( ) = выполнено для всех, для которых и является собственной посылкой, когда является посылкой и минимально среди всех посылок(по включению).

Оказывается, что этот алгоритм можно переформулировать как част ный случай общего алгоритма. Для каждого признака = {1,..., | | } мы построим формальный контекст K = (,, ), объектные содержания которого будут определяться следу ющим образом:

1. Для каждого объекта, такого, что в K будут объекты с / содержаниями равными:, а также {1 }, {2 },..., {| | } 2. Для каждого объекта, такого, что в K будут объекты с содержаниями из множества { {} | } / 3.3. Интенсионально связанные понятия Пусть 1 = (1,, 1 ), 2 = (2,, 2 ),..., = (,, ) – кон тексты с общим множеством признаков. Обозначим через (·) опера тор штриха контекста. Набор понятий (1, 1 ), (2, 2 ),..., (, )) соответствующих контекстов 1, 2,..., называется интенсионально связанным [77], если )11 = ( )22 = ( ··· ) = ( Таким образом, любые интенсионально связанные понятия однозначно определены множествами 1.

Рассмотрим оператор (·)*, определенный как * = 11 22...

для.

Утверждение 8. Пусть 1 = (1,, 1 ), 2 = (2,, 2 ),..., = (,, ) – контексты с общим множеством признаков. Тогда оператор (·)* удовлетворяет следующим свойствам:

(1) ( * ) =, для любых и 1.

(2) (·)* является оператором замыкания.

Доказательство. (1) Действительно, ( * ) = ( ), поскольку для любого 1, следовательно 1 и отсюда ( * ). С другой стороны, 1, таким образом ( * ).

(2) Не сложно проверить, что этот оператор является оператором за мыкания:

1., for 1 i r * * (монотонность) 2. * (доказано выше) (экстенсивность) 3. ** = 1 ( * ) = 1 = * (идемпотентность) Утверждение можно обобщить на случай, когда 1, 2,..., имеют различные множества признаков 1, 2,...,. Для этого нужно просто определить :=.

= Используя оператор (·)* в качестве оракула, можно перечислить все интенсионально связанные понятия с полиномиальной задержкой, приме нив стандартные алгоритмы анализа формальных понятий (см. обзор [71]):

Norris, Next Closure, Close-by-One, и.т.д. Напомним, что алгоритм, перечис ляющий комбинаторные структуры в каком либо порядке называется алго ритмом с полиномиальной задержкой, если время его выполнения между любыми двумя последовательными структурами, которые он перечисляет, полиномиально от размера входа.

3.4. Понятия с общими содержаниями Как и в прошлом разделе, пусть 1 = (1,, 1 ), 2 = (2,, 2 ),..., = (,, ) — контексты с общим множеством при знаков, (·) обозначает оператор штриха контекста для 1.

Подмножество признаков называется общим содержанием контек стов 1, 2,...,, если оно является содержанием каждого контекста, то есть =.

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

В [44] была рассмотрена задача поиска модели из пересечения Хорнов­ ских теорий, заданных своими характеристическими моделями, более то го был получен алгоритм с полиномиальной задержкой для перечисления всех моделей из пересечения Хорновских теорий. На языке анализа фор мальных понятий Хорновская теория, заданная своими характеристиче скими моделями означает в точности систему замыканий, заданную (фор мальным) контекстом, а пересечение Хорновских теорий соответствует си стеме замыканий общих содержаний. Из результатов авторов [44] следует, что задача построения минимального (по количеству объектных содержа ний) контекста задающего систему замыканий общих содержаний, по двум заданным контекстам не может быть решена за полиномиальная время, если =.

Отметим, что авторы [44] в своей статье не интересовались операто ром замыкания (·) системы замыканий общих содержаний. Помимо того, что быстрое вычисление (·) несет в себе самостоятельный интерес, исполь зуя линейный алгоритм для вычисления (·) можно получить большинство алгоритмических результатов из [44] с такой же оценкой сложности, но бо лее коротким путем. Более того, используя алгоритм вычисления (·) как оракул, можно применять множество известных алгоритмов перечисления замкнутых множеств.

Теорема 5. Задача ВХОД Формальные контексты 1 = (1,, 1 ), 2 = (2,, 2 ),..., = (,, ) с общим множеством признаков, и множество. Контексты заданы бинарными матрицами.

ВЫХОД Замыкание множества.

может быть решена за время (| | 1 | |).

Доказательство. Рассмотрим множества = { |, }{ }, 1. Обозначим =. Мы будем поддерживать тот факт, что для любого 1, каждое общее содержание, которое содержит, может быть получено пересечением некоторых элементов из.

Предположим, что существует такой признак, что для неко торого 1 выполнено. Тогда, поскольку каждое общее содержание, которое содержит может быть получено пересечением неко торых элементов из, каждое общее содержание, содержащее, должно содержать. Следовательно, если для некоторого 1 существует, которое не содержит, мы можем обновить, удалив из него и инвариант останется выполненным. Когда ни одно такое удаление не мо жет быть выполнено, мы пытаемся найти другой элемент, который содержится во всех элементах из и так далее. Поскольку конечно, то на некотором шаге такое не найдется. Это означает, что любой элемент либо принадлежит каждому элементу каждого, либо он не принадлежит какому-то элементу из, для любого 1. Поэтому 1 = 2 =... =, 1 и 1 содержится во всех общих содержаниях, которые содержат т.е. 1 =.

GetClosure() 1 answer 2 for 1 to do remove all rows from [] that does not contain 4 for 1 to do for 1 to | | do if not answer [m] then if [][][] = true for all 1 | | then answer [] true push in shared -attributes else for each 1 | | such that not [][][] do push (, ) in not-in[] counter [][] counter [][] + 13 while shared -attributes not empty do pop from shared -attributes while not-in[] not empty do pop (object-index, context-index ) from not-in[] for 1 to | | do if not [][context-index ][object-index ] then counter [context-index ][i ] counter [context-index ][i ] if counter [context-index ][i ] and not answer [i ] then answer [i ] = true push in shared -attributes 23 return answer Псевдокод алгоритма, вычисляющего (·).

Здесь [] - это бинарная матрица, задающая отношение, counter [][] равно количеству объектов из, для которых не выполнено, shared-attributes и not-in[] могут быть реализованы как сте­ ки или как любые другие структуры данных, поддерживающие операции “вытащить"(pop) любой объект и “вставить"(push) любой объект за время (1). Не сложно заметить, что каждая клетка таблицы контекста [], будет обработана не более 3 раз. Поэтому суммарное время работы данного алгоритма равно O(суммы размеров таблиц формальных контекстов).

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

GetClosure_2() 1 answer 2 for 1 to do [] transposed relation of [] objects[i ] { [] | } for each a do |[] [][]| PQ[].(, ) if x = then push a in shared _attributes 10 while shared _attributes not empty do pop from shared _attributes answer answer {} for 1 to do removed _objects objects[i ] [][] objects[i ] objects[i ] [][] for each o removed _objects do PQ[i ].decrease_all() for each a do PQ[i ].increase(a) while PQ[i ]._() = do PQ[i ]._() push a in shared _attributes 23 return answer Псевдокод алгоритма, вычисляющего (·), когда контексты заданы списками признаков.

Операции, и для списков и можно делать за вре мя (|| + ||), используя алгоритм слияния, аналогичный алгоритму в сортировке слияниями. Следовательно, время работы выполнения строк 14 и 15 можно оценить как (|[]| + | [][]|), а новое значе ние |[]| можно оценить как (| [][]|). Поэтому для каждого 1, суммарное время выполнения строк 14 и 15 оценивается как ( 1| | | [][ ]| + | [][1 ]|) = (| []|). Если время выполнения всех операций структуры равно (1), то время выполнения цикла на строках 16–19 можно оценить как ( _ | |). Для каждого, любой объект из массива _ встречается ровно 1 раз.

Поэтому суммарное время выполнения цикла на строках 16–19 можно оце (| []|). Следовательно суммарное время работы алго нить как ритма можно оценить как ((|[]|) + (| []|)) = (|[]|).

Осталось описать устройство структуры данных. Структура данных это приоритетная очередь, которая поддерживает операции:

узнать минимум (get_min), удалить минимум (extract_min), а также опе рации - уменьшить все ключи на 1 (decrease_all) и увеличить значение клю ча, данного элемента на 1 (increase()). Если изначально все ключи при нимают только целые значения от 0 до | |, а также операции decrease_all и increase вызывается не более | | раз, то эту структуру данных мож но реализовать так, чтобы ее инициализация занимала (| |) времени, а все операции выполнялись за (1). Для этого достаточно создать массив размера 2| |, элементы которого будут хранить списки, добавляемых в структуру элементов. Также для каждого, хранимого элемента нужно за поминать где он в этом массиве и соответствующем списке находится (за вести вспомогательный массив для этого). Кроме того нужно завести две переменных: {0, 1,..., | |}, которая будет равна количеству вызовов операции decrease_all() и, которая будет равна индексу первого непустого списка. При инициализации элемент с ключом добавляется в -й список (set(,) добавляет элемент с ключом ). При вызове increase() нуж но переложить элемент из его текущего списка в список с индексом на больше текущего (список и место в списке, где находится элемент можно узнать с помощью вспомогательного массива). Операция get_min возвра щает, а при вызове extract_min необходимо увеличивать до тех пор, пока не встретится непустой список.

Таким образом мы получаем следующую теорему:

Теорема 6. Алгоритм _2() вычисляет для произвольного подмножества признаков и контекстов K1 = (1,, 1 ),..., K = (,, ) за время ( 1 | |).

Задача поиска максимального (по мощности) замкнутого множества относительно операторов (·) и (·)*, очевидно решается за полиномиаль ное время: достаточно просто проверить все объектные содержания и най ти максимальное. Но в отличие от этих операторов замыкания, аналогич ная задача поиска максимального общего содержания, отличного от (на практике это может соответствовать "максимальной схожести двух контек стов") для оператора (·) NP-полна, как показано в следующей теореме.

Утверждение 9. Задача ВХОД Два формальных контекста 1 = (1,, 1 ), 2 = (2,, 2 ), и целое число 0 | |.

ВОПРОС Существует ли такое, что =, и || ?

-полна.

Доказательство. По теореме 5 = может быть проверено за поли номиальное время, таким образом эта задача лежит в. Для доказа тельства -трудности мы сведем хорошо известную -полную задачу о минимальном покрытии (МП) к нашей. Задача МП формулируется сле дующим образом [55]:

ВХОД Конечное множество, множество его подмножеств := {1, 2,..., },, и целое число.

ВОПРОС Существует ли подмножество такое, что = и | | ?

Рассмотрим произвольное конечное множество = {1, 2,..., }, и множество его подмножеств := {1, 2,..., }, для всех 1, и целое число 0 ||. Пусть = {1, 2,..., ||+|| } 11 и 1 = {1, 2,..., || }. Теперь построим контекст 1 = (1,, 1 ), где 1 определено как: 1 для ||, если и только если и / для || тогда и только тогда, когда || =. Тогда покрытия нахо дятся во взаимно однозначном соответствии с содержаниями 1, которые не содержат ни одного, ||. Более того, для любого покрытия размера, соответствующее содержание будет размера ||.

Теперь построим контекст 2 = (2,, 2 ), где 2 = 22 2 {1, 2,..., || }, 2 определено как: для, где 1 ||, = ( {||+ }). Очевидно, множество всех содержаний этого контекста это в точности множество всех подмножеств множества, которые не пересе каются с. Следовательно существует взаимно однозначное соответствие между общими содержаниями контекстов 1 и 2 отличными от, и множеством всех покрытий. Более того минимальные покрытия соответ ствуют максимальным общим содержаниям, и наоборот. Сведение доказано и его полиномиальность очевидна.

Насколько большим может быть минимальный контекст, задающий общие содержания двух заданных контекстов? Ответ дан в следующем утверждении:

Утверждение 10. Существуют два контекста 1 и 2 такие, что множе ство их максимальных (по включению) общих содержаний экспоненциаль но относительно размеров 1 и 2.

Доказательство. Рассмотрим конечное множество = {1, 2,..., 3 }, и множество его подмножеств = 01 {{3+1, 3+2 }, {3+1, 3+3 }, 3+2, 3+3 }}. Существует ровно 3 минимальных покрытий, поскольку для любого 0 подмножество {3+1, 3+2, 3+3 } может быть покрыто только тремя спо собами, используя ровно 2 элемента из. Таким образом, если построить контексты 1 и 2 как в Утверждении 9 в соответствии с и, у этих контекстов будет 3 максимальных (по мощности) общих содержаний. Следствие. Существуют два контекста 1 и 2 такие, что минимальное количество объектов в контексте с оператором замыкания (·) экспоненци ально относительно размеров 1 и 2.

3.5. Сцепления и общие содержания В [54] было дано следующее определение сцеплений Определение 2. Пусть 1 = (1, 1, 1 ) и 2 = (2, 2, 2 ) — фор мальные контексты. Отношение 1 2 называется сцеплением из 1 = (1, 1, 1 ) в 2 = (2, 2, 2 ), если – объем контекста 1 для любого 2, и – содержание контекста 2 для любого 1.

1 1 1 2 Напомним некоторые определение из [54]. Прямое произведение кон текстов 1 = (1, 1, 1 ) и 2 = (2, 2, 2 ) определяется как 1 2 := (1 2, 1 2, ) где (1, 2 )(1, 2 ) 1 1 1 or 2 2 2.

Контрноминальная шкала – это контекст (,, =).

Двойственный контекст для контекста = (,, ) определяется как = (,, ), где.

Утверждение 11. Отношение 1 2 является сцеплением из кон текста 1 = (1, 1, 1 ) в контекст 2 = (2, 2, 2 ) тогда и только тогда, когда является общем содержанием контекстов 1 2 и (1 2 ).

Доказательство. Пусть 1 2 — общее содержание контекстов 1 2 = (1 2, 1 2, 2 ) и (1 2 ) = (1 2, 1 2, 1 ).

Поскольку — содержание контекста 1 2, то {(, ) | (, )2 (, )} = (,) Таблица 3.1. Пример сцепления двух контекстов ({(, ) | 2 } {(, ) | = }), = () взято по всем таким, что (, ) для где (, ) 1 2, некоторого, и () = { | (, ) }. Следовательно, если = для некоторого, рассмотрев пересечение, мы получим = () 2, т.е. замкнуто в 2, и если = для всех, взяв, получим = 2.

Аналогично, поскольку – содержание контекста (1 2 ), мы можем доказать, что замкнуто в контексте 1 для любого 2.

Пусть 1 2 - сцепление из контекста 1 в контекст 2. Тогда замкнуто в 2 для любого 1. Обозначим () = ( )2, тогда = () 2. Рассмотрим ({(, ) | 2 } {(, ) | = }).

= () Выше мы показали, что это множество является содержанием обоих кон текстов 1 2 и (1 2 ), т.е., общим содержанием этих контекстов.

Тогда = для любого 1 и = для любого 2, следовательно =, и – общее содержание контекстов 1 2 и (1 2 ).

Следствие. Оператор замыкания для сцеплений контекстов 1 = (1, 1, 1 ) и 2 = (2, 2, 2 ) может быть вычислен за время ((|1 | · |2 | + |1 | · |2 |) · |2 ||1 |).

Доказательство. Нужно применить утверждение 11 и теорему 5.

4. Обучение гипотезам Теперь мы опишем модель обучения по гипотезам в духе [20, 23] в терминах АФП [52]. Эта модель соответствует общей парадигме обучения по положительным и отрицательным примерам (см., например [52, 73]):

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

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

Входные данные для контекста обучения могут быть представлены множествами положительных, отрицательных и неопределенных приме ров. Положительные примеры (или (+)-примеры) – это объекты, о кото рых известно, что они обладают признаком, а отрицательные примеры (или ()-примеры) – это объекты, о которых известно, что они не обладают признаком Определение 3. Рассмотрим положительный контекст K+ = (+,, + ) и отрицательный контекст K = (,, ). Контекст K± = (+, {}, + + {}) называется контекстом обучения. Оператор Галуа для этого контекста обозначается как ±.

Определение 4. Подмножество называется положительной гипо тезой (или (+)-гипотезой) контекста обучения K±, если - содержание контекста K+ и не является подмножеством ни одного содержания кон текста K.

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

В [23] гипотезы называются "гипотезами первого рода с запретом на контрпример”, причем дополнительно требуется, чтобы гипотеза подтвер ждалась не менее, чем двумя примерами, т.е. | + | 2.

Помимо положительных и отрицательных примеров обычно имеются объекты, для которых значение целевого признака неизвестно. В [23] эти объекты называются неопределенными примерами, они могут быть заданы контекстом K := (,, ), соответствующий оператор Галуа обознача ется через (·).

Гипотезы могут быть использованы для классификации неопределен ных примеров: если содержание := { | (, ) } объекта содержит положительную и ни одной отрицательной гипо тезы, то классифицируется положительно. Отрицательные классифи кации определяются аналогично. Если содержит гипотезы обоих знаков, то классификация противоречива. Если вообще не содержит гипотез, то классификация не определена. В этом случае можно применять методы другого типа, например, основанные на статистических подходах. В [23] классификации называются "гипотезами второго рода”.

В [52, 73, 53] отмечалось, что для классификации можно ограничить ся только минимальными (по вложению ) гипотезами, положительны ми и отрицательными, поскольку объектное содержание содержит поло жительную (отрицательную) гипотезу тогда и только тогда, когда оно со держит некоторую минимальную гипотезу.

Рассмотрим также другое, более слабое определение гипотезы (в [20, 23] называемое "простой (+)-гипотезой 1-го рода по методу сходства") Определение 5. Подмножество называется положительной предги потезой (или (+)-предгипотезой) контекста обучения K±, если является содержанием контекста K+ и не является содержанием контекста K.

Аналогично определяется отрицательная предгипотеза (или (-) предгипотеза).

4.1. Теоретико-решеточная интерпретация гипотез и классифи­ кации В терминах решетки B(K+ ) положительных понятий, каждый отри цательный пример вырезает из решетки (+)-контекста некоторый поряд ковый фильтр.

Для решетки B± ситуация выглядит иначе. Мы можем выделить три типа понятий этой решетки: понятия типа (, {}), где – содержание контекста K+, понятия типа (, ), где – содержание K и понятия типа (, ), где не является содержанием ни K+, ни K.

Утверждение 12. Положительные гипотезы соответствуют понятиям кон текста обучения K±, которые представимы как (, {}), причем не является содержанием K± Действительно, если является содержанием контекста K±, то есть примеры у которых все признаки из, но ни один не содержит признак, а это значит, что содержится в каком-то отрицательном примере.

Отрицательная гипотеза соответствует понятию K±, которое представимо как (, ), и ( {})± =. Это эквивалентно тому, что у K± не / существует понятия, у которого непустой объем и содержание не меньше, чем {}.

В решетке понятий B(K± ) понятия соответствуют (+)- и (-) гипотезам, лежащим ниже понятий, которые не являются гипотезами.

В терминах этой решетки задача классификации неопределенного при мера выглядит следующим образом. Рассмотрим порядковый фильтр решетки B(K± ), заданный максимальными подмножествами { } {}, которые являются содержаниями K±. Если существует понятие (, {}), лежащее в этом порядковом фильтре, такое, что и ( ±, ) не является понятием B(K± ), тогда – гипотеза для / положительной классификации. Отсутствие гипотезы для отрицатель ной классификации означает, что для любого понятия (, ) решетки B(K± ), такого, что и (, ) лежит в порядковом фильтре B(K± ), / заданного максимальными подмножествами { } {}, которые являют ся содержаниями K±, выполнено ( {}) = или существует понятие с непустым объемом, лежащее не выше, чем (( {}), ( {}) ).

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

Утверждение 13. Для контекста обучения K± существует положительная предгипотеза тогда и только тогда, когда решетка B(K+ ) не является под решеткой решетки B(K ).

Аналогично, существование отрицательной предгипотезы эквива лентно тому, что решетка B(K ) не является подрешеткой решетки B(K+ ).

Ниже приведен пример обучающей выборки и некоторое его есте ственное шкалирование:

GM цвет твердый гладкий форма фрукт яблоко желтое нет да круглое + грейпфрут желтый нет нет круглый + киви зеленое нет нет овальное + слива синяя нет да овальная + кубик зеленый да да кубический яйцо белое да да овальное теннисный мяч белый нет нет круглый GM фрукт яблоко + грейпфрут + киви + слива + кубик яйцо теннисный мяч Рис. 4.1. Шкалирование обучающей выборки (контекст K± ) Условные обозначения:

- зеленый, - желтый, - белый, - синий;

- твердый, - нетвердый;

- гладкий, - негладкий;

- круглый, - некруглый;

(+)-Гипотезы: {, }, {, }, {,,, }, {,,, }, {,, }, {,,, }, {,,, } (+)-Предгипотезы: { }, {, }, {, }, {, }, {,,, }, {,,, }, {,, }, {,,, }, {,,, } Рис. 4.2. Решетка понятий положительного контекста (K+ ) 4.2. Перечисление гипотез и дуализация монотонных булевых функций на решетках В [52] было показано, что все гипотезы могут быть перечислены с полиномиальной задержкой (||2 | |) с помощью алгоритма, являюще гося адаптацией Next Closure [54]. На самом деле можно использовать лю бой алгоритм перечисления замкнутых множеств в лектическом порядке (лексикографическом порядке на характеристических векторах). Действи тельно, рассмотрим контекст K = ( +,, + ) (это в точности контекст K± без целевого признака). Введем линейный порядок на объек тах этого контекста, такой, что любой объект из меньше, чем любой объект из +. Заметим, что множество будет гипотезой тогда и толь ко тогда, когда является объемом контекста K и =, а также наоборот – для любой гипотезы множество есть объем контекста K и =. Таким образом, множество гипотез взаимно-однозначно соответствует множеству объемов контекста K, которые не пересекаются c. Поэтому достаточно перечислять объемы контекста K в лектическом порядке до тех пор, пока мы не встретим объем, содержащий объект из.

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

Задача 10. Перечисление минимальных гипотез (MHE) ВХОД: Положительные и отрицательные контексты = K+ (+,, + ), K = (,, ) ВЫХОД: Все минимальные гипотезы контекста K±.

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

Задача 11. Дополнительная минимальная гипотеза (AMH) ВХОД: Положительные и отрицательные контекста = K+ (+,, + ), K = (,, ) и подмножество минимальных гипо тез = {1,..., }.

ВОПРОС: Существует ли дополнительная минимальная гипотеза обучающего контекста K± т.е. такая минимальная гипотеза, что ?

/ Мы сведем -полную задачу выполнимость КНФ (SAT) к AMH.

Приведенное ниже сведение похоже на то сведение, которое мы использо вали для доказательства трудности задачи распознавания псевдосодержа ния.

Рассмотрим произвольный вход задачи SAT – 1,..., с перемен ными 1,...,, где = (1... ), 1 и {1,..., } {¬1,..., ¬ } (1, 1 ) – некоторые переменные или их отрицания, называющиеся литералами. По этой КНФ мы построим положительный контекст K+ = (+,, + ) и отрицательный контекст K = (,, ). Определим = {1,..., } {1, ¬1,...,, ¬ } + = {1, ¬1,...,, ¬ } {1,..., } = {1,..., } Отношение положительного контекста определяется следующим об разом + = = =, где = {(, ) |, 1, 1 } / {(¬, ) | ¬, 1, 1 } / = = {1, ¬1,...,, ¬ } {1, ¬1,...,, ¬ } {(1, 1 ), (¬1, ¬1 ),..., (, ), (¬, ¬ )} = = {(1, 1 ),..., (, )} т.е. для -й клаузы(дизъюнкции) + {1, ¬1,...,, ¬ } является мно жеством литералов не встречающихся в, = – отношение контраноми нальной шкалы.

Отношение отрицательного контекста задается, как =, где = {1, ¬1,...,, ¬ } {(1, 1 ), (1, ¬1 ),..., (, ), (, ¬ )}.

В качестве подмножества минимальных гипотез мы берем = {{1 }, {2 },..., { }}. Очевидно, K± вместе с является корректным входом задачи AMH.

1 2 · · · 1 ¬1 · · · ¬ K+ ¬.

. =.

¬.

. =.

.

..

K Мы будем называть гипотезу (не обязательно минимальную) допол­ нительной, если она не входит в.

Утверждение 14. Если – дополнительная минимальная гипотеза обу чающего контекста K±, то {1, ¬1,...,, ¬ }.

{1, ¬1,...,, ¬ }, тогда т.к.

Доказательство. Допустим не пусто, то найдется некоторая дизъюнкция, 1. Но является минимальной гипотезой и поэтому оно не содержит(строго) никакую другую гипотезу. Следовательно =, что противоречит тому, что дополнительная минимальная гипотеза.

Для любого {1, ¬1,...,, ¬ } такого, что для всех 1 выполнено {, ¬ } мы определим булево назначение переменных естественным образом:

if ;

, ( ) =, if ;

/ В случае {, ¬ } для некоторого 1, назначение не определено.

Симметрично, для назначения определим множество = { | ( ) = } {¬ | ( ) = }.

Ниже для удобства в случае, если {1, ¬1,...,, ¬ } мы обо значим дополнение в {1, ¬1,...,, ¬ } как.

Утверждение 15. Если подмножество {1, ¬1,...,, ¬ } не со держится в содержании ни в одного отрицательного понятия (т.е.

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

Доказательство. Доказательство очевидно.

Следующая теорема доказывает NP-трудность задачи AMH.

Теорема 7. У AMH есть решение тогда и только тогда, когда у SAT есть решение.

Доказательство.() Пусть – дополнительная минимальная гипотеза обучающего контекста K±. Для начала заметим, что по Утверждению и Утверждению 15 назначение корректно определено. Поскольку – непустое содержание контекста K+, из Утверждения 14 и того, что = – отношение контраноминальной шкалы следует, что + = { | } {¬ | ¬ }. Теперь ++ {1, 2,..., } =, отсюда для любого (1 ) найдется некоторый + такой, что +. По / определению последнее означает, что литерал принадлежит. Таким образом ( ) =.

() Пусть – булево назначение переменных и () =. Тогда =. Заметим, что + = { | } {¬ | ¬ }, потому + что = это отношение контраноминальной шкалы и =, 1.

Предположим, что ++ для некоторого 1. Это эквивалент но тому, что + +. Следовательно, по определению отношения, не существует литерала такого, что. Поэтому, дизъюнкция не выполнена, а это противоречит тому, что выполняет КНФ. Таким образом ++ = и – гипотеза. Поскольку не содержит ни одно го { }, оно должно содержать дополнительную минимальную гипотезу (нестрого).

Утверждение 16. MHE не может быть решена за полиномиальное от вы хода время, если =.

Доказательство. Пусть нашелся полиномиальный от выхода алго ритм, который генерирует все минимальные гипотезы за время (|+ |, | |, |+ |, | |, | |, ), где – количество минимальных гипотез.

По этому алгоритму построим алгоритм, который выполняется первые (|+ |, | |, |+ |, | |, | |, + 1) шагов алгоритма. Очевидно, если су ществует более, чем минимальных гипотез, то сделает как минимум Рис. 4.3. - максимальные нули, - минимальные единицы (|+ |, | |, |+ |, | |, | |, + 1) шагов (и наоборот) – следовательно мы можем решить AMH за полимномиальное время.

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

Пусть B - полная конечная решетка и - монотонная булева функ ция на ней. Любая полная конечная решетка изоморфна решетке понятий [54], поэтому без ограничения общности можно считать, что B это решет ка понятий B(,, ) для некоторого контекста K(,, ). Тогда для, имеет место ((, )) ((, )). Известно, что любая монотонная булева функция на решетке однозначно определяется своими минимальными единицами, т.е. множеством {(, ) | (, ) B, ((, )) = 1, ((, )) = 0 }. Мы можем представить мно жество минимальных единиц монотонной булевой функции как множество минимальных гипотез контекста обучения, заданного контекстами K+ и K, где K+ = K и объектные содержания контекста K являются в точ ности всеми минимальными нулями. Аналогично, контекст обучения K± определяет монотонную булеву функцию на решетке понятий контек ста K+ такую, что нули – это максимальные (по включению) объектные содержания K (см. рис. 2). Таким образом, мы получили следующую за дачу:

Задача 12. Дуализация монотонной булевой функции на решетке (MBDL1) ВХОД: Формальный контекст K и множество нулевых значений булевой функции на решетке понятий контекста K.

ВЫХОД: Множество минимальных единиц.

Симметричная этой задаче будет Задача 13. Дуализация монотонной булевой функции на решетке (MBDL2) ВХОД: Формальный контекст K и множество единичных значений булевой функции на решетке понятий контекста K.

ВЫХОД: Множество максимальных нулей.

Поскольку перечисление минимальных гипотез эквивалентно MBDL1, MBDL1 не может быть решена за время полиномиальное от выхода, если =. Заметим, что в случае булевой решетки эта задача полиномиально эквивалентна Монотонной булевой дуализации (Monotone Boolean Dualism) (см. [49]) и минимальные гипотезы в этом случае могут быть построены за квазиполиномиальное от выхода время ((log ) ), где – сумма размера входа и длины записи множества минимальных гипотез.

Мы уже писали, что гипотезы контекста обучения K± находятся во взаимно-однозначном соответствии с объемами контекста K = ( +,, + ), которые не содержат ни одного объекта из. Более то го, минимальные гипотезы соответствуют максимальным объемам и наобо рот. Рассмотрим контексты K + = (, +, + ) и K = (, +, = ), где + = {(, ) | (, ) + }, = {(, ) | (, ) }, = (, ). Множество содержаний контекста K + совпадает с мно жеством объемов контекста K. Заметим, что контекст K + задает решетку B(K + ), объектные содержания контекста K задают единицы некоторой булевой функции на решетке B(K + ), а максимальные нули этой функ ции являются максимальными содережаниями контекста K +, которые не содержат объектных содержаний контекста K. Таким образом, задача MBDL2 эквивалентна задаче MHE.

Как мы показали выше, в случае, когда решетка B задана формаль ным контекстом задача MBDL трудна, поэтому разумно рассмотреть дру гие способы задания решеток. Второй наиболее известный способ задания решетки понятий – задание системы замыканий посредством набора им пликаций (базисом импликаций). В работе [62] показано, что невозможно найти все максимальные (по включению) супремум-неразложимые элемен ты за полиномиальное от выхода время, если =, когда система замы каний задана базисом импликаций. Если рассмотреть задачу дуализации с только одним отрицательным примером –, то мы получим Утверждение 17. В случае, когда решетка B задана базисом импликаций, MBDL2 не может быть решена за полиномиальное от выхода время, если =.

Отметим, что, если немного изменить сведение из [62], то мы получим:

Утверждение 18. В случае, когда решетка B задана базисом импликаций, MBDL1 не может быть решена за полиномиальное от выхода время, если =.

4.3. Распределенное обучение гипотезам Часто бывает ситуация, когда ДСМ-гипотез слишком много (даже минимальных), что затрудняет обучение гипотезам и последующую клас сификацию. Пусть есть несколько обучающих контекстов с одинаковым множеством признаков: K1,..., K. В качестве гипотез будем использо ± ± вать только те гипотезы, которые являются гипотезами в каждом из кон текстов. Формально:

SharedHypotheses(K± 1, K± 2,..., K± ) 1 C AllIntents(GetClosure(·), K+ 1, K+ 2,..., K+ ) K 1 K 2... K } 2 H { | C, 3 Minimize(H ) 4 return H Где – оператор замыкания общих содержаний, а – любой алгоритм АФП поиска всех замкнутых множеств, ис пользующий оператор замыканий (например Next Closure) Условиями применения данной модели обучения могут служить сле дующие ситуации:

1. Несколько исследовательских групп проводят один и тот же экспе римент.

2. Несколько наборов данных с одинаковым набором признаков описы вают одну и ту же задачу, но объекты отличаются по своей природе.

3. Общих содержаний намного меньше, чем содержаний в каждом из положительных контекстов.

Ниже приводятся результаты экспериментов по классификации ток сичности химических соединений ДСМ-методом с использованием общих гипотез. Входные данные для тестирования были взяты из материалов Predictive Toxicology Challenge и получены следующим образом:

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

2. Химические соединения представлены соответствующими молеку лярными графами (графами с метками вершин и ребер).

3. Строятся все частые замкнутые подграфы молекулярных графов (с поддержкой не ниже заданной).

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

Всего было 4 базы данных по токсичности химических соединений ({мыши, крысы} {самки, самцы}).

support Err. Err. Mis. Mis. #Hyp. #Hyp.

30 4,6 10,0 65,9 54,6 13 24, 20 12,7 12,1 35,6 45,8 52 134, 10 14,6 10,5 18,3 45,4 104 270, 5 16,0 10,4 15,1 45,8 151 389, Err. – процент ошибочной классификации при использовании общих гипотез Err. – процент ошибочной классификации при использовании классических гипотез Mis. – процент неклассифицируемых объектов при использовании общих гипотез Mis. - процент неклассифицируемых объектов при использовании классических гипотез #Hyp. – количество минимальных общих гипотез #Hyp. – среднее количество минимальных классических гипотез по 4 базам данных.

Таблица 4.1. Результаты классификации токсичности молекул.

4.4. Устойчивость понятий и гипотез Подходы анализа данных использующие решетки понятий для кла стеризации и инженерии онтологий часто встречают проблему слишком большого количества понятий формального контекста. Было предложено несколько индексов для измерения устойчивости понятий, таких как поня тийная устойчивость [68, 75, 77], вероятность и разделение [66]. Индексы устойчивости использовалась во многих приложениях для выбора понятий как бикластеров похожих объектов, например, в планировании медицин ского лечения [58] или в группировании французских глаголов [45]. В [66] авторы сравнили фильтрацию, основанную на различных индексах и их ли нейных комбинациях для восстановления данных. Линейные комбинации индексов, которые показали наилучшие результаты в компьютерных экс периментах фильтрации понятий, использовали устойчивость с большими коэффициентами. Тем не менее, потенциальное ограничение, применения устойчивости для больших данных это сложность ее вычисления (в [68, 75] было показано, что эта задача #P-полна). С.А. Объедков предложил [85] алгоритм для вычисления индекса устойчивости всех формальных поня тий, используя решетку понятий. Этот алгоритм был достаточно хорош в практических применениях, но в худшем случае его сложность квадратич на относительно размера решетки(которая сама может быть экспоненци альной относительно размера контекста). В этом разделе мы рассмотрим задачу приближенного подсчета устойчивости.

Понятие устойчивости формального понятия впервые было было представлено в [68, 75] и используется в настоящее время, в слегка из мененной форме из [77, 85].

Определение 6. Пусть K = (,, ) – формальный контекст и (, ) – формальное понятие контекста K. Индекс (интенсиональной) устойчиво­ сти (, ), или (), определяется следующим образом:

| | = | (, ) = 2|| Индекс экстенсиональной устойчивость определяется двойствен || =| ным образом: (, ) = () =. Обычно, когда это не при 2|| водит к неправильному пониманию, индексы и опускаются.

Числитель индекса интенсиональной устойчивости (, ) = | | = | равняется количеству генераторов формального понятия (, ), таким образом 2|| = (, ) (,)(,) и 2|| ((, ), (, )), (, ) = (,)(,) где (, ) – это функция Мёбиуса решетки понятий. Неявно это отраже но в алгоритме [85] для вычисления индекса устойчивости, основанного на принципе включения-исключения, как и стандартные алгоритмы вычисле ния функции Мёбиуса на решетке.

4.5. Приближенный подсчет числа замкнутых и незамкнутых множеств Многие задачи подсчета FCA являются #P-полными, но это не озна чает, что они не могут быть решены приближенно.

Ниже, для задачи мы будем обозначать количество решений задачи на соответствующем входе (который будет ясен из контек ста) как |# |.

Для данного гиперграфа = (, ), = {1,..., }, подмноже ство называется независимое множество, если для любого 1 и называетсяконезависимое множество, если для лю бого 1.

Задача 14. Количество независимых множеств (#IS) ВХОД: Гиперграф.

ВЫХОД: Количество независимых множеств гиперграфа Известно, что для задачи #IS в случае когда гиперграф является обычным графом не существует FPRAS, если = (см. [40]). Более того, несложно увидеть, что эта задача трудна даже, когда и {} не могут быть ребрами гиперграфа.

Также нам понадобится формулировка следующей задачи:

Задача 15. Количество конезависимых множеств (#CIS) ВХОД: Гиперграф = (, ), = {1,..., },.

ВЫХОД: Количество конезависимых множеств.

Заметим, что множество является независимым множеством гиперграфа = (, ), = {1,..., } тогда и только тогда, когда является конезависимым множеством гиперграфа = (, ), = { 1,..., }. Следовательно, для задачи #CIS не существует FPRAS, если =.

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

Задача 16. Количество незамкнутых множеств (#NC) ВХОД: A Формальный контекст K = (,, ) ВЫХОД: Количество множеств таких, что = Утверждение 19. Для задачи #NC не существует FPRAS, если = Доказательство. Рассмотрим произвольный вход (, ), = {1,..., } = {1,..., } задачи #CIS. По этому входу мы по строим формальный контекст K = (,, ) с объектными содержания ми 1 { {1 }} { {2 }}... { { }}. Очевидно что, множество является конезависимым множеством гиперграфа (, ), если и только если = или = для контекста K. Следовательно |#| = |# | + 1.

Задача 17. Количество замкнутых множеств базиса импликаций (#J ) ВХОД: Базис импликаций J = {1 1,..., },, ВЫХОД: Колчиство замкнутых множеств базиса J.

Утверждение 20. Для задачи #J не существует FPRAS, если = Доказательство. Рассмотрим произвольный вход (, ), = {1,..., } задачи #IS. По этому входу построим базис импликаций J = {1,..., } (импликации определены на множестве ).

Очевидно, множество является независимым множеством гиперграфа (, ), если и только, если – замкнуто в базисе J и =. Следователь но |#| = |#J | Поскольку замкнутое множество по отношению к базису может быть представлено как выполняющий набор соответствующей Хорновской КНФ, мы получаем Следствие 1. Для задачи подсчета числа решений Хорновской КНФ(# ) не существует FPRAS, если = Задача 18. Количество незамкнутых множеств базиса импликаций (# J ) ВХОД: Базис импликаций J = {1 1,..., },, ВЫХОД: Количество незамкнутых множеств базиса J.

Утверждение 21. Для задачи # J существует FPRAS Доказательство. Рассмотрим вход J = {1 1,..., },, задачи # J. Замкнутые множества базиса имплика ций J находятся во взаимно однозначном соответствии с выполняющими наборами соответствующей Хорновской КНФ J. Следовательно незамкну тые множества J находятся во взаимно однозначном соответствии с выпол няющими наборами ДНФ ¬J. Для задачи подсчета числа решений ДНФ известен FPRAS [83].

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

#closed sets #nonclosed sets FPRAS, если = (K) #1 -complete FPRAS, если = (J) FPRAS Таблица 4.2. Сложность подсчета замкнутых и незамкнутых множеств.

(K) означает случай, когда система замыканий задана контекстом K.

(J) означает случай, когда система замыканий задана базисом имплика ций J.

4.6. Индекс вероятностной устойчивости Известно, что задача подсчета индекса устойчивости формального понятия #P-полна. Более того, из результатов предыдущего раздела сле дует, что для этой задачи не существует FPRAS, если =. По следнее означает, что индекс устойчивости нельзя приблизить за полино миальное в среднем время с полиномиально ограниченной относительной погрешностью (если = ). Чтобы это доказать, достаточно рассмот реть формальный контекст из доказательства Утверждения 19. Очевид но ( ) = (|# | + 1)/2| |. Поскольку приближенный подсчет индекса устойчивости с ограниченной относительной погрешностью за полиноми альное время невозможен, если = и все известные алгоритмы точ ного подсчета индекса устойчивости, сразу для всех понятий, квадратичны от размера решетки, то далее мы сфокусируемся на том как аппроксими ровать индекс устойчивости с ограниченной абсолютной погрешностью.

По определению, индекс устойчивости содержания формального контекста K = (,, ) равен вероятности того, что замыкание случай ного подмножества равно, т.е. () = ( = ), когда выбрано случайно и равномерно из 2. Таким образом чтобы оценить () мы мо жем использовать метод Монте-Карло.

Определим модель вероятностной устойчивости формального поня тия, следующим образом:

=1 () Определение 7 (Индекс вероятностной устойчивости). () =, где () – независимые и одинаково распределенные случайные величины, определяемые как: 1, если = ;

() = 0, если = ;

Когда выбрано случайно и равномерно Для вычисления вероятностного индекса устойчивости () исполь зуем метод Монте-Карло:

GetStability(, ) 1 answer 2 for 1 to do Выбрать случайное подмножество if = then answer answer + answer 6 answer 7 return answer Напомним теорему Чернова (Chernoff-Hoeffding) с упрощенными оценками[83], которая формулируется следующим образом Теорема 8 (Chernoff-Hoeffding). Пусть 1, 2,..., – независимые и оди наково распределенные случайные величины с = ( ). Тогда ) exp (22 ) ( Не сложно получить следующее утверждение, которое говорит, что для достаточно больших = (, ), вероятность | answer ()| не больше чем.

Утверждение 22. Метод Монте-Карло аппроксимирует () с вероятно стью не меньше 1 и абсолютной погрешностью при условии, что 1 ln Доказательство. Если мы возмем случайные величины равные, и подставим их в неравенство из теоремы Chernoff-Hoeffding, то = (1 ) и мы получим + ) exp (22 ).

( Следовательно | ) (| 1 ( ) + ( + ) 2 exp (22 ).

Рассмотрим случайные величины такие, что = 1, если и толь ко если = на -ой итерации GetStability и = 0 иначе. Та ким образом = answer, где answer было возвращено функцией GetStability(A,N) на -ой итерации. Вероятность абсолютной ошибки удовлетворяет (| answer | ) 2 exp (22 ). Следовательно 22 ln 2.

Мы можем использовать этот алгоритм, чтобы получить почти все устойчивые понятия. Ниже псевдокод алгоритма для вычисления топа устойчивых понятий TopStableConcepts(K, 0 ) 1 answer 2 for каждого понятия = (, ) контекста K 3 do if approxStability() then answer answer {(, )} 5 return answer 4.7. Анализ результатов вычислений индекса вероятностной устойчивости В этом разделе мы обсудим эксперементальные результаты вычисле ния устойчивости понятий случайных формальных контекстов разных раз меров и плотности. Результаты приближенного вычисления устойчивости приведены на графиках 1 и 2. Ось (помеченная как Error ) соответствует относительной ошибке |(K,, )(K,, )|/|(K,, )|.


Здесь (K,, ) обозначает множество всех понятий с устойчивостью ;

(K,, ) обозначает множество всех понятий с приближенной устойчивостью, где – параметр (порог устойчивости). Для каж дой пары, случайного контекста K = (,, ) с вероятно стью (называемой плотностью контекста выполнено (, ).

Рис. 4.4. Качество аппроксимации на случайном контексте 100 30 с плотностью 0. Рис. 4.5. Качество аппроксимации на случайном контексте 150 30 с плотностью 0. Результаты экспериментов показывают, что индекс вероятностной устойчивости имеет лучшую точность, когда граница устойчивости ниже.

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

4.8. Устойчивые гипотезы: Результаты экспериментов с данны­ ми по токсичности химических соединений Приведем результаты экспериментов классификации токсичности хи мических соединений на данных, которые мы использовали для тестиро вания распределенного обучения гипотезам в разделе 4.3. В данном тести ровании для классификации мы выбирали только устойчивые гипотезы.

Гипотеза считалась устойчивой, если ее индекс вероятностной устойчиво сти 50 в соответствующем контексте (положительном, для положительной гипотезы и отрицательном, для отрицательной гипотезы) больше заданно го порога 0.65.

support Err. Err. Mis. Mis. #Hyp. #Hyp.

30 31,0 10,0 49.7 54,6 9,8 24, 20 10,9 12,1 44.6 45,8 79,7 134, 10 12,5 10,5 34.5 45,4 265,75 270, 5 12,8 10,4 31.9 45,8 393,5 389, Err. – процент ошибочной классификации при использовании устойчивых гипотез с 0, Err. – процент ошибочной классификации при использовании классических гипотез Mis. – процент неклассифицируемых объектов при использовании устойчивых гипотез с 0, Mis. - процент неклассифицируемых объектов при использовании классических гипотез #Hyp. – среднее количество минимальных устойчивых гипотез по 4 базам данных #Hyp. – среднее количество минимальных классических гипотез по 4 базам данных Таблица 4.3. Результаты классификации токсичности молекул.

Как видно из результатов компьютерных экспериментов, использо вание устойчивых гипотез повышает качество покрытия (процент приме ров, которые удалось классифицировать), но немного увеличивает процент ошибочной классификации (уменьшается качество классификации). Если сравнить результаты из таблицы 4.3 с результатами из таблицы 4.1, то можно заметить, что покрытие у распределенного обучения гипотезам зна чительно выше покрытия устойчивых гипотез, но немного проигрывает в качестве классификации.

5. Комплекс программ 5.1. Программный комплекс Cordiet Программный комплекс Cordiet-FCA [88] разрабатывается отделени ем прикладной математики и информатики НИУ ВШЭ (ОПМИ).

На текущий момент система Cordiet-FCA представляется локальным приложением под операционную систему Windows. Эта версия системы ис пользует локальное XML-хранилище и встроенное окружение для прове дения исследований с профайлером, исполнителем запросов, редактором онтологий и множеством решателей и визуализаторов. Основные решате ли могут строить решетки и подрешетки, искать ассоциативные правила и импликации, вычислять индексы устойчивости формальных понятий, ме ры сходства для контекстов и понятий, и.т.д.

Cordiet-FCA использовался для решения некоторых прикладных за дач, связанных с медицинской информатикой и криминальными расследо ваниями.

5.2. Программная реализация построения базисов импликаций Алгоритмы построения и тестирования базисов импликаций были ре ализованы на языке C++ (около 1000 строк кода) в среде MS Visual Studio 2010 с использованием стандартной библиотеки STL.

Эти реализации вошли в комплекс программ, встроенный в программ ную систему Cordiet-FCA и могут быть использованы для построения при ближенного базиса импликаций.

Структура программы построения и тестирования базисов имплика ций имеет следующий вид:

1. В файлах mset.h и mset.cpp (приложение 1.1) реализованы структуры и функции для работы с множествами, представленными списками элементов.

2. В файлах implications.h и implications.cpp (приложение 1.2) реализо ваны структуры и функции для работы с импликациями. Функция lin_closure(const std::vectorImplication& 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 (приложение 1.5) реали зован алгоритм поиска приближенного базиса импликаций.

Функция std::vectorImplication get_approximate_base(const sparse_context::Context& K, int no_steps) возвращает приближен ный базис импликация контекста K, после no_steps шагов.

6. В файлах 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) функция mset closure(const std::vectorsparse_context::Context& K, const mset& X) вычисляет оператор замыкания общих содержаний для случая ко гда контексты заданы списками признаков.

2. В файлах shared_closure.h и shared_closure.cpp (приложение 2.1) реа лизована структура данных PQ (специальная приоритетная очередь, с поддержкой дополнительный операций), используемая алгоритмом _2.

5.4. Программная реализация распределенного обучения гипо­ тезам Алгоритм распределенного обучения гипотезам был реализован на языке C++ (около 300 строк) в среде MS Visual Studio 2010 с использова нием стандартной библиотеки STL.

Реализация вошла в комплекс программ встроенный в программную систему Cordiet-FCA.

Структура программы распределенного обучения гипотезам имеет следующий вид:

1. В файле JSM_test.cpp (приложение 3.1) функция vectormset find_shared_hypotheses(const vectorContext& pK, const vectorContext& nK) находит все общие гипотезы наборов по ложительных и отрицательных контекстов pK и nK, соответственно.

2. В файле JSM_test.cpp (приложение 3.1) функция mset next_closure_JSM(const mset& X, const Context& K) возвраща ет следующую гипотезу в лексикографическом порядке на объемах соответствующих формальных понятий.

3. В файле JSM_test.cpp (приложение 3.1) функция int classify(const vectormset& pH, const vectormset& nH, const mset& X) возвра щает результат классификации X при использовании множества по ложительных гипотез pH и множества отрицательных гипотез nH.

Данная функция возвращает 1, если результат классификации поло жителен, 1, если результат классификации отрицателен, и 0, если классификация неопределена.

Заключение В диссертационной работе приведен обзор методов поиска строгих зависимостей в данных. В 2006 году участниками конференции ICFCA в Ленсе (Lens, Франция) был составлен список наиболее важных открытых задач в АФП. Одной из них была задача о сложности распознавания псев досодержаний, которая была решена в данной диссертационной работе и опубликована в [31] (публикации, где рассматривалась данная задача и считалась открытой: [74, 89, 90, 91, 92, 38]). Эта задача была также пред ставлена как открытая на Дрезденской конференции по дискретной мате матике в 2002 году.

В отличие от классического минимального базиса импликаций, для которого все известные алгоритмы построения имеют экспоненциальную оценку сложности, среднее время работы построения приближенного ба зиса импликаций полиномиально и оценивается как (| || | · (||| | + | || |) · 1 ), где – минимальный базис импликаций, а – параметр точности приближенного базиса импликаций. Проведенные на реальных данных эксперименты показали, что размер приближенного базиса был значительно меньше (иногда в сотни раз).

В работе было доказано, что если =, то невозможно найти все минимальные ДСМ-гипотезы за полиномиальное от размера выхода время. Модель распределенного обучения гипотезам показала значитель ное сокращение количества гипотез по отношению к числу ДСМ-гипотез в стандартной постановке. Линейный по времени алгоритм вычисления опе ратора замыканий системы замыканий общих содержаний позволил быстро перечислять все общие гипотезы.

В данной работе была доказана трудность аппроксимации индекса классической устойчивости формальных понятий (с полиномиально огра ниченной относительной ошибкой). Была предложена модель вероятност ного индекса устойчивости формальных понятий, которая соответствует аппроксимации классического индекса устойчивости с ограниченной абсо лютной ошибкой и может быть вычислена за полиномиальное время. Про веденные эксперименты показали, что применение вероятностного индекса устойчивости, при использовании ДСМ-метода, уменьшает число некласси фицируемых объектов на 43% при увеличении количества ошибок клас сификации на 23% (число неклассифицируемых объектов, при исполь зовании стандартных ДСМ-гипотез 46%).


Основные результаты и выводы работы:

1. Результаты, связанные с базисами импликаций:

1.1 Доказана трудноразрешимость (в терминах NP- и coNP-полноты и трудности) задач, связанных с вычислением классического мини мального базиса импликаций.

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

2. Результаты, связанные с минимальными гипотезами:

2.1 Доказана трудноразрешимость вычисления минимальных гипотез в стандартной постановке.

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

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

3. Результаты, связанные с индексом устойчивости формальных понятий и гипотез:

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

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

Литература 1. Бабин М.А. О приближенном базисе импликаций // Научно техническая информация. Серия: Информационные процессы и си стемы, №8, С. 20–23, 2012.

2. Бабин М.А., Кузнецов С.О. О теоретико-решеточной интерпретации задач поиска гипотез и зависимостей // Научно-техническая инфор мация. Серия: Информационные процессы и системы, №10, С. 18–22, 2011.

3. Бабин М.А., Кузнецов С.О. Связи между решетками понятий и слож ность их вычисления // Труды МФТИ, том 4 №2(14), С. 73–80, 2012.

4. Биркгоф Г. Теория решеток // М.: Наука, 1984.

5. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов // М., Наука, С.418, 1974.

6. Виноградов Д.В. Формализация правдоподобных рассуждений в ло гике предикатов // НТИ, Сер.2. №11, С.17–20, 2000.

7. Гретцер Г. Общая теория решеток // - М.: Мир, 1982.

8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // - М.: Мир, 1982.

9. Кузнецов С.О. Интерпретация на графах и сложностные характе ристики задач поиска закономерностей определенного вида // НТИ, Сер.2, №1., С.23–28, 1989.

10. Кузнецов С.О. Устойчивость как оценка обоснованности гипотез, по лучаемых на основе операционального сходства // НТИ, Сер.2, №12, С.21–29, 1990.

11. Кузнецов С.О. Введение в ДСМ-метод // Семиотика и информатика, Вып. 31, С.5–40, 1991.

12. Кузнецов С.О. ДСМ-метод как система автоматического обучения // Итоги науки и техники, Сер. Информатика, №15, С.17–54, 1991.

13. Кузнецов С.О. Сложность алгоритмов обучения и классификации, ос нованных на поиске пересечения множеств // НТИ, Сер.2, №9, С.8–15, 1991.

14. Кузнецов С.О. Быстрый алгоритм построения всех пересечений объ ектов из конечной полурешетки // НТИ, Сер.2, №1, С.17–20, 1993.

15. Кузнецов С.О. Алгоритмическая сложность порождения гипотез и классификаций, основанных на поиске пересечения множеств // До клады АН.-335, №3, С.300–303, 1994.

16. Кузнецов С.О., Финн В.К. О модели обучения и классификации, ос нованной на операции сходства // Обозрение Прикладной и Промыш ленной Математики, 3, №1, С.66–90, 1996.

17. Кузнецов С.О., Объедков С.А. Алгоритмы построения множества всех понятий формального контекста и его диаграммы Хассе // Известия Академии Наук, Теория и системы управления, №1, С.120–129, 2001.

18. Кузнецов С.О. Автоматическое обучение на основе анализа формаль ных понятий // Автоматика и телемеханика, №10, С.3–27, 2001.

19. Мейер Д. Теория реляционных баз данных // Москва, Мир, 1987.

20. Финн В.К. О машинно-ориентированной формализации правдоподоб ных рассуждений в стиле Ф.Бэкона - Д.С.Милля. // Семиотика и ин форматика, Вып. 20, С.35–101, 1983.

21. Финн В.К. Правдоподобные выводы и правдоподобные рассуждения // Итоги науки и техн., Сер. Теория вероятностей Мат. стат. Теор.

кибернет. - М.:ВИНИТИ, Вып. 28, С.3–84, 1988.

22. Финн В.К. Об обобщенном ДСМ-методе автоматического порождения гипотез // Семиотика и информатика, Вып.29, С.93–123, 1989.

23. Финн В.К. Правдоподобные рассуждения в интеллектуальных систе мах типа ДСМ // Итоги науки и техники, Сер. Информатика, М.:

ВИНИТИ, №15, С.54–101, 1991.

24. Финн В.К., Михеенкова М.А. О ситуационном расширении ДСМ метода автоматического порождения гипотез // НТИ, Сер.2, №11, С.20–30, 2000.

25. Anshakov O.M., Finn V.K., Skvortsov D.P. On axiomatization of many valued logics associated with the formalization of plausible reasonings // Stud. Log., vol. 25, No. 4, p.23–47, 1989.

26. Agrawal R., Imielinski T., Swami A. N. Mining Association Rules between Sets of Items in Large Databases // SIGMOD Conference, p.207–216, 1993.

27. Agrawal R., Srikant R. Fast Algorithms for Mining Association Rules in Large Databases // Journal of Computer Science and Technology, vol. 15, Issue 6, p.487–499, 1994.

28. Angluin D., Frazier M., Pitt L. Learning Conjunctions of Horn Clauses // Machine Learning, vol. 9, p.147–164, 1992.

29. Armstrong W.W. Dependency structure of data base relationships // Proc. IFIP Congress, Geneva, p.580–583, 1974.

30. Babin M.A., Kuznetsov S.O. On Links between Concept Lattices and Related Complexity Problems // Proc. 8th Int. Conf. on Formal Concept Analysis (ICFCA’10), Lecture Notes in Artificial Intelligence, Springer, vol. 5986, p.138–144, 2010.

31. Babin M.A., Kuznetsov S.O. Recognizing Pseudo-intents is coNP complete // Proc. CLA 2010, p.294–301, 2010.

32. Babin M.A., Kuznetsov S.O. Enumerating Minimal Hypotheses and Dualizing Monotone Boolean Functions on Lattices // Proc. 9th Int.

Conf. on Formal Concept Analysis (ICFCA’11), Lecture Notes in Artificial Intelligence, Springer, vol. 6628, p.42–48, 2011.

33. Babin M.A., Kuznetsov S.O. Approximating Concept Stability // Proc.

10th Int. Conf. on Formal Concept Analysis (ICFCA’12), Lecture Notes in Artificial Intelligence, Springer, vol. 7278, p.7–15, 2012.

34. Babin M.A., Kuznetsov S.O. Computing Premises of a Minimal Cover of Functional Dependencies is Intractable // Discrete Applied Mathematics, принята к публикации, 2012.

35. Bastide Y., Lakhal L., Pasquier N., Taouil R. Efficient Mining of Association Rules Based on Using Closed Itemset Lattices // J. Inf.

Systems, vol. 24, p.25–46, 1999.

36. Bishop C.M. Pattern Recognition and Machine Learning // Information Science and Statistics, Springer, 2006.

37. Borchmann D., Distel F., Ryssel U. Fast Computation of Proper Premises // Proc. International Conference on Concept Lattices and Their Applications(CLA’2011), Nancy (France), 2011.

38. Distel F. Hardness of enumerating pseudo-intents in the lectic order // Proc. ICFCA 2010, Lecture Notes in Artificial Intelligence, vol. 5986, p.124–137, Springer, 2010.

39. Distel F., Sertkaya B. On the complexity of enumerating pseudo-intents // Discrete Applied Mathematics, vol. 159, no.6, p.450–466, 2011.

40. Dyer M., Goldberg L.A., Greenhill C., Jerrum C. On the relative complexity of approximate counting problems, Proc. APPROX 2000, p.108-119, 2000.

41. Duquenne V., Guigues J. L. Familles minimales d’implications informatives resultant d’un tableau de donnes e binaries // Mathmatiques, Informatique et Sciences Humaines, 95, p.5–18, 1986.

e 42. Duquenne V., Obiedkov S.A. Attribute-incremental construction of the canonical implication basis // Annals of Mathematics and Artificial In telligence, 49(1-4):7799, 2007.

43. Egho E., Jay N., Raissi C., Napoli A. A FCA-based Analysis of Sequential Care Trajectories // Proc. 8th of the International Conference on Concept Lattices and Their Applications (CLA’2011), Nancy (France), p.362-376, 2011.

44. Eiter T., Ibaraki T., Makino K. Computing Intersections of Horn Theories for Reasoning with Models // Proc. National Conference on Artificial Intelligence (AAAI’98), Madison, Wisconsin, July 26-30, p.292–297, 1998.

45. Falk I., Gardent C. Combining Formal Concept Analysis and Translation to Assign Frames and Thematic Role Sets to French Verbs // Proc.

International Conference Concept Lattices and Their Applications (CLA’2011), Nancy (France), 2011.

46. Falk I., Gardent C. Bootstrapping a Classification of French Verbs Using Formal Concept Analysis // Proc. Interdisciplinary Workshop on Verbs, Pisa (Italy), 2011.

47. Falk I., Gardent C., Lorenzo A. Using Formal Concept Analysis to Acquire Knowledge about Verbs // Proc. 7th of the International Conference on Concept Lattices and Their Applications (CLA’2010), p.151–162, 2010.

48. Feldman R., Sanger J. The text mining handbook: advanced approaches in analyzing unstructured data // Cambridge University Press, 2007.

49. Fredman M.L., Khachiyan L. On the complexity of dualization of monotone disjunctive normal forms // Journal of Algorithms, vol. 21, p.618–628, 1996.

50. Ganter B. Two Basic Algorithms in Concept Analysis // FB4-Preprint No. 831, TH Darmstadt, 1984.

51. Ganter B. Lattices of Rough Set Abstractions as -Products // Proc.

ICFCA 2008, Lecture Notes in Computer Science, vol. 4933, p.199—216, 2008.

52. Ganter B., Kuznetsov S. Formalizing Hypotheses with Concepts, Proc. 8th Int. Conf. on Conceptual Structures, ICCS’00, Lecture Notes in Artificial Intelligence, vol. 1867, p.342–356, 2000.

53. Ganter B., Kuznetsov S.O. Hypotheses and Version Spaces // Proc. 10th Int. Conf. on Conceptual Structures, ICCS’03, Lecture Notes in Artificial Intelligence, vol. 2746, p.83–95, 2003.

54. Ganter B., Wille R. Formal Concept Analysis: Mathematical Foundations // Springer, Berlin, 1999.

55. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness // W. H. Freeman, 1979.

56. Gold E.M. Language identification in the limit // Information and Control, vol. 10, p.447–474, 1967.

57. Habib M., Medina R., Nourine L., Steiner G. Efficient algorithms on distributive lattices // Discrete Applied Mathematics, vol. 110, no.2-3, p.169–187, 2001.

Ibaraki T., Kogan A., Makino K. Functional Dependencies in Horn Theories // Artificial Intelligence, vol. 108, no. 1-2, p.1–30, 1999.

58. Jay N., Kohler F., Napoli A. Analysis of Social Communities with Iceberg and Stability-Based Concept Lattices // Proc. 6th International Conference on Formal Concept Analysis (ICFCA’2008), p.258-272, 2008.

59. Jerrum M. R., Valiant L.G., Vazirani V.V. Random generation of combinatorial structures from a uniform distribution // Theoretical Computer Science, vol. 43, no. 2-3, p.169–188, 1986.

60. Jiawei H., Jian P., Yiwen Y., Runying M. Mining frequent patterns without candidate generation // Data Mining and Knowledge Discovery, vol. 8, p.53–87, 2004.

61. Johnson D.S., Papadimitriou C.H., Yannakakis M. On Generating All Maximal Independent Sets // Informaion Processing Letters, vol. 27, no.

3, p.119–123, 1988.

62. Kavvadias D. J., Sideri M., Stavropoulos E. C. Generating All Maximal Models of a Boolean Expression, 1999.

63. Kavvadias D.J., Stavropoulos E.C. An Efficient Algorithm for the Transversal Hypergraph Generation // J. Graph Algorithms Appl., vol.

9(2), p.239–264, 2005.

64. Khardon R. Translating between Horn Representations and their Characteristic Models // J. Artificial Intelligence, vol. 3, p.349–372, 1995.

65. Kivinen J., Mannila H. Approximate Inference of Functional Dependencies from Relations // Theoretical Computer Science, vol. 149, no. 1, p.129– 149, 1995.

66. Klimushkin M., Obiedkov S.A., Roth C. Approaches to the Selection of Relevant Concepts in the Case of Noisy Data // Proc. 8th International Conference on Formal Concept Analysis (ICFCA’2010), p.255-266, 2010.

67. Kourie D.G., Obiedkov S.A., Roth C. Towards Concise Representation for Taxonomies of Epistemic Communities // Proc. International Conference Concept Lattices and Their Applications (CLA’2006), Tunis (Tunisia), p.240–255, 2006.

68. Kuznetsov S.O. Stability as an estimate of the degree of substantiation of hypotheses derived on the basis of operational similarity // Nauchn.

Tekh. Inf., ser 2., №12, p.21–29, 1990.

69. Kuznetsov S.O. On Computing the Size of a Lattice and Related Decision Problems // Order, 18(4), p.313–321, 2001.

70. Kuznetsov S.O. Machine Learning on the Basis of Formal Concept Analysis // Automation and Remote Control, vol. 62, no. 10, 2001.

71. Kuznetsov S.O., Obiedkov S.A. Comparing performance of algorithms for generating concept lattices // J. Exp. Theor. Artif. Intell., 14, 2-3, p.189– 216, 2002.

72. Kuznetsov S.O. Stability of a Formal Concept // Proc. 4th Journee d’Informatique Messine (JIM’03), Metz, 2003.

73. Kuznetsov S.O. On the intractability of computing Duquenne-Guigues base // J. Universal Computer Science, vol. 10, no. 8, p.927–933, 2004.

74. Kuznetsov S.O. Complexity of Learning in Concept Lattices from Positive and Negative Examples // Discrete Applied Mathematics, no. 142, p. 111 125, 2004.

75. Kuznetsov S.O. On Stability of a Formal Concept // Annals of Mathematics and Artificial Intelligence, vol. 49, p.101–115, 2007.

76. Kuznetsov S.O., Obiedkov S.A. Counting pseudo-intents and #P completeness // Proc. ICFCA 2006, Lecture Notes in Computer Science, vol. 3874, p.306—308, Springer, 2006.

77. Kuznetsov S.O., Obiedkov S.A., Roth C. Reducing the Representation Complexity of Lattice-Based Taxonomies // Proc. 15th International Conference on Conceptual Structures (ICCS’07), Lecture Notes in Artificial Intelligence (LNAI), vol. 4604, p.241–254, Springer, 2007.

78. Kuznetsov S.O., Obiedkov S.A. Some decision and counting problems of the Duquenne-Guigues basis of implications // Discrete Applied Mathematics, 156(11), p.1994-–2003, 2008.

79. Krtzsch M. and Malik G. The Tensor Product as a Lattice of Regular o Galois Connections // Proc. 4th Inernational Conference on Formal Concept Analysis (ICFCA’2006), Lecture Notes in Artificial Intelligence (LNAI), vol. 3874, p.89–104, Springer 2006.

80. Loshin D. Master Data Management // Morgan Kaufmann Publishers, 2009.

81. Mannila H., Rih K. The design of relational databases // Addison aa Wesley, 1992.

82. Mohammed Z.J. Scalable algorithms for association mining // IEEE Transactions on Knowledge and Data Engineering, vol. 12(3), p.372–390, 2000.

83. Motwani R., Raghavan P. Randomized Algorithms // Cambridge University Press, 1995.

84. Nienhuys-Cheng S.-H., Wolf R. Foundations of Inductive Logic Programming, // Lecture Notes in Artificial Intelligence, vol. 1228, 1997.

85. Obiedkov S.A., Roth C., Kourie D.G. On Succinct Representation of Knowledge Community Taxonomies with Formal Concept Analysis // Int.

J. Found. Comput. Sci., 19(2), p.383–404, 2008.

86. Obiedkov S.A., Roth C., Kourie D.G. Towards Concise Representation for Taxonomies of Epistemic Communities // Proc. 4th International Conference Concept Lattices and Their Applications (CLA’2006), p.240– 255, 2008.

87. Piatetsky-Shapiro G. Discovery, Analysis, and Presentation of Strong Rules // Knowledge Discovery in Databases, p.229–248, 1991.

88. Poelmans J., Elzinga P., Neznanov A., Dedene G., Viaene S., Kuznetsov S.O. Human-Centered Text Mining: A New Software System // ICDM 2012, p.258–272, 2012.

89. Priss U. Some open problems in Formal Concept Analysis // Proc. ICFCA 2006, 2006.

90. Rudolph S. Some notes on pseudo-closed sets // Proc. ICFCA 2007, Lecture Notes in Computer Science, vol. 4390, p.151–165, Springer, 2007.

91. Sertkaya B. Towards the complexity of recognizing pseudo-intents // Proc.

ICCS 2009, Lecture Notes in Computer Science, vol. 5662, p.284–292, Springer, 2009.

92. Sertkaya B. Some computational problems related to pseudo-intents // Proc. ICFCA 2009, Lecture Notes in Computer Science, vol. 5662, p.284– 292, Springer, 2009.

93. Singh K., Singh R. A Descriptive Classification of Causes of Data Quality Problems in Data Warehousing // International Journal of Computer Science Issue, vol. 7, Issue 3, No. 2, 2010.

94. Solomonoff R.J. A formal theory of inductive inference // Information and Control, vol. 7, p. 224–254, 1964.

95. Valiant L.G. The complexity of computing the permanent // Theoretical Computer Science, 8, No. 2, p.189–201, 1979.

96. Valiant L.G. The Complexity of Enumeration and Reliability Problems // SIAM J. Comput., 8, no. 3, p.410–421, 1979.

97. Valiant L.G. A theory of the learnable // Commun. ACM, 27, no. 11, p.1134–1142, 1984.

98. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets, Reidel, p.445–470, Dordrecht–Boston, 1982.

99. Wille R. Conceptual Structure of Multicontexts // Proc. 4th International Conference on Conceptual Structures, Lecture Notes in Artificial Intelligence (LNAI), vol. 1115, p.23–39, Springer, 1996.

100. Сайт репозитория машинного обучения UCI http://archive.ics.uci.edu/ml/ Приложения 5.5. Приложение 1. Файл mset.h:

#i f n d e f MSET_H #define MSDET_H #include v e c t o r #include a l g o r i t h m typedef s t d : : v e c t o r int mset ;

mset rand_set ( int M, double p ) ;

mset get_union ( const mset& A, const mset& B) ;

mset g e t _ i n t e r s e c t i o n ( const mset& A, const mset& B) ;

bool i s _ s u b s e t ( const mset& s u p e r s e t, const mset& s u b s e t ) ;

void p r i n t ( const mset& s, int M) ;

#endif Файл mset.cpp:

#include " mset. h" #include s t d l i b. h mset get_union ( const mset& A, const mset& B) { mset r e t ;

bool ok = true ;

f o r ( int i = 1 ;

i A. s i z e ( ) ;

++i ) { i f (A[ i ] A[ i 1 ] ) { ok = f a l s e ;

break ;

} } i f ( ok ) { f o r ( int i = 1 ;

i B. s i z e ( ) ;

++i ) { i f (B [ i ] B [ i 1 ] ) { ok = f a l s e ;

break ;

} } } i f ( ok ) { int i = 0 ;

int j = 0 ;

while ( i A. s i z e ( ) && j B. s i z e ( ) ) { i f (A[ i ] B [ j ] ) { r e t. push_back (A[ i ] ) ;

++i ;

} e l s e i f (A[ i ] B [ j ] ) { r e t. push_back (B [ j ] ) ;

++j ;

} else { r e t. push_back (A[ i ] ) ;

++i ;

++j ;

} } f o r ( ;

i A. s i z e ( ) ;

++i ) r e t. push_back (A[ i ] ) ;

f o r ( ;

j B. s i z e ( ) ;

++j ) r e t. push_back (B [ j ] ) ;

} else { int n = 0 ;

f o r ( int i = 0 ;

i A. s i z e ( ) ;

++i ) n = s t d : : max( n, A[ i ] + 1 ) ;

f o r ( int i = 0 ;

i B. s i z e ( ) ;

++i ) n = s t d : : max( n, B [ i ] + 1 ) ;

s t d : : v e c t o r bool used ( n, f a l s e ) ;

f o r ( int i = 0 ;

i A. s i z e ( ) ;

++i ) used [A[ i ] ] = true ;



Pages:     | 1 || 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.