автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Модель оценивания параметров поисковых структур в случайной среде

На правах рукописи

005010472

Соловьев Михаил Михайлович

МОДЕЛЬ ОЦЕНИВАНИЯ ПАРАМЕТРОВ ПОИСКОВЫХ СТРУКТУР В СЛУЧАЙНОЙ СРЕДЕ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Ульяновск

2012

005010472

Работа выполнена на кафедре прикладной математики в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Ульяновский государственный университет»

Научный руководитель: доктор физико-математических наук, профессор

Бутов Александр Александрович

Официальные оппоненты: доктор технических наук, профессор

Кумунжиев Константин Васильевич

кандидат технических наук Тронин Вадим Георгиевич

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Ульяновский государственный технический университет»

Защита диссертации состоится «29» февраля 2012 года в Ю00 часов на заседании диссертационного совета Д 212.278.02 при Ульяновском государственном университете по адресу: г. Ульяновск, ул. Набережная р. Свияги, 106, корп. 1, ауд. 703.

С диссертацией можно ознакомиться в научной библиотеке Ульяновского государственного университета, с авторефератом - на сайте ВУЗа http://www.uni.ulsu.ru и на сайте Высшей аттестационной комиссии при Минобрнауки России.

Отзывы на автореферат просим присылать по адресу: 432017, г. Ульяновск, ул. Л. Толстого, д. 42, УлГУ, Отдел послевузовского профессионального образования.

Автореферат разослан «21» 2012 года.

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования. В настоящее время сеть Интернет является важным звеном в получении и обмене информацией в современном обществе. Благодаря широкому распространению компьютерных технологий в электронной форме находится информация большинства отраслей человеческой деятельности, таких как наука, производство, литература и др. Сеть Интернет предоставляет удобный, быстрый и относительно дешевый доступ практически к любому виду данных. В связи с этим возникает потребность в программных средствах, эффективно решающих проблемы связанные с выбором необходимой пользователю информации. Ее поиском в сети занимаются специальные веб-службы - компании (например, Яндекс и Google), имеющие свои сервера, на которых работает сложная поисковая система. Зачастую эти службы являются своего рода посредниками в передаче информации от источника до потребителя. Но по каким критериям, алгоритмам происходит выдача результатов (Интернет-ресурсов) на запрос пользователя известно лишь разработчикам данной системы.

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

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

1 Гулин А. Алгоритм текстового ранжирования Яндекса / А. Гулин, М. Маслов,

И. Сегалович // Труды РОМИП, 2006.; Бродский А. Алгоритмы контекстно-зависимого аннотирования Яндекса / А. Бродский, Р. Ковалев, М. Лебедев, Д. Лещинер, П. Сушин // Труды РОМИП, 2008. С. 160-169. .

2 Статистика сайта Live Internet [Электронный ресурс]. - Режим доступа: httn://www.livcinternet.ni/stat: Google Analytics [Электронный ресурс]. - Режим доступа: http://www.google.com/intl/ru/analytics.

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

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

В рамках данной работы разрабатывается и описывается система сбора статистических данных результатов отклика поисковой системы на запросы пользователя. Описывается система получения значений параметров объектов для их дальнейшего оценивания и анализа3 4. Далее рассматривается задача нахождения оптимального объекта поиска и оптимального количества единовременно выдаваемых результатов при ранжировании. Строится модель оценки вероятностей исследуемых угроз на основе анализа данных (новостей), полученных из глобальной сети Интернет. Для этого разработаны и исследуются математические, стохастические и имитационные компьютерные модели процесса поиска в сети. Данное моделирование позволяет определять статистические закономерности в алгоритмах ранжирования поисковых систем и оптимальные значения параметров для эффективного поиска.

В качестве статистического материала в прикладной части диссертационной работы рассматриваются экспериментальные данные, полученные при помощи системы сбора информации, разработанной автором, а также реальные данные нагрузки на сервер, собранные за 16 дней его функционирования в рабочем режиме. Для оценивания вероятности возникновения чрезвычайных (критических) ситуаций собираются и анализируются данные из новостных информационных ресурсов в сети Интернет.

1 Орлов А. И. Прикладная статистика. Ч. 2. Основные проблемы прикладной статистики, §2.2. / А. И. Орлов. - М.: Изд-во «Экзамен», 2004.

Лемешко Б. Ю. Об оценивании параметров распределений по интервальным наблюдениям / Б. Ю. Лемешко, С. Н. Постовалов // Новосибирский государственный технический университет. Вычислительные технологии. - 1998. - Т. 3, № 2.

Целью и задачей диссертационного исследования является оценивание параметров поисковых структур и применение полученных результатов в прикладных областях. Разработка математических моделей и создание на их основе комплекса программ для решения следующих задач:

1. Мониторинг позиций сайтов по ключевым запросам различных поисковых систем;

2. Сокращение времени поиска путем выдачи оптимального количества результатов;

3. Нахождение момента остановки поиска, результат которого удовлетворяет ожиданиям пользователя;

4. Оценивание вероятности возникновения исследуемых угроз, информация о которых присутствует в сети Интернет.

Для решения этих задач применялись разработанные автором методы с использованием математического моделирования и современных систем компьютерной разработки.

Методы исследования. В диссертационной работе используются методы математического моделирования дискретных систем, теории случайных процессов, численные методы и методы объектноориентированного программирования. Задачи 2, 3 и 4 описываются и решаются с применением вероятностных методов. Для проведения большого количества, экспериментов и имитационного моделирования используются методы генерации случайных данных, .получаемых с использованием нормального и экспоненциального распределения.

Для создания комплекса программ применялись методы объектноориентированного программирования на языках высокого уровня РНР, MySQL и Delphi. В программной реализации моделей используется аппарат численного математического моделирования и библиотеки подпрограмм компьютерной математики.

Численные методы применяются при построении моделей стохастических систем с динамическим выбором шага дискретизации и модифицированный метод нахождения экстремума функций. На этапе проверки адекватности моделей вычисляются средние и среднеквадратичные отклонения теоретических данных от

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

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

Основные положения, выносимые на защиту:

1. Модель формирования результатов поисковой структурой при запросах пользователей па основе заданных параметров объектов.

2. Метод нахождения момента остановки процесса сетевого поиска.

3. Математическая модель оптимизации количества результатов поиска на основе оригинального использования численного метода.

4. Комплекс программ для, имитационного моделирования и численного анализа процессов поиска.

Достоверность результатов обеспечивается использованием аналитических и численных методов расчёта, методов математического моделирования и применением современных методик анализа экспериментальных данных посредством компьютерного моделирования. Для получения достоверных результатов на этапе имитационного моделирования при подборе значений параметров использовались различные нормировочные коэффициенты. Результаты имитационного моделирования привели к значениям параметров близким реальным объектам.

Теоретическая и практическая значимость диссертационного исследования заключается в том, что разработанный комплекс программ

может использоваться как целиком, так и отдельно по четырем компонентам (перечисленным выше задачам). Он позволяет не только анализировать полученные данные, но и прогнозировать, моделировать различные ситуации, которые помогают пользователю принимать управленческие решения. Применение решений диссертационного исследования при поиске информации позволяет быстрее выдавать пользователю желаемый результат и, как следствие, сократить нагрузку на сервер; находить наиболее вероятный момент сбоя в его работе. Полученные теоретические результаты включают в себя метод поиска ожидаемого пользователем результата, позволяющего рассчитывать значения параметров систем такого типа. Часть комплекса была внедрена и применяется на практике в ООО «Креатер» г. Ульяновска.

Апробация работы. Материалы диссертации докладывались на X Всероссийском симпозиуме по прикладной и промышленной математике (Сочи - Дагомыс, 1-8 октября 2009 г.), XI Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 1-8 мая 2010 г.), VI Всероссийской открытой научно-практической конференции (Сочи, 22-27 мая 2010 г.), X Международной научно-практической конференции (Новочеркасск, 5 апреля 2010 г.), в Международной научной школе для молодежи (Москва, октябрь 2010 г.).

Личный вклад автора. Постановка задач осуществлялась научным руководителем профессором Бутовым А.А. Автором диссертационного исследования самостоятельно проведён анализ современного состояния компьютерного моделирования; разработаны программные методы для достижения поставленных задач; разработана структура базы данных, классов и объектов, на основе которых создан комплекс программ; выполнен анализ полученных результатов и сформулированы выводы.

Публикации. По теме диссертации опубликовано 10 работ, в том числе 4 работы в рецензируемых научных журналах, рекомендованных ВАК, их список помещён в конце автореферата.

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы из 97 наименований

7

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

СОДЕРЖАНИЕ РАБОТЫ

Во введении даётся общая характеристика современного состояния проблемы в данной области исследования и диссертационной работы в целом. Обоснована актуальность темы диссертации, сформулированы цели и задачи в общем виде.

В первой главе рассматриваются популярные на данный момент поисковые структуры. Они сравниваются между собой по различным критериям, а также перечисляются их достоинства и недостатки. Приводится пример обобщенного метода ранжирования результатов выдачи поисковой машиной или поисковиком (на примере «Яндекс»),

В параграфе 1.1 рассказывается о развитии поисковых систем со временем. В параграфе 1.2 приводятся наиболее известные из них в сети Интернет. Производится сравнение и сопоставление таких систем.

В параграфе 1.3 рассматривается обобщенный алгоритм ранжирования результатов на примере поисковой машины Google.

Во второй главе описываются задачи, решаемые в данной диссертационной работе. Производится их математическое и имитационное моделирование. ,

Предполагается, что гипотетически поисковик при сортировке результатов опирается на некие характеристики объекта под конкретный запрос пользователя. Исходя из этого, возникает задача определения веса той или иной характеристики объекта для поисковика. Данная задача ставится в параграфе 2.1.

В параграфе 2.2 строится теоретическая модель выдачи результатов по обобщенной формуле (I):

/' =t(KrP/(Q), (1)

i=i

где ?б[1..тя], т,п< 00. Причем Р'(^)~{Р\,Р2^--гРп} - множество

значений характеристик искомых объектов, используемых поисковой структурой для ранжирования результатов выдачи. Эти значения общедоступны, имеются у каждого объекта и могут быть различны для любого элемента из множества поисковых запросов ¿={/ь /2, ..., /.,}• К={к.1, к2, .... к„} - множество коэффициентов (так называемого веса) для параметров Р, которые необходимо оценить. Зная результаты 1( (Л -множество значимостей объекта поиска со временем <=[/,.т}), иными словами, зная позицию объекта при выдаче результатов, можно построить линейное приближение и определить коэффициенты К.

В параграфе 2.3 описывается задача оптимизации процесса поиска, решением которой, должен задаваться разработчик поисковой структуры на примере решения задачи нахождение оптимального количества выдаваемых поисковиком результатов на запрос пользователя. Эта задача рассматривается в диссертационной работе. Критерием оптимальности в этом случае является наименьшее количество действий, затраченных для поиска необходимой информации.

В параграфе 2.4 строится математическая модель процесса поиска, описываемая формулой (2):

Ф (А) = ЕЫ{(а>)+ ЕР^И^со^со)—(2)

л> о

где ^(,-;й,) - позиция /-го объекта на г-ый запрос пользователя, причем г = 1,2,...,/V, здесь N - функция, характеризующая номер последнего запроса в этом конкретном со -эксперименте, при котором пользователь удовлетворен результатом поиска. В момент г = Ы процесс останавливается (т. е. поиск считается завершенным, если число просмотренных пользователем результатов меньше или равно количеству выданных объектов на первой странице), причем в зависимости от ситуации N может быть различно. Таким образом, N можно формально представить формулой (3):

М(со)--=тт(г:г>1,р{(Г;а)< А), (3)

где А - нижняя граница результата, при котором пользователь останавливает эксперимент.

Следует отметить, что при уменьшении единовременно выдаваемых результатов увеличивается количество обращений пользователей к

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

В параграфе 2.5 приведено имитационное стохастическое моделирование данной модели и представлены его результаты в виде графика. Описываются блок-схемы соответствующих алгоритмов данного программного модуля. В результате чего установлено, что решение функционала (2) достигается в 30% от общего количества результатов или от максимальной границы А.

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

В параграфе 2.7 приводится математическое и имитационное описание задачи из параграфа 2.6. Обозначим М- максимальный уровень ожидания пользователя — идеальный результат поиска. Устанавливается реальная граница ожидания Ме = М - е > 0, где е = {1,2,3,..., М -1}. Пусть - множество значений параметров г-го последовательного объекта поиска, экспоненциально распределенных по формуле (4):

/г(Х-) = {1-е УХ'’ Х1>{)’У>{) (4)

[0, Х,.<0

Пусть множество моментов остановок

— 1пЛ:0 <(<Т \71{ = /), являющихся моментами, в которые поисковая система получает объект для анализа, где Т — максимальное время поиска результата (здесь время носит дискретный характер). Таким образом, задача сводится к нахождению т - оптимального момента остановки поиска, описываемого уравнением (5):

г = т {(1:У%>МЕ), (5)

I

где У, =У0 + ¡(Х^ - Г4_)Лг,. Т.е. У, имеет кусочно-постоянные о

траектории, значения которых равны Хк только в моменты скачка .

Иными словами, У/ содержит наблюдения за весь период времени [0; /] в моменты скачков я,, учитывая предыдущее значение процесса. Где к, -это пуассоновский процесс (в разложении Дуба-Мейера). По этому закону задаются объекты для анализа в поисковой системе.

Поэтому задача оптимизации сводится к минимизации среднего времени ожидания наилучшего результата и одновременно к уменьшению границы допустимых отклонений е. Это требование формализуется математически в формуле (6):

Ф(г,£) = а'£: + £-»шт. (6)

с>0 4 '

Результаты имитационного компьютерного моделирования процесса, описываемого в данном параграфе формулой (6) представлены на графиках. Далее подробно рассматривается и описывается блок-схема алгоритма решаемой задачи.

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

В параграфе 3.1 и 3.2 описывается рассматриваемая задача оценивания вероятности возникновения чрезвычайных ситуаций. Приводятся примеры, где текущий вопрос может быть актуален. Предполагается, что к возникновению определенной угрозы на у'-ом

объекте (обозначенной символом Априводят какие-либо факторы угроз

(ФУ) В = {В1}, г е[1,М], где N - количество различных ФУ.

В параграфе 3.3 проводится формализация задачи. Пусть мера

Р(А ) представляет собой вероятность события ЛЛ, оцениваемого по ФУ

с учетом заранее определенных условных вероятностей Р(А'<: | В‘) и

частот появления факторов В1. Оценивание меры В1 производится по входным данным <р1 (векторный набор статистических показателей).

Для вычисления вероятности события А8 используется формула (7):

ру(/,^)=1-Па-^(5')), (7)

/=1

а также допускается, что у каждого оцениваемого объекта, есть защитные меры от факторов В1, которые характеризуется коэффициентом значимости «-го защитного фактора аI.

Формула (8) позволяет определить защитный коэффициент от факторов В1 для /-го объекта:

т

’ (8)

ы

п~ 1

где — факт выполнения «-го защитного фактора у-го объекта, причем

О < К{. < 1. Также принимается во внимание, что каждый источник

информации (ИИ) анализируется в соответствии со временем актуальности

Тл по фактору В1'. ТА ={/,}, г е[1,Лг]. При этом для N источников

информации и для каждого фактора определяется количество

встречаемости каждого из слов в течение времени актуальности ТА в виде

векторов: <р\ - {<р\, (р'у,<р‘ ), где п, - число найденных слов в ИИ для В1. 11

По полученным данным (р1( и коэффициентам значимостей р\ I-ой компоненты /-го вектора входных данных позволяют построить оценку Ко (9):

ш-й)

КЬ=-,^- ■ (9)

}Ш)2 Ш)2

Ь=1 /=1

Далее по формуле (10):

Р;(В1) = у ■ р]{В1) + (1 - у) • Р}{В1), (10)

строятся оценки мер ФУ Pj{B‘), где

р}(в‘)=кЬ-(1~Ц), (п)

представляет собой меру опасности по /-му фактору при условии его полной компенсации защитными мерами объектов. Формула (12)

Pj{Bi) = l-(l-KiD)-K', (12)

представляет собой меру опасности по /-му фактору при условии доминирования любой из опасностей. Таким образом, оценка меры по /-му

фактору Pj(В1) может быть записана в виде (13):

Pj{Bi) = r-KlD-{l-KJs) + (l-r)-(l~(\-KiD).KJs), (13)

где параметр у е [0,1] - баланс соотношения защищенности объекта от ФУ

5'.

Оценки вероятностей Pj(Bl) и Pj(As) приводят нас к итоговой формуле (14) для расчета степени угрозы возникновения события AS:

Р,(^) = 1-П0-^(б')). (14)

i=l

В параграфе 3.4 описывается практическое применение разработанной модели в составе автоматизированной системы расчета угроз авиационной безопасности.

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

В параграфе 4.1 представлено описание комплекса программ. Каждая программа описывается отдельно и может применяться независимо от всего комплекса. Все модули написаны на языках высокого уровня РНР, MySQL и Delphi. Например, описывается созданная система сбора статистики значений параметров объектов для конкретных ключевых запросов и позиций выдачи поисковика со временем для решения поставленной задачи. Данная система не только собирает статистику, но и позволяет отслеживать все изменения в статистиках при помощи графиков (рис. 1) и таблиц. Любой человек, знающий логин и

пароль к системе, может выступать в роли администратора: создавать, редактировать и удалять объекты и поисковые слова. Это позволяет делать удобный и понятный интерфейс системы управления. В данном параграфе приводится таблица сравнения разработанной программы и существующих аналогов.

Время (дни)

х* Indexed ТИЦ * Внутренних ссылок Р Внешних ссылок 'Р' Вес стренцы

Рис. 1. Графики изменения значений параметров со временем

В параграфе 4.2 проверяется адекватность разработанных моделей и алгоритмов. В параграфе 4.3 для задачи оптимизации процесса поиска из параграфа 2.3 рассчитывается эффективность относительно удобности поиска пользователем и уменьшение нагрузки на поисковик. Для этого минимизируется граница А, не выходя за установленные 30% (указанные в параграфе 2.5). Таким образом, чтобы уменьшить нагрузку на саму поисковую структуру и сделать выдачу более восприимчивой для пользователя, необходимо понизить количество результатов выдачи. Но при этом работа пользователя (значение Ф{А)) не должно слишком сильно увеличиваться, граница этого роста обозначается через число В. Исходя из всего перечисленного, введем эффективное значение количества единовременно выдаваемых результатов (G) поиска, выражаемое формулой (15):

G(B) = max{Ai :0 <Ф(А,-)~ Ф(А,+1) < В}. (15)

В> 0

Очевидно, что при минимальных значениях В число G(B) будет весьма велико и не может удовлетворять требованиям по уменьшению

14

числа выдаваемых результатов, наоборот, при выборе В очень большим результат устремляется к нулю.

Ряд проведенных экспериментов показывает, что эффективное количество результатов выдачи (по критерию удобства пользователя -нагрузка поисковика) должна составлять 2-3% от общего количества результатов или от максимальной границы А.

В параграфе 4.5 рассказывается о практическом применении данной модели на реальном примере работы веб-сервера. Проанализированы данные его нагрузки на разработанном алгоритме. Происходит сопоставление теоретических и практических данных, высчитывается их среднее и среднеквадратичное отклонение. В результате чего подобраны параметры для теоретической модели, имеющие наибольшую близость с реальным графиком (рис. 2).

Грвница допустимых отклонений

Рис. 2, Сравнение эмпирического и теоретического графика моделирования.

В выводах и заключении кратко перечислены основные новые достижения и результаты диссертационной работы.

В приложении приведены листинги отдельных фрагментов кода комплекса программ и алгоритмов, применявшихся для построения математических моделей, а также структура базы данных, дополнительные изображения графиков из программного комплекса, не вошедшие в основную часть диссертации, и таблицы с результатами выполнения программ.

Основные результаты, полученные в диссертационной работе:

1. Построены математические модели, способные упростить поиск пользователю и сократить нагрузку на поисковую систему;

2. Разработана математическая и компьютерная модель оценивания возникновения угроз на основе собранных и проанализированных информационных данных из глобальной сети Интернет;

3. Создан комплекс программ для решения задач, связанных с моделированием поиска в случайной среде, а также мониторинга данных для поисковой оптимизации сайта;

4. Разработаны программы, применение которых возможно, как в задачах, имеющих аналитическое решение, так и на практике с использованием реальных объектов.

Результаты использования комплекса программ на практике:

1. При помощи системы сбора параметров сотрудники отдела компании стали ежедневно и более чем 6,5 раз быстрее получать необходимую информацию по интересующим сайтам и ключевым словам;

2. Разработанный модуль ежемесячной генерации отчетов о результатах проделанной работы по продвижению для выбранного сайта позволил сократить время формирования таких отчетов более чем в 4,2 раза;

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

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

Список публикаций по теме диссертации.

Публикации в изданиях, входящих в перечень ВАК

1. Соловьев, М. М. Система анализа новостных Интернет-ресурсов для вычисления угроз авиационной безопасности / М. М. Соловьев, К. О. Раводин, А. А. Бутов, М. А. Волков // Журнал «Естественные и технические науки». Изд. «Спутник+». - М., 2011. - С. 278-282.

2. Соловьев, М. М. Система сбора данных в случайной среде для оценивания параметров поисковых структур / М. М. Соловьев, И. А. Санников // Обозрение прикладной и промышленной математики. Т. 16, вып.

5. - М., 2009. - С. 245-246.

3. Соловьев, М. М. Задача эффективного поиска в сети / М. М. Соловьев // Обозрение прикладной и промышленной математики. Т. 17, вып.

5.-М., 2010.-С. 766-776.

4. Соловьев, М. М. Модель процесса поиска в сети / М. М. Соловьев,

А. А. Корепин // Обозрение прикладной и промышленной математики. Т. 17, Вып. 3.-М., 2010. -С. 459-460. -

Публикации в прочих изданиях

5. Соловьев, М. М. Задача выбора параметра для эффективного

поиска 1 М. М. Соловьев // Актуальные задачи математического моделирования и информационных технологий: материалы VI

Всероссийской открытой научно-практической конф. - Сочи, 2010. -С. 150-151.

6. Соловьев, М. М. Модель эффективного поиска в сети /

М. М. Соловьев // Моделирование. Теория, методы и средства: материалы X Международной научно-практической конф. - Новочеркасск, 2010. -С. 133-134. .

7. Соловьев, М. М. Система сбора данных в случайной среде для оценивания параметров поисковых структур / М. М. Соловьев // Ученые записки Ульяновского государственного университета. Серия Математика и информационные технологии. Вып. 1(2) / под ред. проф. А. А. Смагина. -Ульяновск: УлГУ, 2009. - С. 230-232.

8. Соловьев, М. М. Описание системы в терминах классической СМО с бесконечным числом приборов / Т. В. Бажанова, К. О. Раводин, М. М. Соловьев // Ученые записки Ульяновского государственного университета. Серия Математика и информационные технологии. Вып. 1(2) / под ред. проф. А. А. Смагина. - Ульяновск: УлГУ, 2009. -С. 243-245.

9. Соловьев, М. М. Модель оценивания параметров поисковых структур / М. М. Соловьев // Ученые записки Ульяновского государственного университета. Серия Математика и информационные технологии. Вып. 1(2) / под ред. проф. А. А. Смагина. - Ульяновск: УлГУ, 2009. - С. 249-252.

10. Соловьев М. М. Программа получения и обработки данных объекта в случайной среде / М. М. Соловьев // Математические основы эффективных вычислений и информатики. Сб. научных трудов Международной научной школы для молодежи. - М., 2010. - С. 39-42.

Подписано в печать 24.01.2012.

Формат 60x84/16. Уел. печ. л. 1,0.

Бумага книжно-журнальная.

Тираж 100 экз. Заказ № 9

Отпечатано с оригинал-макета в Издательском центре Ульяновского государственного университета 432017, г. Ульяновск, ул. J1. Толстого, 42

УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

61 12-5/1817

На правах рукописи

Соловьев Михаил Михайлович

МОДЕЛЬ ОЦЕНИВАНИЯ ПАРАМЕТРОВ ПОИСКОВЫХ СТРУКТУР В СЛУЧАЙНОЙ СРЕДЕ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель -

доктор физико-математических наук,

профессор Бутов А. А.

Ульяновск 2012

ОГЛАВЛЕНИЕ

Введение ..................................................................................................................4

Глава 1. Обзор и анализ поисковых структур в случайной среде ...................19

§ 1.1. Исторические сведения ....................................................................19

§ 1.2. Обзор современных поисковых структур в сети Интернет

и их алгоритмов...........................................................................................21

§ 1.3. Анализ алгоритмов формирования результатов............................25

Выводы к главе 1..........................................................................................27

Глава 2. Задачи и модели процессов поиска процессов поиска ......................28

§ 2.1. Постановка задачи нахождения весовых характеристик

поисковой структуры..................................................................................32

§ 2.2. Модель оценивания параметров объектов в сети..........................34

§ 2.3. Задача оптимизации процесса поиска ............................................35

§ 2.4. Моделирование эффективного процесса поиска...........................39

§ 2.5. Имитационное стохастическое моделирование ............................40

§ 2.6. Задача нахождения момента остановки поиска.............................44

§ 2.7. Математическое и имитационное моделирование задачи ...........45

Выводы к главе 2..........................................................................................52

Глава 3. Модель оценивания вероятности возникновения угроз.....................54

§ 3.1. Описание проблемы .........................................................................54

§ 3.2. Постановка задачи ............................................................................55

§ 3.3. Формализация задачи........................................................................55

§ 3.4. Практическое применение описанной модели...............................60

Выводы к главе 3..........................................................................................62

Глава 4. Описание комплекса программ и его практическое использование,

проверка адекватности результатов.....................................................................63

§ 4.1. Описание комплекса программ........................................................63

§ 4.2. Проверка адекватности ....................................................................76

§ 4.3. Результаты внедрения модели оценивания параметров

поисковых структур....................................................................................79

§ 4.4. Эффективность смоделированного процесса поиска....................80

§ 4.5. Практическое применение моделей................................................84

Выводы и заключение...........................................................................................88

Библиографический список..................................................................................90

Приложения.........................................................................................................100

ВВЕДЕНИЕ

В настоящее время Интернет является важным фактором жизнедеятельности современного информационного общества. Благодаря широкому распространению компьютерных технологий в электронной форме представлена информация практически всех отраслей человеческой деятельности, таких как наука, производство, литература и т.д. В России насчитывается 41 млн пользователей 1 глобальной сети. Интернет предоставляет удобный, быстрый и относительно дешевый доступ практически к любому виду информации. В связи с этим возникает потребность в программных средствах, эффективно решающих проблемы выбора необходимой пользователю информации. Основными инструментами, решающими эту задачу, являются так называемые поисковики - Интернет-ресурсы, примерами которых могут служить получившие известность «Яндекс», «Google», «Рамблер» и др. Они могут быть универсальными и осуществлять поиск по обширным критериям, различным тематикам и направлениям или быть определенного профиля (на конкретном ресурсе, в заданной области и т.д.). Объектами поиска зачастую являются сайты. Каждый объект такого поиска характеризуется набором параметров, имеющих конкретные значения для данного ресурса и поисковика. Следует отметить, что эти значения не являются постоянными, а претерпевают изменения во времени в зависимости от содержания объекта (как правило, переменного), изменений внутренних связей объекта (ссылочной составляющей), внешних связей с другими объектами, изменений в их назначении самой поисковой системой и др. Эти значения учитываются поисковыми системами при формировании результатов, вычисляемых в алгоритме ранжирования поисковой структуры [11, 22]. Таким образом, ранжирование результатов определяется изменением значений данных параметров. Это и вызывает набольший интерес как у владельцев сайтов, так

1 По данным компании comScore на сентябрь 2010 года http://www.slideshare.net/Osnat_z/ comscore- online-measurement-russia-riw-november-2010.

4

и у разработчиков поисковых систем. Существует множество компаний [87, 93], продвигающих сайты в Интернете, которые заинтересованы в понимании процессов, формирующих результаты выдачи в популярных поисковиках.

Для понимания работы алгоритма ранжирования требуется большое количество данных, полученных как от поисковых систем, так и от самих объектов. В настоящее время существуют системы [75, 90], способные отслеживать изменения результатов выдачи и значений характеристик сайтов, а также собирать и анализировать их статистические данные. Но эти системы не могут отслеживать информацию по «чужим», сторонним сайтам, в результате чего исследование алгоритмов ранжирования поисковых структур является трудоемкой и нетривиальной задачей. Интерес к изучению данной проблемы нашел свое отражение в многочисленных программных продуктах в сети Интернет, таких как GoogleAnalytics и др. Таким образом, исследование в данной области является актуальным.

Разработанная в диссертационной работе система может отслеживать изменения параметров любого сайта и результаты выдачи поисковика (на примере «Яндекс»). В отличие от существующих систем, она может работать как отдельный сайт и легко переноситься на другую платформу посредством простой установки. Помимо этого, она является свободно распространяемым продуктом и не требует каких-либо материальных затрат. В любой момент пользователь системы может легко получить доступ к собранным данным.

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

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

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

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

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

Целью данной работы является исследование проблем, связанных с эффективным поиском информации, их решение, описание проходящих при

этом процессов и построение их математических, компьютерных и имитационных моделей.

Задачей диссертационного исследования является разработка математических моделей и создание на их основе комплекса программ для решения нескольких типов задач:

1. Мониторинг позиций сайтов по ключевым запросам различных поисковых систем.

2. Сокращение времени поиска путем выдачи оптимального количества результатов.

3. Нахождение момента остановки поиска, результат которого удовлетворяет ожиданиям пользователя.

4. Оценивание вероятности возникновения исследуемых угроз, информация о которых присутствует в сети Интернет.

Для решения этих задач применялись разработанные автором методы с

использованием математического моделирования и современных систем разработки.

Методы исследования. В диссертационной работе используются методы математического моделирования дискретных систем. Задачи 2, 3 и 4 описываются и решаются с применением вероятностных методов. Для проведения большого количества экспериментов и имитационного моделирования используются методы генерации случайных данных, получаемых с использованием нормального и экспоненциального распределения.

При создании комплекса программ применяются методы объектно-ориентированного программирования на языках высокого уровня PHP, MySQL и Delphi. В программной реализации моделей используется аппарат численного математического моделирования и библиотеки подпрограмм компьютерной математики.

Апробация созданных программ проводится путём сравнения результатов их работы со значениями, полученными от реальных объектов и их функционирования. Помимо этого, результаты диссертационной работы докладывались и обсуждались на кафедре прикладной математики и информатики УлГУ, а также на следующих конференциях:

1. X Всероссийский симпозиум по прикладной и промышленной математике, ОППМ, г. Сочи - Дагомыс, 1-8 октября 2009 г.

2. XI Всероссийский симпозиум по прикладной и промышленной математике «Инновационная экономика: проектные решения и управление рисками», ОППМ, г. Кисловодск, 1-8 мая 2010 г.

3. VI Всероссийская открытая научно-практическая конференция «Актуальные задачи математического моделирования и информационных технологий», г. Сочи, 22-27 мая 2010 г.

4. X Международная научно-практическая конференция «Теория, методы и средства», г. Новочеркасск, 5 апреля 2010 г.

5. Международная научная школа для молодежи, г. Москва, октябрь 2010 г.

Численные методы применялись при построении моделей стохастических систем с динамическим выбором шага дискретизации, а также использовался модифицированный метод минимизации, максимизации функций. На этапе проверки адекватности моделей вычисляются средние и среднеквадратичные отклонения теоретических и экспериментальных данных.

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

результат, тем самым сократив нагрузку на сервер или определив наиболее вероятный момент его сбоя. Разработана математическая модель автоматизированного принятия решений на основе данных, полученных из случайной среды.

Основные положения, выносимые на защиту:

1. Модель формирования результатов поисковой структурой при запросах пользователей на основе заданных параметров объектов.

2. Метод нахождения момента остановки процесса сетевого поиска.

3. Математическая модель оптимизации количества результатов поиска на основе оригинального использования численного метода.

4. Комплекс программ для имитационного моделирования и численного анализа процессов поиска.

Достоверность результатов обеспечивается использованием аналитических и численных методов расчёта, методов математического моделирования и применением современных методик анализа экспериментальных данных посредством компьютерного моделирования. Тестирование каждой модели проходило на компьютере путем многократных запусков программ с использованием различных нормировочных коэффициентов.

Теоретическая и практическая значимость диссертационного исследования заключается в том, что разработанный комплекс программ может использоваться как целиком, так и отдельно по трем компонентам. Причем модели и комплекс программ позволяет не только анализировать полученные данные, но и прогнозировать, моделировать различные ситуации, которые позволили сделать поиск более эффективным, определить моменты сбоя сервера и пороговое значение его загруженности. Часть комплекса была внедрена и применяется на практике в ООО «Креатер» г. Ульяновска.

По теме диссертации опубликовано 10 работ, в том числе 4 работы в рецензируемых научных журналах, рекомендованных ВАК.

Диссертация состоит из введения, четырёх глав, заключения, списка литературы из 97 наименований источников отечественных, зарубежных авторов и электронных ресурсов, а также приложений. Общий объём диссертации составляет 126 страниц, в том числе 99 страниц основного текста и 27 страниц приложений.

СОДЕРЖАНИЕ РАБОТЫ

Во введении даётся общая характеристика современного состояния проблемы в данной области исследования и диссертационной работы в целом. Обоснована актуальность темы диссертации, сформулированы цели и задачи в общем виде.

В первой главе рассматриваются популярные на данный момент поисковые структуры. Они сравниваются между собой по различным критериям, а также перечисляются их достоинства и недостатки. Приводится пример обобщенного метода ранжирования результатов выдачи поисковой машиной или поисковиком (на примере «Яндекс»).

В параграфе 1.1 рассказывается о развитии поисковых систем со временем. В параграфе 1.2 приводятся наиболее известные из них в сети Интернет. Производится сравнение и сопоставление таких систем.

В параграфе 1.3 рассматривается обобщенный алгоритм ранжирования результатов на примере поисковой машины Google.

Во второй главе описываются задачи, решаемые в данной диссертационной работе. Производится их математическое и имитационное моделирование.

Предполагается, что гипотетически поисковик при сортировке результатов опирается на некие характеристики объекта под конкретный запрос пользователя. Исходя из этого, возникает задача определения веса той или иной характеристики объекта для поисковика. Данная задача ставится в параграфе 2.1.

В параграфе 2.2 строится теоретическая модель выдачи результатов по обобщенной формуле (1):

(£)> С1)

1=1

где ¿е[1..т], т,п<со. Причем Р1 (Ь) = {Р\,Р2,—,Рп} ~ множество значений характеристик искомых объектов, используемых поисковой структурой для ранжирования результатов выдачи, таких, что значения Р*(Ь) общедоступны, имеются у каждого объекта и могут быть различны для любого элемента из множества поисковых запросов Ь={1\, /г, ..., 4}, К={к1г к2, ..., кп} -множество коэффициентов (так называемого веса) для параметров Р, которые необходимо оценить. Зная результаты / (/ - множество значимостей объекта поиска со временем t=[l..m]), иными словами, зная позицию объекта при выдаче результатов, можно построить линейное приближение и определить коэффициенты К.

В параграфе 2.3 описывается задача оптимизации процесса поиска, решением которой должен задаваться разработчик поисковой структуры, например, решением задачи нахождения оптимального количества выдаваемых поисковиком результатов на запрос пользователя. Эта задача рассматривается в диссертационной работе. Критерием оптимальности в этом случае является наименьшее количество действий, затраченных для поиска необходимой информации.

В параграфе 2.4 строится математическая модель процесса поиска, описываемая формулой (2):

Ф(Л) = ЕЫ1 (со) + ЕР1 (ЛГ- (со); ю)—Ц-тт, (2)

а> о

где ^(г;<й) - позиция /-го объекта на г-й запрос пользователя, причем г = 1,2,..., N, здесь N - функция, характеризующая номер последнего запроса в этом конкретном со -эксперименте, при котором пользователь удовлетворен результатом поиска. В момент г = И процесс о