Компания
241,62
рейтинг
20 января в 10:00

Разработка → Параллельные алгоритмы для обработки BigData: подводные камни и непростые решения

Эта публикация написана по материалам выступления AlexSerbul на осенней конференции BigData Conference.

Большие данные — тема модная и востребованная. Но многих по-прежнему отпугивает избыток теоретических рассуждений и некоторый недостаток практических рекомендаций. В этом посте я хочу отчасти заполнить этот пробел и рассказать об использовании параллельных алгоритмов для обработки больших данных на примере кластеризации товарного каталога из 10 млн позиций.

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



Какой есть выход? Ради экономии времени и денег можно конечно попытаться найти библиотеку, которая позволит реализовать алгоритм параллельной кластеризации. На Java-платформе что-то конечно есть: умирающий Apache Mahout и развивающийся Apache Spark MLlib. К сожалению, Mahout поддерживает мало алгоритмов под MapReduce — большинство из них последовательны.

Обещающий горы Spark MLlib пока тоже не богат на алгоритмы кластеризации. А с нашими объёмами дело еще хуже — вот что предлагается:

  • K-means
  • Gaussian mixture
  • Power iteration clustering (PIC)
  • Latent Dirichlet allocation (LDA)
  • Streaming k-means

Когда у вас 10-20 миллионов сущностей для кластеризации, вышеупомянутые решения уже не помогут, нужен хардкор. Но обо всём по порядку.

Итак, нам нужно кластеризовать каталог из 10 млн товарных позиций. Зачем это нужно? Дело в том, что наши пользователи могут использовать в своих интернет-магазинах рекомендательную систему. А её работа основана на анализе агрегированного каталога товаров всех сайтов, работающих на нашей платформе. Допустим, в одном из магазинов покупателю порекомендовали выбрать топор, чтобы тёщу зарубить (да, это корпоративный блог, но без шуток про бигдату и математику говорить просто нельзя — все заснут). Система об этом узнает, проанализирует и в другом магазине порекомендует тому же покупателю баян, чтобы он играл и радовался. То есть первая задача, решаемая с помощью кластеризации, — передача интереса.

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

Как было отмечено выше, наша база товаров состоит из каталогов нескольких десятков тысяч интернет-магазинов, работающих на платформе «1С-Битрикс». Пользователи вводят туда текстовые описания разной длины, кто-то добавляет марки товаров, модели, производителей. Составить непротиворечивую точную единую систему сбора и классификации всех товаров из десятка тысяч магазинов было бы дорого, долго и тяжело. А мы хотели найти способ, как быстро склеить похожие товары между собой и заметно повысить качество коллаборативной фильтрации. Ведь если система хорошо знает покупателя, то неважно, какими конкретными товарами и их марками он интересуется, система всегда найдёт, что ему предложить.

Выбор инструментария


В первую очередь необходимо было выбрать систему хранения, подходящую для работы с «большими» данными. Я немного повторюсь, но это полезно для закрепления материала. Для себя мы выделили четыре «лагеря» баз данных:

  • SQL на MapReduce: Hive, Pig, Spark SQL. Загрузите в РСУБД один миллиард строк и выполните агрегацию данных — станет понятно, что этот класс систем хранения «не очень» подходит для данной задачи. Поэтому, интуитивно, можно попробовать использовать SQL через MapReduce (что и сделал когда-то Facebook). Очевидные минусы тут — скорость выполнения коротких запросов.
  • SQL на MPP (massive parallel processing): Impala, Presto, Amazon RedShift, Vertica. Представители этого лагеря утверждают, что SQL через MapReduce – это тупиковый путь, поэтому нужно, фактически, на каждой ноде, где хранятся данные, поднимать драйвер, который будет быстро обращаться к этим данным. Но многие из перечисленных систем страдают от нестабильности.
  • NoSQL: Cassandra, HBase, Amazon DynamoDB. Третий лагерь говорит: BigData — это NoSQL. Но мы же понимаем, что NoSQL — это, фактически, набор «memcached-серверов», объединённых в кольцевую структуру, которые могут быстро выполнить запрос типа «взять по ключу значение и вернуть ответ». Ещё могут вернуть отсортированный в оперативной памяти по ключу набор данных. Это почти всё — забудьте про JOINS.
  • Классика: MySQL, MS SQL, Oracle и т.д. Монстры не сдаются и утверждают, что всё вышеперечисленное — фигня, горе от ума, и реляционные базы прекрасно работают с BigData. Кто-то предлагает фрактальные деревья (https://en.wikipedia.org/wiki/TokuDB), кто-то — кластеры. Монстры ведь тоже жить хотят.

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

  • Spark MLlib (Scala/Java/Python/R) — когда много данных.
  • scikit-learn.org (Python) — когда мало данных.
  • R — вызывает противоречивые чувства по причине жуткой кривизны реализации (доверь программирование математикам и статистам), но готовых решений много, а недавняя интеграция со Spark очень радует.



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

Поиск алгоритма кластеризации


Нам нужно было сначала придумать, каким образом объединять в кластроиды текстовые описания товаров (названия и краткие описания). Обработка текстов на естественных языках — это отдельная огромная область Computer Science, включающая в себя и машинное обучение и Information retrieval
и лингвистику и даже (тадам!) Deep Learning.

Когда данных для кластеризации десятки, сотни, тысячи — подойдет практически любой классический алгоритм, даже иерархической кластеризации. Проблема в том, что алгоритмическая сложность иерархической кластеризации равна примерно O(N3). То есть надо ждать «миллиарды лет», пока он отработает на нашем объёме данных, на огромном кластере. А ограничиваться обработкой лишь какой-то выборки было нельзя. Поэтому иерархическая кластеризация в лоб нам не подошла.

Потом мы обратились к «бородатому» алгоритму K-means:



Это очень простой, хорошо изученный и распространённый алгоритм. Однако и он работает на больших данных очень медленно: алгоритмическая сложность равна примерно О(nkdi). При n = 10 000 000 (количество товаров), k = 1 000 000 (ожидаемое количество кластеров), d = <1 000 000 (видов слов, размерность вектора), i = 100 (примерное количество итераций), О = 1021 операций. Для сравнения, возраст Земли составляет 1,4*1017 секунд.

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

Чтобы осуществить кластеризацию, мы решили на первом этапе превратить текст в векторы. Вектор — это некая точка в многомерном пространстве, скопления которых и будут искомыми кластерами.

Нам нужно было кластеризовать описания товаров, состоящие из 2-10 слов. Самое простое, классическое решение в лоб или в глаз — bag of words. Раз у нас есть каталог, то мы можем определить и словарь. В результате, у нас получился корпус размером примерно миллион слов. После стемминга их осталось около 500 тыс. Отбросили высокочастотные и низкочастотные слова. Конечно, можно было использовать tf/idf, но решили не усложнять.

Какие есть недостатки у этого подхода? Получившийся огромный вектор дорого потом обсчитывать, сравнивая его похожесть с другими. Ведь что представляет собой кластеризация? Это процесс поиска схожих между собой векторов. А когда они размером по 500 тыс., поиск занимает очень много времени, поэтому надо научиться их сжимать. Для этого можно использовать Kernel hack, хэшируя слова не в 500 тыс. атрибутов, а в 100 тыс. Хороший, рабочий инструмент, но могут возникать коллизии. Мы его не стали использовать.

И напоследок расскажу ещё об одной технологии, которую мы отбросили, но сейчас всерьёз подумываем начать её использовать. Это Word2Vec, методика статистической обработки текста путем сжатия размерности текстовых векторов двуслойной нейронной сетью, разработанная в Google. По сути, это развитие старых добрых вечных статистических N-gram моделей текста, только используется skip-gram вариация.

Первая задача, которая красиво решается с помощью Word2Vec: уменьшение размерности за счёт «матричной факторизации» (в кавычках специально, т.к. никаких матриц там нет, но эффект очень похож). То есть, получается, например, не 500 тыс. атрибутов, а всего лишь 100. Когда встречаются похожие «по контексту» слова, система считает их «синонимами» (с натяжкой конечно, кофе и чай могут объединиться). Получается, что точки этих похожих слов в многомерном пространстве начинают совпадать, то есть близкие по значению слова кластеризуются в общее облако. Скажем, «кофе» и «чай» будут близкими по значению словами, ведь они часто встречаются в контексте вместе. Благодаря библиотеке Word2Wec можно уменьшить размер векторов, а сами они получаются более осмысленными.

Этой теме много лет: Latent semantic indexing и её вариации через PCA/SVD изучили хорошо, да и решение в лоб через кластеризацию колонок или строк матрицы term2document, по сути, даст похожий результат — только делать это придётся очень долго.

Весьма вероятно, что мы всё же начнём применять Word2Vec. К слову, её использование также позволяет находить опечатки и играться с векторной алгеброй предложений и слов.

«Я построю свой лунапарк!..»


В итоге, после всех долгих поисков по научным публикациям, мы написали свой вариант k-Means — Clustering by Bootstrap Averaging для Spark.

По сути, это иерархический k-Means, делающий предварительный послойный сэмплинг данных. На обработку 10 млн товаров ушло достаточно разумное время, часы, хотя и потребовалось задействовать кучу серверов. Но результат не устроил, т.к. часть текстовых данных кластеризовать не удалось — носки клеились с самолетами. Метод работал, но очень грубо и неточно.

Оставалась надежда на старые, но подзабытые сейчас вероятностные методики поиска дубликатов или «почти дубликатов» — locality-sensitive hashing.

Вариант метода, описанный тут , требовал использования преобразованных из текста векторов одинакового размера, для дальнейшего «раскидывания» их по хэш-функциям. И мы взяли MinHash.

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



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



Pr[ hmin(A) = hmin(B) ] = J(A, B)

Таким образом мы решили задачу сжатия измерений и приведения векторов к единому количеству измерений.

Text shingling


Я совсем забыл рассказать, что мы отказались от векторизации текстов в лоб, т.к. названия и краткие описания товаров создавали чрезвычайно разряженные вектора, страдающие от «проклятья размерности».

Названия товаров обычно были примерно такого вида и размера:
«Штаны красные махровые в полоску»
«Красные полосатые штаны»


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

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

{«штан», «таны», «аны », «ны к», «ы кра», «крас», …}

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

Повторюсь ещё раз: мы отказались от сильно разреженных текстовых векторов, заменили каждый текст на множество (set) шинглов, а затем привели их к единому размеру с помощью MinHash.

Векторизация


В результате мы решили задачу векторизации каталога следующим образом. С помощью MinHash-сигнатуры получили векторы небольшого размера от 100 до 500 (размер выбирается одинаковым для всех векторов). Теперь их нужно сравнить каждый с каждым, чтобы сформировать кластеры. В лоб, как мы уже знаем, это очень долго. А благодаря алгоритму LSH (Locality-Sensitive Hashing) задача решилась в один проход.

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

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


Традиционно используют несколько bands — наборов хэш-функций. Но мы ещё больше упростили задачу — оставили всего один band. Допустим, берутся первые 40 элементов вектора и заносятся в хэш-таблицу. А дальше туда попадают элементы, которые имеют такой же кусок сначала. Вот и всё! Для начала — прекрасно. Если нужна большая точность, то можно работать с группой bands, но тогда на финальной части алгоритма придётся дольше собирать из них взаимно похожие объекты.

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

Теперь у нас всего за два-три часа на 8 spot-серверах кластеризуется 10 млн. товаров в примерно один миллион кластеров. Фактически, в один проход, потому что band лишь один. Поэкспериментировав с настройками, мы получили достаточно адекватные кластеры: яхты, автомобили, колбаса и т.д., уже без глупостей вроде «топор + самолет». И теперь эта сжатая кластерная модель используется для улучшения точности работы системы персональных рекомендаций.

Итоги


В коллаборативных алгоритмах мы стали работать уже не с конкретными товарами, а с кластерами. Появился новый товар, мы нашли кластер, положили его туда. И обратный процесс — рекомендуем кластер, затем выбираем из него самый популярный товар и возвращаем его пользователю. Использование кластерного каталога в разы улучшило точность рекомендаций (измеряем recall текущей модели и за месяц ранее). И это всего лишь за счёт сжатия данных (названий) и объединения их по смыслу. Поэтому хочу посоветовать вам — ищите простые решения ваших задач, связанных с большими данными. Не пытайтесь что-то усложнять. Я верю в то, что всегда можно найти простое, эффективное решение, которое за 10% усилий решит 90% задач! Всем удачи и успехов в работе с большими данными!
Автор: @1cbitrix
1С-Битрикс
рейтинг 241,62

Комментарии (35)

  • +2
    Эмммм. «Мы попробовали вот это это и вот там еще поковырялись»

    Молодцы. Но как-то мало подробностей, всё в общих чертах.
    • 0
      А какие подробности интересуют? Реализация оказалась довольно простой: spark + несколько десятков грубо строк. Гораздо более сложным оказалось построить подходящую математическую модель — но в результате она выглядит ясной, очень простой и интуитивно понятной.

      Мы просеиваем как-бы через вероятностное решено сжатые строки и похожие склеиваются.
  • +1
    А откуда взялась эта цифра в миллион кластеров? Большие кластеры (если их считать по честному) в результате побились, малые — склеились.

    Статья очень хороша в плане описания как решить практическую задачу на ограниченных ресурсах за разумное время, но всё-же — откуда цифры?
    • 0
      Миллион кластеров — круглая целевая цифра, с потолка. Решили сжать до миллиона и посмотреть что получится. Получилось, стало меньше данных, стало удобнее работать с ними.
    • 0
      Попробую подробнее пояснить, в деталях по цифрам.

      Итак, если взять кластеризацию из семейста EM, например K-Means, то он у нас сойдется на каком-то числе кластеров. Если выйти из его итерации раньше — кластера станут больше, но менее точными. Т.е. можно жертвуя одним, получать другое. И посмотреть на выходе — устраивает ли результат.

      LSH-кластеризация еще проще. Если ее делать по-честному, нужно определить число bands и число слотов в них — чем больше, тем меньше погрешность, формула в книжке есть этой: www.mmds.org. Но узкое место — после раскидывания объектов по слотам и бендам, придется идентичные кластера склеивать. Более простое решение — взять один бэнд и он его размера будет плясать число попавших на него кластеров. Кто не попал — будет одиночкой. Грубо, но результаты довольно неплохие и работающие.

      Могу еще подробнее пояснить, с выкладками. Многим может оказаться полезным.
      • +1
        А почему K-Means должен сойтись на каком-то числе кластеров?
        • 0
          Ох, простите, ввел наверно в заблуждение. В k-means мы же задаем число кластеров сразу, а их центры итерационно сходятся все точнее и точнее (уменьшая ошибку).
          • +1
            Да не то что ввели, скорее удивили :)
            Просто кластеризация в отличие от классификации не имеет точного ответа сколько кластеров (классов) должно получиться в результате.
            Сколько зададите, столько и сделаете.
            • +1
              Поспорю :-) Оптимальное число кластеров можно попытаться определить, например измеряя плотность кластеров и поймав точку резкого ее изменения — когда куча мелких схлопываются в небольшое число крупных.

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

              Мы хотели склеить именно дубликаты и частично небольшие узкие темы.
              • +1
                Мы хотели склеить именно дубликаты и частично небольшие узкие темы.
                вот с этого и надо было начинать статью
            • +1
              Плотностные (density-based) методы кластеризации (например, DBSCAN), в каком-то смысле, как раз «пытаются» дать ответ, сколько кластеров.
  • +2
    Спасибо за статью. Всегда интересно познакомиться с чужим опытом.

    Обратите внимание на критику местного сообщества (не критикантство, а именно критику, в ее правильном, если можно так сказать, научном значении). Сейчас ваш подход можно отнести к классу «внезапно эвристических»:
    — мы почему-то решили делать кластеризацию
    — почему-то именно K-Means'ом
    — и почему-то именно на 1 миллион кластеров.
    Без всякого обоснования выбора метода и гиперпараметров.

    Тем не менее, еще раз спасибо вам за статью — было очень интересно и полезно почитать и подумать. Продолжайте, пожалуйста, экспериментировать с данными и публиковать свои наработки. Читатели, возможно, не всегда могут это явно выразить, но точно ценят интересный контент.
    • 0
      1) Почему решили делать кластеризацию? Склеить дубли и похожие товары — чтобы было дешевле обсчитывать товарные рекомендации и улучшить их качество.
      2) Начали с самого простого и понятного и, главное, доступного в библиотеках Spark MLLib. Не лезь же сразу в нечеткую или спектральную кластеризацию :-) И итерационно пришли в тупик на наших объемах данных.
      3) Число понравилось :-)
  • +1
    Алекс, ваш подход мне понятен. Я к тому, что ему сильно недостает научной строгости.
    Кластеризация не единственный (кто-то может даже сказать, что совсем неправильный) подход к работе с дублями.
    Более того, нет никакой гарантии, что кластер 117 и кластер 239251 не содержат дубли друг друга, а в кластер 791512 не вошли похожие, но все же разные товары (или даже вообще непохожие, но с похожими описаниями). Иными словами, кластеризация, строго говоря, не устраняет дубли.
    • 0
      Согласен, но научная строгость слишком дорога в условиях частых релизов и дедлайнов. Мы больше примеряем методы — получить 90% результата за 10% усилий и радуемся, если получилось :-)
      • +1
        Не подумайте, что я придираюсь, но это все же голословные утверждения.
        Вы ведь тоже не за 5 минут к вашему текущему решению пришли. Потратили деньги и немалые.
        А ведь возможно существует другой алгоритм, который вы бы реализовали гораздо быстрее (то есть потратили меньше денег и времени) и который работает быстрее и использует меньше ресурсов (то есть тратит меньше денег и времени).

        Кроме того, что такое «90% результата»? Точность 90%? Так это еще тоже надо доказать, что у вас точность 90%.

        Еще раз повторюсь, ни в коей мере не умаляю вашу работу. Наоборот, всячески ее поддерживаю, в том числе вот так вот неловко намекая на возможность и даже необходимость значительного улучшения алгоритма.
    • 0
      В нашем случае используется четкая кластеризация в неевклидовом пространстве (есть только метрика похожести и… всё), когда один товар может быть в одном и только одном кластере. Ну и мы не первые придумали кластеризацию для борьбы с дублями то, первые вроде сделал в AltaVista Андрей Бродер.
      • 0
        Если вы делите на 1 миллион кластеров, то и получите 1 миллион кластеров, даже если товаров у вас всего два. Разве не так?
        • 0
          Про ценность хороших алгоритмов полностью поддерживаю! Да, вот тут наука рулит миром, вот тут сортировка Шелла рубит к чертям допотопные сортировки выборкой и вставкой :-)

          Смотрите, как работает у нас алгоритм.

          Товаров — 2. Они если похожие, то с вероятностью P («сигмоидная» функция, зависит от числа бэндов и размерности minhash, описана тут в 3 главе, п.3.4.2: ) они попадут в один кластер. Если товары различаются — то попадут в отдельные кластера и кластеров будет 2. Это — четка кластеризация. Если бы была нечетка (c-means и т.п.) — то могли бы размазаться по кластерам, но нам это не нужно.

          Товаров — 10. 7 из них похожи друг на друга, 3 не похожи не на кого. С большой вероятностью образуется 4 кластера — в одном взаимно похожие, в других трех — по одному товару.

          Товаров — 10 000 000. Можно подобрать параметры P, чтобы получилось грубо миллион кластеров. И т.п.

          Т.е. взаимно-похожие попадут в кластера, а взаимно-непохожие будут отдельно. Но с вероятностью… научно строго нужно показать параметры, величину ошибки и т.п. Но визуально получилось неплохо.

  • +1
    Статья очень интересная, спасибо. Уточнение — разве Spark.SQL на MR выполняется? Всегда считал, что он к MPP ближе и скорее во вторую пачку к Impala попадает.
    • 0
      ну да, но на MR внутри Spark — т.е. быстрее и в памяти как правило. Т.е. не «медленно», как через Hadoop MapReduce.
      • 0
        А что из книжек посоветуете почитать по Natural Language Processing?
      • +1
        Упрощая, можно сказать, что MapReduce — это когда после map всегда идет shuffle, чтобы перекомпоновать данные для последующего reduce.

        В Spark'е shuffle происходит далеко не всегда (более того, с каждой новой версией его оптимизирующий движок все более усложняется, чтобы еще больше минимизировать и вообще устранить запуск shuffle). В этом смысле Spark совсем не MapReduce.
  • +2
    Я, конечно, все понимаю, но 10 миллионов элементов и «большие данные»? Серьезно?
    Кроме того:
    О = 1021 операций. Для сравнения, возраст Земли составляет 1,4*1017 секунд.
    1021 — конечно много, но тем не менее осязаемо, сравнение с возрастом земли в секундах — это примерно как сравнение с числом Авогадро — бессмысленное и бесполезное.
    • 0
      Понимаете в чем дело, в лоб задача на MapReduce в разумное время тупо не решалась :-) НЕ РЕШАЛАСЬ. Пришлось искать алгоритмы и писать свою их реализацию для спарка, совсем не классическую.
      • 0
        Есть много задач, которые требуют больших вычислительных ресурсов, но, тем не менее, не относятся к «big data». Или теперь любую «не-классическую», как вы называете (хотя приемы то все классические) реализацию называть «big data»? Подбор коллизий к заданному хешу тоже трудоемкая задача, но вряд ли кому-то стукнет в голову идея называть это «big data».
  • +2
    Как-то задача нечетко сформулирована. Насколько я понял, необходимо найти группы товаров, описания которых синтаксически схожи. При этом, хочется избавиться от шума, т.е. от ошибок в описаниях. Это, по большому счету, две разные задачи, которые однако в обработке текстов можно свести к одной задаче — выделению признаков.
    Задача 1: для двух описаний определить метрику (ну наверное, метрику, раз кластеризацию хочется делать в евклидовом пространстве, имея ввиду задачу 2) схожести так, чтобы игнорировать ошибки написания. Такая задача решается в алгоритмах поиска исправления поискового запроса с опечатками. Один из наиболее распространенных методов — выделить из текстов символьные n-граммы, т.е. представить каждый текст как множество n-грамм (может быть, снабженных дополнительным атрибутом, частотой это n-граммы в тексте) и сравнить два множества. Если множества почти одни и те же, то и исходные тексты похожи. Вы, насколько я понимаю, примерно это и использовали, выделяемые из текстов шинглы и есть эти самые n-граммы. Тут можно еще на основе статистики встречаемости шинглов (n-грамм) во всем корпусе определить их важность (tf/idf или какие-то другие критерии). Важность можно умножать на частоту шингла в тексте описания.
    Задача 2: найти на основе определенной метрики множества схожих описаний товаров. Тексты описаний короткие, поэтому задача кластеризации должна решаться легче, в том смысле, что похожие описания должны образовывать ярко выраженные кластера. Если решать задачу в лоб, то необходимо сравнить каждое описание с каждым другим описанием, т.е. имя N описаний необходимо сделать N^2 сравнений. Это, понятное дело, очень долго при большом N. Я обычно использую инвертированный поисковый индекс для сравнения двух текстов. Все тексты индексирую в таком индексе, в качестве элементов для индексирования выступают шинглы (слова или последовательности слов или символов). Для текста, который надо сравнить со всеми остальными, выделяю шинглы, ищу тексты, в которых эти шинглы встречаются и, таким образом, нахожу множества шинглов для каждого текста (пересечение). Те тексты, пересечение которых достаточно большое, выбираю для подсчета метрики схожести. В результате, вместо N^2 получаю N log N, что для больших N быстро.
    На практике, полученное таким образом множество схожих текстов еще надо проредить. Для этого можно придумать много алгоритмов, но обычно достаточно достаточно простых вычислений на основе статистики корпуса индексированных текстов. Я обычно использую библиотеку xapian для организации индексирования, она написана на C++, но есть интерфейсы на python. Подобный подход реализовал, например, для онлайн кластеризации текстов из соцмедиа. Там идет поток документов порядка 10-50 в секунду, надо образовывать кластера схожих документов. Алгоритмы, конечно, посложнее, чем я описал, но принцип тот же. Для кластеризации используется один мастер-сервер, который ищет похожие документов для переданного в потоке, а потом передает документ на индексирование в slave-сервера, которые представляют собой такие вот поисковые индексы. Один мастер и 5 слейвов вполне себе справляются с такой нагрузкой.
    • 0
      Проблема одна — данных много, 10 млн. объектов и в лоб на MR-не решается. Пришлось искть хаки.
      • 0
        Но за идеи — спасибо! Думал про обратные индексы, но данных многовато показалось. Каждый документ из 10 миллионов нужно же по индексу прогонять сначала для индексации, затем при кластеризации.
    • 0
      Для текста, который надо сравнить со всеми остальными, выделяю шинглы, ищу тексты, в которых эти шинглы встречаются и, таким образом, нахожу множества шинглов для каждого текста (пересечение). Те тексты, пересечение которых достаточно большое, выбираю для подсчета метрики схожести. В результате, вместо N^2 получаю N log N, что для больших N быстро.


      Давайте подумаем. Вот у меня 10 миллионов объектов. Нужно сравнить каждый с каждым. Это N^2 — дофига. Но если запросить «похожие» на текущий объект («похожесть» булевская, по обратному индексу), то да, получим список самых похожих — который берем и сравниваем уже объекты из него с текущим. Операций гораздо меньше, чем N^2.

      Проиндексировать 10 млн. можно в Lucene за довольно разумное время — часы даже на одной железке. Искать по индексу из 10 млн. объектов булевым пересечением в памяти (Lucene это делает за нас) можно за десятки, ну может редко, сотни миллисекунд.

      Отличная идея, работающая, простая, да, мне очень нравится.

      • 0
        Думал про обратные индексы, но данных многовато показалось.

        Проиндексировать 10 млн. можно в Lucene за довольно разумное время — часы даже на одной железке. Искать по индексу из 10 млн. объектов булевым пересечением в памяти (Lucene это делает за нас) можно за десятки, ну может редко, сотни миллисекунд.


        Lucene == обратные инедксы %)
        • +1
          Да знаю :-) Это моя настольная книжка. Просто хочется не программировать, а взять готовый опенсорс :-)
  • 0
    Действительно просто k-means, а не k-means++? Если да, то почему?
  • +1
    Согласен, k-means++ лишен ряда недостатков по сравнению с k-means, в частности при выборе начальных кластеров.
    Вместо k-means можно использовать простое сравнение векторов по косинусу — быстро и просто — только та же проблема в выборе первичных векторов-кластеров.

    Latent semantic indexing и её вариации через PCA/SVD изучили хорошо, да и решение в лоб через кластеризацию колонок или строк матрицы term2document, по сути, даст похожий результат — только делать это придётся очень долго.

    — попробуйте BigARTM К.Воронцова, это реализация LSA без SVD, работает быстро даже на больших массивах, разбираться, правда, долго.

    А вообще закон больших чисел говорит, что во многих задачах по Big data достаточно частотности, все эти TFiDF и их вариации помрут на больших объемах.

    Мы представляем текст в виде шинглов, кусков.

    Это решение было предложено гугловцами еще в 2007-ом в виде реализации на sim hash (можно на min hash). Для поиска дублей — оптимально — скорость высокая, точность можно варьировать. Архитектура, правда, не простая получается при больших объемах.

    Спасибо за статью — хорошее пособие для начинающих «бигдатовцев».

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

Самое читаемое Разработка