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

3.6 Стекинг алгоритмов

Метод использования внешнего мета-алгоритма над результатами работы других базовых алгоритмов называется stacking.

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

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

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

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

3.7 Использование частот совместных встречаемости значений признаков для их перекодировки

3.7.1 Перекодировка частотами встречаемости наборов значений

Каждую пару значений признаков j1 и j2 можно перекодировать частотой совместной встречаемости. Такая перекодировка дает возможность учесть генеративную природу данных.

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

3.7.2 Разложение матриц частот

Кроме напрямую посчитанных оценок частот можно использовать и приближения частот, полученные в результате матричных разложений соответствующих матриц. Рассмотрим на примере некоторых признаков j1 и j2, которые принимают уникальные значения {a_k}^q1 и {b_l}^q2, соответственно. Тогда можно составить матрицу F размера q1 * q2. В такой матрице все значения известны – это частоты вхождения соответствующей пары значений признаков в обучающую выборку. Делая разложения матрицы

l=1

k=1

F ≈ GH, G ∈ R^q1xr, H ∈ R^rxq2,

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

Z^j1j2 = (Gj, Hj) ₂

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

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

D₂ (P,Q) = kP – Qk² = X (P_ij – O_ij)

i j

Однако куда более естественный смысл при аппроксимации частот имеет неотрицательное матричное разложение и обобщенная KL-дивергенция) в качестве меры качества разложения:

P_ij

D_KL(P k Q) = X (P_ij* log --- - P_{ij +} Q_ij)

Q

Эти меры сходства являются частным случаем так называемой β-дивергенции:

P_ij^β-1 – Q_ij^β-1 Q_ij ^β

D ^β (P_ij k Q) = X (P_{ij * _______________ = ____}

β – 1 β

Действительно, при β = 1,имеем:

D ^β (P kQ) → D_KL (P k Q)

а при β = 2

D ^β (P k Q) = D₂ (P, Q)

Стоит обратить внимание, что β-дивергенция, как, впрочем, и KL-дивергенция, в общем случае является несимметричной мерой сходства.

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

1. Данные

Для опытов в своей курсовой работе я выбрал два современных набора реальных данных с категориальными признаками. В данном разделе приведен краткий обзор этих наборов.

• • 1. Обзор набора данных

Первый набор данных был опубликован на международном соревновании по анализу данных Amazon.com – Employee Access Challenge, проводимом в 2013 году. Далее в курсовой для краткости этот набор данных будет называть Amazon.

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

Таблица 1. Количество уникальных значений по каждому из признаков в наборе данных Amazon.

​​​​​​​4. Выбор способа тестирования алгоритмов

Для проведения всех экспериментов и более точного сравнения результатов работы различных алгоритмов было принято решение зафиксировать единую конфигурацию тестирования для всех алгоритмов. Использование произвольных разбиений на обучение и контроль (в различных пропорциях) давало большее отклонение оценки качества, нежели кроссвадилация. На рис.1 показан график зависимости оценки качества ее 2σ-доверительный интервал в зависимости от количества фолдов в случае алгоритмов из принципиально разных семейств: логистической регрессии с dummy-кодированием и наивным байесовским классификаторов. В качестве σ² бралась эмпирическая несмещенная оценка дисперсии в каждой точке. В дальнейшем в работе везде будут использоваться несмещенные σ² доверительные интервалы, если не обговорено обратное.

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

_{0.87 0.800}

Logistic Regression

Naive bayes

Logistic Regression Naive bayes

AUC mean

_{0.86 0.795}

_{0.85 0.790}

_{0.84 0.785}

_{0.83 0.780}

_{0.82 0.775}

_{0.81 0.770}

_{2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10}

Рис. 1. Среднее качество предсказания в зависимости фолдов и 2σ-доверительная трубка на данных Amazon.

Рис. 2. Среднее качество предсказания в зависимости фолдов и 2σ-доверительная трубка на данных Movie Lens.

• 1. Movie Lens

4.1 Обзор набора данных

Второй набор данных был опубликован компанией Movie Lens и называется Movie Lens 100K. В дальнейшем буду писать его просто Movie Lens.

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

Необходимо решить задачу бинарной классификации. Всего в выборке 100000 объектов из них классу 1 принадлежат 64% объектов. Каждый объект описается шестью категориальными признаками. Количество уникальных значений по каждому из признаков приведено в таблице 2.

Таблица 2. Количество уникальных значений по каждому из признаков в наборе данных Movie Lens.

4.2.2 Выбор способа тестирования алгоритмов

Выбор конфигурации тестирования алгоритмов на этом наборе данных проводился аналогично подобной процедуре для набора Amazon. Графики зависимости и отклонения оценки качества в зависимости от количества фолдов показаны на рис. 2. Было решено использовать для всех экспериментов фиксированное разбиение на 5 фолдов.

1. Эксперименты
   1. Используемая система для экспериментов

Все вычисления производились на ПК. Использовался Intel Core i5 7600 3.5 GHz, оперативная память 16 GB 2400MHz DDR4, операционная система Windows 10 x64 Максимальная.

Практически все эксперименты были запрограммированы на языке Python 3.8.6 с использованием библиотеки scikit-learn. Кроме этого были использованы Matlab и R 4.0.9.

• 1. Метод ближайшего соседа

В качестве базового и самого простого алгоритма (бейзлайна) будем использовать метод k ближайших соседей с метрикой Хемминга. На рис.3 показаны зависимости качества от количества ближайших соседей для обоих наборов данных.

AUC

AUC

_{0.74 0.64}

_{0.72 0.62}

_{0.70 0.60}

_{0.68 0.58}

_{0.66 0.56}

_{0.64 0.54}

_{0 5 10 15 20 25 30 35 0 20 40 60 80 100}

_{n_neighbors n_neighbors}

Рис. 3. Зависимость качества предсказания метода ближайших соседей от количества соседей. Слева изображен график для данных Amazon, справа для данных Movie Lens.

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

• 1. Наивный байесовский классификатор и его расширения
     1. Классический наивный байес

В первую очередь мной были проведены эксперименты с обычным наивным байесовским классификатором. При аппроксимации вероятностей p(y X^j) значительную роль играет параметр аддитивного сглаживания α. На рис. 4 можно увидеть зависимость качества работы алгоритмов от параметра сглаживания. Графики приведены для оптимальных в соответствующей задаче значений степени группировки признаков p. Стоит отметить, что оптимальное значение α практически не меняется с увеличением p. Соответственно, можно подобрать α при фиксированном p и использовать его в дальнейших вычислениях.

AUC

^{0.91 0.79}

AUC

^{0.90 0.78}

^{0.89 0.77}

^{0.88 0.76}

^{0.87 0.75}

^{0.86 0.74}

^{0.85 0.73}

^{0.84 0.72}

10^-3 10^-2 10^-1 10⁰ 10^-3 10^-2 10^-1 10⁰ 10¹ 10²

alpha0 alpha0

Рис. 4. Зависимость качества работы наивного байеса от параметра сглаживания. Слева изображен график для данных Amazon в случае группировки признаков по четверкам (p = 4), справа для данных Movie Lens в случае группировки признаков попарно (p = 2).