Sommario
• Introduzione
• Unapanoramicasulletecniche
• Content-based
• Collabora8veFiltering• Collabora8veFilteringinpra8ca:SVD
• RaccomandazioneGraph-based
• MetodiIbridi
• UnprogeBosviluppatodalnostrogruppo
Introduzione
• Un sistema di raccomandazione è una classe di
applicazioni (comunemente web-based) che
predicono le risposte degli uten8 sulla base delle
loropreferenze.
• Dueesempi:• Suggerirear8coliaileBorideiquo8dianion-line;
• Offrireaiclien8deisi8die-commercesuggerimen8sucosapotrebbeessere
dilorointeresse.
Esempiodisistemadiraccomandazione
• ClienteX• AcquistaCDMetallica
• AcquistaCDMegadeth
• ClienteY• FaunaricercasuiMetallica• IlsistemadiraccomandazionesuggerisceMegadethinbaseaida8colleziona8sulclienteX
Lemetodologie
• Diverse tecnologie ma due gruppi
principali:• Content-based systems: esaminare le proprietà degli
ar8coliperraccomandarnenuovi.
• Collabora5vefilteringsystems:usaremisuredisimilarità
tra uten8e/oprodoRper raccomandarenuovi prodoR
(oggeRsimiliodiproprietàdiuten8simili).
Diversi campi di applicazione: Raccomandazione prodotti: Amazon o simili; Raccomandazione film: Netflix o YouTube; Notizie: quotidiani o blog.
Definizione
• Sistemadiraccomandazionehadueclassidien5tà:
• UninsiemediUten5(U={u1,…,un})
• UninsiemediOgge>(O={o1,…,om})
rappresentateall’internodiunau5litymatrix(Um={duo}nxm)
• matricesparsacheperognicoppiautente-oggeBocalcolaungradodipreferenza
dell’utenteperl’oggeBo.
• ObieRvodel sistemadi raccomandazione:predire leentry
vuotedellamatriceperinferirelepreferenzedell’utente.
Esempio
Matrix
Alien
Star Wars
Casablanca
Titanic
Joe 1 1 1 0 0
Jim 3 0 3 0 0
John 4 4 4 0 0
Jack 0 5 5 0 0
Jill 0 0 3 4 4
Jenny 0 0 0 5 5
Jane 3 0 0 2 2
• La matrice rappresenta il rating che l’utente da al film visto usando la scala 1-5, con 5 rating più alto.
• Zero indica che l’utente non ha valutato il film.
Potremmo disegnare un sistema per prendere le proprietà dei film e predire le preferenze degli utenti anche se non hanno visto il film.
IlfenomenodellaLongtail
• Negozifisici:spaziolimitatosugliscaffali,mostrano
piccolafrazionediprodoR(ipiùpopolari).
• Web: non ha questo problema, cos8 per
pubblicizzareiprodoRviciniallozero…
• Piùsceltapergliuten8,ma…vannoaiuta8!
• Ci servono filtri migliori… usiamo i sistemi di
raccomandazione!
Problemichiave
• Collezionare valutazioni “conosciute” per la u8litymatrix.
• Predirevalutazioninuoveedelevateapar8redallevalutazioniconosciute.
ComeoBenerelevalutazioni(ra8ng)
• Costruire una u8lity matrix è un task complicato, due
approcci per scoprire il valore che un utente da ad un
prodoBo:
• Esplicito:• Chiederedivalutareunitem(es.YouTube).
• Implicito:
• Apprenderedalleazionidell’utente.
Estrapolarelau8litymatrixeraccomandare
• DescriviamoiquaBroapprocciprincipali:• Content-based
• Collabora5veFiltering
• Graph-based
• HybridApproach
RaccomandazioniContent-based
• Idea principale: gli oggeR raccomanda8
all’utente U sono simili agli oggeR valuta8
posi8vamentedaU.
• Il sistema focalizza sulle proprietà degli
ogge>.• Lasimilarità tradueoggeRèdeterminatamisurando la
similaritàdelleloroproprietà.
IlprofilodeglioggeR
• PerognioggeBosicreaunprofilo;
• Un Profilo è un insieme di feature che rappresentano
caraBeris8cheimportan8.
• I Documen5 sono una classe di oggeR per i quali non è
semplicedefinirequalidebbanoesserelefeature.
• Usareleparolepiùimportan5diundocumento.
• Comescegliamoleparoleimportan8?
• Tipicaeuris8caTF.IDF(TermFrequency5mesInverseDocFrequency)
TF.IDF
• “fij”frequenzadideltermine“i”neldocumento“dj”
• “ni”numerodidocumen8chemenzionanoiltermine“i”,
• Nilnumerototaledidocumen8,
TF.IDF:“wij=TFij·IDFi”
• Profilo diundocumento:insiemedelleparolechehannoil
piùaltoTF.IDFscore,assiemeailoroscore.
Profiliutenteepredizione
• Userprofile,diversepossibilità:• MediaponderatadeiprofilideglioggeR;
• ...
• Euris5cadipredizione:• Dato il profilo x dell’utente e il profilo i del prodo.o,s8miamo𝑢(𝒙,𝒊) = cos(𝒙,𝒊) = 𝒙·𝒊/||𝒙||⋅||𝒊||
Proecontro
+:Nonc'èbisognodida5sualtriuten5
+:Ingradodiconsigliareagliuten5congus5unici
+:Ingradodiraccomandarear5colinuovienonpopolari
+:faciledainterpretare
–:Trovarelefeaturegiusteèdifficile
–:Raccomandazionepernuoviuten5
–:Monomodale
Schemadelmetodo
Consideriamo l’utente x
Troviamo N altri utenti i cui rating sono “simili” ai rating di x
Stimiamo i rating di x sulla base degli N rating degli utenti
Comemisuriamolasimilarità
• Jaccardsimilarity:
sim(x,y)=|rx∩ry|/|rx∪ry|
• Cosinesimilarity:
sim(x,y)=cos(rx,ry)
• Pearsoncorrela5oncoefficient:
rx = [*, _, _, *, ***] ry = [*, _, **, **, _]
Predizioni
Dallasimilaritàallaraccomandazione:
• SiarxilveBoredira8ngdell’utentex
• SiaNl’insiemedeikuten8piùsimiliaxchehannovalutato
l’oggeBoi
• Predizionedell’oggedoiperl’utentex:• 𝑟↓𝑥𝑖 = 1/𝑘 ∑𝑦∈𝑁↑▒𝑟↓𝑦𝑖
• 𝑟↓𝑥𝑖 = ∑𝑦∈𝑁↑▒𝑠↓𝑥𝑦 ⋅ 𝑟↓𝑦𝑖 /∑𝑦∈𝑁↑▒𝑠↓𝑥𝑦
• Altreopzioni?
• Molte..
𝒔↓𝒙𝒚 =𝒔𝒊𝒎(𝒙,𝒚)
OggeBo-OggeBoCollabora8veFiltering
• Vista:oggedo-oggedo• TroviamoglioggeRsimiliai
• S8miamoilra8ngperiinbaseaira8ngdeglioggeRsimili
∑∑
∈
∈⋅
=);(
);(
xiNj ij
xiNj xjijxi s
rsr
sij… similarità degli oggetti i e j rxj…rating dell’utente x sull’oggetto j N(i;x)… set di oggetti simili a i valutati da x
CF:Approcciocomune
• DefiniamolasimilaritàsijtraglioggeRiej
• SelezioniamoknearestneighborN(i;x)
• OggeRpiùsimiliai,valuta8dall’utentex
• S8miamoilra8ngrxipesatoconlamedia:
Stima baseline per rxi ¡ μ=mediageneraledituRifilm¡ bx=deviazionedelra8ngdallamedia
dell’utentex=(avg.ra1ngutentex)–μ¡ bi=deviazionedelra8ngperl’oggeBoi
∑∑
∈
∈=);(
);(
xiNj ij
xiNj xjijxi s
rsr
∑∑
∈
∈−⋅
+=);(
);()(
xiNj ij
xiNj xjxjijxixi s
brsbr
𝒃↓𝒙𝒊 =𝝁+ 𝒃↓𝒙 + 𝒃↓𝒊
Proecontro
+:Lavoracontu>i5pidiogge>
+:Nonènecessariafeatureselec5on
-:Newuserproblem
-:Newitemproblem
-:Matricedeira5ngsparsa
DimensionalityReduc8on
• Possibile soluzione per il problema dovuto alla
“sparsità”dellamatrice?• DimensionalityReduc5on
• LatentSeman5cIndexing(LSI)• Tecnicaalgoritmicasviluppatatralafinedeglianni‘80primianni‘90
• Risolve problemi di sinonima, “sparsità” e scalabilità per grandi
dataset
• RiduceladimensionalitàecaBuralerelazionilaten8
• Si può mappare facilmente nel Collabora5ve
Filtering!
LSI
• Tecnica di indicizzazione che usa la SingularValue Decomposi5on per iden8ficare
paBernnella relazionetra terminieconceR
contenu8neltesto.
• Si basa sul principio che parole che sono
usatenellostessocontestotendonoadavere
significatosimile.
LSI per CF
• MatriceTermini-Documen8• SpaziodeiconceR• Mappingtra:
• Termini↔Conce>• Documen5↔Conce>
• MatriceUten8-OggeR• Spaziodellecategorie• Mappingtra:
• Ogge>↔Categorie• Uten5↔Categorie
NeklixChallenge
• Compe8zione per iden8ficare il migliore algoritmo di CF per predire
ra8ngdegliuten8perIfilm,sullabasedira8ngpreceden8.
• Prize:USD$1,000,000
• Compe8zioneiniziatanel2006
• Unteamhavintolacompe8zionenel2009(habaButol’algoritmousato
daNeklixmigliorandoleprestazionidel10.06%)
• Dataset:
• ~480,000uten8e~18,000film;solo~100milionidira8ng
• U8litymatrixsparsaal99%!(Circa8.5miliardidira5ngpotenziali)
Singular-ValueDecomposi8on(SVD)
• Rappresentazione low-dimensional di una matrice
high-dimensional• RappresentazioneesaBa
• Facilerimuovereledimensionimenosignifica8ve
• Algoritmiefficien8(R,matlab)
SVD-Definizione
A[nxm]=U[nxr]Λ[ rxr](V[mxr])T
• A:matricenxm(es,ndocumen8,mtermini)
• U:matricenxr(ndocumen8,rconceR)
• Λ:matricediagonalerxr(forzadiogni‘conceBo’)(r:rango(*)dellamatrice)
• V:matricemxr(mtermini,rconceR)
*
*Numerodirigheocolonnelinearmenteindipenden8dellamatrice
SVD-Proprietà
Decomposizionespedraledellamatrice
1 1 1 0 0 2 2 2 0 0 1 1 1 0 0 5 5 5 0 0 0 0 0 2 2 0 0 0 3 3 0 0 0 1 1
= x x u1 u2 l1
l2
v1 v2
#3Query
Matrix
Alien
Star Wars
Casablanca
Titanic
Joe 1 1 1 0 0
Jim 3 3 3 0 0
John 4 4 4 0 0
Jack 5 5 5 0 0
Jill 0 0 0 4 4
Jenny 0 0 0 5 5
Jane 0 0 0 2 2
Matrice di rango 2 relativa ai rating degli utenti ai film. Due concetti (categorie) :
• Fantascienza • Film romantici
EffeBuareraccomandazioni
• UsalaCosineSimilarity
• Grazie alla SVD, possiamo effeBuare delle
predizioniconunsempliceprodoBoscalare.• Datounutenteelalistadeira8ngdeifilmchehavistoea
zeroquellichenonhavisto(p):• Mappiamo i ra5ng corren5 dell’utente dallo spazio originale a quello
dellecategorie(mol5plichiamoperV,matricefilm-categorie): 𝑝 =𝑝×𝑉
• CalcoliamolaraccomandazioneusandonuovamentelamatriceV:
𝑝 = 𝑝 × 𝑉↑𝑇
Joe 1 1 1 0 0Jim 3 3 3 0 0
John 4 4 4 0 0
Jack 5 5 5 0 0
Jill 0 0 0 4 4
Jenny 0 0 0 5 5
Jane 0 0 0 2 2
0.14 0
0.42 0
0.56 0
0.70 0
0 0.60
0 0.75
0 0.30
12.4 0
0 9.5 x
0.58 0.58 0.58 0 0
0 0 0 0.71 0.71
x =
SVD
SVD–Queryconl’usodeiconceR
• Abbiamo l’utente (Alfredo) nuovo, non presente
nellamatrice.
• Possiamocapirecosaglipotrebbepiacere?
• HavistosoloMatrix,rate4
• Rappresen8amoAlfredocome:
p=[40000]
SVD–Queryconl’usodeiconceR
• MappiamoAlfredonellospaziodellecategoriemol8plicando
ilveBoreperlamatricedegliUten8-Categoria
0.58 0
0.58 0
0.58 0
0 0.71
0 0.71
Forteinteresseperlafantascienza
SimilaritàUtente-Categoria
PxV=[40000]x =[2.32,0]
SVD–Queryconl’usodeiconceR
• RimappiamoAlfredonellospaziodeifilmmol8plicando[2.32,0]per
VT.
0.58 0.58 0.58 0 0
0 0 0 0.71 0.71 [2.32,0]x =[1.35,1.35,1.35,0,0]
MetodiGraph-based
• Simile al Collabora8ve Filtering ma usa un grafo bipar5to per
immagazzinareleinformazioni.
• Le raccomandazioni sono oBenute a par8re dalla struBura della rete
bipar8ta.
• Dueclassidiiden8tà:Uten5(U)eOgge>(O).
• Definiamoilgrafobipar8tocomesegue:
• G(U,O,E,W)
• E={eij:uilikesoj)
• W:E→ℜ
• “E”insiemedegliarchie “W”èunafunzionecherappresentaildegreedi
preferenzacheunutentehaperilpar8colareoggeBo.
Lau8litymatrixcomegrafobipar8to
Joe
Jim
John
Jack
Jill
Jenny
Jane
1 3
4
4 5
2 4 5
2
5
5 5
1
1 3 3
5
4 4
NBI
• NBI(Network-basedinference)sviluppatonel2007.
• Bipar5tenetworkprojec5onperoBenereinformazionisulleproiezioni.
• Dopolaproiezione:• Re8connodidellostesso8po(uten8ooggeR);
• Duenodisonoconnessisesonocollega8daalmenounnododialtro8po;
NBI
• Idea base dell’algoritmo: flusso delle risorse sulla
retebipar8ta:• aglioggeRvieneassegnataunaquan8tàinizialedirisorse;
• inunprocessoadue fasi le risorse sono trasferitedaglioggeRagli
uten8esuccessivamentetrasferi8indietroaglioggeR;
• questo processo, con una fase di normalizzazione consente di
oBeneredegliscoreperlecoppieuten8-oggeR.
NBI
• Il calcolo dei pesi avvienea B r a v e r s o l a s e g u e n t eequazione:
• DoveΓ(i,j)èdefinitacome:• Γ(i,j)=D(oj)perNBI
• Γ(i,j)=D(oi)perHeatS
• D(t) degreedelnodo “t”nellaretebipar8ta.
RaccomandazioniconNBI
• Il peso “wij” della proiezione corrisponde a quante risorse
vengono trasferitedall’oggeBo“j”all’oggeBo“i”,oquanto
piaceràl’oggeBo“j”adunutenteacuipiacel’oggeBo“i”.
• Data la matrice di adiacenza “A” del grafo bipar8to e la
matrice“W”,lamatricediraccomandazione“R”pertuRgli
uten8puòesserecalcolatainununicostep:
𝑅=𝑊×𝐴
Proecontro
+:Funzionasutu>i5pidiogge>
+: Risolve il problema della sparsità della u5lity
matrix.
-:Newuserproblem
-:Newitemproblem
-:Richiedeimportan5risorsecomputazionali
Metodiibridi
• Usare in combinazione diversi metodi di
raccomandazione
• Supponiamodiavereimetodi“X”e“Y”chedanno
rispeRvamentegliscore“xa”e“ya”.Loscorediun
modelloibridopuòessereoBenutocome:
• λ∈[0;1]
Mo8vazioni
InseBoricomelabiomedicina
• LeBeraturascien8ficaenorme;
• Cen8naia di database con risulta8 di analisi
sperimentali;
• Può essere difficile a volte iden8ficare risulta8 già
conosciu8..Pocominingsuques8da8..
Mo8vazioni
• Problema:
An8cipare l’informazione di cui l’utente ha bisogno (ma
nonlosa!!).
Definizione:
Dato un insieme di termini che l’utente ha oBenuto per un
ar8colo, interrogando un search engine, vogliamo
raccomandare un insiemepiccolo, significa5vo edifferente,
diterminirilevan=perl’ar8colomanoncontenu8inesso.
Abstractannota8on:unmodoperinferirenuoveipotesi
E2F3 senescence
mir-499 microRNA
EZH2 PDGFB CTGF SOX4
microRNA Cancer
Proposta
• BioTAGMEo Un sistemaper l’estrazione di informazioni nella formadi termini
seman5camentecorrela5:tag/ancoredaPubMed.
o Duetecnologie:ü TAGME:Sistemaperl’estrazionediannotazionidates8;
ü DT-Hybrid:Algoritmodiraccomandazione.
o Ilcontesto Circa 25 milioni di citazioni dalla letteratura biomedica
• TAGME:toolpereffeBuareannotazionion-the-flyintes8nonstruBura8conl’usodi
Wikipedia.
On this day 24 years ago Maradona scored his infamous "Hand of God" goal against England in the quarter-final of the 1986
DT-Hybrid
• DT-Hybrid:tecnicadiraccomandazionegraph-based
o Applicatanelcontestodrug-targetinterac8onpredic8oneneldrugreposi8oning.
o Frameworkgenerale
o DT-HybridstandaloneRpackageewebapp.
Query TAGME Document/Tag Matrix
Candidate Terms Matrix
DT-Hybrid
TAGME Semantic Similarity
Matrix
Sets of Candidate
Terms
Sets of significant
Annotations
Corpus of Abstracts
Pubmed Search
BioTAGMEPipeline
p-Value based filtering
Correlation and
Grouping
Tags Glossary
BioTAGMEwebapp:Architecture
Query
REST API JSON Response
NCBI Pubmed
Entrez
Utilites
XML
Response
DT-Hybrid
Acasestudy:“MicroRNA”
# Paper Source Terms
Predicted Terms
Correlation p-Value
1 Circulating u2 small nuclear rna fragments as a novel diagnostic tool for patients with epithelial ovarian cancer.
4 5 0,90 < 0,01
2 Tumor-suppressive microrna-449a induces growth arrest and senescence by targeting e2f3 in human lung cancer cells.
5 6 0,80 < 0,01
Acasestudy:“MicroRNA”
Source Terms Novel Terms
microrna u2 spliceosomal rna
small nuclear rna ovarian cancer
Correlation Citation
mRNA 0,90 -
ncRNA 1,00 -
parp inhibitor 0,91 The emerging role of parp inhibitors in the treatment of epithelial ovarian cancer.
muc1 0,98 Expression of muc1 and muc2 mucins in epithelial ovarian tumours.
xiap 0,93 Expression and clinical significance of xiap and caspase-3 protien in primary epithelia ovarian cancer.
# Paper Source Terms
Predicted Terms
Correlation p-Value
1 Circulating u2 small nuclear rna fragments as a novel diagnostic tool for patients with epithelial ovarian cancer.
4 5 0,90 < 0,01
Acasestudy:“MicroRNA”
Source Terms Novel Terms
guangzhou senescence
e2f3 mir-449
microrna
Correlation Citation
ezh2 1,00 Validation of the histone methyltransferase ezh2 as a therapeutic target for various types of human cancer and as a prognostic marker
pdgfb 0,80 Pdgf receptors as targets in tumor treatment.
col4a1 1,00 -
ctgf 1,00 Connective tissue growth factor and its role in lung adenocarcinoma invasion and metastasis.
sox4 1,00 -
mcl1 1,00 Mcl-1 regulates survival and sensitivity to diverse apoptotic stimuli in human non-small cell lung cancer cells.
# Paper Source Terms
Predicted Terms
Correlation p-Value
2 Tumor-suppressive microrna-449a induces growth arrest and senescence by targeting e2f3 in human lung cancer cells.
5 6 0,80 < 0,01
ProgeBoinprogress:what’snext
• PubMedofflineCrawling;
• Automa8cbibliographyconstruc8on;
• Sviluppo versione custom di BioTAGME con le
ontologiebiomediche(OMIM,GO).
• Integrazionedibancheda8esterne:raccomandazione
domain-tuned.
Takehomemessage
• ModelliLatentFactoregraphbasedmolto
efficaci.
• Spazio di applicazione dei sistemi di
raccomandazionemoltoampio.
• Moltelibrerieesisten8.
Bibliografiaeringraziamen8
• Alcunicontenu8sonoriadaBa8daMiningMassiveData:hBp://www.mmds.org/
• MetodiGraph-based:
• Zhou, T., Ren, J., Medo, M., and Zhang, Y. (2007). Bipar5te network projec5on and personal recommenda5on. Physical
ReviewE,76(4),046115–22.
• Zhou, T., Kuscsik, Z., Liu, J.-G.,Medo,M.,Wakeling, J. R., and Zhang, Y.-C. (2010).Solving theapparentdiversity-accuracy
dilemmaofrecommendersystems.ProceedingsoftheNa8onalAcademyofSciences,107(10),4511–4515.
• AlgoritmoDT-Hybrid:
• Alaimo S, Pulviren8 A, Giugno R, Ferro A.Drug–target interac5on predic5on through domain-tuned network-
basedinference.Bioinforma8cs201329:2004-2008.
• AlaimoS,GiugnoR,Pulviren8A."ncPred:ncRNA-DiseaseAssocia8onPredic8onthroughTripar8te
Network-BasedInference."Fron1ersinbioengineeringandbiotechnology2(2014).
• TAGME
• Ferragina, P., Scaiella, U. (2012). Fast and Accurate Annota5on of Short Texts withWikipedia
Pages.IEEESo�ware29(1):70-75.AlsoappearedinProcsACMCIKM(2010,pp.1625-1628).
• BioTAGME
• Alaimo S, Ferragina P, Ferro A, Giugno R, Pulviren8 A. An algorithm for the predic5on of
annota5onsonPubmed(submided)
Ilteam!
AlfredoFerro,FullProfessor,UniversitàdiCatania
SalvatoreAlaimo,Post-Doc,UniversitàdiCatania
RosalbaGiugno,AssociateProfessor,UniversitàdiVerona
PaoloFerragina,FullProfessor,UniversitàdiPisa
Top Related