ОБУЧЕНИЕ НА ОСНОВЕ ЭКЗЕМПЛЯРА
Модели ближайшего соседа
Ключевая идея моделей ближайшего соседа состоит в том, что свойства любой конкретной входной точки х, по-видимому, должны быть подобными свойствам точек, соседних по отношению к х. Например, если требуется выполнить оценку плотности (т.е. оценить значение неизвестной плотности вероятности в точке х), то можно просто измерить ту плотность, с какой расположены точки, рассеянные в окрестности х. Такая задача на первый взгляд может показаться очень простой, пока не станет очевидно, что нужно точно определить, что подразумевается под понятием "окрестность". Если окрестность слишком мала, то не будет содержать ни одной точки данных, а если слишком велика, то может включить все точки данных, в результате чего будет получена всюду одинаковая оценка плотности. Одно из возможных решений состоит в том, чтобы определить окрестность как достаточно большую для включения к точек, где к достаточно велико для обеспечения получения осмысленной оценки. При постоянном значении к размеры окрестности изменяются — если данные являются разреженными, то окрестность велика, а если данные расположены плотно, то окрестность мала. На рис. 20.12, а показан пример данных, рассеянных в двух измерениях, а на рис. 20.13 приведены результаты оценки плотности по к ближайшим соседним точкам на основании этих данных при к=3, 10 и 40 соответственно. При к=3 оценка плотности в любой точке основана только на 3 соседних точках и весьма изменчива. При к=10 полученная оценка представляет собой хорошую реконструкцию истинной плотности, показанной на рис. 20.12, б. При ?=4 0 окрестность становится слишком большой и информация о структуре данных полностью теряется. На практике хорошие результаты для большинства наборов данных с малым количеством размерностей можно получить с помощью значения к, находящегося примерно между 5 и 10. Подходящее значение для к можно также выбрать с использованием перекрестной проверки.
Для выявления соседних точек, ближайших к точке запроса, нужна метрика расстояний D{xlf х2). В двухмерном примере, приведенном на рис. 20.12, используется евклидово расстояние. Но такая метрика становится неподходящей, если каждая размерность пространства измеряет что-то другое (например, рост и вес), поскольку изменение масштаба одной размерности приводит к изменению множества ближайших соседних точек. Одним из решений является стандартизация масштаба для каждой размерности. Для этого измеряется среднеквадратичное отклонение каждой характеристики по всему набору данных и значения характеристик выражаются как кратные среднеквадратичного отклонения для этой характеристики (это — частный случай расстояния Махаланобиса, в котором также учитывается ковариация характеристик). Наконец, для дискретных характеристик можно использовать расстояние Хемминга, в котором D(xlr х2) определяется как количество характеристик, по которым отличаются точки хх и х2.
Оценки плотности, подобные приведенным на рис. 20.13, определяют совместные распределения по пространству входных данных. Но в отличие от байесовской сети, представление на основе экземпляра не может содержать скрытых переменных, а это означает, что может выполняться неконтролируемая кластеризация, как это было в случае с моделью смешанного гауссова распределения. Тем не менее оценка плотности все еще может использоваться для предсказания целевого значения у по входным значениям характеристики х путем вычисления вероятности p(ylx)=P(y,х)/Р(х), при условии, что обучающие данные включают значения для соответствующей целевой характеристики.
Идею оценки характеристик с помощью ближайшей соседней точки можно также непосредственно использовать в контролируемом обучении. Если имеется проверочный пример с входными данными х, то выходное значение y=h (х) можно получить на основании значений у для к ближайших соседних точек точки х. В дискретном случае единственное предсказание можно получить с помощью мажоритарного голосования, а в непрерывном случае — предусмотреть усреднение по к значениям или применить локальную линейную регрессию, подгоняя гиперплоскость к к точкам и предсказывая значение в точке х с помощью этой гиперплоскости.
Алгоритм обучения с помощью к ближайших соседних точек является очень простым для реализации, требует весьма небольшой настройки и часто показывает достаточно приемлемую производительность. Вполне целесообразно, столкнувшись с новой задачей обучения, вначале попытаться воспользоваться этим алгоритмом. Но при наличии больших наборов данных требуется эффективный механизм поиска соседних точек, ближайших к точке запроса х, поскольку выполнение метода, в котором просто вычисляется расстояние до каждой точки, занимает слишком много времени. Было предложено много остроумных методов, позволяющих повысить эффективность этого этапа, которые основаны на предварительной обработке обучающих данных. Но, к сожалению, большинство из этих методов не достаточно хорошо масштабируются с увеличением количества размерностей пространства (т.е. количества характеристик).
При использовании многомерных пространств возникает еще одна проблема, связанная с тем, что ближайшие соседние точки в таких пространствах в действительности часто находятся очень далеко! Рассмотрим набор данных с размером N в d-мерном единичном гиперкубе и предположим, что нужно найти гиперкубическую окрестность с размером Ь и объемом bd (те же рассуждения относятся к гиперсферам, но формула объема гиперсферы является более сложной). Чтобы в нее вошло Сточек, средняя окрестность должна занимать долю k/N всего объема гиперкуба, который равен 1. Поэтому bd=k/N, или Ь= (k/N)1/d. До сих пор все шло хорошо. А теперь допустим, что количество характеристик d равно 100, и предположим, что Нравно 10, а N равно 1 ООО ООО. В таком случае получаем, что Ь=0 .89, т.е. что окрестность должна охватывать почти все пространство входных данных! Эти расчеты говорят о том, что методам с ближайшими соседними точками нельзя доверять, когда дело касается многомерных данных, а в случае малого количества размерностей не возникает никаких проблем; при d=2 получаем Ь=0