Введение
1. Современные информационные сети
1.1. Интернет - история и протоколы
1.2. Всемирная паутина - World Wide Web
1.3. Пиринговые сети
1.4. Проблемы развития интернет-контента
2. Информационный поиск
2.1. Булева модель поиска
2.1.1. Классическая булева модель
2.1.2. Расширенная булева модель
2.1.3. Модель нечеткого поиска
2.2. Векторно-пространственная модель поиска
2.3. Вероятностная модель поиска
2.4. Алгоритмы поиска в пиринговых сетях
2.4.1. Алгоритм поиска ресурсов по ключам
2.4.2. Метод широкого первичного поиска
2.4.3. Метод случайного широкого
первичного поиска
2.4.4. Интеллектуальный поисковый механизм
2.4.5. Методы "большинства результатов
по прошлой эвристике"
2.4.6. Метод "случайных блужданий"
2.5. Информационно-поисковые языки
2.6. Характеристики информационного поиска
3. Концепция Text Mining
3.1. Контент-анализ
3.2. Элементы Text Mining
3.2.1. Извлечение понятий
3.2.2. Определение взаимосвязей понятий
3.2.3. Автоматическое реферирование
3.2.4. Поисковые образы документов
3.2.5. Выявление дублирования информации
3.2.6. Выявление новых событий
3.3. Реализации систем с элементами Text Mining
4. Методы классификации информации
4.1. Задача классификации
4.1.1. Формальное описание задачи классификации
4.1.2. Ранжирование и четкая классификация
4.1.3. Линейная классификация
4.2. Метод Rocchio
4.3. Метод регрессии
4.4. ДНФ-классификатор
4.5. Классификация на основе искусственных
нейронных сетей
4.5.1. Формальный нейрон
4.5.2. Искусственная нейронная сеть
4.5.3. Правила обучения перцептрона
4.5.4. Нейронная сеть как классификатор
4.6. Байесовский классификатор
4.6.1. Байесовская логистическая регрессия
4.6.2. Наивная байесовская модель
4.6.3. Байесовский подход
к решению проблемы спама
4.6.4. Определение тональности сообщений
4.7. Метод опорных векторов
4.8. Оценка качества классификации
5. Элементы кластерного анализа
5.1. Латентно-семантический анализ
5.1.1. Матричный латентно-семантический анализ
5.1.2. Вероятностный
латентно-семантический анализ
5.2. Метод k-means
5.3. Иерархическое группирование-объединение
5.4. Метод суффиксных деревьев
5.5. Гибридные методы
5.6. Ранжирование результатов поиска
5.6.1. Алгоритм HITS
5.6.2. Алгоритм PageRank
5.6.3. Алгоритм Salsa
5.6.4. Ранжирование "по Хиршу"
6. Эмпирические распределения и математический
формализм
6.1. Эмпирические закономерности
6.1.1. Распределение Парето
6.1.2. Законы Ципфа
6.1.3. Закономерность Бредфорда
6.1.4. Закон Хипса
6.2. Степенные распределения случайных величин
6.3. Однородные функции и скейлинг
6.4. Параметр порядка и фазовые переходы
7. Энтропия и количество информации
7.1. Энтропия Шеннона
7.2. Свойства энтропии
7.3. Условная энтропия
7.4. Энтропия непрерывного источника информации
7.5. Количество информации
7.6. Взаимная информация
8. Основы теории сложных сетей
8.1. Параметры сложных сетей
8.1.1. Параметры узлов сети
8.1.2. Общие параметры сети
8.1.3. Распределение степеней узлов
8.1.4. Путь между узлами
8.1.5. Коэффициент кластерности
8.1.6. Посредничество
8.1.7. Эластичность сети
8.1.8. Структура сообщества
8.2. Модель слабых связей
8.3. Модель малых миров
8.4. WWW как сложная сеть
8.4.1. Топология WWW
8.4.2. Сетевая структура новостного веб
8.5. Визуализация сложных сетей
9. Элементы теории перколяции
9.1. Задача теории перколяции
9.2. Характеристики перколяционных сетей
9.3. Сеть с экспоненциально широким
распределением
9.4. Диодные перколяционные сети
9.5. Перколяция на случайных сетях
9.6. Теория перколяции
и моделирование атак на сети
10. Модели информационных потоков
10.1. Линейная модель
10.2. Экспоненциальная модель
10.3. Логистическая модель
10.4. Модель диффузии информации
10.5. Модель самоорганизованной критичности
11. Элементы фрактального анализа
11.1. Фракталы и фрактальная размерность
11.2. Абстрактные фракталы
11.3. Информационное пространство и фракталы
11.4. Фракталы и временные ряды
11.4.1. Метод DFA
11.4.2. Корреляционный анализ
11.4.3. Фактор Фано
11.4.4. Показатель Херста
11.5. Мультифрактальный анализ рядов измерений
Заключение
Список сокращений
Глоссарий
Литература
Интернетика - это новое научное направление, охватывающее основы теорий информационного поиска и сложных сетей. Авторы предполагают, что именно на стыке этих двух областей может лежать решение открытой проблемы навигации в современных информационных сетях.
В ней рассматриваются вопросы, относящиеся к информационной структуре веб-пространства, теории сложных сетей, моделям информационного поиска и глубинного анализа текстов, общим закономерностям современных информационных потоков и их моделированию.
Изложение расчитано на специалистов в области информационных технологий, прикладных лингвистов, студентов, аспирантов, аналитиков в различных областях. Она может служить основой для построения учебных курсов, посвященных вопросам информационного поиска в сетевой среде.
Основная идея этого текста - показать связь двух активно развивающихся в настоящее время направлений - теорий информационного поиска и сложных сетей. Именно на стыке этих двух областей может лежать решение открытой проблемы эффективной навигации в современных информационных сетях.
Самое подходящее название такой интеграции, нового научного направления - Интернетика. Во-первых, это направление является развитием информатики, и, что должно быть созвучно этому термину. Связь с теорией сложных сетей [116] обуславливает наличие корня "нет", однако подразумевается, что исследования в рамках данного направления выйдут за рамки конкретной сети Интернет, анализ которой, безусловно входит в сферу интернетики. Во-вторых, этот термин, хотя уже и встречается, но еще недостаточно устоялся. Известны по меньшей мере две трактовки термина "интернетика". В рамках первой интернетика рассматривается как прикладное научное направление, изучающее свойства и способы использования Интернет преимущественно в аспекте воздействия на социально-экономические процессы [35]. Эта трактовка, по нашему мнению, несколько сужает область исследований (хотя и способствует популярности). Вторая трактовка, автором которой является Дж. Фокс (G. Fox) из Сиракузского университета (США), заключается в том, что интернетика - это развитие информатики в направлении применения современных параллельных сетевых вычислений во всех областях науки, охватывая огромные ресурсы, распределенные в сетевой среде [91, 92]. Вторая трактовка понятия "интернетика", предполагающая использование методов точных наук гораздо ближе авторам, чем первая.
Сегодня структура и объемы информационных потоков, в которых приходится выискивать крупицы необходимой, готовой к непосредственному использованию, обуславливают актуальность самого процесса поиска. Развитие Интернет породило ряд специфических проблем, связанных, в первую очередь, с возрастанием объемов данных в веб-пространстве, в том числе и бесполезных, шумовых. По-видимому, организация поиска необходимой информации в этом информационном хранилище требует новых подходов. Можно предположить, что современные информационные технологии готовы к подобному пересмотру принципов обеспечения доступа к сетевым данным.
Многие подходы, излагаемые в этой книге, уже стали классическими и широко используются в практике информационного поиска и анализа информации. Авторы попытались дать систематический и вместе с тем достаточно популярный обзор основных моделей, рассматриваемых в рамках теории информационного поиска, научного направления, сформировавшегося в конце ХХ века. Кроме того, в книге также представлены процедурные основы фрактального анализа, который применяется для исследования информационных потоков.
Сегодня в Интернет существует доступная для экспериментов динамичная информационная база такого объема, который ранее даже трудно было представить. При этом оказалось, что многие задачи, возникающие при работе с сетевым информационным пространством, имеют немало общего, например, с задачами теоретической физики. Это обстоятельство открывает широкие перспективы применения мощного аппарата естественных наук.
Вместе с тем реальный прорыв в области информационного поиска возможен лишь в результате агрегирования различных научных направлений. Излагаемые в книге результаты исследований современного сетевого информационного пространства с нескольких, ранее порой конфликтующих точек зрения, могут представлять интерес как для специалистов в области компьютерной лингвистики, так и для прикладных математиков и физиков, например, в плане аналогового моделирования статистических процессов, в том числе систем с элементами самоорганизации.
Изложение ориентировано на достаточно широкий круг читателей: специалистов в области информационного поиска, прикладных лингвистов, студентов, аспирантов; хочется верить, что она будет также полезна и аналитикам, которые при решении задач в различных областях хотят учитывать особенности современного сетевого информационного пространства. Надеемся, что эта книга окажется также полезной при подготовке учебных курсов по теоретическим и практическим вопросам информационного поиска.
Дмитрий Ландэ, Андрей Снарский, Игорь Безсуднов
Введение
Nothing's gonna change my world...
J. Lennon, P. McCartney
Этот текст посвящен новому научному направлению - интернетике. Сегодня в информационных хранилищах, распределенных в сетях, собраны террабайты текстовых данных. Эти данные можно рассматривать, с одной стороны, как сетевую среду реального информационного поиска, а с другой, как объект и полигон для исследований. Учет этих факторов привел к необходимости представить краткий обзор истории и современного состояния инфраструктуры Интернет, остановиться на особенностях гипертекстовых технологий, сети WWW, а также обозначить перспективы.
Именно этим аспектам посвящена первая глава. Для обеспечения поиска размещенной в сети информации в настоящее время необходима разработка новых подходов. При этом, безусловно, должны учитываться достоинства и недостатки существующих моделей и алгоритмов информационного поиска, которым посвящена вторая глава. В этой главе уделено внимание также моделям поиска в пиринговых сетях - крупнейших по ресурсам и порождаемому интернет-трафику. В таких сетях отсутствуют выделенные серверы, а каждый узел является как клиентом, так и сервером. Пиринговые сети состоят из узлов, каждый из которых взаимодействует лишь с некоторым подмножеством других узлов. При освещении этой тематики учитывались то, что проблемы поиска и уязвимости в таких сетях до сих пор остаются открытыми. Рассмотрены основные модели поиска, все более широко применяемые в пиринговых сетях, а также проблемы, связанные с распространением подобных сетей.
В третьей главе рассматривается концепция глубинного анализа текстов - Text Mining, которая включила в себя технологические и методологические подходы контент-анализа, компьютерной лингвистики. В частности, в этой главе освещены подходы к решению таких задач, как автоматическое реферирование, анализ взаимосвязей понятий, построение поисковых образов документов.
Классификация информации - это традиционная компонента теории и технологии информационного поиска, лежащая на стыке двух областей - машинного обучения и информационного поиска. При классификации текстов, методы которой детально рассматриваются в четвертой главе, используются различные критерии для построения правил их размещения в заранее определенные категории.
Пятая глава посвящена вопросам кластерного анализа массивов текстовых документов. В отличие от классификации, при кластеризации заранее не фиксируются определенные категории. Результатом кластеризации является автоматическая группировка информации в компактные подгруппы. Алгоритмы кластеризации позволяют автоматически находить "скрытые" признаки и разделять объекты по подгруппам. Кластеризация, как правило, предшествует классификации, поскольку помогает экспертам определять группы объектов - классы. В этой же главе подробно рассмотрены основные алгоритмы ранжирования выдачи информационно-поисковых-систем.
В шестой главе приводятся основные закономерности, присущие документальным потокам в современной сетевой среде. При этом уделяется внимание таким необходимым для понимания этих закономерностей математическим понятиям, как степенные распределения, однородные функции и скейлинг.
Теория информации, которая ранее находила свое основное применение в области передачи данных, становится полезной и для анализа текстовых массивов, динамически порождаемых в сетях. Седьмая глава посвящена таким понятиям, как энтропия и количество информации, которые сегодня находят все большее применение в технологиях информационного поиска.
Восьмая глава посвящена теории сложных сетей (complex networks), в рамках которой рассматриваются характеристики, учитывающие не только их топологию, но и статистические распределения характеристик узлов и связей. Сегодня эта теория особо актуальна в задачах выявления и визуализации различных сетевых кластеров, их внутренних корреляций.
Явления, происходящие в сложных сетях, близки к изучаемым в рамках теории перколяции (протекания), элементы которой излагаются в девятой главе. К задачам теории перколяции и анализа сложных сетей относятся такие, как определение предельного уровня проводимости (пропускной способности), изменения длины пути между узлами и его траектории (извилистости, параллельности) при приближении к порогу протекания, количества узлов, которые необходимо удалить, чтобы нарушить связанность сети.
Математическому моделированию информационных потоков посвящена десятая глава, в которой рассматриваются модели, учитывающие "конкуренцию" реальных тематик. При моделировании этих процессов используются методы нелинейной динамики, теории клеточных автоматов и самоорганизованной критичности.
При моделировании информационных потоков изучаются структурные связи между входящими в них массивами документов. Сегодня при этом все чаще применяется фрактальный анализ, подход, базирующийся на свойствах сохранения внутренней структуры массивов документов при изменениях их размеров или масштабов рассмотрения. Этому посвящена одиннадцатая глава.
Хочется подчеркнуть, что традиционно используемый математический аппарат и инструментальные средства информационного поиска сегодня уже не способны в полной мере удовлетворять потребности пользователей. Изначальная парадигма поисковых систем, сформированная несколько десятилетий тому назад, уже не отвечает реальной ситуации - объемам и динамике информационных потоков, сетевой топологии. Необходим поиск новых принципов, в рамках которых оказалось бы возможным проектирование качественно новых систем обработки больших и динамичных массивов данных. Цель изложения - систематически описать состояние существующих теоретических и технологических возможностей, представить читателю возможные перспективы развития, дать импульс новым идеям в области сетевого информационного поиска.
Авторы:
Дмитрий Владимирович ЛАНДЭ
Доктор технических наук, заместитель директора Информационного центра "ЭЛВИСТИ", профессор Института специальной связи и защиты информации Национального технического университета Украины "Киевский политехнический институт". Область научных интересов: теория информационного поиска, компьютерная лингвистика, методы детерминированного хаоса в информационных потоках, исследование сложных сетей. Автор монографий "Моделирование информационно-электоральных процессов" (Академия правовых наук Украины, 2007), "Поиск знаний в Internet" (Диалектика-Вильямс, 2005).
Андрей Александрович СНАРСКИЙ
Доктор физико-математических наук, профессор кафедры общей и теоретической физики физико-математического факультета Национального технического университета Украины "Киевский политехнический институт". Область научных интересов: термоэлектрические явления в анизотропных и неоднородных средах, теория протекания, методы детерминированного хаоса в информационных потоках, магнитная дефектоскопия. Автор монографий "Введение в нелинейную динамику. Хаос и фракталы" (2-е изд., URSS, 2007), "Процессы переноса в макроскопических неупорядоченных средах", 2007.
Игорь Васильевич БЕЗСУДНОВ
Заместитель директора Научно-производственного предприятия "Наука-Сервис". Область научных интересов: явления в средах с перколяцией, самоорганизованная критичность, математическое и компьютерное моделирование систем с протеканием, методы определения примесей драгметаллов и ртути в объектах окружающей среды. Автор нескольких изобретений, а также монографии "Процессы переноса в макроскопических неупорядоченных средах", 2007.
Знаете ли Вы, что, как не тужатся релятивисты, CMB (космическое микроволновое излучение) - прямое доказательство существования эфира, системы абсолютного отсчета в космосе, и, следовательно, опровержение Пуанкаре-эйнштейновского релятивизма, утверждающего, что все ИСО равноправны, а эфира нет. Это фоновое излучение пространства имеет свою абсолютную систему отсчета, а значит никакого релятивизма быть не может. Подробнее читайте в FAQ по эфирной физике.
