Tài liệu Trình bày tổng quan về phân cụm dữ liệu

TRỪƠNG ĐẠI HỌC CÔNG NGHỆ- ĐẠI HỌC QUỐC GIA HÀ NỘI TRÌNH BÀY TÔNG QUAN VỀ PHÂN CỤM DỮ LIỆU Học viên: PHẠM ĐĂNG KHOA Hà nội: 2007 3 MỤC LỤC MỤC LỤC ..................................................................................................... 3 DANH MỤC HÌNH VẼ ................................................................................. 5 LỜI CẢM ƠN ................................................................................................ 6 PHẦN MỞ ĐẦU ............................................................................................ 7 CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU .............................. 9 1.1. Khai phá dữ liệu và khám phá tri thức .................................................. 9 1.2. Ứng dụng của khai phá dữ liệu ........................................................... 11 1.3. Các kỹ thuật khai phá dữ liệu ............................................................. 12 1.3.1. Kỹ thuật khai phá dữ liệu dự đoán ............................................... 12 1.3.2. Kỹ thuật khai phá dữ liệu mô tả ................................................... 12 1.4. Phân cụm dữ liệu................................................................................ 13 1.4.1. Học có giám sát và không có giám sát ......................................... 13 1.4.2. Khái niệm phân cụm dữ liệu ........................................................ 14 1.4.3. Mục tiêu của phân cụm ................................................................ 16 1.4.4. Ứng dụng của phân cụm dữ liệu .................................................. 17 1.4.5. Yêu cầu của phân cụm dữ liệu...................................................... 17 CHƢƠNG 2: CÁC PHƢƠNG PHÁP VÀ THUẬT TOÁN PHÂN CỤM DỮ LIỆU ............................................... 19 2.1. Phƣơng pháp phân cụm phân hoạch ................................................... 20 2.1.1. Thuật toán K-means ..................................................................... 21 2.1.2. Thuật toán PAM ........................................................................... 25 2.1.3. Thuật toán CLARA ....................................................................... 27 2.1.4. Thuật toán CLARANS .................................................................. 29 2.2. Phƣơng pháp phân cụm phân cấp ....................................................... 32 2.2.1. Thuật toán BIRCH. ...................................................................... 34 2.2.2. Thuật toán CURE ........................................................................ 37 2.2.3. Thuật toán AGNES và DIANA ..................................................... 39 2.2.4. Thuật toán CHAMELEON ........................................................... 40 2.3. Phƣơng pháp phân cụm dựa trên mật độ ............................................ 41 2.3.1. Thuật toán DBSCAN .................................................................... 41 4 2.3.2. Thuật toán OPTICS ..................................................................... 46 2.3.3. Thuật toán DENCLUE ................................................................. 48 2.4. Phƣơng pháp phân cụm dựa trên lƣới ................................................. 50 2.4.1. Thuật toán STING ........................................................................ 51 2.4.2. Thuật toán CLIQUE ..................................................................... 53 2.4.3. Thuật toán WAVECLUSTER ........................................................ 54 2.5. Phƣơng pháp phân cụm dựa trên mô hình .......................................... 55 2.5.1. Thuật toán EM ............................................................................. 55 2.5.2.Thuật toán COBWEB .................................................................... 57 CHƢƠNG 3: ỨNG DỤNG CÁC THUẬT TOÁN PHÂN CỤM VỚI DỮ LIỆU NGÀNH BẢO HIỂM XÃ HỘI........................................................... 59 3.1. Những khái niệm chung về Bảo hiểm xã hội ...................................... 59 3.1.1. Bảo hiểm xã hội ........................................................................... 59 3.1.2. Bảo hiểm y tế ............................................................................... 62 3.2. Cơ sở dữ liệu bảo hiểm xã hội ............................................................ 63 3.2.1. Cơ sở dữ liệu người đang tham gia BHXH, BHYT ....................... 63 3.2.2. Cơ sở dữ liệu người đang hưởng các chế độ BHXH hàng tháng .. 67 3.3. Áp dụng các thuật toán phân cụm vào cơ sở dữ liệu của ngành bảo hiểm xã hội ............................................................................................... 68 3.3.1. Bài toán ....................................................................................... 68 3.3.2. Giải pháp ..................................................................................... 69 3.3.3. Chương trình mô phỏng thuật toán PCDL K-means .................... 70 KẾT LUẬN .................................................................................................. 73 TÀI LIỆU THAM KHẢO ............................................................................ 74 5 DANH MỤC HÌNH VẼ Hình 1.1: Quá trình khám phá tri thức Hình 1.2: Sơ đồ quá trình phân cụm dữ liệu Hình 1.3: Ví dụ về phân cụm Hình 2.1: Các thuật toán phân cụm dữ liệu Hình 2.2: Xác lập ranh giới các cụm ban đầu Hình 2.3: Tính toán trọng tâm của các cụm mới Hình 2.4: Một số dạng cụm dữ liệu khi áp dụng thuật toán K-means Hình 2.5: Chiến lƣợc phân cụm phân cấp Hình 2.6: Cây CF đƣợc sử dụng bởi thuật toán BIRCH Hình 2.7: Thuật toán BIRCH Hình 2.8: Khái quát thuật toán CURE Hình 2.9: Các cụm dữ liệu đƣợc khám phá bằng thuật toán CURE Hình 2.10: Các bƣớc thực hiện của thuật toán AGNES và DIANA Hình 2.11: Khái quát thuật toán CHAMELEON Hình 2.12: Hình dạng các cụm khi áp dụng thuật toán DBSCAN Hình 2.13: Mật độ liên lạc và mật độ liên thông Hình 2.14: Thứ tự phân cụm các đối tƣợng của thuật toán OPTICS Hình 2.15: Biểu diễn ví dụ hàm ảnh hƣởng sóng ngang Hình 2.16: Biểu diễn ví dụ hàm ảnh hƣởng Gaussian Hình 2.17: Cấu trúc phân cấp Hình 3.1: Chƣơng trình mô phỏng thuật toán PCDL Hình 3.2: Khởi tạo các thông số cho chƣơng trình Hình 3.3: Kết quả thực hiện thuật toán 9 15 15 20 22 22 24 33 34 35 37 38 39 40 42 44 47 49 50 51 70 71 72 7 PHẦN MỞ ĐẦU Cùng với sự phát triển của xã hội, sự phát triển của lĩnh vực Công nghệ thông tin trong thời gian qua, nhu cầu về thông tin để đáp ứng các yêu cầu hàng ngày của con ngƣời trên mọi lĩnh vực ngày càng phát triển. Do vậy, khối lƣợng thông tin lƣu trữ lại ngày càng tăng làm cho kho dữ liệu tri thức chung của con ngƣời ngày càng trở nên vô tận. Vấn đề đặt ra ở đây là làm thế nào để chúng ta có thể khai thác đƣợc tối đa nguồn tri thức dồi dào và vô tận đó. Khám phá tri thức và khai phá dữ liệu đang nổi lên nhanh chóng và trở thành một trong những hƣớng nghiên cứu chính liên quan tới nhiều lĩnh vực khoa học máy tính và công nghệ tri thức kết hợp với cơ sở dữ liệu, thống kê, học máy và những lĩnh vực có liên quan để trích chọn những thông tin giá trị và tri thức trong khối lƣợng dữ liệu lớn. Khám phá tri thức là cách tiếp cận chung để phân tích và rút ra tri thức hữu ích từ cơ sở dữ liệu sử dụng các kỹ thuật hoàn toàn tự động. Các kỹ thuật chính đƣợc áp dụng trong lĩnh vực này phần lớn đƣợc kế thừa từ lĩnh vực cơ sở dữ liệu, học máy, trí tuệ nhân tạo, lí thuyết thông tin, xác suất thống kê và tính toán hiệu năng cao. 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. Trong thời gian gần đây, trong lĩnh vực phân cụm dữ liệu, tập trung chủ yếu vào nghiên cứu, phân tích các mô hình dữ liệu phức tạp nhƣ dữ liệu văn bản, web, hình ảnh,... và đặc biệt là mô hình hỗn hợp để áp dụng chúng trong phân cụm dữ liệu. Xuất phát trong hoàn cảnh đó, luận văn lựa chọn đề tài “Một số vấn đề về phân cụm dữ liệu và ứng dụng trong ngành bảo hiểm xã hội”. Luận văn nhằm nghiên cứu một số vấn đề về khám phá tri thức trong cơ sở dữ liệu và tập trung vào các kỹ thuật phân cụm dữ liệu. Trên cơ sở đó đề cập đến một ứng dụng thực tế trên cơ sở khám phá tri thức và khai phá dữ liệu trên cơ sở dữ liệu của ngành bảo hiểm xã hội. 8 Luận văn gồm Phần mở đầu, Phần kết luận và 3 chƣơng nội dung, cụ thể nhƣ sau: Chương 1: Trình bày tổng quan về phân cụm dữ liệu và một số khái niệm liên quan, đồng thời cũng trình bày các giai đoạn của quá trình phát hiện tri thức và đề cập đến các kỹ thuật hƣớng tiếp cận chính trong khai phá dữ liệu, những khái niệm liên quan đến phân cụm dữ liệu. Chương 2: Phân tích chi tiết các vấn đề cơ bản trong phân cụm dữ liệu, tóm tắt các đặc trƣng của các phƣơng pháp phân cụm dữ liệu đƣợc sử dụng phổ biến và một số thuật toán phân cụm dữ liệu. Chương 3: Áp dụng một thuật toán phân cụm dữ liệu vào khai phá dữ liệu của ngành bảo hiểm xã hội. 9 CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1.1. Khai phá dữ liệu và khám phá tri thức Tri thức đƣợc xem nhƣ là các thông tin tích hợp, bao gồm các sự kiện, hiện tƣợng và mối quan hệ giữa chúng đã đƣợc nhận thức, khám phá hoặc nghiên cứu. Trong thời đại bùng nổ của công nghệ thông tin hiện nay, bất cứ một lĩnh vực nào cũng đều gắn liền với việc thu thập, lƣu trữ và xử lý thông tin. Do vậy, hiện nay chúng ta đang sở hữu một kho dữ liệu khổng lồ chứa đựng thông tin của tất cả các lĩnh vực. Bài toàn đặt ra ở đây là làm thế nào để nhận biết đƣợc, lấy đƣợc những thông tin mà mình cần sử dụng cho công việc của mình. Bài toán đó đã đƣợc giải quyết bằng việc áp dụng các phƣơng pháp khám phá tri thức trong cơ sở dữ liệu. 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 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 bao gồm các bƣớc sau: Tìm hiểu lĩnh vực ứng dụng Thu thập và tiền xử lý dữ liệu Khai phá dữ liệu Trích chọn tri thức Biểu diễn và đánh giá tri thức Ứng dụng tri thức đã được khám phá Hình 1.1: Quá trình khám phá tri thức 10 Tìm hiểu lĩnh vực ứng dụng: bƣớc này có ý nghĩa quan trọng cho việc rút ra đƣợc các tri thức hữu ích và chọn các phƣơng pháp khai phá dữ liệu thích hợp sao cho phù hợp với mục đích ứng dụng và bản chất dữ liệu. Thu thập và tiền xử lý dữ liệu: bao gồm 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ị thiếu, biến đổ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 để xây dựng 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. Bƣớc này thƣờng tốn thời gian trong toàn bộ quá trình khám phá tri thức. Khai phá dữ liệu, trích chọn tri thức: trích chọn các mẫu ẩn hoặc mô hình ẩn trong dữ liệu. Một mô hình có thể đƣợc xem nhƣ "một biểu diễn tổng thể của một cấu trúc nhằm tóm lƣợ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". Các lớp chính của phƣơng pháp khai phá dữ liệu là mô hình dự đoán nhƣ phân loại và hồi quy; phân đoạn; mô hình phụ thuộc nhƣ đồ thị hoặc ƣớc lƣợng mật độ; tóm lƣợc nhƣ tìm các mối quan hệ giữa các trƣờng, liên kết, trừu tƣợng; và mô hình thay đổi và phát hiện độ lệch trong dữ liệu và tri thức. Biểu diễn và đánh giá tri thức: đặ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 cá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, và quy trình khám phá tri thức cần phải đƣợc lặp đi lặp lại có điều chỉnh theo các tri thức đã phát hiện đƣợc. Để có thể đánh giá các luật đƣợc á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 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. Ứng dụng tri thức đã được khám phá: củng cố các tri thức đã khám phá đƣợc, 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 sử dụng thực tiễn là mục đích cuối cùng của khám phá tri thức. 11 Một bƣớc quan trọng trong quá trình khám phá tri thức trong cơ sở dữ liệu là khai phá dữ liệu. Khai phá dữ liệu là quá trình trích xuất thông tin cần thiết trong cơ sở dữ liệu. Đây là bƣớc tốn nhiều thời gian và tài nguyên nhất trong quá trình khám phá tri thức. Bƣớc này bao gồm các liên quan đến thuật toán, tìm kiếm các mẫu và mô hình trong dữ liệu, thƣờng đề cập đến vấn đề kỹ thuật. Khai phá dữ liệu là một lĩnh vực liên quan tới rất nhiều ngành khoa học khác nhau nhƣ: thống kê, học máy, cơ sở dữ liệu, thuật toán, trừu tƣợng, kỹ thuật cao và tính toán song song, thu nhận tri thức trong hệ chuyên gia, và dữ liệu trừu tƣợng. Đặc trƣng của hệ thống khám phá tri thức nhờ vào các phƣơng pháp, thuật toán, và kỹ thuật từ những lĩnh vực khác nhau. Mục đích cuối cùng là trích ra tri thức từ dữ liệu trong cơ sở dữ liệu khổng lồ. 1.2. Ứng dụng của khai phá dữ liệu Kỹ thuật khai phá dữ liệu có thể đƣợc ứng dụng trong nhiều lĩnh vực, điển hình là: Thông tin thương mại: + Phân tích dữ liệu bán hàng và thị trƣờng; + Phân tích đầu tƣ; + Quyết định cho vay; + Phát hiện gian lận; Thông tin sản xuất: + Điều khiển và lập kế hoạch; + Hệ thống quản lý; + Phân tích kết quả thử nghiệm; Thông tin khoa học: + Dự báo thời tiết; + Cơ sở dữ liệu sinh học; + Khoa học địa lý: tìm động đất; 12 Thông tin cá nhân: 1.3. Các kỹ thuật khai phá dữ liệu Hiện nay có rất nhiều các kỹ thuật khai phá dữ liệu khác nhau, tuy nhiên chúng đƣợc phân chia thành 2 nhóm chính: 1.3.1. Kỹ thuật khai phá dữ liệu dự đoán Sử dụng một số biến hoặc trƣờng trong cơ sở dữ liệu để đoán ra các giá trị không biết hoặc sẽ có của các biến chú ý khác, sử dụng 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 này bao gồm: phân lớp (classification), hồi quy (regression),… Hồi quy là việc học một hàm ánh xạ một dữ liệu tới một giá trị dự đoán thực. Các ứng dụng hồi quy hiện có rất nhiều, ví dụ nhƣ là việc dự đoán số lƣợng khối gỗ trong rừng thông qua các thiết bị vi sóng cảm biến từ xa, đƣa ra xác suất bệnh nhân có thể chết khi có kết quả của xét nghiệm chuẩn đoán. Phân lớp là việc học một hàm để ánh xạ (bộ phân lớp) một dữ liệu vào một trong các phân lớp đã đƣợc định nghĩa sẵn. Các ví dụ về các phƣơng thức phân lớp thƣờng sử dụng nhƣ là một phần của các ứng dụng khai phá tri thức, bao gồm việc phân lớp theo xu hƣớng của các thị trƣờng tài chính (Apte & Hong) và nhận dạng tự động các đối tƣợng khả nghi trong cơ sở dữ liệu ảnh (Fayyad, Djorgovski, & Weir). 1.3.2. Kỹ thuật khai phá dữ liệu mô tả Tập trung vào việc tìm kiếm các mẫu mà con ngƣời có thể hiểu đƣợc để mô tả dữ liệu, mô tả 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 này bao gồm: phân cụm (clustering), khái quát hoá (summerization), phát hiện và thay đổi độ lệch (Evolution and deviation analyst), mô hình hoá sự phụ thuộc,… Phân cụm là mô tả chung việc tìm ra tập xác định các nhóm hay loại để mô tả dữ liệu (Titerington, Smith & Makov 1985, Jain & Dubes 1988). Các nhóm có thể tách riêng, phân cấp, hoặc chồng lên nhau. Khái quát hóa bao gồm các phƣơng thức để tìm kiếm một mô tả cho một tập con dữ liệu. Ví dụ đơn giản là việc lập bảng theo ý nghĩa và độ lệch 13 chuẩn đối với mọi trƣờng hợp. Các phƣơng thức phức tạp hơn có thể là độ lệch của một vài quy tắc chung, các kỹ thuật mô phỏng đa biến và khai phá các quan hệ phụ thuộc giữa các biến. Kỹ thuật khái quát hóa thƣờng áp dụng cho việc phân tích dữ liệu ràng buộc có tính thăm dò và tạo các báo cáo tự động. Mô hình hóa sự phụ thuộc bao gồm việc tìm kiếm một mô hình để mô tả sự phụ thuộc giữa các biến. Các mô hình phụ thuộc tồn tại có hai mức: mức cấu trúc của mô hình xác định các biến nào là phụ thuộc cục bộ với nhau, và mức định lƣợng của mô hình xác định các phụ thuộc theo một quy tắc nào đó. Ví dụ, các mạng phụ thuộc xác suất thƣờng dùng để mô tả các khía cạnh cấu trúc hóa của mô hình và xác suất. Các mạng phụ thuộc xác suất ứng dụng nhiều trong các hệ chuyên gia về y tế, mô hình hóa bộ gen ngƣời. Phát hiện và thay đổi độ lệch tập trung vào khai thác những thay đổi đáng kể nhất trong dữ liệu từ các giá trị chuẩn hoặc đƣợc đo trƣớc (Berndt & Cliffort, Guyon et al. Kloesgen, Mathéu et al., Basseville & Nikiforov 1993). Tuy nhiên trong khuôn khổ của luận văn này tôi chỉ tập trung vào phân tích một trong những phƣơng pháp phổ biến và thông dụng nhất của các phƣơng pháp khai phá dữ liệu đó là “Phân cụm (clustering)”. 1.4. Phân cụm dữ liệu 1.4.1. Học có giám sát và không có giám sát 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 hay nói cách khác là 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ặp dữ liệu đầu vào và đầu ra tƣơng ứng. Đầu ra có thể là một giá trị liên tục (hồi quy) hay có thể là một nhãn đƣợc gán cho một đối tƣợng dữ liệu đầu vào (phân lớp). Nhiệm vụ của chƣơng trình là dự đoán giá trị đầu ra của một hàm cho một đối tƣợng dữ liệu đầu vào hợp lệ với mẫu là một số ví dụ huấn luyện. 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 các tập ví dụ huấn luyện. Nó khác với học có 14 giám sát ở chỗ là đầu ra đúng tƣơng ứng với đầu vào không biết trƣớc. Học không có giám sát thƣờng coi các đối tƣợng đầu vào nhƣ một tập dữ liệu ngẫu nhiên. 1.4.2. Khái niệm phân cụm dữ liệu Có nhiều định nghĩa khác nhau về phân cụm dữ liệu. Đơn giản nhất là gom nhóm những phần tử dữ liệu tƣợng tự nhau vào chung một cụm (cluster). Cụ thể hơn, cho một tập n phần tử dữ liệu X, mục đích là phân chia các phần tử dữ liệu thuộc tập X đó thành k nhóm (cụm) sao cho các cụm này phải thoả mãn các yêu cầu sau: Các phần tử dữ liệu trong một cụm là giống nhau hoặc gần nhau đƣợc xác định bằng độ tƣơng tự (các phần tử trong cùng một cụm là tƣơng tự nhau). Các phần tử dữ liệu trong một cụm là khác với các phần tử dữ liệu trong các cụm khác (các phần tử ở các cụm khác nhau thì phi tƣơng tự với nhau). Ta có thể mô tả quá trình phân cụm dữ liệu qua một sơ đồ tổng quát nhƣ hình dƣới: Hình 1.2: Sơ đồ quá trình phân cụm dữ liệu Số các cụm dữ liệu đƣợc xác định trƣớc theo kinh nghiệm hoặc có thể đƣợc xác định tuỳ thuộc vào phƣơng pháp phân cụm. Hai hay nhiều phần tử đƣợc gom vào cùng một nhóm nếu chúng có chung một định nghĩa về khái niệm hoặc chúng xấp xỉ với khái niệm đƣợc mô tả trƣớc. 15 Một đặc điểm của phân cụm là quá trình phân cụm đƣợc thực hiện (học) bằng cách quan sát chứ không phải đƣợc học qua các ví dụ cho nên phân cụm dữ liệu đƣợc gọi là quá trình học không có giám sát. Để rõ hơn về phân cụm dữ liệu, ta xét ví dụ sau: Hình 1.3: Ví dụ về phân cụm Trong hình dữ liệu đƣợc chia thành 4 cụm; tƣơng tự là khoảng cách: hai hay nhiều đối tƣợng đƣợc xếp vào một cụm nếu chúng là "gần nhau" theo mức độ khoảng cách đã đƣợc xác định; phi tƣơng tự là khoảng cách: hai hay nhiều đối tƣợng đƣợc xếp vào các cụm khác nếu chúng là "xa nhau". Đƣợc gọi là phân cụm dựa trên khoảng cách. Một cách hiểu khác của phân cụm là khái niệm phân cụm: 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 nghĩa về khái niệm hoặc chúng xấp xỉ với các khái niệm mô tả cho trƣớc. Một vấn đề thƣờng gặp trong phân cụm là hầu hết các dữ liệu cần cho phân cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc 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. Nhiễu ở đây là có thể các đối tƣợng dữ liệu không chính xác, hoặc là các đối tƣợng dữ liệu khuyết thiếu thông tin về một số 16 thuộc tính. Một trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá trị các thuộc tính của đối tƣợng nhiễu bằng giá trị thuộc tính tƣơng ứng. Ngoài ra, dò tìm phần tử ngoại lai là một trong những hƣớng nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác định 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, tức là các đối tƣợng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu nhằm tránh sự ảnh hƣởng của chúng tới quá trình và kết quả của phân cụm. Khám phá các phần tử ngoại lai đã đƣợc phát triển và ứng dụng trong viễn thông, dò tìm gian lận thƣơng mại, làm sạch dữ liệu,... Theo các nghiên cứu thì 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 cụm dữ liệu. Hơn nữa, các phƣơng pháp phân cụm cần có cách thức biểu diễn cấu trúc của các cụm dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tƣơng ứng một thuật toán phân cụm phù hợp. Phân cụm đang là vấn đề mở và khó, vì phải giải quyết nhiều vấn đề cơ bản (gồm: 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 cụm dữ liệu; xây dựng 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) một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị dữ liệu, và đây cũng là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu. 1.4.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 gán nhãn. Tuy nhiên, làm thế nào để có thể quyết định đƣợc cái gì tạo thành một cụm tốt. Nó có thể đƣợc chỉ ra rằng không có tiêu chuẩn tuyệt đối "tốt" mà có thể không phụ thuộc vào kết quả của phân cụm. Do vậy, nó đòi hỏi ngƣời sử dụng phải cung cấp tiêu chuẩn này, theo cách mà kết quả phân cụm sẽ đáp ứng yêu cầu. Ví dụ, có thể 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), trong tìm kiếm "các cụm tự nhiên" và mô tả những thuộc tính chƣa biết (kiểu dữ liệu "tự nhiên"), trong 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") hoặc tìm kiếm các đối tƣợng khác thƣờng (dò tìm phần tử ngoại lai). 17 1.4.4. Ứng dụng của phân cụm dữ liệu Tiếp thị: từ cơ sở dữ liệu khách hàng đã mua hàng trong quá khứ, tìm kiếm các nhóm khách hàng có những sở thích tƣơng tự nhau để có những hình thức tiếp thị, khuyến mại phù hợp với nhu cầu, sở thích của từng nhóm khách hàng. Sinh học: phân loại động vật và thực vật dựa trên các đặc điểm của chúng. Thư viện: phân loại các đầu sách dựa trên các thông tin của sách. Bảo hiểm: nhận dạng, phân loại các nhóm ngƣời mua bảo hiểm theo các mức khác nhau; phát hiện đƣợc giả mạo, gian lận. Quy hoạch: phân loại các nhóm nhà ở theo loại, theo giá trị và theo vị trí địa lý. Nghiên cứu động đất: phân lớp các tâm động đất quan sát đƣợc để xác định những vùng nào là vùng nguy hiểm. WWW: phân loại tài liệu,… 1.4.5. Yêu cầu của phân cụm dữ liệu Có khả năng mở rộng: một số thuật toán có thể ứng dụng tốt với tập dữ liệu nhỏ nhƣng không hiệu 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: thuật toán có thể áp dụng hiệu quả với việc phân cụm các tập dữ liệu có các kiểu dữ liệu nhƣ kiểu số, nhị phân, hạng mục,... và thích nghi với kiểu dữ liệu hỗn hợp của các kiểu dữ liệu trên. 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 nhiều cụm dữ liệu với các hình thù khác nhau nhƣ hình lõm, hình cầu, hình que,... do đó để khám phá đƣợc các cụm có tính tự nhiên thì các thuật toán cần phải có khả năng khám phá ra các cụm có hình thù bất kỳ. Yêu 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. 18 Khả năng thích nghi với dữ liệu nhiễu hoặc ngoại lai: hầu hết các dữ liệu phân cụm trong khai phá dữ liệu đều chứa đựng các dữ liệu lỗi, dữ liệu không đầy đủ, do đó thuật toán phân cụm không những hiệu quả đối với các dữ liệu nhiễu mà còn tránh dẫn đến chất lƣợng phân cụm thấp do nhạy cảm với nhiễu. Í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 xử lý cho thuật toán phân cụm dữ liệu với các thứ tự vào của các đối tƣợng dữ liệu ở các lần thực hiện khác nhau thì không ảnh hƣởng lớn đến kết quả phân cụm. Ít nhạy cảm với các tham số đầu vào: giá trị đầu vào của các tham số khác nhau ít gây ra các thay đổi lớn đối với kết quả phân cụm. Thích nghi với dữ liệu đa chiều: thuật toán có khả năng áp dụng hiệu quả cho dữ liệu có số chiều khác nhau. Dễ hiểu và dễ sử dụng. 19 CHƢƠNG 2: CÁC PHƢƠNG PHÁP VÀ THUẬT TOÁN PHÂN CỤM DỮ LIỆU Có rất nhiều các phƣơng pháp phân cụm đƣợc ứng dụng trong thực tế. Các phƣơng pháp phân cụm đều hƣớng tới hai mục tiêu chung: chất lƣợng của các cụm xây dựng đƣợc và tốc độ thực hiện của thuật toán. Tuy nhiên có thể phân loại thành từng loại cơ bản dựa trên phân loại các phƣơng pháp. Hiện nay các phƣơng pháp phân cụm có thể phân loại theo các cách tiếp cận chính sau: + Phƣơng pháp phân cụm phân hoạch + Phƣơng pháp phân cụm phân cấp. + Phƣơng pháp phân cụm dựa trên mật độ. + Phƣơng pháp phân cụm dựa trên lƣới. + Phƣơng pháp phân cụm dựa trên mô hình. Tƣơng ứng với các phƣơng pháp phân cụm trên thì có rất nhiều các thuật toán phân cụm dữ liệu tƣơng ứng. Do có rất nhiều thuật toán phân cụm dữ liệu nhƣ vậy cho nên vấn đề ở đây là khi sử dụng các thuật toán phân cụm dữ liệu khác nhau đối với cùng một tập dữ liệu đầu vào thì kết quả sẽ giống nhau hoặc khác nhau nhƣ thế nào ? Việc xác định xem thuật toán nào là phù hợp trong từng trƣờng hợp cụ thể phụ thuộc vào rất nhiều yếu tố nhƣ kích thƣớc của tập dữ liệu đầu vào, các đặc trƣng của dữ liệu,… Ta có thể xem một cách tổng quát các thuật toán phân cụm dữ liệu tƣơng ứng với các phƣơng pháp phân cụm ở hình sau: 20 Các thuật toán phân cụm 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 Các thuật toán phân cụm dựa trên mật độ Các thuật toán phân cụm dựa trên lƣới Các thuật toán phân cụm dựa trên mô hình Thuật toán k-means Thuật toán BIRCH Thuật toán DBSCAN Thuật toán STING Thuật toán EM Thuật toán PAM Thuật toán CURE Thuật toán OPTICS Thuật toán CLIQUE Thuật toán COBWEB Thuật toán CLARA Thuật toán AGNES Thuật toán DENCLUE Thuật toán WaveCluster v.v... Thuật toán CLARANS Thuật toán DIANA v.v... v.v... v.v... Thuật toán ROCK Thuật toán Chameleon v.v... Hình 2.1: Các thuật toán phân cụm dữ liệu 2.1. Phƣơng pháp phân cụm phân hoạch Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k nhóm cho đến khi xác định số các cụm đƣợc thiết lập. Số các cụm đƣợc thiết lập là các đặc trƣng đƣợc lựa chọn trƣớc. Phƣơng pháp này là tốt cho việc tìm các cụm hình cầu trong không gian Euclidean. Ngoài ra phƣơng pháp này cũng phụ thuộc vào khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là gần nhau 21 với mỗi điểm khác và các điểm dữ liệu nào không có quan hệ hoặc có quan hệ là xa nhau so với mỗi điểm khác. Có một chú ý phƣơng pháp này không thể xử lý các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc. Các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ƣu toàn cục cho vấn đề phân cụm dữ liệu, do nó phải tìm kiếm tất cả các cách phân hoạch có thể đƣợc. Chính vì vậy, trên thực tế thƣờng đi tìm giải pháp tối ƣu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lƣợng của cụm cũng nhƣ để hƣớng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Theo phƣơng pháp này, thông thƣờng bắt đầu khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo phép ngẫu nhiên hoặc heuristic, và liên tục tinh chỉnh nó cho đến khi thu đƣợc một phân hoạch mong muốn, thỏa mãn ràng buộc cho trƣớc. Các thuật toán phân cụm phân hoạch cố gắng cải tiến tiêu chuẩn phân cụm, bằng cách tính các giá trị đo độ tƣơng tự giữa các đối tƣợng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Nhƣ vậy, ý tƣởng chính của thuật toán phân cụm phân hoạch tối ƣu cục bộ là sử dụng chiến lƣợc ăn tham (Greedy) để tìm kiếm nghiệm. 2.1.1. Thuật toán K-means K-means là thuật toán phân cụm trong đó các cụm đƣợc định nghĩa bởi trung tâm của các phần tử trong cụm đó. Phƣơng pháp này dựa trên độ đo khoảng cách của các đối tƣợng dữ liệu trong cụm. Trong thực tế, nó đo khoảng cách tới trung tâm của các đối tƣợng dữ liệu trong cụm (trung tâm của một cụm dữ liệu đƣợc coi nhƣ là giá trị trung bình của các đối tƣợng dữ liệu trong cụm đó). Nhƣ vậy nó cần khởi tạo một tập trung tâm các cụm ban đầu, và thông qua đó nó lặp lại các bƣớc gồm gán mỗi đối tƣợng tới cụm mà trung tâm gần, và tính toán lại trung tâm của mỗi cụm trên cơ sở gán mới cho các đối tƣợng. Quá trình lặp này dừng khi các trung tâm hội tụ. 22 Hình 2.2: Xác lập ranh giới các cụm ban đầu Trong phƣơng pháp k-means, chọn một giá trị k và sau đó chọn ngẫu nhiên k trung tâm của các đối tƣợng dữ liệu. Tính toán khoảng cách giữa đối tƣợng dữ liệu và trung bình mỗi cụm để tìm kiếm phần tử nào là tƣơng tự và thêm vào cụm đó. Từ khoảng cách này có thể tính toán trung bình mới của cụm và lặp lại quá trình cho đến khi mỗi các đối tƣợng dữ liệu là một bộ phận của các cụm k. Mục đích của thuật toán k-means là sinh k cụm dữ liệu {C1, C2,..., Ck} từ một tập dữ liệu chứa n đối tƣợng trong không gian d chiều Xi = (xi1, xi2,..., k xid), i = 1 ÷ n, sao cho hàm tiêu chuẩn: E  xC D 2 ( x  mi ) đạt giá trị tối i 1 i thiểu. Trong đó: mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tƣợng. Hình 2.3: Tính toán trọng tâm của các cụm mới