Luận văn Thạc sĩ Khoa học máy tính: Phân loại thư rác bằng phương pháp học máy

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:67

Thêm vào BST

Báo xấu

35
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài nghiên cứu “Phân loại thư rác bằng phương pháp học máy” với mục đích tìm hiểu, thử nghiệm một số phương pháp tiếp cận cho bài toán phân loại thư, từ đó ngăn chặn thư spam hiệu quả hơn. Để hiểu rõ hơn mời các bạn cùng tham khảo nội dung chi tiết của luận văn này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Phân loại thư rác bằng phương pháp học máy

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG -------o0o------- PHẠM THỊ KIM DUNG PHÂN LOẠI THƯ RÁC BẰNG PHƯƠNG PHÁP HỌC MÁY LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái nguyên, 2015
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG -------o0o------- PHẠM THỊ KIM DUNG PHÂN LOẠI THƯ RÁC BẰNG PHƯƠNG PHÁP HỌC MÁY Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS ĐỖ TRUNG TUẤN Thái nguyên, 2015
ii MỤC LỤC MỤC LỤC ....................................................................................................................... ii LỜI CAM KẾT .............................................................................................................. iv LỜI CẢM ƠN ................................................................................................................. v DANH MỤC CÁC TỪ VIẾT TẮT ............................................................................... vi DANH MỤC HÌNH VẼ VÀ BẢNG BIỂU .................................................................. vii MỞ ĐẦU ....................................................................................................................... vii CHƯƠNG 1.TỔNG QUAN VỀ HỌC MÁY VÀ THƯ RÁC ........................................ 3 1.1. Tổng quan về ho ̣c máy ......................................................................................... 3 1.1.1 Trí tuê ̣ nhân tạo .............................................................................................. 3 1.1.2. Học máy ........................................................................................................ 4 1.1.3. Các kĩ thuật học máy ..................................................................................... 5 1.1.4. Một số ứng dụng của học máy ...................................................................... 7 1.1.5. Học có giám sát ............................................................................................. 7 1.2. Tổng quan về thư rác.......................................................................................... 12 1.2.1. Định nghĩa về thư rác và các đặc trưng của thư rác .................................... 12 1.2.2. Phân loại thư rác.......................................................................................... 15 1.2.3. Đặc điểm thư rác ......................................................................................... 15 1.2.4. Tác hại của thư rác ...................................................................................... 16 1.2.5. Quy trình và thủ đoạn gửi thư rác ............................................................ 17 1.3. Biểu diễn phân loại thư rác dựa trên học máy có giám sát ................................ 20 1.3.1. Nhu cầu phân loại thư rác ........................................................................... 20 1.3.2. Cách biểu diễn nội dung thư rác ................................................................. 23 1.4. Kết luận chương ................................................................................................. 27 CHƯƠNG 2. PHÂN LOẠI THƯ RÁC BẰNG MỘT SỐ THUẬT TOÁN HỌC MÁY CÓ GIÁM SÁT ................................................................................................... 28 2.1. Thuật toán Naïve Bayes ..................................................................................... 28 2.1.1.Giới thiệu Thuật toán Naïve Bayes .............................................................. 28 2.1.2. Mô tả thuật toán .......................................................................................... 28 2.1.3. Áp dụng trong phân loại thư rác ................................................................. 33
iii 2.2. Học máy theo phương pháp máy vec tơ tựa SVM ............................................. 36 2.2.1. Giới thiệu SVM ........................................................................................... 36 2.2.2. Mô tả thuật toán .......................................................................................... 37 2.2.2. Huấn luyện SVM......................................................................................... 40 2.2.3. Ứng dụng trong phân loại thư rác ............................................................... 40 2.3. Xây dựng mô hình lọc thư rác dựa trên học máy có giám sát ........................... 41 2.3.1. Lựa chọn mô hình và thuật toán .................................................................. 41 2.3.2. Xây dựng hệ thống ...................................................................................... 41 2.4. Kết luận chương ................................................................................................. 46 CHƯƠNG 3.CÀI ĐẶT THỬ NGHỆM VIỆC PHÂN LOẠI THƯ RÁC..................... 47 3.1. Bài toán phân loại thư rác .................................................................................. 47 3.2. Cài đặt thử nghiệm và kết quả............................................................................ 50 3.2.1. Bộ dữ liệu thử nghiệm................................................................................. 50 3.2.2. Môi trường cài đặt ....................................................................................... 52 3.2.3. Giao diện của chương trình thử nghiệm...................................................... 52 3.2.4. Kết quả thử nghiệm ..................................................................................... 54 3.3. Đánh giá thử nghiệm .......................................................................................... 55 3.4. Kết luận chương ................................................................................................. 56 KẾT LUẬN ................................................................................................................... 57 Các kết quả đạt được ............................................................................................. 57 Hướng phát triển luận văn ..................................................................................... 57 DANH MỤC TÀI LIỆU THAM KHẢO ...................................................................... 58
iv LỜI CAM KẾT Dưới sự giúp đỡ nhiệt tình và chỉ bảo chi tiết của giáo viên hướng dẫn, tôi đã hoàn thành luận văn của mình. Tôi xin cam kết luận văn này là của bản thân tôi làm và nghiên cứu, không hề trùng hay sao chép của bất kỳ ai. Tài liệu được sử dụng trong luận văn được thu thập từ các nguồn kiến thức hợp pháp. Tác giả luận văn Phạm Thị Kim Dung
v LỜI CẢM ƠN Để hoàn thành chương trình cao học và viết luận văn này, em đã nhận được sự giúp đỡ và đóng góp nhiệt tình của các thầy cô trường Đại học Công nghệ thông tin và Truyền thông, Đại học Thái Nguyên. Trước hết, em xin chân thành cảm ơn các thầy cô trong khoa Đào tạo sau đại học, đã tận tình giảng dạy, trang bị cho em những kiến thức quý báu trong suốt những năm học qua. Xin chân thành cảm ơn gia đình, bạn bè đã nhiệt tình ủng hộ, giúp đỡ, động viên cả về vật chất lẫn tinh thần trong thời gian học tập và nghiên cứu. Trong quá trình thực hiện luận văn, mặc dù đã rất cố gắng nhưng cũng không tránh khỏi những thiếu sót. Kính mong nhận được sự cảm thông và tận tình chỉ bảo của các thầy cô và các bạn.
vi DANH MỤC CÁC TỪ VIẾT TẮT AI Trí tuệ nhân tạo Clustering Phân cụm Computer Vision Nhìn máy ESP Email Service Provider HAM Thư điện tử không là thứ rác ISP Internet Service Provider, nhà cung cấp dịch vụ Internet KNN K người láng giềng gần nhất MI Mutual information, thông tin tương hỗ NB Phương pháp Naïve Bayes Regression Hồi qui Search Engine Máy tìm kiếm Server Máy chủ, phía máy chủ SMO Sequential Minimal Optimization SMS Short Message Service Spam Email Thư rác SQL Structured Query Language Stemming Gốc (của từ) SVM Support Vector Machine, máy vec tơ tựa TTNT Trí tuệ nhân tạo UBE Unsolicited Bulk Email, thư không lành mạnh UCE Unsolicited Commercial Email, thư không yêu cầu đến VC Kích thước Vapnik- Chervonenkis XML eXtensible Markup Language
vii DANH MỤC HÌNH VẼ VÀ BẢNG BIỂU HÌNH Hình 1.1: Cấu trúc một hệ thống học máy tiêu biểu cho trường hợp phân loại ...... 6 Hình 1.2. Mô hình thuật toán học có giám sát......................................................... 8 Hình 1.3. Ví dụ về trang web lấy cắp địa chỉ thư của người dùng ........................ 17 Hình 1.4. Một số website của các công ty gửi thư rác ......................................... 18 Hình 1.5. Minh họa cách gửi thư rác qua máy chủ thư (open relay) ..................... 19 Hình 1.6. Số lượng thư rác từ tháng 4 đến tháng 9 năm 2014 .............................. 21 Hình 1.7. Danh sách các quốc gia phát tán thư rác trong quí 3/2014 của Kaspersky Lab ....................................................................................... 23 Hình 2.1. Ánh xạ dữ liệu từ không gian gốc sang không gian đặc trưng cho phép phân chia dữ liệu bởi siêu phẳng ........................................................... 38 Hình 2.2. Siêu phẳng với lề cực đại cho phép phân chia các hình vuông khỏi các hình tròn trong không gian đặc trưng .................................................... 38 Hình 2.3. Tiền xử lý dữ liệu .................................................................................. 42 Hình 2.4. Huấn luyện dữ liệu ................................................................................ 46 Hình 3.1: Mô hình phân loại thư rác bằng 2 thuật toán Bayse và SVM ............... 48 Hình 3.2. Tập các File trong HAM........................................................................ 51 Hình 3.3. Tập các File trong SPAM ...................................................................... 51 Hình 3.4. Giao diện chương trình chính phân loại thư rác bằng Bayes và SVM .. 52 Hình 3.5. Giao diện xử lý dữ liệu bước huấn luyện .............................................. 53 Hình 3.6. Giao diện kết quả của thử nghiệm ......................................................... 53 Hình 3.7. Độ chính xác phân loại của NB và SVM .............................................. 54 BẢNG Bảng 1.1. Ví dụ nội dung của bốn thư ...................................................................... 24 Bảng 1.2. Biểu diễn vec tơ cho dữ liệu trong bảng 1.1 ............................................ 24 Bảng 2.1: Bộ dữ liệu huấn luyện cho bài toán phân loại “Chơi Tennis” ................. 31 Bảng 3.1: Độ chính xác phân loại hai phương pháp phân loại khác nhau ............... 54
1 MỞ ĐẦU Ngày nay, Internet mở ra nhiều kênh liên lạc, nhiều dịch vụ mới cho người sử dụng, một trong những dịch vụ mà Internet mang lại là dịch vụ thư điện tử (Email), đó là phương tiện giao tiếp rất đơn giản, tiện lợi và hiệu quả đối với cộng đồng người sử dụng dịch vụ này. Chính vì những lợi ích do thư mang lại nên số lượng thư trao đổi trên Internet ngày càng tăng, và một số không nhỏ trong đó là thư rác (Spam). Trong những năm gần đây, spam hay các thư không mong muốn đã trở thành một vấn nạn và đe dọa khả năng giao tiếp của con người trên kênh liên lạc này, đó là một trong những thách thức lớn mà khách hàng và các nhà cung cấp dịch vụ phải đối phó. Spam đã trở thành một hình thức quảng cáo chuyên nghiệp, phát tán virus, ăn cắp thông tin với nhiều thủ đoạn và mánh khóe cực kỳ tinh vi. Người dùng sẽ phải mất khá nhiều thời gian để xóa những thư “không mời mà đến”, nếu vô ý còn có thể bị nhiễm virus và nặng nề hơn là mất thông tin như thẻ tín dụng, tài khoản ngân hàng qua các thư dạng phishing.... Theo báo cáo tình hình thư rác do Kaspersky Lab vừa công bố, tỷ lệ thư rác trong lưu lượng truy cập thư của quý 3/2014 tăng 1,7 % so với quý trước, đạt trung bình 66,9%. Ba nguồn phát tán thư rác hàng đầu gồm có Mỹ (14%) và Nga (6,1%) và Việt Nam đứng vị trí thứ 3 với 6%. Để ngăn chặn spam, nhiều tổ chức, cá nhân đã nghiên cứu và phát triển những kỹ thuật phân loại thư thành các nhóm; từ đó xác định, nhận biết giữa thư rác và thư có giá trị. Tuy nhiên, những người tạo nên thư rác luôn tìm mọi cách vượt qua các bộ phân loại này và phát tán chúng. Vì vậy, cần có một hệ thống phân loại đâu là spam mail và đâu là mail tốt. Xuất phát từ thực trạng đó, tôi chọn hướng nghiên cứu “Phân loại thư rác bằng phương pháp học máy” với mục đích tìm hiểu, thử nghiệm một số phương pháp tiếp cận cho bài toán phân loại thư, từ đó ngăn chặn thư spam hiệu quả hơn. Nội dung của luận văn được trình bày theo 3 chương. Tổ chức cấu trúc như sau:
2 1. Chương 1 Tổng quan về học máy và thư rác: Chương này giới thiệu tổng quát về học máy và thư rác bao gồm khái niệm, ứng dụng và phần trình bày chi tiết về học máy có giám sát, các kỹ thuật của học máy có giám sát dùng cho phân loại như Naïve Bayes, SVM, cây quyết định,… Chương cũng giới thiệu khái quát về thư rác, các đặc trưng của thư rác và biểu diễn thư rác dựa trên học máy có giám sát; 2. Chương 2 Phân loại thư rác bằng một số thuật toán có giám sát: Nội dung chính trong chương này là đi sâu nghiên cứu hai thuật toán học máy có giám sát là Naïve Bayes và phương pháp SVM (Support Vector Machine). 3. Chương 3 Cài đặt, thử nghiệm và đánh giá thuật toán: Phần đầu chương giới thiệu toán phân loại thư rác, bộ dữ liệu thử nghiệm và cài đặt chi tiết hai thuật toán đề cập ở chương 2. Phần cuối của chương trình bày kết quả thu được và đưa ra đánh giá về hai thuật toán được sử dụng trong bài toán lọc thư rác. Cuối luận văn là phần kết luận và danh sách các tài liệu tham khảo. Phần thực nghiệm về phân loại thư rác được trình bày thêm trong phần phụ lục luận văn.
3 CHƯƠNG 1 TỔNG QUAN VỀ HỌC MÁY VÀ THƯ RÁC 1.1. Tổng quan về ho ̣c máy 1.1.1 Trí tuê ̣ nhân tạo Trước đây, mỗi khi nói đến Trí tuệ nhân tạo (TTNT) người ta thường quan tâm đến việc tạo lập các máy tính có khả năng “suy nghĩ”, thậm chí trong một số phạm vi hẹp nào đó, có thể cạnh tranh hoặc vượt quá khả năng của bộ não con người. Những hy vọng này trong một thời gian dài đã ảnh hưởng rất nhiều đến các nghiên cứu trong phòng thí nghiệm. Mặc dù những mô hình tương tự các máy tính thông minh đã được đưa ra hàng nhiều năm trước, nhưng chỉ từ khi Alan Turing công bố những kết quả nghiên cứu quan trọng đầu tiên, người ta mới bắt đầu thực sự nghiên cứu đến các vấn đề TTNT một cách nghiêm túc. Phát hiện của Turing cho rằng chương trình có thể được lưu trữ trong bộ nhớ để sau đó được thực hiện trên cơ sở các phép toán cơ bản thao tác với các bit 0, 1. Điều này đã tạo nên nền tảng của những máy tính hiện đại. Việc lưu trữ chương trình trong máy cho phép thay đổi chức năng của nó một cách nhanh chóng và dễ dàng thông qua việc nạp một chương trình mới vào bộ nhớ. Theo một nghĩa nào đó, khả năng này làm cho máy tính có khả năng học và suy nghĩ. Đó cũng chính là một trong những biểu hiện quan trọng đầu tiên của những máy tính được trang bị TTNT. Trí tuệ nhân tạo (AI) là lĩnh vực khoa học chuyên nghiên cứu các phương pháp chế tạo trí tuệ máy sao cho giống như trí tuệ con người. [4] Vài định nghĩa của trí tuệ nhân tạo điển hình là:  Hệ thống mà biết suy nghĩ như con người  Hệ thống mà biết hành động như con người Để hệ thống mà biết suy nghĩ và hành động như con người thì hệ thống đó phải được trang bị các công cụ như thính giác, tri thức, lý giải tự động, việc học, thị giác và di chuyển giống như con người. Thông thường, cách giải quyết vấn đề của con người được thể hiện qua bốn thao tác cơ bản đó là:
4 1. Xác định tập hợp của các đích 2. Thu thập các sự kiện và luật suy diễn 3. Cơ chế tập trung 4. Bộ máy suy diễn Như vậy, trí tuệ máy là các khả năng giải quyết vấn đề của máy, cần thỏa mãn: 1. Hành động giống như con người. 2. Suy nghĩ giống như con người. 3. Học giống như con người. 4. Xử lý thông tin giống như con người. 5. Hành động và suy nghĩ trên cơ sở logic và chính xác. Ứng dụng của trí tuệ nhân tạo có trong nhiều ngành kinh tế : 1. Điều khiển học, Robotic, giao diện người máy thông minh 2. Trò chơi máy tính 3. Thiết bị điện tử thông minh nhờ sử dụng lôgic mờ 4. Hệ chuyên gia trong: giáo dục, y khoa, địa chất, quản lý, ... 5. Xử lý ngôn ngữ tự nhiên 6. Nhận dạng hình ảnh, âm thanh 7. Các hệ thống xử lý tri thức và dữ liệu tích hợp: cho phép xử lý đồng thời tri thức và dữ liệu (cơ sở dữ liệu suy diễn, biểu diễn luật đối tượng, hệ hỗ trợ quyết định) 8. Mô hình hóa các giải pháp bài toán 1.1.2. Học máy Con người có nhiề u cách ho ̣c như ho ̣c ký ức, ho ̣c các sự kiê ̣n,.. thông qua sự quan sát và thăm dò, ho ̣c cải thiê ̣n kỹ xảo thông qua thực tiễn, ho ̣c qua sự phát triể n của hê ̣ thầ n kinh sinh ho ̣c con người, hoă ̣c ho ̣c qua gen di truyề n từ các thế hê ̣ trước.
5 Dù với cách ho ̣c nào đi nữa, mu ̣c tiêu của viê ̣c ho ̣c chính là thu thâ ̣p tri thức mới, sau đó xử lý tri thức này sao cho thić h nghi đươ ̣c với các tình huố ng, sự kiê ̣n mới. Giố ng với cách ho ̣c của đó, con người cũng muố n xây dựng các chương trình ho ̣c cho máy tính sao cho máy có khả năng thu thâ ̣p tri thức mới, từ đó xử lý tri thức để thích nghi đươ ̣c với các tiǹ h huố ng cu ̣ thể . Đó là lý do ta ̣i sao kỹ thuâ ̣t ho ̣c máy đang càng ngày càng trở thành mố i quan tâm lớn của ngành khoa ho ̣c máy tính hiện nay. Ho ̣c máy là một lĩnh vực của trí tuệ nhân ta ̣o liên quan đến việc phát triển các kĩ thuật cho phép các máy tính có thể "học". Ho ̣c máy được xem là phương pháp tạo ra các chương trình máy tin ́ h sử dụng kinh nghiê ̣m, quan sát hoă ̣c dữ liê ̣u trong quá khứ để cải thiê ̣n công viê ̣c của mình trong tương lai. Chẳ ng ha ̣n, máy tiń h có thể học cách dự đoán dựa trên các mẫu, các ví dụ, hay học cách tạo ra các hành vi phù hợp dựa trên quan sát trong quá khứ. Xét một ví dụ là học cách đánh cờ. Chương triǹ h có thể quan sát các ván cờ nhằ m cải thiê ̣n khả năng chơi cờ với mu ̣c đích tăng số ván thắ ng trong tương lai. Trong trường hợp này, kinh nghiê ̣m được sử du ̣ng để “ho ̣c” cách làm tốt hơn trong công viê ̣c chơi cờ với tiêu chí đánh giá là số ván thắ ng. 1.1.3. Các kĩ thuật học máy Việc sử dụng những da ̣ng kinh nghiê ̣m và dạng biể u diễn khác nhau sẽ dẫn tới những kĩ thuật học máy khác nhau. Tuy nhiên chủ yếu, ho ̣c máy đươ ̣c phân thành 3 loa ̣i chính: 1.1.3.1. Học có giám sát Với cách học này, kinh nghiệm đươ ̣c cho một cách tường minh dưới dạng đầu vào và đầu ra của hàm đích, ví du ̣ cho trước tâ ̣p các mẫu cùng nhañ phân loa ̣i tương ứng. Ho ̣c có giám sát bao gồ m phân loại và hồi quy; trong đó phân loa ̣i là dạng học có giám sát với hàm đích nhâ ̣n giá tri ̣ rời ra ̣c và hồ i quy là ho ̣c có giám sát với hàm đích nhận giá tri ̣ liên tu ̣c. Sơ đồ một hê ̣ thố ng ho ̣c máy điể n hin ̀ h trong trường hơ ̣p ho ̣c có giám sát (phân loa ̣i) được thể hiê ̣n như trên hiǹ h sau.
6 Thí dụ mới (chưa gán nhãn) Các thí dụ Các thu t Hàm đích Nhãn phân huấn luyện t án học máy l ại (có nhãn) Hình 1.1: Cấu trúc một hệ thống học máy tiêu biểu cho trường hợp phân loại 1.1.3.2. Học không có giám sát Ngươ ̣c với ho ̣c có giám sát, ho ̣c không giám sát là cách ho ̣c mà kinh nghiê ̣m chỉ gồ m các mẫu và không có nhañ hoă ̣c giá tri ̣ hàm đích đi kèm. Ví du ̣ chỉ bằ ng quan sát thông thường về cân nă ̣ng của mo ̣i người, dầ n dầ n ta ho ̣c đươ ̣c khái niê ̣m “người béo”, “người bình thường” và “người gầ y”. Hai dạng học không giám sát phổ biế n nhấ t là phân cu ̣m và ho ̣c luâ ̣t kế t hơ ̣p. Trong trường hơ ̣p phân cụm, các đố i tượng được phân chia thành mô ̣t số nhóm sao cho mỗi nhóm gồ m những đố i tươ ̣ng giố ng nhau và khác đố i tượng ở nhóm khác. Học luật kết hợp là cách phát hiê ̣n những đố i tươ ̣ng hoă ̣c giá tri ̣ thuô ̣c tiń h thường xuất hiện cùng nhau, ví du ̣ những mă ̣t hàng thường xuyên đươ ̣c mua cùng nhau (bánh mì và sữa). 1.1.3.3. Học nửa giám sát Học nửa giám sát là việc học có kết hợp các ví dụ có gắn nhãn và không gắn nhãn để sinh một hàm hoặc một bộ phân loại thích hợp. 1.1.3.4. Học tăng cường Đối với da ̣ng ho ̣c này, kinh nghiê ̣m không đươ ̣c cho trực tiế p dưới da ̣ng đầ u vào/ đầu ra. Thay vào đó, hê ̣ thống nhâ ̣n đươ ̣c một giá tri ̣tăng cường là kế t quả cho một chuỗi hành động nào đó. Thuâ ̣t toán cầ n ho ̣c cách hành đô ̣ng để cực đa ̣i hóa giá tri ̣ tăng cường. Ví du ̣ của ho ̣c tăng cường là ho ̣c đánh cờ, trong đó hệ thố ng không được chỉ dẫn nước đi nào là hơ ̣p lý cho từng tình huố ng mà chỉ biết kế t quả toàn ván cờ. Như vâ ̣y, các chỉ dẫn về nước đi đươ ̣c học một cách gián tiế p và có đô ̣ trễ dưới da ̣ng giá tri ̣thưởng.
7 1.1.4. Một số ứng dụng của học máy 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ồ. Cụ thể một số ứng dụng thường thấy như: 1. Xử lý ngôn ngữ tự nhiên: xử lý văn bản, giao tiếp người – máy, … 2. Nhận dạng : nhận dạng tiếng nói, chữ viết tay, vân tay, thị giác máy () … 3. Tìm kiếm 4. 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. 5. Lo ̣c thư rác, phân loa ̣i văn bản: Là dựa trên nô ̣i dung thư điê ̣n tử, chia thư thành loại “thư rác (thư không có giá tri)” ̣ hay “thư bình thường (thư có giá tri)”; ̣ hoă ̣c phân chia tin tức thành các thể loa ̣i khác nhau như “xã hô ̣i”, “kinh tế ”, “thể thao”,… 6. Tin sinh học: phân loại chuỗi gene, quá trình hình thành gene/protein 7. Vật lý: phân tích ảnh thiên văn, tác động giữa các hạt … 8. Phát hiện gian lận tài chính : gian lận thẻ tỉn dụng 9. Dự đoán chỉ số thị trường: Là căn cứ giá tri ̣ mô ̣t vài tham số hiê ̣n thời hoă ̣c trong quá khứ để đưa ra dự đoán, chẳ ng ha ̣n dự đoán giá chứng khoán, giá vàng,… Ngoài những ứng dụng có da ̣ng phân loại hoă ̣c hồ i quy mô ̣t cách tường minh ở trên, học máy có thể dùng trong rấ t nhiề u ứng du ̣ng đòi hỏi ra quyế t định hoă ̣c hành đô ̣ng một cách thông minh. 1.1.5. Học có giám sát 1.1.5.1. Việc học Học có giám sát là một kỹ thuật của ngành học máy để xây dựng một hàm từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp đối tượng đầu vào (thường dạng vec tơ) và đầu ra thực sự. Đầu ra của một hàm có thể là một giá trị liên tục
8 (gọi là hồi quy), hay có thể là dự đoán một nhãn phân lớp cho một đối tượng đầu vào (gọi là phân lớp). 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 cho một đối tượng bất kỳ là đầu vào hợp lệ, sau khi đã xem xét một số ví dụ 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 hoá từ các dữ liệu sẵn có để dự đoán những tình huống chưa gặp phải theo một cách hợp lý. Các ví dụ thường gặp của học có giám sát gồm việc phân loại các e-mail là thư rác, ghi nhãn các trang Web theo thể loại của chúng và nhận dạng chữ viết tay. Tóm lại mục đích chính của bài toán học có giám sát là để học một ánh xạ từ x tới y. Khi cho trước một tập huấn luyện gồm các cặp ( xi, yi ), trong đó yi  Y gọi là các nhãn của các mẫu xi. Nếu nhãn là các số, y  ( yi )T i[n] biểu diễn vec tơ cột của các nhãn. Hơn nữa, một thủ tục chuẩn là các cặp ( xi, yi ) được thử theo giả thiết phân bố ngẫu nhiên độc lập trên khắp X × Y. Mô hình chung của học có giám sát được khái quát như hình sau. Hình 1.2. Mô hình thuật toán học có giám sát Để giải quyết một bài toán nào đó của học có giám sát, người ta phải xem xét nhiều bước khác nhau: 1. Xác định loại của các ví dụ huấn luyện. Trước khi làm bất cứ điều gì, người làm nhiệm vụ phân lớp nên quyết định loại dữ liệu nào sẽ được sử dụng làm ví dụ. Chẳng hạn đó có thể là một kí tự viết tay đơn lẻ, toàn tập một từ viết tay, hay toàn tập một dòng chữ viết tay.
9 2. Thu thập tập huấn luyện. Tập huấn luyện cần đặc trưng cho thực tế sử dụng của hàm chức năng. Vì thế, một tập các đối tượng đầu vào được thu thập và đầu ra tương ứng được thu thập, hoặc từ các chuyên gia hoặc từ việc đo dạc tính toán. 3. Xác định việc biểu diễn các đặc trưng đầu vào cho hàm chức năng cần tìm. 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. 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ụ người thực hiện quá trình phân lớp có thể lựa chọn việc sử dụng mạng nơ-ron nhân tạo hay cây quyết định…. 5. Hoàn thiện thiết kế. Người thiết kế sẽ chạy giải thuật học từ mộ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 hoá 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. Hiện nay đã có rất nhiều thuật toán được sử dụng để tạo những trình học có giám sát, phổ biến nhất là:  Thuật toán K láng giềng gần nhất (KNN)  Mô hình xác suất đơn giản, Naïve Bayes  Phương pháp dùng máy vec tơ tựa SVM.  Phương pháp cây quyết định  Phương pháp mạng nơ ron nhân tạo.
10 1.1.5.2. Thuật toán K láng giềng gần nhất KNN là phương pháp truyền thống khá nổi tiếng và được đánh giá là một trong những phương pháp tố, theo tập dữ liệu Reuters phiên bản 21450, được sử dụng từ những thời kỳ đầu của việc phân loại văn bản. Khi cần phân loại một văn bản mới, thuật toán sẽ tính khoảng cách (khoảng cách Ơclit… của tất cả các văn bản trong tập huấn luyện đến văn bản này đề tìm ra k văn bản gần nhất (gọi là k “láng giềng", hay "hàng xóm”), sau đó dựa trên khoảng cách này tính trọng số cho tất cả chủ đề. Trọng số của một chủ đề chính là tổng tất cả khoảng cách ở trên của các văn bản trong k hàng xóm có cùng chủ đề, chủ đề nào không xuất hiện trong k hàng xóm sẽ có trọng số bằng 0. Sau đó các chủ đề sẽ được sắp xếp theo mức độ trọng số giảm dần và các chủ đề có trọng số cao sẽ được chọn là chủ đề của văn bản cần phân loại. Công thức tính trọng số cho các cụm: W(x, cj) =  di {KNN } sim( x, di ). y(di , c j )  b j (1.1) Trong đó:  y(di , cj) = 1 nếu câu hỏi di thuộc cụm cj; ngược lại y(di , cj) = 0.  sim (x, di) là độ tương đồng giữa câu hỏi phân loại x và câu hỏi di. x.di x di  sim (x, di) = cos (x, di) = (1.2)  bj là ngưỡng phân loại của nhãn cj. 1.1.5.3. Mô hình xác suất Naïve Bayes Kĩ thuật phân hoạch của Naive Bayes dựa trên cơ sở định lí Bayes và đặc biệt phù hợp cho các trường hợp phân loại có kích thước đầu vào là lớn. Mặc dù Naive Bayes khá đơn giản nhưng nó có khả năng phân loại tốt hơn rất nhiều phương pháp phân hoạch phức tạp khác. Với mỗi loại văn bản, thuật toán Naive Bayes tính
11 cho mỗi lớp văn bản một xác suất mà tài liệu cần phân hoạch có thể thuộc loại đó. Tài liệu đó sẽ được gán cho lớp văn bản nào có xác suất cao nhất. Chi tiết về thuật toán Naive Bayes sẽ được trình bày kĩ ở chương 2. 1.1.5.4. Phương pháp cây quyết định Cây quyết định là một trong những kĩ thuật học máy được nhiều người biết đến. Chúng được áp dụng rộng rãi và đa dạng của các lĩnh vực đặc biệt là các ứng dụng trong trí tuệ nhân tạo. Thành công của phương pháp này được chứng minh bằng khả năng xử lí các vấn đề phức tạp theo cách trình bày một khả năng có thể chấp nhận được dễ dàng cho việc diễn dịch và thậm chí còn có khả năng đưa ra các kết luận từ các luật logic. Một số phương pháp đã được đề xuất để xây dựng các cây quyết định. Những thuật toán này có đầu vào là một tập các tài liệu mẫu được đưa vào làm ví dụ. Ở đó mỗi tài liệu đựơc mô tả bởi việc thiết lập các giá trị thuộc tính và được gán cho các lớp. Đầu ra là một cây quyết định bảo đảm sự phân hoạch cho các ví dụ đưa vào. Vấn đề chính được nói rõ trong các thuật toán chuẩn của cây quyết định là kết quả có thể thay đổi bất chợt tùy thuộc vào dữ liệu. Sự không chắc chắn đó có thể xuất hiện trong các cấu tử hoặc có thể xuất hiện trong các giai đoạn phân hoạch. Cây quyết định được sử dụng để phân hoạch các đối tượng mới. Thuật giải trong cây quyết định được bắt đầu từ gốc của cây quyết định. Người ta đánh giá thử những thuộc tính có liên quan và chọn một nhánh tương ứng với sự lựa chọn đó. Qui trình này sẽ được lặp đi lặp lại đến khi gặp phải một lá. Như vậy đối tượng mà ta đang xét sẽ thuộc vào loại của lá mà ta vừa gặp phải. Điều đó cũng có nghĩa là thuật toán cây quyết định kết thúc khi mà quá trình phân tích gặp được một nút lá. 1.1.5.5. Phương pháp mạng nơ ron Phân loại văn bản bằng mô hình mạng nơ ron là một cách thức phân loại mới được đề xuất. Cấu trúc và hoạt động của mạng nơ ron cơ bản dựa trên bộ não con người. Mạng nơ ron được áp dụng trong khá nhiều lĩnh vực khác nhau và có khả
12 năng giải quyết các vấn đề phức tạp, phạm vi rộng. Trong phân loại tài liệu có thể dùng mạng nơ ron để phân chia gần đúng các tài liệu trong tập tài liệu thô đầu vào. Cấu trúc mạng nơ ron khá phức tạp, hầu hết các phần tử cấu thành mạng nơ ron là các nơ ron. Chúng được phân chia thành các lớp khác nhau và có mối liên hệ với các nơ ron trong cùng lớp hoặc khác lớp. Mối quan hệ giữa các nơ ron được biểu diễn bằng các cung tròn có đầu ra từ một nơ ron này và đầu vào từ một nơ ron khác, mối quan hệ giữa hai nơ ron lân cận nhau đặc trưng bằng trọng số w. 1.2. Tổng quan về thư rác 1.2.1. Định nghĩa về thư rác và các đặc trưng của thư rác 1.2.1.1. Định nghĩa về thư rác Từ lâu, thư điện tử đã trở thành một ứng dụng không thể thiếu khi Internet và công nghệ mạng phát triển. Thư điê ̣n tử, hay còn gọi là thư, là mô ̣t hê ̣ thố ng chuyể n nhâ ̣n thư từ qua các mạng máy tính. Thư điện tử là mô ̣t phương tiện truyề n thông rất hữu ích. Nó có thể chuyể n mẫu thông tin từ mô ̣t máy nguồ n tới mô ̣t hay nhiề u máy nhâ ̣n trong cùng mô ̣t lúc. Tuy nhiên, trong những năm gần đây, một hình thức mới của thư điện tử đã xuất hiện với số lượng lớn gây phiền hà cho người nhận và thiệt hại không nhỏ cho nền kinh tế mà ta gọi là thư rác hay spam emails. Hiện nay chưa có một định nghĩa hoàn chỉnh và chặt chẽ về thư rác. Có quan điểm chỉ coi thư rác là những thư quảng cáo không được yêu cầu UCE, có quan điểm có thư rác với nghĩa rộng hơn, bao gồm cả thư quảng cáo, thư nhũng lạm (quấy rối), và những thư có nội dung không lành mạnh UBE. Dưới đây sẽ đưa ra một định nghĩa thông dụng nhất về thư rác và giải thích các đặc điểm của nó để phân biệt thư rác với thư thông thường. Thư rác (spam) là những bức thư điện tử không yêu cầu, không mong muốn và được gửi hàng loạt tới nhiều người nhận. “Thư không yêu cầu” ở đây nghĩa là người nhận thư không yêu cầu người gửi gửi bức thư đó. “Thư được gửi hàng loạt”