TECHNOLOGY OF FORMING «AND/OR» SOLVING TREE FOR PROBLEMS OF THE IMAGES ANALYSIS

Abstract

It is offered a new technology of forming «AND/OR» tree, allowing user-naturalist to form the knowledge base and«AND/OR» tree of expert system without using component «extraction of knowledge». The new algorithm of forming«AND/OR» tree, based on uniting solving «AND» trees for class of problems, is developed. Convergence of such process is proved.

Full Text

Доминирующая в настоящее время технология корректировки базы знаний экспертной системы под- держивается компонентом ЭС «извлечение знаний», пользователем которой является когнитолог. При этом обобщенное дерево решения задач ЭС должно быть задано априори [1]. В этих условиях актуальной явля- ется разработка технологии формирования адекватной базы знаний и соответствующего «И/ИЛИ» дерева, обеспечивающих проблемную ориентацию ЭС, ориен- тированную на работу с пользователем-природоведом. image 1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (код проекта 07-01-00326) и аналитической целевой программы Министерства образования и науки (РПН.3.1.1.5349). Описание цели представляет собой кластер, задан- ный в некотором признаковом пространстве X(x1, x2, …, xn) значениями эталона E(e1, e2, …, en) и критерия компактности е. Пусть задано «И/ИЛИ» дерево, представляющее собой граф редукции исходной цели, полученной от пользователя, на подцели. Корневая вершина дерева соответствует описанию исходной цели, т. е. кластеру в пространстве целей. Дочерние вершины каждой вершины дерева соответствуют описаниям подцелей, для цели, описываемой данной вершиной. Концевые вершины, не имеющие дочерних вершин, соответст- вуют описаниям элементарных целей, не разбиваемых на подцели. Между ребрами «И/ИЛИ» дерева существуют отношения. Это отношения «И» и «ИЛИ», в зависимо- сти от того, должна ли быть достигнута только одна из подцелей текущей цели или же несколько из них. В общем случае из вершины могут выходить ребра, на- ходящиеся в отношении «И» вместе с ребрами, нахо- дящимися в отношении «ИЛИ». Всякое «И/ИЛИ» де- рево можно привести к виду, когда каждая вершина image кластеру (рис. 1). То есть с (E1, E2) < min (е1, е2), где с(E1, E2) - евклидово расстояние между E1 и E2 в про- странстве X. A1 A2 А2 А1 Рис. 1. Кластеры А1 и А2 совпадают Объединенным кластером для пары совпадающих кластеров А1 и А2 называется кластер А3, эталон E3 и критерий компактности е3 которого рассчитываются по формулам C A E1 + C A E2 image 3 E = 1 2 , имеет либо дочерние вершины только типа «И», либо только типа «ИЛИ». Вершина, из которой выходят C A1 + C A2 только «И» ребра, называется «И» вершиной. Вершина, из которой выходят только «ИЛИ» ребра, - «ИЛИ» вершиной. Если из вершины выходит только одно ребро, то такую вершину можно считать как «И» A где C 1 и А2; A и C - весовые коэффициенты кластеров А1 2 e3 = max(e1 + r(E1, E3 ), e2 + r(E1 , E3 )) . вершиной, так и «ИЛИ» вершиной. Для определенно- сти такие вершины считаются «И» вершинами. Достижением некоторой цели, заданной пользова- телем, является поддерево данного «И/ИЛИ» дерева. Весовой коэффициент (C) кластера А равен единице ( CA = 1), если кластер А был найден в процессе достижения цели или был задан априори. Если кластер А был построен как объединенный для пары сов- Такое решающее дерево T определяется следующим образом: исходная задача P - это корень дерева T; если P является «ИЛИ» вершиной, то в T содер- жится только одна из ее дочерних вершин (из «И/ИЛИ» дерева) вместе со своим собственным ре- шающим деревом; если P - это «И» вершина, то все ее дочерние вершины (из «И/ИЛИ» дерева) вместе со своими ре- шающими деревьями содержатся в T. Решающее дерево для исходной цели является «И» деревом, так как все его вершины являются вершина- ми типа «И». Если «И/ИЛИ» дерево априори не зада- но, процесс достижения цели сводится к построению image падающих кластеров А1 и А2, то (рис. 2). А3 А1 А2 1 CA = CA + CA2 решающего «И» дерева. Две цели относятся к одному классу целей тогда и только тогда, когда корневые вершины решающих деревьев для данных целей соответствуют одному и тому же кластеру в пространстве целей. Задача данной работы - разработать технологию построения «И/ИЛИ» дерева, обобщающего решающие «И» деревья для класса целей, путем многократного достиже- ния целей данного класса. Совпадающие кластеры. Пусть в некотором при- знаковом пространстве X(x1, x2, …, xn) заданы два кла- стера А1 и А2 своими эталонами E1(e11, e12, …, e1n) и E2(e21, e22, …, e2n) и критериями компактности е1 и е2. Кластеры А1 и А2 называются совпадающими, если эталон каждого из них принадлежит другому Рис. 2. Объединение совпадающих кластеров Так как каждой вершине «И» дерева соответствует кластер, то вершины будем назвать совпадающими, если совпадают соответствующие им кластеры. Вершину А3 будем называть объединенной вершиной для совпадающих вершин А1 и А2, если она соот- ветствует объединенному кластеру для совпадающих кластеров вершин А1 и А2. Весовым коэффициентом вершины будем называть весовой коэффициент кластера, соответствующе- го данной вершине. Для обозначения совпадающих вершин будем ис- пользовать знак “≈”. 34 Построение обобщенного «И/ИЛИ» дерева. Вве- дем способ задания «И/ИЛИ» дерева. «И/ИЛИ» дерево G описывается тройкой G = {GV , GE ,GI } , где 1) множество вершин GV = {G1 ,G2 ,..., Gn } , где Gi - множество вершин i-го уровня дерева G, n - чис- ло уровней дерева G; В результате объединения деревьев получаем обобщенное «И/ИЛИ» дерево G3 (рис. 6). Сходимость процесса построения обобщенного «И/ИЛИ» дерева. На каждом шаге объединения «И/ИЛИ» дерева с «И» деревом, в общем случае, мо- гут изменяться: структура «И/ИЛИ» дерева, а именно: GE GI множество ребер дерева G; множество двухуровневых «И» подеревьа) добавляться новые вершины; б) образовываться новые «ИЛИ» ветви; ев дерева G. 11 11 12 13 2) уже имеющиеся вершины, входящие в состав «И/ИЛИ» дерева. Пусть G1 - обобщенное «И/ИЛИ» дерево, полу- ченное посредством неоднократного объединения решающих «И» деревьев для целей данного класса. G2 - «И» дерево для новой задачи данного класса. Пусть A1 - вершина обобщенного «И/ИЛИ» дерева G1, а A2 - вершина «И» дерева G2, совпадающая с A1. E1 - эталон кластера, соответствующего вершине A1. E2 - эталон кластера, соответствующего вершине A2. 11 12 13 14 15 Пусть A3 объединенная вершина, которой соответст- image Рис. 3. «И/ИЛИ»-дерево Дерево, изображенное на рис. 3, описывается сле- дующим образом: вует объединенный кластер, построенный для класте- ров вершин A1 и A2, E3 - эталон данного кластера. Ко- эффициентом изменения вершины A1 при построении объединенной вершины A3 для совпадающих вершин A1 и A2 будем называть величину D( A1 , A2 ) = r(E1 , E3 ) . G = {GV , GE ,GI } , где: GV = {{A11},{B11 , B12 , B13},{C11 , C12 , C13 , C14 , C15}} ; GE = {( A11 , B11 ), ( A11 , B12 ), ( A11 , B13 ), (B11 , C11 ), ; (B11 , C12 ), (B12 ,C13 ), (B12 , C14 ), (B13 ,C15 )} GI = {{B11 , B12 , B13 },{C11 , C12 },{C13 , C14 }} . Приведем алгоритм объединения двух «И/ИЛИ» деревьев. Заметим, что «И» дерево является частным случаем «И/ИЛИ» дерева, следовательно, данный ал- горитм применим и для объединения «И» дерева с «И/ИЛИ» деревом. Пусть u(G1, G2) - операция построения обобщен- ного «И/ИЛИ» дерева для двух «И/ИЛИ» деревьев G1 и G2. Операнды могут быть «И» деревьями, которые являются частным случаем «И/ИЛИ» деревьев. Пусть s(G) - функция, вычисляющая сумму весо- вых коэффициентов всех вершин дерева G. Пусть q(G) - функция, вычисляющая количество вершин дерева G. Тогда коэффициентом прироста дерева G1 при объединении его с деревом G2 назовем величину Пусть заданы два дерева G1 = ({G1 , G1 ,..., G1 }, G1 , G1 ) 1 2 n и 2 2 2 2 2 2 d (G , G ) = q(u(G1 ,G2 )) - q(G1 ) . s(G ) E I G = ({G1 , G2 ,...,Gn },GE ,GI ) . Результатом 1 2 работы алгоритма является «И/ИЛИ» дерево G3, 1 обобщающее деревья G1 и G 2 : G3 = ({G3 , G3 ,...,G3}, Очевидно, что d (G1 , G2 ) ³ 0 . E I G3 , G3 ) . 1 2 n Равенство d(G1, G2) = 0 для «И/ИЛИ» дерева G1 и Суть алгоритма заключается в последовательном просмотре уровней обоих деревьев и поиске совпа- дающих вершин на соответствующих уровнях. Если совпадающие вершины найдены, то для каждой пары совпадающих вершин строится объединенная верши- на. При этом вхождение совпадающих вершин в мно- «И» дерева G2 говорит о том, что в результате объеди- нения деревьев G1 и G2 в полученном «И/ИЛИ» дереве не появились новые узлы по сравнению с исходным «И/ИЛИ» деревом G1. Процесс построения обобщенного «И/ИЛИ» дере- ва для данного класса целей называется сходящимся, жества G1 , G1 , G 2 , G 2 заменяется на построенную если объединение данного «И/ИЛИ» дерева с решаю- E I E I объединенную вершину. Результирующее дерево строится из объединенных вершин для совпадающих вершин исходных деревьев, вершин, для которых не нашлось совпадающих, и всех ребер исходных де- ревьев с учетом замены совпадающих вершин на объ- единенные вершины (рис. 4). Пример. Пусть заданы «И/ИЛИ» дерево G1 и «И» щим «И» деревом для новой задачи того же класса удовлетворяет следующим условиям: коэффициент прироста обобщенного «И/ИЛИ» дерева d(G1, G2) не превышает некоторую наперед заданную малую величину; максимальный коэффициент изменения D(Ai, Aj) по всем изменившимся вершинам обобщенного дерево G 2 (рис. 5), (A1 ≈ A2) И (B14 ≈ B21) И (C16 ≈ C21) «И/ИЛИ» дерева не превышает некоторую наперед И (C17 ≈ C22). заданную малую величину. Начало i : = 0 i : = i + 1 i G3 : =Æ i G2 : i G1 : да =Æ нет да =Æ нет i Первую вершину из G2 обозначаем А i i i i G3 : = G3UG1UG2 Сравниваем А с каждой вершиной из G 1 i i = n да нет конец нет i В G1 найдена вершина, совпа- дающая с А? да Найденную вершину обозначим В Для А и В строим объединенную вершину, которую обозначаем С G3 : = G3U {C} i i E Все вхождения А в G2 I и G2 заменя- ем на С. Повторяющиеся элементы удаляем E Все вхождения В в G1 I и G1 за- меняем на С. Повторяющиеся элементы удаляем G1 : = G1 \ {B} i i G2 : = G2 \ {A} i i 36 image Рис. 4. Схема алгоритма объединения «И/ИЛИ» деревьев image image image Рис. 5. «И/ИЛИ» дерево G1 и «И» дерево G 2 image Рис. 6. «И/ИЛИ» дерево G3 Утверждение. Если для всех «И» деревьев Gi за- n ( 1 , 2 ,..., m ) E = en en en , еn - его эталон и критерий ком- дач заданного класса $M Î N такое что, q(Gi ) £ M , то процесс построения обобщенного «И/ИЛИ» дерева для данного класса задач сходится. Доказательство. Пусть G - обобщенное «И/ИЛИ» дерево для за- пактности. Пусть A - кластер, решающего «И» дерева, совпадающий с An, E = (e1 , e2 ,..., em ) - его эталон, е - кри- терий компактности. Докажем, что lim D( An , A) = 0 : n®¥ CA En + CA E дач одного класса. Пусть Gn - решающее «И» дерево для задачи данного класса (n = 1, 2, …). Очевидно, что lim D( An , A) = lim r(En , n®¥ n®¥ image n ) = n CA + CA на первом этапе построения обобщенного «И/ИЛИ» image image = lim r( , nEn + E ) = lim ( i - nen + e )2 = дерева G = G1. Докажем, что lim d (G,Gn ) = 0 : n®¥ En n + 1 n®¥ m å en i =1 i i n +1 n®¥ lim d (G, G ) = lim q(u(G, Gn )) - q(G) . = lim n n n m nei + ei - nei - ei image å ( )2 = n n®¥ image n n®¥ s(G) n ®¥ i 1 +1 = image image m m Величина q(u(G, Gn )) - q(G) показывает, сколько = lim n 1 å (ei - ei )2 £ lim n 1 å( min(e , e))2 = новых узлов появилось в обобщенном «И/ИЛИ» дере- ве G при объединении его с «И» деревом Gn. Так как у n® ¥ image n + 1 i =1 m n ®¥ n +1 i =1 = lim (min(e , e))2 = 0 . деревьев G и Gn совпадают, по крайней мере, корне- вые вершины, то q(u(G, Gn )) - q(G) £ q(G) + q(Gn ) -1- Итак, n®¥ n +1 n m 2 Тогда -q(G) = q(Gn ) -1 £ M -1. image 0 £ D( An , A) £ lim n®¥ n +1 (max(en , e)) = 0 , q(u(G, G )) - q(G) M -1 M -1 image lim n £ lim £ lim . следовательно, lim D( An , A) = 0 . n®¥ n®¥ Итак, s(G) n®¥ s(G) n®¥ n -1 Утверждение доказано. Таким образом, предложена новая технология по- строения обобщенного «И/ИЛИ» дерева решения, по- image 0 £ lim d (G, G ) £ lim M -1 = 0 , зволяющая формировать базу знаний и «И/ИЛИ» де- n®¥ n n®¥ n -1 рево ЭС пользователем-природоведом без использо- следовательно, lim d (G,Gn ) = 0 . n®¥ Пусть An - кластер, соответствующий вершине обобщенного «И/ИЛИ» дерева G, построенный в ре- зультате объединения n совпадающих кластеров. вания компонента «извлечение знаний». В рамках предложенного метода даны понятия совпадающих кластеров целей, совпадающих вершин дерева. Разработан новый алгоритм построения обоб- щенного «И/ИЛИ» дерева, основанный на объедине- нии «И» деревьев через совпадающие вершины. Дано определение сходимости процесса формиро- вания обобщенного «И/ИЛИ» дерева. Доказано, что такой процесс сходится.