Tài liệu Các kỹ thuật phân cụm trong khai phá dữ liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Hiền Các kỹ thuật phân cụm trong khai phá dữ liệu LUẬN VĂN THẠC SĨ Hà Nội - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Hiền Các kỹ thuật phân cụm trong khai phá dữ liệu Ngành: Mã số: Công Nghệ Thông tin 60.48.05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Vũ Đức Thi Hà Nội - 2009 -1- LỜI CAM ĐOAN Tôi xin cam đoan luận văn “Các kỹ thuật phân cụm trong khai phá dữ liệu” là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn được sử dụng trung thực. Những kết luận của luận văn chưa từng được ai công bố trong bất kỳ công trình nghiên cứu nào khác. Học viên thực hiện Nguyễn Thị Thu Hiền -2- LỜI CẢM ƠN Luận văn được hoàn thành dưới sự hướng dẫn, chỉ bảo tận tình, chu đáo của PGS.TS Vũ Đức Thi. Qua đây, tôi xin gửi lời cảm ơn sâu sắc đến Thầy cùng sự giúp đỡ nhiệt tình của Thầy trong suốt quá trình tôi thực hiện luận văn. Tôi xin cảm ơn các Thầy, Cô giáo và các Cán bộ trong trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã truyền thụ kiến thức, kinh nghiệm học tập, nghiên cứu khoa học cho tôi trong suốt quá trình học tập tại trường. Tôi cũng xin gửi lời cảm ơn tới trường Đại học Sư phạm Thái Nguyên, Khoa Toán, Tổ Tin học và các đồng nghiệp đã tạo điều kiện cho tôi thực hiện tốt kế hoạch học tập của mình. Cuối cùng, tôi xin bày tỏ lòng biết ơn tới gia đình tôi đã luôn bên cạnh động viên, ủng hộ và tạo điều kiện tốt nhất cho tôi học tập và hoàn thành luận văn này. Học viên thực hiện Nguyễn Thị Thu Hiền -3- MỤC LỤC LỜI CAM ĐOAN...................................................................................................... 1 LỜI CẢM ƠN ........................................................................................................... 2 MỤC LỤC ................................................................................................................. 3 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ......................................... 5 DANH MỤC BẢNG BIỂU ...................................................................................... 6 DANH MỤC HÌNH VẼ, ĐỒ THỊ ........................................................................... 7 LỜI MỞ ĐẦU ........................................................................................................... 9 CHƢƠNG 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ................................... 11 1.1. Quá trình khám phá tri thức trong cơ sở dữ liệu ...................................... 11 1.2. Tính liên ngành của khai phá dữ liệu ....................................................... 13 1.3. Các bài toán khai phá dữ liệu điển hình ................................................... 14 1.4. Các dạng dữ liệu có thể khai phá dữ liệu ................................................. 16 1.5. Hướng tiếp cận và kỹ thuật chính trong khai phá dữ liệu ........................ 16 1.6. Ứng dụng của khai phá dữ liệu ................................................................. 18 1.7. Các thách thức trong KPTT và KPDL ..................................................... 18 CHƢƠNG 2 - PHÂN CỤM DỮ LIỆU .................................................................. 19 2.1. Bài toán phân cụm dữ liệu ........................................................................ 19 2.2. Các giai đoạn của quá trình phân cụm dữ liệu ......................................... 20 2.3. Ứng dụng của phân cụm dữ liệu ............................................................... 21 2.4. Các kiểu dữ liệu và độ đo tương tự .......................................................... 21 2.5. Các kỹ thuật tiếp cận phân cụm dữ liệu ................................................... 25 2.6. Yêu cầu đối với các thuật toán phân cụm dữ liệu .................................... 29 CHƢƠNG 3 - CÁC THUẬT TOÁN PHÂN CỤM DỮ LIỆU ĐIỂN HÌNH ..... 30 3.1. Các thuật toán phân cụm phân hoạch ....................................................... 30 3.1.1. 3.1.2. 3.1.3. 3.1.4. Thuật toán k-means ........................................................................................ 30 Thuật toán PAM ............................................................................................. 33 Thuật toán CLARA ........................................................................................ 35 Thuật toán CLARANS ................................................................................... 37 -4- 3.2. Các thuật toán phân cụm phân cấp ........................................................... 39 3.2.1. Thuật toán BIRCH ......................................................................................... 39 3.2.2. Thuật toán CURE .......................................................................................... 42 3.3. Các thuật toán phân cụm dựa trên mật độ................................................. 44 3.3.1. Thuật toán DBSCAN ..................................................................................... 44 3.3.2. Thuật toán OPTICS ....................................................................................... 48 3.3.3. Thuật toán DENCLUE .................................................................................. 49 3.4. Các thuật toán phân cụm dựa trên lưới ..................................................... 51 3.4.1. Thuật toán STING ......................................................................................... 51 3.4.2. Thuật toán CLIQUE ...................................................................................... 53 3.4.3. Thuật toán WaveCluster ................................................................................ 53 3.5. Phân cụm dựa trên mô hình ...................................................................... 54 3.5.1. Thuật toán EM ............................................................................................... 54 3.6. Các thuật toán phân cụm dữ liệu kiểu hạng mục ...................................... 57 3.6.1. 3.6.2. 3.6.3. 3.6.4. 3.7. Thuật toán k-modes ....................................................................................... 58 Thuật toán ROCK .......................................................................................... 61 Thuật toán STIRR .......................................................................................... 64 Thuật toán CACTUS ..................................................................................... 66 Phân cụm dữ liệu hỗn hợp ........................................................................ 70 3.7.1. Cơ sở toán học ............................................................................................... 70 3.7.2. Thuật toán k-prototypes ................................................................................. 73 CHƢƠNG 4 - PHÂN CỤM DỮ LIỆU MỜ .......................................................... 76 4.1. Giới thiệu .................................................................................................. 76 4.2. Thuật toán FCM ........................................................................................ 77 4.2.1. Hàm mục tiêu ................................................................................................. 77 4.2.2. Thuật toán FCM ............................................................................................. 78 4.3. Thuật toán FCM ...................................................................................... 80 4.3.1. Hàm mục tiêu ................................................................................................. 80 4.3.2. Thuật toán FCM ........................................................................................... 85 4.4. Một số kết quả thử nghiệm ....................................................................... 85 4.4.1. Thí nghiệm dữ liệu có ngoại lai ..................................................................... 85 4.4.2. Phân cụm dữ liệu các nhóm có ngoại lai và xếp chồng dữ liệu ..................... 88 KẾT LUẬN .............................................................................................................. 91 TÀI LIỆU THAM KHẢO ...................................................................................... 92 PHỤ LỤC ................................................................................................................. 94 CÀI ĐẶT THỬ NGHIỆM THUẬT TOÁN K-MEANS ...................................... 94 -5- DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh Cơ sở dữ liệu CSDL Database Công nghệ thông tin CNTT Information Technology Khám phá tri thức KPTT Knowledge Discovery KDD Knowledge Discovery in Database Khai phá dữ liệu KPDL Data mining Phân cụm dữ liệu PCDL Data Clustering -6- DANH MỤC BẢNG BIỂU Bảng 2.1. Bảng giá trị tham số .................................................................................. 22 Bảng 2.2. Các kiểu thuộc tính với các độ đo thích hợp tương ứng........................... 25 Bảng 3.1. Bảng tổng kết các thuộc tính của các thuật toán PCDL kiểu số .............. 55 Bảng 3.2. Bảng tổng kết các thuộc tính của các thuật toán PCDL hạng mục ......... 69 Bảng 4.1. Số lỗi tâm cụm lớn nhất của FCM và FCM theo số phần tử ngoại lai ... 87 Bảng 4.2. Chuẩn Frobenius của các lỗi tâm các cụm ............................................... 88 Bảng 4.3. Cực đại các lỗi tâm cụm với dữ liệu có ngoại lai ..................................... 89 Bảng 4.4. Frobenius của các lỗi tâm cụm cho dữ liệu có ngoại lai .......................... 89 -7- DANH MỤC HÌNH VẼ, ĐỒ THỊ Hình 1.1. Quá trình khám phá tri thức trong CSDL ................................................ 12 Hình 1.2. Tính đa/liên ngành của khai phá dữ liệu .................................................. 13 Hình 1.3. Sơ đồ biểu diễn mô hình học máy: cần học đường nét rời ...................... 17 Hình 2.1. Quá trình phân cụm dữ liệu ..................................................................... 20 Hình 2.2. Các khoảng cách Euclidean và Manhattan giữa hai đối tượng ................ 23 Hình 2.3. Phương pháp xây dựng cây phân cụm phân cấp ..................................... 26 Hình 2.4. Mô tả phân cụm phân hoạch và phân cụm phân cấp ................................ 27 Hình 3.1. Ý tưởng thuật toán k-means ..................................................................... 30 Hình 3.2. Các bước cơ bản của thuật toán k-means ................................................. 31 Hình 3.3. Chi tiết thuật toán k-means ....................................................................... 32 Hình 3.4. Các bước thực hiện thuật toán PAM ........................................................ 35 Hình 3.5. Các bước thực hiện thuật toán CLARA ................................................... 36 Hình 3.6. Thuật toán CLARANS ............................................................................. 38 Hình 3.7. Thuật toán BIRCH sử dụng cây CF ......................................................... 40 Hình 3.8. Các bước cơ bản của thuật toán BIRCH .................................................. 42 Hình 3.9. Một số cụm dữ liệu được khám phá bởi thuật toán CURE ...................... 43 Hình 3.10. Các bước cơ bản của thuật toán CURE .................................................. 43 Hình 3.11. Hình dạng một số cụm được khám phá bởi thuật toán DBSCAN ......... 45 Hình 3.12. Liên thông mật độ và liên kết mật độ trong PCDL dựa trên mật độ ...... 46 Hình 3.13. Thuật toán DBSCAN .............................................................................. 48 Hình 3.14. Thứ tự các cụm được tăng dần trong OPTICS ....................................... 49 Hình 3.15. Biểu diễn hàm ảnh hưởng sóng ngang và Gaussian .............................. 50 Hình 3.16. Mô hình lưới được sử dụng bởi thuật toán STING ............................... 51 -8- Hình 3.17. Các bước thực hiện thuật toán STING................................................... 52 Hình 3.18. Ứng dụng của thuật toán WaveCluster .................................................. 54 Hình 3.19. Các bước thực hiện thuật toán EM ........................................................ 54 Hình 3.20. Mảng hạng mục của tập dữ liệu .............................................................. 60 Hình 3.21. Số các đối tượng lân cận chung của hai đối tượng dữ liệu i, j ............... 62 Hình 3.22. Tổng quan về ROCK .............................................................................. 63 Hình 3.23. Các bước cơ bản của thuật toán ROCK ................................................ 64 Hình 3.24. Trình bày dữ liệu trong thuật toán STIRR ............................................. 65 Hình 3.25. Một ví dụ sử dụng CACTUS .................................................................. 68 Hình 3.26: Ảnh hưởng của  l trong phân cụm ........................................................ 72 Hình 3.27: Thủ tục phân phối ban đầu trong thuật toán k-prototypes ..................... 74 Hình 3.28: Thủ tục phân phối lại(re-allocation) trong k-prototypes ....................... 75 Hình 3.29: Quá trình hội tụ của thuật toán k-prototypes ......................................... 75 Hình 4.1. Thuật toán FCM ........................................................................................ 78 Hình 4.2. Mô phỏng kết quả các cụm được khám phá bởi thuật toán FCM ............. 79 Hình 4.3. Thuật toán FCM ...................................................................................... 85 Hình 4.4. Thực nghiệm phương pháp FCM .............................................................. 86 Hình 4.5. Thực nghiệm phương pháp FCM với  = 2............................................. 86 Hình 4.6. Thực nghiệm FCM,  = 2 với các cụm có dữ liệu xếp chồng và ngoại lai .. 90 Hình 4.7. Thực nghiệm FCM với các cụm có dữ liệu xếp chồng và ngoại lai ......... 90 -9- LỜI MỞ ĐẦU Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông tin và ngành công nghiệp phần cứng đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó, việc tin học hóa một cách ồ ạt và nhanh chóng của các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh vực hoạt động khác đã tạo ra một lượng dữ liệu lưu trữ khổng lồ. Hàng triệu CSDL đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lí..., trong đó có nhiều CSDL cực lớn. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kĩ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích. Từ đó, các kĩ thuật khám phá hay còn gọi là phát hiện tri thức trong CSDL (Knowledge Discovery in Databases) đã trở thành một lĩnh vực thời sự của ngành công nghệ thông tin trên thế giới hiện nay. Khai phá dữ liệu (Data Mining) là một bước trong quá trình khám phá tri thức và được định nghĩa: là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các CSDL, kho dữ liệu… Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn dùng một số thuật ngữ khác có ý nghĩa tương tự như: khai phá tri thức từ CSDL (knowlegde mining from databases), trích lọc dữ liệu (knowlegde extraction), phân tích dữ liệu/mẫu (data/pattern analysis), khảo cổ dữ liệu (data archaeology), nạo vét dữ liệu (data dredging). Với hai mục đí ch chí nh của khai phá 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: phân lớp (Classification), dự đoán (Prediction), tìm luật liên kết (Association Rule) và các kỹ thuật phân cụm (Clustering) cho khai phá dữ liệu. Phân cụm dữ liệu là quá trình nhóm các đối tượng dữ liệu tương đồng với nhau thành các cụm. Một cụm là tập hợp các đối tượng dữ liệu tương đồng với nhau và các đối tượng dữ liệu thuộc các cụm khác nhau không tương đồng với nhau. Phân cụm dữ liệu nhằm mục đí ch chí nh là tì m kiếm và phát hiện các cụm hoặc các mẫu dữ liệu tự nhiên trong cơ sở dữ liệu lớn , theo đó , cho phép người ta đi sâu vào phân tí ch và nghiên cứu ch o từng cụm dữ liệu này nhằm khám phá các thông tin tiềm ẩn, hữu í ch, phục vụ cho việc ra quyết định . Các kỹ thuật chính được áp dụng trong phân cụm dữ liệu thường phần lớn được kế thừa từ lĩ nh vực thống kê , học máy, nhận dạng,… Đến nay , phân cụm dữ liệu đã được ứng dụng rộng rãi cho việc - 10 - giải quyết các vấn đề trong nhiều lĩnh vực khác nhau như tài chính , thông tin đị a lý , sinh học, nhận dạng ảnh,… Từ những lý do trên, chúng tôi lựa chọn vấn đề “Các kỹ thuật phân cụm trong khai phá dữ liệu” làm đề tài nghiên cứu của mình. Luận văn sẽ trình bày một số vấn đề về khám phá tri thức trong CSDL và tập trung nghiên cứu, trình bày về các kỹ thuật phân cụm trong KPDL. Trong luận văn, ngoài phần mở đầu nêu lên các lý do chính lựa chọn đề tài, phần kết luận nhằm tóm tắt các vấn đề đã tìm hiểu được, đồng thời xác định hướng nghiên cứu tiếp theo, nội dung luận văn được trình bày trong 4 chương và phần phụ lục: Chương 1: Trình bày tổng quan về khám phá tri thức và khai phá dữ liệu: các khái niệm liên quan, các giai đoạn trong quá trình khám phá tri thức, các kỹ thuật tiếp cận chính trong khai phá dữ liệu, … Chương 2: Giới thiệu về phân cụm dữ liệu, trong đó đi sâu phân tích chi tiết các vấn đề cơ bản trong PCDL và ý nghĩa của PCDL. Đồng thời, trình bày tóm tắt về các đặc trưng của các phương pháp PCDL như: phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ,… và nêu các kỹ thuật đánh giá kết quả PCDL. Chương 3: Trình bày các phân tích, đánh giá đối với các thuật toán PCDL điển hình và chỉ ra ưu, nhược điểm của chúng. Chương 4: Trình bày về kỹ thuật phân cụm mờ trong PCDL, cụ thể là trình bày hai thuật toán FCM (Fuzzy C-means) và FCM. Nêu lên một số kết quả thực nghiệm cho các thuật toán phân cụm mờ. Phụ lục: Cài đặt chương trình thử nghiệm cho thuật toán k-means. - 11 - CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. Quá trình khám phá tri thức trong cơ sở dữ liệu Cuộc cách mạng của khoa học kỹ thuật đã cho phép số hóa thông tin dễ dàng, nhanh chóng với chi phí lưu trữ thấp. Đồng thời, cùng với sự phát triển, trang bị hiện đại của hệ thống phần mềm, phần cứng máy tính, một số lượng dữ liệu khổng lồ đã được tích lũy, lưu trữ. Mục đích của việc thu thập và lưu trữ các kho dữ liệu khổng lồ như vậy không ngoài mục tiêu khai phá dữ liệu nhằm phát hiện các tri thức mới có ích cho hoạt động của con người. Chính vì vậy, kỹ thuật thống kê và các công cụ quản trị dữ liệu cũ không thể đáp ứng được nhu cầu phân tích đầy đủ dữ liệu rộng lớn được nữa và một khuynh hướng mới đã được ra đời, phát triển, đó là lĩnh vực khám phá tri thức và khai phá dữ liệu. Theo Fayyad, Piatetsky-Shapiro, Smyth, việc nghiên cứu phát triển lĩnh vực khám phá tri thức trong CSDL (Knowledge Discovery in Databases: KDD) nhằm giải quyết tình trạng “ngập tràn thông tin mà vẫn thiếu thốn tri thức”. [22] Khám phá tri thức trong cơ sở dữ liệu là lĩnh vực đã, đang và sẽ được quan tâm triển khai nghiên cứu, phát triển một cách nhanh chóng và rộng rãi. Đã có rất nhiều các thuật ngữ khác nhau mà được coi là cùng mang nghĩa của KDD như knowledge extraction (chiết lọc tri thức), information discovery (phát hiện thông tin), information harvesting (thu hoạch thông tin), data archaeology (khai quật dữ liệu) và data pattern processing (xử lý mẫu dữ liệu). Năm 1989, Fayyad, Smyth và Piatestsky-Shapiro đã định nghĩa một cách đầy đủ về khái niệm Khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database - KDD) như sau: [12]-[22] Khám phá tri thức trong cơ sở dữ liệu (đôi khi còn được gọi là khai phá dữ liệu) là một quá trình không tầm thường nhận ra những mẫu có giá trị, mới, hữu ích tiềm năng và hiểu được trong dữ liệu. Quá trình khám phá tri thức trong CSDL được chia thành các bước như trong hình 1.1 dưới đây: - 12 - Đánh giá và biểu diễn tri thức Khai phá dữ liệu Biến đổi dữ liệu Trích chọn dữ liệu Tri thức Tiền xử lý dữ liệu Mẫu Dữ liệu chuyển dạng Dữ liệu đã tiền xử lý Dữ liệu đích Dữ liệu Hình 1.1. Quá trình khám phá tri thức trong CSDL - Trích lọc dữ liệu (Data Selection) Là bước trích chọn những tập dữ liệu cần được khai thác từ các tập dữ liệu lớn (databases, datawarehouses) ban đầu theo một số tiêu chí nhất định. - Tiền xử lý dữ liệu (Data preprocessing) Giai đoạn này hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu. Tiền xử lý dữ liệu là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,…), rút gọn dữ liệu (sử dụng các phương pháp nén dữ liệu, histograms, entropy,…), rời rạc hóa dữ liệu (dựa vào histograms, dựa vào phân khoảng,…). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hóa. Có thể nói, đây là một bước rất quan trọng vì dữ liệu này nếu không được “làm sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm trọng. - Biến đổi dữ liệu (Data transformation) Là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho mục đích khai thác ở bước sau. - Khai phá dữ liệu (Data mining) Đây là bước quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật phân tích (phần lớn là các kỹ thuật của học máy) nhằm khai thác, trích chọn được các mẫu thông tin, các mối liên hệ đặc biệt trong dữ liệu. - 13 - - Đánh giá và biểu diễn tri thức (Knowledge representation & evaluation) Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã được khai thác ở bước trên theo dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,… Đồng thời, bước này cũng đánh giá những tri thức khám phá được theo các tiêu chí nhất định. Trong quá trình phát hiện tri thức trong các CSDL đưọc mô tả ở trên, chúng ta nhận thấy có sự tham gia của các kho dữ liệu. Theo W.H. Inmon [12] "kho dữ liệu là tập hợp các dữ liệu định hướng theo chủ đề, được tích hợp từ, có tính phiên bản theo thời gian và kiên định được dùng để hỗ trợ việc tạo quyết định cho người quản trị". 1.2. Tính liên ngành của khai phá dữ liệu Khai phá dữ liệu là một khái niệm ra đời vào cuối những năm 1980. Nó được xem là giai đoạn quan trọng nhất trong tiến trình khai phá tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh. KPDL nhận được sự quan tâm đặc biệt của các nhà nghiên cứu trong nhiều lĩnh vực học máy, thu nhận mẫu, CSDL, thống kê, trí tuệ nhân tạo, thu nhận tri thức đối với hệ chuyên gia (Hình 1.2). Hệ thống KDD lôi cuốn các phương pháp, thuật toán và kỹ thuật từ các lĩnh vực rời rạc nhau này. Mục tiêu thống nhất là trích lọc tri thức từ dữ liệu trong ngữ cảnh các CSDL lớn. [6]-[12]-[15] Hình 1.2. Tính đa/liên ngành của khai phá dữ liệu Đối với các lĩnh vực học máy và thu nhận mẫu, sự đan xen với KDD trải theo các nghiên cứu về lý thuyết và thuật toán đối với các hệ thống trích lọc mẫu và mô hình dữ liệu (chủ yếu đối với các phương pháp khai phá dữ liệu). Trọng tâm của KDD đối với việc mở rộng các lý thuyết và thuật toán này hướng tới bài toán tìm ra - 14 - các mẫu đặc biệt (những mẫu mà trong một số ngữ cảnh còn được gọi là tri thức hữu dụng hoặc hấp dẫn) trong các tập hợp dữ liệu lớn của thế giới thực. Phát hiện máy với mục tiêu là phát hiện các luật kinh nghiệm từ quan sát và thử nghiệm và mô hình nhân quả phát hiện các kết luận của mô hình nhân quả từ dữ liệu là những lĩnh vực nghiên cứu có mối liên hệ với nhau. Một lĩnh vực nghiên cứu và triển khai có liên quan (trong nhiều trường hợp được coi là một bộ phận của lĩnh vực khai phá dữ liệu và phát hiện tri thức trong CSDL) là lĩnh vực kho dữ liệu (data warehouse) chỉ dẫn tới các khuynh hướng hệ thống thông tin quản lý (MIS: Managment Information Systems) phổ biến hiện tại đối với việc thu thập và làm sạch dữ liệu giao dịch và tạo cho chúng sự biến động khi tìm kiếm trực tuyến. Một tiệm cận phổ biến đối với việc phân tích kho dữ liệu gọi là OLAP (On-Line Analytical Processing), qua một tập các nguyên lý được Codd đề xuất vào năm 1993 [19]. 1.3. Các bài toán khai phá dữ liệu điển hình Bước khai phá dữ liệu trong quá trình KDD thường áp dụng một phương pháp khai phá dữ liệu cụ thể, liên quan đến các khái niệm mẫu và mô hình. Mẫu là một biểu thức trong một ngôn ngữ mô tả L được chọn. Mô hình được coi là một biểu thức tổng quát trong ngôn ngữ mô tả L nói trên mà tính tổng quát được thể hiện thông qua các tham số (được gọi là tham số mô hình), trong trường hợp đó, mẫu là một thể hiện của mô hình. Nhiệm vụ của bài toán khai phá dữ liệu là từ dữ liệu (tập các sự kiện) quan sát đã có thì hoặc cần phải xác định mô hình phù hợp với dữ liệu quan sát, hoặc cần tìm ra các mẫu từ dữ liệu đó. Ở mức cao - tổng quát, hai mục tiêu chủ yếu của khai phá dữ liệu là dự đoán và mô tả. Dự đoán dùng một số biến hoặc trường trong CSDL để dự đoán hoặc về giá trị chưa biết hoặc về giá trị sẽ có trong tương lai của các biến. Mô tả hướng tới việc tìm ra các mẫu mô tả dữ liệu. Dự đoán và mô tả có tầm quan trọng khác nhau đối với các thuật toán khai phá dữ liệu riêng. Ở mức chi tiết - cụ thể, dự đoán và mô tả được thể hiện thông qua các bài toán cụ thể như mô tả khái niệm, quan hệ kết hợp, phân cụm, phân lớp, hồi quy, mô hình phụ thuộc, phát hiện biến đổi và độ lệch và một số bài toán cụ thể khác.  Mô tả khái niệm Bài toán mô tả khái niệm là tìm các đặc trưng và tính chất của các khái niệm. Điển hình nhất là các bài toán như tổng quát hóa, tóm tắt, các đặc trưng dữ liệu ràng buộc,…Bài toán tóm tắt là một bài toán điển hình, áp dụng các phương pháp tìm - 15 - một mô tả cô đọng đối với một tập con dữ liệu. Một ví dụ điển hình về tóm tắt là kỳ vọng và độ lệch chuẩn. Kỹ thuật tóm tắt thường được áp dụng trong phân tích dữ liệu tham dò có tương quan và tự động hóa sinh thông báo.  Quan hệ kết hợp Phát hiện mối quan hệ kết hợp là một bài toán quan trọng trong khai phá dữ liệu, trong đó khai phá luật kết hợp là một đại diện điển hình.  Phân lớp Phân lớp (Classification) thực hiện việc xây dựng các mô hình (hàm) dự báo nhằm mô tả hoặc phát hiện các lớp hoặc khái niệm cho các dự báo tiếp theo. Một số phương pháp điển hình là cây quyết định, luật phân lớp, mạng nơron. Nội dung của phân lớp chính là học một hàm ánh xạ các dữ liệu vào một trong một số lớp đã biết. Ví dụ, phân lớp khuynh hướng trong thị trường tài chính, phát hiện tự động hóa các đối tượng đáng quan tâm trong CSDL ảnh lớn…  Phân cụm Phân cụm (Clustering) thực hiện việc nhóm dữ liệu thành các lớp mới để có thể phát hiện các mẫu phân bố. Các cụm có thể rời nhau và toàn phần (tạo nên phân hoạch) hoặc có thể chồng chéo lên nhau. Ví dụ như phát hiện các nhóm người tiêu dùng trong CSDL tiếp thị,... Định hướng thường là cực đại tính tương đồng trong mỗi cụm và cực tiểu tính tương đồng giữa các phần tử thuộc các cụm khác nhau. Có một số ứng dụng yêu cầu cần giải quyết bài toán phân đoạn (segmentation). Về bản chất, phân đoạn là tổ hợp của phân cụm và phân lớp, trong đó phân cụm được tiến hành trước và sau đó là phân lớp.  Hồi quy Hồi quy là học một hàm ánh xạ dữ liệu nhằm xác định giá trị thực của một biến. Tình huống ứng dụng hồi quy rất đa dạng, chẳng hạn như dự báo nhu cầu người tiêu dùng đối với một sản phẩm mới, dự đoán số lượng sinh vật phát quang trong khu rừng nhờ đo vi sóng các sensor từ xa, hoặc ước lượng xác suất người bệnh có thể chết theo kết quả test triệu chứng,…  Mô hình phụ thuộc Bài toán xây dựng mô hình phụ thuộc hướng tới việc tìm ra một mô hình mô tả sự phụ thuộc có ý nghĩa giữa các biến. Mô hình phụ thuộc gồm hai mức: mức cấu trúc của mô hình mô tả (thường dưới dạng đồ thị) và mức định lượng. Trong đó, ở mức cấu trúc của mô hình các biến là phụ thuộc bộ phận vào các biến khác, còn ở mức định lượng của mô hình mô tả sức mạnh của tính phụ thuộc khi sử dụng đo theo số. - 16 -  Phát hiện biến đổi và độ lệch Tập trung vào việc phát hiện hầu hết sự thay đổi có ý nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn.  Ngoài ra có thể kể tới phân tích định hướng mẫu và thống kế khác. 1.4. Các dạng dữ liệu có thể khai phá dữ liệu Nguồn dữ liệu được sử dụng để tiến hành khai phá dữ liệu nhằm phát hiện tri thức rất phong phú.  Cơ sở dữ liệu quan hệ (relational databases) : là các dữ liệu được tổ chức theo mô hình dữ liệu quan hệ.  Cơ sở dữ liệu đa chiều (multidimention structures, data warehouses, data mart): là các kho dữ liệu được tập hợp và chọn lọc từ nhiều nguồn dữ liệu khác nhau. Dạng dữ liệu này chủ yếu phục vụ cho quá trình phân tích cũng như khai phá tri thức và hỗ trợ quá trình ra quyết định.  Cơ sở dữ liệu giao tác (transactonal databases)  Cơ sở dữ liệu quan hệ - hướng đối tượng (object relational databases): là dạng lai giữa hai mô hình quan hệ và hướng đối tượng.  Dữ liệu không gian và thời gian (spatial, temporal, and time-series data)  Cơ sở dữ liệu đa phương tiện (multimedia databases): là dạng dữ liệu âm thanh, hình ảnh, text, www,… 1.5. Hƣớng tiếp cận và kỹ thuật chính trong khai phá dữ liệu Theo quan điểm học máy (Machine Learning) thì các kỹ thuật trong khai phá dữ liệu bao gồm:  Học có giám sát (Supervised learning): là quá trình gán nhãn lớp cho các phần tử trong CSDL dựa trên một tập các ví dụ huấn luyện và các thông tin về nhãn lớp đã biết.  Học không có giám sát (Unsupervised learning): là quá trình phân chia một tập dữ liệu thành các lớp hay cụm dữ liệu tương tự nhau mà chưa biết trước các thông tin về lớp hay tập ví dụ huấn luyện.  Học bán giám sát (Semi - Supervised learning): là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập nhỏ các ví dụ huấn luyện và một số các thông tin về một số nhãn lớp đã biết trước. Một số hƣớng tiếp cận chính của khai phá dữ liệu đƣợc phân chia theo chức năng hay lớp các bài toán khác nhau, bao gồm các kỹ thuật: - 17 -  Phân lớp và dự đoán (classification & prediction): xếp đối tượng vào một trong các lớp đã biết trước. Ví dụ: phân lớp học sinh dựa trên sổ điểm,… Phân lớp là một lĩnh vực rất quan trọng trong khai phá dữ liệu. Phân lớp còn được gọi là học có giám sát. Hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây quyết định (decision tree), mạng nơron nhân tạo (neural network),…  Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng tương đối đơn giản. Ví dụ: “70% sinh viên học chuyên ngành hệ thống thông tin thì có tới 90% trong số đó đăng ký học Data mining”. Luật kết hợp được ứng dụng trong nhiều lĩnh vực kinh doanh, y học, tài chính, thị trường chứng khoán,…  Khai thác mẫu tuần tự (sequential/temporal patterns): tương tự như khai thác luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X  Y phản ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện kế tiếp biến cố Y. Hướng tiếp cận này có tính dự báo.  Phân cụm (clustering/segmentation): Sắp xếp các đối tượng theo từng cụm (số lượng và tên của cụm chưa được biết trước). Các đối tượng được gom cụm sao cho mức độ tương tự giữa các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các cụm khác nhau là nhỏ nhất. Phân cụm còn được gọi là học không có giám sát (unsupervised learning). Mô hình học máy (có giám sát và không giám sát) được trình bày như hình 1.4 dưới đây: Hình 1.3. Sơ đồ biểu diễn mô hình học máy: cần học đƣờng nét rời Trong đó, học máy không giám sát (phân cụm) không có giá trị mục tiêu cho ví dụ học (không có hai đường liền nét hướng tới giá trị mục tiêu) - 18 - 1.6. Ứng dụng của khai phá dữ liệu KPDL đượ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. Tuỳ theo bản chất của từng lĩnh vực, việc vận dụng KPDL có những cách tiếp cận khác nhau. Ứng dụng của KPDL có thể được chia thành hai lớp chính bao gồm ứng dụng phân tích dữ liệu - hỗ trợ quyết định và một số lĩnh vực ứng dụng khác. Các ứng dụng trong phân tích dữ liệu và hỗ trợ quyết định bao gồm các ứng dụng trong phân tích và quản lý thị trường, phân tích và quản lý rủi ro, khám phá ngoại lai và các mẫu không hữu ích. Dữ liệu trong các ứng dụng này là khá phong phú từ các giao dịch thẻ tín dụng, nghiên cứu đời sống công đồng... Các kỹ thuật KPDL đã được áp dụng thành công trong việc dự đoá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 các khách hàng tài năng. Phân tích kiểu khách hàng theo từng loại sản phẩm, phân tích nhu cầu khách hàng, định danh loại sản phẩm thích hợp cho từng lớp khác hàng để đưa ra chiến lược kinh doanh đối với nhóm khách hàng mới. Ngoài ra, ứng dụng trong lập kế hoạch và phân tích tình hình tài chính, đánh giá lưu lượng tiền tệ, dự báo giá của các loại cổ phiếu trong thị trường chứng khoán, dữ liệu thẻ tín dụng, phát hiện gian lận,… trong lĩnh vực tài chính – ngân hàng cũng được phát triển. Các lĩnh vực ứng dụng điển hình khác được kể đến là khai phá Text, khai phá Web, khai phá dữ liệu dòng, khai phá dữ liệu sinh học (tìm kiếm, so sánh các hệ gen và thông tin di truyền, mối liên hệ gen và một số bệnh di truyền),… 1.7. Các thách thức trong KPTT và KPDL - Thách thức đầu tiên trong KPTT và KPDL phải kể đến đó là trong tập dữ liệu thường có chứa các dữ liệu “nhiễu” (noise) do quá trình thu thập thiếu chính xác, không đầy đủ; và chứa phần tử ngoại lai (outlier) – những đối tượng dữ liệu “khác thường” (không tuân theo hành vi hoặc mô hình dữ liệu,…). - Vấn đề thứ hai, kích thước, số chiều của các tập dữ liệu cần xử lý trong KPTT và KPDL thường rất lớn, do đó thời gian xử lý thường rất dài. - Quan hệ giữa các trường phức tạp. - Giao tiếp với người sử dụng và kết hợp với các tri thức đã có. - Tích hợp với các hệ thống khác. - Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp cũng là những thách thức cần quan tâm trong KPTT và KPDL.