Интеллектуальный поиск Новиков Роман - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Английский роман 2-ой половины 19 века 1 37.41kb.
Школьный географический интеллектуальный марафон. Интеллектуальный... 1 100.7kb.
О представлении данных и знаний для интеллектуального анализа социологических... 1 247.25kb.
Учредитель и издатель зао «Роман-газета» 8 2657.61kb.
Информация о межвузовской научной студенческой конференции мнск-2012... 1 73.06kb.
Конт телефон Конференция «Интеллектуальный потенциал ученых России»... 1 54.55kb.
Исторический роман во Франции 1 75.58kb.
Вадим Леванов роман с онегиным 6 901.46kb.
Информационный поиск 1 126.38kb.
Практическое задание №1. Классификация информационно-поискового пространства... 1 110.7kb.
за роман «Мой лейтенант» Даниил Гранин стал лауреатом «Большой книги» 1 24.58kb.
Интернет – ресурсы для учителей изо 1 49.85kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Интеллектуальный поиск Новиков Роман - страница №1/1

Интеллектуальный поиск


Новиков Роман

Аннотация


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

This article is devoted to algorithms and approaches to creation of the intellectual search machines applying methods of a classification of documents are considered. Are subjected to the analysis as classical algorithms (Bayes algorithm and so forth), and likelihood and linguistic methods (algorithm PrTFIDF, algorithm with use of line kernels, Latent Semantic Indexing). During the analysis advantages and lacks of methods of intellectual search are revealed, and also the concept of creation of the search machine which application it is possible to illustrate on an example of the analysis of a news stream is offered.

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

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

Именно установление смысловых связей в базе поисковой машины является одним из важнейших пунктов в разработке интеллектуальной поисковой машины.

Цели и задачи проекта


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

Общий алгоритм разработки данной системы:



  1. Разработка концепции - общая философия работы системы;

  2. Разработка алгоритма индексации и категоризации документов;

  3. Разработка алгоритма нормализации запроса пользователя;

  4. Разработка алгоритмов итеративного обхода сайтов;

  5. Разработка системы сбора информации;

  6. Разработка системы выдачи результатов;

  7. Разработка базы данных поисковой системы, представления информации и информационных связей в ней.

Основные этапы разработки интеллектуальной машины

Концепция поисковой машины


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

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


Индексация документов


Этот пункт разработки тесно связан со структурой базы данных. В целях экономии дискового пространства поисковая машина может анализировать не весь документ, а лишь его контентые части, которые представляют наибольший интерес для пользователя. Выделение данных частей из документа – весьма важная часть алгоритма индексации. Далее контентная часть должна быть подвергнута нормализации и приведению к виду, в котором информация будет храниться в базе данных. Этот метод представления информации является наиболее распространенным и называется «Методом ключевых слов». Текст последовательно проходит ряд обработок, таких как:

  • Графематический анализ (выделение слов, цифровых комплексов, формул и т.д.);

  • Морфологический анализ (построение морфологической интерпретации слов входного текста);

  • Синтаксический анализ (построение дерева зависимостей всего предложения);

  • Семантический анализ (построение семантического графа текста).

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

  • Теряется информация о порядке слов;

  • Потеря контекста, а вероятно и смысла текста;

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

При обработке текста, а также при обработке запроса появляется задача поиска опечаток в тексте. Она может быть решена с помощью «метода Левенштейна». Суть этого метода заключается в поиске лексической схожести двух слов – так называемого «расстояния Левенштейна», минимального количества вставок, замен и удалений символов, необходимых для преобразования строки 1 в строку 2. Тем не менее, даже не смотря на методы устранения опечаток в тексте, остается высокий уровень «лексического шума», который может изрядно затруднить работу алгоритма индексации.

После представления информации в удобном для поисковой машины виде следует этап категоризации информации. Большинство методов распределения текстов по рубрикам или темам, основываются на том, что документы имеют отличительные черты. Относительно этих отличительных черт можно вводить правила категоризации. Существует два противоположных алгоритма выбора отличительных признаков и построения правил: машинное обучение и экспертный метод. Экспертный метод предполагает участие человека (эксперта) в выделении категорий, в то время как машинное обучение стремится к сведению человеческого участия к минимуму и автоматизации распределения документов по категориям. Метод машинного обучения базируется на нескольких наиболее распространенных алгоритмах: методе Байеса, метода Роше и алгоритма PrTFIDF. Общая задача категоризации звучит следующим образом - имеется два множества: D – документов и K – категорий. Каждому элементу из множества D, необходимо поставить в соответствие один или несколько элементов из множества K. Качество процедуры рубрикации будет оцениваться по тестовой выборке, в которую могут входить документы для которых известны соответствия элементов D и К множеств.

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

Нормализация запроса пользователя


Из-за наличия «лексического шума» в языке запросов к поисковой машине, сами запросы требуется также нормализовать, приводя к виду, который будет понятен поисковой машине. Возможно использование «Метода Левенштейна» для отсева орфографических опечаток в тексте. Запрос пользователя также должен быть подвергнут анализу с точки зрения информационно-поискового языка для поисковой машины (речь о них пойдет ниже). Нормализация запроса позволяет использовать поисковой системе алгоритм скрытого семантического индексирования (LSI – Latent Semantic Indexing). Этот алгоритм позволяет проводить автоматическую классификацию документа, проводя исследование слов во всей совокупности документов и подсчет характеристик для каждого документа или употребляемого термина. Скрытое семантическое индексирование очень точно определяет релевантность документа по отношению к запросу пользователя.

Итеративный обход сайтов и сбор информации


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

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

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

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


Система выдачи результатов


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

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



  • «Булевский» метод – в нем используются булевые операторы «И», «ИЛИ», «НЕ». Однако булевый метод плохо масштабирует задачу. Например, оператор «И» может очень сильно сократить число документов, выдаваемых на запрос. Для получения релевантных документов необходимо хорошо знать и понимать лексику системы. Для поисковой системы с таким языком необходимо использовать лексические базы данных со сложными словарями или тезаурусами, содержащими информацию о связи терминов словаря друг с другом;

  • Взвешенный поиск – это модификация «булевского» метода. В этой системе предполагается, что термин описывает содержание документа с некоторой точностью, и эту точность выражают в виде веса термина. Причем взвешивать можно как термины документа, так и термины запроса;

  • Поиск по мерам близости – в этой модели близость документа и запроса рассматривается как угол между ними. В этом случае высчитывается синус угла, получаемого как скалярное произведение двух векторов. В соответствии со значением меры близости происходит ранжирование документов при выдаче на них ссылок;

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

  • Кластерная модель поиска - в такой модели может использоваться два подхода. Первый заключается в том, что массив заранее разбивается на подмножества документов и при поиске вычисляется близость к некоторому подмножеству. В другом подходе кластер "накручивается" вокруг запроса и ближайших к нему терминов. Наиболее часто эта модель применяется в системах, уточняющих запрос по релевантности найденных документов;

  • Вероятностный поиск – в этих моделях вычисляется вероятность принадлежности документа классу релевантных запросу документов. При этом используется вероятность принадлежности терминов запроса каждому из документов базы данных;

  • Алгоритм скрытого семантического индексирования (LSI) – о нем мы уже упоминали выше, само название указывает, что методы ставят задачей выявление скрытых факторов, присутствующих в тексте.

«Булевские» методы поиска и отбора, а также «эвристические» алгоритмы ранжирования в последнее время все меньше и меньше отвечают требованиям современных поисковых систем. Алгебраические модели поиска, основанные на векторном представлении текстов документов, и использующие в качестве меры близости векторы, обладают двумя существенными недостатками. Во-первых, работа с матрицей такого объема крайне сложна из-за ее огромного объема. Во-вторых, такой подход плохо поддерживает синонимию — документы считаются семантически далекими друг от друга, если в них не имеется совпадающих слов. Один из методов, позволяющих преодолеть эти недостатки, являются методы группы LSI. Данный метод позволяет эффективно решить проблемы синонимии, и в значительной мере — омонимии слов.

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



Остановимся подробнее только на индексе цитируемости (в наиболее крупной на сегодняшний день поисковой системе Google он называется PageRank). Традиционные способы нахождения релевантных страниц, в случае односложных запросов не дают хороших результатов, т.к. по популярным темам всегда найдётся большое число страниц, релевантность которых будет одинакова. Индекс цитируемости служит критерием ценности страницы, это статическая величина, предназначенная для оценки качества страниц, не зависимо от каких либо запросов, т.е. с помощью индекса цитируемости вычисляется “глобальная ценность” каждой страницы. Для разработки индекса цитируемости был выбран академический подход оценки важности публикации автора по числу её упоминаний в библиографических ссылках других авторов. Для адаптации к применению в сети Интернет алгоритм был несколько изменен: вес каждой ссылки учитывается индивидуально и нормируется по числу ссылок на ссылающейся странице. Кроме того, индекс цитируемости может быть интерпретирован в терминах случайного блуждания. Также важную роль для ранжирования документа будет играть тематический индекс цитируемости. Грубо говоря, документ будет оцениваться тем выше, чем больше на него ссылок с сайтов схожей тематики.

База данных поисковой системы


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

Выводы


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

Полнота информации


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

Точность


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

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

Немаловажным моментом повышения точности поиска является применение семантических алгоритмов, которые решают целый класс задач:


  • автоматическое определение языка документа;

  • графематический анализ (выделение слов, границ предложений);

  • исключение неинформативных слов (стоп-слов);

  • лемматизация (приведение словоизменительных форм к «словарной», в том числе и для слов, не входящих в словарь системы);

  • разделение сложных слов.

Актуальность


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

Качество


Качество поиска – важнейший параметр оценки поисковой системы. Огромные объемы информации, большое число «информационного шума» - все эти проблемы поисковые системы должны решать в первую очередь. Для оценки качества страницы используют такие критерии как индекс цитируемости и тематический индекс цитируемости. Эта мера позволила резко повысить качество поиска.

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



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

Резюме


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

Использованная литература


  1. Как работают поисковые машины, автор: Илья Сегалович (Яндекс, "Наши публикации", 2004)

  2. Семантический поиск (SEO News, 2006)

  3. Подход к использованию семантических моделей полнотекстового поиска документов в Интернет, авторы: Нечаев Ю.Б., Толстобров А.А. (Научный журнал "Инновационные и информационные процессы и технологии в обществе и экономике" №1, Воронеж: ЦИРЭ, 2006)

  4. Принципы работы поисковой машины Рамблер (Search Engines, 2003)

  5. Классификация веб-страниц на основе алгоритмов машинного обучения, авторы: Борисова П.В., Мышков П.С., Незлобин А.А., Петров А.Д. (Яндекс, "Научные работы", 2004)

  6. Автоматическая рубрикация web-страниц в интернет-каталоге с иерархической структурой, авторы: Е.В. Дунаев, А.А. Шелестов (Яндекс, "Научные работы", 2004)

  7. К вопросу о ссылочном ранжировании, автор: Юрий Агапов (Search Engines, 2005)