Методы извлечения знаний

1

ВВЕДЕНИЕ

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

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

Знания неявно стали одним из главных источников капитала. Цена акций может во много раз превышать их покрытие материальными активами компании-эмитента. Это особенно заметно в случае компаний так называемой новой экономики. Например, для акций компании Oracle соотношение цена/активы (рыночная капитализация, деленная на активы компании за вычетом долгов) составляет 17 к 1. Поэтому многие ведущие компании уже имеют в своем составе специального сотрудника -- chief knowledge officer, -- ответственного за создание инфраструктуры и культуры совместного использования знаний. Главная задача специалистов такого рода -- вычленять, систематизировать и тиражировать интеллектуальный капитал внутри корпораций. Знания при этом воспринимаются как ресурс, а обеспечение ими налаживается по принципу just-in-time (точно вовремя), используемому при снабжении материальными ресурсами производственного процесса. Однако применяются эти знания не столько в производственных, сколько в управленческих процессах, предполагающих принятие стратегических и оперативных решений [17].

Тема извлечения знаний привлекает внимание учёных как в Европе, так и во всём мире. Изучением данной темы занимаются У. Файяд, Г. Пятетский-Шапиро, Т. Гаврилова, Л. Григорьев, П. Смит, Дж. Сейферт, В. Фроли, Ц. Матеус, Е. Монк, Б. Вагнер, С.Хааг и др.

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

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

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

Специфика современных требований к такой переработке следующие:

§ данные имеют неограниченный объем;

§ данные являются разнородными (количественными, качественными, текстовыми);

§ результаты должны быть конкретны и понятны;

§ инструменты для обработки сырых данных должны быть просты в использовании.

Традиционная математическая статистика, долгое время претендовавшая на роль основного инструмента анализа данных, откровенно спасовала перед лицом возникших проблем. Главная причина - концепция усреднения по выборке, приводящая к операциям над фиктивными величинами (типа средней температуры пациентов по больнице, средней высоты дома на улице, состоящей из дворцов и лачуг и т.п.). Методы математической статистики оказались полезными главным образом для проверки заранее сформулированных гипотез (verification-driven data mining) и для «грубого» разведочного анализа, составляющего основу оперативной аналитической обработки данных (online analytical processing, OLAP).

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

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

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

Использование баз данных (БД) и информационных систем(ИС) становится неотъемлемой составляющей деловой деятельности современного человека и функционирования преуспевающих организаций. В связи с этим большую актуальность приобретает освоение принципов построения и эффективного применения соответствующих технологий и программных продуктов: систем управления базами данных(СУБД), САSЕ-систем автоматизации проектирования, средств администрирования и зашиты БД и других.

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

Ценность информации в современном мире очень высока. В основе решения многих задач лежит обработка информации. С развитием экономики и ростом численности населения возрастает и объем взаимосвязанных данных, необходимых для решения коммерческих и административных задач. Для облегчения обработки информации создается ИС. Такая система в первую очередь призвана облегчить труд человека, но для этого она должна как можно лучше соответствовать очень сложной модели реального мира. Автоматизированными называют ИС, в которых применяют технические средства, в частности ЭВМ.

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

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

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

1 ПОСТАНОВКА ЗАДАЧИ

В основу проектирования БД должны быть положены представления конечных пользователей конкретной организации - концептуальные требования к системе. Именно конечный пользователь в своей работе принимает решения с учетом получаемой в результате доступа к БД информации. От оперативности и качества этой информации будет зависеть эффективность работы организации.

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

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

- БД должна удовлетворять выявленным и вновь возникающим требованиям конечных пользователей.

- БД должна легко расширяться при реорганизации и расширении предметной области.

Данные до включения в БД должны проверяться на достоверность.

Необходимо разработать АРМ мастера механического цеха, которая включает в себе базу данних, позволяющую:

· принимать заказы на изготовление деталей в виде таблицы;

· просматривать полную информацию по всем заказам в таблице, а также добавлять нужную Вам информацию;

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

· просматривать полную информации по станкам и инструменту;

· просматривать полную информацию по рабочему персоналу;

· просматривать составы бригады по ее номеру, и вывода отчета по рабочему персоналу;

· Полного просмотра информации ОАО им. М.В. «Фрунзе».

2 АНАЛИЗ МЕТОДОВ АВТОМАТИЗИРОВАННОГО ИЗВЛЕЧЕНИЯ ЗНАНИЙ ИЗ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ

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

Данные имеют неограниченный объем.

Данные являются разнородными (количественными, качественными, текстовыми).

Извлеченные знания должны быть конкретны и понятны.

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

2.1 Автоматизированное извлечение знаний из баз данных

Первоначально основным инструментом анализа данных были классические методы математической статистики, которые не могли эффективно обнаруживать скрытые закономерности в реальных данных. Главной причиной этому была концепция усреднения по выборке, приводящая к операциям над фиктивными величинами. Методы математической статистики оказались полезными главным образом для проверки заранее сформулированных гипотез (verification-driven data mining) и для "грубого" предварительного анализа, составляющего основу оперативной аналитической обработки данных (online analytical processing, OLAP).

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

Существующие системы Data Mining [5] дорогостоящие и не ориентированы на решение задач принятия решений. Самыми известными являются See5/С5.0 (RuleQuest, Австралия), Clementine (Integral Solutions, Великобритания), SIPINA (University of Lyon, Франция), IDIS (Information Discovery, США), KnowledgeSeeker (ANGOSS, Канада). Стоимость этих систем варьируется от 1 до 10 тыс. долл. Поэтому в данной работе рассматривается создание подобной системы автоматического извлечения знаний из баз данных разного формата с возможностью принятия решения на основе выявленных знаний. Структура разрабатываемой системы приведена на рис. 2.1.

Рис. 2.1 - Структура системы извлечения знаний из баз данных

Пользовательский интерфейс обеспечивает доступ ко всем возможностям

системы и управляет процессами извлечения знаний и принятием решений. Качество обнаружения знаний во многом зависит от участии пользователя. Первичная подготовка данных осуществляется в блоке перевода данных во внутреннее представление, учитывающие особенности алгоритмов извлечения знаний. Блок обнаружения знаний основан на алгоритме CLS [6], который выявляет скрытые закономерности в данных. Эти закономерности формируются в виде деревьев решений и сохраняются в базе знаний в форме продукционных правил. Извлечённые знания могут пополнять существующую базу знаний некоторой экспертной системы или сразу использоваться для выработки рекомендаций по достижению поставленных целей.

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

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

Оценка эффективности алгоритма выполнялась на интеллектуальном анализе медицинских данных небольшого объёма - 74 записи. Из них были выявлены знания в количестве 9 продукций. Для увеличения практической значимости разрабатываемой системы (EasyGetKnowledge) намечается расширить ориентацию алгоритма извлечения на базы данных различного формата.

2.1.1 Алгоритм построения деревьев решений для системы автоматизированного извлечения знаний

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

R(DX1, …, DXn, DY1, ..,DYm) = {< x1, …, xn, y1, …, ym>¦xi Є DXi,

yj Є DYj, I = 1..n, j = 1..m8P(x1, …, xn, y1, …,ym) }, (2.1)

где xi -значения входных атрибутов Xi из домена DXi;

yi -значения выходных атрибутов Yi из домена DYi;

P(x1,…,xn,y1,…,ym)- предикат, описывающий условия отображения конкретной предметной области в кортежи значений атрибутов < x1,…,xn,y1,…,ym>.

Необходимо сформировать отображение в виде набора правил:

{X1,X2,..,Xn}-> {Y1,Y2,…,Ym} (2.2)

ставящих каждому входному набору значений {xi=DXi, i=1..n} в соответствие некоторый набор целевых значений {yj=DYj, j=1..m}. Полученные функциональные зависимости:

Yj = Fj(X1,X2,….,Xn), j=1..m (2.3)

должны быть верны для кортежей отношения (1) и могут быть использованы при нахождении выходных атрибутов Yj для новых значений входных атрибутов Xi (i=1..n).

Для автоматизированного извлечения знаний использовался метод CART (classification and regression trees) из класса методов деревьев решений. Данный подход является самым распространенным в настоящее время способом выявления, структурирования и графического представления логических закономерностей в данных. Его преимущества заключаются в следующем[33]:

• быстрый процесс обнаружения знаний;

• генерация правил в предметных областях, в которых трудно формализуются знания;

• извлечение правил на естественном языке;

• создание интуитивно понятной классификационной модели предметной области;

• прогноз с высокой точностью, сопоставимой с другими методами (статистическими и нейросетевыми);

• построение непараметрических моделей.

Хорошая эволюция и достигнутый уровень формализации методов послужили основанием использовать процедуру CART, как лучший из этого класса, в блоке извлечения знаний. В данном алгоритме можно выделить три операции, от реализации которых зависит его трудоёмкость и качество обнаружения знаний: сортировка источника данных при формировании множества условий U для атрибутов числового типа, вычисление критерия Gini [33] при разбиении узлов бинарного дерева, перемещение в таблице значительных объёмов информации при делении узла.

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

Для определения необходимости последующего деления узла потребуется

M проверок. Рассмотрим случай, когда из узла порождаются узлы-потомки. В этом случае для каждого атрибута формируются 2N_cp-1-1 возможных условий ui принадлежит U (|U|=2N_cp-1-1) (2.4), которые определяют варианты разбиения узла. Эта операция реализуется M проверками. Отбор наилучшего варианта разбиения узла дерева проводится по наибольшей классифицирующей силе, вычисляемой по критерию Gini :

(2.4)

Из формулы (2.4) видно, что её вычислительная сложность состоит из суммы следующих операций: подсчёт элементов l_i, r_i класса i (i=1..Ncp) в множествах L и R и вычисление индекса Gini. Подсчёт объектов каждого класса занимает M операций, а вычисление индекса Gini выполняется за 2•Ncp+2 операций. Следовательно, классификация узла по условию u_i и отбор наилучшего разбиения занимает в целом 2M + 2Ncp операций. Тогда для каждого категорийного атрибута потребуется (2M + 2Ncp)•( 2Ncp-1-1) операций. А так как таблица имеет N атрибутов, то классификация одного узла без учёта разделения будет занимать (2M + 2Ncp)•(2Ncp-1-1)•N +M условных операций. На примере таблицы, содержащей 1000 строк, 10 категорийных атрибутов с 5 возможными значениями, разбиение корневого узла дерева потребует приблизительно 300 000 условных операций, что значительно меньше полного перебора.

В качестве предметной области для проведения интеллектуального анализа

рассмотрена медицинская диагностика. Часть данных (90%) использовалась для извлечения знаний, а остальные 10% - для оценки качества прогнозирования исходов лечения. При этом правильно было спрогнозировано 48 исходов лечения из 70. Для увеличения эффективности алгоритма планируется использование генетических алгоритмов для увеличение точности прогноза в узлах дерева содержащих небольшое количество элементов.

2.1.2 Интеллектуальный анализ данных Data Mining

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

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

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

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

Специфика современных требований к такой переработке следующие:

• Данные имеют неограниченный объем

• Данные являются разнородными (количественными, качественными,

текстовыми)

• Результаты должны быть конкретны и понятны

• Инструменты для обработки сырых данных должны быть просты в использовании

Традиционная математическая статистика, долгое время претендовавшая на роль основного инструмента анализа данных, откровенно спасовала перед лицом возникших проблем. Главная причина - концепция усреднения по выборке, приводящая к операциям над фиктивными величинами (типа средней температуры пациентов по больнице, средней высоты дома на улице, состоящей из дворцов и лачуг и т.п.). Методы математической статистики оказались полезными главным образом для проверки заранее сформулированных гипотез (verification-driven data mining) и для "грубого" разведочного анализа, составляющего основу оперативной аналитической обработки данных (online analytical processing, OLAP).

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

Таблица 2.1 - Примеры формулировок задач при использовании методов OLAP и Data Mining [34]

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

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

так называемые скрытые знания (hidden knowledge). К обществу пришло понимание, что сырые данные (raw data) содержат глубинный пласт знаний, при грамотной раскопке которого могут быть обнаружены настоящие самородки (рис. 2.2).

В целом технологию Data Mining достаточно точно определяет Григорий Пиатецкий-Шапиро - один из основателей этого направления:

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

ь ранее неизвестных

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

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

ь и доступных интерпретации знаний,

ь необходимых для принятия решений в различных сферах

ь человеческой деятельности.

Сфера применения Data Mining ничем не ограничена - она везде, где имеются какие-либо данные. Но в первую очередь методы Data Mining сегодня, мягко говоря, заинтриговали коммерческие предприятия, развертывающие проекты на основе информационных хранилищ данных (Data Warehousing). Опыт многих таких предприятий показывает, что отдача от использования Data Mining может достигать 1000%. Например, известны сообщения об экономическом эффекте, в 10-70 раз превысившем первоначальные затраты от 350 до 750 тыс. дол.[35]. Известны сведения о проекте в 20 млн. дол., который окупился всего за 4 месяца. Другой пример - годовая экономия 700 тыс. дол. за счет внедрения Data Mining в сети универсамов в Великобритании.

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

2.1.3 Приложения Data Mining

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

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

v исследование временных шаблонов помогает торговым предприятиям принимать решения о создании товарных запасов. Оно дает ответы на вопросы типа "Если сегодня покупатель приобрел видеокамеру, то через какое время он вероятнее всего купит новые батарейки и пленку?"

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

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

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

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

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

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

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

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

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

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

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

Data Mining может применяться во множестве других областей:

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

v политика гарантий. Производителям нужно предсказывать число клиентов, которые подадут гарантийные заявки, и среднюю стоимость заявок;

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

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

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

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

• ассоциация;

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

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

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

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

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

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

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

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

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

2.1.5 Классы систем Data Mining

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

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

Рис. 2.3 - Data Mining - мультидисциплинарная область

Популярные продукты для DATA Mining:

• Lementine;

• PRW;

• CainSmarts;

• Datamind;

• M1 model 1;

• psOLPARS;

• Cart;

• Cognos;

• S-Plus;

• Wizwhu;

• NeuroShell 2.

Предметно-ориентированные аналитические системы.

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

Статистические пакеты

Последние версии почти всех известных статистических пакетов включают наряду с традиционными статистическими методами также элементы Data Mining. Но основное внимание в них уделяется все же классическим методикам - корреляционному, регрессионному, факторному анализу и другим. Самый свежий детальный обзор пакетов для статистического анализа приведен на страницах ЦЭМИ http://is1.cemi.rssi.ru/ruswin/index.htm. Недостатком систем этого класса считают требование к специальной подготовке пользователя. Также отмечают, что мощные современные статистические пакеты являются слишком "тяжеловесными" для массового применения в финансах и бизнесе. К тому же часто эти системы весьма дороги - от $1000 до $15000.

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

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

2.2 Кластерный анализ

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

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

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

Для решения задачи кластеризации (clustering problem) необходим набор неклассифицированных объектов и средства измерения подобия объектов. Целью кластеризации является организация объектов в классы, удовлетворяющие некоторому стандарту качества, например на основе максимального сходства объектов каждого класса [11].

Числовая таксономия (numeric taxonomy) - один из первых подходов к решению задач кластеризации. Числовые методы основываются на представлении объектов с помощью набора свойств, каждое из которых может принимать некоторое числовое значение. При наличии корректной метрики подобия каждый объект (вектор из n значений признаков) можно рассматривать как точку в n-мерном пространстве. Мерой сходства двух объектов можно считать расстояние между ними в этом пространстве.

Многие алгоритмы кластеризации, как и многие алгоритмы обучения с учителем, определяют категории в терминах необходимых и достаточных условий принадлежности к этим категориям. Эти условия представляют собой наборы признаков, свойственных каждому элементу категории и отличных от признаков другой категории. Таким образом можно описать многие категории, однако человеческие категории не всегда соответствуют этой модели. На самом деле они характеризуются большей гибкостью и более разветвлённой структурой. Человеческие категории определяются сложной системой сходства между элементами, а не необходимыми и достаточными условиями принадлежности членов. При такой категоризации может не существовать свойств, общих для всех элементов класса. Эти проблемы учтены в системе COBWEB [10]. В данной системе реализован инкрементальный алгоритм обучения, не требующий представления всех обучающих примеров до начала обучения. Во многих приложениях обучаемая система получает данные, зависящие от времени. В этом случае она должна строить полезные определения понятий на основе исходных данных и обновлять эти описания с появлением новой информации. В системе COBWEB также решена проблема определения корректного числа кластеров. Подход, когда количество кластеров определяется пользователем нельзя назвать гибким. В системе COBWEB для определения количества кластеров, глубины иерархии и принадлежности категории новых экземпляров используется глобальная метрика качества. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility). Критерий полезности категории был определён при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

Значения суммируются по всем категориям , всем свойствам и всем значениям свойств . Значение называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство принимает значение , относится к категории . Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесённых к одной категории, имеют одинаковые значения. Величина называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории свойство принимает значение . Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение - это весовой коэффициент, усиливающий влияние наиболее распространённых свойств. Благодаря совместному учёту этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этихсвойств у объектов из других категорий [11].

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

Одним из основных подходов в «обнаружении знаний в данных» (Data Mining) является кластеризация. Кластеризация служит для объединения больших объемов данных в группы (кластеры), которые характеризуются тем, что элементы внутри каждой группы имеют больше «сходства» между собой, чем между элементами соседних кластеров. В целом, все методы кластеризации можно подразделить на иерархические и неиерархические. Последние чаще всего используются при анализе больших объемов данных, т.к. они обладают большей скоростью [6].

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

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

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

DBSCAN, BIRTH, CP, CURE и др.) Обработка данных смешанного типа в настоящий момент вызывает значительные трудности и является областью исследований.

Рекомендуемые этапы процесса кластерного анализа.

В общем случае все этапы кластерного анализа взаимосвязаны, и решения, принятые на одном из них, определяют действия на последующих этапах [14].

Аналитику следует решить, использовать ли все наблюдения либо же исключить некоторые данные или выборки из набора даннях:

· Выбор метрики и метода стандартизации исходных данных.

· Определение количества кластеров (для итеративного кластерного анализа).

· Определение метода кластеризации (правила объединения или связи).

По мнению специалистов, выбор метода кластеризации является решающим при определении формы и специфики кластеров.

Анализ результатов кластеризации. Этот этап подразумевает решение таких вопросов: не является ли полученное разбиение на кластеры случайным; является ли разбиение надежным и стабильным на подвыборках данных; существует ли взаимосвязь между результатами кластеризации и переменными, которые не участвовали в процессе кластеризации; можно ли интерпретировать полученные результаты кластеризации.

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

· анализ результатов кластеризации, полученных на определенных выборках набора данных;

· кросс-проверка;

· проведение кластеризации при изменении порядка наблюдений в наборе данных;

· проведение кластеризации при удалении некоторых наблюдений;

· проведение кластеризации на небольших выборках.

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

Как и любые другие методы, методы кластерного анализа имеют определенные слабые стороны, т.е. некоторые сложности, проблемы и ограничения.

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

Существует ряд сложностей, которые следует продумать перед проведением кластеризации.

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

на кластеры и, как следствие, - к неверному решению задачи.

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

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

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

2.2.2 Решения задачи кластеризации

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

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

Одним из первых подходов решения задач кластеризации является числовая таксономия (numeric taxonomy). Численные методы основываются на представлении объектов с помощью свойств, каждое из которых может принимать некоторое числовое значение. При наличии корректной метрики подобия каждый объект (вектор из n значений признаков) рассматривают как точку в n-мерном пространстве. Используя метрику подобия, алгоритмы кластеризации этой группы строят классы по принципу «снизу вверх». В рамках этого подхода, также называемого стратегией накопительной кластеризации (agglomerative clustering), категории формируются следующим образом:

1) среди всех пар объектов выбирается пара с максимальной степенью подобия, которая и становится кластером;

2) определяются свойства кластера как некоторые функции свойств элементов (например, среднее значение), и компоненты объектов заменяются этими значениями признаков;

3) процесс повторяется до тех пор, пока все объекты не будут отнесены к одному кластеру.

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

Примером такой кластеризации является система COBWEB [10]. Не претендуя на лучшую модель человеческого познания, эта система учитывает категории базового уровня и степень принадлежности элемента соответствующей категории. Кроме того, в программе COBWEB реализован инкрементальный алгоритм обучения, не требующий представления всех обучающих примеров до начала обучения. Во многих приложениях обучаемая система получает данные, зависящие от времени. В этом случае она должна строить полезные определения понятий на основе исходных данных и обновлять эти описания с появлением новой информации. В системе COBWEB также решена проблема определения корректного числа кластеров. Подход, когда количество кластеров определяется пользователем нельзя назвать гибким. В системе COBWEB для определения количества кластеров, глубины иерархии и принадлежности категории новых экземпляров используется глобальная метрика качества.

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

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