LỜI MỞ ĐẦU

Như đã biết, trong những năm gần đây công nghệ thông tin phát triển vô cùng nhanh chóng và được ứng dụng rộng rãi trong mọi lĩnh vực đời sống xã hội, nhất là trong quản lý, một lĩnh vực mà yếu tố khoa học công nghệ có tính quyết định. Sự việc đó dẫn đến sự bùng nổ thông tin, làm cho những nhà quản lý rơi vào tình trạng “ngập lụt thông tin". Chính vì vậy, 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”. Tình hình đó đò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 giấu 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 CSDL cần khai phá thường có kích thước rất lớn, chẳng hạncác CSDL tin-sinh-học (Bioinformatics), CSDL đa phương tiện, CSDL giao tác,… . 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á.

Mục đích của rút gọn thuộc tính là làm giảm số chiều của không gian thuộc tính, loại bỏ dữ liệu dư thừa, không liên quan. Rút gọn thuộc tính đóng vai trò quan trọng trong bước tiền xử lý dữ liệu cũng như trong quá trình khai phá. Kếtquả rút gọn thuộc tính ảnh hưởng trực tiếp đến hiệu quả thực hiện các nhiệm vụkhai phá: Gia tăng tốc độ, cải thiện chất lượng, tính dễ hiểu của các kết quả thu được.

Từ năm 1970 đến nay, rút gọn thuộc tính (hay còn gọi là rút gọn số chiều – Dimension reduction) đã trở thành đề tài được quan tâm bởi nhiều nhà nghiên cứu thuộc các lĩnh vực nhận dạng thống kê, học máy, khai phá dữ liệu.

Chính những lý do trên, chúng tôi chọn đề tài “Lựa chọn thuộc tính trong khai phá dữ liệu” làm đề tài nghiên cứu của mình.

Nội dung của luận văn được trình bày trong 3 chương và phần kết luận.

Chương 1: Trình bày khái quát về Khai phá dữ liệu, bao gồm: Khai phá dữ liệu là gì, quy trình khai phá, các kỹ thuật và một số ứng dụng quan trọng của khai phá dữ liệu.

Chương 2: Trình bày khái quát về nội dung, các cách tiếp cận, quy trình giải quyết vấn đề lựa chọn thuộc tính và một số ứng dụng quan trọng của lựa chọn thuộc tính.

Chương 3: Trình bày kết quả nghiên cứu một số thuật toán lựa chọn thuộc tính điển hình.

Thái nguyên, tháng 11 năm 2008.

Học viên

Trịnh Văn Hà

MỤC LỤC

Trang phụ bìa 1

Mục lục2

Lời mở đầu 4

Chương 1. KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU ..6

1.1.Tại sao phải khai phá dữ liệu..6

1.2. Quá trình khai phá dữ liệu ..7

1.3. Các phương pháp khai phá dữ liệu .9

1.4. Các loại dữ liệu có thể khai phá ..10

1.5. Các ứng dụng của khai phá dữ liệu..10

1.6. Một số thách thức đặt ra cho việc khai phá dữ liệu ..14

1.7. Tổng kết chương 1 ..15

Chương 2. KHÁI QUÁT VỀ LỰA CHỌN THUỘC TÍNH TRONG KHAI

PHÁ DỮ LIỆU 16

2.1. Rút gọn thuộc tính16

2.2. Khái quát về lựa chọn thuộc tính ..18

2.2.1. Bài toán lựa chọ thuộc tính 18

2.2.2. Đặc điểm chung của các thuật toán lựa chọn thuộc tính ..20

2.2.3. Ứng dụng của các kỹ thuật lựa chọn thuộc tính ..23

2.3. Kết luận chương 2 26

Chương 3. MỘT SỐ THUẬT TOÁN LỰA CHỌN THUỘC TÍNH ĐIỂN HÌNH 28

3.1. Các thuật toán theo cách tiếp cận filter ..28

3.1.1 Thuật toán RELIEF 28

3.1.2. Thuật toán FOCUS 31

3.1.3. Thuật toán LVF ..33

3.1.4. Thuật toán EBR ..35

3.1.5. Thuật toán SCRAP 38

3.1.6. Lựa chọn nhóm40

3.2. Các thuật toán theo cách tiếp cận wrapper42

3.3.1 Thuật toán LVW ..42

3.3.2 Thuật toán NEURALNET .43

3.3. Một số thuật toán khác ..44

3.3.1. Thuật toán Genetic 44

3.3.2. Lựa chọn thuộc tính thông qua rời rạc hóa dữ liệu .46

3.4. Kết luận chương 3 53

KẾT LUẬN ..54

Tài liệu tham khảo 56