Вернемся к исходному вопросу: какая строка ближе к 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 и хотите построить систему, которая будет рекомендовать фильмы для ваших пользователей. На высоком уровне эта задача похожа на задачу с грейпфрутами!
Информация о каждом пользователе наносится на график.
Положение пользователя определяется его вкусами, поэтому пользователи с похожими вкусами располагаются недалеко друг от друга. Предположим, вы хотите порекомендовать фильмы Приянке. Найдите пять пользователей, ближайших к ней.
У Джастина, Джей-Си, Джозефа, Ланса и Криса похожие вкусы. Значит, те фильмы, которые
