Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 35
Текст из файла (страница 35)
д. Особенностью метода является декомпозиция (5.29) ",»'. М; = ~ч„'ч)+;у вб, \ / с где =й(5»)=п р(5«) справедливая независимо от того, пересекаются кластеры 5, друг с другом или нет'. туре довольно давно, правда, из чисто эвристических соображений, например метод (1-коэффициентов !16! ), алгоритм Спектр (34! и др. В случае, когда часть связей р„может быть отрицательна (если, например, матрица (р„) предварительно центрирована), аппроксимационный критерий д» (5) допускает решение, при котором и (5).
а значит, и порог и, отрицательны. В этом случае оптимальное множество 5 является <антикластером», так как состоит из наиболее непохожих друг на друга объектов. До последнего времени задачи построения антикластеров в приложениях рассматривались редко. Описанный подход допускает естественное развитие, состоящее в многократном повторении аппроксимации применительно к «остаточным» матрицам связей, получаемым вычитанием из ры «объясненных» на данном шаге связей Лз».
Очевидно, на разных этапах процесса аппроксимируемые матрицы связи будут разными, так что конструируемые кластеры и их средние внутренние связи будут, вообще говоря, разными. Указанный метод последовательного исчерпания связей ры (качественный факторный анализ !!1О!) может рассматриваться как пошаговая процедура идентификации модели адаптивных кластеров, согласно которой заданная матрица связи (ры) представляется (с некоторой погрешностью) в виде суммы матриц (Л~з,у), отвечающих искомым кластерам 5,: Разложение (5.29) позволяет трактовать величины я~ как характеристики значимости вклада отдельных кластеров в дисперсию исходных связей н на этой основе оценивать доли объясненной и необъясненной дисперсии данных, что включает кластер-анализ в традиционную методологию многомерного статистического анализа. Указанные свойства метода последовательного исчерпания (декомпозиция (5.29), «сильная компактность> кластеров, вычислительная эффективность) дают ему определенные преимущества по сравнениюсдругими подходами к оценке параметров модели (5.28) [ 1 ! 1).
Рассмотрим некоторые критерии классификации, возникающие в задачах аппроксимации таблиц «объект— свойство>. В этих задачах подмножества объектов 5 задаются п-мерными (1, О)-векторами г = (г;), где г; = 1, если х; 5 5 и г, == 0 в противном случае. Разбиение 5 -= (5„ ..., 5>) множества объектов задается (п Х й)-матрицей Х = .= (гп) со столбцами г,, г«, гю характеризующими классы разбиения 5. Очевидно, (пХп)-матрица ХУ' совпадает с ранее определенной матрипей (зю), а й Х к-матрица Х к — диагональная матрица величин и,.
Линейное пространство Е (г,) — — (г(г =- га при подходящем а) является адекватным представлением разбиения 5, поскольку всякий вектор г —: Ла выражает возможную кодировку классов 5, величинами а,. Аппроксимационные построения в терминах линейных пространств, ассоциированных с номинальными и количественными признаками, приводят к критериям вида (5.1), (5.11) и (5.26) при подходящих способах вычисления характеристик близости объектов [111[.
Здесь рассмотрим только наиболее прозрачную схему метода главных кластеров [112[. Согласно этой схеме матрица данных Х =- (хы)(( — номера объектов, 1 — номера признаков) аппроксимируется какимлибо элементом г 5»' (3), где 2 — (пХЙ)-матрица искомой классификации (с не обязательно непересекающимися классами), так что справедливо представление хгг = ам гп+ а>7 гм +... + аы г, „+ ам (5.30) с «невязками» еьь Смысл равенств (5.30): значения признаков / на объектах О; Е 5~ с точностью до невязок ам совпадают с величинами а,н которые задают, таким образом, «эталон> кластера 5~ в признаковом пространстве.
Модель (5.30) является линейной моделью факторного анализа (см. гл. 14) с той особенностью, что величины г;, принимают не любые значении, а только нулеединичные. 177 Аппроксимациоиная задача отыскания произвольных ам и нулеединичных гы по заданным х„в модели (5.30) с целью минимизации суммы квадратов иевязок ~е„ (5.31) ь» как нетрудно показать, эквивалентна задаче построения классификации 5 == (5„..., 5«) (при непересекающихся классах), минимизирующей критерий (5.11) с а»у = х, (1), илн, что то же самое, максимизирующей критерии вида й(3)=~ ' ~ Ь,, (5.32) — ! ~ ~газ где связи между объектами — их скалярные произведения йы — — Хх» х,ь Вид критерия (5.31) позволяет в каков-то мере уточнить характер предварительного преобразования данных, необходимого для адекватного применения критериев, эквивалентных (5.11) и (5.32).
Действительно, в сумму (5.32) все невязки «„ входят равноправно, что подразумевает равноправие всех элементов матрицы донны. Скажем, изменение масштаба )сго признака в а раз вызовет а-'-ьратное изменение «веса» соответствующих невязок в критерии (5.31) и соответствующее изменение решения. По-видимому, критерию (5.3!) соответствует предварительное уравновешивание матрицы данных, приводящее к выполнению равенств Хх«м -= п, Хх,', р. Ф 1 Формулировка задачи классификации как задачи оценки параметров модели (5.30) позволяет распространить на нее принцип пошаговой аппроксимации. На первом шаге отыскиваются параметры первого кластера путем минимизации критерия Х (хы — ат г;) ' по произвольным а; и ь» нулеединичным г;.
Полученное решение определяет эталонный вектор первого кластера а, = (аы) и его состав г, = = (г„). На общем (т+ 1)-м шаге исходя из полученного решения а„г, и «текущей» остаточной матрицы ха осуществляется переход к матрице следующего шага х'+' =-х' — а,.гм. а ц у Метод назван методом главных кластеров из-за аналогии с методом главных компонент, «простиракяцейся» вплоть до декомпозиции ~~«хну = ~«чю+~~~ в«р (5.33) с« кт где т~ --- а (5,) — — и, Ь (5) — вклад Е-го кластера 5, в суммарный разброс данных, справедливой даже при пересекающихся главных кластерах. Ситуация здесь похожа на ту, которая обсуждалась применительно к модели аддитивных кластеров (5.28) с декомпозицией (5.29).
На каждом Ьм шаге аппроксимация сводится к максимизации величины д (5,) и соответственно каждыи главный кластер является сильным кластером (относительно матрицы связей (Ь„-)). Локально-оптимальный алгоритм последовательного присоединения объектов к кластеру 5 начиная с 5 = Я, по максимуму средней связи Ь (й 5) (О, с~ 5), имеет здесь простой геометрический смысл: к 5 присоединяется тот объект О„ длина проекции которого на радиус-вектор центра тяжести 5 превышает половину длины радиус-вектора.
С точки зрения интерпретации главных кластеров и отбора «значимых» компонент решения особый интерес представляют разложения ч, = д (5,) = У Ь (5 5,) =- .'Р»а «сии »,ез 7 которые характеризуют относительный вклад (значимость) отдельных объектов (Ь (1, 5,)) и признаков (а,", и,) применительно к данному конкретному кластеру. Таким образом, обращение к модели (5.30) расширяет возможности традиционного дисперсион ного критерия (5. 11) и дает решения, обладающие определенными преимуществами («шлейф» интерпретирующих характеристик, «сильная компактность» кластеров, возможность пересечений и т.п,).
ВЫВОДЫ !. Общая постановка задачи классификации совокупности объектов О,, О„..., О„в условиях отсутствия обучающих выборок состоит в требовании разбиения этой совокупности на некоторое число (заранее известное или нет) однородных в определенном смысле классов, При этом исходная информация о классифицируемых объектах представлена либо значениями многомерного признака (по каждому объекту в отдельности), либо матрицей попарных расстояний (или близостей) между объектами, а понятие однородности основано на предположении, что геометрическая близость двух или нескольких объектов означает близость их «физических» состояний, их сходство.
179 2. Математическая постановка задачи автоматической классификации требует формализации понятия «качество разбиения». С этой целью в рассмотрение вводится понятие критерия (функционала) качества разбиения Я (5), который задает способ сопоставления с каждым возможным разбиением 5 заданного множества объектов на классы некоторого числа Я (5), оценивакицего (в определенной шкале) степень оптимальности данного разбиения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
