Apache Mahout: масштабируемое машинное обучение для всех

Познакомьтесь с усовершенствованиями Mahout и научитесь масштабировать Mahout в облаке

Коммиттер проекта Apache Mahout Грант Ингерсолл знакомит с текущей версией библиотеки машинного обучения Mahout и приводит пример развертывания и масштабирования некоторых популярных алгоритмов Mahout.

Грант Ингерсолл, технический специалист, Lucid Imagination

Grant IngersollГрант Ингерсолл (Grant Ingersoll) является основателем и техническим сотрудником компании Lucid Imagination. Его профессиональные интересы как разработчика включают такие вопросы, как информационный поиск, машинное обучение, категоризация и извлечение текста. Кроме того, Грант является разработчиком и представителем проектов Apache Lucene и Apache Solr, а также одним из основателей проекта Apache Mahout, посвященного машинному обучению.



20.08.2012

В мире программного обеспечения два года кажутся вечностью. За последние два года мы были свидетелями стремительного развития социальных сетей, массового освоения крупномасштабных кластерных вычислений (благодаря таким компаниям, как Amazon и RackSpace) и гигантского роста объемов данных и нашей способности анализировать их. И это всего через два года после первой публикации статьи Введение в Apache Mahout на developerWorks. С тех пор сообщество Mahout значительно выросло – как и база кода проекта и его возможности. Mahout осваивают большие и малые компании во всем мире.

В моей предыдущей статье о Mahout я изложил многие идеи машинного обучения и основы использования набора алгоритмов Mahout. Эти идеи по-прежнему справедливы, но набор алгоритмов с тех пор претерпел значительные изменения. Вместо того чтобы повторять основы, в этой статье делается акцент на текущем состоянии Mahout и на том, как масштабировать Mahout в рамках вычислительного кластера с помощью службы Amazon EC2 и набора данных из 7 млн документов электронной почты. Для освежения основ просмотрите раздел Ресурсы, в частности, книгу "Mahout в действии". Кроме того, я предполагаю наличие у читателя базовых знаний в области Apache Hadoop и парадигмы Map-Reduce. (Подробнее о Hadoop см. в разделе Ресурсы.)

Подкаст: Грант Ингерсолл о системе машинного обучения Apache Mahout

В этом подкасте коммиттер и соучредитель проекта Apache Mahout Грант Ингерсолл знакомит с машинным обучением и его идеями и объясняет, как они соотносится с реальными приложениями.

Текущее состояние Mahout

За короткий промежуток времени проект Mahout прошел большой путь. Хотя в его фокусе остается то, что я называю «тремя К», – коллаборативная фильтрация (рекомендаторы), кластеризация и классификация – в проекте появились и другие возможности. Я выделю несколько ключевых расширений и усовершенствований в двух областях: основные алгоритмы (реализации) машинного обучения и инфраструктура поддержки, включая инструменты ввода/вывода, точки интеграции с другими библиотеками и дополнительные примеры для справок. Однако имейте в виду, что это не всё. Более того, ввиду ограниченного пространства в этой статье я смогу сказать лишь по несколько фраз о каждом из усовершенствований. Я призываю читателей обратиться к более подробной информации в разделе новостей Web-сайта Mahout и в примечаниях к каждому новому выпуску Mahout.

Алгоритмы, алгоритмы, алгоритмы

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

Таблица 1. Новые алгоритмы в Mahout
АлгоритмКраткое описаниеПример использования
Логистическая регрессия, решение методом вероятностного наибыстрейшего спуска (Stochastic Gradient Descent - SGD)Быстрый, простой и последовательный классификатор, способный к оперативному обучению в сложных условиях. Рекомендация рекламы пользователям, классификация текста по категориям
Скрытые модели Маркова (Hidden Markov Models - HMM)Последовательные и параллельные реализации классического алгоритма классификации, предназначенные для моделирования реальных процессов, когда основной исходный процесс неизвестен. Разметка частей речи в тексте; распознавание речи
Разложение на сингулярные значения (Singular Value Decomposition - SVD)Снижение уровня шума в больших матрицах, что сокращает их размер и облегчает работу с ними. Применяется для автоматического выбора характеристик перед выполнением кластеризации, рекомендаций и классификации.
Кластеризация ДирихлеПодход к кластеризации на основе модели, когда членство определяется по тому, вписываются ли данные в базовую модель. Полезен при наличии параллелизма или иерархии в данных.
Спектральная кластеризацияСемейство аналогичных подходов с использованием графического метода определения членства в группе. Как и все алгоритмы группирования, полезен при изучении новых крупных наборов данных.
Группирование МинхашаИспользует стратегию хэширования для группирования схожих элементов с образованием кластеровТо же, что и для других подходов к кластеризации.
Многочисленные усовершенствования в алгоритмах-рекомендаторахРаспределенные совпадения, SVD, чередующиеся наименьшие квадраты.Сайты знакомств, электронная коммерция, рекомендации кинофильмов или книг.
КоллокацииРеализация коллокации с использованием алгоритма Map-ReduceПоиск в тексте статистически интересных фраз.

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

Совершенствование и расширение инфраструктуры Mahout

Командная строка Mahout

Недавно проект Mahout опубликовал сценарий оболочки, который облегчает запуск программ Mahout (содержащих main()), заботясь о подкаталогах классов, переменных среды и других элементах настройки. Этот сценарий с именем mahout находится в каталоге $MAHOUT_HOME/bin.

Чем больше людей использует проект с открытым исходным кодом и работает над кодом проекта, тем полнее становится инфраструктура. В случае Mahout эта эволюция привела к целому ряду усовершенствований. Наиболее заметным является гораздо более совершенный и последовательной интерфейс командной строки, который облегчает формулирование и решение задач в локальном режиме и на Apache Hadoop. Этот новый сценарий находится в каталоге bin внутри каталога верхнего уровня Mahout (который я буду называть $MAHOUT_HOME). (См. врезку Командная строка Mahout.)

Два ключевых компонента любой библиотеки машинного обучения ― это надежная математическая библиотека и эффективный пакет коллекций. Математическая библиотека (которая находится в модуле math в каталоге $MAHOUT_HOME) предоставляет широкий спектр функций – от структур данных, представляющих векторы, матрицы и соответствующие операторы для работы с ними, до инструментов генерирования случайных чисел и полезных статистических данных, таких как логарифмическое правдоподобие (см. раздел Ресурсы). Библиотека коллекций Mahout состоит из структур данных, подобных тем, которые содержатся в Java-коллекциях (Map, List и т. д.), но внутренне поддерживающих примитивы Java, такие как int, float и double, а не родственные им объекты типа Integer, Float и Double. Это важно, потому что когда имеешь дело с наборами данных, которые могут иметь миллионы характеристик, нужно учитывать каждый бит. Кроме того, при больших масштабах цена упаковки при переходе от примитивов к соответствующим объектам становится непомерно высокой.

В Mahout появился также новый модуль Integration, содержащий код, предназначенный для дополнения или расширения основных возможностей ядра Mahout, которые требуются не всем и не во всех ситуациях. Например, код рекомендатора (коллаборативная фильтрация) теперь поддерживает хранение своей модели в базе данных (посредством JDBC), MongoDB или Apache Cassandra (см. раздел Ресурсы). Модуль Integration также содержит ряд механизмов для преобразования данных в форматы Mahout и для оценки результатов на выходе. Например, он включает в себя инструменты, которые могут конвертировать каталоги, полные текстовых файлов, в векторный формат Mahout (см. пакет org.apache.mahout.text в модуле Integration).

Наконец, в Mahout появился целый ряд новых примеров, от расчета рекомендаций с набором данных Netflix до кластеризации музыкальных записей Last.fm и многого другого. Пример, который я создал для этой статьи, также добавлен в базу кода Mahout. Я призываю читателя уделить некоторое время более подробному изучению модуля примеров (он находится в каталоге $MAHOUT_HOME/examples).

Теперь, когда вы в курсе текущего состояния проекта Mahout, пришло время обратиться к нашей главной теме: масштабированию Mahout.


Масштабирование Mahout в облаке

Эффективное масштабирование Mahout ― это далеко не просто добавление дополнительных узлов в кластер Hadoop. На эффективность масштабирования Mahout влияют такие факторы, как выбор алгоритма, количество узлов, выбор характеристик и разреженность данных – а также обычные вопросы объема памяти, пропускной способности и быстродействия процессора. Чтобы мотивировать свой рассказ, я буду иллюстрировать его примером выполнения некоторых алгоритмов Mahout на общедоступном наборе данных архивов электронной почты Apache Software Foundation (ASF) с помощью вычислительной инфраструктуры Amazon EC2 и Hadoop, где это уместно (см. раздел Ресурсы).

После раздела "Установка" в каждом из подразделов рассматриваются те или иные ключевые проблемы масштабирования Mahout и исследуется синтаксис выполнения данного примера в среде EC2.

Установка

Процесс установки примеров состоит из двух частей: локальной установки и установки в среде EC2 (облаке). Для работы с примерами вам понадобятся:

  1. Apache Maven 3.0.2 или более поздняя версия.
  2. Система управления версиями Git (можно также завести учетную запись на Github).
  3. *NIX-подобная операционная система, такая как Linux или Apple OS X. Cygwin может работать под Windows®, но я это не проверял.

Для локальной установки выполните следующие команды из командной строки:

  1. mkdir -p scaling_mahout/data/sample
  2. git clone git://github.com/lucidimagination/mahout.git mahout-trunk
  3. cd mahout-trunk
  4. mvn install (добавьте -DskipTests, чтобы пропустить тесты Mahout, которые могут занять некоторое время)
  5. cd bin
  6. /mahout (вы должны увидеть список элементов, которые можно запустить, таких как kmeans).

В результате весь необходимый код должен быть скомпилирован и правильно установлен. Отдельно загрузите данные примера, сохраните их в каталоге scaling_mahout/data/sample и распакуйте (Тар -xf scaling_mahout.tar.gz). Это небольшое подмножество данных, которые мы будем использовать на EC2 для целей тестирования.

Чтобы попасть на Amazon, требуется учетная запись Amazon Web Services (AWS) (то есть секретный ключ, ключ доступа и ID учетной записи) и базовое понимание того, как работают службы Amazon EC2 и Elastic Block Store (EBS). Для получения необходимых прав доступа следуйте документации на Web-сайте Amazon.

Когда реквизиты будут получены, можно переходить к запуску кластера. Лучше всего начать с одного узла, а затем при необходимости добавлять новые. И, конечно, имейте в виду, что за работу на EC2 нужно платить. Так что по окончании работы не забудьте остановить свои узлы.

Чтобы загрузить кластер для использования с примерами из этой статьи, выполните следующие действия:

  1. Загрузите Hadoop 0.20.203.0 из зеркала ASF и распакуйте его локально.
  2. cd hadoop-0.20.203.0/src/contrib/ec2/bin
  3. Откройте hadoop-ec2-env.sh в редакторе и:
    1. Заполните поля AWS_ACCOUNT_ID,AWS_ACCESS_KEY_ID,AWS_SECRET_ACCESS_KEY,EC2_KEYDIR, KEY_NAME и PRIVATE_KEY_PATH. За дополнительной информацией обращайтесь на страницу вики Mahout "Использование существующего AMI Hadoop" (см. раздел Ресурсы).
    2. Установите HADOOP_VERSION to 0.20.203.0.
    3. Введите 490429964467 в поле S3_BUCKET.
    4. Установите ENABLE_WEB_PORTS=true.
    5. Введите в поле INSTANCE_TYPE, как минимум, значение m1.xlarge.
  4. Откройте hadoop-ec2-init-remote.sh в редакторе и:
    1. В раздел, в котором создается hadoop-site.xml, добавьте следующее свойство:
      <property>
      <name>mapred.child.java.opts></name>
      <value>-Xmx8096m></value>
      </property>
      Примечание. Если нужно выполнить классификацию, необходимо использовать экземпляр большего размера и больше памяти. Я использовал экземпляры double X-Large и кучу размером 12 ГБ.
    2. Измените значение параметра mapred.output.compress на false.
  5. Запустите свой кластер:
    ./hadoop-ec2 launch-cluster mahout-clustering X
    X ― это количество узлов, которые нужно запустить (например, 2 или 10). Я предлагаю начать с небольшого значения, а затем добавлять узлы по мере освоения системы. Это поможет контролировать расходы.
  6. Создайте том EBS для ASF Public Data Set (Snapshot: snap--17f7f476) и присоедините его к экземпляру главного узла (это экземпляр в группе безопасности mahout-clustering-master) на /dev/sdh. (См. ссылки на подробные инструкции в онлайн-документации EC2 в разделе Ресурсы.)
    1. При использовании API командной строки EC2 (см. раздел Ресурсы) можно сделать следующее:
      1. ec2-create-volume --snapshot snap-17f7f476 --z ZONE
      2. ec2-attach-volume $VOLUME_NUMBER -i $INSTANCE_ID -d /dev/sdh, где $VOLUME_NUMBER ― выходные данные после шага create-volume, а $ INSTANCE_ID ― идентификатор главного узла, который был запущен командой launch-cluster.
    2. Это можно сделать и через Web-консоль AWS.
  7. Загрузите сценарий setup-asf-ec2.sh (см. раздел Загрузка) в главный экземпляр:
    ./hadoop-ec2 push mahout-clustering $PATH/setup-asf-ec2.sh
  8. Войдите в свой кластер:
    ./hadoop-ec2 login mahout-clustering
  9. Выполните сценарий оболочки, чтобы обновить свою систему, установить Git и Mahout и очистить некоторые из архивов для облегчения работы:
    ./setup-asf-ec2.sh

Оставляя в стороне некоторые детали настройки, на следующем шаге попробуем запустить отдельные популярные алгоритмы Mahout и масштабировать их. Мы сосредоточимся главным образом на реальных задачах масштабирования, но по пути рассмотрим некоторые вопросы, касающиеся выбора характеристик и принятия тех или иных решений.

Рекомендации

Коллаборативная фильтрация ― одна из самых популярных и простых в применении возможностей Mahout, поэтому рассмотрение способов масштабирования Mahout логично начать именно с нее. Напомним, что мы работаем с почтовыми архивами ASF. В случае задачи составления рекомендаций одна интересная возможность заключается в том, чтобы построить систему, которая будет рекомендовать потенциально интересные почтовые потоки пользователя, основываясь на потоках, заинтересовавших других пользователей. Чтобы сформулировать это как задачу коллаборативной фильтрации, определим элемент, который рекомендует система, как почтовый поток, характеризующийся идентификатором сообщения (Message-ID) и ссылками (References) в заголовке письма. Пользователь будет определяться по исходящему адресу сообщения электронной почты (From). Другими словами, нас интересует, кто инициировал сообщение электронной почты или ответил на него. Что касается значения самого предпочтения, то мы будем рассматривать взаимодействие с почтовым потоком просто как логическое предпочтение: "да", если пользователь X взаимодействовал с потоком Y, и "нет", если нет. Один недостаток этого подхода заключается в том, что придется использовать показатель подобия, который работает с логическими предпочтениями, такой как Tanimoto или логарифмическое правдоподобие. Обычно это ускоряет вычисления и часто уменьшает количество шума в системе, но может повлиять на стоимость и потребовать экспериментирования с весовыми коэффициентами.

Потоки, идентификаторы сообщений и враг хорошего

Обратите внимание, что мой подход к обработке потоков сообщений не идеален ввиду распространенной практики угона потоков в списках рассылки. Угон потока происходит, когда кто-то, отвечая на существующее сообщение, инициирует в списке новое сообщение (то есть сообщение на новую тему), тем самым подменяя тему исходного сообщения. Вместо того чтобы пытаться решить здесь эту проблему, я просто проигнорирую ее, однако в реальном решении ее придется как-то учитывать. Таким образом, совершенное я заменяю «достаточно хорошим».

Так как при коллаборативной фильтрации выбор компонентов достаточно прост (пользователь, элемент, дополнительное предпочтение), можно сократить путь, взяв контент прямо из исходного почтового архива и поработав с ним локально, а затем запустить работу в облаке. Обратите внимание, что во многих случаях необходимость в последнем шаге отпадает, потому что можно достаточно быстро получить результаты на одной машине без добавления в уравнение сложностей Hadoop. В качестве грубой оценки в тестах Mahout-сообщества предполагается, что один узел позволяет выдавать рекомендации для 100 млн пользователей. В случае данных электронной почты элементов не так много (примерно 7 млн сообщений), но я все равно собираюсь запустить процесс на Hadoop.

Чтобы увидеть код в действии, я упаковал необходимые шаги в сценарий оболочки, который находится в файле $MAHOUT_HOME/examples/bin/build-asf-email.sh. Выполните этот сценарий, передав ему местонахождение входных данных и место, куда надо помещать результаты:

./build-asf-email.sh ./scaling_mahout/data/sample/content ./scaling_mahout/output/

По запросу выберите recommender (вариант 1) и наблюдайте за работой Mahout и Hadoop. Когда она будет сделана, вы увидите что-то похожее на листинг 1.

Листинг 1. Пример результата выполнения кода recommender
11/09/08 09:57:37 INFO mapred.JobClient: Reduce output records=2072
11/09/08 09:57:37 INFO mapred.JobClient: Spilled Records=48604
11/09/08 09:57:37 INFO mapred.JobClient: Map output bytes=10210854
11/09/08 09:57:37 INFO mapred.JobClient: Combine input records=0
11/09/08 09:57:37 INFO mapred.JobClient: Map output records=24302
11/09/08 09:57:37 INFO mapred.JobClient: SPLIT_RAW_BYTES=165
11/09/08 09:57:37 INFO mapred.JobClient: Reduce input records=24302
11/09/08 09:57:37 INFO driver.MahoutDriver: Program took 74847 ms

Результаты этой задачи охватывают все рекомендации для всех пользователей из входных данных. Они хранятся в подкаталоге выходного каталога с именем prefs/recommendations и содержат один или более текстовых файлов с именами, которые начинаются с part-r-. (Так выводит файлы Hadoop). Изучение одного из этих файлов показывает, с одной оговоркой, что рекомендации имеют следующий формат:

user_id [item_id:score, item_id:score, ...]

Например, для пользователя с идентификатором 25 имеются рекомендации по сообщениям электронной почты с идентификаторами 26295 и 35548. Оговорка заключается всего лишь в том, что user_id и item_id ― не оригинальные идентификаторы, а результат их преобразования в целые числа. Чтобы помочь вам понять причину, пора объяснить, что происходит на самом деле, когда выполняется сценарий оболочки.

Результаты рекомендаций получаются в три этапа:

  1. Файлы mbox преобразуются в формат Hadoop SequenceFile с использованием класса Mahout SequenceFilesFromMailArchives.
  2. Из сообщений извлекается идентификатор сообщения и подпись (поле From), и результаты выводятся в формате, понятном Mahout.
  3. Выполняется класс Mahout RecommenderJob.

Я не буду вдаваться в детали этапа 1 в предположении, что заинтересованные читатели обратятся к коду.

На этапе 2 выполняется немного больше работы по извлечению соответствующих элементов информации из файлов (идентификаторы сообщений, ссылки на исходящие адреса) с последующим их сохранением в виде троек (идентификатор From, ссылка Message-ID) для ввода в RecommenderJob. Этим процессом управляет MailToPrefsDriver, который состоит из трех задач Map-Reduce:

  1. Создание словаря путем сопоставления строки Message-ID с уникальным значением типа long.
  2. Создание словаря путем сопоставления строки адреса электронной почты From с уникальным значением типа long.
  3. Извлечение Message-ID, ссылок и адреса From; их преобразование в значения типа long с использованием словарей, полученных на этапах 1 и 2; и вывод троек в текстовый файл.

После этого можно получить некоторые рекомендации. Для генерирования рекомендаций RecommenderJob выполняет действия, показанные на рисунке 1.

Рисунок 1. Работа Recommender
Работа Recommender

Основной шаг, на котором выполняется самая тяжелая работа, это "вычисление соинцидентов". На этом шаге выполняется попарное сравнение по всей матрице в поисках аналогий. Попутно отметим, что этот шаг (выполняемый классом Mahout RowSimilarityJob) обычно используется для попарного сравнения любых строк в матрице (а не только рейтингов/обзоров).

RecommenderJob вызывается в сценарии оболочки с помощью команды:

bin/mahout recommenditembased --input $PREFS_REC_INPUT --output $RECS_OUT --tempDir
    $PREFS_TMP --similarityClassname SIMILARITY_LOGLIKELIHOOD

Первый аргумент указывает Mahout, какую команду выполнять (RecommenderJob); многие другие (input/output/tempDir) говорят сами за себя. SimilarityClassname указывает Mahout, как определить подобие между элементами при вычислении повторений. Для простоты, ускорения и качества я решил использовать логарифмическое правдоподобие.

Когда результаты получены, приходит время их оценки. В состав Mahout входит пакет оценки (org.apache.mahout.cf.taste.eval) с полезными инструментами, которые позволяют исследовать качество результатов. К сожалению, они не работают с алгоритмами на базе Hadoop, но их можно использовать в других случаях. Эти инструменты показывают процент данных, используемых в качестве тестовых данных, а затем сравнивают их с тем, что выдала система, позволяя оценить ее качество.

Это все, что нужно для генерации рекомендаций – и лучше всего то, что все это можно выполнять прямо в кластере. Для этого войдите в кластер EC2, который вы создали ранее, и запустить тот же сценарий оболочки (он находится в каталоге /mnt/asf-email/mahout-trunk/examples/bin). По мере добавления узлов в кластер вы должны наблюдать сокращение общего времени выполнения этих действий. Например, обработка полного набора данных на локальной машине заняла три дня. 10-узловому кластеру EC2 понадобилось примерно 60 минут для решения основной задачи по выдаче рекомендаций, плюс подготовительная работа по преобразованию сообщений электронной почты в пригодный для использования формат.

Последняя часть, которую я оставил в качестве упражнения для читателя, заключается в использовании полученных рекомендаций в рамках приложения. Как правило, когда в системе имеется значительное количество элементов и пользователей, рекомендации создаются периодически – в зависимости от предъявляемых требований процесс обычно длится где-то между получасом и сутками. В конце концов, когда система достигает определенного количества пользователей и рекомендаций, изменения в выдаваемых рекомендациях становятся гораздо менее заметными.

Теперь давайте рассмотрим пример классификации сообщений электронной почты, которую в некоторых случаях можно рассматривать как систему контекстуальных рекомендации.

Классификация

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

Документы электронной почты разбиты по проектам Apache (Lucene, Mahout, Tomcat и т. д.), и в каждом проекте, как правило, имеется два или более списков рассылки (для пользователей, разработчиков и т. д.). Учитывая, что набор данных электронной почты ASF секционирован по проектам, задача логической классификации заключается в том, чтобы попытаться предсказать, в какой проект следует направить новое входящее сообщение. Например, относится ли новое сообщение к списку рассылки Lucene или Tomcat?

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

Как и в случае рекомендаций, необходимые этапы упакованы в сценарий build-asf-email.sh и выполняются при выборе из меню варианта 3 (а затем варианта 1 по второму приглашению стандартного наивного байесовского классификатора). Аналогично рекомендациям, часть работы, относящаяся к масштабированию кода, заключается в подготовке данных. Для классификации текста это главным образом означает кодирование характеристик с последующим созданием векторов, но включает в себя также настройку обучения и тестовых наборов. Вся последовательность шагов такова:

  1. Исходные файлы mbox преобразуются в формат Hadoop SequenceFile с использованием метода Mahout SequenceFilesFromMailArchives. (Обратите внимание, что параметры среды выполнения здесь немного отличаются.)
    bin/mahout org.apache.mahout.text.SequenceFilesFromMailArchives --charset "UTF-8" 
        --body --subject --input $ASF_ARCHIVES --output $MAIL_OUT
  2. Преобразование записей SequenceFile в разреженные векторы и изменение меток:
    1. bin/mahout seq2sparse --input $MAIL_OUT --output $SEQ2SP --norm 2 --weight TFIDF --namedVector --maxDFPercent 90 --minSupport 2 --analyzerName org.apache.mahout.text.MailArchivesClusteringAnalyzer
    2. bin/mahout org.apache.mahout.classifier.email.PrepEmailDriver --input $SEQ2SP --output $SEQ2SPLABEL --maxItemsPerLabel 1000
  3. Разделение входных данных на обучающие и проверочные наборы:
    bin/mahout split --input $SEQ2SPLABEL --trainingOutput $TRAIN --testOutput $TEST
        --randomSelectionPct 20 --overwrite --sequenceFiles
  4. Выполнение наивного байесовского классификатора для обучения и тестирования:
    1. bin/mahout trainnb -i $TRAIN -o $MODEL -extractLabels --labelIndex $LABEL
    2. bin/mahout testnb -i $TEST -m $MODEL --labelIndex $LABEL

Два основных шага, которые стоит отметить, это шаг 2 и шаг 4. Шаг 2а - это основной этап выбора характеристик и кодирования, и от количества входных параметров зависит, как именно входной текст будет представлен в векторах весовыми коэффициентами. Параметры, связанные с выбором характеристик на шаге 2, приведены в таблице 2.

Таблица 2. Параметры выбора характеристик для создания векторов
ВариантОписаниеПримеры и примечания
--normNorm изменяет все векторы при помощи функции, которая вычисляет их длину (норму)1-я норма = манхэттенское расстояние, 2-я норма = евклидово расстояние
--weightРассчитывает весовой коэффициент любой данной функции как TF-IDF (частота встречаемости термина, частота инверсии документа), либо просто частота встречаемости термина TF-IDF – это общая схема весовых коэффициентов в алгоритмах поиска и машинного обучения для представления текста в качестве векторов.
--maxDFPercent, --minSupportОба эти варианта пропускают термины, которые в коллекции документов встречаются слишком часто (max) или недостаточно часто. Полезно для автоматического пропуска общих или очень редких терминов, малозначимых для расчета.
--analyzerNameКласс анализатора Apache Lucene, который можно использовать для маркировки, выделения основы, удаления или иного изменения слова в документе. Подробнее о классе Lucene см. в разделе Ресурсы.)

Процесс анализа на шаге 2a заслуживает немного более подробного рассмотрения, учитывая, что на нем производится большая часть тяжелой работы, необходимой для выбора компонента. Анализатор Lucene состоит из класса Tokenizer и нуля или более классов TokenFilter. Класс Tokenizer отвечает за разбиение исходных данных на ноль или более маркеров (таких как слова). Экземпляры класса TokenFilter соединяются в цепочку, чтобы затем изменить маркеры, производимые классом Tokenizer. Например, Analyzer используется в следующем примере:

  1. Разделение по пробелам, плюс некоторые граничные случаи со знаками препинания.
  2. Все маркеры переводятся в нижний регистр.
  3. Не-ASCII символы преобразуются в ASCII, по возможности с преобразованием диакритических знаков и т.д.
  4. Маркеры, содержащие более 40 символов, отбрасываются.
  5. Стоп-слова удаляются (список см. в коде; для отображения здесь он слишком велик).
  6. В маркерах выделяется основа с помощью морфологического алгоритма Портера (см. раздел Ресурсы).

Конечным результатом этого анализа является значительно сокращенный вектор каждого документа, из которого исключены общие слова–"шум": (the, a, an и т.п.), которые будут путать классификатор. Этот Analyzer разработан итеративно с использованием примеров данных электронной почты, которые пропускались через Analyzer, и результаты изучались на предмет качества обработки. К сожалению, как и в любой науке, этот процесс во многом опирается на интуицию (опыт). Сам процесс и его результат далеки от совершенства, но их можно считать достаточно хорошими.

На шаге 2b производятся некоторые незначительные преобразования данных для обработки, а также отбрасываются некоторые данные, чтобы в обучающих данных были равномерно представлены различные маркеры. Это важный момент, потому что мои первые эксперименты с данными привели к характерной проблеме машинного обучения - избыточному обучению для тех маркеров, для которых было значительно больше примеров. На самом деле при работе с кластером при полном наборе данных уменьшения значения параметра --maxItemsPerLabel до 1000 недостаточно для получения хороших результатов, так как в некоторых списках почтовой рассылки меньше 1000 сообщений. Возможно, это результат ошибки в Mahout, которую сообщество все еще ищет.

На шаге 4 выполняется фактическая работа по построению модели с последующим тестированием. На шаге 4a параметр --extractLabels просто сообщает Mahout значение маркеров обучения во входных данных. (Альтернативой является передача их ему.) Результатом этого шага становится файл, который можно прочесть с помощью класса org.apache.mahout.classifier.naivebayes.NaiveBayesModel. На шаге 4b выполняется проверка качества обучения с использованием модели и выборки данных. Результатом является матрица неточностей, описанная во Введении в Apache Mahout. Результат для выборки данных приведен в листинге 2:

Листинг 2. Пример результата выполнения кода классификатора
Correctly Classified Instances : 41523 61.9219%
Incorrectly Classified Instances : 25534 38.0781%
Total Classified Instances : 67057
=======================================================
Confusion Matrix
-------------------------------------------------------
a b c d e f ><--Classified as
190440 12 1069 0 0 | 20125 a= cocoon_apache_org_dev
2066 0 1 477 0 0 | 2544 b= cocoon_apache_org_docs
165480 2370 704 0 0 | 19622 c= cocoon_apache_org_users
58 0 0 201090 0 | 20167 d= commons_apache_org_dev
147 0 1 4451 0 0 | 4599 e= commons_apache_org_user

Следует отметить, что на самом деле это довольно слабый результат классификатора (хотя и лучший, чем выбор наугад). Причиной может быть то, что списки рассылки пользователей и разработчиков данного проекта Apache настолько близки по своему словарю, что их слишком сложно различить. Это подтверждается тем, что 16548 сообщений cocoon_user неправильно классифицированы как cocoon_dev. Действительно, запуск задачи с использованием только имени проекта, без разграничения на списки пользователей и разработчиков, на той же выборке данных приводит к результатам, показанным в листинге 3.

Листинг 3. Пример выходных данных после перезапуска кода классификатора только с именем проекта
Correctly Classified Instances : 38944 96.8949%
Incorrectly Classified Instances : 1248 3.1051%
Total Classified Instances : 40192

=======================================================
Confusion Matrix
-------------------------------------------------------
a b c ><--Classified as
18733 1241 0 | 19974 a = cocoon_apache_org
7 20211 0 | 20218 b = commons_apache_org

Думаю, вы согласитесь, что точность в 96% несколько лучше, чем 61%! На самом деле, это, вероятно, даже слишком хорошо, чтобы быть правдой. Скорее всего, такая оценка вызвана характером этой конкретной небольшой выборки данных или более глубокой проблемой, которая требует исследования. На самом деле такая оценка побуждает к продолжению исследований с добавлением дополнительных данных и пересмотром создающего их кода. Пока же оставим их в качестве примера того, как должны выглядеть результаты. Однако чтобы повысить точность, можно попробовать другие методы, лучший выбор характеристик или, возможно, больше учебных примеров. Существует также общепринятый процесс поперечной проверки результатов. В ходе поперечной проверки многократно берется часть данных из примера обучения и помещается в тестовый пример или исключается. Затем о системе судят по качеству всех прогонов, а не по одному.

Перенести это в облако так же просто, как и в случае с рекомендациями. Чтобы весь сценарий выполнялся в кластере, достаточно передать соответствующие пути. При его запуске в EC2 или на 10-узловом кластере обучение и тестирование, включая обычную подготовительную работу выполняется за считанные минуты. К сожалению, однако, качество исполнения в облаке на полном наборе данных будет неважным, потому что некоторые списки почтовой рассылки содержат очень мало точек данных. Вероятно, их следует исключить из рассмотрения.

Последующие шаги к производственному приложению включают создание модели в рамках конкретной рабочей системы и настройку рабочего процесса для корректировки этой модели по мере получения обратной связи от системы. А теперь обратимся к кластеризации.

Кластеризация

Как и в случае с классификацией, Mahout предлагает многочисленные алгоритмы кластеризации, каждый из которых имеет свои особенности. Например, алгоритм K-Means красиво масштабирует, но требует указать количество кластеров, которые вы хотите использовать, тогда как для алгоритма кластеризации Дирихле нужно выбрать модель распределения и также указать количество кластеров. Кластеризация имеет немало общего с классификацией, и иногда их можно использовать совместно, так что кластеры становятся частью классификации. Более того, значительная часть работы по подготовке данных для классификации ― та же, что и для кластеризации — например, преобразование исходных данных в последовательность файлов и затем в разреженные векторы - так что за этой информацией можно обращаться к разделу Классификация.

Главный вопрос, на который необходимо ответить при кластеризации: можно ли независимо от проекта логически сгруппировать все сообщения по сходству их содержания? Например, возможно, что сообщения в списке рассылки Apache Solr об использовании Apache Tomcat в качестве Web-контейнера будут ближе к сообщениям из проекта Tomcat, чем из исходного проекта.

В этом примере первые шаги во многом те же, что и при классификации, но после завершения преобразования в разреженные векторы они начинают отличаться друг от друга. А именно:

  1. Шаги 1 и 2 те же, что и при классификации.
  2. $ bin/mahout kmeans --input "$SEQ2SP/tfidf-vectors" --output $CLUST_OUT -k 50 --maxIter 20 --distanceMeasure org.apache.mahout.common.distance.CosineDistanceMeasure --clustering --method mapreduce --clusters "$CLUST_OUT/clusters"

В данном случае K-Means выполняется для кластеризации, но сценарий оболочки поддерживает и кластеризацию Дирихле. (При выполнении сценария предлагается выбрать желаемый алгоритм.) В предыдущем примере следующие параметры стоит рассмотреть более детально:

  1. -k: количество создаваемых кластеров. Я выбрал 50, но это значение, безусловно, может быть другим.
  2. --maxIter: K-Means ― это итеративный алгоритм, в котором при каждой итерации уточняется центр кластера. В некоторых случаях не гарантировано, что он завершится самостоятельно, так что от этого параметра может зависеть конечность алгоритма.
  3. --distanceMeasure: мера расстояния определяет сходство между текущим центроидом и рассматриваемой точкой. В данном случае я выбрал меру косинусного расстояния, которая часто служит хорошим выбором для текстовых данных. В Mahout есть много других реализаций, и вы можете попробовать их на своих данных.
  4. --clustering: предписывает Mahout указать, к какому центроиду принадлежат точки. По умолчанию Mahout просто вычисляет центроиды, так как часто это все, что нужно.

После запуска можно вывести центроиды кластера (и соответствующие точки) с помощью входящей в Mahout программы ClusterDump. Окончательные результаты будут находиться в подкаталоге каталога kmeans, имя которого начинается с clusters- и заканчивается -final. Точное значение зависит от того, сколько итераций потребовалось для решения задачи; например clusters-2-final ― это выходные данные третьей итерации. Следующая команда выводит кластеры после обработки небольшой выборки данных:

bin/mahout clusterdump --seqFileDir ../output/ibm/clustering/kmeans/clusters-2-final
    --pointsDir ../output/ibm/clustering/kmeans/clusteredPoints/

--SeqFileDir указывает на созданные центроиды, а -pointsDir ― это каталог кластеризованных точек. Небольшая выборка результатов приведена в листинге 4:

Листинг 4. Пример результатов работы ClusterDumper
:VL-337881{n=4420 c=[
  Top Terms:
    user                                    =>0.060885823267350335
    mailscann                               => 0.05059369006868677
    cocoon                                  =>0.048781178576134204
    virus                                   => 0.04285897589148712
    derek                                   => 0.04084340722527813
    legal                                   =>0.040052624979813184
    scan                                    => 0.03861016730680097
    danger                                  => 0.03848600584647758
    csir                                    => 0.03712359352614157
    transtec                                => 0.03388019099942435
  Weight : [props - optional]:  Point:
  1.0 : [distance=0.888270593967813]: 
  /cocoon.apache.org/dev/200004.gz/NBBBIDJGFOCOKIOHGDPBKEPPEEAA.XXXXX = 
  [ag:0.165, briefli:0.250, chang:0.075, close:0.137, cocoon:0.060, 
  cocoon1:0.226, cocoon2:0.218, concept:0.277, develop:0.101, differ:0.144, 
  explain:0.154, greet:0.197, klingenderstrass:0.223, langham:0.223, look:0.105, 
  mailserv:0.293, matthew:0.277, mlangham:0.240, paderborn:0.215, processor:0.231, 
  produc:0.202, put:0.170, scan:0.180, tel:0.163, understand:0.127, virus:0.194]

В листинге 4 обратите внимание на то, что вывод содержит список терминов, выбранных алгоритмом в качестве наиболее характерных представителей кластера. Это может быть полезно для создания маркеров в производственных целях, а также для настройки выбора характеристик на подготовительных этапах – потому что часто бывает, что стоп-слова выявляются в списке после первых нескольких экспериментальных прогонов (в данном случае, например, одним из них, скорее всего, станет слово user).

Как вы, вероятно, уже догадались, выполнить этот сценарий в кластере так же легко, как локально – и как для двух других примеров. В моих тестах, не считая времени на преобразование данных (примерно 150 минут), фактическая работа по кластеризации на 10 узлах заняла около 40 минут.

К сожалению, при кластеризации оценка результатов часто сводится к "тесту на запах", хотя в Mahout есть некоторые инструменты оценки (для вывода наиболее часто употребляемых терминов см. параметры CDbwEvaluator и ClusterDumper). Что касается тестов на запах, то часто наиболее эффективной бывает визуализация кластеров, но многие инструменты визуализации графов, к сожалению, спотыкаются на больших наборах данных, так что вам, возможно, придется выбрать свой собственный.

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


Что еще будет в Mahout?

Проект Apache Mahout продолжает развиваться по нескольким направлениям. В данный момент сообщество занято главным образом продвижением к версии 1.0, выполняя тестирование производительности и документирование, совершенствуя API и добавляя новые алгоритмы. Следующая версия, 0.6, скорее всего, выйдет в конце 2011 или в начале 2012 года. На более глубоком уровне сообщество начинает присматриваться к подходам распределенного решения задач машинного обучения в оперативной памяти. Во многих случаях задачи машинного обучения слишком велики для одной машины, но Hadoop несет слишком много накладных расходов, связанных с операциями ввода-вывода на диски. В любом случае Mahout хорошо справляется с решением сегодняшних наиболее насущных задач обработки больших объемов данных, делая акцент на масштабируемость и облегчая использование сложных алгоритмов машинного обучения.


Загрузка

ОписаниеИмяРазмер
Сценарий оболочкиj-mahout-scaling.zip2 КБ

Ресурсы

Научиться

Получить продукты и технологии

  • Apache Mahout: загрузите версию исходного кода Mahout от Гранта Ингресолла с примерами.

Обсудить

  • Список рассылки пользователей Mahout: подпишитесь, чтобы задавать вопросы, делиться знаниями и обсуждать интересующие вас темы.
  • Примите участие в деятельности сообщества developerWorks. Общайтесь с другими пользователями developerWorks, просматривая блоги, форумы, группы и вики разработчиков.

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=831048
ArticleTitle=Apache Mahout: масштабируемое машинное обучение для всех
publish-date=08202012