Tài liệu Ứng dụng lý thuyết tập thô trong khai phá dữ liệu kinh tế - tài chính

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ————————— NGUYỄN VIỆT HÀ ỨNG DỤNG LÝ THUYẾT TẬP THÔ TRONG KHAI PHÁ DỮ LIỆU KINH TẾ – TÀI CHÍNH LUẬN VĂN THẠC SĨ Ngành: Công nghệ thông tin Mã số: 1.01.10 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS Hồ Thuần HÀ NỘI - 2007 1 MỤC LỤC MỤC LỤC ................................................................................................ 1 DANH MỤC CÁC TỪ VIẾT TẮT .......................................................... 2 DANH MỤC CÁC BẢNG........................................................................ 3 DANH MỤC CÁC HÌNH VẼ .................................................................. 4 MỞ ĐẦU ................................................................................................... 5 CHƢƠNG 1. TỔNG QUAN VỀ LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG TRONG PHÁT HIỆN TRI THỨC ............................................. 7 1.1. Tổng quan về khai phá dữ liệu và phát hiện tri thức ......................... 7 1.2. Một số khái niệm cơ bản ................................................................ 15 1.3. Một số vấn đề KDD trong kinh tế - tài chính .................................. 25 1.4. Tổng kết chương 1 . ....................................................................... 34 CHƢƠNG 2. PHÁT HIỆN TRI THỨC VÀ ỨNG DỤNG TRONG CÁC BÀI TOÁN KINH TẾ - TÀI CHÍNH ........................................... 35 2.1. Rời rạc hoá dữ liệu số và chuyển chuỗi thời gian vào đối tượng tập thô. ........................................................................................................ 35 2.2. Lựa chọn thuộc tính và phân lớp dựa trên quan hệ giá trị gần –VCR (valued closeness relation) .................................................................... 43 2.3. Ứng dụng tập thô trong đánh giá công ty........................................ 54 2.4. Đánh giá chính sách tín dụng của các ngân hàng ............................ 58 2.5 Đánh giá chiến lược thị trường ........................................................ 61 2.6. Nhận xét và thảo luận một số vấn đề về sử dụng lý thuyết tập thô trong ứng dụng kinh tế - tài chính ......................................................... 62 2.7. Tổng kết chương 2 ......................................................................... 64 CHƢƠNG 3. PHÁT HIỆN TRI THỨC QUA LẬP TRÌNH LOGIC QUY NẠP VÀ ỨNG DỤNG TRONG PHÁT HIỆN CÁC DẦU HIỆU TÀI CHÍNH BẤT THƢỜNG ................................................................ 65 3.1. Giới thiệu ....................................................................................... 65 3.2. Lập trình logic qui nạp (Inductive logic programming - LLP)[27] . 67 3.3. Thuật toán FOIL và FOCL [20, 21] ................................................ 68 3.4. Thuật toán MMDR ......................................................................... 73 3.5. Ứng dụng MDDR trong phát hiện các điểm bất thường ................. 77 3.6. Tổng kết chương 3 ......................................................................... 84 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ............................................. 85 TÀI LIỆU THAM KHẢO...................................................................... 87 2 DANH MỤC CÁC TỪ VIẾT TẮT AVL Attribute- value language CSDL Cơ sở dữ liệu DM Data mining DW Data ware house ILP Inductive locgic Programming KDD Knowledge Discovery in Database RDM Realtional Data Mining 3 DANH MỤC CÁC BẢNG Bảng 2.1 Một ví dụ về lựa chọn thuộc tính theo tập thô ............................... 49 Bảng 2.2 Trạng thái ban đầu cho việc lựa chọn đặc trưng............................ 50 Bảng 2.3 Lựa chọn thuộc tính từ tập {a,c,d}................................................. 50 Bảng 2.4 Các thuộc tính điều kiện ................................................................ 55 Bảng 2.5 Các thuộc tính quyết định .............................................................. 56 Bảng 2.6 Các tỷ số sử dụng trong phân tích chính sách tín dụng .................. 60 Bảng 3.1 So sánh các phương pháp dựa trên AVL và ILP logic cấp 1 .......... 66 Bảng 3.2 bảng kết quả đánh giá dự báo trên tập các luật tìm được............... 83 4 DANH MỤC CÁC HÌNH VẼ Hình 1.1 Dữ liệu thông tin, tri thức .............................................................. 8 Hình 1.2 Quá trình phát hiện tri thức trong CSDL ........................................ 9 Hình 1.3. Ví dụ phân lớp .............................................................................. 12 Hình 1.4 Ví dụ đường hồi qui tuyến tính ...................................................... 13 Hình 1.5 Ví dụ phân cụm ............................................................................. 13 Hình 2.1. Mô tả phân hoạch thuộc tính giá trị thực ....................................... 35 Hình 2.2 Mô tả hình học của phương pháp dựa trên 2 ................................. 40 Hình 2.3. Các chỉ số phù hợp và không phù hợp cho đối tượng x và luật r tương ứng với thuộc tính a1 .......................................................................... 54 Hình 2.4 Thủ tục dự báo kinh tế - tài chính sử dụng tập thô ......................... 63 Hình 3.1 Sơ đồ thuật toán MMDR................................................................ 75 Hình 3.2 Kết quả dự báo của các luật tìm được ............................................ 84 5 MỞ ĐẦU Trong những năm gần đây, mặc dù đã có nhiều công cụ hỗ trợ đắc lực cho việc thu thập, lưu trữ, khai thác dữ liệu, song với sự bùng nổ của thông tin thu thập được đã vượt ra ngoài khả năng của con người để nắm bắt và khai thác một cách hiệu quả, do vậy trong nhiều trường hợp các quyết định được đưa ra không dựa vào những thông tin hoặc dữ liệu thu thập được và chủ yếu dựa vào nhận thức, suy đoán của người ra quyết định. Bên cạnh đó những khiếm khuyết của các công cụ hỗ trợ đem lại cho người dùng tình trạng các tri thức lấy ra từ lượng dữ liệu lớn lại thiếu thông tin. Từ đó phát sinh yêu cầu tự nhiên là tìm kiếm một kỹ thuật mới có các đặc tính thông minh và khả năng tự động để hỗ trợ con người chắt lọc thông tin hữu ích trong một khối dữ liệu lớn. Xuất phát từ những thực tiễn đó, mặc dù lý thuyết tập thô được khởi xướng từ thập niên tám mươi của thế kỷ trước, song ngày càng được ứng dụng một cách rộng rãi trong việc phát hiện tri thức, phân tích quyết định, quy luận quy nạp và nhận dạng mẫu. Nó dường như cũng đặc biệt quan trọng cho các hệ thống trợ giúp quyết định và khai phá dữ liệu. Thực tế đây là một cách tiếp cận mới cho việc phân tích dữ liệu. Từ những vấn đề đó, nội dung đề tài này tập trung vào những vấn đề cơ bản của lý thuyết tập thô và những ứng dụng của nó trong các bài toán kinh tế, trong cơ sở dữ liệu thị trường, và trong việc tìm kiếm các yếu tố bất thường trong lĩnh vực tài chính ngân hàng. Mục tiêu nhiệm vụ và phạm vi nghiên cứu Nắm vững cơ sở lý thuyết, các khái niệm cơ bản, khái quát về các phương pháp ứng dụng lý thuyết tập thô trong khai phá dữ liệu; nghiên cứu mô hình tập thô trong các bài toán kinh tế: phương pháp, mô hình phân tích lượng dữ liệu lớn trên cơ sở lý thuyết tập thô, với các ví dụ điển hình của ứng dụng lý thuyết tập thô để giải quyết các vấn để hỗ trợ quyết định 3 lĩnh 6 vực: đánh giá công ty, chính sách tài chính của ngân hàng, chiến lược thị trường. Tìm hiểu ứng dụng mô hình tập thô trong nghiên cứu thị trường qua cơ sở dữ liệu, khám phá các yếu tố, các điểm bất thường trong lĩnh vực tài chính sử dụng lập trình suy luận quy nạp. Bố cục luận văn - Chương 1: Trình bày tổng quan về khai phá dữ liệu và phát hiện tri thức, giới thiệu khái niệm, nhiệm vụ chính của khai phá dữ liệu và phát hiện tri thức. Trình bày chi tiết về lý thuyết tập thô bao gồm: hệ thống thông tin, quan hệ không phân biệt được, xấp xỉ tập, rút gọn và lõi của tập các thuộc tính, hàm thành viên thô, độ chính xác và chất lượng xấp xỉ. Giới thiệu một số vấn đề về khai phá dữ liệu - phát hiện tri thức trong lĩnh vực kinh tế tài chính. - Chương 2 : Trình bày ứng dụng cách tiếp cận tập thô trong dự báo kinh tế - tài chính, bao gồm: lựa chọn và rời rạc hoá các thuộc tính giá trị dạng số, hệ thống thông tin biểu thị thời gian, chuyển đổi chuỗi thời gian vào các đối tượng tập thô, chuỗi dẫn xuất, lựa chọn các thuộc tính để qui nạp luật quyết định dựa trên tập thô, quá trình phân lớp các đối tượng mới theo các luật quyết định dựa trên quan hệ giá trị gần – VCR, giới thiệu ứng dụng trong 3 bài toán kinh tế: đánh giá công ty, đánh giá chính sách tín dụng và chiến lược thị trường. - Chương 3 : Tập trung tìm hiểu phương pháp khai phá dữ liệu quan hệ dựa trên lập trình logic qui nạp (ILP). Giới thiệu mô hình khai phá dữ liệu quan hệ, luật và logic cấp 1, các thuật toán khai phá dữ liệu quan hệ FOIL, FOCL, và thuật toán MMDR để khám phá các yếu tố bất thường trong lĩnh vực kinh tế. 7 Chƣơng 1 TỔNG QUAN VỀ LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG TRONG PHÁT HIỆN TRI THỨC 1.1. Tổng quan về khai phá dữ liệu và phát hiện tri thức 1.1.1 Những tiến bộ trong công nghệ CSDL [2] Nhu cầu tích luỹ và xử lý các dữ liệu nảy sinh trong mọi công việc, trong mọi hoạt động của con người, trong mọi vấn đề từ kỹ thuật, kinh tế xã hội đến hoạt động quản lý. Thập niên 1960 gắn liền với các sản phẩm đầu tiên của hệ quản trị tệp, xuất hiện bộ nhớ ngoài, như là bộ nhớ trong lý tưởng [2]. Giữa những năm 60, thế hệ đầu của hệ quản trị cơ sở dữ liệu đánh dấu bằng việc phân rõ, mô tả những dữ liệu của chương trình ứng dụng và ngôn ngữ truy nhập bên trong, bằng các lệnh hỏi phi thủ tục, người ta có thể truy nhập dữ liệu, tìm đến các bản ghi thay vì phải đi theo cấu trúc lưu trữ vật lý của dữ liệu (Hệ QTCSDL mạng). Thập niên 1970, mô hình dữ liệu quan hệ, cài đặt hệ quản trị CSDL quan hệ. Mô hình quan hệ giúp đơn giản hoá việc truy nhập dữ liệu của người sử dụng bên ngoài. Thập niên 1980, xuất hiện hệ QTCSDL quan hệ, các mô hình dữ liệu nâng cao (quan hệ mở rộng, hướng đối tượng, suy diễn, v.v.) và các hệ quản trị CSDL hướng ứng dụng (không gian, khoa học, cộng nghệ, vv..). Từ thập niên 1990 - những năm 2000: khai phá dữ liệu (data mining) và kho dữ liệu (data warehouse), cơ sở dữ liệu đa phương tiện, cơ sở dữ liệu web . 1.1.2. Dữ liệu, Thông tin và Tri thức [14 ]  Dữ liệu (data): Chúng ta thường thu thập và nhìn thấy hàng ngày, ví dụ: một chuỗi các bit, các con số, kí tự, biểu tượng, hay một đối tượng,... 8  Thông tin (Information): Là “dữ liệu” đã được loại bỏ các phần dư thừa, không cần thiết. Thông tin mô tả các đặc trưng, thuộc tính của “dữ liệu” với chi phí nhỏ nhất.  Tri thức (Knowledge) : o Là sự tích hợp các “thông tin” bao gồm cả quan hệ, là sự đúng đàn đã được kiểm nghiệm, là sự khám phá, sự hiểu biết,... o Nói cách khác tri thức có thể được xem như dữ liệu ở mức cao của của quá trình trừu tượng hóa và khái quát hoá. 1.1.3. Khai phá dữ liệu và phát hiện tri thức Nếu cho rằng các điện tử và các sóng diện từ chính là bản chất của công nghệ điện tử truyền thống thì dữ liệu, thông tin và tri thức hiện dang là tiêu điểm của một lĩnh vực mới trong nghiên cứu và ứng dụng về phát hiện tri thức (Knowledge Discovery) và khai phá dữ liệu (Data Mining) [3]. Phát hiện tri trong cơ sở dữ liệu thức (Knowledge discovery in Database - KDD) là tiến trình nhận diện các dạng/các mô hình cơ bản hiểu được, có giá trị, mới lạ, nhiều tiềm năng hữu ích. Khai phá dữ liệu (Data mining) là một bước trong tiến trình phát hiện tri thức, bao gồm một số thuật toán khai phá dữ liệu cụ thể theo một vài giới hạn tính toán chấp nhận được, nhằm tìm ra các dạng, các mô hình trong dữ liệu [14, 20, 311]. Nói cách khác, mục tiêu của phát hiện tri thức và khai phá dữ liệu là tìm ra các 9 dạng các mô hình quan tâm chứa đựng trong cơ sở dữ liệu mà được che dấu ở giữa các tập lớn dữ liệu. Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy (regularities) trong tập dữ liệu. Thuật ngữ khai phá dữ liệu (data mining) ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lượng lớn các dữ liệu thô. Có nhiều thuật ngữ hiện được dùng cũng có nghĩa tương tự với từ data mining như knowledge mming (khai phá tri thức), knowledge extraction (chắt lọc tri thức), data/pattern analysis (Phân tích dữ liệu/mẫu), data archaeology (khảo cồ dữ liệu), data dredging (nạo vét dữ liệu). Hiện nay, thuật ngữ khai phá dữ liệu (data mining) được dùng quá quen thuộc và người ta thường đồng nhất với thuật ngữ Knowledge Discovery in Databases (KDD). Còn các nhà thống kê thì xem khai phá dữ liệu như là một qui trình phân tích được thiết kế để thăm dò một lượng cực lớn các dữ liệu nhằm phát hiện ra các mẫu thích hợp và/hoặc các mối quan hệ mang tính hệ thống giữa các biến và sau đó sẽ hợp thức hoá các kết quả tìm được bằng cách áp dụng các mẫu đã phát hiện được cho các tập con mới của dữ liệu. Qui trình này bao gồm ba giai đoạn cơ bản: thăm dò, xây dựng mô hình hoặc định nghĩa mẫu, hợp thức/kiểm chứng [3]. 10  Trích chọn dữ liệu: chọn lọc dữ liệu từ các nguồn dữ liệu nhằm phục vụ mục đích khai phá tri thức theo những tiêu chí xác định. Ví dụ, từ CSDL về bán hàng, ta chọn ra các dữ liệu về khách hàng, đơn đặt hàng, hoá đơn,  Tiền xử lý: làm sạch và làm giàu dữ liệu. Làm đầy đủ dữ liệu, xử lý nhiễu, những vấn đề không nhất quán, v.v. Ví dụ, một khách hàng có thể được lưu ở nhiều bản ghi có thể có những tên, địa chỉ khác nhau, cần phải chỉnh sửa để đảm bảo nhất quán và chính xác về khách hàng đó. Những dữ liệu khác nhau về khuôn dạng, đơn vị đo lường, v.v. cần phải có những qui định thống nhất và cách chuyển về một dạng chung.  Biến đổi dữ liệu: thực hiện bước mã hoá dữ liệu và chạy các chương trình tiện ích nhằm tự động hoá việc kết xuất, biến đổi và di chuyển dữ liệu để khai phá dữ liệu .  Khai phá dữ liệu: thực hiện phân tích và ra quyết định. Đây là bước áp dụng các kỹ thuật khai thác để khai phá, trích chọn ra các mẫu tin, những mối quan hệ đặc biệt trong kho.  Biểu diễn tri thức và đánh giá: các kết quả khai thác được có thể tổng hợp dưới dạng các báo cáo nhằm hỗ trợ cho trợ giúp quyết định. Các dạng biểu diễn thường là phải trực quan, dưới dạng đồ hoạ, cây, bảng biểu, hay các luật v.v 1.1.4. Các bước của quá trình khai phá dữ liệu Các giải thuật khai phá dữ liệu thường được miêu tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây, thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong 11 bộ nhớ mà còn vì khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích được. Quá trình xử lý khai phá dữ liệu bắt đầu bằng cách xác định chính xác vấn đề cần giải quyết. Sau đó sẽ xác định các dữ liệu liên quan dùng để xây dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật khai phá dữ liệu có thể hiểu được. Về lý thuyết thì có vẻ rất đơn giản nhưng khi thực hiện thì đây thực sự là một quá trình rất khó khăn, gặp phải rất nhiều vướng mắc như: các dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản lý tập các tệp, các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi), v.v. Có rất nhiều các giải thuật khai phá dữ liệu thực hiện dựa trên những thống kê tóm tắt khá đơn giản của CSDL, khi mà toàn bộ thông tin trong CSDL là quá dư thừa đối với mục đích của việc khai phá dữ liệu. Bước tiếp theo là chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ liệu để tìm được các hình mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó (thường được biểu diễn dưới dạng các luật xếp loại, cây quyết định, luật sản xuất, biểu thức hồi quy, .. ). Đặc điểm của mẫu là phải mới (ít nhất là đối với hệ thống đó). Độ mới có thể được đo tương ứng với độ thay đổi trong dữ liệu bằng cách so sánh các giá trị hiện tại với các giá trị trước đó hoặc các giá trị mong muốn), hoặc bằng tri thức (mối liên hệ giữa phương pháp tìm mới và phương pháp cũ như thế nào). Thường thì độ mới của mẫu được đánh giá bằng một hàm logic hoặc hàm đo độ mới, độ bất ngờ của mẫu. Ngoài ra, mẫu phải có khả năng sử dụng tiềm tàng. Các mẫu này sau khi được xử lý và diễn giải phải dẫn đến những hành động có ích nào đó được đánh giá bởi một hàm lợi ích.Với các giải thuật và các nhiệm vụ của khai phá dữ liệu rất 12 khác nhau, dạng của mẫu chiết xuất được cũng rất da dạng. Dạng của mẫu chiết xuất được có thể được phân loại bởi kiểu mẫu dữ liệu mà nó mô tả. Kỹ thuật khai phá dữ liệu thực chất không có gì mới. Nó là sự kế thừa, kết hợp và mở rộng của các kỹ thuật cơ bản đã được nghiên cứu từ trước như học máy, nhận dạng, thống kê (hồi quy, xếp loại, phân cụm), các mô hình đồ thị, mạng Bayes, trí tuệ nhân tạo, thu thập tri thức hệ chuyên gia, v.v . . . Tuy nhiên, với sự kết hợp tài tình của khai phá dữ liệu, kỹ thuật này có ưu thế hơn hẳn các phưng pháp trước đó, đem lại nhiều triển vọng trong việc ứng dụng phát triển nghiên cứu khoa học cũng như làm tăng mức lợi nhuận trong các hoạt động kinh doanh. 1.1.5. Nhiệm vụ chính của khai phá dữ liệu [14, 31] Rõ ràng mục đích của khai phá dữ liệu là các tri thức chiết xuất sẽ được sử dụng cho lợi ích cạnh tranh trên thương trường và các lợi ích trong nghiên cứu khoa học. Do đó, ta có thể coi mục đích chính của khai phá dữ liệu là mô tả (description) và dự đoán (prediction). Các hình mẫu mà khai phá dữ liệu phát hiện được nhằm vào các mục đích này. Dự đoán liên quan đến việc sử dụng các biến hoặc các trường trong cơ sở dữ liệu để chiết xuất ra các hình mẫu là các dự đoán những giá trị chưa biết hoặc những giá trị trong tương lai của các biến quan tâm. Mô tả tập trung vào việc tìm kiếm các hình mẫu mô tả dữ liệu mà con người có thể hiểu được. Để đạt được hai mục đích này, nhiệm vụ chính của khai phá dữ liệu bao gồm như sau [14, 31] Phân lớp (Classification): - Phân lớp là việc tự học một hàm, hàm này ánh xạ (hay phân loại) một mục dữ liệu vào một trong số các lớp đã xác định trước (Hand 1981; Weiss & Kulilowski 1992) . 13 Hình 1.3 miêu tả đầu ra của nhiệm vụ khai phá dữ liệu phân lớp đối với tập dữ liệu khách hàng đã nêu trên. Đó là một mẫu chia tập dữ liệu khách hàng thành hai miền tuyến tính. - Hồi qui (Regression): Hồi qui là việc tự học một hàm, hàm này ánh xạ một mục dữ liệu thành một biến dự đoán có giá trị thực. Có rất nhiều các ứng dụng khai phá dữ liệu với nhiệm vụ hồi quy. Hình 1.4 miêu tả mẫu kết quả dự đoán tổng dư nợ của khách hàng với nhiệm vụ khai phá dữ liệu là hồi quy. Đường hồi quy tuyến tính cho thấy với những khách hàng có thu nhập càng cao thì tổng dư nợ càng lớn. Mẫu kết quả này không phù hợp với quy luật và điều đó là dễ hiểu vì ta thấy đường hồi quy tuyến tính ở đây không vét cạn được hết các trường hợp xảy ra mà chỉ mô tả được mối liên hệ của một số rất ít khách hàng. - Phân cụm (Clustering): Là việc mô tả chung để tìm ra các tập xác định các cụm hay các loại để mô tả dữ liệu (Titterington, Smith & Makov 1985, Jain & Dules 1988). Các cụm có thể tách riêng nhau hoặc phân cấp hoặc gối lên nhau. Có nghĩa là một dữ liệu có thể vừa thuộc cụm này và vừa thuộc cụm kia. 14 Hình 1.5 miêu tả các mẫu của quá trình khai phá dữ liệu với nhiệm vụ phân cụm. Ở đây, các mẫu là các nhóm khách hàng được xếp thành ba nhóm gối lên nhau. Liên quan chặt chẽ đến việc phân cụm là nhiệm vụ đánh giá mật độ xác suất, bao gồm các kỹ thuật đánh giá dữ liệu, hàm mật độ xác suất đa biến liên kết của tất cả các biến/các trường trong cơ sở dữ liệu (Silvemlan 1986). - Tổng kết hoá (summarization): Liên quan đến các phương pháp tìm kiếm một mô tả tóm tắt cho một tập con dữ liệu. Ví dụ như việc lập bảng các độ lệch chuẩn và trung bình cho tất cả các trường. Các phương pháp phức tạp hơn liên quan đến nguồn gốc của các luật tổng kết (Agrawal et al), khai thác mối liên hệ hàm giữa các biến (Zembowicz & Zytkow). Các kỹ thuật tổng kết thường được áp dụng cho các phân tích dữ liệu tương tác có tính thăm dò và tạo báo cáo tự động. - Mô hình hoá phụ thuộc (Dependency Modeling): Bao gồm việc tìm kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa các biến, các thành phần, phát hiện sự phụ thuộc giữa các thuộc tính. Các mô hình phụ thuộc tồn tại dưới hai mức: mức cấu trúc của mô hình xác định (thường ở dạng đồ hoạ) các biến nào là phụ thuộc cục bộ với nhau, mức định lượng của một mô hình xác định độ mạnh của sự phụ thuộc theo một độ đo nào đó. - Phát hiện sự thay đổi và chệch hƣớng (Change and Deviation Detection): Tập trung vào khai thác những thay đổi đáng kể nhất trong dữ liệu từ các giá trị chuẩn hoặc được đo trước đó (Bemdt & Cliffort; Guyon et., Kloesgen; Matheus et al., Basseville & Nikiforov 1993). Vì những nhiệm vụ khác nhau này yêu cầu số lượng và các dạng thông tin rất khác nhau nên chúng thường ảnh hưởng đến việc thiết kế và chọn giải thuật khai phá dữ liệu khác nhau. Ví dụ như giải thuật cây quyết định tạo ra được một mô tả phân biệt được các mẫu giữa các lớp nhưng không có các tính chất và đặc điểm của lớp. 15 1.2. Một số khái niệm cơ bản Khái niệm lý thuyết tập thô (rough sets theory) được Zdzislaw Pawlak [18,34] đề xuất vào đầu những năm 1980 và đã nhanh chóng trở thành một công cụ toán học mới mẻ để xử lý thông tin mơ hồ và không chắc chắn. Lý thuyết tập thô dựa trên việc giả sử rằng mọi đối tượng trong vũ trụ đều gắn với một thông tin nào đó (như dữ liệu, tri thức) – tương phản với cách tiếp cận cổ điển, ở đó tập được định nghĩa một cách duy nhất bởi các phân tử của nó mà không có thông tin thêm nào về các phần tử của tập. Rõ ràng, với một số phần tử, thông tin như giống nhau có thể được kết hợp và do đó các phần tử có thể không phân biệt được trong khuôn khổ thông tin có sẵn. Như vậy; quan hệ không phân biệt được là vấn đề then chốt của lý thuyết tập thô. Người ta nhận ra rằng tính mơ hồ và tính không chắc chắn liên quan mạnh mẽ với tính không phân biệt được và có thể xác định trên cơ sở của lý thuyết tập thô. 1.2.1. Hệ thống thống tin [18] Trong lý thuyết tập thô, các hệ thống thông tin được sử dụng để mô tả tri thức. Một hệ thống thông tin là một bộ T : (U, A) bao gồm : U- là một tập hữu hạn, không rỗng được gọi là tập vũ trụ (universe) A - Một tập hữu hạn, không rỗng các thuộc tính A = C  D, C  D = , trong đó : C là tập các thuộc tính điều kiện, D là tập các thuộc tính quyết định. Với mỗi thuộc tính q  A liên kết với một tập Vq các giá trị của nó được gọi là miền (domain) của thuộc tính q. Các đối tượng có thể được diễn giải như là các thể hiện, trạng thái, tiến trình, người bệnh và các quan sát. Các thuộc tính có thể được diễn giải như là các đặc trưng, các biến, và các điều kiện tiêu biểu. Một trường hợp đặc biệt của các hệ thống thông tin là bảng quyết định (decision table) hay bảng giá trị thuộc tính (attribute- value table). Trong một bảng quyết định, 16 các hàng tương ứng với các đối tượng còn các cột tương ứng với các thuộc tính. Một bảng quyết định có dạng T : (U, A, d), trong đó, d  A là thuộc tính quyết định và A là tập các thuộc tính điều kiện. 1.2.2. Quan hệ không phân biệt được. Cho một hệ thống thống tin T (U, A), bất kỳ một tập con B của A, xác định một quan hệ tương đương IND(B) trên U được gọi là quan hệ không phân biệt được IND(B) : {(x, y)  U x U:  a  B, a(x) = a(y)} a(x) ký hiệu giá trị thuộc tính a với mỗi phần tử x. IND(B) được gọi là B-quan hệ không phân biệt được. Nếu (x,y)  IND(B), thì các đối tượng x và y là không phân biệt được với nhau bởi các thuộc tính trong B. Quan hệ tương đương IND(B) chia tập vũ trụ thành một họ các lớp tương đương. Họ này, tức là phân hoạch xác định bởi B, sẽ được ký hiệu U/IND(B), hay đơn giản là U/B. Các lớp tương đương của B-quan hệ không biệt được được ký hiệu là [x]B hoặc B(x) . 1.2.3. Xấp xỉ tập Do tính mơ hồ luôn tồn tại trong dữ liệu thế giới thực, luôn có sự xung đột giữa các đối tượng trong một bảng quyết định, ở đây các đối tượng xung đột đề cập đến 2 hay nhiều đối tượng mà không phân biệt được bằng cách sử dụng bất kỳ tập thuộc tính điều kiện nào, tuy vậy chúng lại thuộc về các lớp quyết định khác nhau. Các đối tượng như vậy gọi là không nhất quán. Bảng quyết định này gọi là bảng quyết định không nhất quán. Trong lý thuyết tập thô, khái niệm xấp xỉ tập được đưa ra để giải quyết với tính không nhất quán. Cho T = (U, A) là một hệ thống thông tin và B  A, X  U. Chúng ta có thể xấp xỉ X sử dụng chỉ các thông tin chứa trong B bằng cách xây dựng B-xấp xỉ dưới (B- lower approximation) và B-xấp xỉ trên (B-upper approximation) của X, ký hiệu là BX và BX tương ứng như sau: BX = {x  U : [x]B  X} 17 B X = {x  U : [x]B  X  } xấp xỉ dưới tương ứng với các luật chắc chắn, trong khi đó xấp xỉ trên lại tương ứng với các qui luật có thể xảy ra (các luật với độ tin cậy lớn hơn 0) với X. Xấp xỉ dưới X là tập tất cả các đối tượng có thể có thể được phân lớp chắc chắn vào X sử dụng các thuộc tính trong B. Tập U - X được gọi là Bmiền ngoài của X và bao gồm những đối tượng có thể phân lớp chắc chắn không thuộc vào X sử dụng những thuộc tính trong B . Tập BNB(X) = X X được gọi là B - Vùng biên của X, nó bao gồm những đối tượng mà trên cơ sở các thuộc tính trong B chúng ta không thể phân lớp vào X. Một tập được cho là thô (tương ứng với Rõ) đối với B nếu vùng biên BNB(X) là không rỗng (ngược lại là Rõ). - Các tính chất của xấp xỉ tập [18] (1). B(X)  X  B(X) (2). B()  B() = ,  B(U) = U (3). B(X  Y) = B(X) B(Y) (4). B (X  Y) = B(X) B(Y) (5). X  Y kéo theo B(X) B(Y)và B(X)  B(Y) (6). B (X  Y)  B(X)  B(Y) (7).B(X  Y)  B(X)  B(Y) (8). B(-X) = -B (X) (9).B(-X) = - B(X) . (10) B(B(X)) =B(B(X))= B(X) (11) B ( B (X)) = B ( B (X)) = B (X) Ở đây, ký hiệu: -X biểu thị cho U - X Dễ dàng thấy rằng, xấp xỉ dưới và xấp xỉ trên của một tập tương ứng là phần trong và bao đóng của tập này trong tôpô hình học được phát sinh ra bởi quan hệ không phân biệt được. - Người ta chia tập thô thành 4 loại cơ bản tức là 4 loại mơ hồ [9] 18 + X là B- định nghĩa thô được, B(x)   và B (X)  U, + X là B- không định nghĩa được bên trong nếu, B(x) =  và B (X)  U + X là B- không định nghĩa được bên ngoài nếu, B(x)   và B (X) = U + X là B - không định nghĩa được toàn phần nếu, B(x) =  và B (X) = U - Ý nghĩa trực quan của việc phân loại này như sau: + Nếu X là - B định nghĩa thô được, có nghĩa là chúng ta có thể quyết định một số phần tử của U thuộc về X hay - X sử dụng B . + X là B- không định nghĩa được bên trong, có nghĩa là chúng ta có thể quyết định một số phần tử của U thuộc về - X , nhưng chúng ta không thể quyết định với bất kỳ phân tử nào của U, liệu nó thuộc về X hay không sử dụng B. + X là B- không định nghĩa được bên ngoài, có nghĩa chúng ta có thể quyết định một số các phần tử của U thuộc về X, nhng chúng ta không thể quyết định với bất kỳ phần tử nào của U liệu có thuộc về - X hay không, sử dụng B. + X là B- không định nghĩa được toàn phần, có nghĩa chúng ta không thể quyết định với bất kỳ phần tử nào của U liệu nó có thuộc về X hay - X hay không, sử dụng B. - Độ chính xác của xấp xỉ : Tập thô còn có thể đặc trưng định lượng bởi hệ số sau: B(X)= B( X ) B( X ) được gọi là độ chính xác của xấp xỉ của X bởi B. , ở đây X là ký hiệu lực lượng của tập X   và B là tập các thuộc tính. Rõ ràng 0 < B (X)  1. Nếu B (X) = 1, thì tập X là rõ (crisp) đối với tập B (X là chính xác với B). Ngược lại, nếu B (X) < 1, X là thô Với tập B (x là mơ hồ với tập B). Chất lượng của xấp xỉ [5,13] Cho T là một hệ thống thống tin T = (U, A), B  A và Y = {Yl,.., Yn} là một phân lớp hay một phân hoạch của U, Yi, i = 1,..n là các lớp của 19 phân lớp Y. Một độ đo để mô tả tính không chính xác của phân lớp xấp xỉ được gọi là chất lượng xấp xỉ A bởi tập các thuộc tính B, nó mô tả phần trăm các đối tượng có thể được phân lớp chính xác vào lớp A sử dụng thuộc tính B. B(A)=  n i 1 Card ( BYi ) Card (U ) B(A)=1,thì bảng quyết định là nhất quán, ngược lại nó không nhất quán. 1.2. 4. Rút gọn và lõi [6, 1 8] Trong một hệ thống thông tin, có một số thuộc tính có thể dư thừa với việc phân lớp nhất định. Lý thuyết tập thô đưa ra các khái niệm cho phép rút gọn các thuộc tính mà không làm giảm khả năng phân lớp. Cho một hệ thống thông tin T = (U,A), Một rút gọn của T là một tập tối tiểu các các thuộc tính B  A sao cho IND(B) = IND(A), ký hiệu B = RED(A). Nói cách khác, một rút gọn là một tập tối tiểu các thuộc tính thuộc A mà vẫn giữ được việc phân lớp đầu tiên định nghĩa bởi tập các thuộc tính A. Việc tìm ra một rút gọn tối tiểu là một bài toán Np-hard; người ta có thể chỉ ra rằng với m bất kỳ, tồn tại một hệ thống thông tin với m thuộc tính có số các rút gọn là một hàm mũ của m [6]. Tuy vậy, có một kinh nghiệm tốt để tính toan nhiều rút gọn một cách đầy đủ trong một thời gian chấp nhận được. Như vậy thì một tập các thuộc tính điều kiện có thể có nhiều hơn một rút gọn, giao của tất cả các rút gọn được gọi là lõi (core): CORE(A) =  RED(A) . Cho T là một hệ thống thông tin với n đối tượng, ma trận phân biệt được của T là một ma trận đối xứng n x n với các thành phần cij như sau. Mỗi thành phần là một tập các thuộc tính sao cho giá trị những thuộc tính đó ở trên những đối tượng xi và xj khác nhau. cij = {a  Aa(xi)  a(xj)} với i, j = 1, .., n