Tài liệu Nghiên cứu và phát hiện các phụ thuộc hàm mở rộng trong cơ sở dữ liệu theo cách tiếp cận tập thô

ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ PHAN TRÍ TUỆ NGHIÊN CỨU VÀ PHÁT HIỆN CÁC PHỤ THUỘC HÀM MỞ RỘNG TRONG CSDL THEO CÁCH TIẾP CẬN TẬP THÔ LUẬN VĂN THẠC SĨ HÀ NỘI - 2004 2 ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ LỜI CẢM ƠN Tôi xin chân thành cảm ơn Thầy giáo PGS.TS. Hồ Thuần, người đã trực tiếp hướng dẫn tôi hoàn thành luận văn tốt nghiệp thạc sĩ, thầy giáo TS. Hà Quang Thuỵ,PHAN ngườiTRÍ đã TUỆ giúp đỡ tôi trong việc hoàn thành luận văn, và các thầy cô của Khoa Công nghệ, Đại học Quốc gia Hà nội, những người đã tạo điều kiện thuận lợi cho cá nhân tôi cũng như NGHIÊN CỨU VÀ học PHÁT những học viên khác trong quá trình tập. HIỆN CÁC PHỤ THUỘC HÀM MỞ RỘNG TRONG CSDL THEO CÁCH TIẾP CẬN TẬP THÔ Học viên Chuyên ngành: Công nghệ thông tin Mã số: 1.01.10 Phan Trí Tuệ LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. HỒ THUẦN HÀ NỘI - 2004 MỤC LỤC BẢNG KÝ HIỆU: ............................................................................................................................ 3 MỞ ĐẦU ........................................................................................................................................... 4 CHƯƠNG 1: TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC TRONG CƠ SỞ DỮ LIỆU ........ 6 1. TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC TRONG CƠ SỞ DỮ LIỆU ........................ 6 1.1. PHÁT HIỆN TRI THỨC TRONG CƠ SỞ DỮ LIỆU............................. 6 1.2. QUÁ TRÌNH PHÁT HIỆN TRI THỨC TRONG CƠ SỞ DỮ LIỆU ..... 9 1.3. MỘT SỐ VẤN ĐỀ CỦA VIỆC PHÁT HIỆN TRI THỨC TRONG CƠ SỞ DỮ LIỆU ....................................................................................................... 12 2. CÁC PHƯƠNG THỨC KHAI PHÁ DỮ LIỆU ................................................................. 14 2.1. 2.2. 3. NHỮNG NHIỆM VỤ CHÍNH CỦA KHAI PHÁ DỮ LIỆU ................ 14 CÁC THÀNH PHẦN CỦA THUẬT TOÁN KHAI PHÁ DỮ LIỆU..... 15 KẾT LUẬN ........................................................................................................................... 17 CHƯƠNG 2: LÝ THUYẾT TẬP THÔ .................................................................................. 19 1. HỆ THÔNG TIN VÀ TẬP THÔ......................................................................................... 20 1.1. MỘT SỐ KHÁI NIỆM CHUNNG ......................................................... 20 1.1.1. KHÁI NIỆM VỀ HỆ THÔNG TIN ......................................................... 20 1.2. TẬP THÔ TRONG KHÔNG GIAN XẤP XỈ ......................................... 22 1.2.1. TẬP XẤP XỈ TRÊN, XẤP XỈ DƯỚI VÀ MIỀN BIÊN ............................. 22 1.2.2. ĐỘ CHÍNH XÁC CỦA VIỆC XẤP XỈ .................................................... 24 1.2.3. HÀM THÀNH VIÊN THÔ ...................................................................... 25 1.2.4. SỰ PHỤ THUỘC GIỮA CÁC THUỘC TÍNH ...................................... 25 1.3. VẤN ĐỀ RÚT GỌN CÁC THUỘC TÍNH: ............................................ 26 1.4. CÁC LUẬT QUYẾT ĐỊNH .................................................................... 27 2. MỘT SỐ ỨNG DỤNG CỦA MÔ HÌNH TẬP THÔ ......................................................... 29 2.1. DỰ BÁO THẤT BẠI KINH DOANH .................................................... 30 2.2. NGHIÊN CỨU THỊ TRƯỜNG QUA CƠ SỞ DỮ LIỆU (DATABASE MARKETING) .................................................................................................... 32 2.3. ĐẦU TƯ TÀI CHÍNH............................................................................. 33 3. MỘT SỐ VẤN ĐỀ KHI THỰC HIỆN MÔ HÌNH TẬP THÔ ......................................... 35 3.1. 3.2. 3.3. 4. LỰA CHỌN CÁC CHỈ DẪN, THUỘC TÍNH:...................................... 35 PHÂN ĐOẠN DỮ LIỆU......................................................................... 36 KIỂM TRA THẨM ĐỊNH CÁC KẾT QUẢ: ......................................... 37 KẾT LUẬN ........................................................................................................................... 38 CHƯƠNG 3: CƠ SỞ DỮ LIỆU QUAN HỆ VÀ PHỤ THUỘC HÀM MỞ RỘNG .............. 39 1. CƠ SỞ DỮ LIỆU QUAN HỆ .............................................................................................. 39 1.1. MỘT SỐ KHÁI NIỆM CĂN BẢN ......................................................... 39 1.2. PHỤ THUỘC HÀM ................................................................................ 41 1.2.1. PHỤ THUỘC HÀM ............................................................................... 41 1.2.2. HỆ TIÊN ĐỀ ARMSTRONG CHO PHỤ THUỘC HÀM ....................... 41 2 1.2.3. KHOÁ ..................................................................................................... 42 1.3. BÀI TOÁN CHUẨN HOÁ CÁC QUAN HỆ .......................................... 43 1.3.1. CÁC DẠNG CHUẨN QUAN HỆ ........................................................... 43 1.3.2. CÁC THUẬT TOÁN CHUẨN HÓA ....................................................... 44 2. CÁC TIÊN ĐỀ CỦA ARMSTRONG TRÊN PHỤ THUỘC HÀM MỞ RỘNG THEO CÁCH TIẾP CẬN TẬP THÔ ....................................................................................................... 46 2.1. 2.2. 2.3. 2.4. 3. MỘT SỐ ĐỊNH NGHĨA ......................................................................... 46 TIÊN ĐỀ THỨ HAI CỦA ARMSTRONG ............................................ 47 TIÊN ĐỀ THỨ BA CỦA ARMSTRONG .............................................. 48 MỘT SỐ VÍ DỤ....................................................................................... 50 THUẬT TOÁN PHÁT HIỆN CÁC PHỤ THUỘC HÀM MỞ RỘNG............................ 52 3.1. MỘT SỐ ĐỊNH NGHĨA VÀ BỔ ĐỀ SỬ DỤNG TRONG THUẬT TOÁN 52 3.1.1. CÁC PHÂN HOẠCH VÀ CÁC PHỤ THUỘC ....................................... 53 3.1.2. VẤN ĐỀ TÌM KIẾM ............................................................................... 55 3.2. THUẬT TOÁN ........................................................................................ 61 3.2.1. THUẬT TOÁN CHÍNH: ......................................................................... 61 3.2.2. THỦ TỤC SINH MỨC ........................................................................... 62 3.2.3. TÍNH CÁC PHỤ THUỘC ...................................................................... 64 3.2.4. THU GỌN .............................................................................................. 65 3.2.5. TÍNH CÁC PHÂN HOẠCH ................................................................... 66 3.2.6. THỦ TỤC TÍNH SAI SỐ E..................................................................... 69 3.3. ĐÁNH GIÁ .............................................................................................. 70 4. THỬ NGHIỆM VÀ ĐÁNH GIÁ ......................................................................................... 72 4.1. XÂY DỰNG CHƯƠNG TRÌNH PHẦN MỀM ...................................... 72 4.1.1. LỰA CHỌN HỆ ĐIỀU HÀNH, CÔNG CỤ LẬP TRÌNH ...................... 72 4.1.2. MỘT SỐ YÊU CẦU ĐỐI VỚI CHƯƠNG TRÌNH PHẦN MỀM............ 72 4.2. THỬ NGHIỆM ....................................................................................... 73 4.2.1. LỰA CHỌN BÀI TOÁN THỬ NGHIỆM................................................ 73 4.2.2. QUÁ TRÌNH THỬ NGHIỆM: ................................................................ 74 4.2.3. CÁC KẾT QUẢ THỬ NGHIỆM ............................................................ 77 4.2.4. ĐÁNH GIÁ: ............................................................................................ 78 KẾT LUẬN ............................................................................................................................. 80 TÀI LIỆU THAM KHẢO ...................................................................................................... 82 TÀI LIỆU TIẾNG VIỆT ............................................................................................................... 82 TÀI LIỆU TIẾNG ANH ................................................................................................................ 82 3 BẢNG KÝ HIỆU: Chữ viết tắt Giải thích 1NF First normal form 2NF Second normal form 3NF Third normal form AFD Approximate Functional Dependency BCNF Boyce-Codd Normal Form CSDL Cơ sở dữ liệu KDD Knowledge Discovery in database 4 MỞ ĐẦU Cùng với sự phát triển của ngành Công nghệ Thông Tin, các nhà quản lý hiện nay không chỉ mong muốn có được những hệ thống cung cấp thông tin chính xác, kịp thời, mà còn mong muốn có được những hệ thống thông minh hỗ trợ họ nhiều hơn trong việc phân tích, đánh giá thông tin... Đó chính là một nguyên nhân quan trọng cho sự ra đời của lĩnh vực phát hiện tri thức trong cơ sở dữ liệu. Phát hiện tri thức trong cơ sở dữ liệu là một lĩnh vực rộng, nó bao gồm nhiều vấn đề đang được các nhà khoa học nghiên cứu xem xét. Một trong những vấn đề mà phát hiện tri thức quan tâm đến đó là phát hiện ra các mối ràng buộc có trong dữ liệu, đây chính là nội dung chính của luận văn này. Trong luận văn của mình, chúng tôi tiến hành nghiên cứu các phụ thuộc hàm mở rộng trên cơ sở tập thô, và nghiên cứu phát triển một thuật toán hiệu quả để tìm kiếm các phụ thuộc hàm này trên cơ sở cải tiến thuật toán Tane, một thuật toán được đánh giá rất cao về khả năng tìm kiếm nhanh chóng các phụ thuộc hàm trong dữ liệu. Nội dung trình bày của chúng tôi được thể hiện trong ba chương: - Chương I: trình bày các vấn đề tổng quan về phát hiện tri thức trong cơ sở dữ liệu - Chương II: trình bày các vấn đề cơ bản của tập thô và ứng dụng của nó - Chương III: trình bày các vấn đề của phụ thuộc hàm mở rộng, kiểm tra các tính chất của hệ tiên đề Armstrong trên các phụ thuộc hàm này, nghiên cứu thuật toán tìm kiếm các phụ thuộc hàm mở rộng, đề xuất cải tiến thuật toán, xây dựng chương trình thử nghiệm và đánh giá kết quả. 5 Trong phần kết luận: chúng tôi tổng kết lại kết quả đạt được của luận văn và đưa ra đề xuất về hướng phát triển của thuật toán tìm kiếm các phụ thuộc hàm mở rộng trong tương lai. 6 Chương 1. TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC TRONG CƠ SỞ DỮ LIỆU 1. 1.1. TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC TRONG CƠ SỞ DỮ LIỆU Phát hiện tri thức trong cơ sở dữ liệu Trong thập kỉ trước, loài người đã tập hợp được một khối lượng vô cùng lớn các dữ liệu trong nhiều lĩnh vực khác nhau. Bằng việc sử dụng các kỹ thuật thống kê kết hợp với các công cụ quản trị tệp, nhiều công ty đã đạt được những thành công nhất định trong việc phân tích lượng dữ liệu này. Tuy nhiên, kích cỡ của các kho dữ liệu hiện tại và tốc độ xử lý dữ liệu đòi hỏi cần phải có những cách tiếp cận mới để xử lý những dữ liệu này. Một thế hệ mới của các kỹ thuật và công cụ thông minh hỗ trợ con người trong việc phân tích, tìm kiếm tri thức đã ra đời. Những kỹ thuật, công cụ này thuộc vào một lĩnh vực đang phát triển của Công nghệ thông tin được gọi là phát hiện tri thức trong cơ sở dữ liệu (KDD). Thông thường, dữ liệu được hiểu như là một dãy các bits, hoặc các số và các ký hiệu, trong khi, tri thức được xem như là các dữ liệu tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được hiểu, có thể được phát hiện, hoặc có thể được học. Nói cách khác, tri thức có thể được coi là các dữ liệu có độ trừu tượng và tổ chức cao. Hiện tại có một số định nghĩa khác nhau về phát hiện tri thức trong cơ sở dữ liệu. Trong luận văn này, chúng tôi sử dụng định nghĩa về KDD của Frawley,v PiatetskyShapior và Matheus năm 1991. “Phát hiện tri thức trong cơ sở dữ liệu là một quá trình nhận dạng các mô hình có thể hiểu được, có lợi ích tiềm ẩn, khác thường, có giá trị trong dữ liệu”. 7 Trong đó: Hình 1: một tập dữ liệu đơn giản với 2 lớp - Dữ liệu: là một tập các nhân tố F. Trong ví dụ đưa ra trong hình 1, F bao gồm 23 trường hợp thể hiện các giá trị nợ, thu nhập, và hiện trạng cho vay. - Mẫu: là một biểu thức E trong ngôn ngữ L dùng để mô tả các yếu tố trong một tập con FE của F. E được gọi là một mô hình nếu nó đơn giản hơn so với việc liệt kê tất cả các yếu tố trong FE.. Ví dụ, mô hình “ nếu thu nhập < $t thì người đó được ngầm định là vay nợ” sẽ là một mô hình cho việc lựa chọn tương ứng của t. Mô hình này được minh hoạ trong hình 2: Nợ t$ Thu nhập Hình 2: Sử dụng ngưỡng giá trị thu nhập để phân lớp dữ liệu cho vay nợ - Quá trình: thông thường quá trình KDD là quá trình nhiều bước, nó bao gồm cả việc chuẩn bị số liệu, tìm kiếm mô hình, đánh giá tri thức, làm mịn dữ liệu sau khi hiệu chỉnh. 8 - Có giá trị: các mô hình được phát hiện có giá trị với các dữ liệu mới với độ chắc chắn tương đối. - Khác thường: các mô hình là khác bình thường. Sự khác thường có thể đo bằng sự thay đổi của dữ liệu ( bằng cách so sánh giá trị hiện tại với giá trị trong quá khứ, cũng như giá trị mong muốn). - Lợi ích tiềm ẩn: các mô hình tiềm ẩn các khả năng có ích nào đó và chúng có thể đo được bằng một hàm tiện ích. - Có thể hiểu được đầy đủ: một mục tiêu của KDD là tạo ra các mô hình có thể hiểu được để con người dễ dàng hơn trong việc nắm bắt các thông tin có trong dữ liệu. Điều này là khó để đo lường một cách tường minh, nó thường được thay thế bằng một độ đo đơn giản hơn. Hiện đang có nhiều độ đo đơn giản được sử dụng, chúng bao gồm các các độ đo thuần tuý (dựa trên kích cỡ của mô hình theo bit) cho tới ngữ nghĩa. Trên cơ sở các định nghĩa trên có thể đưa ra định nghĩa về khai phá dữ liệu và quá trình KDD - Khai phá dữ liệu là một bước trong quá trình KDD bao gồm các thuật toán khai phá dữ liệu, theo một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Lưu ý rằng, không gian các mô hình thường là hữu hạn và việc liệt kê các mô hình bao gồm cả việc tìm kiếm trong không gian này. - Quá trình KDD là một quá trình sử dụng các phương thức khai phá dữ liệu (thuật toán) để tìm ra (xác định) cái được cho rằng là tri thức theo các mô tả của các độ đo và các ngưỡng, sử dụng Cơ sở dữ liệu F với một vài tiền tiến trình xử lý, lấy mẫu, và chuyển đổi F cần thiết. 9 1.2. Quá trình phát hiện tri thức trong cơ sở dữ liệu Quá trình phát hiện tri thức bao gồm một số bước như được thể hiện trong hình3: Tìm hiểu và đánh giá Khai phá dữ liệu Thực hiện chuyển đổi Tiền xử lý dữ liệu Hình thành và định nghĩa bài toán Hình 3: Tổng quan về các bước của quá trinh KDD - Bước thứ nhất là tìm hiểu lĩnh vực ứng dụng và hình thành bài toán. Bước này có ý nghĩa quan trọng cho việc rút ra được các tri thức hữu ích và cho việc chọn các phương pháp khai phá dữ liệu thích hợp trong bước ba sao cho phù hợp với mục đích ứng dụng và bản chất của dữ liệu. - Bước thứ hai là xử lý thô, hay còn gọi là tiền xử lý dữ liệu nhằm loại bỏ các dữ liệu nhiễu hoặc các bất thường, xử lý các giá trị bị thiếu, sửa các lỗi mang tính hệ thống, tập hợp các thông tin cần thiết để mô hình hoặc tính toán nhiễu, quyết định các chiến lược xử lý các trường dữ liệu bị lỗi. - Bước thứ ba: thực hiện việc chuyển đổi phát hiện ra các đặc điểm hữu ích để biểu diễn lại dữ liệu sao cho phù hợp với mục tiêu cần đạt tới. Có thể sử dụng phương pháp rút bớt số chiều hoặc biến đổi dữ liệu để giảm bớt số lượng các biến. 10 - Bước thứ tư là khai phá dữ liệu, tức là trích ra các mẫu các mô hình ẩn trong dữ liệu. Một mô hình có thể được xem như một biểu diễn tổng thể của một cấu trúc nhằm tóm lược thành phần mang tính hệ thống có trong dữ liệu hoặc mô tả tập dữ liệu này có thể sinh sôi nảy nở ra sao. Trong khi, một mẫu là một cấu trúc cục bộ có khi chỉ liên quan tới một nhóm các biến và một số trường hợp. Các lớp chính của các phương pháp khai phá dữ liệu là mô hình dự đoán chẳng hạn như phân loại và hồi qui; phân đoạn ; mô hình phụ thuộc chẳng hạn như các mô hình đồ thị hoặc ước lượng mật độ; mô hình tóm lược, ví dụ như tìm các mối quan hệ giữa các trường, các liên kết; và mô hình thay đổi và phát hiện độ lệch trong dữ liệu và tri thức. - Bước thứ năm: tìm hiểu và đánh giá tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán, hai mục tiêu chính của các hệ thống khám phá trong thực tế. Kinh nghiệm cho thấy rằng các mẫu hoặc các mô hình phát hiện được từ các dữ liệu không phải lúc nào cũng đáng quan tâm và có thể trực tiếp sử dụng được ngay, và quy trình KDD cần phải được lặp đi lặp lại có điều chỉnh theo các tri thức đã phát hiện được. Để có thể đánh giá các luật được áp dụng trong qui trình KDD, người ta thường chia dữ liệu thành hai tập, huấn luyện trên tập thứ nhất và kiểm chứng trên tập thứ hai. Có thể lặp lại qui trình này một số lần với các phần chia khác nhau, sau đó lấy trung bình các kết quả để ước lượng các luật thi hành. Dưới đây là một số bước cơ bản trong quá trình phát hiện tri thức trong cơ sở dữ liệu: - Tìm hiểu rõ phạm vi ứng dụng: những tri thức có liên quan trước đây, các mục đích của người sử dụng, ... - Tạo lập tập dữ liệu đích: chọn ra một tập dữ liệu, hoặc tập trung vào một tập con các biến hoặc các mẫu dữ liệu mà trên đó cần phải phát hiện ra các tri thức. - Quá trình làm sạch dữ liệu: các phép cơ bản như loại bỏ nhiễu hoặc các giá trị kỳ dị nếu hợp lý, xử lý các giá trị bị thiếu, sửa các lỗi mang tính hệ thống, tập hợp các lthông tin cần thiết để mô hình hoặc tính toán nhiễu, quyết định các chiến lược xử lý các trường dữ liệu bị lỗi. 11 - Rút gọn và dự đoán dữ liệu: phát hiện ra các đặc điểm hữu ích để biểu diễn lại dữ liệu sao cho phù hợp với mục tiêu cần đạt tới. Có thể sử dụng phương pháp rút bớt số chiều hoặc biến đổi dữ liệu để giảm bớt số lượng các biến. - Lựa chọn nhiệm vụ của khai phá dữ liệu: quyết định xem mục đích của qui trình KDD này là gì: phân loại, hồi qui, hay gộp nhóm, v.v. - Lựa chọn phương pháp khai phá dữ liệu: chọn các phương pháp sẽ sử dụng để tìm các mẫu trong dữ liệu. Trong đó kể cả việc quyết định xem các mô hình nào và các tham số nào là thích hợp. - Khai phá dữ liệu: rút ra các mẫu, các mô hình: tìm kiếm các mẫu đáng chú ý dưới một dạng biểu diễn khác đi hoặc một tập các biểu diễn như vậy: các qui tắc phân loại hoặc các cây, gộp nhóm... - Phân tích ý nghĩa và đánh giá các mẫu,các mô hình, có thể quay lại xử lý một trong các bước trước đó trong trường hợp cần thiết. - Củng cố tri thức đã phát hiện được: tích hợp tri thức này vào hệ thống thực hành, hoặc tạo ra các báo cáo về nó và phân phát cho những người quan tâm. Kiểm tra lại xem tri thức này có gì trái với những tri thức đã có trước đây không. 12 1.3. Một số vấn đề của việc phát hiện tri thức trong cơ sở dữ liệu Các thuật toán khai phá dữ liệu trong KDD thường phải tiến hành tìm kiếm trên toàn bộ không gian của các dữ liệu, do đó kích cỡ của các cơ sở dữ liệu cũng là một vấn đề đáng quan tâm. Các cơ sở dữ liệu với hàng trăm trường và bảng, hàng triệu bản ghi, có dung lượng nhiều gigabyte xuất hiện trong hầu hết các đơn vị quy mô lớn. Những cơ sở dữ liệu cỡ terabyte không còn là điều quá mới lạ đối với các chuyên gia trong các lĩnh vực. Số lượng hàng triệu các bản ghi có ảnh hưởng lớn đối với tốc độ xử lý của các kỹ thuật khai phá, tuy nhiên hầu hết các thuật toán khai phá dữ liệu đều có độ phức tạp thời gian hàm mũ đối với số chiều (biến, trường) của các bảng trong cơ sở dữ liệu. Do đó, để khai phá dữ liệu trên các bảng có số lượng chiều quá lớn thực sự là vấn đề khó khăn đối với các thuật toán khai phá dữ liệu. Một tập dữ liệu có số chiều lớn không những sẽ tạo ra các khó khăn do sự tăng lên về độ lớn của không gian tìm kiếm các mô hình. Hơn nữa, nó còn làm tăng thêm nguy cơ để cho một thuật toán khai phá dữ liệu tìm phải các mẫu sai lệch. Để giải quyết vấn đề này, người ta thường sử dụng các phương pháp rút gọn số chiều của các bảng dữ liệu và sử dụng tri thức trước đó để loại bỏ các biến không có ý nghĩa. Đối với những cơ sở dữ liệu có sự thay đổi rất nhanh, độ mất ổn định cao, thì có thể dẫn tới khả năng làm cho các mẫu đã phát hiện được trong thời gian trước đây gần như không có không còn phù hợp. Ngoài ra, các biến được cho trong các cơ sở dữ liệu ứng dụng có thể đã bị sửa đổi, bị xoá, hoặc được tăng lên với các số đo mới theo thời gian. Các giải pháp có thể thực hiện được bao gồm các phương pháp tăng cường cho việc cập nhật các mẫu và sử dụng chúng để tìm kiếm chỉ các mẫu biến đổi. Đối với các cơ sở dữ liệu thương mại vấn đề dữ liệu nhiễu và thiếu được đặc biệt quan tâm, đây là một vấn đề đặc biệt nhậy cảm. Theo thống kê, tỷ lệ sai sót trong các cơ sở 13 dữ liệu thương mại có thể lên tới 20%. Các thuộc tính quan trọng có thể bị thiếu nếu cơ sở dữ liệu không được thiết kế theo xu hướng có sử dụng các phương pháp phát hiện tri thức. Các giải pháp có thể thực hiện được là sử dụng các chiến thuật thống kê thật tinh vi để nhận ra được các biến và các phụ thuộc hàm đang bị che khuất. Trong nhiều ứng dụng, một vấn đề quan trọng là tính dễ hiểu đối với người dùng. Giải pháp có thể sử dụng cho vấn đề này là sử dụng các biểu diễn bằng đồ thị, ngôn ngữ tự nhiên hay các kỹ thuật hiển thị. Các chiến lược điều chỉnh luật cũng được sử dụng để giải quyết các vấn đề liên quan, nhưng các tri thức được phát hiện có thể bị giản lược. Một hệ thống phát hiện độc lập có hiệu quả không cao mà cần phải có sự tích hợp với các hệ thống khác. Các phương pháp tích hợp điển hình là tích hợp với một hệ quản trị cơ sở dữ liệu (thông qua một giao diện hỏi đáp), tích hợp với các chương trình dạng bảng tính và các công cụ đồ thị. Một ví dụ là những hệ thống KDD tích hợp do Simousdis et al và Shen et al thực hiện. 14 2. CÁC PHƯƠNG THỨC KHAI PHÁ DỮ LIỆU Thành phần khai phá dữ liệu trong quy trình KDD chủ yếu liên quan đến việc phát hiện và liệt kê ra các mẫu từ dữ liệu. Thành phần phát hiện tri thức thực hiện việc đánh giá và phân tích ý nghĩa của các mẫu để đi tới các quyết định mẫu nào có ý nghĩa và mẫu nào không. Nó còn bao gồm việc lựa chọn các lược đồ mã hóa, tiền xử lý dữ liệu, và các phép dự đoán dữ liệu trước khi tiến hành giai đoạn khai phá dữ liệu. 2.1. Những nhiệm vụ chính của khai phá dữ liệu Hai mục đích chính của việc khai thác dữ liệu trong thực tế chính là dự đoán và mô tả. Dự đoán là việc sử dụng một số biến hoặc trường trong cơ sở dữ liệu để đoán ra các giá trị không biết hoặc sẽ có của các biến đáng chú ý khác. Việc mô tả tập trung vào tìm kiếm các mẫu mà con người có thể hiểu được để mô tả dữ liệu. Quan hệ giữa dự báo và mô tả cho các ứng dụng khai phá dữ liệu chuyên dùng rất chặt chẽ. Tuy nhiên trong trường hợp KDD, mô tả được quan tâm nhiều hơn là việc dự báo. Nó ngược lại với các ứng dụng học máy và nhận dạng mẫu (như là nhận dạng tiếng nói), mà trong đó việc dự đoán thường là mục tiêu chính. Các mục tiêu của dự đoán và mô tả được tạo thành bởi các nhiệm vụ khai phá dữ liệu chính sau: - Phân lớp: là việc học một hàm để ánh xạ (bộ phân lớp) một dữ liệu vào một trong các phân lớp đã được định nghĩa sẵn. Các ví dụ về các phương thức phân lớp thường sử dụng như là một phần của các ứng dụng khai phá tri thức, bao gồm việc phân lớp theo xu hướng của các thị trường tài chính (Apte & Hong) và nhận dạng tự động các đối tượng khả nghi trong cơ sở dữ liệu ảnh (Fayyad, Djorgovski , & Weir). - Hồi quy: là việc học một hàm ánh xạ một dữ liệu tới một giá trị dự đoán thực. Các ứng dụng hồi quy hiện có rất nhiều, ví dụ như là việc dự đoán số lượng khối gỗ trong rừng thông qua các thiết bị vi sóng cảm biến từ xa, đưa ra xác suất bệnh nhân có thể chết khi có kết quả của xét nghiệm chuẩn đoán. 15 - Nhóm gộp: là một công việc tìm kiếm để xác định một tập hữu hạn các phân loại hoặc nhóm dữ liệu. Các nhóm có thể loại trừ nhau, giao nhau hoặc phủ nhau. - Khái quát hoá bao gồm các phương thức để tìm kiếm một mô tả gọn cho một tập con dữ liệu. Ví dụ đơn giản là việc lập bảng theo ý nghĩa và độ lệch chuẩn đối với mọi trường. Các phương thức phức tạp hơn có thể là độ lệch của một vài quy tắc chung, các kỹ thuật mô phỏng đa biến và khai phá các quan hệ phụ thuộc giữa các biến. Kỹ thuật khái quát hoá thường áp dụng cho việc phân tích dữ liệu ràng buộc và sinh ra các báo cáo tự động. - Mô hình hoá sự phụ thuộc: bao gồm việc tìm mô hình để mô tả sự phụ thuộc giữa các biến. Các mô hình phụ thuộc tồn tại có hai mức: mức cấu trúc mô tả mô hình trong đó các biến là phụ thuộc cục bộ với nhau, và mức định lượng của các mô hình mô tả các các phụ thuộc sử dụng một số quy mô xác định . Ví dụ , các mạng phụ thuộc xác suất thường dùng để mô tả các khía cạnh cấu trúc hoá của mô hình và xác suất. Các mạng phụ thuộc xác suất ứng dụng nhiều trong các hệ chuyên gia về y tế, mô hình hoá bộ gien người. 2.2. Các thành phần của thuật toán khai phá dữ liệu Thông thường, có ba thành phần chính trong một thuật toán khai phá dữ liệu: biểu diễn mô hình, đánh giá mô hình và tìm kiếm. a. Biểu diễn mô hình: Biểu diễn mô hình bằng một ngôn ngữ để mô tả các mẫu được phát hiện. Nếu việc biểu diễn quá hạn chế sẽ dẫn đến mất độ chính xác của mô hình trên dữ liệu. Một vấn đề rất quan trọng là người phân tích dữ liệu phải hiểu một cách đầy đủ về các giả thiết biểu diễn và nó có thể gắn với một phương thức đặc biệt. Một điều quan trọng nữa là một người thiết kế thuật toán phải nắm một cách rõ ràng những giả thiết biểu diễn được tạo ra từ thuật toán đó. Lưu ý rằng, năng lực biểu diễn mô hình càng cao thì độ nguy hiểm từ việc quá phù hợp của kết quả học càng tăng và làm giảm độ chính xác của việc dự báo trong tương lai. Thêm vào đó, việc tìm kiếm sẽ trở nên phức tạp hơn và khả năng thể hiện của mô hình càng khó khăn. 16 b. Đánh giá mô hình: Đánh giá mô hình để xác định một mẫu (một mô hình hoặc các tham số của nó) là phù hợp với các tiêu chuẩn của quy trình KDD. Việc đánh giá độ chính xác của dự báo (tính đúng đắn) dựa trên việc kiểm tra chéo. Việc đánh giá chất lượng mô tả bao gồm độ chính xác của dự báo, sự khác thường, tính tiện ích và khả năng hiểu được của mô hình phù hợp. Các tiêu chuẩn thông kê và logic cũng có thể được sử dụng để đánh giá mô hình. c. Phương thức tìm kiếm Phương thức tìm kiếm bao gồm hai loại là tìm kiếm tham số và tìm kiếm mô hình. Trong tìm kiếm tham số, thuật toán phải tìm kiếm các tham số tối ưu theo tiêu chuẩn đánh giá mô hình đối với dữ liệu và biểu diễn mô hình cố định. Đối với những vấn đề đơn giản thì không cần thiết phải thực hiện việc tìm kiếm: các ước lượng tham số tối ưu có thể sử dụng để giải quyết trường hợp này. Thông thường, đối với nhiều mô hình, giải pháp này là không thực tế: phương pháp tham lam thường được sử dụng. Tìm kiếm mô hình thường xảy ra như là kết thúc vòng lặp của tìm kiếm tham số: việc biểu diễn mô hình bị thay đổi theo một họ các mô hình được xem xét. Đối với mỗi biểu diễn mô hình cụ thể, phương thức tìm kiếm tham số được minh hoạ để đánh giá chất lượng của mô hình tìm ra. Các phương thức tìm kiếm mô hình hướng đến việc sử dụng các kỹ thuật tìm kiếm kinh nghiệm trên không gian của các mô hình khả năng. 17 3. KẾT LUẬN Trên thực tế trong thời gian qua, rất nhiều hãng kinh doanh, các cơ quan đã tiến hành thu thập một khối lượng khổng lồ các dữ liệu trong nhiều năm. Các đơn vị, cá nhân lưu trữ các dữ liệu vì họ nghĩ rằng có thể có những thông tin quí giá nào đó đang tiềm ẩn trong chúng mà hiện thời họ chưa thể hoặc chưa biết cách khai thác. Có thể thấy rằng, hầu hết các dữ liệu này đều là những dữ liệu về một hiện tượng tự nhiên (thời tiết…) hay một hiện tượng xã hội nào đó (các chuẩn mực xã hội theo từng giai đoạn…) và những dữ liệu này thường được tập hợp một cách cẩn thận, trong một thời gian khá dài nên nó có ý nghĩa khoa học cũng như xã hội thực sự to lớn. Chính những dữ liệu này sẽ là nền tảng cho các nghiên cứu khoa học ứng dụng trong tương lai. Đặc biệt, trong lĩnh vực kinh doanh, các dữ liệu được tích luỹ này càng có ý nghĩa quan trọng, nó hàm chứa các thông tin về các thị trường, về các đối thủ, và về các khách hàng, các thông tin về sản xuất, về vận hành và các khả năng tối ưu, cũng như các giải pháp chủ yếu để cải tiến các qui trình và giải quyết các sự cố. Tuy nhiên, hiện nay chỉ có một số lượng nhỏ các dữ liệu được thu thập là luôn được phân tích, theo một số thống kê tỷ lệ này chỉ chiếm khoảng từ 5%-10% lượng dữ liệu. Còn phần lớn lượng dữ liệu còn lại được thu thập chỉ nhằm phục vụ mục tiêu đảm bảo sẽ không có gì bị bỏ qua trong các dữ liệu đó, mặc dù chi phí để thực hiện điều này là rất đáng kể đối với các doanh nghiệp, đơn vị cơ quan. Cùng với sự tiến bộ về khoa học công nghệ, lượng dữ liệu mà con người hiện nay có thể tập hợp đã trở nên quá lớn so với những cách thức phân tích cổ điển thông thường. Với những cơ sở dữ liệu lớn đến cỡ nhiều Gb, Tb, thì gần như không thể thực hiện việc đưa toàn bộ các dữ liệu đó vào bộ nhớ để tăng tốc độ xử lý, điều này là thách thức không chỉ đối với hệ thống các máy trạm, mà ngay cả đối với hệ thống các siêu máy tính. Do đó, khi các cơ sở dữ liệu ngày càng lớn lên thì khả năng hỗ trợ phân tích và ra quyết định bằng cách truy vấn truyền thống sẽ không thể thực hiện được. 18 Một nhược điểm của hệ thống quản lý thông tin thông thường là nó rất khó có thể hỗ trợ người sử dụng giải đáp những vấn đề mang tính trừu tượng ví dụ: “tìm tất cả các bản ghi trong cơ sở dữ liệu điểm thi có khả năng gian lận” hoặc giúp người sử dụng nhanh chóng phát hiện và đưa ra các quyết định quản lý kịp thời, đặc biệt là khi những người đó không chuyên về lĩnh vực thống kê. Từ thực tế đó, sự ra đời và phát triển của lĩnh vực phát hiện tri thức trong cơ sở dữ liệu (KDD) là tất yếu và thực sự cần thiết, vì KDD bao gồm một thế hệ các kỹ thuật mới và công cụ thông minh để hỗ trợ con người trong việc phân tích, tìm kiếm tri thức một cách nhanh chóng và hiệu quả trong các kho dữ liệu khổng lồ mà con người hiện có.