Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số phương pháp tìm các luật kết hợp phân lớp trên tập mẫu học và ứng dụng trong chẩn đoán bệnh

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:74

Thêm vào BST

Báo xấu

39
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của luận văn này là tổng hợp các kiến thức về kỹ thuật khai phá dữ liệu bằng phương pháp tìm các luật kết hợp phân lớp trên tập mẫu học. Đề tài đi sâu nghiên cứu một mảng kỹ thuật khai phá dữ liệu nhằm hỗ trợ cho mục đích sử dụng khác nhau. Có mục đích tìm các nhân tố tích cực, có mục đích tìm các lỗi lưu trữ trong tập dữ liệu, có mục đích tìm kiếm nhận dạng tội phạm, gian lận tài chính hoặc cũng có thể làm dự báo, phân tích thị trường. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số phương pháp tìm các luật kết hợp phân lớp trên tập mẫu học và ứng dụng trong chẩn đoán bệnh

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM THANH TUẤN NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP TÌM CÁC LUẬT KẾT HỢP PHÂN LỚP TRÊN TẬP MẪU HỌC VÀ ỨNG DỤNG TRONG CHẨN ĐOÁN BỆNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên, 2019 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM THANH TUẤN NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP TÌM CÁC LUẬT KẾT HỢP PHÂN LỚP TRÊN TẬP MẪU HỌC VÀ ỨNG DỤNG TRONG CHẨN ĐOÁN BỆNH Chuyên ngành: Khoa học máy tính Mã số: 8 48 01 01 Người hướng dẫn khoa học: TS. Lê Văn Phùng Thái Nguyên, 2019 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện, dưới sự hướng dẫn khoa học của TS. Lê Văn Phùng. Các số liệu và kết quả trình bày trong luận văn là trung thực, chưa được công bố bởi bất kỳ tác giả này hay ở bất kỳ công trình nào khác. Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
ii LỜI CẢM ƠN Trong quá trình thực hiện đề tài “Nghiên cứu một số phương pháp tìm các luật kết hợp phân lớp trên tập mẫu học và ứng dụng trong chẩn đoán bệnh”, tôi đã nhận được rất nhiều sự giúp đỡ, tạo điều kiện của tập thể Ban Giám hiệu, Phòng Đào tạo, khoa Công nghệ thông tin và các phòng chức năng của trường Đại học Công nghệ thông tin và truyền thông, Đại học Thái Nguyên. Tôi xin bày tỏ lòng cảm ơn chân thành về sự giúp đỡ quý báu đó. Tôi xin được bày tỏ lòng biết ơn sâu sắc đến TS. Lê Văn Phùng là thầy giáo trực tiếp hướng dẫn, chỉ bảo giúp tôi hoàn thành luận văn này. TÁC GIẢ LUẬN VĂN Phạm Thanh Tuấn Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
iii MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN ................................................................................................... ii DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT....................................... v DANH MỤC BẢNG BIỂU ............................................................................. vi DANH MỤC HÌNH VẼ .................................................................................. vii MỞ ĐẦU ........................................................................................................ viii CHƯƠNG 1. PHÂN LỚP VÀ PHƯƠNG PHÁP XÂY DỰNG CÂY PHÂN LỚP THEO TẬP MẪU HỌC ............................................................ 1 1.1. Tổng quan về kỹ thuật khai phá dữ liệu ..................................................... 1 1.1.1. Khái niệm về khai phá dữ liệu ................................................................ 1 1.1.2. Một số phương pháp khai phá dữ liệu hiện đại và thông dụng............... 2 1.1.3. Các ứng dụng khai phá dữ liệu ............................................................... 3 1.2. Những vấn đề chung nhất về phân lớp và phương pháp phân lớp cơ bản . 7 1.2.1 Khái niệm phân lớp dữ liệu ...................................................................... 7 1.2.2. Các bước tiến hành phân lớp dữ liệu ...................................................... 7 1.2.3. Phân lớp theo cây quyết định .................................................................. 9 1.2.4. Phân lớp kiểu Bayes .............................................................................. 12 1.2.5. Phân lớp dựa trên các quy tắc IF-THEN............................................... 13 1.2.6. Phân lớp dựa trên luật kết hợp .............................................................. 16 1.2.7. Phân lớp dựa vào K-lân cận gần nhất ................................................... 18 1.2.8. Phân lớp dựa vào giải thuật di truyền ................................................... 19 1.2.9. Phân lớp theo cách tiếp cận tập thô....................................................... 20 1.2.10. Phân lớp theo cách tiếp cận tập mờ .................................................... 21 1.3. Khái niệm về tập mẫu học và phương pháp xây dựng cây phân lớp ....... 24 1.3.1. Định nghĩa tập mẫu học ........................................................................ 24 1.3.2. Xây dựng cây phân lớp dựa theo Khóa ................................................. 24 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
iv 1.3.3. Xây dựng cây phân lớp nhờ các luật kết hợp phân lớp (Class Association Rules) trong bảng mẫu học ......................................................... 27 CHƯƠNG 2. MỘT SỐ PHƯƠNG PHÁP TÌM CÁC LUẬT KẾT HỢP PHÂN LỚP TRÊN TẬP MẪU HỌC .......................................................... 29 2.1. Phương pháp phân lớp dựa trên luật kết hợp ........................................... 29 2.1.1. Các bước tiến hành phân lớp dựa trên luật kết hợp .............................. 29 2.1.2. Tạo luật kết hợp bằng cây quyết định ................................................... 29 2.2. Một số thuật toán cổ điển xây dựng cây phân lớp dựa trên luật kết hợp . 29 2.2.1. Thuật toán CBA-RG ............................................................................. 30 2.2.2. Thuật toán CBA-CB.............................................................................. 32 2.3. Thuật toán hiện đại ................................................................................... 34 2.3.1. Thuật toán CBA cải tiến........................................................................ 34 2.3.2. Ví dụ áp dụng thuật toán cải tiến .......................................................... 37 CHƯƠNG 3. CHƯƠNG TRÌNH THỬ NGHIỆM TÌM CÁC LUẬT KẾT HỢP PHÂN LỚP DỰA TRÊN TẬP MẪU HỌC....................................... 42 3.1. Bài toán thử nghiệm ................................................................................. 42 3.1.1. Bài toán và tập mẫu học đầu vào .......................................................... 42 3.1.2. Chọn thuật toán thử nghiệm .................................................................. 46 3.2. Môi trường thử nghiệm ............................................................................ 47 3.2.1. Chọn môi trường chứa dữ liệu đầu vào ................................................ 47 3.2.2. Chọn ngôn ngữ lập trình ....................................................................... 47 3.3. Nội dung và kết quả thử nghiệm .............................................................. 47 3.3.1. Mô hình thuật toán thử nghiệm ............................................................. 47 3.3.3. Một số giao diện chính của chương trình thử nghiệm .......................... 50 3.4. Đánh giá chương trình thử nghiệm .......................................................... 51 3.5. Mở rộng bài toán ...................................................................................... 51 KẾT LUẬN .................................................................................................... 60 TÀI LIỆU THAM KHẢO ............................................................................ 62 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
v DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT 1. DM – Data Mining. 2. CSDL – Cơ sở dữ liệu. 3. CBA - Classification-Based Associon 4. CMAR - Classification based on Multiple Asociation Rule Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
vi DANH MỤC BẢNG BIỂU Bảng 1.1. Ví dụ về tập mẫu học…………………………………….….....15 Bảng 1.2. Các bộ huấn luyện đã được phân lớp trong CSDL……….…....20 Bảng 1.3. Ví dụ tập mẫu học được phân lớp dựa theo khóa…………...…33 Bảng 2.1. Ví dụ tập mẫu học để tìm các luật kết hợp phân lớp theo thuật toán cải tiến……………………………………………………...…………..47 Bảng 2.2. Bảng tổng hợp………………………………………..………...49 Bảng 2.3a. Khoản mục…………………………………………..…….…...50 Bảng 2.3b. Các luật kết hợp phân lớp phổ biến 1 – Khoản mục……..….…50 Bảng 2.3c. Các luật kết hợp phân lwps 2 – Khoản mục………..……….…50 Bảng 3.1. Tập mẫu học……………………………………………………55 Bảng 3.2. Bảng mẫu học được số hóa…………………………………….56 Bảng 3.3. Bảng tổng hợp kết quả thu được…………………………...…..59 Bảng 3.4. Bảng mấu học (mở rộng) đầu vào……………………………...60 Bảng 3.5. Bảng mẫu học mở rộng được số hóa………………………......64 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
vii DANH MỤC HÌNH VẼ Hình 1.1. Cây quyết định cho việc chơi Gold………….………………...….16 Hình 1.2. Một tập thô xấp xỉ tập các bộ của C khi dùng các tập xấp xỉ trên và dước của C. Các vùng hình chũ nhật biểu diễn các lớp tương đương………………………………………………………...………………27 Hình 1.3. Các giá trị mờ thật với thu nhập, biểu diễn mức thành viên các giá trị thu nhập theo các loại {thấp, trung bình, cao}……………...................…28 Hình 1.4. Cây phân lớp xây dựng với 2 trường hợp…………………………34 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
viii MỞ ĐẦU 1. Lý do chọn đề tài Thế kỷ XXI được xem là một kỷ nguyên của công nghệ thông tin. Cùng với việc ứng dụng công nghệ thông tin ở hầu hết các lĩnh vực trong nhiều năm qua dẫn đến lượng dữ liệu, thông tin của nhân loại được lưu trữ ngày một tăng. Nguồn dữ liệu khổng lồ ấy được tích lũy với tốc độ bùng nổ từ rất nhiều lĩnh vực: khoa học, kinh doanh, giao dịch, thương mại, chứng khoán,… Vậy chúng ta có thể khai thác được gì từ “núi” dữ liệu tưởng chừng như bỏ đi ấy. Cùng với việc tăng không ngừng khối lượng dữ liệu, các hệ thống thông tin cũng được chuyên môn hóa, phân hạch hóa theo các lĩnh vực như sản xuất, tài chính, buôn bán thị trường .v.v, tuy nhiên các hệ quản trị cơ sở dữ liêu truyền thống chỉ khai thác được một lượng thông tin nhỏ không còn đáp ứng đủ những yêu câu, những thách thức mới. Do vậy một khuynh hướng mới được ra đời đó là kỹ thuật phát hiện tri thức trong cơ sở dữ liệu. Khai phá dữ liệu (Data Mining – DM) ra đời phần nào đó đã giải quyết hữu hiệu những yêu cầu, thách thức đó. Một trong những lĩnh vực nghiên cứu các phương pháp ứng dụng khai phá dữ liệu, tìm kiếm tri thức, kết xuất tri thức… từ dữ liệu là tìm kiếm các Luật kết hợp phân lớp (Class Association Rules) cũng được nghiên cứu từ nhiều năm trước đây và đã có những kết quả khả quan và mang lại hướng ứng dụng có hiệu quả cao. Ngày nay, kỹ thuật khai phá dữ liệu dựa trên việc tìm kiếm các luật kết hợp phân lớp đã được áp dụng và mang lại hiệu quả cho nhiều ngành, nhiều lĩnh vực như: Kinh tế, tài chính, khoa học - kỹ thuật, ngân hàng, thương mại, giáo dục, y tế… các kỹ thuật khai phá dự liệu bằng Luật kết hợp phân lớp rất đa dạng và phong phú như các kỹ thuật dựa trên các thuật toán CBA-RG, CBA-CB,… Với mong muốn nắm vững hơn các quá trình phát hiện tri thức từ dữ liệu Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
ix sử dụng Luật kết hợp phân lớp nhằm phục vụ công tác nghiên cứu chuyên môn cũng như mong muốn đưa các kỹ thuật khai phá dữ liệu sử dụng Luật kết hợp phân lớp vào thực tế nên tôi lựa chọn thực hiện luận văn tốt nghiệp với đề tài “Nghiên cứu một số phương pháp tìm các luật kết hợp phân lớp trên tập mẫu học và ứng dụng trong chẩn đoán bệnh”. Mục đích thực hiện luận văn này là tổng hợp các kiến thức về kỹ thuật khai phá dữ liệu bằng phương pháp tìm các luật kết hợp phân lớp trên tập mẫu học. 2. Đối tượng và phạm vi nghiên cứu: Đối tượng nghiên cứu là những kỹ thuật phân lớp dựa trên luật kết hợp Phạm vi nghiên cứu tập trung vào các thuật toán tìm kiếm Luật kết hợp phân lớp cổ điển và hiện đại. 3. Hướng nghiên cứu của đề tài: Nghiên cứu các kỹ thuật khai phá dữ liệu nói chung, trong đó chú trọng việc tìm các luật kết hợp phân lớp trên tập mẫu học. Nghiên cứu những bài toán ứng dụng phương pháp cải tiến tìm các luật kết hợp phân lớp trên tập mẫu học. 4. Phương pháp nghiên cứu: Kết hợp lý thuyết với đánh giá thực nghiệm. Sưu tập và tổng hợp các kết quả nghiên cứu về khai phá dữ liệu, thuật toán tìm các luật kết hợp phân lớp từ nguồn sách của các nhà xuát bản trong và ngoài nước, các luận văn cao học, luận án tiến sĩ và các bài báo khoa học. Phân tích bài toán ứng dụng và chọn lọc thuật toán thử nghiệm thích hợp (dự kiến là áp dụng thuật toán cải tiến). 5. Ý nghĩa khoa học, thực tiễn của đề tài: * Ý nghĩa khoa học Đề tài đi sâu nghiên cứu một mảng kỹ thuật khai phá dữ liệu nhằm hỗ trợ cho mục đích sử dụng khác nhau. Có mục đích tìm các nhân tố tích cực, có Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
x mục đích tìm các lỗi lưu trữ trong tập dữ liệu, có mục đích tìm kiếm nhận dạng tội phạm, gian lận tài chính hoặc cũng có thể làm dự báo, phân tích thị trường,.... Trong phạm vi ứng dụng rộng rãi như đã nêu ở trên, việc nghiên cứu các thuật toán tìm các luật kết hợp phân lớp dựa trên tập mẫu học đã mang ý nghĩa khoa học và thực tiễn rất lớn. Đề tài thực hiện với hy vọng sẽ đóng góp phần khoa học nhất định trong việc tổng hợp, đánh giá một nhiệm vụ khai phá dữ liệu quan trọng nhằm phát hiện những tri thức có ý nghĩa lớn, bảo đảm cơ sở toán học trong chuyên ngành khoa học máy tính. * Ý nghĩa thực tiễn Góp phần chứng tỏ khả năng ứng dụng phong phú của khai phá dữ liệu, áp dụng trực tiếp vào việc chuẩn đoán bệnh trong các bệnh viện. Dựa trên việc nghiên cứu một số phương pháp tìm các luật phân lớp trên tập mẫu học, đã làm rõ và phong phú thêm về thuật toán mới, thuật toán cải tiến để ứng dụng vào thực tế. Luận văn có thể được sử dụng làm tài liệu tham khảo cho các sinh viên đại học, học viên ngành Công nghệ thông tin nghiên cứu về khai phá dữ liệu bằng luật kết hợp phân lớp. Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
1 CHƯƠNG 1. PHÂN LỚP VÀ PHƯƠNG PHÁP XÂY DỰNG CÂY PHÂN LỚP THEO TẬP MẪU HỌC 1.1. Tổng quan về kỹ thuật khai phá dữ liệu Trong máy tính, thuật ngữ dữ liệu được xem như là các đặc tính được biết đến mà có thể ghi lại và lưu trữ trên các thiết bị ghi nhớ của máy tính. Dữ liệu là những mô tả về sự vật, con người và sự kiện trong thế giới thực. Dữ liệu bao gồm số, ký tự, văn bản, hình ảnh, đồ họa, âm thanh, đoạn phim,…. Có một số giá trị nào đó đối với người sử dụng và chúng được lưu trữ, xử lý trong máy tính. Ví dụ: - Dữ liệu về khách: tên, địa chỉ, điện thoại, thẻ tín dụng... - Dữ liệu về xe ô tô của khách: hãng xe, đời xe, năm sản xuất… - Dữ liệu về nhật ký sử chữa: ngày phục vụ, tên thợ sửa chữa, số tiền thanh toán… Trong hoạt động kinh tế xã hội của con người, người ta thường chia ra hai loại dữ liệu là loại dữ liệu phản ảnh cấu trúc nội bộ của cơ quan (nhân sự, nhà xưởng, thiết bị,… dữ liệu ít biến động) và loại dữ liệu phản ánh hoạt động của tổ chức (sản xuất, mua bán, giao dịch,…). Trong doanh nghiệp, không kể con người và thiết bị, dữ liệu cùng với xử lý là hai thành phần cơ bản của hệ thống: dữ liệu thường dùng để ghi nhận thực trạng. 1.1.1. Khái niệm về khai phá dữ liệu Theo bách khoa toàn thư, khai phá dữ liệu (DM) là khâu chủ yếu trong quá trình phát triển tri thức từ dữ liệu để trợ giúp cho việc làm quyết định trong quản lý. DM sử dụng nhiều phương pháp của phân tích thống kê, của lý thuyết nhận dạng, của các hệ học, các mạng nơ-ron nhân tạo… nhắm phát hiện các mẫu hình tri thức trực tiếp từ các kho dữ liệu. DM và phát triển tri thức là những Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
2 hướng nghiên cứu mới trong tổ chức và khai thác các hệ thống thông tin và trợ giúp quyết định. Thuật ngữ DM do Fayyad Smyth và Piatestky-Shapiro đề xuất năm 1989. Có rất nhiều định nghĩa khác nhau về DM đã được đưa ra. Theo định nghĩa đơn giản nhất, DM là việc trích lọc tri thức từ một lượng lớn dữ liệu. Nó còn có một số tên gọi khác như “trích lọc tri thức”, “phân tích dữ liệu/mẫu”, “khảo cổ dữ liệu”. “nạo vét dữ liệu”,…. Giáo sư Tom Mitchell đã đưa ra định nghĩa về DM như sau: “DM là việc sử dụng dữ liệu lịch sử để khám phá những quy tắc và cải thiện những quyết định trong tương lai”. Với cách tiếp cận thực tế hơn, tiến sĩ Fayyad đã phát biểu : “DM thường được xem là việc khám phá tri thực trong các CSDL, là một quá trình trích xuất những thông tin ẩn, trước đây chữ biết và có khả năng là hữu ích dưới dạng các quy luật, ràng buộc, quy tắc trong CSDL”. Các nhà thống kê thì xem “DM như một quá trình phân tích được thiết kế thăm dò và/hoặc các mối quan hệ mang tính hệ thống giữa các biến và sau đó sẽ hợp thực hóa các kết quả tìm được bằng cách áp dụng các mẫu đã phát hiện được cho tập con mới của dữ liệu”. Nói chung, DM là cốt lõi của quá trình phát hiện tri thức. Nó gồm có các giải thuật DM chuyên dùng, một số quy định về hiệu quả tính toán chấp nhận được. DM nhằm tìm ra những mẫu mới, mẫu có tính chất không tầm thường, những thông tin tiềm ẩn mang tính dự đoán chưa được biết đến và có khả năng mang lại lợi ích. Nói gọn hơn, DM là việc tìm kiếm các kiến thức/các mẫu hấp dẫn trong kho dữ liệu. DM là hoạt động trọng tâm của quá trình phát hiện tri thức. 1.1.2. Một số phương pháp khai phá dữ liệu hiện đại và thông dụng Với hai đích chính của khai thác dữ liệu là dự đoán (Prediction) và mô tả (Description), người ta thường sử dụng các phương pháp sau cho khai phá dữ Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
3 liệu: - Phân lớp (Classification) - Hồi quy (Regression) - Phân nhóm (Clustering) - Tổng hợp (Summarization) - Mô hình ràng buộc (Dependency modeling) - Dò tìm biến đổi và độ lệch (Change and Deviation Dectection) - Biểu diễn mô hình (Model Representation) - Kiểm định mô hình (Model Evaluation) - Phương pháp tìm kiếm (Search Melthod) 1.1.3. Các ứng dụng khai phá dữ liệu Khai phá dữ liệu (DM) được vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn dữ liệu phong phú được lưu trữ trong các hệ thống thông tin. Tùy theo bản chất của từng lĩnh vực, việc vận dụng Data mining có những cách tiếp cận khác nhau. DM được vận dụng có hiệu quả để giải quyết các bài toán phức tạp trong những ngành đòi hỏi kĩ thuật cao như: tìm kiếm mỏ dầu từ ảnh viễn thám, xác định vùng gãy trong ảnh địa chất để dự đoán thiên tai, cảnh báo hỏng hóc trong các hệ thống sản xuất. Phân nhóm và dự đoán là những công cụ rất cần thiết cho việc quy hoạch và phát triển hệ thống quản lý và sản xuất trong thực tế như: dự đoán tái sử dụng điện năng cho các công ty cung cấp điện, lưu lượng viễn thông cho các công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của sản phẩm trên thị trường cho các công ty tài chính hay phân nhóm khách hàng tiềm năng. Ngoài ra DM còn được áp dụng trong việc giải quyết các vấn đề xã hội như: phát hiện tội phạm hay tăng cường an ninh xã hội và mang lại những hiệu Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
4 quả thiết thực cho các hoạt động trong đời sống hàng ngày. Việc ứng dụng DM phân theo ngành phân bố trong khoảng 5 năm gần đây với tỷ lệ sau. * Phân tích dữ liệu gen và sinh học y học - Trong sinh học, DM dùng để tìm kiếm, so sánh các hệ gen và thông tin di truyền, tìm mối liên hệ giữa các hệ gen và chuẩn đoán một số bệnh di truyền. DM đã trở thành một công cụ mạnh và đóng góp thiết thực vào việc phân tích gen theo các cách sau: Nghiên cứu tương tự và so sánh các chuỗi gen: Một nghiên cứu quan trọng trong phân tích gen là nghiên cứu tương tự là so sánh các chuỗi gen. các chuỗi gen được cô lập từ các mô bệnh khỏe và có thể được so sánh với nhau để nhận dạng những khác biệt giữa hai lớp gen. Phân tích kết hợp: Nhận dạng các chuỗi gen cùng xảy ra, phân tích kết hợp có thể được sử dụng giúp chúng ta xác định các loại gen thường kết hợp với nhau để gây nên bệnh. Phân tích hướng đi: Liên kết các gen ở các giai đoạn khác nhau của quá trình phát triển bệnh, nếu một chuỗi hoạt động của các gen ở những giai đoạn khác nhau của bệnh được xác định, thì có thể giúp chúng ta chế tạo ra các dược phẩm can thiệp vào từng giai đoạn của bệnh. Do đó, có thể tạo được cách điều trị bệnh hiệu quả hơn. - Trong y học: DM giúp tìm ra mối liên hệ giữa các triệu chứng, chuẩn đoán bệnh. * Phân tích dữ liệu tài chính Trên phương diện tài chính và thị trường chứng khoán, DM dùng để phân tích tình hình tài chính phân tích đầu tư, phân tích cổ phiếu. Dữ liệu tài chính nhận được tương đối hoàn chỉnh, đáng tin cậy và chất lượng cao làm thuận lợi cho việc phân tích dữ liệu, DM một cách hệ thống. Các ứng dụng của DM vào lĩnh vực tài chính như: Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
5 - Dự đoán trả tiền vay và phân tích chính sách tín dụng khách hàng: Dự đoán trả tiền vay và phân tích chính sách tín dụng khách hàng là vấn đề quan trọng đối với việc kinh doanh của ngân hàng. Có nhiều yếu tố (chẳng hạn: tỉ lệ trả lên thu nhập, mức học vấn, vùng dân cư, lịch sử tín dụng,…) có thể ảnh hưởng mạnh hoặc yếu đến việc thực hiện trả tiền vay và sự đánh giá mức độ tín nhiệm khách hàng. Các phương pháp DM như lựa trọn đặc trưng, xếp hạng các thuộc tính liên quan có thể giúp xác định các yếu tố quan trọng và loại bỏ những yếu tố không liên quan. Do đó, ngân hàng có thể điều chỉnh chính sách cho vay đối với những khách hàng mà trước đây ngân hàng đã từ chối nhưng nay tỉ lệ mạo hiểm đối với họ là thấp dựa vào các phân tích trên. - Phát hiện các tội phạm tài chính: để phát hiện việc chuyển tiền bất chính vào ngân hàng và tội phạm tài chính, việc tích hợp thông tin từ các CSDL khác nhau (CSDL giao dịch ngân hàng, CSDL về lịch sử tội phạm) là rất quan trọng. Sau khi có dữ liệu tổng hợp chúng ta có thể dựa trên các công cụ của DM để phát hiện ra mẫu khác thường. * Dịch vụ bán lẻ Trong thông tin thương mại: dùng để phân tích dữ liệu người dùng, phân tích dữ liệu maketing, phân tích đầu tư, phát hiện gian lận. Dịch vụ bán lẻ là một trong lĩnh vực của DM. Một lượng dữ liệu khổng lồ đã và đang thu nhập ngày càng tăng, đặc biệt với sự gia tăng về sự tiện lợi, lợi ích và tính phổ biến của việc kinh doanh trên web, thương mại điện tử. Dữ liệu bán lẻ cung cấp một kho dữ liệu phong phú cho việc khai phá dữ liệu. Khai phá dữ liệu bán lẻ có thể giúp chúng ta xác định hành vi mua hàng của khách hàng, phát hiện những mẫu mua hàng của người dùng, những khuynh hướng mua hàng. Thiết kế các chiến dịch kinh doanh: giữ khách hàng – phân tích lòng trung thành của khách hàng: lòng trung thành của khách hàng và khuynh hướng Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
6 mua hàng có thể được phân tích một cách hệ thống. * Công nghiệp viễn thông Trong thông tin kĩ thuật: DM dùng để phân tích các sai hỏng, điều khiển và lập lịch trình. Công nghiệp viễn thông đã phát triển nhanh từ các dịch vụ điện thoại cục bộ và điện thoại đường dài cho đến các dịch vụ truyền thông khác như Voice, FAX, Image, E-mail, truyền dữ liệu web, các giao lộ dữ liệu khác, tích hợp viễn thông, mạng máy tính, internet, các phương tiện truyền thông khác đã và đang thực hiện. Điều này tạo ra một yêu cầu lớn về DM để giúp hiểu thêm việc kinh doanh, xác định các mẫu viễn thông, chặn đứng các hoạt động lừa dối tạo nhằm điều kiện sử dụng các tài nguyên tốt hơn và nâng cao được chất lượng dịch vụ. Về phân tích nhu cầu: dữ liệu viễn thông là các dữ liệu đa chiều đích thực, với các chiều như: giờ gọi, thời gian gọi, vị trí người gọi, vị trí người được gọi, kiểu cuộc gọi. Phân tích đa chiều với các dữ liệu kiểu này có thể giúp xác định nhu cầu và hành vi của các nhóm người dùng từng vùng,… Từ đó cung cấp các dịch vụ, thiết bị phù hợp hơn. Về phân tích các mẫu gian lân và xác định các mẫu khác thường: Việc xác định những người dùng gian lận tiềm năng và những mẫu sử dụng không điển hình là rất quan trọng. Những mẫu này có thể được khám phá bởi phân tích đa chiều, phân tích cụm, phân tích phần tử ngoài cuộc. * Công nghiệp viễn thông Khai phá dữ liệu được sử dụng rất nhiều để phân tích dữ liệu, hỗ trợ ra quyết định. * Khai thác dữ liệu Web Các trang web nổi tiếng trên thế giới đã làm dịch vụ tìm kiếm cho đông đảo khách hàng nhờ việc liên kết và sưu tập một khối lượng dữ liệu khổng lồ như Google, Alexa Internet archive, IBM webfountain, Internet Archive,…. Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
7 1.2. Những vấn đề chung nhất về phân lớp và phương pháp phân lớp cơ bản 1.2.1 Khái niệm phân lớp dữ liệu - Khái niệm Phân lớp dữ liệu là một quy trình để tìm ra một tập các mô hình để mô tả và phân lớp các lớp dữ liệu hoặc khái niệm nhằm mục đích phân loại dữ liệu hoặc dự đoán lớp của những đối tượng chưa biết. Việc đưa ra những mô hình phân lớp được dựa trên việc phân tích một tập mẫu học (Training Data), tức là các đối tượng dữ liệu đã biết trước lớp của chúng. Trên cơ sở đó rút ra các luật phân lớp. Các luật này sẽ được áp dụng cho tập dữ liệu có cùng cấu trúc như tập mẫu học. Chúng ta cũng phân biệt kỹ thuật phân lớp (Data classification) với kỹ thuật phân cụm dữ liệu (Data Clustering). Phân cụm dữ liệu (Data Clustering) nhằm mục đích nhóm các đối tượng trong tập dữ liệu thành các nhóm (hoặc lớp) sao cho các đối tượng trong một nhóm thì giống nhau về những tiêu thức nào đó và chúng sẽ khác với các đối tượng trong nhóm khác. Phân lớp dữ liệu (Data Classification) được dựa trên việc phân tích một mẫu học đã biết trước nhãn của lớp. Phân cụm dữ liệu không dựa trên tập mẫu học đã biết mà sử dụng các phương pháp, mô hình khác nhau và các tiêu thức phân loại để tiến hành phân nhóm tập dữ liệu. Có nhiều phương pháp được sử dụng cho kỹ thuật phân cụm, ví dụ: phân cụm dựa trên khoảng cách (Distance – Base Clustering), hoặc phân cụm dựa trên ràng buộc (Constrain - Base Clustering)… 1.2.2. Các bước tiến hành phân lớp dữ liệu Quá trình phân lớp dữ liệu có thể được chia làm các bước như sau: Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
8 * Bước 1 – Thu thập và tiền xử lý: thu thập tạo bảng mẫu học và xử lý trước khi đưa vào xây dựng mô hình. Tập mẫu học là một bảng quan hệ dạng chuẩn, trong đó có một cột là thuộc tính ghi lại giá trị phân lớp (class-attributes), và các cột khác ghi lại các giá trị dựa vào đó để phân lớp (non-class attributes). Tập mẫu học được thu thập hoặc rút ra từ tập dữ liệu thực tế. Các nội dung tiền xử lý bao gồm: - Làm sạch dữ liệu (Data cleaning): loại bỏ những tạp nhiễu ảnh hưởng đến mô hình (có thể dùng các kỹ thuật làm sạch khác nhau) - Phân tích mức thích hợp của thuộc tính: loại bỏ ra khỏi tập mẫu những thuộc tính không cần thiết (ví dụ như thuộc tính ngày trong tuần đối với những ứng dụng không liên quan) - Chuẩn hóa dữ liệu: nhằm loại bỏ dự bị thường dữ liệu hoặc loại bỏ sự thừa dữ liệu. - Chuyển hóa dữ liệu (data transformation): dữ liệu có thể được xử lý tới mức khái niệm ở mức cao hơn. Ví dụ giá trị thuộc tính thu nhập có được chuyển về các giá trị cao, thấp, trung bình. * Bước 2 – Học (Learning): Tập mẫu học được phân tích bằng một thuật toán phân lớp nó tạo ra một mô hình bao gồm các luật phân lớp. Trong bước này có thể sử dụng nhiều phương pháp và thuật toán khác nhau để xây dựng mô hình. * Bước 3 – Phân lớp: Mô hình được sử dụng cho việc phân lớp. Đầu tiên cần phải đánh giá độ chính xác của mô hình (bằng một số phương pháp khác nhau). Nếu độ chính xác của mô hình chấp nhận được thì mô hình sẽ được sử dụng cho việc phân lớp các đối tượng dữ liệu khác mà chưa biết lớp của chúng. - Đánh giá phương pháp phân lớp Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn