Я реализую алгоритм K ближайших соседей для очень разреженных данных. Я хочу рассчитать расстояние между тестовым экземпляром и каждым образцом в обучающем наборе, но я запутался.
Потому что большинство функций в обучающих выборках не существуют в тестовом экземпляре или наоборот (отсутствуют функции).
Как я могу вычислить расстояние в этой ситуации?
Чтобы убедиться, что я правильно понимаю проблему: каждый образец образует очень редко заполненный вектор. Отсутствующие данные различаются между выборками, поэтому трудно использовать какую-либо евклидову или другую метрику расстояния для оценки сходства выборок.
Если это так, то я видел, как эта проблема раньше проявлялась в машинном обучении — в призовом конкурсе Netflix, но конкретно не применялась к KNN. Сценарий там был очень похожим: у каждого профиля пользователя были оценки для некоторых фильмов, но почти никто из пользователей не видел все 17 000 фильмов. Средний профиль пользователя был довольно разреженным.
У разных людей были разные способы решения проблемы, но, насколько я помню, они подставляли фиктивные значения для отсутствующих значений, обычно среднее значение конкретного значения по всем образцам с данными. Затем они использовали евклидово расстояние и т. д., как обычно. Вероятно, вы все еще можете найти обсуждения этой проблемы с отсутствующими значениями на этом форуме. Это была особенно распространенная проблема для тех, кто пытался реализовать декомпозицию по сингулярным числам, которая стала довольно популярной и, если я правильно помню, довольно много обсуждалась.
Вы можете начать здесь: http://www.netflixprize.com//community/viewtopic.php?id=1283
Вам придется немного покопаться. У Саймона Фанка был немного другой подход к этому, но он был более специфичен для СВД. Вы можете найти его здесь: http://www.netflixprize.com//community/viewtopic.php?id=1283 Он называет их пробелами, если вы хотите перейти к соответствующим разделам.
Удачи!
Если вы работаете в пространстве очень высокой размерности. Лучше выполнить сокращение пространства с помощью SVD, LDA, pLSV или аналогичного для всех доступных данных, а затем обучить алгоритм на обученных данных, преобразованных таким образом. Некоторые из этих алгоритмов масштабируемы, поэтому вы можете найти реализацию в проекте Mahout. Особенно я предпочитаю использовать более общие функции, чем такие преобразования, потому что это упрощает отладку и выбор функций. Для этого комбинируйте некоторые функции, используйте стеммеры, мыслите шире.
