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

005059453

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

ПОЛЯКОВ ДМИТРИЙ ВАДИМОВИЧ

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ ЭФФЕКТИВНОГО ПОИСКА ТЕКСТОВОЙ ИНФОРМАЦИИ НА ОСНОВЕ КЛАСТЕРИЗАЦИИ ПО НЕЧЕТКИМ КОЛЛОКАЦИЯМ

Специальность 05.13.17 Теоретические основы информатики

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

1 6 МАП 2013

ТАМБОВ 2013

005059453

Диссертационная работа выполнена на кафедре «Информационные системы и защита информации» федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Тамбовский государственный технический университет» (ФГБОУ ВПО «ТГТУ»),

Научный руководитель Громов Юрий Юрьевич,

доктор технических наук, профессор

Официальные оппоненты: Панкин Олег Викторович,

доктор технических наук, доцент, Воронежский институт правительственной связи (филиал) ГКОУ ВПО Академии ФСО России, начальник кафедры общепрофессиональных дисциплин

Меньших Валерий Владимирович,

доктор физико-математических наук, профессор, федеральное государственное казенное образовательное учреждение высшего профессионального образования «Воронежский институт МВД России», начальник кафедры высшей математики

Ведущая организация ФГБОУ ВПО «Воронежский государственный

технический университет»

Защита диссертации состоится 10 июня 2013 г. в 15.00 часов на заседании диссертационного совета Д.212.038.24 в ауд. 226 ФГБОУ ВПО «Воронежский государственный университет» по адресу: 394006, Россия, г. Воронеж, Университетская пл., 1.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Воронежский государственный университет».

Автореферат разослан 29 апреля 2013 г.

Ученый секретарь

диссертационного совета Чеботарев Андрей Сергеевич

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

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

Степень разработанности темы исследовании. Основные модели информационного поиска представлены в работах Э.Э. Гасанова, В.Б. Кудрявцева, A.A. Санарского, И.В. Безсудова, Г. Солтона, Э.А. Фокса, Г. Ву, С.Э. Робертсона, К. Спарк-Джонса, М.В. Бэрри, Е.В. Ягуновой, JI.M. Пи-воваровой.

Эффективность информационного поиска оценивается множеством метрик или характеристик, с большой частью которых можно ознакомиться в серии документов «Официальные метрики РОМИП». Основными характеристиками информационного поиска являются полнота и точность. Под эффективностью информационного поиска в дальнейшем будем понимать именно эти его характеристики. Естественно, полнота и точность конкретного информационного поиска являются случайными величинами, для оценки которых используются средние значения. Максимальные значения полноты и точности, равные 1, характеризуют идеальный поиск, но на современном этапе не удается достичь одновременно высоких значений обеих характеристик. Так, например, в своей книге «Интернетика» Д.В. Ландэ приводит следующие данные по работе современных информационно-поисковых машин (ИПМ): для значений полноты информационного поиска от 0,6 до 0,7 средняя его точность равна 0,75, а для значений полноты от 0,8 до 0,9 точность поиска достигает всего 0,27. При этом точность, близкая к 1, достигается лишь при полноте 0,4 и менее.

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

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

Большой объем семантической информации скрыт в коллокациях -группах термов (слов), расположенных относительно друг друга в опреде-

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

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

Объект исследования: модели и алгоритмы анализа текста.

Предмет исследования: математическая модель оптимизации запроса и алгоритм кластеризации текстовой информации.

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

• анализ и синтез математической модели параметрической оптимизации запроса;

• построение векторно-пространственной модели текстового документа на основе нечеткого представления коллокаций;

• разработка алгоритма кластеризации информационного массива, на основе построенной векторно-пространственной модели;

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

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

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

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

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

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

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

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

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

Основные результаты работы представлены и обсуждены на IV Межвузовской научно-практической конференции «Новые технологии и инновационные разработки», проходившей в Тамбовском государственном техническом университете в 2011 г., XI Международной научно-методической конференции «Информатика: проблемы, методология, технологии», проходившей 10-11 февраля в Воронежском государственном университете, Международной научно-практической конференции «Техника и безопасность объектов уголовно-исполнительной системы - 2011», проходившей в Воронежском институте ФСИН России в 2011 г., УШ Всероссийской научно-практической конференции «Математические методы и информационно-технические средства», проходившей 22-23 июня в Краснодарском университете МВД России. Кроме того, результаты диссертационного исследования представлены на Всероссийском конкурсе научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий, проходившем в Белгородском государственном университете в 2011 г. В этом же году получен грант на основе результатов диссертационной работы по программе «Участник молодежного научно-инновационного конкурса» («У.М.Н.И.К.»). В 2012 г. по результатам диссертационного исследования направлена заявка под номером 13-07-00182 на конкурс инициативных научно-исследовательских проектов по программе РФФИ.

Внедрение результатов исследования. Основные положения диссертационной работы использованы при обучении студентов кафедры «Информационные системы и защита информации» на факультете «Информационные технологии» ФГБОУ ВПО «ТГТУ». Результаты диссертационной работы приняты к внедрению в 1084-м межвидовом центре подготовки и боевого применения войск РЭБ, на кафедре «Информационные

системы и защита информации» ФГБОУ ВПО «ТГТУ», в ООО «СОВ-ТЕХ» и ООО «КОНУС-ИТ», что подтверждено актами о внедрении результатов исследований.

Публикации. По теме диссертации опубликовано 25 работ, из них 15 статей, в том числе 6 статей в изданиях, рекомендованных ВАК РФ, 9 статей в рецензируемых изданиях, и 10 тезисов докладов на всероссийских и международных научных конференциях.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка использованных источников, содержащего 153 наименования, и приложений. Общий объем диссертации составляет 139 страниц, из них список использованных источников - 12 страниц. Основной текст работы содержит 27 рисунков и 14 таблиц. Работа соответствует п. 5. «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений» Паспорта специальности 05.13.17 - Теоретические основы информатики.

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

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

В главе 1 «Анализ решений задач поиска и кластеризации сведений» представлены результаты исследования моделей информационного поиска, классификации и кластеризации информационных массивов.

В процессе исследования выявлены основные характеристики информационного поиска: точность и полнота. Рассмотрены булева, нечеткая, векторно-пространственная и вероятностная модели поиска текстовой информации. Исследованы элементы Text Mining. В рамках данной концепции особое внимание уделено задачам извлечения понятий, определения взаимосвязей между понятиями, выявления новых событий, автоматического реферирования и создания поисковых образов документов на основе работ М.В. Бэрри, У. Файярда, П. Смита, У. Хана, И. Мани,

A. Бордера, С. Ильинского, М. Кузьмина, А. Мелокого, У. Манберра, Б. Краснова, В. Иванова, Д. Мангейма, Р. Рича и др.

Для улучшения точности и полноты информационного поиска часто используются алгоритмы группировки текстовой информации. Поэтому были исследованы различные модели классификации и кластеризации по работам ВН. Вапника, Й. Хирша, Д.В. Ландэ, И.Д. Мавделя, С.А. Айвазяна,

B.М. Бухштабера, И.С. Енюкова, Л.Д. Мешалкина, О. Замира, А.М. Андреева, Д.В. Березкина, K.M. Кириченко, М.Б. Герасимова, A.A. Афонина, М.Г. Крейнеса и др.

По результатам исследования предложен вариант классификации алгоритмов кластеризации, представленный на рис. 1.

Сплошными линиями на рис. 1 обозначены классы алгоритмов кластеризации, а пунктирными - примеры алгоритмов кластеризации информационных массивов.

Рис. 1. Рассматриваемая классификация алгоритмов кластеризации информационных массивов

Особое внимание было уделено моделям кластеризации на основе коллокаций, так как в них скрывается большой объем семантической информации текстов. Данный подход представлен в работах М. Михайлова, А.Б. Кутузова, O.A. Невзорова, В.А. Капустина, A.A. Ямсена, JT.M. Пиво-варовой, Е.В. Ягуновой, В.П. Захарова, М.В. Хохлова, Р.К. Бишта, Г.С. Дами, И.П. Кривенко, где он сводится к рассмотрению пар слов, встречающихся непосредственно рядом друг с другом, в то время как фактически на семантику текста влияют группы из двух, трех и более слов, встречающихся на некотором расстоянии друг от друга. Для повышения точности модели текстовых документов в диссертационной работе предложено расширить понятие коллокации до произвольного числа слов, находящихся на некотором расстоянии друг от друга. Под расстоянием между двумя словами в тексте понимается число слов между ними. Для формализации расстояний между термами в документах предложено воспользоваться теорией нечетких множеств.

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

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

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

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

Обобщенная схема использования базы знаний в разрабатываемой МИС представлена на рис. 2, где ИПМ - информационно-поисковая машина.

Рис. 2. Обобщенная схема использования базы знаний в МИС

Для построения модели базы знаний МИС и векторно-простран-ственной модели текстовых документов в диссертации были рассмотрены следующие множества:

£) - множество документов, проиндексированных ИПМ, представим О в виде: О = {йъй2, ..., с1ы), |0| = ./V, где ф - некоторый документ, 1 < г < ¿V;

и о — множество всех подмножеств Л;

В={0, 1};

2- множество целых неотрицательных чисел (/V - множество натуральных чисел, N = Z+/{0});

5 — множество всех термов(лемматизированных значимых слов), используемых в документах множества Б, Б = {¿ь ,у2, ..-, .?„(, = п.

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

Было принято обозначение .ур, ле 5, ре В,

\5,р = 0.

Введено в рассмотрение понятие элементарного запроса д :

(1)

[кМ;2 і]<",

(2)

е 1 <;)<п, 7=1,;, 1 е {1е N | 1<1_шах}, где /_тах - некоторое натуральное число, ограничивающее размер элементов д*. Введено определение: выражение

Г*,]*?'2 [*д]... * <1,(1*0 (3)

означает, что = ^ при рц = 1 ¿,8 Ф ^ при р^ — 0) верно,

что если пронумеровать все слова документа сі таким образом, что данный терм (л') будет иметь номер «0», номера рядом стоящих слов будут различаться на единицу, т.е. слова будут пронумерованы подряд, начиная с я,

__7-і

то У/ = 2,1 слово, имеющее номер У^/с, при условии, что рі = 1 (рі. =0)

1=1 ' 1

является (не является) термом 5. .

і

Таким образом, число к] задает расстояние (число слов) между термами с номерами (} и г}+1 в коллокации (1 <г} < п). Например, если 1 = 2, = «руководитель», а ^ = «предприятия», то [2]і,-2 є сі, сі є О , означает, что в документе <1 єсть фрагмент, в котором словоформа терма «предприятия» встречается ровно через два слова после появления словоформы терма «руководитель». Таким фрагментом может быть: «...руководитель строительного, проектно-изыскательского предприятия...» или «...нового руководителя торгового коммерческого предприятия...».

Множество <2 элементов вида (3) назовем множеством элементарных запросов на О.

В диссертации была введена алгебра <2 = <£),« л »,« V », «'» >. Рекурсивно с помощью выражения (3) для каждого документа сіє О задан предикат вида є сі на множестве элементов (?:

є^о є сі) л (с{1 є є ()УсІ є £>;

<7,. Vє сі о(<7, є <і)V(^ є сі),\/ді,д^£>Ус1є О;

дєсі <=> дє ^, \/дє (),УсІє О .

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

I = <2', г/в. Иея(.)>, (4)

где Кед: 2 —* ив, такое что Ксс](<7) = Д,, причем истинно условие: (Уеі є є ¿) а (Уй є О/О, )(<? Є , а 2' = {<? є Є | КеЯ(9) ^ 0}.

Модель (4) позволяет формализовать наиболее распространенные ИПМ, такие, например, как Гугл (google.com) или Яндекс (yandex.ru). С ее помощью была синтезирована математическая модель параметрической оптимизации запроса:

О =1^

а^тах

М<7)

сс(| |) + (1 - а(| І1ея(9) |)) (цА (<?) - п{\іА (0) + М п(цА (<?)))

I Кед(д) |

где (У ~ множество запросов к информационно-поисковой машине; —

отображение из множества запросов на множество текстовых документов, соответствующее работе информационно-поисковой машины; дл(су) — ожидаемое пользователем значение степени принадлежности некоторого документа й?, с1<= Д к множеству пертинентных сведений; |.| - операция взятия мощности множества; п(.) - операция отрицания; N - общее число документов информационного массива, на котором ведется поиск ИПМ; а(.) - функция, которая имеет вид:

О, х < а,

а(х):

-а ]1-у

Ь — а 1 ,х>Ъ,

,а<х<Ь, (6)

где а - количество документов в результатах информационного поиска, которое точно будет просмотрено пользователем; Ь - количество документов, которое пользователь физически не сможет просмотреть; у — степень важности точности поиска относительно полноты поиска для пользователя, уе [0; 1].

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

На основе построенной логико-лингвистической модели процесса формализации пертинентности была предложена формула вычисления |1Л (д):

^л (в) = ЛП ), ) )> ) , ) ), л( ),

(1(4*), \iiql) , ..., ц(9*)),оеЛГ, (7) где ^

<7 =л<?1 . V ¿72 . <7 ' <71* > <?2' Чо ). ое (8) + Ví?•,6 б* , (9)

где значение лингвистической переменной Ак, цЛ/(.) -Л1''; /Vм,

которое произвольному элементу [^г]^'3 [^з]—

ставит в соответствие вектор (к1г к2,..., /- аналитическое выражение, представляющее собой суперпозицию норм и отрицаний, примененную к функциям принадлежности, и аналогичную суперпозицию операций дизъюнкции и конъюнкции, примененных к элементарным запросам.

На основе математической модели параметрической оптимизации запроса предложена структура и объектно-ориентированная модель базы знаний МИС в виде семантической сети (рис. 3). Каждый узел данной сети соответствует некоторому запросу. Данная база позволяет найти оптимальный запрос в соответствии с моделью (4) - (6), а также определить

Father_Request

Request: *fuiher; int: KollRez; double: Tochnost: double: Polnota; d/>uble: FNorma:

XML: Req(); int: Norm(XML); void: F<); void: r{); On Eque Cliange();

Request (gj)

siring: type; Request: *soi

<y-

Koilocation (Лі)

h/Ktl: *st:

Simplc_Request: *falher: <R, Ац>: eque; Kollocation: *addr; Rw>h: *rool;

void: Ask_User(); voiil: 0>i£queChange(X

SimpleJtequest (gt )

int: *veetorN; koiloceititm *daughter;

void: [>'}:

Header ig0)

Request: MavRequest; Request: *M(txRecall\ Request: *MaxPiei:L\tim\ int: KoliQuest;

void: ManageiX void: OnEqueOiangeQ-, void: NewKiioltige0; void: NewQuesiionO',

Рнс. 3. Пример фрагмента структуры БЗ (слева) и диаграмма классов БЗ (справа)

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

В главе 3 «Математическая модель текстового документа и алгоритм кластеризации информационных массивов» для решения задачи автоматического пополнения знаниями разработанной базы с помощью кластеризации предложена модель текстовых документов на основе функции принадлежности (.). Данная функция формализует расстояние между термами произвольной коллокации /¡, (I - число термов в кол-локации) в некотором документе de О, т.е. \1(ин :[0, £_тах]'-1 [0; 1].

Пусть вектор К(кх, к2, ..., £м) - набор расстояний между термами в коллокации }ц. А множество {К,, К2, ..., Ки] - набор таких расстояний, встречающихся в документе й. Было предложено вычисление щ по формуле:

= ), (10)

i=l,M

где \ік. - функция принадлежности, являющаяся результатом фаззификации

набора расстояний Ки встретившегося в документе d для коллокации hi.

Это позволило построить нечеткую векторно-пространственную модель текстового документа d є D на основе нечеткого представления кол-

локаций. Поставим в соответствие каждой /і/ є H',l = l,/_max,i/ = l,At

<2 п

функцию пршшдлежности [0, к_шах]' 1 [0; 1], вычисляемую согласно формуле (10). Тогда документ d представим в виде:

Ш 1*11- M-I2- — М-1/.....Р.,

1 Ai

1> Hi

(П)

_ шах j

В соответствие произвольному множеству Б поставлена система векторов вида (11), как формализующая операцию «и» Г-норма к соответствующим функциям принадлежности.

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

I шах л

p(D„Ds)= X Z

/ л

J 4 s (*,-)-Ц?'(Xl)fdXl

. , ЧdeD

2

(12)

где D, и As - произвольные элементы множества UD. Показано, что функция (12) является метрикой, т.е. удовлетворяет аксиомам тождества, симметрии и треугольника.

Для разработки алгоритма кластеризации на основе нечетких коллокации информационных массивов на основании метрики (12) введено понятие характеристического параметра кластера |Х/г, означающее параметр некоторого кластера Ds, для которого минимальное расстояние между элементом, принадлежащим Ds, и документом вне кластера максимально. Построена и обоснована формула его выявления:

$ = arg шах— min p0(dnds) (13)

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

Приняв, что Г-норма формализует операцию «и», норма - «или», а п(.) - нечеткое отрицание, функция принадлежности элемента данному

кластеру (iDs имеет вид:

/

S

Kds^Ds

Формула (14) позволяет найти запрос, который должен будет наиболее точно соответствовать только элементам, принадлежащим Ds:

VDS=T

<?D, =D

s

ydseDs

(15>

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

б5= Яеч^), (16)

где 05 - кластер, сформированный на репрезентативной выборке, а 65 -соответствующий ему кластер, но уже на всей коллекции, что позволяет

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

Разбиение на классы К осуществляется с помощью агломеративного иерархического алгоритма кластеризации на основе метрики (12).

На основании предложенной нечеткой векторно-пространственной модели текстовых документов разработаны алгоритмы кластеризации информационных массивов /ШиЛ и Л^ен'Юм^?, представленные на рис. 4.

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

Рис. 4. Структурные схемы алгоритмов процедур №м>К1ия1

Рис. 5. Структурная схема алгоритма функции кластеризации коллекций

(КЪМег)

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

Рис. 6. Структурные схемы алгоритмов процедур формирования (слева) и кластеризации (справа) репрезентативной выборки

В диссертационной работе предложены функции, формализующие взятие Г,5-норм и операции отрицания («(.)):

Г(*,эО = лу,*,уе[0;1]; (17)

5(х,у) = *+у-ху,х,уе[0;1]; (18)

и(л) = 1-х,л,уе[0;1], (19)

а также функция принадлежности \1к{хьх2,..., , фаззифицирующая

наборы расстояний между термами вида К{ки к2,..., А."м):

\1К(х1,х2,..., =

/-1 п

1

¿-і

\ЬєВ1~1 І=1 7=1

(УЛ^Дз, ...Дн)є В )(Уі = 1,/—!)(&,■ — Я.,- <х, <¿,->.,+1),

(20)

0,(ЗЛа,Я2, ...Дм)є 5м)(3/ = 1,/-1)((д-, <ki-X¡)v(x¡ >к,-!,+]).

Для функции (20) было обосновано ее использование в качестве функции фаззификации в силу возможности аналитического интегриро-

вания при расчете метрики (12), а также простоты обработки многократного применения нечетких операций (17 - 19) к функциям вида (20) в информационных системах.

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

и величина выборки, равная а/л . Тогда сложность алгоритма кластеризации, формализуемого процедурой ИКкш, равна О(п).

Этот уровень сложности является допустимым, так как он оценивает сложность вычислений некоторых современных известных метапоиско-вых систем, например системы Нигма (nigma.ru).

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

Как видно из рис. 7, при больших значениях полноты (выше 0,8) на заданном наборе документов, состоящем из научных и учебно-методических работ в области информационных технологий, предложенные алгоритмы позволяют существенно (до 30%) повысить эффективность информационного поиска в сравнении с современными ИПМ.

Полнота

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

В заключении сформулированы основные результаты работы.

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

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

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

• Проведена оценка эффективности полученных в ходе исследования моделей и алгоритмов, позволяющая говорить как минимум о некоторых условиях, в которых предложенные алгоритмы позволяют существенно повысить эффективность поиска, а именно: увеличить точность на величину от 10% до 30% при потребной полноте более 0,8.

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК РФ

1. Кластеризация текстовых коллекций на основе нечеткого описания коллокаций / О.Г. Иванова, Д.В. Поляков, АЛО. Громова, В.Е. Дидрих// Информация и безопасность. - Воронеж : Издательско-полиграфический центр Воронежского государственного университета, 2011. - № 3 - С. 459 - 462.

2. Выбор архимедовых норм и конорм на основе использования рядов Фурье / Ю.Ю. Громов, Д.В. Поляков, О.Г. Иванова, Ю.В. Минин // Приборы и системы. Управление, контроль, диагностика. - 2012. - № 3 - С. 3-А.

3. Определение пертинентности результатов запроса с использованием нечеткой логики / Д.В. Поляков, Ю.В. Минин, В.Е. Подольский, А.Ю. Громова // Приборы и системы. Управление, контроль, диагностика. - 2012. - № 3 -С. 29-33.

4. Формализация информационной потребности пользователя на основе нечеткой логики / Д.В. Поляков и др. // Приборы и системы. Управление, контроль, диагностика. - 2012. - № 3. - С. 47 - 50.

5. Формализация информационной потребности с помощью коллокаций на основе теории нечетких множеств для пертинентного поиска текстовых сведений / Ю.Ю. Громов, Д.В. Поляков, Х.Д. Лыонг, А.Б.М.П.Б. Шихук II Информация и безопасность. - Воронеж : Издательско-полиграфический центр Воронежского государственного университета, 2012. - Т. 15, № 2. - С. 213 - 218.

6. Построение многомерных функций принадлежности / Ю.Ю. Громов, Д.В. Поляков, А.П. Ведерникова и др. // Приборы и системы. Управление, контроль, диагностика. - 2012. - № 11. - С. 21 - 26.

Статьи и материалы конференций

1. Поляков, Д.В. Алгоритм поиска идентичных объектов на непрерывном множестве / Д.В. Поляков // Методы управления потоками в транспортных системах : сб. статей. - М.: Изд-во: МАДИ, 2009. - С. 114 - 121.

2. Поляков, Д.В. Модель системы поиска и кластеризации сведений в сети Интернет с использованием существующих информационно-поисковых машин / Д.В. Поляков // Методы управления потоками в транспортных системах : сб. статей. - М.: Изд-во: МАДИ, 2009. - С. 122 - 129.

3. Кластеризация сведений на основе нечеткого представления взаимного расположения термов в документах / Д.В. Поляков, М.П. Аль-Балуши, М. Ауад, Х.Д. Лыонг // Методы управления потоками в транспортных системах : сб. статей. -М.: Изд-во: МАДИ, 2010. - С. 107 - 115.

4. Модель информационной системы метапоиска и мониторинга сведений в сети Интернет / Д.В. Поляков, М.П. Аль-Балуши, М. Ауад, Х.Д. Лыонг // Методы управления потоками в транспортных системах : сб. статей. - М. : Изд-во: МАДИ, 2010.-С. 116-124.

5. Нечеткий подход к описанию информационной потребности пользователя / Д.В. Поляков, М.П. Аль-Балуши, М. Ауад, Х.Д. Лыонг // Методы управления потоками в транспортных системах : сб. статей. - М. : Изд-во: МАДИ, 2010. -С. 124-134.

6. Определение соответствия результатов поиска информационной потребности пользователя / Д.В. Поляков, М.П. Аль-Балуши, М. Ауад, Х.Д. Лыонг // Методы управления потоками в транспортных системах : сб. статей. - М : Изд-во' МАДИ, 2010. - С. 134- 145.

7. К вопросу о генерации непрерывно дифференцируемых архимедовых Т- и 8-норм / Ю.Ю. Громов, Д.В. Поляков, О.Г. Иванова, В.Е. Дидрих // Вестник Воронежского института ФСИН России. - Воронеж : ООО ИПЦ «Научная книга», 20И.-№ 1.-С. 50-52.

8. Нечеткий подход к описанию информационной потребности пользователя для поиска и кластеризации сведений в сети Интернет / Ю.Ю. Громов, Д.В. Поляков, О.Г. Иванова, В.Е. Дидрих // Вестник Воронежского института ФСИН России. - Воронеж : ООО ИПЦ «Научная книга», 2011. - № 2. - С. 78 - 82.

9. Нечеткий подход к определению пертинентности результатов поиска и выбору оптимального запроса / Ю.Ю. Громов, Д.В. Поляков, О.Г. Иванова,

B.Е. Дидрих // Вестник Воронежского института ФСИН России. - Воронеж : ООО ИПЦ «Научная книга», 2011. - № 2. - С. 49 - 55.

10. Поляков, Д.В. Принципы построения системы метапоиска и мониторинга сведений в сети Интернет / Д.В. Поляков // Информатика: проблемы, методология, технологии : материалы XI Международной научно-методической конференции. -Воронеж : Издательско-полиграфический центр ВГУ, 2011. - Т. 2. - С. 190 - 192.

11. Поляков, Д.В. К вопросу о построении информационной системы метапоиска и мониторинга сведений в сети Интернет на основе нечеткого представления коллокаций / Д.В. Поляков // Сборник научных работ Всероссийского конкурса научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий. - Белгород : БелГУ, 2011 - Т. 1. - С. 419 - 424.

12. Поляков, Д.В. Информационная система метапоиска и мониторинга сведений в сети Интернет на основе нечеткого представления коллокаций / Д.В. Поляков // Новые технологии и инновационные разработки : материалы IV Межвузовской научно-практической ежегодной конференции. - Тамбов : ТГТУ, 2011. -

C. 73-75.

13. Подход к определению меры количества и качества информации на основе теории нечетких множеств / Ю.Ю. Громов, О.Г. Иванова, А.Ю. Громова, Д.В. Поляков // Техника и безопасность объектов уголовно-исполнительной системы - 2011 / ФКОУ ВПО Воронежский институт ФСИН России. - Воронеж : ИПЦ «Научная книга», 2011. - Т. 1. - С. 183 - 187.

14. Использование математического аппарата нечеткой логики для определения пертинентности результатов поиска текстовых сведений / Д.В. Поляков, М.П. Аль-Балуши, М. Ауад, Х.Д. Лыонг // Математические методы и информационно-технические средства : труды УШ Всероссийской научно-практической конференции. - Краснодар : Краснодарский университет МВД России, 2012. -С. 163.

15. К вопросу построения математической модели кластеризации текстовых сведений / Д.В. Поляков, В.В. Самойлов, М.П. Аль-Балуши, Х.Д. Лыонг // Математические методы и информационно-технические средства : труды VIII Всероссийской научно-практической конференции. - Краснодар : Краснодарский университет МВД России, 2012. - С. 164.

16. Подход к генерации Т, S-норм на основе рядов Фуръе / Д.В. Поляков, Л.В. Пучков, М.П. Аль-Балуши, М. Ауад // Математические методы и информационно-технические средства : труды УШ Всероссийской научно-практической конференции. - Краснодар : Краснодарский университет МВД России, 2012. - С. 165.

17. Метод фаззификации векторов в я-мертгом пространстве / Д.В. Поляков, Л.В. Пучков, В.В. Самойлов, Т.О. Авдеева // Математические методы и информационно-технические средства : труды VIII Всероссийской научно-практической конференции. - Краснодар : Краснодарский университет МВД России, 2012. - С. 166.

18. Построение пертинентного запроса к информационно-поисковой машине на основе математического аппарата нечеткой логики / Д.В. Поляков, В.В. Самойлов, М. Ауад, Х.Д. Лыонг // Математические методы и информационно-технические средства : труды VIII Всероссийской научно-практической конференции. - Краснодар : Краснодарский университет МВД России, 2012. - С. 167.

19. Определение целевой функции поиска текстовых сведений в сети Интернет / Д.В. Поляков, М.П. Аль-Балуши, М. Ауад, Х.Д. Лыонг // Математические методы и информационно-технические средства : труды VIII Всероссийской научно-практической конференции. - Краснодар : Краснодарский университет МВД России, 2012.-С. 168.

Подписано в печать 25.04.2013. Формат 60x 84/16. 0,93 усл. печ. л. Тираж 100 экз. Заказ № 214

Издательско-полиграфический центр ФГБОУ ВПО «ТГТУ» 392000, г. Тамбов, ул. Советская, д. 106, к. 14

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тамбовский государственный технический университет»

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

04201358275

ПОЛЯКОВ ДМИТРИЙ ВАДИМОВИЧ

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ ЭФФЕКТИВНОГО ПОИСКА ТЕКСТОВОЙ ИНФОРМАЦИИ НА ОСНОВЕ КЛАСТЕРИЗАЦИИ

ПО НЕЧЁТКИМ КОЛЛОКАЦИЯМ

Специальность 05.13.17 Теоретические основы информатики

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

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

ТАМБОВ 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..........................................................................................................................4

ГЛАВА 1. АНАЛИЗ РЕШЕНИЙ ЗАДАЧ ПОИСКА И КЛАСТЕРИЗАЦИИ

СВЕДЕНИЙ........................................................................................................................11

1Л Основные направления развития теории информационного поиска.....................11

1.2 Математические модели и алгоритмы поиска текстовой информации.................12

1.3 Характеристики и критерии оценки информационного поиска.............................21

1.4 Постановка задачи кластеризации и подходы к её решению.................................25

1.5 Исследование существующих алгоритмов кластеризации информационных массивов..............................................................................................................................28

1.6 Выводы по первой главе.............................................................................................36

ГЛАВА 2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ МЕТАПОИСКА НА ОСНОВЕ ПАРАМЕТРИЧЕСКОЙ ОПТИМИЗАЦИИ ЗАПРОСА.................................................39

2.1 Общие подходы к организации метапоиска текстовых сведений..........................39

2.2 Математическая модель информационно-поисковой машины..............................41

2.3 Математическая модель параметрической оптимизации запроса..........................49

2.4 Формализация информационной потребности пользователя.................................55

2.5 Структура базы знаний для решения задачи параметрической оптимизации запроса.................................................................................................................................67

2.6 Алгоритмы параметрической оптимизации запроса и наполнения базы знаний. 71

2.7 Выводы..........................................................................................................................76

ГЛАВА 3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ТЕКСТОВОГО ДОКУМЕНТА И АЛГОРИТМ КЛАСТЕРИЗАЦИИ ИНФОРМАЦИОННЫХ МАССИВОВ.................77

3.1 Математическая модель текстового документа на основе нечёткого представления расстояний между термами в коллокации............................................77

3.2 Метрика на пространстве текстовых документов и их групп.................................80

3.3 Математическая модель кластеризации информационного массива по нечётким коллокациям.......................................................................................................................84

3.4 Алгоритм кластеризации информационного массива по нечётким коллокациям 89

3.5 Разработка алгоритмов фаззификации и дефаззификации. Выбор Т,8 - норм.....94

3.6 Оценка сложности и эффективности разработанных алгоритмов кластеризации

информаци ионных массивов.........................................................................................114

3.7 Выводы........................................................................................................................120

ЗАКЛЮЧЕНИЕ................................................................................................................122

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ......................................................124

ПРИЛОЖЕНИЕ А. ОПИСАНИЕ РАЗРАБОТАННЫХ ФУНКЦИЙ БАЗЫ

ЗНАНИЙ...........................................................................................................................138

ПРИЛОЖЕНИЕ Б. ВИД ФУНКЦИИ ПРИНАДЛЕЖНОСТИ ДЛЯ Ь РАВНОГО

2 И 3...................................................................................................................................141

ПРИЛОЖЕНИЕ В. КОПИИ АКТОВ О РЕАЛИЗАЦИИ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИЯ..........................................................................................................144

ВВЕДЕНИЕ

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

Степень разработанности темы исследования. Основные модели информационного поиска представлены в работах Э.Э. Гасанова, В.Б. Кудрявцева, A.A. Санарского, И.В. Безсудова, Г. Солтона, Э.А. Фокса, Г. Ву, С.Э. Робертсона, К. Спарк-Джонса, М.В. Бэрри, Е.В. Ягуновой, JI.M. Пивоваровой.

Эффективность информационного поиска оценивается множеством метрик или характеристик, с большой частью которых можно ознакомиться в серии документов «Официальные метрики РОМИП». Основными характеристиками информационного поиска являются полнота и точность. Под эффективностью информационного поиска в дальнейшем будем понимать именно эти его характеристики. Естественно, полнота и точность конкретного информационного поиска являются случайными величинами, для оценки которых используются средние значения. Максимальные значения полноты и точности, равные 1, характеризуют идеальный поиск, но на современном этапе не удается достичь одновременно высоких значений обеих характеристик. Так, например, в своей книге «Интернетика» Д.В. Ландэ приводит следующие данные по работе современных информационно-поисковых машин (ИПМ): для значений полноты информационного поиска от 0,6 до 0,7 средняя его точность равна 0,75, а для

значений полноты от 0,8 до 0,9 точность поиска достигает всего 0,27. При этом точность, близкая к 1, достигается лишь при полноте 0,4 и менее.

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

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

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

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

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

Цели и задачи. Целью исследования являлось повышение эффективности анализа текста на основе оптимизации запроса с помощью кластеризации по / нечетким коллокациям. Для достижения цели были решены следующие задачи:

• анализ и синтез математической модели параметрической оптимизации запроса;

• построение векторно-пространственной модели текстового документа на основе нечеткого представления коллокаций;

• разработка алгоритма кластеризации информационного массива, на основе построенной векторно-пространственной модели;

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

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

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

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

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

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

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

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

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

Основные результаты работы представлены и обсуждены на IV Межвузовской научно-практической конференции «Новые технологии и инновационные разработки», проходившей в Тамбовском государственном техническом университете в 2011 г., XI Международной научно-методической конференции «Информатика: проблемы, методология, технологии», проходившей 10-11 февраля в Воронежском государственном университете, Международной научно-практической конференции «Техника и безопасность объектов уголовно-исполнительной системы - 2011», проходившей в Воронежском институте ФСИН России в 2011 г., VIII Всероссийской научно-практической конференции «Математические методы и информационно-технические средства», проходившей 22-23 июня в Краснодарском университете МВД России. Кроме того, результаты диссертационного исследования представлены на Всероссийском конкурсе научно-исследовательских работ студентов и аспирантов в области информатики

и информационных технологий, проходившем в Белгородском государственном университете в 2011 г. В этом же году получен грант на основе результатов диссертационной работы по программе «Участник молодежного научно-инновационного конкурса» («У.М.Н.И.К.»). В 2012 г. по результатам диссертационного исследования направлена заявка под номером 13-07-00182 на конкурс инициативных научно-исследовательских проектов по программе РФФИ.

Внедрение результатов исследования. Основные положения диссертационной работы использованы при обучении студентов кафедры «Информационные системы и защита информации» на факультете «Информационные технологии» ФГБОУ ВПО «ТГТУ». Результаты диссертационной работы приняты к внедрению в 1084-м межвидовом центре подготовки и боевого применения войск РЭБ, на кафедре «Информационные системы и защита информации» ФГБОУ ВПО «ТГТУ», в ООО «СОВТЕХ» и ООО «КОНУС-ИТ», что подтверждено актами о внедрении результатов исследований, копии которых представлены в ПРИЛОЖЕНИИ В.

Публикации. По теме диссертации опубликовано 25 работ, из них 15 статей, в том числе 6 статей в изданиях, рекомендованных ВАК РФ, 9 статей в рецензируемых изданиях, и 10 тезисов докладов на всероссийских и международных научных конференциях.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка использованных источников, содержащего 153 наименования, и приложений. Общий объем диссертации составляет 139 страниц, из них список использованных источников - 12 страниц. Основной текст работы содержит 27 рисунков и 14 таблиц. Работа соответствует п. 5. «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений» Паспорта специальности 05.13.17 - Теоретические основы информатики.

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

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

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

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

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

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

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

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

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

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

Разработаны алгоритмы фаззификации и дефаззификации расстояний между термами в коллокациях. Выбраны Т,8-нормы, операция отрицания.

Проведена оценка эффективности полученных в ходе исследования моделей и алгоритмов.

В заключении кратко изложены основные результаты диссертационных исследований в виде выводов.

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

ГЛАВА 1. АНАЛИЗ РЕШЕНИЙ ЗАДАЧ ПОИСКА И КЛАСТЕРИЗАЦИИ СВЕДЕНИЙ

1.1 Основные направления развития теории информа