- •Об авторе
- •Предисловие
- •Для кого эта книга
- •О чем эта книга
- •Что вам потребуется при чтении этой книги
- •Условные обозначения
- •От издательства
- •Глава 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-трудных задач
- •Упрощение задачи
- •Адаптация известного решения аналогичной задачи
- •Вероятностный метод
- •Когда следует использовать алгоритмы
- •Практический пример — события типа «черный лебедь»
- •Резюме
Введение в библиотеки Python |
31 |
алгоритма. В нем подробно описываются задачи времени выполнения, на кото рые будет разделено задание, созданное для выполнения нашего алгоритма.
11 ( ) |
12 |
Рис. 1.3
Обратите внимание, что на данной диаграмме представлены пять задач, которые были разделены на два разных этапа: этап 11 и этап 12.
ВВЕДЕНИЕ В БИБЛИОТЕКИ PYTHON
После разработки алгоритм должен быть реализован на языке программирова ния в соответствии с проектом. Для этой книги я выбрал Python, так как это гибкий язык программирования с открытым исходным кодом. Python также является базовым языком для инфраструктур облачных вычислений, приоб ретающих все более важное значение, таких как Amazon Web Services (AWS),
Microsoft Azure и Google Cloud Platform (GCP).
Официальная домашняя страница Python доступна по адресу https://www.python. org/. Здесь вы найдете инструкции по установке и полезное руководство для начинающих.
32 |
Глава 1. Обзор алгоритмов |
Если вы раньше не использовали Python, рекомендуем ознакомиться с этим руководством в целях самообразования. Базовое представление о языке Python поможет лучше понять концепции, представленные в этой книге.
Установите последнюю версию Python 3. На момент написания это версия 3.7.3, которую мы и будем использовать для выполнения упражнений в книге.
Библиотеки Python
Python — это язык общего назначения. Он разработан таким образом, чтобы обеспечить минимальную функциональность. В зависимости от цели исполь зования Python вам придется установить дополнительные библиотеки. Самый простой способ — программа установки pip. Следующая команда pip устанав ливает дополнительную библиотеку:
pip install a_package
Установленные ранее библиотеки необходимо периодически обновлять, чтобы иметь возможность использовать новейшие функциональные возможности. Обновление запускается с помощью флага upgrade:
pip install a_package --upgrade
Другим дистрибутивом Python для научных вычислений является Anaconda. Его можно загрузить по адресу https://www.anaconda.com.
В дистрибутиве Anaconda применяется следующая команда для установки новых библиотек:
conda install a_package
Для обновления существующих библиотек дистрибутива Anaconda:
conda update a_package
Существует множество доступных библиотек Python. Некоторые важные биб лиотеки, имеющие отношение к алгоритмам, описаны далее.
Экосистема SciPy
Scientific Python (SciPy) — произносится как сай пай — это группа библиотек Python, созданных для научного сообщества. Она содержит множество функций, включая широкий спектр генераторов случайных чисел, программ линейной
Введение в библиотеки Python |
33 |
алгебры и оптимизаторов. SciPy — это комплексная библиотека, и со временем специалисты разработали множество расширений для ее настройки и дополне ния в соответствии со своими потребностями.
Ниже приведены основные библиотеки, которые являются частью этой экоси стемы:
zz NumPy. При работе с алгоритмами требуется создание многомерных структур данных, таких как массивы и матрицы. NumPy предлагает набор типов дан ных для массивов и матриц, которые необходимы для статистики и анализа данных. Подробную информацию о NumPy можно найти по адресу http:// www.numpy.org/.
zz scikit-learn. Это расширение для машинного обучения является одним из самых популярных расширений SciPy. Scikit-learn предоставляет широкий спектр важных алгоритмов машинного обучения, включая классификацию, регрессию, кластеризацию и проверку моделей. Вы можете найти более под робную информацию о scikit-learn по адресу http://scikit-learn.org/.
zz pandas. Библиотека программного обеспечения с открытым исходным кодом. Она содержит сложную табличную структуру данных, которая широко ис пользуется для ввода, вывода и обработки табличных данных в различных алгоритмах. Библиотека pandas содержит множество полезных функций, а также обеспечивает высокую производительность с хорошим уровнем оптимизации. Более подробную информацию о pandas можно найти по адре су http://pandas.pydata.org/.
zz Matplotlib. Содержит инструменты для создания впечатляющих визуализаций. Данные могут быть представлены в виде линейных графиков, точечных диаграмм, гистограмм, круговых диаграмм и т. д. Более подробную инфор мацию можно найти по адресу https://matplotlib.org/.
zz Seaborn. Считается аналогом популярной библиотеки ggplot2 в R. Она осно вана на Matplotlib и предлагает великолепный расширенный интерфейс для графического отображения статистики. Подробную информацию можно найти по адресу https://seaborn.pydata.org/.
zz IPython. Усовершенствованная интерактивная консоль, предназначенная для того, чтобы упростить написание, тестирование и отладку кода Python.
zz Запуск Python в интерактивном режиме. Этот режим программирования полезен для обучения и экспериментов с кодом. Программы на Python могут быть сохранены в текстовом файле с расширением .py, и этот файл можно запустить из консоли.
34 |
Глава 1. Обзор алгоритмов |
Реализация Python с помощью Jupyter Notebook
Еще один способ запуска программ на Python — через Jupyter Notebook. Jupyter Notebook представляет собой пользовательский интерфейс для разработки на основе браузера. Именно Jupyter Notebook используется для демонстрации примеров кода в этой книге. Возможность комментировать и описывать код с помощью текста и графики делает Jupyter Notebook идеальным инструментом для демонстрации и объяснения любого алгоритма‚ а также отличным инстру ментом для обучения.
Чтобы запустить программу, вам нужно запустить процесс Jupyter-notebook, а затем открыть свой любимый браузер и перейти по ссылке http://localhost:8888 (рис. 1.4).
Рис. 1.4