Tài liệu Nghiên cứu phương pháp học máy cho phân lớp dữ liệu học viên tạo nguồn phát triển đảng

  • Số trang: 82 |
  • Loại file: PDF |
  • Lượt xem: 28 |
  • Lượt tải: 0
thanhphoquetoi

Tham gia: 05/11/2015

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRẦN THỊ LƢƠNG TRƢỜNG ĐẠI HỌC MỞ HÀ NỘI LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN NGHİÊN CỨU PHƢƠNG PHÁP HỌC MÁY CHO PHÂN LỚP DỮ LİỆU HỌC VİÊN TẠO NGUỒN PHÁT TRİỂN ĐẢNG TRẦN THỊ LƢƠNG 2016-2018 HÀ NỘI - 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC MỞ HÀ NỘI LUẬN VĂN THẠC SỸ NGHİÊN CỨU PHƢƠNG PHÁP HỌC MÁY CHO PHÂN LỚP DỮ LİỆU HỌC VİÊN TẠO NGUỒN PHÁT TRİỂN ĐẢNG TRẦN THỊ LƢƠNG CHUYÊN NGÀNH : CÔNG NGHỆ THÔNG TIN MÃ SỐ: 8.48.02.01 NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN QUANG HOAN HÀ NỘI - 2018 LỜI CAM ĐOAN Tôi 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ả nêu trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác. Hà Nội, ngày tháng năm 2018 HỌC VIÊN Trần Thị Lƣơng i LỜI CẢM ƠN Em xin chân thành cảm ơn Trƣờng Đại học Kỹ thuật - Hậu cần CAND, Khoa Công nghệ thông tin - Trƣờng Đại học Mở Hà Nội đã tạo điều kiện thuận lợi giúp em hoàn thành luận văn này. Em xin chân thành cảm ơn sự hƣớng dẫn, chỉ bảo tận tình của PGS.TS. Nguyễn Quang Hoan trong suốt thời gian thực hiện đề tài, cảm ơn thầy đã luôn dành thời gian giúp đỡ em để có thể hoàn thành đƣợc luận văn này. Em xin cảm các thầy cô giáo khoa Công nghệ thông tin - Trƣờng Đại học Mở Hà Nội đã truyền thụ kiến thức, hỗ trợ em trong suốt quá trình học tập vừa qua; Cảm ơn bạn bè, đồng nghiệp, gia đình và những ngƣời thân yêu đã luôn đồng hành, tạo mọi điều kiện, động viên giúp đỡ em trong quá trình học tập, công tác để hoàn thành khóa học và luận văn này. ii MỤC LỤC LỜI CAM ĐOAN ............................................................................................. i LỜI CẢM ƠN .................................................................................................. ii MỤC LỤC ....................................................................................................... iii DANH SÁCH CHỮ VIẾT TẮT TIẾNG VIỆT ........................................... vi DANH SÁCH BẢNG .................................................................................... vii DANH SÁCH HÌNH VẼ.............................................................................. viii LỜI MỞ ĐẦU ................................................................................................. ix CHƢƠNG 1. PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU .............................. 1 1.1. Phân lớp dữ liệu. ..............................................................................................1 1.2. Một số vấn đề liên quan đến giải quyết bài toán phân lớp dữ liệu ..................5 1.2.1. Chuẩn bị dữ liệu cho việc phân lớp ..........................................................5 1.2.2. So sánh các mô hình phân lớp ..................................................................6 1.2.3. Một số phƣơng pháp đánh giá độ chính xác mô hình phân lớp ...............7 1.3. Phƣơng pháp cây quyết định............................................................................8 1.3.1. Định nghĩa ................................................................................................8 1.3.2. Xây dựng cây quyết định ..........................................................................9 1.3.3. Các đặc trƣng trong phân lớp dữ liệu sử dụng cây quyết định ...............10 1.3.4. Các nghiên cứu giải thuật hiện nay ........................................................11 1.4. Kết luận chƣơng 1 ..........................................................................................12 CHƢƠNG 2. GIẢI THUẬT C4.5 VÀ MẠNG NƠRON NHÂN TẠO ..... 13 2.1. Giải thuật C4.5 ...............................................................................................13 2.1.1. Giới thiệu chung .....................................................................................13 2.1.2. Giải thuật C4.5 ........................................................................................13 2.1.3. C4.5 chọn thuộc tính phân loại tốt nhất ..................................................15 2.1.4. Ví dụ minh họa cho giải thuật C4.5 ........................................................16 2.2. Đánh giá cây quyết định trong phân lớp dữ liệu ............................................26 2.2.1. Ƣu điểm của cây quyết định ...................................................................26 2.2.2. Nhƣợc điểm của cây quyết định .............................................................28 2.3. Mạng nơron nhân tạo .....................................................................................28 2.3.1. Nơron sinh học: ......................................................................................28 iii 2.3.2. Nơron nhân tạo .......................................................................................30 2.3.3. Mạng nơron nhân tạo ..............................................................................32 2.3.4 Huấn luyện mạng nơron ..........................................................................35 2.4. Phƣơng pháp học lan truyền ngƣợc và sai số ................................................37 2.5. Kết luận chƣơng 2 ..........................................................................................49 CHƢƠNG 3. PHÂN LỚP DỮ LIỆU HỌC VIÊN TẠO NGUỒN ............ 50 PHÁT TRIỂN ĐẢNG ................................................................................... 50 3.1. Khảo sát và thu thập dữ liệu ..........................................................................50 3.2. Xử lý dữ liệu ..................................................................................................50 3. 3. Phân lớp dữ liệu học viên sử dụng thuật toán C4.5 ......................................53 3.3.1. Áp dụng giải thuật ..................................................................................53 3.3.2. Xây dựng cây quyết định ........................................................................53 3.4. Phân lớp cán bộ sử dụng mạng nơron nhân tạo .............................................53 3.5. Giới thiệu một số ngôn ngữ trong khai phá dữ liệu .......................................53 3.5.1. Giới thiệu về ngôn ngữ R .......................................................................53 3.5.2. Giới thiệu về phần mềm Weka ...............................................................54 3.6. Kết quả thực nghiệm ......................................................................................55 3.6.1. Chạy giải thuật J48 trên ngôn ngữ Weka ...............................................55 3.6.2. Chạy giải thuật mạng nơron trên ngôn ngữ Weka .................................58 3.7. Kết luận chƣơng 3 ..........................................................................................60 KẾT LUẬN .................................................................................................... 61 TÀI LIỆU THAM KHẢO ............................................................................ 62 PHỤ LỤC ....................................................................................................... 63 iv DANH SÁCH THUẬT NGỮ VIẾT TẮT TIẾNG ANH Viết tắt Tiếng Anh Tiếng Việt Evolutionary Programming Lập trình tiến hóa Genetic Algorithm Thuật toán GAs Negative Số mẫu âm Negative Predictive Value Giá trị tiên đoán âm Positive Số mẫu dƣơng PPV Positive Predictive Value Giá trị tiên đoán dƣơng TN True Nagative Thực âm True Nagative Rate Tỷ lệ thực âm True Positive Thực dƣơng TPR True Positive Rate Tỷ lệ thực dƣơng GR Gain Ratio Tỉ số độ lợi IG Information Gain Độ lợi thông tin Accuracy Độ chính xác EP GAs N NPV P TNR TP ACC v DANH SÁCH CHỮ VIẾT TẮT TIẾNG VIỆT Chữ gốc Chữ viết tắt Công an nhân dân CAND Công nhận đối tƣợng CNDT Phân loại học viên PLHV Trung bình TB Có giấy khen CGK Cán bộ đi học CBDH Học sinh phổ thông HSPT Đoàn viên ƣu tú DVUT Công nhận đối tƣợng CNDT Xuất sắc XS Công an trung ƣơng CATW Quyết định QD Phân loại rèn luyện PLRL Kết nạp đảng KND Có C Không K Cơ sở dữ liệu CSDL Ngôn ngữ truy vấn mang tính cấu trúc SQL vi DANH SÁCH BẢNG Bảng 2.1: Bảng cơ sở dữ liệu dự đoán đối tƣợng kết nạp đảng có DVUT = C ........17 Bảng 2.2: Một số hàm H(s) thƣờng dùng cho mô hình nơron nhân tạo ...................31 Bảng 2.3: Một số hàm phi tuyến thƣờng đƣợc sử dụng trong các mô hình nơron ...32 Bảng 2.4: Ma trận nhầm lẫn ......................................................................................47 Bảng 3.1: Bảng cơ sở tri thức....................................................................................52 vii DANH SÁCH HÌNH VẼ Hình 1.1: Quá trình phân lớp dữ liệu - Bƣớc xây dựng mô hình phân lớp .................2 Hình 1.2: Quá trình phân lớp dữ liệu - Ƣớc lƣợng độ chính xác của mô hình ...........3 Hình 1.3: Quá trình phân lớp dữ liệu - Phân lớp dữ liệu mới .....................................4 Hình 1.4: Ƣớc lƣợng độ chính xác của mô hình phân lớp với phƣơng pháp holdout 7 Hình 1.5: Ví dụ về cây quyết định ..............................................................................8 Hình 2.1: Ví dụ Cây quyết định hoàn chỉnh .............................................................23 Hình 2.2: Mô hình nơron sinh học ............................................................................29 Hình 2.3: Mô hình nơron nhân tạo ............................................................................30 Hình 2.4: Sơ đồ đơn giản về một mạng nơron nhân tạo ...........................................33 Hình 2.5: Mạng truyền thẳng một lớp .......................................................................34 Hình 2.6: Mạng truyền thẳng nhiều lớp. ...................................................................34 Hình 2.7: Các dạng học .............................................................................................36 Hình 2.8: Mạng truyền thẳng nhiều lớp ....................................................................38 Hình 2.9: Cấu trúc mạng lan truyền ngƣợc ...............................................................40 Hình 3.1: Kết quả Classifer Output .........................................................................566 Hình 3.2: Cây quyết định sử dụng giải thuật C4.5 trong Weka ................................57 Hình 3.3: Kết quả Classifer Output ...........................................................................58 Hình 3.4: Mạng nơron trong Weka .......................................................................5959 viii LỜI MỞ ĐẦU 1. Lý do chọn đề tài Công tác phát triển Đảng của trƣờng Đại học Kỹ thuật - Hậu cần CAND trong những năm gần đây rất đƣợc Đảng ủy quan tâm chú trọng cả về chất lƣợng và số lƣợng. Số lƣợng đảng viên đƣợc kết nạp sau mỗi năm học ngày càng tăng lên; tuy nhiên, quá trình xét kết nạp, công nhận đối tƣơng phát triển đảng còn nhiều bất cập, chƣa đáp ứng đƣợc nhu cầu thực tế: Chƣa có công cụ hỗ trợ quản lý đánh giá các tiêu chí kết nạp đảng một cách chính xác, minh bạch; việc xem xét kết nạp đảng nhiều khi còn bỏ sót những quần chúng ƣu tú, có nguyện vọng đƣợc đứng trong hàng ngũ của Đảng. Xuất phát từ thực tế công tác, tôi đã tìm hiểu, nghiên cứu về phƣơng pháp phân lớp dữ liệu mà cụ thể ở đây là giải thuật cây quyết định J48 và mạng nơron để phân lớp dữ liệu theo phƣơng pháp học máy với hy vọng tìm ra quy luật, các đặc trƣng tác động đến việc xem xét kết nạp Đảng để có thể giới thiệu nguồn phát triển Đảng cho Đảng ủy Nhà trƣờng đƣợc nhanh nhất và chính xác nhất Với những lý do trên, tôi chọn đề tài “Nghiên cứu phương pháp học máy cho phân lớp dữ liệu học viên tạo nguồn phát triển đảng”. 2. Mục tiêu, đối tƣợng và phạm vi nghiên cứu - Mục tiêu: Phân lớp dữ liệu học viên trƣờng Đại học Kỹ thuật - Hậu cần CAND dựa trên giải thuật C4.5 và Mạng nơron. - Đối tƣợng nghiên cứu: Đối tƣợng nghiên cứu của luận văn là dữ liệu về học viên trƣờng Đại học Kỹ thuật - Hậu cần CAND. - Phạm vi nghiên cứu: Giới hạn thử nghiệm phân lớp theo 6 đặc trƣng và 164 bản ghi đầu vào đƣợc cho là cơ bản nhất; sau đó có thể mở rộng thêm các đặc trƣng cũng nhƣ các bản ghi khác. ix 3. Bố cục luận văn Luận văn đƣợc chia thành ba chƣơng có nội dung nhƣ sau: Luận văn gồm các phần chính sau: - Phần mở đầu - Chƣơng 1: Phƣơng pháp phân lớp dữ liệu - Chƣơng 2: Giải thuật C4.5 và Mạng nơron nhân tạo - Chƣơng 3: Phân lớp dữ liệu học viên tạo nguồn phát triển đảng trƣờng Đại học Kỹ thuật - Hậu cần CAND - Kết luận: Tổng kết các kết quả đã đạt đƣợc của luận văn và hƣớng nghiên cứu tiếp theo. x CHƢƠNG 1. PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU 1.1. Phân lớp dữ liệu. Phân lớp dữ liệu là kỹ thuật dựa trên tập huấn luyện và những giá trị hay là nhãn của lớp trong một thuộc tính phân lớp và sử dụng nó trong việc phân lớp dữ liệu mới. Phân lớp dữ liệu cũng là tiên đoán loại lớp của nhãn. Bên cạnh kỹ thuật phân lớp có một hình thức tƣơng tự là kỹ thuật tiên đoán, kỹ thuật tiên đoán khác với phân lớp ở chỗ phân lớp chỉ liên quan đến tiên đoán loại lớp của nhãn còn kỹ thuật tiên đoán mô hình là những hàm đánh giá liên tục. Ví dụ: Nhờ các quy luật về xu hƣớng mua hàng của khách hàng trong siêu thị mà nhân viên kinh doanh có thể đƣa ra những quyết sách đúng đắn về số lƣợngmặt hàng, chủng loại bày bán Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm của các nhà nghiên cứu trong nhiều lĩnh vực khác nhau nhƣ học máy (Machine Learning), hệ chuyên gia (Expert System), thống kê (Statistics),... Công nghệ này cũng đƣợc ứng dụng trong nhiều lĩnh vực khác nhau nhƣ: Thƣơng mại, maketing, nhà băng, nghiên cứu thị trƣờng, bảo hiểm, y tế, giáo dục,... Phần lớn các giải thuật ra đời đều sử dụng cơ chế dữ liệu cƣ trú trong bộ nhớ (Memory Resident), thƣờng thao tác với lƣợng dữ liệu nhỏ. Một số giải thuật ra đời sau này đã sử dụng kỹ thuật cƣ trú trên đĩa cải thiện đáng kể khả năng mở rộng của giải thuật với những tập dữ liệu lớn lên tới hàng tỷ bản ghi. Quá trình phân lớp dữ liệu gồm hai bƣớc [9]:  Bước thứ nhất Quá trình học nhằm xây dựng một mô hình mô tả một tập các lớp dữ liệu hay các khái niệm định trƣớc. Đầ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), hay ví dụ (Example), đối tượng (Objiect), bản ghi (Record) hay trường hợp (Case).Lớp ở đây là giá trị của một thuộc tính đƣợc chọn làm thuộc tính gán nhãn lớp hay thuộc tính phân lớp (Class lable attribute). Đầu ra của bƣớc này 1 thƣờng là các quy tắc phân lớp dƣới dạng luật if - then, cây quyết định, công thức logic hay mạng nơron. Quá trình này đƣợc mô tả nhƣ trong Hình 1.1 Giải thuật phân lớp Dữ liệu huấn luyện Bộ phân lớp Tuoi NN Chon 25 Anh Yes 35 Anh Yes IF Tuoi <= 35 or NN = Anh THEN Chon = Yes 40 Anh No 27 Pháp No 32 Trung No 30 Anh Yes 32 Anh Yes 40 Pháp No Hình 1.1: Quá trình phân lớp dữ liệu - Bước xây dựng mô hình phân lớp Xây dựng mô hình là mô tả một tập những lớp đƣợc định nghĩa trƣớc, trong đó: mỗi bộ hoặc mẫu đƣợc gán thuộc về một lớp đƣợc định nghĩa trƣớc nhƣ là đƣợc xác định bởi thuộc tính nhãn lớp, tập hợp của những bộ đƣợc sử dụng trong việc sử dụng mô hình đƣợc gọi là tập huấn luyện. Mô hình đƣợc biểu diễn là những luật phân lớp, cây quyết định và những công thức toán học.  Bước thứ hai Trong bƣớc này dùng mô hình đã xây dựng ở bƣớc trƣớc để phân lớp dữ liệu mới. Trƣớc tiên độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo ra đƣợc ƣớc lƣợng. Holdout là một kỹ thuật đơn giản để ƣớc lƣợng độ chính xác. Kỹ thuật này 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. Các mẫu này đƣợc chọn ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu huấn luyện. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đƣa là tỉ lệ phần trăm 2 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 đƣợc ƣớc lƣợng dựa trên tập dữ liệu huấn luyện thì kết quả thu đƣợc là rất khả quan vì mô hình luôn có xu hƣớng “quá vừa” dữ liệu. Quá vừa dữ liệu là hiện tƣợng kết quả phân lớp trùng khít với dữ liệu thực tế vì quá trình xây dựng mô hình phân lớp từ tập dữ liệu huấn luyện tạo có thể đã kết hợp những đặc điểm riêng biệt của tập dữ liệu đó. Do vậy cần sử dụng một tập dữ liệu kiểm tra độc lập với tập dữ liệu huấn luyện. 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. Bộ phân lớp Tập dữ liệu kiểm tra Tuoi 27 34 36 44 NN Anh Phap Trung Anh Chon Yes No No Yes Chon Yes No No No Hình 1.2: Quá trình phân lớp dữ liệu - Ước lượng độ chính xác của mô hình 3 Bộ phân lớp (Mô hình) Tập dữ liệu mới Tuoi 27 34 36 34 NN Anh Phap Trung Anh Chon Yes No No Yes Chon Yes No No No Hình 1.3: Quá trình phân lớp dữ liệu - Phân lớp dữ liệu mới Việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ liệu trong tƣơng lai hoặc phân lớp cho những đối tƣợng chƣa biết đến. Trƣớc khi sử dụng mô hình ngƣời ta thƣờng phải đánh giá tính chính xác của mô hình. Trong đó: nhãn đƣợc biết của mẫu kiểm tra đƣợc so sánh với kết quả phân lớp của mô hình, độ chính xác là phần trăm của tập hợp mẫu kiểm tra mà phân loại đúng bởi mô hình, tập kiểm tra là độc lập với tập huấn luyện. Phân lớp là một hình thức học đƣợc giám sát tức là: tập dữ liệu huấn luyện (quan sát, thẩm định v.v.) đi đôi với những nhãn chỉ định lớp quan sát, những dữ liệu mới đƣợc phân lớp dựa trên tập huấn luyện . Ngƣợc lại với hình thức học đƣợc giám sát là hình thức học không đƣợc giám sát lúc đó nhãn lớp của tập dữ liệu huấn luyện là không đƣợc biết đến. Trong mô hình phân lớp, giải thuật phân lớp dữ vai trò trung tâm, quyết định tới sự thành công của mô hình phân lớp. Do vậy, chìa khóa của vấn đề phân lớp dữ liệu là tìm ra đƣợc một giải thuật phân lớp nhanh, hiệu quả, có độ chính xác cao và có khả năng mở rộng đƣợc. Trong đó, khả năng mở rộng đƣợc của giải thuật đƣợc đặc biệt trú trọng và phát triển [9]. * Các phƣơng pháp ứng dụng trong phân lớp dữ liệu: - Phân lớp cây quyết định - Mạng nơron 4 - Các giải thuật di truyền - Bộ phân lớp Bayesian (Bayesian Classifier) - Mô hình phân lớp K-hàng xóm gần nhất - Phân tích thống kê - Phƣơng pháp tập thô (Rough Set Approach) * Phát biểu bài toán của luận văn - Cho Cơ sở dữ liệu là danh sách học viên của trƣờng Đại học Kỹ thuật - Hậu cần CAND. Gồm 6 đặc trƣng đầu vào (Kết quả phân loại học viên; kết quả rèn luyện; cảm tình đảng; đoàn viên ƣu tú; học lớp đối tƣợng; đối tƣợng) và 3 đầu ra (Kết nạp đảng; công nhận đối tƣợng và không). - Sử dụng giải thuật học toán C4.5 và mạng Nơron để phân lớp dữ liệu học viên; So sánh kết quả của hai giải thuật và đánh giá độ chính xác phân lớp của hai giải thuật trên. 1.2. Một số vấn đề liên quan đến giải quyết bài toán phân lớp dữ liệu 1.2.1. Chuẩn bị dữ liệu cho việc phân lớp Công việc đầu tiên là tiền xử lý dữ liệu cho quá trình phân lớp là một việc làm không thể thiếu và có vai trò quan trọng quyết định tới việc có áp dụng đƣợc mô hình phân lớp hay không. Quá trình tiền xử lý dữ liệu sẽ giúp cải thiện độ chính xác, tính hiệu quả và khả năng mở rộng đƣợc của mô hình phân lớp. Quá trình tiền xử lý dữ liệu gồm các công việc sau: -Làm sạch dữ liệu: Làm sạch dữ liệu liên quan đến việc xử lý lỗi và giá trị thiếu trong tập dữ liệu ban đầu. Trong đó lỗi là các lỗi ngẫu nhiên hay các giá trị không hợp lệ của các biến trong tập dữ liệu. Để xử lý với tập lỗi này có thể dùng kỹ thuật làm trơn. Giá trị thiếu là những ô không có giá trị của các thuộc tính. Giá trị lỗi có thể do lỗi chủ quan trong quá trình nhập liệu hoặc trong trƣờng hợp cụ thể giá trị của các thuộc tính đó không có, hay không quan trọng. Kỹ thuật xử lý ở đây có thể thay giá trị thiếu bằng giá trị phổ biến nhất của thuộc tính đó hoặc bằng giá trị có thể xảy ra nhất dựa trên thống kê. Mặc dù phần lớn giải thuật phân lớp đều có cơ chế xử lý với những giá trị thiếu và lỗi trong tập dữ liệu, nhƣng bƣớc tiền xử lý này có thể làm giảm sự hỗn độn trong quá trình học (xây dựng mô hình phân lớp). 5 - Phân tích sự cần thiết của dữ liệu: Có rất nhiều thuộc tính trong tập dữ liệu có thể hoàn toàn không cần thiết hay liên quan đến một bài toán phân lớp cụ thể. Ví dụ dữ liệu về ngày trong tuần hoàn toàn không cần thiết đối với ứng dụng phân tích độ rủi ro của các khoản tiền cho vay của ngân hàng, nên thuộc tính này là dƣ thừa. Phân tích sự cần thiết của dữ liệu nhằm mục đích loại bỏ những thuộc tính không cần thiết, dƣ thừa khỏi quá trình học vì những thuộc tính đó sẽ làm chậm, phức tạp và gây ra sự hiểu sai trong quá trình học dẫn tới một mô hình phân lớp không dùng đƣợc. - Chuyển đổi dữ liệu: Việc khái quát hóa dữ liệu lên mức khái niệm cao hơn đôi khi là cần thiết trong quá trình tiền xử lý. Việc này đặc biệt hữu ích với những thuộc tính liên tục. Với những thuộc tính rời rạc nhƣ địa chỉ phố có thể đƣợc khái quát hóa lên thành phố. Việc khái quát hóa làm cô đọng dữ liệu học nguyên thủy, vì vậy các thao tác vào, ra liên quan đến quá trình học sẽ giảm. 1.2.2. So sánh các mô hình phân lớp Trong từng trƣờng hợp cụ thể cần lựa chọn mô hình phân lớp phù hợp. Việc lựa chọn đó căn cứ vào sự so sánh các mô hình phân lớp khác nhau, dựa trên các tiêu chuẩn sau: - Độ chính xác dự đoán (Predictive Accuracy): Độ chính xác là khả năng của mô hình để dự đoán chính xác nhãn lớp của dữ liệu mới hay dữ liệu chƣa biết. - Tốc độ (Speed): Tốc độ là chi phí tính toán liên quan đến quá trình tạo ra và sử dụng mô hình. - Sức mạnh (Robustness): Sức mạnh là khả năng mô hình tạo ra những dự đoán đúng từ những dữ liệu lỗi hay dữ liệu với những giá trị thiếu. - Khả năng mở rộng (Scalability): là khả năng thực thi hiệu quả trên lƣợng lớn dữ liệu của mô hình đã học. - Tính hiểu được (interpretability): Tính hiểu đƣợc là mức độ hiểu và hiểu rõ những kết quả sinh ra bởi mô hình đã học. - Tính đơn giản (Simplicity): Tính đơn giản liên quan đến kích thƣớc của cây quyết định hay độ cô đọng của các luật, càng đơn giản càng hiệu quả. Trong các tiêu chuẩn trên, khả năng mở rộng của mô hình phân lớp đƣợc nhấn mạnh và chú trọng phát triển, đặc biệt với cây quyết định [9]. 6 1.2.3. Một số phương pháp đánh giá độ chính xác mô hình phân lớp Độ chính xác của bộ phân lớp là quan trọng ở chỗ nó cho phép dự đoán đƣợc độ chính xác của các kết quả phân lớp những dữ liệu tƣơng lai. Độ chính xác còn giúp so sánh các mô hình phân lớp khác nhau. Dƣới đây là hai phƣơng pháp đánh giá phổ biến là holdout và k-fold cross-validation. Cả hai phƣơng pháp này đều dựa trên các phân hoạch ngẫu nhiên tập dữ liệu ban đầu.  Phương pháp holdout Dữ liệu đƣa ra đƣợc phân chia ngẫu nhiên thành 2 phần là: tập dữ liệu đào tạo và tập dữ liệu kiểm tra. Thông thƣờng 2/3 dữ liệu cấp cho dữ liệu đào tạo, phần còn lại cho tập dữ liệu kiểm tra [9]. Lấy từ bộ Tập dữ liệu đào tạo phân lớp Dữ liệu Ƣớc lƣợng độ chính xác Tập dữ liệu kiểm tra Hình 1.4: Ước lượng độ chính xác của mô hình phân lớp với phương pháp holdout Phương pháp k-fold cross-validation Tập dữ liệu ban đầu đƣợc chia ngẫu nhiên thành k tập con có kích thƣớc xấp xỉ nhau S1,S2,…,Sk. Quá trình phân lớp và test đƣợc thực hiện k lần. Tại lần lặp thứ i, Si là tập dữ liệu kiểm tra, các tập còn lại hợp thành tập dữ liệu đào tạo. Có nghĩa là đầu tiên việc phân lớp đƣợc thực hiện trên các tập S2, S3,…Sk sau đó test trên tập S1, tiếp tục quá trình phân lớp đƣợc thực hiện trên tập S2,S3,S4,…,Sk sau đó test trên 7 tập S2 và cứ tiếp tục. Độ chính xác là toàn bộ số phân lớp đúng từ k lần lặp chia cho tổng số mẫu của tập dữ liệu ban đầu. 1.3. Phƣơng pháp cây quyết định 1.3.1. Định nghĩa Những năm qua, nhiều mô hình phân lớp dữ liệu đã đƣợc các nhà khoa học trong nhiều lĩnh vực khác nhau đề xuất nhƣ mạng nơ ron, mô hình thống kê tuyến tính trên bậc 2, cây quyết định, mô hình di truyền. Trong số những mô hình đó, cây quyết định với những ƣu điểm của mình đƣợc đánh giá là một công cụ mạnh, phổ biến và đặc biệt thích hợp cho data mining nói chung và phân lớp dữ liệu nói riêng [3]. Những ƣu điểm của cây quyết định nhƣ: - Xây dựng tƣơng đối nhanh, đơn giản, dễ hiểu. - Các cây có thể dễ dàng đƣợc chuyển đổi sang các câu lệnh SQL để có thể đƣợc sử dụng để truy nhập dữ liệu một cách hiệu quả. Việc phân lớp dựa trên cây quyết định đạt đƣợc sự tƣơng tự và đôi khi là chính xác hơn so với các phƣơng pháp phân lớp khác [6]. Cây quyết định là biểu đồ phát triển có cấu trúc dạng cây nhƣ trong hình sau: Tuổi Tuổi>18 Tuổi< 18 CNV KNĐ = No CNV = C CNV = K KNĐ = No KNĐ = Yes Hình 1.5: Ví dụ về cây quyết định Trong cây quyết định: - Gốc: là node trên cùng của cây - Node trong: biểu diễn một kiểm tra trên một thuộc tính đơn (hình chữ nhật). 8
- Xem thêm -