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

сточностью до константы.

Вэтом случае, как нетрудно видеть, разбиение, задаваемое разде­ ляющей функцией / (Z), является несмещенным разбиением.

д) Функционалы качества разбиения как результат применени метода максимального правдоподобия к задаче статистического оцени­ вания неизвестных параметров. Приведем здесь пример, иллюстри­

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

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

получаем логарифмическую функцию правдоподобия для наших наблюдений Xlt Х2, ..., Хп.

у на классы Sx, S2, •••, Sk, а также такие вектора средних at и кова­

риационные матрицы 2 и при которых величина —21 (Ѳ) достигала бы своего абсолютного минимума1.

1 Оговоримся сразу, что даже факт состоятельности полученных при этом

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

■96

При известном разбиении у оценками максимального правдо­ подобия для at будут «центры тяжести» классов

Х Ы { 1 ) = ± 2 X t, 1=1,2, .... k. ni xi£Sl

Подставляя их в (3.23) вместо аг и воспользовавшись очевидными тождественными преобразованиями, приходим к эквивалентности задачи поиска минимума функции —21 (Ѳ), определенной соотноше­ нием (3.23), и задачи поиска минимума выражения

В последнем выражении Wt выборочная ковариационная матрица, вычисленная по наблюдениям, входящим в состав 1-го класса (3.13).

Анализ выражений (3.24) и (3.25) в некоторых частных случаях немедленно приводит к следующим интересным выводам:

— если ковариационные матрицы исследуемых генеральных сово­ купностей равны между собой и известны, то задача оценивания не­ известного параметра Ѳ по методу максимального правдоподобия равносильна задаче разбиения наблюдений Хг на классы, подчинен­ ной функционалу качества разбиения вида (S), в котором под рас­ стоянием р подразумевается расстояние Махаланобиса;

— если ковариационные матрицы исследуемых генеральных сово­ купностей равны между собой, но не известны, то, подставляя в (3.25) вместо = 2 ее оценку максимального правдоподобия

2= -

п1=1

убеждаемся в эквивалентности задачи оценивания по методу макси­ мального правдоподобия параметра Ѳ и задачи поиска разбиения наблюдений X* на классы, наилучшего в смысле функционала ка­ чества Q4 (S).

В [68] авторы пытаются конструировать алгоритмы, реализующие идею получения оценок максимального правдоподобия для параметра Ѳ. Однако нам представляется главная ценность подобного подхода

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

5. Эталонные точки

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

§2. ОСНОВНЫЕ ТИПЫ ЗАДАЧ КЛАСТЕР-АНАЛИЗА

ИОСНОВНЫЕ ТИПЫ КЛАСТЕР-ПРОЦЕДУР

т-первых, целесообразно подразделение всех задач кластеранализа на два основных типа Бх и Б 2 в зависимости от объема п сово­

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

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

С точки зрения априорной информации об окончательном числе классов, на которое требуется разбить исследуемую совокупность объектов, задачи кластер-анализа можно подразделить на три ос­ новных типа:

а) число классов априори задано;

98

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

Под иерархическим деревом понимается последовательность пар

Рис. 3.3. Иерархическое дерево как геометрическое представление резуль­ тата действия иерархической процедуры разбиения наблюдений на классы:

а) агломеративное дерево; б) дивизимное дерево

Иерархическое дерево может быть двух типов. Если St1) — разбие­ ние, состоящее из п одноэлементных классов, а каждый класс разбие­

На рис. 3.3 схематически изображены два типа иерархических деревьев. Каждая вершина дерева изображает класс объектов.

— процедуры иерархические (агломеративные и дивизимные). Предназначены в основном для решения задач типа (в). Что касается объема классифицируемой совокупности, то формально иерархические процедуры применимы и для задач Бь и для задач Б 2. Однако посколь­

ку эти процедуры основаны на переборе элементов матрицы расстоя­ ний р ( X h X j ) (или матрицы соответствующих мер близости), то конст­ руктивно реализуемыми их можно признать лишь в пределах задач типа Б].. Следует отметить, что иерархические процедуры применяются иногда и для решения задач типов Б1а и Б1б (см. ниже);

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

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

§3. ОПИСАНИЕ КЛАСТЕР-ПРОЦЕДУР

ИИХ ОСНОВНЫХ СВОЙСТВ

1.Иерархические процедуры

Как отмечалось выше, принцип работы иерархических агломеративных (дивизимных) процедур состоит в последовательном объеди­ нении (разделении) групп элементов сначала самых близких (дале­ ких), а затем все более отдаленных друг от друга (приближенных друг к другу). При этом агломеративные процедуры начинают обычно

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

Снекоторой точки зрения иерархические процедуры, по сравнению

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

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

ной.

Кроме того, имеется широкий класс достаточно естественных примеров, в которых иерархические процедуры, даже подчиненные

100