Ф4.6.1.2. Аномальные группы

Прежде чем описать математическую модель аномальной группы, дадим формулировку алгоритма выделения аномальной группы.

Алгоритм выделения аномальной группы

  • 1. Предобработка. Определим реперную точку а = и ..., av) (если нет явных предположений о «норме», то в качестве а возьмем общее среднее) и стандартизуем таблицу данных сдвигом начала координат в точку а = (av ..., av). Иными словами, из всех значений каждого признака v вычтем величину av(p = 1, 2,..., V).
  • 2. Инициализация аномального центра. Найдем объект, максимально удаленный от начала координат, 0, и поместим туда начальный аномальный центр, с.
  • 3. Обновление аномальной группы. Определим аномальную группу 5 вокруг с правилом: объект yi относится к кластеру 5, если d(yr с) < d(yv 0).
  • 4. Обновление аномального центра. Вычислим внутригрупповое среднее с' для множества объектов S и проверим, отличается ли оно от предыдущего центра с. Если с' и с не равны друг другу, обновляем центр присвоением с <= d и переходим к шагу 3. В противном случае переходим к шагу 5.
  • 5. Выдача результатов. Список группы S и центр с выдаются как результат работы алгоритма.

Нетрудно доказать, что метод аномальной группы, как и метод /С-средних, альтернативно минимизирует некий критерий — своеобразную версию критерия метода К-средних W(S, с), см. выражение (4.9):

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

Можно показать, что критерий (4.10) — не что иное, как критерий наименьших квадратов для модели

где i — номер объекта; v — номер признака; S — множество объектов искомой аномальной группы, тогда как с = (q,..., cv, — ее центр. Эта модель имеет очень простую структуру: объект либо принадлежит аномальной группе, либо нет, причем в первом случае он должен как можно точнее совпадать с с, а во втором — с 0! (Не забудем, что 0 здесь — это реперная точка, например, точка средних значений всех признаков.) Подобная простая модель характерна и для метода /С-средних: в ней каждый объект должен как можно точнее совпадать с центром кластера, которому он принадлежит. Подобные простые модели лежат в основе практически всех популярных методов анализа данных. В частности, путем раскрытия скобок в квадратичных расстояниях d, критерий (4.10) может быть преобразован к следующему виду.

В этой формуле замечательны оба выражения справа от знака равенства. Первое из них представляет сумму квадратов всех элементов матрицы данных. Эта сумма часто называется разбросом данных, так как она составлена из суммы квадратов расстояний от всех объектов до точки отсчета пространства, 0. Второе выражение — произведение численности группы S, S, на сумму квадратов компонент ее центра с. Эта последняя сумма — не что иное, как квадрат расстояния от с до 0, называемый в математике квадратом нормы с и обозначаемый через ||с||2. Таким образом, приходим к разложению разброса данных на сумму двух слагаемых:

где Г(У) — разброс данных в матрице Y. Первое слагаемое выражает ту часть разброса данных, которая объяснена аномальной группой, а второе — необъясненную часть. Поскольку метод минимизирует необъясненную часть, а разброс данных — постоянная величина, то одновременно максимизируется объясненная часть. Ее относительная величина — результат деления на разброс данных — выражает вклад аномальной группы в разброс данных. Чем больше вклад, тем лучше эта группа отделена от остальных данных.

Теперь покажем, что разложение (4.12) на самом деле реализует, в некотором смысле, критерий метода /С-срсдних. Для этого вернемся к обозначениям, сделанным нами ранее для разбиений. А именно, будем обозначать разбиение множества объектов на К кластеров через S = {5Д, а совокупность их центров через с = (q), k = 1, ..., К. Как доказано в [17], с. 231, для любого разбиения S = {5Д и центров с = (q) , полученных усреднением значений признаков на объектах внутри кластеров, т.е. в соответствии с алгоритмом /С-средних, имеет место разложение разброса данных, аналогичное (4.12):

В этом разложении слева — квадратичный разброс данных, справа — критерий W(S, с) метода К-средних. Средняя часть — предмет нашего интереса. Это вклад разбиения S в разброс данных, максимизируемый при минимизации W(S, с), гак как разброс данных — величина постоянная. Чтобы максимизировать сумму величин Nkкк >, составляющих этот критерий, надо, чтобы каждая величина Nfr число объектов в кластере Skt и < > — квадрат Евклидова расстояния

от 0 до ск, была как можно больше. Иными словами, критерий ^-средних требует искать разбиение, которое бы состояло из больших аномальных кластеров.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >