Кластеризація графів і пошук спільнот. Частина 1: вступ, огляд інструментів і Волосяні Кулі

Привіт, Хабр! У нашій роботі часто виникає потреба у виділенні спільнот (кластерів) різних об'єктів: користувачів, сайтів, продуктових сторінок інтернет-магазинів. Користь від такої інформації дуже багатогранна – ось лише кілька областей практичного застосування якісних кластерів:

  1. Виділення сегментів користувачів для проведення цільових рекламних кампаній.
  2. Використання кластерів в якості предикторів («фичей») у персональних рекомендаціях (content-based методах або як додаткова інформація до колаборативної фільтрації).
  3. Зниження розмірності в будь задачі машинного навчання, де в якості фичей виступають сторінки або домени, відвідані користувачем.
  4. Звірення товарних URL між різними інтернет-магазинами з метою виявлення серед них груп, що відповідають одному і тому ж товару.
  5. Компактна візуалізація — людині буде простіше сприймати структуру даних.
З точки зору машинного навчання на отримання таких пов'язаних груп виглядає як типова задача кластеризації. Однак не завжди бувають легко доступні фічі спостережень, у просторі яких можна було б шукати кластери. Контентые або семантичні фічі досить трудомісткі в отриманні, як і інтеграція різних джерел даних, звідки ці штуки можна було б дістати. Зате у нас є DMP під назвою Facetz.DCA, де на поверхні лежать факти відвідувань користувачами сторінок. З них легко отримати кількість відвідувань сайтів, як кожного окремо, так і спільних відвідувань для кожної пари сайтів. Цієї інформації вже достатньо для побудови графів веб-доменів або продуктових сторінок. Тепер задачу кластеризації можна сформулювати як задачу виділення спільнот в отриманих графах.

Забігаючи вперед, скажу, що спільноти веб-доменів нам вже вдалося застосувати з великою користю у рекламних RTB-кампаніях. Класична проблема, з якою стикаються трейдери — це необхідність лавірувати між точністю таргетування та обсягом сегмента. З одного боку, грубий таргетинг за соціально-демографічними ознаками надто широкий і неефективний. З іншого боку, хитрі тематичні сегменти часто занадто вузькі, і зміни порогів ймовірності в класифікаторах не здатні розширити сегмент до необхідного об'єму (скажімо, до декількох десятків мільйонів кук). У той же час, люди, часто відвідують домени з одного кластера, утворюють хороші сегменти як раз для таких широкоохватных кампаній.

У цій серії постів я спробую зупинитися більше на алгоритмічної стороні завдання, ніж на бізнесовій, і зробити наступне. По-перше, описати наші експерименти і показати картинки, які у нас вийшли. По-друге, докладно зупинитися на методах: що ми застосували / хотіли застосувати, але передумали / все ще хочемо застосувати в перспективі.

Багатьом з вас, ймовірно, доводилося кластеризовать дані, але, мабуть, більшість, як і ми, ніколи не кластеризовали граф. Головна особливість кластеризації графів — це відсутність фичей спостережень. У нас немає відстані між двома довільними точками в просторі, тому що немає самого простору, немає норми, і неможливо визначити відстань. Замість цього, у нас є метадані ребер (в ідеалі, для кожної пари вершин). Якщо є «вага» ребра, то його можна інтерпретувати як відстань (або, навпаки, як схожість), і тоді у нас визначені відстані для кожної пари вершин.

Багато з алгоритмів кластеризації в евклідовому просторі підходять і для графів, так як для цих алгоритмів потрібно лише знати відстань між спостереженнями, а не між довільними «точками в просторі». Деякі вимагають саме простір фичей і для графів не годяться (наприклад, k-means). З іншого боку, у графів є багато своїх унікальних властивостей, які теж можна використовувати: компоненти зв'язності, локальні скупчення ребер, місця зациклення інформаційних потоків та ін

Огляд інструментів
До теперішнього моменту люди винайшли величезна кількість методів кластеризації графів — кожен зі своїми перевагами і косяками. В одному з наступних постів розберемо докладніше деякі алгоритми та їх властивості. А поки вважаємо корисним поділитися посиланнями на відкриті інструменти для аналізу графів, де вже реалізовано щось для кластеризації та знаходження спільнот.

  1. Дуже модний і розвивається нині GraphX. Його потрібно було написати першим елементом списку, але як таких готових алгоритмів кластеризації там поки немає (версія 1.4.1). Є підрахунок трикутників і зв'язних компонент, що, укупі з стандартними операціями над Spark RDD, можна використовувати для написання своїх алгоритмів. Поки що у GraphX є апі тільки для scala, що також може ускладнити його використання.

  2. Бібліотека Apache Giraph з назвою Okapi використовує декілька алгоритмів, у тому числі досить новий алгоритм власної розробки під назвою Spinner, заснований на label propagation. Giraph — це надбудова над Hadoop, призначена для обробки графів. У ній майже немає машинного навчання, і для компенсації цього в компанії Telefonica і був створений Okapi. Ймовірно, зараз Giraph виглядає вже не так перспективно на тлі GraphX, але сам алгоритм Spinner добре лягає і на парадигму Spark. Про Spinner можна прочитати тут.

  3. Бібліотека graph-tool для пітона містить кілька новітніх алгоритмів кластеризації і дуже швидко працює. Ми використовували її для звірення URL, які відповідають одному і тому ж товару. Все, що можна, распараллелено по ядер процесора, і для локальних обчислень (графи розміром до пари сотень тисяч вузлів) це найшвидший варіант.

  4. Gephi — відомий інструмент, який ми обійшли увагою, можливо, незаслужено. Довгий час Gephi практично не розвивався, зате у нього з'явилися хороші плагіни, в тому числі для виділення спільнот. Останнім часом проект знову ожив і очікується версія 0.9

  5. GraphLab Create. Це питоновская обгортка над C++, що дозволяє проганяти машинне навчання як локально, так і распределенно (на Yarn). Кластеризації графів там все ще немає, тільки знаходження k-ядер.

  6. Хвалений networkX, незважаючи на достаток алгоритмів, не вміє кластеризовать графи, але тільки аналізувати зв'язкові компоненти і кліки. До того ж він набагато повільніше graph-tool, і по частині візуалізації поступається того ж graph-tool і gephi.

  7. Реалізація алгоритму марківської кластеризації (MCL) від його винахідника. Автор знизив складність звичайного MCL в гіршому випадку з inline_formulainline_formula, де inline_formula— число вузлів, а inline_formula— максимальна ступінь вузла, і ображається, коли алгоритм MCL називають немасштабируемым.Також він додав фішки для регулювання числа кластерів. Однак у MCL було кілька інших серйозних проблем, і незрозуміло, чи вирішені вони. Наприклад, проблема нестабільності розміру кластерів (наш невеликий експеримент видав одну гігантську зв'язну компоненту і багато маленьких кластерочков по 2-3 вузла, але, можливо, ми не знайшли потрібну ручку). Остання новина на сайті датується 2012 роком, що не дуже добре.

  8. Різні реалізації одного з найбільш популярних алгоритмів Louvain: C, для Python, ще для Python. Класична стаття про цей алгоритм: посилання.

  9. Сайт, присвячений алгоритмом Infomap і його модифікацій, від авторів методу. Як і скрізь, є відкритий код. Крім хорошої підтримки і документації, є дивовижні демки, що ілюструють роботу алгоритму: ось і ось. Дізнатися, як працює алгоритм, можна тут.

  10. Пакет для R під назвою igraph. У ньому реалізовано досить багато алгоритмів кластеризації, але ми не можемо сказати нічого конкретного про них, оскільки не вивчали пакет.
Якщо мета — провести відтворений експеримент на невеликих даних, а не виставляти у продакшн готовий продукт, то серед усього перерахованого вище кращими варіантами є, на наш погляд, graph-tool (пункт 3), Gephi (пункт 4) або Infomap (пункт 9).

Наші експерименти
А тепер ми розповімо, як ми формували графи доменів Рунета і околиць, і покажемо картинки з результатами їх кластеризації. У наступній частині нашого циклу буде описаний алгоритм, за допомогою якого були отримані наведені нижче картинки. Це модифікований k-medoids, який ми в кращих традиціях велосипедирования написали на кореневому пітоні, і з допомогою якого вдалося напрочуд добре вирішити деякі завдання. Частина інформації з цього і наступного поста, а також опис деяких інших алгоритмів, є у презентації, яку я розповідав на newprolab в digital october цієї весни:


Дані
Перша задача — кластеризація веб-доменів. З DMP ми беремо дані про відвідування користувачами різних доменів, і на їх основі будуємо граф, де в якості вузлів виступають домени, а в якості ребер — еффініті між доменами. Еффініті (ліфт) між доменами inline_formulainline_formula— це вибіркова оцінка того, наскільки події «відвідування юзером inline_formulaдомену inline_formula» і «відвідування юзером inline_formulaдомену inline_formula» близькі до незалежності. Якщо inline_formula— загальна кількість розглянутих юзерів, а inline_formulaкількість користувачів, що відвідали inline_formula:


Щоб позбутися від шумів, потрібно відфільтрувати домени з дуже маленьким числом відвідувань, а також ребра з низьким еффініті. Практика показує, що досить порогу в 15-20 з поличок і 20-25 по еффініті. При більш високому порозі по еффініті в результаті з'являється дуже багато ізольованих вершин.

Подібний спосіб побудови графа дозволяє побачити в даних досить чітку структуру «спільнот» доменів. Одна з цікавих його особливостей полягає в тому, що найбільші домени (пошукові системи, соціальні мережі, деякі великі магазини і сайти новин), як правило, не мають дуже товстих ребер з жодною іншою вершиною. Це призводить до того, що ці домени знаходяться на відшибі і часто залишаються ізольованими вершинами, не потрапляючи ні в один із кластерів. Ми вважаємо це плюсом, так як спільне відвідування vk.com і якого-небудь вузькоспеціалізованого сайту дійсно мало що говорить про їх зв'язки один з одним.

Треба сказати, що отримати і фільтрувати дані, побудувати граф і порахувати по ньому різні матриці — завдання набагато більш дешева, ніж отримання самих кластерів. Деякі етапи (зокрема, обчислення попарної подібності) вдалося розпаралелити з допомогою пакета pathos (pathos.multiprocessing). На відміну від стандартного питоновского пакету multiprocessing, він не відчуває проблем з серіалізацією, оскільки використовує dill замість pickle. Синтаксис у нього абсолютно ідентичний стандартного multiprocessing. Тут можна почитати про dill.

Візуалізація
Настав час показати трохи картинок з графами (як вони вийшли, ми розповімо в наступній частині). Відомо, що networkX не призначений для візуалізації графів, і що для цієї мети краще звертатися до d3.js, gephi або graph-tool. Ми надто пізно дізналися про це, і всупереч здоровому глузду, все одно продовжили мужньо малювати картинки в networkX. Вийшов не те щоб чистий мед (зокрема, не вдалося налаштувати взаємне відштовхування вузлів і неперекрывающиеся написи), але ми, як могли, старалися і вичавили все що можна з можливостей networkX. У всіх картинках діаметр кружечка (домену) відповідає його відвідуваності, товщина ребра відповідає еффініті, колір кружечка означає приналежність домену кластеру. Колір ребра означає приналежність обох вершин даного кластеру, сірий колір відповідає ребер, що з'єднують вершини з різних кластерів.

Коментарі до кластерів на прикладі одного з графів
Не дуже великий граф з 1285 доменів:

На картинці намальований його розріджений варіант: велика частина ребер видалена за методом local sparsification (він буде описаний в наступній частині), з-за чого угрупування спільноти виглядає більш чітко, і пом'якшується ефект «Великого Волосяного Кулі». Кластерів всього 18. Повний розмір зображення (png).

На кожній вершині написано назву домену і номер кластера, до якого він належить. Зверніть увагу на ізольовані вершини по зовнішньому колу — це, як правило, великі домени без сильних зв'язків з ким-небудь. Нижню частину графа можна охарактеризувати як «жіночу» (вірніше, «сімейну»). Вона досить безладна, ймовірно, тому що з одного браузера (з одного куки) сторінки переглядали кілька членів сім'ї в різний час. З виділенням спільнот в цій частині графа алгоритм не впорався дуже добре.

В один величезний кластер під номером 17 (рожевий) потрапило багато чого — від сайтів з ведення вагітності внизу і медичних сайтів в центрі, до мішанини з прогнозів погоди, жіночих форумів і журналів у верхній частині кластера. До «південно-захід» від нього розташований кулінарний кластер (номер 4):



До «південний схід» від сімейного кластера — нерухомість + пошук роботи (об'єдналися в один кластер номер 2):



До «південь» від кластера 17 розташувалася дуже погано розмічена область. Так, алгоритму не вдалося виділити співтовариство туристичних доменів (вони розкидані по різних спільнот), а в кластер кулінарії потрапив сайт про зброю.

У невеликій кластер 15 (червоний) потрапили, в основному, юридичні сайти:



До «північно-захід» від «сімейної» частини розташовані найбільш чіткі кластери. По всій видимості, браузерами відвідувачів цих сайтів ніхто більше не користується (і це логічно, виходячи з тематик кластерів). По-перше, впадають в очі два щільних кластера: російські (номер 16, цегляний) і українські (номер 12, синій) новинні сайти, причому останній набагато щільніше, хоч і менше за розміром. Можна помітити також, що змінюється ангажованість сайтів уздовж російського кластера:



До «північно-схід» від новинних сайтів розташовуються фільми, серіали онлайн кінотеатри (сірий і жовтий кластери під номерами 3 і 8). Між кластерами фільмів і кластером українських новин як перехідна зона розташований кластер порнографії.



Ще східніше розташований кластер номер 1 — весь казахський інтернет. Поруч з ним — автомобільні сайти (кластер 6, бузковий) і російські спортивні сайти (вони влилися до інших новин в кластер 16).



Далі на південь розташований кластер мультфільмів і дитячих ігор (номер 10, болотний), а також тісно пов'язані з ним шкільні кластера словників, онлайн-решебников і рефератів: великий російський (номер 5, персиковий) і зовсім невеликий український (номер 0, зелений). В кластер номер 0 також потрапили українські сайти всіх тематик, крім новин (їх виявилося зовсім небагато). Шкільні кластери на «півдні» плавно переходять в головний жіночий кластер номер 17.



Останнє, що можна відзначити — кластер книг, розташований на відшибі в «східній» частини картинки:



Зміни за рік
Ось так виглядає той самий граф, тільки намальований без проріджування:


Повний розмір.

А ось так виглядає приблизно аналогічний граф, побудований за майже рік до попереднього. У ньому 12 кластерів:

Повний розмір.

Як можна помітити, що за цей час структура в цілому залишилася колишньою (новинні сайти, великий жіночий кластер, велика розріджена область розважальних сайтів різної спрямованості). З відмінностей можна відзначити остаточне зникнення кластера з музикою за цей час. Ймовірно, за цей час люди для знаходження музики майже перестали користуватися спеціалізованими сайтами, частіше звертаючись до соцмереж і набирає обертів сервісів начебто Spotify. Розділюваність усього графа співтовариства в цілому зросла і кількість осмислених кластерів вдалося довести з 12 до 18. Причини цього, швидше за все, криються не в зміні поведінки користувачів, а просто у зміні наших джерел даних і механізму збору даних.

Якщо ми збільшимо вибірку користувачів і залишимо на колишньому рівні фільтри на мінімальну кількість відвідувань домену і пари доменів, а також мінімальне еффініті для формування ребра, ми отримаємо більш великий граф. Нижче представлений такий граф з 10121 вершини і 30 кластерів. Як видно, силовий алгоритм малювання з networkx вже не дуже справляється і видає досить плутану картинку. Тим не менш, деякі патерни можна простежити і в такому вигляді. Кількість ребер зменшено з півтора мільйонів до 40000 з допомогою такого ж методу розрідження (local sparsification). PNG-файл займає 80 Мб, тому прохання дивитися в повному розмірі тут.



На візуалізації не вдалося як слід виділити структуру співтовариств (мішанина в центрі), але в дійсності кластера вийшли не менш змістовними, ніж у випадку 1285 доменів.

Зі збільшенням кількості даних спостерігаються цікаві закономірності. З одного боку, починають виділятися маленькі периферійні кластера, які були непомітні на малих даних. З іншого боку, те, що погано кластеризовалось на малих даних, погано кластеризуется і на великих (наприклад, змішуються сайти про нерухомість і про пошук роботи, часто до них примикає езотерика і астрологія).

Ось кілька прикладів нових спільнот. На самому відшибі виділився іспанська кластер, так як ми щось бачимо звідти:



Недалеко від нього, ближче до основного скупчення точок, розташовується азербайджанський кластер (номер 2) і грузинський (номер 4):



З'явився узбецько-таджицький кластер, а також білоруський (номер 16) — всередині основної маси доменів, поруч з «російським новинним» і «українським неновостным» спільнотами:



В наступному пості буде опис алгоритму:

– як були отримані самі кластера, щоб можна було так розфарбовувати граф;
– як віддалялися надлишкові ребра.

Готові відповісти на ваші питання в коментарях. Stay tuned!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.