Выбор логических закономерностей для построения решающего правила распознавания

Полный текст

Постановка задачи отбора закономерностей. К настоящему времени разработаны довольно эффективные алгоритмы классификации для решения задач диагностики и прогнозирования, которые при умелой настройке решают задачи с большой точностью. Но при практическом применении таких алгоритмов зачастую встает вопрос об интерпретируемости и доказательности результатов. Для принятия решений требуется модель в явном виде, такая модель, в которой вычисляемые решения обоснованы и опираются на имеющиеся данные. В данной работе строится модель принятия решений, состоящая из набора логических правил, которые описывают закономерности в исследуемом явлении или системе. Основная задача - выявить эти закономерности и привести к виду, в котором они будут использованы для построения модели принятия решений. Выявление закономерностей на основе имеющегося набора данных является сложной вычислительной задачей, требующей эффективного алгоритмического обеспечения и его программной реализации. Но получаемые классификаторы способны эффективно решать практические задачи [1; 2], в том числе в аэрокосмической отрасли [3; 4]. Процесс формирования решающих правил сопровождается решением задач выбора наилучших альтернатив в соответствии с некоторым критерием. Формализация этого процесса в виде ряда задач комбинаторной оптимизации формирует гибкий и эффективный алгоритм логического анализа для классификации данных. Рассмотрим задачу распознавания объектов, описываемых бинарными признаками и разделенных на два класса K = K + u K- с {0,1}n . Объект X є K описывается бинарным вектором X = (х1,х2, ... xn) и может быть представлен как точка в гиперкубе пространства бинарных признаков B2n . Под закономерностью P (или правилом) понимается терм, который покрывает хотя бы один объект некоторого класса и не покрывает ни одного объекта другого класса. То есть закономерность соответствует подкубу, имеющему непустое пересечение с одним из множеств (K+ или K-) и пустое пересечение с другим множеством (K- или K+ соответственно). Закономерность P, которая не пересекается с K-, будем называть положительной, а закономерность P’, которая не пересекается с K + - отрицательной. Закономерности являются элементарными блоками для построения логических алгоритмов распознавания. Предположим, что в результате выполнения процедуры поиска закономерностей по обучающей выборке найден ряд положительных закономерностей Pi, i = 1, ..., p, и отрицательных закономерностей Nj, j = 1, •••, n. Решающая функция может быть задана выражением D(a) = - £ Pi (a) -1 £ Nj (a) p i=1 n j=1 для некоторого объекта a, где Pi(a) = 1, если закономерность Pi покрывает объект a, и Pi(a) = 0 в противном случае. То же самое для Nj(a). В [5] описаны алгоритмы поиска закономерностей. В частности, это алгоритмы, которые ведут поиск закономерности, опираясь на некоторый объект обучающей выборки. Поэтому в результате их работы может быть записано большое число закономерностей, вплоть до числа объектов обучающей выборки, некоторые из которых, впрочем, могут повторяться. При решении многих задач встает вопрос отбора закономерностей из общего их числа для формирования решающего правила, что способно не только уменьшить его размер, но в некоторых случаях и улучшить распознавание. Основное преимущество, которое предоставляют логические алгоритмы распознавания при решении практических задач, - это прозрачность процесса распознавания новых объектов по полученной модели. Все выявленные закономерности представлены в явном виде. Но если этих закономерностей много, более, допустим, 10-15, то алгоритм распознавания становится трудно интерпретируемым. В связи с этим исследуем некоторые способы отбора из общего числа найденных закономерностей. Минимизация числа закономерностей. Введем переменные, определяющие, будет ли закономерность присутствовать в решающей функции: Г1, P присутствует в решающей функции, Xi = In [0, в противном случае; 1, Nj присутствует в решающей функции, 0, в противном случае. Один из способов произвести отбор закономерностей - выделить подмножество закономерностей, которые необходимы для покрытия всех объектов обучающей выборки [6]. Каждый объект обучающей выборки должен при этом покрываться хотя бы одной закономерностью. Используя введенные переменные, это условие можно записать в виде p £ xiPi (a) > 1 для любого a є K +, i=1 n £yjNj (a) > 1 для любого a є K- . j=1 Для повышения робастности алгоритма число 1 в правой части неравенств следует заменить целым положительным числом d. В таком случае каждый объект обучающей выборки должен подчиняться заданному количеству d закономерностей. Таким образом, имеем следующую задачу минимизации числа используемых в решающем правиле закономерностей: p q Xx +XУ] ^min і=1 ]= 1 при ограничениях на переменные: p X xiPi (a) > d для любого a є K +, i=1 n X УjN] (a) > d для любого a є K- . j=1 Полученная оптимизационная модель представляет собой задачу условной псевдобулевой оптимизации, в которой целевая функция и функции в ограничениях являются унимодальными монотонными псевдобулевыми функциями [7]. Для решения задачи использовались приближенные алгоритмы условной псевдобулевой оптимизации, основанные на поиске оптимального решения среди граничных точек допустимой области [8]. Для того чтобы оценить, как влияет уменьшение числа закономерностей в решающем правиле на точность распознавания, была проведена серия экспериментов на задачах распознавания и прогнозирования. Поиск закономерностей производился на основе оптимизационной модели [9], позволяющей находить максимальные закономерности, т. е. закономерности с наибольшим покрытием объектов некоторого класса. Каждая выборка данных была разделена на две части - обучающую и тестовую. На основе каждого объекта обучающей выборки производился поиск закономерности. Проводилось сравнение качества распознавания решающих правил, построенных из полного набора закономерностей и из уменьшенного набора, полученного путем решения описанной выше оптимизационной задачи. При проведении экспериментов использовались следующие задачи распознавания [10]: - breast-cancer - задача диагностики рака молочной железы, объем выборки - 699 объектов, описываемых 9 разнотипными признаками (в результате бинаризации получено 80 бинарных признаков); - wdbc - задача диагностики рака молочной железы, объем выборки - 569 объектов, описываемых 30 разнотипными признаками (120 бинарных признаков); - hepatitis - задача диагностики наследственного гепатита, объем выборки - 155 объектов, описываемых 19 разнотипными признаками (37 бинарных признаков); - spect - данные по сердечной компьютерной томографии объем выборки - 80 объектов, описываемых 22 бинарными признаками. Результаты экспериментов приведены в табл. 1. Как видно, применение решающего правила, основанного на уменьшенном наборе закономерностей, в некоторых задачах приводит к незначительному снижению качества распознавания, но в то же время сопровождается значительным снижением числа закономерностей, которые необходимо использовать для принятия решения, что положительно сказывается на прозрачности получаемых решений. Максимизация разделяющей полосы. Еще один способ заключается в том, чтобы произвести отбор таких закономерностей, которые при совместном использовании увеличат разделяющую способность решающего правила. Таблица 1 Результаты распознавания Задача распознавания Набор закономерностей Число положительных закономерностей Число отрицательных закономерностей Точность распознавания положительных объектов Точность распознавания отрицательных объектов Breast-cancer Полный набор 419 209 0,97 0,91 Уменьшенный набор 12 14 0,97 0,88 Wdbc Полный набор 291 163 0,94 0,98 Уменьшенный набор 9 11 0,92 0,96 Hepatitus Полный набор 27 97 0,8 0,85 Уменьшенный набор 7 7 0,8 0,81 Spect Полный набор 38 34 1 0,83 Уменьшенный набор 7 8 1 0,83 a z ba D'(a) В качестве критерия при формировании решающего правила рассмотрим ширину «разделяющей полосы»: min{D(a): а є K + } - max{D(a): a є K- }, 1 p 1 n где D(a) = - V Рг (a) - V Nf (а) для некоторого P г=1 n j=1 объекта a. Учтем наличие выбросов, которые могут присутствовать в реальных задачах. Для этого введем переменную 1, a принимается за выброс, 0, в противном случае. Тогда задачу отбора закономерностей можно записать в следующем виде: v+ + v~ -C V za • \ba\ ^ max , aєK где v+ = min{D'(a): a є K +, za = 0}, v = min{-D '(a): a є K , za = 0}, V ХгРг (a) V PjNj (a) г =1 j =1 p _n Vx. Vyj г=1 j=1 v+ - D' (a), a є K +, v~ + D' (a), a є K-. Алгоритмы для решения таких задач оптимизации приведены в [11]. Декомпозиция обучающей выборки при выявлении закономерностей. Рассматриваемые в работах [12; 13] способы поиска закономерностей предполагают использование в качестве «опорной точки» объект обучающей выборки (прецедент), частичное повторение свойств которого может быть обнаружено в других объектах этого же класса. Описанный выше способ предписывает использовать большое число таких опорных объектов (возможно, всех объектов обучающей выборки) для получения закономерностей, а затем проводить отбор из найденных. Рассмотрим другой способ, заключающийся в отборе самих этих опорных объектов. Всё множество объектов обучающей выборки некоторого класса, скажем K+, можно разбить на группы объектов так, чтобы объекты были схожи внутри каждой группы: K + = K+u K2+u... u K+. Для этого можно использовать алгоритм k-средних, в результате работы которого получаем набор центроидов Cj,c2,...,ck так, что будет выполняться правило a є K+, если ||a - Cj для всех i = 1, 2, ..., k , i Ф j, где Kjj - множество объектов, входящих в кластер с центроидом c j . Эти центроиды можно использовать в качестве опорных объектов для выявления логических закономерностей. Описанный подход позволяет существенно снизить трудоемкость работы логического алгоритма распознавания, производя отбор объектов, используемых в качестве опорных при поиске закономерностей. Рассмотрим результаты использования этого подхода применительно к задаче прогнозирования осложнений инфаркта миокарда: фибрилляции предсердий (ФП) и фибрилляции желудочков (ФЖ) [14]. Для нахождения центроидов использовался алгоритм k-средних программного приложения Weka [15], для поиска закономерностей и оценки точности построенного решающего правила использовалось авторское программное обеспечение. Выборка для задачи ФП состояла из 184 положительных и 184 отрицательных объектов, описываемых 112 разнотипными признаками. Число бинаризованных признаков составило 215. Для каждого класса выделено по 15 центроидов, которые использовались для поиска закономерностей. Выборка для задачи ФЖ состояла из 80 положительных и 80 отрицательных объектов, описываемых 112 разнотипными признаками. Число бинаризованных признаков составило 200. Для каждого класса выделено по 10 центроидов, которые использовались для поиска закономерностей. 10 % объектов выборки было выделено для тестирования полученного решающего правила. Результаты распознавания приведены в табл. 2. В результате использования декомпозиции объектов обучающей выборки и соответствующего отбора объектов, используемых в качестве опорных для поиска закономерностей, получаем упрощение решающего правила - число используемых в решающем правиле закономерностей уменьшается в 7-10 раз. При этом для некоторых задач наблюдается даже увеличение точности распознавания тестовых объектов. < a - c. Заключение. Подводя итог, следует заключить, что отбор логических закономерностей, произведенный в соответствии с некоторым критерием, позволяет значительно снизить их число и упростить решающее правило, лишь немного снижая точность распознавания. При решении ряда практических задач распознавания и прогнозирования большое значение имеет интерпретируемость получаемых решений и возможность их обосновать, опираясь на правила и закономерности, которые, в свою очередь, основаны на прецедентах в виде объектов выборки данных. Поэтому использование описанных в этой работе подходов представляется полезным для решения таких задач. Сравнение результатов распознавания Таблица 2 Задача распознавания Набор закономерностей Число положительных закономерностей Число отрицательных закономерностей Точность распознавания положительных объектов Точность распознавания отрицательных объектов ФП Полный набор 165 165 0,7 0,79 Уменьшенный набор 15 15 0,68 0,77 ФЖ Полный набор 72 72 0,87 0,71 Уменьшенный набор 10 10 0,9 0,88

Об авторах

Александр Николаевич Антамошкин

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева Российская Федерация

Email: oleslav@mail.ru
доктор технических наук, профессор, профессор кафедры системного анализа и исследования операций 660014, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

Игорь Сергеевич Масич

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева Российская Федерация

Email: i-masich@yandex.ru
кандидат физико-математических наук, доцент 660014, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

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

Дополнительные файлы