Tài liệu áp dụng kĩ thuật khai phá dữ liệu cho phân lớp các ca kiểm thử phần mềm

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- LÊ LÊ NA ÁP DỤNG KĨ THUẬT KHAI PHÁ DỮ LIỆU CHO PHÂN LỚP CÁC CA KIỂM THỬ PHẦN MỀM LUẬN VĂN THẠC SĨ KỸ THUẬT (Theo định hướng ứng dụng) HÀ NỘI - 2019 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- LÊ LÊ NA ÁP DỤNG KĨ THUẬT KHAI PHÁ DỮ LIỆU CHO PHÂN LỚP CÁC CA KIỂM THỬ PHẦN MỀM Chuyên ngành: Hệ thống thông tin Mã số: 8.48.01.04 NGƯỜI HƯỚNG DẪN KHOA HỌC : PGS.TS TRẦN ĐÌNH QUẾ HÀ NỘI - 2019 i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ nghiên cứu nào khác. Hà Nội, ngày tháng Tác giả luận văn Lê Lê Na năm ii LỜI CẢM ƠN Để có thể hoàn thành luận văn thạc sĩ một cách hoàn chỉnh, bên cạnh sự nỗ lực của bản thân thì phần quan trọng là sự hướng dẫn hỗ trợ nhiệt tình của quý Thầy Cô cũng như sự ủng hộ động viên tinh thần của gia đình bạn bè, đồng nghiệp trong suốt thời gian học tập nghiên cứu và thực hiện luận văn thạc sĩ. Tôi xin trân trọng bày tỏ lòng biết ơn sâu sắc tới PGS.TS Trần Đình Quế, người đã hết lòng giúp đỡ và tạo mọi điều kiện tốt nhất cho tôi hoàn thành luận văn này. Xin chân thành bày tỏ lòng biết ơn đến toàn thể quý Thầy Cô trong Khoa Công nghệ thông tin và Khoa Sau đại học Học viện Công nghệ Bưu chính Viễn thông đã tận tình truyền đạt những kiến thức quý báu cũng như tạo mọi điều kiện thuận lợi nhất cho tôi trong suốt quá trình học tập nghiên cứu và cho đến khi thực hiện đề tài luận văn. Tôi xin chân thành cảm ơn các đồng nghiệp công ty đã tạo điều kiện để tôi được tiến hành nghiên cứu, cung cấp các thông tin đầy đủ và trung thực cho nghiên cứu này, luôn tạo điều kiện, quan tâm và động viên tôi hoàn thành luận văn. Cuối cùng, tôi xin chân thành cảm ơn đến gia đình, các anh chị và các bạn đồng nghiệp đã hỗ trợ cho tôi rất nhiều trong suốt quá trình học tập, nghiên cứu và thực hiện đề tài luận văn thạc sĩ một cách hoàn chỉnh. Hà Nội, ngày tháng Tác giả luận văn Lê Lê Na năm iii MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ............................................................................................................ ii DANH MỤC BẢNG ...................................................................................................v DANH MỤC HÌNH VÀ BIỂU ĐỒ .......................................................................... vi MỞ ĐẦU .....................................................................................................................1 CHƯƠNG 1: KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN PHÂN LỚP CÁC CA KIỂM THỬ ............................................................................................................................3 1.1 Khai phá dữ liệu .................................................................................................3 1.1.1 Tại sao lại cần khai phá dữ liệu ...................................................................3 1.1.2 Khái niệm ....................................................................................................3 1.1.3 Quá trình khai phá dữ liệu: ..........................................................................4 1.1.4 Các bài toán thông dụng trong Khai phá dữ liệu: .......................................5 1.2 Kỹ thuật kiểm thử phần mềm ............................................................................6 1.2.1 Một số phương thức thiết kế kiểm thử ........................................................6 1.2.2 Ví dụ thử nghiệm .........................................................................................7 1.3 Kết luận .................................................................................................................9 CHƯƠNG 2: PHÂN LỚP DỮ LIỆU DỰA TRÊN NAIVE BAYES VÀ CÂY QUYẾT ĐỊNH J48 ....................................................................................................10 2.1 Kỹ thuật Naive Bayes cho phân lớp dữ liệu ....................................................10 2.1.1 Một số khái niệm cơ bản ...........................................................................10 2.1.2 Kỹ thuật Naïve Bayes ................................................................................11 2.1.3 Phân lớp dữ liệu với Naïve Bayes .............................................................13 2.2 Kỹ thuật cây quyết định J48 ............................................................................15 2.2.1 Cây quyết định...........................................................................................15 2.2.2 Thuật toán ID3: .........................................................................................17 2.2.4 Phân lớp dữ liệu dựa trên J48 ....................................................................19 2.3 Kết luận ............................................................................................................20 CHƯƠNG 3: PHÂN LOẠI CÁC CA KIỂM THỬ, THỬ NGHIỆM VÀ ĐÁNH GIÁ ...................................................................................................................................21 iv 3.1 Phát biểu bài toán .............................................................................................21 3.2 Xây dựng dữ liệu .............................................................................................21 3.2.1 Giới thiệu về file arff: ................................................................................21 3.2.2 Xây dựng ứng dụng ...................................................................................22 3.2.3 Sinh các ca kiểm thử .................................................................................24 3.2.4 Xây dựng bộ dữ liệu và tiền xử lý. ............................................................27 3.3 Thống kê dữ liệu ..............................................................................................28 3.4 Thử nghiệm và đánh giá ..................................................................................29 3.4.1 Sử dụng Weka để phân loại .......................................................................29 3.4.2 Sử dụng thuật toán Naïve Bayes ...............................................................31 3.4.3 Sử dụng thuật toán J48 ..............................................................................35 3.5 Đánh giá, so sánh .............................................................................................39 3.6 Kết luận ............................................................................................................42 KẾT LUẬN ...............................................................................................................43 TÀI LIỆU THAM KHẢO .........................................................................................44 v DANH MỤC BẢNG Bảng 1.1: Các ca kiểm thử phủ cấp 2..........................................................................9 Bảng 3.1: Tổng quan ứng dụng máy tính bỏ túi .......................................................22 Bảng 3.2: Hoạt động của từng hàm trong ứng dụng .................................................23 Bảng 3.3: Luồng thực thi của ứng dụng ....................................................................24 Bảng 3.4: Hướng dẫn sử dụng randoop ....................................................................25 Bảng 3.5 : Kết quả chạy Naïve Bayes với cross-validation ......................................32 Bảng 3.6 : Kết quả chạy Naïve Bayes với kỹ thuật Percentage Split .......................34 Bảng 3.7 : Kết quả J48 với cross validation..............................................................36 Bảng 3.7: Kết quả J48 với Percentage split ..............................................................38 Bảng 3.8: So sánh Naïve Bayes và J48 với cross validation ....................................39 Bảng 3.9: So sánh Naïve Bayes và J48 với percentage split ....................................40 vi DANH MỤC HÌNH VÀ BIỂU ĐỒ Hình 1.1 Các bước của quá trình phát triển tri thức trong cơ cở dữ liệu ....................3 Hình 2. 1: Naive Bayes trong bài toán phân lớp .......................................................14 Hình 2. 2: Cây quyết định và luồng thực hiện ..........................................................16 Hình 2. 3: Ví dụ về bài toán phân lớp sử dụng cây quyết định J48 ..........................20 Hình 3.1: Mẫu file arff chuẩn dựa trên bộ dữ liệu iris ..............................................22 Hình 3.2: Thao tác với randoop bước 2 ....................................................................25 Hình 3.3: Thao tác với randoop bước 3 ....................................................................25 Hình 3.4: Kết quả chạy với randoop. ........................................................................25 Hình 3.5: Kết quả khi chạy Coverage với công cụ hỗ trợ là Eclemma.....................26 Hình 3.6: Kết quả JaCoCo Metrics. ..........................................................................27 Hình 3.7: Bộ dữ liệu huấn luyện mẫu .......................................................................27 Hình 3.9: Tiền xử lý dữ liệu bằng Weka ...................................................................28 Hình 3.10: Các bước thực hiện đối với Weka ...........................................................31 Hình 3.11: Kết quả thử nghiệm Naïve Bayes với n=5 ..............................................31 Hình 3.12: Kết quả thử nghiệm Naïve Bayes với n=10 ............................................32 Hình 3.14: Kết quả chạy Naïve Bayes với tỷ lệ phân chia 50% ...............................33 Hình 3.16: Kết quả chạy Naïve Bayes với tỷ lệ phân chia 75% ...............................34 Hình 3.17: Kết quả chạy Naïve Bayes với tỷ lệ phân chia 80% ...............................34 Hình 3.18: Kết quả J48 với n=5 ................................................................................36 Hình 3.19: Kết quả J48 với n=10 ..............................................................................36 Hình 3.21: Kết quả J48 với tỷ lệ phân chia 50% ......................................................37 Hình 3.23: Kết quả J48 với tỷ lệ phân chia 75% ......................................................38 Hình 3.24: Kết quả J48 với tỷ lệ phân chia 80% ......................................................38 vii Biểu đồ 3.1: Lược đồ Naïve Bayes với cross-validation ..........................................33 Biểu đồ 3.2: Lược đồ Naïve Bayes với Percentage Split ..........................................35 Biểu đồ 3.3: Kết quả J48 với cross validation ..........................................................37 Biểu đồ 3.4: Kết quả J48 với Percentage split ..........................................................39 Biểu đồ 3.5: So sánh Naïve Bayes và J48 kỹ thuật Cross-validation .......................40 Biểu đồ 3.6: So sánh Naïve Bayes và J48 với Percentage Split ...............................41 1 MỞ ĐẦU Cùng với sự phát triển mạnh mẽ của công nghệ thông tin, các sản phẩm phần mềm sử dụng nguồn dữ liệu lớn xuất hiện không ngừng. Kĩ thuật phần mềm là lĩnh vực nghiên cứu liên quan đến thiết kế, triển khai và sửa đổi để xây dựng một phần mềm phù hợp và duy trì lâu dài. Kiểm thử là một trong những giai đoạn chính trong quy trình phát triển phần mềm, là một trong những giai đoạn không thể thiếu trong vòng đời phát triển phần mềm. Kiểm thử thường tiến hành trên quy mô lớn để tìm ra lỗi trong phần mềm và cũng là để kiểm tra các kết quả thực tế của phần mềm đúng với mong muốn thiết kế hay không. Điều này đòi hỏi phải xây dựng các trường hợp thử nghiệm mà khai thác hết tất cả các trường hợp có thể của phần mềm. Sẽ là rất rủi ro và phức tạp nếu tất cả các trường hợp thử nghiệm đều được thực hiện bằng tay bởi vậy việc tạo mô hình thử nghiệm tự động đã ra đời nơi mà các trường hợp thử nghiệm được xây dựng một cách tự động. Nhưng vấn đề với các tiếp cận trên là nếu phần mềm được xây dựng trên hàng ngàn dòng mã thì việc thực hiện tất cả các trường hợp thử nghiệm sẽ mất rất nhiều thời gian có thể mất vài ngày để hoàn thành. Khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới. Trong kiểm thử phần mềm, khai phá dữ liệu cũng đã trở nên vô cùng phổ biến, giúp phân tích và khai thác dữ liệu, chia nhỏ các vùng thử nghiệm từ đó giúp tiết kiệm thời gian cũng như tăng độ chính xác của từng trường hợp thử nghiệm. Xác định các ca kiểm thử, phân loại và giản lược các ca kiểm thử là những vấn đề đã được nhiều quan tâm nghiên cứu ([1],[2],[3],[4],[5]...[15]) Với mục đích đưa những tiến bộ công nghệ phục vụ cho công việc hằng ngày, luận văn đã chọn đề tài tìm hiểu "Áp dụng kĩ thuật khai phá dữ liệu cho phân lớp các ca kiểm thử phần mềm" . Trong phạm vi luận văn sẽ trình bày về cách xử lý bài toán khi kiểm thử chương trình của một máy tính bỏ túi sử dụng các phép toán cộng, trừ, nhân, chia.... mặc dù khá đơn giản nhưng các trường hợp kiểm thử đặt ra cũng vô cùng phức tạp và số lượng testcases là khá nhiều. Luận văn tập trung áp dụng thuật toán Naive 2 Bayes, thuật toán cây quyết định J48 để phân tích các ca kiểm thử nhằm tối giản để tránh mất quá nhiều thời gian, tăng hiệu quả làm việc cũng như chất lượng phần mềm. Ngoài phần mở đầu và kết luận, luận văn bao gồm 3 chương chính: Chương 1: Khai phá dữ liệu và bài toán phân lớp các ca kiểm thử Chương này trình bày chung về khái niệm khai phá dữ liệu và một số ý về bài toán phân lớp. Giới thiệu một số ví dụ về các trường hợp kiểm thử và độ bao quát của từng trường hợp kiểm thử. Chương 2: Phân lớp dữ liệu dựa trên Naive Bayes và cây quyết định J48 Chương này sẽ đi vào tìm hiểu một số thuật toán về phân lớp, cụ thể trong luận văn áp dụng thuật toán Naive Bayes và cây quyết định J48. Chương 3: Phân loại các ca kiểm thử, thử nghiệm và đánh giá Chương này đi sâu phân tích dữ liệu và áp dụng dữ liệu thực tế vào Weka, áp dụng thuật toán với dữ liệu cụ thể. Từ đó phân tích và đánh giá kết quả thu được. 3 CHƯƠNG 1: KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN PHÂN LỚP CÁC CA KIỂM THỬ 1.1 Khai phá dữ liệu 1.1.1 Tại sao lại cần khai phá dữ liệu Với sự bùng nổ thông tin trong những thập kỷ gần đây thì lượng thông tin ngày càng trở nên khổng lồ. Làm thế nào để khai thác được “kho” thông tin đó đang là một câu hỏi cần thiết được đặt ra. Khai phá dữ liệu (Data Mining) ra đời như là một hướng giải quyết hữu hiệu câu hỏi trên. Có khá nhiều định nghĩa về Data Mining như là một công nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu được tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó. 1.1.2 Khái niệm Khai phá dữ liệu (Data Mining) là một quá trình chắt lọc hay khai phá tri thức từ một lượng dữ liệu lớn. Theo Frawley, Piatetski-Shapiro và Matheus Khai phá là một bước trong quá trình phát triển tri thức trong cơ sở dữ liệu. thi hành một thuật toán khai phá dữ liệu để tìm ra các mẫu từ dữ liệu. Hình 1.1 Các bước của quá trình phát triển tri thức trong cơ cở dữ liệu 4 Khai phá dữ liệu là bước thứ 5 trong 7 bước của quá trình phát triển tri thức trong cơ cở dữ liệu 1.1.3 Quá trình khai phá dữ liệu:  Tìm hiểu dữ liệu: Nhà tư vấn nghiên cứu kiến thức về lĩnh vực áp dụng, bao gồm các tri thức cấu trúc về hệ thống, các nguồn dữ liệu hiện hữu, ý nghĩa, vai trò và tầm quan trọng của các thực thể dữ liệu.  Chuẩn bị dữ liệu: Giai đoạn này sử dụng các kỹ thuật tiền xử lý bao gồm để biến đổi và cải thiện chất lượng dữ liệu để thích hợp với các yêu cầu của các giải thuật học. Các giải thuật tiền xử lý bao gồm: - Xử lý dữ liệu bị thiếu, mất. Các dữ liệu bị thiếu sẽ được thay thế bởi các giá trị thích hợp. - Khử sự trùng lặp: Các đối tượng dữ liệu trùng lặp sẽ bị loại bỏ. Kỹ thuật này không được sử dụng cho các tác vụ có quan tâm đến phân bổ dữ liệu. - Giảm nhiễu: nhiễu và các đối tượng tách rời khỏi phân bố chung sẽ bị loại ra khỏi dữ liệu. - Chuẩn hóa: Miền giá trị của dữ liệu sẽ được chuẩn hóa. - Rời rạc hóa: Các dữ liệu số sẽ được biến đổi ra các giá trị rời rạc. - Rút trích và xây dựng đặc trưng mới từ các thuộc tính đã có. - Giảm chiều: các thuộc tính chứa ít thông tin sẽ bị loại bỏ bớt.  Mô hình hóa dữ liệu: Các giải thuật học sử dụng các dữ liệu đã được tiền xử lý trong giai đoạn hai để tìm kiếm các quy tắc ẩn và chưa biết.  Hậu xử lý và đánh giá mô hình: - Dựa trên đánh giá của người dùng sau khi kiểm tra trên các tập thử các mô hình sẽ được tinh chỉnh và kết hợp lại nếu cần. Chỉ các mô hình đạt được các yêu cầu cơ bản của người dùng mới đưa ra triển khai trong thực tế. 5 - Trong giai đoạn này, các kết quả được biến đổi từ dạng học thuật sang dạng phù hợp với môi trường nghiệp vụ và dễ hiểu hơn cho người dùng.  Triển khai tri thức - Các mô hình được đưa vào hệ thống thông tin thực tế dưới dạng các modun hỗ trợ việc đưa ra quyết định - Mối quan hệ chặt chẽ giữa các giai đoạn trong quá trình khai phá dữ liệu là rất quan trọng cho việc nghiên cứu trong khai phá dữ liệu. Một giải thuật trong khai phá dữ liệu không thể được phát triển độc lập, không quan tâm đến bối cảnh áp dụng mà thường được xây dựng để giải quyết một mục tiêu cụ thể. - Quá trình này có thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa trên phản hồi từ kết quả của các giai đoạn sau. 1.1.4 Các bài toán thông dụng trong Khai phá dữ liệu:  Phân lớp (Classification): Với 1 tập dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật sẽ học ra bộ phân loại (classiffier) dùng để phân loại các dữ liệu mới vào trong những lớp đã được xác định trước. Giới thiệu một số thuật toán phân lớp điển hình: - Support Vector Machine (SVM) - Thuật toán Bayes - Cây quyết định  Dự đoán (Prediction): sẽ học ra các bộ dự đoán. Khi có dữ liệu mới đến, bộ dự đoán sẽ dựa trên thông tin đang có để đưa ra một giá trị số học cho hàm cần dự đoán.  Tìm luật liên kết (Association Rule): tìm kiếm các mối liên kết giữa các thành phần từ dữ liệu.  Phân cụm (Clustering) sẽ nhóm các đối tượng dữ liệu có tính chất giống nhau vào cùng một nhóm. 6 1.2 Kỹ thuật kiểm thử phần mềm 1.2.1 Một số phương thức thiết kế kiểm thử Quá trình phát triển một hệ thống phần mềm bao gồm một chuỗi các hoạt động sản sinh ra mã lệnh, tài liệu, nơi mà những sai sót của con người có thể xẩy ra bất cứ lúc nào. Một lỗi có thể xuất hiện ngay từ lúc bắt đầu những dòng code đầu tiên, do đó quá trình phát triển một phần mềm phải kết hợp với một quá trình kiểm thử. Hiện tại phát triển rất nhiều các phương thức thiết kế các trường hợp kiểm thử cho phần mềm. Những phương pháp này đều cung cấp một hướng kiểm thử có tính hệ thống. Quan trọng hơn nữa là chúng cung cấp một hệ thống có thể đảm bảo sự hoàn chỉnh của các trường hợp kiểm thử phát hiện lỗi cho phần mềm. Một sản phẩm đều có thể kiểm thử theo hai cách:  Hiểu rõ một chức năng cụ thể của một hàm hay một module. Các trường hợp kiểm thử có thể được xây dựng để kiểm thử tất cả các thao tác đó.  Hiểu rõ cách hoạt động của một hàm/module hay sản phẩm. Các trường hợp kiểm thử có thể được xây dựng để đảm bảo tất cả các thành phần con khớp với nhau. Đó là tất cả các thao tác nội bộ của hàm dựa vào các mô tả và tất cả các thành phần nội bộ đã được kiểm thử một cách thỏa đáng. Cách tiếp cận đầu tiên gọi là kiểm thử hộp đen (Black-box testing) và cách tiếp cận thứ hai gọi là kiểm thử hộp trắng (White-box testing). Trong luận văn này tôi sẽ đề cập đến cách kiểm thử với hướng tiếp cận thứ 2 kiểm thử hộp trắng. Đặc điểm của kiểm thử hộp trắng là dựa vào các giải thuật cụ thể, vào cấu trúc dữ liệu bên trong của đơn vị phần mềm cần kiểm thử để xác định đơn vị phần mềm đó có được thực hiện đúng không. Kỹ thuật kiểm thử này thường mất rất nhiều thời gian và công sức nếu mức độ kiểm thử được nâng cao lên ở cấp kiểm thử tích hợp hay kiểm thử hệ thống. Thông thường sau khi code xong một vài chức năng thì chúng ta sử dụng các công cụ như Junit testing để kiểm thử cho ứng dụng. Có 2 hoạt động kiểm thử hộp trắng: 7 - Kiểm thử luồng điều khiển : tập trung kiểm thử giải thuật chức năng. - Kiểm thử dòng dữ liệu : tập trung kiểm thử đời sống của từng biến dữ liệu được dùng trong giải thuật. Trong kiểm thử hộp trắng có rất nhiều phương pháp được đưa ra nhưng trong luận văn này tôi xin giới thiệu về phương pháp phổ biến thường được sử dụng nhiều nhất là phương pháp kiểm thử đường thi hành (Execution Path). Kiểm thử đường thi hành là 1 kịch bản thi hành đơn vị phần mềm tương ứng, cụ thể nó là danh sách có thứ tự các lệnh được thi hành ứng với 1 lần chạy cụ thể của đơn vị phần mềm, bắt đầu từ điểm nhập của đơn vị phần mềm đến điểm kết thúc của đơn vị phần mềm. 1.2.2 Ví dụ thử nghiệm Mỗi TPPM có từ 1 đến n (có thể rất lớn) đường thi hành khác nhau. Mục tiêu của phương pháp kiểm thử luồng điều khiển là đảm bảo mọi đường thi hành của đơn vị phần mềm cần kiểm thử đều chạy đúng. Rất tiếc trong thực tế, công sức và thời gian để đạt mục tiêu trên đây là rất lớn, ngay cả trên những đơn vị phần mềm nhỏ. Thí dụ đoạn code sau : for (i=1; i<=1000; i++) for (j=1; j<=1000; j++) for (k=1; k<=1000; k++) doSomethingWith(i,j,k); chỉ có 1 đường thi hành, nhưng rất dài : dài 1000*1000*1000 = 1 tỉ lệnh gọi hàm doSomething(i,j,k) khác nhau. Mà cho dù có kiểm thử hết được toàn bộ các đường thi hành thì vẫn không thể phát hiện những đường thi hành cần có nhưng không (chưa) được hiện thực. Do đó, ta nên kiểm thử 1 số test case tối thiểu mà kết quả độ tin cậy tối đa. Nhưng làm sao xác định được số test case tối thiểu nào có thể đem lại kết quả có độ tin cậy tối đa ? 8 Phủ kiểm thử (Coverage) : là tỉ lệ các thành phần thực sự được kiểm thử so với tổng thể sau khi đã kiểm thử các test case được chọn. Phủ càng lớn thì độ tin cậy càng cao. Thành phần liên quan có thể là lệnh thực thi, điểm quyết định, điều kiện con hay là sự kết hợp của chúng. Phủ cấp 0 : kiểm thử những gì có thể kiểm thử được, phần còn lại để người dùng phát hiện và báo lại sau. Đây là mức độ kiểm thử không thực sự có trách nhiệm. Phủ cấp 1 : kiểm thử sao cho mỗi lệnh được thực thi ít nhất 1 lần. Phân tích hàm foo sau đây : 1 float foo(int a, int b, int c, int d) { 2 float e; 3 if (a==0) 4 return 0; 5 int x = 0; 6 if ((a==b) || ((c==d) && bug(a))) 7 x = 1; 8 e = 1/x; 9 return e; 10} Với hàm foo trên, ta chỉ cần 2 test case sau đây là đạt 100% phủ cấp 1 : 1. foo(0,0,0,0), trả về 0 2. foo(1,1,1,1), trả về 1 nhưng không phát hiện lỗi chia 0 ở hàng lệnh 8. Phủ cấp 2 : kiểm thử sao cho mỗi điểm quyết định luận lý đều được thực hiện ít nhất 1 lần cho trường hợp TRUE lẫn FALSE. Ta gọi mức kiểm thử này là phủ các nhánh (Branch coverage). Phủ các nhánh đảm bảo phủ các lệnh. 9 L Predicate True 3 (a == 0) Test False ine Case 1 foo(0, 0, 0, 0) return 0 6 ((a==b) OR Test Case 1, 1, 1) return 1 2 foo(1, 1, 1, 1) ((c == d) Test Case 2 foo(1, Test Case 3 foo(1, 2, 1, 2) division by zero! return 1 AND bug(a) )) Bảng 1.1: Các ca kiểm thử phủ cấp 2 Với 2 test case xác định trong slide trước, ta chỉ đạt được 3/4 = 75% phủ các nhánh. Nếu thêm test case 3 : 3. foo(1,2,1,2), thì mới đạt 100% phủ các nhánh. 1.3 Kết luận Có rất nhiều kỹ thuật khai phá dữ liệu đã được áp dụng nhằm xử lý kho dữ liệu trong phát triển phần mềm. Trong 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. 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. 2.1 Kỹ thuật Naive Bayes cho phân lớp dữ liệu 2.1.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 𝐵. Ký hiệu 𝑃(𝐴|𝐵). 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ữ 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.1.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