Метод аномальных кластеров

П4.6.1.2. Аномальные кластеры

Далее будет описан метод оценки числа и местоположения кластеров до применения метода^{-средних.} Можно считать, что метод в какой-то мерс «разведает» структуру данного множества объектов. Он основан на последовательном выявлении и удалении так называемых аномальных групп. Аномальность понимается как удаленность от некой «реперной» точки. Реперная точка выбирается как проявление «нормы», «среднего» или «нормального» объекта, нс обязательно среди множества наблюденных объектов. Например, при анализе оценок студентов по различным предметам, можно выбрать точку, представляющую «нормального студента», с оценками по контрольным работам и экзаменам, которые считаются нормальными в данной среде, а затем уже выделять группы, наиболее отклоняющиеся от выбранной реперной точки в ту или иную сторону. Или же менеджер банка может определить в качестве «нормы» группу клиентов с определенным уровнем образования и дохода, а затем выделять «аномальные», отклоняющиеся от нормы, группы клиентов.

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

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

Аномальная группа конструируется как кластер, наиболее удаленный от реперной точки. Процесс начинается с того, что объект, наиболее удаленный от реперной точки, объявляется центром аномальной группы. Затем версия метода iC-средних с К = 2 применяется к двум центрам: один — это реперная точка, которая не меняется все время процесса вычислений, а второй — это центр аномальной группы, который обновляется согласно стандартной процедуре. Л именно, при заданном аномальном центре, аномальная группа определяется как множество объектов, которые ближе к этому центру, чем реперной точке. При заданной аномальной группе ее центр вычисляется как центр масс с помощью нахождения среднего всех входящих в группу объектов. Процедура повторяется до тех пор, пока не сойдется (рис. 4.18).

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

Первая итерация показана на левой части рисунка, а финальная — на правой Таким образом, метод аномальной группы — это версия метода /С-средних, в которой:

• а) количество кластеров К равно 2;
• б) центром одного из кластеров является 0, перенесенный в реперную точку и не меняющийся в процессе итераций;
• в) начальный центр аномальной группы выбирается как максимально удаленный от точки 0.

Свойство «в» автоматизирует определение начального центра аномального кластера исходя из того, что центр должен быть максимально удаленным от точки отсчета 0.

На самом деле эта идея заложена в самом критерии метода /^-средних [18]: см. формулу (4.13) и комментарий к ней в разделе Ф4.6.1.2.

Рабочий пример 4.6. Аномальная группа прибрежных городов Юго-Западной Англии

Применим метод аномальной группы к данным о прибрежных городах. В качестве реперной точки возьмем среднюю точку, куда и перенесем точку отсчета пространства, 0, а признаки нормируем делением на размах.

Наиболее удаленный от 0 (напомним, туда перенесена точка средних значений!) является объект 35 (St Austell); его расстояние до нуля равно 4,33. Объявляем этот объект центром аномальной группы, которую надо построить. Имеются только три объекта: 26, 29 и 44 (Newton Abbot, Penzance и Truro), которые находятся ближе к центру, чем к нулю. Это дает текущий кластер, состоящий из объектов 26, 29, 35 и 44. Вычислим среднее этих четырех городов и повторим операцию обновления кластера для этого нового центра. Приходим к стабильной группе, состоящей из 8 объектов: 4, 9, 25, 26, 29, 35, 41, 44. Ее центр приведен в табл. 4.15.

Таблица 4.15

Центр аномальной группы в данных о прибрежных городах в реальных и стандартизованных единицах.

Все компоненты стандартизированного центра в табл. 4.16 положительны, причем их большая часть попадает в интервал 0,3—0,5, что близко к максимуму нормализованной шкалы. Это означает, что полученная аномальная группа состоит из городов с высоким уровнем значений показателей — все значения в центре больше, чем средние на всем множестве, на 30—50% размаха значений признаков. Возможно, это связано с тем, что группа включает 8 из 11 городов с населением более 10 000 человек. Остальные три больших города нс попали в группу из-за недостатка в них таких характеристик, как больницы и фермерские рынки. Тот факт, что размах шкалы численности населения в данных на порядки превышает остальные, не сильно влияет на вычисления, потому что они проводятся в нормализованных шкалах, при которых общий вклад признака «численность населения» в разброс данных невелик, около 8,5%.

Рис. 4.19. Первая и вторая итерации построения аномальной группы, визуализированные на плоскости первых главных компонент. Разброс группы вдоль оси ординат отражает то, что эта ось слишком сильно соответствует признаку «наличие фермерского рынка»:

«да» — вверху, «нет» — внизу.

Данный процесс проиллюстрирован на рис. 4.19. Звезды обозначают реперную точку и аномальные центры. Визуально аномальная группа на этом рисунке не очень-то «аномальна», в отличие от аномальной группы на рис. 4.18. А именно, аномальная группа распределена здесь поперек всей плоскости, что противоречит тому, что объекты группы должны быть ближе к ее центру, чем к реперной точке. Причина такой картины — не ошибка в данных, а недостаток визуального отображения. Дело в том, что данная двумерная плоскость хотя и представляет все 12 признаков, но представляет их довольно избирательно. Несмотря па то что эта плоскость и вносит почтенные 76% в разброс данных, дело в оси ординат — она слишком хорошо коррелирует с последним признаком, «Наличие фермерского рынка», что и отражается в разбросе группы по этой оси на те, где есть и те, где нет.

Самостоятельная работа

4.6.2. Удалите полученные восемь «аномальных» городов из выборки и на оставшихся данных (о 37 городах), не меняя стандартизации, опять примените метод аномального паттерна. Какой из оставшихся городов соответствует самой дальней от начала координат точке? Попробуйте отобразить полученный кластер на том же самом графике рис. 4.19, модифицируя представленные выше команды МатЛаб надлежащим образом.