авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |   ...   | 26 |

«Электронные библиотеки: Перспективные Методы и Технологии, Электронные коллекции English Труды RCDL 2010 ...»

-- [ Страница 11 ] --

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

«Электронные библиотеки: перспективные методы и технологии, электронные коллекции» – RCDL’2010, На каждом из них описание выбранной предмет Казань, Россия, 2010 ной области может быть представлено как совокуп ность элементов, которые определены на множестве каждом из аспектов может быть представлено как характеристических признаков и связаны отноше- совокупность элементов Mi, которые в рамках зако ниями (объекты и отношения предметного уровня, на композиции Zi определены на множестве харак концепты и концептуальные отношения, лексемы и теристических признаков Ai и связаны отношениями Ri. Согласно [5, 18], такое описание научного иссле лингвистические отношения) в рамках закона ком дования в частности можно назвать его онтологией.

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

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

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

темой.

Множество объектов реального мира представ ляется в языке множеством лексических единиц 3 Обзор подходов к формализации (знаков), каждая из которых именует предмет или текстов ряд предметов и выражает некоторое понятие. От Как было выяснено, существует два подхода к ражение предметов и понятий в языке иллюстриру решению задачи анализа, формализации и структу ет семиотический треугольник Фреге [11].

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

на определении частых наборов слов и объе материи. Понятие – это смысл языкового знака или динении их в ключевые понятия и др. [2]. Лингвис соответствующий знаку образ, формирующийся в тический подход предполагает проведение различ сознании человека. Объекты, воплощающие соот ных видов лингвистического анализа текста с целью ветствующие понятия, находятся на материальном идентификации фактов в тексте и извлечении их уровне. Знаки в свою очередь также являются объ характеристик [3].

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

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

граммных средств, в основу работы которых поло С точки зрения общей теории систем, согласно жен этот подход, являются Autonomy IDOL Server, [12], описание научного исследования может быть TextAnalyst и др. [14, 20, 22].

представлено как система S = {Si}, i=1,..,n, уровне Применение только лингвистического подхода вых моделей дескриптивного представления пред не позволяет выделить в тексте характеристические метной области научного исследования:

для данного текста признаки, а также замедляет и Si = Mi, Ai, Ri, Zi, затрудняет решение задачи, так как нет возможно сти исключить из рассмотрения и не подвергать где i – аспект, который формально соответствует анализу слова, изначально не являющиеся кандида требованиям назначения и формы представления (и, тами на информативные термины. При данном под таким образом, идентифицирован своим законом ходе под ключевыми понятиями подразумеваются композиции Zi), Mi – множество элементов, Ai – все факты, встречающиеся в тексте. В лингвистиче множество атрибутов, Ri – множество отношений.

ском подходе существует несколько направлений Иными словами, описание научного исследования в [1, 3, 7 и др.], которые в большинстве своем являют- сическая информация (принадлежность к именной ся модификациями одного наиболее распространен- или глагольной группе). Меткам дуг присваиваются ного, который заключается в извлечении фактов при названия лингвистических отношений между клю помощи сопоставления текста с набором регуляр- чевыми словами, обозначаемыми лексемами или ных выражений (образцов, шаблонов и т. д.). Се- разделителями, находящимися в вершинах, соеди мантика текста при данном подходе сохраняется с ненных этими дугами.

помощью ключевых понятий, которые в основном являются именами существительными: имена и фа милии людей, названия организаций и др. Иногда выделенные факты связываются ссылками друг на друга. Этот способ наилучшим образом подходит для решения задач информационной разведки (сбо ра разрозненной и распределенной информации по определенной теме, проблеме, персоналиям). Для задач поиска научной информации эти факты в большинстве случаев даже не являются информаци онно значимыми (характеристическими) объектами, а представляют собой второстепенные сведения, служащие для более полного представления пред метной области и используемые на самых низких уровнях абстракции представления. При этом связей типа «ссылок» не достаточно для построения поня тийного образа научного текста, т. к. важны смы словые связи между ключевыми понятиями, кото рые отражают функциональные зависимости и тем самым несут дополнительную смысловую инфор мацию по предметной области, которая зачастую не присутствует в тексте в явном виде. Программные средства КРОТ, Криминал, Аналитик и др., реали Рис. 1. Схема построения понятийной структуры зующие данный подход, представлены в [7, 15].

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

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

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

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

ков происходят на основании лингво-статистичес Лексемам и разделителям приписываются графема кой модели анализа текста, согласно которой клю тическая информация (положение в тексте, длина, чевые слова определяются на основании расчета шрифт, язык и т. д.), морфологическая информация полезности слов-кандидатов на информативные (часть речи и множество наборов граммем), стати термины. Все слова, которые не являются стоп стическая информация (полезность слова) и синтак словами, автоматически становятся словами- верку следующего вида (или, в соответствии с опре кандидатами на информативные термины. На осно- делением Ю.А. Шрейдера [13], знаковую систему):

вании результатов проведенного анализа методов E = L, K, D, I, расчета весов терминов [2, 16, 17, 21] для расчета полезности слов за основу была взята методика где L – множество лексических единиц (знаков);

K – TL*TF (Term Length*Term Frequency), одним из кон- множество понятий, в которых описываются (пред кретных применений которой является мера Чена. ставляются) концепты;

D – множество объектов Построенная функция полезности слов отражает предметной области (денотатов);

I – интерпретации, зависимость «полезности» слова для читателя с точ- соотносящие знаку его концепт (в связи с исключе ки зрения информативности, характеристичности нием из рассмотрения отношения знака к своему данного слова от значений длины и частоты появле- денотату).

ния слова в тексте и имеет следующий вид: Для перехода от элементов знакового уровня к элементам концептуального уровня используется подход группирования лингвистических отношений по признакам их роли при связывании лексических единиц. Соотнесение знакам (согласно [10], именам где uj – полезность слова j;

l norm – длина на- понятий) их денотатов происходит в два этапа.

j На первом этапе каждому знаку ставится в соот чальной (словарной) формы слова j;

N – количество ветствие выражаемое им понятие (концепт имени m понятия или несколько концептов в случае омони начальных форм слов документа;

norm j – количе мии). Каждое понятие обозначает класс объектов ство предложений, в которых присутствуют слова с предметной области, границы которой шире, чем начальной формой слова j;

m – число предложений в границы предметной области описываемого научно документе.

го исследования, или, согласно [10], класс денотатов Выделение словаря информативных слов делает имени этого понятия.

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

знаков расширяется за счет добавления слов, непо 1) Группа отношений сужения объема по средственно связанных с ними лингвистическими нятия отношениями.

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

воплощающих данное понятие, будет являться пере Для связывания лексем, полученных в результа сечением классов объектов, воплощающих два ис те обработки текста, используются знания о лин ходных понятия, таким образом, он будет меньше, гвистических отношениях, которые берутся из рус чем классы объектов, воплощающих два исходных ского общесемантического словаря (РОСС), описа понятия (при условии, что исходные понятия не ние которого приведено в [8, 19]. Семантическая совпадают). Словосочетание, образуемое из имен сеть предложения получается путем соединения пар этих понятий, будет именем нового понятия и будет слов (в которых слова связаны лингвистическими обозначать класс объектов предметной области, отношениями) по совпадающим словам в пределах отраженной в анализируемом тексте.

предложения.

2) Группа отношений между разными по нятиями 4.2 Этап семантической интерпретации Лингвистические отношения из этой группы по На данном этапе происходит идентификация казывают связь объекта, воплощающего данное по (восстановление) объектов и связей предметной нятие, с другим объектом, воплощающим другое области по ее знаковому представлению как систе- понятие. Объединение этих понятий также может мы взаимосвязанных самостоятельных объектов, привести к увеличению содержания нового понятия, обладающих своими характеристиками, путем пере- но оно выйдет за границы отраженной в тексте хода от знакового уровня к концептуальному, а предметной области, т. е. пересечение классов объ именно, сведения элементов и отношений знакового ектов, воплощающих два исходных понятия, будет уровня к понятиям и концептуальным отношениям. пустым в пределах предметной области описывае Также решается обратная задача визуализации ото- мого научного исследования. Также из имен этих бражения концептуального уровня представления понятий не всегда можно составить словосочетание, описания предметной области на знаковом уровне. так как слова, выражающие имена этих понятий, не Множества элементов всех уровней представле ния предметных областей представляют собой чет всегда непосредственно связаны в предложении форических ссылок, а также происходит уточнение грамматически. смысловых отношений, связывающих ключевые Лингвистические отношения, не вошедшие в эти компоненты понятийной структуры.

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

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

между ними.

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

тестовый набор из ряда текстов (порядка 30) разной O = C, P, V, J, степени сложности по различным предметным об ластям. Тестирование проводилось авторами тек где C – множество лингвистических отношений (от стов или экспертами в соответствующих предмет ношений знакового уровня);

P – множество концеп ных областях. С точки зрения экспертов, получен туальных отношений;

V – множество отношений ные графы соответствовали тексту с точностью до предметного (вещного) уровня;

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

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

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

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

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

Граф понятий наглядно представляет результаты выполненного исследования, а также дает представ Рис. 2. Понятийная структура в аспекте назначения ление о понятийной структуре предметной области научного исследования. Существенно, что при соотнесении автоматиче ски построенного представления текста с реальным 4.3 Этап анализа понятий представлением автора или эксперта (его знаниями На этапе анализа понятий происходит уточнение в данной предметной области) и внесении измене полученных ранее ключевых компонент понятийной ний и дополнений в автоматически полученную структуры путем восстановления умолчаний и ана- структуру выявлялись скрытые (неявные, не отра женные в тексте) знания автора или эксперта. Таким получения. Для того чтобы информация адекватно образом, происходило выделение понятийных свя- передавала в машинной форме знания автора, она зей, которые явно не присутствовали в анализируе- должна фиксироваться в виде контекстно мом тексте. обусловленных данных. Это возможно благодаря Также изложенные подходы к построению сис- использованию интерактивных методов и средств темы формирования и использования научной ин- построения формализованных представлений ин формации были реализованы в рамках проекта формации.

«Разработка и внедрение информационно- Использование уровневой семиотической моде аналитической системы регистрации, учёта, обра- ли дескриптивного представления предметных об ботки и хранения отчётных документов по НИОКР с ластей научных исследования позволяет нам утвер целью проведения мониторинга состояния и основ- ждать, что знаковое представление предметной об ных тенденций и направлений развития научных ласти дает возможность идентифицировать сущест исследований и разработок, выполняемых компа- венные свойства и связи самого объекта. Следова ниями государственного сектора, в том числе на- тельно, применение технологии формирования по правленных на реализацию приоритетных направ- нятийной структуры научного контента, в основу лений развития науки, технологий и техники в Рос- которой положена данная модель, позволяет строить сийской Федерации, а также критических техноло- средства автоматизированного построения форма гий Российской Федерации» 1. лизованных представлений информации.

В качестве программной основы использовалась документальная информационно-аналитическая Литература система xIRBIS [9], интегрированная с системой [1] Алексеев С.С., Морозов В.В., Симаков К.В. Ме лингвистического анализа АОТ.

тоды машинного обучения в задачах извлечения информации из текстов по эталону// Электрон 6 Направления дальнейшей работы ные библиотеки: перспективные методы и тех В дальнейшем планируется разработать модели нологии, электронные коллекции – RCDL’2009:

и методы представления построенной понятийной Труды Всерос. науч. конф. – 2009.

структуры в виде так называемого «навигационно- [2] Алыгулиев Р.М. Математическое программиро го» графа. Такие представления позволят пользова- вание в Text Mining// Электронные библиотеки:

телю перемещение (как по различным графам, так и перспективные методы и технологии, электрон по системе аспектных описаний предметных облас- ные коллекции - RCDL’2005: Труды Всерос. на тей («в ширину»), так и в пределах разных описа- уч. конф. – 2005.

тельных уровней представления предметных облас- [3] Барсегян А.А., Куприянов М.С., Степаненко тей («в глубину») с запоминанием траектории. В.В., Холод И.И. Технологии анализа данных:

Предполагается использование разработанного Data Mining, Visual Mining, Text Mining, OLAP.

комплекса в составе информационно-поисковой – СПб.: БХВ-Петербург, 2007.

системы, что сделает возможным представление [4] Вихнин А.Г., Сакипов Н.З. Штурм четвертого всех текстов отдельно взятой документальной базы мегапроекта: кто будет новым Биллом Гейтсом?

«навигационными» графами и формирования еди- Системный анализ и выбор стратегии. – М.:

ного графа предметной области. Это, в свою оче- «Диалог МИФИ», 2008.

редь, позволит осуществить нахождение соответст- [5] Джарратано Д., Гайли Г. Экспертные системы.

вий пользовательского запроса частям графа пред- Принципы разработки и программирования. – метной области. При этом структура «навигацион- М.: Издательский дом «Вильямс», 2007.

ного графа» позволит сначала выделить ту его [6] Дубейковский В.И. Практика функционального часть, которая наиболее точно соответствует запро- моделирования. – М.: «Диалог МИФИ», 2004.

[7] Кузнецов И.П., Мацкевич А.Г. Лингвистические су потребителя, а затем сформировать «траекторию и алгоритмические аспекты выделения объектов прохождения» потребителем информационного и связей из предметно-ориентированных тек массива для решения конкретной задачи.

стов // Труды межд. конф. по компьютерной лингвистике и интеллектуальным технологиям 7 Заключение «Диалог 2007», Бекасово, 2007. – C. 333-342.

В машинном виде существуют различные, с точ- [8] Леонтьева Н.Н., Кудряшова И.М., Соколова Е.Г.

ки зрения назначения, технологии создания и ис- Семантическая словарная статья в системе пользования, формы (и виды публикаций) представ- ФРАП//ПГЭПЛ. – М.: Ин-т русского языка АН ления знаний, но все они, так или иначе, представ- СССР, 1979. – Вып. 121. – С. 64.???

ляют собой тексты на естественных языках. Пред- [9] Максимов Н.В. Документальная информацион ставленные таким образом знания существуют объ- но-аналитическая система xIRBIS: программа ективно и независимо от истории (контекста) их для ЭВМ. / Максимов Н.В., Васина Е.Н., Голи цына О.Л. и др. // Свидетельство о гос. регист рации №2008611511 от 25.03.2008.

Федеральная целевая программа «Исследования и разра ботки по приоритетным направлениям развития научно технологического комплекса России на 2007– 2012»

[10] Мейен С.В., Шрейдер Ю.А. Методологические аспекты теории классификации //Вопросы фи лософии. – 1976. – №12. – С. 67-79.

[11] Попов Э.В. Общение с ЭВМ на естественном языке. – М.: Наука, 1982.

[12] Урманцев Ю.А. Общая теория систем: состоя ние, приложения и перспективы развития// Сборник «Система, Симметрия, Гармония». – М.: Мысль, 1988. – С. 38-124.

[13] Шрейдер Ю.А. Элементы семиотики. – М.: Зна ния, 1974.

[14] Autonomy IDOL. – http://www.autonomy.com/ content/Products/IDOL.

[15] Avicomp. – http://www.avicomp.ru/.

[16] Buckley C., Allan J., Salton G. Automatic routing and retrieval using SMART: TREC-2// Inf. Proc.& Manag. – 1986. – V. 31, No 3. – P. 315-326.

[17] Chen Hsinchun, Ng Tobun D., Martinez Joanne, Bruce R., Schatz. A concept space approach to ad dressing the vocabulary problem in scientific in formation retrieval: an experiment on the Worm Community System// J. of the American Society for Information Science. – January 1997. – V. 48, No 1.

[18] Gruber T.R. Towards principles for the design of ontologies used for knowledge sharing// Int. Work shop on Formal Ontology, March, Padova, Italy, 1993.

[19] Leontyeva N.N. ROSS: semantic dictionary for text understanding and summarization //META. – 1995.

– V. 40, No 1. – P. 178-184.

[20] Megaputer. – http://www.megaputer.com/products/ ta/index.php3.

[21] Salton G., Zhang Y. Enhancement of text represen tations using related document titles// Inf. Proc. & Manag. – 1986. – V. 22, No 5. – P. 385-394.

[22] TextAnalyst. – http://www.analyst.ru/.

Technology of the aided formation of conceptual structure of scientific content O.V. Okropishina Technology of the aided formation of conceptual struc tures (that represents knowledge domains on different descriptive levels) in form of sequence of statistic and linguistic scientific work text processing procedures, based on level semeiotic model of representation of knowledge domain of scientific investigation are con sidered.

Экономия времени как мера качества поисковой системы © И.Е. Куралёнок1, М.А. Скачков2, О.В. Басков Яндекс, г. 2Санкт-Петербург Санкт-Петербургский государственный университет solar@yandex-team.ru, skvmichael@yandex.ru, ov.japh@gmail.com Традиционным подходом оценки качества поис Аннотация ковой машины является Кренфилдский подход Данная статья описывает подход к оценке (Cranfield), основанный на сравнении результатов качества поисковых систем, основанный на поиска с эталонным результатом. Более полная времени удовлетворения пользователями их классификация способов оценки качества поиско информационной потребности. Статья вых машин, а также подробное описание Кренфилд включает описание математической моде- ского подхода приведены в [1].

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

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

мента, приводятся в части 4. В частях 5 и 6 полу - доля кликов на первый результат выдачи поис ченные выводы о качестве поисковых систем срав ковой машины по всем запросам, ниваются с Кренфилдской оценкой и оценками, ос - средняя позиция первого клика, нованными на других пользовательских метриках.

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

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

зователей на этом документе или в процессе поиска Определение этой степени влияния является слож [4, 5, 7]. Такие подходы имеют свои недостатки, ной задачей. При её решении возникает несколько поскольку достаточное количество статистики та- требующих внимания моментов:

ким образом можно собрать только для определён- - как смоделировать пользователя поисковой ного класса наиболее частотных пар «запрос – системы, чтобы обеспечить повтор?

документ». - как измерять степень влияния поисковой сис темы на время поиска?

Мы поставили эксперимент следующим образом. В Труды 12й Всероссийской научной конференции качестве участников эксперимента были взяты ре «Электронные библиотеки: перспективные методы и альные люди. Задачи составлялись на основе репре технологии, электронные коллекции» – RCDL’2010, Казань, Россия, 2010 зентативной выборки сессий пользователей одной Рис. 2. Распределение кликов Рис. 1. Максимальный просмотренный результат поиска мента получилось 4337 сессий, записанных в файлы по одной сессии на файл.

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

экране результатов первого поискового запроса. За Участники эксперимента в непринуждённой до конечную точку принято время, когда пользователь машней обстановке не спеша выполняли задания, отметил конец поисковой сессии. Поскольку поль сформулированные в виде одного предложения, зователь мог отвлекаться, то если время между со например, «выяснить, сколько стоит тур в Париж на седними действиями пользователя было больше 10 дней». Свободно распоряжаясь своим временем, определённого тайм-аута, этот отрезок вырезался из участники могли выполнять задания не сразу и пе рассматриваемого промежутка времени. В качестве риодически отвлекаться, позже возвращаясь к нему.

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

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

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

обще говоря, не всегда возможно;

В эксперименте принимали участие 41 человек.

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

лать один человек. Из них выполненными хотя бы Чтобы понять, похоже ли поведение участников одним участником эксперимента оказались 203.

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

задание, но в разных поисковых системах. В качест - максимально просмотренный результат поиска ве поисковых систем выступали 3 коммерческие (рис. 1);

поисковые системы Google, Yandex и Rambler. Сес - распределение кликов по результатам поиска сией будем называть последовательность действий (рис. 2);

одного пользователя для решения одного задания в - распределение запросов по времени (рис. 3).

одной поисковой системе. В результате экспери ния и пользователя на время поиска будем считать одинаковой.

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

t C /( SU ). (1) Выразим отсюда коэффициент качества поисковой системы:

S C /(tU ).

По сделанным выше предположениям коэффи циент пропорциональности является константой для любых значений S, C, U. Для упрощения задачи будем искать коэффициенты качества поисковых систем S не в чистом виде, а их соотношение для Рис. 3. Распределение всех запросов по времени разных систем. Таким образом, коэффициент про (в абсолютных величинах) порциональности сократится. Поэтому для просто Поскольку в выдаче поисковой системы Rambler ты вычислений будем считать его единицей изна на каждой странице присутствуют 15 результатов, а чально. Тогда формула (1) примет вид t = C /( SU ).

в поисковых системах Google и Yandex – по 10 ре зультатов, данные статистики рассматривались Для удобства возьмём натуральный логарифм только для заданий, выполненных в поисковых сис ln t = ln C ln S ln U.

темах Google и Yandex.

Эти графики выглядят естественно и соответст Запишем это уравнение для каждой сессии, полагая, вуют ранее полученным результатам. Например, в что их количество равно I,, количество заданий исследовании [2], посвящённом вопросу о том, как равно J, количество пользователей равно K, ко люди просматривают страницу результатов выдачи поисковой системы, приводится распределение про- личество поисковых систем равно M :

смотров результатов, которое примерно соответст ln ti = ln C j ln S m ln U k.

вует полученному графику распределения кликов.

3 Модель Имеем: bi = x j x j + k x j + k + m, b = Ax. Матрица A системы в каждой строке имеет 3 ненулевых Чтобы измерить степень влияния поисковой сис значения: одну 1 и две 1. Очевидно, эта система темы на время выполнения задания, необходимо смоделировать процесс поиска. Это очень сложная имеет достаточно много строк и не имеет решения в задача. Упростим её, введя некоторые дополнитель- чистом виде, поэтому будем искать ближайшее ре ные предположения. Ясно, что время выполнения шение методом наименьших квадратов:

задания зависит от поисковой системы, пользовате- x* = arg min( Ax t ).

ля, задания и от других аргументов, т. е.

Попарные соотношения экспонент от величин t = f ( s, u, c,...), где s – поисковая система, u – x*+ k + m дадут искомые результаты.

пользователь, c – задание. j В основе модели лежит предположение, что 4 Результаты эксперимента функцию времени можно разложить на независи мые сомножители, т. к. нам кажется, что сложность В ходе эксперимента описанная модель была задания и собственная скорость пользователя при применена к исходным данным следующим обра поиске не зависит от поисковой системы: зом. В качестве меры для определения невязки была t = f1 ( s ) f 2 (u ) f3 ( c ) f (...). взята евклидова мера. В качестве минимизирующе го алгоритма выбран метод сопряжённых градиен Функция f (...) не зависит от пользователя, по тов из-за простоты вычисления градиента линейной исковой системы и задания и является свойством функции. Полученные коэффициенты качества по самого эксперимента. Поэтому будем полагать её исковых систем приведены в табл. 1.

константой. За неимением лучших предположений, Из-за предположений, допущенных в модели функции f1 ( s ), f 2 (u ), f3 ( c ) будем считать линей (мы опустили коэффициент пропорциональности), ными, т. е. долю влияния поисковой системы, зада- эти коэффициенты нельзя рассматривать как неко торую метрику и сравнивать их в чистом виде с по добными коэффициентами, полученными другими Поскольку наша модель не определяет коэффи методами. Необходимо рассмотреть их соотноше- циенты качества поисковой системы напрямую, а ние. Для удобства выберем одну из поисковых сис- лишь только их соотношения, вычислим отношения тем, относительно которой будем нормировать по- MRR для рассматриваемых систем, при этом нор лученные коэффициенты. Нами была выбрана поис- мирование проведём относительно поисковой сис ковая система Rambler. Итоговые соотношения при- темы Rambler.

ведены в табл. 2.

Таблица 4. Отношения коэффициентов качества Таблица 1. Значение коэффициентов качества поисковых систем для модели на основе поисковых систем Кренфилдской статистики MRR Поисковая сис- Google / Rambler 1. ln S k Sk тема Yandex / Rambler 1. 1.54*10- Google -11.0840 Rambler / Rambler 1. 1.35*10- Yandex -11. Эти результаты отличаются от результатов, по 1.17*10- Rambler -11. лученных для модели на основе времени продолжи тельности сессии. При этом, если для поисковой Таблица 2. Отношения коэффициентов качества системы Google отличия незначительны, то поиско поисковых систем вую систему Yandex данная модель оценивает зна Google / Rambler 1.308 чительно ниже, чем модель на основе времени. Од Yandex / Rambler 1.151 нако модель на основе MRR ранжирует поисковые Rambler / Rambler 1.000 системы так же, отдавая первое место поисковой системе Google, второе – Yandex и третье – Rambler.

Из табл. 2 видно, что Google выступает лучше, чем Rambler, в смысле времени продолжительности 6 Связь с другими пользовательскими сессии в 1.308 раза. Это означает, что в поисковой метриками системе Google участники эксперимента в среднем быстрее решали поставленные задачи, чем в поис- Рассмотрим связь предложенной модели с моде ковой системе Rambler. Качество системы Yandex лями оценки качества поисковых систем на основе выше качества системы Rambler в 1.151 раза. Таким других метрик. Для исследования нами были вы образом, на момент проведения эксперимента поис- браны 4 пользовательские метрики:

ковую систему Google можно считать лучшей в - средняя позиция первого клика;

смысле времени поиска поисковой системой из рас- - доля коротких сессий (короткой будем назы сматриваемых, в то время как поисковая система вать сессию, длившуюся менее 1 минуты);

Rambler выступает хуже всех рассматриваемых сис- - вероятность клика на первую ссылку в выдаче тем. поисковой системы;

- средняя позиция последнего клика.

5 Связь с Кренфилдской оценкой Значения этих метрик на данных нашего экспе римента приведены в табл. 5.

Поскольку участники эксперимента отмечали Аналогично случаю Кренфилдской оценки вы специальным маркером те ресурсы, которые, по их числим соотношения между полученными метри мнению, полностью или частично удовлетворяли ками, обращая внимание на зависимость качества поставленному заданию, можно говорить о Крен поисковой системы от значения метрики (в случае филдских оценках. Сравним полученные результа метрик (2) и (3) зависимость прямая, в случае мет ты с оценками качества поисковых систем, осно рик (1) и (4) зависимость обратная). Результаты вы ванными на одной из таких оценок – mean reciprocal числения приведены в табл. 6.

rank (MRR). Напомним, что reciprocal rank (RR) оп Отсюда видно, что наиболее близкий к нашей ределяется как величина, обратная позиции первого модели оценки качества поисковой системы резуль корректного документа (в нашем случае – первого тат даёт метрика (1) – средняя позиция первого кли документа, отмеченного как хороший), а MRR явля ка.

ется средним значением RR по всем запросам. Та ким образом, MRR является величиной, которой Таблица 5. Значения пользовательских метрик можно характеризовать поисковую систему. Значе ния MRR для рассматриваемых поисковых систем Google Yandex Rambler приведены в табл. 3. 1.838 2.165 2. 1 Средняя позиция первого клика Таблица 3. Значение mean reciprocal rank 0.181 0.168 0. 2 Доля коротких для поисковых систем сессий (менее минуты) Поисковая система MRR 0.559 0.435 0. 3 Вероятность кли Google 0. ка на первую по Yandex 0.514 зицию Rambler 0. Таблица 6. Соотношения качества поисковых сис- [6] Chapelle O., Metlzer D., Zhang Ya, Grinspan P.

Expected reciprocal rank for graded relevance// тем для пользовательских метрик CIKM '09: Proc. of the 18th ACM Conf. on Infor mation and Knowledge Management.

Сред- Доля Вероят- Средняя [7] Joachims T., Granka L.A., Pan B., Hembrooke H., няя корот ность позиция Gay G. Accurately interpreting clickthrough data as пози- ких клика послед ция сессий на пер- него implicit feedback// SIGIR '05. – P. 154-161.

первого вую клика [8] Buckley C., Voorhees E.M. Retrieval system eval клика позицию uation// In E.M. Voorhees and D.K. Harman, edi 1.324 1.175 1.325 1. Google / tors, TREC: experiment and evaluation in informa Rambler tion retrieval. – MITT Press, 2005.

1.124 1.091 1.031 1. Yandex / [9] Turpin A., Scholer F. User performance versus Rambler precision measures for simple web search tasks// 1.000 1.000 1.000 1. Rambler / Proc. of the ACM SIGIR Int. Conf. on Research Rambler and Development in Information Retrieval, Seattle, WA, 2006. – P. 11–18.

7 Заключение и будущая работа Мы ввели новую метрику качества поисковых Time saving as a quality measure систем, основанную на влиянии поисковой системы of retrieval system на одно из важнейших пользовательских свойств – время поиска необходимой информации. Мы иссле I.E. Kuralenok, M.A. Skachkov, O.V. Baskov довали вопрос связи полученного способа оценки поисковой системы с моделью, основанной на од This paper describes an approach to assessing the qual ной из Кренфилдских метрик – позиция первого ity of search engines based on time to satisfy users’ просмотренного документа, отмеченного как удач information needs. The paper includes a description of ный. При этом были получены результаты, дающие the mathematical model, the results of its application to то же самое ранжирование поисковых систем по the experimental data simulating search engine logs and качеству, но отличающиеся по соотношению коэф a comparison of the results with estimates of search фициентов качества. Также были рассмотрены дру engines based on other custom metrics.

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

Мы считаем недостаточным сравнение предло женной модели с Кренфилдскими метриками, в то время как данные метрики являются широко ис пользуемыми. В будущем мы планируем связать нашу модель с другими оценками, такими, как MAP [8, 9], nDCG [3], ERR [6].

Литература [1] Кураленок И.Е., Некрестьянов И.С. Оценка сис тем текстового поиска// Программирование. – 2002. – Т. 28, №4. – С. 226-242.

[2] Google’s Golden Triangle. Eye Tracking Study, 2005. – http://www.enquiroresearch.com/images/ eyetracking2-sample.pdf.

[3] Yilmaz E., Kanoulas E., Aslam J.A. A simple and efficient sampling method for estimating AP and NDCG// SIGIR '08: Proc. of the 31st annual Int.

ACM SIGIR Conf. on Research and Development in Information Retrieval.

[4] Cen R., Liu Y., Zhang M., Zhou Bo, Ru L., Ma S.

Exploring relevance for clicks// CIKM '09: Proc. of the 18th ACM Conf. on Information and Knowl edge Management.

[5] Dupret G., Liao C. A model to estimate intrinsic document relevance from the clickthrough logs of a web search engine// WSDM '10: Proc. of the third ACM Int. Conf. on Web Search and Data Mining.

Оценка разнообразия результатов веб-поиска с помощью материалов Wikipedia © А.В. Стрелковский, И.Е. Кураленок С.-Петербургский государственный университет thinkingwhat@yandex.ru, solar@yandex-team.ru время как запросов вида «ягуар + конкретизирую Аннотация щие слова» было задано на порядок меньше. На Существует большое количество многозначных пример, второе место по количеству запросов, со поисковых запросов. Целью данной работы яв- держащих слово «ягуар», – запрос «ягуар напиток»

ляется оценка качества результатов, выдавае- – это всего лишь 7073 показа, третье место – запрос мых поисковыми системами по таким запросам, «ягуар машина» – 4653 показа.

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

ние метода увеличения количества тем в ответе Например, в [2] авторы предлагают метод оценки поисковой системы, основанного на кластери- качества поиска, принимающий во внимание разно зации результатов поиска. В качестве источника образие и объем новой информации, привносимой тем и неоднозначных терминов используются каждым документом в ответ системы. В [2] также материалы Википедии. упоминается ряд других работ, связанных с неодно значностью запросов. В [10] описан обучающийся 1 Введение алгоритм ранжирования, обеспечивающий наличие как минимум одного релевантного документа на Есть два подхода к решению проблемы ответа первых позициях ответа для любого пользователя, поисковой системы по неоднозначным запросам:

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

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

вило, владеет довольно скромным количеством ин Есть такая крупная онлайн-энциклопедия:

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

блема: многозначные термины. Решается она там с Поэтому стоит обратить внимание на генерализа помощью так называемых "disambiguation pages" – цию – именно она и будет далее обсуждаться.

страниц с перечислением и кратким описанием всех Рассмотрим пример неоднозначного запроса:

возможных тем по неоднозначному понятию. Если пусть это будет запрос «ягуар». Под ним можно термин, введенный пользователем, имеет несколько иметь в виду автомобильную компанию, напиток, значений, то он сначала попадает на такую страни животное, производителя металлических дверей и цу и на ней выбирает ту тему, которая его интересу т. д. Пользователь, отправивший такой запрос, мог ет. В данной работе для оценки разнообразия выда иметь в виду животное, и поэтому ответ из 10 ссы чи поисковиков используются данные disambi лок на сайты по продаже автомобилей его не удов guation-страниц Википедии.

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


пользователей (генерализация).

Пусть это снова будет слово «ягуар». Под ним Некоторым может показаться, что большая часть можно подразумевать, например, следующие вещи пользователей не будет задавать такие однослож (темы первых 10 запросов, содержащих данное сло ные и неоднозначные запросы, что логичнее доба во, по статистике Wordstat):

вить какие-то конкретизирующие слова, но стати • ягуар — напиток, стические данные wordstat.yandex.ru говорят об об • ягуар — машина, ратном. Рассмотрим тот же «ягуар»: по данным • ягуар — животное, Wordstat за последний месяц (относительно момен • ягуар — фильм та последней правки статьи) поисковой системе Яндекс было задано 71416 запросов «ягуар», в то http://wikipedia.org Посмотрим соответствующую disambiguation- того чтобы определить тему документа, находим страницу Википедии. Каждая тема на ней описыва- ближайший к вектору документа (построенному ется словосочетанием либо одним – двумя предло- тоже по bm25) вектор темы. Так как рассматрива жениями. Темы для рассматриваемого термина с ются tf-idf векторы, то в качестве расстояния между векторами x и y бралось = 1 – cos(x,y). Если рас этой страницы:

• ягуар — хищник семейства кошачьих, стояние от документа до найденного вектора темы меньше, чем некоторая заданная константа 3, то • Jaguar — английская автомобильная компания, документ относится к теме, соответствующей вы • Jaguar — слабоалкогольный напиток, бранному вектору, иначе – к теме "unclassified".

• Ягуар — название нескольких художественных Автор понимает, что такой способ классифика фильмов: фильм Себастьяна Аларкона (1986), ции не всегда дает идеальные результаты, но плю фильм Френсиса Вебера (1996), фильм Эрнеста сом этого метода является то, что он не смещен в Пинтоффа (1979), сторону какой-либо поисковой системы, так как • и еще 5 тем.

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

рое количество других тем.

Конечно, таким образом невозможно получить 3 Суть работы и результаты абсолютно все темы по любому понятию, но, так как Википедия является очень крупным ресурсом 3.1 Суть работы (3,288,067 статей на английском и 533,423 статьи на Для оценки разнообразия выдачи с помощью русском языках на момент написания работы), ко Википедии было набрано 576 неоднозначных рус торый наполнялся содержанием годами (запущена в ских понятий и 705 неоднозначных английских по январе 2001 года), ожидается, что оценки, получен нятий. Из каждого из этих наборов случайным обра ные с ее использованием, будут достаточно полны.

зом было выбрано по 300 понятий и проведена сле Также в 2007 году Wikipedia являлась первым по дующая процедура. По каждому понятию:

посещаемости сайтом в мире, посещенным после • запрос 10 результатов первой страницы от главной страницы Google. Википедия сейчас явля вета у систем Яндекс, Google, Yahoo;

ется самым крупным и наиболее популярным спра • запрос 100 результатов первой страницы вочником в интернете 2. По объёму сведений и тема ответа у системы Яндекс и кластеризация этих ре тическому охвату она считается самой полной эн зультатов с помощью алгоритмов K-Means (k = 75) циклопедией из когда-либо создававшихся за всю (см. [6] и [7]) и Quality Threshold 4 (см. [1]);

историю человечества.

• из набора кластеров, полученных с помо В работе описание каждой темы рассматривается как «мешок слов». По каждому описанию строится tf-idf вектор с tf по форме bm25 (см. [5]). Далее, для в работе полагается = 0. в работе использовалась вариация qt-алгоритма, описан согласно Alexa® (http://www.alexa.com) ная в [1] щью QT (Яндекс), выбиралось 10 самых крупных;

лапласиан графа. Рассматривались как нормирован далее из каждого из них с равной вероятностью вы- ный, так и ненормированный лапласианы, метод их биралось по одному документу, таким способом построения изложен в [3].

был получен четвертый набор из 10 документов;

Далее строились графики собственных чисел ла • то же самое делалось и для кластеров, по- пласиана.

лученных с помощью K-Means (Яндекс) – был по- Пример. Запрос: «война и мир», 100 документов;

лучен пятый набор из 10 документов;

система: Яндекс.

• запрос 100 результатов первой страницы График собственных чисел ненормированного ответа у системы Google и кластеризация этих ре- лапласиана (упорядочены по возрастанию, первое зультатов с помощью алгоритмов K-Means (k = 75) и собственное число не отображено на графике, так Quality Threshold4;

как оно равно нулю для любого лапласиана) пред • из набора кластеров, полученных с помо- ставлен на рис. 2.

щью QT (Google), выбиралось 10 самых крупных;

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

• то же самое делалось и для кластеров, по лученных с помощью K-Means (Google) – был по лучен седьмой набор из 10 документов;

• к полученным 7 наборам применялась классификация по способу, описанному ранее;

в итоге были образованы группы тем для каждого набора.

На рис. 1 представлена схема, поясняющая дан ную процедуру.

В процессе кластеризации использовались заго ловки и аннотации («сниппеты») документов, так как это как раз то, что видит пользователь в ответе Рис. системы, и, соответственно, это то, на основе чего Полагалось, что количество кластеров в выдаче он решает, к какой тематике относится тот или иной должно быть равно номеру того собственного чис документ. Сниппеты и заголовки при этом рассмат ла, после которого начинается резкий рост собст ривались как «мешки слов», по которым строились венных чисел (В примере можно положить количе tf-idf векторы.

ство кластеров равным 80). Данный эвристический Выбор документов из кластеров производился подход более подробно описан в [3]. Вообще такой случайным образом с целью сгладить их неодно способ определения количества кластеров можно родность (так как при выборе, например, медианы, обосновать по-разному, например, методами спек наличие «плохого» документа в кластере, т. е. дале тральной теории графов (см. [9]) либо при помощи кого по смыслу от остальных документов, может теории возмущений (в идеальном случае имеем k сильно сдвинуть эту самую медиану). В то же время несвязанных кластеров, при этом первые k собст вероятность выбора таким способом «плохого» до венных чисел лапласиана будут равны нулю, что кумента равна отношению количества этих «пло доказывается достаточно тривиально).

хих» документов в кластере к размеру самого кла стера.

3.3 Результаты Приведем некоторую общую статистику.

3.2 Спектральный анализ По английским понятиям:

Число кластеров k = 75 для алгоритма K-Means Система Общее количество тем по было подобрано на основе спектрального анализа 300 понятиям ([3], [4], [9]) результатов поиска по некоторому на Яндекс бору запросов. (K-Means был рассмотрен именно QT (Яндекс) из-за своей линейной по количеству кластеризуе K-Means (Яндекс) мых объектов вычислительной сложности, поэтому Google было решено не проводить спектральный анализ QT (Google) для результатов по каждому из рассматриваемых K-Means (Google) неоднозначных запросов, а взять среднее число по Yahoo уже полученной ранее статистике).

Суть анализа заключалась в рассмотрении мно По русским понятиям:

жества документов в выдаче поисковой системы в Общее количество тем по Система виде графа, вершинами которого являются доку 300 понятиям менты, а веса ребер положены равными cos(x,y), где Яндекс x и y – векторы, построенные по соответствующим QT (Яндекс) документам (т. е. вершинам графа). Далее строился ло 2% для K-Means). В то же время, выяснилось, что K-Means (Яндекс) поисковые системы Google и Yahoo в аспекте разно Google образия результатов существенно обходят Яндекс.

QT (Google) Что касается русских понятий, то тут немного K-Means (Google) иная картина: лидирует Google, за ним Яндекс, а Yahoo последним идет Yahoo. В данном случае кластери Как видно из результатов, для английских поня зация результат не улучшила ни для Яндекса, ни тий алгоритм QT позволил очень существенно для Google.

улучшить разнообразие выдачи Яндекса (примерно Ниже представлены диаграммы, иллюстрирую на 23.9%). Более быстрый алгоритм K-Means (лине щие соотношение количеств тем по различным за ен по k и n) также обеспечил улучшение, но не столь просам в ответах рассматриваемых поисковых сис значительное (около 14.2%). Для ответов поисковой тем (а также в выборках, полученных в результате системы Google обнаружилось более скромное кластеризации).

улучшение разнообразия (около 7.4% для QT и око Соотношение по двадцати русским запросам (запросы упорядочены по убыванию количества тем в Википедии, горизонтальная ось – ось номеров запросов, вертикальная – ось количеств тем) То же самое, но без столбцов по Википедии Только Яндекс (русскоязычные запросы) Здесь заметно, что столбцы по обычной выдаче Яндекса выше, чем столбцы по методам кластеризации.

Только Google (русскоязычные запросы) Здесь примерное равенство между обычным ответом Google и результатом работы обоих алгоритмов кластеризации. Заметна нестабильность K-Means (скачки).

Соотношение по двадцати английским запросам (запросы упорядочены по убыванию количества тем в Википедии;

горизонтальная ось – ось номеров запросов, вертикальная – ось количеств тем) То же самое, но без столбцов по Википедии На диаграмме видно, что столбцы, соответствующие методам кластеризации, в основном выше, чем столбцы, соответствующие обыкновенным ответам. Также можно заметить, что столбцы, соответствующие QT, тоже в среднем немного выше, чем столбцы K-Means.


Только Яндекс (англоязычные запросы) Здесь видно то улучшение, которое обеспечивает QT.

Только Google (англ. Запросы) Здесь улучшение не столь очевидно, но, всё же, для большинства запросов выигрывает один из алгорит мов кластеризации.

[10] Radlinski F., Kleinberg R., Joachims T. Learning 4 Заключение diverse rankings with multi-armed bandits. – 2008.

В работе проведено исследование разнообразия результатов веб-поиска и возможности его улучше- Evaluation of the diversity of web-search ния с помощью кластеризации. Было выяснено, что results with the help of Wikipedia materials кластеризация позволяет повысить количество тем в A.V. Strelkovskiy, I.E. Kuralenok ответах по англоязычным запросам рассмотренных поисковых систем. При этом сравнивались два алго- There are a lot of ambiguous search requests, which can ритма кластеризации: Quality Threshold и K-Means, be sent to a search engine by a user. The aim of this причем количество кластеров для алгоритма K- work is the evaluation of the quality of the results pro Means подбиралось на основе данных, полученных vided by search engines for such requests, with respect с помощью спектрального анализа результатов по- to the amount of topics presented in them. This work иска. also covers the research of a method of improving the Было также обнаружено, что алгоритм QT дей- diversity of web-search results, which is based on clus ствительно помогает существенно повысить разно- terization. The source of the ambiguous concepts and образие результатов, в то время как повышение раз- topics used in this work is Wikipedia.

нообразия от применения K-Means было менее за метно (но, всё же, это было улучшение). В случае же русскоязычных запросов кластеризация не дала положительных результатов ни для Яндекса, ни для Google. Также было проведено сравнение качества выдачи поисковых систем Яндекс, Google и Yahoo с точки зрения разнообразия и выявлено, что по анг лийским запросам лидирует Yahoo, за ним идет Google, а последний – Яндекс, а по русским – лиди рует Google, за ним с небольшим разрывом – Ян декс, последний – Yahoo.

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

Литература [1] Heyer L.J. et al. Exploring expression data: identifi cation and analysis of coexpressed genes// Genome Research. – 2009. – V. 9. – P. 1106-1115.

[2] Clarke C.L.A. Kolla C.M., Cormack G.V., Vechto mova O., Ashkan A., Bttcher S., MacKinnon I.

Novelty and diversity in information retrieval evalu ation. – University of Waterloo.

[3] von Luxburg U. A tutorial on spectral clustering// Statistics and Computing. – 2007. – V. 17, No 4.

[4] Ng A.Y., Jordan M.I., Weiss Y. On spectral cluster ing: analysis and an algorithm//NIPS 14, 2001.

[5] Robertson S.E., Walker S., Hancock-Beaulieu M.

Okapi at TREC-7//Proc. of the Seventh Text RE trieval Conf., Gaithersburg, USA, November 1998.

[6] Aloise D., Deshpande A., Hansen P., Popat P. NP hardness of Euclidean sum-of-squares clustering// Machine Learning. – 2009. – V. 75. – P. 245-249.

[7] Kanungo T., Mount D.M., Netanyahu N.S., Piatko C.D., Silverman R., Wu A.Y. An efficient k means clustering algorithm: analysis and implemen tation// IEEE Trans. Pattern Analysis and Machine Intelligence. – 2002. – V. 24. – P. 881-892.

[8] Hartigan J.A. Clustering algorithms. – Wiley, 1975.

[9] Chung F. Spectral graph theory// CBMS Regional Conf. Series in Math., Conference Board of the Ma thematical Sciences, Washington, 1997. – V. 92.

О функции поиска в электронной библиотеке © В.А. Резниченко, Г.Ю. Проскудина Институт программных систем НАН Украины, г. Киев reznich@isofts.kiev.ua, gupros@isofts.kiev.ua лиотечной системы, работающей с ее использовани Аннотация ем.

Работа посвящена описанию функции поиска в электронной библиотеке. На примерах реально 2 Lucene действующей информационной системы рассмот рены все аспекты функции поиска, включая син- Lucene – высокопроизводительная и масштаби таксис запроса поисковой библиотеки программ руемая библиотека Java-программ (один JAR-файл Lucene. Рассмотрены также модели поиска, поло размером менее 1 Мб, не имеющий зависимостей) женные в основу работы Lucene, и описаны осо или набор инструментов для осуществления инфор бенности ранжирования документов.

мационного поиска, которая не предназначена для использования в качестве автономного продукта, не 1 Введение содержит поисковых роботов (веб-краулеров), В рамках развития вопросов, связанных с всесто- фильтров документов и поискового интерфейса ронним описанием современных систем электронных пользователя. Тем не менее, в качестве подтвержде библиотек [1], наряду с описанием информационной ния популярности Lucene можно привести целый ряд составляющей предпринимается попытка макси- полнофункциональных приложений поиска, которые мально полно описать также ее функциональную были интегрированы либо построены на ее основе. В составляющую. дополнение к тем организациям, что перечислены на странице Wiki Lucene 1, можно привести и другие Функциональная часть электронных библиотек крупные и известные многонациональные организа (ЭБ) представляет собой различные возможности и ции, работающие с использованием Lucene. Она пре услуги, предоставляемые пользователям ЭБ. Это доставляет возможности поиска в системе DSpace, наиболее объемная и наиболее открытая часть, по одной из наиболее широко распространенных систем скольку охватывает всю обработку ресурсов, а также электронных библиотек.

действия пользователей в ЭБ. Функции в ЭБ можно О популярности Lucene также говорит и тот факт, условно разделить на пять классов: доступа к ресур что хотя она написана на Java, существуют много сам;

управления ресурсами;

совместной работы;

численные способы доступа (порты) к функциональ управления и настройки ЭБ [2].

ности Lucene из других программных сред (C/C++, Данная работа посвящена описанию функции по C#, Ruby, Perl, Python, PHP и др.).

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

нике данных, его формате и даже его языке. Это оз Учитывая возрастающие пользовательские требо начает, что можно индексировать и производить по вания к поисковым возможностям, а также тот факт, иск данных, хранящихся в файлах, например, веб что современные популярные поисковые веб страницах на удаленных веб-серверах, документов, системы (в частности, Google) в значительной степе хранящихся в локальный файловой системе, простых ни уже установили базовые требования, пользовате текстовых файлов, документов Microsoft Word, XML, ли ожидают примерно того же и от библиотечных HTML, PDF-файлов или файлов любого другого приложений. Поэтому разработчики популярных формата, из которого можно извлечь текстовую ин библиотечных систем могут использовать уже гото формацию.

вые приложения или библиотеки программ.

Поиск представляет собой процесс нахождения Хорошим примером здесь может служить добав слов в индексе, с помощью которого находятся до ление функций индексирования и поиска в библио кументы, содержащие эти слова. Индекс – это специ течные приложения, базирующееся на библиотеке ально разработанная структура данных, хранящаяся в программ Lucene [3]. В этой работе на примерах файловой системе в виде набора индексных файлов и приводится описание поисковых возможностей биб являющаяся инструментом поиска. Качество поиска, как правило, описывается с помощью показателей Труды 12ой Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» – RCDL2010, http://wiki.apache.org/lucene-java/PoweredBy Казань, Россия, • точности и полноты. Полнота показывает, насколько выбор ресурсов определенного вида (книги, хорошо система поиска находит соответствующие журналы, диссертации и др.);

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

возможность быстрого поиска в текстах большого • использование иерархических словарей по объема;

поддержку одно- и многословных запросов, исковых терминов, предметных рубрикаторов, тезау запросов фраз, групповых символов, нечетких запро- русов или классификаторов.

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

какой-либо библиотечной системе. Исходя из высо Результаты поиска могут быть отсортированы по ких пользовательских требований к поисковым ма автору;

названию;

дате выпуска;

степени релевант шинам, можно утверждать, что предоставление как ности;

другим характеристикам.

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

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

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

сов, в которые заносятся значения параметров, зада • поисковые термины должны состоять из от ваемых пользователем. Там, где возможно, значения дельных поисковых слов или фраз;

поисковых терминов выбираются из заданных спи • отсечение окончания или начала слов в по сков (например, язык документа, формат документа, исковых терминах;

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

няющих один или несколько символов: знак вопроса Как правило, системы ЭБ предоставляют сле (?) может представлять какой-либо одиночный сим дующие варианты поиска:

вол;

звездочка (*) используется для представления простой или стандартный поиск;

какого-либо символа или группы символов);

расширенный поиск;

• использование булевой логики (как правило, профессиональный поиск.

логических связок И-ИЛИ-НЕ);

Пользователь имеет возможность самостоятельно • поиск по словоформам и синонимам поиско выбирать тот или иной поиск.

вых терминов, а также с учетом морфологии языка (поиск слова во всех его морфологических формах), 3.1 Простой или стандартный поиск на котором формулируются поисковые термины;

Стандартный поиск – простейший вариант поис- • чувствительность или нечувствительность к ка, он представляет некоторые минимальные поиско- регистру символов;

вые возможности, которыми может легко овладеть • поиск по близости размещения слов в тексте;

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

всех индексах, которые построены в системе, т. е. во Основу поискового языка составляют поисковые всех описательных полях и во всех текстах. Боль термины. Существует два вида терминов: слова и шинство поисковых запросов формулируется с ис фразы, использование которых опишем подробнее.

пользованием возможностей именно этого вида по иска. 3.1.1 Поиск слов В современных системах ЭБ можно сузить про 1) Поиск отдельных слов – осуществляет нахож странство поиска, а также осуществлять многошаго дение наличия того или иного слова среди всех опи вый поиск. Сужение пространства поиска преду сательных полей, а также в тексте статей. Так, на сматривает возможность отделить подмножество информационных разыскиваемых ресурсов. Крите риями такого отделения могут быть следующие:

пример, если использовать в качестве простого поис- просе указываем Ан?с?мов. Разумеется, что этого ка слово Резниченко, то получим результат 2, где не можно достичь в случае, когда написание фамилии (или другого поискового слова) отличается только все найденные статьи имеют в качестве автора Рез отдельными буквами в одних и тех же позициях сло ниченко, среди найденных есть статьи с автором ва. Можно использовать несколько подряд располо Резніченко (написание фамилии на украинском женных символов ?. Так, например, если использо языке), а также статья, в которой только один автор – вать поисковое слово алекс??в, то будут найдены Стадник. Подчеркнем, что в простой поиск вовлека статьи с авторами Алексеев, Алексеєв и Алексєєв.

ются все описательные поля, а также полные тексты Символ * используется в том случае, когда в слове статей. И, скорее всего, это поисковое слово встреча известна лишь некоторая последовательность симво ется в текстах (например, в списке литературы тех лов, а другие – не известны. Например, спрашиваю статей, где автором является Резніченко). Так как щий помнит, что фамилия точно начинается на Ан поиск проводится по всем описательным полям, то, тон, но следующие буквы не помнит. В этом случае например, используя в качестве поискового слова нужно использовать поисковое слово Антон*, и бу УДК – 004.82, можно получить все статьи данной дут найдены все те статьи, в которых фамилия автора библиотеки с этим УДК. Но при этом следует пом начинается на нужные символы, например, Антонюк, нить, что 004.82 может встречаться в других полях, Антонцева, Антонов, Антонова (и некоторые дру например, в аннотации или тексте самой статьи. Но наибольшей будет вероятность того, что в найден- гие, в которых поисковое слово находится в других описательных полях или в текстах статей). Можно ных статьях слово 004.82 встречается в УДК.

одновременно использовать символы * и ?. Напри 2) Слова, по которым не производится поиск, мер, поисковое слово Р?зн*е?ко является коррект стоп-слова. Механизм поиска игнорирует некоторые ным, здесь отыскиваются все те статьи, которые со слова, которые часто встречаются в языке, однако ответствуют его содержанию. Заметим, что не раз являются бессмысленными с точки зрения поиска. К решается использовать символы ? и * в начале слова.

ним относятся, например, в английском языке: a, В этом случае и во всех других, когда поисковый and, are, as, at, be, but, by, for, if, in, into, is, запрос сформулирован неправильно, выводится со it, no, not, of, on, or, such, the, to, was. Если ука общение, что не правильно сформулирован поиско зать в качестве поискового слова какое-либо из этих вый запрос.

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

найдены статьи, которые содержат однокоренные 3) Поиск по нескольким словам. В поисковом за слова, например, семантические, семантическому, просе можно указать несколько слов. В этом случае семантическими и т. д., а также такие близкие по производится поиск статей, которые содержат какие звучанию слова, такие, как генетический, стати либо из указанных слов. Нет каких-либо ограниче ний на количество слов в поисковом запросе. ческий, механические, органический, электри 4) Использование в словах групповых символов. ческие, математический, электрический и т. д.

Групповой символ – это специальный символ, кото- Также можно указать дополнительный (факульта рый замещает один или несколько символов в поис- тивный) параметр, показывающий меру близости ковом слове. Существует два групповых символа: звучания слов и находящийся в интервале 0 – 1. На знак вопроса (?) и звездочка (*). Знак вопроса заме- пример, cемантический~0.4. Чем больше число, щает какой-либо одиночный символ в слове в том тем большая понадобится схожесть звучания. На месте, где он расположен. Символ * используется пример, с использованием выражения для представления какого-либо символа или группы cемантический~0.8 в тестируемой ЭБ были найде символов. Символ ? можно использовать, например, ны статьи только с однокоренными словами, но не если спрашивающий не знает точного написания были найдены другие однокоренные слова, которые поискового слова. Например, если он точно не знает, не так близки по звучанию, например, семантиче как пишется английское слово dynamic или скому, семантического. Если мера близости звуча dinamic, то можно указать в поисковом запросе ния не указывается, то по умолчанию используется d?namic. Другой вариант возможного использования значение 0.5. Следует отметить, что поиск по близо – если фамилия автора в разных статьях указывается сти звучания слова выполняется с использованием на украинском либо на русском языке, например, алгоритма нахождения минимального расстояния Анісімов и Анисимов. Если нужно найти все статьи редактирования, описание которого можно найти, этого автора, не учитывая языка, то в поисковом за- например, в [4].

3.1.2 Поиск фраз Все представленные в работе примеры проверены в Фраза – это последовательность слов, располо библиотечной системе http://dspace.nbuv.gov.ua:8080/dspace женных в двойных кавычках. Например, фразами лення и онтологій удалить слова бібліотечних и являются база данных, исчисление предикатов, за, то между ними расположено 6 слов. Если указать семантическая сеть. При использовании фразы расстояние 5, то эта статья не будет найдена. Отме осуществляется поиск статей, в которых содержится тим, что порядок промежуточных слов не является указанная фраза, т. е. именно такая последователь- существенным.

ность слов. Например, если указать фразу 3) Поиск по важности слов или фраз. Когда пе речисляются слова или фразы, предоставляется воз knowledge base, то можно получить результат, ко можность указать, какие из них являются более важ торый содержит украиноязычные и русскоязычные ными (релевантными). Важность слов и фраз влияет статьи. Статья может иметь дополнительное англоя на порядок расположения статей в результате поис зычное название или англоязычную аннотацию, или ка. Сначала следуют статьи с наиболее важными эта фраза встречается в тексте статьи, например, сре словами/фразами, а потом с менее важными. Для ди перечня использованной литературы.



Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |   ...   | 26 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.