Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Алгоритмы ограниченного перебора



Алгоритмы ограниченного перебора были предложены в середине 60-х годов М.М. Бонгардом для поиска логических закономерностей в данных. С тех пор они продемонстрировали свою эффективность при решении множества задач из самых различных областей.

Эти алгоритмы вычисляют частоты комбинаций простых логических событий в подгруппах данных. Примеры простых логических событий: X = a; X < a; X > a; a < X < b и др., где X — какой либо параметр, “a” и “b” — константы. Ограничением служит длина комбинации простых логических событий (у М. Бонгарда она была равна 3). На основании анализа вычисленных частот делается заключение о полезности той или иной комбинации для установления ассоциации в данных, для классификации, прогнозирования и пр.

Наиболее ярким современным представителем этого подхода является система WizWhy предприятия WizSoft. Хотя автор системы Абрахам Мейдан не раскрывает специфику алгоритма, положенного в основу работы WizWhy, по результатам тщательного тестирования системы были сделаны выводы о наличии здесь ограниченного перебора (изучались результаты, зависимости времени их получения от числа анализируемых параметров и др.).

Рисунок 7. Система WizWhy обнаружила правила, объясняющие низкую урожайность некоторых сельскохозяйственных участков

Автор WizWhy утверждает, что его система обнаруживает ВСЕ логические if-then правила в данных. На самом деле это, конечно, не так. Во-первых, максимальная длина комбинации в if-then правиле в системе WizWhy равна 6, и, во-вторых, с самого начала работы алгоритма производится эвристический поиск простых логических событий, на которых потом строится весь дальнейший анализ. Поняв эти особенности WizWhy, нетрудно было предложить простейшую тестовую задачу, которую система не смогла вообще решить. Другой момент — система выдает решение за приемлемое время только для сравнительно небольшой размерности данных.

Тем не менее, система WizWhy является на сегодняшний день одним из лидеров на рынке продуктов Data Mining. Это не лишено оснований. Система постоянно демонстрирует более высокие показатели при решении практических задач, чем все остальные алгоритмы. Стоимость системы около $ 4000, количество продаж — 30000.

Системы для визуализации многомерных данных

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

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

Рисунок 8. Визуализация данных системой DataMiner 3D

Резюме

1. Рынок систем Data Mining экспоненциально развивается. В этом развитии принимают участие практически все крупнейшие корпорации (см. например http: //www.kdnuggets.com). В частности, Microsoft непосредственно руководит большим сектором данного рынка (издает специальный журнал, проводит конференции, разрабатывает собственные продукты).

2. Системы Data Mining применяются по двум основным направлениям: 1) как массовый продукт для бизнес-приложений; 2) как инструменты для проведения уникальных исследований (генетика, химия, медицина и пр.). В настоящее время стоимость массового продукта от $1000 до $10000. Количество инсталляций массовых продуктов, судя по имеющимся сведениям, сегодня достигает десятков тысяч. Лидеры Data Mining связывают будущее этих систем с использованием их в качестве интеллектуальных приложений, встроенных в корпоративные хранилища данных.

3. Несмотря на обилие методов Data Mining, приоритет постепенно все более смещается в сторону логических алгоритмов поиска в данных if-then правил. С их помощью решаются задачи прогнозирования, классификации, распознавания образов, сегментации БД, извлечения из данных “скрытых” знаний, интерпретации данных, установления ассоциаций в БД и др. Результаты таких алгоритмов эффективны и легко интерпретируются.

4. Вместе с тем, главной проблемой логических методов обнаружения закономерностей является проблема перебора вариантов за приемлемое время. Известные методы либо искусственно ограничивают такой перебор (алгоритмы КОРА, WizWhy), либо строят деревья решений (алгоритмы CART, CHAID, ID3, See5, Sipina и др.), имеющих принципиальные ограничения эффективности поиска if-then правил. Другие проблемы связаны с тем, что известные методы поиска логических правил не поддерживают функцию обобщения найденных правил и функцию поиска оптимальной композиции таких правил. Удачное решение указанных проблем может составить предмет новых конкурентоспособных разработок.

В заключение отметим очередное симптоматичное событие. Компания Microsoft официально объявила об усилении своей активности в области Data Mining. Специальная исследовательская группа Microsoft, возглавляемая Усамой Файядом, и пять приглашенных партнеров (Angoss, Datasage, E.piphany, SAS, Silicon Graphics, SPSS) готовят совместный проект по разработке стандарта обмена данными и средств для интеграции инструментов Data Mining с базами и хранилищами данных.

В дополнение к приведенному краткому обзору по теме Data Mining для заинтересовавшихся читателей сообщаю, что более подробные сведения можно будет почерпнуть из моей новой книги “Искусственный интеллект: извлечение скрытых знаний”.

Литература

1. Айвазян С. А., Бухштабер В. М., Юнюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989.

2. Knowledge Discovery Through Data Mining: What Is Knowledge Discovery? — Tandem Computers Inc., 1996.

3. Кречетов Н.. Продукты для интеллектуального анализа данных. — Рынок программных средств, № 14–15, 1997, c. 32–39.

4. Boulding K. E. General Systems Theory — The Skeleton of Science//Management Science, 2, 1956.

5. Гик Дж., ван. Прикладная общая теория систем. — М.: Мир, 1981.

6. Киселев М., Соломатин Е.. Средства добычи знаний в бизнесе и финансах. — Открытые системы, № 4, 1997, с. 41–44.

7. Дюк В.А. Обработка данных на ПК в примерах. — СПб: Питер, 1997.

В.А. Дюк, Санкт-Петербургский институт информатики и автоматизации РАН

 

nowledge Discovery in Databases (KDD) – это процесс поиска полезных знаний в " сырых" данных. KDD включает в себя вопросы: подготовки данных, выбора информативных признаков, очистки данных, применения методов Data Mining (DM), постобработки данных и интерпретации полученных результатов. Безусловно, " сердцем" всего этого процесса являются методы DM, позволяющие обнаруживать знания.

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

Процесс Knowledge Discovery in Databases, состоит из следующих шагов:

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

2. Предобработка данных. Для того чтобы эффективно применять методы Data Mining, следует обратить внимание на вопросы предобработки данных. Данные могут содержать пропуски, шумы, аномальные значения и т.д. Кроме того, данные могут быть избыточны, недостаточны и т.д. В некоторых задачах требуется дополнить данные некоторой априорной информацией. Наивно предполагать, что если подать данные на вход системы в существующем виде, то на выходе получим полезные знания. Данные должны быть качественны и корректны с точки зрения используемого метода DM. Поэтому первый этап KDD заключается в предобработке данных. Более того, иногда размерность исходного пространства может быть очень большой, и тогда желательно применять специальные алгоритмы понижения размерности. Это как отбор значимых признаков, так и отображение данных в пространство меньшей размерности.

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

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

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

Knowledge Discovery in Databases не задает набор методов обработки или пригодные для анализа алгоритмы, он определяет последовательность действий, которую необходимо выполнить для того, чтобы из исходных данных получить знания. Данный подход универсальный и не зависит от предметной области, что является его несомненным достоинством.

Deductor – полнофункциональная платформа для решения задач Knowledge Discovery in Databases, позволяющая провести все вышеописанные шаги.

1. Подготовка исходного набора данных. В состав системы входит Deductor Warehouse – многомерное хранилище данных, ориентированное на решение задач консолидации информации из разнородных источников и быстрого извлечения интересующего набора данных. Deductor Warehouse поддерживает богатый семантический слой, позволяющий конечному пользователю оперировать бизнес терминами для получения интересующих данных. Кроме собственного хранилища Deductor поддерживает работу и с другими источниками: Oracle, DB2, MS SQL, Informix, Sybase, Interbase, DBase, FoxPro, Paradox, MS Access, CSV (текстовые файлы с разделителями), ODBC, ADO. Для обеспечения максимального быстродействия Deductor поддерживает прямой (direct) доступ к большинству наиболее популярных баз данных.

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

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

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

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

Deductor удовлетворяет всем требованиям для успешного взаимодействия с экспертом (аналитиком):

· Единая платформа, в которой можно пройти все этапы Knowledge Discovery in Databases;

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

· Возможность произвольного комбинирования любых методов обработки;

· Большой набор методов визуализации полученных результатов;

· Пакетное выполнение всей действий по обработке данных.

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

 

 


Поделиться:



Последнее изменение этой страницы: 2019-05-17; Просмотров: 556; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.02 с.)
Главная | Случайная страница | Обратная связь