Разработка системы поиска логических закономерностей в реляционных базах данных Выполнила : Чуйко Ю. В. Научный руководитель : к. ф.- м. н., доцент Вдовицын В. Т.

Введение С развитием информационных технологий наиболее популярным способом хранения информации стала организация реляционных баз данных. Средства СУБД облегчает обработку собранного материала, однако стандартный набор их возможностей ( ввод, поиск, корректировка данных ) недостаточен для более сложного автоматизированного анализа данных. В настоящее время активно развивается Data Mining - направление, в рамках которого разрабатываются методы интеллектуального анализа больших объемов информации.

Цели работы Исследование возможностей применения методов Data Mining для решения задач анализа реляционных баз данных в технических и в гуманитарных областях науки Разработка методики применения этих методов на практике Создание программных средств для автоматизации процесса проведения анализа данных на основе данной методики

Методы Data Mining Вывод уравнений – Входные данные - выборки числовых значений – Результат - зависимости в виде уравнений – Используемая база - математический аппарат прикладной статистики, методы ИИ – Примеры - регрессионный, дисперсионный, дискриминантный, кластерный и т. д. анализ F=α 1 F 1 +α 2 F 2 +α 3 F 3 ρ H =Σ|x ik -x jk | Y=ax+b

Методы Data Mining Кросс - табуляция – Входные данные - таблицы частот значений переменных в выборке – Результат - таблицы частот различных сочетаний значений табулируемых переменных – Пример кросс - табуляции : Язык ФинскийРусский К-во компонент1 к-т2 к-та Σ 1 к-т2 к-та Σ Топонимы Этнонимыn 1 11 n 1 12 n 1 1* n 2 11 n 2 12 n 2 1* Антропонимы n 1 21 n 1 22 n 1 2* n 2 21 n 2 22 n 2 2* Σ n 1 *1 n 1 *2 n 1 n 2 *1 n 2 *2 n 2

Методы Data Mining Поиск логических закономерностей – Входные данные - цепочки значений переменных – Результат - логические закономерности : значимые множества : сочетания значений, регулярные эпизоды правила : ассоциативные, условия, классификации тенденции отклонения периоды – Используемые в работе методы : поиск значимых множеств и генерация правил

Поиск логических закономерностей в реляционных базах данных Исходные данные - набор кортежей, являющихся выборкой значений определенного набора атрибутов отношений реляционной базы данных. (a1=…, a2=…, …..) (a1=…, a3=…, …..) (a4=…, a5=…, …..) ………………………… Один из атрибутов данного набора - первичный ключ. Каждому значению первичного ключа в выборке соответствует некоторый объект. Кортежи с одним значением первичного ключа описывают свойства одного объекта.

Поиск логических закономерностей в реляционных базах данных Формальная модель исходных данных T={t} - исходный набор, в котором каждый объект t={ τ i } описывается как множество свойств τ i. Θ = { ω : t T : τ i t : τ i = ω } - множество всех возможных свойств, элементы которого составляют любое множество свойств e={e i Θ } Θ.

Поиск логических закономерностей в реляционных базах данных Поиск значимых множеств Для любого множества свойств e Θ определена величина - поддержка e в T. minsupport - задаваемый нижний порог поддержки. Значимым множеством называется e Θ : s(e,T)>minsupport. Алгоритмы поиска значимых множеств : Apriory - ограниченный перебор, Prefix-Span - построение дерева решений.

Поиск логических закономерностей в реляционных базах данных Генерация правил Rule={Antecedent => Consequent | c, s} - правило, где Antecedent и Consequent - подмножества Θ, - поддержка Rule в T. - степень уверенности Rule в T. Правила с задаваемыми нижними порогами поддержки и уверенности minsupport и minconf генерируются непосредствено из найденных значимых множеств.

Программная система DMiner DMiner - програмная система, представляющая собой набор инструментов для анализа реляционных баз данных. Программная система реализована на языке Java и является клиентским приложением по отношению к СУБД анализируемых баз данных. Java-приложениеDMiner JDBCDriverManager JDBC-ODBCBridge-драйверODBC-драйвер JDBC-драйвер СУБД собственный протокол доступа СУБД

Базовый состав модулей DMiner Модули для загрузки исходных данных в рабочую базу данных – Загрузка с интерактивной настройкой параметров – Загрузка на основе параметров из текстового файла Модули, реализующие процедуры выполнения алгоритмов поиска значимых множеств и генерации правил Модули, обеспечивающие доступ к результатам поиска логических закономерностей и их наглядное представление

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

Общая схема работы с DMiner Подготовка исходных данных – Настройка параметров загрузки данных Интерактивная настройка Текстовый файл – Загрузка и кодирование данных Анализ данных – Поиск значимых множеств – Генерация правил Просмотр результатов анализа

Интерактивная настройка параметров загрузки

Текстовый файл с параметрами загрузки

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

Интерфейс для доступа к результатам анализа

Анализ топонимической базы данных TORIS База данных TORIS содержит информацию по топонимам Европейского Севера России, описываемым по 25 характеристикам. Г. М. Кертом определен ряд задач, связанных с анализом этих данных. В основе анализа лежит определение частотных характеристик топонимов, выявление характерных повторяемых элементов. Подобные задачи могут быть решены с использованием методов поиска логических закономерностей. Работа по применению методов поиска логических закономерностей к анализу топонимической базы данных поддержана грантом РГНФ (N в ).

Анализ топонимической базы данных TORIS Анализируемая часть базы данных : топонимы Кемского района (397 русских топонимов ) Анализируемые свойства для топонима : объект топонима, компоненты топонима Схема работы : – загрузка информации о компонентах и объектах топонимов Кемского района – поиск значимых множеств с minsupport=0.5% – генерация ассоциативных правил с minsupport=0.5% и minconf=2% – просмотр результатов в текстовом представлении

Анализ топонимической базы данных TORIS Примеры полученных правил : –( Объект = остров )=>( Компонент = луда ) c=26.28%, s=7.81% –( Объект = остров )=>( Компонент = большой ) c=5.08%, s=1.51% –( Объект = остров )=>( Компонент = малый ) c=4.24%, s=1.26% –( Объект = остров )=>( Компонент = горелый ) c=3.4%, s=1.01% –( Объект = остров )=>( Компонент = остров ) c=3.4%, s=1.01% –( Объект = остров )=>( Компонент = березовец ) c=3.4%, s=1.01% –( Объект = остров )=>( Компонент = луды ) c=2.56%, s=0.76%

Анализ посещений Web-сайта Схема работы : Подготовка исходных данных – сканирование сайта для определения его логической структуры в терминах гиперссылок – разбор log- файла сервера с занесением в базу данных информации о переходах пользователей по гиперссылкам – выделение для каждого пользователя сессий - цепочек переходов по гиперссылкам сайта за один сеанс посещения Поиск регулярных эпизодов - значимых множеств в виде цепочек переходов Просмотр результатов в текстовом и графическом виде

Сканирование сайта

Разбор log-файла сервера

Анализ посещений Web-сайта Схема работы : Подготовка исходных данных – сканирование сайта для определения его логической структуры в терминах гиперссылок – разбор log- файла сервера с занесением в базу данных информации о переходах пользователей по гиперссылкам – выделение для каждого пользователя сессий - цепочек переходов по гиперссылкам сайта за один сеанс посещения Поиск регулярных эпизодов - значимых множеств в виде цепочек переходов Просмотр результатов в текстовом и графическом виде

Представление результатов в графическом виде

Результаты анализа посещений Исходные данные : log- файл сервера с 22 ноября 1999 г. по 27 ноября 2001 г. Количество ресурсов сайта : 267 страниц, связанных 2264 гиперссылками Количество посетителей : 1947 Количество запрошенных страниц : Количество выделенных сессий : 1234 Примеры регулярных эпизодов : –(Insects->Mammals->Ladoga ringled sea) s=0.97% –(Forest->Plants->Protected Areas->Wetlands) s=0.81% –( Насекомые -> Млекопитающие -> Ладожская нерпа ) s=0.65% –( Галерея фотографий -> Птицы восточного Приладожья -> Редкие и охраняемые виды птиц -> Ключевые орнитологические территории и охрана птиц Карелии ) s=0.57%

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