Все мы знаем о классическом алгоритме классификации машинного обучения, K-ближайшего соседа, как об одном из самых успешных непараметрических алгоритмов машинного обучения. Впервые оно было введено Фиксом и Ходжесом в неопубликованном отчете Школы авиационной медицины ВВС США за 1951 год [1], которое стало известно как правило k-ближайшего соседа и в последующие годы претерпело дальнейшие модификации. В последнее время хорошо известно, что он отлично справляется с проблемами классификации изображений, связанными с компьютерным зрением.
Но осознаем ли мы или опасаемся его непредсказуемости в случае хорошо сбалансированных данных? На самом деле многие из нас настолько привыкли к таким инструментам машинного обучения, как Scikit-Learn в Python, программированию R, MATLAB Machine Learning Toolbox или WEKA, что алгоритмам машинного обучения часто не придается значение на уровне их реализации. По словам некоторых практикующих ОД:
«Что нужно знать о том, что происходит под капотом? .. Кто попросит вас дать алгоритмическое описание или обзор алгоритмов обучения? Просто реализуйте (вызовите их функцию) с помощью набора инструментов (а именно Scikit-Learn)… конечный результат - единственное, что имеет значение… Глубокое изучение алгоритмов машинного обучения - пустая трата времени ».
Более того, во многих книгах вроде
Практическое машинное обучение с помощью Scikit Learn и TensorFlow [2]
не дают никакого алгоритмического обзора и сразу переходят к реализации Scikit-Learn алгоритмов машинного обучения. Я не считаю книгу неуместной до тех пор, пока авторы книги ожидают, что читатели будут хорошо разбираться, по крайней мере, с обзором или интуитивным подходом алгоритмов машинного обучения в качестве предварительного условия, прежде чем изучать правильное использование Scikit-Learn.
В любом случае, я глубоко изучил алгоритм kNN на уровне реализации и обнаружил интересную аномалию в алгоритме.
kNN фактически создается с использованием евклидовой геометрии пространственных объектов, что делает его алгоритмом обучения без параметров. Прежде чем переходить к псевдокоду, важно визуализировать все точки данных в пространстве функций.
Псевдокод для алгоритма kNN в двоичной классификации приведен ниже:
Есть несколько функций, которые будут использоваться в псевдокоде только для объяснения работы, а не программирования или кодирования на любом языке.
- near_neighbors (x): возвращает двумерный массив выборок, в котором 1-е измерение представляет различные евклидовы расстояния в массиве в порядке убывания, а 2-е измерение представляет выборки с таким же евклидовым расстоянием от x.
- find (nb, data): он возвращает индексы путем сопоставления выборок, возвращаемых функцией near_neighbors, nb, с исходным набором данных, data.
- count (p, num): возвращает частоту num (любое число, здесь метка) в массиве, p
- size (m): возвращает длину вектора, m
- y: исходные целевые метки набора данных.
Псевдокод приводится ниже.
1. kNN(x)
2. {
3. k = 0
4. c = k
5. nearest = nearest_neighbors(x)
6. indices = find(nearest[0],data)
7. label = y[indices]
8. if(size(label)==1)
9. {
10. prediction = label[0]
11. }
12. else
13. {
14. while c == k:
15. {
16. n_0 = count(prediction,0)
17. n_1 = count(prediction,1)
18. if (n_1 > n_0)
19. {
20. prediction = 1
21. break
22. }
23. else if(n_0 > n_1)
24. {
25. prediction = 0
26. break
27. }
28. else
29. {
30. k = k + 1
31. indices = find(nearest[k],data)
32. if(size(y[indices])==1)
33. {
34. prediction = y[indices][0]
35. break
36. }
37. else
38. {
39. c = c + 1
40. }
41. }
42. }
43. }
44. result = [prediction;c]
45. return result
46.}
Здесь псевдокод k-ближайшего соседа формируется с помощью функции kNN (), которая принимает один тестовый образец или экземпляр, x в качестве аргумента и возвращает двумерный вектор, содержащий результат прогнозирования в качестве 1-го элемента и значение k. как 2-й элемент.
До сих пор проблем нет, и формулировка алгоритма кажется красивой и конкретной. Но внутри алгоритма есть большая аномалия.
Теперь, погрузившись глубже, давайте рассмотрим возможности наихудшего случая при выполнении двоичной классификации с использованием k-ближайшего соседа.
ОБЪЯСНЕНИЕ АНОМАЛИИ:
Наихудший случай возникает, когда существует четное (›1) количество, скажем, n ближайших соседей, и половина из n соседей принадлежит метке 0, а другая половина принадлежит метке 1. Тогда (n + 1) -ые ближайшие соседи должны быть быть найденным (согласно алгоритму), и если такой же случай возникнет снова, будут найдены (n + 2) -ые ближайшие соседи и так далее. Если этот случай продолжает возникать (может возникать в высоко сбалансированном наборе данных), в определенный момент в наборе данных больше не останется выборок, и при каждом рассмотрении n-го ближайшего соседа одинаковое количество экземпляров обеих меток нашел. Следовательно, невозможно принять решение о предсказании тестовой выборки, даже если после достижения максимального значения k согласно набору данных.
ПРИМЕРНЫЕ ДАННЫЕ ДЛЯ ДОКАЗАТЕЛЬСТВА АНОМАЛИИ:
Образец набора данных показан в пространстве признаков, содержащем 12 экземпляров, и каждый экземпляр имеет 2 функции, F1 и F2.
Предметы будущего для читателей:
Читателям предлагается глубоко понять, почему приведенная выше визуализация набора данных Exemplar является ошибочным случаем kNN. Им также предлагается подготовить такой набор данных и выбрать подходящую тестовую выборку. После этого используйте наборы инструментов, такие как Scikit-Learn или программирование на R, чтобы увидеть прогноз или решение, принятое классификатором. Если будут замечены какие-либо новые изменения или возникнут какие-либо осложнения в связи с неисправным случаем kNN, пожалуйста, укажите в разделе комментариев ниже.
Возможное решение, чтобы избежать этого ошибочного случая:
Такой набор данных, который показан в визуализации пространства признаков, действительно очень сложен для работы, и это тоже касается выбора такой тестовой выборки (центр концентрических кругов). Конечно, можно сделать вывод, что в наборе данных будут присутствовать выбросы (несущественные экземпляры или экземпляры, снижающие производительность). Следовательно, одним из возможных решений этой проблемы является занижение выборки. Один из наиболее распространенных и успешных алгоритмов недостаточной выборки в области интеллектуального анализа данных - это метод недостаточной выборки большинства на основе кластерных центроидов (CCMUT) [3]. Таким образом, с помощью недостаточной выборки можно нарушить равномерную балансировку набора данных и, следовательно, затем применить kNN для классификации выбранной тестовой выборки.
ССЫЛКИ:
[1] http://www.scholarpedia.org/article/K-nearest_neighbor
[2] Жерон, Орельен. Практическое машинное обучение с помощью Scikit-Learn и TensorFlow: концепции, инструменты и методы для создания интеллектуальных систем. «O’Reilly Media, Inc.», 2017 г.
Для личных контактов относительно статьи или обсуждений машинного обучения / интеллектуального анализа данных или любого отдела науки о данных, не стесняйтесь обращаться ко мне в LinkedIn
