Анализ больших наборов данных

Юре Лесковец, Ананд Раджараман, Джеффри Д. Ульман

Анализ  
больших 
наборов данных

Mining
of
Massive
Datasets

Jure Leskovec
Stanford Univ.

Anand Rajaraman
Milliway Labs

Jeffrey D. Ullman
Stanford Univ.

Ìîñêâà, 2023

Анализ 
больших 
наборов 
данных

Юре Лесковец
Stanford Univ.

Ананд Раджараман
Milliway Labs

Джеффри Д. Ульман
Stanford Univ.

2-е издание, электронное

УДК 004.6
ББК 32.972
Л50

Л50
Лесковец, Юре.
Анализ больших наборов данных / Ульман Дж. Д., Лесковец Ю., Раджараман А. ; пер. 
с англ. А. А. Слинкина. — 2-е изд., эл. — 1 файл pdf : 500 с. — Москва : ДМК Пресс, 2023. — 
Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : 
электронный.

ISBN 978-5-89818-304-2

Эта книга написана ведущими специалистами в области технологий баз данных и веба. Благодаря популярности интернет-торговли появилось много чрезвычайно объемных баз данных, для 
извлечения информации из которых нужно применять методы добычи данных (data mining).
В книге описываются алгоритмы, которые реально использовались для решения важнейших 
задач добычи данных и могут быть с успехом применены даже к очень большим наборам данных. 
Изложение начинается с рассмотрения технологии MapReduce — важного средства распараллеливания алгоритмов. Излагаются алгоритмы хэширования с учетом близости и потоковой обработки данных, которые поступают слишком быстро для тщательного анализа. В последующих 
главах рассматривается идея показателя PageRank, нахождение частых предметных наборов и 
кластеризация. Во второе издание включен дополнительный материал о социальных сетях, машинном обучении и понижении размерности.
Издание будет в равной мере полезна студентам и программистам-практикам.

УДК 004.6 
ББК 32.972

Электронное издание на основе печатного издания: Анализ больших наборов данных / Ульман Дж. Д., Лесковец Ю., Раджараман А. ; пер. с англ. А. А. Слинкина. — Москва : ДМК Пресс, 2016. — 498 с. — ISBN 978-597060-190-7. — Текст : непосредственный.

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

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских 
прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-89818-304-2
©  2010, 2011, 2012, 2013, 2014 Anand Rajaraman, 
Jure Leskovec, Jeffrey D. Ullman
© Оформление, издание, ДМК Пресс, 2016

ОГЛАВЛЕНИЕ

Предисловие ................................................................ 17
О чем эта книга ............................................................................................. 17
Требования к читателю ................................................................................. 18
Упражнения .................................................................................................. 18
Поддержка в вебе ......................................................................................... 18
Автоматизированные домашние задания ..................................................... 18
Благодарности ............................................................................................. 19

ГЛАВА 1.  
Добыча данных ............................................................. 20
1.1. Что такое добыча данных? ..................................................................... 20
1.1.1. Статистическое моделирование ......................................................... 20
1.1.2. Машинное обучение ........................................................................... 21
1.1.3. Вычислительные подходы к моделированию ...................................... 21
1.1.4. Обобщение ......................................................................................... 22
1.1.5. Выделение признаков ......................................................................... 23
1.2. Статистические пределы добычи данных ............................................... 23
1.2.1. Тотальное владение информацией ..................................................... 24
1.2.2. Принцип Бонферрони ......................................................................... 24
1.2.3. Пример применения принципа Бонферрони ....................................... 25
1.2.4. Упражнения к разделу 1.2 ................................................................... 26
1.3. Кое-какие полезные сведения ............................................................... 26
1.3.1. Важность слов в документах ............................................................... 27
1.3.2. Хэш-функции ...................................................................................... 28
1.3.3. Индексы .............................................................................................. 29
1.3.4. Внешняя память .................................................................................. 31
1.3.5. Основание натуральных логарифмов .................................................. 31
1.3.6. Степенные зависимости ..................................................................... 32
1.3.7. Упражнения к разделу 1.3 ................................................................... 34
1.4. План книги ............................................................................................. 35
1.5. Резюме .................................................................................................. 37
1.6. Список литературы ................................................................................ 38

Оглавление

ГЛАВА 2.  
MapReduce и новый программный стек ............................. 39
2.1. Распределенные файловые системы ..................................................... 40
2.1.1. Физическая организация вычислительных узлов ................................ 40
2.1.2. Организация больших файловых систем............................................. 42
2.2. MapReduce ............................................................................................ 42
2.2.1. Задачи-распределители ..................................................................... 44
2.2.2. Группировка по ключу ......................................................................... 44
2.2.3. Задачи-редукторы .............................................................................. 45
2.2.4. Комбинаторы ...................................................................................... 45
2.2.5. Детали выполнения MapReduce .......................................................... 46
2.2.6. Обработка отказов узлов .................................................................... 48
2.2.7. Упражнения к разделу 2.2 ................................................................... 48
2.3. Алгоритмы, в которых используется MapReduce .................................... 48
2.3.1. Умножение матрицы на вектор с применением MapReduce ................ 49
2.3.2. Если вектор v не помещается в оперативной памяти ........................... 50
2.3.3. Операции реляционной алгебры ......................................................... 51
2.3.4. Вычисление выборки с помощью MapReduce ..................................... 53
2.3.5. Вычисление проекции с помощью MapReduce .................................... 54
2.3.6. Вычисление объединения, пересечения и разности  
с помощью MapReduce ................................................................................ 54
2.3.7. Вычисление естественного соединения с помощью MapReduce ......... 55
2.3.8. Вычисление группировки и агрегирования с помощью MapReduce .... 56
2.3.9. Умножение матриц ............................................................................. 56
2.3.10. Умножение матриц за один шаг MapReduce ...................................... 57
2.3.11. Упражнения к разделу 2.3 ................................................................. 58
2.4. Обобщения MapReduce ......................................................................... 59
2.4.1. Системы потоков работ ...................................................................... 60
2.4.2. Рекурсивные обобщения MapReduce .................................................. 61
2.4.3. Система Pregel ................................................................................... 64
2.4.4. Упражнения к разделу 2.4 ................................................................... 65
2.5. Модель коммуникационной стоимости .................................................. 65
2.5.1. Коммуникационная стоимость для сетей задач................................... 65
2.5.2. Физическое время .............................................................................. 68
2.5.3. Многопутевое соединение .................................................................. 68
2.5.4. Упражнения к разделу 2.5 ................................................................... 71
2.6. Теория сложности MapReduce ............................................................... 73
2.6.1. Размер редукции и коэффициент репликации .................................... 73
2.6.2. Пример: соединение по сходству........................................................ 74
2.6.3. Графовая модель для проблем MapReduce ......................................... 76
2.6.4. Схема сопоставления ......................................................................... 78
2.6.5. Когда присутствуют не все входы ........................................................ 79
2.6.6. Нижняя граница коэффициента репликации ....................................... 80
2.6.7. Пример: умножение матриц ................................................................ 82
2.6.8. Упражнения к разделу 2.6 ................................................................... 86
2.7. Резюме .................................................................................................. 87

Оглавление

2.8. Список литературы ................................................................................ 89

ГЛАВА 3.  
Поиск похожих объектов ................................................. 92
3.1. Приложения поиска близкого соседям .................................................. 92
3.1.1. Сходство множеств по Жаккару .......................................................... 93
3.1.2. Сходство документов .......................................................................... 93
3.1.3. Коллаборативная фильтрация как задача о сходстве множеств .......... 94
3.1.4. Упражнения к разделу 3.1 ................................................................... 96
3.2. Разбиение документов на шинглы .......................................................... 96
3.2.1. k-шинглы ............................................................................................ 97
3.2.2. Выбор размера шингла ....................................................................... 97
3.2.3. Хэширование шинглов ........................................................................ 98
3.2.4. Шинглы, построенные из слов ............................................................ 98
3.2.5. Упражнения к разделу 3.2 ................................................................... 99
3.3. Сигнатуры множеств с сохранением сходства ..................................... 100
3.3.1. Матричное представление множеств ................................................ 100
3.3.2. Минхэш ............................................................................................ 101
3.3.3. Минхэш и коэффициент Жаккара ...................................................... 102
3.3.4. Минхэш-сигнатуры ........................................................................... 102
3.3.5. Вычисление минхэш-сигнатур .......................................................... 103
3.3.6. Упражнения к разделу 3.3 ................................................................. 105
3.4. Хэширование документов с учетом близости ....................................... 107
3.4.1. LSH для минхэш-сигнатур ................................................................. 107
3.4.2. Анализ метода разбиения на полосы ................................................ 109
3.4.3. Сочетание разных методов ............................................................... 110
3.4.4. Упражнения к разделу 3.4 ................................................................. 111
3.5. Метрики ............................................................................................... 111
3.5.1. Определение метрики ...................................................................... 112
3.5.2. Евклидовы метрики .......................................................................... 112
3.5.3. Расстояние Жаккара ......................................................................... 113
3.5.4. Косинусное расстояние .................................................................... 114
3.5.5. Редакционное расстояние ................................................................ 114
3.5.6. Расстояние Хэмминга ....................................................................... 115
3.5.7. Упражнения к разделу 3.5 ................................................................. 116
3.6. Теория функций, учитывающих близость ............................................. 118
3.6.1. Функции, учитывающие близость ..................................................... 119
3.6.2. LSH-семейства для расстояния Жаккара .......................................... 120
3.6.3. Расширение LSH-семейства ............................................................. 120
3.6.4. Упражнения к разделу 3.6 ................................................................. 122
3.7. LSH-семейства для других метрик ....................................................... 123
3.7.1. LSH-семейства для расстояния Хэмминга ........................................ 123
3.7.2. Случайные гиперплоскости и косинусное расстояние....................... 124
3.7.3 Эскизы ............................................................................................... 125
3.7.4. LSH-семейства для евклидова расстояния ....................................... 126
3.7.5. Другие примеры LSH-семейств в евклидовых пространствах ........... 127

Оглавление

3.7.6. Упражнения к разделу 3.7 ................................................................. 128
3.8. Применения хэширования с учетом близости ...................................... 129
3.8.1. Отождествление объектов ................................................................ 129
3.8.2. Пример отождествления объектов .................................................... 129
3.8.3. Проверка отождествления записей................................................... 131
3.8.4. Сравнение отпечатков пальцев ......................................................... 132
3.8.5. LSH-семейство для сравнения отпечатков пальцев .......................... 132
3.8.6. Похожие новости .............................................................................. 134
3.8.7. Упражнения к разделу 3.8 ................................................................. 135
3.9. Методы для высокой степени сходства ................................................ 136
3.9.1. Поиск одинаковых объектов .............................................................. 137
3.9.2. Представление множеств в виде строк ............................................. 137
3.9.3. Фильтрация на основе длины строки ................................................ 138
3.9.4. Префиксное индексирование ........................................................... 138
3.9.5. Использование информации о позиции ............................................ 140
3.9.6. Использование позиции и длины в индексах ..................................... 141
3.9.7. Упражнения к разделу 3.9 ................................................................. 144
3.10. Резюме .............................................................................................. 144
3.11. Список литературы ............................................................................ 147

ГЛАВА 4.  
Анализ потоков данных ..................................................149
4.1. Потоковая модель данных .................................................................... 149
4.1.1. Система управления потоками данных ............................................. 150
4.1.2. Примеры источников потоков данных ............................................... 151
4.1.3. Запросы к потокам............................................................................ 152
4.1.4. Проблемы обработки потоков ........................................................... 153
4.2. Выборка данных из потока ................................................................... 154
4.2.1. Пояснительный пример .................................................................... 154
4.2.2. Получение репрезентативной выборки ............................................. 155
4.2.3. Общая постановка задачи о выборке ................................................ 155
4.2.4. Динамическое изменение размера выборки ..................................... 156
4.2.5. Упражнения к разделу 4.2 ................................................................. 156
4.3. Фильтрация потоков ............................................................................ 157
4.3.1. Пояснительный пример .................................................................... 157
4.3.2. Фильтр Блума ................................................................................... 158
4.3.3. Анализ фильтра Блума ...................................................................... 158
4.3.4. Упражнения к разделу 4.3 ................................................................. 160
4.4. Подсчет различных элементов в потоке ............................................... 160
4.4.1. Проблема Count-Distinct ................................................................... 160
4.4.2. Алгоритм Флажоле-Мартена ............................................................ 161
4.4.3. Комбинирование оценок ................................................................... 162
4.4.4. Требования к памяти ......................................................................... 163
4.4.5. Упражнения к разделу 4.4 ................................................................. 163
4.5. Оценивание моментов ......................................................................... 163
4.5.1. Определение моментов .................................................................... 163

Оглавление

4.5.2. Алгоритм Алона-Матиаса-Сегеди для вторых моментов ................... 164
4.5.3. Почему работает алгоритм Алона-Матиаса-Сегеди .......................... 165
4.5.4. Моменты высших порядков............................................................... 166
4.5.5. Обработка бесконечных потоков ....................................................... 166
4.5.6. Упражнения к разделу 4.5 ................................................................. 168
4.6. Подсчет единиц в окне ......................................................................... 169
4.6.1. Стоимость точного подсчета ............................................................. 169
4.6.2. Алгоритм Датара-Гиониса-Индыка-Мотвани .................................... 170
4.6.3. Требования к объему памяти для алгоритма DGIM ............................ 171
4.6.4. Ответы на вопросы в алгоритме DGIM ............................................... 172
4.6.5. Поддержание условий DGIM ............................................................. 172
4.6.6. Уменьшение погрешности ................................................................ 174
4.6.7. Обобщения алгоритма подсчета единиц ........................................... 174
4.6.8. Упражнения к разделу 4.6 ................................................................. 175
4.7. Затухающие окна ................................................................................. 176
4.7.1. Задача о самых частых элементах ..................................................... 176
4.7.2. Определение затухающего окна ....................................................... 176
4.7.3. Нахождение самых популярных элементов ....................................... 177
4.8. Резюме ................................................................................................ 178
4.9. Список литературы .............................................................................. 180

ГЛАВА 5.  
Анализ ссылок .............................................................182
5.1. PageRank ............................................................................................. 182
5.1.1. Ранние поисковые системы и спам термов ....................................... 183
5.1.2. Определение PageRank .................................................................... 184
5.1.3. Структура веба ................................................................................. 187
5.1.4. Избегание тупиков ............................................................................ 189
5.1.5. Паучьи ловушки и телепортация ....................................................... 192
5.1.6. Использование PageRank в поисковой системе ................................ 194
5.1.7. Упражнения к разделу 5.1 ................................................................. 194
5.2. Эффективное вычисление PageRank.................................................... 196
5.2.1. Представление матрицы переходов ................................................. 196
5.2.2. Итеративное вычисление PageRank с помощью MapReduce ............. 197
5.2.3. Использование комбинаторов для консолидации  
результирующего вектора .......................................................................... 198
5.2.4. Представление блоков матрицы переходов ...................................... 199
5.2.5. Другие эффективные подходы к итеративному вычислению  
PageRank ................................................................................................... 200
5.2.6. Упражнения к разделу 5.2 ................................................................. 201
5.3. Тематический PageRank ....................................................................... 202
5.3.1. Зачем нужен тематический PageRank ............................................... 202
5.3.2. Смещенное случайное блуждание .................................................... 202
5.3.3. Использование тематического PageRank .......................................... 204
5.3.4. Вывод тем из слов ............................................................................ 205
5.3.5. Упражнения к разделу 5.3 ................................................................. 205

Оглавление

5.4. Ссылочный спам .................................................................................. 206
5.4.1. Архитектура спам-фермы ................................................................. 206
5.4.2. Анализ спам-фермы ......................................................................... 207
5.4.3. Борьба со ссылочным спамом .......................................................... 208
5.4.4. TrustRank .......................................................................................... 208
5.4.5. Спамная масса ................................................................................. 209
5.4.6. Упражнения к разделу 5.4 ................................................................. 210
5.5. Хабы и авторитетные страницы ............................................................ 210
5.5.1. Предположения, лежащие в основе HITS .......................................... 211
5.5.2. Формализация хабов и авторитетных страниц .................................. 211
5.5.3. Упражнения к разделу 5.5 ................................................................. 214
5.6. Резюме ................................................................................................ 214
5.7. Список литературы .............................................................................. 218

ГЛАВА 6.  
Частые предметные наборы ...........................................219
6.1. Модель корзины покупок ..................................................................... 219
6.1.1. Определение частого предметного набора ....................................... 220
6.1.2. Применения частых предметных наборов ......................................... 221
6.1.3. Ассоциативные правила ................................................................... 223
6.1.4. Поиск ассоциативных правил с высокой достоверностью ................. 225
6.1.5. Упражнения к разделу 6.1 ................................................................. 225
6.2. Корзины покупок и алгоритм Apriori ..................................................... 226
6.2.1. Представление данных о корзинах покупок ....................................... 227
6.2.2. Использование оперативной памяти для подсчета предметных  
наборов...................................................................................................... 228
6.2.3. Монотонность предметных наборов ................................................. 230
6.2.4. Доминирование подсчета пар ........................................................... 230
6.2.5. Алгоритм Apriori ................................................................................ 231
6.2.6. Применение Apriori для поиска всех частых предметных наборов ..... 232
6.2.7. Упражнения к разделу 6.2 ................................................................. 235
6.3. Обработка больших наборов данных в оперативной памяти ................. 236
6.3.1. Алгоритм Парка-Чена-Ю (PCY) .......................................................... 236
6.3.2. Многоэтапный алгоритм ................................................................... 238
6.3.3. Многохэшевый алгоритм .................................................................. 240
6.3.4. Упражнения к разделу 6.3 ................................................................. 242
6.4. Алгоритм с ограниченным числом проходов ........................................ 244
6.4.1. Простой рандомизированный алгоритм ........................................... 244
6.4.2. Предотвращение ошибок в алгоритмах формирования выборки ...... 245
6.4.3. Алгоритм SON ................................................................................... 246
6.4.4. Алгоритм SON и MapReduce ............................................................. 247
6.4.5. Алгоритм Тойвонена ......................................................................... 248
6.4.6. Почему алгоритм Тойвонена работает .............................................. 249
6.4.7. Упражнения к разделу 6.4 ................................................................. 249
6.5. Подсчет частых предметных наборов в потоке ..................................... 250
6.5.1. Методы выборки из потока ............................................................... 250