Tổng quan khai phá dữ liệu và bài toán luật kết hợp
Khái niệm
Khai phá dữ liệu, được giới thiệu vào cuối thập kỷ 80, bao gồm nhiều kỹ thuật nhằm phát hiện thông tin giá trị ẩn trong các tập dữ liệu lớn Quá trình này liên quan đến việc phân tích dữ liệu và áp dụng các phương pháp để tìm ra các mẫu hình quy luật trong tập dữ liệu.
Vào năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã giới thiệu khái niệm Phát hiện tri thức trong cơ sở dữ liệu, chỉ toàn bộ quy trình khám phá tri thức có ích từ các tập dữ liệu lớn Khai phá dữ liệu là một bước quan trọng trong quy trình này, sử dụng các thuật toán đặc biệt để chiết xuất mẫu và mô hình từ dữ liệu Ở mức độ trừu tượng, khai phá dữ liệu được định nghĩa là quá trình tìm kiếm và phát hiện tri thức mới, tiềm ẩn và hữu dụng trong cơ sở dữ liệu lớn.
Khám phá tri thức (KDD) được coi là mục tiêu chính của khai phá dữ liệu, dẫn đến việc hai khái niệm này thường được xem là tương đương Tuy nhiên, nếu phân biệt rõ ràng, khai phá dữ liệu thực sự là một bước quan trọng trong quá trình KDD.
Quá trình phát hiện tri thức trong cơ sở dữ liệu
Khám phá tri thức trong cơ sở dữ liệu (KDD) là một lĩnh vực đa dạng, kết hợp các ngành như thống kê, học máy, cơ sở dữ liệu, thuật toán, trực quan hóa dữ liệu, tính toán song song và hiệu năng cao.
Quá trình phát hiện tri thức nhằm mục đích khai thác tri thức từ dữ liệu trong các cơ sở dữ liệu lớn KDD là một quy trình đa giai đoạn và có tính lặp lại, với khả năng lặp lại có thể xảy ra ở bất kỳ bước nào trong quá trình này.
Quá trình đó có thể được mô tả theo hình sau:
Bước đầu tiên trong quy trình giải quyết bài toán là xác định và định nghĩa rõ ràng bài toán, bao gồm việc tìm hiểu lĩnh vực ứng dụng để hình thành bài toán và xác định các nhiệm vụ cần hoàn thành Giai đoạn này rất quan trọng, vì nó quyết định việc rút ra tri thức hữu ích và lựa chọn các phương pháp khai thác dữ liệu phù hợp với mục đích ứng dụng cũng như bản chất của dữ liệu.
Bước thứ hai trong quy trình phát hiện tri thức là thu thập và tiền xử lý dữ liệu, bao gồm việc làm sạch dữ liệu để loại bỏ nhiễu, xử lý các giá trị thiếu để làm giàu dữ liệu, biến đổi và rút gọn dữ liệu khi cần thiết Đây là bước tốn nhiều thời gian nhất do dữ liệu thường được lấy từ nhiều nguồn khác nhau, dẫn đến sự không đồng nhất và có thể gây nhầm lẫn Sau khi hoàn thành, dữ liệu sẽ trở nên nhất quán, đầy đủ, được rút gọn và rời rạc hoá.
Bước thứ ba trong quy trình khai thác dữ liệu là rút ra tri thức từ các mẫu và mô hình ẩn trong dữ liệu Giai đoạn này rất quan trọng và bao gồm việc xác định chức năng, nhiệm vụ và mục đích của khai phá dữ liệu, cũng như lựa chọn phương pháp phù hợp Các bài toán khai phá dữ liệu thường được chia thành hai loại: bài toán mô tả, nhằm đưa ra các đặc điểm chung của dữ liệu, và bài toán dự báo, bao gồm việc phát hiện các suy diễn từ dữ liệu hiện có Việc xác định loại bài toán sẽ giúp chọn phương pháp khai phá dữ liệu hiệu quả nhất.
Bước thứ tư trong quá trình này là áp dụng các tri thức đã phát hiện, đặc biệt là làm rõ các mô tả và dự đoán Các bước trước đó có thể được lặp lại nhiều lần, và kết quả thu được sẽ được tính trung bình từ tất cả các lần thực hiện.
Quá trình khai phá tri thức (KDD) bao gồm nhiều bước, và kết quả của nó có thể được ứng dụng trong nhiều lĩnh vực khác nhau Những kết quả này có thể là các dự đoán hoặc mô tả, cho phép chúng được tích hợp vào các hệ thống hỗ trợ ra quyết định nhằm tự động hóa quy trình này Tóm lại, khai phá dữ liệu là giai đoạn quan trọng nhất trong quá trình KDD, giúp trích xuất tri thức từ kho dữ liệu.
Các kĩ thuật khai phá dữ liệu
1.3.1 Các kĩ thuật tiếp cận trong khai phá dữ liệu
Căn cứ vào lớp các bài toán cần giải quyết, khai phá dữ liệu có các kỹ thuật áp dụng sau:
Phân lớp và dự đoán là quá trình xếp một đối tượng vào các lớp đã biết trước, chẳng hạn như phân loại bệnh nhân trong hồ sơ bệnh án Phương pháp này thường áp dụng các kỹ thuật học máy như cây quyết định và mạng nơ ron nhân tạo để đạt được độ chính xác cao trong việc phân loại.
Luật kết hợp là phương pháp dùng để phát hiện các mối liên hệ giữa các thành phần dữ liệu trong cơ sở dữ liệu (CSDL) Kết quả của thuật toán khai phá dữ liệu là một tập hợp các luật kết hợp được tìm ra Ví dụ điển hình về luật kết hợp có thể thấy trong việc phân tích CSDL bán hàng, cho thấy rằng khách hàng mua máy tính thường có xu hướng mua thêm phần mềm quản lý tài chính trong cùng một lần giao dịch.
“Mua máy tính Mua phần mềm quản lý tài chính”
Độ hỗ trợ và độ tin cậy là hai chỉ số quan trọng trong việc đánh giá sự liên quan của luật Độ hỗ trợ 4% cho thấy chỉ 4% các tác vụ phân tích cho thấy máy tính và phần mềm quản lý tài chính được mua cùng nhau Trong khi đó, độ tin cậy 70% cho biết 70% khách hàng mua máy tính cũng chọn mua phần mềm quản lý tài chính, phản ánh mức độ chắc chắn trong mối liên hệ giữa hai sản phẩm này.
Phân tích chuỗi theo thời gian là một phương pháp tương tự như khai phá luật kết hợp, nhưng với sự bổ sung về tính thứ tự và thời gian Phương pháp này được áp dụng rộng rãi trong lĩnh vực tài chính và thị trường chứng khoán nhờ vào khả năng dự báo cao của nó.
Phân cụm: xếp các đối tượng theo từng cụm dữ liệu tự nhiên
Mô tả khái niệm: thiên về mô tả, tổng hợp và tóm tắt khái niệm Ví dụ: tóm tắt văn bản.
1.3.2 Dạng dữ liệu có thể khai phá
Khai phá dữ liệu được ứng dụng rộng rãi và có khả năng làm việc với nhiều kiểu dữ liệu khác nhau Một số dạng dữ liệu điển hình bao gồm cơ sở dữ liệu quan hệ, cơ sở dữ liệu đa chiều (như kho dữ liệu), cơ sở dữ liệu dạng giao dịch, cơ sở dữ liệu quan hệ-hướng đối tượng, dữ liệu không gian và thời gian, dữ liệu chuỗi thời gian, cơ sở dữ liệu đa phương tiện, cũng như dữ liệu văn bản và web.
1.3.3 Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu là một lĩnh vực quan trọng và được áp dụng rộng rãi trong nhiều ngành Một số ứng dụng điển hình của khai phá dữ liệu bao gồm phân tích hành vi khách hàng, dự đoán xu hướng thị trường, phát hiện gian lận và cải thiện quy trình sản xuất.
Phân tích dữ liệu và hỗ trợ ra quyết định;
Tài chính và thị trường chứng khoán;
Bài toán khai phá luật kết hợp và ứng dụng
1.4.1 Luật kết hợp trong cơ sở dữ liệu
Gọi I = I 1 , I 2, , I m là tập m thuộc tính riêng biệt, mỗi thuộc tính gọi là một mục Gọi D là một cơ sở dữ liệu, trong đó mỗi bản ghi T là một giao dịch và chứa các tập mục, T I Định nghĩa 1: Một luật kết hợp là một quan hệ có dạng X Y, trong đó X, Y I là các tập mục(itemsets), và X Y Ở đây, X được gọi là tiền đề, Y là mệnh đề kết quả
Hai thông số quan trọng của luật kết hợp là độ hỗ trợ và độ tin cậy Độ hỗ trợ (support) của luật kết hợp X Y được định nghĩa là tỷ lệ phần trăm các bản ghi X Y so với tổng số giao dịch trong cơ sở dữ liệu Trong khi đó, độ tin cậy (confidence) được tính là tỷ lệ số giao dịch chứa X Y so với số giao dịch chứa X, với đơn vị tính là phần trăm (%).
Lựa chọn luật Ứng dụng
Khai thác luật kết hợp từ cơ sở dữ liệu là quá trình tìm kiếm tất cả các luật có độ hỗ trợ và độ tin cậy vượt ngưỡng do người dùng xác định, ký hiệu là minsup và mincof Tập mục X ∪ Y được coi là tập mục lớn nếu luật X ⇒ Y có độ hỗ trợ lớn hơn minsup Một đặc điểm quan trọng trong khai thác luật kết hợp là "tập mục con của một tập mục lớn cũng là tập mục lớn" Các thuật toán trích xuất luật kết hợp, như Apriori, dựa trên ý tưởng loại bỏ các tập mục không lớn từ các tập mục đơn ban đầu, sau đó kết hợp các tập mục còn lại và tiếp tục kiểm tra cho đến khi tìm ra tập mục lớn nhất có thể.
Luật kết hợp mờ cho phép chia một mục thành các miền mờ như "trẻ" hay "trung niên", giúp phân loại các mục con một cách linh hoạt Giá trị của mỗi hàng trong mục này nằm trong khoảng [0,1], thay vì chỉ là 0 hoặc 1 Độ hỗ trợ của một miền mờ si đối với mục xi được định nghĩa để phản ánh mức độ phù hợp của miền mờ đó.
FS (1) còn độ hỗ trợ của các miền mờ s 1 , s2, , sk của các mục x1, x2, , xk tương ứng sẽ là
FS (2) ở đó xi là mục thứ i, si là miền mờ thuộc mục thứ i, n là số hàng trong CSDL, s x i i )
( d x j i là độ thuộc của giá trị tại cột thứ i, hàng j vào tập mờ si.
Luật kết hợp là một khái niệm quan trọng được áp dụng rộng rãi trong nhiều lĩnh vực như khoa học, kinh doanh, tiếp thị, thương mại, phân tích thị trường chứng khoán, tài chính và đầu tư Việc ứng dụng luật kết hợp cần làm rõ các đặc điểm như nguồn gốc, điều kiện áp dụng, phạm vi ứng dụng và mục đích ứng dụng, được thể hiện qua một mô hình cụ thể.
Hình 2 Mô hình ứng dụng luật
Yêu cầu sử dụng tập luật có phạm vi ứng dụng rộng rãi trong nhiều lĩnh vực như khoa học, kinh doanh, tiếp thị, thương mại và phân tích thị trường chứng khoán.
Theo tập luật R, ở giai đoạn này, các tập luật được đề cập là những tập luật được sinh ra từ cơ sở dữ liệu chứa các tác nhân yêu cầu sử dụng.
Lựa chọn luật, ở bước này chúng ta tiến hành lọc các luật hữu ích nhất phục vụ cho phạm vi sử dụng
Ứng dụng, đây là kết quả mong đợi nhất từ khi bắt đầu khai thác cho đến khi thi hành luật
Mô hình ứng dụng luật đã làm sáng tỏ tính ứng dụng của việc khai thác luật kết hợp trong cơ sở dữ liệu
Khai thác luật kết hợp trong cơ sở dữ liệu giao dịch là một phần quan trọng của khai phá dữ liệu, với ứng dụng rộng rãi trong bối cảnh phát triển của xã hội hiện nay.
Khai thác luật kết hợp trong cơ sở dữ liệu giao dịch mang lại tính ứng dụng cao, cho phép sử dụng các tập luật đã được phát hiện để phục vụ những mục đích cụ thể và đạt được hiệu quả tối ưu.
Một số thuật toán khai phá luật kết hợp
Thuật toán Apriori
Thuật toán Apriori, được đề xuất lần đầu vào năm 1993 bởi Rakesh Agrawal, Tomasz Imielinski và Arun Swami, là một giải pháp tìm kiếm các giao dịch có độ hỗ trợ và độ tin cậy vượt quá ngưỡng đã định.
Thuật toán Apriori tính toán tất cả các tập ứng cử viên của tập k trong một lần duyệt cơ sở dữ liệu, dựa vào cấu trúc cây băm Khi tìm kiếm xuống cấu trúc cây, mỗi khi chạm lá, thuật toán xác định một tập ứng cử viên có tiền tố chung trong giao dịch Các tập ứng cử này sau đó được kiểm tra trong các giao dịch đã được ánh xạ trước đó, và nếu tìm thấy, biến đếm sẽ được tăng lên 1.
Giả sử các mục trong mỗi giao dịch được lưu giữ theo trật tự từ điển Kích thước của một tập mục được định nghĩa là số lượng các mục trong đó, và tập mục có kích thước k được gọi là tập k-mục Các mục trong mỗi tập mục cũng được sắp xếp theo trật tự từ điển.
Lk: Tập các tập k-mục phổ biến (với độ hỗ trợ cực tiểu minsup nào đó)
Ck : Tập các tập k-mục ứng cử (các tập mục phổ biến tiềm năng)
Output: Tập các tập mục phổ biến
4 { C k = apriori_gen(L k-1 , minsup);// các ứng cử mới theo chương trình con ở dưới đây
6 { C t =Subset (C k ,t);// ứng cử viên được chứa trong t
// sinh ứng cử viên mới (**)
5 if( has_inrequent_subset(c, L k-1 )) delete c;
2.1.3 Sinh luật kết hợp từ các tập mục phổ biến
Sau khi xác định các tập mục phổ biến trong cơ sở dữ liệu, ta có thể sinh ra các luật kết hợp mạnh Luật kết hợp mạnh được định nghĩa là những luật thỏa mãn cả độ hỗ trợ và độ tin cậy tối thiểu Để thực hiện điều này, chúng ta cần sử dụng tính độ tin cậy của luật, cụ thể là độ tin cậy của luật X .
Y là: conf (X Y) = P(Y/X) = sup(XY)/sup(X) ở đó sup(XY) là độ hỗ trợ của XY và sup(X) là độ hỗ trợ của X
Có thể coi tỷ số trên là tỷ số giữa: số các tác vụ chứa XY và số các tác vụ chứa
X Dựa trên biểu thức tính toán đó, các luật kết hợp có thể được sinh như sau:
Với mỗi tập mục phổ biến l, sinh ra tất cả các tập con không rỗng của l
Với mỗi tập con không rỗng a của l, ta có luật a (l-a) nếu
) sup( a l minconf ở đó minconf là ngưỡng độ tin cậy cực tiểu
Do các luật được hình thành từ những tập mục phổ biến, nên mức độ hỗ trợ của luật đã được đảm bảo, tức là mức độ hỗ trợ của luật chính là sup(l).
Chúng ta tối ưu hóa quy trình xử lý bằng cách tạo ra các tập con từ tập lớn thông qua phương pháp đệ quy ưu tiên độ sâu Chẳng hạn, với tập mục ABCD, chúng ta sẽ bắt đầu xem xét tập con ABC, tiếp theo là AB, và tiếp tục theo thứ tự như vậy.
Nếu tập con a của tập mục lớn l không tạo ra được luật, thì không cần xem xét các tập con của nó Ví dụ, nếu luật ABC → D không đạt độ tin cậy, thì luật AB → CD cũng không cần được xem xét Điều này có thể được chứng minh một cách đơn giản.
Nếu luật a (l-a) không thoả mãn độ tin cậy, tức là: conf(al-a)) nhỏ hơn minconf, thế thì với bất kỳ tập con b nào của a ta có:
Vì b a nên supp(b)supp(a), do vậy:
Tức là độ tin cậy của luật b(l-b) cũng nhỏ hơn minconf
Thuật toán đơn giản này có thể mô tả như sau:
For all large itemsets l k , k2 do call genrules(l k ,l k )
Ggenrules(l k :large k-itemsets, a m : large m-itemsets){
A={(m-1)-itemsets a m-1 |a m-1 a m }; for (a m-1 A){ conf=support(l k )/support(a m-1 );
{ output the rule a m-1 (l k -a m-1 ), with confidence=conf and support=support(l k ) if (m-l > l) then call genrules(l k ,a m-1 );
//để sinh ra các luật với tập con của a m-1 là phần tiền đề }
Ứng dụng logic mờ trong thuật toán khai luật kết hợp Apriori
2.2.1 Ứng dụng logic mờ trong thuật toán khai phá luật kết hợp Apriori
Thuật toán Apriori đã cung cấp một phương pháp cơ bản để khai phá luật kết hợp trong siêu thị, nhưng chỉ áp dụng cho dữ liệu nhị phân, tức là các mặt hàng trong cơ sở dữ liệu chỉ có giá trị có hoặc không {0,1} Mặc dù phương pháp này hiệu quả trong việc xử lý tập dữ liệu lớn, nhưng nó không phù hợp với các thuộc tính thực tế trong cơ sở dữ liệu, như thuộc tính số học và phạm trù, ví dụ như thu nhập và tuổi trong dữ liệu cá nhân Việc chỉ dựa vào dữ liệu nhị phân sẽ không giải quyết được các vấn đề phức tạp hơn trong khai phá dữ liệu thực tế.
Những hạn chế của phương pháp Aragwa đã được nhận diện, và nhiều nghiên cứu sau đó đã đề xuất các giải pháp khắc phục Tuy nhiên, hầu hết các phương pháp này vẫn dựa trên ý tưởng cốt lõi của thuật toán Apriori, đó là: "Tập mục lớn chỉ khi tất cả các tập mục con của nó cũng là tập mục lớn."
Một trong những phương pháp tiếp cận là chuyển đổi các dữ liệu không phải nhị phân thành dạng nhị phân bằng cách thiết lập một ngưỡng t để phân loại dữ liệu thành hai giá trị {0,1} Ví dụ, với dữ liệu đã cho, chúng ta có thể áp dụng quy tắc này để xác định kết quả.
Bảng 1 Ví dụ dữ liệu mẫu case age income risk credit result
Theo như phương pháp nói trên, thì với mỗi thuộc tính sẽ được đặt một ngưỡng α để chuyển đổi dữ liệu về dạng nhị phân theo hàm:
1 𝑛ế𝑢 𝐴 𝑖𝑗 ≥ 𝛼 𝑖 ,trong đó, 1 ≤ i ≤ n, 1 ≤ j ≤ m Giả sử cho 𝛼 1 = 30, 𝛼 2 = 35000, 𝛼 3 = 0, khi đó dữ liệu tương ứng được chuyển về thành dạng:
Bảng 2 Dữ liệu được chuyển về dạng nhị phân case age income risk credit result
Mô hình thuật toán Apriori sẽ được áp dụng để giải quyết bài toán, tuy nhiên việc chọn ngưỡng là rất quan trọng và phụ thuộc vào người xây dựng bài toán Độ chính xác của tập luật chịu ảnh hưởng lớn từ các ngưỡng này Hơn nữa, việc chuyển đổi dữ liệu thành dạng {0,1} như trong ví dụ trên có thể làm mất đi các giá trị cơ bản của dữ liệu, dẫn đến kết quả không phù hợp.
Cách tiếp cận thứ hai trong việc giải quyết bài toán là ứng dụng lý thuyết logic mờ, bao gồm các lý thuyết như lý thuyết tập mờ, lý thuyết thống kê, lý thuyết tập thô và lý thuyết tập cặp Lý thuyết tập mờ, được Zadeh trình bày lần đầu vào năm 1965, được ưa chuộng nhờ tính đơn giản và sự tương đồng với logic con người Lý thuyết này tập trung vào việc lượng hóa và lập luận bằng ngôn ngữ tự nhiên, sử dụng các từ có tính mờ để tăng tính linh hoạt trong việc hỗ trợ quyết định cho người dùng Hiện nay, lý thuyết tập mờ ngày càng được áp dụng rộng rãi trong các hệ thống thông minh.
Trong đú: Hàm thuộc xỏc định độ thuộc của x trong A cho thấy rằng khi giá trị của x càng lớn, thì x càng thuộc A nhiều hơn Tập mờ có thể được mở rộng thành tập cứng, trong đó các phần tử chỉ có thể thuộc hoặc không thuộc tập.
Hiện nay, các phương pháp khai phá luật kết hợp dựa trên logic mờ đang thu hút sự chú ý trong lĩnh vực này Logic mờ gần gũi với cách lập luận tự nhiên của con người, giúp cải thiện khả năng tính toán và độ chính xác của tập luật.
Thuật toán khai phá luật kết hợp dựa trên logic mờ được trình bày sau đây Ngưỡng hỗ trợ và ngưỡng tin cậy được cho trước
Các ký hiệu dùng trong thuật toán: n: Tổng số giao giao dịch trong cơ sở dư liệu m: Tổng số các thuộc tính
R jk : miền mờ thứ k của A j , 1 ≤ k ≤ |A j | w jk : Trong số của Rjk, 0 ≤ w jk ≤ 1
D(i) dữ liệu giao dịch thứ i, 1 ≤ i ≤ n v j (i): Giá trị phàm trù hoặc định lượng của Aj trong D(i); f jk (i) giá trị hàm thuộc của v j (i) trong R jk , 1 ≤ f jk (i) ≤ m;
Sup(R jk ): Độ hỗ trợ của R jk
Sup: giá trị hỗ trợ của mỗi tập mục lớn;
Conf: độ tin cậy của mỗi tập mục lớn
Minsup: Giá trị hỗ trợ tối thiểu cho trước
Minconf: giá trị tin cậy cho trước
C r : tập các tập mục thỏa mãn với r thuộc tính (tập mục), 1 ≤ r ≤ m;
L r : tập các tập mục lớn thỏa mãn với r thuộc tính (tập mục) 1 ≤ r ≤ m;
Thuật toán khai phá dữ liệu mờ có trọng số cho các giá trị định lượng được thực hiện theo các bước sau:
Input: n,m, w jk , hàm thuộc của các tập mục, minsup và minconf Output: luật kết hợp mờ
Bước 1: Chuyển các giá trị định lượng và phàm trù v j (i) của mỗi giao dịch D(i), i từ
1 tới n, với mỗi thuộc tính Aj, j từ 1 tới m, về giá trị mờ fjk(i)(1 ≤ k ≤ |A|) bằng hàm thuộc Rjk
Bước 2 : Tính giá trị hỗ trợ
𝑛 , 1 ≤ 𝑗 ≤ 𝑛, 1 ≤ 𝑘 ≤ 𝐴 𝑗 giá trị hỗ trợ của miền mờ Rjk, để chuyển C1 thành tập tham chiếu 1- itemsets
Bước 3 : Nếu Sup(Rjk) ≥ minsup thì đưa Rjk vào L1(L1 là tập mục lớn mức 1)
Bước 4 : Nếu L1 không rỗng, tiếp tục bước sau, nếu rỗng thoát chương trình
Bước 5 trong quá trình xây dựng tập mục lớn mức r là lựa chọn hai tập mục lớn mức r-1 chỉ khác nhau ở một mục duy nhất Bằng cách kết hợp hai tập mục này, ta tạo ra tập mục ứng viên Cr Nếu tập mục này xuất hiện trong cơ sở dữ liệu và đạt yêu cầu về giá trị hỗ trợ cũng như độ tin cậy, nó sẽ được thêm vào danh sách các tập mục lớn mức r.
Bước 6: Tiếp tục thực hiện các bước con cho các tập mục lớn hơn, cụ thể là tập mục lớn S với các mục (s1, s2, …, st, …, sr+1) trong Cr+1, với điều kiện 1≤ t ≤ r+1.
Để tính toán các giá trị mờ cho mỗi giao dịch D(t) của S, ta sử dụng công thức 𝑓𝑠(𝑡) = 𝑟 + 1 𝑡=1 𝑤𝑠𝑡𝑓𝑠𝑡(𝑖), trong đó fst(i) là giá trị hàm thuộc của D(t) trong miền mờ st, và wst là trọng số tương ứng của st Khi áp dụng toán tử cực tiểu, ta có fs(t) = min wstfst(i).
Tính giá trị hỗ trợ sup(S) của S trong giao dịch
If Sup(S) ≥ minsup, thì đưa S vào Lr+1 𝑛
Bước 7 : Nếu Lr+1 là rỗng, thì thực hiện bước tiếp theo, ngược lại, đặt r=r+1, thực hiện lại bước 5 và 6
Bước 8 : Thu thập các tập mục lớn
Bước 9 : Đưa ra các luật kết hợp từ các tập mục lớn vừa thu thập theo cách sau:
Với mỗi luật kết hợp khả thi sau đây: s 1 ∩…∩s x ∩s y ∩…∩s q → sk (k=1 tới q, x=k-1, y= k+1)
Tính độ tin cậy của luật
Conf(s1∩…∩sx∩sy∩…∩sq → sk) = 𝑛 𝑖=1 𝑚𝑖𝑛 𝑘=1 𝑞 𝑓 𝑠𝑡 (𝑖) min (𝑚𝑖𝑛 𝑘=1 𝑥 𝑊𝑠𝑘 )
2.2.3 Nhận xét về thuật toán Apriori mờ
Việc ứng dụng lý thuyết logic mờ vào thuật toán đã cải thiện khả năng gán nhãn cho các trường dữ liệu định lượng, từ đó hỗ trợ khai phá luật kết hợp hiệu quả hơn Tuy nhiên, xây dựng hàm mờ để gán nhãn có thể gặp nhiều khó khăn và phụ thuộc vào từng bài toán cụ thể, dẫn đến việc giảm khả năng ứng dụng của các kỹ thuật khai phá luật kết hợp mờ.
Thuật toán khai phá luật kết hợp dựa trên lý thuyết đại số gia tử
Giới thiệu về lý thuyết đại số gia tử
Ý tưởng áp dụng ĐSGT trong khai thác dữ liệu dựa trên cấu trúc rõ ràng của các giá trị biến ngôn ngữ, chẳng hạn như "tuổi" và "trình độ chuyên môn" Trong ĐSGT tuyến tính, các giá trị của biến ngôn ngữ được sắp xếp theo thứ tự, ví dụ như giá trị "tuổi" được phân loại từ "rất trẻ" đến "khá già".
Các giá trị ngôn ngữ như "già" và "rất già" được phân bố có quy luật trên trục số giữa hai giá trị tối thiểu và tối đa Theo các giả thiết hợp lý, mỗi giá trị này gắn với một khoảng lân cận trên trục số, tạo thành một phân hoạch cho đoạn giá trị min, max Chúng ta có thể sử dụng giá trị đại diện cho khoảng này trong các ứng dụng khai thác dữ liệu, thay cho các giá trị hàm trong lý thuyết tập mờ của Zadeh Thông tin chi tiết về ĐSGT có thể tham khảo từ các tài liệu [1], [2], [8], [9].
Giả thiết đại số gia tử AX* = (X*, G, H, σ, , ) được xác định là tuyến tính và đầy đủ, với X* là tập cơ sở, G = (0, c−, W, c+, 1) là tập các phần tử sinh, và H là tập các gia tử Quan hệ thứ tự toàn phần trên X* được biểu diễn bằng , trong khi và là hai phép toán mở rộng Đối với mọi x thuộc X*, x và σx tương ứng là cận dưới đúng và cận trên đúng trong X* của tập H(x), tập hợp tất cả các phần tử sinh ra từ x thông qua các tác động của các gia tử trong H.
Gia tử được phân loại thành dương và âm dựa trên các điều kiện cụ thể Gia tử được gọi là dương nếu hc + > c + (hay hc < c ) và là âm nếu ngược lại Tập hợp các gia tử dương được ký hiệu là H +, trong khi tập hợp các gia tử âm được ký hiệu là H - Tổng hợp tất cả các gia tử tạo thành H = H + ∪ H -
Gia tử h được xem là dương (âm) đối với gia tử k khi tồn tại ít nhất một x thuộc miền xác định của X, sao cho nếu x nhỏ hơn kx thì kx lớn hơn hkx, hoặc nếu x lớn hơn kx thì kx nhỏ hơn hkx.
Tính chất 1.2.1.Tính chất dương (âm) của một gia tử này đối với một gia tử khác không phụ thuộc vào phần tử x mà chúng tác động
Nếu \( hx < kx \), thì với mọi \( p, q \in H \), ta có \( phx < qkx \) hay \( H(hx) < H(kx) \) Một ánh xạ \( f \) được gọi là ánh xạ định lượng ngữ nghĩa của \( X \) nếu nó thỏa mãn các điều kiện đã nêu.
Q2) f bảo toàn thứ tự trên X *, tức là x < y f(x) < f(y), và f( 0 ) = 0, f( 1 ) = 1;
Q3) Tính chất liên tục: x X *, f(x) = infimum f(H(x)) và f(x) = supremum f(H(x))
H(x) bao gồm các khái niệm mờ phản ánh ý nghĩa của khái niệm x, và kích thước của tập H(x) thể hiện tính mờ của x Qua ánh xạ ngữ nghĩa f, tập H(x) có thể được định lượng bằng độ dài của tập f(H(x)), ký hiệu là fm(x) Độ đo tính mờ được xác định qua định nghĩa 2 và một hàm fm : X * [0,1] được gọi là độ đo tính mờ của biến ngôn ngữ X nếu nó thỏa mãn các tính chất nhất định.
F1) fm là một độ đo đầy đủ trên X *, nghĩa là fm(c ) + fm(c + ) = 1 và, u X *,
F2) Nếu x là một khái niệm chính xác, tức là H(x) = x, thì fm(x) = 0 Đặc biệt ta có: fm(0) = fm(W) = fm(1) = 0;
Tỷ số fm = hx không phụ thuộc vào bất kỳ phần tử cụ thể nào trong X*, mà chỉ phụ thuộc vào h Do đó, chúng ta có thể ký hiệu nó bằng μ(h), được gọi là độ đo tính mờ của gia tử h.
Giả sử rằng H = h -1 , , h -q , với h -1
