В тот момент, когда я узнал, как работает k-means для кластеризации данных в этом замечательном курсе Эндрю Нг, я понял, что с этим алгоритмом может быть что-то не так, если я добавлю какие-то необычные, несбалансированные данные.

В этом алгоритме я заметил две вещи. Во-первых, это уклон в сторону более плотной области. Вы знаете, если у вас есть много точек в одной области, функция среднего (среднего) будет стремиться переместить центр тяжести в эту область. Это имеет смысл, поскольку более плотная область, скорее всего, является скоплением! Во-вторых, кластер, которому принадлежит каждая точка, будет зависеть от ее расстояния между центроидом и точкой, а не от того, насколько близко она находится к своей окрестности (как вы знаете, очень важно различать). Таким образом, эти два свойства в сумме дают плохой эффект, который я продемонстрирую чуть позже.

Поэтому после первоначального размышления я решил создать прототип с помощью Octave, очень мощного инструмента для машинного обучения. Я специально создал набор данных с двумя кластерами, один из которых больше и плотнее, чем другой. Я делаю кластеры достаточно близко друг к другу, так что внешние точки первого кластера будут ближе ко второму центроиду, чем к первому, вот так:

Меньший кластер имеет около 4% от общего количества баллов. Вы заметили точки в правом верхнем углу большого квадрата? Интуитивно вы скажете, что они принадлежат большему, верно? Нет… не так быстро, по крайней мере, с k-means!

После запуска k-средних вот результат, который я получил (как и ожидал):

Что случилось? Почему большая часть большего квадрата принадлежит второму? Разве эти два кластера не разделены четко?

Ну, это первый пункт, который я упомянул. Центроид второго кластера будет иметь тенденцию приближаться к большей области, поскольку эта область более плотная. Чтобы сделать его более интуитивным, думайте о большем как о городской/городской зоне, а о втором как о сельской местности; и вы парень, который живет в верхней правой части города, которая близка к сельской местности. Затем, однажды, правительство решило использовать метод k-средних, чтобы сгруппировать людей в этих районах, чтобы они принадлежали либо к городскому району, либо к сельскому. Итак, после этого вы вдруг понимаете, что вы теперь земляки! Вы соотечественник, потому что живете недалеко от сельской местности, и правительство решило использовать k-средства! (Хотя я не различаю людей, я действительно люблю сельскую местность)

Это очень расстраивает и противоречит здравому смыслу, верно?

И это еще более фрустрирует: второе свойство k-средних. Через некоторое время я решил немного изменить данные: сделать меньший кластер более плотным. Поэтому я добавляю больше очков во второй кластер, от 4% до 10%, 20% и вплоть до 70%. Вот что я получил:

Итак, как вы можете видеть, поскольку я поместил больше точек в меньшую (синюю) область, теперь она стала более плотной, а центр тяжести близок к тому, что должен быть, то есть к центру меньшего квадрата.

Но даже при 70-процентном распределении некоторые точки в большом квадрате по-прежнему принадлежат второму кластеру! Просто потому, что он ближе ко второму центроиду. Итак, вернемся к метафоре «город/сельская местность». Теперь вы понимаете, что независимо от того, насколько сбалансировано количество людей в обоих районах, вы все равно остаетесь соотечественником.

Это очень расстроило.

Вывод

Что здесь происходит? После недолгих поисков я наткнулся на эту исследовательскую работу. И действительно, есть такой эффект k-средних, который я продемонстрировал выше. Это называется равномерным эффектом кластеризации k-средних. Здесь много математических деталей, но подводя итог: k-средние склонны давать кластеры одинакового размера (одинаковые по количеству), даже если входные данные имеют разные истинные кластеры. размер. Они также вводят метод коэффициента варианта, который может обнаруживать единообразный эффект k-средних. Я попробую позже и отпишусь о результате здесь. Но остается вопрос: как мы можем смягчить этот эффект, если заранее знаем, что это на самом деле неправильно? Я не знаю, честно.

P/S: в некоторых случаях равномерный эффект может иметь смысл, поскольку данные, которые у нас есть выше (обучающий набор), могут быть просто частью реальных данных, поэтому в этом случае меньший кластер можно рассматривать как шум.