Концепция кортежности и ее реализация для матричных кортежей

Запропоновано концепцію кортежних операторів для набору матриць фіксованої розмірності, що дає можливість переносити методи евклідового простору в матричний простір....

Full description

Saved in:

Bibliographic Details
Date:	2016
Main Authors:	Донченко, В.С., Зинько, Т.П.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Series:	Проблемы управления и информатики
Subjects:	Математическое моделирование и исследование сложных управляемых систем
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/208192
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Концепция кортежности и ее реализация для матричных кортеже / В.С. Донченко, Т.П. Зинько // Проблемы управления и информатики. — 2016. — № 4. — С. 87-99. — Бібліогр.: 10 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208192
record_format	dspace
spelling	irk-123456789-2081922025-10-21T00:01:54Z Концепция кортежности и ее реализация для матричных кортежей Концепція кортежності та її реалізація для матричних кортеже Cortege conception and its implementation for matrix corteges Донченко, В.С. Зинько, Т.П. Математическое моделирование и исследование сложных управляемых систем Запропоновано концепцію кортежних операторів для набору матриць фіксованої розмірності, що дає можливість переносити методи евклідового простору в матричний простір. The concept of cortege operators for a set of fixed dimension matrices is introduced, enabling transfer of Euclidean space methods to matrix spaces. 2016 Article Концепция кортежности и ее реализация для матричных кортеже / В.С. Донченко, Т.П. Зинько // Проблемы управления и информатики. — 2016. — № 4. — С. 87-99. — Бібліогр.: 10 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208192 512.64:004.93 10.1615/JAutomatInfScien.v48.i7.50 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Математическое моделирование и исследование сложных управляемых систем Математическое моделирование и исследование сложных управляемых систем
spellingShingle	Математическое моделирование и исследование сложных управляемых систем Математическое моделирование и исследование сложных управляемых систем Донченко, В.С. Зинько, Т.П. Концепция кортежности и ее реализация для матричных кортежей Проблемы управления и информатики
description	Запропоновано концепцію кортежних операторів для набору матриць фіксованої розмірності, що дає можливість переносити методи евклідового простору в матричний простір.
format	Article
author	Донченко, В.С. Зинько, Т.П.
author_facet	Донченко, В.С. Зинько, Т.П.
author_sort	Донченко, В.С.
title	Концепция кортежности и ее реализация для матричных кортежей
title_short	Концепция кортежности и ее реализация для матричных кортежей
title_full	Концепция кортежности и ее реализация для матричных кортежей
title_fullStr	Концепция кортежности и ее реализация для матричных кортежей
title_full_unstemmed	Концепция кортежности и ее реализация для матричных кортежей
title_sort	концепция кортежности и ее реализация для матричных кортежей
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
topic_facet	Математическое моделирование и исследование сложных управляемых систем
url	https://nasplib.isofts.kiev.ua/handle/123456789/208192
citation_txt	Концепция кортежности и ее реализация для матричных кортеже / В.С. Донченко, Т.П. Зинько // Проблемы управления и информатики. — 2016. — № 4. — С. 87-99. — Бібліогр.: 10 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT dončenkovs koncepciâkortežnostiieerealizaciâdlâmatričnyhkortežej AT zinʹkotp koncepciâkortežnostiieerealizaciâdlâmatričnyhkortežej AT dončenkovs koncepcíâkortežnostítaíírealízacíâdlâmatričnihkorteže AT zinʹkotp koncepcíâkortežnostítaíírealízacíâdlâmatričnihkorteže AT dončenkovs cortegeconceptionanditsimplementationformatrixcorteges AT zinʹkotp cortegeconceptionanditsimplementationformatrixcorteges
first_indexed	2025-10-21T01:21:36Z
last_indexed	2025-10-22T01:10:19Z
_version_	1846642390899621888
fulltext	© В.С. ДОНЧЕНКО, Т.П. ЗИНЬКО, 2016 Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 4 87 УДК 512.64:004.93 В.С. Донченко, Т.П. Зинько КОНЦЕПЦИЯ КОРТЕЖНОСТИ И ЕЕ РЕАЛИЗАЦИЯ ДЛЯ МАТРИЧНЫХ КОРТЕЖЕЙ Введение Решение фундаментальных прикладных задач, к которым относятся задачи группирования информации, невозможно без использования развитых математи- ческих структур и средств оперирования ими. Евклидовые пространства числовых векторов ,nR математические структуры, связанные с ними, чаще всего используются в прикладных исследованиях. С одной стороны, это определяется богатством струк- турных связей, порожденных операциями и скалярным произведением в рамках этих пространств, с другой — богатством конструктивных возможностей опери- рования такими структурами. В евклидовых пространствах такие фундаменталь- ные структуры обозначают линейные подпространства, гиперплощади (сдвинутые подпространства), эллипсоиды и эллипсоидальные цилиндры. Эти структуры обо- значим термином «множественные». К базовым структурам можно отнести мат- рицы линейных операторов и симметричных неотрицательно определенных квад- ратичных форм. Эти базовые образования в евклидовых пространствах обозначим как сингловые (одиночные — single). В евклидовых пространствах nR множе- ственные и сингловые структуры связаны между собой. Так, с матрицей линейно- го оператора естественным образом связывают два подпространства: множество возможных значений и ядро оператора, а множество возможных решений или псевдорешений системы линейных алгебраических уравнений (СЛАУ) является гиперплощадью. Эллипсоидальные цилиндры и матрицы неотрицательно опреде- ленных квадратичных форм, которые их задают, также связаны между собой. Эффективность конструктивного использования базовых структур в значительной мере определяется средствами оперирования ими, в частности, возможностью пере- хода от сингловых к множественным, и наоборот. Так, множество решений СЛАУ: точных или псевдо — это гиперплощадь (сдвинутое подпространство), т.е. множе- ственная структура. Ее конструктивное описание определяется возможностью ее описания по сингловой структуре — матрицей СЛАУ. Такие возможности реали- зуются сингулярным представлением матрицы (singular valued decomposition — SVD), матрицы СЛАУ и псевдообращение (ПдО) к ней. Также SVD и ПдО позво- ляют построить ортогональные проекторы на подпространства и гиперплощади, порожденные наборами векторов; сингловые структуры по множественным. Та- кой переход реализует возможность эффективного вычисления расстояний до исследуемых множественных образований. Вычисление таких расстояний прин- ципиально в задачах классификации и кластеризации. SVD и ПдО, а также опе- раторы на их основе, реализуют возможности эффективного описания матрицы квадратичной формы, которые задают эллипсоиды, «накрывающие» оптимальным об- разом заданный набор векторов. Упомянутая связь между множественными и сингловими структурами, возможности конструктивного описания очень важны в прикладных задачах, которые можно обозначить термином «задачи группирова- ния информации» (Grouping information problem — GIP): задачи классификации– кластеризации и задачи восстановления функции, представленной наблюдениями. Однако GIP-задачи важны не только для ситуаций, когда объектами группирова- ния являются числовые векторы. Типичный пример упомянутой ситуации — задачи распознавания аудиосигналов, которые естественным образом представлены матри- 88 ISSN 0572-2691 цами спектрограмм, и матрицы, представляющие изображения в задачах обработки изображений. В то же время отсутствуют средства конструктивного описания в структурах на основе матриц, которые предоставляли бы те же возможности, что и для .nR Итак, развитие математических средств решения GIP для матричных объек- тов, аналогичных тем, что существуют для евклидовых пространств числовых векто- ров, — актуальная и важная задача для прикладных исследований. Как отмечалось выше, такие возможности служат решающей основой средств оперирования базовы- ми структурами в nR SVD и ПдО для матриц. Использование упомянутой фунда- ментальной техники в евклидовых пространствах, отличных от ,nR в частности, на матричные евклидовые пространства, требует иного взгляда на эти объекты. Это озна- чает, что SVD и ПдО становятся образом представления линейных операторов между благоприятными евклидовыми пространствами. Именно это составляет основу кон- цепции кортежных операторов для решения задачи развития техники оперирования базовыми структурами в матричных евклидовых пространствах. В настоящей статье рассмотрены адекватные классы операторов между под- ходящими евклидовыми пространствами, которые сделали бы возможным по- строение средств оперирования базовыми алгебраическими структурами в евкли- довом пространстве матриц фиксированной размерности, аналогичные использу- емым в ,nR с тем же уровнем конструктивности такого использования. Приведены примеры применения техники оперирования в матричных евклидовых пространствах для решения задач группирования информации. 1. Абстрактный вариант сингулярного представления линейных операторов между евклидовыми пространствами SVD-представление матрицы (тот или другой вариант ее факторизации) яв- ляется важным средством конструктивного описания и оперирования базовыми структурами .nR Для конструктивного оперирования такими же структурами в других евклидовых пространствах необходимо SVD-представление матрицы бо- лее широкого «операторного» значения. Основные объекты и обозначения. В дальнейшем )),(,( E — абстрактное евклидово пространство, на которое, при необходимости, будем ссылаться как на Е с индексами. Скалярное произведение в разных евклидовых пространствах не будет индексироваться. Линейный оператор (ЛО) между двумя евклидовыми пространствами обозначим ,: 21 EEA  сопряженный — .: 12 EEA  Линей- ные подпространства ,)( ALA    A LA )( — множества возможных значе- ний (рейнджи) операторов ,, AA соответственно будут обозначаться ,KerA A Ker — их ядра (множества нулей). Рейнджи и ядра — линейные подпростран- ства, причем ядра являются ортогональными дополнениями к рейнджам сопря- женных операторов [1]: ,)))(((Ker   A A LA .))((Ker   AA LA Рейнджи и ядра операторов AA, будем называть фундаментальными под- пространствами оператора А или операторов ., AA Ортогональный проектор линейного подпространства EL будем обозна- чать .LP Напомним, что ,LEL PIP  EI — тождественный оператор в .E Ниже под сингулярностью линейного оператора будем подразумевать пару: соб- ственное число–собственный вектор. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 4 89 Ортогональные проекторы ядер операторов AA, будем обозначать ),(AZ .)( AZ Очевидно, что ,)( 1   A LE PIAZ .)( 2 ALE PIAZ  Напомним, что ,e ,Ee обозначает линейный функционал ,: 1REe  который определяется соотношением ).,( xexe  Заметим, что ,e сопряженный к линейному оператору ,: 1REe  являет- ся линейным оператором ,: 1 ERe  действие которого определяется соотно- шением ., 1Ree  Будем отождествлять eA с е, в частности, запишем .ee   Обычно сопряже- ние является линейным преобразованием. Абстрактный вариант SVD-представления линейного оператора. Ни- же приведем теорему 1, которая является абстрактным вариантом теоремы об SVD-представлении оператора между произвольными евклидовыми пространствами. Теорема 1 [2]. Для произвольного линейного оператора A между евклидовы- ми пространствами ,, 21 EE такого что ,: 21 EEA  и его сопряженного A спра- ведливы следующие представления: .),( ,),( 11 11        r i iii r i uii r i iii r i vii uvvA vuuA i i   (1) Здесь 0... 22 1  r — общий набор ненулевых собственных чисел операторов AAAA , ; riEvEu ii ,1,, 12  , — ортонормированные наборы собственных векторов операторов, соответственно ,AA ,AA которые отвечают ненулевым собственным числам: ,2 iii uuAA  ,2* iii vAvA  ,,1 ri  ,T ijjuu i  ,T ijji vv  ;ji  ,,1, ri Av u i i i    ;,1, * ri uA v i i i    ALARr dim)(dim  — размерность подпространства возможных значений оператора А, Exuxuxu  ,),,( — ли- нейный функционал на евклидовом пространстве, порожденный вектором .Eu Доказательство приведено в [3]. Следствие. Теорему об SVD-представлении матрицы линейного оператора см. в [1, 2, 4, 5]. Произвольную матрицу nmRA  ранга ),(min nmr  предста- вим в виде       r i iii r i uii r i iii r i vii uvvAA vuuA i i 1 T 1 T 1 T 1 ,   (2) по ненулевым наборам сингулярности Arrivu iiii rank,,1),,().,( 22  матриц AAAA TT, соответственно. 90 ISSN 0572-2691 Заметим, что ,,T nRvv  — реализация линейного функционала v средства- ми матричной алгебры. Важен следующий результат, «обратный» теореме 1. Его доказательство см. в [3]. Теорема 2. Пусть в абстрактных евклидовых пространствах 21, EE заданы: 1) набор положительных чисел ,0...: 22 1 2  ri );dim,min(dim,,1 21 EErri  2) ортонормированный набор векторов ;,1,1 riEvi  3) ортонормированный набор векторов .,1,2 riEui  Тогда для оператора ,,, vuA определенного равенством , 1 ,,     r i uiivu i uA  (3) его SVD-представление совпадает с соотношением (3), которое его задает. 2. Абстрактный вариант псевдообращения Как и ранее, употребление термина «абстрактный» означает ссылку на ре- зультат, который касается евклидовых пространств вообще. В абстрактном ПдО линейного оператора целесообразно использовать его SVD-представления. Определение 1. ПдО для линейного оператора А между евклидовыми простран- ствами 21, EE будем называть оператор ,: 12 EEA  который по SVD-пред- ставлению А определяется соотношением       r i iii r i uii uvvA i 1 1 1 1 ).,( (4) Замечание. В соответствии с обратной теоремой об SVD-представлении со- отношение (4) определяет сингулярное представление оператора .A Все свойства классического ПдО для матриц остаются справедливыми и в случае общего варианта определения с точностью до замены транспонирования на сопряженность, а реализации скалярного произведения средствами матричной алгебры — скалярным произведением. Рассмотрим основные свойства абстрактного ПдО: 1. .)()(   AA 2. ,AAP A L   AAIPIPAZ ELEA A   11Ker)( — операторы ортого- нального проектирования на подпространство возможных значений оператора A и ядро оператора A соответственно. 3. ,  AAAAP AL    AAIPIPAZ ELEA A 22Ker )( — операто- ры ортогонального проектирования на подпространство возможных значений оператора А и ядро оператора A соответственно. 4. .)()(   AAAAAA 5. Множество решений или псевдорешений y СЛАУ yAx  задается со- отношением .)( 1EAZyAy   (5) Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 4 91 Если ,0))(,(  yAZy множество (5) задает множество решений, если 0))(,(  yAZy — псевдорешений. Условие 0))(,(  yAZy является необходи- мым и достаточной для разрешимости СЛАУ. Под псевдорешениями имеются в виду решения оптимизационной задачи 2 minArg yAx nRx   поиска — наилучшего квадратического приближения правой части СЛАУ значениями левой части. 6. Группирующие операторы ),(AR )( AR определяются соотношениями ,)(  AAAR .)(  AAAR Их называют также взвешенными проекционными операторами. 7. .)(     A L AA PAAAARA  3. Кортежные операторы В работе [2] выдвинута концепция кортежных операторов (КО-концепция), реализованная в упомянутой работе для варианта матричных строчных кортежей матриц фиксированной размерности: строк матриц. В классической матричной алгебре такие образования называют блочными матрицами, имея в виду их ис- пользование в рамках матричной алгебры. КО-концепция предусматривает, что реализация программы перенесения техники оперирования основными базовыми структурами в евклидовых пространствах числовых векторов на матричные ев- клидовы пространства разрешается введением в рассмотрение и исследованием линейных операторов над подходящими евклидовыми пространствами [6, 7]. Такие линейные операторы в рамках предлагаемой КО-концепции назовем кор- тежными. В дальнейшем будем использовать матричное евклидово пространство nmR  -матриц фиксированной размерности nm с покоординатными операциями сложения и умножения на скаляр, а также — с покоординатным определением скалярного произведения: .)(),(:),( ,1,,1 nm ijijijij njmi RbBaAbaBA     Это скалярное произведение называют также «следовым», поскольку .tr),( TBABA  Упорядоченный набор )...,,( 1 KAA матриц фиксированной размерности: ,,1, KkRA nm k   будем называть строчным матричным кортежем (длины К). Определение 2. Кортежным оператором (КорО) , соответствующим матричному кортежу ),...,,( 1 KAA будем называть линейный оператор ,: nmK RR    который задается соотношением ),...,,(, 1 1 K K k kk AAAxx     .:)...,,( 1 T K K Rxxxx  Очевидно, имеет место следующая лемма, соответствующая теореме для .nR Согласно этой теореме линейное подпространство значений линейного оператора является линейной оболочкой векторов-столбцов матрицы, которой этот оператор задается. 92 ISSN 0572-2691 Лемма 1. Линейное подпространство ),,1,( KkAL k  порожденное набором матриц ,,1, KkRA nm k   совпадает с линейным подпространством L воз- можных значений КорО , определяемое кортежем )....,,( 1 KAA В дальнейшем понадобятся следующие объекты и обозначения. 1. Символ F обозначает матрицу скалярных произведений набора матриц ,kA ,,1 Kk  матричного кортежа )...,,( 1 KAA : .),( ,1, Kjiji AAF   (6) Заметим, что матрица F, определенная соотношениям (6), является матрицей Грамма набора элементов (матриц) KAA ...,,1 евклидового пространства .nmR  2. Пусть ,,1),,( 2 riv ii  — набор ненулевых сингулярностей матрицы F с ортонормированным набором собственных векторов и ненулевых собственных чисел: ,2 iii vFv  ,rank,,1 Frri  ;,1,;,,1 rjijivvv jii  ,0...21  r ),...,,( 1 T Kiii vvv  .,1 ri  3. ,nm i RU  ,,1 ri  — нормированные образы собственных векторов ,iv ,,1 ri  ,rank Fr  при применении КорО : .,1, 1 11 riAU K k kkiiiii       Отсюда справедлива следующая теорема, конкретизирующая теорему 1. Теорема 3 [8] (сингулярное разложение КорО). В обозначениях (1), (2) набо- ры riv ii ,1),,( 2  и ,,1),,( 2 riU ii  однозначно определяют SVD-разложение операторов    , в виде                                    ,,),( ,,),( 111 11 T 1 nm r i iii r i Uii r i Uii K r i iii r i iii r i vii RYYYUvYvYvY RxxvUxvUxUx ii i   (7) .rank Fr  Упомянутые наборы являются стандартными наборами ортонормированных сингулярностей операторов, соответственно .,      Кроме того, соб- ственные векторы двух наборов сингулярностей связаны стандартными соот- ношениями: .,1,, ri v U U v i i i i i i           (8) Замечание 1. Обратим внимание, что сингулярные разложения (кортежного оператора и сопряженного к нему соотношения (7)) строятся на основе решения Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 4 93 классической матричной задачи на собственные значения для матрицы F — мат- рицы Грамма элементов матричного кортежа . Таким образом, данное представ- ление имеет конструктивность того же порядка, что и в случае классического SVD-разложения матриц. Псевдообращение для кортежных операторов. ПдО для КорО определяют- ся согласно абстрактному определению ПдО в соответствии с (3). Определение 3 [8]. ПдО      , и сопряженный к нему КорО определяются абстрактным определением ПдО в соответствии с равенствами ,,),( 1 1 1 1 1 1 nm r i iii r i Uii r i Uii RYYUvYvYvY ii                     (9) ,,)( 1 T1 1 T1 1 1 1 1 K r i iii r i iii r i vii r i vii RxxvUxvUxUxUx ii                               (10) .rank Fr  Замечание 2. Для ПдО КорО выполняются все свойства п. 2 абстрактного определения ПдО. Ортогональные проекторы основных подпространств для кортежных операторов. Фундаментальными подпространствами линейных операторов явля- ются: множество возможных значений (рейндж) для самого оператора и сопря- женного к нему, а также их ортогональные дополнения, которые являются ядрами сопряженных операторов. ПдО-теория Мура–Пенроуза для матриц предоставляет возможности конструктивного описания ортогональных проекторов упомянутых подпространств в евклидовых пространствах числовых векторов. Эти результаты полностью переносятся на кортежные операторы. В дальнейшем для базовых подпространств КорО будут использоваться все обозначения абстрактного варианта. Лемма 2. Ортогональные проекторы ),Z(,,      KerLL PPP a  a KerP )Z( a фундаментальных подпространств операторов    , определяются соотношениями ,,        a LL PP (11) .)( ,)(          nmKerKKer EZPEZP (12) Свойства псевдообращения для кортежных операторов. Как отмечалось выше, ПдО для КорО имеет те же свойства, что и классическое ПдО для матриц. В частности, выполняются следующие соотношения. 1. Аксиомы преобладания и ортогональных проекторов из определения по Муру:                       LL PP , , 2. Аксиома оптимальности из определения ПдО по Пенроузу: ,minarg 2 minArg 2 xY Yxx      ,0,   YRY nm — аксиома преобладания; — аксиома ортогональных проекторов. 94 ISSN 0572-2691 т.е. значение   на аргументе 0,   YRY nm — наименьшее по норме решение задачи наилучшего приближения правой части СЛАУ ,, KRxYx  ,nmRY  0Y значениями левой части. В [9, 10] приведен вид упомянутых операторов ортогонального проектирова- ния и их использование в расстояниях соответствия для решения задач распозна- вания жестов дактильного языка. 3. Квадрат расстояния 2 матрицы nmRY  от подпространства ),...,,( 1 KAAL ,,1, KkRA nm k   порожденного набором ,,1, KkRA nm k   определяется со- отношением      )))(Z,())(,())...,,(,( 1 2 YYYIYAALY mnK )....,,(,,),( 1 22 ,1 K nm kk Kk AARYvY       (13) Далее под гиперплоскостью ,,,),( nmnm RLRMLMLM   понимает- ся смещенное на элемент М евклидового пространства nmR  подпространство L: }.,:{),( nmnm RZZMXRXLMLM   4. Квадрат расстояния от гиперплоскости  MAALM K ))...,,(,( 1 ,:)...,,( 1 MAAL K ,,1, KkRA nm k   определяется соотношением   ))()(,()))...,,(,(,( * 1 2 MYZMYAALMY K ,,) ~ ,( 2 ,1 nm k Kk RYUMY     (14) .,1, ~ ), ~ ...,, ~ (~),...,,( 11 KkAAAAAAA kkKK  5. Множество решений или псевдорешений Y СЛАУ Yx  задается со- отношениям .)( K Y RZY     (15) Если ,0))(,(   YZY множество (15) задает множество решений, если 0))(,(   YZY — псевдорешений. Условие 0))(,(   YZY является необходимым и достаточным для разре- шимости СЛАУ. Группирующие операторы и эллипсоиды группирования. Напомним, что в случае евклидового пространства числовых векторов группирующие (взвешен- ные проекционные) операторы задают структуры второго порядка: эллипсоиды или минимальные эллипсоиды группировки и матрицы квадратичных форм, ко- торые определяют упомянутые эллипсоиды. Под эллипсоидами группировки (простыми или минимальными, центральными или нецентральними) подразуме- ваются эллипсоиды (эллипсоидальные цилиндры), которые оптимально «накры- вают» векторы из заданной последовательности, в частности векторы обучающей выборки, если речь идет о задачах классификации в прикладных задачах. Центром эллипсоидов может быть начало координат — центральные или другой центр — нецентральные. Оптимальность эллипсоидов состоит в том, что их оси максими- Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 4 95 зируют сумму квадратов проекций элементов, группировки на соответствующие оси при последовательном построении этих осей по упомянутому принципу и ис- ключение из области определения задачи оптимизации. Концепция кортежных операторов позволяет полностью перенести все утверждения о группировке векторов на наборы матриц. Для матричных наборов справедливы все утверждения об эллипсах (эллипсоидальных цилиндрах) группи- ровки в евклидовых пространствах nR . Эти утверждения о группировке для ев- клидового пространства nmR  матриц фиксированной размерности и являются предметом теорем, приведенных ниже. Как и в утверждениях о группировке для ,nR основными средствами груп- пировки служат операторы, ассоциированные с набором элементов, и операторы, построенные на их основе средствами ПдО. Определение 4. Группирующими для кортежного оператора будем называть операторы ),(),(    RR определяемые соотношениями .)(,)(            RR Лемма 3. Каждый из двух группирующих операторов может быть представ- лен на основе элементов SVD-представления кортежного оператора  в виде , ),( )( ,1 2 ,1 2              ri i ii ri i Ui UUU R i  .)( ,1 2 T ,1 2        ri i ii ri i vi vvv R i  Утверждение следующей леммы фиксирует оптимизационные свойства набора сингулярностей ,,1),,( 2 riU ii  из SVD кортежного оператора. Лемма 4. Одномерные подпространства ,,1, riL iU  порожденные вектора- ми ненулевого набора сингулярностей ,,1),,( 2 riU ii  оператора   являют- ся решениями оптимизационных задач о максимизации суммы квадратов проек- ций на одномерные подпространства с последующим сужением области задачи до подпространства, ортогонального уже построенным векторам:                  ,max ,maxarg 2 )( 1),...,(,1: 2 2 )( 1),...,(,1: 11 11 kUL K kUULUURU i kUL K kUULUURU i AP APU i nm i nm (16) .rank,,1 Frri  Теорема 4 [2]. Пусть произвольный набор матриц из ,nmR  )...,,( 1 KAA — матричный кортеж, а  — соответствующий ему кортежный оператор. Тогда все матрицы набора принадлежат внутренности эллипса, точнее, эллипсоидально- го цилиндра, который определяется соотношением ,1 )( ),( 1 2 2     r i i i r XU (17) 96 ISSN 0572-2691 или, что эквивалентно, ,,rank,1))(,( 1 nmRXFrXRrX     (18) где )(  R — группирующий оператор .)(     R Эллипсоиды, которые определяются неравенством (17) или (18), будем назы- вать центральными эллипсоидами группирования. В задачах группирования матриц значительную роль играют также нецент- ральные эллипсоиды группирования. Это такие эллипсоиды, которые имеют среднее A элементов набора ,,1, KkAk  в качестве центра, а кортежный опера- тор определяется кортежем .,1, ~ ), ~ ...,, ~ (~ 1 KkAAAAA kkK  Определение 5. Нецентральным эллипсоидом группирования для кортежного оператора : )...,,( 1 KAA будем называть эллипсоид, который определяется соотношением .,1))()(,(1 ) ~ ( ), ~ ( ~1 1 2 2 nm r i i i RXAXRrAX r AXU         (19) Теорема 5. Все матрицы — элементы матричного кортежа ),,,( 1 KAA  принадлежат нецентральному эллипсоиду группирования, построенного по эле- ментам SVD представления кортежного оператора ). ~ ...,, ~ (~, 1~ KAA Минимальные эллипсоиды группировки для кортежных операторов. Длину полуосей в эллипсоидах группировки (центральных или нецентральных) можно пропорционально уменьшить так, чтобы дальнейшее уменьшение с сохра- нением свойства покрытия было невозможно. Определим rrrr  minmin ~, соответственно соотношениями ). ~ )(, ~ (max~),)(,(max ~ ,1 min ,1 min kk Kk kk Kk ARArARAr        (20) Теорема 6. Все матрицы набора ,,1, KkRA nm k   принадлежат внутрен- ности эллипсов, точнее, эллипсоидальных цилиндров — центральных или нецен- тральных, которые задаются соответственно соотношениями [2] .1)))((~,(,1))(,( ~1 min 1 min       AXRrAXXRrX (21) Определение 6. Эллипсоиды группировки, которые определяются соотноше- ниями (21), будем называть минимальными эллипсами группирования. Кортежность для евклидовых пространств числовых векторов. Концеп- ция кортежности операторов по матричным кортежам естественным образом обобщает концепцию матрицы как линейного оператора между двумя евклидо- выми пространствами числовых векторов. Действительно, матрица ,nmRA  за- писанная по столбцам: ),( 1 naaA  ,,1, njRa m j  может рассматриваться как кортеж с элементами из .mR Этот кортеж определяет кортежным образом ли- нейный оператор, ,: mn A RR  который совпадает с оператором, задаваемым матрицей .:)...,,(, 1 T 1 n n n j jjA RxxxxAxaxx    Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 4 97 Кроме того, матрица Грамма F для оператора элементов кортежа из столбцов матрица А — это матрица :T AA .),()( ,1,,1,1,,1 TT njmijinjmiji aaaaAAF   (22) Именно кортежность позволяет перенести все методы исследования GIP-задач для евклидовых пространств числовых векторов на матрицы. Она предоставляет воз- можность устанавливать связи между множественными структурами: подпростран- ствами или гиперплощадями и эллипсами группирования, порожденными наборами элементов евклидового пространства, числовых векторов или матриц. Такая возмож- ность принципиально важна для задач кластеризации–классификации, в которых принадлежность группам объектов с тем или другим свойством (кластера, класса) осуществляется на основе так называемых расстояний соответствия. Так, расстояни- ями соответствия являются функции на исследуемых объектах, по значениям кото- рых определяется принадлежность к тому или иному классу. Такие расстояния соот- ветствия могут быть индивидуальными для каждого класса. Индивидуализация рас- стояний соответствия реализуется через ассоциацию погружение с каждым классом стандартной структуры евклидового пространства: линейной или нелинейной; под- пространства или гиперплоскости и эллипсоидов группировки: центральных или не- центральных, обычных или минимальных. Результаты для матриц, приведенные вы- ше, позволяют утверждать, что расстояния соответствия, построенные на основе по- гружения в подходящие структуры евклидовых пространств числовых векторов, справедливы и для евклидовых пространств матриц фиксированной размерности. 4. Расстояния соответствия в задачах кластеризации При обучении с учителем каждый класс Kl представляется обучающей вы- боркой: векторами признаков — числовыми векторами ,,1, njRa m j  или набором матриц .,1 KkRA nm k   Класс, которому принадлежат элементы обу- чающей выборки, может ассоциироваться либо с линейной структурой: подпро- странством или гиперплощадью, либо с квадратичной: эллипсоидом или мини- мальным эллипсоидом группирования — центральным или нецентральным. Рас- стояния от соответствующих структур будут определяться по характеристикам кортежных операторов, которые порождаются обучающими выборками разных классов. Как отмечалось выше, кортежный оператор по векторам из mR совпада- ет с матрицей, столбцы которой являются элементами обучающей выборки. Погружение в линейные структуры. Если класс Kl ассоциируется с линей- ной структурой:                      ))),1, ~ (,( ),1,( )),1,~(( ),1,( KkALA LKkAL njaLa LnjaL Kl k k j Aj где – — осреднение, а ~ — центрирование средним. Расстояния соответствия для каждого класса — евклидовые расстояния от линейных структур, которые ассоциируются с классом Kl, определяются фор- мулами (13), (14) для матриц и их соответствий для векторов оператора )...,,(: 1 KAA и матрицы :)...,,( 1 naaA              )),() ~ (,(),(,( ),)(,(),( )),( ~ 2 2 2 AYZAYLAY YZYLY KlY (23) — векторы, — матрицы, Kl — подпространство Kl — гиперплоскость. 98 ISSN 0572-2691 Векторный вариант расстояний соответствия для каждого класса — евклидо- вые расстояния от линейных структур, которые ассоциируются формально, полу- чается заменой прописных букв строчными и использованием сингулярностей матрицы F:          ).()A ~ ()())() ~~ (),((),(,( ,)())(,(),( )),( TT~2 TT2 2 ayZayayAAIayLAy yAZyyAAIyLy Kly mA mA Погружение в нелинейные структуры. В случае, когда Kl ассоциирует- ся с эллипсом группировки, расстояния соответствия определяются соотно- шениями: • эллипсоиды группирования (обычные)              )))((,( ),)(,( )),( 1 1 2 AYRrAY YRrY KlY • минимальные эллипсоиды группирования              )))((,( ),)(,( )),( 1 min 1 min2 AYRrAY YRrY KlY Расстояния соответствия для евклидовых пространств числовых векторов, как и в предыдущем случае, получаются заменой прописных букв строчными и операторов   на ,TA а  ~ — на . ~TA Заключение Оперирование базовыми линейными и нелинейными структурами в матричных евклидовых пространствах nmR  требует развития адекватных математических средств. Практика использования упомянутых структур в nR в значительной мере базируется на SVD-представлении матриц и ПдО матриц по Муру–Пенроузу. Поэто- му построение средств оперирования в nmR  нуждается в подходящих операто- рах, их SVD и ПдО в связи с новыми объектами, например кортежными, постро- енными по строчным кортежам матриц. Концепция развития средств оперирова- ния базовыми структурами для матричных евклидовых пространств может быть обозначена термином концепция кортежности. Для описанного в работе класса кортежных операторов построено SVD-представление, которое позволило реали- зовать на основе такого представления теорию псевдообращения с конструктив- ными возможностями получения формульных выражений как для ортогональных проекторов базовых подпространств оператора, так и для группирующих опера- торов. Упомянутая выше конструктивность означает, что построение основных объектов теории сводится к классической задаче на собственные значения для обычных матриц. Наличие средств оперирования базовыми структурами в мат- ричных пространствах существенно расширяет возможности использования таких матриц в математическом моделировании с матричными векторами признаков. Напомним, что во многих важных в прикладном отношении задачах математиче- ского моделирования именно матрицы появляются как представители анализиру- емых объектов. — центральный эллипсоид, — нецентральный эллипсоид; — центральный эллипсоид, — нецентральный эллипсоид; Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 4 99 В.С. Донченко, Т.П. Зінько КОНЦЕПЦІЯ КОРТЕЖНОСТІ ТА ЇЇ РЕАЛІЗАЦІЯ ДЛЯ МАТРИЧНИХ КОРТЕЖІВ Запропоновано концепцію кортежних операторів, реалізовану для варіанта, ко- ли кортежем є набір матриць фіксованої розмірності. Запропонована концепція дозволяє перенести конструктивні засоби опису основних лінійних та нелі- нійних структур евклідового простору числових векторів на матричні евклідові простори зі збереженням основних відношень та зв'язків. Це повністю стосу- ється використання зазначених структур в прикладних задачах класифікації та кластеризації. Принципово, що складність опису згаданих структур в матрич- них евклідових просторах не перевищує складності опису числових векторів для евклідових просторів і зводиться до задачі на власні значення для матриць. V.S. Donchenko, T.P. Zinko CORTEGE CONCEPTION AND ITS IMPLEMENTATION FOR MATRIX CORTEGES Cortege operators concept is implemented for version when cortege is a set of matri- ces with fixed dimensions. Suggested concept allows to transfer constructive tools of describing the basic linear and nonlinear structures of numerical vectors Euclidean space to matrix Euclidean spaces with preservation of the basic relations and ties. This completely concerns the use of these structures in applied problems of classifi- cation and clustering. The critical moment is that the difficulty of describing such structures in the matrix Euclidean spaces is not greater than the difficulty of describ- ing numerical vectors for Euclidean spaces and is reduced to the eigenvalue problem for matrices. 1. Kirichenko N.F. Analytical representation of perturbation of pseudoinverse matrices // Cybernet- ics and systems analysis. — 1997. — 33, N 2. — P. 230–239. 2. Donchenko V., Zinko T., Skotarenko F. «Feature vectors» in grouping information problem in ap- plied mathematics: vectors and matrixes // ITNEA, 2012. — P. 111–124. 3. Донченко В.С., Зінько Т.П., Скотаренко Ф.М. Концепція кортежності для лінійних опера- торів та її реалізація для матричних кортежів // Журнал обчислювальної та прикладної ма- тематики. — 2015. — № 3. — С. 127–140. 4. Кириченко Н.Ф. Аналитическое представление возмущений псевдообратных матриц // Ки- бернетика и системный анализ. — 1997. — № 2. — C. 98–107. 5. Kirichenko N.F., Donchenko V.S., Serbaev D.P. Nonlinear recursive regression transformers: dy- namic systems and optimization // Cybernetics and system analysis. — 2005. — 41, N 3. — P. 364–373. 6. Донченко В., Кривонос Ю., Омардибирова В. Базовые структуры евклидовых пространств: конструктвные методы описания и использования // New Trends in Classification and Data Mining. — 2010. — P. 155–170. 7. Donchenko V., Nazaraga I., Tarasova O. Matrixes least squares method and examples of its ap- plication // International Journal Information Technologies & Knowledge. —2013. — 7, N 4. — P. 325–336. 8. Донченко В.С. Евклидовы пространства: конструктивные методы описания базовых струк- тур и их использование // ITNEA, 2010. — P. 362–376. 9. Голік А.О. Відстані відповідності та засоби групування для векторних та матричних век- торів ознак та їх застосування в задачах розпізнавання мови та мови жестів: Дис. … канд. техн. наук: 01.05.04. — К., 2014. –– 154 с. 10. Голік А.О., Донченко В.С. Застосування еліпсоїдальної та ортогональної відстаней відповід- ності у задачах розпізнавання мови та жестів // Вісник Київського національного універ- ситету ім. Тараса Шевченка. — 2013. — Вип. 1. — С. 146–155. Получено 10.03.2016 Статья представлена к публикации членом редколлегии чл.–корр. НАН Украины А.А. Чикрием.

Концепция кортежности и ее реализация для матричных кортежей

Institution

Similar Items