Анализ очередности выполнения запросов в информационно-поисковых системах

 

1 ПОСТАНОВКА ЗАДАЧИ

 

1.1 Определение по Парето групповой очередности выполнения запросов в автоматизированной информационно-поисковой системе

Пусть в очереди автоматизированной информационно-поисковой системы находится N ожидающих выполнения запросов. Каждый запрос характеризуется М показателями - определенными требованиями на ресурсы (это могут быть объем занимаемой оперативной памяти, время занятия канала ввода-вывода, частота обращения к информационному фонду и т.д.). Будем считать, что чем больше ресурсы, требуемые для выполнения запроса, тем раньше его надо выполнять.

Все показатели a_ij,(i = [1..M], j =[1..N]) представлены в матрице   A = || a_ij ||

Необходимо осуществить  групповое ранжирование запросов, то есть определить, какую группу запросов следует выполнять в первую очередь, какую - во вторую и т.д.

1.2 Оценка непротиворечивости суждений эксперта при попарном сравнении запросов в шкале отношений

Проведен опрос эксперта, который должен был указать степень  важности каждого из n запросов Q₁, Q₂,..., Q_n с точки зрения очередности его выполнения - чем важнее, по мнению эксперта, запрос, тем быстрее его надо выполнять. Сравнение запросов производилось в шкале отношений.

В результате получилась квадратная матрица A = || a_ij || порядка n, где a_ij - число, показывающее, во сколько раз запрос Q_i важнее (менее важен) запроса Q_j.

Согласно правилам экспертизы матрица А - положительная обратносимметрическая (ПО - матрица), т. е. такая, что  "i,j          (i,j=[1..n]): a_ij > 0 и  a_ij = a_ij^-1                                                                                 (1)

При идеальной непротиворечивости (согласованности) суждений эксперта элементы матрицы должны удовлетворять свойству транзитивности, т. е.  "i,j,к (i,j,к=1,n): a_ij * a_jk   =  a_jk           (2)

ПО - матрица, удовлетворяющая (2), называется согласованной.

На практике, в силу особенностей процедуры попарного сравнения  объектов и субъективности суждений эксперта, матрица А, полученная от экспертов, оказывается, вообще говоря, несогласованной. Вопрос состоит в  том, насколько велика эта несогласованность. Если она незначительна, то с матрицей можно работать дальше, в частности, находить так называемый вектор приоритетов, т. е. нормализованный вектор

W = (W₁,W₂,...,W_n),   где åW_i = 1, i=[1..n]                              (3)

где W_i - «вес», приписываемый экспертом запросу Q_j по сравнению с остальными запросами. Если матрица А - существенно несогласованная, то надо искать причины несогласованности (эксперт неправильно понял задачу экспертизы, организаторы экспертизы ошиблись в подборе объектов, эксперт некомпетентен и т. д.) и запускать процедуру экспертного опроса заново.

В любом случае системный  аналитик должен уметь:

- оценивать степень согласованности  матрицы попарных сравнений;

- вычислять по этой  матрице вектор приоритетов;

В данном разделе по заданной ПО - матрице А необходимо:

Получить количественную оценку согласованности ПО - матрицы  А с  точностью d=0,001.

Найти с точностью d=0,001 вектор приоритетов W эксперта, составившего эту матрицу.

 

1.3  Оценка согласованности мнений экспертов при групповой экспертизе

Имеются результаты опроса М экспертов относительно важности N запросов с точки зрения очередности  их выполнения. Сравнение запросов производилось в порядковой (ранговой) шкале. В итоге получилась матрица

X = || X_ij ||_MXN где X_ij- ранг, присвоенный i-ым экспертом j-му запросу.

В силу субъективности мнений экспертов и по ряду других причин, ранги, приписанные одному и тому же запросу разными экспертами, вообще говоря, различны.

Если это различие очень  велико, то пытаются выяснить причины  рассогласованности. В частности, находят  группы экспертов, мнения которых хорошо коррелируют друг с другом и экспертов, суждения которых сильно отличаются от «основной массы». Следствием такого анализа является корректировка  процедуры экспертного опроса и  его повторное проведение с учетом сделанных изменений. Если же согласованность  суждений экспертов удовлетворительная, то организаторы экспертного опроса «конструируют» групповое мнение в виде количественных оценок, репрезентативно отражающих мнение всей группы экспертов, участвовавших в опросе. В данном разделе, имея матрицу результатов опроса экспертов c

X =|| X_ij ||_MXN ,  необходимо:

1. Вычислить коэффициент конкордации матрицы X и оценить его  значимость на уровне значимости a.

2. Вычислить коэффициенты ранговой корреляции Спирмена и Кендалла между всеми парами экспертов. Оценить их значимость на уровне значимости a.

3. Сделать вывод о степени согласованности всей группы, а также по каждой паре экспертов.

4. Вычислить (независимо от выводов пункта 3) по каждому запросу:

- групповой средний ранг

- медиану распределения  рангов.

2 ИСХОДНЫЕ ДАННЫЕ

 

2.1   Для первой части

М = 5;  N = 20,  где  М - количество используемых ресурсов, N - количество запросов ожидающих выполнения. 5 двадцатимерных векторов:

Si = (Si(1), Si(2), ... ,Si(j), ... ,Si(20)),   i = [1..5], компоненты которых равномерно  распределенные на отрезке [0,1] псевдослучайные величины, в каждой  из которых отброшены все знаки  после запятой, кроме первого, и результат умножен на 10. Исходные данные представлены в таблице 2.1.1.

 

Таблица 2.1.1 - Исходная матрица А

№	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	6	8	1	9	0	4	6	3	1	3	9	3	2	1	9	5	0	5	7	0
2	0	6	4	2	5	2	0	3	5	8	6	6	1	3	1	3	3	2	9	5
3	2	0	8	7	6	1	0	7	2	1	5	9	2	7	5	7	8	0	5	4
4	8	6	0	7	4	4	2	1	1	8	5	4	7	3	8	6	3	3	5	6
5	5	5	6	6	4	5	8	5	5	4	5	9	0	4	3	0	4	5	4	0

 

Рассматривая эти векторы  как строки вспомогательной матрицы 

A' = ||a'_ij||_5*20(a'_ij=S_i^(j)), элементы матрицы А находим по формуле:

a'_ij + 1 при     1 <= j <=  5

a'_ij + 2 при     6 <= j <= 10

a'_ij + 3 при    11 <= j <= 15

a'_ij + 4 при    16 <= j <= 20

В результате получаем матрицу  представленную таблицей 2.1.2 ниже.

Таблица 2.1.2 - Матрица A

№	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	7	9	2	10	1	6	8	5	3	5	12	6	5	4	12	9	4	9	11	4
2	1	7	5	3	6	4	2	5	7	10	9	9	4	6	4	7	7	6	13	9
3	3	1	9	8	7	3	2	9	4	3	8	12	5	10	8	11	12	4	9	8
4	9	7	1	8	5	6	4	3	3	10	8	7	10	6	11	10	7	7	9	10
5	6	6	7	7	5	7	10	7	7	6	8	12	3	7	6	4	8	9	8	4

 

2.2  Для второй части

Количество строк ПО-матрицы: n = 3.

Элементы ПО - матрицы  А выше главной диагонали для  данного варианта приведены в таблице 2.2.1 ниже.

 

Таблица 2.2.1 - Исходные данные

5	4	7

 

Находим ПО-матрицу, исходя из ее свойств:

 

"i,j (i,j=[1..n]): а_ij > 0 и а_ij  =  а_ji^-1  a_ii = 1  для "i

 

 

Для оценки согласованности  матрицы необходима величина случайного индекса (СИ). Для n=3 эта величина составляет 0,58.

2.3   Для третьей части

М = 4;  N = 10;  a = 0,05,  где

М – количество экспертов,

N – количество объектов,

a - уровень значимости.

Матрица X (Таблица 2.3.2) составляется на основании Таблицы 2.3.1 следующим образом: элемент X₁₁ равен номеру варианта (для данной работы это вариант №9, то есть цифра 6. Все строки заполняются круговой перестановкой цифр, начиная с первой строки, причем

X₂₁ = X₁₂ , X₃₁ = X₂₂, X₄₁ = X₃₂

 

Таблица 2.3.1 - Исходная матрица X

Эксперты	Объекты
	1	2	3	4	5	6	7	8	9	10
1	2	4	6	8	10	1	3	5	7	9
2	4	6	8	10	1	3	5	7	9	2
3	6	8	10	1	3	5	7	9	2	4
4	8	10	1	3	5	7	9	2	4	6