Tài liệu Phân cụm dữ liệu định danh với số chiều cao

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ------------------------------------------- PHAN THỊ LUÂN PHÂN CỤM DỮ LIỆU ĐỊNH DANH VỚI SỐ CHIỀU CAO LUẬN VĂN THẠC SỸ Hà Nội – 2013 2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ------------------------------------------- PHAN THỊ LUÂN PHÂN CỤM DỮ LIỆU ĐỊNH DANH VỚI SỐ CHIỀU CAO Ngành: Công nghệ thông tin Chuyên ngành: Công nghệ phần mềm Mã số: 60 48 10 LUẬN VĂN THẠC SỸ NGƢỜI HƢỚNG DẪN KHOA HỌC PGS.TS. HOÀNG XUÂN HUẤN Hà Nội - 2013 1 MỤC LỤC LỜI CẢM ƠN ...................................................................................................................... 1 MỤC LỤC ........................................................................................................................... 1 DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT .................................................................... 5 DANH MỤC CÁC HÌNH VẼ ............................................................................................. 6 DANH MỤC BẢNG BIỂU………………………………………………………………..7 MỞ ĐẦU ............................................................................................................................. 8 CHƢƠNG 1: GIỚI THIỆU VỀ KHÁM PHÁ TRI THỨC VÀ PHÂN CỤM DỮ LIỆU . 11 1.1. Khám phá tri thức .................................................................................................... 11 1.2. Phân cụm dữ liệu ..................................................................................................... 12 1.3. Vấn đề chuẩn hóa dữ liệu ........................................................................................ 13 1.4. Các ứng dụng của phân cụm dữ liệu. ....................................................................... 15 1.5. Mêtric trên dữ liệu hỗn hợp. .................................................................................... 16 1.6. Độ tƣơng đồng ......................................................................................................... 19 CHƢƠNG 2. MỘT SỐ PHƢƠNG PHÁP PHÂN CỤM CHÍNH ..................................... 22 2.1. Phƣơng pháp phân hoạch. ........................................................................................ 22 2.1.1. Thuật toán K-Means.......................................................................................... 24 2.1.2. Thuật toán phân cụm K-centroid ...................................................................... 26 2.2. Phƣơng pháp phân cấp. ............................................................................................ 26 2.2.1. Thuật toán BIRCH ............................................................................................ 28 2.2.2. Thuật toán ROCK ............................................................................................. 30 2.3. Phƣơng pháp phân cụm dựa trên mật độ. ................................................................ 31 2.4. Phƣơng pháp phân cụm dựa trên lƣới ...................................................................... 33 CHƢƠNG 3: PHÂN CỤM DỮ LIỆU VỚI THUỘC TÍNH ĐỊNH DANH ..................... 36 3.1. Mode và thuật toán k-modes .................................................................................... 37 3.1.1. Mode của tập dữ liệu hỗn hợp. .......................................................................... 37 3.1.2. Thuật toán k-modes ........................................................................................... 40 2 3.2. Thuật toán K-Prototypes .......................................................................................... 40 3.3. Thuật toán k-modes có trọng số. .............................................................................. 41 3.4. Thuật toán k-modes cho dữ liệu hỗn hợp có trọng số. ............................................ 46 3.5. Entropy và thuật toán COOLCAT ........................................................................... 55 3.5.1. Entropy và cụm ................................................................................................. 55 3.5.2. Vấn đề về công thức. ......................................................................................... 58 3.5.3. Thuật toán COOLCAT ...................................................................................... 59 3.6. Tiêu chuẩn đánh giá chất lƣợng phân cụm..............................................................64 CHƢƠNG 4: KẾT QUẢ THỬ NGHIỆM ......................................................................... 64 4.1. Giới thiệu ................................................................................................................. 64 4.2. Chƣơng trình và dữ liệu thử nghiệm ........................................................................ 64 4.2.1. Chƣơng trình ..................................................................................................... 64 4.2.2. Dữ liệu thử nghiệm. .......................................................................................... 65 4.3. Kết quả thử nghiệm ................................................................................................ 67 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ........................................................................ 74 TÀI LIỆU THAM KHẢO ................................................................................................. 75 PHỤ LỤC .......................................................................................................................... 78 3 DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT Từ hoặc cụm từ Thuật toán BIRCH Từ viết tắt BIRCH Từ tiếng Anh Balanced Interative Reducing and Clustering using Hierarchies Thuật toán CLARA CLARA Clustering LARge Applications Cơ sở dữ liệu CSDL DataBase Thuật toán CURE CURE Clustering Using Representatives Thuật toán DBSCAN DBSCAN Density-Based Spatial Clustering of Applications with Noise Thuật toán DENCLUE DENCLUE DENsity – based CLUstEring Khai phá tri thức trong cơ sở dữ liệu KDD Knowledge Discovery in Databases Khai phá dữ liệu KPDL Data Mining Khai phá tri thức KPTT Knowledge Discovery Thuật toán OPTICS OPTICS Ordering Points To Indentify the Clustering Structure Thuật toán PAM PAM Partitioning Around Medoids Phân cụm dữ liệu PCDL Data Clustering Thuật toán ROCK ROCK RObust Clustering using linKs 4 DANH MỤC CÁC HÌNH VẼ Hình 1.1 Quá trình phát hiện tri thức trong CSDL..................................................... 12 Hình 1.2 Mô phỏng vấn đề phân cụm dữ liệu............................................................ 13 Hình 1.3 Dữ liệu chữ thập với các mêtric khác nhau............................................... 14 Hình 1.4 Kết quả phân cụm thay đổi khi thay đổi tỉ lệ trục tọa độ............................. 14 Hình 2.1 Minh họa phân cụm K-means..................................................................... 25 Hình 2.2 Ví dụ về trộn và tách của phân cụm phân cấp trên tập đối tƣợng{a, b, c, d} 27 Hình 2.3 Cấu trúc cây CF.......................................................................................... 29 Hình 2.4 Phạm vi và sự liên kết mật độ trong phân cụm dựa trên mật độ................. 33 Hình 2.5 Ví dụ về xác định các cụm trung tâm và các cụm có hình dạng tùy ý........ 33 Hình 2.6 Ví dụ về đặc trƣng của không gian 2 chiều................................................ 34 Hình 2.7 Multiresolution of the feature space........................................................... 34 Hình 3.1 Tần số thuộc tính aj...................................................................................... 37 Hình 3.2 Các chức năng giá trị khách quan đối với các lần lặp khác nhau ban đầu dự 54 đoán............................................................................................................... Hình 4.1 C-Free tạo ra chƣơng trình.......................................................................... 64 Hình 4.2 Giao diện khi chạy chƣơng trình................................................................. 65 Hình 4.3 Mô hình quan hệ của dữ liệu thử nghiệm................................................... 67 Hình 4.4 Biểu đồ biến thiên giá trị CU trung bình của 2 thuật toán theo số cụm ứng 70 với CSDL thuê bao di động................................................................. Hình 4.5 Biểu đồ biến thiên thời gian chạy chƣơng trình của 2 thuật toán ứng với 70 CSDL thuê bao di động........................................................................... Hình 4.6 Biểu đồ biến thiên giá trị CU trung bình của 2 thuật toán theo số cụm ứng 71 với cơ sở dữ liệu điều tra dân số của Mỹ năm 1990……………………… Hình 4.7 Biểu đồ biến thiên thời gian chạy chƣơng trình của 2 thuật toán theo số cụm ứng với cơ sở dữ liệu điều tra dân số năm 1990……………………. 72 5 DANH MỤC BẢNG BIỂU Bảng 1.1 Bảng tham số.............................................................................................. 20 Bảng 3.1 Ví dụ về tập dữ liệu..................................................................................... 44 Bảng 3.2 Phân phối tần số cho một biến định tính.................................................... 55 Bảng 3.3 Bảng tiếp liên để so sánh hai phân cụm...................................................... 62 Bảng 4.1 Kết quả thử nghiệm với dữ liệu đậu tƣơng................................................. 68 Bảng 4.2 Kết quả thử nghiệm với tập dữ liệu nấm…………………………………. 68 Bảng 4.3 Kết quả thử nghiệm với tập dữ liệu ung thƣ phổi....................................... 69 Bảng 4.4 Kết quả thử nghiệm với tập dữ liệu thuê bao di động phát sinh của thủ đô 69 Hà Nội với số cụm k biến thiên................................................................... Bảng 4.5 Kết quả thử nghiệm với tập dữ liệu USCensus với số cụm k biến thiên… 71 8 MỞ ĐẦU Phân cụm dữ liệu nhằm chia tập dữ liệu thành nhiều cụm, trong đó các phần tử trong một cụm giống nhau nhiều hơn các phần tử khác cụm, là một phần quan trọng trong phân tích thống kê nhiều chiều và học máy không giám sát. Bài toán này có nhiều ứng dụng trong các lĩnh vực khác nhau nhƣ: gian lận tài chính, chẩn đoán trong y tế, xử lý hình ảnh, tìm kiếm thông tin, tin sinh học. Những thuật toán phân cụm đầu tiên làm việc với các đặc trƣng số nhƣ là một phần của thống kê toán [15]. Cùng với sự phát triển của ứng dụng công nghệ thông tin, khối lƣợng dữ liệu tăng nhanh đòi hỏi phát triển các kỹ thuật khám phá tri thức trên các dạng dữ liệu khác nhau trên dữ liệu lớn với độ phức tạp thấp. Mặt khác các kỹ thuật khám phá tri thức thƣờng phải làm việc với dữ liệu quan hệ nhiều chiều với các thuộc tính giá trị định danh [16]. Trong trƣờng hợp đó việc phân dữ liệu thành các nhóm con có độ tƣơng tự cao trong mỗi nhóm để xử lý sẽ giảm đáng kể thời gian chạy cho các thuật toán và tăng chất lƣợng của kỹ thuật khám phá tri thức. Bài toán phân cụm dữ liệu thuộc loại “thiết lập không đúng đắn” theo nghĩa lời giải thƣờng không duy nhất và thay đổi nhiều khi dữ liệu thay đổi ít. Vì vậy ngƣời ta có nhiều cách tiếp cận dựa trên quan sát tổng thể tập dữ liệu để áp dụng thuật toán thích hợp. Khi số chiều cao, ngoài khối lƣợng tính toán tăng lên, dữ liệu phân bố “thƣa” nên việc quan sát dữ liệu để phân tích đặc điểm hình học cũng rất khó khăn nên phân cụm khó hiệu quả. Một cách tiếp cận cho dữ liệu chiều cao là chiếu chúng lên không gian có chiều thấp hơn, chẳng hạn, các phƣơng pháp: CLIQUE[2], ENCLUS[6], MAFIA[19], Proclus[4], ORCLUS[5], FINDIT[13], DOC [7], d-clusters[9], HARP[14] và LDR[11] cho dữ liệu số. Trong các phƣơng pháp phân cụm, thuật toán k-means do MacQueen (1967 ) đề xuất có độ phức tạp thấp, thích hợp với dữ liệu lớn và có số chiều cao. Ban đầu thuật toán này đƣợc dùng cho dữ liệu số sau đó đƣợc phát triển thành thuật toán k-modes cho các dữ liệu định danh. Tuy nhiên khi dữ liệu nhiều chiều, việc xem đồng thời các thuộc tính nhƣ nhau khi phân cụm ở thuật toán này không thích hợp và ngƣời ta phát triển nhiều thuật toán mới. Để giải quyết hiệu quả vấn đề này, luận văn đã trình bày một số thuật toán tối ƣu hoá để so sánh phân nhóm dữ liệu phân loại chiều cao. 9 Trong các thuật toán trình bày, một kỹ thuật trọng số mới phân loại dữ liệu đƣợc đƣa ra để tính toán trọng số cho mỗi thuộc tính (hoặc chiều) trong mỗi cụm và sử dụng các giá trị trọng số để xác định tập hợp con cuả các thuộc tính quan trọng mà phân loại cụm khác nhau. Các nghiên cứu thực nghiệm cho thấy rằng các thuật toán đề xuất có hiệu quả trong nhóm phân loại tập hợp dữ liệu và cũng có khả năng mở rộng dữ liệu lớn với độ phức tạp là tuyến tính. Ngoài phần kết luận luận văn đƣợc trình bày thành 4 chƣơng với nội dung đƣợc trình bày nhƣ sau: Chƣơng 1: Giới thiệu về khám phá tri thức và phân cụm dữ liệu. Trình bày cách biểu diễn dữ liệu trong máy tính nhằm phục vụ cho quá trình phân cụm, giới thiệu độ tƣơng đồng giữa các đối tƣợng trong tập dữ liệu, các phƣơng pháp phân cụm dữ liệu. Chƣơng 2: Một số phƣơng pháp phân cụm chính. Ở chƣơng này với mỗi phƣơng pháp phân cụm sẽ trình bày một số thuật toán chính. Tƣ tƣởng của phƣơng pháp phân hoạch là tìm cách phân chia tập dữ liệu thành các tập không giao nhau, thỏa mãn điều kiện làm tối ƣu hàm đánh giá. Trong mỗi tập con thƣờng có ít nhất một phần tử đại diện, phần tử đại diện thƣờng là tâm của tập con đó. Mỗi đối tƣợng trong tập dữ liệu đƣợc phân vào cụm có điểm đại diện gần với đối tƣợng đó nhất. Quá trình này lặp đi lặp lại cho tới khi hàm mục tiêu không thay đổi. Phƣơng pháp phân cấp phân tách các tập đối tƣợng theo hai cách: Tiếp cận từ dƣới lên (BottomUp) hoặc trên xuống (Top-Down). Tiếp cận từ dƣới lên bắt đầu với mỗi đối tƣợng đƣợc xem nhƣ một nhóm, sau đó gộp các đối tƣợng hay các nhóm theo các hàm nhƣ hàm khoảng cách giữa các tâm của hai nhóm và điều này đƣợc thực hiện cho tới khi tất cả các nhóm đƣợc gộp vào làm một nhóm hoặc cho tới khi điều kiện kết thúc đƣợc thỏa mãn. Tiếp cận theo phƣơng pháp từ trên xuống bắt đầu với tất cả các đối tƣợng nằm trong cùng một cụm. Trong mỗi lần lặp, một cụm đƣợc tách ra thành các cụm nhỏ hơn theo một ƣớc lƣợng nào đó. Điều này đƣợc thực hiện cho tới khi mỗi đối tƣợng là một cụm, hoặc cho tới khi điều kiện kết thúc thỏa mãn. Đối với phƣơng pháp đƣợc phát triển dựa trên quan niệm về mật độ. Các cụm tiêu biểu đƣợc xét là các vùng có các đối tƣợng tập trung đậm đặc và đƣợc phân chia bởi các vùng có mật độ thấp (đặc trƣng cho nhiễu). Các phƣơng pháp dựa trên mật độ có thể sử dụng để lọc ra các nhiễu (phần tử ngoại lai), và khám phá ra các cụm có hình dạng bất kỳ. Cách tiếp cận dựa trên lƣới sử dụng cấu trúc lƣới của dữ 10 liệu. Nó lƣợng tử hóa khoảng cách vào một số hữu hạn các ô là cấu trúc dạng lƣới để tất cả các phép toán phân cụm thực hiện đƣợc. Chƣơng 3: Phân cụm dữ liệu với thuộc tính định danh Với dữ liệu tồn tại trong tự nhiên là rất lớn và phong phú. Trong khuôn khổ luận văn quan tâm đến việc phân cụm dữ liệu định danh. Ở chƣơng này chúng tôi có trình bày một số thuật toán, trong đó đi sâu vào hai thuật toán COOLCAT và MWKM để phân cụm dữ liệu định danh với nhiều thuộc tính. Luận văn cũng đã so sánh đƣợc ƣu, nhƣợc điểm của hai thuật toán này thông qua kết quả thực nghiệm ở chƣơng 4. Chƣơng 4: Kết quả thực nghiệm Luận văn đã trình bày kết quả thực nghiệm so sánh hai thuật toán COOLCAT và MWKM với 5 bộ dữ liệu với nhiều thuộc tính: Cơ sở dữ liệu đậu tƣơng, cơ sở dữ liệu nấm, cơ sở dữ liệu ung thƣ phổi, CSDL về thuê bao di động phát sinh của thành phố Hà Nội và CSDL điều tra dân số của Mỹ năm 1990. Các hàm mục tiêu để đánh giá chất lƣợng phân cụm là CU, ARI và ER đã đƣợc trình bày kỹ trong chƣơng 3. Cuối cùng là kết luận, hƣớng phát triển, tài liệu tham khảo và phụ lục. Phần kết luận trình bày tóm tắt kết quả thu đƣợc và đề xuất hƣớng nghiên cứu tiếp theo. 11 CHƢƠNG 1: GIỚI THIỆU VỀ KHÁM PHÁ TRI THỨC VÀ PHÂN CỤM DỮ LIỆU Nội dung của chƣơng này giới thiệu quá trình khám phá tri thức từ dữ liệu và các ứng dụng thực tế có sự hỗ trợ của các kỹ thuật khai thác dữ liệu. Đồng thời, trình bày khái niệm về phân cụm dữ liệu và lĩnh vực khai thác dữ liệu. 1.1. Khám phá tri thức Trong nhiều năm trở lại đây khai thác dữ liệu đã thu hút đƣợc rất nhiều sự quan tâm trong ngành công nghiệp thông tin và xã hội, do dữ liệu sẵn có là vô cùng lớn và sự cần thiết chuyển dữ liệu đó thành thông tin và kiến thức hữu ích. Các thông tin và kiến thức thu đƣợc có thể đƣợc sử dụng cho các ứng dụng khác nhau, ví dụ nhƣ phân tích thị trƣờng, phát hiện gian lận, và duy trì khách hàng, để kiểm soát sản xuất và khoa học thăm dò. Khai phá dữ liệu có thể đƣợc xem nhƣ là một kết quả của sự tiến hóa tự nhiên của công nghệ thông tin [10]. Khái niệm KDD (Knowledge Discovery in Databases): KDD đƣợc định nghĩa là quá trình trích chọn các mẫu hoặc tri thức hấp dẫn (không tầm thƣờng, tiềm ẩn, chƣa biết và hữu dụng tiềm năng) trong CSDL lớn. Quá trình KDD có thể phân thành các giai đoạn sau [10,18, 21]: 1. Lựa chọn dữ liệu: Là bƣớc ta lựa chọn tập dữ liệu ban đầu theo một số tiêu chí nhất định từ tập dữ liệu lớn nhƣ: database, data warehouses hay data repositories. 2. Tiền xử lý dữ liệu: Bƣớc này làm sạch dữ liệu (xử lý với dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, …), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phƣơng pháp nén dữ liệu, sử dụng histograms, lấy mẫu, ….), rời rạc hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng, ...). Qua bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn, và đƣợc rời rạc hóa. 3. Đổi dạng: Là bƣớc chuẩn hóa và làm mịn dữ liệu để đƣa dữ liệu về dạng phù hợp nhất nhằm phục vụ cho các kỹ thuật khai phá ở bƣớc sau. 4. Khai phá dữ liệu (Data mining): Đây là bƣớc áp dụng những kỹ thuật phân tích (phần nhiều là các kỹ thuật của học máy) nhằm để khai thác dữ liệu, trích chọn đƣợc những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu. Đây đƣợc xem là bƣớc quan trọng và tốn nhiều thời gian nhất của toàn quá trình KDD. 12 5. Biểu diễn: Các mẫu thông tin và mối liên hệ trong dữ liệu đã đƣợc khám phá ở bƣớc trên đƣợc chuyển dạng và biểu diễn ở một dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật, ... Đồng thời bƣớc này cũng đánh giá những tri thức khám phá đƣợc theo những tiêu chí nhất định. Đổi dạng Khai phá dữ liệu Tri thức Tiền xử lý Chọn lựa Dữ liệu đích Biểu diễn Dữ liệu đã tiền xử lý Chuyển dạng dữ liệu Mẫu Dữ liệu Hình 1.1 Quá trình phát hiện tri thức trong CSDL 1.2. Phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật quan trọng trong công nghệ tri thức đƣợc ứng dụng rộng rãi và đa dạng trong các ngành khoa học nhƣ sinh học, y học, tâm lý học, ngành marketting, thị giác máy tính và điều khiển học. PCDL (Data clustering) là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tƣơng tự" (Similar) với nhau và các phần tử trong các cụm khác nhau sẽ "phi tƣơng tự" (Dissimilar) với nhau. Số các cụm dữ liệu đƣợc phân ở đây có thể đƣợc xác định trƣớc theo kinh nghiệm hoặc có thể đƣợc tự động xác định của phƣơng pháp phân cụm. Mục tiêu của phƣơng pháp phân cụm dữ liệu là tìm kiếm các nhóm đối tƣợng theo hình dạng tự nhiên. Các thuật toán phân cụm hƣớng tới việc tìm kiếm cấu trúc trong dữ liệu. 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 lĩnh vực nhận dạng mẫu (Patterm Recognition) nói riêng và trong trí tuệ nhân tạo nói chung. 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 đó [3, 10]. Dựa vào khám phá cấu trúc dữ liệu, ta chia tập dữ liệu thành các cụm rời nhau sao cho các đối tƣợng trong cùng một cụm thì tƣơng tự nhau so với các đối tƣợng khác cụm. Trong các bài toán này, ta không có thông tin về dữ liệu có nhãn mà chỉ đơn thuần dựa vào tính tƣơng đồng của các đối tƣợng dữ liệu để phân lớp nên gọi tiếp cận này thuộc loại hƣớng dữ liệu (data driven). 13 Ví dụ minh họa về phân cụm dữ liệu nhƣ hình 1.2 sau: Hình 1.2: Mô phỏng vấn đề PCDL Có nhiều thuật toán phân cụm dựa trên các cách tiếp cận khác nhau về liên quan của đối tƣợng (tính tƣơng đồng), J. Han và M. Kamber [10] phân làm 4 loại chính:  Phƣơng pháp phân hoạch (Partition Based Data Clustering).  Phƣơng pháp phân cấp (Hierarchical Data Clustering).  Phƣơng pháp dựa trên mật độ (Density Based Data Clustering).  Phƣơng pháp dựa trên lƣới (Grid Based Data Clustering). Mỗi một phƣơng pháp phân cụm dữ liệu đều có ƣu, nhƣợc điểm riêng, chƣa có một phƣơng pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cụm dữ liệu. Một thuật toán phân cụm phù hợp cho một ứng dụng phải thỏa mãn cả hai tiêu chuẩn về chất lƣợng và tốc độ yêu cầu. Trƣớc khi giới thiệu các phƣơng pháp phân cụm, ta xem xét vấn đề chuẩn hóa dữ liệu, một số khái niệm nhƣ chiều và phần tử nhiễu. 1.3. Vấn đề chuẩn hóa dữ liệu. Việc chọn mêtric và đơn vị chia cho mỗi đặc trƣng của dữ liệu ảnh hƣởng nhiều tới kết quả phân cụm. Trong hình 1.3 biểu diễn tập dữ liệu hình chữ thập, nếu chia tập dữ liệu thành hai cụm theo tiêu chuẩn cực tiểu sai số trung bình 2 E=  i 1 1 ni  d ( x, y) x , y  i và dùng chuẩn Euclide thì ta đƣợc hai cụm ở hình a còn dùng chuẩn Mahattan thì ta đƣợc hai cụm ở hình b . 14 Hình 1.3. Dữ liệu chữ thập với các mêtric khác nhau: a) Euclide; b) Mahattan Việc chọn đơn vị cho đặc trƣng cũng có thể cho kết quả khác nhau. Trong hình 1.4 chỉ ra rằng bằng trực quan ta thấy cách chia dữ liệu về tội phạm có thể khác nhau khi ta dùng các cách chia tỷ lệ cho mỗi đặc trƣng. Hình 1.4: Kết quả phân cụm thay đổi khi thay đổi tỷ lệ trục tọa độ.a) {Faro, V.Real} {Setúba, Viseu}; b) { Viseu, V.Real} {Setúba, Faro }; Nói chung không phải dữ liệu nào cũng cần chuẩn hóa, đặc biệt với các bài toán cần thông tin từ đặc trƣng gốc. Tuy vậy sau đây là một số cách để chuẩn hóa các đặc trƣng của dữ liệu: yi = (xi - m)/s với m,s tƣơng ứng là trung bình và độ lệch chuẩn của xi ; (1.3a) yi = (xi - min(xi))/(max(xi)-min(xi)); (1.3b) yi = xi /(max(xi)-min(xi)); (1.3c) yi = xi /a . (1.4d) Tóm lại ta cần lƣu ý rằng: 1. Để thực hiện phân cụm, ta cần chọn mêtric thích hợp 15 2. Mêtric thích hợp phụ thuộc vào phƣơng pháp chuẩn hóa 3. Để chọn phƣơng pháp chuẩn hóa ta cần biết về kiểu cụm muốn có.  Chiều: Là số thuộc tính của một đối tƣợng dữ liệu. Một số các thuật toán phân cụm thực hiện tốt, nó không bị giảm chất lƣợng khi số chiều tăng lên. Giảm chất lƣợng thể hiện: tăng thời gian thực hiện hoặc giảm chất lƣợng cụm. Bởi vậy, tùy thuộc vào ứng dụng mà ta chọn thuật toán nhiều chiều phù hợp.  Các phần tử nhiễu (noise), ngoại lai (Outlier) trong dữ liệu: Trong dữ liệu phân cụm hầu hết đều chứa các dữ liệu nhiễu và các phần tử ngoại lai. Một số thuật toán phân cụm dữ liệu rất dễ bị ảnh hƣởng bởi nhiễu và các phần tử ngoại lai. Cho nên việc làm sạch dữ liệu trƣớc khi sử dụng cũng là một vấn đề đặt ra hoặc phải lựa chọn kỹ lƣỡng nếu dữ liệu trong ứng dụng bao gồm một lƣợng lớn “nhiễu”. Bởi vậy, các vấn đề liên quan đến bài toán phân cụm dữ liệu là vấn đề biểu diễn dữ liệu trong máy tính, xác định phƣơng pháp, từ đó đƣa ra thuật toán cụ thể để áp dụng, đồng thời xác định độ tƣơng đồng giữa các đối tƣợng. Đối với các thuật toán trong phƣơng pháp dựa vào phân hoạch thì ta còn phải xây dựng hàm mục tiêu phù hợp để thuật toán cho ra kết quả phân cụm tốt. 1.4. Các ứng dụng của phân cụm dữ liệu. 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. Hiện nay, nó là một trong những công cụ chính đƣợc ứng dụng trong nhiều lĩnh vực nhƣ thƣơng mại và khoa học. Các kỹ thuật PCDL đã đƣợc áp dụng cho một số ứng dụng điển hình trong các lĩnh vực sau [1, 10, 17]:  Tóm tắt và giải thích dữ liệu bài toán: Nhiều bài toán, dữ liệu có thể đƣợc tóm tắt nhờ xem xét thuộc tính của các cụm dữ liệu mà không cần thiết xem xét thuộc tính của từng mẫu. Trong nhiều lý thuyết khoa học, việc giải thích theo cụm cũng rất có ý nghĩa, chẳng hạn việc phân tích tiến hóa sinh học có thể thực hiện theo loài và nhóm.  Tạo mẫu cho tiếp cận phân lớp thống kê: Trong nhiều bài toán phân lớp, việc thu thập dữ liệu mất nhiều thời gian và chi phí lớn. Việc phân cụm dữ liệu đƣợc thực hiện ở giai đoạn đầu để ƣớc lƣợng phân phối lớp cho các tập mẫu nhỏ.  Để tạo tâm cho các nơron nhân tạo trong các bộ phân lớp loại này: Khi dùng mạng nơron nhân tạo để phân lớp, ngƣời ta thƣờng dùng vector trung bình của các vector đặc trƣng trong cụm làm tâm của các nơron để nhận biết các mẫu có đặc trƣng gần đó. 16  Thương mại: Trong thƣơng mại, PCDL có thể giúp các thƣơng nhân khám phá ra các nhóm khách hàng quan trọng có các đặc trƣng tƣơng đồng nhau và đặc tả họ từ các mẫu mua bán trong CSDL khách hàng.  Sinh học: Trong sinh học, PCDL đƣợc sử dụng để xác định các loại sinh vật, phân loại các Gen với chức năng tƣơng đồng và thu đƣợc các cấu trúc trong các mẫu.  Phân tích dữ liệu không gian: Do sự đồ sộ của dữ liệu không gian nhƣ dữ liệu thu đƣợc từ các hình ảnh chụp từ vệ tinh các thiết bị y học hoặc hệ thống thông tin địa lý (GIS), …làm cho ngƣời dùng rất khó để kiểm tra các dữ liệu không gian một cách chi tiết. PCDL có thể trợ giúp ngƣời dùng tự động phân tích và xử lý các dữ liêu không gian nhƣ nhận dạng và chiết xuất các đặc tính hoặc các mẫu dữ liệu quan tâm có thể tồn tại trong CSDL không gian.  Lập 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ị.  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.  Địa lý : Phân lớp các động vật và thực vật và đƣa ra đặc trƣng của chúng.  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;  Web Mining: PCDL có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý nghĩa trong môi trƣờng Web. Các lớp tài liệu này trợ giúp cho việc khám phá tri thức từ dữ liệu,… 1.5. Mêtric trên dữ liệu hỗn hợp. Nhƣ đã trình bày ở 1.2 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 (tên gọi “các kiểu dữ liệu” hay “các kiểu thuộc tính dữ liệu” là tƣơng đƣơng nhau). Các thuộc tính này là các tham số để 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[10]: 17 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:  x1 1  ...   x i1   ... x  n1 ... x1 f ... ... ... ... ... x if ... ... ... ... ... x nf ... x1 p   ...  x ip   ...  x np   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  d ( 2 ,1)   d (3,1)     d ( n ,1)  0 d (3, 2 ) 0    d (n, 2) ... ...       0  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. Trong lƣợc đồ quan hệ R, miền giá trị của các thuộc tính Aj có thể là tập số thực, định danh hay là tập có thứ tự [1, 10]. Định nghĩa 1.5.1. Giả sử DOM(Aj) là miền giá trị của thuộc tính Aj. Ta có các khái niệm sau. i) Thuộc tính định danh. Đây là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, Aj đƣợc gọi là thuộc tính định danh nếu DOM(Aj) là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử, tức là  a,b  DOM(Aj), hoặc a = b hay a  b. Chẳng hạn nhƣ thuộc tính nơi sinh hoặc thuộc tính tên gọi của người. ii) Thuộc tính số. Aj đƣợc gọi là thuộc tính số nếu DOM(Aj) là tập số thực. 18 iii) Thuộc tính 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 DOM(Aj) là tập hữu hạn và có thứ tự hoàn toàn thì Aj đƣợc gọi là thuộc tính có thứ tự, chẳng hạn: DOM(Aj) = { không đau, hơi đau, đau và rất đau}. Trên miền giá trị DOM(Aj) của một thuộc tính Aj ta xác định các khoảng cách nhƣ sau. iv) Thuộc tính nhị phân là thuộc tính có hai giá trị là 0 và 1. Định nghĩa 1.5.2.  x,y  DOM(Aj) ta hàm dj(x,y) xác định bởi : i) Nếu Aj là thuộc tính số thì dj(x,y) = x y (1.5a) ii) Nếu Aj là thuộc tính thứ tự và DOM(Aj) = a 1j ,..., a kj  với hàm đơn điệu fj: DOM(Aj)→ [0,1] sao cho là: f j (a j )  i i 1 k 1 a 1 j  a 0  1 j  ...  a f j ( a j )  0 ; f j ( a j )  1 (Hàm 1 k ) . Khi đó dj(x,y) = │fj(x)-fj(y) │. iii) Nếu Aj là thuộc tính định danh thì dj(x,y) = 2 k j , ta lấy một này có thể (1.5b) khi : x  y (1.5c) khi : x  y Bây giờ ta định nghĩa khoảng cách trên Định nghĩa 1.5.3. Giả sử x = (x1,...,xn) và y = (y1,...,yn) là hai đối tƣợng dữ liệu hỗn hợp trên D, khoảng cách d(x,y) đƣợc tính bởi công thức: n d ( x, y)    j d j (x j, y j ) 2 2 (1.5d) j 1 trong đó các dj(xj,yj) đƣợc tính theo các công thức (1.5a -1.5c) và  là các trọng số dƣơng j cho bởi các chuyên gia tuỳ theo mức quan trọng của thuộc tính. Với định nghĩa trên, ta luôn có thể xem các thuộc tính thứ tự có miền giá trị là đoạn [0,1] để tìm mode (các giá trị trên thuộc tính này của D là tập con) và nó cũng đƣợc xem là thuộc tính số khi không xảy ra nhầm lẫn. Chú ý. Nếu xem miền giá trị của các thuộc tính có thứ tự là đoạn [0,1] và mode của tập hợp xác định nhƣ đã nói ở trên thì với mọi tập dữ liệu hỗn hợp C , mode(C) cực tiểu hàm: E(x) =  2 d ( y, x) yC trong đó x là phần tử của quan hệ r trên lƣợc đồ quan hệ R={A1,...,An}. 19 1.6. Độ tƣơng đồng. Phân cụm dữ liệu là phƣơng pháp nhóm các đối tƣợng có độ tương tự (Similar) hay độ tƣơng đồng vào trong một nhóm, các đối tƣợng ở các nhóm khác nhau thì có độ tƣơng đồng thấp. Độ tƣơng đồng giữa các đối tƣợng mô tả tính chất giống nhau hoặc khác nhau giữa chúng theo một ý nghĩa nào đó. Có rất nhiều hàm đƣợc dùng để biểu diễn độ tƣơng đồng giữa các đối tƣợng. Trong khuôn khổ luận văn chỉ trình bày một số các hàm đo tƣơng đồng phổ biến gọi là các hàm khoảng cách. Tất cả phƣơng pháp đo khoảng cách đều phụ thuộc vào kiểu thuộc tính (hay kiểu dữ liệu) của các đối tƣợng đƣợc phân tích. Chẳng hạn thuộc tính hạng mục (Categorical) ngƣời ta 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. Mỗi một kiểu dữ liệu đều tồn tại một không gian đo mêtric cho nó. Một không gian mêtric là một tập trong đó có xác định các “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. Khoảng cách giữa hai mẫu thứ i và mẫu thứ k kí hiệu là d(i, k) phải thỏa mãn tính chất sau: i) d(i, i) = 0 với mọi i. ii) d(i, k) = d(k, i) với mọi cặp (i, k). iii) d(i, k) >= 0 với mọi cặp (i, k). Một số phép đo độ tƣơng tự áp dụng cho các kiểu thuộc tính [10].  Thuộc tính khoảng: Sau khi chuẩn hóa, độ đo phi tƣơng tự của hai đối tƣợng dữ liệu x, y đƣợc xác định bằng các mêtric khoảng cách nhƣ sau: Độ đo Khoảng cách Minskowski Khoảng cách Euclide Công thức n d (x, y)  (  |x  i i 1 n d ( x, y)  1/q q y i|  ( x i  y i) i 1 Giải thích 2 q - số tự nhiên dƣơng ) Đây là trƣờng hợp đặc biệt của khoảng cách Minskowski trong trƣờng hợp q = 2. 20 Độ đo Công thức Khoảng cách Manhattan Đây là trƣờng hợp đặc biệt của khoảng cách Minskowski trong trƣờng hợp q = 1. n d ( x, y)  |x i  y i 1 Khoảng cách cực đại Giải thích d ( x, y)  n Max i 1 | | i x i  y Đây là trƣờng hợp của khoảng | cách Minskowski trong trƣờng i hợp q   . Thuộc tính nhị phân: Trƣớc hết chúng ta có xây dựng bảng tham số sau : Bảng 1.1 : Bảng tham số y 1 0 1    + 0    + x  Trong đó :  +  +  =  +  +  +  , các đối tƣợng x, y mà tất cả các thuộc tính tính của nó đều là nhị phân biểu thị bằng 0 và 1. Bảng trên cho ta các thông tin sau :   là tổng số các thuộc tính có giá trị là 1 trong cả hai đối tƣợng x, y.   là tổng số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y   là tổng số các giá trị thuộc tính có giá trị là 0 trong x và 1 trong y   là tổng số các giá trị thuộc tính có giá trị là 0 trong x và y Các phép đo độ tƣơng tƣơng đồng đối với dữ liệu thuộc tính nhị phân đƣợc định nghĩa nhƣ sau : o Hệ số đối sánh đơn giản: d ( x, y)     , ở đây cả hai đối tƣợng x và y có vai trò nhƣ nhau, nghĩa là chúng đối xứng và có cùng trọng số.