Software & Systems

Электронные документы (ЭД) занимают существенный объем в круговороте информационного обмена. Решение задач информационного поиска текстовых ЭД в современных условиях осложняется рядом проблем: неструктурированность информации, постоянный ее рост и дублирование, искажение информации в результате многократного цитирования, отсутствие эффективных механизмов подтверждения актуальности и достоверности информации, достижение оптимальных показателей информационного поиска, фрагментарность ЭД, решение вопросов безопасности ЭД, децентрализованный характер наполнения хранилищ ЭД, потребность в быстром и качественном поиске информации, необходимость производить тематический мониторинг ресурсов. Указанные проблемы решают автоматизированные системы специального класса – информационно-поисковые системы (ИПС). ИПС будем называть программно-аппаратный комплекс, обеспечивающий механизмы индексирования, хранения и поиска ЭД.

Индексирование документов является операцией, обеспечивающей возможности информационного поиска. В настоящее время наиболее популярными являются методы координатного (или векторного) индексирования (Мидоу Ч. Анализ информационно-поисковых систем. М.: Мир, 1970). Классическое описание процесса индексации включает операцию взвешивания (Солтон Дж. Динамические библиотечно-информационные системы. М.: Мир, 1978). Операция взвешивания терминов приписывает терминам некоторый вес, отражающий предполагаемую важность термина в документе или наборе документов. Существуют разнообразные алгоритмы получения числовой характеристики значимости термина, позволяющие автоматизировать операцию взвешивания.

Сравнительный анализ алгоритмов
взвешивания терминов

Алгоритмы абсолютных частотных мер. Первые серьезные работы по автоматическому анализу текста проводились в середине 50-х годов прошлого века Х.П. Луном. Лун впервые использовал абсолютные частотные меры: частота появления термина в документе и суммарная частота термина в наборе документов. Указанный метод основывается на простом приравнивании веса к его частоте появления в тексте: . Развитием частотного метода является метод вычисления нормализованной частоты (TF – term frequency), то есть .

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

Алгоритм «сигнал-шум». Еще одна группа параметров базируется на вычислениях соотношения «сигнал-шум», по аналогии с теорией передачи информации Шеннона: или , где – шум термина, рассчитываемый по формуле ;– сигнал термина, рассчитываемый по формуле .

Алгоритм распределения частоты термина. Еще один способ оценки значимости термина связан с величиной распределения частоты термина. Обозначим среднюю частоту термина k в n документах, тогда несмещенная выборочная оценка среднеквадратичного уклонения определяется:.

Подходящим параметром оценки пригодности некоторого термина служит отношение:.

Алгоритмы, основанные на способности термина различать документы набора. На практике было обнаружено, что полезными характеристиками обладают также параметры, основанные на способности термина различать документы набора.

Рассмотрим набор документов. Пусть s(Dⁱ, D^j) обозначает коэффициент подобия документов i и j. Если вычислить коэффициент s для всевозможных пар документов (Dⁱ, D^j), таких что ,то можно получить – среднее значение коэффициента попарного подобия документов данного набора, то есть, где c – некоторая постоянная. Для каждого термина k можно рассчитать дискриминантное значение. Если терминам приписать некоторые ранги в порядке уменьшения величины их дискриминантной (различительной) способности, то оказывается, что лучшие термины имеют средние значения частоты появления в документах, не слишком большие, не слишком малые и довольно асимметричные распределения частот.

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

Алгоритмы, использующие документообразующие признаки. Для более детального и тщательного наделения весами в литературе предлагается усиливать структуризацию текста с выделением документообразующих признаков: адресные реквизиты, автор, название, аннотация, оглавление, классификационный индекс, ссылки или список использованной литературы, приложения (Воробьев Г.Г. Документ: информационный анализ. М.: Наука, 1973). В работе В.О. Толчеева «Разработка и исследование новых модификаций метода ближайшего соседа» (Прилож. к журн. «Информационные технологии», №2, 2005) представлены результаты экспериментов данного утверждения и предлагается линейная формула определения веса ключевого слова по его появлению в названии, аннотации и теле документа:, где – соответственно частотный вес термина в названии, в аннотации и ключевых словах (теле) документа; – весовые коэффициенты. Использование такого документообразующего признака, как библиография позволяет строить семантические сети документов и их ключевых слов. Об алгоритмическом решении говорилось задолго до широкого использования технологии Web, но именно развитие Internet позволило применить новые средства оценки, кластеризации и построения сетей навигации по информационным ресурсам. Например, в Internet-поисковике Yandex используется так называемый индекс цитируемости, в Internet-поисковике Google – Page Rank.

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

Метод расчета нечеткого сбалансированного веса

Введем базовые переменные. Пусть D{d₁,..,d_n} – множество ЭД, на которых проводится эксперимент. Каждый документ обладает определенным набором термов T^1..n {t₁,...,t_m}, а {a₁,...,a_k} – множество алгоритмов взвешивания; W^1..n{w₁,...,w_k} – множество векторов весов для каждого документа. Каждый вектор w имеет размерность, равную числу термов конкретного документа. Результаты применения всех алгоритмов взвешивания нормализуются (например, к диапазону [1,100]). На основании результатов взвешивания можно принять решение, какой набор ключевых слов формирует тот или иной алгоритм взвешивания (например, к ключевым словам могут относиться термы, имеющие вес свыше 80). Далее проводится экспертная оценка и формируется W¢ – эталонный набор ключевых слов. Сравнение W и W¢ позволит определить расхождение и сформировать коэффициент доверия каждому алгоритму, который представляется в виде множества P {p₁,...,p_k}. Коэффициент доверия может представлять собой среднюю нормализованную оценку расхождения W и W¢ (например, 80 % соответствует коэффициенту 0,8). На коэффициент доверия может влиять не только процент неугаданных ключевых слов, но также процент предложенных алгоритмом взвешивания ошибочных ключевых слов. Для расчета нечеткого сбалансированного веса можно рассчитать общий балл терма: или среднего веса .

Полученный сбалансированный вес будет принадлежать диапазону [1..100].

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

Программная реализация индексации ЭД

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

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

Одним из этапов разработки ИСА ЭИР является разработка модуля индексирования, включающего операцию взвешивания. Первый этап разработки модуля «ИСА ЭИР: индексатор» реализован:

- спроектирована и реализована БД для хранения ЭД, результатов индексирования (нечетких частотных словарей);

- разработан программный модуль индексирования ЭД (форматы MS Word, RTF, TXT) и заполнения БД;

- расчет весов термов по формулам абсолютных и частных мер, формуле "сигнал-шум", формуле распределения частоты термина.

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