ТЕМА 2. МЕТОДЫ ИНТЕЛЛЕКТУАЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ

Вопросы:

1. Что такое интеллектуальная обработка информации (Data Mining)

2. Области использования Data Mining

3. Типы закономерностей

4. Классы систем Data Mining

2.1. Что такое интеллектуальная обработка информации (Data Mining)

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

Методов традиционной статистики оказалась явно недостаточно для качественного анализа больших объемов данных.

Главная причина – недостаточность концепции усреднения по выборке для поиска неизвестных закономерностей. Методы статистики оказались полезными главным образом для проверки заранее сформулированных гипотез и для грубого разведочного анализа, составляющего основу оперативной аналитической обработки данных (OLAP).

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

Примеры характерных различий между традиционной статистикой (OLAP) и Data Mining приведены в таблице 2.1.

Важная особенность Data Mining – нетривиальность разыскиваемых шаблонов. Это означает, что найденные шаблоны должны отражать неочевидные, неожиданные регулярности в данных, составляющие так называемые скрытые знания. Сырые данные (raw knowledge) содержат глубинный пласт знаний, при грамотной раскопке которого могут быть обнаружены неочевидные и важные закономерности.

Таблица 2.1. Характерные различия между OLAP и Data Mining

Сущность Data Mining можно определить следующими положениями:

Data Mining – это процесс обнаружения в сырых данных:

- ранее неизвестных;

- нетривиальных;

- практически полезных;

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

2.2. Области использования Data Mining

Методы Data Mining могут использоваться практически во всех областях человеческой деятельности. Однако наибольшее распространение они получили:

1) В торговле:

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

- исследование временных шаблонов и создание прогнозирующих моделей с целью оптимизации запасов.

2) В банковском деле:

- для выявления мошенничества с кредитными карточками;

- сегментации клиентов;

- прогнозирования изменений клиентуры.

3) Специальные приложения:

- медицина – для создания экспертных систем по постановке медицинских диагнозов;

- молекулярная генетика и генная инженерия: для расшифровки генома человека и наследственных заболеваний;

- прикладная химия – для анализа высокомолекулярных соединений и создания соединений с требуемыми свойствами: лекарства, парфюмерия и т.д.

2.3. Типы закономерностей

Выделяют пять стандартных типов закономерностей, которые позволяют выявлять методы Data Mining:

- ассоциацию;

- последовательность;

- классификация;

- кластеризация;

- прогнозирование.

Ассоциация имеет место в том случае, если несколько событий каким-либо образом связаны друг с другом.

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

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

Кластеризация отличается от классификации тем, что группы (правила классификации) заранее не созданы. С помощью кластеризации средства Data Mining самостоятельно выделяют различные однородные группы данных.

2.4. Классы систем Data Mining

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

Рассмотрим детальнее существующие классы систем Data Mining

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

2) Статистические пакеты – последние версии почти всех статистических пакетов включают наряду с традиционными статистическими методами также элементы Data Mining, хотя основное внимание в них все же уделяется традиционным статистическим методам.

Недостатком систем такого класса считают ограниченный набор возможностей в области Data Mining, а также требования к специальной подготовке пользователя.

3) Нейронные сети – это большой класс систем, архитектура которых имеет аналогию с построением нервной ткани из нейронов. Наиболее распространены структуры, содержащие несколько слоев искусственных нейронов. На нейроны первого слоя подается входная информация (сигнал), а затем происходит послойная обработка информации. Выходной сигнал рассматривается как ответ. За счет подбора коэффициентов связей между нейронами различных уровней можно добиться того, чтобы при определенном классе входных сигналов получался заданный класс выходных. При такой постановке вопроса самым важным этапом является «тренировка» или обучение нейросети.

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

4) Системы рассуждений на основе аналогичных случаев (case based reasoning – CBR). В этих системах для того, чтобы сделать прогноз на будущее, или выбрать правильное решение, находят в прошлом близкие аналоги данной ситуации и выбирают тот ответ, который был для них правилен. Поэтому этот метод называют еще методом ближайшего соседа.

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

Недостатки таких систем следующие:

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

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

5) Деревья решений (decision trees). В этом случае создается иерархическая структура решающих правил типа «если – то», имеющая вид дерева. Для принятия решения, к какому классу отнести некоторый объект или ситуацию, требуется ответить на вопросы, стоящие в узлах (точках ветвления) этого дерева, начиная с его корня (широкой части).

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

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

Другое направление эволюционного программирования связано с поиском зависимости целевых переменных от остальных в виде функций какого-то определенного вида. В одном из наиболее удачных алгоритмов этого типа – методе группового учета аргументов (МГУА)- зависимость ищут в форме полинома.

7) Генетические алгоритмы. Data Mining – не основная область их использования. Их можно рассматривать скорее как мощное средство решения комбинаторных задач и задач оптимизации. Тем не менее генетические алгоритмы вошли в стандартный набор методов Data Mining, почему и рассматриваются здесь.

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

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

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

Наиболее известным представителем этого класса продуктов является программа WizWhy фирмы Wizsoft. В настоящее время этот продукт является одним из лидеров в области Data Mining и демонстрирует более высокие результаты при решении практических задач по сравнению с остальными методами Data Mining.

Литература к теме:

1. Дюк В., Самойленко А. Data Mining: учебный курс – СПб.: Питер – 2011. 368 с.

2. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем – СПб.: Питер – 2010. – 384 с.

3. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации – М.: Нолидж – 2011. – 352 с.

ТЕМА 3. ОБРАБОТКА И ПОИСК ТЕКСТОВОЙ

ИНФОРМАЦИИ

Вопросы:

1. Назначение и основные понятия

2. Общая функциональная структура ДИПС

3. Формальное представление смыслового содержания текста

4.Обработка входящей текстовой информации

5.Поиск текстовой информации

6.Оценка качества ДИПС

3.1. Назначение и основные понятия

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

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

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

Такие системы поиска текстовых знаний получили название документальных информационно-поисковых систем (ДИПС).

Основной функцией любой ДИПС является информационное обеспечение потребителей путем информационного поиска и последующей выдачи ответов на их вопросы.

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

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

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

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

В процессе проведения информационного поиска в ДИПС определяется степень соответствия содержания документов и запроса пользователя путем сопоставления поискового предписания и поисковых образов. А на основе такого сопоставления принимается решение о выдаче документа (он признается релевантным) или его невыдаче (он считается нерелевантным).

Решение о выдаче или невыдаче документа в ответ н запрос принимается на основании некоторого набора правил, по которому данной ДИПС определяется степень смысловой близости между поисковым предписанием и поисковым образом. Такой набор правил получил название критерия смыслового соответствия.

3.2. Общая функциональная структура ДИПС

В состав типичной ДИПС входят, как правило, четыре основных подсистемы:

- Подсистема ввода и регистрации;

- Подсистема обработки;

- Подсистема хранения;

- Подсистема поиска.

Подсистема ввода и регистрации решает следующие основные задачи:

- создание электронных копий бумажных документов, включая распознавание текста или ввод с клавиатуры;

- подключение к каналам доставки электронных документов;

- преобразование при необходимости формата электронного документа;

- присвоение электронным документам уникальных идентификаторов (имен).

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

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

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

3.3. Формальное представление смыслового содержания текста

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

- многообразием и неформализуемостью средств передачи смысла:((контекст, ссылки, текстуальные отношения между словами и др.);

- семантическая неоднозначность, связанная с наличием синонимов и различной трактовки одних и тех же слов;

- многозначность;

- эллипсность (возвраты и пропуски слов)..

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

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

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

ИПЯ принято разбивать на два основных класса:

- классификационные языки;

- дескрипторные языки.

Особенностью классификационных языков является то, что заранее, группой экспертов, отбираются понятия ИПЯ в виде слов естественного языка или сочетаний слов. В этом случае построение сложных языковых конструкций заменяется выбором из набора простых и сложных понятий. Происходит своего рода классификация терминов и выражений входящего сообщения, с чем и связано название этого типа искусственных языков. Примером такого класса языков является рубрикатор (напр. УДК), состоящий из рубрик и многоуровневых вложенных подрубрик.

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