Luận án: Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử

Lý do chọn đề tài Trong cuộc sống con người, ngôn ngữ được hình thành một cách tự nhiên để đáp ứng nhu cầu trao đổi thông tin của xã hội. Hơn thế, ngôn ngữ là công cụ để con người mô tả các sự vật, hiện tượng trong thế giới thực và dựa trên đó để tư duy, lập luận đưa ra những nhận định, phán quyết nhằm phục vụ cho cuộc sống xã hội của chúng ta. Trong thực tế, các khái niệm mờ luôn tồn tại, ví dụ như trẻ, rất trẻ, hơi già, quá già,. nên 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 đủ miêu tả các vấn đề của thế giới thực.

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 nhiều nhà nghiên cứu. Bằng các phương pháp tiếp cận khác nhau, nhiều nhà nghiên cứu như Dubois, Prade [21], Mariana [50], Ishibuchi [36], Herrera [8], Yakun Hu [77],… đã đư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 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,… và đã tìm ra cách biểu diễn chúng bằng một khái niệm toán học, được gọi là tập mờ. Tuy nhiên, việc mô hình hóa quá trình tư duy lập luận của con người là một vấn đề khó luôn thách thức các nhà nghiên cứu bởi đặc trưng giàu thông tin của ngôn ngữ và cơ chế suy luận không những dựa trên tri thức mà còn là kinh nghiệm, trực quan cảm nhận theo ngữ cảnh của con người.

Cấu trúc thứ tự cảm sinh trên các khái niệm mờ biểu thị bằng các giá trị ngôn ngữ không được thể hiện trên các tập mờ vì hàm thuộc của chúng lại không sánh được với nhau. Hơn thế nữa, việc thiết lập các tập mờ của các giá trị ngôn ngữ một cách cố định dựa theo chủ quan của người thiết lập, trong khi một giá trị ngôn ngữ sẽ mang ngữ nghĩa tương đối khác nhau trong các bài toán khác nhau [2], [7], [8]. 1 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử Nhằm khắc phục phần nào những nhược điểm trên, năm 1990, N. Wechler đã khởi xướng phương pháp tiếp cận đại số đến cấu trúc tự nhiên của miền giá trị của các biến ngôn ngữ [23]-[27].

Theo cách tiếp cận này, mỗi giá trị ngôn ngữ của một biến ngôn ngữ nằm trong một cấu trúc đại số gọi là đại số gia tử (ĐSGT). Dựa trên những tính chất ngữ nghĩa của ngôn ngữ được phát hiện, bằng phương pháp tiên đề hóa nhiều tác giả đã tập trung phát triển lý thuyết ĐSGT với các kết quả như ĐSGT mở rộng, ĐSGT mịn hóa, ĐSGT mở rộng đầy đủ, ĐSGT PN-không thuần nhất. Trên cơ sở đó, đã 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 các lĩnh vực: điều khiển mờ và lập luận mờ [3], [4], [5], cơ sở dữ liệu mờ [1], [63], phân lớp mờ [28], [31],… và đã cho chúng ta nhiều kết quả rất khả quan, có khả năng ứng dụng tốt. Những kết quả này, dù chưa nhiều, nhưng đã cho thấy ý nghĩa cũng như thế mạnh của ĐSGT trong ứng dụng và đây là một hướng nghiên cứu đang được nhiều nhà khoa học quan tâm.

Thêm vào đó, với sự bùng nổ dữ liệu của thời đại thông tin như hiện nay, lượng dữ liệu được tạo ra hàng ngày là rất lớn. Khối lượng thông tin dữ liệu khổng lồ này vượt khỏi giới hạn khả năng ghi nhớ và xử lý của con người. Nhu cầu cần thiết là nghĩ đến các quá trình tự động tìm kiếm các thông tin hữu ích, các quan hệ ràng buộc dữ liệu trong các kho dữ liệu lớn để phát hiện các tri thức, các quy luật hay khuynh hướng dữ liệu hỗ trợ con người phán đoán, nhận xét, ra quyết định. Nhằm đáp ứng các nhu cầu đó, nhiều nhà khoa học đã đề xuất, nghiên cứu và phát triển các phương pháp mới trong khai phá dữ liệu.

Các bài toán được biết đến trong lĩnh vực này như phân lớp và nhận dạng mẫu, hồi quy và dự báo, phân cụm, khai phá luật kết hợp,. với rất nhiều kết quả đã được công bố [6], [10], [11], [32], [36], [38], [49],. Phân lớp dữ liệu là một quá trình quan trọng của khai phá dữ liệu, đó là quá trình chia các đối tượng dữ liệu thành các lớp dựa trên các đặc trưng của tập dữ liệu. Quá trình phân lớp dữ liệu bao gồm việc xây dựng một mô hình dựa trên việc phân tích các mẫu dữ liệu sẵn có và sử dụng mô hình để phân lớp các dữ liệu chưa biết.

Các phương pháp thường được sử dụng trong quá trình học phân lớp như: thống kê, mạng nơron, cây quyết định,… trong đó cây quyết định là một giải pháp hữu hiệu để mô tả quá trình phân lớp dữ liệu. Do cây quyết định 2 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử rất hữu dụng nên đã có nhiều nghiên cứu để xây dựng nó mà nổi bật là các thuật toán học quy nạp như ID3, C45 [41], [67],… CART, SLIQ, SPRINT [14], [52], [74],… Fuzzy ID3 [46], [69], [70],… LDT, LID3 [40], [55], [84], [85],. Trong việc phân lớp dữ liệu bằng cây quyết định, quá trình xây dựng tại mỗi nút của cây, các thuật toán đều tính lượng thông tin và chọn thuộc tính tương ứng có lượng thông tin tối đa làm nút phân tách trên cây. Các thuộc tính này sẽ chia tập mẫu thành các lớp mà mỗi lớp có một phân loại duy nhất hay ít nhất phải có triển vọng đạt được điều này, nhằm để đạt được cây có ít nút nhưng có khả năng dự đoán cao.

Tuy vậy, các cách tiếp cận cho việc huấn luyện cây quyết định hiện nay vẫn còn nhiều vấn đề cần giải quyết: - Breiman L, Friedman J. [60-62], Shou-Hsiung Cheng, Yi Yang và các cộng sự [67], [78] đã dựa vào khái niệm Entropi thông tin để tính lợi ích thông tin và tỷ lệ lợi ích thông tin của các thuộc tính tại thời điểm phân chia các nút. Hướng tiếp cận này cho chúng ta các thuật toán có độ phức tạp thấp nhưng việc phân chia k-phân trên các thuộc tính rời rạc làm cho số nút của cây tăng nhanh, làm tăng chiều rộng của cây, dẫn đến tình trạng quá khớp trên cây kết quả nên ảnh hưởng đến khả năng dự đoán. - Manish Mehta, Jorma Rissanen, Rakesh Agrawal [47], [48], Narasimha Prasad, Mannava Munirathnam Naidu [52], Zhihao Wang, Junfang Wang, Yonghua Huo, Hongze Qiu [87], Haitang Zhang và các cộng sự [32] dựa vào việc tính hệ số Gini và tỷ lệ hệ số Gini của các thuộc tính để lựa chọn điểm phân chia.

Theo hướng tiếp cận này, chúng ta không cần đánh giá mỗi thuộc tính mà chỉ cần tìm điểm chia tách tốt nhất cho mỗi thuộc tính đó. Tuy nhiên, tại mỗi thời điểm chúng ta phải tính một số lượng lớn hệ số Gini cho các giá trị rời rạc nên chi phí về độ phức tạp tính toán cao và cây kết quả mất cân xứng vì phát triển nhanh theo chiều sâu, số nút trên cây lớn. [16], Daveedu Raju Adidela, Jaya Suma. [83] và các cộng sự đã thông qua lý thuyết tập mờ để tính lợi ích thông tin của các thuộc tính mờ cho quá trình phân lớp.

Hướng 3 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử tiếp cận này đã giải quyết được các giá trị mờ trong tập huấn luyện thông qua việc xác định các hàm thuộc, từ đó các bộ giá trị này có thể tham gia vào quá trình huấn luyện. Cách làm này đã giải quyết được hạn chế là bỏ qua các giá trị dữ liệu mờ của cách tiếp phân lớp rõ. Tuy vậy, hiện vẫn còn gặp phải những hạn chế xuất phát từ bản thân nội tại của lý thuyết tập mờ: hàm thuộc của chúng không so sánh được với nhau, xuất hiện sai số lớn tại quá trình xấp xỉ, phụ thuộc vào sự chủ quan, giá trị ngôn ngữ còn thiếu một cơ sở đại số làm nền tảng. - Suzan Kantarci-Savas, Efendi Nasibov [69], Zengchang Qin, Jonathan Lawry, Yongchuan Tang [84], [85] và các cộng sự đã xác định các giá trị ngôn ngữ cho tập dữ liệu mờ và xây dựng cây quyết định ngôn ngữ (Linguistic Decision Tree - LDT) bằng phương pháp LID3.

Với việc xây dựng các nhãn ngôn ngữ cho các giá trị mờ dựa vào xác suất của các nhãn liên kết trong khi vẫn giữ được các giá trị rõ đã biết, hướng tiếp cận này đã làm giảm sai số đáng kể cho quá trình huấn luyện. Tuy vậy, hướng tiếp cận này làm này sẽ làm phát sinh cây đa phân do có sự phân chia lớn theo chiều ngang tại các nút ngôn ngữ khi tập giá trị ngôn ngữ của thuộc tính mờ lớn. Lan [1-5], [27], [28], [29], [30], [31] và các cộng sự đã chỉ ra phương pháp định lượng ngữ nghĩa theo điểm dựa trên ĐSGT, nhằm thuần nhất dữ liệu về các giá trị số hay giá trị ngôn ngữ và cách thức truy vấn dữ liệu trên thuộc tính này. Bài toán xây dựng cây quyết định mờ lúc này có thể sử dụng các thuật toán học theo cách tiếp cận cây quyết định rõ trong một ĐSGT đã xây dựng.

Tuy vậy, hướng tiếp cận này vẫn còn một số vấn đề như: vẫn xuất hiện sai số lớn khi thuần nhất theo điểm mờ, khó đưa ra dự đoán khi có sự đan xen ở điểm phân chia mờ của cây kết quả, phụ thuộc vào miền trị [min, max] từ miền giá trị rõ của thuộc tính mờ. Thêm vào đó, tất cả các thuật toán học phân lớp bằng cây quyết định hiện có đều phụ thuộc lớn vào việc chọn tập mẫu của người huấn luyện. Khi chúng ta chọn tập mẫu không đặc trưng thì cây quyết định được sinh ra sẽ không có khả năng dự đoán. Mà trong thế giới thực, việc lưu trữ dữ liệu tại các kho dữ liệu nghiệp vụ nhằm nhiều mục đích khác nhau.

Nhiều thông tin phục vụ tốt cho việc dự đoán nhưng nhiều thông tin khác chỉ có ý nghĩa lưu trữ thông thường, phục 4 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử vụ cho việc diễn giải thông tin. Các nhóm thuộc tính này làm phức tạp mẫu nên tăng chi phí cho quá trình huấn luyện, quan trọng hơn là chúng gây nhiễu nên cây được xây dựng không có hiệu quả cao.