- •Об авторе
- •Предисловие
- •Для кого эта книга
- •О чем эта книга
- •Что вам потребуется при чтении этой книги
- •Условные обозначения
- •От издательства
- •Глава 1. Обзор алгоритмов
- •Что такое алгоритм
- •Этапы алгоритма
- •Определение логики алгоритма
- •Псевдокод
- •Использование сниппетов
- •Создание плана выполнения
- •Введение в библиотеки Python
- •Библиотеки Python
- •Реализация Python с помощью Jupyter Notebook
- •Методы разработки алгоритмов
- •Параметры данных
- •Параметры вычислений
- •Анализ производительности
- •Анализ пространственной сложности
- •Анализ временной сложности
- •Оценка эффективности
- •Выбор алгоритма
- •«О-большое»
- •Проверка алгоритма
- •Точные, приближенные и рандомизированные алгоритмы
- •Объяснимость алгоритма
- •Резюме
- •Глава 2. Структуры данных, используемые в алгоритмах
- •Структуры данных в Python
- •Список
- •Кортеж
- •Словарь
- •Множество
- •DataFrame
- •Матрица
- •Абстрактные типы данных
- •Вектор
- •Стек
- •Очередь
- •Базовый принцип использования стеков и очередей
- •Дерево
- •Резюме
- •Глава 3. Алгоритмы сортировки и поиска
- •Алгоритмы сортировки
- •Обмен значений переменных в Python
- •Сортировка пузырьком
- •Сортировка вставками
- •Сортировка слиянием
- •Сортировка Шелла
- •Сортировка выбором
- •Алгоритмы поиска
- •Линейный поиск
- •Бинарный поиск
- •Интерполяционный поиск
- •Практическое применение
- •Резюме
- •Глава 4. Разработка алгоритмов
- •Знакомство с основными концепциями разработки алгоритма
- •Вопрос 1. Даст ли разработанный алгоритм ожидаемый результат?
- •Вопрос 2. Является ли данный алгоритм оптимальным способом получения результата?
- •Вопрос 3. Как алгоритм будет работать с большими наборами данных?
- •Понимание алгоритмических стратегий
- •Стратегия «разделяй и властвуй»
- •Стратегия динамического программирования
- •Жадные алгоритмы
- •Практическое применение — решение задачи коммивояжера
- •Использование стратегии полного перебора
- •Использование жадного алгоритма
- •Алгоритм PageRank
- •Постановка задачи
- •Реализация алгоритма PageRank
- •Знакомство с линейным программированием
- •Практическое применение — планирование производства с помощью линейного программирования
- •Резюме
- •Глава 5. Графовые алгоритмы
- •Представление графов
- •Типы графов
- •Особые типы ребер
- •Эгоцентрические сети
- •Анализ социальных сетей
- •Введение в теорию сетевого анализа
- •Кратчайший путь
- •Создание окрестностей
- •Показатели центральности
- •Вычисление показателей центральности с помощью Python
- •Понятие обхода графа
- •BFS — поиск в ширину
- •DFS — поиск в глубину
- •Практический пример — выявление мошенничества
- •Простой анализ мошенничества
- •Анализ мошенничества методом сторожевой башни
- •Резюме
- •Глава 6. Алгоритмы машинного обучения без учителя
- •Обучение без учителя
- •Обучение без учителя в жизненном цикле майнинга данных
- •Современные тенденции исследований в области обучения без учителя
- •Практические примеры
- •Алгоритмы кластеризации
- •Количественная оценка сходства
- •Иерархическая кластеризация
- •Оценка кластеров
- •Применение кластеризации
- •Снижение размерности
- •Метод главных компонент (PCA)
- •Ограничения PCA
- •Поиск ассоциативных правил
- •Примеры использования
- •Анализ рыночной корзины
- •Ассоциативные правила
- •Оценка качества правила
- •Алгоритмы анализа ассоциаций
- •Практический пример — объединение похожих твитов в кластеры
- •Тематическое моделирование
- •Кластеризация
- •Алгоритмы обнаружения выбросов (аномалий)
- •Использование кластеризации
- •Обнаружение аномалий на основе плотности
- •Метод опорных векторов
- •Резюме
- •Глава 7. Традиционные алгоритмы обучения с учителем
- •Машинное обучение с учителем
- •Терминология машинного обучения с учителем
- •Благоприятные условия
- •Различие между классификаторами и регрессорами
- •Алгоритмы классификации
- •Задача классификации
- •Оценка классификаторов
- •Этапы классификации
- •Алгоритм дерева решений
- •Ансамблевые методы
- •Логистическая регрессия
- •Метод опорных векторов (SVM)
- •Наивный байесовский алгоритм
- •Алгоритмы регрессии
- •Задача регрессии
- •Линейная регрессия
- •Алгоритм дерева регрессии
- •Алгоритм градиентного бустинга для регрессии
- •Среди алгоритмов регрессии победителем становится...
- •Практический пример — как предсказать погоду
- •Резюме
- •Глава 8. Алгоритмы нейронных сетей
- •Введение в ИНС
- •Эволюция ИНС
- •Обучение нейронной сети
- •Анатомия нейронной сети
- •Градиентный спуск
- •Функции активации
- •Инструменты и фреймворки
- •Keras
- •Знакомство с TensorFlow
- •Типы нейронных сетей
- •Перенос обучения
- •Практический пример — использование глубокого обучения для выявления мошенничества
- •Методология
- •Резюме
- •Глава 9. Алгоритмы обработки естественного языка
- •Знакомство с NLP
- •Терминология NLP
- •Библиотека NLTK
- •Мешок слов (BoW)
- •Эмбеддинги слов
- •Окружение слова
- •Свойства эмбеддингов слов
- •Рекуррентные нейросети в NLP
- •Использование NLP для анализа эмоциональной окраски текста
- •Практический пример — анализ тональности в отзывах на фильмы
- •Резюме
- •Глава 10. Рекомендательные системы
- •Введение в рекомендательные системы
- •Типы рекомендательных систем
- •Рекомендательные системы на основе контента
- •Рекомендательные системы на основе коллаборативной фильтрации
- •Гибридные рекомендательные системы
- •Ограничения рекомендательных систем
- •Проблема холодного старта
- •Требования к метаданным
- •Проблема разреженности данных
- •Предвзятость из-за социального влияния
- •Ограниченные данные
- •Области практического применения
- •Практический пример — создание рекомендательной системы
- •Резюме
- •Глава 11. Алгоритмы обработки данных
- •Знакомство с алгоритмами обработки данных
- •Классификация данных
- •Алгоритмы хранения данных
- •Стратегии хранения данных
- •Алгоритмы потоковой передачи данных
- •Применение потоковой передачи
- •Алгоритмы сжатия данных
- •Алгоритмы сжатия без потерь
- •Практический пример — анализ тональности твитов в режиме реального времени
- •Резюме
- •Глава 12. Криптография
- •Введение в криптографию
- •Понимание важности самого слабого звена
- •Основная терминология
- •Требования безопасности
- •Базовое устройство шифров
- •Типы криптографических методов
- •Криптографические хеш-функции
- •Симметричное шифрование
- •Асимметричное шифрование
- •Практический пример — проблемы безопасности при развертывании модели МО
- •Атака посредника (MITM)
- •Избежание маскарадинга
- •Шифрование данных и моделей
- •Резюме
- •Глава 13. Крупномасштабные алгоритмы
- •Введение в крупномасштабные алгоритмы
- •Определение эффективного крупномасштабного алгоритма
- •Терминология
- •Разработка параллельных алгоритмов
- •Закон Амдала
- •Гранулярность задачи
- •Балансировка нагрузки
- •Проблема расположения
- •Запуск параллельной обработки на Python
- •Разработка стратегии мультипроцессорной обработки
- •Введение в CUDA
- •Кластерные вычисления
- •Гибридная стратегия
- •Резюме
- •Глава 14. Практические рекомендации
- •Введение в практические рекомендации
- •Печальная история ИИ-бота в Твиттере
- •Объяснимость алгоритма
- •Алгоритмы машинного обучения и объяснимость
- •Этика и алгоритмы
- •Проблемы обучающихся алгоритмов
- •Понимание этических аспектов
- •Снижение предвзятости в моделях
- •Решение NP-трудных задач
- •Упрощение задачи
- •Адаптация известного решения аналогичной задачи
- •Вероятностный метод
- •Когда следует использовать алгоритмы
- •Практический пример — события типа «черный лебедь»
- •Резюме
Типы криптографических методов |
|
|
319 |
|
файла. После копирования файла мы генерируем хеш копии файла — hcopied. Если |
||||
horiginal = hcopied, то есть сгенерированный хеш совпадает с исходным, это подтверж |
||||
дает, что файл не изменился и никакие данные не были утеряны в процессе |
||||
загрузки. Для создания хеша в этих целях можно использовать любую крипто |
||||
графическую хеш-функцию, например MD5 или SHA. |
|
|||
Теперь рассмотрим симметричное шифрование. |
|
|||
Симметричное шифрование |
|
|
||
В криптографии ключ — это комбинация чисел, используемая для кодирования |
||||
открытого текста с использованием выбранного алгоритма. При симметричном |
||||
шифровании для кодирования и декодирования применяется один и тот же ключ. |
||||
Если ключ, используемый для симметричного шифрования, равен K, то вы |
||||
полняется следующее уравнение: |
|
|
|
|
|
|
EK(P) = C. |
|
|
Здесь P — это открытый текст, а C — зашифрованный. |
|
|||
Для расшифровки мы используем тот же ключ, K, преобразуя его обратно в P: |
||||
|
|
DK(С) = Р. |
|
|
Данный процесс показан на диаграмме (рис. 12.9). |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
Рис. 12.9 |
|
|
Теперь посмотрим, как симметричное шифрование реализуется на Python. |
Реализация симметричного шифрования
В этом разделе для демонстрации симметричного шифрования используется библиотека Python под названием cryptography. Это комплексная библиотека,
320 |
Глава 12. Криптография |
реализующая множество криптографических алгоритмов, таких как симметрич ные шифры и различные алгоритмы дайджеста сообщений (message digests). Установим ее с помощью команды pip:
!pip install cryptography
После установки используем библиотеку для реализации симметричного шиф рования.
1. Прежде всего импортируем нужные библиотеки:
import cryptography as crypt
from cryptography.fernet import Fernet
2. Далее сгенерируем ключ (рис. 12.10).
Рис. 12.10
3. Теперь давайте откроем ключ:
file = open('mykey.key', 'wb') file.write(key)
file.close()
4. Используя ключ, зашифруем сообщение:
file = open('mykey.key', 'rb') key = file.read() file.close()
5. Теперь расшифруем сообщение с помощью этого же ключа:
from cryptography.fernet import Fernet message = "Ottawa is really cold".encode()
f = Fernet(key)
encrypted = f.encrypt(message)
6. Расшифруем сообщение и присвоим его переменной с именем decrypt:
decrypted = f.decrypt(encrypted)
7.Выведем decrypt, чтобы проверить, удастся ли получить одно и то же со общение (рис. 12.11).
Типы криптографических методов |
321 |
|
|
|
|
|
|
|
Рис. 12.11
Рассмотрим преимущества и недостатки симметричного шифрования.
Преимущества симметричного шифрования
Хотя производительность симметричного шифрования зависит от конкретного алгоритма, в целом оно намного быстрее, чем асимметричное (которое мы рас смотрим ниже).
Недостатки симметричного шифрования
Когда два пользователя или процесса планируют использовать для связи сим метричное шифрование, им необходимо обменяться ключами через защищенный канал. Это ведет к следующим проблемам:
zz Защита ключа. Как защитить симметричный ключ шифрования?
zzРаспространение ключа. Как передать ключ симметричного шифрования от источника к месту назначения?
Перейдем теперь к асимметричному шифрованию.
Асимметричное шифрование
В 1970-х годах для устранения упомянутых в предыдущем разделе недостатков симметричного шифрования было разработано асимметричное шифрование.
Первым шагом в асимметричном шифровании является создание двух ключей, которые выглядят совершенно по-разному, но алгоритмически связаны. Один из них выбирается в качестве закрытого ключа (private key) Kpr, а другой — в качестве открытого ключа (public key), Kpu. Математически это можно представить так:
EKpr(P) = C.
Здесь P — это открытый текст, а C — зашифрованный.
Можно расшифровать его следующим образом:
DKpu(C) = P.
322 |
Глава 12. Криптография |
Открытые ключи могут свободно распространяться, а закрытые — хранятся владельцем пары ключей в секрете.
Фундаментальный принцип заключается в том, что если данные закодированы с помощью первого, открытого ключа, единственный способ расшифровать их — использовать второй, закрытый ключ. Рассмотрим один из основных про токолов асимметричного шифрования — SSL/TLS. Это протокол подтверждения связи, или протокол рукопожатия (handshake protocol), обеспечивающий уста новление соединения между двумя нодами с использованием асимметричного шифрования.
Протокол SSL/TLS
SSL (Secure Sockets Layer — уровень защищенных cокетов) изначально был разработан для повышения безопасности HTTP. Со временем SSL был заменен более эффективным и надежным протоколом TLS (Transport Layer Security — безопасность транспортного уровня). Безопасный сеанс связи HTTP базирует ся на процедуре установки TLS-рукопожатия. TLS-соединение происходит между двумя участвующими объектами — клиентом и сервером. Данный процесс показан на диаграмме (рис. 12.12).
|
|
|
|
|
|
|
|
|
|
- |
|
(SSL) |
|
- |
|
SSL |
|
SSL |
|
- |
|
|
|
- |
Рис. 12.12
TLS-соединение устанавливает безопасную связь между участвующими нодами. Ниже приведены этапы данного процесса.
Типы криптографических методов |
323 |
1.Клиент отправляет серверу сообщение client hello. В сообщении также содержится:
yy Версия используемого TLS.
yy Список наборов шифров, поддерживаемых клиентом. yy Алгоритм сжатия.
yy Случайная строка байтов, byte_client.
2.Сервер в ответ отправляет клиенту приветственное сообщение server hello. В сообщении также содержится следующее:
yy Набор шифров, выбранный сервером из списка, предоставленного кли ентом.
yy ID сеанса.
yy Случайная строка байтов, byte_server.
yy Цифровой сертификат сервера, cert_server, содержащий открытый ключ сервера.
yy Если сервер требует цифровой сертификат для аутентификации клиента, его запрос включает также:
Уникальные названия допустимых центров сертификации.Типы поддерживаемых сертификатов.
3.Клиент проверяет cert_server.
4.Клиент генерирует случайную байтовую строку byte_client2 и шифрует ее
спомощью открытого ключа сервера, предоставленного через cert_server.
5.Клиент генерирует случайную строку байтов и осуществляет шифрование
спомощью собственного закрытого ключа.
6.Сервер проверяет сертификат клиента.
7.Клиент отправляет на сервер сообщение finished, зашифрованное секретным ключом.
8.Чтобы подтвердить получение, сервер отправляет клиенту сообщение finished, также зашифрованное секретным ключом.
9.Cервер и клиент установили безопасный канал связи. Теперь они могут об мениваться сообщениями, которые симметрично зашифрованы с помощью общего секретного ключа. Вся методология выглядит следующим образом (рис. 12.13).
324 |
|
Глава 12. Криптография |
SLL |
[1] • «client hello» |
C SSL |
|
|
|
|
[2] • «server hello» |
|
|
[4] ‰ Š ‹ |
|
[3] |
Š , ‹ Ž Š Š |
[6] |
|
[5] ’ |
|
|
|
( ) |
|
[7] «”nished» |
|
|
|
|
|
[8] «”nished» |
|
|
[9] ˜ ™ ( |
|
|
) |
|
|
Рис. 12.13 |
|
Теперь обсудим, как используется асимметричное шифрование для создания |
||
инфраструктуры открытых ключей (public key infrastructure, PKI), предна |
||
значенной для достижения одной или нескольких целей безопасности органи |
||
зации. |
|
|
Инфраструктура открытых ключей (PKI) |
|
Для реализации инфраструктуры открытых ключей (PKI) используется асим метричное шифрование. PKI является одним из самых популярных и надежных способов управления ключами шифрования в рамках организации. Все участ ники доверяют надежному органу — центру сертификации (certification authority, CA). Центр сертификации идентифицирует отдельное лицо или организацию, а затем выдает им цифровые сертификаты. Сертификат содержит копию от крытого ключа лица (или организации) и его идентификационные данные. Тем самым центр подтверждает, что публичный ключ на самом деле принадлежит лицу или организации.
Центр сертификации просит пользователя подтвердить свою личность, при этом для отдельных лиц и организаций применяются разные стандарты. Это может быть простая проверка принадлежности доменного имени или более тщательный процесс, включающий подтверждение личности (в зависимости от типа циф