Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Khai thác mẫu phổ biến và luật từ cơ sở dữ liệu chuỗi (tóm tắt)...

Tài liệu Khai thác mẫu phổ biến và luật từ cơ sở dữ liệu chuỗi (tóm tắt)

.PDF
28
784
98

Mô tả:

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TRẦN MINH THÁI KHAI THÁC MẪU PHỔ BIẾN VÀ LUẬT TỪ CƠ SỞ DỮ LIỆU CHUỖI Chuyên ngành: Khoa học máy tính Mã số chuyên ngành: 62 48 01 01 TÓM TẮT LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Tp. Hồ Chí Minh, năm 2016 Công trình được hoàn thành tại Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự Nhiên - Đại học Quốc Gia Thành phố Hồ Chí Minh Người hướng dẫn khoa học: PGS. TS. LÊ HOÀI BẮC Phản biện 1: PGS. TS. Hồ Bảo Quốc Phản biện 2: PGS. TS. Nguyễn Đình Thuân Phản biện 3: TS. Nguyễn An Tế Phản biện độc lập 1: PGS. TS. Đỗ Trung Tuấn Phản biện độc lập 2: PGS. TS. Lê Anh Cường Luận án sẽ được bảo vệ trước Hội đồng chấm luận án họp tại vào lúc giờ ngày tháng năm Có thể tìm hiểu luận án tại thư viện: - Thư viện Khoa học Tổng hợp Thành phố Hồ Chí Minh - Thư viện Trường Đại học Khoa học Tự Nhiên TÓM TẮT LUẬN ÁN Hiện tại, khai thác dữ liệu chuỗi là một trong những hướng chính trong lĩnh vực khai thác dữ liệu và đang được nhiều nhà khoa học tập trung nghiên cứu. Việc khai thác này có tính ứng dụng cao trong thực tiễn, như: dự báo xu hướng, phân tích thói quen hay hành vi khách hàng, dự đoán thiên tai, ngăn ngừa xâm nhập hệ thống, hoặc trong việc phân tích hay phát hiện các dị thường trong cấu trúc protein, DNA, xử lý văn bản, v.v… Tuy nhiên, vấn đề khai thác dữ liệu chuỗi đang đối mặt với hai thách thức chính. Thách thức thứ nhất là thời gian khai thác và thứ hai là vấn đề rút trích được tập luật tuần tự không dư thừa trong số các luật được sinh ra từ mẫu tuần tự. Để giải quyết bài toán này, ngoài việc thiết kế mô hình dữ liệu phù hợp, cùng với việc phát hiện, tỉa mẫu nhằm giảm bớt số lượng mẫu không cần thiết và rút trích được tập luật đầy đủ và không dư thừa là một trong những yếu tố chính dẫn đến thành công. Đây chính là nội dung nghiên cứu của luận án. Trong đó, luận án tập trung vào việc giải quyết vấn đề giảm thời gian trong quá trình khai thác mẫu tuần tự bằng cách xây dựng cấu trúc dữ liệu nén dạng vector kết hợp với các thông tin cần thiết giúp cho việc kiểm tra và loại trừ mẫu dư thừa một cách hợp lý và nhanh chóng. Tiếp theo đó, luận án cũng trình bày cách thức khai thác hiệu quả luật không dư thừa, kết hợp với kỹ thuật phát hiện sớm và dừng sinh luật cho những mẫu không tiềm năng. Các đề xuất tập trung vào việc giảm thiểu thời gian khai thác, chi phí tính toán và tối ưu không gian lưu trữ trong quá trình khai thác dữ liệu chuỗi. Nội dung luận án bao gồm hai phần và bốn chương được tóm tắt như sau: Phần mở đầu Nội dung của phần này trình bày tóm tắt về tính cấp thiết của luận án, mục tiêu, phạm vi nghiên cứu và kết quả đạt được của luận án. 1 1. Giới thiệu Chuỗi (sequence) là danh sách có thứ tự các sự kiện hay ký hiệu. Dữ liệu dạng này tồn tại trong hầu hết các hoạt động hay những thông tin mang tính thứ tự. Cơ sở dữ liệu (CSDL) chuỗi (sequence database) bao gồm danh sách các chuỗi. Ví dụ: chuỗi các trang web được viếng thăm của một người dùng được thể hiện theo thứ tự thời gian truy cập, chuỗi các sản phẩm được mua bởi khách hàng tại siêu thị hay cửa hàng bán lẻ, chuỗi các triệu chứng quan sát được của bệnh nhân tại một bệnh viện, v.v... Mục đích chính của việc khai thác dữ liệu chuỗi là giúp cho việc dự báo sự kiện kế tiếp dựa trên những sự kiện quan sát được trước đó. Ví dụ, nếu một khách hàng đã mua lần lượt các mặt hàng A, B và C trong một cửa hàng thì mặt hàng kế tiếp họ sẽ mua là gì. Nhờ vậy, cửa hàng này có thể chủ động trong việc quản lý danh sách các mặt hàng dựa vào xu hướng của khách hàng. Vấn đề khai thác dữ liệu chuỗi có rất nhiều ứng dụng trong các lĩnh vực như phân tích thói quen hay hành vi mua sắm của khách hàng, phân tích mẫu truy cập web, phân tích các thí nghiệm khoa học, chuẩn đoán bệnh, phân tích những bất thường trong cấu trúc protein và DNA, lĩnh vực viễn thông, hay dự báo và ngăn ngừa thảm hoạ thiên nhiên, v.v… Khai thác dữ liệu chuỗi thường được chia làm hai giai đoạn chính bao gồm: giai đoạn khai thác mẫu tuần tự và giai đoạn khai thác luật tuần tự. 2. Tính cấp thiết của luận án Khai thác CSDL chuỗi có nhiều ứng dụng trong thực tế. Tuy nhiên, thách thức chính của bài toán khai thác trên CSDL chuỗi là thời gian khai thác và rút trích được tập luật tuần tự không dư thừa từ số lượng lớn các luật được sinh ra từ tập mẫu tuần tự. Các đóng góp cho bài toán khai thác mẫu tuần tự liên chuỗi còn hạn chế. Cho đến thời điểm hiện tại chỉ có đóng góp của Wang và Lee (khai thác mẫu tuần tự liên chuỗi năm 2009) và của Wang và đồng sự (khai thác mẫu tuần tự 2 liên chuỗi đóng năm 2013). Hơn nữa, bài toán này có độ phức tạp cao hơn bài toán khai thác mẫu tuần tự. Cho nên, cần phải được tiếp tục nghiên cứu vấn đề này. Bên cạnh đó, nghiên cứu phương pháp loại bỏ các luật dư thừa cũng rất có ý nghĩa. Ngoài ra, việc kết hợp hai giai đoạn khai thác mẫu và luật cũng có ý nghĩa góp phần làm giảm các bước không cần thiết, cố gắng khai thác và tận dụng được những thông tin cần thiết trong mỗi giai đoạn, hạn chế quá trình khai thác lại và trùng lắp trong khai thác. 3. Mục tiêu, đối tượng, phạm vi và nội dung nghiên cứu của luận án Mục tiêu của luận án tập trung vào nghiên cứu bài toán khai thác mẫu tuần tự và luật tuần tự từ CSDL chuỗi. Dữ liệu sử dụng là các CSDL chuỗi tổng hợp được sinh ra từ công cụ phát sinh chuẩn của IBM hoặc các CSDL chuỗi thực tế. Nội dung nghiên cứu của luận án được chia thành hai giai đoạn. Giai đoạn thứ nhất, nghiên cứu kỹ thuật khai thác hiệu quả mẫu tuần tự từ CSDL chuỗi. Giai đoạn tiếp theo, nghiên cứu cách thức sinh luật tuần tự và các phương pháp loại bỏ luật dư thừa. Nội dung nghiên cứu của luận án tập trung vào ba vấn đề chính: (i) Phát triển thuật toán khai thác mẫu tuần tự đóng. (ii) Phát triển thuật toán khai thác mẫu tuần tự liên chuỗi đóng. (iii) Phát triển thuật toán sinh luật tuần tự không dư thừa. 4. Phương pháp nghiên cứu Khảo sát và nghiên cứu các cách tiếp cận, cùng với các kỹ thuật và phương pháp đã được công bố từ trước đến nay của các tác giả trong và ngoài nước có liên quan đến lĩnh vực khai thác CSDL chuỗi. Trên cơ sở phân tích, đánh giá các đặc điểm để có thể đưa ra hướng giải quyết và các cải tiến nhằm áp dụng vào bài toán của luận án. 3 Tiến hành thực nghiệm và đánh giá, so sánh các phương pháp được đề xuất trong luận án với các phương pháp đã có. 5. Các đóng góp của luận án Nghiên cứu và đề xuất cách thức tổ chức dữ liệu cho các mẫu tuần tự và kết quả khai thác một cách tối ưu về không gian lưu trữ và thời gian xử lý trong quá trình khai thác. Dựa vào đặc điểm của mẫu tuần tự và cấu trúc dữ liệu được đề xuất, luận án đề xuất kỹ thuật loại trừ sớm ứng viên và kỹ thuật kiểm tra mẫu tuần tự đóng trực tiếp dựa vào thông tin vị trí của mẫu tuần tự. Đề xuất kỹ thuật khai thác hiệu quả luật tuần tự không dư thừa thông qua việc kết hợp kỹ thuật khai thác mẫu tuần tự đóng và khai thác tập sinh cùng với việc tỉa những luật không đủ độ tin cậy. Chương 1. Giới thiệu tổng quan Chương này trình bày tổng quan về lĩnh vực khai thác dữ liệu và hướng nghiên cứu chính trong khai thác dữ liệu, trong đó có vấn đề khai thác dữ liệu chuỗi. Bên cạnh trình bày các kỹ thuật đã được áp dụng trong bài toán này, luận án trình bày khảo sát và đánh giá các công trình nghiên cứu liên quan nhằm làm rõ tính cấp thiết và nội dung nghiên cứu của luận án. 1.1. Tổng quan về khai thác dữ liệu 1.1.1. Khai thác dữ liệu Sự bùng nổ thông tin cùng với sự phát triển của công nghệ lưu trữ và mạng Internet làm cho khối lượng dữ liệu phục vụ cho nhu cầu hàng ngày của mỗi tổ chức ngày càng trở nên đa dạng và phong phú. Do vậy, nhu cầu khám phá những thông tin cần thiết, những tri thức phục vụ cho nhu cầu quản lý, định hướng chiến lược cho tổ chức ngày càng khó khăn. Chính vì thế khai thác dữ liệu ra đời nhằm phục vụ cho nhu cầu khai thác các tri thức tiềm ẩn đó. 4 Khai thác dữ liệu hay còn được gọi là khám phá tri thức trong CSDL. Đây chính là quá trình khám phá những mẫu hay tri thức có ích từ nguồn dữ liệu, ví dụ như là CSDL, văn bản, ảnh, hay dữ liệu Web. Các mẫu khai thác được phải có giá trị, có khả năng hữu ích và dễ hiểu. Cho nên, khai thác dữ liệu là một lĩnh vực đa ngành có liên quan đến máy học, thống kê, CSDL, trí tuệ nhân tạo, thu thập thông tin và mô phỏng trực quan hóa dữ liệu. Quá trình khám phá tri thức trong CSDL có thể được thực hiện trong ba giai đoạn chính: (i) giai đoạn tiền xử lý dữ liệu, (ii) giai đoạn khai thác dữ liệu, và (iii) giai đoạn hậu xử lý. Quá trình này là một quá trình lặp, được thực hiện lặp đi lặp lại nhiều lần để có thể đạt được kết quả khả quan cuối cùng. 1.1.2. Các kỹ thuật khai thác dữ liệu Hiện tại, khai thác dữ liệu thường tập trung vào các hướng chính và được đề cập nhiều nhất gồm: phân lớp, phân cụm dữ liệu, khai thác luật kết hợp và khai thác luật tuần tự. Các mô hình liên quan được đề xuất bao gồm khai thác văn bản, khai thác dữ liệu Web, khai thác dữ liệu không gian và thời gian, v.v… Một trong những mô hình dữ liệu quan trọng và đang được tập trung nhiều nghiên cứu hiện nay là mô hình CSDL chuỗi. Trong đó, khai thác luật từ CSDL chuỗi đóng vai trò quan trọng trong việc hỗ trợ các tổ chức dự đoán các xu hướng, các biến đổi của dữ liệu nhằm tìm ra cách thức tổ chức, quản lý công việc tốt hơn. 1.2. Tổng quan về khai thác CSDL chuỗi Khai thác luật tuần tự là một trong những chủ đề nghiên cứu thiết thực và quan trọng hiện nay của lĩnh vực khai thác dữ liệu. Mục đích của nó là tìm ra các luật tiềm ẩn trong CSDL chuỗi. Mỗi luật thể hiện mối quan hệ giữa các mẫu dữ liệu theo thứ tự thời gian. 5 Khai thác tập mẫu tuần tự đóng giúp làm giảm đáng kể số lượng mẫu dư thừa. Do vậy, để hạn chế sự phát triển và bùng nổ về số lượng luật, hướng tiếp cận hiện tại là khai thác luật tuần tự không dư thừa dựa vào tập mẫu tuần tự đóng hoặc kết hợp tập mẫu tuần tự đóng với tập sinh. Tiêu biểu như của Jaroszewicz và Simovici, (2002), Zaki (2004), Ashrafi và đồng sự (2004, 2005), hay David Lo và đồng sự (2009). Các nghiên cứu đã đề xuất các kỹ thuật theo các cách tiếp cận khác nhau, hay kết hợp nhiều hướng tiếp cận với mục tiêu chính là không ngừng cải tiến thuật toán khai thác nhằm đáp ứng tốt hơn cả về thời gian thực thi lẫn hiệu quả sử dụng bộ nhớ. Quá trình khai thác luật tuần tự từ CSDL chuỗi thường được chia thành hai giai đoạn chính: Giai đoạn khai thác mẫu tuần tự (hoặc mẫu tuần tự đóng) và tiếp theo là Giai đoạn sinh luật tuần tự. Do vậy, số lượng mẫu tuần tự khai thác được là nhân tố quyết định và ảnh hưởng rất lớn đến việc sinh ra luật tuần tự có hiệu quả hay không. 1.3. Phân loại các kỹ thuật khai thác mẫu tuần tự Gần đây có rất nhiều nghiên cứu tập trung vào khai thác mẫu tuần tự từ CSDL chuỗi bao gồm những hướng cụ thể như: - Khai thác mẫu tuần tự tổng quát hay còn gọi là khai thác mẫu tuần tự; - Khai thác mẫu tuần tự liên chuỗi; - Khai thác mẫu tuần tự dựa trên ràng buộc; - Khai thác mẫu tuần tự trên CSDL tăng trưởng; - Khai thác mẫu tuần tự gần đúng; - Khai thác mẫu tuần hoàn một phần. Trong đó, bài toán khai thác mẫu tuần tự là một trong những vấn đề cơ bản nhất. 6 1.4. Các công trình nghiên cứu liên quan đã được đề xuất 1.4.1. Khai thác mẫu tuần tự Các tiếp cận chính của các thuật toán bao gồm các hướng sau: (1) Tiếp cận theo phép kết - sinh Apriori: AprioriAll (Agrawal và Srikant, 1995), GSP (Agrawal và Srikant, 1996), PSP (Masseglia và đồng sự, 1999), hay SPAM (Ayers và đồng sự, 2002). (2) Tiếp cận theo phương pháp phát triển mẫu: FreeSpan (Han và đồng sự, 2000), Wap-mine (Pei và đồng sự, 2000), PrefixSpan (Pei và đồng sự, 2001), hay FS-Miner (EI-Sayed và đồng sự, 2004). (3) Tiếp cận theo phương pháp tỉa ứng viên: DISC-all (Chiu và đồng sự, 2004), hay LAPIN (Yang và đồng sự, 2007). (4) hoặc kết hợp các ưu điểm của các hướng trên: SPADE (Zaki, 2001), PLWAP (Ezeife và Lu, 2005), hay PRISM (Gouda, Hassaan và Zaki, 2010). 1.4.2. Khai thác mẫu tuần tự đóng Hạn chế chính của các thuật toán khai thác mẫu tuần tự tổng quát là cố gắng tìm tất cả những mẫu tuần tự có thể có. Điều này sẽ làm gia tăng nhanh chóng mẫu khai thác được, dẫn đến sự dư thừa, trùng lắp của các mẫu. Mục đích của khai thác mẫu tuần tự đóng là giúp giảm bớt những mẫu tuần tự không cần thiết. Một số thuật toán khai thác hiệu quả mẫu (mẫu tuần tự) đóng được đề xuất bao gồm A-Close (Pasquier và đồng sự, 1999), CLOSET (Pei và đồng sự, 2000), CHARM (Zaki và Hsiao, 2002) và CLOSET+ (Wang và đồng sự, 2003), CloSpan (Yan và đồng sự, 2003), và BIDE (Wang và đồng sự, 2007). Tuy nhiên, một số thuật toán này phải duy trì mẫu tuần tự khai thác được ở bước trước để phục vụ cho việc kiểm tra mẫu tuần tự đóng mới được sinh ra. Một số thuật toán khác thì phải duyệt lại CSDL chuỗi nhiều lần. 7 1.4.3. Khai thác mẫu tuần tự liên chuỗi Bài toán khai thác mẫu tuần tự liên chuỗi là bài toán có quan tâm đến mối quan hệ giữa các mẫu tuần tự của các giao dịch tại các thời điểm khác nhau nhằm thể hiện mối quan hệ theo thứ tự thời gian giữa các chuỗi trong CSDL chuỗi. Do đó, mẫu tuần tự liên chuỗi mang ý nghĩa tổng quát và phức tạp hơn so với mẫu tuần tự. Bởi vì, trong quá trình khai thác mẫu tuần tự liên chuỗi đã bao gồm luôn việc khai thác mẫu tuần tự và kết hợp các mẫu tuần tự này theo các khoảng thời gian khác nhau. Thuật toán tiêu biểu đầu tiên cho bài toán khai thác mẫu tuần tự liên chuỗi là EISP-Miner (Wang và Lee, 2009). Tiếp theo đó, Wang và đồng sự (2013) đã đề xuất thuật toán khai thác mẫu tuần tự liên chuỗi đóng giúp giải quyết vấn đề số lượng tập mẫu thu được quá lớn. 1.4.4. Khai thác luật tuần tự Khai thác luật tuần tự giúp cho việc rút trích và biểu diễn được những thông tin hữu ích từ tập mẫu tuần tự. Khai thác luật tuần tự là giai đoạn tiếp theo của việc khai thác CSDL chuỗi. Luật tuần tự được sinh ra từ tập mẫu tuần tự. Mỗi luật khai thác được thể hiện mối quan hệ của những sự kiện theo thời gian, giúp dự đoán được những sự kiện xảy ra tiếp theo. Phương pháp khai thác tập luật tuần tự đầy đủ đầu tiên được đề xuất bởi Spiliopoulou vào năm 1999. Sau đó, bài toán được khái quát thành thuật toán Full (Lo và đồng sự, 2009). Tuy nhiên, việc khai thác toàn bộ tập luật sẽ dẫn đến việc tồn tại những luật dư thừa. Do vậy, các thuật toán khai thác luật tuần tự không dư thừa được đề xuất nhằm giải quyết các vấn đề này. 8 Vấn đề khai thác luật tuần tự không dư thừa được đề cập kể từ khi Lo đưa ra khái niệm và đề xuất thuật toán CNR (Lo và đồng sự, 2009). Dựa vào đặc tính cấu trúc cây tiền tố, thuật toán MSR-ImpTree (Van và đồng sự, 2011) đã cải tiến thuật toán Full nhằm làm tăng hiệu quả khai thác luật, thuật toán CloGen (Pham và đồng sự, 2013) cho phép khai thác luật tuần tự không dư thừa một cách hiệu quả. Chương 2. Phương pháp khai thác mẫu tuần tự đóng Chương này trình bày các khái niệm của việc khai thác mẫu tuần tự và mẫu tuần tự đóng. Khai thác mẫu tuần tự đóng giúp giảm đáng kể số lượng mẫu không cần thiết. Phần cuối của chương, luận án trình bày một đề xuất cải tiến cho việc khai thác hiệu quả mẫu tuần tự đóng. 2.1. Mục tiêu Khai thác mẫu tuần tự giúp khám phá những mẫu tuần tự xuất hiện thường xuyên để tìm ra mối quan hệ giữa các sự kiện 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. Dựa vào đặc điểm của mẫu cần khai thác, bài toán khai thác mẫu tuần tự thường tập trung vào hai dạng chính: Khai thác mẫu tuần tự và khai thác mẫu tuần tự liên chuỗi. 2.2. Các định nghĩa Một CSDL chuỗi được định nghĩa là một danh sách các chuỗi, ký hiệu SDB. Mỗi chuỗi bao gồm các tập sự kiện (itemset) xảy ra theo thứ tự thời gian. Mỗi tập sự kiện là một tập khác rỗng bao gồm một nhóm các sự kiện (item) xảy ra trong cùng một thời điểm. Mỗi sự kiện thường được ký hiệu là các ký tự chữ cái. Các sự kiện trong một tập sự kiện được thể hiện theo thứ tự từ điển và được ký hiệu trong cặp dấu ngoặc tròn. Các sự kiện có thể là các trang Web, các mặt hàng hay các từ trong văn bản. Bảng 2-1 trình bày một ví dụ về CSDL chuỗi. 9 Chiều dài chuỗi được tính là số lượng các sự kiện có trong chuỗi. Chuỗi có chiều dài k được gọi là k-sequence. Kích thước của chuỗi được tính dựa vào số lượng các tập sự kiện có trong chuỗi. Chuỗi Sa = 〈a1 a2 ⋯ am 〉 được gọi là được chứa trong hay còn gọi là chuỗi con (subsequence) của chuỗi Sb = 〈b1 b2 ⋯ bn 〉 nếu tồn tại một vị trí 1 ≤ i1 < i2 < ⋯ < im ≤ n sao cho: a1 ⊆ bi1 , a2 ⊆ bi2 , …, am ⊆ bim . Trường hợp này, Sb được gọi là chuỗi cha (supersequence) của chuỗi Sa , ký hiệu là Sa ⊆ Sb . Bảng 2-1. Một ví dụ về CSDL chuỗi SDB ID Chuỗi 1 〈C A A (A C)〉 2 〈A B (A B C) B〉 3 〈A (B C) A B C E〉 4 〈A B (B C) A D〉 Độ hỗ trợ (support) của chuỗi Sa trong CSDL chuỗi SDB được tính là tổng số dòng có chứa Sa trong các giao dịch của SDB, ký hiệu là sup(Sa ). Một chuỗi Sa được gọi là phổ biến (hay mẫu tuần tự) trên CSDL chuỗi nếu sup(Sa ) ≥ minSup, với minSup là ngưỡng phổ biến tối thiểu do người dùng qui định trước. 2.3. Khai thác mẫu tuần tự Bài toán khai thác mẫu tuần tự là đi tìm tất cả các mẫu tuần tự trong CSDL chuỗi với một ngưỡng phổ biến tối thiểu minSup do người dùng qui định trước. Khai thác mẫu tuần tự là việc khai thác các mẫu dựa theo sự kết hợp thứ tự của các sự kiện và các tập sự kiện hay còn gọi là khai thác các mở rộng của mẫu tuần tự. Dạng mở rộng của mỗi mẫu tuần tự được thực hiện theo hai dạng: mở rộng sequence và mở rộng itemset. 10 2.4. Khai thác mẫu tuần tự đóng Hạn chế của các thuật toán khai thác mẫu tuần tự là cố gắng tìm tất cả những mẫu tuần tự có thể có trong CSDL chuỗi cho trước. Do đó, sẽ có những mẫu không cần thiết, sẽ dẫn đến việc sinh ra những luật tuần tự dư thừa. Cho nên, khai thác mẫu tuần tự đóng được đề xuất nhằm giải quyết vấn đề này. Mẫu tuần tự Sa được gọi là mẫu tuần tự đóng trên SDB nếu mẫu Sa là phổ biến và không tồn tại mẫu tuần tự cha Sb nào của Sa có cùng độ hỗ trợ. Bài toán khai thác mẫu tuần tự đóng là khai thác những mẫu tuần tự đóng trong CSDL chuỗi với ngưỡng minSup cho trước. 2.4.1. Các nghiên cứu liên quan về khai thác mẫu tuần tự đóng Một số thuật toán tiêu biểu cho khai thác mẫu đóng hay mẫu tuần tự đóng gồm có A-CLOSE (Pasquier và đồng sự, 1999), CLOSET (Pei và đồng sự, 2000), CHARM (Zaki và Hsiao, 2002), CLOSET+ (Wang và đồng sự, 2003), CloSpan (Yan và đồng sự, 2003), BIDE (Wang và đồng sự, 2007) và ClaSP (Gomariz và đồng sự, 2013). Tuy nhiên, phần lớn các thuật toán này phải duy trì tập phổ biến khai thác được để kiểm tra mẫu nào là mẫu đóng của tập phổ biến ứng viên vừa được sinh ra trước khi loại trừ chúng. Một số thuật toán khác thì dùng kỹ thuật chiếu trên CSDL và phải duyệt lại CSDL chiếu nhiều lần. Do vậy, chúng sẽ yêu cầu nhiều không gian lưu trữ trung gian trong quá trình khai thác. 2.4.2. Đề xuất cải tiến và mô tả thuật toán Tiếp cận của luận án trong việc cải tiến phương pháp cho bài toán khai thác mẫu tuần tự đóng hiệu quả thông qua đề xuất phương pháp tổ chức cấu trúc dữ liệu để biểu diễn thông tin của mẫu tuần tự. Với cấu trúc dữ liệu được đề xuất, luận án sẽ áp dụng các kỹ thuật tỉa mẫu ứng viên và kỹ thuật kiểm tra mẫu tuần tự đóng trực tiếp (không dựa vào mẫu trước đó) nhằm tăng hiệu quả khai thác tập mẫu tuần tự phổ biến đóng từ CSDL chuỗi. 11 2.4.2.1. Cấu trúc dữ liệu vector bit động Cấu trúc vector bit cho phép nén thông tin các sự xuất hiện của mẫu. Bit ‘1’ cho biết rằng có sự kiện tương ứng xuất hiện và ngược lại bit ‘0’ thể hiện tại giao dịch đó không có sự xuất hiện của sự kiện đang xét. Cấu trúc vector bit động (Dynamic Bit Vector - DBV) giúp loại bỏ những bit ‘0’ ở phần đầu và phần cuối của bảng bit. Mỗi cấu trúc DBV gồm hai phần: (1) Start bit: Vị trí xuất hiện đầu tiên của bit ‘1’ và (2) Vector bit: Dãy các bit bắt đầu từ bit khác không đầu tiên cho đến bit khác không cuối cùng. Cấu trúc DBV được dùng để lưu trữ các mẫu tuần tự theo định dạng dọc. Độ hỗ trợ của mẫu tuần tự được tính đơn giản bằng cách dựa vào số lượng bit ‘1’ trong bảng bit. 2.4.2.2. Cấu trúc dữ liệu CloFS-DBVPattern Cấu trúc CloFS-DBVPattern là sự kết hợp giữa DBV với thể hiện thông tin của mẫu tuần tự. Mỗi cấu trúc CloFS-DBVPattern gồm hai phần: (i) Sequence: Chứa thông tin mẫu tuần tự và (ii) BlockInfo: Gồm DBV và danh sách các vị trí xuất hiện của mẫu tuần tự trong mỗi dòng của CSDL chuỗi. 2.4.2.3. Cấu trúc cây CloFS-DBV Cấu trúc cây CloFS-DBV là một dạng mở rộng của cấu trúc cây tiền tố. Mỗi nút trên cây lưu trữ các mẫu tuần tự theo cấu trúc CloFS-DBVPattern. Với cấu trúc cây tiền tố, việc sinh luật tuần tự sẽ hiệu quả hơn bằng cách xét từng nút (tiền tố) và các nút con của nó (hậu tố), tương ứng với phần bên trái và phần bên phải của luật. 2.4.2.4. Thuật toán CloFS-DBV Thuật toán CloFS-DBV đề xuất gồm bốn giai đoạn chính: (1) Duyệt CSDL chuỗi ban đầu để tìm mẫu tuần tự có chiều dài 1 thỏa ngưỡng minSup, mỗi mẫu được lưu trữ theo cấu trúc CloFS-DBVPattern; 12 (2) Áp dụng kỹ thuật loại trừ sớm mẫu tiền tố không có khả năng sinh ra mẫu tuần tự đóng mới; (3) Mở rộng cho những mẫu tuần tự còn lại để sinh mẫu ứng viên mới thông qua các phép giao trên bit; (4) Kiểm tra mẫu tuần tự đóng trực tiếp dựa vào đặc điểm vị trí của mẫu. Giai đoạn (2) đến (4) được lặp đi lặp lại nhiều lần cho đến khi không còn mẫu tuần tự đóng nào được sinh ra. 2.4.3. Kết quả thực nghiệm Kết quả thực nghiệm được thực hiện trên CSDL chuỗi tổng hợp với hai thuật toán khai thác mẫu tuần tự đóng chuẩn gồm BIDE (Wang và đồng sự, 2007) và CloSpan (Yan và đồng sự, 2003). Với cùng tập mẫu tuần tự đóng khai thác được của các thuật toán, các kết quả đã chứng minh được tính hiệu quả của thuật toán CloFS-DBV cả về thời gian và không gian sử dụng trong quá trình khai thác. Chương 3. Phương pháp khai thác mẫu tuần tự liên chuỗi đóng Chương này trình bày vấn đề khai thác mẫu tuần tự liên chuỗi và ý nghĩa của việc khai thác mẫu tuần tự liên chuỗi đóng. Phần cuối của chương, luận án trình bày thuật toán đề xuất cho bài toán khai thác mẫu tuần tự liên chuỗi đóng. 3.1. Giới thiệu Khác với bài toán khai thác mẫu tuần tự (chỉ quan tâm đến mối quan hệ thứ tự diễn ra trong cùng một giao dịch), bài toán khai thác mẫu tuần tự liên chuỗi quan tâm đến mối quan hệ giữa các giao dịch xảy ra tại các thời điểm khác nhau. Bởi vì những giao dịch này có mối quan hệ chặt chẽ với nhau, những giao dịch trước có thể ảnh hưởng đến những giao dịch xảy ra sau đó. Khai thác mẫu tuần tự liên chuỗi là một mở rộng của khai thác mẫu tuần tự. 13 Do vậy, các thuật toán khai thác mẫu tuần tự liên chuỗi có thể được dùng cho trường hợp khai thác mẫu tuần tự và cả mẫu tuần tự liên chuỗi tùy thuộc vào khoảng thời gian cần xem xét giữa các giao dịch. Thuật toán EISP-Miner (Wang và Lee, 2009) được đề xuất đầu tiên cho phép khai thác mẫu tuần tự liên chuỗi giữa các giao dịch trong CSDL chuỗi. Sau đó, thuật toán CISP-Miner (Wang và đồng sự, 2013) được đề xuất cho phép khai thác mẫu tuần tự liên chuỗi đóng nhằm làm giảm số lượng mẫu tuần tự liên chuỗi dư thừa trong tập khai thác được. Tuy nhiên, thuật toán này vẫn còn tồn tại hạn chế là phải duy trì mẫu khai thác ở bước trước để phục vụ cho việc kiểm tra mẫu đóng ở bước sau. Sau khi kiểm tra các mẫu này, thuật toán sẽ quyết định giữ lại hoặc loại bỏ. 3.2. Các định nghĩa Thuộc tính thời gian của CSDL chuỗi trong ngữ cảnh khai thác mẫu tuần tự liên chuỗi có thể được định nghĩa thông qua các mẫu tuần tự tại các giao dịch khác nhau (ID) trong CSDL. Gọi 𝑡1 và 𝑡2 là thuộc tính thời gian tương ứng cho mẫu tuần tự 𝑆1 và 𝑆2 . Nếu 𝑡1 được lấy làm thời điểm bắt đầu, khoảng cách thời gian giao dịch (gọi là span) của 𝑆1 và 𝑆2 được định nghĩa là [𝑡2 – 𝑡1 ]. Mẫu tuần tự 𝑆2 tại thời điểm 𝑡2 so với 𝑡1 được gọi là mẫu tuần tự mở rộng (e-seq) và được ký hiệu là 〈𝑆2 〉[𝑡2 – 𝑡1 ]. Giả sử có một e-seq 𝑆[𝑑] = 〈𝑒1 𝑒2 𝑒3 … 𝑒𝑚 〉[𝑑], trong đó 𝑒𝑗 là một tập sự kiện 1 ≤ 𝑗 ≤ 𝑚 và [𝑑] là span của 𝑆. Trong đó, 𝑒𝑗 kết hợp với [d] được định nghĩa là tập sự kiện mở rộng (e-iset), ký hiệu là 〈ej 〉[d]. Nếu ej = (i1 i2 i3 … in ), với ik là một sự kiện (1 ≤ k ≤ n), ik kết hợp với [d] được định nghĩa là sự kiện mở rộng (e-item), ký hiệu là ik [d]. Một mẫu tuần tự liên chuỗi là danh sách các e-seq liên tiếp trong CSDL chuỗi. Số lượng e-item trong một mẫu được gọi là chiều dài của mẫu. Một mẫu tuần tự liên chuỗi với chiều dài k được gọi là k-pattern. 14 Trong cùng một mẫu tuần tự liên chuỗi, span giữa ID của giao dịch thứ nhất (t1 ) và ID của giao dịch cuối cùng (t x ) phải nhỏ hơn hay bằng với maxSpan (t x – t1 ≤ maxSpan), trong đó maxSpan là ngưỡng span tối đa do người dùng định nghĩa. Nếu maxSpan = 0, bài toán khai thác mẫu tuần tự liên chuỗi sẽ trở thành bài toán khai thác mẫu tuần tự. Bảng 3-3 thể hiện ví dụ về CSDL liên chuỗi với maxSpan = 1. Bảng 3-3. Biểu diễn CSDL chuỗi theo dạng CSDL liên chuỗi ID Chuỗi giao dịch 1 〈A(AC)〉 Mẫu tuần tự liên chuỗi (maxSpan = 1) 〈A(AC)〉[0] 2 〈A(ABC)B〉 〈A(ABC)B〉[1] 〈A(ABC)B〉[0] 3 〈A(BC)〉 〈A(BC)〉[1] 4 〈B〉 〈A(BC)〉[0] 〈B〉[1] 〈B〉[0] Từ tập các mẫu tuần tự liên chuỗi đóng với chiều dài k (k ≥ 1), các mở rộng mẫu tuần tự liên chuỗi được thực hiện để tạo thành các mẫu ứng viên có chiều dài k + 1. Quá trình này được lặp đi lặp lại nhiều lần cho đến khi không còn mẫu tuần tự liên chuỗi đóng mới nào được sinh ra. Ngoài hai hình thức mở rộng như trong khai thác mẫu tuần tự (đã được đề cập trong Chương 2), khai thác mẫu tuần tự liên chuỗi bổ sung thêm một hình thức mở rộng liên chuỗi (mở rộng inter-sequence). 3.3. Đề xuất thuật toán khai thác mẫu tuần tự liên chuỗi đóng Thuật toán ClosedISP đề xuất sử dụng cấu trúc DBV kết hợp với span và thông tin giao dịch thành cấu trúc ClosedIS-Pattern để biểu diễn mẫu tuần tự liên chuỗi đóng. Cấu trúc cây ClosedIS-Tree được dùng để lưu trữ tất cả mẫu tuần tự liên chuỗi đóng. Chiến lược loại trừ và kiểm tra mẫu liên chuỗi đóng được áp dụng trong thuật toán. 15 3.3.1. Cấu trúc dữ liệu ClosedIS-Pattern Cấu trúc ClosedIS-Pattern là một mở rộng của cấu trúc CloFSDBVPattern (Chương 2). Trong đó, mỗi cấu trúc ClosedIS-Pattern gồm 2 phần: (i) Pattern: mẫu tuần tự với giá trị span tương ứng, và (ii) BlockeInfo: DBV giao dịch và danh sách các vị trí xuất hiện trong mẫu tuần tự của các giao dịch. Với cấu trúc ClosedIS-Pattern, chiến lược loại trừ và kiểm tra hiệu quả mẫu đóng có thể được thực hiện trực tiếp để tránh chi phí phát sinh mẫu và duyệt lại CSDL, và độ hỗ trợ có thể được tính một cách nhanh chóng. Hơn nữa, quá trình mở rộng mẫu được thực hiện thông qua thao tác trên bit gồm dịch phải bit (≫) và phép giao (AND) trên bit. 3.3.2. Cấu trúc cây ClosedIS-Tree Nhằm tăng hiệu quả việc khai thác luật và duyệt chiều sâu theo từng tiền tố, các mẫu tuần tự liên chuỗi đóng cũng được lưu trữ trong cấu trúc cây tiền tố được gọi là cây ClosedIS-Tree. Mỗi nút chứa thông tin ClosedIS-Pattern. Tương tự như cấu trúc cây tiền tố được trình bày trong Chương 2, nút gốc của cây (root) tại mức trên cùng và được gán nhãn là NULL. Tuy nhiên, quá trình mở rộng của mỗi nút trên cây được bổ sung thêm một hình thức mở rộng mới (mở rộng inter-sequence). 3.3.3. Thuật toán ClosedISP Thuật toán ClosedISP gồm bốn giai đoạn chính: (1) Duyệt CSDL chuỗi ban đầu để tìm tập những mẫu tuần tự liên chuỗi có chiều dài 1 và được lưu theo cấu trúc ClosedIS-Pattern, (2) Kiểm tra và loại trừ sớm tiền tố không có khả năng mở rộng, (3) mở rộng những mẫu có khả năng sinh ra mẫu tuần tự liên chuỗi đóng, và cuối cùng là (4) kiểm tra mẫu đóng trực tiếp để quyết định lưu lại hoặc không. Đối với mẫu có chiều dài 1, việc mở rộng mẫu sẽ được tiến hành để tạo các mẫu tuần tự liên chuỗi chiều dài 2 gồm các mẫu: mẫu được mở rộng theo 16 sequence, mẫu được mở rộng theo itemset và mẫu được mở rộng theo intersequence. Số lượng mẫu được mở rộng theo inter-sequence tùy thuộc vào giá trị maxSpan được cung cấp. Tiếp theo, thuật toán sẽ tiến hành mở rộng theo ba hình thức cho những mẫu có độ dài k (k > 1) để tạo thành các mẫu có độ dài k + 1. Quá trình thực hiện này lặp lại cho đến khi không có thêm mẫu tuần tự liên chuỗi đóng mới được sinh ra. 3.3.4. Kết quả thực nghiệm Kết quả thực nghiệm được thực hiện trên CSDL tổng hợp (được phát sinh từ công cụ sinh dữ liệu của IBM) và CSDL thực (Gazelle) để đánh giá hiệu quả của thuật toán được đề xuất. Thuật toán CISP-Miner được dùng để so sánh hiệu quả thực thi về thời gian và bộ nhớ sử dụng. Chương 4. Phương pháp khai thác luật tuần tự không dư thừa Chương này trình bày giai đoạn tiếp theo của khai thác CSDL chuỗi. Trong đó, bên cạnh trình bày cơ sở lý thuyết về kỹ thuật khai thác luật tuần tự và phương pháp khai thác luật tuần tự không dư thừa từ CSDL chuỗi. Luận án cũng sẽ trình bày kết quả nghiên cứu và phát triển một số kỹ thuật sinh luật tuần tự không dư thừa. 4.1. Giới thiệu Khai thác luật tuần tự là giai đoạn tiếp theo sau khi khai thác mẫu tuần tự. Mục tiêu của khai thác luật tuần tự là tìm mối quan hệ giữa sự xuất hiện của các sự kiện tuần tự trong CSDL chuỗi. Một luật tuần tự được thể hiện dưới dạng r = X → Y. Nghĩa là, nếu X xuất hiện trong mẫu tuần tự của CSDL thì Y cũng xuất hiện trong mẫu tuần tự đó và ngay sau X với độ tin cậy cao. Tập mẫu tuần tự khai thác được ảnh hưởng rất lớn đến việc sinh ra luật tuần tự. Nếu các mẫu thu được quá lớn và nhiều mẫu không cần thiết thì sẽ dẫn đến việc sinh ra luật dư thừa và tác động đến thời gian khai thác luật. 17 Tiếp cận theo hướng khai thác tập mẫu tuần tự đóng và tập sinh để giải quyết vấn đề sinh ra luật tuần tự không dư thừa. Trong đó, tiêu biểu là thuật toán CNR (Lo và đồng sự, 2009). Tuy nhiên, phần lớn các thuật toán được đề xuất một cách độc lập theo từng mục đích khai thác. Vì thế, hạn chế của những thuật toán khai thác luật là sinh luật tuần tự dựa vào kết quả của những thuật toán khai thác mẫu phổ biến sẵn có. Do vậy, chúng phải phụ thuộc hoàn toàn vào cấu trúc dữ liệu của mẫu phổ biến khai thác được. Muốn tăng hiệu quả sinh luật, các thuật toán này phải xây dựng lại cấu trúc dữ liệu tổ chức các mẫu tuần tự cho phù hợp trước khi bắt đầu thực hiện quá trình sinh luật. 4.2. Các định nghĩa Một luật tuần tự thể hiện mối quan hệ thứ tự thời gian xuất hiện giữa các mẫu tuần tự trong CSDL chuỗi và được ký hiệu là r = 〈pre〉 → 〈post〉, {sup(r), conf(r)}, với pre và post là phần đầu và cuối được tách ra từ một mẫu tuần tự X ban đầu trong CSDL. Với sup(r) = sup(X), conf(r) = sup(r)/sup(〈pre〉) là giá trị hỗ trợ và độ tin cậy tương ứng của r. Cho ngưỡng phổ biến tối thiểu minSup và ngưỡng tin cậy tối thiểu minConf. Nếu sup(r) ≥ minSup thì r được xem là luật tuần tự phổ biến. Nếu conf(r) ≥ minConf thì r được gọi là luật tuần tự tin cậy. Một luật tuần tự được gọi là dư thừa nếu nó có thể được suy dẫn bởi một luật khác. Một mẫu tuần tự P được xem là tiền tố sinh (prefixed generator) nếu không tồn tại P′ sao cho P′ ⊂ P ∧ sup(P ′ ) = sup(P). Luật r = pre → post được gọi là luật tuần tự không dư thừa nếu thỏa cả hai điều kiện: Vế trái và vế phải của luật được tạo ra từ mẫu tuần tự đóng và vế trái phải là tiền tố sinh. 18
- Xem thêm -

Tài liệu liên quan