dcheklov: Спасибо за сообщение! Ответил. Кажется, это баг, который вызывают затеганные наблюдения. Попробуйте теперь модуль из моей форкнутой ветки, и скажите, исчез ли баг. Если нет, дайте, пожалуйста, какой-нибудь воспроизводимый пример.
Да, вы правы насчет kaggle-конкурсов, это очень похоже.
Нужен CTR-предиктор известно зачем: оптимальным образом формировать ставку в аукционах реального времени. Также он является составной частью предиктора конверсий. Впрочем, для формирования ставки мало одного предиктора — нужно еще предсказывать вторую цену на аукционе.
Используем, в частности, категориальные фичи контекста бида (id площадки, рекламодателя, кампании и т.д., день недели, время суток, данные юзерагента), исторические данные кликов по кампании и юзеру, а также разные данные из нашей DMP (например, хорошо работают кластера доменов из моего прошлого поста).
Нет, но планируем попробовать GraphX. Если доставать графы посещений доменов более низкого уровня, или вообще интернет-страниц, то без этого, мне кажется, не обойтись.
Ссылки на разную литературу по нахождению сообществ (скопировал из комментария к предыдущей части). Может быть, кто-то заинтересуется.
Статьи:
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 — хорошая книга не только про графы, но и вообще. Есть еще курс на курсере.
Если дело касается коммерческих показателей, то тут критерии используем самые обычные: CTR, post-click-показатели, доходность (по CPM, CPC ...). Трейдеры имеют возможность экспериментировать с множеством тонких ручек. Если хотите узнать про крутые автоматические способы оптимизировать таргетинг, почекайте MOE.
Спасибо за коммент! Куча вопросов :)
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? Спарк вроде, все дела. Или там еще все слишком сыро и нестабильно?
2.1 Про пересечение пользователей разных сегментов — это действительно не проблема, так как это не ухудшает качество таргетинга. Кроме того, сегменты, построенные по кластерам доменов, с большой вероятностью будут пересекаться слабее других как раз из-за того, что построены они по совместным посещениям юзеров. Домены, оказавшиеся в разных кластерах, редко посещаются одним юзером.
2.2 В чем-то ваш подход похож, но не полностью. Во-первых, тут, скорее, нужно считать не самые популярные сайты, а сайты с самым большим affinity (иначе вылезет яндекс, гугл, авито и т.п), так как он делает поправку на глобальную популярность. Во-вторых, если вы решили считать аффинити, то будет уже не так просто. Аффинити можно иначе записать как — не аддитивно по . Если аффинити всех юридических сайтов вместе взятых и какого-то стороннего сайта оказалось небольшим, это не значит, что не окажется отдельных юридических сайтов, имеющих достаточно высокий аффинити для возникновения ребра в графе. Если у сайта есть хотя бы одно-два ребра с кластером, то он уже может оказаться присоединенным к этому кластеру, и это реально будет означать смежные «грани». Вот и преимущество для таргетинга. Другой пример — «семейная мешанина», ее еще сложнее получить без графа.
Мы достаем семпл пользователей с их визитами (у нас они хранятся в hbase), и на их основе считаем количество посещений каждого домена. Затем для пар крупных доменов считаем количество совместных посещений (похоже на apriori). Затем мы считаем affinity и используем его как ребра графа. Про similarity отдельный разговор — мы используем меру Жаккарда по соседям для нахождения сообществ, об этом будет написано в следующем посте, он скоро выйдет :)
Да, сегменты пользователей — это посетители определенного кластера, можно еще задавать различные правила на частоту и недавность посещения. Что вы имеете в виду под пересечениями из первого примера?
Преимущество состоит, скорее, в том, что кластера доменов, в отличие от соцдем-сегментов, позволяют выделить группу, интересующуюся определенной тематикой, без сильного падения объема. С другой стороны, преимущество над тематическими сегментами состоит в том, что кластер доменов может связать воедино несколько неочевидных «граней» интересов, которые часто сосуществуют в одном пользователе. Эти «грани» хорошо проявляются при совместном посещении сайтов разных тематик, однако это очень сложно отследить, анализируя контент страниц или придумывая вручную список урлов.
Для некоторых сегментов, полученных машинным обучением (например, сегменты психотипов или контентный классификатор сайтов, описанные в других статьях нашего блога) объем может достигать нескольких миллионов кук, что не так много в сравнении с общим объемом данных (650 млн кук) и для некоторых целей может быть недостаточно.
Сегменты, полученные по спискам урлов с ручными правилами посещений, по определению неполны. Они годятся для формирования очень точных и качественных маленьких аудиторий, но не наоборот.
Если запирать боту открытую двойку, то он почему-то перестает видеть очевидную вилку.
Нужен CTR-предиктор известно зачем: оптимальным образом формировать ставку в аукционах реального времени. Также он является составной частью предиктора конверсий. Впрочем, для формирования ставки мало одного предиктора — нужно еще предсказывать вторую цену на аукционе.
Используем, в частности, категориальные фичи контекста бида (id площадки, рекламодателя, кампании и т.д., день недели, время суток, данные юзерагента), исторические данные кликов по кампании и юзеру, а также разные данные из нашей DMP (например, хорошо работают кластера доменов из моего прошлого поста).
Статьи:
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 — хорошая книга не только про графы, но и вообще. Есть еще курс на курсере.
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? Спарк вроде, все дела. Или там еще все слишком сыро и нестабильно?
2.2 В чем-то ваш подход похож, но не полностью. Во-первых, тут, скорее, нужно считать не самые популярные сайты, а сайты с самым большим affinity (иначе вылезет яндекс, гугл, авито и т.п), так как он делает поправку на глобальную популярность. Во-вторых, если вы решили считать аффинити, то будет уже не так просто. Аффинити можно иначе записать как
Преимущество состоит, скорее, в том, что кластера доменов, в отличие от соцдем-сегментов, позволяют выделить группу, интересующуюся определенной тематикой, без сильного падения объема. С другой стороны, преимущество над тематическими сегментами состоит в том, что кластер доменов может связать воедино несколько неочевидных «граней» интересов, которые часто сосуществуют в одном пользователе. Эти «грани» хорошо проявляются при совместном посещении сайтов разных тематик, однако это очень сложно отследить, анализируя контент страниц или придумывая вручную список урлов.
Написали бы хоть, на основе какой информации вы пришли к заключению о качестве данных, если у вас есть информация, а то получается нехорошо.
Если у кого-нибудь есть вопросы по данным, исследованию, идеи по улучшению исследования, или другие идеи — с удовольствием прочитал бы!