Luận văn Học nửa giám sát dựa trên đồ thị và ứng dụng

tôi xin bày tỏ lòng biết ơn sâu sắc đến thầy giáo PGS.TS Đoàn Văn Ban, ngƣời đã tận tình hƣớng dẫn, chỉ bảo cho tôi trong suốt quá trình thực hiện luận văn. Xin cùng bày tỏ lòng biết ơn chân thành tới các thầy, cô giáo trong Viện Công nghệ Thông tin cũng nhƣ các thầy, cô giáo trong Trƣờng Đại học Công nghệ Thông tin & Truyền thông Thái Nguyên, đã đem lại cho tôi những kiến thức vô cùng có ích trong những năm học tập tại trƣờng. ngƣời đã luôn bên cạnh, động viên và khuyến khích tôi trong quá trình thực hiện đề tài nghiên cứu của mình. Tôi xin chân thành cảm ơn! , ngày 10 tháng 4 năm 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN LỜI CẢM ƠN ............................................................................................................. i DANH MỤC HÌNH VẼ ..............................................................................................v LỜI MỞ ĐẦU .............................................................................................................1 1. ............................................................................................................ 1 ...................................................................................................... 2 .................................................................................. 2 ............................................................................................... 2 ............................................................................................... 3 6. .......................................................................................................... 3 CHƢƠNG 1: TỔNG QUAN VỀ CÁC PHƢƠNG PHÁP HỌC MÁY ......................4 1.1. Giới thiệu về học máy ................................................................................................. 4 1.2. Các phƣơng pháp học máy .......................................................................................... 7 1.2.1. Học có giám sát .................................................................................................... 7 1.2.2. Học không giám sát .............................................................................................. 8 1.2.3. Học tăng cƣờng .................................................................................................. 11 1.2.4. Học nửa giám sát ................................................................................................ 12 1.3. Một số phƣơng pháp học nửa giám sát ..................................................................... 14 1.3.1. Phƣơng pháp tự huấn luyện ................................................................................ 14 1.3.2. Phƣơng pháp đồng huấn luyện ........................................................................... 15 1.3.3. Phƣơng pháp Máy véc tơ hỗ trợ truyền dẫn ....................................................... 18 1.3.4. Phƣơng pháp dựa trên đồ thị .............................................................................. 22 1.4. Kết luận ..................................................................................................................... 24 CHƢƠNG 2: PHƢƠNG PHÁP HỌC NỬA GIÁM SÁT DỰA TRÊN ĐỒ THỊ .....25 2.1. Giới thiệu .................................................................................................................. 25 2.2. Các loại đồ thị phổ biến có thể sử dụng trong học nửa giám sát .............................. 27 2.2.1. Đồ thị kết nối đầy đủ .......................................................................................... 27 2.2.2. Đồ thị rời rạc ...................................................................................................... 27 2.2.3. Đồ thị -láng giềng gần nhất ............................................................................ 28 2.2.4. Đồ thị -láng giềng gần nhất ............................................................................. 28 2.2.5. Đồ thị trọng số exp ............................................................................................ 29 Số hóa bởi Trung tâm Học liệu – ĐHTN 2.3. Các phƣơng pháp xác định khoảng cách giữa các điểm dữ liệu ............................... 29 2.3.1. Khoảng cách cục bộ, khoảng cách toàn cục và trọng số .................................... 29 2.3.2. Khoảng cách Hamming ...................................................................................... 30 2.3.3. Khoảng cách Manhattan cho các thuộc tính số học ........................................... 30 2.3.4. Các hàm khoảng cách cục bộ không đồng nhất ................................................. 31 2.3.5. Hàm khoảng cách tri thức chuyên gia ................................................................ 31 2.4. Thuật toán lan truyền nhãn trong đồ thị .................................................................... 32 2.4.1. Ký hiệu ............................................................................................................... 32 2.4.2. Nội dung thuật toán ............................................................................................ 33 2.4.3. Sự hội tụ của thuật toán ...................................................................................... 34 2.4.4. Phƣơng pháp xác định siêu tham số của đồ thị .................................................. 36 2.4.5. Độ phức tạp của thuật toán ................................................................................. 38 2.5. Thuật toán học nửa giám sát dựa trên đồ thị - Mincut .............................................. 38 2.6. Các trƣờng Gaussian ngẫu nhiên và các hàm điều hòa ............................................. 40 2.6.1. Các trƣờng Gaussian ngẫu nhiên........................................................................ 40 2.6.2. Đồ thị Laplacian ................................................................................................. 42 2.6.3. Các hàm điều hòa ............................................................................................... 43 2.7. Đánh giá .................................................................................................................... 44 2.8. Kết luận chƣơng ........................................................................................................ 44 CHƢƠNG 3: CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN ................................45 3.1. Mô tả bài toán ........................................................................................................... 45 3.2. Mô tả dữ liệu đầu vào ............................................................................................... 45 3.3. Trích chọn đặc trƣng ................................................................................................. 47 3.4. Cài đặt và thử nghiệm ............................................................................................... 50 Môi trƣờng cài đặt và thử nghiệm ................................................................................ 50 Các chức năng của chƣơng trình .................................................................................. 51 3.5. Kết quả thực nghiệm và đánh giá độ phức tạp .......................................................... 54 3.6. Kết luận ..................................................................................................................... 56 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ................................................................57 TÀI LIỆU THAM KHẢO .........................................................................................58 Số hóa bởi Trung tâm Học liệu – ĐHTN DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT Thuật ngữ Viết tắt Ý nghĩa Concept Concept Khái niệm Self-training Self-training Tự huấn luyện Co-training Co-training Đồng huấn luyện Machine learning Machine learning Học máy Supervised learning Supervised learning Học có giám sát Unsupervised learning Unsupervised learning Học không giám sát Reinforcement learning Reinforcement learning Học tăng cƣờng Semi-supervised Semi-supervised learning Học nửa giám sát learning Support vector machine SVM Máy véc tơ hỗ trợ Transductive support Máy véc tơ hỗ trợ truyền TSVM vector machine dẫn Labeled Propagation Labeled Propagation Lan truyền nhãn Graph-based Graph-based Dựa trên đồ thị Số hóa bởi Trung tâm Học liệu – ĐHTN DANH MỤC HÌNH VẼ Hình 1.1: Phƣơng pháp phân cụm dữ liệu. ................................................................. 9 Hình 1.2: Khung nhìn dữ liệu giữa văn bản và liên kết ............................................ 17 Hình 1.3: Dữ liệu đƣợc học theo phƣơng pháp Co-training. .................................... 18 Hình 1.4: Phƣơng pháp Máy véc tơ hỗ trợ ................................................................ 19 Hình 1.5: Phƣơng pháp máy vecto hỗ trợ truyền dẫn ............................................... 22 Hình 1.6: Minh họa đồ thị đƣợc gán nhãn ................................................................ 23 Hình 2.1: Phƣơng pháp dựa trên đồ thị ..................................................................... 25 Hình 2.2: Đồ thị kết nối đầy đủ ................................................................................. 27 Hình 2.3: Đồ thị rời rạc ............................................................................................. 27 Hình 2.4: Đồ thị -láng giềng gần nhất ................................................................... 28 Hình 2.5: Đồ thị -láng giềng gần nhất ..................................................................... 28 Hình 2.6: Trọng số cạnh giữa hai đỉnh của đồ thị ..................................................... 29 Hình 2.7: Đồ thị với các trọng số cạnh ..................................................................... 32 Hình 3.1: Tệp dữ liệu tin nhắn mẫu .......................................................................... 45 Hình 3.2: Nội dung tin nhắn đƣợc chuyển thành dạng vector ................................. 46 Hình 3.3: Nội dung file dữ liệu dạng vector ............................................................ 47 Hình 3.4: Trích chọn đặc trƣng ............................................................................... 48 Hình 3.5: Trích chọn thuộc tính cho file đầu vào của chƣơng trình ........................ 49 Hình 3.6: Dữ liệu của chƣơng trình ......................................................................... 49 Hình 3.7: Dữ liệu của chƣơng trình mở bằng Notepad ............................................ 50 Hình 3.8: Giao diện chọn tệp dữ liệu ....................................................................... 51 Hình 3.9: Kết quả khi lựa chọn phƣơng pháp tự huấn luyện ................................... 52 Hình 3.10: Giao diện đồ thị lan truyền nhãn trƣớc khi thực hiện ............................ 53 Hình 3.11: Giao diện đồ thị lan truyền nhãn sau khi thực hiện ............................... 54 Hình 3.12: Kết quả đồ thị sau khi đƣợc gán nhãn ở dạng đồ thị.............................. 54 Số hóa bởi Trung tâm Học liệu – ĐHTN 1 LỜI MỞ ĐẦU 1. Học máy (Machine learning) là một ngành khoa học nghiên cứu các kĩ thuật, các phƣơng pháp cho phép các máy tính có khả năng "học" giống nhƣ con ngƣời. Hay nói một cách khác cụ thể hơn, học máy là một phƣơng pháp để tạo ra các chƣơng trình máy tính bằng việc phân tích các tập dữ liệu, qua đó máy tính có khả năng tích lũy đƣợc tri thức thông qua việc học đƣợc các khái niệm để có thể ra quyết định trong các trƣờng hợp tƣơng tự. Lĩnh vực học máy truyền thống thƣờng đƣợc chia thành bốn lĩnh vực con, bao gồm: Học có giám sát (Supervised learning), Học không giám sát (Unsupervised learning), Học nửa giám sát (Semi-Supervised learning) và Học tăng cƣờng (Reinforcement learning). Học nửa giám sát sử dụng cả dữ liệu đã gán nhãn và chƣa gán nhãn để huấn luyện - điển hình là một lƣợng nhỏ dữ liệu có gán nhãn cùng với lƣợng lớn dữ liệu chƣa gán nhãn. Học nửa giám sát đứng giữa học không giám sát (không có bất kì dữ liệu có nhãn nào) và có giám sát (toàn bộ dữ liệu đều đƣợc gán nhãn). Để gán nhãn dữ liệu cho một bài toán học máy thƣờng đòi hỏi một phân loại bằng tay các ví dụ huấn luyện. Chi phí cho quy trình này khiến tập dữ liệu đƣợc gán nhãn hoàn toàn trở nên không khả thi, trong khi dữ liệu không . Trong tình huống đó, học nửa giám sát có giá trị thực tiễn lớn lao. Chính vì vậy, học nửa giám sát là sự kết hợp một số lƣợng lớn các dữ liệu chƣa đƣợc gán nhãn cùng với các dữ liệu đã đƣợc gán nhãn để xây dựng các bộ phân lớp tốt hơn. Một số phƣơng pháp điển hình trong lĩnh vực này đƣợc kể đến nhƣ: Phƣơng pháp EM với mô hình sinh hỗn hợp (EM with generative mixture models), phƣơng pháp Tự huấn luyện (Self-training), phƣơng pháp Đồng huấn luyện (Co-training), phƣơng pháp máy véc tơ hỗ trợ (Transductive support vector machines) và phƣơng pháp Dựa trên đồ thị (Graph-based). Trong đó phƣơng pháp học nửa giám sát dựa trên đồ thị (Graph-based) đang là hƣớng nghiên cứu mở và đem lại hiệu quả lớn. Với những lý do trên, tác giả đã chọn đề tài “ Số hóa bởi Trung tâm Học liệu – ĐHTN ” làm đề tài nghiên cứu luận văn tốt nghiệp thạc sĩ chuyên ngành Khoa học máy tính. Nghiên cứu tổng quan về học nửa giám sát và một số phƣơng pháp học nửa giám sát. Nghiên cứu phƣơng pháp học nửa giám sát dựa trên đồ thị Cài đặt thử nghiệm thuật toán lan truyền nhãn trên đồ thị và thuật toán tự huấn luyện. Đối tượng nghiên cứu: Học nửa giám sát. Phạm vi nghiên cứu: - Nghiên cứu tổng quan về học có giám sát, học không giám sát và học nửa giám sát. - Các phƣơng pháp học nửa giám sát phổ biến. - Phƣơng pháp học nửa giám sát dựa trên đồ thị (Graph-based) và một số thuật toán. - Cài đặt thử nghiệm thuật toán lan truyền nhãn trong phƣơng pháp học nửa giám sát dựa trên đồ thị và thuật toán tự huấn luyện. Các luận điểm chính mà luận văn đã thể hiện đƣợc: Nghiên cứu tổng quan và đánh giá các phƣơng pháp học nửa giám sát, tập trung vào phƣơng pháp học nửa giám sát dựa trên đồ thị. Tập trung tìm hiểu một số thuật toán trong lĩnh vực học nửa giám sát nhƣ: Phƣơng pháp EM với mô hình sinh hỗn hợp, phƣơng pháp Tự huấn luyện, phƣơng pháp Đồng huấn luyện và phƣơng pháp máy véc tơ hỗ trợ. Đồng thời tập trung nghiên cứu chi tiết phƣơng pháp dựa trên đồ thị. Cài đặt phần mềm thử nghiệm mô phỏng thuật toán lan truyền nhãn và thuật toán tự huấn luyện, đánh giá độ phức tạp của hai thuật toán này. Số hóa bởi Trung tâm Học liệu – ĐHTN - Đọc tài liệu, phân tích, tổng hợp. - Thống kê, phân tích dữ liệu. - Thực nghiệm và đánh giá kết quả. - Kết hợp nghiên cứu lý thuyết, tìm hiểu tình hình ứng dụng, đánh giá khả năng ứng dụng và đề xuất giải pháp. 6. Nội dung luận văn gồm 03 chƣơng: Chƣơng 1: Tổng quan về các phƣơng pháp học máy Chƣơng này trình bày tổng quan về các phƣơng pháp học máy gồm phƣơng pháp Học có giám sát (Supervised learning), Học không giám sát (Unsupervised learning), Học nửa giám sát (Semi-Supervised learning). Chƣơng 2: Phƣơng pháp học nửa giám sát dựa trên đồ thị Tập trung tìm hiểu một số thuật toán trong lĩnh vực học nửa giám sát nhƣ: Phƣơng pháp EM với mô hình sinh hỗn hợp, phƣơng pháp Tự huấn luyện, phƣơng pháp Đồng huấn luyện và phƣơng pháp máy véc tơ hỗ trợ. Đồng thời tập trung nghiên cứu chi tiết phƣơng pháp dựa trên đồ thị. Chƣơng 3: Cài đặt và thử nghiệm thuật toán Cài đặt thử nghiệm thuật toán tự huấn luyện và lan truyền nhãn dựa trên đồ thị . Số hóa bởi Trung tâm Học liệu – ĐHTN CHƢƠNG 1: TỔNG QUAN VỀ CÁC PHƢƠNG PHÁP HỌC MÁY 1.1. Giới thiệu về học máy Học máy (Machine Learning) là một ngành khoa học nghiên cứu các thuật toán cho phép máy tính có thể học đƣợc các khái niệm (concept)[7]. Có hai loại phƣơng pháp học máy chính: Phƣơng pháp quy nạp: Máy học/phân biệt các khái niệm dựa trên dữ liệu đã thu thập đƣợc trƣớc đó. Phƣơng pháp này cho phép tận dụng đƣợc nguồn dữ liệu rất nhiều và sẵn có. Phƣơng pháp suy diễn: Máy học/phân biệt các khái niệm dựa vào các luật. Phƣơng pháp này cho phép tận dụng đƣợc các kiến thức chuyên ngành để hỗ trợ máy tính. Hiện nay, các thuật toán đều cố gắng tận dụng đƣợc ƣu điểm của hai phƣơng pháp này. Các ngành khoa học liên quan đến lĩnh vực học máy điển hình là: Lý thuyết thống kê: các kết quả trong xác suất thống kê là tiền đề cho rất nhiều phƣơng pháp học máy. Đặc biệt, lý thuyết thống kê cho phép ƣớc lƣợng sai số của các phƣơng pháp học máy. Các phƣơng pháp tính: các thuật toán học máy thƣờng sử dụng các tính toán số thực/số nguyên trên dữ liệu rất lớn. Trong đó, các bài toán nhƣ: tối ƣu có/không ràng buộc, giải phƣơng trình tuyến tính v.v đƣợc sử dụng rất phổ biến. Khoa học máy tính: là cơ sở để thiết kế các thuật toán, đồng thời đánh giá thời gian chạy, bộ nhớ của các thuật toán học máy. Lĩnh vực học máy truyền thống thƣờng đƣợc chia thành bốn lĩnh vực con: Học có giám sát: Máy tính đƣợc xem một số mẫu gồm đầu vào và đầu ra tƣơng ứng trƣớc. Sau khi học xong các mẫu này, máy tính quan sát một đầu vào mới và cho ra kết quả. Học không giám sát: Máy tính chỉ đƣợc xem các mẫu không có đầu ra, sau đó máy tính phải tự tìm cách phân loại các mẫu này và các mẫu mới. Số hóa bởi Trung tâm Học liệu – ĐHTN Học nửa giám sát: Một dạng lai giữa hai nhóm giải thuật trên. Học tăng cƣờng: Máy tính đƣa ra quyết định hành động và nhận kết quả phản hồi từ môi trƣờng. Sau đó máy tính tìm cách chỉnh sửa cách ra quyết định hành động của mình. Học máy có ứng dụng rộng khắp trong các ngành khoa học/sản xuất, đặc biệt những ngành cần phân tích khối lƣợng dữ liệu khổng lồ. Một số ứng dụng thƣờng thấy: Xử lý ngôn ngữ tự nhiên (Natural Language Processing): xử lý văn bản, giao tiếp ngƣời – máy, Nhận dạng (Pattern Recognition): nhận dạng tiếng nói, chữ viết tay, vân tay, thị giác máy (Computer Vision) Tìm kiếm (Search Engine) Chẩn đoán trong y tế: phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán tự động. Tin sinh học: phân loại chuỗi gene, quá trình hình thành gene/protein Vật lý: phân tích ảnh thiên văn, tác động giữa các hạt Phát hiện gian lận tài chính (financial fraud): gian lận thẻ tỉn dụng Phân tích thị trƣờng chứng khoán (stock market analysis) Chơi trò chơi: tự động chơi cờ, hành động của các nhân vật ảo Rôbốt: là tổng hợp của rất nhiều ngành khoa học, trong đó học máy tạo nên hệ thần kinh/bộ não của ngƣời máy. Trong đó phải kể đến các ứng dụng quan trọng nhất của nó trong khai phá dữ liệu. Khai phá dữ liệu (Data mining) là quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. Khai phá dữ liệu là một bƣớc của quá trình khai phá tri thức, bao gồm: Xác định vấn đề và không gian dữ liệu để giải quyết vấn đề. Chuẩn bị dữ liệu, bao gồm các quá trình làm sạch dữ liệu, tích hợp dữ liệu, chọn dữ liệu, biến đổi dữ liệu. Khai phá dữ liệu: xác định nhiệm vụ khai phá dữ liệu và lựa chọn kĩ thuật khai phá dữ liệu. Kết quả cho ta một nguồn tri thức thô. Số hóa bởi Trung tâm Học liệu – ĐHTN Đánh giá: dựa trên một số tiêu chí tiến hành kiểm tra và lọc nguồn tri thức thu đƣợc. Triển khai. Quá trình khai phá tri thức không chỉ là một quá trình tuần tự từ bƣớc đầu tiên đến bƣớc cuối cùng mà là một quá trình lặp và có quay trở lại các bƣớc đã qua. Về cơ bản, khai phá dữ liệu có thể ứng dụng cho bất kỳ kho thông tin nào bao gồm: Các cơ sở dữ liệu quan hệ, kho dữ liệu, các cơ sở dữ liệu giao tác, các hệ thống cơ sở dữ liệu tiên tiến, các tệp, ... Phân lớp dữ liệu Phân lớp dữ liệu là kĩ thuật dựa trên tập dữ liệu huấn luyện và những giá trị trong một thuộc tính phân lớp (hay còn gọi là nhãn của lớp), sử dụng nó trong việc phân lớp dữ liệu mới. Phân lớp 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òn có một hình thức tƣơng tự gọi 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 những hàm đánh giá liên tục[6]. Kĩ thuật phân lớp đƣợc tiến hành bao gồm 2 bƣớc: Xây dựng mô hình và sử dụng mô hình. 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át đị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 . Sử dụng mô hình: 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 Số hóa bởi Trung tâm Học liệu – ĐHTN (quan sát, thẩm định ...) đ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 này. Trong phƣơng pháp học máy truyền thống, để phân lớp dữ liệu ta chỉ sử dụng một tập dữ liệu đã đƣợc gán nhãn để huấn luyện. Tuy nhiên, để có đƣợc các mẫu dữ liệu đã đƣợc gán nhãn thƣờng khó khăn, tốn kém thời gian và chi phí hay nó đòi hỏi những nỗ lực của các chuyên gia. Trong khi đó, dữ liệu chƣa đƣợc gán nhãn có thể sƣu tầm tƣơng đối dễ dàng, và có một số phƣơng pháp để sử dụng chúng. Học nửa giám sát đề cập tới vấn đề này bằng cách sử dụng một số lƣợng lớn các dữ liệu chƣa đƣợc gán nhãn cùng với các dữ liệu đã đƣợc gán nhãn để xây dựng các bộ phân lớp tốt hơn. Do học nửa giám sát đòi hỏi nỗ lực của con ngƣời ít hơn và đƣa ra độ chính xác cao, đó là sự quan tâm lớn cả về lý thuyết và thực hành. Để hiểu bản chất của học nửa giám sát, ta sẽ xem xét các khái niệm về học có giám sát, học không giám sát và học tăng cƣờng. 1.2. Các phƣơng pháp học máy 1.2.1. Học có giám sát Học có giám sát là một kỹ thuật của ngành học máy nhằm mục đích xây dựng một hàm f từ dữ tập dữ liệu huấn luyện (Training data). Dữ liệu huấn luyện bao gồm các cặp đối tƣợng đầu vào và đầu ra mong muốn. Đầu ra của hàm f có thể là một giá trị liên tục hoặc có thể là dự đoán một nhãn phân lớp cho một đối tƣợng đầu vào[8]. Nhiệm vụ của chƣơng trình học có giám sát là dự đoán giá trị của hàm f cho một đối tƣợng đầu vào hợp lệ bất kì, sau khi đã xét một số mẫu dữ liệu huấn luyện (nghĩa là các cặp đầu vào và đầu ra tƣơng ứng). Để đạt đƣợc điều này, chƣơng trình học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán đƣợc những tình huống chƣa gặp phải theo một cách hợp lý. Phƣơng pháp học có giám sát có thể đƣợc mô tả tóm tắt nhƣ sau: Hệ thống học sẽ quan sát một tập dữ liệu huấn luyện đã đƣợc gán nhãn, bao gồm các cặp (đặc tính, nhãn), đƣợc biểu diễn bởi {(x1, y1), (x2, y2), ..., (xn, yn)}. Mục đích nhằm dự đoán nhãn y cho bất kỳ đầu vào mới với đặc tính x. Một nhiệm Số hóa bởi Trung tâm Học liệu – ĐHTN vụ của học có giám sát đƣợc gọi là hồi quy khi y ∈ ℝ và phân lớp khi y có một tập các giá trị rời rạc. Để giải quyết bài toán học có giám sát, ta phải thực hiện các bước sau: 1. Xác định loại dữ liệu huấn luyện: Đầu tiên ta nên xác định xem loại dữ liệu nào sẽ đƣợc sử dụng làm dữ liệu huấn luyện. Chúng có thể là dữ liệu liên tục hay dữ liệu rời rạc, hoặc một dạng đặt biệt nào đó. 2. Xây dựng tập dữ liệu huấn luyện: Việc thu thập để tạo nên tập dữ liệu huấn luyện là quan trọng vì nó sẽ phục vụ cho việc sử dụng hàm huấn luyện f. Dữ liệu huấn luyện có thể thu thập đƣợc từ nhiều nguồn khác nhau: dữ liệu đầu vào, số liệu đo đạc, tri thức hay kinh nghiệm của các chuyên gia lĩnh vực, 3. Biễu diễn các đặc trƣng đầu vào: Sự chính xác của hàm chức năng phụ thuộc lớn vào cách các đối tƣợng đầu vào đƣợc biểu diễn. Thông thƣờng, đối tƣợng đầu vào đƣợc chuyển đổi thành một vec-tơ đặc trƣng, chứa một số các đặc trƣng nhằm mô tả cho đối tƣợng đó. Số lƣợng các đặc trƣng không nên quá lớn nhƣng phải đủ lớn để việc dự đoán đầu ra đƣợc chính xác. 4. Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tƣơng ứng. Ví dụ, có thể lựa chọn việc sử dụng giải thuật K-láng giềng gần nhất hay giải thuật cây quyết định, 5. Hoàn thiện thiết kế. Ngƣời kĩ sƣ sẽ chạy giải thuật học từ tập huấn luyện thu thập đƣợc. Các tham số của giải thuật học có thể đƣợc điều chỉnh bằng cách tối ƣu hóa hiệu năng trên một tập con (gọi là tập kiểm chứng -validation set) của tập huấn luyện, hay thông qua kiểm chứng chéo (cross-validation). Sau khi học và điều chỉnh tham số, hiệu năng của giải thuật có thể đƣợc đo đạc trên một tập kiểm tra độc lập với tập huấn luyện. Các thuật toán sử dụng trong học có giám sát nhƣ: Cây quyết định (Decision Trees), Máy véc tơ hỗ trợ (Support Vector Machine (SVM)), k-láng giềng gần nhất (k- Nearest Neighbor), Cực đại Entropy (Maximum Entropy (MaxEnt)), Naive Bayes,... 1.2.2. Học không giám sát Học không giám sát là một phƣơng pháp của ngành học máy nhằm tìm ra Số hóa bởi Trung tâm Học liệu – ĐHTN một mô hình phù hợp với các quan sát. Nó khác với học có giám sát ở chỗ là đầu ra đúng tƣơng ứng cho mỗi đầu vào là không biết trƣớc. Trong học không giám sát, một tập dữ liệu đầu vào đƣợc thu thập. Học không giám sát thƣờng đối xử với các đối tƣợng đầu vào nhƣ là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ đƣợc xây dựng cho tập dữ liệu đó[8]. Học không giám sát có thể đƣợc dùng kết hợp với suy diễn Bayes (Bayesian inference) để cho ra xác suất có điều kiện (nghĩa là học có giám sát) cho bất kì biến ngẫu nhiên nào khi biết trƣớc các biến khác. Học không giám sát cũng hữu ích cho việc nén dữ liệu: về cơ bản, mọi giải thuật nén dữ liệu hoặc là dựa vào một phân bố xác suất trên một tập đầu vào một cách tƣờng minh hoặc không tƣờng minh. Phân cụm dữ liệu Một ứng dụng khác của học không giám sát là phân cụm dữ liệu (data clustering). Phân cụm đƣợc xem nhƣ vấn đề quan trọng nhất trong học không giám sát, vì nhƣ các vấn đề khác của phân cụm dữ liệu, nó có liên quan tới việc tìm kiếm một cấu trúc trong một tập các dữ liệu không có nhãn[3]. Một định nghĩa rộng hơn về phân cụm: “ phân cụm là quá trình tổ chức các đối tƣợng dữ liệu vào trong các nhóm trong đó các đối tƣợng giống nhau theo một cách nào đó”. Do đó, một cụm là một tập hợp các đối tƣợng mà giữa chúng có sự giống nhau và khác với các đối tƣợng thuộc về các cụm khác. Hình 1.1: Phƣơng pháp phân cụm dữ liệu. Trong ví dụ trên, chúng ta có thẻ dễ dàng xác định đƣợc 4 cụm mà trong đó Số hóa bởi Trung tâm Học liệu – ĐHTN dữ liệu đƣợc phân chia. Tiêu chí giống nhau ở đây là “khoảng cách”, hai hay nhiều đối tƣợng thuộc về một cụm nếu chúng gần nhau hơn dựa theo khoảng cách đƣa ra. Điều này gọi là phân cụm dựa trên khoảng cách. Một dạng khác của phân cụm là Phân cụm khái niệm, hai hay nhiều đối tƣợng thuộc về một cụm nếu ta định nghĩa một khái niệm phổ biến cho tất cả các đối tƣợng. Tóm lại, các đối tƣợng đƣợc nhóm lại theo điều kiện mô tả chúng. Mục đích của phân cụm dữ liệu Mục đích của việc phân cụm dữ liệu là để xác định các nhóm trong một tập các dữ liệu không có nhãn. Nhƣng làm thế nào để quyết định đƣợc điều gì tạo nên việc phân cụm tốt. Có thể nói rằng, không có một tiêu chuẩn tuyệt đối nào là tốt nhất, do đó ngƣời sử dụng phải đƣa ra các tiêu chuẩn này để các dữ liệu sau khi đƣợc phân cụm sẽ phù hợp với yêu cầu của ngƣời sử dụng. Các ứng dụng của Phân cụm dữ liệu Các thuật toán phân cụm dữ liệu có thể áp dụng trong nhiều lĩnh vực, ví dụ nhƣ: Tiếp thị: việc tìm ra các nhóm khách hàng có hành vi giống nhau sẽ đƣa ra một CSDL lớn chứa thông tin khách hàng và thông tin mua sắm của họ. Sinh học: phân loại động vật và thực vật dựa trên các đặc trƣng của chúng Thƣ viện: đặt sách www: phân lớp văn bản, phân cụm dữ liệu weblog để xác định các nhóm ngƣời truy cập tƣơng tự nhau. Các yêu cầu với thuật toán phân cụm: Các yêu cầu chính mà một thuật toán phân cụm cần đáp ứng là: Khả năng mở rộng Đối xử với các loại thuộc tính khác nhau của đối tƣợng dữ liệu Phát hiện ra các cụm với hình dạng có thể là bất kỳ. Tối thiểu hóa yêu cầu cho miền tri thức để xác định các tham số đầu vào. Khả năng xử lý các dữ liệu tạp và sự chênh lệch,... Các thuật toán đƣợc sử dụng phổ biến nhất hiện nay: K-means, Fuzzy C-means, Phân cụm có thứ bậc, Hỗn hợp Gaussian. Số hóa bởi Trung tâm Học liệu – ĐHTN 1.2.3. Học tăng cƣờng Học tăng cƣờng là một lĩnh vực con của ngành học máy, nghiên cứu cách thức để một Agent nên chọn thực hiện các hành động nào trong một “môi trƣờng” để cực đại hóa số “phần thƣởng” nào đó. “Môi trƣờng” trong học tăng cƣờng đƣợc biểu diễn dƣới dạng một quá trình trạng thái quyết định hữu hạn Markov (Markov decision process – MDP)[8]. Cụ thể hơn, trong học tăng cƣờng, các Agent tƣơng tác với môi trƣờng của nó bằng cách đƣa ra các hành động a1, a2, ... Những hành động này ảnh hƣởng tới trạng thái của môi trƣờng do đó kết quả nhận đƣợc trong Agent lần lƣợt là số phần thƣởng hoặc hình phạt r1, r2,... Mục đích của Agent là học một hành động trong một cách nào đó để cực đại hóa thuộc tính phần thƣởng nó nhận đƣợc (hay cực tiểu hóa rủi ro) trên vòng đời của nó. Khác với học có giám sát, học tăng cƣờng không có các cặp dữ liệu vào hay kết quả đúng, các hành động gần tối ƣu cũng không đƣợc đánh giá đúng sai một cách tƣờng... bằng nhau và 1 trong các trƣờng hợp khác. Nếu hàm khoảng cách toàn cục đƣợc định nghĩa nhƣ là tổng của các hàm khoảng cách cục bộ thì chúng ta sẽ đếm số lƣợng các thuộc tính mà trên đó hai trƣờng hợp không đồng nhất. Điều này gọi là khoảng cách Hamming. Tổng trọng số và trọng số trung bình cũng có thể xảy ra. 2.3.3. Khoảng cách Manhattan cho các thuộc tính số học Nếu một thuộc tính là thuộc tính số học thì hàm khoảng cách cục bộ có thể đƣợc định nghĩa nhƣ độ chênh lệch tuyệt đối của các giá trị: Số hóa bởi Trung tâm Học liệu – ĐHTN Nếu khoảng cách toàn cục đƣợc tính bằng tổng của các khoảng cách cục bộ này thì chúng ta đề cập tới khoảng cách Manhattan. Tổng trọng số và trọng số trung bình cũng có thể xảy ra. Một nhƣợc điểm của khoảng cách Manhattan đó là, nếu một trong số các thuộc tính có miền giá trị tƣơng đối lớn thì nó có thể sẽ chế ngự các thuộc tính khác. Vì vậy, khoảng cách cục bộ thƣờng đƣợc chuẩn hóa, do đó chúng nằm trong phạm vi từ 0 đến 1. Có nhiều cách để chuẩn hóa. Để đơn giản, chúng ta chỉ xét một công thức sau. Chúng ta chia miền giá trị chấp nhận đƣợc: Trong đó, Amax là giá trị lớn nhất có thể của A và Amin là giá trị nhỏ nhất có thể của A. Chúng ta gọi là khoảng cách đã đƣợc chuẩn hóa. Một nhƣợc điểm nữa của ý tƣởng này là nó chỉ có thể đƣợc sử dụng trên các thuộc tính số học. 2.3.4. Các hàm khoảng cách cục bộ không đồng nhất Chúng ta có thể kết hợp khoảng cách tuyệt đối và độ trùng khớp để xử lý cả hai thuộc tính số và thuộc tính ký hiệu (symbolic): Khoảng cách toàn cục ở đây có thể đƣợc tính bằng tổng trọng số hoặc trọng số trung bình của khoảng cách cục bộ. 2.3.5. Hàm khoảng cách tri thức chuyên gia Các chuyên gia đôi khi có thể định nghĩa miền đặc biệt cho hàm khoảng cách cục bộ, đặc biệt là cho các giá trị-ký hiệu của các thuộc tính. Một ví dụ tuy không phải là phổ biến là khi có một số định nghĩa ở phần trƣớc trên các giá trị của các thuộc tính ký hiệu. Ví dụ, bữa ăn cuối cùng một ngƣời đã ăn có các giá trị là: không ăn gì, ăn nhanh và ăn đầy đủ. Những thứ này có thể đƣợc nghĩ tới một thứ tự đã đƣợc sắp xếp trƣớc về số lƣợng thức ăn tiêu thụ: không Số hóa bởi Trung tâm Học liệu – ĐHTN ăn gì < ăn nhanh < ăn đầy đủ. Chúng ta có thể phân chia các giá trị số nguyên nhƣ sau: không ăn gì = 0; ăn nhanh = 1; ăn đầy đủ = 2. Bây giờ chúng ta có thể sử dụng công thức sau: Nhƣ vậy, chúng ta đã tìm hiểu một số hàm xác định khoảng cách giữa các điểm dữ liệu với các miền thuộc tính khác nhau. Sau đây chúng ta sẽ nghiên cứu thuật toán lan truyền nhãn trên đồ thị (Label Propagation). Ý tƣởng của thuật toán là nhãn của các đỉnh sẽ đƣợc lan truyền tới các đỉnh láng giềng dựa vào các đỉnh gần chúng. Trong quá trình này, ta cố định các nhãn trên tập dữ liệu đã đƣợc gán nhãn. Do đó dữ liệu đã đƣợc gán nhãn sẽ đƣợc xem nhƣ một tập nguồn và đƣa ra các nhãn thông qua dữ liệu chƣa đƣợc gán nhãn. 2.4. Thuật toán lan truyền nhãn trong đồ thị 2.4.1. Ký hiệu Hình 2.7: Đồ thị với các trọng số cạnh Cho đồ thị G = (V, E, W), trong đó: - V: Tập các đỉnh, |V|=n. - E: tập các cạnh - W: Ma trận trọng số các cạnh tính theo công thức Euclid (Wn×n) Số hóa bởi Trung tâm Học liệu – ĐHTN - n: Số lƣợng đỉnh trong G, n=nℓ+n . . nℓ: số đỉnh đã đƣợc gán nhãn . n : số đỉnh chƣa đƣợc gán nhãn - C: tập các nhãn, thể hiện số lƣợng các nhãn, với |C|=m. - P: Ma trận xác suất chuyển đổi nhãn, Pn×n - Y: ma trận nhãn ban đầu Yℓ×C - f: là ma trận fn×m, lƣu trữ thông tin của các nhãn của đỉnh đang huấn luyện. Phƣơng pháp học nửa giám sát với đồ thị sẽ tính ma trận f từ các ma trận P, Y. 2.4.2. Nội dung thuật toán Cho {(x1, y1)(xℓ, yℓ)} là các dữ liệu đã gán nhãn, YL={y1, yℓ} là các nhãn của các lớp, y ={1..C} và {xℓ+1 xℓ+u} là các dữ liệu chƣa đƣợc gán nhãn, thƣờng ℓ≪u. Cho n=ℓ+u. Chúng ta thƣờng sử dụng L và U để thể hiện tƣơng ứng với tập dữ liệu đã gán nhãn và tập dữ liệu chƣa gán nhãn. Giả sử rằng, số lƣợng các lớp C là đã biết và tất cả các lớp đã đƣợc thể hiện trong dữ liệu đã gán nhãn. Chúng ta sẽ nghiên cứu bài toán lan truyền cho việc tìm kiếm các nhãn cho tập U. Bằng trực giác chúng ta muốn các điểm dữ liệu tƣơng tự nhau sẽ có cùng nhãn. Ta tạo ra một đồ thị đầy đủ mà các đỉnh là tất cả các điểm dữ liệu, cả dữ liệu đã gán nhãn và chƣa gán nhãn. Cạnh nối bất kỳ giữa đỉnh i và đỉnh j biểu thị cho sự giống nhau của chúng. Giả sử đồ thị là đầy đủ với các trọng số sau đây, các trọng số đƣợc điều khiển bởi tham số . hoặc cụ thể hơn Trong đó: dij là khoảng cách giữa điểm dữ liệu xi và xj. Có thể lựa chọn cách tính giá trị khoảng cách khác nhau, tuy nhiên có lẽ là phù hợp nếu x là các giá trị rời rạc. Trong phạm vi thuật toán này, chúng tôi lựa chọn khoảng cách Euclid để xác định khoảng cách giữa các điểm dữ liệu và tùy theo Số hóa bởi Trung tâm Học liệu – ĐHTN các giá trị siêu tham số cho mỗi chiều thuộc tính. Tất cả các đỉnh có nhãn mềm có thể thay đổi nhãn trong quá trình thực hiện việc lan truyền nhãn và đƣợc hiểu là phân phối nhãn. Chúng ta cho nhãn của một đỉnh lan truyền tới tất cả các đỉnh khác thông qua các cạnh giữa chúng. Cạnh có trọng số lớn hơn cho phép các nhãn đi qua dễ dàng hơn. Ta định nghĩa một Ma trận xác suất chuyển đổi Pn×n. Trong đó Pij là xác suất để nhảy từ đỉnh i tới j. Cũng định nghĩa một ma trận nhãn YL ℓ×C mà dòng thứ i của chúng là một véctơ chỉ số cho yi, i ∈ L: Yic=δ(yi, c). Chúng ta sẽ tính toán nhãn mềm f cho các đỉnh. f là ma trận n × C (f n×C), các hàng có thể đƣợc thể hiện nhƣ sự phân bổ xác suất trên các nhãn. Việc khởi tạo giá trị ban đầu cho f là không quan trọng. Sau đây chúng ta sẽ xem xét thuật toán: Thuật toán: Đầu vào: đồ thị vô hƣớng bao gồm các đỉnh đã gán nhãn và các đỉnh chƣa gán nhãn. Đầu ra: đồ thị vô hƣớng với các đỉnh đã đƣợc gán nhãn. Thuật toán lan truyền nhãn thực hiện theo các bƣớc sau: Bƣớc 1. Lan truyền: f ← Pf Bƣớc 2. Gán (giữ lại) các dữ liệu đã gán nhãn fL = YL (YL đã xây dựng ở trên) Bƣớc 3. Lặp lại từ bƣớc 1 cho tới khi f hội tụ. Trong bƣớc 1, tất cả các đỉnh lan truyền các nhãn tới các láng giềng của chúng. Bƣớc 2 là quan trọng: chúng ta muốn giữ lại các nhãn từ dữ liệu đã gán nhãn. Vì vậy, thay vì cho việc làm các nhãn mờ đi, chúng ta giữ lại chúng ở ma trận YL. Với sự hỗ trợ từ các đỉnh đã đƣợc gán nhãn, các lớp biên có thể đƣợc phân loại thông qua các vùng có tỉ trọng cao và các vùng tỉ trọng thấp. 2.4.3. Sự hội tụ của thuật toán Bây giờ ta thể hiện sự hội tụ của thuật toán tới một lời giải đơn giản. Số hóa bởi Trung tâm Học liệu – ĐHTN Cho f dƣới dạng sau: . Vì fL đƣợc gán bằng YL nên chúng ta chỉ quan tâm đến fU. (fU chính là phần ma trận của các phần tử chƣa đc gán nhãn). Mục đích của chúng ta cũng là xác định ma trận fU này. Chia ma trận P thành ma trận con đã gán nhãn và ma trận con chƣa gán nhãn, có dạng: Theo công thức ở trên, thuật toán có thể đƣợc mô tả nhƣ sau : Dẫn đến 0 Trong đó, f U là giá trị khởi tạo ban đầu của fU. Chúng ta cần cho thấy Vì P có các hàng bình thƣờng và PUU là ma trận con của P, dẫn đến: Do đó n Do đó tổng các hàng của (PUU) hội tụ về 0. Điều này có nghĩa rằng Số hóa bởi Trung tâm Học liệu – ĐHTN 0 Do đó giá trị khởi tạo của f U là không quan trọng. Mà −1 fU=(I−PUU) PULYL là cố định. Do đó nó là điểm cố định duy nhất và là lời giải cho việc lặp lại thuật toán. Điều này đƣa ra cho chúng ta một cách giải quyết bài toán lan truyền nhãn một cách trực tiếp không cần lan truyền lặp lại. Lƣu ý: lời giải này khả thi khi ma trận (1-PUU) có thể nghịch đảo đƣợc. Điều kiện này sẽ đƣợc thỏa mãn khi mọi thành phần kết nối trong đồ thị có ít nhất một điểm dữ liệu đƣợc gán nhãn. 2.4.4. Phƣơng pháp xác định siêu tham số của đồ thị Các thuật toán học nửa giám sát đã đƣợc áp dụng thành công trong nhiều ứng dụng với số lƣợng ít dữ liệu có nhãn bằng cách sử dụng các dữ liệu không có nhãn. Một vấn đề quan trọng là các thuật toán học nửa giám sát dựa trên đồ thị phụ thuộc vào chất lƣợng của đồ thị hay siêu tham số của nó[6]. Phƣơng pháp học nửa giám sát dựa trên đồ thị tạo ra một đồ thị mà các đỉnh tƣợng trƣng cho dữ liệu có nhãn và chƣa có nhãn, trong khi các cạnh đƣợc thể hiện sự giống nhau giữa các cặp điểm dữ liệu. Sự phân lớp ở đây đƣợc thực hiện bằng cách sử dụng đồ thị và gán nhãn cho các dữ liệu chƣa có nhãn dựa vào việc các đỉnh đƣợc kết nối bởi các cạnh có trọng số lớn hơn thì sẽ có nhãn giống nhau. Các bộ phân lớp phụ thuộc đáng kể vào độ đo tƣơng tự của đồ thị, thƣờng đƣợc thực hiện theo hai bƣớc. Bƣớc thứ nhất, các trọng số cạnh đƣợc xác định cục bộ bằng cách sử dụng các hàm tính khoảng cách. Các hàm tính khoảng cách đóng vai trò thành phần quan trọng trong học nửa giám sát dựa trên đồ thị để có đƣợc một khoảng cách tốt nhất. Bƣớc thứ hai là bƣớc làm mịn, đƣợc áp dụng vào toàn bộ đồ thị, điển hình là dựa trên sự lan truyền quang phổ của đồ thị Laplace. Hiện nay, mới chỉ có một vài phƣơng pháp tiếp cận để giải quyết vấn đề học trên đồ thị nhƣ: Học không tham số trên đồ thị Laplace, phƣơng pháp này giả sử rằng trọng số và khoảng cách đƣợc đƣa ra trƣớc; Học có tham số trên đồ thị sử dụng phƣơng pháp chứng minh cực đại hóa sử dụng suy luận xấp xỉ gradient. Việc sử dụng chứng minh cực đại hóa và xấp xỉ Laplace để học các tham số đơn giản của Số hóa bởi Trung tâm Học liệu – ĐHTN các hàm tƣơng tự vì chỉ học trên một đồ thị tốt, đề xuất xây dựng các đồ thị mạnh hơn bằng cách áp dụng sự xáo trộn ngẫu nhiên và bỏ đi cạnh từ một tập các cạnh trong cây bao trùm nhỏ nhất. Kết hợp đồ thị Laplace để học đồ thị. Học các băng thông khác nhau với các chiều khác nhau bằng phƣơng pháp cực tiểu hóa Entropy trên dữ liệu chƣa gán nhãn, giống nhƣ phƣơng pháp lề cực đại trong TSVM. Trở lại với công thức tính ma trận W trong nội dung thuật toán Lan truyền nhãn (Labeled Propagation), siêu tham số của đồ thị đƣợc ký kiệu là α. Ma trận trọng số W đƣợc đƣa ra là cố định. Sau đây chúng ta nghiên cứu việc học các trọng số từ cả dữ liệu gán nhãn và dữ liệu chƣa gán nhãn. Có một số phƣơng pháp dùng để xác định siêu tham số nhƣ: Phƣơng pháp chứng minh cực đại trong các tiến trình Gaussian (Evidence Maximization), Phƣơng pháp Cực tiểu hóa Entropy (Entropy Minimization) và phƣơng pháp Cây khung nhỏ nhất (Minimum spanning tree). Sau đây, chúng ta sử dụng phƣơng pháp Cây khung nhỏ nhất, để xác định siêu tham số cho đồ thị. Phƣơng pháp cây khung nhỏ nhất: Nếu các cạnh của đồ thị đƣợc đánh trọng số exp với một siêu tham số , ta có thể xác định giá trị tham số này theo thuật toán sau: Ta xây dựng một cây khung nhỏ nhất trên tất cả các điểm dữ liệu với thuật toán Kruskal[6]. Ban đầu không có đỉnh nào đƣợc nối với nhau. Trong suốt quá trình phát triển cây, các cạnh lần lƣợt đƣợc xác định bởi trọng số từ ngắn đến dài. Một cạnh đƣợc thêm vào cây nếu nó kết nối hai thành phần riêng biệt với nhau. Quá trình lặp lại cho tới khi toàn bộ đồ thị đƣợc kết nối. Ta tìm ra cạnh đầu tiên của cây mà kết nối hai thành phần với nhãn khác nhau. Ta coi độ dài của cạnh này là d0 nhƣ là một giải thuật tối thiểu hóa khoảng cách giữa các vùng lớp với nhau. Sau đó ta đặt = d0/3 theo quy tắc 3α, do đó trọng số của cạnh này sẽ gần tới 0, với hy vọng rằng việc lan truyền cục bộ chủ yếu bên trong các lớp. Số hóa bởi Trung tâm Học liệu – ĐHTN 2.4.5. Độ phức tạp của thuật toán Thuật toán lan truyền nhãn đƣợc thực hiện dựa trên quá trình tính toán các ma trận và việc lặp lại để xác định sự hội tụ của thuật toán. Đầu vào của thuật toán là một đồ thị, trong đó: ℓ: số đỉnh đã gán nhãn. u: số đỉnh chƣa gán nhãn (u ≫ ℓ). n = ℓ + u : tổng số đỉnh của đồ thị. Thuật toán thực hiện các quá trình tính toán với độ phức tạp của các thành phần nhƣ sau: - Quá trình xác định các ma trận trọng số W, ma trận xác suất P, ma trận xác suất chuyển nhãn PUU, ma trận xác suất PUL, ma trận nhãn YL, ma trận xác suất nhãn f, có độ phức tạp: O(n2). (*) - Quá trình xác định siêu tham số α dựa trên thuật toán tìm cây khung nhỏ nhất, có độ phức tạp: O (n2×log n). (**) - Quá trình lặp để thực hiện việc lan truyền nhãn đƣợc thực hiện trong m bƣớc lặp (m khá lớn), trong đó: việc xác định sự hội tụ của thuật toán dựa trên quá trình tính toán các định thức ma trận, các phép toán nhân ma trận và tìm ma trận nghịch đảo, có độ phức tạp: O(n3). Do đó, độ phức tạp của quá trình lặp là: O (m x n3). (***) Từ (*), (**) và (***) suy ra độ phức tạp của thuật toán la truyền nhãn là: O (m x n3). 2.5. Thuật toán học nửa giám sát dựa trên đồ thị - Mincut Thuật toán Mincut là một thuật toán dựa trên việc tìm kiếm một lát cắt nhỏ nhất trên đồ thị, chúng sử dụng các cặp quan hệ giữa các điểm dữ liệu để học từ cả dữ liệu đã gán nhãn và chƣa gán nhãn. Thuật toán sử dụng một độ đo tƣơng tự giữa các điểm dữ liệu để xây dựng đồ thị và sau đó đƣa ra kết quả phân loại dữ liệu tƣơng ứng với việc phân chia đồ thị bằng cách cực tiểu hóa số lƣợng các cặp dữ liệu tƣơng tự nhau mà có nhãn khác nhau[4]. Bài toán cho trƣớc một tập dữ liệu đã gán nhãn và chƣa gán nhãn, chúng ta xây dựng một đồ thị trên các mẫu dữ liệu này, do đó lát cắt nhỏ nhất trên đồ thị này sẽ cho ta việc gán nhãn nhị phân tối ƣu trên các dữ liệu chƣa gán nhãn theo một Số hóa bởi Trung tâm Học liệu – ĐHTN hàm tối ƣu nhất định. Giống nhƣ hầu hết các phƣơng pháp tiếp cận khác dùng để kết hợp dữ liệu đã gán nhãn và chƣa gán nhãn, ý tƣởng chính của thuật toán này là gán giá trị cho các dữ liệu chƣa có nhãn để tối ƣu hóa một hàm mục tiêu có liên quan. Với phƣơng pháp tiếp cận Mincut, loại hàm đƣợc tối ƣu đƣợc giới hạn để chỉ phụ thuộc vào mối quan hệ giữa các cặp dữ liệu. Điều gì làm cho phƣơng pháp này thực sự đƣợc quan tâm? Đó là các hàm chúng ta có thể xử lý, các lát cắt đồ thị đƣa ra một thuật toán có thời gian đa thức để tìm ra sự tối ƣu hóa toàn cục. Thuật toán Mincut Giả sử, xét bài toán phân lớp nhị phân (dữ liệu đã gán nhãn đƣợc ký hiệu bởi +, dữ liệu chƣa gán nhãn đƣợc ký hiệu bởi − ), L: là tập các dữ liệu đã gán nhãn, U: là tập các dữ liệu chƣa gán nhãn, L+: tập các dữ liệu có nhãn dƣơng trong tập L, L−: tập các dữ liệu có nhãn âm trong tập L. Thuật toán nhƣ sau: Bƣớc 1 . Xây dựng một đồ thị trọng số G=(V, E) trong đó V=L ∪ U ∪ { v+, v−}, và E ⊆ V×V. Với mỗi cạnh e ∈ E có trọng số w(e). Gọi các đỉnh v+, v− là các đỉnh phân lớp (Classication vertices) và tất cả các đỉnh khác gọi là các đỉnh mẫu (Example vertices). Bƣớc 2. Các đỉnh phân lớp có nhãn giống nhau đƣợc nối với nhau bởi các cạnh có trọng số ∞. Ví dụ, w(v, v+)=∞ với tất cả các đỉnh v ∈ L+ và w(v, v−)=∞ với tất cả các đỉnh v ∈ L− Bƣớc 3. Các cạnh nối giữa Các Đỉnh mẫu đƣợc gán trọng số dựa trên mối quan hệ giữa các mẫu dữ liệu đó, ví dụ nhƣ sự giống nhau hoặc khoảng cách giữa chúng. Việc lựa chọn cụ thể các trọng số cạnh này sẽ đƣợc đề cập ở phần sau. Hàm gán trọng số cho các cạnh đƣợc kết nối bởi Các đỉnh dữ liệu sẽ đƣợc gọi là Hàm gán trọng số w. Bƣớc 4. Bây giờ ta xác định một lát cắt nhỏ nhất (v+, v−) cho đồ thị; đó là, phải tìm ra tổng trọng số nhỏ nhất của các cạnh mà nếu loại bỏ chúng đi thì sẽ làm mất kết nối giữa các đỉnh v+ và v−. Điều này có thể tìm đƣợc bằng cách sử dụng thuật toán Số hóa bởi Trung tâm Học liệu – ĐHTN Luồng cực đại mà trong đó các đỉnh v+ là các đỉnh đầu, v− là các đỉnh đƣợc ẩn đi và các trọng số cạnh đƣợc xem nhƣ capacities. Việc loại bỏ các cạnh theo lát cắt sẽ chia đồ thị thành hai tập đỉnh đƣợc gọi là V+ và V−, với v+ ∈ V+ và v− ∈ V−. Nếu có nhiều lát cắt, ta có thể đặt cho thuật toán chọn một tập đỉnh V+ là nhỏ nhất. Bƣớc 5. Ta gán nhãn dƣơng (+) cho tất cả các mẫu dữ liệu chƣa có nhãn trong tập V+ và gán nhãn âm (−) cho tất cả các mẫu dữ liệu chƣa có nhãn trong tập V−. Trong thuật toán này, nếu các cạnh nối giữa các điểm dữ liệu có trọng số cao tƣơng tự nhau thì hai điểm dữ liệu tƣơng tự nhau sẽ đƣợc đặt trong cùng một tập đỉnh thu đƣợc từ lát cắt nhỏ nhất. Điều này phù hợp với giả thiết cơ bản của nhiều thuật toán học (giống nhƣ láng giềng gần nhất) rằng các điểm dữ liệu tƣơng tự nhau thì có khuynh hƣớng đƣợc phân lớp giống nhau. Nhƣ vậy, thực tế đặt ra là chúng ta có thể đánh trọng số các cạnh nhƣ thế nào? Nếu chúng ta có một khái niệm gọi là “khoảng cách” giữa các điểm dữ liệu thì các mẫu dữ liệu này sẽ có nhãn giống nhau, sau đó hàm tính khoảng cách sẽ đặt các cạnh nối các điểm dữ liệu gần nhau một trọng số cao và các cạnh có nối giữa các điểm dữ liệu xa nhau (hoặc không có cạnh nối) một trọng số thấp. Nếu chúng ta không khởi tạo ban đầu một hàm tính khoảng cách thì chúng ta có thể giữ các điểm dữ liệu đã gán nhãn trong một số thuật toán học trợ giúp để học một hàm khoảng cách. Ví dụ, chúng ta có thể sử dụng các dữ liệu đã gán nhãn để đánh trọng số cho các thuộc tính dựa trên các thông tin có đƣợc. Ta cũng có thể đánh trọng số cho một cạnh (x, y) với x ∈ U dựa trên y ∈ L hoặc không. Việc lựa chọn hàm đánh trọng số cạnh có thể ảnh hƣởng đến chất lƣợng đầu ra của thuật toán. 2.6. Các trƣờng Gaussian ngẫu nhiên và các hàm điều hòa 2.6.1. Các trƣờng Gaussian ngẫu nhiên Một cách tiếp cận khác của học nửa giám sát là đề xuất dựa trên mô hình Gaussian ngẫu nhiên (GRF). Dữ liệu đã gán nhãn và chƣa gán nhãn đƣợc đƣa ra nhƣ là các đỉnh trong một đồ thị có trọng số, với việc mã hóa trọng số các cạnh giữa các mẫu dữ liệu giống nhau. Bài toán học sau đó đƣợc xây dựng trong các trƣờng Gaussian ngẫu nhiên trên đồ thị này, tại đó ý nghĩa của các trƣờng đƣợc đặc trƣng Số hóa bởi Trung tâm Học liệu – ĐHTN bởi các hàm điều hòa và hiệu quả thu đƣợc bằng cách sử dụng các phƣơng pháp ma trận hay lan truyền tin cậy. Không giống nhƣ các phƣơng pháp khác hiện nay, dựa trên hàm năng lƣợng cực tiểu và các trƣờng ngẫu nhiên trong học máy, ta xem xét các trƣờng Gaussian ngẫu nhiên trên không gian trạng thái liên tục thay vì các trƣờng ngẫu nhiên trên các tập dữ liệu rời rạc. Đặc biệt, dạng phổ biến nhất của các trƣờng (field) có thể xảy ra là duy nhất, đƣợc đặc trƣng bởi các hàm điều hòa và có thể tính toán dựa vào các phƣơng pháp ma trận hay lan truyền. Ngƣợc lại, với các trƣờng ngẫu nhiên đa nhãn, việc tính toán cấu hình năng lƣợng thấp nhất thƣờng là NP-khó và các thuật toán xấp xỉ hay ƣớc lƣợng đƣợc sử dụng. Kết quả của thuật toán phân lớp với các trƣờng Gaussian có thể đƣợc xem nhƣ một dạng của phƣơng pháp tiếp cận láng giềng gần nhất, tại đó các mẫu dữ liệu láng giềng đã đƣợc gán nhãn bởi phƣơng pháp Bƣớc di chuyển trên đồ thị. Ta giả sử có ℓ điểm đã đƣợc gán nhãn (x1, y1),..., (xℓ, yℓ) và u điểm chƣa gán nhãn xℓ+1, ..., xℓ+u; ℓ<<u. Cho n=ℓ+u là tổng số các điểm dữ liệu. Để bắt đầu, ta giả sử các nhãn mang giá trị nhị phân: y ∈ {0, 1}. Xét một đồ thị liên thông G=(V, E) với tập các đỉnh V tƣơng ứng với n điểm dữ liệu, với tập L các đỉnh ứng với các điểm dữ liệu đã gán nhãn, với các nhãn y1,..., yℓ và tập U các đỉnh tƣơng ứng với các điểm dữ liệu chƣa đƣợc gán nhãn. Nhiệm vụ của chúng ta là dự đoán các nhãn cho các điểm dữ liệu trong tập U. Ta giả sử một ma trận trọng số đối xứng Wn×n trên các cạnh của đồ thị đƣợc đƣa ra. Ví dụ khi x ∈ ℝm thì ma trận trọng số đƣợc biểu diễn theo công thức sau: Trong đó, xid là thành phần thứ d của mẫu dữ liệu xi biểu diễn nhƣ một véc tơ m xi ∈ ℝ và σ1, ..., σm là siêu tham số cho mỗi chiều. Chiến lƣợc của chúng ta đầu tiên là tính toán một hàm giá trị thực f: VR trên đồ thị G với các thuộc tính nhất định và sau đó gán các nhãn dựa trên f. Chúng Số hóa bởi Trung tâm Học liệu – ĐHTN ta hạn chế f để f(i) = fl(i) ≡ yi trên dữ liệu đã gán nhãn i=1, ..., ℓ. Bằng trực giác chúng ta muốn các điểm dữ liệu chƣa gán nhãn gần nhau trong đồ thị sẽ có nhãn tƣơng tự nhau. Điều này dẫn tới sự lựa chọn hàm bậc 2: Rõ ràng, E đƣợc cực tiểu hóa bởi hàm không đổi. Nhƣng vì ta đã có một số dữ liệu đã gán nhãn, chúng ta gán cho f một giá trị f(i) = yi, (i ∈ L trên tập dữ liệu đã gán nhãn). Ta chỉ định một phân bổ xác suất tới hàm f bởi một trƣờng Gausian ngẫu nhiên (GRF). Trong đó β là một tham số “nghịch đảo” và Z là một hàm phân hoạch. đƣợc chuẩn hóa trên các hàm ràng buộc với YL trên dữ liệu đã gán nhãn. Ta đang quan tâm đến vấn đề suy luận p(fi|YL), i ∈ U hay nghĩa là Sự phân bố p(f) giống các trƣờng Markov ngẫu nhiên với các trạng thái rời rạc. Thực tế thì sự khác biệt duy nhất là trạng thái giá trị số thực. Tuy nhiên, điều này làm cho vấn đề suy luận đơn giản hơn rất nhiều. Bởi vì hàm năng lƣợng bậc 2 p(f) và p(fU|YU) đều là phân phối Gaussian đa biến. Do đó p đƣợc gọi là GRF. Biên p(fi|YL) là một biến đơn Gaussian và gần với giải pháp đƣa ra. 2.6.2. Đồ thị Laplacian Bây giờ ta xem xét tổ hợp Laplat, ký hiệu: Δ Cho D là ma trận đƣờng chéo bậc của các đỉnh, có Dii = ΣjWij là bậc của đỉnh i. Laplat đƣợc định nghĩa nhƣ sau: Δ ≡ D – W. Laplat là viết tắt cho hàm năng lƣợng: Số hóa bởi Trung tâm Học liệu – ĐHTN Hàm Gaussian ngẫu nhiên có thể đƣợc viết nhƣ sau: 2.6.3. Các hàm điều hòa Không khó để chỉ ra rằng hàm năng lƣợng cực tiểu là hàm điều hòa, cụ thể là Δf = 0 trên các điểm dữ liệu chƣa gán nhãn trong tập U, và bằng Δf =YL trên các điểm dữ liệu đã gán nhãn L. Ký hiệu hàm điều hòa là: Thuộc tính điều hòa ở đây có nghĩa là giá trị của (i) tại mỗi điểm dữ liệu chƣa gán nhãn i là giá trị trung bình của các láng giềng của nó trong đồ thị, ta có công thức sau: Do các nguyên lý cực đại của hàm điều hòa (Doyle & Snell, 1984), thỏa mãn 0 ≤ (i) ≤1 với i ∈ U (lƣu ý: (i)=0 hoặc (i)=1 cho mỗi i ∈L). Để tính toán giải pháp điều hòa, ta chia nhỏ ma trận W (tƣơng tự D, Δ, ...) thành 4 khối cho L và U: Giải pháp điều hòa Δh=0 với hL = YL đƣợc đƣa ra bởi −1 Mô tả cuối cùng giống với công thức fU = ( I−PUU) PULYL, mà P=D/W là ma trận lan truyền trong đồ thị. Thuật toán lan truyền nhãn (labled propagation) thực tế đã tính hàm điều hòa này. Hàm điều hòa đã cực tiểu hóa năng lƣợng và do đó nó là một dạng của Trƣờng Gaussian ngẫu nhiên. Số hóa bởi Trung tâm Học liệu – ĐHTN Hàm điều hòa có thể đƣợc thể hiện trong một vài cách nhìn khác nhau và những cách nhìn khác nhau này cung cấp một tập hợp các lý luận bổ sung và kỹ thuật phong phú cho lĩnh vực học nửa giám sát. 2.7. Đánh giá Hầu hết các thuật toán học nửa giám sát dựa trên đồ thị đều dựa trên việc học lan truyền, một nhƣợc điểm của phƣơng pháp này là chúng ta không thể dễ dàng mở rộng thêm các điểm dữ liệu mới mà không thuộc tập L∪ U, hoặc nếu các điểm dữ liệu mới đƣợc thêm vào đồ thị thì sẽ làm thay đổi cấu trúc của đồ thị, dẫn tới chi phí tính toán bị tăng lên. Bên cạnh đó, một lý do nữa có ảnh hƣởng tới chi phí tính toán đó là phụ thuộc vào loại đồ thị sẽ xây dựng, nếu sử dụng đồ thị kết nối đầy đủ thì ta phải tính toán cho tất cả các cạnh nối giữa hai đỉnh bất kỳ. 2.8. Kết luận chƣơng Trong chƣơng này, chúng ta đã tìm hiểu về phƣơng pháp học nửa giám sát dựa trên đồ thị và một số thuật toán sử dụng để phục vụ quá trình học. Nghiên cứu thuật toán lan truyền nhãn để học từ cả dữ liệu đã gán nhãn và chƣa gán nhãn, các nhãn đƣợc lan truyền trong đồ thị thông qua hàm trọng số và các đỉnh lân cận đã gán nhãn. Đây là thuật toán khá quan trọng với học máy trên đồ thị. Chúng ta cũng nghiên cứu cách xác định các siêu tham số để phục vụ trong quá trình lan truyền nhãn với thuật toán Cây khung nhỏ nhất. Vì các đồ thị là đầu vào của tất cả các thuật toán nên chúng ta cần xây dựng đồ thị sao cho phù hợp nhất với yêu cầu của bài toán. Số hóa bởi Trung tâm Học liệu – ĐHTN CHƢƠNG 3: CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN 3.1. Mô tả bài toán Với mục tiêu gán nhãn cho các đỉnh trên đồ thị dựa trên cơ sở các đỉnh đã có nhãn tiến hành xây dựng một chƣơng trình ứng dụng nhằm mô phỏng quá trình thực hiện của thuật toán. Chƣơng trình ứng dụng sẽ cài đặt hai thuật toán học nửa giám sát theo hai phƣơng pháp là phƣơng pháp tự huấn luyện với sự kết hợp của các dữ liệu đã gán nhãn, chƣa gán nhãn và phƣơng pháp dựa trên đồ thị để thực hiện việc phân loại các tin nhắn rác có trong một tập các tin nhắn thông thƣờng. 3.2. Mô tả dữ liệu đầu vào Dữ liệu đầu vào của chƣơng trình đƣợc lấy ngẫu nhiên với 50 tin nhắn trong đó có 8 tin nhắn rác trong bộ dữ liệu thử nghiệm SMS Spam corpus (nguồn Mỗi dòng dữ liệu sẽ chứa nội dung một tin nhắn dƣới dạng text. Kết thúc mỗi dòng sẽ là dấu phân cách “phẩy”, sau dấu phẩy này tin nhắn sẽ đƣợc phân loại thành ham-tin nhắn hợp lệ và spam-tin nhắn rác. Ví dụ về nội dung của bộ dữ liệu: Hình 3.1: Tệp dữ liệu tin nhắn mẫu Số hóa bởi Trung tâm Học liệu – ĐHTN Trƣớc khi tiến hành phân lớp dữ liệu, cần phải xử lý để chuyển đổi dữ liệu về định dạng phù hợp. Luận văn sử dụng phần mềm Weka (nguồn để thực hiện các thao tác tiền xử lý dữ liệu. Chi tiết các bƣớc xử lý nhƣ sau: Bƣớc 1: Chuyển đổi dữ liệu dạng chuỗi về dạng vector: weka sẽ xây dựng bộ từ điển về các từ khóa. Sau khi chuyển đổi, bộ dữ liệu dùng để chuyển đổi ở đây bao gồm 148 bản ghi và 100 thuộc tính. Hình 3.2 chỉ rõ dữ liệu sau khi đã đƣợc chuyển đổi. Hình 3.2: Nội dung tin nhắn được chuyển thành dạng vector Khi đó dữ liệu dạng vector đƣợc mô tả nhƣ trong hình sau. Các thuộc tính là các từ trong nội dung tin nhắn, mỗi thuộc tính là 1 cột dữ liệu. Mỗi tin nhắn đƣợc thể hiện trên một hàng với các số 0,1 thể hiện số lần xuất hiện thuộc tính (từ tiếng anh) trong nội dung của tin nhắn nhƣ hình 3.3. Khi đó ta vẫn có thể chỉnh sửa đƣợc nội dung file nếu cần. Số hóa bởi Trung tâm Học liệu – ĐHTN Hình 3.3: Nội dung file dữ liệu dạng vector Bƣớc 2: Trích chọn đặc trƣng đƣợc trình bày chi tiết trong mục 3.3. Bƣớc 3: Thực hiện gán số thứ tự cho các đỉnh với mỗi đỉnh là một SMS đƣợc thể hiện trên một dòng dữ liệu và gán nhãn trƣớc cho một số đỉnh còn một số đỉnh thì chƣa gán nhãn. Bằng cách thêm một số nhãn 1,0 (thể hiện là nhãn) hay -1 (chƣa gán nhãn) trƣớc phần dữ liệu của tin nhắn. Bƣớc này đƣợc thực hiện trong chƣơng trình nhằm chuẩn hóa dữ liệu đầu vào cho phù hợp với dữ liệu đầu vào của thuật toán. 3.3. Trích chọn đặc trƣng Trích chọn đặc trƣng (Feature Selection, Feature Extraction) là nhiệm vụ rất quan trọng giai đoạn tiền xử lý dữ liệu khi triển khai các mô hình khai phá dữ liệu hoặc máy học. Một vấn đề gặp phải là các bộ dữ liệu dùng để xây dựng mô hình dữ liệu thƣờng chứa nhiều thông tin không cần thiết (thậm chí gây nhiễu) cho việc xây dựng mô hình. Chẳng hạn, một bộ dữ liệu gồm hàng trăm thuộc tính dùng để mô tả về khách hàng của một doanh nghiệp đƣợc thu thập, tuy nhiên khi xây dựng một mô Số hóa bởi Trung tâm Học liệu – ĐHTN hình nào đó chỉ cần khoảng 50 thuộc tính từ hàng trăm thuộc tính đó. Nếu ta sử dụng tất cả các thuộc tính (hàng trăm) của khách hàng để xây dựng mô hình thì ta cần nhiều CPU, nhiều bộ nhớ trong quá trình huấn luyện, thậm chí các thuộc tính không cần thiết đó làm giảm độ chính xác của mô hình và gây khó khăn trong việc phát hiện tri thức. Có nhiều phƣơng pháp để trích chọn ra các thuộc tính tốt để huấn luyện mà vẫn đảm bảo đƣợc yêu cầu, giúp quá trình thực thi huấn luyện nhanh hơn. Trong trích chọn đặc trƣng văn bản, các phƣơng pháp có thể kể đến nhƣ Bag-of-words hay Chỉ số Gain, luận văn sử dụng phƣơng pháp trích chọn dựa trên bag-of-words với kỹ thuật loại bỏ từ dừng “stop word” và lấy từ gốc “stemming”. Sau khi các đặc trƣng phù hợp đƣợc chọn, bộ phân lớp đƣợc đào tạo với tập dữ liệu huấn luyện. Quá trình huấn luyện thƣờng đƣợc lặp đi lặp lại nhiều lần để có đƣợc một mô hình tốt nhất. Hiệu năng của mô hình phân loại sau đó đƣợc đánh giá bởi tập dữ liệu kiểm tra đã chuẩn bị riêng. Trong luận văn này Wake 3 đƣợc sử dụng để chọn ra các đặc trƣng tốt bằng cách sử dụng tính năng Attribute Selection với tùy chọn Best First để lọc bỏ các tính năng không thực sự quan trọng từ đó giảm số thuộc tính cần xét giúp chƣơng trình thuật toán thực hiện đƣợc nhanh hơn mà vẫn đảm bảo một số tiêu chí dùng cho phân lớp nhƣ hình sau. Hình 3.4: Trích chọn đặc trưng Số hóa bởi Trung tâm Học liệu – ĐHTN Từ đó ta đƣợc file đầu vào cho bài toán tự huấn luyện và lan truyền nhãn với 30 thuộc tính cơ bản nhƣ hình 3.5. Dữ liệu đầu vào có thể xem và sửa nếu cần thiết nhƣ hình 3.5 nhƣ sau: Hình 3.5: Trích chọn thuộc tính cho file đầu vào của chương trình Hình 3.6: Dữ liệu của chương trình Số hóa bởi Trung tâm Học liệu – ĐHTN Dữ liệu đầu vào của thuật toán là tập các bản ghi dữ liệu chƣa đƣợc phân lớp. Với mỗi bản ghi dữ liệu sẽ chứa giá trị của các thuộc miền rời rạc. Hình 3.7: Dữ liệu của chương trình mở bằng Notepad Cấu trúc dữ liệu của tệp đầu vào có thể mô tả lại nhƣ sau: Đầu tiên là các thông tin về Wake 3 Tiếp theo là n dòng thông tin các thuộc tính có dạng @ thuộc tính với n là số thuộc tính. Mỗi dòng tƣơng ứng với giá trị của một đối tƣợng trong luận văn thì mỗi dòng thể hiện dữ liệu các thuộc tính của 1 sms. Các giá trị của mỗi thuộc tính cách nhau bởi một dấu “,” 3.4. Cài đặt và thử nghiệm Môi trƣờng cài đặt và thử nghiệm Chƣơng trình thử nghiệm đƣợc viết bằng ngôn ngữ C#.Net trên bộ Visual Studio 2010 sử dụng phiên bản .Net Framework 4.0. Dữ liệu của chƣơng trình đƣợc lƣu trữ trong hệ quản trị cơ sở dữ liệu Sql Server 2008 R2. Số hóa bởi Trung tâm Học liệu – ĐHTN Các chức năng của chƣơng trình Nhập dữ liệu: Cho phép nhập dữ liệu từ tệp text có cấu trúc nhƣ trong mô tả ở mục 3.6. Trƣớc khi nhập liệu, ngƣời dùng có thể chỉnh sửa trên phần mềm Wake 3. Để nhập dữ liệu, ngƣời dùng nhấn vào nút “Chọn...”, sau đó tìm đến tệp dữ liệu lƣu trữ trên máy tính có đuôi dạng *.arff hoặc *.text. Sau khi chọn tệp, dữ liệu sẽ đƣợc lấy thông tin cần thiết về các thuộc tính và thực hiện lƣu vào cơ sở dữ