Tài liệu Cải tiến thuật toán cây plwap cho khai thác chuỗi dữ liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- QUÁCH ĐẶNG HOÀNG MỸ CẢI TIẾN THUẬT TOÁN CÂY PLWAP CHO KHAI THÁC CHUỖI DỮ LIỆU LUẬN VĂN THẠC SĨ Chuyên ngành : Công nghệ Thông tin Mã số ngành : 60480201 TP. HỒ CHÍ MINH, tháng 04 năm 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- QUÁCH ĐẶNG HOÀNG MỸ CẢI TIẾN THUẬT TOÁN CÂY PLWAP CHO KHAI THÁC CHUỖI DỮ LIỆU LUẬN VĂN THẠC SĨ Chuyên ngành : Công nghệ Thông tin Mã số ngành : 60480201 CÁN BỘ HƯỚNG DẪN KHOA HỌC: TS NGUYỄN THỊ THANH SANG TP. HỒ CHÍ MINH, tháng 04 năm 2015 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM Cán bộ hướng dẫn khoa học : . (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Công nghệ TP. HCM ngày 11 tháng 04 năm 2015. Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm: (Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ Luận văn Thạc sĩ) TT Họ và tên Chủ tịch Hội đồng 1 GS. TSKH. Hoàng Văn Kiếm 2 TS. Võ Đình Bảy Phản biện 1 3 TS. Cao Tùng Anh Phản biện 2 4 TS. Lư Nhật Vinh Ủy viên 5 TS. Nguyễn Văn Mùi Chủ tịch Ủy viên, Thư ký Xác nhận của Chủ tịch Hội đồng đánh giá Luận sau khi Luận văn đã được sửa chữa (nếu có). Chủ tịch Hội đồng đánh giá LV TRƯỜNG ĐH CÔNG NGHỆ TP. HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG QLKH – ĐTSĐH Độc lập – Tự do – Hạnh phúc TP. HCM, ngày 11 tháng 04 năm 2015 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên:…..…..QUÁCH ĐẶNG HOÀNG MỸ...............Giới tính: .…....Nam ........ Ngày, tháng, năm sinh:......................07/03/1989.....................Nơi sinh:...Cà Mau…. .. Chuyên ngành: .............Công nghệ thông tin.............................MSHV: …1341860012... I- Tên đề tài: CẢI TIẾN THUẬT TOÁN CÂY PLWAP TRONG KHAI THÁC CHUỖI DỮ LIỆU............................................................................................................ II- Nhiệm vụ và nội dung: - Nghiên cứu các kỹ thuật khai thác các mẫu chuỗi dữ liệu phổ biến được truy cập dựa vào các hành vi sử dụng web của người dùng được ghi trong web log - Nghiên cứu thuật toán khai thác cây PLWAP. - Nghiên cứu mô hình xác suất, cụ thể là mô hình Markov - Áp dụng mô hình xác suất Markov lên thuật toán khai thác cây PLWAP. III- Ngày giao nhiệm vụ: 08-08-2014 IV- Ngày hoàn thành nhiệm vụ: 11-04-2015 V- Cán bộ hướng dẫn: (Ghi rõ học hàm, học vị, họ, tên)................................................ 1. TS NGUYỄN THỊ THANH SANG...................................................... CÁN BỘ HƯỚNG DẪN (Họ tên và chữ ký) KHOA QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã được cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Học viên thực hiện luận văn (Ký và ghi rõ họ tên) ii LỜI CÁM ƠN Lời cảm ơn chân thành chúng tôi xin gởi đến Ban Giám Hiệu, toàn thể cán bộ nhân viên, giảng viên trường Đại Học HUTECH, Ban lãnh đạo Phòng Quản Lý Khoa Học và Đào Tạo Sau Đại Học, khoa Công Nghệ Thông Tin đã tạo điều kiện thuận lợi cho chúng tôi học tập và nghiên cứu trong suốt học trình cao học. Chúng tôi xin chân thành tri ân đến các thầy cô đã trực tiếp động viên, hướng dẫn chúng tôi trong suốt học trình: PGS.TS Lê Hoài Bắc, PGS.TS Nguyễn Xuân Huy, TS Nguyễn An Khương, TS Nguyễn Chánh Thành, TS Nguyễn Thị Thanh Sang, TS Tân Hạnh, TS Nguyễn Đình Thuân, TS Lê Mạnh Hải, TS Nguyễn Tuấn Đăng, TS Lư Nhật Vinh, TS Võ Đình Bảy, TS Cao Tùng Anh, TS Nguyễn Văn Mùi, GS. TSKH. Hoàng Văn Kiếm. Với lòng tri ân sâu sắc, chúng tôi muốn nói lời cảm ơn chân thành đến cô TS Nguyễn Thị Thanh Sang đã rất tận tụy và nghiêm túc hướng dẫn chúng tôi trong quá trình thực hiện nghiên cứu này. Chúng tôi cũng xin chân thành cảm ơn Ban lãnh đạo Phòng Quản Trị, Phòng Tổ Chức Hành Chính, Phòng Tài Chính, Trung Tâm Thư Viện cùng đồng nghiệp của trường HUTECH đã tạo điều kiện, cho phép, động viên và giúp đỡ chúng tôi trong suốt học trình cao học và thực hiện nghiên cứu này. Cuối cùng nhưng cũng là một yếu tố quan trọng giúp chúng tôi hoàn thành nghiên cứu này, đó là gia đình. Chúng tôi muốn nói lời tri ân chân thành đến cha mẹ, anh chị em chúng tôi đã động viên và chia sẻ mọi hoàn cảnh với chúng tôi trong suốt học trình này. Quách Đặng Hoàng Mỹ iii TÓM TẮT Hệ thống đề xuất web là hệ thống đề xuất những thông tin hữu ích qua việc khai thác sử dụng web từ thông tin lịch sử truy cập web của người dùng lưu trong tập tin web log của máy chủ. Hiện nay, trên thế giới, nhiều website thương mại điện tử đã ứng dụng hệ thống này vào website của mình để đề xuất thông tin cho người dùng dựa trên lịch sử tương tác của người đó và những người khác với hệ thống nhằm giảm thiểu thời gian trực tuyến của người dùng, giúp người dùng định hướng tốt hơn trên website mình. Tuy nhiên, lượng thông tin được đề xuất từ tập hợp các chuỗi phổ biến lại quá nhiều, mặc dù dữ liệu trong web log đã được tiền xử lý và khai thác bởi một số thuật toán, điển hình là thuật toán khai thác cây PLWAP. Chính vì vậy, việc nghiên cứu cải thiện thuật toán khai thác cây PLWAP, cải tiến về thời gian, độ chính xác dự đoán cao từ mẫu chuỗi phổ biến được khai thác từ web log. Từ đây, tôi quyết định chọn đề tài nghiên cứu “Cải tiến thuật toán cây PLWAP trong khai thác chuỗi dữ liệu”. Các yêu cầu cần thực hiện trong đề tài nghiên cứu này là: - Nghiên cứu thuật toán cây PLWAP trong khai thác chuỗi dữ liệu. - Nghiên cứu mô hình Markov. - Nghiên cứu và ứng dụng mô hình chuỗi Markov vào thuật toán cây PLWAP cho việc đề xuất web. - Nhận xét, đánh giá về thuật toán cây PLWAP trước và sau khi áp dụng mô hình Markov vào, dựa vào kết quả đã thực nghiệm trên bộ dữ liệu cụ thể. iv ABSTRACT The web recommendation system is a system proposed useful information through the use of web mining that the users web access history information file stored on the server's web log. Nowadays, in the world, many website commercial have already applied this system into their website to proposed with information for user based on that user’s interactive history and the others with system to reduce user online time, help user has a good orientation on their website. However, amount of information has recommended from set of frequent sequence that is so much, although data in web log that has preprocessed and mining by some algorithm, typically is mining PLWAP-tree algorithm. Therefore, the research improves algorithm mining PLWAP-tree, improve about time, recommendation information object to predict has a height precision from frequent sequence pattern that is mining from web log. Hence, I decided to choose a topic of research “Improve algorithm PLWAP-tree in mining data sequences”. These request need do in this research topic: - Research algorithm PLWAP-tree in mining data sequences - Research Markov model - Research and apply Markov model to algorithm PLWAP-tree in order to improve the performance of Web recommendation. - Comment, evaluation for algorithm PLWAP-tree before and after applied Markov, based on result experimented on specific dataset v MỤC LỤC DANH MỤC CÁC THUẬT NGỮ VÀ CÁC CHỮ VIẾT TẮT ............................... vii DANH MỤC CÁC HÌNH ........................................................................................ viii DANH MỤC CÁC BẢNG.......................................................................................... x CHƯƠNG 1 GIỚI THIỆU .......................................................................................... 1 1.1. Phát biểu vấn đề ............................................................................................. 1 1.2. Định hướng nghiên cứu ................................................................................. 2 1.3. Tổng quan về tình hình nghiên cứu ............................................................... 2 1.3.1. Tổng quan về hệ thống đề xuất web........................................................ 2 1.3.2. Tổng quan về khai thác chuỗi dữ liệu ..................................................... 5 1.3.3. Tổng quan về lĩnh vực nghiên cứu .......................................................... 7 1.4. Tổ chức của luận văn ..................................................................................... 8 CHƯƠNG 2 CÁC THUẬT TOÁN KHAI THÁC CHUỖI DỮ LIỆU ....................... 9 2.1. Tổng quan về các thuật toán khai thác chuỗi dữ liệu .................................... 9 2.2. liệu Thuật toán khai thác cây WAP và cây PLWAP trong khai thác chuỗi dữ ..................................................................................................................... 17 2.2.1. Khai thác WAS từ web log .................................................................... 17 2.2.2. Thuật toán khai thác cây WAP ............................................................. 19 2.2.3. Thuật toán khai thác cây PLWAP ......................................................... 25 CHƯƠNG 3 CẢI TIẾN THUẬT TOÁN KHAI THÁC CÂY PLWAP TRONG KHAI THÁC CHUỖI DỮ LIỆU .............................................................................. 40 3.1. Mô hình Markov .......................................................................................... 40 3.2. Cải tiến thuật toán cây PLWAP trong khai thác chuỗi dữ liệu ................... 42 3.3. Luật đề xuất ................................................................................................. 48 CHƯƠNG 4 THỰC NGHIỆM VÀ ĐÁNH GIÁ ...................................................... 50 4.1. Thực nghiệm ................................................................................................ 50 4.2. Đánh giá giải thuật PLWAP và PLWAP–Markov ...................................... 50 4.3. Kết quả thực nghiệm.................................................................................... 54 vi CHƯƠNG 5 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ........................................... 59 5.1. Kết luận........................................................................................................ 59 5.2. Hướng phát triển .......................................................................................... 60 TÀI LIỆU THAM KHẢO ......................................................................................... 61 vii DANH MỤC CÁC THUẬT NGỮ VÀ CÁC CHỮ VIẾT TẮT Thuật ngữ, chữ viết tắt CS-Mine FP FWAP GSP PLWAP-tree PLWAP-Mine PSP WAS WASD WAP-Mine WAP-tree WCM WSM WRS Tiếng Anh Tiếng Việt Graph Traversal Đồ thị giao nhau Precision Độ chính xác Satisfactory Độ thỏa mãn, độ đạt được Pre-processing Tiền xử lý Data minning Khai thác dữ liệu Conditional Sequences mining algorithm Frequent Pattern Thuật toán khai thác chuỗi điều kiện Mẫu phổ biến Frequent Web Access Pattern Generatized Sequential Patterns Pre-Order Linked WAP-tree Pre-Order Linked WAP mining algorithm Prefix-Tree Sequential Patterns Web Access Sequences Web Access Sequences Database Web Access Pattern mining algorithm Web Access Pattern - tree Web Content Mining Web Structure Mining Web Recommender System Mẫu truy cập web phổ biến Mẫu tuần tự tổng quát Cây WAP liên kết thứ tự trước Thuật toán khai thác mẫu truy cập web liên kết thứ tự trước Mẫu tuần tự cho cây tiền tố Chuỗi truy cập web Cơ sở dữ liệu chuỗi truy cập web Thuật toán khai thác mẫu truy cập web Cây mẫu truy cập web Khai thác nội dung web Khai thác cấu trúc web Hệ thống đề xuất web viii DANH MỤC CÁC HÌNH Hình 1.1 - Hệ thống đề xuất web ................................................................................ 3 Hình 2.1 - Thế hệ của tập phổ biến ứng cử viên và tập phổ biến với hỗ trợ cực tiểu là 2 [9] ........................................................................................................................... 11 Hình 2.2 - Cây FP ghi nén, thông tin mẫu phổ biến [9] ............................................ 14 Hình 2.3 - Cây FP điều kiện liên kết với nút điều kiện I3 [9]................................... 15 Hình 2.4 - Xây dựng cây WAP ban đầu [3] .............................................................. 22 Hình 2.5 - Xây dựng lại cây WAP cho khai thác mẫu có điều kiện dựa trên c [3]... 23 Hình 2.6 - Ấn định mã nhị phân với các nút vị trí trong cây nhị phân [3]................ 26 Hình 2.7 - Xây dựng cây PLWAP sử dụng giao nhau thứ tự trước [3] .................... 30 Hình 2.8 - Khai thác cây PLWAP để tìm ra chuỗi phổ biến bắt đầu với a [3] ......... 35 Hình 2.9 - Khai thác cây PLWAP để tìm ra chuỗi phổ biến bắt đầu với ab hoặc ac [3] .............................................................................................................................. 37 Hình 2.10 - Khai thác cây PLWAP để tìm ra chuỗi phổ biến bắt đầu với b hoặc c [3] ................................................................................................................................... 39 Hình 3.1 - Mô hình chuỗi Markov ........................................................................... 41 Hình 3.2 - Xây dựng đồ thị liên kết cho các trang .................................................... 43 Hình 3.3 - Xác suất từ trang i đến trang j .................................................................. 44 Hình 3.4 - Ma trận truyền .......................................................................................... 45 Hình 4.1 - Thời gian thực thi của giải thuật PLWAP và PLWAP-Markov trên hai bộ dữ liệu Cezeife và NASA .......................................................................................... 55 ix Hình 4.2 - Precision và satisfactory đo được từ hai giải thuật PLWAP và PLWAPMarkov trên bộ dữ liệu Cezeife ................................................................................ 57 Hình 4.3 - Precision và satisfactory đo được từ hai giải thuật PLWAP và PLWAPMarkov trên bộ dữ liệu NASA .................................................................................. 58 x DANH MỤC CÁC BẢNG Bảng 2.1 - Danh sách các tập giao dịch của người dùng truy cập web [9] ............... 10 Bảng 2.2 - Khai thác cây FP bằng cách tạo ra cơ sở mẫu điều kiện [9] ................... 15 Bảng 2.3 - Danh sách dữ liệu chuỗi truy cập web [3] ............................................... 18 Bảng 2.4 - Danh sách dữ liệu chuỗi truy cập web cho cây WAP [3] ....................... 20 Bảng 2.5 – Thuật toán cây PLWAP [3] .................................................................... 30 Bảng 2.6 - Thuật toán xây dựng cây PLWAP [3] ..................................................... 31 Bảng 2.7 - Thuật toán khai thác cây PLWAP [3] ..................................................... 32 Bảng 3.1 - Thuật toán sinh luật cho cây PLWAP-Markov ....................................... 49 Bảng 4.1 - Thông tin bộ dữ liệu Cezeife và NASA .................................................. 50 Bảng 4.2 - Thuật toán sinh luật cho cây PLWAP [16] ............................................. 51 Bảng 4.3 - Thuật toán tính toán độ chính xác cho cây PLWAP [16] ....................... 52 Bảng 4.4 - Thuật toán tính toán độ chính xác cho cây PLWAP-Markov ................. 53 1 CHƯƠNG 1: GIỚI THIỆU 1.1. Phát biểu vấn đề Hệ thống đề xuất web (WRS) là một hệ thống thông minh, đề xuất thông tin cho người sử dụng web dựa trên lịch sử tương tác của người đó và những người khác với hệ thống nhằm tăng tính tin cậy và thu hút nhiều người sử dụng web. Hệ thống đề xuất web được áp dụng trong nhiều lĩnh vực, ví dụ các trang web thương mại điện tử, nhằm giúp đề xuất các sản phẩm đang được quan tâm nhiều nhất cho khách hàng, tạo sự tiện lợi cho khách hàng tìm kiếm sản phẩm và tăng doanh số bán ra. Đồng thời, sự gia tăng nhanh chóng lượng dữ liệu web và những kỹ thuật khai thác dữ liệu phát triển gần đây đã dẫn đến sự quan tâm ngày càng cao trong các phương pháp để khám phá dữ liệu sử dụng web. Trong bối cảnh đó, việc khai thác sử dụng web có thể được sử dụng để khám phá mẫu sử dụng web để hỗ trợ người dùng thực hiện quyết định tốt hơn bằng cách gợi ý một cách hiệu quả hơn về tổ chức các trang web cho ứng dụng dựa trên web. Đối với một công ty thương mại điện tử, việc khai thác sử dụng web có thể được áp dụng để tìm ra những khách hàng tiềm năng trong tương lai, những người này có thể sẽ tạo ra một số lượng lớn mua hàng, hoặc để dự đoán các giao dịch thương mại điện tử dựa trên quan sát của du khách trước đó. Từ đây, việc lựa chọn một thuật toán khai thác hiệu quả đóng một vai trò quan trọng trong việc đề xuất thông tin cho người sử dụng trực tuyến. Các thuật toán khai thác tuần tự giống như Apriori sẽ tạo ra bộ các mẫu ứng cử viên rất lớn, đặc biệt là khi các mẫu còn rất dài, còn thuật toán khai thác cây WAP có nhược điểm là đệ quy xây dựng lại cây WAP trung gian trong khai thác, tốn thời gian. Trong khi đó, thuật toán khai thác cây PLWAP thì các lưu trữ dữ liệu chuỗi trong một cây WAP liên kết 2 thứ tự trước, mỗi nút của cây này có một vị trí mã nhị phân chỉ định cho trực tiếp khai thác các mẫu chuỗi mà không cần xây dựng cây WAP trung gian. Tuy nhiên, thuật toán khai thác cây PLWAP vẫn còn một số hạn chế như sau: - Về bộ nhớ máy tính: tốn nhiều bộ nhớ để lưu cấu trúc cây. - Về tốc độ, thời gian chạy: mất nhiều thời gian sinh tạo các mẫu truy cập Web phổ biến nếu số lượng phần tử và các chuỗi nhập quá lớn. - Về mặt ngữ nghĩa: vì hệ thống đề xuất chưa hiểu được sự kiện, đối tượng là gì (nó là sách, video,…) nên nếu hiểu được đối tượng, sự kiện là gì, thì hệ thống sẽ đề xuất những thông tin đem lại hiệu quả cao hơn. - Về thông tin đề xuất: có nhiều đối tượng / thông tin được đề xuất cho người dùng mà chưa được phân loại hay sắp xếp kết quả. 1.2. Định hướng nghiên cứu Kết quả cuối cùng của thuật toán khai thác cây PLWAP mang lại là tập hợp tất cả các chuỗi phổ biến để đề xuất cho người dùng, vấn đề là khi đề xuất thông tin thì có lại nhiều chuỗi phổ biến được đề xuất. Vì vậy, việc xây dựng đề tài nghiên cứu, cải tiến thuật toán khai thác cây PLWAP trong việc khai thác chuỗi dữ liệu, cụ thể là nghiên cứu, cải tiến về thời gian, về độ chính xác từ mẫu chuỗi phổ biến được khai thác từ web log. Cải tiến này sẽ giúp cho giải thuật đề xuất những đối tượng / thông tin hiệu quả hơn, thời gian đề xuất nhanh hơn cũng như giúp cho người dùng hay khách hàng ở các trang thương mại điện tử có những quyết định tốt hơn. 1.3. Tổng quan về tình hình nghiên cứu 1.3.1. Tổng quan về hệ thống đề xuất web Ngày nay, dựa vào mạng Internet mà nhiều loại hình kinh doanh trực tuyến được hình thành. Với hình thức kinh doanh này, người tiêu dùng có thể tiếp cận với 3 hàng hóa một cách dễ dàng và nhanh chóng so với các hình thức mua bán hàng truyền thống. Với những thế mạnh của mình, những trang web bán hàng sẽ dần thay thế các gian hàng hay các siêu thị truyền thống. Để khách hàng có thể tìm mua được những món hàng ưng ý thì việc đề xuất, gợi ý rất là quan trọng. Đối với phương thức bán hàng truyền thống thì người bán hàng tư vấn trực tiếp là một lợi thế. Vì thế, để hình thức mua bán qua mạng thực sự phát triển thì bên cạnh các lợi thế vốn có của mình việc có thêm một “người đề xuất, gợi ý” là rất cần thiết. Trên thực tế, hệ thống tư vấn thực chất là quá trình hỗ trợ khách hàng đưa ra quyết định của mình trong việc chọn lựa sản phẩm. Nó đóng vai trò giống như một người bán hàng có khả năng thu thập thông tin về sở thích của khách hàng thông qua việc truy cập web, sau đó tìm trong kho hàng của mình những mặt hàng thích hợp nhất với sở thích đó. Và cũng từ đây, hệ thống tự đề xuất dần dần được hình thành và phát triển. Một hệ thống đề xuất tốt có thể đóng vai trò như người trung gian giúp khách hàng đưa ra quyết định tốt hơn khi chọn hàng. Cơ cấu làm việc của hệ thống đề xuất là dựa trên lịch sử tương tác của người dùng đó và những người khác với hệ thống để tìm ra chuỗi truy cập web, sau đó nó được khai thác và xử lý để tìm ra những chuỗi truy cập phổ biến để đề xuất cho người dùng. Chuỗi truy cập web thường được khai thác và xử lý bởi một trong số thuật toán khai thác. Web log WAP-mine, PLWAP- mine,… Pre-processing WAS Data mining FWAP Hình 1.1 - Hệ thống đề xuất web Web Recommendation 4 Qui trình của hệ thống đề xuất web [1] như sau: - Web log: được lấy từ server, mỗi dòng dữ liệu trong web log có định dạng sau: host/ip user [date:time] “request [30/Aug/2001:12:03:24-0500] url” status bytes 137.207.76.120- “GET/jdk1.3/docs/relnotes/deprecatedlist.html HTTP/1.0” 200 2781 Thông tin này ghi nhận từ trái sang phải, địa chỉ ip máy chủ của máy tính truy cập vào trang web (137.207.76.120), số nhận dạng người dùng (-), thời gian truy cập (12:03:24 ngày 30 tháng 8 năm 2001 múi giờ quốc tế 5), yêu cầu (GET/jdk1.3/docs/relnotes/deprecatedlist.html), khu tài liệu tham khảo thống nhất (url) của trang web được truy cập (HTTP/1.0), trạng thái yêu cầu (có thể chuỗi 200 cho thành công, chuỗi 300 cho chuyển hướng, chuỗi 400 cho thất bại, chuỗi 500 cho lỗi máy chủ), số lượng byte dữ liệu được yêu cầu (2781). Để sử dụng được web log này cho việc nghiên cứu, thì nó phải qua bước tiền xử lý, tức pre-processing. - Pre-processing: bao gồm chuyển đổi việc sử dụng, nội dung và cấu trúc thông tin trong nhiều nguồn dữ liệu có sẵn vào trừu tượng hóa dữ liệu cần thiết cho phát hiện mẫu. Quá trình tiền xử lý dữ liệu như làm sạch dữ liệu, nhận dạng người dùng và xác định phiên có thể được xác định trên dữ liệu log và các web log ban đầu được chuyển tới người dùng truy cập bộ dữ liệu cho phiên phát hiện mẫu hơn nữa và dữ liệu phân tích… - WAS: sau khi tiền xử lý web log, ta được chuỗi web log trong cơ sở dữ liệu giao dịch có mỗi tupe gồm một ID giao dịch và chuỗi truy cập web của giao dịch đó. Ví dụ như người sử dụng ID 200 từ web log, đã truy cập các trang a, d, b, a và c. 5 - Data mining: quá trình khai thác dữ liệu từ chuỗi truy cập web bằng các sử dụng các phương pháp, kỹ thuật, các thuật toán khai thác dữ liệu như cây WAP, cây PLWAP, … - FWAP: mẫu truy cập web phổ biến có được sau khi khai thác dữ liệu. - Web recommendation: cuối cùng, những mẫu phổ biến này được dùng để đề xuất, dự đoán đối tượng thông tin sẽ xuất hiện tiếp theo cho người dùng. 1.3.2. Tổng quan về khai thác chuỗi dữ liệu Hiện nay, với sự gia tăng nhanh chóng trong việc sử dụng các trang web trên toàn thế giới cho các doanh nghiệp thương mại điện tử, dịch vụ web… thì khai thác web là một trong những lĩnh vực ứng dụng phổ biến nhất. Bên cạnh đó, việc khai thác web cũng được phân thành ba loại: khai thác nội dung trang web (WCM), khai thác cấu trúc web (WSM) và khai thác sử dụng web (WUM) [2].  Khai thác nội dung trang web yêu cầu việc tìm ra các thông tin hữu ích từ các dữ liệu thật trên trang web, chẳng hạn như dữ liệu mà trang web được thiết kế để truyền đạt cho người sử dụng. Nó thường bao gồm một số loại dữ liệu như văn bản, hình ảnh, âm thanh, video, siêu dữ liệu, cũng như siêu liên kết. Dữ liệu nội dung trang web bao gồm văn bản tự do, dữ liệu bán cấu trúc như các tài liệu HTML và dữ liệu có cấu trúc giống như dữ liệu trong bảng, cũng như cơ sở dữ liệu tạo ra các trang HTML và XML.  Khai thác cấu trúc web tìm ra các mẫu cấu trúc liên kết cơ bản của trang web. Mẫu này dựa trên cấu trúc liên kết của các liên kết có hoặc không có mô tả của các liên kết. Nó có thể được sử dụng để phân loại các trang web và rất hữu ích cho việc tạo ra các thông tin giống nhau và mối quan hệ khác nhau giữa các trang web. Khai thác cấu trúc web có thể được quyền tìm ra các trang web, đó 6 là các tổ chức trang web cho các chủ đề đặc biệt và có nhiều liên kết đến các trang web khác có liên quan dựa trên chủ đề này.  Khai thác sử dụng web là khai thác web log, nơi mà các chuỗi của truy cập trang web được thực hiện bởi người sử dụng trang web khác nhau trong một khoảng thời gian, được ghi nhận thông qua một máy chủ. Khai thác sử dụng web nghĩa là dữ liệu được tạo ra bằng cách quan sát phiên duyệt web hoặc hành vi truy cập của người dùng. Khai thác sử dụng web, tìm thấy mối quan hệ khác nhau giữa người sử dụng truy cập. Ví dụ, nó có thể được phát hiện ra rằng: 90% số khách hàng truy cập trang web với URL/sản phẩm/product.html, cũng truy cập trang /contact /contact.html. Thông tin này tiết lộ rằng hai trang này là liên quan chặt chẽ và có thể được tổ chức lại với nhau để cung cấp người sử dụng với một lộ trình duyệt dễ dàng hơn. Tất cả hành vi người sử dụng trên mỗi máy chủ web có thể được chiết xuất từ web log. Kỹ thuật khai thác sử dụng web giải quyết vấn đề phát hiện hành vi sử dụng web của người dùng từ các hoạt động truy cập web của họ. Sử dụng dữ liệu web là có tính chất tuần tự, tức là, mỗi phần dữ liệu là một danh sách thứ tự / chuỗi các trang web truy cập. Các kỹ thuật khai thác sử dụng web bao gồm khai thác mẫu chuỗi, khai thác luật kết hợp… Khai thác luật kết hợp là một kỹ thuật khai thác dữ liệu tìm ra các kết hợp mạnh hay mối quan hệ tương quan giữa các dữ liệu. Cho một tập hợp các giao dịch (tương tự như bản ghi cơ sở dữ liệu), trong đó mỗi giao dịch bao gồm các phần tử, luật kết hợp X → Y, trong đó X và Y là tập hợp các phần tử và X ∩ Y = ∅. Độ hỗ trợ của luật này được định nghĩa là tỷ lệ phần trăm của các giao dịch có chứa các bộ X ∪ Y, trong khi độ tin cậy của nó là tỷ lệ phần trăm của các giao dịch “X” cũng chứa các phần tử trong “Y”. Trong khai thác luật kết hợp, tất cả các phần tử với độ hỗ trợ cao hơn hỗ trợ cực tiểu quy định được gọi là tập phổ biến. Một tập phổ biến X được gọi là i-tập