Статистика государственных финансов
Правила переоформления студенческих работ
Требования к оформлению студенческих работ

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

ГлавнаяИнформатикаИнформационные системы
ДисциплинаИнформационные системы
ВУЗУГТУ
Номер варианта20

Содержание

1. Постановка задачи 
1.1. Определение по Парето групповой очередности выполнения запросов в автоматизированной информационно-поисковой системе (АИПС)
1.2 Оценка непротиворечивости суждений эксперта при попарном сравнении запросов в шкале отношений
1.3 Оценка согласованности мнений экспертов при групповой экспертизе
2. Исходные данные
3. Результаты
2. Исходные данные
2.1 К разделу I
М = 5; N = 20.
Необходимо сгенерировать 5 двадцатиметровых векторов:
Si = (Si (1), Si (2), …, Si (j), …, Si (20)), i = 1,5, компоненты которых суть равномерно распределенные в [0,1] случайные числа, в каждом из которых отброшены все знаки после запятой, кроме первого, и результат умножен на 10. Рассматривая эти векторы как строки вспомогательной матрицы А’= // a’ij //5*20 (a’ij = Si (j)), элементы a’ij матрицы А находим по формуле:
aij = a’ij + 1 при 1  j  5
aij = a’ij + 2 при 6  j  10 i = 1,5
aij = a’ij + 3 при 11  j  15
aij = a’ij + 4 при 6  j  20
2.2. К разделу II
n = 3.
элементы ПО: а12 = 5, а23 = 7, а13 =6.
По свойству ПО – матрицы аii = 1 для любого i. Элементы ниже главной диагонали вычисляются по формуле (1), в результате получим:
а11 = 1 а12 = 5 а13 = 6
а21 = 0,200 а22 = 1 а23 = 7
а31 = 0,167 а32 = 0,143 а33 = 1
III. Для оценки согласованности матрицы используется величина СИ (случайного индекса)
СИ = 0.58 для n = 3.
2.3. К разделу III
М = 4; N = 10;  = 0,05.
Матрица Х:
Результаты
3.1. К разделу I
Будем считать, что объект Qi строго предпочтительней объекта Qk. Если оценка Qi хотя бы по одному критерию превосходит оценку Qk, а по всем остальным критериям не хуже оценок Qk, тогда оптимальным по Парето объектам будет тот, для которого не существует доминирующих объектов и множество таких объектов – паретооптимальным множеством.
Групповое ранжирование объектов осуществляется в несколько этапов:
1. выделяется паретооптимальное множество, которому присваивается ранг 1;
2. определяется паретооптимальное подмножество исходного множества, на котором удалены группа объектов первого ранга, и присваивается этому подмножеству ранг второй и т.д., пока не исчерпаем все исходное множество объектов.
Поскольку ранги объектов определяются не абсолютными оценками, а относительными, то для реализации метода ранжирования достаточно лишь знать для каждой пары объектов (Qi,Qk), доминирует ли один объект другого. Для этого рассматривают булеву матрицу А размерностью NxN, элемент Aij которой определяется:
Аij = 1, если Оi доминирует Оj
0, в противном случае
Оптимальным объектом считается тот, в котором не существует доминирующих объектов, т.е. столбец этого объекта в матрице не будет содержать единиц. Единицы в i-ой строке определяют объекты Qj, которые объект Qi доминируют, поэтому, если в некотором каком-нибудь столбце стоят одни 0, то не существует объекта, который бы доминировал этот объект Qk и следовательно, множество всех объектов с нулевыми столбцами в матрице А и будет паретооптимальным множеством.
Результаты:
Рис. 1 Сгенерированные исходные данные и булева матрица
Рис. 2 В первый ранг заносятся 11, 12, 17, 19 и 20 запросы
Рис. 3 Во второй ранг заносятся 2, 4, 5, 6, 9, 10, 13 и 15 запросы
Рис. 4 В третий ранг заносятся 3, 7, 8, 14, 16 и 18 запросы
Рис. 5 В четвертый ранг заносится последний оставшийся 1 запрос
Код программы находится в приложении 1.
3.2. К разделу II
Оценка непротиворечивости суждений эксперта при попарном сравнении запросов в шкале отношений позволяет:
1. вычислить max и W с заданной точностью 
2. вычислить отношение согласованности ОС
Итеративная процедура для приближенного вычисления max и W основана на соотношениях:
max=lim[tr(Ak)]1/k
k
где: max - наибольшее собственное значение матрицы А,
Ak - k-я степень А
tr(Ak) - след матрицы Ak , где следом матрицы А называется сумма ее диагональных эле-ментов
Ak * e
lim  = CW ;
k // Ak //
// Ak // = eTAke,
Где e = (l,l,...,1)T, T - знак транспонирования
W - Собственный вектор матрицы А, соответствующий ее главному собственному значению =max
С - постоянная.
Краткий вычислительный способ получения главного собственного вектора таков:
возводим матрицу А в степень, каждая из которых представляет собой квадрат предыдущей, при этом нахождение главного собственного вектора с заданно точностью продолжается до тех пор, пока разность между последним и предпоследним найденными значениями строчной величины не станет меньше данной величины (точности величины), т.е. =0,001.
Отношение согласованности ОС вычисляется по формуле:
ОС = ИС/СИ,
где: ОС – отношение согласованности;
ИС – индекс согласованности:
ИС = (max - n)/(n-1),
СИ – случайный индекс (при n=3 СИ=0.58).
Если ОС<=0.1, то согласованность считается приемлемой, иначе согласованность плохая.
Тогда начинают вычислять причины несогласованности.
В результате работы за К=5 итераций получили:
1. W = (0.688, 0.248, 0.064)
2. max = 3.356
3. ОС = 0.307 (т.к. ОС = 0.307 > 0.1, то согласованность матрицы неудовлетворительная)
Рис. 6 Программная форма:
Код программы находится в приложении 2.
3.3. К разделу III
1. Конкордация.
Конкордация суждений экспертов по Кенделлу оценивается с помощью коэффициента конкордации W:
(1), где ,
M - количество экспертов
N - количество объектов
Xij - ранг, который приписал i-ый эксперт j-му объекту.
Используя распределение 2 с =N-1 степенями свободы, можно узнать значимость коэффициента конкордации на уровне значимости . При этом, если N>=10, то W*M(N-1)2, затем 2 сравнивают с 2крит.. Если 2<2крит. – согласованность мнений неудовлетворительная, в противном случае наоборот.
2. Ранговая корреляция.
Ранговая корреляция Спирмена определяется по формуле:
где i - это оценки одного эксперта, а rxi - это оценки того же запроса другим экспертом.
Значимость Rs оценивается, через Tкритическое= tкритическое() *
tкритическое - критическая точка односторонней критической области распределения Стьюдента с числом степеней свободы  и точностью .
Если Rs <Tкрит., то согласие считается неудовлетворительным, в противном случае наоборот.
• Ранговый коэффициент корреляции Кендалла Rk определяется по формуле:
(3)
где U- число инверсий в последовательности рангов одного эксперта, при условии, что ранги другого расположены в строго возрастающем порядке.
Проверка значимости Rк: если n>10, то Zкритическое= zкритическое* (4)
zкритическое - односторонняя критическая точка стандартного нормального распределения для уровня значимости .
Если Rк < Zкрит., то согласие считается неудовлетворительным, в противном случае наоборот.
В результате работы были получены следующие значения:
Рис. 7 Программная форма:
Коэффициент конкордации:
1. W=0. 2. 2=2.7273
т.к. 2набл. < 2крит., то согласие неудовлетворительное.
• Ранговые коэффициенты корреляции Спирмена: Rs < Ткр (согласие неудовлетв.)
• Ранговые коэффициенты корреляции Кендалла:
Из формулы (4), вычисляем Zкрит, которое равно Zкрит=0.7057
Rk < Zкр (согласие неудовлетворительное).
Код программы приведен в приложении 3.
Вывод о степени согласованности всей группы на основе результатов расчета:
Вычислив коэффициент конкордации, выяснилось, что для данных наших оценок 10-ти объектов 4 экспертами согласие неудовлетворительное, и что среди экспертов нет групп, имеющих сходные мнения.