[ЗАСТАВКА] Кластеризация — это отдельный класс задач машинного обучения, отличающийся от классификации тем, что у объектов обучающей выборки нет заранее заданных ответов учителя. Рассмотрим формальную постановку задачи: имеется пространство объектов, среди которых конечное множество объектов — обучающая выборка, и на этих объектах задана функция расстояния, то есть мы знаем расстояние между этими объектами, и требуется найти метки кластеров этих объектов. То есть так разделить конечное множество объектов на группы или кластеры, чтобы близкие объекты оказались внутри каждой группы, а между объектами разных групп расстояния были достаточно большие. Эту задачу можно решать большим числом способов, она некорректно поставлена, её решение неоднозначно. И нету каких-то общепризнанных правильных критериев качества кластеризации, нету какого-то единого метода и подхода, который всеми бы признавался как единственно правильный, но и сама функция расстояния, как правило, формируется экспертами, и можно сделать это по-разному. И также и количество кластеров тоже мы, как правило, не знаем заранее. Вот в этих условиях, тем не менее, задачу решать хочется, есть много разных целей, ради которых решаются задачи кластеризации. Как правило, это упрощение представления о большом количестве объектов, понимание их внутренней структуры, что они всё-таки состоят из каких-то групп однородных объектов, дальше с этими отдельными выделенными группами уже можно делать какой-то анализ, ну и так далее, то есть решать задачи кластеризации тем не менее нужно, несмотря на принципиальную некорректность постановки этой задачи. Рассмотрим несколько частных случаев. Интуитивно, когда мы говорим «кластеризация», в голове тут же представляем несколько компактных сгустков точек, между которыми есть чёткие разделяющие области. Это далеко не всегда так. Иногда у кластеров можно считать, что мы хотим найти какую-то определенную геометрическую форму, например, выделить шарообразные кластеры. Иногда у этих шарообразных кластеров могут образовываться перемычки между ними, и алгоритмы должны и в этих условиях давать достаточно устойчивые результаты. Должны они также работать и в тех случаях, когда в пространстве объектов разбросаны какие-то отдельные шумовые объекты. Имеются также более сложные задачи, когда кластеры имеют не шарообразную форму, а так называемую ленточную. Они представляют собой значительную трудность для многих алгоритмов кластеризации, основанных на предположении, что расстояние между точками внутри кластера меньше, чем расстояние между точками различных кластеров. Когда у нас ленты, то расстояние внутрикластерные могут быть существенно больше, чем межкластерные, как показано на рисунке. Также отдельную трудность представляют собой кластеры, которые могут быть наложены друг на друга, но при это отличаться друг от друга существенно плотностью точек. И мы с вами, глядя на рисунок, чётко видим здесь два кластера, но для алгоритмов, основанных на попарных близостях точек, эта ситуация будет представлять значительную трудность. Также иногда мы интуитивно под кластером понимаем какие-то сложные геометрические закономерности, которые мы, имея априорные представления о геометрии пространства, чётко различаем и видим, что, например, на третьей картинке здесь два кластера, но для метрических алгоритмов кластеризации эта задача также будет практически нерешаемой. На практике часто возникают и такие ситуации, когда заказчик очень хочет получить кластеризацию и узнать кластерную структуру большого множества объектов, но оказывается, что никакой структуры де-факто, реально не существует. Есть одно большое облако точек, где-то оно может быть погуще, где-то поплотнее, где-то поразреженней, и никакими алгоритмами кластеризации выделить там компактные области не удаётся. Один из самых простых, базовых методов кластеризации — это метод k-средних. Этот метод применим в тех случаях, когда объекты исходно задаются признаковыми описаниями, то есть у нас имеется n вещественных признаков, и поэтому возникает возможность эти векторы признаков складывать, умножать на число, и для любого подмножества объектов искать центр кластера просто путём усреднения векторов-признаков этого кластера. Так называемый центр масс-кластера. И вот на этом приёме основан алгоритм, который итерационно повторяет два шага. На первом шаге каждый объект относится к кластеру ближайшему, то есть выбирается ближайший центр, а на втором шаге уже, зная кластерную принадлежность каждого объекта, мы берём каждый кластер и по всем объектам этого кластера вычисляем среднее как новое положение центра этого кластера. Эти два шага повторяются в итерациях, пока центры не перестанут существенно меняться. В качестве начального приближения инициализации берут либо случайные точки, ну это иногда плохо работает и можно делать и более интересные инициализации, о которых я расскажу чуть ниже. Этот алгоритм плох тем, что он застревает в локальных экстремумах. Конечно, он решает некую оптимизационную задачу, но локальных оптимумов у этого функционала слишком много, и в зависимости от начального приближения мы можем получать не очень хорошее решение. Эту проблему решают многими способами, в частности есть так называемая «мягкая кластеризация», которая позволяет вести итерационный процесс более мягко и не застревать в локальных экстремумах. Отличие заключается вот в чем: что теперь мы будем не жестко относить каждый объект только к одному кластеру, а мы будем оценивать степень близости каждого объекта ко всем центрам кластеров. Получается, что каждый объект размазывается по всем кластерам, но, тем не менее, мы всё равно можем взять тот кластер, оценка близости для которого максимальна, и всё равно и жёстко отнести объект именно к этому кластеру. Но тот факт, что объект вот так вот размазан и принадлежит одновременно всем кластерам в разной степени позволяет точнее, мягче оценивать центры этих кластеров, и они не так сильно... не так сильно и не так резко изменяются, как в предыдущем алгоритме, где центр кластера всегда перескакивает на какую-то определённую величину, и эти шаги дискретны, потому что состав кластеров всегда дискретен. Вот. В данном случае, опять таки, два шага. Первый шаг — это оценивание близости каждого объекта ко всем центрам, а второй шаг — это вычисление новых положений центров. При этом, в отличие от предыдущего алгоритма. где мы по каждому кластеру вычисляли среднее, здесь мы вычисляем среднее по всей выборке, но у каждого кластера есть свои степени принадлежности объектов — giy, и поэтому для каждого кластера y получается своё положение центра. Обращу внимание, что здесь заодно вычисляются также и мощности кластеров. Вот этого момента не было в предыдущем алгоритме. Мы можем усреднить по всем объектам обучающей выборки вот эти степени принадлежности giy и получить величину wy, которая говорит, какую долю во всей выборке занимает данный кластер. И эту величину интересно можно использовать для того, чтобы подправить близость, близость объекта к центру кластера теперь еще и пропорциональна мощности этого кластера, это тоже несколько улучшает качество работы этого алгоритма. Ну и итерации продолжаются до тех пор, пока принадлежности объектов кластерам не перестанут изменяться. В этом алгоритме также, как и в предыдущем, всё равно надо аккуратно подбирать начальное приближение, и сейчас мы этот вопрос тоже рассмотрим. Есть много разных методов выбора начальных приближений. Одна из идей заключается в том, что если мы хотим получить k кластеров, то давайте возьмём k наиболее удалённых друг от друга объектов обучающей выборки. Сделать это можно очень простым алгоритмом, который на слайде представлен в шагах 3 и 4. Мы сначала находим два самых удалённых друг от друга объектов обучающей выборки, а затем начинаем по очереди пристраивать к ним третий объект, четвёртый и так далее так, чтобы каждый новый объект имел максимальное расстояние до ближайшего из уже выбранных объектов. Вот такой вот минимаксный принцип жадного отбора объектов по очереди. Но в этом алгоритме тоже есть один недостаток. Если объекты распределены в пространстве так, что кроме сгустков кластеров есть ещё некий фон, или если могут попадаться объекты, которые очень далеко улетают от всех кластеров и находятся где-то на периферии выборки, они нам будут мешать в этом алгоритме. потому что именно они будут в первую очередь выбираться как вот такие опорные объекты, но тем не менее они не представительны, они не принадлежат никаким кластерам. Чтобы справиться с этой проблемой, мы можем сделать следующий эвристический приём: посчитать среднее расстояние до q ближайших соседей для каждого объекта, и понятно, что такой периферийный объект-выброс будет иметь наибольшее расстояние до своих ближайших соседей. Именно такие объекты надо отбросить. И поэтому мы упорядочиваем всю выборку вот по этим расстояниям ri до q ближайших соседей и отбрасываем шумовые объекты, для которых эти расстояния самые большие. Параметр (какую долю отбросить) Δ, является параметром этого метода точно также, как и сколько ближайших соседей брать (q) тоже параметр, ну и число кластеров k — это тоже параметр, тот самый, который дальше будет использоваться в алгоритме k- средних. Вот с помощью такой инициализации можно вычислить неплохое начальное приближение для k-средних как в жёстком варианте, так и в мягком. Ну, резюмируя, ещё раз повторю, что недостаток этих методов — это чувствительность к выбору начального приближения. Рассказанный способ далеко не единственный, есть много других хороших идей. Например, можно делать мультистарт, выбирать много случайных начальных приближений, из них стартовать алгоритм, а потом выбирать кластеризацию, которая окажется лучшей по какому-то функционалу качества. Можно пользоваться идеей сэмплирования из всей большой выборки выбирать случайное подмножество и его кластеризовать. Сделать так можно много раз и из всех полученных кластеризаций выбрать ту, которая окажется наилучшей в смысле функционала качества заданного, посчитанного по уже теперь полной выборке. Ну и, наконец, есть много способов задавать число кластеров. Можно определять их в ходе итераций, это потребует существенной модификации рассказанных методов, либо можно несколько раз задать число k и выбрать наилучшее, но, опять-таки, для этого нужен некоторый функционал качества кластеризации. Ещё существуют иерархические методы, где число кластеров вообще не определяется, его можно определить после того, как сделана такая иерархическая кластеризация, но об этом в следующей лекции. [ЗАСТАВКА] [ЗАСТАВКА]
