- NGUYỄN TRUNG TUẤN NGHIÊN CỨU ĐỘ ĐO TƯƠNG TỰ HỖN HỢP TRONG PHÁT HIỆN TRI THỨC TỪ DỮ LIỆU LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI. - NGUYỄN TRUNG TUẤN NGHIÊN CỨU ĐỘ ĐO TƯƠNG TỰ HỖN HỢP TRONG PHÁT HIỆN TRI THỨC TỪ DỮ LIỆU Chuyên ngành: Đảm bảo toán học cho máy tính và hệ thống tính toán Mã số LUẬN ÁN TIẾN SĨ KỸ THUẬT Người hướng dẫn khoa học: 1. - Ngô Văn Thứ - Trưởng khoa Toán Kinh tế, Trường Đại học kinh tế Quốc dân đã giúp đỡ về việc cung cấp các bộ dữ liệu thử nghiệm và các góp ý về phương pháp phân tích dữ liệu mà các nhà nghiên cứu kinh tế thường sử dụng. - 19 1.2 Phát hiện tri thức và khai phá dữ liệu. - 19 1.2.1 Tổng quan về phát hiện tri thức và khai phá dữ liệu. - 19 1.2.2 Quá trình phát hiện tri thức và khai phá dữ liệu. - 24 1.2.3 Các hệ thống phần mềm phát hiện tri thức và khai phá dữ liệu. - 26 1.2.4 Các phương pháp khai phá dữ liệu. - 28 1.2.5 Các vấn đề cần nghiên cứu của phát hiện tri thức và khai phá dữ liệu. - NGHIÊN CỨU ĐỘ ĐO TƯƠNG TỰ HỖN HỢP TRONG PHÁT HIỆN TRI THỨC TỪ DỮ LIỆU. - 70 2.3.5 Thử nghiệm tính độ đo tương tự hỗn hợp với dữ liệu ví dụ. - 74 2.3.7 Quy trình sử dụng độ đo MSM-R trong bài toán khai phá dữ liệu dựa trên khoảng cách. - THỬ NGHIỆM ĐỘ ĐO MSM-R TRONG BÀI TOÁN PHÂN LỚP VÀ PHÂN CỤM DỮ LIỆU. - 79 3.2 Thử nghiệm phân lớp dữ liệu với thuật toán k-láng giềng gần nhất. - 80 3.2.3 Kết quả thử nghiệm phân lớp với các bộ dữ liệu mẫu [CT6. - 88 3.2.5 Thử nghiệm phân lớp với dữ liệu chứa thuộc tính định danh có thứ tự [CT6. - Phân lớp dữ liệu kinh tế - xã hội Việt Nam bằng kỹ thuật láng giềng gần nhất với độ đo tương tự hỗn hợp. - 91 3.2.6.1 Tổng quan về các bộ dữ liệu kinh tế - xã hội Việt Nam dùng thử nghiệm. - 91 3.2.6.2 Trích lọc dữ liệu. - 93 3.2.6.3 Phân lớp với bộ dữ liệu Tiểu học. - 93 3.2.6.4 Phân lớp với bộ dữ liệu Ngân hàng. - 97 3.3 Bài toán phân cụm dữ liệu với thuật toán k-medoids sử dụng độ đo tương tự hỗn hợp MSM-R. - 105 3.3.1 Thuật toán phân cụm dữ liệu k-medoids. - 106 3.3.2 Phân cụm dữ liệu kinh tế - xã hội Việt Nam với độ đo MSM-R. - Phân cụm với bộ dữ liệu Tiểu học. - Phân cụm với bộ dữ liệu Ngân hàng. - Cấu trúc file dữ liệu và các hàm tính khoảng cách đã được lập trình 122 Phụ lục 3. - Kết quả phân lớp các bộ dữ liệu thử nghiệm sau khi đã rời rạc hóa các thuộc tính số. - Đặc điểm của dữ liệu kinh tế - xã hội và bài toán phân lớp dữ liệu. - Cấu trúc và một số bản ghi ví dụ của bộ dữ liệu điều tra khả năng đọc và làm toán của học sinh tiểu học (trích bằng phần mềm SPSS. - Cấu trúc và một số bản ghi ví dụ của bộ dữ liệu gốc về khách hàng vay vốn ngân hàng (trích bằng phần mềm SPSS. - 145 - 8 - DANH MỤC CÁC KÝ HIỆU, THUẬT NGỮ VÀ TỪ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt BI Business Intelligence Kinh doanh thông minh/trí tuệ doanh nghiệp DA/PA Data/Pattern analysis Phân tích dữ liệu/mẫu DBMS Database Management System Hệ quản trị cơ sở dữ liệu IND Indiscernibility Quan hệ không phân biệt được KDD Knowledge Discovery and Data Mining Phát hiện tri thức và Khai phá dữ liệu KE Knowledge Extraction Trích chọn tri thức ML Machine Learning Học máy MSM Mixed Similarity Measure Độ đo tương tự hỗn hợp MSM-R Mixed Similarity Measure based on Rough sets theory Độ đo tương tự hỗn hợp có trọng số dựa trên lý thuyết tập thô PAM Partitioning Around Medoids Phân vùng quanh các tâm RS Rough set Tập thô SPSS Statistical Package for the Social Sciences Phần mềm thống kê chuyên dụng SPSS ⇒ Dẫn đến - 9 - DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ Hình 1.1 Mối quan hệ của KDD với các lĩnh vực khác [42. - 22 Hình 1.3 Qui trình 5 bước khai phá dữ liệu. - 25 Hình 1.4 Mô hình hệ thống khai phá dữ liệu [42. - 77 Hình 3.1 Độ chính xác phân lớp k-NN. - 84 Hình 3.2 Độ chính xác phân lớp k-NN. - 84 Hình 3.3 Độ chính xác phân lớp k-NN. - 85 Hình 3.4 Độ chính xác phân lớp k-NN. - 85 Hình 3.5 Độ chính xác phân lớp k-NN. - 86 Hình 3.6 Độ chính xác phân lớp k-NN. - 86 Hình 3.7 So sánh độ chính xác lớn nhất của bộ phân lớp k-NN. - 89 Hình 3.9 Kết quả phân lớp với dữ liệu có thuộc tính ordinal. - 91 Hình 3.10 Kết quả phân lớp bộ dữ liệu Ngân hàng. - 98 Hình 3.11 Kết quả phân lớp bộ dữ liệu Ngân hàng 1 bằng SPSS. - 103 Hình 3.12 Kết quả phân lớp bộ dữ liệu Ngân hàng 2 bằng SPSS. - 104 - 10 - Hình 3.14 Kết quả phân lớp khi sử dụng toàn bộ dữ liệu để kiểm thử. - 105 Hình PL3.1 Độ chính xác lớn nhất của bộ phân lớp k-NN. - cho dữ liệu đã rời rạc hóa với k=1. - 125 Hình PL3.2 Độ chính xác lớn nhất của bộ phân lớp k-NN. - cho dữ liệu đã rời rạc hóa với k=3. - 125 Hình PL3.3 Độ chính xác lớn nhất của bộ phân lớp k-NN. - cho dữ liệu đã rời rạc hóa với k=5. - 126 Hình PL3.4 Độ chính xác lớn nhất của bộ phân lớp k-NN. - cho dữ liệu đã rời rạc hóa với k=7. - 126 Hình PL3.5 Độ chính xác lớn nhất của bộ phân lớp k-NN. - cho dữ liệu đã rời rạc hóa với k=9. - 127 Hình PL3.6 Độ chính xác lớn nhất của bộ phân lớp k-NN. - cho dữ liệu đã rời rạc hóa với k=10. - 64 Bảng 2.2 Bảng dữ liệu ví dụ về khám lâm sàng. - 66 Bảng 2.3 Bộ dữ liệu ví dụ. - 75 Bảng 3.1 Mô tả đặc điểm của các bộ dữ liệu thử nghiệm. - 82 Bảng 3.2 So sánh độ chính xác của bộ phân lớp k-NN. - 83 Bảng 3.3 So sánh độ chính xác lớn nhất của bộ phân lớp k-NN. - 89 Bảng 3.5 Kết quả phân lớp với dữ liệu có thuộc tính ordinal. - 90 Bảng 3.6 Danh sách các thuộc tính của bộ dữ liệu Tiểu học. - 97 Bảng 3.12 Kết quả phân lớp cho bộ dữ liệu Ngân hàng 1. - 100 Bảng 3.13 Kết quả phân lớp cho bộ dữ liệu Ngân hàng 2. - 104 Bảng 3.15 Kết quả phân lớp khi sử dụng toàn bộ dữ liệu để kiểm thử. - 107 - 12 - Bảng 3.18 Kết quả phân cụm cho dữ liệu Tiểu học. - 108 Bảng 3.19 Kết quả phân cụm cho dữ liệu Ngân hàng. - 109 Bảng PL1.1 Bộ dữ liệu theo Goodall. - 122 Bảng PL3.1 So sánh độ chính xác của bộ phân lớp k-NN cho dữ liệu đã rời rạc hoá. - và phân lớp bằng cây quyết định cho dữ liệu đã rời rạc hoá. - 128 Bảng PL5.1 Cấu trúc của bộ dữ liệu Tiểu học. - 139 Bảng PL5.2 Giá trị của một số biến trong bộ dữ liệu Tiểu học. - 140 Bảng PL5.3 Ví dụ một số bản ghi của bộ dữ liệu Tiểu học. - 141 Bảng PL6.1 Cấu trúc của bộ dữ liệu Ngân hàng. - 142 Bảng PL6.2 Giá trị của một số trường trong bộ dữ liệu Ngân hàng. - 143 Bảng PL6.3 Ví dụ một số bản ghi trong bộ dữ liệu Ngân hàng. - Chính vì vậy, khối lượng dữ liệu con người thu thập được thông qua các hoạt động kinh tế - xã hội ngày càng lớn, hình thành nên những nhà kho dữ liệu có dung lượng hàng terabyte, các hệ thống máy tính được kết nối mạng với nhau làm cho các dữ liệu ngày càng trở nên phong phú và phức tạp. - Trong bối cảnh đó, con người được máy tính hỗ trợ quản lý và lưu trữ dữ liệu có dung lượng khổng lồ nhưng khả năng phân tích, hiểu được những ngữ nghĩa, tri thức ẩn chứa trong đó còn rất hạn chế. - Một trong các lĩnh vực đang được nghiên cứu, ứng dụng mạnh mẽ trong khai thác, phân tích dữ liệu ngày nay là Phát hiện tri thức và khai phá dữ liệu. - Trong thực tế, để thể hiện thông tin của các đối tượng, các hiện tượng hay vấn đề nào đó người ta phải sử dụng kết hợp nhiều loại dữ liệu khác nhau cùng lúc như kiểu dữ liệu số, dữ liệu định danh, dữ liệu định danh có thứ tự. - Bài toán đặt ra là làm thế nào để kết hợp các thuộc tính lại với nhau để giải quyết tốt nhất các bài toán cơ bản trong khai phá dữ liệu như Phân lớp, Phân cụm. - Với các dữ liệu thuần nhất hiện đã có nhiều độ đo được đề xuất, mỗi độ đo này có một ý nghĩa riêng và tuỳ thuộc theo lĩnh vực bài toán áp dụng cũng như đặc tính của loại dữ liệu. - Việc chuyển đổi các dạng dữ liệu khác nhau về cùng một loại trong khi tính toán độ tương tự có thể dẫn đến sai khác về ý nghĩa hay mất mát thông tin. - Đồng thời, mỗi loại dữ liệu khác nhau sẽ có ý nghĩa khác nhau nên không thể kết hợp chúng lại trong cùng một độ đo một cách thuần tuý. - Vì những lý do đó, đề tài của luận án này nhằm nghiên cứu độ đo tương tự hỗn hợp hoặc độ đo khoảng cách hỗn hợp giữa các đối tượng để có thể xử lý dữ liệu - 14 - dưới dạng hỗn hợp mà không cần thiết phải chuyển đổi các dạng dữ liệu, như vậy sẽ tránh được mất mát thông tin. - Mục đích nghiên cứu của luận án Qua quá trình tìm hiểu, nghiên cứu về phát hiện tri thức và khai phá dữ liệu, đặc điểm của các loại dữ liệu và đặc biệt là độ đo tương tự hỗn hợp, tác giả nhận thấy độ đo tương tự hỗn hợp hay độ đo khoảng cách hỗn hợp đóng vai trò rất quan trọng trong các bài toán khai phá dữ liệu dựa trên khoảng cách. - Vì vậy, mục đích của luận án là nghiên cứu nhằm tìm ra hoặc cải tiến các phương pháp, các kỹ thuật tính toán độ đo tương tự hỗn hợp áp dụng trong bài toán phân lớp dữ liệu một cách hiệu quả, thực hiện các thực nghiệm trên các bộ dữ liệu chuẩn dùng để nghiên cứu phát hiện tri thức và khai phá dữ liệu, thực nghiệm trên bộ dữ liệu kinh tế - xã hội thực tế của Việt Nam. - Đối tượng, phạm vi nghiên cứu Nghiên cứu các vấn đề cơ bản của phát hiện tri thức và khai phá dữ liệu. - bài toán phân lớp, phân cụm trong phát hiện tri thức và khai phá dữ liệu. - Các nội dung nghiên cứu sẽ được thử nghiệm trên một số bộ dữ liệu của cộng đồng nghiên cứu phát hiện tri thức và khai phá dữ liệu trên internet và các dữ liệu kinh tế - xã hội của Việt Nam. - Phương pháp nghiên cứu Tác giả sử dụng phương pháp khảo sát các vấn đề cần nghiên cứu, so sánh, phân tích dựa trên những lý thuyết cơ bản của các lĩnh vực như: phát hiện tri thức và khai phá dữ liệu. - Các đề xuất của tác giả sẽ được kiểm nghiệm bằng các dữ liệu chuẩn được công bố cho cộng đồng nghiên cứu sử dụng và các dữ liệu kinh tế - xã hội thực tế của Việt Nam. - Khi phân tích các dữ liệu thực tế, các đối tượng thường được thể hiện bằng một bộ các dữ liệu có nhiều kiểu khác nhau hay nói cách khác là tồn tại dưới dạng hỗn hợp. - Trong các phương pháp xử lý truyền thống người ta thường phải chuyển đổi dữ liệu về cùng một dạng để thực hiện phân tích, đồng thời việc xác định trọng số cho các thuộc tính dữ liệu thường phụ thuộc vào kinh nghiệm và các yếu tố chủ quan của người nghiên cứu, chính vì thế, tác giả đã đề xuất một phương pháp tự động xác định trọng số cho các thuộc tính trong độ đo tương tự hỗn hợp với tiếp cận lý thuyết tập thô để có thể áp dụng trên các dữ liệu loại này. - Ở đây, tác giả sử dụng lý thuyết tập thô để xác định trọng số cho các thuộc tính do trong lý thuyết tập thô cho phép tìm được mối quan hệ giữa các thuộc tính, đây cũng là một hướng ứng dụng mới của lý thuyết tập thô trong các bài toán phát hiện tri thức và khai phá dữ liệu. - Tác giả cũng thực hiện thử nghiệm bước đầu cho bài toán phân cụm dữ liệu sử dụng độ đo tương tự hỗn hợp có trọng số này. - Thông qua các kết quả thử nghiệm về phân lớp bằng thuật toán láng giềng gần nhất với các bộ dữ liệu chuẩn trên Internet và các bộ dữ liệu thực tế kinh tế - xã hội Việt Nam, qua việc đánh giá tác động của số lượng thuộc tính theo các kiểu dữ liệu khác - 16
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt