Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
Пользуясь (5.28), легко убедиться в справедливости следующих равенств
Brxy /да > 0, Brxv Idc =S 0,
(5.30)
BrxyIbb =? 0, BrxyZBd 2® 0.
Легко обнаружить также, что ггу достигает своего наибольшего возможного значения rxy = 1 (идеальный поиск), когда подмножества x и y совпадают и минимально возможного i\y = -1 (идеальный инвертор), когда подмножества x и y дополняют друг друга до исходного (универсального) множества N. Во всех остальных случаях имеет место Irlv I < 1.
112 Из (5.28) легко установить, что имеют место
'л I = rVA = ~'Vv- '5-3D
Переходя в (5.28) к переменным a= a In, b=bhi, с = с / п и d = = d in и вспомнив (см. главу 3), что из этих неременных только три являются независимыми, нетрудно убедиться в принципиальной возможности выразить значение / п через произвольные три независимые неременные из (0, СО], CO2, X. X1, X2 (связь этих переменных с элементами матрицы сопряженности приведена, например, в разделе 5.3).
Из (5.28). например, нетрудно вывести формулу
^ і , a,+ Xo-uv'cHi-w)
Tn =U1, X-,, со)= , -..........—------------------(5.32)
VlX2 -со(Х, +X1, - i)|(l - X2 +со(Х, + X2 - 1)1
где знак выражения X1 + X2- 1 совпадает со знаком определителя матрицы сопряженности. В реально функционирующих промышленных АСДП имеет место Xi + X2 - 1 > 0,и поэтому в дальнейшем именно эти случаи и будут предметом нашего рассмотрения. Из (5.32) следует, что при фиксированных характеристиках X1 = а!(а + с) и X2 = d/(d + b) собственно АСДП значение /'„. зависит еще и от характеристики среды, а именно от со = [а + с)/п. Можно показать, например, что при заданных характеристиках системы X1 и X2 (Xj + X2 * 1) существует единственное решение уравнения HrxyIdсо = 0, а именно [2]:
Jx2 (1-Х,)
со = со=-F==U=— 2' (5.33)
VX2O-X2^jX1(I-X1)
при котором значение / (XbX2lCO) достигает своего экстремального значения,равного
KX1, X2, (Or) = V^T-Vd-MI-M- (5-34)
Эта величина больше нуля и равна максимуму / (XbX2lCO). если X1 + X2 > 1. Если же X1 + X2 < 1, то эта же величина меньше нуля и равна минимуму / (XbX2lCO). Иными словами, независимо от того, больше или меньше нуля выражение X1 + X2 - 1, абсолютное значение гху достигает своего максимума при со = сог. При заданных характеристиках АСДП Xi и X2 (X1 + X2 Ф 1) поисковую среду с со = со,, будем называть согласованной с данной АСДП средой. Очевидно, при работе АСДП с согласованной средой поисковый эффект от ее работы получается наибольшим (разумеется, если X1 + X2 > 1).
Особый интерес представляет зависимость значения rxv от параметров X1, X2, и С0|. Напомним, что в литературе по информатике эти параметры называются коэффициентами полноты, специфичности и точности, и ряд специалистов для оценки качества работы АСДП
113
ГЛАВА 5 пользуется именно этими параметрами [11]. Из (5.28) нетрудно вывести формулу:
n 1 (^l + ~')>/с0| (!-СО,)
/-(X1, X2, a3I)= /. . . , •• (5.35)
^/X1X2 — CO1 (A1 + X2-I)
Как и в предыдущем случае, примем, что характеристики собственно АСДП, а именно Xi и X2 (Л-j + X2 Ф 1) нам заданы, и проанализируем зависимость г (X1 ,X2, CO1) от параметра CO1. Используя (5.35), легко показать, что при этом существует единственное решение уравнения Э/ дт /ЭсО] = 0, а именно:
Wl = = h і ffl V, ^ ' (5-36)
VX1X2 +V( I-X1Kl-X2)
при котором значение г (X1, X2, CO1) достигает своего экстремального значения, равного
г(Х,, X2, (Olr) = V^-Vo-Ml-X^)- (5.34а)
Как и при рассмотрении / (XllX2lCO), эта величина больше нуля и равна максимуму г (X1, X2, CO1), если X1 + X2 > 1, и меньше нуля и равна минимуму г (X1, X2, CO1), если X1 + X2 < 1. Рассмотрим численный пример.
Пусть сопоставляются результаты трех экспериментов, при проведении которых были определены значения коэффициентов полноты (X1), специфичности (X2), и точности (CO1). Определим на их основе значения гху, CO1,. и гтах.
Таблица 5.1. Результаты экспериментов по определению характеристик работы АСДП
№ п/п Параметр Эксперимент
обозн. название I II III
1 X, коэф. полноты 0,60 0,65 0,65
2 X2 коэф. специфичности 0,80 0,85 0,85
3 (O1 коэф. точности 0,71 0,97 0,76
4 Ь коэф. корреляции 0,41 0,34 0,57
5 (O1,. значение (O1, при котором 0,71 0,76 0,76
достигается максимально
возможное значение коэф.
корреляции
6 'max максимально возможное значе- 0,41 0,57 0,57
ние коэф.корреляции
Сначала сравним результаты первого и третьего экспериментов. В обоих этих экспериментах характеристики со поисковых сред оказались согласованными с характеристиками собственно АСДП, т.е. в обоих
114 экспериментах имели место (O1 = (O1,.. Это привело к тому, что реальные значения г (X1, X2, (O1) оказались равными их максимальным возможным значениям / (XbX2t(O1), т.е. в обоих случаях имели место г (X1, X2, (0|) = г (X1, X2, (O1,.). Представляется вполне естественным, что значение коэффициента корреляции в третьем эксперименте оказалось выше значения этого коэффициента в первом эксперименте. Ведь коэффициенты полноты, специфичности и точности в третьем эксперименте оказались большими по сравнению с этими коэффициентами в первом эксперименте.
