Comments 17
Спасибо за пост, могли бы пояснить почему тематические модели «слишком узки»?
Кажется, что вы прикрываете недостаток и низкое качество данных.
Кажется, что вы прикрываете недостаток и низкое качество данных
Написали бы хоть, на основе какой информации вы пришли к заключению о качестве данных, если у вас есть информация, а то получается нехорошо.
Если у кого-нибудь есть вопросы по данным, исследованию, идеи по улучшению исследования, или другие идеи — с удовольствием прочитал бы!
- Для некоторых сегментов, полученных машинным обучением (например, сегменты психотипов или контентный классификатор сайтов, описанные в других статьях нашего блога) объем может достигать нескольких миллионов кук, что не так много в сравнении с общим объемом данных (650 млн кук) и для некоторых целей может быть недостаточно.
- Сегменты, полученные по спискам урлов с ручными правилами посещений, по определению неполны. Они годятся для формирования очень точных и качественных маленьких аудиторий, но не наоборот.
Спасибо за публикацию.
Я правильно понимаю, что
1. Из большой разреженной матрицы — пользователи и количество просмотренных ими страниц сайтов за определенный период, вы получаете similarity matrix на основе affinity index?
2.Посетители страниц любого из сайтов кластера — это и есть сегменты пользователей? Если да, то какие пересечения сегментов получаются, скажем, для первого примера? И можно подробнее о преимуществах полученных сегментов по сравнению с соц.-дем. характеристиками — почему они не столь широки и таргетирование по ним более эффективно?
Я правильно понимаю, что
1. Из большой разреженной матрицы — пользователи и количество просмотренных ими страниц сайтов за определенный период, вы получаете similarity matrix на основе affinity index?
2.Посетители страниц любого из сайтов кластера — это и есть сегменты пользователей? Если да, то какие пересечения сегментов получаются, скажем, для первого примера? И можно подробнее о преимуществах полученных сегментов по сравнению с соц.-дем. характеристиками — почему они не столь широки и таргетирование по ним более эффективно?
- Мы достаем семпл пользователей с их визитами (у нас они хранятся в hbase), и на их основе считаем количество посещений каждого домена. Затем для пар крупных доменов считаем количество совместных посещений (похоже на apriori). Затем мы считаем affinity и используем его как ребра графа. Про similarity отдельный разговор — мы используем меру Жаккарда по соседям для нахождения сообществ, об этом будет написано в следующем посте, он скоро выйдет :)
- Да, сегменты пользователей — это посетители определенного кластера, можно еще задавать различные правила на частоту и недавность посещения. Что вы имеете в виду под пересечениями из первого примера?
Преимущество состоит, скорее, в том, что кластера доменов, в отличие от соцдем-сегментов, позволяют выделить группу, интересующуюся определенной тематикой, без сильного падения объема. С другой стороны, преимущество над тематическими сегментами состоит в том, что кластер доменов может связать воедино несколько неочевидных «граней» интересов, которые часто сосуществуют в одном пользователе. Эти «грани» хорошо проявляются при совместном посещении сайтов разных тематик, однако это очень сложно отследить, анализируя контент страниц или придумывая вручную список урлов.
1. Хорошо. Жду следующей части.
2. Про пересечения. Не получится ли так, что, например, какие-либо два сегмента состоят большей частью из одних и тех же пользователей? Или это не проблема в этой задаче?
Про формирование тематических сегментов в заданном соц.-дем. ЦА. Допустим, нужны сайты юридической тематики, но объем не достаточно высок. Отбираем среди пользователей этих сайтов, с учетом ЦА, несколько наиболее популярных сайтов, отличных от юридических, чтобы получить требуемый объем. Пока не пойму, чем такой «локальный» метод, с точки зрения таргетированного размещения, хуже, чем полученный 15 кластер в вашем решении.
2. Про пересечения. Не получится ли так, что, например, какие-либо два сегмента состоят большей частью из одних и тех же пользователей? Или это не проблема в этой задаче?
Про формирование тематических сегментов в заданном соц.-дем. ЦА. Допустим, нужны сайты юридической тематики, но объем не достаточно высок. Отбираем среди пользователей этих сайтов, с учетом ЦА, несколько наиболее популярных сайтов, отличных от юридических, чтобы получить требуемый объем. Пока не пойму, чем такой «локальный» метод, с точки зрения таргетированного размещения, хуже, чем полученный 15 кластер в вашем решении.
2.1 Про пересечение пользователей разных сегментов — это действительно не проблема, так как это не ухудшает качество таргетинга. Кроме того, сегменты, построенные по кластерам доменов, с большой вероятностью будут пересекаться слабее других как раз из-за того, что построены они по совместным посещениям юзеров. Домены, оказавшиеся в разных кластерах, редко посещаются одним юзером.
2.2 В чем-то ваш подход похож, но не полностью. Во-первых, тут, скорее, нужно считать не самые популярные сайты, а сайты с самым большим affinity (иначе вылезет яндекс, гугл, авито и т.п), так как он делает поправку на глобальную популярность. Во-вторых, если вы решили считать аффинити, то будет уже не так просто. Аффинити можно иначе записать как
— не аддитивно по 
. Если аффинити всех юридических сайтов вместе взятых и какого-то стороннего сайта оказалось небольшим, это не значит, что не окажется отдельных юридических сайтов, имеющих достаточно высокий аффинити для возникновения ребра в графе. Если у сайта есть хотя бы одно-два ребра с кластером, то он уже может оказаться присоединенным к этому кластеру, и это реально будет означать смежные «грани». Вот и преимущество для таргетинга. Другой пример — «семейная мешанина», ее еще сложнее получить без графа.
2.2 В чем-то ваш подход похож, но не полностью. Во-первых, тут, скорее, нужно считать не самые популярные сайты, а сайты с самым большим affinity (иначе вылезет яндекс, гугл, авито и т.п), так как он делает поправку на глобальную популярность. Во-вторых, если вы решили считать аффинити, то будет уже не так просто. Аффинити можно иначе записать как
2.2 Обычно «самых жадных» (яндекс, гугл, авито) знают в лицо. При необходимости, их можно исключить.
Да, аффинити не аддитивно по набору элементов кластера. Но не могу сказать, что это однозначно указывает на преимущество такого таргетинга. Надо будет разобраться.
Вы используете какие-нибудь критерии, которые сравнивают какой из двух произвольных таргетингов более подходящий? И если да, то какие?
Да, аффинити не аддитивно по набору элементов кластера. Но не могу сказать, что это однозначно указывает на преимущество такого таргетинга. Надо будет разобраться.
Вы используете какие-нибудь критерии, которые сравнивают какой из двух произвольных таргетингов более подходящий? И если да, то какие?
Если дело касается коммерческих показателей, то тут критерии используем самые обычные: CTR, post-click-показатели, доходность (по CPM, CPC ...). Трейдеры имеют возможность экспериментировать с множеством тонких ручек. Если хотите узнать про крутые автоматические способы оптимизировать таргетинг, почекайте MOE.
1. Кластеризация которую выдает MCL сильно зависит от симилярити. В своем мануале они пишут что неплохо было бы чтоб она интерпретировалась линейно. То есть вдвое большее значение симилярити подразумевает вдвое большую «похожесть». Поэкспериментируйте с преобразованием исходных значений. Всякое логарифмирование или экспонирование может помочь. У нас mcl'евские кластера доменов активно используются, об этом я немного говорил на прошлом хайлоаде.
Вообще, размеры кластеров на выходе этого алгоритма распределены похоже что по Ципфу, но нас это вполне устраивает. «Ручки» которые можно покрутить у алгоритма как раз меняют крутость распределения.
2. В NetworkX действительно нет кластеризации по-дефолту, однако есть прекрасная, хоть и сыроватая, библиотека Community. Она реализует отличную вот эту статью. К сожалению, даже на тачке со 128 гигами оперативы, NetworkX не справляется с нашими графами, поэтому сейчас пилим тот же алгоритм под Giraph. Об этом я надеюсь 11го сентября в Киеве рассказать.
Вообще, размеры кластеров на выходе этого алгоритма распределены похоже что по Ципфу, но нас это вполне устраивает. «Ручки» которые можно покрутить у алгоритма как раз меняют крутость распределения.
2. В NetworkX действительно нет кластеризации по-дефолту, однако есть прекрасная, хоть и сыроватая, библиотека Community. Она реализует отличную вот эту статью. К сожалению, даже на тачке со 128 гигами оперативы, NetworkX не справляется с нашими графами, поэтому сейчас пилим тот же алгоритм под Giraph. Об этом я надеюсь 11го сентября в Киеве рассказать.
Спасибо за коммент! Куча вопросов :)
1. Какую реализацию MCL вы используете: micans.org или другую? Что там надо покрутить, чтобы смягчить ципфовость?
2. Пробовали ли вы многоуровневый вариант MCL (MLR-MCL) и есть ли вообще смысл пробовать разные сложные модификации MCL?
3. Под симилярити вы, наверное, имеете в виду веса ребер графа (для expand — первого шага MCL)? У нас не MCL, другой алгоритм, он использует меру Жаккарда по соседям в уже готовом графе. Мы сами написали этот алгоритм, и скоро я его опишу подробно (хотя, возможно, от этого изобретения велосипеда уже немного пользы при большом количестве готовых хороших методов).
4. Про библиотеку — так это же алгоритм Louvain! Спасибо, не знал, что это есть в networkX. Мы тоже не используем networkX для кластеризации, только для визуализации, хоть это и не лучший рисовальщик сетей.
5. А вы не пробовали graph-tool? Там есть хороший алгоритм stochastic blockmodeling. По нашему опыту он ест гораздо меньше ресурсов, чем networkX, так что может хватить одной машины (не уверен, конечно, может быть, у вас огромные графы).
6. Почему вы решили пилить на Giraph, а не на GraphX? Спарк вроде, все дела. Или там еще все слишком сыро и нестабильно?
1. Какую реализацию MCL вы используете: micans.org или другую? Что там надо покрутить, чтобы смягчить ципфовость?
2. Пробовали ли вы многоуровневый вариант MCL (MLR-MCL) и есть ли вообще смысл пробовать разные сложные модификации MCL?
3. Под симилярити вы, наверное, имеете в виду веса ребер графа (для expand — первого шага MCL)? У нас не MCL, другой алгоритм, он использует меру Жаккарда по соседям в уже готовом графе. Мы сами написали этот алгоритм, и скоро я его опишу подробно (хотя, возможно, от этого изобретения велосипеда уже немного пользы при большом количестве готовых хороших методов).
4. Про библиотеку — так это же алгоритм Louvain! Спасибо, не знал, что это есть в networkX. Мы тоже не используем networkX для кластеризации, только для визуализации, хоть это и не лучший рисовальщик сетей.
5. А вы не пробовали graph-tool? Там есть хороший алгоритм stochastic blockmodeling. По нашему опыту он ест гораздо меньше ресурсов, чем networkX, так что может хватить одной машины (не уверен, конечно, может быть, у вас огромные графы).
6. Почему вы решили пилить на Giraph, а не на GraphX? Спарк вроде, все дела. Или там еще все слишком сыро и нестабильно?
1. Использовали оригинальную, которая micans.org и писали свою с доп.ручками. В итоге своя осталась в виде прототипа на питоне, потому что реально лучше не стало. В оригинальной версии основной параметр -I, чем он больше тем, кажется, более пологое распределение получается.
2. Не пробовали, но обязательно попробуем, спасибо:)
3. Мы пробовали разные метрики, сейчас для кластеризации доменов тоже используем Жаккара, его и называю симилярити. Идея в том, что даже мера Жаккара может быть интерпретированна по-разному в зависимости от данных. Может оказаться так, что <0.5 — не похожи, 0.5-0.75 немного похожи, 0.75-0.9 похожи и т.д. И сразу понятно, что зависимость не линейная.
4. Пожалуйста:)
5. graph-tool не пробовали, пока не дошли руки.
6. Выбрали жираф, потому что на текущий момент намного меньше телодвижений для того чтоб его поднять и поиграться на кластере. Спарк тоже хочется, и с ним мы тоже поиграемся, но пока в прод не сможем запилить.
2. Не пробовали, но обязательно попробуем, спасибо:)
3. Мы пробовали разные метрики, сейчас для кластеризации доменов тоже используем Жаккара, его и называю симилярити. Идея в том, что даже мера Жаккара может быть интерпретированна по-разному в зависимости от данных. Может оказаться так, что <0.5 — не похожи, 0.5-0.75 немного похожи, 0.75-0.9 похожи и т.д. И сразу понятно, что зависимость не линейная.
4. Пожалуйста:)
5. graph-tool не пробовали, пока не дошли руки.
6. Выбрали жираф, потому что на текущий момент намного меньше телодвижений для того чтоб его поднять и поиграться на кластере. Спарк тоже хочется, и с ним мы тоже поиграемся, но пока в прод не сможем запилить.
Посоветуйте литературу об алгоритмах кластеризации на графах.
Это с удовольствием!
Статьи:
Louvain — иерархическая кластеризация на основе модулярности. Несмотря на недостатки (resolution limit модулярности), один из самых широкоизвестных методов за счет быстроты.
MCL + MLR-MCL — Марковская кластеризация, имитация случайного блуждания на графе + ее иерархический и более быстрый вариант + оптимальное прореживание ребер и другая предобработка.
SCD — алгоритм на основе подсчета замкнутых треугольников внутри и между сообществами, очень качественный и быстрый.
Spinner — на основе label propagation, с подробным описанием как его реализовать распределенно.
Infomap (серия публикаций) — на основе оптимального кодирования узлов графа, чтобы случайное блуждание на нем представлялось наиболее компактно.
RG — «рандомизированный жадная» эвристика для максимизации модулярности (но может быть использована, в принципе, для чего угодно)
Blockmodeling — байесовский подход (довольно зубодробительная статья и все ее последователи тоже).
Стабильные ядра — одно из исследований, как улучшать качество кластеров, если сеть все время эволюционирует.
Ансамблевый подход к кластеризации, на основе тех же стабильных ядер.
Книги:
Data clustering: algorithms and applications (могу прислать электронную версию) — здесь есть одна большая глава про кластеризацию графов, в ней описаны классические методы (Kernigan-Lin, Girwan-Newman, спектральная кластеризация). Про них можно еще посмотреть на курсере, википедии или в других местах.
Mining Massive Datasets — хорошая книга не только про графы, но и вообще. Есть еще курс на курсере.
Статьи:
Louvain — иерархическая кластеризация на основе модулярности. Несмотря на недостатки (resolution limit модулярности), один из самых широкоизвестных методов за счет быстроты.
MCL + MLR-MCL — Марковская кластеризация, имитация случайного блуждания на графе + ее иерархический и более быстрый вариант + оптимальное прореживание ребер и другая предобработка.
SCD — алгоритм на основе подсчета замкнутых треугольников внутри и между сообществами, очень качественный и быстрый.
Spinner — на основе label propagation, с подробным описанием как его реализовать распределенно.
Infomap (серия публикаций) — на основе оптимального кодирования узлов графа, чтобы случайное блуждание на нем представлялось наиболее компактно.
RG — «рандомизированный жадная» эвристика для максимизации модулярности (но может быть использована, в принципе, для чего угодно)
Blockmodeling — байесовский подход (довольно зубодробительная статья и все ее последователи тоже).
Стабильные ядра — одно из исследований, как улучшать качество кластеров, если сеть все время эволюционирует.
Ансамблевый подход к кластеризации, на основе тех же стабильных ядер.
Книги:
Data clustering: algorithms and applications (могу прислать электронную версию) — здесь есть одна большая глава про кластеризацию графов, в ней описаны классические методы (Kernigan-Lin, Girwan-Newman, спектральная кластеризация). Про них можно еще посмотреть на курсере, википедии или в других местах.
Mining Massive Datasets — хорошая книга не только про графы, но и вообще. Есть еще курс на курсере.
Sign up to leave a comment.
Кластеризация графов и поиск сообществ. Часть 1: введение, обзор инструментов и Волосяные Шары