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