Введение в Data Mining

Автоматическое приобретение знаний из БД
Автоматическое приобретение знаний из баз данных – это методы и технологии выявления компьютером скрытых правил и закономерностей в больших наборах данных.
Синонимы: Data Mining («добыча» или «раскопка» данных), Knowledge Discovery in Databases (обнаружение знаний в базах данных), интеллектуальный анализ данных.

Актуальность автомати-ческого приобретения знаний
В 2002 году, согласно оценке профессо-ров из ун-та Berkeley, объём информации в мире увеличился на 5•1018 = 5 000 000 000 000 000 000 байт!
Согласно другим оценкам, информация удваивается каждые 2 – 3 года.
В 1989 году большая БД – это БД объёмом 1 мегабайт.
В 2003 году большая БД – это БД объёмом 1 петабайт (примерно в миллион раз больше).

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

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

Области применения авто-матич. приобретения знаний
Другие приложения в бизнесе
сегментация рынка;
развитие автомобильной промышленности;
поощрение часто летающих клиентов.
Медицина
автоматизация создания баз знаний медицинских ЭС (вместо врачей-экспертов – медицинская база данных).

Типы закономерностей, извлекаемых из БД
Ассоциация;
Классификация;
Кластеризация;
Прогнозирование.

Методы автоматического приобретения знаний
Статистические методы
Нейронные сети
Рассуждения на основе аналогич-ных случаев
Деревья решений
Генетические алгоритмы

Статистические методы
Корреляционный, регрессионный, факторный анализ и др.
Преимущества: классические методы с развитым математическим аппаратом.
Недостатки:
− требуют спец. подготовки пользователя;
− усреднённые характеристики выборки, используемые в статистической парадигме, при исследовании сложных феноменов предметной области часто оказываются фиктивными величинами.
Инструментальные системы: SAS (SAS, США), STATISTICA (StatSoft, США), SPSS Statistics (SPSS, США).

Нейронные сети
Моделируют структуру нервной системы (множество параллельно работающих простых элементов – нейронов – объединённых взвешенными связями).
Преимущества:
– аппроксимация сложных нелинейных зависимостей;
– адаптивность;
– эффективная аппаратная реализуемость.
Недостатки:
– большой объём обучающей выборки;
– плохая интерпретируемость обученной нейронной сети человеком.
Инструментальные системы: BrainMaker (CSS), NeuroShell (Ward Systems Group), OWL (HyperLogic).

Рассуждения на основе аналогичных случаев
Синонимы: Case Based Reasoning, рассуждения по прецедентам, метод ближайшего соседа. Идея: для выбора правильного решения в базе находятся близкие аналоги наличной ситуации и выбирает-ся ответ, который был правильным для них.
Преимущества: простота реализации и наглядность результатов анализа.
Недостатки:
− не строятся модели или правила, обобща-ющие предыдущий опыт;
− сложность выбора адекватной меры близости прецедентов.
Инструментальные системы: KATE tools (Acknosoft, Франция), Pattern Recognition Workbench (Unica, США).

Деревья решений
Деревья решений (Decision Trees) – один из самых популярных методов автоматического извлечения знаний. Они создают иерархическую структуру классифицирующих правил типа «ЕСЛИ... ТО...», имеющую вид дерева.
Преимущества: наглядность и понятность.
Недостатки:
− проблема значимости;
− проблема независимости признаков.
Инструментальные системы: See5/С5.0 (RuleQuest, Австралия), Clementine (Integral
Solutions, Великобритания), SIPINA (University of Lyon, Франция), IDIS (Information Discovery, США).

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

Генетические алгоритмы (окончание)
Преимущества:
− пригодность для поиска в сложном пространстве решений большой размерности;
− эффективная аппаратная реализация.
Недостатки:
− функции приспособленности и процедуры генетического алгоритма являются эвристическими;
− как и в реальной жизни, эволюцию может «заклинить» на непродуктивной ветви.
Инструментальные системы: GeneHunter (Ward Systems Group).

Алгоритм индуцирования знаний из БД
Алгоритм генерирует продукционные правила.
В алгоритме используется представле-ние знаний в виде деревьев решений.
Рассмотрим пример.
Пусть необходимо построить базу
знаний для получения ответа: «Как поступить, чтобы при-быль росла?».

Исходная база данных, из которой извлекаются знания
Окончание на следующем слайде…

Исходная база данных, из которой извлекаются знания (окончание)

Искомый атрибут «Прибыль» бу-дем называть атрибутом класса.
Для построения дерева решений нужно взять один из атрибутов таб-лицы в качестве основного (корне-вого) атрибута. Пусть это будет «Возраст».
Преобразуем исходную таблицу к следующему виду:

Из таблицы видно, что при значе-нии атрибута «Возраст», равном «новый», прибыль всегда растёт, а при значении «старый» – падает.
В случае же значения «средний» такого определённого вывода сделать нельзя.
Поэтому продолжим разбивку таб-лицы по атрибуту «Конкуренция».

Получим другую таблицу:

Поскольку теперь для атрибута класса наше дерево решений выво-дит однозначный ответ, то дерево решений построено.
Порождаем правила:
1. ЕСЛИ Возраст = новый
ТО Прибыль = растёт
2. ЕСЛИ Возраст = старый
ТО Прибыль = падает