Khoa CNTT – TRƯỜNG ÐẠI HỌC KHOA HỌC TỰ NHIÊN
Tìm hiểu về hệ thống tư vấn thông tin di
động
Đồ Án Môn Phương Pháp Nghiên Cứu Khoa Học
TP.HCM 2012
ng dn: GS.TSKH Hoàng Kim
Sinh viên thc hin: Nguyn Th Ngc Hoa
Mã s sinh viên: 1112011
Mobile Location-Based Recommender System

2 Lời mở đầu



 . 













, 
không dây,  , 



 ng (Mobile
Recommender Systems  MRSs) 



















(Location Based Services) 



.
Tài liu này 







, , 








3

Contents


1. Tng quan v u khoa hc 4
1.1 1. Gii Thin Sáng To Khoa Hc 4
1.2 n Sáng To Trong Tin Hc 5
1.3 Gii thiu 40 Nguyên tc sáng to trong khoa hc k thut 5


2. Tng quan v các h thng 11
2.1 Location Based Services (LBSs) ? 11
2.1.1 



 11
2.1.2 

(Geographic Information Systems)  12
2.1.3 



(Location-Based Services Infrastructure) 12
2.1.4 

(Types of Location-Based Services) 13
2.2 Recommender System 14



4. Các nguyên tc sáng tc vn dng trong xây dng FourSquare 28
Mobile Location-Based Recommender System

4



1. 
1.1 
Nói mt cách ngn gN SÁNG TO" (Creativity Methodologies) là b môn
khoa hc có mc ng và trang b cho mi h th c
hành tiên tin v  gii quyt v và ra quynh mt cách sáng to, v lâu dài, tin ti
u khi
N SÁNG TO" là phn ng dng ca khoa hc rng li hình thành
và phát trin trong thi gian gC SÁNG TO (Creatology).
Theo các nhà nghiên cu sau nông nghip, công nghip và tin hc. Làn sóng ng vi Creatology (hay
còn gi là thi hu tin hc) chính là s nhn mnh vai trò ch th to ci
trong th k XXI.
Mi làm vic, không th i ci tin công vic ph cho mi suy
a chúng ta. Nói cách khác, mu c sáng to là
tài nn nht ca mi. Chúng ta cn sáng to vì chúng ta cm thy rng, mi vic
cc thc hi nào, chúng ta vn
luôn mong mun ta.
Sáng to gn lin vi s i mi), sáng chng m
la chn mi. S sáng to thuc v c ra quynh, thuc v s kt hc liên



- 









.
- .
- 





 

.
(02) 








 , ) 


.
- .
- 















 






.





- 






















.
- 



- 



























Mobile Location-Based Recommender System

, 
(09) 








- Gâ




























- 

  ,  , 




.
- 



, 












, , 

.
(12) 






- 




















, 







.
(14) 



( ) 
- 











 , 







.
(15) 




- 














.
- 













. n.
(17) 








- 







 (  ) 





.
- .
- S.
- 































.
- 









, .
- 
































.
(20) 
















).
- 









.
- 












.
- 











.
(22) 










- 


















.
- 



















, .
(24) 






- 





, 

.
(25) 








- 





, , 

.
(26) 



(copy)
- 













 , 






 (, 
) 







.
- 






























 (
).
(28) 






-  



, quang, 

, 




.
- 











 , 




gian, .
- 
















 , 











 : 
, , , , .
(30) 




















-  (


, 

)
- 







, 







- 













.
- 


















, .
- 









, .
(33) 






- 



 , 










.
(34) 












- 





















- 

 .
- 









.
- 













 : 




, 




(37) 










, 





















.
(38) 








- 

 





.
- 





, , .
Mobile Location-Based Recommender System

10

- 


















 (
composite). 

, 











.

Mobile Location-Based Recommender System

11












?










 , 






















(Location Based Services).
2.1 Location Based Services (LBSs) ?
2.1.1 




  .









 “Where are you? Can I join?”, 
.
Location Based Services (LBSs) 





























i s
tin trin ca dch v ng công cng.
H tha lý (Geographical information system) là mt h thng , phân tích, qun
lý và trình bày d liu liên quan ti v a lý. Theo cách hiu hin nay, GIS còn bao
gm các công c truy vn thông tin, phân tích và kt hp các thông tin ri rc, b c
ng dng trong khá nhiu ngànng sn, y t, an ninh quc phòng hay quy ho.
t quan trng trong các LBS, vì nu thi d liu thông tin v các v trí do GIS
cung cp, LBS không th  thông tin v c
2.1.3 





a LBS (Location-Based Services Infrastructure)








, 






c nhà cung c  c cho dch v ca mình. Trong thc t, h thng
nh v toàn cu GPS là la chn s mng các h thng LBS. Vì
nhin tích ph sóng bao ph toàn b b m chính xác cao, cho
phép s dng tín hiu min phí mà hin tt hing tích hp chnh v
bng GPS vào các thit b c bin tho
 Service and application Provider: Nhà cung cp ng dng và dch v nhn yêu cu t khách
nh v trí ca h thông qua d linh v c gi kèm yêu c 
cung cp s tr giúp hong vi v trí và yêu cu ca khách hàng. Các ng
dng và dch v c nhà cung cp trinh v dng, tra ca
lý, cu h cu nn, qu

Hình 1. (component) .
2.1.4 

(Types of Location-Based Services)
 , 























 , 






















































14









 . 




















?
H thn (Recommeder System - RS) , 





























(



,  ),


 (, 



, ), quá trình 

(ratings, tags,
 





















 (item). 



















 . 
 



/



.
 ,   [Burke,
2007]: 





 (collaborative-based), 



 (content-based), 




(knowledge-based), (hybrid).
2.2.2.1 Collaborative-based Recommender Systems
Các hệ thống tư vấn cộng tác s tính toán mối g quan gia nhi s d

 . 

















 Amazon.com
(people who buy x also buy y).

Hình 3. 







.
 (Collaborative filtering) 



  




a hai ma trn nh ren, 2008]. , 


























.




 i s dng hin ti, 

 












 





 












 (Information retrieval) [Manning, 2008]
  (text)  (



 ) 




























 , 








, 





(cold start problem).
2.2.2.3 Knowledge-based Recommender Systems























 n da trên
ng hp (case-based reasoning  CBR) [Bridge et al., 2006], 






















.




: 
























.
Mobile Location-Based Recommender System

18 Hình 6. 





lai.
2.2.3 














. :
  phim, .
 

  

, , trang web, 











.
 






























, 




Vi s phát trin ca các thit b ng có tích hp GPS, hin ti có rt nhiu ng dng có th to ra
 a lí (location-based ratings), t v
trí ci dùng (user) hoc sn phm (item). Ví d, các mng xã hi dm (Foursquare
và Face-k-i mt v 
 t hp thông tin v trí ca c i s dng
và sn phm.
y s i ca các h thn da trên v trí (Location Based Recommender
System)nh  c(spatial aspect of ratings) s c khai thác
 n theo v trí (location-aware recommendations). Mt ví d cho loi hình này là
 trong mng xã hi Foursquare. Các h thng này hong ch yu trên môi
ng, 





















3.2 
3.2.1 Gii thiu chung
Foursquare là mng xã hi da trên v trí (location-based social
network) có tích hp các yu t ca trò i vào tháng 3/2009.
ng dng s dng chnh v v tinh (GPS), chy trên nn các
smartphone.
i dùng thc hi-m khác nhau mà h n,
ghi chú, nhn xét v nh vi bn bè và nhn phn
ng, gim giá ca các doanh nghip dành cho các thành viên ca
  - nhiu nht ti m  m nht nh s c   min "Th
ng" t  n khi b  t qua. i nhn s nhc
chc bit ca các doanh nghip tng.
S hp dn vn có ca các mng xã hi cng vng và yu t 
thành mt trong nhng mng xã hng ln nht (sau Instagram) vi s n
triu và hàng tri-i ngày. [Fousquare, 2012]
3.2.2 
Explore, i cùng vi phiên bn Foursquare 3.0 vào cui s dng khám phá
nhanh chóng nhm thú v trên hành trình
tip theo ca mình.
i dùng s la chn lo  m h 
mun, chng h
ng dng s  xum tt nht
theo mt vài tiêu chí (Hình 5). Kt qu tr v là mt
     c xp hng vi các
thi tng
n xét ca h
Hình 7. a FourSquare.
V t Recommender Engine,  n
c rút trích t hong ci dùng, bn bè ca h, v a lí da trên GPS, và nhng

 thm này có tc gii quyt các thut
toán này là mt thách thc li nhng nghiên cu nhnh  c ng
kê ph bin và bí truyn.
Mt s ng ln cám khác nhau cn phc khng thi, phi cân bng các thông
tin gây nhiu.
n thng khác khi s dng lc cp v khi
u lh ng mt thu gii quyt v này.
Mobile Location-Based Recommender System

22

Mt v c quan tâm là vic gii thích kt qu i s dng. “Tại sao” h nên
 c gii quy coi trng và khuyn khích
các mi liên kt xã h (loyalty) ci s dng.
H thng s i dùng bit nhn bè ca h n ma
m h t l-a h ti m
Nhng thông tin này không ch n kt qu xp hng mà còn b sung kinh nghim, gi lên
mt cuc trò chuyn vi bn bè, hoc gi nh i dùng ti mm mà h 
trong mt khong thi gian. [ Moore, 2011]
3.2.3.2 
Sự chậm trễ lớn nhất đến từ việc truy vấn cơ s dữ liệu, bao gồm:
Truy vn d li xp hng
o Yêu cu: ly tp hnh (tuy
nhiên b li mt s vì lí do hiu sut). Cn có mt cách truy v ly
c top N giá tr t s 
o Gii pháp: Hu ht các CSDL hin tc yêu cu này vi quy mô d
liu cu tiên ph mc (indexing) v ma lí,
  p nht các ch m a lý này. Mongo (open source document-
oriented NoSQL database system) c la chn. MongoDB có th thc hin truy vn
trên vi thi gian 30ms cho mt bán kính 10 dm  thành ph New

Foursquare và Movilens. [Levandoski et al. 2012]
3.3.1.1 Mô 
Trong các RS truyn thng không quan tâm ti v c biu din bi b ba
c chia làm ba loi:
 “spatial ratings for non-spatial items”, biu din bi b bn (user, ulocation, rating, item),
ulocation” là v trí ci dùng.
 “nonspatial ratings for spatial items” , biu din bi b bn (user, rating, item, ilocation)
 “spatial ratings for spatial items”, biu din bi b   cation, rating, item,
ilocation)
Mobile Location-Based Recommender System

24

3.3.1.2 

Hình 8.  trí [Levandoski et al. 2012]
Hai tính chc bic rút ra khi kho sát tp d liu ca Foursquare và
Movilens [Levandoski et al. 2012] là:
 Preference locality (tm d thích cc bt này ch ra ri dùng trong
mt khu va lí s có s thích (phim, hom) rt khác vi nhi  khu vc
khác, thm chí là nhng khu vc lân cn cho mi dùng u phi
khai thác da trên các rating r gn v ma lí vi u nht.
 Travel locality ( tm dn cc bn mang yu t không
ng la chm nm trong mt khong cách gii
hn nhnh (limited distance). Trong bng phân tích d liu ci ta nhn
thy ri dùng di chuyn trong 10 dm hoi ch di
chuyn trong vòng bán kính 50 dm. Quan sát này ch ra rng  các khong cách
ga chn.
3.3.2 SPATIAL RATINGS FOR NON-SPATIAL ITEMS
 n cho loi hình - (vi b bn (user,

ulocation, rating, item, ilocation), LARS s dng c t  và 
 khai thác c v trí cng tích hc
tính ni bt ca LARS, c t có th c s dng riêng r, hoc kt hp tùy vào lo
theo v trí (location-based ratings) mà h thng h tr. [Levandoski et al. 2012]
3.4 
Cùng mp cn gii quyt v khá khác nhau.
V vic khai thác v  t qu vn, Foursquare, vi nhng yêu cu ca mt ng
dng thc t gt nh thc hin vic xp hn trong phm vi
c th ca ng dng. Trái li, các tác gi c
giá theo v   xut khai thác mt
cách hiu qu thông tin v v n.
V v t truy vn trên d lic Foursquare gii quyt bng nh
mc l xut ra mt truy vn hiu qu da trên Tng v
