Luận văn: Luật Kết Hợp Mờ và Toán Tử Ngưỡng trong Khai Phá Dữ Liệu

Luận văn thạc sĩ: Nghiên cứu luật kết hợp mờ & toán tử ngưỡng trong khai phá dữ liệu. Chuyên ngành Công nghệ Thông tin, mã số 1 01 10.

• Tác giả: Lê Thị Thanh Hải
• Người hướng dẫn: PGS. Bùi Công Cường
• Trường học: Trường Đại học Công nghệ
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu
• Loại tài liệu: Luận văn thạc sỹ
• Năm xuất bản: 2007
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỤC LỤC
• DANH MỤC BẢNG BIỂU, HÌNH VẼ, CÔNG THỨC & KÍ HIỆU VIẾT TẮT
• 1. CHƯƠNG 1 - LUẬT KẾT HỢP
• 1.1. Ý NGHĨA THỰC TIỄN CỦA LUẬT KẾT HỢP
• 1.2. MÔ HÌNH HÌNH THỨC CỦA VẤN ĐỀ PHÁT HIỆN LUẬT
• 1.2.1. Thuộc tính và CSDL
• 1.2.2. Độ hỗ trợ của một tập thuộc tính
• 1.2.3. Tập phổ biến (Frequent Itemset):
• 1.2.4. Độ hỗ trợ của luật r = X  Y
• 1.2.5. Độ tin cậy của luật: r = X  Y
• 1.2.6. Luật kết hợp mạnh:
• 1.2.7. Bài toán luật kết hợp
• 1.2.8. Một số tính chất của tập phổ biến và luật kết hợp
• 1.3. THUẬT TOÁN TÌM LUẬT KẾT HỢP
• 1.3.1. Thuật toán Apriori nhị phân
• 1.3.1.1. Các bước thực hiện
• 1.3.1.2. Giải thích:
• 1.3.2. Thuật toán AprioriTid
• 1.3.2.1. Các bước thực hiện
• 1.3.2.2. Giải thích
• 1.3.3. Sinh ra các luật kết hợp mạnh từ tập phổ biến
• 1.3.3.1. Thuật toán nhanh hơn:
• 1.3.4. Thuật toán FP-Growth
• 2. CHƯƠNG 2 - LUẬT KẾT HỢP MỜ
• 2.1. Ý NGHĨA VỀ LUẬT KẾT HỢP MỜ
• 2.2. Định nghĩa tập mờ:
• 2.3. Các phép toán trên tập mờ:
• 2.4. Số mờ và một số dạng phổ biến
• 2.4.1. Định nghĩa tập mức:
• 2.4.2. Định nghĩa số mờ:
• 2.4.3. Các dạng phổ biến của số mờ:
• 2.5. Các phép toán trong logic mờ (toán tử mờ)
• 2.5.1. Phép phủ định (negation)
• 2.6. LUẬT KẾT HỢP MỜ
• 2.6.1. Cơ sở dữ liệu và thuộc tính:
• 2.6.2. Độ ủng hộ của bản ghi cho mệnh đề
• 2.6.3. Độ hỗ trợ của mệnh đề
• 2.6.4. Tập phổ biến
• 2.6.5. Độ hỗ trợ của một luật mờ:
• 2.6.6. Độ tin cậy của một luật mờ
• 2.6.7. Ưu điểm của việc áp dụng tập mờ để rời rạc hoá dữ liệu.
• 2.7. LUẬT KẾT HỢP MỜ VỚI CÁC TOÁN TỬ CÓ NGƯỠNG
• 2.7.1. Toán tử có ngưỡng
• 2.7.1.1. Định nghĩa: t-chuẩn có ngưỡng
• 2.7.1.2. Định nghĩa: t-đối chuẩn có ngưỡng
• 2.7.2. Các ký hiệu sử dụng trong thuật toán:
• 2.7.3. Các chương trình con sử dụng trong thuật toán:
• 2.7.4. Ví dụ minh họa thuật toán (Ví dụ 2.
• 2.7.5. Chuyển luật kết hợp mờ về luật có thuộc tính số
• 2.7.6. Luật kết hợp mờ với thuộc tính được đánh trọng số
• 2.7.7. Luật thật sự có ích
• 2.7.8. Phương pháp loại bỏ luật thừa
• 2.7.9. Phương pháp tìm luật đơn giản
• 3. CHƯƠNG 3 - CÀI ĐẶT THỬ NGHIỆM
• TÀI LIỆU THAM KHẢO
• DANH MỤC BẢNG BIỂU, HÌNH VẼ, CÔNG THỨC & KÍ HIỆU VIẾT TẮT
• DANH MỤC BẢNG BIỂU. DANH MỤC BẢNG BIỂU
• DANH MỤC HÌNH VẼ. DANH MỤC HÌNH VẼ
• DANH MỤC CÔNG THỨC. DANH MỤC CÔNG THỨC
• KÝ HIỆU VIẾT TẮT. KÝ HIỆU VIẾT TẮT
• MỞ ĐẦU

Tóm tắt

I. Luật Kết Hợp Mờ Tổng Quan Ý Nghĩa Trong Khai Phá Dữ Liệu

Luật kết hợp mờ là một lĩnh vực quan trọng trong khai phá dữ liệu, phát triển mạnh mẽ. Kỹ thuật khai phá luật kết hợp ngày càng được quan tâm, trở thành hướng nghiên cứu lớn. Chương này trình bày các khái niệm cơ sở và thuật toán kinh điển. Luật kết hợp có dạng X -> Y. Trong lĩnh vực bán hàng, ví dụ: "40% khách hàng mua cafe thì mua thêm bánh quy, 3% khách hàng mua cả cafe và bánh quy". Cafe là tiền đề, bánh quy là kết quả, 40% là độ tin cậy, 3% là độ hỗ trợ. Độ hỗ trợ và độ tin cậy là 2 thước đo quan trọng. Mô hình hình thức của vấn đề phát hiện luật bao gồm: Thuộc tính và CSDL, Độ hỗ trợ của một tập thuộc tính, Tập phổ biến (Frequent Itemset), Độ hỗ trợ của luật r = X -> Y, Độ tin cậy của luật: r = X -> Y, Luật kết hợp mạnh, Bài toán luật kết hợp, Một số tính chất của tập phổ biến và luật kết hợp. Khai phá luật kết hợp nhị phân có một số hạn chế khi ta không chỉ cần quan tâm đến sự có mặt hoặc không có mặt của một thuộc tính nào đó. Trong thực tế các thông tin không rõ ràng, không đầy đủ, không chắc chắn và mang tính định lượng là phổ biến. Việc áp dụng fuzzy logic vào data mining đem lại nhiều hiệu quả. Theo Zaden, tập mờ được coi như là sự mở rộng trực tiếp của tập hợp kinh điển.

1.1. Các Bước Cơ Bản Trong Khai Phá Luật Kết Hợp

Bài toán khai phá luật kết hợp thường chia làm 2 pha: Tìm tất cả các tập phổ biến (FX) trong cơ sở dữ liệu, nghĩa là tìm tất cả các tập thuộc tính X sao cho supp(X) >= minsupp. Sinh ra các luật kết hợp mạnh từ các tập phổ biến tìm thấy ở pha 1. Thuật toán Apriori nhị phân là một thuật toán nhằm phát hiện các tập phổ biến bằng nhiều lần duyệt dữ liệu. Thuật toán AprioriTid cũng sử dụng hàm apriori_gen để xác định các tập ứng cử khi bắt đầu duyệt.

1.2. Tính Chất Quan Trọng Của Tập Phổ Biến Luật Kết Hợp

Với tập phổ biến ta có 3 tính chất sau: Tính chất 1 (độ hỗ trợ của tập con): Nếu A ⊆ B với A, B là các tập thuộc tính thì supp (A) ≥ supp (B). Tính chất 2: Một tập chứa một tập không phổ biến thì cũng là tập không phổ biến. Tính chất 3: Các tập con của tập phổ biến cũng là tập phổ biến. Với luật kết hợp ta có 4 tính chất sau: Tính chất 4. Không hợp các luật kết hợp. Tính chất 5: Không tách luật. Tính chất 6: Các luật kết hợp không có tính bắc cầu. Tính chất 7: Nếu luật A → (L-A) không thỏa mãn độ tin cậy cực tiểu thì với các tập mục B ⊆ A ⊂ L, luật B → (L-B) cũng không thỏa mãn.

1.3. Giới Thiệu Thuật Toán Apriori Ứng Dụng Trong Data Mining

Thuật toán Apriori là thuật toán nhằm phát hiện các tập phổ biến bằng nhiều lần duyệt dữ liệu. Trong lần duyệt đầu tiên chúng ta tính độ hỗ trợ của các tập thuộc tính riêng lẻ và xác định nó có là tập phổ biến hay không bằng cách so sánh độ hỗ trợ của nó với độ hỗ trợ cực tiểu (minsupp). Ở những lần duyệt sau, chúng ta bắt đầu từ 1 tập phổ biến hạt giống của các tập phổ biến đã tìm được ở lần duyệt trước. Thuật toán FP-Growth thực hiện như sau: Duyệt CSDL lần thứ nhất để tính độ hỗ trợ của từng thuộc tính (đếm số lần xuất hiện của từng thuộc tính). Loại bỏ những thuộc tính không đáp ứng được độ hỗ trợ tối thiểu. Các thuộc tính còn lại được sắp theo thứ tự giảm dần của độ hỗ trợ (cũng tức là sắp theo thứ tự giảm dần số lần xuất hiện trong CSDL). Ta nhận được danh sách L các thuộc tính đã được sắp.

II. Thách Thức Vấn Đề Điểm Biên Gãy Trong Rời Rạc Hóa

Việc khai phá luật kết hợp nhị phân có một số hạn chế khi ta không chỉ cần quan tâm đến sự có mặt hoặc không có mặt của một thuộc tính nào đó. Trong thực tế các thông tin không rõ ràng, không đầy đủ, không chắc chắn và mang tính định lượng là phổ biến. Khi rời rạc hóa dữ liệu cho các thuộc tính để chuyển chúng về dạng nhị phân ta có thể gặp phải vấn đề “điểm biên gãy” (sharp boundary problem). Giải pháp khai phá dữ liệu mờ đã đem lại hiệu quả đáng kể trong việc giải quyết vấn đề trên. Trước khi tìm hiểu cách khai phá dữ liệu mờ, cần tìm hiểu các khái niệm liên quan đến tập mờ. Theo Zaden, tập mờ được coi như là sự mở rộng trực tiếp của tập hợp kinh điển. Cần nắm rõ Định nghĩa tập mờ, Các phép toán trên tập mờ: Phép hợp, Phép giao, Phần bù. Số mờ và một số dạng phổ biến. Các phép toán trong logic mờ (toán tử mờ).

2.1. Tại Sao Rời Rạc Hóa Dữ Liệu Gây Ra Điểm Biên Gãy

Đối với các thuộc tính số người ta có thể rời rạc hóa bằng cách chia khoảng giá trị rồi sau đó áp dụng như đối với thuộc tính hạng mục. Tuy nhiên ta gặp phải vấn đề “điểm biên gãy” (sharp boundary problem). Ví dụ thuộc tính Tuổi ta chia làm các khoảng [0..13], [14..100]. Giả sử với độ trợ tối thiểu minssup khoảng [0..13] không thỏa mãn, khoảng [14..100] cũng không thỏa mãn. Tuy nhiên nếu ta chia khoảng [10..14] thì lại thỏa mãn độ hỗ trợ tối thiểu. Như vậy phép phân khoảng có thể tạo ra điểm biên gãy giữa giá trị 13,14.

2.2. Khái Niệm Cơ Bản Tập Mờ Hàm Thuộc Ứng Dụng

Cho X - Không gian nền X (X ≠ ∅). A - tập mờ trên X, được xác định bởi hàm thuộc 𝜇A: X -> [0,1]. 0 <= 𝜇A(x) <= 1. 𝜇A(x) - gọi là độ thuộc của x vào tập mờ A. Chúng ta cũng sẽ ký hiệu A = {( 𝜇A(x)/x): x∈X)}. Ví dụ: X - tập học viên cao học. A1 - tập học viên cao học của khóa K10. A2 - tập học viên cao học chăm chỉ. Ta thấy A1 là tập rõ còn A2 là tập mờ trên tập X.

2.3. Các Phép Toán Logic Mờ Phủ Định Hội T Chuẩn Đối Chuẩn

Phép phủ định (negation): Tính v( P ) theo v(P) = x ( x∈[0,1]). Định nghĩa: Phép phủ định. Phép phủ định là hàm số n:[0,1] -> [0,1]. Phép hội (conjunction): Phép hội (vẫn quen gọi là phép AND) là một trong những phép toán logic cơ bản nhất. Nó cũng là cơ sở để định nghĩa phép giao của hai tập mờ. Định nghĩa t-chuẩn (t-norm): Hàm số T:[0,1] x [0,1] -> [0,1] gọi là t-chuẩn nếu thỏa mãn:

III. Luật Kết Hợp Mờ Giải Pháp Cho Thuộc Tính Định Lượng

Khai phá luật kết hợp mờ là phát hiện các luật kết hợp sử dụng khái niệm tập mờ đối với các thuộc tính định lượng. Bài toán tìm luật kết hợp mờ trên CSDL D là bài toán tìm cách rút ra các luật dạng Nếu X là A thì Y là B. A và B là tập các tập mờ tương ứng của các thuộc tính trong X và Y. Các mệnh đề này được xem là thoả mãn khi có đủ số bản ghi đóng góp cho sự ủng hộ của cặp <thuộc tính-tập mờ> với tổng tất cả sự ủng hộ là lớn hơn ngưỡng do người sử dụng đưa ra. Cần quan tâm tới những luật có đủ độ quan trọng (significance) và độ chắc chắn (certainty) cao. Các bước chính: Chuyển từ cơ sở dữ liệu quan hệ sang cơ sở dữ liệu mờ. Tìm tất cả các tập mờ có độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu. Sinh các luật kết hợp mờ tin cậy từ các tập phổ biến đã tìm thấy .

3.1. Độ Ủng Hộ Độ Hỗ Trợ Tập Phổ Biến Trong Luật Mờ

Độ ủng hộ của bản ghi cho mệnh đề. Cho cơ sở dữ liệu D trên tập tất cả các thuộc tính I, <X,A> là mệnh đề trên I. Với d là một bản ghi trên CSDL D (d ∈ D), khi đó, độ ủng hộ của bản ghi d cho mệnh đề <X,A> được tính bởi: vote(d , X , A) = 𝜇 X A 1 (d [I ]) ⊗ 𝜇 X A 2 (d [I ]) ⊗ ... ⊗ 𝜇 X A p (d [I X p ]) Độ hỗ trợ của mệnh đề. Để sinh luật kết hợp mờ, chúng ta phải tìm tất cả các tập phổ biến là những tập thuộc tính có độ hỗ trợ cao hơn ngưỡng do người sử dụng đưa ra. Tập phổ biến. Một tập thuộc tính mờ là phổ biến nếu độ hỗ trợ của nó lớn hơn hoặc bằng độ hỗ trợ tối thiểu fminsupp (fuzzy minimum support) do người dùng nhập vào.

3.2. Công Thức Tính Độ Hỗ Trợ Độ Tin Cậy Của Luật Kết Hợp Mờ

Luật r = Nếu X là A thì Y là B hay ký hiệu có độ hỗ trợ được tính bởi công thức: fsupp (<X,A>-> <Y,B>) = fsupp (<X∪Y,A∪B>). Độ tin cậy của một luật mờ: Khi chúng ta đã có một tập phổ biến , chúng ta muốn sinh các luật kết hợp mờ có cấu trúc “Nếu X là A thì Y là B” với X ⊂ Z, Y = Z - X, A ⊂ C, B = C – A.

3.3. Ưu Điểm Vượt Trội Của Luật Kết Hợp Mờ So Với Phương Pháp Cũ

Giải quyết được vấn đề “điểm biên gãy” nhờ tập mờ có thể phân khoảng mịn hơn nhờ vào độ trơn của hàm thuộc. Rời rạc hoá bằng phân đôi khoảng khi tạo ra số khoảng rất lớn và do đó số thuộc tính nhị phân cũng rất lớn. Còn khi sử dụng tập mờ thì số lượng tập mờ gắn với mỗi thuộc tính là không đáng kể. Tập mờ cho phép chúng ta biểu diễn luật kết hợp dưới dạng tự nhiên hơn, gần gũi hơn với người sử dụng.

IV. Toán Tử Có Ngưỡng Nâng Cao Hiệu Quả Khai Phá Luật Mờ

Ta có thể sử dụng các toán tử T-chuẩn để xác định độ ủng hộ. Đối với một số tập mờ, khi độ thuộc của một phần tử đạt hoặc không đạt đến một ngưỡng nào đó thì việc sử dụng các toán tử phù hợp khác nhau để kết hợp 2 tập mờ cũng làm cho việc khai phá dữ liệu đạt kết quả tốt hơn. Hay nói cách khác, ta có thể sử dụng các toán tử có ngưỡng cho bài toán khai phá dữ liệu bằng luật kết hợp mờ. Khi đưa khái niệm ngưỡng vào các toán tử t-chuẩn, t-đối chuẩn chúng ta được các lớp mới, lớp các toán tử có ngưỡng.

4.1. Định Nghĩa Ứng Dụng Toán Tử T Chuẩn T Đối Chuẩn Có Ngưỡng

Định nghĩa: t-chuẩn có ngưỡng. Nếu gọi 𝛼 là miền ngưỡng, 𝛼 = (𝛼1,𝛼2), 0  𝛼1,𝛼2  1. Cho t1(x,y), t2(x,y) là 2 t-chuẩn mà t2(x,y)  t1(x,y) với 0  x,y  1. Khi đó, t-chuẩn có ngưỡng T(x,y,𝛼) xác định trên [0,1]2 như sau: T(x, y,α) = {t1(x, y) α1  x and α 2  y ; t2(x, y) ∃i ∈ 1, p, 𝜇 (d[I ]) < α }. Định nghĩa: t-đối chuẩn có ngưỡng. Nếu gọi 𝛽 là miền ngưỡng, 𝛽 = (𝛽1, 𝛽2), 0  𝛽1, 𝛽2  1. Cho s1(x,y), s2(x,y) là 2 t-đối chuẩn mà s1(x,y)  s2(x,y) với 0  x,y  1. Khi đó, t-đối chuẩn có ngưỡng S(x,y,𝛼) xác định trên [0,1]2 như sau:

4.2. Bài Toán Khai Phá Luật Mờ Với Toán Tử Ngưỡng Input Output

Đầu vào: Cơ sở dữ liệu D với tập tất cả các thuộc tính I và các bản ghi T, độ hỗ trợ tối thiểu fminsupp, độ tin cậy tối thiểu fminconf, các tập mờ ứng với các thuộc tính số, ngưỡng ứng với các tập mờ đó và các toán tử t-chuẩn tương ứng. Đầu ra: Tất cả các luật kết hợp mờ tin cậy. Bài toán này gồm 3 pha như sau: i) Chuyển từ cơ sở dữ liệu quan hệ sang cơ sở dữ liệu mờ nghĩa là xây dựng các hàm thuộc của các tập mờ tương ứng với từng thuộc tính. ii) Tìm tập tất cả các tập phổ biến mờ ∈ FR (tập có độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu fminsupp ) iii) Sinh các luật kết hợp mờ tin cậy từ các tập phổ biến mờ đã tìm thấy .

4.3. Các Chương Trình Con Hỗ Trợ Thuật Toán Khai Phá Luật Mờ

Chương trình con Mo_hoa(D,I,T). Chương trình này thực hiện nhiệm vụ chuyển cơ sở dữ liệu D ban đầu sang cơ sở dữ liệu mờ DF. Chương trình con Tinh(DF,IF,TF, fminsupp). Chương trình này sinh ra F1 là tập phổ biến chứa 1 thuộc tính. Chương trình con Join(Fk-1). Chương trình này thực hiện việc sinh ra tập các tập thuộc tính mờ có độ lớn k từ tập các tập phổ biến có độ lớn k-1 (Fk-1). Chương trình con Checking(Ck, DF, fminsupp). Chương trình này duyệt lại CSDL DF để cập nhật độ hỗ trợ cho các tập thuộc tính trong Ck để từ đó chọn những tập phổ biến đưa vào Fk. Chương trình con Tim_luat(Fk, fminconf). Chương trình này sinh luật kết hợp mờ tin cậy từ các tập phổ biến Fk.

V. Cài Đặt Thử Nghiệm Ứng Dụng Trong Phân Tích Thị Trường

Chương trình được viết bằng Visual Basic nhằm thử nghiệm thuật toán. Dữ liệu thử nghiệm về tình trạng sử dụng internet, hơn 10.000 bản ghi, với các thuộc tính: Dung lượng tải về, Dung lượng gửi đi, Loại dịch vụ sử dụng, Thời gian kết nối, Thời điểm. Sau khi mờ hóa dữ liệu theo các thuộc tính mờ, chương trình thực hiện tính toán độ hỗ trợ của các tập, đưa ra luật thông qua bảng. Mục tiêu: phân tích thị trường sử dụng internet, góp phần vào các chiến dịch giảm giá, khuyến mại của nhà cung cấp dịch vụ. Các tham số của tập mờ mang tính chủ quan.

5.1. Các Thuộc Tính Mờ Quá Trình Mờ Hóa Dữ Liệu Thực Tế

Chương trình này được viết với mục đích thử nghiệm thuật toán bằng ngôn ngữ Visual Basic. Dữ liệu thử nghiệm về tình trạng sử dụng internet, thử nghiệm trên hơn 10.000 bản ghi, với các thuộc tính như sau:Thuộc tính mờ gốc thuộc tính gốc thuộc tính mờ In_ngan Bytesin Dung lượng tải về ít In_TB Dung lượng tải về trung bình In_dai Dung lượng tải về nhiều Out_ngan Bytesout Dung lượng gửi đi ít Out_TB Dung lượng gửi đi trung bình Out_dai Dung lượng gửi đi nhiều

5.2. Phân Tích Kết Quả Ý Nghĩa Trong Nghiên Cứu Thị Trường

Việc tìm các luật kết hợp mờ ở đây nhằm phân tích thị trường sử dụng internet góp phần vào các chiến dịch giảm giá, khuyến mại của các nhà cung cấp dịch vụ. Vì lĩnh vực nghiên cứu thị trường sử dụng internet không phải là chuyên môn nên những tham số của các tập mờ trong thuật toán này mang tính chủ quan của tác giả. Dưới đây là một số giao diện của chương trình

VI. Kết Luận Hướng Nghiên Cứu Mở Rộng Trong Tương Lai

Khai phá dữ liệu là lĩnh vực được quan tâm, bao gồm nhiều lĩnh vực, kỹ thuật. Khai phá luật kết hợp mờ là mục tiêu quan trọng. Luận văn đã nghiên cứu, trình bày: khái niệm, định nghĩa, thuật toán điển hình để giải quyết bài toán khai phá luật kết hợp, đánh giá ưu nhược điểm của chúng. Đề xuất đưa vào các toán tử phù hợp để xác định độ ủng hộ, khái niệm toán tử có ngưỡng, thử nghiệm cho bài toán, trực quan hóa các bước của thuật toán. Hướng mở rộng: nghiên cứu, đánh giá các thuật toán cải tiến, thuộc tính đa mức, phương pháp tìm hàm thuộc của tập mờ, ngưỡng.

6.1. Tóm Tắt Các Vấn Đề Đã Nghiên Cứu Giải Quyết Trong Luận Văn

Chương 1: Trong chương này ngoài việc phát biểu các khái niệm, định nghĩa một cách hình thức còn trình bày các thuật toán điển hình để giải quyết bài toán khai phá luật kết hợp. Chương 2: Thực tế là các dữ liệu thường ở dạng thuộc tính số và hạng mục. Chính vì vậy bài toán tìm luật kết hợp với thuộc tính số và hạng mục đã được đề cập một cách sơ lược để đánh giá ưu và nhược điểm của chúng. Chương 3: Đây là phần cài đặt thử nghiệm cho bài toán đưa ra ở chương 2. Dữ liệu của chương trình là về thời gian và các loại dịch vụ sử dụng internet ADSL.

6.2. Đề Xuất Hướng Nghiên Cứu Tiềm Năng Trong Tương Lai

Khai phá dữ liệu lĩnh vực được nhiều nhà nghiên cứu quan tâm vì nó ứng dụng rộng rãi trong đời sống xã hội ngày nay và vì vậy có rất nhiều hướng nghiên cứu mở rộng khác nhau. Trong luận văn này tôi chỉ chọn một vấn đề nhỏ để nghiên cứu, khi có điều kiện tôi sẽ mở rộng hướng nghiên cứu ra một số hướng sau: Nghiên cứu, đánh giá các thuật toán cải tiến tối ưu hơn để từ đó gắn với các toán tử mờ có ngưỡng.

Trích đoạn nội dung tài liệu

Chương 1: Luật kết hợp. Trong chương này tôi đã trình bày những nét khái quát nhất về khai phá dữ liệu bằng luật kết hợp thông qua việc đưa ra các khái niệm, định nghĩa và bài toán tìm luật kết hợp. Những thuật toán điển hình của luật kết hợp như thuật toán Apriori và một vài thuật toán khác cũng được đề cập để giải quyết bài toán. Chương 2: Luật kết hợp mờ với toán tử có ngưỡng.

Ở phần đầu của chương tôi trình bày các khái niệm liên quan đến tập mờ để từ đó làm cơ sở đưa vào bài toán khai phá luật kết hợp. Với các bài toán có thuộc tính số và hạng mục thì việc rời rạc hóa dữ 7 TIEU LUAN MOI download : [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu liệu có thể xảy ra một vài nhược điểm như vấn đề “điểm biên gãy”. Vì thế luật kết hợp mờ là một giải pháp rất hiệu quả. Phần cuối chương là các khái niệm về các toán tử có ngưỡng và đưa ra bài toán xây dựng luật kết hợp mờ với các toán tử có ngưỡng.

Chương 3: Cài đặt thử nghiệm: Là phần cài đặt thử nghiệm chương trình dùng dữ liệu về việc sử dụng internet. Kết luận: Phần này nêu lại những việc đã thực hiện và kết quả đạt được của luận văn, vấn đề còn chưa được giải quyết thấu đáo và một số hướng nghiên cứu trong tương lai. 8 TIEU LUAN MOI download : [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu 1. CHƢƠNG 1 - LUẬT KẾT HỢP Luật kết hợp là một lĩnh vực quan trọng trong khai phá dữ liệu và vì thế kỹ thuật khai phá luật kết hợp ngày càng được quan tâm và phát triển mạnh trong những năm trở lại đây, trở thành một hướng nghiên cứu lớn.

Trong chương này, chúng ta cùng tìm hiểu các khái niệm cơ sở và các thuật toán kinh điển của luật kết hợp. Ý NGHĨA THỰC TIỄN CỦA LUẬT KẾT HỢP Luật kết hợp là những luật có dạng: X  Y Trong lĩnh vực bán hàng ta có thể có luật: “40% khách hàng mua cafe thì mua thêm bánh quy, 3% khách hàng mua cả cafe và bánh quy” Ở ví dụ này diễn tả mối quan hệ giữa cafe và bánh quy hay ta có luật X  Y tương đương với cafe  bánh quy. Cafe là tiền đề của luật và bánh quy là kết quả của luật. Các hệ số 40% và 3% là các độ đo của luật - 40% là độ tin cậy của luật: trong những khách hàng mua cafe có 40% mua thêm bánh quy - 3% là độ hỗ trợ của luật: trong tất cả khách hàng mua ở cửa hàng có 3% mua cả 2 mặt hàng là cafe và bánh quy.

Các số này ta sẽ định nghĩa cụ thể ở các phần dưới 1. MÔ HÌNH HÌNH THỨC CỦA VẤN ĐỀ PHÁT HIỆN LUẬT 1. Thuộc tính và CSDL - I = {I1, I2, …,In} là tập tất cả các mục (Item) hay được gọi là tập tất cả các thuộc tính (attributes) mỗi một thuộc tính Ii với i = 1, n được gọi là 1 mục dữ liệu - X = {Ix1, Ix2,…,Ixp}  I là 1 tập thuộc tính (Itemset) - D = (T1, T2, …, Tm) là cơ sở dữ liệu trên I, là tập tất cả các tác vụ (transaction) hay được gọi là tập các bản ghi. Mỗi bản ghi Tk với k = 1, m đều có định danh (TID- Transaction Identification) và nó là một tập các thuộc tính Tk  I với k = 1, m Ta có Tk(Iv) xác định giá trị của thuộc tính Iv.

Ví dụ: nếu xét thuộc tính phân, Tk(Iv) = 1 nghĩa là khách hàng Tk chọn mua mặt hàng 9 TIEU LUAN MOI download : [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu Iv, Tk(Iv) = 0 nếu khách hàng Tk không chọn mua hàng Iv). - Một luật kết hợp có dạng X  Y Trong đó: + X  I là tiền đề của luật + Y  I là hệ quả của luật, +XY= biểu thị mối quan hệ giữa tập thuộc tính X và tập thuộc tính Y. Vì vậy có thể nói luật kết hợp biểu thị mối quan hệ giữa các tập con của I Độ hỗ trợ và độ tin cậy là 2 thước đo của 1 luật kết hợp 1. Độ hỗ trợ của một tập thuộc tính Cho một tập thuộc tính X  I, cơ sở dữ liệu D Độ hỗ trợ (support) của tập thuộc tính X trong cơ sở dữ liệu D (Ký hiệu supp(X)) là tỷ lệ % giữa số bản ghi trong cơ sở dữ liệu D chứa tập thuộc tính X với tổng số các bản ghi trong cơ sở dữ liệu D.

| {Tk  D \ X  Tk | Supp( X )  <1. Tập phổ biến (Frequent Itemset): Cho một tập thuộc tính X  I trong cơ sở dữ liệu D và ngưỡng hỗ trợ tối thiểu minsupp  (0,1] (minsupp - Minimum Support) được xác định bởi người sử dụng. Một tập thuộc tính X được gọi là tập phổ biến theo ngưỡng minsupp khi và chỉ khi độ hỗ trợ của nó lớn hơn hoặc bằng ngưỡng minsupp X  I là tập phổ biến  supp(X)  minsupp Ký hiệu: FX(D, minsupp) là tập hợp các tập phổ biến theo ngưỡng minsupp FX( D, minsupp) = {X  I \supp(X)  minsupp} 1. Độ hỗ trợ của luật r = X  Y Độ hỗ trợ của luật được tính bằng công thức: Supp (r) = supp(XY) <1.

Độ tin cậy của luật: r = X  Y Độ tin cậy của luật r trong cơ sở dữ liệu D (Ký hiệu là conf(r)) là tỷ lệ % giữa số bản ghi trong D chứa tập thuộc tính X thì cũng chứa tập thuộc tính Y. Về mặt xác suất độ tin cậy của luật r là xác suất có điều kiện xảy ra Y với điều kiện đã xảy ra X 10 TIEU LUAN MOI download : [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu Tk  D \ X  Tk , Y  Tk  conf (r )  Tk  D \ X  Tk  Tk  D \ X  Y  Tk   <1.3> Tk  D \ X  Tk  Tk  D \ X  Y  Tk  D  D Tk  D \ X  Tk  supp( X  Y )  supp( X ) 1. Luật kết hợp mạnh: Luật r = X  Y được gọi là luật kết hợp mạnh theo ngưỡng độ hỗ trợ tối thiểu minsupp  (0,1] và độ tin cậy tối thiểu minconf  (0,1] (Minimum Confidence) khi và chỉ khi độ hỗ trợ của luật lớn hơn hoặc bằng độ hỗ trợ tối thiểu và độ tin cậy của luật lớn hơn hoặc bằng độ tin cậy tối thiểu. Bài toán luật kết hợp Người ta chỉ quan tâm đến luật kết hợp mạnh theo ngưỡng minsupp và minconf cho trước.

Chính vì vậy bài toán khai phá luật kết hợp thường chia làm 2 pha: 1- Tìm tất cả các tập phổ biến (FX) trong cơ sở dữ liệu, nghĩa là tìm tất cả các tập thuộc tính X sao cho supp(X)  minsupp 2- Sinh ra các luật kết hợp mạnh từ các tập phổ biến tìm thấy ở pha 1- Ví dụ 1.1: Bài toán khai phá luật kết hợp Thực hiện bài toán khai phá luật kết hợp ở trên đối với đầu vào: Cho CSDL D = {T1, T2, T3, T4, T5, T6} trên I = {A, B, C, D, E, F} TID Các thuộc tính T1 A, C, E, F T2 B, C, E T3 A, B, D, E 11 TIEU LUAN MOI download : [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu T4 A, B, C, E T5 D, F T6 A, C, D Bảng 1.1 CSDL giao dịch (Ví dụ 1.1) Ta lần lượt tìm độ hỗ trợ của các tập thuộc tính. Bắt đầu từ tập có 1 thuộc tính rồi đến 2,3…. Độ hỗ trợ của tập có 1 thuộc tính được tính trong bảng sau theo cách Thuộc tính A có mặt trong 4 bản ghi (T1, T3, T4, T6) của D nên supp (A) = 4/6 = 67,7% Thuộc tính Số bản ghi Độ hỗ trợ supp(X) A 4 67,7% B 3 50,0% C 4 67,7% D 3 50% E 4 67,7% F 2 33,3% Bảng 1.2 Độ hỗ trợ của các thuộc tính (Ví dụ 1.1) Nếu ta chọn độ hỗ trợ tối thiểu minsupp = 50% thì với cách tính tương tự trong bảng 1 ta có danh sách các tập phổ biến Số thuộc tính Danh sách các tập phổ biến 1 {A}, {B}, {C}, {D}, {E} 2 {AC}, {AE}, {BE}, {CE} Bảng 1.3 Danh sách các tập mục phổ biến (Ví dụ 1.1) Từ danh sách tập phổ biến đó các luật kết hợp được đưa ra trong bảng sau: Luật kết hợp Độ tin cậy A→C 75% A→E 75% B→E 100 % C→E 75% Bảng 1.4 Độ tin cậy của các luật sinh từ tập phổ biến (Ví dụ 1.1) Nếu ta chọn độ tin cậy tối thiểu minconf = 80% thì chỉ có luật B → E là luật kết hợp 12 TIEU LUAN MOI download : [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu mạnh. Một số tính chất của tập phổ biến và luật kết hợp Với tập phổ biến ta có 3 tính chất sau: Tính chất 1 (độ hỗ trợ của tập con): Nếu A  B với A, B là các tập thuộc tính thì supp (A) ≥ supp (B) Điều này là rõ ràng vì tất cả các bản ghi trong D chứa B thì cũng chứa A.

Tính chất 2: Một tập chứa một tập không phổ biến thì cũng là tập không phổ biến Nếu tập A không đủ độ hỗ trợ cực tiểu tức là supp(A) < minsupp thì tập B  A cũng không phổ biến vì supp (B) ≤ supp (A) < minsupp (áp dụng tính chất 1) Tính chất 3: Các tập con của tập phổ biến cũng là tập phổ biến Nếu tập B là tập phổ biến trong D, tức là supp (B) ≥ minsupp, mọi tập con A của B cũng là phổ biến trong D, bởi vì supp (A) ≥ supp(B) ≥ minsupp theo tính chất 1. Với luật kết hợp ta có 4 tính chất sau: Tính chất 4. Không hợp các luật kết hợp Nếu có X  Z và Y  Z trong D thì không nhất thiết X  Y  Z là đúng.