Luận văn Nghiên cứu các kỹ thuật phân cụm dữ liệu và ứng dụng

i ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ =================== Nguyễn Thị Huế NGHIÊN CỨU CÁC KỸ THUẬT PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ HÀ NỘI - 2011 ii LỜI CẢM ƠN Để hoàn thành được luận văn này, trước hết tôi xin gửi lời cảm ơn sâu sắc nhất tới GS.TS Vũ Đức Thi, Viện trưởng Viện công nghệ thông tin đã tận tình hướng dẫn, chỉ bảo, định hướng, đóng góp những ý kiến quý báu trong suốt quá trình tôi thực hiện luận văn. Tôi xin chân thành cảm ơn các thầy, cô giáo trong Bộ môn Hệ thống thông tin, Khoa Công nghệ thông tin, Phòng Đào tạo Sau đại học - Nghiên cứu Khoa học, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất để tôi hoàn thành khóa học này. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè, những người luôn khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt quá trình học tập và làm luận văn này. Hà Nội, ngày 10 tháng 04 năm 2011 Học viên Nguyễn Thị Huế iii LỜI CAM ĐOAN Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày hoàn chỉnh trong bất cứ tài liệu nào. Hà Nội, ngày 10 tháng 04 năm 2011 Học viên Nguyễn Thị Huế iv MỤC LỤC MỞ ĐẦU ................................................................................................................1 Chương 1.................................................................................................................3 TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU ..................3 1.1. Giới thiệu chung ...........................................................................................3 1.2. Khai phá tri thức và quá trình khai phá tri thức .............................................3 1.2.1. Khai phá tri thức ....................................................................................3 1.2.2. Quá trình khai phá tri thức .....................................................................4 1.3. Khai phá dữ liệu ...........................................................................................5 1.3.1. Khai phá dữ liệu.....................................................................................5 1.3.2. Mục tiêu của khai phá dữ liệu ................................................................6 1.3.3. Quá trình khai phá dữ liệu ......................................................................6 1.3.4. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu..7 1.3.5. Thách thức – khó khăn trong khai phá tri thức và khai phá dữ liệu .......13 1.3.6. Ứng dụng của khai phá dữ liệu.............................................................13 1.3.7. Kết luận ...............................................................................................14 Chương 2. PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG ...............15 PHÂN CỤM DỮ LIỆU .........................................................................................15 2.1. Giới thiệu....................................................................................................15 2.2. Các ứng dụng của phân cụm .......................................................................16 2.3. Các yêu cầu về thuật toán phân cụm dữ liệu................................................17 2.4. Các kiểu dữ liệu trong phân cụm.................................................................18 2.5. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu .....................21 2.6. Các hướng tiếp cận của bài toán phân cụm dữ liệu......................................28 2.6.1. Phương pháp phân hoạch (Partitioning Methods) ...........................28 2.6.2. Phương pháp phân cấp (Hierarchical Methods) ..............................36 2.6.3. Phương pháp dựa trên mật độ (Density-Based Methods) ................44 2.6.4. Phương pháp dựa trên lưới (Gird-Based Methods)..........................51 2.6.5. Kết luận ..........................................................................................56 Chương 3: ỨNG DỤNG ........................................................................................58 KẾT LUẬN ...........................................................................................................65 TÀI LIỆU THAM KHẢO .....................................................................................66 PHỤ LỤC..............................................................................................................68 v DANH MỤC CÁC KÝ HIỆU, TỪ 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 Khai phá tri thức trong cơ sở dữ liệu KDD Knowledge Discovery in Databases Khai phá dữ liệu KPDL Data Mining Phân cụm dữ liệu PCDL Data Clustering Khai phá tri thức KPTT Knowledge Discovery vi DANH MỤC HÌNH VẼ Hình 1.2: Quá trình khai phá tri thức .....................................................................4 Hình 1.3: Qúa trình khai phá dữ liệu.......................................................................7 Hình 2.1: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ.................15 Hình 2.2: Khoảng cách Euclidean ........................................................................24 Hình 2.3: Bảng tham số .........................................................................................26 Hình 2.4: Ví dụ quá trình phân hoạch với k=3 ......................................................30 Hình 2.6: Ví dụ về một số hình dạng cụm dữ liệu được khám phá bởi K-means .....32 Hình 2.7: Các chiến lược phân cụm phân cấp .......................................................37 Hình 2.8: Ví dụ về kết quả phân cụm bằng thuật toán BIRCH. ..............................39 Hình 2.9. Khái quát thuật toán CURE ...................................................................41 Hình 2.10. Các cụm dữ liệu được khám phá bởi CURE ........................................41 Hình 2.11. Ví dụ thực hiện phân cụm bằng thuật toán CURE ...............................43 Hình 2.12: Các bước thuật toán CHAMELEON ....................................................44 Hình 2.13: Hình dạng các cụm được khám phá bởi DBSCAN ...............................45 Hình 2.14: Mật độ - đến được trực tiếp .................................................................46 Hình 2.15: Mật độ - đến được................................................................................47 Hình 2.16: Mật độ - liên thông ..............................................................................47 Hình 2.17: Cụm và nhiễu.......................................................................................48 Hình 2.18: Mô hình cấu trúc dữ liệu lưới ..............................................................52 Hình 2.19: Mô hình thuật toán STING...................................................................53 Hình 3.1: Kết quả phân cụm với Minpt = 3, Epxilon = 200000000 ......................60 Hình 3.2: Kết quả phân cụm trên dữ liệu thuộc tính và trên bản đồ .......................61 Hình 3.3: Màu của các cụm thể hiện trên bản đồ..................................................61 Hình 3.4: Giao diện chương trình Phân cụm dữ liệu bằng thuật toán DBSCAN ....68 Hình 3.5: Giao diện chương trình sau khi thực hiên phân cụm ..............................69 Hình 3.6: Kết quả phân cụm ..................................................................................70 1 MỞ ĐẦU Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong các lĩnh vực của đời sống, kinh tế, xã hội trong nhiều năm qua cũng đồng nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích lũy nhiều lên. Hơn nữa, các công nghệ lưu trữ và phục hồi dữ liệu phát triển một cách nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh nghiệp, đơn vị ngày càng nhiều thông tin tiềm ẩn phong phú và đa dạng. Mặt khác, trong môi trường cạnh tranh, người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với những lý do như vậy, các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật khai phá tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining). Khai phá tri thức trong cơ sở dữ liệu có thể được coi như quá trình tìm tri thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn (discovery of interesting, implicit, and previously unknown knowledge from large databases)[5] Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng trong những năm gần đây. Những vấn đề được quan tâm là phân lớp nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu, phần tử dị biệt,… Phân cụm cơ sở dữ liệu là một trong những phương pháp quan trọng trong quá trình tìm kiếm tri thức. Phân cụm là phương pháp học từ quan sát (learning from obversation) hay còn gọi là học không thầy (unupervised learning or automatic classfication) trong trí tuệ nhân tạo. Phân cụm đặc biệt hiệu quả khi ta không biết về thông tin của các cụm, hoặc khi ta quan tâm tới những thuộc tính của cụm mà chưa biết hoặc biết rất ít về những thông tin đó. Phân cụm được coi như một công cụ độc lập để xem xét phân bố dữ liệu, làm bước tiền xử lý cho các thuật toán khác. Việc phân cụm dữ liệu có rất nhiều ứng dụng như trong tiếp thị, sử dụng đất, bảo hiểm, hoạch định thành phố … Hiện nay, phân cụm dữ liệu là một hướng được nghiên cứu rất nhiều trong Tin học. Chính vì lý do đó mà em chọn đề tài “Nghiên cứu các kỹ thuật phân cụm dữ liệu và Ứng dụng” là hướng nghiên cứu chính cho luận văn của mình. 2 Nội dung chính của luận văn được trình bày trong 3 chương: Chương 1: Tổng quan về khai phá tri thức và khai phá dữ liệu. Trong chương này trình bày tổng quan về khai phá tri thức, khai phá dữ liệu; qui trình khai phá tri thức, khai phá dữ liệu; … Chương 2: Phân cụm và các kỹ thuật phân cụm. Trong chương này trình bày tổng quan về phân cụm dữ liệu, một số phương pháp phân cụm dữ liệu dữ liệu phổ biến 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 độ, phân cụm dựa trên lưới; trình bày một số giải thuật điển hình của mỗi phương pháp phân cụm; … Chương 3: Ứng dụng, triển khai bài toán với giải thuật DBSCAN Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận văn, đồng thời đưa ra các vấn đề nghiên cứu tiếp cho tương lai. Phần phụ lục trình bày một số modul chương trình cài đặt bằng thuật toán DBSCAN. Do thời gian nghiên cứu và trình độ có hạn, luận văn không tránh khỏi những hạn chế và thiếu sót. Em rất mong nhận được sự chỉ bảo, đóng góp ý kiến của các thầy thầy/ cô giáo cũng như bạn bè và đồng nghiệp. Em xin chân thành cảm ơn! 3 Chương 1. TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU 1.1. Giới thiệu chung Cách mạng khoa học kỹ thuật tạo ra bước nhảy vọt trong tất cả các lĩnh vực của đời sống kinh tế, xã hội, … Một thành công không thể không kể đến của cuộc cách mạng này là sự bùng nổ thông tin, khiến cho khối lượng thông tin mà con người thu thập và lưu trữ ngày một khổng lồ, kích thước của CSDL tăng một cách nhanh chóng. Trong những CSDL đó tiềm ẩn nhiều rất nhiều tri thức mà con người chưa khám phá ra được. Đứng trước núi dữ liệu khổng lồ thu thập được, việc khám phá tri thức và thông tin trở nên rất khó khăn. Chính vì lý do đó nhu cầu tìm kiếm tri thức trong khối CSDL đã nảy sinh, nhu cầu này ngày một cấp thiết và dẫn tới sự hình thành của một lĩnh vực mới – lĩnh vực khai phá dữ liệu (Data Mining) hay khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in databases - KDD). Khai phá tri thức trong cơ sở dữ liệu có thể được coi như quá trình tìm tri thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn (discovery of interesting, implicit, and previously unknown knowledge from large databases) Tuy mới ra đời nhưng khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng trong những năm gần đây. Những vấn đề được quan tâm là phân lớp nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu, phần tử dị biệt,… 1.2. Khai phá tri thức và quá trình khai phá tri thức 1.2.1. Khai phá tri thức Khai phá hay phát hiện tri thức trong các cơ sở dữ liệu là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp, hợp thức, khả ích, và có thể hiểu được. Còn khám phá dữ liệu là một bước trong qui trình khám phá tri thức gồm có các thuật toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các 4 mô hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và khai phá dữ liệu chính là tìm ra các mẫu và/hoặc các mô hình đang tồn tại trong các cơ sở dữ liệu nhưng nhưng vẫn còn bị che khuất bởi hàng núi dữ liệu. 1.2.2. Quá trình khai phá tri thức Việc khai phá tri thức thông thường có thể mô tả bằng sơ đồ các quy trình sau [4]: Hình 1.2: Quá trình khai phá tri thức Trong đó, mỗi bước là một quy trình có vai trò riêng và nhiệm vụ khác nhau, bao gồm: Bước thứ nhất: tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. Bước thứ hai: thu thập và xử lý dữ liệu thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ quy trình khai phá tri thức. Bước thứ ba: khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dưới các dữ liệu. 5 Bước thứ tư: hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện. Bước thứ năm: sử dụng tri thức đã được khám phá vào thực tế, các tri thức phát hiện được tích hợp chặt chẽ trong hệ thống. Tuy nhiên để sử dụng được các tri thức đó đôi khi cần đến các chuyên gia trong các lĩnh vực quan tâm vì tri thức rút ra có thể chỉ mang tính chất hỗ trợ quyết định hoặc cũng có thể được sử dụng cho một quá trình khai phá tri thức khác. Mặc dù được tóm tắt thành năm bước như trên, nhưng thực chất quá trình xây dựng và thực hiện việc khám phá tri thức không chỉ phải tuân theo các bước cố định mà các quá trình này còn có thể được lặp đi lặp lại ở một hoặc một số giai đoạn, lần sau sẽ hoàn thiện hơn lần trước và giai đoạn sau dựa vào kết quả của giai đoạn trước và cứ tiếp tục như thế sẽ làm cho quá trình khai phá và tìm kiếm dữ liệu ngày càng hoàn thiện hơn. 1.3. Khai phá dữ liệu 1.3.1. Khai phá dữ liệu Khai phá dữ liệu là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất nó là giai đoạn duy nhất tìm ra được thông tin mới. Việc khai phá dữ liệu còn được coi như là việc khai phá tri thức từ dữ liệu (knowlegde mining from databases), trích lọc tri thức (knowlegde extraction), phân tích dữ liệu - mẫu (data- partent analysis), khảo cứu dữ liệu (data archaeology), đào xới, nạo vét dữ liệu (data dredging). Khai phá dữ liệu (Data Mining) được định nghĩa là quá trình trích lọc các thông tin có giá trị ẩn trong lượng lớn dữ liệu được lưu trữ trong các CSDL hoặc các kho dữ liệu,… Khai phá dữ liệu cũng còn được coi là một quá trình tìm kiếm, khám phá ở nhiều góc độ để tìm ra các mối tương quan, các mối liên hệ dưới nhiều góc độ khác nhau nhằm tìm ra các mẫu hay các mô hình tồn tại bên trong cơ sở dữ liệu đang bị che khuất. Để trích rút các mẫu, mô hình tiềm ẩn có tính “tri thức” ta phải tìm và áp dụng các phương pháp, kỹ thuật khai phá sao cho các kỹ thuật và 6 phương pháp này phải phù hợp với tính chất, đặc trưng của dữ liệu và mục đích sử dụng. Tuy khai phá dữ liệu chỉ là một bước trong quá trình khám phá tri thức nhưng nó lại là bước tiên quyết, quan trọng và ảnh hưởng đến toàn bộ quá trình. Tóm lại, khai phá dữ liệu là một quá trình tìm kiếm thông tin “tri thức” tiềm ẩn trong cơ sở dữ liệu lớn, khổng lồ. Vì thế, có thể nói rằng hai thuật ngữ khám phá tri thức và khai phá dữ liệu là tương đương nếu nói ở khía cạnh tổng quan, còn nếu xét ở một góc độ chi tiết thì khai phá dữ liệu là một giai đoạn có vai trò quan trọng trong quá trình khám phá tri thức [3][4][9]. 1.3.2. Mục tiêu của khai phá dữ liệu Qua những nội dung đã trình bày ở trên, ta có thể hiểu một cách sơ lược rằng khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích, tiềm ẩn và mang tính dự báo trong các cơ sở dữ liệu lớn. Việc khai phá dữ liệu nhằm các mục đích chính như sau: - Khai thác những thông tin tiềm ẩn mang tính dự đoán từ những cơ sở dữ liệu lớn dựa trên các công cụ khai phá dữ liệu nhằm dự đoán những xu hướng trong tương lai nhằm giúp các đối tượng cần tri thức khai phá như: các tổ chức, doanh nghiệp, nhà nghiên cứu, …. để hỗ trợ việc đưa ra những quyết định kịp thời, được định hướng trên những tri thức được khám phá mang lại; - Thực hiện phân tích xử lý, tính toán dữ liệu một cách tự động cho mỗi quá trình xử lý dữ liệu để tìm ra tri thức. 1.3.3. Quá trình khai phá dữ liệu KPDL là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất, nó là giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong CSDL chủ yếu phục vụ cho mô tả và dự đoán. Dự đoán là thực hiện việc suy luận trên dữ liệu để đưa ra các dự báo nhằm phân tích tập dữ liệu huấn luyện và tạo ra một mô hình cho phép dự đoán các mẫu, mô hình mới chưa biết. Mô tả dữ là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con người có thể hiểu được. Quá trình KPDL bao gồm các bước như trong hình sau: 7 Hình 1.3: Qúa trình khai phá dữ liệu  Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết.  Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp.  Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền xử lý chúng sao cho thuật toán KPDL có thể hiểu được. Đây là một quá trình rất khó khăn, có thể gặp phải rất nhiều các vướng mắc như: dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi), v.v..  Thuật toán khai phá dữ liệu: Lựa chọn thuật toán KPDL và thực hiện việc PKDL để tìm được các mẫu có ý nghĩa, các mẫu này được biểu diễn dưới dạng luật kết hợp, cây quyết định... tương ứng với ý nghĩa của nó. 1.3.4. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp cận chính sau: 1.3.4.1. Phân lớp và dự đoán Hướng tiếp cận này làm 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 thời. Kỹ thuật này gồm có: phân lớp (classification), hồi quy (regression)... Là quá trình xếp một đối tượng vào một trong những lớp đã biết trước (ví dụ: phân lớp các bệnh nhân theo dữ liệu hồ sơ bệnh án, phân lớp vùng địa lý theo dữ liệu thời tiết...). Đối với hướng tiếp cận này thường sử dụng một số kỹ 8 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),... 1.3.4.2. Phân cụm dữ liệu Mục tiêu của phương pháp phân cụm dữ liệu là quá trình nhóm các điểm dữ liệu trong cơ sở dữ liệu thành các cụm sao cho những điểm dữ liệu trong cùng một cụm có độ tương đồng lớn và những điểm không cùng một cụm có sự tương đồng là rất nhỏ. Điểm mạnh của phân cụm dữ liệu là đưa ra được những cấu trúc có ích hoặc những cụm các đối tượng tìm thấy trực tiếp từ dữ liệu mà không cần bất kì một tri thức cơ sở nào. Giống như cách tiếp cận học máy, phân cụm dữ liệu được hiểu như là phương pháp “học không có thầy” (unsupervised learning). Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ (learning by example). Trong phương pháp này sẽ không thể biết kết quả các cụm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, cần có một chuyên gia để đánh giá các cụm thu được. Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web… Ngoài ra, phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu khác. 1.3.4.3. Phân lớp dữ liệu và hồi qui Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô hình: - Bước 1: một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn 9 được gọi là học có thầy (supervised learning) khác với phân cụm dữ liệu là học không có thầy (unsupervised learning). - Bước 2: sử dụng mô hình để phân lớp dữ liệu. Trước hết phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Phương pháp hồi qui khác với phân lớp dữ liệu ở chỗ, hồi qui dùng để dự đoán về các giá trị liên tục còn phân lớp dữ liệu thì chỉ dùng để dự đoán về các giá trị rời rạc. 1.3.4.4. Luật kết hợp Có rất nhiều kiểu luật có thể được phát hiện từ cơ sở dữ liệu nói chung. Ví dụ như luật đặc trưng, luật biệt số, luật kết hợp, luật về sự lệch hướng và sự phát triển. Phương pháp phát hiện luật kết hợp không gian cũng là một phương pháp quan trọng trong khám phá tri thức. Phương pháp phát hiện luật kết hợp đưa ra những luật về sự kết hợp giữa một hoặc nhiều thuộc tính đối với một hoặc nhiều thuộc tính khác. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin sinh học, giáo dục, viễn thông, tài chính và thị trường chứng khoán,... Khái niệm về luật kết hợp được phát biểu diễn như sau: một luật có dạng X Y (c%) với X và Y là tập các thuộc tính với độ tin cậy là c% được coi là luật kết hợp nếu có ít nhất c% đối tượng trong cơ sở dữ liệu đang xét thoả mãn: nếu điều kiện X được thoả mãn thì điều kiện Y cũng thoả mãn. Ví dụ, luật sau là luật kết hợp: is_a(x, school)  close (x, park) (80%). Luật trên thể hiện là: 80% trường học gần với công viên. Như vậy, có rất nhiều kiểu thuộc tính có thể tạo thành những luật kết hợp. Điều này khiến cho trong nhiều trường hợp số luật kết hợp tìm được vượt quá nhu cầu. Để hạn chế số luật kết hợp tìm được, người ta sử dụng khái niệm hỗ trợ tối thiểu  (minimum support) và độ tin cậy tối thiểu  (minimum confidence). Hai tham số sẽ giúp loại bớt các luật tìm thấy và chỉ để lại những luật thực sự có ích cho người sử dụng: 1. Hỗ trợ tối thiểu 10 Trong cơ sở dữ liệu lớn, có thể có rất nhiều luật giữa các đối tượng nhưng phần lớn các luật đó chỉ có thể áp dụng vào một số nhỏ các đối tượng hoặc độ tin cậy của luật là rất thấp. Chính vì thế mà phần lớn các luật không có ích với người sử dụng. Ví dụ, người sử dụng có thể không quan tâm nhiều tới mối quan hệ giữa nhà ở và trường học nếu luật đó chỉ áp dụng cho 5% số nhà ở trong khi người ta muốn ít nhất luật đó cũng phải được áp dụng cho trên 50% các ngôi nhà. Do đó chúng ta có thể lọc bỏ những luật kết hợp mà chỉ có thể áp dụng cho % đối tượng trong cơ sở dữ liệu. 2. Độ tin cậy tối thiểu Nếu một luật được đưa ra với mức độ tin cậy (độ tin cậy là tỉ lệ số đối tượng dữ liệu thoả mãn X và thoả mãn Y so với tổng số các đối tượng thoả mãn X) thấp thì cũng không có ý nghĩa ứng dụng. Ví dụ như luật: số người bị bệnh tim do ăn cá biển chỉ đúng 1% thì gần như không có ý nghĩa trong y học khi chuẩn đoán nguyên nhân bị bệnh tim của một bệnh nhân. Do đó, chúng ta sẽ loại bỏ những luật có độ tin cậy thấp mà chỉ giữ lại luật có độ tin cậy cao tỷ lệ đúng tối thiểu %. 1.3.4.5. Phân tích chuỗi theo thời gian Cũng tương tự như khai phá dữ liệu bằng 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 biến cố Y. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán bởi chúng có tính dự báo cao. 1.3.4.6. Khai phá dữ liệu sử dụng mạng Neural Mạng Neural là một phương pháp khai phá dữ liệu phát triển dựa trên cấu trúc toán học với khả năng học trên mô hình hệ thần kinh con người. Mạng Neural có thể đưa ra ý nghĩa các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết suất các mẫu và phát hiện xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được. Một trong những ưu điểm của mạng Neural là khả năng tạo ra các mô hình dự đoán do độ chính xác cao, có thể áp dụng cho nhiều các bài toán khác nhau, đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như: phân lớp, phân nhóm, mô hình hoá, dự báo… 11 Mẫu chiết suất bằng mạng Neural được thể hiện bằng một trong những nút đầu của mạng. Mạng Neural sử dụng các hàm số chứ không sử dụng các hàm biểu tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó. Đặc điểm của mạng Neural là không cần gia công dữ liệu nhiều, trước khi bắt đầu quá trình học như các kỹ thuật khác. Tuy nhiên, để có thể sử dụng mạng Neural có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như: - Mô hình mạng là gì? - Mạng cần bao nhiêu nút? - Số lớp ẩn sử dụng cho mạng là như thế nào? - Khi nào thì việc học dừng? Ngoài ra còn có nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu trước khi đưa vào mạng Neural để mạng có thể hiểu được. Mạng Neural được đóng gói với những thông tin trợ giúp của các chuyên gia đáng tin cậy và được họ đảm bảo các mô hình này làm việt tốt. Sau khi học, mạng có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học. 1.3.4.7. Khai phá dữ liệu sử dụng thuật giải di truyền Đây là phương pháp không chỉ thực hiện phát hiện tri thức mà còn phục vụ rất nhiều bài toán khác. Tư tưởng của thuật toán là áp dụng quy luật của sự chọn lọc tự nhiên. Người ta mô phỏng tập dữ liệu ban đầu bằng ký tự nhị phân và gọi là những quần thể xuất phát. Bằng các thao tác lai ghép, đột biến nhằm biến đổi quần thể gene ban đầu và loại đi một số gene, làm cho số lượng gene trong quần thể là không thay đổi. Một hàm thích nghi được xây dựng để xác định mức độ thích nghi ngày càng cao. Về mặt lý thuyết giải thuật di truyền cho lời giải tối ưu toàn cục (khác với phương pháp mạng Neural). Tuy nhiên, người ta cũng hạn chế lời giải với một mức độ thích nghi nào đó để hạn chế số lượng các bước xây dựng quần thể. Nói theo nghĩa rộng, giải thuật di truyền mô phỏng lại hệ thống tiến hoá trong tự nhiên, chính xác hơn là giải thuật chỉ ra tập các cá thể được hình thành, được ước lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào để loại bỏ. 12 Giải thuật di truyền là một giải thuật tối ưu hoá, được sử dụng rất rộng rãi trong việc tối ưu hoá các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng Neural. Sự kết hợp của nó với các giải thuật khai phá dữ liệu ở chỗ tối ưu hoá là cần thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất. 1.3.4.8. Khai phá dữ liệu sử dụng cây quyết định Phân lớp khai phá dữ liệu luật là cách tiếp cận quan trọng trong quá trình khai phá dữ liệu, với mục tiêu nhằm tạo ra một tập luật tương đối nhỏ có độ đúng đắn cao từ cơ sở dữ liệu lớn. Cây quyết định được cọi là phương pháp tiếp cận truyền thống cho phép phân lớp luật [10]. Cây quyết định đưa ra cách tiếp cận heuristic nhằm tìm kiếm các thuộc tính tốt nhất và dẫn đến kết quả cao nhất. Tuy nhiên, cây quyết định có một số hạn chế khi triển khai lựa chọn thuộc tính khi xây dựng cây. Hạn chế của cây quyết định là các trường hợp phân rã và tái tạo, vấn đề khi phân rã là khi cây quyết định cần phân chia dữ liệu nhiều lần để có thể nhận biết được toàn bộ dữ liệu mẫu. Vấn đề khi tái tạo là một cây con cần được xây dựng lại nhiều lần làm cho cây quyết định có độ sâu quá lớn và khó hiểu. Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên của các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá mô tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với giá trị của thuộc tính của đối tượng tới lá. Quá trình xây dựng cây quyết định là quá trình phát hiện ra các luật phân chia dữ liệu đã cho thành các lớp đã được định nghĩa. Trong thực tế, tập các cây quyết định có thể có đối với bài toán này rất lớn và rất khó có thể duyệt hết một cách tường tận. Có nhiều phương pháp xây dựng cây quyết định khi khai phá dữ liệu, đó là các phương pháp sử dụng các thuật toán CLS, ID3, C4.5,… và một phương pháp tương đối tiên tiến hiện nay và đang là tâm điểm được nghiên cứu là phương pháp xây dựng cây quyết định dựa trên phụ thuộc hàm. 13 1.3.5. Thách thức – khó khăn trong khai phá tri thức và khai phá dữ liệu KPTT và KPDL liên quan đến nhiều ngành, nhiều lĩnh vực trong thực tế, vì vậy các thách thức và khó khăn ngày càng nhiều, càng lớn. Một số các thách thức và khó khăn cần được quan tâm: Các cơ sở dữ liệu lớn, các tập dữ liệu cần xử lý có kích thước rất lớn, trong thực tế, kích thước của các tập dữ liệu thường ở mức tera-byte (hàng ngàn giga- byte). - Mức độ nhiễu cao hoặc dữ liệu bị thiếu - Số chiều lớn - 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 - Quan hệ giữa các trường phức tạp 1.3.6. Ứng dụng của khai phá dữ liệu Các kỹ thuật KDD có thể được áp dụng vào trong nhiều lĩnh vực, điển hình:  Thông tin thương mại: o Phân tích dữ liệu tiếp thị và bán hàng và thị trường; o Phân tích vốn đầu tư; o Quyết định cho vay vốn; o Phát hiện gian lận; o v.v..  Thông tin sản xuất: o Điều khiển và lập lịch; o Hệ thống quản lý; o Quản trị mạng; o Phân tích kết quả thí nghiệm; o V.v ...  Thông tin khoa học: o Dự báo thời tiết; o CSDL sinh học; 14 o Khoa học địa lý: tìm động đất; v.v..  Thông tin cá nhân  V.v… 1.3.7. Kết luận Khai phá dữ liệu là lĩnh vực đã và đang trở thành một trong những hướng nghiên cứu thu hút được sự quan tâm của nhiều chuyên gia về CNTT trên thế giới và được ứng dụng trong nhiều lĩnh vực khác nhau. Tại Việt Nam kỹ thuật này còn tương đối mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng. Trong những năm gần đây, rất nhiều các phương pháp và thuật toán mới liên tục được công bố. Điều này chứng tỏ những ưu thế, lợi ích và khả năng ứng dụng thực tế to lớn của khai phá dữ liệu. Trong chương này đã trình bày một cách tổng quan về khai phá tri thức và khai phá dữ liệu. 15 Chương 2. PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG PHÂN CỤM DỮ LIỆU 2.1. Giới thiệu Phân cụm là quá trình nhóm các điểm dữ liệu trong cơ sở dữ liệu thành các cụm sao cho những điểm dữ liệu trong cùng một cụm có độ tương đồng lớn và những điểm không cùng một cụm có sự tương đồng là rất nhỏ. Một cụm các đối tượng dữ liệu có thể xem như là một nhóm trong nhiều ứng dụng, ví dụ: mô hình về phân cụm các trường dựa trên tiêu chuẩn về thu nhập và số nợ. Cụm 1 là cụm những người thu nhập cao, số nợ nhiều. Cụm 2 gồm những người thu nhập cao nhưng nợ ít. Cụm 3 gồm những đối tượng thu nhập ít nhưng nợ nhiều. Hình 2.1: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ Quá trình phân cụm là quá trình tìm ra các đối tượng trong cơ sở dữ liệu một cách tự động. Không giống như phân lớp (clasification), phân cụm không cần những thông tin được xác định trước. Nói cách khác, phân cụm là phương pháp học từ quan sát (learning from obversation) hay còn gọi là học không thầy (unsupervised learning or automatic classfication) trong trí tuệ nhân tạo. Phân cụm đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta quan tâm tới các thuộc tính của cụm mà chưa biết hoặc biết rất ít về các thông tin đó. Đã có rất nhiều thuật toán cũng như hệ thống được phát triển cho bài toán phân cụm trong cơ sở dữ liệu lớn. Sự phát triển của lĩnh vực này đã được áp dụng 16 vào nhiều lĩnh vực ứng dụng như xử lý ảnh, nhận dạng, đánh giá kinh doanh…Sự đa dạng của thuật toán phân cụm là do sự khác nhau của những ứng dụng thực tế cũng dẫn tới những yêu cầu về dữ liệu khác nhau và đòi hỏi những thuật toán phân cụm khác nhau. Một trong những câu hỏi lớn đặt ra trong bài toán phân cụm là đo độ tương đồng không gian giữa các đối tượng dữ liệu (spatial similarity). Trong dữ liệu không gian thì độ đo tương đồng được xem như sự quan hệ về vị trí không gian giữa các đối tượng dữ liệu. Nói cách khác thì hai đối tượng dữ liệu được gọi là tương đồng nếu “khoảng cách không gian” giữa chúng là nhỏ. Một trong những phương pháp đo độ tương đồng giữa hai đối tượng là bằng nghịch đảo của hàm không tương đồng (dissimilarity function). Hàm không tương đồng, hàm dựa trên những thuộc tính không gian của các đối tượng dữ liệu như: toạ độ của các đối tượng, độ cao của các đối tượng… Trong nhiều trường hợp thì hàm không tương đồng được xem như là hàm khoảng cách không gian giữa các đối tượng như hàm khoảng cách Euclid, hàm khoảng cách Manhattan, hàm khoảng cách Minkowski… Bài toán phân cụm là quá trình nhóm một cơ sở dữ liệu thành những nhóm đối tượng dữ liệu phục vụ cho mục đích cụ thể của từng ứng dụng thực tế. Không có một thuật toán phân cụm nào là tốt nhất và thích hợp cho tất cả mọi ứng dụng mà với mỗi ứng dụng khác nhau thì người sử dụng phải lựa chọn ra một thuật toán phân cụm cụ thể thích ứng với ứng dụng đó. Kết quả đánh giá cho từng thuật toán cũng phụ thuộc vào những yêu cầu của từng ứng dụng. 2.2. Các ứng dụng của phân cụm Phân cụm dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng tại nhiều lĩnh vực như:  Quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lí… nhằm cung cấp thông tin cho quy hoạch đô thị; 17  Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm;  Thương mại: Tìm kiếm nhóm các khách hàng quan trọng có đặc trưng tương đồng và những đặc tả họ từ các bản ghi mua bán trong CSDL mua hàng;  Sinh học: Phân loại các gen với các chức năng tương đồng và thu được các cấu trúc trong mẫu;  Thư viện: Theo dõi độc giả, sách, dự đoán nhu cầu của độc giả…;  Bảo hiểm: : Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch vụ tài chính, dự đoán xu hướng của khách hàng, phát hiện gian lận tài chính;  WWW: Phân loại tài liệu, phân loại người dùng web. 2.3. Các yêu cầu về thuật toán phân cụm dữ liệu Theo các nghiên cứu cho thấy hiện này 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 CSDL. 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 CSDL, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng thuật toán phân cụm phù hợp. Vì vậy, phân cụm dữ liệu vẫn đang là một vấn đề khó và mở vì phải giải quyết nhiều vấn đề cơ bản 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à với kho dữ liệu hỗn hợp đang ngày càng tăng và đây cũng là một trong những thách thức lớn trong lĩnh vực KPDL. Vậy phân cụm dữ liệu là một thách thức trong lĩnh vực nghiên cứu vì những ứng dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc biệt của chúng. Do đặc thù của của cơ sở dữ liệu là lớn, phức tạp, và có dữ liệu nhiễu nên những thuật toán phân cụm được áp dụng phải thoả mãn những yêu cầu sau:[4][14]:  Thuật toán phải hiệu quả và thời gian chạy phải là tăng tuyến tính theo kích thước của dữ liệu 18  Thuật toán phải xử lý và áp dụng được với cơ sở dữ liệu nhiều nhiễu, phức tạp gồm cả dữ liệu không gian, phi không gian, dữ liệu số, phi số, kiểu nhị phân, dữ liệu định danh, hạng mục, thích nghi với kiểu dữ liệu hỗn hợp.  Thuật toán phải có khả năng xác định được những cụm với hình dáng bất kỳ bao gồm cả những cụm có hình dạng lồng nhau, cụm có hình dạng lõm, hình cầu, hình que…  Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào. Do các giá trị đầu vào thường ảnh hưởng rất lớn đến thuật toán phân cụm và rất phức tạp để xác định các giá trị vào thích hợp đối với các CSDL lớn.  Thuật toán phải thực hiện với mọi thứ tự đầu vào dữ liệu. Nói cách khác kết quả của thuật toán nên độc lập với dữ liệu đầu vào (Cùng một tập dữ liệu, khi đưa vào xử lý cho thuật toán PCDL 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 )  Thuật toán không đòi hỏi những tri thức về cơ sở dữ liệu từ người dùng  Thuật toán phải làm việc được với cơ sở dữ liệu chứa nhiều lớp đối tượng dữ liệu phức tạp và có tính chất khác nhau.  Thuật toán phải 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ố khác chiều nhau.  Thuật toán phải dễ hiểu, dễ cài đặt và khả thi: Người sử dụng có thể chờ đợi những kết quả phân cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể cần được giải thích ý nghĩa và ứng dụng rõ ràng. Việc nghiên cứu cách để một ứng dụng đạt được mục tiêu rất quan trọng có thể gây ảnh hưởng tới sự lựa trọn các phương pháp phân cụm. 2.4. Các kiểu dữ liệu trong phân cụm Trong phân cụm, các đối tượng dữ liệu thường được diễn tả dưới dạng các đặc tính hay còn gọi là thuộc tính ( Khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu“ được xem là tương đương với nhau). Các thuộc tính này là các tham số 19 để giải quyết vấn đề phân cụm và sự lựa chọn chúng có tác động đáng kể đến kết quả phân cụm. Phân loại các kiểu thuộc tính khác nhau là vấn đề cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các phương tiện thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Các thuật toán phân cụm thường sử dụng một trong hai cấu trúc dữ liệu sau: Ma trận dữ liệu (Data matrix, object-by-variable structure): là mảng n hàng, p cột, trong đó p là số thuộc tính của mỗi đối tượng. Mỗi hàng biểu diễn một đối tượng, các phần tử trong mỗi hàng chỉ giá trị thuộc tính tương ứng của đối tượng đó. Mảng được cho như sau: 11 1 1 1 1 ... ... ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... f p i if ip n nf np x x x x x x x x x                Ma trận phi tương tự (Dissimilarity matrix, object-by-object structure): là mảng n hàng, n cột. Phần tử d(i,j) chứa khoảng cách hay độ khác biệt giữa các đối tượng i và đối tượng j, d(i,j) là một số không âm, trong đó nếu d(i,j) xấp xỉ 0 thì hai đối tượng i và j là khá "gần" nhau, nếu d(i,j) càng lớn thì hai đối tượng i, j khá khác nhau. Do d(i,j) = d(j,i) = 0 nên ta có thể biểu diễn ma trận phi tương tự như sau: 0 (2,1) 0 (3,1) (3, 2) 0 ... ... ... ... ... ( ,1) ( , 2) ... ... 0 d d d d n d n                Phần lớn các thuật toán phân cụm sử dụng cấu trúc ma trận phi tương tự. Do vậy, nếu dữ liệu cần phân cụm được tổ chức dưới dạng ma trận dữ liệu thì cần biến đổi về dạng ma trận phi tương tự trước khi tiến hành phân cụm. Có hai đặc trưng để phân loại: kích thước miền và hệ đo [10]. Cho một CSDL D chứa n đối tượng trong không gian k chiều; x, y, z là các đối tượng thuộc D: 20 1 2 1 2 1 2( , ,..., ); ( , ,... ); ( , ,... )k k kx x x x y y y y z z z z   trong đó xi, yi, zi với i = 1,.., k là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng x, y, z; như vậy sẽ có các kiểu dữ liệu sau: 1. Kiểu dữ liệu dựa trên kích thước miền  Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm được, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác (ví dụ, các thuộc tính mầu, nhiệt độ hoặc cường độ âm thanh,…)  Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn, đếm được (ví dụ: các thuộc tính số,…) trường hợp đặc biệt của thuộc tính rời rạc là thuộc tính nhị phân mà miền giá trị chỉ có hai phân tử (ví dụ: Yes/No, True/False, On/Off..) 2. Kiểu dữ liệu dựa trên hệ đo  Thuộc tính định danh: Là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó có miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử. Nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x ≠ y hoặc x =y.  Thuộc tính có thứ tự: Là thuộc tính định danh nhưng có thêm tính thứ tự nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x< y.  Thuộc tính khoảng: để đo các giá trị theo xấp xỉ tuyến tính, với thuộc tính khoảng có thể xác định một thuộc tính là đứng trược hoặc đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi > yi thì có thể nói x cách y một khoảng xi - yi tương ứng với thuộc tính thứ i. Việc lựa chọn đơn vị đo cho các thuộc tính cũng ảnh hưởng đến chất lượng phân cụm. Nếu đơn vị độ đo của một thuộc tính càng được chia nhỏ, thì khoảng cách xác định của thuộc tính đó càng lớn và ảnh hưởng nhiều hơn đến kết quả phân cụm. Để tránh phụ thuộc vào việc lựa chọn đơn vị đo, dữ liệu cần được chuẩn hóa. Việc chuẩn hóa sẽ gán cho tất cả các thuộc tính một trọng số bằng nhau. Tuy nhiên, 21 trong nhiều trường hợp người sử dụng có thể thay đổi trọng số cho các thuộc tính ưu tiên. Để chuẩn hóa các độ đo, một cách làm phổ biến là biến đổi các thuộc tính về dạng không có đơn vị đo. Giả sử đối với các thuộc tính f, ta thực hiện như sau: - Tính độ lệch trung bình: 1 2 1 ( ... )f f f f f nf fS x m x m x mn        trong đó 1 ,...f nfx x là giá trị thuộc tính f của n phần tử dữ liệu, và fm là giá trị trung bình của f, được cho như sau: 1 2 1 ( ... )f f f nfm x x xn     - Độ đo được chuẩn hóa: if f if f x m z S    Thuộc tính nhị phân là thuộc tính có hai giá trị là 0 và 1.  Thuộc tính tính tỷ lệ: Là thuộc tính khoảng nhưng được xác định một cách tương đối so với điểm mốc. Trong các thuộc tính trình bày ở trên, thuộc tính định danh và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục, còn thuộc tính khoảng cách và thuộc tính tỷ lệ được gọi là thuộc tính số. Đặc biệt, còn có dữ liệu không gian là loại dữ liệu có thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên quan đến không gian chứa đựng các đối tượng (ví dụ: thông tin về hình học, Quan hệ metric, Quan hệ hướng, …) Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc. - Dữ liệu không gian liên tục: Bao chứa một vùng không gian. - Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều chiều và cho phép xác định khoảng cách giữa các đối tượng dữ liệu trong không gian. 2.5. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu 1. Khái niệm tương tự, phi tương tự 22 Khi các đặc tính của dữ liệu được xác định, phải tìm cách thích hợp để xác định “khoảng cách” giữa các đối tượng hay là phép đo tương tự dữ liệu. Đây là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ tương tự hoặc là để tính độ phi tương tự giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống nhau giữa các đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ nghịch với hàm tính độ tương tự. Độ tương tự hoặc phi tương tự có nhiều cách để xác định, chúng thường được đo bằng khoảng cách giữa các đối tượng. Tất cả các cách đo độ tương tự đều phụ thuộc vào kiểu thuộc tính mà con người phân tích. Ví dụ, thuộc tính hạng mục thì không sử dụng độ đo khoảng cách mà sử dụng một hướng hình học của dữ liệu. Tất cả các độ đo dưới đây được xác định trong không gian metric. Bất kỳ một metric nào cũng là một độ đo, nhưng điều ngược lại không đúng. Để tránh sự nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tương tự hoặc hàm tính độ phi tương tự. Một không gian metric là một tập trong đó có xác định “khoảng cách” giữa từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học. Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) các đối tượng dữ liệu trong CSDL D đề cập ở trên được gọi là một không gian metric nếu: - Với mỗi cặp phần tử x, y thuộc X đều xác định theo một quy tắc nào đó, một số thực δ(x,y) được gọi là khoảng cách giữa x và y. - Quy tắc nói trên thỏa mãn hệ tính chất sau: (i) δ(x,y) > 0 nếu x ≠ y; (ii) δ(x,y) = 0 nếu x= y ; (iii) δ(x,y) = δ(y,x) với mọi x,y ; (iv) δ(x,y) ≤ δ(x,z) + δ(z,y) ; Hàm δ(x,y) được gọi là một metric của không gian. Các phần tử của X được gọi là các điểm của không gian này. 2. Thuộc tính khoảng 23 Một thành phần quan trọng trong thuật toán phân cụm là phép đo khoảng cách giữa hai điểm dữ liệu. Nếu thành phần của vectơ thể hiện dữ liệu thuộc trong cùng một đơn vị giống nhau thì nó tồn tại khoảng cách Euclidean có thể xác định được nhóm dữ liệu tương tự. Tuy nhiên, không phải lúc nào khoảng cách Euclidean cũng cho kết quả chính xác. Tuy nhiên chú ý rằng đây không phải vấn đề đồ thị: vấn đề phát sinh từ công thức toán học được sử dụng để kết hợp khoảng cách giữa các thành phần đơn đặc tính dữ liệu vectơ vào trong một độ đo khoảng duy nhất mà có thể được sử dụng cho mục đích phân cụm: các công thức khác nhau dẫn tới những cụm khác nhau. Các thuật toán cần có các phép đo khoảng cách hoặc độ tương tự giữa hai đối tượng để thực hiện phân cụm. Kiến thức miền phải được sử dụng để để trình bày rõ ràng phép đo khoảng thích hợp cho mỗi ứng dụng. Hiện nay, phép đo có nhiều mức độ khách nhau tùy theo từng trường hợp.  Khoảng cách Minkowski được định nghĩa như sau :   ;1,, /1 1          qyxyxdist qn i q iiq Trong đó x, y là hai đối tượng với n là số lượng thuộc tính, 1 2( , ,..., )nx x x x và 1 2y = (y , ,..., );ny y dist là kích thước của dữ liệu.  Khoảng cách Euclidean:     ;, 2 1    n i iiq yxyxdist là khoảng cách giữa hai đối tượng trong trường hợp đặc biệt q = 2.  Khoảng cách Manhattan :   ;, 1          n i iiq yxyxdist là khoảng cách trung bình giữa hai đối tượng trong trường hợp đặc biệt q=1.  Khoảng cách Chebychev :   ;max, 1 iini yxyxdist   24 Trong trường hợp q = ∞, hữu ích để định nghĩa các đối tượng phi tương tự nếu chúng khác nhau chỉ trong một kích thước biến đổi.  Bình phương khoảng cách Euclidean.     2 1 ,    n i iiq yxyxdist (1)  Tỉ lệ khác nhau. Giả sử các biến là tuyệt đối.     , /i idist x y Number x y i  (2) Khoảng cách Euclidean được sử dụng phổ biến nhất để đo độ tương tự của khoảng cách Minkowski. Giả sử có hai trường hợp C1 và C2 có các biến liên tục x và y, lấy lần lượt các giá trị (x1, y1) và (x2, y2) tương ứng, có thể vẽ đồ thị hai trường hợp trong không gian x-y (Hình 2.2) : Hình 2.2: Khoảng cách Euclidean Tuy nhiên không có nguyên tắc tổng quát để chọn phép đo áp dụng cho bất cứ bài toán nào. Một cách đơn giản để đo độ tương tự giữa các nhóm trong khung tương tự bằng cách thay thế nhóm cho thuộc tính thứ i của đối tượng đo chẳng hạn như khoảng cách Euclidean, khoảng cách Manhattan, hoặc bình phương Mahalanobis. Ví dụ, Giả sử rằng nhóm A có vectơ trung bình A  anaa xxx ,...,, 21 và nhóm B có vectơ trung bình B  bnbb xxx ,...,, 21 , thì cách đo bằng khoảng cách Euclidean giữa hai nhóm có thể được định nghĩa là: y x C2(x2, y2) C1(x1, y1) d12 25     2/1 1 2 ,          n i biai xxBAdist (3) Cách tiếp cận khác để khoảng cách giữa phần tử gần nhất hoặc phần tử xa nhất. Cách tiếp này sử dụng các thuật toán phân cụm phân cấp chẳng hạn như liên kết đơn và liên kết đầy đủ. Vấn đề chính với hai cách tiếp cận này giống nhau là không cảm nhận được mâu thuẫn định lượng và không tính toán cho các yếu tố của các phần tử trong một nhóm. Cách tiếp cận khác, là trung bình nhóm, có thể sử dụng phép đo tương tự giữa các nhóm. Cách tiếp cận này, sự giống nhau giữa các nhóm được đo bằng cách lấy giá trị trung bình cả tất cả các phép đo giữa các đối tượng cho từng cặp đối tượng trong các nhóm khác nhau. Ví dụ, trung bình phi tương tự giữa nhóm A và B có thể được định nghĩa là :     nyxdBAdist x bn i n j ii /,, 1 1           (4) trong đó, n là tổng số các đối tượng cùng cặp, n = nx  ny, nx và ny lần lượt là số các đối tượng trong đối tượng xi và yi, d(xi, yi) là phi tương tự của một cặp đối tượng xi và yi, xi A, yi  B. Hàm phi tương tự có thể dễ dàng chuyển đổi sang hàm tương tự bằng cách thay đổi cho nhau. 3.Thuộc tính nhị phân Tất cả các phép đo được định nghĩa ở trên là đa số thích hợp cho các biến liên tục. Cho các biến danh nghĩa, “phép đo khoảng cách” là 0 nếu các trường hợp có cùng giá trị danh nghĩa, và 1 nếu các trường hợp có các giá trị danh nghĩa khác nhau, hoặc với độ đo tương tự 1 (nếu các trường hợp có cùng giá trị danh nghĩa) và 0 (nếu không giống nhau). Do đó nếu xem xét p biến định danh, có thể đánh giá độ tương tự của các trường hợp bằng số các biến mà có giá trị giống nhau. Nói chung định nghĩa với một biến nhị phân mới từ mỗi biến danh nghĩa, bằng việc nhóm các nhãn danh nghĩa thành hai lớp, một nhãn là 1, nhãn khác là 0. Xây dựng và xem xét bảng ngẫu 26 nhiên các sự kiện có thể xảy ra và định nghĩa các thuộc tính của đối tượng x, y bằng các biến số nhị phân 0 và 1. y 1 0 1 a b a+b x 0 c d c+d a+c b+d p=a+b+c+d Hình 2.3: Bảng tham số Trong đó: a là tổng số các thuộc tính có giá trị 1 trong hai đối tượng x, y b là tổng số các thuộc tính có giá trị 1 trong x và giá trị 0 trong y c là tổng số các thuộc tính có giá trị 0 trong x và giá trị 1 trong y d là tổng số các thuộc tính có giá trị 0 trong hai đối tượng x, y p là tổng tất cả các thuộc tính của hai đối tượng x, y Các phép đo độ tương tự của các trường hợp với dữ liệu thuộc tính nhị phân được thực hiện bằng các cách sau:  Hệ số đối sánh đơn giản: ( , ) a dd x y p   ; cả hai đối tượng có vai trò như nhau, nghĩa là chúng đối xứng và có cùng trọng số.  Hệ số Jaccard: ( , ) ad x y a b c    ; tham số này bỏ qua số các đối sánh 0-0. Công thức này sử dụng trong trường hợp mà trọng số của các thuộc tính có giá trị 1 của đối tượng dữ liệu cao hơn nhiều so với các thuộc tính có giá trị 0. Như vậy thuộc tính nhị phân ở đây là không đối xứng.   p ayxd ,   cb ayxd  , 27   cba ayxd   2 , Các giá trị được định nghĩa trong khoảng [0, 1] và có thể biến đổi sang độ đo phi tương tự bằng biểu thức: ( , ) 1 ( , ).ds x y d x y  4. Thuộc tính định danh Độ đo phi tương tự giữa hai đối tượng x và y được định nghĩa như sau:   p mpyxd , trong đó, m là số thuộc tính đối sánh tương ứng trùng nhau, p là tổng số các thuộc tính. 5. Thuộc tính có thứ tự Phép đo độ phi tương tự giữa các đối tượng dữ liệu với thuộc tính thứ tự được thực hiện như sau: Giả sử i là thuộc tính thứ tự có Mi giá trị (Mi là kích thước miền giá trị):  Các trạng thái Mi được sắp xếp thứ tự như nhau: [1…Mi], có thể thay thế mỗi giá trị của thuộc tính bằng giá trị cùng loại ri với ri  {1…Mi}.  Mỗi thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy phải chuyển đổi chúng về cùng miền giá trị [0, 1] bằng cách thực hiện phép biến đổi sau cho mỗi thuộc tính:     1 1    i f ij i M rz  Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với các giá trị  z ji , đây chũng chính là độ phi tương tự của thuộc tính có thứ tự. 6. Thuộc tính tỷ lệ Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ. Một trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính xi, ví dụ qi = 28 log(xi), qi đóng vai trò như thuộc tính khoảng. Phép biến đổi logarit này thích hợp trong trường hợp các giá trị của thuộc tính là số mũ. Trong thực tế, khi tính độ tương tự dữ liệu, chỉ xem xét một phần các thuộc tính đặc trưng đối với các kiểu dữ liệu hoặc là đánh trọng số cho tất cả các thuộc tính dữ liệu. Trong một số trường hợp, loại bỏ đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hóa chúng, hoặc gán trọng số cho mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Các trọng số này có thể sử dụng trong các độ đo khoảng cách trên, ví dụ với mỗi thuộc tính dữ liệu đã được gán trọng số tương ứng wi (1 ≤ i ≤ k), độ tương đồng dữ liệu được xác định như sau:       n i iii yxwyxd 1 2, Có thể chuyển đổi giữa các mô hình cho các kiểu dữ liệu trên, ví dụ như dữ liệu kiểu hạng mục có thể chuyển đổi thành dữ liệu nhị phân hoặc ngược lại. Giải pháp này rất tốn kém về chi phí tính toán, do vậy, cần phải cân nhắc khi áp dụng cách thức này. Tóm lại, tùy từng trường hợp dữ liệu cụ thể mà có thể sử dụng các mô hình tính độ tương tự khác nhau. Việc xác định độ tương đồng dữ liệu thích hợp, chính xác đảm bảo khách quan là rất quan trọng, góp phần xây dựng thuật toán PCDL có hiệu quả cao trong việc đảm bảo chất lượng cũng như chi phí tính toán. 2.6. Các hướng tiếp cận của bài toán phân cụm dữ liệu Các phương pháp phân cụm dữ liệu được phân thành các nhóm: phương pháp phân hoạch (partitioning), phương pháp phân cấp (hierarchical), phương pháp dựa trên mật độ (density-based), phương pháp dựa trên lưới (grid-based). Trong khuôn khổ luận văn này chỉ giới thiệu một vài thuật toán đại diện cho mỗi phương pháp. 2.6.1. Phương pháp phân hoạch (Partitioning Methods) Thuật toán phân hoạch là một thuật toán phân cụm có từ rất lâu và khá phổ biến trước khi xuất hiện lĩnh vực khai phá dữ liệu [15]. Phân cụm không thứ bậc hoặc phân cụm theo phân hoạch (nonhierarchy or partition clustering) chia cơ sở 29 dữ liệu bằng cách xác định trước các đối tượng đại diện (đối tượng nhân) của các cụm. Kế tiếp mỗi đối tượng dữ liệu sẽ được đưa vào cụm mà khoảng cách từ đối tượng dữ liệu đến đối tượng đại diện của cụm là nhỏ nhất. Sau mỗi bước thì đối tượng đại diện của mỗi cụm có thể được xác định lại dựa vào các đối tượng dữ liệu thuộc cụm đó. Mặc dù biểu diễn các cụm dữ liệu khác nhau, tuy nhiên các thuật toán đều có cách tiếp cận chung khi tính toán các giải pháp. Ý tưởng của phương pháp phân hoạch như sau: Cho tập D gồm n đối tượng, và một tham số đầu vào k được xác định bởi người dùng. Thuật toán phân hoạch sẽ chọn k đối tượng đại diện cho k cụm (k đối tượng đại diện có thể được chọn ngẫu nhiên hoặc theo một tiêu chuẩn của người sử dụng). Với một đối tượng dữ liệu q sẽ được đưa vào cụm có đối tượng đại diện gần với q nhất. Sau đó, đối tượng đại diện của mỗi cụm sẽ được tính lại dựa vào những điểm dữ liệu thuộc cụm đó. Thông thường thì đối tượng đại diện được xác định sao cho khoảng cách từ đối tượng đại diện đến điểm xa nhất là nhỏ nhất có thể được. Hình dưới mô tả quá trình phân hoạch với k=3. Khởi tạo bởi hình A với 3 đối tượng đại diện là 3 điểm đậm được lựa chọn ngẫu nhiên. Kế tiếp mỗi đối tượng dữ liệu được đưa vào cụm mà khoảng cách từ điểm đó tới đối tượng đại diện của cụm là nhỏ nhất. Với mỗi cụm tìm đối tượng đại diện cho cụm đó (lấy đối tượng dữ liệu mới là điểm trung bình của tất cả các đối tượng dữ liệu thuộc cụm). Quá trình trên được lặp lại cho đến khi các đối tượng đại diện của tất cả các cụm là không thay đổi. 30 Hình 2.4: Ví dụ quá trình phân hoạch với k=3 Mô hình thuật toán phân cụm phân hoạch Đầu vào: Số cụm k và CSDL D gồm n đối tượng. Đầu ra: tập các cụm. Partition(D, k); 1. Chọn ngẫu nhiên k tâm bất kỳ O0. Đặt i = 0. 2. Với mỗi điểm dữ liệu p  D thì tìm đối tượng đại diện gần nhất và đưa p vào cụm đó. 3. Tính lại đối tượng đại diện của các cụm Oi+1 dựa vào các điểm dữ liệu thuộc cụm. 4. Nếu Oi+1 = Oi thì dừng lại. Trong trường hợp ngược lại i = i+1 và quay lại 2. Oi = {o1(i), o2(i),…, ok(i)} là tập các đối tượng đại diện của k cụm. Với phương pháp này, số cụm được thiết lập là đặc trưng được lựa chọn trước. Phương pháp phân hoạch thích hợp với bài toán tìm các cụm trong không gian 2D. Ngoài ra, phương pháp xem xét đến khoảng cách cơ bản giữa các điểm dữ liệu để xác định chúng có quan hệ gần nhau, hoặc không gần nhau hay không có quan hệ. Nhược điểm của phương pháp này là đòi hỏi phải đưa vào tham số k và không xử lý trên bộ dữ liệu thuộc cụm có hình dạng phức tạp hoặc mật độ phân bố dày đặc. Thêm vào đó, thuật toán có độ phức tạp tính toán lớn khi cần xác định kết quả tối ưu. 31 Các thuật toán trong phương pháp phân hoạch: k-means, PAM (Partitioning Around Medoids), CLARA (Clustering LARge Application), CLARANS (Clustering Large Applications based upon RANdomized Search),... Dưới đây trình bày 3 trong số các thuật toán điển hình trong phương pháp phân hoạch. 2.6.1.1. Thuật toán k-means Thuật ngữ “k-means” được J. MacQueen giới thiệu vào năm 1967 và phát triển dựa trên ý tưởng của H.Steinhaus đề xuất năm 1956. Thuật toán này sử dụng giá trị trung bình (mean) của các đối tượng trong cụm làm tâm của cụm đó. Tư tưởng chính của thuật toán K-Means là tìm cách phân nhóm các đối tượng đã cho vào K cụm (K là số các cụm được xác đinh trước, K nguyên dương) sao cho tổng bình phương khoảng cách giữa các đối tượng đến tâm cụm là nhỏ nhất. Tổng bình phương khoảng cách giữa các đối tượng đến tâm cụm còn gọi là hàm tiêu chuẩn (criterion function) được tính bởi công thức: 2 1     k i iCx imxE Trong đó, x là một điểm, mi là giá trị trung bình của cụm Ci. Thuật toán k-means chi tiết như sau: Đầu vào: Số các cụm k, cơ sở dữ liệu gồm n đối tượng Đầu ra: Tập k cụm mà có giá trị hàm tiêu chuẩn E nhỏ nhất. Phương pháp: B1: Khởi tạo k điểm trung tâm cụm bằng cách chọn k đối tượng tùy ý B2: Lặp các bước B2.1. Gán mỗi đối tượng vào cụm có trung tâm gần đối tượng đó nhất, hình thành một tập các cụm mới B2.2. Tính lại giá trị E của mỗi cụm theo các đối tượng mới thu được sau bước B2.1. B3. Thuật toán dừng khi giá trị E không thay đổi. 32 Tại bước 1, thực hiện chọn ngẫu nhiên k điểm từ cơ sở dữ liệu các đối tượng cần phân cụm là điểm tâm cho k cụm. Sau đó, thực hiện lần lượt tính khoảng cách từ điểm tâm tới các điểm, so sánh xem giá trị nào nhỏ hơn (có nghĩa gần tâm hơn) thì gán điểm đó vào cụm chứa điểm tâm đó. Tiếp đến tính lại giá trị hàm tiêu chuẩn E, nếu giá trị mới nhỏ hơn giá trị cũ thì thay đổi giá trị E. Thuật toán lặp lại các bước cho đến khi giá trị E không thay đổi nữa. Để tính khoảng cách giữa điểm tâm tới các điểm, dùng độ đo khoảng cách Euclidean. Thuật toán k-means chỉ áp dụng khi trung bình của một cụm được xác định. Hình 2.6: Ví dụ về một số hình dạng cụm dữ liệu được khám phá bởi K-means Nhược điểm của thuật toán là chỉ áp dụng với dữ liệu có thuộc tính số và khám phá các cụm có dạng hình cầu, không thích hợp với việc tìm các cụm có hình dáng không lồi hay các cụm có hình dáng khác xa nhau, nhạy cảm với các phần tử ngoại lai, phần tử nhiễu, phần tử cận biên cụm. Với các phần tử như vậy có thể gây ảnh hưởng đáng kể đến giá trị trung bình. Việc chọn lựa tập điểm trung tâm ban đầu cũng ảnh hưởng nhiều đến chất lượng cụm sinh ra [14]. Trên thực tế chưa có một giải pháp tối ưu nào để chọn các tham số đầu vào, giải pháp thường được sử dụng nhất là thử nghiệm với các giá trị đầu vào k khác nhau rồi sau đó chon giải pháp tốt nhất. 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K=2 Chọn k đối tượng trung tâm tùy ý Gán mỗi đối tượng vào các cụm Cập nhật lại trọng tâm Gán lại các đối tượng Cập nhật lại trọng tâm Gán lại các đối tượng 33 Thuật toán k-means được xếp vào lớp bài toán NP, do vậy để phát triển thuật toán này người ta kết hợp với phỏng đoán (heuristic). Trong quá trình xử lý của thuật toán, dữ liệu được tổ chức theo cây K-D tree để tăng tốc độ tìm kiếm. Thuật toán này được hỗ trợ trong hầu hết các công cụ phân cụm phổ biến dùng trong các ứng dụng khoa học và công nghiệp. 2.6.1.2. Thuật toán k-medoids Mỗi cụm được biểu diễn bởi một điểm/ đối tượng thuộc cụm đó. Đây là giải pháp đơn giản vì phù hợp với mọi kiểu thuộc tính. Khi một đối tượng được chọn làm trọng tâm của cụm, cụm được định nghĩa là tập con các điểm gần điểm trọng tâm đó. Mục tiêu đặt ra là tính khoảng cách trung bình hoặc sử dụng hàm tính độ tương tự bất kỳ giữa các đối tượng và trọng tâm của nó. Các bước trong thuật toán k-medoids gần giống như thuật toán k-means, trong đó giá trị k chính là k đối tượng được chọn ngẫu nhiên làm trọng tâm cụm. Phiên bản điển hình cho k-medoids là thuật toán PAM (Partitioning Around Medoids) gồm các bước như sau Phương pháp: B1: Lấy ngẫu nhiên k đối tượng tùy ý làm trọng tâm của k cụm (n>k) B2: Lặp các bước B2.1. Gán các đối tượng vào cụm mà có độ tương tự gần với trọng tâm của cụm đó B2.2.. Chọn ngẫu nhiên đối tượng O’ thuộc n-k B2.3. Tính tổng chi phí S để chuyển từ điểm trọng tâm cũ sang O’ B2.4. Nếu S<0 thì chuyển điểm trọng tâm sang O’ B5. Thuật toán dừng khi tập các đối tượng k không thay đổi. Tại bước 2.1, để tính độ đo tương tự có thể dùng khoảng cách Euclidean, Manhattan hay Minkowski. Thuật toán này chú tâm đến việc tìm cách thay thế các đối tượng trọng tâm ban đầu bằng n-k đối tượng còn lại. Nếu không có sự thay thế xảy ra, thuật toán dừng. Bước 2.3 tính độ lệch E giữa trọng tâm cụm với đối tượng 34 thuộc cụm đó. Do vậy, thuật toán này thực hiện việc tính E là n-k lần tương ứng với việc so sánh với n-k điểm, nên thuật toán thực hiện tốn thời gian nếu số đối tượng cần phân cụm lớn. Để cải tiến nhược điểm của thuật toán PAM, thuật toán CLARA (Clustering LARge Application) ra đời vào năm 1990 bởi Kaufman và Rousseeuw [15]. Thay vì thực hiện so sánh với n-k đối tượng còn lại, CLARA chỉ thực hiện trên một phần dữ liệu mẫu được chọn từ tập dữ liệu ban đầu. CLARA chọn từng nhóm đối tượng, sau đó dùng thuật toán PAM trên nhóm đối tượng đó. Kết quả trả về là các cụm tốt nhất. Nhược điểm của CLARA nếu mẫu được chọn không chứa k điểm trọng tâm tốt nhất thì CLARA không đưa ra cách phân cụm tốt nhất. Năm 1994, Raymond T. Ng và Jiawei H. giới thiệu thuật toán CLARANS và đến năm 2002 thuật toán này được công bố là một phương pháp gom cụm hiệu quả trên cơ sở dữ liệu lớn, cơ sở dữ liệu không gian [15]. 2.6.1.3. Thuật toán CLARANS CLARANS (Clustering Large Application Based on RANDOM Search) [19]. CLARANS phân cụm dựa trên việc tìm kiếm ngẫu nhiên các tập gồm k đối tượng để làm tâm của k cụm. Đối tượng dữ liệu nhân (medoid) là đối tượng dữ liệu thể hiện “tâm“ của đối tượng dữ liệu thuộc cụm đó. Tại mỗi bước tìm kiếm sẽ xác định được độ tốt của nó và giữ lại kết quả tìm kiếm tốt nhất. Các tác giả đã thực hiện việc tìm kiếm và đánh giá độ tốt của phép tìm kiếm bằng cách xây dựng một đồ thị tìm kiếm. Đồ thị tìm kiếm có dạng như sau: với n đối tượng cần chia làm k cụm thì đồ thị được đặt tên là Gn,k. Mỗi đỉnh của Gn,k là một tập gồm k đối tượng   k1 mm O,....,O , ngụ ý rằng mỗi đối tượng Omi là tâm của một cụm. Tập đỉnh của đồ thị là   CSDLO,...,O|O,....,O k1k1 mmmm  . Hai đỉnh của đồ thị được gọi là kề nhau nếu chúng có khác nhau duy nhất một đối tượng. Nghĩa là S1 =  k1 mm O,...,O và S2 =  11 ww O,...,O thì S1 và S2 được gọi là kề nhau nếu và chỉ nếu |S1  A2| = k - 1. Như vậy mỗi đỉnh có k(n-k) đỉnh kề. Theo cách định nghĩa đồ thị thì mỗi đỉnh là một phương án chọn k điểm tâm của k cụm, gán mỗi đỉnh của đồ thị với một trọng số là tổng khoảng của tất cả các đối tượng đến tâm tương ứng. Dùng trọng số này để đánh giá độ tốt của mỗi phương án. 35 Thuật toán yêu cầu hai tham số từ người sử dụng: Là numlocal (số cục bộ địa phương cần tìm) và maxneighbor (số đỉnh kề cần xét). Trong đó Maxneighbor là số đối tượng hàng lân cận của một nút trong đồ thị sẽ được kiểm tra và Numlocal là số lớn nhất của các điểm cực tiểu địa phương sẽ thu thập. Quá trình thực hiện của thuật toán như sau:CLARANS khởi tạo bằng cách chọn một tập điểm nhân ngẫu nhiên. Kế tiếp thuật toán kiểm tra một trường hợp trong đối tượng lân cận của một tập đối tượng nhân vừa chọn. Nếu một tập điểm nhân lân cận đang được xét tốt hơn so với tập điểm nhân đang có dựa trên đánh giá về sự khác nhau giữa hai tập điểm thì thay tập điểm nhân cũ bởi tập điểm nhân đang xét. Quá trình trên được thực hiện cho đến khi điều kiện về Maxneighbor được thoả mãn. Trong trường hợp ngược lại, tập điểm đạt được gọi là tập điểm cực tiểu địa phương. Kết quả đưa ra là tập cực tiểu địa phương tốt nhất trong tập các điểm các tập cực tiểu địa phương thu được. Thuật toán CLARANS được mô tả như sau: CLARANS (Numlocal, Maxneighbor, D) Buil (D, Gn,k); mincost = ; BestNode = nil; For i =1 to Numlocal do Begin Current = Get_random(Gn,k); j = 1; While (j <= maxneighbor) do Begin S = Get_random(Neighbor(Current)); if (cost(S) < cost (Current)) then Begin Current = S; j = 0; End; j = j+1; 36 End; If (cost (Current) < cost (BestNode) then BestNode = Current; End; Giá trị Maxneighbor ảnh hưởng tới chất lượng của các cụm được tạo ra. Với giá trị Maxneighbor đủ lớn thì kết quả phân cụm có hiệu quả gần với PAM. Tham số Numlocal ảnh hưởng lớn tới thời gian chạy. Những thí nghiệm đánh giá nếu nhận thấy rằng chất lượng của cụm nhận được là tốt trong trường hợp Numlocal có giá trị bằng 2 và nếu với giá trị Numlocal lớn hơn thì thuật toán CLARANS cũng không đưa ra được kết quả tốt hơn. Vì thế, thông thường thì Numlocal được đặt là 2 trong các trường hợp sử dụng CLARANS. Hạn chế của CLARANS là sự thiếu hiệu qủa. Vòng lặp bên trong của thuật toán cần thời gian O(N) khi duyệt qua toàn bộ cơ sở dữ liệu. Mặc dù, tác giả đã đưa ra thời gian chạy của CLARANS là xấp xỉ tuyến tính nhưng trong thực tế, thời gian cho mỗi bước tìm đã là O(KN)2 và tổng thời gian của toàn bộ quá trình chia cho thời gian này ít nhất là hàm mũ 2. Ngoài ra, có thể những bước tìm kiếm cực tiểu địa phương không tìm được cực tiểu địa phương thực sự mặc dù đã được duyệt với kỹ thuật lấy mẫu. CLARANS lưu trữ tất cả mọi điểm dữ liệu trong bộ nhớ vì thế CLARANS chỉ có thể áp dụng lên cơ sở dữ liệu nhỏ. Để khắc phục được điều này, một kỹ thuật lấy mẫu đã được áp dụng để cải tiến CLARANS có thế xử lý với dữ liệu lớn. Nếu CLARANS không áp dụng kỹ thuật nào thì không thể xử lý được dữ liệu lớn. Mặc dù thuật toán cho kết quả hoàn toàn độc lập với thứ tự dữ liệu đầu vào nhưng CLARANS chỉ có thể tìm ra cụm với hình thù đơn giản mà không tìm ra cụm với hình thù bất kỳ. Hơn nữa CLARANS không làm việc được với dữ liệu nhiều chiều. Dựa trên phương pháp lấy mẫu thì thuật toán có thể không xử lý được với những trường hợp dữ liệu có chứa nhiễu. Thuật toán có thể sẽ xác định một điểm dữ liệu cực tiểu địa phương. Mặc dù không cần thiết phải xác định số cụm trước như những thuật toán phân hoạch khác nhưng thuật toán CLARANS lại yêu cầu hai tham biến là Numlocal và Maxneighbor từ người sử dụng. 2.6.2. Phương pháp phân cấp (Hierarchical Methods) Phương pháp này xây dựng một phân cấp trên cơ sở các đối tượng dữ liệu đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng 37 hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Kỹ thuật này có 2 cách tiếp cận đó là: - Tiếp cận hội tụ, thường được gọi là tiếp cận Bottom – Up - Tiếp cận phân chia nhóm, thường được gọi là tiếp cận Top – Down Hình 2.7: Các chiến lược phân cụm phân cấp 1) Tiếp cận bottom-up: bắt đầu với mỗi đối tượng thành lập một cụm riêng biệt. Sau đó tiến hành hợp hoặc nhóm các đối tượng theo một vài tiêu chí đó như khoảng cách giữa trung tâm của 2 nhóm. Thuật toán kết thúc khi tất cả các nhóm được hợp thành một nhóm (nút gốc của cây) hoặc thỏa mãn điều kiện dừng. Từ cây mới tạo được, đưa ra các cụm bằng cách chọn tập các đối tượng tại các nút thoả mãn điều kiện dừng. 2) Tiếp cận top-down: Xuất phát từ gốc là một cụm với tất cả các đối tượng trong một cơ sở dữ liệu. Tại mỗi bước lặp thì cụm được phân chia thành cụm nhỏ hơn theo tiêu chí nào đó. Việc phân chia dừng khi mỗi đối tượng là một cụm hoặc thỏa mãn điều kiện dừng (kết thúc). Điều kiện kết thúc là điều kiện để xác định một tập các đối tượng tại mỗi nút có phải là một cụm hay không. Điều kiện kết thúc được đưa vào từ người sử dụng. Ưu điểm của phương pháp này là kết hợp linh hoạt vào mức độ chi tiết, dễ dàng xử lý với bất kỳ kiểu đo độ tương tự/khoảng cách nào, thích hợp với mọi kiểu dữ liệu thuộc tính. 38 Nhược điểm là điều kiện để dừng vòng lặp rất mơ hồ, không cụ thể. Mặt khác, phương pháp không duyệt lại các mức trước khi xây dựng để cải tiến chất lượng các cụm. Phương pháp này gồm có các thuật toán: AGNES (Agglomerative NEsting) và DIANA (DIvisia ANAlysic), CURE (Clustering Using Representatives), BIRCH (Balance Iterative Reducing and Clustering using Hierarchies), CHAMELEON … Dưới đây mô tả 2 trong số các thuật toán trên. 2.6.2.1. Thuật toán BIRCH BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) do Tian Zhang, amakrishman và Liviny được giới thiệu vào năm 1996 [17], là thuật toán phân cụm phân cấp sử dụng chiến lược top-down BIRCH sử dụng cấu trúc dữ liệu kiểu cây CF –tree hoặc Clustering – Feature tree (là cây cân bằng được sử dụng để lưu trữ các đặc trưng cụm) để phân cụm những đối tượng dữ liệu khi chúng được đưa vào. Cây CF là cây mà trong đó mỗi thành phần (entry) lưu bộ ba giá trị tổng hợp để duy trì và quản lý một cụm, ),,( SSLSNCF   với N là số điểm trong cụm,     Ni iXLS 1 là tổng tuyến tính của N điểm, và     Ni iXSS 1 2 là tổng bình phương của N điểm. Khi hòa nhập hai cụm ta có CF = CF1 + CF2 = (n1 + n2, LS1 + LS2, SS1 + SS2) khoảng cách giữa các cụm có thể đo bằng khoảng cách Euclide, Manhatta… VD: CF = (n, LS, SS), n là số đối tượng dữ liệu. 39 Hình 2.8: Ví dụ về kết quả phân cụm bằng thuật toán BIRCH. Ý tưởng chính của BIRCH là nén các đối tượng dữ liệu thành nhiều cụm nhỏ hơn, sau đó thực hiện phân cụm trên các cụm con. Nhờ việc nén dữ liệu, số các cụm con nhỏ hơn số đối tượng, nên việc gom cụm được thực hiện trên bộ nhớ chính và chỉ cần duyệt dữ liệu một lần. Thuật toán BIRCH chỉ làm việc trên trường dữ liệu kiểu số (metric) và sử dụng trên cơ sở dữ liệu lớn [17] Thuật toán BIRCH phân cụm với các giai đoạn: - Giai đoạn 1: Lấy dữ liệu ra bộ nhớ, sau đó xây dựng cây CF-tree (Clustering Feature tree) để lưu trữ dữ liệu. - Giai đoạn 2: Giảm kích thước (condense) tập dữ liệu (tùy chọn). Xây dựng lại cây CF-tree với kích thước T nào đó, tiến hành loại bỏ các phần tử ngoại lai và nhóm các cụm con có phân bố dầy. - Giai đoạn 3: Sử dụng các thuật toán gom cụm hiện có (K-means, CLARANS,...) trên cây CF-tree. Xác định cách giải quyết vấn đề liên quan đến cụm vốn có của các đối tượng. - Giai đoạn 4: Làm mịn lại các cụm (tùy chọn). Duyệt lại các đối tượng trong cơ sở dữ liệu rồi gán lại các đối tượng vào cụm tương ứng trong giai 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 CF = (5, (16,30),(54,190)) (3,4) (2,6) (4,5) (4,7) (3,8) 40 đọan 3. Xác định cách giải quyết các đối tượng có cùng giá trị thuộc nhiều lá khác nhau. Giai đoạn 2 và giai đoạn 4 được sử dụng để tăng hiệu quả của thuật toán nhưng không nhất thiết phải có. Ưu điểm: Với cấu trúc CF được sử dụng, BIRCH có tốc độ thực hiện PCDL nhanh và có thể áp dụng đối với tập CSDL lớn, BIRCH cũng có hiệu quả khi áp dụng với tập dữ liệu tăng trưởng theo thời gian, và nó thực hiện tính toán khá tốt. BIRCH duyệt cơ sở dữ liệu duy nhất một lần nên độ phức tạp của thuật toán là O(N) khi N>>K (K là số cụm con). Khi K xấp xỉ N thì thời gian chạy sẽ là O(N2). Do đó, nên ngưỡng sử dụng trong giai đoạn 1 phải được chọn rất cẩn thận. Nhược điểm: Một trong những điểm yếu chính của BIRCH là BIRCH sử dụng phương pháp dựa vào điểm trung tâm để tạo các cụm với duy nhất một lần duyệt dữ liệu, nên các cụm được tạo ra có thể không đều về hình dáng và kích thước. Nhưng đối tượng dữ liệu nằm ở biên của một cụm lớn hơn có thể rất gần với tâm của cụm nhỏ. Trong trường hợp đó, đối tượng dữ liệu đó sẽ được phân bố lại vào cụm nhỏ mặc dù thực tế đối tượng dữ liệu đó thuộc cụm lớn. Ngoài ra, thứ tự của dữ liệu vào cũng ảnh hưởng tới kết quả của việc phân cụm. BIRCH là phương pháp phân cụm dựa vào điểm trung tâm nên chỉ có thể tạo ra được những cụm với hình dáng là hình tròn hoặc đa giác lồi. Để khắc phục được điều này, ta có thể duyệt cơ sở dữ liệu nhiều lần. Tuy nhiên việc lặp đi lặp lại quá trình duyệt sẽ dẫn tới thời gian chạy tăng lên đáng kể. Thêm vào nữa là BIRCH yêu cầu nhiều tham biến từ người dùng. Một điểm chú ý nếu các cụm không có dạng hình cầu thì thuật toán này thực hiện không tốt bởi vì nó dùng giá trị bán kính và đường kính để kiểm soát đường biên cụm. 2.6.2.2. Thuật toán CURE CURE (Clustering Using REpresentatives) [12][14] được đề xuất năm 1998 bởi Sudipto Guha, RajeevRastogi và Kyuseok Shim là thuật toán sử dụng chiến lược Bottom up của kỹ thuật phân cụm phân cấp. Trong khi hầu hết các thuật toán thực hiện phân cụm với các cụm hình cầu và kích thước tương tự nên không hiệu quả khi xuất hiện các phần tử ngoại lai. Thuật toán CURE khắc phục được vấn đề này và tốt hơn với các phân tử ngoại lai. Thuật toán này định nghĩa một số cố định các điểm đại diện nằm rải rác trong toàn bộ không gian dữ liệu và được chọn 41 để mô tả các cụm được hình thành. Các điểm này được tạo ra bởi trước hết lựa chọn các đối tượng nằm rải rác cho cụm và sau đó “co lại” hoặc di chuyển chúng về trung tâm cụm bằng nhân tố co cụm. Quá trình này được lặp lại, có thể đo tỉ lệ gia tăng của cụm. Tại mỗi bước của thuật toán, hai cụm có cặp các điểm đại diện gần nhau (mỗi điểm trong cặp thuộc về mỗi cụm khác nhau) được hoà nhập. Vậy, có nhiều hơn một điểm đại diện mỗi cụm cho phép CURE khám phá được các cụm có hình dạng không phải hình cầu. Việc co lại các cụm có tác dụng làm giảm tác động của các phần tử ngoại lai. Hình 2.9. Khái quát thuật toán CURE Hình 2.10. Các cụm dữ liệu được khám phá bởi CURE Với mục đích của CURE để xử lý các cơ sở dữ liệu lớn, CURE sử dụng mẫu ngẫu nhiên của dữ liệu và phân hoạch. Một mẫu được xác định ngẫu nhiên trước khi được phân hoạch, và sau đó tiến hành phân cụm trên mỗi phân hoạch. Như vậy trên mỗi phân hoạch là từng phần đã được phân cụm, quá trình này lặp lại cho đến khi ta thu được phân hoạch đủ tốt. Các cụm thu được lại được phân cụm lần thứ hai để thu được các cụm con mong muốn, nhưng mẫu ngẫu nhiên không nhất thiết đưa ra một mô tả tốt cho toàn bộ tập dữ liệu. Việc sử dụng mẫu ngẫu nhiên của dữ liệu để giải quyết 2 vấn đề: 1) Mẫu có thể đươc chọn để lưu trữ được trong bộ nhớ trong. Điều này loại bỏ được thời gian dữ liệu vào/ra; 42 2) Mẫu ngẫu nhiên có thể giúp loại bỏ những điểm dữ liệu bất thường. Phải chọn mẫu ngẫu nhiên sao cho xác xuất để mất cụm là nhỏ nhất. Kích thước của mẫu sẽ ảnh hưởng đến sự phân tách giữa các cụm và mật độ các điểm bên trong một cụm. Để tăng tốc độ trong quá trình phân cụm mà tăng kích thước của mẫu lớn lên, CURE phân hoạch và phân cụm một cách từng phần những dữ liệu trong mẫu được chọn. Thuật toán CURE được thực hiện qua các bước cơ bản sau: B1: Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu. B2: Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thước bằng nhau: Ý tưởng chính ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng nhau, kích thước của mỗi phân hoạch là n’/p (n’ là kích thước của mẫu). B3: Phân cụm các điểm của mỗi nhóm: Thực hiện PCDL cho các nhóm cho đến khi được phân thành n’/(pq) cụm (với q > 1). B4: Loại bỏ các phân tử ngoại lai: Trước hết, khi các cụm được hình thành cho đến khi số các cụm giảm xuống một phần so với số các cụm ban đầu. Sau đó, trong trường hợp các phân tử ngoại lai được lấy mẫu cùng với quá trình pha khởi tạo mẫu dữ liệu, thuật toán sẽ tự động loại bỏ các nhóm nhỏ. B5: Phân cụm các cụm không gian: Các đối tượng đại diện cho các cụm di chuyển về hướng trung tâm cụm, nghĩa là chúng được thay thế bởi các đối tượng gần trung tâm hơn. B6 : Đánh dấu dữ liệu với các nhãn tương ứng. Như vậy, thuật toán này có khả năng: - CURE đưa ra được cụm với hình dáng bất kỳ. - CURE không bị ảnh hưởng bởi trường hợp bất thường và có khả năng loại bỏ điểm bất thường. - Mẫu với kích thước thích hợp không làm giảm chất lượng của các nhóm được tạo. 43 - Thời gian chạy nhanh Độ phức tạp thuật toán của CURE trong trường hợp xấu nhất là O(N2logN) với N là số điểm trong ví dụ mẫu. Với không gian có số chiều nhỏ thì độ phức tạp giảm xuống chỉ còn là O(N2). Độ phức tạp của CURE phụ thuộc vào độ lớn của tập mẫu chứ không phụ thuộc trực tiếp vào độ lớn của dữ liệu. CURE là thuật toán tin cậy trong việc khám phá ra các cụm với hình dạng bất kỳ và có thể áp dụng tốt đối với dữ liệu có phần tử ngoại lai, và trên các tập dữ liệu hai chiều. Tuy nhiên, nó lại rất nhạy cảm với các tham số như số các đối tượng đại diện, tỉ lệ của các phần tử đại diện. Hình 2.11. Ví dụ thực hiện phân cụm bằng thuật toán CURE 2.6.2.3. Thuật toán CHAMELEON Thuật toán CHAMELEON, được Karypis G. giới thiệu vào năm 1999, có cách tiếp cận giống AGNES, cải tiến chất lượng cụm bằng cách dùng các điều kiện phức tạp hơn khi hợp các cụm. Hình vẽ dưới mô tả cách tiếp cận của thuật toán CHAMELEON để tìm các cụm trong tập dữ liệu. 44 Hình 2.12: Các bước thuật toán CHAMELEON Thuật toán thao tác trên đồ thị rời rạc (sparse graph) trong đó mỗi một nút là một đối tượng trong tập dữ liệu, cạnh biểu diễn độ tương tự nhau giữa các đối tượng. Để tìm các cụm của tập dữ liệu, thuật toán gồm 2 giai đoạn: - Giai đoạn 1 thực hiện phân chia đồ thị rời rạc thành các cụm con tương đối. - Giai đoạn 2 tìm các cụm thật sự bằng cách lặp lại thao tác kết hợp các cụm con. Thuật toán sử dụng mô hình động để xác định độ tương tự bằng cách kiểm tra chỉ số RI (tính liên thuộc - relative interconnectivity) và RC (tính gần nhau - relative closeness). Với cặp cụm đang xét nếu cả hai chỉ số trên cao thì hai cụm được hòa nhập thành một cụm mới [14]. Nhờ vậy, thuật toán không phụ thuộc vào mô hình tĩnh do người dùng cung cấp mà nó tự thích nghi với các đặc tính bên trong của các cụm đang hòa nhập lại [14]. Độ phức tạp tính toán của thuật toán này là O(n2), thuật toán có thể tìm ra các cụm có hình dáng phức tạp hoặc khác nhau, mật độ cũng như kích thước mỗi cụm khác nhau. 2.6.3. Phương pháp dựa trên mật độ (Density-Based Methods) Phương pháp dựa trên mật độ phân cụm các đối tượng dữ liệu dựa trên mối quan hệ của các đối tượng dữ liệu với các điểm lân cận của các điểm dữ liệu đó. Phân cụm dựa trên mật độ (có điều kiện cụm cục bộ) giống như các điểm có khả năng liên kết theo mật độ (density-connected). Một cụm được mở rộng theo hướng bất kỳ mà mật độ dẫn theo, do đó phương pháp này có khả năng tìm ra các cụm có hình dạng phức tạp. Mặc dù chỉ duyệt tập dữ liệu một lần nhưng phương pháp này có khả năng loại bỏ phần tử nhiễu và phần tử ngoại lai. Phương pháp này phù hợp 45 với các đối tượng có trường dữ liệu kiểu số, dữ liệu thuộc tính chỉ là thuộc tính mô tả thêm cho các đối tượng không gian. Phương pháp này có thể tiếp cận theo 2 hướng chính: liên kết dựa trên mật độ và hàm mật độ. Các thuật toán thuộc phương pháp này bao gồm DBSCAN (Density Based Spatial Clustering of Application with Noise), OPTICS (Ordering Points to Identify the Clustering Structure), DENCLUE (Density-based CLUstEring), DBCLASD (Distribution Based Clustering of Large Spatial Databased). Dưới đây mô tả hai trong số các thuật toán trên. 2.6.3.1. Thuật toán DBSCAN DBSCAN (Density based Spatial Clutering of Application with Noise) [11][14] được đề xuất năm 1996 bởi Ester, P.Kriegel và J.Sande, khi nghiên cứu các thuật toán phân cụm dữ liệu không gian dựa trên định nghĩa cụm là tập tối đa các điểm liên thông về mật độ. Thuật toán thực hiện tốt trên không gian 2 chiều, 3 chiều hay một số không gian nhiều chiều khác; thích hợp với cơ sở dữ liệu có mật độ phân bố dày đặc kể cả có phần tử nhiễu. Hình 2.13: Hình dạng các cụm được khám phá bởi DBSCAN Một số khái niệm sử dụng trong giải thuật DBSCAN 1. Lân cận với ngưỡng Eps của một điểm: Lân cận với ngưỡng Eps của một điểm p ký hiệu là Neps(p) được xác định như sau: Neps(p) = {q  D | khoảng cách dist(p,q)  Eps} với D là tập dữ liệu cho trước. 46 Một điểm p muốn nằm trong một cụm C nào đó thì NEps(p) phải có tối thiểu MinPts điểm. Số điểm tối thiểu được chọn là bao nhiêu cũng là bài toán khó vì nếu số điểm tối thiểu lớn thì chỉ những điểm nằm thực sự trong cụm C mới đạt đủ tiêu chuẩn, trong khi đó những điểm nằm ngoài biên của cụm không thể đạt đựơc điều đó. Ngược lại, nếu số điểm tối thiểu là nhỏ thì mọi điểm sẽ rơi vào một cụm. Theo định nghĩa trên, chỉ những điểm thực sự nằm trong cụm mới thoả mãn điều kiện là điểm thuộc vào cụm. Những điểm nằm ở biên của cụm thì không thoả mãn điều kiện đó, bởi vì thông thường thì lân cận với ngưỡng Eps của điểm biên bé hơn lân cận với ngưỡng cũng Eps của điểm nhân. Để tránh được điều này, có thể đưa ra một tiêu chuẩn khác để định nghĩa một điểm thuộc vào một cụm như sau: Nếu một điểm p muốn thuộc một cụm C phải tồn tại một điểm q mà p Epsq N (q) và số điểm NEps(q) phải lớn hơn điểm tối thiểu. Điều này dẫn đến ba phép đo được sử dụng để mô tả thuộc tính của các điểm dữ liệu, là mật độ liên lạc trực tiếp, mật độ liên lạc và mật độ liên thông được định nghĩa như sau: 2. Một điểm dữ liệu p được gọi là điểm nhân (core - point) nếu miền lân cận của p với bán kính Eps có ít nhất là minpt điểm. 3. Mật độ - đến được trực tiếp (Directly Density-reachable) : q được gọi là đến được theo mật độ trực tiếp nếu p là điểm nhân và q  Neighbor(p, Eps). Hình 2.14: Mật độ - đến được trực tiếp 4. Mật độ - đến được (Density - Reachable): Một điểm p được gọi là mật độ - đến được từ điểm q theo tham số Eps và MinPts nếu tồn tại một dãy p = p0, p1,…, pn = q với pi là đến được theo mật độ trực tiếp từ pi+1. 47 Hình 2.15: Mật độ - đến được. Hai điểm của cụm C có thể không đến được với nhau bởi vì cả hai cùng không thoả mãn điều kiện nhân. Mặc dù vậy, phải tồn tại một điểm nhân trong C mà cả hai điểm đều có thể đến được từ điểm đó. 5. Mật độ - liên thông (Density - Connected): Một điểm p gọi là mật độ - liên thông với q nếu có một điểm 0 mà cả p và q đều là mật độ - đến được từ 0. Hình 2.16: Mật độ - liên thông 6. Cụm: Một tập con C khác rỗng của D được gọi là một cụm (cluster) theo Eps và minpts nếu thoả mãn hai điều kiện: a. Với mọi p, q  D, nếu p  C và q có thể đến được từ p theo Eps và Minpts thì p  C. b. Với mọi p, q  C, p liên thông theo mật độ với q theo Eps và Minpts. 7. Dữ liệu nhiễu (noise): Giả sử C1, C2, …, Ck là các cụm trong tập dữ liệu D theo tham số Eps và MinPts, một điểm dữ liệu nếu không thuộc vào 48 cụm nào trong các cụm C1, C2, …, Ck thì gọi là nhiễu, tức là nhiễu = {p | i = 1… k, p  Ci} Hình 2.17: Cụm và nhiễu. Ngoài việc sử dụng các định nghĩa trên, DBSCAN còn có hai bổ đề để quan trọng để kiểm tra tính đúng đắn của thuật toán. Với các tham số Eps và MinPts đã cho trước chúng ta có thể phát hiện một cụm theo phương pháp mật độ theo hai bước sau: - Thứ nhất chọn một điểm bất kì trong CSDL thỏa mãn điều kiện điểm nhân, coi điểm này là hạt giống (seed). - Thứ hai tìm tất cả các điểm kề mật độ với điểm hạt giống trong cụm. Bổ đề 1: Giả sử p là một điểm trong D và ||NEps(p)||  MinPts. Tập O = {o | oD và o có thể liên lạc từ p} là một cụm theo Eps và MinPts. Không rõ ràng rằng cụm C được xác định bởi duy nhất một điểm nhân nào của nó. Tuy nhiên, mỗi điểm trong C là điểm kề mật độ với một điểm nhân bất kì của C và theo đó C chính xác chứa các điểm mà kề mật độ với một điểm nhân bất kì của C. Bổ đề 2: Giả sử C là một cụm theo Eps và MinPts, p là điểm bất kỳ trong C với ||NEps(p)|| MinPts. Khi đó, C trùng với tập O = {o | oD và o có thể liên lạc theo Eps và MinPts}. Ý tưởng chính của DBSCAN là với mỗi điểm của cụm láng giềng thuộc bán kính cho trước có chứa số điểm là ít nhất, ví dụ mật độ trong láng giềng có thể vượt quá ngưỡng nào đó. Vùng láng giềng có hình dạng được xác định bằng việc chọn hàm khoảng cách của 2 điểm, ký hiệu dist(p, q), tùy thuộc vào ứng dụng đó. Chẳng hạn nếu chọn hàm khoảng cách Manhattan thì vùng láng giềng có hình chữ nhật. 49 Khái niệm được dùng trong thuật toán này là tham số toàn cục Eps và MinPts, đối tượng nhân (core) và đối tượng biên (border). Tham số Eps là bán kính lớn nhất của miền láng giềng. Miền láng giềng Eps của điểm p, ký hiệu NEps(p), là các điểm q thuộc không gian đối tượng D sao cho khoảng cách dist(p, q)  Eps. Tham số MinPts là số điểm ít nhất nằm trong vùng láng giềng Eps của điểm đó. Đối tượng nhân là các đối tượng thực sự nằm bên trong cụm và đối tượng biên là các đối tượng nằm trên đường biên của cụm. Số điểm trong miền Eps của đối tượng biên nhỏ hơn so với đối tượng nhân. Thuật toán chi tiết như sau: B1: Tạo đồ thị gồm các đối tượng trong tập dữ liệu B2: Với mỗi điểm nhân c vẽ cạnh từ c tới mọi điểm p thuộc NEps(c) B3: Gán N = số nút trên đồ thị B4: Nếu N không chứa bất kỳ điểm nhân nào thì dừng B5: Lấy điểm nhân c trong N B6: Gán X = tập các điểm mà từ c có thể đi tiếp đến B6.1. Tạo cụm chứa X  {c} B6.2. Gán N = N \ (X  {c}) B7: Quay lại B4. Thuật toán DBSCAN yêu cầu hai tham số là Eps và minpts từ người dùng, việc xác định giá trị của hai tham số này có ảnh hưởng lớn đến các cụm được phát hiện. Tham số Eps xác định tập các đối tượng lân cận của một đối tượng dữ liệu. Minpts là tham số ngưỡng mật độ của các đối tượng dữ liệu. Việc xác định giá trị Eps và MinPts tối ưu là một bài toán cần tìm lời giải, bởi vì nếu các giá trị đủ lớn thì mọi điểm thuộc cụm đó đều phải thỏa mãn. Tuy nhiên nếu các giá trị đó nhỏ thì có thể rơi vào trường hợp mọi điểm trong tập dữ liệu đều thuộc một cụm. 50 Thuật toán này sử dụng cấu trúc cây R*-tree để lưu trữ tập dữ liệu. DBSCAN có độ phức tạp tính toán khi chưa dùng cây chỉ mục để xử lý là O(n2) và sau khi dùng R*-tree là O(n*log(n)). 2.6.3.2. Thuật toán DENCLUE DENCLUE (Density-based CLUstEring) được giới thiệu năm 1998 bởi Hinne Burg Kein [13] là thuật toán phân cụm tổng quát, được đề xuất vào năm 1998 bởi Hinne Burg Kein. Thuật toán này được xây dựng dựa trên các ý tưởng: (1) sự ảnh hưởng của mỗi điểm dữ liệu có thể biểu diễn dưới dạng mô hình thông qua hàm toán học, gọi là hàm ảnh hưởng (influence function) dùng để mô tả ảnh hưởng của điểm dữ liệu lên vùng láng giềng của nó; (2) toàn bộ mật độ của không gian dữ liệu có thể được mô hình hóa theo giải tích là tổng các hàm ảnh hưởng của mọi điểm dữ liệu; (3) các cụm có thể được xác định theo toán học bởi các điểm mật độ cao (density attractor), trong đó điểm mật độ cao là điểm đạt cực đại hàm mật độ toàn cục. Với đối tượng x, y trong không gian d-chiều ký hiệu Fd, hàm ảnh hưởng của đối tượng y lên x là một hàm  0: RFf dy B được định nghĩa dưới dạng một hàm ảnh hưởng cơ bản ),()(: yxfXff b y Bb  . Hàm ảnh hưởng có thể là hàm bất kỳ xác định khoảng cách của hai véc tơ d(x, y) trong không gian d chiều. Hàm mật độ tại điểm x  Fd là tổng các hàm ảnh hưởng của tất cả các điểm dữ liệu. Với n là các đối tượng dữ liệu mô tả bởi tập véc tơ D={x1, x2,…, xn}Fd, hàm mật độ được định nghĩa    n i ix B D B xfxF 1 )()( . Hàm mật độ cục bộ (local density function)     )(1 1 )()( xnearx x B D xfxf trong đó hàm near(x) được xác định với x1 near(x) thì d(x1, x)  near. Hàm mật độ cục bộ quan tâm đến sự ảnh hưởng của các điểm gần với điểm đang xét và ảnh hưởng của các điểm xa thì bỏ qua. Thuật toán DENCLUE gồm 2 bước như sau: 51 Bước 1: Xây dựng bản đồ chứa không gian dữ liệu cần phân cụm để việc tính toán hàm mật độ được thực hiện nhanh hơn. Tiến hành phân chia không gian bằng khối siêu lập phương d-chiều có độ dài cạnh là 2, sau đó dựng cây lưu trữ dữ liệu bằng cấu trúc cây B+-tree hoặc cây tìm kiếm ngẫu nhiên và chỉ lưu trữ các khối siêu lập phương có chứa dữ liệu. Mỗi nút trên cây tương ứng với một khối c, cần lưu thêm thông tin số điểm dữ liệu trong khối, tổng giá trị trong khối để tính giá trị trung bình mean(c) của mỗi khối. Nếu cụm thuộc nhiều khối, cần cho biết các khối láng giềng với khối đang xét. Thông thường khối c2 được gọi là liên thông với c1 khi giá trị khoảng cách d(mean(c1), mean(c2))  4. Bước 2: Thực hiện việc phân cụm, chỉ có những khối có mật độ cao Cp và các khối liên thông của chúng được xem xét trong quá trình phân cụm. Tính hàm mật độ cục bộ )(xf D  và điểm mật độ cao x* của điểm x, nếu hàm mật độ của x* thỏa mãn điều kiện thì điểm x được phân loại và gán vào cụm theo x* [20]. Thuật toán có độ phức tạp tính toán là O(n*log(n)) và phụ thuộc nhiều vào tham số mật độ và ngưỡng nhiễu, việc chọn tham số thích hợp ảnh hưởng đến chất lượng của các cụm thu được. Tuy nhiên thuật toán cho kết quả tốt kể cả tập dữ liệu lớn và có nhiễu, thậm chí các cụm có hình dạng bất kỳ trong tập dữ dữ liệu đa chiều cũng được mô tả trong công thức toán đơn giản. Cấu trúc dữ liệu theo ô lưới làm cho thuật toán có khả năng xử lý các khối dữ liệu lớn kể cả dữ liệu đa chiều. 2.6.4. Phương pháp dựa trên lưới (Gird-Based Methods) Phương pháp phân cụm dựa trên lưới thích hợp với dữ liệu nhiều chiều, và chủ yếu được dùng để phân cụm cho dữ liệu không gian. Phương pháp sử dụng cấu trúc dữ liệu lưới (grid), bằng cách chia không gian thành số hữu hạn các ô để hình thành cấu trúc lưới và mọi thao tác phân cụm đều thực hiện trên đó. Ưu điểm là thời gian xử lý nhanh mà không bị ảnh hưởng bởi số các đối tượng dữ liệu, ngược lại nó phụ thuộc vào số các ô trong mỗi chiều của không gian được chia [13][14]. 52 Cách tiếp cận dựa trên lưới hiệu quả hơn so với phương pháp dựa trên mật độ và phân cấp, vì chỉ làm việc với từng đối tượng trong từng ô mà không phải đối tượng dữ liệu, mặt khác phương pháp này không trộn/hòa nhập các ô như phân cấp. Một ví dụ về cấu trúc dữ liệu lưới chứa các ô trong không gian như hình sau: Hình 2.18: Mô hình cấu trúc dữ liệu lưới Các thuật toán điển hình theo phương pháp dựa trên lưới gồm: STING (STatistical INformation Grid), WaveCluster, CLIQUE (CLustering In QUEst)… Dưới đây là trình bày hai trong số các thuật toán trên. 2.6.4.1. Thuật toán STING STING (STatistical Information Grid-based method) [16] được đề xuất năm 1997 bởi Wang, Yang và Muntz. Thuật toán này là kỹ thuật phân cụm đa phân giải dựa trên lưới, khám phá tính chất của cụm dựa vào cấu trúc chỉ số. STING chia miền không gian thành những ô lưới chữ nhật theo chiều ngang hoặc chiều dọc và đánh chỉ số cho từng ô lưới. Sau đó, mỗi đối tượng dữ liệu sẽ được đưa vào ô lưới tương ứng. Một cấu trúc phân cấp được sử dụng để xây dựng lên lưới của miền dữ liệu không gian. Mỗi một ô ở tầng i thì được chia thành k ô ở tầng kế tiếp. STING lưu trữ tham số trong mỗi ô với mục đích có thể trả lời những yêu cầu về thống kê. Ngoài việc lưu trữ số điểm hoặc đối tượng trong từng ô, STING lưu trữ thêm một vài giá trị khác gồm[20]: - m – giá trị trung bình của tất cả giá trị trong ô. 53 - s – mức deviation của tất cả các giá trị của thuộc tính trong một ô. - min – giá trị nhỏ nhất của một thuộc tính trong một ô. - max – giá trị lớn nhất của một thuộc tính trong một ô. - Dis – kiểu phân bố mà một thuộc tính trong một ô tuân theo. Kiểu phân bố có thể là: Thường, đều, hàm số mũ hoặc không xác định. Kiểu phân bố có thể được xác định trước bởi người dùng hoặc xác định bằng phương pháp X2. Hình 2.19: Mô hình thuật toán STING. Các truy vấn không gian được thực hiện bằng cách xét các ô thích hợp tại mỗi mức của phân cấp. Truy vấn không gian được xác định như là một thông tin khôi phục lại của dữ liệu không gian và các quan hệ của chúng. Một câu truy vấn đưa ra một kết quả mà người sử dụng muốn tìm. Ví dụ như “Đưa ra vùng lớn nhất mà ít nhất có 100 ngôi nhà trong một đơn vị, có ít nhất 70% nhà có giá trị trên $400K với độ tin cậy là 90%”. Để xác định được câu truy vấn này, STING bắt đầu từ gốc (tầng cao nhất) của cấu trúc cây và tìm các ô thoả mãn cho câu truy vấn. Ô thoả mãn câu truy vấn được xác định trên khả năng của các đối tượng trong câu truy vấn. Chỉ những con của ô thoả mãn thì mới được xét tiếp tục và quá trình dừng lại khi lá thấp nhất được tìm thấy. Kết quả đưa ra là những ô ở tầng thấp nhất. Độ phức tạp của STING là O(N), với N là số đối tượng trong cơ sở dữ liệu. STING chỉ cần duyệt qua toàn bộ cơ sở dữ liệu một lần để đưa ra được cấu trúc cây mà mỗi lần trả lời một câu truy vấn cần thời gian chạy là O(K) với K là số ô lưới. Chú ý là N>>k. 54 Ưu điểm: - Tính toán dựa trên lưới là truy vấn độc lập vì thông tin thống kê được bảo quản trong mỗi ô đại diện nên chỉ cần thông tin tóm tắt của dữ liệu trong ô lưới chứ không phải dữ liệu thực tế và không phụ thuộc vào câu truy vấn. - Cấu trúc dữ liệu lưới thuận tiện cho quá trình xử lí song song và cập nhật liên tục. - Duyệt toàn bộ cơ sở dữ liệu cho một lần để tính toán các đại lượng thống kê cho mỗi ô, nên nó rất hiệu quả. Hạn chế: Mặc dù STING có thể đưa ra một phân cụm tốt đáp ứng được yêu cầu của người sử dụng trong khoảng thời gian rất nhanh nhưng vẫn tồn tại hai vấn đề: 1) Thuật toán chỉ dựa trên thuộc tính của các lá ở tầng cuối cùng; 2) Thuật toán không dựa vào mối quan hệ giữa các nút con không cùng một cha. Vì thế, thuật toán đưa ra được cụm với biên là chiều ngang và chiều dọc nhưng không đưa ra được biên có chiều là đường chéo. Điều này cũng ảnh hưởng tới chất lượng của thuật toán. 2.6.4.2. Thuật toán CLIQUE CLIQUE (Clustering In QUEst) [10] được đề xuất năm 1998 bởi Agrawal, Gehrke, Gunopulos, Raghavan; CLIQUE là một hướng tiếp cận mật độ và phương pháp chia lưới áp dụng cho cơ sở dữ liệu nhiều chiều. Mô hình thuật toán phân cụm cho cơ sở dữ liệu nhiều chiều là hạn chế không gian tìm kiếm trong một không gian con (sub_space) thay vì thêm vào những chiều mới được tạo ra bằng cách tích hợp các chiều ban đầu. Hướng tiếp cận mật độ được áp dụng cho phép phân cụm trong không gian con đó. Với mục đích là xấp xỉ mật độ của điểm dữ liệu, mỗi một chiều sẽ được phân hoạch thành những khoảng bằng nhau dựa vào cách tiếp cận từ dưới lên. Độ lớn của mỗi phân hoạch là giống nhau và mật độ của phân hoạch có thể coi như là số điểm bên trong phân hoạch đó. Những thông số về mật độ sẽ được sử dụng để xác định không gian con. 55 Cụm được xác định trong không gian con bằng cách chia những điểm dữ liệu dựa vào hàm mật độ của các điểm và mật độ của một không gian con. Để đơn giản, mỗi cụm sẽ được giới hạn bởi một hình khối chữ nhật có các cạnh song song với các trục. Các cụm được hình thành lên bằng cách nhóm một số hình chữ nhật gối lên nhau. Hai tham biến dùng để phân hoạch không gian con và xác định đơn vị mật độ là  và  trong đó  là số khoảng với độ dài bằng nhau mà một không gian sẽ được chia,  là ngưỡng để xác định một khối có là khối mật độ hay không. Thuật toán gồm các bước cụ thể như sau Bước 1: Xác định miền không gian con chứa các cụm. Thuật toán xử lý theo từng mức và sử dụng phương pháp dưới lên (bottom-up) để tìm ra những đơn vị mật độ. Đầu tiên sẽ đi duyệt qua toàn bộ cơ sở dữ liệu để tìm ra được đơn vị mật độ một chiều. Một đơn vị mật độ cha sẽ được xác định dựa vào những thông tin có sẵn trong những đơn vị con. Những không gian con được phủ bởi nhiều đơn vị mật độ nhất sẽ được lựa chọn và cắt bỏ những phần còn lại. Những không gian con được sắp theo số điểm mật độ trong không gian đó… Bước 2: Tìm kiếm các cụm. Thuật toán là tìm các thành phần liên thông sử dụng các đơn vị như các đỉnh và giữa hai đỉnh có một cạnh khi và chỉ khi chúng có chung ít nhất một mặt. Một thuật toán tìm kiếm theo chiều sâu được sử dụng để tìm ra những thành phần liên thông của đồ thị. Các cụm được phụ thuộc vào số khối mật độ. Bước 3: Sinh ra đặc tả tối thiểu cho mỗi cụm (cụm được tạo ra từ bước 2). Với mỗi cụm, xác định vùng lớn nhất chứa cụm các đơn vị mật độ liên thông. Tiếp đó xác định phủ tối tiểu (minimal cover) cho cụm đó. Độ phức tạp của thuật toán phụ thuộc vào 3 phần: Xác định không gian con O(ck + mk) với k là hằng số, k là số chiều lớn nhất của các đơn vị mật độ và m là số điểm dữ liệu đầu vào. Thuật toán sẽ đi qua dữ liệu k lần. Tại bước thứ 2, thuật toán kiểm tra 2k điểm lân cận để tìm ra các miền liên thông của các đơn vị mật độ. Độ phức tạp của bước cuối cùng là 2kn. Độ phức tạp của bước cuối cùng là O(n2) với n là số đơn vị mật độ. Thời gian chạy xấp xỉ biến đổi tuyến tính với kích thước của dữ liệu vì số lần duyệt qua dữ liệu là không thay đổi. Tuy nhiên, khi số chiều của dữ liệu tăng lên thì độ phức tạp cũng tăng rất nhanh. CLIQUE không phụ thuộc vào thứ tự vào ra của dữ liệu và không yêu cầu những thông tin của dữ liệu trước. CLIQUE yêu cầu hai tham biến từ người sử dụng 56 và làm việc hiệu quả với dữ liệu nhiễu. Tuy nhiên khi gía trị  quá nhỏ thì sẽ có những đơn vị chứa dữ liệu nhiễu nhưng vẫn được xem là đơn vị của cụm và xem như là một cụm. 2.6.5. Kết luận Mỗi một phương pháp phân cụm đều có điểm mạnh điểm yếu và thích hợp cho từng ứng dụng cụ thể. 1) Phương pháp phân hoạch Phương pháp phân hoạch đơn giản, dễ