Елизаров А.М. Математические методы в библиотечной работе

Подождите немного. Документ загружается.

информационном поиске в ИПС. Следовательно, здесь

можно исиользовать те же математические модели,

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

просу в ИПС. Тем самым определяется способ уста-

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

фонда.

Рассмотрим множества документов фонда D и

новых документов R,> заиндексированных при помощи

n линейно-упорядоченных терминов. Тогда любой

документ D представляется в виде n-мерного вектора

D = (d

, d

,..., d

); аналогичным образом представляются

новые документы R = (r

, r

,..., r

). Пусть ин-

дексирование будет бинарным, т. е.

)= 1,если документ D(R) содержит i-й термин,

0 в остальных случаях.

Предположим, что имеется выборка из р

документов фонда и q новых документов, а также

(pxq)- матрица релевантности Z=(z..) со следующими

свойствами:

1, если 1-й документ D

релевантен j-му ново-

= му документу R

в остальных случаях.

Предположим, что заданы функция совпадения f

документов D

и R

и пороговое значение T

, при ко-

тором документ R

включается в фонд тогда и только

тогда, когда f (D

, R

) ≥ Т

. Функция f измеряет сте-

пень близости векторов документов на основе подо-

бия соответствующих терминов этих векторов. В

частности, число совпадений (или несовпадений)

терминов для двух бинарных векторов можно опре-

делить как количество терминов, содержащиеся

в обоих векторах (соответственно как количество

терминов, содержащихся в одном векторе и отсут-

ствующих в другом). В первом случае мы вычисляем

количество общих единиц у двух векторов, а во втором

— берем количество пар неодинаковых координат

одного номера. Например, если D = (1, 0, 1, 1), R

= (1, 0, 0, 1), то число совпадений терминов равно 2

(термины № 1 и № 4), а число несовпадений есть 1

(термин № 3). Выбор функции f в указанном виде

соответствует стратегии „на пересечение" включения

документа в фонд. Возможен выбор стратегий „на

включение" и „на совпадение", когда все термины

нового документа включаются или совпадают с на-

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

201

С другой стороны, индексационные термины не-

равнозначны и играют различную роль при индекси-

ровании. Поэтому между ними необходимо зафикси-

ровать отношения, определяющие их роль при

индексировании. Такие отношения задаются в виде

классификации терминов, когда каждый термин пред-

ставляется как k-мерный бинарный вектор t =

=(t

, t

, ..., t

), где

1, если термин t входит в класс i,

= 0, если термин t не входит в класс i,

а, если нет сведений относительно вхождения t

в класс i.

Вектор t = (t

, t

, ..., t

), построенный указанным об-

разом, называется вектором класса. Если данный

термин относится к нескольким классам, его вектор

класса имеет более одной единицы.

Теперь для любой пары терминов нетрудно опре-

делить понятие совпадения (несовпадения) классов,

используя векторы классов (аналогично определенно-

му выше совпадению и несовпадению терминов).

Совпадение (соответственно несовпадение) классов

определяется, как количество единиц, совместно со-

держащихся в обоих векторах (соответственно со-

держащихся только в одном, но не содержащихся

в другом векторе). В этом случае введение неопре-

деленного условия а не считается ни совпадением,

ни несовпадением.

При определении степени подобия новых доку-

ментов и документов фонда имеется возможность

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

определив следующим образом для R и D k-мерные

вектора классов R

и D

1, если некоторый из терминов R(D) входит

в класс i (у терминов при отнесении к клас-

су i стоит по меньшей мере одна 1 на месте

соответствующей координаты);

0, если ни один из терминов R (D) не входит

в класс i (терминам присваивается значение

0 или а);

а, если все термины R(D) относительно клас-

са i имеют значение а.

Другими словами, правило построения координат

вектора класса документов по координатам вектора

классов терминов таково:

202

а 0 = 0, а 1 = 1, 0 1 = 1, а а = а.

Характерной функцией совпадения является f = = (А -

В)/(А + В) + (А' — B')/(A' + В') где A и B -число

совпадений и несовпадений терминов, А' и B' —

число совпадений и несовпадений классов.

Заметим, что при описанной процедуре особую

роль играют общие термины в сравниваемых векторах-

Очевидно, что они приписываются к совпадениям

терминов. Если же общий термин содержится и в

некотором классе С, происходит дополнительное сов-

падение классов. Поэтому общие термины приобре-

тают чрезмерный вес. Чтобы избежать этого ослож-

нения, обычно перед вычислением совпадений и

несовпадений классов из рассмотрения исключают

все общие термины.

Сформулируем, используя теоретико-множествен-

ные операции, процедуру сопоставления новых доку-

ментов R с документами фонда D на основании их

векторов терминов и классов.

1. Находим D ∩R, D\R, R\D.

2. Вычисляем число А совпадений терминов из

D∩R и число В несовпадений терминов из

D\R

R\D.

Строим вектор класса для

D\R

R\D

(обоз-

начения (D\R)

и (R\D)

4. Вычисляем числа А' и B' совпадений и несов-

падений (D\R)

и (R\D)

5. Вычисляем значения функции f и, сравнивая

его с пороговым значением, выносим решение

о включении документа в фонд.

Пример, Даны матрица,

состоящая из векторов клас-

са данного набора терминов

, Т

, ..., Т

, документ

фонда D = (0, 0, 0, 0, 1, 1, 1, 1),

новый документ R = (0, 1, 1,

0, 0, 1, 1, 0) и пороговое зна-

чение |f(D, R)| ≥,0, 1. Имеем

D\R = (0, 0, 0, 0, 1, 0, 0, 1),

R\D = (0, 1, 1, 0, 0, 0, 0, 0),

D∩R = (0, 0, 0, 0, 0,1, 1, 0),

A = 2, В = 4;

203

Таблица 36

. Классы

Термины

(D\R)

= (0, 0, а, а, 1) (1, а, а, а, 0) = (1, 0, а, а, 1);

(R\D)

=(а, 0, 0, 1, 0) (0, а, а, а, 0) = (0, 0, 0, 1, 1),

А' = 1, В'=1. Следовательно, |f(D, R)| = |—2/6+0|=

= 1/3 > 0,1, т. е. документ R нужно включать в фонд.

В заключение отметим, что описанная процедура

установления соответствия двух документов может

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

R и документа D при заданном пороговом значении

и в неизменном виде может использоваться в каче-

стве способа информационного поиска в ИПС.

2. Процессы каталогизации. Под библиотечными

каталогами понимают перечень произведений печати,

составленный в определенном порядке и имеющий

своими задачами раскрытие содержания фонда, по-

мощь пользователям в выборе документов, руковод-

ство чтением.

Удобный и предсказуемый порядок размещения

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

мации — в каталогах, обеспечивают библиотечные

системы классификации.

Понятие классификации толкуется теперь настолько

широко, что любой класс определяется просто как

множество терминов, обозначающих некоторую пред-

метную область. Классы присваиваются документам

для обозначения их смыслового содержания, причем

между классами могут задаваться некоторые отно-

шения. Системам классификации можно присваивать

различные формальные свойства. Наконец, классифи-

кация может быть упорядочена путем установления

систематических отношений между классами.

При каталогизации предпочтительнее иметь менее

жесткие требования, т. к. документы и термины не

бывают определены настолько точно, чтобы имело

смысл строить классы по одному признаку. По этой

же причине наилучшими должны считаться пересе-

кающиеся классы, чтобы элемент мог включаться

более чем в один класс. В некоторых случаях целе-

сообразно создание либо упорядоченных классифи-

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

ментов. Но когда не налагается никаких специальных

oграничений, неупорядоченная классификация дает, как

правило, более разумное деление на классы.

Процесс классификации можно охарактеризовать

математически, исходя из используемых параметров

204

Рис. 67.

и типа формируемых классов. Классы можно охарак-

теризовать теми свойствами подобия, которыми обла-

дают входящие в них объекты: а) каждый объект

подобен каждому из остальных объектов класса

(клика); б) каждый объект подобен одному объекту,

расположенному в центре (звезда); в) объект 1 подо-

бен объекту 2 и т. д. (цепь); г) подобие каждого

объекта множеству других объектов группы превы-

шает определенное пороговое значение (кламп). Все

эти схемы представлены на рис. 67.

В ИПС и каталогах между индексированием и

классификацией существует тесная взаимосвязь. Клас-

сификация терминов, пригодных для поиска, зависит,

очевидно, от терминов, используемых для идентифи-

кации единиц информации. При информационном

поиске каждому документу сопоставляется его ПОД

в виде набора индексационных терминов. Поэтому

используемые термины непосредственно оказывают

влияние как на классификацию терминов, так и на

классификацию документов. Таким образом, классы

документов непосредственно зависят от методов

индексирования.

При практическом использовании классификаций

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

при помощи одного или нескольких идентификаторов,

нарываемых профилем класса или центроидом. Про-

филь класса может быть представлен некоторым

формальным объектом, расположенным в центре

класса, или любым представительным объектом,

способным характеризовать все остальные. Поскольку

объекты, относящиеся к одному классу, должны об-

ладать бoльшим подобием, чем относящиеся к раз-

личным классам, ясно, что каждый объект должен

205

иметь большее сходство с профилем своего класса,

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

ное определение профилей является важным условием

успешной работы каталога.

Пусть класс С состоит из объектов D

: C =

=(D

, D

, ..., D

). Тогда можно выделять следующие

виды профилей:

1. Логический профиль P

. Если D

= (d

, d

..., d

) - такой набор терминов, что d

=1, если

термин у относится к объекту D

и d

= 0 в против

ном случае, то профиль P

определяется в виде

= (p

, p

)=D

... D

т. е. p

= 1 тогда и только тогда, когда по крайней

мере один объект класса содержит термин j. В осталь-

ных случаях P

= 0.

2. Профиль частотности документа Р

. Если

каж-

дому документу соответствует одно и то же описа

ние, можно использовать взвешенный профиль, когда

вес каждого термина р

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

ментов, содержащих данный термин j. Имеем Р

= (p

...,

)=D

+...+D

где d

= 1 при

условии, что термин у относится к D

, в остальных

случаям d

= 0.

3. Профиль частотности термина Р

. Если d

—

значимость (весовой коэффициент), приписанная j-му

термину в D

, то Р

= (р

, р

, ..., р

) = D

+ D

+ ... + D

, где р

— суммарный вес термина у во всех

документах массива.

Можно ввести различные коэффициенты нормали-

зации. Например, можно нормализовать термин в Р

, если делить на число п документов в классе. При

этом получается определение, аналогичное опре-

делению центра масс Р

Другой способ

нормализации предполагает деление каждого доку-

мента на его длину | D

|, т. е.

Оста-

новимся на одном способе разбиения массива из n

документов D

, D

, ..., D

на классы. Этот способ

основан на построении полной матрицы подобия раз-

мера п

, в которой каждой паре {D

, D

} ставится

206

в соответствие коэффициент s

подобия документов D

и D

(табл. 37). Очевидно, матрица симметрична относительно

главной диагонали.

Таблица 37

Обычно выбирают пороговое значение Т

и приводят

матрицу подобия к бинарному виду путем замены всех

коэффициентов подобия, больших T

—единицей, а меньших

—нулем. Далее искомые классы определяются

как клики, которые могут быть получены из бинарной матри-

цы подобия. При этом совершаются следующие опе-

рации:

1) отождествляем документы D

и D

имеющие

коэффициент s

=l (т. е. соединяем вершины D

графа ребрами, если s

= 1);

2) для каждой пары вершин D

и D

находим все

такие D

(k ≠ i, j), что s

=1, и соединяем их

с D

и D

соответственно;

3) затем для полученных троек D

, D

находим

четвертые вершины, которые можно соединить с

ними, исходя из правила равенства 1 соответствую

щего коэффициента в матрице подобия;

4) процесс продолжаем до тех пор, пока не будут

исчерпаны все подграфы максимальной размерности.

Каждый такой подграф (клика) определяет класс

разбиения.

В процессах каталогизации и информационного поиска

большое значение имеют различные методы упорядочения

данных, позволяющие сократить время поиска нужных

сведений и избежать сплошного перебора. Упорядочение

состоит в том, что на исходном множестве тем или иным

способом задается отношение порядка (см. п. 4 § 3). При

этом существенным является то, в какой степени это

отношение упорядочивает исходное множество. С этой

точки зрения мы различали линейный и частичный порядок.

Например, упорядочение записей каталога на основании

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

называется лексикографическим. Наиболее интересным

является древесный порядок. Заметим, что линейный

порядок удобен при организации „руч-

207

ного" хранения данных в виде картотек, книг и т. п.

предназначенных для непосредственного чтения чело-

веком. В то же время для „машинного" хранения и

поиска в большинстве случаев оказывается более

эффективным древесный порядок. Рассмотрим не-

сколько примеров.

При выборе способа организации данных приходится,

в первую очередь, учитывать два фактора: скорость

поиска и удобство пополнения массива данных. С

обеих точек зрения последовательная организация

массива оказывается неэффективной. Значительно

эффективнее организация данных по схеме

бинарного дерева, позволяющая осуществить быстрый

поиск и производить пополнение массива новыми

данными без перестройки уже

имеющейся системы упорядочения.

Пусть единицами данных являются

числа, например, 70, 820, 850, 68, 900,

30, 250, 410, упорядочиваемые в

порядке поступления.

Принцип упорядочения по схеме

бинарного дерева состоит в сле-

дующем: первая запись а

(число 70)

объявляется входом в массив

Рис. 68. Упорядоче- (корнем дерева). Каждое после-

ние по схеме бинар-

дующее число а

сравнивается с

ного дерева первым и связывается с ним пра-

вой подчиняющей стрелкой, если a

, либо левой

подчиняющей стрелкой, если a

< а

(считаем, что

двух одинаковых записей в массиве нет). Если соот-

ветствующая cтрелка уже проведена, а

сравнивается с

числом, присоединенным этой стрелкой, с теми же

исходами и т. д. На рис. 68 показано упорядочение

данного набора чисел.

Если допустить, что число 70 по величине соот-

вeтствует середине массива и числа во входном маc-

сиве хорошо перемешаны (а это означает, что дерево

растет равномерно по всем направлениям), то поиск

нужной записи в массиве из N записей будет произ-

водиться в среднем за n=log

N шагов.

Довольно часто поиск должен производиться в

больших, массивах данных, отличающихся только по

некоторым из своих элементов. В этом случае можно

упорядочить такие данные по схеме дерева. Напри-

208

мер, в алфавитном каталоге фамилии авторов мoгут

следовать в таком порядке:

Корин

Королев

Короткое

Котин

Котов

Котовский

Котон...

У соседних авторов начала фамилий (2—3—4 и

более букв) совпадают. В связи с этим возникает

идея — повторяющиеся части фамилий записывать

только один раз, добавляя лишь

отличающиеся окончания. По-

следовательная реализация этой

идеи приводит к представлению

данных по схеме ориентирован-

ного дерева так, чтобы каждая

,,запись" распределялась по де-

реву от корня до концевой

вершины (рис. 69). Соответствен-

но одно дерево представляет

столько записей, сколько у него Рис. 69.

концевых вершин. Всего же деревьев требуется

столько, сколько различающихся начальных элементов

(например, первых букв фамилии) имеют записи

массива. В данном примере обычное для каталога

последовательное представление фамилий (даже без

учета разделителей) занимает объем в 50 символов;

представление по схеме дерева занимает в два раза

меньший объем. Описанная схема, организации данных

будет тем эффективнее, чем больше кратность

повторяющихся элементов в записях массива.

3. Полнота библиотечного фонда. Одной из самых

сложных проблем теории формирования библиотек

ного фонда является проблема его оптимальной пол-

ноты. Относительно полно подобранный фонд дает

возможность с оптимальной полнотой удовлетворить

читательские запросы.

В предыдущем пункте обсуждались критерии вклю-

чения документа в фонд в смысле соответствия из-

14 т-743 209

дания профилю фонда. Обозначим этот показатель с

и будем считать, что он может принимать значения

от 0 до 1. Из построений п. 1 следует, что чем больше

признаков фонда отражено в его модели, тем точнее

показатель с. Каждый признак в зависимости от своей

важности получает собственный весомый коэффициент,

максимальное значение которого также не превосходит

единицы. Если, например, с оценивается по четырем

признакам c

, c

, с

(соответствие профильной теме,

типу, виду и языку), то в итоге после оценки

каждого коэффициента будем иметь

с = с

. Кроме соответствия издания профи-

лю библиотеки, нужно иметь признак, на основе ко-

торого можно судить, заслуживает ли издание при-

обретения и сохранения в фонде при вторичном от-

боре. Таким признаком является ценность, выражаю-

щаяся в виде Ц = И• с, где показатель И характери-

зует степень информативности содержания, 0 ≤ И ≤ 1, а

с — введенный выше показатель. Подавляющее боль-

шинство библиотек стремится отобрать в фонд изда-

ния возможно большей ценности. При этом чем

меньше библиотечный фонд по величине, тем более

высокой ценности должны быть составляющие его

издания. Итог определения показателя информатив-

ности И выражается количественно с тем большим

приближением к объективности, чем больше число

показателей и методов определения при этом исполь-

зовано. Однако даже при полном наличии всех приз-

наков информативности издание может быть не вклю-

чено в фонд, если оно там уже имеется. В этом

случае считаем И=0.

При оценке правильности политики комплектова-

ния наибольшую сложность представляет выбор кри-

терия, устанавливающего соответствие между дос-

тигнутыми целями и затратами на их достижение.

В качестве такого критерия обычно берут отношение

величин, характеризующих эффективность совершен-

ных действий и стоимость сделанных затрат. Приме-

нительно к комплектованию этот критерий можно

сформулировать как отношение количества запросов

на данный документ к стоимости его приобретения.

Известны и другие критерии. Если исходить из того,

что для достижения максимальной эффективности оп-

ределяющим является нахождение оптимального со-

210