Вы говорите, что алгоритм таков: алгоритм k-ближайшего соседа с k = количеством используемых тренировочных точек. Я определяю это как JMS-K-ближайший сосед .
Поскольку размерность VC является наибольшим числом обучающих точек, которые могут быть разбиты алгоритмом с ошибкой поезда 0, размерность VC jms-k-ближайшего соседа может быть только k или 0.
1 обучающий экземпляр => k = 1: во время обучения jms-1-ближайший сосед сохраняет именно этот экземпляр. Во время применения к одному и тому же обучающему набору один экземпляр является ближайшим к сохраненному обучающему экземпляру (поскольку они совпадают), поэтому ошибка обучения равна 0.
Итак, я согласен, размерность VC составляет не менее 1.
2 варианта обучения => k = 2: проблема может возникнуть только в случае различий в метках. В этом случае вопрос заключается в том, как принимается решение о метке класса. Голос большинства большинством не приводит к результату (VC = 0?), Если мы используем большинство голосов, взвешенных обратно пропорционально расстоянию, измерение VC равно 2 (при условии, что нельзя использовать один и тот же обучающий экземпляр дважды с разными метками, в этом В этом случае размерность VC всех алгоритмов будет равна 0 (я думаю).
Не существует стандартного алгоритма k-ближайшего соседа, это скорее семейство с той же базовой идеей, но разным вкусом, когда дело доходит до деталей реализации.
Используемые ресурсы: слайды измерений VC от Эндрю Мура