LUẬN VĂN:ÁP DỤNG PHưƠNG PHÁP TRÍCH CHỌN THUỘC TÍNH ĐẶC TRƯNG ĐỂ NÂNG CAO HIỆU QUẢ PHÂN LỚP KHI KHAI PHÁ DỮ LIỆU LỚN

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

Thêm vào BST

Báo xấu

295
lượt xem 112
download

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

Trong khóa luận này tôi áp dụng thuật toán di truyền (Genetic Algorithm) để bước đầu cải tiến hiệu quả phân lớp của phương pháp minimax probability machine (MPM). Phần đầu tôi xin giới thiệu tổng quan về khái niệm khai phá dữ liệu. Tiếp đó, tôi sẽ trình bày về cơ sở lý thuyết của thuật toán di truyền và phương pháp phân lớp minimax probability machine. Cuối cùng, tôi sẽ mô tả chi tiết về quá trình xây dựng hệ thống có ứng dụng thuật toán di truyền trong phân lớp minimax probability machine để chuẩn đoán bệnh...

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:ÁP DỤNG PHưƠNG PHÁP TRÍCH CHỌN THUỘC TÍNH ĐẶC TRƯNG ĐỂ NÂNG CAO HIỆU QUẢ PHÂN LỚP KHI KHAI PHÁ DỮ LIỆU LỚN

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Trần Phƣơng Nhung ÁP DỤNG PHƢƠNG PHÁP TRÍCH CHỌN THUỘC TÍNH ĐẶC TRƢNG ĐỂ NÂNG CAO HIỆU QUẢ PHÂN LỚP KHI KHAI PHÁ DỮ LIỆU LỚN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2009
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Trần Phƣơng Nhung ÁP DỤNG PHƢƠNG PHÁP TRÍCH CHỌN THUỘC TÍNH ĐẶC TRƢNG ĐỂ NÂNG CAO HIỆU QUẢ PHÂN LỚP KHI KHAI PHÁ DỮ LIỆU LỚN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hƣớng dẫn: TS. Nguyễn Hà Nam HÀ NỘI - 2009
Lời cảm ơn “Để hoàn thành khóa luận này, tôi xin gửi lời cảm ơn chân thành tới quý thầy cô trong trường Đại học Công Nghệ - ĐHQGHN đã tận tình chỉ bảo tôi trong suốt bốn năm học đại học. Tôi cũng xin cảm ơn sự hướng dẫn nhiệt tình của thầy Nguyễn Hà Nam, cùng sự giúp đỡ của anh Đặng Tất Đạt – sinh viên cao học khoa Toán Tin trường Đại học Tự Nhiên, ĐHQGHN. Tôi cũng thầm biết ơn sự ủng hộ của gia đình, bạn bè – những người thân yêu luôn luôn là chỗ dựa tinh thần vững chắc cho tôi.” Hà Nội, tháng 05 năm 2009. Sinh viên Trần Phương Nhung
Tóm tắt khóa luận Trong khóa luận này tôi áp dụng thuật toán di truyền (Genetic Algorithm) để bước đầu cải tiến hiệu quả phân lớp của phương pháp minimax probability machine (MPM). Phần đầu tôi xin giới thiệu tổng quan về khái niệm khai phá dữ liệu. Tiếp đó, tôi sẽ trình bày về cơ sở lý thuyết của thuật toán di truyền và phương pháp phân lớp minimax probability machine. Cuối cùng, tôi sẽ mô tả chi tiết về quá trình xây dựng hệ thống có ứng dụng thuật toán di truyền trong phân lớp minimax probability machine để chuẩn đoán bệnh ung thư. Mô hình phân lớp mới này sẽ được chạy thử trên một số cơ sở dữ liệu lớn và đưa ra những số liệu thống kê để có thể thấy được hiệu quả của hệ thống so với phương pháp phân lớp chỉ sử dụng minimax probability machine. 1
Mục lục Giới thiệu......................................................................................................................... 8 Chương 1: Giới thiệu về khai phá dữ liệu.................................................................... 10 Khai phá dữ liệu là gì?...................................................................................... 10 1.1. Tại sao phải tiến hành khai phá dữ liệu? ........................................................... 10 1.2. Quá trình khai phá dữ liệu ................................................................................ 11 1.3. Kiến trúc điển hình của một hệ khai phá dữ liệu ............................................... 12 1.4. Các bài toán khai phá dữ liệu điển hình ............................................................ 13 1.5. Các lĩnh vực liên quan đến khai phá dữ liệu ..................................................... 15 1.6. Các ứng dụng điển hình của khai phá dữ liệu ................................................... 15 1.7. Các thách thức với khai phá dữ liệu .................................................................. 16 1.8. Kết luận ............................................................................................................ 16 1.9. Chương 2: Trích chọn thuộc tính phù hợp .................................................................. 17 Giới thiệu ......................................................................................................... 17 2.1. Mô hình trong bài toán trích chọn ..................................................................... 18 2.2. Các mô hình trong trích chọn .................................................................... 18 2.2.1. Đánh giá hai mô hình Filter và Wrapper ................................................... 19 2.2.2. 2.2.2.1. Mô hình Filter .................................................................................... 19 2.2.2.2. Mô hình Wrapper ............................................................................... 19 Một số kỹ thuật xử lý........................................................................................ 20 2.3. Bộ sinh tập con (Feature Subset Generator) .............................................. 20 2.3.1. Bộ đánh giá tập con đặc trưng (Feature Subset Evaluator) ....................... 21 2.3.2. Thuật toán học điều khiển (Central machine learning algorithm) .............. 22 2.3.3. Kết luận ............................................................................................................ 22 2.4. 2
Chương 3: Genetic algorithms ..................................................................................... 23 3.1. Giới thiệu ........................................................................................................... 23 3.2. Động lực ............................................................................................................ 23 3.3. Thuật giải di truyền ............................................................................................ 24 3.3.1. Nội dung thuật toán ....................................................................................... 24 3.3.2. Thể hiện các giả thuyết .................................................................................. 26 3.3.3. Các toán tử di truyền ..................................................................................... 27 3.3.4. Hàm thích nghi và sự chọn lọc ....................................................................... 29 Chương 4: Minimax probability machine ................................................................... 31 4.1. Giới thiệu ........................................................................................................... 31 4.2. Nội dung thuật toán ............................................................................................ 31 4.3. Ưu điểm và nhược điểm của minimax probability machine ................................ 32 4.4. Các phiên bản cải tiến của minimax probability machine ................................... 32 4.4.1. Minimum error minimax probability machine (MEMPM) .............................. 32 4.4.2. Biased minimax probability machine (BMPM) ............................................... 34 Chương 5: Phương pháp đề nghị ................................................................................. 35 Tổng quan về phương pháp .............................................................................. 35 5.1. Mô tả phương pháp ................................................................................... 35 5.1.1. 5.1.2. Mô hình bài toán ....................................................................................... 36 Mô tả dữ liệu sử dụng ....................................................................................... 36 5.2. Các module trong hệ thống và giao diện của chương trình ................................ 37 5.3. Chi tiết các module của Genetic Algorithm ............................................... 37 5.3.1. Chi tiết các module của minimax probability machine............................... 41 5.3.2. Thực nghiệm và phân tích kết quả .................................................................... 43 5.4. 5.4.1. Phương pháp đánh giá ................................................................................... 43 5.4.2. Phân tích kết quả ........................................................................................... 44 3
5.4.2.1. Kết quả thực hiện phân lớp trên bộ dữ liệu ban đầu ................................. 44 5.4.2.2. Kết quả thực hiện phân lớp trên bộ dữ liệu giảm chiều (outData.mat) ...... 45 5.4.2.3. So sánh kết quả 4 trường hợp kiểm thử .................................................... 51 5.4.2.4. Kết luận................................................................................................... 52 Chương 6: Tổng kết ...................................................................................................... 53 4
Danh sách các hình Hình 1.1: Quá trình phát hiện tri thức trong cơ sở dữ liệu [2]. ........................................ 12 Hình 1.2: Kiến trúc điển hình của hệ thống khai phá dữ liệu [2]. .................................... 13 Hình 1.3: Tính đa/ liên ngành của khai phá dữ liệu [2]. .................................................. 15 Hình 2.1: Bốn bước cơ bản trong quá trình trích chọn các thuộc tính phù hợp [6]. ......... 17 Hình 2.2: Mô hình Filter [6] ........................................................................................... 18 Hình 2.3: Mô hình Wrapper [6] ...................................................................................... 18 Hình 3.1: Các toán tử chung cho thuật giải di truyền [20]............................................... 28 Hình 4.1: Mô tả sự khác nhau giữa MEMPM (h.1) và MPM (h.2) với cùng xác suất tiên nghiệm cho 2 lớp. [17] .................................................................................................... 34 Hình 5.1: Mô hình kết hợp thuật toán di truyền và phương pháp phân lớp MPM............ 36 Hình 5.2: 6 bước thực hiện để tìm ra chromosome tốt nhất............................................. 38 Hình 5.3: Giá trị của hàm đánh giá tại mỗi thế hệ. .......................................................... 39 Hình 5.4: Hình ảnh biểu diễn hàm đánh giá của GA tại mỗi thế hệ. ................................ 40 Hình 5.5: Kết quả quá trình tối ưu tập thuộc tính của dữ liệu ban đầu............................. 41 Hình 5.6: Giao diện kết quả của bộ phân lớp minimax probability machine. .................. 42 Hình 5.7: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 1). ................................................................................................................................... 46 Hình 5.8: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 2). ................................................................................................................................... 47 Hình 5.9: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 3). ................................................................................................................................... 49 Hình 5.10: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 4). ............................................................................................................................ 50 Hình 5.11: So sánh kết quả phân lớp trung bình trong 4 trường hợp kiểm thử và kết quả phân lớp của dữ liệu gốc. ................................................................................................ 51 5
Danh sách các bảng Bảng 3.1: Thuật giải di truyền mẫu. [20] ........................................................................ 24 Bảng 5.1: Mô tả bảng dữ liệu sử dụng (file Stomach_Full.mat) ...................................... 37 Bảng 5.2: Kết quả phân lớp trên bộ dữ liệu ban đầu ....................................................... 44 Bảng 5.3: Kết quả phân lớp trong trường hợp 1 .............................................................. 45 Bảng 5.4: Kết quả phân lớp trong trường hợp 2 .............................................................. 46 Bảng 5.5: Kết quả phân lớp trong trường hợp 3 .............................................................. 48 Bảng 5.6: Kết quả phân lớp trong trường hợp 4. ............................................................. 49 6
Bảng các từ viết tắt Biased Minimax Probability Machine BMPM Genetic Algorithm GA Genetic Algorithms G as Las Vegas LV Matlab Matrix Laboratory Minimax Probability Machine MPM Minimum Error Minimax Probability Machine MEMPM Online Analytical Processing OLAP 7
Giới thiệu Những năm gần đây, các cơ sở dữ liệu đã đem lại những lợi ích vô cùng to lớn cho con người. Song hành cùng sự phát triển nhanh chóng của công nghệ thông tin và những ứng dụng của nó trong đời sống, kinh tế và xã hội, lượng dữ liệu thu thập ngày càng nhiều theo thời gian, dẫn đến việc xuất hiện ngày càng nhiều các hệ thống cơ sở dữ liệu có kích thước lớn. Trong xã hội hiện đại, thông tin được coi như sức mạnh và là yếu tố quyết định thành công trong mọi lĩnh vực, do đó việc tìm ra thông tin hữu ích trong khối dữ liệu khổng lồ được xem như mục tiêu hàng đầu của mọi tổ chức và cá nhân. Trong khóa luận này, tôi sẽ ứng dụng kỹ thuật chọn lựa tập các thuộc tính có ích trong bài toán trích chọn để nhằm cải thiện hiệu quả phân lớp dữ liệu, là nền tảng cho hệ thống chuẩn đoán bệnh ung thư. Hệ thống này sẽ được huấn luyện với tập dữ liệu về các bệnh nhân có từ trước và khi có dữ liệu của bệnh nhân mới, hệ thống sẽ tự động đưa ra chuẩn đoán người đó có bị bệnh hay không? Tôi sử dụng phương pháp phân lớp Minimax Probability Machine (MPM) kết hợp cùng thuật toán di truyền (Genetic Algorithm) để xây dựng hệ thống này. Với mục đích làm tăng độ chính xác của quá trình phân lớp dữ liệu và giảm thời gian huấn luyện của bộ phân lớp, tôi sử dụng thuật toán di truyền để lựa chọn tập thuộc tính tốt nhất của tập dữ liệu ban đầu nhằm tìm ra bộ dữ liệu phù hợp nhất cho đầu vào của bộ phân lớp MPM. Kết quả thực nghiệm đã chứng minh rằng phương pháp phân lớp sử dụng thuật toán di truyền để tối ưu tập thuộc tính cho kết quả tốt hơn phương pháp truyền thống. Nội dung chính của khóa luận bao gồm sáu chương, với nội dung cụ thể như sau: Chương 1 tập trung mô tả về khai phá dữ liệu (data mining), giới thiệu những bài toán điển hình trong khai phá dữ liệu cũng như những ứng dụng rộng rãi của lĩnh vực này. Cuối cùng là những thách thức đặt ra cho quá trình khai phá dữ liệu. Chương 2 có nội dung chủ yếu trình bày về khái niệm trích chọn thuộc tính phù hợp, những mô hình trích chọn điển hình và một số kỹ thuật xử lý trong quá trình trích chọn. Chương 3 giới thiệu về cơ sở lý thuyết cũng như những bước thực hiện của thuật toán di truyền. Thuật toán này được sử dụng để tìm ra tập các thuộc tính phù hợp nhất với thuật toán MPM sẽ được trình bày ở chương sau. 8
Chương 4 sẽ mô tả phương pháp phân lớp minimax probability machine. Phân tích những mặt mạnh và yếu của phương pháp này để đề ra những cải tiến nhằm nâng cao hiệu quả phân lớp của minimax probability machine. Chương 5 trình bày chi tiết quá trình xây dựng mô hình dự kiến của tôi bao gồm phân lớp minimax probability machine kết hợp với thuật toán di truyền. Phần còn lại của chương dùng để mô tả quá trình đánh giá chất lượng, từ đó đưa ra những phân tích kỹ thuật và kết luận về hiệu quả của mô hình. Chương 6 tóm tắt lại những kết quả đã đạt được của khóa luận, đồng thời nêu ra những mặt còn hạn chế trong phương pháp đề nghị và những hướng nghiên cứu có thể trong tương lai nhằm cải tiến hiệu quả của phương pháp này. 9
Chương 1: Giới thiệu về khai phá dữ liệu 1.1. Khai phá dữ liệu là gì? Có khá nhiều định nghĩa về khai phá dữ liệu, nhưng định nghĩa đơn giản nhất là khai phá dữ liệu là việc trích rút thông tin hay tri thức mới và có ích từ nguồn dữ liệu khổng lồ (Frawley, Piatetski-Shapiro và Matheus) [1]. Ngoài ra, khai phá dữ liệu còn có thể hiểu là trích rút các thông tin có ích từ những dữ liệu không tường minh, hoặc trích rút lấy những thông tin không biết trước và tiềm tàng trong dữ liệu. Cũng có thể hiểu, khai phá dữ liệu là việc phân tích khảo sát một cách tỉ mỉ số lượng lớn dữ liệu bằng các phương pháp tự động hoặc bán tự động nhằm tìm ra các thông tin hay tri thức có ích. Có thể nhận xét rằng, khái niệm khai phá dữ liệu là khá rộng lớn, nhưng không phải tất cả mọi công việc liên quan đến dữ liệu đều được coi là khai phá dữ liệu, chẳng hạn như những việc xử lý truy vấn đơn giản như tra cứu một số điện thoại, hay thống kê ra những học sinh giỏi của một lớp, thì không thể coi đó là khai phá dữ liệu. Nhưng những công việc như gom nhóm các tài liệu trả về từ máy tìm kiếm theo từng ngữ cảnh thì lại được xem là khai phá dữ liệu. Chính vì sự phong phú và đa dạng này mà dẫn đến thực trạng là tồn tại một số quan niệm khác nhau về chuyên ngành nghiên cứu gần gũi nhất với lĩnh vực khai phá dữ liệu. Tài liệu này của tôi tán thành quan điểm về khai phá dữ liệu của Frawley, Piatetski-Shapiro và Matheus [1]. 1.2. Tại sao phải tiến hành khai phá dữ liệu? Trong những năm gần đây, khai phá dữ liệu trở thành một lĩnh vực nghiên cứu rộng rãi trong ngành công nghiệp thông tin, nguyên nhân chủ yếu là do khối lượng khổng lồ của dữ liệu mà con người tạo ra, đi kèm với nó là sự cần thiết của việc rút trích tri thức từ những dữ liệu đó. Thông tin và tri thức có thể được áp dụng vào nhiều lĩnh vực từ phân tích thị trường tài chính, phát hiện giả mạo, cho đến điều khiển sản xuất và nghiên cứu khoa học. Nhìn vào hai lĩnh vực sinh ra nhiều dữ liệu nhất đó là thương mại và khoa học. Trong lĩnh vực thương mại, hàng ngày hàng giờ con người đang tạo ra, thu thập và lưu trữ lại rất nhiều dữ liệu, như dữ liệu web, dữ liệu về thương mại điện tử, dữ liệu về việc thanh toán tại các cửa hàng và các dữ liệu thanh toán trong các tài khoản… Tính cạnh tranh trong 10
kinh doanh là rất cao, cho nên việc phân tích dữ liệu để cung cấp dịch vụ tốt hơn, có nhiều tiện ích cho khách hàng, và đón bắt chính xác nhu cầu của khách hàng rất quan trọng. Trong lĩnh vực khoa học, dường như lượng dữ liệu sinh ra và thu thập lại còn lớn hơn nhiều, lên tới hàng GB/giờ, chẳng hạn như dữ liệu từ vệ tinh, từ các ảnh chụp vũ trụ và từ các mô phỏng thử nghiệm khoa học. Khai phá dữ liệu giúp các nhà khoa học trong việc phân lớp dữ liệu và hỗ trợ trong việc đưa ra các quyết định. Cùng với sự phát triển của khoa học, của ngành cơ sở dữ liệu không thể không kể đến là sự phát triển của ngành công nghiệp máy tính, người ta đã tạo ra những phương tiện lưu trữ lớn hơn, những máy tính rẻ hơn, tốc độ cao hơn, trợ giúp cho quá trình thu thập dữ liệu cũng như khai phá chúng. Trong quá trình tác nghiệp, người ta thường phải đưa ra các quyết định, tuy nhiên, với lượng dữ liệu khổng lồ như thế, người ta không thể sử dụng hết, hoặc nếu muốn sử dụng thì phải mất thời gian quá nhiều, như vậy có nguy cơ đánh mất cơ hội. Do đó, việc sử dụng máy tính để khai phá dữ liệu nhằm giúp đỡ con người trong công việc càng được thúc đẩy mạnh mẽ, làm sao với các dữ liệu đã thu thập được có thể đưa ra hành động mang lại lợi ích tối đa. 1.3. Quá trình khai phá dữ liệu Ở một góc độ nào đó, khái niệm khai phá dữ liệu và khai phá tri thức nhiều khi được coi là một. Tuy nhiên, nếu xét kỹ thì khai phá dữ liệu chỉ là một khâu quan trọng trong khai phá tri thức [1]. Một quá trình phát hiện tri thức trong cơ sở dữ liệu bao gồm các giai đoạn chính sau [2]: (1) Làm sạch dữ liệu (Data Cleaning): Khử nhiễu và các dữ liệu mâu thuẫn. (2) Tích hợp dữ liệu (Data Integration): Kết hợp nhiều nguồn dữ liệu khác nhau. (3) Lựa chọn dữ liệu (Data Selection): Chắt lọc lấy những dữ liệu liên quan đến nhiệm vụ phân tích sau này. (4) Biến đổi dữ liệu (Data Transformation): Biến đổi dữ liệu thu được về dạng thích hợp cho quá trình khai phá. (5) Khai phá dữ liệu (Data Mining): Sử dụng những phương pháp thông minh để khai thác dữ liệu nhằm thu được các mẫu mong muốn. (6) Đánh giá kết quả (Pattern Evaluation): Sử dụng các độ đo để đánh giá kết quả thu được. 11
(7) Biểu diễn tri thức (Knowledge Presentation): Sử dụng các công cụ biểu diễn trực quan để biểu diễn những tri thức khai phá được cho người dùng. Đánh giá & Trình diễn Tri thức Khai phá dữ liệu Mẫu Lựa chọn & Chuyển dạng Dữ liệu chuyển Kho dữ Làm sạch & dạng liệu Tích hợp Dữ liệu Hình 1.1: Quá trình phát hiện tri thức trong cơ sở dữ liệu [2]. Quá trình này có thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa trên phản hồi từ kết quả của các giai đoạn sau. 1.4. Kiến trúc điển hình của một hệ khai phá dữ liệu Trong kiến trúc điển hình của một hệ khai phá dữ liệu (hình 1.2), các nguồn dữ liệu cho hệ thống khai phá dữ liệu bao gồm cơ sở dữ liệu, hoặc kho dữ liệu, hoặc World Wide Web, hoặc kho chứa dữ liệu kiểu bất kỳ khác, hoặc tổ hợp các kiểu dữ liệu nói trên. Cơ sở tri thức bao chứa các tri thức hiện có về miền ứng dụng, được sử dụng trong thành phần khai phá dữ liệu để tăng tính hiệu quả của thành phần này. Một số tham số của thuật toán khai phá dữ liệu tương ứng sẽ tinh chỉnh theo tri thức miền sẵn có từ cơ sở tri thức trong hệ thống. Cơ sở tri thức còn được sử dụng trong việc đánh giá các mẫu đã khai phá được xem chúng có thật sự đúng đắn hay không, trong đó có đối chứng với các tri 12
thức đã có trong cơ sở tri thức. Nếu mẫu khai phá được thực sự là hấp dẫn thì được bổ sung vào cơ sở tri thức để phục vụ cho hoạt động tiếp theo của hệ thống. Giao diện người dùng Đánh giá mẫu khai phá được Cơ sở tri thức Thành phần khai phá dữ liệu Phục vụ Cơ sở dữ liệu/ Kho dữ liệu Làm sạch, tích hợp và chọn lựa dữ liệu Kiểu kho Cơ sở dữ Kho dữ World chứa thông tin liệu liệu Wide khác Web Hình 1.2: Kiến trúc điển hình của hệ thống khai phá dữ liệu [2]. 1.5. Các bài toán khai phá dữ liệu điển hình Hai mục tiêu chủ yếu của khai phá dữ liệu là dự báo (prediction) và mô tả (description). Dự báo dùng một số biến hoặc trường trong trong cơ sở dữ liệu để dự đoán về giá trị chưa biết hoặc về giá trị sẽ có trong tương lai của các biến. Mô tả hướng tới việc tìm ra các mẫu mô tả dữ liệu. Dự báo và mô tả được thể hiện thông qua các bài toán cụ thể sau [2]:  Mô tả khái niệm (Summarization) Mục đích của bài toán là tìm ra các đặc trưng và tính chất của các khái niệm. Điển hình cho bài toán này là các bài toán như tổng quát hóa, tóm tắt, các đặc trưng dữ liệu ràng buộc. 13
 Quan hệ phụ thuộc (Dependency relationship) Một trong những vấn đề của phát hiện mối quan hệ là làm rõ ràng và nguyên nhân. Bài toán tìm luật kết hợp là một đại diện điển hình, thực hiện việc phát hiện ra mối quan hệ giữa các thuộc tính (các biến), có dạng ở phụ thuộc hàm trong cơ sở dữ liệu quan hệ.  Phân lớp (Classification)[5] Phân lớp còn được gọi là học máy có giám sát (supervised learning). Với một tập các dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật phân loại sẽ học ra bộ phân loại (classifier) dùng để phân dữ liệu mới vào trong những lớp (còn gọi là loại) đã được định trước. Một số phương pháp điển hình là cây quyết định, luật phân lớp, mạng neuron.  Phân cụm (Clustering) Phân cụm còn được gọi là học máy không giám sát (unsupervised learning), thực hiện việc nhóm dữ liệu thành các lớp mới để có thể phát hiện các mẫu phân bố. Phân cụm chỉ là bái toán mô tả hướng tới việc nhận biết một tập hữu hạn các loại hoặc các cụm để mô tả dữ liệu. Các loại (cụm) có thể rời nhau và toàn phần (tạo nên phân hoạch) hoặc chồng chéo lên nhau [3].  Phân đoạn (Segmentation) Về bản chất phân đoạn là tổ hợp của phân cụm và phân lớp, trong đó phân cụm được tiến hành trước và sau đó là phân lớp.  Hồi quy (Regression) Hồi quy là học một hàm ánh xạ dữ liệu nhằm tìm và xác định giá trị thực của một biến.  Mô hình phụ thuộc (Dependency modeling) Bài toán xây dựng mô hình phụ thuộc hướng tới việc tìm ra một mô hình mô tả sự phụ thuộc có ý nghĩa giữa các biến. Mô hình phụ thuộc gồm hai mức: mức cấu trúc của mô hình mô tả (thường dưới dạng đồ thị) và mức định lượng.  Phát hiện biến đổi và độ lệch (Change and Deviation Detection) Tập trung vào việc phát hiện hầu hết sự thay đổi có ý nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn. 14
1.6. Các lĩnh vực liên quan đến khai phá dữ liệu Khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực như thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán song song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu... Đặc biệt khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các phương pháp thống kê để mô hình dữ liệ u và phát hiện các mẫu, luật. Ngân hàng dữ liệu (Data Warehousing) và các công cụ phân tích trực tuyến (OLAP – Online Analytical Processing) cũng liên quan chặt chẽ với khai phá dữ liệu [2]. Các kỹ thuật truyền thống không còn thích hợp với các loại dữ liệu bị lỗi, bị nhiễu hay dữ liệu nhiều chiều và các hệ dữ liệu tự nhiên phân tán hay hỗn tạp. Do đó khi kết hợp với nhau, hình thành lĩnh vực mới, đó là khai phá dữ liệu. Thống kê Hệ thống cơ sở dữ liệu Khai phá Học máy Trực quan hóa dữ liệu Thuật toán Các bộ môn khác Hình 1.3: Tính đa/ liên ngành của khai phá dữ liệu [2]. 1.7. Các ứng dụng điển hình của khai phá dữ liệu Ứng dụng của khai phá dữ liệu được chia thành hai lớp chính bao gồm các ứng dụng phân tích – hỗ trợ ra quyết định và lớp các lĩnh vực ứng dụng khác.  Lớp các ứng dụng trong phân tích dữ liệu và hỗ trợ ra quyết định bao gồm các ứng dụng trong [2] [4]: - Thông tin thương mại: Phân tích dữ liệu Marketing, khách hàng; Phân tích đầu tư; Phê duyệt cho vay vốn hay phát hiện gian lận. Thông tin kỹ thuật: Điều khiển và lập trình lịch; Quản trị mạng. - 15
Bảo hiểm y tế. - Viễn thông. - Thể thao -  Lớp các lĩnh vực ứng dụng điển hình khác được kể đến là khai phá văn bản, khai phá Web, khai phá dữ liệu sinh học và khai phá dữ liệu dòng. 1.8. Các thách thức với khai phá dữ liệu  Cơ sở dữ liệu lớn.  Số chiều lớn.  Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp.  Dữ liệu bị thiếu hoặc bị nhiễu.  Quan hệ giữa các trường phức tạp.  Giao tiếp với người sử dụng và kết hợp với các tri thức đã có.  Tích hợp với các hệ thống khác [2] [4] … 1.9. Kết luận Qua các vấn đề đã trình bày, chúng ta nhận thấy với một lượng dữ liệu thực tế nhỏ và với mục đích bài toán cụ thể nhưng ta có thể tiếp cận theo nhiều hướng khác nhau của cùng một phương pháp khai phá dữ liệu và đạt được kết quả khác nhau, điều đó càng làm sáng tỏ khả năng ứng dụng thực tế to lớn đồng thời với những thách thức đối với kỹ thuật khai phá dữ liệu trong các bài toán kinh tế - xã hội và trong nhiều lĩnh vực khác. 16
Chương 2: Trích chọn thuộc tính phù hợp 2.1. Giới thiệu Trích chọn đặc trưng (Feature Selection) là phương pháp chọn ra một tập con tốt nhất từ tập các đặc trưng đầu vào bằng cách lọai bỏ những đặc trưng có rất ít hoặc không có thông tin dự đoán. Trích chọn đặc trưng có vai trò quan trọng trong việc chuẩn bị và lựa chọn dữ liệu cho quá trình khai phá dữ liệu. Nó sẽ làm giảm kích cỡ của không gian đặc trưng, loại bỏ dư thừa hay nhiễu của dữ liệu. Phương pháp này có thể tìm chính xác những tập con đặc trưng có khả năng dự đoán, do đó giúp cải thiện đáng kể kết quả thu được trong các mô hình phân lớp. Về cơ bản, quá trình trích chọn đặc trưng bao gồm bốn bước cơ bản: sinh tập con (subset generation), đánh giá tập con (subset evaluation), kiểm tra điều kiện dừng của quá trình trích chọn (stopping criterion) và kết quả (result validation). Subset Subset Subset Original Generation Evaluation Set Goodness of Subset YES NO Result Stopping Validation Criterion Hình 2.1: Bốn bước cơ bản trong quá trình trích chọn các thuộc tính phù hợp [6]. Subset generation là một thủ tục tìm kiếm. Về cơ bản, nó sinh ra một tập con của tập các đặc trưng để đánh giá. Giả sử có N đặc trưng trong tập dữ liệu gốc, thì số lượng các tập con tiềm năng là 2n. Vì một tập con tối ưu các điểm đặc trưng không phải là duy nhất nên số lượng các tập con có thể thỏa mãn là rất lớn, do đó quá trình tìm kiếm trong trích chọn đặc trưng sẽ tốn nhiều thời gian và công sức. Mỗi tập con được sinh ra cần phải được đánh giá và so sánh với những tập con tốt nhất đã được tìm thấy trước. Nếu tập con tìm thấy sau là tốt hơn thì nó sẽ được thay thế cho tập con tốt nhất trước đây. Nếu không 17