Выпускная работа по «Основам информационных технологий»



Скачать 154.49 Kb.
Дата05.09.2014
Размер154.49 Kb.
ТипВыпускная работа

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




Выпускная работа по

«Основам информационных технологий»



Минск, 2009 г.


Магистрант кафедры кибернетики

Макаревич Юрий Викторович

Руководители:

доцент, к. ф.-м. н.

Воротницкий Юрий Иосифович,

старший преподаватель

Кожич Павел Павлович


Оглавление


Оглавление 2

Список обозначений 3

Реферат на тему «Применение современных информационных технологий при автоматизированном анализе информационных ресурсов сети Интернет» 4

Введение 4

Глава 1. Актуальность работы 4

Глава 2. База данных сайта Wikipedia и алгоритм HITS 5

Глава 3. Адаптированный алгоритм HITS 6

Глава 5. Исследование эффективности работы адаптированного алгоритма HITS 9

Заключение 10

Список литературы 11

Предметный указатель 12

Интернет ресурсы в предметной области исследования 13

Личный сайт 14

Граф научных интересов 15

Тестовые вопросы по основам информационных технологий 17

Презентация к магистерской работе 18

Список литературы 19

Приложение. Презентация магистерской работы 20





Список обозначений


HITS – Hyperlink-Induced Topic Search

Реферат на тему «Применение современных информационных технологий при автоматизированном анализе информационных ресурсов сети Интернет»

Введение


Увеличение числа и изменение качества электронных документов в сети Интернет постоянно выдвигает новые требования к технологиям, позволяющим производить поиск среди всего этого многообразия информации. Очень маловероятно, что такая область исследования, как интеллектуальных анализ данных (data mining), потеряют свою актуальность в ближайшем будущем [1].

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

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

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

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

Глава 1. Актуальность работы


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

Предлагаемый метод основывается на автоматизированном исследовании ресурсов сети Интернет. В качестве исходных данных используется база данных статей сайта Wikipedia [4]. Эти данные анализируются с помощью модифицированного алгоритма HITS. И в результате для каждого термина находится его синоним, а также указывается степень синонимичности. Это позволяет значительно ускорить построение базы данных синонимов для дальнейшего использования их в алгоритмах автоматизированного анализа данных.


Глава 2. База данных сайта Wikipedia и алгоритм HITS


В качестве исходных данных для построения базы данных синонимов используется база данных сайта Wikipedia. Этот сайт представляет собой энциклопедию, содержащую более 14 миллионов статей на различных языках [5]. Каждая статья является описанием какого-либо факта, или явления, или какой-либо личности. Также эта статья может ссылаться на какие-либо другие статьи. Анализируя эти статьи можно заметить, что статьи в подавляющем большинстве содержат ссылки на другие статьи, которые описывают схожие идеи или явления. Таким образом, можно предположить, что если статья A ссылается на статью B, то статья B является синонимом статьи A.

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

Описанный выше граф анализируется алгоритмом, основанном на алгоритме подсчета «важности» страниц HITS [6]. Этот алгоритм для каждой статьи вычисляет две величины authority и hub. Значение величины authority описывает «качество» данных в статье – количество статей, ссылающихся на эту статью. Значение величины hub описывает вероятность того, что данная статья является хабом – то есть, сама статья может не нести в себе много информации, однако она ссылается на множество других статей по данной тематике.

Предположим, что – граф описывающий все множество статей и ссылок между ними, где – это множество статей (pages), а – отношение, описывающее тот факт, что она статья ссылается на другую (то есть, если где – статьи, то статья ссылается на статью ).

Для каждой статьи определим множество статей , которые ссылаются на данную страницу:


(1)

а также множество статей на которые ссылается данная статья:




(2)

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




(3)



(4)

Эти величины подсчитываются таким образом, чтобы в конечном итоге выполнялись следующие условия:


(5)



(6)

Подсчет этих величин выполняется по следующему алгоритму:



  1. Всем величинам authority и hub присваивается значение 1:

  2. Для всех статей обновляется значение величины authority по формуле (7).

  3. Для всех статей обновляется значение величины hub по формуле (8).

  4. Производится нормализация значений величин authority и hub:


(9)



(10)


  1. Все повторяется с шага 2 до тех пор, пока значения authority и hub не перестанут меняться.

Сходимость такого алгоритма доказана в [Error: Reference source not found].

Глава 3. Адаптированный алгоритм HITS


Для построения базы данных синонимов с учетом особенности базы данных статей Wikipedia базовый алгоритм HITS был адаптирован.

В энциклопедии Wikipedia существуют специальные статьи, которые описывают категории. Под категорией в данном случае понимается некоторый набор статей, объединенных общей тематикой. Например, в категории «Алгоритмы поиска» могут находится ссылки на такие статьи как «Линейный поиск», «Двоичный поиск», «Задача поиска ближайшего соседа».

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


(11)

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

На основе этого множества категорий определим граф ребра которого заданы следующим образом:


(12)

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




(13)



(14)



(15)



(16)

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

Перед описанием алгоритма кластеризации определим граф на множестве кластеров Его ребра зададим способом, аналогичным (17):


(18)

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




(19)



(20)

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




(21)



(22)

Весом ребра графа кластеров будем называть суммарный вес кластеров, из которых состоит это ребро:




(23)



(24)

Кластеризация категорий производится по следующему алгоритму:



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

  2. Пересчитываются веса всех ребер из множества

  3. Выбирается ребро с наименьшим весом:


(25)


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

  2. Строится новое разбиение, в соответствии с которым кластеры, которые являются вершинами этого ребра, объединяются. Формально новому разбиению соответствует следующий граф:


(26)



(27)



(28)


  1. Алгоритм повторяется, начиная с шага 2.

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

Для поиска синонимов некоторого термина производятся следующие шаги:



  1. Находится статья соответствующая данному термину

  2. Находится множество всех категорий, в которые входит данная статья:


(29)


  1. Объединяется множество всех тех кластеров, в которые входят элементы (получается один большой кластер):


(30)


  1. Определяется подграф графа элементы которого входят в :


(31)



(32)


  1. На подграфе для каждой статьи проводится расчет величин authority и hub в соответствии с алгоритмом HITS, описанным в главе 4.

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

Глава 5. Исследование эффективности работы адаптированного алгоритма HITS


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

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

Исследование проводилось с локально установленной версией сайта Wikipedia, соответствующей версии оригинального сайта на 8 декабря 2009 года. Она включала в себя 901,861 страницу с 18,380,035 ссылками на английском языке и 30,161 страницу с 468,771 ссылкой на русском языке.

Оно позволил установить, что разработанная система в целом позволяет получить большее количество синонимов для данного слова, чем, например, предоставляет словарь Lingvo [7]. Например, для слова “robot” система позволяет найти следующий список синонимов: “machine”, “virtual”, “digitally”, “clockwork”, “roboraptor”,“autonomous”. В то же время Lingvo в качестве синонима позволяет найти только слово “automaton”.


Заключение


В работе представлен адаптированный алгоритм HITS для поиска синонимов и близких по смыслу слов в корпусах текстов с гиперссылками и категориями. Алгоритм реализован в программе Synarcher, осуществляющей поиск в английской и русской версиях энциклопедии Wikipedia.




Рисунок 1. Результаты поиска синонимов к слову «дорогу» представленные в виде текста и графа.
Проведён ряд экспериментов, показывающих возможность успешного поиска синонимов с помощью данной программы. Для некоторых слов были найдены синонимы, отсутствующие в тезаурусах таких словарей как Lingvo. Это можно объяснить свойствами источника данных (энциклопедии Wikipedia): наличие статей, ориентированных на классическую для энциклопедии тематику (наука, искусство, политика и др.), и статей, ориентированных на самую современную тематику (база обновляется, буквально, каждый день).

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


Список литературы

Предметный указатель


HITS 3, 5, 6, 7, 9, 10

Wikipedia 5, 6, 9, 10, 22

кластер 8, 9

кластеризация 8




Интернет ресурсы в предметной области исследования


  1. http://aclweb.org/ – сайт международной ассоциации по обработке естественных языков и вычислительной лингвистике. Содержит большое количество доступных статей, а также перечень проводимых в мире конференций по вычислительной лингвистике.

  2. http://nlp.stanford.edu/ – сайт группы обработки естественных языков Стэндфордского университета. Он содержит обучающие ресурсы, текущие новости в плане исследований, а также много доступных для скачивания публикаций.

  3. http://www.machinelearning.ru/ – профессиональный информационно-аналитический ресурс, посвященный машинному обучению, интеллектуальному анализу данных и распознаванию образов. Содержит большое количество научных статей, постоянно обновляется. В рамках данного ресурса функционирует проект «Полигон», целью которого является создание распределенной системы тестирования алгоритмов классификации.

  4. http://arxiv.org/ – сайт библиотеки университета Корнель, содержащий множество различных публикаций по естественным наукам. Новые публикации на сайте появляются ежедневно.

  5. http://www.iop.org/ – сайт Института Физики, который предоставляет ряд бесплатных и предоставляемых по подписке услуг на английском языке международному физическому сообществу.

  6. http://www.google.com/ – сайт, в котором можно найти любую информацию по любой тематике.



Личный сайт


http://makarevich-yura2.narod.ru – личный сайт магистранта кафедры кибернетики Макаревича Юрий Викторовича. На нем размещены краткая информация о самом магистранте, результаты работ в области исследования автоматизированного анализа ресурсов сети Интернет, результаты магистерской работы, гостевая книга и некоторая другая информация.

Граф научных интересов


магистранта Макаревича Юрия Викторовича факультета радиофизики и электроники БГУ специальности «компьютерная безопасность; программно-аппаратные методы и средства».


Смежные специальности

Основная специальность

Сопутствующие специальности


05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

  1. Разработка теории алгоритмов и программ, формальных языков

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




05.13.13 – телекоммуникационные системы и компьютерные сети

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

  2. Разработка новых методов реализации технологий человеко-машинного интерфейса

  3. Разработка новых технологий защиты распределенной информации




05.13.17 – теоретические основы информатики, физ.-мат.

  1. Исследование средствами вычислительной техники моделей информационных структур и информационных процессов

  2. Исследование и разработка моделей представления данных и знаний

  3. Разработка методов и моделей распознавания и понимания речи




05.13.19 – методы и системы защиты информации, информационная безопасность

  1. Теория и методология обеспечения информационной безопасности.

  2. Разработка новых средств криптографической защиты

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




01.04.03 – радиофизика

  1. Нелинейные динамические системы

  2. Электродинамика

  3. Распространение радиоволн

  4. Оптические методы обработки информации




05.13.01 – системный анализ, управление и обработка информации

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

  2. Методы и алгоритмы интеллектуальной поддержки при принятии решений

  3. Методы получения, анализа и обработки экспертной информации.

Тестовые вопросы по основам информационных технологий


Вопрос №1



Что такое информационные технологии?



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

глобальная телекоммуникационная сеть информационных и вычислительных ресурсов

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

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





Вопрос №2



Что такое интеллектуальный анализ данных?



способ постановки эксперимента, в ходе которого испытуемая система принудительно обучается с помощью примеров "стимул-реакция"

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

разделение множества входных векторов на группы (кластеры) по степени «похожести» друг на друга

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









Презентация к магистерской работе


Полная презентация магистерской работы находится в Интернете по адресу: http://makarevich-yura2.narod.ru/present.ppt. Выдачи слайдов презентации находятся в приложении.

Список литературы


  1. Joseph W. Habraken Microsoft Office 2003 all-in-one / Habraken J. W. – All in One Series – Que Publishing, 2004 – 951 pages

  2. Nancy Andrews Microsoft Word: the Microsoft reference guide to all commands, functions, and features / Andrews N. – Microsoft Press, 1987 – 309 pages

Приложение. Презентация магистерской работы





































1. Mehmed Kantardzic Data mining: concepts, models, methods, and algorithms / M. Kantardzic – Wiley-Interscience, 2003 – 345 pages

2. Браславский П. Автоматические операции с запросами к машинам поиска интернета на основе тезауруса: подходы и оценки / Браславский П. – Компьютерная лингвистика и интеллектуальные технологии: Труды Междунар. конф. Диалог'2004. – М.: Наука, 2004. – С. 79-84. 4.

3. Curran, J., Moens, M. Improvements in automatic thesaurus extraction. In Proceedings of the ACL / Curran, J., Moens, M. –Workshop on Unsupervised Lexical Acquisition – Philadelphia, P.A. 2002 – 267 pages

4. Wikipedia, the free encyclopedia [Electronic resource] / Wikimedia Foundation, Inc. – 2009 – Mode of access: http://en.wikipedia.org/

5. Wikipedia [Electronic resource]: from Wikipedia, the free encyclopedia / Wikimedia Foundation, Inc. – 2009 – Mode of access: http://en.wikipedia.org/wiki/Wikipedia

6. J.M.Kleinberg Authoritative Sources in a Hyperlink Environment / J.M.Kleinberg – Journal of the ACM vol. 46, 1999 – pp. 604-632.

7. Dictionary Software ABBYY Lingvo x3 [Electronic resource] / ABBYY – 2009 – Mode of access: http://www.lingvo.com/


Похожие:

Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»
Реферат на тему «Результаты внедрения информационных технологий в область изобразительного искусства» 5
Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»
Реферат на тему «Применение информационных технологий в социологических исследованиях» 5
Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»
«Применение информационных технологий в судопроизводстве: электронное правосудие» 4
Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»
Использование информационных технологий в современных прагмалингвистических исследованиях
Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»
Использование информационных технологий при изучении насаждения осадничества в полесском воеводстве в межвоенный перио
Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»

Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»
Последние десятилетия ХХ века отмечены событиями, существенным образом трансформировавшими современную социокультурную реальность....
Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»
На современном этапе ни одни исследования в науке невозможно представить без использования информационных технологий. Данный реферат...
Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»
Реферат на тему «Применение ит в автоматическом доказательстве геометрических теорем» 4
Выпускная работа по «Основам информационных технологий» iconВыпускная работа по «Основам информационных технологий»
Алгоритм адаптивного стеганографического маркирования объектов спутниковых изображений 16
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org