Глава 2. Обработка гиперспектральных данных с использованием алгоритмов обучения без учителя

2. 1. Метод k внутригрупповых средних с использованием метода минимальной длины описания

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

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

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

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

Задача сводится к объединению образов из обучающей выборки в группы, на основе которых составляются классы, т.к. решающее правило устанавливает соответствие между каждым образом и одним из классов. Приведенное выше объединение называется группированием [7].

Исходя из вышесказанного, возникает вопрос: основываясь, на чем одни образы мы относим к одному классу, а другие к другому?

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

Рассмотрим один из алгоритмов кластеризации, а конкретнее алгоритм k средних. На вход данному алгоритму подается число кластеров, обозначим их переменной k и , как множество классов.

Пошаговое описание алгоритма:

1. Для каждого из k кластеров случайным образом выбираются их центры, в данном случае они же являются эталонными образами . Центрами являются случайно выбранные k образов из обучающей выборки

(1)

2. Каждый объект обучающей выборки относим в тот кластер, расстояние до которого минимально:

(2)

3. Далее пересчитываем центры кластеров, основываясь на том, к какому центру какие образы были отнесены:

(3)

где – количество образов содержащихся в классе .

4. Повторяем пункт 2 и 3 до тех пор, пока классы не перестанут изменяться, т.е. пока не будет достигнута сходимость.

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

Рассмотрим принцип МДО применительно к методу k средних.

Ниже перечислены компоненты, которые необходимы для описания модели:

1. Оптимальная точность, с которой мы выполняем дискретизацию пространства параметров для кодирования параметров нашей модели. , где M – количество элементов в обучающей выборке.

2. Число кластеров k, для кодирования которых необходимо бит.

3. Общее число параметров модели равное Nk.

Общая длина описания модели:

(4)

Определим каждый образ из обучающей выборки следующим образом:

1. Номер центра класса, который лежит рядом для обозначения, которого необходимо бит.

2. Вектор разности, представленный в виде и ее длина описания

(5)

,где С – некая константа, обозначающая точность кодирования векторов.

Исходя из всего вышеперечисленного, длина описания данных исследуемой модели равна:

(6)

Конечный критерий с применением принципа МДО будет:

(7)

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