Chương 1 của luận án trình bày một số vấn đề liên quan đến bài toán phân lớp dữ liệu bằng cây quyết định, cây quyết định mờ và các kiến thức cơ bản của đại số gia tử dùng để nghiên cứu trong quá trình học phân lớp dữ liệu bằng cây quyết định. Nội dung của chương này bao gồm: tập mờ, đại số gia tử và các phương pháp học phân lớp dữ liệu bằng cây quyết định. Lý thuyết tập mờ 1.Tập mờ và thông tin không chắc chắn Thực tế đã chứng minh khái niệm mờ luôn tồn tại, hiện hữu trong các bài toán ứng dụng, trong cách suy luận của con người, ví dụ như trẻ, rất trẻ, hơi già, quá già,. Vì thế, với việc quan niệm các đối tượng được sử dụng phải luôn rõ ràng ở trong logic cổ điển sẽ không không đủ tốt cho việc miêu tả các vấn đề của bài toán thế giới thực.
Như vậy, rất cần một tiếp cận nghiên cứu mới so với logic cổ điển. Zadeh đã đề xuất hình thức hóa toán học của khái niệm mờ [79], từ đó lý thuyết tập mờ được hình thành và ngày càng thu hút sự nghiên cứu của nhiều tác giả. Bằng các phương pháp tiếp cận khác nhau, các nhà nghiên cứu như Dubois, Prade, Mariana, Ishibuchi, Herrera, Yakun Hu,… đã đưa ra những kết quả cả về lý thuyết và ứng dụng cho nhiều lĩnh vực như: điều khiển mờ, cơ sở dữ liệu mờ, khai phá dữ liệu mờ,. Ý tưởng nổi bật của khái niệm tập mờ của Zadeh là từ những khái niệm trừu tượng về ngữ nghĩa của thông tin mờ, không chắc chắn như trẻ-già, nhanh- chậm, cao-thấp, xấu-đẹp,… ông đã tìm cách biểu diễn chúng bằng một khái 10 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử niệm toán học, được gọi là tập mờ, như là một sự khái quát trực tiếp của khái niệm tập hợp kinh điển.
[80] Cho một tập vũ trụ V khác rỗng. Một tập mờ A trên tập vũ trụ V được đặc trưng bởi hàm thuộc: 𝜇𝐴 (𝑥): 𝑉 → [0, 1] (1.1) với 𝜇𝐴(𝑥) là độ thuộc của phần tử x trong tập mờ A. Một tập mờ hữu hạn được ký hiệu bởi: 𝜇𝐴 𝑥1 𝜇𝐴 𝑥2 𝜇𝐴 𝑥𝑛 𝐴= + + ⋯+ (1.2) 𝑥1 𝑥2 𝑥𝑛 Một tập mờ vô hạn được ký hiệu bởi: 𝐴= 𝜇𝐴 (𝑥)/𝑥 (1. Xét tập A gồm 5 người x1, x2, …, x5 tương ứng có tuổi là 10, 15, 50, 55, 70.
Gọi A~ là tập hợp các người có tuổi là “Trẻ”. Khi đó ta có thể xây dựng hàm thuộc như sau: Trẻ(10) = 0.05 và tập mờ 𝐴~ = + + + +. 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 Giá trị hàm µA(x) càng gần tới 1 thì mức độ thuộc của x trong A càng cao. Tập mờ là sự mở rộng của khái niệm tập hợp kinh điển.
Thật vậy, khi A là một tập hợp kinh điển, hàm thuộc của nó, µA(x), chỉ nhận 2 giá trị 1 hoặc 0, tương ứng với x có nằm trong A hay không. Một khái niệm quan trọng trong việc tiếp cận giải bài toán phân lớp đó là phân hoạch mờ. Về hình thức, chúng ta có định nghĩa như sau: Định nghĩa 1. [63] Cho p điểm cố định m1, m2,.
< mp ở trong tập V = [a, b] ⊂ R. Khi đó tập Φ gồm p tập mờ A1, A2, ., Ap (với µ𝐴 , 1 µ𝐴 ,…, µ𝐴 là các hàm thuộc tương ứng) trên V được gọi là một phân hoạch mờ 2 𝑝 của V nếu các điều kiện sau thỏa mãn, ∀k = 1,. µ𝐴 (𝑚𝑘 ) = 1; mk được gọi là một điểm trong nhân của Ak. Nếu x ∉ [mk-1, mk+1], µ𝐴 (𝑥) = 0; trong đó m0 = m1 = a và mp+1 = mp = 𝑘 b.
𝑘 11 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 4. Tất cả mọi điểm trong V đều thuộc một lớp 𝑘 của phân hoạch này với độ thuộc nào đó khác không. Thực tế các khái niệm mờ trong các bài toán ứng dụng rất đa dạng và khó để xác định được các hàm thuộc của chúng một cách chính xác, thông thường dựa trên ngữ cảnh mà khái niệm mờ đó đang được sử dụng. Ngược lại một khái niệm mờ có thể được mô hình hóa bởi các tập mờ.
Trên cơ sở mối quan hệ này, L. Zadeh đã đưa ra khái niệm biến ngôn ngữ. Biến ngôn ngữ Khái niệm biến ngôn ngữ đã được L. Zadeh giới thiệu, là một công cụ quan trọng để phát triển phương pháp lập luận xấp xỉ dựa trên logic mờ [79], [81].
Ông đã viết: “Khi thiếu hụt tính chính xác bề ngoài của những vấn đề phức tạp cố hữu, một cách tự nhiên là tìm cách sử dụng các biến gọi là biến ngôn ngữ; đó là các biến mà các giá trị của chúng không phải là các số mà là các từ hoặc các câu trong một ngôn ngữ tự nhiên hoặc nhân tạo. Động lực cho việc sử dụng các từ, các câu hơn các số là đặc trưng ngôn ngữ của các từ, các câu thường là ít xác định hơn của số”. [81] Biến ngôn ngữ là một bộ gồm năm thành phần (X, T(X), U, R, M), trong đó X là tên biến, T(X) là tập các giá trị ngôn ngữ của biến X, U là không gian tham chiếu của biến cơ sở u, mỗi giá trị ngôn ngữ xem như là một biến mờ trên U kết hợp với biến cơ sở u, R là một qui tắc cú pháp sinh các giá trị ngôn ngữ cho tập T(X), M là qui tắc ngữ nghĩa gán mỗi giá trị ngôn ngữ trong T(X) với một tập mờ trên U. Xét biến ngôn ngữ Age, tức là X = Age, biến cơ sở u thể hiện tuổi con người có miền xác định U = [1, 100].
Khi đó, các giá trị ngôn ngữ tương ứng của biến Age là T(Age) có thể bao gồm các giá trị: {young, old, very old, old, possible old, less old, less young, quite young, more young,. Các giá trị ngôn ngữ young và old được gọi là các giá trị nguyên thủy. Mỗi giá trị ngôn ngữ trong T(Age) là tên của một biến mờ trên U, tức là biến có thể nhận giá trị trên U với một mức độ tương thích trong đoạn [0, 1], ràng buộc trên mỗi giá trị ngôn ngữ 12 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử hình thành ngữ nghĩa cho giá trị ngôn ngữ đó. Chẳng hạn với giá trị nguyên thủy old, quy tắc gán ngữ nghĩa M cho old bằng tập mờ sau: M(old) = {(u, µold(u)) : u ∈ [0, 100]} (𝑢−60) trong đó 𝜇𝑜𝑙𝑑 (𝑢) = 𝑚𝑎𝑥(𝑚𝑖𝑛(1, ), 0) là một cách chọn hàm thuộc cho 20 khái niệm mờ old.
Ngữ nghĩa các giá trị ngôn ngữ khác trong T(Age) có thể tính thông qua tập mờ của các giá trị nguyên thủy bởi các phép toán tương ứng với các gia tử tác động, chẳng hạn như gia tử very, more or less,. Vấn đề mô hình các hóa các gia tử ngôn ngữ sử dụng tập mờ đã được nhiều nhà nghiên cứu quan tâm, chẳng hạn L. Mặt khác, chúng ta thấy việc gán ngữ nghĩa cho biến ngôn ngữ không có quy tắc ràng buộc nhất định như cách chọn hàm thuộc 𝜇𝑜𝑙𝑑(𝑢) ở trên, hơn nữa các phép toán trên tập mờ nói chung không đóng. Vì vậy trong các nghiên cứu của mình về biến ngôn ngữ và lập luận xấp xỉ, L.
Zadeh luôn nhấn mạnh hai đặc trưng quan trọng sau đây của biến ngôn ngữ: 1. Tính phổ quát: miền giá trị của hầu hết các biến ngôn ngữ có cùng cấu trúc cơ sở theo nghĩa các giá trị ngôn ngữ tương ứng là giống nhau ngoại trừ phần tử sinh nguyên thủy. Tính độc lập ngữ cảnh của gia tử và liên từ: ngữ nghĩa của các gia tử và liên từ hoàn toàn độc lập với với ngữ cảnh, khác với giá trị nguyên thủy của các biến ngôn ngữ lại phụ thuộc vào ngữ cảnh. Do đó khi tìm kiếm mô hình cho các gia tử và liên từ chúng ta không phải quan tâm đến giá trị nguyên thủy của biến ngôn ngữ đang xét.
Các đặc trưng này cho phép chúng ta sử dụng cùng một tập gia tử và xây dựng một cấu trúc toán học duy nhất cho miền giá trị của các biến ngôn ngữ khác nhau. Dựa trên khái niệm của biến ngôn ngữ, lý thuyết lập luận xấp xỉ nhằm mô hình hóa quá trình suy luận của con người đã được L. Zadeh đề xuất và nghiên cứu [80]. Vấn đề sử dụng tập mờ để biểu diễn các giá trị ngôn ngữ và dùng các phép toán trên tập mờ để biểu thị các gia tử ngôn ngữ đã cho phép thực hiện các thao tác dữ liệu mờ, một phần nào đã đáp ứng được nhu cầu thực tế của con 13 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử người.
Tuy nhiên, theo cách sử dụng tập mờ cho thấy vẫn có nhiều hạn chế do việc xây dựng các hàm thuộc và xấp xỉ các giá trị ngôn ngữ bởi các tập mờ còn mang tính chủ quan, phụ thuộc nhiều vào ý kiến chuyên gia cho nên dễ mất mát thông tin. Mặc khác, bản thân các giá trị ngôn ngữ có một cấu trúc thứ tự nhưng ánh xạ gán nghĩa sang tập mờ, không bảo toàn cấu trúc đó nữa. Do đó, vấn đề đặt ra là cần có một cấu trúc toán học mô phỏng chính xác hơn cấu trúc ngữ nghĩa của một khái niệm mờ. Đại số gia tử Nhằm để giải quyết các hạn chế của tập mờ, đại số gia tử được ra đời do đề xuất của N.
Việc sử dụng khái niệm đại số gia tử tuyến tính, đầy đủ đã giải đáp tốt các hạn chế đã nêu. Đến nay, đã có nhiều nghiên cứu về lý thuyết cũng như ứng dụng của nhiều tác giả trong và ngoài nước, đã cho chúng ta nhiều kết quả rất khả quan, có khả năng ứng dụng lớn. Các kết quả nỗi bật như: điều khiển mờ và lập luận mờ [3], [4], [5], cơ sở dữ liệu mờ [1], [2], [63], phân lớp mờ [28], [31],… 1. Khái niệm đại số gia tử Xét một ví dụ có miền ngôn ngữ của biến chân lý TRUTH gồm các từ sau: Dom(TRUTH) = {đúng, sai, rất đúng, rất sai, ít nhiều đúng, ít nhiều sai, khả năng đúng, khả năng sai, xấp xỉ đúng, xấp xỉ sai, ít đúng, ít sai, rất khả năng đúng, rất khả năng sai,.}, trong đó đúng, sai là các từ nguyên thuỷ, các từ nhấn rất, ít nhiều, khả năng, xấp xỉ, ít,… được gọi là các gia tử.
Khi đó, miền ngôn ngữ T = Dom(TRUTH) có thể biểu thị như một đại số X = (X, G, H, ), trong đó G là tập các từ nguyên thuỷ {thấp, cao} được xem là các phần tử sinh.