Seminar Công nghệ tri thức GVHD: GS-TSKH. Hoàng Kiếm ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN ________________ BÁO CÁO SEMINAR CHUYÊN ĐỀ CÔNG NGHỆ TRI THỨC Đề tài: ỨNG DỤNG CÔNG NGHỆ TRI THỨC TRONG VIỆC TÌM HIỂU CÁC PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN – EMAIL Giảng viên hướng dẫn: GS-TSKH. Hoàng Kiếm Sinh viên thực hiện: Trần Thị Diễm Trang – CH0901057 Lớp: Cao học CNTTQM – Khóa 4 Tp. Hồ Chí Minh – Tháng 03/2014 Seminar Công nghệ tri thức GVHD: GS-TSKH. Hoàng Kiếm ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN ________________ BÁO CÁO SEMINAR CHUYÊN ĐỀ CÔNG NGHỆ TRI THỨC Đề tài: ỨNG DỤNG CÔNG NGHỆ TRI THỨC TRONG VIỆC TÌM HIỂU CÁC PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN – EMAIL Giảng viên hướng dẫn: GS-TSKH. Hoàng Kiếm Sinh viên thực hiện: Trần Thị Diễm Trang – CH0901057 Lớp: Cao học CNTTQM – Khóa 4 Tp. Hồ Chí Minh – Tháng 03/2012 Trần Thị Diễm Trang – CH0901057 Trang 1 Seminar Cụng ngh tri thc GVHD: GS-TSKH. Hong Kim MC LC TRNG I HC CễNG NGH THễNG TIN 1 TRNG I HC CễNG NGH THễNG TIN 1 MC LC 2 LI CM N 4 LI NểI U 6 CHệễNG I:TNG QUAN 8 I.Yờu cu t ra 8 II.Cỏc cỏch thc con ngi x lý vi spam 8 III. Cỏc phng phỏp tip cn phõn loi vn bn - email 9 1.í tng ca mt s phng phỏp tip cn 9 2.Phng phỏp tip cn Mỏy hc (Machine Learning) 10 CHệễNG II:TèM HIU MT S THUT TON PHN LOI VN BN EMAIL 12 IV.Thut toỏn cõy quyt nh (Decision Tree) 12 1.nh ngha 12 3.Thut toỏn 12 4.u Nhc im ca phng phỏp cõy quyt nh 15 V.Thut toỏn K-NN (K-Nearest Neighbors algorithm) 16 1.Gii thiu 16 2.Thut toỏn K-NN 16 5.u Nhc im ca phng phỏp K-NN 17 CHệễNG III:THUT TON NAẽVE BAYES V ADABOOST - NG DNG TRONG PHN LOI EMAIL 18 VI.Thut toỏn Naùve Bayes 18 1.Gii thiu 18 6.Phõn loi email bng phng phỏp Naùve Bayes 19 7.u nhc im ca phng phỏp phõn loi Naùve Bayes 21 VII.Thut toỏn AdaBoost 22 1.Gii thiu 22 8.Thut toỏn AdaBoost 22 9.AdaBoost trong phõn loi vn bn nhiu lp 23 Trn Th Dim Trang CH0901057 Trang 2 Seminar Công nghệ tri thức GVHD: GS-TSKH. Hoàng Kiếm 10.Ứng dụng AdaBoost trong phân loại email 24 11. Ưu – nhược điểm của phương pháp phân loại AdaBoost 29 CHÖÔNG IV:ĐÁNH GIÁ - KẾT LUẬN 31 TÀI LIỆU THAM KHẢO 32 * * * Trần Thị Diễm Trang – CH0901057 Trang 3 Seminar Công nghệ tri thức GVHD: GS-TSKH. Hoàng Kiếm LỜI CẢM ƠN  Công nghệ tri thức ngày nay đóng vai trò hết sức quan trọng trong ngành công nghệ máy tính. Chính nhờ nó mà máy tính có thể “hiểu”, giải quyết nhiều bài toán phức tạp trong nhiều ngành khoa học cũng như các nhu cầu trong đời sống hằng ngày Qua Seminar chuyên đề “Công nghệ tri thức”, tôi cũng như các bạn cùng lớp đã đúc kết được rất nhiều kiến thức bổ ích cho bản thân. Tuy thời gian nghiên cứu cho chuyên đề không nhiều nhưng những thông tin mới mẻ cũng như xu hướng phát triển của tri thức hiện nay mà Thầy Hoàng Kiếm cung cấp trong môn học đã giúp chúng tôi hình thành những cái nhìn sâu hơn, mới hơn về công nghệ tri thức cũng như các ứng dụng của chúng vào trong thực tế. Trong thời gian học tập cũng như làm báo cáo seminar này, bản thân tôi và các bạn cùng lớp đã nhận được sự chỉ dạy, hướng dẫn rất nhiệt tình và khoa học của GS- TSKH. Hoàng Kiếm, Thầy đã hỗ trợ bài giảng, tài liệu, cũng như luôn theo dõi, hướng dẫn và động viên chúng tôi kịp lúc. Chúng em rất cảm ơn và xin kính chúc Thầy nhiều sức khỏe, thành công. Cũng xin gởi lời cảm ơn chân thành đến quý Thầy Cô của Phòng Sau ĐH, cũng như tất cả quý Thầy Cô của trường Đại Học Công Nghệ Thông Tin đã tận tình hướng dẫn, giảng dạy và truyền đạt kiến thức cho chúng em trong suốt quá trình học. Xin cám ơn các bạn cùng lớp Cao học CNTTQM khóa 4 đã giúp đỡ tôi trong thời gian học tập, nghiên cứu, trao đổi bài học trên diễn dàn. Cuối cùng, xin tri ân gia đình, nơi có những người thân yêu luôn ở bên cạnh chia sẻ, giúp đỡ và động viên tôi về tinh thần cũng như vật chất trong quãng thời gian hơn hai năm học tập. Trân trọng. Trần Thị Diễm Trang Trần Thị Diễm Trang – CH0901057 Trang 4 Seminar Công nghệ tri thức GVHD: GS-TSKH. Hoàng Kiếm * * * Trần Thị Diễm Trang – CH0901057 Trang 5 Seminar Công nghệ tri thức GVHD: GS-TSKH. Hoàng Kiếm LỜI NÓI ĐẦU  Phân loại văn bản là một vấn đề quan trọng trong lĩnh vực xử lý ngôn ngữ, nhiệm vụ của nó là gán các tài liệu văn bản vào nhóm các chủ đề cho trước. Đây là một bài toán rất thường gặp trong thực tế, một ví dụ điển hình cho việc phân loại văn bản thường thấy là việc phân loại email, và đây là giới hạn cho phạm vi nghiên cứu của đề tài này. Thời đại ngày nay là thời đại bùng nổ thông tin, việc sử dụng Internet trở nên quen thuộc và không thể thiếu trong cuộc sống mỗi người, mỗi quốc gia. Các dịch vụ trên Internet đã trở nên rất phổ biến, trong đó có email, là dịch vụ nhận/gửi thư điện tử có chi phí rất thấp, nhanh chóng và hiệu quả nhất. Hằng ngày mỗi người chúng ta đều có thể nhận được một lượng lớn email, khi email được gửi đến hộp thư, nếu để người dùng phải đọc tất cả các email thì sẽ tốn rất nhiều thời gian vì trong đó có những email cần thiết, hữu ích; nhưng cũng có những email vô bổ, chứa nội dung mà ta không quan tâm, không muốn nhận; ta gọi các email đó là email spam. Ngược lại, những email không phải spam gọi là non-spam – email hợp lệ được người dùng chấp nhận. Spam chính là những email được phát tán rộng rãi không theo bất cứ một yêu cầu nào của người nhận, với số lượng lớn, nhiều nhất là những email quảng cáo, đính kèm virus, …. Spam đã và đang gây tác hại đến người sử dụng dịch vụ email và tốc độ đường truyền Internet, gây thiệt hại rất lớn về kinh tế. Với người sử dụng email, spam gây cho họ cảm giác bực bội và phải mất thời gian và công sức để xóa chúng, đôi khi bị xóa nhầm và do đó họ còn có thể mất đi những email quan trọng khác. Tốc độ đường truyền của Internet cũng bị spam làm cho chậm lại vì số lượng spam được chuyển đi là cực lớn. Cho dù được nhận diện là “kẻ thù cộng đồng” (public enemy), nhưng spam đã và đang mang lại lợi nhuận cho một số nhà đầu tư. Trong số 100.000 email spam phát tán, chỉ cần một email nào có phản hồi là đã có thể bù đắp chi phí đầu tư. Trần Thị Diễm Trang – CH0901057 Trang 6 Seminar Công nghệ tri thức GVHD: GS-TSKH. Hoàng Kiếm Trong thời gian vài năm trở lại đây chúng ta đã chứng kiến sự bùng nổ của số người sử dụng Internet. Và cũng từ đây spam đã phát triển một cách nhanh chóng, do đó những kỹ thuật ngăn chặn spam phải ngày một nâng cấp và cải tiến hơn và cần có một hệ thống phân loại hiệu quả đâu là email spam và đâu là email non-spam. Để ngăn chặn spam, nhiều nhà khoa học, các tổ chức, cá nhân đã nghiên cứu và phát triển những kỹ thuật phân loại và lọc văn bản nói chung và email nói riêng. Tuy nhiên, các spammer – những người tạo và phát tán spam – cũng tìm mọi cách vượt qua các bộ lọc này. Cuộc chiến giữa các spammer và những người chống spam vẫn đang còn tiếp diễn và dường như không có hồi kết. Thực tế cho thấy, nhu cầu có một phương pháp và công cụ chống spam hữu hiệu là rất cần thiết. Để giải bài toán này đã có rất nhiều phương pháp được đưa ra như: Naïve Bayes, K-NN (K-Nearest- Neighbor), Cây quyết định (Decision Tree), Mạng Neuron nhân tạo (Artificial Neural Network) và SVM (Support Vector Machine), AdaBoost, …. Mỗi phương pháp đều cho kết quả khá tốt, tuy nhiên để có được sự so sánh đầy đủ, ở các phần sau chúng ta sẽ đi vào tìm hiểu từng phương pháp. Xuất phát từ thực trạng trên, tôi chọn đề tài báo cáo seminar chuyên đề Công nghệ tri thức là “Ứng dụng công nghệ tri thức trong việc tìm hiểu các phương pháp phân loại văn bản – email”. Đề tài thực hiện gồm các chương: Chương I: Tổng quan Chương II: Tìm hiểu một số thuật toán phân loại văn bản - email Chương III: Thuật toán Naïve Bayes và AdaBoosting – Ứng dụng trong phân loại email Chương IV: Đánh giá – Kết luận. * * * Trần Thị Diễm Trang – CH0901057 Trang 7 Seminar Công nghệ tri thức GVHD: GS-TSKH. Hoàng Kiếm CHÖÔNG I: TỔNG QUAN I. Yêu cầu đặt ra Việc phân loại văn bản (cụ thể giới hạn trong đề tài này là email) và ngăn chặn email spam là phân biệt được email đó là spam hay non-sam, từ đó sẽ có biện pháp ngăn chặn được email spam. Hiệu quả việc phân loại spam phải khả quan, tuy nhiên cần tránh việc cho rằng email non-spam là email spam vì có thể gây hậu quả nghiêm trọng hơn là khả năng lọc spam thấp. Bởi vì cùng với việc tăng khả năng, hiệu quả phân loại spam thì khả năng nhận nhầm email non-spam là email spam cũng tỉ lệ theo. Do đó yêu cầu đặt ra đối với một hệ thống phân loại spam là phải nhận ra được email spam càng nhiều càng tốt và giảm thiểu lỗi nhận sai email non-spam là spam. II. Các cách thức con người xử lý với spam Khi ta nhận được một email mới gửi đến, khi đó ta dựa vào một số đặc điểm hay thuộc tính nào đó của email để tăng khả năng phân loại chính xác email đó. Các đặc điểm của một email như: tiêu đề, nội dung, có tập tin đính kèm hay không… Càng nhiều những thông tin như vậy xác suất phân loại đúng càng lớn, tất nhiên còn phụ thuộc vào kích thước của tập mẫu huấn luyện. Hiện nay đã có nhiều công ty, tổ chức, cá nhân phát triển hệ thống với nhiều cách thức khác nhau để giải quyết vấn nạn spam, như: - Xây dựng sẵn một danh sách đen (Blacklist) chứa các tên miền mà từ đó spam được tạo ra và phát tán; các email đến từ các tên miền này hoàn toàn bị khóa (block out) - Căn cứ vào header của email (như nơi gửi (from), chủ đề (subject), …) và loại bỏ những email có địa chỉ xuất phát từ spammer. - Dựa vào nội dung của email với những dấu vết cho thấy sự tồn tại của email (như email có quá nhiều dấu chấm than, số chữ cái được viết hoa nhiều một cách bất bình thường, …) Tuy nhiên để đối phó với các hệ thống lọc, các spammer sẽ ngày càng tinh vi, các kỹ thuật cải tiến spam ngày càng được đổi mới, và chính những cải tiến này ngày càng thôi thúc các spammer trở nên tinh vi và khó lường hơn… Kết quả là hiện nay Trần Thị Diễm Trang – CH0901057 Trang 8 Seminar Công nghệ tri thức GVHD: GS-TSKH. Hoàng Kiếm các email spam gần giống với email thông thường. Tuy nhiên email spam có một đặc điểm không bao giờ thay đổi, đó là bản chất nội dung của nó. Những email spam luôn có nội dung là quảng cáo sản phẩm hay dịch vụ nào đó. Cho nên đây chính là cơ sở cho phương pháp lọc spam dựa trên nội dung (content based filterng). Theo đó hệ thống lọc cố gắng phát hiện ra các ngôn ngữ dùng để quảng cáo thay vì chú ý đến các chỉ số thống kê của email. III. Các phương pháp tiếp cận phân loại văn bản - email 1. Ý tưởng của một số phương pháp tiếp cận Có rất nhiều phương pháp tiếp cận phân loại văn bản - email đã được nghiên cứu như: - Complaining to Spammers’ ISPs: Tìm cách tăng chi phí gửi spam của các spammer bằng những lời than phiền, phản ánh đến các nơi cung cấp dịch vụ mạng (ISP). - Mail Blacklists/Whitelists: Một danh sách đen các địa chỉ email hay các máy chủ email (mail server) chuyên dùng của các spammer sẽ được thiết lập và dựa vào đó ta có thể ngăn chặn nhận email spam được phát tán từ những nơi này. - Mail volume: Bộ lọc sẽ dùng thuật toán để kiểm tra số lượng email nhận được từ một máy chủ (host) cụ thể trong các lần kết nối sau cùng. Nếu số lượng email nhận được lớn hơn một ngưỡng nào đó thì các email đó sẽ được phân loại là spam. - Signature/Checksum Schemes: Đây là một trong những phương pháp phân loại email dựa trên nội dung. Khi một email tới thì giá trị “Signature/checksum” sẽ được tính toán cho mỗi email này và so sánh nó với giá trị tính được từ những email spam đặc trưng trong những email có sẵn trên Internet. Email sẽ được xem là spam nếu giá trị “Signature/checksum” của nó giống với bất kỳ giá trị nào trong cơ sở dữ liệu. Trần Thị Diễm Trang – CH0901057 Trang 9 [...]... thuc tớnh no ú ca email thỡ ta cú th nõng cao hiu qu nhn c email l mt spam Mt email cú nhiu c im nh: tiờu , ni dung, cú ớnh kốm tp tin hay khụng, Ta cú th da vo cỏc thụng tin ny nõng cao hiu qu phõn loi email spam Mt vớ d n gin: nu ta bit c rng 95% email html l email spam, v ta li nhn c mt email html, nh vy cú th da vo xỏc sut bit trc 95% email html l email spam tớnh c xỏc sut email m ta nhn c l... Seminar Cụng ngh tri thc GVHD: GS-TSKH Hong Kim T xỏc sut ny, ta so sỏnh vi mt giỏ tr ngng t m ta cho l ngng phõn loi email spam hay khụng, nu xỏc sut ny ln hn t, ta cho email ú l spam, ngc li ta xem email ú l non-spam b) Chn ngng phõn loi email: Trong phõn loi email, cú hai loi sai lm: sai lm th nht l nhn mt email l spam mc dự thc t nú l non-spam (false positive) v sai lm th hai l nhn mt email l non-spam... nh nht 10 ng dng AdaBoost trong phõn loi email Trn Th Dim Trang CH0901057 Trang 24 Seminar Cụng ngh tri thc GVHD: GS-TSKH Hong Kim Bi toỏn chỳng ta ang xột l phõn loi email, õy chỳng ta ch phõn loi email hoc l loi spam hoc l non-spam Nh vy bi toỏn phõn loi email l trng hp c bit ca phõn loi vn bn nhiu lp khi mi mu hun luyn ch nhn mt nhón n thay vỡ mt tp nhón Khi ú phõn loi email vi 2 lp spam v non-spam... tha s trong tớch trờn cú th c tớnh d dng t tp hun luyn ban u, nh vy vi phng phỏp Naùve Bayes gim s phc tp ca vic tớnh toỏn giỏ tr xỏc sut P(X1=x1 X2=x2 Xn=xn | C=c) 6 Phõn loi email bng phng phỏp Naùve Bayes õy mi mu m ta xột chớnh l mi mt email, tp cỏc lp m mi email cú th thuc v l C = {spam, non-spam} Khi ta nhn c mt email, nu ta khụng bit mt thụng tin gỡ v nú, do ú khú cú th quyt nh chớnh xỏc email. .. ngh tri thc - GVHD: GS-TSKH Hong Kim Genetic Algorithms: B lc da trờn thut toỏn di truyn s dng cỏc b nhn dng c trng ghi im cho mi email phõn bit email cú l spam hay khụng - Rule-Based (Heuristic): Da vo lut tỡm kim cỏc mu cú du hiu l spam nh cỏc t v ng xỏc nh, hng lot cỏc ch hoa v du chm than, phn header ca email sai nh dng, ngy ca email khụng ỳng vi thc t - Challenge-Response: Khi bn nhn c mt email. .. kh nng cũn hn ch v thi gian cú hn nờn trong bỏo cỏo ny tụi mi ch thc hin phn trỡnh by lý thuyt tỡm hiu v cỏc phng phỏp, cha thc hin vic th nghim demo chng trỡnh kim th v phõn loi email thc t Bờn cnh ú cn m rng phõn loi vi email l ting Vit thay vỡ ch thc hin vi email ting Anh Tuy nhiờn vn phõn loi email ting Vit cú mt s im khú khn l khụng cú sn mt kho ng liu email ting Vit phc v cho vic hc, thờm... s tỡm hiu chi tit phng phỏp phõn loi vn bn email vi hai thut toỏn mi v ph bin hin nay l Naùve Bayes v AdaBoost *** Trn Th Dim Trang CH0901057 Trang 17 Seminar Cụng ngh tri thc CHệễNG III: GVHD: GS-TSKH Hong Kim THUT TON NAẽVE BAYES V ADABOOST NG DNG TRONG PHN LOI EMAIL VI Thut toỏn Naùve Bayes 1 Gii thiu Phõn loi Naùve Bayes l phng phỏp phõn loi s dng tri thc cỏc xỏc sut ó qua hun luyn Phng phỏp... s tng lờn nhn mnh nhng mu hun luyn b phõn loi sai, ngc li, trng s gim xung 9 AdaBoost trong phõn loi vn bn nhiu lp * Cỏc thut toỏn trong AdaBoost Mt trong cỏc lnh vc ng dng quan trng ca thut toỏn AdaBoost l phõn loi vn bn Trong phõn loi vn bn vi nhiu lp, cú hai thut toỏn AdaBoost mi nht l AdaBoost.MH v AdaBoost.MR, trong phm vi bi bỏo cỏo ny tụi ch xin tp trung nghiờn cu tỡm hiu thut toỏn AdaBoost.MH... xỏc sut email ú l nonspam, cú th kt lun rng email ú l spam, tuy nhiờn kt lun ny khụng chớnh xỏc lm Nhng nu ta cú c nhiu xỏc sut bit trc nh vy, thỡ kt lun s tr nờn ỏng tin cy hn cú c cỏc xỏc sut bit trc ny, s dng phng phỏp Naùve Trn Th Dim Trang CH0901057 Trang 19 Seminar Cụng ngh tri thc GVHD: GS-TSKH Hong Kim Bayes hun luyn mu (email) ban u, sau ú s s dng cỏc xỏc sut ny ng vo phõn loi mt mu (email) ... hn rt nhiu Trn Th Dim Trang CH0901057 Trang 29 Seminar Cụng ngh tri thc GVHD: GS-TSKH Hong Kim *** Trn Th Dim Trang CH0901057 Trang 30 Seminar Cụng ngh tri thc CHệễNG IV: GVHD: GS-TSKH Hong Kim NH GI - KT LUN Trong bỏo cỏo chuyờn ny tụi ó trỡnh by vic ng dng cụng ngh tri thc vo quỏ trỡnh tỡm hiu cỏc phng phỏp tip cn dựng phõn loi email núi riờng v phõn loi vn bn núi chung, vi vic tỡm hiu tng quỏt . đề Công nghệ tri thức là Ứng dụng công nghệ tri thức trong việc tìm hiểu các phương pháp phân loại văn bản – email . Đề tài thực hiện gồm các chương: Chương I: Tổng quan Chương II: Tìm hiểu. TIN ________________ BÁO CÁO SEMINAR CHUYÊN ĐỀ CÔNG NGHỆ TRI THỨC Đề tài: ỨNG DỤNG CÔNG NGHỆ TRI THỨC TRONG VIỆC TÌM HIỂU CÁC PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN – EMAIL Giảng viên hướng dẫn: GS-TSKH. Hoàng. THỨC Đề tài: ỨNG DỤNG CÔNG NGHỆ TRI THỨC TRONG VIỆC TÌM HIỂU CÁC PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN – EMAIL Giảng viên hướng dẫn: GS-TSKH. Hoàng Kiếm Sinh viên thực hiện: Trần Thị Diễm Trang – CH0901057