CLUSTERED BY FEATURE LINEAR REGRESSION ON DATA WITH REAL VALUE

Resumo

The authors offer a linear regression modification, based on preset clustering by char. value. Approbation of this method with some real-valued features databases showed highly better results, in comparison with the classical linear regression. The fuzzy sets method was applied to generate discrete features from the real ones.

Texto integral

Задача восстановления данных может считаться одной из наиболее сложных задач в области анализа данных, она требует тщательного исследования исходного набора данных и методов, подходящих для анализа. Следует отметить, что эта задача заведомо некорректна и не может быть решена без дополнительных предположений. В работе речь идет о числовых данных. Существует множество методов анализа и восстановления данных. Они основаны на различных «технологиях»: деревья регрессии [1; 2], анализ и преобразование (или отбор) входных признаков [3; 4], кластеризация данных [5-7] и др. Выбор метода для решения конкретной задачи зависит прежде всего от характера обрабатываемых данных. Большое распространение получили линейные методы анализа и восстановления данных. Их широкое применение обусловлено тем, что большое количество реальных процессов в экономике и бизнесе можно с достаточной точностью описать линейными моделями. Можно выделить два типа восстановления данных: классификация и прогнозирование. Под классификацией будем понимать отнесение объектов (наблюдений, событий) к одному из заранее известных классов. Прогнозирование - это установление функциональной зависимости между зависимыми и независимыми переменными. В данной работе зависимые переменные будем называть «выходными» или «целевыми» признаками, а независимые - «входными». Заметим, что не все методы, пригодные для классификации, способны решать задачу прогнозирования. Однако результаты прогнозирования всегда можно интерпретировать с позиции классификации. В работе решается задача прогнозирования для трех различных выборок данных. Несмотря на то, что эти выборки относятся к разным областям, у них есть общие черты: малое количество признаков, очень большое количество объектов и непрерывные шкалы признаков. Рассматривается один из основных линейных методов прогнозирования - линейная регрессия. А также описывается модификация линейной регрессии, основанная на кластеризации данных, которая значительно увеличивает точность прогноза. Существует множество методов кусочной линейной регрессии (или линейной регрессии с предварительной кластеризацией) - регрессии, в которой обучающее множество разбивается на подмножества, для каждого из которых строится своя линейная регрессия [5-8]. Эти методы различаются способом деления обучающего множества на подмножества. Существуют два разных подхода - разделение на непе-ресекающиеся подмножества и разделение на перекрывающиеся подмножества. Для сравнения из всего многообразия методов было отобрано несколько. Одним из наиболее известных методов разбиения обучающего множества на непересекающиеся подмножества является метод, основанный на методе кластеризации k-Means. Строится к классов, для каждого из которых описываются свое уравнение линейной регрессии. Метод двойной регрессии является еще одним ярким представителем методов, разбивающих обучающее множество на непересекающиеся подмножества. 71 Математика, механика, информатика Его ключевое отличие от метода, основанного на k-Means, состоит в том, что разбиваются множества на подмножества не на основе расположения точек в исходном пространстве, а на основе вычисления некоторой функции. Суть метода состоит в следующем. На всем обучающем множестве строится линейная регрессия. Далее все точки упорядочиваются по возрастанию вычисленного значения целевого признака. Множество вычисленных значений целевого признака разбивается на k интервалов. На основе точек обучающего множества, попавших в каждый из интервалов, в каждом интервале строится своя линейная регрессия. Крайним случаем по степени дробления обучающего множества является метод локальной линейной регрессии, основанный на kNN (k ближайших соседей, см., например, [9; 10]). Идея метода состоит в том, что для каждой проверяемой точки определяются k ближайших к ней точек. На основе отобранных точек строится уравнение регрессии, которое используется для вычисления значения целевого признака в проверяемой точке. Пусть для некоторой задачи имеется таблица данных A размерностью N*M, где N - число объектов наблюдения, M - число признаков объектов (рис. 1). Таблица данных A не содержит пробелов. Признак 1 Признак 2 Признак М Объект 1 Объект 2 Объект N Рис. 1. Структура таблицы «объект - признак» Строка таблицы является формализованным описанием некоторого объекта наблюдения. Каждый столбец таблицы - это некоторое свойство описываемых объектов. Существуют различные типы шкал признаков [11; 12]. В данной работе рассматриваются задачи с признаками в непрерывной и номинальной шкалах. Необходимо определить линейную функциональную зависимость одних признаков (целевых или выходных) от других (входных). Причем для каждого выходного признака осуществляется поиск зависимости только от входных признаков. Пусть имеется объект O для этой же задачи с полностью известными входными и выходными признаками. Требуется предоставить прогноз значений выходных признаков объекта О, используя таблицу A и входные признаки объекта O, а также оценить, насколько предложенные прогнозы отличаются от истинных значений. Линейная регрессия. Одним из самых популярных и, в некотором смысле, естественным линейным методом прогнозирования является линейная регрессия. Линейная регрессия - это метод, позволяющий аппроксимировать зависимость между несколькими входными и одной выходной переменной. Модель линейной регрессии описывается гиперплоскостью. Запишем уравнение регрессии [13]: M Y _fbkxk + b0 . k _1 Коэффициенты уравнения линейной регрессии подбираются так, чтобы минимизировать сумму квадратов отклонения реальных точек данных от этой гиперплоскости вдоль оси целевого (вычисляемого) признака. Найдем коэффициенты X = {b0, b1, ..., bN} из условия минимума функции невязки: P(b) _1 f (Y - Y )2 ^ min, 2 i _1 где Yi - вычисленное значение точки xi; Yi - истинное значение точки xi. Пусть целевой вектор имеет вид O' :{o1 ,...,o'N} и содержит пробел oi _ @ . Тогда m oj _f bkok + b0. k _1 k * j что и будет его прогнознам значением. Линейная регрессия с предварительной кластеризацией. Чаще всего при анализе данных они представляются как облако точек в M-мерном пространстве (M - количество признаков), а их координаты задаются значениями соответствующего признака. При таком подходе естественной является кластеризация на основе взаимного расположения точек-объектов в пространстве. При этом кластеры формируются на основе сгущений точек. Однако в данной работе предлагается принципиально другая процедура выделения кластеров [8]. Для выделения кластеров необходимо в первую очередь выбрать признаки, и по их значениям разделить выборку на кластеры - в один кластер попадут объекты с одинаковым значением данного признака. Такие признаки должны обладать следующими свойствами: - дискретностью значений; - небольшим количеством значений. Эти требования соотносятся с тем, что кластеров, полученных по значениям одного признака, не должно быть слишком много, иначе количество объектов, им принадлежащих, будет мало, что может негативно сказаться на точности прогноза. Полученные кластеры пересекаются. Иными словами, объект может входить в несколько кластеров одновременно. После того, как для текущего объекта определены кластеры, которым он принадлежит, требуется найти «лучший» из них - тот, по которому далее будет проводиться восстановление данных. Для этого на каждом кластере проводится тест обучающего множества и фиксируется ошибка прогнозирования выходного признака. Оценкой кластера является относительная ошибка прогнозирования его выходного признака: 72 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева ep = N Z ak k=1 •100%, (1) где аг - истинное значение целевого признака г-го объекта, рг - прогнозное значение целевого признака г-го объекта. Переход к бинарным признакам. Для перехода от непрерывного признака к набору бинарных признаков применялся подход, основанный на нечеткой классификации и нечетких множествах [5]. Для подбора оптимального числа нечетких классов, нечеткая классификация проводилась на разное число классов. Определим требования к нечеткой классификации. Пусть необходимо построить k нечетких классов. Дан непрерывный признак X, принимающий n значений. Построим нечеткий классификатор этого признака на k нечетких классов. Носителем г-го нечеткого класса будем называть интервал Мг = [а^-^] (рис. 2). Сами нечеткие множества будем обозначать так же, как их носитель. При этом объект со значением признака X равным х, принадлежит г-му нечеткому классу, если хеМг. Назовем нечеткие множества М и Mj соседними, если их номера отличаются на единицу. 100 ! 110 ! 010 ! 011 ! 001 а0 al а2 аЗ а4 а5 Рис. 2. Переход к бинарным признакам Определим требования к нечетким классам: 1. Нечеткие классы должны покрывать все множе- ство X: X ç Q Мг . г=1 2. Носители соседних нечетких классов должны пересекаться: Mt П Мг+1 ф 0. 3. Носители несоседних нечетких классов не пересекаются: Мг ПMj = 0, V(г, j) : |i-j| > 1. 4. Носитель каждого нечеткого множества имеет фрагмент, не принадлежащий соседним множествам: ( Мг П Мм ) U ( Мг П Мг +1 )Ф Мг . 5. Носители всех нечетких классов должны содержать приблизительно одинаковое число точек множества X. Для построения носителей нечетких множеств, удовлетворяющих предъявленным требованиям, проведем следующую процедуру. 1. Упорядочим значения признака X по возрастанию значений, получим множество X = {хг, г = 1, ..., n, хг < Х/+1 }. 2. Определим 2k точек z, разбивающих множество X на подмножества равной мощности. Мощность каждого подмножества будет равна n r =-. 2k -1 Значения точек zt определим следующим образом: z1 = х1; z2k = xn; z = (г-1)r 2(г-1)r+1,г = 2,---,2k-1. 3. Дополним множество точек z^ двумя крайними точками, для учета возможного появления значений, выходящих за границы интервала: z0 = 2z1 - z2 и z2k+1 = 2z2k - z2k-1. 4. Определим границы интервала носителя каждого нечеткого множества: аг z2--2. Тестирование проводилось на трех базах данных: «Ископаемый уголь», «Шаттл» [14], «Fried» [15] (табл. 1). База данных «Ископаемый уголь» предоставлена компанией «Weatherford Laboratories». Она описывает зависимость химического состава образцов ископаемого угля от их физических характеристик. Сравниваются методы: - классическая линейная регрессия; - линейная регрессия с кластеризацией по значениям признаков; - линейная регрессия с кластеризацией методом k-Means; - линейная регрессия с кластеризацией методом kNN; - двойная линейная регрессия. Оценивается влияние наличия порожденных бинарных признаков среди входных признаков выборки. Основной критерий для сравнения методов - относительная ошибка прогнозирования (1). Таблица 1 Тестовые базы данных База данных Количество объектов Количество признаков Количество выходных признаков Ископаемый уголь 6 504 12 9 Шаттл 58 000 10 1 Fried 40 768 11 1 73 Математика, механика, информатика Выходной признак базы данных «Шаттл» имеет дискретную шкалу и всего семь различных значений. Поэтому для нее помимо ошибки прогнозирования рассчитывается и ошибка классификации. Ошибка классификации - это доля «промахов» при определении классов значений. Считается, что класс значения некоторого признака определен верно, если предсказанное значение ближе к истинному значению, чем к любому другому значению из множества возможных дискретных значений этого признака. Обозначим множество значений признака: F:{/1...f}; истинное значение целевого признака i-го объекта: aieF; прогнозное значение целевого признака i-го объекта: p. Определим ошибку классификации: 1 N - f N \ zi i_1 У ■100%, z _ j0, при I pt - ai I < I fj - ai I, Vfj * ai, [1, в остальных случаях. Тестирование методов осуществляется на тестовом множестве: выборка делится на две части - тестовое множество и обучающее множество. Какой объект попадет в тестовое множество, а какой - в обучающее, определялось случайным образом. Для базы данных «Шаттл» выборка была разделена изначально. По обучающему множеству строится модель данных и с помощью этой модели рассчитываются прогнозы для каждого объекта тестового множества. В данной работе тестовое множество содержит 25 % объектов выборки, а обучающее множество - 75 %. Поскольку базы данных имеют довольно большое количество объектов, нет необходимости в многократном повторении экспериментов с различными разбиениями. Исследуется зависимость качества прогноза линейной регрессии с кластеризацией по признаку от количества порождаемых бинарных признаков. Каждый входной признак выборки порождает 3, 5, 7 или 9 бинарных признаков. Действительные и бинарные признаки используются совместно. Также оценивается влияние количества порожденных бинарных признаков. Результаты вычислительных экспериментов представлены в табл. 2, 3. На базе данных «Ископаемый уголь» предложенные модификации линейной регрессии оказывают положительное влияние на результаты прогнозирования для всех целевых признаков выборки. Для одних признаков это влияние выражено сильнее (влажность, кислород), для других - слабее (связанный углерод, зола). В целом наилучший результат получен при использовании линейной регрессии с кластеризацией по признаку. На базе данных «Шаттл» предложенные модификации очень эффективны: добавление бинарных признаков снизило ошибку классификации с 34,95 до 7,41 %. А применение кластеризации позволило снизить ошибку классификации практически до нуля - достигнута точность 99,87 %. По ошибке прогнозирования наибольшая точность достигнута при использовании семи нечетких классов для линейной регрессии с кластеризацией, и девяти - для классической линейной регрессии. Если рассматривать все результаты в целом, то линейная регрессия с кластеризацией по значению признака чаще всего (хоть и не всегда) показывает наилучший результат среди рассмотренных методов. Гибридные или комбинированные методы зачастую оказываются алгоритмически сложнее базовых. Поэтому их применение оправдано только при существенном повышении точности результатов. Мера существенности зависит от задачи. Например, для постановки медицинского диагноза прирост точности прогноза всего на 1-2 % имеет большое значение. База данных «Ископаемый уголь». Ошибка прогнозирования (%) Таблица 2 Влажность Летучее вещество Связанный углерод Зола Водо род Угле род Азот Кисло род Сера ЛР 68,65 13,13 12,43 25,86 2,64 12,29 19,75 41,88 62,44 ЛР{3} 51,08 10,75 11,05 23,94 2,01 10,11 17,26 31,97 57,81 ЛР{5} 48,03 10,32 10,94 23,89 1,88 9,65 16,48 29,82 57,90 ЛР{7} 44,50 9,78 10,78 23,71 1,74 9,34 15,87 28,11 57,13 ЛР{9} 44,27 9,69 10,87 23,94 1,73 9,40 16,10 28,25 57,62 ЛРК{3} 48,17 9,68 10,20 23,70 1,39 9,10 16,25 29,97 55,27 ЛРК{5} 39,78 9,24 10,12 23,54 1,43 8,90 15,58 26,61 54,17 ЛРК{7} 39,14 9,29 10,14 23,13 1,42 8,75 15,35 26,76 54,40 ЛРК{9} 41,24 9,28 10,01 23,26 1,42 8,76 15,33 27,00 54,29 Двойная ЛР* 38,38 10,53 11,17 25,36 1,44 10,64 18,72 29,31 62,54 k-Means ЛР* 58,24 11,98 11,02 23,68 2,13 10,78 18,28 35,60 55,13 kNN ЛР* 45,94 10,21 10,32 22,72 1,66 9,47 16,52 30,00 53,86 Примечание: *при оптимальном количестве кластеров (объектов в кластере для kNN); ЛР - классическая линейная регрессия; ЛРК - линейная регрессия с кластеризацией по признаку; двойная ЛР - двойная линейная регрессия; k-Means ЛР - линейная регрессия с кластеризацией методом k-Means; kNN ЛР - линейная регрессия с кластеризацией методом kNN; в фигурных скобках обозначено количество бинарных признаков, порождаемых из одного действительного. 74 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Таблица 3 Базы данных «Шаттл», «Fried». Ошибки прогнозирования (%) и классификации (%) База данных «Шаттл» База данных «Fried» Ошибка прогнозирования, % Ошибка классификации, % Ошибка прогнозирования, % ЛР 29,58 34,95 14,21 ЛР{3} 17,96 16,32 10,27 ЛР{5} 16,31 11,32 9,86 ЛР{7} 12,50 8,92 9,80 ЛР{9} 11,34 7,41 9,73 ЛРК{3} 4,88 4,32 9,07 ЛРК{5} 2,78 2,33 7,68 ЛРК{7} 0,79 0,30 7,28 ЛРК{9} 0,92 0,13 7,08 Двойная ЛР* 9,64 9,63 13,55 k-Means ЛР* 3,80 3,60 9,99 kNN ЛР* 0,58 0,55 7,67 Примечание: * при оптимальном количестве кластеров (объектов в кластере для kNN). В данной работе были предложены модификации линейной регрессии, основанные на порождении бинарных признаков и кластеризации. Рассмотренные методы протестированы на 3-х различных базах данных. На всех базах предварительная кластеризация по значениям признаков повысила результаты линейной регрессии на каждом целевом признаке. На одних признаках произошло значительное повышение точности прогноза (до 30 %), на других - почти не заметное. Предложена и успешно применена технология порождения бинарных признаков из действительных признаков с непрерывной шкалой, основанная на теории нечетких множеств. Совместное использование исходных действительных и порожденных бинарных признаков позволило существенно повысить качество прогноза линейной регрессии. А применение кластеризации данных по бинарным признакам дало еще больший прирост точности. Результаты прогнозирования чувствительны к количеству порожденных бинарных признаков. Однако последовательное увеличение количества бинарных признаков дает все меньший прирост точности, а для метода, использующего кластеризацию по значению признака - постепенно приводит к ее падению.