О пользе технологий больших данных в повседневной жизни



    Среди многих исследователей и разработчиков бытует мнение, что инструменты обработки больших данных в области машинного обучения часто избыточны – всегда можно сделать сэмпл, загнать в память и использовать любимые R, Python и Matlab. Но на практике встречаются задачи, когда даже относительно небольшой объем данных, размером в пару гигабайт, обработать в таком стиле затруднительно – и тут-то и могут помочь те самые технологии «больших данных».

    Хорошим наглядным примером такой задачи является задача нашего конкурса SNA Hakathon 2016: дан социальный граф одного миллиона пользователей и их демография. Задача — найти скрытые связи в этом графе. Размер предоставленного графа всего два гигабайта в GZip и, казалось бы, применение технологий больших данных здесь не оправданно, но это только на первый взгляд.

    Одной из самых важных «фич» в задаче поиска скрытых связей в социальном графе является количество общих друзей. И в расчетном плане это очень тяжелая «фича» — количество узлов, между которыми существуют пути длины 2, на несколько порядков больше, чем количество прямых связей в графе. В результате при расчете граф «взрывается» и из разрежённой матрицы на два гигабайта превращается в плотную терабайтную матрицу.

    Казалось бы, для решение этой задачи впору поднимать небольшой кластер, но спешить не стоит: взяв на вооружение принципы обработки больших данных и соответствующие технологии, задачу можно решить и на обычном ноутбуке. Из принципов мы возьмем «разделяй и властвуй» и «руби хвосты сразу», а в качестве инструмента — Apache Spark.

    В чем проблема?


    Открытый для анализа граф представлен в виде списка смежности (для каждой вершины дан список соседей) и асимметричен (не для всех вершин известны исходящие дуги). Очевидный способ рассчитать количество общих друзей между вершинами в этом графе выглядит следующим образом:



    1. Переводим граф в вид списка пар;
    2. Join-им список пар сам на себя по «общему другу»;
    3. Суммируем число вхождений каждой пары.

    К плюсам такого подхода, несомненно, следует отнести простоту — на Spark это решение займет 5 строчек. Но минусов у него гораздо больше. Уже на втором шаге при реализации join-a происходит shuffle (пересылка данных между разными этапами обработки), который очень быстро исчерпает ресурсы локального хранилища. А если вдруг на вашем ноутбуке все-таки хватит под него места, то его уже точно не хватит для shuffle-а на третьем этапе.

    Чтобы справиться с задачей, нужно разбить её на части («разделяй и властвуй») и отфильтровать результаты с небольшим количеством общих друзей («руби хвосты сразу»). Но выполнить оба условия сразу проблематично – при расчете числа общих друзей только на части графа мы получим неполную картину и не сможем адекватно применить фильтр…

    Где решение?


    Попробуем взглянуть на проблему с другой стороны. Больше всего неприятностей вызывает join списка пар на втором этапе: сам формат списка пар неэффективен с точки зрения размера, к тому же одну из сторон join-a невозможно отфильтровать, не исказив результат. Можно ли обойтись без конвертации в список пар и join-a? Да, если воспользоваться принципом «я общий друг для двух своих друзей». В этом случае мы итерируемся по списку смежности для каждого из списка друзей и генерируем все пары, а после чего считаем сколько раз каждая из пар появилась в целом по системе – в итоге задача решается с помощью одного shuffle :)

    Развивая эту идею, несложно сделать и следующий шаг: вместо того, чтобы генерировать все возможные пары, надо генерировать только пары для определенного подмножества пользователей в левой части (например, с четными идентификаторами). Далее эту процедуру можно повторить несколько раз и получить полное покрытие. При этом на каждой итерации можно смело применять фильтр для отсечения «длинного хвоста» – для пользователей в этом подмножестве цифры получены точно.

    Этот подход хорошо работает для симметричного графа, но представленный на SNA Hakathon 2016 граф асимметричен – для некоторых пользователей известны только входящие дуги. Чтобы использовать этот трюк, граф надо сначала развернуть:



    Результат конвертации уже можно сохранить и использовать в качестве входа для итеративного алгоритма:



    Стоит ли игра свеч?


    Именно на этом графе подсчет количества общих друзей «в лоб» занял 1 час на кластере из 100 серверов. Оптимизированный итеративный вариант отработал за 4 с половиной часа на одном двухъядерном ноутбуке. Эти цифры позволяют сделать вывод, что вариант «в лоб» приемлем только для достаточно крупных фирм и/или исследовательских коллективов, тогда как оптимизированный вариант может запустить практически любой желающий. К тому же, весь необходимый код и инструкции опубликованы в открытом доступе на GitHub.

    Действительно ли в этой схеме необходимы те самые «технологии больших данных»? Можно ли то же самое повторить на R или Python? Теоретически, нет ничего невозможного. Но на практике при реализации придется решить большое количество проблем и познакомиться со многими весьма специфичными пакетами и функциями. Полученный в результате код будет больше по размеру и явно дороже в разработке и поддержке.

    На самом деле, даже если абстрагироваться от данного примера, использование Apache Spark во многих случаях может оказаться предпочтительнее R и Python: для Spark естественной является параллельная обработка данных, что обеспечивает более высокую скорость, практически без изменений код может быть перенесен на кластер в Google Cloud (case study) и применен к значительно большему объему данных. Ну а коллекция поддерживаемых алгоритмов машинного обучения, хотя еще и уступает «прародителям», но уже достаточно внушительна и постоянно пополняется (MLLib).

    Время учить Scala :)
    Одноклассники 55,68
    Делимся экспертизой
    Поделиться публикацией
    Комментарии 11
    • +2
      Честно говоря, непонятен посыл статьи. 1 час кластера в 100 серверов дороже или дешевле дня работы программиста-оптимизатора?
      • 0
        А что делать если вы студент-дипломник и у вас нет кластера? Да и на большом кластере когда работают 20 программистов-неоптимизаторов тоже становиться некомфортно...

        Ну а посыл в том что даже на одном ноуте можно получить бенефит используя технологии и методы работы с большими данными.
        • 0
          2 Гб, пусть и в сжатом виде, это уже большие данные? Странно. Я то считал большими данными то, что не помещается на одном сервере.

          И не понятно, чем занимался кластер из 100 машин, если на каждую приходилось по 20 Мб сжатых данных. Подозреваю, что это был hadoop кластер и обработка графа выполнялась с помощью MapReduce?
          • 0
            Да, на каждый мэппер всего по 20мб. Но каждые 20мб очень быстро превращаются в 2Гб так как "количество узлов, между которыми существуют пути длины 2, на несколько порядков больше, чем количество прямых связей в графе".

            Обрабатывать "в лоб" пробовали и на Spark, и на Pig, и на Pig + Tez. Спарк с пигом отработали норм, а тез залажал — начал делать хэш-джойн вместо мерж джойна и получил 3 часа в итоге

            Попробуйте ;)
            • +2
              Пробовал считать граф, в котором было примерно 20 млрд вершин и 1,5 трлн ребер на кластере меньше 100 машин. Подход MapReduce для графов совершенно не подходит. Spark интересный и перспективный инструмент, но и он не подходит для работы с графами. Есть GraphX, который будет оптимальней. Правда до тех пор, пока данные помещаются в оперативной памяти.

              С очень большими графами на момент, когда я его смотрел, он работать не мог :-(
              • 0
                Ну про "совсем не" я бы не говорил — все сильно зависит от задачи. Получалось делать в рамках мапреда весьма интересные вещи с графами малой кровью, а спарк с итеративностью и кешом вообще норм. Выбор и специализированных графовых тулов сечас вполне ничего, но с большими графами проблемы бывают не только у graphx.

                И есть еще ньюанс — в данном случае нам на самом деле надо не только посчитать общих друзей, но и потом собрать тренировочное множество, натренировать регрессию и записать результат в нужном виде. И тут "шейцарский нож" спарка подходит в самый раз, позволяя решить все нужный задачи в одном инструменте, да еще и сохранить возможность проделать все на минимальных ресурсах.
                • +2
                  Теперь давайте представим, что пользователей 20 млдр, у каждого 200 друзей. Это уже достаточно большие данные.

                  Как будет работать ваше решение? Ведь граф придется делать распределенным, на одной машине он не поместится даже на жесткий диск.
                  • 0
                    Ну нам то надо всего 1М пользователей ;). На самом деле поскольку процесс итеративный и с фильтрацией, то потенциально даже на одной ноде можно подсчитать общих друзей и на гораздо более крупном графе.

                    Ну и при наличии кластера подход с одним шаффлом все равно быстрее. А при использовании спарка можно организовать итеративный процесс так, что из памяти на диск будут писаться только итоговые отфильтрованные результаты, а сам граф и данные шаффлов будут идти память-сеть-память, без диска. Работать будет в разы быстрее чем "в лоб", ± сравнимо с графлабом (хотя там, конечно, можно затюнить еще круче, если запариться).
                    • +1
                      Так ведь статья о применении подхода работы с большими данными :-)

                      В реальной жизни для обработки действительно большого графа (например web-графа) вам потребовалось бы реализовывать например pregel (http://web.stanford.edu/class/cs347/reading/pregel.pdf). На spark такое считать совсем не рентабельно. Однако для небольших графов, которые не являются big-data и помещаются на одной машине он не эффективен.
                      • 0
                        Статья о пользе от технологий "больших" данных для тех кто привык пользоваться технологиями "маленьких" (R, Python). Как типичный студент/аспирант может показать хороший результат на SNA Hackathon 2016 не покидая свой уютный ноутик.
      • –1

        Как Вы думаете: убьёт ли Scala питон в нише прототипирования?

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое