Một số thuật toán phân cụm dữ liệu

  • Số trang: 103 |
  • Loại file: PDF |
  • Lượt xem: 36 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

ĐẠI HỌC CÔNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI TRẦN THỊ KIM THUYẾN MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU LUẬN VĂN THS CÔNG NGHỆ THÔNG TIN Người hướng dẫn PGSTSKH : BÙI CÔNG CƯỜNG Hà nội: 2007 1 MỤC LỤC MỤC LỤC ..................................................................................................... 1 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .................................. 3 DANH MỤC HÌNH VẼ, ĐỒ THỊ .................................................................. 4 MỞ ĐẦU ....................................................................................................... 6 CHƢƠNG 1. TỔNG QUAN .......................................................................... 9 1.1 QUÁ TRÌNH KHÁM PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU ............ 9 1.2 KHAI PHÁ DỮ LIỆU ................................................................................ 11 1.2.1 KHÁI NIỆM VỀ KHAI PHÁ DỮ LIỆU ...................................................... 11 1.2.2 CÁC KỸ THUẬT KHAI PHÁ DỮ LIỆU ..................................................... 12 1.3 PHÂN CỤM DỮ LIỆU .............................................................................. 14 1.3.1 1.3.2 1.3.3 1.3.4 1.3.5 1.3.6 KHÁI NIỆM VỀ PHÂN CỤM DỮ LIỆU ..................................................... 14 MỘT SỐ VẤN ĐỀ TRONG PHÂN CỤM DỮ LIỆU ................................... 16 MỤC TIÊU CỦA PHÂN CỤM .................................................................... 17 CÁC BƢỚC CƠ BẢN TRONG PHÂN CỤM............................................... 18 YÊU CẦU CỦA PHÂN CỤM ...................................................................... 19 ỨNG DỤNG CỦA PHÂN CỤM .................................................................. 20 CHƢƠNG 2. CÁC KỸ THUẬT PHÂN CỤM ............................................. 22 2.1 KIỂU DỮ LIỆU .......................................................................................... 22 2.1.1 PHÂN LOẠI KIỂU DỮ LIỆU DỰA TRÊN KÍCH THƢỚC MIỀN .............. 22 2.1.2 PHÂN LOẠI KIỂU DỮ LIỆU DỰA TRÊN HỆ ĐO..................................... 23 2.2 PHÉP ĐO ĐỘ TƢƠNG TỰ VÀ PHÉP ĐO KHOẢNG CÁCH .................. 24 2.2.1 KHÁI NIỆM TƢƠNG TỰ VÀ PHI TƢƠNG TỰ ......................................... 24 2.2.2. ĐỘ ĐO TƢƠNG TỰ VÀ KHÔNG TƢƠNG TỰ .......................................... 25 2.2.3 PHÉP ĐO KHOẢNG CÁCH ........................................................................ 26 2.3 PHƢƠNG PHÁP PHÂN CỤM DỮ LIỆU ................................................... 33 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5 2.3.6 PHƢƠNG PHÁP PHÂN CỤM PHÂN HOẠCH ........................................... 33 PHƢƠNG PHÁP PHÂN CỤM PHÂN CẤP ................................................. 34 PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN MẬT ĐỘ ................................ 36 PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN LƢỚI ...................................... 36 PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN MÔ HÌNH............................... 37 PHƢƠNG PHÁP PHÂN CỤM CÓ DỮ LIỆU RÀNG BUỘC....................... 38 CHƢƠNG 3. MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU ................. 40 3.1 THUẬT TOÁN PHÂN CỤM PHÂN HOẠCH ........................................... 41 3.1.1 3.1.2 3.1.3 3.1.4 THUẬT TOÁN K-MEANS .......................................................................... 41 THUẬT TOÁN PAM ................................................................................... 46 THUẬT TOÁN CLARA .............................................................................. 51 THUẬT TOÁN CLARANS ......................................................................... 53 3.2 CÁC THUẬT TOÁN PHÂN CỤM PHÂN CẤP ......................................... 54 2 3.2.1 THUẬT TOÁN HERACHICAL ................................................................... 54 3.2.2 THUẬT TOÁN BIRCH ................................................................................ 62 3.2.3 THUẬT TOÁN CURE ................................................................................. 66 3.3 CÁC THUẬT TOÁN PHÂN CỤM DỰA TRÊN MẬT ĐỘ ........................ 69 3.3.1 THUẬT TOÁN DBSCAN ............................................................................ 70 3.3.2 THUẬT TOÁN OPTICS ............................................................................. 76 3.4 CÁC THUẬT TOÁN PHÂN CỤM DỰA TRÊN LƢỚI ............................. 77 3.4.1 THUẬT TOÁN STING ................................................................................ 78 3.4.2 THUẬT TOÁN CLIQUE ............................................................................. 81 CHƢƠNG 4. PHÂN CỤM DỮ LIỆU MỜ ............................................. 83 4.1 VẤN ĐỀ PHÂN CỤM MỜ ......................................................................... 83 4.2 KHÁI NIỆM VỀ TẬP MỜ VÀ PHÂN CỤM MỜ ...................................... 84 4.2.1 KHÁI NIỆM VỀ TẬP MỜ VÀ BIỂU DIỄN TẬP MỜ ................................. 84 4.2.2 KHÁI NIỆM PHÂN CỤM MỜ .................................................................... 85 4.3 THUẬT TOÁN PHÂN CỤM MỜ K-MEANS ........................................... 86 4.3.1 MÔ TẢ THUÂT TOÁN ............................................................................... 88 4.3.2 ĐỘ PHỨC TẠP CỦA THUẬT TOÁN ......................................................... 89 KẾT LUẬN .................................................................................................. 91 TÀI LIỆU THAM KHẢO ............................................................................ 93 PHỤ LỤC .................................................................................................... 95 3 DANH MỤC CÁC CHỮ VIẾT TẮT CỤM TỪ CHỮ VIẾT TẮT Balanced Iterative Reducing and Clustering BIRCH using Hierarchies Clustering LARge Applications CLARA A Clustering Algorithm Based On CLARANS Randomized Search CLustering In QUEst CLIQUE Clustering Using REpresentatives CURE Fuzzy C Means FCM Ordering Points To Indentify the OPTICS Clustering Structure Partition Around Medoids PAM STatistical INformation Grid STING 4 DANH MỤC HÌNH VẼ, ĐỒ THỊ Hình 1.1: Quá trình khám phá tri thức Hình 1.2. Các kỹ thuật khai phá dữ liệu Hình 1.3. Quy trình phân cụm Hình 1.4. Các phần tử ngoại lai trong dữ liệu Hình 2.1. Mối quan hệ giữa tỷ lệ phép đo và sự phân cụm Hình 2.2. Ví dụ về các phép đo khoảng cách Hình 2.3. Một số loại khoảng cách giữa hai cụm Hình 2.4. Các chiến lƣợc phân cụm phân cấp Hình 2.5. Cấu trúc dữ liệu lƣới Hình 3.1. Xác định ranh giới của các cụm khởi tạo Hình 3.2. Tính toán trọng tâm của các cụm mới Hình 3.3. Ví dụ của thuật toán K-MEANS với k=2 Hình 3.4. Một số dạng cụm đƣợc khám phá bởi k-means Hình 3.5. Khởi tạo các đối tƣợng medoid Hình 3.6. Trƣờng hợp Cjmp không âm Hình 3.7. Trƣờng hợp Cjmp có thể âm hoặc dƣơng Hình 3.8. Trƣờng hợp Cjmp=0 Hình 3.9. Trƣờng hợp Cjmp luôn âm Hình 3.10. Thuật toán PAM với k=2 5 Hình 3.11. Cây CF đƣợc dùng trong thuật toán BIRCH Hình 3.12. Ý tƣởng của thuật toán phân cụm phân cấp Hình 3.13. Các điểm dữ liệu của một cụm trong CURE Hình 3.14. Phân hoạch và phân cụm dữ liệu Hình 3.15. Co cụm các điểm biểu diễn Hình 3.16. Lân cận với ngƣỡng  của điểm P Hình 3.17. Mật độ liên lạc Hình 3.18. Mật độ liên thông Hình 3.19. Cụm và nhiễu Hình 3.20. Một cụm đƣợc khám phá bởi DBSCAN Hình 3.21. Thứ tự phân cụm của các đối tƣợng OPTICS Hình 3.22. Cấu trúc lƣới phân cụm Hình 3.23. Các mức ô lƣới khác nhau trong quá trình truy vấn Hình 3.24. Quá trình nhận dạng các ô của CLIQUE Hình 5.1. Chƣơng trình mô phỏng thuật toán K-means 6 MỞ ĐẦU Từ vài thập niên trở lại đây, những tác động mạnh mẽ của các tiến bộ trong công nghệ phần cứng và truyền thông, các hệ thống dữ liệu phục vụ cho các lĩnh vực kinh tế-xã hội đã phát triển bùng nổ, lƣợng dữ liệu đƣợc tạo ra ngày càng lớn. Sự phong phú về dữ liệu, thông tin cùng với khả năng kịp thời khai thác của chúng đã mang đến những năng suất và chất lƣợng mới cho công tác quản lý, hoạt động kinh doanh,... Các yêu cầu về thông tin trong các lĩnh vực hoạt động, đặc biệt trong lĩnh vực làm ra quyết định ngày càng đòi hỏi cao, cần có những hiểu biết, những tri thức để hỗ trợ cho việc ra quyết định. Đến những năm 90 nhu cầu khám phá tri thức thực sự bùng nổ, theo đó hàng loạt các lĩnh vực nghiên cứu về tổ chức các kho dữ liệu và kho thông tin, các hệ trợ giúp quyết định, các thuật toán nhận dạng mẫu, phân cụm.... ra đời. Phân cụm dữ liệu là quá trình tìm kiếm và phát hiện ra các cụm hoặc các mẫu dữ liệu tự nhiên trong cơ sở dữ liệu lớn. Các kỹ thuật chính đƣợc áp dụng trong phân cụm dữ liệu phần lớn đƣợc kế thừa từ lĩnh vực thống kê, học máy, nhận dạng, lƣợng hoá,... Có nhiều ứng dụng phân cụm dữ liệu cho việc giải quyết các vấn đề trong các lĩnh vực nhƣ tài chính, ngân hàng, y học, xã hội học, nhận dạng ảnh, .... Nhờ sự phát triển mạnh mẽ của ngành công nghệ thông tin đã làm cho khả năng thu thập và lƣu trữ dữ liệu của các hệ thống thông tin tăng một cách vũ bão. Kho dữ liệu, nguồn tri thức của nhân loại cũng trở nên vô tận và làm thế nào để khai thác đƣợc nguồn tri thức đó đang là một vấn đề nóng bỏng của nền công nghệ thông tin thế giới. Vấn đề Khám phá tri thức trong Cơ sở dữ liệu (Knowledge Discovery in Databases) đang đƣợc rất nhiều các nhà khoa học quan tâm nghiên cứu. Khai phá dữ liệu là một bƣớc quan trọng trong quá trình khám phá tri thức. 7 Khai phá dữ liệu có rất nhiều hƣớng tiếp cận, các kỹ thuật khai phá dữ liệu liên quan đến rất nhiều ngành khoa học khác nhƣ: Hệ cơ sở dữ liệu, thống kê, học máy, trực quan hoá,…Tuỳ vào từng cách tiếp cận cụ thể đƣợc sử dụng, khai phá dữ liệu còn áp dụng một số kỹ thuật khác nhƣ mạng nơron, lý thuyết tập mờ, biểu diễn tri thức,… Phân cụm dữ liệu là một trong những kỹ thuật khai phá dữ liệu phổ biến nhất, nằm trong nhóm kỹ thuật khai phá dữ liệu mô tả, có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có. Luận văn này tập trung trình bày một số vấn đề của phân cụm dữ liệu, luận văn gồm bốn chƣơng, phần kết luận và phần phụ lục là chƣơng trình mô phỏng một thuật toán phân cụm dữ liệu. Chƣơng 1: Tổng quan về phân cụm dữ liệu, bao gồm một số vấn đề về khám phá tri thức, khai phá dữ liệu và tập trung trình bày một số khái niệm trong phân cụm dữ liệu và các lĩnh vực ứng dụng liên quan. Chƣơng 2: Các kỹ thuật phân cụm, trong đó có đề cập đến một số kiến thức cơ sở là nền tảng cho phân cụm dữ liệu nhƣ các kiểu dữ liệu, các phép đo khoảng cách giữa các đối tƣợng dữ liệu, các kỹ thuật tiếp cận trong phân cụm dữ liệu. Chƣơng 3: Các thuật toán phân cụm dữ liệu, tập trung trình bày một số thuật toán tiêu biểu của phân cụm dữ liệu phân chia theo các kỹ thuật tiếp cận nhƣ các thuật toán phân cụm phân hoạch, các thuật toán phân cụm phân cấp, Chƣơng 4: Trình bày về phân cụm mờ và kỹ thuật mờ trong phân cụm dữ liệu, cụ thể là thuật toán FCM. Kết luận: Tổng kết lại những nội dung đã trình bày và những kết quả đã đạt đƣợc trong luận văn. Qua đó cũng đề cập đến những vấn đề chƣa giải quyết đƣợc và đề xuất hƣớng nghiên cứu tiếp theo. 8 Phụ lục: Trình bày chƣơng trình mô phỏng một thuật toán phân cụm dữ liệu K-means, một trong những thuật toán phân cụm dữ liệu phổ biến nhất. 9 CHƢƠNG 1. TỔNG QUAN 1.1 QUÁ TRÌNH KHÁM PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU Cùng với sự phát triển vƣợt bậc của các công nghệ điện tử và truyền thông đã làm cho khả năng thu thập, lƣu trữ và xử lý dữ liệu cho các hệ thống tin học không ngừng nâng cao. Bên cạnh đó, việc tin học hoá nhiều lĩnh vực của cuộc sống đã tạo ra cho chúng ta một kho dữ liệu khổng lồ. Quá trình khám phá tri thức trong Cơ sở dữ liệu (Knowledge Discovery in Databases) đang là một vấn đề thời sự của nền công nghệ thông tin thế giới hiện nay. Nó đƣợc ứng dụng vào nhiều lớp bài toán thực tế khác nhau và thu đƣợc nhiều thành quả to lớn. Khám phá tri thức trong cơ sở dữ liệu là một quá trình nhận biết đúng đắn, mới, hữu ích và cuối cùng là có thể hiểu đƣợc mẫu hoặc mô hình trong dữ liệu. Quá trình khám phá tri thức có thể bao gồm các bƣớc nhƣ hình 1.1 [7] Tri thức Dữ liệu thô Trích chọn dữ liệu Đánh giá và giải thích Khai phá dữ liệu Tiền xử lý dữ liệu Biến đổi dữ liệu Hình 1.1: Quá trình khám phá tri thức - Trích chọn dữ liệu: Là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá từ tập dữ liệu lớn ban đầu theo một tiêu chí nhất định. Đây là bƣớc quan trọng để rút ra những tri thức hữu ích và chọn phƣơng pháp khai phá dữ liệu phù hợp với mục đích ứng dụng và bản chất dữ liệu. - Tiền xử lý dữ liệu: Là bƣớc làm sạch dữ liệu: lựa chọn dữ liệu nguồn, loại bỏ các dữ liệu nhiễu hoặc ngoại lai, xử lý các giá trị không đầy đủ, biến 10 đổi và rút gọn dữ liệu, sửa các lỗi mang tính hệ thống, tập hợp các thông tin cần thiết để mô hình hoặc tính toán nhiễu, quyết định các chiến lƣợc xử lý các trƣờng dữ liệu bị lỗi. 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 hoá. - Biến đổi dữ liệu: Đây là bƣớc chuẩn hoá 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 kỹ thuật khai phá ở bƣớc sau. - Khai phá dữ liệu: Áp dụng các kỹ thuật phân tích nhằm để khai thác dữ liệu, trích chọn các mẫu ẩn hoặc mô hình trong dữ liệu. Một mô hình có thể xem nhƣ là một biểu diễn tổng thể của cấu trúc nhằm tóm lƣợc các thành phần mang tính hệ thống có trong dữ liệu hoặc mô tả dữ liệu phát sinh. Ngƣợc lại, một mẫu là một cấu trúc cục bộ có khi chỉ liên quan tới một nhóm các biến và một số trƣờng hợp. - Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu đã đƣợc khám phá ở bƣớc trên đƣợc chuyển dạng và đƣợc biểu diễn ở một dạng gần gũi với ngƣời sử dụng, đồng thời đánh giá những tri thức khám phá đƣợc theo những tiêu chí nhất định. Đặc biệt là làm sáng tỏ các mô tả và dự đoán, hai mục tiêu chính của các hệ thống khám phá trong thực tế. Kinh nghiệm cho thấy rằng các mẫu hoặc mô hình phát hiện đƣợc từ các dữ liệu không phải lúc nào cũng đáng quan tâm và có thể trực tiếp sử dụng đƣợc ngay, quy trình khám phá tri thức đƣợc lặp đi lặp lại có điều chỉnh theo các tri thức phát hiện đƣợc. Để đánh giá đƣợc các luật áp dụng trong quy trình khám phá tri thức, dữ liệu thƣờng đƣợc chia thành hai tập, huấn luyện trên tập thứ nhất và kiểm chứng trên tập thứ hai. Có thể lặp lại quy trình này với một số lần với các phần chia khác nhau, sau đó lấy trung bình các kết quả để ƣớc lƣợng các luật thi hành. 11 - Ứng dụng tri thức được khám phá: Củng cố các tri thức đã khám phá, kết hợp các tri thức thành một hệ thống máy tính. Giải quyết các xung đột tiềm năng trong tri thức khai thác đƣợc. Đƣa kết quả vào thực tiễn là mục đích cuối cùng của khám phá tri thức. Khai phá dữ liệu là một giai đoạn quan trọng nhất của quá trình khám phá tri thức. Bản chất của quá trình khám phá tri thức là rút ra đƣợc tri thức phù hợp từ cơ sở dữ liệu. 1.2 KHAI PHÁ DỮ LIỆU 1.2.1 KHÁI NIỆM VỀ KHAI PHÁ DỮ LIỆU Khai phá dữ liệu (Data mining) là quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong các cơ sở dữ liệu lớn, các kho dữ liệu…Các kết quả khoa học cùng những thành công trong khám phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực mang lại nhiều lợi ích và có triển vọng, có ƣu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Khai phá dữ liệu là một lĩnh vực có liên quan đến rất nhiều ngành khoa học khác nhƣ: Hệ cơ sở dữ liệu, thống kê, học máy, trực quan hoá…Tuỳ vào cách tiếp cận đƣợc sử dụng thì khai phá dữ liệu còn áp dụng một số kỹ thuật khác nhƣ mạng nơron, lý thuyết tập thô hoặc tập mờ, biểu diễn tri thức…So với các phƣơng pháp này, khai phá dữ liệu có một số ƣu thế rõ rệt. So với phƣơng pháp học máy, khai phá dữ liệu có thể sử dụng dữ liệu có nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục. Trong khi đó, phƣơng pháp học máy đòi hỏi tập dữ liệu phải đầy đủ, ít biến động và không quá lớn. Phƣơng pháp hệ chuyên gia, các ví dụ của chuyên gia thƣờng phải đòi hỏi chất lƣợng cao hơn nhiều so với dữ liệu trong cơ sở dữ liệu. 12 Phƣơng pháp thống kê là một trong những nền tảng lý thuyết của khai phá dữ liệu nhƣng khai phá dữ liệu đã khắc phục đƣợc một số tồn tại của phƣơng pháp thống kê nhƣ: Các phƣơng pháp thống kê chuẩn không phù hợp với các kiểu dữ liệu có cấu trúc trong rất nhiều kiểu cơ sở dữ liệu, nó hoạt động hoàn toàn theo dữ liệu, nó không sử dụng tri thức sẵn có của lĩnh vực, kết quả phân tích của thống kê rất nhiều và khó có thể làm rõ đƣợc, phƣơng pháp thống kê cần có sự hƣớng dẫn của ngƣời dùng để xác định phân tích dữ liệu nhƣ thế nào và ở đâu. Với những ƣu điểm đó, khai phá dữ liệu đang đƣợc áp dụng vào nhiều lĩnh vực nhƣ tài chính, ngân hàng, bảo hiểm, y tế, an ninh, internet…Các công ty phần mềm lớn trên thế giới cũng đã rất quan tâm chú trọng việc nghiên cứu và phát triển các kỹ thuật khai phá dữ liệu: Oracle tích hợp các công cụ khai phá dữ liệu vào bộ Oracle9i, IBM phát triển khai phá dữ liệu với các ứng dụng nhƣ Intelligence Miner,…[5] 1.2.2 CÁC KỸ THUẬT KHAI PHÁ DỮ LIỆU Nếu đứng trên quan điểm của học máy (Machine learning) thì kỹ thuật 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 cơ sở dữ liệu 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. Đây là một kỹ thuật của ngành học máy để xây dựng một hàm từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp gồm đối tƣợng đầu vào và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục (gọi là hồi qui), hay có thể là dự đoán một nhãn phân loại cho một đối tƣợng đầu vào (gọi là phân loại). Nhiệm vụ của chƣơng trình học có giám sát là dự đoán giá trị của hàm cho một đối tƣợng bất kì là đầu vào hợp lệ, sau khi đã xem xét một số ví dụ huấn luyện (các cặp đầu vào và đầu ra 13 tƣơng ứng). Để đạt đƣợc điều này, chƣơng trình học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán đƣợc những tình huống chƣa gặp phải theo một cách “hợp lí”. - 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 là cụm (clustering) dữ liệu tƣơng tự nhau mà chƣa biết trƣớc các thông tin về lớp một phƣơng pháp của ngành học máy nhằm tìm ra một mô hình mà phù hợp với các quan sát. Nó khác biệt với học có giám sát ở chỗ là đầu ra đúng tƣơng ứng cho mỗi đầu vào là không biết trƣớc. Trong học không có giám sát, một tập dữ liệu đầu vào đƣợc thu thập. Học không có giám sát thƣờng đối xử với các đối tƣợng đầu vào nhƣ là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ đƣợc xây dựng cho tập dữ liệu đó [4]. - Học nửa 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 dữ liệu 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. Nếu căn cứ vào lớp các bài toán cần giải quyết thì kỹ thuật khai phá dữ liệu gồm các kỹ thuật sau: - Kỹ thuật khai phá dữ liệu mô tả: Có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có. Các kỹ thuật loại này gồm có: Phân cụm (Clustering), tóm tắt (Summarization), trực quan hoá (Visualization), phân tích sự phát triển và độ lệch (Evolution and deviation analysis), phân tích luật kết hợp (Association rules),… - Kỹ thuật khai phá dữ liệu dự đoán: Có nhiệm vụ đƣa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện tại. Các kỹ thuật loại này gồm có: Phân lớp (Classification), hồi quy (Regression),… 14 Trong luận văn này, tôi tập trung trình bày về một trong những phƣơng pháp thông dụng nhất thuộc kỹ thuật khai phá dữ liệu mô tả là “Phân cụm dữ liệu”. Khai phá dữ liệu Kỹ thuật khai phá dữ liệu dự đoán Phân lớp Hồi quy Phân tích thời gian Kỹ thuật khai phá dữ liệu mô tả Dự đoán Phân cụm Tóm tắt Khám phá chuỗi Phân tích luật kết hợp Hình 1.2. Các kỹ thuật khai phá dữ liệu 1.3 PHÂN CỤM DỮ LIỆU 1.3.1 KHÁI NIỆM VỀ PHÂN CỤM DỮ LIỆU Phân cụm dữ liệu (PCDL) là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin hữu ích cho việc ra quyết định. Nhƣ vậy phân cụm dữ liệu là kỹ thuật sử dụng quan sát đối tƣợng để nhóm các đối tƣợng thành các cụm hoặc chia một tập dữ liệu ban đầu thành các cụm sao cho: 15 - Các đối tƣợng trong cùng một cụm là giống nhau hoặc gần giống nhau đƣợc xác định bằng độ tương tự. Hay nói một cách khác, các đối tƣợng trong cùng một cụm là tương tự với nhau. - Các đối tƣợng thuộc các cụm khác nhau sẽ không tương tự (phi tương tự) với nhau. Vậy có thể hiểu một cách đơn giản là “Phân cụm là qúa trình tổ chức các đối tượng thành các nhóm sao cho các đối tượng trong cùng một nhóm là tương tự với nhau”. Quy trình này đƣợc thể hiện nhƣ hình 1.3. Thuật toán N đối tƣợng Phân cụm K nhóm Hình 1.3. Quy trình phân cụm Phân cụm tối ƣu thuộc lớp bài toán NP-Hard, số cách để phân chia n đối tƣợng thành k cụm đƣợc tính theo công thức: Số các cụm đƣợc xác định tuỳ thuộc vào phƣơng pháp phân cụm. Các thuật toán phân cụm tìm các nhóm chứa đối tƣợng tƣơng tự nhau. Hai hay nhiều đối tƣợng đƣợc xếp vào cùng một cụm nếu chúng có chung một định 16 nghĩa về khái niệm hoặc chúng xấp xỉ với các khái niệm đƣợc mô tả trƣớc. Một cụm là các đối tƣợng có thể xem nhƣ là một nhóm trong nhiều ứng dụng. Mặt khác, phân cụm là học bằng quan sát hơn là học bằng ví dụ nên còn đƣợc gọi là học không giám sát. Hầu hết các nhiệm vụ chính của khai phá dữ liệu, bắt đầu ở ngoài với một tập huấn luyện chƣa phân lớp và thử phát triển một mô hình có khả năng dự đoán một bản ghi mới sẽ đƣợc phân lớp nhƣ thế nào. Trong phân cụm, không có dữ liệu đƣợc phân lớp trƣớc và không có sự phân biệt giữa các biến độc lập và biến phụ thuộc. Trong học máy, phân cụm là một vấn đề quan trọng của học không có giám sát, vì nó phải đi giải quyết vấn đề tìm một cấu trúc trong tập hợp các dữ liệu chƣa biết trƣớc thông tin về lớp hay thông tin về tập ví dụ huấn luyện. Trong nhiều trƣờng hợp, khi phân lớp đƣợc xem là vấn đề học có giám sát thì phân cụm dữ liệu là một bƣớc trong phân lớp dữ liệu, trong đó phân cụm sẽ khởi tạo các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu [14][15]. 1.3.2 MỘT SỐ VẤN ĐỀ TRONG PHÂN CỤM DỮ LIỆU - Xử lý nhiễu: Hầu hết các dữ liệu sử dụng để phân cụm đều bị nhiễu do quá trình thu thập thiếu chính xác hay thiếu đầy đủ. Vì vậy cần phải xây dựng chiến lƣợc cho bƣớc tiền xử lý dữ liệu nhằm khắc phục hoặc loại bỏ nhiễu trƣớc khi chuyển sang giai đoạn phân tích cụm dữ liệu. Dữ liệu bị nhiễu là dữ liệu không chính xác hay là dữ liệu khuyết thiếu thông tin về một số thuộc tính. Một trong các kỹ thuật xử lý nhiễu hiện nay là việc thay thế giá trị các thuộc tính của đối tƣợng nhiễu bằng các giá trị thuộc tính tƣơng ứng. - Dò tìm phần tử ngoại lai: Phần tử ngoại lai là một nhóm nhỏ các đối tƣợng dữ liệu khác thƣờng so với các dữ liệu trong cơ sở dữ liệu. Loại bỏ những dữ liệu kiểu này để tránh ảnh hƣởng đến kết quả phân cụm. 17 Hình 1.4. Các phần tử ngoại lai trong dữ liệu - Phân cụm đang là vấn đề mở và khó: Vì phân cụm đang phải giải quyết nhiều vấn đề cơ bản nhƣ: Xây dựng hàm tính độ tƣơng tự, xây dựng các tiêu chuẩn phân cụm, xây dựng mô hình cho cấu trúc dữ liệu, xây dựng các thuật toán phân cụm và xác lập các điều kiện khởi tạo, xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm. Hiện nay, chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc dữ liệu. Với những loại dữ liệu hỗn hợp thì việc phân cụm càng trở nên khó khăn và đây đang là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu. 1.3.3 MỤC TIÊU CỦA PHÂN CỤM Mục tiêu của phân cụm là xác định đƣợc bản chất nhóm trong tập dữ liệu chƣa có nhãn. Nhƣng để có thể quyết định đƣợc cái gì tạo thành một cụm tốt. Nó đòi hỏi ngƣời sử dụng phải đƣa ra một số tiêu chuẩn mà theo cách đó kết quả phân cụm sẽ đáp ứng đƣợc yêu cầu. Ví dụ nhƣ quan tâm đến việc tìm đại diện cho các nhóm đồng nhất (rút gọn dữ liệu), tìm kiếm các nhóm hữu ích và phù hợp (các lớp dữ liệu hữu ích), tìm kiếm các đối tƣợng khác thƣờng (dò tìm phần tử ngoại lai),… 18 1.3.4 CÁC BƢỚC CƠ BẢN TRONG PHÂN CỤM - Chọn lựa đặc trưng: các đặc trƣng phải đƣợc chọn lựa một cách hợp lý để có thể mã hoá nhiều nhất thông tin liên quan đến công việc quan tâm. Mục tiêu chính là phải giảm thiểu sự dƣ thừa thông tin giữa các đặc trƣng. Các đặc trƣng cần đƣợc tiền xử lý trƣớc khi dùng chúng trong các bƣớc sau. - Chọn độ đo gần gũi: đây là một độ đo chỉ ra mức độ tƣơng tự hay không tƣơng tự giữa hai vectơ đặc trƣng. Phải đảm bảo rằng tất cả các vectơ đặc trƣng góp phần nhƣ nhau trong việc tính toán độ đo gần gũi và không có đặc trƣng nào át hẳn đặc trƣng nào, điều này đƣợc đảm bảo bởi quá trình tiền xử lý. - Tiêu chuẩn phân cụm: điều này phụ thuộc vào sự giải thích của chuyên gia cho thuật ngữ “dễ nhận thấy” dựa vào loại của các cụm đƣợc chuyên gia cho rằng đang ẩn giấu dƣới tập dữ liệu. Chẳng hạn, một cụm loại chặt của véctơ đặc trƣng trong không gian n chiều có thể dễ nhận thấy theo một tiêu chuẩn, trong khi một cụm loại “dài và mỏng” lại có thể đƣợc dễ nhận thấy bởi một tiêu chuẩn khác. Tiêu chuẩn phân loại có thể đƣợc diễn đạt bởi hàm chi phí hay một vài loại quy tắc khác. - Thuật toán phân loại: cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm làm sáng tỏ cấu trúc phân cụm của tập dữ liệu. - Công nhận kết quả: khi đã có kết quả phân loại thì ta phải kiểm tra tính đúng đắn của nó. Điều này thƣờng đƣợc thực hiện bởi việc dùng các kiểm định phù hợp. - Giải thích kết quả: trong nhiều trƣờng hợp, chuyên gia trong lĩnh vực ứng dụng phải kết hợp kết quả phân loại với những bằng chứng thực nghiệm và phân tích để đƣa ra các kết luận đúng đắn. 19 Trong một số trƣờng hợp, nên có cả bƣớc phân tích khuynh hƣớng phân cụm, trong bƣớc này có các kiểm định khác nhau để chỉ ra tập dữ liệu có hay không một cấu trúc phân cụm. Ví dụ nhƣ tập dữ liệu của ta có thể hoàn toàn ngẫu nhiên vì vậy mọi cố gắng phân cụm đều là vô nghĩa. Các lựa chọn khác nhau của các đặc trƣng, độ đo gần gũi, tiêu chuẩn phân cụm có thể dẫn tới các kết quả phân cụm khác nhau. 1.3.5 YÊU CẦU CỦA PHÂN CỤM Thuật toán phân cụm phải thoả mãn một số yêu cầu sau: - Có khả năng mở rộng: Một số thuật toán có thể áp dụng tốt với tập dữ liệu nhỏ nhƣng lại không hiệu quả khi áp dụng cho tập dữ liệu lớn. - Thích nghi với các kiểu thuộc tính khác nhau của dữ liệu. - Khám phá các cụm với hình thù bất kỳ: Hầu hết các cơ sở dữ liệu có chứa các cụm dữ liệu với các hình thù khác nhau nhƣ hình lõm, hình cầu,… - Tối thiểu lƣợng tri thức cần cho xác định các tham số đầu vào: Các giá trị đầu vào thƣờng rất ảnh hƣởng đến thuật toán phân cụm và rất phức tạp để xác định các giá trị đầu vào thích hợp đối với các cơ sở dữ liệu lớn. - Khả năng thích nghi với các dữ liệu nhiễu hoặc ngoại lai. - Ít nhạy cảm với thứ tự của dữ liệu vào: Cùng một tập dữ liệu khi đƣa vào phân nhóm với các thứ tự khác nhau thì không ảnh hƣởng đến kết quả phân cụm. - Thích nghi với dữ liệu đa chiều: Thuật toán áp dụng hiệu quả cho dữ liệu với số chiều khác nhau. - Dễ hiểu và dễ sử dụng.
- Xem thêm -