Метод оптимальной классификации одномерного упорядоченного множества на основе "склеивания с ближайшим"

Размещено на http://www.allbest.ru

Введение

Данная курсовая работа посвящена разработке на тему «Метод оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим».

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

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

Объектом изучения данного исследования является оптимальная классификация одномерного упорядоченного множества.

Предметом изучения данного исследования является метод оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим» и его программирование в среде Visual Studio 2013.

Цель данной работы - разработать метод оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим» и на его основе составить программу.

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

Изучить теоретические основы различных методов классификации данных;

Разработать метод оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим»;

Составить рабочую программу на основе алгоритмов классификации и провести вычислительные эксперименты по оценке эффективности их работы.

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

Во введении обоснована актуальность темы «метод оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим». упорядоченный множество алгоритм склеивание

Первый раздел - теоретическая часть, в которой раскрываются теоретические основы различных методов классификации.

Второй раздел имеет исследовательский характер. В нём приведены этапы разработки метода оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим».

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

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

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



1. Теоретические основы методов классификации

1.1 Понятие классификации

КЛАССИФИКАЦИЯ (от лат. Classis -- разряд, класс и facio -- делаю, раскладываю) -- общенаучное и общеметодологическое понятие, означающее такую форму систематизации знания, когда вся область изучаемых объектов представлена в виде системы классов, или групп, по которым эти объекты распределены на основании их сходства в определенных свойствах.

Классификация является результатом некоторого приближенного описания изучаемых явлений. С развитием знаний происходит уточнение и изменение классификаций [1].

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

Классифицирование проводится в следующих целях:

систематизация объектов некоторой области и фиксирование их свойств и отношений,

поиск упорядоченных объектов.



2. Разработка алгоритма оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим»

2.1 Основные положения алгоритма метода оптимального «склеивания» классов

Исходные данные:

- количество классов, на которые необходимо разбить упорядоченное множество Х,

- количество классифицируемых элементов в множестве Х,

, , - значения элементов упорядоченного множества Х.

Пусть I - количество классов после некоторого разбиения множества Х.

Информацию о разбиении на классы предлагается хранить в виде множества (), , где - содержит номер первого элемента в классе i.

Будем считать, что -ый «фиктивный» класс начинается с «фиктивного» элемента с номером ,

.

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

,

, .

Метод оптимального «склеивания» классов состоит в следующем.

Для выполнения очередного оптимального «склеивания» двух соседних классов необходимо:

1) Найти погрешности представления всех попарных объединений соседних классов.

2.2 Алгоритмы первоначального разбиения

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

Приведем листинг функции, реализующей указанное «простое» разбиение.

Листинг 1. Функция, реализующая алгоритм «простого» начального разбиения

//функция простого первоначального разбиения

//возвращает количество классов

int f_init0(int*n, int N0)

{

int i;

for (i = 0; i < (N0 + 1); i++)

{

n[i] = i;

}

return N0;

}

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

.

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

1) ширина класса должна быть не более заданной величины ,

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



3. Программная реализация метода оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим»

В качестве среды разработки [3, 4, 5] метода оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим» выбрана среда MSVisualStudio 2013.

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

3.1 Интерфейс программной реализации

«Метод оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим»» реализован в виде консольного приложения Win32 написанного на языке программирования С++ [6, 7].

Исходные данные о значениях элементов классифицируемого множества вводятся из файла.

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



Рисунок 3.1 - Ввод количества классов в окне консольного приложения «Метод оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим»»

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

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

Рисунок 3.2 - Вывод результатов классификации

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

После завершения расчетов в файл выводятся следующие результаты работы программы:

Количество элементов исходного множества;

Количество классов, на которое необходимо разбить исходное множество элементов;

Исходные элементы;

Номера первых элементов классов при оптимальной классификации;

Значения центров тяжести классов при оптимальной классификации;

Значения погрешностей центров тяжести классов при оптимальной классификации;

Номера первых элементов классов при равномерной классификации;

Значения центров тяжести классов при равномерной классификации;

Значения погрешностей центров тяжести классов при равномерной классификации;

Значения среднеквадратического отклонения при оптимальной и равномерной классификации.

3.2 Программная реализация основных функций метода оптимальной классификации

В ходе программной реализации основных функций работы метода оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим» в среде VisualStudio 2013 на языке С++ [8, 9] разработаны следующие фрагменты кода программы.

Приведём листинг подключения стандартных библиотек.

Листинг 4. Фрагмент программы подключения стандартных библиотек

#include "stdafx.h"

#include <iostream>

#include <fstream>

#include <math.h>

Функция, которая ищет «центр тяжести» одного класса, приведена в листинге 5.

Листинг 5. Функция, ищущая «центр тяжести» одного класса

//функция ищет центр тяжести одного класса

//возвращает координату центра

double f_centre1(int*n, double*x, int i)

{

double sum1;

int k;

sum1 = 0;

for (k = n[i]; k < n[i + 1]; k++)

{

sum1 = sum1 + x[k];

}

sum1 = sum1 / (n[i + 1] - n[i]);

return sum1;

}

Функция, которая ищет «центр тяжести» фиктивно объединённых двух классов, приведена в листинге 6.

Листинг 6. Функция, ищущая «центр тяжести» фиктивно объединённых двух классов

//функция ищет центр тяжести фиктивно объединённых двух классов

//возвращает координату центра

double f_centre2(int*n, double*x, int i)

{

double sum1;

int k;

sum1 = 0;

for (k = n[i]; k < n[i + 2]; k++)

{

sum1 = sum1 + x[k];

}

sum1 = sum1 / (n[i + 2] - n[i]);

return sum1;

}

Функция, которая считает погрешность аппроксимации одного класса, приведена в листинге 7.

Листинг 7. Функция, считающая погрешность аппроксимации одного класса

//функция считает погрешность аппроксимации одного класса

//возвращает значение погрешности

double f_error1(double y0, int*n, double*x, int i)

{

double sum2;

int k;

sum2 = 0;

for (k = n[i]; k < n[i + 1]; k++)

{

sum2 = sum2 + fabs(y0 - x[k]);

}

sum2 = sum2 / (n[i + 1] - n[i]);

return sum2;

}

Функция, которая считает погрешность аппроксимации двух классов, приведена в листинге 8.

Листинг 8. Функция, считающая погрешность аппроксимации двух классов

//функция считает погрешность аппроксимации двух классов

//возвращает значение погрешности

double f_error2(double y0, int*n, double*x, int i)

{

double sum2;

int k;

sum2 = 0;

for (k = n[i]; k < n[i + 2]; k++)

{

sum2 = sum2 + fabs(y0 - x[k]);

}

sum2 = sum2 / (n[i + 2] - n[i]);

return sum2;

}

Функция, которая вычисляет сумму квадратов всех элементов множества Х, приведена в листинге 9.

Листинг 9. Функция, вычисляющая сумму квадратов всех элементов множества Х

//функция вычисляет сумму квадратов всех элементов множества Х

//возвращает сумму квадратов всех элементов множества Х

double f_sum2(int N0, double*x)

{

int k;

double sumX2;

sumX2 = 0;

for (k = 0; k<N0; k++)

{

sumX2 = sumX2 + pow(x[k], 2);

}

return sumX2;

}

Функция, которая ищет минимальное значение sMin1 и его номер iMin1 в массиве s длиной n, приведена в листинге 10.

Листинг 10. Функция, ищущая минимальное значение sMin1 и его номер iMin1 в массиве s длиной n

//функция ищет минимальное значение sMin1 и его номер iMin1 в массиве s длиной n

//возвращает sMin1 и iMin1

int f_Min(double *s, int n, double *sMin1)

{

//double sMin1;

int iMin1, i;

iMin1 = 0;

*sMin1 = s[iMin1];

for (i = 1; i < n; i++)

{

if (s[i] < *sMin1)

{

*sMin1 = s[i];

iMin1=i ;

}

}

return iMin1;

}

Функция, которая считает погрешность аппроксимации при равномерном разбиении, приведена в листинге 11.

Листинг 11. Функция, считающая погрешность аппроксимации при равномерном разбиении

//функция считает погрешность аппроксимации при равномерном разбиении

//возвращает значение погрешности

double f_error3(int N1, int N0, double sumX2, int*nC, double*yC, double*x)

{

int i, k;

double sum1, sReg;

sum1 = 0;

for (i = 0; i<N1; i++)

{

for (k = nC[i]; k<nC[i + 1]; k++)

{

sum1 = sum1 + pow(yC[i] - x[k], 2);

}

}

sReg = sqrt(sum1 / sumX2);//погрешность

return sReg;

}

Полный листинг кода программы, реализующей метод оптимальной классификации, приведён в приложении 2.

3.3 Проверка работоспособности программы

Для проверки работоспособности были приведены следующие расчеты.

Исходные данные о значениях элементов классифицируемого множества вводятся из файла Test2.txt (рисунок 3.3).

Рисунок 3.3 - Файл с исходными данными

В данном файле находятся 10 исходных элементов.

В окне консольного приложения вводится количество классов, на которое необходимо разбить исходное множество элементов (вводится число 5). Затем в окне консольного приложения выводятся исходные данные, введенные из файла, и их количество (рисунок 3.4).

Рисунок 3.4 - Ввод количества классов в окне консольного приложения «Метод оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим»»

После выполнения расчетов по классификации в окне консольного приложения выводятся значения центров тяжести 5 классов - yOpt[i], i=0,1,2,3,4, погрешность представления исходных данных в каждом классе при оптимальном разбиении - s[i], i=0,1,2,3,4, значения среднеквадратического отклонения при оптимальной sOpt и равномерной sReg классификации (рисунок 3.5).

Рисунок 3.5 - Вывод результатов классификации

После завершения расчетов в файл TestOut1.txt выводятся результаты работы программы.

Приведём фрагменты файла с результатами работы данной программы.

В файл TestOut1.txt выводится количество элементов исходного множества:

N0= 10

В файл TestOut1.txt выводится количество классов, на которое необходимо разбить исходное множество элементов:

N1= 5

В файл TestOut1.txt выводятся исходные элементы:

1

3

4

7

8

10

11

12

13

20

В файл TestOut1.txt выводятся номера первых элементов классов при оптимальной классификации:

n=

0

3

5

7

9

10

В файл TestOut1.txt выводятся значения центров тяжести классов при оптимальной классификации:

Step End: yOpt

2.66667

7.5

10.5

12.5

20

В файл TestOut1.txt выводятся значения погрешностей центров тяжести классов при оптимальной классификации:

Step End: s

1.11111

0.5

0.5

0.5

0

В файл TestOut1.txt выводятся номера первых элементов классов при равномерной классификации:

nC=

0

3

5

8

9

10

В файл TestOut1.txt выводятся значения центров тяжести классов при равномерной классификации:

yC

2.9

6.7

10.5

14.3

18.1

В файл TestOut1.txt выводятся значения погрешностей центров тяжести классов при равномерной классификации:

sC

1.03333

0.8

0.833333

1.3

1.9

В файл TestOut1.txt выводятся Значения среднеквадратического отклонения при оптимальной и равномерной классификации.

sOpt= 0.0758098

sReg= 0.116887

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

3.4 Оценивание эффективности метода оптимальной классификации

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



Заключение

При выполнении курсовой работы цели и задачи выполнены в полном объёме.

Был приведён краткий обзор методов классификации. Рассмотрены методы классификации: иерархическая классификация, FOREL (Формальный Элемент), метод k-medians, алгоритм КРАБ, равномерная классификация. На основе проведенного анализа характеристик известных методов классификации можно утверждать, что основным недостатком большинства методов классификации является ограничение на количество элементов классифицируемого множества.

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

В курсовой работе приведена реализация программы «Метод оптимальной классификации одномерного упорядоченного множества на основе «склеивания с ближайшим». Обоснован выбор среды разработки MSVisualStudio 2013. Описан интерфейс и выполнена проверка работы программы. Также были проведены вычислительные эксперименты по оценке эффективности работы алгоритма оптимальной классификации. Для сравнения эффективности применения разработанного метода оптимальной классификации на основе «склеивания с ближайшим» был использован метод равномерной классификации. Сравнение проводилось на примере изображения в оттенках серого. Предоставленные расчёты продемонстрировали работоспособность метода оптимальной классификации и показали преимущество в точности аппроксимации (значение среднеквадратического отклонения) разработанного метода оптимальной классификации по сравнению с методом равномерной классификации.

Список использованных источников

Елисеева И., Рукавишников В. Группировка, корреляция, распознавание образов (статистические методы классификации и измерения связей). - М.: Статистика, 1977. - 144 с.

Князев Е., Шопырин Д. Методы автоматизированной классификации изменений программного кода. - М.: LAP Lambert Academic Publishing, 2011. - 136 с.

Пахомов Б. C/C++ и MS Visual C++ 2010 для начинающих. - СПб.: БХВ-Петербург, 2010. - 711 с.

Мартынов Н.Н. Программирование для Windows на C/C++. В 2 томах. Том 1. - М.: Бином, 2012. - 528 с.

Мартынов Н.Н. Программирование для Windows на С/С++. В 2 томах. Том 2. - М.: Бином-Пресс, 2013. - 480 с.

Архангельский А.Я. Язык С++ в С++Builder. - М.: Бином-Пресс, 2008. - 944 с.

Архангельский А.Я. Програмирование в С++ Builder 6. - М.: ООО «Бином-Пресс», 2005. - 1168 с.

Страуструп Б. Язык программирования С++. - М.: Бином, 2011. - 1136 с.

Фридман А.Л. Язык программирования Си++. Курс лекций. - М.: Интернет-университет информационных технологий, 2010. - 264 с.

Красильников Н.Н. Цифровая обработка 2D- и 3D-изображений. - СПб.: БХВ-Петербург, 2011. - 608 с.

Гонсалес Р., Вудс Р. Цифровая обработка изображений. - М.: Техносфера, 2012. - 1104 с.

Сэломон Д. Сжатие данных, изображений и звука. - М.: Техносфера, 2006. - 386 с.

Размещено на Allbest.ru