SimRank - SimRank

SimRank je generál opatření podobnosti, založené na jednoduchém a intuitivním graficko-teoretický model.SimRank je použitelný ve všech doména s objektem na objekt vztahy, který měří podobnost strukturálního kontextu, ve kterém se objekty vyskytují, na základě jejich vztahů s jinými objekty. Účinně je SimRank měřítkem, které říká „dva objekty jsou považovány za podobné, pokud na ně odkazují podobné objekty„Ačkoli je SimRank široce přijímán, může vyprodukovat nepřiměřené skóre podobnosti, které je ovlivněno různými faktory a lze jej vyřešit několika způsoby, například zavedením faktoru důkazní váhy,^[1] vkládání dalších výrazů, které SimRank zanedbává^[2] nebo pomocí alternativ založených na PageRank.^[3]

Úvod

Mnoho aplikace vyžadují míru „podobnosti“ mezi objekty. Jedním zjevným příkladem je dotaz „najít podobný dokument“ na tradiční textové korpusy nebo Celosvětová Síť Obecněji, a opatření podobnosti lze zvyknout klastrové objekty, například pro společné filtrování v doporučující systém, ve kterém jsou „podobní“ uživatelé a položky seskupeny podle preferencí uživatelů.

K určení podobnosti lze použít různé aspekty objektů, obvykle v závislosti na doméně a příslušné definici podobnosti pro danou doménu. korpus dokumentů lze použít odpovídající text a pro společné filtrování lze podobné uživatele identifikovat podle společných předvoleb. SimRank je obecný přístup, který využívá vztahy mezi objekty v mnoha doménách, které nás zajímají. Web například dvě stránky spolu souvisejí, pokud existují hypertextové odkazy Podobný přístup lze uplatnit na vědecké práce a jejich citace nebo na jakýkoli jiný korpus dokumentu s křížový odkaz V případě doporučovacích systémů představuje preference uživatele pro položku vztah mezi uživatelem a položkou. Tyto domény jsou přirozeně modelovány jako grafy, s uzly představující objekty a hrany představující vztahy.

Intuice za algoritmem SimRank spočívá v tom, že v mnoha doménách podobné objekty jsou odkazovány podobnými objektyPřesněji řečeno, objekty ${displaystyle a}$ a ${displaystyle b}$ jsou považovány za podobné, pokud jsou namířeny z předmětů ${displaystyle c}$ a ${displaystyle d}$, respektive, a ${displaystyle c}$ a ${displaystyle d}$ jsou si podobní základní případ je to, že objekty jsou si maximálně podobné.^[4]

Je důležité si uvědomit, že SimRank je obecný algoritmus, který určuje pouze podobnost strukturálního kontextu. SimRank se vztahuje na jakoukoli doménu, kde existuje dostatek relevantních vztahů mezi objekty, aby založila alespoň určitou představu o podobnosti na vztazích. - důležité jsou také specifické aspekty; tyto mohou - a měly by být kombinovány s relační strukturálně-kontextovou podobností pro celkovou míru podobnosti. Například pro webové stránky SimRank lze kombinovat s tradiční textovou podobností; stejná myšlenka platí pro vědecké práce nebo jiné korpusy dokumentů. U doporučovacích systémů mohou existovat zabudované známé podobnosti mezi položkami (např. oba počítače, oba oděvy atd.), jakož i podobnosti mezi uživateli (např. stejné pohlaví , stejná úroveň výdajů). Tyto podobnosti lze znovu kombinovat se skóre podobnosti, která se počítají na základě vzorů preferencí, aby se vytvořilo celkové měřítko podobnosti.

Základní rovnice SimRank

Pro uzel ${displaystyle v}$ v orientovaném grafu označíme ${displaystyle I (v)}$ a ${displaystyle O (v)}$ soubor sousedních a odchozích sousedů ${displaystyle v}$Jednotliví sousedé jsou označováni jako ${displaystyle I_ {i} (v)}$, pro ${displaystyle 1leq ileq left | I (v) ight |}$a jednotliví sousedé jsou označováni jako ${displaystyle O_ {i} (v)}$, pro ${displaystyle 1leq ileq left | O (v) ight |}$.

Označme podobnost mezi objekty ${displaystyle a}$ a ${displaystyle b}$ podle ${displaystyle s (a, b) v [0,1]}$. V návaznosti na dřívější motivaci je napsána rekurzivní rovnice ${displaystyle s (a, b)}$.Li ${displaystyle a = b}$ pak ${displaystyle s (a, b)}$ je definován jako ${displaystyle 1}$.V opačném případě,

${displaystyle s (a, b) = {frac {C} {left | I (a) ight | left | I (b) ight |}} součet _ {i = 1} ^ {left | I (a) ight | } součet _ {j = 1} ^ {left | I (b) ight |} s (I_ {i} (a), I_ {j} (b))}$

kde ${displaystyle C}$ je konstanta mezi ${displaystyle 0}$ a ${displaystyle 1}$.Malá techničnost je zde také to ${displaystyle a}$ nebo ${displaystyle b}$ nemusí mít žádné sousedy. Protože neexistuje způsob, jak odvodit jakoukoli podobnost mezi nimi ${displaystyle a}$ a ${displaystyle b}$ v tomto případě je podobnost nastavena na ${displaystyle s (a, b) = 0}$, takže součet ve výše uvedené rovnici je definován jako ${displaystyle 0}$ když ${displaystyle I (a) = emptyset}$ nebo ${displaystyle I (b) = emptyset}$.

Maticová reprezentace SimRank

Nechat ${displaystyle mathbf {S}}$ být matice podobnosti, jejíž vstup ${displaystyle [mathbf {S}] _ {a, b}}$ označuje skóre podobnosti ${displaystyle s (a, b)}$, a ${displaystyle mathbf {A}}$ být sloupec normalizovaná matice sousedství, jejíž záznam ${displaystyle [mathbf {A}] _ {a, b} = {frac {1} {| {mathcal {I}} (b) |}}}$ pokud existuje hrana z ${displaystyle a}$ na ${displaystyle b}$, a 0 jinak. Pak lze v maticových notacích formulovat SimRank jako

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

kde ${displaystyle mathbf {I}}$ je matice identity.

Výpočet SimRank

Řešení rovnic SimRank pro graf ${displaystyle G}$ lze dosáhnout opakování do a pevný bod.Nechat ${displaystyle n}$ být počet uzlů v ${displaystyle G}$Pro každou iteraci ${displaystyle k}$, můžeme si nechat ${displaystyle n ^ {2}}$ záznamů ${displaystyle s_ {k} (*, *)}$, kde ${displaystyle s_ {k} (a, b)}$ dává skóre mezi ${displaystyle a}$ a ${displaystyle b}$ na iteraci ${displaystyle k}$Postupně počítáme ${displaystyle s_ {k + 1} (*, *)}$ na základě ${displaystyle s_ {k} (*, *)}$Začínáme s ${displaystyle s_ {0} (*, *)}$ kde každý ${displaystyle s_ {0} (a, b)}$ je dolní mez skutečného skóre SimRank ${displaystyle s (a, b)}$:

${displaystyle s_ {0} (a, b) = {egin {cases} 1 {mbox {}}, {mbox {}} {mbox {if}} a = b {mbox {}}, 0 {mbox {} }, {mbox {}} {mbox {if}} aeq b {mbox {}}. end {cases}}}$

Vypočítat ${displaystyle s_ {k + 1} (a, b)}$ z ${displaystyle s_ {k} (*, *)}$, použijeme základní rovnici SimRank k získání:

${displaystyle s_ {k + 1} (a, b) = {frac {C} {left | I (a) ight | left | I (b) ight |}} součet _ {i = 1} ^ {left | I (a) ight |} součet _ {j = 1} ^ {left | I (b) ight |} s_ {k} (I_ {i} (a), I_ {j} (b))}$

pro ${displaystyle aeq b}$, a ${displaystyle s_ {k + 1} (a, b) = 1}$ pro ${displaystyle a = b}$To znamená při každé iteraci ${displaystyle k + 1}$, aktualizujeme podobnost ${displaystyle (a, b)}$ pomocí skóre podobnosti sousedů ${displaystyle (a, b)}$ z předchozí iterace ${displaystyle k}$ podle základní rovnice SimRank. Hodnoty ${displaystyle s_ {k} (*, *)}$ jsou neklesající tak jako ${displaystyle k}$ zvyšuje. Bylo ukázáno v ^[4] že hodnoty konvergovat na limity splňuje základní rovnici SimRank, skóre SimRank ${displaystyle s (*, *)}$, tj. pro všechny ${displaystyle a, bin V}$, ${displaystyle lim _ {k o infty} s_ {k} (a, b) = s (a, b)}$.

Původní návrh SimRank navrhl zvolit faktor rozpadu ${displaystyle C = 0,8}$ a pevné číslo ${displaystyle K = 5}$ provedených iterací. Nedávný výzkum ^[5] ukázaly, že dané hodnoty pro ${displaystyle C}$ a ${displaystyle K}$ obecně znamenají relativně nízké přesnost iterativně vypočítaných skóre SimRank. Pro zajištění přesnějších výsledků výpočtu navrhuje tento článek buď použití menšího faktoru rozpadu (zejména ${displaystyle C = 0,6}$) nebo více iterací.

CoSimRank

CoSimRank je varianta SimRank s výhodou, že má také místní formulaci, tj. CoSimRank lze vypočítat pro jeden pár uzlů.^[6] Nechat ${displaystyle mathbf {S}}$ být matice podobnosti, jejíž vstup ${displaystyle [mathbf {S}] _ {a, b}}$ označuje skóre podobnosti ${displaystyle s (a, b)}$, a ${displaystyle mathbf {A}}$ být sloupcová normalizovaná matice sousedství. Pak v maticových notacích lze CoSimRank formulovat jako:

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

kde ${displaystyle mathbf {I}}$ je matice identity. Chcete-li vypočítat skóre podobnosti pouze jednoho páru uzlů, nechte ${displaystyle p ^ {(0)} (i) = e_ {i}}$, s ${displaystyle e_ {i}}$ je vektorem standardního základu, tj ${displaystyle i}$-tá položka je 1 a všechny ostatní položky jsou 0. Potom lze CoSimRank vypočítat ve dvou krocích:

1. ${displaystyle p ^ {(k)} = Ap ^ {(k-1)}}$
2. ${displaystyle s (i, j) = součet _ {k = 0} ^ {infty} C ^ {k} jazyk p ^ {(k)} (i), p ^ {(k)} (j) úhel}$

Prvním krokem je zjednodušená verze přizpůsobeného PageRank. Krok dva shrnuje vektorovou podobnost každé iterace. Maticová i lokální reprezentace počítají stejné skóre podobnosti. CoSimRank lze také použít k výpočtu podobnosti sad uzlů úpravou ${displaystyle p ^ {(0)} (i)}$.

Další výzkum na SimRank

• Fogaras a Racz ^[7] navrhl urychlení výpočtu SimRank pravděpodobnostní výpočet pomocí Metoda Monte Carlo.
• Antonellis a kol.^[8] rozšířené SimRankovy rovnice, aby se zohlednil (i) důkazní faktor pro incident uzly a (ii) hmotnosti závaží.
• Yu a kol.^[9] dále vylepšil výpočet SimRank pomocí jemnozrnného memorování metoda sdílení malých společných částí mezi různými dílčími částkami.
• Chen a Giles diskutovali o omezeních a případech správného použití SimRank.^[3]

Memoizace částečných částek

Lizorkin a kol.^[5] navrhla tři optimalizační techniky pro urychlení výpočtu SimRank:

1. Výběr základních uzlů může eliminovat výpočet zlomku párů uzlů s apriorním nulovým skóre.
2. Memoizace částečných součtů může účinně snížit opakované výpočty podobnosti mezi různými páry uzlů ukládáním části součtů podobnosti do mezipaměti pro pozdější opětovné použití.
3. Nastavení prahové hodnoty podobnosti umožňuje další snížení počtu párů uzlů, které se mají vypočítat.

Zejména druhé pozorování memoizace částečných částek hraje prvořadou roli ve velkém urychlení výpočtu SimRank z ${displaystyle {mathcal {O}} (Kd ^ {2} n ^ {2})}$ na ${displaystyle {mathcal {O}} (Kdn ^ {2})}$, kde ${displaystyle K}$ je počet iterací, ${displaystyle d}$ je průměrný stupeň grafu a ${displaystyle n}$ je počet uzlů v grafu. Ústřední myšlenka memoizace částečných částek se skládá ze dvou kroků:

Nejprve částečné částky ${displaystyle I (a)}$ jsou memoized jako

${displaystyle {ext {Partial}} _ {I (a)} ^ {s_ {k}} (j) = součet _ {iin I (a)} s_ {k} (i, j), qquad (pro všechny jin I (b))}$

a pak ${displaystyle s_ {k + 1} (a, b)}$ je iterativně počítáno z ${displaystyle {ext {Partial}} _ {I (a)} ^ {s_ {k}} (j)}$ tak jako

${displaystyle s_ {k + 1} (a, b) = {frac {C} {| I (a) || I (b) |}} součet _ {jin I (b)} {ext {částečný}} _ {I (a)} ^ {s_ {k}} (j).}$

V důsledku toho výsledky ${displaystyle {ext {Partial}} _ {I (a)} ^ {s_ {k}} (j)}$, ${displaystyle for all jin I (b)}$, lze znovu použít později, když vypočítáme podobnosti ${displaystyle s_ {k + 1} (a, *)}$ pro daný vrchol ${displaystyle a}$ jako první argument.

Viz také

• PageRank

Citace

Zdroje

• Cai, Y .; Cong, G .; Jia, X .; Liu, H .; On, J .; Lu, J .; Du, X. (01.12.2009). „Efektivní algoritmus pro výpočet podobnosti propojení v sítích reálného světa“. 2009 Devátá mezinárodní konference IEEE o dolování dat: 734–739. doi:10.1109 / ICDM.2009.136. ISBN  978-1-4244-5242-2.