Хранилище данных для основанной на знаниях системы извлечения информации из данных
Изобретение относится к системам извлечения информации. Техническим результатом является сокращение времени и затрат вычислительных ресурсов на обработку больших массивов данных с целью извлечения требуемой информации. Система содержит хранилище данных, механизмы анализа более низкого уровня, механизмы анализа более высокого уровня, индексатор. Согласно способу на основе первого набора правил, соответствующего первому механизму анализа, генерируют первый ключ, который направляют во второй механизм анализа, в котором на основе второго набора правил генерируют второй ключ, присоединяют первый и второй ключи к объектам и индексируют ключи и значения ключей. 2 н. и 13 з.п. ф-лы, 5 ил.
Область техники, к которой относится изобретение
Настоящее изобретение в целом относится к системам извлечения информации из данных.
Предпосылки создания изобретения
Извлечение информации из данных - это процесс выделения информации из информационных фондов в соответствии с желанием пользователя. В отношении этого процесса (первоначального описанного в англоязычных источниках как "data mining") в русскоязычной литературе также вошли в употребление такие термины, как "информационная проходка", "добыча данных", "обнаружение знаний", "интеллектуальный анализ данных" и др. С учетом контекста изобретения все эти термины рассматриваются как синонимичные понятию извлечения информации из данных. Возможно наиболее распространенным примером извлечения информации из данных является функциональность механизмов поиска или поисковых систем, которые включены в состав большинства Web-браузеров и позволяют пользователям вводить ключевые слова и затем получать в ответ список документов (иногда состоящий из нескольких тысяч документов), которые пользователь затем просматривает, чтобы найти нужную ему информацию.
В основу работы существующих поисковых систем, таких как AltaVista, Google, Northern Light, FAST и Inktomi положен принцип навигации по всемирной паутине, т.е. эти системы получают доступ к Web-страницам и к страницам, гиперссылки на которые содержат страницы, к которым был осуществлен доступ, с генерированием инвертированного индекса ключевых слов, встречающихся на Web-страницах. В таком индексе ключевые слова соотнесены с идентификаторами (унифицированными указателями информационного ресурса или URL) страниц, которые содержат ключевые слова. Для ответа на запрос осуществляют доступ к индексу, используя в качестве действительных параметров запрошенные ключевые слова, после чего из указателя возвращаются URL-адреса страниц, удовлетворяющие запросам. Вернувшиеся идентификаторы страниц обычно упорядочивают по релевантности, например, по данным о ссылке или частоте употребления ключевых слов.
Несмотря на то, что в большинстве коммерческих механизмов поиска результаты поиска выстраиваются по их релевантности, для нахождения информации определенного рода пользователю обычно приходится перелопачивать огромный объем результатов запроса. Это объясняется тем, что для отсеивания полезной информации от бесполезной часто необходимы специальные знания в определенной области. Действительно, при создании изобретения была осознана возможность ситуации, когда для обработки множества документов с целью отбора подмножества документов требуется один специалист, использующий для этого одни критерии отбора, после чего необходимо, чтобы другой специалист, пользуясь другими критериями, систематизировал нужную информацию, содержащуюся в подмножестве документов, отобранных первым специалистом. Несмотря на то, что данная процедура является всего лишь необходимым этапом работы, предшествующим этапу использования данных, она связана со значительными затратами труда и может занять больше времени, чем любой другой этап работы.
Рассмотрим, например, случай ответа на сложный вопрос из области маркетинга, такой как "каково мнение наших клиентов в северо-западных штатах Тихоокеанского побережья об оздоровительной продукции нашего конкурента с точки зрения узнаваемости и ценности ее товарного знака?". Анализ Web-страниц может начаться с поиска ключевого слова, в качестве которого может использоваться название компании-конкурента, однако затем специалисту потребуется значительное время, чтобы отсеять, возможно, тысячи документов, таких как правительственные отчеты, которые не дают ответа на заданный вопрос, хотя в остальном являются релевантными. Среди прошедших первый этап отсеивания документов может остаться множество документов, имеющих еще меньшее отношение к делу, таких как документы из подростковых чатов, в которых может упоминаться название компании-конкурента, но для отсеивания которых потребуются специальные знания о демографическом составе целевого сегмента покупателей.
Рассмотрим также простой вопрос "совместима ли программа Adobe Acrobat с MS Word?". В ответ на столь простой запрос, введенный в одну из вышеупомянутых поисковых систем, был получен список результатов из 33 миллионов Web-страниц, на большинстве из которых не содержалось искомого ответа "да" или "нет". Для отсеивания бесполезных страниц потребовался бы специалист, который просмотрел бы каждую страницу и определил, является ли она страницей, которая может содержать информацию о совместимости программ. Затем потребовался бы другой специалист для изучения страниц, отобранных первым специалистом, и определения, действительно ли такие страницы содержат ответ на конкретный поставленный вопрос. Несложно понять, что на работу сменяющих друг друга специалистов, просеивающих большой объем информации, может уйти чрезмерно много времени.
Краткое изложение сущности изобретения
Одним объектом изобретения является система извлечения информации из данных, включающая в себя: по меньшей мере одно хранилище, или склад данных, в котором содержатся объекты; по меньшей мере один механизм анализа более низкого уровня, связанный с хранилищем данных и генерирующий выходные данные на основе первого набора правил, реализованных в указанном механизме анализа более низкого уровня; и по меньшей мере один механизм анализа более высокого уровня, принимающий выходные данные механизма анализа более низкого уровня и генерирующий свои выходные данные на основе второго набора правил, реализованных в указанном механизме анализа более высокого уровня, причем выходные данные механизмов анализа более низкого и более высокого уровней присоединены к объектам, содержащимся в хранилище данных.
В частных вариантах предложенной системы хранилище данных может представлять собой базу данных и может содержать вертикальные и горизонтальные таблицы. Вход в вертикальные таблицы может осуществляться с использованием выходных данных механизма анализа одного из вышеупомянутых уровней, а вход в горизонтальные таблицы - с использованием идентификации объекта. Выходными данными могут быть ключи, представляющие соответствующие характеристики объекта, которому эти ключи сопоставлены. Как альтернативный вариант, хранилищем данных может быть, например, файловая система.
При необходимости в системе может также использоваться индексатор, связанный с хранилищем данных, а также быстродействующая кэш-память на полупроводниках и процессор обработки запросов для выполнения запросов по меньшей мере от одного механизма анализа. Кроме того, с механизмами анализа могут быть связаны очереди работ.
В частном предпочтительном варианте индексатор содержит индексы ключей и значения ключей, имеющихся в структурах хранения данных, например, таблицах. Он также может содержать булевы индексы, хранящие значения "да" или "нет" на запросы по форме "имеет ли ключ k значение v?". Кроме того, индексатор может содержать интервальные индексы, хранящие интервалы значений ключей, а также индексы текста. При необходимости индексатор может представлять собой обобщенное воплощение текстового индексатора в виде инвертированного файла, индексирующего Web-документы и обеспечивающего интерфейс прикладного программирования (API) для поиска документов по ключевым словам.
В предпочтительном варианте индексатор может содержать определенные ключи, позволяющие осуществлять запросы в отношении конкретного объекта с применением булевой логики. Кроме того, в индексаторе могут содержаться графические данные, поддерживающие входящие и исходящие запросы.
Целесообразно, чтобы снабжение индексов метками и индексирование в индексаторе осуществлялось раздельно.
Другим объектом изобретения является способ хранения данных для поддержки системы извлечения информации из данных, заключающийся в том, что: по меньшей мере в одном хранилище данных сохраняют объекты; с хранилищем данных устанавливают связь посредством по меньшей мере одного первого механизма анализа; на основе первого набора правил, соответствующего первому механизму анализа, генерируют выходные данные; направляют эти выходные данные по меньшей мере в один второй механизм анализа; на основе второго набора правил, соответствующего второму механизму анализа, генерируют выходные данные; и присоединяют сгенерированные выходные данные к объектам.
Краткое описание чертежей
Ниже изобретение более подробно рассмотрено на примере предпочтительного варианта его осуществления, поясняемого прилагаемыми чертежами, на которых:
на фиг.1 показана структурная схема системы с предпочтительной архитектуры системы,
на фиг.2 приведена блок-схема, поясняющая общую логику выполнения операций,
на фиг.3 показана схема горизонтальной таблицы,
на фиг.4 показана схема вертикальной таблицы,
на фиг.5 приведена блок-схема, иллюстрирующая логику выполнения операций анализатором.
Подробное описание предпочтительного варианта осуществления
На фиг.1 показана система, в целом обозначенная позицией 10, используемая для ответа на вводимые клиентами запросы на получение данных. По существу в системе 10 собраны воедино знания множества специалистов, необходимые для просеивания, т.е. подробного анализа, крупного информационного фонда и ответа на запросы информации, которые могут оказаться довольно сложными, например, как это описано выше. В частных вариантах осуществления изобретения, не ограничивающих объем патентных притязаний, система 10 может использоваться для анализа данных о предприятиях, сбора информации о конкурентах, анализа тенденций, выявления скрытых взаимосвязей, предоставления услуг Web-порталов, кластеризации и создания таксономической иерархии. Кроме того, система 10 может применяться для поддержки целевых функций, требующих использования в ней значительного объема специальных знаний, например, пакета снабженческих услуг (представляющих интерес для определенной части предприятия).
Система 10 может базироваться в одном месте, где находится ее разработчик, и обслуживаться одним процессором или группой процессоров с тем, чтобы отвечать на запросы клиентов на получение данных в служебном формате. Как вариант, некоторые компоненты системы 10 могут быть предоставлены в распоряжение клиента для извлечения информации из данных на оборудовании клиента.
Как более подробно описано ниже, система 10 имеет уровень сбора данных, уровень хранения данных, уровень анализа данных, уровень представления данных и уровень управления системой. На уровне сбора данных находящийся в левой части фиг.1 навигатор 12 всемирной паутины (WWW) получает доступ к всемирной паутине 14 (и при необходимости к другим частям сети Internet). Навигатор 12 также может получать доступ, например, к корпоративным сетям Intranet 16, в том числе к собственной информации фирмы, которую можно получить лишь путем соответствующей аутентификации. Предпочтительно, чтобы навигатор 12 осуществлял непрерывную навигацию по всемирной паутине 14, просматривая при этом одни страницы чаще других с учетом частоты обновления страниц и других критериев, и при помощи интерфейса 20 прикладного программирования (API) выводил просмотренные страницы в хранилище данных 18. В предпочтительном частном варианте осуществления изобретения интерфейсом 20 является протокол компании IBM для обслуживания запросов, известный как "Vinci xTalk", который представляет собой упрощенный протокол на основе языка XML в сочетании с набором пользовательских соглашений, регламентирующих текущий контроль, регистрацию и передачу данных. При описании используемых в системе API-интерфейсов сетевого уровня используются терминология фреймов протокола xTalk.
Также предпочтительно, чтобы навигатор имел канал обратной связи, позволяющий при необходимости изменять режим функционирования навигатора. В предпочтительном частном варианте осуществления изобретения навигатор 12 представляет собой инструмент, описанный в патенте US 6263364, или навигатор, описанный в полученном компанией IBM патенте US 6418433 (патентная заявка США №09/239921) под названием "System and Method for Focussed Web Crawling", также включенных в настоящее описание путем ссылки. Помимо получения данных при помощи навигатора 12 система при необходимости также может иметь инструмент 22 сбора структурированных данных, который осуществляет обработку данных из клиентских и сторонних баз данных 24 и передает обработанные данные в хранилище, или склад данных 18.
Что касается хранилища данных 18, в одном из вариантов изобретения хранилищем данных является система управления реляционной базой данных (реляционная СУБД), такая как СУБД DB2 компании IBM. В других вариантах могут использоваться иные системы, например файловые системы. Следующее далее описание применимо к хранилищам данных обоих типов.
В одном из вариантов осуществления хранилище данных 18 может иметь централизованную программу, выполняющуюся на одной или на нескольких ЭВМ. Описанные ниже механизмы анализа - анализаторы могут выполняться на независимых ЭВМ, обращаясь к программе хранилища данных с запросами для считывания или записи данных. Как альтернативный вариант, хранилище данных 18 может быть распределено по нескольким ЭВМ, при этом анализаторы действуют на таких ЭВМ в параллельном режиме. В таком варианте для повышения эффективности использования ресурсов документ может быть считан из местной (локальной) части хранилища данных в память, находясь в оперативной памяти, пройти по цепочке зависимых или независимых анализаторов и снова быть сохраненным в хранилище данных. В действительности оба вышеупомянутых типа архитектуры могут быть реализованы в одной и той же системе 10, учитывая тот факт, что одни анализаторы лучше работают в архитектуре второго типа (например, анализаторы, работающие постранично), тогда как для других анализаторов могут требоваться служебные сигналы или данные, обеспечиваемые архитектурой первого типа.
Хранилище данных 18 связано с индексатором 26 и, при необходимости, с быстродействующей кэш-памятью 28 на полупроводниках. Для выполнения запросов анализаторов предусмотрен процессор 30 обработки запросов, имеющий доступ к кэш-памяти 28, индексатору 26 и хранилищу данных 18, как это описано ниже. Как составная часть уровня хранения данных системы 10 в системе могут быть реализованы очереди работ анализаторов, рассматриваемые ниже.
В хранилище данных 18 содержится довольно большой объем информации, например, данные Web-страниц, полученные от навигатора 12. В хранилище данных 18 также хранятся объекты, представляющие данные, на основе которых могут приниматься решения, что описано ниже. Такие объекты имеют соответствующие универсальные идентификаторы (UEID), кодирующие идентификацию и тип объекта, например, "Web-страница", "гиперссылка", "частное лицо", "корпорация", "статья". Объекты также могут содержать ключи с соответствующими значениями, которые присоединены к объектам описанными ниже анализаторами. Например, анализатор обрабатывает страничный объект и создает ключ, названный "Crawl:Content", который включает в себя HTTP-содержимое соответствующей Web-страницы (поэтому длина значения ключа относительно велика). В любом случае объекты могут быть сохранены в файловой системе, СУБД, такой как DB2, где они представлены в горизонтальных и вертикальных таблицах, или в другой системе хранения данных.
Индексатор 26, помимо прочих элементов, содержит индексы ключей и значения ключей, имеющихся в хранилище данных. Индексатор 26 может содержать булевы индексы, хранящие значения "да" или "нет" на запросы по форме "имеет ли ключ k значение v?". Кроме того, в индексаторе 26 могут содержаться интервальные индексы, хранящие интервалы значений ключей, например, координат географических областей, индексы текста, являющиеся обычными индексами для характеризующих объекты данных, а также при необходимости другие индексы.
В любом случае предпочтительно, чтобы индексы (и таблицы для хранения данных в случае, когда хранилище данных представляет собой базу данных) указывали не на возможное местоположение конкретного наименования или текста, а лишь на то, что конкретная страница имеет определенную характеристику, или на то, что в каком-то месте на этой странице находится конкретный текстовый элемент. Таким образом, благодаря довольно высокой степени структурированности системы 10 к хранилищу данных предъявляются меньшие требования по объему памяти, чем в противном случае, что облегчает практическую реализацию хранилища данных. Вместе с тем, при желании может быть указано, где именно на Web-странице может находиться конкретное наименование или текст.
Что касается дополнительных деталей, касающихся уровня хранения данных системы 10, в предпочтительном частном варианте изобретения индексатор 26 представляет собой обобщенное воплощение обычного текстового индексатора в виде инвертированного файла. В одном варианте выполнения он индексирует Web-документы и обеспечивает интерфейс прикладного программирования (API) для поиска документов по ключевым словам. Набор сопоставленных документу ключевых слов может представлять собой просто слова из документа, либо он может быть по необходимости пополнен - посредством описываемых ниже анализаторов - дополнительной информацией, относящейся, например, к имеющимся на странице географическим районам, собственным именам, ссылкам на продукцию или рестораны или иные известные системе 10 объекты, результаты семантического анализа страницы и тому подобное. В этом случае API-интерфейс поиска по ключевым словам допускает включение в запросы любого слова из подобных расширенных наборов ключевых слов.
В других вариантах реализации в индексаторе 26 содержатся определенные ключи, позволяющие осуществлять запросы в отношении конкретного объекта с применением булевой логики или позволяющие графическим данным поддерживать входящие и исходящие запросы, и тому подобное. Чтобы обеспечить такую универсальность, снабжение метками (tokenization) проводится отдельно от индексирования. В частности, индексатор 26 рассчитан на получение потока меток, а не потока документов. Соответственно, снабжение метками осуществляется перед индексированием. Для каждой индексированной метки положение метки (относительное положение метки в потоке) сохраняется вместе с определяемыми пользователем данными метки, которые могут быть произвольными. Такая упрощенная модель обеспечивает эффективное индексирование и обеспечивает универсальный API-интерфейс, применимый в разнообразных случаях. Кроме того, развязка снабжения данных метками и индексирования позволяет совместно индексировать метки, происходящие из разных вариантов реализации правил (например, из различных генераторов меток).
Несколько версий индексатора 26 могут выполняться одновременно. Для простоты "главным" текстовым индексатором считается индексатор, в котором хранятся метки, соответствующие всему набору просмотренных и отобранных страниц. Как указано ниже в отношении анализаторов согласно настоящему изобретению, анализаторы присоединяют "ключи" к объектам, хранящимся в хранилище данных 18. Генераторы меток, связанные с индексатором 26, действуют точно по тому же принципу. В частном варианте изобретения генератор текстовых меток может быть выполнен на основе генератора меток Text Analysis Framework (TAF), разработанного компаниями IBM Research и IBM Software (г.Беблинген). Такой генератор меток считывает данные страницы и записывает результат исходной разметки для каждой страницы. Затем задействуются другие генераторы меток, которые используют эти данные или, по своему выбору, необработанные данные страниц и сохраняют в хранилище данных другие метки. В частности, один генератор меток может сопоставлять собственные имена и тегировать (метить) их в качестве таковых, а другой генератор меток - считывать только выходные данные генератора меток собственных имен и записывать метки, содержащие метаданные, соотносящие собственные имена с конкретными известными объектами, находящимися в любом другом месте системы 10. Все эти генераторы меток регистрируются в главном индексаторе 26.
За подробным описанием предпочтительного частного варианта выполнения индексатора 26 следует рассмотрение процессора 30 обработки запросов. Для активизации процессора 30 обработки запросы потоков данных из хранилища данных 18 могут осуществляться описанными ниже анализаторами на расширяемом языке запросов. Принцип доступа к процессору 30 обработки запросов в точности совпадает с принципом доступа к индексатору 26, т.е. инициатор запроса направляет запрос на обслуживание (в данном случае постановку задачи на расширяемом языке запросов) и получает поток данных из процессора 30 обработки запросов. Запрос может предполагать объединение нескольких потоков с использованием стандартных операций комбинационной логики, объединяющие потоковые данные (булевых операторов, таких как И и ИЛИ, операторов соединения баз данных, таких как внутреннее и внешнее соединения, операторов сортировки и операторов, пополняющих поток дополнительной информацией за счет, например, дополнения каждого универсального идентификатора объекта UEID в потоке значением определенного ключа). Язык запроса может соединять любые произвольные потоки.
Как упомянуто выше, уровень анализа данных системы 10 включает библиотеку 32 анализаторов, в которой хранятся реализованные программно анализаторы, которые взаимодействуют с API-интерфейсом 20 уровня сбора данных и, следовательно, с уровнем хранения данных. В типичном частном варианте изобретения библиотека 32 анализаторов включает анализатор 34 ссылок, выдающий ссылки на определенную страницу и/или со страницы, фильтр 36 спама, выявляющий спам в хранилище данных 18, фильтр 38 порнографии, выявляющий в хранилище данных 18 порнографические страницы, анализатор-классификатор 42, который классифицирует страницы на основе наличия на страницах последовательностей терминов, анализатор 44 географических данных, выявляющий на Web-странице любую географическую информацию, анализатор 46 корпораций, анализатор 48 таксономии, выдающий страницы заданной таксономической категории, анализатор 50 регулярных выражений, выдающий поток страниц, содержащих определенное регулярное выражение, и так далее.
Под "анализатором" или "элементом анализа данных" понимается механизм анализа, который на основе набора правил генерирует выходные данные, в частности - выходные данные, которые могут содержать один или несколько ключей, представляющих характеристики объекта. Такие правила могут быть определены эвристически и могут включать статистически обоснованные правила. В качестве примера, анализатор 38, реализующий функцию фильтра порнографии, при помощи техники анализа изображений может определять, содержит ли Web-страница порнографию, и присоединять к странице ключ и булево значение ключа: "порно = да" или "порно = нет". Для примера, в таком анализаторе порнографии могут использоваться принципы, описанные в патенте US 6295559 на имя компании IBM. Или же анализатор 46 корпораций на основе правил взаимосвязи слов, анализа URL-адресов или иным способом может определять, является ли определенная страница страницей какой-либо корпорации, и затем присоединять к такой странице ключ, указывающий на результат проведенного анализа. Опять же, в анализаторе, реализующем фильтр 36 спама, могут использоваться, например, принципы, описанные в патенте US 6266692 на имя компании IBM. Такой анализатор может присоединять к Web-страницам или сообщениям, получаемым по электронной почте, ключи, указывающие на то, являются ли они спамом. Далее, анализатор 44 географических данных может присоединять к Web-странице ключ, представляющий интервалы градусов широты и долготы, относящиеся к теме страницы или ее автору, используя правила для извлечения такой информации. В частном примере выполнения изобретения в основу работы анализатора географических данных могут быть положены принципы, описанные в патенте US 6285996 на имя компании IBM. Следует учитывать, что конкретные типы анализаторов и конкретные правила, используемые каждым анализатором, могут различаться, не сказываясь на работоспособности и объеме настоящего изобретения.
В любом случае анализаторы представляют собой модульные компоненты, которые имеют определенные спецификации входных и выходных данных. Они могут быть написаны на любом языке и могут занимать, например, от нескольких строк на простом языке Perl для нахождения ключевых слов до десятков тысяч (или более) строк кода для выполнения сложных распределенных операций. Крупные задачи могут быть разбиты на более мелкие части, каждая из которых может быть легко решена отдельным анализатором данных или его разработчиком. Получаемые промежуточные результаты можно легко просматривать, проверять и отлаживать, при этом они могут представлять: самостоятельный интерес для других разработчиков анализаторов. Таким образом, анализаторы представляют собой эквивалент объектно-ориентированного проектирования, реализованные в архитектуре обслуживания широкого круга запросов. Анализаторы специфицируются с точки зрения данных, обычно указываемых посредством рассматриваемых ниже ключей, которые должны присутствовать при начале их работы, и данных (в том числе других ключей), которые они создают в процессе успешной обработки данных.
В частности, в предпочтительном варианте изобретения анализатор может снабжаться работой (заданиями) из управляемой системой очереди работ на основе одной или нескольких зависимостей, определенных этим анализатором. В качестве примера, некий анализатор ("анализатор А"), заинтересованный в обработке страниц, содержащих указания определенных персоналий или определенных географических районов, может зарегистрировать свою зависимость от анализатора 44 географических данных и анализатора персоналий. Тогда очередь работ для анализатора А будет непрерывно обновляться за счет включения объектов, которые были обработаны анализатором географических данных и анализатором персоналий, на что указывают ключи, присоединенные к этим объектам в хранилище данных анализатором географических данных и анализатором персоналий, но пока еще не анализатором А. После обработки таких объектов анализатор А может присоединить к обработанным объектам собственный ключ или ключи, используя при этом - в том случае, если хранилище данных представляет собой базу данных - существующие таблицы объектов, либо создать новые объекты (при помощи соответствующих таблиц, если хранилище данных реализовано в форме базы данных), при этом каждый ключ представляет определенную характеристику объекта. В таком режиме работают анализаторы, извлекающие ссылки на конкретные виды продукции, торговые наименования, людей, отрасли промышленности, актеров и так далее.
С другой стороны, анализатор может не брать работы из очереди работ, а вместо этого зарегистрировать свои требования к свежести данных в описанной далее системе управления, определяющей то, как часто и в какой среде должен использоваться анализатор. Другие анализаторы, которые, например, осуществляют еженедельные суммарные подсчеты, могут запросить описанную ниже систему управления инициировать один или несколько экземпляров такого анализатора, чтобы исполнить еженедельное формирование итоговой суммарной таблицы или структуры данных, также используя в качестве входных данных объекты, к которым присоединены соответствующие ключи.
Таким образом, анализаторы считывают из хранилища данных 18 долговременные и достоверные потоки необработанного содержимого (т.н. контента), а также обработанные данные, созданные другими анализаторами. Эти анализаторы, а также по сути дела многие анализаторы системы 10 потребляют и обрабатывают данные. Две рассмотренные выше модели осуществления доступа к данным включают в себя произвольный доступ к конкретному объекту или множеству объектов и потоковый доступ к перечню объектов. В случае произвольного доступа в хранилище данных 18 анализатор просто запрашивает релевантные части соответствующего объекта, используя универсальный идентификатор объекта UEID. Для получения потока данных инициируется составление перечня объектов путем запроса данных из хранилища данных 18 с использованием индексатора 26 или процессора 30 обработки запросов.
Например, анализаторы с более сложными требованиями к данным могут обращаться к процессору 30 обработки запросов со сложными запросами, возможно предусматривающими необходимость получения доступа к множеству компонентов, при этом обычными способами осуществляется оптимизация запросов, и в ответ генерируются потоки данных. Такие запросы могут повлечь за собой соединение баз данных по множеству таблиц, создание справочных таблиц индексов, включая поиск текста, запросы интервалов значений, географические справочные таблицы и сложение в системе меньших наборов результатов из множества различных источников. Независимо от того, выведены ли перечни из индексатора 26 или процессора 30 обработки запросов, эти перечни обеспечивают постоянство существования объектов, а доступ к ним может осуществляться последовательно или параллельно - в зависимости от характера обработки.
Результаты обработки, осуществленной анализаторами, сохраняются в хранилище данных 18 с возможностью доступа к ним других анализаторов и конечных пользователей. Как указано выше, для записи данных в хранилище данных 18 с возможностью доступа к ним других анализаторов анализатор просто создает новые ключи и значения, которые следует присоединить к объекту, после чего выполняет операцию записи в память.
Результаты запроса конкретного клиента на получение информации, предоставляемой анализаторами согласно настоящему изобретению, могут быть представлены на уровне 52 представления данных. Результаты могут быть распечатаны или представлены в аудиовизуальной форме или иной форме по желанию. Описанными выше уровнями управляет уровень 54 подсистемы управления кластером, что более подробно описано ниже. Для облегчения ввода данных и ответа на запросы клиентами информации, клиентский интерфейс 56 при необходимости может получать доступ к API-интерфейсу 20 уровня сбора данных и клиентским базам данных 58.
В рассматриваемом предпочтительном варианте осуществления уровень 54 подсистемы управления планирует, инициирует, контролирует и регистрирует операции, происходящие в различных компонентах. Конечные приложения берут результаты из визуализированных таблиц, хранилища данных 18 или анализаторов, обрабатывающих запросы в режиме реального времени.
В частном предпочтительном варианте изобретения система 10 и уровень 54 подсистемы управления поддерживаются большим кластером (многомашинной вычислительной системой). Помимо управления анализаторами система управления 54 обнаруживает отказы и сбои аппаратного и программного обеспечения кластера и по определенной программе восстанавливает работоспособность системы после сбоев, соответствующим образом уведомляя системных администраторов. Уровень 54 подсистемы управления также обеспечивает функциональные возможности, такие как перемещение, выравнивание и планирование нагрузки для каждого компонента программного обеспечения.
Все события в системе 10 стекаются на один информационный сервер, который отслеживает состояние системы, ведет статистику, регистрацию и получает коды ошибок из приложений и компонентов инфраструктуры. События генерируются разнообразными источниками и включают в себя классы ошибок, используемые компонентами программного обеспечения кластера, событие базы данных DB2 и диспетчер регистрации, связанный с хранилищем данных 18, системные и сетевые компоненты контроля и так называемые наблюдающие агенты ("няньки" - "Nanny"), которые являются частью уровня 54 подсистемы управления и выполняются на соответствующих ЭВМ кластера.
Предпочтительно, чтобы наблюдающие агенты инициировали, прекращали и контролировали процессы и отслеживали ресурсы соответствующих ЭВМ, на которых такие агенты установлены. Они предпринимают и/или контролируют переброску информации, использование диска, памяти, процессора, ресурсов ядра (процессов, сокетов и т.д.) и управление вычислительным процессом, включая команды "запустить", "остановить", "уничтожить все". Наблюдающие агенты также получают информацию о состоянии от отдельных анализаторов, действующих на соответствующих ЭВМ, на которых они установлены, в том числе зарегистрированные сообщения, сообщения об ошибках, статистику, число ожидающих документов, число документов, обработанных в секунду, фактическую скорость потока документов, скорость обработки в байтах или объектах в секунду и другую информацию о состоянии, характерную для анализаторов.
На фиг.2 представлена общая логика работы описанной выше системы 10. На шаге 60 навигатор 12 осуществляет поиск во всемирной паутине 14, чтобы пополнить данными хранилище данных 18. При желании пополнение хранилища данных 18 данными из базы 24 данных может быть осуществлено на шаге 62 при помощи инструмента 22 сбора данных.
После пополнения хранилища данных 18 данными на шаге 64 по меньшей мере те из анализаторов, которые могут рассматриваться как анализаторы более низкого уровня (низшего уровня), осуществляют доступ к данным и обрабатывают данные, как это описано выше. Анализаторы более низкого уровня записывают результаты обработки обратно в хранилище данных 18. Например, анализаторы-фильтры, такие как фильтр 36 спама и фильтр 38 порно могут обрабатывать все Web-страницы, находящиеся в хранилище данных 18, и присоединять к соответствующим объектам соответствующие ключи, указывающие на то, является ли соответствующий сайт источником спама или порнографии. Кроме того, на каждой странице может быть активизирован удаляющий теги анализатор, который при обработке страницы удаляет элементы разметки языка гипертекстовой разметки (HTML), оставляя лишь необработанный текст, и затем присоединяет к каждому соответствующему объекту указывающий на это ключ "без тегов".
Далее на шаге 66 могут приниматься запросы клиентов на предоставление информации. В ответ на шаге 68 могут быть записаны дополнительные анализаторы более низкого уровня или созданы анализаторы более высокого уровня (или высшего уровня), если они необходимы, но еще не разработаны. Под анализаторами более высокого уровня могут пониматься анализаторы, которые устанавливают для себя зависимость от выходных данных других анализаторов, т.е. которые требуют для обработки объекты, тегированные ключами, выданными анализаторами более низкого уровня.
Примером анализатора или механизма анализа более высокого уровня может служить анализатор, отвечающий на вышеупомянутый вопрос "каково мнение наших клиентов в северо-западных штатах Тихоокеанского побережья об оздоровительной продукции нашего конкурента с точки зрения узнаваемости и ценности ее товарного знака?". Такой анализатор может установить, что ему требуются лишь страницы из северо-западных штатов Тихоокеанского побережья, на что указывает географический ключ, присоединяемый к объектам анализатором географических данных, и только при условии, что объект содержит название компании-конкурента, на что указывает ключ, присоединенный к объекту анализатором собственных имен. Множество таких зависимостей можно сформулировать на основе гипотез, при этом предполагается, что специалист, устанавливающий зависимости для такого анализатора, использует эвристический метод согласно своим знаниям и опыту и может не знать того, каким образом специалист, создавший, например, анализатор географических данных, пришел к такому решению. На шаге 70 клиенту сообщают результаты и выставляют ему счет на основе цены одного запроса или стоимости подписки.
На фиг.3 и 4 показана схема горизонтальных и вертикальных таблиц, которые могут использоваться, когда - в качестве частного примера осуществления изобретения - хранилище данных реализовано в виде СУБД, такой как DB2. На фиг.3 показана горизонтальная таблица 72, каждая строка 74 которой отображает какой-либо объект. В каждой строке имеется столбец 76 универсальных идентификаторов объектов UEID, столбец 78 меток времени (если они требуются) и множество столбцов 80 ключей. В отличие от горизонтальной таблицы, показанная на фиг.4 вертикальная таблица 82 имеет множество строк 84, в каждой из которых имеется один столбец 86 ключей, столбец 88 универсальных идентификаторов объектов UEID, столбец 90 кодов ключей кодов, в котором указан тип ключа, и столбец 92 значений ключей, в котором указано значение ключа, например, булево значение, значение интервала и т.д. При необходимости может быть добавлен столбец 94 меток времени, в котором указано время ввода соответствующих данных в таблицу.
Из вышесказанного должно быть понятно, что хранилище данных 18 посредством реализованных в виде базы данных таблиц 72, 82 абстрагируется от формата реальных данных, что позволяет принимать решение относительно того, таблицы какого типа использовать для конкретного объекта, чтобы повысить эффективность тех схем доступа, которые, как предполагается, являются характерными для такого объекта. Предпочтительно, чтобы хранилище данных 18 также абстрагировалось от действующих в DB2 ограничений по длине строки, автоматически используя объекты с переменным числом символов (VARCHAR) или крупных двоичных объектов (BLOB) для запоминания значений, длина которых превышает максимальную длину строки. Для облегчения программистам прямого доступа к базе данных DB2 для написания кода, не зависящего от физического размещения данных, в предлагаемой системе предусмотрены API-интерфейсы.
Например, навигатор 12 записывает ключ Crawl:Content (поиск содержимого), ключ Crawl: Header (поиск заголовка) и ряд ключей извлеченных метаданных, таких как URL-адрес, данные задержки выборки, последняя дата изменения страницы, данные сервера, код возврата HTTP и так далее. Если хранилище данных 18 реализовано в виде базы данных, вся информация такого рода записывается в одну горизонтальную таблицу, в которой на каждый ключ навигатора предусмотрен один столбец. Записывается информация только навигатором 12, однако считывать ее может любой анализатор, имеющий разрешение. Анализаторы, которым требуется содержание страницы, должны лишь запросить значение ключа Crawl:Content, а хранилище данных 18 отображает соответствующую таблицу.
Для повышения эффективности таких вычислений в хранилище данных 18 при желании может быть создан словарь данных, содержащий информацию об установлении соответствия между определенным ключом и реальным местоположением в реляционной базе данных. Кроме того, в нем содержится вспомогательная информация, такая как тип и владелец ключа. Анализаторы, которые записывают множество ключей, могут записывать такие ключи в особую горизонтальную таблицу, при этом за одну операцию обновления строки может быть записано множество ключей.
Как было сказано выше, несколько анализаторов, в том числе навигатор 12, наиболее естественным образом работают на страничном уровне, создавая и потребляя постраничную информацию. Вместе с тем, другие анализаторы могут работать и с объектами, отличными от необработанных страниц. В частности, одни анализаторы, такие как фильтр 36 спама на основе ссылок, работают с целыми Web-сайтами, определяя, является ли весь сайт источником спама. Другие анализаторы могут работать с фразами, собственными именами, названиями компаний или названиями населенных пунктов, ресторанов, именами предпринимателей и т.д. Каждая такая категория данных представляет отдельный объект и для нее требуется собственный набор горизонтальных и вертикальных таблиц (или иная структура хранения данных) в хранилище данных 18. Соответственно, подобно тому, как навигатор 12 записывает данные в горизонтальную таблицу страничного объекта, находящегося в базе данных, анализатор 46 корпораций способен заполнять горизонтальную таблицу в отношении корпораций. Другие анализаторы, которые должны присоединять пары "ключ-значение" к корпорациям, могут получать доступ к ключам, присоединенным к объектам анализатором 46 корпораций, и затем записывать другие ключи в другую структуру данных объекта-корпорации.
На фиг.5 показана конкретная логическая блок-схема, применимая в том случае, когда на шаге 96 из навигатора 12 поступает Web-страница. На шаге 98 может быть активизирован удаляющий теги анализатор, который при обработке странице на шаге 100 удаляет разметку HTML, оставляя лишь необработанный текст, и присоединяет к объекту ключ "без тегов", содержащий соответствующее указание.
На шаге 102 объект в соответствии с вышеизложенными принципами может поступить в другие анализаторы, для чего система управления 54 на основе ключа "без тега" доставляет объект другим таким анализаторам. На шаге 104 эти другие анализаторы обрабатывают характеризующие объект данные и могут присоединять собственные ключи к элементам структуры данных объекта, например, и в горизонтальной таблице, представляющей объект, и в соответствующей вертикальной таблице, отображающей ключ, если хранилище данных реализовано в виде базы данных. Некоторые анализаторы также могут извлекать информацию, например, название корпорации, например, из страничного объекта и создавать структуры хранения дополнительных данных объекта (в виде файлов или таблиц), отображающие такие объекты, например, объекты-корпорации.
После завершения начальной обработки данных анализаторами осуществляется переход к обозначенному ромбом шагу 106 принятия решения, на котором устанавливается, запрашивались ли объекты с заданными ключами какими-либо еще анализаторами, например, n-м анализатором. Если объект содержит все ключи, затребованные n-м анализатором в качестве входных данных, на шаге 108 n-му анализатору предоставляется такой объект, например, путем помещения объекта в очередь работ анализатора. Затем n-й анализатор на шаге 110 осуществляет доступ к объекту путем, например, обращения к своей очереди работ, чтобы осуществить обработку объекта и/или обработку характеризующих объект данных. На шаге 112 n-ный анализатор выдает собственный ключ или ключи и вводит такие ключи в структуры данных объекта подходящим образом для связывания ключа или ключей с этим объектом. Далее на шаге 114 анализатор клиента может активизировать другие анализаторы и/или получить доступ к объектам соответствующим образом для создания базы данных, содержащей информацию, которую ищет клиент системы.
Описанная система 10 может применяться для решения множества конкретных задач в интересах клиентов. Одной из таких задач является создание ссылок на объекты/углубленных комментариев к объектам (action link/drill note), когда в систему поступает документ, и анализаторы системы на основе определенных правил выявляют в документе важные "объекты" или сущности (например, людей, места, события). Затем анализатор-компилятор системы 10 составляет досье или совокупность информации в иной форме о каждом из таких объектов. Далее такое досье (или его аналог) связывают с объектом в исходном документе.
Досье или его аналог может представлять собой мини-портал для такого объекта, например, может выглядеть как специальный справочник типа Yahoo для такого объекта. Соответственно, если объектом является какой-либо человек, для него могут быть созданы подкатегории, содержащие адреса, имеющие отношение к такому человеку, имена людей, имеющих отношение к такому человеку, местоположения, имеющие отношение к такому человеку, области деятельности, имеющие отношение к такому человеку, публикации о таком человеке и т.д. Выбор объектов для создания ссылок осуществляет анализатор-компилятор, предпочтительно, в соответствии с функцией перестраиваемого предпочтения или по иному правилу, которое может быть определено эвристически.
Другим частным примером применения системы 10 служит прикладная программа "поиска и формирования ссылок на правовые отношения", одним из компонентов которого является упомянутая выше система создания ссылок на объекты/углубленных комментариев к объектам и которое также осуществляет поиск вероятных связей между "объектами", при этом объекты хранятся в хранилище данных 18, а по меньшей мере некоторые искомые элементы связей могут в нем отсутствовать. В качестве примера, рассмотрим судебное дело, в котором в структуре данных объектов-персоналий указаны Джон Доу и Джейн Смит (объекты-персоналии), но данные, складированные в хранилище данных 18, не указывают на явную взаимосвязь между ними. Анализатор прикладной программы поиска и формирования ссылок на правовые отношения идентифицирует оба объекта как важные на основе набора определенных правил, после чего выясняет, существуют ли другие объекты, через эти два человека которые могут быть взаимосвязаны. Например, может оказаться, что оба названных человека являются членами правления какой-либо компании или благотворительной организации, могли совместно опубликовать какой-либо доклад, могли упоминаться в прессе как коллеги или партнеры по какой-либо сделке и т.д. В таких случаях связующий объект (например, компания, членами правления которой Джон и Джейн одновременно являются, доклад, который они опубликовали совместно) может рассматриваться как "соединяющий объект" и быть включен в запросы на выявление скрытых взаимосвязей.
Следовательно, фаза выявления скрытых взаимосвязей судебного дела может быть расширена и предусматривать не только запрос документов, имеющих непосредственное отношение к определенным темам, людям или событиям, но также поиск документов, релевантных для "соединяющих объектов", через внешние источники данных.
В другом частном примере возможностей использования системы 10 она реализована в виде прикладной программы по маркетингу конкурирующих товаров. В систему 10 может быть введена информация о ряде товаров и могут быть созданы анализаторы для однозначного выявления упоминаний товара и классификации таких упоминаний на основе контекста упоминания. Например, чтобы отличить моющее средство Tide от приливов (tide - англ.) как явления природы. Для классификации контекста упоминаний также используется анализатор-классификатор/профилировщик, который при классификации/определении характеристик упоминания, основанной на множестве ранее классифицированных/профилированных упоминаний, предпочтительно использует статистические средства. Кроме того, для определения соответствующих географических связей, имеющих отношение к источнику, в котором встречается упоминание, может использоваться анализатор географических данных. Затем рассматриваемая прикладная программа может быть настроена для выдачи точно дифференцированной меры "общественного внимания" или "хождения слухов" вокруг определенного ряда товаров по сравнению с "общественным вниманием" или "хождения слухов", которые вызывают конкурентные изделия. Такая информация может быть отображена на карте, например, различными цветами или уровнями яркости, соответствующими уровню "общественного внимания" или "хождения слухов". Она также может быть отслежена во времени, что помогает выявлять заслуживающие внимания положительные или отрицательные тенденции. В систему также могут быть введены сегментированные по географическому или демографическому признаку данные, отображающие затраты на рекламу или иную маркетинговую деятельность, имеющую отношение к изделию, а анализатор осуществляет проверку прямого соотношения между такой деятельности и "общественным вниманием" или "хождением слухов", за счет чего создается определенный критерий эффективности маркетинговой деятельности.
Хотя подробно рассмотренные выше основанная на знаниях система извлечения информации из данных и хранилище данных для нее способны в полной мере решать описанные выше задачи изобретения, следует иметь в виду, что это лишь предпочтительный на данный момент вариант осуществления изобретения, характеризующий широкое по своей сущности предложенное техническое решение. Под патентные притязания на настоящее изобретение целиком подпадают и другие варианты осуществления, которые могут быть очевидными для специалистов, и объем этих притязаний не ограничен ничем, кроме формулы изобретения, в которой упоминание какого-либо элемента в единственном числе, если только это не указано в прямой форме, означает не "один единственный", а "один или несколько". Все конструктивные и функциональные аналоги элементов описанного выше предпочтительного варианта осуществления, которые известны или станут известными впоследствии специалистам в данной области техники, считаются входящими в объем настоящих патентных притязаний. Кроме того, любое устройство или способ считаются входящими в объем настоящих патентных притязаний, даже если такое устройство или способ не призван решать абсолютно все задачи, которые должно решать настоящее изобретение. Более того, ни один элемент, компонент или шаг осуществления способа, упомянутый в настоящем описании, не предназначен для передачи в общественное пользование, независимо от того, упомянут ли в прямой форме такой элемент, компонент или шаг осуществления способа в формуле изобретения.
1. Вычислительная система для интеллектуального анализа данных, включающая в себя по меньшей мере одно хранилище данных, в котором содержатся объекты, и следующие программные средства:
по меньшей мере один механизм анализа более низкого уровня, взаимодействующий с хранилищем данных и генерирующий в качестве своих выходных данных по меньшей мере один ключ, представляющий соответствующие характеристики объекта, с которым этот ключ соотнесен, на основе первого набора правил, реализованных в механизме анализа более низкого уровня;
по меньшей мере один механизм анализа более высокого уровня, принимающий выходные данные механизма анализа более низкого уровня и генерирующий в качестве своих выходных данных по меньшей мере один ключ, представляющий соответствующие характеристики объекта, с которым этот ключ соотнесен, на основе второго набора правил, реализованных в механизме анализа более высокого уровня, причем указанные выходные данные присоединяются к объектам, содержащимся в хранилище данных; и
индексатор, связанный с хранилищем данных и содержащий индексы ключей и значения ключей, имеющихся в хранилище данных, причем генерирование ключей в механизмах анализа и индексирование в индексаторе производятся раздельно.
2. Система по п.1, в которой в хранилище данных имеются вертикальные и горизонтальные таблицы, причем ввод данных в вертикальные таблицы осуществляется с использованием одного из ключей, а ввод данных в горизонтальные таблицы осуществляется с использованием идентификатора объекта.
3. Система по п.1, в которой хранилище данных представляет собой реляционную базу данных.
4. Система по п.1, в которой хранилище данных представляет собой файловую систему.
5. Система по п.4, содержащая также быстродействующую кэш-память на полупроводниках, связанную с индексатором и хранилищем данных.
6. Система по п.5, содержащая также процессор обработки запросов, имеющий доступ к одному или нескольким из следующих элементов: кэш-памяти, индексатору и хранилищу данных, для выполнения запросов по меньшей мере от одного механизма анализа.
7. Система по п.6, содержащая также по меньшей мере одну очередь работ, связанную по меньшей мере с одним механизмом анализа.
8. Система по п.1, в которой объекты идентифицируются посредством идентификаторов, кодирующих тип объекта.
9. Система по п.1, в которой индексатор содержит булевы индексы, хранящие значения "да" или "нет" на запросы по форме "имеет ли ключ k значение v?".
10. Система по п.1, в которой индексатор содержит интервальные индексы, хранящие интервалы значений ключей.
11. Система по п.1, в которой индексатор содержит индексы текста.
12. Система по п.1, в которой индексатор содержит индексы, а хранилище данных - таблицы, в которых отсутствует указание на местоположение конкретного наименования или текста в объекте, а имеется лишь указание на наличие у объекта определенной характеристики.
13. Система по п.1, в которой индексатор указывает на наличие в Web-документе определенного текстового элемента и обеспечивает интерфейс прикладного программирования (API) для поиска документов по ключевым словам.
14. Система по п.1, в которой индексатор содержит определенные ключи, позволяющие осуществлять запросы в отношении конкретного объекта с применением булевых операторов.
15. Способ хранения данных для поддержки системы интеллектуального анализа данных, заключающийся в том, что
по меньшей мере в одном хранилище данных сохраняют объекты,
взаимодействуют с хранилищем данных посредством по меньшей мере одного первого механизма анализа,
на основе первого набора правил, соответствующего первому механизму анализа, генерируют по меньшей мере один первый ключ, представляющий соответствующие характеристики объекта, с которым первый ключ соотнесен,
направляют первый ключ по меньшей мере в один второй механизм анализа,
на основе второго набора правил, соответствующего второму механизму анализа, генерируют по меньшей мере один второй ключ, представляющий соответствующие характеристики объекта, с которым второй ключ соотнесен,
присоединяют первый и второй ключи к объектам и
индексируют ключи и значения ключей, имеющиеся в хранилище данных, причем генерирование ключей в механизмах анализа и индексирование проводят раздельно.
