Luận Văn Thạc Sĩ Về Thuật Toán Khai Phá Luật Quyết Định Trên Cơ Sở Dữ Liệu Di Động

Luận văn thạc sĩ luật học nghiên cứu vnu uet một số thuật toán khai phá luật quyết định trên cơ sở dữ liệu di động, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp

• Tác giả: Nguyễn Thị Thu Hương
• 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: Một Số Thuật Toán Khai Phá Luật Quyết Định Trên Cơ Sở Dữ Liệu Động
• 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
• 1. CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN
• 1.1. Khai phá dữ liệu là gì
• 1.2. Các khái niệm cơ bản của tập thô
• 1.3. Hệ thống thông tin
• 1.4. Quan hệ bất khả phân
• 1.5. Tập xấp xỉ trên và xấp xỉ dưới
• 1.6. Bảng quyết định
• 1.7. Luật quyết định
• 1.8. Khai phá luật quyết định dựa trên tập thô
• 1.9. Kết luận chương 1
• 2. CHƯƠNG 2: THUẬT TOÁN TIẾP CẬN GIA TĂNG ĐỂ KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN CƠ SỞ DỮ LIỆU CÓ GIÁ TRỊ THUỘC TÍNH THAY ĐỔI
• 2.1. Định nghĩa về việc thay đổi giá trị thuộc tính
• 2.2. Mô hình tiếp cận gia tăng và thuật toán
• 2.3. Mô hình bài toán và kiến thức cơ sở tiếp cận thuật toán khi giá trị thuộc tính thay đổi
• 2.4. Thuật toán tiếp cận gia tăng khi làm thô, làm mịn các giá trị thuộc tính
• 2.5. Đánh giá độ phức tạp theo thời gian của thuật toán
• 2.6. Ví dụ minh họa
• 2.7. Kết luận chương 2
• 3. CHƯƠNG 3: THUẬT TOÁN TIẾP CẬN GIA TĂNG ĐỂ KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN CƠ SỞ DỮ LIỆU CÓ CÁC ĐỐI TƯỢNG THAY ĐỔI
• 3.1. Thuật toán tính toán gia tăng ma trận độ chính xác và độ phủ
• 3.2. Mô hình tiếp cận gia tăng
• 3.3. Các tình huống thực hiện mô hình
• 3.4. Độ phức tạp tính toán
• 3.5. Ví dụ minh họa
• 3.6. Thuật toán tính toán gia tăng ma trận độ hỗ trợ
• 3.7. Cơ sở tiếp cận thuật toán
• 3.8. Các tình huống thực hiện mô hình
• 3.9. Độ phức tạp tính toán
• 3.10. Ví dụ minh họa
• 3.11. Đánh giá hai thuật toán
• 3.12. Cài đặt thuật toán tính toán gia tăng ma trận độ hỗ trợ
• 3.13. Kết luận chương 3
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Thuật Toán Khai Phá Luật Quyết Định

Thuật toán khai phá luật quyết định là một lĩnh vực quan trọng trong khai thác dữ liệu. Nó giúp trích xuất các quy luật từ cơ sở dữ liệu, đặc biệt là trong các hệ thống thông tin động. Việc áp dụng các thuật toán này không chỉ giúp tối ưu hóa quy trình ra quyết định mà còn nâng cao hiệu quả trong việc phân tích dữ liệu. Các nghiên cứu gần đây đã chỉ ra rằng việc khai thác luật quyết định có thể cải thiện đáng kể khả năng dự đoán và phân loại trong nhiều lĩnh vực khác nhau.

1.1. Khái Niệm Cơ Bản Về Khai Phá Dữ Liệu

Khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích từ một lượng lớn dữ liệu. Nó bao gồm các bước như lọc dữ liệu, tích hợp và chuyển đổi dữ liệu để phục vụ cho việc phân tích. Các phương pháp khai thác dữ liệu như phân lớp, phân cụm và khai phá luật kết hợp đều có vai trò quan trọng trong việc rút ra tri thức từ dữ liệu.

1.2. Tầm Quan Trọng Của Luật Quyết Định

Luật quyết định giúp xác định mối quan hệ giữa các thuộc tính trong cơ sở dữ liệu. Chúng cung cấp thông tin quý giá cho việc ra quyết định trong các lĩnh vực như tài chính, y tế và marketing. Việc áp dụng luật quyết định có thể giúp các tổ chức tối ưu hóa quy trình và nâng cao hiệu quả hoạt động.

II. Vấn Đề Trong Khai Phá Luật Quyết Định Trên Cơ Sở Dữ Liệu Động

Một trong những thách thức lớn trong việc khai phá luật quyết định là sự thay đổi liên tục của cơ sở dữ liệu di động. Dữ liệu không chỉ thay đổi về số lượng mà còn về thuộc tính, điều này làm cho việc duy trì độ chính xác của các luật quyết định trở nên khó khăn. Các nhà nghiên cứu cần phát triển các phương pháp mới để cập nhật và điều chỉnh các luật quyết định khi dữ liệu thay đổi.

2.1. Thách Thức Về Độ Chính Xác

Độ chính xác của các luật quyết định có thể bị ảnh hưởng khi dữ liệu thay đổi. Việc cập nhật các luật này đòi hỏi phải có các thuật toán hiệu quả để đảm bảo rằng các quyết định được đưa ra vẫn chính xác và đáng tin cậy.

2.2. Khó Khăn Trong Việc Phân Tích Dữ Liệu Động

Phân tích dữ liệu động là một thách thức lớn do sự biến đổi liên tục của các thuộc tính và đối tượng. Các phương pháp truyền thống thường không đủ linh hoạt để xử lý các thay đổi này, dẫn đến việc cần thiết phải phát triển các thuật toán mới.

III. Phương Pháp Khai Phá Luật Quyết Định Hiệu Quả

Để khai phá luật quyết định hiệu quả, cần áp dụng các phương pháp tiên tiến như học máy và thuật toán tiếp cận gia tăng. Những phương pháp này cho phép cập nhật và điều chỉnh các luật quyết định một cách nhanh chóng và chính xác, ngay cả khi dữ liệu thay đổi liên tục.

3.1. Thuật Toán Tiếp Cận Gia Tăng

Thuật toán tiếp cận gia tăng cho phép cập nhật các luật quyết định mà không cần phải khai thác lại toàn bộ dữ liệu. Điều này giúp tiết kiệm thời gian và tài nguyên, đồng thời duy trì độ chính xác của các luật quyết định.

3.2. Ứng Dụng Học Máy Trong Khai Phá Luật

Học máy cung cấp các công cụ mạnh mẽ để phân tích và khai thác dữ liệu. Các mô hình học máy có thể học từ dữ liệu mới và tự động điều chỉnh các luật quyết định, giúp cải thiện độ chính xác và hiệu quả trong việc ra quyết định.

IV. Ứng Dụng Thực Tiễn Của Khai Phá Luật Quyết Định

Khai phá luật quyết định đã được áp dụng rộng rãi trong nhiều lĩnh vực như tài chính, y tế và marketing. Các ứng dụng này không chỉ giúp cải thiện quy trình ra quyết định mà còn tối ưu hóa các chiến lược kinh doanh. Nghiên cứu cho thấy rằng việc áp dụng các luật quyết định có thể mang lại lợi ích kinh tế đáng kể cho các tổ chức.

4.1. Ứng Dụng Trong Tài Chính

Trong lĩnh vực tài chính, khai phá luật quyết định giúp dự đoán xu hướng thị trường và tối ưu hóa danh mục đầu tư. Các tổ chức tài chính sử dụng các luật này để đưa ra quyết định đầu tư chính xác hơn.

4.2. Ứng Dụng Trong Y Tế

Khai phá luật quyết định trong y tế giúp cải thiện quy trình chẩn đoán và điều trị. Các bác sĩ có thể sử dụng các luật này để đưa ra quyết định điều trị tốt hơn cho bệnh nhân.

V. Kết Luận Và Tương Lai Của Khai Phá Luật Quyết Định

Khai phá luật quyết định là một lĩnh vực đang phát triển mạnh mẽ và có tiềm năng lớn trong tương lai. Với sự phát triển của công nghệ thông tin và dữ liệu lớn, việc khai thác luật quyết định sẽ ngày càng trở nên quan trọng hơn. Các nghiên cứu tiếp theo cần tập trung vào việc phát triển các phương pháp mới để xử lý dữ liệu động và cải thiện độ chính xác của các luật quyết định.

5.1. Xu Hướng Nghiên Cứu Tương Lai

Các nghiên cứu trong tương lai sẽ tập trung vào việc phát triển các thuật toán mới để khai thác luật quyết định trong các hệ thống thông tin động. Điều này sẽ giúp cải thiện khả năng ra quyết định trong nhiều lĩnh vực.

5.2. Tác Động Của Công Nghệ Mới

Công nghệ mới như trí tuệ nhân tạo và học sâu sẽ có tác động lớn đến việc khai phá luật quyết định. Những công nghệ này sẽ giúp nâng cao khả năng phân tích và dự đoán, từ đó cải thiện hiệu quả trong việc ra quyết định.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh công nghệ thông tin phát triển mạnh mẽ, lượng dữ liệu được tạo ra ngày càng lớn và đa dạng, việc khai thác hiệu quả các cơ sở dữ liệu động trở thành một thách thức quan trọng. Khai phá dữ liệu (Data Mining) đã trở thành lĩnh vực trọng điểm nhằm trích xuất tri thức có giá trị từ dữ liệu thô. Tuy nhiên, hầu hết các phương pháp truyền thống tập trung vào hệ thống dữ liệu tĩnh, trong khi thực tế dữ liệu thường xuyên thay đổi về số lượng đối tượng và giá trị thuộc tính. Theo ước tính, việc cập nhật tri thức trong cơ sở dữ liệu động đòi hỏi các thuật toán khai phá luật quyết định có khả năng xử lý gia tăng, giúp duy trì tính chính xác và độ phủ của các luật khi dữ liệu biến đổi.

Mục tiêu nghiên cứu của luận văn là phát triển và đánh giá một số thuật toán khai phá luật quyết định trên cơ sở dữ liệu động theo hướng tiếp cận gia tăng, tập trung vào hai trường hợp chính: thay đổi giá trị thuộc tính và thay đổi tập đối tượng. Phạm vi nghiên cứu tập trung vào các hệ thống thông tin động trong lĩnh vực công nghệ thông tin, với dữ liệu thu thập và phân tích trong khoảng thời gian gần đây, nhằm nâng cao hiệu quả khai phá tri thức trong môi trường dữ liệu biến đổi liên tục. Nghiên cứu có ý nghĩa quan trọng trong việc cải thiện tốc độ xử lý, giảm thiểu chi phí tính toán và đảm bảo tính cập nhật của các luật quyết định, từ đó hỗ trợ các ứng dụng thực tiễn như dự báo tài chính, chuẩn đoán y tế, và quản lý dữ liệu lớn.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên lý thuyết tập thô (Rough Set Theory) do Zdzislaw Pawlak đề xuất, cung cấp công cụ toán học để xử lý dữ liệu không chắc chắn và không đầy đủ. Các khái niệm chính bao gồm:

• Hệ thống thông tin: Mô hình dữ liệu gồm tập đối tượng và tập thuộc tính, trong đó mỗi đối tượng được mô tả bởi các giá trị thuộc tính.
• Quan hệ bất khả phân (Indiscernibility Relation): Xác định các lớp tương đương của đối tượng dựa trên tập thuộc tính con.
• Tập xấp xỉ trên và xấp xỉ dưới: Biểu diễn các đối tượng chắc chắn và có khả năng thuộc về một tập con nhất định.
• Bảng quyết định và luật quyết định: Bảng phân loại dữ liệu thành các phân lớp dựa trên thuộc tính điều kiện và quyết định, từ đó trích xuất các luật dạng "Nếu... thì...".
• Độ chính xác và độ phủ của luật quyết định: Các chỉ số đánh giá mức độ tin cậy và phạm vi áp dụng của luật.

Ngoài ra, luận văn áp dụng mô hình tiếp cận gia tăng (Incremental Approach) trong khai phá dữ liệu, cho phép cập nhật tri thức khi dữ liệu thay đổi mà không cần xử lý lại toàn bộ dữ liệu gốc.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu là các cơ sở dữ liệu động mô phỏng các hệ thống thông tin có sự biến đổi về thuộc tính và đối tượng. Phương pháp phân tích bao gồm:

• Xây dựng và mô phỏng các thuật toán khai phá luật quyết định theo hướng tiếp cận gia tăng dựa trên ma trận độ hỗ trợ, độ chính xác và độ phủ.
• Phân tích các trường hợp thay đổi giá trị thuộc tính (làm thô, làm mịn) và thay đổi tập đối tượng (thêm, bớt đối tượng).
• Đánh giá độ phức tạp tính toán của thuật toán qua các phép thử với kích thước dữ liệu khác nhau.
• Thời gian nghiên cứu kéo dài trong khoảng năm 2013-2014, tại Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội.

Phương pháp chọn mẫu là sử dụng dữ liệu mô phỏng và dữ liệu thực tế từ các hệ thống thông tin, đảm bảo tính đại diện cho các trường hợp thay đổi dữ liệu động. Các thuật toán được cài đặt và kiểm thử trên môi trường lập trình phù hợp, với các bước tính toán ma trận và trích xuất luật được tự động hóa.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Thuật toán gia tăng ma trận độ hỗ trợ cho giá trị thuộc tính thay đổi: Thuật toán cập nhật hiệu quả ma trận độ hỗ trợ khi giá trị thuộc tính được làm thô hoặc làm mịn, giúp giảm đáng kể thời gian tính toán so với phương pháp xử lý lại toàn bộ dữ liệu. Độ phức tạp tính toán được ước tính là $O(|U|^2)$, với $|U|$ là số lượng đối tượng trong hệ thống.

2. Thuật toán gia tăng ma trận độ chính xác và độ phủ cho tập đối tượng thay đổi: Thuật toán của Liu và thuật toán cải tiến dựa trên ma trận độ hỗ trợ đều cho phép cập nhật nhanh chóng các luật quyết định khi có sự thêm hoặc bớt đối tượng. Độ phức tạp tính toán của thuật toán Liu là khoảng $O(|U|^3)$, trong khi thuật toán cải tiến có hiệu quả tính toán cao hơn nhờ sử dụng ma trận độ hỗ trợ.

3. Hiệu quả trích xuất luật quyết định có ý nghĩa: Các luật được trích xuất thỏa mãn ngưỡng độ chính xác và độ phủ cho trước, đảm bảo tính tin cậy và khả năng áp dụng trong thực tế. Ví dụ minh họa với bảng dữ liệu về đặc điểm con người và thu nhập cho thấy thuật toán có thể xử lý các trường hợp làm thô, làm mịn thuộc tính và thay đổi đối tượng một cách linh hoạt.

4. So sánh hiệu quả thuật toán: Thuật toán dựa trên ma trận độ hỗ trợ có ưu điểm không cần thực hiện lại phân lớp toàn bộ khi dữ liệu thay đổi, giảm thiểu chi phí tính toán và tăng tốc độ cập nhật tri thức so với thuật toán dựa trên ma trận độ chính xác và độ phủ.

Thảo luận kết quả

Nguyên nhân của hiệu quả trên là do việc sử dụng ma trận độ hỗ trợ làm cơ sở cập nhật các ma trận độ chính xác và độ phủ, giúp giảm số phép tính cần thiết khi dữ liệu biến đổi. Kết quả này phù hợp với các nghiên cứu gần đây trong lĩnh vực khai phá dữ liệu động, đồng thời mở rộng ứng dụng của lý thuyết tập thô trong môi trường dữ liệu thực tế có tính biến đổi cao.

Việc mô phỏng thuật toán trên các bộ dữ liệu thực tế và mô phỏng cho thấy khả năng áp dụng rộng rãi trong các hệ thống thông tin động, đặc biệt trong các lĩnh vực như quản lý khách hàng, dự báo tài chính, và y tế. Các biểu đồ so sánh thời gian xử lý và độ chính xác luật quyết định có thể minh họa rõ ràng sự ưu việt của thuật toán gia tăng ma trận độ hỗ trợ.

Đề xuất và khuyến nghị

1. Phát triển thuật toán đa luồng và phân tán: Tăng cường khả năng xử lý song song để giảm thời gian tính toán trên các hệ thống dữ liệu lớn, hướng tới ứng dụng trong môi trường Big Data.

2. Mở rộng phạm vi nghiên cứu cho dữ liệu phi cấu trúc: Nghiên cứu áp dụng lý thuyết tập thô và thuật toán gia tăng cho các loại dữ liệu phi cấu trúc như văn bản, hình ảnh nhằm khai thác tri thức đa dạng hơn.

3. Tích hợp với các kỹ thuật học máy hiện đại: Kết hợp khai phá luật quyết định với mạng neuron, học sâu để nâng cao khả năng dự báo và phân loại trong các hệ thống thông tin động.

4. Xây dựng công cụ phần mềm hỗ trợ khai phá luật quyết định động: Phát triển phần mềm thân thiện, dễ sử dụng cho các nhà phân tích dữ liệu và chuyên gia trong các lĩnh vực ứng dụng.

Các giải pháp trên cần được thực hiện trong vòng 2-3 năm tới, với sự phối hợp giữa các nhà nghiên cứu, doanh nghiệp và các tổ chức đào tạo để đảm bảo tính khả thi và hiệu quả ứng dụng.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và giảng viên ngành Công nghệ Thông tin: Nghiên cứu sâu về lý thuyết tập thô, khai phá dữ liệu động và phát triển thuật toán gia tăng.

2. Chuyên gia phân tích dữ liệu và kỹ sư dữ liệu: Áp dụng thuật toán khai phá luật quyết định trong các hệ thống dữ liệu lớn, đặc biệt là dữ liệu có tính biến đổi theo thời gian.

3. Nhà quản lý dự án công nghệ và phát triển phần mềm: Lập kế hoạch và triển khai các giải pháp khai phá tri thức trong doanh nghiệp, nâng cao hiệu quả quản lý dữ liệu.

4. Sinh viên cao học và nghiên cứu sinh ngành Kỹ thuật Phần mềm, Khoa học Máy tính: Tham khảo để phát triển đề tài nghiên cứu, luận văn thạc sĩ và tiến sĩ liên quan đến khai phá dữ liệu và học máy.

Mỗi nhóm đối tượng có thể ứng dụng các kết quả nghiên cứu để nâng cao năng lực chuyên môn, cải tiến quy trình xử lý dữ liệu và phát triển các sản phẩm công nghệ mới.

Câu hỏi thường gặp

1. Khai phá luật quyết định là gì và tại sao nó quan trọng?
Khai phá luật quyết định là quá trình trích xuất các quy tắc dạng "Nếu... thì..." từ dữ liệu để mô tả mối quan hệ giữa thuộc tính điều kiện và quyết định. Nó quan trọng vì giúp hiểu rõ cấu trúc dữ liệu, hỗ trợ ra quyết định và dự báo trong nhiều lĩnh vực.

2. Lý thuyết tập thô hỗ trợ khai phá dữ liệu như thế nào?
Lý thuyết tập thô cung cấp công cụ toán học để xử lý dữ liệu không chắc chắn và không đầy đủ, giúp phân lớp và rút trích luật quyết định một cách chính xác mà không cần thông tin bổ sung về phân phối xác suất.

3. Thuật toán gia tăng có ưu điểm gì so với phương pháp truyền thống?
Thuật toán gia tăng cho phép cập nhật tri thức khi dữ liệu thay đổi mà không cần xử lý lại toàn bộ dữ liệu, tiết kiệm thời gian và tài nguyên tính toán, phù hợp với môi trường dữ liệu động.

4. Làm thô và làm mịn giá trị thuộc tính có ý nghĩa gì trong khai phá dữ liệu?
Làm thô là quá trình kết hợp các giá trị thuộc tính thành một giá trị mới, làm mịn là tách giá trị thành các giá trị nhỏ hơn. Hai quá trình này ảnh hưởng đến phân lớp dữ liệu và luật quyết định, cần được xử lý chính xác để duy trì tính nhất quán.

5. Thuật toán khai phá luật quyết định có thể áp dụng trong những lĩnh vực nào?
Thuật toán có thể áp dụng trong y tế (chuẩn đoán bệnh), tài chính (dự báo thị trường), quản lý khách hàng (phân nhóm khách hàng), và các hệ thống thông tin doanh nghiệp cần xử lý dữ liệu động.

Kết luận

• Luận văn đã phát triển và trình bày các thuật toán khai phá luật quyết định theo hướng tiếp cận gia tăng trên cơ sở dữ liệu động, xử lý hiệu quả sự thay đổi giá trị thuộc tính và tập đối tượng.
• Thuật toán dựa trên ma trận độ hỗ trợ cho thấy ưu thế về hiệu quả tính toán và khả năng cập nhật tri thức nhanh chóng so với các phương pháp truyền thống.
• Độ phức tạp tính toán của các thuật toán được đánh giá và minh họa qua các ví dụ thực tế, đảm bảo tính khả thi trong ứng dụng.
• Nghiên cứu góp phần nâng cao hiệu quả khai phá tri thức trong môi trường dữ liệu biến đổi liên tục, mở rộng phạm vi ứng dụng của lý thuyết tập thô.
• Các bước tiếp theo bao gồm phát triển thuật toán đa luồng, mở rộng cho dữ liệu phi cấu trúc và tích hợp với các kỹ thuật học máy hiện đại nhằm nâng cao khả năng ứng dụng thực tiễn.

Để khai thác tối đa giá trị từ nghiên cứu này, các nhà nghiên cứu và chuyên gia công nghệ thông tin được khuyến khích áp dụng và phát triển thêm các thuật toán gia tăng trong khai phá dữ liệu động.

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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ THU HƢƠNG MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN CƠ SỞ DỮ LIỆU ĐỘNG LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội - 2014 LUAN VAN CHAT LUONG download : add [e-mail] ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ THU HƢƠNG MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN CƠ SỞ DỮ LIỆU ĐỘNG Ngành: Công Nghệ Thông Tin Chuyên ngành: Kỹ Thuật Phần Mềm Mã số: 60480103 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: GS. VŨ ĐỨC THI Hà Nội - 2014 LUAN VAN CHAT LUONG download : add [e-mail] 1 LỜI CẢM ƠN Trƣớc khi trình bày nội dung chính của luận văn, tôi xin bày tỏ lòng biết ơn sâu sắc tới GS.TS Vũ Đức Thi – thầy giáo trực tiếp hƣớng dẫn và chỉ bảo tôi hoàn thành luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy, cô giáo trong khoa Công nghệ Thông tin -Trƣờng Đại học Công nghệ - Đại học Quốc gia Hà Nội đã dạy bảo tôi tận tình trong suốt quá trình học tập tại khoa. Tôi cũng xin chân thành cảm ơn Thầy giáo NCS. Nguyễn Thanh Tùng, các anh em đồng nghiệp và gia đình đã giúp đỡ, tạo điều kiện cho tôi trong quá trình thực hiện và hoàn thành luận văn này. Học viên Nguyễn Thị Thu Hƣơng LUAN VAN CHAT LUONG download : add [e-mail] 2 LỜI CAM ĐOAN Tôi xin cam đoan luận văn này hoàn toàn do tôi thực hiện, không sao chép của ai. Các đoạn trích dẫn lý thuyết, các thuật toán đƣợc trình bày trong luận đều đƣợc dẫn nguồn và có độ chính xác cao nhất trong phạm vi tìm hiểu của tôi. Hà Nội, ngày 29 tháng 10 năm 2014 Học Viên Nguyễn Thị Thu Hƣơng LUAN VAN CHAT LUONG download : add [e-mail] 3 MỤC LỤC LỜI CẢM ƠN .1 LỜI CAM ĐOAN .3 DANH MỤC CÁC KÝ HIỆU .5 DANH MỤC CÁC BẢNG .6 DANH MỤC CÁC HÌNH . CÁC KHÁI NIỆM CƠ BẢN . Khai phá dữ liệu là gì . Các khái niệm cơ bản của tập thô . Hệ thống thông tin . Quan hệ bất khả phân . Tập xấp xỉ trên và xấp xỉ dƣới . Bảng quyết định . Luật quyết định . Khai phá luật quyết định dựa trên tập thô . Kết luận chƣơng 1 . THUẬT TOÁN TIẾP CẬN GIA TĂNG ĐỂ KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN CƠ SỞ DỮ LIỆU CÓ GIÁ TRỊ THUỘC TÍNH THAY ĐỔI . Định nghĩa về việc thay đổi giá trị thuộc tính . Mô hình tiếp cận gia tăng và thuật toán . Mô hình bài toán và kiến thức cơ sở tiếp cận thuật toán khi giá trị thuộc tính thay đổi . Thuật toán tiếp cận gia tăng khi làm thô, làm mịn các giá trị thuộc tính 27 2. Đánh giá độ phức tạp theo thời gian của thuật toán . Ví dụ minh họa . Kết luận chƣơng 2 .36 LUAN VAN CHAT LUONG download : add [e-mail] 4 CHƢƠNG 3. THUẬT TOÁN TIẾP CẬN GIA TĂNG ĐỂ KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN CƠ SỞ DỮ LIỆU CÓ CÁC ĐỐI TƢỢNG THAY ĐỔI . Thuật toán tính toán gia tăng ma trận độ chính xác và độ phủ . Mô hình tiếp cận gia tăng . Các tình huống thực hiện mô hình . Độ phức tạp tính toán . Ví dụ minh họa . Thuật toán tính toán gia tăng ma trận độ hỗ trợ . Cơ sở tiếp cận thuật toán . Các tình huống thực hiện mô hình . Độ phức tạp tính toán . Ví dụ minh họa . Đánh giá hai thuật toán . Cài đặt thuật toán tính toán gia tăng ma trận độ hỗ trợ . Kết luận chƣơng 3 .68 TÀI LIỆU THAM KHẢO .69 LUAN VAN CHAT LUONG download : add [e-mail] 5 DANH MỤC CÁC KÝ HIỆU Ký hiệu Ý nghĩa U Tập các đối tƣợng 𝐴 Tập các thuộc tính 𝐶 Tập thuộc tính điều kiện 𝐷 Tập thuộc tính quyết định 𝐵⊂𝐴 B là tập thuộc tính con của A IND(B) Quan hệ bất khả phân trên U theo B [𝑥]𝐼𝑁𝐷(𝐵) Các lớp tƣơng của 𝑥 trong mối quan hệ IND(B) 𝐵𝑋 Tập xấp xỉ dƣới của X theo B 𝐵𝑋 Tập xấp xỉ dƣới của X theo B 𝐵𝑁𝑋 Tập biên của X trên U theo B 𝐶𝑖 Phân lớp điều kiện thứ i 𝐷𝑗 Phân lớp tƣơng đƣơng quyết định thứ j 𝑆𝑢𝑝𝑝(𝐶𝑖 , 𝐷𝑗 ) Độ hỗ trợ của luật quyết định Ci→ Dj 𝐴𝑐𝑐(𝐶𝑖 , 𝐷𝑗 ) Độ chính xác của luật quyết định Ci→ Dj 𝐶𝑜𝑣(𝐶𝑖 , 𝐷𝑗 ) Độ phủ của luật quyết định Ci→ Dj 𝑆𝑢𝑝𝑝𝑡 (𝐶, 𝐷); 𝑆𝑢𝑝𝑝𝑡+1 (𝐶, 𝐷) Ma trận độ hỗ trợ thời điểm t và t+1 của các luật Ci→ Dj 𝐴𝐶𝐶𝑡 (𝐶, 𝐷); 𝐴𝑐𝑐𝑡+1 (𝐶, 𝐷) Ma trận độ chính xác thời điểm t và t+1 của các luật Ci→ Dj 𝐶𝑜𝑣𝑡 (𝐶, 𝐷); 𝐶𝑜𝑣𝑡+1 (𝐶, 𝐷) Ma trận độ độ phủ thời điểm t và t+1 của các luật Ci→ Dj α Ngƣỡng của độ chính xác γ Ngƣỡng của độ phủ LUAN VAN CHAT LUONG download : add [e-mail] 6 DANH MỤC CÁC BẢNG Bảng 1.1: Ví dụ về một bảng thông tin .2: Nhóm các đối tƣợng có bộ giá trị giống nhau .3: Ví dụ về một bảng quyết định .4: Bảng tính độ phủ, độ chính xác .1: Bảng quyết định cho ví dụ minh họa .2: Bảng trích rút các luật quan tâm .1: Bảng phân loại thu nhập đầu ngƣời trƣởng thành ở cụm dân cƣ .2: Kết quả độ chính xác và độ phủ thời điểm t+1- Thuật toán của Liu .3: Kết quả tính độ chính xác, độ phủ các luật bằng thuật toán gia tăng ma trận độ hỗ trợ .61 LUAN VAN CHAT LUONG download : add [e-mail] 7 DANH MỤC CÁC HÌNH Hình 1.1: Quá trình khái phá tri thức trong cơ sở dữ liệu .2: Mô hình thể hiện tập xấp xỉ trên và xấp xỉ dƣới của X .1: Tiến trình thêm/ bớt đối tƣợng khỏi hệ thống .2: Màn hình nhập dữ liệu .3: Màn hình chọn cơ sở dữ liệu .4: Màn hình hiển thị dữ liệu của cơ sở dữ liệu .5: Màn hình bổ sung/loại bỏ đối tƣợng .6: Màn hình hiển thị kết quả .67 LUAN VAN CHAT LUONG download : add [e-mail] 8 MỞ ĐẦU Trong những năm gần đây, công nghệ thông tin phát triển mạnh mẽ và đi sâu vào nhiều lĩnh vực trong cuộc sống. Công nghệ thông tin phát triển đi kèm với sự gia tăng không ngừng của cơ sở dữ liệu và nhu cầu sử dụng dữ liệu hiệu quả cũng trở nên ngày càng thiết yếu. Do đó, khai phá dữ liệu đã trở thành lĩnh vực phát triển mạnh với nhiều phƣơng pháp tiếp cận khác nhau. Thời gian đầu, phƣơng pháp tiếp cận quy nạp các luật dựa trên trên tập thô đƣợc sử dụng phổ biến với nhiều ứng dụng toàn diện để khai phá dữ liệu nhƣ dự báo tài chính, chuẩn đoán y tế.Các ứng dụng này đã chứng tỏ rằng rằng hƣớng tiếp cận này là rất hữu ích cho việc khai phá kiến thức bằng các luật quyết định từ cơ sở dữ liệu ban đầu. Tuy nhiên, hƣớng nghiên cứu và các ứng dụng của khai phá tri thức chủ yếu tập trung trong các hệ thống thông tin tĩnh. Nghĩa là các đối tƣợng và các thuộc tính trong một hệ thống thông tin nhất định không đổi. Trong thực tế, các nguồn dữ liệu thực có đặc điểm động, phát triển lớn mạnh lên về cả thuộc tính và số lƣợng đối tƣợng với tốc độ nhanh chóng. Để duy trì hiệu quả kiến thức từ dữ liệu động, các nhà nghiên cứu đã đi theo hƣớng nghiên cứu tiếp cận gia tăng cho việc cập nhật tri thức. Hiện nay, phƣơng pháp cận gia tăng dựa trên tập thô đã và đang đƣợc nhận rất nhiều quan tâm. Theo [6], dữ liệu động chủ yếu tập trung vào hai trƣờng hợp: (1) Tập các đối tƣợng trong hệ thống thông tin thay đổi theo thời gian trong khi các tập thuộc tính vẫn không đổi. (2) Tập các thuộc tính trong hệ thống thông tin thay đổi theo thời gian trong khi tập đối tƣợng vẫn không đổi. Do dữ liệu luôn thay đổi, các phân lớp dữ liệu cũng thay đổi theo. Vì vậy, luận văn tập trung tìm hiểu và trình bày “ một số thuật toán khai phá luật quyết định trên sơ sở dữ liệu động” theo hƣớng tiếp cận gia tăng với kỹ thuật phân lớp dựa trên tập thô. Các luật quyết định có độ chính xác và độ phủ cao là những luật có thể cung cấp các tri thức quan trọng. Để khai phá các luật quyết định có ý nghĩa, ta cần đặt ra ngƣỡng của độ chính xác và độ phủ để khai phá đƣợc các tri thức quan tâm. Nội dung của luận văn tập trung vào hƣớng đã nêu trong trƣờng hợp (1) và (2). Trong đó, luận văn gồm 3 chƣơng. Chƣơng 1: Trình các kiến thức cơ bản về khai phá dữ liệu và các khái niệm cơ bản trong tập thô nhƣ khái niệm tập hợp, tập thô, tập mờ, hệ thống thông tin, các mỗi quan hệ, bảng quyết định và luật quyết định. Chƣơng 2: Trình bày về thuật toán khai phá luật quyết định trên bảng dữ liệu khi có giá trị thuộc tính thay đổi (làm thô, làm mịn) theo hƣớng tiếp cận gia tăng ma trận độ hỗ trợ. Trong chƣơng này, luận văn tập trung trình bày các mối quan hệ của các lớp khi thuộc tính của dữ liệu khi đƣợc làm thô, làm mịn, thuật toán và đánh giá độ phức tap tính toán theo thời gian của thuật toán. Chƣơng 3: Trình bày hai thuật toán khai phá luật quyết định trên bảng dữ liệu động khi có tập đối thƣợng thay đổi. Hai thuật toán này đều đƣợc xây dựng trên cùng một mô hình chỉ khác nhau về hƣớng tiếp cận. Thuật toán LUAN VAN CHAT LUONG download : add [e-mail] 9 một là thuật toán khai phá luật quyết định theo hƣớng tiếp cận gia tăng ma trận độ chính xác và ma trận độ phủ. Thuật toán hai là thuật toán khai phá luật quyết định theo hƣớng tiếp cận gia tăng ma trận độ hỗ trợ. Kết thúc là phần kết luận và đề xuất những vấn đề cần tiếp tục nghiên cứu. LUAN VAN CHAT LUONG download : add [e-mail] 10 CHƢƠNG 1. CÁC KHÁI NIỆM CƠ BẢN 1. Khai phá dữ liệu là gì Khai phá dữ liệu đã thu hút rất nhiều sự chú ý trong ngành công nghệ thông tin và trong xã hội nói chung trong những năm gần đây. Do sự sẵn và rộng của lƣợng lớn dữ liệu và sự cần thiết để chuyển đổi dữ liệu đó thành thông tin hữu ích. Nên khai thác dữ liệu ra đời và đƣợc xem nhƣ là một kết quả của sự tiến hóa tự nhiên của công nghệ thông tin.