B GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HC BÁCH KHOA HÀ NI
---------------------------------------
Võ Trng Trung
NÂNG CAO CHẤT LƢỢNG QUNG CÁO TRC TUYN
S DỤNG PHƢƠNG PHÁP HỌC MÁY
Chuyên ngành : Công ngh thông tin
LUẬN VĂN THẠC SĨ KỸ THUT
…......................................
NGƢỜI HƢỚNG DN KHOA HC
TS. CAO TUẤN DŨNG
Hà Ni - 2015
LI CẢM ƠN
Trƣc tiên, tôi xin gi li cảm ơn lòng biết ơn sâu sắc nht ti Tiến
Cao Tuấn Dũng, ngƣời đã tn tình ch bảo hƣớng dn tôi trong sut quá trình thc
hin luận văn.
Tôi chân thành cảm ơn các thầy, đã tạo cho tôi những điều kin thun lợi để
hc tp và nghiên cu ti trƣờng Đại hc Bách khoa Hà Ni.
Tôi cũng xin gi li cảm ơn tới ng ty amobi đã thu thập, xvà cung cp d
liu giúp cho tôi có th nghiên cu, th nghim, áp dng vào lun văn.
Tôi xin chân thành cảm ơn!
MC LC
DANH MC BNG BIU ......................................................................................................... i
DANH MC HÌNH V ............................................................................................................. ii
DANH MC CÁC T VIT TT ........................................................................................... iii
M ĐẦU ................................................................................................................................... iv
Chƣơng I TNG QUAN V QUNG CÁO TRC TUYN ............................................. 1
1.1. Qung cáo trc tuyến là gì ............................................................................................... 1
1.2. Những ƣu điểm ca qung cáo trc tuyến ....................................................................... 1
1.3. Cách tính phí qung cáo ................................................................................................... 2
1.4. Tìm hiu qung cáo trên ng dụng di động ..................................................................... 3
1.5. Vấn đề quảng cáo trúng đích ........................................................................................... 6
Chƣơng II MT S PHƢƠNG PHÁP HỌC MÁY ............................................................... 7
2.1. Gii thiu v hc máy và h khuyến ngh ....................................................................... 7
2.1.1 Khái nim hc máy .................................................................................................... 7
2.1.1. H thng khuyến ngh ............................................................................................. 10
2.2. Mt s phƣơng pháp khuyến ngh ................................................................................. 13
2.2.1. Lc cng tác da vào b nh .................................................................................. 13
2.2.2. Phƣơng pháp phân rã ma trận (Matrix-factorization) ............................................. 22
2.2.3. Phƣơng pháp đồng phân cm ................................................................................. 28
Chƣơng III ÁP DỤNG CÁC PHƢƠNG PHÁP KHUYẾN NGH VÀO BÀI TOÁN
QUNG CÁO TRC TUYN ................................................................................................ 35
3.1. Bài toán quảng cáo trên di động .................................................................................... 35
3.2. Phƣơng pháp đánh giá ................................................................................................... 37
3.3. Th nghim .................................................................................................................... 37
3.3.1. Tin x lý d liu .................................................................................................... 38
3.3.2. Không s dụng phƣơng pháp học máy ................................................................... 41
3.3.3. Phƣơng pháp lọc cng tác da vào ng dng: ........................................................ 42
3.3.4. Phƣơng pháp lọc cng tác da vào qung cáo: ....................................................... 44
3.3.5. Phƣơng pháp phân rã ma trận ................................................................................. 46
3.3.6. Phƣơng pháp đồng phân cm ................................................................................. 50
3.4. Kết qu đạt đƣợc và đề xut .......................................................................................... 54
Chƣơng IV H THNG KHUYN NGH QUNG CÁO .................................................. 59
4.1. Cơ sở d liu .................................................................................................................. 59
4.2. H thng theo dõi khuyến ngh ...................................................................................... 61
KT LUN ............................................................................................................................... 67
i
DANH MC BNG BIU
Bng 2.1: Ví d v lc cng tác ................................................................................................ 14
Bng 2.2: Độ phc tp thut toán ............................................................................................. 33
Bng 3.1: Mô t d liu view.................................................................................................... 39
Bng 3.2: Mô t d liu click.................................................................................................... 39
Bng 3.3: Mô t kết qu hc lc cng tác theo ng dng ......................................................... 43
Bng 3.4: Mô t kết qu hc lc cng tác theo qung cáo ....................................................... 45
Bng 3.5: Mô t ma trn tim n ng dng .............................................................................. 48
Bng 3.6: Mô t ma trn tim n qung cáo ............................................................................. 49
Bng 3.7: Mô t cm ng dng ................................................................................................ 51
Bng 3.8: Mô t cm qung cáo ............................................................................................... 52
Bng 3.9: Mô t t l click/view trung bình ng dng ............................................................. 52
Bng 3.10: Mô t t l click/view trung bình qung cáo .......................................................... 53
Bng 3.11: Mô t t l click/view trung bình cm ng dng .................................................. 53
Bng 3.12: Mô t t l click/view trung bình cm qung cáo .................................................. 53
Bng 3.13: Mô t t l click/view trung bình đồng phân cm .................................................. 54
Bng 3.14: Kết qu kim th .................................................................................................... 55
ii
DANH MC HÌNH V
Hình 2.1: Ví d v xếp hng trang web ...................................................................................... 8
Hình 2.2: Ví d lc cng tác ....................................................................................................... 9
Hình 2.3: Ví d nhn dng khuôn mt ........................................................................................ 9
Hình 2.4: Quá trình x lý ca lc cng tác ............................................................................... 14
Hình 2.5: S khác nhau gia lc cộng tác theo ngƣời dùng và theo item ................................ 18
Hình 2.6: Tính khong cách theo item ...................................................................................... 19
Hình 2.7: Ví d phân rã ma trn ............................................................................................... 23
Hình 3.1: Ảnh hƣớng ca k ti RMSE ca lc cng tác theo ng dng .................................. 42
Hình 3.2: Ảnh hƣớng ca k ti RMSE ca lc cng tác theo qung cáo ................................. 44
Hình 3.3: Ảnh hƣớng ca f ti RMSE ca phân rã ma trn ..................................................... 46
Hình 3.4: Ảnh hƣớng của λ tới RMSE ca phân rã ma trn ..................................................... 47
Hình 3.5: Ảnh hƣớng ca k ti RMSE của đồng phân cm ..................................................... 50
Hình 3.6: Ảnh hƣớng ca l ti RMSE của đồng phân cm ...................................................... 51
Hình 3.7: Biểu đồ so sánh thi gian hc của các phƣơng pháp ................................................ 55
Hình 3.8: Biểu đồ so sánh thi gian d đoán của các phƣơng pháp ......................................... 56
Hình 3.9: Biểu đồ so sánh tài nguyên của các phƣơng pháp .................................................... 56
Hình 3.10: Biểu đồ so sánh sai s RMSE và MAE của các phƣơng pháp ............................... 57
Hình 4.1: Mô t cơ sở d liu ca h khuyến ngh ................................................................... 60
Hình 4.2: Chức năng top ứng dng ........................................................................................... 61
Hình 4.3: Chức năng khuyến ngh qung cáo cho ng dng .................................................... 62
Hình 4.4: Chức năng so sánh tỷ l click/view ca ng dng và qung cáo gia d đoán và thực
tế ................................................................................................................................................ 63
Hình 4.5: Chức năng top quảng cáo.......................................................................................... 64
Hình 4.6: Chức năng khuyến ngh ng dng ............................................................................ 65
Hình 4.7: Chức năng so sánh tỷ l click/view ca qung cáo và ng dng gia d đoán và thực
tế ................................................................................................................................................ 66
iii
DANH MC CÁC T VIT TT
Cơ Sở D Liu
Click-through Rate T l click
Matrix Factorization phân rã ma trn
Cost Per Click Giá theo lƣợt click
Cost Per Impression Giá theo lƣợt ghé thăm
Cost per Duration Giá theo thi gian
Cost Per Action Giá theo hành động
Cost Per Install Giá theo cài đặt
Stochastic Gradient Descent - Phƣơng pháp xuống đôì ngẫu nhiên
Root Mean Square Error Sai s bình phƣơng trung bình
Mean Absolute Error Sai s tuyệt đối trung bình
Column cluster Cm ct
Row cluster Cm hàng
Co-Cluster Đồng phân cm
iv
M ĐẦU
Hin nay vi s bùng n ca công ngh thông tin, lƣợng d liu lƣu thông trên
internet ngày một đồ s, s ngƣời dùng thƣng xuyên trc tuyến ngày càng gia tăng,
cùng với đó sự chuyển hƣớng marketing t các phƣơng pháp truyền thng sang
mng toàn cu internet. Mt trong nhng cách qung sn phm ca các doanh
nghip qung cáo trc tuyến thông qua mng internet. Qung o trên mng khác
hn quảng o trên các phƣơng tiện thông tin đại chúng khác, giúp ngƣời tiêu dùng
th tƣơng tác vi qung cáo. Vy vic khai thác các tƣơng tác y đ giúp h thng
thông minh hơn, quảng cáo trúng đích đến ngƣời tiêu dùng mt ci tiến giúp c
doanh nghip tiếp cận ngƣời dùng d dàng hơn. Các doanh nghiệp thƣờng thông qua
các kênh qung cáo trung gian, chi phí hiu qu thông thƣờng đƣc quy đổi
thành t l click/view. Để qung cáo trc tuyến hiu qu hơn tđồng nghĩa vi vic
tăng tỷ l này. Để làm đƣợc điều y cn áp dụng các phƣơng pháp học máy để giúp
các h thng qung cáo quảng cáo thông minh hơn, mang lại hiu qu cao hơn.
Do đó, luận văn "Nâng cao chất lƣợng qung cáo trc tuyến s dng
phƣơng pháp học máy" sau đây tìm hiểu v tng quan v hc y, một vài phƣơng
pháp hc y, thc trng qung cáo trc tuyến th nghim các phƣơng pháp học
máy vào qung cáo trc tuyến, t đó đề xut áp dng hc y vào h thng qung cáo
trc tuyến đểng cao cht lƣng qung cáo. V b cc luận văn chia làm 3 chƣơng:
Chƣơng I: Trình bày v tng quan v qung cáo trc tuyến, các ƣu đim so vi
qung cáo truyn thống, và đặt vấn đề vi toán quảng cáo trên di động
Chƣơng II: Trình y tng quan v hc máy, mt s phƣơng pháp khuyến ngh
lc cng tác da vào b nhớ, phƣơng pháp phân ma trận phƣơng pháp đồng phân
cm
Chƣơng III: Nêu bài toán qung cáo trc truyến công ty amobi và áp dng các
phƣơng pháp trình y chƣơng II vào bài toán quảng cáo, đƣa ra kết luận, đề xut áp
dng vào vic nâng cao chất lƣợng qung o bằng cách ƣu tiên c quảng cáo d
đoán tỷ l click/view ln s đƣợc ƣu tiên hin th lên ng dng.
Chƣơng IV: Xây dng h thng khuyến ngh, theo dõi tƣơng quan ca vic áp
dng h khuyến ngh trong vic d đoán t l click/view và thc tế.
1
Chƣơng I
TNG QUAN V QUNG CÁO TRC TUYN
1.1. Qung cáo trc tuyến là gì
Tƣơng tự các loi hình qung cáo báo giy, truyn hình, áp phích,... qung cáo
trc tuyến cũng nhằm mục đích cung cấp thông tin, giúp ngƣời dùng tiếp cn sn phm
thúc đẩy vic mua bán giữa ngƣời dùng doanh nghiệp. Nhƣng quảng cáo trc
tuyến khác hn quảng cáo trên các phƣơng tiện thông tin đại chúng khác, giúp
ngƣời tiêu dùng th tƣơng tác vi qung cáo. Khách hàng th nhn vào qung
cáo để ly thông tin, cung cấp đánh giá, hoc mua sn phm cùng mu trên qung
cáo đó.
Qung cáo trc tuyến đã tạo hội cho các nhà qung cáo nhm chính xác vào
khách hàng ca mình, giúp h tiến hành quảng cáo theo đúng với s thích th
hiếu của ngƣời tiêu ng. Các phƣơng tiện thông tin đại chúng khác cũng khả năng
nhm chn, nhƣng chỉ có mng Internet mi có kh năng nhắm chn chính xác nht.
Khái nim nhà qung cáo đây đƣợc hiu ngƣời chuyên môn, chu trách
nhim cho một thƣơng hiu hay sn phm trong vic thiết lp giám sát mt chiến
dch qung cáo.
1.2. Những ƣu đim ca qung cáo trc tuyến
Kh năng nhắm chn
Qung cáo trc tuyến rt nhiu kh năng nhm chn vào doanh nghip,
ngƣời dùng không b gii hn v địa lý, quốc gia, lĩnh vực hot động. H cũng
2
th da vào s thích cá nhân hành vi của ngƣời tiêu dùng để nhắm vào đối tƣợng
thích hp.
Kh năng theo dõi
Nhng nhà qung cáo th theo dõi hành vi của ngƣời dùng đi vi các sn
phm mà h qung cáo, tìm hiu các khách hàng tim năng. Thông qua tƣơng tác click,
xem, mua,... t các qung cáo, thì các nhà qung cáo d dàng xác định hiu qu ca
mt qung cáo không cn tn nhiu công sc, việc đối vi các loi qung cáo
có truyn thng khó thc hin.
Tính linh hot và kh năng phân phối
Qung cáo trc tuyến th đƣợc trin khai vào bt c thi gian nào bt c
khong thi gian nào nhà quảng cáo cũng thể cp nht hoc hy b chiến dch
qung cáo vào bt c lúc nào. Qua quá trình theo dõi hiu qu quảng cáo vào ng
khong thi gian bt k, nhà qung cáo th phân phi qung cáo ra các kênh khác
nhau, cp nht các thông tin liên quan hoc hy b chiến dch mt cách d dàng, điều
mà khó có th thay đổi các loi hình qung cáo truyn thng.
Tính tƣơng tác
Kh năng tƣơng tác gia quảng cáo và ngƣời dùng trong qung cáo trc tuyến
cc k cao. Ngƣời dùng có th dùng mt cú click chuột để xem thông tin chi tiết v sn
phm, mua luôn sn phm mà h đang xem thông qua các liên kết điều hƣớng.
1.3. Cách tính phí qung cáo
Theo thi gian: CPD (Cost per Duration), Chi phí đƣc tính thông qua thi
gian đăng quảng cáo.
3
Theo lƣợt xem: CPM (Cost per Impression), Chi phí đƣợc tính dựa trên t
xem của ngƣời dùng, nói cách khác lƣợt tiếp cn của ngƣời ng đến qung cáo,
thông thƣờng đƣợc tính da vào block mỗi 1000 lƣt xem
Theo lƣợt click: CPC (Cost per Click) hay PPC (Pay per Click), Cách tính này
da vào các click của ngƣời dùng lên quảng cáo, nghĩa dựa vào khách hàng tim
năng, họ quan tâm đến sn phm.
Theo giá tr: CPA (Cost Per Action hoc Cost Per Acquisition) hay PPP
(Pay Per Performance), hình thc y da vào s chuyển đi hiu qu qung cáo thành
khách hàng, khách ng th đăng tài khoảng vào h thng ca doanh nghip
hay là hoàn thành mua đơn hàng từ qung cáo
Theo lƣợt cài đt: CPI (Cost Per Install), hình thc doanh nghip s
hu ng dng tr tin cho nhà qung cáo ng dụng đó thông qua s ợt ngƣời dùng
cài ng dng t quảng cáo, thƣờng đƣợc áp dng cho các ng dụng trên điện thoi di
động.
1.4. Tìm hiu qung cáo trên ng dụng di động
Qung cáo mobile (theo http://ingaads.com/) (tên tiếng anh: Mobile Ads) là hình
thc nhm chn qung cáo ti những ngƣời s dụng điện thoại di động kết ni
internet. Cũng giống nhƣ quảng cáo nhm tới ngƣời s dng máy vi tính, qung cáo
mobile th dƣới dạng text, banner hay video. Điu khác bit nhng mu qung
cáo này s kích thƣớc nh hơn cho phù hợp vi rt nhiu cu hình màn hình mobile
khác nhau, quảng cáo đƣợc hin th trên các website, ng dng (application) dành
cho mobile, game cho ngƣời dùng mobile ch không phi cho ngƣi dùng máy vi tính.
4
Ti sao qung cáo mobile?
Theo s liu ca Trung m internet Vit Nam, tính tới tháng 7 năm 2012 Việt
Nam đã tới 31 triệu ngƣi dùng internet, chiếm hơn 35% dân số c nƣớc. Trong đó,
s truy cp internet qua mobile chiếm ti 38% tng các truy cp internet t l này
không ngừng tăng lên nhanh chóng do điện thoi thông minh ngày càng ph biến.
Do kích thƣc màn hình nh nhu cu s dng mobile không giống nhƣ sử
dng máy vi tính, hàng lot các website thông tin, game, các ng dng hu ích đƣợc
thiết kế dành riêng cho ngƣời dùng mobile. Qung cáo nhm đến đối tƣợng ngƣi s
dng mobile vì thế cũng cần đƣợc điều chnh v kích thƣớc, cách thc xut hiện và nơi
đặt cho phù hp.
Ngƣời dùng mobile cũng thói quen truy xut thông tin liên quan vic mua
sm khác với ngƣời dùng máy tính, do vậy các marketer thƣờng tách riêng các chiến
dch qung cáo nhm chọn riêng nhóm đối tƣợng khách hàng s dng mobile internet
để có th đo lƣờng và đánh giá hiệu qu c th.
Quảng cáo trên di động d kích thích ngƣời tiêu dùng thc hiện hành động mc
tiêu nhƣ mua hàng, đăng tài khoản, download phn mm ng dụng,… Ngay khi
chng kiến banner hin th ti wapsite, mng hội,… khách hàng thể d dàng tra
t khóa tìm hiu sn phẩm, tìm ra địa ch gn nht bán sn phẩm đó, gọi điện đặt hàng,
lƣu sự kin chƣơng trình khuyến mãi vào lch nhc nh hay ti cài đặt game và ng
dng ngay tc thì,…
Li ích ca qung cáo trên di động: D dàng giúp khách hàng tƣơng tác ngay
vi doanh nghip:
- Gi điện đặt hàng, tìm hiu thông tin
- Lƣu số điện thoi vào danh b
5
- Lƣu website vào bookmark
- Tìm đƣợc đa ch gn nht
- Lƣu sự kiện, chƣơng trình khuyến mi vào lch nhc nhở…
- Click > tải > cài đặt > s dng các ng dụng, game… ngay tức thì
S dĩ qung cáo mobile ngày càng phát trin bi nhng nguyên nhân:
- ợng ngƣời s dụng smartphone ngày càng đông. Số ngƣời truy cp internet
trên mobile cũng tăng chóng mặt.
- Qung cáo trên mobile s không ph thuc vào không gian và thi gian
- Tăng mức đ nhn biết v nhãn hiệu/ thƣơng hiệu ca bn
- Định hƣớng s chú ý ca khách hàng vào qung cáo
- Đo lƣng hiu qu qung cáo chính xác và nhanh chóng.
- Chi phí thp
- Kh năng nhắm chọn đối tƣng mc tiêu d dàng:
+ Nhm chn theo vùng min
+ Nhm chn theo h điu hành
+ Nhm chn theo hãng sn xut
+ Nhm chn theo nhà mng
6
Qung cáo trong Game/ ng dng
Đây là hình thc qung cáo da trên các mng quảng cáo di đng, cho phép các
nhà phát trin phn mm hay công ty qung cáo th qung cáo sn phm ca mình
trc tiếp trên ng dng ca các sn phm vi các h điều hành khác nhau.
1.5. Vấn đề quảng cáo trúng đích
a) Thc trng quảng cáo trên di động hin nay Vit Nam:
- S thiếu tin tƣởng ca các doanh nghip: Mặc chi phí ít hơn nhƣng khi làm
qung cáo, không nhiu doanh nghip ti Vit Nam chn qung cáo trc tuyến. l
h không thc s tin tƣởng vào chất lƣợng ca quảng cáo đó cũng nhƣ hiu qu
mang li cho doanh nghip. Quảng cáo trên di đng còn khá mi m thƣng
không đánh trúng nhu cầu ca khách hàng.
- D ng qung cáo: Những banner dày đặc trên các website, ng dng làm
phiền ngƣời s dng do h không có nhu cu v sn phm đƣc qung cáo.
b) Gii pháp qung cáo trúng đích
Phát trin chuyên sâu qung cáo trc tuyến trên di động. Hin ti rt ít các công
ty phát trin chuyên sâu v qung cáo di đng trc tuyến Vit Nam, dẫn đến th
trƣng quảng cáo trên di động ch yếu ph thuộc vào công ty nƣớc ngoài nhƣ google,
yahoo... Để quảng cáo trên di động thu hút đƣợc s tin ng ca các doanh nghip thì
t l click/view qung cáo phải đạt t l cao, tức ngƣời dùng thy hng thú vi các
qung cáo h bt gặp đúng thứ h cần, cũng nhƣ doanh nghiệp tiếp cận đúng
khách hàng để h click để xem chi tiết sn phẩm đƣợc qung cáo.
Để thc hiện điều đó thì ứng dng hc máy để phân tích hành vi ngƣời dùng,
đƣa ra quảng cáo hp lý gii thiu tới ngƣời dùng là hết sc cn thiết.
7
Chƣơng II
MT S PHƢƠNG PHÁP HC MÁY
2.1. Gii thiu v hc máy và h khuyến ngh
2.1.1 Khái nim hc máy
Con ngƣời nhiu cách hc khác nhau nhƣ học c, hc các s kin nh
thông qua s quan sát và khám phá, hc ci thin k ng thông qua thực tin, hc nh
s phát trin ca h thn kinh sinh hc của con ngƣi nh gen di truyn t thế h
này sang thế h khác,... cách hc có thế nào đi chăng nữa thì mc tiêu ca vic hc
thu thp thông tin mi x tri thc mi sao cho thích nghi vi tình hung mi.
Ging vi cách hc của con ngƣời, ngƣời ta mun y dựng các chƣơng trình y tính
sao cho máy có kh năng thu thập tri thc mi x tri thc mi sao cho thích nghi
vi tình hung mi, t động x mà không hoc ít s can thip của con ngƣi
để đƣa ra các quyết đnh, kết qu hp lý.
Hc máy hay máy hc một lĩnh vực trong ttu nhân to nghiên cu xây
dng các chương trình máy tính nhm tối ưu một tiêu chí x nh toán nào đó bng
cách s dng d liu hay kinh nghiệm đã [5,31] .Chúng ta cn đến phƣơng pháp
hc khi mà chúng ta không th viết chƣơng trình tính toán trc tiếp theo mt công thc
hay mt x lý tun t nào đó để gii quyết vấn đề, mà cn ti d liu hoc kinh nghim
đã đƣợc hc b sung thêm trong quá trình hoạt động. Vic hc cn thc hin khi
không cn s hin din của con ngƣời hoặc chính con ngƣời nhiều khi cũng không
th giải thích đƣợc sao có nhng quyết đnh, vấn đề do chính con ngƣời đƣa ra.
Chúng ta cn thiết mt h thng th thích ng vi nhng hoàn cnh
khác nhau hơn viết các chƣơng trình khác nhau cho từng trƣờng hp riêng bit. Hay
nói cách khác học máylĩnh vực nghiên cu v kh năng học ca máy tính không
cn phi lập trình tưng minh ngay t đầu [13,3] - Arthur Samuel (1959).