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

Размещено на http://www.allbest.ru/

Томский государственный архитектурно-строительный университет, Томск

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

А.Е. Янковская

С.В. Китлер

Задача построения отказоустойчивых диагностических тестов (ДТ) не нова и впервые возникла при синтезе дискретных автоматов и применена для помехоустойчивого кодирования внутренних состояний асинхронных автоматов (устойчивых к отказам элементов памяти) [Янковская, 1968]; [Закревский и др., 1971]. Однако она не потеряла своей актуальности при создании интеллектуальных систем (ИС), а также для анализа баз знаний ИС с матричным представлением знаний [Янковская, 1990] и далее развита применительно к задаче построения ДТ с учётом ошибок измерения значений признаков (отказоустойчивых тестов) [Янковская, 2009a]. Алгоритм построения k-значных ДТ в ИС с матричным представлением знаний, изложен в статье [Янковская, 1998].

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

Основные понятия и определения. Матричная модель. Закономерности в данных и знаниях

Воспользуемся определениями и понятиями [Янковская, 1998]; [Журавлёв и др., 1990]; [Янковская, 2000].

Тестом называется совокупность признаков, различающих любые пары объектов, принадлежащих разным образам.Тест называется безызбыточным (тупиковым [Журавлёв и др., 1990]), если содержит безызбыточное количество признаков. Безызбыточный безусловный ДТ (ББДТ) характеризуется одновременным предъявлением всех входящих в него признаков исследуемого объекта при принятии решений.

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

Будем говорить, что f-я строка целочисленной матрицы поглощаетl-ю строку

,

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

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

Используемая нами матричная модель представления данных и знаний включает целочисленную матрицу описаний (Q), задающую описание объектов в пространстве характеристических признаков z₁,z₂,...,z_m и целочисленную матрицу различений (R), задающую разбиение объектов на классы эквивалентности по каждому механизму классификации. Если значение признака несущественно для объекта, то данный факт отмечается прочерком ("-") в соответствующем элементе матрицы Q. Множество всех неповторяющихся строк матрицы R сопоставлено множеству выделенных образов, представленных одностолбцовой матрицейR', элементами которой являются номера образов.В данной модели недопустимо пересечение описаний объектов из разных образов.

На Рис. 1 приведён пример матричной модели данных и знаний.

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

Рис. 1. Матрицы Q, Rи R'

Построение формулы вычисления весовых коэффициентов признаков. Основы построения отказоустойчивых тестов

Построим формулу для вычисления весового коэффициентаw_j целочисленного признака z_j по его разделяющей способности аналогично формуле для вычисления w_j для двоичного признака z_j[Янковская, 2000].

, (2.1)

где K - число выделенных образов; N_c - число строк в описании c-го образа (c{r, s}); , где q_aj (q_bj) - значение признака z_jиз образа a(b), a ? b; s_a- число объектов в образеa (a=1, ..., K), вычисляемое по формуле: (d- интервал измерения j-го признака, принимающего значение "-" в l-ой строке матрицы Q, p_l - коэффициент повторения l-ой строки, S_l - количество строк, принадлежащих образу a, в которых содержится хотя бы один признак со значением "-").

Для построения k-значных отказоустойчивых ББДТ применяется построение матрицы импликаций [Янковская, 1998]; [Янковская, 2000], представляющей собойцелочисленную матрицуU, столбцы которой сопоставлены столбцам матрицы Q, а строки - всевозможным парам объектов v, l из разных образов a, b соответственно; v{1,2,...,у(Q^a)}, l{1,2,...,у(Q^b)}, где у(Q^a) (у(Q^b)) - количество строк в подматрице Q^a (Q^b) матрицы Q. Строка U_i (i{1,2,...,n})матрицы U представляет собой значение целочисленной вектор-функции различения, j - я (j{1,2,...,m}) компонента u_ij которой вычисляется по формуле:

, (2.2)

где () - значение признака z_j для объекта v (l), а u_ijвычисляется для каждой пары образов.

Отметим, что если один из признаков или оба признака принимают значение "-", то результат операции (формула 1) будем считать равным 0, что обусловлено дальнейшим исключением при построении безызбыточной матрицы импликации (U') строки U_i, порождаемой наличием строки (строк) в матрице Q, используемой (используемых) при нахождении соответствующих вектор-функций различения.

Построение сокращённых матриц описания, различений и безызбыточной матрицы импликаций

Для сокращения перебора при построении k-значных отказоустойчивых ДТ в публикации [Янковская и др., 2009b] предложено использовать целочисленные сокращённые матрицу описания (Q') и матрицу различений (R'').

Предлагается итеративная процедура построения матриц Q' и R''.

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

, (3.1)

, (3.2)

где - значение признака z_j для объекта l {1, 2, …, r_c} из образа c, а r_c - количество объектов, принадлежащих образу c.

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

На 2-м шаге построения при пересечении образов в строящейся матрице Q' будем использовать правило, являющееся модификацией правила [Янковская и др., 2009b] и применяемого при построении ДТ без учета ошибок измерения значений признаков.Модификация связанна с учётом числа t ошибок измерения значений признаков, от которого зависит величина h (h = t + 2), указанная в приведённом ниже достаточном условии построения отказоустойчивых ББДТ.

Модифицированное правило:если строка в матрице Q'из образа c различается со строкой из образа e (c ? e) меньше чем на hзначений признаков, то заменяются все строки матриц Q' и R'' из образов c, e строками матриц Q и R' из образов c, e соответственно.

Модифицированное правило будем применять до тех пор, пока в строящейся матрице Q' не останется строк, принадлежащих разным образам и отличающихся менее чем h элементами. При невозможности такого построения необходимо расширить признаковое пространство, т.е. доопределить матрицу Q. Строки, отличающиеся h одноимёнными элементами, будем называть h-различимыми. Это правило справедливо только для репрезентативной обучающей выборки, представленной матрицами Q и R', и приводит к корректировке матриц Q' и R''.Далее скорректированные матрицы обозначим через Q'' и R''' соответственно.

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

, (3.3)

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

Сформулируем теорему, на основе которой будем осуществлять построение k-значных отказоустойчивых ББДТ.

Теорема.Для построения ББДТ, устойчивого к числу tошибок измерения (занесения) характеристических признаков, в матрице Q'' для каждой пары объектов из разных образов достаточно обеспечение условия f(U''_i) ?h (h = t+2) для любой строкиU''_Iматрицы U, где i{1,2,...,у(U'')}, а у(U'') - количество строк в матрице U''.

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

Алгоритм ускоренного построения k-значных отказоустойчивых ББДТ

Приведём алгоритм ускоренного построения отказоустойчивых ББДТ.

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

2. Построение по матрицам QиR'матрицы U' (с применением формулы2.2) и вычисление w_i по формуле 2.1.

3. Построение по матрицам QиR' сокращённых матриц Q'иR'' с использованием формул 3 и 4.

4. При пересечении в матрице Q'образов по h признакам, корректировка по модифицированному правилу совпадающих строк матриц Q'иR' до тех пор, пока в матрице Q' будут отсутствовать h-различимые строки. При невозможности такой корректировки переход к пункту 9. Обозначение скорректированных матриц через Q'' и R'''.

5. Построение по формуле 5 матрицы U'' на основе матриц Q'' и R''' с одновременным удалением поглощающих строк в матрице U''и вычислением весовых коэффициентов признаковпо формуле 1.

6. Построение всех безызбыточных h-кратных столбцовых покрытий матрицы U'' либо части при превышении числа безызбыточных h-кратных столбцовых покрытий в процессе их построениязаданной величины g.

7. Проверка, является ли каждое безызбыточное h-кратное столбцовое покрытие матрицы U'' таковым для матрицы U' и исключение из матрицы U''тех безызбыточных h-кратных столбцовых покрытий, для каждого из которых покомпонентная сумма элементов столбцов матрицы U'содержит хотя бы один нулевой элемент.

8. Построение по оставшимся безызбыточным h-кратным столбцовым покрытиям матрицы U''всех отказоустойчивых ББДТ. Переход к п. 10.

9. Доопределение матрицы Q и переход к пункту 2.

10. Конец.

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

Учёт весовых коэффициентов признаков приведёт к сокращению перебора при построении отказоустойчивых ББДТ.

Иллюстративный пример

Пусть заданы матрицы Q и R' (Рис. 1) и диапазон изменения значений следующих признаков: значение 1-го изменяется от 1 до 5, 2-го - от 4 до 7, 3-го - от 3 до 6, 4-го - от 6 до 9, 5-го - от 1 до 6, 6-го - от 1 до 7, 7-го - от 2 до 8, 8-го - от 4 до 8. Необходимо построить ББДТ при t=1 (h=3).

Шаг 1. Упорядочим строки матриц Q и R'(Рис. 2).

Шаг 2. Построим матрицу U'(п.2 алгоритма) и вычислим w_i. Вычисление w_i опустим, поскольку рамки статьи ограничены.

Шаг 3. Построим матрицы Q'иR'' в соответствии с п. 3 алгоритма. При построении матриц Q'иR'' в матрице Q'совпали строки: 1-я и 5-я (п. 4 алгоритма).Поскольку для данного примера обучающая выборка не репрезентативна, применение модифицированного правила не имеет смысла. Поэтому для иллюстрации дальнейших пунктов алгоритма применим правило, приведённое в статье [Янковская и др., 2009b]. В результате получим скорректированные матрицы Q'' и R'''(Рис. 3).

Рис. 2. Упорядоченные матрицы Q, Rи R'

Рис. 3. Скорректированные матрицы Q''и R'''

Шаг 4. Построим безызбыточную матрицу U''(формула 3.3) в соответствии с п. 5 алгоритма (Рис. 4).

Шаг 5. В соответствии с п. 6 алгоритмапостроим безызбыточные 3-кратные столбцовые покрытия матрицы U''.В результате выполнения шага 5 получим следующиебезызбыточные 3-кратные столбцовые покрытия матрицыU'': {1,2,3,4,5,6,7}, {2,3,5,6,7,8}, {2,3,4,5,6,8}, {2,3,4,5,7,8}. Признаки z₆и z₇ являются альтернативными.

Шаг 6: Проверим, являются ли найденные безызбыточные 3-кратные столбцовые покрытия матрицы U'' безызбыточными 3-кратными столбцовыми покрытиями для матрицы U', и исключим те из матрицы U'', которые не являются таковыми для матрицы U' (п. 7 алгоритма).

Рис. 4. Матрица U''

По оставшимся безызбыточным 3-кратным столбцовым покрытиям на основе применения п. 8 алгоритма построим отказоустойчивые ББДТ T₁={z₂,z₃,z₄,z₅,z₆,z₈}, T₂={z₂,z₃,z₄,z₅,z₇,z₈}.

Описание интеллектуальной системы

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

Предлагаемая ИС реализована в виде динамически подключаемого модуля к интеллектуальному инструментальному средству (ИИС) ИМСЛОГ [Yankovskaya et al., 2002], на базе которого строятся прикладные интеллектуальные системы. Модуль разработан на основе программой среды BuilderC++. Входными данными модуля являются матрицы Qи R, заданное число tошибок измерения, диапазон измерения характеристических признаков. Выходными данными являются все (либо часть при большом признаковом пространстве) k-значные отказоустойчивые ББДТ. Библиотека классов модуля содержит математические объекты (k-значные векторы и матрицы), динамически создаваемые, обрабатываемые и удаляемые по мере необходимости.

Программная реализация ИИС ИМСЛОГ выполнена с использованием системы программирования BorlandC++ Builder, а также API и GUI операционной среды Windows.

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

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

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

Благодарности. Работа выполнена при финансовой поддержке РФФИ (проект № 10-01-00462-а) и РГНФ (проект № 10-06-64604а).

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

отказоустойчивый диагностический тест дискретный

1. [Закревский и др., 1971] Закревский А.Д., Янковская А.Е. Помехоустойчивое кодирование внутренних состояний асинхронного автомата// Информационные материалы. - М.: ВИНИТИ, Ип., 1971. № 3 (50).

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

3. [Янковская, 1996] Янковская А.Е. Функции различения при анализе БЗ интеллектуальных систем с матричным представлением знаний// Искусственный интеллект-90. Тезисы докладов II Всесоюзной конференции. Том 1. - Минск, 1990.

4. [Янковская, 2009a] Янковская А.Е. Принятие решений, устойчивых к ошибкам измерения значений признаков в интеллектуальных системах// Искусственный интеллект. Интеллектуальные системы (ИИ-2009)// Материалы X Междунар. научно-технической конф. - Таганрог: Изд-во ТТИ ЮФУ. 2009.

5. [Янковская, 1998] Янковская А.Е. Построение k-значных диагностических тестов в интеллектуальной системе с матричным представлением знаний// Сборник научных Трудов VI Национальной конф. по искусственному интеллекту с международным участием Т. I, Пущино. 1998.

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

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

8. [Янковская, 1968] Янковская А.Е. Помехоустойчивое кодирование внутренних состояний асинхронных автоматов// Тез. докл. 3-го Симп. по использованию избыточности в информационных системах. - Ленинград, 1968. - С. 61-63.

9. [Yankovskayaet al., 2002] Yankovskaya A.E., Gedike A.I., Ametov R.V., Bleikher A.M. IMSLOG-2002 Software Tool for Supporting Information Technologies of Test Pattern Recognition// Pattern Recognition and Image Analysis. 2003. Vol. 13. No. 2.

Размещено на Allbest.ru