Chương 1. TỔNG QUAN VỀ KHAI PHÁ HỮU ÍCH CAO VÀ CHE GIẤU THÔNG TIN NHẠY CẢM TRONG KHAI PHÁ HỮU ÍCH CAO TỪ CƠ SỞ DỮ LIỆU GIAO TÁC Nội dung chính của chương tập trung nghiên cứu tổng quan về khai phá hữu ích cao và che giấu thông tin nhạy cảm trong khai phá hữu ích cao từ CSDL giao tác. Ngoài ra, việc lựa chọn một công cụ toán học để ứng dụng vào trong KPDL là quan trọng. Chính vì vậy, chương này cũng trình bày tổng quan về ứng dụng lý thuyết Giàn trong KPDL.
Phần cuối của chương mô tả về các CSDL được sử dụng để chạy thực nghiệm trong các thuật toán đề xuất của luận án. Kết quả nghiên cứu của chương này là cơ sở lý thuyết nền tảng để xây dựng các thuật toán che giấu thông tin nhạy cảm trong khai phá hữu ích cao được trình bày trong chương 2 và chương 3 của luận án. Tổng quan về khai phá hữu ích cao từ CSDL giao tác Khai phá hữu ích cao là một mở rộng của khai phá tập phổ biến khi vai trò của các mục trong CSDL được xem xét đến. Cơ sở lý thuyết của mô hình khai phá hữu ích cao được đề xuất trong [52] vào năm 2004 để khai phá từ CSDL giao tác tập các tập mục thỏa mãn một ngưỡng hữu ích tối thiểu cho trước và được gọi là khai phá tập mục hữu ích cao.
Cho đến nay, khai phá tập mục hữu ích cao có nhiều hướng nghiên cứu mở rộng để đáp ứng nhu cầu thực tế của xã hội: Khai phá tập mục hữu ích cao và phổ biến; khai phá tập mục hữu ích trung bình cao; khai phá luật kết hợp hữu ích cao,. Cơ sơ lý thuyết của khai phá hữu ích cao Phát biểu: Cho tập hữu hạn gồm các mục I = {x1 , x2 ,. , xm }, mỗi mục x ∈ I có một giá trị hữu ích ngoại, ký hiệu là p(x). , xk }, với X ⊆ I, k là độ dài của tập mục X.
, Tn } chứa n giao tác, mỗi giao tác Tc ⊆ I, 1 ≤ c ≤ n có một định danh gọi là T id. Mỗi mục x trong giao tác Tc kết hợp với một trọng số gọi là hữu ích nội (số lượng), ký hiệu là q(x, Tc ). 7 luan an Bảng 1.1: CSDL Giao tác D Tid Giao tác Tid Giao tác T1 A(3), B(1), C(5), F(2) T6 B(2), C(2), F(1), H(2) T2 D(2), E(3), F(3), G(1) T7 D(1), E(2), F(3), G(2), H(2) T3 A(2), B(3), C(1), D(3), E(5), F(1) T8 B(1), D(2), H(2) T4 A(3), B(2), C(1),E(2) T9 B(4), D(3), F(1) T5 D(2), E(3), F(5) T10 B(4), D(1), F(3) Bảng 1.2: Hữu ích ngoại của CSDL D. Mục A B C D E F G H Hữu ích 4 2 6 4 2 1 2 1 Ví dụ 1.
Cho I là tập hữu hạn gồm các mục {A, B, C, D, E, F, G, H}. Mỗi mục x ∈ I có một giá trị hữu ích ngoại p(x), cụ thể trong Bảng 1. CSDL giao tác D gồm 10 giao tác, cụ thể trong Bảng 1. CSDL này được sử dụng cho tất cả ví dụ trong toàn bộ nội dung của luận án này.
Khai phá tập mục hữu ích cao Khai phá tập mục hữu ích cao là quá trình khai thác từ CSDL giao tác tất cả các tập mục có giá trị hữu ích không nhỏ hơn một ngưỡng hữu ích tối thiểu cho trước. Giá trị hữu ích được xác định bởi các định nghĩa sau: Định nghĩa 1.1) - Giá trị hữu ích của tập mục X trong giao tác Tc , ký hiệu u(X, Tc ), được xác định: X u(X, Tc ) = u(x, Tc ) (1.2) x∈X - Giá trị hữu ích của tập mục X trong CSDL D, ký hiệu u(X), được xác định: X u(X) = u(X, Tc ) (1.3) X⊆Tc ∧Tc ∈D - Giá trị hữu ích của giao tác Tc trong CSDL D, ký hiệu T U (Tc ), được xác định: X T U (Tc ) = u(x, Tc ) (1.4) x∈Tc 8 luan an - Giá trị hữu ích của CSDL D, ký hiệu DU (D), được xác định: X DU (D) = T U (Tc ) (1. DU (D) = T U (T1 ) + T U (T2 ) + T U (T3 ) + T U (T4 ) + T U (T5 ) + T U (T6 ) + T U (T7 ) + T U (T8 ) + T U (T9 ) + T U (T1 0) = 237 Định nghĩa 1. (Tập mục hữu ích cao): Tập mục X là tập mục hữu ích cao trong CSDL D nếu giá trị hữu ích của X không nhỏ hơn ngưỡng hữu ích tối thiểu ε cho trước.
Gọi HUIs là tập các tập mục hữu ích cao, ta có: HU Is = {X|X ⊆ I, u (X) ≥ ε} (1. Với ε = 40, hai tập mục {DF G} và {ACE}. Tập mục {DF G} không là tập mục hữu ích cao vì u({DF G}) = 24 < ε, còn tập mục {ACE} là tập mục hữu ích cao vì u({ACE}) = 46 > ε. Khai phá tập mục hữu ích cao và phổ biến Khai phá tập mục hữu ích cao và phổ biến là một mở rộng của khai phá tập mục hữu ích cao.
Tức là khai thác từ CSDL giao tác tất cả các tập mục thỏa mãn đồng thời hai điều kiện: giá trị hữu ích của tập mục không nhỏ hơn ngưỡng hữu ích tối thiểu và độ hỗ trợ của tập mục không nhỏ hơn ngưỡng hỗ trợ tối thiểu cho trước. Các định nghĩa liên quan đến khai phá tập mục hữu ích cao và phổ biến được trình bày như sau: Định nghĩa 1.7) |D| Trong đó, supc(X) = |{Tc |X ⊆ Tc , Tc ∈ D}|. 9 luan an Định nghĩa 1. (Tập mục hữu ích cao và phổ biến): Tập mục X là tập mục hữu ích cao và phổ biến nếu giá trị hữu ích của X không nhỏ hơn ngưỡng hữu ích tối thiểu ε và độ hỗ trợ của X không nhỏ hơn ngưỡng hỗ trợ tối thiểu δ.
Gọi HU F Is là tập các tập mục hữu ích cao và phổ biến, khi đó HU F Is được xác định: HU F Is = {X|u(X) ≥ ε ∧ support(X) ≥ δ} (1. Xét hai tập mục {BC} và {AE}. Do đó, tập mục {BC} là tập mục hữu ích cao và phổ biến còn tập mục {AE} không phải là tập mục hữu ích cao và phổ biến. Khai phá tập mục hữu ích trung bình cao Khai phá tập mục hữu ích trung bình cao là một mở rộng của khai phá tập mục hữu ích cao.
Giá trị hữu ích trung bình của tập mục được xác định là trung bình chung giá trị hữu ích của tất cả các mục trong tập mục. Các định nghĩa liên quan đến tập mục hữu ích trung bình cao được trình bày như sau: Định nghĩa 1.9) |X| - Giá trị hữu ích trung bình của tập mục X trong CSDL D, ký hiệu au(X), được xác định: X au(X) = au(X, Tc ) (1.10) X⊆Tc ∧Tc ∈D Ví dụ 1. (Tập mục hữu ích trung bình cao): Tập mục X là tập mục hữu ích trung bình cao nếu giá trị hữu ích trung bình của X không nhỏ hơn ngưỡng hữu ích trung bình tối thiểu µ. Gọi HAU Is là tập các tập mục hữu ích trung bình cao thì: HAU Is = {X|au(X) ≥ µ} (1.
Khai phá luật kết hợp hữu ích cao Để xác định mối quan hệ suy diễn trong tập mục hữu ích cao, các tác giả trong [39] đã đề xuất mô hình khai phá luật kết hợp hữu ích cao. Các định nghĩa liên quan đến vấn đề này được trình bày lại như sau: Định nghĩa 1. - Giá trị hữu ích cục bộ của một mục x trong tập mục X tại giao tác Tc ký hiệu luv(x, X, Tc ), được định nghĩa: luv(x, X, Tc ) = u(x, Tc )|x ∈ X ⊆ Tc ∧ Tc ∈ D (1.12) - Giá trị hữu ích cục bộ của tập mục X trong tập mục Y tại giao tác Tc ký hiệu luv(X, Y, Tc ), được định nghĩa: X luv(X, Y, Tc ) = luv(x, X, Tc ) (1.13) x∈X∧X⊆Y ∧Y ⊆Tc - Giá trị hữu ích cục bộ của tập mục X trong tập mục Y trong CSDL D, ký hiệu là luv(X, Y ), được định nghĩa: X X luv(X, Y ) = luv(x, X, Tc ) (1.14) X⊆Y ∧Y ⊆Tc ∧Tc ∈D x∈X - Độ tin cậy hữu ích của luật R : X → Y (X, Y ⊆ I ∧ X ∩ Y = ∅), ký hiệu uconf (R) được định nghĩa: luv(X, XY ) uconf (R) = (1. Với tập mục hữu ích cao XY (X ∩ Y = ∅), luật kết hợp R : X → Y là luật kết hợp hữu ích cao nếu độ tin cậy hữu ích của luật R không nhỏ hơn ngưỡng tin cậy hữu ích tối thiểu µ cho trước.
Gọi HRs là tập chứa các luật kết hợp hữu ích cao, khi đó ta có: HRs = {R : X → Y |uconf (R) ≥ µ} (1. Cho ngưỡng hữu ích tối thiểu ε = 40, ngưỡng tin cậy hữu ích tối thiểu µ = 70%: - Xét tập mục {AC} và {ACF }, ta có: u({AC}) = u({AC}, T1 ) + u({AC}, T3 ) + u({AC}, T4 ) = 42 + 14 + 18 = 74 và u({ACF }) = u({ACF }, T1 ) + u({ACF }, T3 ) = 44 + 15 = 59. Như vậy, hai tập mục {AC} và {ACF } đều là tập mục hữu ích cao. - Với tập mục hữu ích cao {ACF }, xét luật AC → F , ta có: 11 luan an luv({AC}, {ACF }) = luv({AC}, {ACF }, T1 ) + luv({AC}, {ACF }, T3 ) = 42 + 14 = 56.
Như vậy, luật AC → F là luật kết hợp hữu ích cao. Tổng quan tình hình nghiên cứu về khai phá hữu ích cao Các thuật toán khai phá tập phổ biến không đề cập đến vai trò của các mục và xem chúng có vai trò như nhau trong CSDL. Tuy nhiên, nếu các mục được xem xét về tầm quan trọng của chúng sẽ có ý nghĩa thực tế hơn. Để giải quyết vấn đề đặt ra, các thuật toán mở rộng của khai phá tập phổ biến đã được đề xuất, các thuật toán này có thể được nhóm lại như sau: Khai phá tập mục phổ biến có trọng số (Weighted itemset mining): Là một dạng mở rộng của khai phá tập phổ biến.
Ở đây, mỗi mục được gắn thêm một đơn vị được gọi là trọng số nhằm mục đích chỉ ra tầm quan trọng của chúng. Bài toán khai phá tập mục phổ biến có trọng số được Cai và cộng sự đề xuất vào năm 1998 [4].