Thuật toán rút gọn bảng quyết định nhất quán - Trường Đại học CNTT & Truyền Thông

I. Toàn cảnh về thuật toán rút gọn bảng quyết định nhất quán

Trong bối cảnh bùng nổ dữ liệu, việc trích xuất tri thức hữu ích từ các tập dữ liệu khổng lồ đã trở thành một yêu cầu cấp thiết. Một trong những thách thức lớn nhất là xử lý các thuộc tính dư thừa, gây nhiễu và làm tăng chi phí tính toán. Thuật toán rút gọn bảng quyết định nhất quán ra đời như một giải pháp hiệu quả để giải quyết vấn đề này. Về cơ bản, một bảng quyết định là một dạng đặc biệt của hệ thông tin, nơi các thuộc tính được phân chia thành hai nhóm: thuộc tính điều kiện (nguyên nhân) và thuộc tính quyết định (kết quả). Một bảng quyết định được gọi là nhất quán khi các đối tượng có cùng giá trị thuộc tính điều kiện cũng phải có cùng giá trị thuộc tính quyết định. Mục tiêu của thuật toán rút gọn là tìm ra một tập con nhỏ nhất của các thuộc tính điều kiện mà vẫn bảo toàn được khả năng phân lớp của bảng quyết định gốc. Quá trình này không chỉ giúp giảm kích thước dữ liệu, tăng tốc độ xử lý mà còn cải thiện độ chính xác của các mô hình dự báo bằng cách loại bỏ thông tin không cần thiết. Các phương pháp rút gọn thuộc tính thường dựa trên nền tảng của lý thuyết tập thô (Rough Set Theory), sử dụng các khái niệm như tập rút gọn (reduct) và tập lõi (core) để xác định các thuộc tính quan trọng nhất. Luận văn "Nghiên cứu một số thuật toán liên quan đến tập rút gọn trên bảng quyết định nhất quán" của tác giả Dương Đức Nguyên (2013) đã đi sâu vào việc xây dựng các thuật toán hiệu quả, đặc biệt là hướng tiếp cận sử dụng metric để đánh giá và lựa chọn thuộc tính, mở ra một hướng đi đầy hứa hẹn trong lĩnh vực khai phá dữ liệu.

1.1. Bảng quyết định nhất quán là gì và vai trò của nó

Một bảng quyết định là một hệ thống thông tin DS=(U, C ∪ D), trong đó U là tập các đối tượng, C là tập thuộc tính điều kiện và D là tập thuộc tính quyết định. Bảng quyết định được xem là nhất quán nếu một phụ thuộc hàm C → D là đúng. Điều này có nghĩa là, với hai đối tượng bất kỳ trong U, nếu chúng không thể phân biệt được dựa trên tất cả các thuộc tính trong C, thì chúng cũng không thể phân biệt được dựa trên các thuộc tính trong D. Nói cách khác, các thuộc tính điều kiện đủ để xác định duy nhất giá trị của thuộc tính quyết định. Vai trò của bảng quyết định nhất quán là vô cùng quan trọng trong các bài toán phân lớp và ra quyết định. Nó cung cấp một mô hình rõ ràng, dễ hiểu về mối quan hệ nhân quả giữa các yếu tố đầu vào và kết quả đầu ra, làm cơ sở để xây dựng các hệ thống hỗ trợ quyết định, chẩn đoán y khoa, hay phân tích hành vi khách hàng. Tính nhất quán đảm bảo rằng các quy tắc được sinh ra từ bảng dữ liệu là đáng tin cậy và không mâu thuẫn.

1.2. Tầm quan trọng của việc rút gọn thuộc tính trong KPDL

Rút gọn thuộc tính là một trong những ứng dụng quan trọng nhất của lý thuyết tập thô trong khai phá dữ liệu (KPDL). Mục tiêu chính là loại bỏ các thuộc tính không cần thiết hoặc dư thừa ra khỏi tập thuộc tính điều kiện C mà không làm thay đổi khả năng phân loại của bảng quyết định. Tầm quan trọng của quá trình này thể hiện ở ba khía cạnh chính. Thứ nhất, nó giúp giảm thiểu đáng kể khối lượng tính toán và yêu cầu lưu trữ, cho phép áp dụng các thuật toán trên những cơ sở dữ liệu có quy mô lớn. Thứ hai, việc loại bỏ các thuộc tính nhiễu giúp cải thiện hiệu suất và độ chính xác của các mô hình học máy. Cuối cùng, một tập thuộc tính nhỏ hơn giúp con người dễ dàng hiểu và diễn giải các quy tắc hoặc tri thức được khám phá, từ đó đưa ra các quyết định sáng suốt hơn. Việc tìm ra một tập rút gọn tối ưu là một bài toán NP-hard, do đó các thuật toán heuristic được phát triển để tìm kiếm các giải pháp gần tối ưu một cách hiệu quả.

II. Thách thức trong việc rút gọn thuộc tính Tại sao cần tối ưu

Mặc dù lợi ích của việc rút gọn thuộc tính là không thể bàn cãi, quá trình thực hiện lại đối mặt với nhiều thách thức đáng kể. Thách thức lớn nhất đến từ độ phức tạp tính toán. Với một bảng quyết định có n thuộc tính điều kiện, số lượng các tập con thuộc tính có thể có là 2^n, một con số tăng theo hàm mũ. Việc kiểm tra tất cả các khả năng để tìm ra tập rút gọn nhỏ nhất là bất khả thi đối với các bộ dữ liệu lớn. Điều này đòi hỏi phải có các thuật toán rút gọn bảng quyết định nhất quán hiệu quả, thường là các thuật toán heuristic, để tìm ra một giải pháp tốt trong thời gian chấp nhận được. Một thách thức khác là việc xác định đúng các thuộc tính cốt lõi và dư thừa. Không phải tất cả các thuộc tính không nằm trong tập lõi đều là dư thừa hoàn toàn. Một số có thể thay thế cho nhau, tạo ra nhiều tập rút gọn khác nhau. Việc lựa chọn tập rút gọn nào để sử dụng phụ thuộc vào tiêu chí đánh giá và mục tiêu của bài toán cụ thể. Hơn nữa, dữ liệu trong thực tế thường chứa nhiễu và các giá trị thiếu, làm phức tạp thêm việc đánh giá sự phụ thuộc giữa các thuộc tính. Việc tối ưu hóa các thuật toán không chỉ là giảm thời gian chạy mà còn là đảm bảo rằng tập rút gọn tìm được thực sự có ý nghĩa, giữ lại được bản chất thông tin của dữ liệu gốc và có khả năng khái quát hóa tốt trên dữ liệu mới.

2.1. Vấn đề dư thừa thuộc tính và độ phức tạp tính toán

Sự dư thừa thuộc tính xảy ra khi thông tin của một thuộc tính đã được chứa đựng trong một hoặc nhiều thuộc tính khác. Việc loại bỏ thuộc tính này không làm mất mát thông tin cần thiết cho việc phân lớp. Tuy nhiên, việc xác định sự dư thừa không phải lúc nào cũng đơn giản. Một thuộc tính có thể dư thừa khi xét cùng một nhóm thuộc tính này, nhưng lại cần thiết khi xét cùng một nhóm khác. Vấn đề này dẫn đến sự tồn tại của nhiều tập rút gọn khác nhau cho cùng một bảng quyết định. Như đã đề cập, tìm tất cả các tập rút gọn là một bài toán có độ phức tạp tính toán rất cao. Các thuật toán truyền thống thường có độ phức tạp thời gian theo hàm mũ so với số lượng thuộc tính, khiến chúng không thể áp dụng cho các bài toán thực tế với hàng trăm hoặc hàng nghìn thuộc tính. Do đó, nghiên cứu tập trung vào việc phát triển các phương pháp heuristic thông minh để giảm không gian tìm kiếm và nhanh chóng hội tụ đến một giải pháp chất lượng cao.

2.2. Phân biệt khái niệm tập rút gọn tập lõi và thuộc tính dư thừa

Để hiểu rõ về thuật toán rút gọn bảng quyết định nhất quán, cần phân biệt rõ ba khái niệm cốt lõi. Tập lõi (core) là tập hợp tất cả các thuộc tính cần thiết (indispensable). Một thuộc tính được gọi là cần thiết nếu việc loại bỏ nó sẽ làm giảm khả năng phân lớp của bảng quyết định. Nói cách khác, tập lõi là giao của tất cả các tập rút gọn. Tập rút gọn (reduct) 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 lớp ban đầu. Tối thiểu ở đây có nghĩa là không thể loại bỏ thêm bất kỳ thuộc tính nào khỏi tập rút gọn mà không làm ảnh hưởng đến kết quả. Một bảng quyết định có thể có nhiều tập rút gọn khác nhau. Thuộc tính dư thừa (redundant) là thuộc tính không thuộc bất kỳ tập rút gọn nào. Việc loại bỏ các thuộc tính này hoàn toàn không ảnh hưởng đến khả năng phân lớp của hệ thống. Hiểu rõ các khái niệm này là nền tảng để xây dựng và đánh giá các thuật toán rút gọn.

III. Phương pháp rút gọn thuộc tính dựa trên lý thuyết tập thô

Lý thuyết tập thô, do Zdzisław Pawlak đề xuất vào những năm 1980, cung cấp một nền tảng toán học vững chắc cho việc xử lý dữ liệu không chắc chắn và không đầy đủ, và là công cụ cốt lõi cho thuật toán rút gọn bảng quyết định nhất quán. Phương pháp tiếp cận chính của lý thuyết này dựa trên quan hệ không phân biệt (indiscernibility relation). Với một tập thuộc tính B, hai đối tượng được coi là không phân biệt được nếu chúng có cùng giá trị cho tất cả các thuộc tính trong B. Quan hệ này tạo ra một phân hoạch trên tập các đối tượng, trong đó mỗi khối bao gồm các đối tượng không thể phân biệt được với nhau. Dựa trên phân hoạch này, bất kỳ tập đối tượng nào cũng có thể được xấp xỉ bởi hai tập: xấp xỉ dưới và xấp xỉ trên. Xấp xỉ dưới chứa các đối tượng chắc chắn thuộc về tập, trong khi xấp xỉ trên chứa các đối tượng có khả năng thuộc về tập. Sự khác biệt giữa hai tập xấp xỉ này định nghĩa miền biên, thể hiện mức độ mơ hồ của tập hợp. Trong bài toán rút gọn, mục tiêu là tìm một tập thuộc tính B ⊆ C nhỏ nhất sao cho phân hoạch sinh bởi B liên quan đến thuộc tính quyết định D là không đổi. Điều này thường được đo lường thông qua miền dương (positive region), POSB(D), là tập hợp các đối tượng có thể được phân lớp một cách chắc chắn vào các lớp quyết định chỉ dựa trên các thuộc tính trong B. Một tập B được gọi là tập rút gọn nếu POSB(D) = POSC(D) và B là tối thiểu.

3.1. Mô hình tập thô và các khái niệm xấp xỉ trên xấp xỉ dưới

Trong lý thuyết tập thô, dữ liệu được biểu diễn trong một hệ thông tin IS=(U, A). Với một tập con thuộc tính B ⊆ A, ta có các lớp tương đương của phân hoạch U/B. Để biểu diễn một tập đối tượng X ⊆ U, người ta sử dụng hai khái niệm xấp xỉ. B-xấp xỉ dưới của X, ký hiệu BX, là tập hợp tất cả các đối tượng mà lớp tương đương của nó hoàn toàn nằm trong X. Đây là tập các thành viên chắc chắn của X. B-xấp xỉ trên của X, ký hiệu BX, là tập hợp tất cả các đối tượng mà lớp tương đương của nó có phần giao khác rỗng với X. Đây là tập các thành viên có thể của X. Tập X được gọi là tập thô nếu xấp xỉ dưới và xấp xỉ trên của nó khác nhau, và ngược lại là tập rõ. Các khái niệm này là nền tảng để định lượng sự không chắc chắn và xây dựng các quy tắc quyết định.

3.2. Định nghĩa tập rút gọn Pawlak và miền dương POSC D

Trong ngữ cảnh của bảng quyết định, miền dương POSC(D) là tập hợp các đối tượng trong U có thể được phân loại một cách duy nhất vào các lớp của thuộc tính quyết định D chỉ bằng cách sử dụng thông tin từ tập thuộc tính điều kiện C. Bảng quyết định là nhất quán khi và chỉ khi POSC(D) = U. Một tập con R ⊆ C được gọi là một tập rút gọn Pawlak (hoặc tập rút gọn dựa trên miền dương) nếu nó thỏa mãn hai điều kiện: 1) POSR(D) = POSC(D), tức là R bảo toàn khả năng phân lớp của C; và 2) với mọi thuộc tính r ∈ R, POSR-{r}(D) ≠ POSC(D), tức là R là tối thiểu, không chứa thuộc tính thừa. Việc tìm kiếm các tập rút gọn này là mục tiêu trung tâm của các thuật toán rút gọn thuộc tính, vì chúng đại diện cho những đặc trưng cốt lõi và cần thiết nhất của dữ liệu.

IV. Thuật toán rút gọn bảng quyết định nhất quán sử dụng metric

Một hướng tiếp cận mới và hiệu quả để giải quyết bài toán rút gọn là sử dụng các hàm metric (đo lường khoảng cách) để đánh giá tầm quan trọng của thuộc tính. Hướng tiếp cận này được trình bày chi tiết trong nghiên cứu của Dương Đức Nguyên (2013). Ý tưởng cốt lõi là xây dựng một không gian metric trên các tri thức được biểu diễn bởi các phân hoạch dữ liệu. Khoảng cách giữa hai tri thức, ví dụ như K(C) và K(C ∪ D), thể hiện mức độ thông tin mà tập thuộc tính C cung cấp để xác định D. Mục tiêu của thuật toán rút gọn bảng quyết định nhất quán lúc này là tìm một tập con R ⊆ C sao cho khoảng cách d(K(R), K(R ∪ D)) bằng với khoảng cách d(K(C), K(C ∪ D)), đồng thời R phải là tối thiểu. Tầm quan trọng của một thuộc tính được định nghĩa là sự thay đổi của khoảng cách này khi thêm thuộc tính đó vào tập đang xét. Thuật toán thường được triển khai theo hướng tiếp cận từ dưới lên (bottom-up). Đầu tiên, thuật toán xác định tập lõi MCORE(C). Sau đó, nó lặp lại việc thêm vào tập kết quả các thuộc tính chưa được chọn có độ quan trọng lớn nhất cho đến khi điều kiện bảo toàn khoảng cách được thỏa mãn. Cuối cùng, một bước kiểm tra lại được thực hiện để loại bỏ các thuộc tính có thể trở nên dư thừa trong quá trình thêm vào. Cách tiếp cận này có ưu điểm là trực quan và thường có độ phức tạp tính toán thấp hơn so với các phương pháp dựa trên entropy.

4.1. Xây dựng metric và tính khoảng cách giữa các tri thức

Để áp dụng thuật toán rút gọn dựa trên metric, trước tiên cần định nghĩa một hàm khoảng cách phù hợp. Nghiên cứu đề xuất một công thức metric dJ(K(P), K(Q)) dựa trên các phân hoạch U/P và U/Q. Hàm khoảng cách này có các tính chất toán học quan trọng, đặc biệt là tính phản đơn điệu: nếu P ⊆ Q thì d(K(P), K(P ∪ D)) ≥ d(K(Q), K(Q ∪ D)). Điều này có nghĩa là khi tập thuộc tính càng lớn (chứa nhiều thông tin hơn), nó càng "gần" với tri thức đầy đủ, và khoảng cách đến mục tiêu phân lớp càng nhỏ. Việc tính toán khoảng cách này dựa trực tiếp vào kích thước của các khối trong phân hoạch và phần giao của chúng với các lớp quyết định. Công thức này không yêu cầu các phép tính phức tạp như logarit, giúp giảm đáng kể chi phí tính toán.

4.2. Heuristic tìm tập rút gọn tối ưu theo hướng bottom up

Thuật toán heuristic tìm một tập rút gọn tốt nhất được thực hiện theo chiến lược tham lam từ dưới lên (bottom-up). Quy trình bao gồm ba bước chính. Bước 1: Tìm tập lõi MCORE(C) là tập các thuộc tính không thể thiếu. Tập kết quả R được khởi tạo bằng tập lõi này. Bước 2: Trong một vòng lặp, thuật toán tính toán độ quan trọng của tất cả các thuộc tính trong C-R. Độ quan trọng SIGR(a) được đo bằng mức giảm khoảng cách khi thêm thuộc tính 'a' vào R. Thuộc tính có độ quan trọng lớn nhất sẽ được chọn và thêm vào R. Vòng lặp này tiếp tục cho đến khi R có khả năng phân lớp tương đương với C. Bước 3: Sau khi có được tập R, thuật toán thực hiện một bước sàng lọc để loại bỏ bất kỳ thuộc tính nào có thể đã trở nên dư thừa, đảm bảo tính tối thiểu của tập rút gọn cuối cùng.

4.3. Phân tích độ phức tạp thời gian và hiệu quả của thuật toán

Một ưu điểm lớn của thuật toán rút gọn bảng quyết định nhất quán sử dụng metric là hiệu quả về mặt tính toán. Theo phân tích trong tài liệu gốc, độ phức tạp thời gian của thuật toán này là O(|C|^2|U|), trong đó |C| là số thuộc tính điều kiện và |U| là số đối tượng. Độ phức tạp này thấp hơn đáng kể so với các thuật toán phổ biến dựa trên Entropy Shannon, vốn thường có độ phức tạp O(|C|^2|U| + |U|^3). Nguyên nhân của sự hiệu quả này là do thuật toán tận dụng được kết quả tính toán phân hoạch ở bước trước để tính toán cho bước sau, và công thức metric không đòi hỏi các phép toán phức tạp. Điều này làm cho phương pháp dựa trên metric trở thành một lựa chọn hấp dẫn cho các bài toán với bộ dữ liệu lớn, nơi hiệu suất tính toán là một yếu tố quan trọng.

V. Kết quả nghiên cứu Ứng dụng thuật toán trên dữ liệu thực tế

Lý thuyết cần được kiểm chứng bằng thực nghiệm. Luận văn của Dương Đức Nguyên đã tiến hành cài đặt và thử nghiệm thuật toán rút gọn bảng quyết định nhất quán dựa trên metric trên nhiều bộ dữ liệu mẫu để đánh giá tính đúng đắn và hiệu quả. Chương trình được phát triển để thực hiện các chức năng chính: kiểm tra tính nhất quán của bảng quyết định, tìm tập lõi và tìm một tập rút gọn tốt nhất. Các bộ dữ liệu được sử dụng bao gồm "Flu" (dữ liệu về triệu chứng bệnh cúm) và hai bộ dữ liệu tổng hợp "EXAMPLE1", "EXAMPLE". Quá trình thực nghiệm cho thấy thuật toán hoạt động chính xác theo lý thuyết đã đề ra. Nó có khả năng xác định đúng tập lõi và tìm ra được một tập rút gọn hợp lệ, tức là một tập con tối thiểu của thuộc tính điều kiện mà vẫn bảo toàn được khả năng phân lớp. Ví dụ, với bộ dữ liệu "Flu", thuật toán có thể xác định rằng thuộc tính "Thân nhiệt" là thuộc tính lõi, trong khi "Đau đầu" và "Đau cơ" là các thuộc tính có thể thay thế cho nhau trong tập rút gọn. Những kết quả này không chỉ xác nhận giá trị của phương pháp tiếp cận dựa trên metric mà còn cho thấy tiềm năng ứng dụng của nó trong các lĩnh vực thực tiễn như y khoa, kinh doanh, nơi việc xác định các yếu tố ảnh hưởng chính là vô cùng quan trọng.

5.1. Cài đặt và thử nghiệm trên các bộ dữ liệu mẫu Flu EXAMPLE1

Chương trình thử nghiệm được cài đặt để minh họa cho hoạt động của thuật toán rút gọn. Với bộ dữ liệu "Flu", bảng quyết định ban đầu có các thuộc tính điều kiện như "Mệt mỏi", "Đau đầu", "Đau cơ", "Thân nhiệt" và thuộc tính quyết định là "Cảm cúm". Sau khi thực thi, thuật toán xác định được tập lõi là {Thân nhiệt} và hai tập rút gọn là R1={Đau cơ, Thân nhiệt} và R2={Đau đầu, Thân nhiệt}. Điều này cho thấy "Mệt mỏi" là thuộc tính dư thừa. Tương tự, khi chạy trên các bộ dữ liệu "EXAMPLE1" và "EXAMPLE", chương trình cũng đưa ra kết quả chính xác về tính nhất quán, tập lõi và các tập rút gọn. Các thử nghiệm này chứng tỏ thuật toán không chỉ đúng về mặt lý thuyết mà còn có thể áp dụng hiệu quả trên các cấu trúc dữ liệu khác nhau.

5.2. Đánh giá hiệu quả so với phương pháp Entropy Shannon

Một phần quan trọng của nghiên cứu là so sánh hiệu quả của phương pháp dựa trên metric với các phương pháp truyền thống hơn, đặc biệt là các thuật toán dựa trên Entropy Shannon. Về mặt lý thuyết, độ phức tạp thời gian của thuật toán metric (O(|C|^2|U|)) đã cho thấy ưu thế so với các thuật toán như MIBARK hay CEBARKCC (thường có độ phức tạp cao hơn). Về mặt thực tiễn, việc tính toán metric không liên quan đến các hàm logarit phức tạp, giúp giảm tải cho bộ xử lý. Mặc dù luận văn không trình bày một so sánh trực tiếp về thời gian chạy thực tế, những phân tích về độ phức tạp đã chỉ ra rằng phương pháp metric có tiềm năng vượt trội hơn trong các ứng dụng quy mô lớn. Điều này khẳng định rằng thuật toán rút gọn bảng quyết định nhất quán sử dụng metric là một hướng phát triển hiệu quả và đáng được quan tâm trong cộng đồng nghiên cứu khai phá dữ liệu.

VI. Kết luận và định hướng tương lai cho các thuật toán rút gọn

Nghiên cứu về thuật toán rút gọn bảng quyết định nhất quán đã tổng hợp và phát triển một hướng tiếp cận hiệu quả dựa trên việc sử dụng metric. Phương pháp này đã chứng tỏ được giá trị khoa học thông qua nền tảng lý thuyết vững chắc và kết quả thực nghiệm tích cực. Việc tìm ra các tập rút gọn và tập lõi không chỉ là một bài toán lý thuyết mà còn mang lại ý nghĩa thực tiễn to lớn, giúp giảm chi phí tính toán, tăng cường hiệu quả của các mô hình dự báo và hỗ trợ con người trong việc khám phá tri thức từ dữ liệu. Luận văn đã thành công trong việc xây dựng một thuật toán heuristic bottom-up có độ phức tạp thời gian thấp hơn so với các phương pháp dựa trên entropy, đồng thời cung cấp một công cụ thực nghiệm để kiểm chứng. Hướng nghiên cứu này vẫn còn nhiều tiềm năng để phát triển. Trong tương lai, các thuật toán có thể được mở rộng để xử lý các bảng quyết định không nhất quán, một dạng dữ liệu phổ biến hơn trong thực tế. Ngoài ra, việc kết hợp phương pháp metric với các kỹ thuật tối ưu hóa khác như thuật toán di truyền hoặc học tăng cường có thể giúp tìm ra các tập rút gọn chất lượng hơn nữa. Việc áp dụng các thuật toán này vào các lĩnh vực cụ thể như phân tích dữ liệu y sinh, tài chính hoặc marketing sẽ tiếp tục khẳng định giá trị và tính ứng dụng của chúng.

6.1. Tóm tắt giá trị khoa học của phương pháp rút gọn dựa trên metric

Giá trị khoa học chính của phương pháp rút gọn dựa trên metric nằm ở việc nó cung cấp một cách tiếp cận mới, hiệu quả và có cơ sở toán học rõ ràng cho bài toán rút gọn thuộc tính. Nó đã chứng minh rằng khoảng cách metric có thể được sử dụng như một tiêu chí mạnh mẽ để đo lường tầm quan trọng của thuộc tính, thay thế cho các độ đo phức tạp hơn như entropy. Thuật toán rút gọn bảng quyết định nhất quán được xây dựng dựa trên nền tảng này không chỉ hiệu quả về mặt lý thuyết (với độ phức tạp thời gian thấp hơn) mà còn đơn giản hơn trong cài đặt. Nghiên cứu này đóng góp một tài liệu tham khảo giá trị cho cộng đồng khoa học, đặc biệt là những người quan tâm đến lý thuyết tập thô và khai phá dữ liệu.

6.2. Các hướng nghiên cứu mở rộng trong khai phá dữ liệu quan hệ

Từ nền tảng của nghiên cứu này, nhiều hướng phát triển có thể được khai thác. Một hướng đi quan trọng là xử lý các bảng quyết định không nhất quán, nơi các đối tượng giống nhau về thuộc tính điều kiện nhưng lại khác nhau về thuộc tính quyết định. Các thuật toán cần được cải tiến để có thể xử lý các mâu thuẫn này một cách hợp lý. Hướng thứ hai là phát triển các thuật toán rút gọn thuộc tính động (dynamic), có khả năng cập nhật tập rút gọn khi có dữ liệu mới được thêm vào mà không cần phải chạy lại từ đầu. Ngoài ra, việc nghiên cứu mối liên hệ giữa tập rút gọn của bảng quyết định và các khái niệm trong cơ sở dữ liệu quan hệ, như phụ thuộc hàm và tập tối thiểu, cũng là một lĩnh vực đầy hứa hẹn, có thể dẫn đến những thuật toán lai mạnh mẽ và hiệu quả hơn.

Nghiên cứu thuật toán rút gọn trên bảng quyết định nhất quán

LỜI CAM ĐOAN

LỜI CẢM ƠN

MỤC LỤC

MỞ ĐẦU

1. CHƢƠNG 1: MỘT SỐ KHÁI NIỆM CƠ BẢN

1.1. Quá trình khai phá tri thức từ cơ sở dữ liệu

1.2. Thu thập và tiền xử lí dữ liệu

1.3. Khai phá dữ liệu

1.4. Một số quan niệm về khai phá dữ liệu

1.5. Nhiệm vụ của khai phá dữ liệu

1.6. Triển khai việc khai phá dữ liệu

1.7. Một số ứng dụng khai phá dữ liệu

1.8. Các kỹ thuật khai phá dữ liệu

1.9. Kiến trúc của hệ thống khai phá dữ liệu

1.10. Quá trình khai phá dữ liệu

1.11. Những khó khăn trong khai phá dữ liệu

1.12. Hệ thông tin đầy đủ và mô hình tập thô truyền thống

1.13. Hệ thông tin đầy đủ

1.14. Mô hình tập thô truyền thống

1.15. Bảng quyết định đầy đủ. Tập rút gọn và tập lõi

1.16. Một số khái niệm cơ bản

1.17. Một số thuật toán cơ bản

1.18. Tổng kết chƣơng

2. CHƢƠNG 2: RÚT GỌN THUỘC TÍNH VÀ MỘT SỐ THUẬT TOÁN TRÊN BẢNG QUYẾT ĐỊNH NHẤT QUÁN

2.1. Một số tính chất của metric trên bảng quyết định

2.2. Rút gọn thuộc tính trong bảng quyết định sử dụng metric

2.3. Tập lõi và tập rút gọn của bảng quyết định dựa trên metric

2.4. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng metric

2.5. Mối liên hệ giữa tập rút gọn dựa trên Metric và tập rút gọn Entropy Shannon

2.6. Thuật toán tìm tập rút gọn theo tham số độ chắc chắn của tập luật

2.7. Thuật toán tìm tập tất cả các thuộc tính rút gọn của bảng quyết định nhất quán

2.8. Thuật toán tìm họ tất cả các tập rút gọn của bảng quyết định nhất quán

2.9. Thuật toán xây dựng các phụ thuộc hàm từ bảng quyết định nhất quán

2.10. Thuật toán xây dựng bảng quyết định từ tập phụ thuộc hàm

2.11. Tổng kết chƣơng 2

3. CHƢƠNG 3: CÀI ĐẶT CHƢƠNG TRÌNH TÌM TẬP TẤT CẢ CÁC THUỘC TÍNH RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH NHẤT QUÁN

3.1. Yêu cầu hệ thống và cấu hình cho máy

3.2. Yêu cầu hệ thống

3.3. Cấu hình cho máy

3.4. Giới thiệu chƣơng trình và cách sử dụng

3.5. Cấu trúc chƣơng trình

3.6. Giới thiệu chƣơng trình

3.7. Thực hiện thuật toán với bộ dữ liệu Flu, EXAMPLE1, EXAMPLE

3.8. Bộ dữ liệu “Flu”

3.9. Bộ dữ liệu “EXAMPLE1”

3.10. Bộ dữ liệu “EXAMPLE”

3.11. Tổng kết chƣơng

KẾT LUẬN VÀ ĐỀ NGHỊ

TÀI LIỆU THAM KHẢO

DANH MỤC CÁC BẢNG

DANH MỤC CÁC HÌNH

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT