Всем привет! Тема сегодняшней лекции - FOREL.
Это никак не связано с рыбалкой,
это связано с кластерным анализом.
И это очередной метод кластерного анализа,
который расшифровывается, как формальный элемент.
Из названия вы понимаете,
что он был придуман где-то в России,
более того он был придуман где-то в Новосибирске, и еще более того,
он был придуман недалеко от того места,
где мы сейчас записываем лекции.
Был придуман Загоруйко Николаем Григорьевичем,
и его командой, и собственно,
является еще одним методом кластерного анализа.
Но сначала напомним задачу.
Есть у нас есть выборка объектов,
каждый описывается набором признаков,
и мы ввели какую-то меру сходства, они бывают разные,
как мы помним, и хотим выделить,
и надеемся что есть, некоторую структуру внутреннюю.
И мы уже рассмотрели иерархические методы,
рассмотрели и традиционные, k-средних - самый распространенный.
Так вот, сегодня мы будем рассматривать FOREL,
который по своей идее больше напоминает k-средних, чем иерархической метод.
И идея у FOREL довольно интересная и простая.
То есть, мы пытаемся в k-мерном пространстве,
где k - количество признаков,
построить гиперсферы, таким образом,
чтобы охватить наилучшие и наибольшие концентрации объектов.
Берем одну гиперсферу, ищем наибольшую концентрацию,
захватываем потом вторую, и так далее пока не кончатся объекты.
Количество сфер - это будет количество кластеров
и объектов в этих кластерах, которые мы захватили.
Более формально выглядит следующим образом: первое что нам
необходимо сделать - это всегда при FOREL нормировать все точки.
То есть, нормировка это мы приводим все признаки к единой шкале от 0 до 1,
по такой примерно формуле. Зачем это делать?
Потому что нам нужна именно гиперсфера,
а не гипер-непонятно-какая-то фигура.
После этого, мы строим гиперсферу с таким радиусом,
чтобы он охватывал все наши точки, очень большая сфера,
но при этом был минимальный,
в начале нашего радиуса.
После этого мы уменьшаем этот радиус,
допустим умножаем на 0,9,
0,8 то есть берём какую-то долю от него и заново строим гиперсферу.
В результате, теперь у нас уже гиперсфера не включает все точки,
а включает только часть.
В этой сфере мы берем точки и считаем для них центр тяжести,
то есть ищем место наибольшей их концентрации.
И туда перемещаем нашу гиперсферу.
Таким образом, у нас часть точек могла пропасть,
заново считаем центр тяжести,
и так далее перемещаем до тех пор,
пока она перестанет двигаться.
Потом, когда перестало все двигаться,
захваченные точки исключаются, то есть остаются какие-то другие,
и заново начинаем весь процесс.
И так, пока у нас не кончатся, собственно, все точки.
Кроме того, когда мы знаем количество кластеров,
мы можем здесь уже несколько менять алгоритм,
то есть менять радиус при каждой итерации, делать все то же самое,
нормировать построить какой-то большой радиус,
потом его уменьшить, найти первый кластер,
а потом мы можем изменить этот радиус.
Таким образом, можем добиться более высокой скорости сходимости,
или наоборот ее замедлить и можем получить
таким образом необходимое количество кластеров,
потому что в зависимости от радиуса будет различное количество кластеров.
Очевидным плюсом алгоритма бесспорно является то,
что доказана сходимость за конечное количество шагов,
в отличие от k-средних, то есть он всегда сойдется и это очень хорошо.
Кроме того, он позволяет в процессе считать меру качества кластеризации,
в зависимости от количества кластеров,
опять же в отличие от k-средних.
Кроме того, можно модифицировать алгоритм,
то есть менять радиус на итерациях,
что может изменить и сходимость, может привести к нужному количеству кластеров.
Еще одним плюсом может быть то,
что вам можно и не знать начальное количество кластеров,
он сам найдет столько, сколько ему нужно.
Минусы: что опять же чем меньше радиус,
тем больше кластеров, и,
собственно говоря, вы можете получить количество кластеров равное вообще всей выборке.
Так же зависит от начального приближения,
как и k-средних, но, если кидать много раз,
то получится много разных разбиений,
и здесь лучше выбирать то,
когда сумма расстояний от центра до каждого объекта минимальна.
Еще минус такой, что он плохо работает на данных,
не имеющих какой-то четкой структуры, четких кластеров,
или на данных с вытянутыми кластерами.
В следующей лекции мы подробно рассмотрим пример использования FOREL на наших данных,
и о том как выбирать возможно лучшие кластеры,
как плохие, и как он вообще себя ведет.
Ольга Ечевскаядоцент, кандидат социологических наук
Виктор ДёминСпециалист по анализу данных, кандидат технических наук
Наталья ГалановаСпециалист по анализу данных
