i LỜI CAM ĐOAN Tôi xin cam đoan công trình nghiên cứu riêng Các số liệu, kết nêu luận văn trung thực Nội dung luận văn có tham khảo sử dụng tài liệu, thông tin đăng tải ấn phẩm, tạp chí trang web trích dẫn theo danh mục tài liệu tham khảo 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 Thầy Cô khoa CNTT, Thầy Cô trường Đại Học Khoa Học Huế Suốt thời gian học tập, nghiên cứu trường cụ thể khoa CNTT em cảm kích trước nhiệt tình bảo, dạy dỗ, truyền đạt nhiều kiến thức cho em anh chị học viên Qua em xin bày tỏ lòng biết ơn sâu sắc lời cảm ơn chân thành tới 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 giúp đỡ em thời gian thực luận văn tốt nghiệp Trong thời gian làm việc với Cô em học hỏi nhiều kiến thức chuyên ngành bổ ích mà học tinh thần làm việc, thái độ nghiên cứu khoa học nghiêm túc Cô Em xin cảm ơn người thân gia đình, tất bạn bè anh chị em, bạn, anh chị lớp Cao học KHMT 2008 có ý kiến đóng góp lời động viên giúp em hoàn thành đề tài Mặc dù cố gắng hoàn thiện luận văn chắn tránh khỏi thiếu sót Một lần nữa, em xin chân thành cảm ơn mong nhận đóng góp quý báu Thầy Cô tất 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 BẢNG v DANH MỤC CÁC HÌNH ẢNH vi MỞ ĐẦU Chƣơng - CÁC KHÁI NIỆM CƠ BẢN 1.1 Hệ thống thông tin 1.1.1 Hệ thống thông tin không đầy đủ 1.1.2 Bảng định 1.2 Quan hệ không phân biệt 1.3 Ma trận phân biệt 1.4 Xấp xỉ tập 1.5 Tập rút gọn Core 13 Chƣơng - MỘT SỐ PHƢƠNG PHÁP TÍNH CORE DỰA VÀO LÝ THUYẾT TẬP THÔ 16 2.1 Core hệ thống thông tin quán 16 2.1.1 Phương pháp tính Core dựa vào toán tử hệ sở 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 hệ thống thông tin không quán 31 2.2.1 Phương pháp tính Core dựa vào ma trận phân biệt 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ô hệ thống thông tin không đầy đủ 44 2.3.1 Tri thức Entropy tập thô 44 2.3.2 Ý nghĩ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 - CÀI ĐẶT CÁC THUẬT TOÁN 51 3.1 Thu thập mẫu liệu 51 3.2 Một số thủ tục, chương trình 52 3.3 So sánh 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 1.2 Hệ thống thông tin không đầy đủ 1.3 Bảng định 1.4 Hệ thống thông tin 1.5 Bảng định 1.6 Ma trận phân biệt 1.7 Hệ thống thông tin 1.8 Hệ thống thông tin 14 1.9 Bảng rút gọn thứ 15 1.10 Bảng rút gọn thứ hai 15 2.1 Bảng định 17 2.2 Bảng định 19 2.3 Bảng định 28 2.4 Bảng định 30 2.5 Bảng định 32 2.6 Ma trận phân biệt 33 2.7 Bảng định 34 2.8 Bảng định 36 2.9 Ma trận phân biệt rút gọn 36 2.10 Bảng định 42 2.11 Bảng hệ thống thông tin không đầy đủ 49 3.1 Bảng đị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 liệu 51 3.2 Bảng liệu 52 3.3 Giao diện chương trình 56 3.4 Giao diện chương trình 57 MỞ ĐẦU Tính cấp thiết đề tài Trong khai phá liệu, việc rút gọn thuộc tính hệ thống thông tin nhằm loại thuộc tính dư thừa, không cần thiết Nói cách khác, cần tập thuộc tính rút gọn có thông tin toàn hệ thống Tuy nhiên, hệ thống có nhiều tập rút gọn khác nhau, thực tế ứng dụng cụ thể cần tập rút gọn phù hợp có đầy đủ thông tin mong muốn Core định nghĩa giao tất tập rút gọn Core= R RRe d Điều đòi hỏi phải biết tất tập rút gọn tính Core Do tất thuộc tính Core có mặt tập rút gọn Core sử dụng hiệu việc tạo định nhiều biến Vì vậy, vấn đề đặt liệu phát Core cách độc lập trước tìm tập rút gọn không? Nhiều nhà nghiên cứu nổ lực giải vấn đề có thành công định Mục đích đề tài Đề tài thực với mục đích tìm hiểu, tổng hợp, so sánh số phương pháp tính Core khác dựa vào lý thuyết tập thô Đặc biệt, quan tâm đến phương pháp heuristic, nhằm tăng tốc độ tính toán, để từ rút phương pháp tính Core phù hợp với liệu tình toán cụ thể thực tế Đối tƣợng phạm vi nghiên cứu  Nghiên cứu lý thuyết tập thô lý thuyết thông tin  Một số phương pháp tính Core hệ thống thông tin đầy đủ hệ thống thông tin không đầy đủ Phƣơng pháp nghiên cứu Tìm hiểu, tổng hợp số phương pháp tính Core dựa vào lý thuyết tập thô Cài đặt thử nghiệm số phương pháp Ý nghĩa thực tiễn đề tài Trên thực tế, có nhiều nghiên cứu phương pháp tính Core khác Ví dụ: Hu trình bày thuật toán tính Core dựa ma trận phân biệt được, Dongyi Ye đưa ma trận phân biệt dựa miền khẳng định chứng minh Core tính toán với thuật toán thiết kế ma trận phân biệt quán với Core tính toán dựa miền khẳng định… Đề tài nhằm tìm hiểu, tổng hợp số phương pháp tính Core có đánh giá độ phức tạp phương pháp Cấu trúc luận văn Luận văn gồm chương, tổ chức sau: Chương 1: Nêu số khái niệm khai phá liệu lý thuyết tập thô có liên quan đến nội dung 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 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 hệ thống thông tin quán, hai phương pháp tính Core hệ thống thông tin không đầy đủ phương pháp tính Core hệ thống thông tin không đầy đủ Chương 3: Cài đặt số thuật toán so sánh kết thuật toán Chƣơng CÁC KHÁI NIỆM CƠ BẢN Lý thuyết tập thô đề xuất Pawlak vào năm 1982 Lý thuyết có nhiều ứng dụng thành công học máy, khai phá liệu, trí tuệ nhân tạo ứng dụng khác Lý thuyết tập thô dựa giả thiết để định nghĩa tập hợp, cần có thông tin đối tượng tập vũ trụ Trong lý thuyết tập thô tồn số đối tượng giống số thông tin tri thức coi khả phân loại đối tượng Ở đây, phân loại chủ yếu dựa vào quan hệ không phân biệt với Đây quan hệ quan trọng điểm xuất phát lý thuyết tập thô: biên tập thô không rõ ràng để xác định biên ta phải xấp xỉ tập hợp khác nhằm mục đích cuối trả lời đối tượng có thuộc tập hợp hay không Lý thuyết tập thô với cách tiếp cận ứng dụng nhiều lĩnh vực đời sống xã hội [3] Ngoài ra, lý thuyết tập thô phân loại tất thuộc tính vào loại: thuộc tính Core, thuộc tính rút gọn 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 cặp (U,A) Trong đó, U tập hữu hạn đối tượng khác rỗng (được gọi tập vũ trụ đối tượng) A tập hữu hạn thuộc tính khác rỗng.Với aA, ta ký hiệu Va tập giá trị a Mặt khác, uU aA ta ký hiệu u(a)Va giá trị thuộc tính a đối tượng u [2] 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} tập hợp đối tượng A = {Quang cảnh, Nhiệt độ, Độ ẩm, Gió} tập hợp thuộc tính u1(Quang cảnh) = Nắng giá trị thuộc tính Quang cảnh đố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) gọi không đầy đủ tồn thuộc tính aA đối tượng uU mà giá trị u(a) bị 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 chia làm hai loại: - Giá trị bị mất, giá trị ký hiệu “?”: ban đầu, giá trị thuộc tính đối tượng xét có tồn có ảnh hưởng đến việc 49 Input: Một hệ thống thông tin không đầy đủ IS = (U,A) Output: Tập Core A Method: Bước 1: Core(A) = ; Tính entropy thô E(A) thuộc tính A; Bước 2: For a  A Begin Tính K = sigA – {a}(a); If K > then Core(A) = Core (A) a; End Ví dụ 2.8 Cho bảng định sau Bảng 2.11 Bảng hệ thống thông tin không đầy đủ Car Giá Kích thước Động 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 Thấp Lớn Gasoline Cao Đây hệ thống thông tin không đầy đủ, U={u1,u2,u3,u4,u5} A={a1,a2,a3,a4}, với a1 Giá, a2 Kích thước, a3 Động cơ, a4 Tốc độ tối đa Với bảng 2.11, tính Core theo thuật toán 50 Bước 1: Tính U/SIM(A) = {SA(u1), SA(u2), SA(u3), SA(u4), SA(u5)}, đó: SA(u1)={u1}, SA(u2)= {u2}, SA(u3)= SA(u4) = {u3, u4}, SA(u5)= {u5}, E(A)= 0.8 Bước 2: Tính sigA-{a1}(a1) = sigA-{a2}(a2) = sigA-{a4}(a4) = 0, SigA-{a3}(a3) = E(A-{a3}) – E(A) = 0.16-0.8 = 0.8>0; Vậy Core(A) ={a3} = {Động cơ} Với k số thuộc tính điều kiện Vòng lặp for thực tối đa k lần, bước lặp thực tính entropy thô ý nghĩa thuộc tính, nên độ phức tạp vòng lặp O(k) 51 Chƣơng CÀI ĐẶT CÁC THUẬT TOÁN 3.1 Thu thập mẫu liệu Dữ liệu đầu vào thuật toán tính Core bảng định, gồm thuộc tính điều kiện thuộc tính định có thuộc tính Tùy vào thuật toán, đặc điểm loại liệu khác nhau: - Đối với thuật toán tính Core hệ thống thông tin quán: phương pháp tính Core dựa vào toán tử hệ sở liệu Core dựa vào thông tin Entropy liệu bảng định quán, giá trị thuộc tính liệu kiểu số kiểu chuỗi Hình 3.1: Bảng liệu - Đối với thuật toán tính Core hệ thống thông tin không quán: phương pháp tính Core dựa vào ma trận phân biệt dựa vào miền khẳng định liệu vào bảng định không quán Bảng định trường hợp có giá trị thuộc tính điều kiện định kiểu số, giá trị kiểu chuỗi ta phải tìm cách chuyển liệu kiểu số 52 Hình 3.2: Bảng liệu 3.2 Một số thủ tục, chƣơng trình Chương trình cài đặt thuật toán viết môi trường Visual Studio 2008, viết ngôn ngữ C# Dưới số chương trình trích dẫn từ code chương trình cài đặt Chương trình tính Core dựa vào toán tử hệ Cơ sở liệu private void TinhCore_DuavaoCSDL() { List C = new List(); string str_Dieukien = ""; string D = ""; DataTable tbl = table; int countCol = tbl.Columns.Count; for (int i = 0; i < countCol - 1; i++) { C.Add(tbl.Columns[i].ColumnName); str_Dieukien += tbl.Columns[i].ColumnName + ","; } 53 D = tbl.Columns[countCol - 1].ColumnName; str_Dieukien = str_Dieukien.Substring(0, str_Dieukien.Length - 1); string kq = ""; string sql = ""; DataTable card1 = new DataTable(); DataTable card2 = new DataTable(); for (int j = 0; j < C.Count; j++) { string st = str_Dieukien; int k = st.IndexOf(C[j]); st = (st.Remove(k, C[j].Length)); if (k == 0) st = st.Remove(0, 1); if (k < st.Length && k > 0) st = st.Remove(k - 1, 1); if (k == st.Length) st = st.Remove(k - 1, 1); sql = "select distinct " + st + " from " + AccessTablecmb.Text; card1 = ExcuteQuery(sql); if (st != "") st += "," + D; else st = D; sql = "select distinct " + st + " from " + AccessTablecmb.Text; card2 = ExcuteQuery(sql); if (card1.Rows.Count != card2.Rows.Count) kq += C[j] + ","; ; } if (kq != "") lblKetqua.Text = ""; else lblKetqua.Text = "Khong the xac dinh!"; } 54 Chương trình tính Core dựa vào miền khẳng định: Bước 1: Tìm bảng định rút gọn Bước 2: Tìm Core bảng định rút gọn private void TinhCore_DuavaoMienkhangdinh() int s = Upost.Count; int t = Uneg.Count; int D_index = C.Count + 1; int r = countC; List Core = new List(); for (int i = 0; i < s; i++) for (int j = i + 1; j < s + 1; j++) { if (j < Upost.Count) { ArrayList fy_i = Upost[i]; ArrayList fy_j = Upost[j]; if (Convert.ToInt32(fy_i[D_index]) != Convert.ToInt32(fy_j[D_index])) { ArrayList B = new ArrayList(); int flag = 0; for (int k = 0; k < r; k++) { if (Convert.ToInt32(fy_i[k + 1]) != Convert.ToInt32(fy_j[k + 1])) { B.Add(C[k]); flag += 1; } if (flag > 1) break; } if (flag == 1) { Core.Add(B); } } } } int d0 = 0; for (int i = 0; i < s; i++) 55 { d0 = 0; for (int j = 0; j < t; j++) { if (j < Uneg.Count) { ArrayList fy_i = Upost[i]; ArrayList fz_j = Uneg[j]; ArrayList B = new ArrayList(); int flag = 0; for (int k = 0; k < r; k++) { if (Convert.ToInt32(fy_i[k + 1]) != Convert.ToInt32(fz_j[k + 1])) { B.Add(C[k]); flag += 1; } if (flag > 1) break; } if (flag == 1) { Core.Add(B); } d0 += 1; } } } int c = d0; string kq = ""; for (int f = 0; f < Core.Count; f++) { kq += Core[f][0].ToString() + ","; } if (kq != "") lblKetqua.Text = kq.Substring(0, kq.Length - 1); else lblKetqua.Text = "Khong xac dinh duoc"; } 56 Giao diện chƣơng trình Form thực kết nối Cơ sở liệu lựa chọn phương pháp tính Core Hình 3.3 Giao diện chương trình Sau chọn sở liệu danh sách bảng sở liệu hiển thị combobox Table để ta chọn bảng Khi thực chọn bảng có sở liệu liệu load lên form Tiếp theo, thực chọn phương pháp tính Core cách kích vào combobox Select method Chọn xong phương pháp, kích vào nút Submit để xem kết Core thu 57 Form lựa chọn phương pháp tính Core kích vào Submit, kết tập Core xuất dạng lable form Hình 3.4 Giao diện chương trình 3.3 So sánh phƣơng pháp tính Core Như vậy, có nhiều phương pháp tính Core khác Tùy thuộc liệu vào ta áp dụng phương pháp tính Core phù hợp Với bảng định quán dùng phương pháp tính Core dựa vào toán tử hệ sở liệu phương pháp tính Core dựa vào thông tin entropy Với bảng định không quán dùng phương pháp tính Core dựa vào ma trận phân biệt phương pháp tính Core dựa vào miền khẳng định Đối với hệ thống thông tin không đầy đủ dùng phương pháp tính Core dựa vào Entropy thô Từ kết kết hợp vài nghiên cứu có dẫn ta thấy phương pháp tính Core không tương đương 58 Gọi phương pháp tính Core dựa vào ma trận phân biệt Hu Core1(C), phương pháp tính Core dựa vào miền khẳng định Core2(C) phương pháp tính Core dựa vào entropy Core3(C) Ta tìm khác định nghĩa thuộc tính Core lý thuyết tập thô bảng định quán, tức hệ thống thông tin quán Core1(C)= Core2(C)=Core3(C) Tuy nhiên, bảng định không quán, kết thuật toán không giống Cụ thể, ta có Core2(C)Core3(C)Core1(C) [4] [7] Ví dụ 3.1 Bảng 3.1 bảng định không quán Thuộc tính điều kiện a, b thuộc tính định d Bảng 3.1 Bảng định U a b D u1 1 u2 1 u3 1 u4 0 u5 1 u6 u7 0 u8 0 Thuộc tính Core bảng 1, kết từ thuật toán tính Core theo phương pháp dựa vào ma trận phân biệt {a,b}, Core1 = {a, b} Tuy nhiên, quan điểm thông tin lý thuyết tập thô H ({d } \ {a, b}) 1 1  4( ( log( )  log( ))) , 2 2  log( 2) 59 H ({d } | {a})  H ({d } | {b}) 1 1  2( ( log( )  log( ))) 2 2  log(2) Vì vậy, H ({d} | {a, b})  H ({d} | {a})  H ({d} | {b}) Do đó, thuộc tính Core bảng quan điểm thông tin lý thuyết tập thô , có nghĩa Core3 =  Vì vậy, Core1  Core3 60 KẾT LUẬN Luận văn thực tìm hiểu, tổng hợp, trình bày số phương pháp tính Core dựa vào lý thuyết tập thô Mỗi thuật toán trình bày hệ thống áp dụng có phân tích đánh giá độ phức tạp thuật toán Cụ thể có phương pháp tính Core trình bày Trong đó: - Phương pháp tính Core dựa vào toán tử hệ sở liệu, ý tưởng sử dụng toán tử đếm chiếu để kiểm tra lực lượng hai tập thuộc tính C-{cj}+D C- {cj} lực lượng phép chiếu hai tập khác cj thuộc tính Core - Phương pháp tính Core dựa vào thông tin Entropy sử dụng khái niệm entropy lý thuyết thông tin để thực tính Core Nếu tri thức Entropy thuộc tính định d với điều kiện toàn tập thuộc tính C khác với tri thức Entropy d với điều kiện C–{cj} cj thuộc tính Core - Phương pháp tính Core dựa vào ma trận phân biệt dựa ý tưởng xây dựng ma trận phân biệt được, giá trị ma trận phân biệt có phần tử thuộc tính Core - Phương pháp tính Core dựa vào miền khẳng định, xây dựng ma trận phân biệt dựa theo miền khẳng định Từ tính Core theo ma trận - Phương pháp tính Core dựa vào Entropy thô, sử dụng số định lý, khái niệm, định nghĩa hệ thống thông tin không đầy đủ, sau đưa công thức tính Core cho hệ thống thông tin không đầy đủ 61 Dù cố gắng thực tốt đề tài này, nhiên kết thực nhiều hạn chế, chưa thực tổng hợp cài đặt đầy đủ thuật toán mô hình thực tế cụ thể Hƣớng phát triển luận văn - Tìm hiểu, cài đặt phương pháp tính Core cho liệu không chắn, liệu mờ - Tìm hiểu đưa phương pháp tính Core vào toán ứng dụng thực tế cụ thể 62 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt Hoàng Thị Lan Giao (2009), Bài giảng datamining, Đại Học Khoa Học Huế Hồ Thuần, Hoàng Thị Lan Giao (2005), “Một thuật toán tìm tập rút gọn sử dụng ma trận phân biệt được”, Chuyên san công trình nghiên cứu triển khai Viễn thông CNTT, số 15 (12/2005), 83-87 Tài liệu tiếng Anh A.Sknowron, C.Rauser (1991), The discernibility matrices and function in information system, Institute of Computer Science, Nowowiejska 15/19, 00-665 Warsaw, Poland Guoyin Wangm, Long Chen (2004), “Attribute Core of Decision Table in the Algebra View and Information View”, Chongqing 400065, P R CHINA Hao Ge, Chuanjian Yang and Wanlian Yuan (2010), “A Quick Incremental Updating Algorithm for Computing Core Attributes”, Yu et al (Eds): RSKT 2010, LNAI 6401, pp 249-256 2010 © Springer- Verlag Berlin Heidelberg JiYe Liang, Zongben Xu (2002), “The algorithm on knowledge reduction in incomplete information systems”, International Journal of Uncertainty, Fuzziness and Knowledge – Based Systems Vol 10 No 95-103 Jun Yang Zhangyan Xu (2005), “Different Core Attributes’s Comparison and Analysis”, School of information engineering and Department of 63 computer University of Science and Technology Beijing Guangxi Normal University, Ming Li, Xiao-Feng Zhang (August 2004), “Knowledge Entropy in Rough set Theory”, Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, 26-29 Wei-Dong Cai, Zhang-Yan Xu, Wei Song, and Bing-Ru Yang (2007), “A Quick Algorithm for Computing Core Based on the Possifive Region”, DOI 10.1109/SNPD.2007.87 10 Xiahua Tony Hu T Y Lin Jianchao Han (2003), “A New Rough Sets Model Based on Database Systems”, College of Information Science and Technology, Drexel University, Philadelphia, PA 19104, 11 Yang, C J., Ge, H., Yao, G.S., Ma, LS (June 2009), “Core and Atribute Reduction Agorithm Base on Compatible Discernibility Matrix”, The International Conference on Computational Intelligence and Natural Computing, CINC, Wuhan, China, vol.2, pp 103-106 12 Zhangyan Xu Wenhao Shu Bo Yang (2009), “New Algorithm for Computing the Core Based on Information Entropy”, International Conference on Artificial Intelligence and Computational Intelligence [...]... lượng là một thuộc tính Core của bảng Ở đây, đưa ra một thuật toán mới dựa trên toán tử cơ sở dữ liệu để có thuộc tính Core của một bảng quyết định Thuật toán tính Core dựa vào toán tử cơ sở dữ liệu [10] Input: Một bảng quyết định T(C, D) Output: Core – {tập thuộc tính Core của bảng T} Method: Core = ; For cjC { If Card((C-{cj}+D))  Card((C-{cj})) Then Core = Core {cj}; } Với k là số thuộc tính điều... Không tốt Đủ Chấp nhận u4 Tốt Không đủ Từ chối Core ={Khách hàng biết đến, Kho dự trữ} {Sự tín nhiệm, Kho dự trữ} = {Kho dự trữ} 16 Chƣơng 2 MỘT SỐ PHƢƠNG PHÁP TÍNH CORE DỰA VÀO LÝ THUYẾT TẬP THÔ 2.1 Core trong hệ thống thông tin nhất quán 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 Nhiều mô hình tập thô đã được phát triển bởi cộng đồng tập thô trong những thập kỷ cuối bao gồm mô... tính, C= {ci| i= 1,2,…,m} là tập thuộc tính điều kiện và D={d} là tập thuộc tính quyết định Output: Thuộc tính Core của T trong quan điểm thông tin, Core( C) Method: 1 Core( C) = ; 2 For mỗi thuộc tính điều kiện cj trong C If H({d}\C) < H({d}\C–{cj}) then Core( C) = Core( C){cj}; 3 Output Core( C); Tương tự thuật toán tính Core dựa vào toán tử hệ cơ sở dữ liệu, với k là số thuộc tính điều kiện Vòng lặp for... T=(U,C,D), một tập con của C, được ký hiệu bởi R được gọi là một tập rút gọn của hệ thống quyết định nếu R thỏa mãn hai điều kiện: (1) H(D\C) = H(D\R) (2) Đối với mỗi rR, H(D\R)  H(D\R–{r}) Core của hệ thống quyết định là tập: Core = {a|H(D\C)>H(D\C-{a})} 30 Thuật toán tính Core dựa vào entropy [4], [8] Input: Một bảng quyết định T=(U, A), trong đó, U là tập vũ trụ các đối tượng, A=CD là tập các thuộc tính, ... được: Core = ; Card((C- {Quang cảnh}+D)) =7  Card((C- {Quang cảnh}))=5; Core= {Quang cảnh}; Card((C- {Nhiệt độ}+D)) =Card((C- {Quang cảnh}))=7; Card((C- {Độ ẩm}+D)) =Card((C- {Độ ẩm}))=7; Card((C- {Gió}+D)) =7  Card((C- {Gió}))=5;  Core = {Quang cảnh, Gió} 2.1.2 Phương pháp tính Core dựa vào thông tin entropy Hiện tại nghiên cứu của lý thuyết tập thô có hai hướng chính: một là mở rộng lý thuyết. .. pháp đại số, vũ trụ là một tập hợp và tri thức là khả năng tạo phân đoạn của tập hợp Lý thuyết entropy là một khái niệm trong lý thuyết thông tin và nó có thể phân tích chất lượng thông tin Cho U là tập vũ trụ, P và Q là tập thuộc tính, phân chia tập vũ trụ theo giá trị của P và Q gọi là tri thức trên vũ trụ Vì tri thức được cấu trúc bởi quan hệ tương đương nên có thể nói rằng P và Q như là tập tri... hình tập thô tập trung mở rộng hạn chế của tập thô ban đầu như trình bày xác suất phân phối hoặc dữ liệu nhiễu và nhiều sự chú ý được xem là tạo ra mô hình tập thô mới để tìm tập Core, tập rút gọn hiệu quả trong cơ sở dữ liệu lớn Dựa vào kinh nghiệm về áp dụng các mô hình trong tập cơ sở dữ liệu lớn trong ứng dụng khai phá dữ liệu, ta tìm ra một trong những hạn chế nhất của tập thô là thuật toán tính Core, ... của lý thuyết tập thô và các lý thuyết khác như sự thống nhất của lý thuyết tập thô và phân tích khái niệm thông thường để nghiên cứu nó trong 20 quan điểm của khái niệm Ở đây, xét trong quan điểm của thông tin entropy và mô tả các khái niệm cơ bản trong tập thô bằng tri thức entropy [8] 2.1.2.1 Tri thức trong entropy [8] Lý thuyết tập thô truyền thống được định nghĩa trong quan điểm của phương pháp. .. 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... phương pháp này rất hiệu quả và có thể phát triển Dưới đây là một định nghĩa mới đầu tiên về Core, có thể không cần tập rút gọn dựa trên toán tử cơ sở dữ liệu Định nghĩa 2.1 [10] Một thuộc tính cj là một thuộc tính Core nếu nó thỏa điều kiện Card ((C- {cj}+D))  Card ((C- {cj})) 17 Định nghĩa 2.2 [10] Một thuộc tính cjC là một thuộc tính phân biệt được đối với D nếu kết quả phân loại của mỗi bộ ... biệt được, tập xấp xỉ, tập rút gọn 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 hệ thống thông tin quán, hai phương pháp tính Core hệ thống... tập 1.5 Tập rút gọn Core 13 Chƣơng - MỘT SỐ PHƢƠNG PHÁP TÍNH CORE DỰA VÀO LÝ THUYẾT TẬP THÔ 16 2.1 Core hệ thống thông tin quán 16 2.1.1 Phương pháp tính Core. .. cứu lý thuyết tập thô lý thuyết thông tin  Một số phương pháp tính Core hệ thống thông tin đầy đủ hệ thống thông tin không đầy đủ Phƣơng pháp nghiên cứu Tìm hiểu, tổng hợp số phương pháp tính Core