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

Янкелевич Алексей Владимирович

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ПОИСКА ИНФОРМАЦИОННЫХ ШАБЛОНОВ В ХРАНИЛИЩАХ И ПОТОКАХ ТРАНЗАКЦИЙ

05 13 11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва-2007

Работа выполнена на кафедре «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей» Московского государственного университета приборостроения и информатики

Научный руководитель:

доктор технических наук, профессор Петров О М

Официальные оппоненты

доктор технических наук Ивашкин Ю А кандидат технических наук Стефанский М А

Ведущая организация:

Институт системного анализа РАН

Защита состоится 13 ноября 2007 г. в 12°° на заседании диссертационного совета Д 212 119 02 в Московском государственном университете приборостроения и информатики по адресу 107996 Москва, Стромынка,20 (тел 268-01-01)

С диссертацией можно ознакомиться в библиотеке МГУПИ Автореферат разослан 9 О Ктября 2007 г

Ученый секретарь диссертационного с к т н, профессор

Зеленко Г В

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы Совершенствование алгоритмов поиска и классификации взаимосвязей и закономерностей в гетерогенных хранилищах и потоках информации является одной из основных задач развития средств автоматизированного анализа С ростом локальных сетей, а также все большим использованием сети Internet увеличивается обмен как внутри организаций, так и между ними Возрастает количество поставщиков и пользователей информации Помимо увеличения плотности информационных потоков, усложняется и их структура Любая организация, как правило, для решения своих задач редко обходится одним программным комплексом Каждый из комплексов порождает свои информационные объекты. Существующие задачи стратегического анализа деятельности организации заставляют использовать гетерогенные хранилища и потоки информации, объединяющие в рамках одного информационного поля разнородные объекты.

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

• обработка результатов научно-технических исследований и испытаний образцов техники,

• обработка финансовой информации;

• анализ покупательской активности,

• мониторинг в системах безопасности,

• обработка потоков данных и мониторинг в системах автоматизации избирательных процессов,

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

Одним из решений обозначенных проблем являются так называемые системы извлечения данных (англ Data Mining). Научная область систем извлечения данных включает в себя практически все наиболее значимые направления исследования прикладного использования алгоритмов искусственного интеллекта К этим направлениям можно отнести классификацию, кластеризацию, поиск информационных шаблонов, прогнозирование. Одним из наиболее практически значимых направлений является поиск информационных шаблонов Под поиском информационных шаблонов понимается поиск и классификация взаимосвязей, закономерностей в гетерогенном хранилище или потоке информации Поскольку выявление взаимосвязей, подразумевает выполнение операций не на уровне отдельных информационных объектов, а на уровне всего хранилища/потока информации, то этот процесс является гораздо более вычислительно- и ресурсоемким, нежели обьгчные процедуры поиска и классификации в базах данных Таким образом, совершенствование алгоритмов поиска и классификации взаимосвязей и закономерностей в гетерогенных хранилищах и потоках информации является важной и актуальной для дальнейшего развития средств автоматизированного анализа Несмотря на то, что история разработки алгоритмов искусственного интеллекта, предназначенных для классификации, кластеризации и предсказания, насчитывает уже более полувека, направление, связанное с поиском информационных шаблонов, является относительно новым Первые значимые исследования в этой области датированы началом 90-х годов прошлого века. Сама концепция информационного шаблона впервые была предложена исследователями лаборатории ЮМ Research в 1992 году Исследователями М Заки, Р Агравапем была описана математическая модель поиска информационных шаблонов, предложена концепция элементного множества и последовательности элементных множеств

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

Реализация поставленной цели подразумевает решение следующих задач

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

• Исследование проблемы поиска элементных множеств и последовательностей в потоках информации,

• Разработка алгоритма поиска последовательностей в информационном хранилище,

• Разработка алгоритма поиска элементных множеств в потоке информации,

• Разработка алгоритма поиска последовательностей в потоке информации,

• Программная реализация разработанных алгоритмов

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

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

Научная новизна Научная новизна работы заключается в следующем

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

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

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

• Предложены методы оценки качества алгоритмов поиска элементных множеств и последовательностей;

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

Реализация результатов Разработанные в данной работе программные средства входят в состав программного обеспечения «Система автоматизации информационной инфраструктуры»

Апробация работы Результаты диссертационной работы докладывались и обсуждались на трех конференциях в 2005, 2006 годах на всероссийской конференции студентов, аспирантов и молодых ученых «Технологии МюгобоЙ в теории и практике программирования» и 2007 году

на XXXVI международной конференции молодых ученых «Информационные технологии в науке, социологии, экономике и бизнесе IT+S&E'07»

Публикации По материалам диссертационной работы опубликовано 7 печатных работ.

Структура диссертации Диссертация состоит из введения, четырех глав, заключения и списка литературы

Общий объем работы - 132 с машинописного текста, включая 39 рисунков и 59 таблиц

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, сформулированы цель, задачи, объект и предмет исследования, определены научная и практическая значимость работы, приведена краткая характеристика основных разделов диссертации

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

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

Определение. Если дан определенный класс шаблонов Р и предикат q, определяющий интересность q Р -> {0,1}, то набор Р„= {р е Р • q(p) = 1} будем считать интересными шаблонами Дополнение Qq= Р\ Pq представляет набор неинтересных шаблонов

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

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

Определение (элементы и элементные множества). Пусть дано множество возможных элементов L Элементным множеством X называется подмножество L Для краткости дальнейшего изложения элементное множество X, состоящее из элементов Ai,A2,.. ,А|Х| будем записывать AiA2.. А|х|.

Приведены определения таких ключевых понятий как транзакция, транзакционная база данных, покрытие, поддержка, частота

Определение (транзакции и транзакционные базы данных)

Транзакцией t назовем пару <i,X>, где i - номер транзакции (tid), а X -элементное множество Количество элементов в элементном множестве X транзакции t=<i,X> обозначим [t|

Транзакционной базой данных D будем называть набор транзакций Каждая транзакция в D имеет уникальный порядковый номер Количество транзакций определяется как |D| и номера транзакций определяются tid(D) = {1, -JD|}

Определение (покрытие, поддержка и частота). Транзакция t=<i,Y> покрывает элементное множество X, если ХсУ Покрытие элементного множества X в D есть множество соver(X,D)= (i < i,Y >е D,X ^У] Поддержкой sup(X) элементного множества в базе данных D называется мощность множества cover sup(X,D) = |cover(X,D)| Частотой X в D называется поддержка X деленная на мощность множества D

\D\

Дается описание новой области исследования - поиск последовательностей элементных множеств в хранилищах и потоках информации

В первой главе даны математические основы к кластеризации в алгоритмах поиска информационных шаблонов

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

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

Алгоритм начинается с определения всех последовательностей длины 1, для которых Sup(S)>MinSup Все последовательности, не обладающие необходимой поддержкой, отсекаются. Обозначим полученное множество всех S(l), обладающих необходимой поддержкой, Н(1) Далее, попарно комбинируя элементы Н(1), сгенерируем множество кандидатов последовательностей длины 2 Алгоритм генерации последовательностей-

кандидатов длины 2 представлен ниже' __________

Из 2-х элементов Si(l) и S2(l) можно образовать последовательность

1 {Si(l)S2(l)} - назовем это 1-шаг,

2 fSi(l), S2(I)} - назовем это S-шаг

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

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

последовательностей- кандидатов длиной, превышающей 2_

Рассмотрим 2 последовательности 81={ХЬХ2, Хт} и 52={У/, У2, Л„} Возможны 2 варианта объединения

1 5 - шаг: Если К, является подмножеством Х„, и 5/ состоит более чем из одного элементного множества, то 5шндидат={Х1Х2, Хт,Уъ ,У„ }

2 I — шаг:

а Если т-п и 5; и различаются только одним элементом в множествах Хт и У„ , то

^.иУ.ДХ.П!',)},

Ь Если У[ является подмножеством Х„, и Б/ состоит из одно _элементного множества, то 5ка„дшк,т--{Х¡Х2, Хт, У2, ,У„ }_

После генерации кандидата 5 необходимо убедиться, что Яир (5)>Мт$ир

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

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

Алгоритм заканчивает работу в момент, когда на определенном шаге J невозможно сгенерировать кандидатов, обладающих требуемой поддержкой

Все последовательности с шага */-/, участвующие в генерации кандидатов шага 7 добавляются в результирующий набор

Все используемые матрицы, отсортированы по возрастанию по колонкам СГО,ТГО.

На первом шаге сформируем матрицу принадлежности /последовательности Б(1) для каждой записи {СЮ.ТЮ} в базе данных, в виде таблицы 1:

Таблица 1 Матрица принадлежности последовательностей

СЮ TID | Бит принадлежности

<CID> <TID> 1 - если S( 1) принадлежит транзакции 1 0 - в противном случае

На втором и последующих шагах сгенерируем матрицы для последовательностей-кандидатов, полученных с помощью 5- и 1-шагов Матрица и правила вычисления битов представлены в таблице 2.

CID TID S.(j-l) S2(j-1) Кандидат на шаге J

I-шаг в-шаг

<сш> <тю> bi b2 b, ль2 1- если для одного и того же СЮ, существует ТГО52>ТЮМ такой, что Ъ2 (ТШ52) =1 и Ы(ТГО5!)=1 0- в противном случае

Для оценки производительности нового алгоритма выполнялось сравнение его скорости работы и наиболее производительных в настоящий момент алгоритмов SPADE и PrefixSpan Сравнение выполнялось двумя различными способами Во-первых, замерялась скорость работы трех алгоритмов на малых, средних и больших наборах данных для различных значений минимальной поддержки Ряд замеров показал, что разработанный алгоритм превосходит SPADE приблизительно в 2 5 раза на малых наборах данных и почти на порядок на больших наборах данных PrefixSpan превосходит немного разработанный алгоритм на малых наборах данных, но проигрывает ему почти на порядок на больших. Тестирование алгоритмов выполнялось на синтетических данных Для генерации тестовых данных использовался алгоритм AssocGen В качестве параметров AssocGen принимает следующие значения, см таблицу 3.

Таблица 3 Параметры генератора тестовых данных

Параметр Значение

D Количество сессий в наборе данных

С Среднее количество транзакций на сессию

Т Среднее количество элементов на транзакцию

S Средняя длина максимальной последовательности

I Средняя длина транзакций в максимальной последовательности

Иллюстрация замеров скорости работы представлена в таблице 4 и на рисунке 1

Таблица 4 Результат замеров

Параметр Значение

D 5

С 15

Т 10

S 10

1 10

Мин поддержка 0 3 0 35 04 0 45 0 5

Время работы "Алгоритм" с 103 49 15 6 5

Время работы "SPADE" с 954 367 67 43 19

Время работы "PrefixSpan" с 386 168 44 20 7

Рисунок 1 Замер скорости работы алгоритма

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

Окно 1

Окно 2

Окно 3

N+1

Окно 4

Рисунок 2 Плавающее окно

N+1

Время

В алгоритме поиска элементных множеств разрабатывается новая структура для увеличения скорости работы алгоритма. Структура основана

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

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

Родительская Родительская

последовательность 1 последовательность 2

Ссыпка на родителя 1 Ссылка на родителя 2 I I юрядковыи I

I номер I

Тип операции

Отсортированный массив \Л // элементов последнего элементного множества . '•'" Ч I I 1-0 Хеш-таблица последовательности

Щ ■■' I дочерние

Ссылки на дочерние последовательности

Рисунок 3 Структура узла лексикографического дерева

Искомые максимальные последовательности являются листовыми элементами дерева. Дерево вдоль вертикальной оси делится на уровни.

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

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

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

2. элементы А и В образуют последовательность А -> В, если в рамках одной сессии В, часть номеров транзакций элемента В больше, чем часть номеров транзакций элемента А. При генерации следует учитывать, что А->В не эквивалентно В->А.

Ьс -> <)

|Л| Уровень 3

Ь->а

Ьс

Ь->с1

с->д

КДЛ Уровень 2

Уровень 1

Ь |

I

2 !

Рисунок 4 Лексикографическое дерево

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

1 если последовательности SI и S2 отличаются друг от друга только последними элементами А и В, соответственно, то кандидат образуется путем добавления к S1 элемента В, если А<В ИЛИ объединением S2 и А, если А>В Хеш-таблица вычисляется по следующему алгоритму

1 1 Для каждого номера сессии получить списки номеров транзакций последовательностей SI и S2

111 вычислить подмножество I как пересечение множеств номеров транзакций Tend(S¡) и Tend(S2),

112 присвоить списку Tend, результирующей последовательности значение I

2 Для каждой последовательности выполняется проверка на возможность увеличить размерность последовательности на единицу Обозначим через Suffix(S) - последнее элементное множество последовательности Дчя каждого элемента Ai множества Suffix(S) найти последовательность вида Ai->Bj, такую, что Sup(Ai->Bj)>=MinSup Если последовательности S->Bj еще не существует, вычислить хеш-таблицу для последовательности S->Bj по следующему алгоритму

21 Для каждого номера сессии получить списки SList последовательностей Ai->Bj, такие, что в каждом списке {Ai} = Suffix(S) и все последовательности внутри списка имеют одинаковое окончание Bj

2 11 Для каждого списка SLisífkJ последовательностей из SList 2 111 Составить множество 1 из всех элементов множества Tend первой последовательности списка SListfk], значение которых больше Min(Tend(S)), 2 112 Если 1 не пусто, использовать его в качестве значения множества Tend результирующей последовательности

Предложены эвристические подходы по оптимизации выполнения I- и 8-шагов

Рассмотрим более подробно этап удаления самой старой транзакции Для описания процесса введем следующие обозначения

1 ЗеБзюпСБ , I) - функция проверяет принадлежит ли последовательность Б сессии с номером I Для проверки принадлежности, выполняется поиск номера сессии в списке ключей хеш-таблицы последовательности,

2 МтТ(1) — функция, возвращает минимальный номер транзакции для сессии с номером I Функция построена на базе массива минимальных номеров транзакций для каждой из сессий Массив формируется на этапе заполнения окна транзакциями Далее при поступлении каждой новой транзакции, номер вытесненной транзакции заменяется на номер следующей по очереди

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

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

алгоритму_________

I Для каждой одноэлементной последовательности S 1 1 проверяем ее принадлежность к номеру сессии 1 и транзакции с номером MinT(I) Если принадлежность определяется, то

111 из хеш-таблицы последовательности по номеру сессии I извлечь массивы Tstart и Tend Удалить из массива Тstart первый элемент Удалить из Tend все элементы, которые меньше или равны новому первому элементу Tstart Если Tstart = 0, то удалить из хеш-таблицы элемент с ключом 1,

112 Если Sup(S)>=MinSup, то для каждого дочернего элемента S рекурсивно выполнить шаг 11, в противном случае если длина последовательности больше 1, удалить S и все дочерние элементы

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

1 Для каждого элемента добавляемой транзакции пройти по всему поддереву, порождаемому элементом В каждом узле поддерева по номеру текущей транзакции найти в хеш-таблице список Tend В найденный список внести номер добавляемой транзакции,

2 Во время прохода по поддереву для каждого листового элемента проверить возможность порождения последовательности длины |5| + 1 При этом следует учитывать, что S-шаг имеет смысл только для 2-х элементных последовательностей, оканчивающихся на элемент, принадлежащий новой транзакции Аналогично, 1 — шаг имеет смысл только для последовательностей, оканчивающихся на элементы, принадлежащие новой транзакции

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

• количество сессий О,

• размер окна N.

• среднее количество элементов на транзакцию Т,

• средняя глубина лексикографического дерева Н,

• средняя ширина лексикографического дерева

• минимальная требуемая поддержка МтБир,

Выполнена как теоретическая, так и экспериментальная оценка объемов потребляемой памяти, см таблицы 5,6.

Таблица 5 Теоретическая оценка

О N т н \У Память, Мб Количество узлов в дереве

1000 100 10 15 200 76,2105 3000

1000 100 10 15 400 153,321 6000

1000 100 10 15 800 310,242 12000

1000 100 10 15 1600 634,884 24000

1000 100 10 15 3200 1327,368 48000

Таблица б Результаты экспериментальны* замеров

И N т Мшвир Память, Мб Количество узлов в дереве

1000 100 20 0,7 528 20341

1000 100 20 0,75 488,43 18786

1000 100 20 0,8 373,2 14354

1000 100 20 0,85 249,23 9586

1000 100 20 0,9 149,8 5743

Следующей важной характеристикой алгоритма является время перестроения лексикографического дерева Суть экспериментов заключалась в определении влияния параметров алгоритма на время выполнения Варьированию подвергались минимальная поддержка, количество сессий и среднее количество элементов в транзакции Приведем результаты экспериментальных прогонов алгоритма в таблицах Зафиксировав все параметры кроме минимальной поддержки, были получены следующие результаты замеров, см таблицы 7, 8,9

Таблица 7 Результаты экспериментов

№ эксперимента О N т М11гёир Время работы, сек

1 100 100 20 0,7 2,71

2 100 100 20 0,7 3,23

3 100 100 20 0,7 2,94

4 100 100 20 0,7 2,75

5 100 100 20 0,7 2,86

Таблица 8 Результаты экспериментов

№ эксперимента О N т Мпгёир Время работы, сек

1 100 100 20 0,75 2 27

2 100 100 20 0,75 2 24

3 100 100 20 0,75 2,24

4 100 100 20 0,75 2 47

5 100 100 20 0,75 2,17

Таблица 9 Результаты экспериментов

№ эксперимента О N т Мтвир Время работы, сек

1 100 100 20 0.85 1,3

2 ¡00 100 20 0,85 1.58

3 100 100 20 0.85 1,44

4 100 100 20 0,85 1,35

5 100 100 20 0,85 1,32

Вычислив среднее время работы для каждого из блоков экспериментов, получим следующую таблицу 10 и гистограмму на рисунке 5.

Таблица 10 Агрегированные результаты экспериментов

МтЗир 0.7 0,75 0,85

Время, сек 2,898 2,278 1,398

Рисунок 5 Агрегированные результаты экспериментов

Эксперименты показали следующее. При изменении минимальной поддержки время работы алгоритма изменяется практически линейно. При изменении количества сессий на 200% среднее время работы изменилось на 2%. Оба наблюдения являются хорошей характеристикой алгоритма с практической точки зрения, поскольку обеспечивают не только высокую производительность алгоритма, но и масштабируемость и предсказуемость систем, построенных на его базе.

Четвертая глава содержит описание использования разработанных алгоритмов в компании ЗАО "КРОК инкорпорейтед", в программном обеспечении «Система автоматизации информационной инфраструктуры». Апробация разработанных алгоритмов проводилась при построении внутренней системы автоматизации бизнес-процессов компании «КРОК инкорпорейтед». Целью применения разработанных в диссертации алгоритмов было решение следующих задач:

• повышение уровня доступности сервисов и релевантности сопроводительной документации для сотрудников компании;

• сокращение числа запросов, связанных с поиском информационных сервисов, в аналитическую службу.

Задача автоматизации доступа к информационной инфраструктуре компании состоит из нескольких составляющих В компании разработано порядка 80 сервисов, предоставляющих информационное обеспечение сотрудникам компании Помимо сервисов, существует база знаний компании, хранящая нормативно-справочную, техническую и правовую документацию. Сотрудники обращаются к сервисам в рамках выполнения определенных бизнес-процессов Бизнес-процесс состоит из обращения к последовательности сервисов В свою очередь каждый из сервисов состоит их нескольких атомарных операций по вводу данных В процессе работы с сервисов требуется многочисленное обращение к документации из базы знаний компании Документация, таким образом, как бы обеспечивает информационный контекст бизнес-процесса, причем данный контекст непосредственно зависит от вводимых данных, а также последовательности исполнения сервисов, см рисунок 6

Рисунок 6 Система автоматизации информационной инфраструктуры

Транзакцией в данной системе является совокупность введенных данных и использованных при работе с сервисом документов из базы знаний Сессия соответствует отдельному пользователю системы

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

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

• на основе поиска максимальных последовательностей в «плавающем» окне Для поиска используется алгоритм поиска последовательностей в потоке транзакций

Комбинирование двух способов формирования информационного контекста позволило обеспечить пользователя исчерпывающим набором наиболее «интересных» документов

Для оценки эффективности построенной системы, в течении 5 недель собиралась статистика по количеству запросов на информацию от пользователей в аналитическую службу В таблице 11 представлен относительный процент сокращения запросов пользователей

Таблица 11 Снижение количества запросов пользователей

Номер недели 1 2 3 4 5

Относительный процент уменьшения запросов пользователей 1,2% 3,5% 6,3% 14,1% 18,7%

За счет применения предложенного решения удалось достичь следующих результатов

• сокращение запросов от пользователей к аналитической службе,

• повышение релевантности найденных документов

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

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

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

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

4. Разработан алгоритм поиска последовательностей элементных множеств в потоке данных Предложен новый подход к обработке данных внутри «плавающего окна» Проведено практическое исследование алгоритма Предложены подходы к теоретической оценке показателей производительности алгоритма

Создана библиотека программных компонент, реализующих предложенные алгоритмы

Результаты работы используются в программном обеспечении «Система автоматизации информационной инфраструктуры»

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Россинский Е Б , Янкелевич А В Комплекс обработки и архивирования радиографических снимков // Труды Всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования». - М Издательство МГТУ им Н Э Баумана, 2005 - с 22-23

2 Янкелевич А В Построение автоматизированных систем текстовой классификации на базе векторной модели // Математическое моделирование и управление в сложных системах. Сборник научных трудов Выпуск 8 - М . МГАПИ, 2005 -с 98-101

3 Янкелевич А В Система извлечения информации из полуструктурированных текстов на естественном языке // Труды Всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» - М Издательство МГТУ им. Н Э Баумана, 2006 - с 75

4 Янкелевич А В Фонетический анализ в задачах текстовой классификации // Математическое моделирование и управление в сложных системах. Сборник научных трудов Выпуск 8 - М МГАПИ, 2005.-с 101-102.

5 Янкелевич А В Алгоритм поиска максимальных элементных множеств в потоках транзакций // Материалы IV международной конференции молодых ученых «Информационные технологии в науке, социологии, экономике и бизнесе IT+S&E'07» — М Приложение к журналу «Открытое образование», 2007 - с 132-134

6 Ахрем А А, Янкелевич А В Поиск максимальных последовательностей элементных множеств с помощью битовых матриц // Сборник ИСА РАН «Информационно аналитические аспекты в задачах управления» — М КомКнига, 2007 -с 276-289

7 Янкелевич А В Алгоритм поиска максимальных последовательностей элементных множеств с помощью битовых матриц // Сборник трудов X Всероссийской научно-технической конференции (Москва, МГУПИ, 19-20 апреля 2007г)-М МГУПИ, 2007. - с 180-184

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25 09 2000 г Подписано в печать 25 09 07 Тираж 100 экз Усл. п л 1,25 Печать авторефератов (495) 730-47-74, 778-45-60

ВВЕДЕНИЕ

ГЛАВА 1. ПРОБЛЕМЫ ПОИСКА ИНФОРМАЦИОННЫХ ШАБЛОНОВ В ХРАНИЛИЩАХ И ПОТОКАХ ИНФОРМАЦИИ

1.1. ЭВОЛЮЦИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ

1.2. Анализ современных средств поиска информационных шаблонов

1.2.1. Информационный шаблон

1.2.2. элементные множества и последовательности элементных множеств

1.2.3. Ассоциативные правила

1.2.4. Основы теории поиска информационн ых шаблонов

1.2.5. Компактное представление коллекций шаблонов

1.2.6. Кластеризация

1.3. Выводы и постановка задачи

ГЛАВА 2. ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПОИСКА ИНФОРМАЦИОННЫХ ШАБЛОНОВ В ХРАНИЛИЩАХ ИНФОРМАЦИИ

2.1. Задача поиска последовательностей элементных множеств в хранилище транзакций

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

2.3. Исследование эффективности алгоритма

2.4. Выводы

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ ПОИСКА ШАБЛОНОВ В ПОТОКАХ ТРАНЗАКЦИЙ

3.1. Задача поиска информационных шаблонов в потоке транзакций

3.2. Разработка алгоритма поиска элементных множеств в потоке транзакций

3.3. Исследование эффективности алгоритма поиска элементных множеств в потоке транзакций

3.4. Разработка алгоритма поиска последовательностей элементных множеств в потоке транзакций

3.5. Исследование эффективности алгоритма поиска последовательностей элементных множеств в потоке транзакций

3.6. Выводы

ГЛАВА 4. ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ В ЗАДАЧАХ ИНФОРМАЦИОННО-АНАЛИТИЧЕСКОГО ОБЕСПЕЧЕНИЯ

4.1. Система автоматизации информационной инфраструктуры

4.2. выводы

Актуальность проблемы. Совершенствование алгоритмов поиска и классификации взаимосвязей и закономерностей в гетерогенных хранилищах и потоках информации является одной из основных задач развития средств автоматизированного анализа. С ростом локальных сетей, а также все большим использованием сети Internet увеличивается обмен как внутри организаций, так и между ними. Возрастает количество поставщиков и пользователей информации. Помимо увеличения плотности информационных потоков, усложняется и их структура. Любая организация, как правило, для решения своих задач редко обходится одним программным комплексом. Каждый из комплексов порождает свои информационные объекты. Существующие задачи стратегического анализа деятельности организации заставляют использовать гетерогенные хранилища и потоки информации, объединяющие в рамках одного информационного поля разнородные объекты.

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

• обработка результатов научно-технических исследований и испытаний образцов техники;

• обработка финансовой информации;

• анализ покупательской активности;

• мониторинг в системах безопасности;

• обработка потоков данных и мониторинг в системах автоматизации бизнес-процессов;

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

Одним из решений обозначенных проблем являются так называемые системы извлечения данных (англ. Data Mining). Научная область систем извлечения данных включает в себя практически все наиболее значимые направления исследования прикладного использования алгоритмов искусственного интеллекта. К этим направлениям можно отнести классификацию, кластеризацию, поиск информационных шаблонов, прогнозирование. Одним из наиболее практически значимых направлений является поиск информационных шаблонов. Под поиском информационных шаблонов понимается поиск и классификация взаимосвязей, закономерностей в гетерогенном хранилище или потоке информации. Поскольку выявление взаимосвязей, подразумевает выполнение операций не на уровне отдельных информационных объектов, а на уровне всего хранилища/потока информации, то этот процесс является гораздо более вычислительно- и ресурсоемким, нежели обычные процедуры поиска и классификации в базах данных. Таким образом, совершенствование алгоритмов поиска и классификации взаимосвязей и закономерностей в гетерогенных хранилищах и потоках информации является важной и актуальной для дальнейшего развития средств автоматизированного анализа. Несмотря на то, что история разработки алгоритмов искусственного интеллекта, предназначенных для классификации, кластеризации и предсказания, насчитывает уже более полувека, направление, связанное с поиском информационных шаблонов, является относительно новым. Первые значимые исследования в этой области датированы началом 90-х годов прошлого века. Сама концепция информационного шаблона впервые была предложена исследователями лаборатории IBM Research в 1992 году. Исследователями М.Заки, Р.Агравалем была описана математическая модель поиска информационных шаблонов, предложена концепция элементного множества и последовательности элементных множеств.

Цели и задачи. Целью работы является повышение скорости работы алгоритмов поиска информационных шаблонов в хранилищах информации и разработка новых алгоритмов поиска информационных шаблонов в потоках информации.

Реализация поставленной цели подразумевает решение следующих задач:

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

• Исследование проблемы поиска элементных множеств и последовательностей в потоках информации;

• Разработка алгоритма поиска последовательностей в информационном хранилище;

• Разработка алгоритма поиска элементных множеств в потоке информации;

• Разработка алгоритма поиска последовательностей в потоке информации;

• Программная реализация разработанных алгоритмов.

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

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

Научная новизна. Научная новизна работы заключается в следующем:

• Разработан алгоритм поиска максимальных последовательностей элементных множеств в хранилищах данных с использованием битовых матриц. Алгоритм превосходит по скорости работы существующие аналоги;

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

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

• Предложен метод оценки ресурсоемкости алгоритма поиска элементных множеств и последовательностей элементных множеств;

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

Реализация результатов. Разработанные в данной работе программные средства входят в состав комплекса «Система автоматизации информационной инфраструктуры», внедренного в компании ЗАО «КРОК инкорпорейтед».

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на трех конференциях: в 2005, 2006 годах на всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» и 2007 году на XXXVI международной конференции молодых ученых «Информационные технологии в науке, социологии, экономике и бизнесе IT+S&E'07».

Публикации. По материалам диссертационной работы опубликовано 7 печатных работ.

Структура диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы.

6. Результаты работы используются в программном обеспечении «Система автоматизации информационной инфраструктуры» внедренном в компании ЗАО «КРОК инкорпорейтед». Выдан акт внедрения, подтверждающий практическую значимость разработанных в диссертации алгоритмов.

Заключение

Работа посвящена совершенствованию алгоритмов поиска информационных шаблонов в хранилищах транзакций и разработке новых алгоритмов поиска информационных шаблонов в потоках транзакций. Основные результаты работы следующие:

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

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

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

4. Разработан алгоритм поиска последовательностей элементных множеств в потоке данных. Предложен новый подход к обработке данных внутри «плавающего окна». Проведено практическое исследование алгоритма. Предложены подходы к теоретической оценке показателей производительности алгоритма;

5. Создана библиотека программных компонент, реализующих предложенные алгоритмы;

1. Ramesh С. Agarwal, Charu С. Aggarwal, and V. V. V. Prasad. A tree projection algorithm for generation of frequent item sets. Journal of Parallel and Distributed Computing, 61:350-371, 2001.

2. G. Ausiello, P. Crescenzi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, 1999.

3. Setsuo Arikawa and Einoshin Suzuki, editors. Discovery Science, 7th International Conference, DS 2004, Padova, Italy, October 2-5, 2004,

4. Proceedings, volume 3245 of Lecture Notes in Computer Science. Springer, 2004.

5. Ralph Kimball, "The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouses", John Wiley & Sons, 1996 и "The Data Webhouse Toolkit: Building the Web-Enabled Data Warehouse", John Wiley & Sons, 2000

6. E.F. Codd, S.B. Codd, and C.T.Salley, Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate. Technical report, 1993

7. Янкелевич A.B. Построение автоматизированных систем текстовой классификации на базе векторной модели // Математическое моделирование и управление в сложных системах. Сборник научных трудов. Выпуск 8. М.: МГАПИ, 2005.-с. 98-101.

8. Янкелевич А.В. Фонетический анализ в задачах текстовой классификации // Математическое моделирование и управление в сложных системах. Сборник научных трудов. Выпуск 8. М.: МГАПИ, 2005. - с. 101-102.

9. Ахрем А. А., Янкелевич А.В. Поиск максимальных последовательностей элементных множеств с помощью битовых матриц // Труды ИСА РАН «Информационно аналитические аспекты в задачах управления», Т.29. М.:КомКнига, 2007. - с. 276-289.

10. Янкелевич А.В. Алгоритм поиска максимальных последовательностей элементных множеств с помощью битовых матриц // Сборник трудов X Всероссийской научно-технической конференции (Москва, МГУ ПИ, 19-20 апреля 2007г.) М.: МГУПИ, 2007. - с.180-184.

11. Г. Корн, Т. Корн, Справочник по математике, М. «Наука» 1973 г., 832 стр. с илл.

12. Гутер Р.С., Резниковский П.Т., Программирование и вычислительная математика, М. «Наука» 1971 г., 264 стр. с илл.

13. Бермант А.Ф., Краткий курс математического анализа для втузов,М. Физматгиз 1963г., 664 стр. с илл.

14. Аттетков А.В., Галкин С.В., Зарубин B.C., Методы оптимизации, М. МГТУ им. Н.Э. Баумана

15. Правовая охрана программ для ЭВМи баз данных. М.: Издательство ПРИОР,2002. - 48 с.

16. Кнут Д.Э. Искусство программирования, том. 3. Сортировка и поиск.,СПб.: Издательский дом «Вильяме»

17. Кнут Д.Э. Искусство программирования, том. 1. Основные алгоритмы.,СПб.: Издательский дом «Вильяме»

18. Топп У., Форд У. Структуры данных С++

19. Дейт К.Дж., Введение в системы баз данных,6-е издание,24.0'Коннор Дж. Искусство системного мышления, Пер. с англ.

20. М.: Альпина Бизнес Букс,2006. 256 с.

21. Jean-Fran, cois Boulicaut and Savso Dvzeroski, editors. 2nd International Workshop on Knowledge Discovery in Inductive Databases, 2003.

22. Francesco Bonchi, Fosca Giannotti, Alessio Mazzanti, and Dino Pedreschi. ExAnte: Anticipated data reduction in constrained pattern mining. In Lavravc et al.

23. Mihai B'adoiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montr'eal, Qu'ebec, Canada, pages 250-257. ACM, 2002.

24. J'er'emy Besson, C'eline Robardet, and Jean-Fran.cois Boulicaut. Constraint-based mining of formal concepts in transactional data. In Dai et al. DSZ04., pages 615-624.

25. Leo Breiman. Random forests. Machine Learning, 45:5-32,2001.

26. Artur Bykowski, Jouni K. Sepp'anen, and Jaakko Holm'en. Model-independent bounding of the supports of Boolean formulae in binary data. In Mika Klemettinen and Rosa Meo, editors, KDID. Helsinki University Printing House, Helsinki, 2002.

27. Yves Bastide, Rafik Taouil, Nicolas Pasquier, Gerd Stumme, and Lotfi Lakhai. Mining frequent patterns with counting inference. SIGKDD Explorations, 2(2):66-75,2000.

28. Christian S. Calude. Algorithmic Information Theory: An Algorithmic Perspective. EATCS Texts in Theoretical Computer Science. Springer-Verlag, 2nd edition, 2002.

29. Toon Calders. Computational complexity of itemset frequency satisfiability. In Proceedings of the Twenty-Third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 13-18,2004, Maison de la Chimie, Paris, France. ACM, 2004.

30. Toon Calders. Deducing bounds on the supports of itemsets. In Meo et al. MLK04., pages 214-233.

31. Marek Chrobak and Christoph D'urr. Reconstructing polyatomic structures from discrete X-rays: NPcompleteness proof for three atoms. Theoretical Computer Science, 259(l-2):81-98, 2001.

32. Toon Calders and Bart Goethals. Minimal k-free representations of frequent sets. In Lavra"c et al.

33. Gemma Casas-Garriga. Discovering unbounded episodes in sequential data. In Lavravc et al.

34. E. G. Coffman Jr., C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, and M. Yannakakis. Perfect packing theorems and the averagecase behaviour of optimal and online bin packing. SIAM Review, 44(1 ):95-108,2002.

35. Nick Cercone, Tsau Young Lin, and Xindong Wu, editors. Proceedings of the 2001 IEEE International Conference on Data Mining, 29 November 2 December 2001, San Jose, California, USA. IEEE Computer Society, 2001.

36. W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani. Approximation schemes for clustering problems. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11,2003, San Diego, CA, USA. ACM, 2003.

37. Luc De Raedt. A perspective on inductive databases. SIGKDD Explorations, 4(2):69-77, 2003.

38. Heikki Mannila and Hannu Toivonen. Levelwise search and borders of theories in knowledge discovery. Data Mining and Knowledge Discovery, 1(3):241-258,1997.

39. Luc De Raedt, Manfred Jaeger, Sau Dan Lee, and Heikki Mannila. A theory of inductive query answering. In Kumar and Tsumoto KT02., pages 123-130.

40. Luc Dehaspe and Hannu T.T. Toivonen. Discovery of relational association rules. In Savso Dvzeroski and Nada Lavravc, editors, Relational Data Mining, pages 189-212. Springer, 2001.

41. Vladimir Estivill-Castro. Why so many clustering algorithms a position paper. SIGKDD Explorations, 4(l):65-75, 2002.

42. Tapio Elomaa and Juho Rousu. On the computational complexity of optimal multisplitting. Fundamenta Informaticae, 47(1—2):35—52, 2001.

43. Alexandre Evfimievski, Ramakrishnan Srikant, Rakesh Agrawal, and Johannes Gehrke. Privacy preserving mining of association rules. In Hand et al.

44. Usama Fayyad. The digital physics of data mining. Communications of the ACM, 44(3):62-65, 2001.

45. Martin Farach-Colton, Paolo Ferragina, and S. Muthukrishnan. On the sorting-complexity of suffix tree construction. Journal of the Association for Computing Machinery, 47(6):987—1011, 2000.

46. Uriel Feige. A threshold of In n for approximation set cover. Journal of the Association for Computing Machinery, 45(4):634 652,1998.

47. Tom'as Feder and Daniel H. Greene. Optimal algorithms for approximate clustering. In Proceedings of the twentieth annual ACM

48. Symposium on Theory of Computing, Chicago, Illinois, May 2-4, 1988, pages 434-444. ACM, 1988.

49. Walter D, Fisher. On grouping for maximum homogeneity. Journal of the American Statistical Association, 53(284):789-798,1958.

50. Csilla Farkas and Sushil Jajodia. The inference problem: A survey. SIGKDD Explorations, 4(2):6-l 1,2002.

51. Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. Journal of Computer and Systems Science, 57(2): 187-199, 1998.

52. Usama Fayyad and Ramasamy Uthurusamy. Evolving data mining into solutions for insights. Communications of the ACM, 45(8):28-31,2002.

53. Zvi Galil. Efficient algorithms for finding maximum matchings in graphs. ACM Computing Surveys, 18(l):23-38, 1986.

54. Robert Gwadera, Mikhail Atallah, and Wojciech Szpankowski. Reliable detection of episodes in event sequences. In Wu et al. WTS03., pages 67-74.

55. Floris Geerts, Bart Goethals, and Taneli Mielik'ainen. Tiling databases. In Arikawa and Suzuki AS04., pages 278-289.

56. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman and Company, 1979.

57. R. Giegerich and S. Kurtz. From Ukkonen to Mc-Creight and Weiner: A unifying view of linear-time suffix tree construction. Algorithmica, 19:331-353, 1997.

58. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31:228 248, 1999.

59. Dimitrios Gunopulos, Roni Khardon, Heikki Mannila, Sanjeev Saluja, Hannu Toivonen, and Ram Sewak Sharma. Discovering all most specific sentences. References 189ACM Transactions on Database Systems, 28(2): 140-174, 2003.

60. Lise Getoor, Ted E. Senator, Pedro Domingos, and Christos Faloutsos, editors. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24 27, 2003. ACM, 2003.

61. Gunter Grieser, Yuzuru Tanaka, and Akihiro Yamamoto, editors. Discovery Science, 6th International Conference, DS 2003, Sapporo, Japan, October 17- 19, 2003, Proceedings, volume 2843 of Lecture Notes in Computer Science. Springer, 2003.

62. Bart Goethals and Jan Van den Bussche. On supporting interactive association rule mining. In Yahiko Kambayashi, Mukesh K. Mohania, and A. Min Tjoa, editors, DaWaK, volume 1874 of Lecture Notes in Computer Science, pages 307-316. Springer, 2000.

63. Bart Goethals and Jan Van den Bussche. Relational association rules: Getting WARMeR. In Hand et al. Bernhard Ganter and Rudolf Wille. Formal Concept Analysis: Mathematical Foundations. Springer-Verlag, 1999.

64. David J. Hand, Niall M. Adams, and Richard J. Bolton, editors. Pattern Detection and Discovery, ESF Exploratory Workshop,1.ndon, UK, September 16-19, 2002, Proceedings, volume 2447 of Lecture Notes in Computer Science. Springer, 2002.

65. Jiawei Han, Russ B. Altman, Vipin Kumar, Heikki Mannila, and Daryl Pregibon. Emerging scientific applications in data mining. Communications of the ACM, 45(8):54-58, 2002.

66. David J. Hand. Pattern detection and discovery. In Hand et al. HAB02., pages 1-12.

67. Mohammed J. Zaki. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3):372-390, 2000.

68. Mohammed J. Zaki. SPADE: An efficient algoritm for mining frequent sequences. Machine Learning, 42:31- 60, 2001.

69. Mohammed J. Zaki. Efficiently mining frequent trees in a forest. In Hand et al. HKN02.

70. Mohammed Javeed Zaki and Mitsunori Ogihara. Theoretical foundations of association rules. In SIGMOD'

71. D. Hand, D. Keim, and R. Ng, editors. Proceedings of the Eighth ACM SIGKDD International Conference References 191 on Knowledge Discovery and Data Mining, July 23-26, 2002, Edmonton, Alberta, Canada. ACM, 2002.

72. PauI Helman, Bernard M. E. Moret, and Henry D. Shapiro. An exact characterization of greedy structures. SIAM Journal on Discrete Mathematics, 6(2):274 283, 1993.

73. David J. Hand, Heikki Mannila, and Padhraic Smyth. Principles of Data Mining. MIT Press, 2001.

74. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Auotmata Theory, Languages and Computation. Addison-Wesley, 2nd edition, 2001.

75. Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent patterns without candidate generation: A frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(l):53-87, 2004.

76. Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. Springer-Verlag, 2001.

77. Robert W. Irving and Mark R. Jerrum. Threedimensional statistical data security problems. SIAM Journal on Computing, 23(1): 170-184, 1994.

78. Thomasz Imieli'nski, Leonid Khachiyan, and Amin Abdulghani. Cubegrades: Generalizing association rules. Data Mining and Knowledge Discovery, 6(3):219-257, 2002.

79. Thomas Imielinski and Heikki Mannila. A database perspective on knowledge discovery. Communications of The ACM, 39(11):58—64, 1996.

80. Akihiro Inokuchi, Takshi Washio, and Hiroshi Motoda. Complete mining of frequent patterns from graphs: Mining graph data. Machine Learning, 50:321-354, 2003.

81. H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Viswanath Poosala, Kenneth C. Sevcik, and Torsten Suel. Optimal histograms with quality guarantees. In Ashish Gupta, Oded Shmueli, and Jennifer

82. Widom, editors, VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA, pages 275- 286. Morgan Kaufmann, 1998.

83. Stasys Jukna. Extremal Combinatorics: With Applications in Computer Science. EATCS Texts in Theoretical Computer Science. Springer-Verlag, 2001.

84. Michihiro Kurakochi and George Karypis. Frequent subgraph discovery. In Cercone et al. CLW01., pages 313-320.

85. O.David Kempe, Jon Kleinberg, and 'Eva Tardos. Maximizing the spread of influence through a social network.

86. Jon Kleinberg. An impossibility theorem for clustering. In Advances in Neural Information Processing Systems (NIPS), volume 15, 2002.

87. Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Computational Geometry: Theory and Applications, 28:89-112, 2004.

88. Donald E. Knuth. Sorting and Seaching, volume 3 of The Art of Computer Programming. Addison-Wesley, second edition, 1998.

89. Ron Kohavi, Neal J. Rothleder, and Evangelos Simoudis. Emerging trends in business analytics. Communications of the ACM, 45(8):45-48, 2002.

90. Marzena Kryszkiewicz. Concise representation of frequent patterns based on disjunction-free generators. In Cercone et al., pages 305312.

91. Feng Pan, Gao Cong, Anthony К. H. Tung, Jiong Yang, and Mohammed J. Zaki. CARPENTER: Finding closed patterns in long biological datasets. In Getoor et al.

92. Jianyong Wang, Jiawei Han, and Jian Pei. CLOSET+: Searching for the best strategies for mining frequent closed itemsets. In Getoor et al.

93. J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen,U. Dayal, and M.-C. Hsu. PrefixSpan miningR.

94. О внедрении результов кандидатской диссертации «Математическое и программное обеспечение для поиска информационных шаблонов в хранилищах и потоках транзакций»