chương 1 đã đề cập đến những bước quan trọng diễn ra trong quá trình khai phá dữ liệu như chuẩn bị dữ liệu, mô hình hóa dữ liệu, xử lý và đánh giá, cuối cùng là triển khai áp dụng thực tế. Trong chương này cũng đã đề cập đến một số phương pháp cơ bản để thực hiện kiểm thử phần mềm cũng như phân tích đặc điểm, hiệu quả, phạm vi áp dụng của từng phương pháp. Kỹ thuật khai phá dữ liệu được chọn áp dụng trong luận văn là kỹ thuật phân lớp dữ liệu và phương pháp kiểm thử được chọn là phương pháp kiểm thử hộp trắng. Cụ thể hơn là phương pháp kiểm thử đường thi hành hay còn gọi là kiểm thử luồng điều khiển.
e 10 CHƯƠNG 2: PHÂN LỚP DỮ LIỆU DỰA TRÊN NAIVE BAYES VÀ CÂY QUYẾT ĐỊNH J48 Trong chương này, luận văn sẽ nêu lên hai thuật toán chính sử dụng trong luận văn đó là Naïve Bayes và J48. Nội dung chính của chương bao gồm khái niệm, thuật toán và áp dụng vào bài toán phân lớp dữ liệu nói chung.1 Kỹ thuật Naive Bayes cho phân lớp dữ liệu 2.1 Một số khái niệm cơ bản Định lý Bayes cho phép tính xác xuất xảy ra của sự kiện ngẫu nhiên A khi biết sự kiện liên quan B đã xảy ra. Xác suất này được ký hiệu là 𝑃(𝐴|𝐵), đọc là “xác suất của 𝐴 nếu có 𝐵”. Đại lượng này được gọi là xác suất có điều kiện hay xác suất hậu nghiệm vì nó được rút ra từ giá trị được cho của 𝐵.
Theo định lý Bayes, xác suất xảy ra 𝐴 khi biết 𝐵 sẽ phụ thuộc vào 3 yếu tố sau: Xác suất xảy ra 𝐴 mà không quan tâm đến 𝐵. Ký hiệu là 𝑃(𝐴) và đọc là xác suất của 𝐴. Đây còn được gọi là xác suất tiên nghiệm – nghĩa là nó không quan tâm đến bất kỳ thông tin nào của 𝐵 (prior). Xác suất xảy ra 𝐵 mà không quan tâm đến 𝐴.
Ký hiệu là 𝑃(𝐵) và đọc là xác suất của B. Đại lượng này là hằng số chuẩn hóa, vì nó không phụ thuộc vào sự kiện 𝐴 đang muốn biết (evidence). Xác suất xảy ra 𝐵 khi biết 𝐴 xảy ra. Ký hiệu 𝑃(𝐵|𝐴) và đọc là xác suất của 𝐵 nếu có 𝐴.
Đại lượng này là khả năng xảy ra 𝐵 khi biết 𝐴 đã xảy ra. Xác suất có điều kiện mà 𝐴 xảy ra khi đã biết 𝐵. Xác suất này còn được gọi là xác suất sau (likelihood). Khi biết ba đại lượng kể trên.
Xác suất của 𝐴 khi biết 𝐵 được cho bởi công thức: (Công thức định lý Bayes) (posterior). 𝑃(𝐵|𝐴)𝑃(𝐴) 𝑙𝑖𝑘𝑒𝑙𝑖ℎ𝑜𝑜𝑑 ∗ 𝑝𝑟𝑖𝑜𝑟 𝑃(𝐴|𝐵) = = 𝑃(𝐵) 𝑒𝑣𝑖𝑑𝑒𝑛𝑐𝑒 Bài toán thực tế trong học máy sử dụng định lý Bayes: Vấn đề cần làm là tìm hiểu mô hình của chúng ta từ một tập hợp các thuộc tính nhất định (dựa vào tập dữ e 11 liệu đặc trưng đã quan sát được), mỗi bộ dữ liệu lại có một biến đại diện cho tập dữ liệu đó. Sử dụng định lý Bayes để xây dựng xác suất của biến dữ đoán đáp ứng được bộ dữ liệu ban đầu và đưa ra tập các thuộc tính mới. Giả thiết cho rằng số thuộc tính là 𝑛, số giá trị nó có thể có là 2 (đú𝑛𝑔 ℎ𝑜ặ𝑐 𝑠𝑎𝑖).
Để huấn luyện phân loại và áp dụng định lý Bayes, ta cần tính toán 𝑃(𝐵|𝐴), theo đó số lượng phép tính cần tính là xấp xỉ 2 ∗ (2𝑛 − 1) các tham số cho mô hình này. Có thể nhận thấy con số trên là một vấn đề khá lớn trong những bài toán có nhiều thuộc tính. Để giải quyết bài toán này, ta sẽ cần áp dụng thuật toán Naïve Bayes. Naive Bayes được nghiên cứu rộng rãi từ những năm 1950, ứng dụng và đưa vào thực tế những năm 1960.
Naive Bayes được xây dựng dựa trên định lý Bayes về lý thuyết xác suất để đưa ra các dự đoán cũng như phân loại dữ liệu dựa trên các dữ liệu quan sát được. Hiện nay thuật toán dược áp dụng nhiều trong lĩnh vực học máy dùng để đưa ra các dự đoán dựa trên tập dữ liệu thu thập được. Nó thuộc bài toán học dựa trên mẫu có trước. Có một số giả định được thực hiện trong Naïve Bayes.
Ngay cả khi những giả định này bị vi phạm một chút thì nó vẫn hoạt động rất tốt. Giả định đầu tiên cũng được coi là khá quan trọng khi thực thi Naïve Bayes là tất cả các biến ngẫu nhiên đầu vào phải độc lập với nhau và được lấy từ một phân phối tương tự nhau. Giả định thứ hai là tất cả những biến ngẫu nhiên kể trên đều có điều kiện độc lập. Trên thực tế, đối với các mô hình xác suất khác nhau mà có những phương pháp phân loại dựa trên Naïve Bayes khác nhau để có kết quả tốt nhất.
Thực tế cho thấy, một báo cáo năm 2006 đưa ra rằng phân loại Bayes vượt trội hơn so với các phương pháp khác như cây (trees) hoặc rừng ngẫu nhiên (random forests).2 Kỹ thuật Naïve Bayes Naïve Bayes là kỹ thuật phân loại phổ biến trong học máy có giám sát. Ý tưởng chính của kỹ thuật này dựa vào xác suất có điều kiện giữa từ hay cụm từ và nhãn phân loại để dự đoán văn bản mới cần phần loại thuộc lớp nào. Naïve Bayes e 12 được ứng dụng nhiều trong giải quyết các bài toán phân loại văn bản [6]; xây dựng bộ lọc thư rác tự động [7],[8]; hay trong bài toán khai phá quan điểm [9],[10] bởi tính dễ hiểu, đễ triển khai cũng như độ chính xác tốt. Ý tưởng cơ bản của cách tiếp cận Naïve Bayes là sử dụng xác suất có điều kiện giữa các đặc trưng và nhãn để dự đoán xác suất nhãn của một văn bản cần phân loại.
Điểm quan trọng của phương pháp này chính là ở chỗ giả định rằng sự xuất hiện của tất cả các đặc trưng trong văn bản đều độc lập với nhau. Giả định đó làm cho việc tính toán Naïve Bayes hiệu quả và nhanh chóng hơn các phương pháp khác vì không sử dụng việc kết hợp các đặc trưng để đưa ra phán đoán nhãn. Kết quả dự đoán bị ảnh hưởng bởi kích thước tập dữ liệu, chất lượng của không gian đặc trưng… Thuật toán Naïve Bayes dựa trên định lý Bayes được phát biểu như sau: 𝑃(𝐶𝑘 )𝑃(𝒙|𝐶𝑘 ) 𝑃(𝐶𝑘 |𝒙) = 𝑃(𝒙) Áp dụng trong bài toán phân loại, các dữ kiện gồm có: D: tập dữ liệu huấn luyện đã được vec-tơ hóa dưới dạng 𝑥⃗ = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) Ci: phân loại i, với i = {1,2,…,m}. Các thuộc tính độc lập điều kiện đôi một với nhau.
Theo định lý Bayes: 𝑃(𝑋|𝐶𝑖 )𝑃(𝐶𝑖 ) 𝑃(𝐶𝑖 |𝑋 ) = 𝑃(𝑋) Theo tính chất độc lập điều kiện: 𝑛 𝑃(𝑋 |𝐶𝑖 ) = ∏ 𝑃(𝑥𝑘 |𝐶𝑖 ) 𝑘=1 Trong đó: 𝑃(𝐶𝑖 |𝑋) là xác suất thuộc phân loại i khi biết trước mẫu X. 𝑃(𝐶𝑖 ) xác suất là phân loại i. 𝑃(𝑥𝑘 |𝐶𝑖 ) xác suất thuộc tính thứ k mang giá trị xk khi đã biết X thuộc phân loại i. e 13 Thuật toán Naïve Bayes: Input : Bộ dữ liệu đã huấn luyện Dữ liệu đầu vào ví dụ ở bài toán này là một ca kiểm thử (testcase) Output : Nhãn phân loại của ca kiểm thử đầu vào Bước 1: Huấn luyện Naïve Bayes (dựa vào tập dữ liệu), tính 𝑃(𝐶𝑖 ) và 𝑃(𝑥𝑘 |𝐶𝑖 ) Bước 2: Phân loại 𝑋 𝑛𝑒𝑤 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ), ta cần tính xác suất thuộc từng phân loại khi đã biết trước Xnew.
Xnew được gán vào lớp có xác suất lớn nhất theo công thức 𝑛 max (𝑃(𝐶𝑖 ) ∏ 𝑃(𝑥𝑘 |𝐶𝑖 )) 𝐶𝑖 ∈𝐶 𝑘=1 2.3 Phân lớp dữ liệu với Naïve Bayes Khi áp dụng thuật toán Naïve Bayes vào bài toán phân lớp thực tế, để ước tính các tham số phù hợp với phân phối của đối tượng cần phân lớp mười ta sẽ phải giả định những phân phối các tính năng và được gọi là mô hình sự kiện của bài toán phân lớp dữ liệu với Naïve Bayes. Tùy thuộc bộ dữ liệu đầu vào để sử dụng những phân phối phù hợp nhất. 1: Naive Bayes trong bài toán phân lớp - Gaussian Naïve Bayes: Mô hình này sử dụng phân phối chuẩn Gaussian, được áp dụng chủ yếu trong bài toán có dữ liệu là các biến liên tục. Với mỗi chiều dữ liệu 𝑖 và một phân lớp 𝑐, 𝑥𝑖 tuân theo một phân phối chuẩn (phân phối Gaussian) có kỳ vọng 𝜇𝑐𝑖 và phương sai 𝜎𝑐𝑖2 : (𝑥𝑖 −𝜇𝑐𝑖 )2 1 − 2 𝑃(𝑥𝑖 |𝑐 ) = 𝑃(𝑥𝑖 |𝜇𝑐𝑖 , 𝜎𝑐𝑖2 ) = 𝑒 2𝜎𝑐𝑖 √2𝜋𝜎𝑐𝑖2 - Multinomoal Naïve Bayes: Mô hình này chủ yếu được sử dụng trong bài toán phân loại văn bản mà các vector tính năng (features) được biểu diễn bởi một vector có cùng độ dài 𝑑, các vector này là tập từ điển của văn bản.
Giá trị của phần tử thứ 𝑖 trong mỗi vector chính là số lần từ thứ 𝑖 xuất hiện trong văn bản đó. Khi đó, giá trị 𝑃(𝑥𝑖 |𝑐) được tính bằng công thức sau: 𝑁𝑐𝑖 𝑃(𝑥𝑖 |𝑐 ) = 𝑁𝑐 e 15 Trong đó: 𝑁𝑐𝑖 là tổng số lần từ thứ 𝑖 xuất hiện trong các văn bản của phân lớp thứ 𝑐, nó được tính là tổng các thành phần thứ 𝑖 của các vector tính năng ứng với phân lớp 𝑐. 𝑁𝑐 là tổng số từ (kể cả lặp) xuất hiện trong phân lớp thứ 𝑐. Nói cách khác, nó bằng tổng độ dài của toàn bộ các văn bản thuộc phân lớp 𝑐.
Hạn chế của phương pháp này là nếu có một từ mới chưa bao giờ xuất hiện trong phân lớp 𝑐 thì biểu thức kể trên sẽ có giá trị bằng 0, điều này dẫn đến kết quả của bài toán không còn chính xác nữa. - Bernoulli Naïve Bayes: Mô hình này được áp dụng cho các loại dữ liệu mà mỗi thành phần là một giá trị 0 hoặc 1. Khi đó, 𝑃(𝑥𝑖 |𝑐 ) được tính bằng công thức sau: 𝑃(𝑥𝑖 |𝑐 ) = 𝑃(𝑖 |𝑐 )𝑥𝑖 (1 − 𝑃(𝑖|𝑐 )1−𝑥𝑖 ) Với 𝑃(𝑖 |𝑐 ) là xác suất từ thứ 𝑖 xuất hiện trong phân lớp thứ 𝑐.2 Kỹ thuật cây quyết định J48 2.1 Cây quyết định Học bằng cây quyết định là một phương pháp thông dụng trong khai phá dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây.
Trong đó, các lá đại diện cho các phân loại còn cành đại diện cho các kết hợp của các thuộc tính dẫn tới phân loại đó. Một cây quyết định có thể được học bằng cách chia tập hợp nguồn thành các tập con dựa theo một kiểm tra giá trị thuộc tính. Quá trình này được lặp lại một cách đệ quy cho mỗi tập con dẫn xuất. Quá trình đệ quy hoàn thành thì không thể tiếp tục thực hiện việc chia tách được nữa.