Ф4. 6. 2. Метод К-средних: формулировки и вычисление

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

Ниже дастся точная формулировка алгоритма w/C-средних (?), где t — порог разрешения, т. е. задаваемое пользователем минимальное количество объектов в аномальной группе, необходимое, чтобы она могла восприниматься как генератор отдельного кластера. В приложениях, использующих небольшие объемы данных (порядка десятков и сотен объектов), значение t может быть принято равным 1.

Алгоритм иК-средних (t)

• 0. Настройка. Предобработка и стандартизация данных. Полагаем k = 1, I_k = I — соответственно номер кластера и множество объектов, на котором ищется аномальная группа. Выбирается реперная точка а и вычитается из всех строк таблицы данных (сдвиг точки отсчета в а).
• 1. Аномальная группа. Метод выделения аномальной группы применяется к I_k для нахождения k-й аномальной группы 5* и ее центра q.
• 2. Условие остановки. Если условие остановки (см. ниже) не выполняется, то удаляем S^ из 1производим замену k <= k + 1 и /^<= I_k— Sпосле которой переходим на шаг 1. Если же условие остановки верно, то переходим к шагу 3.
• 3. Отбрасывание малых кластеров. Удалим все найденные группы, состоящие из t или менее объектов. (В зависимости от желания пользователя, объекты из удаленных групп либо возвращаются в данные для последующей кластеризации, либо удаляются из данных вовсе как «нехарактерные» объекты.) Обозначим количество оставшихся кластеров через К, а их центры через q, с₂,…, с_к.
• 4. Метод /^-средних. Применяем метод iC-средних, используя с_и с₂, с_к в качестве начальных центров.

Условие остановки на шаге 2 может включать в себя любые или даже все из следующих условий:

• 1. Во множестве I не осталось объектов, не попавших в ту или иную аномальную группу, т. е. S_k = I_k.
• 2. Большой суммарный вклад: суммарный вклад первых аномальных групп в разброс данных достиг изначально заданного порога, например 50%.
• 3. Малый вклад отдельной аномальной группы: вклад S_K в разброс данных слишком мал; например, сравним со средним вкладом одного объекта, T (Y) / N, где T (Y) — разброс данных.
• 4. Количество кластеров достигло заранее заданного значения К.

Условие 1 выполняется часто, особенно если в данных есть «естественные» кластеры, сильно отличающиеся по вкладу в разброс данных. Условия 2 и 3 могут быть рассмотрены в качестве уровней разрешения, задаваемых пользователем. В отличие от условия 4, они основаны на структуре анализируемых данных, а не на априорных представлениях.

Рабочий пример 4.8. Кластеризация выборки из одномерного нормального распределения методом иК-средних

Сгенерируем одномерную выборку X из 280 точек из Гауссового распределения с параметрами Л^г(0, 10) (рис. 4.20). Для удобства читателя данное случайное множество представлено в приложении (см. табл. П5.2). Многие бы сказали, что это множество составляет единичный Гауссов кластер, так что нет никакого смысла его разбивать далее. Мы применяем алгоритм иК-средних, чтобы обнажить принцип кластеризации, заложенный в этом алгоритме.

Несмотря на симметричность Гауссова распределения, выборка несколько смещена в отрицательную сторону: среднее равно -0,89, а не 0, а медиана вообще равна -1,27. При этом максимальное расстояние до среднего приходится на максимальное положительное значение 32,02, а не на «максимально отрицательное» — 30,27.

Рис. 4.20. Гистограмма выборки из 280 элементов, сгенерированных командой 10*randn в среде программирования МатЛаб из нормального распределения

с параметрами JV (0,10)

Вычисление аномальной группы начинается с наиболее удаленного от 0 значения 32,02 и в итоге составляет 83 объекта в интервале между 5,28 и максимумом. Такое разделение согласуется с тем, что происходит в реальности. Например, для роста молодых мужчин, призываемых на военную службу, гистограмма имеет колоколообразный вид, т. е. может рассматриваться как приближенно нормальная. Однако «объекты», соответствующие двум сторонам «колокола», отличаются в разных реальных ситуациях. Например, люди невысокого роста не могут выполнить ряд специфических задач, тогда как слишком высоким будет трудновато в тесных помещениях.

Итеративное применение метода выделения аномальных групп отсекает крайние фрагменты распределения и его остатков. Аномальные группы, в порядке их формирования, включая внутригрупповые средние и вклады в разброс данных, представлены в табл. 4.17.

Последние из полученных групп расположены вокруг 0, и они совсем невелики. Можно также видеть, что вклад следующей группы может быть больше, чем предыдущей, из-за локальности алгоритма выделения аномальной группы, несмотря на критерий, требующий, чтобы на каждой итерации отыскивался кластер с наибольшим вкладом. Суммарный вклад девяти кластеров составляет около 86%, при этом последние пять кластеров практически ничего не добавляют к этому.

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

4.6.4. Проведите подобное вычисление самостоятельно, сгенерировав 500 гауссовых значений. Подсказка: генерация выборки х, состоящей из 500 значений из Гауссова распределения с нулевым математическим ожиданием и стандартным отклонением 10, может быть осуществлена в МагЛабе с помощью команды х= 10 • randn (500,l).

Метод w/C-средних является достаточно гибким, позволяя отделять как выбросы, так и промежуточные объекты, а также и «трясину» объектов, находящихся рядом с общим средним. Например, можно удалить все малые аномальные группы перед тем, как окончательно применять метод К-средних. В некоторых задачах, например, в структурировании множества регионов для лучшего планирования или мониторинга или анализа климатических изменений не следует исключать из рассмотрения ни один объект. В других задачах, таких как формирование обзора корпуса документов, аномальные тексты, сильно отличающиеся от остальных, могут быть полностью удалены перед окончательным кластер-анализом.

Таблица 4.17

Характеристики кластеров, полученных итеративным применением метода

выделения аномальной группы к выборке из нормального распределения из табл. А5.2. Кластеры представлены в порядке их получения, наряду с их размерами, левой и правой границами номеров объектов в порядке возрастания, а также средними и вкладами в разброс данных

В ряде экспериментов с перекрывающимися гауссовыми кластерами, описанными в работе [25], метод иК-средних показал себя вполне конкурентоспособным и оказался лучше многих других способов выбора К.

Проект 4.1. Роль предварительного преобразования по методу главных компонент

Метод главных компонент — один из основных методов суммаризации данных, восходящий к работам К. Пирсона (см., например, [17, 27]). Он формирует линейные комбинации исходных признаков, вносящие максимальный вклад в разброс данных — они-то и называются главными компонентами. Существует мнение, что структура многомерных данных лучше выявляется, если данные сначала будут «очищены» с помощью метода главных компонент, используя всего несколько главных компонент вместо исходных признаков. Это мнение далеко не общепринято. Одно из возражений относительно целесообразности применения метода главных компонент дано в книге А. Крыштановского [4]: в ней приводится пример структуры данных, которая становится менее выраженной при переходе к главным компонентам. Попробуем проверить, действительно ли это так.

В примере Крыштановского рассматриваются сгенерированные данные, состоящие из двух Гауссовых кластеров, каждый из которых содержит пятьсот 15-мерных элементов. Первый кластер может быть получен с помощью следующих команд в МатЛабс:

«Ь (1:500,1)=10*randn (500,1);

«Ь (1:500,2:15)=repmat (b (1:500,1), 1,14)+20*randn (500,14).

Первая переменная является Гауссовой со средним 0 и стандартным отклонением 10, тогда как остальные четырнадцать переменных добавляют к данной гауссовой величине еще одну со средним 0 и стандартным отклонением, равным 20. Поэтому это множество — выборка из 15-мерного Гауссова распределения с диагональной матрицей ковариации, центр которого находится в начале координат пространства, со стандартными отклонениями признаков, равными 22,36, т. е. квадратному корню из 10² + 20², за исключением первого признака, стандартное отклонение которого равно 10.

Элементы второго кластера генерируются путем создания 500 следующих строк той же матрицы в той же манере:

«b (501:1000,1)=20+10*randn (500,1);

«b (501:1000,2:15)=repmat (b (501:1000,l), l,14)+20*randn (500,14)+10;

Первый признак имеет центр в точке 20, а остальные — в точке 30. Стандартные отклонения — такие же, как в первом кластере.

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

Метод мК-средних в применении к этим, предварительно центрированным и нормализованным по размаху данным, находит гораздо больше кластеров, 13, при пороге разрешения, равном t = 1. Если же увеличить порог разрешения до t = 200, т. е. исключить все аномальные группы меньшего размера, то метод выдаст два кластера, которые отличаются от сгенерированных 96 элементами (см. первый столбец табл. 4.19, показывающей результаты вычислений), так что суммарная ошибка равна 9,6%. Тот же метод, примененный к данным, центрированным и нормализованным с помощью стандартных отклонений, приводит к 99 ошибкам; достаточно умеренное повышение с учетом специфики сгенерированных данных.

Так как Крыштановский |4| работал с четырьмя главными компонентами, мы также рассчитаем первые четыре главные компоненты. Например, случай, когда данные предварительно центрированы по средним и нормированы по размаху, реализуется следующими командами МатЛаба:

«n=1000; br=(b-repmat (mean (b), n, l))./ repmat (max (b)-min (b), n^);%стандартизация «[zr, mr, cr] =svd (br); % сингулярное разложение матрицы данных «zr4=zr (, l:4); %те же объекты, признаки — первые 4 главные компоненты.

Рис. 4.21. Представление сгенерированных данных, после центрирования, на плоскости двух главных компонент (левый рисунок), с выделением точек второго кластера в виде кружков (правый рисунок).

При нормировании по стандартным отклонениям используются те же команды, только в первой строке вместо max (b)-min (b) нужно поставить std (b). Четыре главные компоненты составляют порядка 66% разброса данных как в первом, так и втором случаях.

Таблица 4.18

Количество ошибок метода w/f-средних при разных стандартизациях исходных данных и соответствующих четырех главных компонентах

Данные, нормированные стандартными отклонениями, особенно важны в данном контексте, потому что Крыштановский использовал стандартную версию метода главных компонент, которая основана на матрице корреляции между признаками. Использованная выше версия основана па так называемом сингулярном разложении матрицы данных. Она более гибкая, чем стандартная версия, так как позволяет использовать различные предварительные преобразования данных. Две версии дают одинаковые результаты в случае, когда данные центрированы по средним и нормализованы по стандартным отклонениям, т. е. подвергнуты преобразованию z-скоринг [ 17]. Метод иК-средних, примененный к каждому из трех множеств данных (центрированные (а) ненормализованные, (б) нормализованные по размаху, (в) нормализованные по стандартному отклонению) при пороге разрешения 200, показал достаточно согласованные результаты (см. табл. 4.1).

В общем, эти результаты скорее подтверждают, нежели опровергают, идею о том, что при использовании главных компонент «очищенные» данные лучше структурированы. Например, для стандартной версии главных компонент использование исходных данных приводит к 99 ошибкам, а «очищенных» — к 92 ошибкам. Неудовлетворительные результаты использования главных компонент в [4], возможно, связаны с тем, что применялась версия метода /С-средних со случайными инициализациями для всех случаев без исключений, что помешало найти «правильную» пару начальных центров, в отличие от метода и/(-средних, который такую пару находит автоматически, как противоположные друг другу «аномальности».

Кстати говоря

• 4. Коррелирование и классификация
• 4.1. Оказывается, у выражения: «Если ты такой умный, то почему такой бедный?» есть строгое математическое обоснование. Начнем с двух известных постулатов:

Постулат 1: Знание = сила.

Постулат 2: Время = деньги.

Все знают, что: путь = скорость • время = работа / сила.

Отсюда работа / время = сила • скорость. (1).

Подставив значения для времени и силы из обоих постулатов в выражении (1), получим:

работа / (знание • скорость) = деньги. (2).

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

• 4.2.
• — Что-то наш баран сегодня грустный какой-то. Может, его зарежем?
• — Ну, если думаешь, что это его развеселит…
• 4.3. Так, значит, этот тип, он жалуется невропатологу на бессоницу. Врач внимательно слушает, потом достает целую кучу разных клякс, вынимает одну:
  • —Так, мистер Джонсон, что Вы видите на этой картинке?

Джонсон:

— Секс.

Доктор смотрит на кляксу, пожимает плечами, роется и достает новую:

— А что вы думаете об этой картинке?

Джонсон:

— Секс.

Врач делает пометки в блокноте, просматривает список обычных ответов, делает новые пометки:

• — Hv хорошо. А вот эта клякса?
• — Секс!!!

Доктор сурово смотрит на пациента:

• — Мистер Джонсон, а Вам не приходило в голову, что у Вас ненормально сильная сексуальная озабоченность?
• — У меня? Вот это да, доктор! Вы же сами пристаете ко мне с этими Вашими грязными картинками…
• 4.4. Пещерные люди обычно стукали девушек по голове дубинкой, а затем уволакивали их. Вы всегда смогли бы отличить самую хорошенькую девушку племени — у нее черный синяк под глазом, разодраны губы, переломан нос…
• 4.6. Профессор математики студентам:
  • — Я делю людей на три типа: тех, кто умеет считать, и тех, кто не умеет!!!
• 4.7. Бежит слепой зайчик по тропинке и спотыкается об змею. Обращается к змее:
  • — Извините, я слепой, и не видел вас, из-за слепоты, я даже не знаю, кто я. Змея отвечает:
  • — Я тебя понимаю. Я тоже слепая и не знаю, кто я.

Зайчик предлагает:

— Давай, ощупаем друг друга и определим кто мы…

Змея ощупывает зайчика и говорит:

— Ты мягкий, пушистый, с коротким хвостом и длинными ушами. Ты, наверное, зайчик.

Зайчик в свою очередь ощупал змею и говорит:

• — Ты холодная, скользкая, у тебя маленькая голова и очень длинный язык. Ты, наверное, менеджер или руководитель проекта…
• 4.8.
• — Давайте, определим причину вашего невроза, — говорит психотерапевт пациенту.
• — Скажите, что у вас за работа?
• — Я сортирую апельсины.
• — Так, так, расскажите поподробнее.
• — Вниз по желобу скатываются апельсины, я стою внизу и должен их сортировать. В одну корзину — большие, в среднюю — поменьше, и в маленькую — маленькие.
• — Но в чем причина нервничать на этой спокойной работе?
• — Спокойной? Да поймите же вы, наконец, что целый день я должен принимать решения, решения, решения!
• 4.9. Возвращается сын нового русского первого сентября из школы. Отец спрашивает, как ему там понравилось, на что сын отвечает:
  • — Да ну-у, как всегда надули… Ни видака, ни телевизора, двадцать лохов сидят, да еще и парты со стульями деревянные. А говорили: «ПЕРВЫЙ КЛАСС!».
• 4.10. Едет 600-й мерседес. Ему в заднюю часть кузова въезжает КамАЗ. Из «мерса» выходит новый русский весь в красных пиджаках (ну как обычно) и говорит тому, который в КамАЗе:
  • — Ты попал на бабки!

Тот ему:

• — Сколько?
• — Да ты меня что, не понял? Ты на бабки попал!!!
• — Да сколько?
• — Тридцатник.

Тот из КамАЗа открывает кузов, а у него весь КамАЗ пачками баксов заложен. Берет одну пачку, отдаст.

— Вот тебе тридцатник, и еще пара штук сверху за беспокойство.

Наш друг из мерседеса:

• — Слушай, а ты кто?
• — Я? Я новый русский. А ты?
• — Да теперь уж и не знаю.
• 4.11. Муж, мрачный как туча, возвращается домой из больницы, где проведывал тещу. Жена встречает его у дверей.

Ж:

— Как дела у мамы?

М:

— Твоя мать здорова, как лошадь, скоро выйдет из больницы и будет жить у нас!

Ж:

— Не понимаю. Вчера врач сказал мне, что она при смерти.

М (зло):

• — Не знаю, что он сказал тебе, а мне он велел готовиться к самому худшему.
• 4.12. Изобретатель демонстрирует свое новое изобретение.
• — Я разработал систему, которая позволяет установить личность человека, но голосу.
• — И что же я должен сделать?
• — Вы должны четко и ясно назвать свои имя и фамилию…
• 4.13.
• — О Боже! — закричала ворожея, посмотрев на руку клиента.
• — Вас четвертуют, засолят и съедят!
• — Одну минуточку! — говорит клиент. — Я просто забыл снять перчатки. Недавно купил, из настоящей свиной кожи.