Tài liệu Khai phá tập mục thƣờng xuyên lợi ích cao trong cơ sở dữ liệu

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN AN KHÁNH KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn THÁI NGUYÊN - 2012 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN AN KHÁNH KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: GS. TS: Vũ Đức Thi THÁI NGUYÊN - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CẢM ƠN Lời đầu tiên cho tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc đến GS. TS Vũ Đức Thi – Viện Công nghệ Thông tin, Viện Khoa học và Công nghệ Việt Nam, ngƣời thầy đáng kính đã chỉ bảo và hƣớng dẫn tận tình cho tôi trong suốt quá trình nghiên cứu khoa học và thực hiện luận văn này Tôi xin chân thành cảm ơn sự dậy bảo, giúp đỡ, tạo điều kiện và khuyến khích tôi trong quá trình học tập và nghiên cứu của các thầy cô giáo Viện Công nghệ Thông tin, Viện Khoa học và Công nghệ Việt Nam Xin chân thành cảm ơn Ban Giám hiệu và thầy cô giáo Trƣờng Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên, nơi tôi học tập và làm việc, xin đƣợc gửi lời cảm ơn chân thành và sâu sắc nhất đến các thầy cô. Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, bạn bè và đồng nghiệp – những ngƣời luôn ở bên tôi những lúc khó khăn nhất, luôn động viên tôi, khuyến khích tôi trong cuộc sống và trong công việc. Tôi xin chân thành cảm ơn! Thái Nguyên, ngày 20 tháng 6 năm 2012 Tác giả Nguyễn An Khánh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan Luận văn “ Khai phá tập mục thƣờng xuyên lợi ích cao trong cơ sở dữ liệu “ đƣợc thực hiện theo đúng mục tiêu đề ra dƣới sự hƣớng dẫn của GS. TS Vũ Đức Thi. Trong toàn bộ luận văn, những điều đƣợc trình bày là của cá nhân hoặc là đƣợc tổng họp từ nhiều nguồn tài liệu. Tất cả các loại tài liệu đều có xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp. Thái Nguyên, ngày 20 tháng 6 năm 2012 Tác giả Nguyễn An Khánh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT Trong luận văn này, dùng thống nhất các ký hiệu và chữ viết tắt sau: Các ký hiệu: I = {i1,i2,…,in}: Tập n mục dữ liệu. DB = {T1,T2,…,Tm}: Cơ sở dữ liệu có m giao tác. db: cơ sở dữ liệu giao tác con của DB, db  DB. ip: Mục dữ liệu thứ p. Tq: Giao tác thứ q. n: Số mục dữ liệu một cơ sở dữ liệu giao tác. m: Số giao tác một cơ sở dữ liệu giao tác. A, B, C,…: Tên các mục dữ liệu trong cơ sở dữ liệu giao tác ví dụ. X, Y,…: Tập con của tập mục dữ liệu I, X, Y  I. X = ABC thay cho X={A,B,C} trong các cơ sở dữ liệu giao tác ví dụ. Nếu X  Y thì X gọi là tập con của tập Y, Y gọi là tập cha của tập X. minsup: Ngƣỡng độ hỗ trợ tối thiểu. minShare: Ngƣỡng cổ phần tối thiểu. minutil: Giá trị lợi ích tối thiểu. X: Số phần tử của tập hợp X. Viết tắt: CSDL: Cơ sở dữ liệu. CNTT: Công nghệ Thông tin. CNTT và TT: Công nghệ Thông tin và Truyền thông. DL: Dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỤC LỤC MỞ ĐẦU .....................................................................................................................7 Chƣơng 1 KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG ..........9 1.1MỞ ĐẦU ...........................................................................................................9 1.2CÁC KHÁI NIỆM CƠ BẢN ...........................................................................10 1.2.1 Cơ sở dữ liệu giao tác ..................................................................... 10 1.2.2 Tập mục thƣờng xuyên và luật kết hợp.......................................... 13 1.2.3 Bài toán khai phá luật kết hợp........................................................ 14 1.3 KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN.................................................15 1.3.1 Các cách tiếp cận khai phá tập mục thƣờng xuyên ....................... 15 1.3.2 Thuật toán Apriori ......................................................................... 16 1.3.3 Thuật toán FP-growth ................................................................... 21 1.4 MỞ RỘNG BÀI TOÁN KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN ..........27 1.5 KẾT LUẬN CHƢƠNG 1 ...............................................................................28 Chƣơng 2 KHAI PHÁ TẬP MỤC LỢI ÍCH CAO ......................................................30 2.1. GIỚI THIỆU ..................................................................................................30 2.2 BÀI TOÁN KHAI PHÁ TẬP MỤC LỢI ÍCH CAO ......................................32 2.3 THUẬT TOÁN COUI-Mine1 ........................................................................35 2.3.1 Xây dựng cây TWUI-tree............................................................... 37 2.3.2 Khai phá cây TWUI-tree ................................................................ 42 2.3.3 Đánh giá thuật toán COUI-Mine1.................................................. 51 2.3.3.1: Bƣớc xây dựng cây TWUI-tree: ............................................ 51 2.3.3.2: Bƣớc khai phá cây TWU-tree ................................................ 52 2.3.4 Nhận xét thuật toán COUI-Mine1.................................................. 54 2.3.5 Khai phá tƣơng tác với cây TWUI-tree ......................................... 55 2.4 THUẬT TOÁN COUI-Mine2 ........................................................................57 2.4.1 Xây dựng cây UP-tree .................................................................... 57 2.4.2 Khai phá cây UP-tree ..................................................................... 59 2.4.3 Ví dụ áp dụng minh họa ................................................................. 61 2.4.3.1 Xây dựng cây UP-tree ............................................................. 62 2.4.3.2 Khai phá cây UP-tree .............................................................. 64 2.4.4 Nhận xét thuật toán COUI-Mine2.................................................. 68 2.5 THUẬT TOÁN COUI-Mine3 ........................................................................70 2.5.1 Cơ sở của thuật toán ....................................................................... 70 2.5.2 Xây dựng và khai phá mảng giao tác ............................................. 71 2.5.2.1 Xây dựng mảng giao tác ......................................................... 71 2.5.2.2 Khai phá mảng giao tác :......................................................... 75 2.5.3 Nhận xét thuật toán COUI-Mine3.................................................. 78 2.6 KẾT LUẬN CHƢƠNG 2 ...............................................................................80 Chƣơng 3 THỰC NGHIỆM THUẬT TOÁN KHAI PHÁ TẬP MỤC LỢI ÍCH CAO ..81 PHẦN KẾT LUẬN .....................................................................................................85 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 MỞ ĐẦU Ngày nay, cùng với sự phát triển không ngừng của ngành công nghệ thông tin và truyền thông vào nhiều lĩnh vực đời sống văn hóa xã hội, quản lý kinh tế, khoa học kỹ thuật, … đã tạo ra nhiều cơ sở dữ liệu khổng lồ. Để khai thác hiệu quả nguồn thông tin dữ liệu lớn, hỗ chợ tiến trình ra quyết định, bên cạnh các phƣơng pháp khai thác thông tin truyền thống một khuynh hƣớng kỹ thuật mới ra đời đó là Kỹ thuật Khai phá dữ liệu và khám phá tri thức (KDD – Knownledge Discovery and DataMining) là một lĩnh vực quan trọng của nghành Công nghệ thông tin. Đây là lĩnh vực đã thu hút đƣợc đông đảo các nhà khoa học trên thế giới và trong nƣớc tham gia nghiên cứu. Khai phá tập mục thƣờng xuyên là bài toán có vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu. Mô hình khai phá tập mục thƣờng xuyên cơ bản có nhiều ứng dụng trong thực tế bên cạnh đó còn có những hạn chế, không đáp ứng đƣợc nhu cầu của ngƣời sử dụng. Để đáp ứng yêu cầu thực tiễn, một số hƣớng mở rộng của bài toán đã đƣợc quan tâm nghiên cứu, theo hƣớng này, từ các bài toán khai phá tập mục thƣờng xuyên ban đầu các nhà nghiên cứu đã đề xuất các mô hình mở rộng, một trong số đó có mô hình Khai phá tập mục lợi ích cao, đánh giá lợi ích mà tập mục dữ liệu mang lại trong cơ sở dữ liệu. Khai phá tập mục lợi ích cao là thực sự là một lĩnh vực đang thu hút nhiều nhà nghiên cứu tham gia. Trong luận văn này, tôi trình bày ba thuật toán khai phá tập mục lợi ích cao dựa trên cấu trúc cây đơn giản và cách khai phá không đệ quy (Thuật toán COUIMine1, COUI-Mine2, COUI-Mine 3). Các thuật toán đề xuất sử dụng cấu trúc cây FP-tree đƣợc Han, Wang và Yin giới thiệu năm 2000 trong cách khai phá cây FPtree không đệ quy bởi cấu trúc cây COFI-tree do Mohammad El-Hajj và Osmar R. Zaiane đề xuất năm 2003. Hai thuật toán đầu sử dụng cấu trúc cây FP-tree để xây dựng cây chứa thông tin của các giao tác, sau đó khai phá cây này để tìm ra các tập Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 mục lợi ích cao. Thuật toán thứ 3 chuyển đổi dữ liệu thành mạng ma trận để lƣu ở bộ nhớ ngoài, sau khi đã chuyển đổi sang dạng biểu diễn mới, có thể khai phá các ngƣỡng lợi ích khác nhau. Thuật toán thứ ba này có thể khai phá đƣợc các tập dữ liệu lớn vì hầu nhƣ toàn bộ dữ liệu đặt tại bộ nhớ ngoài, chỉ đƣa vào bộ nhớ trong một phần nhỏ dữ liệu để khai phá. Ba thuật toán đề xuất thực hiện khai phá hiệu quả vì các lí do: 1) Số lần duyệt cơ sở dữ liệu ít, 2) Không sinh ra khối lƣợng khổng lồ các tập ứng viên, giảm chi phí thanh toán và 3) sử dụng tiết kiệm bộ nhớ. Với thời gian và kiến thức còn hạn chế, luận văn này không tránh khỏi những thiếu sót, rất mong đƣợc sự quan tâm định hƣớng của thầy cô giáo sự góp ý của các bạn đồng nghiệp để báo cáo hoàn thiện hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Chƣơng 1 KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG 1.1 MỞ ĐẦU Khai phá tập mục thƣờng xuyên đóng vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu. Khai phá tập mục thƣờng xuyên xuất hiện nhƣ là bài toán con của nhiều lĩnh vực khai phá dữ liệu nhƣ khám phá luật kết hợp, khám phá mẫu tuần tự, phân tích tƣơng quan, phân lớp, phân cụm dữ liệu, khai phá Web,…Bài toán khai phá tập mục thƣờng xuyên đƣợc giới thiệu lần đầu bởi Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị, trong mô hình của bài toán khai phá luật kết hợp. Khai phá luật kết hợp là phát hiện những mối quan hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu, các mối quan hệ đó chính là các luật kết hợp. Khai phá luật kết hợp có hai bƣớc: bƣớc thứ nhất, tìm các tập mục thƣờng xuyên thỏa mãn ngƣỡng độ hỗ trợ tối thiểu minsup cho trƣớc, bƣớc thứ hai, từ các tập mục thƣờng xuyên tìm đƣợc, sinh ra các luật kết hợp thỏa mãn ngƣỡng độ tin cậy minconf cho trƣớc. Mọi khó khăn của bài toán khai phá luật kết hợp tập trung ở bƣớc thứ nhất, đó là khai phá tất cả các tập mục thƣờng xuyên thỏa mãn ngƣỡng độ hỗ trợ cho trƣớc. Kể từ khi Agrawal đề xuất, khai phá tập mục thƣờng xuyên đã thu hút đƣợc sự quan tâm của nhiều nhà nghiên cứu, đã có hàng trăm kết quả nghiên cứu đƣợc công bố giới thiệu các thuật toán mới hay đề xuất các giải pháp nâng cao hiệu quả các thuật toán đã có. Tập mục thƣờng xuyên đã có vai trò quan trọng trong nhiều ứng dụng thực tế nhƣ quản lý quan hệ khách hàng, nâng cao hiệu quả của thƣơng mại điện tử, trong lĩnh vực tin sinh học, phân tích cấu trúc của Protein và DNA, mở rộng truy vấn, phát hiện xâm nhập mạng,… Mô hình khai phá tập mục thƣờng xuyên cơ bản có nhiều ứng dụng trong thực tế nhƣng có những hạn chế, không đáp ứng đầy đủ yêu cầu của ngƣời sử dụng. Rằng buộc về độ hỗ trợ và độ tin cậy của luật kết hợp chỉ mang ngữ nghĩa thống kê, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 không phản ánh đƣợc vai trò khác nhau của các thuộc tính cũng nhƣ đặc tính dữ liệu vốn có của chúng trong cơ sở dữ liệu. Để đáp ứng yêu cầu của thực tiễn, khai phá tập mục thƣờng xuyên đã có nhiều cách thức mở rộng và ứng dụng, từ thay đổi phƣơng pháp luận đến thay đổi đa dạng các kiểu dữ liệu, mở rộng các nhiệm vụ khai phá và đa dạng các ứng dụng mới. Trong những năm qua, đã có nhiều hƣớng mở rộng bài toán đƣợc quan tâm nghiên cứu. Chƣơng một này sẽ trình bày các vấn đề cơ bản của bài toán khai phá tập mục thƣờng xuyên và một số mở rộng của bài toán. 1.2 CÁC KHÁI NIỆM CƠ BẢN Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Mục tiêu khai phá là phát hiện những mối quan hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Mô hình đầu tiên của bài toán khai phá luật kết hợp là mô hình nhị phân (hay còn gọi là mô hình cơ bản) đƣợc R.Agrawal, T.Imielinski và A.Swami đề xuất vào năm 1993, xuất phát từ nhu cầu phân tích dữ liệu của cơ sở dữ liệu giao tác, phát hiện các mối quan hệ giữa các tập mục hàng hóa (Itemsets) đã bán đƣợc tại các siêu thị. Việc xác định các quan hệ này không phân biệt vai trò khác nhau cũng nhƣ không dựa vào các đặc tính dữ liệu vốn có của các thuộc tính mà chỉ dựa vào sự xuất hiện cùng lúc của chúng. Phần tiếp sau đây nêu một số khái niệm cơ bản và phát biểu bài toán khai phá luật kết hợp, bài toán đầu tiên dẫn đến bài toán khai phá tập mục thƣờng xuyên. 1.2.1 Cơ sở dữ liệu giao tác Định nghĩa 1.1: Cho tập các mục (item) I={i1,i2,…,in}. Một giao tác (transaction) T là một tập con của I, T  I. Cơ sở dữ liệu giao tác là một tập các giao tác DB ={T1,T2,…,Tm}. Mỗi giao tác đƣợc gán một định danh TID. Một tập mục con X  I, gồm k mục phân biệt đƣợc gọi là một k-tập mục. Giao tác T gọi là chứa tập mục X nếu X  T. Biểu biễn cơ sở dữ liệu giao tác: Cơ sở dữ liệu giao tác thƣờng đƣợc biểu diễn ở dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 Biểu diễn ngang: Cơ sở dữ liệu là một danh sách các giao tác. Mỗi giao tác có một định danh TID và một danh sách các mục dữ liệu trong giao tác đó. Ví dụ 1.1: Bảng 1.1: Biểu diễn ngang của cơ sở dữ liệu giao tác. TID Mục dữ liệu T1 B, C, D T2 B, C, D T3 A, B, D T4 C, D, F T5 C, D T6 A, C T7 A, B, C, F T8 A, C T9 A, B, E T10 A, E T11 A, B, C Biểu diễn dọc: Cơ sở dữ liệu là một danh sách các mục dữ liệu, mỗi mục dữ liệu có một danh sách tất cả các định danh của các giao tác chứa mục dữ liệu này. Bảng 1.2: Biểu diễn dọc của cơ sở dữ liệu giao tác. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 Mục dữ liệu Định danh giao tác A T3, T6, T7, T8, T9, T10, T11 B T1, T2, T3, T7, T9, T11 C T1, T2, T4, T5, T6, T7, T8, T11 D T1, T2, T3, T4, T5 E T9, T10 F T4, T7 Ma trận giao tác: Cơ sở dữ liệu giao tác DB={T1,T2,…,Tm} trên tập các mục (item) I={i1,i2,…,in} đƣợc biểu diễn bởi ma trận nhị phân M= (mpq)mxn, ở đó : 1 khi iq  Tp m pq   0 khi iq  Tp Ví dụ 1.2: Cơ sở dữ liệu bảng 1.1 biểu diễn ở dạng ma trận giao tác là: Bảng 1.3: Ma trận giao tác của cơ sở dữ liệu bảng 1.1. TID A B C D E F T1 0 1 1 1 0 0 T2 0 1 1 1 0 0 T3 1 1 0 1 0 0 T4 0 0 1 1 0 1 T5 0 0 1 1 0 0 T6 1 0 1 0 0 0 T7 1 1 1 0 0 1 T8 1 0 1 0 0 0 T9 1 1 0 0 1 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 T10 1 0 0 0 1 0 T11 1 1 1 0 0 0 1.2.2 Tập mục thƣờng xuyên và luật kết hợp Định nghĩa 1.2: Cho tập mục X  I. Ta gọi độ hỗ trợ (Support) của X trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm các giao tác chứa X trên tổng số các giao tác trong DB, tức là : sup(X)= Ta có: 0  sup(X)  1 với mọi tập mục X  I. Định nghĩa 1.3: Cho tập mục X  I và ngƣỡng hỗ trợ tối thiểu (minimum support) minisup 0,1  (đƣợc xác định trƣớc bởi ngƣời sử dụng). X đƣợc gọi là tập mục thƣờng xuyên(frequent itemset hoặc large itemset) với độ hỗ trợ tối thiểu minisup nếu sup(X)  minisup, ngƣợc lại X gọi là tập mục không thƣờng xuyên. Định nghĩa 1.4: Một luật kết hợp là biểu thức dạng X  Y, trong đó X và Y là các tập con của I, X  Y = ; X gọi là tiền đề, Y gọi là kết luận của luật. Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy. Định nghĩa 1.5: Độ hỗ trợ (Support) của một luật kết hợp X  Y, ký hiệu là sup(X  Y), là độ hỗ trợ của tập mục X  Y, sup(X  Y) =sup(X  Y). Nhƣ vậy độ hỗ trợ của luật kết hợp X  Y chính là xác suất P(X  Y) của sự xuất hiện đồng thời của X và Y trong một giao tác. Ta có: 0  sup(X  Y)  1. Định nghĩa 1.6: Độ tin cậy(Confidence) của một luật X  Y , ký hiệu conf(X  Y), là tỷ lệ phần trăm giữa số giao tác chứa X  Y và số giao tác chứa X trong cơ sở dữ liệu DB. Conf(X  Y) = Độ tin cậy của luật kết hợp X  Y chính là xác suất có điều kiện P(Y/X): P(Y/X) = = Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên = http://www.lrc-tnu.edu.vn 14 Và ta có 0  conf(X  Y)  1. Các luật thỏa mãn cả hai ngƣỡng độ hỗ trợ tối thiểu (minsup) và độ tin cậy tối thiểu (minconf), tức thỏa mãn sup(X  Y)  minsup và conf(X  Y)  minconf, đƣợc gọi là luật kết hợp mạnh. Tính chất cơ bản của tập mục thƣờng xuyên: Cho cơ sở dữ liệu giao tác DB và ngƣỡng độ hỗ trợ tối thiểu minsup. Các tập mục thƣờng xuyên có các tính chất sau: (1) Nếu X, Y là các tập và X  Y thì sup(X)  sup(Y). (2) Nếu một tập mục là không thƣờng xuyên thì mọi tập cha của nó cũng không thƣờng xuyên. (3) Nếu một tập mục là thƣờng xuyên thì mọi tập con khác rỗng của nó cũng là tập mục thƣờng xuyên. Tính chất (3) đƣợc gọi là tính chất Apriori, tính chất này là cơ sở để rút gọn không gian tìm kiếm các tập mục thƣờng xuyên. 1.2.3 Bài toán khai phá luật kết hợp Cho cơ sở dữ liệu giao tác DB, ngƣỡng độ hỗ trợ tối thiểu minsup và ngƣỡng độ tin cậy tối thiểu minconf. Yêu cầu: Tìm tất cả các luật kết hợp X  Y trên cơ sở dữ liệu DB sao cho sup(X  Y)  minsup và conf(X  Y)  minconf. Bài toán khai phá luật kết hợp này đƣợc gọi là bài toán cơ bản hay bài toán nhị phân, vì ở đây, giá trị của mục dữ liệu trong cơ sở dữ liệu là 0 hoặc 1 (xuất hiện hay không xuất hiện). Bài toán khai phá luật kết hợp đƣợc chia thành hai bài toán con. Bài toán thứ nhất là tìm tất cả các tập mục thỏa mãn độ hỗ trợ tối thiểu cho trƣớc, tức là tìm tất cả các tập mục thƣờng xuyên. Bài toán thứ hai là sinh ra các luật kết hợp từ các tập mục thƣờng xuyên đã tìm đƣợc thỏa mãn độ tin cậy tối thiểu cho trƣớc. Bài toán thứ hai đƣợc giải quyết nhƣ sau: Giả sử đã tìm đƣợc X là tập mục thƣờng xuyên, ta sinh ra các luật kết hợp bằng cách tìm  Y  X, kiểm tra độ tin Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 cậy của luật X\YY có thỏa mãn độ tin cậy tối thiểu không. Bài toán thứ hai này đơn giản, mọi khó khăn nằm ở bài toán thứ nhất, hầu hết các nghiên cứu về luật kết hợp đều tập trung giải quyết bài toán thứ nhất là tìm các tập mục thƣờng xuyên. Phần tiếp theo sau đây sẽ trình bày chi tiết về khai phá tập mục thƣờng xuyên. 1.3 KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN 1.3.1 Các cách tiếp cận khai phá tập mục thƣờng xuyên Các nghiên cứu về khai phá tập mục thƣờng xuyên tập trung vào tìm các thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có. Phần này sẽ trình bày khái quát các kỹ thuật chính để khai phá tập mục thƣờng xuyên. Bài toán khai phá tập mục thƣờng xuyên có thể chia thành hai bài toán nhỏ: Tìm các tập mục ứng viên và tìm các tập mục thƣờng xuyên. Tập mục ứng viên là tập mục mà ta hy vọng nó là tập mục thƣờng xuyên, phải tính độ hỗ trợ của nó để kiểm tra. Tập mục thƣờng xuyên là tập mục có độ hỗ trợ lớn hơn hoặc bằng ngƣỡng hỗ trợ tối thiểu cho trƣớc. Đã có rất nhiều thuật toán tìm tập mục thƣờng xuyên đƣợc công bố, ta có thể phân chúng theo hai tiêu chí sau:  Phƣơng pháp duyệt qua không gian tìm kiếm.  Phƣơng pháp xác định độ hỗ trợ của tập mục. Phƣơng pháp duyệt qua không gian tìm kiếm đƣợc phân làm hai cách: Duyệt theo chiều rộng(Breadth First Search - BFS) và duyệt theo chiều sâu(Depth First Search - DFS). Duyệt theo chiều rộng là duyệt qua cơ sở dữ liệu gốc để tính độ hỗ trợ của tất cả các tập mục ứng viên có (k-1) mục trƣớc khi tính độ hỗ trợ của các tập mục ứng viên có k mục. Với cơ sở dữ liệu có n mục dữ liệu, lần lặp thứ k phải kiểm tra độ hỗ trợ của tất cả = tập mục ứng viên có k mục. Duyệt theo chiều sâu là duyệt qua cơ sở dữ liệu đã đƣợc chuyển đổi thành cấu trúc cây, quá trình duyệt gọi đệ quy theo chiều sâu của cây. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 Với cơ sở dữ liệu có n mục dữ liệu, không gian tìm kiếm có tất cả 2 n tập con, rõ ràng đây là bài toán NP khó, do vậy cần phải có phƣơng pháp duyệt thích hợp, tỉa nhanh các tập ứng viên. Phƣơng pháp xác định độ hỗ trợ của tập mục X đƣợc chia làm hai cách: cách thứ nhất là đếm số giao tác chứa X trong cơ sở dữ liệu và cách thứ hai là tính phần giao của các tập chứa định danh của các giao tác chứa X. Các thuật toán khai phá có thể phân loại nhƣ sau: DFS BFS Đếm Đếm Giao Giao AIS Apriori Dic FPEclat growth Hình 1.1: Phân loại các thuật toán khai phá tập mục thƣờng xuyên. Partition Phần tiếp sau mô tả chi tiết nội dung hai thuật toán tiêu biểu và là cơ sở để phát triển các thuật toán mới trong luận văn: Thuật toán Apriori tiêu biểu cho phƣơng pháp sinh ra các tập mục ứng viên và kiểm tra độ hỗ trợ của chúng; Thuật toán FPgrowth, đại diện cho phƣơng pháp không sinh ra tập mục ứng viên, cơ sở dữ liệu đƣợc nén lên cấu trúc cây, sau đó khai phá bằng cách phát triển dần các mẫu cây này. 1.3.2 Thuật toán Apriori Apriori là thuật toán khai phá tập mục thƣờng xuyên do R.Agrawal và R.Srikant đề xuất vào năm 1993. Ý tƣởng của thuật toán Apriori còn là nền tảng cho việc phát triển nhiều thuật toán khai phá tập mục thƣờng xuyên khác về sau. Ý tƣởng chính của thuật toán nhƣ sau: sinh ra các tập mục ứng viên từ các tập mục thƣờng xuyên ở bƣớc trƣớc, sử dụng kỹ thuật “tỉa” để bỏ đi các tập mục Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 17 ứng viên không thỏa mãn ngƣỡng hỗ trợ cho trƣớc. Cơ sở của kỹ thuật này là tính chất Apriori: Bất kỳ tập con nào của tập mục thường xuyên cũng phải là tập mục thường xuyên. Vì vậy các tập mục ứng viên gồm k mục có thể đƣợc sinh ra bằng cách kết nối các tập mục thƣờng xuyên có (k-1) mục và loại bỏ tập mục ứng viên nếu nó có chứa bất kỳ một tập con nào không phải là thƣờng xuyên. Giả sử các mục dữ liệu trong mỗi giao tác đƣợc lƣu theo trật tự từ điển. Thuật toán sử dụng các ký hiệu sau đây: Tập k mục Chức năng Lk Tập các k-tập mục thƣờng xuyên(với độ hỗ trợ tối thiểu minsup). Mỗi phần tử của tập này có 2 trƣờng: i) Tập mục(itemsets) ii) Độ hỗ trợ(count) Tập các k-tập mục ứng viên(các tập mục thƣờng xuyên tiềm Ck năng). Mỗi phần tử của tập này có 2 trƣờng: i) Tập mục(itemsets) ii) Độ hỗ trợ(count) Thuật toán duyệt cơ sở dữ liệu nhiều lần. Mỗi lần duyệt, thuật toán thực hiện hai bƣớc: bước kết nối và bước tỉa. Trong lần lặp thứ k, thuật toán nối hai (k1)-tập mục để sinh ra k-tập mục, sử dụng tính chất Apriori để tỉa các tập ứng viên. Bƣớc nối và bƣớc tỉa nhƣ sau: Bƣớc kết nối (tìm Ck): Tập các k-tập mục ứng viên Ck đƣợc sinh ra bởi việc kết nối Lk-1với chính nó. Hai tập mục L1 và L2 của Lk-1 đƣợc kết nối nếu chúng có (k-2) mục dữ liệu đầu bằng nhau, mục dữ liệu thứ (k-1) của L1 nhỏ hơn của L2: (L1[1]=L2[1])(L1[2]=L2[2]) …(L1[k-2]=L2[k-2])  (L1[k-1] - Xem thêm -