Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по базам знаний и экспертным системам - файл 1.doc


Лекции по базам знаний и экспертным системам
скачать (1259 kb.)

Доступные файлы (1):

1.doc1259kb.24.11.2011 09:16скачать

содержание
Загрузка...

1.doc

1   2   3   4   5   6   7   8   9   10
Реклама MarketGid:
Загрузка...
^

Полный алгоритм вывода на СС


Пусть имеется множество дизъюнктов: S1,S2,…,Sn=S. Выберем из каждого дизъюнкта какую-нибудь литеру L1,L2, …,Ln. Такую последовательность литер назовем путём на множестве S. Пример: P(a)Q(b),P(x)C(d), C(x). Тогда путь – это следующая последовательность литер: P(a), P(x), C(x).

Алгоритм:

  1. Выделяем некоторый путь p из исходного множества S.

  2. Выводим все возможные дизъюнкты на этом пути, т.е. если имеются контрольные пары, они резольвируются и результат добавляется к СС.

  3. Литеры, соответствующие вновь сформированным дизъюнктам, добавляются в путь р.

  4. Процесс продолжается до получения пустого дизъюнкта.

В СС выделению литеры соответствует процесс выделения вершины по дуге. Обозначим F-11(p) – выделение литеры, связанной с вершиной p дугой 1-го типа.
^

Алгоритм параллельного вывода на СС


Дедуктивному выводу присущи 2 вида параллелизма:

  • OR-параллелизм (Один и тот же дизъюнкт. Одна литера в СС резольвируется во всех возможных местах, параллельно выполняется унификация и генерация новых дизъюнктов.);

  • AND-параллелизм (система вывода параллельно резольвирует несколько дизъюнктов, при этом возникает проблема параллельного выполнения различных унификаций одной и той же литеры; система должна гарантировать корректность выполнения алгоритма унификации).

Будем называть переменную простой, если она используется в дизъюнкте только один раз. В противном случае, переменную будем называть разделенной. Пример: P(x,y)Q(x). Здесь x – разделенная, у – простая.

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

^ При параллельном выводе на СС возможно параллельное выполнение следующих операций:

  1. параллельная унификация: выполняется внутри одной вершины, свободной от мультидуг;

  2. параллельное удаление вершин, свободных от мультидуг, не имеющих общих дизъюнктов. Рекомендуется использовать следующее эвристическое правило: в первую очередь выбираются вершины минимальной степени;

  3. параллельная стяжка мультидуг одного цвета;

  4. параллельная стяжка внутри одной вершины, имеющей несколько мультидуг: может выполняться по каждой дуге, входящей в мультидугу;

  5. параллельное расщепление различных вершин, имеющих мультидуги.
^

Нечеткая математика и ее применение в ЭС

Введение в нечеткую теорию множеств


Пусть имеется универсальное множество Ω.

Нечетким множеством А называется пара А = (Ω, μА), μА: Ω  [0, 1] – функция принадлежности.

В классической теории множеств μА называется индикатором.



А – μА, В – μВ

С = , μС = 1 - μА

С = A  B, μС = max(μА, μВ)

С = A  B, μС = min(μА, μВ)

Заметим, что при данном определении операций, все свойства сохраняются для нечетких множеств.
^

Меры возможности и нечеткие множества


Информационная система, описывающая неопределенную неточную информацию, оперирует сведениями, содержащими 2 вида оценки качества информации – это неопределенность и неточность. Будем считать, что база знаний состоит из информационных единиц. Каждая информационная единица задается четверкой: объект, признак, значение, уверенность (достоверность).

Признак – это некоторый предикат или высказывание, характеризующее свойство объекта.^ Значение признак – функциональную зависимость.

Уверенность – показатель надежности информационной единицы.

Неточность – это характеристика качества значения признака, а неопределенность – это соответствие данного значения действительности.

Понятия правдоподобности и доверия соответствуют способу вывода в БЗ. Например, заслуживает доверия все то, что непосредственно выводимо дедуктивно в БЗ.

Правдоподобно все то, что не противоречит БЗ.

Пример: скорее всего, рост среднего человека не менее 170 см. Для каждого конкретного человека данный факт либо ложь, либо истина.

Пусть имеется некое универсальное множество Ω, на котором задана функция g(A)  [0, 1], A  Ω

Функция g называется степенью уверенности, или мерой возможности, если g() = 0, g(Ω) = 1. Если A  B g(A)  g(B), A, B g(A  B)  max(g(A), g(B)), g(A  B)  min(g(A), g(B)).

Такая функция g – мера возможности, если выполняется условие g(A  B) = max(g(A), g(B))   .

Если g(A  B) = min(g(A), g(B)), получаем меру необходимости – N.

Между этими двумя мерами существует следующая связь:

  1. для A (A)  N(A);

  2. если N(A) > 0, тогда (A) = 1;

  3. если (A) < 1, то N(A) = 0.

Практически функции принадлежности занимают некое промежуточное положение между мерами возможности и необходимости.

Max((A), ()) = 1. Для A (A)  P(A)  N(A).

Пусть у нас есть система нечетких множеств: Ω, μА.

 срезом нечеткого множества A=(Ω, μА) называется множество F={ω | ω  Ω, μА(ω) > }.

Строим  срез: .

Единичный  срез соответствует точной теории множеств. Ядро нечеткого множества – это единичный  срез, т.е. , а носитель – .

Нечеткие множества А(Ω,μА), В(Ω, μВ), μАμВ.

Два нечетких множества считаются равными, если совпадают их функции принадлежности: A=B, μАВ.
^

Методы построения функции принадлежности


Существует два основных случая:

  1. функция принадлежности отражает субъективное предпочтение о некоторой расплывчатой категории;

  2. функция принадлежности строится на основе статистических данных.

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

а)

  1. оцениваемый объект является простой категорией, определенный на объективнолинейно-упорядоченном универсальном множестве («большой и высокий»);

  2. сложная категория, т.е. объекты оцениваются с точки зрения одновременного рассмотрения нескольких простых категорий («коренастый»);

  3. отсутствие универсальной шкалы («красивый»).

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

Наиболее эффективным является метод парных сравнений: на основании опроса экспертов определяется множество допустимых значений нечеткой величины, т.е. определяется носитель множества, или множество значений нечеткой величины. Пусть это множество .

Строим матрицу, где Bij – оценка эксперта, отражающая, во сколько раз объект xi в большей степени обладает исследуемым свойством, чем объект xj: biji/ μj.

Далее считается, что , где ωi – собственный вектор матрицы В.
^

Нечеткие числовые величины

Способы задания нечетких числовых величин


Нечеткая числовая величина f, заданная на , задается своей функцией принадлежности μf()=[0, 1].

μf может быть непрерывной или дискретной. Доказано, что в большинстве случаев достаточно использовать дискретную функцию принадлежности, принимающую не более 10 различных значений.

Пусть имеется 2 нечеткие числовые величины: А и В с носителями SA=(a, b), SB=(c, d), ab, cd.

Арифметическая операция над числами А и В: с = g(A, B), это некая функция, отображающая g: , μС(х) = sup(μA(y), μB(z)), g(y, z)=x, ySA,zSB.

Данное определение называется принципом обобщения. Принцип обобщения корректен в вероятностной трактовке.

Пусть fA, fB, fC - плотности распределения вероятностей случайных величин A, B, C. Тогда считая, что случайные величины А и В независимы, получаем:



Для задания нечетких случайных величин используется следующие основные представления:

  1. явное задание функции принадлежности;

  2. интервальное представление, т.е. каждому нечеткому числу А ставится в соответствие интервал, равный по размеру носителя нечеткого числа

A[mA, MA] - SA

  1. треугольное представление: любому нечеткому числу ставится в соответствие тройка А[ mA, VA, MA], притом предполагается μA(VA)=1, [mA, MA] - SA



  1. трапециевидные числа: любое число характеризуется парой А=(A, mA, MA, A),

[mA, MA] - ядро нечеткого числа,

SA= [mA-A, MA+A]- носитель

Для трапециевидных чисел доказано, что множество трапециевидных чисел замкнуто относительно операций сложения и вычитания и для операции умножения при соблюдении некоторых дополнительных условий.

A, B – нечеткие числа.

A  B = (A + B, mA  MB, MA  mB, A + B)

Дополнительная операция вычитания: A  B = (A + B, mA - MB, MA - mB, A + B)

max(A, B) = (max(A, B), max(mA, mB), max(MA, MB), max(A, B))

*A = mA - A;

*A = MA + A;

max(A, B)  A или B



Можно доказать max(A, B) + min(A, B) = A + B,

max(A, B) = A  min(A, B) = B.

Для трапециевидных чисел предложена методика решения нечетких уравнений и нечетких систем линейных уравнений.

Замечание:

При использовании принципа обобщения возможны два варианта его применения при вычислении сложных выражений: С = А /(А + В), D = A + B  C = A / D. Нечеткая числовая величина СC.
^

Экспертоны, R-экспертоны


Технология экспертонов используется для обобщения и получения интегрированных оценок экспертов.

Пусть N экспертов строят доверительный интервал для некой числовой величины ,

Каждому эксперту предъявляется получившийся интервал и он оценивает близость этого интервала к наиболее возможному с его точки зрения значению:

i = 0..1 шагом 0,1

i = 0 – оцениваемый параметр соответствует в точности

0,1 – скорее всего

0,2 – почти

0,3 – близко

0,4 – ближе к , чем к

0,5 – находится в любом месте между

0,6

0,7

0,8

0,9

1 – соответствует в точности

Эксперт выражает свою оценку с помощью семейства значений.

Доказано, что данная шкала является достаточной для получения объективных оценок



Получившаяся в результате совокупность интервалов bi является функцией принадлежности нечеткой числовой величины.

Для выполнения арифметических операций над заданными таким образом нечеткими числовыми величинами можно использовать технологию R-экспертонов.

Пример:

Пусть необходимо оценить объем продаж фирмы.

V = с ∙ S, с – стоимость товара, S – количество.

Пусть возможные цены продаж оценивает группа экспертов NC и полученные оценки .

S оценивает NS экспертов и получается .

Экспертоны являются технологией, преобразующей экспертные оценки в нечеткие числа, задаваемые своими α-уровнями.

Пусть получены следующие оценки: [41, 54] – обобщенный интервал.

0,2

0,4

0,3

1

0

0,6

0,2

0,3

0,9

0,9

0,7

0,7

0,5

0,7

Этап А – считаем частоту, с которой встречается каждая граница.

0

1




1

1

54

54

9720

9720

0,1

-




0,85

1

52

54

9396

9720

0,2

1




0,85

1

52

54







0,3

1

1

0,5

1

48

54







0,4

-




0,42

0,85

46

52







0,5

1

1

0,42

0,7

46

50







0,6




1

0,29

0,7

45

50







0,7

1

2

0,29

0,57

45

48







0,8







0,14

0,29

43

45







0,9

1

1

0,14

0,29

42,8

44,7







1

-

1




0,14

41

42,8

6560

7029





  1. Строим накопленную частоту

f10=t10, fj-1=fj+tj-1

  1. c1j, c2j



Это экспертон. Он, с одной стороны, учитывает мнение экспертов, с другой стороны, не зависит от количества экспертов.

Аналогичным образом строим экспертон для оценки количества продаж.

Для оценки общая стоимость продаж строим экспертон для V. Вычисляя V по элементным перемножением экспертонов, соответствующим c и S. Получаем, что наиболее возможный интервал [7901, 8724].

Выполнив обратные преобразования, можно получить α-уровни для представления числа V.
^

Нечеткие рассуждения


Возможны следующие типы нечетких высказываний:

  1. Y есть Hi – безусловная зависимость

  2. Y есть Hi есть λi, λi – степень достоверности зависимости

  3. Если Х есть Gi, то Y есть Hi

  4. Если Х есть Gi есть λi, то Y есть Hi

Hi и Gi – нечеткие подмножества

Пример:

  1. Знания студента отличные

  2. Знания студента средние с большой вероятностью

  3. Если студент ориентируется в теме «Исчисление высказываний», то его знания не менее, чем средние

  4. Если студент задает вопросы со степенью разумности 0,75, то его знания хорошие

Пример:

  1. Если х владеет машиной VW и х читает газету Washington Post, то х будет голосовать за демократов

  2. Если х не любит Р. Рейгана и х против войны, то х будет голосовать за демократов

S1(Q|S1)

S2(Q|S2)

S1 & S2 – ?

Функция, которая суммирует f((Q|S1), (Q|S2)) цены нескольких свидетельств должен обладать свойствами:

  1. f(, ) = f(, )

  2. f(, )  [0, 1]

  3. f(1, 1) = 1

  4. f(0, ) = 

  5. Должна быть разложима в ряд Тейлора

Тогда получается, что вид функции должен быть таким, чтобы было легко искать max.

f(, ) =  +  -  ·  – формула Шорлиффа

f(, ) =  +  - (1 -  - )
^

Данные и знания.
Перспективы развития ЭС.


Информация – это совокупность сведений, воспринимаемых из окружающей среды, выдаваемых в окружающую среду, либо сохраняемых внутри ИС.

Данные – это представленная в формализованном виде конкретная информация об объектах предметной области, их свойствах и взаимосвязях.

Данные – это отдельные факты, характеризующие предметную область.

Знания – это хорошо структурированные данные, данные о данных или метаданные.

Знания – обобщенная формализованная информация о свойствах и законах предметной области, с помощью которых реализуется процесс решения задач и преобразования данных и самих знаний.

Информация – интерпретация:

  • Внутренняя (типы);

  • Внешняя  имена  внутренние, внешние.
1   2   3   4   5   6   7   8   9   10



Скачать файл (1259 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru