Tài liệu ứng dụng giải thuật di truyền vào phân loại tài liệu dạng văn bản

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TRẦN THỊ THANH ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO PHÂN LOẠI TÀI LIỆU DẠNG VĂN BẢN LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH Thái Nguyên - 2012 LỜI CAM ĐOAN Tôi xin cam đoan luận văn “Ứng dụng giải thuật di truyền vào phân loại tài liệu dạng văn bản” là công trình nghiên cứu của riêng tôi dƣới sự hƣớng dẫn của PGS.TS. Bùi Thế Hồng. Toàn bộ phần mềm do chính tôi lập trình và kiểm thử. Tôi xin chịu trách nhiệm về lời cam đoan của mình. Các số liệu và thông tin sử dụng trong luận văn này hoàn toàn là trung thực. Tác giả Trần Thị Thanh i MỤC LỤC MỤC LỤC ................................................................................................................... i DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ............................................... vi DANH MỤC CÁC BẢNG....................................................................................... vii DANH MỤC CÁC HÌNH VẼ................................................................................. viii MỞ ĐẦU .....................................................................................................................1 CHƢƠNG 1: TÌM HIỂU VỀ KHAI PHÁ DỮ LIỆU ................................................3 1.1 Giới thiệu chung ................................................................................................3 1.1.1. Giới thiệu ....................................................................................................3 1.1.2. Khái niệm ...................................................................................................3 1.1.3. Đặc điểm của bài toán khai phá dữ liệu .....................................................4 1.2. Quá trình khám phá tri thức trong cơ sở dữ liệu...............................................6 1.2.1. Gom dữ liệu ................................................................................................7 1.2.2. Trích lọc dữ liệu .........................................................................................7 1.2.3. Làm sạch, tiền xử lý và chuẩn bị trƣớc dữ liệu ..........................................8 1.2.4. Chuyển đổi dữ liệu .....................................................................................9 1.2.5. Khai phá dữ liệu - Phát hiện và trích mẫu dữ liệu......................................9 1.2.6. Đánh giá kết quả mẫu ...............................................................................10 1.3. Khái quát các kỹ thuật khai phá dữ liệu .........................................................10 1.3.1. Kỹ thuật khai phá dữ liệu dự đoán ...........................................................10 1.3.1.1. Phân lớp dữ liệu ............................................................................................... 10 1.3.1.2. Hồi quy ............................................................................................................... 12 1.3.2. Kỹ thuật khai phá dữ liệu mô tả...................................................................13 1.3.2.1 Phân cụm dữ liệu ............................................................................................. 13 1.3.2.2. Tóm tắt................................................................................................................ 14 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 1.3.3. So sánh các tiếp cận khai phá dữ liệu: phân cụm - phân lớp ...................14 1.3.4. Ứng dụng phân cụm .................................................................................15 1.3.5. Ví dụ .........................................................................................................15 1.4. Ý nghĩa thực tiễn và tình hình ứng dụng ........................................................17 1.4.1. Ý nghĩa thực tiễn ......................................................................................17 1.4.2. Tình hình ứng dụng ..................................................................................18 CHƢƠNG 2: TÌM HIỂU VỀ THUẬT GIẢI DI TRUYỀN ....................................19 2.1. Tổng quan về giải thuật di truyền ...................................................................19 2.1.1. Giới thiệu ..................................................................................................19 2.1.2. Các tính chất quan trọng của giải thuật di truyền .....................................20 2.1.3. Cơ sở sinh học của giải thuật di truyền ....................................................21 2.1.4. Sơ đồ thực hiện giải thuật di truyền .........................................................21 2.1.5. Ứng dụng ..................................................................................................24 2.2. Các khái niệm chung về giải thuật di truyền ..................................................24 2.2.1. Chuỗi nhiễm sắc thể .................................................................................24 2.2.2. Các cá thể .................................................................................................25 2.2.3. Phƣơng pháp mã hóa ................................................................................25 2.2.4. Quần thể ...................................................................................................25 2.2.5. Hàm thích nghi .........................................................................................26 2.2.6. Lai ghép, đột biến, tái sinh và chọn lọc ....................................................26 2.3. Các phép toán di truyền. .................................................................................27 2.3.1. Mã hóa ......................................................................................................27 2.3.1.1 Mã hóa nhị phân ................................................................................................ 27 2.3.1.2 Mã hóa hoán vị .................................................................................................. 28 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 2.3.1.3 Mã hóa giá trị ..................................................................................................... 28 2.3.1.4 Mã hóa theo cây ................................................................................................ 28 2.3.2. Quá trình lai ghép .....................................................................................29 2.3.2.1. Lai ghép giá trị thực ........................................................................................ 29 2.3.2.2. Lai ghép giá trị nhị phân ................................................................................ 31 2.3.3. Đột biến ....................................................................................................32 2.3.3.1. Đột biến các giá trị thực................................................................................ 32 2.3.3.2 Đột biến các giá trị nhị phân .......................................................................... 33 2.3.4. Phép chọn lọc ...........................................................................................33 2.3.4.1. Phƣơng pháp chọn lọc dùng bánh xe Roulette ....................................... 33 2.3.4.2. Phƣơng pháp chọn lọc Stochastic Universal Sampling ......................... 34 2.3.4.3. Phƣơng pháp chọn lọc địa phƣơng ............................................................ 35 2.3.4.4. Phƣơng pháp lựa chọn loại bỏ .................................................................... 36 2.4. Các tham số của thuật giải di truyền ...............................................................36 2.4.1. Kích thƣớc quần thể .................................................................................36 2.4.2. Xác suất lai giống .....................................................................................37 2.4.3. Xác suất đột biến ......................................................................................37 2.4.4. Số lƣợng thế hệ .........................................................................................38 CHƢƠNG 3: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO PHÂN LOẠI ........39 TÀI LIỆU DẠNG VĂN BẢN ..................................................................................39 3.1. Phân loại văn bản ............................................................................................39 3.1.1. Khái niệm .................................................................................................39 3.1.2. Quá trình phân loại văn bản .....................................................................39 3.2. Giới thiệu bài toán phân loại văn bản .............................................................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 iv 3.3. Các phƣơng pháp biểu diễn văn bản ...............................................................41 3.3.1. Mô hình không gian vector (Vector Space Model - VSM) ......................41 3.3.2. Mô hình BOOLEAN ................................................................................43 3.3.3. Mô hình tần suất .......................................................................................44 3.3.3.1. Phƣơng pháp dựa trên tần số thuật ngữ (TF) ........................................... 44 3.3.3.2. Phƣơng pháp dựa trên nghịch đảo tần số văn bản (TDF) ..................... 45 3.3.3.3. Phƣơng pháp TF × IDF .................................................................................. 45 3.3.4. Phƣơng pháp xử lý vector thƣa ................................................................46 3.3.5 Mô hình đồ thị ...........................................................................................46 3.4. Các thuật toán phân loại văn bản ....................................................................48 3.4.1. Bộ phân loại Vector hỗ trợ (SVM) ...........................................................48 3.4.2. Phân loại văn bản và SVM .......................................................................53 3.4.3. Thuật toán k-NN (k-Nearest Neighbor) ...................................................60 3.5. Giải thuật di truyền phân loại văn bản ............................................................62 3.5.1. Lựa chọn mô hình biểu diễn văn bản .......................................................62 3.5.1.1. Biểu diễn vector của văn bản ....................................................................... 63 3.5.1.2. Phép tính độ tƣơng tự giữa hai vector ........................................................ 63 3.5.1.3. Vector trọng tâm của một nhóm văn bản .................................................. 63 3.5.1.4. Phép tính độ tƣơng tự giữa hai nhóm văn bản ......................................... 63 3.5.2. Phƣơng án tách thuật ngữ .........................................................................64 3.5.2.1. Đối với các ngôn ngữ đơn âm tiết (single-term) ..................................... 64 3.5.2.2. Đối với các ngôn ngữ đa âm tiết (multi-term) ......................................... 64 3.5.2.3. Loại nhiễu .......................................................................................................... 65 3.5.2.4. Mã hóa ký tự ..................................................................................................... 66 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 3.5.2.5. Tách từ khóa...................................................................................................... 66 3.5.2.6. Loại từ dừng (Stop Words) ........................................................................... 66 3.5.2.7. Thống kê từ khóa ............................................................................................. 66 3.5.3. Sử dụng thuật giải di truyền trích chọn từ khóa .......................................67 3.5.3.1.Giới thiệu ............................................................................................................ 67 3.5.3.2. Độ thích hợp của từ khóa .............................................................................. 67 3.5.3.3. Ứng dụng giải thuật di truyền để tối ƣu hóa độ thích nghi của từ khóa .............................................................................................................................................. 69 3.6. Cài đặt và thử nghiệm chƣơng trình ...............................................................69 KẾT LUẬN ...............................................................................................................73 TÀI LIỆU THAM KHẢO .........................................................................................74 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 vi DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT Các từ viết tắt Nghĩa tiếng anh Nghĩa tiếng việt KDD Knowledge Discovery and Data Kỹ thuật phát hiện tri thức Mining và khai phá dữ liệu VSM Vector Space Model Mô hình không gian vector VC Vapnik-Chervonenkis Kích thƣớc VC SVM Support Vector Machine Bộ phân loại Vector hỗ trợ RBF Radial Basis Functions Bộ phân loại chức năng SMO Sequential Minimal Optimization Tối ƣu hóa tuần tự cực tiểu TF term frequency Tần suất từ k-NN k-Nearest Neighbor Thuật toán k-NN WFST Weighted Finite State Transducer Mô hình WFST kết hợp mạng Noron SW Stop Words Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Loại từ dừng http://www.lrc-tnu.edu.vn vii DANH MỤC CÁC BẢNG Bảng 2.1: Biểu diễn cá thể trƣớc và sau đột biến......................................................33 Bảng 2.2: Độ thích nghi và xác suất của cá thể ........................................................34 Bảng 3.1: Vector biểu diễn văn bản 1 và văn bản 2 theo tần suất xuất hiện ............43 Bảng 3.2: Vector Boolean biểu diễn văn bản 1.........................................................44 Bảng 3.3: Các tham số tối ƣu tƣơng ứng với mỗi số lƣợng đặc trƣng. .....................58 Bảng 3.4: Độ chính xác phân loại trên mỗi lớp và trên toàn bộ ..............................58 Bảng 3.5: Một số từ dừng trong tiếng Việt ..............................................................66 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 viii DANH MỤC CÁC HÌNH VẼ Hình 1.1: Quá trình khám phá tri thức ........................................................................7 Hình 1.2: Các đƣờng biên phân loại đối với một láng giềng gần nhất ....................11 Hình 1.3: Đƣờng biên phân loại học bởi phân loại không tuyến tính .......................12 Hình 1.4: Một hồi quy tuyến tính đơn giản với tập dữ liệu vay nợ ..........................12 Hình 1.5: Một phép phân cụm đơn giản của tập dữ liệu vào 3 cụm ........................14 Hình 1.6: Phân cụm các điểm trong không gian .......................................................15 Hình 1.7: Phân cụm các ngôi nhà dựa vào khoảng cách địa lý.................................16 Hình 2.1: Giải quyết vấn đề bằng giải thuật di truyền. ............................................20 Hình 2.2: Sơ đồ giải thuật di truyền. .........................................................................22 Hình 2.3: Nguyên tắc thực hiện lai ghép chéo ..........................................................31 Hình 2.4: Nguyên tắc thực hiện lai ghép đa điểm .....................................................32 Hình 2.5: Ảnh hƣởng của quá trình đột biến ............................................................32 Hình 2.6: Quá trình chọn lọc cá thể bằng phƣơng pháp bánh xe Roulette ...............34 Hình 2.7: Quá trình chọn lọc cá thể bằng phƣơng pháp Stochastic Universal Sampling....................................................................................................................35 Hình 2.8: Mô tả các lân cận của cá thể .....................................................................35 Hình 2.9: Mô tả các lân cận của cá thể .....................................................................36 Hình 3.1: Các bƣớc nhỏ trong quá trình đánh chỉ số ................................................40 Hình 3.2: Biểu diễn các vector văn bản trong không gian chỉ có 2 thuật ngữ ..........42 Hình 3.3: Đồ thị biểu diễn văn bản ...........................................................................47 Hình 3.4. Đồ thị đồng hiện của văn bản....................................................................48 Hình 3.5. Mặt phẳng tách các mẫu dƣơng khỏi các mẫu âm ....................................49 Hình 3.8: Minh họa việc khoanh vùng k văn bản gần nhất với k = 5 .......................60 Hình 3.9: Mô hình tách từ khoá từ văn bản thô ........................................................65 Hình 3.10: Giao diện chƣơng trình chính .................................................................70 Hình 3.11: Thực hiện phân tách từng văn bản định dạng txt ....................................70 Hình 3.12: Quá trình loại bỏ các stop word có trong từng văn bản ..........................70 Hình 3.13:Thực hiện học phân lớp thể thao và pháp luật .........................................71 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 ix Hình 3.14: Trích chọn đặc trƣng theo giải thuật di truyền ........................................71 Hình 3.15: Thực hiện biểu diễn các văn bản trong từng phân lớp theo đặc trƣng đƣợc trích chọn dựa trên giaỉ thuật di truyền và biểu diễn dƣới dạng vecto thƣa ....72 Hình 3.16: Thực hiện phân loại từng văn bản theo từng thể loại..............................72 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 MỞ ĐẦU Chúng ta đang sống trong một thế giới có nền khoa học phát triển rất hiện đại. Thế kỷ 21 là thế kỷ của công nghệ thông tin nói chung và của tin học nói riêng. Đó là một trong những thành tựu vĩ đại nhất mà con ngƣời đã đạt đƣợc trong thiên niên kỷ này. Tin học giữ vai trò đặc biệt quan trọng trong các hoạt động của toàn nhân loại. Nhân loại ứng dụng tin học vào phục vụ cho nghiên cứu khoa học, cho công nghệ sản xuất, phục vụ cho nghành quản lý kinh tế, sản xuất kinh doanh, du lịch, y tế tạo điều kiện cho nền sản xuất xã hội ngày càng phát triển đồng thời giảm bớt đáng kể sức lao động của con ngƣời, đƣa mức sống con ngƣời ngày càng cao Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining) đã và đang đƣợc nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nƣớc trên thế giới. Tại Việt Nam, kỹ thuật này tƣơng đối còn mới mẻ tuy nhiên cũng đang đƣợc nghiên cứu và dần đƣa vào ứng dụng. Bƣớc quan trọng nhất của quá trình này là Khai phá dữ liệu, giúp ngƣời sử dụng thu đƣợc những tri thức hữu ích từ những cơ sở dữ liệu hoặc các nguồn dữ liệu khổng lồ khác. Lý do của điều này là sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong nhiều lĩnh vực của đời sống, kinh tế xã hội trong nhiều năm qua cũng đồng nghĩa với lƣợng dữ liệu đã đƣợc các cơ quan thu thập và lƣu trữ ngày một nhiều. Theo thống kê thì chỉ có một lƣợng nhỏ của những dữ liệu này (khoảng từ 5% đến 10%) đƣợc phân tích, trong khi số còn lại không đƣợc khai thác và vẫn tiếp tục thu thập nên rất tốn kém với ý nghĩ lo sợ rằng sẽ có cái gì đó quan trọng đã bị bỏ qua sau này có lúc cần đến nó. Mặt khác, trong môi trƣờng cạnh tranh, ngƣời ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên một khối lƣợng dữ liệu khổng lồ đã có. Với những lý do nhƣ vậy, các phƣơng pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng đƣợc. Yêu cầu thực tế đã làm phát triển một khuynh hƣớng kỹ thuật mới đó là Kỹ thuật phát hiện tri thức và khai phá dữ liệu nhƣ đã nêu trê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 2 Có nhiều phƣơng pháp tiếp cận, giải thuật nhằm ứng dụng công nghệ khai phá dữ liệu vào công tác quản lý nguồn tài liệu văn bản trong đó giải thuật di truyền là một hƣớng đi mới có nhiều ƣu điểm trong kỹ thuật tìm kiếm lời giải tối ƣu đáp ứng yêu cầu của nhiều bài toán xử lý văn bản. Luận văn cấu trúc gồm 3 chƣơng: Chƣơng 1: Chƣơng 1 chúng ta tìm hiểu tổng quan về khai phá dữ liệu, quá trình khai phá dữ liệu, các hƣớng tiếp cận và các phƣơng pháp khai phá dữ liệu. Đặc điểm của các bài toán khai phá dữ liệu và qui trình khám phá tri thức trong cơ sở dữ. Chƣơng 2: Chƣơng 2 nghiên cứu giải thuật di truyền và ứng dụng vào phân loại tài liệu dạng văn bản. Trong chƣơng này chúng ta tìm hiểu về các phép toán di truyền và các tham số của giải thuật di truyền. Quá trình phân loại văn bản, bài toán phân loại văn bản, các phƣơng pháp biểu diễn văn bản và các thuật toán phân loại văn bản. Chƣơng 3: Chƣơng 3 chúng ta sẽ cài đặt chƣơng trình thuật toán ở chƣơng 2. Ứng dụng giải thuật để tối ƣu hóa độ thích nghi của từ khóa. Luận văn này đƣợc hoàn thành dƣới sự hƣớng dẫn tận tình của PGS.TS. Bùi Thế Hồng, em xin bày tỏ lòng biết ơn chân thành của mình đối với thầy. Em xin chân thành cảm ơn các thầy, cô giáo Viện Công nghệ thông tin, Trƣờng Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên đã tham gia giảng dạy, giúp đỡ em trong suốt qúa trình học tập nâng cao trình độ kiến thức. Tuy nhiên vì điều kiện thời gian và khả năng có hạn nên luận văn không thể tránh khỏi những thiếu sót. Em kính mong các thầy cô giáo và bạn đọc đóng góp ý kiến để đề tài đƣợc hoàn thiện hơ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 1: TÌM HIỂU VỀ KHAI PHÁ DỮ LIỆU 1.1 Giới thiệu chung 1.1.1. Giới thiệu Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông tin và ngành công nghiệp phần cứng đã làm cho khả năng thu thập và lƣu trữ thông tin của các hệ thống thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó việc tin học hóa nhanh chóng các hoạt động sản xuất, kinh doanh cũng nhƣ nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lƣợng dữ liệu lƣu trữ khổng lồ. Hàng triệu CSDL đã đƣợc sử dụng trong các hoạt động sản xuất, kinh doanh, quản lý... trong đó có nhiều CSDL cực lớn. Sự bùng nổ này dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lƣợng dữ liệu khổng lồ kia thành tri thức có ích. Từ đó các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền công nghệ thông tin thế giới hiện nay. 1.1.2. Khái niệm Thuật ngữ khai phá dữ liệu ra đời vào những năm cuối của thập kỷ 1980. Theo Giáo sƣ Tom Mitchell “Khai phá dữ liệu là việc sử dụng dữ liệu l ịch sƣ̉ để khám phá những quy tắc và cải thiện nhƣ̃ng quyết đị nh trong tƣơng lai”. Với cách tiếp cận ƣ́ng dụng hơn , Tiến sỹ Fayyad đã phát biểu : “Khai phá dƣ̃ liệu , thƣờng đƣợc xem là việc khám phá tri thƣ́c trong các cơ sở dƣ̃ liệu , là một quá trình trích xuất những thông tin ẩn trƣớc đây chƣa biết và có khả năng hữu ích , dƣới dạng các quy luật , ràng buộc, quy tắc trong cơ sở dƣ̃ liệu” . Tóm lại, khai phá dƣ̃ liệu là một quá trì nh học tri thƣ́c mới tƣ̀ nhƣ̃ng dƣ̃ liệu đã thu thập đƣợc . Ngoài thuật ngữ khai phá dữ liệu còn có một số thuật ngƣ̃ khác đƣợc sƣ̉ dụng với nghĩa tƣơng đƣơng nhƣ: khai phá tri thƣ́c cơ s ở dữ liệu (Knowlegde Mining from Databases ), trích lọc dƣ̃ liệu (Knowlegde Extraction ), phân tí ch dƣ̃ liệu / mẫu (Data/Pattern Analysis ), khảo cổ dữ liệu (Data Archaeology), nạo vét dữ liệu (Data Dredging). Thực ra, Khai phá d ữ liệu là một bƣớc chính trong quá trì nh Khám phá tri thƣ́c trong CSDL (Knowlegde Discovery in Databases - KDD). 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 1.1.3. Đặc điểm của bài toán khai phá dữ liệu * Khai phá dữ liệu là giai đoạn chủ yếu của quá trình phát hiện tri thức. Nếu phát hiện tri thức là toàn bộ quá trình xuất tri thức từ CSDL thì khai phá dữ liệu là một giai đoạn chủ yếu của quá trình đó. Thông thƣờng, quá trình phát hiện tri thức từ dữ liệu phải trải qua rất nhiều giai đoạn. Có thể kể một vài giai đoạn quan trọng là: tìm hiểu lĩnh vực ứng dụng và mục đích khai phá, xác định dữ liệu liên quan và nhiệm vụ khai phá, tiền xử lý dữ liệu, chọn thuật toán khai phá và chuyển dữ liệu về dạng phù hợp, thực hiện khai phá và sau đó là tinh lọc và ứng dụng tri thức tìm đƣợc. Khai phá dữ liệu là để tìm ra các mẫu có ý nghĩa đƣợc tiến hành trên tập dữ liệu mà ta hy vọng sẽ thích hợp với nhiệm vụ khai phá hiện thời.Khai phá dữ liệu không phải là tìm kiếm từ dữ liệu trong một thời gian đủ dài để cho ra những mẫu không thực sự có ích nhƣ việc thống kê đã làm trƣớc đây. Khai phá dữ liệu thƣờng bao gồm việc thử tìm mô hình phù hợp với tập dữ liệu và tìm kiếm các mẫu từ tập dữ liệu theo mô hình đó. * Mẫu tìm được từ quá trình khai phá dữ liệu phải có tính mô tả và dự đoán. Mục đích chính của khai phá dữ liệu là chiết xuất tri thức từ dữ liệu.Những tri thức này đƣợc sử dụng cho lợi ích cạnh tranh trên thƣơng trƣờng và trong nghiên cứu khoa học.Dự đoán ở đây có nghĩa là trên cơ sở những điều đã biết trong quá khứ để dự đoán trƣớc những gì sẽ xảy ra trong tƣơng lai.Còn mô tả tập trung vào ý nghĩa hàm chứa trong mẫu tìm đƣợc và điều này là có nghĩa trong lĩnh vực ứng dụng. Các mẫu cuối cùng tìm đƣợc do khai phá dữ liệu sẽ có một trong hai hoặc cả hai tính chất này. * Khai phá dữ liệu là quá trình trong đó con người làm trung tâm. Mặc dù khai phá dữ liệu sử dụng nhiều phƣơng pháp khác nhau và với sự hỗ trợ của công cụ tin học nhƣng trong bất cứ giai đoạn nào của quá trình khai phá, con ngƣời vẫn luôn đóng vai trò quan trọng. Hệ thống không thể làm việc một cách hoàn toàn tự động mà không có sự trợ giúp của con ngƣời. 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 Thật vậy, để quá trình khai phá cho ra kết quả tốt, cần phải có sự phối hợp trợ giúp thƣờng xuyên của các chuyên gia cả về lĩnh vực tin học lẫn lĩnh vực ứng dụng.Sở dĩ có yêu cầu này là vì dữ liệu đầu vào và yêu cầu của bài toán khai phá thay đổi vô chừng.Các chuyên gia về lĩnh vực ứng dụng sẽ giúp các chuyên gia về tin học hiểu đƣợc điều họ mong muốn là gì.Sau đó, trách nhiệm của các chuyên gia tin học là biên dịch lại những yêu cầu đó để hệ thống khai phá hiểu và tìm ra đƣợc điều mà họ mong muốn. Các thông tin đầu vào cho hệ thống khai phá là rất quan trọng. Thông tin có đầy đủ, chính xác, đúng đắn và phù hợp với yêu cầu thì kết quả khai phá mới có thể giúp ích cho ngƣời dùng đƣợc. Các thông tin này chỉ có thể đƣợc cung cấp bởi các chuyên gia về lĩnh vực ứng dụng.Đó có thể là tập dữ liệu còn cần thiết, các tiêu chuẩn dùng trong quá trình tìm kiếm tri thức, cả những kinh nghiệm đƣợc biểu diễn bằng một ngôn ngữ nào đó mà hệ thống có thể hiểu đƣợc. Có thể khẳng định một điều rằng, nếu quá trình khai phá tri thức không có sự phối hợp tích cực của các chuyên gia tin học và các chuyên gia về lĩnh vực ứng dụng thì sẽ không đạt đƣợc kết quả gì cả. * Khai phá dữ liệu là quá trình tìm kiếm tri thức chỉ từ dữ liệu. Lý luận và thực tiễn thực hiện các quá trình phát hiện tri thức mà ta xét ở đây là sự tiếp thu, sử dụng và phát triển nhiều thành tựu và công cụ của các lĩnh vực đã phát triển trƣớc đó nhƣ: lý thuyết nhận dạng, hệ chuyên gia, trí tuệ nhân tạo… Dù vậy, đặc điểm cơ bản giúp phân biệt việc phát hiện tri thức với các ngành đã có từ trƣớc là phát hiện tri thức là quá trình tìm kiếm tri thức trực tiếp từ dữ liệu. Ví dụ: một hệ chuyên gia thì cơ sở tri thức đƣợc hình thành từ kinh nghiệm và kiến thức của các chuyên gia là chủ yếu. Trong khi bài toán nhận dạng dùng tập mẫu cho trƣớc… * Khai phá dữ liệu mang tính chất hướng nhiệm vụ. Khai phá phải nhằm vào việc giải quyết tốt một số nhiệm vụ đề ra nào đó.Tri thức mà ta đề cập đến trong bài toán khai phá dữ liệu là tri thức rút ra từ CSDL, thƣờng để phục vụ cho việc giải quyết một loạt các nhiệm vụ nhất định trong một 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 lĩnh vựcnhất định.Không thể có các yêu cầu cho một hệ thống phát hiện tri thức – trong đó khai phá dữ liệu là giai đoạn chủ yếu – là tìm mọi tri thức có thể có về lĩnh vực đó.Ngoài ra, mỗi lĩnh vực đều có đặc thù riêng về dữ liệu và những yêu cầu của lĩnh vực đó, sẽ không thể có một hệ thống phát hiện tri thức dùng cho mọi lĩnh vực. 1.2. Quá trình khám phá tri thức trong cơ sở dữ liệu Muốn thực hiện khai phá dữ liệu, đầu tiên phải tìm hiểu nghiệp vụ ứng dụng và xác định mục tiêu khai phá.Điều này xuất phát từ nhu cầu thực tế của những ngƣời làm trong lĩnh vực cần khai thác dữ liệu.Đó có thể là các tri thức chiết xuất đƣợc sử dụng cho lợi ích cạnh tranh trên thƣơng trƣờng hoặc các lợi ích trong nghiên cứu khoa học.Đây là một bƣớc rất quan trọng giúp định hƣớng cho toàn bộ quá trình khai phá. Có hiểu rõ vấn đề và xác định đúng đắn mục tiêu thì các bƣớc sau mới đƣợc thực hiện tốt và bài toán khai phá dữ liệu mới có thể cho kết quả tốt đƣợc. Ngoài ra, việc hiểu rõ tri thức đã có của ngƣời dùng cũng rất quan trọng vì qua đó sẽ hiểu rõ lĩnh vực ứng dụng hơn. Và những tri thức này thực sự giúp ích đƣợc rất nhiều trong khi thực hiện khai phá lẫn khi thực hiện hậu xử lý kết quả đạt đƣợc của quá trình khai phá luật nhằm lọc ra các luật thật sự giúp ích đƣợc cho ngƣời dùng. Sau khi tìm hiểu các lĩnh vực ứng dụng và xác định mục đích khai phá dữ liệu một cách đúng đắn, sẽ bƣớc vào quá trình khám phá tri thức trong cơ sở dữ liệu nhƣ hình 1.1. 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 Hình 1.1: Quá trình khám phá tri thức Bƣớc 1: Tích hợp dữ liệu, làm sạch dữ liệu, và chọn dữ liệu tạo nên 1 kho dữ liệu Bƣớc 2: Biến đổi dữ liệu thích hợp với bộ máy khai phá Bƣớc 3: Xác định nhiệm vụ khai phá dữ liệu và lựa chọn kĩ thuật khai phá, kết quả cho ta nguồn tri thức thô Bƣớc 4: Đánh giá các mẫu, dựa trên 1 số tiêu trí để tiến hành kiểm tra và lọc nguồn tri thức thu đƣợc. 1.2.1. Gom dữ liệu Tập hợp dữ liệu là bƣớc đầu tiên trong quá trình khai phá dữ liệu.Đây là bƣớc đƣợc khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. 1.2.2. Trích lọc dữ liệu Tập hợp dữ liệu từ nhiều nguồn khác nhau vào trong một cơ sở dữ liệu. +Chỉ chọn những dữ liệu cần thiết cho tiến trình khai phá 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 8 +Loại bỏ dữ liệu dƣ thừa và trùng lặp. +Phát hiện và giải quyết các mâu thuẫn trong dữ liệu. *Dữ liệu dư thừa, trùng lặp: +Một thuộc tính là thừa nếu nó có thể suy ra từ các thuộc tính khác. +Cùng một một thuộc tính có thể có nhiều tên trong các cơ sở dữ liệu khác nhau (ví dụ: năm sinh, tuổi). +Một số mẫu tin dữ liệu bị lặp lại. Cần tìm cách loại bỏ những dữ liệu dƣ thừa để tăng độ chính xác. 1.2.3. Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu Làm sạch dữ liệu là vấn đề quan trọng nhất của nhà kho dữ liệu. Các nhiệm vụ của công đoạn làm sạch dữ liệu: +Điền các giá trị còn thiếu. +Xác định các sai biệt và khử dữ liệu tạp nhiễu. +Sửa chữa các dữ liệu mâu thuẫn. -Bỏ qua các mẫu tin có giá trị thiếu: dễ nhƣng không hiệu quả, đặc biệt khi tỷ lệ giá trị thiếu của thuộc tính cao -Điền các giá trị thiếu bằng tay: không khả thi. -Điền các giá trị thiếu tự động: +Thay thế bằng hằng số chung ví dụ: “không biết” có thể thành lớp mới trong dữ liệu. +Thay thế bằng giá trị trung bình của thuộc tính. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không đƣợc “làm sạch - tiền xử lý - chuẩn bị trƣớc” thì sẽ gây nên những kết quả sai lệch nghiêm trọ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 9 Các giải thuật tiền xử lý bao gồm: a. Xử lý dữ liệu bị thiếu/mất: Các dữ liệu bị thiếu sẽ đƣợc thay thế bởi các giá trị thích hợp. b. Khử sự trùng lặp: Các đối tƣợng dữ liệu trùng lặp sẽ bị loại bỏ đi. Kỹ thuật này không đƣợc sử dụng cho các tác vụ có quan tâm đến phân bố dữ liệu. c. Giảm nhiễu: Nhiễu và các đối tƣợng tách rời khỏi phân bố chung sẽ bị loại đi khỏi dữ liệu. d. Chuẩn hóa: miền giá trị của dữ liệu sẽ đƣợc chuẩn hoá. e. Rời rạc hóa: các dữ liệu số sẽ đƣợc biến đổi ra các giá trị rời rạc. f. Rút trích và xây dựng đặc trƣng mới từ các thuộc tính đã có. g. Giảm chiều: các thuộc tính chứa ít thông tin sẽ đƣợc loại bớt. h. Kiểm tra tính toàn vẹn của dữ liệu 1.2.4. Chuyển đổi dữ liệu Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đƣa ra có thể sử dụng và điều khiển đƣợc bởi việc tổ chức lại nó tức là dữ liệu sẽ đƣợc chuyển đổi về dạng phù hợp cho việc khai phá bằng cách thực hiện các thao tác nhóm hoặc tập hợp. Thông thƣờng ngƣời ta đƣa dữ liệu về dạng chuẩn, đó là dạng nhị phân.Việc chuyển dữ liệu về dạng nhị phân không làm thay đổi thông tin của dữ liệu đầu vào. Đây có thể xem nhƣ là một cách thể hiện khác của dữ liệu ban đầu. Thực tế, có hai cách để thể hiện lại dữ liệu (dạng nhị phân và dạng số) trƣớc khi dùng nhƣ là đầu vào của thuật toán. Cách chuyển dữ liệu về dạng nhị phân nói trên sẽ làm tăng số chiều dữ liệu nhƣng bù lại thuật toán dùng để khai phá trở nên đơn giản hơn. Cách còn lại không chuyển dữ liệu về dạng nhị phân mà chuyển về dạng số, không làm thay đổi số chiều của dữ liệu nhƣng thuật toán khai phá phải xử lý dữ liệu phức tạp hơn. 1.2.5. Khai phá dữ liệu- Phát hiện và trích mẫu dữ liệu Đây là bƣớc quan trọng nhất của quá trình khám phá tri thức.Ở giai đoạn này nhiều thuật toán khác nhau đã đƣợc sử dụng để trích ra các mẫu từ dữ liệu. Thuật 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