Методы ближнего и дальнего соседа

[zw0rk]

Сорри, если не туда (не нашел в CS подфорума для таких вопросов). Задали тут мне задачку. В которой не совсем ясна формулировка, но я предполагаю, что задача распространённая и потому знающие люди мне подскажут куда копать (мне не решение надо, а формулировку уточнить

Дана матрица (m1+m2)*n эл-тами которой являються числа 0 и 1. На вход подаёться некоторая послед-ть длины n тоже из чисел 0 и 1. Надо найти к какому классу (?) принадлежит введённый элемент методами ближнего и дальнего соседа, расстоянием считать расстояние Хемминга.

У меня такие вопросы, если кто с чем подобным сталкивался. Что имееться в виду -- найти в какой из частей матрицы (m1*n или m2*n) лежит ближайшая в смысле Хемминга введённой строка матрицы или найти все расстояния от введённой строки до строк из m1*n и m2*n и какие из них в сумме меньше -- те и взять или еще что? Тут, видимо у меня путаница из-за отсутствия определения понятия класс.. ну и что такое методы ближнего и дальнего соседа, конечно

Гуглил, всё очень расплывчато по этому делу. Помогите какой-нибудь правдоподобной идеей, пожалуйста . Или книжкой вумной.

[PAV]

У нас есть объекты двух классов (это двоичные строки из матрицы, одна часть - один класс, другая - другой). Подается новый объект, требуется определить принадлежность его к одному или другому классу. Задана метрика (Хемминг).

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

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

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

[zw0rk]

Огромное спасибо!