Tài liệu Luận văn async smote một giải pháp cho phân lớp dữ liệu mất cân bằng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI -------- ĐỖ NGỌC QUỲNH NGHIÊN CỨU PHƢƠNG PHÁP DEC-SVM PHÂN LỚP DỮ LIỆU MẤT CÂN BẰNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI, NĂM 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI -------- ĐỖ NGỌC QUỲNH NGHIÊN CỨU PHƢƠNG PHÁP DEC-SVM PHÂN LỚP DỮ LIỆU MẤT CÂN BẰNG Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Ngƣời hƣớng dẫn khoa học: TS. Đặng Xuân Thọ HÀ NỘI, NĂM 2017 LỜI CAM ĐOAN Tôi xin cam đoan bản luận án này là kết quả nghiên cứu của cá nhân tôi. Các số liệu và tài liệu được trích dẫn trong luận án là trung thực. Kết quả nghiên cứu này không trùng với bất cứ công trình nào đã được công bố trước đó. Tôi chịu trách nhiệm với lời cam đoan của mình. Hà Nội, ngày tháng năm 2017 Tác giả luận văn Đỗ Ngọc Quỳnh LỜI CẢM ƠN Để hoàn thành luận văn này, em xin bày tỏ lòng kính trọng và biết ơn sâu sắc đến TS. Đặng Xuân Thọ, đã tận tình hướng dẫn, động viên và giúp đỡ em trong suốt thời gian thực hiện đề tài. Em xin chân thành cảm ơn các thầy cô giáo trong khoa Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội đã tạo mọi điều kiện thuận lợi cho em được học tập và nghiên cứu trong thời gian qua. Cuối cùng, em xin gửi lòng biết ơn đến những người thân trong gia đình và bạn bè đã dành cho em sự khích lệ, động viên và giúp đỡ em trong suốt quá trình học tập. Mặc dù đã có nhiều cố gắng để thực hiện luận văn, nhưng quá trình thực hiện không thể tránh khỏi những thiếu sót và hạn chế. Rất mong nhận được sự thông cảm và ý kiến đóng góp của các thầy cô giáo và các bạn. Em xin chân thành cảm ơn! Hà Nội, ngày… tháng … năm 2017 Tác giả luận văn Đỗ Ngọc Quỳnh MỤC LỤC MỤC LỤC ..............................................................................................................1 DANH MỤC CÁC HÌNH VẼ ................................................................................3 DANH MỤC CÁC BẢNG BIỂU...........................................................................3 DANH MỤC CÁC TỪ VIẾT TẮT ........................................................................4 PHẦN 1 – MỞ ĐẦU .............................................................................................5 PHẦN 2 – NỘI DUNG...........................................................................................9 Chương 1: GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU .............................................9 1.1. Tổng quan về khai phá dữ liệu ....................................................................9 1.1.1. Khai phá dữ liệu là gì? .........................................................................9 1.1.2. Ứng dụng của khai phá dữ liệu ..........................................................11 1.2. Phân lớp dữ liệu .........................................................................................12 1.2.1. Phân lớp dữ liệu là gì? ........................................................................12 1.2.2. Một số kỹ thuật phân lớp dữ liệu chuẩn .............................................13 1.3. Phân cụm dữ liệu .......................................................................................18 1.3.1. Phân cụm dữ liệu là gì? ......................................................................18 1.3.2. Một số kỹ thuật phân cụm dữ liệu chuẩn ...........................................19 Chương 2: THUẬT TOÁN DEC-SVM CHO BÀI TOÁN PHÂN LỚP DỮ LIỆU MẤT CÂN BẰNG ...............................................................................................24 2.1. Vấn đề mất cân bằng trong dữ liệu hiện nay .............................................24 2.2. Hướng giải quyết cho bài toán phân lớp dữ liệu mất cân bằng hiện nay ..25 2.3. Thuật toán DEC-SVM cho bài toán phân lớp dữ liệu mất cân bằng.....30 1 2.3.1. Điều chỉnh dữ liệu bằng thuật toán DE (Differential Evolution oversampling) ......................................................................................30 2.3.2. Kỹ thuật làm sạch dữ liệu sử dụng phân cụm ....................................31 2.3.3. Thuật toán ...........................................................................................33 Chương 3: CÀI ĐẶT VÀ THỬ NGHIỆM ...........................................................36 3.1. Các tiêu chí đánh giá .................................................................................36 3.1.1. Ma trận nhầm lẫn ................................................................................36 3.1.2. F-Measure ...........................................................................................37 3.1.3. G-mean ...............................................................................................37 3.1.4. Đường cong ROC và độ đo AUC.......................................................37 3.2. Dữ liệu và thiết lập thực nghiệm ...............................................................38 3.2.1. Dữ liệu ................................................................................................38 3.2.2. Thiết lập thực nghiệm.........................................................................38 3.3. Kết quả thực nghiệm và đánh giá ..............................................................39 Hình 3. 2 - Biểu đồ so sánh hiệu quả phân lớp giữa thuật toán DE-SVM và DECSVM ......................................................................................................................41 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................42 TÀI LIỆU THAM KHẢO ....................................................................................43 2 DANH MỤC CÁC HÌNH VẼ Hình 1.1 – Các bước trong quá trình KDD ...............................................................10 Hình 1.2 – Vị trí của khai phá dữ liệu trong tiến trình ra quyết định........................10 Hình 1.3 – Quá trình xây dựng mô hình phân lớp ....................................................12 Hình 1.4 – Quá trình phân lớp dữ liệu ......................................................................13 Hình 1.5 – Cây quyết định cho tiến trình lựa chọn phương tiện vận chuyển ...........15 Hình 1.6 – Phân lớp dữ liệu với K-NN .....................................................................16 Hình 1.7 – Phân lớp dữ liệu bằng SVM ....................................................................17 Hình 1.8 – Phân cụm dữ liệu .....................................................................................18 Hình 1.9 – Quá trình phân cụm dữ liệu .....................................................................19 Hình 1.10 – Hai phương pháp phân cụm phân cấp ..................................................21 Hình 1.11 – Khả năng tới được trực tiếp theo mật độ (directly density-reachable) .22 Hình 1.12 – Khả năng tới được theo mật độ (density-reachable) .............................22 Hình 1.13 – Kết nối dựa trên mật độ .........................................................................22 Hình 2.1 – Biểu đồ tỷ lệ giữa lớp thiểu số và lớp đa số của một số bộ dữ liệu ........25 Hình 2.2 – Phương pháp sinh ngẫu nhiên phần tử lớp thiểu số ...............................26 Hình 2.3 – Sinh thêm phần tử nhân tạo bằng thuật toán SMOTE ...........................27 Hình 2.4 – Loại bỏ phần tử lớp đa số ........................................................................29 Hình 2.5 – Minh họa phân cụm tập dữ liệu mất cân bằng ........................................32 Hình 3. 1 - Quá trình thực hiện 10-Fold Cross Validation .......................................39 Hình 3. 2 - Biểu đồ so sánh hiệu quả phân lớp giữa thuật toán DE-SVM và DECSVM ..........................................................................................................................41 DANH MỤC CÁC BẢNG BIỂU Bảng 3.1 – Ma trận nhầm lẫn ...................................................................................36 Bảng 3. 2 - Một số bộ dữ liệu sử dụng cho thực nghiệm ..........................................38 Bảng 3. 3 - Phân lớp dữ liệu sử dụng thuật toán DE-SVM ......................................40 Bảng 3. 4– Phân lớp dữ liệu sử dụng thuật toán DEC-SVM ....................................40 Bảng 3. 5– Bảng so sánh hiệu quả phân lớp .............................................................40 4 DANH MỤC CÁC TỪ VIẾT TẮT STT Từ viết tắt Diễn giải 1 CSDL Cơ sở dữ liệu 2 KDD Knowledge Discovery in Databases 3 SVM Support Vector Machine 4 K – NN K – Nearest Neighbor 5 SMOTE 6 DBSCAN 7 DEC – SVM 8 DE - SVM Synthentic Minority Over-sampling Technique Density-Based Spatial Clustering of Applications with Noise Differential Evolution Clustering hybrid resampling SVM algorithm Differential Evolution over-sampling SVM algorithm 4 PHẦN 1 – MỞ ĐẦU 1. Lý do chọn đề tài Hiện nay, công nghệ thông tin là lĩnh vực có tầm quan trọng và sức ảnh hưởng lớn tới nhiều mặt của đời sống. Trong những năm gần đây, công nghệ thông tin đã gặt hái được nhiều thành công mang tính đột phá hỗ trợ hữu hiệu cho các lĩnh vực khác. Cùng với sự phát triển của xã hội, vấn đề khai thác và xử lý thông tin ngày càng được chú trọng và có thể đóng vai trò quyết định thành công trong một số lĩnh vực. Trong khi lượng thông tin trên toàn cầu đang ngày một gia tăng và ngày càng phong phú, các kỹ thuật trong Khai phá dữ liệu góp phần hữu hiệu giúp con người khai thác một cách có hiệu quả khối dữ liệu mà họ đang nắm giữ. Một trong những kỹ thuật quan trọng trong Khai phá dữ liệu là phân lớp dữ liệu, và phân lớp dữ liệu đối với dữ liệu mất cân bằng hiện vẫn đang là bài toán cần được chú trọng. Phân lớp dữ liệu là kỹ thuật dựa vào một mô hình phân lớp với các nhãn lớp đã cho trong mô hình đó, dự đoán nhãn lớp của một đối tượng dữ liệu mới. Mô hình phân lớp được xây dựng dựa trên một tập dữ liệu huấn luyện, với một đối tượng dữ liệu mới, ta có thể đặt nó vào một lớp cụ thể bằng cách so sánh thuộc tính của nó với định nghĩa đã xây dựng cho các lớp trong tập dữ liệu huấn luyện. Tuy nhiên, dữ liệu thu được trong thực tế ngày càng xuất hiện nhiều các tập dữ liệu mất cân bằng, nghĩa là trong tập dữ liệu tồn tại lớp có nhiều phần tử hơn những lớp khác. Lớp có nhiều phần tử hơn ta gọi là lớp đa số, lớp có ít phần tử hơn ta gọi là lớp thiểu số. Sự chênh lệch về số lượng giữa lớp đa số và lớp thiểu số làm cho việc phân lớp đúng các mẫu thuộc lớp thiểu số bị giảm hiệu quả. Tỷ lệ mất cân bằng của tập dữ liệu càng cao thì việc phát hiện đúng các mẫu của lớp thiểu số càng khó khăn. Ví dụ điển hình cho mất cân bằng dữ liệu có thể kể đến là các bài toán chẩn đoán bệnh trong y học, nghĩa là xác định một người có bệnh hay không [17]. Hay bài toán phát hiện gian lận, cụ thể là gian lận thẻ tín dụng hay gian lận cước di động [17]… Thông thường trong các bài toán này, lớp cần quan tâm lại là lớp thiểu số (lớp người mắc bệnh, lớp người có khả năng gian lận thẻ tín dụng, …). Việc xác 5 định đúng nhãn cho lớp thiểu số là điều rất cần thiết, nếu nhãn của lớp nhỏ được chẩn đoán sai thì hậu quả đem đến là không hề nhỏ. Hiện nay, đã có nhiều giải pháp hữu hiệu cho bài toán phân lớp đối với các tập dữ liệu mất cân bằng. Để giải quyết các bài toán này, có hai cách tiếp cận chủ yếu: tiếp cận dựa trên mức độ dữ liệu hoặc tiếp cận dựa trên mức độ thuật toán. Tiếp cận dựa trên mức dữ liệu nghĩa là điều chỉnh phân bố dữ liệu của các lớp sao cho hạn chế hoặc không còn bị mất cân bằng để đưa vào áp dụng cho các thuật toán phân lớp chuẩn [17]. Có nhiều cách điều chỉnh dữ liệu như: sinh thêm phần tử cho lớp thiểu số, loại bỏ các phần tử ở lớp đa số, hoặc kết hợp hai phương pháp trên [17]. Tiếp cận dựa trên mức độ thuật toán nghĩa là điều chỉnh các thuật toán phân lớp chuẩn sao cho khi áp dụng với bộ dữ liệu mất cân bằng vẫn đạt được hiệu quả cao. Trong hai cách tiếp cận nêu trên, chúng tôi rất quan tâm tới giải pháp sinh thêm phần tử cho lớp thiểu số. Một thuật toán điều chỉnh dữ liệu dựa trên giải pháp này phải kể đến là thuật toán SMOTE (2002) [14].Thuật toán SMOTE điều chỉnh dữ liệu bằng cách với mỗi phần tử thuộc lớp thiểu số thực hiện sinh thêm các phần tử nhân tạo giữa phần này với các láng giềng của nó. Một số thuật toán khác cải tiến dựa trên thuật toán SMOTE đã đạt được hiệu quả với các bộ dữ liệu mất cân bằng như: thuật toán Borderline-SMOTE (2005) [9], thuật toán Safe-Level-SMOTE (2009) [3]. Tuy nhiên, với sự phong phú ngày càng gia tăng của thông tin và đặc thù của các tập dữ liệu hầu hết không giống nhau, không có giải pháp nào là hữu hiệu cho mọi tập dữ liệu. Trong luận văn này, tôi nghiên cứu một thuật toán điều chỉnh dữ liệu cho bài toán phân lớp dữ liệu mất cân bằng – thuật toán DEC (a novel Differential Evolution Clustering hybrid resampling) được công bố vào năm 2010 của nhóm tác giả Leichen Chen, Zhihua Cai, Lu Chen và Qiong Gu [1]. Thuật toán này là sự kết hợp giữa phương pháp sinh thêm phần tử cho lớp thiểu số và sử dụng kỹ thuật phân cụm K-means để loại bỏ bớt phần tử dư thừa, nhiễu trong dữ liệu. Ban đầu, với mỗi mẫu thuộc lớp thiểu số, thuật toán tạo ra một mẫu đột biến từ hai trong số những láng giềng gần nó nhất, sau đó sử dụng thuật toán di truyền để sinh 6 thêm phần tử cho lớp thiểu số từ mẫu thiểu số ban đầu và mẫu đột biến mới tạo ra. Cuối cùng, sử dụng thuật toán SVM để phân lớp cho tập dữ liệu huấn luyện mới. Thuật toán phân lớp dữ liệu này được đặt tên là DEC-SVM. 2. Mục đích nghiên cứu Mục đích nghiên cứu của luận văn : - Giới thiệu về bài toán phân lớp dữ liệu mất cân bằng và một số phương pháp giải quyết bài toán. - Trình bày thuật toán DEC điều chỉnh dữ liệu cho bài toán phân lớp dữ liệu mất cân bằng. 3. Khách thể và đối tƣợng nghiên cứu - Một số phương pháp điều chỉnh dữ liệu mất cân bằng. - Một số thuật toán phân lớp/ phân cụm dữ liệu chuẩn - Ngôn ngữ R 4. Giả thuyết khoa học Việc kết hợp kỹ thuật phân cụm trong quá trình phân lớp cho các bộ dữ liệu mất cân bằng sẽ giúp nâng cao hiệu quả phân lớp. 5. Phạm vi nghiên cứu - Lý thuyết tổng hợp trong khai phá dữ liệu - Các kỹ thuật phân lớp/phân cụm dữ liệu - Các phương pháp phân lớp dữ liệu mất cân bằng hiện nay - Các tiêu chí đánh giá hiệu quả phân lớp - Nghiên cứu ngôn ngữ R - một loại ngôn ngữ lập trình và môi trường phần mềm dành cho tính toán và đồ họa thống kê 6. Phƣơng pháp nghiên cứu - Đọc tài liệu, phân tích, phân loại, tổng hợp, đối chiếu, so sánh, thảo luận , rút trích, để xây dựng luận văn - Quan sát, lập trình và thử nghiệm 7. Cấu trúc luận văn Luận văn được chia thành ba chương: 7 Chương 1: Tổng quan về khai phá dữ liệu Chương này giới thiệu tổng quan về Khai phá dữ liệu và trình bày một số kỹ thuật phổ biến của Khai phá dữ liệu. Chương 2: Thuật toán DEC điều chỉnh dữ liệu trong phân lớp dữ liệu mất cân bằng. Chương này đề cập đến dữ liệu mất cân bằng và các hướng giải quyết và một số phương pháp phổ biến cho các bài toán có liên quan đến dữ liệu mất cân bằng. Trình bày thuật toán điều chỉnh dữ liệu mới nâng cao hiệu quả trong bài toán phân lớp dữ liệu mất cân bằng – thuật toán DEC. Đồng thời kết hợp thuật toán DEC với kỹ thuật phân lớp SVM tạo nên thuật toán phân lớp DEC-SVM. Chương 3: Cài đặt và thử nghiệm. Nội dung của chương 3, trình bày các kết quả thực nghiệm thu được khi áp thuật toán phân lớp dữ liệu DEC-SVM. Các thực nghiệm sẽ được tiến hành trên các bộ dữ liệu lấy từ kho dữ liệu UCI. Cuối cùng, dựa vào các tiêu chí đánh giá, để so sánh hiệu quả của thuật toán DEC-SVM với một số thuật toán đã biết. 8 PHẦN 2 – NỘI DUNG Chƣơng 1: GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU 1.1. Tổng quan về khai phá dữ liệu 1.1.1. Khai phá dữ liệu là gì? Trong thời đại bùng nổ của công nghệ thông tin cùng với những thành tựu to lớn trong lĩnh vực này đã góp phần không nhỏ trong sự phát triển của hầu hết các lĩnh vực trong đời sống. Sự phát triển mạnh mẽ của xã hội dẫn tới nhu cầu sử dụng và trao đổi thông tin ngày càng tăng cao. Với các ứng dụng của công nghệ thông tin cùng sự ra đời các kết nối internet tốc độ cao, sự phát sinh và lan truyền lượng dữ liệu lớn đã được tự động hóa trong thập kỷ qua. Hậu quả là, nhân loại đang phải đối mặt với nhiều thách thức trong việc đối phó với lượng thông tin khổng lồ đang ngày càng gia tăng cùng những bộ dữ liệu quá lớn đối với phân tích thủ công. Các công nghệ lưu trữ tiên tiến hiện nay đã tạo điều kiện cho các tổ chức, doanh nghiệp hay cá nhân thuận lợi hơn trong quá trình thu thập và lưu trữ thông tin. Các kho dữ liệu ngày càng lớn và chứa nhiều thông tin có ích. Tuy nhiên, vẫn còn khó khăn để tự động khai thác những thông tin có giá trị bên trong chúng. Theo đánh giá của IBM, các phương pháp khai thác thông tin truyền thống chỉ thu được khoảng 80% thông tin từ CSDL, phần còn lại bao gồm các thông tin mang tính khái quát, thông tin có quy luật vẫn còn tiềm ẩn bên trong dữ liệu. Lượng thông tin này tuy nhỏ nhưng là thông tin cốt lõi và cần thiết cho tiến trình ra quyết định [28]. Trước sự bùng nổ thông tin cùng những thách thức trong việc khai thác và xử lý thông tin, Khai phá dữ liệu ra đời, và cho đến nay đã gặt hái được nhiều thành tựu. Khai phá dữ liệu (Data Mining) là một bước trong quá trình khai phá tri thức từ CSDL (Knowledge Discovery in Databases – KDD). Khai phá dữ liệu bao gồm các thuật toán khai phá đặc biệt nằm trong giới hạn khả năng của máy tính để tìm ra các mẫu, mô hình dữ liệu hoặc các thông tin có ích. Hình 1.1 thể hiện các bước trong quá trình KDD [25] 9 Hình 1.1 – Các bước trong quá trình KDD Định nghĩa cổ điển của khai phá tri thức của Fayyad et al. từ năm 1996 mô tả KDD là "quá trình không tầm thường của việc xác định tính có hiệu lực, tính mới mẻ, khả năng hữu dụng, và các mô hình dễ hiểu cuối cùng trong dữ liệu [5]. Hai mục tiêu cơ bản cấp độ cao của khai phá dữ liệu trong thực tế có xu hướng là dự đoán và mô tả [5]. Khai phá dữ liệu giúp phát hiện những xu thế phát triển từ những thông tin quá khứ, cũng như đề xuất các dự báo mang tính thống kê, gom cụm và phân loại dữ liệu [28]. Có thể thấy khai phá dữ liệu là một mắt xích quan trọng trong quá trình khai phá tri thức và hỗ trợ ra quyết định. Hình 1.2 thể hiện vị trí của khai phá dữ liệu trong tiến trình ra quyết định. Hình 1.2 – Vị trí của khai phá dữ liệu trong tiến trình ra quyết định 10 Khai phá dữ liệu có một số kỹ thuật phổ biến như: phân lớp, phân cụm, khai phá luật kết hợp, dự báo, cây quyết định, … Trong luận văn này tôi xin trình bày hai kỹ thuật: phân lớp dữ liệu (phần 1.2) và phân cụm dữ liệu (phần 1.3) 1.1.2. Ứng dụng của khai phá dữ liệu Khai phá dữ liệu đã và đang được ứng dụng trong nhiều lĩnh vực trong đời sống. Dưới đây là một số lĩnh vực nổi bật có sự giúp sức hữu hiệu của khai phá dữ liệu. 1.1.2.1. Lĩnh vực tài chính, ngân hàng và thương mại điện tử ‒ Xây dựng mô hình dự báo rủi ro tín dụng [28] ‒ Tìm kiếm tri thức, quy luật thị trường chứng khoán và đầu tư bất động sản [28] ‒ Phân tích hiệu quả của các chiến dịch bán hàng [20] ‒ Phân loại, phân nhóm, phân tích hành vi khách hàng cho tiếp thị tài chính [20] ‒ Tìm hiểu, định hướng, thúc đẩy, giao tiếp với khách hàng [28] ‒ Phát hiện các hoạt động rửa tiền và tội phạm tài chính [20] 1.1.2.2. Lĩnh vực viễn thông ‒ Phân tích dữ liệu đa chiều viễn thông ‒ Xây dựng các mô hình phát hiện bất thường, phát hiện gian lận trong giao dịch viễn thông ‒ Phân tích hành vi sử dụng dịch vụ viễn thông của khách hàng ‒ Phát hiện xâm nhập mạng trái phép [20] 1.1.2.3. Lĩnh vực sinh học, y học ‒ Xây dựng các công cụ trực quan trong phân tích dữ liệu di truyền. ‒ Xây dựng mô hình khai phá các mạng di truyền và cấu trúc Gen, protein ‒ Lập chỉ mục, tìm kiếm tương tự, bất thường trong cơ sở dữ liệu Gen. ‒ Phát hiện và phân tích dữ liệu di truyền. 11 1.2. Phân lớp dữ liệu 1.2.1. Phân lớp dữ liệu là gì? Phân lớp dữ liệu là tiến trình tìm kiếm một tập các mô hình mô tả và phân biệt các lớp dữ liệu hoặc các khái niệm, nhằm mục đích sử dụng các mô hình để dự đoán nhãn lớp của các đối tượng dữ liệu có nhãn không xác định [7] Mô hình được thừa kế được dựa trên sự phân tích một tập dữ liệu huấn luyện (ví dụ như các đối tượng đã biết nhãn lớp) [7] Quá trình phân lớp gồm hai bước: ‒ Bước thứ nhất – bước học (huấn luyện): bước này xây dựng một mô hình phân lớp dựa trên việc phân tích, học tập, huấn luyện trên một tập dữ liệu đã biết trước nhãn lớp. ‒ Bước thứ hai – phân lớp: phân lớp dữ liệu mới sử dụng mô hình phân lớp ở bước trước nếu như độ chính xác của mô hình phân lớp đó được đánh giá là chấp nhận được. Ở bước thứ nhất, đầu vào của quá trình này là một tập dữ liệu có cấu trúc được mô tả bằng các thuộc tính và được tạo ra từ tập các bộ giá trị của các thuộc tính đó. Mỗi bộ giá trị được gọi chung là một phần tử dữ liệu (data tuple), có thể là các mẫu (sample), ví dụ (example), đối tượng (object), bản ghi (record) hay trường hợp (case) [18] Hình 1.3 – Quá trình xây dựng mô hình phân lớp Bước thứ hai dùng mô hình đã xây dựng ở bước trước để phân lớp cho dữ liệu mới. Nhưng trước tiên, độ chính xác của mô hình phân lớp vừa tạo ra phải được đánh 12 giá. Kỹ thuật đánh giá độ chính xác của mô hình phân lớp sử dụng một tập dữ liệu kiểm tra với các mẫu đã được gán nhãn lớp và độc lập với dữ liệu huấn luyện. Độ chính xác của mô hình là tỉ lệ phần trăm các các mẫu trong tập dữ liệu kiểm tra được mô hình phân lớp đúng (so với thực tế). Nếu độ chính xác của mô hình là chấp nhận được, thì mô hình được sử dụng để phân lớp những dữ liệu tương lai, hoặc những dữ liệu mà giá trị của thuộc tính phân lớp là chưa biết. Hình 1.4 – Quá trình phân lớp dữ liệu Trong mô hình phân lớp, thuật toán phân lớp giữ vai trò trung tâm, quyết định tới sự thành công của mô hình phân lớp. Hiện nay, bên cạnh các kỹ thuật phân lớp cơ bản, giới khoa học vẫn không ngừng nghiên cứu và tìm ra những phương pháp mới nhằm nâng cao hiệu quả, khả năng chính xác trong quá trình phân lớp dữ liệu. Luận văn này xin trình bày khái quát một số kỹ thuật phân lớp cơ bản hiện nay. 1.2.2. Một số kỹ thuật phân lớp dữ liệu chuẩn 1.2.2.1. Thuật toán phân lớp cây quyết định (Decision tree) Phân lớp bằng cây quyết định là một kỹ thuật thông dụng trong khai phá dữ liệu. 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 và các cành đại diện cho sự kết hợp của các thuộc tính dẫn đến các phân loại [11]. Một cách để học một cây quyết định là chia tập mẫu thành các tập con dựa trên một số kiểm tra thuộc tính. Quá trình này sau đó được lặp đi lặp lại một cách đệ quy trên các tập con, với mỗi giá trị của bộ chia trở thành một gốc cây con. Quá trình này 13 dừng lại khi một tập con bị nhỏ đến nỗi không cần thiết chia nữa hoặc một tập con chứa các mẫu chỉ có một phân loại [11]. Phân lớp dựa trên cây quyết định được sử dụng để hỗ trợ cho tiến trình ra quyết định hoặc dự đoán, quản lý rủi ro, … Hình 1.5 là một ví dụ về việc sử dụng cây quyết định trong tiến trình lựa chọn loại phương tiện vận chuyển. Hiện nay, có một số giải thuật phân lớp dựa trên cây quyết định phổ biến hiện nay như ID3 (Iterative Dichotomiser 3), CLS (Concept Learning System), C4.5, CART (Classification And Regression Trees). Một số ưu điểm của phương pháp phân lớp dựa trên cây quyết định là tốc độ học tương đối nhanh, có thể chuyển thành luật một cách dễ dàng, độ chính xác tương đối tốt và đòi hỏi tiền xử lý dữ liệu đơn giản. 14 Hình 1.5 – Cây quyết định cho tiến trình lựa chọn phương tiện vận chuyển 1.2.2.2. Thuật toán phân lớp K láng giềng gần nhất (K-NN) Thuật toán phân lớp K láng giềng gần nhất – K-NN (K – Nearest neighbor) là phương pháp phân lớp các đối tượng dựa vào khoảng cách gần nhất giữa đối tượng cần phân lớp và tất cả các đối tượng trong dữ liệu huấn luyện. Một đối tượng được phân lớp dựa vào K láng giềng của nó. K là số nguyên dương được xác định trước khi thực hiện thuật toán. Người ta thường dùng khoảng cách Euclidean để đo khoảng cách giữa các đối tượng 15 Ý tưởng của thuật toán K-NN như sau: Đầu tiên cần xác định tham số K. Đối với đối tượng cần phân lớp, tính khoảng cách giữa đối tượng đó và tất cả cả các đối tượng trong tập dữ liệu huấn luyện rồi sắp xếp các khoảng cách vừa tính được để tìm ra K láng giềng gần nhất. Sau đó xác định nhãn lớp của K láng giềng gần nhất vừa tìm được, nhãn lớp của đối tượng cần phân lớp sẽ là nhãn lớp của phần đông đối tượng trong K láng giềng gần nhất của nó. Hình 1.6 – Phân lớp dữ liệu với K-NN Trong Hình 1.6 với K = 3, đối tượng cần phân lớp sẽ được gán nhãn “Positive”. Với K = 5, đối tượng cần phân lớp sẽ được gán nhãn “Negative”. 1.2.2.3. Thuật toán phân lớp Naïve Bayes Naïve Bayes là phương pháp phân lớp dữ liệu dựa vào xác suất được giới thiệu đầu tiên bởi John và Langle năm [10]. Đây là kỹ thuật được ứng dụng khá rộng rãi trong phân lớp dữ liệu, đặc biệt là trong phân lớp văn bản (text). Naïve Bayes dự đoán xác suất mà một mẫu thuộc về một lớp là lớn nhất dựa trên định lý Bayes, giả định rằng các thuộc tính là độc lập và quan trọng như nhau. Bài toán phân lớp Naïve Bayes: Cho tập dữ liệu huấn luyện D gồm các mẫu đã biết trước nhãn lớp. Mỗi mẫu được biểu diễn bằng một véc tơ thuộc tính n chiều . Một mẫu mới sẽ được phân vào tập các nhãn lớp vào lớp nào? Quá trình phân lớp Naïve Bayes được thực hiện như sau: 16