Другой способ встраивания сущностей
Около года назад я работал над регрессионной моделью, в которой было более миллиона функций. Излишне говорить, что обучение было очень медленным, и модель сильно переоснащалась. Изучив эту проблему, я понял, что большинство функций были созданы с использованием однократного кодирования категориальных функций, а некоторые из них имели десятки тысяч уникальных значений.
Проблема отображения категориальных характеристик в пространство меньшей размерности не нова. В последнее время одним из популярных способов борьбы с этим является использование слоев нейронной сети, встраиваемых в сущности. Однако этот метод предполагает использование нейронных сетей. Что, если бы мы решили вместо этого использовать древовидные алгоритмы? В этом случае мы можем использовать методы теории спектральных графов для создания низкоразмерных вложений категориальных функций.
Идея пришла из алгоритмов вложения спектральных слов, спектральной кластеризации и уменьшения спектральной размерности. Если вы можете определить меру подобия между различными значениями категориальных признаков, мы можем использовать методы спектрального анализа, чтобы найти низкоразмерное представление категориальных признаков.
Из функции подобия (или функции ядра) мы можем построить матрицу смежности, которая является симметричной матрицей, где элемент ij является значением функции ядра между значениями категорий i и j:
Очень важно, что мне нужна только функция ядра, а не многомерное представление. Это означает, что шаг 1-горячего кодирования здесь не требуется. Также для методов машинного обучения на основе ядра этап кодирования категориальных переменных также не требуется, потому что важна функция ядра между двумя точками, которую можно построить с использованием отдельных функций ядра.
Как только матрица смежности построена, мы можем построить матрицу степеней:
Здесь δ - символ Кронекера. Матрица Лапласа - это разница между ними:
А нормализованная матрица Лапласа определяется как:
Следуя теории спектральных графов, мы приступим к собственному разложению нормированной матрицы Лапласа. Количество нулевых собственных значений соответствует количеству связанных компонент. В нашем случае предположим, что наша категориальная характеристика имеет два набора совершенно разных значений. Это означает, что ядерная функция K (i, j) равна нулю, если i и j принадлежат разным группам. В этом случае у нас будет два нулевых собственных значения нормированной матрицы Лапласа.
Если есть только одна компонента связности, у нас будет только одно нулевое собственное значение. Обычно он неинформативен и отбрасывается, чтобы предотвратить мультиколлинеарность функций. Однако мы можем сохранить его, если планируем использовать древовидные модели.
Нижние собственные значения соответствуют «гладким» собственным векторам (или модам), которые более точно соответствуют функции подобия. Мы хотим сохранить только эти собственные векторы и отбросить собственные векторы с более высокими собственными значениями, потому что они, скорее всего, представляют собой шум. Очень часто ищут пробел в спектре матрицы и выбирают собственные значения ниже щели. Результирующие усеченные собственные векторы могут быть нормализованы и представлять вложения значений категориальных признаков.
В качестве примера рассмотрим День недели. 1-горячее кодирование предполагает, что каждый день похож на любой другой день (K (i, j) = 1). Это маловероятное предположение, потому что мы знаем, что дни недели разные. Например, посещаемость бара резко возрастает по пятницам и субботам (по крайней мере, в США), потому что следующий день - выходной. Кодировка метки также неверна, потому что из-за нее «расстояние» между понедельником и средой будет вдвое больше, чем между понедельником и вторником. А «расстояние» между воскресеньем и понедельником будет в шесть раз больше, даже если дни находятся рядом друг с другом. Кстати, кодировка метки соответствует ядру K (i, j) = exp (−γ | i − j |)
Рассмотрим пример, когда будние дни похожи друг на друга, но сильно отличаются от выходных.
array([[ 0, 10, 9, 8, 5, 2, 1],
[10, 0, 10, 9, 5, 2, 1],
[ 9, 10, 0, 10, 8, 2, 1],
[ 8, 9, 10, 0, 10, 2, 1],
[ 5, 5, 8, 10, 0, 5, 3],
[ 2, 2, 2, 2, 5, 0, 10],
[ 1, 1, 1, 1, 3, 10, 0]])
array([[ 1. , -0.27788501, -0.24053512, -0.21380899, -0.14085904, -0.07049074, -0.040996 ],
[-0.27788501, 1. , -0.25993762, -0.23394386, -0.13699916, -0.06855912, -0.03987261],
[-0.24053512, -0.25993762, 1. , -0.25 , -0.21081851, -0.06593805, -0.03834825],
[-0.21380899, -0.23394386, -0.25 , 1. , -0.26352314, -0.06593805, -0.03834825],
[-0.14085904, -0.13699916, -0.21081851, -0.26352314, 1. , -0.17376201, -0.12126781],
[-0.07049074, -0.06855912, -0.06593805, -0.06593805, -0.17376201, 1. , -0.50572174],
[-0.040996 , -0.03987261, -0.03834825, -0.03834825, -0.12126781, -0.50572174, 1. ]])
array([0. , 0.56794799, 1.50908645, 1.08959831, 1.3053149 , 1.25586378, 1.27218858])
Обратите внимание, что собственные значения здесь не упорядочены. Построим график собственных значений, игнорируя неинформативный ноль.
Мы видим довольно существенный разрыв между первым собственным значением и остальными собственными значениями. Если это не дает достаточной производительности модели, вы можете включить второе собственное значение, потому что разрыв между ним и более высокими собственными значениями также весьма значителен.
Выведем все собственные векторы:
array([[ 0.39180195, 0.22866879, 0.01917247, -0.45504284, 0.12372711, -0.41844908, -0.62957304],
[ 0.40284079, 0.24416078, 0.01947223, -0.4281388 , -0.53910465, -0.01139734, 0.55105271],
[ 0.41885391, 0.23795901, -0.0032909 , -0.00102155, 0.24759021, 0.82656956, -0.15299308],
[ 0.41885391, 0.21778112, -0.01536901, 0.36430356, 0.56996731, -0.36551902, 0.43094387],
[ 0.39735971, -0.02474713, 0.07869969, 0.66992782, -0.54148697, -0.08518483, -0.29331097],
[ 0.3176117 , -0.61238751, -0.71702346, -0.09280736, 0.02933834, 0.00752668, 0.02123917],
[ 0.27305934, -0.63907128, 0.69187421, -0.13963728, 0.11758088, 0.02521838, 0.06615712]])
Посмотрите на второй собственный вектор. Значения выходных дней имеют другой размер, чем рабочие дни, а пятница близка к нулю. Это доказывает переходную роль пятницы, которая, будучи днем недели, также является началом выходных.
Если мы собираемся выбрать два наименьших ненулевых собственных значения, наша категориальная кодировка признаков приведет к следующим векторам категорий:
array([[ 0.22866879, -0.45504284],
[ 0.24416078, -0.4281388 ],
[ 0.23795901, -0.00102155],
[ 0.21778112, 0.36430356],
[-0.02474713, 0.66992782],
[-0.61238751, -0.09280736],
[-0.63907128, -0.13963728]])
На графике выше мы видим, что понедельник и вторник, а также суббота и воскресенье сгруппированы близко друг к другу, а среда, четверг и пятница находятся далеко друг от друга.
Изучение функции ядра
В предыдущем примере мы предполагали, что задана функция подобия. Иногда это так, когда это можно определить на основе бизнес-правил. Однако можно узнать об этом по данным.
Один из способов вычисления ядра - использование Дивергенции Кульбака-Лейблера:
Где D - симметричное расхождение KL:
Здесь pi - вероятность данных при значении категории i:
Идея состоит в том, чтобы оценить распределение данных (включая целевую переменную, но исключая категориальную переменную) для каждого значения категориальной переменной. Если для двух значений распределения похожи, то расхождение будет небольшим, а значение подобия будет большим. Обратите внимание, что γ - гиперпараметр и его необходимо настраивать.
Для опробования этого подхода воспользуемся набором данных о продажах спиртных напитков. Чтобы файл оставался маленьким, я удалил несколько столбцов и собрал данные.
Поскольку мы заботимся о продажах, давайте закодируем день недели, используя информацию из столбца продаж. Сначала проверим гистограмму:
sns.distplot(liq.sales, kde=False);
Мы видим, что распределение сильно искажено, поэтому попробуем вместо этого использовать журнал продаж.
sns.distplot(np.log10(1+liq.sales), kde=False);
Это намного лучше. Итак, мы будем использовать журнал для нашей раздачи
liq["log_sales"] = np.log10(1+liq.sales)
Здесь мы будем следить за этим блогом для вычисления дивергенции Кульбака-Лейблера. Также обратите внимание, что, поскольку в воскресенье нет продажи спиртных напитков, мы рассматриваем только шесть дней в неделю.
array([[0.00000000e+00, 8.77075038e-02, 4.67563784e-02, 4.73455185e-02, 4.36580887e-02, 1.10008520e-01],
[8.77075038e-02, 0.00000000e+00, 6.33458241e-03, 6.12091647e-03, 7.54387432e-03, 1.24807509e-03],
[4.67563784e-02, 6.33458241e-03, 0.00000000e+00, 1.83170834e-06, 5.27510292e-05, 1.32091396e-02],
[4.73455185e-02, 6.12091647e-03, 1.83170834e-06, 0.00000000e+00, 7.42423681e-05, 1.28996949e-02],
[4.36580887e-02, 7.54387432e-03, 5.27510292e-05, 7.42423681e-05, 0.00000000e+00, 1.49325072e-02],
[1.10008520e-01, 1.24807509e-03, 1.32091396e-02, 1.28996949e-02, 1.49325072e-02, 0.00000000e+00]])
Как мы уже упоминали, гиперпараметр γ необходимо настроить. Здесь мы просто выбираем значение, которое даст правдоподобный результат.
gamma = 20
kernel = np.exp(-gamma * kl_matrix)
np.fill_diagonal(kernel, 0)
kernel
array([[0. , 0.17305426, 0.39253579, 0.38793776, 0.41762901, 0.11078428],
[0.17305426, 0. , 0.88100529, 0.88477816, 0.85995305, 0.97534746],
[0.39253579, 0.88100529, 0. , 0.99996337, 0.99894554, 0.76783317],
[0.38793776, 0.88477816, 0.99996337, 0. , 0.99851625, 0.77259995],
[0.41762901, 0.85995305, 0.99894554, 0.99851625, 0. , 0.74181889],
[0.11078428, 0.97534746, 0.76783317, 0.77259995, 0.74181889, 0. ]])
norm_lap = normalized_laplacian(kernel)
sz, sv = np.linalg.eig(norm_lap)
sz
array([1.11022302e-16, 9.99583797e-01, 1.22897829e+00, 1.27538999e+00, 1.24864532e+00, 1.24740260e+00])
In [18]:
sns.stripplot(data=sz[1:], jitter=False, );
Игнорируя нулевое собственное значение, мы видим, что существует больший разрыв между первым собственным значением и остальными собственными значениями, даже если все значения находятся в диапазоне от 1 до 1,3.
В конечном итоге количество используемых собственных векторов - это еще один гиперпараметр, который следует оптимизировать для задачи обучения с учителем. Поле «Категория» - еще один кандидат для проведения спектрального анализа и, вероятно, лучший выбор, так как в нем больше уникальных значений.
len(liq.Category.unique()) 107
array([[0.00000000e+00, 1.01321384e-02, 2.38664557e-01, ..., 5.83930416e-02, 2.05621708e+01, 4.44786939e-01],
[1.01321384e-02, 0.00000000e+00, 1.50225839e-01, ..., 1.17178087e-01, 2.24843754e+01, 5.89215704e-01],
[2.38664557e-01, 1.50225839e-01, 0.00000000e+00, ..., 5.33952956e-01, 2.95549456e+01, 1.33572924e+00],
...,
[5.83930416e-02, 1.17178087e-01, 5.33952956e-01, ..., 0.00000000e+00, 1.59700549e+01, 1.80637715e-01],
[2.05621708e+01, 2.24843754e+01, 2.95549456e+01, ..., 1.59700549e+01, 0.00000000e+00, 8.58405693e+00],
[4.44786939e-01, 5.89215704e-01, 1.33572924e+00, ..., 1.80637715e-01, 8.58405693e+00, 0.00000000e+00]])
plot_eigenvalues(100);
Мы видим, что многие собственные значения сгруппированы вокруг отметки 1.1. Собственные значения, расположенные ниже этого кластера, можно использовать для кодирования функции категории. Также обратите внимание, что этот метод очень чувствителен к выбору гиперпараметра γ. Для иллюстрации позвольте мне выбрать более высокую и более низкую гамму.
plot_eigenvalues(7000);
plot_eigenvalues(10)
Заключение и дальнейшие шаги
Мы представили способ кодирования категориальных признаков в виде вектора низкой размерности, который сохраняет большую часть информации о сходстве признаков. Для этого мы используем методы спектрального анализа по значениям категориального признака. Чтобы найти функцию ядра, мы можем либо использовать эвристику, либо изучить ее, используя различные методы, например, используя расхождение Кульбака – Лейблера в распределении данных, обусловленное значением категории. Чтобы выбрать подмножество собственных векторов, мы использовали анализ пробелов, но что нам действительно нужно, так это проверить эти методы путем анализа различных наборов данных и задач классификации и регрессии. Нам также необходимо сравнить это с другими методами кодирования, например, с внедрением сущностей с использованием нейронных сетей. Используемая нами функция ядра также может включать информацию о частоте категорий, что поможет нам работать с высокими значениями информации, но с низкими частотными значениями.
Обновление от 04.07.2019: лучший способ вычислить функцию подобия - использовать расстояние Вассерштейна вместо симметричного расхождения Кульбака – Лейблера. Обновленный код можно найти в моем репозитории на github.
