Tài liệu Khai thác k-mẫu tuần tự phổ biến dựa trên roaring bitmap

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM LÊ HỮU NHƠN KHAI THÁC K-MẪU TUẦN TỰ PHỔ BIẾN DỰA TRÊN ROARING BITMAP LUẬN VĂN THẠC SĨ Chuyên ngành: Công Nghệ Thông Tin Mã 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 LÊ HỮU NHƠN KHAI THÁC K-MẪU TUẦN TỰ PHỔ BIẾN DỰA TRÊN ROARING BITMAP LUẬN VĂN THẠC SĨ Chuyên ngành: Công Nghệ Thông Tin Mã ngành: 60480201 CÁN BỘ HƯỚNG DẪN KHOA HỌC: PGS. TS. LÊ HOÀI BẮC 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: PGS. TS LÊ HOÀI BẮC Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Công nghệ TP. HCM (HUTECH) 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: TT Họ và Tên Chức danh Hội đồng 1 PGS. TS. Lê Trọng Vĩnh Chủ tịch 2 GS. TSKH. Hoàng Văn Kiếm Phản biện 1 3 TS. Võ Đình Bảy Phản biện 2 4 PGS. TS. Đỗ Phúc Ủy viên 5 TS. Nguyễn Văn Mùi Ủy viên, Thư ký Xác nhận của Chủ tịch Hội đồng đánh giá Luận văn sau khi Luận văn đã 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..… tháng….. năm 2015 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên : Lê Hữu Nhơn Giới tính : Nam. Ngày, tháng, năm sinh : 08 – 08 – 1974 Nơi sinh : Sài Gòn. Chuyên ngành : Công Nghệ Thông Tin MSHV : 1341860015 I- Tên đề tài: KHAI THÁC K MẪU TUẦN TỰ PHỔ BIẾN DỰA TRÊN ROARING BITMAP II- Nhiệm vụ và nội dung: - Nghiên cứu lĩnh vực khám phá tri thức và khai thác mẫu tuần tự trên CSDL chuỗi. - Nghiên cứu và triển khai thuật toán khai thác k mẫu tuần tự phổ biến TKS. - Nghiên cứu và triển khai phương pháp nén chuỗi bit Roaring bitmap. - Áp dụng Roaring bitmap vào để cải tiến thuật toán TKS. III- Ngày giao nhiệm vụ: 18 – 08 – 2014 IV- Ngày hoàn thành nhiệm vụ: 14 – 03 – 2015 V- Cán bộ hướng dẫn: Phó Giáo Sư . Tiến Sĩ. Lê Hoài Bắc CÁN BỘ HƯỚNG DẪN KHOA QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) (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ũng như các trích dẫn hay tài liệu học thuật tham khảo đã được cảm ơn đến tác giả 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 ii LỜI CÁM ƠN Trước hết, cho tôi được gửi lời cảm ơn đến sự hướng dẫn và giúp đỡ tận tình của PGS.TS. Lê Hoài Bắc. Xin cảm ơn TS. Cao Tùng Anh cùng các bạn Trương Quốc Dũng, Châu Nguyễn Nhật Thanh đã sát cánh và cung cấp cho tôi những kiến thức quí báu trong suốt thời gian học tập và nghiên cứu thực hiện luận văn. Tôi cũng xin gởi lời cảm ơn đến gia đình, bạn bè và những người thân đã luôn quan tâm và giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu hoàn thành luận văn này. Luận văn không thể tránh khỏi những sai sót, rất mong nhận được ý kiến đóng góp của mọi người cho luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn. TP. Hồ Chí Minh, tháng 04 năm 2015 LÊ HỮU NHƠN iii TÓM TẮT Khai thác mẫu tuần tự là một phần quan trọng của khai thác dữ liệu với các ứng dụng rộng rãi. Tuy nhiên, việc tinh chỉnh thông số minsup trong các thuật toán khai thác mẫu tuần tự để tạo ra đủ số mẫu mong muốn là rất khó khăn và tốn thời gian. Để giải quyết vấn đề này, người ta đã đề xuất xác định lại vấn đề khai thác mẫu tuần tự như là khai thác k mẫu tuần tự phổ biến, với k là số mẫu tuần tự được tìm ra (được trả về) và được thiết lập bởi người dùng. Thuật toán tốt nhất hiện nay để giả quyết vấn đề này là TKS (Top-K Sequential pattern mining) [15]. Tuy nhiên, thuật toán này sử dụng bit vector có kích thước cố định cho mỗi item trong CSDL chuỗi (có chiều dài bằng tổng số itemset trong CSDL), do đó nó sử dụng nhiều bộ nhớ để lưu trữ và tiêu tốn nhiều thời gian để thực thi các phép giao bit vector. Để cải tiến thuật toán, luận văn này đề xuất sử dụng Roaring bitmap [16] thay thế cho bit vector có kích thước cố định trong TKS nhằm mục đích làm giảm bộ nhớ được sử dụng và giảm thời gian thực thi các phép giao bit vector. Kết quả thực nghiệm cho thấy thuật toán cải tiến có chi phí vượt trội về thời gian thực thi và hiệu quả sử dụng bộ nhớ so với thuật toán TKS gốc, đặc biệt là trên các cơ sở dữ liệu lớn. iv ABSTRACT Sequential pattern mining is a important part of data minning with wide applications. However, fine-tuning the minsup parameter of sequential pattern mining algorithms to generate enough patterns is difficult and time-consuming. To address this problem, it was proposed to redefine the problem of mining sequential patterns as the problem of mining the top-k sequential patterns, where k is the number of sequential patterns to be found and is set by the user. The current best algorithm for this problem is TKS (Top-K Sequential pattern mining) [15]. However, this algorithm uses a fixed size bit vector for each item in sequence database (its length is equal to total number of itemsets in the database), so it uses much memory to store and spend much time to compute bit vector intersections. To improve the performance of the algorithm, this paper proposes to use Roaring bitmap [16] to replace fixed size bit vectors in TKS in order to use less memory and reduce the execution time of bit vector intersections. The experimental result show that the improved algorithm outperforms original TKS algorithm by more than an order of magnitude in execution time and memory, especially on large database. v MỤC LỤC TÓM TẮT.................................................................................................................. iii ABSTRACT ...............................................................................................................iv DANH MỤC CÁC TỪ VIẾT TẮT ..........................................................................vii DANH MỤC CÁC BẢNG...................................................................................... viii DANH MỤC CÁC HÌNH..........................................................................................ix CHƯƠNG 1 MỞ ĐẦU ...............................................................................................1 1.1 LÝ DO CHỌN ĐỀ TÀI..................................................................................1 1.2 Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN ....................................................2 1.3 MỤC ĐÍCH CỦA ĐỀ TÀI.............................................................................3 1.4 ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU ...............................................3 1.5 PHƯƠNG PHÁP NGHIÊN CỨU ..................................................................3 CHƯƠNG 2 TỔNG QUAN VỀ KHAI THÁC MẪU TUẦN TỰ .............................4 2.1 GIỚI THIỆU...................................................................................................4 2.2 PHÁT BIỂU BÀI TOÁN VÀ KÝ HIỆU .......................................................5 2.3 CÁC THUẬT TOÁN KHAI THÁC MẪU TUẦN TỰ .................................6 2.3.1 Các thuật toán dựa trên Apriori ............................................................7 2.3.2 Các kỹ thuật phát triển mẫu ................................................................11 2.3.3 Các kỹ thuật loại trừ sớm ....................................................................20 2.3.4 Các thuật toán lai.................................................................................25 2.4 CÁC ỨNG DỤNG CỦA KHAI THÁC MẪU TUẦN TỰ ..........................30 CHƯƠNG 3 KHAI THÁC K MẪU TUẦN TỰ PHỔ BIẾN DỰA TRÊN ROARING BITMAP..........................................................................................33 3.1 GIỚI THIỆU.................................................................................................33 vi 3.2 THUẬT TOÁN TKS (Top-K Sequential pattern mining) ...........................34 3.2.1 Cơ sở dữ liệu bitmap dọc (vertical bitmap database) .........................34 3.2.2 Thủ tục tạo ứng viên SPAM Search ...................................................34 3.2.3 Các chiến lược tăng hiệu quả khai thác dữ liệu ..................................37 3.2.4 Nhận xét ..............................................................................................43 3.3 ROARING BITMAP....................................................................................43 3.3.1 Giới thiệu ............................................................................................43 3.3.2 Mô tả Roaring bitmap .........................................................................44 3.4 ÁP DỤNG ROARING BITMAP VÀO THUẬT TOÁN TKS ....................52 CHƯƠNG 4 THỰC NGHIỆM – ĐÁNH GIÁ KẾT QUẢ .......................................55 4.1 BỘ DỮ LIỆU................................................................................................56 4.2 ĐÁNH GIÁ THỰC NGHIỆM .....................................................................56 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 vii DANH MỤC CÁC TỪ VIẾT TẮT Ký hiệu, viết tắt Ý nghĩa tiếng Việt Ý nghĩa tiếng anh CSDL Cơ sở dữ liệu Database Itemset Tập mục Itemset TID Giao tác Transaction Item Database PMAP Bản đồ thứ tự ưu tiên Precedence Map GPU Bộ xử lý đồ họa Graphics Processing Unit Item Mục Item viii DANH MỤC CÁC BẢNG Bảng 2.1 Cơ sở dữ liệu chuỗi D1.................................................................................6 Bảng 2.2 Cơ sở dữ liệu chuỗi D2.................................................................................7 Bảng 2.3 Cơ sở dữ liệu chuỗi D3.................................................................................7 Bảng 2.4 S-Matrix để xây dựng chuỗi 2-sequences từ CSDL ở bảng 2.3 ................13 Bảng 2.5 Phát sinh mẫu từ S-Matrix .........................................................................13 Bảng 2.6 Chạy PrefixSpan trên CSDL ở bảng 2.3....................................................15 Bảng 2.7 Các mẫu phổ biến của CSDL truy cập web từ bảng 2.2............................16 Bảng 2.8 CSDL và phần ở mức thứ nhất của bảng 2.3.............................................22 Bảng 2.9 CSDL chuỗi ví dụ cho SPADE, biến đổi từ CSDL chuỗi ở bảng 2.2 .......26 Bảng 3.1 CSDL chuỗi D4 ..........................................................................................33 Bảng 3.2 CSDL bitmap dọc được xây dựng từ CSDL chuỗi D 4 ..............................34 Bảng 3.3 Cấu trúc dữ liệu PMAP được xây dựng từ CSDL chuỗi D 4 ......................42 Bảng 4.1 Liệt kê đặc tính của các bộ dữ liệu thực nghiệm .......................................56 Bảng 4.2 Kết qủa thực nghiệm ứng với k = 1000, 2000 và 3000 .............................56 ix DANH MỤC CÁC HÌNH Hình 2.1 Cây từ điển biểu diễn các chuỗi, với đường nét nhạt là mở rộng theo chuỗi và nét đậm là mở rộng theo itemset..........................................................10 Hình 2.2 Khai thác cây WAP sử dụng thuật toán WAP-mine..................................17 Hình 2.3 Cây FS và bảng đầu liên kết cho các web log của bảng 2.2 ......................18 Hình 2.4 Chuỗi ứng viên với itemset có kích thước 1 và itemset có kích thước 2...24 Hình 2.5 Dàn được tạo ra bởi các chuỗi phổ biến cực đại ........................................26 Hình 2.6 Các lớp tương đương {[a]θ1, [b]θ1, [e]θ1} sinh bởi quan hệ θk trên S ....27 Hình 2.7 Khai thác cây trong thuật toán PLWAP.....................................................29 Hình 3.1 Thuật toán SPAM.......................................................................................35 Hình 3.2 Thủ tục tạo ứng viên ..................................................................................35 Hình 3.3 Mở rộng s-extension...................................................................................36 Hình 3.4 Mở rộng i-extension ...................................................................................36 Hình 3.5 Thuật toán TKS ..........................................................................................38 Hình 3.6 Thủ tục tạo ứng viên đã được sửa đổi ........................................................39 Hình 3.7 Thủ tục SAVE ............................................................................................39 Hình 3.8 Cấu trúc của Roaring bitmap .....................................................................44 Hình 3.9 So sánh bộ nhớ được sử dụng cho mảng và bitmap (nguồn http://www.elasticsearch.org/blog/frame-of-reference-and-roaring-bitmaps/) ..45 Hình 3.10 Minh họa phép OR giữa hai Roaring bitmap khi chỉ mục cấp 1 không bằng nhau.................................................................................................47 Hình 3.11 Thuật toán 1 - Thủ tục tính phép giao giữa hai container bitmap ............48 Hình 3.12 Thuật toán 2 - Thuật toán được tối ưu để chuyển đổi vị trí các bit 1 trong một bitmap thành một danh sách các số nguyên.......................................49 Hình 3.13 Thuật toán 3 – Thủ tục tính toán phép giao của hai container bitmap.....49 x Hình 3.14 Thuật toán 4 – Thuật toán được tối ưu để tính toán phép hội của nhiều Roaring bitmap .........................................................................................51 Hình 3.15 Mô tả cách thực hiện bước s-extension ngắn gọn....................................54 Hình 4.1 Giao diện chương trình ..............................................................................55 Hình 4.2 Biểu đồ so sánh thời gian thực hiện (a) và sử dụng bộ nhớ (b) của 2 thuật toán sử dụng CSDL BmsWebView1.........................................................57 Hình 4.3 Biểu đồ so sánh thời gian thực hiện (a) và sử dụng bộ nhớ (b) của 2 thuật toán sử dụng CSDL Levithan ....................................................................57 Hình 4.4 Biểu đồ so sánh thời gian thực hiện (a) và sử dụng bộ nhớ (b) của 2 thuật toán sử dụng CSDL Bible..........................................................................57 Hình 4.5 Biểu đồ so sánh thời gian thực hiện (a) và sử dụng bộ nhớ (b) của 2 thuật toán sử dụng CSDL FIFA..........................................................................58 Hình 4.6 Biểu đồ so sánh thời gian thực hiện (a) và sử dụng bộ nhớ (b) của 2 thuật toán sử dụng CSDL Kosarak .....................................................................58 1 CHƯƠNG 1 MỞ ĐẦU 1.1 LÝ DO CHỌN ĐỀ TÀI Trong những năm gần đây, với sự phát triển nhanh chóng của công nghệ thông tin và sự phổ biến của Internet thì khối lượng dữ liệu được tạo ra và thu thập lại từ các ứng dụng dưới nhiều dạng khác nhau ngày càng trở nên đồ sộ. Sự đa dạng và phong phú của khối lượng dữ liệu này đã hình thành nên nhiều mô hình dữ liệu khác nhau như mô hình dữ liệu giao tác (transaction), mô hình dữ liệu chuỗi (sequence), mô hình dòng dữ liệu (data stream), chuỗi thời gian (time-series)... Với mô hình dữ liệu chuỗi, sự kiện hoặc dữ liệu nói chung tồn tại theo một chuỗi có trật tự thời gian nhưng không nhất thiết phải gắn liền với một khái niệm thời gian cụ thể. Ví dụ chuỗi các mặt hàng đã mua sắm của các khách hàng tại một cửa hàng, chuỗi truy cập web, chuỗi di truyền trong sinh học, chuỗi sự kiện trong khoa học, dữ liệu điều trị y tế, các mẫu gọi điện thoại, dữ liệu về thị trường và chứng khoán… Bản chất của dữ liệu chuỗi là có tính thứ tự và mô hình dữ liệu chuỗi thể hiện rõ rệt mối quan hệ xuyên thời gian của dữ liệu nên việc áp dụng khai thác mẫu tuần tự trên mô hình dữ liệu này sẽ mang lại nhiều tri thức tiềm ẩn quí giá có ý nghĩa thiết thực và có tính dự báo, dự đoán rất cao. Khai thác mẫu tuần tự (sequential pattern mining) trên mô hình dữ liệu chuỗi là một phần quan trọng của khai thác dữ liệu và được ứng dụng rộng rãi trong nhiều lĩnh vực như y khoa, giáo dục đào tạo, kinh tế, khoa học, xã hội…Chính vì vậy, nhiều nghiên cứu đã được thực hiện và nhiều thuật toán đã được đề xuất trong lĩnh vực này. Trong đó, thuật toán TKS (Top-K Sequential pattern mining) được đánh giá cao bởi vì chi phí thực hiện thấp hơn nhiều lần so với các thuật toán khác trong việc khai thác k mẫu tuần tự phổ biến [15]. Tuy nhiên, thuật toán này sử dụng CSDL bitmap dọc (vertical bitmap database) [4] để trình bày dữ liệu, với mỗi item là một bit vector có kích thước cố định (có chiều dài bằng tổng số các itemsets trong CSDL chuỗi) làm dư thừa các bit 0 không cần thiết nên khi áp dụng trên các CSDL 2 chuỗi có số lượng itemsets lớn thì tốc độ sẽ rất chậm do phải tiêu tốn rất nhiều thời gian để thực hiện các phép giao trên các bit vector này và tốn rất nhiều bộ nhớ để lưu trữ chúng. Để nâng cao hiệu quả khai thác các mẫu tuần tự, luận văn này đề xuất một phương pháp tiếp cận khác là phương pháp tiếp cận dựa trên Roaring bitmap [16]. Phương pháp này đặc biệt hiệu quả khi áp dụng trên các CSDL chuỗi lớn với chi phí vượt trội về thời gian thực thi và sử dụng bộ nhớ so với thuật toán TKS. 1.2 Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN Khai thác mẫu tuần tự là một phần quan trọng của khai thác dữ liệu với các ứng dụng rộng rãi như phân tích dữ liệu sinh học, dữ liệu y tế, dữ liệu e-learning, phân tích truy cập web theo thứ tự thời gian, phân tích sự thực thi của chương trình, phân tích thói quen mua sắm của khách hàng, phân tích các thí nghiệm khoa học... Từ đó dự đoán được hành vi của các đối tượng nghiên cứu. Ví dụ như trong lĩnh vực y khoa, dựa trên một chuỗi các triệu chứng bệnh mà chúng ta có thể chẩn đoán được bệnh cho bệnh nhân đó; Trong lĩnh vực kinh tế, dựa trên một chuỗi các biến động của thị trường mà chúng ta có thể dự đoán được xu thế sắp tới của nền kinh tế để có kế hoạch kinh doanh phù hợp; Trong lĩnh vực khoa học, dựa trên một chuỗi các hiện tượng tự nhiên mà chúng ta có thể dự đoán được các thảm họa thiên nhiên sắp xảy ra, từ đó có các biện pháp ứng phó thích hợp và kịp thời… Do đó, nghiên cứu về khai thác mẫu tuần tự có ý nghĩa rất quan trọng. Bên cạnh đó, sự bùng nổ về thông tin đã tạo ra các tập dữ liệu khổng lồ và các tập dữ liệu này ngày càng phình to ra. Việc áp dụng các thuật toán khai thác mẫu tuần tự hiện nay vào khai thác các tập dữ liệu này sẽ cho ra kết quả rất chậm, thậm chí là không thể cho ra kết quả do hạn chế về tài nguyên phần cứng (chẳng hạn như “out of memory”). Vì vậy, việc nghiên cứu để cho ra thuật toán trong luận văn này nhằm nâng cao hiệu quả khai thác dữ liệu, giảm thời gian thực thi và giảm chi phí phần cứng (bằng cách sử dụng tối ưu tài nguyên phần cứng) là rất cấp thiết. Trong thời buổi kinh tế thị trường hiện nay, việc tổng hợp ra được những thông tin hữu ích và tri thức từ các tập dữ liệu khổng lồ này càng có ý nghĩa hơn bao giờ 3 hết, nó đóng vai trò chìa khóa thành công cho sự phát triển của các tổ chức và cá nhân. Các thông tin tìm được có thể được vận dụng để cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu, cắt giảm chi phí, tăng thời gian phát triển và tối ưu hóa sản phẩm, đồng thời hỗ trợ con người đưa ra những quyết định đúng và hợp lý hơn. Việc nghiên cứu và ứng dụng thuật toán trong luận văn này giúp chúng ta có được những thông tin hữu ích một cách nhanh chóng và kịp thời. Điều này tạo nên ưu thế rất lớn trong việc phát triển và cạnh tranh. 1.3 MỤC ĐÍCH CỦA ĐỀ TÀI Thay thế bit vector có kích thước cố định được sử dụng trong thuật toán TKS bằng Roaring bitmap nhằm làm giảm dung lượng bộ nhớ được sử dụng để lưu trữ các bit vector này và giảm thời gian thực thi phép giao giữa chúng. Từ đó, có thể cải thiện được đáng kể hiệu suất của thuật toán về thời gian thi hành và hiệu quả sử dụng bộ nhớ, đặc biệt là trên các CSDL chuỗi lớn. 1.4 ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU Đối tượng nghiên cứu là CSDL chuỗi và bit vector (chuỗi bit hay còn gọi là bitmap – bitset) nhưng phạm vi nghiên cứu tập trung vào thuật toán khai thác k mẫu tuần tự phổ biên TKS và phương pháp nén chuỗi bit Roaring bitmap. 1.5 PHƯƠNG PHÁP NGHIÊN CỨU - Tiến hành thu thập và đọc các tài liệu có liên quan đến đề tài. - Nghiên cứu tổng quan về cơ sở dữ liệu chuỗi và các khái niệm có liên quan. - Nghiên cứu thuật toán khai thác k mẫu tuần tự phổ biến TKS. - Nghiên cứu phương pháp nén chuỗi bit Roaring bitmap. - Nghiên cứu áp dụng phương pháp tiếp cận dựa trên Roaring bitmap vào thuật toán TKS. - Xây dựng chương trình demo và đánh giá kết quả đạt được. 4 CHƯƠNG 2 TỔNG QUAN VỀ KHAI THÁC MẪU TUẦN TỰ 2.1 GIỚI THIỆU Trong cuộc sống của chúng ta, dữ liệu chuỗi rất phổ biến và tồn tại ở khắp mọi nơi. Chẳng hạn như chuỗi mua sắm của khách hàng, dữ liệu điều trị y tế, dữ liệu liên quan tới các thảm họa tự nhiên, dữ liệu về thị trường và chứng khoán, các mẫu gọi điện thoại, chuỗi truy cập web, chuỗi DNA, chuỗi thực thi của chương trình…Trong các chuỗi này, có thể có sự tồn tại của các chuỗi có ý nghĩa và việc phát hiện các chuỗi con phổ biến (toàn bộ hoặc một phần các chuỗi con được sắp xếp thứ tự) có thể mang lại nhiều tri thức có ích. Từ đó, khai thác mẫu tuần tự đã được phát sinh như là một kỹ thuật khám phá các chuỗi con phổ biến. Vấn đề khai thác mẫu tuần tự được giới thiệu lần đầu tiên bởi Agrawal và Srikant năm 1995 [2] và sau đó đã thu hút nhiều nghiên cứu khác như [4], [5], [6], [7], [9], [12]…Trong đó, mẫu tuần tự (sequential pattern) là một chuỗi các itemset xuất hiện phổ biến có trình tự, tất cả các item trong cùng một itemset được giả sử là chúng có cùng tại thời điểm giao dịch hoặc chúng có trong cùng một khoảng thời gian giao dịch. Thông thường tất cả các giao dịch của một khách hàng được gắn kết với nhau theo trình tự thời gian và được xem là một chuỗi. Khai thác mẫu tuần tự là khám phá các chuỗi con phổ biến (được gọi là mẫu) trong một CSDL chuỗi. Một CSDL chuỗi lưu trữ một hoặc nhiều bản ghi và tất cả các bản ghi này là những chuỗi các sự kiện có thứ tự, có thể gắn với một khái niệm thời gian cụ thể hoặc không (ví dụ như chuỗi truy cập web và chuỗi DNA). Mỗi bản ghi trong CSDL chuỗi có thể có độ dài khác nhau và mỗi sự kiện (itemset) trong một chuỗi có thể có một hay nhiều item (ví dụ các chuỗi gen có độ dài tối thiểu là vài trăm nhưng độ dài tối đa lên đến hàng trăm nghìn). Khai thác mẫu tuần tự là bài toán quan trọng được ứng dụng rộng rãi, bao gồm: phân tích thói quen mua sắm của khách hàng, mẫu truy cập web, các thí nghiệm khoa học, các thảm họa thiên nhiên, các kết cấu của protein, chẩn đoán bệnh… 5 Thuật toán khai thác mẫu tuần tự trên CSDL chuỗi là đi tìm những mẫu xuất hiện lặp lại (được gọi là chuỗi phổ biến) để tìm kiếm mối liên quan giữa các item khác nhau, hoặc giữa các sự kiện tiềm ẩn trong dữ liệu phục vụ cho các mục đích như các chiến dịch tiếp thị, tái tổ chức kinh doanh, dự báo và lập kế hoạch… 2.2 PHÁT BIỂU BÀI TOÁN VÀ KÝ HIỆU Cho I = {i1, i2,…,im} là một tập gồm m phần tử (được gọi là item). Một itemset là tập khác rỗng và không có thứ tự của các item. itemset i ký hiệu là (i1, i2, …, ik ) với mỗi ij là một item. Không mất tính tổng quát, giả sử các item trong itemset được sắp theo thứ tự tăng dần. Một chuỗi (sequence) là một danh sách có thứ tự những itemset. Chuỗi s được ký hiệu là s1, s2,…, sn hoặc s1→s2→…→sn với mỗi si là một itemset, n là số lượng các itemset. Kích thước của chuỗi bằng số lượng itemset có trong chuỗi. Chiều dài của chuỗi là tổng số item có trong chuỗi, ký hiệu là l = ∑ . Chuỗi có chiều dài k còn được gọi là k-sequence. Ví dụ s = (b)(ac) là một 3-sequence có kích thước n=2. Chuỗi β = b1, b2, …, bm được gọi là chuỗi con của chuỗi α = a1, a2,…, an hay α là chuỗi cha của β, ký hiệu β ⊆ α, nếu tồn tại những số nguyên 1≤ j1 < j2 < … < jn ≤ m sao cho b1⊆ aj1, b2⊆ aj2,…, bm⊆ ajm. Ví dụ chuỗi (b)(ac) là chuỗi con của (ab)(e)(acd) vì b ⊆ ab, ac ⊆ acd và thứ tự của các itemset vẫn được bảo tồn. Tuy nhiên, chuỗi (ab)(e) không phải là chuỗi con của chuỗi (abe) và ngược lại. Cơ sở dữ liệu chuỗi: Cơ sở dữ liệu chuỗi là một tập hợp các bộ dữ liệu có dạng (sid, s), trong đó sid là định danh của chuỗi và s là chuỗi các itemset. Mẫu: Mẫu là một chuỗi con của một chuỗi dữ liệu. Mỗi itemset trong một mẫu còn được gọi là một thành phần (element). Độ hỗ trợ (support): Cho CSDL chuỗi D, mỗi chuỗi có một chỉ số định danh duy nhất. Độ hỗ trợ tuyệt đối của một mẫu tuần tự f là tổng số chuỗi trong D có chứa f, ký hiệu supD (f) = |{Si ∈ D | f ⊆ Si}|. Độ hỗ trợ tương đối của f là tỉ lệ phần 6 trăm các chuỗi trong D chứa f. Ở đây, mức hỗ trợ tuyệt đối hoặc tương đối sẽ được sử dụng chuyển đổi qua lại, kí hiệu là sup(f). Mẫu tuần tự: Cho trước ngưỡng hỗ trợ tối thiểu minSup xác định bởi người dùng. Một mẫu f được coi là phổ biến nếu độ hỗ trợ của nó lớn hơn hoặc bằng minSup: sup(f) ≥ minSup, khi đó f được gọi là mẫu tuần tự. Ví dụ: Cho CSDL chuỗi D1 như bảng 2.1 có tập các item phân biệt là {a, b, c} và minSup là 2. Xét chuỗi s1 = (ab)(b)(b)(ab)(b)(ac), chuỗi s1 có 6 itemset là: (ab), (b), (b), (ab), (b), (ac) và có 9 item. Vậy s1 có kích thước là 6 và có độ dài là 9. Trong chuỗi s1, item a xuất hiện ba lần nhưng độ hỗ trợ của item a chỉ được tính là 1 đối với chuỗi s1 đó. Chuỗi p = (ab)(c) là một chuỗi con của chuỗi s1, vì vậy chuỗi con p còn được gọi là mẫu. Trong D1, chỉ có chuỗi s1, s2 và s5 có chứa mẫu p, vậy độ hỗ trợ của mẫu p là 3. Vì sup(p) > minSup nên p là một mẫu tuần tự. Bảng 2.1 Cơ sở dữ liệu chuỗi D1 SID Sequences 1 〈 (ab)(b)(b)(ab)(b)(ac)〉 2 〈 (ab)(bc)(bc)〉 3 〈 (b)(ab)〉 4 〈 (b)(b)(bc)〉 5 〈 (ab)(ab)(ab)(a)(bc)〉 Khai thác mẫu tuần tự: là tìm một tập đầy đủ các chuỗi con phổ biến (mẫu tuần tự) trong CSDL chuỗi có độ hỗ trợ lớn hơn hoặc bằng ngưỡng minSup được xác định bởi người dùng. 2.3 CÁC THUẬT TOÁN KHAI THÁC MẪU TUẦN TỰ Phần này trình bày tổng quan về các thuật toán cùng với ví dụ minh họa cho từng thuật toán. Phần 2.3.1 trình bày các thuật toán dựa trên Apriori, phần 2.3.2 trình bày các thuật toán dựa trên phát triển mẫu, phần 2.3.3 trình bày các thuật toán dựa trên kỹ thuật loại trừ sớm và phần 2.3.4 bàn về các thuật toán lai ghép nhiều kỹ thuật. Các thuật toán khai thác chuỗi mà mỗi itemset là một item được thảo luận theo CSDL của bài toán 1 (bảng 2.2), còn những thuật toán khai thác chuỗi mà có