Воронежский институт МВД России
Кафедра информационной безопасности
ПЛАН
проведения практического занятия
По дисциплине «Компьютерная разведка»
тематический модуль № 1
Тема 2: «Основы аналитической обработки информации»
Практическое занятие: Эффективная методика поиска информации
В сети Интернет.
Обсужден и одобрен
на заседании кафедры
протокол №____ от «__»______2012 г.
Разработал:
доцент кафедры информационной безопасности, к.ф.-м.н., доцент,
полковник полиции
_________________________С.П. Алексеенко
Воронеж 2012
1. Организационная часть - 3 минуты.
Прием рапорта, проверка наличия и готовности курсантов к занятию (внешний вид, тетради, ручки).
2. Вступительная часть - 2 минуты.
Объявление темы, цели занятия и учебных вопросов
3. Опрос по материалам лекции 15 минут
4. Изложение вопроса №1 - 10 минут
5. Изложение вопроса №2 - 10 минут
6. Изложение вопроса №2 - 10 минут
7. Практическая отработка материала – 25 минут
6. Ответы на вопросы - 5 минут
7. Подведение итогов - 2 минуты
8. Задание на самоподготовку - 3 минуты
Итого 90 минут
Форма проведения занятия – самостоятельная работа курсантов под руководством преподавателя, работа преподавателя и курсантов в форме диалога, устный (письменный) опрос по ранее изученному материалу.
Задание по подготовке к практическому занятию
1. Изучить материал лекций по теме №2.
2. Повторить основные понятия, относящиеся к вопросам Основы аналитической обработки информации.
3. Подготовить ответы на контрольные вопросы, заданные на лекционных занятиях по теме №2.
Литература для подготовки:
Основная:
1. Меньшаков Ю. К. Теоретические основы технических разведок: учебное пособие: доп. УМО по образованию в обл. информ. безопасности / Ю. К. Меньшаков; под ред. Ю. Н. Лаврухина. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2008. - 536 с.
Дополнительная:
1. Защита информации в компьютерных системах и сетях /под ред. В.Ф.Шаньгина – 2-е издание перераб. и доп. –М.: Радио и связь, 2001. –376 с.
2. Зима В.М. Безопасность глобальных сетевых технологий./ Зима В.М., Молдавян А.А., Молдовян Н.А. – 2-е изд. - СПб: БХВ - Санкт-Петербург, 2003. - 368 с.
3. Защита от вторжений. Расследование компьютерных преступлений/ Кевин Мандиа Крис.Пер. с англ. Просис. Издательство «Лори», 2005.- 476 с.
4. Руководство по защите от хакеров/ Коул Эрик. Пер. с англ. – М. Издательский дом «Вильямс», 2002. – 640 с.
5. Касперски К. Записки исследователя компьютерных вирусов/ К. Касперски– СПб.: Питер, 2005. – 16 с.
Теоретический материал
ЭФФЕКТИВНАЯ МЕТОДИКА ПОИСКА ИНФОРМАЦИИ В СЕТИ ИНТЕРНЕТ
Автоматический анализ текстов Стратегия поиска Проверка метода на практике
Оказывается, все созданные человеком тексты построены по единым правилам! Никому не удается обойти их. Какой бы язык ни использовался, кто бы ни писал -- классик или графоман, -- внутренняя структура текста останется неизменной. Она описывается законами Зипфа (G.K. Zipf). Зипф предположил, что природная лень человеческая (впрочем, это свойство любого живого существа) ведет к тому, что слова с большим количеством букв встречаются в тексте реже коротких слов. Основываясь на этом постулате, Зипф вывел два универсальных закона:
Первый закон Зипфа "ранг -- частота"
Выберем любое слово и посчитаем, сколько раз оно встречается в тексте. Эта величина называется частота вхождения слова. Измерим частоту каждого слова текста. Некоторые слова будут иметь одинаковую частоту, то есть входить в текст равное количество раз. Сгруппируем их, взяв только одно значение из каждой группы. Расположим частоты по мере их убывания и пронумеруем. Порядковый номер частоты называется ранг частоты. Так, наиболее часто встречающиеся слова будут иметь ранг 1, следующие за ними -- 2 и т.д. Ткнем наугад в страницу и определим вероятность встретить слово, на которое пал выбор. Вероятность будет равна отношению частоты вхождения этого слова к общему числу слов в тексте.
Вероятность = Частота вхождения слова / Число слов
Зипф обнаружил интересную закономерность. Оказывается, если умножить вероятность обнаружения слова в тексте на ранг частоты, то получившаяся величина (С) приблизительно постоянна!
С = (Частота вхождения слова х Ранг частоты) / Число слов
Если мы немного преобразуем формулу, а потом заглянем в справочник по математике, то увидим, что это функция типа y=k/x и ее график -- равносторонняя гипербола. Следовательно, по первому закону Зипфа, если самое распространенное слово встречается в тексте, например, 100 раз, то следующее по частоте слово вряд ли встретится 99 раз. Частота вхождения второго по популярности слова, с высокой долей вероятности, окажется на уровне 50. (Разумеется, вы должны понимать, что в статистике ничего абсолютно точного нет: 50, 52 -- не так уж и важно.)
Значение константы в разных языках различно, но внутри одной языковой группы остается неизменно, какой бы текст мы ни взяли. Так, например, для английских текстов константа Зипфа равна приблизительно 0,1. Интересно, как выглядят с точки зрения законов Зипфа русские тексты? Они не исключение. Анализ хранящихся в моем компьютере файлов с русскими текстами убедил, что закон безупречен и тут. Для русского языка коэффициент Зипфа получился равным 0,06-0,07. Хотя эти исследования не претендуют на полноту, универсальность законов Зипфа позволяет предположить, что полученные данные вполне достоверны.
Второй закон Зипфа "количество -- частота"
Рассматривая первый закон, мы отмахнулись от факта, что разные слова входят в текст с одинаковой частотой. Зипф установил, что частота и количество слов, входящих в текст с этой частотой, тоже связаны между собой. Если построить график, отложив по одной оси (оси Х) частоту вхождения слова, а по другой (оси Y) -- количество слов в данной частоте, то получившаяся кривая будет сохранять свои параметры для всех без исключения созданных человеком текстов! Как и в предыдущем случае, это утверждение верно в пределах одного языка. Однако и межъязыковые различия невелики. На каком бы языке текст ни был написан, форма кривой Зипфа останется неизменной. Могут немного отличаться лишь коэффициенты, отвечающие за наклон кривой [рис. 1] (в логарифмическом масштабе, за исключением нескольких начальных точек, график -- прямая линия).
Законы Зипфа универсальны. В принципе, они применимы не только к текстам. В аналогичную форму выливается, например, зависимость количества городов от числа проживающих в них жителей. Характеристики популярности узлов в сети Интернет -- тоже отвечают законам Зипфа. Не исключено, что в законах отражается "человеческое" происхождение объекта. Так, например, ученые давно бьются над расшифровкой манускриптов Войнича. Никто не знает, на каком языке написаны тексты и тексты ли это вообще. Однако исследование манускриптов на соответствие законам Зипфа доказало: это созданные человеком тексты. Графики для манускриптов Войнича точно повторили графики для текстов на известных языках.
Что дают нам законы Зипфа? Как с их помощью извлечь слова, отражающие смысл текста? Воспользуемся первым законом Зипфа и построим график зависимости ранга от частоты. Как уже упоминалось, его форма всегда одинакова [рис. 2].
Исследования показывают, что наиболее значимые слова лежат в средней части диаграммы. Это и понятно. Слова, которые попадаются слишком часто, в основном оказываются предлогами, местоимениями, в английском -- артиклями и т.п. Редко встречающиеся слова тоже, в большинстве случаев, не имеют решающего смыслового значения.
От того, как будет выставлен диапазон значимых слов, зависит многое. Поставь широко -- нужные термины потонут в море вспомогательных слов; установи узкий диапазон -- потеряешь смысловые термины. Каждая поисковая система решает проблему по-своему, руководствуясь общим объемом текста, специальными словарями и т.п. Проведем эксперимент. Подвергнем абзац текста математическому анализу и попытаемся определить список значимых слов.
В качестве примера возьмем один из предыдущих абзацев (абзац, начинающийся словами "Законы Зипфа универсальны"). Посмотрим, какие слова попали в область значимых слов, а какие нет. В таблице 1 приведены все слова абзаца и указана частота их вхождения. Как видите, слова с частотой 2 и 3 наиболее точно отражают смысл абзаца. Слово с наибольшей частотой вхождения оказалось предлогом, а слова с меньшей -- общими словами.
На рисунке 3 приведен график частота-ранг этого абзаца. Выделим зону значимых слов. Пусть это будут слова с рангом 2, 3 и частотой 3, 2 соответственно. (Обратите внимание, как смещение или расширение зоны значимых слов влияет на их состав.)
Давайте теперь проанализируем выделенную нами область значимых слов. Не все слова, которые попали в нее, отражают смысл текста. Смысл абзаца очень точно выражают слова: зипфа, манускриптов, войнича, законам. Запрос типа: + "закон* зипфа" + "манускрипт* войнича" непременно найдет нам этот документ. Однако в область попали и слова: на, не, для, например, это. Эти слова являются "шумом", помехой, которая затрудняет правильный выбор. "Шум" можно уменьшить путем предварительного исключения из исследуемого текста некоторых слов. Для этого создается словарь ненужных слов -- стоп-слов (словарь называется стоп-лист). Например, для английского текста стоп-словами станут термины: the, a, an, in, to, of, and, that... и так далее. Для русского текста в стоп-лист могли бы быть включены все предлоги, частицы, личные местоимения и т. п. Наверняка попали бы и слова из нашего "шума": на, не, для, это. Есть и другие способы повысить точность оценки значимости терминов.
Весовые коэффициенты
До сих пор мы рассматривали отдельно взятый документ, не принимая во внимание, что он входит в базу данных наряду с множеством других документов. Если представить всю базу данных как единый документ, к ней можно будет применить те же законы, что и к единичному документу. Посмотрите на список терминов в нашем примере. В одну компанию попали слова-термины «Зипфа» и «не» -- они входят в документ равное количество раз. Исследовав остальные документы базы данных на предмет вхождения в них этих терминов, мы, естественно, обнаружим, что «не» встречается очень часто, в то время как «Зипфа» -- довольно редко. Напрашивается очевидный вывод: слово «зипфа» должно стать термином, в то время как «не» следует отбросить, как помеху. Чтобы избавиться от лишних слов и в тоже время поднять рейтинг значимых слов, вводят инверсную частоту термина. Значение этого параметра тем меньше, чем чаще слово встречается в документах базы данных. Вычисляют его по формуле:
Инверсная частота термина i = log (количество документов в базе данных / количество документов с термином i).
Теперь каждому термину можно присвоить весовой коэффициент, отражающий его значимость:
Вес термина i в документе j = частота термина i в документе j х инверсная частота термина i.
Наверняка в нашем примере термин «не» получит нулевой или близкий к нулю вес, поскольку практически во всех текстах попадается это слово. Термин же «зипфа» -- напротив, приобретет высокий вес.
Современные способы индексирования не ограничиваются анализом перечисленных параметров текста. Поисковая машина может строить весовые коэффициенты с учетом местоположения термина внутри документа, взаимного расположения терминов, частей речи, морфологических особенностей и т.п.
В качестве терминов могут выступать не только отдельные слова, но и словосочетания. Джорж Зипф (George K. Zipf) опубликовал свои законы в 1949 году. Пять лет спустя знаменитый математик Беноит Мандлеброт (Benoit Mandlebrot) внес небольшие изменения в формулы Зипфа, добившись более точного соответствия теории практике. Без этих законов сегодня не обходится ни одна система автоматического поиска информации. Как видите, математический анализ позволяет машине с хорошей точностью, без участия человека распознать суть текста.