Luận văn Phân tách cụm danh từ cơ sở triếng việt sử dụng mô hình CRFS

à nhất quán nếu mọi đối tượng trong xU đều là nhất quán. 12 1.4.3. Quan hệ không phân biệt được Một trong những đặc điểm cơ bản của lý thuyết tập thô là dùng để lưu giữ và xử lý các dữ liệu trong đó có sự mập mờ, không phân biệt được. Trong một hệ thông tin theo định nghĩa trên cũng có thể có những đối tượng không phân biệt được. Định nghĩa 6: Cho hệ thông tin S = (U, A). Với mỗi tập thuộc tính B  A đều tạo ra tương ứng một quan hệ tương đương, kí hiệu IND(B) [1]-[8]: IND(B) = {(x,x’)  U2 |  a B, x(a) = x’(a) } IND(B) được gọi là quan hệ B-không phân biệt được. Nếu (x,x’)  IND(B) thì các đối tượng x và x’ là không thể phân biệt được với nhau qua tập thuộc tính B. Với mọi đối tượng x  U, lớp tương đương của x trong quan hệ IND(B) được kí hiệu bởi [x]B là tập tất cả các đối tượng có quan hệ IND(B) với x. Quan hệ B- không phân biệt được phân hoạch tập đối tượng U thành các lớp tương đương, kí hiệu là U/ IND(B) hay U/B, tức là U/B = {[x]P | x  U}. Ví dụ 1.3. [8] Xét hệ thông tin cho trong Bảng 1 Xét thuộc tính B = {LEMS}, ta có phân hoạch của tập U sinh bởi quan hệ tương đương IND(B) là: U/B = {{x1}, {x2}, {x3, x4}, {x5, x6, x7}} Khi đó, ta nói các cặp đối tượng x3, x4 và x5, x6 là không phân biệt qua tập thuộc tính {LEMS} vì chúng thuộc cùng một lớp tương đương định bởi quan hệ IND(B). Nếu ta xét B = {Age, LEMS}, ta có: U/B = {{x1}, {x2}, {x3, x4}, {x5, x7},{ x6}} Khi đó x5 và x6 là phân biệt được qua tập thuộc tính {Age, LEMS} vì chúng không thuộc cùng lớp tương đương định bởi quan hệ IND(B). 1.4.4. Xấp xỉ tập hợp Ta thấy ở bảng 2 khái niệm Walk không thể định nghĩa rõ ràng qua 2 thuộc tính điều kiện Age và LEMS vì có x3, x4 thuộc cùng một lớp tương đương tạo bởi 2 thuộc tính Age và LEMS nhưng lại có giá trị khác nhau tại thuộc tính 13 Walk. Vì vậy, nếu một đối tượng nào đó có (Age,LEMS) = (31-45, 1-25) thì ta vẫn không thể biết chắc chắn giá trị của nó tại thuộc tính Walk là Yes hay No. Vì vậy, ta thấy khái niệm Walk không được mô tả rõ ràng. Tuy nhiên, căn cứ vào tập thuộc tính {Age, LEMS} ta vẫn có thể chỉ ra được chắc chắn một số đối tượng có Walk là Yes, một số đối tượng có Walk là No, còn lại là các đối tượng thuộc tính về biên của hai giá trị Yes và No, cụ thể:  Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} thuộc tập {{16-30, 50}, {16-30, 26-49}} thì có Walk là Yes.  Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} thuộc tập {{16-30, 0}, {46-60, 26-49}} thì có Walk là No.  Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} = {31-45, 1- 25} thì có Walk là Yes hoặc No. Chính vì vậy ta có khái niệm xấp xỉ tập hợp như sau: Định nghĩa 1.3. [10] Cho hệ quyết định DT = (U, CD), tập thuộc tính BC, tập đối tượng XU. Chúng ta có thể xấp xỉ tập hợp X bằng cách sử dụng các thuộc tính trong B từ việc xây dựng các tập hợp B-xấp xỉ dưới và B-xấp xỉ trên được định nghĩa như sau: B-xấp xỉ dưới của tập X: BX = {x  U | [x]B  X} B-xấp xỉ trên của tập X: B X = {x  U | [x]B X ≠  Tập hợp BX là tập các đối tượng trong U mà sử dụng các thuộc tính trong B ta có thể biết chắc chắn được chúng là các phần tử của X. Tập hợp BX là các đối tượng trong U mà sử dụng các thuộc tính trong B ta chỉ có nói rằng chúng có thể là các phần tử của X. Tập BNB(X) = B X \BX được gọi là B-biên của tập X, nó chứa các đối tượng mà sử dụng các thuộc tính của B ta không thể xác định được chúng có thuộc tập X hay không. Tập U\ BX được gọi là B-ngoài của tập X, gồm những đối tượng mà sử dụng tập thuộc tính B ta biết chắc chắn chúng không thuộc tập X. Một tập hợp được gọi là thô nếu đường biên của nó là không rỗng, ngược lại ta nói tập này là rõ. Ví dụ 1.4. Xét hệ quyết định cho trong Bảng 2 14 Xét tập đối tượng X = {x U | x(Walk) = Yes} = {x1, x4, x6} và tập thuộc tính B = {Age, LEMS}. Khi đó ta có [8]: U/B ={{x1}, {x2}, {x3, x4}, {x5, x7},{ x6}} BX = {x U | [x]B  X} = {x1, x6} B X = {x  U | [x]B X ≠ } = {u1, u2, u5, u7, u8} Hình 4. Xấp xỉ tập đối tượng trong Bảng 2 bởi các thuộc tính điều kiện Age và LEMS 1.5. Kết luận chương 1 + Chương này đã giới thiệu tổng quan về khai phá dữ liệu, ứng dụng của khai phá dữ liệu, và giới thiệu một số phương pháp khai phá dữ liệu thông dụng. + Trình bày tổng quan về lý thuyết tập thô bao gồm hệ thống thông tin, quan hệ không phân biệt được, các tập thô, bảng quyết định,… Và đồng thời trình bày các ví dụ cụ thể để minh họa các khái niệm này. 15 Chương 2- CÂY QUYẾT ĐỊNH VÀ CÁC THUẬT TOÁN XÂY DỰNG CÂY QUYẾT ĐỊNH 2.1. Tổng quan về cây quyết định Cây quyết định là công cụ dùng để phân lớp các dữ liệu, nó có cấu trúc cây. Mỗi cây quyết định là một sự tượng trưng cho một sự quyết định của một lớp các dữ kiện nào đó. Mỗi nút trong cây là tên của một lớp hay một phép thử thuộc tính cụ thể nào đó, phép thử này phân chia không gian trạng thái các dữ kiện tại nút đó thành các kết quả có thể đạt được của phép thử. Mỗi tập con được phân chia của phép thử là không gian con của các sự kiện, nó tương ứng với một vấn đề con của sự phân lớp. Các cây quyết định được dùng để hỗ trợ quá trình ra quyết định. 2.1.1. Định nghĩa Cây quyết định là một cây mà mỗi nút của cây là: - Nút lá hay còn gọi là nút trả lời biểu thị cho một lớp các trường hợp mà nhãn của nó là tên của lớp. - Nút không phải là nút lá hay còn gọi là nút trong, nút định phép kiểm tra các thuộc tính, nhãn của nút này là tên của thuộc tính và có một nhánh nối nút này đến các cây con ứng với mỗi kết quả có thể có phép thử. Nhãn của nhánh này là các giá trị của thuộc tính đó. Nút trên cùng gọi là nút gốc. Hình 5. Mô tả chung về cây quyết định Để phân lớp mẫu dữ liệu chưa biết, giá trị các thuộc tính của mẫu được đưa vào kiểm tra trên cây quyết định. Mỗi mẫu tương ứng có một đường đi từ gốc đến lá và lá biểu diễn dự đoán giá trị phân lớp của mẫu đó. Nút gốc Các nhánh Nút trong Nút trong Nút lá Nút lá 16 Ví dụ 2.1: Cây quyết định Hình 6. Ví dụ về Cây quyết định 2.1.2. Thiết kế cây quyết định 2.1.2.1. Xử lý dữ liệu Trong thế giới thực, nói chung dữ liệu thô chắc chắn có mức độ nhiễu. Điều này có các nguyên nhân khác nhau như là dữ liệu lỗi, dữ liệu có đại lượng không chính xác, .... Do đó, chúng ta thường tiền xử lý (nghĩa là, “làm sạch”) để cực tiểu hoá hay huỷ bỏ tất cả dữ liệu thô bị nhiễu. Các giai đoạn tiền xử lý này cũng có thể biến đổi dữ liệu thô hiển thị hữu ích hơn, như hệ thống thông tin. Khi nhiều bước tiền xử lý ứng dụng hiệu quả, nó sẽ giúp cải tiến hiệu quả phân lớp. Các công việc cụ thể của tiền xử lý dữ liệu bao gồm những công việc như: - Filtering Attributes: Chọn các thuộc tính phù hợp với mô hình. - Filtering samples: Lọc các mẫu (instances, patterns) dữ liệu cho mô hình. - Transformation: Chuyển đổi dữ liệu cho phù hợp với các mô hình như chuyển đổi dữ liệu từ numeric sang nomial - Discretization (rời rạc hóa dữ liệu): Nếu bạn có dữ liệu liên tục nhưng có một số thuật toán chỉ áp dụng cho các dữ liệu rời rạc (như ID3, ADTDA,…) thì bạn phải thực hiện việc rời rạc hóa dữ liệu. mild Humidity high Normal low Outlook Temp Overcast Rainy hot TRUE FALSE TRUE FALSE Sunn TRUE FALSE 17 2.1.2.2. Tạo cây Cây quyết định được tạo thành bằng cách lần lượt chia (đệ quy) một tập dữ liệu thành các tập dữ liệu con, mỗi tập con được tạo thành chủ yếu từ các phần tử của cùng một lớp. Các nút (không phải là nút lá) là các điểm phân nhánh của cây. Việc phân nhánh tại các nút có thể dựa trên việc kiểm tra một hay nhiều thuộc tính để xác định việc phân chia dữ liệu. 2.1.2.3. Tiêu chuẩn tách Việc lựa chọn chủ yếu trong các thuật toán phân lớp dựa vào cây quyết định là chọn thuộc tính nào để kiểm tra tại mỗi nút của cây. Chúng ta mong muốn chọn thuộc tính sao cho việc phân lớp tập mẫu là tốt nhất. Như vậy chúng ta cần phải có một tiêu chuẩn để đánh giá vấn đề này. Có rất nhiều tiêu chuẩn được đánh giá được sử dụng đó là: + Lượng thông tin thu thêm IG (Information Gain, thuật toán ID3 của John Ross Quilan [9]). + Độ phụ thuộc của thuộc tính quyết định vào thuộc tính điều kiện theo nghĩa lí thuyết tập thô của Zdzisław Pawlak [3]-[10] Các tiêu chuẩn trên sẽ được trình bày trong các thuật toán xây dựng cây quyết định ở các phần dưới đây. 2.1.2.4. Tiêu chuẩn dừng Đây là phần quan trọng trong cấu trúc phân lớp của cây quyết định nhằm chia một nút thành các nút con. Chúng ta tập trung một số tiêu chuẩn dừng chung nhất được sử dụng trong cây quyết định. Tiêu chuẩn dừng truyền thống sử dụng các tập kiểm tra. Chúng ta kiểm tra cây quyết định trong suốt qúa trình xây dựng cây với tập kiểm tra và dừng thuật toán khi xảy ra lỗi. Một phương pháp khác sử dụng giá trị ngưỡng cho trước để dừng chia nút. Chúng ta có thể thay ngưỡng như là giảm nhiễu, số các mẫu trong một nút, tỉ lệ các mẫu trong nút, hay chiều sâu của cây, ... 2.1.2.5. Tỉa cây Trong giai đoạn tạo cây chúng ta có thể giới hạn việc phát triển của cây bằng số bản tin tối thiểu tại mỗi nút, độ sâu tối đa của cây hay giá trị tối thiểu của lượng thông tin thu thêm. Sau giai đoạn tạo cây chúng ta có thể dùng phương pháp “Độ dài mô tả ngắn nhất” (Minimum Description Length) hay giá trị tối thiểu của IG để tỉa cây 18 (chúng ta có thể chọn giá trị tối thiểu của IG trong giai đoạn tạo cây đủ nhỏ để cho cây phát triển tương đối sâu, sau đó lại nâng giá trị này lên để tỉa cây). 2.1.3. Phương pháp tổng quát xây dựng cây quyết định Quá trình xây dựng một cây quyết định cụ thể bắt đầu bằng một nút rỗng bao gồm toàn bộ các đối tượng huấn luyện và làm như sau [3]: 1. Nếu tại nút hiện thời, tất cả các đối tượng huấn luyện đều thuộc vào một lớp nào đó thì cho nút này thành nút lá có tên là nhãn lớp chung của các đối tượng. 2. Trường hợp ngược lại, sử dụng một độ đo, chọn thuộc tính điều kiện phân chia tốt nhất tập mẫu huấn luyện có tại nút. 3. Tạo một lượng nút con của nút hiện thời bằng số các giá trị khác nhau của thuộc tính được chọn. Gán cho mỗi nhánh từ nút cha đến nút con một giá trị của thuộc tính rồi phân chia các các đối tượng huấn luyện vào các nút con tương ứng. 4. Nút con t được gọi là thuần nhất, trở thành lá, nếu tất cả các đối tượng mẫu tại đó đều thuộc vào cùng một lớp. Lặp lại các bước 1-3 đối với mỗi nút chưa thuần nhất. Trong các thuật toán cơ sở xây dựng cây quyết định chỉ chấp nhận các thuộc tính tham gia vào quá trình phân lớp có giá trị rời rạc, bao gồm cả thuộc tính được dùng để dự đoán trong quá trình học cũng như các thuộc tính được sử dụng để kiểm tra tại mỗi nút của cây. Do đó trong trường hợp các thuộc tính có giá trị liên tục có thể dễ dàng loại bỏ bằng cách phân mảnh tập giá trị liên tục của thuộc tính thành một tập rời các khoảng. Việc xây dựng cây quyết định được tiến hành một cách đệ qui, lần lượt từ nút gốc xuống tới tận các nút lá. Tại mỗi nút hiện hành đang xét, nếu kiểm tra thấy thoả điều kiện dừng: thuật toán sẽ tạo nút lá. Nút này được gán một giá trị của nhãn lớp tùy điều kiện dừng được thoả mãn. Ngược lại, thuật toán tiến hành chọn điểm chia tốt nhất theo một tiêu chí cho trước, phân chia dữ liệu hiện hành theo điều kiện chia này. Sau bước phân chia trên, thuật toán sẽ lặp qua tất cả các tập con (đã được chia) và tiến hành gọi đệ qui như bước đầu tiên với dữ liệu chính là các tập con này. 19 Trong bước 3, tiêu chuẩn sử dụng lựa chọn thuộc tính được hiểu là một số đo độ phù hợp, một số đo đánh giá độ thuần nhất, hay một quy tắc phân chia tập mẫu huấn luyện. 2.1.3. Ứng dụng cây quyết định trong khai phá dữ liệu Sau khi đã xây dựng thành công cây quyết định ta sử dụng kết quả từ mô hình cây quyết định đó. Đây là bước sử dụng mô hình để phân lớp dữ liệu hoặc rút ra các tri thức trong phương pháp khai phá dữ liệu bằng phương pháp phân lớp. 2.1.3.1. Xác định lớp của các mẫu mới Trên cơ sở đã biết giá trị của các thuộc tính của các mẫu X1, X2, …, Xn ta xác định thuộc tính quyết định (hay phân lớp) Y của đối tượng đó (có thể dùng kỹ thuật này để nhận dạng mẫu, dự báo, …) Hình 7. Mô hình phân lớp các mẫu mới 2.1.3.2. Rút ra các tri thức hay luật từ cây Với mục đích và nhiệm vụ chính của việc khai phá dữ liệu là phát hiện ra các quy luật, các mô hình từ trong CSDL. Từ mô hình thu được ta rút ra các tri thức hay các quy luật dưới dạng cây hoặc các luật dưới dạng “If … Then…”. Hai mô hình trên là tương đương, chúng có thể được chuyển đổi qua lại giữa các mô hình đó với nhau. (Sunny, True, Cool, High) Cây quyết định Dữ liệu huấn luyện Dữ liệu cụ thể Kết quả ? 20 Ví dụ 2.2: Một trong các luật rút ra từ cây trong ví dụ 2.1 là +Luật 1: IF(Humidity: high) AND (Outlook: rainy) THEM (=> Quyết định: False) +Luật 2: IF(Humidity: high) AND (Outlook: sunny) THEM (=> Quyết định: False) +Luật 3: IF(Humidity: high) AND (Outlook: Overcast) THEN (=> Quyết định: True) … Từ đây ta sử dụng các luật này để hỗ trợ quá trình ra các quyết định, dự đoán, … 2.2. Thuật toán xây dựng cây quyết định dựa vào Entropy 2.2.1. Tiêu chí chọn thuộc tính phân lớp Tiêu chí để đánh giá tìm điểm chia là rất quan trọng, chúng được xem là một tiêu chuẩn “heuristic” để phân chia dữ liệu. Ý tưởng chính trong việc đưa ra các tiêu chí trên là làm sao cho các tập con được phân chia càng trở nên “trong suốt” (tất cả các bộ thuộc về cùng một nhãn) càng tốt. Thuật toán dùng độ đo lượng thông tin thu thêm (information IG - IG) để xác định điểm chia [9]. Độ đo này dựa trên cơ sở lý thuyết thông tin của nhà toán học Claude Shannon, độ đo này được xác như sau: Xét bảng quyết định DT = (U, C  {d} ), số giá trị (nhãn lớp) có thể của d là k. Khi đó Entropy của tập các đối tượng trong DT được định nghĩa bởi: i k i i ppUEntropy 2 1 log)(    trong đó pi là tỉ lệ các đối tượng trong DT mang nhãn lớp i. Lượng thông tin thu thêm (Information Gain - IG) là lượng Entropy còn lại khi tập các đối tượng trong DT được phân hoạch theo một thuộc tính điều kiện c nào đó. IG xác định theo công thức sau: )( || ||)(),( v Vv v UEntropy U UUEntropycUIG c    21 trong đó Vc là tập các giá trị của thuộc tính c, Uv là tập các đối tượng trong DT có giá trị thuộc tính c bằng v. IG(U, c) được John Ross Quinlan [9] sử dụng làm độ đo lựa chọn thuộc tính phân chia dữ liệu tại mỗi nút trong thuật toán xây dựng cây quyết định ID3. Thuộc tính được chọn là thuộc tính cho lượng thông tin thu thêm lớn nhất. 2.2.2. Thuật toán ID3 Thuật toán ID3 – Iterative Dichotomiser 3 [9] là thuật toán dùng để xây dựng cây quyết định được John Ross Quinlan trình bày. Ý tưởng chính của thuật toán ID3 là để xây dựng cây quyết định bằng cách ứng dụng từ trên xuống (Top- Down), bắt đầu từ một tập các đối tượng và các thuộc tính của nó. Tại mỗi nút của cây một thuộc tính được kiểm tra, kết quả của phép kiểm tra này được sử dụng để phân chia tập đối tượng theo kết quả kiểm tra trên. Quá trình này được thực hiện một cách đệ quy cho tới khi tập đối tượng trong cây con được sinh ra thuần nhất theo một tiêu chí phân lớp nào đó, hay các đối tượng đó thuộc cùng một dạng giống nhau nào đó. Các lớp hay các dạng này được gọi là nhãn của nút lá của cây, còn tại mỗi nút không phải là nút lá thì nhãn của nó là tên thuộc tính được chọn trong số các thuộc tính được dùng để kiểm tra có giá trị IG lớn nhất. Đại lượng IG được tính thông qua hàm Entropy. Như vậy, IG là đại lượng được dùng để đưa ra độ ưu tiên cho thuộc tính nào được chọn trong quá trình xây dựng cây quyết định. Giả mã của thuật toán ID3 như sau: Dữ liệu vào: Bảng quyết định DT = (U, C  {d}) Dữ liệu ra: Mô hình cây quyết định Function Create_tree (U, C, {d}) Begin If tất cả các mẫu thuộc cùng nhãn lớp di then return một nút lá được gán nhãn di else if C = null then return nút lá có nhãn dj là lớp phổ biến nhất trong DT else begin bestAttribute:= getBestAttribute(U, C); // Chọn thuộc tính tốt nhất để chia 22 C := C- {bestAttribute}; //xóa bestAttribute khỏi tập thuộc tính Với mỗi giá trị v in bestAttribute begin Uv := [U]v ; //Uv là phân hoạch của U theo thuộc tính //bestAttribute có giá trị là v ChildNode:=Create_tree(UV, C, {d}); //Tạo 1 nút con Gắn nút ChildNode vào nhánh v; end end End Giả mã của hàm getBestAttribute như sau: Dữ liệu vào: Bảng quyết định DT = (U, C{d}) Dữ liệu ra: Thuộc tính điều kiện tốt nhất Function getBestAttribute (U, C); Begin maxIG := 0; Với mỗi c in C begin tg : = IG(U, c); // Tính lượng thông tin thu thêm IG(U,c) If (tg > max IG) then begin maxIG := tg; kq := c; end end return kq; //Hàm trả về thuộc tính có lượng thông tin thu thêm IG là lớn nhất End 23 2.2.3. Ví dụ về thuật toán ID3 Xét bảng quyết định DT = {U, C  {d}} sau đây: Outlook Windy Temp Humidity d 1 overcast true cool high True 2 sunny false mild high false 3 sunny false hot high false 4 overcast false hot normal false 5 sunny true hot low True 6 rainy false mild high false 7 rainy false hot high false 8 rainy false hot normal false 9 overcast true hot low True 10 rainy false mild normal True 11 rainy true hot normal false 12 rainy false hot high false Bảng 3. Dữ liệu huấn luyện Giải thích cơ sở dữ liệu trong bảng 5: Mỗi một mẫu biểu diễn cho tình trạng thời tiết gồm các thuộc tính Outlook (quang cảnh), Temp (nhiệt độ), Humidity (độ ẩm) và Windy (gió); và đều có một thuộc tính quyết định d (chơi Tennis). Thuộc tính quyết định chỉ có hai giá trị True, False (chơi, không chơi tennis). Mỗi thuộc tính đều có một tập các giá trị hữu hạn: Thuộc tính Outlook có ba giá trị: Overcast (âm u) , Rain (mưa), Sunny (nắng); Temp có ba giá trị: Hot (nóng), Cool (mát) , Mild (ấm áp); Humidity có hai giá trị: High (cao), Normal (TB) và Windy có hai giá trị: True (có gió), False (không có gió). Các giá trị này chính là ký hiệu (symbol) dùng để biểu diễn bài toán. Thuật toán xây dựng cây quyết định như sau.  Đầu tiên nút lá được khởi tạo gồm các mẫu từ 1 đến 12 Để tìm điểm chia tốt nhất, phải tính toán chỉ số IG của tất cả các thuộc tính trên. Đầu tiên sẽ tính Entropy cho toàn bộ tập huấn luyện U gồm: bốn bộ 24 {1, 5, 9, 10} có giá trị thuộc tính nhãn là “TRUE” và tám bộ {2, 3, 4, 6, 7, 8, 11, 12} có thuộc tính nhãn là “FALSE”, do đó: Tính IG cho từng thuộc tính: - Thuộc tính “Outlook”. Thuộc tính này có ba giá trị là “Overcast”, “Sunny” và “Rainy”. Nhìn vào bảng dữ liệu ta thấy:  Với giá trị “Overcast” có ba bộ {1, 9} có giá trị thuộc tính nhãn là “TRUE” và có một bộ {4} có nhãn lớp là “FALSE”.  Tương tự giá trị “Sunny” có một bộ {5} có nhãn lớp là “TRUE” và có hai bộ {2, 3} có nhãn lớp là “FALSE”;  Với giá trị “Rainy” có một bộ {10} có nhãn lớp “TRUE” và năm bộ {6, 7, 8, 11, 12} có nhãn lớp “FALSE”. Theo công thức trên, độ đo lượng thông tin thu thêm của thuộc tính “Outlook” xét trên U là: Theo cách tính tương tự như trên, ta tính được: - IG(U,Windy)= )]log 8 7log 8 1( 12 8)log 4 1log 4 3( 12 4[918.0 8 7 28 1 24 1 24 3 2  = 0.285 - IG(U, Temp)= 148.0)]log 8 6log 8 2( 12 8)log 3 2log 3 1( 12 3[918.0 8 6 28 2 23 2 23 1 2  - IG(U, Humidity)= 323.0)]log 4 3log 4 1( 12 4)log 6 5log 6 1( 12 6[918.0 4 3 24 1 26 5 26 1 2  Như vậy, thuộc tính “Humidity” là thuộc tính có chỉ số IG lớn nhất nên sẽ được chọn là thuộc tính phân chia. Vì thế thuộc tính “Humidity” được chọn làm nhãn cho nút gốc, ba nhánh được tạo ra lần lượt với tên là: “high”, “Normal”, “low”. 0.918log 12 8log 12 4)( 12 8 212 4 2 UEntropy    Outlook )( || ||)()Outlook,( Vv v v UEntropy U UUEntropyUIG 134.0)]log 6 5log 6 1( 12 6)log 3 2log 3 1( 12 3)log 3 1log 3 2( 12 3[918.0 6 5 26 1 23 2 23 1 23 1 23 2 2  25 Hơn nữa nhánh “low” có các mẫu {5, 9} cùng thuộc một lớp “TRUE ” nên nút lá được tạo ra với nhãn là “TRUE ”. Kết quả phân chia sẽ là cây quyết định như sau: Hình 8. Cây sau khi chọn thuộc tính Humidity (ID3)  Bước tiếp theo gọi thuật toán đệ quy: ID3(U1, C-{Humidity}, {d}) Tương tự để tìm điểm chia tốt nhất tại thuật toán này, phải tính toán chỉ số IG của các thuộc tính “Outlook”, “Windy”, “Temp”. - Đầu tiên ta cũng tính Entropy cho toàn bộ tập huấn luyện trong U1 gồm một bộ {1} có thuộc tính nhãn là “TRUE ” và năm bộ {2, 3, 6, 7, 12} có thuộc tính nhãn là “FALSE”: - Tiếp theo tính IG cho thuộc tính “Outlook”, thuộc tính này có ba giá trị là “Overcast”, “Sunny” và “Rainy”. Nhìn vào bảng dữ liệu:  Với giá trị “Overcast” chỉ có một bộ {1} có giá trị thuộc tính nhãn là “TRUE ”.  Tương tự giá trị “Sunny” chỉ có hai bộ {2, 3} đều có nhãn lớp là “FALSE”;  Với giá trị “Rainy” chỉ có ba bộ {6, 7, 12} đều có nhãn lớp “FALSE”. Do đó, độ đo lượng thông tin thu thêm của thuộc tính “Outlook” xét trên U1 là: IG(U1, Outlook) =0.65 - )]log3 3( 6 3)log 2 2( 6 2)log 1 1( 6 1[ 3 3 22 2 21 1 2  = 0.65 - Tính tương tự ta cũng có: Humidity {1, 2, …., 12} ID3(U1, C-{humidity}, {d}) {1, 2, 3, 6, 7, 12} ID3(U2, C-{humidity}, {d}) {4, 8, 10, 11} high Normal low TRUE {5, 9 } 65.0log 6 5log 6 1)( 6 5 26 1 21 UEntropy 26 IG(U1, Windy) = 0.65 - )]log5 5( 6 5)log 1 1( 6 1[ 5 5 21 1 2  = 0.65 IG(U1, Temp) = 0.65 - )]log5 5( 6 5)log 1 1( 6 1[ 5 5 21 1 2  = 0.65 Ta thấy chỉ số IG của ba thuộc tính “Outlook”, “Windy”, “Temp” là như nhau, ta có thể chọn bất kỳ thuộc tính nào để phân chia. Giả sử ta chọn thuộc tính “Outlook” để phân chia. Do đó, thuộc tính “Outlook” làm nhãn cho nút bên trái nối với nhánh “high”. Thuộc tính này có ba giá trị “Overcast”, “Sunny” và “Rainy” nên ta tiếp tục tạo thành ba nhánh mới là “Overcast”, “Sunny” và “Rainy”:  Với nhánh “Overcast” gồm một mẫu {1} và có giá trị quyết định là “TRUE ” nên ta tạo nút lá là “TRUE ”.  Với nhánh “Sunny” gồm hai mẫu {2, 3} và có cùng giá trị quyết định là “FALSE” nên tạo nút lá là “FALSE”.  Với nhánh “Rainy” có ba mẫu {6, 7, 12} và đều có giá trị quyết định là “FALSE” nên ta tạo nút lá là “FALSE”. Sau khi thực hiện xong thuật toán đệ quy: ID3(U1, C-{Humidity}, {d}), ta có cây như sau: Hình 9. Cây sau khi chọn thuộc tính Outlook (ID3)  Bước tiếp theo gọi thuật toán đệ quy: ID3(U2, C-{ Humidity}, {d}) Tính một cách tương tự như trên ta có: Entropy (U2) = 811.0log4 3log 4 1 4 3 24 1 2  Overcast Rainy Humidity {1, 2,…, 12} high Normal low Outlook {1, 2, 3, 6, 7, 12} ID3(U2, C-{humidity}, {d}) {4, 8, 10 , 11} TRUE {5, 9 } FALSE {6, 7, 12 } TRUE {1 } FALSE {2, 3 } Sunny 27  IG(U2, Outlook) = 0.811 - )]log 3 2log 3 1( 4 3)log 1 1( 4 1[ 3 2 23 1 21 1 2  = 0.811-0.689 = 0.123  IG(U2, Windy) = 0.811 - )]log 1 1(4/1)log 3 2log 3 1( 4 3[ 1 1 23 2 23 1 2  = 0.811-0.689 = 0.123  IG(U2, Temp) = 0.811 - )]log 1 1( 3 1)log 3 3( 4 3[ 1 1 23 3 2  = 0.811-0 = 0.811 Ta thấy chỉ số IG của “Temp” là lớn nhất, nên nó được chọn để phân chia. Do đó, thuộc tính “Temp” làm nhãn cho nút bên phải nối với nhánh “Normal”. Trong U2, thuộc tính này có hai giá trị “hot” và “mild” nên ta tiếp tục tạo thành hai nhánh mới là “hot” và “mild”:  Với nhánh “hot” gồm ba mẫu {4, 8, 11} và đều có giá trị quyết định là “FALSE” nên ta tạo nút lá là “FALSE”.  Với nhánh “mild” gồm một mẫu {10} và có giá trị quyết định là “TRUE ” nên tạo nút lá là “TRUE ”. Cây cuối cùng như sau: Hình 10. Cây kết quả (ID3) mild Humidity {1, 2,…, 12} high Normal low Outlook {1, 2, 3, 6, 7, 12} Temp {4, 8, 10 , 11} Overcast Rainy hot TRUE {5, 9 } FALSE {6, 7, 12 } TRUE {1 } FALSE {2, 3 } Sunny TRUE {10 } FALSE {4, 8, 11 } 28 2.3. Thuật toán xây dựng cây quyết định dựa vào độ phụ thuộc của thuộc tính 2.3.1. Độ phụ thuộc của thuộc tính theo lý thuyết tập thô Xét bảng quyết định DT = (U, C  {D}). Ta nói D phụ thuộc C với độ phụ thuộc k (0 k  1) [10]: k = γ(C,D) = || |)(| U DCPOS Dễ dàng thấy rằng: γ(C,D) =   )(/ || || DINDUX U XC 0  (C, D)  1 Độ phụ thuộc (C, D) có các tính chất sau: - Nếu (C, D) = 1 thì D phụ thuộc hoàn toàn vào C - Nếu 0 < (C, D) < 1 thì d phụ thuộc một phần vào B - Nếu (d, B) = 0 thì không có đối tượng nào của U có thể được phân lớp đúng (như d) dựa vào tập thuộc tính B. 2.3.2. Độ phụ thuộc chính xác  theo lý thuyết tập thô Xét bảng quyết định DT = (U, C  {D}) và tập con thuộc tính điều kiện B  C. Giả sử U/D = {Y1, Y2, …, Ym} và U/B = {X1, X2, …, Xn}. Đặt       || |x| |x||x ),( U Y DB B B B        (B, D) gọi là độ phụ thuộc chính xác  dùng để đo tỉ lệ các đối tượng được phân lớp với mức độ chính xác , trong đó giá trị  (0.5 ≤  ≤ 1) dùng để xác định tỉ lệ các phân lớp đúng [10]. 2.3.3. Tiêu chí chọn thuộc tính để phân lớp Theo cách tiếp cận tập thô, độ phụ thuộc (c, d) được sử dụng làm tiêu chuẩn lựa chọn thuộc tính kiểm tra tại mỗi nút trong quá trình phát triển cây quyết định: thuộc tính được chọn là thuộc tính c cho giá trị (c, d) lớn nhất trong số các thuộc tính còn lại tại mỗi bước [10]. Nếu tất cả độ phụ thuộc (c, d) của các thuộc tính bằng không thì thuộc tính được chọn là thuộc có độ phụ thuộc chính xác  lớn nhất. 29 2.3.4. Thuật toán xây dựng cây quyết định ADTDA Thuật toán ADTDA - Algorithm for Buiding Decision Tree Based on Dependency of Attributes [10] là thuật toán dùng để xây dựng cây quyết định được Longjun Huang, Minghe Huang, Bin Guo, and Zhiming Zhang trình bày. Ý tưởng chính của thuật toán ADTDA là để xây dựng cây quyết định bằng cách ứng dụng từ trên xuống chiến lược tham lam thông qua các tập đã cho để kiểm tra từng thuộc tính ở mọi nút của cây. Để chọn thuộc tính "tốt nhất" (để có cây tối ưu – có độ sâu nhỏ nhất), người ta phải tính độ phụ thuộc của thuộc tính quyết định vào thuộc tính điều kiện. Thuộc tính được chọn phải có độ phụ thuộc lớn nhất. Giả mã của thuật toán ADTDA như sau: Dữ liệu vào: Bảng quyết định DT = (U, C  {d}) Dữ liệu ra: Mô hình cây quyết định Function Create_tree (U, C, {d}) Begin If tất cả các mẫu thuộc cùng nhãn lớp di then return một nút lá được gán nhãn di else if C = null then return nút lá có nhãn dj là lớp phổ biến nhất trong DT else begin bestAttribute:= getBestAttribute(U, C); // Chọn thuộc tính tốt nhất để chia Lấy thuộc tính bestAttribute làm gốc; C := C- {bestAttribute}; //xóa bestAttribute khỏi tập thuộc tính Với mỗi giá trị v in bestAttribute begin Uv := [U]v ; //Uv là phân hoạch của DT theo thuộc tính //bestAttribute có giá trị là v ChildNode:=Create_tree(Uv, U, {d}); //Tạo 1 nút con Gắn nút ChildNode vào nhánh v; end 30 end End Thuật toán ADTDA giống thuật toán ID3, nhưng khác nhau ở hàm getBestAttribute. Giả mã của hàm getBestAttribute như sau: Dữ liệu vào: Bảng quyết định DT = (U, C{d}) Dữ liệu ra: Thuộc tính điều kiện tốt nhất Function getBestAttribute (U, C); Begin maxDependency := 0; Với mỗi c in C begin k : = DependencyGama(U, c); // Tính độ phụ thuộc của thuộc tính γ(c,d) If (k > maxDependency) then begin maxDependency := k; kq := c; end end return kq; //Hàm trả về thuộc tính có độ phụ thuộc của thuộc tính γ(c,d) lớn nhất End 2.3.5. Ví dụ Xét bảng quyết định cho trong Bảng 5  Để xây dựng cây ta tính độ phụ thuộc của tất cả các thuộc tính điều kiện vào thuộc tính quyết định d. - Thuộc tính quyết định d có 4 mẫu {1, 5, 9, 10} có giá trị “TRUE ” và 6 mẫu {2, 3, 4, 6, 7, 8, 11, 12} có giá trị “FALSE” , nên ta có: [U]d = {{1, 5, 9 ,10}, {2, 3, 4, 6, 7, 8, 11, 12}} - Thuộc tính “Outlook” có ba giá trị “Overcast” gồm 3 mẫu {1, 4, 9}, “sunny” gồm 3 mẫu {2, 3, 5} và “rainy” gồm sáu mẫu {6, 7, 8, 10, 11, 12} nên : [U]Outlook= {{1, 4, 9}, {2, 3, 5}, {6, 7, 8, 11, 11, 12}} 31 Do đó: 0 12 0 || |{}| || |)(| ),(  UU dpos dOutlook Outlook Tương tự, ta có:  [U]Windy = {{1, 5, 9, 11},{2, 3, 4, 6, 7, 8, 10, 12}} .0 12 0 || |{}| || |)(| )dWindy,( Windy  UU dpos   [U]Temp={{1}, {2, 6, 10}, {3, 4, 5, 7, 8, 9, 11, 12} . 12 1 || |}1{| || |)(| ),(  UU dpos dTemp Temp  [U]Humidity = {{1, 2, 3, 6, 7, 12}, {4, 8, 10, 11}, {5, 9}} . 12 2 || |}9,5{| || |)(| ),Humidity( Humidity  UU dpos d Ta thấy ),Humidity( d có giá trị lớn nhất nên ta chọn thuộc tính “Humidity” làm thuộc tính phân chia. Như vậy nút gốc có nhãn là “Humidity” và có 3 nhánh được tạo ra lần lượt với tên là: “high”, “Normal”, “low”. Hơn nữa nhánh “low” có các mẫu {5, 9} cùng thuộc một lớp “TRUE ” nên nút lá được tạo ra với nhãn là “TRUE ”. Kết quả phân chia sẽ là cây quyết định như sau: Hình 11. Cây sau khi chọn thuộc tính Humidity (ADTDA)  Bước tiếp theo gọi thuật toán đệ quy: ADTDA (U1, C-{Humidity}, {d}) Ta có: [U1]d = {{1}, {2, 3, 6, 7, 12}}  [U1]Outlook= {{1}, {2, 3}, {6, 7, 12}} Do đó, 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dposdOutlook Outlook  [U1]windy = {{1}, {2, 3, 6, 7, 12} Humidity U={1, 2, …., 12} ADTDA(U1, C-{humidity}, {d}) U1={1, 2, 3, 6, 7, 12} ADTDA(U2, C-{humidity}, {d}) U2={4, 8, 10, 11} high Normal low TRUE {5, 9 } 32 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dpos dwindy windy  [U1]Temp={{1}, {2, 6}, {3, 7, 12}} 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dpos dTemp Temp Ta thấy độ phụ thuộc của ba thuộc tính “Outlook”, “Windy”, “Temp” vào thuộc tính quyết định d là như nhau, nên ta có thể chọn bất kỳ thuộc tính nào để phân chia. Tương tự như ở thuật toán ID3, ta có cây như sau: Hình 12. Cây sau khi chọn thuộc tính Outlook (ADTDA)  Bước tiếp theo gọi thuật toán đệ quy: ADTDA(U2, C-{Humidity}, {d}) Một cách tương tự như trên ta có: [U2]d= {{10}, {4, 8, 11}}  [U2]Outlook = {{4}, {8, 10, 11}} Do đó, 4 1 || |}4{| || |)(| ),( 22  UU dposdOutlook Outlook  [U2]windy = {{4, 8, 10}, {11} 4 1 || |}11{| || |)(| ),( 22  UU dpos dwindy windy  [U2]Temp={{4, 8, 11}, {10}} high Normal low outlook U1={1, 2, 3, 6, 7, 12} ADTDA(U2, C-{humidity}, {d}) U2={4, 8, 10 , 11} Overcast Rainy TRUE {5, 9 } FALSE {6, 7, 12 } TRUE {1 } FALSE {2, 3 } Sunny Humidity U={1, 2, …., 12} 33 1 4 4 || |}11,10,8,4{| || |)(| ),( 22  UU dpos dTemp Temp Ta thấy ),( dTemp là lớn nhất, nên thuộc tính “temp” được chọn để phân chia. Do đó, thuộc tính “Temp” làm nhãn cho nút bên phải nối với nhánh “Normal”. Tương tự như trong thuật toán ID3, cây cuối cùng như sau: Hình 13. Cây kết quả (ADTDA) 2.4. Thuật toán xây dựng cây quyết định dựa vào Entropy và độ phụ thuộc của thuộc tính 2.4.1. Tiêu chí chọn thuộc tính để phân lớp Xét bảng quyết định DT = (U, C  {d}). Lượng thông tin thu thêm ổn định IGfix - Fixed Information Gain [5] là tiêu chuẩn mới cho chọn thuộc tính thuộc tính điều kiện c nào đó để phân chia. IGfix được xác định theo công thức sau: || ),(*),(),( c cUIGcdcUIG fix  Trong đó: + |c| là số các giá trị khác nhau của thuộc tính điều kiện c + (c, d) là độ phụ thuộc c vào d + IG(U, c) là lượng thông tin thu thêm high Normal low Outlook {1, 2, 3, 6, 7, 12} Temp {4, 8, 10 , 11} Overcast Rainy mild hot TRUE {5, 9 } FALSE {6, 7, 12 TRUE {1 } FALSE {2, 3 } Sunny Humidity {1, 2,…, 12} TRUE {10 } FALSE {14, 8, 11} 34 Lượng thông tin thu thêm ổn định của thuộc tính được sử dụng như một tiêu chuẩn cho việc chọn thuộc tính kiểm tra tại mỗi nút trong cây quyết định. Thuộc tính điều kiện với giá trị lượng thông tin thu thêm ổn định lớn nhất được chọn từ tập rút gọn thuộc tính và được sử dụng làm nút gốc của cây. 2.4.2. Thuật toán FID3 (Fixed Iterative Dichotomiser 3 [5] ) Dữ liệu vào: Bảng quyết định DT = (U, C  {d}) Dữ liệu ra: Mô hình cây quyết định Function Create_tree (U, C, {d}) Begin If tất cả các mẫu thuộc cùng nhãn lớp di then return một nút lá được gán nhãn di else if C = null then return nút lá có nhãn dj là lớp phổ biến nhất trong DT else begin bestAttribute:= getBestAttribute(U, C); // Chọn thuộc tính tốt nhất để chia Lấy thuộc tính bestAttribute làm gốc; C := C- {bestAttribute}; //xóa bestAttribute khỏi tập thuộc tính Với mỗi giá trị v in bestAttribute begin Uv := [U]v ; //Uv là phân hoạch của DT theo thuộc tính //bestAttribute có giá trị là v ChildNode:=Create_tree(Uv, C, {d}); //Tạo 1 nút con Gắn nút ChildNode vào nhánh v; end end End Thuật toán FID3 giống thuật toán ID3, nhưng khác nhau ở hàm getBestAttribute. Giả mã của hàm getBestAttribute như sau [5]: 35 Dữ liệu vào: Bảng quyết định DT = (U, C{d}) Dữ liệu ra: Thuộc tính điều kiện tốt nhất Function getBestAttribute (U, C); Begin C’:= C ; Với mỗi c in C begin k := DependencyGama(U, c); // Tính độ phụ thuộc của thuộc tính γ(c,d) If (k =0) then C’:= C’ - {c}; end Với mỗi c in C’ begin tg := Igfix(U,c); //Tính lượng thông tin thu thêm ổn định If (tg>maxIGfix) then begin maxIGfix:= tg; kq := c; end end return kq; //Hàm trả về thuộc tính có lượng thông tin thu thêm IGfix(U,c) lớn nhất End 2.4.3. Ví dụ Xét bảng quyết định DT= (U, C  {d}} cho trong Bảng 5 Trong thuật toán ADTDA ở trên, ta đã tính được: γ(Outlook,d) = 0 γ(Windy,d) = 0 γ(Temp,d) = 12 1 . 12 2),Humidity( d 36 Nên thuộc tính mới C’ = {Temp, Humidity}. Ta tính IGfix(U,Temp) và IGfix(U, Humidity) : Trong thuật toán ID3 ở trên ta có: IG(U, Temp)= 0.148 IG(U, Humidity)= 0.323 Do đó: IGfix(U,Temp) = 064.03 148.0* 12 1 || ),( *),(  Temp TempUIG dTemp IGfix(U,Humidity) = || ),(*),( Temp HumidityUIGdHumidity = 134.0 3 323.0* 12 2  Ta thấy IGfix(U,Humidity) có giá trị lớn nhất nên ta chọn thuộc tính “Humidity” làm thuộc tính phân chia. Tương tự như thuật toán ID3, ta có cây như sau: Hình 14. Cây quyết định sau khi chọn thuộc tính Humidity (FID3)  Bước tiếp theo gọi thuật toán đệ quy: FID3(U1, C-{Humidity}, {d})  Theo thuật toán ADTDA ta có: [U1]d = {{1}, {2, 3, 6, 7, 12}  [U1]Outlook= {{1}, {2, 3}, {6, 7, 12}} Do đó, 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dposdOutlook Outlook  [U1]windy = {{1}, {2, 3, 6, 7, 12} TRUE U={1, 2, …., 12} FID3(U1, C-{humidity}, {d}) U1={1, 2, 3, 6, 7, 12} FID3(U2, C-{humidity}, {d}) U2={4, 8, 10, 11} high Normal low TRUE {5, 9 } 37 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dpos dwindy windy  [U1]Temp={{1}, {2, 6}, {3, 7, 12}} 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dpos dTemp Temp  Theo thuật toán ID3 ta có: IG(U1, Windy) = 0.65 IG(U1, Outlook) = 0.65 IG(U1, Temp) = 0.65 Vậy:  IGfix(U1, Windy)= 57.02 65.0*1 || ),( *),( 1  Windy WindyUIGdWindy  IGfix(U1, Outlook)= 465.03 65.0*1 || ),( *),( 1  Outlook OutlookUIGdOutlook  IGfix(U1, Temp)= 465.03 65.0*1 || ),( *),( 1  Temp TempUIGdTemp Ta thấy IGfix(U1, Windy) có giá trị lớn nhất nên thuộc tính “Windy” được chọn làm thuộc tính phân chia. Do đó, thuộc tính “Windy” làm nhãn cho nút bên trái nối với nhánh “high”. Thuộc tính này có hai giá trị “true” và “false” nên ta tiếp tục tạo thành hai nhánh mới là “true” và “false”:  Với nhánh “true” gồm một mẫu {1} và có giá trị quyết định là “Y” nên ta tạo nút lá là “Y”.  Với nhánh “false” gồm năm mẫu {2, 3, 6, 7, 12} và có cùng giá trị quyết định là “N” nên tạo nút lá là “N”. Sau khi thực hiện xong thuật toán đệ quy: FID3(U1, C-{Humidity}, {d}), ta có cây như sau: 38 Hình 15. Cây quyết định sau khi chọn thuộc tính Windy (FID3)  Bước tiếp theo gọi thuật toán đệ quy: FID3(U2, C-{Humidity}, {d})  Theo thuật toán ADTDA ta có: [U2]d= {{10}, {4, 8, 11}}  [U2]Outlook = {{4}, {8, 10, 11}} Do đó, 4 1 || |}4{| || |)(| ),( 22  UU dposdOutlook Outlook  [U2]windy = {{4, 8, 10}, {11} 4 1 || |}11{| || |)(| ),( 22  UU dpos dwindy windy  [U2]Temp={{4, 8, 11}, {10}} 1 4 4 || |}11,10,8,4{| || |)(| ),( 22  UU dpos dTemp Temp  Theo thuật toán ID3 ta có:  IG(U2, Outlook) =0.123  IG(U2, Windy) = 0.123  IG(U2, Temp) = 0.811 Vậy:  IGfix(U2, Windy)= 124.02 123.0* 4 1 || ),( *),( 2  Windy WindyUIGdWindy  IGfix(U2, Outlook)= 101.0 3 1235.0* 4 1 || ),( *),( 2  Outlook OutlookUIGdOutlook Humidity {1, 2,…, 12} high Normal low windy {1, 2, 3, 6, 7, 12} FID3(U2, C-{humidity}, {d}) {4, 8, 10 , 11} true false TRUE {5, 9 } FALSE {2, 3, 6, 7, 12 } TRUE {1 } 39  IGfix(U2, Temp)= 519.03 811.0*1 || ),( *),( 2  Temp TempUIGdTemp Ta thấy chỉ số IGfix(U2,Temp) là lớn nhất, nên nó được chọn để phân chia. Tương tự như thuật toán ID3 ta có cây cuối cùng như sau: Hình 16. Cây kết quả (FID3) 2.5. Kết luận chương 2 Trong chương này đã trình bày phương pháp tổng quát xây dựng cây quyết định; ba thuật toán xây dựng cây quyết định ID3, ADTDA, FID3; các ví dụ cụ thể để minh họa từng bước trên mỗi thuật toán; high Normal low windy {1, 2, 3, 6, 7, 12} true false TRUE {5, 9 } FALSE {2, 3, 6, 7, 12 } TRUE {1 } Humidity {1, 2,…, 12} temp {4, 8, 10 , 11} mild hot TRUE {10 } FALSE {4, 8, 11} 40 Chương 3 - ỨNG DỤNG KIỂM CHỨNG VÀ ĐÁNH GIÁ 3.1. Giới thiệu bài toán Chúng ta đang sống trong thế giới thừa thông tin thiếu tri thức – đó là nhận định của nhiều người trong thời đại bùng nổ thông tin hiện nay. Sử dụng phương pháp khai phá tri thức từ dữ liệu để dự đoán rủi ro tín dụng là một phương pháp mới nhằm nâng cao chất lượng tín dụng của Ngân hàng. Rủi ro tín dụng có thể được hiểu là nguy cơ một người đi vay không thể trả được gốc và/hoặc lãi đúng thời hạn quy định. Hiện nay, để phòng ngừa rủi ro tín dụng, các chuyên gia Ngân hàng thực hiện các phương pháp thu thập, phân tích và đánh giá các thông tin về khách hàng, tài sản bảo đảm của khoản vay… Phương pháp truyền thống này có nhiều hạn chế do phụ thuộc vào trình độ, tâm lý và yếu tố chủ quan khác của các cán bộ thẩm định hồ sơ vay nợ của khách hàng. Chính vì vậy mà một công cụ trợ giúp thẩm định và ước đoán chất lượng tín dụng một cách khách quan dựa trên các cơ sở khoa học là hết sức có ý nghĩa và cần thiết. Việc đề xuất cho vay hay không dựa vào các luật quyết định (phân lớp) được xây dựng thông qua cây quyết định đã được nghiên cứu. Nhờ các luật quyết định này sẽ hỗ trợ cán bộ tín dụng có quyết định cho khách hàng vay hay không. Trong phạm vi luận văn này tôi đã tập trung nghiên cứu đối với công tác tín dụng tiêu dùng của khách hàng với tập dữ liệu Bank_data. Dựa vào tập Bank_data sẽ xây dựng mô hình cây quyết định, từ cây quyết định rút ra các luật quyết định. Dựa vào các luật quyết định đó ta sẽ phân lớp được tập dữ liệu mới (dữ liệu về khách hàng xin vay tiêu dùng, nhưng chưa được phân lớp) và tập dữ liệu sau khi được phân lớp sẽ hỗ trợ cho các cán bộ tín dụng ra quyết định cho khách hàng vay hay không. 3.2. Giới thiệu về cơ sở dữ liệu Trong quá trình thử nghiệm, tôi sử dụng tập dữ liệu Bank_data trích từ cơ sở dữ liệu được sưu tầm bởi giáo sư Bamshad Mobasher của Khoa “School of Computing, College of Computing and Digital Media” tại đại học “DePaul University” tại Mỹ ( bank-data.csv). Tập dữ liệu này gồm 600 đối tượng, sau khi tiền sử lí với phần 41 mềm Weka và lưu dưới dạng file excel ta có tập dữ liệu gồm 600 đối tượng, 10 thuộc tính điều kiện và thuộc tính quyết định “result” quyết định mỗi khách hàng là được vay và không được vay. Các thuộc tính và giá trị của các thuộc tính của tập dữ liệu Bank_data được mô tả trong bảng sau: Thứ tự Tên thuộc tính Giá trị Giải thích 1 Tuoi Tre, Trung nien, Gia Trẻ, trung niên, già 2 Gioi_tinh Nam, Nu Nam, Nữ 3 Khu_vuc NT, TTran, Ngoai o, TP Nông thôn, Thị trấn, ngoại ô, thành phố 4 Thu_nhap Thap, TB, Cao Thấp, trung bình, cao 5 Ket_hon C, K Có, không 6 Con 0_Con, 1_con, 2_con, 3_con Không con, một con, hai con, ba con 7 Xe C, K Có, không 8 TKTK (tài khoản tiết kiệm) C, K Có, không 9 TK_Htai (tài khoản hiện tại) C, K Có, không 10 The_chap C, K Có, không 11 RESULT (Cho vay) True, false Có (True), không (False) Bảng 4. Bảng các thuộc tính của tập dữ liệu Bank_data 3.3. Cài đặt ứng dụng Ứng dụng này được viết trong môi trường Visual Studio 2008, viết bằng ngôn ngữ lập trình Visal Basic. Ứng dụng này tập trung vào xây dựng và đánh giá độ chính xác của các thuật toán được trình bày ở chương 2. Từ các cây quyết định hay các luật quyết định rút ra từ cây quyết định sẽ hỗ trợ cho các cán bộ tín dụng trong ngân hàng quyết định cho khách hàng được vay hay không. 42 3.4. Kết quả và đánh giá thuật toán 3.4.1. Mô hình cây quyết định tương ứng với tập dữ liệu Bank_data  Cây quyết định ứng với thuật toán ID3 Hình 17. Dạng cây quyết định ID3  Cây quyết định ứng với thuật toán ADTDA Hình 18. Dạng cây quyết định ADTDA 43  Cây quyết định ứng với thuật toán FID3 Trong quá trình thực nghiệm tác giả thấy trong thuật toán FID3 nếu áp dụng trên 1 cơ sở dữ liệu lớn thì độ phục thuộc của các thuộc tính điều kiền vào thuộc tính quyết định đều bằng 0 (ở bước đầu tiên khi xây dựng cây quyết định). Do đó, lượng thông tin thu thêm ổn định IGfix của các thuộc tính điều kiện cũng bằng 0. Trong trường hợp này thì thuật toán sẽ chọn một thuộc tính bất kỳ (thuộc tính đầu tiên) làm thuộc tính phân chia, và như vậy cây quyết định sẽ không tối ưu. Vì vậy, tác giả đã mạnh dạn cải tiến dựa theo thuật toán ADTDA, đó là nếu tất các các độ phụ thuộc của thuộc tính điều kiện vào thuộc tính quyết định là bằng 0, thì lượng thông tin thu ổn định IGfix sẽ được tính dựa vào độ phụ thuộc chính xác , tức là: Và khi đó cây quyết định của thuật toán FID3 trên cơ sở dữ liệu Bank_data như sau: Hình 19. Dạng cây quyết định FID3 || ),(*),(),( c cUIGcdcUIG fix  44 3.4.2. Các luật quyết định tương ứng với tập dữ liệu Bank_data  Các luật quyết định ứng với cây quyết định ID3 Hình 20. Một số luật của cây quyết định ID3  Các luật quyết định ứng với cây quyết định ADTDA Hình 21. Một số luật của cây quyết định ADTDA  Các luật quyết định ứng với cây quyết định FID3 Hình 22. Một số luật của cây quyết định FID3 3.4.3. Đánh giá thuật toán Đánh giá độ chính xác của thuật toán với số nếp gấp (fold) là 10 trên bộ dữ liệu tennis (Bảng 3) và bộ dữ liệu Bank_data, ta được kết quả như sau: 45 Dữ liệu Số mẫu Số thuộc tính ID3 ADTDA FID3 Bank_data 600 11 77.33% 78.57% 80.71% Tennis 12 5 80% 80% 80% Trung bình 78.67% 79.29% 80.36% Bảng 5. Độ chính xác của các thuật toán 3.4.4. Ứng dụng cây quyết định trong khai phá dữ liệu Ứng dụng hỗ trợ các bộ ngân hàng ra quyết định cho khách hàng vay hay không. Với những tin về khách hàng xin vay (đã biết giá trị của các thuộc tính điều kiện nhưng chưa được phân lớp) dựa vào mô hình cây quyết định đã được xây dựng ta dự đoán được lớp của bộ dữ liệu đó (cho vay hay không cho vay). Từ đó hỗ trợ cho cán bộ ngân hàng trong quá trình ra quyết định cho vay hay không. Trong ứng dụng, khi xây dựng mô hình cây quyết định có đánh giá độ chính xác của từng luật quyết định dựa trên bộ dữ liệu đưa vào để training. Do đó, việc phân lớp các mẫu dữ liệu mới đã đưa ra được độ tin cậy của việc phân lớp đó. Ví dụ khi đánh giá độ chính xác của luật 9 dựa trên bộ dữ liệu training là 90%. Quá trình phân lớp trên mẫu dữ liệu nào đó dựa vào luật 9, thì độ tin cậy của lớp đó sẽ là 90%. Độ tin cậy của các luật quyết định phụ thuộc rất lớn vào bộ dữ liệu training, dữ liệu training càng đủ lớn thì độ tin cậy của các luật càng cao. Tuy nhiên, trong ứng dụng này việc xây dựng cây quyết định chỉ dựa trên bộ dữ liệu training gồm 600 dữ liệu, do đó độ tin cậy của các luật chỉ mang tính chất minh họa (tính chính xác không cao). 46 Hình 23. Giao diện ứng dụng 3.5. Kết luận chương 3 Trong chương này đã phát biểu bài toán để kiểm chứng các thuật toán xây dựng cây quyết định ở chương 2 trên bộ dữ liệu mẫu Bank_data. Đồng thời cài đặt, đánh giá độ chính xác của từng thuật toán và đánh giá độ chính xác của các luật. Dựa vào mô hình cây quyết định (các luật quyết định) đã được xây dựng, phân lớp các mẫu dữ liệu mới. 47 KẾT LUẬN Khai phá dữ liệu là một lĩnh vực đã, đang và luôn luôn thu hút các nhà nghiên cứu bởi nó là một lĩnh vực cho phép phát hiện tri thức trong cơ sở dữ liệu khổng lồ bằng các phương thức thông minh. Nghiên cứu lĩnh vực này đòi hỏi người nghiên cứu phải biết tổng hợp các kết quả nghiên cứu ở nhiều lĩnh vực của khoa học máy tính và việc ứng dụng nó trong từng nhiệm vụ của khai phá dữ liệu. Qua hai năm học tập, tìm tòi, nghiên cứu, đặc biệt là trong khoảng thời gian làm luận văn, tác giả đã hoàn thiện luận văn với các mục tiêu đặt ra ban đầu. Cụ thể luận văn đã đạt được những kết quả sau: - Trình bày các kiến thức cơ bản về khai phá dữ liệu; hệ thống hóa các kiến thức cơ bản của lý thuyết tập thô được áp dụng để xây dựng cây quyết định. - Giới thiệu phương pháp tổng quát xây dựng cây quyết định, và trình bày ba thuật toán xây dựng cây quyết định ID3, ADTDA, FID3 và một số ví dụ minh họa cho các phương pháp xây dựng cây quyết định cũng được trình bày. - Cài đặt bằng Visual Basic ba thuật toán xây dựng cây quyết định ID3, ADTDA, FID3 trên cơ sở dữ liệu mẫu Bank_data. Đánh giá độ chính xác của các thuật toán trên và đánh giá độ chính xác của từng luật trong mô hình cây quyết định. Qua quá trình học tập, nghiên cứu tác giả không những tích lũy được thêm các kiến thức mà còn nâng cao được khả năng lập trình, phát triển ứng dụng. Tác giả nhận thấy luận văn đã giải quyết tốt các nội dung, yêu cầu nghiên cứu đặt ra, có các ví dụ minh họa cụ thể. Song do thời gian có hạn nên luận văn vẫn còn tồn tại một số thiếu sót, một số vấn đề mà tác giả còn phải tiếp tục nghiên cứu, tìm hiểu. Hướng phát triển của đề tài là: Về lý thuyết: - Cần tiếp tục nghiên cứu các thuật toán khai phá dữ liệu bằng cây quyết định dựa vào tâp thô như: thuật toán ADTCCC (dựa vào CORE và đại 48 lượng đóng góp phân lớp của thuộc tính), thuật toán ADTNDA (dựa vào độ phụ thuộc mới của thuộc tính), … - Nghiên cứu các phương pháp xây dựng cây quyết định trên hệ thống thong tin không đầy đủ, dữ liệu liên tục và không chắc chắn. Về chương trình demo: - Cần bổ sung thêm dữ liệu cho tập training để mô hình cây quyết định có độ tin cậy cao hơn và hoạt động hiệu quả hơn. - Cần tiếp tục phát triển hoàn thiện theo hướng trở thành phần mềm khai phá dữ liệu trong tín dụng tiêu dùng nhằm hỗ trợ cho cán bộ tín dụng đưa ra quyết định cho khách hàng vay hay không. - Tìm hiểu nhu cầu thực tế để từ đó cải tiến chương trình, cài đặt lại bài toán theo các thuật toán đã nghiên cứu để làm việc tốt hơn với các cơ sở dữ liệu lớn và có thể có được sản phẩm trên thị trường.. 49 TÀI LIỆU THAM KHẢO Tiếng Việt [1] Hồ Thuần, Hoàng Thị Lan Giao (2005), “Một thuật toán tìm tập rút gọn sử dụng ma trận phân biệt được”, Chuyên san các công trình nghiên cứu triển khai Viễn thông và CNTT, (15), tr. 83-87. [2] Nguyễn Thanh Bình (2007), “Ứng dụng cây quyết định trong bài toán phân lớp”, Luận văn thạc sỹ khoa học. Trường đại học Khoa học - Đại học Huế. [3] Nguyễn Thanh Tùng (2009), “Một tiêu chuẩn mới chọn nút xây dựng cây quyết định”, Tạp chí Khoa học và Công nghệ, 47(2), tr. 15–25. Tiếng Anh [4] Andrzej Skowron, Ning Zhong (2000), “Rough Sets in KDD”, Tutorial Notes. [5] Baoshi Ding, Yongqing Zheng, Shaoyu Zang (2009), "A New Decision Tree Algorithm Based on Rough Set Theory", Asia-Pacific Conference on Information Processing, (2), pp. 326-329. [6] Cuiru Wang, Fangfang OU (2008), "An Algorithm for Decision Tree Construction Based on Rough Set Theory", International Conference on Computer Science and Information Technology, pp. 295-298. [7] Ho Tu Hao, Knowledge Discovery and Dataming Techniques and Practice, http:// www.netnam.vn/unescocourse/knowledge. [8] Jan Komorowski, Lech Polkowski, Andrzej Skowron, “Rough Sets: A Tutorial”. [9] John Ross Quilan (1990), “Decision trees and decision making”, IEEE transactions on Man and Cybernetics, (20), pp. 339-346. [10] Longjun Huang, Minghe Huang, Bin Guo, Zhimming Zhang (2007), "A New Method for Constructing Decision Tree Based on Rough Set 50 Theory", IEEE International Conference on Granular Computing, pp. 241- 244. [11] Ramadevi Yellasiri, C.R.Rao, Vivekchan Reddy (2007), “Decision Tree Induction Using Rough Set Theory – Comparative Study”, Journal of Theoretical and Applied Information Technology, pp. 110-114. [12] Sang Wook Han, Jae Yearn Kim (2007), "Rough Set-based Decision Tree using the Core Attributes Concept", Second International Conference on Innovative Computing Information and Control, pp. 298 - 301. [13] Weijun Wen (2009), “A New Method for Constructing Decision Tree Based on Rough Set Theory”, Proceedings of the International Symposium on Intelligent Information Systems and Applications Qingdao China, pp. 416-419. [14] Z. Pawlak (1998) - Rough Set Theory and Its Application to Data Analysis, Cybernetics and Systems: An International Journal 29, pp. 661-688.