Chương 1: Tổng quan Chương này trình bày tổng quan về lĩnh vực nghiên cứu. Chương 2: Cơ sở lý thuyết Trong chương này, luận văn sẽ trình bày một số khái niệm, định nghĩa và tính chất của tập phổ biến, tập phổ biến đóng một số tiếp cận trong khai thác tập phổ biến. Ngoài ra, trong chương cũng trình bảy các thuật toán làm cơ sở nghiên cứu cho chương tiếp theo. Chương 3: Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến Trong chương này, luận văn sẽ trình bày các nghiên cứu về sử dụng cấu trúc vector bit trong khai thác dữ liệu, sử dụng phương pháp chia để trị và cắt tỉa trong khai thác ngang.
Chương 4: Kết quả thực nghiệm và đánh giá Chương này sẽ trình bày kết quả thực nghiệm và một số nhận xét đánh giá về vấn đề đã được nghiên cứu. Chương 5: Kết luận Chương này sẽ trình bày kết quả thực nghiệm và một số nhận xét đánh giá về vấn đề đã được nghiên cứu. Kết luận chương Các dữ liệu có ích tồn tại trong các CSDL có ý nghĩa rất lớn trong nhiều ngành, lĩnh vực. Do đó việc phát hiện và trích xuất các dữ liệu tìm ẩn từ các tập dữ liệu lớn ngày càng trở nên cần thiết, đặc biệt trong gia đoạn hiện nay khi mà sự phát triền nhanh chóng của các ứng dụng công nghệ thông tin ở nhiều lĩnh vực trong đời sống xã hội.
Trong chương này, luận văn trình bày tổng quan về lĩnh vực nghiên cứu khai thác dữ liệu. Trong khai thác dữ liệu, kỹ thuật khai tác tập phổ biến là một trong những lĩnh vực đang được quan tâm và nghiên cứu mạnh mẽ. Giới thiệu tổng quan Bài toán xác định luật kết hợp lần đầu tiên được Agrawal. R [3] giới thiệu vào năm 1993.
Khai phá luật kết hợp là một kỹ thuật được sử dụng trong khai phá dữ liệu nhằm tìm ra các phần tử thường xuyên xuất hiện lặp đi lặp lại (hay phổ biến) trong cơ sở dữ liệu, từ đó rút ra được các luật về ảnh hưởng của một tập phần tử dẫn đến sự xuất hiện của tập phần tử khác. Các thuật toán khai phá luật kết hợp tìm kiếm các mối liên kết giữa các phần tử trong cơ sở dữ liệu. Những nghiên cứu về luật kết hợp gần đây tập trung xây dựng các thuật toán khai phá luật kết hợp mới, hiệu quả hoặc cải tiến hay phát triển các thuật toán hiệu quả hơn từ các thuật toán đã có. Chúng ta xem xét một bài toán về khai phá luật kết hợp như sau: phân tích hóa đơn mua hàng của khách hàng khi đi siêu thị.
Việc khai phá luật kết hợp trong bài toán này nhằm tìm ra các luật kết hợp giữa các mặt hàng mà khách hàng đã mua. Thí dụ một số luật kết hợp rút ra được sau khi phân tích hóa đơn khách hàng mua: 60% khách hàng mà mua “bánh mì” tại siêu thị thì đều mua “sữa” chúng ta thấy có sự kết hợp giữa “bánh mì” với “sữa”. Những luật kết hợp như vậy rất có ích trong việc giúp các nhà quản lý nắm bắt được thói quen mua hàng của khách hàng khi mua một (hoặc một số) mặt hàng này thì khách hàng có xu hướng mua thêm một số mặt hàng nào nữa. Từ đó đề ra những chiến lược quản lý hợp lý.
Như vậy, khai phá luật kết hợp có thể giải quyết được bài toán hết sức đời thường như: khách hàng vào siêu thị sẽ mua mặt hàng nào? Những mặt hàng nào mà khách hàng kết hợp cùng mua. Tất nhiên, khai phá luật kết hợp cũng có nhiều ý nghĩa trong các lĩnh vực khác như tài chính, y học, công nghệ… Nhiệm vụ chính của khai phá luật kết hợp là phát hiện ra các tập con cùng xuất hiện trong một khối lượng giao tác lớn của một cơ sở dữ liệu cho trước. Nói cách khác, thuật toán khai phá luật kết hợp cho phép tạo ra các luật mô tả các sự kiện xảy ra đồng thời (một cách thường xuyên) như thế nào. Bài toán tìm luật kết hợp là bài toán cơ bản trong khai thác dữ liệu gồm hai bước chính: Bước 1: Tìm tất cả các tập phổ biến theo ngưỡng phổ biến cho trước, Bước 2: Tìm ra luật kết hợp dựa vào tập phổ biến đã tìm thấy ở Bước 1.
Nội dung luận văn này cũng đi sâu vào nghiên cứu thuật toán để tìm các tập phổ biến hiệu quả hơn. Các khái niệm và định nghĩa 2. Hạng mục Cho I là một tập các thuộc tính nhị phân. Cho I = {I1, I2, …, Im}, mỗi Ik (1km) là một hạng mục.
Tập hạng mục Một tập 𝑋 ⊆ 𝐼 là một tập các hạng mục. Cơ sở dữ liệu giao tác Một CSDL giao tác là một tập gồm nhiều hạng mục, mỗi hạng mục là một giao tác được định danh bởi một giá trị duy nhất là mã giao tác. Một CSDL giao tác trên I là một tập các định danh giao tác T = {t1, t2,…,tn}, với ti (1in) là một định danh giao tác trên I chứa một tập các danh mục dữ liệu X ⊆ I.1: Trong bài toán giỏ hàng, cơ sở dữ liệu giao tác là các lần mua hàng của mỗi khách hàng, cho biết trong một lần mua hàng, khách hàng mua những mặt hàng nào. Mã giao tác Nội dung giao tác 1 a, b, d, e 2 b, c, e 3 a, b, d, e 4 a, b, c, e 5 a, b, c, d, e 6 b, c, d Bảng 2.1 Cơ sở dữ liệu mẫu 2.
Độ phổ biến Cho CSDL bao gồm: Tập các danh mục I, tập danh mục X I và tập các giao tác D Độ phổ biến của X trong D có ký hiệu là sup(X) và được định nghĩa là số giao tác mà X xuất hiện trong D.2: Sử dụng CSDL ví dụ 2.1 với số lượng 6 giao tác. Tập danh mục {a, b, c, d, e} Với CSDL mẫu trong bảng 2.1, thì ta có: 7 Tập danh mục I = {a, b, c, d, e} và tập giao tác D gồm có 6 giao tác: {abde, bce, abde, abce, abcde, bcd} Độ phổ biến của tập danh mục X1 = {a} là số giao tác trong D có chứa {a}, do đó sup(X1) = 4 Như vậy tương tự ta có: X2 = {a, d} => độ phổ biến của X2 là sup(X2) = 3 2. Tập phổ biến: Tập X I được gọi là tập phổ biến nếu sup(X) minsup, với minsup là giá trị do người dùng chỉ định.3: Ta xét lại CSDL mẫu trong bảng 2.1, với minsup = 3 (50%) thì tập X2 = {a, d} là tập phổ biến vì có sup(X2) = 3 minsup. Tương tự ta có với X3 = {a, b, d} thì sup(X3) = 3 minsup và X3 cũng là tập phổ biến.
Ngược lại, với X4 = {b, c, d} thì sup(X4) = 2 < minsup, vì vậy X4 không phải là tập phổ biến. Tập phổ biến đóng: Cho I = {i1, i2, …, im} là tập các hạng mục. Cho T = {t1, t2, …, tn} là tập các mã giao tác. Kết nối Galois Ta có t : 2I → 2T được định nghĩa như hàm sau: t(X) = {t ∈ T | X ⊆ i(t)} (1) Ta có i : 2T → 2I được định nghĩa như hàm sau: i(Y ) = {i ∈ I | ∀t ∈ Y, t chứa x} (2) Ánh xạ (1): t(X) lấy tất cả tid của giao tác có chứa tập hạng mục X.
Ánh xạ (2): i(Y) lấy tất cả hạng mục tồn tại trong tất cả giao tác Y. Toán tử đóng: 𝒄 = 𝒊 ∘ 𝒕 Tập hạng mục X là tập đóng nếu c(X) = X. Tập phổ biến đóng: là tập hạng mục đóng thỏa ngưỡng minsup cho trước.4: Ta xét lại CSDL mẫu trong bảng 2. Kiểm tra ae, bc có phải là tập phổ biến đóng? Sử dụng toán tử đóng: c(ae) = i(t(ae)) = i(1345) = abe c(bc) = i(t(bc)) = i(2456) = bc Vậy bc là tập phổ biến đóng, ae không là tập phổ biến đóng.
8 Tóm tắt định nghĩa: Tập phổ biến đóng là tập phổ biến mà không có tập nào bao nó có cùng độ phổ biến. Với F là tập hợp gồm tất cả tập phổ biến. F = {X | X ⊆ I và sup(X) ≥ minsup} Gọi C là tập hợp gồm tất cả tập phổ biến đóng.5: Sắp xếp theo độ phổ Mã giao tác Nội dung giao tác biến giảm dần 1 a, c, f, m, p f, c, a, m, p 2 a, c, d, f, m, p f, c, a, m, p 3 a, b, c, f, g, m f, c, a, b, m 4 b, f, i f, b 5 b, c, n, p c, b, p Bảng 2.2 Cơ sở dữ liệu mẫu hạng mục được sắp xếp Giả sử minsup =2, chúng ta có thể tìm kiếm và sắp xếp danh sách các hạng mục phổ biến theo độ phổ biến giảm dần. Danh sách hạng mục đã được sắp xếp được gọi là f_list.
Trong ví dụ này f_list = {f: 4, c: 4, a: 3, b: 3, m: 3, p: 3}. Các hạng mục phổ biến trong mỗi giao tác đều được sắp xếp theo f_list và hiển thị trong cột thứ ba của bảng 2. Tập {fc} là một tập phổ biến gồm 2 hạng mục với độ phổ biến là 3, nhưng nó không phải là tập đóng, bởi vì có một tập cha {fcam} mà độ phổ biến cũng là 3. Vậy {fcam} là một tập phổ biến đóng.
Các tính chất của tập phổ biến Tính chất 1: Độ phổ biến của tập con lớn hơn tập cha. Cho hai tập phổ biến X, Y với X Y thì sup(X) sup(Y) Tính chất 2 : Mọi tập con của một tập phổ biến đều là tập phổ biến. 9 X là tập phổ biến và Y X thì sup(Y) sup(X) minsup, vì vậy Y cũng là tập phổ biến. Tính chất 3 : Mọi tập cha của một tập không phổ biến thì cũng không phổ biến.
X là tập không phổ biến và Y X thì sup(Y) sup(X) < minsup, vì vậy Y cũng không phải là tập phổ biến. Cách biểu diễn dữ liệu Trong các cơ sở dữ liệu quan hệ, thông thường dữ liệu sẽ được lưu trữ theo chiều ngang. Tức là các bảng dữ liệu hai chiều sẽ gồm N dòng tương ứng với các giao tác, và M cột tương ứng với các danh mục. Việc bố trí theo chiều ngang giúp cho việc xác định các danh mục thuộc về một giao tác đơn giản nhanh chóng.
Tuy nhiên khi cần xác định một danh mục cụ thể thuộc vào những giao tác nào thì cách bố trí theo chiều ngang lại gây ra khó khăn, khi đó ta phải duyệt tất cả các giao tác có trong CSDL và ghi nhận những giao tác có chứa danh mục cụ thể đó.