Tài liệu Các tập mục thường xuyên trong khai phá dữ liệu và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG MINH QUANG CÁC TẬP MỤC THƯỜNG XUYÊN TRONG KHAI PHÁ DỮ LIỆU VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ Hà Nội, 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG MINH QUANG CÁC TẬP MỤC THƯỜNG XUYÊN TRONG KHAI PHÁ DỮ LIỆU VÀ ỨNG DỤNG Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN: PGS. TS. Vũ Đức Thi Hà Nội, 2010 1 MỤC LỤC MỤC LỤC ............................................................................................ 1 DANH MỤC VIẾT TẮT VÀ KÝ HIỆU ........................................... 2 DANH MỤC BẢNG BIỂU, HÌNH ẢNH .......................................... 3 GIỚI THIỆU ....................................................................................... 4 I. KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN ............................... 5 I.1. I.2. I.3. I.4. I.5. I.6. I.7. Mở đầu ..................................................................................................... 5 Một số khái niệm cơ bản về tập mục ....................................................... 6 Tập mục thường xuyên và luật kết hợp.................................................... 7 Mô tả bài toán khai phá luật kết hợp ........................................................ 9 Một số thuật toán khai phá tập mục thường xuyên và luật kết hợp ....... 14 Thuật toán Apriori .................................................................................. 16 Thuật toán FP-Growth............................................................................ 20 II. CÁC BÀI TOÁN MỞ RỘNG KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN ........................................................................... 27 II.1. Một số nghiên cứu chuyên sâu về khai phá luật kết hợp ....................... 27 II.2. Khai phá tập mục cổ phần cao ............................................................... 28 II.3. Khai phá tập mục lợi ích cao.................................................................. 45 III. CÀI ĐẶT ỨNG DỤNG THỬ NGHIỆM KHAI PHÁ TẬP MỤC LỢI ÍCH CAO ........................................................................ 54 KẾT LUẬN ........................................................................................ 62 TÀI LIỆU THAM KHẢO ................................................................ 64 2 DANH MỤC VIẾT TẮT VÀ KÝ HIỆU 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 trong một cơ sở dữ liệu giao tác m: Số giao tác của 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 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ơ sở dữ liệu giao tác minsup: Ngưỡng độ hỗ trợ tối thiểu minShare: Ngưỡng cổ phần tối thiểu minutil: Ngưỡng 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 DB: Cơ sở dữ liệu giao tác DL: Dữ liệu 3 DANH MỤC BẢNG BIỂU, HÌNH ẢNH Bảng 1. Biểu diễn cơ sở dữ liệu giao tác ngang ................................................ 6 Bảng 2. Biểu diễn cơ sở dữ liệu giao tác dọc .................................................... 7 Bảng 4. Cơ sở dữ liệu minh họa thực hiện thuật toán COFI-tree................ 22 Bảng 5. Các mục dữ liệu và độ hỗ trợ ............................................................. 22 Bảng 6. Các mục dữ liệu thường xuyên đã sắp thứ tự .................................. 22 Bảng 7. Các mục dữ liệu trong giao tác sắp xếp giảm dần theo độ hỗ trợ .. 23 Hình 1. Hình cây FP-Growth........................................................................... 23 Hình 2. Cây COFI-tree của mục D.................................................................. 24 Hình 3. Các bước khai phá cây D-COFI-tree ................................................ 25 Bảng 8. Cơ sở dữ liệu giao tác cho khai phá tập mục cổ phần cao .............. 29 Bảng 9. Xét CSDL Bảng 8 với minShare ≥ 30% ........................................... 30 Bảng 10. Biểu diễn tất cả tập mục cổ phần cao.............................................. 31 Bảng 11. CSDL minh họa có trường hợp hai hàm tới hạn bằng nhau ....... 39 Bảng 12. CSDL minh họa trường hợp hai hàm tới hạn luôn bằng nhau. ... 40 Bảng 13. Giá trị của hai hàm tới hạn với k=1. ............................................... 40 Bảng 14. Các giá trị lmv và hàm tới hạn với k=1. ......................................... 43 Bảng 15. Các giá trị lmv và hàm tới hạn với k=2. ........................................ 43 Bảng 16. các giá trị lmv và hàm tới hạn với k=3. .......................................... 44 Bảng 17. Cơ sở dữ liệu giao tác trong khai phá tập mục lợi ích cao............ 47 Bảng 18. Bảng lợi ích các mục dữ liệu ............................................................ 47 Bảng 19. Cở sở dữ liệu giao tác lợi ích cao với khai pháp cổ phần cao ....... 49 Giao diện 1. Sheet HUI, dữ liệu được sinh bởi chương trình ....................... 54 Giao diện 2. Sheet Profit, dữ liệu nhập vào bằng tay .................................... 54 Giao diện 3. Giao diện chương trình chính .................................................... 55 Giao diện 4. Kết quả thực hiện với ngưỡng lợi ích 30% ............................... 56 4 GIỚI THIỆU Sự phát triển nhanh chóng các ứng dụng CNTT và Internet vào nhiều lĩnh vực đời sống, 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 từ các cơ sở dữ liệu lớn, hỗ trợ 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, các nhà nghiên cứu đã phát triển các phương pháp, kỹ thuật và phần mềm mới hỗ trợ tiến trình khám phá, phân tích, tổng hợp thông tin. Khai phá dữ liệu và khám phá tri thức (Data mining and knowledge discovery) là một lĩnh vực quan trọng của ngành Công nghệ thông tin. Đây là lĩnh vực đã thu hút đô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 được biết đến như một bài toán con của khai phá luật kết hợp được giới thiệ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ị, phân tích sở thích mua của khách hàng bằng cách tìm ra những mặt hàng khác nhau được khách hàng mua trong cùng một lần mua. Những thông tin như vậy giúp người quản lý kinh doanh tiếp thị chọn lọc và thu xếp không gian bày hàng hợp lý hơn, giúp cho việc kinh doanh hiệu quả hơn. Khai phá tập mục thường xuyên gặp khó khăn khi xử lý cơ sở dữ liệu lớn. Vì thế đã có nhiều nghiên cứu về cách thức mở rộng, ứng dụng. Rất nhiều kết quả nghiên cứu đã được công bố nhưng vấn đề khai phá tập mục thường xuyên vẫn được coi là bài toán khó. Với mục đích đóng góp vào lĩnh vực sôi động này, tác giả tìm hiểu và nghiên cứu về các thuật toán khai phá tập mục thường xuyên phổ biến nhất, đem lại một cái nhìn tổng quát về khai phá tập mục thường xuyên và luật kết hợp. 5 I. KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN I.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ư 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ị [9] 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 độ 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ập mục thường xuyên thỏa mãn ngưỡng độ hỗ trợ cho trước. Kể từ khi Agrawa đề 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 Protein và DNA, mở rộng truy vấn, phát hiện xâm nhập mạng…[13, 14, 15, 16]. 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ê, 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. 6 Để đá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áp tập mục thường xuyên. I.2. Một số khái niệm cơ bản về tập mục Định nghĩa 1.1: Cho tập mục (item) I={I1,I2,…,Im}. 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à 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à 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 diễ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. 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 đó. Giao tác Mục dữ liệu T1 A, C, D T2 B, C, E T3 A, B, C, E T4 B, E Bảng 1. Biểu diễn cơ sở dữ liệu giao tác ngang 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. 7 Mục dữ liệu Các giao tác A T1, T3 B T2, T3, T4 C T1, T2, T3 D T1 E T2, T3, T4 Bảng 2. Biểu diễn cơ sở dữ liệu giao tác dọc Biểu diễn ma trận nhị phân: Cơ sở dữ liệu giao tác trên tập mục (item) được biểu diễn bởi ma trận nhị phân M = (mpq)mxn ở đó 1 ݇ℎ݅ ݅௣ ∈ ܶ௤
݉௣௤ = ൜ 0 ݇ℎ݅ ݅௣ ∉ ܶ௤ Mục T1 T2 T3 T4 A 1 0 1 0 B 0 1 1 1 C 1 1 1 0 D 1 0 0 0 E 0 1 1 1 Bảng 3. Biểu diễn cơ sở dữ liệu giao tác ma trận I.3. 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. Độ hỗ trợ (Support) của tập mục X trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm của các giao tác chứa tập mục X trên tổng số giao tác trong DB, tức là: sup( X ) = | {T ∈ DB | T ⊇ X } | | DB | Định nghĩa 1.3: Cho tập mục X⊆I với ngưỡng hộ trợ tối thiểu (minimum support) minsup ∈ [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 8 thiểu minsup nếu sup(X) ≥ minsup, 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à một 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) luật kết hợp, 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) luật kết hợp, ký hiệu là 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 ) = sup( X ∪ Y ) sup( X ) Độ 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(X/Y): P( X / Y ) = | {T ∈ DB | X ⊆ T ∧ Y ⊆ T } | | {T ∈ DB | X ∪ Y ⊆ T } | sup( X ∪ Y ) = = | {T ∈ DB | X ⊂ T } | | {T ∈ DB | X ⊆ T } | sup( X ) Và ta có 0 ≤ conf(X →Y ) ≤ 1. I.3.1. Bài toán khai phá luật kết hợp Xác định tất cả X⇒ ⇒Y thỏa mãn độ hỗ trợ và độ tin cậy tối thiểu thì luật X⇒ ⇒Y được gọi là luật kết hợp mạnh. 9 I.3.2. Một số tính chất 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ó tính chất sau: (1) Nếu X, Y là các tập mục 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 là 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) là tính chất quan trọng, nó đượ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. I.4. Mô tả bài toán khai phá luật kết hợp Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Vấn đề này được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất lần đầu vào năm 1993 [9]. Sau đó năm 1996 được Rakesh Agrawal, Heikki Mannia, Ramakrishnan Srikant, Hannu Toivonen, A.Inkeri Verkamo tiếp tục cải tiến. Ngày nay bài toán khai thác các luật kết hợp nhận được rất nhiều sự quan tâm của nhiều nhà khoa học. Việc khai thác các luật như thế nào vẫn là một trong các phương pháp khai thác mẫu phổ biến nhất trong việc khám phá tri thức và khai thác dữ liệu (KDD – Knowledge Discovery and Data Minning). Mục đích chính của khai phá dữ liệu là trích rút tri thức một cách tự động, hiệu quả và “thông minh” từ kho dữ liệu. Trong hoạt động sản xuất kinh doanh, ví dụ kinh doanh các mặt hàng tại siêu thị, các nhà quản lý rất thích có được những thông tin mang tính thống kê như: “90% phụ nữ có xe máy màu đỏ và đeo đồng hồ Thụy Sỹ thì dùng nước hoa hiệu Chanel” hoặc “70% khách hàng là công nhân thì mua TV thường mua loại 21 inches”. Những thông tin như vậy rất hữu ích trong việc định hướng kinh doanh. Vậy vấn đề đặt ra là liệu có tìm được các luật như vậy bằng các 10 công cụ khai phá dữ liệu hay không? Câu trả lời là hoàn toàn có thể. Đó chính là nhiệm vụ khai phá luật kết hợp. Giả sử chúng ta có một CSDL D. Luật kết hợp cho biết phạm vi mà trong đó sự xuất hiện của tập các thuộc tính S nào đó trong các bản ghi (records) của D sẽ kéo theo sự xuất hiện của một tập những thuộc tính khác U cũng trong những bản ghi đó. Mỗi luật kết hợp được đặc trưng bởi một cặp tỉ lệ hỗ trợ (support ration). Mỗi tỉ lệ hỗ trợ được biểu diễn bằng tỉ lệ % những bản ghi trong D chứa cả S và U. Vấn đề khám phá luật kết hợp được phát biểu như sau: Cho trước tỉ lệ hỗ trợ (support ration) θ và độ tin cậy (confidence) β Đánh số tất cả các luật trong D có các giá trị tỉ lệ hỗ trợ và tin cậy lớn hơn θ và β tương ứng. Ví dụ: Gọi D là CSDL mua bán và với θ = 40%, β = 90% Vấn đề phát hiện luật kết hợp được thực hiện như sau: Liệt kê (đếm) tất cả những quy luật chỉ ra sự xuất hiện một số các mục kéo theo một số mục khác. Chỉ xét những quy luật mà tỉ lệ hỗ trợ lớn hơn 40% và độ tin cậy lớn hơn 90% Hay chúng ta hãy tưởng tượng, một công ty bán hàng qua mạng Internet. Các khách hàng được yêu cầu điền vào các mẫu bán hàng để công ty có một CSDL về các yêu cầu của khách hàng. Giả sử công ty quan tâm đến mối quan hệ “tuổi, giới tính, nghề nghiệp => sản phẩm”. Khi đó có thể có rất nhiều câu hỏi tương ứng với luật trên. Ví dụ: trong lứa tuổi nào thì những khách hàng nữ là công nhân đặt mua mặt hàng gì đó, ví dụ áo dài chẳng hạn là nhiều nhất (thỏa mãn một ngưỡng nào đó)? 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 minconf. 11 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 2 bài toán con. Bài toán thứ nhất: 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: 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 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. Bài toán thứ hai có thể giải quyết như sau: Giả sử X là tập mục thường xuyên, ta sinh ra luật kết hợp bằng cách tìm mọi Y là tập con của X, kiểm tra độ tin cậy của X\Y ⇒ Y có thỏa mãn độ tin cậy tối thiểu không. I.4.1. Một số 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: 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 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 2 tiêu chí: 12 - 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 CSDL có n mục, lần lặp thứ k phải kiểm tra độ hỗ trợ của tất cả Ckn tập ứng viên có k mục Duyệt theo chiều sâu là duyệt qua CSDL đã được chuyển thành cấu trúc dạng cây, quá trình duyệt gọi đệ quy theo chiều sâu của cây. Với cơ sở dữ liệu có n mục dữ liệu, không gian tìm kiếm có 2n tập con, rõ ràng đây là bài toán NP khó, do đó 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 2 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ứ 2 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. I.4.2. Một số tiếp cận khai phá luật kết hợp Luật kết hợp nhị phân (binary association rule hoặc boolean associaiton rule): là hướng nghiên cứu đầu tiên của luật kết hợp. Hầu hết các nghiên cứu ở thời kỳ đầu về luật kết hợp đều liên quan đến luật kết hợp nhị phân. Trong dạng luật kết hợp này, các mục (thuộc tính) chỉ được quan tâm là có hay không xuất hiện trong giao tác của CSDL chứ không quan tâm về “mức độ” xuất hiện. Ví dụ: Trong hệ thống tính cước điện thoại thì việc gọi 10 cuộc điện thoại và 1 cuộc được xem là giống nhau. Thuật toán tiêu biểu nhất khai phá dạng luật này là thuật toán Apriori và các biến thể của nó. Đây là dạng luật đơn giản và các luật khác cũng có thể chuyển về dạng luật này nhờ một số phương pháp như rời rạc hóa, mờ hóa… Một ví dụ về dạng luật này: “gọi liên tỉnh = ‘yes’ AND gọi 13 di động = ‘yes’ => gọi quốc tế =’yes’ AND gọi dịch vụ 108 = ‘yes’, với độ hỗ trợ 20% và độ tin cậy 80%. Luật kết hợp có thuộc tính số và thuộc tính hạng mục (quantitative and categorial association rule): Các thuộc tính của các CSDL thực tế có kiểu rất đa dạng (nhị phân – binary, số - quantitative, hạng mục – categorial,…). Để phát hiện luật kết hợp với các thuộc tính này, các nhà nghiên cứu đã đề xuất một số phương pháp rời rạc hóa nhằm chuyển dạng luật này về dạng nhị phân để có thể áp dụng các thuật toán đã có. Một ví dụ về dạng luật này “phương thức gọi” = ‘Tự động’ AND giờ gọi IN [’23:00:39..23:00:59’] AND thời gian đàm thoại IN [‘200..300’] => gọi liên tỉnh =’có’, với độ hỗ trợ là 23.53% và độ tin cậy là 80%”. Luật kết hợp tiếp cận theo hướng tập thô (mining association rules base on rough set): Tìm kiếm luật kết hợp dựa trên lý thuyết tập thô. Luật kết hợp nhiều (multi – level association rule): với cách tiếp cận theo luật này sẽ tìm kiếm thêm những luật dạng “mua máy tính PC => mua hệ điều hành AND mua phần mềm tiện ích văn phòng,…” thay vì chỉ những luật quá cụ thể như “mua máy tính IBM PC => mua hệ điều hành Microsoft Windows AND mua phần mềm tiện ích văn phòng Microsoft Office,..”. Như vậy dạng luật đầu là dạng luật tổng quát hóa của dạng luật sau và tổng quát theo nhiều mức khác nhau. Luật kết hợp mờ (fuzzy association rule): với những hạn chế còn gặp phải trong quá trình rời rạc hóa các thuộc tính số (quantitave attributes), các nhà nghiên cứu đã đề xuất luật kết hợp mờ nhằm khắc phục các hạn chế trên và chuyển luật kết hợp về dạng tự nhiên hơn, gần gũi hơn với người sử dụng. Một ví dụ của dạng này là: “thuê bao tư nhân =’yes’ AND thời gian đàm thoại lớn AND cước nội tỉnh = ‘yes’ => cước không hợp lệ =’yes’, với độ hỗ trợ là 4% và độ tin cậy là 85%”. Trong luật trên, điều kiện thời gian đàm thoại lớn ở về trái của luật là một thuộc tính đã được mờ hóa. Luật kết hợp với thuộc tính được đánh trọng số (association rule with weighted items): trong thực tế, các thuộc tính trong CSDL không phải lúc nào 14 cũng có vai trò như nhau. Có một số thuộc tính được chú trọng hơn và có mức độ quan trọng cao hơn hơn các thuộc tính khác. Ví dụ khi khảo sát về doanh thu hàng tháng, thông tin về thời gian đàm thoại, vùng cước là quan trọng nhiều hơn so với thông tin về phương thức gọi… Trong quá trình tìm kiếm luật, chúng ta sẽ gán thời gian gọi, vùng cước các trọng số lớn hơn thuộc tính phương thức gọi. Đây là hướng nghiên cứu rất thú vị và đã được một số nhà nghiên cứu đề xuất cách giải quyết bài toán này. Với luật kết hợp có thuộc tính được đánh trọng số, chúng ta sẽ khai thác được những luật “hiếm” (tức là có độ hỗ trợ thấp nhưng có ý nghĩa đặc biệt hoặc mang rất nhiều ý nghĩa). Khai thác luật kết hợp song song (parallel mining of association rules): Bên cạnh khai thác luật kết hợp tuần tự, các nhà làm tin học cũng tập trung nghiên cứu các thuật giải song song cho quá trình phát hiện luật kết hợp. Nhu cầu song song hóa và xử lý phân tán là cần thiết bởi kích thước dữ liệu ngày càng lớn đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ của hệ thống phải được đảm bảo. Có rất nhiều thuật toán song song khác nhau đã đề xuất để có thể không phụ thuộc vào phần cứng. Bên cạnh những nghiên cứu về những biến thể của luật kết hợp, các nhà nghiên cứu còn chú trọng đề xuất những thuật toán nhằm tăng tốc độ quá trình tìm kiếm tập phổ biến từ CSDL. Ngoài ra, còn một số phương pháp nghiên cứu khác về khai thác luật kết hợp như: khai thác luật kết hợp trực tuyến, khai thác luật kết hợp được kết nối trực tiếp đến các kho dữ liệu đa chiều (Multidimensional data, data warehouse) thông qua công nghệ OLAP (Online Analysis Processing), MOLAP (Multidimensional OLAP), ROLAP (Relational OLAP), ADO (Active X Data Object) for OLAP… I.5. Một số thuật toán khai phá tập mục thường xuyên và luật kết hợp I.5.1. Thuật toán AIS Thuật toán hoàn toàn sử dụng chiến lược “vét cạn”, xem xét toàn bộ các tập mục thường xuyên bằng cách sinh tổ hợp tập các mục và chạy kiểm tra. 15 I.5.2. Thuật toán SETM Được đề xuất do mong muốn dùng SQL để tìm các tập mục thường xuyên. Cũng giống như thuật toán AIS, SETM cũng sinh ra các tập ứng viên dựa trên các giao dịch đọc được từ CSDL. Vì thế, nó sinh ra và đếm mỗi tập mục ứng cử viên mà thuật toán AIS sinh ra. Tuy nhiên để phép nối (JOIN) chuẩn của SQL, SETM chia sự phát sinh ứng cử viên từ việc đếm. I.5.3. Thuật toán CHARM Thực hiện trên cả không gian các tập phổ biến và không gian các tập định danh. CHARM không tìm tất cả các tập con có thể của tập mục mà thuật toán kết hợp tìm tập đóng hiệu quả hơn (bottom – up). Nếu CSDL của tập mục là lớn và tập mục thường xuyên là dày thì CHARM duyệt cả không gian tập mục và tập định danh đồng thời sẽ bỏ qua nhiều mức để tìm tập phổ biến đóng thay cho việc tính toán nhiều tập con không đóng. I.5.4. Thuật toán APRIORI Ý tưởng chính của thuật toán này là: 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ỏ bớt đi những tập mục ứng viên không thỏa mãn ngưỡng hỗ trợ tối thiểu (minsup). Cơ sở của thuật toán 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”. Thuật toán giúp tỉa bớt những tập ứng viên có tập con không thường xuyên trước khi tính độ hỗ trợ. Nhược điểm của thuật toán là chi phí sinh ra số lượng khổng lồ tập ứng viên và phải duyệt CSDL nhiều lần. I.5.5. Thuật toán FP-Growth Phát triển từ thuật toán Apriori, J.Han, J Pei, Y.Yin và R.Mao đã đề xuất thuật toán FP-growth [14] nhằm khắc phục những hạn chế của thuật toán Apriori. Thuật toán này được xây dựng với ba kỹ thuật chính là: Nén dữ liệu thích hợp vào một cấu trúc cây gọi là FP-tree. Chỉ có 1–tập mục ở trong cây và các nút của cây được sắp xếp để các nút xuất hiện thường xuyên hơn có thể dễ dàn chia sẻ với các nút xuất hiện ít hơn; Thực hiện phương pháp khai phá phát 16 triển (growth) từng đoạn dựa trên cây FP-tree gọi là phương pháp FP-growth; Kỹ thuật tìm kiếm được dùng ở đây là dựa vào sự phân chia, “chia để trị”, phân rã nhiệm vụ khai phá thành nhiệm vụ nhỏ hơn. I.6. Thuật toán Apriori Bước 1: Đếm 1-tập mục Bước lặp: - Kết hợp các (k-1)-tập mục sinh ra tập ứng viên Ck - Tỉa các kết nối để thu được k-tập mục, xác định các tập mục thường xuyên dựa trên độ hỗ trợ. I.6.1. Ý tưởng thuật toán Apriori Apriori là một giải thuật được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất lần đầu vào năm 1993 [9]. Thuật toán tìm giao dịch t có độ hỗ trợ và độ tin cậy thỏa mãn lớn hơn một ngưỡng giá trị nào đó. Thuật toán được tỉa bớt những tập ứng viên có tập con không thường xuyên trước khi tính độ hỗ trợ. Thuật toán Apriori tính tất cả các tập ứng cử của tập k trong một lần duyệt CSDL. Apriori dựa vào cấu trúc cây băm (hashtree). Tìm kiếm đi xuống trên cấu trúc cây mỗi khi ta chạm vào lá, ta tìm được một tập ứng cử viên có tiền tố chung được bao gồm trong các giao dịch. Sau đó các tập ứng cử này được tìm trong giao dịch đã được ánh xạ trước đó. Trong trường hợp tìm thấy biến đếm được tăng lên 1. I.6.2. Thuật toán Apriori Input: CSDL D, minsup. Output: Tập các tập mục thường xuyên L1= {Các 1-tập mục thường xuyên} 17 k=2; While(Lk-1!=∅) { Ck = apriori_gen(Lk-1, minsup); //các ứng cử mới theo chương trình con dưới đây. for(∀ giao dịch t∈D) { Ct=Subset(Ck,t);//ứng cử viên được chứa trong t for(∀ứng cử c∈Ct) c.count++; } Lk={c∈Ck|c.count ≥ minsup} k++; } Return L=∪kLk′; //sinh tập ứng viên mới (**) void apriori_gen(Lk-1, minsup) { for(∀itemset l1∈Lk-1) for(∀itemset l2∈Lk-1) if((L1(1)==L2(1)&&L1(2)==L2(2)&&…&&L1(k-2)==L2(k-2) &&L1(k-1)==L2(k-1)) { c=L1 kết nối với L2; if(has_infrequent_subset(c, Lk-1)) delete c; else add c to Ck; 18 } Return Ck; } Boolean has_infrequent_subset(c,Lk-1) { for(∀(k-1)-subset s ∈ c) if(s ∉Lk-1)return TRUE; else return FALSE; } I.6.3. Giải thích Lần duyệt đầu tiên, sẽ tính số lần xuất hiện của mỗi mục để xác định các 1-tập mục thường xuyên. Lần duyệt thứ k (k≥2) sẽ bao gồm 2 giai đoạn: Giai đoạn 1: tập mục thường xuyên Lk-1 đã tìm thấy ở các lần duyệt thứ k-1 được sử dụng để sinh ra các tập ứng cử viên bằng việc sử dụng hàm apriori_gen. 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-1 với chính nó. Hai tập mục l1 và l2 của Lk-1 được 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(k1)==L2(k-1) Giai đoạn 2: Dựa vào CSDL, tính độ hỗ trợ của các tập ứng viên trong Ck. Các ứng viên trong Ck mà được chứa trong giao dịch T có thể được xác định một cách hiệu quả bằng việc sử dụng cây băm được mô tả như sau: Trong giai đoạn 2 (giai đoạn sửa, tỉa): xóa bỏ các tập c ∈ Ck sao cho một vài (k-1)–tập mục con của c không nằm trong Lk-1. Thủ tục này là đầy đủ đối với bất kỳ tập nào Lk với độ hỗ trợ tối thiểu thì các tập con kích cỡ (k-1) cũng có độ hỗ trợ tối thiểu, do đó nếu ta mở rộng mỗi tập trong Lk-1 với tất cả các tập