k-ближайшие соседи

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

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

Таблица 12.6. Цены на цифровые камеры

Камера

Мегапиксели

Зум

Цена

C1

7,1

3,8x

$399

C2

5,0

2,4x

$299

C3

6,0

4,0x

$349

C4

6,0

12,0x

$399

C5

10,0

3x

$449

Предположим, что вы хотите узнать цену новой камеры с шестью мегапикселями и объективом, имеющим зум 6x. Первым делом нужно найти способ измерить степень подобия двух образцов. Ранее мы пользовались евклидовым расстоянием, но в книге были описаны и другие метрики, в частности коэффициент корреляции Пирсона и коэффициент Танимото. В терминах евклидова расстояния ближайшей камерой будет C3. Для визуализации результата нанесите образцы на диаграмму, где по оси x отложены мегапиксели, а по оси y – зум. Сами образцы представлены на диаграмме своими ценами (рис. 12.10). Можно было бы в качестве ответа просто взять цену $349 (это ведь ближайшее соответствие, правда?), но вдруг эта цена – аномалия? Поэтому лучше взять несколько самых похожих камер и усреднить их цены.

Рис. 12.10. Цены камер в пространстве зум-мегапиксели

Параметр k в методе k-ближайших соседей – это количество усредняемых образцов. Например, проводя усреднение по трем самым похожим камерам, вы применяете алгоритм kNN с k = 3.

Вместо прямолинейного усреднения можно вычислить средневзвешенное с учетом того, насколько далеко отстоят образцы. Чем больше расстояние, тем меньше вес. Ранее были рассмотрены различные функции вычисления весов. В данном примере цене $349 можно приписать наибольший вес, а двум ценам $399 – веса поменьше. Например:

Цена = 0,5 x 349 + 0,25 x 399 + 0,25 x 399 = 374

Масштабирование и лишние переменные

У описанного выше варианта алгоритма kNN есть существенный недостаток – он вычисляет расстояние по всем переменным. Но если переменные измеряют несопоставимые характеристики и одна из них оказывается заметно больше прочих, то она будет несоразмерно сильно влиять на понятие «близости». Представьте, что в рассмотренном наборе разрешение измеряется в пикселях, а не в мегапикселях. Понятно, что разница в зуме на 10 единиц гораздо более важна, чем разница в разрешении на 10 пикселей, но алгоритм трактует их одинаково. Бывают также ситуации, когда некоторые переменные абсолютно бесполезны для прогнозирования, но они тоже вносят вклад в прогноз. Эту проблему можно решить масштабированием данных до вычисления расстояний. Ранее нами был написан метод для масштабирования, подразумевающий увеличение амплитуды одних переменных и уменьшение – других. Бесполезные переменные можно умножить на 0, после чего они перестают влиять на результат. Ценные переменные, принимающие значения из существенно различающихся диапазонов, можно привести к общему масштабу, например, решив, что разница в 2000 пикселей эквивалентна разнице в 1 единицу зума.

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

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

Рис. 12.11. Перекрестный контроль с одним изъятым образцом

Использование ранее написанного кода

Ранее были написаны функции, реализующие простой и взвешенный алгоритм kNN. Их легко применить к набору данных, показанному в табл.12.6.

>>> cameras=[{‘input’:(7.1,3.8),’result’:399},

… {‘input’:(5.0,2.4),’result’:299}, … {‘input’:(6.0,4.0),’result’:349}, … {‘input’:(6.0,12.0),’result’:399}, … {‘input’:(10.0,3.0),’result’:449}] >>> import numpredict >>> numpredict(cameras,(6.0,6.0),k=2) 374.0

>>> numpredict.weightedknn(cameras,(6.0,6.0),k=3)

351.52666892719458

Возможно, результат удастся улучшить путем масштабирования данных. Для этого служит функция rescale: >>> scc=numpredict.rescale(cameras,(1,2)) >>> scc

[{‘input’: [7.1, 7.6], ‘result’: 399}, {‘input’: [5.0, 4.8], ‘result’: 299}, {‘input’: [6.0, 8.0], ‘result’: 349}, {‘input’: [6.0, 24.0], ‘result’: 399}, {‘input’: [10.0, 6.0], ‘result’: 449}]

А с помощью функции crossvalidate вы сможете найти наилучший коэффициент масштабирования:

>>> numpredict.crossvalidate(knn1,cameras,test=0.3,trials=2)

3750.0

>>> numpredict.crossvalidate(knn1,scc,test=0.3,trials=2)

2500.0

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

Сильные и слабые стороны

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

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

Алгоритм kNN относится к числу оперативных методов, то есть данные можно добавлять в любой момент, в отличие, скажем, от машины опорных векторов, которую требуется переучивать при каждом изменении данных. Более того, при добавлении новых данных не нужны вообще никакие вычисления; достаточно просто включить данные в набор. Основной недостаток kNN заключается в том, что для прогнозирования ему требуются все данные, на которых производилось обучение. Если в наборе миллионы образцов, то на это расходуется не только память, но и время – для выработки каждого прогноза приходится сравнивать новый образец с каждым из имеющихся, чтобы найти ближайшие. Для некоторых приложений это недопустимо медленно.

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100