Václav Nádraský 3/2010
1. Úvod
2. Model sociální sítě
3. Ohodnocovací model v sociálních sítí
4. Zpracování dotazu
5. Dosažené výsledky u implementací v reálných sítích 6. Závěrečné zhodnocení
Sociální sítě se staly velmi populárními ◦ Mnoho uživatelů, mnoho dat
Nové způsoby propojení publikovaných informací ◦ Vztahy mezi uživateli ◦ Použití tagů (nebo jiné, uživatelsky specifické, formy definice skóre)
Facebook, del.icio.us, Flickr, LibraryThing, MySpace, LinkedIn, YouTube…
SS (sociální sítě) nabízí nové způsoby vyhledávání ◦ ◦ ◦ ◦
Výsledek dotazu závisí na iniciátorovi dotazu Více důvěřuji doporučení svých přátel Příbuznost tagů „Wisdom of the crowd“ (Explicitní, Implicitní)
Velké množství možností v dotazování ◦ Vyžaduje efektivní a škálovatelné metody ◦ Běžné způsoby dotazování
Neefektivní (DataMining – data rychle narůstají) Neberou v potaz vztahy mezi uživateli (Web search)
Nový inkrementální top-k algoritmus (založený na threshold algoritmu) s dvourozměrnou expanzí ◦ Sociální expanze ◦ Sémantická expanze
Různé zaměření různých SS ◦ Všechny jsou ale založené na podobném principu
Formálnější definice SS ◦ ◦ ◦ ◦
Uživatelé se musí registrovat Produkují obsahové informace = „dokumenty“ Přidávají k dokumentům tagy, popř. hodnocení Uživatelé si definují svůj vlastní seznam přátel Velikost seznamu ~ reputace uživatele v dané síti
SS lze chápat jako graf
Friendship(User1, User2, FriendshipStrength) ◦ Určuje existenci uživatele 2 na seznamu přátel uživatele 1 ◦ Lze definovat i sílu vztahu ◦ Tranzitivní uzávěr
TagSimilarity(Tag1, Tag2, TagSim) ◦ Různá slova, stejný význam ◦ Synonyma, hyponyma
Linkage(Document1, Document2, Weight) ◦ Odkazy mezi dokumenty ◦ GPS souřadnice pro místo pořízení fotografie
DocContent(Document, Tag, ContentScore) ◦ Určuje přiřazení tagu k dokumentu ◦ Pomocí ContentScore lze určit i jak dobře tag dokument vystihuje
Tagging(User, Tag, TagScore)
◦ Zdali uživatel použil (a jak intenzivně) daný tag ◦ Určuje témata, o které se uživatel zajímá
Rating(User, Document, RatingScore)
◦ Typicky hodnocení dokumentu uživatelem ◦ V jistých případech lze chápat i jako autorství
Dotaz Q(u, q1 … qn)
◦ u je iniciátor dotazu ◦ q1 … qn je seznam hledaných tagů pro zjednodušení bez vah
◦ relevantní výsledek dotazu seřazen podle příslušného skóre
výsledek závisí na iniciátorovi (oproti standardnímu IR dotazu)
Ohodnocovací model je rozšířen o
◦ relativní důležitost uživatelů vůči iniciátorovi ◦ relativní důležitost použitého tagu vůči uživateli ◦ (volitelně) podobnost tagů
Fu (u)
Funkce udávající důležitost uživatele relativně k iniciátorovi Fu (u ) 0
uživatele nezajímají jeho dokumenty
u U
Fu (u) 1
lze nahlédnout jako na pravděpodobnost
Několik možných interpretací ◦ Syntaktický pohled velikost průniku společných tagů
◦ Sociální pohled vzdálenost v grafu mezi uživateli
◦ Globální pohled Globální důležitost uživatele (PageRank)
Fu (u)
Kombinace syntaktického a sociálního pohledu
Podobnost přímo spojených uživatelů
Podobnost nepřímo spojených uživatelů
Finální podobnost
konstantní podobnost (závisí na α) je pro uživatele bez konexí
sfu (d , t )
Nahrazuje klasickou frekvenci tf Odráží podobnost uživatelů, kteří použili tag na dokument, který může být předmětem zájmu iniciátora
◦ kolikrát uživatel použil tag t na dokumentu d
pro dnešní sociální sítě je to typicky binární hodnota 1 (použil) nebo 0 (nepoužil)
Po dosazení
◦
globální část (nezávisí na iniciátorovi)
su (d , t )
skóre dokumentu d vzhledem k tagu t ohodnocovací funkce (zjednodušená BM25)
k1 je definovatelný koeficient (tunable coefficient in BM25) idf(t) je inverzní frekvence tagu v dokumentech
df(t) je počet dokumentů, které byly označeny tagem t
◦ na rozdíl od originální formule BM25 se nebereme v potaz délka dokumentů
* u
s (d , t )
Uživatelé nepoužívají unifikované tagy ◦ Je třeba „sjednocovat“ významově stejné tagy ◦ Ne vždy je to dobrá volba ověřeno experimentálně
◦ Zvolena opatrná expanze „careful expansion“ expandují se jen ti „nejlepší“
◦ Podobnost tagů:
Skóre dokumentu d vzhledem k tagu t (včetně expanze)
* u
s (d , q1 ,, qn )
Součet všech dílčích skóre pro všechny tagy v dotazu
Based on threshold algorithm over impactorder inverted lists ◦ Nelze však předpočítávat skóre pro každý tag nebo uživatele (skóre je závislé na iniciátorovi)
Nová verze algoritmu ContextMerge ◦ Využívá „indexy“, které jsou již z principu dostupné Seznam dokumentů otagovaných konkrétním uživatelem Počet dokumentů, na které byl použit konkrétní tag
◦ Skóre počítá průběžně – inkrementálně Pro dokumenty udržuje horní a dolní hranici skóre Lze tedy vykonávání ukončit „dříve“
Je využíváno několika indexů
◦ lze je předzpracovat v čase tvoření indexů
DOCS(t)
◦ obsahuje seznam dokumentů pro daný tag spolu s globální frekvencí tagu TF(d,t)
USERDOCS(u,t)
FRIENDS(u)
SIMTAGS(t)
◦ obsahuje pro daného uživatele u a tag t množinu dokumentů spolu s tfu(d,t) ◦ obsahuje seznam přátel uživatele u spolu s Pu(u’) ◦ obsahuje seznam tagů podobných tagu t spolu s tsim(t,t’)
Během zpracování se sekvenčně čtou indexy USERDOCS a DOCS V jedné iteraci hlavní smyčky se načte celkem batchsize nových dokumentů (prokládaně z indexů USERDOCS a DOCS), které mají nejlepší očekávané skóre (vyhodnocuje funkce ChooseNextList) ◦
udržuje se hodnota high[i] a highF[i] – poslední přečtená hodnota z indexu DOCS a FRIENDS
Během zpracování se udržuje seznam zatím nejlepších kandidátů na top-k Každý kandidát obsahuje následující informace: ◦
- hodnota přečtená z indexu DOCS (pro každý tag q)
◦ ◦
- množina indexů již přečtených DOCS
◦
- kolikrát byl dj v uživatelském seznamu pro qi
◦
- dolní hranice finálního skóre
◦
- horní hranice finálního skóre
Experimentální implementace nad reálnými sítěmi ◦ del.icio.us 12389 uživatelů, 175754 záložek 2781096 tagů, 152306 přátel ◦ Flickr 52347 uživatelů, 10000000 obrázků 29111183 tagů, 1293777 přátel (ve smyslu okomentování obrázků) ◦ LibraryThing 9986 uživatelů, 6453605 knížek 14295693 tagů, 17317 přátel
Co jsou relevantní výsledky? ◦ Velmi závislé na iniciátorovi ◦ Nelze jednoduše definovat
2 nezávislé metody vyhodnocení ◦ user-specific ground truth ◦ uživatelská studie
Dokumenty, které byly označeny všemi tagy v dotazu iniciátorem nebo jeho přímými přáteli
◦ Uživatel pravděpodobně tyto dokumenty viděl a souhlasil s použitými tagy
Dotazy náhodně vybrány z dvojice tagů se střední hodnotou frekvence použití
Iniciátor náhodně vybrán z uživatelů, kteří tyto tagy použili, a má alespoň jednoho přítele
Nelze použít u Flickeru
◦ Téměř žádný průnik použitých tagů
5 reálných uživatelů na LibraryThing ◦ každý použil tag na alespoň 20 knížek ◦ každý navázal nějaká přátelství
Uživatelé navrhli 28 dotazů vztahujících se k „jejich“ knížkám Po vyhodnocení dotazů iniciátor manuálně doplnil výsledek dotazu o informaci „vysoce relevantní“, „relevantní“, „úplně mimo“ (očima iniciátora)
Jako hodnocení pro určité hodnoty α spočítána ◦ Přesnost ◦ NDCG (Normalized Discounted Cumulative Gain)
Uživatelská studie
User-specific ground truth
◦ Sémantický pohled zdá se důležitější než sociální ◦ Pokud není zahrnuta sociální komponenta vůbec, efektivita výsledku naopak klesne
Jazyk ◦
DB server ◦
Windows 4xOperton 16GB RAM
Porovnáváno se základním algoritmem ◦
Oracle 10b
Server ◦ ◦ ◦
Java
join-then-sort
Horní graf bez expanze tagů ◦ Více než 50% úspora času
Dolní graf včetně expanze tagů ◦ 3-5 násobná úspora času
Nové možnosti ohodnocování dokumentů ◦ relevantnější výsledky
Upravený top-k algoritmus ContextMerge ◦ Velmi efektivní ◦ Menší počet přístupů na disk ◦ Několikanásobně rychlejší
Světlá budoucnost
Zdroj informací ◦ Efficient Top-k Querying over Social-Tagging Networks
R. Schenkel, T. Crecelius, M. Kacimi, S. Michel, T. Neumann, J. X. Parreira, G. Weikum
SIGIR’08, 07/2008, Singapore
http://lsirpeople.epfl.ch/smichel/publications/sigir2008.pdf
