Новые полные метрики и меры нетривиальности для формул многозначных логик в автоматической кластеризации формул из логической базы знаний. I

1Институт математики им. С.Л.Соболева СО РАН, Новосибирск, Россия;

2Новосибирский государственный университет, Россия (E-mail: [email protected])

Новые полные метрики и меры нетривиальности для формул многозначных логик в автоматической кластеризации формул из

логической базы знаний. I

В статье рассмотрены следующие задачи: обобщены ранее введённые расстояния и меры нетриви- альности наn-значный случай любой логики, сняв ограничения на параметры; используя новые рас- стояния, разработаны алгоритмы кластеризации множеств формул вn-значной логике; проведены кластеризации подмножеств формул из различных баз знаний и предложены способы сравнения ре- зультатов различных адаптированных алгоритмов кластеризации.

Ключевые слова:расстояния и меры, кластеризация множеств, логика, алгоритмы.

Введение

Задачи анализа экспертной информации и извлечения знаний из баз данных приобретают всё большую важность [1-11]. Одним из направлений этой проблематики являются информативность высказываний экспертов [8] и работа с базами знаний [9]. Определение информативности эксперт- ного высказывания зависит от определения информативности его компонент, а также от степени различия этих компонент. Если мы сможем ввести метрику на множестве экспертных высказы- ваний, то их, возможно, стоит подвергнуть кластерному анализу, что даст мощный инструмент для анализа имеющейся информации и изучения новых знаний.

Задача сравнения экспертных высказываний по информативности, их ранжированию и вве- дению метрики на пространстве высказываний была поставлена Г.С. Лбовым и Н.Г. Загоруйко в середине 1990-х гг. [10], [12].

Экспертные высказывания было предложено записывать в виде логических формул исчисле- ния. Таким образом, задача сравнения и ранжирования высказываний экспертов превращается в задачу сравнения и ранжирования логических формул между собой. Для этого надо ввести расстояние между формулами и меру нетривиальности каждой формулы.

Для 2-значной логики решением этой задачи занимались Г.С. Лбов и А. А. Викентьев [7].

Впоследствии А. А. Викентьевым был предложен более общий теоретико-модельный подход к анализу логических высказываний [13]. В качестве исчисления высказываний берется n-значная логика Ln. С помощью развитой теории моделей для формул многозначной логики вводились разные варианты расстояний и мер нетривиальности (опровержимости, недостоверности, инфор- мативности), исследовались свойства этих величин [2]. Затем на основе введённых расстояний и мер нетривиальности стали проводить кластеризацию множеств формул n-значной логики Лу- касевича [14] и решалась задача ранжирования экспертных высказываний.

Кластеризация проводилась для малых nи небольшого числа переменных в формулах, а рас- стояние (более полное) вводилось с логическими (жёсткими) весами [6]. Чтобы автоматизировать вычислительную работу, с необходимостью создавали программы для вычисления расстояний,

Ре по зи то ри й Ка рГ У

1 Определения и обозначения

Определимn-значную логикуL_n, формулами которой представляются высказывания, а также рассмотрим применение теории моделей к формуламL_n.

1.1 Конструкция n-значной логикиLn

Определение 1.1.1. Пропозициональный язык L состоит из следующих пропозициональных символов:

1) x,y,z, ...–пропозициональные переменные;

2) ¬,→–пропозициональные связки (отрицание и импликация);

3) ( , ) – вспомогательные символы.

Определение 1.1.2. Под формулами будем понимать следующие последовательности слов из пропозициональных символов:

1) x,y,z, ... –формулы;

2) если ϕи ψ – формулы, то ¬ϕ, ϕ→ψ – тоже формулы;

3) никакие другие последовательности из исходных символов, кроме построенных в силу пунктов 1-2, не являются формулами.

Теперь мы можем построить типичную n-значную логикуLn.

Определение 1.1.3. n-значная матричная логикаLn определяется через Mn=hV_n,¬,→,{1}i – логическую матрицу;

Vn=

0, 1

n−1, ...,n−2 n−1,1

–множество значений истинности;

¬:Vn→Vn, – операция отрицания;

→:V_n×V_n→V_n –операция импликации; {1}– выделенное значение истины.

Рассмотрим логические операции вn-значной логике.

Определение 1.1.4. Логические операции на V_n задаются следующим образом:

¬x= 1−x– отрицание;

x→y=min{1,1−x+y} –импликация; x∨y= (x→y)→y=max{x, y} –дизъюнкция; x∧y=¬(¬x∨ ¬y) =min{x, y} –конъюнкция.

1.2 Основные понятия и модели для логик Пусть Σ– конечное множество формул Ln.

Определение 1.2.1.S(ϕ)– носитель формулыϕизL_n(множество переменных, используемых при ее написании).

S(Σ) =∪_ϕ∈ΣS(ϕ) – носитель множестваΣ.

Определение 1.2.2. Модель M – кортеж из означенных переменных, на котором вычислимо значение истинности любой формулы.

P(S(Σ))– множество всех моделей,|P(S(Σ))|=n^|S(Σ)| [13]. Будем использовать обозначение ϕ k

n−1

, когда ϕ принимает на модели значение _n−1^k , k = 0, ..., n−1.M(ϕ k

n−1) – количество моде- лей, на которых ϕ принимает значение _n−1^k . M(_n−1^k ,_n−1^l ) – количество моделей, на которых ϕ принимает значение

Ре по

зи

то ри

й Ка рГ У

2 Расстояние и мера нетривиальности формул в Ln

В определении расстояния мы учитываем разницу между любыми различными значениями двух формул на каждой модели. Таким образом, более полно используем многозначность ло- гических формул. Мера нетривиальности служит для ответа на вопрос: насколько добавление формулы в базу знаний повышает ее информативность. Чем более формула недостоверна (а зна- чит, информативна), тем выше мера её нетривиальности.

Покажем, как строится расстояние для формул n-значной логики Ln. Естественно предполо- жить, что чем меньше модуль разности между значениямиϕиψ, тем ближе формулы в данной модели. Будем умножать количество моделей с одинаковыми модулями разности на коэффици- ент, учитывающий близость значений формул. Ранее в качестве таких коэффициентов брались nистинностных значений (для логики Лукасевича) Ln:

˜

ρ₀(ϕ, ψ) = 0·

M(0,0) +M( 1 n−1, 1

n−1) +M( 2 n−1, 2

n−1) +...+M(n−2 n−1,n−2

n−1) +M(1,1)

+

+ 1 n−1·

M(0, 1

n−1) +M( 1

n−1,0) +M( 1 n−1, 2

n−1) +...+M(n−2

n−1,1) +M(1,n−2 n−1)

+...

...+n−2 n−1·

M(0,n−2

n−1) +M(n−2

n−1,0) +M( 1

n−1,1) +M(1, 1 n−1)

+

+1·(M(0,1) +M(1,0)) =

n−1

X

k=0 n−1

X

l=0

|k−l|

n−1 ·M( k n−1, l

n−1).

Таким образом, в качестве расстояния между формулами ϕ и ψ n-значной логики L_n при S(ϕ)∪S(ψ)⊆S(Σ)на множестве P(S(Σ))ранее принималась нормированная величина ρ˜₀ :

ρ0(ϕ, ψ) = 1 n^|S(Σ)| ·

n−1

X

k=0 n−1

X

l=0

|k−l|

n−1 ·M( k n−1, l

n−1). (1)

Пример. Для случаяn= 5ρ0(ϕ∧ψ, ϕ∨ψ) = 0.4,ρ0(ϕ∧ψ∧χ∧ω, ϕ→ω) = 0.2576[6]. Недо- статком величины является взятая конструкция весов ^|k−l|_n−1. Она не позволяет выбирать, с каким именно коэффициентом величина M(_n−1^k ,_n−1^l )(число моделей с одинаковым модулем разности) будет входить в итоговое расстояниеρ0. Такая же проблема возникает для ранее использованной меры нетривиальности формулn-значной логикиLn:

I0(ϕ) =ρ0(ϕ,1) =

n−2

X

i=0

n−1−i n−1 ·

M(ϕ i n−1)

n^|S(Σ)| . (2)

Пример. Для случая n = 5 I0(ϕ → ψ) = 0.2, I0(ϕ∨ψ∨χ ∨ω) = 0.1416 [6]. Однозначно определенным весом величины ??является коэффициент ⁿ⁻¹⁻ⁱ_n−1 . Естественно, необходимо попы- таться пошевелить взятые когнитивно найденные и обоснованные величины, указанные выше, и избавиться от жестких ограничений, накладываемых ранее в поиске подходящих коэффициентов.

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

1 Ершов Ю.Л., Палютин Е.А. Математическая логика. — М.: Наука, 1987.

Ре по зи то ри й Ка рГ У

3 Викентьев А.А. О возможных расстояниях и степенях недостоверности в многозначных высказываниях экспертов и приложении этих понятий в проблемах кластеризации и распо- знавания // Проблемы информатики - (Новосибирск: СО РАН) 2011. — Т. 3. — С. 33–45.

4 Бериков В.Б. Коллектив алгоритмов с весами в кластерном анализе разнородных данных // Вестн. Томск. гос. ун-та. — 2013. — № 2(23). — С. 22–31.

5 Авилов М.С.Программный комплекс вычислений расстояний, мер нетривиальности и кла- стеризации множеств высказываний в n-значной логике// Студент и научно-технический прогресс: материалы 52-й Междунар. науч. студ. конф.-Новосибирск, 2015.

6 Викентьев А.А., Кабанова Е.С. Расстояния между формулами пятизначной логики Лу- касевича и мера недостоверности высказываний экспертов в кластеризации баз знаний //

Вестн. Томск. гос. ун-та. — 2013. — № 2(23). — С. 121–129.

7 Vikent’ev A.A., Lbov G.S. Setting the metrics and informativeness on statements of experts //

Pattern Recognition And Image Analysis. — 1997. — Vol. 7. — No. 2. — P. 175–183.

8 Cooke R., Goossens L. Delft expert judgment data base//Reliability Engineering and System Safety. — 2008. — No. 93(5). — P. 657–674.

9 Baskerville R., Dulipovici A.The theoretical foundations of knowledge management // Knowledge Management Research & Practice. — 2006. — Vol. 4. — P. 83-105.

10 Загоруйко Н.Г.Прикладные методы анализа данных и знаний. — Новосибирск: Изд-во Ин- та математики, 1999.

11 Лбов Г.С.,Бериков В.Б.Устойчивость решающих функций в задачах распознавания образов и анализа разнотипной информации. — Новосибирск: Изд-во Ин-та математики, 2005.

12 Лбов Г.С., Старцева Н.Г.Логические решающие функции и вопросы статистической устой- чивости решений. — Новосибирск: Изд-во Ин-та математики, 1999.

13 Викентьев А.А. Мера опровержимости высказываний экспертов, расстояния в многознач- ной логике и процессы адаптации // Knowledge-Dialogue-Solution: Proceedings of the XIII-th International Conference (June, 18-24, 2007, Varna (Bulgaria)). — 2008. — P. 179–188.

14 Карпенко А.C.Логики Лукасевича и простые числа. — М.: Наука, 2000.

А.А.Викентьев, М.С.Авилов

Логикалық бiлiм қорынан автоматтандырылған формулалар кластеризациясында көпмәндi логика формулалары үшiн нольдiк

емес өлшемдер мен жаңа толық метрикалар. I

Мақалада келесi есептер қарастырылған: параметрлерге шектеу алынып, кез келгенn-мәндi логи- каның жағдайына бұрын енгiзiлген нольдiк емес өлшемдер мен аралықтар жалпыланған; жаңа ара- лықтарды қолдана отырып, n-мәндi логикадағы формулалар жиындарын кластеризациялау алго- ритмдерi құрылған; әр түрлi бiлiм қорынан формулалардың iшкi жиындарына кластеризация жүр- гiзiлiп, кластеризацияның әр түрлi алгоритмдерiнiң нәтижелерiн салыстыру тәсiлдерi ұсынылған.

Ре по зи то ри й Ка рГ У

A.A.Vikent’ev , M.S. Avilov

New comprehensive metrics and nontrivial steps to formulas multi-valued logic in the automatic clustering of logical formulas

Knowledge Base. I

This article describes the following tasks: summarized previously entered distances and non-triviality of the measures on the n-digit case of any logic, removing restrictions on the parameters; with the new range, developed algorithms for clustering sets of formulas in the n-valued logic; conducted clustering subsets of formulas from different knowledge bases and provides methods of comparison adapted results of various clustering algorithms.

References

1 Ershov Yu.L., Palyutin E.A. Mathematical logic, Мoscow: Nauka, 1987.

2 Vikent’ev A.A., Vikent’ev R.A.Bull. of Novosibirsk State University, Ser. Mathematics, mechanics, computer science, 2011, 11, p. 51–64.

3 Vikent’ev A.A.Informatics Problems, 2011, 3, p. 33–45.

4 Berikov V.B. Bull. of Tomsk State University, 2013, 2(23), p. 22–31.

5 Avilov M.S. Student and scientific - technical progress: proceedings of the 52nd International Scientific Student Conference, Novosibirsk, 2015.

6 Vikent’ev A.A., Kabanova E.S. Bull. of Tomsk State University, 2013, 2(23), p. 121–129.

7 Vikent’ev A.A., Lbov G.S.Pattern Recognition And Image Analysis, 1997, 7, 2, p. 175–183.

8 Cooke R., Goossens L.Reliability Engineering and System Safety, 2008, 93(5), p. 657–674.

9 Baskerville R., Dulipovici A.Knowledge Management Research Practice, 2006, 4, p. 83–105.

10 Zagoruiko N.G.Applied methods of data analysis and knowledge, Novosibirsk: Publ. of the Institute of Mathematics, 1999.

11 Lbov G.S., Berikov V.B.Stability crucial functions in problems of pattern recognition and analysis of heterogeneous information, Novosibirsk: Publ. of the Institute of Mathematics, 2005.

12 Lbov G.S., Startseva N.G. The logical decision functions and statistical stability issues making, Novosibirsk: Publ. of the Institute of Mathematics, 1999.

13 Vikent’ev A.A.Knowledge-Dialogue-Solution: proceedings of the XIII-th International Conference (June, 18-24, 2007, Varna (Bulgaria)), 2008, p. 179–188.

14 Karpenko A.S. Logic Lukasiewicz and prime numbers, Мoscow: Nauka, 2000.

Ре по зи то ри й Ка рГ У