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

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

В предыдущей статье было про: динамическое программирование. Здесь далее текст пойдёт об алгоритме k ближайших соседей.

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

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

Представьте, что вы работаете с сайтом о кино и хотите построить систему, которая будет рекомендовать фильмы для ваших пользователей. Положение пользователя определяется его вкусами, поэтому пользователи с похожими вкусами располагаются недалеко друг от друга. Предположим, вы хотите порекомендовать фильмы Алексею. Найдите 5 пользователей, ближайших к нему. Допустим, окажется, что у Ивана, Сергея, Анны, Ларисы и Анатолия похожие вкусы. Значит, те фильмы, которые нравятся им, с большой вероятностью понравятся и Алексею! После того как у вас появится такая диаграмма, построить рекомендательную систему будет несложно. Если Анатолию нравится какой-нибудь фильм, порекомендуйте этот фильм Алексею. Однако в картине не хватает одного важного фрагмента. Вы сравнивали вкусы двух пользователей. Но как определить, насколько они близки?

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

В примере с фруктами можно сравнивать фрукты на основании их размера и цвета кожуры. Размер и цвет — признаки, по которым ведется сравнение. Теперь предположим, что у вас есть три фрукта. Вы можете извлечь из них информацию, то есть провести извлечение признаков. Данные этих фруктов наносятся на график. Предположим, что из диаграммы хорошо видно, что фрукты A и B похожи. Давайте измерим степень их сходства. Для вычисления расстояния между двумя точками применяется формула Пифагора: Формула расстояния подтверждает то, что мы видим: между фруктами есть или отсутствует сходство. Допустим, вместо фруктов вы сравниваете пользователей. Пользователей нужно будет как-то нанести на график. Следовательно, каждого пользователя нужно будет преобразовать в координаты. Когда вы сможете нанести пользователей на график, вы также сможете измерить расстояние между ними. Начнем с преобразования пользователей в набор чисел. Когда пользователь регистрируется на сайте, предложите ему оценить несколько категорий фильмов: нравятся они лично ему или нет. Таким образом у вас появляется набор оценок для каждого пользователя! И в итоге каждый пользователь представляется набором из чисел. Вместо вычисления расстояния в двух измерениях вы теперь вычисляете расстояние в n измерениях(зависит от категорий жанров у фильмов). Тем не менее формула расстояния остается неизменной: Формула расстояния универсальна: даже если вы используете набор из миллиона чисел, расстояние вычисляется по той же формуле. Естественно спросить: какой смысл передает метрика расстояния с пятью числами? Она сообщает, насколько близки между собой эти наборы из пяти чисел.

Массивы чисел, такие как(2, 2) или (3, 4, 4, 1, 4) называются векторами. Если вам встретится статья о машинном обучении и вы увидите, что авторы говорят о векторах, знайте, что они имеют в виду подобный массив чисел.

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

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

Регрессия

А теперь предположим, что просто порекомендовать фильм недостаточно: вы хотите спрогнозировать, какую оценку Алексей поставит фильму. Возьмите 5 пользователей, находящихся вблизи от нее. В числе «5» нет ничего особенного: с таким же успехом можно взять 2 ближайших пользователей, 10 или 10 000. Поэтому-то алгоритм и называется «алгоритмом k ближайших пользователей», а не «алгоритмом 5 ближайших пользователей»! Допустим, вы пытаетесь угадать оценку Алексея для фильма «». Как этот фильм оценили Иван, Сергей, Лариса, Ольга и Антон?

Если вычислить среднее арифметическое их оценок, вы получите 4,2. Такой метод прогнозирования называется регрессией. У алгоритма k ближайших соседей есть два основных применения — классификация и регрессия:

• классификация = распределение по категориям;
• регрессия = прогнозирование ответа (в числовом выражении).

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

• погода по шкале от 1 до 5 (1 = плохая, 5 = отличная);
• праздник или выходной (1, если сегодня праздник или выходной, 0 в противном случае);
• проходят ли сегодня спортивные игры (1 = да, 0 = нет).

И вы знаете, сколько буханок хлеба было продано в прошлом при разных сочетаниях признаков. A(5,1,0) = 300 буханок; B(3,1,1) = 225; C(1,1,0) = 75; D(4,0,1) = 200; E(4,0,0) = 150; F(2,0,0) = 50.

Сегодня выходной и хорошая погода. Сколько буханок вы продадите на основании только что приведенных данных? Используем алгоритм k ближайших соседей для k = 4. Сначала определим четырех ближайших соседей для этой точки: (4,1,0) = ?. Ниже перечислены расстояния. Точки A, B, D и E являются ближайшими: A - 1, B - 2, C - 9, D - 2, E - 1, F - 5. Вычисляя среднее арифметическое продаж в эти дни, вы получаете ≈ 218. Значит, именно столько буханок нужно выпекать на сегодня!

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

Выбор признаков

Чтобы подобрать рекомендации, вы предлагаете пользователям ставить оценки категориям фильмов. А если бы вы вместо этого предлагали им ставить оценки картинкам? Наверное, вам удалось бы найти пользователей, которые ставили похожие оценки этим картинкам. Однако у вас получилась бы самая плохая рекомендательная система в мире, потому что эти «признаки» не имеют никакого отношения к их вкусам в области кино! Или представьте, что вы предлагаете пользователям оценить фильмы для формирования рекомендаций — но только «Игру престолов», «Игру престолов-2» и «Игру престолов-3». Эти оценки ничего не скажут вам о вкусах пользователей. Когда вы работаете с алгоритмом k ближайших соседей, очень важно правильно выбрать признаки для сравнения. Под правильным выбором признаков следует понимать:

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

Как вы думаете, оценки хорошо подходят для рекомендации фильмов? Возможно, я поставил «Золушке» более высокую оценку, чем «Охотникам за приведениями», но на самом деле я провел больше времени за просмотром «Охотников». Как улучшить рекомендательную систему? Возвращаясь к примеру с пекарней: сможете ли вы придумать два хороших и два плохих признака, которые можно было бы выбрать для прогнозирования объема выпечки? Возможно, нужно выпечь побольше хлеба после рекламы в газете. Или увеличить объем производства по понедельникам. В том, что касается выбора хороших признаков, не существует единственно правильного ответа. Тщательно продумайте все факторы, которые необходимо учесть при прогнозировании.

Знакомство с машинным обучением

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

OCR

Сокращение OCR означает «Optical Character Recognition», то есть «оптическое распознавание текста». Иначе говоря, вы берете фотографию страницы текста, а компьютер автоматически преобразует изображение в текст. Google использует OCR для оцифровки книг. Как работает OCR? Для примера возьмем следующую цифру: 7.

Как автоматически определить, что это за цифра? Можно воспользоваться алгоритмом k ближайших соседей:

1. Переберите изображения цифр и извлеките признаки.
2. Получив новое изображение, извлеките признаки и проверьте ближайших соседей.

По сути, это та же задача, что и задача классификации. В общем случае алгоритмы OCR основаны на выделении линий, точек и кривых. Затем при получении нового символа из него можно извлечь те же признаки. Извлечение признаков в OCR происходит сложнее чем в задачах классификации. Однако важно понимать, что даже сложные технологии строятся на основе простых идей(таких, как алгоритм k ближайших соседей). Те же принципы могут использоваться для распознавания речи или лиц. Когда вы отправляете фотографию на Яндекс Диск, иногда сервису Яндекса хватает сообразительности для автоматической пометки людей на фото. Да это машинное обучение в действии! Первый шаг OCR, в ходе которого перебираются изображения цифр и происходит извлечение признаков, называется тренировкой. В большинстве алгоритмов машинного обучения присутствует фаза тренировки: прежде чем компьютер сможет решить свою задачу, его необходимо натренировать. В следующем примере рассмотрим создание спам-фильтров, и в нем тоже есть шаг тренировки.

Построение спам-фильтра

Спам-фильтры используют другой простой алгоритм, называемый наивным классификатором Байеса. Сначала наивный классификатор Байеса тренируется на данных. Предположим, вы получили сообщение с темой «Получите свой миллион прямо сейчас!» Это спам? Предложение можно разбить на слова, а затем для каждого слова проверить вероятность присутствия этого слова в спам сообщении. Например, в нашей очень простой модели слово «миллион» встречается только в спаме. Наивный классификатор Байеса вычисляет вероятность того, что сообщение с большой вероятностью является спамом. На практике он применяется примерно для тех же целей, что и алгоритм k ближайших соседей. Например, наивный классификатор Байеса может использоваться для классификации фруктов: есть большой и красный фрукт. Какова вероятность того, что он окажется грейпфрутом? Это простой, но весьма эффективный алгоритм — из тех, что нравятся больше всего!

Прогнозы на биржевых торгах

Есть одна задача, в которой трудно добиться успеха машинным обучением: точно спрогнозировать курсы акций на бирже. Как выбрать хорошие признаки? Предположим, вы говорите, что если курс акций рос вчера, то он будет расти и сегодня. Хороший это признак или нет? Или, предположим, вы утверждаете, что курс всегда снижается в апреле. Сработает или нет? Не существует гарантированного способа прогнозировать будущее на основании прошлых данных. Прогнозирование будущего — сложное дело, а при таком количестве переменных оно становится почти невозможным.

Тренировка модели машинного обучения

Тренировка нейросети МО состоит из нескольких основных этапов:

1. Сбор данных
2. Анализ и очистка данных
3. Извлечение признаков
4. Процесс обучения на тестовых данных
5. Проверка на новых данных
6. Проверка(валидация) и корректировка модели

Рассмотрим последовательность действий по тренировке модели МО. Все начинается со сбора данных. В примере с рекомендательной системой по фильмам данными были оценки пользователей. Затем необходимо провести очистку данных, то есть удаление неподходящих данных. Например, какой-нибудь пользователь не пожелал оценивать фильмы, поэтому расставил случайные оценки и перешел к следующему экрану. Такие данные необходимо удалить из набора. После этого требуется извлечь из данных признаки. Получив признаки, можно переходить к тренировке модели. Выберите модель — например, k ближайших соседей, создайте структуру нейронов и саму нейросеть — и проведите ее тренировку на 90% данных. Оставьте около 10% данных для проверки модели. После того как модель пройдет обучение, протестируйте ее, предложив ей составить прогноз. Чтобы оценить качество прогноза, используйте зарезервированные или новые данные. Например, вы хотите проверить рекомендательную модель фильмов. Можно спросить, понравились ли некоторому пользователю некоторые фильмы и сериалы. Модель выдаёт прогнозы. А мы при этом заранее знаем, какие фильмы нравятся пользователю, — эта информация содержится в 10 % данных, которые мы зарезервировали. Эти зарезервированные данные сравниваются с прогнозами модели. После сравнения результатов модели и реальных данных, можно сделать вывод о том, что модель выдала хороший результат или не очень. Хороший результат у модели получается тогда, когда числа достаточно близки к реальным оценкам пользователя. Этот шаг тестирования модели называется проверкой (или валидацией) модели. После проверки можно вернуться к модели и скорректировать ее. Представьте, что вы построили модель k ближайших соседей, в которой k = 5. Можно опробовать ее с k = 7, чтобы посмотреть, не даст ли она лучший результат. Это называется корректировкой(или подкруткой) параметров. После того как вы завершите тренировку и оценку модели, ваша модель будет готова к работе. Так выглядит процедура построения модели МО в общем случае.

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

Ещё об алгоритмах

Ниже краткий обзор 10 алгоритмов, которые не рассматривались. Вы узнаете, для чего нужны эти алгоритмы. А также рекомендация книг, которые стоит читать дальше в зависимости от того, какие темы вам интересны.

Линейная регрессия

Представьте, что вы хотите продать свой дом. Его площадь составляет 300 квадратных метров. Вы изучаете описания домов, недавно проданных по соседству:

1. 100 кв. метров 10 миллионов рублей;
2. 200 кв. метров 13 миллионов рублей;
3. 400 кв. метров 25 миллионов рублей.

Какую цену вы бы назначили за свой дом, исходя из этой информации? Ниже представлено одно из возможных решений. Сначала вы наносите все точки на график. Затем соединяете их прямой линией(отсюда и название линейная).

Теперь вы видите, где на этой линии находится точка 300 квадратных метров. Соответствующую ей цену можно сделать начальной ценой. Так работает линейная регрессия. Она выстраивает линию из заданной группы точек, а затем использует эту линию для вычисления прогнозов. Линейная регрессия уже давно применяется в статистике, а теперь и в машинном обучении, поскольку это метод, с которого легко начинать. Линейная регрессия полезна, если значения непрерывны. Если вам нужно сделать прогноз, проще всего использовать именно линейную регрессию.

Инвертированные индексы

Перед вами сильно упрощенное объяснение того, как работает поисковая система. Допустим, имеются три веб-страницы с простым содержимым. Строиться хеш-таблица для этого содержимого или проще python словарь. Ключами словаря являются слова, а значения указывают, на каких страницах встречается каждое слово. Теперь предположим, что пользователь ищет слово "python". Далее проверяется, на каких страницах это слово встречается. Пусть, слово встречается на страницах А и B. Выведем эти страницы в результатах поиска. Или предположим, что пользователь ищет слово "питон". И система проверяет, что это слово встречается на страницах A и C. Несложно, верно? Хеш-таблица — это очень полезная структура данных: хеш-таблица, связывающая слова с местами, в которых эти слова встречаются. Такая структура данных, называемая инвертированным индексом, часто используется для построения поисковых систем. Если вас интересует область поиска, эта тема станет хорошей отправной точкой для дальнейшего изучения.

Преобразование Фурье

Преобразование Фурье — действительно выдающийся алгоритм: великолепный, элегантный и имеющий миллион практических применений. Пример для преобразования Фурье: если у вас есть коктейль, преобразование Фурье сообщает, из каких ингредиентов он состоит. Или для заданной песни преобразование разделяет ее на отдельные частоты. Оказывается, эта простая идея находит множество практических применений. Например, если песню можно разложить на частоты, вы можете усилить тот диапазон, который вас интересует, — скажем, усилить низкие частоты и приглушить высокие. Преобразование Фурье прекрасно подходит для обработки сигналов. Также оно может применяться для сжатия музыки: сначала звуковой файл разбивается на составляющие. Преобразование Фурье сообщает, какой вклад вносит каждая составляющая в музыку, что позволяет исключить несущественные составляющие. Собственно, именно так работает музыкальный формат MP3! Музыка — не единственный вид цифровых сигналов. Графический формат JPG также использует сжатие и работает по тому же принципу. Кроме того, преобразование Фурье применяется для прогнозирования землетрясений и анализа ДНК. С его помощью можно построить приложение, которое находит песни по отрывкам. Преобразование Фурье очень часто применяется на практике! Подробнее о преобразовании Фурье в работе со звуком есть отличная статья.

Параллельные алгоритмы

Следующие три темы связаны с масштабируемостью и обработкой больших объемов данных. Когда-то компьютеры становились все быстрее и быстрее. Если вы хотели, чтобы ваш алгоритм работал быстрее, можно было подождать несколько месяцев и запустить программу на более мощном компьютере. Но сейчас этот период подошел к концу. Современные компьютеры и ноутбуки оснащаются многоядерными процессорами. Чтобы алгоритм заработал быстрее, необходимо преобразовать его в форму, подходящую для параллельного выполнения сразу на всех ядрах! Рассмотрим простой пример. Лучшее время выполнения для алгоритма сортировки равно приблизительно O(n log n). Известно, что массив невозможно отсортировать за время O(n), если только не воспользоваться параллельным алгоритмом! Существует параллельная версия быстрой сортировки, которая сортирует массив за время O(n). Параллельный алгоритм трудно разработать. И так же трудно убедиться в том, что он работает правильно, и понять, какой прирост скорости он обеспечивает. Одно можно заявить твердо: выигрыш по времени нелинеен. Следовательно, если процессор вашего компьютера имеет два ядра вместо одного, из этого не следует, что ваш алгоритм по волшебству заработает вдвое быстрее. Это объясняется несколькими причинами:

• Затраты ресурсов на управление параллелизмом — допустим, нужно отсортировать массив из 1000 элементов. Как разбить эту задачу для выполнения на двух ядрах? Выделить каждому ядру 500 элементов, а затем объединить два отсортированных массива в один большой отсортированный массив? Слияние двух массивов требует времени.
• Закон Амдала — представьте, что вы пишете картину. Это занимает очень много времени, допустим около 30 часов. В идеале вам хотелось бы уложиться в 10 часов. Вы решаете оптимизировать процесс. Для этого разбиваете его на два шага: (1) эскиз и (2) рисование красками. Исходный эскиз не обязательно рисовать вручную — конечно, с помощью трейсинга(обводки) это делается быстрее. Но при следующей попытке на картину уходит 29 часов и 5 минут! Что произошло? Раньше эскиз занимал 1 час. Вы сократили его до 5 минут, что стало значительным улучшением. Тем не менее бóльшая часть времени приходится на рисование красками, так что оптимизация оказалась незначительной. Это проявление так называемого закона Амдала. Он гласит, что при оптимизации одной части системы выигрыш в производительности ограничивается тем, какую долю времени занимает эта часть. В данном случае время создания эскиза сокращается до 1/12 исходного значения. При этом экономятся 55 минут. Если бы нам удалось сократить время рисования красками в той же степени, это сэкономило бы 2090 минут!Ускоряя алгоритм за счет параллелизации, подумайте, какую его часть следует распараллелить — создание эскиза или рисование?
• Распределение нагрузки — допустим, необходимо выполнить 10 задач, и вы назначаете каждому ядру 5 задач. Однако ядру A достаются все простые задачи, поэтому оно выполняет свою работу за 10 секунд, тогда как ядро B справится со сложными задачами только за минуту. Это означает, что ядро A целых 50 секунд простаивает, пока ядро B выполняет всю работу! Как организовать равномерное распределение работы, чтобы оба ядра трудились с одинаковой интенсивностью?

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

MapReduce

Существует разновидность параллельных алгоритмов, которая в последнее время активно набирает популярность: распределенные алгоритмы. Конечно, параллельный алгоритм удобно запускать на компьютере, если для его выполнения требуется от двух до четырех ядер. Но если нужны сотни? Тогда алгоритм записывают так, чтобы он мог выполняться на множестве машин. Компания Google популяризировала распределенный алгоритм, который называется MapReduce, но его функции известны уже давно. Для чего нужны распределенные алгоритмы? Предположим, имеется таблица с миллиардами или триллионами записей и к ней нужно сделать сложный запрос SQL. В MySQL это сделать не удастся, потому что MySQL начнет «тормозить» уже после нескольких миллиардов записей. Используйте MapReduce! Или, предположим, вам нужно обработать длинный список задач. Обработка каждой задачи занимает 10 секунд, а всего в списке 1 миллион задач. Если выполнять эту работу на одном компьютере, она займет несколько месяцев! Если бы ее можно было выполнить на 100 машинах, работа завершилась бы за несколько дней. Распределенные алгоритмы хорошо работают в ситуациях, когда нужно выполнить большой объем работы за максимально короткое время.

Фильтры Блума и HyperLogLog

Представьте себя на месте сайта Reddit. Когда пользователь публикует ссылку, нужно проверить, публиковалась ли эта ссылка ранее. Истории, которые еще не публиковались, считаются более ценными. Или представьте себя на месте поискового бота Google. Обрабатывать веб-страницу нужно только в том случае, если она еще не обрабатывалась ранее. Итак, нужно проверить, обрабатывалась ли страница ранее. Или представьте себя на месте bit.ly — сервиса сокращения URL. Пользователи не должны перенаправляться на вредоносные сайты. У вас имеется набор URL-адресов, которые считаются вредоносными. Теперь нужно выяснить, не направляется ли пользователь на URL-адрес из этого набора. Во всех этих примерах возникает одна проблема. Имеется очень большой набор данных. Появляется новый объект, и вы хотите узнать, содержится ли он в существующем наборе. Эта задача быстро решается при помощи хеша. Например, представьте, что Google создает большой хеш, ключами которого являются все обработанные страницы. Как узнать, обрабатывался ли сайт ashtana.ru? Нужно заглянуть в хеш. У ashtana.ru имеется свой ключ в хеше, а значит, адрес уже обрабатывался. Среднее время обращения к элементам в хеш-таблице составляет O(1). Таким образом, вы узнали о том, что страница ashtana.ru уже проиндексирована за постоянное время. Неплохо! Вот только этот хеш получится просто огромным. Google индексирует триллион веб-страниц. Если хеш содержит все URL-адреса, индексируемые Google, он займет слишком много места. У Reddit и bit.ly возникает аналогичная проблема. Сталкиваясь с такими объемами данных, приходится действовать более изобретательно!

Фильтры Блума

Для решения проблемы можно воспользоваться вероятностными структурами данных, которые называются фильтрами Блума. Они дают ответ, который может оказаться ложным, но с большой вероятностью является правильным. Вместо того чтобы обращаться к хешу, вы спрашиваете у фильтра Блума, обрабатывался ли этот URL-адрес ранее. Хеш-таблица даст точный ответ. Фильтр Блума дает ответ, правильный с высокой вероятностью:

• возможны ложноположительные срабатывания. Фильтр скажет: «Этот сайт уже обрабатывался», хотя этого не было;
• ложноотрицательные срабатывания исключены. Если фильтр утверждает, что сайт не обрабатывался, вы можете быть в этом уверены.

Фильтры Блума хороши тем, что занимают очень мало места. Хеш-таблице пришлось бы хранить все URL-адреса, обрабатываемые Google, а фильтру Блума это не нужно. Фильтр Блума очень удобен тогда, когда нет необходимости в точном ответе(как во всех приведенных примерах).

HyperLogLog

Примерно так же действует другой алгоритм, который называется HyperLogLog. Предположим, Google хочет подсчитать количество уникальных поисков, выполненных пользователями. Или Amazon хочет подсчитать количество уникальных предметов, просмотренных пользователями за сегодняшний день. Для получения ответов на эти вопросы потребуется очень много места! Так, в примере с Google придется вести журнал всех уникальных вариантов поиска. Когда пользователь что-то ищет, вы сначала проверяете, присутствует ли условие в журнале, и если нет, добавляете его. Даже для одного дня этот журнал получится гигантским. HyperLogLog аппроксимирует количество уникальных элементов в множестве. Как и фильтры Блума, он не дает точного ответа, но выдает достаточно близкий результат с использованием малой части памяти, которую обычно занимает такая задача. Если вы используете большие объемы данных и вас устраивают приближенные ответы — воспользуйтесь вероятностными алгоритмами!

HTTPS и обмен ключами Диффи — Хеллмана

HTTPS — опора современного интернета. Этот протокол обеспечивает безопасные онлайн-транзакции, от ввода пароля до оплаты покупок. Работа HTTPS основана на шифровании сообщений между клиентом и сервером. Как же работает шифрование? Функции передаются сообщение и секретный ключ. Затем функция генерирует зашифрованное сообщение. Чтобы расшифровать его, передайте зашифрованное сообщение и тот же ключ функции, и вы получите исходное сообщение. Когда вы отправляете данные серверу, ваш браузер зашифровывает сообщение, после чего сервер расшифровывает его. Да, кроме одного: как проверить, что браузер и сервер используют один и тот же ключ? Помните, что для работы HTTPS обе стороны должны иметь одинаковые ключи. Но как задать ключ, чтобы никто его не видел? Если отправить ключ серверу, злоумышленник сможет перехватить этот ключ. Как задать ключ, чтобы только браузер и сервер знали его? Задача кажется неразрешимой, но это не так! Для ее решения существует очень умный алгоритм, называемый обменом ключей Диффи — Хеллмана.

Ниже описано, как работает алгоритм Диффи — Хеллмана. На шаге 1 мы генерируем собственные ключи. Я — клиент, и я генерирую ключ для себя. Сервис также генерирует ключ. Эти ключи разные. Мы не знаем ключи друг друга, они закрытые. В реальности ключи представляют собой байты. На шаге 2 генерируется общий шаблон. Это открытый шаблон. Он виден обеим сторонам и всем остальным. Нам неважно, кто его видит. На шаге 3 этот шаблон совмещается с закрытыми ключами. В результате мы получаем открытые ключи. Раз они открытые, нас не интересует, кто их видит. Сервер видит мой открытый ключ, а я вижу его открытый ключ. Наконец, на шаге 4 я получаю открытый ключ сервера и совмещаю его со своим закрытым ключом. Сервис делает то же самое с моим открытым ключом. Теперь у нас одинаковые ключи! У каждого из нас есть ключ, объединяющий три шаблона. Нам удалось задать ключ, не отправляя ключи друг другу. Заданный ключ называется общим секретом; так работает обмен ключами Диффи — Хеллмана.

HTTPS — интересная и важная часть нашей повседневной жизни. Вот немного терминологии, связанной с HTTPS:

• TLS — протокол безопасности транспортного уровня (Transport Layer Security). TLS используется для установления безопасного соединения.
• SSL — прежнее название TLS, но люди часто не различают их. Если вы слышите, как кто-то упоминает SSL, то, скорее всего, речь идет о TLS. В этом протоколе часто находят дефекты безопасности, поэтому его постоянно приходится обновлять. Протокол TLS впервые появился в 1999 году. Все версии протокола SSL, выпущенные до TLS, небезопасны.
• Шифрование с симметричным ключом — в нашем примере выше обе стороны используют одинаковые ключи. Но существует и асимметричное шифрование с открытым ключом, когда обе стороны используют разные ключи. Я говорю о шифровании с симметричным ключом, потому что оно используется HTTPS.

HTTPS использует измененную версию обмена ключей Диффи — Хеллмана, называемую эфемерным обменом ключей Диффи — Хеллмана. Она работает так же, как было показано, кроме того, что закрытые ключи генерируются заново для каждого соединения. Это означает, что даже если злоумышленнику станет известен один из закрытых ключей, он сможет расшифровать сообщения только одного соединения. Криптография — интересная и глубокая тема, в которую можно сильно погрузиться.

Локально-чувствительное хеширование

Многие хеш-функции имеют одну важную особенность: они являются локально-нечувствительными. Предположим, имеется строка, для которой генерируется хеш-код с помощью алгоритма SHA-256: dog → cd6357. Если изменить в строке всего один символ, а потом сгенерировать хеш заново, строка полностью изменяется! И это хорошо, потому что сравнение хешей не позволит атакующему определить, насколько он близок к взлому пароля. Иногда требуется обратный результат: локально-чувствительная функция хеширования. Здесь на помощь приходит алгоритм Simhash. При незначительном изменении строки Simhash генерирует хеш-код, который почти не отличается от исходного. Это позволяет сравнивать хеш-коды и определять, насколько похожи две строки, — весьма полезная возможность! Примеры использования Simhash:

• Google использует Simhash для выявления дубликатов в процессе индексирования.
• Система проверки на антиплагиат может использовать Simhash для обнаружения плагиата(копирования рефератов из интернета).
• Книжное издательство позволяет пользователям загружать документы или книги, чтобы они стали доступны для других пользователей. Но издатель не хочет, чтобы пользователи размещали информацию, защищенную авторским правом! С помощью Simhash сайт может обнаружить, что отправленная информация похожа на изданную книгу, и при обнаружении сходства автоматически запретить ее размещение.
• Simhash используется для выявления сходства между фрагментами текста.

Минимальные кучи и приоритетные очереди

Минимальная куча — структура данных, построенная на базе деревьев. В таких кучах хранятся числа. Минимальные кучи позволяют быстро найти наименьший элемент кучи, потому что наименьшее значение всегда находится в корне. Это самое важное свойство минимальной кучи, и наименьший элемент находится за время O(1). Или же за время O(log n) его можно удалить из кучи, заменив новым минимумом. Благодаря кучам проводить сортировку очень легко — просто продолжая запрашивать минимальное значение. И сохранять значения по порядку. В конце куча будет пустой, а у вас появится отсортированный список чисел! Такой алгоритм называется пирамидальной сортировкой, или сортировкой кучей. Максимальные кучи (невозрастающие пирамиды) очень похожи на минимальные, но у них в корне хранится наибольшее значение. Кучи отлично подходят для реализации приоритетных очередей. Вспомните, что очереди относятся к категории FIFO (First In, First Out — «первым пришел, первым вышел»). С другой стороны, стек относится к структуре данных LIFO(Last In, First Out — «последним пришел, первым вышел»). Приоритетная очередь похожа на обычную очередь, не считая того, что при запросе элемента приоритетная очередь выдает элемент с наибольшим приоритетом. Приоритетная очередь отлично подходит для реализации списка задач. Сначала вы сохраняете в списке задачи, а затем запрашиваете задачу для работы; приоритетная очередь выдает задачу с наибольшим приоритетом. Приоритетные очереди также используются для реализации эффективной версии алгоритма Дейкстры.

Линейное программирование

Линейное программирование — одна из самых интересных областей, которые мне известны. Линейное программирование используется для максимизации некоторой характеристики при заданных ограничениях. Предположим, ваша компания выпускает два продукта: рубашки и сумки. На рубашку требуется 1 метр ткани и 5 пуговиц. На изготовление сумки необходимо 2 метра ткани и 2 пуговицы. У вас есть 11 метров ткани и 20 пуговиц. Рубашка приносит прибыль 200 рублей, а сумка — 300. Сколько рубашек и сумок следует изготовить для получения максимальной прибыли? Здесь мы пытаемся максимизировать прибыль, а ограничения определяют количество имеющихся материалов. Другой пример: вы политик, пытающийся получить максимальное количество голосов. Предположим, что исследования показали, что на каждый голос жителя Белгорода требуется примерно 1 час работы (маркетинг, исследования и т.д.), а на каждый голос жителя Курска — 1,5 часа. Вам нужны голоса как минимум 500 жителей Белгорода и как минимум 300 жителей Курска. В вашем распоряжении 50 дней. Кроме того, затраты на жителя Белгорода составляют 200 рублей, а на жителя Курска — 100. Ваш бюджет составляет 1500000 рублей. Какое максимальное количество голосов вы сможете получить от жителей двух городов? На этот раз вы стремитесь к максимуму голосов при ограничениях по времени и деньгам. Возможно, вы подумаете: «Есть много задач решающие вопросы оптимизации. Как они связаны с линейным программированием?» Все алгоритмы, работающие с графами, могут быть реализованы средствами линейного программирования. Линейное программирование — намного более общая область, а задачи с графами составляют ее подмножество. В линейном программировании используется симплекс-метод. Этот алгоритм достаточно сложен, поэтому я не привожу его. Если вы заинтересуетесь различными задачами оптимизации, поищите информацию о линейном программировании!

Надеюсь, этот краткий обзор показал, как много всего ещё можно узнать. Я считаю, что лучший способ узнать что-то — найти тему, которая вас интересует, и постоянно изучать её!