14.4. Классификация по ближайшему соседу
Предположим, что имеются образцы, полученные для каждого класса. Пусть вектор признаков для 
образца 
класса будет 
Один из возможных путей для классификации неизвестного вектора х заключается в нахождении образца, ближайшего к неизвестному, и определении класса, к которому он относится. Для некоторых к и 
это означает, что если 
для всех 
и 
то неизвестный х принадлежит классу 
.
При использовании этой простой идеи возникают две проблемы. Во-первых, хотя образцы, соответствующие отдельным классам, часто образуют кластеры, эти кластеры могут перекрываться. Неизвестный вектор, попавший в область перекрытия, может рассматриваться как
принадлежащий тому классу, представитель которого оказался поблизости. Классификация в таких областях по существу случайна. Возмож- но, что это лучшее, что можно сделать, однако простая граница всегда предпочтительнее.
Возможно, мы получим лучшие результаты, если просмотрим несколько соседей. Неизвестному вектору можно, например, приписать класс, встречающийся чаще всего среди к ближайших соседей. Это приведет к несколько лучшим результатам в пересекающихся областях, так как обеспечит оценку того, для какого из классов получилась наибольшая плотность вероятности.
Вторая проблема при классификации по ближайшему соседу связана с вычислениями. Если примеров много, то требуется большой объем памяти. Более того, если не использовать какой-либо схемы для разделения пространства, придется вычислять расстояние между неизвестным объектом и всеми образцами. Тем не менее это хороший метод, который не требует многих предположений о распределении вероятностей для представителей класса.
В некоторых случаях кластеры образуют неперекрывающиеся пятна. Если выпуклые оболочки кластеров не пересекаются, грани выпуклой оболочки можно использовать вместо всех образцов в кластере. В конечном счете это приводит к значительной экономии как времени, так и вычислений.
Большим преимуществом классификации по ближайшему соседу является то, что кластеры могут иметь сложную форму; им не обязательно быть симметричными относительно вращения или даже выпуклыми.
