Đề tài Hỗ trợ chẩn đoán tự động tổn thương xuất huyết-Tụ máu dựa vào ảnh ct não

gưỡng như sau: khi một ảnh độ xám bao gồm nhiều vùng phân biệt, histogram của nó thường sẽ có nhiều đỉnh phân biệt nhau, mỗi đỉnh ứng với một vùng và giữa 2 đỉnh liền kề nhau thường là một “thung lũng” sâu. Đáy của thung lũng này có thể được chọn để làm ngưỡng phân biệt giữa 2 vùng kề nó. Xét ảnh có histogram như trong hình 2.1, trong đó ta kí hiệu f(x,y) là độ xám của điểm (x,y). Có thể hình dung (a) là ảnh gồm một đối tượng sáng trên nền tối, và do đó histogram sẽ bao gồm 2 đỉnh rõ rệt. Rõ ràng là ta có thể tách đối tượng ra khỏi nền bằng cách chọn một ngưỡng T sao cho chia cách được 2 đỉnh này. Khi đó, mọi điểm f(x,y) nhỏ hơn T sẽ được xem là nền, trong khi những điểm có độ xám lớn hơn T sẽ được cho là thuộc về đối tượng. Hình 2-1(b) cho ta một trường hợp phức tạp hơn: histogram gồm có 3 đỉnh (chẳng hạn như 2 đối tượng sáng trên một nền màu tối). Tương tự như trên, ta có thể chọn 2 ngưỡng T1 và T2 để phân biệt 2 đối tượng trên và nền. Mặc dù vậy, phương pháp đa ngưỡng này kém tin cậy hơn so với trường hợp đơn ngưỡng. Lí do là vì ta rất khó xác lập được nhiều ngưỡng sao cho chúng 21 có thể cô lập thật hiệu quả tất cả các vùng cần quan tâm, đặc biệt là khi số lượng các đỉnh trong histogram tương ứng khá nhiều. Hình 2-1: Ảnh độ xám với: (a) 1 ngưỡng phân đoạn và (b) 2 ngưỡng phân đoạn Về mặt hình thức, phép lọc ngưỡng có thể được xem như là một phép thử của hàm T có dạng: T = T[x, y, p(x,y), f(x,y)] trong đó f(x,y) là độ xám của điểm (x,y), p(x,y) tượng trưng cho một đặc điểm cục bộ nào đó của điểm (x,y), ví dụ như trung bình độ xám của 4 điểm xung quanh (x,y) (lân cận 4 của (x,y)). Kết quả của phép lọc ngưỡng là một ảnh g(x,y) thỏa: ⎩⎨ ⎧ ≤ >= Tyxfif Tyxfif yxg ),(0 ),(1 ),( trong đó 1 tượng trưng cho một giá trị độ xám nào đó mà ta muốn gán cho đối tượng, và 0 ứng với độ xám gán cho nền. Khi T chỉ phụ thuộc vào f(x,y), ta có ngưỡng toàn cục (hình 2-1 (a)). Nếu T phụ thuộc vào cả f(x,y) và p(x,y), ta có ngưỡng cục bộ. Thêm nữa, nếu T phụ thuộc vào tọa độ của x và y, ta có ngưỡng động. 22 2.2.2 Phương pháp dựa vào biên Phương pháp phân đoạn dựa vào biên giả định rằng tại các biên vùng sẽ xảy ra sự thay đổi đột ngột của độ xám. Nhiều phương pháp đã được đề xuất nhằm tìm ra các biên trong ảnh. Một trong những phương pháp quen thuộc nhất là sử dụng toán tử gradient (tương ứng với mặt nạ Sobel như trong hình 2-2), hoặc toán tử Laplace (tương ứng với mặt nạ trong hình 2-3). Hình 2-2: Mặt nạ Sobel Hình 2-3: Mặt nạ của toán tử Laplace Kĩ thuật phân đoạn dựa vào biên không cho được kết quả tốt như mong đợi, lý do là vì thao tác tìm biên thường liên quan đến các phép toán vi phân (như 2 toán tử Gradient và Laplace đã nói ở trên), vốn rất nhạy cảm đối với nhiễu. Như vậy, cách tiếp cận dựa trên đường biên không phải sự lựa chọn tốt cho bài toán phân đoạn ảnh. 23 2.2.3 Phương pháp dựa trên vùng Phương pháp phân đoạn dựa trên vùng sử dụng các thuật toán region- growing để thực hiện phân đoạn ảnh. Thuật toán region-growing bắt đầu từ một hoặc nhiều điểm hạt giống (seed point) và sau đó lan rộng ra bằng cách kết hợp với các điểm lân cận nó theo một tiêu chuẩn tương tự nào đó. Nếu các điểm liền kề nhau là tương tự so với điểm hạt giống, nó sẽ được đánh dấu thuộc về vùng có điểm hạt giống đó. Quá trình tiếp diễn cho đến khi mọi điểm ảnh đều được gán vào một vùng nào đó. Nhiều thuật toán đã được đề xuất cho cách tiếp cận này, trong đó có thể kể đến phương pháp của Chang và Li [3]. Phương pháp của hai ông có tên gọi là phân đoạn thích nghi nhanh. Thuật toán chia ảnh thành nhiều vùng nhỏ vốn có một điểm tương đồng nào đó.. Các vùng nhỏ này sẽ được kiểm tra theo tiêu chuẩn tương tự. Nếu tiêu chuẩn này thỏa, các vùng này sẽ được nối lại để hình thành vùng lớn hơn. Quá trình cứ tiếp tục cho đến khi không thể thực hiện được nữa. Rõ ràng trong hướng tiếp cận này, có thể thấy việc chọn lựa điểm hạt giống là rất quan trọng, và có thể được thực hiện thủ công hoặc tự động. Một ví dụ cho trường hợp chọn điểm hạt giống một cách tự động là dựa vào các đỉnh của histogram. Xét ví dụ minh họa sau (hình 2-4a: một ảnh kích thước 6*6, trong đó con số trong mỗi ô chỉ độ xám của ô đó. Với điểm hạt giống bắt đầu là điểm có tọa độ (3,3) cùng tiêu chí “trị tuyệt đối của độ xám 2 điểm kề nhau không vượt quá 3”. Đầu tiên, điểm hạt giống được đưa vào vùng. Tiếp theo đó, nó kiểm tra tất cả các điểm lân cận với điều kiện đã nêu, và đưa những điểm thỏa vào vùng (hình 2-4b). Những điểm vừa được bổ sung sẽ trở thành điểm hạt giống mới, và quá trình tiếp tục cho đến khi không còn có thêm điểm nào được thêm vào nữa (hình 2-4c). 24 (a) (b) 25 Hình 2-4: Ví dụ về thuật toán Region Growing (a) ảnh ban đầu, (b) sau khi qua bước lan vùng thứ 1, (c) kết quả cuối cùng 2.2.4 Phương pháp thống kê và Bayes Phương pháp thống kê và Bayes sử dụng “không gian đặc trưng” để phân đoạn ảnh. Phương pháp này chuyển thông tin điểm ảnh thành không gian đặc trưng và tiến hành phân đoạn bằng cách sử dụng các tính chất xác suất của chúng. Phương pháp xác suất thu hút nhiều quan tâm của các nhà nghiên cứu vì chúng cho phép thực hiện các phân tích toán học cho bài toán phân đoạn thay cho những phương pháp sử dụng heuristic đã trình bày phía trên. Khuyết điểm lớn nhất của cách tiếp cận dựa trên thống kê và Bayes là độ phức tạp tính toán của chúng khá lớn. Một khó khăn khác nữa là chúng đòi hỏi một mô hình ảnh ngẫu nhiên (stochastic image model) tốt, vốn rất khó đạt được. 2.2.5 Phương pháp mạng nơ ron và logic mờ Mọi hệ thống thị giác đều cần có tốc độ nhanh, mạnh mẽ, ít nhạy cảm với nhiễu cũng như những sai sót khác ở một mức độ hợp lí. Đó chính là 26 mục tiêu chính của phương pháp phân đoạn dùng mạng nơ ron và lý thuyết tập mờ. Nhiều nghiên cứu đã dùng mạng nơ ron vào công việc phân đoạn ảnh, chẳng hạn trong [4]. Ông đã sử dụng mạng nơ ron 3 lớp, trong đó số nút ở lớp nhập được xác định theo số đặc trưng được rút ra cho mỗi pixel, số nút xuất ứng với số phân vùng của ảnh. Mạng nơ ron nhiều lớp cũng đã được dùng để phân đoạn ảnh nhiễu. Các trọng số được cập nhật sao cho chúng có thể làm giảm được độ mờ của hệ thống. Như vậy, cách tiếp cận này nhằm mục đích kết hợp các ưu điểm của tập mờ (suy luận dựa trên tính không chính xác/không hoàn chỉnh của tri thức) và ưu điểm của mạng nơ ron. 2.3 Làm mảnh biên Làm mảnh biên là một bước quan trọng và cần thiết trong nhiều bài toán. Chẳng hạn, trong vấn đề mà ta đang xem xét, có một yêu cầu đặt ra là tìm ra đường biên (và chỉ cần đường biên mà thôi) của sọ để làm mốc và tạo thuận lợi cho việc định vị những vùng khác trong não. Nói chung, các thuật toán làm mảnh sẽ liên tục xóa những điểm ở biên trong vùng đang quan tâm theo 3 ràng buộc sau đây: i. Không xóa những điểm cuối. ii. Không làm mất tính liên tục của vùng. iii. Không làm vùng đang xét bị rỗng quá mức. Sau đây là một thuật toán quen thuộc dùng để làm mảnh. Không mất tính tổng quát, có thể giả sử rằng các điểm thuộc đối tượng đang xét có giá trị bằng 1 và các điểm nền có độ xám bằng 0. Ta gọi một điểm là điểm biên (contour point) nếu điểm đó có giá trị 1 và một trong 8 điểm lân cận của nó có giá trị bằng 0 (hình 2-4). Quá trình thực hiện gồm 2 bước, bước 1 như sau: (a) 6)(2 1 ≤≤ pN (b) S(p1) = 1 (c) p2 * p4 * p6 = 0 (d) p4 * p6 * p8 = 0 27 trong đó N(p1) là tổng số điểm lân cận khác 0 của p1: N(p1) = p2 + p3 + … + p8 + p9 Hình 2-5 :Lân cận 8 của điểm p1 Và S(p1) là số lần chuyển từ 0 sang 1 trong chuỗi (theo đúng thứ tự) p2, p3, …, p7, p8, p2. Ở bước 2, ta giữ nguyên 2 điều kiện (a) và (b), nhưng thay (c) và (d) bằng (c’) và (d’) sau: (c’) p2 * p4 * p8 = 0 (d’) p2 * p6 * p8 = 0 Bước 1 được áp dụng cho tất cả mọi điểm biên trong vùng đang xét. Nếu có ít nhất 1 trong 4 điều kiện (a) – (d) bị vi phạm, ta giữ nguyên giá trị điểm ảnh đó. Ngược lại, ta đánh dấu điểm ảnh đó và sau này nó sẽ bị xóa. Lưu ý rằng ta chỉ xóa điểm ảnh khi tất cả các điểm biên đã được duyệt qua, nhờ vậy dữ liệu không bị thay đổi trong quá trình xử lý. Sau khi thực hiện xong bước 1, ta xóa tất cả các điểm đã đánh dấu và thực hiện tiếp bước 2 giống như đã thực hiện cho bước 1. Như vậy, quá trình thực hiện là một vòng lặp liên tục gồm các giai đoạn sau: i. Áp dụng bước 1 để đánh dấu điểm cần xóa. ii. Xóa các điểm đã đánh dấu. iii. Áp dụng bước 2 để đánh dấu điểm. iv. Xóa các điểm đã được đánh dấu. Thuật toán dừng khi không còn điểm nào được xóa nữa. Điều kiện (a) bị vi phạm khi điểm biên p1 có 1 hoặc 7 điểm lân cận có giá trị 1. Trường hợp 1 điểm lân cận đồng nghĩa với việc p1 là điểm cuối, và 28 do đó không thể xóa được. Tương tự, trong trường hợp p1 có 7 điểm lân cận, nếu ta xóa nó sẽ gây ra lỗ hổng trong vùng đang xét. Điều kiện (b) không thỏa khi điểm đang xét nằm trên vùng biên có độ dày bằng 1, và do đó nếu xóa nó sẽ làm mất tính liên tục của đối tượng. 2.4 Biểu diễn đường biên Cách lưu trữ ảnh thô thường thấy nhất là lưu trữ theo dạng ma trận. Đây là lưu trữ chứa đựng được nhiều thông tin nhất (dù thông tin đó ở dạng tiềm ẩn hoặc tường minh). Tuy vậy, trong trường hợp cần biểu diễn đường biên của một đối tượng, phương pháp trên sẽ có những bất tiện như tốn nhiều bộ nhớ và không thuận lợi cho xử lý. Trong phần dưới đây, ta sẽ tìm hiểu 2 phương pháp lưu trữ đường biên khá hiệu quả và có sử dụng trong chương trình. 2.4.1 Biểu diễn bằng chain -code Cách biểu diễn này dựa trên lân cận 4 và lân cận 8 của một điểm. Tùy theo vị trí tương đối của một điểm so với điểm hiện tại mà hướng của nó sẽ được mã hóa bằng 1 con số tương ứng như trong hình 2-5. Để xây dựng chain code của một đường biên, trước hết ta cần chọn 1 điểm khởi đầu, ví dụ như điểm ở góc trái trên của ảnh. Sau đó, ta duyệt lần lượt qua tất cả các điểm theo chiều ngược chiều kim đồng hồ, gán mã cho nó theo một trong 2 kiểu trong hình 2-5. Lấy ví dụ như trong hình 2-6, chain code tương ứng của nó là 5-6-5- 5-6-7-0-0-0-1-7-1-2-1-3-3-4-4-3. 29 Hình 2-6: Mã tương ứng với hướng của (a) chain code 4 hướng và (b) chain code 8 hướng Hình 2-7: Ví dụ về chain code của đường biên, ở đây ta dùng chain code lân cận 8 Chain code tỏ ra rất hữu dụng khi dùng để xác định hướng của đường biên tại một điểm, hoặc dùng để tính chu vi của vùng (xem 2.5.1). Tuy vậy, nếu xét trong vấn đề mà chúng ta đang bàn, cách biểu diễn này không phù hợp. Lí do là vì với cách biểu diễn này, thật khó có thể rút ra được các thông tin cần thiết cho quá trình xử lý, chẳng hạn như khoảng cách từ một điểm đến đường biên. 30 2.4.2 Biểu diễn bằng dòng quét (scanline) Nguyên tắc tắc rất đơn giản: xem mỗi đối tượng là một tập hợp các dòng, và thay vì lưu tất cả các điểm trong mỗi dòng, ta chỉ cần lưu chỉ số của dòng đó, cùng với điểm bắt đầu và kết thúc tương ứng trong dòng. Ví dụ: Xét ảnh trong hình 2-7, biểu diễn đường biên của nó theo dòng quét của nó là: 1 5,6 2 4,7 3 3,8 4 3,9 5 4,7 7,9 6 4,6 8,8 7 5,5 Hình 2-8: Vùng và biểu diễn dòng quét của nó 31 Nhận thấy rằng cách biểu diễn này đã khắc phục những bất lợi của phương pháp chain code, và đem đến cho ta những thuận lợi trong các phép xử lý sau (vốn được sử dụng thường xuyên trong bài): i. Tính diện tích vùng. ii. Xác định một điểm là nằm trong hay ngoài vùng. iii. Dễ dàng duyệt qua toàn bộ các điểm trong vùng. 2.5 Các đặc trưng mô tả vùng (đường kính, chu vi, diện tích…) Trong phần này ta tìm hiểu về một số đặc trưng thường được dùng để mô tả vùng. Các đặc trưng này rất hữu dụng cho việc phân lớp vùng và cung cấp nhiều thông tin quan trọng để so sánh và phân lớp vùng trong ảnh nhị phân. Hình 2-8 mô tả một vùng ảnh nhị phân điển hình. Hình 2-9: Một số đặc trưng dùng để mô tả vùng 2.5.1 Diện tích và chu vi Diện tích và chu vi là 2 trong số những đặc trưng được sử dụng nhiều nhất cho những bài toán phân lớp trong ảnh nhị phân. Diện tích của một vùng tương ứng với tổng số điểm ảnh thuộc vùng đó. Tương tự, chu vi của vùng nhị phân bằng tổng số điểm ảnh nằm trên đường biên của vùng. Đối với biên ảnh xác định bằng lân cận 4, ta có thể xuất phát từ một điểm tùy ý 32 trên biên, đếm tất cả các điểm dọc theo đường biên cho đến khi trở về điểm ban đầu. Tuy vậy, vấn đề sẽ phát sinh nếu đường biên được tạo xác định bằng lân cận 8. Khi đó, khoảng cách giữa 2 điểm kề nhau không phải lúc nào cũng bằng 1 nữa, mà sẽ là 2 . Khi đó, ta có thể sử dụng cách mô tả đường biên bằng chain code. Gọi Ne và No lần lượt là tổng số số chẵn và lẻ có trong chuỗi (theo phần 2.4.1, số chẵn ứng với trường hợp 2 điểm liên tiếp cùng cột hoặc cùng dòng, còn số lẻ ứng với trường hợp 2 điểm nằm theo đường chéo), ta ước lượng chu vi theo công thức sau: Chu vi = Ne + No 2 2.5.2 Khoảng cách xuyên tâm (radial distance) Khoảng cách xuyên tâm là khoảng cách Euclide giữa tâm khối lượng của vùng và tâm của hợp tất cả các vùng trong ảnh. Cách đơn giản nhất để ước lượng tâm vùng là dùng giá trị trung bình của tọa độ các điểm của vùng đó. Đối với ảnh nhị phân, ta có thể tính tâm khối lượng bằng cách dùng moment. Moment (i,j) của vùng R được định nghĩa như sau: ∑∑= x y ji ij yxRyx ),(μ trong đó x và y là tọa độ của các điểm ảnh trong vùng. Khi đó, tâm khối lượng có thể được tính như sau: 00 10 μ μ=x 00 01 μ μ=y Khoảng cách xuyên tâm có thể được tính bằng cách sử dụng khoảng cách Euclide de giữa tâm khối lượng của hợp tất cả các vùng và của vùng đang xét theo công thức sau: 22 )()(),( lrlre yyxxurd −+−= trong đó r và u tương ứng là vùng đang xét và vùng tổng hợp. 33 Bên cạnh đó, ta có thể sử dụng khoảng cách xuyên tâm chuẩn hóa u e R urd ),( , trong đó Ru là bán kính của vùng tổng hợp. Vì 00μ là diện tích của vùng, suy ra Ru có thể được xấp xỉ theo công thức π μ 4 00=uR , với giả định rằng vùng tổng hợp có dạng hình tròn. 2.5.3 Chiều dài trục chính và phụ Chiều dài trục chính và phụ là những đặc trưng rất quan trọng và có thể được ước lượng bằng cách sử dụng các giá trị riêng. Trước hết, một vùng sẽ được biểu diễn như là một tập các điểm {(x1, y1), (x2, y2), (x3, y3), . . . , (xn, yn)} và giả sử rằng các điểm này được biểu diễn bởi một vector ngẫu nhiên S = [x, y]. Gọi C là ma trận hiệp phương sai của vector đó: ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛= 0211 1120 μμ μμ C trong đó: ∑∑ −−= x y yyxx ))((11μ ∑∑ −= x y xx 220 )(μ ∑∑ −= x y yy 202 )(μ với x và y là tâm của vùng đang tính. Vector riêng của ma trận hiệp phương sai cho ta hướng của 2 trục chính và phụ. Chiều dài của các trục bằng với căn bậc hai của các giá trị riêng của ma trận hiệp phương sai. 34 Hình 2-10: Trục chính và trục phụ hình ellipse. 2 vector e1 và e2 là 2 vector riêng của ma trận hiệp phương sai. 2.6 Cây quyết định 2.6.1 Giới thiệu về cây quyết định Cây quyết định là một cây đồ thị trong đó mỗi nút bên trong đại diện cho một điểm quyết định và mỗi nút lá tương ứng với một nhãn (lớp) sẽ được gán cho mỗi bộ dữ liệu nhập. Mỗi nút của cây là một phép thử (so sánh) của một thuộc tính nào đó, và nhánh trổ xuống từ nút đó đại diện cho những giá trị có thể có của thuộc tính này. Để xây dựng được cây quyết định, ta cần có một tập dữ liệu được phân lớp trước (dữ liệu học). Việc xây dựng các cây quyết định chính là quá trình phát hiện ra các luật phân chia tập dữ liệu đã cho thành các lớp đã được định nghĩa trước. Việc sinh cây quyết định bao gồm hai giai đoạn: i. Xây dựng cây: • Tại thời điểm khởi đầu, tất cả các ca ( case ) dữ liệu học đều nằm tại gốc. • Các ca dữ liệu được phân chia đệ qui trên cơ sở các thuộc tính được chọn. 35 ii. Rút gọn cây: • Phát hiện và bỏ đi các nhánh chứa các điểm dị thường và nhiễu trong dữ liệu. Hầu hết các thuật toán dựa vào qui nạp hiện có đều sử dụng phương pháp của Hunt dùng để xây dựng một cây quyết định từ một tập T các ca học với các lớp được kí hiệu là {C1,C2,……Cn}. - Trường hợp 1: T chứa một hoặc nhiều ca, tất cả đều thuộc về một lớp đơn C1: Cây quyết định T là một lá định dạng lớp C1. - Trường hợp 2: T không chứa ca nào: Cây quyết định cho T là một lá, nhưng lớp được gắn với lá này phải được xác định từ các thuộc tính không thuộc T. - Trường hợp 3: T chứa các ca thuộc về một hỗn hợp các lớp: Một phép thử được lựa chọn dựa vào một thuộc tính đơn có một hoặc nhiều kết quả ( giá trị ) loại trừ lẫn nhau {O1,O2,….On}. T được phân chia thành các tập con T1, T2, ….Tn trong đó T1 chứa tất cả các ca trong T có kết quả O1 của phép thử đã chọn. Cây quyết định cho T gồm một đỉnh quyết định định danh cho phép thử, và một nhánh cho mỗi kết quả có thể có. Cơ chế xây dựng cây này được áp dụng đệ qui cho từng tập con của các ca học. Bảng 2-1 là một tập dữ liệu học của một ví dụ về thi đấu tennis với năm thuộc tính và hai lớp ( thuộc tính Ngày được sử dụng làm định danh cho các ca ). Hình 2-10 chỉ ra cách làm việc của thuật toán Hunt, một phép thử dựa trên thuộc tính đơn được chọn để khai triển đỉnh hiện hành. 36 Ngày Quang cảnh Nhiệt độ Độ ẩm ( %) Gió to Kết quả N1 Nắng 24 70 Không Thi đấu N2 Nắng 27 90 Có Không thi đấu N3 Nắng 30 85 Không Không thi đấu N4 Nắng 22 95 Không Không thi đấu N5 Nắng 20 70 Không Thi đấu N6 Nhiều mây 22 90 Có Thi đấu N7 Nhiều mây 28 75 Không Thi đấu N8 Nhiều mây 18 65 Có Thi đấu N9 Nhiều mây 28 75 Không Thi đấu N10 Mưa 21 80 Có Không thi đấu N11 Mưa 18 70 Có Không thi đấu N12 Mưa 24 80 Không Thi đấu N13 Mưa 20 80 Không Thi đấu N14 Mưa 21 96 Không Thi đấu Bảng 2-1: Dữ liệu minh họa cho cây quyết định Hình 2-11: Minh họa phương pháp của Hunt 37 2.6.2 Thuật toán ID3 Thuật toán ID3 ( Quinlan86 ) là một trong những thuật toán xây dựng cây quyết định sử dụng information gain để lựa chọn thuộc tính phân lớp đối tượng. Nó xây dựng cây theo cách từ trên xuống, bắt đầu từ một tập các đối tượng và đặc tả của các thuộc tính. Tại mỗi đỉnh của cây, một thuộc tính có information gain lớn nhất sẽ được chọn để phân chia tập đối tượng. Quá trình này được thực hiện một cách đệ qui cho đến khi một tập đối tượng tại một cây con đã cho trở nên thuần nhất, tức là nó chỉ chứa các đối tượng thuộc về cùng một lớp. Lớp này sẽ trở thành một lá của cây. Việc lựa chọn một thuộc tính nào cho phép thử là rất quan trọng. Nếu chọn không thích hợp, chúng ta có thể có một cây rất phức tạp. Ví dụ, nếu ta chọn thuộc tính Nhiệt độ làm gốc cây thì cây quyết định sẽ có hình dạng như trong hình 2-11. Nhưng nếu chọn thuộc tính Quang cảnh làm gốc thì ta lại có một cây quyết định tất đơn giản như đã chọn trong hình 2-10. Vậy nên chọn thuộc tính nào là tốt nhất? Thông thường việc chọn thuộc tính đều dựa vào một độ đo gọi là Entropy Gains hay còn gọi là Information Gains của các thuộc tính. Entropy của một thuộc tính được tính toán từ các thuộc tính phân lớp. Đối với thuộc tính rời rạc, cần phải có các thông tin phân lớp của từng giá trị thuộc tính. Lớp Giá trị thuộc tính Thi đấu Không thi đấu Nắng 2 3 Nhiều mây 4 0 Mưa 3 2 Bảng 2-2: Thông tin phân bố thuộc tính quang cảnh 38 Lớp Giá trị thuộc tính Phép thử nhị phân Thi đấu Không thi đấu 65 1 0 > 8 5 70 3 1 > 6 4 75 5 1 > 4 4 78 5 1 > 4 4 80 7 2 > 2 3 85 7 3 > 2 2 90 8 4 > 1 1 95 8 5 > 1 0 96 9 5 > 0 0 Bảng 2-3: Thông tin phân bố lớp của thuộc tính Độ ẩm Bảng 2-2 cho thấy thông tin phân lớp của thuộc tính Quang cảnh. Đối với một thuộc tính liện tục. chúng ta phải xét phép thử nhị phân đối với tất cả các giá trị khác nhau của thuộc tính. Bảng 2-3 chỉ ra thông tin phân lớp của thuộc tính Độ ẩm. 39 Một khi đã thu nhận được các thông tin phân lớp của tất cả các thuộc tính, chúng ta sẽ tính Entropy. Một thuộc tính với Entropy lớn nhất sẽ được chọn làm một phép thử để khai triển cây. 2.6.2.1 Hàm Entropy Hàm Entropy xác định tính không thuần khiết của một tập các ca dữ liệu bất kỳ. Chúng ta gọi S là tập các ca dương tính ( ví dụ Thi đấu ) và âm tính ( ví dụ Không thi đấu ). P(+) là tỉ lệ các ca dương tính S, P(-) là tỉ lệ âm tính S. Entropy(S) = -P(+)log 2 P(+) – P(-)log 2 P(-) Ví dụ 1. Trong Bảng 2-1 của ví dụ thi đấu tennis, tập S có 9 ca dương và 5 ca âm ( ký hiệu là [9+,5-]). Entropy(S) = Entropy([9+,5-]) = - 14 9 log 2 14 9 - 14 5 log 2 14 5 = 0.940 Hình 2-12: Một cây quyết định chọn nhiệt độ làm gốc Nhận xét. Entropy bằng 0 nếu tất cả các ca trong S đều thuộc về cùng một lớp. Chẳng hạn như, nếu tất cả các ca đều dương thì P(+) = 1 và P(-) = 0, do vậy: Entropy(S) = -1log 2(1) – 0log 2 (0) = 0 40 Entropy bằng 1 nếu tập S chứa số ca dương và âm bằng nhau. Nếu số các ca này khác nhau thi Entropy nằm giữa 0 và 1. Trường hợp tổng quát, nếu S bao gồm c lớp thì Entropy của S được tính bằng công thức sau: Entropy(S) = ∑ -P = n i 1 ilog 2 Pi trong đó Pi là tỉ lệ thuộc tính I trong tập S. 2.6.2.2 Độ đo (Informatic Gain) Đo mức độ hiệu quả của một thuộc tính trong bài toán phân lớp dữ liệu. Đó chính là sự rút gọn mà ta mong đợi khi phân chia các ca dữ liệu theo thuộc tính này. Nó được tính theo công thức sau đây: Gains(S,A) = Entropy(S) - ∑ )( AValue r S S Entropy(S) trong đó Value(A) là tập tất cả các giá trị có thể có đối với thuộc tính A và Sr là tập con của S mà A có giá trị là v. Ví dụ 2. Value(Gió to) = { true,false},S=[9+,5-] Strue là đỉnh con với giá trị là “true”, bằng [2+,3-] Sfalse là đỉnh con với giá trị là “false”, bằng [7+,2-] Gaint(S,Gió to) = Entropy(S) - ∑ )( AValue r S S Entropy(S) = Entropy(S) - 14 5 * Entropy(Strue) - 14 9 * 41 Entropy(Sfalse) = 0.940 - 14 5 *0.97 - 14 9 *0.764 = 0.1024 Tương tự như vậy, ta có thể tính được độ đo cho các thuộc tính còn lại của ví dụ trong Bảng 1. Đối với thuộc tính Độ ẩm. ta lấy độ ẩm 75% để chia các ca thành hai phần, một phần ứng với các ca có độ ẩm ≤ 75% được gọi là độ ẩm Bình thường ( [5+,1-] ), phần còn lại được gọi là có độ ẩm Cao ( [4+,4-] ). Còn đối với thuộc tính Nhiệt độ, ta sẽ chia thành ba mức, các ngày có nhiệt độ nhỏ hơn 210 được gọi là Lạnh(4 ngày), các ngày có nhiệt độ lớn hơn hay bằng 210 đến nhỏ hơn hoặc bằng 270 được gọi là Ấm (6 ngày), và còn lại là những ngày có nhiệt độ lớn hơn hoặc bằng 270 được gọi là Nóng (4 ngày). Gain(S,Quang cảnh) = 0.246 Gain(S,Gió to) = 0.1024 Gain(S,Nhiệt độ) = 0.029 Gain(S,Độ ẩm) = 0.045 Từ đây ta thấy rằng độ đo của S đối với thuộc tính Quang cảnh là lớn nhất trong số 4 thuộc tính. Như vậy, có thể quyết định chọn Quang cảnh làm thuộc tính đầu tiên khai triển cây, Hình 2-12 là khai triển của cây quyết định theo thuộc tính Quang cảnh. Tương tự như vậy, ta có thể tiến hành triển khai các nút ở mức tiếp theo: Snắng = {N1, N2, N3, N4, N5} Entropy(Snắng) = - 5 2 log 2 5 2 - 5 3 log 2 5 3 = 0.970 Gain(Snắng , Độ ẩm) = 0.970 - 5 3 *0.0 - 5 2 *0.0 = 0.970 42 Gain(Snắng , Nhiệt độ) = 0.970 - 5 2 *0.0 - 5 2 *1.0 - 5 1 *0.0 = 0.570 Gain(Snắng , Gió to) = 0.970 - 5 2 *1.0 - 5 3 *0.918= 0.019 Từ các giá trị của Entropy Gain, ta thấy Độ ẩm là thuộc tính tốt nhất cho đỉnh nằm dưới nhánh Nắng của thuộc tính Quang cảnh. Tiếp tục quá trình trên cho tất cả các đỉnh và sẽ dừng khi không còn đỉnh nào có thể khai triển được nữa. Cây kết quả sẽ có dạng như phần c) của hình 2-12. 2.7 Thông tin tương hỗ Cho trước một biến ngẫu nhiên X = {x1, …, xn}. Ta định nghĩa công thức tính entropy Shannon như sau: ∑ = −= n i ii ppXH 1 log)( với pi = Pr[X = xi] và n là lực lượng của X. Độ đo entropy này thể hiện độ thông tin trung bình hay là độ không chắc chắn của biến ngẫu nhiên. Bây giờ ta xét thêm một biến ngẫu nhiên Y = {y1, …, yn}. Ta định nghĩa entropy có điều kiện với p∑∑ = = −= m j n i jiij ppYXH 1 1 |log)|( i|j = Pr[X = xi|Y=yj ] là xác suất có điều kiện và entropy hợp với p∑∑ = = −= n i m j ijij ppYXH 1 1 log),( ij = Pr[X = xi, Y=yj]. Thông tin tương hỗ giữa X và Y được xác định theo công thức: ∑∑ = = = n i m j ji ij ij qp p pYXI 1 1 log),( Dễ thấy I(X,Y) = H(X) – H(X|Y) = H(Y) – H(Y|X) nên còn được gọi là thông tin chia sẻ giữa X và Y. 43 Một kết quả cơ bản của lý thuyết thông tin là bất đẳng thức về xử lý thông tin có thể được diễn tả dưới dạng sau: nếu X -> Y -> Z là chuỗi Markov, nói cách khác p(x,y,z) = p(x)p(y|x)p(z|y) thì: ),(),( ZXIYXI ≥ Kết quả này nói lên rằng không tồn tại cách xử lý Y nào, dù là ngẫu nhiên hay chủ ý, có thể làm tăng thông tin Y chứa về X. Ở phần 3.4, ta sẽ bàn về cách sử dụng thông tin tương hỗ này vào bài toán phân vùng ảnh. 2.8 Học dựa vào sự trình diễn Theo [4], một vấn đề quan trọng khi xây dựng những hệ thống dựa vào tri thức là giai đoạn thu thập tri thức. Đây là một thách thức lớn và là một đề