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

кандидата технических наук
Седова, Татьяна Львовна
город
Москва
год
2008
специальность ВАК РФ
05.13.13
цена
450 рублей
Диссертация по информатике, вычислительной технике и управлению на тему «Модели и алгоритмы специализированного поиска образовательных Интернет порталов для снижения загрузки телекоммуникационной сети»

Автореферат диссертации по теме "Модели и алгоритмы специализированного поиска образовательных Интернет порталов для снижения загрузки телекоммуникационной сети"

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

СЕДОВА ТАТЬЯНА ЛЬВОВНА

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

Специальность: 05.13.13- Телекоммуникационные системы и

компьютерные сети

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва-2008

003456557

Работа выполнена в Федеральном государственном учреждении «Государственный научно-исследовательский институт информационных технологий и телекоммуникаций» (ФГУ ГНИИ ИТТ «ИНФОРМИКА»)

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

доктор технических наук, профессор Иванников А.Д.

Официальные оппоненты:

доктор технических наук, профессор Вишнеков А.В.

кандидат физико - математических наук Сережников С.В.

Ведущая организация: Московский государственный

институт радиотехники, электроники и автоматики (технический университет) (МИРЭА)

Защита диссертации состоится "16" декабря 2008г. в 14-00 часов на заседании диссертационного совета Д212.133.03 при Московском государственном институте электроники и математики (МИЭМ): 109028, Москва, Б. Трехсвятительский пер., дом 3.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики.

Автореферат разослан ноября 2008г.

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

кандидат технических наук,

дешент

Леохин Ю.Л.

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

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

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

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

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

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

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

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

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

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

Целыо работы является создание моделей и алгоритмов позволяющих:

• осуществлять поиск информации в сформированной системе образовательных порталов;

• минимизировать загрузку телекоммуникационной сети при просмотре пользователями предлагаемых источников информации;

• производить оценку каждого найденного пункта по заранее определенным критериям.

В качестве предмета поиска были вьтбпаны образовательные песупсы

í ^ XI

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

Для достижения поставленной цели в работе сформулированы и решены следующие задачи:

• проведен анализ современных поисковых систем, используемых в Интернет среде, выявлены их достоинства и недостатки;

• разработаны алгоритмы оценки близости показателей образовательных порталов к требуемым и их ранжирования;

• разработан комплекс математически моделей для вычисления близости показателей образовательных порталов к требуемым и оценки эффективности различных процедур поиска информации в системе образовательных порталов;

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

На защиту выносятся:

1. Классификация основных компонент образовательных порталов.

2. Математические модели и алгоритмы оценки близости показателей образовательных порталов к *;

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

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

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

Научная новизна полученных результатов заключается в следующем:

1. Разработаны базовые принципы оценки близости основных показателей образовательных порталов к требуемым.

2. Разработана методика получения и обработки экспертных оценок основных компонент образовательных порталов.

3. Разработаны математические модели оценки эффективности процедур поиска путем анализа требуемого количества запросов и длительности сеанса поиска.

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

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

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

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

Реализация и внедрение результатов исследований. Результаты, полученные в диссертации, внедрены и эффективно используются в Федеральном государственном учреждении «Государственный научно-исследовательский институт информационных технологий и телекоммуникаций» (ФГУ ГНИИ ИТТ «ИНФОРМИКА») и Пензенском государственном университете, что подтверждено актами о внедрении.

Апробация работы. Основные положения диссертации докладывались на семинарах ФГУ ГНИИ ИТТ «Информика», Международной конференции «Информационные технологии и системы: наука и практика» (Владикавказ, 2002), Международной научно-технической конференции «Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике» (Владикавказ, 2003), Всероссийской научно-методической конференции «Телематика» (Санкт-Петербург, 2002,2003,2004,2005), Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий (Улан-Удэ, 2002.).

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

Струшура и объем диссертации. Диссертация состоит из введения, четырех глав, списка литературы и приложения. Объем диссертации 134 страницы.

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

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

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

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

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

Исследован алгоритм случайного поиска, когда из множества известных порталов последовательно, случайным образом выбираются для просмотра порталы, до тех пор, пока требуемые данные не будут найдены. При таком поиске никакой информации о содержимом порталов не требуется. Для анализа алгоритма применялась конечная поглощающая Цепи Маркова. Состояние цепи это номер шага поиска. Общее число состояний цепи равно {К+\). К — число порталов. Состояние номер 0 - поглощающее состояние. Из каждого состояния номер г, (К > г > 1) можно перейти только либо в поглощающее (поиск окончен), либо в следующее - (г+1) (поиск продолжается на следующем шаге). Вероятности перехода из состояния / в состояние ] - р образуют матрицу переходных вероятностей Р. Для вычисления требуемых характеристик использовалась фундаментальная матрица N = (I - <3)~'.

До О О

До 0 Яг

До 0

До 0

О О

О Д3 О О

Ят® \Рт 0

О о о о

о .. о , о . РИ-

о о

о о

о о

.0 о

.0 о

•0 ({к-ьк

о о

0(К-1)К 0

о ...... о

О (К-2)/(КЧ) 0 ....... 0

0 0 (К-3)/(К-7) .......0

0 0

0 о

о о

1/2 о

Среднее число шагов до попадания в поглощающее состояние (среднее число попыток поиска до получения результата) может быть вычислено по формуле: п = N0, где е- единичный вектор-столбец размерности К, п -вектор-столбец размерности К.

Среднее время от начала процесса до попадания в поглощающее состояние, при условии, что для всех состояний среднее время пребывания в состоянии, одинаково вычисляется по формуле: 1 = /,п, где /, среднее время поиска на портале 1 - вектор—столбец размерности 1С у которого * - среднее время до попадания в поглощающее состояние при начале процесса в состоянии /.

Отметим, что система обслуживания запросов пользователей двухступенчатая, на первой ступени обслуживание происходит на поисковом сервере. Поэтому полное среднее время обслуживания запроса складывается из времени обслуживания на сервере и длительности поиска нужного портала. Отсюда получим, что среднее время обслуживания запроса пользователя равно:Т0 = Г00 + , где Г00 = я01.

Полное среднее число обращений к каналу связи при обработке одного запроса складывается из обращения к поисковому серверу и обращений к порталам при поиске, и равно: М0 -1 + Ы00, где #00 = л0п. я0 = (гг01,7Г02,...,я-0) , вектор-строка начальных состояний цепи где 0< яй <1

- вероятность того, что перед первым шагом цепь находится в состоянии/.

Далее исследован алгоритм поиска в установленном порядке (по списку), который устанавливается поисковым сервером на основе предварительного анализа содержимого порталов и их ранжирования. В качестве математической модели для анализа процедуры поиска использована К - фазная СМО. На вход системы поступает поток запросов на поиск требуемой информации. Каждое обслуживающее устройство (ОУ) соответствует порталу. Номера ОУ и порталов совпадают. Входящий поток запросов является пуассоновским с параметром А; длительность обслуживания запроса на фазе номер ; случайная величина, распределенные по экспоненциальному закону с параметром >0, т.е.

У7) (/) = 1 ~ е . р! - вероятность того, что искомые данные находятся на

к

портале номер г (/-ой фазе); при этом X р1 = 1.

ы

Получена формула для вычисления среднего времени пребывания запроса в системе: Г, = Е />, [ Ё (1 /(/ - Л + Л 2 Р„,)) | • Показано, что

1 = 1 = 1 т = 1 )

величина 1\ будет минимальна, если поиск проводить в порядке возрастания времени поиска на портале.

Средне число обращений к каналу связи при поиске информации в

к

заданном порядке можно вычислить по формуле: Лг| = 1 + , где Л^,, = £ (р, ■

1=1

Показано, что величина Лгп будет минимальной, если поиск производится в порядке убывания вероятностей р^1 = \,К. Если р:=\/К, / = 1 ,К, то при любом порядке поиска, = (АГ +1)/2.

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

Третий алгоритм подразумевает наличие на поисковом сервере полных данных о порталах, в результате чего сразу однозначно определяется портал, где находятся искомые данные. В качестве модели используется двухфазная СМО, где на фазе 1 проводится обработка запроса на поисковом сервере, а на фазе 2 -обслуживание запроса на портале.

На вход первой фазы поступает пуассоновский поток запросов с параметром А. Длительность обслуживания одного запроса, случайная величина с экспоненциальным распределением и параметром /х0. Поток с фазы 1 на ¡'-й портал является пуассоновским с параметром Л, = Ар,,

1=1 ,К. Длительность обслуживания запроса на портале /- случайная величина с экспоненциальным распределением с параметром //,, / = 1, К.

Среднее число шагов поиска равно: Н2 =2.

Третья глава посвящена разработке математических моделей для оценки качества и поиска в Интернете образовательных порталов. Была проведена оценка качества портала с помощью таксономии путем определения в пространстве критериев «расстояния» от выбранного до «идеального» портала. Для этого использовались следующие обозначения и определения:

Х - вектор переменных, используемых для вычисления значений критериев; Хк - множество значений, принимаемых к- й переменной; Р,(Х)- ¡-й критерий

(] = 1, 2, ...... п); I - множество индексов, используемых для обозначения

критериев (111 = п); <р^Х)- е ограничение; К, - величина, соответствующая наилучшему значению г-го критерия; - величина, соответствующая наихудшему значению /-го критерия. Наилучшему «фиктивному» порталу отвечают значения К, определяемые решением п однокритериальных задач вида:

Решая задачу (1) по каждому критерию К,, получим вектор К={КХ, Кг,.....Д,},

которому в п-мерном пространстве критериев соответствует точка "а" (на рисунке), отвечающая сочетанию наилучших значений Е,(Х). Инвертируя цели оптимизации в (1), аналогично можно получить точку "Ь", (на рисунке) и отвечающий ей вектор критериев IV = { , и',, . ., \Уп}, соответствующий сочетанию наихудших значений критериев К,(Х), /е! . Как вектору к, так и

Среднее время сеанса поиска: Т2 -

.К, шах (тш);

\/к:хкеХ,; Х={х„ х2,....., х,„.}.

(1)

вектору 1¥ может соответствовать недопустимый вектор аргументов X. Это означает, что порталы, соответствующие этим векторам, могут являться фиктивными.

Исследован подход к ранжированию порталов связанный с использованием методов таксономии. В этом случае задача оптимального ранжирования решается в два этапа: на первом строится полный неориентированный граф С(Х,и), вершины которого отвечают порталам, а вес каждого ребра - расстоянию между соответствующими порталами в пространстве критериев. На втором этапе алгоритмом Прима граф преобразуется в сеть без циклов С(Х,и') , после чего вершины (порталы) упорядочиваются согласно расстоянию до «наилучшего» либо «наихудшего» портала, причем понятие «расстояние» меняется: ему соответствует суммарный вес ребер, отвечающих маршруту, соединяющему выбранные вершины. На рисунке приведен пример графа для п=8.

соответствующая лучшему порталу; 5 - вершина, ближайшая к «лучшей»; 4 -вершина, наиболее удаленная от «худшей».

Таким образом, задача оценки качества портала представляет собой поиск расстояния от лучшего (идеального) портала до оцениваемой вершины. Формально задача поиска значения критерия качества Интернет портала может быть сформулирована следующим образом: на заданном взвешенном неориентированном графе без циклов G(X,U) требуется выделить вершину

х, еХ, для которой справедливо: r(x,b)=minr(i,b).

Формальная постановка задачи поиска вершины на таком графе, наиболее удаленной от наихудшей, имеет вид: ^ r(/,/) = max где Ь -

(ij)si(w.j;) d (..,)ei.(„,.</)

вершина, принадлежащая "худшему" эталону ; а - вершина, принадлежащая "лучшему" эталону ; L(q,d) - множество дуг, принадлежащих маршруту от вершины q до вершины d\ r(i,j) - длина ребра между /-й иу'-й вершинами.

Для разработки специализированного ПО оценки качества Интернет портала разработаны необходимые алгоритмы.

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

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

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

Номер портала Адрес портала Значения критериев

I www.edu.ru kl=5, k2=3, k3=3

2 www.opeaet.ru kl=3,k2=3,k3=l

3 www .humanities.ru kl=5, k2=3, кЗ—l

4 www.admin.novsu.ac.ru kl=3, k2=3, k3=l

5 www.ecsocman.edu.ru kl=3,k2=l,k3=l

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

К1

Взаимное располозкение порталов по значениям их критериев

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

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

Зависимость выигрыша времени поиска данных от числа порталов Здесь г] - отношение максимального времени поиска ко времени, определяемом оптимальной последовательностью просмотра порталов.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Проведен анализ наиболее распространенных алгоритмов поиска, случайный поиск, поиск в заданном порядке (по списку), направленный поиск, когда однозначно определен адрес искомых данных. Показано,

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

3. Исследована проблема анализа и сравнительной оценки качества Интернет порталов в & пространстве: методы таксономии были применены для решения задачи оценки разнородных критериев с целью их обобщенного сравнения. Разработаны различные варианты постановки и решения задач оценки качества образовательных Интернет порталов, что позволило разработать машинно-ориентированные алгоритмы оценки качества и ранжирования образовательных Интернет порталов.

4. Разработаны алгоритмы и математические модели для количественной оценки близости заданного набора показателей образовательных Интернет порталов к аналогичному набору требуемых (искомых) показателей. Модели дают возможность проводить ранжирование порталов в заданной системе показателей и составлять оптимальные списки поиска.

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

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

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

7. Проведены экспериментальные исследования, доказывающие эффективность предложенного в работе подхода.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Воробьева Г.И. , Седова T.JI. Технологии определения рейтингов порталов //Научно-информационный журнал «Вестник Московского государственного университета леса-Лесной вестник» № 4 (53) Издательство МГУЛ, 2007г. с.161-164

2. Седова T.JI. Математическое моделирование образовательных порталов //Материалы Международной конференции «Информационные технологии и системы: наука и практика. Владикавказ, Изд-во Владикавказского научного центра, 2002, с.166-169.

3. Седова T.JI. Образовательные порталы - краеугольный камень открытого образования//Материалы международной конференции «Новые информационные технологии в науке, образовании, экономике» Владикавказ, СКГТУ: Изд-во «Терек» 2002г., с.8-9.

4. Седова Т.Л. Математические модели формирования оптимальных порталов//Материалы III Международной конференции «Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике. Владикавказ, Изд-во Владикавказского научного центра, 2003 с. 97-101.

5. Седова T.J1. Структура и информационное наполнение образовательного портала// Материалы всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий», изд-во ВСГТУ, Улан-Удэ:, 2002. с.293-295.

6. Седова T.JI. Создание современных Интернет-порталов // Труды Всероссийской научно-методической конференции «Телематика 2002» Санкт-Петербург, 2002 с.88-89.

7. Седова T.JI. Пути создания оптимального портала//Труды X Всероссийский научно-методической конференции «Телематика 2003» Санкт-Петербург, 2003 с.171-172.

8. Седова Т.Л. Принципы построения механизма поиска образовательных ресурсов на образовательных сайтах// Труды XI Всероссийской научно-методической конференции «Телематика 2004» Санкт-Петербург, 2004 с.116-117.

9. Седова T.JI. Разработка критериев оценки образовательных порталов //Труды XII Всероссийской научно-методической конференции «Телематика 2005», Санкт-Петербург, 2005 с.138.

Подписано в печать 06.11.2008. Формат 60x84/16. Бумага типографская N2 2. Печать - ризография. Усл. печ. л. 1,1 Тираж 100 экз. Заказ

Московский государственный институт электроники и математики 109028, Москва, Б.Трехсвятительский пер., 3/12.

Центр оперативной полиграфии (495) 916-88-04, 916-89-25

Оглавление автор диссертации — кандидата технических наук Седова, Татьяна Львовна

ВВЕДЕНИЕ.

1. АНАЛИТИЧЕСКИЙ ОБЗОР.

1.1. Интернет порталы.

1.2. Общие сведения о поисковых системах.

1.2.1. Индексированные каталоги.

1.2.2. Тематические коллекции ссылок.

1.2.3. Поисковые машины.

1.2.4. Основы работы поисковых машин.

1.2.5. Построение индекса.

1.2.6. Поиск по индексу.

1.2.7. Метапоисковые системы.

1.2.8. Онлайновые энциклопедии и справочники.

Обзор существующих методов таксономии.

1.3.1. Содержательное описание алгоритмов.

1.3.1.1 Алгоритм FOREL.

1.3.1.2. Алгоритм FOREL-2.

1.3.1.3. Алгоритм SKAT.

1.3.2. Поиск в Х - пространстве.

1.3.2.1. Содержательное описание алгоритма KRAB.

1.3.2.2. Проверка качества таксономии алгоритмом KRAB.

Выводы.

2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ РАСЧЕТА ХАРАКТЕРИСТИК ПРОЦЕДУР ПОИСКА НА ИНТЕРНЕТ ПОРТАЛАХ.

2.1. Описание системы.

2.2. Модель процедуры случайного поиска.

2.3. Модель процедуры поиска в заданном порядке.

2.4. Модель процедуры направленного поиска.

2.5. Сравнительный анализ результатов моделирования.

Выводы.

3. СРАВНИТЕЛЬНЫЙ АНАЛИЗ КАЧЕСТВА И ПОИСК В ИНТЕРНЕТЕ ОБРАЗОВАТЕЛЬНЫХ ПОРТАЛОВ.

3.1. Анализ требований к системе сравнительного анализа образовательных порталов в телекоммуникационных сетях.

3.2. Разработка критериев оценки образовательных порталов с помощью бальных оценок.

3.3. Естественные единицы измерения критериев.

3.4. Формальные постановки задачи.

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

3.4.2. Однокритериальные постановки задачи ранжирования.

3.5. Описание алгоритма сравнительного анализа качества Интернет порталов.

Выводы.

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПОИСКОВОЙ СИСТЕМЫ И ТИПОВАЯ МЕТОДИКА ВЫБОРА ОБРАЗОВАТЕЛЬНЫХ ПОРТАЛОВ.

4.1. Существующие технологии формирования динамических страниц в сети Интернет.

4.2. Дополнительные программные средства.

4.2.1. MySQL -решение для WEB.

4.2.2. Поддержка работы с транзакциями.

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

4.3.1. Определение оптимального упорядочения порталов.

4.4. Интерфейс и структура БД.

Выводы.

Введение 2008 год, диссертация по информатике, вычислительной технике и управлению, Седова, Татьяна Львовна

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

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

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

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

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

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

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

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

Целью работы является создание моделей и алгоритмов позволяющих:

• осуществлять поиск информации в сформированной системе образовательных порталов;

• минимизировать загрузку телекоммуникационной сети при просмотре пользователями предлагаемых источников информации;

• производить оценку каждого найденного пункта по заранее определенным критериям.

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

Для достижения поставленной цели в работе сформулированы и решены следующие задачи:

• проведен анализ современных поисковых систем, используемых в Интернет среде, выявлены их достоинства и недостатки;

• разработаны алгоритмы оценки близости показателей образовательных порталов к требуемым и их ранжирования;

• разработан комплекс математически моделей для вычисления близости показателей образовательных порталов к требуемым и оценки эффективности различных процедур поиска информации в системе образовательных порталов;

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

На защиту выносятся:

1. Классификация основных компонент образовательных порталов.

2. Математические модели и алгоритмы оценки близости показателей образовательных порталов к требуемым.

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

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

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

Научная новизна полученных результатов заключается в следующем:

1. Разработаны базовые принципы оценки близости основных показателей образовательных порталов к требуемым.

2. Разработана методика получения и обработки экспертных оценок основных компонент образовательных порталов.

3. Разработаны математические модели оценки эффективности процедур поиска путем анализа требуемого количества запросов и длительности сеанса поиска.

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

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

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

Апробация работы. Основные положения диссертации докладывались на семинарах ФГУ ГНИИ ИТТ «Информика», Международной конференции «Информационные технологии и системы: наука и практика» (Владикавказ, 2002), Международной научно-технической конференции «Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике» (Владикавказ, 2003), Всероссийской научно-методической конференции «Телематика» (Санкт-Петербург,

2002,2003,2004,2005), Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий (Улан-Удэ, 2002.).

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

Заключение диссертация на тему "Модели и алгоритмы специализированного поиска образовательных Интернет порталов для снижения загрузки телекоммуникационной сети"

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ

РАБОТЫ

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

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

3. Исследована проблема анализа и сравнительной оценки качества Интернет порталов в Я пространстве: методы таксономии были применены для решения задачи оценки разнородных критериев с целью их обобщенного сравнения. Разработаны различные варианты постановки и решения задач оценки качества образовательных Интернет порталов, что позволило разработать машинно-ориентированные алгоритмы оценки качества и ранжирования образовательных Интернет порталов.

4. Разработаны алгоритмы и математические модели для количественной оценки близости заданного набора показателей образовательных Интернет порталов к аналогичному набору требуемых (искомых) показателей. Модели дают возможность проводить ранжирование порталов в заданной системе показателей и составлять оптимальные списки поиска.

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

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

7. Проведены экспериментальные исследования, доказывающие эффективность предложенного в работе подхода.

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

Библиография Седова, Татьяна Львовна, диссертация по теме Телекоммуникационные системы и компьютерные сети

1. Айзерман А.А., Браверман Э.М., Розоноэр Э.И. Метод потенциальных функций в теории обучения машин. - М.: Наука, 1970.

2. Андерсон Т.В. Введение в многомерный статистический анализ. М. Физматиздат 1963 г.

3. Аркадьев А.Г., Браверман Э.М. Обучение машины распознаванию образов.

4. Банник В.Н., Червоненкис А.Я. Теория распознавания образов. М. Наука, 1974.

5. Бонгард М.М. Проблема узнавания. М. Наука, 1967.

6. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. — М.: Изд-воРУДН, 1995.-529 с.

7. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. -М.: Техносфера, 2003. 512с.

8. Волошин Г.Я., Бурлаков И.А., Косенкова С.Т. Статистические методы решения задач распознавания, основанные на аппроксимационном подходе. Владивосток: ТОЙ ДВО РАН, 1992.

9. Гладун В.П. Планирование решений. Киев, Наукова думка. 1987.

10. Ю.Горелик A.JL, Скрипкин В.А. Методы распознавания. М.: Высш. шк.,1977.

11. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.

12. В.Н.Елкина, Загоруйко Н.Г., Новоселов Ю.А. Математические методы агроинформатики. Тр.ИМ СО АН СССР, Новосибирск, 1987г.

13. Елкина В.Н., Загоруйко Н.Г., Куклин А.П. Типы золотоносных территорий Чукотской складчатой области. Сб. "Колыма", N4, Магадан, 1974 г, с.41-45.

14. Елкина В.Н., Загоруйко Н.Г. Количественные критерии качества таксономии и их использование в процессе принятия решений. Тр. ИМ СО РАН серия "Вычислительные системы", 1969, вып. 36, Новосибирск, с.29

15. Загоруйко Н.Г. Метакритерий для отбора предикатов в алгоритмах прогнозирования. Тр. 3-го Сибирского Конгресса по прикладной и индустриальной математике (ИНПРИМ-98). Новосибирск, 1998,Часть IV, с.95-96

16. Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов. радио, 1972.

17. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск, 1999 г.

18. Загоруйко Н.Г., Ёлкина В.Н., Емельянов С.В., Лбов Г.С. Пакет прикладных программ ОТЭКС. М.: Финансы и статистика, 1986.

19. Загоруйко Н.Г., Заславская Т.И. Распознавание образов в социальных исследованиях. Новосибирск, Наука, 1968 г.

20. Кемени Дж., Снелл Дж. Конечные цепи Маркова.- М.:Наука, 1970. 272 с.

21. Клейнрок JI. Вычислительные системы с очередями. Пер. с англ. Под ред. Б.С. Цыбакова.- М.: Мир. 1979. 600 с.

22. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. М. Наука. 1967.

23. Мамчур. Е. А. Проблема выбора теории. М. Наука 1975.

24. Моисеев И.Н. Алгоритмы развития М., Наука 1987.25.0лифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. СПб.: Питер, 1999. 672 с.

25. Патрик Э. Основы теории распознавания образов. М.: Сов. радио, 1980. Перевод с английского Киев, Техника, 1965г.

26. Себастьян Г.С. Процессы принятия решений при распознавании образов.

27. Танненбаум Э., М. Ван Стен. Распределенные системы. Принципы ипарадигмы. СПб.: Питер, 2003. - 877 с.

28. Фу К.С. Последовательные методы в распознавании образов и обучении машин. М.: Наука, 1971.

29. Фу К.С. Структурные методы в распознавании образов. М.: Мир, 1977.31 .Материалисты древней Греции. Изд. "Мир", Москва, 1957.

30. N.G.Zagoruiko, T.I.Zaslavska. On possibility of pattern recognition methods utilization in sociological researh. Int.J."Quanlity and Quantity" v.IV (1970), n.2, pp. 365-374.

31. Воробьева Г.И., Седова Т.JI. Технологии определения рейтингов порталов //Научно-информационный журнал «Вестник Московского государственного университета леса -Лесной вестник» № 4 (53) Издательство МГУ Л, 2007г. с. 161-164

32. Седова Т.Л. Математическое моделирование образовательных порталов //Материалы Международной конференции «Информационные технологии и системы: наука и практика. Владикавказ, Изд-во Владикавказского научного центра, 2002, с.166-169.

33. Седова Т.Л. Образовательные порталы — краеугольный камень открытого образования//Материалы международной конференции «Новые информационные технологии в науке, образовании, экономике» Владикавказ, СКГТУ: Изд-во «Терек» 2002г., с.8-9.

34. Седова Т.Л. Структура и информационное наполнение образовательного портала// Материалы всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий», изд-во ВСГТУ, Улан-Удэ:, 2002. с.293-295.

35. Седова Т. JI. Создание современных Интернет-порталов // Труды Всероссийской научно-методической конференции «Телематика 2002» Санкт-Петербург, 2002 с.88-89.

36. Седова Т.Д. Пути создания оптимального портала//Труды X Всероссийский научно-методической конференции «Телематика 2003» Санкт-Петербург, 2003 с. 171-172.

37. Седова T.JI. Принципы построения механизма поиска образовательных ресурсов на образовательных сайтах// Труды XI Всероссийской научно-методической конференции «Телематика 2004» Санкт-Петербург, 2004 с.116-117.

38. Седова T.JI. Разработка критериев оценки образовательных порталов //Труды XII Всероссийской научно-методической конференции «Телематика 2005», Санкт-Петербург, 2005 с. 138.