Решение
Итоговая версия таблицы выглядит так:
А это моя формула для заполнения ячеек:
На псевдокоде эта формула реализуется так:
if word_a[i] == word_b[j]: Буквы совпадают
cell[i][j] = cell[i-1][j-1] + 1 Буквы несовпадают
else:
cell[i][j] = 0
Аналогичная таблица для строк hish и vista:
Важный момент: в этой задаче окончательное решение далеко не всегда находится в последней ячейке! В задаче о рюкзаке последняя ячейка всегда содержит окончательное решение. Но в задаче поиска самой длинной общей подстроки решение определяется самым большим числом в таблице — и это может быть не последняя, а какая-то другая ячейка.
Вернемся к исходному вопросу: какая строка ближе к hish? У строк hish и fish есть общая подстрока длиной в три буквы. У hish и vista есть общая подстрока из двух букв. Скорее всего, Алекс хотел ввести строку fish.
Самая длинная общая подпоследовательность
Предположим, Алекс ввел строку fosh. Какое слово он имел в виду: fish или fort?
Сравним строки по формуле самой длинной общей подстроки.
Длина подстрок одинакова: две буквы! Но fosh при этом ближе к fish:
Мы сравниваем самую длинную общую подстроку, а на самом деле нужно сравнивать самую длинную общую подпоследовательность: количество букв в последовательности, общих для двух слов. Как вычислить самую длинную общую подпоследовательность?
Ниже приведена частично заполненная таблица для fish и fosh.
Сможете ли вы определить формулу для этой таблицы? Самая длинная общая подпоследовательность имеет много общего с самой длинной общей подстрокой, и их формулы тоже очень похожи. Попробуйте решить задачу самостоятельно, а я приведу ответ ниже.
Самая длинная общая подпоследовательность — решение
Окончательная версия таблицы:
А теперь моя формула для заполнения каждой ячейки:
На псевдокоде эта формула реализуется так:
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 определяет, с какими пользователями у вас общие вкусы.