Chương 1: Tổng quan Phần đầu của chương này sẽ giới thiệu tổng quan quy trình khai phá dữ liệu (data mining) một cách ngắn gọn. Luật kết hợp trình bày trong phần tiếp theo được xem như là một kỹ thuật khai phá dữ liệu. Khai phá dữ liệu Khả năng sản sinh và thu thập dữ liệu đã tăng lên rất nhanh trong thập niên gần đây.Các tiến bộ trong thu thập dữ liệu khoa học và thương mại như thiết bị mã vạch, bộ cảm biến, vệ tinh không gian,. đã làm dữ liệu trở nên “ngập lụt”.
Bên cạnh đó, công nghệ lưu trữ cũng có tiến bộ. Con người đã tạo ra những thiết bị lưu trữ nhanh, rẻ, dung lượng lớn như đĩa từ, đĩa CD-ROM. Chúng ta cần có công nghệ mới hay công cụ với khả năng thông minh để tự động biến đổi dữ liệu đã được xử lý thành những thông tin và tri thức có ích. Thuật ngữ phát hiện tri thức trong cơ sở dữ liệu (knowledge discovery in databases - KDD) đã trở nên phổ biến.
Quá trình phát hiện tri thức phải trải qua một số bước tương tác và lặp. Xen giữa các bước là việc ứng dụng các giải thuật để trích rút ra các mẫu dữ liệu, gọi là khai phá dữ liệu (data mining). Theo [1], các bước cơ bản của quá trình phát hiện tri thức gồm: 1. Sau khi phân tích mục đích của người sử dụng cuối và nhận về các tri thức cần thiết, chúng ta chọn ra các tập dữ liệu đích.
Điều này có nghĩa là tập trung vào một tập con các biến hay dữ liệu mẫu. Dữ liệu đích được tiền xử lý và làm sạch để loại bỏ những dữ liệu bẩn và ngoại lai. Đưa ra những đặc trưng có ích biểu diễn dữ liệu. Mục tiêu của quá trình phát hiện tri thức là dự đoán các giá trị tương lai của các biến quan tâm hoặc tìm ra những mẫu dữ liệu mà con người có thể hiểu.
Giải thuật khai phá dữ liệu thích hợp được lựa chọn và áp dụng. Có một số thuật giải: kết hợp, phân lớp, phân nhóm,. Nguyễn Hồng Phương 8/78 Phát hiện các luật kết hợp trong cơ sở dữ liệu Chọn Tiền xử lý Biến đổi Khai phá Thông dịch / dữ liệu Đánh giá Dữ liệu Dữ liệu tiền Dữ liệu biến Dữ liệu mục tiêu xử lý đổi Mẫu Tri thức Hình 1.1: Quá trình phát hiện tri thức 1. Luật kết hợp Bài toán phát hiện luật kết hợp từ dữ liệu được đề xuất trong [8] và gọi là "bài toán cái rỏ hàng".
Bài toán cho một tập các mặt hàng và một tập lớn các giao dịch. Nhiệm vụ là tìm ra mối quan hệ giữa các mặt hàng trong rỏ hàng. Ralf Rantzau [1] có trình bày các định nghĩa liên quan đến luật kết hợp. Định nghĩa chính thức Cho I = {I1 , I 2 ,., I m } là một tập các thuộc tính gọi là các mục (items).
Một tập con X ⊆ I được gọi là một tập mục (itemset). Một k-tập mục (k-itemset) là một tập mục chứa k mục. Cho cơ sở dữ liệu D = {T1 ,T2 ,.,Tn } là một tập các giao dịch, trong đó mỗi giao dịch Ti , i ∈ {1,., n} là một tập mục. Một giao dịch T chứa một tập mục X nếu X ⊆ T.
Mỗi tập mục có một thông số thống kê gọi là độ hỗ trợ (support) hay tần số (frequency). Độ hỗ trợ s của một tập mục X là tỉ lệ các giao dịch trong cơ sở dữ liệu D chứa tập mục X , tức là: {T ∈ D X ⊆ T } s( X ) = Một luật kết hợp là một luật có dạng , trong đó và ∅. X⇒ Y X ⊂ I Y ⊂I X Y X được gọi là phần đầu của luật (antecedent) và Y được gọi là phần thân của luật (consequent). Luật X ⇒Y có độ hỗ trợ s trong tập giao dịch D nếu s% các giao dịch trong D chứa X ∪Y : X∪ Y s= D Nguyễn Hồng Phương 9/78 Phát hiện các luật kết hợp trong cơ sở dữ liệu Luật X ⇒ Y có độ tin cậy c trong tập giao dịch D nếu c% các giao dịch trong D chứa X thì cũng chứa Y : X∪ Y s( X ∪ Y) c= hay c( X, Y) = X s( X ) Độ tin cậy biểu thị khả năng của một luật.
Một ngưỡng c min của độ tin cậy (còn gọi là độ tin cậy tối thiểu - minconf) được sử dụng để loại bỏ những luật không đủ mạnh. Một ngưỡng smin của độ hỗ trợ (còn gọi là độ hỗ trợ tối thiểu - minsupp) loại bỏ các luật mà số lượng các giao dịch chứa phần đầu và thân luật nhỏ hơn một lượng xác định. Các tập mục với độ hỗ trợ tối thiểu được gọi là các tập mục thường xuyên (frequent itemsets) hay các tập mục lớn (large itemsets). Bài toán tìm kiếm các luật kết hợp được phát biểu như sau: Cho một tập mục I , một cơ sở dữ liệu các tập mục D , một ngưỡng hỗ trợ smin và một ngưỡng tin cậy c min , chúng ta phải tìm ra các luật kết hợp X ⇒Y trong D với độ hỗ trợ s ≥ smin và độ tin cậy c ≥ cmin 1.
Định nghĩa thay thế Cho D = {T1 , T2 ,., Tn } là một quan hệ trên sơ đồ quan hệ I = {I1 , I 2 ,., I m } , trong đó mỗi thuộc tính I i , i ∈ {1,., m} nhận hai giá trị {true, false}. Nói theo cách khác, D là một tập các vector nhị phân chiều dài m. Với mỗi hàng T của quan hệ D thỏa mãn điều kiện ∀ i ∈ {1,. Độ hỗ trợ của một tập mục X ⊆ I là: {T ∈ D∀ I ∈ X :T[i]} i s( X) = D Hơn nữa, chúng ta có thể dùng cách tiếp cận xác suất để định nghĩa độ hỗ trợ và độ tin cậy.
X và Ylà các tập mục, trong đó X ⊂ I , Y ⊂ I và X ∩ Y = ∅. P( X) là xác suất tất cả các mục trong X có trong một giao dịch. Độ hỗ trợ s của một luật X ⇒Y được định nghĩa là s = P( X ∪Y) và độ tin cậy c là xác suất có điều kiện của Y khi có X, tức là Ví dụ: Bảng 1.2 là một ví dụ về cơ sở dữ liệu các giao dịch trong siêu thị. I là một tập các mặt hàng bao gồm các mặt hàng A, B, C, D.
Mỗi dòng của bảng chứa một định danh giao dịch TID mô tả một giao dịch mua hàng của một khách hàng, hay nói khác đi đó là một rỏ các mặt hàng khách hàng đã quyết định mua. Độ hỗ trợ của tập mục {A, B} là 0. Độ hỗ trợ của tập {A, B, D} là 0. Do đó, độ tin cậy của luật {A, B}⇒{D} là 0.
Nếu độ hỗ trợ tối thiểu smin nhỏ hơn hoặc bằng Nguyễn Hồng Phương 10/78 Phát hiện các luật kết hợp trong cơ sở dữ liệu 0.3 và độ tin cậy cmin nhỏ hơn hoặc bằng 0.75 thì luật này được coi là luật kết hợp. Chúng ta có thể phát biểu "Nếu khách hàng mua mặt hàng A và B thì có cơ hội 75% khách hàng cũng sẽ mua D". TID Rỏ hàng 1 {A, C} 2 {B} 3 {A, B, C, D } 4 {B, D} 5 {A, B, D} 6 {A, B} 7 {A, D} 8 {B, C, D} 9 {C, D} 10 {A, B, D} Bảng 1.2: Ví dụ cơ sở dữ liệu 1. Các vấn đề về phát hiện luật kết hợp trong cơ sở dữ liệu Các nghiên cứu đều tập trung vào phát hiện các luật kết hợp trong cơ sở dữ liệu giao dịch và cơ sở dữ liệu quan hệ.
Cơ sở dữ liệu giao dịch là cơ sở dữ liệu có chứa các giao dịch mà mỗi giao dịch thể hiện trạng thái "có" hay "không" sự xuất hiện của các thuộc tính. Chính vì thế, nó còn được gọi là cơ sở dữ liệu nhị phân. Cơ sở dữ liệu quan hệ, như đã biết, có rất nhiều thuộc tính như thuộc tính nhị phân, thuộc tính phạm trù, thuộc tính định lượng (số),… Đối với cơ sở dữ liệu giao dịch, để phát hiện các luật kết hợp trong đó, đã có rất nhiều công trình được đăng trên các tạp chí, kỷ yếu hội thảo. Thuật toán Apriori và các cải tiến của nó [2][8] đã được đề xuất để thực hiện nhiệm vụ này.
Một đặc điểm của những thuật toán này là tốn khá nhiều chi phí cho việc sinh ra các tập mục ứng cử. Để giải quyết vấn đề này, [15][16][32] đã đề xuất sử dụng cây mẫu thường xuyên (FP-tree) để phát hiện các tập mục thường xuyên, tránh được việc phải sinh quá nhiều tập mục ứng cử. Xoay quanh bài toán đối với cơ sở dữ liệu giao dịch, một số bài báo cũng trình bày khía cạnh khác: luật kết hợp đa mức [19][22][23][24][25]. Đối với cơ sở dữ liệu quan hệ, vấn đề trở nên phức tạp hơn rất nhiều.
Vì cơ sở dữ liệu quan hệ chứa các thuộc tính định lượng, phạm trù,… nên nảy sinh công đoạn xử lý các thuộc tính này trước khi sinh các tập mục thường xuyên. Các bài toán ở đây gồm: phát hiện luật kết hợp định lượng và phạm trù [1], phát hiện luật kết hợp mờ và luật kết hợp mờ có trọng số [5][6][13][14][28][29]. Nguyễn Hồng Phương 11/78 Phát hiện các luật kết hợp trong cơ sở dữ liệu Bản luận văn này trình bày các vấn đề trên theo cấu trúc sau: Phát hiện các luật kết hợp trong cơ sở dữ liệu Phát hiện các luật kết hợp Phát hiện các luật kết hợp trong cơ sở dữ liệu giao dịch trong cơ sở dữ liệu quan hệ Kiểu Apriori Sử dụng Luật đa Luật định Luật mờ Luật mờ FP-Tree mức lượng có trọng số Hình 1.3: Các vấn đề trình bày trong báo cáo Sau đó là phần cài đặt thử nghiệm các thuật toán và kết luận. Nguyễn Hồng Phương 12/78 Phát hiện các luật kết hợp trong cơ sở dữ liệu Chương 2: Luật kết hợp cơ bản Chương này giới thiệu một số thuật giải phát hiện các luật kết hợp trong cơ sở dữ liệu giao dịch.
Cách làm ở đây chia ra thành hai nhiệm vụ nhỏ hơn: - Tìm kiếm các tập mục với độ hỗ trợ lớn hơn hoặc bằng ngưỡng tối thiểu smin - Xây dựng các luật kết hợp với độ tin cậy lớn hơn hoặc bằng ngưỡng tối thiểu cmin 2. Hai tính chất 2. Tính chất 1 Nếu một tập mục là nhỏ (không thường xuyên) thì tất cả các siêu tập (tập cha) của nó cũng là nhỏ (không thường xuyên).1: A nhỏ thì superset(A) cũng nhỏ 2. Tính chất 2 Nếu một tập mục là lớn (thường xuyên) thì các tập con của nó cũng lớn (thường xuyên).