Distance between formulas of the five-valued Lukasiewicz logic and unreliability measure of expert statements on the clustering of knowledge databases.pdf На сегодняшний день актуальной является проблема анализа многозначной экспертной информации, представленной в виде высказываний экспертов, которые можно записать в виде логических формул исчисления высказываний. В данной работе экспертные высказывания представлены в виде формул пятизначной логики Лукасевича [1]. Ясно, что различные высказывания и соответствующие им формулы несут разное количество информации. Тем самым возникает вопрос о сравнении экспертных высказываний по информативности и, как следствие, их ранжировании. Ясно, что информативность всего высказывания должна зависеть от информативности элементарных компонент и степени различия содержащейся в них информации. Следовательно, необходимо ввести «расстояние» между логическими формулами, соответствующими высказываниям, для которого, по определению расстояния, должны выполняться аксиома тождества, аксиома симметрии и неравенство треугольника, а также меру недостоверности высказывания. В [2, 3] определены расстояние и мера недостоверности для случая классической двузначной логики [5]. Помимо основных свойств введённое там расстояние обладает свойствами, учитывающими семантику совпадения и различия информации. Основной задачей работы являлось введение расстояния и меры недостоверности для формул пятизначной логики Лукасевича L5, причём таким образом, чтобы выполнялось как можно больше свойств, характерных для данных величин, введённых и доказанных для формул классической логики, и чтобы учитывались все возможные истинностные значения L5. исполь- 1. Расстояние между формулами Ls Теоретико-модельные понятия для случаев классической логики и L5, зуемые в данной работе, определены в [2-4]. Для краткости будем пользоваться следующими обозначениями: Mod, M (Ф _) = 4 (Ф) _ 4 S (!) , k l то есть количество моделей, где формула ф принимает значение —, а у - -. Mods(Е)((ф)k &(у)к) 4 4 Расстояние между двумя формулами двузначной логики определяется как мощность симметрической разности моделей этих формул. Это расстояние задаёт метрику на классах эквивалентных высказываний [2,3]. Определение 1. [2, с. 89; 3] Расстоянием между формулами ф и у двузначной логики при S(ф) u S(у) с S(Е) на множестве P(S(Е)) называется величина. = \ModS(Е) ((-ф & у) v (ф & -у))| '= 2s Преобразуем формулу (1) к следующему виду: Ps(Е) (Ф, У) = 2Щ" ModS(Е) ((-Ф & У) v (Ф & -у))| = M(0,1) + M(1,0) = = 1 • M(0,1) +1 • M(1,0) + 0 • M(0,0) + 0 • M(1,1) = -js^ X X |k - l|M(k, l). 2 k=0,11=0,1 Таким образом, предположим, что для определения расстояния можно учитывать разность между истинностными значениями формул ф и у на каждой модели. Замечание (доказательство в [2, с. 93; 4]): Для вычисления расстояния между формулами ф и у, такими, что S(ф) u S(у) с S(Е), достаточно рассматривать не всё S(E), а только S(ф) u S(у). Или, точнее, любое S(E0), такое, что S(ф)u S(у) с S(Ее) с S(Е) . Далее, нижний индекс S(E) в записи р ^ будем опускать. Обобщим этот подход на пятизначный случай. Объединим модели с одинаковыми модулями разности между значениями ф и у. Естественно предположить, что чем меньше модуль разности между значениями ф и у, тем формулы более близки в данной модели. Следовательно, умножим количество моделей с одинаковыми модулями разности на коэффициент, учитывающий близость формул. В качестве таких коэффициентов возьмём пять истинностных значений для L5: P (ф, у) = 0 \м (0,0) + M (1,1) + M (1,1) + M (1,1) + M (1,1) 1 + ^ 44 22 44 ) 1 1 11 11 13 31 3 3 1 +-IM (0,-) + м (—,0) + M (-,-) + M (-,-) + м (-,-) + M (-,-) + M (-,1) + M (1,-) 1+ 4v 4 4 42 24 24 42 4 4 ) +1 ^ м (0,-2)+м (1,0)+м (11) + м (11)+м (1,1)+м (1,2)) + (2) +3 Гм (0,3) + M (3,0) + M (1,1) + M (1,1) 1 + м (k, к) = 4 4 Ps(Е)(Ф, у) = J-та-L. (1) 41 4 4 4 4 ) Ы(м (0,1)+м (1,0) ) = ££ Мм (11). k=0l=0 Остаётся только нормировать величину р . Определение 2. Расстоянием между формулами ф и у пятизначной логики L5 при S(ф) u S(у) с S(!) на множестве P(S(!)) назовём величину 1 4 4 _ - Л _ , Теорема 1. Расстояние между двумя формулами L5, определённое равенством (3), для любых ф, у, х е ! удовлетворяет следующим свойствам: 1) 0 + - M (ф !> + 1M (Фо) . 4 2 4 i^M (ф (). 5 S (Е) 5 £ 4 Определение 3. Мера недостоверности /(ф) для формул ф пятизначной логики L5, таких, что S(ф) с S(Е), на множестве P(S(Е)) задаётся равенством m (ф ^) 4 5 S (Е) i=o - 5iS Теорема 2. Мера недостоверности, определённая равенством (5), для любых формул ф, у, х е Е удовлетворяет следующим свойствам: 1) 0 < /(ф) < 1; 2) / (ф) + / (-ф) = 1; 3) / (флу) > max{/(ф), / (у)}; 4) /(фvу) < min{/(ф),/(у)}; 5) / (ф v у) + / (флу) > / (ф) + / (у); 6) / (флу) = р(ф, у) + / ^у); 7) р(ф,у) р(ф^у, у); 9) / (ф ^ у) l. Тогда 4-l = k-l + 4-k , 4-1 = 4-1, свойство выполняется. Случай 2: k,l Ф 4, k < l. Тогда 4 - k = l - k + 4 -1, 4 - k = 4 - k . Случай 3: k = 4, l Ф 4. Тогда 4 -1 = 4 -1 + 4 - 4, 4 -1 = 4 -1. Случай 4: k Ф 4 , l = 4. Тогда, симметрично третьему случаю, 4 - k = 4 - k . Случай 5: k = l. Тогда 4 - k = 4 - k , свойство выполнено. Других случаев нет. 7) Следует из того, что мера недостоверности по определению равна расстоянию от данной формулы до тождественно истинной, а для расстояния между формулами выполняется правило треугольника. 8) Рассмотрим произвольную модель. Надо доказать неравенство 4 - k > |min{4,4 - k +1} -1|. Случай 1: k = l. Тогда 4 - k > |4 -1|, 4 - k = 4 -1. Случай 2: k > l. Тогда 4 - k > |4 - k +1 -1|, 4 - k = 4 - k . Случай 3: k < l. Тогда 4 -k > |4 -1|, 4 -k > 4 -1. 9) Рассмотрим произвольную модель. Надо доказать неравенство 4 - min{4,4 - k +1} < |k -1|. Случай 1: k = l. Тогда 0=0. Случай 2: k > l. Тогда 4 - (4 - k +1) < k -1, k -1 = k -1. Случай 3: k < l. Тогда 4 - 4 < l - k, 0 < l -k . 10) Рассмотрим произвольную модель. Надо доказать неравенство 4 - max{k, l} < |min{4,4 - k +1} - min{k, l}|. Случай 1: k = l. Тогда 4 - k < |4 - k\, 4 - k = 4 - k . Случай 2: k> l. Тогда 4-k < |4-k +1-1| ,4-k = 4-k . Случай 3: k < l. Тогда 4 -1 < |4 -k|, 4 -1 < 4 -k . Теорема доказана. Замечание: Попробуем подойти к определению меры недостоверности для L5 с другой стороны. Так как в L5 истинностных значений, отличных от 1, не одно, а четыре, то имеет смысл учитывать все модели, на которых формула ф принимает значения k/4 при k = 0,...,3. Естественно предположить, что при каждом M/4) должен стоять коэффициент, учитывающий, насколько близко истинностное значение формулы ф к 1. Ясно, что модели, на которых формула принимает значение 1/4 , должны учитываться с большим коэффициентом, чем те, на которых формула принимает значение 3/4, так как 3/4 ближе к единице. А так как истинностные значения в логике Лукасевича распределены равномерно между 0 и 1, то можно определить значения коэффициентов как (4 - i)/4, i = 0,...,3. 3. Примеры Применим иерархический алгоритм кластеризации с объединением кластеров по методу ближайшего соседа к некоторой группе высказываний. Пусть есть n высказываний. Сначала считаем, что у нас есть n кластеров. Построим матрицу расстояний для группы из n высказываний, потом выделим наименьшее расстояние между формулами ф,- и фу и объединим формулы ф,- и фу в один кластер. Затем пересчитаем матрицу расстояний уже для n-1 высказывания по правилу р(ф^, фу) = шт{р(ф£, ф,), р(ф^, ф j )} и будем повторять действия до тех пор, пока все высказывания не объединятся в один кластер. ф1 = X ^ у ; ф2 = —(x ^ у); фз = (x v z) ^ y; ф4 = —((X л у) v z) ^ w; ф5 = у ^ (x л z); ф6 = (—у v (x ^ z)) ^ w; ф7 = ((x ^ у) ^ z) ^ w; ф8 = (w ^ z) л (у ^ x). Их меры недостоверности соответственно равны: /(ф1) = 0,2000; /(ф2) = 0,8000; /(ф3) = 0,3000; 1(ф4) = 0,3584; 1(ф5) = 0,3000; 1(ф6) = 0,4092; 1(ф7) = 0,2716; 1(ф8) = 0,3416. Шаг 1: minр(ф,,фу) = 0,0508 = р(ф4,ф6). Кластеры: ф:,ф2,ф3,ф46,ф5,ф7,ф8. J Шаг 2: minр(ф,,фу) = 0,1000 = р(ф1,ф3). Кластеры: ф13,ф2,ф46,ф5,ф7,ф8. J Шаг 3: minр(ф,,ф у) = 0,1300 = р(ф7,ф46). Кластеры: ф13, ф2, ф467, ф5, ф8. ,ф J Шаг 4: minр(ф,,фу) = 0,1416 = р(ф5,ф8). Кластеры: ф13,ф2,ф467,ф58. ,Ф J Шаг 5: minр(ф,-,ф,) = 0,2460 = р(ф13,ф467). Кластеры: ф2, ф58, ф13467 . ,Ф J Шаг 6: minр(ф,,фf) = 0,4032 = р(ф58,фВ467). Кластеры: ф2,фт5678. ,Ф J Шаг 7: Р(ф2 , ф1345678) = 0,5000 . Кластер ф12345678 . Мера недостоверности здесь может выступать в качестве критерия остановки процесса объединения формул в кластеры, если количество кластеров заранее не известно. Например, на шаге 4 максимальная разница между мерами недостоверности элементов одного кластера равна 0,1376, а на шаге 5 - 0,2092. В реальной задаче значение 0,2092 может оказаться неприемлемым (слишком большим). Поэтому перед началом кластеризации можно задать допустимую разницу между мерами недостоверности элементов одного кластера. Соответственно, алгоритм останавливается, когда разница между мерами недостоверности достигает допустимого значения. Заключение Введённое расстояние р между формулами L5 удовлетворяет не только свойствам расстояния (2) - (4), но и свойствам, учитывающим семантику совпадения и различия информации в высказываниях. В дальнейшем, наряду с мерой недостоверности, можно ввести некую меру неопределённости, определив её как расстояние от произвольной формулы ф до формулы, тождественно равной 0,5. Помимо иерархического алгоритма кластеризации были рассмотрены и другие, но наиболее подходящим был выбран указанный в данной работе. Расстояние между высказываниями и меру недостоверности можно использовать при анализе баз знаний, их кластеризации, согласовании высказываний, создании экспертных систем, а также при построении логических решающих функций в распознавании [6; 7].

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