Основы технологии Data Mining
Что такое Data Mining
Корпоративная база данных любого современного предприятия обычно содержит набор таблиц, хранящих записи о тех или иных фактах либо объектах (например, о товарах, их продажах, клиентах, счетах). Как правило, каждая запись в подобной таблице описывает какой-то конкретный объект или факт. Например, запись в таблице продаж отражает тот факт, что такой-то товар продан такому-то клиенту тогда-то таким-то менеджером, и по большому счету ничего, кроме этих сведений, не содержит. Однако совокупность большого количества таких записей, накопленных за несколько лет, может стать источником дополнительной, гораздо более ценной информации, которую нельзя получить на основе одной конкретной записи, а именно — сведений о закономерностях, тенденциях или взаимозависимостях между какими-либо данными.
Подобного рода информация обычно используется при прогнозировании, стратегическом планировании, анализе рисков, и ценность ее для предприятия очень высока. Видимо, поэтому процесс ее поиска и получил название Data Mining (mining по-английски означает «добыча полезных ископаемых», а поиск закономерностей в огромном наборе фактических данных действительно сродни этому). Термин Data Mining обозначает не столько конкретную технологию, сколько сам процесс поиска корреляций, тенденций, взаимосвязей и закономерностей посредством различных математических и статистических алгоритмов: кластеризации, создания субвыборок, регрессионного и корреляционного анализа. Цель этого поиска — представить данные в виде, четко отражающем бизнес-процессы, а также построить модель, при помощи которой можно прогнозировать процессы, критичные для планирования бизнеса (например, динамику спроса на те или иные товары или услуги либо зависимость их приобретения от каких-то характеристик потребителя).
В основу современной технологии Data Mining положена концепция шаблонов, отражающих закономерности, свойственные подвыборкам данных. Поиск шаблонов производится методами, не использующими никаких априорных предположений об этих подвыборках. Если при статистическом анализе или при применении OLAP обычно формулируются вопросы типа «Каково среднее число неоплаченных счетов заказчиками данной услуги?», то применение Data Mining, как правило, то подразумевает ответы на вопросы типа «Существует ли типичная категория клиентов, не оплачивающих счета?». При этом именно ответ на второй вопрос нередко обеспечивает более нетривиальный подход к маркетинговой политике и к организации работы с клиентами.
Важной особенностью Data Mining является нестандартность и неочевидность разыскиваемых шаблонов. Иными словами, средства Data Mining отличаются от инструментов статистической обработки данных и средств OLAP тем, что вместо проверки заранее предполагаемых пользователями взаимозависимостей они на основании имеющихся данных способны находить такие взаимозависимости самостоятельно и строить гипотезы об их характере.
Следует отметить, что применение средств Data Mining не исключает использования статистических инструментов и OLAP-средств, поскольку результаты обработки данных с помощью последних, как правило, способствуют лучшему пониманию характера закономерностей, которые следует искать.
Типы закономерностей, выявляемых методами Data Mining
Cогласно В.А.Дюку , выделяют пять стандартных типов закономерностей, выявляемых методами Data Mining:
ассоциация — высокая вероятность связи событий друг с другом (например, один товар часто приобретается вместе с другим);
последовательность — высокая вероятность цепочки связанных во времени событий (например, в течение определенного срока после приобретения одного товара будет с высокой степенью вероятности приобретен другой);
классификация — имеются признаки, характеризующие группу, к которой принадлежит то или иное событие или объект (обычно при этом на основании анализа уже классифицированных событий формулируются некие правила);
кластеризация — закономерность, сходная с классификацией и отличающаяся от нее тем, что сами группы при этом не заданы — они выявляются автоматически в процессе обработки данных;
временные закономерности — наличие шаблонов в динамике поведения тех или иных данных (типичный пример — сезонные колебания спроса на те или иные товары либо услуги), используемых для прогнозирования.
Методы исследования данных в Data Mining
C егодня существует довольно большое количество разнообразных методов исследования данных. Основываясь на вышеуказанной классификации, предложенной В.А.Дюком, среди них можно выделить:
регрессионный, дисперсионный и корреляционный анализ (реализован в большинстве современных статистических пакетов, в частности в продуктах компаний SAS Institute, StatSoft и др.);
методы анализа в конкретной предметной области, базирующиеся на эмпирических моделях (часто применяются, например, в недорогих средствах финансового анализа);
нейросетевые алгоритмы, идея которых основана на аналогии с функционированием нервной ткани и заключается в том, что исходные параметры рассматриваются как сигналы, преобразующиеся в соответствии с имеющимися связями между «нейронами», а в качестве ответа, являющегося результатом анализа, рассматривается отклик всей сети на исходные данные. Связи в этом случае создаются с помощью так называемого обучения сети посредством выборки большого объема, содержащей как исходные данные, так и правильные ответы;
алгоритмы — выбор близкого аналога исходных данных из уже имеющихся исторических данных. Называются также методом «ближайшего соседа»;
деревья решений — иерархическая структура, базирующаяся на наборе вопросов, подразумевающих ответ «Да» или «Нет»; несмотря на то, что данный способ обработки данных далеко не всегда идеально находит существующие закономерности, он довольно часто используется в системах прогнозирования в силу наглядности получаемого ответа;
кластерные модели (иногда также называемые моделями сегментации) применяются для объединения сходных событий в группы на основании сходных значений нескольких полей в наборе данных; также весьма популярны при создании систем прогнозирования;
алгоритмы ограниченного перебора, вычисляющие частоты комбинаций простых логических событий в подгруппах данных;
эволюционное программирование — поиск и генерация алгоритма, выражающего взаимозависимость данных, на основании изначально заданного алгоритма, модифицируемого в процессе поиска; иногда поиск взаимозависимостей осуществляется среди каких-либо определенных видов функций (например, полиномов).
Ведущие производители средств Data Mining
К современным средствам Business Intelligence относятся генераторы отчетов, средства аналитической обработки данных, средства разработки BI-решений (BI Platforms) и так называемые Enterprise BI Suites — средства анализа и обработки данных масштаба предприятия, которые позволяют осуществлять комплекс действий, связанных с анализом данных и с созданием отчетов, и нередко включают интегрированный набор BI-инструментов и средства разработки BI-приложений. Последние, как правило, содержат в своем составе и средства построения отчетов, и OLAP-средства, а нередко — и Data Mining-средства.
По данным аналитиков Gartner Group, лидерами на рынке средств анализа и обработки данных масштаба предприятия являются компании Business Objects, Cognos, Information Builders, а претендуют на лидерство также Microsoft и Oracle (рис. 1). Что касается средств разработки BI-решений, то основными претендентами на лидерство в этой области являются компании Microsoft и SAS Institute (рис. 2).
Рис. 1. Enterprise BI Suites Magic Quadrant
Рис. 2. BI Platform Magic Quadrant
Отметим, что средства Business Intelligence компании Microsoft относятся к сравнительно недорогим продуктам, доступным широкому кругу компаний. Именно поэтому мы и собираемся рассмотреть некоторые практические аспекты применения Data Mining на примере продуктов этой компании в последующих частях данной статьи.
Средства Data Mining корпорации Microsoft
Средства Data Mining, входящие в комплект поставки Microsoft SQL Server 2000, содержат реализацию двух популярных алгоритмов:
Microsoft Decision Trees — алгоритм построения так называемых деревьев решений, основанных на создании иерархической структуры, которая базируется на ответе «Да» или «Нет» на набор вопросов;
Microsoft Clustering — алгоритм, основанный на объединении сходных событий в группы на базе сходных значений нескольких полей в наборе данных.
Кроме того, средства Data Mining компании Microsoft позволяют подключать библиотеки независимых производителей, реализующие другие алгоритмы поиска закономерностей. Согласно сведениям, полученным от менеджеров Microsoft, ответственных за данную линейку продуктов, следующая версия Microsoft SQL Server под кодовым названием Yukon будет содержать еще более внушительный набор алгоритмов.
Что такое кластеризация
Людям свойственно классифицировать и группировать все объекты и явления, с которыми они сталкиваются, и на основе отнесения объекта к той или иной группе пытаться предсказывать его поведение. Например, мы оцениваем опасность, исходящую от пробегающей мимо собаки, по ее размеру, принадлежности к той или иной породе, наличию у нее ошейника и присутствию рядом хозяина, бессознательно относя ее к определенной группе собак, типичное поведение которых считается более или менее известным.
В качестве еще одного примера групп (или кластеров) можно привести возрастной состав участников демонстрации против введения повременной оплаты за телефонные разговоры, состоявшейся в одном из крупных российских городов несколько лет назад. Эта демонстрация состояла в основном из молодых людей преимущественно мужского пола (пользователей Интернета) и очень пожилых людей преимущественно женского пола (одиноких пенсионерок, для которых телефон — практически единственное средство общения с друзьями). При этом в демонстрации практически не участвовали ни люди среднего возраста, ни дети. Схематически состав этих групп можно изобразить так, как это представлено на рис. 1.
рис. 1
Иными словами, можно сказать, что типичный участник данной демонстрации принадлежит с высокой долей вероятности к одной из двух указанных групп и что вероятность участия в ней человека среднего возраста невелика. Впрочем, данный пример крайне прост (наблюдаемых параметров в нем всего два — возраст и пол), равно как и логическое объяснение полученных данных. В более сложных случаях закономерности, по которым группируются объекты или события, не столь очевидны, особенно если число параметров велико.
Обычно алгоритмы кластеризации используются в тех случаях, когда нет абсолютно никаких предположений о характере взаимосвязи между данными, а результаты их применения нередко являются исходными данными для других алгоритмов, например для построения деревьев решений.
Как же работают подобные алгоритмы? Обычно они осуществляют итеративный поиск групп данных на основании заранее заданного числа кластеров. Изначально центры будущих кластеров представляют собой случайным образом выбранные точки в n-мерном пространстве возможных значений (где n — число параметров). Затем все исходные данные перебираются и в зависимости от значений параметров помещаются в тот или иной кластер, при этом постоянно происходит поиск точек, сумма расстояний которых до остальных точек в данном кластере является минимальной. Эти точки становятся центрами новых кластеров, и процедура повторяется до тех пор, пока центры и границы новых кластеров не перестанут перемещаться.
Отметим, что данный алгоритм далеко не всегда приводит к результату, поддающемуся логическому объяснению, — он просто позволяет определить различные группы объектов или событий. Кроме того, не всегда можно с первого раза точно угадать число кластеров, отражающее реально существующее число групп.
Постановка задачи
В качестве примера применения кластеризации рассмотрим принцип действия антиспамового фильтра, назначение которого — принять решение о том, является ли данное письмо несанкционированно рассылаемой рекламной информацией. Действие подобного фильтра может базироваться на разных алгоритмах, но, как правило, состоит из двух процессов: настройки фильтра (которая выполняется либо однократно, либо периодически, но не часто) и принятия решения о том, относится ли спама конкретное письмо к категории (что происходит намного чаще, чем настройка фильтра).
Один из возможных алгоритмов настройки антиспамового фильтра выглядит следующим образом. Берется большое количество писем, о которых точно известно, принадлежат ли они к несанкционированно рассылаемой рекламе. Далее для каждого письма вычисляется частотность встречающихся в нем определенных, заранее заданных слов, словосочетаний или символов. Сведения об этом наборе служат исходными данными для процесса создания кластеров согласно описанному выше алгоритму (этот процесс в некоторых источниках называется model training — тренировка модели). Принятие решения о принадлежности конкретного письма к категории спама осуществляется на основании того, в какой кластер попадет данное письмо. Заметим, что алгоритм действия коммерческих антиспамовых фильтров может быть сложнее — данная статья отнюдь не претендует на детальный разбор принципов их работы.
В качестве примера исходных данных воспользуемся набором сведений о более чем 4 тыс. писем, изученных сотрудниками компании Hewlett-Packard в 1999 году. Этот набор данных, доступный в виде файла в формате CSV по адресу www.ics.uci.edu/~mlearn/MLRepository.html (на указанном сайте находится довольно много интересных баз данных, которые разрешено свободно применять в научных целях), содержит одну таблицу, в которой имеется колонка IsSpam с целочисленными значениями (1 — письмо является спамом, 0 — письмо не является таковым), а также большое количество колонок с частотностью различных английских слов. Для упрощения работы с этим набором данных импортируем его в какую-нибудь СУБД, например в Access или Microsoft SQL Server. Имеет также смысл создать автоматически заполняемое целочисленное ключевое поле, которое потребуется при создании модели Data Mining на основе этих данных (рис. 2).
рис. 2
Итак, можно приступить к созданию кластеров.
Создание кластеров
ля создания кластеров следует запустить инструмент администрирования аналитических служб Microsoft SQL Server Analysis Manager С помощью Analysis Manager следует создать новую многомерную базу данных (назовем ее MyMiningData) и описать в ней доступ к источнику исходных данных (в нашем случае — к базе данных Access; рис. 3).
рис. 3
Далее следует выбрать соответствующую дочернюю ветвь Mining Models, а из ее контекстного меню — пункт New Mining Model. Затем нужно ответить на вопросы мастера построения моделей Data Mining. В частности, необходимо указать следующее: для построения модели используются реляционные данные, применяется алгоритм Microsoft Clustering, данные для анализа расположены в одной таблице (при этом следует выбрать ее имя). Затем в этой таблице нужно выбрать поле, являющееся уникальным идентификатором каждого письма в наборе (case key), а также поля, которые будут использоваться в качестве параметров для построения кластеров. В нашем примере из имеющихся в таблице нескольких десятков полей, соответствующих частоте употребления в письмах разных слов и символов, мы выбрали десять (рис. 4).
рис. 4
Завершить создание модели можно в редакторе Relational Mining Model Editor, указав в свойствах модели число кластеров (пусть оно будет равно пяти). Создание самих кластеров осуществляется с помощью выбора пункта меню Tools ® Process Mining Model (рис. 5).
рис. 5
Ниже мы рассмотрим, что представляют собой полученные кластеры.
Результаты кластеризации
Чтобы увидеть результаты кластеризации, нужно выбрать пункт View ® Content в меню редактора Relational Mining Model Editor. Здесь можно изучить свойства полученных пяти кластеров, выбирая их последовательно в разделе Content Detail. В нашем примере наибольший интерес представляют первые два из них — самые большие по объему: 1806 и 1114 из 4681. В одном значении поля IsSpam для всех членов кластера оказалось равным нулю (что означает, что письмо, параметры которого соответствуют этому кластеру, с высокой вероятностью не является спамом), в другом — единице (это означает, что письмо, параметры которого соответствуют данному кластеру, с очень высокой вероятностью является спамом; данный кластер показан на рис. 6).
рис. 6
Третий кластер (653 письма) также практически не содержит данных, относящихся к категории спама, а в оставшихся двух кластерах имеются данные обеих категорий (то есть письма с подобными характеристиками могут оказаться как спамом, так и обычными деловыми или личными посланиями).
Таким образом, мы создали модель настройки антиспамового фильтра. Применение его вполне очевидно — принятие решения о том, относится ли письмо к категории спама, зависит от того, в какой из полученных кластеров оно попадет.