Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 305
Текст из файла (страница 305)
Но независимо от применяемого алгоритма кластеризации требуется решить еше одну задачу, прежде чем результаты кластеризации можно будет использовать для представления результируюгцего набора, — найти удобный способ описания кластера. При использовании метода классификации имена категорий уже определены (например, "Еагп)пйз" — доходы), но при кластеризации имена категорий приходится изобретать заново. Один из способов выполнения этой задачи состоит в подборе списка слов, которые являются представительными для этого кластера. Еше один вариант состоит в применении названий одного или нескольких документов, близких к центру кластера.
11!9 Глава 23. Вероятностная обработка лингвистической информации Создание систем информационного поиска До сих пор в этой главе было приведено описание работы систем информационного поиска в общих чертах, но не показано, как добиться эффективного функционирования этих систем для того, чтобы машины поиска 1теЬ могли возвращать искомые результаты обработки коллекции, состоящей из многих миллиардов страниц, за десятые доли секунды. Двумя основными структурами данных любой системы информационного поиска являются лексикон, содержащий списки всех слов в рассматриваемой коллекции документов, и инвертированный индекс, в котором перечислены все места, где каждое слово встречается в коллекции документов.
Лексиконом называется структура данных, которая поддерживает одну важную операцию: после получения определенного слова она возвращает данные о том, в каком месте инвертированного индекса хранятся экземпляры этого слова. В некоторых версиях систем информационного поиска эта структура возвращает также данные об общем количестве документов, содержащих искомое слово. Лексикон должен быть реализован с использованием хэш-таблицы или аналогичной структуры данных, которая обеспечивает быстрое выполнение этой операции поиска.
Иногда в лексикон не включают ряд широко распространенных слов, имеющих малое информационное содержание. Эти слова, называемыми св. запретными словами ("гйе", "оГ, "го", "Ье", "а'* и т.д.), только занимают место в индексе, но не увеличивают ценность результата. Единственным резонным основанием для включения нх в лексикон может служить вариант, в котором лексикон используется для поддержки фразовых запросов, — индекс, содержащий запретные слова, необходим для эффективной выборки результатов для таких запросов, как "Го Ье ог пог го Ье". св. Инвертированный индекс', подобно индексу (предметному указателю), приведенному в конце данной книги, состоит из множества Ж списков позиций — обозначений тех мест, где встречается каждое слово.
Применительно к булевой модели ключевых слов список позиций представляет собой список документов. А список позиций, применяемый в модели однословных сочетаний, представляет собой список пар (документ, количество). Для обеспечения поддержки фразового поиска список позиций должен также включать обозначения позиций в каждом документе, где встречается каждое слово. Если запрос состоит из одного слова (а такая ситуация встречается в 26% случаев, согласно [!4111), его обработка происходит очень быстро. Для этого выполняется единственная операция поиска в лексиконе для получения адреса списка позиций, а затем создается пустая очередь по приоритету. В дальнейшем происходит обработка списка позиций одновременно по одному документу и проверка количества экземпляров искомого слова в документе.
Если очередь по приоритету имеет меньше, чем д элементов (где й — размер желаемого результирующего набора), то пара (документ, количество) добавляется к очереди. В противном случае, если количество экземпляров искомого слова больше по сравнению с соответствующими данными элемента с наименьшими показателями в очереди по приоритету, этот элемент а Термин "инвертированный индекс" бптепеб (паек) является избыточным; лучшим термином был бы просто "индекс". Индекс называют инвертированным поточу, что он задаст порядок расположения слов, отличный от того порядка, в котором слова расположены в тексте, но таковы все индексы.
Тем не менее по традиции в системах информационного поиска применяется термин "инвертированный индекс". 1120 Часть Ъ"г1. Общение, восприятие и осушествление действий с наименьшими показателями удаляется из очереди и добавляется новая пара (документ, количество). Таким образом, поиск ответа на запрос требует затрат времени, пропорциональных 0(н+я1одя), где и — количество документов в списке позиций.
Если запрос состоит из п слов, требуется выполнить слияние п списков позиций, для чеготребуется затраты времени, равные о(пнья1одк). В данной главе теоретический обзор средств информационного поиска представлен с использованием вероятностной модели, поскольку эта модель основана на идеях, уже описанных при изложении других тем в настоящей книге. Но в системах информационного поиска, фактически применяемых на практике, чаШе всего используется другой подход, называемый Ж моделью векторного пространства.
Эта модель основана на таком же подходе с использованием мультимножества слов, как и вероятностная модель. Каждый документ представлен в виде вектора частот однословных сочетаний. Запрос также представляется полностью аналогичным образом; например, запрос (вауеэ хпйогтасхоп гесгхеча1 пос(е11 представляется в виде вектора: ( о, ..., т, о, ..., т, о, ..., т, о, ..., т, о, ... 1 Применяемая здесь идея состоит в том, что суШествует по одному измерению для каждого слова в коллекции документов, а запрос получает оценку 0 по каждому измерению, кроме тех четырех, которые фактически присутствуют в запросе.
Релевантные документы отбираются путем поиска среди векторов документов именно тех векторов, которые являются ближайшими соседями по отношению к вектору запроса в векторном пространстве. Одним из критериев подобия служит точечное произведение между вектором запроса и вектором документа; чем больше это произведение, тем ближе два вектора. С точки зрения алгебры указанные вычисления обеспечивают получение высоких оценок теми словами, которые часто появляются и в документе, и в запросе. А с точки зрения геометрии точечное произведение между двумя векторами равно косинусу угла между этими векторами; максимизация косинуса угла между двумя векторами (находяШимися в одном и том же квадранте) равносильна уменьшению этого угла до нуля.
Это краткое описание далеко не исчерпывает всю проблематику модели векторного пространства. На практике эта модель была развита до такой степени, чтобы в ней можно было учесть целый ряд дополнительных средств, уточнений, исправлений и дополнений. Основная идея ранжирования документов по их подобию в векторном пространстве позволяет внести новые понятия в систему числового ранжирования. Некоторые специалисты утверждают, что вероятностная модель позволила бы выполнять аналогичные манипуляции более научно обоснованным способом, но исследователи в области информационного поиска вряд ли согласятся перейти на другой инструментарий до тех пор, пока не убедятся в явных преимуществах другой модели с точки зрения производительности.
Для того чтобы получить представление о том, с какими масштабами применения средств индексации приходится сталкиваться при решении типичной задачи информационного поиска, рассмотрим стандартную совокупность документов из коллекции ТКЕС (Тех! КЕ!г!еча! Соп(егепсе), состояшую из 750 тысяч документов с общим объемом в 2 Гбайт текста. Лексикон этой коллекции содержит приблизительно 500 тысяч слов, к которым применены операции выделения основы и приведения к нижнему регистру; лля хранения этих слов требуется объем памяти от 7 до 10 Мбайт.
Инвертированный индекс с парами (документ, количество) занимает 324 ! 121 Глава 23. Вероятностная обработка лингвистической информации Мбайт, хотя и остается возможность применить методы сжатия для сокрашения этого объема до 83 Мбайт. Методы сжатия позволяют экономить пространство за счет небольшого увеличения потребностей в обработке. Но если сжатие позволяет держать весь индекс в памяти, а не хранить его на диске, то появляется возможность добиться существенного общего прироста производительности.
Для поддержки фразовых запросов требуется увеличение этого объема примерно до 1200 Мбайт не в сжатом виде или до 600 Мбайт со сжатием. Машины поиска %еЬ действуют в масштабах, превышающих примерно в 3000 раз указанные выше. При этом многие из описанных здесь проблем остаются теми же, а поскольку задача оперирования с терабайтами данных в одном компьютере практически не осу(цествима, индекс разделяется на )г сегментов и каждой сегмент сохраняется на отдельном компьютере. Запрос передается параллельно на все компьютеры, а затем )г результирующих наборов сливаются в один результирующий набор, который предъявляется пользователю. Кроме того, машины поиска ЮеЬ вынужден)я справляться с тысячами запросов, поступающих в секунду, поэтому для них требуется и копий )г компьютеров. Со временем значения )г и и продолжают возрастать.
23.3. ИЗВЛЕЧЕНИЕ ИНФОРМАЦИИ 'Ъ. Извлечением информации называется процесс создания записей базы данных путем просмотра текста и выявления экземпляров конкретного класса объектов или событий, а также связей между этими объектами и собь(тиями. Может быть предпринята попытка применить такой процесс для извлечения данных об адресах из %еЬ-страниц и внесения в базу данных информации об улице, городе, штате и почтовом коде или извлечения сведений о происходящих штормах из сообщений о погоде и внесения в базу данных информации о температуре, скорости ветра и количестве осадков. Системы извлечения информации занимают промежуточное положение между системами информационного поиска и полными синтаксическими анализаторами текста, поскольку к ним предъявляются более высокие требования, чем просто преобразование документа в мультимножество слов, но меньшие требования по сравнению с полным анализом каждого предложения.
Простейшим типом системы извлечения информации является система, основанная на атрибутах, поскольку в ней предполагается, что весь текст относится к одному объекту и задача состоит в извлечении атрибутов этого объекта. Например, в разделе 10.5 упоминалась задача извлечения из текста "17(п БХОА Мопйог (ог оп1у $249.99" отношений базы данных, определяемых следующим выражением: 3т и е сотрисепноп1сопе л Язае(п, гпопеп(17) ) л Ргхое(п, 3 (249. 99) ) л леео1исдоп(п, 1280х1024) Определенная часть этой информации может обрабатываться с помощью 'Ъ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
