Tài liệu Luận văn smote inffc giải quyết nhiễu và các phần tử ở đường biên trong phân lớp mất cân bằng bởi bộ lọc dựa trên sự hợp nhất các phân lớp.

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI ---------------OO------------ GIÁP THỊ PHƢƠNG THẢO SMOTE-INFFC: GIẢI QUYẾT NHIỄU Ở ĐƢỜNG BIÊN TRONG PHÂN LỚP MẤT CÂN BẰNG BẰNG PHƢƠNG PHÁP TÁI LẤY MẪU VỚI BỘ LỌC CÓ KIỂM SOÁT ĐỘ NHẠY CẢM NHIỄU Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 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 vă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, tháng 6 năm 2017 Tác giả luận văn Giáp Thị Phƣơng Thảo i LỜI CẢM ƠN Để hoàn thành luận văn, em xin bày tỏ lòng biết ơn sâu sắc đến các thầy cô giáo Trƣờng Đại học Sƣ phạm Hà Nội, đặc biệt là các thầy cô trong khoa Công nghệ thông tin, những ngƣời đã truyền đạt cho em nhiều kiến thức và đã tạo điều kiện giúp em thực hiện luận văn này. Em xin bày tỏ lòng biết ơn chân thành đến TS. Đặng Xuân Thọ đã dành nhiều thời gian tâm huyết, tận tình hƣớng dẫn, chỉ bảo cho em trong suốt quá trình thực hiện đề tài. Cuối cùng, em gửi lời biết ơn cha mẹ và anh chị em trong gia đình, các anh chị em đồng nghiệp luôn động viên và giúp đỡ trong quá trình học tập và nghiên cứu Mặc dù đã có nhiều cố gắng để hoàn thành luận văn một cách tốt nhất, tuy nhiên do thời gian nghiên cứu còn ít, bản thân còn thiếu kinh nghiệm trong nghiên cứu khoa học nên luận văn vẫn còn thiếu sót. Rất mong nhận đƣợc sự góp ý của thầy cô giáo và anh chị em đồng nghiệp. Em xin chân thành cảm ơn! Hà Nội, tháng 6 năm 2017 Học viên Giáp Thị Phƣơng Thảo ii MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN ................................................................................................... ii MỤC LỤC ........................................................................................................ iii DANH MỤC TỪ VIẾT TẮT ............................................................................... v DANH MỤC BẢNG BIỂU ............................................................................. vi DANH MỤC CÁC HÌNH VẼ ........................................................................ vii PHẦN I: MỞ ĐẦU .......................................................................................... 1 PHẦN II: NỘI DUNG ..................................................................................... 5 CHƢƠNG I. GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU................................. 5 1.1. Khai phá dữ liệu ........................................................................................... 5 1.1.1 Khái niệm. ................................................................................................ 5 1.1.2 Quá trình khai phá dữ liệu....................................................................... 6 1.1.3 Các kỹ thuật khai phá dữ liệu ................................................................. 8 1.2. Phân lớp.......................................................................................................10 1.2.1. Giới thiệu phân lớp ...............................................................................10 1.2.2. Một số vấn đề liên quan đến phân lớp dữ liệu ....................................11 1.3. Phân lớp mất cân bằng .............................................................................12 1.3.1. Phƣơng pháp tái lấy mẫu ......................................................................13 1.3.2 Học chi phí nhạy cảm (Cost-sensitive learning) ..................................15 1.4. Nhiễu và xử lý nhiễu ..................................................................................16 CHƢƠNG II. NGHIÊN CỨU PHƢƠNG PHÁP SMOTE-INFFC XỬ LÝ NHIỄU VÀ CÁC PHẦN TỬ ĐƢỜNG BIÊN TRONG PHÂN LỚP MẤT CÂN BẰNG. ..................................................................................19 2.1. Giới thiệu các phƣơng pháp tiếp cận giải quyết dữ liệu mất cân bằng ...19 2.1.1. Tiếp cận mức độ dữ liệu .......................................................................19 2.1.2. Tiếp cận mức độ thuật toán ..................................................................20 iii 2.2. Kỹ thuật sinh thêm phần tử nhân tạo ở lớp thiểu số............................21 2.2.1. Sinh thêm phần tử ở lớp thiểu số với việc thay thế ............................21 2.2.2. SMOTE .................................................................................................22 2.2.3. Một số kỹ thuật sử dụng SMOTE làm giảm phần tử nhiễu ...............25 2.3. Một số vấn đề khó khăn do nhiễu. ..........................................................26 2.4. Giới thiệu các bộ lọc nhiễu .......................................................................26 2.4.1. Lọc tập hợp (EF - Ensemble Filter).....................................................27 2.4.2. Lọc phân vùng lặp lại (IPF - Iterative-Partitioning Filter).................28 2.4.3. Lọc nhiễu dựa trên hợp nhất phân lớp (INFFC - Iterative Noise Filter based on the Fusion of Classifiers) ......................................................29 2.5. Phƣơng pháp SMOTE-INFFC xử lý nhiễu và các phần tử ở đƣờng biên trong phân lớp mất cân bằng .....................................................36 CHƢƠNG III. THỰC NGHIỆM ....................................................................39 3.1. Dữ liệu..........................................................................................................39 3.2. Tiêu chí đánh giá. .......................................................................................39 3.3 Phƣơng pháp phân tích ..............................................................................44 3.4. Kết quả và đánh giá. ..................................................................................44 PHẦN 3: KẾT LUẬN .......................................................................................54 1. Những kết quả thu đƣợc của luận văn .......................................................54 2. Hƣớng phát triển trong tƣơng lai ............................................................ 54 TÀI LIỆU THAM KHẢO................................................................................55 iv DANH MỤC TỪ VIẾT TẮT SMOTE Synthetic Minority Over sampling Technique INFFC Iterative Noise Filter based on the Fusion of Classifiers IPF Iterative Partitioning Filter EF Ensemble Filter FC Fusion of Classifiers SVM Support Vector Machine SL Safe Level BL Border Line ROC Receiver Operating Characteristic AUC Area Under Curve v DANH MỤC BẢNG BIỂU Bảng 1: Ví dụ về nhiễu.................................................................................... 17 Bảng 2: Bộ dƣ liệu thực nghiệm ..................................................................... 39 Bảng 3: Ma trận nhầm lẫn ............................................................................... 39 Bảng 4: Kết quả của bộ dữ liệu abalone ......................................................... 45 Bảng 5: Kết quả của bộ dữ liệu blood ............................................................. 46 Bảng 6: Kết quả của bộ dữ liệu ecoli .............................................................. 47 Bảng 7: Kết quả của bộ dữ liệu newthyroid.................................................... 48 Bảng 8: Kết quả của bộ dữ liệu haberman ...................................................... 49 Bảng 9: Kết quả Gmean của các bộ dữ liệu sau thực nghiệm ........................ 50 vi DANH MỤC CÁC HÌNH VẼ Hình 1: Quá trình khai phá tri thức ................................................................... 7 Hình 2: Ví dụ về oversampling ....................................................................... 21 Hình 3: Mô tả thuật toán SMOTE ................................................................... 23 Hình 4: Sơ đồ thực hiện lọc của INFFC ......................................................... 30 Hình 5: Tập dữ liệu huấn luyện ban đầu ......................................................... 37 Hình 6: Tập dữ liệu huấn luyện sau khi sử dụng SMOTE – INFFC .............. 37 Hình 7: Sơ đồ quá trình thực hiện phƣơng pháp SMOTE-INFFC ................. 38 Hình 8: Ví dụ về đồ thị ROC .......................................................................... 41 Hình 9: Ví dụ về đồ thị AUC .......................................................................... 42 Hình 10: Biểu đồ so sánh giá trị AUC của bộ dữ liệu abalone. ...................... 45 Hình 11: Biểu đồ so sánh giá trị AUC của bộ dữ liệu blood .......................... 46 Hình 12: Biểu đồ so sánh giá trị AUC của bộ dữ liệu ecoli............................ 47 Hình 13: Biểu đồ so sánh giá trị AUC của bộ dữ liệu newthyroid. ................ 48 Hình 14: Biểu đồ so sánh giá trị AUC của bộ dữ liệu haberman. .................. 49 Hình 15: Biểu đồ so sánh giá trị Gmean của bộ dữ liệu abalone .................... 51 Hình 16: Biểu đồ so sánh giá trị Gmean của bộ dữ liệu blood ....................... 51 Hình 17: Biểu đồ so sánh giá trị Gmean của bộ dữ liệu ecoli ........................ 52 Hình 18: Biểu đồ so sánh giá trị Gmean của bộ dữ liệu haberman ................ 52 Hình 19: Biểu đồ so sánh giá trị Gmean của bộ dữ liệu newthyroid .............. 53 vii PHẦN I: MỞ ĐẦU 1. Lý do chọn đề tài Trong khai phá dữ liệu, hai vấn đề phổ biến về chất lƣợng dữ liệu mà thƣờng ảnh hƣởng đến phân lớp dữ liệu trong thực tế là lớp nhiễu và lớp mất cân bằng. Lớp nhiễu, nơi các giá trị thuộc tính đƣợc ghi nhầm lẫn làm rối một bộ phân lớp và làm giảm hiệu suất dự đoán. Lớp mất cân bằng xảy ra khi một lớp chỉ chiếm một phần nhỏ trong những phân tử trong tập dữ liệu, và trong trƣờng hợp nhƣ vậy thì phân lớp thƣờng kém chính xác trên lớp thiểu số. Hiệu suất phân lớp càng trở nên tồi tệ hơn khi hai vấn đề xảy ra đồng thời. Hiện nay để giải quyết bài toàn phân lớp dữ liệu có chứa lớp mất cân bằng và lớp nhiễu đa số các nghiên cứu dựa trên hai hƣớng tiếp cận chính là dựa trên mức độ dữ liệu và dựa trên mức độ thuật toán. Tiếp cận dựa trên mức độ thuật toán là cải tiến các kỹ thuật tìm kiếm hoặc chiến lƣợc phân lớp để phù hợp cho loại dữ liệu mất cân bằng và xử lý đúng đắn các nhiễu hoặc ít chịu ảnh hƣởng bởi sự xuất hiện của nó. Tiếp cận dựa trên mức độ dữ liệu bao gồm những phƣơng pháp tiền xử lý các tập dữ liệu nhằm loại bỏ các phần tử nhiễu nhƣ một bƣớc trƣớc và điều chỉnh phân bố dữ liệu của các lớp làm giảm tính mất cân bằng trong lớp mất cân bằng . Trong các phƣơng pháp trên có phƣơng pháp sinh thêm phần tử nhân tạo ở lớp thiểu số (SMOTE) đã đƣợc xuất hiện trong nhiều công trình khoa học và đã có các kết quả nhất định. Mặc dù SMOTE đã hoàn thành rất tốt việc phân bố số lƣợng Phần tử ở mỗi lớp. Khi sử dụng độc lập thì nó có thể có kết quả không tốt nhƣ nó có thể hoặc nó có thể phản tác dụng trong nhiều trƣờng hợp. Đó là bởi vì SMOTE có một số hạn chế liên quan đến sinh thêm phần tử “mù”. Bởi vậy việc sinh thêm các phần tử tích cực (ở lớp thiểu số) chỉ làm cho các phần tử mới tạo ra và những phần tử ở mỗi lớp là gần sát nhau. Trong khi các đặc tính khác của dữ 1 liệu bị bỏ qua nhƣ sự phân bố của các phần tử ở lớp đa số. Những hạn chế này có thể làm tăng thêm những khó khăn tạo bởi các phần tử nhiễu và các phần tử ở đƣờng biên trong quá trình học. Đó là tạo ra quá nhiều các phần tử tích cực không cần thiết mà không thuận lợi cho việc học của lớp thiểu số. Phá vỡ các ranh giới giữa các lớp và tăng sự chồng chéo giữa chúng. Tác giả đề xuất một sự mở rộng của SMOTE thông qua một nhân tố mới với một bộ lọc lặp đi lặp lại dựa trên tập hợp các phân lớp đó là INFFC (Iterative Noise Filter based on the Fusion of Classifiers) để loại bỏ nhiễu. Phƣơng pháp SMOTE – INFFC trong phân lớp dữ liệu mất cân bằng. Phƣơng pháp này sử dụng kỹ thuật tái lấy mẫu SMOTE để sinh thêm phần tử nhân tạo ở lớp thiểu số, cân bằng phân lớp và áp dụng kỹ thuật lọc INFFC (Iterative Noise Filter based on the Fusion of Classifiers) để loại bỏ nhiễu và các phần tử ở đƣờng biên. 2. Mục đích nghiên cứu Tổng quan về khai phá dữ liệu, bài toán phân lớp, nhiễu và xử lý nhiễu. Nghiên cứu phƣơng pháp SMOTE, các bộ lọc nhiễu. Đề xuất mở rộng của SMOTE thông qua một nguyên tố mới, một bộ lọc có kiểm soát độ nhạy cảm nhiễu INFFC (Iterative Noise Filter based on the Fusion of Classifiers), có thể khắc phục đƣợc vấn đề phát sinh bởi nhiễu và phần tử ở đƣờng biên trong các tập dữ liệu không cân bằng và thực nghiệm trên ngôn ngữ R. 3. Khách thể và đối tƣợng nghiên cứu Tìm hiểu những vấn đề cơ bản về thuật toán SMOTE, các bộ lọc nhiễu và ngôn ngữ R. Đi sâu vào nghiên cứu, tìm hiểu thuật toán SMOTE, các bộ lọc nhiễu, ngôn ngữ R. 2 Phƣơng pháp mới SMOTE-INFFC: Giải quyết nhiễu ở đƣờng biên trong phân lớp mất cân băng bằng phƣơng pháp tái lấy mẫu với bộ lọc dựa vào hợp nhất các phân lớp. Thực nghiệm dựa trên bộ dữ liệu chuẩn. 4.Giả thuyết khoa học Giải quyết nhiễu và các phần tử ở đƣờng biên trong phân lớp mất cân bằng bằng phƣơng pháp SMOTE-INFFC. 5. Nhiệm vụ nghiên cứu Nghiên cứu phƣơng pháp SMOTE, nghiên cứu bộ lọc nhiễu INFFC, và thực hiện kết hợp SMOTE và INFFC thành bộ lọc nhiễu sử dụng cho phân lớp mất cân bằng. 6. Giới hạn phạm vi nghiên cứu Tiến hành thực nghiệm phƣơng pháp SMOTE-INFFC trên một số bộ dữ liệu chuẩn. Đánh giá về hiệu suất phân lớp các bộ dữ liệu sau khi sử dụng phƣơng pháp SMOTE-INFFC dựa trên các tiêu chí nhƣ Gmean, AUC. Phạm vi nghiên cứu trên các bộ dữ liệu mất cân bằng. 7. Phƣơng pháp nghiên cứu - Phƣơng pháp phân tích, tổng hợp - Phƣơng pháp quan sát, thực nghiệm, thảo luận, trình bày, tham khảo ý kiến đánh giá dựa trên kết quả thống kê. 8. Đóng góp mới của luận văn Luận văn đã nghiên cứu cơ sở lý luận và thực tiễn của một số bộ lọc nhiễu trên cơ sở tổng quan có chọn lọc một số bộ lọc đã đƣợc các nhà khoa học trong lĩnh vực khai phá dữ liệu và học máy trình bày, kết hợp đúc rút thực tiễn tác giả đề xuất bộ lọc nhiễu mới SMOTE-INFFC sử dụng lọc nhiễu cho phân lớp mất cân bằng. 3 9. Cấu trúc luận văn Nội dung chính của luận văn đƣợc trình bày trong 3 chƣơng: Chƣơng I. Giới thiệu về khai phá dữ liệu. Chƣơng II. Nghiên cứu phƣơng pháp SMOTE-INFFC xử lý nhiễu và các phần tử ở đƣờng biên trong phân lớp mất cân bằng. Chƣơng III. Thực nghiệm. 4 PHẦN II: NỘI DUNG CHƢƠNG I. GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU Trong chương này sẽ nghiên cứu khái niệm cơ bản về khai phá dữ liệu, sau đó đi vào tìm hiểu một số nội dung chính của khai thác dữ liệu như mô hình phân lớp, phân lớp với dữ liệu mất cân bằng, dữ liệu nhiễu và cách xử lý dữ liệu nhiễu. 1.1. Khai phá dữ liệu 1.1.1 Khái niệm. Chúng ta đang sống trong một thế giới thông tin luôn mở rộng, dữ liệu mà con ngƣời thu thập và lƣu trữ đƣợc là rất lớn và có thể vƣợt ngoài khả năng quản lý của con ngƣời. Vì vậy việc cần thiết phải tìm cách tự động phân tích dữ liệu, tự động phân loại, tóm tắt, phát hiện và mô tả các xu hƣớng trong nó là hết sức quan trọng và cần thiết trong các lĩnh vực nhƣ trong y tế, phân tích thị trƣờng, giáo dục, kỹ thuật sản xuất, quan hệ khách hàng, ngân hàng tài chính, phát hiện xâm nhập, điều tra tội phạm, tin sinh học.. Dữ liệu ngày càng tăng nhanh và đa dạng trong các lĩnh vực nhƣ vậy, rõ ràng các phƣơng pháp thủ công truyền thống áp dụng để phân tích dữ liệu sẽ không hiệu quả, tốn kém và dễ dẫn đến những sai lệch. Do đó để có thể khai phá hiệu quả các cơ sở dữ liệu lớn cần phải có những kỹ thuật mới, các kỹ thuật khai phá dữ liệu (Data Mining). Dữ liệu do con ngƣời tạo ra ngày càng nhiều hơn về số lƣợng, tăng nhanh về khối lƣợng, phát triển mạnh về quy mô khiến việc phân loại, lựa chọn, khai thác, sử dụng gặp những khó khăn nhất định. Khái niệm về khai phá dữ liệu (Data Mining) ra đời hỗ trợ công việc này. Do sự phát triển nhanh chóng về phạm vi áp dụng và các phƣơng pháp tìm kiếm tri thức, nên đã có nhiều quan điểm khác nhau về khai phá dữ liệu. 5 Nhƣng ở một mức độ trừu tƣợng nhất định chúng ta định nghĩa khai phá dữ liệu nhƣ sau: Khai phá dữ liệu (đôi khi đƣợc gọi là dữ liệu hoặc khám phá tri thức) là quá trình phân tích dữ liệu từ những quan điểm khác nhau, tổng hợp nó thành thông tin có ích. 1.1.2 Quá trình khai phá dữ liệu Quá trình khai phá dữ liệu đƣợc thực hiện qua các bƣớc sau: 1) Nghiên cứu lĩnh vực: Cần nghiên cứu lĩnh vực cần sử dụng Data mining để xác định đƣợc những tri thức ta cần chắt lọc, từ đó định hƣớng để tránh tốn thời gian cho những tri thức không cần thiết. 2) Tạo tập tin dữ liệu đầu vào: Xây dựng tập tin để lƣu trữ các dữ liệu đầu vào để máy tính có thể lƣu trữ và xử lý. 3) Tiền xử lý, làm sạch, mã hóa: Ở bƣớc này ta tiến hành bỏ bớt những dữ liệu rƣờm rà, không cần thiết, tinh chỉnh lại cấu trúc của dữ liệu và mã hóa chúng để tiện cho quá trình xử lý. 4) Rút gọn chiều: Thông thƣờng một tập dữ liệu có chiều khá lớn sẽ sinh ra một lƣợng dữ liệu khổng lồ, ví dụ với n chiều ta sẽ có 2n tổ hợp. Do đó, đây là một bƣớc quan trọng giúp giảm đáng kể hao tổn về tài nguyên trong quá trình xử lý tri thức. 5) Chọn tác vụ khai phá dữ liệu: Để đạt đƣợc mục đích ta cần, ta cần chọn đƣợc tác vụ khai phá dữ liệu sao cho phù hợp. Thông thƣờng có các tác vụ sau: * Đặc trƣng (feature) * Phân biệt (discrimination) * Kết hợp (association) * Phân lớp (classification) * Gom cụm (clusterity) 6 * Xu thế (trend analysis) * Phân tích độ lệch * Phân tích hiếm 6) Chọn các thuật giải Khai phá dữ liệu 7) Khai phá dữ liệu: Tìm kiếm tri thức Sau khi tiến hành các bƣớc trên thì đây là bƣớc chính của cả quá trình, ta sẽ tiến hành khai thác và tìm kiếm tri thức. 8) Đánh giá mẫu tìm đƣợc: Cần đánh giá lại xem trong các tri thức tìm đƣợc, ta sẽ sử đụng đƣợc những tri thức nào, những tri thức nào dƣ thừa, không cần thiết 9) Biểu diễn tri thức: Biểu diễn tri thức vừa thu thập đƣợc dƣới dạng ngôn ngữ tự nhiên và hình thức sao cho ngƣời dùng có thể hiểu đƣợc những tri thức đó. 10) Sử dụng các tri thức vừa khám phá Hình 1: Quá trình khai phá tri thức [11] 7 1.1.3 Các kỹ thuật khai phá dữ liệu Tùy thuộc vào các loại dữ liệu và các ứng dụng khác nhau sẽ sử dụng các kỹ thuật khai phá dữ liệu phù hợp. Hiện nay có một số kỹ thuật khai phá dữ liệu đƣợc áp dụng nhiều nhƣ Khai phá luật kết hợp, phân loại, phân cụm, dự đoán, mẫu tuần tự, cây quyết định... Luật kết hợp: là một trong những kỹ thuật khai thác dữ liệu nổi tiếng nhất. Trong luật kết hợp, một mô hình đƣợc phát hiện dựa trên mối quan hệ giữa các hạng mục trong cùng một giao dịch. Đó là lý do tại sao khai phá luật kết hợp cũng đƣợc gọi là kỹ thuật liên kết . Kỹ thuật liên kết đƣợc sử dụng trong phân tích giỏ hàng để xác định một tập hợp các sản phẩm mà khách hàng thƣờng mua với nhau. Các nhà bán lẻ đang sử dụng kỹ thuật hiệp hội để nghiên cứu thói quen mua của khách hàng. Dựa vào dữ liệu bán hàng trƣớc đây, các nhà bán lẻ có thể nhận ra rằng khách hàng luôn mua khoai tây chiên khi họ mua bia, và do đó họ có thể đặt bia và khoai tây chiên cạnh nhau để tiết kiệm thời gian cho khách hàng và tăng doanh thu. Phân lớp: là một kỹ thuật khai phá dữ liệu cổ điển dựa trên học máy. Về cơ bản, phân lớp đƣợc sử dụng để phân lớp mỗi mục trong một bộ dữ liệu thành một trong một nhóm các nhóm hoặc nhóm đƣợc xác định trƣớc. Phƣơng pháp phân lớp sử dụng các kỹ thuật toán học nhƣ cây quyết định, lập trình tuyến tính, mạng nơ-ron và thống kê. Trong phân lớp, đã có nhiều nhà phát triển các phần mềm có thể học cách phân lớp các mục dữ liệu thành các nhóm. Ví dụ, phân lớp trong ứng dụng "cho tất cả hồ sơ của nhân viên rời khỏi công ty, dự đoán ai sẽ rời khỏi công ty trong thời gian tới" Trong trƣờng hợp này, hồ sơ của nhân viên đƣợc chia thành hai nhóm có tên "bỏ đi" và "ở lại". Và sau đó chúng ta có thể yêu cầu phần mềm khai thác dữ liệu phân lớp nhân viên vào các nhóm riêng biệt. 8 Phân cụm: là một kỹ thuật khai thác dữ liệu làm cho một cụm các đối tƣợng có ý nghĩa hoặc có ích có các đặc tính tƣơng tự sử dụng kỹ thuật tự động. Kỹ thuật phân cụm định nghĩa các lớp và đặt các đối tƣợng trong mỗi lớp, trong khi trong kỹ thuật phân lớp, các đối tƣợng đƣợc gán vào các lớp đƣợc xác định trƣớc. Để làm cho khái niệm rõ ràng hơn, chúng ta có thể quản lý cuốn sách trong thƣ viện làm ví dụ. Trong thƣ viện, có rất nhiều sách về các chủ đề có sẵn. Thách thức là làm thế nào để giữ cho những cuốn sách theo cách mà ngƣời đọc có thể tham gia một số cuốn sách về một chủ đề cụ thể mà không có rắc rối. Bằng cách sử dụng kỹ thuật xếp nhóm, chúng tôi có thể giữ các sách có một số loại tƣơng đồng trong một cụm hoặc một kệ và gắn nhãn nó với một cái tên có ý nghĩa. Nếu độc giả muốn lấy sách trong chủ đề đó. Dự đoán: là một trong những kỹ thuật khai phá dữ liệu phát hiện mối quan hệ giữa các biến độc lập và mối quan hệ giữa các biến phụ thuộc và độc lập . Ví dụ , kỹ thuật phân tích dự đoán có thể đƣợc sử dụng trong bán để dự đoán lợi nhuận trong tƣơng lai nếu chúng ta coi việc bán là một biến độc lập, lợi nhuận có thể là một biến phụ thuộc. Sau đó dựa trên số liệu bán và lợi nhuận trong quá khứ, chúng ta có thể vẽ đƣờng cong hồi quy đƣợc sử dụng để dự đoán lợi nhuận. Phân tích mẫu tuần tự là một trong kỹ thuật khai thác dữ liệu nhằm tìm kiếm hoặc xác định mô hình tƣơng tự, các sự kiện hoặc xu hƣớng thƣờng xuyên trong dữ liệu giao dịch trong một khoảng thời gian kinh doanh. Trong bán hàng, với dữ liệu giao dịch lịch sử, các doanh nghiệp có thể xác định một bộ các mặt hàng mà khách hàng mua với nhau vào những thời điểm khác nhau trong năm. Sau đó, các doanh nghiệp có thể sử dụng thông tin này để khuyến nghị khách hàng mua nó với các giao dịch tốt hơn dựa trên tần số mua hàng của họ trong quá khứ. 9 Cây quyết định: là một trong những kỹ thuật khai thác dữ liệu đƣợc sử dụng phổ biến nhất vì mô hình của nó rất dễ hiểu đối với ngƣời dùng. Trong kỹ thuật cây quyết định, gốc của cây quyết định là một câu hỏi đơn giản hoặc điều kiện có nhiều câu trả lời. Mỗi câu trả lời sau đó dẫn đến một tập hợp các câu hỏi hoặc điều kiện giúp chúng tôi xác định dữ liệu để chúng tôi có thể đƣa ra quyết định cuối cùng dựa trên nó. Tùy thuộc vào nhu cầu phân tích dữ liệu mà ngƣời ta có thể sử dụng đơn lẻ từng kỹ thuật hoặc kết hợp các kỹ thuật để đạt kết quả nhƣ mong muốn. 1.2. Phân lớp. 1.2.1. Giới thiệu phân lớp Phân lớp là một trong những kỹ thuật khai thác dữ liệu đƣợc sử dụng chủ yếu để phân tích một tập dữ liệu và với mỗi trƣờng hợp của nó đƣợc cho một lớp sao cho lỗi phân lớp là ít nhất. Nó đƣợc sử dụng để trích xuất các mô hình, xác định chính xác các lớp dữ liệu quan trọng trong tập dữ liệu cho trƣớc. Phân lớp là một quá trình gồm hai bƣớc [24] đó là xây dựng mô hình hay chính là xây dựng phân lớp và sử dụng mô hình Bước thứ nhất: Xây dựng mô hình (learning). Xây dựng mô hình là mô tả một tập hợp các lớp đƣợc xác định trƣớc. Mỗi bộ hoặc mẫu đƣợc giả định là thuộc về một lớp đƣợc xác định trƣớc, đƣợc xác định bởi thuộc tính của nhãn lớp. Tập hợp các bộ ký tự dùng để xây dựng mô hình là tập huấn luyện. Mô hình đƣợc biểu diễn dƣới dạng các quy tắc phân loại, cây quyết định hoặc các công thức toán học. Bước thứ 2: sử dụng mô hình (classification) Bƣớc này là bƣớc phân lớp. Ở đây dữ liệu kiểm thử đƣợc sử dụng để ƣớc tính độ chính xác của các quy tắc phân lớp. Các quy tắc phân lớp có thể 10 đƣợc áp dụng cho bộ dữ liệu mới nếu độ chính xác đƣợc coi là chấp nhận đƣợc.Vì vậy, phân lớp là quá trình gán nhãn lớp từ bộ dữ liệu có nhãn lớp không biết. Độ chính xác của quy tắc phân lớp đƣợc ƣớc tính và nếu nó là tìm thấy chấp nhận đƣợc sau đó áp dụng cho các bộ dữ liệu khác. Các vấn đề phân lớp đơn giản nhất là phân lớp nhị phân mà chỉ có hai giá trị thấp và cao. Cái khác vấn đề phân lớp đã có hơn hai giá trị. Có kỹ thuật khác nhau đƣợc sử dụng để phân lớp dữ liệu để xác định mối quan hệ giữa các giá trị của các yếu tố dự báo và giá trị của mục tiêu. Các phƣơng pháp thƣờng đƣợc sử dụng để khai phá dữ liệu nhiệm vụ phân lớp có thể đƣợc phân loại thành các nhóm sau đây Phƣơng pháp dựa trên cây quyết định Phƣơng pháp dựa trên luật Dựa trên bộ nhớ học tập Các mạng Neural Mạng Bayes Máy vector hỗ trợ. 1.2.2. Một số vấn đề liên quan đến phân lớp dữ liệu Vấn đề chính là chuẩn bị dữ liệu cho phân lớp và nó liên quan đến các hoạt động sau: Vệ sinh dữ liệu: Làm sạch dữ liệu bao gồm việc loại bỏ nhiễu và sửa chữa các giá trị bị thiếu. Nhiễu đƣợc gỡ bỏ bằng cách áp dụng các kỹ thuật làm mịn và vấn đề thiếu giá trị đƣợc giải quyết bằng cách thay thế giá trị còn thiếu bằng giá trị phổ biến nhất cho thuộc tính đó. Phân tích sự liên quan dữ liệu: Cơ sở dữ liệu cũng có thể có các thuộc tính không liên quan. Phân tích tƣơng quan đƣợc sử dụng để biết liệu có hai thuộc tính nào có liên quan hay không. 11 Chuyển đổi và giảm dữ liệu: Dữ liệu có thể đƣợc chuyển đổi bằng bất kỳ phƣơng pháp nhƣ: +Chuẩn hóa: Dữ liệu đƣợc chuyển đổi bằng cách sử dụng chuẩn hóa. Việc chuẩn hóa liên quan đến việc mở rộng tất cả các giá trị cho thuộc tính cho trƣớc để làm cho chúng rơi vào một phạm vi quy định nhỏ. Chuẩn hóa đƣợc sử dụng khi ở bƣớc học tập, các mạng thần kinh hoặc các phƣơng pháp đo lƣờng đƣợc sử dụng. +Tổng quát: Các dữ liệu cũng có thể đƣợc chuyển đổi bằng cách tổng quát hóa nó với khái niệm cao hơn. Với mục đích này, chúng ta có thể sử dụng các hệ thống phân cấp khái niệm. Tiếp theo là so sánh các phƣơng pháp phân lớp. Đây là tiêu chí để so sánh các phƣơng pháp phân lớp Độ chính xác: Độ chính xác của phân loại là khả năng phân loại. Nó dự đoán nhãn lớp một cách chính xác và độ chính xác của dự đoán đƣợc đề cập đến mức độ dự báo cho trƣớc có thể đoán đƣợc giá trị của thuộc tính dự đoán cho một dữ liệu mới. Tốc độ: Điều này đề cập đến chi phí tính toán trong việc tạo ra và sử dụng phân loại hoặc dự đoán. Tính mạnh mẽ: Nó đề cập đến khả năng phân loại hoặc dự đoán để đƣa ra dự đoán chính xác từ dữ liệu ồn ào. Khả năng mở rộng: Khả năng mở rộng đề cập đến khả năng để xây dựng các phân lớp hoặc dự đoán một cách hiệu quả; Cho số lƣợng lớn dữ liệu. Khả năng giải thích: Nó đề cập đến mức độ phân lớp hoặc dự đoán đã hiểu. 1.3. Phân lớp mất cân bằng Phân lớp mất cân bằng xuất hiện ở nhiều lĩnh vực quan trọng và đòi hỏi nhiều thách thức khác nhau từ viễn thám, tràn dầu, lỗi máy móc và phát hiện 12