Файл: Методыискусственногоинтеллекта.pdf

100
Гл. 2. Методы автоматизации рассуждений
где i, j — все возможные пары индексов измеряемых признаков,
(i, j = 1, 2, ... , n). Выражения в скобках есть отклонения значений переменных x
β
1k от соответствующего среднего x ik
. n — количество объектов в классе. При i = j вычисляются среднеквадратичные от- клонения, которые соответствуют дисперсиям параметров, а при i 6= j оценивается ковариация между двумя параметрами.
Метрика Евклида используется для определения расстояния между точками пространства признаков x
1
и x
2
и удовлетворяет всем аксио- мам расстояния; она удобна для определения расстояния между двумя точками, например, между точкой наблюдаемых параметров и центром
(выборочным средним) класса. Однако она не учитывает распределение точек в классе.
Метрика Махаланобиса в отличие от метрики Евклида учитывает статистические распределения значений параметров и неприменима,
если выборочная дисперсия хотя бы одного из параметров равна нулю;
•

2.4. Рассуждения на основе прецедентов
101
В этом случае значения заключены между 0 и 1. Обычно перед использованием этой метрики данные стандартизуют. Данные после стандартизации должны быть неотрицательными;
• метрика Чекановского:
d ik
=
b + c
2a + b + c
Коэффициенты a, b, c, и d берутся из таблицы (матрицы) ассоциатив- ности, построенной для двух объектов i и k, в которой 1 указывает на наличие признака у объекта, 0 — на его отсутствие. Проще всего рассмотреть эти коэффициенты, обратившись к таблице (матрице) ас- социативности размера 2 × 2:
1 0 1 a b
0 c d ;
• метрика Жаккара:
d ik
=
a a + b + c
Как и в случае метрики Чекановского, коэффициенты a, b, c, и d берутся из таблицы ассоциативности.
• обобщенное расстояние Евклида–Махаланобиса.
Рассмотрим эту метрику, следуя [37].
Для определения расстояния от точки, координаты которой пред- ставляют собой параметры наблюдаемого объекта, до класса n сходных объектов обычно пользуются метриками Евклида и Махаланобиса.
Каждая из этих метрик имеет свои преимущества и недостатки.
Метрика Евклида, используемая для определения расстояния меж- ду точками x
1
, x
2
:
R
2
E
(x
1
, x
2
) = (x
1
− x
2
)
⊤
· (x
1
− x
2
),
удовлетворяет всем аксиомам расстояния, она удобна для определения расстояния между двумя точками, например, между точкой наблюдае- мых параметров и центром (выборочным средним) класса. Метрика не учитывает распределение точек в классе.
Метрика Махаланобиса неприменима, если выборочная дисперсия хотя бы одного из параметров равна нулю, в этом случае lim
D
i
→
0
R
2
M
(x, X) = ∞.

102
Гл. 2. Методы автоматизации рассуждений
Метрика Махаланобиса совпадает с евклидовой в случае, если класс представляет собой вектор реализаций нормированных (дис- персии D
i
= 1, i = 1, ..., n) независимых (ковариации K
ij
= 0, i, j =
= 1, ..., n, i 6= j) случайных величин. Проверка аксиом расстояния затруднена тем, что метрика используется для определения расстояния между разнородными объектами.
Метрику Евклида можно, как и метрику Махаланобиса, предста- вить в виде квадратичной формы, матрицей которой является единич- ная матрица:
R
2
E
(x
1
, x
2
) = (x
1
− x
2
)
⊤
E (x
1
− x
2
).
Метрика Махаланобиса может также использоваться и для измере- ния расстояния между двумя классами X
1
и X
2
. Для этого используют среднее взвешенное расстояний Махаланобиса от выборочных сред- них:
e
R
2
M
(X
1
, X
2
) = γR
2
M
(x
1
, X
2
) + (1 − γ)R
2
M
(x
2
, X
1
).
Такая метрика неудобна, так как если класс X
1
состоит из един- ственной точки x
1
, то e
R
2
M
(x
1
, X
2
) 6= R
2
M
(x
1
, X
2
). Рассмотрим обобщен- ную метрику Евклида–Махаланобиса [8], определяющую расстояние между двумя классами X
1
и X
2
в виде квадратичной формы
R
2
G
(X
1
, X
2
) = (x
1
− x
2
)
⊤
A
−
1
(x
1
− x
2
),
где x
1
и x
2
— средние выборочные классов, матрица A
−
1
является обратной матрицей для
A = C
1
+ C
2
+ E,
C
1
и C
2
— ковариационные матрицы для первого и второго классов соответственно, E — единичная матрица. Для любых двух классов
X
1
и X
2
, у которых x
1
= x
2
, расстояние R
2
G
(X
1
, X
2
) = 0. Если класс
X
1
представляет собой точку, то соответствующая ему ковариационная матрица состоит из нулей и мы получаем расстояние, аналогичное рас- стоянию Махаланобиса, с той разницей, что R
2
G
(x
1
, X
2
) = R
2
E
(x
1
, x
2
)
в случае, если дисперсия D
i
= 0 (i = 1, ..., n). Если оба класса пред- ставляют собой точки, то R
2
G
(x
1
, x
2
) = R
2
E
(x
1
, x
2
). Такая метрика удоб- на для решения задач распознавания образов, в которых некоторые параметры, описывающие наблюдаемые объекты, не изменяются.
2.4.2. Согласование прецедентов. Особенность задач, которые предстоит рассмотреть в ближайших параграфах, состоит в том, что для построения описаний множеств прецедентов во многих случаях требуется не только метрическая характеристика их близости, но и некоторая другая характеристика, которая позволяет сделать вывод о степени соответствия их структур. Для этой цели в настоящем

2.4. Рассуждения на основе прецедентов
103
параграфе вводится понятие согласования прецедентов [36]. Coгласо- вание можно рассматривать как количественную характеристику бли- зости структур прецедентов.
Нахождение количественной оценки степени согласования должно основываться на соответствии элементов различных прецедентов.
Это соответствие задается локальной функцией согласования.
Определение 2.4.1. Пусть E — множество элементов прецедентов
(например, множество пар АТРИБУТ_ЗНАЧЕНИЕ). Локальная функ-
ция согласования
λ
λ : E × E → R
такова, что
λ(e
1
, e
2
) = r ∈ R.
Согласование можно рассматривать как меру сравнимости элементов e
1
и e
2
. Если элементы e
1
и e
2
несравнимы, то локальная функ- ция согласования на них не определена. Множество всех элементов e
2
, с которыми сравним элемент e
1
, обозначим через Θ = {e
2
|, если
λ(e
1
, e
2
) определена)}.
Содержательно, сравнимость элементов означает, что они принадле- жат одному и тому же типу или домену и тогда λ(e
1
, e
2
) > 0 может рас- сматриваться как «напоминание» о e
2
при обнаружении e; λ(e
1
, e
2
) = 0
означает, что напоминание о e
2
отсутствует, а λ(e
1
, e
2
) > 0 указывает,
что e
1
не может рассматриваться в качестве напоминания о e
2
Используя локальную функцию согласования, можно определить глобальную функцию согласования Λ: П(E) × П(E) → R так, что
Λ(π
1,
π
2
) = r, где П(E) — множество прецедентов, определенных на элементах из E, а R — множество рациональных чисел; Λ(π
i
, π
j
) >
> Λ(π
i
, π
k
) свидетельствует о том, что прецеденты π
i и π
j более согласованы, чем прецеденты π
i и π
k
. Отрицательные значения этой функции интерпретируются как рассогласование прецедентов.
Глобальную функцию согласования Λ можно рассматривать как линейную форму локальных функций согласования λ
ij
, коэффициенты которой g ij являются весами соответствующих значений локальных функций и можно выразить через локальные следующим образом:
Λ
(π
1
, π
2
) =
n
X
i=1
m
X
j=1
g ij
· λ
ij
(Q
i
, e j
),
где Q
i
, e j
— элементы прецедентов π
1
и π
2
, соответственно (i = 1, ..., n,
j = 1, 2, ..., m).
2.4.3. Предпочтения и глобальная релевантность. Собствен- но, релевантность прецедента некоторому элементу характеризуется
частичной функцией релевантности
ρ : E × П(E) → R, так что r = ρ(q, π), где q ∈ E — элемент, π ∈ П(E) — прецедент.

104
Гл. 2. Методы автоматизации рассуждений
Глобальную функцию релевантности, характеризующую релевант- ность прецедента π
2
прецеденту π
1
будем, для простоты, считать ли- нейной формой частичных функций релевантности:
rel (π
1
, π
2
) = ϕ(ρ(e
1
, π
2
), ..., ρ(e n
, π
2
)),
где e
1
, ..., e n
— элементы π
1
Глобальную функцию релевантности нормируем так, что для всяких
π
1
и π
2
имеет место rel (π
1
, π
2
) ∈ [ 0, 1]. Введем понятие предпочтения,
которое будет служить для обнаружения таких прецедентов, которые могут оказаться подходящими для некоторого заданного прецедента.
Отношение σ
q предпочтения на множестве прецедентов π
1
σ
q
π
2
озна- чает, что π
1
предпочтительнее π
2
в смысле некоторого прецедента q.
Естественно считать, что π
1
σ
q
π
2
≡ rel (π
1
, q) > rel (π
2
, q).
Таким образом, поиск подходящего прецедента включает две фазы:
1) поиск для проблемного прецедента π
1
множества наиболее согла- сованных с ним прецедентов П
+
;
2) выбор из множества П
+
наиболее предпочтительного для π
1
прецедента π
2
2.4.4. Адаптация прецедентов. Существует большое число раз- личных методов адаптации, используемых в различных исследованиях.
Тем не менее, б´ольшую часть имеющихся подходов можно отнести к одному из трех классов: а) подстановочная адаптация; б) трансфор- мационная адаптация, в) генеративная адаптация, [38].
Подстановочная адаптация является наиболее простым видом адап- тации, предполагающим, что искомый прецедент очень близок к це- левому случаю. Тогда адаптация сводится лишь к замене некоторых параметров в решениях найденных прецедентов. Для такой замены в базе прецедентов выполняется поиск зависимостей между параметра- ми описания ситуаций и соответствующих решений. Чаще всего такой подход применяется в задачах идентификации и прогнозирования.
Трансформационная адаптация предусматривает реорганизацию элементов решений и позволяет добавлять и удалять эти элементы в соответствии с определенными условиями. Обычно системы трансформационной адаптации содержат фиксированное множество операторов адаптации и трансформационных правил.
Генеративная адаптация является наиболее сложным случаем адап- тации. Она предусматривает использование не только базы прецеден- тов, но и детальных знаний, необходимых для построения цепочки рассуждений, приводящих к частичному решению задачи. Эта цепочка рассуждений взаимодействует с контекстом новой целевой задачи, мо- дифицируется на основе применения знаний о предметной области и,
таким образом, приводит к решению целевой задачи.