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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2015
Автори:	Павлов, В.А., Коновал, А.О.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2015
Назва видання:	Індуктивне моделювання складних систем
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/125036
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений / В.А. Павлов, А.О. Коновал // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2015. — Вип. 7. — С. 220-231. — Бібліогр.: 9 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-125036
record_format	dspace
spelling	irk-123456789-1250362017-10-14T03:03:36Z Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений Павлов, В.А. Коновал, А.О. В работе предложен рекуррентный аддитивно-мультипликативный многоэтапный алгоритм метода группового учета аргументов для поиска наилучшей структуры моделей объектов классификации, заданных множествами наблюдений. Найденная структура применяется для приведения задачи классификации из многомерного пространства признаков в пространство параметров моделей объектов классификации. В роботі запропоновано рекурентний адитивно-мультиплікативний багатоетапний алгоритм методу групового врахування аргументів, що застосовується для пошуку найкращої структури моделей об'єктів класифікації, заданих множинами спостережень. Знайдена структура використовується для приведення задачі класифікації з багатовимірного простору ознак у простір параметрів моделей об'єктів класифікації. This paper proposes a recursive additive-multiplicative multi-step algorithm of Group Method of Data Handling to find the best structure models of objects classification given the set of observations. The obtained structure is used to transfer the classification problem from multidimensional space of variables in the parameter space of the models classification objects. 2015 Article Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений / В.А. Павлов, А.О. Коновал // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2015. — Вип. 7. — С. 220-231. — Бібліогр.: 9 назв. — рос. XXXX-0044 http://dspace.nbuv.gov.ua/handle/123456789/125036 681.513.8 ru Індуктивне моделювання складних систем Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	В работе предложен рекуррентный аддитивно-мультипликативный многоэтапный алгоритм метода группового учета аргументов для поиска наилучшей структуры моделей объектов классификации, заданных множествами наблюдений. Найденная структура применяется для приведения задачи классификации из многомерного пространства признаков в пространство параметров моделей объектов классификации.
format	Article
author	Павлов, В.А. Коновал, А.О.
spellingShingle	Павлов, В.А. Коновал, А.О. Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений Індуктивне моделювання складних систем
author_facet	Павлов, В.А. Коновал, А.О.
author_sort	Павлов, В.А.
title	Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений
title_short	Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений
title_full	Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений
title_fullStr	Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений
title_full_unstemmed	Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений
title_sort	рекуррентный аддитивно-мультипликативный многоэтапный алгоритм мгуа для задачи классификации объектов, заданных множествами наблюдений
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2015
url	http://dspace.nbuv.gov.ua/handle/123456789/125036
citation_txt	Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА для задачи классификации объектов, заданных множествами наблюдений / В.А. Павлов, А.О. Коновал // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2015. — Вип. 7. — С. 220-231. — Бібліогр.: 9 назв. — рос.
series	Індуктивне моделювання складних систем
work_keys_str_mv	AT pavlovva rekurrentnyjadditivnomulʹtiplikativnyjmnogoétapnyjalgoritmmguadlâzadačiklassifikaciiobʺektovzadannyhmnožestvaminablûdenij AT konovalao rekurrentnyjadditivnomulʹtiplikativnyjmnogoétapnyjalgoritmmguadlâzadačiklassifikaciiobʺektovzadannyhmnožestvaminablûdenij
first_indexed	2025-07-09T02:27:22Z
last_indexed	2025-07-09T02:27:22Z
_version_	1837134557606838272
fulltext	Павлов В.А. Коновал А.О. Індуктивне моделювання складних систем, №7, 2015 220 УДК 681.513.8 РЕКУРРЕНТНЫЙ АДДИТИВНО-МУЛЬТИПЛИКАТИВНЫЙ МНОГОЭТАПНЫЙ АЛГОРИТМ МГУА ДЛЯ ЗАДАЧИ КЛАССИФИКАЦИИ ОБЪЕКТОВ, ЗАДАННЫХ МНОЖЕСТВАМИ НАБЛЮДЕНИЙ В.А. Павлов, А.О. Коновал Киевский национальный технический университет Украины (КПИ) vpavlo@bk.ru, alexandra.konoval@gmail.com В роботі запропоновано рекурентний адитивно-мультиплікативний багатоетапний алгоритм методу групового врахування аргументів, що застосовується для пошуку найкращої структури моделей об'єктів класифікації, заданих множинами спостережень. Знайдена структура використовується для приведення задачі класифікації з багатовимірного простору ознак у простір параметрів моделей об'єктів класифікації. Ключові слова: класифікація, моделювання, рекурентний адитивно-мультиплікативний багатоетапний алгоритм (РАМБА), метод групового врахування аргументів (МГУА), простір параметрів, критерій селекції, критерій роздільності This paper proposes a recursive additive-multiplicative multi-step algorithm of Group Method of Data Handling to find the best structure models of objects classification given the set of observations. The obtained structure is used to transfer the classification problem from multidi- mensional space of variables in the parameter space of the models classification objects. Keywords: classification, modeling, recursive multistage additive-multiplicative algorithm (RAMMA), Group Method of Data Handling (GMDH), the parameter space, selection criterion, separability criterion В работе предложен рекуррентный аддитивно-мультипликативный многоэтапный алгоритм метода группового учета аргументов для поиска наилучшей структуры моделей объектов классификации, заданных множествами наблюдений. Найденная структура применяется для приведения задачи классификации из многомерного пространства признаков в пространство параметров моделей объектов классификации. Ключевые слова: классификация, моделирование, рекуррентный аддитивно- мультипликативный многоэтапный алгоритм (РАММА), МГУА, пространство параметров, критерий селекции, критерий разделимости. Вступление Известной проблемой задач распознавания образов есть неоднозначность решения при недостаточной информативности "портрета" объекта классификации. При этом, как правило, мы имеем дело с одноразовыми измерениями его характеристик (признаков). Проблема распознавания становится тем более очевидной, если значения признаков объекта могут меняться в зависимости от значения некоторого неконтролируемого параметра, или в целом от состояния среды. Проблема проистекает из возможности частичного пересечения областей значений признаков в исходном пространстве измеряемых переменных для объектов из различных классов при различных состояниях среды, что влечет очевидную неоднозначность результата классификации. Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА Індуктивне моделювання складних систем, № 7, 2015 221 Определенным выходом из положения является описание объекта не одним, а множеством измерений, осуществленных при различных состояниях среды. Такой комплекс измерений позволяет более точно описать объект, как некоторое множество его состояний в исходном многомерном пространстве. Однако проблема классификации, тем не менее, остается, так как, во-первых, разработанные подходы к распознаванию, как правило, предполагают однократное измерение признаков объекта, а во-вторых, мы допускаем частичное пересечение областей исходного пространства признаков для объектов классификации из различных классов (рис.1). Данные условия не позволяют при классификации объекта непосредственно использовать отдельные точки, а требуют разработки специальных подходов, где возможно оперировать множествами измерений, или характеристиками, полученными на основании этих множеств, или параметрами различных целесообразных разложений имеющихся характеристик в модельный ряд. 1. Постановка задачи. Задан факт существования некоторого множества классов  KDDDD ,...,, 21 , представляющих собой конечные или бесконечные множества объектов:  11 dD  ,  22 dD  ,...,  KdD K . Известен факт, что множества  ji DD  при ji  . Нам классы KDDD ,...,, 21 задаются, как их приближения 11 DD  , 22 DD  , … , KK DD  через усеченные множества объектов, им принадлежащих:    111 ddD  ,    222 ddD  , … ,    KKK ddD  , где    11 1 1 1 ,..., nddd  ,    22 1 2 2 ,..., nddd  , ….,    K n KK K ddd ,,...1 . Очевидно, что ввиду  ji DD , выполняется  ji DD  при ji  . Предполагается, что объекты классификации d , описываются в конечномерном пространстве MRZ  множествами  dz векторов признаков T Mzz ),...,( 1z , образующими в пространстве mR соответствующие классам KDDD ,...,, 21 множества (области) KZZZ ,...,, 21 . Причем, как указывалось ранее, в пространстве Z допускаются частичные пересечения, как множеств (областей), в которых формируются множества dz (по типу рис.1) так и множеств (областей) iZ . Павлов В.А. Коновал А.О. Індуктивне моделювання складних систем, №7, 2015 222 Необходимо на основании обучающих подмножеств объектов d из различных классов 11 ZZ  , 22 ZZ  ... , KK ZZ  построить наилучшее правило классификации объектов из исходных множеств  KDDDD ,...,, 21 . Рассмотрим некоторые известные подходы к решения задач такого класса. 2. Анализ и обоснование подхода к решению задачи. Исходя из особенностей практических приложений задачи распознавания образов традиционно формулируются в 2-х (в некоторых случаях эквивалентных) постановках: - (1) для многомерного пространства, где объекты классификации задаются одной многомерной точкой и - (2) для многомерного пространства, где объекты задаются, как подмножества многомерных точек (многомерных измерений). Подавляющее число методов и алгоритмов распознавания образов были разработаны для решения задач классификации в первой постановке, для второго случая рассматриваются, как правило, подходы к сведению задачи к постановке (1). Исторически, постановка (2) рассматривалась, как задача распознавания кривых, или, в более сложном случае, плоских геометрических объектов (например букв). И так, имеем множество кривых (одна из них приведена на - рис.2), заданных, каждая, множеством двухмерных точек ( или графиком - рис.2) и множество геометрических форм (рис.3), заданных на условной (пиксельной) сетке. Для решения задачи распознавания кривых чаще применяется координатный подход, для распознавания геометрических форм - пиксельный. Рис.2 К задача распознавания Рис.3 К задаче распознавания кривых плоской формы Для описания первой задачи классификации в форме постановки (1), кривые ( рис.2) определяются значением признака z1, как значением z(t1) ,..., значение признака zn принимается, как значение z(tn). Для описания второй задачи в форме постановки (1), значениями переменных zi есть степени заштрихованности (яркости, цветности) соответствующего пикселя. Признаки интерпретируются, как случайные величины, задача нахождения классификатора сводится к получению распределений значений признаков в Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА Індуктивне моделювання складних систем, № 7, 2015 223 классах и нахождению дискриминантной функции позволяющей разделить эти распределения [1]. Однако существуют известные препятствия на пути классического подхода: 1.Построение многомерных (а в данном случае, очень многомерных) распределений требует значительных объемов обучающих выборок и выполнения достаточно жестких предположений о виде функций распределения (например нормальность) 2.Крайне желательно применить целесообразные процедуры сокращения размерности пространства переменных 3.В общем случае, когда объекты классификации задаются в многомерном пространстве, и при этом, представлены, каждый, подмножеством многомерных точек, решение задачи классификации требует построения плотностей распределения, размерностью, на порядки большей, чем в рассмотренных выше случаях. Таким образом, в общей постановке данный подход уже не конструктивен. Рассмотрим ниже еще два возможные пути решения проблемы. Пусть в пространстве MRZ  заданы обучающие подмножества 11 ZZ  , 22 ZZ  ... , KK ZZ  объектов  i jd , где i - индекс класса, j - индекс объекта в классе. Каждый объект i jd описывается в пространстве Z подмножествами i jdZ многомерных точек (вектор-строк) матрицы объект- свойства tz :   i j i j dtdZ z . Пусть данные в матрице объект-свойства упорядочены по классам. Обозначим kn - количество объектов в k-том классе,    K knn 1k - количество объектов в матрице. Тогда kWkk NnN  - количество точек в k-м классе, если количество точек в каждом объекте k-го класса одинаково и равно kW N , и    kn 1i k iWk NN если количество точек в объектах k id различно и равно k iW N . Здесь kW и k iW - подмножества точек в соответствующих классах и отдельных объектах класса k, соответственно. Общее количество точек (строк) в матрице данных      K k n i k iWK k NNN 1 1 K 1k . Существенным далее есть то, что для каждого объекта k id известна не одна, а некоторое подмножество точек k i i djdZ        zk , тут          i q k q k p p i q W k p p NNNNj k q 1 1 1 1 1 1 1 ,...,1 , где i - номер объекта в классе k. Существенным есть также то, что, в общем случае, области существования объектов id и jd : ZZZ ji dd , , представленные в обучении подмножествами векторов   ii dttdZ   z ,   jj dttdZ   z , могут частично Павлов В.А. Коновал А.О. Індуктивне моделювання складних систем, №7, 2015 224 пересекаться, при этом указанные объекты, могут принадлежать и различным классам [2]. Тогда возможно рассматривать следующие 2 пути для сведения постановки (2) задачи классификации к постановке (1): 1. Необходимо определить свертку типа    k j jd Wt ttzZ  подмножества многомерных векторов   j i j ddZ z в некоторую многомерную точку jdZ , таким образом, чтобы она однозначно определяла объект jd в своем классе k в исходном пространстве признаков z1…..zM. Определение такой свертки должно сопровождаться условиями наилучшей классификации объектов в данном классе сверток. 2. Пусть в исходном пространстве признаков z1…..zM описание объекта d дается подмножеством точек   jddZ z , неизвестной нам характеристики объекта fd(z1,…,zM)=0. Тогда указанных характеристик предполагается столько, сколько объектов: 1,...,nd0),...,z,zf(z M21  , (1) Далее, рассматриваем тот случай, задачи, когда среди исходных переменных z1,…,zM возможно выделить выходную переменную. Определим новое пространство признаков x, как пространство обобщенных переменных (ОП) x1, x2,…,xМ1 полученных из переменных исходного пространства MRZ  , при этом ОП x1, x2,…,xМ1 наилучшим образом представляют характеристики fd(z1,…,zM)=0 d=1,..,n по исходным множествам точек   jddZ z уже как линейные свертки по хi. Тогда с точностью до переобозначения, характеристики (1) возможно искать в виде (2): i M i ii M i i xrrzrrу    1 0 1 0 )( (2) где, для простоты, М снова обозначает размерность нового пространства обобщенных переменных x для представления объекта d. Тогда решение задачи классификации переведем в сопряженное пространству обобщенных переменных x, пространство параметров   MjjrR ,...,0  характеристик i M i i xrrу    1 0 , что позволит рассматривать объекты d уже не как множества   jddZ z , и не как характеристики fd(z1,…,zM)=0, d=1,..,n, а как точки в пространстве параметров R [2]. Отдельные точки rd уже однозначно определяют объекты d ввиду отсутствия полностью совпадающих подмножеств   jddZ z . В дальнейшем Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА Індуктивне моделювання складних систем, № 7, 2015 225 предполагается классифицировать объекты d, как точки rd в пространстве параметров R . Ниже рассматривается второй из указанных путей для перевода исходной задачи в постановке (2) к постановке (1) построения классификатора. Возражением для применением данного похода могут быть соображения по поводу возможного нарушения гипотезы компактности и сопутствующих проблем, связанных с выбором меры близости в полученном пространстве R при решении задачи классификации. Однако риск данных проблем существует в любой задаче и обоснованность подхода подтверждается, или не подтверждается результатами классификации на проверочной и экзаменационной выборках данных. Близкий по постановке подход рассматривался в задаче диагностики нарушений работы сердечной мышцы при выделении признаков, как параметров разложения сигнала электрокардиограммы в ортогональный дискретный ряд Кравчука [3]. Другим примером использования указанного подхода в исходном пространстве Z фазовых координат являются работы [4,5] по применению методов классификации для оценки областей параметров устойчивости динамических систем. К этому же пути решения задачи принадлежит предлагаемый подход, когда при нахождения наилучшей структуры параметрического пространства характеристик объектов d предлагается использовать метод группового учета аргументов [6]. 3. Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм (РАММА) МГУА Ключевым моментом в реализации изложенного выше подхода есть задача определения единой, наилучшей для всех известных объектов полиномиальной структуры (2). Решение данной задачи целесообразно осуществить в рамках направления моделирования, известного, как метод группового учета аргументов - МГУА [6]. Существует большое количество работ, посвященных развитию, оптимизации различных алгоритмов МГУА [6]. В [2], например, предложено искать указанную выше полиномиальную структуру с помощью версии комбинаторного алгоритма МГУА, адаптированного для одновременного поиска множества моделей единой структуры. Однако такой подход возможен только для класса задач достаточно ограниченной размерности. В [2] применение комбинаторного алгоритма оправдано размерностью расширенного пространства переменных m=8 и количеством объектов моделирования - порядка 150. Для размерностей, существенно больших, необходимо предлагать версии многорядных или многоэтапных алгоритмов МГУА. В настоящей работе для реализации целесообразной версии сокращенного перебора возможных структур моделей объектов классификации предложен рекуррентный аддитивно- мультипликативный многоэтапный алгоритм МГУА. Перебираемые структуры при этом имеют вид ,......,...., 11i 10101 kikik xaхaayхaay   и Павлов В.А. Коновал А.О. Індуктивне моделювання складних систем, №7, 2015 226 образуют последовательно усложняющиеся описания, к каждому из (F) которых, на каждом k-том этапе, добавляется лучшая, по внешнему критерию, обобщенная переменная (ОП) ki х , генерируемая, как член полного полинома вида .... 1 1 11 1 m 1 0       kji m i m j m k ijk m i m j jiij i ii zzzazzazaay (3) где, iz - переменные расширенного множества исходных переменных. Рассмотрим основные этапы предлагаемого алгоритма 1. Предварительная обработка данных. 1.1 Формирование матрицы расширенного множества переменных. Расширение обеспечивает лучшую способность алгоритма к отражению моделируемых свойств объектов классификации. Здесь реализовано расширение исходного множества переменных z дополнительными переменными z 1 , -3z , 3-z 1 . Обозначим далее, для простоты, переменные из расширенного множества, снова через z . 1.2 Формирование матрицы обобщенных переменных (ОП). Каждая из ОП является одним из возможных произведений уже существующих переменных расширенного множества переменных, как членов полного полинома (3) заданной максимальной степени p. Известно, что число членов такого полинома определяется (4), где m – количество аргументов (переменных) 1  m pmCS (4) Далее, по аналогии с [6], возможно сформировать в (р+1) системе счисления ряд чисел (обозначим его, как ряд "S"), каждое из которых будет определять вид соответствующей ОП. В отличие от [6], генерируются последовательно десятичные натуральные числа и переводятся в (р+1) систему счисления. Будем игнорировать те из них, для которых сумма цифр данного числа в десятичной системе будет более (p+1). Сформированный таким образом ряд из S чисел есть табличное отображение полинома. Действительно, каждой ОП из полинома (4), соответствует некоторый член ряда "S". В каждой ОП участвует столько сомножителей, сколько имеет разрядов соответствующее число ряда "S". Каждый сомножитель, есть исходная переменная, десятичный индекс которой есть место по порядку разряда числа ряда "S", а его степень - значение в данном разряде. 1.3. Переход к матрице центрированных переменных. Позволяет отбросить свободный член в искомой структуре, вплоть до момента ее окончательного определения. После нахождения оптимальной структуры Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА Індуктивне моделювання складних систем, № 7, 2015 227 выполняется обратный переход к исходным переменным и рассчитывается свободный член полученной модели. Центрирование осуществляется по среднему обучающей выборки в данном объекте: A j yy jY , A iijij kkk xx X (5) 2 Формирование информационной матрицы XX T максимального размера для каждого объекта. Этап позволяет избежать повторных расчетов при формировании исходных данных для нахождения параметров каждой новой структуры. 3 Организация перебора вложенными структурами. Для генерации моделей используется дерево переборного алгоритма (рис.4). Ветви дерева соответствуют созданным ранее ОП. На каждом ряду алгоритма реализуется движение по узлам дерева слева направо и сверху вниз. Для дерева, изображенного на рис.4, соответствующим образом полинома будет набор отображенный в табл.1. Для того, чтоб двигаться по данному дереву слева направо и сверху вниз необходимо восходить по соответствующему табличному массиву снизу вверх, - сначала по рядам, сумма значений которых равна 1, потом, где равна 2 и далее (до p+1). Таблица 1 Схема полинома Z3 Z2 Z1 0 0 1 0 0 2 0 0 3 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 3 0 1 0 0 1 0 1 1 0 2 1 1 0 1 1 1 1 2 0 2 0 0 2 0 1 2 1 0 3 0 0 Павлов В.А. Коновал А.О. Індуктивне моделювання складних систем, №7, 2015 228 Рис. 4 – Дерево переборного алгоритма Для первого и всех последующих уровней дерева в алгоритме введены степени свободы (F1 и F2), которые определяют максимальное количество лучших, по внешнему критерию, узлов на данном уровне, от которых продолжается поиск. Параметр F определяет количество моделей которые отбираем в процессе выполнения алгоритма. Для каждой из сгенерированных структур: 3.1 Из полученной ранее полной матрицы XX T для каждого объекта на обучающей выборке формируются информационные матрицы, соответствующие рассматриваемой структуре. Как впервые было предложено для алгоритмов МГУА в [7], для сокращения времени расчета параметров модели в данном алгоритме на всех рядах селекции, начиная со второго, обратные матрицы рассчитываются с использованием метода «окаймления»: Обозначив матрицу XX T на n-той итерации алгоритма для конкретной структуры через An, напомним (8,9):                              nnn nn nnnnnn nnnnnn nn nn n aV UA aaaa aaaa aaaa aaaa A 1 ,1,2,1, ,11,12,11,1 ,21,22221 ,11,11211 ... ... ............... ... ... ; (6) Тогда обратную ей матрицу 1A ищем:                          nn nn n nn n nnnn n aa Av a uA a AvuA A A 11 1 1 1 1 1 1 11 1 1 ; (7) Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА Індуктивне моделювання складних систем, № 7, 2015 229 3.2 Рассчитываем параметры моделей (коэффициенты при ОП в оцениваемой структуре) для каждого объекта на обучающей подвыборке (8) ;)( 1 YXXXa TT  (8) Количество формируемых структур ограничивается степенями свободы на каждом уровне. Поиск оптимальных моделей (ОП) не продолжается далее по ветке, если её узел не улучшил структуру. Для полученной структуры рассчитывается критерий селекции и его значение сравнивается со значением критерия худшей структуры из F уже сохраненных в буфере (худшей из лучших). Если сравнение в пользу новой структуры - она замещает в буфере ранее отобранный вариант. В программной реализации применено две целесообразные формы внешнего критерия: 1.Критерий селекции [2] , который базируется на значениях относительных нормированных среднеквадратических ошибок  A и  B для данной структуры моделей. Рассчитывается значение критерия (9), где – вес ошибок обучения,  – вес несогласованности ошибок, а k – веса соответствующих классов. AB AB BAselCr    )())1(()1(   ; (9) ; )( )( 2 ),( 2          Ai i K k n j jkAi M q A kiqiqkjik A Y rxYk   (10) ; )( )( 2 ),( 2          Bi i K k n j jkBi M q B kiqiqkjik B Y rxYk   (11) 2.Предлагается рассчитывать критерий селекции, который базируется на значениях дисперсий (12). Поскольку, конечной целью работы является именно классификация, то логичной есть оценка качества искомой структуры с точки зрения ее разделяющей способности. Такой критерий селекции представляет собой отношение суммы дисперсий внутри классов к значению дисперсии между центрами классов. Пусть Rj - множество точек ri в пространстве параметров моделей объектов классификации Rm, принадлежащих классу j, j=1,..,K , i=1,...,nj а 2 KC - количество сочетаний из К по 2, тогда введем критерий в виде: Павлов В.А. Коновал А.О. Індуктивне моделювання складних систем, №7, 2015 230            K i K ij ji K K j n Rr i j sel C nK Cr j ji 1 1 2 2 1 2 1 11 rr rr j (12) С учетом покоординатной дисперсии для m координат (p=1,...,m, где m - размерность пространства Rm ), понимая под нормой эвклидово расстояние между i-той точкой q-того кластера и его центром, выражение для нормы будет иметь вид (13), а (12) примет вид (14). Здесь для удобства, введено переобозначение: текущий номер класса q перенесли, как верхний индекс. ;)( 1 22    m p q pip rrq i rr (13)                K i K ij m p q pip K K q n i m p q pip q sel rr C r nK Cr q 1 1 2 12 1 1 2 1 )( 1 )r( 11 (14) 4.Лучшая структура (и мультипликативная, и аддитивная составляющие) определяются минимумом критерия селекции или «наращивание» структуры происходит до тех пор, пока критерий селекции будет улучшаться более, чем на некоторую минимальную заданную величину (предельное значение улучшения модели). После определения критерия селекции новая структура сравнивается с худшей из сохраненных в буфере и, при сравнении в пользу новой, замещает ее. Для окончательно отобранных моделей выполняется расчет свободных членов полинома (15). ik k ki kk xrxryr  ...110 ; (15) 4. Выводы Предложен подход к распознаванию объектов, заданных подмножествами строк матрицы объект-свойства. Подход предполагает построение процедур распознавания в пространстве параметров наилучшей структуры моделей объектов классификации, что позволяет перевести задачу в многомерное пространство, где каждый объект представлен точкой в пространстве параметров своей модели. Для нахождении такой структуры разработан рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА. Для увеличения точности искомых моделей предусмотрено расширение исходного множества переменных. Для организации передвижения по проверяемым структурам образуется дерево переборного алгоритма с использованием вложенных структур. Организованная последовательность Рекуррентный аддитивно-мультипликативный многоэтапный алгоритм МГУА Індуктивне моделювання складних систем, № 7, 2015 231 вложенных структур позволила использовать подход [9] и применить для расчета параметров моделей рекуррентные формулы метода «окаймления», что существенно увеличило быстродействие алгоритма. Применено два варианта внешнего критерия алгоритма: критерий селекции [2], основанный на значениях относительных нормированных среднеквадратических ошибок для модели и предложен критерий селекции основанный на значениях внутриклассовой и межклассовой дисперсий в пространстве моделей объектов классификации. В результате, осуществленный переход в параметрическое пространство моделей заданных объектов позволяет применять затем весь набор разработанных в настоящее время методов многомерной классификации. Литература 1. Keinosuke Fukunaga. Introduction to statistical pattern recognition/ School of Electrical Engineering Purdue University Lafayette, Indiana/ Academic Press, New York and London, -1972. - Р. 307 2. G.V. Knishov. Combinatorial agorithm for constructing a parametric feature space for the classification of multidimensional models / G.V. Knishov, Е.A. Nastenko, , O.K. Nosovets, V.A. Pavlov, N.V. Kondrashova // Cybernetics and Systems Analysis. - July 2014. - Volume 50, Issue 4. - Pp 627-633. 3. Забара С.С. Метод виділення інваріантнихознак сигналів / С.С. Забара, Н.Б. Філімонова, К.Х. Зеленский // Доповіді Національної академії наук України. – 2009. – №2. –с.49-55. 4. Редько И.Н. Оценка области глобальной устойчивости уравнения маятникового типа методами теории классификации объектов / И.Н. Редько И.Н. // 4-я конференция "Нелинейные колебания в механических системах" ННГУ. – 1996.–c. 45-46. 5. Редько И.Н. Применение методов теории классификации объектов для оценок областей существования установившихся движений / И.Н. Редько, В.Д. Шалфеев // Вестник ННГУ, сер. Радиофизика (Нелинейная динамика - синхронизация и хаос). - 1998. – c. 28-36. 6. Ивахненко А.Г. Помехоустойчивость моделирования / А.Г. Ивахненко, В.С. Степашко // Киев: «Наук.думка». – 1985.– 216 7. Степашко В.С. Комбинаторный алгоритм МГУА с оптимальной схемой перебора моделей[Текст] /В.С. Степашко // Автоматика. – 1981. – №3.– c. 31–36. 8. Фаддеев Д.К. Вычислительные методы линейной алгебры / Д.К. Фаддеев, В.Н.Фаддеев // СПб.: Лань. – 2002. – 736 с. 9. Гергей Й. Обращение матриц и решение систем линейных и нелинейных уравнений методом окаймления // ЖВММФ. — 1979. — Т. 19. — № 4. — С. 803-810. http://link.springer.com/journal/10559 http://link.springer.com/journal/10559 http://link.springer.com/journal/10559/50/4/page/1

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

Репозитарії

Схожі ресурси