итерационный способ получения функции похожести между объектами со ссылками

Формула изобретения

1. Итерационный способ получения функции похожести между объектами со ссылками, хранящимися в базе данных ЭВМ, по которому каждому объекту базы данных присваивают индивидуальный идентификатор, для пары сравниваемых объектов, имеющих идентификаторы а и b, задают начальное приближенное значение для функции похожести R₀(a, b), равное единице, если идентификаторы объектов а и b совпадают, и нулю в противном случае задают коэффициент затухания С, имеющий любое постоянное положительное значение больше 0 и меньше 1, задают количество итераций К, проводимых для вычисления значений похожести, имеющее положительное целочисленное значение больше единицы, вычисляют значение константы по формуле =C^K+1-C^K+2, в памяти вычислительной машины выделяют массив частичных сумм Р, количество ячеек хранения в котором равно количеству объектов в базе и каждая ячейка которого предназначена для хранения вещественного числа либо специального значения «значение ячейки не определено», при этом каждому объекту из базы сопоставляют индивидуальную ячейку в выделенном массиве, причем первоначально все ячейки в массиве имеют значение «не определено», выделяют память под множество один Т и множество два Е, причем оба множества на момент создания пусты, выделяют ячейку памяти k под целочисленный тип данных, для хранения номера текущей итерации, производят К+1 итерацию, при этом числовое значение в ячейке k последовательно меняют от 1 до К+1, причем на каждой итерации вычисляют значение константы кроме того, последовательно сканируют каждый объект в базе, и для каждого идентификатора а сканируемого объекта, если текущая итерация не является последней (т.е. k K+1), то в базе проверяют наличие ссылок из объекта, соответствующего идентификатору а, на другие объекты, при этом, если у объекта отсутствуют такие ссылки, то последующие шаги алгоритма для данного объекта на данной итерации пропускают, в противном случае заполняют элементы множества Т для объекта а таким образом, что множество Т состоит из всех таких объектов, которые имеют ненулевую похожесть в соответствии с предыдущей итерацией с каким-либо объектом, имеющем ссылку на а, при этом для заполнения элементов множества Т производят сканирование всех объектов, имеющих в базе ссылку на объект а, и для каждого такого объекта обозначаемого и производят запрос к функции похожести от предыдущей итерации для получения набора всех объектов, имеющих с u ненулевую похожесть, обозначают их v, и для каждого такого объекта v производят добавление этого объекта к множеству Т, кроме того, на основании элементов множества Т заполняют элементы множества Е, для этого производят сканирование всех элементов множества Т и для каждого объекта v этого множества производят запрос к базе на получение всех объектов b таких, на которые имеется ссылка с объекта v, при этом все объекты b добавляют к множеству Е, при этом для каждого объекта b из множества Е в памяти вычислительной машины выделяют ячейку вещественного типа, на которую в дальнейшем ссылаются по имени r, вещественное число, содержащееся в данной ячейке, обозначает значение близости между объектами а и b, и первоначально в ячейку записывают нулевое значение, при этом производят последовательный обход по базе всех объектов v, которые имеют ссылку на объект b, и для каждого такого объекта v проверяют, определено ли значение ячейки в массиве частичных сумм Р, соответствующей объекту v, если это значение не определено, то производят обход всех объектов u, которые в базе имеют ссылку на объект а, значения похожести по предыдущей итерации между объектами u и v суммируют, и в ячейку массива частичных сумм записывают полученную сумму при этом значение ячейки r увеличивают на значение этой ячейки из массива частичных сумм, после этого значение, содержащееся в ячейке r, умножают на величину , где обозначает количество объектов в базе, имеющих ссылку на объект a, обозначает аналогичное для объекта b, при этом если значение, содержащееся в ячейке r, превосходит величину порога _k, то к функции похожести R_k добавляют тройку (а, b, r), отражающую информацию о том, что значение похожести между объектами а и b на текущей итерации равно величине, содержавшейся в ячейке r, при этом множества Т и Е очищают, удаляя все содержащиеся в них идентификаторы объектов, а все ячейки в массиве частичных сумм Р перезаписывают неопределенными значениями, при этом для каждой пары объектов а и b, значение функции похожести R _K+1(a, b), полученное на последней итерации, принимают как результирующее значение похожести объектов а и b, а функцию похожести, полученную на последней итерации, сохраняют в постоянной памяти вычислительной машины для последующего использования в приложениях, которым нужна мера похожести объектов из базы данных ЭВМ.

2. Способ по п.1, отличающийся тем, что С выбирают равным 0,6.

3. Способ по п.1, отличающийся тем, что К выбирают равным 5.

Описание изобретения к патенту

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

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

1. Гипертекстовая энциклопедия (далее для краткости просто «энциклопедия» или «база данных») - совокупность информации, состоящая из объектов и ссылок между объектами. Каждый объект представляет собой некоторую энциклопедическую концепцию (которая может быть интересна читателю), например, «Город Москва» или «Теорема Пифагора». Каждый объект может иметь ссылки на другие объекты, где ссылка обозначает отношение взаимосвязи между двумя объектами: (i) тем объектом, который ссылается, и (ii) тем объектом, на который ссылаются при помощи ссылки. Помимо ссылок, каждый объект, содержащийся в энциклопедии, может иметь произвольные дополнительные данные, относящиеся к данному объекту, например: текстовое имя концепции, тип сущности («имя собственное», «существительное» и т.п.), текстовое описание сущности. Какой-либо конкретный формат или содержимое подобных дополнительных данных у объектов в настоящей модели не фиксируется и может быть произвольным.

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

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

В практической деятельности часто актуальной является задача определения степени семантической похожести между парой объектов в энциклопедии. Данная задача складывается из двух аспектов:

1) имея пару объектов из энциклопедии, определить степень похожести между ними.

2) имея один объект из энциклопедии, определить максимально похожие на него объекты в порядке убывания похожести.

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

Для формализации семантической похожести между объектами энциклопедии вводится функция похожести, которая в общем случае определяется как функция от пары объектов как аргументов - похожесть (а, b ) - и значения которой для любой пары объектов принадлежат отрезку от 0 до 1. При этом значение похожести, равное 1, означает максимальную похожесть между парой объектов; обычно максимальная похожесть достигается для пары тождественных объектов. В противоположность, значение похожести, равное нулю, означает непохожесть пары объектов. Функция похожести хранится в памяти вычислительной машины как совокупность троек (a, b, s); первые две компоненты в каждой тройке являются идентификаторами объектов, похожесть которых специфицирует данная тройка, а третья компонента содержит значение похожести.

Известна мера похожести "SimRank", которая определяет значения похожести между объектами в энциклопедии, описанная в «Glen Jeh, and Jennifer Widom. SimRank: A measure of structural-context similarity. In Proceedings of the 8-th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 538-543, 2002» [1]. B модели данных меры SimRank используют только два типа сущностей из энциклопедии: объекты и ссылки между объектами. Основная предпосылка модели формулируется так: «два объекта похожи, если на них ссылаются похожие объекты». Поскольку данная предпосылка формулирует понятие похожести через саму себя, то базовой предпосылкой в модели SimRank служит утверждение: «каждый объект считается максимально похожим на себя самого», т.е. имеющим с самим собой значение похожести, равное единице.

Обозначая под I(a) множество всех тех объектов в энциклопедии, которые имеют ссылки на объект а, мера похожести SimRank получает следующую формулировку. В качестве базового случая, каждый объект имеет максимальную похожесть с самим собой, т.е. s( a, b)=1. В общем случае, похожесть пары объектов а и b выражается через похожесть объектов, которые на них ссылаются, т.е.

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

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

Известна сходимость вышеописанного итеративного процесса, причем значения похожести, достигаемые через К=5 итераций, считаются достаточно точными для того, чтобы считать их теоретическими значениями похожести. Однако для вышеописанного способа вычисления количество требуемых операций в общем случае равно O(n⁴), где число n равно количеству объектов в энциклопедии. Ввиду такого большого количества требуемых операций, для энциклопедий (баз данных) с большим количеством объектов (единиц хранения) использование известного способа вычисления значений похожести оказывается практически неприменимым. Например, для энциклопедии, содержащей 1 миллион объектов, вычисление значений похожести потребует порядка 10²⁴ вычислительных операций. Даже при способности современных вычислительных машин к выполнению десятков миллиардов операций в секунду, выполнение такого объема вычислений потребует многих лет работы вычислительной машины, что является практически неприемлемым. Другим ограничивающим фактором при вычислении значений похожести является объем машинной памяти, требуемой для хранения итеративных и результирующих значений похожести. Непосредственное хранение значения похожести для каждой пары объектов из энциклопедии требует в целом порядка n² единиц памяти. Так, для энциклопедии с 1 миллионом объектов размер требуемой памяти для известного способа хранения значений похожести составляет несколько Терабайтов, что не может быть предоставлено аппаратурой большинства современных стандартных вычислительных машин. Приведенные оценки для количества требуемых операций и памяти показывают, что известный способ является неприменимым для типичных электронных энциклопедий, и это является основным недостатком известного способа.

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

Сущность изобретения состоит в том, что предложен итерационный способ получения функции похожести между объектами со ссылками, хранящимися в базе данных ЭВМ, по которому каждому объекту базы данных присваивают индивидуальный идентификатор, для пары сравниваемых объектов, имеющих идентификаторы а и b, задают начальное приближенное значение для функции похожести R₀ (a, b), равное единице, если идентификаторы объектов а и b совпадают, и нулю в противном случае, задают коэффициент затухания С, имеющий любое постоянное положительное значение больше 0 и меньше 1, задают количество итерации К, проводимых для вычисления значений похожести, имеющее положительное целочисленное значение больше единицы, вычисляют значение константы по формуле =C^K+1-C^K+2, в памяти вычислительной машины выделяют массив частичных сумм Р, количество ячеек хранения в котором равно количеству объектов в базе и каждая ячейка которого предназначена для хранения вещественного числа либо специального значения «значение ячейки не определено», при этом каждому объекту из базы сопоставляют индивидуальную ячейку в выделенном массиве, причем первоначально все ячейки в массиве имеют значение «не определено», выделяют память под множество один Т и множество два Е, причем оба множества на момент создания пусты, выделяют ячейку памяти k под целочисленный тип данных, для хранения номера текущей итерации, производят К+1 итерацию, при этом числовое значение в ячейке k последовательно меняют от 1 до К+1, причем на каждой итерации вычисляют значение константы , кроме того, последовательно сканируют каждый объект в базе, и для каждого идентификатора а сканируемого объекта, если текущая итерация не является последней (т.е. k К+1), то в базе проверяют наличие ссылок из объекта, соответствующего идентификатору а, на другие объекты, при этом, если у объекта отсутствуют такие ссылки, то последующие шаги алгоритма для данного объекта на данной итерации пропускают, в противном случае заполняют элементы множества Т для объекта а таким образом, что множество Т состоит из всех таких объектов, которые имеют ненулевую похожесть в соответствии с предыдущей итерацией с каким-либо объектом, имеющим ссылку на а, при этом для заполнения элементов множества Т производят сканирование всех объектов, имеющих в базе ссылку на объект а, и для каждого такого объекта, обозначаемого и, производят запрос к функции похожести от предыдущей итерации для получения набора всех объектов, имеющих с и ненулевую похожесть, обозначают их v , и для каждого такого объекта v производят добавление этого объекта к множеству Т, кроме того, на основании элементов множества Т заполняют элементы множества Е, для этого производят сканирование всех элементов множества Т, и для каждого объекта v этого множества производят запрос к базе на получение всех объектов b, таких, на которые имеется ссылка с объекта v, при этом все объекты b добавляют к множеству Е, при этом для каждого объекта b из множества Е в памяти вычислительной машины выделяют ячейку вещественного типа, на которую в дальнейшем ссылаются по имени r, вещественное число, содержащееся в данной ячейке, обозначает значение близости между объектами а и b, и первоначально в ячейку записывают нулевое значение, при этом производят последовательный обход по базе всех объектов v, которые имеют ссылку на объект b, и для каждого такого объекта v проверяют, определено ли значение ячейки в массиве частичных сумм Р, соответствующей объекту v, если это значение не определено, то производят обход всех объектов и, которые в базе имеют ссылку на объект а, значения похожести по предыдущей итерации между объектами и и v суммируют, и в ячейку массива частичных сумм записывают полученную сумму , при этом значение ячейки r увеличивают на значение ячейки из массива частичных сумм, после этого значение, содержащееся в ячейке r, умножают на величину ,

где обозначает количество объектов в базе, имеющих ссылку на объект а,

обозначает аналогичное для объекта b, при этом если значение, содержащееся в ячейке r, превосходит величину порога _k, то к функции похожести R_k добавляют тройку (а, b, r), отражающую информация о том, что значение похожести между объектами а и b на текущей итерации равно величине, содержавшейся в ячейке r, при этом множества Т и Е очищают, удаляя все содержащиеся в них идентификаторы объектов, а все ячейки в массиве частичных сумм Р перезаписывают неопределенными значениями, при этом для каждой пары объектов а и b значение функции похожести R_K+1 (а, b), полученное на последней итерации, принимают как результирующее значение похожести объектов а и b, а функцию похожести, полученную на последней итерации, сохраняют в постоянной памяти вычислительной машины для последующего использования в приложениях, которым нужна мера похожести объектов из базы данных ЭВМ.

Кроме того, при вычислениях значение коэффициента затухания могут выбирать равным 0.6, а К могут выбирать равным 5.

Технический результат использования предлагаемого изобретения состоит в том, что изобретение позволяет получать значения похожести между объектами электронной энциклопедии за значительно меньшее количество вычислительных операций и с более экономным использованием памяти, чем известный ранее способ, что делает практически выполнимым вычисление значений похожести между всеми объектами электронной энциклопедии типичного размера ресурсами стандартной ЭВМ. Так, при количестве объектов в энциклопедии, равном n, и при общем количестве ссылок в энциклопедии, равном l, предлагаемое изобретение обеспечивает вычисление значений похожести для всех пар объектов энциклопедии за количество операций O(nl). Даже в самом неблагоприятном с вычислительных позиций случае, когда каждый объект в энциклопедии имеет ссылку на каждый другой объект (что крайне маловероятно для практической энциклопедии), предлагаемое изобретение обеспечивает вычисление значений похожести за количество операций, не большее O(n³), что является значительным улучшением по сравнению с известным ранее способом. Поскольку в типичной энциклопедии присутствует гораздо меньшее количество ссылок, изобретение обеспечивает на практике еще более значительный вычислительный выигрыш при вычислении значений похожести. Помимо улучшения по количеству операций, изобретение также обеспечивает уменьшение объема машинной памяти, используемой для хранения значений похожести, что делает вычисление значений похожести для электронных энциклопедий менее требовательным к ресурсам вычислительных машин.

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

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

- Уменьшение количества операций при суммировании.

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

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

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

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

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

Изобретение работает следующим образом.

1. Вычисляется значение константы вещественного типа, определяемое как =C^K+1-C^K+2, где верхний индекс обозначает операцию возведения в степень. Данная константа задает максимальную погрешность, которая может возникать ввиду отбрасывания малых значений похожести по ходу последующих шагов алгоритма. Заметим, что поскольку С<1, то имеет положительное значение.

2. Задается начальное (нулевое) приближение для функции похожести: R ₀(a, b), равное единице, если идентификаторы объектов а и b совпадают (т.е. идентифицируют один и тот же объект в базе), и нулю в противном случае. Заметим, что в соответствии со способом хранения, принятым для функции похожести, нулевое приближение для функции похожести не требует памяти вычислительной машины для хранения. (Все тройки, в совокупности образующие функцию похожести, имеют попарно различные первые две компоненты (т.е. значение похожести для любой пары объектов хранится не более одного раза). С целью экономии памяти вычислительных машин в функции похожести не хранятся следующие виды троек: (а) для пар объектов, имеющих нулевую похожесть; (б) для объекта с самим собой, поскольку в последнем случае значение похожести заранее известно и равно единице по определению похожести.)

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

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

5. Заводится ячейка памяти под целочисленный тип данных, к которой мы в дальнейшем обращаемся по имени k и которая в каждый момент времени содержит номер текущей итерации. Производится К+1 итерация, т.е. числовое значение в ячейке k последовательно меняется от 1 до К+1. На каждой итерации выполняются следующие действия.

a) вычисляется значение константы _k вещественного типа, определяемое как Данная константа фиксирует величину порога для значений похожести на текущей итерации;

b) последовательно сканируется каждый объект в базе, и для каждого идентификатора а текущего объекта выполняются следующие действия:

i) Если текущая итерация не является последней (т.е. k K+1), то в базе проверяется наличие ссылок из объекта, соответствующего идентификатору а, на другие объекты. Если у объекта отсутствуют такие ссылки, то последующие шаги алгоритма для данного объекта на данной итерации пропускаются. (В работе «Dmitry Lizorkin, Pavel Velikhov, Maxim Grinev and Denis Turdakov. Accuracy estimate and optimization techniques for SimRank computation. Proceedings of the 34-th international conference on Very Large Data Bases (VLDB-2008), 1(1):422-433, 2008» [2], Утверждение 4 и Следствие 1, доказывается, что в описанном случае вычислять попарную похожесть объекта а с другими объектами не требуется.)

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

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

(2) Для каждого такого объекта v производится добавление этого объекта к множеству Т.

iii) На основании элементов множества Т заполняются элементы множества Е. Для этого производится сканирование всех элементов множества Т, и для каждого объекта v этого множества:

(1) Производится запрос к базе на получение всех объектов b, таких, на которые имеется ссылка с узла v.

(2) Все объекта b добавляются к множеству Е.

iv) Для каждого объекта b из множества Е выполняются следующие действия

(Для прочих узлов в базе вычисление их похожести с узлом а на данной итерации не требуется, что доказывается в работе [2], Утверждение 3.)

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

(2) Производится последовательный обход по базе всех объектов v, которые имеют ссылку на объект b, и для каждого такого объекта v производятся следующие действия:

(a) Проверяется, определено ли значение ячейки в массиве частичных сумм Р, соответствующей объекту v. Если это значение не определено, то производится обход всех объектов и, которые в базе имеют ссылку на объект а, значения похожести по предыдущей итерации между объектами и и v суммируются, и в ячейку массива частичных сумм записывается полученная сумма:

(b) Значение ячейки r увеличивается на значение этой ячейки из массива частичных сумм: r+=P(v).

(3) Значение, содержащееся в ячейке r, умножается на величину: .

Здесь нотация обозначает количество объектов в базе, имеющих ссылку на объект а; нотация обозначает аналогичное для объекта b.

(4) Если значение, содержащееся в ячейке r, превосходит величину порога _k, то к функции похожести R_k добавляется тройка (а, b, r), т.е. информация о том, что значение похожести между объектами а и b на текущей итерации равно величине, содержавшейся в ячейке r .

v) Множества Т и Е очищаются (т.е. из них удаляются все содержащиеся в них идентификаторы объектов). Все ячейки в массиве частичных сумм Р перезаписываются неопределенными значениями. Для каждой пары объектов а и b значение функции похожести R_K+1 (а, b), полученное на последней итерации, принимается как результирующее значение похожести соответствующих объектов. Функция похожести, полученная на последней итерации, сохраняется в постоянной памяти вычислительной машины для последующего использования в приложениях, которым нужна мера похожести объектов из базы. (В работе [2], Утверждение 7 доказывается, что посчитанные в соответствии с приведенным выше алгоритмом значения похожести отличаются от теоретической похожести SimRank не более чем на величину C^K+1, что совпадает с точностью неоптимизированного итеративного вычисления.)

При этом следует иметь в виду следующее:

1. Коэффициент затухания С в модели SimRank варьируется в пределах 0<С<1 и определяет, насколько сильно влияет на значение похожести объекта а и b объект, который ссылается на а и b посредством цепочки ссылок. А именно, если из объекта d ведет цепочка ссылок длины m к объекту а и цепочка ссылок такой же длины к объекту b, то вклад объекта d в похожесть объектов а и b в модели SimRank пропорционален величине С^m. Таким образом, при выборе маленького значения С вклад похожести по цепочкам ссылок затухает быстрее. Значение С может быть выбрано любым в пределах 0<С<1 в зависимости от конкретной прикладной области; в большинстве случаев может быть рекомендовано значение С=0.6.

2. Традиционно для SimRank для итераций, проводимых для вычисления значений похожести, используется значение К=5; в работе [2] было доказано, что это значение в большинстве случаев обеспечивает достаточную точность результата.

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

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

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

1) Определяем величину , через значение которой определяются величины порогов на каждой из итераций: =C^K+1-C^K+2=0.6²⁺¹+0.6 ²⁺²=0.0864.

2) Задаем начальное приближение для значений похожести R₀(а, b), равное 1 для одного и того же объекта и 0 для разных объектов. В терминах хранения значений похожести в вычислительной машине нулевые значения похожести и значения похожести для объекта с самим собой (всегда равное 1) физически не хранятся. Данное соглашение позволяет экономить ресурсы памяти вычислительных машин и позволяет однозначно узнать значение похожести для любой пары объектов: если для этой пары объектов значение похожести не хранится, то это означает, что это значение похожести равно 0 в случае различных объектов и равно 1 в случае одного и того же объекта. При сделанных соглашениях начальное приближение для значений похожести R₀(а, b) не требует никаких ресурсов памяти для хранения значений похожести.

3) Выделяем в памяти вычислительной машины массив частичных сумм Р, количество ячеек хранения в котором равно количеству объектов в примере (8 объектов) и каждая ячейка которого предназначена для хранения вещественного числа либо специального значения «значение ячейки не определено». Каждому объекту сопоставляется индивидуальная ячейка в выделенном массиве.

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

5) Производим первую итерацию: k=1:

а) Определяем значение порога для первой итерации:

b) Последовательно рассматриваем каждый объект (чтобы вычислить для него его похожесть со всеми остальными объектами на данной итерации).

c) Рассматриваем объект а=«Дорога»:

i) Анализируем ячейку хранения для данного объекта в базе со ссылками и определяем, имеет ли данный объект ссылки на какие-либо другие объекты в базе. Поскольку объект а не ссылается ни на какой другой объект и поскольку текущая итерация не является последней, то для данного объекта никаких действий на данной итерации не требуется.

d) Полностью аналогичным образом обрабатываются объекты «Автомобиль», «Самолет» и «Вертолет», поскольку ни один из этих объектов также не имеет ссылок на другие объекты в базе со ссылками.

e) Рассматриваем объект а=«Транспорт»:

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

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

iii) Поскольку множество Е состоит из всех объектов, на которые ссылается хотя бы один объект из множества Т, и множество Т - пустое, то пустым является и множество Е.

iv) Так как множество Е пусто, то нет ни одного объекта, который имеет ненулевую похожесть с данным объектом а=«Транспорт», поэтому действия над этим объектом в данной итерации завершаются.

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

g) Рассматриваем объект а=«Наземный транспорт»:

i) Данный объект имеет ссылки на другие объекты в базе со ссылками, поэтому для данного объекта выполняются последующие действия.

ii) Множество Т (состоящее из всех объектов, которые имеют ненулевую похожесть по предыдущей итерации с каким-либо объектом, имеющим ссылку на данный объект а) состоит из единственного элемента - объекта «Транспорт».

iii) Множество существенных объектов Е для данного объекта а=«Наземный транспорт» включает в себя сам этот объект и объект «Воздушный транспорт».

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

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

v) Для каждого объекта b из множества Е, т.е. в данном случае для объекта b=«Воздушный транспорт», выполняются следующие действия:

(1) В памяти вычислительной машины заводится ячейка r вещественного типа, значение которой будет обозначать значение похожести объектов а и b; на момент создания в ячейку r записывается нулевое значение.

(2) Для объекта b в базе со ссылками сканируются все объекты, которые имеют ссылку на b. Для каждого такого объекта, в данном случае для единственного объекта «Транспорт», на который мы далее будем ссылаться по имени v, выполняются следующие действия:

(a) Проверяется, определено ли значение ячейки для объекта v в массиве частичных сумм Р. Так как значение этой ячейки не определено, то оно вычисляется суммированием значений похожести с предыдущей итерации объекта v с каждым из объектов в базе со ссылками, имеющими ссылку на объект а. В виде математической формулы значение ячейки массива Р для объекта v определяется как .

В данном случае суммирование производится по единственному объекту «Транспорт», и в качестве слагаемого берется значение похожести этого объекта с самим собой, что дает единицу.

(b) Значение ячейки r теперь увеличивается на содержимое ячейки массива частичных сумм P(v), т.е. теперь становится равным единице.

(3) Значение, содержащееся в ячейке r, теперь умножается на величину , где в знаменателе стоит количество объектов, имеющих в базе со ссылками ссылки на объекты а и b соответственно. Поскольку на оба объекта ссылается по одному объекту, то значение множителя равно С и значение, содержащееся в ячейке r, становится равным: r=С=0.6.

(4) Полученное значение похожести превосходит величину порога ₁=0.08, поэтому полученное значение не отбрасывается, но к функции похожести R₁ добавляется тройка (а , b, r), т.е. информация о том, что значение похожести между объектами а=«Наземный транспорт» и b=«Воздушный транспорт» на текущей итерации равно 0.6, сохраняется в памяти вычислительной машины.

vi) Множества Т и Е очищаются (т.е. из них удаляются все содержащиеся в них идентификаторы объектов). Все ячейки в массиве частичных сумм Р прописываются значением «неопределенное значение».

h) Объект а=«Воздушный транспорт» обрабатывается полностью симметрично предыдущему.

i) Таким образом, все объекты для данной итерации были просмотрены. Отметим, что тогда как полное рассмотрение всевозможных пар включает 8×8 комбинаций, рассмотренный метод позволил сократить необходимое количество пар всего до двух.

6) Вторая итерация (k=2) происходит аналогично первой за исключением величины порога ₂, и значения похожести на этой итерации остаются неизменными по сравнению с прошлой итерацией.

7) Производим последнюю итерацию: k=К+1=3.

a) Значение порога для данной итерации равно:

b) Последовательно рассматриваем каждый объект.

c) Рассматриваем объект а=«Автомобиль».

i) Поскольку текущая итерация является последней, для данного объекта а последующие действия выполняются вне зависимости от того, есть ли у этого объекта ссылки на другие объекты.

ii) На данный объект имеются ссылки у объектов «Автомобильная инфраструктуры» и «Наземный транспорт». В соответствии с предыдущей итерацией, каждый из этих объектов имеет ненулевую похожесть с самим собой, а также объект «Наземный транспорт» имеет ненулевую похожесть с объектом «Воздушный транспорт». Таким образом, множество Т состоит из трех элементов: «Автомобильная инфраструктура», «Наземный транспорт» и «Воздушный транспорт».

iii) Соответственно, множество Е состоит из всех объектов, на которые имеются ссылки от одного из элементов множества Т, что дает объекты «Дорога», «Автомобиль», «Самолет» и «Вертолет».

iv) Последовательно обрабатываем каждый объект из множества Е:

v) Для объекта b=«Самолет» из этого множества выполняются следующие действия:

(1) Снова заводится ячейка r вещественного типа, имеющая нулевое значение на момент создания, значение которой будет обозначать значение похожести объектов а и b.

(2) Для объекта b в базе со ссылками берутся все объекты, которые имеют ссылку на b. Множество таких объектов состоит из единственного объекта - «Воздушный транспорт». Для каждого объекта v из этого множества, т.е. для v =«Воздушный транспорт», выполняются следующие действия:

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

.

В данном случае суммирование производится по двум объектам и - «Автомобильная инфраструктура» и «Наземный транспорт», и в качестве слагаемых в соответствии с предыдущей итерацией стоят соответственно величины 0 и 0.6, что в сумме дает 0.6.

(b) Значение ячейки r увеличивается на содержимое ячейки массива частичных сумм Р(v), т.е. становится равным 0.6.

(3) Значение ячейки r наконец умножается на величину , которая равна: . Таким образом, значение ячейки r становится равным .

(4) Полученное значение ячейки r превосходит величину порога ₃, поэтому полученное значение сохраняется в памяти вычислительной машины как значение похожести на третьей итерации в виде тройки (а, b, r), т.е. обозначает похожесть между объектами «Автомобиль» и «Самолет», равную 0.18.

vi) Аналогичным образом вычисляется похожесть данного узла а с узлом b=«Вертолет». Существенным наблюдением здесь является то, что значение соответствующей ячейки Р(v) в массиве частичных сумм уже определено, поэтому его повторное вычисление не требуется.

vii) Похожесть данного узла а с узлом b=«Дорога» вычисляется технически аналогично, и значение похожести равно 0.3.

viii) Множества Т и Е очищаются (т.е. из них удаляются все содержащиеся в них идентификаторы объектов). Все ячейки в массиве частичных сумм Р прописываются значением «неопределенное значение».

d) Для объектов «Дорога», «Самолет» и «Вертолет» все вычисления производятся по аналогии.

8) Полученные на последней итерации значения похожести становятся результирующими значениям похожести. Отметим, что в данном примере полученные значения похожести являются точными значениями, т.е. проведение последующих итераций не дает изменения значений похожести.

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

- похожесть(«Наземный транспорт», «Воздушный транспорт»)=0.6,

т.к. оба объекта являются конкретизациями объекта «Транспорт».

- похожесть(«Автомобиль», «Дорога») = 0.3,

т.к. оба объекта принадлежат категории «Автомобильная инфраструктура»

похожесть («Автомобиль», «Самолет»)=похожесть(«Автомобиль», «Вертолет») = 0.18,

через общую категорию «Транспорт», которая является не непосредственной, но косвенной, для обоих объектов в паре

- похожесть(«Самолет», «Вертолет») = 0.6.

т.к. оба объекта принадлежат категории «Воздушный транспорт».

Из полученных значений похожести следует, в частности, что в соответствии с рассмотренным примером объект «Автомобиль» более всего похож на объект «Дорога» (т.к. оба относятся к автомобильной инфраструктуре) и в меньшей степени похож на объекты «Самолет» и «Вертолет» (т.к. все являются транспортными средствами). Объект «Дорога», с другой стороны, не похож на объект «Вертолет».

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