Научный журнал
Международный журнал прикладных и фундаментальных исследований
ISSN 1996-3955
ИФ РИНЦ = 0,593

УСКОРЕННЫЙ ШАГОВО-ЦИКЛИЧЕСКИЙ АЛГОРИТМ ПОСТРОЕНИЯ K-ЗНАЧНЫХ БЕЗЫЗБЫТОЧНЫХ БЕЗУСЛОВНЫХ ДИАГНОСТИЧЕСКИХ ТЕСТОВ

Янковская А.Е. Китлер С.В.

Введение

Задача построения k-значных безызбы­точных безусловных диагностических те­стов (ББДТ) в интеллектуальных системах не нова и представлена в ряде публикаций, например в [1, 2, 6]. Однако, до сих пор, она не потеряла своей актуальности.

Предлагается построение k-значных ББДТ осуществлять посредством ускоренного шагово-циклического алгоритма с использо­ванием оптимизирующих преобразований матричного описания данных и знаний и матриц, построенных на их основе.

В данной статье приводятся основные понятия и определения, дается поста­новка задачи, описывается ускоренный шагово-циклический алгоритм построения k-значных ББДТ.

Представление данных и знаний

Данные и знания представляются с ис­пользованием матричной модели [1-4, 6], включающей целочисленную матрицу опи­саний (0, задающую описание объектов в пространстве характеристических призна­ков z1,z2..,zm и целочисленную матрицу раз­личений (R), задающую разбиение объектов на классы эквивалентности по каждому ме­ханизму классификации. Если значение ха­рактеристического признака несущественно для объекта, то данный факт отмечается про­черком («-») в соответствующем элементе матрицы Q. множество всех неповторяющих­ся строк матрицы различений сопоставлено множеству выделенных образов. обозначим через R´ одностолбцовую матрицу, элемента­ми которой являются номера образов.

Под образом будем понимать подмноже­ство объектов базы знаний с совпадающими значениями классификационных призна­ков. пример матриц Q, R и R´ представим на рис.1.

Построение матрицы импликаций. матрицей импликаций [1] назовем цело­численную матрицу U, столбцы которой сопоставлены характеристическим призна­кам z1,z2,...,z а строки - всевозможным па­рам объектов a, b из разных образов. Строка Ui матрицы U представляет
собой значение елочисленной вектор-функции различения,  - я (j∈{1, 2, ..., m}) компонента uij которой вычисляется по следующей формуле:

где qai j  , ( qbi j) - значение признака zj для объекта a (b), объекты a,b из разных образов.

Будем говорить, что строка Uk поглощает строку  

 

 где  i∈{1,2, ...,s} - множество строк ма­трицы U.

Отроки Uk и U несравнимы

 

Безызбыточной матрицей импликаций назовем такую матрицу U´, в которой отсут­ствуют поглощающие строки и поглощае­мые столбцы.

Тестом [5] называется совокупность при­знаков, различающих любые пары объектов, принадлежащих разным образам.

Тест называется безызбыточным, если содержит безызбыточное количество при­знаков.

Под закономерностями [4] в знаниях бу­дем понимать следующие подмножества признаков: константные, устойчивые (кон­стантные внутри образа), неинформатив­ные (не различающие ни одной пары объек­тов), альтернативные (в смысле включения в диагностический тест (ДТ)), зависимые (в смысле включения подмножеств раз­личимых пар объектов), несущественные (не входящие ни в один безызбыточный тест (БТ)), обязательные (входящие во все БТ), псевдообязательные (входящие в мно­жество используемых при распознавании БТ и не являющиеся обязательными) при­знаки, а также все минимальные и все (либо часть - при большом признаковом пространстве) безызбыточные различаю­щие подмножества признаков, являющие­ся, по сути, соответственно минимальными и БТ (тупиковыми тестами [5]).

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

Будем определять весовой коэффициент признака (БЮТ) z. по его разделяющей спо­собности [2] и обозначать через wi

где K - число выделенных образов; N - число строк в описании c-го образа  (c∈{r,t});   где qgi (qji) - значение признака zi из образа g (j), g ≠ j; σj - число бъектов в j-ом образе (j=1, ..., K), вычисляемое по формуле: (d - l - число значений «-» в l-ой строке матрицы Q, pl -
коэффициент повторения l-ой строки).

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

Построение сокращенных матриц описания, различений и безызбыточ­ной матрицы импликаций. Сокращен­ные целочисленные матрицы описания Q´, различений R´ и целочисленная безызбы точная матрица импликаций U´ использу­ются при построении ускоренного шагово-циклического алгоритма. Идея построения матриц изложена в публикации [6].

Построим матрицы Q´ и R´ по матрицам Q и R. каждый образ представляется двумя строками матрицы Q´. каждая четная (нечетная) строка Q´i (Q´f) матрицы Q´ представляет собой целочисленный вектор (i=2c, f=2c-1, c∈ {1, 2, ..., v}, v - количество образов), j-я (j∈{1, 2, ..., m}) компонента которого соответствует максимальному (минимальному) значению j-го ха ракте ристического признака внутри каждого образа и вычисляется по формуле: 

где ql (c) j - значение признака zj для объекта l∈ {1, 2, ..., rc} из образа c, а rc - количество объек тов, принадлежащих образу c.

Матрица R´ строится одновременно с по­строением матрицы Q´.

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

С целью обеспечения непересечения образов предлагается использовать пра­вило 1: если строки в матрице Q´ из об­разов c, e (c Ф e) совпадают, то в матрице Q выбирается строка в одном из выделен­ных образов, изменение которой приводит к наименьшему изменению значений наи­меньшего количества признаков в одной из совпадающих строк матрицы Q´, при­ водящее к непересечению каждой пары об­разов.

Далее скорректированные матрицы будем обозначать также через Q´ и R´ соответ­ственно.

После процедуры упорядочивания строк в матрицах Q и R (рис.1) и построения ма­триц Q´ и R´ выявляем, что строки 1 и 3 матриц Q´ и R´ совпадают. Далее осущест­вляем корректировку матриц Q´ и R´ путем применения правила 1, что приводит к за­мене значения признака z равное 10 в 1-ой строке, на значение 11, выделеное полужир­ным шрифтом (рис.2).

 

По матрицам Q´ и R´ построим сокращеную безызбыточную матрицу импликаций, обозначаемую далее через U´´, строка U´´i которой представляет собой значение целочисленной вектор-функции различения,а j- я (j∈{1, 2, ..., m}) компонента u´´ij вычисляется по формуле:

 

где объекты a и b из разных образов, q´a j  ,  q´ b j  - значение признака zj для объекта a (b) из матрицы Q´.

К сожалению, рамки доклада не позволя­ют привести иллюстрирующий пример. От­метим лишь, что при построении k-значных ББДТ   по матрицам   Q и   R (см.   рис.1) с использованием ускоренного шагово-циклического алгоритма, количество строк матрицы импликаций при построении со­кращенной матрицы импликаций сокраща­ется с 303 до 24.

Постановка задачи построения k-значных ББДТ и алгоритм ее реше­ния. Необходимо: по заданным матрицам Q и R в пространстве k-значных признаков построить матрицу U´´, найти все ее безыз­быточные столбцовые покрытия и соответ­ствующие множества характеристических признаков, вошедших в k-значные ББДТ.

Ускоренный шагово-циклический алго­ритм построения k-значных ББДТ осно­вывается на идеи ускоренного шагово-циклического алгоритма построения бинарных ББДТ [3] и состоит из следующих шагов:

Упорядочивание строк матриц Q и R по принадлежности к образам.

Построение матриц Q´ и R´ с использо­ванием формул 2, 3 и, в случае пересече­ния образов, корректировка матриц Q´ и R´ по правилу 1.

Построение матрицы U´´ (формула 4) и вычисление w. по формуле 1. Выделе­ние ядра в матрице U´´ и выявление зако­номерностей по алгоритму, приведенному в статье [1].

Построение ББДТ с использованием ускоренного шагово-циклического алгорит­ма [3].

Конец.

При большом количестве ББДТ предла­гается осуществлять остановку алгоритма по времени, либо по заданному количе­ству тестов. Для приведенного примера построено  8  ББДТ:   [z2,z3,z4},   [z2,z3,z5},  {z2,z4,z6}, {z2,z5,z6}, {z1,z3,z4,z7}, {z1,z3,z5,z7}, {z1,z4,z6,z7}, {z1,z5,z6,z7}.

Заключение

Предложено построение сокращенных матриц описания и различения и ориги­нальный ускоренный шагово-циклический алгоритм построения k-значных ББДТ. Предложенный алгоритм сокращает коли­чество переборных процессов, тем самым уменьшая временные затраты на построение k-значных ББДТ.

Дальнейшие исследования связаны с оценкой эффективности алгоритма, разра­боткой модуля на языке Си++ и включением его в интеллектуальное инструментальное средство ИМСЛОГ [7].

Работа выполнена при поддержке РФФИ (проект № 09-01-99014-рофи).

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

1. Янковская А.Е. Построение k-значных диагностических тестов в интеллектуальной системе с матричным представлением знаний// Сб. научных трудов VI Национальной конф. по искусственному интеллекту с межд. участ. (КИИ-98). Том I. - Пущино, 1998. - С. 264-269.

2.      Янковская А.Е. Логические тесты и средства когнитивной графики в интеллектуальной системе// Новые информационные технологии в исследовании дискретных структур. Доклады 3-ей Всерос. конф. с междунар. участием. - Томск: изд-во СО РАН, 2000. - С. 163-168.

3.   Янковская А.Е. Ускоренный шагово-циклический  алгоритм  построения безызбыточных безусловных диагностиче­ских тестов в интеллектуальном инструмен­тальном средстве ИМСЛОГ-2002// Научная сессия МИФИ-2003. Сборник научных тру­дов. Т. 3. Интеллектуальные системы и тех­нологии. - М.: МИФИ, 2003. - С. 168­169.

4 .Гедике А.И., Янковская А.Е. Постро­ение всех безызбыточных безусловных диагностических тестов в интеллектуаль­ном инструментальном средстве ИМСЛОГ// Интеллектуальные системы (AIS´05). Тр. Межд. научн.-техн. конф. Т.1. - М.: Физ-матлит, 2005. - С. 209-214.

5.    Журавлев Ю.И., Гуревич И.Б. Распо­знавание образов и анализ изображений// Искусственный интеллект. Кн. 2. Моде­ли и методы/ Под ред. Д.А. Поспелова. - М.:Радио и связь, 1990. - С. 149-190.

6.    Янковская А.Е., Китлер С.В. Опти­мизация обработки и хранения k-значной информации в системах искусственного ин­теллекта// Сб. научных трудов Всерос. конф. с элементами научной школы для молодежи «Проведение научных исследований в об­ласти обработки, хранения, передачи и за­щиты информации». Том 2. - Ульяновск: УлГТУ, 2009. - С. 439-447.

7.    Yankovskaya A.E., Gedike A.I., Ame-tov R.V., Bleikher A.M. IMSLOG-2002 Soft­ware Tool for Supporting Information Tech­nologies of Test Pattern Recognition// Pattern Recognition and Image Analysis. - 2003. - Vol. 13. - No. 2. - pp. 243-246.


Библиографическая ссылка

Янковская А.Е., Китлер С.В. УСКОРЕННЫЙ ШАГОВО-ЦИКЛИЧЕСКИЙ АЛГОРИТМ ПОСТРОЕНИЯ K-ЗНАЧНЫХ БЕЗЫЗБЫТОЧНЫХ БЕЗУСЛОВНЫХ ДИАГНОСТИЧЕСКИХ ТЕСТОВ // Международный журнал прикладных и фундаментальных исследований. – 2010. – № 5. – С. 162-167;
URL: https://applied-research.ru/ru/article/view?id=705 (дата обращения: 28.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674