??? ??></a></td>
                <td align=
Поиск:     
Главная
Каталог
Для партнеров
Статьи
Ссылки    

Метод к ближайших соседей

В отличие от метода Роккио, метод к ближайших соседей (k nearest neighbors), или kNN-классификация, определяет разделяющие границы локально. В варианте 1NN каждый документ относится к определенному классу в зависимости от информации о его ближайшем соседе. В варианте kNN каждый документ относится к преобладающему классу ближайших соседей, где к — параметр метода. В основе метода kNN лежит факт, что в соответствии с гипотезой компактности мы ожидаем, что тестовый документ d будет иметь такую же метку, как и обучающие документы в локальной области, окружающей документ d

Разделяюшие границы в методе 1NN представляют собой смежные сегменты диаграммы Вороного (Voronoi resselation), показанной на рис. 14.6. Диаграмма Вороного для множества объектов разделяет пространство на ячейки, состоящие из точек, которые ближе к данному объекту, чем к другим. В нашем случае объектами являются документы. Диаграмма Вороного разделяет плоскость на |Ш)| выпуклых многоугольников, каждый из который содержит соответствующий документ (и не содержит других), как показано  выпуклый многоугольник есть выпуклая область двумерного пространства, ограниченная линиями.

Для произвольного параметра ке N в методе kNN рассмотрим область пространства, для которой множество к ближайших соседей остается одинаковым. Эта область также представляет собой выпуклый многоугольник, а пространство оказывается разделенным на выпуклые многоугольники, внутри каждого из которых множество к ближайших соседей является инвариантным.

Обобщением многоугольника на пространства более высоких размерностей является многогранник, т.е. область М-мерного пространства, ограниченная (М- 1)-мерными гиперплоскостями. В М-мерных пространствах границы решений в методе kNN состоят из сегментов (М- 1)-мерных полуплоскостей, образующих диаграмму Вороного, состоящую из выпуклых многогранников, построенных по обучающему множеству документов. Критерий отнесения документа к преобладающему среди его к ближайших соседей классу одинаково применим к М=2 (разбиение на многоугольники) и М>2 (разбиение на многогранники).

Метод 1NN не очень устойчив. Классификация каждого текстового документа зависит от класса, к которому относится отдельный обучающий документ, который может иметь неверную метку или вообще быть нетипичным. Метод kNN при k> 1 является более устойчивым. Он приписывает документы к превалирующему классу по к ближайшим соседям, случайным образом разрывая связи между ними.

Существует вероятностный вариант метода kNN. Можно оценить вероятность того, что документ принадлежит классу с, как долю к ближайших соседей в классе с. На рис. 14.6 приведен пример классификации при к = 3. Оценки вероятностей того, что документ, отмеченный звездочкой, принадлежит трем классам, таковы: (класс кружоч- ков|звездочка) = 1/3, (класс крестиков|звездочка) = 2/3, (класс ромбиков|звездочка) = 0. Оценки метода 3NN (/J (класс кружочков|звездочка) = 1/3) и метода INN ( Pt (класс кру- жочков|звездочка) =1) отличаются, поэтому метод 3NN отдает предпочтение классу крестиков, а метод 1NN — классу кружочков.

Параметр к в методе kNN часто выбирается на основании опыта или знаний о решаемой задаче классификации. Желательно, чтобы параметр к был нечетным, чтобы уменьшить вероятность “ничьей”. Чаще всего выбираются значения к = 3 и к = 5, но используются и большие значения, между 50 и 100. В качестве альтернативы параметр к можно выбрать так, чтобы он гарантировал наилучшие результаты на отложенной части обучающего множества

Интернет-реклама дает возможность оперативно вносить изменения в рекламную кампанию и использовать именно тот материал который способствует продвижению сайта и росту его популярности. Спонсор статьи напоминает – доверьте Интернет-рекламу специалистам.

 
 
Copyright KYPON.RU, 2006. All rights reserved. Powered by Shop-Script FREE - shop-script