Data Mining (добыча знаний)

Появление и широкое использование хранилищ данных способствовало развитию такого направления их обработки, как Data Mining (переводится как «добыча» или «раскопка данных»). Нередко наряду с Data Mining встречаются слова «обнаружение знаний в базах данных» (knowledge discovery in databases) и «интеллектуальный анализ данных». Их можно считать синонимами Data Mining.

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

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

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

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

Примеры заданий на такой поиск при использовании Data Mining могут быть следующими:

§ Имеются ли характерные портреты клиентов, которые, по всей вероятности, собираются отказаться от услуг телефонной компании?

§ Существуют ли стереотипные схемы покупок для случаев мошенничества с кредитными карточками?

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

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

Уровни данных, извлекаемые из данных, показаны на рисунке 1.3.

Рис. 1.3.

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

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

Можно привести примеры некоторых возможных бизнес-приложения Data Mining.

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

· Анализ покупательской корзины (анализ сходства) предназначен для выявления товаров, которые покупатели стремятся приобретать вместе. Знание покупательской корзины необходимо для улучшения рекламы, выработки стратегии создания запасов товаров и способов их раскладки в торговых залах.

· Исследование временных шаблонов помогает торговым предприятиям прини­мать решения о создании товарных запасов. Оно дает ответы на вопросы типа: «Если сегодня покупатель приобрел видеокамеру, то через какое время он ве­роятнее всего купит новые батарейки и пленку?».

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

Достижения технологии Data Mining используются в банковском деле для реше­ния следующих распространенных задач:

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

· Сегментация клиентов. Разбивая клиентов на различные категории, банки де­лают свою маркетинговую политику более целенаправленной и результатив­ной, предлагая различные виды услуг разным группам клиентов.

· Прогнозирование изменений клиентуры. Data Mining помогает банкам строить прогнозные модели ценности своих клиентов и соответствующим образом обслуживать каждую категорию.

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

· Анализ записей о подробных характеристиках вызовов. Назначение такого ана­лиза — выявление категорий клиентов с похожими стереотипами пользования их услугами и разработка привлекательных наборов цен и услуг.

· Выявление лояльности клиентов. Data Mining можно использовать для опре­деления характеристик клиентов, которые, один раз воспользовавшись услу­гами данной компании, с большой долей вероятности останутся ей верными. В итоге средства, выделяемые на маркетинг, можно тратить там, где отдача больше всего.

Страховые компании в течение ряда лет накапливают большие объемы данных. Здесь обширное поле деятельности для методов Data Mining:

· Выявление мошенничества. Страховые компании могут снизить уровень мошенничества, отыскивая определенные стереотипы в заявлениях о выплате cтрахового возмещения, характеризующих взаимоотношения между юристами, врачами и заявителями.

· Анализ риска. Путем выявления сочетаний факторов, связанных с оплаченными заявлениями, страховщики могут уменьшить свои потери по обязательствам. Известен случай, когда в США крупная страховая компания обнаружила, что суммы, выплаченные по заявлениям людей, состоящих в браке, вдвое превышают суммы по заявлениям одиноких людей. Компания отреагировала на это новое знание пересмотром своей общей политики предоставления скидок семейным клиентам.

В литературе по Data Mining можно найти много других примеров для различных сфер деятельности.

Типы выявляемых закономерностей и классы систем Data Mining.

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

· ассоциация

· последовательность

· классификация

· кластеризация

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

Ассоциация имеет место в том случае, если несколько событий связаны друг с другом. Например, исследование, проведенное в супермаркете, может показать, что 65 % купивших кукурузные чипсы берут также и «кока-колу», а при наличии скидки за такой комплект «колу» приобретают в 85 % случаев. Располагая сведениями о подобной ассоциации, менеджерам легко оценить, насколько действенна предо­ставляемая скидка.

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

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

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

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

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

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

Статистические пакеты. Последние версии почти всех известных статистических пакетов включают наря­ду с традиционными статистическими методами также элементы Data Mining. Но основное внимание в них уделяется все же классическим методикам — корреля­ционному, регрессионному, факторному анализу и др.

Недостатком систем этого класса считают требование к специальной подготовке пользователя. Также отмечают, что мощные современные статистические пакеты являются слишком «тяжеловесными» для массового применения в финансах и биз­несе. К тому же часто эти системы весьма дороги — от $1000 до $15 000.

В качестве примеров наиболее мощных и распространенных статистических па­кетов можно назвать SAS (компания SAS Institute), SPSS (SPSS), STATGRAPICS (Manugistics), STATISTICA, STADIA и др.

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

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

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

Примеры нейросетевых систем — BrainMaker (CSS), NeuroShell (Ward Systems Group), OWL (HyperLogic). Стоимость их довольно значительна: $1500-8000.

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

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

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

Примеры систем, использующих CBR, — КАТЕ tools (Acknosoft, Франция), Рattern Recognition Workbench (Unica, США).

Деревья решений. Деревья решения (decision trees) являются одним из наиболее популярных подходов к решению задач Data Mining. Они создают иерархическую структуру классифицирующих правил типа «ЕСЛИ... ТО...» (if-then), имеющую вид дерева. Для принятия решения, к какому классу отнести некоторый объект или ситуацию, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная с его корня. Вопросы имеют вид «значение параметра А больше х?». Если ответ положительный, осуществляется переход к правому узлу следующего уровня, если отрицательный — к левому узлу; затем снова следует вопрос, связанный с соответ­ствующим узлом.

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

Вместе с тем, большинство систем используют именно этот метод. Самыми изве­стными являются See5/C5.0 (RuleQuest, Австралия), Clementine (Integral Solutions, Великобритания), SIPINA (University ofLyon, Франция), IDIS (Information Discovery, США), KnowledgeSEEKER (ANGOSS, Канада). Широко используются при анализе банковской информации. Стоимость этих систем варьи­руется от $1 до $10 тыс.

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

Другое направление эволюционного программирования связано с поиском зависимости целевых переменных от остальных в форме функций какого-то опреде­ленного вида. Например, в одном из наиболее удачных алгоритмов этого типа - методе группового учета аргументов (МГУА) — зависимость ищут в форме полиномов. В настоящее время из продающихся в России систем метод МГУА реализован в системе NeuroShell компании Ward Systems Group.

Стоимость систем до $5000.

Генетические алгоритмы. Генетические алгоритмы вошли сейчас в стандартный инструментарий методов Data Mining.

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

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

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

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

Генетические алгоритмы имеют ряд недостатков. Критерий отбора хромосом и используемые процедуры являются эвристическими и совсем не гарантируют нахождение «лучшего» решения. Как и в реальной жизни, эволюцию может «зак­линить» на какой-либо непродуктивной ветви. И, наоборот, можно привести примеры, как два неперспективных родителя, которые будут исключены из эволюции гене­тическим алгоритмом, оказываются способными произвести высокоэффективно­го потомка. Это становится особенно заметно при решении высокоразмерных задач со сложными внутренними связями.

Примером может служить система GeneHunter фирмы Ward Systems Group (стоимость — около $1000).

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

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

Наиболее ярким современным представителем этого подхода является система WizWhy предприятия WizSoft.

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

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

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

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

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

Системы Data Mining применяются по двум основным направлениям:

· Как массовый продукт для бизнес-приложений.

· Как инструменты для проведения уникальных исследований (генетика, хи­мия, медицина. финансы и пр.).

В настоящее время стоимость массового продукта от $ 1000 до $10 000. Количество инсталляций массовых продуктов, судя по име­ющимся сведениям, сегодня достигает десятков тысяч. Лидеры Data Mining связывают будущее этих систем с использованием их в качестве интеллек­туальных приложений, встроенных в корпоративные хранилища данных.

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

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

Дата добавления: 2014-01-05