Статистические модели группировки

основываются на вероятностной
оценки наших данных , при этом мы

Для каждой группы задается априорная вероятность Р1,Р2 ,…Рс

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

Общая функция плотности вероятности определяется следующим образом:

Мы имеем объекты, которые описываются моделью конечной смеси - это и есть

некоторый многомерный параметр, которым описывается конечная смесь.
Статистические модели группировки
(С;

)=

- многомерный параметр.

Мы должны оценить вектор этого многомерного параметра.

Каждый максимум соответствует некоторому параметру этой смеси.

Восстановить эти параметры можно из условия:

если из этого условия однозначно

С=С1

2)

В общем виде эта задача решается как задача оценки многомерного параметра.
Лучше всего решать ее по методу максимального правдоподобия

С - известно.
Строится функция правдоподобия:

Статистические модели группировки

достаточно сложная .
Аналитическое решение получить достаточно сложно.
В основном

Для случаев нормального распределения и когда С- известно эту задачу можно
решать приближенно более простым способом (например методом к-средних).

Метод к-средних позволяет найти центры соответствующих локальных
максимумов:

Находим mi i =1..C

2) Разбиваем выборку

на кластеры

разбиение на кластеры
Статистические модели группировки
3) Мы должны для любого

, где

-матрица ковариации

В результате этой деятельности мы для каждого кластера получаем следующее:

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

некоего распределения. Далее функцию сложной плотности можно представить в виде

Статистические модели группировки

Статистическое решающее правило можно представить в следующем виде:

Есть 2 способа провести классификацию:
- отношение правдоподобия
- классификация по минимуму расстояния

? расстояние Махланобиса.

классификации, использующий кластер-анализ для
формирования подклассов “сложного класса”.
Алгоритм ориентирован

Пусть имеется некоторый класс

Предполагаем, что он может быть представлен в виде

где

- подклассы, рассматриваемые как кластеры.

Пусть

- плотность распределения, соответствующая классу

- условная плотность распределения, соответствующая подклассу

- априорная вероятность появления объектов из подкласса

Тогда плотность вероятности распределения будет иметь вид

максимумы функции
Поэтому цель кластеризации - определить совместную плотность распределения,

Алгоритм автоматической классификации на основе
кластер-анализа

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

Обозначив через

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

, минимизирующего функционал

оптимальное значение вектора

Последнее значение может быть получено по предъявленной

Найдя

можно легко определить функцию

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

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

Поэтому был предложен несколько модифицированный алгоритм класса ISODATA,
получивший название алгоритм "адаптивного выбора подклассов" (АВП).

подклассов.

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

Процесс кластер-анализа заключается в попытке аппроксимации функции
совместной плотности распределения

с помощью смеси нормальных плотностей распределения каждая компонента
этой смеси представляется в виде

- вектор математического ожидания i-кластера;

- матрица ковариации i-кластера;

- размерность вектора классификационных признаков;

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

В соответствии с этим каждая нормальная компонента смеси представляется в виде

- компоненты вектора

- диагональные элементы ковариационной матрицы

цель классификации будет достигнута, если будут получены оценки параметров

окончания обучения обеспечивается вычисление
полной ковариационной матрицы соответствующих кластеров
Введем

Мода с номером

1)

Модой будем называть область векторов в пространстве признаков

близких к

В качестве метрики используется квадрат эвклидова расстояния

2)

Моду с номером

будем называть свободной, если ее параметр

мода

свободна при

- Число векторов, входящих в моду.

а через вектор

вторых моментов
-ой моды
5)
Кластер
и таксон

есть синоним термина мода

Алгоритм “адаптивного выбора подклассов”

в следующем.
Пусть на вход АВП поступили первые

векторов обучающей

Так как у нас на начальном этапе имеется

то указанные вектора становятся начальными векторами мод

свободных мод,

для

Начиная с

алгоритм выходит на поиск ближайшей к данному вектору

-го вектора

моды

Алгоритм “адаптивного выбора подклассов”

происходит уточнение параметров данной моды по формулам
в указанную моду,



и

Алгоритм “адаптивного выбора подклассов”

мод


и

Если вектор

ближе к

чем к

и


то происходит

и корректируется порог моды

В противном случае производится объединение двух ближайших мод

и

Алгоритм “адаптивного выбора подклассов”

по формуле

Освободившаяся мода с номером
становится центром вновь формируемой

моды

Алгоритм “адаптивного выбора подклассов”

всех

векторов обучающей выборки
происходит оценка дисперсий кластеров

и вероятностей кластеров



Выявляются

Состоятельные кластеры перенумеровываются в порядке

И начинается второй этап итерации по обучающей выборке с целью уточнения
оценок параметров кластеров.

Алгоритм “адаптивного выбора подклассов”

кластера производится предварительная классификация векторов
обучающей выборки с целью выявления

если выполняется условие

где

Определяется уточненное значение центра кластера

Алгоритм “адаптивного выбора подклассов”

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

Сформированное множество состоятельных кластеров формирует алфавит
подклассов

соответственно отнесение некоторого вектора

к подклассу

может быть выполнено с использованием принципа максимальной апостериорной
вероятности по следующему правилу:

Алгоритм “адаптивного выбора подклассов”

может быть использован в нескольких вариантах:
Задана априорная классификация распознаваемых объектов

1)

Задача состоит в нахождении подклассов в каждом классе

с помощью

алгоритма АВП. Далее классификация объекта осуществляется по критерию
минимального расстояния

Алгоритм “адаптивного выбора подклассов”

задача эквивалентна обычной задаче кластеризации данных
(или “обучение без учителя”

Алгоритм “адаптивного выбора подклассов”