Взвешенные соседи

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

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

Инвертирующая функция

Для преобразования расстояний в веса мы пользовались инвертирующей функцией. На рис. 8.3 показано, что получится, если отложить по одной оси вес, а по другой – цену.

Рис. 8.3. Функция инвертирования весов

В простейшем случае функция возвращает просто 1, поделенную на расстояние. Но иногда образцы оказываются в точности одинаковы или расположены очень близко друг к другу, и тогда значение получается слишком большим или бесконечным. Поэтому перед инвертированием необходимо добавить к расстоянию небольшую величину. Добавьте в файл numpredict.py функцию inverseweight: def inverseweight(dist,num=1.0,const=0.1): return num/(dist+const)

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

Функция вычитания

Второй вариант – это функция вычитания, график которой приведен на рис. 8.4.

Она просто вычитает расстояние из некоторой константы. Если получившийся в результате вес оказывается меньше нуля, то он приравнивается к нулю. Добавьте в файл numpredict.py функцию subtractweight: def subtractweight(dist,const=1.0): if dist>const:

return 0 else:

return const-dist

Рис. 8.4. Функция вычитания весов

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

Гауссова функция

И последней мы рассмотрим гауссову функцию, которую иногда называют колоколообразной кривой. Она несколько сложнее прочих функций, но, как вы увидите, не страдает от некоторых присущих им ограничений. График гауссовой функций изображен на рис. 8.5.

Рис. 8.5. Гауссова функция

Эта функция назначает вес 1, когда расстояние равно 0, а по мере увеличения расстояния вес уменьшается. Но, в отличие от функции вычитания, вес не становится равен 0, поэтому прогноз всегда возможен. Реализация гауссовой функции немного сложнее, и она работает не так быстро, как две другие функции.

Добавьте в файл numpredict.py функцию gaussian:

def gaussian(dist,sigma=10.0):

return math.e**(-dist**2/(2*sigma**2))

Попробуйте применить к одним и тем же образцам разные функции с различными параметрами и посмотрите, как будут изменяться результаты:

>>> reload(numpredict)

<module ‘numpredict’ from ‘numpredict.py’> >>> numpredict.subtractweight(0.1)

0.9

>>> numpredict.inverseweight(0.1)

5.0

>>> numpredict.gaussian(0.1)

0.99501247919268232 >>> numpredict.gaussian(1.0) 0.60653065971263342 >>> numpredict.subtractweight(1)

0.0

>>> numpredict.inverseweight(1)

0.90909090909090906 >>> numpredict.gaussian(3.0)

0.01110899653824231

Вы увидите, что все функции принимают максимальное значение в точке 0,0, а затем убывают, хотя и по-разному.

Взвешенный алгоритм kNN

Код взвешенного алгоритма kNN устроен так же, как и код обычного, то есть сначала мы получаем отсортированный массив расстояний и выбираем из него k ближайших элементов. Но дальше мы вычисляем не простое, а взвешенное среднее. Для этого каждый элемент умножается на вес, произведения суммируются, и результат делится на сумму всех весов. Добавьте в файл numpredict.py функцию weightedknn:

def weightedknn(data,vec1,k=5,weightf=gaussian):

#  Получить расстояния dlist=getdistances(data,vec1) avg=0.0

totalweight=0.0

#  Вычислить взвешенное среднее for i in range(k):

dist=dlist[i][0] idx=dlist[i][1] weight=weightf(dist) avg+=weight*data[idx][‘result’] totalweight+=weight avg=avg/totalweight return avg

Эта функция в цикле обходит k ближайших соседей и передает расстояние до каждого из них одной из рассмотренных выше функций вычисления весов. Переменная age вычисляется путем суммирования произведений веса и значения каждого соседа. В переменной totalweight накапливается сумма весов. В самом конце avg делится на totalweight. Протестируйте эту функцию в интерактивном сеансе и сравните результаты с обычным алгоритмом kNN:

>>> reload(numpredict)

<module ‘numpredict’ from ‘numpredict.py’> >>> numpredict.weightedknn(data,(99.0,5.0))

32.640981119354301

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

Вы можете следить за любыми ответами на эту запись через 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