4.3.6. Классификация по правилу ближайшего соседа

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

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

Прежде чем описать сам метод, уместно будет кратко обсудить понятие усреднения. Из-за чего можно усомниться в том, что имеет смысл усреднять измерения? Ответ заключается в том, что усреднение имеет смысл, только когда можно предположить, что измерение, соответствующее среднему, представительно по отношению к отдельным измерениям. Чтобы увидеть, когда это так, а когда не так, вернемся снова к данным Крейгов (рис. 4.5). Экспериментальные точки для образцов из четырех карьеров явно сгруппированы вокруг некоторой центральной, так что для нахождения типичной экспериментальной точки имеет смысл усреднять по выборкам из каждого карьера. Но данные карьера Наксос, по-видимому, образуют два отдельных скопления (Крейги именно так и интерпретируют эти данные, хотя и не указывают причин своего предположения). Усреднение по всем точкам из обоих скоплений Наксоса дает среднюю (центральную) точку, которая на самом деле не будет представителем экспериментальных точек. Подобные примеры, конечно, можно построить для еще более очевидных случаев. Например, величина „человек среднего веса" должна вычисляться с учетом всех людей, как мужчин, так и женщин, что явно не имеет смысла. Вообще, задачи, в которых усреднение непригодно, для человека очевидны, но как объяснить машине то, что очевидно для человека?

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

применяют простые правила (например, голосование по большинству).

Метод ближайшего соседа был впервые описан Фиксом и Ходжесом в 1951 г. С тех пор ему почти не уделяли внимания, возможно, потому, что он кажется слишком простым, чтобы быть интересным! Однако удивительно, что в тех исследованиях, в которых применялась классификация по правилу ближайшего соседа, обычно получались хорошие результаты. Кавер и Харт (1967; см. также Кавер, 1969) доказали для случая одну теорему, которая дает объяснение этому явлению.

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

Заметим, что это точная оценка только в предположении, что — независимые случайные выборки с возвращением. — случайная величина с математическим ожиданием

Интуитивно ясно, что с ростом стремится (формальное доказательство см. (Кавер и Харт, 1967)). Пусть будет риском ошибочной классификации любого случайным образом выбранного наблюдения при использовании некоторого неизвестного бейесовского метода оптимальной классификации. Кавер и Харт доказали, что для случая двух классов

В табл. 4.3 приведены значения верхней границы для соответствующей некоторым типичным уровням бейесовского риска (нижней границы). Чтобы решить, приемлемы ли эти границы, рассмотрим „мысленный эксперимент". Пусть даны два черных ящика, представляющие собой устройство классификации. Они могут быть либо оба бейесовскими, либо оба по правилу ближайшего соседа, либо различными. Наша задача заключается в выяснении, какая из этих возможностей на самом деле осуществляется. Чтобы решить ее, потребуем, чтобы каждое устройство классификации работало с различными выборками из объектов. Так как выборки различны, можно было бы ожидать, что устройство классификации по правилу ближайшего соседа сделает больше ошибок. Поэтому, если шансов менее 1 из 100, что число наблюдаемых ошибок будет таким же, как в

Таблица 4.3 (см. скан) Верхняя и ннжняя границы асимптотического риска при использовании правила ближайшего соседа. Размер выборки, необходимый для различения оптимального бейесовского правила и правила ближайшего соседа (наихудший случай)

случае одинаковых устройств классификации, мы решаем признать одно устройство бейесовским, другое — по правилу ближайшего соседа. Если же расхождение не слишком велико, то будем считать эти устройства классификации одинаковыми. Как велико должно быть число N, чтобы а) у нас были хорошие шансы правильно считать устройства классификации различными каждый раз, когда они действительно различны, или б) правильно решать этот вопрос в той же ситуации в трех случаях из четырех? Ответ можно получить, используя для оценки возможностей неравенства (65) и затем применяя статистические методы оценки мощности критерия (Коэн, 1969). Не будем останавливаться на объяснении результатов, просто сформулируем их. В столбцах За и 36 табл. 4.3 приведены необходимые размеры выборки для каждого эксперимента с различными уровнями бейесовского риска. Эти оценки могут оказаться лишь заниженными, поскольку при подготовке таблицы предполагалось, что устройство классификации по правилу ближайшего соседа функционирует с максимально возможным риском.

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

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

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