Tài liệu Khai phá dữ liệu văn bản bằng lý thuyết tập thô

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG LA ĐỨC DŨNG KHAI PHÁ DỮ LIỆU VĂN BẢN BẰNG LÝ THUYẾT TẬP THÔ LUẬN VĂN THẠC SỸ 0KHOA HỌC MÁY TÍNH Thái Nguyên – 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG LA ĐỨC DŨNG KHAI PHÁ DỮ LIỆU VĂN BẢN BẰNG LÝ THUYẾT TẬP THÔ LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS Vũ Đức Thi. Thái Nguyên – 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn a MỤC LỤC LỜI CẢM ƠN...................................................................................I LỜI CAM ĐOAN..............................................................................II DANH MỤC CÁC HÌNH VẼ ............................................................. III DANH MỤC CÁC BẢNG BIỂU ........................................................ IV DANH MỤC CHỮ VIẾT TẮT .............................................................V LỜI MỞ ĐẦU ........................................................................................ 1 CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VĂN BẢN VÀ LÝ THUYẾT TẬP THÔ ....................................................................... 4 1.1 Khai phá dữ liệu văn bản ................................................................ 4 1.1.1 Khai phá dữ liệu .......................................................................... 4 1.1.1.1 Khái niệm ............................................................................. 4 1.1.1.2 Lịch sử nghiên cứu ................................................................ 5 1.1.1.3 Các khía cạnh khai phá chủ yếu ............................................ 5 1.1.1.4 Quy trình của DM ................................................................. 7 1.1.1.5 Các phương pháp của DM..................................................... 7 1.1.2 Khai phá dữ liệu văn bản ............................................................11 1.1.2.1 Khái niệm ............................................................................11 1.1.2.2 Các kỹ thuật khai phá văn bản..............................................13 1.2 Khai phá tri thức ứng dụng lý thuyết tập thô ...............................17 1.2.1 Khai phá tri thức theo cách tiếp cận tập thô ............................17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn b 1.2.1.1 Một số khái niệm..................................................................17 1.2.1.1.1 Hệ thống thông tin............................................................17 1.2.1.1.2. Khái niêm về bảng quyết định………………………….19 1.2.1.1.3. Khái niệm quan hệ không phân biệt được trong hệ thông tin.20 1.2.1.1.4. Khái niệm tập các nhát cắt, nhát cắt trong bảng quyết định...22 1.2.1.2. Tập thô trong không gian xấp xỉ............................................22 1.2.1.3 Khai phá tri thức theo cách tiếp cận tập thô............................25 1.2.2 Sự rời rạc hoá dữ liệu theo cách tiếp cận tập thô ........................27 1.2.3 Lựa chọn thuộc tính dựa trên tập thô ..........................................27 1.2.4 Khám phá luật bới bảng phân bố tổng quát dựa trên tập thô .......28 1.3 Kết luận chƣơng 1 ..........................................................................29 CHƢƠNG 2. MỘT SỐ PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU TRONG XỬ LÝ VĂN BẢN ................................................................................30 2.1. Biểu diễn văn bản ..........................................................................30 2.1.1. Biểu diễn văn bản ......................................................................30 2.1.2. Các phương pháp biểu diễn văn bản ..........................................30 2.1.2.1. Tiền xử lý văn bản ..............................................................30 2.1.2.2. Mô hình Logic ....................................................................32 2.1.2.3. Mô hình phân tích cú pháp .................................................34 2.1.2.4. Mô hình không gian vector .................................................35 2.1.2.5. Mô hình Boolean ................................................................36 2.1.2.6. Mô hình tần suất .................................................................37 2.1.2.7. Mô hình dựa trên tập mờ (Fuzzy Set) ..................................39 2.1.2.8. Mô hình tập thô dung sai (Tolerance Rough Set Model-TRSM) ........................................................................................................41 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn c 2.2. Các thuật toán lập nhóm văn bản .................................................43 2.2.1. Thuật toán K – Means ..............................................................43 2.2.2. Thuật toán lập nhóm theo cây phân cấp .....................................44 2.2.2.1. Thuật toán theo cây phân cấp từ trên xuống ( Top Down Hierachical Clustering) ....................................................................44 2.2.2.2. Thuật toán theo cây phân cấp từ dưới lên ( Bottom Up Hierachical Clustering) ....................................................................45 2.2.2.3. Giải thuật lập nhóm Non Hierachical Clustering Overlap ...45 2.2.2.4. Giải thuật lập nhóm Non Hierachical Clustering Non Overlap46 2.2.3. Xác định các thuật đại diện cho nhóm .......................................46 2.2.4. Độ tương tự giữa văn bản và nhóm văn bản ..............................47 2.3 Bài toán phân lớp văn bản .............................................................47 2.3.1 Bài toán ......................................................................................47 2.3.2 Các nghiên cứu liên quan ...........................................................48 2.4 Các phƣơng pháp phân lớp............................................................49 2.4.1 Phân lớp dựa trên thuật toán Naive Bayes ..................................49 2.4.2 Phương pháp K – Nearest Neighbor ( K-NN) .............................51 2.4.3 Phân lớp sử dụng Support Vector Machines (SVM) ...................52 2.5 Kết luận chƣơng 2 ..........................................................................54 CHƢƠNG 3. PHÂN LOẠI VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ ÁP DỤNG LÝ THUYẾT TẬP THÔ .........................................................55 3.1 Kiến trúc hệ thống phân loại văn bản tiếng Việt tự động ............55 3.2. Các chức năng của hệ thống .........................................................56 3.2.1 Xây dựng tập văn bản dùng cho huấn luyện ...............................56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn d 3.2.2 Xây dựng tập từ dừng, từ tầm thường .........................................56 3.2.3 Xây dựng tập thuật ngữ ..............................................................56 3.2.4 Tiền xử lý văn bản đầu vào ........................................................56 3.2.5 Huấn luyện .................................................................................57 3.2.6 Phân lớp văn bản ........................................................................61 3.3 Kết luận chƣơng 3 ..........................................................................62 CHƢƠNG 4. XÂY DỰNG HỆ THỐNG PHÂN LOẠI VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ .........................................................................63 4.1 Môi trường và nền tảng ứng dụng .................................................63 4.2 Giao diện hệ thống ........................................................................65 4.3 Kết luận chương 4 .........................................................................67 PHỤ LỤC 1. DANH SÁCH CÁC TỪ DỪNG, TỪ TẦM THƢỜNG 73 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn I LỜI CẢM ƠN Tôi xin bày tỏ lòng biết ơn đến trường Đại học Công nghệ, Đại học Thái Nguyên, Viện Công nghệ thông tin và các thầy cô giáo đã trực tiếp giảng dạy, hướng dẫn tôi trong quá trình học tập và định hướng quan trọng trong việc hình thành ý tưởng nghiên cứu. Tôi xin chân thành cảm ơn Chi bộ, BGĐ, BCH Công đoàn, Tổ Tự nhiên và cán bộ giáo viên, công nhân viên Trung tâm GDTX Thiệu Hóa đã động viên, giúp đỡ và tạo điều kiện thuận lợi cho tôi trong quá trình học tập và nghiên cứu. Đặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc GS.TS Vũ Đức Thi, người thầy đã trực tiếp hướng dẫn và giúp đỡ tôi hoàn thành luận văn tốt nghiệp. Xin được cảm ơn bố mẹ, anh chị em gia đình nội ngoại tạo điều kiện về mọi mặt để bản thân hoàn thành tốt chương trình khóa học và bảo vệ luận văn hôm nay. Mặc dù đã có nhiều cố gắng, nhưng do thời gian có hạn và bản thân còn những hạn chế nhất định nên luận văn không tránh khỏi thiếu sót. Mong nhận được các ý kiến phê bình, góp ý của Hội đồng chấm luận văn, các thầy cô giáo và đồng nghiệp để công trình nghiên cứu được hoàn chỉnh hơn. Thái Nguyên, tháng 9 năm 2011 Tác giả La Đức Dũng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn II LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là công trình do tôi tổng hợp và nghiên cứu. Trong luận văn có sử dụng một số tài liệu tham khảo như đã nêu trong phần tài liệu tham khảo. Tác giả Luận văn La Đức Dũng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn III DANH MỤC CÁC HÌNH VẼ Hình 1.1. Quy trình DM. ......................................................................... 7 Hình 1.2. Các chức năng chính của khai phá dữ liệu. .............................12 Hình 2.1. Mô tả tần suất các từ. ..............................................................32 Hình 2.2. Biểu diễn các vector văn bản trong không gian 2 chiều……...35 Hình 2.4 : Mô hình SVM. .......................................................................53 Hình 3.1. Kiến trúc hệ thống phân loại văn bản áp dụng lý thuyết tập thô.55 Hình 3.2. Quy trình tiền xử lý văn bản. ..................................................57 Hình 3.3. Thuật toán tiền xử lý văn bản. .................................................57 Hình 3.4 Cập nhật giá trị tần suất thuật ngữ............................................58 Hình 3.5. Thuật toán cập nhật trọng số cho các thuật ngữ. ......................58 Hình 3.6 Tạo lớp dung sai xấp xỉ cho các thuật ngữ. ..............................59 Hình 3.7. Thuật toán tạo lớp dung sai cho các thuật ngữ. .......................59 Hình 3.8 Sơ đồ tạo tập xấp xỉ. ................................................................60 Hình 3.9. Thuật toán tạo xấp xỉ trên và xấp xỉ dưới. ...............................60 Hình 3.10. Phân lớp văn bản. .................................................................61 Hình 3.11. Thuật toán phân lớp văn bản. ................................................62 Hình 4.1. Hệ thống phân loại văn bản tiếng Việt tự động. ....................653 Hình 4.2. Kho lưu trữ các văn bản dành cho huấn luyện.......................654 Hình 4.3 Mô tả file huấn luyện của hệ thống ........................................664 Hình 4.4. Hệ thống VLSP.....................................................................665 Hình 4.5 Bảng cơ sở dữ liệu. ................................................................675 Hình 4.6 Giao diện chính..........................................................................66 Hình 4.7. Giao diện huấn luyện................................................................66 Hình 4.8 Giao diện quy trình phân lớp………………………………….67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn IV DANH MỤC CÁC BẢNG BIỂU Bảng 1.1. Ví dụ về hệ thống thông tin………………………………………….18 Bảng 1.2. Ví dụ về bảng quyết định………………………………………...….19 Bảng 2.1. Ví dụ về mô hình logic…………………………..………………….33 Bảng 2 .2. Ví dụ về mô hình không gian vector.................................................36 Bảng 2.3. Mô tả giá trị của mô hình Boolean.....................................................37 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn V DANH MỤC CHỮ VIẾT TẮT STT Chữ viết tắt Mô tả 1 KDD Knowledge Discovery in Database 2 CSDL Cơ sở dữ liệu 3 SVM Support Vector Machine 4 DM Data Mining 5 PRE-TEXT Tiền xử lý văn bản 6 CRE-CLUS Tạo lớp dung sai 7 UP-TERM Cập nhật trọng số thuật ngữ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 LỜI MỞ ĐẦU 1. Tính cấp thiết của đề tài Với sự bùng nổ của công nghệ thông tin, trong những năm gần đây nó được áp dụng rộng rãi trong mọi lĩnh vực đời sống xã hội. Các chuyên gia cho rằng, hiện nay chúng ta đang sống trong một xã hội “rất giàu về thông tin nhưng nghèo về tri thức”. Chính vì vậy đòi hỏi phải phát triển các phương pháp khai phá, phát hiện ra những thông tin, tri thức có ích bị che lấp trong các “núi” dữ liệu phục vụ cho công việc của các nhà quản lý, các chuyên gia, từ đó thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh của các tổ chức, doanh nghiệp. Khai phá dữ liệu (Data Mining) là một lĩnh vực khoa học liên ngành mới xuất hiện gần đây nhằm đáp ứng nhu cầu này. Các kết quả nghiên cứu cùng với những ứng dụng thành công trong khai phá dữ liệu, khám phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích, đồng thời có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Hiện nay, các cơ sở dữ liệu (CSDL) cần khai phá thường có kích thước rất lớn, chẳng hạn các CSDL tin-sinh-học (Bioinformatics), CSDL đa phương tiện, CSDL giao tác, CSDL văn bản,... Các CSDL này thường chứa tới hàng ngàn thuộc tính, gây rất nhiều khó khăn cho việc khai phá, thậm chí còn làm cho nhiệm vụ khai phá trở nên bất khả thi. Vấn đề đặt ra là phải tìm cách rút gọn số thuộc tính mà không làm những thông tin cần thiết phục vụ nhiệm vụ khai phá. Khai phá dữ liệu là một lĩnh vực liên quan đến rất nhiều ngành học như hệ cơ sở dữ liệu, thống kê, trực quan hóa với nhiều cách tiếp cận, sử dụng các kỹ thuật khác nhau như mạng nơron, lý thuyết tập thô, tập mờ, biểu diễn tri thức,... Khai phá dữ liệu là bước rất quan trọng nhằm trích suất ra các thông Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 tin có giá trị, có hiệu quả tiềm ẩn trong lượng dữ liệu lớn được lưu trữ trong các cơ sở dữ liệu, kho dữ liệu. Để khai thác nguồn thông tin có hiệu quả thì các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống đang ngày càng không đáp ứng nhu cầu. Vì vậy việc nghiên cứu tổ chức khai thác dữ liệu văn bản để khám phá tri thức thông tin là vấn đề cần thiết. Xuất phát từ những lý do trên, chúng tôi chọn và nghiên cứu đề tài luận văn: “Khai phá dữ liệu văn bản bằng lý thuyết tập thô”. 2. Mục tiêu của luận văn Mục tiêu của luận văn là nghiên cứu lý thuyết tập thô phân loại văn bản tiếng Việt theo chủ đề. 3. Các đóng góp của luận văn Luận văn đã có ba đóng góp chính sau đây: - Đề xuất phương pháp: Đề tài đã đề xuất được phương pháp phân loại văn bản dựa trên lý thuyết tập thô. - Xây dựng hệ thống: Xây dựng hệ thống phân loại văn bản tiếng Việt theo chủ đề dựa trên phương pháp đã đề xuất. - Xây dựng kho ngữ liệu: Các văn bản tiếng Việt được tổng hợp từ các trang tin Việt nam http://www.vnexpress.net, http://vnbbnews.com và http://vietnamnet.vn. 4. Bố cục của luận văn Luận văn được bố cục thành 4 chương, gồm 74 trang. Chương 1 giới thiệu tổng quan về khai phá dữ liệu văn bản và lý thuyết tập thô. Chương 2 trình bày các phương pháp biểu diễn văn bản, phân nhóm và phân loại văn bản. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chương 3 trình bày kiến trúc hệ thống phân loại văn bản tự động và phương pháp phân loại văn bản áp dụng lý thuyết tập thô. Chương 4 Xây dựng hệ thống phân loại văn bản tiếng việt theo chủ đề Cuối cùng, luận văn đưa ra một số kết luận và đề xuất các hướng nghiên cứu trong tương lai. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VĂN BẢN VÀ LÝ THUYẾT TẬP THÔ Trong chương này, chúng tôi trình bày tổng quan về khai phá dữ liệu bao gồm khai phá dữ liệu văn bản, các khía cạnh khai phá dữ liệu văn bản, các chu trình khai phá và tổng quan về lý thuyết tập thô. 1.1. Khai phá dữ liệu văn bản 1.1.1. Khai phá dữ liệu 1.1.1.1. Khái niệm Trước sự phát triển không ngừng của internet dẫn đến những kho dữ liệu đã lưu trữ một lượng dữ liệu khổng lồ, trong lượng dữ liệu khổng lồ đó ẩn chứa rất nhiều những thông tin quan trọng. Tuy nhiên, trước đây người ta vẫn thường sử dụng những phương pháp thủ công mà rất khó khăn để khai phá chúng. Những thông tin quan trọng luôn thôi thúc con người tìm cách để khai phá. Còn các hệ thống kho dữ liệu chỉ nhằm làm nhiệm vụ lưu trữ dữ liệu. Cùng với sự phát triển của kỹ thuật máy tính và kỹ thuật thông tin, thông tin ngày càng được phát triển mạnh mẽ, đã vượt qua mọi khả năng phân tích thủ công của con người, cho dù hệ thống kho dữ liệu có thể nâng cao khả năng tìm kiếm, thống kê… nhưng không thể phát hiện được những mối quan hệ và những quy luật nằm bên trong dữ liệu, đồng thời cũng không thể căn cứ vào những phương pháp phân tích truyền thống được nữa. Trong một biển dữ liệu khổng lồ, làm thế nào để lấy được những thông tin có giá trị có tri thức đã trở thành một nhiệm vụ vô cùng quan trọng, Con người mong muốn loại bỏ những dữ liệu thô để chắt lọc những dữ liệu tinh, Khai phá dữ liệu DM bắt nguồn từ đây. Nó xuất hiện vào cuối những năm 80 của thế kỷ 20, từ những năm 90 nó bắt đầu khởi phát, cho tới thế kỷ 21, rất nhiều các khái niệm gần Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 đúng với nó ví dụ KDD(Knowledge Discovery in Database), phân tích dữ liệu, Data Fusion, Data warehouse… Trong lúc này, một lĩnh vực nằm trong ngành trí tuệ nhân tạo là học máy đang không ngừng phát triển. Học máy làm nâng cao tính năng của những chương trình máy tính, thu nhận được từ nhiều ngành khoa học khác nhau bao gồm: trí tuệ nhân tạo, xác suất thống kê, tâm lý học, triết học… rồi căn cứ vào những mô hình học khác nhau để đưa ra phương pháp học, ví dụ: học không giám sát, học có giám sát, mạng noron và di truyền… Cuối cùng: Data Mining là việc tiến hành xử lý, khai phá từ trong kho dữ liệu lớn, không hoàn chỉnh, nhiều nhiễu, mơ hồ, để trích rút ra những thông tin có giá trị, có tri thức. 1.1.1.2. Lịch sử nghiên cứu Khái niệm về KDD lần đầu tiên được tổ chức vào ngày 20 tháng 8 năm 1989 tại hội nghị trí tuệ nhân tạo quốc tế lần thứ 11[32] thu hút các nhà khoa học từ 69 nước trên thế giới tham gia. Từ đó tới nay, rất nhiều các chuyên gia, học giả ở nhiều quốc gia đã nghiên cứu về DM. Các hiệp hội được hình thành như ACM SIGKDD, IEEE, ICDM, SDM, PAKDD, VLDB, FSKD, MLDM… Tại Việt Nam, khoảng 10 năm trở lại đây, ngày càng có nhiều các chuyên gia nghiên cứu DM và DM cũng ngày được phát triển, nó đang là một xu thế mới trong nghiên cứu để ứng dụng vào cuộc sống. 1.1.1.3. Các khía cạnh khai phá chủ yếu Nhiệm vụ chủ yếu là phân tích dữ liệu, phân lớp, phân loại, đo lường, đo độ lệch … Phân tích kết hợp (association analysic) Khai phá luật kết hợp do Rakesh Apwal và cộng sự cùng đưa ra. Giá trị giữa 2 biến hoặc hai biến trở lên tồn tại một tính quy luật được gọi là kết hợp. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 Luật kết hợp dữ liệu là một vấn đề khá quan trọng trong kho dữ liệu, để nhằm phát hiện ra tri thức. Kết hợp được phân thành kết hợp đơn giản, kết hợp time-series và kết hợp nhân quả. Mục đích của phân tích kết hợp là tìm ra mạng kết hợp tiềm ẩn trong kho dữ liệu. Phân lớp ( clustering ) Phân lớp là căn cứ vào tính chất của dữ liệu để phân thành từng lớp khác nhau. Trong một lớp dữ liệu có nhiều đặc tính tương thích, phân lớp là căn cứ vào các đặc trưng khái quát của dữ liệu để phân chúng thành từng lớp khác nhau, ví dụ như căn cứ vào mô hình phân bố của dữ liệu, quan hệ giữa các thuộc tính của dữ liệu. Phân loại ( classification ) Phân loại là tìm ra khái niệm miêu tả của một lớp nào đó, nó đại diện cho chỉnh thể tin tức của dữ liệu, rồi dựa vào hàm miêu tả, đồng thời dùng hàm mô tả này để miêu tả mô hình dữ liệu. Thông thường, dùng mô hình cây quyết định để biểu thị. Phân loại là lợi dụng việc huấn luyện tập dữ liệu thông qua một số các thuật toán nhất định để đạt được quy tắc phân loại. Dự đoán ( predication ) Dự đoán là lợi dụng lịch sử của dữ liệu để tìm ra được quy luật biến hóa, xây dựng mô hình, đồng thời từ mô hình đó để áp dụng vào loại dữ liệu trong tương lai để tiến hành khẳng định, khẳng định quan tâm tới độ tinh và tính chuẩn xác, thông thường dùng phương sai của khẳng định để đo lường. Mô hình chuỗi thời gian (time –series) Time –series chỉ sự thông qua sự tuần tự của thời gian tìm kiếm những mô hình phát sinh. Tựa như hồi quy, nó cũng dùng để nhận biết giá trị tương lai của dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Độ lệch ( deviation) Trong độ lệch bao gồm rất nhiều tri thức, trong kho dữ liệu, dữ liệu tồn tại những khác biệt, phát hiện những khác biết trong kho dữ liệu là rất quan trọng. Độ lệch giữa kết quả quan sát được giữa giá trị trả về theo tính toán và kết quả thực tế. 1.1.1.4. Quy trình của DM Quy trình của DM theo sơ đồ như sau Đánh giá kết quả mẫu Tri thức Khai phá dữ liệu Làm sạch tiền xử lý dữ liệu Chuyển đổi dữ liệu Các mẫu Trích lọc dữ liệu Gom dữ liệu Internet Dữ liệu Dữ liệu Mục tiêu Dữ liệu qua tiền xử lý Dữ liệu đã chuyển đổi Hình 1.1. Quy trình DM (Fayyad et al., 1996). - Gom (tập hợp) dữ liệu (Gathering): Đây là bước đầu tiên trong quá trình khai phá dữ liệu, nó được khai thác trong một cơ sở dữ liệu, kho dữ liệu... - Trích lọc dữ liệu (Selection): Các dữ liệu được lựa chọn và phân chia theoo một số tiêu chuẩn nào đó. - Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu (Cleaning, Pre-processing and Preparation): Đây là giai đoạn hết sức quan trọng trong quá trình khai phá Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 dữ liệu, nó tiến hành xử lý các dữ liệu bị lỗi, dư thừa, không có giá trị và không có khả năng kết nối dữ liệu do quá trình gọm cụm không đủ tính chặt chẽ, logic thành dạng sao cho giải thuật khai phá dữ có thể hiểu được. - Chuyển đổi dữ liệu (Transformation): Các dữ liệu được chuyển đổi sang các dạng phù hợp cho quá trình xử lý - Phát hiện và trích mẫu dữ liệu (Pattern Extraction and Discovery) [21]: Chọn các thuật toán khai phá dữ liệu thích hợp khác nhau và thực hiện việc khai phá dữ liệu: Nhằm tìm được các mẫu có ý nghĩa dưới dạng biểu diễn tương ứng với ý nghĩa của nó. Thuật toán thường là các nguyên tắc phân loại, nguyên tắc kết hợp. - Đánh giá kết quả mẫu (Evaluation of Result) [21]: Giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. Đặc điểm của mẫu là phải mới mẻ, độ mới có thể được đo tương đương với độ thay đổi trong dữ liệu hoặc bằng tri thức. Thông thường độ mới của mẫu được đánh giá bằng một hàm lôgic hoặc một hàm độ đo mới, độ bất ngờ của mẫu. Mẫu còn phải có khả năng sử dụng tiềm ẩn, phải có giá trị đối với dữ liệu mới độ chính xác nhất định. Tuy nhiên không phải bất cứ dữ liệu nào cũng đều hữu ích, đôi khi nó vẫn còn những sai lệch. 1.1.1.5. Các phương pháp của DM Các kỹ thuật của DM bao gồm học máy, trí tuệ nhân tạo và thống kê học. Trí tuệ nhân tạo được áp dụng trong học máy thông qua các giải pháp của trí tuệ nhân tạo để nâng cao hiệu quả học giải quyết những vấn đề khoa học và kỹ thuật còn tồn tại. Dưới đây là một số phương thức mà khai phá dữ liệu thường dùng: Mạng noron nhân tạo (Artificial neural networks ) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Mạng noron mô tả kết cấu của bộ não người, cơ sở là mô hình MP và phương pháp học Hebb. Nó có 3 mô hình mạng thần kinh chính: (1). Mạng lan truyền tiến (mô hình học không giám sát) (2). Mạng lan truyền ngược. Giống mô hình mạng Hopfield. (3). Mạng tự tổ chức như mô hình ART, Koholon thường dùng trong trường hợp phân cụm, phân lớp … Phƣơng pháp di truyền (Genetic Algorithms) Giải thuật di truyền là áp dụng quá trình tiến hóa của sinh vật, do yếu tố cấu thành: (1). Lựa chọn (Selection):Lựa chọn cá thể trong một quần thể để lai ghép (2). Lai ghép (Crossover) Là quá trình lựa chọn 2 cá thể độc lập để lai ghép (3). Biến dị (Mutation) Là quá trình biến dị trên từng cá thể ( ví dụ 0 biến 1, 1 biến 0…) để tạo ra một cá thể mới. Giải thuật di truyền thường dùng để sản sinh ra cá thể tốt hơn ở đời sau nhằm thỏa mãn một giá trị nào đó, thông qua quá trình di truyền, lai ghép, biến dị. Giải thuật này thường dùng trong tính toán và phân loại học máy. Cây quyết định (decision trees) Cây quyết định là sử dụng những thông tin lập luận để tìm kiếm những đặc trưng trong lượng thông tin lớn để tạo thành các điểm. Trên thực tế, người ta thường sử dụng và ảnh hưởng nhiều nhất bởi cây quyết định do Qiulan nghiên cứu và phương pháp ID3. Tập thô (Rough set) Tập thô được đề xuất bởi Zdzisław I. Pawlak vào năm 1980. Tập thô mô tả một cách hình thức tính xấp xỉ của một tập rõ bằng cận xấp xỉ trên và cận Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn