Tài liệu Phân lớp ý kiến khách hàng và ứng dụng trong hệ tư vấn bán hàng trực tuyến

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC MỞ HÀ NỘI LUẬN VĂN THẠC SĨ Chuyên ngành: Công nghệ thông tin Mã ngành: 84.8.02.01 Đề tài: PHÂN LỚP Ý KIẾN KHÁCH HÀNG VÀ ỨNG DỤNG TRONG HỆ TƢ VẤN BÁN HÀNG TRỰC TUYẾN HỌC VIÊN THỰC HIỆN: TẠ VĂN KHOA HƢỚNG DẪN KHOA HỌC: PGS. TS ĐOÀN VĂN BAN HÀ NỘI, 2022 LỜI CẢM ƠN Lời cảm ơn trân trọng đầu tiên, tôi muốn dành tới các thầy, cô giáo Trƣờng Đại học Mở Hà Nội cùng các thầy, cô giáo Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tận tình giảng dạy và truyền đạt kiến thức trong suốt khóa học cao học vừa qua. Đặc biệt tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất của mình tới thầy PGS.TS. Đoàn Văn Ban, đã tận tình dìu dắt và hƣớng dẫn tôi trong suốt quá trình làm luận văn, sự chỉ bảo và định hƣớng của thầy giúp tôi tự tin nghiên cứu những vấn đề mới và giải quyết bài toán một cách khoa học. Tôi xin chân thành cảm ơn các thầy, cô giáo viên Công nghệ Thông Tin trƣờng Trƣờng Đại học Mở Hà Nội đã tạo điều kiện thuận lợi cho tôi trong quá trình học tập, nghiên cứu. Cuối cùng, tôi xin cảm ơn tập thể lớp Công nghệ thông tin khóa 18, các bạn đã cổ vũ, khích lệ và chia sẻ kinh nghiệm bản thân giúp luận văn của tôi ngày một hoàn thiện. Mặc dù đã cố gắng rất nhiều nhƣng chắc chắn trong quá trình học tập cũng nhƣ luận văn không khỏi những thiếu sót. Tôi rất mong nhận đƣợc sự thông cảm và chỉ bảo tận tình của các thầy cô và các bạn. Tôi xin chân thành cảm ơn! Hà Nội, ngày 21 tháng 04 năm 2021 Tạ Văn Khoa i LỜI CAM ĐOAN Tên tôi là: Tạ Văn Khoa Sinh ngày: 11/01/1988 Là học viên lớp cao học : 18M-CT52 Trƣờng Đại học Mở Hà Nội Nơi công tác: Trƣờng Cao đẳng Cơ Khí Nông Nghiệp – Vĩnh Phúc Tôi xin cam đoạn : 1. Tôi xin cam đoan “Phân lớp ý kiến khách hàng và ứng dụng trong hệ tƣ vấn bán hàng trực tuyến” là công trình nghiên cứu khoa học của tôi dƣới sự hƣớng dẫn khoa học trực tiếp của PGS.TS. Đoàn Văn Ban. Các nội dung nghiên cứu, kết quả nghiên cứu đƣợc trình bày trong luận văn hoàn toàn là trung thực, không vi phạm bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật của Việt Nam . 2. Mọi tham khảo dùng trong khóa luận đều đƣợc trích dẫn rõ ràng tên tác giả, tên công trình, thời gian, địa điểm công bố . 3. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu hoàn toàn trách nhiệm . Hà Nội , ngày 21 tháng 04 năm 2021 Học viên thực hiện Tạ Văn Khoa ii MỤC LỤC LỜI CẢM ƠN .................................................................................................... i LỜI CAM ĐOAN ............................................................................................. ii MỤC LỤC ........................................................................................................ iii DANH MỤC BẢNG ....................................................................................... vii DANH MỤC HÌNH ....................................................................................... viii MỞ ĐẦU ........................................................................................................... 1 1. Tính cấp thiết của đề tài ............................................................................ 1 3. Đối tƣợng và phạm vi nghiên cứu ............................................................. 2 4. Phƣơng pháp nghiên cứu........................................................................... 2 5. Cấu trúc luận văn ...................................................................................... 3 CHƢƠNG 1: PHÂN LỚP DỮ LIỆU ................................................................ 4 1. 1. Giới thiệu phân lớp dữ liệu ................................................................... 4 1.2. Quy trình phân lớp dữ liệu ..................................................................... 6 1.3. Các vấn đề liên quan đến phân lớp dữ liệu ............................................ 9 CHƢƠNG 2: MỘT SỐ KỸ THUẬT TRONG PHÂN LOẠI VĂN BẢN ..... 16 2.1. Xử lý văn bản tiếng Việt ...................................................................... 16 2.1.1. So sánh giữa tiếng Anh và tiếng Việt ........................................... 16 2.1.2. Một số phƣơng pháp tách từ ......................................................... 17 2.2. Biểu diễn văn bản ................................................................................. 26 2.2.1. Mô hình boolean ........................................................................... 26 2.2.2. Mô hình không gian vector ........................................................... 27 2.2.3. Mô hình logic ............................................................................... 32 2.2.4. Mô hình phân tích cú pháp ........................................................... 33 2.2.5. Mô hình tần suất ........................................................................... 34 2.2.6. Các mô hình biểu diễn văn bản khác ............................................ 36 2.3. Độ tƣơng đồng...................................................................................... 37 2.3.1. Khái niệm ...................................................................................... 38 2.3.2. Độ tƣơng đồng văn bản trong Tiếng Việt ..................................... 38 2.3.3. Độ tƣơng đồng văn bản dựa trên tập từ chung.............................. 39 iii 2.3.4. Độ tƣơng đồng văn bản dựa trên vector biểu diễn ........................ 40 2.3.5. Tính độ tƣơng đồng cho toàn bộ văn bản ..................................... 41 2.4. Các phƣơng pháp phân loại văn bản .................................................... 42 2.4.1. Phƣơng pháp Naïve Bayes (NB) ................................................... 42 2.4.2. Phƣơng pháp K-Nearest Neighbor (K - NN) ................................ 43 2.4.3. Phƣơng pháp Linear Least Square Fit (LLSF).............................. 45 2.4.4. Phƣơng pháp Support Vector Machine (SVM) ............................ 46 2.4.5. Phƣơng pháp Centroid- based vector ............................................ 53 2.4.6. Đánh giá nhận xét.......................................................................... 53 2.5. Kết luận chƣơng 2 ................................................................................ 54 CHƢƠNG 3: PHÂN LỚP Ý KIẾN ĐÁNH GIÁ CỦA KHÁCH HÀNG TRÊN HỆ THỐNG BÁN HÀNG TRỰC TUYẾN .................................................... 56 3.1. Website bán hàng trực tuyến ................................................................ 56 3.2. Xây dựng mô hình ứng dụng khai phá ý kiến phản hồi của khách hàng trên website dựa trên SVM để hỗ trợ bán hàng trực tuyến ......................... 62 3.2.1. Phát biểu bài toán ......................................................................... 62 3.2.2. Mô hình ứng dụng khai phá ý kiến phản hồi của khách hàng trên website dựa trên SVM...................................................................... 62 3.3. Yêu cầu phần cứng phần mềm ............................................................. 65 3.3.1. Cấu hình máy thực nghiệm ........................................................... 65 3.3.2. Công cụ và phần mềm sử dụng ..................................................... 65 3.4. Một số kết quả và đánh giá .................................................................. 66 3.4.1. Kết quả thử nghiệm ...................................................................... 66 3.4.2. Huấn luyện và phân lớp dữ liệu .................................................... 77 3.4.3. Đánh giá kết quả ............................................................................ 79 3.5. Kết luận chƣơng 3 ................................................................................ 79 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ...................................................... 80 TÀI LIỆU THAM KHẢO ............................................................................... 81 iv DANH MỤC CÁC KÝ TỰ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt 1 SVM Support Vector Machine Máy vector hỗ trợ 2 Zalo OA Zalo Official Account Tài khoản Zalo chính STT thức 3 TP Số lƣợng dự đoán chính True Positive xác 4 TN Số lƣợng dự đoán chính True Negative xác một cách gián tiếp 5 FP Số lƣợng các dự đoán False Positive sai lệch 6 FN Số lƣợng các dự đoán False Negative sai lệch một cách gián tiếp 7 TBL Transformation-based Learning Phƣơng pháp học dựa trên sự cải biến 8 9 10 WFST IGATEC TFxIDF Weighted- Finite State Chuyển đổi trạng thái Transducer trọng số hữu hạn Internet and Genetics Phƣơng pháp tách từ Algorithm based Text dựa trên thống kê từ trên Categorization for Documents Internet và giải thuật di in Vietnamese truyền Term Frequency times Inverse Phƣơng pháp tần suất từ Document Frequency khóa kết hợp phƣơng pháp nghịch đảo tần số văn bản v 11 NB Phƣơng pháp tiếp cận Naïve Bayes xác suất thống kê 12 K – NN K-Nearest Neighbor Thuật toán K láng giềng gần 13 LLSF Linear Least Square Fit Thuật toán tuyến tính bình phƣơng nhỏ nhất 14 NNet Neural Network Mạng Neural 15 CRF Conditional Random Field Thuật toán xác suất có điều kiện vi DANH MỤC BẢNG Bảng 2.1 So sánh những đặc điểm chính của Tiếng Việt và Tiếng Anh ................. 15 Bảng 2.2 Tách chuỗi từ “Tôi là công dân nƣớc Việt Nam” ..................................... 17 Bảng 2.3 Biểu diễn văn bản trong mô hình Logic ................................................... 31 Bảng 3.1 Kết quả huấn luyện và kiểm thử ............................................................... 76 vii DANH MỤC HÌNH Trang Hình 1.1 Mô hình mô tả bài toán phân lớp dữ liệu .................................................. 6 Hình 1.2 Quá trình phân lớp dữ liệu - (a) Bƣớc xây dựng mô hình phân lớp ......... 7 Hình 1.3 Quá trình phân lớp dữ liệu - (b1) Ƣớc lƣợng độ chính xác của mô hình.. 8 Hình 1.4 Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới ........................... 9 Hình 1.5 Các chỉ số đánh giá mô hình phân lớp ...................................................... 13 Hình 2.1 Sơ đồ các bƣớc sử lý của WFST ............................................................... 20 Hình 2.2 Giải thuật di truyền IGATEC .................................................................... 21 Hình 2.3 Mô hình thuật toán K-NN ......................................................................... 42 Hình 2.4 Các điểm đƣợc khoanh tròn là các vector hỗ trợ ...................................... 45 Hình 2.5. Tập dữ liệu đƣợc phân chia tuyến tính ..................................................... 47 Hình 2.6. Tập dữ liệu phân chia tuyến tính nhƣng có nhiễu .................................... 48 Hình 2.7. Tập dữ liệu không phân chia tuyến tính ................................................... 49 Hình 3.1 Giao diện trang chủ ................................................................................... 54 Hình 3.2 Giao diện trang sản phẩm .......................................................................... 55 Hình 3.3 Giao diện trang đăng ký bảo dƣỡng .......................................................... 55 Hình 3.4 Giao diện trang tin tức – tƣ vấn ................................................................ 56 Hình 3.5 Giao diện trang liên hệ .............................................................................. 56 Hình 3.6 Nút đánh giá ngay ..................................................................................... 57 Hình 3.7 Form điền thông tin ý kiến ........................................................................ 57 Hình 3.8 Thống kê báo cáo ý kiến khách ................................................................. 58 Hình 3.9 xem ý kiến khách hàng .............................................................................. 58 viii Hình 3.10 Các bƣớc trong quá trình phân lớp văn bản ............................................ 59 Hình 3.11 Giao diện phần mềm Weka ..................................................................... 63 Hình 3.12 Chuyển đổi dữ liệu sang .arff .................................................................. 67 Hình 3.13 Vector hóa dữ liệu ................................................................................... 68 Hình 3.14 Giao diện huấn luyện .............................................................................. 75 Hình 3.15 Kết quả huấn luyện.................................................................................. 75 ix i MỞ ĐẦU 1. Tính cấp thiết của đề tài Hiện nay, chúng ta đang bƣớc vào cuộc cách mạng 4.0, cuộc cách mạng tập trung chủ yếu vào sản xuất thông minh dựa trên các thành tựu đột phá trong công nghệ thông tin, trí tuệ nhân tạo, công nghệ sinh học, công nghệ nano,… Dựa vào công nghệ hiện nay, cá nhân, doanh nghiệp bán hàng trực tuyến rất muốn biết phản hồi của khách hàng về sản phẩm, dịch vụ của họ nhƣ thế nào, cũng nhƣ họ muốn phân lớp khách hàng để có thể tung ra những chiến dịch marketing, sản phẩm phù hợp với từng loại đối tƣợng khách hàng. Việc nhiều ý kiến đánh giá của khách về sản phẩm từ nhiều nguồn khác nhau (Website bán hàng, OA Zalo, Blog, Facebook, Youtube, …). Để có thể tổng hợp ý kiến đánh giá, phản hồi của khách hàng về chất lƣợng, thì phải tự động hóa đƣợc công việc thu thập và phân tích đánh giá ý kiến của khách hàng. Công nghệ phân lớp dữ liệu phục vụ cho việc phân lớp quan điểm khách hàng đang rất phát triển, đây là một bài toán lớn trong việc hỗ trợ bán hàng trực tuyến, và mọi doanh nghiệp muốn phát triển mảng bán hàng online thì việc phân lớp khách hàng rất quan trọng. Trong vài năm gần đây, phân lớp dữ liệu đã thu hút sự quan tâm 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 nhƣ ứng dụng trong nhiều lĩnh vực thực tế nhƣ: tƣ vấn bán hàng trực tuyến, thƣơng mại, nhà băng, maketing, …. Phân lớp khách hàng chính là việc phân lớp văn bản là bài toán cơ bản trong khai phá quan điểm. Các hệ thống phân lớp văn bản là các hệ thống phải có khả năng xác định, khai phá ra nội dung thông tin. Do đó tôi chọn đề tài “Phân lớp ý kiến khách hàng và ứng dụng trong hệ tƣ vấn bán hàng trực tuyến” đề tài nghiên cứu một số kỹ thuật phân lớp văn bản nhƣ Naïve Bayes (NB), Support Vector Machine (SVM) , K-Nearest Neighbor (KNN) , Linear Least Square Fit (LLSF) , Centroid – based vector để sử dụng trong 1 phƣơng pháp học máy phân lớp quan điểm khách hàng và ứng dụng thực tế vào bán hàng trực tuyến. 2. Mục tiêu nghiên cứu + Nghiên cứu tổng quan về một số kỹ thuật phân lớp văn bản nhƣ: Naïve Bayes (NB), Support Vector Machine (SVM) , K-Nearest Neighbor (K-NN) , Linear Least Square Fit (LLSF) , Centroid – based vector. + Nghiên cứu một số kỹ thuật sử dụng để phân lớp ý kiến khách hàng trên sản phẩm bán hàng trực tuyến. + Đề xuất cải tiến hoàn thiện module thu thập dữ liệu và module xử lý dữ liệu ngôn ngữ kết hợp với thuật toán SVM phân tích phân lớp ý kiến khách hàng và ứng dụng trong hệ tƣ vấn bán hàng trực tuyến 3. Đối tƣợng và phạm vi nghiên cứu + Đối tƣợng: ý kiến khách hàng và ứng dụng trong hệ tƣ vấn bán hàng trực tuyến. + Phạm vi:  Hệ thống xử lý văn bản đƣợc ứng dụng trong hệ tƣ vấn bán hàng trực tuyến trên dòng xe ô tô VinFast Fadil bản tiêu chuẩn.  Nghiên cứu đƣợc tiến hành từ tháng 12/2020 đến 12/2021. 4. Phƣơng pháp nghiên cứu - Phƣơng pháp nghiên cứu tài liệu, phân tích, tổng hợp là phƣơng pháp thu thập thông tin thông qua nghiên cứu tài liệu nhằm mục đích tìm chọn những khái niệm và tƣ tƣởng cơ bản là cơ sở cho lý luận của đề tài, hình thành giả thuyết khoa học, dự đoán về những thuộc tính của đối tƣợng nghiên cứu, xây dựng những mô hình lý thuyết hay thực nghiệm ban đầu. Trong luận văn phƣơng pháp nghiên cứu lý thuyết đƣợc sử dụng để tìm hiểu một số kỹ thuật phân lớp văn bản nhƣ Naïve Bayes (NB), Support Vector Machine (SVM) , K-Nearest Neighbor (K-NN) , Linear Least Square Fit (LLSF) , Centroid – based vector. 2 - Phƣơng pháp thực nghiệm và đối chứng qua chƣơng trình thử nghiệm là một trong những bƣớc quan trọng bậc nhất. Trong đó, nghiên cứu sẽ chủ động tác động vào đối tƣợng cần đƣợc nghiên cứu và quá trình diễn biến bao gồm các sự kiện hoặc hiện tƣợng mà đối tƣợng tham gia. Trong luận văn pháp thực nghiệm và đối chứng qua chƣơng trình thử nghiệm đã sử dụng thu thập dữ liệu về ý kiến khách hàng trên dòng xe VinFast Fadil bản tiêu chuẩn tại web http://vinfastvinhphuc.net/san-pham/vinfast-fadil-tieuchuan/ - Phƣơng pháp trao đổi khoa học, lấy ý kiến chuyên gia là phƣơng pháp điều tra qua đánh giá của các chuyên gia về vấn đề, một sự kiện khoa học nào đó. Trong quá trình thực hiện luận văn, bản thân học viên đã tham vấn các thầy, các chuyên gia trong việc phân lớp ý kiến khách hàng khi mua sản phẩm trực tuyến . 5. Cấu trúc luận văn Ngoài phần mở đầu, kết luận, luận văn đƣợc chia thành 3 chƣơng nhƣ sau: Chƣơng 1: Phân tích lớp dữ liệu Chƣơng 2: Một số kỹ thuật trong phân loại văn bản Chƣơng 3: Phân lớp ý kiến đánh giá của khách hàng trên hệ thống bán hàng trực tuyến 3 CHƢƠNG 1: PHÂN LỚP DỮ LIỆU 1. 1. Giới thiệu phân lớp dữ liệu Ngày nay phân lớp dữ liệu (classification) là một trong những hƣớng nghiên cứu chính của khai phá dữ liệu. Thực tế đặt ra nhu cầu là từ một cơ sở dữ liệu với nhiều thông tin ẩn con ngƣời có thể trích rút ra các quyết định nghiệp vụ thông minh. Phân lớp và dự đoán là hai dạng của phân tích dữ liệu nhằm trích rút ra một mô hình mô tả các lớp dữ liệu quan trọng hay dự đoán xu hƣớng dữ liệu tƣơng lai. Phân lớp dự đoán giá trị của những nhãn xác định (categorical label) hay những giá trị rời rạc (discrete value), có nghĩa là phân lớp thao tác với những đối tƣợng dữ liệu mà có bộ giá trị là biết trƣớc [5]. Trong khi đó, dự đoán lại xây dựng mô hình với các hàm nhận giá trị liên tục. Ví dụ mô hình phân lớp dự báo thời tiết có thể cho biết thời tiết ngày mai là mƣa, hay nắng dựa vào những thông số về độ ẩm, sức gió, nhiệt độ, …, của ngày hôm nay và các ngày trƣớc đó. Hay nhờ các luật về xu hƣớng, ý kiến mua hàng của khách hàng trên website thƣơng mại điện tử, các nhân viên kinh doanh có thể ra những quyết sách đúng đắn về lƣợng mặt hàng cũng nhƣ chủng loại bày bán, … Phần lớn các thuật toán ra đời trƣớc đề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ố thuật toán 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 thuật toán với những tập dữ liệu lớn lên tới hàng tỉ bản ghi. Bài toán phân lớp quan điểm: Là quá trình phân lớp một đối tƣợng dữ liệu vào một hay nhiều lớp cho trƣớc nhờ một mô hình phân lớp mà mô hình này đƣợc xây dựng dựa trên một tập hợp các đối tƣợng dữ liệu đã đƣợc gán nhãn từ trƣớc gọi là tập dữ liệu học (tập huấn luyện). Quá trình phân lớp còn đƣợc gọi là quá trình gán nhãn cho các đối tƣợng dữ liệu [1], [3]. Nhiệm vụ của bài toán phân lớp dữ liệu là cần xây dựng mô hình phân lớp để khi có một dữ liệu mới vào thì mô hình phân lớp sẽ cho biết dữ liệu đó thuộc lớp nào. 4 Có nhiều bài toán phân lớp dữ liệu, nhƣ phân lớp nhị phân, phân lớp đa lớp, phân lớp đa trị, …. [5]. Phân lớp nhị phân là quá trình tiến hành việc phân lớp dữ liệu vào một trong hai lớp khác nhau dựa vào việc dữ liệu đó có hay không một số đặc tính theo quy định của bộ phân lớp [5], [7]. Phân lớp đa lớp là quá trình phân lớp với số lƣợng lớp lớn hơn hai. Nhƣ vậy, tập hợp dữ liệu trong miền xem xét đƣợc phân chia thành nhiều lớp chứ không đơn thuần chỉ là hai lớp nhƣ trong bài toán phân lớp nhị phân. Về bản chất, bài toán phân lớp nhị phân là trƣờng hợp riêng của bài toán phân lớp đa lớp. Trong phân lớp đa trị, mỗi đối tƣợng dữ liệu trong tập huấn luyện cũng nhƣ các đối tƣợng mới sau khi đƣợc phân lớp có thể thuộc vào từ hai lớp trở lên. Ví dụ nhƣ trang web về việc bùng phát bệnh cúm gia cầm, thủy cầm tại một số tính phía Bắc vừa thuộc về lĩnh vực y tế liên quan đến lây bệnh sang ngƣời nhƣng cũng thuộc về lĩnh vực kinh tế liên quan đến ngành chăn nuôi, …  Phân lớp dữ liệu: Phân lớp dữ liệu (classification) là một trong những hƣớng nghiên cứu chính của khai phá dữ liệu. Thực tế đặt ra nhu cầu là từ một cơ sơ dữ liệu với nhiều thông tin ẩn con ngƣời có thể rút trích ra các quyết định nghiệp vụ thông minh. Phân lớp là một dạng của phân tích dữ liệu nhằm rút trích ra một mô hình mô tả các lớp dữ liệu quan trọng hay dự đoán xu hƣớng dữ liệu trong tƣơng lai. Phân lớp dự đoán giá trị của những nhãn xác định hay những giá trị rời rạc, có nghĩa là phân lớp thao tác với những đối tƣợng dữ liệu mà có bộ giá trị là biết trƣớc. Tóm lại, phân lớp là quá trình nhóm các đối tƣợng giống nhau vào một lớp dựa trên các đặc trƣng dữ liệu của chúng. Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm 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 ứng dụng trong nhiều lĩnh vƣc khác nhau nhƣ: thƣơng mại, ngân hàng, maketing, nghiên cứu thị trƣờng, bảo hiểm, y tế, giáo dục… 5  Bài toán phân lớp dữ liệu: Là quá trình phân lớp một đối tƣợng dữ liệu vào một hay nhiều lớp đã cho trƣớc nhờ một mô hình phân lớp (model). Mô hình này đƣợc xây dựng dựa trên một tập dữ liệu đƣợc xây dựng trƣớc đó có gán nhãn (còn gọi là tập huấn luyện). Quá trình phân lớp là quá trình gán nhãn cho đối tƣợng dữ liệu. Nhiệm vụ của bài toán phân lớp là cần tìm một mô hình phân lớp để khi có dữ liệu mới thì có thể xác định đƣợc dữ liệu đó thuộc vào phân lớp nào. Bài toán phân lớp dữ liệu có thể đƣợc mô tả nhƣ hình 1.1 dƣới đây [5]. Hình 1.1 Mô hình mô tả bài toán phân lớp dữ liệu Bài toán phân lớp dữ liệu có thể phát biểu tổng quát nhƣ sau: Cho U = {A1, A2,…., Am} là tập có m thuộc tính, Y = {y1, y2, ….., yn} là tập các nhãn của lớp: với D = A1 … Am là tích Đề - các của các miền của m thuộc tính tƣơng ứng có n số lớp và N là số mẫu dữ iệu. Mỗi dữ liệu di D thuộc một lớp yi Y tƣơng ứng tạo thành từng cặp (di, yi) . 1.2. Quy trình phân lớp dữ liệu Giới thiệu mô hình và phân tích quy trình phân lớp dữ liệu, quá trình phân lớp dữ liệu thƣờng gồm hai bƣớc: xây dựng mô hình (tạo bộ phân lớp) và sử dụng mô hình đó để phân lớp dữ liệu, và đƣa ra chi tiết của hai bƣớc trên. 6 Quy trình thực hiện phân lớp dữ liệu thƣờng đƣợc thực hiện theo 2 bƣớc: Bƣớc thứ nhất (learning) quá trình học để xây dựng mô hình phân lớp và bƣớc thứ hai áp dụng mô hình phân lớp ở bƣớc thứ nhất để phân lớp dữ liệu mới.  Bước thứ nhất (learning) 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), ví dụ (example), đối tƣợng (object), bản ghi (record) hay trƣờng hợp (case). Trong tập dữ liệu này, mỗi phần tử dữ liệu đƣợc giả sử thuộc về một lớp định trƣớc, 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 thƣờng là các quy tắc phân lớp dƣới dạng luật dạng 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ƣ hình 1.2 [5], [8]. Hình 1.2 Quá trình phân lớp dữ liệu -(a) xây dựng mô hình phân lớp  Bước thứ hai (classification) 7 Bƣớc thứ hai dùng mô hình đã xây dựng ở bƣớc thứ nhất để 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 đào tạo. Độ 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 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 đào tạo 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 đào 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 mà giá trị của thuộc tính phân lớp là chƣa biết. Hình 1.3 Quá trình phân lớp dữ liệu - (b1) Ước lượng độ chính xác của mô hình 8 Hình 1.4 Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới 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. 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 thuật toán 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ủa thuật toán đƣợc đặc biệt chú trọng và phát triển. 1.3. Các vấn đề liên quan đến phân lớp dữ liệu Vấn đề về chuẩn bị dữ liệu bao gồm: Làm sạch dữ liệu, phân tích sự cần thiết của dữ liệu, chuyển đổi dữ liệu [5]. Làm sạch dữ liệu Làm sạch dữ liệu liên quan đến việc xử lý với lỗi (noise) và giá trị thiếu (missing value) trong tập dữ liệu ban đầu. Noise 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 loại lỗi này có thể dùng kỹ 9