Содержание к диссертации
Введение
Глава 1. Алгоритмы информационного поиска 11
1.1 Основные задачи информационного поиска 11
1.2 Сравнение предложений 20
1.3 Логические методы отождествления 22
1.4 Выводы по главе 1 25
Глава 2. Разработка системы связей для тюркских языков 27
2.1 Морфология тюркских языков 30
2.2 Реализация алгоритмов выделения основ 39
2.3 Наиболее важные связи для тюркских языков 41
2.4 Выводы по главе 2 47
Глава 3. Определение тем текстов 49
3.1 Методы тематического анализа текстовой информации 50
3.2 Вычисление весов слов 52
3.3 Определение тем текстов и вычисление их важности 54
3.4 Процесс резюмирования 55
3.5 Выводы по главе 3 58
Глава 4. Программная реализация 60
4.1 Общие сведения 60
4.2 Реализация алгоритма отожествления 61
4.3 Построение графа для системы предложений 64
4.4 База данных 67
4.5 Результаты экспериментов 68
4.6 Выводы по главе 4 79
Заключение 81
Литература 84
Приложения 95
- Основные задачи информационного поиска
- Морфология тюркских языков
- Процесс резюмирования
- Результаты экспериментов
Основные задачи информационного поиска
Объемы обрабатываемой электронной информации нарастают по экспоненте. Этому способствует активное внедрение мультимедиа, широкое распространение корпоративных и глобальных сетей, уход большинства предприятий от бумажного документооборота и переход на автоматизированные системы управления предприятиями. В подобной ситуации резко возросла потребность в системах поиска и анализа данных. Традиционные системы поиска, развивающиеся в тесной взаимосвязи с СУБД, в основном ориентированы на работу со структурированными текстовыми данными и мало приспособлены для обработки мультимедийной и неструктурированной информации. По статистике, доля структурированных данных в современных архивах составляет не более 20%, остальные же 80% приходятся на долю различных документов, сканированных текстов и другой разрозненной информации [1]. Соответственно возникает проблема поиска и выборки необходимой информации из большого неструктурированного массива данных.
Другим фактором, стимулирующим развитие технологий поиска, является появление большого количества электронных библиотек, содержащих значительные объемы актуальных знаний. Производительность и эффективность любой подобной системы хранения информации напрямую зависит от эффективности и производительности поисковых систем. Именно поисковая система (ПС) определяет, превратятся ли в знания многочисленные разрозненные данные, поступающие по различным каналам связи и накапливаемые в разнообразных государственных, ведомственных, частных и прочих электронных архивах.
Самой распространенной задачей, ставящейся перед ПС, является задача поиска информации в предварительно проиндексированных полнотекстовых массивах данных. Это могут быть как данные на локальной машине, так и распределенные данные внутри Интранет/Интернет сетей. Подобная задача поиска стоит как перед поисковыми системами Интернет, так и перед специализированными средствами полнотекстового поиска. Выделяются следующие подзадачи: поиск по контексту, тематический поиск, построение карты знаний, авторубрикатор, поиск документов по отношению близости.
На сегодняшний день существует достаточно много интересных решений для улучшения характеристик поиска. Практически у каждой известной поисковой системы имеется своя реализация поиска и своя подборка нововведений, которые улучшают общие показатели поиска такие, как индекс цитирования в Яндекс, ранжирование в Google. Все эти решения широко распространены. Однако легко можно указать их основные недостатки: - поиск по ключевым словам дает слишком много ссылок, и многие из них оказываются бесполезными, отсутствует оценка связности слов в запросе;
- большое количество поисковых машин с разными пользовательскими интерфейсами порождает у пользователя проблему информационной перегрузки;
- методы индексирования баз данных, как правило, семантически слабо связаны с их информационным содержанием;
- неадекватные стратегии поддержки каталогов часто приводят к тому, что пользователю выдаются ссылки на информацию, которой уже нет в сети;
- поисковые машины еще не столь совершенны, чтобы понимать достаточно сложные конструкции естественного языка;
- по тому представлению результатов, которое обеспечивают современные поисковые машины, невозможно сделать логически обоснованный вывод о полезности источников;
- существующие решения для так называемого Semantic Web трудно сопрягаемы с другими формами хранения и поиска информации в условиях уже существующих объемов данных.
При разработке ПС, независимо от предполагаемой ее архитектуры, встают две основные проблемы, от эффективности решения которых, кардинально зависит качество создаваемой ПС:
- проблема эффективного семантического анализа текста документа для последующего его индексирования и определения соответствия его запросу пользователя;
- проблема организации эффективного поиска по базе индексов релевантных документов, отвечающих запросу пользователя.
Первая проблема подразумевает разработку алгоритмов обработки текстов документов для выделения значимых терминов, определяющих содержание документа, а также для определения весовых коэффициентов этих терминов. Данные термины и их веса используются при создании индекса документа - информации, в сжатом виде представляющей основной смысл документа. Решение второй проблемы сводится к разработке структуры хранения индексов документов, алгоритмов поиска по данной базе индексов и алгоритмов определения степени релевантности документа поисковому запросу. Поскольку основной лексической единицей текстового документа является слово или термин, существующие методы индексации базируются именно на терминах Основными и наиболее значимыми критериями, используемыми поисковыми системами для описания индексируемых терминов документа, являются следующие:
- степень присутствия в документе (частота появления);
- специфичность, определяется при уточнении смыслового значения и специфики термина;
- место присутствия в документе (находится в заголовке, подзаголовке, начале документа).
При составлении индекса обычно исключаются слова, несущие чисто грамматические функции, общеупотребительные слова, знаки препинания. Общеупотребительные слова встречаются в любом текстовом документе и слабо коррелированны с его тематикой. Это такие части речи как предлоги, союзы и т.д.
При разработке методов индексации необходимо учитывать проблему общности/специфичности. Общность индексации подразумевает составление индекса, максимально отражающего все аспекты содержания документа. Специфичность, наоборот, подразумевает выделение из документов только наиболее важных терминов. Общность и специфичность индексации напрямую связаны с общностью и точностью поиска.
Наиболее часто используется статистический метод индексации. Предположим, что имеется коллекция, состоящая из N документов. Определим функцию tft. как относительную частоту появления термина tt в документе d .: tftj =ntln, где nt - число встречаемости термина в документе, п - число всех терминов в документе.
Выделив множество часто встречающихся терминов, можно построить простейший индекс, содержащий значения функции tft. для каждого термина в документе. Такой метод индексации ориентирован на максимальную общность поиска, точность поиска при этом будет низкая. Усовершенствование этого метода можно произвести, введя веса терминов, характеризующие их специфичность.
Определим величину как количество документов в коллекции, содержащих термин tt. Тогда, величина log(—) именуемая инверсной частотой появления термина в документах, может служить величиной, характеризующей специфичность термина tt (чем меньшая доля документов содержит термин, тем больше ценность ti как термина, дискриминирующего документы определенного класса). Широко применяемый комбинированный метод индексации [7] определяет веса терминов как величину wt.
В зарубежной литературе такой метод обозначается как TF IDF метод. В соответствии с ним, наибольший вес имеют термины, которые встречаются достаточно часто, но при этом, сосредоточенные в небольшой доле документов коллекции.
Определение степени релевантности обрабатываемого документа сводится к определению степени соответствия запроса пользователя к текущему индексу. Для этого необходимо запрос пользователя привести к тому же виду что и индекс, т.е. для терминов запроса необходимо применить операцию приведения к канонической форме.
Для определения степени релевантности часто используют алгебраические методы, которые основаны на предположении, согласно которому множество документов коллекции может быть представлено набором векторов в векторном пространстве индексируемых терминов. При этом необходимо проводить нормализацию векторов. Нормализация несет дополнительную положительную роль. Она позволяет нормализовать документ относительно его размера. Без проведения нормализации документы, имеющие большой объем и, за счет этого, большие степени присутствия терминов в документе, получат преимущество перед малыми документами, реально имеющих большую плотность и состав полезных терминов в своем содержимом.
Запрос пользователя так же представляется в виде вектора в том же пространстве. Степень релевантности документа, т.е. его «похожесть» на вектор-запрос, вычисляется как некоторая мера расстояния между векторами запроса и документа
Морфология тюркских языков
Задаче полного автоматического морфологического анализа словоформ естественного языка посвящено множество теоретических исследований и практических разработок [30– 33]. В частности, такого рода исследования проводились в рамках работ по созданию автоматического перевода [29, 35, 36], информационно-поисковых систем [38, 39], орфографического контроля [40].
С точки зрения типов морфологической организации слов в естественных языках выделим флективность и агглютинацию [41–43].
Флективность характеризует отсутствием четких границ между морфами, а сами морфы могут иметь несколько различных грамматических значений. По сути, семантические и формальные границы между морфами в флективных языках плохо различимы.
Для слов флективных языков характерно, что корень слова несет главные лексико-грамматические значения. С одной стороны, в одном словоизменительном аффиксе могут содержаться различные грамматические категории (например, падеж и число в существительных русского языка). С другой – одно и то же грамматическое значение может формироваться различными аффиксами. Флективность языков характеризуется системой чередований, возникающих на стыках морфем.
Для агглютинативных языков (например, тюркских) характерна достаточно развитая система словообразовательной и словоизменительной аффиксации, грамматическая однозначность аффиксов, отсутствие чередований.
Агглютинация суть образование новых грамматических форм и слов посредством присоединения к основе слова аффиксов с четко выраженными свойствами таким образом, что границы морфов не изменяются. Каждый аффикс имеет единственное значение и каждая функция выражается одним определенным аффиксом. Явление агглютинации сводится к присвоению без изменения словообразующего суффикса к морфу базового слова. В этом случае каждый конкретный суффикс, каждый аффикс языка обладают конкретными семантическими, психолингвистическими значениями, функциями [43].
Особенности агглютинативных языков выделены в [44]:
- развитая система словоизменительных аффиксов, большинство из которых грамматически однозначны (т.е. одним аффиксом выражается один грамматический признак);
- единый тип словоизменения: отсутствие строгого разграничения между именным и глагольным типом словоизменения - склонением и спряжением (ср. флективные языки);
- отсутствие значимых морфонологических чередований в основах, четкая фонетическая обусловленность использования алломорфов.
Агглютинативная словоформа формируется присоединением к основе в указанном порядке однозначных стандартных аффиксов. При этом границы морфем должны быть отчетливы, фонетические изменения на стыках морфем подчиняться строгим правилам. Попытка построения словообразовательной парадигмы для конкретного слова сталкивается с использованием большого числа словоизменительных аффиксов и является чрезвычайно сложной. Возникает необходимость построения морфологического анализатора тюркских языков, учитываюших всевозможные допустимые комбинации морфем.
В задачах автоматического анализа текстов на естественном языке ключевой проблемой является морфологический анализ слов с целью получения знаний о нормальной форме слова и его парадигме, без которых невозможно осуществлять корректную индексацию и последующий поиск информации по построенному индексу, решать более сложные задачи искусственного интеллекта.
Морфологический анализ предназначен для решения двух основных задач (морфологического анализа и синтеза, соответственно):
- определения начальной формы слова по произвольной словоформе (и, желательно грамматических признаков словоформы);
- построения всех форм слова по начальной форме.
В настоящее время в системах анализа текста в русском языке используется различные морфологические анализаторы [27, 28]. При этом выделяют два принципиально различающихся подхода к морфологическому анализу: основанный на словарях и бессловарные морфологические анализаторы.
Наиболее полно задача морфологического анализа решается словарными анализаторами, позволяющими определять грамматические характеристики для словоупотреблений в текстах на естественных языках, без которых становится невозможно, например, проводение фрагментации текстов, выделение именных и предложных групп, однородных членов предложения.
Вместе с тем, методы морфологического анализа, основанные на использовании словарей, обладают одним главным недостатком. Если анализируемая словоформа отсутствует в словаре, то и получить какую-либо морфологическую информацию о ней невозможно. Учитывая, что неизменяемое лексическое ядро естественного языка составляет порядка 80% используемого в речи и письме словарного запаса [45], применение только словарных морфологических компьютерных моделей не решает проблему полноты определения всех возможных слов, встречаемых в текстах на естественном языке [46]. Ситуация осложняется при обработке текстов из сети Интернет.
В настоящее время аналитические методы выделения основы являются одной из основных компонент информационно-поисковых систем как общего, так и специального назначения. Они применимы для осуществления индексации и последующего поиска информации в информационно-поисковых системах [47-49], позволяя повысить полноту поиска и оптимизировать размер индекса информационно-поисковой системы. Кроме этого, алгоритмы аналитического выделения основы находят широкое применение в задачах классификации [50, 51], автоматического реферирования [52, 53] и других задачах автоматической обработки текстовой информации.
Аналитическим алгоритмом выделения основы называется процесс приведения словоформы, полученной от канонической формы слова в результате словоизменения или словообразования, к псевдооснове (аналогу корня слова). Важно отметить, что получаемая псевдооснова не обязана совпадать с грамматической основой рассматриваемой словоформы, но при этом достаточно, чтобы словоформы, соответствующие одной парадигме, получили в результате работы алгоритма одну и ту же псевдооснову.
Можно определить несколько типов алгоритмов аналитического выделения основы, различающихся по скорости обработки текстовой информации и качеству получаемых результатов. Они подразделяются на три больших класса:
- алгоритмы, основанные на отсечении аффиксов;
- статистические алгоритмы;
- смешанные алгоритмы.
Рассмотрим один из синтетических агглютативных языков, обладаюший богатой и сложной морфологией, турецкий язык. По своему морфологическому строю турецкий язык относится к агглютинативным языкам. Слова в нем обычно состоят из основы и добавляемых к ней аффиксов, которых бывает, по крайней мере, два или три. Алгоритм описан на основе работы [54].
Рассматриваемая морфологическая модель анализирует имена существительных, так как они составляют основную часть турецкого языка, а также глаголы с учетом словоизменения.
В турецком языке суффиксы можно разделить на две группы:
- суффиксы имен существительных;
- именные глагольные суффиксы.
Слова, оканчивающиеся на именные глагольные суффиксы, могут выступать в предложении в роли глаголов.
По своему морфологическому строю турецкий язык относится к агглютинативным языкам, в котором аффиксы имен существительных можно разделить на две группы:
- падежные аффиксы;
- аффиксы принадлежности.
При этом аффиксы глаголов можно разделить на три больших класса:
- аффиксы времени;
- аффиксы лица;
- аффиксы наклонения.
В турецком языке аффиксы добавляются к основе с помощью конечного числа правил, это позволяет представить морфологическую модель в виде конечного автомата. Состояние, помеченное символом «А», является стартовым. Терминальные состояния отмечены двойными окружностями. На дугах конечного автомата будем указывать номер суффикса (приведены далее в списках), который позволяет перейти из текущего состояния в следующее. В процессе работы автомата при достижении терминального состояния, осуществляется проверка, имеется ли переход из этого состояния, который можно осуществить при выполнении некоторого условия. Если переход совершить невозможно, то анализ словоформы завершается, иначе - происходит переход в следующее состояние.
Процесс резюмирования
Сначала в общих терминах опишем основную идею. На данной стадии рассматривается некоторый заранее заготовленный текстовый фрагмент Set,, точно относящийся к определенной теме. Фрагмент Set2 - анализируемый фрагмент. Он сопоставляется с фрагментом Set, на предмет соответствия той же теме. В нашем случае он представляет собой фрагмент, выделенный из исходного (большого) текста посредством кластеризации, как было описано в предыдущем разделе. Процесс сбора всех фрагментов, удовлетворяющих определенному критерию соответствия, и является, по сути дела, процессом резюмирования [96, 101].
Перейдем теперь к более детальному описанию алгоритма. Фрагменту Set, соответствует ориентированный граф G = (V,E). Пусть далее wi} - вес ребра (Гг,Г})еЕ, если таковое имеется, и м г] = 0 в противном случае. Рассмотрим неориентированный граф, ассоциированный с графом G естественным образом. Множество вершин то же самое. Ребра возникают посредством «забывания» об ориентации. Вес ребра в новом графе будет равен Lmk_Strengthl]=2xmm(wy,w]l). Большое значение данной величины означает, что данные два слова многократно встречаются рядом в двух вариантах. А именно, первое слово предшествует второму, и наоборот второе слово предшествует первому.
Далее вводим величину Path _Lengthy =11 Link_Lengthi}. То есть, осуществлен переход к обратным величинам. Таким образом получаем, что чем меньше Path _Lengthl}, тем более выражено упомянутое выше свойство, т. е. данные слова «очень связаны» между собой внутри данной темы.
Центральность по близости (Closeness centrality)
Центральность по близости обычно используется при изучении социальных сетей и является показателем, насколько быстро распространяется информация в сети от одного участника к остальным. В качестве меры расстояния между двумя участниками используется кратчайший путь по графу (геодезическое расстояние). Так, непосредственные друзья участника находятся на расстоянии 1, друзья друзей - на расстоянии 2, друзья друзей друзей - на расстоянии 3 и т. д. Далее берется сумма всех расстояний и нормируется. Полученная величина называется удаленностью вершины Vi от других вершин. Близость определяется как величина, обратная удаленности. где da(y t) - кратчайший путь от вершины Vt до вершины t.
Другими словами, центральность по близости позволяет понять, насколько близок рассматриваемый участник ко всем остальным участникам сети. Таким образом, важно не только наличие непосредственных друзей, но и чтобы у самих этих друзей тоже были друзья.
В нашем случае мы имеем дело с текстами, а не с социальными сетями. Но в обоих случаях используются теоретико-графовые конструкции. Поэтому, аналогично, можно вычислить центральность по близости для любой вершины в рассматриваемом неориентированном графе. При вычислении геодезического расстояния используются веса ребер Path _Length4 .
Переходим теперь к процессу сравнения двух фрагментов Set, и Set2. Продемонстрируем основную идею на примере. Предположим, что каждый из них состоит из трех предложений:
Каждому из текстовых фрагментам Set[ и Set 2 соответствует свой неориентированный граф. Заметим, что множество вершин у этих графов будет одно и то же, а именно {A,B,C,D,N}. Соответственно для всех вершин Vi можно вычислить центральность по близости в первом графе и во втором. Обозначим их Cc(Vi\ и Cc(Vi)2 соответственно.
Далее подсчитываем величину Diff(Vi) = (\Cc(Vi)2 -C Vi /C Vi), хЮО) . Она характеризует, насколько одинаково или различно употребление данного слова в контекстах первого и второго текстовых фрагментов. Далее устанавливаем порог, который служит критерием «одинаковости» употребления слова.
Например, в качестве порога можно взять медиану величин DiffiV , и далее этот порог можно использовать при анализе других фрагментов.
На финальной стадии подсчитывается, сколько слов «преодолели» порог по формуле: Score(Set, ,Set2) = (Countmatch {Set, ,Set2)l Count(Set,)) x 100;
Countmatch(Set„Set2) - количество всех слов из Set,, которые одновременно входят в Set, и Set2, и которые «преодолели» порог, т. е. прошли проверку на идентичность употребления в обоих текстовых фрагментах;
Count(Set,) - количество всех слов из Set,, которые подвергались анализу, т. е. просто одновременно входят в Set, и Set2.
Окончательный вывод делается по тому, насколько велико Score(Set„Set2), т. е. в конечном итоге и здесь эксперт выбирает соответствующий порог, позволяющий сделать вывод, что тема фрагмента Set2 соответствует теме эталонного текстового фрагмента Set1 .
Результаты экспериментов
Результаты тестовых испытаний с документами на русском языке
Исследуем текст, представляющий собой отрывок из романа Л.Толстого «Война и мир». Предварительно определим частоту встречаемости слов с использованием алгоритма ссылочного ранжирования в выбранном отрывке. К ключевым словам будут отнесы слова с наибольшим весом в соответствии с рисунком 10.
Приведем оценки близости между документами, указанными в таблице 8. Предварительно для каждого из них выделим ключевые слова и вычислим центральности. Мы заинтересованы в попарной оценке близости документов. Чем выше оценка, тем большее сходство найдено между документами. Результаты расчетов приведены в таблице 9.
Нетрудно видеть, что наиболее близкими являются документы 3 и 4, то есть наибольшее сходство наблюдается между Дж. Оруэлл «1984» и Дж. Стейнбек «Гроздья гнева» (отрывок).
Результаты тестовых испытаний с документами на английском языке.
Приведем оценки близости между документами.
Мы предлагаем алгоритм сравнения текстов (как последовательности предложений) и оценки их сходства. Метод применим только для предложениий, которые могут быть достаточно корректно проанализированны с помощью LGP. Предлагаемая мера учитывает лексические, синтаксические и семантические отношения между словами.
Объем словаря казахского и турецкого языка на данный момент составляет около 1000 слов и 100 аффиксов. Размер текстов на обоих языках для нашего эксперимента был 11-27 Кб.
Были получены следующие результаты сравнения текстов для казахского языкаВ результате тестов система отправляла запросы поисковой системе www.googleapis.com, от которой получала списки URL с их текстовым описанием. Каждому предоставленному текстовому описанию система давала оценку соответствия запросу. Программа оставляла релевантные ссылки, отбрасывая не релевантные по ее мнению. Эксперт произвел оценку полученных текстовых описаний, в результате чего были выявлены следующие результаты работы [110, 113, 116-118]:
В итоге выяснилось, что на проведенных тестах в среднем из 130 ссылок, полученных из поисковой системы, программа выделела 5-20 качественных релевантных ссылок, около 2 ссылок программа ошибочно принимала за релевантные и остальные отбрасывала как нерелевантные, что соответсвовало действительности. Это показывает, что система смогла произвести фильтрацию на хорошем уровне. Большое количество примеров тестирования приведено в конце диссертации (прил. А, Б).
Оценка качества информационного поиска
Точность (precision).
Определяется как отношение числа релевантных документов, найденных ИПС, к общему числу найденных документов:
Precision = rel retr
\Dretr\
Полнота (recall).
Отношение числа найденных релевантных документов, к общему числу релевантных документов:
Recall = rel retA
\DrA
Выпадение (fall-out).
Выпадение характеризует вероятность нахождения нерелевантного ресурса и определяется, как отношение числа найденных нерелевантных документов к общему числу нерелевантных документов:
Fall-out = nrel retr
V- nretr
В действительности, для оценки качества информационного поиска используются и другие характеристики. Можно указать по крайней мере 7 таких показателей. В наших примерах в cреднем получались следующие значения: Prec=0,75; Rec=0,89; Fall-out=0,25.