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

Инетенетмагазин:
www.dmkpress.com
Книга – почтой:
email: orders@alians-kniga.ru
Оптовая продажа: 
«Альянскнига»
Тел./факс: (499) 7823889
email: books@alians-kniga.ru

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

Данная книга представляет собой Стэнфордский курс о добыче данных 
в вебе (Web Mining) с акцентом на анализе данных очень большого 
объема. В книге принят алгоритмический подход: извлечение данных — 
это применение алгоритмов к данным, а не использование данных для 
«обучения» той или иной машины. 

Основные рассматриваемые темы:

• 
распределенные файловые системы и технология распределенияредукции (map-reduce) как средство создания параллельных алгоритмов;

• 
поиск по сходству, в том числе MinHash и хэширование с учетом близости;

• 
обработка потоков данных и специализированные алгоритмы для работы 
с быстро поступающими данными;

• 
принципы работы поисковых систем, в том числе алгоритм Google PageRank, распознавание ссылочного спама и метод авторитетных и хабдокументов;

• 
частые предметные наборы, в том числе поиск ассоциативных правил, 
анализ корзины, алгоритм Apriori и его усовершенствованные варианты;

• 
алгоритмы кластеризации очень больших многомерных наборов данных;

• 
важные задачи: управление рекламой и рекомендательные системы;

• 
алгоритмы анализа структуры очень больших графов, в особенности 
графов социальных сетей;

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

• 
алгоритмы машинного обучения, применимые к очень большим наборам 
данных.

9 785970 601907

ISBN 978-5-97060-190-7
Анализ
больших наборов
                      данных
www.дмк.рф

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

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

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

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

Mining
of
Massive
Datasets

Jure Leskovec
Stanford Univ.

Anand Rajaraman
Milliway Labs

Jeffrey D. Ullman
Stanford Univ.

Москва, 2016

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

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

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

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

УДК 
004.6
ББК 
32.972
Л50

Л50    Юре Лесковец, Ананд Раджараман, Джеффри Д. Ульман
Анализ больших наборов данных. / Пер. с англ. Слинкин А. А. – М.: ДМК 
Пресс, 2016. – 498 с.: ил.

            ISBN 978-5-97060-190-7

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

Original English language edition published by Cambridge University Press, 132 Avenue of 
the Americas, New York, NY 10013-2473, USA. Copyright © 2010, 2011, 2012, 2013, 2014 Anand 
Rajaraman, Jure Leskovec, Jeffrey D. Ullman. Russian-language edition copyright © 2015 by DMK 
Press. All rights reserved.

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

ISBN 978-1-118-62986-4 (англ.) 
© 2010, 2011, 2012, 2013, 2014 Anand 
 
 
Rajaraman, Jure Leskovec, Jeffrey D. Ullman
ISBN 978-5-97060-190-7 (рус.) 
 
© Оформление, издание, ДМК Пресс, 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