Tối ưu quá trình học cây quyết định cho bài toán phân lớp theo cách tiếp cận khoảng mờ lớn nhất

Nội dung text: Tối ưu quá trình học cây quyết định cho bài toán phân lớp theo cách tiếp cận khoảng mờ lớn nhất

1. Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông Tối ưu quá trình học cây quyết định cho bài toán phân lớp theo cách tiếp cận khoảng mờ lớn nhất Lê Văn Tường Lân1, Nguyễn Mậu Hân1, Nguyễn Công Hào2 1Khoa Công nghệ Thông tin, Trường Đại học Khoa học, Đại học Huế 2Trung tâm Công nghệ Thông tin, Đại học Huế E-mail: lvtlan@yahoo.com, nmhan2009@gmail.com, nchao@hueuni.edu.vn Tác giả liên hệ: Lê Văn Tường Lân Ngày nhận: 07/07/2017, ngày sửa chữa: 20/09/2017, ngày duyệt đăng: 09/10/2017 Tóm tắt: Hiện nay, khai phá dữ liệu rõ không thể giải quyết tất cả các yêu cầu đặt ra và bài toán phân lớp cây quyết định mờ tất yếu đóng góp một vai trò quan trọng của bài toán khai phá dữ liệu mờ. Tuy vậy, việc học cây quyết định dựa vào định lượng ngữ nghĩa theo điểm vẫn còn một số hạn chế như vẫn xuất hiện nhiều sai số trong quá trình xử lý, cây kết quả thu được không thật sự linh hoạt. Bằng cách thức đối sánh theo khoảng mờ, cây thu được đã giảm thiểu sai số và linh hoạt trong dự đoán tuy nhiên số nút trên cây tăng nhanh nên không đơn giản với người dùng và mất thời gian duyệt cây khi dự đoán. Trong bài báo này, chúng tôi đề xuất khái niệm khoảng mờ lớn nhất để xây dựng phương pháp học quy nạp cây quyết định mờ HAC4.5*, nhằm thu được cây quyết định mờ đạt được tối thiểu về số nút trên cây nhưng có khả năng dự đoán cao. Từ khóa: Khai phá dữ liệu, cây quyết định, cây quyết định mờ, khoảng mờ lớn nhất, HAC4.5*. Title: Fuzzy Decision Tree Learning for Classification based on Maximum Fuzziness Intervals Abstract: Nowadays, data mining based on precise logic cannot satisfy all requirements, so classification based on fuzzy decision trees is important due to the fuzziness nature of data mining. However, decision tree learning based on the quantitative methods of the hedge algebra still has some restrictions because of errors involved and the resulted tree not truly flexible. Using fuzziness interval matching, the resulted tree has reduced the number of errors and increase flexibility in prediction. However, the number of nodes in the resulted tree increases rapidly, causing difficulty to use and more time to produce prediction results. In this paper, a concept of maximum fuzziness interval is proposed in order to build an inductive learning method called “HAC4.5* fuzzy decision tree”, resulting a fuzzy decision tree with the minimum number of nodes and highly accurate prediction. Keywords: Data mining, decision tree, fuzzy decision tree, maximum fuzziness intervals, HAC4.5*. I. ĐẶT VẤN ĐỀ U D. Mỗi dữ liệu ui U thuộc một lớp yi Y tương ⊂ ∈ ∈ ứng tạo thành từng cặp ui, yi V. Giải bài toán phân lớp ( ) ∈ Thế giới thực thì vô hạn trong khi ngôn ngữ của chúng dựa trên mô hình cây quyết định chính là xây dựng một ta lại hữu hạn, vì thế sẽ xuất hiện những cụm từ không cây quyết định để phân lớp, ký hiệu S, là một ánh xạ từ chính xác hoặc mơ hồ. Trong thế giới thực, các kho dữ liệu tập dữ liệu vào tập nhãn: nghiệp vụ được lưu trữ mờ là tất yếu, vì thế bài toán phân lớp cây quyết định rõ không thể giải quyết tất cả các yêu S : D Y. (1) cầu đặt ra và bài toán phân lớp dữ liệu cây quyết định mờ → là vấn đề tất yếu của khai phá dữ liệu [1–12]. Cây quyết định biểu diễn cho tri thức về bài toán, nó Cho một tập các mẫu dữ liệu V = U Y, trong đó U = không chỉ phản ánh đúng với tập dữ liệu mẫu mà còn phải × ui i = 1, , N là tập dữ liệu, Y = y , , yn là tập có khả năng dự đoán và cung cấp giúp cho người dùng { | } { 1 } các nhãn của các lớp, ui D là dữ liệu thứ i với D = phán đoán, ra quyết định đối với đối tượng trong tương lai ∈ A Am là tích Đề-các của các miền của m thuộc tính mà nhãn lớp của nó chưa được xác định từ tập dữ liệu chưa 1 × · · · × tương ứng, n là số lớp và N là số mẫu dữ liệu, để ý rằng biết. Với bài toán phân lớp cây quyết định được nêu ở (1), 42
2. Tập V-2, Số 18 (38), 12/2017 nếu tồn tại một thuộc tính mờ Aj trong số các thuộc tính của D thì ta nói (1) là bài toán phân lớp cây quyết định mờ. Nút phân Như vậy, mô hình cây quyết định S phải đạt các mục Giá trị chia mờ Giá trị tiêu như hiệu quả phân lớp cao, tức là sai số phân lớp cho ngôn ngữ 1 ngôn ngữ k các dữ liệu ít nhất có thể, cây có ít nút nhưng có khả năng dự đoán cao, không xảy ra tình trạng quá khớp. Mục tiêu về hiệu quả phân lớp nhằm đáp ứng tính đúng đắn đối với Hình 1: Điểm phân chia đa phân theo giá trị tập dữ liệu mẫu được cho của bài toán, còn mục tiêu sau Hình 1. Điểm phân chia đa phân theo giá trị ngôn ngữ tại thuộc ngôn ngữ tại thuộc tính mờ được đưa ra với mong muốn mô hình cây quyết định nhận tính mờ. được phải đơn giản và dễ hiểu đối với người dùng. Gọi fh S là hàm đánh giá tính hiệu quả của quá trình ( ) phân lớp, fn S là hàm đánh giá tính đơn giản của cây và Theo cách tiếp cận ĐSGT, chúng ta có thể thuần nhất ( ) dễ hiểu đối với người dùng, mục tiêu của bài toán là các trường mà dữ liệu của nó bao gồm cả dữ liệu rõ và mờ. Các tác giả trong [16–20] đã chỉ ra phương pháp định fh S max và fn S min. (2) ( ) → ( ) → lượng ngữ nghĩa theo điểm nhằm thuần nhất dữ liệu về các Hai mục tiêu ở (2) khó có thể đạt được đồng thời. Khi giá trị số hay giá trị ngôn ngữ và cách thức truy vấn dữ số nút của cây giảm đồng nghĩa với lượng tri thức về bài liệu trên thuộc tính này. Từ đó, chúng ta có thể học phân toán giảm thì nguy cơ phân lớp sai tăng lên, nhưng khi có lớp trên tập mẫu thuần nhất đó. quá nhiều nút cũng có thể gây ra sự quá khớp thông tin Bài toán xây dựng cây quyết định mờ lúc này có thể sử trong quá trình phân lớp. Bên cạnh đó, sự phân chia tại dụng các thuật toán xây dựng cây quyết định rõ như C4.5, mỗi nút ảnh hưởng đến tính phổ quát hay cá thể tại nút đó. SLIQ, v.v. [7, 8, 10, 12]. Các nút phân chia nhị phân được Nếu sự phân chia tại một nút là nhỏ sẽ làm tăng tính phổ tính theo dựa theo điểm phân chia với các giá trị ngôn ngữ quát và ngược lại nếu sự phân chia lớn sẽ làm tăng tính cá đã có thứ tự và hoàn toàn xác định tương ứng với một giá thể của nút đó. Tính phổ quát của nút trên cây sẽ làm tăng trị số trong ĐSGT đã xây dựng. khả năng dự đoán nhưng nguy cơ gây sai số lớn, trong khi Tuy vậy, cách thuần nhất dựa trên phương pháp định tính cá thể giảm khả năng dự đoán nhưng lại tăng tính đúng lượng ngữ nghĩa theo điểm này vẫn xuất hiện nhiều sai số đắn nhưng nó cũng là nguyên nhân của tình trạng quá khớp vì một đoạn con các giá trị rõ đã có sẽ được quy về một trên cây. Các phương pháp giải quyết bài toán mô hình cây điểm tức là một giá trị ngôn ngữ tương ứng, điều này cũng quyết định đều phải thỏa hiệp giữa các mục tiêu này để đạt làm xuất hiện các giá trị gần nhau có thể được phân hoạch được kết quả cuối cùng. ở hai đoạn con khác nhau nên kết quả phân lớp khác nhau. Hiện có một số cách tiếp cận như sau. Trước hết là cách Bên cạnh đó, cây kết quả cũng khó đưa ra dự đoán trong tiếp cận giá trị ngôn ngữ cho tập mờ để xây dựng cây quyết các trường hợp cần dự đoán mà tại đó có sự đan xen ở định mờ. Các tác giả trong [13–15] đã xác định các giá trị điểm phân chia mờ, ví dụ ta cần dự đoán cho trường hợp ngôn ngữ cho tập dữ liệu mờ và xây dựng cây quyết định đoạn con x1, x2 , với x1 < x < x2 tại nút phân chia mờ ở ngôn ngữ (LDT: Linguistic Decision Tree) bằng cách sử [ ] Hình 2. dụng tư tưởng của thuật toán ID3 của cây quyết định rõ cho các nút ứng với các thuộc tính ngôn ngữ (LID3). Cách tiếp cận thứ ba là bằng cách thức đối sánh theo Tuy nhiên, cách làm này sẽ làm phát sinh cây đa phân, có khoảng mờ dựa trên ĐSGT, cây kết quả thu được đã giảm sự phân chia theo chiều ngang lớn tại các nút ngôn ngữ khi thiểu sai số và linh hoạt nhờ chúng ta vẫn giữ nguyên miền tập giá trị ngôn ngữ của thuộc tính mờ lớn (Hình 1), nên giá trị rõ trong khi vẫn đối sánh được với các giá trị mờ dễ dẫn đến tình trạng quá khớp. Thêm vào đó, tại nút này, trong tập mẫu cho quá trình huấn luyện [20], như Hình 3. ta không thể sử dụng cách phân chia nhị phân của thuật Tuy vậy, số nút trên cây kết quả có khả năng tăng cao nên toán C4.5 vì không có thứ tự giữa các giá trị ngôn ngữ. không đơn giản với người dùng và mất thời gian duyệt cây Hơn nữa, với các giá trị rõ trong miền thuộc tính mờ của khi dự đoán. Do vậy, hàm mục tiêu đã nêu ở (2) có thể tập dữ liệu huấn luyện, một đoạn con các giá trị rõ sẽ được không đạt được. ánh xạ bằng một giá trị ngôn ngữ nên có sự sai lệch lớn. Trong bài báo này, chúng tôi đề xuất một phương pháp Cách tiếp cận mờ thứ hai là theo đại số gia tử (ĐSGT) học cây quyết định mờ khi tập mẫu huấn luyện không thuần do N. C. Ho và W. Wechler khởi xướng từ 1990. Cách này nhất giá trị dựa trên khái niệm khoảng mờ lớn nhất, trong có nhiều ưu điểm vì theo cách tiếp cận này, mỗi giá trị khi giữ nguyên các ưu điểm của phương pháp đối sánh theo ngôn ngữ của một biến ngôn ngữ nằm trong một cấu trúc khoảng mờ nhưng tối ưu về số nút trên cây kết quả, nhằm đại số nên ta có thể đối sánh giữa các giá trị ngôn ngữ. thu được cây quyết định có đơn giản và hiệu quả. 43
3. Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông Nút phân Giá trị ngôn ngữ chia mờ ≥ Giá trị số x tại h 2 > > h p và h1 b1 tức Ib2 > Ib1 , If m c− và If m c là các khoảng con và tạo thành một ( ) ( ) + ii) Nếu Ib2 = Ib1 tức b2 = b1 thì Ia2 > Ia1 tức a2 > a1, phân hoạch của 0, 1 , thỏa If m c− If m c . Tức là [ ] ( ) ≤ + ( ) với mọi u If m c và mọi v If m c : u v. Điều và lúc này ta nói dãy a1, b1 , a2, b2 là dãy có 2 khoảng ∈ ( −) ∈ ( ) ≤ [ ] [ ] này hoàn toàn phù hợp với thứ tự ngữ nghĩa của c− có quan hệ thứ tự trước sau. c+ và . Định lý 1. Cho k khoảng khác nhau từng đôi một a , b , [ 1 1] Ký hiệu độ dài của If m x là If m x , ta có If m c− = a , b ,. . . , a , b , ta luôn sắp xếp để được một dãy có k + ( ) + ( ) ( ) 2 2 k k If m c và If m c = If m c ; [ ] [ ] ( −) ( ) ( ) khoảng với quan hệ thứ tự trước sau. ii) Giả sử với mọi x X có độ dài bằng k (l x = k), ∈ ( ) có khoảng mờ là If m x và If m x = f m x . Các Thật vậy, với k khoảng khác nhau từng đôi một a , b , ( ) ( ) ( ) [ 1 1] khoảng mờ của y = hi x, với mọi i p, p + a , b ,. . . , ak, bk , ta luôn tìm được khoảng trước nhất ∈ [− − [ 2 2] [ ] 1, , 1, 1, 2, , q , lúc này l y = k + 1, là tập của dãy là ai, bi , với ai = min a , a , , an . Nếu có − ] ( ) [ ] ( 1 2 ) If m hi x thoả mãn một phân hoạch của If m x , nhiều khoảng aj, bj , i = 1 k mà aj = ai thì chọn ta { ( )} ( ) [ ] If m hi x = If m hi x và có thứ tự tuyến tính tương khoảng ai, bi là khoảng có bi bé nhất trong các giá trị bj . ( ) ( ) [ ] ứng với thứ tự của tập h p x, h p+1 x, , hq x . Việc chọn bi luôn tìm được duy nhất vì các khoảng đã cho { − − } Khi l x = k, ta ký hiệu I x thay cho If m x , Xk = khác nhau từng đôi một nên nếu ai = aj thì bi , bj (Định ( ) ( ) ( ) x X l x = k là tập các phần tử trong X có độ nghĩa 2). {∀ ∈ | ( ) } 44
4. Tập V-2, Số 18 (38), 12/2017 Sau khi tìm được khoảng trước nhất của dãy là ai, bi , trong đó k = len x , l = len y và m = len z với z = [ ] ( ) ( ) ( ) ta tiếp tục tìm khoảng thứ 2 và cứ thế tiếp tục. Sau k lần x, y . ∼max( ) tìm và sắp xếp ta có được dãy gồm k khoảng mà các phần Mệnh đề 2. Cho một ĐSGT X = X, G, H, , với mọi tử của dãy đã được sắp xếp theo quan hệ thứ tự trước sau. ( ≤) x, y X, ta có các tính chất về mức độ gần nhau của các ∈ hạng từ như sau: 2. Khoảng mờ lớn nhất và phương pháp tính khoảng i) Hàm sim x, y có tính chất đối xứng, tức là sim x, y = mờ lớn nhất ( ) ( ) sim y, x ; ( ) Trong ĐSGT, một hạng từ có thể mang ngữ nghĩa của ii) x, y không có quan hệ kế thừa ngữ nghĩa khi và chỉ một hạng từ khác tức hạng từ được dùng để sinh ra nó. khi sim x, y = 0; ( ) Chẳng hạn “very old” mang ngữ nghĩa của “old”, “very iii) sim x, y = 1 x = y; ( ) ⇔ little old” cũng mang ngữ nghĩa của “old”. Vậy, hai hạng iv) x, y, z Xk , x y z sim x, z sim x, y và ∈ ≤ ≤ ⇒ ( ) ≤ ( ) từ “very old” và “very little old” đều có quan hệ kế thừa ∀sim x, z sim y, z . ngữ nghĩa (hay quan hệ kế thừa) của “old”, ta gọi “very ( ) ≤ ( ) old” và “very little old” có quan hệ kế thừa ngữ nghĩa. Định nghĩa 4. Một ĐSGT X = X, G, H, , với mọi x, y Chứng minh. i) Hiển nhiên theo định nghĩa. ( ≤) ∈ X, được gọi là có quan hệ kế thừa ngữ nghĩa với nhau ii) Theo định nghĩa, ta có m = 0 khi và chỉ khi x, y và được ký hiệu x, y nếu tồn tại z X sao cho x = y ∼( ) ∈ không có quan hệ kế thừa ngữ nghĩa. Vậy nếu x và hi hi z = hj hj z. n ··· 1 m ··· 1 không có quan hệ kế thừa ngữ nghĩa thì m = 0 suy ra sim x, y = 0. Ngược lại, khi sim x, y = 0 thì m = 0 hoặc Mệnh đề 1. Với mọi x, y X xác định hai khoảng mờ mức ( ) ( ) ∈ 1 v x v y = 0. Khi m = 0 tức x, y không có quan k và mức l lần lượt là Ik x và Il y , chúng hoặc không ( − | ( ) − ( )|) ( ) ( ) hệ kế thừa ngữ nghĩa. Trường hợp 1 v x v y = 0 có quan hệ kế thừa, hoặc có quan hệ kế thừa với nhau nếu ( − | ( ) − ( )|) thì v x v y = 1 suy ra x = 0, y = 1 hoặc x = 1, y = 0 tồn tại z X, z = v, v min l, k , IL z IL y , IR z | ( ) − ( )| ∈ | | ≤ ( ) ( ) ≤ ( ) ( ) ≥ nên x, y không có quan hệ kế thừa ngữ nghĩa. IR y , và IL z IL x , IR z IR x hay Iv z Ik x ( ) ( ) ≤ ( ) ( ) ≥ ( ) ( ) ⊇ ( ) và Iv z Il y , tức là x, y được sinh ra từ z. iii) Do m max k, l và 0 v x , v y 1 nên: ( ) ⊇ ( ) ≤ ( ) ≤ ( ) ( ) ≤ sim x, y = 1 m = max k, l và v x v y = 0 ( ) ⇔ ( ) | ( ) − ( )| Chứng minh. Mệnh đề này dễ dàng suy ra từ tính phân x = y. hoạch các khoảng mờ. ⇔ iv) Theo giả thiết x y z v x v y v z Khi x và y có quan hệ kế thừa ngữ nghĩa, ta nói rằng ≤ ≤ ⇒ ( ) ≤ ( ) ≤ ( ) 1 v x v z 1 v x v y và 1 v x v z khoảng tính mờ Iv z bao hàm hai khoảng tính mờ Ik x ⇒ − | ( ) − ( )| ≤ − | ( ) − ( )| − | ( ) − ( )| ≤ ( ) ( ) 1 v y v z . Mặt khác, cũng theo giả thiết x, y, z Xk và Il y , hay z bao hàm ngữ nghĩa của x và y và ta ký − | ( ) − ( )| ∈ ( ) len x = len y = len z = k. Vậy đặt w = x, y , hiệu z = x, y . Theo định nghĩa, rõ ràng hai hạng từ x, y ⇒ ( ) ( ) ( ) 1 ∼max( ) ∼( ) w2 = max y, z , w3 = max x, z , theo qui tắc sinh các có quan hệ ngữ nghĩa nếu chúng có dạng x = hin hi1 z, ∼ ( ) ∼ ( ) ··· hạng từ của ĐSGT với giả thiết x y z nên len w1 y = hj hj z. Nếu hi = hj = h , hi = hj = h . . . thì ta ≤ ≤ ( ) ≥ m ··· 1 1 1 10 2 2 20 len w và len w len w . Vậy theo Định nghĩa 6 ta có có z = h c hoặc z = h h c đều bao hàm ngữ nghĩa của x ( 3) ( 2) ≥ ( 3) 10 10 20 sim x, y sim x, z và sim y, z sim x, z .  và y. Tuy nhiên, thực tế sử dụng z thay thế cho cả x và y ( ) ≤ ( ) ( ) ≤ ( ) có thể làm mất ngữ nghĩa của chúng và rõ ràng, trên thực Định nghĩa 7 (Tính kề nhau của các khoảng mờ). Cho một tế chúng ta cần phải xác định z sao cho ngữ nghĩa càng ĐSGT X = X, G, H, , hai khoảng tính mờ I x và I y ( ≤) ( ) ( ) gần với x, y càng tốt.  được gọi là kề nhau nếu chúng có một điểm mút chung, tức là IL x = IR y hoặc IR x = IL y . Định nghĩa 5. Cho một ĐSGT X = X, G, H, , với x, ( ) ( ) ( ) ( ) ( ≤) y, z X, z = x, y . Nếu z1 X, z1 = x, y và ∈ ∼( ) ∃ ∈ ∼( ) Giả sử IR x = IL y ta có khoảng mờ I x nằm kề trái len z len z thì ta nói z có ngữ nghĩa gần với x, y ( ) ( ) ( ) ( ) ≥ ( 1) của khoảng mờ I y và theo Định nghĩa 3, ta có I x < I y . nhất, hay khoảng mờ z có độ dài lớn nhất và được ký hiệu ( ) ( ) ( ) z = max x, y . Như vậy với hai khoảng mờ x và y, ta có thể sử dụng ∼ ( ) khoảng mờ z đại diện mà không làm mất nhiều ngữ nghĩa Định nghĩa 6. Cho một ĐSGT X = X, G, H, , với x, ( ≤) ∀ của x và y bằng cách dựa vào hàm sim x, y và việc sử y X và x, y . Mức độ gần nhau của x và y theo quan ( ) ∈ ∼( ) dụng z thay thế cho x và y được xem như phép kết nhập hệ kế thừa ngữ nghĩa, ký hiệu là sim x, y , được định nghĩa ( ) khoảng mờ x, y thành khoảng mờ z. như sau: m Để tìm khoảng mờ lớn nhất của hai khoảng mờ cho trước, sim x, y = 1 v x v y , ( ) max k, l ( − | ( ) − ( )|) chúng ta sử dụng Thuật toán 1. ( ) 45
5. Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông Thuật toán 1: Thuật toán tính khoảng mờ lớn nhất của hai Như vậy, thuộc tính mờ A của tập huấn luyện sau khi đã khoảng mờ cho trước phân hoạch theo khoảng mờ theo khoảng mờ lớn nhất có Input: k khoảng khác nhau và đã được sắp xếp theo thứ tự trước ĐSGT X = X, G, H, và x, y X sau là: Ia , Ib 0 do 1) Tính lợi ích thông tin cho các khoảng mờ tại thuộc begin tính mờ: if z X, z = v and Ik x Iv z Do thuộc tính mờ của tập huấn luyện đã được đã được ∃ ∈ | | ( ) ⊆ ( ) and Il y Iv z then phân hoạch theo khoảng mờ là một đoạn con của 0, 1 ( ) ⊆ ( ) [ ] return Iv z và miền dữ liệu của nó là một tập được sắp xếp thứ tự ( ) else tuyến tính theo quan hệ trước sau. Ta có thể so sánh để v = v 1; phân ngưỡng cho tập giá trị này tại một khoảng bất kỳ − end if I x = Ia, Ib 0, 1 được chọn, tương tự như các giá trị ( ) [ ] ⊆ [ ] end số liên tục trong C4.5. end while Việc tìm ngưỡng để cho phép tách cũng dựa theo tỷ lệ return NULL; lợi ích thông tin của các ngưỡng trong tập D tại nút đó. Tỷ lệ lợi ích thông tin của các ngưỡng đối với thuộc tính A là thuộc tính số trong tập D tại nút đó. III. THUẬT TOÁN HAC4.5* SỬ DỤNG KHÁI NIỆM Giả sử thuộc tính A là thuộc tính mờ đã phân hoạch theo KHOẢNG MỜ LỚN NHẤT TRONG QUÁ TRÌNH khoảng mờ và có k khoảng khác nhau đã được sắp xếp theo HUẤN LUYỆN CÂY QUYẾT ĐỊNH thứ tự trước sau là: Ia1, Ib1 Thi . ra trường hợp đó là các khoảng mờ khác nhau nhưng lại {∀ [ ] [ ] } có chung kết quả dự đoán, điều này làm cho mô hình Lúc này ta có cây thu được có nhiều nút và khi chúng ta sử dụng mức D GainHA D, ThHA = Entropy D | 1| Entropy D k có giá trị càng lớn, để tăng tính chính xác, thì vấn i ( ) − D × ( 1) đề này càng có khả năng xảy ra. Hơn nữa, tại ngưỡng   | | D2 HA = , | | Entropy D2 , được chọn Thi Iai Ibi , việc chia tập huấn luyện D − D × ( ) [ ] HA | | thành các tập: D1 = Iaj , Ibj Iaj , Ibj Th không phải lúc nào D1 D1 ∀ [ ] [  ] i } SplitInfoHA D, ThHA = | | log | | cũng là lựa chọn tốt nhất vì có thể thể xảy ra trường hợp i − D × 2 D    | | | | một đoạn con của D1 hoặc D2 mới có lợi ích thông tin D D | 2| log | 2|, lớn nhất. − D × 2 D | | | | Do thuộc tính mờ A của tập huấn luyện đã được đã được HA HA Gain D, Thi phân hoạch theo khoảng mờ là một đoạn con của 0, 1 và HA HA [ ] GainRatio D, Thi = . miền dữ liệu của nó là một tập được sắp xếp thứ tự tuyến HA HA SplitInfo D, Thi tính theo quan hệ trước sau nên các khoảng mờ của chúng     có tính kề trái và kề phải. Như vậy với hai khoảng mờ x Trên cơ sở tính toán tỷ lệ lợi ích thông tin cho các ngưỡng, và y nếu chúng có chung lớp dự đoán, ta có thể sử dụng ngưỡng nào có tỷ lệ lợi ích thông tin lớn nhất thì được chọn khoảng mờ z = x, y thay thế mà không làm thay đổi để phân tách tập huấn luyện D. ∼max( ) ngữ nghĩa của x và y trong quá trình học phân lớp. Việc sử 2) Thuật toán đề xuất: dụng phép kết nhập z thay thế cho x và y được thực hiện Trong mục này, chúng tôi đề xuất thuật toán, gọi là cho tất cả các khoảng mờ của thuộc tính mờ A. HAC4.5*, chi tiết trong Thuật toán 2. 46
6. Tập V-2, Số 18 (38), 12/2017 Thuật toán 2: Thuật toán HAC4.5* S1.Thuộc tính = L.Thuộc tính - X; S = Ix Ix L, Ix > T ; Input: Tập mẫu huấn luyện D. 2 { i i ⊆ i } S .Nút cha = L; Output: Cây quyết định mờ S. 2 Method: S2.Thuộc tính = L.Thuộc tính - X; S = S + S + S L; //Đánh dấu nút L đã for each (thuộc tính mờ X của D) 1 2 − begin xét và bổ sung thêm các nút con của L ứng với các tập S và S Xây dựng ĐSGT Xk tương ứng thuộc tính mờ X; 1 2 Chuyển các giá trị số và giá trị ngôn ngữ của X về end các giá trị đoạn 0, 1 ; end if ⊆ [ ] end else if (L là thuộc tính liên tục) then Khởi tạo tập các nút lá S; S = D; begin HA for each (nút lá L thuộc S) T = Ngưỡng có GainRatio lớn nhất; S = xi xi L, xi T ; if (L thuần nhất) or (L.Tập thuộc tính là rỗng) then 1 { | ∈ ≤ } L.Nhãn = Tên lớp S1.Nút cha = L; else S1.Thuộc tính = L.Thuộc tính - X; S = xi xi L, xi > T ; begin 2 { | ∈ } if (L là thuộc tính mờ) then S2.Nút cha = L; begin S2.Thuộc tính = L.Thuộc tính - X; S = S + S + S L; //Đánh dấu nút L đã xét và for each (khoảng mờ x của thuộc tính L) 1 2 − for each (khoảng mờ y của thuộc tính L bổ sung thêm 2 nút con của L ứng với tập S1 và S2 mà y , x) end //Gọi thuật toán 1 else //L là thuộc tính rời Tìm và thay thế x bởi z = x, y begin ∼max( ) P = xi xi K, xi đơn nhất ; end { | ∈ } for each (xi P) end if ∈ X = Thuộc tính tương ứng có GainRatio hay begin HA Si = xj xj L, xj = xi GainRatio lớn nhất; { ∈ } S .Nút cha = L; L.Nhãn = Tên thuộc tính X; i if (L là thuộc tính mờ) then Si.Thuộc tính = L.Thuộc tính - X; begin S = S + Si; //Đánh dấu nút L đã xét và bổ T = Ngưỡng có GainRatioHA lớn nhất; sung tất cả các nút con của L ứng với tập Si Gán nhãn T của thuộc tính X cho cây S; end S = Ix Ix L, Ix < T ; S = S L; 1 { i i ⊆ i } − S .Nút cha = L; end 1 end 3. Đánh giá thuật toán ta tìm được một thuộc tính phù hợp để tạo cây thì tại các điểm phân chia này, tập mẫu huấn luyện tương ứng trên Như vậy, bằng việc tìm các khoảng mờ lớn nhất cho mọi mỗi nhánh của cây thay đổi nên các khoảng mờ của thuộc khoảng mờ trong tập huấn luyện và xác nhập chúng, thuật tính mờ thay đổi. toán HAC4.5* đã làm giảm thiểu số lượng khoảng mờ tham Với m là số thuộc tính, n là số thể hiện của tập huấn gia trong quá trình học xây dựng cây nên làm giảm số nút luyện, độ phức tạp của C4.5 là O m n log n ; Với ( × × ) trên cây kết quả. Tuy vậy, do sự kết nhập các khoảng mờ HAC4.5*, trước tiên ta mất O n2 cho mỗi một thuộc tính ( ) dựa trên độ đo về tính tương tự của các khoảng mờ đó đối mờ để tính các phân hoạch đoạn mờ. Sau đó, độ phức với thuộc tính huấn luyện nên nó không sai lệch đến kết tạp của thuật toán tại mỗi bước lặp theo thuộc tính mi là quả phân lớp cuối cùng. O n log n nếu mi không phải là thuộc tính mờ và là ( × ) Trong mỗi bước lặp của thuật toán, chúng ta đều phải O n n log n nếu là thuộc tính mờ do phải mất thêm ( × × ) tính các khoảng mờ lớn nhất và thực hiện sát nhập các O n để tìm ngưỡng cho các khoảng mờ đối với thuộc tính ( ) khoảng mờ với chi phí là O n2 . Để ý rằng trong thuật này và O n2 để tìm khoảng mờ lớn nhất cho mỗi khoảng ( ) ( ) toán trên, chúng ta không thể chuyển việc tìm và sát nhập mờ trong tập huấn luyện. Tuy vậy, việc tìm khoảng mờ lớn các khoảng mờ lớn nhất ra khỏi vòng lặp. Do khi chúng nhất và xác định ngưỡng cho các khoảng mờ là tuần tự nên 47
7. Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông độ phứt tạp của HAC4.5* là O m n3 log n . 2. Kết quả trên dữ liệu dự đoán thu nhập trên dữ ( × × ) Tính đúng và tính dừng của thuật toán được rút ra từ liệu Bank tính đúng của C4.5 và cách thức đối sánh giữa các giá trị khoảng mờ. Bộ dữ liệu Bank có hơn 45.000 mẫu tin gồm 17 thuộc tính bao gồm dữ liệu rời rạc, liên tục, logic và mờ, trong đó IV. THỰC NGHIỆM VÀ SO SÁNH thuộc tính Age (Tuổi) chứa cả dữ liệu rõ và mờ. Chúng tôi tách riêng biệt 30.000 mẫu tin cho tập huấn luyện và dùng Chương trình thực nghiệm được cài đặt bằng ngôn ngữ 15.000 mẫu còn lại để chọn ngẫu nhiên 5.000 mẫu dùng Java (Eclipse Mars Release (4.5.0) trên máy tính có cấu cho việc kiểm tra. Kết quả được thể hiện trong Bảng III và ® TM hình: Intel Core i5-2450, 4 CPU với mỗi CPU có tốc Bảng IV. độc xử lý là 2, 5 GHz, RAM có 4 GB, hệ thống 64 bit, cho đồng thời cả ba thuật toán: C4.5, HAC4.5 và HAC4.5* trên đồng thời hai bộ dữ liệu là Adult và Bank. Bảng IV TỶ LỆ KIỂM TRA TRÊN DỮ LIỆU BANK 1. Kết quả trên dữ liệu dự đoán thu nhập Adult Số mẫu kiểm tra Bộ dữ liệu Adult có hơn 40.000 mẫu tin gồm 14 thuộc Thuật toán tính bao gồm dữ liệu rời rạc, liên tục, logic và mờ, trong 1000 2000 3000 4000 5000 đó có 2 thuộc tính Age (Tuổi) và HoursPerWeek (Số giờ C4.5 61,3% 58,1% 58,3% 61,2% 64,7% làm việc) chứa cả dữ liệu rõ và mờ. Chúng tôi tách riêng HAC4.5 76,6% 72,6% 72,9% 76,5% 80,9% biệt 20.000 mẫu tin cho tập huấn luyện và dùng 20.000 mẫu còn lại để chọn ngẫu nhiên 5.000 mẫu dùng cho việc HAC4.5* 85,2% 83,5% 83,2% 82,1% 81,1% kiểm tra. Kết quả cụ thể như Bảng I và Bảng II. Thời gian (s) Bảng I 3000 ĐỐI SÁNH HUẤN LUYỆN TRÊN DỮ LIỆU ADULT 2500 2000 Thuật toán Thời gian huấn luyện (s) Tổng số nút trên cây 1500 C4.5 479,8 682 1000 HAC4.5 1863,7 1873 500 0 HAC4.5* 2610,8 1624 C4.5 HAC4.5 HAC4.5* Bảng II TỶ LỆ KIỂM TRA TRÊN DỮ LIỆU ADULT Hình 4. Đối sánh thời gian huấn luyện và số nút của cây kết quả trên dữ liệu Adult. Số mẫu kiểm tra Thuật toán 1000 2000 3000 4000 5000 98.0% C4.5 84,5% 85,7% 85,9% 86,2% 85,7% 96.0% 94.0% HAC4.5 92,3% 91,5% 93,0% 95,0% 96,1% úng 92.0% đ 90.0% HAC4.5* 92,8% 91,6% 93,2% 95,1% 96,3% án o đ 88.0% C4.5 ự 86.0% d ệ HAC4.5 l 84.0% Bảng III ỷ T HAC4.5* ĐỐI SÁNH HUẤN LUYỆN TRÊN DỮ LIỆU BANK 82.0% 80.0% 78.0% Thuật toán Thời gian huấn luyện (s) Tổng số nút trên cây 1000 2000 3000 4000 5000 C4.5 2243 562 Số lượng mẫu HAC4.5 4587,2 1061 Hình 5. Đối sánh tỷ lệ kiểm tra từ 1.000 đến 5.000 trên mẫu trên HAC4.5* 6610,5 892 dữ liệu Bank. 48
8. Tập V-2, Số 18 (38), 12/2017 dự đoán không cao. Thứ đến, HAC4.5 xây dựng một ĐSGT Thời gian (s) tại các trường mờ và dùng nó để thuần nhất tập mẫu nên 7000 chúng ta đã xử lý được các giá trị mờ mà vẫn giữ nguyên 6000 các giá trị rõ nên không làm xuất hiện thêm sai số trong 5000 quá trình phân hoạch,vì thế kết quả trong các quá trình dự 4000 đoán tốt hơn nhiều so với C4.5. Tuy vậy, so với C4.5 thì 3000 cây kết quả thu được không giản đơn vì có nhiều nút. Cuối 2000 cùng, HAC4.5* cho kết quả tốt nhất vì trong quá trình huấn 1000 0 luyện cây, chúng ta đã tìm được các điểm phân hoạch tốt C4.5 HAC4.5 HAC4.5* nhất tại các thuộc tính mờ nên ít cây kết quả thu được có sai số ít hơn. Hơn nữa, việc tìm các khoảng mờ lớn nhất và kết nhập các giá trị mờ trên thuộc tính mờ đã làm cho Hình 6. Đối sánh thời gian huấn luyện và số nút của cây kết quả lực lượng của các thuộc tính mờ tương ứng giảm, vì thế số trên dữ liệu Bank. nút trên cây thu được cũng giảm nên cây kết quả thu được là tốt nhất. 90.0% 80.0% 70.0% V. KẾT LUẬN úng 60.0% đ 50.0% án Bài toán phân lớp cây quyết định mờ đóng vai trò quan o đ 40.0% C4.5 ự trọng trong quá trình khai phá dữ liệu. Tuy vậy, việc phân d 30.0% ệ HAC4.5 l 20.0% lớp bằng cây quyết định mờ dựa trên lý thuyết tập mờ luôn ỷ T HAC4.5* 10.0% gặp phải những hạn chế do xuất phát từ bản thân nội tại 0.0% của lý thuyết tập mờ. ĐSGT với lợi thế của mình đã trở 1000 2000 3000 4000 5000 thành một công cụ thật sự hữu ích để giải quyết bài toán Số lượng mẫu phân lớp cây quyết định. Bằng việc nhận ra các hạn chế của phương pháp định Hình 7. Đối sánh tỷ lệ kiểm tra từ 1.000 đến 5.000 trên mẫu trên lượng ngữ nghĩa theo điểm của việc sử dụng ĐSGT trong dữ liệu Bank. quá trình huấn luyện, cách thức đối sánh theo khoảng mờ là một giải pháp nhằm giảm thiểu sai số cho việc học cây quyết định mờ. Bằng việc đưa ra khái niệm khoảng mờ lớn 3. Đánh giá kết quả thực nghiệm nhất, bài báo đã đề xuất một phương pháp học quy nạp cây Việc đồng thời cài đặt cả ba thuật toán C4.5, HAC4.5 quyết định mờ HAC4.5*, nhằm thu được cây quyết định và HAC4.5*, kết quả đánh giá trên cùng các bộ dữ liệu mờ đơn giản và hiệu quả cho bài toán phân lớp mờ. là Adult và Bank đã cho phép chúng ta có các đánh giá sau. Về chi phí huấn luyện, kết quả ở Hình 4 và Hình 6 TÀI LIỆU THAM KHẢO cho chúng ta thấy rằng, thuật toán C4.5 luôn cho thời gian nhanh nhất trong tất cả các bộ mẫu kể cả trong quá trình [1] A. Bikas, E. Voumvoulakis, and N. Hatziargyriou, “Neuro- fuzzy decision trees for dynamic security control of power huấn luyện hay kiểm tra, vì nó bỏ qua các giá trị mờ trong systems,” in 15th International Conference on Intelligent tập mẫu nên không mất thời gian xử lý. HAC4.5 phải trải System Applications to Power Systems (ISAP’09). IEEE, qua quá trình xây dựng các ĐSGT cho các trường mờ và 2009, pp. 1–6. [2] G. G. Anuradha, “Fuzzy decision tree construction in crisp chi phí để chuyển đổi các giá trị về đoạn 0, 1 ban đầu và [ ] scenario through fuzzified trapezoidal membership func- tại mỗi bước cần thêm thời gian để chọn đoạn phân chia tion,” Internetworking Indonesia, vol. 7, no. 2, pp. 21–28, nên tốn nhiều thời gian hơn nhiều so với C4.5. HAC4.5* 2015. [3] B. Chandra and P. P. Varghese, “Fuzzy SLIQ decision vì mỗi bước lặp cần thêm thời gian để tìm các khoảng mờ tree algorithm,” IEEE Transactions on Systems, Man, and lớn nhất cho miền trị mờ của thuộc tính mờ tương ứng nên Cybernetics, Part B (Cybernetics), vol. 38, no. 5, pp. 1294– HAC4.5* chậm nhất so với các thuật toán khác. 1301, 2008. [4] H. Ishibuchi and T. Nakashima, “Effect of rule weights in Về dự đoán, kết quả ở Hình 5 và Hình 7 cho chúng ta fuzzy rule-based classification systems,” IEEE Transactions thấy rằng, trước hết C4.5 bỏ qua các giá trị mờ trong tập on Fuzzy Systems, vol. 9, no. 4, pp. 506–515, 2001. mẫu, chỉ quan tâm các giá trị rõ nên cây kết quả thu được [5] K. K. R. C and V. Babu, “A survey on issues of decision tree and non-decision tree algorithms,” International Journal of khá giản đơn vì ít nút. Tuy nhiên, do việc bỏ qua các giá trị Artificial Intelligence and Applications for Smart Devices, mờ nên làm mất dữ liệu tại các trường mờ, vì thế kết quả vol. 4, no. 1, pp. 9–32, 2016. 49
9. Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông [6] S. Moustakidis, G. Mallinis, N. Koutsias, J. B. Theocharis, [20] L. V. T. Lân, N. M. Hân, and N. C. Hào, “An algorithm and V. Petridis, “SVM-based fuzzy decision trees for clas- to building a fuzzy decision tree for data classification sification of high spatial resolution remote sensing images,” problem based on the fuzziness intervals matching,” Journal IEEE Transactions on Geoscience and Remote Sensing, of Computer Science and Cybernetics, vol. 32, no. 4, pp. vol. 50, no. 1, pp. 149–169, 2012. 367–380, 2017. [7] M. Mehta, R. Agrawal, and J. Rissanen, “SLIQ: A fast scalable classifier for data mining,” Advances in Database Technology-EDBT’96, pp. 18–32, 1996. [8] J. Shafer, R. Agrawal, and M. Mehta, “SPRINT: A Fast Scalable Classifier for Data Mining,” IBM Almaden Reseach Lê Văn Tường Lân sinh năm 1974 tại Center, 1996. [9] P. Fatima, D. Parveen, and M. Sathik, “Fuzzy decision tree thành phố Huế. Ông nhận bằng Thạc sĩ, based effective imine indexing,” International Journal of chuyên ngành Công nghệ Thông tin tại Computer Technology and Electronics Engineering, vol. 1, Trường Đại học Bách khoa Hà Nội, năm 2011. 2002. Hiện nay, ông đang là giảng viên [10] J. R. Quinlan, “Simplifying decision trees,” International và là nghiên cứu sinh tại Khoa Công nghệ Journal of Man-Machine Studies, vol. 27, no. 3, pp. 221– Thông tin, Trường Đại học Khoa học, Đại 234, 1987. [11] R. H. Tajiri, E. Z. Marques, B. B. Zarpelão, and học Huế, chuyên ngành Khoa học Máy tính. L. de Souza Mendes, “A new approach for fuzzy classifi- Lĩnh vực nghiên cứu của ông là khai phá dữ liệu và công nghệ cation in relational databases,” in International Conference phần mềm. on Database and Expert Systems Applications. Springer, 2011, pp. 511–518. [12] S. Ruggieri, “Efficient C4.5,” 2000. [13] Z. Qin and Y. Tang, “Linguistic decision trees for classifica- Nguyễn Mậu Hân sinh năm 1957 tại Thừa tion,” in Uncertainty Modeling for Data Mining. Springer, Thiên Huế. Ông nhận bằng Tiến sĩ tại 2014, pp. 77–119. Viện Công nghệ Thông tin Hà Nội và được [14] J. Zhang and V. Honavar, “Learning decision tree classifiers from attribute value taxonomies and partially specified data,” phong hàm Phó Giáo sư năm 2013. Hiện in Proceedings of the International Conference on Machine nay, ông là giảng viên tại Khoa Công nghệ Learning, Washington DC, 2003. Thông tin, Trường Đại học Khoa học, Đại [15] M. Zeinalkhani and M. Eftekhari, “Comparing different học Huế. Lĩnh vực nghiên cứu của ông là stopping criteria for fuzzy decision tree induction through xử lý song song và phân tán, tính toán lưới IDFID3,” Iranian Journal of Fuzzy Systems, vol. 11, no. 1, pp. 27–48, 2014. và điện toán đám mây. [16] N. C. Ho and N. Van Long, “Fuzziness measure on complete hedge algebras and quantifying semantics of terms in linear hedge algebras,” Fuzzy Sets and Systems, vol. 158, no. 4, pp. 452–471, 2007. Nguyễn Công Hào sinh năm 1976 tại Thừa [17] N. C. Ho and H. V. Nam, “An algebraic approach to linguistic Thiên Huế. Ông nhận bằng Tiến sĩ tại Viện hedges in Zadeh’s fuzzy logic,” Fuzzy Sets and Systems, vol. Công nghệ Thông tin Hà Nội, năm 2008. 129, no. 2, pp. 229–254, 2002. Hiện nay, ông là Giám đốc Trung tâm Công [18] N. C. Ho and W. Wechler, “Hedge algebras: an algebraic nghệ Thông tin, Đại học Huế. Lĩnh vực approach to structure of sets of linguistic truth values,” Fuzzy nghiên cứu của ông là cơ sở dữ liệu mờ, các Sets and Systems, vol. 35, no. 3, pp. 281–293, 1990. [19] ——, “Extended hedge algebras and their application to phương pháp tính toán mềm và các phương fuzzy logic,” Fuzzy Sets and Systems, vol. 52, no. 3, pp. pháp lập luận xấp xỉ. 259–281, 1992. 50