Файл: Задача бинарной классификации.pdf

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

1. Постановка задачи

1.1 Основные понятия. Задача бинарной классификации

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

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

- 1. Оценка качества алгоритмов

Для субъективной оценки качества работы обученных алгоритмов используют различные функционалы. В реальной работе будет использована метрика AUC (площадь под ROC-кривой). Предположим, что есть истинный вектор меток y для n объектов и вектор y˜ предсказанных степеней принадлежности классу 1.

Pn Pn I [yi < yj] * I[y˜i < y˜j]

i=1 j=1

AUC (y, y) =͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟͟ ∈ [0,1].

(Pn I[yi = 0]) * (Pn I[yi – 1])

i=1 i=1

Чем ближе значение AUC к единице, тем выше качество алгоритма.

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

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

1.2 Постановка задач с категориальными признаками

Многие классические подходы машинного обучения предполагают, что все признаки Xj R. Однако в задачах признаки могут принимать значения из множеств, не совпадающих с множествами вещественных чисел. Признаки могут принимать значения из конечного неупорядоченного множества. К примеру, это может быть признак сайт со значениями из множества {ВКонтакте, Фейсбук, Твиттер, Инстаграм и др…}. Такие признаки будут называться категориальными.

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

ВКонтакте → 1

Фейсбук → 2

Твиттер → 3

Инстраграм → 4

…

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

2. Примеры задач с категориальными признаками

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

Большая группа задач с категориальными признаками являются задачами, связанными с коллаборативной фильтрацией. В таких задачах каждый объект Оценка пользователя, представлен двумя категориальными признаками: Пользователь и Предмет. По обучающей выборке оценок пользователей необходимо научиться предсказывать оценки для еще неизвестных пар (Пользователь, Предмет). Основным толчком для изучения подобных задач стало трехлетнее соревнование Netflix’a.

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

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

3. Используемые методы

3.1 Группировка значений признаков

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

3.2 Метод q ближайших соседей

Предположим, некий признак принимает q значений {a1, … , aq}. Тогда для каждого объекта Хi можно заменить признак Xj на q-бинарные признаки следующим образом:

Z^ak= I[X^j= a_k], k ∈ {1, ..., q},

Где I[A] индикатор события А, т.е.

I[A] = 1, если А верно,

0, если А неверно.

Такой способ называется dummy-кодированием. Если закодировать каждый признак исходной матрицы таким методом, то к полученным описаниям объектов Z1, … , Zn можно применять многие классические алгоритмы для работы с вещественными признаками.

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

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

3.3 Произвольная перенумерация значений

Как уже было написано в разделе 2.2, обыкновенная нумерация значений признаков маловероятно приведет к качественному результату из-за того, что алгоритмы начинают учитывать не имеющую смысла упорядоченность значений признаков. Такие алгоритмы являются очень нестабильными к различным нумерациям значений признаков и показывают низкой уровень качества по отдельности. Однако, как показал Leo Braiman, схожие неустойчивые, но несмещенные алгоритмы можно максимально эффективно соединить в композиции, с помощью техники bagging. Таким образом можно обучать независимые слабые алгоритмы с произвольно пронумерованными признаками и в качестве финального предсказания брать усредненный ответ по всем ним. Такой подход позволяет увеличить качество композиции и сэкономить потраченное время в сравнении с каждым взятым отдельным базовым алгоритмом.

3.4 Наивный байесовский классификатор

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

argymax p(y|X) = argymax p(y) Y p(Xj|y)

j=1

Для удобства расчетов было сделано следующее преобразование:

m m

Argymaxp(y) Y p(y = 1 Xj) |Y| p(y = 1cXj).

j=1 j=1

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

Pn I[yi = y] * I[Xj = Xj]

P(y|Xj)= ____________________

i=1

Pn I[Xj = Xj]

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

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

Также можно использовать некий внешний мета-алгоритм f, который бы выражал искомую вероятность не просто произведением вероятностей, а более сложным аппроксиматором:

Prediction = f(p(y|x1), …, p(y|x1)).

В качестве такого мета-алгоритма можно использовать любой классификатор или регрессор в зависимости от задачи. Например, если обучать линейный мета-алгоритм с весами (w1, …, wm) на логарифмах факторизованных вероятностей, то получим приближение:

prediction = p^wj(y|x^j).

j=1

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

3.5 Аппроксимация целевых меток с помощью взвешенных разреженных разложений матриц

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

Рассмотрим некоторую пару признаков j1 и j2, которые принимают уникальные значения {ak}^q1и {bl}^q2, соответственно.

^{k=1 l=1}

Тогда можно составить матрицу F размера q1 * q2 оценок значения метки для соответствующей значений пары признаков j1 и j2. Если в обучающей выборке не встречались прецеденты для некоторой пары значений, то значение матрицы считается неизвестным. Оценкой значения метки может служить, эмпирическое математическое ожидание значение метки.

Назовем латентным вектором значения ak признака j1 k-ю строчку матрицы G и H латентным вектором значения bl признака j2 1-й столбец матрицы Н. Вместо перекодировки исходных значений пар признаков восстановленными с помощью матричного разложения значений целевых меток можно перекодировать соответствующие латентные вектора, полученными из матриц G и H. При решении таким способом каждый признак будет перекодирован новыми 2r признаками. Такое решение может позволить внешним мета-алгоритмам находить более глубокие закономерности в данных.

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

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