Software & Systems

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

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

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

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

К1 ÞJ ³ k1Mmax,                                                       (1)

где J – общее количество воздушных объектов, находящихся в обработке; Mmax – максимальная производительность канала (потребителя); k1 – коэффициент, определяющий допустимую загрузку каналов по количеству воздушных судов.

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

К2 ÞN ³ k2Nmax,                                                       (2)

где N, Nmax – количество формируемых для передачи стандартных кодограмм в данном цикле обмена и производительность канала по количеству передаваемых кодограмм соответственно; k2 – коэффициент, определяющий допустимую загрузку каналов по количеству передаваемых стандартных кодограмм.

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

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

При решении задачи классификации объектов перспективными АСУ в условиях параметрической неопределенности классов широко используется способ Г.В. Шелейховского, характеризующийся высокой степенью достоверности классификации в условиях параметрической неопределенности и пересечения классов [2]. Данный способ максимизирует энтропию, давая в результате наименее сомнительное распределение вероятностей принадлежности объектов классификации к классам из каталога (далее будем называть этот способ базовым). Способ имеет ряд недостатков, затрудняющих применение в АСУ [3], к которым относятся высокая вычислительная трудоемкость и возможное проявление проблемы сходимости. В связи с этим представляет научный интерес анализ основных этапов реализации базового способа с целью устране- ния или ослабления известных недостатков и обеспе- чения возможности реализации данного способа СППР, интегрированной в состав АСУ.

Основой для классификации типа объекта классификации по значениям его параметров, представленных в виде совокупности входных признаков, является каталог эталонных значений, записанный в памяти АСУ. Базовый метод оперирует данными из классификационной матрицы D:

D = ½dk,j½,                                                                (3)

где k = 1, …, V; j = 1, …, W.

В матрице (1) число столбцов V равно числу классов в объединении множеств типов, к которым могут относиться все объекты классификации, находящиеся в обработке. Число строк матрицы равно числу подмножеств однотипных объектов W. В результате применения процедуры последовательного нормирования матрица D преобразуется в матрицу вероятности отнесения объектов классификации к различным классам из каталога эталонных значений:

P = ½pk,j½, k = 1, …, V; j = 1, …, W,                     (4)

где pk, j – вероятность принадлежности k-й группы объектов к j-му классу; V – число подмножеств однотипных объектов классификации; W – число классов.

В матрице (4) для каждого k-го объекта либо набора объектов в результате реализации базового метода определена вероятность его принадлежности к j-му классу из каталога. На основе данной матрицы для каждого объекта классификации строится результирующий вектор распределения вероятностей, который является основой для принятия решения о принадлежности объекта определенному классу из каталога.

Базовый способ можно разделить на три основные составляющие:

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

-     работа классификационной процедуры последовательного нормирования;

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

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

Представление в параметрическом пространстве классов из каталога эталонных значений в виде областей, а объектов классификации в виде точек позволяет оценить наличие пересечений классов и места попаданий точек (объектов классификации) в области (классы) или пересечения областей. Так, например, при составлении классификационного вектора нет необходимости сравнивать параметры объекта классификации с параметрами всех классов из каталога эталонных значений, достаточно обнаружить первое попадание точки в область и дополнительно оценить принадлежность данной точки только тем областям, которые имеют пересечения с обнаруженной областью. Попадание в параметрическом пространстве точки в область является критерием установки соот Рис. 1. Блок-схема методики классификации объектов Fig. 1. The block diagram of the methodology for object classification ветствующей единицы в классификационном векторе объекта, представленного данной точкой. Если точка попадает в пересечение областей, это говорит о том, что соответствующий объект классификации будет иметь несколько единиц в своем классификационном векторе.

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

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

Сущность решения задач по предложенной методике заключается в следующем [4].

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

2. Анализ, выявление и устранение условий несходимости при решении задачи классификации.

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

4. При создании и обработке классификационной матрицы обеспечить хранение в памяти ЭВМ и обработку только ненулевых элементов матрицы.

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

Алгоритм предварительного анализа входных данных

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

Очевидно, что обработку входных данных на подготовительном этапе можно разбить на два подэтапа:

-     предварительный анализ каталога эталонных значений с целью выявления параметрических пересечений допустимых интервалов;

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

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

Алгоритм предварительного анализа входных данных реализуется совокупностью блоков 1–3 комбинированной методики классификации (рис. 1) и может быть представлен следующим образом.

1. Предварительный анализ каталога эталонных значений. По аналогии с методом дробящихся этало- нов, в котором по обучающей выборке строятся гипер- сферы, для каталога эталонных значений строятся гиперсферы в N-мерном параметрическом пространстве. Учитывая специфику представления данных в каталоге в виде допустимых интервалов некоторых зна- чений, целесообразно воспользоваться упрощенной разновидностью метода, в которой вместо гиперсфер используются гиперпараллелепипеды. Стороны параллелепипедов параллельны параметрическим координатным осям, что существенно облегчает задание их исходных размеров и положения, а также проверку условия попадания точек внутрь параллелепипедов или в их пересечения. Применение такого подхода к построению и использованию гиперсфер (гиперпараллелепипедов) позволяет экономить до 30 % машинного времени при обработке данных.

Таким образом, в соответствии с методом дробящихся эталонов в результате будет получен набор гиперпараллелепипедов первого уровня (далее областей) в N-мерном параметрическом пространстве для каталога эталонных значений. Наличие пересечений данных областей говорит о том, что может возникнуть проблема отнесения анализируемого объекта более чем к одному классу. Если же нет ни одного пересечения, можно с уверенностью сказать, что все поступающие на обработку объекты будут однозначно классифицированы или отнесены к классу «новый объект» в случае непопадания ни в одну область. Следовательно, еще до поступления объектов на обработку можно установить, будет ли целесообразным применение процедуры последовательного нормирования или используемый метод выродится в метод построения эталонов [4].

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

Формирование классификационных векторов объектов классификации происходит следующим путем:

-     для очередного объекта классификации ищется его первое попадание в область;

-     если обнаружена область, в которую попадает объект, выбираются все области, имеющие пересечения с обнаруженной;

-     анализируется попадание объекта классификации в области, выбранные на предыдущем шаге;

-     составляется список областей, в которые попадает объект, – классификационный вектор объекта.

Таким образом, классификационная матрица строится не методом последовательного перебора возможности отнесения анализируемого объекта к каждому классу из каталога эталонных значений, как это делается в базовом методе, а по результатам данного шага алгоритма. Блок-схема алгоритма предварительного анализа входных данных показана на рисунке 3 [5].

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

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

Программная реализация процедуры последовательного нормирования «простым» способом, то есть с использованием обычных двумерных массивов, не представляет особой сложности. В дальнейшем будем называть этот способ матричным. Как правило, на практике объект классификации не может попадать во все классы из каталога эталонных значений (или в большую их часть), отсюда следует вывод о разреженности классификационной матрицы. Следовательно, при матричном способе представления и обработки классификационной матрицы программа большую часть времени будет обрабатывать нулевые элементы, которые, помимо обработки, нуждаются еще и в выделении памяти для хранения. Исходя из вышесказанного, имеет смысл разработка варианта реализации процедуры последовательного нормирования, оперирующего с классификационной матрицей, представленной в виде циклически связанных ортогональных списков [6].

Суть предлагаемого алгоритма заключается в исключении из рассмотрения нулевых элементов матрицы, то есть в создании псевдоматрицы, состоящей только из значащих элементов [7]. Данный алгоритм реализует блок 6 комбинированного метода классификации (рис. 1). В роли строки матрицы выступает динамический список, который создается при анализе принадлежности i-го объекта к j-му классу. В случае возможности принадлежности создается очередной элемент списка. Столбцы матрицы также являются списками. Каждый элемент матрицы входит в состав списка-строки и списка-столбца. Назовем данный способ хранения и обработки данных алгоритмом списочного представления классификационной матрицы. Фрагмент псевдоматрицы приведен на рисунке 4, где элементы списка, содержащие рассчитываемые значения вероятностей, обозначены Р. Помимо самой псевдоматрицы, существуют еще два динамических списка, в которых хранится основная информация по строкам (столбцам). Элемент списка основной информации содержит начальный адрес списка со значениями вероятности, абсолютный номер соответствующей строки (столбца) и сумму элементов в строке (столбце). Каждый элемент списка основной информации является «головой» списка со значениями вероятности. На ри Рис. 4. Фрагмент псевдоматрицы Fig. 4. Fragment of pseudomatrix сунке 4 эти элементы обозначены А [8].

Блок-схема реализации процедуры последовательного нормирования с помощью циклически связанных ортогональных списков приведена на рисунке 5 [8, 9].

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

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

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

Следует отметить, что на практике классификация объектов зачастую проходит в условиях сильно насыщенной ложными помеховыми объектами обстановки. А во множестве описаний объектов, поступивших на обработку, могут быть описания объектов различных типов, число которых неизвестно [10–12]. Таким образом, из всего множества новых (неклассифицированных) объектов следует выделить объекты, имеющие постоянные параметры, то есть меняющие свои значения от измерения к измерению в пределах заданного допустимого интервала. При этом все остальные объекты, характерной особенностью которых является резкое изменение некоторых параметров или кратковременное появление, следует относить к ложным, «помеховым» объектам. Данную задачу можно решить построением областей в параметрическом пространстве, используя принципы кластерного анализа.

Разработанный алгоритм анализа результатов классификации при формировании новых классов реализуется совокупностью блоков 8–11 комбинированной методики классификации (рис. 1). Сущность алгоритма представлена ниже [7].

При первом измерении в уже имеющемся параметрическом пространстве, созданном на подготовительном этапе работы метода, для каждого неклассифицированного (нового) объекта строится область, характеризующая новый класс. Центром области является сам объект, а радиусом – заданное заранее значение. При следующем измерении существование области должно подтвердиться попаданием в нее объекта из состава входных данных. Если существование области подтвердилось определенное количество раз (порог подтверждения), информация об эталоне данной области заносится во временный каталог новых классов. В противном случае область удаляется из параметрического пространства. Для объекта, не попавшего ни в одну область, строится новая область. Блок-схема разработанного алгоритма представлена на рисунке (см. http://www.swsys.ru/uploaded/image/2019-1/2019-1-dop/10.jpg).

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

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

Литература

1.     Гетманчук А.В. Алгоритм классификации радиотехнических сигналов по методу Г.В. Шелейховского // Состояние, проблемы и перспективы создания корабельных информационно-управляющих комплексов: сб. докл. науч.-технич. конф. М., 2013. С. 258–262.

2.     Шпак B.Ф., Радченко С.А., Кулаков А.А. Программная реализация алгоритма классификации по методу Г.В. Шелейховского // Вопросы специальной радиоэлектроники. 2010. Вып. 3. С. 49–57.

3.     Дикарев В.А. Обработка параметров системы информационного обеспечения авиационных комплексов радиоэлектронной борьбы // Радиотехника. 2001. № 4. С. 59–64.

4.     Хайдуков Д.С. Применение кластерного анализа в государственном управлении // Философия математики: актуальные проблемы: тез. II Междунар. научн. конф. М.: МАКС Пресс, 2009. С. 57–69.

5.     Кулаков А.А., Лобода К.П., Шпак В.Ф.  Основные принципы параллельной обработки входной информации разнотипными АСУ радиотехнических комплексов // Вопросы специальной радиоэлектроники. 2013. Вып. 2. С. 15–20.

6.     Рыбина Г.В. Основы построения интеллектуальных систем. М.: Финансы и статистика, ИНФРА-М, 2010. 178 с.

7.     Гетманчук А.В. Высокопроизводительные метод и алгоритмы автоматической классификации объектов в условиях параметрической неопределенности и пересечения классов на основе методологии с системной максимизацией энтропии // Изв. ЮФУ. 2016. № 7. С. 39–52.

8.     Потапов А.Н., Семин М.В., Титов И.Ю. Программно-ориентированный комплекс имитационной математической модели оценки качества представления информации в автоматизированной системе управления для выдачи в каналы передачи данных «Оценка КПИ АСУ». Свид. о гос. регистр. прогр. для ЭВМ № 2017613390 РФ. Зарегистр. 17.03.2017.

9.     Круг П.Г. Нейронные сети и нейрокомпьютеры. М.: Изд-во МЭИ, 2002. 128 с.

10.  Горелик А.Л., Барабаш Ю.Л., Кривошеев О.В., Эпштейн С.С. Селекция и распознавание на основе локационной информации. М.: Радио и связь, 1990. С. 32–43.

11.  Jenssen R. An information theoretic approach to machine learning. Thesis of Dг. Sc. Department of Physics Univ. of Tromso, Norway, 2005, pp. 111–118.

12.  Torkkola K. Feature extraction by non-parametric mutual information maximization. J. Machine Learning Research. 2013, vol. 3, pp. 24–30.

References

1. Getmanchuk A.V. An algorithm for radio signals classification by the method of G.V. Sheleykhovsky. Proc. Sci. and Tech. Conf. “State, Problems and Prospects of Ship Management Information Systems”. Moscow, 2013, pp. 258–262 (in Russ.).
2. Shpak V.F., Radchenko S.A., Kulakov A.A. Classification algorithm software implementation by the method of G.V. Sheleykhovsky. Special Radio Electronics Issues. Taganrog, 2010, iss. 3, pp. 49–57 (in Russ.).
3. Dikarev V.A. Processing of system parameters of information support systems of electronic warfare aircraft systems. Radio Engineering. 2001, no. 4, pp. 59–64 (in Russ.).
4. Khaydukov D.S. Application of cluster analysis in public administration. Proc. 2nd Intern. Sci. Conf. “Philosophy of Mathematics: Important Problems”. Moscow, MAX Press, 2009, pp. 57–69 (in Russ.).
5. Kulakov A.A., Loboda K.P., Shpak V.F. Basic principles of parallel processing of input information by different types of radio engineering complex ACS. Special Radio Electronics Issues. Moscow–Taganrog, 2013, iss. 2, pp. 15–20 (in Russ.).
6. Rybina G.V. Basics of intellectual system construction. Moscow, Finansy and Statistika, INFRA-M Publ., 2010, 178 p.
7. Getmanchuk A.V. High-performance methods and algorithms for automatic object classification under parametric uncertainty and classes intersection based on the methodology with system entropy maximization. Izvestiya SFedU. Engineering Sciences. Taganrog, 2016, no. 7, pp. 39–52 (in Russ.).
8. Potapov A.N., Semin M.V., Titov I.Yu. A program-oriented complex of a simulation mathematical model for of information presentation quality evaluation in an automated control system for the issuance in data transfer channels “ACS IPQ Evaluation”. Certificate of registration of a computer program no. 2017613390, 2017 (in Russ.).
9. Krug P.G. Neural Networks and Neurocomputers. Moscow, MEI Publ., 2002, 128 p.
10. Gorelik A.L., Barabash Yu.L., Krivosheev O.V., Epshtein S.S. Selection and recognition based on location information. Moscow, Radio i Svyaz Publ., 1990, pp. 32–43 (in Russ.).
11. Jenssen R. An information theoretic approach to machine learning. Dr.Sc. Thesis. Tromso, Norway, 2005, pp. 111–118.
12. Torkkola K. Feature extraction by non-parametric mutual information maximization. J. of Machine Learning Research. 2013, vol. 3, pp. 24–30.