Использование Hadoop и Mahout в машинном обучении Созыкин Андрей Владимирович к.т.н. зав.кафедрой высокопроизводительных компьютерных технологий

2 Hadoop и MahoutСозыкин А.В. Big Data Big Data – задачи обработки больших объемов данных: Терабайты и петабайты Высокая скорость обработки – невозможно сделать традиционными подходами Оценки аналитиков Gartner и IDC: Big Data входит в ТОП 10 наиболее важных тенденций развития информационных технологий Рынок Big Data один из самых быстрорастущих MapReduce – одна из наиболее популярных моделей обработки данных в Big Data

3 Hadoop и MahoutСозыкин А.В. План Основы MapReduce и Apache Hadoop Экосистема Hadoop Машинное обучение в Apache Mahout

4 Hadoop и MahoutСозыкин А.В. История Hadoop и MapReduce Технологию MapReduce придумали в Google для системы поиска в Интернет: Цель – хранить и обрабатывать большие объемы данных на обычных компьютерах, объединенных сетью Goggle не распространяет свою реализацию MapReduce Jeffrey Dean, Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google File System Apache Hadoop – открытая реализация MapReduce: Разработан на основе идей Google Написан на Java

5 Hadoop и MahoutСозыкин А.В. Кто использует Hadoop Кто использует Hadoop: Самый большой кластер Hadoop в Yahoo!: 4500 серверов Используется для поисковой системы и подбора рекламных объявлений

6 Hadoop и MahoutСозыкин А.В. Основные технологии Hadoop HDFS (Hadoop Distributed File System) – хранение данных MapReduce – обработка данных

7 Hadoop и MahoutСозыкин А.В. HDFS Файл

8 Hadoop и MahoutСозыкин А.В. HDFS Файл 64МБ

9 Hadoop и MahoutСозыкин А.В. HDFS Файл 64МБ

10 Hadoop и MahoutСозыкин А.В. HDFS Data Node 1Data Node 2Data Node 3 Data Node 4Data Node 5Data Node 6 Name Node 1, 4, 6 1, 3, 5 1, 2, 5

11 Hadoop и MahoutСозыкин А.В. Работа с HDFS Блоки файлов в HDFS распределены по разным серверам: Нельзя смонтировать HDFS Не работают стандартные команды ls, cp, mv и т.п. Необходимо использовать специальную команду: $ hadoop dfs –cmd Примеры: $ hadoop dfs -ls Found 3 items -rw-r--r-- 1 hadoop supergroup :58 /user/hadoop/file1 -rw-r--r-- 1 hadoop supergroup :58 /user/hadoop/file2 -rw-r--r-- 1 hadoop supergroup :58 /user/hadoop/file3 $ hadoop dfs -put /tmp/file4 $ hadoop dfs -cat file4 Hello, world!

12 Hadoop и MahoutСозыкин А.В. Особенности HDFS HDFS – специализированная файловая система, оптимизированная для параллельной потоковой работы с большими файлами Подходит не для всех задач! Модель Write Once Read Many: Нельзя изменять файл, можно только добавлять в конец Большой размер блока: По-молчанию 64 МБ (часто 128 или 256 МБ) Не эффективен произвольный доступ (базы данных и т.п.)

13 Hadoop и MahoutСозыкин А.В. MapReduce MapReduce – технология распределенных вычислений Цель MapReduce – разделить логику приложения и организацию распределенного взаимодействия: Программист реализует только логику приложения Распределенная работа в кластере обеспечивается автоматически MapReduce работает с данными как с парами Ключ:Значение: смещение в файле: текст идентификатор пользователя: профиль пользователь: список друзей временная метка: событие в журнале Источник:

14 Hadoop и MahoutСозыкин А.В. Функции Map и Reduce Источник:

15 Hadoop и MahoutСозыкин А.В. Пример MapReduce: WordCount Задача: посчитать, сколько раз слово встречается в файле Количество обращений к Web-страницам Количество просмотра видео или прослушивания песни Исходные данные: Текстовые файлы Каждый файл делится на пары: Смещение:Тест Пример: Цель MapReduce – разделить логику приложения и организацию распределенного взаимодействия. Программист реализует только логику приложения

16 Hadoop и MahoutСозыкин А.В. WordCount: функция Map Исходные данные: Цель MapReduce – разделить логику приложения и организацию распределенного взаимодействия. Программист реализует только логику приложения Результаты обработки:,,,,,,,,,,,,, Сортировка и группировка по ключу:,,,,,,,,,,,,,.

17 Hadoop и MahoutСозыкин А.В. WordCount: функция Reduce Пары с одинаковыми ключами передаются в одну функцию Reduce:,,

18 Hadoop и MahoutСозыкин А.В. Модель MapReduce MapReduce – странный подход к решению задачи WordCount Есть более простые и интуитивно понятные решения Достоинства MapReduce: Возможность автоматического распараллеливания – функции Map и Reduce могут обрабатывать элементы списка параллельно не зависимо друг от друга Масштабируемость – данные могут размещаться на разных серверах (в HDFS) и обрабатываться также на разных серверах Отказоустойчивость – при выходе из строя сервера функции Map или Reduce запускаются на другом сервере Недостатки MapReduce: Фиксированный алгоритм обработки данных Высокие накладные расходы на распараллеливание

19 Hadoop и MahoutСозыкин А.В. Перемещение вычислений к данным

20 Hadoop и MahoutСозыкин А.В. Пример запуска задачи Hadoop $ hadoop jar hadoop-examples-*.jar grep input output 'dfs[a-z.]+ ' hadoop-examples-*.jar – Имя архива с примерами из дистрибутива Hadoop grep – Имя команды в архиве с примерами input – Каталог входных данных (в HDFS) output – Каталог выходных данных (в HDFS) 'dfs[a-z.]+ ' – Шаблон для поиска

21 Hadoop и MahoutСозыкин А.В. Экосистема Hadoop MapReduce – мощная модель программирования, но низкоуровневая Реализация практически полезных алгоритмов требует высоких трудозатрат Hadoop сложен в установке и администрировании На основе Hadoop сложилась экосистема: Программные продукты для решения различных прикладных задач, использующие Hadoop для масштабирования Дистрибутивы Hadoop Облачный хостинг для Hadoop

22 Hadoop и MahoutСозыкин А.В. Экосистема Hadoop Pig – декларативный язык анализа данных Hive – анализ данных с использованием языка, близкого к SQL Oozie – поток работ в Hadoop Hbase – база данных (нереляционная), аналог Google Big Table Mahout – машинное обучение Sqoop – перенос данных из РСУБД в Hadoop и наоборот Flume – перенос логов в HDFS Zookeeper, MRUnit, Avro, Giraph, Ambari, Cassandra, HCatalog, Fuse-DFS и т.д.

23 Hadoop и MahoutСозыкин А.В. Дистрибутивы Hadoop Apache hadoop.apache.org Оригинальный дистрибутив, только Hadoop Альтернативные дистрибутивы: Совместно Hadoop, HBase, Pig, Hive, Mahout, Sqoop, Zookeeper и др. Средства автоматизации установки и администрирования, мониторинг, безопасность Поставщики альтернативных дистрибутивов: Cloudera MapR Hortonworks Intel

24 Hadoop и MahoutСозыкин А.В. Облачный хостинг Hadoop Amazon Elastic MapReduce (Amazon EMR) Партнерство с MapR Apache Hadoop on Rackspace hadoop-on-rackspace-private-cloudhttp:// hadoop-on-rackspace-private-cloud Партнерство с Hortonworks Microsoft Windows Azure Qubole Data Service Web-интерфейс для анализа данных с Hadoop, Hive, Pig и др. на Amazon EMR

25 Hadoop и MahoutСозыкин А.В. Apache Mahout Масштабируемая библиотека машинного обучения (machine learning) Режимы работы: В кластере Hadoop Отдельно на одном компьютере Mahout – слово из индийского языка, означает погонщик слонов Открытые исходные коды: Написан на Java Лицензия Apache 2.0 Страница проекта:

26 Hadoop и MahoutСозыкин А.В. Машинное обучение в Mahout Коллаборативная (совместная) фильтрация Рекомендации Кластеризация Объединение объектов в группы (кластеры, заранее не известные) Примеры: Google News объединяет новости на одну тему Алгоритмы в Mahout: K-Means, Fuzzy K-Means, Mean Shift, Dirichlet, Canopy и др. Классификация: Определение принадлежности объекта к заданному классу (классы известны заранее) Примеры: определение спама, определение тематики текста (текст о политике, спорте и т.п.) Алгоритмы в Mahout: Logistic Regression, Naive Bayes, Support Vector Machines, Online Passive Aggressive и др.

27 Hadoop и MahoutСозыкин А.В. Рекомендации

28 Hadoop и MahoutСозыкин А.В. Актуальность рекомендаций Хорошая система рекомендаций может существенно повысит доход от продаж и рекламы $1M NetflixPrize: Компания Netflix устроила соревнования по улучшению алгоритма рекомендации DVD Размер приза: 1 миллион долларов Условие получения приза: улучшить алгоритм рекомендации на 10% Приз получила команда «BellKors Pragmatic Chaos» в 2009 г. Соревнования проходили с 2006 по 2009 г. Каждый год выплачивался приз за прогресс $

29 Hadoop и MahoutСозыкин А.В. Способы рекомендаций На основе контента Пример: пользователь выбрал книгу Пушкина, значит можно рекомендовать ему другую книгу Пушкина или классическую литературу Недостаток: система рекомендаций сильно зависит от домена и непереносима На основе предпочтений Рекомендации на основе оценок пользователей Объекты рекомендации могут быть любыми Можно реализовать общую систему, не зависимую от домена Реализован в Mahout

30 Hadoop и MahoutСозыкин А.В. Предпочтение Рекомендации в Mahout выдаются на основе предпочтений пользователей Предпочтение в Mahout: Пользователь (целое число) Объект (целое число) Предпочтение (число двойной точности) Пример данных о предпочтениях для Mahout из проекта GroupLens (Университет Минесоты) – оценка пользователями фильмов: user id | item id | rating | timestamp (Не используется в Mahout)

31 Hadoop и MahoutСозыкин А.В. Подходы к рекомендации На основе пользователей: Найти пользователей с похожими вкусами Посмотреть, что нравится этим пользователям Рекомендовать объекты в соответствии с предпочтениями похожих пользователей Недостатки: подход плохо масштабируется, предпочтения быстро меняются На основе объектов: Найти объекты, похожие на те, которые понравились пользователю Рекомендовать наиболее популярные из них Преимущества: хорошо масштабируется, оценки объектов меняются редко. Рекомендации можно генерировать в автономном режиме (с использованием Hadoop)

32 Hadoop и MahoutСозыкин А.В. Рекомендации на основе пользователей public static void main(String[] args) throws Exception { DataModel model = new FileDataModel (new File("u.data")); UserSimilarity similarity = new PearsonCorrelationSimilarity (model); UserNeighborhood neighborhood = new NearestNUserNeighborhood (2, similarity, model); Recommender recommender = new GenericUserBasedRecommender ( model, neighborhood, similarity); List recommendations = recommender.recommend(1, 1); for (RecommendedItem recommendation : recommendations) { System.out.println(recommendation); } RecommendedItem [item:643, value: ]

33 Hadoop и MahoutСозыкин А.В. Рекомендации на основе пользователей Источник: Sean Owen, Robin Anil, Ted Dunning, and Ellen Friedman. Mahout in Action

34 Hadoop и MahoutСозыкин А.В. Выбор похожих пользователей Как определить, что вкусы пользователей похожи? Мера «похожести» - число от -1 до 1. 1 – вкусы пользователей совпадают 0 – у пользователей нет общих вкусов -1 – вкусы пользователей противоположны Mahout использует несколько алгоритмов расчета «похожести»: Коэффициент Пирсона Евклидово расстояние Корреляция Спирмена Коэффициент Танимото Логарифмическое правдоподобие

35 Hadoop и MahoutСозыкин А.В. «Соседние» пользователи Источник: Sean Owen, Robin Anil, Ted Dunning, and Ellen Friedman. Mahout in Action Фиксированное число соседей (NearestNUserNeighborhood ) Соседи в пределах границы (ThresholdUserNeighborhood)

36 Hadoop и MahoutСозыкин А.В. Выбор параметров Какой тип «похожести» пользователей лучше? Какой тип «соседства» лучше? Критерии оценки: Однозначного ответа нет Результаты разные для разных данных Проводите эксперименты с разными параметрами! Источник: Sean Owen, Robin Anil, Ted Dunning, and Ellen Friedman. Mahout in Action

37 Hadoop и MahoutСозыкин А.В. Рекомендации на основе объектов public static void main(String[] args) throws Exception { DataModel model = new FileDataModel (new File("u.data")); ItemSimilarity itemSimilarity = new LogLikelihoodSimilarity(dataModel); ItemBasedRecommender recommender = new GenericItemBasedRecommender(dataModel, itemSimilarity); List recommendations = recommender.recommend(1, 1) for (RecommendedItem recommendation : recommendations) { System.out.println(recommendation); } RecommendedItem [item:271, value: ]

38 Hadoop и MahoutСозыкин А.В. Mahout и Hadoop Источник: Sean Owen, Robin Anil, Ted Dunning, and Ellen Friedman. Mahout in Action

39 Hadoop и MahoutСозыкин А.В. Mahout и Hadoop Mahout может работать как отдельно, так и в кластере Hadoop Запуск рекомендации Mahout в Hadoop выполняется с помощью класса RecommenderJob Данные о предпочтениях должны быть записаны в HDFS Полученные рекомендации записываются в HDFS Рекомендации можно перенести в базу данных с помощью sqoop

40 Hadoop и MahoutСозыкин А.В. Пример запуска Mahout в Hadoop $ hadoop jar mahout-core-0.7-job.jar \ org.apache.mahout.cf.taste.hadoop.item.RecommenderJob \ -Dmapred.input.dir=input -Dmapred.output.dir=output --usersFile users_list.txt Возможные параметры: Dmapred.input.dir – каталог с данными о предпочтениях (в HDFS, может быть несколько файлов) Dmapred.output.dir – каталог, куда записываются сгенерированные рекомендации (в HDFS) --usersFile – файл с идентификаторами пользователей, для которых нужно сгенерировать рекомендации --similarityClassname – имя класса, который реализует расчет «похожести» --numRecommendations – количество рекомендаций на одного пользователя

41 Hadoop и MahoutСозыкин А.В. Итоги MapReduce – программная модель для обработки больших объемов данных (BigData) Hadoop – открытая реализация MapReduce Экосистема Hadoop Mahout – машинное обучение в Hadoop: Рекомендации, классификация, кластеризация Рекомендации в Mahout: Предпочтения: пользователь, объект, оценка Рекомендации на основе пользователей и на основе объектов «Похожесть» пользователей и объектов «Соседство» пользователей Запуск Mahout RecommenderJob в Hadoop

42 Hadoop и MahoutСозыкин А.В. Вопросы? Контакты Андрей Созыкин