Luận văn: Core và các phương pháp tìm Core - Nguyễn Tri Thức (ĐH Quảng Nam)

Tài liệu nghiên cứu 1348 core và các phương pháp tìm core nguyễn tri thức luận văn đh quảng nam, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên sâu về .

• Trường học: Đại Học Quảng Nam
• Đề tài: 1348 Core Và Các Phương Pháp Tìm Core Nguyễn Tri Thức
• Loại tài liệu: Luận Văn

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỞ ĐẦU
• Lý do chọn đề tài
• Mục tiêu của đề tài
• Đối tượng và phạm vi nghiên cứu
• Đối tượng nghiên cứu
• Phạm vi nghiên cứu
• Phương pháp nghiên cứu
• Lịch sử nghiên cứu
• Đóng góp của đề tài
• Cấu trúc đề tài
• 1. CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN
• 1.1. Hệ thống thông tin
• 1.1.1. Khái niệm
• 1.1.2. Hệ thống thông tin đầy đủ
• 1.1.3. Hệ thống thông tin không đầy đủ
• 1.2. Bảng quyết định
• 1.3. Tập rút gọn và Core
• 1.3.1. Tập rút gọn
• 1.3.2. Core
• 1.3.3. Ví dụ
• 2. CHƯƠNG 2: MỘT SỐ PHƯƠNG PHÁP TÌM CORE
• 2.1. Các phương pháp cơ bản
• 2.1.1. Tìm Core theo định nghĩa
• 2.1.1.1. Định nghĩa
• 2.1.1.2. Thuật toán
• 2.1.1.3. Ví dụ
• 2.1.2. Tìm Core dựa vào phép toán đại số
• 2.2. Các phương pháp mở rộng
• 2.2.1. Tập Core và ma trận phân biệt được
• 2.2.1.1. Ma trận phân biệt được
• 2.2.1.2. Thuật toán tính Core
• 2.2.2. Tập Core và miền khẳng định
• 2.2.2.1. Miền khẳng định
• 2.2.2.2. Ma trận phân biệt rút gọn dựa trên miền khẳng định
• 2.2.3. Ví dụ
• 3. CHƯƠNG 3: ĐÁNH GIÁ PHƯƠNG PHÁP VÀ CÀI ĐẶT
• 3.1. Đánh giá phương pháp
• 3.1.1. Tìm Core theo định nghĩa
• 3.1.2. Tìm Core theo phương pháp đại số
• 3.1.3. Phương pháp tìm Core dựa vào ma trận phân biệt được
• 3.1.4. Phương pháp tìm Core dựa vào miền khẳng định
• 3.2. Dữ liệu mẫu
• 3.3. Chương trình
• 3.3.1. Giao diện chính
• 3.3.2. Giao diện kết nối cơ sở dữ liệu
• 3.3.3. Chạy chương trình
• KẾT LUẬN VÀ KIẾN NGHỊ
• Kết quả đạt được
• Kiến nghị
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC

Tóm tắt

I. Tổng quan Core và các phương pháp tìm Core trong luận văn ĐH Quảng Nam

Trong lĩnh vực khai phá dữ liệu, việc xử lý các tập dữ liệu khổng lồ và phức tạp là một thách thức lớn. Một trong những nhiệm vụ cốt lõi là giảm thiểu số lượng thuộc tính mà không làm mất thông tin quan trọng, từ đó tối ưu hóa quá trình phân tích và xây dựng mô hình. Khái niệm Core và tập rút gọn (reduct) ra đời như một giải pháp hiệu quả cho vấn đề này. Theo luận văn tốt nghiệp "Core và các phương pháp tìm Core" của sinh viên Nguyễn Tri Thức tại trường Đại học Quảng Nam khoa kỹ thuật (Công nghệ thông tin), Core được định nghĩa là tập hợp tất cả các thuộc tính điều kiện cần thiết và không thể thiếu trong một hệ thống thông tin. Đây là phần giao của tất cả các tập rút gọn có thể có của hệ thống. Việc xác định chính xác Core giúp loại bỏ các thuộc tính dư thừa, giảm độ phức tạp tính toán và tăng tốc độ xử lý dữ liệu. Luận văn này đã tổng hợp và phân tích sâu sắc các phương pháp tìm Core, từ những cách tiếp cận cơ bản dựa trên định nghĩa cho đến các kỹ thuật mở rộng sử dụng cấu trúc toán học phức tạp hơn. Nghiên cứu này không chỉ mang giá trị học thuật mà còn có ý nghĩa thực tiễn, cung cấp nền tảng cho việc xây dựng các thuật toán trích chọn đặc trưng thông minh, góp phần nâng cao hiệu quả của các bài toán phân lớp, dự đoán trong học máy và khai phá dữ liệu.

1.1. Hiểu đúng về Core và tập rút gọn trong khai phá dữ liệu

Trong một bảng quyết định, tập rút gọn là một tập con tối thiểu của các thuộc tính điều kiện mà vẫn duy trì được khả năng phân loại đối tượng giống như khi sử dụng toàn bộ tập thuộc tính ban đầu. Nói cách khác, nó là tập thuộc tính nhỏ nhất đủ để phân biệt các đối tượng có quyết định khác nhau. Core, hay lõi, là tập hợp các thuộc tính xuất hiện trong MỌI tập rút gọn. Một thuộc tính thuộc Core được xem là tuyệt đối cần thiết; nếu loại bỏ nó, khả năng phân loại của hệ thống sẽ suy giảm ngay lập tức. Ví dụ, nếu một hệ thống thông tin có hai tập rút gọn là {thuộc tính A, thuộc tính B} và {thuộc tính A, thuộc tính C}, thì Core sẽ là {thuộc tính A}. Việc hiểu rõ mối quan hệ giữa Core và tập rút gọn là nền tảng để áp dụng các thuật toán giảm chiều dữ liệu hiệu quả.

1.2. Tầm quan trọng của việc tìm Core trong luận văn thạc sĩ xây dựng dữ liệu

Việc xác định Core đóng vai trò then chốt trong các công trình nghiên cứu học thuật, đặc biệt là các luận văn thạc sĩ xây dựng mô hình dữ liệu. Tìm ra Core giúp nhà nghiên cứu tập trung vào các thuộc tính quan trọng nhất, từ đó xây dựng các mô hình dự đoán chính xác và dễ diễn giải hơn. Trong bối cảnh "bùng nổ dữ liệu", việc loại bỏ các thuộc tính nhiễu và không liên quan không chỉ giúp tiết kiệm tài nguyên tính toán mà còn cải thiện hiệu suất của thuật toán. Luận văn của Nguyễn Tri Thức đã nhấn mạnh rằng, tìm được Core là bước đầu tiên và quan trọng nhất trong quá trình trích chọn tri thức, tác động trực tiếp đến chất lượng của tri thức được khám phá. Đây là một bước không thể thiếu để đảm bảo sức chịu tải của đất nền tri thức không bị suy yếu bởi dữ liệu dư thừa.

II. Thách thức khi xử lý thuộc tính dư thừa trong hệ thống thông tin

Một trong những thách thức lớn nhất trong khai phá dữ liệu hiện đại là sự tồn tại của các thuộc tính dư thừa và không liên quan trong các hệ thống thông tin. Những thuộc tính này không chỉ làm tăng kích thước bộ nhớ cần thiết để lưu trữ mà còn gây ra "lời nguyền của số chiều" (curse of dimensionality), làm giảm hiệu quả và độ chính xác của nhiều thuật toán học máy. Thuộc tính dư thừa có thể che mờ các mẫu quan trọng, khiến mô hình bị quá khớp (overfitting) và khó khái quát hóa trên dữ liệu mới. Luận văn của Nguyễn Tri Thức chỉ ra rằng việc xác định đâu là thuộc tính cần thiết (core attributes) và đâu là thuộc tính có thể loại bỏ là một bài toán không hề tầm thường. Nếu loại bỏ sai thuộc tính, hệ thống có thể mất đi thông tin phân loại quan trọng. Ngược lại, nếu giữ lại quá nhiều, chi phí tính toán sẽ tăng vọt. Do đó, việc phát triển các phương pháp tìm Core hiệu quả và chính xác là yêu cầu cấp thiết để xây dựng các hệ thống thông tin thông minh và tinh gọn, đảm bảo mọi phân tích mẫu đất đá dữ liệu đều dựa trên những thông tin cốt lõi nhất.

2.1. Phân biệt thuộc tính cốt yếu và không cốt yếu trong bảng quyết định

Trong một bảng quyết định, không phải tất cả các thuộc tính điều kiện đều có vai trò như nhau. Một thuộc tính được gọi là cốt yếu (essential) nếu việc loại bỏ nó sẽ làm thay đổi khả năng phân loại của hệ thống, tức là tồn tại ít nhất hai đối tượng có quyết định khác nhau nhưng lại trở nên không phân biệt được sau khi bỏ thuộc tính đó. Các thuộc tính cốt yếu này chính là thành phần tạo nên Core. Ngược lại, thuộc tính không cốt yếu (dispensable) có thể được loại bỏ mà không ảnh hưởng đến mối quan hệ phụ thuộc giữa thuộc tính điều kiện và thuộc tính quyết định. Thách thức nằm ở việc thiết kế một quy trình khoan khảo sát dữ liệu có hệ thống để xác định chính xác tập hợp các thuộc tính cốt yếu này một cách hiệu quả về mặt tính toán.

2.2. Ảnh hưởng của dữ liệu nhiễu đến quá trình tìm Core chính xác

Dữ liệu trong thực tế thường chứa nhiễu hoặc các giá trị thiếu, điều này gây ra khó khăn đáng kể cho các phương pháp tìm Core. Các giá trị nhiễu có thể tạo ra các phụ thuộc giả, dẫn đến việc một thuộc tính không quan trọng bị xác định nhầm là thuộc Core. Tương tự, dữ liệu thiếu trong hệ thống thông tin không đầy đủ làm cho việc so sánh các đối tượng trở nên phức tạp. Luận văn đã đề cập đến sự cần thiết phải có các bước tiền xử lý dữ liệu cẩn thận trước khi áp dụng thuật toán tìm Core. Việc xử lý nhiễu và điền các giá trị bị thiếu một cách hợp lý là điều kiện tiên quyết để đảm bảo báo cáo kết quả khoan lõi dữ liệu (kết quả tìm Core) có độ tin cậy cao và phản ánh đúng bản chất của địa tầng và cấu trúc địa chất của dữ liệu.

III. Hướng dẫn 2 phương pháp tìm Core cơ bản từ luận văn Nguyễn Tri Thức

Luận văn của Nguyễn Tri Thức đã trình bày chi tiết hai phương pháp cơ bản để xác định Core của một hệ thống thông tin, cung cấp một nền tảng vững chắc cho những người mới bắt đầu nghiên cứu lĩnh vực này. Hai phương pháp này, tuy đơn giản về mặt lý thuyết, nhưng lại rất hiệu quả trong việc minh họa bản chất của Core và tập rút gọn. Phương pháp đầu tiên là "Tìm Core theo định nghĩa", một cách tiếp cận trực tiếp bằng cách liệt kê tất cả các tập rút gọn có thể có và sau đó tìm phần giao của chúng. Phương pháp thứ hai là "Tìm Core dựa vào phép toán đại số", sử dụng một định lý toán học để kiểm tra tính cần thiết của từng thuộc tính một cách độc lập mà không cần tìm tất cả các tập rút gọn. Mỗi phương pháp có ưu và nhược điểm riêng, phù hợp với các loại bảng quyết định có quy mô và độ phức tạp khác nhau. Việc nắm vững hai kỹ thuật này là bước khởi đầu quan trọng trước khi đi sâu vào các thuật toán phức tạp hơn như sử dụng ma trận phân biệt được hay miền khẳng định, tương tự như việc phải nắm vững kỹ thuật khoan xoay cơ bản trước khi thực hiện các dự án khảo sát địa chất công trình phức tạp.

3.1. Quy trình tìm Core theo định nghĩa thông qua tập rút gọn

Phương pháp này bám sát định nghĩa lý thuyết: Core là giao của tất cả các tập rút gọn. Quy trình khoan khảo sát dữ liệu bao gồm hai bước chính: (1) Tìm tất cả các tập rút gọn của tập thuộc tính điều kiện. Quá trình này thường bắt đầu với toàn bộ tập thuộc tính, sau đó thử loại bỏ lần lượt từng thuộc tính và kiểm tra xem khả năng phân loại của hệ thống có bị ảnh hưởng hay không. Một tập con là tập rút gọn nếu nó vẫn duy trì khả năng phân loại và không có tập con thực sự nào của nó có tính chất này. (2) Sau khi đã có danh sách tất cả các tập rút gọn, ta thực hiện phép giao (intersection) trên các tập này để tìm ra Core. Mặc dù phương pháp này rất trực quan và dễ hiểu, nó có thể trở nên không khả thi về mặt tính toán đối với các bộ dữ liệu có số lượng thuộc tính lớn do số lượng tập rút gọn có thể tăng theo cấp số nhân.

3.2. Cách tiếp cận tìm Core hiệu quả dựa trên phép toán đại số

Phương pháp đại số cung cấp một cách tiếp cận hiệu quả hơn để xác định Core mà không cần phải tìm tất cả các tập rút gọn. Nó dựa trên định lý: "Một thuộc tính c thuộc Core khi và chỉ khi việc loại bỏ nó ra khỏi tập thuộc tính điều kiện ban đầu làm thay đổi mối quan hệ phụ thuộc". Cụ thể, thuật toán sẽ xét từng thuộc tính điều kiện c. Với mỗi c, ta tạm thời loại bỏ nó và kiểm tra xem trong tập dữ liệu mới có xuất hiện mâu thuẫn hay không (tức là có hai đối tượng giống hệt nhau về các thuộc tính còn lại nhưng lại có quyết định khác nhau). Nếu mâu thuẫn xuất hiện, thuộc tính c đó là cần thiết và được đưa vào Core. Quá trình này được lặp lại cho tất cả các thuộc tính. Cách tiếp cận này trực tiếp kiểm tra tính cốt yếu của từng thuộc tính, giúp giảm đáng kể độ phức tạp so với việc tìm tất cả các tập rút gọn.

IV. Bí quyết tìm Core nâng cao với ma trận phân biệt và miền khẳng định

Ngoài các phương pháp cơ bản, luận văn cũng đi sâu vào các kỹ thuật mở rộng, mang lại hiệu quả cao hơn khi xử lý các bài toán phức tạp. Hai trong số các phương pháp nổi bật nhất là sử dụng ma trận phân biệt được (discernibility matrix) và miền khẳng định (positive region). Đây là những công cụ toán học mạnh mẽ trong lý thuyết tập thô (Rough Set Theory) cho phép phân tích mối quan hệ giữa các đối tượng và thuộc tính một cách có hệ thống. Ma trận phân biệt được lưu trữ thông tin về những thuộc tính có thể phân biệt từng cặp đối tượng có quyết định khác nhau. Từ ma trận này, việc tìm Core và các tập rút gọn trở thành một bài toán logic. Trong khi đó, phương pháp dựa trên miền khẳng định tập trung vào việc đánh giá chất lượng mẫu lõi dữ liệu bằng cách xác định tập hợp các đối tượng có thể được phân loại một cách chắc chắn dựa trên một tập thuộc tính. Một thuộc tính được xem là thuộc Core nếu việc loại bỏ nó làm giảm kích thước của miền khẳng định. Những kỹ thuật này, được phân tích tại trường Đại học Quảng Nam, đại diện cho sự tiến bộ trong việc tự động hóa quá trình trích chọn tri thức.

4.1. Ứng dụng ma trận phân biệt được để xác định thuộc tính cần thiết

Ma trận phân biệt được M là một ma trận đối xứng, trong đó mỗi phần tử M(i, j) chứa tập hợp các thuộc tính có giá trị khác nhau giữa đối tượng i và đối tượng j. Tuy nhiên, ta chỉ quan tâm đến các cặp đối tượng (i, j) có thuộc tính quyết định khác nhau. Khi đó, M(i, j) chính là tập các thuộc tính tối thiểu cần có để phân biệt được hai đối tượng này. Core được xác định một cách đơn giản là tập hợp các thuộc tính xuất hiện dưới dạng một phần tử đơn (singleton) trong ma trận. Tức là, nếu M(i, j) = {c} cho một cặp (i, j) nào đó, thì thuộc tính c là thuộc tính duy nhất có thể phân biệt chúng, do đó c chắc chắn phải thuộc Core. Phương pháp này chuyển bài toán tìm Core về việc xây dựng và phân tích ma trận, một cách tiếp cận có cấu trúc và dễ cài đặt.

4.2. Kỹ thuật tìm Core dựa trên khái niệm miền khẳng định Positive Region

Miền khẳng định POSc(D) của tập quyết định D đối với tập điều kiện C là tập hợp tất cả các đối tượng trong vũ trụ U có thể được phân loại một cách duy nhất vào các lớp của D chỉ dựa vào thông tin từ C. Một thuộc tính c trong C được coi là cốt yếu và thuộc Core nếu miền khẳng định bị thu hẹp khi loại bỏ c ra khỏi C. Tức là, c ∈ Core nếu và chỉ nếu POSc(D) ≠ POSc-{c}(D). Phương pháp này đo lường tầm quan trọng của một thuộc tính thông qua sự đóng góp của nó vào khả năng phân loại tổng thể của hệ thống. Đây là một cách tiếp cận mạnh mẽ, đặc biệt hữu ích trong các hệ thống thông tin không nhất quán (inconsistent), nơi không phải tất cả các đối tượng đều có thể được phân loại một cách chắc chắn. Việc này cũng tương tự như thí nghiệm mẫu lõi để xác định các thành phần quan trọng nhất.

V. Đánh giá và so sánh các phương pháp tìm Core trong luận văn ĐH Quảng Nam

Chương cuối của luận văn "Core và các phương pháp tìm Core" của Nguyễn Tri Thức tập trung vào việc đánh giá và so sánh hiệu quả của các phương pháp đã trình bày. Mỗi phương pháp được phân tích dựa trên các tiêu chí như độ phức tạp tính toán, thời gian thực thi, khả năng xử lý các bộ dữ liệu lớn và độ nhạy với dữ liệu nhiễu. Phương pháp tìm Core theo định nghĩa, mặc dù dễ hiểu, được đánh giá là không hiệu quả về mặt thời gian khi số lượng thuộc tính tăng lên. Phương pháp đại số cho thấy sự cải thiện đáng kể về tốc độ đối với các bộ dữ liệu vừa và nhỏ. Tuy nhiên, đối với các hệ thống thông tin quy mô lớn, các phương pháp dựa trên ma trận phân biệt được và miền khẳng định tỏ ra vượt trội hơn hẳn. Luận văn cũng trình bày kết quả cài đặt demo một số thuật toán, cho phép so sánh trực quan hiệu năng của chúng trên các bộ dữ liệu mẫu. Những đánh giá chất lượng mẫu lõi (RQD) này cung cấp cái nhìn sâu sắc và những kiến nghị quý báu cho các nhà nghiên cứu trong việc lựa chọn phương pháp tìm Core phù hợp nhất cho bài toán cụ thể của mình.

5.1. Phân tích ưu nhược điểm của từng thuật toán tìm Core cụ thể

Luận văn đã chỉ ra rằng không có một phương pháp nào là tối ưu cho mọi trường hợp. Phương pháp theo định nghĩa có ưu điểm là đảm bảo tìm ra kết quả chính xác theo lý thuyết nhưng nhược điểm là chi phí tính toán rất cao. Phương pháp đại số nhanh hơn nhưng vẫn có thể gặp khó khăn với dữ liệu lớn. Phương pháp dùng ma trận phân biệt được có ưu điểm là cấu trúc rõ ràng, nhưng việc xây dựng và lưu trữ ma trận có thể tốn bộ nhớ. Phương pháp miền khẳng định linh hoạt và mạnh mẽ, đặc biệt với dữ liệu không nhất quán, nhưng đòi hỏi sự am hiểu sâu về lý thuyết tập thô. Việc lựa chọn phụ thuộc vào đặc điểm của bộ dữ liệu như số lượng đối tượng, số lượng thuộc tính và mức độ nhiễu, tương tự như việc chọn tiêu chuẩn lấy mẫu lõi phù hợp cho từng loại cọc khoan nhồi.

5.2. Kết quả nghiên cứu và kiến nghị từ luận văn tốt nghiệp tại Quảng Nam

Công trình nghiên cứu của Nguyễn Tri Thức tại Đại học Quảng Nam đã đạt được mục tiêu tổng hợp, phân tích và so sánh một cách hệ thống các phương pháp tìm Core. Kết quả demo chương trình đã minh họa thành công hoạt động của các thuật toán trên dữ liệu mẫu. Dựa trên các phân tích, luận văn đưa ra kiến nghị về việc kết hợp các phương pháp hoặc phát triển các thuật toán heuristic để tối ưu hóa quá trình tìm Core trên các bộ dữ liệu siêu lớn (big data). Hướng phát triển trong tương lai có thể bao gồm việc nghiên cứu các thuật toán tìm Core song song hoặc phân tán, cũng như áp dụng các kỹ thuật này vào các lĩnh vực cụ thể như y sinh, tài chính, hay kỹ thuật, nơi việc trích chọn đặc trưng cốt lõi mang lại giá trị thực tiễn to lớn. Đây là một đóng góp quan trọng, cung cấp một tài liệu tham khảo chi tiết và hữu ích cho cộng đồng nghiên cứu khai phá dữ liệu.

Trích đoạn nội dung tài liệu

Chương 1: Các khái niệm cơ bản > Nghiên cứu, tìm hiểu tổng quan, trích chọn, trình bày một số khái niệm cơ bản về khai phá dữ liệu và Core. Chương 2: Một số phương pháp tìm Core > Trình bày một số phương pháp tính Core. Chương 3: Cài đặt và ứng dụng > Demo một số thuật toán tính Core. > So sánh, đánh giá các phương pháp.

“Trang 2 PHAN 2: NOI DUNG NGHIEN CUU CHUONG 1: CAC KHAI NIEM CO BAN 1. Hệ thống thông tin 1. Khái niệm Hệ thống thông tin là một cặp (U, A). Trong đó: U là ác đôi tượng hữu hạn không rồng (được gọi là tập vũ trụ các đối tượng) và A là tập các thuộc tính hữu hạn không rỗng và với mọi a e A, ta có, A: U > V, và ta ký hiệu V, là tập gid tri cua a.

Mat khác nếu u U và a e A thì ta sẽ ký hiệu u(a) € V, là giá trị thuộc tính a của đối tượng u. Ví dụ U Dau dau Đau cơ Thân nhiệt _. uy Có | Có Bình thường | u | Có Có Cao | us Có Có Rất cao tạ Không Có Bình thường Us Không Không Cao ug Khéng Có | Rất cao Trong đó: ~ Tập đối tượng U = (u¡,u;,u›,u;ms,u,) ập thuộc tính A = (Đau đầu, Đau cơ, Thân nhiệt) 1. Hệ thống thông tin đầy đủ Hệ thống thông tin đầy đủ là một hệ thống thông tin có day đủ các giá trị thuộc tính.

Hệ thống thông tin không đầy đủ Hé thống thông tin A được gọi là không, day đủ nếu tổn tại thuộc tính acA. và đối tượng u < U ma gia trị u(a) bị mat hay nói cách khác Vạ chứa gia tri null. Hoặc, hệ thống thông tin không đầy đủ là hệ thống thông tin bị thiếu một số giá trị thuộc tính trên một số đối tượng nào đó, tức là chứa giá trị thiếu vì nhiều lý đo khác nhau. Giá trị thiếu trong bảng thường ký hiệu bởi ký tự * hay bởi ký tự ? Trang 3 Ví dụ: U | Đanđầu Đau cơ Thân nhiệt | u C6 C6 — | Bìhthường| u | Có * Cao | Us * Có Rất cao.

Ug Không Có Bình thường Us * Không Cao U6 Khong * Rat cao 1. Bảng quyết định Bảng quyết định là một hệ thống thông tin có dang T = (U, C +¿ D), với: A=CUD, CAD = 6, trong đó € là tập thuộc tính điêu kiện còn D là tập thuộc tính quyết định. Vi du: U Dau dau Dau co “Thân nhiệt | Cảm cúm u; Có | Có Bình thường | Không „| Có, Có co Có Us Có | Có Rat cao Có u¿| Không Có Bình thường | Không Us Khéng Khéng Cao Không U6 Không | Có Rất cao Có Ở đây: > Các thuộc tính điều kiện C là: Dau đầu, Dau cơ, Thân nhiệt > Thuộc tính quyết định D là: Cảm cúm 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. Tập rút gọn và Core 1 1.

Tập rút gọn Có một số tập chỉ giữ c thuộc tính mà duy trì quan hệ không phân biệt được và cũng vì thế duy trì xấp xỉ của tập. Có nhiều tập con thuộc tính như thế và 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 trì thức. Cụ thể, cho c e C, ta có định nghĩa sau: Trang 4 Thuộc tính c là không can thiết trong T nếu POS.,(D), ngược lại thuộc tính e là cần thiết trong T.

>_C- miền khẳng định của D; POS,(D)= |J €X xi > T=(U,C, D) là độc lập nếu tất cả c e C là cần thiết trong T. Tập các thuộc tính R c 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,(Ð) = POS,. Core 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 ra khỏi một số thuộc tính điều kiện có thể không cần thiết thì ta đượ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 điều kiện € là tập thuộc tính điều kiện B C C giữ nguyên khả năng phân loại của C, hay IND(B) = IND(C). Ta thấy, 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 P, 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ụ Cho hệ thống thông tin: U |Đauđầu Daucơ Thân nhiệt | Cảm cúm tụ Có Có _ Bìnhthường | Không lu | có Có Cao Có tw | Có Có Ratcao | Có | w | Không | Có jBìnhthường Không u | Không | Không Cao Không u | Không Có Rất cao Có ' > Reduct] = { Đau cơ, Thân nhiệt } Trang 5 U Đau cơ | Thân nhiệt | Cảm cúm tị tạ Có Bình thường | _ Không tạ Có Cao Có U3 Us Có Rất cao Có us | Không Cao Không > Reduct2 = { Đau đầu, Thân nhiệt } U |Đauđầu| Thân nhiệt | Cảm cúm uy Có Bình thường |_ Không WwW Có Cao Có Us Có Rất cao Có u¿ | Không | Bình thường | Không | us | Không Cao Không | us | Không | Rat cao Có s* Core = {Đau cơ,Thân nhiệt } ¬ {Đau đầu,Thân nhiệt} = { Thân nhiệt} Trang 6 CHƯƠNG 2: MỘT SỐ PHƯƠNG PHÁP TÌM CORE 2. Các phương pháp cơ bản 2. Tìm Core theo định nghĩa 2. Định nghĩa 4) Tập rút gọn Rút gọn của hệ thống thông tin: cho hé théng théng tin (U,A), tap RCA được gọi là tập rút gọn của A (hay hệ thống) nếu R 1a tap nho nhat thoa ROA đúng trên U.

Rút gọn của bảng quyết định: cho bảng quyết dinh (U, C U D) tap RoC được gọi là tập rút gọn của bảng quyết định (hay tập thuộc tính điều kiện C) nếu R là tập nhỏ nhất thỏa R —> D đúng trên U. b) Core Core = () R ReRED 2. Thuật toán ay tưởng Dựa vào định nghĩa để tìm tập rút gọn, từ đó tìm Core cho bảng quyết định. b) Thuật toán Input: U, C, D.

Output: Core Method: Gan Core = Ø For each R do Begin Gan R = C tim tap nit gọn của bảng quyết định Forc € R do IF (R\{e}—>D) then loại e ra khỏi R Core = Core VR End “Thực hiện cho đến khi tìm được đầy đủ các tập rút gọn Tim Core Core = QM R ReRrD Trang 7 2. Vidu a) Vĩ dụ 1 Cho bảng quyết định: U | Đauđầu Đaucơ | Thânnhiệt uw Có Có Bình thường tạ Có Có Cao u Có Có Rat cao uy Không | C6 Bình thường | _ Không Us Khéng | Khong Cao Không Us không | C6 Rat cao Có Với € = {Đau dau, Dau cơ, Thân nhiệt} và D = {Cam cam} Mô tả bài toán: Với quyết định cần được đưa ra là một người có mắc bệnh cảm cúm hay không, ta phải xét đồng thời ba thuộc tính điều kiện: Đau dầu, Đau cơ, Thân nhiệt. Trong tập thuộc tính điều kiện trên, cần xác định được những thuộc tính quan trọng, không thê thiếu cho việc đưa ra quyết định. Với phương pháp tìm Core dựa vào định nghĩa, ta thực hiện các bước như sau: * Gan R=C * Trường hợp l: - Xét c = {Dau dau} -R\ {Dau dau} = {Dau cơ, Thân nhiệt} - Xây dựng bảng I: Bang 1 [ut [ Đau cơ | Thân nhiệt | Cảm cúm ty uy Có Bình thường |_ Không uạ Có Cao Có tu Có Rất cao Có Us Không Cao Không ~ Trong bảng 1: tập thuộc tính điều kiện R \ {Đau đầu) suy dẫn ra được thuộc tính quyết định {Cảm cúm}, nên: > Gán: Rị =R \ {Dau dau} = {Đau cơ, Thân nhiệt} Trang 8 > Trường hợp 1.1: Xét c = {Đau cơ} - R¿ \ {Đau cơ} = {Thân nhiệt} - Xây dựng bảng 2: Bang 2 U Thân nhiệt Cảm cúm -uu¿ - Bình thường không | | Up Cao Có Us Ug RAt cao Có Us Cao Khéng - Trong bảng 2: xuất hiện mâu thuẫn giữa 2 nhóm đối tượng: (u;) va (Us) - Hay: tập thuộc tính diéu kién R, \ {Đau cơ} không suy dẫn ra được thuộc tính quyết định {Cảm cúm}, nên: Rị ¡ = R; Œ®) > Trường hợp 1.2: Xét e = {Thân nhiệt} ~ Rị \ {Thân nhiệt} = {Đau cơ} - Xây dựng bảng 3: Bang 3 Đaucơ | Cảm cúm Uy Uy Có Không Up Us Us Có Có Us Không Không - Trong bảng 3: xuất hiện mâu thuẫn giữa 2 nhóm đối tượng: (u2,U3,Us) va (us) - Hay, tập thuộc tính điều kiện: R, \ {Thân nhiệt} không suy dẫn ra được thuộc tính quyết định {Cảm cúm}, nên: Rị;= Rị (**) - Từ (*) và(**), kết thúc trường hợp 1 được l tập rút gọn: Rị = {Đau cơ, Thân nhiệt} ** Trường hợp 2: - Xét c = {Đau cơ} ~ R\ {Đau co} = {Dau dau, Thân nhiệt} - Xây dựng bảng 4: Trang 9 Bảng 4 U j Đauđầu | Thânnhiệt | Cảm cúm uy; Có Bình thường |_ Không up Có Cao Có uy Có ¡ Rấtcao Có Us Không | Binh thường Us Không | Cao Ug Khéng Rất cao ~ Trong bảng 4: tập thuộc tính điều kiện: R \ {Đau cơ} suy dẫn ra được thuộc tính quyết định {Cảm cúm}, nên: > Gán: Rạ= R\ {Đau cơ} = {Đau đầu, Thân nhiệt} > Trường hợp 2.1: xét = {Đau đầu} ~ R¿\ {Dau dau} = {Thân nhiệt} trùng với trường hợp I.

- Hay R;¡ = Rạ(*) > Trường hợp 2.