Đề tài Quảng cáo trực tuyến hướng câu truy vấn với sự giúp đỡ của phân tích chủ đề và kỹ thuật tính hạng

Sn d KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Hữu Phương QUẢNG CÁO TRỰC TUYẾN HƯỚNG CÂU TRUY VẤN VỚI SỰ GIÚP ĐỠ CỦA PHÂN TÍCH CHỦ ĐỀ VÀ KỸ THUẬT TÍNH HẠNG ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Hữu Phương QUẢNG CÁO TRỰC TUYẾN HƯỚNG CÂU TRUY VẤN VỚI SỰ GIÚP ĐỠ CỦA PHÂN TÍCH CHỦ ĐỀ VÀ KỸ THUẬT TÍNH HẠNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: PGS. TS. Hà Quang Thụy Cán bộ đồng hướng dẫn: CN. Nguyễn Minh Tuấn HÀ NỘI - 2009 Lời cảm ơn Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo sư Tiến sĩ Hà Quang Thụy và Cử nhân Nguyễn Minh Tuấn, người đã tận tình chỉ bảo và hướng dẫn tôi trong suốt quá trình thực hiện khoá luận tốt nghiệp. Tôi chân thành cảm ơn các thầy, cô đã tạo cho tôi những điều kiện thuận lợi để học tập và nghiên cứu tại trường Đại Học Công Nghệ. Tôi cũng xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong nhóm “Khai phá dữ liệu” đã giúp đỡ và hỗ trợ tôi rất nhiều về kiến thức chuyên môn và trong việc thu thập dữ liệu. Cuối cùng, tôi muốn gửi lời cảm vô hạn tới gia đình và bạn bè, những người thân yêu luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp. Tôi xin chân thành cảm ơn ! Sinh viên Nguyễn Hữu Phương Tóm tắt Quảng cáo trên máy tìm kiếm hiện đang là hình thức quảng cáo thu hút được nhiều sự chú ý nhất ngày nay, trong đó các quảng cáo được hiển thị bên cạnh kết quả tìm kiếm theo truy vấn của người dùng. Điều này dẫn đến một bài toán là làm thế nào để hiển thị những quảng cáo phù hợp nhất với truy vấn. Khóa luận này tập trung nghiên cứu các phương pháp xếp hạng quảng cáo trên máy tìm kiếm theo độ phù hợp với truy vấn, đề xuất mô hình quảng cáo sử dụng phân tích chủ đề ẩn và kĩ thuật tính hạng. Đồng thời đưa ra phương pháp biểu diễn các quảng cáo theo những đặc trưng mới, đặc trưng về chủ đề ẩn. Tiến hành thực nghiệm dựa trên việc sử dụng query logs trong xây dựng tập dữ liệu học, mô hình đã khai thác được các thông tin hữu ích từ hành vi người dùng và đem lại kết quả khá khả quan. Độ chính xác trung bình của kết quả xếp hạng vào khoảng 82%-84%. Mục lục Lời mở đầu....................................................................................................................................... 1 Chương 1. Khái quát về quảng cáo trực tuyến ................................................................................ 3 1.1. Giới thiệu về quảng cáo .................................................................................................... 3 1.2. Quảng cáo trực tuyến ........................................................................................................ 4 1.2.1. Tốc độ tăng trưởng và thị phần .................................................................................. 4 1.2.2. Các hình thức quảng cáo trực tuyến .......................................................................... 5 1.3. Quảng cáo trực tuyến ở Việt Nam .................................................................................... 6 1.3.1. Tổng quan về quảng cáo trực tuyến ở Việt Nam ....................................................... 7 1.3.2. Những tài nguyên chưa được khai thác và thị trường quảng cáo trực tuyến ........... 10 1.4. Quảng cáo thông qua tìm kiếm ....................................................................................... 13 Chương 2. Các phương pháp quảng cáo thông qua tìm kiếm ....................................................... 16 2.1. Mô hình trích xuất từ khóa trong nội dung trang web .................................................... 16 2.2. Mô hình so khớp với tập từ vựng mở rộng (impedance coupling) ................................. 17 2.3. Mô hình tối ưu xếp hạng với thuật toán di truyền (Genetic Programming) ................... 18 2.4. Mô hình quảng cáo sử dụng phản hồi liên quan ............................................................. 19 2.5. Mô hình ước lượng CTR (Click Through Rate) ............................................................. 21 2.6. Mô hình tìm kiếm và xếp hạng sử dụng chủ đề ẩn trong quảng cáo theo ngữ cảnh ....... 22 Chương 3. Hệ thống quảng cáo trực tuyến sử dụng xếp hạng và chủ đề ẩn ................................. 25 3.1 Xếp hạng ......................................................................................................................... 25 3.1.1 Xếp hạng trong máy tìm kiếm ................................................................................. 25 3.1.2 Học xếp hạng và SVM Rank ................................................................................... 26 3.1.3 Các phương pháp đánh giá xếp hạng ....................................................................... 30 3.2 Chủ đề ẩn ........................................................................................................................ 33 3.2.1 Latent Dirichlet Allocation (LDA) .......................................................................... 34 3.2.2 Mô hình sinh trong LDA ......................................................................................... 35 3.2.3 Ước lượng tham số và suy luận ............................................................................... 36 3.3 Mô hình quảng cáo trực tuyến hướng câu truy vấn với sự giúp đỡ của phân tích chủ đề và kỹ thuật tính hạng ................................................................................................................. 39 3.3.1 Mô tả bài toán .......................................................................................................... 39 3.3.2 Mô hình tổng quan ................................................................................................... 40 3.3.3 Xác định đặc trưng cho mô hình ............................................................................. 41 Chương 4. Thực nghiệm và đánh giá ............................................................................................ 43 4.1. Dữ liệu ............................................................................................................................ 43 4.2. Môi trường thực nghiệm ................................................................................................. 43 4.2.1 Cấu hình phần cứng ..................................................................................................... 43 4.2.2 Các công cụ được sử dụng ........................................................................................... 44 4.3. Quá trình thực nghiệm .................................................................................................... 45 4.3.1. Tiền xử lý dữ liệu ........................................................................................................ 45 4.3.2. Thu thập thông tin từ các URL có được ...................................................................... 46 4.3.3. Véc tơ hóa dữ liệu ........................................................................................................ 47 4.3.4. Thiết kế thực nghiệm ................................................................................................... 47 4.4. Kết quả thực nghiệm ....................................................................................................... 48 4.5. Đánh giá kết quả thực nghiệm ........................................................................................ 50 Kết luận .......................................................................................................................................... 52 Tài liệu tham khảo ......................................................................................................................... 53 Danh sách các bảng Bảng 1. Một số website lớn cung cấp dịch vụ quảng cáo trực tuyến ở Việt Nam .......................... 9 Bảng 2 Cấu hình phần cứng sử dụng trong thực nghiệm .............................................................. 44 Bảng 3. Danh sách các phần mềm mã nguồn mở được sử dụng ................................................... 44 Bảng 4. Giá trị các độ đo tại một số truy vấn khác nhau. .............................................................. 50 Danh sách các hình Hình 1. Doanh thu quảng cáo trực tuyến nửa đầu và cuối những năm từ 1999 đến 2008 ở Mĩ ..... 5 Hình 2. Phân loại doanh thu quảng cáo trực tuyến trong 6 tháng đầu năm 2007 và 2008 ở Mĩ ..... 6 Hình 3. Quảng cáo trực tuyến tại một trang báo điện tử Việt Nam ................................................. 8 Hình 4. Doanh thu từ quảng cáo trực tuyến của VnExpress và VietnamNet trong 3 năm 2004, 2005, 2006. .................................................................................................................................... 12 Hình 5. Mô tả nội dung một quảng cáo ......................................................................................... 14 Hình 6. Kiến trúc cơ bản của hệ thống quảng cáo thông qua tìm kiếm ......................................... 14 Hình 7. Kiến trúc hệ thống quảng cáo sử dụng phản hồi liên quan ............................................... 20 Hình 8. Thuật toán ước lượng tham biến τ .................................................................................... 30 Hình 9. Mô hình biểu diễn của LDA ............................................................................................. 35 Hình 10. Mô hình sinh đầy đủ cho LDA. ...................................................................................... 36 Hình 11. Mô hình tổng quan hệ thống quảng cáo sử dụng chủ đề ẩn ........................................... 40 Hình 12. Trung bình các độ đo trên tất cả các truy vấn ................................................................. 49 Hình 13. Trung bình độ đo NDCG@5 tại các sô lượng truy vấn khác nhau ................................ 49 Hình 14. Trung bình độ đo MAP tại các số lượng truy vấn khác nhau ......................................... 50 Bảng các từ viết tắt CPA Cost Per Action/Acquisition CPC Cost Per Click CPM Cost Per Mille/Thousand CTR Cost Through Rate IDF Inverse Document Frequencies LDA Latent Dirichlet Allocation LSA Latent Semantic Analysis LSI Latent Semantic Indexing PLSA Probabilistic Latent Semantic Analysis PLSI Probabilistic Latent Semantic Indexing PPC Pay Per Click TF Term Frequencies Lời mở đầu Quảng cáo trực tuyến đang ngày càng phát triển và đem lại những khoản lợi nhuận khổng lồ trong các năm gần đây, lên đến 47.5 tỉ đô la [33]. Quảng cáo trên máy tìm kiếm là hình thức quảng cáo trực tuyến phổ biến nhất, trong đó các quảng cáo được hiển thị bên cạnh kết quả tìm kiếm trả về cho người dùng. Trong 5 năm gần đây, nhằm tìm kiếm và đưa ra một thứ tự quảng cáo phù hợp nhất, rất nhiều công trình trong nước cũng như trên thế giới đã được công bố [11], [22], [24], [25], [27], [30]. Lê Diệu Thu [27] đã đi theo một hướng tiếp cận mới trong quảng cáo theo ngữ cảnh bằng việc mở rộng tập từ khóa quảng cáo sử dụng kỹ thuật phân tích chủ đề ẩn. Tác giả đã chỉ ra những ảnh hưởng tích cực của chủ đề ẩn trong việc tìm kiếm và xếp hạng quảng cáo. Khóa luận này tiếp tục xem xét bài toán xếp hạng quảng cáo trên máy tìm kiếm và đề xuất mô hình xếp hạng quảng cáo sử dụng kỹ thuật phân tích chủ đề ẩn theo hướng tiếp cận mới. Khác với cách tiếp cận ở [27], mô hình của khóa luận này biểu diễn quảng cáo theo những đặc trưng về chủ đề ẩn và khai thác sự giúp đỡ của query logs trong việc xây dựng tập dữ liệu học và đã thu được những kết quả khả quan. Khóa luận gồm bốn chương được mô tả sơ bộ dưới đây: Chương 1. Khái quát về quảng cáo trực tuyến trình bày về tình hình quảng cáo trực tuyến trên thế giới cũng như ở Việt Nam, đồng thời giới thiệu về hình thức quảng cáo trên máy tìm kiếm và bài toán xếp hạng quảng cáo trên máy tìm kiếm. Chương 2. Các phương pháp quảng cáo thông qua tìm kiếm trình bày những công trình đã được đưa ra trong những năm gần đây nhằm giải quyết bài toán xếp hạng quảng cáo, chỉ ra ưu, nhược điểm của mỗi phương pháp. Chương 3. Hệ thống quảng cáo trực tuyến sử dụng kĩ thuật xếp hạng và phân tích chủ đề ẩn. Chương này trình bày về kĩ thuật xếp hạng, phương pháp học xếp hạng SVM Rank, kĩ thuật phân tích chủ đề ẩn và đề xuất mô hình xếp hạng quảng cáo sử dụng chủ đề ẩn. Chương 4. Thực nghiệm và đánh giá mô hình trình bày về dữ liệu được sử dụng, các giai đoạn xử lý dữ liệu và thực nghiệm, đưa ra kết quả của mô hình, nhận xét và phân tích kết quả thu được. 1 Phần kết luận. Tổng kết và tóm lược nội dung chính của khóa luận. 2 Chương 1. Khái quát về quảng cáo trực tuyến 1.1. Giới thiệu về quảng cáo Quảng cáo là hình thức tuyên truyền, giới thiệu hàng hoá, dịch vụ nhằm tạo sự hấp dẫn và kích thích người mua để đẩy mạnh việc bán hàng cũng như thực hiện dịch vụ. Trong chừng mực nhất định, quảng cáo cũng có tác dụng tích cực, tuy nhiên nó làm tăng giá cả của hàng hoá. Trong nền kinh tế hàng hoá, chi phí về quảng cáo thường rất lớn. Hình thức quảng cáo rất phong phú: áp phích đặc biệt, đăng báo, phát thanh, vô tuyến truyền hình, điện ảnh, triển lãm chế phẩm, nhãn hiệu sản xuất, tủ kính bày hàng ở các cửa hàng hay các xí nghiệp, thư tín, quà biếu [6]. Theo một tài liệu khác, quảng cáo là một hiện tượng phức tạp, gắn bó mật thiết với xã hội, văn hóa, lịch sử và kinh tế, nó không tuân theo bất cứ một định nghĩa đơn giản hay riêng biệt nào. Một vài khía cạnh của quảng cáo rất phổ dụng trong khi một vài khía cạnh khác lại mang đặc trưng cụ thể về văn hóa. Quảng cáo biến đổi từ nghệ thuật bán hàng cá nhân tới truyền thông gián tiếp, cung cấp những thông tin mới nhằm thuyết phục con người. Bên cạnh những thông báo nhằm mục đích bán hàng nó còn ẩn chứa những giá trị văn hóa và các ý kiến xã hội. Tùy thuộc vào từng quan điểm khác nhau, quảng cáo có thể có tác dụng tích cực hay tiêu cực tới xã hội và kinh tế [8]. Cũng theo [39] thì cha đẻ của hình thức quảng cáo là một người Ai Cập cổ. Ông ta đã dán tờ thông báo đầu tiên trên tường thành Thebes vào khoảng năm 3000 trước Công nguyên. Vài thế kỷ sau đó, ở Hy Lạp hình thức thông báo này trở nên rất phổ biến khi các thông tin dành cho công chúng được vẽ lên các tấm bảng gỗ trưng bày ở quảng trường thành phố. Nếu như các bảng quảng cáo đã phát triển nhanh sau sự ra đời của phương pháp in (bức áp phích đầu tiên do Caxton, người Anh, in từ năm 1477), thì họa sĩ Pháp J.Chéret (1835-1932) lại là người phát minh ra hình thức quảng cáo hiện đại. Đó là tờ quảng cáo một buổi biểu diễn năm 1867, gồm một câu ngắn và một hình ảnh màu mè gây ấn tượng mạnh. Tuy nhiên, chính họa sĩ Italy L.Cappiello (1875-1942) mới là người đầu tiên thực sự đề cập tới áp phích quảng cáo với tấm biển quảng cáo kẹo chocolate "Klaus" của ông năm 1903. 3 Ngày nay quảng cáo đã có những bước phát triển mới và được tiến hành thông qua các phương tiện thông tin đại chúng như: truyền hình, báo chí, phát thanh, quảng cáo qua bưu điện và đặc biệt, là quảng cáo trực tuyến qua Internet. 1.2. Quảng cáo trực tuyến Quảng cáo trực tuyến là một loại hình quảng cáo được thể hiện trên Internet và đặc biệt là các trang web [8]. Việc sử dụng Internet và World Wide Web ngày càng trở nên phổ biến, do vậy Internet đã trở thành một trong những phương tiện quảng cáo quan trọng nhất ngày nay. Một trong các lợi ích của việc quảng cáo trực tuyến là cho phép công bố thông tin và nội dung ngay lập tức mà không bị giới hạn bởi vị trí địa lý hay thời gian. Nó cho phép truyền đạt thông tin quảng cáo ở mức độ toàn cầu, tới một lượng lớn người dùng với một chi phí rất thấp. Quảng cáo trực tuyến đem lại hiệu quả đầu tư lớn cho khách hàng quảng cáo, nó cho phép tuỳ chỉnh các quảng cáo, bao gồm nội dung và các trang web mà quảng cáo sẽ được đăng lên. Một ví dụ đó là, AdWords và AdSense của Google cho phép quảng cáo được hiển thị trên các trang web có liên quan hoặc hiển thị bên cạnh kết quả tìm kiếm trên máy tìm kiếm đối với một số từ khóa được định nghĩa trước. Một trong các ưu điểm của quảng cáo trực tuyến là cách thức thanh toán, việc thanh toán được thực hiện với nhiều cách thức khác nhau, dựa vào phản ứng của người dùng đối với quảng cáo. Một số cách thức thanh toán như: CPM (Cost Per Mile/Thousand), CPV (Cost Per Visitor), CPC (Cost Per Click), CPA (Cost Per Action), CTR(Click Through Rate) [27]. 1.2.1. Tốc độ tăng trưởng và thị phần Năm 1994, quảng cáo trực tuyến bắt đầu xuất hiện trên trình duyệt web thương mại đầu tiên, Netscape Navigator 1.0, dưới hình thức là các banner quảng cáo [32]. Những quảng cáo đầu tiên trên web là những nội dung tĩnh hay logo của các công ty. Chúng thường xuất hiện ở đầu mỗi trang web vì đó thường là nơi dễ được quan sát nhất. Khi công nghệ ngày càng phát triển, mở ra nhiều cơ hội mới, rất nhiều hình thức quảng cáo trực tuyến đã xuất hiện. Một vài công ty tiến hành quảng cáo thông qua web site bởi những pop-up, như DoubleClick, AdForce và Windwire. Họ cung cấp một vài 4 thông tin hình ảnh và trình duyệt web sẽ thực thi một số công việc khi người dùng click vào một quảng cáo [32]. Một thập niên sau khi xuất hiện, những người quảng cáo trên thị trường Mĩ đã chi 9.6 tỉ đô la cho quảng cáo trực tuyến, năm 2004 tăng hơn 31.5% so với năm 2003; so sánh với 10% cho quảng cáo trên truyền hình, 7.4 % cho những dịch vụ quảng cáo khác nói chung và 6.6% cho GDP của nền kinh tế Mĩ (Hình 1). Theo báo cáo của IAB [33] vào năm 2008, doanh thu từ quảng cáo trực tuyến đã đạt tới hơn 23 tỉ đô la vào cuối năm 2008. Hình 1. Doanh thu quảng cáo trực tuyến nửa đầu và cuối những năm từ 1999 đến 2008 ở Mĩ [33]. Theo báo cáo mới nhất của Strategy Analytics [38], tổng chi phí cho quảng cáo trực tuyến trên toàn thế giới đã lên tới gần 47.5 tỉ đô la vào năm 2007 và có thể vượt 100 tỉ đô la vào năm 2012. Những thông tin trên cho thấy tốc độ phát triển nhanh chóng của quảng cáo trực tuyến trong những năm qua và còn hứa hẹn những mức doanh thu khổng lồ trong các năm tới. 1.2.2. Các hình thức quảng cáo trực tuyến Quảng cáo trực tuyến có thể được phân loại thành hai loại: hợp pháp (các mạng quảng cáo) và không hợp pháp (spamming). 5 Quảng cáo spam thường xâm nhập vào hệ thống và được gọi là Spyware, Adware hay quảng cáo Pop-up. Ví dụ, khi một trình duyệt mới được mở, pop-up quảng cáo xuất hiện và chuyển hướng người dùng tới website quảng cáo. Điều này gây nhiều bức xúc cho người dùng, vì vậy nhiều trình duyệt hỗ trợ chức năng chặn pop-up để giới hạn các pop- up không hợp pháp. Spyware và Adware thường là những ứng dụng mở rộng, một vài trong số chúng có thể gây hại, ví dụ như Trojan. Những quảng cáo hợp pháp có thể được phân loại thành: Quảng cáo trưng bày, email, phân loại và đấu giá, Lead Generation, đa phương tiện và tìm kiếm. Chi tiết về các hình thức quảng cáo này có thể tìm thấy tại [27]. Dưới đây là biểu đồ mô tả thu nhập của các loại này trong 6 tháng đầu của năm 2007 và năm 2008 tại Mĩ [33]. Hình 2. Phân loại doanh thu quảng cáo trực tuyến trong 6 tháng đầu năm 2007 và 2008 ở Mĩ [33] Như chúng ta thấy trên (Hình 2), search advertising, mà trong nội dung khóa luận này ta gọi là quảng cáo thông qua tìm kiếm, là loại hình quảng cáo phổ biến nhất và có doanh thu lớn nhất tại thị trường Mĩ từ năm 2007 đến năm 2008. Nó chiếm 41% tổng thu nhập từ quảng cáo trực tuyến trong 6 tháng đầu năm 2007 và 46% trong 6 tháng đầu năm 2008. 1.3. Quảng cáo trực tuyến ở Việt Nam Cùng với sự phát triển của quảng cáo trực tuyến trên thế giới, quảng cáo trực tuyến tại Việt Nam cũng từng bước phát triển và đã đạt được những thành công bước đầu. 6 1.3.1. Tổng quan về quảng