Грокаем а Иллюстрированное пособие для программистов и любопытствующих

ПРОДШКТЕ!

Шпаргалка

Надеюсь, вы хотя бы в общих чертах поняли, что можно сделать с помощью алгоритма k ближайших соседей и машинного обучения! Машинное обу­чение — интересная область, и при желании в нее можно зайти достаточно глубоко.
□ Алгоритм k ближайших соседей применяется для классификации и ре­грессии. В нем используется проверка k ближайших соседей.

• 
  Классификация = распределение по категориям.
  
• 
  Регрессия = прогнозирование результата (например, в виде числа).
  
• 
  «Извлечением признаков» называется преобразование элемента (на­пример, фрукта или пользователя) в список чисел, которые могут ис­пользоваться для сравнения.
  
• 
  Качественный выбор признаков — важная часть успешного алгоритма k ближайших соседей.
  

Ч


В этой главе

• 
  Приводится краткий обзор 10 алгоритмов, которые не рассматривались в книге. Вы узнаете, для чего нужны эти алгоритмы.
  
• 
  Я порекомендую книги, которые стоит читать дальше в зависимости от того, какие темы представляют инте­рес для вас.
  

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

то дальше?
возникает проблема: каждый раз, когда на сайте регистрируется новый пользователь, придется заново сортировать массив, потому что бинарный поиск работает только с отсортированными массивами. Насколько удобнее было бы вставить пользователя в правильную ячейку массива, чтобы потом его не пришлось сортировать заново! Именно эта идея заложена в основу структуры данных бинарного дерева поиска.
Бинарное дерево поиска выглядит так:



Для каждого узла все узлы левого поддерева содержат меньшие значения, а все узлы правого поддерева — большие значения.



Предположим, вы ищете узел Maggie. Поиск начинается с корневого узла.
1



Строка Maggie идет после David, поэтому идем направо.



Строка Maggie предшествует Manning, поэтому идем налево.



Мы нашли узел Maggiel В целом процедура поиска напоминает бинарный поиск. Поиск элемента в бинарном дереве поиска в среднем выполняется
за время 0(log п), а в худшем случае — за время 0(п). Поиск в отсортиро­ванном массиве выполняется за время O(log п) в худшем случае — казалось бы, отсортированный массив эффективнее. Однако бинарное дерево поиска в среднем работает намного быстрее при удалении и вставке элементов.

	АААССИ6
поиск
ЬСТАВКА	ом
УДАЛЕНИЕ	ом