«Машинное обучение»

Лабораторная работа № 1 «Алгоритмы заполнения пропущенных значений в таблицах данных»

Цель работы: ознакомиться с основными алгоритмами заполнения пропущенных значений в эмпирических таблицах данных. Исследовать, программно реализовать и оценить работу алгоритмов многомерной линейной регрессии, среднего арифметического и ЕМ-алгоритма.

Ход работы

1. Ознакомиться с основными алгоритмами заполнения пропущенных значений.

2. В соответствии с таблицей 1 получить задание на лабораторную работу.

Таблица 1 – Варианты заданий

Номер бригады	Выборка данных	Номер бригады	Выборка данных
1	auto-mpg	6	water-treatment
2	glass	7	waveform
3	housing	8	wine
4	liver-disorders	9	hayes-roth
5	pima-indians-diabetes	10	ionosphere

3. Изучить и программно реализовать (любая среда разработки) алгоритмы многомерной линейной регрессии, среднего арифметического и ЕМ-алгоритм.

4. Занести в таблицу табл.2 результаты экспериментальных исследований и сравнить полученные результаты.

Таблица 2 – Оценка работы алгоритмов заполнения пропущенных значений

Алгоритм	Количество пропущенных значений (% от всей выборки данных)
	10%	20%	40%	60%
Среднее значение по атрибуту	Значение погрешности восстановления данных
ЕМ-алгоритм
Регрессионное моделирование

5. Составить отчет по лабораторной работе

Содержание отчета

1. Титульный лист.

2. Цель работы.

3. Ход работы (код программы (основные модули), таблицы с результатами экспериментов, оценка качества работы алгоритмов в зависимости от объема пропущенных значений).

4. Выводы по работе.

Контрольные вопросы

1. На какие группы можно разделить алгоритмы заполнения пропущенных значений? Дайте краткую характеристику каждой из них.

2. Охарактеризуйте простую группу алгоритмов заполнения пропусков. Метод k ближайших соседей.

3. Как выполняется заполнение пропусков с помощью регрессионных алгоритмов?

4. Охарактеризуйте алгоритм Zet, перечислите его достоинства и недостатки.

5. Охарактеризуйте ЕМ-алгоритм, перечислите его достоинства и недостатки.

Теоретические исследования

Алгоритмы заполнения пропущенных значений разрабатываются для эмпирических таблиц типа «объект-свойство». Таблицы типа «объект-свойство» – это численные таблицы, в которых в строках перечислены объекты (например, студенты), а в столбцах – их свойства (атрибуты, например, успеваемость, рост, вес). Эти таблицы экспериментальных данных могут содержать пропуски.

Задача алгоритмов заполнения пропущенных значений заключается в заполнении пропусков в таблицах наиболее правдоподобными значениями с наименьшей погрешностью. Можно выделить 4 основные группы методов заполнения пропусков [1, 3]:

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

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

Глобальные алгоритмы – в оценивании (предсказании) каждого пропущенного значения участвуют все объекты рассматриваемой совокупности: метод Бартлета, ЕМ-алгоритмы и Resampling.

Локальные алгоритмы – в оценивании (предсказании) каждого пропущенного значения участвуют полные наблюдения, находящиеся в некоторой окрестности предсказываемого объекта. К данной группе относятся алгоритмы Zet и Zet Braid [1, 2].

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

Рисунок 1.1 – Алгоримы заполнения пропущенных значений в таблицах данных

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

1. Простые алгоритмы заполнения пропусков в таблицах «объект-свойство»

Наиболее распространёнными алгоритмами заполнения таблиц являются методы интеллектуального анализа данных (Data Mining).

1.1.1 Метод заполнения средним арифметическим.

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

Таким образом, неизвестное значение а_ij в матрице A размера N×M предсказывается по формуле:

_(1.1)

1.1.2 Метод k ближайших соседей (k-nearest neighbor algorithm(k-NN))

K-NN – метод автоматической классификации объектов. Основным принципом является то, что объект присваивается тому классу, который является наиболее распространённым среди соседей данного элемента.

Соседи берутся, исходя из множества объектов, классы которых уже известны, и, исходя из ключевого для данного метода значения k высчитывается, какой класс наиболее многочислен среди них. В основе алгоритма k ближайших соседей лежит предположение, что если объекты близки по значениям n-1 свойств, то они близки по значению n-ого свойства.

Заполнение пропусков в таблице данных методом k ближайших соседей выглядит следующим образом: вначале среди всех строчек таблицы находят k строчек, наиболее «похожих» на строчку, содержащую пробел. В качестве меры «похожести» строчек (объектов) фигурирует декартово расстояние между строчками в пространстве столбцов (свойств). Чем меньше декартово расстояние между объектами в пространстве свойств, тем более они «похожи» друг на друга.

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

_{, (1.2)}

где С_l – вес (компетентность) l-го ближайшего соседа, обратно пропорциональный декартовому расстоянию r_lj между l-той и j-той строкой

_{. (1.3)}

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

Рисунок 1.2 – Схематичное представление работы алгоритма k-NN

Главной особенностью, выделяющей метод k-NN среди остальных, является отсутствие у этого алгоритма стадии обучения.

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

Главный недостаток метода k-ближайших соседей заключается в длительности времени работы на этапе классификации.

1.1.3 Регрессионное моделирование пропусков

Один из самых популярных в настоящее время методов – многомерная линейная регрессия с автоматическим выбором независимых параметров – основан на применении алгоритма пошагового выбора независимых переменных. Первоначально список включенных в регрессионную модель независимых переменных пуст. Сначала рассматриваются все линейные модели, зависящие только от одной переменной, и для каждой из них вычисляется стандартная ошибка и значение F-меры. Выбирается независимая переменная, имеющая минимальную ошибку, и включается в список. Далее аналогичным образом отбирается вторая переменная. Рассматриваются все возможные такие двумерные линейные модели, первая из переменных которой совпадает с уже включенной в список переменной, и среди них выбирается наилучшая модель. Вычисляется стандартная ошибка и достоверность определения регрессионных коэффициентов или значения F-мер всех входящих в модель коэффициентов, и в список добавляется вторая переменная, наиболее значимо влияющая на целевую переменную. И так на каждом шаге прибавляется новая независимая переменная. Этот процесс продолжается пока достоверность определения регрессионного коэффициента новой независимой переменной, добавляемой в список, не становится меньше некоторого заданного порогового значения. Когда в список независимых переменных добавляется новый элемент, может перестать выполняться критерий для величины F-меры какой-нибудь уже включенной в список переменной. В такой ситуации удаляется из списка старая, не удовлетворяющая критерий переменная, и добавляется новая, если полученная регрессионная модель дает уменьшение стандартной ошибки по сравнению с предыдущей, в этом случае продолжается. Окончание процесса добавления новых переменных означает, что все переменные, значимо влияющие на зависимую переменную, уже включены в список (если, конечно, список не остался пустым).

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

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

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

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

Пусть задана N×nтаблица «объект-свойство» вида

	1	…	p	…	j	…	n
1	x11	…	x1p	…	x1j	…	x1n
…	…	…	…	…	…	…	…
i	xi1	…	xip	…	xij	…	xin
…	…	…	…	…	…	…	…
k	xk1	…	xkp	…	xkj	…	xkn
…	…	…	…	…	…	…	…
N	xN1	…	xNp	…	xNj	…	xNn

содержащая информацию об N объектах, каждый из которых описывается (1×n) – вектором-строкой признаков, при этом предполагается, что N_G строк могут иметь по одному пропуску, а N_F= N-N_G заполнены полностью. В процессе обработки таблицы необходимо заполнить пропуски так, чтобы восстановленные элементы были бы в некотором смысле «наиболее правдоподобны» или «близки» к априори неизвестным закономерностям, содержащихся в таблице.

Представим таблицу 1 в виде (N×n) – матрицы Х, в которой отсутствует один элемент или в более общем случае отсутствуют N_G элементов. Предполагается, что между столбцамисуществует линейная зависимость, на основании которой и производится восстановление пропуска с помощью регрессии

,(1)

или

,

(2)

где – – вектор параметров, подлежащих определению, вектор-строка признаков k-того объекта без -того элемента и с единицей на первой позиции.

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

,

(3)

где , - символ псевдообращения по Муру-Пенроузу.

Если же пробелы имеются в строках и в разных столбцах, из матрицы исключаются все эти строки и на основании полученной усеченной матрицыраз находятся векторы параметров (3) для всех .

Далее с помощью уравнения (1) или (3) заполняются все пробелы полученными оценками .

Рассмотренный алгоритм представлен на схеме (рис.1.3)

Рисунок 1.3 – Пакетный алгоритм заполнения пробелов

Применимость этого метода ограничивается двумя обстоятельствами. Во-первых, он может вовсе не обнаружить наличия какой-либо зависимости в данных. Подобная ситуация может встретиться в случае сильно нелинейной зависимости – например, если переменная y зависит от квадрата величины x, а величина x распределена в данных примерно симметрично. Во-вторых, этот метод, как и другие регрессионные методы, плохо работает с данными, в которых мало чисел и много дискретных (булевых и категориальных) полей. Поэтому, хотя многомерная линейная регрессия с автоматическим выбором независимых параметров и нашла очень широкое применение в практических исследованиях, это далеко не универсальный метод нахождения зависимостей.

2. Сложные алгоритмы заполнения пропущенных данных

Существуют и более сложные алгоритмы заполнения пропусков. Методы Барлетта и resampling основаны на уравнениях многомерной линейной регрессии. В методе Барлетта пропуску присваивается какое-то начальное значение (например, среднее арифметическое столбца), затем строят уравнение многомерной линейной регрессии с использованием начального значения пропуска, и после анализа этого уравнения предсказывается пробел. Метод resampling является итеративным, в этом методе вместо пропуска подставляется набор значений, и при каждом значении из этого набора строится уравнение многомерной линейной регрессии. Все эти уравнения анализируются, и после анализа выводится итоговое уравнение линейной регрессии, на основе которого и предсказывается пропуск. В настоящее время интенсивно развиваются методы прогнозирования, основанные на оценках максимального правдоподобия (МП-оценках), особенно в рамках нормальных распределений.

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

1. Алгоритм ZET

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

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

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

Третье предположение (гипотеза локальной компетентности) заключается в том, что избыточность носит локальный характер: у каждого объекта есть свое подмножество объектов-аналогов и у каждого свойства есть свое подмножество свойств-аналогов. Если это так, то не имеет смысла привлекать к предсказанию значения некоторого элемента b_ij информацию, содержащуюся в строках, не похожих на i-ю строку, и в столбцах, не похожих на j-й столбец. В предсказаниях должны участвовать только, так называемые "компетентные" строки и столбцы, которые выбираются для каждого предсказываемого элемента отдельно.

Рисунок 1.4 – Гипотезы алгоритма ZET

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

1.3 Глобальные алгоритмы заполнения пропущенных данных

1.3.1 ЕМ-алгоритм

Метод максимизации ожиданий (ЕМ –expectation maximization), в некоторых источниках так же называемый ЕМ-оцениванием, позволяет не только восстанавливать пропущенные значения с использованием двухэтапного итеративного алгоритма, но и оценивать средние значения, ковариационные и корреляционные матрицы для количественных переменных.

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

Этот алгоритм реализуется в 2 этапа, первые буквы названий которых образуют общую аббревиатуру алгоритма. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.

Как правило, ЕМ-алгоритм применяется для решения задач двух типов.

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

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

Этап Е

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

В случае работы с неполными даными на Е-этапе определяется функция условного математического ожидания логарифма полной функции правдоподобия при известном значении целевой перменной Х :

(1)

Когда имеют дело с полным наблюдением, у которого характеристика Х принимает значение x, выражение (1) для вычисления значений функции принимает вид:

После определения этой функции начинается второй этап работы алгоритма – М этап.

Этап М

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

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

Здесь Θ обозначает рассчитанное ожидаемое условное значение, отсутствующей характеристики для некоторого наблюдения [4].

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

 

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

1. Заполнение всех пропусков в таблице по указанному алгоритму. 

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

3. Заполнение пропусков только на базе информации, имеющейся в исходной таблице.

4. Заполнение каждого следующего пропуска с использованием исходной информации и прогнозных значений ранее заполненных пропущенных знаоений.