Comments 35
Эмммм. «Мы попробовали вот это это и вот там еще поковырялись»
Молодцы. Но как-то мало подробностей, всё в общих чертах.
Молодцы. Но как-то мало подробностей, всё в общих чертах.
А какие подробности интересуют? Реализация оказалась довольно простой: spark + несколько десятков грубо строк. Гораздо более сложным оказалось построить подходящую математическую модель — но в результате она выглядит ясной, очень простой и интуитивно понятной.
Мы просеиваем как-бы через вероятностное решено сжатые строки и похожие склеиваются.
Мы просеиваем как-бы через вероятностное решено сжатые строки и похожие склеиваются.
А откуда взялась эта цифра в миллион кластеров? Большие кластеры (если их считать по честному) в результате побились, малые — склеились.
Статья очень хороша в плане описания как решить практическую задачу на ограниченных ресурсах за разумное время, но всё-же — откуда цифры?
Статья очень хороша в плане описания как решить практическую задачу на ограниченных ресурсах за разумное время, но всё-же — откуда цифры?
Миллион кластеров — круглая целевая цифра, с потолка. Решили сжать до миллиона и посмотреть что получится. Получилось, стало меньше данных, стало удобнее работать с ними.
Попробую подробнее пояснить, в деталях по цифрам.
Итак, если взять кластеризацию из семейста EM, например K-Means, то он у нас сойдется на каком-то числе кластеров. Если выйти из его итерации раньше — кластера станут больше, но менее точными. Т.е. можно жертвуя одним, получать другое. И посмотреть на выходе — устраивает ли результат.
LSH-кластеризация еще проще. Если ее делать по-честному, нужно определить число bands и число слотов в них — чем больше, тем меньше погрешность, формула в книжке есть этой: www.mmds.org. Но узкое место — после раскидывания объектов по слотам и бендам, придется идентичные кластера склеивать. Более простое решение — взять один бэнд и он его размера будет плясать число попавших на него кластеров. Кто не попал — будет одиночкой. Грубо, но результаты довольно неплохие и работающие.
Могу еще подробнее пояснить, с выкладками. Многим может оказаться полезным.
Итак, если взять кластеризацию из семейста EM, например K-Means, то он у нас сойдется на каком-то числе кластеров. Если выйти из его итерации раньше — кластера станут больше, но менее точными. Т.е. можно жертвуя одним, получать другое. И посмотреть на выходе — устраивает ли результат.
LSH-кластеризация еще проще. Если ее делать по-честному, нужно определить число bands и число слотов в них — чем больше, тем меньше погрешность, формула в книжке есть этой: www.mmds.org. Но узкое место — после раскидывания объектов по слотам и бендам, придется идентичные кластера склеивать. Более простое решение — взять один бэнд и он его размера будет плясать число попавших на него кластеров. Кто не попал — будет одиночкой. Грубо, но результаты довольно неплохие и работающие.
Могу еще подробнее пояснить, с выкладками. Многим может оказаться полезным.
А почему K-Means должен сойтись на каком-то числе кластеров?
Ох, простите, ввел наверно в заблуждение. В k-means мы же задаем число кластеров сразу, а их центры итерационно сходятся все точнее и точнее (уменьшая ошибку).
Да не то что ввели, скорее удивили :)
Просто кластеризация в отличие от классификации не имеет точного ответа сколько кластеров (классов) должно получиться в результате.
Сколько зададите, столько и сделаете.
Просто кластеризация в отличие от классификации не имеет точного ответа сколько кластеров (классов) должно получиться в результате.
Сколько зададите, столько и сделаете.
Поспорю :-) Оптимальное число кластеров можно попытаться определить, например измеряя плотность кластеров и поймав точку резкого ее изменения — когда куча мелких схлопываются в небольшое число крупных.
Аналогично, выполняя агломеративную кластеризацию, можно попытаться определить где склеиваются дубли, а где уже пошло дело грубо и склеиваются целые понятийные области.
Мы хотели склеить именно дубликаты и частично небольшие узкие темы.
Аналогично, выполняя агломеративную кластеризацию, можно попытаться определить где склеиваются дубли, а где уже пошло дело грубо и склеиваются целые понятийные области.
Мы хотели склеить именно дубликаты и частично небольшие узкие темы.
Плотностные (density-based) методы кластеризации (например, DBSCAN), в каком-то смысле, как раз «пытаются» дать ответ, сколько кластеров.
Спасибо за статью. Всегда интересно познакомиться с чужим опытом.
Обратите внимание на критику местного сообщества (не критикантство, а именно критику, в ее правильном, если можно так сказать, научном значении). Сейчас ваш подход можно отнести к классу «внезапно эвристических»:
— мы почему-то решили делать кластеризацию
— почему-то именно K-Means'ом
— и почему-то именно на 1 миллион кластеров.
Без всякого обоснования выбора метода и гиперпараметров.
Тем не менее, еще раз спасибо вам за статью — было очень интересно и полезно почитать и подумать. Продолжайте, пожалуйста, экспериментировать с данными и публиковать свои наработки. Читатели, возможно, не всегда могут это явно выразить, но точно ценят интересный контент.
Обратите внимание на критику местного сообщества (не критикантство, а именно критику, в ее правильном, если можно так сказать, научном значении). Сейчас ваш подход можно отнести к классу «внезапно эвристических»:
— мы почему-то решили делать кластеризацию
— почему-то именно K-Means'ом
— и почему-то именно на 1 миллион кластеров.
Без всякого обоснования выбора метода и гиперпараметров.
Тем не менее, еще раз спасибо вам за статью — было очень интересно и полезно почитать и подумать. Продолжайте, пожалуйста, экспериментировать с данными и публиковать свои наработки. Читатели, возможно, не всегда могут это явно выразить, но точно ценят интересный контент.
1) Почему решили делать кластеризацию? Склеить дубли и похожие товары — чтобы было дешевле обсчитывать товарные рекомендации и улучшить их качество.
2) Начали с самого простого и понятного и, главное, доступного в библиотеках Spark MLLib. Не лезь же сразу в нечеткую или спектральную кластеризацию :-) И итерационно пришли в тупик на наших объемах данных.
3) Число понравилось :-)
2) Начали с самого простого и понятного и, главное, доступного в библиотеках Spark MLLib. Не лезь же сразу в нечеткую или спектральную кластеризацию :-) И итерационно пришли в тупик на наших объемах данных.
3) Число понравилось :-)
Алекс, ваш подход мне понятен. Я к тому, что ему сильно недостает научной строгости.
Кластеризация не единственный (кто-то может даже сказать, что совсем неправильный) подход к работе с дублями.
Более того, нет никакой гарантии, что кластер 117 и кластер 239251 не содержат дубли друг друга, а в кластер 791512 не вошли похожие, но все же разные товары (или даже вообще непохожие, но с похожими описаниями). Иными словами, кластеризация, строго говоря, не устраняет дубли.
Кластеризация не единственный (кто-то может даже сказать, что совсем неправильный) подход к работе с дублями.
Более того, нет никакой гарантии, что кластер 117 и кластер 239251 не содержат дубли друг друга, а в кластер 791512 не вошли похожие, но все же разные товары (или даже вообще непохожие, но с похожими описаниями). Иными словами, кластеризация, строго говоря, не устраняет дубли.
Согласен, но научная строгость слишком дорога в условиях частых релизов и дедлайнов. Мы больше примеряем методы — получить 90% результата за 10% усилий и радуемся, если получилось :-)
Не подумайте, что я придираюсь, но это все же голословные утверждения.
Вы ведь тоже не за 5 минут к вашему текущему решению пришли. Потратили деньги и немалые.
А ведь возможно существует другой алгоритм, который вы бы реализовали гораздо быстрее (то есть потратили меньше денег и времени) и который работает быстрее и использует меньше ресурсов (то есть тратит меньше денег и времени).
Кроме того, что такое «90% результата»? Точность 90%? Так это еще тоже надо доказать, что у вас точность 90%.
Еще раз повторюсь, ни в коей мере не умаляю вашу работу. Наоборот, всячески ее поддерживаю, в том числе вот так вот неловко намекая на возможность и даже необходимость значительного улучшения алгоритма.
Вы ведь тоже не за 5 минут к вашему текущему решению пришли. Потратили деньги и немалые.
А ведь возможно существует другой алгоритм, который вы бы реализовали гораздо быстрее (то есть потратили меньше денег и времени) и который работает быстрее и использует меньше ресурсов (то есть тратит меньше денег и времени).
Кроме того, что такое «90% результата»? Точность 90%? Так это еще тоже надо доказать, что у вас точность 90%.
Еще раз повторюсь, ни в коей мере не умаляю вашу работу. Наоборот, всячески ее поддерживаю, в том числе вот так вот неловко намекая на возможность и даже необходимость значительного улучшения алгоритма.
В нашем случае используется четкая кластеризация в неевклидовом пространстве (есть только метрика похожести и… всё), когда один товар может быть в одном и только одном кластере. Ну и мы не первые придумали кластеризацию для борьбы с дублями то, первые вроде сделал в AltaVista Андрей Бродер.
Если вы делите на 1 миллион кластеров, то и получите 1 миллион кластеров, даже если товаров у вас всего два. Разве не так?
Про ценность хороших алгоритмов полностью поддерживаю! Да, вот тут наука рулит миром, вот тут сортировка Шелла рубит к чертям допотопные сортировки выборкой и вставкой :-)
Смотрите, как работает у нас алгоритм.
Товаров — 2. Они если похожие, то с вероятностью P («сигмоидная» функция, зависит от числа бэндов и размерности minhash, описана тут в 3 главе, п.3.4.2: ) они попадут в один кластер. Если товары различаются — то попадут в отдельные кластера и кластеров будет 2. Это — четка кластеризация. Если бы была нечетка (c-means и т.п.) — то могли бы размазаться по кластерам, но нам это не нужно.
Товаров — 10. 7 из них похожи друг на друга, 3 не похожи не на кого. С большой вероятностью образуется 4 кластера — в одном взаимно похожие, в других трех — по одному товару.
Товаров — 10 000 000. Можно подобрать параметры P, чтобы получилось грубо миллион кластеров. И т.п.
Т.е. взаимно-похожие попадут в кластера, а взаимно-непохожие будут отдельно. Но с вероятностью… научно строго нужно показать параметры, величину ошибки и т.п. Но визуально получилось неплохо.
Смотрите, как работает у нас алгоритм.
Товаров — 2. Они если похожие, то с вероятностью P («сигмоидная» функция, зависит от числа бэндов и размерности minhash, описана тут в 3 главе, п.3.4.2: ) они попадут в один кластер. Если товары различаются — то попадут в отдельные кластера и кластеров будет 2. Это — четка кластеризация. Если бы была нечетка (c-means и т.п.) — то могли бы размазаться по кластерам, но нам это не нужно.
Товаров — 10. 7 из них похожи друг на друга, 3 не похожи не на кого. С большой вероятностью образуется 4 кластера — в одном взаимно похожие, в других трех — по одному товару.
Товаров — 10 000 000. Можно подобрать параметры P, чтобы получилось грубо миллион кластеров. И т.п.
Т.е. взаимно-похожие попадут в кластера, а взаимно-непохожие будут отдельно. Но с вероятностью… научно строго нужно показать параметры, величину ошибки и т.п. Но визуально получилось неплохо.
Статья очень интересная, спасибо. Уточнение — разве Spark.SQL на MR выполняется? Всегда считал, что он к MPP ближе и скорее во вторую пачку к Impala попадает.
ну да, но на MR внутри Spark — т.е. быстрее и в памяти как правило. Т.е. не «медленно», как через Hadoop MapReduce.
А что из книжек посоветуете почитать по Natural Language Processing?
Прекрасная книга, читаю с огромным удовольствием. И авторы не уходят в математические дебри, что важно.
www.amazon.com/Speech-Language-Processing-2nd-Edition/dp/0131873210
Но и читать посты и презы очень опытных коллег, порекомендую ServPonomarev
www.amazon.com/Speech-Language-Processing-2nd-Edition/dp/0131873210
Но и читать посты и презы очень опытных коллег, порекомендую ServPonomarev
Упрощая, можно сказать, что MapReduce — это когда после map всегда идет shuffle, чтобы перекомпоновать данные для последующего reduce.
В Spark'е shuffle происходит далеко не всегда (более того, с каждой новой версией его оптимизирующий движок все более усложняется, чтобы еще больше минимизировать и вообще устранить запуск shuffle). В этом смысле Spark совсем не MapReduce.
В Spark'е shuffle происходит далеко не всегда (более того, с каждой новой версией его оптимизирующий движок все более усложняется, чтобы еще больше минимизировать и вообще устранить запуск shuffle). В этом смысле Spark совсем не MapReduce.
Я, конечно, все понимаю, но 10 миллионов элементов и «большие данные»? Серьезно?
Кроме того:
Кроме того:
О = 1021 операций. Для сравнения, возраст Земли составляет 1,4*1017 секунд.1021 — конечно много, но тем не менее осязаемо, сравнение с возрастом земли в секундах — это примерно как сравнение с числом Авогадро — бессмысленное и бесполезное.
Понимаете в чем дело, в лоб задача на MapReduce в разумное время тупо не решалась :-) НЕ РЕШАЛАСЬ. Пришлось искать алгоритмы и писать свою их реализацию для спарка, совсем не классическую.
Есть много задач, которые требуют больших вычислительных ресурсов, но, тем не менее, не относятся к «big data». Или теперь любую «не-классическую», как вы называете (хотя приемы то все классические) реализацию называть «big data»? Подбор коллизий к заданному хешу тоже трудоемкая задача, но вряд ли кому-то стукнет в голову идея называть это «big data».
Как-то задача нечетко сформулирована. Насколько я понял, необходимо найти группы товаров, описания которых синтаксически схожи. При этом, хочется избавиться от шума, т.е. от ошибок в описаниях. Это, по большому счету, две разные задачи, которые однако в обработке текстов можно свести к одной задаче — выделению признаков.
Задача 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 слейвов вполне себе справляются с такой нагрузкой.
Задача 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 слейвов вполне себе справляются с такой нагрузкой.
Проблема одна — данных много, 10 млн. объектов и в лоб на MR-не решается. Пришлось искть хаки.
Для текста, который надо сравнить со всеми остальными, выделяю шинглы, ищу тексты, в которых эти шинглы встречаются и, таким образом, нахожу множества шинглов для каждого текста (пересечение). Те тексты, пересечение которых достаточно большое, выбираю для подсчета метрики схожести. В результате, вместо N^2 получаю N log N, что для больших N быстро.
Давайте подумаем. Вот у меня 10 миллионов объектов. Нужно сравнить каждый с каждым. Это N^2 — дофига. Но если запросить «похожие» на текущий объект («похожесть» булевская, по обратному индексу), то да, получим список самых похожих — который берем и сравниваем уже объекты из него с текущим. Операций гораздо меньше, чем N^2.
Проиндексировать 10 млн. можно в Lucene за довольно разумное время — часы даже на одной железке. Искать по индексу из 10 млн. объектов булевым пересечением в памяти (Lucene это делает за нас) можно за десятки, ну может редко, сотни миллисекунд.
Отличная идея, работающая, простая, да, мне очень нравится.
Думал про обратные индексы, но данных многовато показалось.
Проиндексировать 10 млн. можно в Lucene за довольно разумное время — часы даже на одной железке. Искать по индексу из 10 млн. объектов булевым пересечением в памяти (Lucene это делает за нас) можно за десятки, ну может редко, сотни миллисекунд.
Lucene == обратные инедксы %)
Да знаю :-) Это моя настольная книжка. Просто хочется не программировать, а взять готовый опенсорс :-)
Действительно просто k-means, а не k-means++? Если да, то почему?
Согласен, k-means++ лишен ряда недостатков по сравнению с k-means, в частности при выборе начальных кластеров.
Вместо k-means можно использовать простое сравнение векторов по косинусу — быстро и просто — только та же проблема в выборе первичных векторов-кластеров.
— попробуйте BigARTM К.Воронцова, это реализация LSA без SVD, работает быстро даже на больших массивах, разбираться, правда, долго.
А вообще закон больших чисел говорит, что во многих задачах по Big data достаточно частотности, все эти TFiDF и их вариации помрут на больших объемах.
Это решение было предложено гугловцами еще в 2007-ом в виде реализации на sim hash (можно на min hash). Для поиска дублей — оптимально — скорость высокая, точность можно варьировать. Архитектура, правда, не простая получается при больших объемах.
Спасибо за статью — хорошее пособие для начинающих «бигдатовцев».
Вместо k-means можно использовать простое сравнение векторов по косинусу — быстро и просто — только та же проблема в выборе первичных векторов-кластеров.
Latent semantic indexing и её вариации через PCA/SVD изучили хорошо, да и решение в лоб через кластеризацию колонок или строк матрицы term2document, по сути, даст похожий результат — только делать это придётся очень долго.
— попробуйте BigARTM К.Воронцова, это реализация LSA без SVD, работает быстро даже на больших массивах, разбираться, правда, долго.
А вообще закон больших чисел говорит, что во многих задачах по Big data достаточно частотности, все эти TFiDF и их вариации помрут на больших объемах.
Мы представляем текст в виде шинглов, кусков.
Это решение было предложено гугловцами еще в 2007-ом в виде реализации на sim hash (можно на min hash). Для поиска дублей — оптимально — скорость высокая, точность можно варьировать. Архитектура, правда, не простая получается при больших объемах.
Спасибо за статью — хорошее пособие для начинающих «бигдатовцев».
Sign up to leave a comment.
Параллельные алгоритмы для обработки BigData: подводные камни и непростые решения