Классификация существующих задач, моделей и методов Data Mining

В данном пункте представлена классификация существующих задач, моделей и методов Data Mining.

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

Задачи Data Mining

Разберем основный задачи Data Mining с формальными постановками.

Решения задач Data Mining можно разделить на две основные группы. Первая группа - это обучение с учителем, вторая - обучение без учителя.

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

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

Задача классификации

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

Пусть имеется множество классов:

(1)

состоящее из непересекающихся классов M. Следует множество объектов X разбить на классы:

, (2)

и алгоритм должен давать ответ на вопрос "какому классу принадлежит объект x?". В некоторых задачах классы называют образами и говорят о задаче распознавания образов [21].

Формальная постановка задача сводится к тому, что у нас есть X - множество описаний объектов, Y - множество классов.

Есть неизвестная зависимость, именуемая отображением y: X > Y, значения которой будут известны только на объектах конечной обучающий выборки.

В конечном итоге необходимо составить алгоритм a: X>Y, способный отнести к определённому классу целевой объект из множества X.

Задача регрессии

Задачи регрессии чем-то схожи с задачами классификации. Они позволяют значение некоторого параметра объекта по его заранее известным характеристикам. Отличительная черта заключается в том, что знанием параметров - это не конечное множество известных классов, а множество действительных чисел, характеризующих этот класс [20]. В формальной постановке задача регрессии отличается множеством Y. Если

(3)

то это задача не классификации, а задача восстановления регрессии [21].

Поиск ассоциативных правил

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

Пусть покупателю необходимо предложить товар в онлайн магазине и для этого нужно разместить на основной витрине "ассоциированные" товары ближе друг к другу. Поиск ассоциативных правил как раз и подбирает эти товары на основе уже сделанных покупок предыдущих пользователей. Задача нахождения ассоциативных правил разбивается на две подзадачи: нахождение всех наборов часто встречающихся элементов и генерация правил из наборов элементов, найденных согласно предыдущему пункту. Данные правила могут быть использованы для более эффективного понимания основной идеи анализируемых данных, а также для прогнозирования появления определенных событий [20].

В обобщенное виде постановка задачи выглядит следующим образом. Имеются объекты, представляющие из себя исследуемые наборы:

, (4)

где - объекты, состоящие в исследуемых наборах, а n - это общее число анализируемых объектов.

Данные наборы объектов, входящие в представленное множество I, именуются транзакциями. Представим транзакцию как подмножество множества:

. (5)

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

(6)

где n - общее число всех исследуемых объектов, а m - количество доступных для последующего анализа.

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

(7)

Набор, состоящий из k объектов, называется k-элементным набором.

Множество транзакций, в которые входит набор F, представим в виде следующего множества:

(8)

Отношение количества транзакций, содержащее набор F, к общему количество транзакций именуется поддержкой набора F и обозначается Supp (F):

(9)

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

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

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

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

Имеется обучающая выборка:

(10)

и функция расстояния между анализируемыми объектами

. (11)

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

Алгоритм кластеризации можно представить в виде следующей функции:

, (12)

которая ставит каждому объекту из множества X метку кластера из множества Y. В некоторых случаях мы заранее знаем множество меток, а в некоторых задачах нам необходимо определить оптимальное число кластеров [21].

Отличительная черта кластеризации от классификации заключается в том, что у объектов для кластеризации метки изначально не известны, более того может быть ситуация, что не известно само множество меток.

Модели Data Mining

Цель технологии Data Mining - нахождение в анализируемых данных таких моделей, нахождение которых весьма затруднительно или вовсе невозможно обычными методами. Выделяют два основных вида моделей: предсказательные и описательные, а также по математической постановке можно поделить на вероятностные, логические и линейные [21]. Рассмотрим для начала предсказательные модели.

Предсказательные модели

Предсказательные модели (predictive model) основываются на данных с уже заранее известными результатами. На основании других наборов данных строятся предсказания результатов. Требования к модели - максимальная точность работы, модель оправданна и имела статистическую значимость.

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

К данным типам моделей можно отнести следующие:

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

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

Описательные модели

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

К данным типам моделям можно отнести следующие виды [21]:

· Модели кластеров - описывают группы (кластеры), на которые можно разделить объекты, данные о которых подвергаются анализу. Группируются объекты (наблюдения, события) на основе данных (свойств), описывающих сущность объектов. Объекты внутри кластера должны быть "похожими" друг на друга и отличаться от объектов, вошедших в другие кластеры. Чем сильнее "похожи" объекты внутри кластера и чем больше отличий между кластерами, тем точнее кластеризация;

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

· Модели исключений - описывают исключительные ситуации в записях (например, отдельных пациентов), которые резко отличаются чем-либо от основного множества записей (группы больных). Знание исключений может быть использовано двояким образом. Возможно, эти записи представляют собой случайный сбой, например, ошибки операторов, вводивших данные в компьютер. Характерный случай: если оператор, ошибаясь, ставит десятичную точку не в том месте, то такая ошибка сразу дает резкий "всплеск" на порядок. Подобную "шумовую" случайную составляющую имеет смысл отбросить, исключить из дальнейших исследований, поскольку большинство методов, которые будут рассмотрены в данной главе, очень чувствительно к наличию "выбросов" - резко отличающихся точек, редких, нетипичных случаев. С другой стороны, отдельные, исключительные записи могут представлять самостоятельный интерес для исследования, т.к. они могут указывать на некоторые редкие, но важные аномальные заболевания. Даже сама идентификация этих записей, не говоря об их последующем анализе и детальном рассмотрении, может оказаться очень полезной для понимания сущности изучаемых объектов или явлений;

· Итоговые модели - выявление ограничений на данные анализируемого массива. Например, при изучении выборки данных по пациентам не старше 30 лет, перенесшим инфаркт миокарда, обнаруживается, что все пациенты, описанные в этой выборке, либо курят более 5 пачек сигарет в день, либо имеют вес не ниже 95 кг. Подобные ограничения важны для понимания данных массива, по сути дела это новое знание, извлеченное в результате анализа. Таким образом, построение итоговых моделей заключается в нахождении каких-либо фактов, которые верны для всех или почти всех записей в изучаемой выборке данных, но которые достаточно редко встречались бы во всем мыслимом многообразии записей такого же формата и, например, характеризовались бы теми же распределениями значений полей. Если взять для сравнения информацию по всем пациентам, то процент либо сильно курящих, либо чрезмерно тучных людей будет весьма невелик. Можно сказать, что решается как бы неявная задача классификации, хотя фактически задан только один класс, представленный имеющимися данными;

· Ассоциативные модели - выявление закономерностей между связанными событиями. Примером такой закономерности служит правило, указываю - ее, что из события X следует событие Y. Такие правила называются ассоциативными.

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

Вероятностные модели

Модели Data Mining построенные на основе теории вероятностей. Пример такой модели - наивный байесовский классификатор.

Наивный байесовский классификатор - простой вероятностный классификатор, основанный на применении Теоремы Байеса со строгими предположениями о независимости. Сама теорема выражается следующей формулой:

, (13)

где

· P (c|d) - вероятность что элемент d принадлежит классу c.

· P (d|c) - вероятность встретить элемент d среди всех элементов класса c.

· P (c) - безусловная вероятность встретить элемент класса c в корпусе элементов.

· P (d) - безусловная вероятность элемента d в корпусе элементов.

Смысл теорема Байеса - переставить местами причину и следствие. Зная с какой вероятностью, причина приводит к некому событию, эта теорема позволяет вычислить вероятность того что именно эта причина привела к данному результату.

Цель классификации заключается в том, чтобы понять к какому классу принадлежит объект, потому необходима не сама вероятность, а наиболее вероятный класс элемента. Байесовский классификатор использует оценку апостериорного максимума для определения наиболее вероятного класса. Грубо говоря, это класс с максимальной вероятностью [22].

Линейные модели

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

Пусть X - пространство объектов; Y = {?1, 1} - множество допустимых ответов; объекты описываются n числовыми признаками f_j: X > R, j = 1,., n.

Вектор x = (x¹,., xⁿ) ЎК Rⁿ, где x^j = f_j (x), называется признаковым описанием объекта x. Если дискриминантная функция определяется как скалярное произведение вектора x и вектора параметров w ЎК Rⁿ, то получается линейный классификатор:

, (14)

Уравнение = 0 задаёт гиперплоскость, разделяющую классы в пространстве R_n. Если вектор x находится по одну сторону гиперплоскости с её направляющим вектором w, то объект x относится к классу +1, иначе - к классу ?1.

Параметр w₀ иногда опускают. Иногда полагают, что среди признаков есть константа, f_j (x) ? ?1, и тогда роль свободного коэффициента w₀ играет параметр w_j [21].

Логические модели

Логические методы, или методы логической индукции, включают:

· Нечеткие запросы и анализы.

· Символьные правила.

· Деревья решений.

· Генетические алгоритмы.

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

Методы Data Mining

В данном пункте рассмотрены основные методы Data Mining.

Базовые методы

Алгоритмы, которые основаны на переборе, следует относится к базовым методам. Для простого перебора требуется О (2N) операций, где N - количество исследуемых объектов. Практически невозможно решать задачи базовыми алгоритмами, так как с увеличением количества данных объем вычислений растет экспоненциально.

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

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

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

Нечеткая логика

Основным способом исследования задач анализа данных является их отображение на формализованный язык и последующий анализ полученной модели.

Неопределенность по объему отсутствующей информации у системного аналитика можно разделить на три большие группы:

1. Неизвестность.

2. Неполнота (недостаточность, неадекватность).

3. Недостоверность.

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

Выделяют два вида физической неопределенности:

1. Неточность (неточность измерений значений определенной величины, выполняемых физическими приборами).

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

Выделяют два вида лингвистической неопределенности:

1. Неопределенность значений слов (многозначность, расплывчатость, неясность, нечеткость). Она возникает в случае, если отображаемые одним и тем же словом объекты задачи управления различны.

2. Неоднозначность смысла фраз (выделяют синтаксическую и семантическую).

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

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

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