- PHÂN LOẠI THƯ RÁC VỚI GIẢI THUẬT BOOSTING CÂY QUYẾT ĐỊNH NGẪU NHIÊN XIÊN PHÂN ĐƠN GIẢN. - Trong bài viết này chúng tơi đưa ra hướng tiếp cận học tự động để phát hiện thư rác với giải thuật Boosting cây quyết định ngẫu nhiên xiên phân đơn giản (Boosting of Random Oblique Decision Stump). - Để thực hiện, đầu tiên phải tạo ra tập dữ liệu gồm một bộ sưu tập các thư rác và thư khơng phải là thư rác. - Kế tiếp thực hiện tiền xử lý dữ liệu, bao gồm các bước phân tích từ vựng, chọn tập hợp từ hữu dụng để phân loại thư rác, xây dựng mơ hình túi từ. - Bước tiền xử lý sinh ra tập dữ liệu cĩ số chiều rất lớn, chúng tơi đề nghị giải thuật mới cĩ tên là Boosting cây quyết định ngẫu nhiên xiên phân đơn giản cho phép phân lớp hiệu quả tập dữ liệu này. - Kết quả thực nghiệm trên tập dữ liệu thực thu thập từ 1143 thư rác và 778 thư khơng phải thư rác cho thấy giải thuật do chúng tơi đề nghị phân lớp chính xác hơn so với giải thuật SVM và Nạve Bayes qua các tiêu chí so sánh như Accuracy, F1-Measure, Precision, TP Rate và TN Rate.. - Từ khĩa: Phân loại thư rác, giải thuật học Boosting cây quyết định ngẫu nhiên xiên phân đơn giản, giải thuật phân lớp dữ liệu, khai mỏ dữ liệu.. - trên tồn cầu nhận nhiều thư điện tử khơng phục vụ cho mục đích thiết thực của họ, mà thường chỉ là những thư quảng cáo, thư phản động, chơi đánh bạc, thậm chí là những đoạn mã độc hại, đồi trụy khác, mà chúng ta gọi đĩ là thư rác (spam emails).. - Trong những năm gần đây, các phương pháp chống thư rác đều theo hai nhĩm tiếp cận chính (Goodman et al., 2007), (Guzella and Caminhas, 2009), (Sebastiani, 2002). - Nhĩm giải pháp đầu tiên dựa vào việc tìm kiếm chính xác các mẫu xác định danh sách chính xác các địa chỉ người gửi thư rác, các địa chỉ mạng, tìm kiếm chính xác từ khĩa, để ngăn chặn thư rác. - Nhĩm giải pháp này thường rất nhanh nhưng rất dễ bị người phát tán thư rác qua mặt do chỉ cần thay đổi một ít thơng tin là các chương trình khơng thể phát hiện được. - Trong thực tế, các nghiên cứu chủ yếu tập trung vào máy học để phân loại thư rác dựa vào nội dung. - Nghiên cứu của Drucker và các cộng sự của ơng (Drucker et al., 1999) sử dụng mơ hình túi từ và giải thuật máy học véctơ hỗ trợ (SVM (Vapnik, 1995)) để phân lớp hiệu quả thư rác. - Một nghiên cứu khác của Sahami và các cộng sự (Sahami et al., 1998) đề xuất kết hợp mơ hình túi từ và giải thuật học Bayes thơ ngây (Nạve Bayes (Good, 1965)) cho phân lớp thư rác. - Trong bài viết này, chúng tơi đề xuất giải thuật phân lớp thư rác bằng phương pháp kết hợp mơ hình túi từ và giải thuật mới do chúng tơi đề xuất tên là Boosting cây quyết định ngẫu nhiên xiên phân đơn giản (Boosting of Random Oblique Decision Stump - BRODS). - BRODS là một giải thuật đơn giản, phân lớp hiệu quả trên tập dữ liệu cĩ số chiều rất lớn và thời gian thực hiện tương đối nhanh. - Kết quả thực nghiệm trên tập dữ liệu thư điện tử cho thấy rằng BRODS phân loại thư rác với độ chính xác cao hơn so với SVM (Vapnik, 1995) và Bayes thơ ngây (Good, 1965) trên các tiêu chí như Accuracy, F1-Measure, Precision, TP Rate và TN Rate.. - Trong phần 2, chúng tơi sẽ trình bày tĩm tắt các bước tiền xử lý dữ liệu dùng để phân loại thư rác dựa trên thư viện Bow (McCallum, 1998). - Tiếp theo, chúng tơi sẽ mơ tả giải thuật BRODS dùng cho việc phân loại thư rác trong phần 3. - 2 TIỀN XỬ LÝ DỮ LIỆU. - Tiếp cận của phương pháp mơ hình túi từ và máy học bắt đầu từ việc tạo ra tập dữ liệu để học mơ hình phân lớp thư điện tử cĩ phải là thư rác hay khơng. - Để giải quyết vấn đề này, chúng tơi phải tạo ra tập dữ liệu học gồm các thư rác và khơng phải thư rác, phân tích từ vựng và tách các từ trong nội dung thư của tập dữ liệu này. - Sau đĩ chọn tập hợp các từ mà cĩ thể dùng để phân loại thư rác, biểu diễn dữ liệu thư điện tử về dạng bảng để từ đĩ các giải thuật máy học cĩ thể học để phân loại thư.. - Tập dữ liệu do chúng tơi sưu tầm gồm cĩ 1921 tập tin sử dụng ngơn ngữ tiếng Anh và tiếng Việt (loại bỏ dấu) được phân vào hai thư mục tương ứng với hai lớp thư rác hay khơng phải thư rác. - Tập dữ liệu cĩ 1143 thư rác và 778 thư khơng phải thư rác. - Chúng tơi chỉ sử dụng tiêu đề và nội dung của thư để xử lý. - Véctơ này được xem như một phần tử trong tập dữ liệu, để làm được điều này, chúng tơi sử dụng thư viện Bow (McCallum, 1998) để tách từ và chuyển dữ liệu về với dạng bảng, gồm hai bước sau:. - Bước 1: Xây dựng mơ hình tách từ của các thư điện tử trong hai thư mục thư rác và khơng phải thư rác. - Dịng : 1921 dịng tương ứng với 1921 thư trong tập dữ liệu.. - Hình 1: Mơ hình tách từ của thư điện tử thu được từ thư viện Bow. - Bước 2: Dựa trên mơ hình tách từ của Bow vừa xây dựng, chúng tơi biểu diễn thư điện tử về mơ hình túi từ bằng cách trích ra cột thứ 2 làm lớp dữ liệu và các cột tần số xuất hiện của các từ đưa về một bảng dữ liệu. - Với mơ hình túi từ, chúng tơi thu được bảng dữ liệu cĩ 1921 dịng (mỗi dịng tương ứng với một thư) và 28719 thuộc tính (mỗi thuộc tính tương ứng với một từ, giá trị mỗi thuộc tính là tần số xuất hiện của từ trong thư) và thuộc tính cuối cùng là lớp dữ liệu (thư rác hay khơng phải thư rác).. - Qua bước tiền xử lý dữ liệu, chúng ta cĩ thể thấy rằng tập dữ liệu thư cĩ số lượng chiều (thuộc tính) rất lớn. - Ngoại trừ giải thuật SVM (Vapnik, 1995) và rừng ngẫu nhiên xiên phân RF-ODT (Do et al., 2009), hầu hết các phương pháp học tự động hiện nay gặp nhiều khĩ khăn trong việc xử lý tập dữ liệu cĩ số chiều lớn. - Để cĩ thể phân lớp hiệu quả tập dữ liệu thư này, chúng tơi đã đề xuất giải thuật Boosting cây quyết định ngẫu nhiên xiên phân đơn giản (BRODS) được kết hợp từ cây ngẫu nhiên xiên phân (Do et al., 2009) với kỹ thuật Boosting (Freund and Schapire, 1995).. - 3 BOOSTING CÂY NGẪU NHIÊN XIÊN PHÂN ĐƠN GIẢN (BRODS) Giải thuật boosting cây quyết định ngẫu nhiên xiên phân đơn giản (BRODS) là xây dựng tập các bộ phân lớp yếu là cây ngẫu nhiên xiên phân đơn giản sao cho mỗi bước xây dựng cây tập trung vào khắc phục lỗi từ các mơ hình xây dựng từ các bước lặp trước đĩ.. - 3.1 Cây quyết định ngẫu nhiên xiên phân đơn giản. - Quá trình xây dựng cây quyết định của các giải thuật học tự động CART (Breiman et al., 1984) hay C4.5 (Quinlan, 1993) được làm như sau:. - Bắt đầu nút gốc, tất cả các dữ liệu học ở nút gốc,. - Nếu dữ liệu tại 1 nút cĩ cùng lớp thì nút được cho là nút lá, nhãn của nút lá là nhãn của các phần tử trong nút lá (hay luật bình chọn số đơng nếu nút lá cĩ chứa các phần tử cĩ lớp khác nhau),. - Nếu dữ liệu ở nút khơng thuần nhất (cĩ sự lẫn lộn các phần tử của nhiều lớp khác nhau) thì nút được cho là nút trong, tiến hành phân hoạch dữ liệu một cách đệ quy bằng việc chọn 1 thuộc tính để thực hiện phân hoạch tốt nhất cĩ thể.. - Chúng ta cĩ thể thấy rằng quá trình xây dựng cây của các giải thuật học chỉ chọn một thuộc tính cho việc phân hoạch dữ liệu tại các nút. - Hơn nữa, khi Freund và các cộng sự (Freund and Schapire, 1995) đề xuất boosting trên cây quyết định đơn giản (decision stump chỉ gồm 1 nút gốc và 2 nút lá) cĩ thể thấy rằng cây chỉ sử dụng duy nhất 1 thuộc tính để tạo bộ phân lớp yếu. - Do đĩ, tính mạnh mẽ của cây bị giảm khi làm việc với các tập dữ liệu cĩ số chiều lớn và phụ thuộc lẫn nhau, chẳng hạn như dữ liệu thư điện tử mà chúng tơi xử lý ở đây. - Tức là, cây quyết định đơn giản (decision stump) khơng hiệu quả bằng cây quyết định xiên phân đơn giản (decision oblique stump).. - Để khắc phục nhược điểm trên, nhiều giải thuật xây dựng cây quyết định sử dụng phân hoạch đa thuộc tính (xiên phân) tại các nút được đề nghị. - Nghiên cứu tiên phong của Murthy và các cộng sự trong (Murthy et al., 1993) đã đưa ra giải thuật OC1, một hệ thống dùng để xây dựng các cây quyết định xiên trong đĩ dùng leo đồi để tìm một phân hoạch xiên tốt dưới dạng một siêu phẳng.. - Rừng ngẫu nhiên xiên phân RF-ODT của chúng tơi trong (Do, et al., 2009) xây dựng các cây xiên phân ngẫu nhiên dựa trên siêu phẳng tối ưu (phân hoạch hiệu quả cao, khả năng chịu đựng nhiễu tốt) thu được từ huấn luyện SVM (Vapnik, 1995).. - Để giải quyết 2 vấn đề chính là độ phức tạp và hiệu quả của bộ phân lớp yếu của kỹ thuật boosting, chúng tơi đề xuất chỉ xây dựng cây ngẫu nhiên xiên phân đơn giản (Random Oblique Decision Stump, RODS). - Giải thuật RODS xây dựng cây như mơ tả trong hình 3. - Cây xiên phân 3 nút, bắt đầu với tồn bộ dữ liệu nằm ở nút gốc, chọn ngẫu nhiên n’ thuộc tính từ tập n thuộc tính ban đầu của dữ liệu là tìm ra siêu phẳng tối ưu n’ chiều (SVM (Vapnik, 1995)) để phân hoạch dữ liệu.. - Dựa vào dấu của biểu thức mà dữ liệu sẽ được phân hoạch qua trái hay qua phải để dự báo nhãn.. - Cây xiên phân ngẫu nhiên đơn giản cĩ thể làm việc hiệu quả trên tập dữ liệu cĩ số chiều lớn do nĩ đảm bảo được 2 yếu tố cơ bản là thời gian xây dựng nhanh và hiệu quả phân lớp cao. - Do đơn giản chỉ cĩ 3 nút, việc xây dựng cây xiên phân ngẫu nhiên rất nhanh khi chỉ tìm một siêu phẳng tối ưu trong khơng gian n’ chiều (n’ <<. - Việc kết hợp nhiều thuộc tính để tạo phân hoạch xiên phân giúp phân lớp hiệu quả dữ liệu cĩ số chiều lớn.. - Hình 3: Cây ngẫu nhiên xiên phân đơn giản. - 3.2 Giải thuật Boosting cây ngẫu nhiên xiên phân đơn giản (BRODS). - Tuy nhiên, để cải thiện hơn hiệu quả phân lớp dữ liệu thư rác, chúng tơi tiếp tục áp dụng kỹ thuật boosting dựa trên bộ phân lớp yếu là cây ngẫu nhiên xiên phân đơn giản.. - Đây là một phương pháp xây dựng tập hợp các mơ hình phân lớp yếu để nâng cao hiệu quả của các bộ phân lớp này.. - Ý tưởng chính của giải thuật này là lặp lại quá trình học của một bộ phân lớp yếu nhiều lần. - Sau mỗi bước lặp, bộ phân lớp yếu (chẳng hạn như cây ngẫu nhiên xiên phân đơn giản) sẽ tập trung học trên các phần tử bị phân lớp sai trong các lần lặp trước. - Sau mỗi bước học, các trọng số này sẽ được cập nhật lại bằng cách tăng trọng số cho các phần tử bị phân lớp sai và giảm cho các phần tử được phân lớp đúng. - Kết thúc quá trình học thu được tập hợp các mơ hình học dùng để phân lớp. - Để phân lớp dữ liệu mới đến, người ta sử dụng luật bình chọn số đơng từ kết quả phân lớp của từng mơ hình phân lớp yếu. - Lấy ngẫu nhiên n’ thuộc tính từ tập n thuộc tính của dữ liệu (n’ <<. - Giải thuật 1: Boosting của cây ngẫu nhiên xiên phân đơn giản. - Giải thuật boosting cây ngẫu nhiên xiên phân đơn giản cải thiện được độ chính xác so với việc sử dụng mơ hình đơn của một cây. - Giải thuật đáp ứng được yêu cầu xử lý hiệu quả dữ liệu thư điện tử cĩ số chiều lớn.. - Để đánh giá hiệu quả của tiếp cận do chúng tơi đề xuất cho phân lớp thư rác, chúng tơi đã tiến hành cài đặt giải thuật boosting cây ngẫu nhiên xiên phân đơn giản (BRODS) bằng C/C++ trên hệ điều hành LINUX (Mandriva 2008) cĩ sử dụng thư viện SGDSVM (Bottou and Bousquet, 2008).. - Như đã trình bày ở phần 2, sau bước tiền xử lý chúng tơi thu được tập dữ liệu cĩ 1921 phần tử (1143 thư rác và 778 thư khơng phải thư rác), 28719 thuộc tính, 2 lớp (thư rác hay khơng phải thư rác). - Chúng tơi sử dụng giải thuật boosting cây ngẫu. - m phần tử dữ liệu : {(x j , y j. - khởi động phân phối của m phần tử dữ liệu Dist 1 (j) cho j = 1 tới m thực hiện. - học mơ hình cây ngẫu nhiên xiên phân đơn giản h i từ tập mẫu S i h i = RODS(S i. - tính lại lỗi dự đốn của mơ hình h i. - tính trọng số cho mơ hình h i α i =(1/2)ln[(1-ε i )/ε i. - cập nhật lại phân phối của m phần tử dữ liệu cho j = 1 tới m thực hiện. - trả về T cây ngẫu nhiên xiên phân đơn giản và trọng số tương ứng {h i , α i } i=1,T. - Phân lớp:. - phân lớp phần tử x: H(x. - nhiên xiên phân đơn giản, giải thuật máy học SVM chuẩn (LibSVM (Chang and Lin, 2001)) và Bayes thơ ngây trong thư viện máy học Weka (Witten and Frank, 2005) để phân lớp dữ liệu thư rác hay khơng. - Nghi thức kiểm tra chéo (10-fold) được áp dụng để đánh giá hiệu quả của các giải thuật phân lớp. - tập dữ liệu chia thành 10 phần bằng nhau, ở lần thứ i lấy ra phần thứ i để làm tập kiểm tra và 9 phần cịn lại dùng làm tập huấn luyện. - Các tiêu chí đánh giá hiệu quả dựa vào các kết quả thu được từ phân lớp của các giải thuật.. - tp: số thư rác được phân loại vào lớp thư rác,. - fp: số thư khơng phải thư rác được phân loại vào lớp thư rác, fn: số thư rác được phân loại vào lớp khơng phải thư rác,. - tn: số thư khơng phải thư rác được phân vào lớp khơng phải thư rác.. - Chúng tơi sử dụng cả 5 tiêu chí trên để so sánh hiệu quả của các giải thuật phân lớp thư rác. - Bảng 1 trình bày kết quả thu được từ 3 giải thuật phân lớp boosting cây ngẫu nhiên xiên phân đơn giản, SVM và Bayes thơ ngây. - Nhìn vào bảng kết quả, cĩ thể thấy được Bayes thơ ngây cho kết quả rất thấp khi phân lớp. - Mặc dù Bayes thơ ngây được dùng phổ biến trong thực tế cho lọc thư rác nhưng với dữ liệu số chiều lớn thì mơ hình này khơng cịn hiệu quả nữa. - Tiếp đến là giải thuật SVM, cĩ lẽ do sử dụng mơ hình đơn nên SVM cho kết quả thấp hơn giải thuật do chúng tơi đề xuất (boosting cây ngẫu nhiên xiên phân đơn giản BRODS). - Kết quả này cho phép chúng tơi tin tưởng vào khả năng xử lý hiệu quả của giải thuật cho vấn đề phân lớp thư rác và dữ liệu cĩ số chiều lớn.. - Bảng 1: Kết quả phân lớp thư rác. - Trong bài viết này, chúng tơi vừa trình bày một hướng tiếp cận trong việc phân loại thư rác. - Chúng tơi đã sử dụng mơ hình túi từ để biểu diễn các thư điện tử. - Tập dữ liệu thư rác sau bước tiền xử lý cho ra tập dữ liệu cĩ số chiều lớn đến 28719.. - Tiếp theo sau, chúng tơi đề nghị giải thuật mới Boosting cây quyết định ngẫu nhiên xiên phân đơn giản cho phép phân lớp hiệu quả trên dữ liệu thư điện tử cĩ số chiều lớn. - Kết quả thực nghiệm cho thấy giải thuật do chúng tơi đề xuất cho kết quả tốt hơn giải thuật SVM và Nạve Bayes qua các tiêu chí so sánh như Accuracy, F1-Measure, Precision, TP Rate và TN Rate.. - Trong tương lai, chúng tơi sẽ phát triển để xây dựng ứng dụng tích hợp vào hệ thống của server cho phép lọc thư rác