К вычислению весовых коэффициентов признаков в интеллектуальных динамических системах

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

Аннотация

УДК 519.7:007.52;519.81;007.01.362

К ВЫЧИСЛЕНИЮ ВЕСОВЫХ КОЭФФИЦИЕНТОВ ПРИЗНАКОВ В ИНТЕЛЛЕКТУАЛЬНЫХ ДИНАМИЧЕСКИХ СИСТЕМАХ Работа выполнена при частичной финансовой поддержке РФФИ (проект № 04-01-00144), РГНФ (проект № 06-06-12603в).

С.И. Колесникова 634029, Томск, ул. Белинского, 21/1, кв. 50, ТГАСУ, skolesnikova@yandex.ru., А.Е. Янковская 634003, Томск, ул. Читинская, 2, кв. 28, ТГАСУ, yank@tsuab.ru.

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

Введение

В докладе продолжается обсуждение задачи определения весовых коэффициентов характеристических признаков [Журавлев, 1990], актуальной в тестовом распознавании, логическом выводе, используемых в интеллектуальных системах выявления закономерностей и принятия решений. В работах [Янковская и др., 2004a, Янковская и др., 2004b] излагаются как ранее опубликованные, так и вновь предлагаемые методы определения весовых коэффициентов признаков (ВКП) в тестовых распознающих системах, на основе которых построена коллективная оценка, используемая при принятии решения в интеллектуальных системах. В настоящей работе рассматривается задача использования метода вычисления ВКП в форме зависимостей от времени, учитывающего взаимозависимость признаков и основанного на матричной модели представления данных и знаний, формализме мультимножеств [Петровский, 2003], методе анализа иерархий (МАИ) Саати в пространстве, обладающем большой размерностью. Как известно [Саати, 1989, Ногин, 2004], данная задача до сих пор является нетривиальной не только в случае задания предпочтений экспертами вручную, но и в случае, когда относительная важность ВКП вычисляется по предложенным в [Янковская и др., 2004a, Янковская и др., 2004b] формулам. Например, в случае 50-ти признаков, используемых в задачах диагностики, количество парных сравнений составит 1225, что является не только трудоемким процессом, но и проблематичным для хранения такого объема данных в памяти ЭВМ.

1. Основные определения и понятия

Все рассматриваемые методы основаны на известной матричной модели представления данных и знаний, включающей матрицу описаний (Q) объектов в пространстве характеристических и матрицу различений (R) объектов в пространстве классификационных признаков. Элемент q_ij матрицы Q задает значение j-го признака для i-го объекта. Если значение q_ij отмечено символом " - ", то считается, что признак может принимать как нулевые, так и единичные значения, а в случае k-значных признаков - любые целочисленные значения признаков из заданного интервала значений признака. Элемент r_ij матрицы R задает принадлежность i-го объекта одному из выделенных классов по j-му механизму классификации. Множество всех неповторяющихся строк матрицы R сопоставлено множеству выделенных образов. Элементами образа являются объекты, представленные строками матрицы Q, сопоставленными одинаковым строкам матрицы R. Если имеется единственный механизм классификации, матрица различений вырождается в столбец, что соответствует традиционному представлению знаний в задачах распознавания образов.

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

При q_ij{0,1, - } используются следующие определения.

Признаки называются зависимыми, если имеется хотя бы одна пара объектов из разных образов, различаемая этими признаками.

Совокупность признаков, различающих все пары объектов из разных образов (классов), назовем диагностическим тестом (далее слово "диагностический" будем опускать).

Два объекта считаются различимыми, если хотя бы один признак в описании одного из них принимают значение 1 (0), а в описании другого - инверсное (0 (1)).

Авторами предложен подход [Янковская и др., 2004a, Янковская и др., 2004b] и реализующий его метод определения весовых коэффициентов характеристических признаков, используемых в интеллектуальных тестовых распознающих системах. Подход основан на представлении совокупности всех различимых пар объектов из разных образов для каждого признака () в виде мультимножества и применении метода анализа иерархий Саати, использующего парные сравнения критериев (признаков) в матрицах доминирования на основе специальным образом выбранной меры относительной важности признаков, учитывающей их взаимозависимость.

Предложенный метод состоит из трех этапов, на каждом из которых формируется матрица парных сравнений (МПС) признаков (M - количество признаков в тесте) на основе определенной меры относительной важности признака i над признаком j, в качестве которой поэтапно выбираются величины:

, , , (1.1)

где - мощность (общее количество элементов) [Петровский, 2003]i-го мультимножества, соответствующего признаку ; размерность (количество элементов, встречающихся один раз) i-го мультимножества; - разность мультимножеств, соответствующих признакам и ; , если , и , иначе. На s-м () этапе вычисляется М - компонентный вектор значений ВКП -

,

совпадающий со значением нормализованного главного собственного вектора соответствующей матрицы (по Саати - локальные приоритеты). Вектор:

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

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

Для дальнейшего изложения перечислим требования к матрице относительных весов [Саати, 1989]:

1): a_ij > 0;

2) ;

3)

4) число M является максимальным собственным значением матрицы A, и для некоторого единственного (нормированного) вектор-столбец:

а

с положительными компонентами выполняется равенство:

A W = M W.

Из свойства 3) [Ногин, 2004] следует, что при формировании матрицы парных сравнений достаточно получить набор элементов первой строки (в том числе от эксперта), после чего остальные элементы матрицы A можно однозначно вычислить (если позволяет специфика задачи) по формуле:

.

Следуя [Ногин, 2004], будем использовать следующие понятия.

Будем говорить, что некоторый набор элементов матрицы:

,

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

Минимальный (по числу) определяющий набор элементов матрицы А назовем базисным.

2. Постановка задачи

Пусть по матрицам Q и R построены все (часть) безызбыточные тесты, представленные матрицей тестов Т, строки которой сопоставлены тестам, а столбцы - характеристическим признакам, и определено число различающих пар "объект- объект" по каждому характеристическому признаку. Требуется определить весовые коэффициенты характеристических признаков, входящих в объединение всех (части) безызбыточных тестов [Янковская и др., 2004a] с учетом возможной взаимозависимости этих признаков. При этом, не исключается возможность того, что размерность признакового пространства достаточно велика, а весовые коэффициенты признаков могут зависеть от времени. иерархия коэффициент признак пространство

3. Методы формирования матрицы парных сравнений при большом количестве признаков

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

Подход, заключающийся в применении операции кластеризации [Айвазян, 1989], которой подвергается множество признаков (или построении некоторой иерархии важности признаков), и в последовательном построении матриц парных сравнений с вычислением локальных приоритетов признаков в каждой таблице, учитывающихся при получении окончательных значений (первичных) признаков, не умаляет количество требуемых сравнений и, соответственно, вычислений.

Второй подход к решению данной проблемы связан с упрощенным вариантом МАИ [Ногин, 2004], технология применения которого к данной задаче может быть следующая.

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

Первый способ связан с выбором некоторого "идеального" признака-образца, в качестве которого может служить либо признак с наибольшим весом, рассчитанным по формуле, предложенной в [Янковская и др., 2004b], либо объединение всех мультимножеств, порожденных соответствующими признаками (). Далее формируем первую строку на основе соответствующей меры относительной важности (1.1) признака-образца над остальными признаками, элементы которой являются базисными. Остальные элементы МПС находятся из условия, которое обеспечивает выполнение свойства совместности матрицы парных сравнений:

(3.1)

Тогда компоненты весового ненормализованного вектора:

(верхний индекс "У" означает "упрощенный"), следуя теореме 1 [Ногин, 2004], вычисляются по формуле:

(3.2)

Таким образом, компоненты весового вектора составляют последний столбец МПС А, элементы которой получены по формуле (3.2).

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

Второй способ предполагает следующий набор базисных элементов: , который реализует схему последовательного сравнения (некоторый "идеальный образец" сравнивается с 1-м, затем 1-й сравнивается со вторым, и т.д.). Сформулируем основные результаты.

Теорема 1. Пусть МПС построена по следующим правилам:

1) элементы являются базисными и определяются по формуле:

, ; (3.3)

2) остальные элементы определяются по формуле:

, . (3.4)

Тогда МПС удовлетворяет всем требованиям относительных весов 1) - 4), и компоненты ненормированного собственного вектора определяются по формуле:

,

Теорема 2. Если матрица парных сравнений:

с элементами, определяющимися по формуле (1.1), удовлетворяет всем требованиям относительных весов 1) - 4), то ее собственный вектор совпадает с собственным вектором МПС, элементы которой вычислены по формулам (3.3), (3.4).

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

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

Рассмотрим пример, где представлены численные значения весовых коэффициентов признаков, полученных по методу, основанному на мультимножествах и МАИ, следуя [4], и методу, использующему упрощенный МАИ, а также их численное сравнение. Ввиду громоздкости МПС при большой ее размерности и ограничения на объем доклада, а также имея в виду, что интерес, главным образом, представляет: а) погрешность в точности получаемых оценок по данным методам, т.е. |W^М - W^У|, где W^М - нормализованный собственный вектор МПС по методу, основанному на мультимножествах и МАИ, W^У - нормализованный собственный вектор МПС по упрощенному МАИ; б) факт совместности МПС или значение индекса согласованности в указанных методах, а значит:

,

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

Рис. 1. Матрицы описаний Q, различений R и тестов T

В матрице парных сравнений признаков на основе меры относительной важности расположим признаки по невозрастанию мощностей соответствующих разностей мультимножеств (табл. 1), учитывая, что:

|P₅ - P₉|=13, |P₉ - P₅|=15, |P₅ - P₁₁|=14, |P₁₁ - P₅|=14, |P₉ - P₁₁|=10, |P₁₁ - P₉|=8.

Соответствующая МПС признаков на основе указанной меры относительной важности имеет вид: