1) Проблема выбора информативных признаков

Формирование признаковых описаний случайных сигналов различной природы в задачах классификации можно рассматривать как отображение сигнала из некоторого функционального пространства, элементами которого являются реализации S(t), в векторное пространство _i, i=,элементы которого называются признаками. Размерность исходного пространства_i может быть велика, что вызывает необходимость анализа исходных описаний сцелью выявления действительно информативных элементов и сокращения размерности. При анализе описаний сигналов в общем случае в качестве признаков целесообразно рассматривать совокупность множеств точек отрезковчисловой оси, отражающих степень выраженности различных свойств этих сигналов. Значениям признаковхарактеризующим сигналS_j(t), ставится в соответствие некоторый набор элементов множеств _i. Тогда и существует совокупность последовательностей признаковS_j= (), описывающих любой элемент из множества сигналовS₁(t), S₂(t), ... ,S_m(t) при распознавании (классификации).

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

1. методы выбора в пространстве измерений

- Суть: выбор признаков производится путем сокращения размерности исходного описания по критерию, минимизирующему ошибку классификации

-собственно методы группы:

- - методы, основанные на мерах расстояний, мерах зависимостей и мерах по евклидовым расстояниям

2) методы выбора в преобразованных пространствах

- Суть: анализируется вся информация в пространстве _i, из которого в другом пространстве получается минимизированное описание

- методы группы:

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

-- методы, основанные на мерах разделимости, разложении Карунена-Лоэва, неортогональных преобразованиях

Общими недостатками методов обеих групп являются весьма значительный объем вычислений при решении практических задач, использование априорных вероятностей классов или функций распределения собственных областей в пространстве _i либо необходимость соблюдения трудновыполнимых ограничений и др.

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

2. Методы оценки информативности.

Рассмотрим два класса объектов К₁иК₂, каждый из которых представлен выборками признаковых описаний реализаций сигналовS_j=(), j =причем положим, что классК₁составляют описания реализаций с номерамиj=1,2,...,r₁, а классК₂ - j = r₁+1, r₁+2, ..., r₁+r₂; r₁+r₂=r.

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

- меру, служащую одномерным критерием адекватности i-го признака для разделения двух классов и соответствующую критерию Фишера:

выборочное среднее значение_iдля классаК₁

- выборочное стандартное отклонение для классаК₁, а для классаК₂значенияиопределяются аналогично при

- меру, характеризующую относительное нормированное различие между классами по средним значениям признаков:

где

- меру, основанную на применении концепции дивергенции:

и– дисперсии.

Для случая L классов (L>2) приведенные формулы позволяют получить значения мер для любой пары сравниваемых классов. Осредненные значения мер для всех классов получаются взвешенным суммированием, например

Аналогичным образом вычисляются оценки .

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

Основные цели

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

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

Области применения

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

Медицина: кластеризация болезней, методов лечения или симптомов (определение кластеров симптомов шизофрении в психиатрии).

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

Расстояния между образами

При формировании кластеров используется несходство (или расстояние) между объектами. Эти расстояния могут быть определены для одного или нескольких измерений. Например, если нам нужно классифицировать гамбургеры, мы можем принять во внимание количество калорий, их содержание, цену, субъективные оценки вкуса, и т.д.

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

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

Наиболее часто используемый тип расстояния. Является простым геометрическим расстоянием в многомерном пространстве и вычисляется следующим образом:

dist (x, y) =

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

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

dist(x, y) =

Покоординатное расстояние

Это расстояние в некотором смысле усредняет разницу между различными компонентами векторов. В большинстве случаев, эта мера расстояния дает результаты, подобные простому евклидову расстоянию. Однако, отметим, что при данной мере, эффект привносимый отдельными большими компонентами демпфируется (так как они не возводятся в квадрат). Покоординатное расстояние вычисляется так:

dist(x, y) =

Расстояние Чебышева

Эта мера расстояния может подойти в случае, когда нам потребуется определить два объекта как различные, если они различны хотя бы по одному измерению. Чебышево расстояние вычисляется как:

dist(x,y) =

Степенное расстояние

Иногда может потребоваться увеличить или уменьшить вес увеличения расстояний по измерениям. Это может быть достигнуто путем использования степенного расстояния. Расстояние это вычисляется как:

dist(x, y) =

21. Кластерный анализ. Алгоритм иерархической группировки.

Определения

Рассмотрим последовательность разделений n выборок на c групп. Первое из них - это разделение на n групп, причем каждая из групп содержит точно по одной выборке. Следующее разделение на n-1 групп, затем на n-2 и т.д. до n-го, в котором все выборки образуют одну группу. Будем говорить, что находимся на k-ом уровне в последовательности, когда c = n - k+1. Таким образом, первый уровень соответствует n-группам, а n-й одной группе. Если даны две любые выборки x и x’ , на некотором уровне они будут собраны в одну группу. Если последовательность обладает тем свойством, что, когда две выборки попадают в одну группу на уровне k, они остаются вместе на более высоких уровнях, то такая последовательность называется иерархической группировкой.

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

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

Формальное описание алгоритма

c - желаемое число кластеров

n - количество элементов выборки

,..., - исходная выборка

- разбиение на i-м шаге

1. ; k:=0

2. Имеем

Вычислим матрицу взаимных расстояний ^(k)между классами и найдем пару классов

т.ч.:

3) Пусть тогда положим

4. k:=k+1

4. Если k<n-c,то переход на п.2, иначе - конец иерархической группировки.

21. Кластерный анализ. Метод K-внутригрупповых средних.

Общая логика

Этот метод кластеризации весьма сильно отличается от алгоритмов иерхической группировки и двунаправленного объединения. Предположим, что у вас уже есть гипотеза относительно числа кластеров в ваших значениях или переменных. Можно просто потребовать, чтобы компьютер формировал точно 3 кластера, которые должны быть различны насколько возможно. Вопрос именно такого типа может разрешить алгоритм k-внутригрупповых средних. Вообще, данный метод формирует ровно k различных кластеров, наиболее “удаленных” друг от друга.

Пример

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

Вычисления

С вычислительной точки зрения, этот метод похож на анализ вариации "наоборот". Программа начинает работу с k произвольными кластерами, и затем перемещает объекты между этими кластерами с целью (1) минимизации разброса внутри кластера, и (2) максимизации разброса между кластерами. Данные разброса являются стандартным выходом алгоритма.

Интерпретация результатов

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

Формальное описание

C - число кластеров

1. Выберем случайным образом некоторое начальное разбиение

где

приi  j

2) Построено k-е разбиение

Вычислим набор средних , где

3) Построим максимальное дистанционное разбиение, порождаемое набором и возьмем его в качестве. Это делается из следующих соображений:

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

для 1lc

4) Если , то переход на п.2 и m:=m+1, иначе - конец алгоритма.

65