Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 26)

Окончательная версия таблицы:

А теперь моя формула для заполнения каждой ячейки:

На псевдокоде эта формула реализуется так:

if word_a[i] == word_b[j]:    Буквы совпадают

  cell[i][j] = cell[i-1][j-1] + 1    Буквы не совпадают

else:

  cell[i][j] = m a x(cell[i-1][j], cell[i][j-1])

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

• Биологи используют самую длинную общую подпоследовательность для выявления сходства в цепях ДНК. По этой метрике можно судить о сходстве двух видов животных, двух заболеваний и т.д. Самая длинная общая подпоследовательность используется для поиска лекарства от рассеянного склероза.

• Вы когда-нибудь пользовались ключом diff (например, в команде git diff)? Этот ключ выводит информацию о различиях между двумя файлами, а для этого он использует динамическое программирование.

• Мы также упоминали о сходстве строк. Расстояние Левенштейна оценивает, насколько похожи две строки, а для его вычисления применяется динамическое программирование. Расстояние Левенштейна используется в самых разных областях, от проверки орфографии до выявления отправки пользователем данных, защищенных авторским правом.

• Вы когда-нибудь работали в приложении, поддерживающем перенос слов, например Microsoft Word? Как определить, где следует расставить переносы, чтобы длина строки оставалась более или менее постоянной? Динамическое программирование!

Упражнения

9.3 Нарисуйте и заполните таблицу для вычисления самой длинной общей подстроки между строками blue и clues.

Шпаргалка

• Динамическое программирование применяется при оптимизации некоторой характеристики.

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

• В каждом решении из области динамического программирования строится таблица.

• Значения ячеек таблицы обычно соответствуют оптимизируемой характеристике.

• Каждая ячейка представляет подзадачу, поэтому вы должны подумать о том, как разбить задачу на подзадачи.

• Не существует единой формулы для вычисления решений методом динамического программирования.

10. Алгоритм k ближайших соседей

В этой главе

• Вы научитесь строить системы классификации на базе алгоритма k ближайших соседей.

• Вы узнаете об извлечении признаков.

• Вы узнаете о регрессии: прогнозировании чисел (например, завтрашних биржевых котировок или успеха фильма у зрителей).

• Вы познакомитесь с типичными сценариями использования и ограничениями алгоритма k ближайших соседей.

Апельсины и грейпфруты

Взгляните на этот фрукт. Что это, апельсин или грейпфрут? Я слышал, что грейпфруты обычно крупнее, а их кожура имеет красноватый оттенок.

Мой мыслительный процесс выглядит примерно так: у меня в мозге существует некое подобие графика.

Как правило, крупные и красные фрукты оказываются грейпфрутами. Этот фрукт большой и красный, поэтому, скорее всего, это грейпфрут. Но что, если вам попадется фрукт вроде такого?

Как классифицировать этот фрукт? Один из способов — рассмотреть соседей этой точки. Возьмем ее трех ближайших соседей.

Среди соседей больше апельсинов, чем грейпфрутов. Следовательно, этот фрукт, скорее всего, является апельсином. Поздравляем: вы только что применили алгоритм k ближайших соседей для классификации! В целом алгоритм работает по довольно простому принципу.

Алгоритм k ближайших соседей прост, но полезен! Если вы пытаетесь выполнить классификацию чего-либо, сначала попробуйте применить алгоритм k ближайших соседей. Рассмотрим более реалистичный пример.

Построение рекомендательной системы

Представьте, что вы работаете на сайте Netflix и хотите построить систему, которая будет рекомендовать фильмы для ваших пользователей. На высоком уровне эта задача похожа на задачу с грейпфрутами!

Информация о каждом пользователе наносится на график.

Положение пользователя определяется его вкусами, поэтому пользователи с похожими вкусами располагаются недалеко друг от друга. Предположим, вы хотите порекомендовать фильмы Приянке. Найдите пять пользователей, ближайших к ней.

У Джастина, Джей-Си, Джозефа, Ланса и Криса похожие вкусы. Значит, те фильмы, которые нравятся им, с большой вероятностью понравятся и Приянке!

После того как у вас появится такая диаграмма, построить рекомендательную систему будет несложно. Если Джастину нравится какой-нибудь фильм, порекомендуйте этот фильм Приянке.

Однако в картине не хватает одного важного фрагмента. Вы оценивали, насколько близки вкусы двух пользователей на графике. Но как определить, насколько они близки?

Извлечение признаков

В примере с грейпфрутами мы сравнивали фрукты на основании их размера и цвета кожуры. Размер и цвет — признаки, по которым ведется сравнение. Теперь предположим, что у вас есть три фрукта. Вы можете извлечь из них информацию, то есть провести извлечение признаков.

Данные трех фруктов наносятся на график.

Из диаграммы хорошо видно, что фрукты A и B похожи. Давайте измерим степень их сходства. Для вычисления расстояния между двумя точками применяется формула Пифагора.

Например, расстояние между A и B вычисляется так:

Расстояние между A и B равно 1. Другие расстояния вычисляются аналогично.

Формула расстояния подтверждает то, что мы видим: между фруктами A и B есть сходство.

Допустим, вместо фруктов вы сравниваете пользователей Netflix. Пользователей нужно будет как-то нанести на график. Следовательно, каждого пользователя нужно будет преобразовать в координаты — так же, как это было сделано для фруктов.

Когда вы сможете нанести пользователей на график, вы также сможете измерить расстояние между ними.

Начнем с преобразования пользователей в набор чисел. Когда пользователь регистрируется на Netflix, предложите ему оценить несколько категорий фильмов: нравятся они лично ему или нет. Таким образом у вас появляется набор оценок для каждого пользователя!

Приянка и Джастин обожают мелодрамы и терпеть не могут ужасы. Морфеусу нравятся боевики, но он не любит мелодрамы (хороший боевик не должен прерываться слащавой романтической сценой). Помните, как в задаче об апельсинах и грейпфрутах каждый фрукт представлялся двумя числами? Здесь каждый пользователь представляется набором из пяти чисел.

Математик скажет, что вместо вычисления расстояния в двух измерениях вы теперь вычисляете расстояние в пяти измерениях. Тем не менее формула расстояния остается неизменной.

Просто на этот раз используется набор из пяти чисел вместо двух.

Формула расстояния универсальна: даже если вы используете набор из миллиона чисел, расстояние вычисляется по той же формуле. Естественно спросить: какой смысл передает метрика расстояния с пятью числами? Она сообщает, насколько близки между собой эти наборы из пяти чисел.

Это расстояние между Приянкой и Джастином.

Вкусы Приянки и Джастина похожи. А насколько различаются вкусы Приянки и Морфеуса? Вычислите расстояние между ними, прежде чем продолжить чтение.

Сколько у вас получилось? Приянка и Морфеус находятся на расстоянии 24. По этому расстоянию можно понять, что у Приянки больше общего с Джастином, чем с Морфеусом.

Прекрасно! Теперь порекомендовать фильм Приянке будет несложно: если Джастину понравился какой-то фильм, мы рекомендуем его Приянке, и наоборот. Вы только что построили систему, рекомендующую фильмы.

Если вы являетесь пользователем Netflix, то Netflix постоянно напоминает вам: «Пожалуйста, оценивайте больше фильмов. Чем больше фильмов вы оцените, тем точнее будут наши рекомендации». Теперь вы знаете почему: чем больше фильмов вы оцениваете, тем точнее Netflix определяет, с какими пользователями у вас общие вкусы.

Упражнения

10.1 В примере с Netflix сходство между двумя пользователями оценивалось по формуле расстояния. Но не все пользователи оценивают фильмы одинаково. Допустим, есть два пользователя, Йоги и Пинки, вкусы которых совпадают. Но Йоги ставит 5 баллов любому фильму, который ему понравился, а Пинки более разборчива и ставит «пятерки» только самым лучшим фильмам. Вроде бы вкусы одинаковые, но по метрике расстояния они не являются соседями. Как учесть различия в стратегиях выставления оценок?

10.2 Предположим, Netflix определяет группу «авторитетов». Скажем, Квентин Тарантино и Уэс Андерсон относятся к числу авторитетов Netflix, поэтому их оценки оказывают более сильное влияние, чем оценки рядовых пользователей. Как изменить систему рекомендаций, чтобы она учитывала повышенную ценность оценок авторитетов?

Регрессия

А теперь предположим, что просто порекомендовать фильм недостаточно: вы хотите спрогнозировать, какую оценку Приянка поставит фильму. Возьмите 5 пользователей, находящихся вблизи от нее.