ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƢỜNG ĐẠI HỌC BÁCH KHOA -------------- BK TP.HCM HOÀNG VIẾT LÃM KHAI PHÁ CHỦ ĐỀ TIỀM ẨN TRONG DỮ LIỆU KHỞI NGHIỆP, ÁP DỤNG GIẢI THUẬT LDA Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.01 LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 11 năm 2015 CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI TRƢỜNG ĐẠI HỌC BÁCH KHOA – ĐHQG – HCM Cán bộ hƣớng dẫn khoa học: TS. Lê Thanh Vân Cán bộ chấm nhận xét 1: TS.
Trần Minh Quang Cán bộ chấm nhận xét 2: PGS. Đỗ Phúc Luận văn thạc sĩ đƣợc bảo vệ tại Trƣờng Đại học Bách Khoa, ĐHQG Tp.Hồ Chí Minh, ngày. Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. Nguyễn An Khƣơng 3.
Trần Minh Quang 4. Lƣơng Thế Nhân Xác nhận của Chủ tịch Hội đồng đánh giá luận văn và Trƣởng Khoa quản lý chuyên ngành sau khi luận văn đã đƣợc sửa chữa (nếu có). CHỦ TỊCH HỘI ĐỒNG TRƢỞNG KHOA TS. Phạm Trần Vũ ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Hoàng Viết Lãm MSHV: 13073032 Ngày, tháng, năm sinh: 05/10/1989 Nơi sinh: Quảng Ngãi Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.
TÊN ĐỀ TÀI: Khai phá chủ đề tiềm ẩn trong dữ liệu khởi nghiệp, áp dụng giải thuật LDA II. NHIỆM VỤ VÀ NỘI DUNG: Tìm hiểu lý thuyết, các công trình nghiên cứu liên quan đến bài toán rút trích dữ liệu, khai phá chủ đề tiềm ẩn trên tập dữ liệu khởi nghiệp. Đề xuất giải pháp để giải quyết bài toán khai phá chủ đề tiềm ẩn trong dữ liệu khởi nghiệp, xây dựng mô hình suy luận chủ đề dựa trên tập dữ liệu khởi nghiệp đƣợc thu thập từ nhiều nguồn. Tiến hành thực nghiệm, phân tích kết quả thu đƣợc từ giải pháp kỹ thuật khai phá chủ đề tiềm ẩn của đề tài, kiểm nghiệm kết quả thông qua một ứng dụng phân tích chủ đề, đánh giá khả năng thực tế.
NGÀY GIAO NHIỆM VỤ: 19/01/2015 IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 04/12/2015 V. CÁN BỘ HƢỚNG DẪN: TS. Lê Thanh Vân Tp.
CÁN BỘ HƢỚNG DẪN TRƢỞNG KHOA KH & KTMT (Họ tên và chữ ký) (Họ tên và chữ ký) TS. Lê Thanh Vân iii LỜI CẢM ƠN Trƣớc tiên, tôi xin gửi lời cảm ơn chân thành và sâu sắc đến cô TS. Lê Thanh Vân, khoa Khoa Học và Kỹ Thuật Máy Tính, trƣờng Đại Học Bách Khoa Tp.HCM đã tận tình hƣớng dẫn và giúp đỡ trong thời gian qua để tôi có thể hoàn thành tốt luận văn này. Tôi xin gửi lời cảm ơn chân thành đến các Thầy Cô trong khoa Khoa Học và Kỹ Thuật Máy Tính nói riêng và trƣờng Đại Học Bách Khoa Tp.HCM nói chung đã giảng dạy, cung cấp những kiến thức quý báu cho tôi trong suốt quá trình học tập và nghiên cứu tại trƣờng Tôi xin gửi lời cảm ơn đến gia đình, bạn bè và đồng nghiệp đã hỗ trợ tôi về thời gian và tinh thần, tạo mọi điều kiện thuận lợi giúp tôi hoàn thành luận văn.
Do thời gian và kiến thức có hạn nên luận văn chắc chắn không tránh khỏi những thiếu sót nhất định. Tôi rất mong nhận đƣợc những ý kiến đóng góp quý báu của các thầy cô và các bạn. HCM, ngày 15 tháng 11 năm 2015 Học viên Hoàng Viết Lãm iv TÓM TẮT LUẬN VĂN Ngày nay, với sự phát triển mạnh mẽ của khoa học và công nghệ, kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang đƣợc nghiên cứu, ứng dụng trong nhiều lĩnh vực, giải quyết các vấn đề trong xã hội. Trong lĩnh vực khởi nghiệp, việc nghiên cứu, khai thác thông tin tri thức sẽ rất cần thiết vì khởi nghiệp hiện nay là một đề tài nóng không chỉ trong nƣớc mà cả ngoài nƣớc, rất nhiều dự án khởi nghiệp đƣợc hình thành và phát triển, dẫn đến có nhu cần cần biết thông tin về tình hình khởi nghiệp, kinh nghiệm khởi nghiệp, vốn-đầu tƣ, xu thế thị trƣờng.
Luận văn sẽ trình bày cơ sở lý thuyết và giải pháp cho việc khai thác chủ đề tiềm ẩn trong dữ liệu hƣớng nghiệp dựa vào giải thuật Latent Dirichlet Allocation - LDA. LDA là một giải thuật khai thác chủ đề tiềm ẩn đã và đang đƣợc áp dụng mạnh mẽ trong nhiều lĩnh vực nhƣ quảng cáo, tài chính, phân tích hành vi ngƣời dùng.Chính vì vậy việc nghiên cứu và áp dụng giải thuật này cho dữ liệu khởi nghiệp sẽ giải quyết đƣợc nhu cầu về thông tin khởi nghiệp đã nêu trên. Dựa vào cơ sở lý thuyết và giải pháp, luận văn sẽ phát triển một công cụ phân tích chủ đề khởi nghiệp tiềm ẩn với dữ liệu đầu vào là một URL về tin tức khởi nghiệp. Hy vọng với giải pháp và công cụ phân tích chủ đề khởi nghiệp tiềm ẩn sẽ giúp giải quyết đƣợc phần nào nhu cầu thông tin và xu hƣớng khởi nghiệp trong xã hội.
Ngoài ra luận văn đã tìm hiểu xử lý ngôn ngữ tự nhiên – Natural Language Processing NLP, áp dụng các frameworks cho xử lý và lƣu trữ dữ liệu lớn. Luận văn đã xây dựng đƣợc mô hình và phát hiện ra 8 chủ đề tiềm ẩn trong tập dữ liệu huấn luyện. Thực hiện quá trình kiểm tra, đánh giá mô hình. v LỜI CAM ĐOAN Tôi xin cam đoan rằng ngoài các kết quả, các thông tin tham khảo từ các công trình khác nhƣ đã ghi rõ trong luận văn, những công việc, kết quả đƣợc trình bày trong luận văn này là do chính tôi thực hiện và chƣa đƣợc sử dụng để lấy bất kỳ bằng cấp, chứng chỉ nào khác.
HCM, ngày 15 tháng 11 năm 2015 Học viên Hoàng Viết Lãm vi MỤC LỤC NHIỆM VỤ LUẬN VĂN THẠC SĨ. iii LỜI CẢM ƠN. iv TÓM TẮT LUẬN VĂN. v LỜI CAM ĐOAN.
vi MỤC LỤC. vii DANH MỤC HÌNH. ix DANH MỤC BẢNG. x DANH MỤC THUẬT NGỮ ANH – VIỆT .1 Giới thiệu đề tài .2 Mục tiêu nghiên cứu đề tài .3 Phương pháp nghiên cứu .4 Ý nghĩa của đề tài .5 Bố cục luận văn .1 Những phương pháp rút trích dữ liệu tiềm ẩn LSI (Latent Semantic Indexing) và pLSI (probabilistic Latent Semantic Indexing) – tiền thân của giải thuật LDA (Latent Dirichlet Allocation) .2 Phương pháp LDA (Latent Dirichlet Allocation) .1 Định nghĩa LDA 18 2.2 Giải thuật LDA 19 2.1 Phân phối Dirichlet .2 Các chủ đề tiềm ẩn trong LDA .3 Suy diễn và ƣớc lƣợng tham số trong LDA 23 2.2 Ƣớc lƣợng tham số .1 Phát biểu bài toán .2 Mô hình ứng dụng .3 Các thành phần ứng dụng .1 Thu thập dữ liệu khởi nghiệp 33 3.2 Nguồn dữ liệu thu thập .2 Tiền xử lý dữ liệu 40 3.3 Xử lý dữ liệu 41 3.1 Lƣu trữ dữ liệu .2 Xử lý dữ liệu .3 MapReduce trên LDA .4 Tunning các thông số mô hình chạy .1 Kết quả thực nghiệm .1 Hiện thực ứng dụng kiểm chứng 49 4.2 Chuẩn bị dữ liệu chạy thực nghiệm 53 4.2 Qui trình thực nghiệm .3 Kết quả chạy thực nghiệm 53 4.1 Data thực nghiệm trong bộ huấn luyện .2 Data thực nghiệm ngoài bộ huấn luyện .1 Đóng góp của luận văn .2 Hướng phát triển tiếp theo.
58 TÀI LIỆU THAM KHẢO. 61 viii DANH MỤC HÌNH Hình 1: Mô hình LDA cơ bản. 20 Hình 2: Mô hình LDA mịn. 21 Hình 3: Ví dụ quá trình sinh mẫu LDA.
22 Hình 4: (Bên trái) Mô hình LDA. (Bên phải) Mô hình suy diễn biến phân LDA. 25 Hình 5: Giải thuật suy diễn biến phân LDA. 26 Hình 6: Ví dụ chuỗi Markov.
27 Hình 7: Giải thuật suy diễn Gibbs Sampling. 28 Hình 8: Sự hội tụ của chuỗi Markov. 28 Hình 9: Giải thuật suy diễn Gibbs Sampling LDA. 30 Hình 10: Mô hình ứng dụng.
32 Hình 11: Chi tiết định dạng JSON của dữ liệu Facebook. 34 Hình 12: Cấu trúc index url_paging. 36 Hình 13: Dữ liệu mẫu index url_paging. 37 Hình 14: Cấu trúc index url_info.
38 Hình 15: Dữ liệu index url_info. 40 Hình 16: Phân tích cú pháp câu. 40 Hình 17: Xử lý dữ liệu (huấn luyện dữ liệu). 42 Hình 18: Giai đoạn Map trong Gibbs Sampling.
44 Hình 19: Ví dụ minh hoạ MapReduce. 45 Hình 20: Ma trận tài liệu-chủ đề áp dụng MapReduce trên 2 máy tính. 46 Hình 21: Ma trận từ-chủ đề áp dụng MapReduce. 46 Hình 22: Công cụ tìm kiếm tài liệu dựa vào những từ xuất hiện.
50 Hình 23: Data flow ứng dụng. 51 Hình 24: Ứng dụng thực nghiệm. 52 ix DANH MỤC BẢNG Bảng 1: Cấu trúc các thành phần bài post – API Facebook. 33 Bảng 2: Cấu trúc các thành phần bài bình luận – API Facebook.
34 Bảng 3: Bảng dữ liệu pattern url_paging của các websites. 37 Bảng 4: Bảng dữ liệu pattern url_info của các websites. 39 Bảng 5: Bảng dữ liệu định nghĩa về Tags. 41 Bảng 6: Cấu trúc bảng lƣu trữ trong HBase.
42 Bảng 7: Ví dụ cách gán nhãn một chủ đề mô hình. 48 Bảng 8: Bảng 20 chủ đề và danh sách 10 từ có trọng số cao nhất. 49 Bảng 9: Bảng gán nhãn các chủ đề mô hình. 50 Bảng 10: Kết quả thực nghiệm trong bộ huấn luyện.
53 Bảng 11: Kết quả thực nghiệm ngoài bộ huấn luyện. 55 x DANH MỤC THUẬT NGỮ ANH – VIỆT STT Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt Viết tắt 1 Information retrieval Truy vấn thông tin IR 2 Term frequency – inverse TF-IDF document frequency 3 Latent Semantic Indexing Chỉ mục ngữ nghĩa tiềm ẩn LSI 4 Probabilistic LSI Xác suất chỉ mục ngữ nghĩa pLSI tiềm ẩn 5 Latent Dirichlet Allocation LDA 6 Singular Value Decomposition SVD 7 Topic Chủ đề 8 Kullback- Leibler KL xi 1 CHƢƠNG 1: GIỚI THIỆU 1.1 Giới thiệu đề tài Ngày nay với sự bùng nổ mạnh mẽ của công nghệ thông tin trong nhiều lĩnh vực đã tạo ra lƣợng dữ liệu khổng lồ, hằng ngày có đến hằng tỷ gigabyte dữ liệu phát sinh, trao đổi và chia sẻ qua mạng. Đây là tiền đề của cuộc cách mạng dữ liệu. Các nhà nghiên cứu đã nhận định thế kỷ này là thế kỷ của dữ liệu siêu lớn – big data.
Tiếp xúc với nguồn dữ liệu to lớn đó, con ngƣời xuất hiện nhu cầu tìm kiếm tri thức, con ngƣời không thể thao tác dữ liệu nhƣ cách truyền thống đƣợc. Có rất nhiều bài toán phát sinh từ nhu cầu thiết yếu này và khai phá dữ liệu lấy ra các chủ đề tiềm ẩn là một trong số đó. Phƣơng pháp này sẽ giúp chúng ta tiết kiệm thời gian và công sức, không cần phải duyệt qua tất cả tập dữ liệu khổng lồ đó mà vẫn lấy đƣợc mẫu thông tin/tri thức cần thiết.