Файл: Айвазян, С. А. Классификация многомерных наблюдений.pdf

для каждой группы признаков фактора, отличающегося на некоторый

нике для систематизации вновь открытых растений делают разбиение набора признаков на группы, так, чтобы 1-я группа характеризова­ ла бы форму листа, 2-я группа — форму плода и т. д. В связи с этим и возник эвристический метод корреляционных плеяд [7], [12], [13].

Метод корреляционных плеяд так же, как и метод экстремальной группировки, предназначен для нахождения таких групп признаков— «плеяд», что корреляционная связь, т. е. сумма модулей коэффициен­ тов корреляции, между параметрами одной группы (внутриплеядная связь) достаточно велика, а связь между параметрами из разных групп (межплеядная) — мала.

А именно, по определенному правилу по корреляционной матрице признаков образуется чертеж-граф, который затем с помощью различ­ ных приемов разбивают на подграфы. Элементы, соответствующие каждому из подграфов, и образуют плеяду.

Рассмотрим корреляционную матрицу R = (ri}), і, / = 1, 2, ..., р исходных признаков. Нарисуем р кружков; внутри каждого кружка напишем номер одного из признаков. Каждый кружок соединяется линиями со всеми остальными кружками; над линией, соединяющей і-й и /-й элементы (ребром графа), ставится значение модуля коэф­ фициента корреляции \rij\. Полученный таким образом чертеж рас­ сматриваем как исходный граф.

Задавшись (произвольным образом или на основании предвари­ тельного изучения корреляционной матрицы) некоторым пороговым значением коэффициента корреляции г0, исключаем из графа все реб­ ра, которые соответствуют коэффициентам корреляции, по модулю меньшим г0. Затем задаем некоторое гг >» г0 и повторяем описанную процедуру. При некотором достаточно большом г граф распадется на несколько подграфов, т. е. таких групп кружков, что связи (ребра графа) между кружками различных групп отсутствуют. Очевидно, что для полученных таким образом плеяд внутриплеядные коэффици­ енты корреляции будут больше г, а межплеядные — меньше г.

В другом варианте корреляционных плеяд [7] предлагается упоря­ дочивать признаки и рассматривать только те коэффициенты корреля­ ции, которые соответствуют связям между элементами в упорядочен­ ной системе.

Упорядочивание производится на основании принципа максималь­ ного корреляционного пути, а именно: все р признаков связываются при помощи (р—1) линий (ребер) так, чтобы сумма модулей коэффици­ ентов корреляции была максимальной. Это достигается следующим образом: в корреляционной матрице находится наибольший по абсо­ лютной величине коэффициент корреляции, например \ги т\ = г<'1) (коэффициенты на главной диагонали матрицы, равные единице, не рассматриваются).

196

Рисуем кружки, соответствующие параметрам хй> и х<т >, и над «связью» между ними пишем значение Н1). Затем, исключив г'1), нахо­ дим наибольший коэффициент в т-м столбце матрицы (это соответ­ ствует нахождению признака, который наиболее сильно после «связан» с х<т )) и наибольший коэффициент в 1-й строке матрицы (это соответствует нахождению признака, наиболее сильно после «свя­ занного» с х(/). Из найденных таким образом двух коэффициентов кор­ реляции выбирается наибольший — пусть это будет |г^| = г<2). Рисуем кружок х ^ \ соединяем его с кружком хй> и проставляем зна­

шаге мы получили новый признак, поэтому признаки, уже изобра­

каждом шаге находятся параметры, наиболее сильно связанные с дву­ мя последними рассмотренными параметрами, а затем выбирается один из них, соответствующий большему коэффициенту корреляции. Про­ цедура заканчивается после (р —1)-го шага; граф оказывается состоя­ щим из р кружков, соединенных (р—1) линией. Затем задается поро­ говое значение г, а все линии, соответствующие меньшим чем г коэф­ фициентам корреляции, исключаются из графа.

Назовем незамкнутым графом такой граф, для которого для любых двух кружков существует единственная траектория, составленная из линий связи, соединяющая эти два кружка. Очевидно, что во вто­ ром варианте метода корреляционных плеяд допускается построение только незамкнутых графов, а в первом варианте такое ограничение отсутствует.

Поэтому разбиения на плеяды, полученные разными способами, могут не совпадать.

В работе [10] приводятся результаты экспериментальной проверки алгоритмов экстремальной группировки параметров, а также сравне­ ние полученных результатов с результатами, даваемыми методом кор­ реляционных плеяд.

Эксперимент проводился на физиологическом материале: исследо­ вались влияния шумов и вибрации на работоспособность и самочув­ ствие. Снимались 33 признака (р — 33), из них 7 параметров, характеризующих температуру тела; 4 — кровяное давление; 14 — аудиометрию (т. е. порог слышимости на заданной частоте); 2 — дыха­ ние; 4 — силу и выносливость рук и 2 (обособленных параметра) — пульс и скорость реакции.

С точки зрения физиолога «идеальным» было бы разбиение, при котором все характеристики температур образовали бы отдельную груп­ пу; параметры, характеризующие давление — свою отдельную груп­ пу и т. д., обособленные параметры образовали бы группы, состоящие из одного элемента. Наиболее близким к «идеальному» оказалось раз­ биение, полученное вторым алгоритмом экстремальной группировки, хотя алгоритм и присоединяет обособленные параметры к другим груп­

197

пам. Наименее точные (среди трех сравниваемых алгоритмов) резуль­ таты дал метод корреляционных плеяд.

г) Снижение размерности с помощью кластер-процедур. В ряде си туаций удобно рассматривать признаки х (г) (і = 1,2,...,/?), как одно­ мерные наблюдения и использовать многократное повторение этих наблюдений (на п исследуемых объектах) для введения и вычисления таких естественных мер близости между объектами (признаками) xU) и х</>, какими являются в данном случае абсолютная величина ко­ эффициента корреляции гі} или корреляционное отношение гр; (по поводу вычисления Гц и тру-, и их свойств (см., например, Ш)1.

Следуя идее обобщенного (степенного) среднего (см. § 1 главы III), введем в качестве меры близости групп признаков A t и A q величину

где т — некоторый числовой параметр, выбор конкретного значения которого находится в нашем распоряжении, а тѵ— число признаков, составляющих группу Лѵ. Аналогично вводится средняя мера бли­ зости R (Аі) признаков, входящих в одну группу

Если желаемая размерность p' {p' <; р) задана заранее, то исходные р признаков хб), лг<2*), ..., *(р) разбивают на p' однородных групп одним из двух способов: либо последовательно объединяя в одну группу два

ходных признаков на p' групп, при котором усредненная мера вну­ тригрупповой близости признаков

была бы максимальной. Последнего обычно удается добиться с по­ мощью простого перебора вариантов, так как общее число признаков р, как правило, не превосходит несколько десятков, а p' — несколько единиц. После этого от каждой группы следует отобрать по одному пред­

1 Если для описания меры близости между х ^ и используется корреля­ ционное отношение, то предварительно целесообразно произвести симметризацию этой меры, рассматривая в качестве симметричной характеристики степени бли­

198

ставителю, используя для этого технику метода главных компо­ нент или факторного анализа (отдельно внутри каждой группы).

Если же желаемая размерность р' заранее не определена, то раз^ биение исходных признаков на группы, а следовательно, и выбор не­ известного р' , можно подчинить задаче максимизации функционала типа

R {x) + Zx,

где Zx — введенная в предыдущей главе мера концентрации разбие­ ния, т. е.

X

Здесь v(x<‘>) — число признаков в группе, содержащей признак х^К Можно воспользоваться также и двойственной формулировкой экстре­ мальной задачи разбиения объектов (признаков) на неизвестное чис­ ло групп (см. § 1, глава III).

2. Выявление наиболее информативных признаков при наличии обучения

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

о каждой из которых известно, что она извлечена из какого-то одного класса (представляет один из исследуемых «образов»), причем эти пор­ ции представляют все k исследуемых классов (образов).

При наличии обучающих выборок (4.45) и при заданном алгорит­ ме классификации б задачу выявления наиболее информативных при­ знаков можно сформулировать следующим образом: для любого на­ перед заданного р' <ср указать' такой набор признаков

отобранных из числа исходных р признаков лМ), х<2ф ..., х(р\ классифи­ кация по которому (т. е. при игнорировании всех остальных р — р' признаков) с помощью заданного алгоритма б пг элементов обучающей выборки приводила бы к наименьшей средней доле ошибочно расклас­ сифицированных наблюдений (4.45).

То есть подвектор Х(°'> (б) вектора X должен обладать тем свой­ ством, что

- = у у; (б; Х<р">(б))

т .

199

Здесь ѵг (б; Х<р'>) — число неправильно расклассифицированных

наблюдения і -го класа (т. е. я г — это удельный вес наблюдений г-го класса в совокупности всех мыслимых наблюдений), то набор Х (р,>(б) определяют из условия минимизации взвешенной средней доли оши­ бочно расклассифицированных наблюдений обучающих выборок, т. е.

а) Методы перебора вариантов. Будем называть пространство Х<р'> размерности p' < р наиболее информативным (относительно заданного

алгоритма классификации б), если его координаты Х<р'> обладают свойством (4.47) (или свойством (4.48) в байесовской постановке, т. е. при наличии априорных вероятностей я ;). Очевидно, наиболее инфор­

мативное подпространство Х<р'> может быть определено с помощью метода полного перебора вариантов, при котором для каждого из

Ср вариантов наборов] из р’ признаков подсчитывается средняя доля q ошибочно расклассифицированных наблюдений обучающих

выборок и выбирается тот набор, при котором q = q — min. Однако такой метод требует огромного объема вычислений. Объем вычислений можно сократить, использовав метод Монте-Карло или метод случай­ ного поиска. Метод Монте-Карло отличается от полного перебора тем, что значения q находятся не для всех подпространств размерности р' , а только для некоторых. Эти подпространства выбираются случай­ ным образом из множества всех подпространств в предположении, что все подпространства равновероятны.

Назовем эффективным подпространством признаков такие подпро­

Поясним на примере, насколько метод Монте-Карло может умень­ шить число «перебираемых» подпространств по сравнению с методом полного перебора.

П р и м е р . Пусть k = 3, р=17, признаки распределены нормаль­ но с одной и той же ковариационной матрицей во всех трех классах, причем корреляция для различных пар признаков колеблется от 0,01

200

достаточно для оценки q в случае

Был построен график дискретной функции N (ѵ), показывающий, сколько подпространств соответствует различным значениям ѵ.

Оказалось, что ѵ = vmln = 88,[и нашлось только одно подпростран­

метод Монте-Карло с высокой степенью вероятности (в среднем в 95 случаях из ста) даст значительный выигрыш в вычислениях: 126 под­ пространств вместо 680.

Метод, названный случайным поиском с адаптацией (СПА), [8],

является улучшением метода Монте-Карло. В отличие от чистого мето­ да Монте-Карло этот метод состоит в случайном поиске подпростран­ ства ХЭф(р') с «поощрением» и «наказанием» отдельных признаков, х(1), Д 1), ..., х^К Для этого в начале поиска задаются вероятности выбора

яь я 2, ..., яр каждого из признаков х(1), х<2), ..., х ^ \ если перед на­ чалом поиска нет информации о предпочтительности выбора какого-

к изменению вероятностей ях, я 2, ..., яр выбора признаков на следую­ щих этапах поиска в зависимости от результатов предыдущих этапов.

дений обучающих выборок. После анализа некоторого числа г случай­

но выбранных подпространств Х[(р ), Х2Р \ ..., Х‘р ) находим подпро­ странства Xj.min и Хі.тах, дающие минимальное vmin и максималь­ ное ѵтах значения из всех г подсчитанных значений ѵ. Далее, увели­ чиваем вероятность выбора каждого из признаков составивших

A (iPmin на некоторую добавочную вероятность h. После такого поощ­ рения проводим наказание признаков, на которых построено

При измененных вероятностях выбора каждого из признаков л:*1*,

201