Любой, кто играл в покемонов, заметил, что есть определенные образы, в которые попадают покемоны: Пикачу, Плюсл, Пачирису и Деденне — милые покемоны электрического типа; есть множество покемонов «больших монстров», таких как Райдон, Нидокинг, Тиранитар и Аггрон; и многие другие классы, которые можно было бы заметить. Как специалисты по данным, мы спрашиваем себя: можем ли мы идентифицировать эти группы, используя данные? Какие еще группы мы можем найти?
Алгоритмический процесс поиска неизвестных группировок — или кластеров — в данных называется кластеризацией. Кластеризация, как правило, не контролируется, то есть мы заранее не знаем, какими должны быть кластеры, хотя у нас может быть мнение о том, как они должны выглядеть. Контролируемая версия кластеризации, в которой у нас есть метки кластеров, которые мы хотим предсказать, называется классификацией, и она станет предметом будущей статьи о PokeML.
Однако мы можем полагать, что в данных есть четко определенные кластеры, что это могут быть наблюдения проблемы классификации, в которой просто отсутствуют метки. Существование функции классификации позволяет нам математически рассуждать о том, как должны выглядеть наши данные. В частности, если функция классификации непрерывна, что похожие покемоны относятся к одному и тому же классу, то факт из топологии говорит нам о том, что данные должны быть несвязаны — должны быть кластеры!
Непрерывность и несвязность в своей основе являются топологическими утверждениями, поэтому мы должны убедиться, что наше кодирование данных совместимо с внутренней топологией проблемы. Вот почему мы приложили большие усилия, чтобы закодировать аспекты покемонов как битовые векторы и использовали причудливые методы для создания альтернативных кодировок движений и способностей покемонов. Теперь, когда они у нас есть, мы можем выполнить кластеризацию.
Самый простой алгоритм кластеризации известен как k-Means и работает, когда данные лежат в векторном пространстве. Сначала мы выбираем количество кластеров, которые хотим найти — недостаток этого типа алгоритма — а затем алгоритм k-средних повторяет следующие два шага, сначала случайным образом выбирая k точек (центроидов) в пространстве, каждая из которых представляет один кластер. .
Самый простой алгоритм кластеризации известен как k-Means и работает, когда данные лежат в векторном пространстве. Сначала мы выбираем количество кластеров, которые хотим найти — недостаток этого типа алгоритма — а затем алгоритм k-средних повторяет следующие два шага, сначала случайным образом выбирая k точек (центроидов) в пространстве, каждая из которых представляет один кластер. .
- Назначьте каждую точку данных ближайшему центроиду
- Пересчитайте центроид как среднее значение назначенных ему точек данных.
После того, как этот процесс стабилизируется, у нас есть кластерные назначения. Несмотря на простоту, этот процесс имеет несколько недостатков. k-Means имеет тенденцию искать круговые (или действительно «вороные») кластеры, которые не являются единственным способом реализации кластеров, также как рандомизированный и итеративный алгоритм, он чувствителен к инициализации и может стабилизироваться в локальном минимуме. . Наконец, хотя наша исходная матрица покемонов живет в векторном пространстве, поскольку покемоны буквально представлены в виде векторов, не очевидно, как мы должны включать информацию о тематической модели. Для дальнейшего мы заменим бит-векторы способностей и ходов средним значением тематических распределений для способностей и ходов (отдельно), соответствующих покемонам. Кроме того, мы стандартизируем столбцы матрицы покемонов, чтобы они имели единичную дисперсию, и назначим их 30 кластерам.
Делая это на исходной матрице покемонов, мы получаем несколько небольших кластеров с ‹20 участниками, несколько с 20–60 участниками и один с более чем 100 участниками! В тематической модели оказывается, что кластеры более поляризованы, причем размеры кластеров в основном составляют ‹20 или ›60. Однако настоящая проверка выполняется вручную, когда мы смотрим на сами кластеры и смотрим, есть ли смысл. Для краткости рассмотрим случайный выбор кластеров.
Original Pokemon Matrix clusters #4 (4): Baltoy, Claydol, Bronzor, Shuckle #11 (83): Marshtomp, Poliwhirl, Drizzile, Kingdra, Quagsire ... #14 (5): Morelull, Shiinotic, Foongus, Vileplume, Amoonguss #17 (70): Azelf, Lunatone, Uxie, Calyrex, Solrock ... #26 (2): Zekrom, Kyurem-Black #28 (62): Shelgon, Bagon, Vibrava, Salamence, Flygon ... Topic Model Pokemon Matrix clusters #0 (9): Conkeldurr, Darmanitan-G, Kangaskhan, Darmanitan, Rhydon ... #4 (13): Rhyhorn, Swinub, Shelmet, Spheal, Seedot ... #7 (1): Heatmor #12 (62): Moltres, Flygon, Arcanine, Dracozolt, Arctozolt ... #26 (73): Tangela, Bellossom, Grookey, Lilligant, Thwackey ... #29 (2): Urshifu, Urshifu-Rapid Strike
Я бы сказал, что эти кластеры достойные. Некоторые небольшие кластеры действительно выбирают довольно уникальных покемонов — Хитмор, Уршифус, Зекром и Кюрем — и у более крупных кластеров есть какая-то рифма и причина. Однако есть некоторые сомнительные результаты, например, действительно ли Bronzor принадлежит к кластеру с Shuckle и Claydol, но без Bronzong, или что должен означать кластер № 4 из данных тематической модели.
Одним из преимуществ k-Means как простого, так и рандомизированного алгоритма является то, что мы можем использовать его результаты для описания самих покемонов. Можно подумать, что покемоны, приписанные к небольшому кластеру, более «уникальные»; запустив k-Means несколько раз и отслеживая размер кластера, которому назначен покемон, мы можем измерить это качество. Поскольку размер кластера имеет тенденцию сильно различаться, рассмотрение среднего значения не слишком информативно. Вместо этого мы рассматриваем 75-й процентиль размера кластера покемонов, что позволяет нам оценить как размер, так и дисперсию кластеров.
Original matrix: Most "unique": Wobuffet, Zygarde 10%, Cosmog, Cosmoem, Zacian-Crowned Least "unique": Toxel, Mawile, Dunsparce, Dreepy, Dubwool Topic model matrix: Most "unique": Necrozma Dawn Wings, Cosmog, Cosmoem, Rotom-Heat, Rotom-Wash Least "unique": Seadra, Wartortle, Drakloak, Popplio, Mudkip
Они также кажутся разумными: Cosmog и Cosmoem, безусловно, являются уникальными покемонами, а более типичные покемоны, идентифицированные матрицей тематической модели, как правило, являются не полностью развитыми типами воды, которые являются наиболее распространенным типом. Более типичные покемоны из оригинальной матрицы несколько удивляют — если не считать Dubwool, эти покемоны не кажутся особо стандартными.
Это приводит к другой проблеме с кластеризацией k-Means и широким набором алгоритмов кластеризации: каждый элемент назначается кластеру, даже если он не обязательно принадлежит ему. Точка данных, которая хорошо изолирована от кластера, все еще может быть назначена этому кластеру — например, в k-Means, если эта точка не слишком сильно влияет на центроид (из-за расстояния или из-за других выбросов), она будет назначена до ближайшего кластера. По этой причине рассмотрение «случайных» членов кластера может ввести в заблуждение; вместо этого члены, ближайшие к центроиду (или самому центроиду!), являются более репрезентативными.
Существуют различные способы смягчения проблемы неправильно назначенного членства в кластере, и мы обсудим два из них в оставшейся части этой статьи. Первый — это агломеративная кластеризация, при которой кластеры формируются путем последовательного (агломеративного) группирования элементов в порядке увеличения расстояния, останавливающегося при выполнении желаемого критерия. Поскольку нас беспокоят покемоны, которые далеко не все истинные кластеры, мы можем надеяться, что в какой-то момент ближе к концу процесса расстояние между двумя объединенными кластерами начнет резко увеличиваться, указывая на то, что мы объединяем объекты, которые не принадлежат друг другу. .
Собственно, именно это мы и видим. Мы также можем использовать хитрый прием для определения изгиба: повернув график так, чтобы первая и последняя точки данных были выровнены по горизонтали, изгиб будет находиться вокруг самой низкой точки повернутого графика. Остановив нашу кластеризацию в этой точке, в данном случае с 31 кластером, мы можем надеяться, что кластеры достаточно хорошо сформированы. Давайте взглянем!
Original Pokemon Matrix clusters #5 (88): Piloswine, Boldore, Sealeo, Armaldo, Swinub ... #9 (9): Clefairy, Igglybuff, Wigglytuff, Cleffa, Clefable ... #13 (2): Zygarde, Zygarde-Complete #14 (46): Gloom, Petilil, Budew, Treecko, Grovyle ... #17 (2): Xerneas, Yveltal #19 (29): Ponyta, Darumaka, Growlithe, Arcanine, Rapidash ... #20 (1): Comfey #21 (2): Toxtricity, Toxtricity-Low Key
Здесь мы видим несколько довольно хорошо сформированных кластеров — легендарки X&Y Box сгруппированы вместе (№ 17), как и трио Clefairy/Jigglypuff/Chansey (№ 9). Одноразовые также имеют смысл: Comfey, Toxtricity и Zygarde достаточно уникальны.
Еще одно преимущество агломеративной кластеризации — и многих других методов, отличных от k-средних, — заключается в том, что они требуют, чтобы наши точки данных находились только в метрическом, а не векторном пространстве. Короче говоря, это означает, что нам нужно знать только расстояние между любыми двумя нашими точками, а не то, где в пространстве расположена каждая точка. Это чрезвычайно полезно для нашей матрицы тематической модели, учитывая, как сильно мы старались выше закодировать различные распределения тем таким образом, чтобы это имело смысл для k-средних; мы просто усреднили распределения, что уничтожило много информации. Используя этот метод для агломеративной кластеризации, мы получаем один кластер с 306 членами, почти половиной покемонов! Если мы хотим улучшить кластеризацию, нам придется изменить нашу кодировку.
Вместо этого мы можем вычислить расстояние между наборами движений и способностями покемонов, сопоставив тематические распределения движений и способностей между двумя покемонами. Частично это просто: движения и способности, которые используются двумя покемонами, не увеличивают расстояние. Однако, например, как нам измерить расстояние между Мэджикарпом и Фибасом?
Magikarp Abilities: Swift Swim, Rattled Moves: Bounce, Flail, Hydro Pump, Splash, Tackle Feebas Abilities: Swift Swim, Oblivious, Adaptability Moves: Dive, Dragon Pulse, Flail, Splash, Tackle, (and 32 others)
Как человек, имеющий опыт работы с покемонами, я, возможно, захочу совместить Bounce с Dive (поскольку оба являются физическими атаками за два хода) и Hydro Pump с Dragon Pulse (поскольку оба являются специальными атаками с одной целью), но я не хочу иметь сделать это своими руками. Мне также нужно быть осторожным — возможно, лучше сочетать Hydro Pump с Dive (атаки водного типа по одной цели) — и убедиться, что я каждый раз нахожу оптимальное сочетание. Проблема в том, что существует 34⋅33⋅32≈36 000 способов соединить три непревзойденных хода Мэджикарпа с тремя из 34 непревзойденных ходов Фибаса, что вычислительно невозможно. Для двух покемонов с самыми непересекающимися Movesets — Charizard и Calyrex-Ice, изучающих 60 и 79 Moves, другой соответственно — количество пар составляет 100 цифр!
У нас есть случай задачи о назначении линейной суммы: какое сопоставление дает наименьшее общее расстояние? К счастью, у него есть относительно быстрое решение, венгерский алгоритм, который снижает вычислительные затраты на это вычисление с наивного O(n!) до более управляемого O(n²). Вычисление этих расстояний для всех 734 покемонов было по-прежнему сложным, поскольку моя неоптимизированная реализация на Python заняла чуть больше часа.
Однако замена векторного кодирования матрицей попарных расстояний требует дополнительных затрат. В предыдущей агломеративной кластеризации метрикой расстояния, которую мы использовали, была кластерная дисперсия: на каждом шаге объединялась пара кластеров с минимальной совокупной общей дисперсией. Это особый тип метрики по двум причинам: во-первых, она часто работает довольно хорошо, а во-вторых, ее можно вычислить с помощью метода Уорда и, следовательно, довольно быстро. Вместо этого sklearn предоставляет три других показателя или связи; оказывается, что для нашего набора данных полная связь работает лучше всего — одиночный и средний оба создают единый кластер, содержащий более 700 покемонов, что не особенно полезно.
Topic Model Pokemon Matrix Clusters (34) #0 (179): Marshtomp, Mudkip, Corsola-Galar, Meowth-Galar ... #3 (106): Tangela, Grookey, Bellossom, Lilligant, Vileplume ... #5 (25): Smoochum, Mime Jr, Cutiefly, Pichu, Igglybuff ... #10 (2): Celesteela, Stakataka #11 (3): Solgaleo, Lunala, Necrozma #22 (1): Bunnelby #24 (1): Zeraora #31 (1): Mew
Похоже, это тоже сработало очень хорошо! Конечно, распределение размеров кластеров более концентрированное, чем в исходной матрице, с двумя кластерами, содержащими более трети покемонов, но в целом кластеры имеют смысл. Легендарные Alolan Legendary сгруппированы вместе в № 11, а Baby Pokemon, похоже, сгруппированы в № 5. С другой стороны, Баннелби не особенно чувствует себя принадлежащим к кластеру сам по себе.
Спектральная кластеризация — это еще один алгоритм кластеризации, который мы можем использовать и который работает непосредственно с парной матрицей расстояний. Слово «спектральный» в названии происходит от слова «спектр» в линейной алгебре, еще одного слова, обозначающего распределение собственных значений матрицы; значений λ, для которых существует ненулевой вектор v (собственный вектор), удовлетворяющий условию Mv=λv.
Представьте, если бы у нас была идеальная матрица смежности для наших кластеризованных данных: матрица n × n, в которой запись содержит 1, если элементы, соответствующие строке и столбцу для этой записи, находятся в одном кластере, и 0 в противном случае. Мы можем сразу определить некоторые собственные векторы и собственные значения для этой системы: характеристический вектор кластера с единицами в строках, элементы которых принадлежат кластеру, и нулями в других местах, является собственным вектором, собственное значение которого равно количеству элементов в кластере.
Более того, если бы мы вычли из каждой записи на диагонали этой матрицы размер соответствующего кластера, также называемого степенью, каждый из этих характеристических векторов имел бы собственное значение, равное нулю. И наоборот, если мы посмотрим на собственные векторы, соответствующие нулевому собственному значению, они должны выглядеть как характеристические векторы! Это свойство настолько полезно, что эта специальная матрица получила название — лапласиан.
Конечно, у нас нет идеальной матрицы смежности. Но мы могли бы надеяться, что если мы построим матрицу так, что элемент будет близок к 1, когда соответствующие элементы расположены близко, и близок к 0, когда соответствующие элементы расположены далеко, мы сможем получить что-то, что работает достаточно хорошо. Оказывается, это так!
Мы часто вычисляем эту матрицу смежности, применяя ядро поэлементно к матрице попарных расстояний, которая удовлетворяет k (0) = 1 и k (∞) = 0; k(x)=exp(-γ x²) — популярный выбор, а γ›0 — параметр настройки. Кроме того, разница между нашей построенной матрицей смежности и «истинной» матрицей смежности означает, что интерпретация собственных векторов как характеристических векторов может быть запутанной. Поскольку собственные векторы должны на самом деле выглядеть как характеристические векторы, мы можем искусственно создавать компоненты для каждой точки данных из ее записи в каждом характеристическом векторе и просто использовать k-средние для этого представления, чтобы назначить каждую точку данных кластеру.
Поскольку каждый кластер вносит свой вклад в ядро лапласиана, мы можем изучить распределение собственных значений, чтобы определить количество кластеров. Как обычно, мы ищем острый обрыв, однако, даже если мы его не найдем, мы все равно можем взять наименьшие собственные векторы, чтобы увидеть, что мы получим. Мы также можем настроить форму кривой собственного значения, изменив значение γ, которое определяет мягкую границу того, насколько далеко могут быть два объекта, которые все еще считаются «близкими». Взятие средней суммы строк матрицы смежности также может дать хорошее представление о правильности выбора γ; половина от среднего ожидаемого размера кластера является хорошим эмпирическим правилом.
Однако оказывается, что как исходная матрица покемонов, так и матрица тематической модели дают ужасные спектры, на самом деле без разумного обрыва для любого значения γ и с результатами кластеризации, которые просто помещают все, кроме горстки Покемонов в единый кластер. Чтобы спасти это, мы можем изменить используемую функцию ядра; в то время как ядро Гаусса из предыдущего популярно, ядро k-ближайших соседей также широко используется. Для этого ядра запись равна 1, если каждая соответствующая точка данных находится среди k ближайших точек данных к другой, и нулю в противном случае. Принимая k равным 40, мы получаем разумные размеры кластера. Но как членство?
Original Pokemon Matrix clusters #0 (29): Anorith, Walrein, Kabuto, Mamoswine, Kabutops ... #8 (5): Lilligant, Steenee, Bounsweet, Cutiefly, Slurpuff #12 (7): Mienfoo, Mienshao, Tyrogue, Riolu, Hitmontop ... #19 (2): Ditto, Stunfisk #20 (13): Qwilfish, Corsola, Skrelp, Tentacool, Tentacruel ... #27 (6): Aggron, Dragonite, Krookodile, Nidoqueen, Charizard ... #29 (16): Pawniard, Meowth-Galar, Bisharp, Impidimp, Nuzleaf ... #33 (10): Meltan, Magnezone, Registeel, Magneton, Steelix ... Topic Model Pokemon Matrix clusters #4 (4): Thwackey, Impidimp, Fraxure, Amaura #10 (5): Beldum, Karrablast, Rolycoly, Sinistea, Drampa #12 (13): Sneasel, Azumarill, Lickitung, Weavile, Beartic ... #20 (55): Shelgon, Bagon, Drizzile, Larvesta, Gloom ... #25 (6): Mr. Mime-Galar, Grubbin, Mr. Rime, Hippopotas ... #26 (13): Mesprit, Kirlia, Gardevoir, Togetic, Togekiss ... #35 (1): Kubfu #39 (8): Sealeo, Walrein, Spheal, Poliwhirl, Gible ...
Кластеры исходной матрицы кажутся довольно приличными; № 27, в частности, возможно, впечатляет тем, что объединяет вместе некоторых приличных «монстров» покемонов, а другие кластеры обычно представляют собой кластеры на основе типов. Тем не менее, кластеры тематических моделей здесь довольно плохи, поскольку большинство из них не идентифицируют какие-либо заметные закономерности среди своих членов.
Это важный урок для изучения кластеризации и неконтролируемых методов в целом. В этой статье мы, как специалисты по данным, сделали множество активных выборов в том, как мы рассматриваем наши данные; от кодирования наших данных до используемой метрики расстояния, до алгоритма кластеризации и параметров, используемых для алгоритма. Таким образом, получаемые нами результаты не зависят исключительно от данных. Да, информация о данных, но мы должны помнить о своих пальцах на весах.
Люди часто представляют алгоритмические результаты как «беспристрастные» и ставят их на пьедестал выше более тщательных описаний. Одной из областей с особенно высокими ставками, где это происходит, является процесс перераспределения округов в Соединенных Штатах. В среде, где недемократические махинации остаются без внимания, слепые алгоритмические подходы часто пропагандируются как жизнеспособное решение. Однако как специалисты по данным мы должны признать, что построение алгоритма обязательно включает в себя принятие решений, которые могут привести к нежелательным результатам, точно так же, как наша спектральная кластеризация матрицы тематической модели. Более того, поскольку эти результаты возникают благодаря алгоритму, может быть трудно объяснить, что пошло не так.
Существует множество других алгоритмов кластеризации, каждый из которых имеет свои преимущества и недостатки. Методы на основе плотности, такие как DBSCAN, явно помечают некоторые точки данных как изолированные/шумовые, если их ближайший сосед находится слишком далеко, что может помочь избежать проблемы универсального членства k-средних. Также могут использоваться альтернативные метрики и ядра, особенно минимаксное расстояние пути, которое помогает идентифицировать невыпуклые и/или некомпактные кластеры в данных. Однако, как всегда, лучше сначала попробовать более простые и дешевые методы на наборе данных, а затем приспосабливаться к более сложным методам по мере понимания проблемы.
Мы начали эту статью с обсуждения кластеризации как решения неизвестной проблемы классификации. В следующей статье мы перейдем к следующему шагу: как мы делаем классификацию? Наконец-то мы воспользуемся некоторыми данными о покемонах из «реального мира» и попытаемся сделать некоторые прогнозы — надеюсь увидеть вас там!
