Исследование и анализ трудоемкости алгоритмов концептуальной классификации

№58-4,

физико-математические науки

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

Похожие материалы

Введение

Огромный объем данных, который постоянно используется в современном мире требует специальных методов обработки [5, 6]. Цель каждой обработки – это анализ и получение каких - либо выводов. Удобным методом для работы с огромными объемами является классификация. Ее задача из множества единичных объектов получить конечные множества, которые объединяют эти единичные объекты по определенным признакам. Так как в большинстве случаев в процессе классификации объектов исследователь как правило не обладает полным знанием и объем выборки ограничен, то следует обратить внимание на те алгоритмы, которые способны решить данную проблему. С этой задачей хорошо справляются концептуальные алгоритмы, то есть алгоритмы, использующие в своей основе априорные вероятности [2]. Это дает им неоспоримые преимущества перед классическими алгоритмами.

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

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

Постановка задачи

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

Большим достоинством классификации является то, что она позволяет выполнить разбиение объектов не по одному заданному параметру, а по заданному набору признаков. Недостатком данного подхода является четкое задание классов, на которые необходимо разбить данные. Но концептуальные алгоритмы позволяют производить классификацию не на основе четких данных, а на основе вероятности принадлежности к тому или иному классу. Это делает их более гибкими и удобными для решения многих задач. Но встает вопрос о целесообразности использования данных алгоритмов. И самым первым вопросом, на который следует ответить, это является ли вероятностная классификация достаточно качественной для ее использования [2].

Оценка качества классификации может быть выполнена двумя способами [1]:

  1. Формальный способ. Формальный способ основывается на определении некоторых формальных критериев. Лучшим считается то решение, для которого значение формального критерия максимально.
  2. Экспертный способ. Решение оценивается специалистами заданной предметной области.

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

В качестве систем аналогов были рассмотрены следующие:

  1. Экспертная система нечеткой кластеризации нейропроцессорных систем (Система 1);
  2. Система Эйдос;
  3. Интеллектуальная система для комплексной диагностики промышленного оборудования (Система 2);
  4. Система «Довольный Гражданин»;

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

A1 – загрузка данных из файла;

A2 – выбор метода классификации;

A3 – визуализация результатов классификации в виде текста;

A4 – визуализация результатов классификации графически;

A5 – оценка трудоемкости алгоритмов классификации.

Для определения весов критериев воспользуемся аналитической иерархической процедурой Саати [3-4].

Матрица парных сравнений, средние геометрические и веса критериев представлены в таблице 1.

Таблица 1. Матрица парных сравнений, средние геометрические и веса критериев

A1

A2

A3

A4

A5

Среднее геометрическое

Веса критериев

A1

1

1/3

1/5

1/5

1/7

0,29

0,04

A2

3

1

1/3

1/3

1/5

0,58

0,08

A3

5

3

1

1/3

1/5

1,00

0,14

A4

5

3

3

1

1/3

1,72

0,24

A5

7

5

5

3

1

3,50

0,49

Сумма

7,09

1

Диаграмма весовых коэффициентов для критериев A1, A2, A3, A4, A5 представлена на рис. 1.

Весовые коэффициенты критериев качества
Рисунок 1. Весовые коэффициенты критериев качества

Выполним проверку матрицы попарных сравнений на непротиворечивость [4].

Суммы столбцов матрицы парных сравнений:

R1=21; R2=12,33; R3=9.53; R4=4.87; R5=1.88.

Путем суммирования произведений сумм столбцов матрицы на весовые коэффициенты альтернатив рассчитывается вспомогательная величина L = 5.38. Индексом согласованности ИС = (L-N)/(N-1) = 0.078.

Величина случайной согласованности для размерности матрицы парных сравнений: СлС = 1.12.

Отношение согласованности ОС=ИС/СлС = 0.07. не превышает 0.2, поэтому уточнение матрицы парных сравнений не требуется.

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

Определим (по введенной шкале) количественные значения функциональных возможностей Xij(таблица 1.2). Вычислим интегральный показатель качества для каждого программного продукта [4].

Таблица 2. Интегральные показатели качества

Критерии

Весовые коэф-ты

Программные продукты

Базовые значения

Разрабатываемая система

Система 1

Система Эйдос

Система 2

Система «Довольный Гражданин»

a1

0,04

5

4

4

5

5

6

a2

0,08

3

5

4

4

4,2

5

a3

0,14

5

6

5

5

4,6

6

a4

0,24

5

6

4

2

4,6

6

a5

0,49

1

4

2

0

2,4

5

Интегр. показ-ль качества Q

2,94

4,85

3,15

1,69

3,512

5,47

где Qj=∑ai*Xij интегральный показатель качества для j-го программного средства.

Построим лепестковую диаграмму интегрального показателя качества каждого программного продукта (рис. 2).

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

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

Лепестковая диаграмма значений функциональных характеристик
Рисунок 3. Лепестковая диаграмма значений функциональных характеристик

На рисунке 4 показана диаграмма верхнего уровня процесса «Анализ трудоемкости алгоритмов классификации».

Диаграмма верхнего уровня процесса «Анализ трудоемкости алгоритмов классификации».
Рисунок 4. Диаграмма верхнего уровня процесса «Анализ трудоемкости алгоритмов классификации».

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

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

Исполнителями процесса являются пользователь системы и информационная система (ИС).

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

На рисунке 5 показана детализация процесса «Анализ трудоемкости алгоритмов классификации».

Детализация диаграммы А1 «Анализ трудоемкости алгоритмов классификации».
Рисунок 5. Детализация диаграммы А1 «Анализ трудоемкости алгоритмов классификации».

Анализ трудоемкости алгоритмов классификации осуществляется в пять этапов:

  1. задание необходимых исходных данных для выполнения анализа» - на данном этапе пользователь загружает в систему файл, содержащий данные, которые необходимо классифицировать (т.е. разбить на группы);
  2. реализация выбранного алгоритма классификации» – на данном этапе выполняется классификация загруженных пользователем данных на основании выбранного им алгоритма, результаты классификации отображаются пользователю;
  3. расчет коэффициентов качества классификации» – выполняется расчет коэффициентов качества классификации в соответствии с описанной математической моделью;
  4. оценка трудоемкости алгоритмов классификации» – на данном этапе выполняется оценка трудоемкости выбранного алгоритма классификации на заданном наборе данных;
  5. сохранение результатов анализа в БД» – на данном этапе выполняется сохранение в БД информации об исходных данных, выбранном алгоритме классификации и результатах оценки качества классификации и трудоемкости алгоритма.

Список литературы

  1. Морозов А.О., Рыбанов А.А. Экспертная оценка программных продуктов для расчета метрических характеристик физической схемы базы данных // Современные научные исследования и инновации. 2015. № 1-1 (45). С. 97-102.
  2. Назаров А. О. Модель и метод концептуальной кластеризации объектов, характеризуемых нечеткими параметрами // Фундаментальные исследования. 2014. №9-5 С.993-997.
  3. Рыбанов А. Определение весовых коэффициентов сложности тем учебного курса на основе алгоритма Cаати // Педагогические измерения. 2014. № 4. С. 21-28.
  4. Рыбанов А.А., Макушкина Л.А. Технология определения весовых коэффициентов сложности тем дистанционного курса на основе алгоритма Саати // Открытое и дистанционное образование. 2016. № 1 (61). С. 69-79.
  5. Рыбанов А.А., Усмонов М.С.О., Попов Ф.А., Ануфриева Н.Ю., Бубарева О.А. Информационные системы и технологии/Научный ред. И. А. Рудакова / Центр научной мысли (г. Таганрог). Москва, 2013. Том Часть 4. -90 с.
  6. Черняев А.О., Рыбанов А.А. Разработка и исследование алгоритмов автоматизированного проектирования логических схем реляционных баз данных // В мире научных открытий. -2010. -№ 4, ч. 11. - C. 128-129.