Luận văn: Khai phá dữ liệu dựa trên bảng quyết định nhờ lý thuyết tập thô

Luận văn thạc sĩ: Ứng dụng lý thuyết tập thô và bảng quyết định trong khai phá dữ liệu. Nghiên cứu phương pháp mới, hiệu quả để trích xuất tri thức từ dữ liệu.

• Tác giả: Hoàng Thị Kim Oanh
• Người hướng dẫn: GS. Vũ Đức Thi
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Khai Phá Dữ Liệu Dựa Trên Bảng Quyết Định Nhờ Lý Thuyết Tập Thô
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC CÁC THUẬT NGỮ
• DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ
• MỞ ĐẦU
• 1. CHƢƠNG 1: KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN TẬP THÔ
• 1.1. Hệ thông tin
• 1.2. Bảng quyết định
• 1.3. Quan hệ không phân biệt đƣợc
• 1.4. Các tập xấp xỉ
• 1.5. Tập rút gọn và tập lõi
• 1.6. Ma trận phân biệt và hàm phân biệt
• 2. PHƢƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT TRÊN BẢNG QUYẾT ĐỊNH
• 2.1. Phương pháp rút gọn thuộc tính trên bảng quyết định
• 2.2. Phương pháp rút gọn thuộc tính dựa trên entropy Shannon
• 2.2.1. Entropy Shannon trên bảng quyết định
• 2.2.2. Tập lõi của bảng quyết định dựa trên Entropy Shannon
• 2.2.3. Tập rút gọn của bảng quyết định dựa trên Entropy Shannon
• 2.2.4. Độ quan trọng của thuộc tính dựa trên entropy Shannon
• 2.2.5. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng Entropy Shannon
• 2.3. Sinh luật quyết định trên tập rút gọn của bảng quyết định
• 2.3.1. Luật quyết định
• 2.3.2. Các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn
• 2.3.3. Thuật toán sinh luật quyết định dựa trên tập rút gọn của bảng quyết định
• 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ
• 3.1. Một số kết quả thử nghiệm
• 3.2. Kết quả thử nghiệm thuật toán rút gọn thuộc tính sử dụng entropy Shannon
• 3.3. Kết quả thử nghiệm thuật toán sinh luật quyết định dựa trên tập rút gọn
• 3.4. Ứng dụng thuật toán rút gọn thuộc tính vào thực tế
• 3.5. Một số giao diện chương trình
• 3.5.1. Thực hiện thuật toán rút gọn thuộc tính CEBARKCC
• 3.5.2. Thực hiện thuật toán sinh luật quyết định
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Khai phá dữ liệu Tổng quan về Bảng quyết định Tập thô

Ngày nay, sự bùng nổ của công nghệ thông tin và Internet đã tạo ra một lượng dữ liệu khổng lồ, dẫn đến tình trạng “ngập lụt thông tin”. Do đó, nhu cầu khai phá dữ liệu để tìm ra tri thức ẩn giấu trong dữ liệu ngày càng trở nên cấp thiết. Lý thuyết tập thô, được đề xuất bởi Zdzislaw Pawlak, là một cách tiếp cận hiệu quả để phát hiện tri thức và là cơ sở cho các ứng dụng khai phá dữ liệu. Nó đặc biệt hữu ích trong việc giải quyết các bài toán phân lớp dữ liệu, phát hiện luật trong dữ liệu không chắc chắn. Các mối quan hệ được biểu diễn thông qua quan hệ không phân biệt được, và dữ liệu được biểu diễn thông qua tập xấp xỉ trên và dưới. Dữ liệu trong lý thuyết tập thô thường được biểu diễn bằng hệ thông tin hoặc bảng quyết định. Bảng quyết định là một mô hình phổ biến, nơi giá trị của thuộc tính điều kiện cung cấp thông tin về giá trị của thuộc tính quyết định. Trong thực tế, các cơ sở dữ liệu (CSDL) cần khai phá thường rất lớn, chứa hàng ngàn thuộc tính, gây khó khăn cho việc phân tích dữ liệu. Do đó, việc rút gọn số lượng thuộc tính mà không làm mất thông tin quan trọng là vô cùng quan trọng. Rút gọn thuộc tính là một ứng dụng quan trọng của lý thuyết tập thô, nhằm loại bỏ các thuộc tính dư thừa và tìm ra các thuộc tính cốt yếu. Với bảng quyết định, rút gọn thuộc tính là tìm tập con nhỏ nhất của tập thuộc tính điều kiện mà vẫn bảo toàn thông tin phân lớp. Mười năm trở lại đây, nhiều nhà khoa học đã tập trung nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định sử dụng lý thuyết tập thô. Các phương pháp chính bao gồm phương pháp dựa trên miền dương, phương pháp sử dụng các phép toán trong đại số quan hệ, phương pháp sử dụng ma trận phân biệt và phương pháp sử dụng entropy thông tin. Tại Việt Nam, các nghiên cứu cũng đã đề xuất các thuật toán heuristic để tìm tập rút gọn. Với những lý do trên, tập thô đã chứng tỏ là một trong những lý thuyết hiệu quả trong lĩnh vực khai phá dữ liệu. Luận văn này tập trung vào hai vấn đề chính: tìm hiểu về lý thuyết tập thô và nghiên cứu các phương pháp rút gọn thuộc tính, đặc biệt là phương pháp sử dụng Entropy Shannon trong bảng quyết định.

1.1. Tổng quan về Hệ thông tin và Bảng quyết định

Hệ thông tin là một bộ IS = (U, A, V, f), trong đó U là tập hữu hạn các đối tượng, A là tập hữu hạn các thuộc tính, V là tập giá trị của thuộc tính và f là hàm thông tin. Bảng quyết định là một dạng đặc biệt của hệ thông tin, trong đó tập các thuộc tính A bao gồm hai tập con tách biệt: tập thuộc tính điều kiện C và tập thuộc tính quyết định D. Bảng quyết định DS được gọi là nhất quán khi và chỉ khi phụ thuộc hàm C → D nghiệm đúng. Trong thực tế, bảng quyết định được sử dụng rộng rãi để biểu diễn các bài toán phân loại và dự đoán.

1.2. Quan hệ không phân biệt được trong Tập thô

Một trong những đặc điểm cơ bản của lý thuyết tập thô là khả năng xử lý dữ liệu không phân biệt được. Quan hệ không phân biệt được trên U theo P, ký hiệu là IND(P), được định nghĩa là tập hợp các cặp đối tượng (u, v) sao cho u(a) = v(a) với mọi a ∈ P. Nếu (u, v) ∈ IND(P) thì hai đối tượng u và v không phân biệt được bởi các thuộc tính trong P. Quan hệ tương đương IND(P) xác định một phân hoạch trên U, ký hiệu là U/IND(P) hay U/P. Lớp tương đương trong phân hoạch U/P chứa đối tượng u ký hiệu là [u]P. Quan hệ không phân biệt được là một công cụ quan trọng trong lý thuyết tập thô, giúp xác định các đối tượng tương tự nhau và loại bỏ các thuộc tính dư thừa.

II. Xấp xỉ Tập và Rút gọn Thuộc tính trong Lý thuyết Tập thô

Trong lý thuyết tập thô, để biểu diễn một tập đối tượng X bằng tri thức có sẵn B, người ta xấp xỉ X bởi hợp của một số hữu hạn các lớp tương đương của phân hoạch U/B. Có hai cách xấp xỉ: B-xấp xỉ dưới (BX) và B-xấp xỉ trên (BX). Tập BX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, còn tập BX bao gồm các phần tử của U có khả năng được phân loại vào X dựa vào tập thuộc tính B. Từ hai tập xấp xỉ này, người ta định nghĩa các tập miền biên (BNB(X)) và miền ngoài (NEGB(X)). Rút gọn thuộc tính là quá trình tìm tập con nhỏ nhất của tập thuộc tính điều kiện mà vẫn bảo toàn thông tin phân lớp của bảng quyết định. Các thuộc tính được chia thành thuộc tính lõi (cốt yếu) và thuộc tính không cần thiết (dư thừa). Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa để tìm ra các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Các phương pháp rút gọn thuộc tính khác nhau đã được đề xuất, dựa trên các tiêu chuẩn khác nhau, nhưng đều thực hiện các công việc: đưa ra khái niệm tập rút gọn, đưa ra khái niệm độ quan trọng của thuộc tính và xây dựng thuật toán heuristic.

2.1. Tập Xấp xỉ trên và Tập Xấp xỉ dưới

Cho hệ thông tin IS = (U, A, V, f) và tập đối tượng X ⊆ U. Với một tập thuộc tính B ⊆ A cho trước, chúng ta có các lớp tương đương của phân hoạch U/B. B-xấp xỉ dưới của X, ký hiệu là BX, được xác định như sau: BX = {u ∈ U | [u]B ⊆ X}. B-xấp xỉ trên của X, ký hiệu là BX, được xác định như sau: BX = {u ∈ U | [u]B ∩ X ≠ ∅}. Tập BX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, còn tập BX bao gồm các phần tử của U có khả năng được phân loại vào X dựa vào tập thuộc tính B.

2.2. Tập Rút gọn và Tập Lõi

Trong bảng quyết định, các thuộc tính điều kiện được phân thành thuộc tính lõi và thuộc tính không cần thiết. Thuộc tính lõi là thuộc tính cốt yếu, không thể thiếu trong việc phân lớp chính xác tập dữ liệu. Thuộc tính không cần thiết là thuộc tính dư thừa mà việc loại bỏ thuộc tính này không ảnh hưởng đến việc phân lớp dữ liệu. Rút gọn thuộc tính là quá trình loại bỏ các thuộc tính không cần thiết để tìm ra tập con nhỏ nhất của các thuộc tính quan trọng.

2.3. Ma trận phân biệt và hàm phân biệt

Ma trận phân biệt là một công cụ sử dụng để tìm tập rút của bảng quyết định. Ma trận phân biệt của DS, ký hiệu M = (mij) 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 theo công thức cụ thể.

III. Entropy Shannon Phương pháp Rút gọn Thuộc tính hiệu quả

Entropy Shannon là một đại lượng toán học dùng để đo độ không chắc chắn của một đại lượng ngẫu nhiên. Trong những năm gần đây, entropy Shannon là một trong những công cụ hiệu quả để giải quyết bài toán rút gọn thuộc tính trong hệ thông tin. Các thuật toán heuristic tìm tập rút gọn sử dụng entropy Shannon có điều kiện, sử dụng entropy tương hỗ để đánh giá độ quan trọng của thuộc tính và xây dựng thuật toán heuristic tìm tập rút gọn của bảng quyết định MIBARK. Trong các công trình nghiên cứu, các tác giả đã đưa ra khái niệm tập rút gọn và tập lõi của bảng quyết định dựa trên entropy Shannon có điều kiện và đề xuất hai thuật toán heuristic tìm tập rút gọn của bảng quyết định: thuật toán CEBARKCC và thuật toán CEBARKNC. CEBARKCC là thuật toán heuristic tính toán lõi còn CEBARKNC là thuật toán heuristic không tính toán lõi. Trong cả hai thuật toán, độ quan trọng của thuộc tính đều được xây dựng trực tiếp từ công thức tính entropy có điều kiện.

3.1. Định nghĩa Entropy Shannon và Entropy có điều kiện

Cho bảng quyết định DS = (U, C ∪ D, V, f) và tập thuộc tính P ⊆ C. Entropy Shannon của P được định nghĩa bởi công thức toán học liên quan đến lực lượng của tập X. Entropy Shannon có điều kiện của D khi đã biết C được định nghĩa bởi một công thức phức tạp hơn, liên quan đến số lượng các phần tử trong các tập giao của C và D. Entropy Shannon cung cấp một cách để đo lường độ không chắc chắn trong dữ liệu và được sử dụng để xác định các thuộc tính quan trọng nhất trong bảng quyết định.

3.2. Tập Lõi dựa trên Entropy Shannon

Thuộc tính a ∈ C được gọi là không cần thiết (dư thừa) trong DS dựa trên entropy Shannon có điều kiện nếu H(D|C) = H(D|C-{a}). Ngược lại, a gọi là cần thiết. Tập tất cả các thuộc tính cần thiết trong DS được gọi là tập lõi dựa trên entropy Shannon có điều kiện và ký hiệu là HCORE(C).

IV. Thuật toán CEBARKCC Tìm Tập Rút gọn bằng Entropy Shannon

CEBARKCC (Conditional Entropy Based Algorithm for Reduction of Knowledge with Computing Core) là thuật toán heuristic tìm tập rút gọn tốt nhất trong bảng quyết định sử dụng entropy Shannon có điều kiện có tính toán lõi. Ý tưởng của thuật toán là xuất phát từ tập lõi R = HCORE(C), lần lượt bổ sung vào tập R các thuộc tính có độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn. Thuật toán này bao gồm các bước tính toán độ quan trọng của thuộc tính, lựa chọn thuộc tính có độ quan trọng cao nhất và loại bỏ các thuộc tính dư thừa.

4.1. Các bước chính của Thuật toán CEBARKCC

1. Tìm tập lõi HCORE(C).
2. R = HCORE(C).
3. While H(D|R) ≠ H(D|C) do
4. Chọn am ∈ C-R sao cho SIGR(am) = Max {SIGR(a)} với a ∈ C-R.
5. R = R ∪ {am}.
6. End.
7. For each a ∈ R do
8. If H(D|R-{a}) = H(D|C) then
9. R = R - {a}.
10. End.
11. End.
12. Return R.

4.2. Độ phức tạp thời gian của Thuật toán CEBARKCC

Độ phức tạp thời gian của Thuật toán CEBARKCC phụ thuộc vào số lượng thuộc tính (C) và số lượng đối tượng (U) trong bảng quyết định. Việc tính toán độ quan trọng của thuộc tính và lựa chọn thuộc tính có độ quan trọng cao nhất đòi hỏi thời gian đáng kể. Thuật toán CEBARKCC hiệu quả hơn so với các phương pháp khác.Độ phức tạp thời gian để chọn thuộc tính có độ quan trọng lớn nhất là . Vòng lặp For tại dòng lệnh 17 thực hiện R* lần, mỗi lần ta phải tính H(D|R) với độ phức tạp thời gian O(RU). Do đó, độ phức tạp thời gian của dòng lệnh 17 là O(RRU). Vì vậy, độ phức tạp thời gian của thuật toán là OC^2U.

V. Sinh Luật Quyết định trên Tập Rút gọn Tối ưu Tri thức

Rút trích và đánh giá hiệu năng tập luật quyết định từ bảng quyết định là bước tiếp theo của rút gọn thuộc tính trong quá trình khai phá dữ liệu sử dụng lý thuyết tập thô. Mục tiêu là tạo ra các luật quyết định đơn giản và dễ hiểu từ tập rút gọn, giúp đưa ra các dự đoán và quyết định chính xác. Các độ đo đánh giá hiệu năng tập luật quyết định được sử dụng để đánh giá tính đúng đắn và tính hiệu quả của các luật được sinh ra.

5.1. Luật Quyết định và các Độ đo Cổ điển

Cho bảng quyết định DS = (U, C ∪ D). Một luật quyết định đơn có dạng Zij: des(Xi) → des(Yj), trong đó Xi ∈ U/C và Yj ∈ U/D. Các độ đo cổ điển đánh giá luật quyết định đơn Zij bao gồm:

• Độ chắc chắn: μ(Zij) = |Xi ∩ Yj| / |Xi|
• Độ hỗ trợ: s(Zij) = |Xi ∩ Yj| / |U|
• Độ nhất quán: τ(Zij) = |Xi ∩ Yj| / |Yj| Tuy nhiên, các độ đo này chỉ phù hợp cho việc đánh giá các luật quyết định đơn lẻ, không phù hợp cho việc đánh giá hiệu năng tổng thể của tập luật.

5.2. Độ đo Đánh giá Hiệu năng Tập Luật Quyết định

Để đánh giá hiệu năng tập luật quyết định, các độ đo như độ chắc chắn (α), độ nhất quán (β) và độ hỗ trợ (γ) được sử dụng. Công thức và cách tính các độ đo này được cung cấp, giúp đánh giá tính tổng quát và độ tin cậy của tập luật.

• Độ chắc chắn (α): 𝑎 = 𝐸𝐸 𝐸𝐸𝐸𝐸 𝜇 𝐸𝐸𝐸 𝐸 = 𝐸𝐸 𝐸𝐸𝐸𝐸 𝐸 ⋂ 𝐸 𝐸 / 𝐸𝐸 𝐸
• Độ hỗ trợ: 𝐸 𝐸𝐸𝐸 = 𝐸𝐸 𝐸𝐸𝐸 𝐸 = 𝐸𝐸 𝐸𝐸𝐸𝐸 𝐸 ⋂ 𝐸 𝐸 / 𝐸
• Độ nhất quán: 𝛽 𝐸𝐸𝐸 = 𝐸1 − 𝐸𝐸 𝐸1 − 𝜇 𝐸𝐸𝐸 𝐸 / 𝐸/ 𝐸

VI. Thử nghiệm Đánh giá Ứng dụng Thực tế và Giao diện

Luận văn này đã thực hiện các thử nghiệm và đánh giá các thuật toán rút gọn thuộc tính sử dụng entropy Shannon và thuật toán sinh luật quyết định trên các bộ số liệu thực tế. Các kết quả thử nghiệm cho thấy các thuật toán này có thể giúp giảm số lượng thuộc tính và luật quyết định, đồng thời cải thiện độ chính xác và độ tin cậy của các dự đoán. Các giao diện chương trình cũng được phát triển để hỗ trợ người dùng thực hiện các thuật toán này một cách dễ dàng.

6.1. Kết quả Thử nghiệm Thuật toán Rút gọn Thuộc tính

Thuật toán CEBARKCC đã được thử nghiệm trên nhiều bộ số liệu từ kho dữ liệu UCI, với kết quả cho thấy thuật toán có khả năng giảm số lượng thuộc tính một cách đáng kể. Thời gian thực hiện thuật toán phụ thuộc vào kích thước của bộ số liệu. Kết quả thử nghiệm cho thấy, trên tập rút gọn tốt nhất thu được bởi Thuật toán CEBARKCC, số lượng các luật giảm xuống, độ dài các luật giảm. Độ chắc chắn của tập luật không thay đổi.

6.2. Ứng dụng Thực tế và Giao diện Chương trình

Các phương pháp rút gọn thuộc tính có ý nghĩa rất quan trọng trong thực tế, giúp loại bỏ các thuộc tính dư thừa và cải thiện hiệu quả của quá trình khai phá dữ liệu. Các bài toán ứng dụng bao gồm dự đoán bệnh ung thư phổi và chuẩn đoán bệnh viêm gan. Giao diện chương trình được thiết kế thân thiện và dễ sử dụng, giúp người dùng thực hiện các thuật toán một cách trực quan.