Методы классификации. Алгоритмы классификации.

Системы классификации, построенные с использованием методов обучения, реализуются с помощью различных алгоритмов, в большей или меньшей степени эвристических. Среди множества таких алгоритмов рассмотрим три: алгоритм максимина, алгоритм К-средних, алгоритм ИЗОДАТА.

Алгоритм максимина

Алгоритм Максимина используют для автоматического нахождения экземпляров классов на базе обучающей выборки объёмом и распределения образов по классам. При этом неизвестны, ни количество классов, ни экземпляры классов. Идея данного алгоритма заключается в следующем. В качестве экземпляра первого класса выбирают произвольно один из образов. Пусть это будет образ . Вычисляют расстояния между экземпляром первого класса и всеми оставшимися образами - . Среди этих расстояний найдем наибольшее

.

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

Рассмотрим словесное описание этого алгоритма.

Шаг 1. Задать количество образов в выборке - и значения их существенных признаков. Выбрать метрику для вычисления расстояний.

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

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

.

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

Шаг 4. Вычислить величину порогового расстояния, равную половине расстояния между экземплярами классов и :

.

Шаг 5. Увеличить число классов на единицу: .

Шаг 6. Выбрать образ в качестве экземпляра следующего класса .

Шаг 7. Вычислить расстояния между экземплярами классов и всеми оставшимися образами

Шаг 8. Найти наименьшие расстояния между образом и экземплярами классов : и упорядочить их в порядке убывания. Установить количество образов, которые не являются экземплярами классов , и положить .

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

Шаг 10. Если , то алгоритм закончен.

Шаг 11. Из массива определить номер образа и номер класса. Отнести образ к классу , т.е. . Увеличить счетчик классифицированных образов на единицу и перейти к шагу 10.

Задача классификации считается выполненной, если количество экземпляров классов не изменяется, а все образы распределены по классам.

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

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

Первая – это таблица значений существенных признаков объектов (номер строки – номер объекта номер столбца – номер существенного признака).

Y (i,j)

Вторая таблица – таблица пометок объектов. Если объект – это экземпляр класса, то ему присваивают отрицательную пометку (номер экземпляра класса с отрицательным знаком) или положительную пометку равную номеру класса, к которому отнесён данный объект.

Pm (i)

Третья таблица – это расстояния в выбранной метрике между экземплярами классов и непомеченными объектами.

	d (i,j)

 

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

Номер строки таблицы – это порядковый номер экземпляра класса; первый столбец – значение минимального расстояния; второй столбец – порядковый номер непомеченного объекта, который находится на минимальном расстоянии от данного экземпляра класса; третий столбец – номер этого класса.

Выберем в качестве экземпляра первого класса первый объект: . В таблице пометок, первому элементу присвоим пометку .

Pm (i)
-1

Вычислим расстояния между экземпляром класса k=1 и всеми непомеченными объектами с номерами в метрике Манхеттена.

Занесем полученные расстояния в таблицу .

d (i,j)
№ об. № кл.

Находим наибольшее расстояние между экземпляром класса и непомеченными объектами

,

запоминаем номер этого объекта .

Выберем этот объект в качестве экземпляра следующего класса . Присвоим объекту пометку .

Pm (i)
-1			-2

 

Вычислим пороговое значение расстояния

.

Вычислим расстояния между экземпляром нового класса и всеми непомеченными объектами и занесем данные в таблицу

 

 

d (i,j)
№ об. № кл.

Для всех объектов находим наименьшие расстояния между непомеченным объектом экземплярами классов:

Занесем эти расстояния, номера соответствующих объектов и классов в таблицу . В рассматриваемом примере - это

, , , , , ...

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

 

Сравним с порогом. Если значение , то увеличим количество классов на единицу и объекту с номером присвоим пометку

.

Таблица пометок будет иметь вид

Pm (i)
-1			-2		-3

Уточним значение порогового расстояния

.

Тогда

.

Вычисляем расстояния от экземпляра класса до всех непомеченных объектов.

d (i,j)
№ об. № кл.

 

Находим наименьшие расстояния между непомеченными объектами и экземплярами классов: .Упорядочим их в порядке убывания и занесем в таблицу

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

Pm (i)
-1			-2		-3

 

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

Алгоритм К-средних

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

Алгоритм К-средних отличается от алгоритма Максимина, в первую очередь тем, что заранее известно или задано количество классов . В качестве представителей этих классов могут использовать либо первых элементов из обучающей выборки, либо любые элементов. Классификации в этом случае заключается в поиске центров заданного количества классов . Установив центры классов необходимо провести первый этап классификации, который заключается в распределении объектов обучающей выборке по заданным классам по принципу наименьшего расстояния. Это означает, что объект относят к тому классу, для которого является наименьшим. Распределив все объекты обучающей выборки по классам, находят новые центры классов. Новые положения центров классов в пространстве существенных признаков определяют из условия минимума среднеквадратического отклонения объектов данного класса от его центра

здесь - вектор соответствующий центру -го класса.

Отсюда следует что положение центра -того класса определяется из соотношения

.

Тогда получим, что

,

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

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

Рассмотрим словесное описание алгоритма К–средних. Он состоит из следующих шагов.

Шаг 1. Задать количество классов и параметр .

Шаг 2. На первой итерации () выбирают в качестве экземпляров классов первые элементов обучающей выборки:

Шаг 3. Распределить объекты обучающей выборки по классам. Классы формируют следующим образом. Пусть необходимо установить к какому из классов принадлежит объект . Вычислим расстояния между данным объектом и центрами классов в выбранной метрике (например, пусть это будет метрика Евклида)

.

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

,

запомним соответствующий номер класса - . Отнесем объект к классу с номером . Классы считаются сформированными, если обработаны все объекты обучающей выборки.

Шаг 4. Положить и вычислить новые положения центров классов

,

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

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

.

Если при этом выполняется условие

,

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

нужно вернуться к шагу 3.

Рассмотрим реализацию этого алгоритма на примере, когда количество объектов равно , а количество существенных признаков равно .

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

Y (i,j)

Вторая таблица – таблица пометок объектов. Если объект – это центр класса, то ему присваивают отрицательную пометку (номер класса с отрицательным знаком) или положительную пометку равную номеру класса, к которому отнесён данный объект.

Pm (i)

Третья таблица - это расстояния в выбранной метрике между координатами центров классов и непомеченными объектами.

 

d (i,j)
№ об. № кл.

 

Четвертая таблица – координаты центров классов.

N (i,j)
j i

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

N (i,j)
j i

и присвоим им отрицательные пометки в таблице пометок

Pm (i)
-1	-2	-3

Вычислим расстояние между центрами классов и всеми непомеченными объектами (в метрике Манхэттена).

d (i,j)

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

Pm (i)
-1	-2	-3

Здесь объекту с номером присваивается положительная пометка, равная номеру класса, расстояние до которого от данного объекта минимально.

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

.

В координатном представлении:

.

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

Найдем расстояния между новыми и предыдущими центрами одноименных классов:

, и .

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

Для второго центра координаты не изменились, поэтому его пометку не изменяем.

Pm (i,j)
	-2

 

Занесем новые координаты центров в соответствующую таблицу.

N (i,j)
j i

Обнуляем все положительные пометки. В данном случае таблица пометок примет вид:

Pm (i,j)
	-2

Вычисляем расстояния между центрами классов и непомеченными объектами

d (i,j)

Находим наименьшие расстояния в столбцах этой таблицы. Классифицируем объекты и заполняем таблицу пометок

Pm (i)
	-2

 

Вычисляем новые координаты центров , , , сравниваем их с предыдущими значениями. Положение центра изменилось и его предыдущая пометка отрицательная, поэтому изменим ее знак: .

Pm (i)

 

Заносим координаты новых центров в таблицу, если они изменились

N (i,j)

Координаты центров поменялись, выполняем следующую итерацию. Обнуляем все положительные пометки.

Pm (i)

Вычисляем расстояния от новых центров классов до всех объектов

d (i,j)

Классифицируем объекты:

Pm (i)

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

N (i,j)

Поскольку координаты центров не изменились, то алгоритм закончен. Таблица пометок содержит всю информацию о распределении объектов между классами.