СимРанк

SimRank — это общая мера сходства , основанная на простой и интуитивно понятной модели теории графов . SimRank применим в любом домене с отношениями «объект-к-объекту» , который измеряет сходство структурного контекста, в котором встречаются объекты, на основе их отношений с другими объектами. По сути, SimRank — это показатель, который говорит, что « два объекта считаются похожими, если на них ссылаются похожие объекты ». Хотя SimRank широко распространен, он может выдавать необоснованные оценки сходства, на которые влияют различные факторы, и это можно решить несколькими способами, например, введением весового коэффициента доказательств, ^[1] вставкой дополнительных терминов, которые игнорируются SimRank ^[2] или используя альтернативы на основе PageRank. ^[3]

Введение

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

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

Интуиция алгоритма SimRank заключается в том, что во многих доменах на похожие объекты ссылаются похожие объекты . Точнее, объекты и считаются подобными, если они указываются из объектов и соответственно, и и сами подобны. Базовый случай — объекты максимально похожи сами на себя. ^[4] ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle d}$

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

Основное уравнение SimRank

Для узла ориентированного графа мы обозначаем и множество внутренних и внешних соседей соответственно. Отдельные внутренние соседи обозначаются как , для , а отдельные внешние соседи обозначаются как , for . ${\displaystyle v}$ ${\displaystyle I(v)}$ ${\displaystyle O(v)}$ ${\displaystyle v}$ ${\displaystyle I_{i}(v)}$ ${\displaystyle 1\leq i\leq \left|I(v)\right|}$ ${\displaystyle O_{i}(v)}$ ${\displaystyle 1\leq i\leq \left|O(v)\right|}$

Обозначим сходство между объектами и через . Следуя предыдущей мотивации, для . Если то определяется как . В противном случае, ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle s(a,b)\in [0,1]}$ ${\displaystyle s(a,b)}$ ${\displaystyle a=b}$ ${\displaystyle s(a,b)}$ ${\displaystyle 1}$

${\displaystyle s(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s(I_{i}(a),I_{j}(b))}$

где константа между и . Небольшая формальность здесь заключается в том, что соседи могут иметь или не иметь своих соседей. Поскольку невозможно определить какое-либо сходство между и в этом случае, сходство устанавливается равным , поэтому суммирование в приведенном выше уравнении определяется как когда или . ${\displaystyle C}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle s(a,b)=0}$ ${\displaystyle 0}$ ${\displaystyle I(a)=\emptyset }$ ${\displaystyle I(b)=\emptyset }$

Матричное представление SimRank

Учитывая произвольную константу между и , пусть будет матрицей подобия, запись которой обозначает оценку сходства , и будет нормализованной по столбцу матрицей смежности , чья запись , если есть ребро от до , и 0 в противном случае. Тогда в матричных обозначениях SimRank можно сформулировать как ${\displaystyle C}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \mathbf {S} }$ ${\displaystyle [\mathbf {S} ]_{a,b}}$ ${\displaystyle s(a,b)}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle [\mathbf {A} ]_{a,b}={\tfrac {1}{|{\mathcal {I}}(b)|}}}$ ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle {\mathbf {S} }=\max\{C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} }),{\mathbf {I} }\},}$

где – единичная матрица. ${\displaystyle \mathbf {I} }$

Вычисление SimRank

Решение уравнений SimRank для графа может быть достигнуто путем итерации до фиксированной точки . Пусть будет число узлов в . Для каждой итерации мы можем сохранять записи , где указывается оценка между итерациями и на ней . Мы последовательно вычисляем на основе . Начнем с того, где каждый из них является нижней границей фактического балла SimRank : ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle n^{2}}$ ${\displaystyle s_{k}(*,*)}$ ${\displaystyle s_{k}(a,b)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle k}$ ${\displaystyle s_{k+1}(*,*)}$ ${\displaystyle s_{k}(*,*)}$ ${\displaystyle s_{0}(*,*)}$ ${\displaystyle s_{0}(a,b)}$ ${\displaystyle s(a,b)}$

${\displaystyle s_{0}(a,b)={\begin{cases}1{\mbox{ }},{\mbox{ }}{\mbox{if }}a=b{\mbox{ }},\\0{\mbox{ }},{\mbox{ }}{\mbox{if }}a\neq b{\mbox{ }}.\end{cases}}}$

Для вычисления from мы используем базовое уравнение SimRank, чтобы получить: ${\displaystyle s_{k+1}(a,b)}$ ${\displaystyle s_{k}(*,*)}$

${\displaystyle s_{k+1}(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s_{k}(I_{i}(a),I_{j}(b))}$

для и для . То есть на каждой итерации мы обновляем сходство, используя оценки сходства соседей из предыдущей итерации в соответствии с основным уравнением SimRank. Значения не уменьшаются по мере увеличения. В ^[4] было показано , что значения сходятся к пределам , удовлетворяющим основному уравнению SimRank, баллам SimRank , т.е. для всех , . ${\displaystyle a\neq b}$ ${\displaystyle s_{k+1}(a,b)=1}$ ${\displaystyle a=b}$ ${\displaystyle k+1}$ ${\displaystyle (a,b)}$ ${\displaystyle (a,b)}$ ${\displaystyle k}$ ${\displaystyle s_{k}(*,*)}$ ${\displaystyle k}$ ${\displaystyle s(*,*)}$ ${\displaystyle a,b\in V}$ ${\displaystyle \lim _{k\to \infty }s_{k}(a,b)=s(a,b)}$

Первоначальное предложение SimRank предлагало выбрать коэффициент затухания и фиксированное количество выполняемых итераций. Однако недавнее исследование ^[5] показало, что приведенные значения и в целом подразумевают относительно низкую точность итеративно вычисленных оценок SimRank. Для обеспечения более точных результатов вычислений в последней статье предлагается либо использовать меньший коэффициент затухания (в частности, ), либо брать больше итераций. ${\displaystyle C=0.8}$ ${\displaystyle K=5}$ ${\displaystyle C}$ ${\displaystyle K}$ ${\displaystyle C=0.6}$

CoSimRank

CoSimRank — это вариант SimRank, преимущество которого состоит в том, что он также имеет локальную формулировку, т. е. CoSimRank может быть вычислен для одной пары узлов. ^[6] Пусть – матрица сходства, запись которой обозначает оценку сходства , и – нормализованная по столбцам матрица смежности. Тогда в матричных обозначениях CoSimRank можно сформулировать как: ${\displaystyle \mathbf {S} }$ ${\displaystyle [\mathbf {S} ]_{a,b}}$ ${\displaystyle s(a,b)}$ ${\displaystyle \mathbf {A} }$

${\displaystyle {\mathbf {S} }=C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} })+{\mathbf {I} },}$

где – единичная матрица. Чтобы вычислить показатель сходства только для одной пары узлов, пусть , будучи вектором стандартного базиса, т. е. -я запись равна 1, а все остальные записи равны 0. Затем CoSimRank можно вычислить в два этапа: ${\displaystyle \mathbf {I} }$ ${\displaystyle p^{(0)}(i)=e_{i}}$ ${\displaystyle e_{i}}$ ${\displaystyle i}$

1. ${\displaystyle p^{(k)}=Ap^{(k-1)}}$
2. ${\displaystyle s(i,j)=\sum _{k=0}^{\infty }C^{k}\langle p^{(k)}(i),p^{(k)}(j)\rangle }$

На первом этапе можно увидеть упрощенную версию персонализированного PageRank . Второй шаг суммирует векторное сходство каждой итерации. И матричное, и локальное представление вычисляют один и тот же показатель сходства. CoSimRank также можно использовать для вычисления сходства наборов узлов путем изменения . ${\displaystyle p^{(0)}(i)}$

Дальнейшие исследования SimRank

• Фогарас и Рац ^[7] предложили ускорить вычисление SimRank за счет вероятностных вычислений с использованием метода Монте-Карло .
• Антонеллис и др. ^[8] расширили уравнения SimRank, чтобы принять во внимание (i) фактор доказательства для инцидентных узлов и (ii) веса каналов.
• Ю и др. ^[9] дополнительно улучшили вычисление SimRank с помощью метода детальной мемоизации , позволяющего разделить небольшие общие части между различными частичными суммами.
• Чен и Джайлз обсудили ограничения и варианты правильного использования SimRank. ^[3]

Мемоизация частичных сумм

Лизоркин и др. ^[5] предложили три метода оптимизации для ускорения расчета SimRank:

1. Выбор существенных узлов может исключить вычисление части пар узлов с априорно нулевыми баллами.
2. Запоминание частичных сумм может эффективно сократить повторные вычисления сходства между различными парами узлов за счет кэширования части суммирования сходства для последующего повторного использования.
3. Установка порога сходства позволяет дополнительно сократить количество вычисляемых пар узлов.

В частности, второе наблюдение запоминания частичных сумм играет первостепенную роль в значительном ускорении вычисления SimRank от до , где – количество итераций, – средняя степень графа, – количество узлов в графе. Основная идея мемоизации частичных сумм состоит из двух этапов: ${\displaystyle {\mathcal {O}}(Kd^{2}n^{2})}$ ${\displaystyle {\mathcal {O}}(Kdn^{2})}$ ${\displaystyle K}$ ${\displaystyle d}$ ${\displaystyle n}$

Во-первых, частичные суммы запоминаются как ${\displaystyle I(a)}$

${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)=\sum _{i\in I(a)}s_{k}(i,j),\qquad (\forall j\in I(b))}$

а затем итеративно вычисляется по формуле ${\displaystyle s_{k+1}(a,b)}$ ${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)}$

${\displaystyle s_{k+1}(a,b)={\frac {C}{|I(a)||I(b)|}}\sum _{j\in I(b)}{\text{Partial}}_{I(a)}^{s_{k}}(j).}$

Следовательно, результаты , , можно повторно использовать позже, когда мы вычисляем сходство для данной вершины в качестве первого аргумента. ${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)}$ ${\displaystyle \forall j\in I(b)}$ ${\displaystyle s_{k+1}(a,*)}$ ${\displaystyle a}$

Смотрите также

• Рейтинг страницы

Цитаты

1. И. Антонеллис, Х. Гарсиа-Молина и К.-К. Чанг. Simrank++: переписывание запросов посредством анализа ссылок графа кликов. В VLDB '08 : Материалы 34-й Международной конференции по очень большим базам данных, страницы 408–421. [1]
2. В. Ю, С. Линь, В. Чжан, Л. Чанг и Дж. Пей. Больше – проще: эффективная и действенная оценка сходства пар узлов на основе гиперссылок. В VLDB '13 : Материалы 39-й Международной конференции по очень большим базам данных, страницы 13–24. [2]
3. Х. Чен и CL Джайлз. «ASCOS++: мера асимметричного сходства для взвешенных сетей для решения проблемы SimRank». Транзакции ACM по обнаружению знаний из данных (TKDD) 10.2 2015 г. [3]
4. Г. Джех и Дж. Видом. SimRank: мера структурно-контекстного сходства. В KDD'02 : Материалы восьмой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных, страницы 538-543. ACM Press , 2002. «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 12 мая 2008 г. Проверено 2 октября 2008 г.{{cite web}}: CS1 maint: archived copy as title (link)
5. Д. Лизоркин, П. Велихов, М. Гринев и Д. Турдаков. Методы оценки точности и оптимизации расчета SimRank. В VLDB '08 : Материалы 34-й Международной конференции по очень большим базам данных, страницы 422–433. «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 7 апреля 2009 г. Проверено 25 октября 2008 г.{{cite web}}: CS1 maint: archived copy as title (link)
6. С. Роте и Х. Шютце. CoSimRank: гибкая и эффективная мера сходства на основе теории графов. В ACL '14 : Материалы 52-го ежегодного собрания Ассоциации компьютерной лингвистики (Том 1: Длинные статьи), страницы 1392-1402. [4]
7. Д. Фогарас и Б. Рач. Масштабирование поиска по сходству на основе ссылок. В WWW '05 : Материалы 14-й международной конференции по Всемирной паутине, страницы 641–650, Нью-Йорк, Нью-Йорк, США, 2005. ACM . [5]
8. Антонеллис, Иоаннис, Гектор Гарсия Молина и Чи Чао Чанг. «Simrank++: переписывание запроса посредством анализа ссылок графа кликов». Труды Фонда VLDB 1.1 (2008): 408-421. arXiv : 0712.0499
9. В. Ю, С. Линь, В. Чжан. На пути к эффективному вычислению SimRank в больших сетях. В ICDE '13: Материалы 29-й Международной конференции IEEE по инженерии данных, страницы 601–612. «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 12 мая 2014 г. Проверено 9 мая 2014 г.{{cite web}}: CS1 maint: archived copy as title (link)

Источники

• Кай, Ю.; Конг, Г.; Цзя, X.; Лю, Х.; Он, Дж.; Лу, Дж.; Ду, X. (1 декабря 2009 г.). «Эффективный алгоритм вычисления сходства на основе ссылок в сетях реального мира». 2009 Девятая международная конференция IEEE по интеллектуальному анализу данных . стр. 734–739. дои :10.1109/ICDM.2009.136. ISBN 978-1-4244-5242-2. S2CID  9799597.