19.2. Проекционные индексы, подходящие для выделения кластеров

19.2.1. Смеси эллипсоидально симметричных распределений как модель кластерной структуры.

Будем предполагать, что плотность распределения , генерирующего выборку представляет собой смесь унимодальных эллиптически симметричных плотностей

(19.2)

где

— нормирующая константа; — веса компонента смеси; — некоторая неотрицательная, монотонно убывающая при функция — вектор средних компоненты смеси; W — невырожденная матрица ковариаций (внутрикомпонентного рассеивания), одинаковая для всех компонент.

В частности, если , то будет плотностью нормального распределения. (Некоторые другие примеры плотностей приведены в § 20.1.)

Смесь плотностей вида (19.2), (19.2) можно рассматривать как одну из возможных моделей для описания кластерной структуры. Плотность имеет k модальных значений (если компоненты смеси достаточно разнесены), и точки в окрестности какой-либо модальной точки можно считать относящимися к одному и тому же кластеру.

Матрицу ковариаций для случайного вектора с плотностью можно представить в виде , где — матрица межкомпонентного рассеивания

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

Пусть теперь — некоторая одномерная проекция. Плотность случайной величины z есть А-компонентная смесь симметричных унимодальных распределений

где

Дисперсия z равна где — величина межкомпонентного разброса для z, т. е. Введем отношение

которое можно рассматривать как меру различия компонент смеси для одномерной проекции, задаваемой вектором

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

19.2.2. Дискриминантное подпространство.

В дискриминантном анализе используются так называемые канонические переменные (см. [129]), где векторы суть собственные векторы с положительными собственными значениями задачи . Число и зависит от геометрической конфигурации векторов средних . В частности, если центры компонент смеси лежат на одной прямой, то . Векторы V, будут В-ортогональными, W — ортогональными, и, следовательно, - ортогональными. Величина собственного числа t, равна значению т. е. отношения (19.3) для направления проецирования

Подпространство называется дискриминантным подпространством (ДП) и содержит полную информацию о различиях среди компонент смеси (19.2), другое эквивалентное определение этого подпространства будет:

В связи с вышесказанным следует, что проекционные векторы для ЦП (в рамках модели (19.2), (19.2)) должны принадлежать

Оценка ДП является одной из задач дискриминантного анализа. Однако в ДА считается, что известны или могут быть оценены обе матрицы В и W. Оценка матрицы W производится по обучающим выборкам (ОВ), т. е. в дискриминантном анализе матрица должна быть разбита на k подматриц XV относительно объектов (наблюдений), из которых известно, что они принадлежат компоненте смеси (19.2).

Если же ОВ нет, то может быть оценена только матрица и приходится использовать другие подходы.

19.2.3. Проекционные индексы, использующие математическое ожидание монотонных функций плотности одномерной проекции.

Рассмотрим однопараметрическое семейство проекционных индексов (ПИ) для одномерных проекций, задаваемых вектором

где — оператор математического ожидания по плотности .

Приведем без доказательств неравенства, связывающие значение и отношение в рамках модели (19.2):

где константа не зависит от U.

В частности, если имелась смесь нормальных распределений, то

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

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

Пример 19.1. Приведем выражение для вычисления в случае смеси нормальных распределений при

Для нормальной плотности величина .

Когда , критерий (19.4) переходит в энтропийный критерий

Все приведенные выше эвристические соображения могут быть применимы и к (19.6).

Замечание. Можно использовать и отрицательные значения Р в (19.4). Тогда, однако, нужно либо искать направления U, минимизирующие величину либо переходить к ПИ вида или и снова решать для последних задачу на максимальное значение.

19.2.4. Проекционные индексы, основанные на использовании моментов третьего и четвертого порядков.

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

Дальше всюду, без ограничения общности, будем считать данные центрированными, т. е. полагать тогда

Из выражения (19.7) видно, что отличие от нуля обусловлено только несовпадением средних значений компонент смеси Конечно, даже при несовпадении средних может быть равен 0 для любой проекции, например, для любой проекции двухкомпонентной смеси с равными весами

В качестве ПИ в решении максимизационной задачи целесообразнее использовать не сам третий момент, а коэффициент асимметрии. Хотя возможно и непосредственное использование для восстановления дискриминантного подпространства (см. п. 19.3.2).

Использование четвертого момента и связанного с ним коэффициента эксцесса как ПИ основано на том соображении, что если имеется смесь нормальных плотностей, проекциям, на которых компоненты смеси не разделены, соответствует нулевое значение коэффициента эксцесса Для выделения выразительных проекций, вообще говоря, следует решать две задачи — искать как проекции, доставляющие максимум так и проекции, доставляющие минимум. Выражение для четвертого момента одномерной проекции имеет вид:

Константа с зависит только от функции . В частности, для нормального распределения с Коэффициент эксцесса тесно связан с ПИ, предложенными Краскалом в работе [259).

где дисперсия расстояний в степени а между точками из — среднее значение степеней расстояний Т. е. икраск — это коэффициент вариации степеней расстояний.

Дж. В. Краскал предлагал использовать значения в частности . Однако, как показывает опыт практического использования таких ПИ, на самом деле более эффективно использовать Легко показать, что при a . Как и при использовании моментов третьего порядка, для восстановления дискриминантного подпространства не обязательно решать оптимизационную задач) с Альтернативный подход используется в п. 19.3.2.

19.2.5. Проекционные индексы, основанные на распределении разностных векторов.

В задачах кластерного анализа и разделения смесей важной характеристикой структуры данных является распределение разностного вектора

Предположим, что -мерный случайный вектор X имеет плотность распределения . Введем ПИ

где Плотность распределения случайной величины имеет вид:

Следовательно,

где — плотность равномерного распределения на интервале . Таким образом, является оценкой и при при

В случае, когда имеется матрица данных в качестве оценки значения ПИ естественно взять частоту встречаемости пар векторов таких, что где s - выборочное стандартное отклонение.

Обратим внимание, что указанную оценку для ПИ можно использовать для поиска и -мерных выразительных проекций

Выборочное значение ПИ дает оценку значения ПИ Q, (19.4) и тем самым еще одну содержательную интерпретацию ПИ . Покажем, что соответствующая интерпретация ПИ существует и для всех целых

Пусть выборка из генеральной совокупности случайного вектора X с плотностью . Введем проекционный индекс

где — произвольное целое;

— объем единичного шара в -мерном пространстве.

Плотность распределения -мерной случайной величины сосредоточена на подпространстве, задаваемом уравнением и имеет вид:

Следовательно,

где -плотность равномерного распределения в шаре с центром , радиуса а в подпространстве . В случае, когда задана матрица выборочной оценкой значения ПИ является частота встречаемости в данной выборке объема подвыборок объема , стандартное отклонение которых не превосходит где s — стандартное отклонение всей выборки. Те же рассуждения, что и выше, показывают, что выборочное значение ПИ дает оценку значения ПИ