Tài liệu Một số phương pháp tính core dựa vào lý thuyết tập phô

i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn là trung thực. Nội dung luận văn có tham khảo và sử dụng các tài liệu, thông tin được đăng tải trên các ấn phẩm, tạp chí và các trang web trích dẫn theo danh mục tài liệu tham khảo của luận văn đã nêu. Huế, tháng 11 /2010 Tác giả: Nguyễn Thị Liệu ii LỜI CẢM ƠN Đầu tiên em xin gửi lời cảm ơn chân thành tới các Thầy Cô trong khoa CNTT, các Thầy Cô trong trường Đại Học Khoa Học Huế. Suốt thời gian học tập, nghiên cứu ở trường và cụ thể là tại khoa CNTT em rất cảm kích trước sự nhiệt tình chỉ bảo, dạy dỗ, truyền đạt nhiều kiến thức cho em và các anh chị học viên. Qua đây em xin bày tỏ lòng biết ơn sâu sắc và lời cảm ơn chân thành tới các Thầy Cô giáo. Em xin bày tỏ lòng biết ơn đến Cô Hoàng Thị Lan Giao, người đã tận tình hướng dẫn và giúp đỡ em trong thời gian thực hiện luận văn tốt nghiệp này. Trong thời gian làm việc với Cô không những em học hỏi được nhiều kiến thức chuyên ngành bổ ích mà còn học được tinh thần làm việc, thái độ nghiên cứu khoa học nghiêm túc của Cô. Em xin cảm ơn những người thân trong gia đình, tất cả các bạn bè anh chị của em, các bạn, anh chị cùng lớp Cao học KHMT 2008 đã có những ý kiến đóng góp và những lời động viên giúp em hoàn thành đề tài này. Mặc dù đã cố gắng hoàn thiện luận văn nhưng chắc chắn không thể tránh khỏi những thiếu sót. Một lần nữa, em xin chân thành cảm ơn và luôn mong nhận được sự đóng góp quý báu của các Thầy Cô và tất cả mọi người. Huế, tháng 11 /2010 Nguyễn Thị Liệu iii MỤC LỤC LỜI CAM ĐOAN ........................................................................................... i LỜI CẢM ƠN ................................................................................................ ii MỤC LỤC .................................................................................................... iii ̉ DANH MỤC CÁC BANG ............................................................................. v DANH MỤC CÁC HÌNH ẢNH .................................................................... vi MỞ ĐẦU ....................................................................................................... 1 Chƣơng 1 - CÁC KHÁI NIỆM CƠ BẢN .................................................... 3 1.1. Hệ thống thông tin................................................................................ 3 1.1.1. Hệ thống thông tin không đầy đủ................................................ 4 1.1.2. Bảng quyết định ......................................................................... 5 1.2. Quan hệ không phân biệt được ........................................................... 6 1.3. Ma trận phân biệt được ....................................................................... 7 1.4. Xấp xỉ của tập ..................................................................................... 9 1.5. Tập rút gọn và Core ......................................................................... 13 Chƣơng 2 - MỘT SỐ PHƢƠNG PHÁP TÍNH CORE DỰA VÀO LÝ THUYẾT TẬP THÔ .................................................................................. 16 2.1. Core trong hệ thống thông tin nhất quán ............................................ 16 2.1.1. Phương pháp tính Core dựa vào các toán tử hệ cơ sở dữ liệu. ... 16 2.1.2. Phương pháp tính Core dựa vào thông tin entropy .................... 19 2.2. Core trong hệ thống thông tin không nhất quán .................................. 31 2.2.1. Phương pháp tính Core dựa vào ma trận phân biệt được .......... 31 2.2.2. Phương pháp tính Core dựa vào miền khẳng định .................... 33 iv 2.3. Core dựa vào entropy thô trong hệ thống thông tin không đầy đủ ...... 44 2.3.1. Tri thức và Entropy của tập thô ................................................ 44 2.3.2. Ý nghĩa của thuộc tính đánh giá theo entropy thô ..................... 47 2.3.3. Thuật toán tính Core dựa vào Entropy thô ................................ 48 Chƣơng 3 - CÀI ĐẶT CÁC THUẬT TOÁN............................................. 51 3.1. Thu thập mẫu dữ liệu ......................................................................... 51 3.2. Một số thủ tục, chương trình .............................................................. 52 3.3. So sánh các phương pháp tính Core ................................................... 57 KẾT LUẬN .................................................................................................. 60 TÀI LIỆU THAM KHẢO ............................................................................ 62 v CÁC LOẠI DANH MỤC DANH MỤC CÁC BẢNG Số hiê ̣u bảng Tên bảng Trang 1.1 Hệ thống thông tin 4 1.2 Hệ thống thông tin không đầy đủ 5 1.3 Bảng quyết định 5 1.4 Hệ thống thông tin 7 1.5 Bảng quyết định 8 1.6 Ma trận phân biệt được 8 1.7 Hệ thống thông tin 9 1.8 Hệ thống thông tin 14 1.9 Bảng rút gọn thứ nhất 15 1.10 Bảng rút gọn thứ hai 15 2.1 Bảng quyết định 17 2.2 Bảng quyết định 19 2.3 Bảng quyết định 28 2.4 Bảng quyết định 30 2.5 Bảng quyết định 32 2.6 Ma trận phân biệt được 33 2.7 Bảng quyết định 34 2.8 Bảng quyết định 36 2.9 Ma trận phân biệt rút gọn 36 2.10 Bảng quyết định 42 2.11 Bảng hệ thống thông tin không đầy đủ 49 3.1 Bảng quyết định 58 vi DANH MỤC CÁC HÌNH ẢNH Số hiệu hình vẽ Tên hình vẽ Trang 1.1 Tập xấp xỉ 10 3.1 Bảng dữ liệu 51 3.2 Bảng dữ liệu 52 3.3 Giao diện chương trình 56 3.4 Giao diện chương trình 57 1 MỞ ĐẦU 1. Tính cấp thiết của đề tài Trong khai phá dữ liệu, việc rút gọn thuộc tính trong hệ thống thông tin nhằm loại đi những thuộc tính dư thừa, không cần thiết. Nói cách khác, chỉ cần trên một tập thuộc tính rút gọn có thể có được thông tin của toàn hệ thống. Tuy nhiên, đối với một hệ thống có thể có nhiều tập rút gọn khác nhau, trong thực tế đôi khi một ứng dụng cụ thể chỉ cần một tập rút gọn phù hợp là có thể có đầy đủ thông tin mong muốn. Core được định nghĩa bằng giao của tất cả các tập rút gọn Core= R. RRe d Điều này đòi hỏi phải biết được tất cả tập rút gọn thì mới tính được Core. Do tất cả các thuộc tính trong Core đều có mặt ở bất kỳ tập rút gọn nào và Core có thể được sử dụng hiệu quả trong việc tạo cây quyết định nhiều biến. Vì vậy, vấn đề được đặt ra liệu có thể phát hiện Core một cách độc lập trước khi tìm được tập rút gọn không? Nhiều nhà nghiên cứu đã nổ lực giải quyết vấn đề này và đã có những thành công nhất định. 2. Mục đích của đề tài Đề tài này được thực hiện với mục đích tìm hiểu, tổng hợp, so sánh một số phương pháp tính Core khác nhau dựa vào lý thuyết tập thô. Đặc biệt, quan tâm đến các phương pháp heuristic, nhằm tăng tốc độ tính toán, để từ đó có thể rút ra được những phương pháp tính Core phù hợp với dữ liệu trong các tình huống bài toán cụ thể trên thực tế. 3. Đối tƣợng và phạm vi nghiên cứu  Nghiên cứu lý thuyết tập thô và lý thuyết thông tin 2  Một số phương pháp tính Core trên hệ thống thông tin đầy đủ và hệ thống thông tin không đầy đủ. 4. Phƣơng pháp nghiên cứu Tìm hiểu, tổng hợp một số phương pháp tính Core dựa vào lý thuyết tập thô. Cài đặt thử nghiệm một số phương pháp. 5. Ý nghĩa thực tiễn của đề tài Trên thực tế, đã có rất nhiều nghiên cứu về phương pháp tính Core khác nhau. Ví dụ: Hu đã trình bày thuật toán tính Core dựa trên ma trận phân biệt được, Dongyi Ye đã đưa ra ma trận phân biệt được dựa trên miền khẳng định và đã chứng minh rằng Core đã tính toán với thuật toán được thiết kế bằng ma trận phân biệt được là nhất quán với Core đã được tính toán dựa trên miền khẳng định… Đề tài này nhằm tìm hiểu, tổng hợp một số phương pháp tính Core có đánh giá độ phức tạp của từng phương pháp. 6. Cấu trúc của luận văn Luận văn gồm 3 chương, được tổ chức như sau: Chương 1: Nêu một số khái niệm cơ bản trong khai phá dữ liệu và lý thuyết tập thô có liên quan đến nội dung chính của luận văn như: Hệ thống thông tin, quan hệ không phân biệt, ma trận phân biệt được, tập xấp xỉ, tập rút gọn và Core. Chương 2: Trình bày năm phương pháp tính Core dựa vào lý thuyết tập thô: hai phương pháp tính Core trong hệ thống thông tin nhất quán, hai phương pháp tính Core trong hệ thống thông tin không đầy đủ và một phương pháp tính Core trong hệ thống thông tin không đầy đủ. Chương 3: Cài đặt một số thuật toán và so sánh kết quả của các thuật toán. 3 Chƣơng 1 CÁC KHÁI NIỆM CƠ BẢN Lý thuyết tập thô được đề xuất bởi Pawlak vào năm 1982. Lý thuyết này có nhiều ứng dụng thành công trong học máy, khai phá dữ liệu, trí tuệ nhân tạo và các ứng dụng khác. Lý thuyết tập thô dựa trên giả thiết rằng để định nghĩa một tập hợp, chúng ta cần có thông tin về mọi đối tượng trong tập vũ trụ. Trong lý thuyết tập thô có thể tồn tại một số đối tượng giống nhau ở một số thông tin nào đó và tri thức được coi là khả năng phân loại giữa các đối tượng. Ở đây, sự phân loại chủ yếu dựa vào quan hệ không phân biệt được với nhau. Đây chính là quan hệ quan trọng và là điểm xuất phát của lý thuyết tập thô: biên của tập thô là không rõ ràng và để xác định biên ta phải xấp xỉ bằng các tập hợp khác nhằm mục đích cuối cùng là trả lời được rằng mọi đối tượng nào đó có thuộc tập hợp hay không. Lý thuyết tập thô với cách tiếp cận như vậy đã được ứng dụng trong rất nhiều lĩnh vực của đời sống xã hội [3]. Ngoài ra, lý thuyết tập thô phân loại tất cả các thuộc tính vào 3 loại: thuộc tính Core, thuộc tính rút gọn và thuộc tính không cần thiết [10]. 1.1. Hệ thống thông tin Hệ thống thông tin IS là một cặp (U,A). Trong đó, U là tập hữu hạn các đối tượng khác rỗng (được gọi là tập vũ trụ các đối tượng) và A là tập hữu hạn các thuộc tính khác rỗng.Với mọi aA, ta ký hiệu Va là tập giá trị của a. Mặt khác, nếu uU và aA thì ta sẽ ký hiệu u(a)Va là giá trị thuộc tính a của đối tượng u [2]. 4 Ví dụ 1.1. Bảng 1.1. Hệ thống thông tin U Quang cảnh Nhiệt độ Độ ẩm Gió u1 Nắng Nóng Cao Không u2 Nắng Nóng Cao Có u3 Âm u Nóng Cao Không u4 Mưa Trung bình Cao Không u5 Mưa Mát mẻ Trung bình Không u6 Mưa Mát mẻ Trung bình Có u7 Âm u Mát mẻ Trung bình Có Trong đó, U= {u1, u2, u3, u4, u5, u6, u7} là tập hợp các đối tượng. A = {Quang cảnh, Nhiệt độ, Độ ẩm, Gió} là tập hợp các thuộc tính. u1(Quang cảnh) = Nắng là giá trị của thuộc tính Quang cảnh của đối tượng u1. 1.1.1. Hệ thống thông tin không đầy đủ Hệ thống thông tin IS=(U,A) được gọi là không đầy đủ nếu tồn tại thuộc tính aA và đối tượng uU mà giá trị u(a) bị mất hay nói cách khác Va chứa giá trị null [6]. Trên hệ thống thông tin không đầy đủ, giá trị thuộc tính được chia làm hai loại: - Giá trị bị mất, giá trị này được ký hiệu là “?”: ban đầu, giá trị thuộc tính đó của đối tượng đang xét có tồn tại và có ảnh hưởng đến việc 5 phân lớp quyết định của đối tượng. Tuy nhiên, vì lý do nào đó mà giá trị này bị xóa đi và hiện tại không thể xác định được. - Giá trị điều kiện không quan trọng, giá trị này được ký hiệu là “*”: giá trị ban đầu của đối tượng trên thuộc tính đang xét không được lưu lại do không có ý nghĩa trong việc ra quyết định phân lớp đối tượng đó. Ví dụ 1.2. Bảng 1.2. Hệ thống thông tin không đầy đủ U Giá Kích thước Động cơ Tốc độ tối đa u1 Thấp Nhỏ * Thấp u2 Thấp Lớn Diesel Cao u3 Cao Lớn Diesel Trung bình u4 Cao * Diesel Trung bình u5 ? Lớn Gasoline Cao 1.1.2. Bảng quyết định Bảng quyết định là một hệ thống thông tin có dạng T=(U,C,D), với A=CD, CD=, trong đó C là tập thuộc tính điều kiện còn D là tập thuộc tính quyết định. Ví dụ 1.3. Bảng 1.3. Bảng quyết định U Quang cảnh Nhiệt độ Độ ẩm Gió Chơi tennis u1 Nắng Nóng Cao Không Không u2 Nắng Nóng Cao Có Không u3 Âm u Nóng Cao Không Có u4 Mưa Trung bình Cao Không Có u5 Mưa Mát mẻ Trung bình Không Có 6 Trong bảng 1.3, các thuộc tính điều kiện C là: Quang cảnh, Nhiệt độ, Độ ẩm, Gió. Thuộc tính quyết định D là: Chơi tennis Trong bảng quyết định các đối tượng giống nhau hay không phân biệt được có thể được mô tả nhiều lần. Bảng quyết định mà các đối tượng có các thuộc tính điều kiện giống nhau nhưng thuộc tính quyết định khác nhau thì gọi là bảng quyết định không nhất quán, ngược lại là bảng quyết định nhất quán. 1.2. Quan hệ không phân biệt đƣợc [1], [3] Cho IS=(U,A) là một hệ thống thông tin, R là một quan hệ hai ngôi trên U, có nghĩa là R  UU, khi đó R được gọi là một quan hệ tương đương nếu R thỏa mãn các tính chất: Phản xạ: uU, uRu Đối xứng: u,vU, uRv vRu Bắc cầu: u,v,tU, uRv và vRt  uRt Với bất kỳ BA, có một quan hệ tương đương định nghĩa trên U như sau: IND(B) = {(u,v)U2| aB, u(a) = v(a)} IND(B) được gọi là B–quan hệ không phân biệt được. Nếu (u,v)IND(B), thì các đối tượng u và v là không phân biệt được với nhau bởi các thuộc tính trong B. Lớp tương đương chứa u của B–quan hệ không phân biệt được ký hiệu [u]B. Ký hiệu U/B là tập hợp thương của quan hệ tương đương IND(B). Ví dụ 1.4. 7 Bảng 1.4. Hệ thống thông tin U Quang cảnh Gió Chơi tennis u1 Nắng Không Không u2 Nắng Có Không u3 Âm u Không Có u4 Mưa Không Có u5 Mưa Không Có u6 Mưa Có Không u7 Âm u Có Có Các tập con không rỗng của tập thuộc tính điều kiện là {Quang cảnh}, {Gió} và {Quang cảnh, Gió}. IND(Quang cảnh) = {{u1,u2}, {u3, u7}, {u4,u5,u6 }} IND(Gió) = {{u1, u3, u4, u5},{u2, u6, u7}} IND({Quang cảnh, Gió }) = {{u1}, {u2}, {u3}, {u4,u5}, {u7}, {u6}} 1.3. Ma trận phân biệt đƣợc Giả sử U={u1, u2,…, un}. Ma trận phân biệt được của T, ký hiệu M(T)=(mij)nn, là một ma trận đối xứng mà mỗi phần tử của nó là một tập hợp các thuộc tính, được xác định như sau: {c  C : c(u i )  c(u j )} nÕu  d  D | d(u i )  d(u j )  m ij   nÕu  d  D | d(u i )  d(u j ) λ  Như vậy, mij là tập hợp gồm tất cả các thuộc tính điều kiện có thể xếp các đối tượng ui và uj vào các lớp tương đương khác nhau theo phân hoạch trên U đối với thuộc tính đó. Giá trị  hàm ý rằng cặp đối tượng ui và uj là không phân biệt trên tập thuộc tính quyết định D. Nếu mij =  thì bảng quyết định là không nhất quán [1], [5]. Ví dụ 1.5. Xét bảng quyết định sau 8 Bảng 1.5. Bảng quyết định U a b c d e u1 1 0 2 1 1 u2 1 0 2 0 1 u3 1 2 0 0 2 u4 1 2 2 1 0 u5 2 1 0 0 2 u6 2 1 1 0 2 u7 2 1 2 1 1 Trong đó, tập thuộc tính điều kiện C={a,b,c,d} và tập thuộc tính quyết định D={e}. Ma trận phân biệt được tương ứng : Bảng 1.6. Ma trận phân biệt được U u1 u2 u3 u4 u1  u2   u3 {b,c,d} {b,c}  u4 {b} {b,d} {c,d} u5 u6  u5 {a,b,c,d} {a,b,c}  {a,b,c,d}  u6 {a,b,c,d} {a,b,c}  {a,b,c,d}   {a,b,c,d} {a,b} {c,d} {c,d} u7 u7    9 1.4. Xấp xỉ của tập [1], [2], [3] Cho hệ thống thông tin IS=(U,A) và BA, XU. Xấp xỉ dưới và xấp xỉ trên của tập X tương ứng với B, ký hiệu theo thứ tự là B X và B X được định nghĩa như sau: BX  {x | [x] B  X } BX  {x | [x] B  X  } Với [x]B là lớp tương đương chứa phần tử x của quan hệ IND(B) Rõ ràng, B X  X  B X . Tập BNB(X) = B X – B X được gọi là B– miền biên của X, bao gồm tất cả những đối tượng mà ta không thể phân lớp một cách rõ ràng thuộc vào tập X dựa trên tập thuộc tính B. U - B X là B – miền ngoài của X, bao gồm tất cả những đối tượng có thể được phân lớp chắc chắn là không thuộc X. Ví dụ 1.6. Bảng 1.7. Hệ thống thông tin X Age LEMS Walk x1 16-30 50 Yes x2 16-30 0 No x3 31- 45 1-25 No x4 31- 45 1-25 Yes x5 46 -60 26-49 No x6 16 -30 26-49 Yes x7 46 -60 26-49 No Cho W = {x | Walk(x) = Yes}. 10 A W = {x1, x6}, A W = {x1, x3, x4, x6}, BNA(A) = {x3, x4}, U - A W = {x2, x5, x7}. Các xấp xỉ dưới và xấp xỉ trên: Xấp xỉ trên: R X ={YU/R: YX  } Xấp xỉ dưới: R X = {YU/R: YX} AW {{x2}, {x5,x7}} AW {{x3,x4} yes {{x1}, {x1}} yes/no no RX U/R RX R : tập con của các thuộc tính TậpＸ Hình 1.1: Tập xấp xỉ 11 Một số tính chất của các tập xấp xỉ 1. B( X )  X  B X 2. B( )  B( )   , B(U )  B(U )  U 3. 4. B( X  Y )  B( X )  B(Y ) B( X  Y )  B( X )  B(Y ) 5. Nếu X Y thì B( X )  B(Y ) , B( X )  B(Y ) 6. B( X  Y )  B( X )  B(Y ) 7. B( X  Y )  B( X )  B(Y ) 8. B(U \ X )  U \ B( X ) 9. B(U \ X )  U \ B( X ) 10. B( B( X ))  B( B( X ))  B( X ) 11. B( B( X ))  B( B( X ))  B( X ) Chứng minh một số tính chất điển hình. 3. Để chứng minh B( X  Y )  B( X )  B(Y ) cần chứng minh : o B (XY)  o B (X) B (Y) Từ định nghĩa xấp xỉ trên ta có: Với o B (X Y)  PU|IND(B): (oP, P(XY) ). Mặt khác: P(XY)    PX  hoặc PY Do đó: o B (XY)  (oP, PX) hoặc (oP, PY )  (o B (X)) hoặc (o B (Y))  o B (X) B (Y) 12 4. Chứng minh tương tự 3. 5. Chứng minh: X  Y  ( B( X )  B(Y )) Giả sử: XY Xét o B(X ) . Khi đó, P, PU|IND(B): oP, PX Mà XY nên PY. Nhưng theo định nghĩa xấp xỉ dưới: B(Y ) = {x|xP, PU|IND(B), PY} Nên: P B(Y ) , từ đó o B(Y ) Vậy: B( X )  B(Y ) . Tương tự ta chứng minh được B (X) B (Y) 6. Xét o  B( X )  B(Y )  P, PU|IND(B), oP, (PXPY)  PXY. Mặt khác theo định nghĩa tập xấp xỉ dưới: B( X  Y )  {x | x  P, P U | IND( B), P  X  Y } Vậy P B( X  Y ), từ đó o  B( X  Y )  điều phải chứng minh. 7. Chứng minh tương tự 6 8. Ta có: B(U \ X )  {P | P U | IND( B), P  U \ X } = U \ {P | P U | IND( B), P  X  } = U \ B( X ) (điều phải chứng minh) 13 Chứng minh tương tự hoặc có thể suy ra từ 8 Từ định nghĩa của tập xấp xỉ dưới: B( B(( X ))  {x U | xB  B( X )}  {x  U | xB  X )} , vì B(X )  X = B(X ) Tương tự: B( B( X ))  B( X ). Vậy ta có điều phải chứng minh. Chứng minh tương tự 10 1.5. Tập rút gọn và Core [1], [2], [3] Trong hệ thống thông tin có một số tập chỉ giữ lại các thuộc tính duy trì quan hệ không phân biệt được và duy trì xấp xỉ của tập. Trong những tập thuộc tính như thế có những tập tối thiểu được gọi là tập rút gọn. Một tập rút gọn của tri thức là phần cần thiết đủ để định nghĩa tất cả các khái niệm cơ bản xảy ra trong việc xem xét tri thức. Cụ thể, cho cC, ta có định nghĩa sau: Định nghĩa 1.1 [9]. Thuộc tính c là không cần thiết trong T nếu POS C ( D)  POS (C {c}) ( D) , ngược lại thuộc tính c là cần thiết trong T. C- miền khẳng định của D: POSC ( D)  CX X U / D T= (C, D) là độc lập nếu tất cả cC là cần thiết trong T. Tập các thuộc tính R  C được gọi là một rút gọn của C, nếu T’=(U,RD) là độc lập và POS R ( D)  POS C ( D). 14 Tập tất cả các thuộc tính điều kiện cần thiết trong T được gọi là lõi của C, ký hiệu Core(C). Lưu ý rằng lõi có thể là tập rỗng và khi đó mọi tập con của P với lực lượng bằng card(C)-1 đều giữ nguyên khả năng phân loại của C. Khi loại khỏi C các thuộc tính không cần thiết thì được một rút gọn của C. Nói cách khác, rút gọn của một tập thuộc tính C là tập thuộc tính BC giữ nguyên khả năng phân loại của C, hay IND(B)=IND(C). Vì lõi của C là tập các thuộc tính cần thiết của C nên tất cả các rút gọn của C đều chứa tập thuộc tính lõi. Tập thuộc tính lõi của C là giao của tất cả các rút gọn của C, tức là: CORE(C )  RED (C ) Trong đó, RED(C) là tập tất cả các rút gọn C. Ví dụ 1.7. Cho hệ thống thông tin Bảng 1.8. Hệ thống thông tin U Sự tín nhiệm Khách hàng biết đến Kho dự trữ Sắp xếp hàng u1 Tốt Có Đủ Chấp nhận u2 Tốt Không Không Đủ Từ chối u3 Tốt Không Đủ Chấp nhận u4 Không tốt Không Không đủ Từ chối u5 Không tốt Có Đủ Chấp nhận