close

Вход

Забыли?

вход по аккаунту

?

PopovSoloviev

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
(ГУАП)
В.П. Попов, Н.В. Соловьев
РАСПОЗНАВАНИЕ
В ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ
Лабораторный практикум
Санкт-Петербург
2017
УДК 004.8(076)
Попов В.П. Распознавание в интеллектуальных системах : лабораторный
практикум / В.П. Попов, Н.В. Соловьев. – СПб.: ГУАП, 2017. – 40 с.
Лабораторный практикум предназначен помочь студентам, обучающимся
по направлению 09.04.01 «Информатика и вычислительная техника», получить
практические умения и навыки по дисциплине «Интеллектуальные системы». Изложены принципы построения экспертных систем с применением формулы Байеса, распознавания образов с помощью однослойных нейронных сетей, а также некоторые подходы к кластеризации образов.
© Попов В.П., Соловьев Н.В., 2017
© ГУАП, 2017
2
Содержание
Работа №1 Кластерный анализ в распознавании образов
4
Работа № 2 Моделирование однослойной нейронной сети
15
Работа № 3 Подготовка базы данных экспертной системы
23
Работа № 4 Разработка оболочки экспертной системы
29
Рекомендуемая литература
40
3
Лабораторная работа №1
КЛАСТЕРНЫЙ АНАЛИЗ В РАСПОЗНАВАНИИ ОБРАЗОВ
Цель работы: Ознакомиться с методами кластеризации образов и расстояниями в
пространстве признаков, разработать программу, выполняющую кластеризацию
заданного множества образов.
Теоретические пояснения.
Любой физический объект или процесс обладает набором некоторых параметров (характеристик, свойств), которые, собственно, и позволяют отличать
один объект от другого. Объекты, имеющие похожие параметры, можно объединить в группу (класс). Отнесение некоторого объекта к одной из известных групп
называется распознаванием или классификацией.
Измеряемые или вычисляемые свойства объектов, позволяющие отличить
классы друг от друга, называются признаками. Совокупность конкретных значений признаков, относящихся к одному объекту, называется образом объекта. Тогда класс можно определить как множество образов, обладающих близкими значениями признаков. Эти образы называются элементами класса.
В пределе каждый класс может состоять только из одного элемента, как,
например, при распознавании человека. В таком случае принято говорить об опознавании или идентификации образа. С другой стороны, все множество образов
может быть разделено всего на два класса, например, «свой» и «чужой».
При разработке системы распознавания некоторого множества образов, разделенного на классы, используется одно множество признаков, отличающихся
значениями для разных классов. Если число признаков, используемых при классификации, равно n, то образ можно представить в виде некоторого упорядоченного набора значений признаков или вектора признаков вида x = (x1, ..., xn), где xi –
значение i-го признака данного образа. В многомерном пространстве, осями координат которого являются отдельные признаки, каждый образ определяется точ4
кой, причем расстояние от этой точки до начала координат и расстояние между
точками определяется выбранной метрикой пространства.
Каждый класс занимает некоторую область в n-мерном пространстве признаков. Форма этой области определяется степенью отличия элементов класса и
может задаваться границами, например, плоскостями, или характеристиками признаков класса, например, векторами средних значений и среднеквадратичных отклонений признаков.
Множество образов, используемое при разработке системы распознавания,
называется обучаемым. Элементы этого множества относятся к разным классам,
причем иногда заранее неизвестно к какому классу относится каждый образ. Порой неизвестно и число классов, на которые можно разделить множество имеющихся образов. Процедуру разбиения множества образов на классы называют
кластеризацией, а совокупность, отнесенных к отдельному классу образов – кластером. Результаты кластеризации зависят от выбранной метрики пространства
признаков и применяемого метода кластеризации.
Для определения расстояния между точками в пространстве признаков
необходимо выбрать метрику, т.е. определить процедуру измерения расстояния
dlp между точками l и p в этом пространстве так, чтобы выполнялись следующие
аксиомы:
-
симметричность расстояния (dlp = dpl);
-
правило треугольника (dlh + dhp > dlp);
-
положительность расстояния (dlp >= 0, причем dlp = 0 только если l = p).
Наиболее часто в пространстве признаков используется Евклидово расстоя-
ние: d lp 
n
(x
i 1
il
 xip ) 2 ,
(1)
где xil, xip – i-ые координаты точек l и p соответственно. Так как при распознавании важно не абсолютное, а относительное расстояние между точками в пространстве признаков, то квадратный корень в (1) при распознавании не вычисляется. Тогда в векторной форме Евклидово расстояние между двумя образами в
пространстве признаков можно представить как:
5
dlp = (xl – xp) × (xl – xp)T,
(2)
где × – операция умножения векторов, xl, xp – вектор-строка признаков для образов l и p соответственно.
Евклидово расстояние является частным случаем расстояния Минковского,
n

которое вычисляется как: d lp   ( xil  xip ) ,
(3)
i 1
где λ – целое положительное число.
Манхеттенское расстояние представляет собой сумму абсолютных значений
n
разности двух образов по каждому признаку, т.е. d lp   xil  xip .
i 1
(4)
За расстояние доминирования между двумя образами принимается макси-


xil  xip .
мальная разность значений признаков, т.е. dlp  max
i 1,n
(5)
Если диапазоны возможных значений признаков существенно отличаются,
например, число углов замкнутого контура и его длина в миллиметрах, то признаки нормируются следующим образом: x' 
x  xmin
, где x′ – нормированное знаxmax  xmin
чение признака x, xmax, xmin – возможные максимальное и минимальное значения
признака. В результате все признаки получают один диапазон изменения 0 … 1.
Учесть различие диапазонов изменений признаков позволяет и расстояние
n
xil  xip
i 1
xil  xip
Канберра: d lp  
,
(6)
которое не требует предварительного нормирования признаков. Из (6) следует,
что чем меньше абсолютное значение признака, тем большее влияние он оказывает на результат вычисления расстояния.
Признаки могут иметь разную ценность при распознавании, например, отличие в числе вершин на единицу более существенно, чем такое же по величине
отличие в длине контура. Чтобы учесть этот момент применяют весовые коэффициенты признаков, что приводит к изменению формул (1) – (6), например, форму-
6
ла для вычисления Евклидова расстояния будет иметь вид d lp 
n
 ( x
i 1
i
il
 xip ) 2 ,
где ηi – весовой коэффициент i-го признака.
Косинусное расстояние представляет собой угол αlp между векторами xl и
xp. В векторной форме оно вычисляется как:


x l  xTp


 lp  arccos
 (x  xT )1/ 2 (x  xT )1/ 2  ,
l
p
p
 l

(7)
и дает хорошие результаты при распознавании классов, образы которых вытянуты
вдоль радиус-вектора в пространстве признаков. Так как расстояние (7) основано
на скалярном произведении векторов xl  xTp  (xl  xTl )1/ 2 (x p  xTp )1/ 2 cos  , то в качестве альтернативы косинусному расстоянию можно использовать обратное значение скалярного произведения векторов.
При разработке системы распознавания кроме расстояния между точками в
пространстве признаков необходимо задать и способ определения расстояния
между точкой и множеством точек, которое далее будем называть классом. Как
правило, при задании этого способа используются статистические характеристики
признаков класса: вектор средних значений m и ковариационная матрица Cov или
матрица ковариации.
Статистические характеристики признаков класса вычисляются следующим
образом. Пусть набор n-мерных векторов, описывающих в пространстве признаков множество образов, относящихся к одному классу, задан в виде матрицы:
 x11

X   ...
x
 n1
x12
...
xn 2
... ... x1m 

... ... ...  , где m – число образов, составляющих данный класс.
... ... xnm 
1 m
Тогда m  ( 1 , 2 ,...,n ) : i   xik ,
m k 1
(8)
 D11

D
Cov   21
...

 Dn1
(9)
D12
D22
...
Dn 2
m
... D1n  
 Dii  1  ( xik   i ) 2 ;
... D2 n  
m k 1
:

1 m
... ...  
 Dij   ( xik   i )( x jk   j ),
m k 1
... Dnn  
7
где xik – значение i-го признака k-го образа (k=1,…,m), i – среднее значение i-ой
компоненты вектора признаков, Dii – дисперсия i-го признака, Dij – коэффициент
ковариации i-го и j-го признаков.
Из (9) видно, что ковариационная матрица симметрична относительно главной диагонали и, следовательно, необходимо вычислять только половину ее элементов. Ковариация характеризует степень линейной зависимости (корреляции)
случайных величин. Если ковариация равна нулю, то величины называются некоррелированными.
Необходимо отметить важный факт, касающийся ковариационной матрицы.
Если число образов, относящихся к некоторому классу, меньше или равно числу
признаков, то ковариационная матрица, вычисляемая по этому множеству образов, будет вырожденной при любых значениях признаков каждого образа. Справедливость данного утверждения легко показать, если представить ковариационx1  m
ную матрицу как результат матричного умножения Cov = xc×xcT, где x c 
... .
xm  m
Как известно из линейной алгебры определитель матрицы, полученной таким образом, равен нулю, если m ≤ n, следовательно, обратная ковариационная матрица
существует только при выполнении условия m>n.
Наиболее простой способ определения расстояния между точкой и классом
в пространстве признаков состоит в использовании формул (1) – (7) с заменой
вектора признаков одной из точек на вектор средних значений признаков класса.
Такой подход не учитывает степень компактности класса, которая определяется
дисперсиями его признаков. Следующие два расстояния позволяют устранить
этот недостаток.
Евклидово расстояние с учетом дисперсий признаков между точкой и классом в пространстве признаков:
d = (x – m) D-1 (x –m)T,
(10)
где, x – вектор признаков точки, m – вектор средних значений признаков класса,
D – диагональная матрица (диагональные элементы – дисперсии признаков, а
остальные элементы равны нулю).
8
Более полно учесть статистические особенности признаков позволяет расстояние Махаланобиса:
d = (x–m) Cov-1 (x–m)T,
(11)
где Cov-1 – обратная ковариационная матрица признаков.
Расстояния (10) и (11) дают хорошие результаты для классов, имеющих эллипсоидную форму в пространстве признаков. Для классов, имеющих более
сложную форму в качестве расстояния между точкой и классом часто используется расстояние от точки до ближайшего представителя класса, что существенно
увеличивает время вычислений, особенно при большом количестве точек, принадлежащих классу.
Третьим видом расстояний, которое иногда приходится задавать при разработке системы распознавания, является расстояние между классами. Наиболее
простой способ – использование расстояний (1) – (7) с заменой векторов признаков точек на вектора средних значений. Такой способ дает хорошие результаты
для компактных классов, имеющих эллипсоидную форму. Для классов сложной
формы можно использовать приведенные ниже расстояния.
Расстояние ближнего соседа – расстояние между ближайшими точками,
принадлежащими разным классам w1 и w2, т.е.
d(w1,w2) = min(dlp), (l = 1,m1; p = 1,m2),
(12)
где m1, m2 – число точек классов w1 и w2 соответственно.
Расстояние дальнего соседа – расстояние между самыми дальними точками,
принадлежащими разным классам w1 и w2, т.е.
d(w1,w2) = max(dlp), (l = 1,m1; p = 1,m2),
(13)
К-расстояние или расстояние по Колмогорову между классами определяет1/ 
 
 1
ся как: d ( w1 , w2 )   m m   d lp 
 1 2 l 1 p 1 
m m
1 2
,
(14)
где λ – целое число в диапазоне ± ∞. При λ –> ∞ К-расстояние вырождается в расстояние дальнего соседа, а при λ –> -∞ – в расстояние ближнего соседа.
Отметим, что в (12) – (14) способ определения расстояние между точками
9
dlp выбирается разработчиком системы распознавания, например, из (1) – (7) с
учетом нормирования признаков и введения весовых коэффициентов при необходимости.
Основной целью кластеризации является разбиение множества образов на
подмножества близких между собой образов. Определение степени близости зависит от способа вычисления расстояний и метода кластеризации. Ниже рассмотрено несколько наиболее простых методов кластеризации.
Пороговый алгоритм кластеризации состоит в следующем. Пусть в пространстве признаков задано множество образов M={x1, …, xk, …, xm }, где xk –
вектор признаков k-го образа, m – мощность множества. Будем считать, что центр
первого кластера z1 совпадает с любым из образов множества, например с x1, т.е.
w1 = x1. Далее вычисляется расстояние d21 между образом x2 и центром кластера
w1. Напомним, что способ вычисления расстояния между точкой и кластером выбирается разработчиком. Если значение расстояния больше заранее заданной пороговой величины t, то образ x2 принимается за новый центр кластера w2. В противном случае образ x2 включается в кластер w1. Для следующего образа оцениваются расстояния от него до имеющихся кластеров. Если все расстояния больше
порога, то образ принимается за новый кластер. Если часть расстояний меньше
порога, то образ относится к ближайшему кластеру. Процедура продолжается пока не будут исчерпаны все образы множества M.
Следует отметить, что при добавлении образа в кластер характеристики
кластера пересчитываются. Результат кластеризации зависит от выбора первого
центра кластера, порядка предъявления образов из множества М, способа вычисления расстояния и значения порога.
Для кластеров сложной, например, вытянутой, формы можно применить
метод цепной кластеризации, являющийся разновидностью порогового алгоритма, в котором за расстояние между точкой и кластером в пространстве признаков
принимается расстояние от точки до ближайшего представителя кластера.
Метод заключается в следующем. Вначале любому образу присваивается
принадлежность к первому кластеру. К данному кластеру присоединяются все об10
разы, принадлежность которых к какому-либо кластеру еще не установлена, и
расстояние от которых до исходного образа меньше пороговой величины t. Затем
для каждого из присоединенных образов данная процедура повторяется. После
того как к первому кластеру больше нельзя отнести ни одного образа, из оставшихся образов в качестве исходного образа для второго кластера берется произвольный образ. Процедура повторяется до тех пор, пока не будут исчерпаны все
образы.
Метод кластеризации слиянием тоже достаточно прост. Вначале каждый
образ считается отдельным кластером, далее вычисляется расстояние между всеми кластерами, т.е. формируется квадратная, диагонально-симметричная таблица
расстояний, строки и столбцы которой – имеющиеся кластеры. На каждом шаге
сливаются два самых близких кластера, после чего размер таблицы уменьшается
на единицу и вычисляются новые расстояния между изменившимися кластерами.
Процесс прекращается при достижении заданного числа кластеров или когда расстояние между ближайшими кластерами больше заданной пороговой величины.
Данный метод требует многократных вычислений изменяющихся на каждом шаге расстояний, что может стать достаточно трудоемкой задачей при большом количестве образов.
Метод кластеризации по k средним требует задания числа кластеров – k. На
первом шаге в пространстве признаков произвольно выбирается положение k центров кластеров, не обязательно совпадающих с какими-либо образами. Далее на
каждом шаге, во-первых, каждый образ относится к тому кластеру, расстояние до
центра которого для него минимально, а во-вторых, после распределения всех образов по кластерам производится перерасчет положения центров кластеров. Процесс продолжается до тех пор, пока не стабилизируется состав кластеров.
Цель метода – минимизировать суммарное расстояние от центров кластеров
до отнесенных к ним образов по всем кластерам. Возможно схождение процесса к
локальному минимуму, а также отсутствие образов в некоторых кластерах, но,
изменяя число кластеров и сравнивая результаты, можно найти подходящее число
кластеров.
11
Порядок выполнения работы
1. Разработать программу, выполняющую кластеризацию заданного множества
образов с возможностью нормирования признаков и введения весов (способы
задания расстояний, метод кластеризации и состав множества образов выбирается в соответствии с номером варианта).
2. Провести эксперименты по кластеризации, изменяя порог и/или число формируемых кластеров, а также используя нормирование признаков и весовые коэффициенты.
3. Проанализировать полученные результаты и подготовить отчет.
Содержание отчета
1. Цель работы и задание.
2. Используемые в программе расстояния и метод кластеризации.
3. Описание интерфейса и текст разработанной программы.
4. Результаты экспериментов.
5. Анализ результатов и выводы.
Контрольные вопросы
1. Чем характеризуется образ в пространстве признаков?
2. Что такое расстояние в метрическом пространстве?
3. Какие виды расстояний необходимо задавать для кластеризации?
4. Как вычисляются статистические характеристики кластера?
5. Какие методы кластеризации требуют задания порога?
Варианты заданий
В вариантах заданий, приведенных в таблице 1, используется следующая
нумерация расстояний и методов кластеризации.
Расстояние между образами: 1 – Евклидово; 2 – Манхеттенское; 3 – доминирования; 4 – Камберра; 5 – косинусное.
12
Расстояние между образом и кластером: 1 – до центра кластера; 2 – до
ближнего образа кластера; 3 – Евклидово с учетом дисперсии; 4 – Махаланобиса.
Расстояние между кластерами: 1 – между центрами; 2 – ближнего соседа; 3
– дальнего соседа; 4 – К-расстояние.
Метод кластеризации: 1 – пороговый; 2 – цепной; 3 – слиянием; 4 – по k
средним.
Таблица 1
Расстояние между
№
Метод
№ множества
вар.
образами
кластером и образом
кластерами
кластеризации
образов
1
1,4
1
-
1
1
2
2,3
2
-
2
2
3
1,3
-
1
3
3
4
1,4
1
-
4
4
5
1,2
3
-
1
5
6
1,4
2
-
2
6
7
2,4
-
2
3
7
8
5
3
-
4
8
9
2,3
4
-
1
9
10
1,2
2
-
2
10
11
5
-
3
3
1
12
2,4
4
-
4
2
13
3,4
1
-
1
3
14
5
2
-
2
4
15
1,2
-
4
3
5
16
1,3
1
-
4
6
17
1,2
2
-
1
7
18
1,3
2
-
2
8
19
3,4
-
1
3
9
20
2,3
4
-
4
10
13
Множество образов для кластеризации выбирается из таблицы 2 в соответствии с номером варианта задания.
Таблица 2
№
мн.
1
Состав множества образов для кластеризации
(0,1,1), (0,1,7), (5,7,4), (0,5,5), (9,4,5), (7,1,2) (10,0,19), (0,12,7), (-5,-4,5),
(20,10,15), (0,16,-16), (-1,9,-30), (18,0,17), (6,18,4)
2
(11,2,15), (5,18,4), (-10,-3,6), (18,15,14), (2,19,-13), (-3,5,-33), (13,5,12),
(6,11,1), (-7,-2,2), (14,13,11), (4,20,-11), (-5,8,-21), (-5,-3,2), (16,19,20)
3
(15,6,15), (1,19,0), (-8,-1,4), (13,19,15), (15,17,-14), (-3,9,-35), (12,4,16),
(8,14,9), (-6,0,5), (11,17,10), (12,17,-10), (-1,10,-25), (18,17,-11), (-4,9,-31)
4
(16,1,11), (9,13,8), (-9,-2,1), (17,12,14), (8,16,-19), (-2,7,-29), (19,7,10),
(4,12,5), (-10,-4,3), (16,15,16), (6,16,-17), (-4,6,-32), (12,7,10), (4,20,7)
5
(20,3,19), (7,18,4), (-5,-5,2), (15,19,20), (11,19,-20), (-3,8,-30), (17,5,13),
(6,15,3), (-8,-3,4), (11,13,18), (18,17,-15), (-4,7,-34), (-6,0,1), (20,10,20)
6
(17,0,11), (5,13,0), (-5,-4,0), (14,16,18), (5,15,-11), (-3,10,-35), (16,2,15),
(6,15,3), (-9,-2,5), (19,17,11), (6,13,-14), (-4,5,-25), (15,12,20), (-2,10,-32)
7
(11,5,19), (9,10,4), (-7,0,3), (13,14,15), (12,19,-17), (-5,9,-30), (20,7,20),
(0,19,9), (-6,-1,2), (13,11,18), (0,15,-20), (-2,6,-24), (11,4,15), (3,15,6)
8
(19,4,13), (8,14,10), (-6,-5,1), (20,20,20), (7,16,-17), (-1,7,-26), (15,1,10),
(0,11,8), (-8,-1,5), (10,10,10), (12,15,-10), (-4,5,-27), (-7,-1,4), (13,17,11)
9
(13,6,14), (1,12,6), (-9,-3,0), (19,11,10), (4,5), (-5,8,-28), (12,5,12), (3,17,7), (10,0,4), (15,16,17), (7,20,-14), (0,0,-34), (19,19,-19), (-1,10,-25)
10
(14,3,16), (2,16,1), (-9,-4,3), (18,11,11), (11,15,-12), (-1,7,-32), (10,2,18),
(7,19,2), (-8,-5,6), (15,14,18), (16,16,-20), (-3,6,-33), (13,6,13), (9,16,4)
14
Лабораторная работа №2
МОДЕЛИРОВАНИЕ ОДНОСЛОЙНОЙ НЕЙРОННОЙ СЕТИ
Цель работы: Приобретение практических навыков в моделировании однослойных бинарных нейронных сетей, обучаемых методом коррекции ошибки.
Теоретические пояснения.
Приведенное ниже описание свойств искусственных нейронных сетей взято
из книги Ф.Уоссермена «Нейрокомпьютерная техника: Теория и практика» (Перевод на русский язык – Ю.А.Зуев и В.А.Точенов, 1992).
Искусственные нейронные сети индуцированы биологией, так как они состоят из элементов, функциональные возможности которых аналогичны большинству элементарных функций биологического нейрона. Эти элементы затем
организуются по способу, который может соответствовать или не соответствовать
анатомии мозга. Несмотря на такое поверхностное сходство, искусственные
нейронные сети демонстрируют удивительное число свойств, присущих мозгу.
1) Обучение. Искусственные нейронные сети могут менять свое поведение в
зависимости от внешней среды. Этот фактор в большей степени, чем любой другой, ответствен за тот интерес, который они вызывают. После предъявления входных сигналов (возможно, вместе с требуемыми выходами) они самонастраиваются, чтобы обеспечивать требуемую реакцию. Было разработано множество обучающих алгоритмов, каждый со своими сильными и слабыми сторонами, однако,
все еще существуют проблемы относительно того, чему сеть может обучиться и
как обучение должно проводиться.
2) Обобщение. Отклик сети после обучения может быть до некоторой степени нечувствителен к небольшим изменениям входных сигналов. Эта внутренне
присущая способность видеть образ сквозь шум и искажения жизненно важна для
распознавания образов в реальном мире. Она позволяет преодолеть требование
строгой точности, предъявляемое обычным компьютером, и открывает путь к системе, которая может иметь дело с тем несовершенным миром, в котором мы жи15
вем. Важно отметить, что искусственная нейронная сеть делает обобщения автоматически благодаря своей структуре, а не с помощью использования «человеческого интеллекта» в форме специально написанных компьютерных программ.
3) Абстрагирование. Некоторые из искусственных нейронных сетей обладают способностью извлекать сущность из входных сигналов. Например, сеть
может быть обучена на последовательность искаженных версий буквы «А». После
соответствующего обучения предъявление такого искаженного примера приведет
к тому, что сеть породит букву совершенной формы. В некотором смысле она
научится порождать то, что никогда не видела.
Одной из областей применения нейронных сетей является распознавание
образов в пространстве признаков. Простейшая однослойная нейронная сеть, состоящая из m искусственных нейронов, может быть обучена распознаванию m
классов образов. В процессе обучения нейронной сети предъявляются образы, относящиеся к известным классам, и по результатам на выходе сети производится
корректировка весовых коэффициентов связей нейронов.
Схема искусственного нейрона приведена на рис. 1. Нейрон имеет n входов,
на которые подается вектор входных сигналов X=(x1,…,хn), т.е. в нашем случае
вектор признаков распознаваемого или обучаемого образа. Значения входных
сигналов могут быть действительными или целыми числами, а в простейшем случае принимать только бинарные значения (0, 1). Каждый входной сигнал умножается на соответствующий элемент вектора весовых коэффициентов w = (w1,…,wn).
x0=1
w0
x1
w1
x2
w2
Σ
S
f
y
.......
xn
wn
Рис.1 – Схема искусственного нейрона
16
Взвешенные входные сигналы поступают на блок суммирования, который и
n
определяет уровень возбуждения нейрона s   wi xi или в матричной форме:
i 0
s = wXT.
Выходной сигнал нейрона у определяется пропусканием уровня возбуждения s через нелинейную функцию f: y = f(s). Обычно в качестве функции f исполь1, s  
зуются нелинейные функции, например бинарная y  
, где  - настраивае0, s  
мый порог срабатывания или возбуждения нейрона. Дополнительный весовой коэффициент w0 для постоянного единичного входного сигнала и определяет порог
срабатывания  данного нейрона.
Отдельный нейрон может быть использован для распознавания двух образов, т.к. принимает на выходе два значения – 0 или 1. Однослойная нейронная
сеть, показанная на рис. 2, теоретически может распознавать 2m классов, но на
практике для повышения надежности распознавания каждый нейрон используется
для распознавания только одного класса.
Выходной
вектор Y
Входной
вектор X
x0 =1
x1
w01
I0
N1
y1
w02
w11
N2
I1
y2
w1m
wn1
xn
w0 n
In
wnm
Nm
ym
Рис.2 – Однослойная нейронная сеть
В матричной форме результат работы сети можно представить как Y = f(S),
ST = WTXT, где W – матрица весовых коэффициентов нейронов N (wij – весовой
17
коэффициент связи i-го признака с j-м нейроном). В данном случае предполагается, что для получения элементов вектора Y функция f применяется к каждому
элементу вектора S.
Для обучения или настройки весов нейронной сети применяются различные
методы, среди которых одним из наиболее простых является метод коррекции
ошибки:
Шаг 1 – инициализация. Задается обучающее множество M = {(X(1),T(1)), …
,(X(m), T(m))}, состоящее из пар: вектор признаков X(k) и требуемый выходной вектор T(k), (k=1,…,m). В данном случае один элемент множества M соответствует
одному классу, т.е. мощность множества равна числу распознаваемых классов
(возможно задание нескольких обучающих образов, относящихся к одному классу, но с частично различающимися векторами признаков). Для k-го класса требуемый выходной вектор имеет вид (t1=0, … ,tk=1, …tm=0). Матрица весовых коэффициентов W обнуляется.
Шаг 2 – коррекция весов. Для каждой k-ой пары из множества M входной
вектор Xk подается на вход нейронной сети и проверяется совпадение элементов
выходного Y и требуемого Tk векторов. Если они отличаются, то элементы матрицы весовых коэффициентов W(l-1) корректируется (l – номер коррекции) по пра(l 1)
вилу: wij  wij
(l )
 xi (t j  y j ) (i=0,…,n; j=1,…,m),
(15)
Из (15) видно, что коррекция матрицы WT выполняется только для тех j-х
столбцов, в которых yj ≠ tj, т.е. изменяются весовые коэффициенты только у ошибающихся нейронов.
Шаг 3 – проверка условий окончания обучения. Если для всех пар из множества M после подачи входного вектора выходной и требуемый вектора совпадают, то обучение заканчивается, иначе шаг 2 повторяется.
Основная идея метода заключается в усилении связей, соединяющих нейроны с одинаковой активностью, и ослаблении связей, соединяющих нейроны с различной активностью. Если множество обучающих образов достаточно разнообразно, то в результате обучения нейронная сеть может с высокой надежностью
распознавать образы, отличающиеся в какой-то степени от эталонов.
18
Для бинарных входных и выходных векторов однослойной нейронной сети
коррекция весовых коэффициентов (15) принимает вид:
0,
если y j  t j

  j  xi , где  j  1,
если y j  0, t j  1.
 1, если y  1, t  0
j
j

wij(l )  wij(l 1)
(16)
В качестве примера рассмотрим применение метода коррекции ошибки для
обучения двух нейронов с бинарной функцией возбуждения распознаванию двух
бинарных изображений, показанных на рисунке 3. Согласно рисунку 3 у нас имеется два класса, каждый из которых состоит из одного эталонного образа, представленного вектором признаков из девяти элементов (нумерация признаков приведена на рис. 3). В таком случае каждый нейрон выходного слоя должен иметь
10 входов, включая нулевой вход с постоянной единицей, вес которого и определяет смещение. Пусть первому изображению соответствует единичный выходной
сигнал только первого нейрона, а второму изображению – только второго.
x(1)
x(2)
w(1/2)
1
2
3
1
2
3
0/0
-1/1
0/0
4
5
6
4
5
6
0/0
0/-1
0/0
7
8
9
7
8
9
-1/1
0/0
0/0
темная клетка – 1,
светлая – 0
w01 = 0, w02 = 0
Рис. 3 – Распознаваемые бинарные изображения и весовые коэффициенты
первого и второго нейронов после обучения
Шаг 1 – инициализация. Обучающее множество состоит из двух элементов:
M = {(x(1) = (1,0,1,1,1,1,0,0,1), t(1) = (1,0)); (x(2) = (1,1,1,1,0,1,1,0,1), t(2) = (0,1))}.
Матрица весовых коэффициентов обнуляется: w(0) = 0, т.е. wi1 = 0, wi2 = 0 (i=0, …,
9).
Шаг 2 – ввод очередного образа из множества M и коррекция весов. На входы нейронов подается вектор x, выходной вектор y сравнивается с t и веса связей
19
корректируются согласно (16). Результаты вычислений векторов s и y, а также
коррекция весовых коэффициентов приведены в таблице 3.
Шаг 3 – проверка условий окончания обучения. Из таблицы 3 видно, что
после двух последних предъявлений коррекция W не производилась, следовательно, обучение закончено.
При наличии нескольких различных образов, относящихся к одному классу,
обучение продолжалось бы, до тех пор, пока нейронная сеть не научилась бы правильно различать все образы из обучаемого множества.
Таблица 3 – Изменение весовых коэффициентов.
x
t
s
y
t-y
1
1
0
1
0
0
0
0
1
-1
0
0
1
1
-6
1
2
1
2
1
w0j w1j
w2j
w3j
w4j
w5j
w6j
w7j
w8j
w9j
0
0
0
0
0
0
0
0
0
-1
-1
0
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
0
-1
0
1
0
0
1
0
0
-1
0
1
0
0
-6
0
1
0
0
-1
0
0
0
0
-1
0
0
0
-1
0
0
0
0
1
0
0
-1
0
1
0
0
0
-2
0
0
0
0
-1
0
0
0
0
-1
0
0
1
2
1
0
0
0
1
0
0
-1
0
1
0
0
1
0
1
0
0
0
-1
0
0
0
0
-1
0
0
0
-1
0
0
0
0
1
0
0
-1
0
1
0
0
Полученные в результате обучения веса связей приведены на рис. 3. Обратите внимание, что нулевые веса соответствуют одинаковым значениям признаков образов x(1) и x(2), т.е. эти признаки не используются при распознавании. Для
упрощения структуры нейронной сети после обучения можно удалить связи между нейронами с нулевыми весами и сократить вектор признаков x.
Проверим, способна ли обученная нейронная сеть распознать образы, отличающиеся от эталонных значениями признаков x2, x5 или x7, у которых веса связей
с нейронами выходного слоя отличны от нуля.
20
Пусть надо распознать образ x = (1,1,1,1,1,1,1,0,1), отличающийся от x(2)
значением x5. Тогда s1 = -2, s2 = 1, следовательно у1 = 0, у2 = 1. Распознаваемый
образ относится ко второму классу.
Пусть надо распознать образ x = (1,0,1,1,0,1,0,0,1), отличающийся от x(1) тоже значением x5. Тогда s1 = 0, s2 = 0, следовательно у1 = 1, у2 = 1. Образ не распознан.
Пусть надо распознать образ x = (1,1,1,1,1,1,0,0,1), отличающийся от x(1)
значением x2. Тогда s1 = -1, s2 = 0, следовательно у1 = 0, у2 = 1. Распознаваемый
образ ошибочно отнесен ко второму классу.
Таким образом, однослойная сеть обладает свойствами обучения и обобщения, правда в минимальной степени. Для увеличения надежности распознавания
необходимо ввести в обучающее множество М несколько различных образов, относящихся к одному классу, что со своей стороны приведет к увеличению времени обучения.
Еще один серьезный недостаток построенной сети заключается в том, что в
распознавании участвует только небольшая часть (33%) элементов входного вектора x. В результате образ x = (0,0,0,0,1,0,0,0,0) будет отнесен к первому классу,
что явно является ошибкой, т.к. данный вектор не похож на x(1) или x(2).
Для устранения таких ошибок можно ввести дополнительный нейрон, выдающий на выходе единицу при наличии во входном векторе числа единиц больше порогового значения, например, пять и более единиц. Настройка весов такого
нейрона имеет вид: w0=5, w1= w2= w3= w4= w5= w6= w7= w8= w9= 1. После ввода в
сеть дополнительного нейрона распознаваемый образ будет отнесен к первому
классу, если y = (1,0,1), и ко второму классу, если y = (0,1,1). При любых других
значениях элементов вектора y образ можно считать нераспознанным.
Следует отметить, что однослойные нейронные сети способны обучиться
распознаванию только классов, множество образов которых линейно разделимо в
пространстве признаков.
21
Порядок выполнения работы
1. Разработать структуру сети, обучаемой по методу коррекции ошибки, которая
сможет распознавать первые буквы из Вашей фамилии, имени, отчества и
цифры Вашего порядкового номера в списке группы (всего 5 разных символов, размерность входного вектора – не менее 35).
2. Написать программу, моделирующую разработанную сеть. Предусмотреть два
режима работы (обучение и распознавание), возможность ввода распознаваемых образов и обучающего множества, регистрацию, матрицы весовых коэффициентов, количества циклов обучения и результатов распознавания.
3. Подготовить два обучающих множества - с одиночными эталонными образами для каждого класса и с различающимися образами, относящимися к одному классу.
4. Провести обучение и распознавание образов, не входящих в обучающие множества. Зафиксировать число циклов обучения для разных обучающих множеств и результаты распознавания.
Содержание отчета
1. Цель работы и задание.
2. Структура разработанной нейронной сети.
3. Текст программы и описание пользовательского интерфейса.
4. Содержание обучающих множеств и распознаваемые образы.
5. Результаты обучения и распознавания.
6. Выводы.
Контрольные вопросы
1. Какими свойствами обладают нейронные сети?
2. Что представляет собой и как работает искусственный нейрон?
3. Как производится обучение нейронных сетей?
4. Для чего требуется дополнительный постоянный вход x0?
5. Из каких шагов состоит метод обучения коррекцией ошибки?
22
Лабораторная работа №3
ПОДГОТОВКА БАЗЫ ДАННЫХ ЭКСПЕРТНОЙ СИСТЕМЫ
Цель работы: Ознакомиться с принципами построения базы данных экспертной
системы, использующей вероятностный подход к распознаванию, и заполнить
сформированную структуру базы данных информацией, необходимой для решения конкретной задачи.
Теоретические пояснения.
Одно из основных отличий систем распознавания от экспертных систем состоит в том, что в системе распознавания, как правило, распознаваемый образ
представляется вектором признаков, в котором перед началом распознавания все
значения элементов известны. В экспертных системах процесс распознавания
совмещен с процессом получения информации об объекте, причем последовательность получения значений признаков меняется в зависимости от полученных
ранее данных. Такой подход к распознаванию применяется при большом количестве признаков и классов, иерархической структуре классов и отсутствии в описании каждого класса всех признаков. Кроме этого, в экспертных системах часто
требуются большие затраты на получение значений признаков. Например, в медицинской диагностике полное обследование пациента может включать в себя
длительные и дорогостоящие анализы, проведение которых требуется далеко не
при всех диагнозах. Далее рассматривается подход к построению экспертных систем, в которых информация о распознаваемых объектах носит вероятностный
характер.
Цель экспертной системы – на основании полученных данных о распознаваемом объекте сделать вывод о его принадлежности к известному системе классу,
причем желательно минимизировать объем получаемых данных о распознаваемом объекте. В зависимости от области применения система может на основании
симптомов поставить диагноз больному, по значениям параметров найти неисправность в устройстве, по геологическим характеристикам местности предска23
зать наличие полезных ископаемых, по психофизическим характеристикам и
предпочтениям человека подобрать подходящую сферу деятельности или место
отдыха и т.д.
Экспертная система состоит из двух достаточно независимых частей – программы-оболочки для хранения и обработки информации и базы данных с необходимыми для работы системы сведениями о конкретной области знаний. Процесс создания экспертной системы включает в себя следующие этапы:
-
разработка структуры базы данных;
-
разработка алгоритмов выбора последовательности запросов и принятия
решения;
-
разработка диалогового интерфейса;
-
заполнение базы данных;
-
тестирование.
Если интерфейс экспертной системы соответствует требованиям пользова-
теля и тестирование системы дает удовлетворительные результаты, то система
принимается в опытную эксплуатацию. Во время опытной эксплуатации экспертной системы информация, заложенная в базу данных, корректируется с целью получения адекватных ответов.
При построении экспертной системы одной из основных проблем является
формализация представления знаний о связях между признаками (в дальнейшем
будем называть их симптомами) и классами образов (в дальнейшем будем называть их диагнозами). Заметим, что часто эти связи носят вероятностный характер,
т.е. одно и тоже значение симптома может с разной вероятностью соответствовать
нескольким диагнозам. Например, в медицинской сфере боль в горле является
симптомом, как ангины, так и наличия инородного тела, или в сфере технической
диагностики отсутствие света фар у автомобиля может быть следствием, как севшего аккумулятора, так и неисправности проводки.
Проблему представляет и количественное описание симптомов. Например,
если с температурой, весом, ростом или давлением проблем на первый взгляд не
будет, то такие характеристики как уровень головной боли или износ покрышек
24
количественно оценить труднее. В таком случае возможно задание нескольких
диапазонов. Например, при вопросе об уровне боли ответ может выбираться из
трех вариантов – легкая боль, средняя, острая. Симптомы могут быть и бинарными, т.е. иметь только два возможных значения – да или нет, например, наличие
света фар.
Рассмотрим одну из возможных структур базы данных для представления в
экспертной системе знаний о конкретной области ее применения.
Симптомы Xi (i = 1 ... n), где n – число симптомов, удобно представить в виде списка вопросов, которые система будет задавать в процессе работы, т.е. всего
один вопрос на каждый симптом. Например, «Ваш вес?», «Уровень боли в горле»,
«Включаются ли фары автомобиля?» и т.п.
Диагнозы Wj (j =1 … k), где k – число диагнозов, можно представить в виде
списка со строками разной длины. Каждая строка списка описывает один диагноз
и состоит из следующих полей:
-
название диагноза Wj;
-
априорная вероятность диагноза pa(Wj);
-
связь данного диагноза с симптомами в виде массива из трех элементов –
номер строки симптома Xi, условная вероятность наличия данного симптома
при данном диагнозе p(Xi/Wj), условная вероятность наличия данного симптома при любом другом диагнозе p(Xi/noWj).
Под априорной вероятностью диагноза понимается вероятность наличия
данного диагноза у объекта при отсутствии информации о симптомах. Например,
у людей ангина встречается чаще, чем инфаркт, а у автомобилей севший аккумулятор встречается чаще, чем обрыв в проводке.
Заметим, что сумма последних двух вероятностей не равна единице. Например, при гриппе головная боль присутствует в 80%, а в 30% случаев присутствие
головной боли вызвано другим диагнозом. Сумма априорных вероятностей по
всем диагнозам должна быть меньше единицы, т.к. показывает вероятность наличия у объекта какого-либо диагноза (неисправности, болезни).
25
Если между симптомами отсутствует корреляция, т.е. они статистически независимы, то возможно применение соответствующих формул для вычисления
оценки возможных вероятностей диагнозов. Два симптома X1 и X2 статистически
независимы, если для j-го диагноза условная вероятность p(X1&X2/Wj) =
p(X1/Wj)*p(X2/Wj). Например, пусть из 100 автомобилей у 20-ти не горят фары, а у
10-ти не заводится двигатель. Эти события можно считать статистически независимыми, если у 2-х автомобилей одновременно не горят фары и не заводится двигатель (20/100 * 10/100 = 2/100). При выборе симптомов необходимо проверять их
статистическую независимость. Например, существует корреляция между симптомами «наличие озноба» и «высокая температура». Использование таких симптомов делает некорректным использование статистических формул для вычисления условных вероятностей диагнозов, связанных с этими симптомами.
При необходимости можно дополнить структуру базы данных и списком
рекомендаций по каждому диагнозу, которые будут выдаваться пользователю после принятия системой решения о наиболее вероятном диагнозе.
Заполнение базы данных, пожалуй, наиболее ответственный, сложный и
трудоемкий этап создания экспертной системы. От его результатов в основном
зависит правильность работы экспертной системы. Основные трудности заключаются в сборе и обработке статистической информации. Например, на первый
взгляд, при подготовке экспертной системы в области медицины достаточно взять
справочник по болезням и выписать из него диагнозы с соответствующими симптомами. Однако вряд ли Вы найдете в справочнике данные об априорных вероятностях заболеваний и тем более условные вероятности симптомов по каждому
диагнозу.
При подготовке вопросов по симптомам большую сложность представляет
проверка статистической независимости симптомов. Если между симптомами
есть корреляция, то приходится задавать условные вероятности всех возможных
сочетаний симптомов для каждого диагноза, что существенно увеличивает объем
базы данных.
26
Важно правильно сформулировать связанный с симптомом вопрос, а также
дать возможные варианты ответов. Бывает полезно представить последовательность вопросов, в которой последующие уточняют предыдущие. Например, первый вопрос – «Бывают ли у Вас боли в груди?» можно дополнить вопросами о частоте, месте и уровне болей. При этом не следует забывать, что каждый вопрос
должен быть связан хотя бы с одним диагнозом.
Формирование списка, связывающего диагноз с симптомами, с указанием
условных вероятностей также представляет собой серьезную проблему. Для каждого диагноза необходимо максимально полно учесть связанные с ним симптомы.
Не следует забывать, что на повышение вероятности диагноза влияют как положительный, так и отрицательный ответы. Таким образом, для одного и того же
вопроса положительный ответ может быть связан с одним диагнозом, а отрицательный – с другим.
Можно предложить следующий порядок подготовки базы данных системы –
на первом этапе формируется список диагнозов с соответствующими им симптомами, а по нему составляется список симптомов с соответствующими вопросами.
На втором этапе собирается необходимая статистическая информация, что требует изучения имеющихся источников и возможно проведения специальных исследований.
Порядок выполнения работы
1. Выбрать предметную область для разрабатываемой экспертной системы: медицинская или техническая диагностика, определитель биологических объектов (растения, животные и т.п.), прогнозирование событий (погода, фондовый
рынок), рекомендации по выбору пользователем профессии, места отдыха, товара и т.п. Согласовать предметную область с преподавателем.
2. Разработать структуру базы данных для экспертной системы с учетом особенностей выбранной предметной области. Обеспечить возможность извлечения
и наглядного представления информации из базы данных. Минимальные требования к объему базы данных:
27
- количество признаков (симптомов) – не менее 20;
- количество классов (диагнозов) – не менее 10;
- количество симптомов в каждом классе (диагнозе) – не менее 5.
3. Собрать необходимую информацию и заполнить базу данных. Проанализировать возможность статистической независимости выбранных признаков.
Содержание отчета
1. Цель работы и задание.
2. Структура разработанной базы данных для экспертной системы в выбранной
предметной области.
3. Содержание базы данных.
4. Оценка статистической независимости выбранных признаков.
5. Выводы.
Контрольные вопросы
1. В чем основное отличие экспертной системы от других систем распознавания?
2. Каким образом в структуре базы данных учитывается вероятностный характер
связи признаков с классами?
3. Из каких элементов состоит структура базы данных экспертной системы?
4. При каком условии признаки можно считать статистически независимыми?
5. Приведите последовательность действий при сборе и первоначальной обработке информации для базы данных экспертной системы?
28
Лабораторная работа №4
РАЗРАБОТКА ОБОЛОЧКИ ЭКСПЕРТНОЙ СИСТЕМЫ
Цель работы: Ознакомиться с принципами функционирования экспертной системы, использующей вероятностный подход к распознаванию, и разработать реализующую ее программу.
Теоретические пояснения.
Далее рассматривается построение достаточно универсальной экспертной
системы, способной диагностировать объект в некоторой области знаний после
заполнения базы данных системы соответствующей информацией. Система
должна последовательно задавать вопросы о состоянии объекта, причем их количество и порядок могут меняться в зависимости от полученных ранее ответов, и
после анализа имеющихся данных принять решение, т.е. отнести объект к одному
из известных системе классов.
Алгоритм работы экспертной системы является циклическим. В каждом
цикле анализируется один симптом (напомним – в структуре базы данных, описанной в предыдущей работе, имеется один вопрос на каждый симптом). Для этого выполняется следующая последовательность шагов:
-
выбирается наиболее информативный симптом и задается соответствующий ему вопрос;
-
полученный ответ используется для вычисления вероятностей диагнозов, а
вопрос (симптом) больше не задается;
-
по результатам вычисления некоторые диагнозы могут исключаться из
дальнейшего рассмотрения;
-
если вероятность какого-то диагноза достаточна для принятия решения, то
система заканчивает работу, если нет – то цикл повторяется.
Особенность экспертной системы состоит в том, что не все признаки (симп-
томы) используются в описании каждого класса (диагноза), а при получении информации о симптоме вероятности связанных с ним диагнозов изменяются. В та29
ком случае, можно считать наиболее информативным вопрос о симптоме, ответ
на который изменит вероятность максимального числа диагнозов. Вычислить этот
показатель довольно легко – для каждого еще не заданного вопроса определяется
количество еще не исключенных диагнозов, в которых он учитывается. Вопрос с
максимальным значением считается самым информативным в текущем цикле.
В зависимости от вопроса ответ может иметь разный вид (целочисленный,
перечисляемый, бинарный). В простейшем случае ограничимся рассмотрением
только вопросов с бинарным ответом – положительным или отрицательным.
Получив ответ на заданный вопрос, необходимо использовать его для вычисления вероятностей диагнозов, в описании которых он присутствует. При этом
подтверждать диагноз может как положительный, так и отрицательный ответ. Для
вычисления условной вероятности диагноза при наличии данного симптома (ответ «да») используется формула Байеса
p(Wj / Xi ) 
p(Wj ) * p( Xi / Wj )
,
p(Wj ) * p( Xi / Wj )  (1  p(Wj )) * p( Xi / noWj )
(17)
где p(Wj)- вероятность диагноза Wj на текущем шаге. До получения ответа
на первый вопрос p(Wj) = pa(Wj), а после обработки ответа на i-й вопрос можно
считать p(Wi) = p(Wi/Xj). При ответе «нет»
p(Wj / Xi ) 
p(Wj ) * (1  p( Xi / Wj ))
p(Wj ) * (1  p( Xi / Wj ))  (1  p(Wj )) * (1  p( Xi / noWj ))
(18).
Если вероятность p(Wj/Xi), вычисленная по (17) или (18), близка к нулю, то
j-й диагноз можно исключить из дальнейшего рассмотрения. Если вероятность
p(Wj/Xi) близка к единице, то j-й диагноз можно считать истинным и закончить
работу системы. Порог близости устанавливается заранее и его точное значение
подбирается экспериментально в процессе настройки системы.
После того как будут пересчитаны вероятности всех диагнозов, в описании
которых используется симптом, связанный с заданным вопросом, необходимо для
каждого из этих диагнозов оценить возможные максимальную и минимальную
вероятности. Для этого у каждого диагноза просматривается список еще не рассмотренных симптомов и по каждому из них выполняется следующая последова30
тельность действий (при первом цикле эта последовательность выполняется для
всех диагнозов).
Во-первых, необходимо определить какой ответ – положительный или отрицательный, увеличивает вероятность j-го диагноза. Если p(Xi/Wj) > p(Xi/noWj),
то положительный ответ увеличивает p(Wj/Xi) и при оценке возможных вероятностей диагноза расчетные условные вероятности p'(Xi/Wj) и p'(Xi/noWj) не изменяются, т.е. p'(Xi/Wj) = p(Xi/Wj) и p'(Xi/noWj) = p(Xi/noWj). Если же p(Xi/Wj) <
p(Xi/noWj), то p(Wj/Xi) увеличивается при отрицательном ответе и для оценки
следует использовать обратные значения условных вероятностей, т.е. считать
p'(Xi/Wj) = 1 – p(Xi/Wj), p'(Xi/noWj) = 1 – p(Xi/noWj).
(19)
Если между симптомами нет корреляции, т.е. они статистически независимы, то максимально и минимально возможные вероятности диагноза вычисляются как произведение условных вероятностей по всем еще не заданным вопросам,
связанным с симптомами данного диагноза, при условии соответственно положительных и отрицательных ответов на них.
Во-вторых, с учетом (19) вычисляются четыре условные вероятности (m –
число еще не рассмотренных симптомов j-го диагноза):
-
вероятность j-го диагноза при всех положительных ответах
p(Wj / X  ) 
m
 p( Xi / Wj) ;
i 1
-
вероятность не j-го диагноза при всех положительных ответах
p(noWj / X  ) 
m
 p( Xi / noWj) ;
i 1
-
вероятность j-го диагноза при всех отрицательных ответах
p(Wj / noX  ) 
(20)
m
 (1  p( Xi / Wj)) ;
i 1
-
вероятность не j-го диагноза при всех отрицательных ответах
p(noWj / noX  ) 
m
 (1  p( Xi / noWj)) .
i 1
31
В-третьих, используя результаты вычислений (20), по формуле Байеса определяются максимально возможная вероятность i-го диагноза
pmax (Wj ) 
p(Wj ) * p(Wj / X  )
p(Wj ) * p(Wj / X  )  (1  p(Wj )) * p(noWj / X  )
(21)
и минимально возможная вероятность i-го диагноза
pmin (Wj ) 
p(Wj ) * p(Wj / noX  )
p(Wj ) * p(Wj / noX  )  (1  p(Wj )) * p(noWj / noX  )
(22).
Если pmax(Wj) < p(Wj), то j-й диагноз можно исключить из дальнейшего рассмотрения, т.к. его максимально возможная вероятность при всех положительных
симптомах меньше вероятности наличия данного диагноза у объекта до получения каких-либо данных о еще не рассмотренных симптомах.
После оценки возможных максимальных и минимальных вероятностей всех
еще не исключенных из рассмотрения диагнозов выполняется поиск наиболее вероятного диагноза. Для этого находится диагноз Wd, у которого минимально возможная вероятность максимальна, т.е. pmin(Wd) ≥ pmin(Wj) для всех j = 1…k. Если
минимально возможная вероятность этого диагноза больше максимально возможной вероятности любого другого диагноза, т.е. pmin(Wd) ≥ pmax(Wj) для всех j =
1…k, i ≠ d, то диагноз Wd считается наиболее вероятным и сообщается пользователю. Если такой диагноз не находится, то цикл повторяется.
Процесс выполняется до тех пор, пока не найден наиболее вероятный диагноз, или не рассмотрены все симптомы, или не исключены все диагнозы. В двух
последних случаях система не принимает никакого решения, но может выдавать
пользователю вероятности диагнозов после последнего цикла.
Минимальный диалоговый интерфейс экспертной системы должен обеспечивать возможность задавать пользователю вопросы, получать от него ответы в
требуемой форме и сообщать результат работы – наиболее вероятный диагноз и
соответствующую рекомендацию, если она имеется. Полезной для пользователя
будет информация о количестве уже заданных и еще оставшихся вопросов, число
и наименование исключенных из рассмотрения диагнозов, а по окончании работы
системы – наименования ближайших диагнозов, со значениями их вероятностей.
32
Для анализа работы системы и внесения необходимых изменений в алгоритм и базу данных следует обеспечить в отладочном режиме на каждом шаге
возможность просмотра результатов вычислений и при необходимости их сохранения, а также фиксации последовательности заданных вопросов и полученных
ответов. Эта информация облегчает выявление причин неадекватной реакции системы, внесение изменений в базу данных и повторное прохождение последовательности вопросов и ответов.
Для облегчения ввода априорных вероятностей диагнозов и условных вероятностей симптомов можно предусмотреть ввод только начальных статистических данных, переложив на систему вычисления соответствующих вероятностей и
проверку корректности введенных данных. Например, вводится общее число обследованных объектов, число объектов имеющих данный диагноз и число объектов имеющих данный симптом при данном диагнозе. Из этой информации можно
вычислить априорные вероятности диагнозов, условные вероятности, связывающие симптомы и диагнозы, а также проверить корректность исходных данных.
Тестирование экспертной системы производится для обнаружения недостатков и внесение необходимых изменений. На первом этапе проверяется работоспособность системы, т.е. корректность работы алгоритма и удобство интерфейса, на втором – полнота и непротиворечивость информации, заложенной в базу данных о конкретной области знаний.
Для проверки работоспособности системы база данных заполняется тестовой информацией минимально необходимого объема. Данные подготавливаются
таким образом, чтобы можно было на каждом шаге следить за процессом решения
и проверить реакцию системы в критических ситуациях.
Правильность заполнения базы данных проверить значительно сложнее, т.к.
количество возможных сочетаний симптомов не позволяет проверить реакцию
системы на них в полном объеме. Например, пусть имеется всего 100 симптомов
и каждый может принимать 2 значения. Тогда число возможных комбинаций
симптомов с разными значениями составляет 2100. Конечно реальное число комбинаций несколько меньше этой оценки, но в целом порядок сохраняется.
33
Разработчики экспертных систем вынуждены очень тщательно готовить исходные данные и проверять правильность их внесения в систему. После проверки
некоторого количества комбинаций симптомов с заранее известным результатом
система переводится в опытную эксплуатацию, в процессе которой могут продолжать выявляться некорректные результаты.
Рассмотрим пример работы системы, построенной по изложенному выше
алгоритму. В качестве исходных данных возьмем не связанную с конкретной областью абстрактную информацию, приведенную в таблице 4.
Таблица 4 – исходные значения p(Xi/Wj) и p(Xi/noWj)
Диагноз 1
Диагноз 2
Диагноз 3
pa(Wj)
0,3
0,2
0,1
Симптом 1
0,6/0,01
-
0,8/0,03
Симптом 2
0,7/0,02
0,8/0,01
0,02/0,1
Симптом 3
0,1/0,2
0,9/0,02
0,9/0,01
Симптом 4
-
0,01/0,07
0,7/0,04
В нашей базе данных всего четыре симптома или признака (i = 1…4) и три
возможных диагноза или класса (j = 1…3). Первый диагноз связан с первыми тремя симптомами, второй – с последними тремя, а третий – со всеми четырьмя
симптомами. Напомним, что pa(Wj) – априорная вероятность диагноза Wj, p(Xi/Wj)
– условная вероятность наличия симптома Xi при диагнозе Wj, p(Xi/noWj) –
условная вероятность наличия симптома Xi при отсутствии диагноза Wj.
Наша информация не является статистически полной, т.к. сумма априорных
вероятностей всех диагнозов меньше единицы и для некоторых комбинаций «диагноз – симптом» информация отсутствует. Например, неизвестна статистика по
первому симптому при первом диагнозе, что неэквивалентно отсутствию первого
симптома при первом диагнозе, т.к. такая информация (отсутствие симптома)
подтверждала бы первый диагноз. В нашем случае для этой пары отсутствуют
статистические данные, что не помешает разработке экспертной системы, но мо34
жет сказаться на результатах ее работы. В случае появления недостающей статистики она может быть добавлена в базу данных, и после переобучения результаты
работы, скорее всего, улучшатся.
До начала первого цикла «вопрос-ответ» текущая вероятность каждого диагноза принимаем равной его априорной вероятности p(Wj) = pa(Wi). Далее определим максимально и минимально возможные вероятности диагнозов.
Для этого при условии статистической независимости симптомов вычислим
по (20) условные вероятности для диагноза W1 (в данный момент еще не задано ни
одного вопроса и ни один диагноз не исключен из рассмотрения):
p(W1/XП) = 0,6*0,7*0,9 = 0,378; p(noW1/XП) = 0,01*0,02*0,8 = 0,00016;
p(W1/noXП) = 0,4*0,3*0,1 = 0,012; p(no W1/noXП) = 0,99*0,98*0,2 = 0,19404.
Заметим, что у третьего симптома согласно (19) используются обратные условные
вероятности p'(X3/W1) и p'(X3/noW1), т.к. p(X3/W1) < p(X3/noW1).
Далее согласно (21) и (22) найдем:
pmax(W1) = (0,3*0,378)/(0,3*0,378+0,7*0,00016) = 0,999;
pmin(W1) = (0,3*0,012)/(0,3*0,012+0,7*0,19404) = 0,02582.
Аналогично вычисляются pmax и pmin для двух других диагнозов. Результаты
расчетов приведены в таблице 5.
Таблица 5 – начальные pmax и pmin
Диагноз 1
Диагноз 2
Диагноз 3
0,378
0,7128
0,49392
p(noWj/XП)
0,00016
0,00019
0,00119
p(Wj/noXП)
0,012
0,0002
0,00012
p(noWj/noXП)
0,19404
0,06791
0,09219
pmax(Wj)
0,99901
0,99893
0,97878
pmin(Wj)
0,02582
0,00074
0,00014
p(Wj/XП)
В качестве критерия информативности симптома можно выбрать среднюю
вероятность диагнозов, в описание которых входит данный симптом. Чем эта
35
средняя вероятность выше, тем информативнее симптом. В нашем случае второй
и третий симптомы присутствуют в описании всех диагнозов, и задаваемый вопрос приходится выбирать случайным образом. Пусть это будет вопрос о втором
симптоме и на него получен ответ «да».
Исключим второй симптом из списка и согласно (17) вычислим текущие
значения вероятностей тех диагнозов, в описании которых он входит:
p(W1/X2) = (0,3*0,7)/(0,3*0,7+0,7*0,02) = 0,9375;
p(W2/X2) = (0,2*0,8)/(0,2*0,8+0,8*0,01) = 0,95238;
p(W3/X2) = (0,1*0,02)/(0,1*0,02+0,9*0,1) = 0,02174.
После обработки ответа на второй вопрос наибольшая вероятность у второго диагноза, но если принять порог достоверности 0,99, то вероятность
p(W2)=0,95238 недостаточна для принятия решения.
Повторим вычисление pmax и pmin для всех диагнозов, не забывая, что второй
симптом исключен. Результаты расчетов приведены в таблице 6.
Таблица 6 – p(Wi), pmax и pmin после ответа на вопрос № 2
Диагноз 1
Диагноз 2
Диагноз 3
p(Wj)
0,9375
0,95238
0,02174
p(Wj/XП)
0,54
0,891
0,504
p(noWj/XП)
0,008
0,0186
0,00001
p(Wj/noXП)
0,04
0,001
0,006
p(noWj/noXП)
0,198
0,0686
0,92189
pmax(Wj)
0,99901
0,99896
0,99893
pmin(Wj)
0,75188
0,22573
0,00015
Из таблицы 6 видно, что пока ни один диагноз нельзя исключить. Максимальное значение pmin имеет первый диагноз, но pmax(W2) > pmin(W1), следовательно, первый диагноз пока нельзя считать наиболее вероятным.
Из оставшихся трех симптомов наиболее информативным будет третий.
Пусть на него получен ответ «нет».
36
Исключим третий симптом из списка и согласно (18) вычислим текущие
значения вероятностей тех диагнозов, в описании которых он входит, учитывая
отрицательный ответ:
p(W1/X3) = (0,9375*0,3)/(0,9375*0,3+0,0625*0,98)= 0,94406;
p(W2/X3) = (0,2*0,8)/(0,2*0,8+0,8*0,01)=0,67114;
p(W3/X3) = (0,1*0,02)/(0,1*0,02+0,9*0,1)=0,0022.
После обработки ответа на третий вопрос наибольшая вероятность у первого диагноза, но порог достоверности не преодолен.
Повторим вычисление pmax и pmin для всех диагнозов, не забывая, что второй
и третий симптомы исключены. Результаты расчетов приведены в таблице 7.
Таблица 7 – p(Wi), pmax и pmin после ответа на вопрос № 3
Диагноз 1
Диагноз 2
Диагноз 3
p(Wi)
0,94406
0,67114
0,00022
p(Wi/XП)
0,6
0,99
0,56
p(noWi/XП)
0,01
0,93
0,012
p(Wi/noXП)
0,4
0,01
0,06
p(noWi/noXП)
0,99
0,07
0,9312
pmax(Wi)
0,99901
0,68479
0,51160
pmin(Wi)
0,87209
0,22573
0,00015
На этот раз значение pmin снова имеет первый диагноз, но pmax(W2) < pmin(W1)
и pmax(W3) < pmin(W1), следовательно, первый диагноз можно считать наиболее вероятным.
Если на каждый вопрос отвечать «да», то экспертная система задаст все вопросы и будет вынуждена выбрать в качестве наиболее вероятного третий диагноз, хотя его вероятность почти совпадает с вероятностью второго диагноза (после окончания работы p(W3) = 0,99893; p(W2) = 0,99228).
Необходимо отметить, что наша экспертная система представляет собой довольно грубую модель реальной экспертной системы, способную распознавать
37
сильно отличающиеся диагнозы при отсутствии корреляции симптомов. Реальные
экспертные системы должны уметь различать близкие диагнозы при условии корреляции некоторых симптомов, что требует подстройки программы-оболочки под
конкретную область знаний.
Порядок выполнения работы
1. Изучить теоретические основы проектирования экспертной системы, в которой информация о распознаваемых объектах носит вероятностный характер.
2. Разработать исполняемые модули программы, реализующей оболочку экспертную системы, в среде визуального программирования на одном из объектно-ориентированных языков высокого уровня по выбору студента.
3. Разработать интерфейс для реализации экспертной системы в форме Windowsприложения. Приложение должно обеспечивать:
-
ввод и отображение информации, из базы данных,
-
вывод принятого решения с указанием вероятности диагноза,
-
возможность пошагового наблюдения за процессом принятия решения.
4. Провести эксперименты по применению подготовленной базы данных для
разработанной оболочки экспертной системы. Система должна принимать
правдоподобные решения при соответствующих ответах на вопросы. При
необходимости следует внести изменения в базу данных.
5. Проверить изменение порядка запроса признаков (симптомов) при изменении
их значений в процессе ввода.
Содержание отчета
1. Цель работы и задание.
2. Описание исполняемых модулей и пользовательского интерфейса.
3. Содержание базы данных.
4. Результаты работы экспертной системы.
5. Выводы.
38
Контрольные вопросы
1. Приведите последовательность действий экспертной системы в каждом цикле.
2. Как выбирается следующий задаваемый вопрос о симптоме?
3. Вероятности каких диагнозов изменяются при получении значения симптома?
4. Как оцениваются возможные вероятности диагнозов?
5. В каких случаях система прекращает работу?
39
Рекомендуемая литература.
1. Ерош, И.Л. Обработка и распознавание изображений в системах превентивной
безопасности / И.Л. Ерош, М.Б. Сергеев, Н.В. Соловьев. СПб.: ГУАП, 2006. –
154 с.
2. Соловьев, Н.В. Введение в системы искусственного интеллекта / Н.В. Соловьев. СПб.: ГУАП, 2008, – 104 с.
3. Люгер, Д.Ф. Искусственный интеллект: стратегии и методы решения сложных
проблем: пер. с англ. / Д.Ф. Люгер. М.: Вильямс, 2003. – 864с.
4. Буреева, Н.Н. Многомерный статистический анализ с использование ППП
Statistica : учеб. пособие / Н.Н. Буреева. Нижний Новгород : НГУ, 2007 – 114с.
5. Бородин, А.Н. Элементарный курс теории вероятностей и математической статистики / А.Н. Бородин. СПб.: Лань, 2002. – 256с.
6. Уоссерман, Ф. Нейрокомпьютерная техника: пер. с англ./ Ф. Уоссерман. М.:
Мир, 1992. – 126c.
7. Нейлор, К. Как построить свою экспертную систему: пер. с англ. / К. Нейлор.
М.: Энергоатомиздат, 1991. – 286с.
40
Документ
Категория
Без категории
Просмотров
1
Размер файла
558 Кб
Теги
popovsoloviev
1/--страниц
Пожаловаться на содержимое документа