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

Встречается и другой вариант использования понятия обобщенной дисперсии как характеристики качества разбиения, в котором опера­ ция суммирования Wl по классам заменена операцией умножения

QAS)= П (det W $ l . i=1

Как видно из формул (3.12 и 3.13), функционал Q3 (5) является средней арифметической (по всем классам) характеристикой обобщен­ ной внутриклассовой дисперсии, в то время как функционал Qi (S) пропорционален средней геометрической характеристике тех же ве­ личин.

Заметим, что использование функционалов Q3 (S) и Q4(S) является особенно уместным в ситуациях, при которых исследователь, в первую очередь, задается вопросом: не сосредоточены ли наблюдения, разби­ тые на классы S4, S 2, ..., S h, в пространстве размерности меньшей, чем р?

З а м е ч а н и е . При вероятностной модификации схем кластеранализа соответственно видоизменится запись приведенных выше функционалов. Так, например,

Q I ( S ) = 2 } p*(X,X(i))P(dX),

!= 1S(

где

параметров, характеризующих межклассовую и внутриклассовую структуру наблюдений. Зададимся вопросом: нельзя ли выделить такой достаточно полный набор величин «i(S), u2(S),..., характеризую­ щих как межклассовую, так и внутриклассовую структуру наблюде­ ний при каждом фиксированном разбиении на классы S, чтобы су­ ществовала некоторая функция Q (щ, и2, ...) от этих величин, которую мы могли бы считать в каком-то смысле универсальной характеристи­

числовые характеристики: степени близости элементов внутри клас­ сов (ы4); степени удаленности классов друг от друга (и2); степени «оди­ наковости» распределения многомерных наблюдений внутри классов (и3); степени равномерности распределения общего числа классифи­ цируемых наблюдений п по классам (м4).

Что касается установления общего вида функции Q (щ, и2, и3, м4), то без введения дополнительной априорной информации о наблю­ дениях Х і (характере и общем виде их закона распределения внутри

87

классов и т. п.) единственным возможным подходом в решении этой задачи, как нам представляется, является экспертно-эксперименталь­ ное исследование. Именно с этих позиций в [12] сделана попытка опре­ деления общего вида функции Q. Чтобы определить рассмотренные в этой работе величины иъ и2, и3 и «4, введем понятие кратчайшего не­ замкнутого пути (КИП), соединяющего все п точек исходной сово­ купности в связный неориентированный графе минимальной суммарной длиной ребер1. Под длиной ребра понимается расстояние между соот­ ветствующими точками совокупности в смысле выбранной метрики. Построение такого графа можно начать с пары наиболее близких точек. Если таких пар несколько, то выбирается любая из этих пар. Пусть это будут наблюдения с номерами і0 и /0. Затем с помощью срав­

Всего таких ребер, как легко видеть, будет пг — 1. И пусть pm]n (р) — минимальное из ребер, непосредственно примыкающих к ребру f> и относящихся к /-му классу, если таковое имеется. Занумеруем в оп­ ределенном порядке граничные, разрубленные ребра Я,1( таким образом, чтобы имелось взаимно-однозначное соответствие

между номерами граничных ребер и номерами примыкающих к ним классов, за исключением одного, геометрически представленного одним из «хвостов» графа. На рис. 3.2 представлено изображение кратчайшего незамкнутого пути. Выбрасывая ребра I, II, III, полу­ чаем четыре связных графа, что соответствует разбиению совокупности на четыре группы. Обозначим с помощью \ одно из таких ребер /-го класса.

1 Использование КНП в задачах классификации имеет длинную историю. Методы классификации, основанные на КНП, использовались для решения за­ дач в области антропологии, биологии, сельского хозяйства, лингвистики (см.,

любую из точек Хт (ід) и Хт (/ ).

88

Теперь, следуя [12], мы опреде­

лим величины щ следующим обра­ зом:

k ~ 1 / = 1

Рис. 3.2. Графическое изображение кратчайшего незамкнутого пути

Эмпирический перебор различных вариантов общего вида функции Q в сочетании с анализом результатов экспертных оценок качества всевозможных разбиений привели авторов [12] к следующей формуле:

(3.15)

где а, Ь, с и d — некоторые неотрицательные параметры, оставляющие исследователю определенную свободу выбора в каждом конкретном случае. Авторы [12] отмечали хорошее согласие своих экспериментов с экспертными оценками при a = ö = c = d = 1.

тором Q (S*) = max Q (S ). s

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

б) Функционалы качества разбиения при неизвестном числе классов.

В ситуациях, когда исследователю заранее не известно, на какое число классов подразделяются исходные многомерные наблюдения Хи Х ъ ..., Хп, функционалы качества разбиения Q (S ) выбирают чаще всего в виде простой алгебраической комбинации (суммы, разности, произведения, отношения) двух функционалов Ix (S) и / 2 (S), один

89

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

Л ( 5 ) = ѵ 2 Р(Х„ Х(/))

I = i x i esl

и

h (5) = ck (S),

где k (S) — число классов, получающихся при разбиении S, а с — некоторая положительная постоянная, характеризующая потери ис­ следователя при увеличении числа классов на единицу.

Другой вариант функционалов качества такого типа можно найти, например, в [10], где полагают

Весьма гибкой и достаточно общей схемой, реализующей идею одновременного учета двух функционалов, нам представляется схема, предложенная А. Н. Колмогоровым (см. сноску к стр. 83). Эта схема опирается на понятия меры концентрации Zr(S) точек, соответствую­

щей разбиению S, и средней меры внутриклассового рассеяния l[K) (S), характеризующей то же разбиение S.

90

Под мерой концентрации Zr (S) предлагается понимать величину

где V ( X i ) — число элементов в кластере, содержащем точку X t , а выбор числового параметра г находится в распоряжении исследователя и за­ висит от конкретных целей разбиения. При выборе г полезно иметь в виду следующие частные случаи Zr (S):

Заметим, что при любом г предложенная мера концентрации имеет

минимальное значение, равное , при разбиении исследуемого множе­

ства на п одноточечных кластеров и максимальное значение, равное 1, при объединении всех исходных наблюдений в один общий кластер.

При конструировании и сравнении различных кластер-процедур полезно иметь в виду, что объединение двух кластеров 5 г и S m в один дает прирост меры концентрации Zx (S), равный

Определение средней меры внутриклассового рассеяния l[K) (S) также опирается на понятие степенного среднего. В частности, пола­ гают

91