Data Mining — добыча данных

Data Mining - добыча данных Развитие методов записи и хранения данных привело к бурному росту объемов собираемой и анализируемой информации. Объемы данных настолько внушительны, что человеку просто не по силам проанализировать их самостоятельно, хотя необходимость проведения такого анализа вполне очевидна, ведь в этих "сырых" данных заключены знания, которые могут быть использованы при принятии решений. Для того чтобы провести автоматический анализ данных, используется Data Mining. Data Mining – это процесс обнаружения в "сырых" данных ранее неизвестных нетривиальных практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Data Mining является одним из шагов Knowledge Discovery in Databases. Информация, найденная в процессе применения методов Data Mining, должна быть нетривиальной и ранее неизвестной, например, средние продажи не являются таковыми. Знания должны описывать новые связи между свойствами, предсказывать значения одних признаков на основе других и т.д. Найденные знания должны быть применимы и на новых данных с некоторой степенью достоверности. Полезность заключается в том, что эти знания могут приносить определенную выгоду при их применении. Знания должны быть в понятном для пользователя не математика виде. Например, проще всего воспринимаются человеком логические конструкции "если … то …". Алгоритмы, используемые в Data Mining, требуют большого количества вычислений. Раньше это являлось сдерживающим фактором широкого практического применения Data Mining, однако сегодняшний рост производительности современных процессоров снял остроту этой проблемы. Теперь за приемлемое время можно провести качественный анализ сотен тысяч и миллионов записей. Решение большинства из проблем бизнес анализа сводится к той или иной задаче Data Mining или к их комбинации. Например, оценка рисков – это решение задачи регрессии или классификации, сегментация рынка – кластеризация, стимулирование спроса – ассоциативные правила. Фактически, задачи Data Mining являются элементами, из которых можно собрать решение подавляющего большинства реальных бизнес задач. 1. Автокорреляция Корреля́ция — статистическая взаимосвязь двух или нескольких случайных величин (либо величин, которые можно с некоторой допустимой степенью точности считать таковыми). При этом изменения одной или нескольких из этих величин приводят к систематическому изменению другой или других величин. Математической мерой корреляции двух случайных величин служит коэффициент корреляции. Коэффицие́нт корреля́ции или парный коэффицие́нт корреля́ции в теории вероятностей и статистике — это показатель характера изменения двух случайных величин. Корреляция может быть положительной и отрицательной (возможна также ситуация отсутствия статистической взаимосвязи — например, для независимых случайных величин). Отрицательная корреляция — корреляция, при которой увеличение одной переменной связано с уменьшением другой переменной, при этом коэффициент корреляции отрицателен. Положительная корреляция — корреляция, при которой увеличение одной переменной связано с увеличением другой переменной, при этом коэффициент корреляции положителен. Автокорреляция — статистическая взаимосвязь между случайными величинами из одного ряда, но взятых со сдвигом, например, для случайного процесса — со сдвигом по времени. Метод обработки статистических данных, заключающийся в изучении коэффициентов (корреляции) между переменными, называется корреляционным анализом. Целью автокорреляционного анализа является выяснение степени статистической зависимости между различными значениями (отсчетами) случайной последовательности, которую образует поле выборки данных. В процессе автокорреляционного анализа рассчитываются коэффициенты корреляции (мера взаимной зависимости) для двух значений выборки, отстоящих друг от друга на определенное количество отсчетов, называемые также лагом. Совокупность коэффициентов корреляции по всем лагам представляет собой автокорреляционную функцию ряда (АКФ): R(k)=corr(X(t),X(t+k)), где k>0 – целое число (лаг). По поведению АКФ можно судить о характере анализируемой последовательности и наличии периодичности (например, сезонной). Очевидно, что при k=0, автокорреляционная функция будет максимальной и равной 1, т.е. значение последовательности полностью коррелированно само с собой, степень статистической взаимозависимости максимальна. Действительно, если факт появления данного значения имел место, то и соответствующая вероятность равна 1. По мере увеличения числа лагов, т.е. увеличения расстояния между двумя значениями, для которых вычисляется коэффициент корреляции, значения АКФ будут убывать из-за уменьшения статистической взаимозависимости между этими значениями (вероятность появления одного из них все меньше влияет на вероятность появления другого). При этом чем быстрее убывает АКФ, тем быстрее изменяется анализируемая последовательность. И наоборот, если АКФ убывает медленно, то и соответствующий процесс является относительно гладким. Если в исходной выборке имеет место тренд (плавное увеличение или уменьшение значений ряда), то плавное изменение АКФ также будет иметь место. При наличии сезонных колебаний в исходном наборе данных, АКФ также будет иметь периодические всплески. Для применения алгоритма автокорреляции в Deductor Studio необходимо выбрать поле, для которого вычисляется АКФ. В поле «Количество отсчетов» требуется указать количество отсчетов, для которых будут рассчитаны значения АКФ. График автокорреляционной функции можно получить, отложив по оси ординат коэффициент корреляции двух функций (базовой и функции сдвинутой на величину τ) а по оси абсцисс величину τ. Если исходная функция строго периодическая, то на графике автокорреляционной функции тоже будет строго периодическая функция. Автокорреляционная функция играет важную роль в математическом моделировании и анализе временных рядов, показывая характерные времена для исследуемых процессов 2. Нейронные сети В наши дни возрастает необходимость в системах, которые способны не только выполнять однажды запрограммированную последовательность действий над заранее определенными данными, но и способны сами анализировать вновь поступающую информацию, находить в ней закономерности, производить прогнозирование и т.д. В этой области приложений самым лучшим образом зарекомендовали себя так называемые нейронные сети – самообучающиеся системы, имитирующие деятельность человеческого мозга. Рассмотрим подробнее структуру искусственных нейронных сетей (НС) и их применение в конкретных задачах. Нейросети – это распределенные и параллельные системы, способные к адаптивному обучению путем реакции на положительные и отрицательные воздействия. В основе построения сети лежит элементарный преобразователь, называемый искусственным нейроном или просто нейроном по аналогии с его биологическим прототипом. Структуру нейросети можно описать следующим образом. Нейросеть состоит из нескольких слоев: входной, внутренние (скрытые) и выходной слои. Входной слой реализует связь с входными данными, выходной – с выходными. Внутренних слоев может быть от одного и больше. В каждом слое содержится несколько нейронов. Между нейронами есть связи, называемые весами. Назначение и подготовка обучающей выборки. Нейросеть способна имитировать какой-либо процесс. Любое изменение входов нейросети ведет к изменению ее выходов. Причем выходы нейросети однозначно зависят от ее входов. Перед тем как использовать нейросеть, ее необходимо обучить. Задача обучения здесь равносильна задаче аппроксимации функции, то есть восстановление функции по отдельно взятым ее точкам – таблично заданной функции. Таким образом, для обучения нужно подготовить таблицу с входными значениями и соответствующими им выходными значениями, то есть подготовить обучающую выборку. По такой таблице нейросеть сама находит зависимости выходных полей от входных. Далее эти зависимости можно использовать, подавая на вход нейросети некоторые значения. На выходе будут восстановлены зависимые от них значения. Причем на вход можно подавать значения, на которых нейросеть не обучалась. Важно следующее. Обучающая выборка не должна содержать противоречий, так как нейросеть однозначно сопоставляет выходные значения входным. После обучения на вход нейросети необходимо подавать значения из диапазона, на котором она обучалась. Например, если при обучении нейросети на один из ее входов подавались значения от 0 до 100, то в дальнейшем следует на этот вход подавать значения из диапазона от 0 до 100. Допускается подавать значения, лежащие рядом с диапазоном. Настройка назначения полей. В самом начале работы с нейросетью нужно определиться, что является ее входами, а что – выходами. Предполагается, что у нас уже есть таблица с обучающей выборкой. Обычно для ее подготовки пользуются методами очистки и трансформации данных – редактируются аномалии, заполняются или удаляются пропуски, устраняются дубликаты и противоречия, производится квантование и табличная замена, данные приводятся к скользящему окну, преобразуется формат данных. Представление входных данных Основное отличие НС в том, что в них все входные и выходные параметры представлены в виде чисел с плавающей точкой обычно в диапазоне [0..1]. В то же время данные предметной области часто имеют другое кодирование. Так, это могут быть числа в произвольном диапазоне, даты, символьные строки. Таким образом данные о проблеме могут быть как количественными, так и качественными. Рассмотрим сначала преобразование качественных данных в числовые, а затем рассмотрим способ преобразования входных данных в требуемый диапазон. Качественные данные мы можем разделить на две группы: упорядоченные (ординальные) и неупорядоченные. Для рассмотрения способов кодирования этих данных мы рассмотрим задачу о прогнозировании успешности лечения какого-либо заболевания. Примером упорядоченных данных могут, например, являться данные, например, о дополнительных факторах риска при данном заболевании. нет ожирение алкоголь курение гипертония А также возможным примером может быть, например, возраст больного: до 25 лет 25-39 лет 40-49 лет 50-59 лет 60 и старше Опасность каждого фактора возрастает в таблицах при движении слева направо. В первом случае мы видим, что у больного может быть несколько факторов риска одновременно. В таком случае нам необходимо использовать такое кодирование, при котором отсутствует ситуация, когда разным комбинациям факторов соответствует одно и то же значение. Наиболее распространен способ кодирования, когда каждому фактору ставится в соответствие разряд двоичного числа. 1 в этом разряде говорит о наличии фактора, а 0 - о его отсутствии. Параметру нет можно поставить в соответствии число 0. Таким образом для представления всех факторов достаточно 4-х разрядного двоичного числа. Таким образом число 10102 = 1010 означает наличие у больного гипертонии и употребления алкоголя, а числу 00002 соответствует отсутствие у больного факторов риска. Таким образом факторы риска будут представлены числами в диапазоне [0..15]. Во втором случае мы также можем кодировать все значения двоичными весами, но это будет нецелесообразно, т.к. набор возможных значений будет слишком неравномерным. В этом случае более правильным будет установка в соответствие каждому значению своего веса, отличающегося на 1 от веса соседнего значения. Так, число 3 будет соответствовать возрасту 50-59 лет. Таким образом возраст будет закодирован числами в диапазоне [0..4]. В принципе аналогично можно поступать и для неупорядоченных данных, поставив в соответствие каждому значению какое-либо число. Однако это вводит нежелательную упорядоченность, которая может исказить данные, и сильно затруднить процесс обучения. В качестве одного из способов решения этой проблемы можно предложить поставить в соответствие каждому значению одного из входов НС. В этом случае при наличии этого значения соответствующий ему вход устанавливается в 1 или в 0 при противном случае. К сожалению, данный способ не является панацеей, ибо при большом количестве вариантов входного значения число входов НС разрастается до огромного количества. Это резко увеличит затраты времени на обучение. В качестве варианта обхода этой проблемы можно использовать несколько другое решение. В соответствие каждому значению входного параметра ставится бинарный вектор, каждый разряд которого соответствует отдельному входу НС. Нормализация значений полей. После того, как указаны входные и выходные поля, следует нормализация данных в обучающей выборке. Целью нормализации значений полей является преобразование данных к виду, наиболее подходящему для обработки алгоритмом. Для таких обработчиков как нейронная сеть, дерево решений, линейная модель прогнозирования данные, поступающие на вход, должны иметь числовой тип, а их значения должны быть распределены в определенном диапазоне. Нормализатор может преобразовать дискретные данные к набору уникальных индексов или значения, лежащие в произвольном диапазоне к диапазону [0..1]. Для нейросети доступны следующие виды нормализации полей. 1. Линейная нормализация. Используется только для непрерывных числовых полей. Позволяет привести числа к диапазону [min..max], то есть минимальному числу из исходного диапазона будет соответствовать min, а максимальному – max. Остальные значения распределяются между min и max. 2. Уникальные значения. Используется для дискретных значений. Такими являются строки, числа или даты, заданные дискретно. Чтобы привести непрерывные числа в дискретные, можно, например, воспользоваться обработкой «квантование». Так следует поступать для величин, для которых можно задать отношение порядка, то есть, если для двух любых дискретных значений можно указать, какое больше, а какое меньше. Тогда все значения необходимо расположить в порядке возрастания. Далее они нумеруются по порядку, и значения заменяются их порядковым номером. 3. Битовая маска. Используется для дискретных значений. Этот вид нормализации следует использовать для величин, которые можно только сравнивать на равенство или неравенство, но нельзя сказать, какое больше, а какое меньше. Все значения заменяются порядковыми номерами, а номер рассматривается в двоичном виде или в виде маски из нулей и единиц. Тогда каждая позиция маски рассматривается как отдельное поле, содержащее ноль или единицу. К такому полю можно применить линейную нормализацию, то есть заменить ноль некоторым минимальным значением, а единицу – максимальным. После такой нормализации на вход нейросети будет подаваться не одно это поле, а столько полей, сколько разрядов в маске. Настройка обучающей выборки. После нормализации полей следует настроить обучающую выборку. Обучающую выборку разбивают на два множества – обучающее и тестовое. Обучающее множество включает записи (примеры), которые будут использоваться непосредственно для обучения сети, т.е. будут содержать входные и желаемые выходные (целевые) значения. Тестовое множество также включает записи (примеры), содержащие входные и желаемые выходные (целевые) значения, но используемое не для обучения сети, а для проверки результатов обучения. Разбивать исходную выборку на эти множества можно двумя способами: либо по порядку, либо случайно. Если разбиение происходит по порядку, то тестовое множество выбирается либо из начала, либо из конца исходной выборки. Настройка структуры нейросети. Далее задаются параметры, определяющие структуру нейронной сети - количество скрытых слоев и нейронов в них, а также активационная функция нейронов. Замечание. К выбору количества скрытых слоев и количества нейронов для каждого скрытого слоя нужно подходить осторожно. Хотя до сих пор не выработаны четкие критерии выбора, дать некоторые общие рекомендации все же возможно. Считается, что задачу любой сложности можно решить при помощи двухслойной нейросети, поэтому конфигурация с количеством скрытых слоев, превышающих 2, вряд ли оправдана. Для решения многих задач вполне подойдет однослойная нейронная сеть. При выборе количества нейронов следует руководствоваться следующим правилом: «количество связей между нейронами должно быть значительно меньше количества примеров в обучающем множестве». Количество связей рассчитывается как связь каждого нейрона со всеми нейронами соседних слоев, включая связи на входном и выходном слоях. Слишком большое количество нейронов может привести к так называемому «переобучению» сети, когда она выдает хорошие результаты на примерах, входящих в обучающую выборку, но практически не работает на других примерах. Обучение нейросети. После настройки конфигурации сети следует выбрать алгоритм ее обучения. 1. Метод обратного распространения ошибки – итеративный градиентный алгоритм обучения, который используется с целью минимизации среднеквадратичного отклонения текущих значений выходов сети от требуемых. Одним из важнейших свойств алгоритма обратного распространения ошибки является высокая устойчивость, а, следовательно, надежность. Хотя нейронные сети, использующие алгоритм обратного распространения, являясь мощным инструментом поиска закономерностей, прогнозирования и качественного анализа, получили широкое распространение, им свойственны некоторые недостатки. К ним относится невысокая скорость сходимости (большое число требуемых итераций), что делает процесс обучения слишком долгим, и поэтому данный алгоритм оказывается неприменимым для широкого круга задач, требующих быстрого решения. Другие алгоритмы обучения нейросетей хотя и работают быстрее, в большинстве случаев обладают меньшей устойчивостью. 2. Метод Resilent Propogation (Rprop) – эластичное распространение. Алгоритм использует так называемое «обучение по эпохам», когда коррекция весов происходит после предъявления сети всех примеров из обучающей выборки. Преимущество данного метода заключается в том, что он обеспечивает сходимость, а, следовательно, и обучение сети в 4-5 раз быстрее, чем алгоритм обратного распространения. Теперь все готово к процессу обучения сети. В начале все веса нейросети инициализируются случайными значениями. После обучения эти веса принимают определенные значения. Обучение может с большой долей вероятности считаться успешным, если процент распознанных примеров на обучающем и тестовом множествах достаточно велик (близок к 100%). Пример. Рассмотрим пример построения системы оценки кредитоспособности физического лица. Предположим, что эксперты определили основные факторы, определяющие кредитоспособность. Ими оказались: возраст, образование, площадь квартиры, наличие автомобиля, длительность проживания в данном регионе. В организации была накоплена статистика возвратов или невозвратов взятых кредитов. Эта статистика представлена таблицей. Это обучающая выборка. Теперь необходимо нормализовать поля. Поля «Сумма кредита», «Возраст», «Площадь квартиры» и «Длительность проживания» – непрерывные значения, которые преобразуем к интервалу [–1..1]. Образование представлено тремя уникальными значениями, которые можно сравнивать на большее или меньшее, а точнее лучшее или худшее, т.е. образование можно упорядочить так: среднее, специальное, высшее. Значения поля с наличием автомобиля упорядочить нельзя. Его нужно преобразовать к битовой маске. Для кодирования трех значений требуется два бита. Следовательно, это поле будет разбито на два. На этом нормализация закончена. Обучающую выборку разобьем на обучающее и тестовое множества так, как программа предлагает это сделать по умолчанию, т.е. в обучающее множество попадут случайные 95 процентов записей, а остальные 5 процентов – в тестовое. Конфигурация сети будет такой: во входном слое – 7 нейронов, то есть по одному нейрону на один вход (в обучающей выборке 6 столбцов, но столбец «Автомобиль» представлен битовой маской из двух бит, для каждого из которых создан новый вход). Сделаем один скрытый слой с двумя нейронами. В выходном слое будет один нейрон, на выходе которого будет решение о выдаче кредита. Выберем алгоритм обучения сети Resilient Propagation с настройками по умолчанию. Условие окончания обучения оставим без изменения. Обученную таким образом нейросеть можно использовать для принятия решения о выдаче кредита физическому лицу. Это можно сделать, применяя анализ «что-если». Для его включения нужно выбрать визуализатор «Что-если». Тогда откроется форма, представленная на рисунке. После изменения в этой таблице входных полей система сама принимает решение о выдаче кредита и в поле «Давать кредит» проставляет либо «Да», либо «Нет». Столбцы «Минимум» и «Максимум» определяют диапазон значений, на которых обучалась нейросеть. Следует придерживаться этих ограничений, хотя и возможно взять значения немного выходящие за границы диапазона. Кроме такой таблицы анализ «что-если» содержит диаграмму, на которой отображается зависимость выходного поля от одного из входных полей при фиксированных значениях остальных полей. Например, требуется узнать, на какую сумму кредита может рассчитывать человек, обладающий определенными характеристиками. Это можно определить по диаграмме. То есть, человек в возрасте 37 лет со специальным образованием, имеющий квартиру площадью 37 кв. м, отечественный автомобиль и проживающий в данной местности 22 года может рассчитывать на сумму кредита не больше 20000. Качество построенной модели можно определить по таблице сопряженности, которая является одним из визуализаторов. 3. Линейная регрессия В результате работы данного компонента строится линейная модель данных. Применяется следующий алгоритм построения модели. Пусть имеется набор входных значений Xi, где i=1...n, т.е {X1,X2,...,Xn}. Тогда можно указать такой набор выходных значений Yj (j=1..m), который будет соответствовать линейной комбинации входных значений с коэффициентами аi (i=1...n): [1,X1,X2,...,Xn] [a0,a1,a2,...,an] = [Y1,Y2,...,Ym] Если для простоты предположить, что выходное значение одно, то можно записать a0+X1a1+X2a2+...+Xnan=Y. Таким образом, задача сводится к подбору коэффициентов ai. Подбор производится путем итеративного обучения модели, когда на входные поля подается обучающий набор данных, а на выход - целевое значение Y. Целью обучения является получение такого набора коэффициентов линейного преобразования ai, при котором ошибка рассогласования реального Y и рассчитанного Y' значений выходов будет минимальной. Линейная регрессия может быть получена с помощью нейросетей. Для этого нужно создать нейросеть с одним внутренним слоем, состоящим из одного нейрона и с линейной функцией активации. С помощью линейной регрессии модель может быть построена в несколько раз быстрее, поэтому ее эффективней применять на больших наборах данных. Однако нужно помнить, что она предназначена для поиска линейных зависимостей в данных. Если же зависимости нелинейные, то модель с использованием линейной регрессии может быть не построена вообще. Это будет сразу видно на диаграмме рассеяния, т.к. прогнозные значения величины будут сильно разбросаны относительно действительных значений. В этом случае нужно использовать более мощные алгоритмы, например, нейронные сети. Подготовка и настройка обучающей выборки, настройка назначений полей и их нормализация производятся так же, как и для нейронных сетей. Пример. Есть данные о продажах, представленные таблицей. Пусть, например, необходимо составить прогноз объемов продаж на следующий месяц, основываясь на продажах за три предыдущих месяца. Для этого преобразуем таблицу к скользящему окну. Входными полями у модели являются X-3, X-2, X-1, а выходным – X. Способ разбиения множеств оставим по умолчанию и перейдем сразу к построению модели. Запустим процесс построения модели. Для оценки качества построенной модели воспользуемся диаграммой рассеяния. Судя по диаграмме, разброс между эталонными значениями выходного поля и значениями, рассчитанными моделью, достаточно невелик. Из этого можно сделать следующий вывод. Временной ряд хорошо укладывается в линейную модель и, следовательно, на основании этой модели можно строить прогноз на будущие периоды времени. 4. Прогнозирование Прогнозирование позволяет получать предсказание значений временного ряда на число отсчетов, соответствующее заданному горизонту прогнозирования. Алгоритм прогнозирования работает следующим образом. Пусть в результате преобразования методом скользящего окна была получена последовательность временных отсчетов: X(-n), ..., X(-2), X(-1), X где X – текущее значение. Прогноз на X(+1) строится на основании построенной модели. Чтобы построить прогноз для значения X(+2), нужно сдвинуть всю последовательность на один отсчет влево, чтобы ранее сделанный прогноз X(+1) тоже вошел в число исходных значений. Затем снова будет запущен алгоритм расчета прогнозируемого значения и X(+2) будет рассчитан с учетом X(+1) и так далее в соответствии с заданным горизонтом прогноза. Для настройки алгоритма прогнозирования необходимо задать горизонт прогноза, а также поля таблицы, которые необходимо подавать на вход модели для построения прогноза (для вычисления выходного поля модели). Пример. Продолжим предыдущий пример. На основании построенной модели временного ряда спрогнозируем продажи на следующий месяц. Для этого на входы модели необходимо подать значения о продажах за 3 месяца – 01.04.2004, 01.05.2005, 01.06.2004. А это есть поля X-2, X-1 и X. После применения алгоритма прогноза будет получена таблица. Первый день месяца X-3 X-2 X-1 X Шаг прогноза … … … … … 01.04.2004 1000 1160 1210 1130 01.05.2004 1160 1210 1130 1250 01.06.2004 1210 1130 1250 1300 01.07.2004 1130 1250 1300 1400 1 Столбец X показывает историю продаж, включая спрогнозированное значение на следующий месяц. Для получения прогнозного значения 1400 на вход модели были поданы значения: 1130, 1250, 1300. Если задать горизонт прогноза 2, то для получения значения на второй шаг прогноза будут использоваться значения: 1250, 1300, 1400, то есть в расчете новой величины будет участвовать прогнозное значение, полученное на предыдущем шаге и так далее на любое число шагов прогноза. В связи с тем, что для получения прогноза на большое число шагов используются не реальные данные, а вычисленные моделью, ошибка такого прогноза может быть очень велика. Поэтому при построении прогноза не следует заглядывать слишком далеко вперед, так как с увеличением погрешности ценность полученного прогноза очень быстро падает.