Цікаві алгоритми кластеризації, частина перша: Affinity propagation

Якщо ви запитаєте початківця аналітика даних, які він знає методи класифікації, вам напевно перерахують досить пристойний список: статистика, дерева, SVM, нейронні мережі… Але якщо запитати про методи кластеризації, у відповідь ви швидше за все отримаєте впевнене «k-means ж!» Саме цей золотий молоток розглядають на всіх курсах машинного навчання. Часто справа навіть не доходить до його модифікацій (k-medians) або зв'язно-графових методів.

Не те щоб k-means так вже й поганий, але його результат майже завжди дешевий і сердитий. досконаліші способи кластеризації, але не всі знають, який коли слід застосовувати, і дуже мало хто розуміє, як вони працюють. Я б хотів прочинити завісу таємниці над деякими алгоритмами. Почнемо з Affinity propagation.

image

Передбачається, що ви знайомі з класифікацією методів кластеризації, а також вже застосовували k-means і знаєте його плюси і мінуси. Я постараюся не дуже глибоко вдаватися в теорію, а спробувати донести ідею алгоритму простою мовою.

Affinity propagation
Affinity propagation (AP, він же метод розповсюдження близькості) отримує на вхід матриці схожості між елементами датасета $\textbf{S}=N \times N$ і повертає набір міток, присвоєних цим елементам. Без зайвих слів відразу викладу алгоритм на стіл:

image

Ха, було б що викладати. Всього три рядки, якщо розглядати основний цикл; (4) — явно правило присвоєння міток. Але не все так просто. Більшості програмістів зовсім не очевидно, що ж ці три рядки роблять з матрицями $\textbf{S}$, $\textbf{R}$ і $\textbf{A}$. Околоофициальная стаття пояснює, що $\textbf{R}$ і $\textbf{A}$ — матриці «відповідальності» і «доступності» відповідно, і що в циклі відбувається «обмін повідомленнями» між потенційними лідерами кластерів та іншими точками. Чесно сказати, це досить поверхневе пояснення, і толком незрозуміло ні призначення цих матриць ні як і чому змінюються їхні значення. Спроба розібратися швидше за все приведе вас куди-небудь сюди. Хороша стаття, але непідготовленій людині важко витримати цілий екран монітора, забитий формулами.

Так що я почну з іншого кінця.

Інтуїтивне пояснення
У деякому просторі, у деякій державі живуть точки. Біля точок багатий внутрішній світ, але існує певне правило $s(i, k)$, за яким вони можуть сказати, наскільки схожий на них сусід. Більш того, у них вже є таблиця $\textbf{S}$, де записані всі $s(i, k)$, і вона майже ніколи не змінюється.

Одним жити на світі нудно, тому точки хочуть зібратися в гуртки за інтересами. Гуртки формуються навколо лідера (exemplar), який представляє інтереси всіх членів товариства. Кожна точка хотіла б бачити лідером когось, хто максимально на неї схожий, але готова миритися з іншими кандидатами, якщо ті подобаються багатьом іншим. Слід додати, що точки досить-таки скромні: всі думають, що лідером має бути хто-небудь інший. Можна переформулювати їх низьку самооцінку так: кожна точка вважає, що коли справа доходить до об'єднання в групи, то вона сама на себе не схожа ($s(k, k) < 0$). Переконати точку стати лідером, можуть або колективні підбадьорення з боку схожих на неї товаришів, або, навпаки, якщо в суспільстві не буде зовсім нікого схожого на неї.

Точки заздалегідь не знають, що це будуть за колективи, ні загальна їх кількість. Об'єднання йде зверху вниз: спочатку точки чіпляються за президентів груп, потім тільки розмірковують, хто ще підтримує того ж кандидата. На вибір точки в якості лідера впливають три параметра: схожість (про нього вже сказано), відповідальність та доступність. Відповідальність (responsibility, таблиця $\textbf{R}$ c елементами $r(i, k)$) відповідає за те, наскільки $i$ хоче бачити $k$ своїм ватажком. Відповідальність покладається кожною точкою на кандидата в лідери групи. Доступність (availability, таблиця $\textbf{A}$, c елементами $a(i, k)$) — є відповідь від потенційного ватажка $k$, наскільки добре $k$ готова представляти інтереси $i$. Відповідальність і доступність точки обчислюють у тому числі і самі для себе. Тільки коли велика самоответственность (так, я хочу представляти свої інтереси) і самодоступность (так, я можу представляти свої інтереси), тобто $a(k, k) + r(k, k) > 0$, точка може перебороти вроджену невпевненість у собі. Пересічні точки в кінцевому підсумку приєднуються до лідера, для якого у них найбільша сума $a(i, k) + r(i, k)$. Зазвичай на самому початку, $\textbf{R}=\textbf{0}$ і $\textbf{A}=\textbf{0}$.

Візьмемо простий приклад: точки X, Y, Z, U, V, W, весь внутрішній світ яких — любов до котикам, $K$. У X алергія на кішок, для нього будемо вважати $K=-2$, Y відноситься до неї прохолодно, $K=-1$, а Z просто не до них, $K=0$. У U будинку чотири кішки ($K=4$), у V — п'ять ($K=5$), а у W цілих сорок ($K=40$). Визначимо несхожість як абсолютну величину різниці $K$. X несхожий на Y на один умовний бал, а на U — на цілих шість. Тоді схожість, $s(i, k)$ — це просто мінус несхожість. Виходить, що точки з нульовим схожістю як раз таки однакові; чим більш негативно $s(i, k)$, тим сильніше відрізняються точки. Трохи контринтуитивно, ну да ладно. Розмір «самонепохожести» у прикладі оцінимо в 2 бали ($s(k, k) = -2$).

Отже, на першому кроці кожна точка $i$ покладає відповідальність на всіх $k$ (в тому числі і на себе) пропорційно схожості між $i$ і $k$ і обернено пропорційно схожості між $i$ і самим схожим на нього вектором крім $k$ ((1) c $a(i,j) = 0$). Таким чином
  • Найближча (сама схожа) точка задає розподіл відповідальності для всіх інших точок. Розташування точок далі перших двох поки що впливає тільки на $r(i, k)$ відведену їм і тільки їм.
  • Відповідальність, покладена на найближчу точку також залежить від розташування другий найближчою.
  • Якщо в радіусі досяжності $i$ є кілька більш-менш схожих на нього кандидатів, на тих буде покладено приблизно однакова відповідальність
  • $s(k, k)$ виступає свого роду обмежувачем — якщо якась точка занадто сильно схожа на всі інші, їй нічого не залишається, крім як сподіватися тільки на себе
Якщо $r(i, k) > 0$, $i$ хотіла б, щоб $k$ був її представником. $r(k, k) > 0$ означає, що сама $k$ хоче бути засновником колективу, $r(k, k) < 0$ — що $k$ хоче належати іншому колективу.

Повертаючись до прикладу: X покладає на Y відповідальність у розмірі $inline$-1-(-2)=1$inline$ бал, на Z — $inline$-2-(-1)=-1$inline$ бал, на U — $inline$-6-(-1)=-5$inline$, а на себе $inline$-2-(-1)=-1$inline$. X в загальному-то не проти, щоб лідером групи котоненавистников був Z, якщо Y не захоче бути їм, але навряд чи буде спілкуватися з U і V, навіть якщо вони зберуть велику команду. W настільки несхожа на всі інші точки, що їй нічого не залишається, як покладати відповідальність у розмірі $inline$-2-(-35)=33$inline$ бала тільки на себе.

Потім точки починають думати, наскільки вони самі готові бути лідером (доступні, available, для лідерства). Доступність для самого себе (3) складається з усієї позитивної відповідальності, «голосів», відданих точці. Для $k$ неважливо, скільки точок думають, що вона буде погано їх представляти. Для неї головне, що хоч хтось думає, що вона буде представляти їх добре. Доступність $k$, $i$ залежить від того, наскільки сильно $k$ готовий представляти сам себе і від кількості позитивних відгуків про нього (2) (хтось інший теж вважає, що він буде відмінним представником колективу). Ця величина обмежується зверху нулем, щоб знизити вплив точок, про яких занадто багато думають добре, щоб вони не об'єднали в одну групу ще більше точок і цикл не вийшов з під контролю. Чим менше $r(k, k)$, тим більше голосів потрібно зібрати $k$ на $a(i, k)$ було дорівнює 0 (тобто ця точка була не проти взяти під своє крило ще і $i$).

Починається новий етап виборів, але тепер уже $\textbf{A} \neq \textbf{0}$. Згадаймо, що $a(k, k) \geq 0$, $a(i, k) \leq 0, i \neq k$. Це по-різному впливає на $r(i, k)$

  1. $i = k$. Тоді $a(k, k) \geq 0$ не грає ролі, і в (1) $inline$-max(\dots)$inline$ в правій частині будуть не менші, ніж були на першому кроці. $a(i, j) < 0$ по суті віддаляє точку $i$ і $j$. Самоответственность точки підвищується від того, що у самого кращого кандидата з її точки зору, погані відгуки.
  2. $i \neq k$. Тут виступають обидва ефекту. Цей випадок розщеплюється на два:
    • $a(i, j) + s(i, j), i \neq j$ — max. Те ж саме що і у випадку 1, але підвищується відповідальність покладається на точку $k$
    • $a(i, i) + s(i, i)$ — max. Тоді $inline$-max(\dots)$inline$ буде не більше, ніж на першому кроці, $r(i, k)$ зменшується. Якщо продовжувати аналогію, то це як якщо б точка, яка і так вже замислювалася, не стати її лідером, отримала додаткове схвалення.
Доступність залишає у змаганні точки які чи готові самі постояти за себе (W, $a(i, i) = 0$, але це ніяк не впливає на (1), т. к. навіть з урахуванням поправки W знаходиться дуже далеко від решти точок) або ті, за яких готові постояти інші (Y, (3) у неї за доданку від X і Z). X і Z, які не строго краще всього схожі на когось, але при цьому на когось таки схожі, вибувають із змагання. Це впливає на розподіл відповідальності, що впливає на розподіл доступності і так далі. Зрештою, алгоритм зупиняється — $a(i, k)$ перестають змінюватися. X, Y і Z об'єднуються в компанію навколо Y; дружать U і V c U у якості лідера; W добре і з 40 кішками.

Перепишемо вирішальне правило, щоб отримати ще один погляд на вирішальне правило алгоритму. Скористаємося (1) і (3). Позначимо $\tilde s(i, k) = a(i, k) + s(i, k)$ — схожість з поправкою на те, що $k$ говорить про своїх командирських здібностях $i$; $\tilde d(i, k) = - \tilde s(i, k)$ — несхожість $i$ -$k$ з поправкою.

image

Приблизно те, що я сформулював спочатку. Звідси видно, що чим менше впевнені в собі точки, тим більше «голосів» необхідно зібрати або тим більше несхожою на решту треба бути, щоб стати лідером. Тобто чим менше $s(k, k)$, тим крупніше виходять групи.

Що ж, я сподіваюся, ви придбали певний інтуїтивне уявлення того, як працює метод. Тепер трохи серйозніше. Давайте поговоримо про нюанси застосування алгоритму.

Дуже-дуже короткий екскурс в теорію
Кластеризацію можна представити у вигляді задачі дискретної максимізації з обмеженнями. Нехай на множині елементів задана функція подібності $s(i, j)$. Наша задача знайти такий вектор міток $\mathbf{c} = \{c_1, c_2 ... c_N\}, c_i \in \{1 \dots N\}$, який максимізує функцію
$S© = \sum^N_{i=1}{s(i, c_i)} + \sum^N_{k=1}{\delta(c_k)}$
де $\delta(c_k)$ — член обмежувач, рівний $inline$-\infty$inline$, якщо існує точка $i$, яка вибрала точку $k$ своїм лідером ($c_i = k$), але сама $k$ лідером себе не вважає ($c_k \neq k$). Погана новина: знаходження ідеального $\mathbf{c}$ — це NP-складна задача, відома як задача про розміщення об'єктів. Тим не менш, для її рішення існує кілька наближених алгоритмів. У нас цікавлять методи $s_i$, $c_i$ і $\delta_i$ представляються вершинами двудольного графа, після чого між ними відбувається обмін інформацією, дозволяє з імовірнісної точки зору оцінити, яка мітка краще підійде для кожного елемента. См. висновок тут. Про поширення повідомлень у дводольних графах див. здесь. Взагалі поширення близькості — це приватний випадок (швидше, звуження) циклічного поширення переконань (loopy belief propagation, LBP, див. тут), але замість суми ймовірностей (підтип Sum-Product) в деяких місцях ми беремо тільки максимальну (підтип Max-Product) з них. По-перше, LBP-Sum-Product на порядок складніше, по-друге, там легше зіткнутися з обчислювальними проблемами, по-третє теоретики стверджують, що для задачі кластеризації це має більший сенс.

Автори AP при багато говорять про «повідомлення» від одного елемента графа до іншого. Така аналогія відбувається виведення формул через поширення інформації в графі. На мій погляд вона трохи плутає, адже в реалізаціях алгоритму ніяких повідомлень «точка-точка» немає, зате є три матриці $\textbf{S}$, $\textbf{R}$ і $\textbf{A}$. Я б запропонував таке трактування:
  1. При обчисленні $r(i, k)$ йде пересилання повідомлень від точок даних $i$ потенційним лідерам $k$ — ми переглядаємо матриці $\textbf{S}$ і $\textbf{A}$ вздовж рядків
  2. При обчисленні $a(i, k)$ йде пересилання повідомлень від потенційних лідерів $k$ до всіх інших точок $i$ — ми переглядаємо матриці $\textbf{S}$ і $\textbf{R}$ вздовж стовпців
Affinity propagation детермінований. Він має складність $O(N^2T)$, де $N$ — розмір набору даних, а $T$ — кількість ітерацій, і займає $O(N^2)$ пам'яті. Існують модифікації алгоритму для розріджених даних, але все одно AP сильно грустнеет із збільшенням розміру датасета. Це досить серйозний недолік. Зате поширення близькості не залежить від розмірності елементів даних. Поки що не існує распараллеленного варіанти AP. Тривіальне ж розпаралелювання у вигляді безлічі запусків алгоритму не підходить в силу детермінованості. офіційному FAQ, написано, що варіантів з додаванням даних в реальному часі теж немає, але я знайшов ось таку статтю.

Існує прискорений варіант AP. Запропонований у статті метод ґрунтується на ідеї, що необов'язково обчислювати взагалі всі оновлення матриць доступності та відповідальності, адже всі точки в гущавині інших точок відносяться до далеких від них екземплярів приблизно однаково.

Якщо вам хочеться експериментів (так тримати!), я б запропонував поворожити над формулами (1-5). Частини $\max{(0, x)}$ в них виглядають підозріло схоже на нейронно-сіткові ReLu. Цікаво, що вийде якщо використовувати ELu. Крім того, раз ви тепер розумієте суть того, що відбувається в циклі, ви можете додати до формули додаткові члени, відповідальні за необхідне вам поведінку. Таким чином можна «підштовхнути» алгоритм у бік кластерів певного розміру або форми. Також можна накласти додаткові обмеження, якщо відомо, що якісь елементи з більшою ймовірністю належать одній множині. Втім, це вже спекуляції.

Обов'язкові оптимізації і настройки
Affinity propagation, як багато інших алгоритмів, можна перервати достроково, якщо $\textbf{R}$ і $\textbf{A}$ перестають оновлюватися. Для цього майже у всіх реалізаціях використовується два значення: максимальна кількість ітерацій і період, з яким перевіряється величина оновлень.

Affinity propagation схильний обчислювальним осцилляциям у випадках, коли є кілька хороших розбиття на кластери. Щоб уникнути проблем, по-перше, на самому початку до матриці подібності додається трохи шуму (дуже-дуже небагато, щоб не вплинути на детерменированность, в sklearn-імплементації порядку $10^{-16}$), а по-друге, при оновленні $\textbf{R}$ і $\textbf{A}$ використовується не просте присвоювання, а присвоювання экпоненциальным згладжуванням. Друга оптимізація притому в цілому добре впливає на якість результату, але з-за неї збільшується кількість необхідних ітерацій $T$. Автори радять використовувати параметр згладжування $0.5 \leq \gamma < 1.0$ зі значенням за замовчуванням $0.5$. Якщо алгоритм не сходиться або сходиться частково, слід збільшити $\gamma$ і $0.9$ або $0.95$, з відповідним збільшенням кількості ітерацій.

Ось так виглядає відмова — купа дрібних кластерів, оточена кільцем кластерів середнього розміру:
image

Як вже було сказано, замість наперед заданої кількості кластерів використовується параметр «самоподібність» $s(k, k)$; чим менше $s(k, k)$, тим більші кластери. Існують евристики для автоматичного підстроювання значення цього параметра: використовуйте медіану за всіма $s(i, k)$ бльшего числа кластерів; 25 перцентиль або навіть мінімум $s(i, k)$ — для меншого (все одно доведеться підганяти, ха-ха). При дуже маленькому або занадто великому значенні «самоподібність» алгоритм і зовсім не видасть якихось корисних результатів.

В якості $s(i, k)$ само собою напрошується використовувати негативне евклідова відстань між $i$ і $j$, але вас ніхто не обмежує у виборі. Навіть у разі датасета з векторів дійсних чисел можна перепробувати багато цікавого. Взагалі ж, автори стверджують, що на функцію подібності не накладено жодних особливих обмежень; навіть не обов'язково, щоб виконувалося правило симетрії або правило трикутника. Але варто зауважити, що чим більше хитромудра у вас $s(i, j)$, тим менше ймовірність, що алгоритм зійдеться до чогось цікавого.

Розміри кластерів, отриманих в ході поширення близькості, варіюються в досить невеликих межах, і якщо в датасете є дуже різні за розміром скупчення, AP може пропустити маленькі, або порахувати великі за кілька. Зазвичай друга ситуація менш неприємна — вона виправлена. Тому часто AP потребує постобробці — додаткової кластеризації лідерів груп. Підходить будь-який інший метод, тут може допомогти додаткова інформація про задачу. Слід пам'ятати, що чесним самотньо стоїть точок виділяється свої кластери; такі викиди потрібно фільтрувати перед постобробки.

Експерименти
Фух, закінчилася стіна тексту, почалася стіна картинок. Перевіримо Affinity propagation на різного виду кластерах.
Стіна картинокПоширення близькості непогано працює на кластерах у вигляді складок розмірності менше розмірності даних. AP зазвичай не виділяє всю складку, а розбиває її на дрібні шматки-субкластеры, які потім доведеться склеювати воєдино. Втім, це не так уже й складно: з двадцятьма точками це простіше, ніж з двадцятьма тисячами, плюс у нас є додаткова інформація про витягнутості кластерів. Це набагато краще, ніж k-means та багато інших неспеціалізовані алгоритми.

image
image
image
image

Якщо складка перетинає інший згусток, справа йде гірше, але навіть так AP допомагає зрозуміти, що в цьому місці відбувається щось цікаве.

image
image

При хорошому підборі параметра і кластеризатора-постобработчика AP виграє і в разі кластерів різного розміру. Зверніть увагу на картинку з $s(i, i)=-8$ — майже ідеальне розділення, якщо об'єднати кластери зверху-праворуч.

image
image

З кластерами однакової форми, але різної щільності у AP і k-means плюс-мінус паритет. В одному випадку потрібно добре вгадати $s(i, i)$, а в іншому — $k$.

image
image

Зі згустком більшої щільності в іншому згустку, на мій погляд, трохи виграє k-means. Він, звичайно, «від'їдає» значний шматок на користь кластера більшої щільності, але по візуальному результату роботи AP взагалі не дуже видно неоднорідність.

image
image

Ще трохи картинок:

image
image
image
image


Підсумок
Використовуйте Affinity propagation, коли
  • У вас не дуже великий ($N < 10^5 - 10^6$) або в міру великий, але розріджений ($N < 10^6 - 10^7$) датасет
  • Заздалегідь відома функція близькості
  • Ви очікуєте побачити безліч кластерів різної форми і трохи варьирующимся кількістю елементів
  • Ви готові повозитися з постобробкою
  • Складність елементів датасета значення не має
  • Властивості функції близькості значення не мають
  • Кількість кластерів значення не має
Затверджується, що різні вчені успішно застосовували Affinity propagation для
  • Сегментації зображень
  • Виділення груп у геномі
  • Розбиття міст на групи по доступності
  • Кластеризації зразків граніту
  • Групування фільмів на Netflix
У всіх цих випадках був отриманий результат краще, ніж за допомогою k-means. Не те щоб це якийсь суперський результат саме по собі. Мені невідомо, чи проводилося у всіх цих випадках порівняння з іншими алгоритмами. Я планую зробити це в наступних статтях. По всій видимості, на датасетах з реального життя найбільше допомагає вміння поширення близькості обходитися з кластерами різної геометричної форми.

Що ж, начебто і все. Наступного разу розглянемо ще який-небудь алгоритм і порівняємо його з методом поширення близькості. Удачі, Хабр!
Джерело: Хабрахабр

0 коментарів

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