Logical inference on the base of optimal subset of mixed diagnostic tests for intelligent systems.pdf Существует широкий круг проблемных областей, для которых характерно последовательноеуточнение решений, принимаемых относительно исследуемых объектов,где описания объектов задаются сотнями и даже тысячами признаков. Поэтому весьмаактуальной является разработка алгоритмов сокращения признакового пространства,необходимого для принятия решений, и поэтапного логического вывода решенийв ориентированных на подобные задачи интеллектуальных системах. Существеннымипри этом являются такие параметры, как повышение быстродействия и уменьшениетрудоемкости (стоимости) принятия решений, естественно, без потери качества принимаемыхрешений.В рамках развиваемого логико-комбинаторного подхода к принятию решений, базирующегосяна матричной модели представления данных и знаний и построении логическихтестов [1], по каждому из которых осуществляется логический вывод, сокращениепризнакового пространства достигается построением на основе многокритериальноговыбора оптимального подмножества (ОП) безызбыточных безусловных диагностическихтестов (ББДТ) [2].В [3] обоснована целесообразность использования смешанных диагностических тестов(СДТ), представляющих собой оптимальное сочетание безусловных и условныхсоставляющих [4], что позволяет одновременно с построением СДТ принимать решенияпри меньших вычислительных и стоимостных затратах.В [5] предложен алгоритм построения СДТ на основе ОП ББДТ.Для представления данных и знаний используются матрицы описаний (Q) в пространствехарактеристических признаков и матрицы различений (R) в пространствеклассификационных признаков, которым сопоставлены различные механизмы классификации.Элемент qjj матрицы Q принимает значения из множества {0,1, - } , где единица(ноль) означает, что j -й признак присущ (не присущ) i-му объекту, а прочерк означает,что значение признака безразлично для данного объекта, т. е. оно может равнятьсяи 0, и 1. Элементы целочисленной матрицы R интерпретируются как номера классов,которым принадлежат объекты по соответствующим механизмам классификации.Считается, что объекты, для которых заданы одинаковые решения, сопоставленныестрокам матрицы R, принадлежат одному и тому же образу, а число образов равночислу различных решений.ОП ББДТ представляется двоичной матрицей T o, строки которой сопоставляютсятестам, столбцы - признакам, входящим во все тесты (единица означает, что признаквходит в соответствующий этой строке тест). Отметим, что в процессе анализа обучающихобъектов вычисляются весовые коэффициенты признаков (ВКП), характеризующиеих вклад в различимость объектов из разных образов.Будем называть ядром (G) подмножество признаков, входящих в каждый тест изОП ББДТ. Ядро образует безусловную составляющую всех СДТ, которые могут бытьпостроены по ОП ББДТ.Описание исследуемого объекта формируется путем последовательного ввода значенийзапрашиваемых признаков, входящих в очередной тест, из множества {0, 1, - } ,где прочерк (в отличие от матрицы Q) означает, что значение признака неизвестно,т. е. равно или 0, или 1.Реакцией матрицы Q на i-й тест называется подмножество строк матрицы Q, в которыхзначение 0 (или 1) каждого признака, входящего в тест, совпадает со значением0 (или 1) вводимых признаков. Считается также, что значение « -» соответствующегоэлемента матрицы Q совпадает со значением 0 (или 1) вводимого признака.Если же значение вводимого признака равно « - » , то нужно строить две реакции: ипо значению 0, и по значению 1. Реакция матрицы Q на тест строится в виде последовательностиреакций матрицы Q на значения уже введенных на текущий моментпризнаков.Предлагается осуществлять логический вывод в процессе построения дерева СДТ.Корню дерева сопоставляется матрица Q и приписываются номера признаков, входящихв ядро G. Если G = 0 , то корню дерева СДТ приписывается номер признака,выбранного первым для ввода. Ребрам, ведущим к первому ярусу, приписываютсязначения всех введенных на текущий момент признаков.Вершинам первого яруса сопоставляются реакции матрицы Q на значения ведущихк ним ребер и приписываются значения, равные номерам признаков, выбранныхдля ввода. Ребрам, выходящим из этих вершин, приписываются последовательностизначений введенных на текущий момент признаков.Аналогично вершинам следующих ярусов сопоставляются реакции матрицы Q назначения ведущих к ним ребер и приписываются (кроме концевых вершин) значения,равные номерам признаков, выбранных для ввода. Ребрам, выходящим из этихвершин, приписываются последовательности значений введенных на текущий моментпризнаков.Каждой концевой вершине соответствует реакция, содержащая строки, сопоставленныетолько одному образу, номер которого приписывается этой вершине. Отметим,что концевые вершины могут достигаться на подмножествах признаков, входящихв тест.При построении дерева СДТ существенное значение имеет очередность рассмотрениякак ББДТ, так и признаков, входящих в каждый из них. Для выбора очередногоББДТ из матрицы T o и очередного признака в ББДТ предлагаются следующие критерии.Критерий 1. Выбирается неотмеченная строка матрицы T o, имеющая наименьшеечисло неотмеченных признаков. Если таковых несколько, то выбирается строка снаибольшей суммой весовых коэффициентов неотмеченных признаков. Если же таковыхтоже несколько, то выбирается строка с наименьшим номером.Критерий 2. Выбирается неотмеченный признак в строке матрицы To, для которогов соответствующем столбце имеется наибольшее число единиц в неотмеченныхстроках. Если таковых несколько, то выбирается признак с наибольшим весовым коэффициентом.Если же таковых тоже несколько, то выбирается признак с наименьшимномером.Критерии 1 и 2 позволяют сокращать перебор и, как правило, строить дерево СДТне по всем ББДТ из ОП, что снижает вычислительные затраты.Построение каждого СДТ выполняется в интерактивном режиме одновременнос принятием решения относительно исследуемого объекта на основе голосов, отданныхсоответствующим тестом за образы. Если для некоторых ББДТ из ОП значения всехпризнаков уже известны, но эти ББДТ не участвовали в построении дерева СДТ, тона их основе тоже принимаются решения.Сначала строится одна ветвь дерева СДТ по одному из БДДТ, представленномустрокой матрицы T o. При этом все запрашиваемые для ввода признаки отмечаются.Затем последовательно строятся все возможные ветви по другим БДДТ с учетом значенийранее введенных и отмеченных признаков. Строки матрицы T o, по которымстроятся СДТ, тоже отмечаются.Если при формировании описания исследуемого объекта ни один вводимый признакне принимает значение « - » , то каждый СДТ задает единственный путь от корняк концевой вершине, иначе появляются разветвления. В первом случае голос, отданныйтестом за образ, принимается равным единице. Во втором случае голос, отданныйтестом за каждый образ, делится пропорционально количеству концевых вершин дляданного СДТ.Процесс построения дерева СДТ заканчивается, когда будутотмечены все признаки,сопоставленные столбцам матрицы T o. Если при этом в матрице T o останутсянеотмеченные строки, то для соответствующих этим строкам ББДТ ищутся пути в ужепостроенном дереве СДТ с одновременным подсчетом голосов, отданных этими тестамиза образы. Итоговым решением является принадлежность исследуемого объектаобразу, получившему наибольшее число голосов.Результаты испытаний алгоритма на тестовых примерах позволяют сделать вывод,что предлагаемый алгоритм построения ОП СДТ является эффективным по быстродействию,так как позволяет сократить перебор (поскольку длина СДТ не больше длиныББДТ и принятие решения осуществляется одновременно с построением СДТ) [3],а также дает возможность строить дерево СДТ не по всем ББДТ из ОП, что существенноснижает вычислительные затраты. В настоящее время ведется работа попрограммной реализации алгоритма построения ОП СДТ с одновременным принятиемрешений в интеллектуальном инструментальном средстве ИМСЛОГ [6], являющемсяинтегрированной средой разработки прикладных интеллектуальных систем.

Скачать электронную версию публикации