Đồ án Nghiên cứu sâu hơn về t-Chuẩn có ngưỡng và bước đầu ứng dụng vào khai phá dữ liệu

húng ta sẽ khảo sát các so sánh giữa một số cặp họ t-chuẩn với cùng tham số. Mệnh đề 2.2.61. Cho t1 là t-chuẩn Yager và t2 là t-chuẩn Schweizer với cùng tham số a > 0, thế thì: t1 ≥ t2 : a > 1 t1 ≤ t2 : a < 1 Chứng minh: Giả sử t1 là t-chuẩn Yager với hàm sinh cộng tính g1(x) = (1-x)a, t2 là t-chuẩn Schweizer với hàm sinh cộng tính g2(x) = 1-xa, ta có: f(x) = = là hàm không giảm khi a < 1, vậy ta có t1 ≤ t2 theo hệ quả 2.2.48 □. h(x) = = là hàm không giảm khi a > 1, vậy ta có t2 ≤ t1 theo hệ quả 2.2.48 □. Mệnh đề 2.2.62. Cho t1 là t-chuẩn Weber, t2 là t-chuẩn Jane Doe #4, với cùng tham số a, thế thì: t1 ≤ t2 : a > 1 t1 ≥ t2 : a < 1 Chứng minh: Giả sử t1 là t-chuẩn Weber với hàm sinh cộng tính g1(x) = loga((a-1)(1-x)+1), t2 là t-chuẩn Jane Doe #4 với hàm sinh cộng tính g2(x) = 1-loga((a-1)x+1), ta có: f(x) = = là hàm không giảm khi a > 1, vậy ta có t1 ≤ t2 theo hệ quả 2.2.48. □. h(x) = = là hàm không giảm khi a < 1, vậy ta có t2 ≤ t1 theo hệ quả 2.2.48 □. Từ [28], ta có họ t-chuẩn Jane Doe #3 có hàm sinh 1-(1-x)a, họ Yager có hàm L-sinh 1-(1-x)a, họ Frank có hàm sinh , họ Jane Doe #6 có hàm L-sinh . Theo mệnh đề 2.2.47, ta có các kết quả sau. Mệnh đề 2.2.63. Cho t1 là t-chuẩn Jane Doe #3, t2 là t-chuẩn Yager có cùng tham số a, khi đó t1 ≥ t2. Mệnh đề 2.2.64. Cho t1 là t-chuẩn Frank, t2 là t-chuẩn Jane Doe #6 có cùng tham số a, khi đó t1 ≥ t2. Mệnh đề 2.2.65[39]. Xét hai t-chuẩn sau: t-chuẩn min tm(x,y) = min(x,y) t-chuẩn z tz(x,y) = Thế thì, với mọi t-chuẩn, ta luôn có tm(x,y) ≥ t(x,y) ≥ tz(x,y). Kết luận Trong chương này chúng tôi đã tổng kết lại các nghiên cứu về toán tử mờ có ngưỡng. Các khảo sát về cặp hàm sinh sẽ được sử dụng trong việc tạo ra các toán tử mờ có ngưỡng tham số. Các xem xét giải tích về các họ toán tử mờ tham số ở cuối chương là tổng kết các tính chất về thứ tự của các toán tử này và có thể sử dụng để tạo ra các t-chuẩn có ngưỡng tham số. LUẬT KẾT HỢP MỜ Chương này tóm tắt lại một số khái niệm cơ bản của bài toán luật kết hợp mờ, khảo sát sơ lược một số vấn đề về không gian tìm kiếm, việc sử dụng các toán tử mờ và toán tử mờ có ngưỡng trong bài toán tìm luật kết hợp mờ. Chúng tôi cũng đưa ra thuật toán F-Apriori để giải bài toán tìm luật kết hợp mờ. Giới thiệu Sự phát triển của công nghệ thông tin, công nghệ về thu nhận, lưu trữ và phân phối dữ liệu đã dẫn tới sự bùng nổ về thông tin và dữ liệu. Thách thức lớn nhất đối với các tổ chức cũng như các cá nhân ngày nay không chỉ là ở việc có ngày càng nhiều dữ liệu càng tốt mà còn ở việc trích rút từ kho dữ liệu khổng lồ thu nhận được ra các tri thức hữu ích. Vấn đề này đã tập hợp nhiều nhà nghiên cứu thuộc nhiều lĩnh vực khác nhau như thống kê, máy học, cơ sở dữ liệu, … vào một lĩnh vực nghiên cứu mới, đó là khai phá dữ liệu (Data Mining). Khai phá dữ liệu thường được xét đến như là một khâu trong một quá trình lớn hơn đó là Phát hiện tri thức trong cơ sở dữ liệu (Knowledge discovery in databases-KDD) [17]. Bài toán này bao gồm: Tìm hiểu về lĩnh vực ứng dụng, các tri thức đã có trước đó, và mục tiêu của người sử dụng. Lựa chọn loại tập dữ liệu tiến hành quá trình phát hiện tri thức, thực hiện công tác chuẩn hoá và chuyển đổi dữ liệu nếu cần. Lựa chọn hình thức khai phá dữ liệu, giải thuật, và quyết định mô hình cũng như các tham số có thể có. Thực hiện quá trình khái phá dữ liệu, trích ra các mẫu và mô hình. Hiển thị, diễn giải và hợp nhất các tri thức được phát hiện. Quá trình này được tiến hành lặp đi lặp lại do một bước có thể dẫn đến những sửa đổi của bước đã được tiến hành trước đó. Quá trình lặp cũng do người dùng có thể giới hạn lại khối lượng công việc của hệ thống trong phạm vi mà anh ta thực sự quan tâm. Bước khai phá dữ liệu là công việc trích rút các thông tin, một cách tự động từ dữ liệu. Các thông tin này có thể có giá trị đối với người sở hữu kho dữ liệu. Định nghĩa vắn tắt về thao tác này được đưa ra trong [24]: Khai phá dữ liệu là phân tích tập dữ liệu (thường là lớn, thậm chí rất lớn) thu nhận được nhằm tìm kiếm các mối quan hệ chắc chắn và tổng hợp dữ liệu theo một hình thức mới để trở nên hiểu được và hữu dụng đối với chủ của dữ liệu. Để phân tích dữ liệu, một vài dạng công việc khác nhau đã được phân biệt, tương ứng với mục tiêu của quá trình phân tích, và quan trọng hơn là tương ứng với sản phẩm dự kiến. Những công việc này có thể được phân loại như sau [24]. Phân tích dữ liệu thăm dò. Mục đích là thăm dò dữ liệu mà không hề có một ý tưởng rõ ràng về mục tiêu tìm kiếm. Các kỹ thuật thông thường gồm có hiển thị đồ hoạ, chiếu và tóm tắt. Tìm kiếm theo nội dung. Người dùng có một mẫu riêng trong ý nghĩ và muốn tìm kiếm những mẫu tương tự trong tập dữ liệu. Công việc này thường được sử dụng nhiều nhất để thu nhận thông tin từ một tập lớn dữ liệu văn bản và hình ảnh. Thách thức chính ở đây là định nghĩa sự tương tự và tìm kiếm các mẫu tương tự dựa theo định nghĩa này. Một ví dụ nổi tiếng là máy tìm kiếm Google (http: //www.google.com) của Brin và Page [6], cho phép tìm kiếm trang web chứa đựng thông tin tương tự như tập các từ khoá do người dùng nhập vào. Mô tả mô hình. Phương pháp mô tả mô hình tìm cách mô tả tất cả dữ liệu thu nhận được. Các phương pháp mô tả thông thường bao gồm một vài mô hình thống kê, phân cụm và mô hình phụ thuộc. Dự đoán mô hình. Kỹ thuật dự đoán như phân loại và hồi quy tìm cách trả lời câu hỏi dựa trên việc kiểm tra các tri thức đã có và các câu trả lời nhằm mục đích tổng quát hoá chúng cho các trường hợp tương lai. Một ví dụ ấn tượng của thao tác phân lớn là hệ thống SKICAT của Fayyad et al. [16], có thể tiến hành công tác phân lớp các ngôi sao và thiên hà tương đương với một chuyên gia. Hệ thống này của họ được sử dụng tại NASA nhằm phân lớp tự động hàng triệu ngôi sao và thiên hà từ những bức ảnh chụp bầu trời. Phát hiện mẫu. Mục đích là tìm các mẫu xuất hiện thường xuyên trong cơ sở dữ liệu. Rất nhiều thuật toán đã được nghiên cứu cho các loại mẫu khác nhau như các tập [2], cấu trúc cây [42], cấu trúc đồ thị [37,30], hay cấu trúc quan hệ bất kỳ [15,21] và luật kết hợp trên những cấu trúc này. Dạng mẫu được nghiên cứu nhiều nhất là tập các mục dữ liệu xuất hiện cùng nhau trong các cơ sở dữ liệu, ví dụ lưu trữ của các hoá đơn bán lẻ. Một ứng dụng tiêu biểu của luật kết hợp là trong ứng dụng bán hàng [5]. Trong những năm gần đây, đã có một vài cuốn sách và nhiều nghiên cứu được xuất bản về lĩnh vực này, chúng tôi có thể kể ra ở đây [24,26,29]. Luật kết hợp được giới thiệu lần đầu tiên trong [2]. Xuất phát từ bài toán bán hàng siêu thị, theo đó, chúng ta có một cơ sở dữ liệu “lớn” các giao dịch của khách hàng. Siêu thị của chúng ta có một lượng lớn các chủng loại mặt hàng, vấn đề đặt ra đối với nhà quản lý siêu thị là cần quyết định nên bán những mặt hàng nào, những mặt hàng nào nên đặt cạnh nhau, tóm lại là cách thức bày các mặt hàng trên các giá hàng nhằm thu lợi nhuận lớn nhất. Một phương pháp tiếp cận chủ yếu là sử dụng cơ sở dữ liệu về các giao dịch đã có trong quá khứ. Thông thường, người ta sẽ tiến hành xem xét các dữ liệu tích luỹ về một khoảng thời gian bán hàng như một năm, một tháng, một tuần hay một ngày, được lưu trữ trên máy tính. Hiện nay, với công nghệ sử dụng mã vạch, ta có thể theo dõi được trong một giao dịch, có cụ thể những mặt hàng nào. Thậm chí, chúng ta có thể theo dõi không chỉ các mặt hàng trong từng giao dịch mà còn cả các mặt hàng trong một khoảng thời gian như đối với khác hàng là một câu lạc bộ sách hay âm nhạc. Bài toán tìm luật kết hợp đầu tiên được đưa ra nhằm giải quyết việc tìm những mối liên hệ “có ý nghĩa” giữa các mặt hàng trong các giao dịch được biểu diễn dưới dạng các chuỗi nhị phân biểu thị việc có hay không có của từng mặt hàng trong giao dịch. Các luật này có thể cho biết rằng, mọi người khi mua bơ và sữa thường sẽ mua cả bánh mì, rõ ràng những hiểu biết dạng này rất có ý nghĩa đối với nhà quản lý của siêu thị. Ví dụ cho luật này có thể là như sau: “90% số người mua bơ và sữa sẽ mua cả bánh mì” và “30% số người vào siêu thị sẽ mua bơ, sữa và bánh mì.” Như thế, người quản lý có thể xem xét việc xếp bơ, sữa và bánh mì ở cạnh nhau nhằm tạo sự tiện dụng cho khác hàng. Hay, cũng có thể xem xét việc tăng cường bán bơ, sữa để có thể tăng lượng bánh mì bán được. Một cách hình thức, có thể xem đây là bài toán tìm mối liên hệ giữa các giá trị “1” trong cơ sở dữ liệu quan hệ mà các thuộc tính đều có dạng Boolean. Bảng trong cơ sở dữ liệu này có một thuộc tính tương ứng với mỗi mặt hàng và mỗi một bản ghi tương ứng với một giao dịch. Giá trị của một thuộc tính đối với một bản ghi cho trước là “1” nếu mặt hàng tương ứng có trong giao dịch tương ứng và “0” nếu ngược lại. Trong [40], bài toán này được gọi là bài toán luật kết hợp Boolean. Một mở rộng của bài toán này chính là bài toán tìm các luật kết hợp lượng hoá được nêu ra trong [40]. Trong [40] chỉ ra rằng, hầu hết các cơ sở dữ liệu khoa học hay kinh doanh, các thuộc tính thường có khả năng diễn đạt cao hơn là chỉ gồm có dạng boolean, các thuộc tính thường có dạng biểu diễn số liên tục như tuổi, số vốn, hay được chia khoảng như mức thu nhập (thấp, trung bình, cao…). Các thuộc tính boolean có thể được xem như trường hợp riêng của thuộc tính chia khoảng. Việc giới hạn các luật kết hợp với các thuộc tính boolean rõ ràng là đã giới hạn khả năng phân tích một cơ sở dữ liệu nhằm mang lại những thông tin hữu ích. Một mở rộng tự nhiên là xem xét các luật kết hợp cho các cơ sở dữ liệu mà các thuộc tính là các số định lượng. Bài toán này được giới thiệu đầu tiên trong [40] và được gọi là bài toán luật kết hợp lượng hoá (Quantitative Association Rules Problem). Các luật này có thể được phát biểu dạng như sau: “45% người trong độ tuổi [40-50], đã kết hôn có hai ô tô.” Nhằm tận dụng các thuật toán đã có đối với bài toán luật kết hợp boolean, [40] đưa ra cách giải quyết phân hoạch miền giá trị của các thuộc tính thành các khoảng và sau đó kết hợp các khoảng rời nhau để cho lời giải của bài toán. Thao tác này thực chất là chuyển bài toán luật kết hợp số về bài toán luật kết hợp boolean. Tuy nhiên, như trong [35] đã chỉ ra, rõ ràng việc sử dụng các biên rõ ràng giữa các phân hoạch của miền thuộc tính sẽ làm mất một số thông tin có thể thu được từ cơ sở dữ liệu đối với các giá trị nằm gần các biên này. Trong [35], đề nghị xem xét bài toán tìm các luật kết hợp dạng “Nếu X là A thì Y là B”, trong đó A và B là các tập mờ. Ví dụ, ta có các luật dạng “Một người trung niên thì thường có mức sống trung lưu.”. Trên thực tế, các thuộc tính số có thể quy về các thuộc tính mờ, ví dụ, độ tuổi [40-50] tương ứng với độ tuổi trung niên. Ngược lại, nếu coi các thuộc tính là tập mờ, với giá trị tương ứng trong một bản ghi biểu diễn độ thuộc của đối tượng vào tập mờ đó, khi đó các thuộc tính mờ có thể được coi như trường hợp riêng của thuộc tính lượng hoá. Thuộc tính boolean cũng có thể được coi là một trường hợp riêng của thuộc tính mờ. Việc sử dụng các tập mờ có ưu điểm thể hiện một cách mềm dẻo biến đổi giữa đối tượng thuộc hay không thuộc một tập nào đó so với phương pháp phân hoạch. Hơn nữa, việc sử dụng tập mờ tỏ ra đặc biệt có ưu thế đối với các bài toán có dữ liệu đầu vào là các biến ngôn ngữ. Bài toán tìm các luật kết hợp đối với các cơ sở dữ liệu mờ, nghĩa là cơ sở dữ liệu có các thuộc tính có miền giá trị là đoạn [0,1], trong [35] được gọi là bài toán luật kết hợp mờ. Trong thực tế, việc sử dụng các toán tử mờ có ngưỡng có thể có những ý nghĩa nhất định trong việc phân tích các dữ liệu. Lấy ví dụ, đối với các luật kết hợp mờ dạng “Những người giàu, nhiều tuổi thường thích đi du lịch”, việc sử dụng ngưỡng khi phân tích mức độ giàu cũng như mức độ nhiều tuổi là rất có ý nghĩa đối với những nhà quản lý hoạch định phương án tiếp thị kinh doanh của một công ty du lịch. Mô tả bài toán Tìm kiếm luật kết hợp mờ là tìm kiếm các luật kết hợp sử dụng tập mờ để mô tả dữ liệu đầu. Trong phần này, chúng tôi sẽ đưa ra các khái niệm cơ bản cho bài toán tìm luật kết hợp mờ. Thuộc tính và cơ sở dữ liệu Cho I là tập các thuộc tính I = {I1,…,In}, trong đó dom(Iv) là miền giá trị của thuộc tính Iv. Lấy ví dụ, trong cơ sở dữ liệu quản lý về các tính năng kỹ thuật của xe gắn máy, thông số về lượng xăng tiêu thụ trung bình trên 100km là một thuộc tính, với dom = [0,100]. Ta có một cơ sở dữ liệu D trên I là tập các bản ghi d. Với mọi bản ghi d D, ta có d[Iv] xác định giá trị iv dom(Iv) của thuộc tính Iv của d. Từ Xét I = {I1, I2, …, In} là tập các thuộc tính, giả sử mỗi một thuộc tính Iv có thể được mô tả bằng một tập các từ Lv = { ,,…,}. Lấy ví dụ, thông số về lượng xăng tiêu thụ trung bình trên 100km có thể được mô tả bằng tập từ {“thấp”, “trung bình”, “cao”}. Chú ý rằng, ở đây, các từ mô tả các thuộc tính khác nhau là khác nhau, mặc dù chúng có thể có cùng nhãn, ví dụ cùng là “thấp”, “trung bình” hay “cao”. Xét là một từ mô tả thuộc tính Iv của cơ sở dữ liệu. Khi đó, được biểu diễn bằng một hàm thuộc : dom(Iv) → [0,1] biểu diễn mức độ đúng đắn của việc sử dụng từ để mô tả giá trị iv dom(Iv). Lấy ví dụ hàm thuộc ứng với từ “thấp” trong mô tả thuộc tính lượng xăng tiêu thụ trung bình trên 100km của xe biểu diễn mức độ đúng đắn của việc sử dụng từ “thấp” khi mô tả một lượng xăng x nào đó, nghĩa là mức độ đúng đắn của mệnh đề “lượng xăng tiêu thụ x là thấp”. Ký hiệu Mv là tập tất cả các hàm thuộc biểu diễn các từ mô tả thuộc tính Iv. LI là tập tất cả các tập từ mô tả các thuộc tính của I, LI được gọi là mô tả của I. MI là tập tất cả các tập các hàm thuộc biểu diễn các từ trong mô tả LI của I, MI được gọi là biểu diễn của I ứng với LI. Mệnh đề Cho trước một cơ sở dữ liệu D trên tập thuộc tính I và các tập từ cũng như các hàm thuộc gắn với các thuộc tính này. Từ cơ sở dữ liệu này, bài toán tìm luật kết hợp mờ tìm cách rút ra các luật dạng: “Nếu X là A thì Y là B”. Trong phần này, chúng tôi sẽ xem xét biểu diễn hình thức của các mệnh đề dạng “X là A” hay “Y là B”. Định nghĩa 3.2.1. Cho I là tập thuộc tính, X = {, , …, } I là tập các thuộc tính, cho A là tập các từ mô tả các thuộc tính trong X, nghĩa là A = {, , …,}. A được gọi là mô tả của X, khi đó một mệnh đề trên tập thuộc tính I và tập từ LI (hay gọi tắt mệnh đề) “X là A”, có ký hiệu hình thức . Chú ý rằng ở đây, có tương ứng một một giữa A và X, theo nghĩa từ trong A là mô tả của thuộc tính trong X. Như trong [35] đã chỉ ra, chúng ta chỉ quan tâm tới những luật kết hợp có độ quan trọng và độ chắc chắn đủ lớn, sau đây, chúng ta sẽ tìm hiểu về các tiêu chuẩn đánh giá một luật kết hợp mờ. Định nghĩa 3.2.2[35]. Cho cơ sở dữ liệu D trên tập các thuộc tính I, là một mệnh đề trên I và tập từ LI, MI là biểu diễn của I ứng với LI. Xét d D là một bản ghi. Khi đó, độ ủng hộ của d cho ứng với MI được cho bởi: vote(d,X,A,MI) := (d[]).(d[])…(d[])) (3.2.1) Ý nghĩa của biểu thức trên biểu diễn giá trị đúng đắn của mệnh đề “ là và là và … và là ”. Trong trường hợp không gây nhầm lẫn có thể bỏ qua MI. Trong [35] cũng đề nghị rằng, trong công thức (3.2.1) bên cạnh toán tử nhân, cũng có thể sử dụng toán tử min. Từ đó, ta có thể thấy, trong (3.2.1), chúng ta có thể sử dụng một t-chuẩn trong lôgíc mờ để xác định độ ủng hộ, đặc biệt, ở đây, chúng tôi đề nghị sử dụng t-chuẩn có ngưỡng [9]: vote(d,X,A,MI) := ((d[]),(d[]),…,(d[])) Trong đó, ngưỡng αvk ứng với thuộc tính Iv và từ mô tả thuộc tính này. Việc sử dụng t-chuẩn có ngưỡng ở đây rất có ý nghĩa đối với một số bài toán thực tế. Lấy ví dụ, đối với thuộc tính lượng xăng tiêu thụ trung bình của xe máy, nếu độ thuộc của giá trị này vào từ “rất cao” là lớn, chúng ta nên và cần thiết sử dụng những xem xét khác với các trường hợp khác. Vấn đề sử dụng t-chuẩn có ngưỡng trong việc xác định độ ủng hộ của một bản ghi đối với một mệnh đề sẽ được mô tả rõ hơn ở phần sau. Định nghĩa 3.2.3 [35]. Khi đó độ hỗ trợ của trong D ứng với MI : supp(X,A,D,MI) := Trong trường hợp không gây nhầm lẫn, có thể bỏ qua D và MI. Bên cạnh khái niệm độ hỗ trợ, chúng ta cũng có thể sử dụng khái niệm độ quan trọng. Định nghĩa 3.2.4[35]. Độ quan trọng của trong D ứng với MI : sign(X,A,D,MI) := Trong trường hợp không gây nhầm lẫn, có thể bỏ qua D, MI. Trong bài toán tìm luật kết hợp mờ, chúng ta chỉ quan tâm tới những mệnh đề có độ hỗ trợ (độ quan trọng) là đủ lớn, nghĩa là vượt một ngưỡng cho trước nào đó. Nghĩa là, chúng tôi chỉ quan tâm tới những mệnh đề có supp(X,A,D,MI) ≥ σabs hay sign(X,A,D,MI) ≥ σrel, với σabs và σrel là các ngưỡng cho trước nào đó. Nếu một mệnh đề có độ hỗ trợ đủ lớn ta gọi mệnh đề đó là đáng kể. Định nghĩa 3.2.5. Tập các mệnh đề đáng kể trên D ứng với ngưỡng σ và MI được cho bởi: S(D,σ,MI) := { | supp(X,A) ≥ σ} Bài toán 3.2.1. (Tìm mệnh đề) Cho trước một tập thuộc tính I, LI là tập từ mô tả I, MI là tập hàm thuộc biểu diễn I ứng với LI, một cơ sở dữ liệu D trên I, và ngưỡng hỗ trợ nhỏ nhất σ, tìm S(D,σ,MI). Trong thực tế, chúng ta không chỉ cần các mệnh đề đáng kể mà còn cần xác định cả độ hỗ trợ của chúng để sử dụng khi tìm luật kết hợp. Luật kết hợp Trong phần này, chúng tôi sẽ mô tả luật kết hợp và các tiêu chí để đánh giá một luật kết hợp là quan tâm. Định nghĩa 3.2.6. Cho trước một tập thuộc tính I, LI là tập các từ mô tả I, MI là tập các hàm thuộc biểu diễn I ứng với LI, D là một cơ sở dữ liệu trên I, mục tiêu của chúng tôi là tìm các luật dạng “Nếu X là A thì Y là B” có biểu diễn hình thức → , trong đó X, Y I là tập các thuộc tính, X Y = {}, A, B là các tập từ mô tả X, Y tương ứng. Phần được gọi là phần thân (hay tiền tố) của luật, được gọi là phần đầu (hay hệ quả) của luật. Ý nghĩa của luật này nói lên việc nếu “X là A” được thoả mãn thì “Y là B” cũng được thoả mãn. Định nghĩa 3.2.7[35]. Cho trước một tập thuộc tính I, tập từ LI mô tả I, tập hàm thuộc MI biểu diễn I ứng với LI, D là cơ sở dữ liệu trên I, X, Y I là các tập thuộc tính, X Y = {}, A, B là các tập từ mô tả X, Y tương ứng. Độ hỗ trợ của luật → trên D ứng với MI được cho bởi: supp( → ,D,MI) = supp(X Y,A B,D,MI) Độ chắc chắn (certainty) của luật trên D ứng với MI được cho bởi: cert( → ,D,MI) = Trong trường hợp không gây nhầm lẫn, có thể bỏ qua D, MI. Luật được gọi là tin chắc nếu độ chắc chắn của nó vượt một ngưỡng độ chắc chắn tối thiểu γ cho trước nào đó. Một luật được gọi là quan tâm nếu nó là đáng kể và tin chắc. Định nghĩa 3.2.8. Tập các luật quan tâm được ký hiệu: R(D,σ,γ,MI) = { → | X,Y I, X Y = {}, S(D,σ,MI), cert( → ) ≥ γ} Bài toán 3.2.2. (Tìm luật) Cho trước I là tập thuộc tính, LI là tập các từ mô tả I, MI là tập các hàm thuộc biểu diễn I ứng với LI, D là cơ sở dữ liệu trên I, σ, γ tương ứng là các ngưỡng độ hỗ trợ và độ chắc chắn tối thiểu, tìm R(D,σ,γ,MI). t-chuẩn có ngưỡng và độ ủng hộ Trong phần này, chúng tôi sẽ mô tả các khái niệm cơ bản của việc sử dụng t-chuẩn có ngưỡng trong việc xác định độ ủng hộ của một bản ghi đối với một mệnh đề. Trước hết là mở rộng t-chuẩn từ 2 biến cho n-biến [19] Cho t là t-chuẩn, ký hiệu t(x1,…,xn) = t(t(x1,…,xn-1),xn), với n ≥ 3 Cho I = {I1,…,In} là tập thuộc tính, với mỗi thuộc tính Iv, với mỗi thuộc tính Iv, xét Lv = {, …, } là tập từ mô tả thuộc tính đó, là hàm thuộc ứng với từ . Với mỗi từ , ta có là ngưỡng ứng với từ này. Xét t1, t2 là hai t-chuẩn sao cho t1(x,y) ≤ t2(x,y) với mọi x, y [0,1]2. Xét mệnh đề trên I, trong đó X = {, …, }, A = {, …, }, ta có độ ủng hộ của d cho được xác định như sau: vote(d,X,A) = Chú ý ở đây, các miền ngưỡng đối với mỗi từ mô tả cũng như các t-chuẩn thành phần t1, t2 do người sử dụng cung cấp phụ thuộc vào từng bài toán phân tích dữ liệu cụ thể. Không gian tìm kiếm Việc tìm tất cả các mệnh đề đáng kể cũng như các luật tin chắc có một số khó khăn nhất định. Không gian tìm kiếm là hàm mũ đối với số thuộc tính có trong giao dịch. Trong phần này, chúng ta sẽ xem xét về kích thước của không gian tìm kiếm cũng như một số kết quả nhằm làm thu hẹp không gian tìm kiếm. Tìm mệnh đề Cho I là tập thuộc tính, giả sử kích thước trung bình của tập từ mô tả một thuộc tính là k, ta có kết quả sau về không gian tìm kiếm các mệnh đề. Mệnh đề 3.3.1. Không gian tìm kiếm tất cả các mệnh đề có khoảng (k+1)|I| mệnh đề khác nhau. Chứng minh: Ta có mỗi một thuộc tính có thể xuất hiện hoặc không xuất hiện trong một mệnh đề, và nếu xuất hiện thì có thể sử dụng một trong k từ để mô tả nó, như thế số mệnh đề có thể có (tính cả mệnh đề rỗng, nghĩa là mệnh đề không có thuộc tính nào) sẽ là: (k+1)|I| Như thế, tiếp cận ngây thơ là khởi tạo và tính độ hỗ trợ của tất cả các mệnh đề trong cơ sở dữ liệu là không thực tế về mặt thời gian. Thay vào đó, ở đây, chúng ta sử dụng phương pháp phát triển từ bài toán luật kết hợp Boolean [3] đó là tạo ra mệnh đề ứng viên sau đó xác định độ độ hỗ trợ của chúng để tìm tất cả các mệnh đề đáng kể. Ta có định nghĩa một cách hình thức sau. Định nghĩa 3.3.1 (mệnh đề ứng viên) Cho trước một cơ sở dữ liệu giao dịch D, ngưỡng độ hỗ trợ nhỏ nhất σ, một thuật toán xác định F(D,σ), một mệnh đề được gọi là ứng viên nếu thuật toán này xác định liệu có phải là đáng kể hay không. Nói chung, một thuật toán tốt cần phải tạo ra đủ và càng ít mệnh đề ứng viên càng tốt. Tốt nhất là thuật toán chỉ tạo ra những mệnh đề đáng kể, tuy nhiên, điều này là không thể xảy ra trong thực tế. Vấn đề là cần đánh giá một mệnh đề có phải là ứng viên hay không. Chúng ta có kết quả về tính đơn điệu của độ hỗ trợ của mệnh đề, đây chính là một mở rộng của tính đơn điệu độ hỗ trợ của tập mục đã được nhắc đến trong [22]. Trước hết, ta có định nghĩa. Định nghĩa 3.3.2: Cho I là tập các thuộc tính, X = {, , …, } I là tập thuộc tính, A = {, , …, } là tập từ mô tả X, Y = {, , …, } X (chú ý rằng q ≤ p). Khi đó: A|Y := {, , …, } được gọi là chiếu của A trên Y. Mệnh đề được gọi là mệnh đề con của mệnh đề Mệnh đề được gọi là chứa mệnh đề Từ định nghĩa của độ ủng hộ và tính đơn điệu của t-chuẩn [19] cũng như t-chuẩn có ngưỡng [9], ta có kết quả sau về tính đơn điệu của độ ủng hộ. Mệnh đề 3.3.2. (Tính đơn điệu của độ ủng hộ) Cho X, Y I là hai tập thuộc tính, A là tập từ mô tả X, d là một bản ghi của D, khi đó: Y X vote(d,X,A) ≤ vote(d,Y,A|Y) Dựa vào kết quả trên, và định nghĩa của độ hỗ trợ, ta có kết quả sau: Mệnh đề 3.3.3. (Tính đơn điệu của độ hỗ trợ) Cho X, Y I là hai tập thuộc tính, A là tập từ mô tả X. Khi đó: Y X supp(X,A) ≤ supp(Y,A|Y) Như thế, nếu một mệnh đề là không đáng kể thì tất cả các mệnh đề chứa nó là không đáng kể. Trên cơ sở đó, ta có thể kiểm tra một mệnh đề có phải là ứng viên không thông qua việc kiểm tra các mệnh đề con của nó có phải là đáng kể không. Tìm luật Tương tự như bài toán tìm mệnh đề, cho I là tập thuộc tính, và giả sử lực lượng của tập từ mô tả mỗi thuộc tính là k, ta có kết quả sau về kích thước không gian tìm kiếm của bài toán tìm luật. Mệnh đề 3.3.4. Không gian tìm kiếm tất cả các luật kết hợp có khoảng (2k+1)|I| luật có thể có. Chứng minh: Thật vậy, với mỗi thuộc tính có thể hoặc không xuất hiện trong một mệnh đề, nếu xuất hiện thì có thể xuất hiện hoặc ở phần đầu hoặc ở phần thân, và có thể sử dụng một trong k từ để mô tả, nghĩa là ta có (2k+1)|I| luật có thể có. Cũng giống như bài toán tìm mệnh đề, chúng ta cũng nên sử dụng các mệnh đề ứng viên để thu hẹp không gian tìm kiếm, ta có kết quả sau về tính đơn điệu của độ chắc chắn. Mệnh đề 3.3.5. (Tính đơn điệu của độ chắc chắn) Cho X, Y, Z I là ba tập thuộc tính, sao cho X Y = {}, A là tập từ mô tả X Y Z, khi đó: cert(→) ≤ cert(→) Chứng minh: Do X Y X Y Z nên theo mệnh đề 3.1.3, ta có: supp(X Y Z,A) ≤ supp(X Y,) Mặt khác, do X\Z X, nên cũng theo mệnh đề 3.1.3, ta có: supp(X,A|X) ≤ supp(X\Z,A|X\Z) Từ đó, ta có: cert(→) = ≤ = cert( → ) □. Nói cách khác, độ chắc chắn là đơn điệu giảm theo sự mở rộng của phần đầu của luật, theo nghĩa một thuộc tính nằm ở phần thân được chuyển sang phần đầu. Do đó, nếu một phần đầu của một luật kết hợp chỉ tạo từ tập thuộc tính I và tập từ mô tả A là không tin chắc thì mọi phần đầu chứa nó cũng sẽ cho một luật không tin chắc tạo từ tập thuộc tính I và tập từ A. Trên cơ sở các khảo sát về tính đơn điệu của độ hỗ trợ cũng như độ chắc chắn, trong phần sau, chúng tôi sẽ mô tả một thuật toán tìm luật kết hợp mờ. Thuật toán Thuật toán được mô tả ở đây là một phát triển của thuật toán Apriori đã được mô tả trong [3], gồm hai bước như sau. B1: Tìm tất cả các mệnh đề đáng kể có độ độ hỗ trợ vượt ngưỡng độ hỗ trợ nhỏ nhất σ. B2: Với các mệnh đề đã tìm được trong B1, xét tập con thực sự X của Z. Xác định: cert(→) =, ghi nhận luật kết hợp → nếu cert(→) đạt ngưỡng độ tin cậy nhỏ nhất γ. Từ mệnh đề 3.3.3, ta có nếu là đáng kể thì cũng là đáng kể. Vì thế, chúng tôi sẽ lưu độ độ hỗ trợ của các mệnh đề được tìm thấy trong B1 để sử dụng cho B2. Tìm mệnh đề Thuật toán sau sử dụng cho pha tìm kiếm mệnh đề. Chúng tôi sử dụng ký hiệu X[i] để biểu diễn thuộc tính thứ i trong X, A[i] là từ thứ i trong tập từ A, L(I) là tập từ mô tả thuộc tính I, Ck là tập các tập mệnh đề ứng viên độ dài k và Sk là tập các mệnh đề đáng kể độ dài k. Thuật toán 1 F-Apriori-Tìm kiếm mệnh đề Vào: D,σ,LI,MI Ra: S(D,σ) Thuật toán: //Khởi tạo tập các ứng viên độ dài một bằng tất cả các mệnh đề độ dài 1 C1 := { | i I, a L(i)} k := 1 while Ck ≠ {} do //Tính độ hỗ trợ của tất cả các mệnh đề ứng viên for all d D do for all mệnh đề ứng viên Ck do .supp := .supp+vote(d,X,A) end for end for //Tìm tất cả các mệnh đề đáng kể Sk := { Ck|.supp ≥ σ} //Tạo mệnh đề ứng viên mới Ck+1 := {} for all , Sk, X[i] = Y[i], A[i] = B[i] với 1 ≤ i ≤ k-1, và X[k] < Y[k] do I := X {Y[k]} D := A {B[k]} if S2 then Ck+1 := Ck+1 {} end if end for k++ end while Phân tích. Thuật toán thực hiện quá trình tìm kiếm theo chiều rộng trên không gian tìm kiếm tất cả các tập mục bằng cách khởi tạo tập các tập mục ứng viên Ck+1, bắt đầu với k = 0 (dòng 2). Một mệnh đề là ứng viên nếu tất cả các tập con của nó đều đã được biết là đáng kể, đặc biệt, C1 sẽ chứa tất cả các mệnh đề độ dài 1 có thể có. Công việc tạo mệnh đề ứng viên ở bước k được tiến hành qua hai bước. Đầu tiên là bước giao, Sk được lấy giao với chính nó. Mệnh đề hợp của các mệnh đề , Sk được tạo ra nếu chúng có chung k-1-tiền tố (dòng 15-16). Trong bước lược bỏ, X Y chỉ được thêm vào Ck+1 nếu mệnh đề có trong S2 (dòng 18). Trong dòng 15, chúng tôi chỉ sử dụng phép so sánh bằng giữa các từ mô tả thuộc tính, vì thế vấn đề thứ tự trong tập từ mô tả một thuộc tính không được đặt ra ở đây. Từ đó, vấn đề sử dụng tập từ mô tả của thuộc tính có thể rất rộng, bao hàm cả việc sử dụng các gia tử đối với các tập từ này, cũng như những phép toán trên từ khác. Để đếm độ hỗ trợ của tất cả các k-tập mục ứng viên, thuật toán tiến hành quét cơ sở dữ liệu và cập nhật độ hỗ trợ của tất cả các tập mục ứng viên (dòng 6-10). Tất cả các mệnh đề đáng kể độ dài k được cho vào Sk (dòng 12). Nếu số lượng các mệnh đề độ dài k+1 ứng viên là quá lớn để lưu trữ trong bộ nhớ chính, quá trình tạo ứng viên sẽ ngừng lại và tiến hành tính toán độ hỗ trợ của các ứng viên đã được tạo ra. Nhưng sau đó, trong bước lặp tiếp theo, thay vì tính các mệnh đề ứng viên độ dài k+2, phần còn lại của các các mệnh đề ứng viên độ dài k+1 sẽ được tạo ra và đếm cho đến khi đã sinh được tất cả các mệnh đề đáng kể độ dài k+1. Tiếp sau đây, chúng ta xét thuật toán tìm luật kết hợp. Tìm luật kết hợp Thuật toán tìm luật kết hợp cũng tương tự như thuật toán tìm mệnh đề, bắt đầu từ các mệnh đề đáng kể, xác định các phần đầu ứng viên, sau đó kiểm tra xem các phần đầu ứng viên có làm cho luật trở thành tin chắc không. Thuật toán 2 F-Apriori-Tìm luật kết hợp Vào: D, σ, γ, LI, MI Ra: R(D,σ,γ) Thuật toán: Tính S(D,σ) R := {} for all S do C1 := {{i} | i I*} k := 1 while Ck ≠ {} do //Tìm tất cả các phần đầu của các luật kết hợp tin chắc} Hk := {X Ck | cert( → ,D) ≥ γ} //Tạo các phần đầu ứng viên mới Ck+1 := {} for all X,Y Hk, X[i] = Y[i] với 1 ≤ i ≤ k-1, và X[k] < Y[k] do I := X {Y[k] } if X[k]Y[k] Hk then Ck+1 := Ck+1 {I} end if end for k++ end while //Lưu lại tất cả các luật kết hợp R := R { → | X H1 … Hk} end for Phân tích. Đầu tiên, tất cả các mệnh đề đáng kể được tính theo thuật toán 1, Sau đó, tất cả các mệnh đề đáng kể I* được chia thành phần đầu ứng viên Y và phần thân X = I*\Y. Thuật toán tiến hành tạo các phần đầu ứng viên độ dài k+1 Ck+1, bắt đầu với k = 0 (dòng 4). Phần đầu sẽ là ứng viên nếu tất cả các tập con của nó đều đã biết là biểu diễn cho một luật tin chắc. Quá trình tạo các phần đầu ứng viên này tương tự như quá trình tạo mệnh đề ứng viên trong thuật toán 1 (dòng 10-16). Để tính độ tin cậy của luật có Y là phần đầu, độ hỗ trợ của I và X đã có từ bước tính F. Tất cả các phần đầu làm cho luật tin chắc được lưu trong Hk (dòng 8). Cuối cùng tất cả các luật tin chắc được lưu trong R (dòng 20). Chú ý rằng ở đây, mỗi khi xét một mệnh đề đáng kể, tập từ mô tả nó là hoàn toàn xác định, do đó, mặc dù khi kiểm tra, chúng ta phải kiểm tra các từ này, nhưng trong các bước tạo tập ứng viên chỉ cần quan tâm các thuộc tính mà không cần quan tâm tới các từ (dòng 8, 12-14) □. Vấn đề mờ hoá dữ liệu Từ đầu đến giờ, chúng tôi đã giả thiết làm việc trên cơ sở dữ liệu mờ, trong đó mỗi một thuộc tính được mô tả bằng một bộ từ, ứng với mỗi một từ là một hàm thuộc xác định mức độ đúng đắn của việc dùng từ để mô tả một giá trị của thuộc tính tương ứng. Trong phần này, chúng tôi sẽ nói kỹ hơn về hàm thuộc này và các vấn đề liên quan. Trong thực tế, hàm thuộc thường phụ thuộc vào bài toán cụ thể, hay nói cách khác, việc xác định tập từ mô tả cũng như hàm thuộc của chúng có thể người dùng hay các chuyên gia về lĩnh vực đang xét cung cấp. Tuy nhiên, ở đây có một số khó khăn nhất định. Thứ nhất, không phải tập từ và hàm thuộc tương ứng nào do các chuyên gia cung cấp cũng thích hợp với việc tìm luật kết hợp mờ trong cơ sở dữ liệu. Thứ hai, yêu cầu cung cấp những hàm này, đôi khi là rất khó khăn đối với các chuyên gia, đặc biệt đối với các chuyên gia không chuyên về các lĩnh vực toán học. Nói chung, chất lượng của kết quả trả về của thuật toán phụ thuộc chủ yếu vào tập từ và hàm thuộc có phù hợp đối với cơ sở dữ liệu cho trước hay không. Vấn đề đối với hầu hết các ứng dụng là rất khó để xác định tập từ cũng như hàm thuộc nào là thích hợp nhất. Để giải quyết các vấn đề trên, và cũng để phục vụ cho việc nghiên cứu những cơ sở dữ liệu thuộc những lĩnh vực mà chúng tôi không phải chuyên gia, chúng tôi đề nghị phương pháp tạo các tập từ cũng như các hàm thuộc tương ứng một cách tự động. Chú ý rằng, chúng ta cần một thuật toán hiệu quả, sử dụng trên một cơ sở dữ liệu lớn, nói chung sẽ được lưu trữ trên bộ nhớ ngoài, nghĩa là được truy cập tuần tự, các thao tác vào ra dữ liệu là rất tốn kém. Phương pháp chúng tôi sử dụng ở đây dựa trên một phương pháp phân cụm nhằm tìm các trung tâm cụm dữ liệu tương ứng với c từ mô tả cho mỗi thuộc tính, sau đó xây dựng c hàm thuộc từ c trung tâm này. Bài toán phân cụm dữ liệu và phân cụm mờ Trong khoảng 30 năm trở lại đây, phân cụm dữ liệu có rất nhiều ứng dụng trong nhiều lĩnh vực như y tế (phân loại bệnh), hoá học (phân nhóm các hợp chất), xã hội học (phân lớp thống kê),… Mục đích chính của công tác phân cụm dữ liệu là nhận dạng cấu trúc hay các cụm có trong dữ liệu, nghĩa là tìm cách chia dữ liệu thành các nhóm trong đó dữ liệu trong một nhóm là gần gũi với nhau theo một nghĩa nào đó. Các thuật toán phân cụm dữ liệu thực chất là một thao tác gán nhãn các véc tơ. Nghĩa là, cho trước n đối tượng cần phân vào c cụm. Bài toán phân cụm là tìm cách gán nhãn cho n véc tơ Uk = (u1k,…,uck)t, k = , với ý nghĩa uik là mức độ thuộc của đối tượng thứ i vào cụm thứ j. Nếu uik {0,1} và = 1 với mọi i, k thì ta có bài toán phân cụm rõ. Nếu uik [0,1] và với mọi k i để uik > 0, ta có bài toán phân cụm mờ. Bài toán tìm hàm thuộc cho c từ mô tả thuộc tính trở thành bài toán phân cụm mờ miền giá trị của một thuộc tính thành c cụm. Các thuật toán phân cụm dữ liệu cho đến này có thể được chia thành hai loại: các phương pháp cấu trúc (hierarchical methods) và các phương pháp phân hoạch (partitioning methods). Các phương pháp cấu trúc hoặc sử dụng phương pháp tích tụ hoặc là phương pháp phân chia. Cho trước n đối tượng cần phân cụm, phương pháp tích tụ bắt đầu với n cụm (mỗi cụm một đối tượng) sau đó các cụm được chọn và được nối lại với nhau. Trong khi đó, phương pháp phân chia bắt đầu bằng cách đặt tất cả các đối tượng trong một cụm sau đó tiến hành chia nhỏ dần các cụm. Các phương pháp cấu trúc tỏ ra rất thành công trong các ứng dụng sinh học (tạo ra các phân loại động hay thực vật), tuy nhiên chúng lại tỏ ra yếu kém do không bao giờ có thể sửa đổi được những thao tác đã được tiến hành trước đó. Một khi phương pháp tích tụ tiến hành kết hợp các cụm thì các đối tượng trong đó sẽ luôn luôn ở trong cùng một cụm, một khi phương pháp chia nhỏ chia tác hai đối tượng, chúng sẽ không bao giờ được nhóm trở lại trong cùng một cụm. Phương pháp phân hoạch dựa trên việc cho trước số lượng c phân hoạch cần tìm, cố gắng tìm c phân hoạch tốt nhất cho n đối tượng. Phương pháp phân cụm mờ dựa trên phân hoạch tìm c biểu diễn cho c phân hoạch, sau đó độ thuộc của mỗi đối tượng vào mỗi cụm được xác định theo mức độ gần gũi của đối tượng với biểu diễn của cụm này. Cho đến nay, có nhiều phương pháp phân hoạch đã được phát triển, chia thành hai hướng chính là c-means và c-medoids. Phương pháp c-means tìm c trung tâm (mean) cho c cụm, sau đó mỗi một đối tượng được chia vào cụm có trung tâm gần nó nhất. Phương pháp c-medoids tìm đối tượng biểu diễn cho mỗi cụm, gọi là các medoid, nghĩa là đối tượng gần với trung tâm của cụm nhất. Ở đây chúng tôi xem xét việc sử dụng phương pháp c-means làm nền tảng cho việc phân cụm mờ vì một số ưu điểm sau: phương pháp này tỏ ra hiệu quả đối với các dữ liệu nói chung có phân bố tương đối đều đặn, thứ hai, phương pháp này không bị phụ thuộc vào thứ tự xem xét của các đối tượng, và đặc biệt, với cài đặt cải tiến, phương pháp này tỏ ra thích hợp với cơ sở dữ liệu lớn và được lưu trữ tuần tự như trên đã nói. Phần sau sẽ mô tả thuật toán FCM (Fuzzy c-means), thuật toán này đã được mô tả chi tiết trong [4]. Thuật toán FCM Phương pháp FCM dựa trên việc tối tiểu hàm J(U,V,w) = + theo U, V. Trong đó U = (U1,…,Un) được gọi là ma trận phân cụm mờ với Uk = (u1k,…,uck)t, gọi là véc tơ phân cụm mờ của đối tượng thứ i, trong đó uik biểu diễn mức độ phụ thuộc của đối tượng thứ k vào cụm thứ i, V = (v1,…,vc) là biểu diễn của c-trung tâm cụm. xk là biểu diễn của đối tượng thứ k, wi là hệ số phạt, ứng với tổn thất của việc phân loại một đối tượng vào cụm thứ i, m ≥ 1 là độ mờ của phân lớp, Dik(xk,vi) là độ không tương tự giữa đối tượng thứ k và trung tâm cụm thứ i. Trong thực hành, wi thường được chọn bằng 0, biểu thị mức độ ngang bằng của các cụm trong phân lớp, m thường được chọn bằng 2 và Dik thường được chọn là khoảng cách Euclide trong trường hợp các đối tượng được biểu diễn như là các điểm trong không gian nhiều chiều. Dựa trên các kết quả giải tích, với việc chọn cách hệ số phạt bằng 0, Dik là khả vi theo xk và vi, ta có, với V cho trước, thì: uik = (3.5.1) và với U cho trước, thì vi = (3.5.2) Từ đó ta có thuật toán FCM như sau: Thuật toán 3-FCM Vào X = {x1,…,xn}, c Ra U,V; T số bước lặp tối đa, e sai số tối thiểu Thuật toán: Khởi tạo ngẫu nhiên c tâm cụm V = {v1,…,vc} Khởi tạo t = 0 Do t := t+1; V* := V; Tính U theo 3.5.1; Tính V theo 3.5.2; E := maxi|vi-vi*| While (t e) Phương pháp chia đều Bên cạnh phương pháp FCM, chúng tôi cũng sử dụng một phương pháp phân cụm tự động có thể là khá thô sơ tuy nhiên cũng tỏ ra rất hữu dụng trong một số trường hợp. Phương pháp này hoạt động như sau. Giả sử, ta có miền dữ liệu là [a,b] R cần được chia thành c cụm (c ≥ 3), xác định vi = a + i (i = ), khi đó độ thuộc của phần tử xk (k = vào cụm i được xác định thông qua việc sử dụng các số mờ tam giác như sau: u1k = uck = uik = : 2 i c-1 Các kết quả thực nghiệm cho thấy, phương pháp chia đều cho kết quả phân cụm khá tốt, theo nghĩa là kết quả phân cụm mờ thể hiện được đặc trưng của dữ liệu đầu vào nếu như số cụm là nhỏ (3 hoặc 5 cụm). Ngoài ra, phương pháp chia đều cũng có thể được sử dụng ở bước khởi tạo (dòng 1) trong thuật toán FCM. Kết luận Trong chương này, chúng tôi đã mô tả các khái niệm cơ bản của bài toán luật kết hợp mờ, phân tích về không gian tìm kiếm, và cuối cùng đưa ra thuật toán F-Apriori để giải bài toán này. Chúng tôi cũng đã nêu lên phương pháp sử dụng t-chuẩn có ngưỡng đối với bài toán luật kết hợp mờ. Thuật toán F-Apriori và phương pháp tính độ ủng hộ sử dụng t-chuẩn cũng như t-chuẩn có ngưỡng đã được cài đặt bằng Visual Basic 6.0 và chạy thử nghiệm.  Các toán tử mờ có ngưỡng tham số Sau đây, chúng tôi sẽ liệt kê một số họ t-chuẩn có ngưỡng dựa trên các xem xét giải tích đã đề cập đến trong phần 2.2.5. Chú ý là khi xác định IT, ta chỉ cần xét trường hợp y < x, do theo [19], ta đã có khi y ≥ x thì IT(x,y) = 1. Họ loại 1 T(x,y,α): t1(x,y) = min(x,y) t2(x,y) là t-chuẩn bất kỳ S(x,y,β) s1(x,y) = max(x,y) s2(x,y) là t-đối chuẩn bất kỳ IS(x,y,γ): i1(x,y) = max(n(x),y) i2(x,y) = s2(n(x),y) với n là phép toán phủ định, s2 là t-đối chuẩn bất kỳ. IT(x,y,γ): i1(x,y) = y i2(x,y) = supz{t2(x,z) ≤ y} với t2 là t-đối chuẩn bất kỳ Họ loại 2: T(x,y,α) t1(x,y) là t-chuẩn bất kỳ t2(x,y) = S(x,y,β) s1(x,y) là t-đối chuẩn bất kỳ s2(x,y) = IS(x,y,γ) i1(x,y) = s1(n(x),y) với n là phép phủ định, s1 là t-đối chuẩn bất kỳ. i2(x,y) = IT(x,y,γ): i1(x,y) = supz{t1(x,z) ≤ y} với t1 là t-chuẩn bất kỳ i2(x,y) = Dombi-Jane Doe #1-Hamacher 0 < r2 ≤ r1, a2 ≥ a1 ≥ 0 T(x,y,α): t1 = t2 = S(x,y,β): s1 = s2 = IS(x,y,γ): i1 = i2 = IT(x,y,): i1 = i2 = Aczél-Alsina r1 > r2 > 0 T(x,y,α): t1 = t2 = S(x,y,β): s1 = s2 = IS(x,y,γ) i1 = i2 = IT(x,y,γ): i1 = i2 = Frank a1 > a2 > 0 T(x,y,α): t1 = t2 = S(x,y,β): s1 = 1- s2 = 1- IS(x,y,γ): i1 = 1- i2 = 1- IT(x,y,γ): i1 = i2 = Schweizer a1 < a2 T(x,y,α): t1 = t2 = S(x,y,β): s1 = 1- s2 = 1- IS(x,y,γ): i1 = 1- i2 = 1- IT(x,y,γ): i1 = i2 = Jane Doe #2 a2 > a1 ≥ 0 T(x,y,α): t1 = xy t2 = xy S(x,y,β): s1 = 1-(1-x)(1-y) s2 = 1-(1-x)(1-y) IS(x,y,γ): i1 = 1-x(1-y) i2 = 1-x(1-y) IT(x,y,γ): i1 = i2 = Jane Doe #3 a2 > a1 > 0 T(x,y,α): t1 = t2 = S(x,y,β): s1 = s2 = IS(x,y,γ): i1 = i2 = IT(x,y,γ): i1 = 1- i2 = 1- Yager a1 > a2 > 0 T(x,y,α): t1 = t2 = S(x,y,β): s1 = 1- s2 = 1- I(x,y,γ): i1 = 1- i2 = 1- Weber a2 > a1 > 0 T(x,y,α): t1 = (a1(x+y-1)-(a1-1)xy) 0 t2 = (a2(x+y-1)-(a2-1)xy) 0 S(x,y,β): s1 = 1 s2 = 1 I(x,y,γ): i1 = i2 = Jane Doe #4 a2 > a1 > 0 T(x,y,α): t1 = 0 t2 = 0 S(x,y,β): s1 = (x+y+(a1-1)xy) 1 s2 = (x+y+(a2-1)xy) 1 I(x,y,): i1 = i2 = Jane Doe #6 a1 < a2; a1, a2 ≠ 1 T(x,y,α): t1 = t2 = S(x,y,β): s1 = s2 = I(x,y,γ): i1 = i2 = Yager-Schweizer a > 1 (Trường hợp a < 1 tương tự) T(x,y,α): t1 = t2 = S(x,y,β): s1 = s2 = 1- I(x,y,γ): i1 = i2 = 1- Weber-Jane Doe #4 a > 1 (Trường hợp a < 1 tương tự) T(x,y,α): t1 = (a(x+y-1)-(a-1)xy) 0 t2 = S(x,y,β): s1 = (1-a(1-x-y)+(a-1)(1-x)(1-y)) 1 s2 = 1 I(x,y,γ) i1 = 1-a(x-y)+(a-1)x(1-y) i2 = 1-((x-y)+(a-1)x(1-y)) Jane Doe #3-Yager a > 0 T(x,y,α): t1(x,y) = 1 - t2(x,y) = max S(x,y,β): s1(x,y) = s2(x,y) = min IS(x,y,γ): i1(x,y) = i2(x,y) = min IT(x,y,γ): i1(x,y) = i2(x,y) = min Frank-Jane Doe #6 a > 0, a ≠ 1 T(x,y,α) t1(x,y) = loga t2(x,y) = loga S(x,y,β) s1(x,y) = 1-loga s2(x,y) = 1-loga IS(x,y,γ): i1(x,y) = 1-loga i2(x,y) = 1-loga IT(x,y,γ): i1(x,y) = loga i2(x,y) = 1-loga  Chương trình Fuzzy Rules Miner Chương trình Fuzzy Rules Miner được xây dựng nhằm thực hiện quá trình tìm kiếm các luật kết hợp mờ trên cơ sở dữ liệu lượng hoá. Chương trình được viết và biên dịch bằng bộ trình biên dịch Microsoft Visual Basic 6.0. Chương trình gồm các Module sau. Các Module chương trình mdiMain Đóng vai trò điều khiển, gọi các chức năng của chương trình. frmFuzzySetFinder Làm nhiệm vụ mờ hoá dữ liệu đầu vào Hình 1: Module frmFuzzySetFinder Module cho phép người sử dụng nhập dữ liệu đầu vào là cơ sở dữ liệu lượng hoá (file .QDF) và file định dạng cơ sở dữ liệu (.CFF). Người sử dụng có thể chọn phương pháp tìm c tâm cụm theo FCM hay theo phương pháp chia đều. Dữ liệu cũng có thể được mờ hoá theo phương pháp FCM hay theo phương pháp sử dụng số mờ tam giác, sau đó dữ liệu được xuất ra dưới dạng mờ (file .FDF). frmDataMiner Làm nhiệm vụ tìm kiếm các mệnh đề đáng kể và các luật quan tâm với đầu vào là cơ sở dữ liệu mờ. Hình 2: Module frmDataMiner Module cho phép người sử dụng nhập dữ liệu đầu vào là cơ sở dữ liệu mờ (file .FDF). Người sử dụng lựa chọn sử dụng t-chuẩn hay t-chuẩn có ngưỡng, nếu sử dụng t-chuẩn có ngưỡng thì nhập dữ liệu đầu vào là các ngưỡng (file .TF). Nếu người sử dụng dùng các t-chuẩn và t-chuẩn có tham số thì chương trình cũng yêu cầu người dùng nhập các giá trị tham số. Quá trình tìm kiếm mệnh đề và tìm kiếm luật dựa trên ngưỡng độ quan trọng và ngưỡng độ tin cậy do người dùng cung cấp. Mỗi mệnh đề được ghi theo thứ tự gồm các thuộc tính, các từ mô tả các thuộc tính tương ứng, độ hỗ trợ, độ quan trọng. Các thuộc tính được ký hiệu bằng các chữ cái in hoa, các từ được ký hiệu bằng các chữ số. Các luật được ghi theo thứ tự gồm các thuộc tính ở phần thân, các từ mô tả phần thân, các thuộc tính ở phần đầu, các từ mô tả phần đầu, độ hỗ trợ, độ quan trọng và độ chắc chắn của luật. Module cũng cho phép người dùng xuất kết quả tính toán ra file (file .PF chứa các mệnh đề đáng kể và file .RF chứa các luật quan tâm). Cấu trúc các file dữ liệu .CFF File chứa cấu trúc của cơ sở dữ liệu đầu vào gồm các thông số: số bản ghi, số thuộc tính và số từ mô tả cho mỗi thuộc tính. Các thông số được ghi tuần tự ngăn cách nhau bởi khoảng trắng và/hoặc ký tự xuống dòng. .QDF File chứa cơ sở dữ liệu lượng hoá. Dữ liệu được ghi tuần tự theo từng bản ghi và từng thuộc tính. Các số ngăn cách nhau bởi khoảng trắng và/hoặc ký tự xuống dòng. .FDF File chứa cơ sở dữ liệu mờ. Dữ liệu được ghi tuần tự theo từng bản ghi, từng thuộc tính và giá trị hàm thuộc theo từng từ mô tả thuộc tính. Các số ngăn cách nhau bởi khoảng trắng và/hoặc ký tự xuống dòng. .TF File chứa các ngưỡng cho việc sử dụng t-chuẩn các ngưỡng. Các ngưỡng được ghi tuần tự theo từng thuộc tính và theo từng từ mô tả thuộc tính đó. Các số ngăn cách nhau bởi khoảng trăng và/hoặc ký tự xuống dòng. .PF File chứa các mệnh đề đáng kể, mỗi mệnh đề được ghi trên một dòng theo cấu trúc đã mô tả ở trên. .RF File chứa các luật, mỗi luật được ghi trên một dòng theo cấu trúc đã mô tả ở trên. Cơ sở dữ liệu chạy thử nghiệm Mô tả Cơ sở dữ liệu chạy thử nghiệm chứa các đặc tính kỹ thuật của ô tô lấy từ www.ics.uci.edu/~mlearn/. Cơ sở dữ liệu có 398 bản ghi, 9 thuộc tính, trích rút lại 6 thuộc tính sau: mpg Số dặm đi được trên mỗi gallon xăng. cylinders Số xilanh động cơ. displacement Kích thước horsepower Sức ngựa weight Trọng lượng accleration Khả năng tăng tốc Kết quả Kết quả chạy thử nghiệm sử dụng cơ sở dữ liệu mờ hoá theo phương pháp chia đều, mỗi thuộc tính được mô tả bằng ba từ “thấp”, “trung bình”, “cao”. Chạy thử nghiệm với ngưỡng độ hỗ trợ 100, ngưỡng độ chắc chắn 0.8, t-chuẩn có ngưỡng với t1(x,y) = min(x,y), t2(x,y) = xy, các giá trị ngưỡng đều là 0.1. Chương trình tìm ra được 53 mệnh đề đáng kể và 144 luật quan tâm. Sau đây là một số luật tiêu biểu: Thân Đầu Độ quan trọng Độ chắc chắn Xilanh cao Số dặm thấp 32.84% 96.38% Xilanh thấp Sức ngựa thấp 50.86% 96.30% Xilanh thấp Sức ngựa thấp, chiếm chỗ thấp 50.86% 96.29% Xilanh thấp Chiếm chỗ thấp, trọng lượng thấp 47% 90.88% TÀI LIỆU THAM KHẢO A.Amir, R.Feldman, and R.Kashi. A New and Versatile Method for Association Generation. Information Systems, 2:333-347, 1997. R.Argawal, T.Imielinski and A.Swami. Mining Association Rules Between Sets of Item in Large Databases. In P.Buneman and S.Jajodia, editors Proceeding of the 1993 ACM SIGMOD International Conference on Management of Data, volume 22(2) of SIGMOD Record, pages 207-216. ACM Press, 1993. R.Argawal and R.Skirgant. Fast Algorithms for Mining Association Rules in Large Databases. IBM Research Report RJ9839, IBM Almaden Research Center, San Jose, California, June 1994. James C Bezdek. Fuzzy Clustering. In Enrique H Ruspini et al. [39], section F6.2. T.Brijs, B.Goethals, G.Swinnen, K.Vanhoof, and G.Wets. A Data Mining Framework for Optimal Product Selection in Retail Supermarket Data: The Generalized Profset Model. In Ramakrishnan et al. [16], pages 300-304. S.Brin and L.Page. The Anatomy of a Large-scale Hypertextual Web Search Engine. In Proceeding of the Seventh International World-Wide-Web Conference, volume 30 (1-7) of Computer Networks, pages 107-117. Elsevier Science, 1998. N.Cercone, T.Y.Lin, and X.Wu, editors. Proceeding of the 2001 IEEE International Conference on Data Mining. IEEE Computer Society, 2001. Bùi Công Cường và Nguyễn Doãn Phước, Hệ mờ, mạng nơron và ứng dụng, NXB Khoa học và kỹ thuật, 2001. B.C.Cuong. T-norm with threshold and some related problems, Preprint 2000/12, Institute of Mathematics, Hanoi, 2000. B.C. Cuong, L.B.Long, P.V.Loi and D.T.Hieu. Some properties of t-norms with threshold. Proceedings of the second Vietnam-Japan Symposium on Fuzzy Systems and Applications, VJFUZZY’2001, 28-33, 2001. Bui Cong Cuong, Nguyen Hoang Phuong, Ho Khanh Le, Bui Truong Son and Koichi Yamada. Fuzzy Inference Methods Employing T-norm with threshold and Their Implementation. Journal of Advanced Computational Inteligence and Intelligence Informatics , vol.7, n.3, 2003,362-369 B.C.Cuong, Some Lectures on T-norms with Threshold, Preprint 2002/27, Institute of Mathematics, Hanoi, 2002. B.C.Cuong and L.C.Ngoc. Some Remarks on Fuzzy Operators with Threshold. Proceeding of the Sixth International Conference on Fuzzy Systems, AFSS’ 2004, December 15-16, 2004, Hanoi. D.Dubois and H.Prade New results about properties and semantics of fuzzy set-theoretic operators. In Fuzzy Sets: Theory and Applications to Policy Analysis and Information Systems, P.P.Wang and S.K.Chang, editors, Plenum. L.Dehaspe and H.Toivonen. Discovery of Relational Association Rules. In S.Dzeroski and N.Lavrac, editors, Relational Data Mining, pages 189-212. Springer, 2001. U.M.Fayyad, S.G.Djorgovski, and N.Weir. Automating the Analysis and Cataloging of Sky Surveys. In Fayyad et al. [18], pages 471-494. U.M Fayyad, G. Piatetsky-Shapiro, and P.Smyth. From Data Mining to Knowledge Discovery: An overview. In Fayyad et al. [18], pages 1-34. U.M Fayyad, G.Piatetsky-Shapiro, P.Smyth, and R.Uthurusamy, editors. Advances in Knowledge Discovery and Data Mining. MIT Press, 1996. Janos Fodor and Marc Roubens. Fuzzy Preference Modelling and Multicriteria Decision Support. Kluwer Academic Publishers, 1994. Gehrke, C. L.Walker and E. A. Walker. Algebraic Aspect of Fuzzy Connectives. Proceedings of the International Symposium on Medical Informatics and Fuzzy Technologiey, August 26-29, 306- 314, 1999, Hanoi B.Goethals and J.Van den Bussche. On Supporting Interactive Asscociation Rule Mining. In Y.Kambayashi, M.K.Mohamia, and A.M.Tjoa, editors, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, volume 1874 of Lecture Notes in Computer Science, pages 307-316. Springer, 2000. B.Goethals. Efficient Frequent Pattern Mining. PhD thesis, University Limburg, 2002. Gosta Grahne and Jianfei Zhu. Efficiently Using Prefix-trees in Mining Frequent Itemsets. In Proceedings of FIMI ’03. D.Hand, H.Mannila, and P.Smyth. Principle of Data Mining. MIT Press, 2001. D.Hand, D.Keim, and R.T.Ng, editors. Proceeding of the Eight ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2002. J.Han and M.Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2001. J.Han, J.Pei and Y.Yin. Mining Frequent Parterns without Candidate Generation. In W.Chen, J.F.Naughton, and P.A.Bernstein, editors. Proceedings of the 2000 ACM SIGMOD International Cinference on Management of Data, volume 29(2) of SIGMOD Record, pages 1-12. ACM Press, 2000. Hung T. Nguyen and Elbert A. Walker. A first Course in Fuzzy Logic, Second Edition. Chaman&Hall/CRC, NewYork, 2000. T.Imielinski and H.Mannila. A Database Perspective on Knowledge Discovery. Communications of the ACM, 29 (11):58-64, 1996. A. Inokuchi, T.Washio, and H.Motoda. An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data. In Zighed et al. [44], pages 13-23. Ion Iancu. T-norms with thresholds. Fuzzy Sets and Systems, vol. 85, 1997, 83-92. E.P.Klement, R.Mesiar and E.Pap. Triangular Norms. Position paper I: Basic Analytical and Algebraic Properties. FLLL-TR-0208. E.P.Klement, R.Mesiar, and E.Pap. Triangular Norms. Position paper II: General Constructions and Parameterized Families. FLLL-TR-0215. E.P.Klement, R.Mesiar, and E.Pap. Triangular Norms. Position paper III: Continuos t-norms. C.M.Kuok, A.Fu and M.H.Wong. Fuzzy Asociation Rules in Large Databases with Quantitative Attributes. In ACM SIGMOD Record, March, 1998. C.M.Kuok, Ada Fu and Man Hon Wong. Mining Fuzzy Association Rules in Databases. SIGMOD Record, 1998. M.Kuramochi and G.Karypis. Frequent Subgraph Discovery. In Cercone et al [7], pages 313-320. G.Piatesky-Sshapiro and W.J.Frawley. Knowledge Discovery in Databases. AAA1 Press/The MIT Press, Menlo Park, California, 1991. Enrique H Ruspini, Piero P Bonissone and Witold Pedrycz, editors. Handbook of Fuzzy Computation. Institute of Physics Publishing Bristol and Philadelphia, 1998. R.Skirgant and R.Argawal. Mining Quantitative Association Rules in Large Relational Databases. In Prooceedings of ACM SIGMOD, pages 1-12, 1996. L.A.Zadeh. Fuzzy sets. Information Control. 8 338-53. M.J.Zaki. Efficiently Mining Frequent Trees in a Forest. In Hand et al [25], pages 71-80. D.A Zighed, H.J.Komorowski, and J.M. Zytkow, editors. Proceeding of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, volume 1910 of Lecture Notes in Computer Science. Springer, 200.