Thạc Sĩ Nghiên cứu một số phương pháp khai phá dữ liệu theo tiếp cận lý thuyết tập thô

Luận án tiến sĩ năm 2012
Đề tài: Nghiên cứu một số phương pháp khai phá dữ liệu theo tiếp cận lý thuyết tập thô
Định dạng file word

MỤC LỤCMỤC LỤC i
Danh mục các thuật ngữ iv
Bảng các ký hiệu, từ viết tắt v
Danh sách bảng. vii
Danh sách hình vẽ. viii
MỞ ĐẦU . 1
Chương 1. CÁC KHÁI NIỆM CƠ BẢN . 7
1.1. Hệ thông tin đầy đủ và mô hình tập thô truyền thống. 7
1.1.1. Hệ thông tin đầy đủ. 7
1.1.2. Mô hình tập thô truyền thống. 8
1.1.3. Bảng quyết định đầy đủ. 10
1.1.4. Tập rút gọn và tập lõi 10
1.1.5. Ma trận phân biệt và hàm phân biệt 12
1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai 13
1.2.1. Hệ thông tin không đầy đủ. 13
1.2.2. Bảng quyết định không đầy đủ. 15
1.2.3. Tập rút gọn của bảng quyết định không đầy đủ. 16
1.3. Cơ sở dữ liệu quan hệ. 17
1.3.1. Một số khái niệm cơ bản. 17
1.3.2. Một số thuật toán cơ bản. 19
Chương 2. SO SÁNH, ĐÁNH GIÁ CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH ĐẦY ĐỦ . 23
2.1. Mở đầu. 23
2.2. Mối liên hệ giữa các loại tập rút gọn dựa trên các tiêu chuẩn khác nhau. 28
2.2.1. Các định nghĩa về tập rút gọn dựa trên entropy thông tin. 28
2.2.2. Mối liên hệ giữa tập rút gọn Entropy Shannon với tập rút gọn Pawlak. 31
2.2.3. Mối liên hệ giữa tập rút gọn dựa trên entropy Shannon với ma trận phân biệt 33
2.2.4. Mối liên hệ giữa tập rút gọn dựa trên độ khác biệt của tri thức với tập rút gọn Entropy Liang 37
2.2.5. Tổng kết mối liên hệ giữa các loại tập rút gọn và phân loại các phương pháp. 39
2.3. Sự thay đổi 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. 40
2.3.1. Luật quyết định và các độ đo cổ điển. 41
2.3.2. Các độ đo đánh giá hiệu năng tập luật quyết định. 42
2.3.3. Độ nhất quán mới của tập luật quyết định. 43
2.3.4. Sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định. 47
2.4. Tiêu chuẩn đánh giá các phương pháp rút gọn thuộc tính. 49
2.4.1. Lựa chọn nhóm phương pháp rút gọn thuộc tính. 49
2.4.2. Tiêu chuẩn đánh giá các phương pháp rút gọn thuộc tính. 50
2.5. Kết luận chương 2. 51
Chương 3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH ĐẦY ĐỦ SỬ DỤNG METRIC 52
3.1. Mở đầu. 52
3.2. Metric trên họ các tri thức và các tính chất 53
3.2.1. Khoảng cách Jaccard giữa hai tập hợp hữu hạn. 53
3.2.2. Metric trên họ các tri thức. 55
3.2.3. Một số tính chất của metric trên bảng quyết định. 56
3.3. Rút gọn thuộc tính trong bảng quyết định sử dụng metric. 59
3.3.1. Tập lõi và tập rút gọn của bảng quyết định dựa trên metric. 59
3.3.2. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng metric. 59
3.3.3. 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. 66
3.3.4. 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 66
3.4. Thực nghiệm các thuật toán tìm tập rút gọn. 68
3.4.1. Thực nghiệm thuật toán tìm tập rút gọn tốt nhất sử dụng metric. 68
3.4.2. Thực nghiệm thuật toán tìm tập rút gọn theo tham số độ chắc chắn. 70
3.5. Thực nghiệm các phương pháp phân lớp dựa trên tập rút gọn. 72
3.5.1. Thực nghiệm phương pháp phân lớp sử dụng tập thô. 72
3.5.2. Thực nghiệm phương pháp phân lớp bằng cây quyết định. 73
3.6. Kết luận chương 3. 76
Chương 4. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ SỬ DỤNG METRIC 77
4.1. Mở đầu. 77
4.2. Entropy Liang mở rộng trong hệ thông tin không đầy đủ và các tính chất 78
4.2.1. Entropy Liang mở rộng của tập thuộc tính. 78
4.2.2. Entropy Liang mở rộng có điều kiện. 79
4.2.3. Một số tính chất của entropy Liang mở rộng. 80
4.3. Metric trên họ các phủ và các tính chất 84
4.3.1. Metric trên họ các phủ. 84
4.3.2. Một số tính chất của metric. 87
4.4. Rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng metric. 90
4.4.1. Tập rút gọn của bảng quyết định không đầy đủ dựa trên metric. 90
4.4.2. Thuật toán tìm tập rút gọn của bảng quyết định không đầy đủ. 90
4.4.3. Mối liên hệ giữa tập rút gọn dựa trên metric với tập rút gọn Kryszkiewicz. 96
4.4.4. Mối liên hệ giữa tập rút gọn dựa trên metric với tập rút gọn dựa trên lượng thông tin 98
4.5. Thực nghiệm thuật toán. 99
4.6. Kết luận chương 4. 101
Chương 5. MỘT SỐ THUẬT TOÁN TRÊN BẢNG QUYẾT ĐỊNH NHẤT QUÁN 102
5.1. Mở đầu. 102
5.2. 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. 102
5.2.1. Đặt vấn đề. 102
5.2.2. Thuật toán. 103
5.2.3. Thực nghiệm thuật toán. 106
5.3. 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. 106
5.4. 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. 109
5.5. Thuật toán xây dựng bảng quyết định từ tập phụ thuộc hàm 110
5.6. Kết luận chương 5. 114
KẾT LUẬN . 115
Danh mục các công trình của tác giả. 117
Tài liệu tham khảo 118
Phụ lục. 125

MỞ ĐẦULý thuyết tập thô - do Zdzislaw Pawlak [42] đề xuất vào những năm đầu thập niên tám mươi của thế kỷ hai mươi - được xem là công cụ hữu hiệu để giải quyết các bài toán phân lớp, phát hiện luật chứa dữ liệu mơ hồ không chắc chắn. Từ khi xuất hiện, lý thuyết tập thô đã được sử dụng hiệu quả trong các bước của quá trình khai phá dữ liệu và khám phá tri thức, bao gồm tiền xử lý số liệu, trích lọc các tri thức tiềm ẩn trong dữ liệu và đánh giá kết quả thu được.
Trong lý thuyết tập thô, dữ liệu được biểu diễn thông qua một hệ thông tin với U là tập các đối tượng và A là tập các thuộc tính. Phương pháp tiếp cận chính của lý thuyết tập thô là dựa trên quan hệ không phân biệt được để đưa ra các tập xấp xỉ biểu diễn tập đối tượng cần quan sát. Khi đó, mọi tập đối tượng đều được xấp xỉ bởi hai tập rõ là xấp xỉ dưới và xấp xỉ trên của nó. Xấp xỉ dưới bao gồm các đối tượng chắc chắn thuộc tập đó, còn xấp xỉ trên chứa tất cả các đối tượng có khả năng thuộc về tập đó. Nếu tập xấp xỉ dưới bằng tập xấp xỉ trên thì tập đối tượng cần quan sát là tập rõ, ngược lại làtập thô. Các tập xấp xỉ là cơ sở để đưa ra các kết luận từ dữ liệu. Bảng quyết định là một hệ thông tin IS với tập thuộc tính được chia thành hai tập con khác rỗng rời nhau và , lần lượt được gọi là tập thuộc tính điều kiện và tập thuộc tính quyết định. Nói cách khác, với . Bảng quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại các thuộc tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính quyết định. Bảng quyết định là nhất quán khi phụ thuộc hàm là đúng, trái lại là không nhất quán.
Rút gọn thuộc tính là ứng dụng quan trọng nhất trong lý thuyết tập thô. 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. 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 bảo toàn thông tin phân lớp của bảng quyết định. Đối với một bảng quyết định có thể có nhiều tập rút gọn khác nhau Tuy nhiên, trong thực hành thường không đòi hỏi tìm tất cả các tập rút gọn mà chỉ cần tìm được một tập rút gọn tốt nhất theo một tiêu chuẩn đánh giá nào đó là đủ. Vì vậy, mỗi phương pháp rút gọn thuộc tính đều đề xuất một thuật toán heuristic tìm tập rút gọn. Các thuật toán này giảm thiểu đáng kể khối lượng tính toán, nhờ đó có thể áp dụng đối với các bài toán có khối lượng dữ liệu lớn.
Mười năm trở lại đây đã chứng kiến sự phát triển mạnh mẽ và sôi động của lĩnh vực nghiên cứu về rút gọn thuộc tính sử dụng lý thuyết tập thô. Trong xu thế đó, nhiều nhóm nhà khoa học trên thế giới quan tâm nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định. Các phương pháp chính là: phương pháp dựa trên miền dương [18, 29, 41, 42, 67], phương pháp sử dụng các phép toán trong đại số quan hệ [20, 61], phương pháp sử dụng ma trận phân biệt [11, 19, 65, 69], phương pháp sử dụng entropy thông tin [39, 52, 55, 56, 57, 58, 59, 60, 63], phương pháp sử dụng các độ đo trong tính toán hạt [12, 24, 26, 27, 28, 70, 71]. Tại Việt Nam, luận án tiến sĩ của tác giả Hoàng Thị Lan Giao [1] đã đề xuất các thuật toán heuristic tìm tập rút gọn và tìm tập rút gọn xấp xỉ của bảng quyết định nhất quán, bao gồm thuật toán sử dụng các phép toán trong đại số quan hệ và thuật toán sử dụng ma trận phân biệt. Luận án tiến sĩ của tác giả Nguyễn Đức Thuần [2] đề xuất thuật toán heuristic tìm tập rút gọn của bảng quyết định đầy đủ nhất quán dựa vào phủ tập thô.
Với mục tiêu tìm kiếm một phương pháp phù hợp, hiệu quả rút gọn thuộc tính trong bảng quyết định, vấn đề trước tiên là cần đưa ra tiêu chuẩn lựa chọn các phương pháp phù hợp với lớp bài toán cần giải quyết và tiêu chuẩn so sánh, đánh giá các phương pháp. Tiêu chuẩn lựa chọn các phương pháp phù hợp là tập rút gọn của phương pháp phải bảo toàn độ chắc chắn của bảng quyết định. Việc lựa chọn các phương pháp phù hợp được thực hiện bằng việc nghiên cứu sự thay đổi giá trị 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. Tiêu chuẩn so sánh, đánh giá các phương pháp là số lượng thuộc tính tập rút gọn của phương pháp và độ phức tạp của thuật toán tìm tập rút gọn. Việc so sánh số lượng thuộc tính tập rút gọn của phương pháp được thực hiện bằng việc nghiên cứu mối liên hệ giữa các tập rút gọn. Tập rút gọn của phương pháp càng ít thuộc tính thì độ hỗ trợ của tập luật dựa trên tập rút gọn đó càng cao và phương pháp đó càng hiệu quả. Độ phức tạp thuật toán tìm tập rút gọn của phương pháp càng nhỏ thì phương pháp đó càng hiệu quả. Từ hai tiêu chuẩn này, ta có thể chứng minh được phương pháp cần tìm kiếm là phù hợp và hiệu quả hơn các phương pháp đã có hay không. Trên thế giới và tại Việt Nam, một số nhóm tác giả đã nghiên cứu mối liên hệ giữa các loại tập rút gọn của một số phương pháp rút gọn thuộc tính và nghiên cứu một số độ đo đánh giá hiệu năng tập luật quyết định [2, 6, 37, 48, 61, 64]. Tuy nhiên trên cả bảng quyết định nhất quán và không nhất quán, các tác giả trên chưa nghiên cứu đầy đủ mối liên hệ giữa các loại tập rút gọn và chưa nghiên cứu đầy đủ sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định dựa trên các loại tập rút gọn này.
Trong các bài toán thực tế, các hệ thông tin thường thiếu giá trị trên các thuộc tính, gọi là các hệ thông tin không đầy đủ. Xuất phát từ mô hình tập thô mở rộng dựa trên quan hệ dung sai trong hệ thông tin không đầy đủ do Kryszkiewicz [23] đề xuất, nhiều nhóm nhà khoa học trên thế giới đã quan tâm nghiên cứu các độ đo không chắc chắn [31, 32, 44, 45] và sử dụng các độ đo này để giải quyết bài toán rút gọn thuộc tính [13, 21, 28, 34]. Trên lớp bài toán rút gọn thuộc tính trong bảng quyết định không đầy đủ, vấn đề các nhà nghiên cứu tiếp tục quan tâm là cải tiến các các phương pháp đã có hoặc xây dựng các phương pháp mới hiệu quả hơn theo các tiêu chuẩn đánh giá được chọn.
Cho bảng quyết định nhất quán , tập thuộc tính được gọi là một tập rút gọn của tập thuộc tính điều kiện C nếu là tập tối thiểu thỏa mãn phụ thuộc hàm . Xét quan hệ trên tập thuộc tính , tập thuộc tính được gọi là một tập tối thiểu của thuộc tính nếu là tập tối thiểu thỏa mãn phụ thuộc hàm . Do đó, khái niệm tập rút gọn của bảng quyết định tương đương với khái niệm tập tối thiểu của thuộc tính {d} trên quan hệ, và một số bài toán trong bảng quyết định liên quan đến tập rút gọn có thể được giải quyết bằng một số kết quả liên quan đến tập tối thiểu của một thuộc tính trong cơ sở dữ liệu quan hệ; bao gồm bài toán tìm tập tất cả các thuộc tính rút gọn, bài toán tìm họ tất cả các tập rút gọn, bài toán trích lọc các tri thức dưới dạng các phụ thuộc hàm từ bảng quyết định, bài toán xây dựng bảng quyết định từ tập phụ thuộc hàm cho trước. Cho đến nay, hướng tiếp cận này chưa được nhiều tác giả quan tâm nghiên cứu.
Từ các nội dung đã trình bày ở trên, luận án đặt ra các vấn đề nghiên cứu sau:
1) Trên bảng quyết định đầy đủ, vấn đề đầu tiên là nghiên cứu đầy đủ mối liên hệ giữa các loại tập rút gọn của các phương pháp rút gọn thuộc tính và nghiên cứu đầy đủ sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định dựa trên các loại tập rút gọn này. Mục đích nghiên cứu trước tiên là lựa chọn các phương pháp phù hợp với lớp bài toán cần giải quyết, sau đó là so sánh, đánh giá các phương pháp theo các tiêu chuẩn khác nhau. Dựa trên các kết quả này, vấn đề nghiên cứu tiếp theo là tìm kiếm một phương pháp mới hiệu quả hơn các phương pháp đã có theo các tiêu chuẩn đánh giá được chọn.
2) Trên bảng quyết định không đầy đủ, vấn đề nghiên cứu đặt ra là tìm kiếm một phương pháp rút gọn thuộc tính hiệu quả hơn các phương pháp đã có theo các tiêu chuẩn đánh giá được chọn.
3) Trên bảng quyết định nhất quán, vấn đề nghiên cứu đặt ra là xây dựng các thuật toán có ý nghĩa liên quan đến tập rút gọn sử dụng một số kết quả liên quan đến tập tối thiểu của một thuộc tính trong cơ sở dữ liệu quan hệ.
[B]Mục tiêu của luận án tập trung nghiên cứu [I]bốn vấn đề chính. [I]Vấn đề thứ nhất là so sánh, đánh giá các phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ theo các tiêu chuẩn khác nhau. [I]Vấn đề thứ hai là đề xuất phương pháp mới rút gọn thuộc tính trong bảng quyết định đầy đủ sử dụng metric và chứng minh phương pháp mới hiệu quả hơn các phương pháp đã có dựa trên kết quả nghiên cứu của vấn đề thức nhất. [I]Vấn đề thứ ba là đề xuất phương pháp mới rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng metric và chứng minh phương pháp mới hiệu quả hơn các phương pháp đã có theo các tiêu chuẩn đánh giá được chọn. [I]Vấn đề thứ tư là đề xuất một số thuật toán trong bảng quyết định nhất quán sử dụng một số kết quả trong cơ sở dữ liệu quan hệ.
[B]Đối tượng nghiên cứu của luận án là các [I]bảng quyết định đầy đủ và các [I]bảng quyết định không đầy đủ với kích thước trung bình và kích thước lớn.
[B]Phạm vi nghiên cứu của luận án [I]tập trung vào bài toán rút gọn thuộc tính trong bước tiền xử lý số liệu. Ngoài ra, luận án nghiên cứu thêm phương pháp trích lọc tri thức từ bảng dữ liệu dưới dạng phụ thuộc hàm trong bước khai phá dữ liệu ở chương 5.
[B]Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết: các định lý, mệnh đề trong luận án được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về nghiên cứu thực nghiệm: luận án thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI, so sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết, từ đó kết luận tính đúng đắn của kết quả nghiên cứu.
[B]Bố cục của luận án gồm phần mở đầu và năm chương nội dung, phần kết luận và danh mục các tài liệu tham khảo. Chương 1 trình bày các khái niệm cơ bản về mô hình tập thô truyền thống, mô hình tập thô mở rộng dựa trên quan hệ dung sai và cơ sở dữ liệu quan hệ. Chương 1 cũng trình bày một số thuật toán cơ bản trong cơ sở dữ liệu quan hệ được sử dụng để xây dựng các thuật toán trên bảng quyết định nhất quán trong chương 5.
Các đóng góp chính của luận án được trình bày trong chương 2, chương 3, chương 4 và chương 5.
Chương 2 trình bày kết quả nghiên cứu về mối liên hệ giữa các loại tập rút gọn của các phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ và sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định dựa trên các loại tập rút gọn này. Trên cơ sở đó, chương 2 phân loại các phương pháp rút gọn thuộc tính trong bảng quyết định không nhất quán thành [I]3 nhóm, lựa chọn nhóm phương pháp phù hợp với lớp bài toán cần giải quyết và đánh giá các phương pháp trong 3 nhóm dựa trên hai tiêu chuẩn: [I]số lượng thuộc tính tập rút gọn của phương pháp và [I]độ phức tạp thuật toán tìm tập rút gọn
Chương 3 trình bày phương pháp xây dựng một metric trên họ các tri thức trong hệ thông tin đầy đủ dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn. Sử dụng metric được xây dựng, chương 3 đề xuất một phương pháp mới rút gọn thuộc tính trong bảng quyết định đầy đủ. Dựa trên lý thuyết, thực nghiệm và dựa trên kết quả nghiên cứu của chương 2, chương 3 chứng minh phương pháp sử dụng metric [I]hiệu quả hơn các phương pháp khác trên cả hai tiêu chuẩn đánh giá: [I]số lượng thuộc tính tập rút gọn của phương pháp và [I]độ phức tạp thuật toán tìm tập rút gọn.
Chương 4 trình bày phương pháp xây dựng một metric trên họ các phủ trong hệ thông tin không đầy đủ dựa trên entropy Liang mở rộng. Sử dụng metric được xây dựng, chương 4 đề xuất phương pháp mới rút gọn thuộc tính trong bảng quyết định không đầy đủ. Bằng lý thuyết và thực nghiệm, chương 4 chứng minh phương pháp sử dụng metric [I]hiệu quả hơn phương pháp sử dụng độ đo lượng thông tin và phương pháp sử dụng ma trận dung sai theo tiêu chuẩn đánh giá [I]độ phức tạp thuật toán tìm tập rút gọn.
Chương 5 đề xuất bốn thuật toán trên bảng quyết định nhất quán dựa trên một số kết quả trong cơ sở dữ liệu quan hệ. [I]Thuật toán 5.1 tìm tập tất cả các thuộc tính rút gọn của bảng quyết định với độ phức tạp thời gian là đa thức. Đây là thuật toán thực sự có ý nghĩa trong tiền xử lý dữ liệu vì cho phép xác định và loại bỏ tất cả các thuộc tính dư thừa thực sự trong bảng dữ liệu trước khi thực hiện các nhiệm vụ khai phá dữ liệu tiếp theo. [I]Thuật toán 5.2tìm họ tất cả các tập rút gọn của bảng quyết định. [I]Thuật toán 5.3 trích lọc tất cả các tri thức dưới dạng phụ thuộc hàm từ bảng quyết định cho trước.[I]Thuật toán 5.4 xây dựng bảng quyết định từ tập các phụ thuộc hàm cho trước. Độ phức tạp thời gian của [I]Thuật toán 5.2, Thuật toán 5.3 và [I]Thuật toán 5.4 đều là hàm mũ.
Cuối cùng, phần kết luận nêu những đóng góp của luận án, hướng phát triển và những vấn đề quan tâm của tác giả.
[/I][/I][/I][/I][/I][/I][/I][/I][/I][/I][/I][/I][/I][/I][/B][/B][/I][/B][/I][/I][/B][/I][/I][/I][/I][/I][/B]