Tài liệu Tóm tắt dữ liệu quan hệ dùng phương pháp phân cụm bán giám sát dựa trên giải thuật di truyền

5 MỤC LỤC LỜI CẢM ƠN ................................................................................................................3 LỜI CAM ĐOAN ..........................................................................................................4 MỤC LỤC ...................................................................................................................... 5 DANH MỤC BẢNG BIỂU ........................................................................................... 8 MỞ ĐẦU ......................................................................................................................... 9 CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU..................................11 Giới thiệu ................................................................................................................. 11 Biểu diễn dữ liệu ...................................................................................................... 12 Độ tương đồng ......................................................................................................... 13 Các phương pháp phân cụm dữ liệu không giám sát ............................................... 15 1.4.1. Các phương pháp phân hoạch ........................................................................ 16 1.4.2. Các phương pháp phân cấp ............................................................................ 19 1.4.3. Phương pháp phân cụm dựa trên mật độ ....................................................... 24 1.4.4. Các phương pháp phân cụm dựa trên lưới..................................................... 27 1.5. Các phương pháp cụm dữ liệu bán giám sát ............................................................ 29 1.5.1. Giới thiệu ........................................................................................................ 29 1.5.2. Thuật toán phân cụm bán giám sát K-means ................................................. 30 1.1. 1.2. 1.3. 1.4. CHƯƠNG 2: GIẢI THUẬT DI TRUYỀN .......................................................... 34 2.1. Giới thiệu ................................................................................................................. 34 2.2. Giải thuật di truyền cổ điển ...................................................................................... 34 2.2.1. Phương pháp mã hoá và giải mã.................................................................... 36 2.2.2. Thủ tục chọn lọc ............................................................................................. 36 2.2.3. Quá trình tái tạo. ............................................................................................ 37 2.2.4. Sự hội tụ của GA ............................................................................................. 38 2.2.5. Ví dụ................................................................................................................ 38 2.3. Biểu diễn bằng véc tơ số thực .................................................................................. 40 2.3.1. Các toán tử tương giao chéo .......................................................................... 41 2.3.2. Các toán tử biến dị ......................................................................................... 41 2.3.3. Ứng dụng của GA trong các thuật toán phân cụm ......................................... 41 CHƯƠNG 3: TÓM TẮT DỮ LIỆU QUAN HỆ SỬ DỤNG PHƯƠNG PHÁP PHÂN CỤM BÁN GIÁM SÁT DỰA TRÊN GIẢI THUẬT DI TRUYỀN ............43 3.1. Giới thiệu ................................................................................................................. 43 3.2. Chuyển đổi dữ liệu ................................................................................................... 44 3.2.1. Giới thiệu ........................................................................................................ 44 3.2.2. Cơ sở dữ liệu quan hệ ..................................................................................... 45 3.2.3. Quá trình mã hóa các mẫu tin thành số nhị phân .......................................... 46 3.3. Dữ liệu đại diện trong một mô hình không gian Vector .......................................... 50 3.4. Tổng kết dữ liệu bằng cách phân cụm ..................................................................... 51 3.5. Kỹ thuật phân cụm bán giám sát .............................................................................. 52 3.6. Kỹ thuật phân cụm bán giám sát dựa trên giải thuật di truyền ................................ 54 6 3.6.1. Giảm dữ liệu và gieo hạt ................................................................................ 54 3.6.2. Thuật toán phân cụm dựa trên giải thuật di truyền ........................................ 55 CHƯƠNG 4: KẾT QUẢ THỬ NGHIỆM THUẬT TOÁN ............................... 58 4.1. Giới thiệu ................................................................................................................. 58 4.2. Chương trình và dữ liệu thử nghiệm ........................................................................ 58 4.2.1. Module 1 ......................................................................................................... 58 4.2.2. Module 2 ......................................................................................................... 60 4.3. Kết quả thử nghiệm .................................................................................................. 70 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .................................................................72 TÀI LIỆU THAM KHẢO........................................................................................... 73 7 DANH MỤC CÁC HÌNH VẼ Hình 1.1: Các giai đoạn trong bài toán gom cụm .......................................................... 11 Hình 1.2: Hiển thị nhị phân của một chữ cái viết tay .................................................... 13 Hình 1.3: Thuật toán K-Means ...................................................................................... 17 Hình 1.4: Quá trình phân cụm tập điểm thành 3 cụm theo k-means ............................. 17 Hình 1.5: Thuật toán K-medoid..................................................................................... 18 Hình 1.6: Quá trình phân cụm tập điểm thành 3 cụm theo k- medoids ........................ 18 Hình 1.7: phân cụm phân cấp dạng tích lũy và phân chia trên các đối tượng dữ liệu .. 20 Hình 1.8: Một cây cấu trúc CF ...................................................................................... 21 Hình 1.9: Phương pháp Chameleon .............................................................................. 23 Hình 1.10: Phạm vi mật độ và sự liên kết mật độ trong phân cụm dựa trên mật độ ..... 25 Hình 1.11: Phân cụm dựa trên phương pháp mật độ ..................................................... 27 Hình 1.12: Ba tầng liên tiếp nhau của cấu trúc STING ................................................. 27 Hình 1.13: CLIQUE xác định các vùng tiềm năng dựa trên các đơn vị dày đặc .......... 28 Hình 1.14: Thuật toán Seeded-Kmeans ......................................................................... 31 Hình 1.15: Thuật toán Constrained-Kmeans ................................................................. 32 Hình 1.16: Chi tiết thuật toán COP-Kmeans ................................................................. 33 Hình 2.1: Sơ đồ cấu trúc thuật toán di truyền ................................................................ 35 Hình 2.2: Minh họa cho bánh xe sổ số với quần thể có 5 cá thể ................................... 37 Hình 3.1: Ba giai đoạn chính trong quá trình tóm tắt dữ liệu quan hệ .......................... 44 Hình 3.2: Liên kết một-nhiều giữa hai quan hệ ............................................................. 45 Hình 3.3: Một tập dữ liệu trong cơ sở dữ liệu quan hệ với hai mối quan hệ 1:n .......... 45 Hình 3.4: Biến đổi dữ liệu trong bảng tham chiếu với thuộc tính đơn .......................... 48 Hình 3.5: Dữ liệu được lưu trong bảng tham chiếu với nhiều thuộc tính ..................... 50 Hình 4.1: Giao diện module tạo vecto ........................................................................... 60 Hình 4.2 : Giao diện module phân cụm các vecto......................................................... 68 Hình 4.3: Giao diện Borland C++ builder tạo chương trình ......................................... 69 Hình 4.4: Mô hình quan hệ của dữ liệu thử nghiệm ...................................................... 70 8 DANH MỤC BẢNG BIỂU Bảng 3.1 : Danh sách các mẫu được tạo ra ................................................................... 49 Bảng 3.2: Thiết lập các giá trị của hai đại lượng vô hướng β and α ............................ 57 Bảng 4.1: Tỷ lệ bón phân ............................................................................................. 70 Bảng 4.2: So sánh kết quả thử nghiệm các thiết lập........................................................ 70 9 MỞ ĐẦU Trong thời đại hiện nay, cuộc cách mạng về khoa học và công nghệ đã có những bước phát triển vượt bậc, đánh dấu những mốc son đáng tự hào trong nền văn minh của thế giới. Đóng góp một phần cho sự thay đổi này, không thể kể không kể đến các ngành đã và đang được xem là mũi nhọn hiện nay như: Công nghệ thông tin, điện tử và truyền thông, công nghệ sinh học… với những ứng dụng rộng rãi, đem lại những lợi ích to lớn cho các ngành khoa học khác và các hệ thống phục vụ cho đời sống, kinh tế, xã hội. Cùng với sự phát triển này, một lượng dữ liệu ngày càng lớn và vô cùng phong phú đã được tạo ra. Với các kho dữ liệu khổng lồ như vậy, các thông tin yêu cầu từ nó không đơn thuần là các số liệu, mà đòi hỏi thêm ở mức cao hơn là các tri thức có thể hỗ trợ ra quyết định cho người dùng. Đã có rất nhiều các công trình nghiên cứu về việc tổ chức các kho dữ liệu, các thuật toán nhận dạng mẫu, và phân lớp ảnh, các hệ thốn thông tin lớn, các hệ hỗ trợ ra quyết định, …được công bố và ứng dụng. Một khái niệm mới là Data mining ra đời và mở ra những xu hướng mới trong công nghệ khám phá tri thức hiện nay. Một trong các hướng nghiên cứu của Data mining là Phân cụm dữ liệu. Bài toán phân cụm dữ liệu thuộc lĩnh vực học không giám sát, nhằm phân tập dữ liệu thành các tập con, thỏa mãn điều kiện các đối tượng trong cùng một tập con có độ tương đồng cao, và ngược lại các đối tượng ở các tập con khác nhau thì có độ tương đồng thấp. Hay nói cách khác, bài toán phân cụm dữ liệu là bài toán khám phá cấu trúc của tập dữ liệu. Tùy theo đặc điểm cấu trúc của tập dữ liệu và mục đích sử dụng, có các phương pháp giải quyết khác nhau như: Phân cụm dựa vào phân hoạch, phân cụm theo phân cấp, phân cụm dựa vào mật độ và phân cụm dựa vào lưới. Trong đó, phương pháp phân cụm bán giám sát đươc ứng dụng khá phổ biến. Đây là phương pháp kết hợp giữa học không giám sát và học có giám sát. Trong việc giải quyết bài toán phân loại trong khai phá dữ liệu quan hệ, các phương pháp truyền thống thường yêu cầu liên kết dữ liệu được lưu trong nhiều bảng thành một bảng duy nhất. Khi đó, bảng dữ liệu thu được sẽ có kích thước vô cùng lớn. Để truy vấn, phải sử dụng các phép toán đại số quan hệ và tối ưu các phép toán này bằng phương pháp tối ưu truy vấn heuristic tức là tìm cách thực hiện các phép chiếu, phép chọn trước các phép toán 2 ngôi. Trong một số trường hợp khi nối nhiều bảng sẽ gây mất thông tin hoặc trùng lặp dữ liệu. Do đó, chuyển đổi dữ liệu trở thành phức tạp và tóm tắt dữ liệu thường kém hiệu quả. Mặt khác, việc áp dụng các phương pháp tóm tắt dữ liệu trong khai phá dữ liệu được lưu trên nhiều bảng có quan hệ một-nhiều thường bị hạn chế do sự phức tạp của lược đồ cơ sở dữ liệu. Để có thể khắc phục được các vấn đề nêu trên, luận văn sẽ nghiên cứu một phương pháp tiếp cận: Sử dụng kỹ thuật phần cụm bán giám sát dựa trên giải thuật di 10 truyền để tóm tắt dữ liệu được lưu trong nhiều bảng. Nghiên cứu này dựa trên ý tưởng nghiên cứu của Rayner Alfred [17]. Kết quả của thuật toán được áp dụng phân cụm cho dữ liệu thử nghiệm năng suất lúa. Ngoài phần kết luận và các phụ lục, phần còn lại của luận văn được chia thành 4 chương chính: Chương I - Tổng quan về phân cụm dữ liệu. Giới thiệu 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. Với mỗi phương pháp phân cụm sẽ trình bày một số thuật toán tương ứng. Chương II – Giải thuật di truyền. Chương này trình bày về giải thuật di truyền với các cách biểu diễn dữ liệu, cách xây dựng một giải thuật di truyền và mô tả các phép toán thực hiện trên đó. Tiếp theo là phân tích ứng dụng của giải thuật di truyền trong bài toán phân cụm. Chương III – Tóm tắt dữ liệu quan hệ sử dụng phương pháp phân cụm bán bán giám sát dựa trên giải thuật di truyền. Chương này đi sâu phân tích khái niệm, cấu trúc quan hệ các bảng trong cơ sở dữ liệu, cách chuyển đổi dữ liệu. Thông qua đó luận văn trình bày thuật toán phân cụm bán giám sát dựa trên giải thuật di truyền để tóm tắt dữ liệu. Chương IV - Kết quả cài đặt thử nghiệm thuật toán. Chương này trình bày các kết quả thực nghiệm về phương pháp tóm tắt dữ liệu quan hệ sử dụng thuật toán phân cụm bán giám sát dựa trên giải thuật di truyền. Chương trình cài đặt thử nghiệm cho thuật toán được thực hiện bằng ngôn ngữ C++ trên tập dữ liệu thử nghiệm về năng suất lúa. Thông qua các nhận xét về giá trị các độ đo đánh giá, kết quả thực hiện chương trình là khả quan. Phần Kết luận trình bày tổng hợp các kết quả thực hiện luận văn và phương hướng nghiên cứu tiếp theo về các nội dung của luận văn. Mặc dù đã có một môi trường làm việc tương đối đầy đủ và thuận tiện, nhưng luận văn chắc hẳn sẽ không tránh khỏi có nhiều thiếu sót. Rất mong được sự đóng góp ý kiến, nhận xét để tôi có thể hoàn thiện được kết quả làm việc của mình. 11 CHƯƠNG 1: 1.1. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU Giới thiệu Phân cụm dữ liệu là một kỹ thuật quan trọng trong khai phá dữ liệu và được ứng dụng rộng rãi và đa dạng trong các ngành khoa học như sinh học, tâm lý học, y học, ngành marketing, điều khiển học v.v. Phân cụm dữ liệu tổ chức dữ liệu bằng cách nhóm các đối tượng có độ tương đồng cao để khám phá cấu trúc của dữ liệu mà không yêu cầu các giả thiết cho trước từ các phương pháp thống kê. Mục tiêu của phương pháp phân cụm dữ liệu là tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định. Bài toán phân cụm là bài toán phân loại tập mẫu dữ liệu ra thành nhiều nhóm dựa vào độ tương tự giữa các mẫu. Các mẫu trong cùng cụm giống nhau hơn so với các mẫu thuộc cụm khác. Hiện nay, có rất nhiều kỹ thuật phân cụm dữ liệu. Sự khác nhau giữa những kỹ thuật là phương pháp biểu diễn dữ liệu, phương pháp đo độ tương tự giữa các mẫu dữ liệu, và phương pháp gom các mẫu dữ liệu thành các cụm. Như vậy, bài toán gom cụm bao gồm ba giai đoạn chính như mô tả trong hình 1.1: Hình 1.1: Các giai đoạn trong bài toán gom cụm Giai đoạn đầu tiên là quá trình chọn lựa, rút trích những đặc điểm nổi bật nhất của mẫu dữ liệu. Ví dụ, dữ liệu là hình ảnh thì màu sắc và hình dạng có thể được xem là những đặc điểm nổi bật của chúng. Tiếp theo là quá trình đo độ tương tự giữa các mẫu dữ liệu, thường được đo bằng một hàm xác định khoảng cách giữa từng cặp mẫu. Có nhiều phương pháp đo khoảng cách khác nhau, trong đó, khoảng cách Euclidean là phương pháp đơn giản và thường được sử dụng để đo độ khác nhau giữa hai mẫu ([4]). Trong mô hình không gian vectơ, khoảng cách Cosine được sử dụng phổ biến để đo độ tương tự giữa hai vectơ. Cuối cùng là bước gom các mẫu thành nhiều cụm khác nhau dựa vào một giải thuật gom cụm nào đó. Trong nhiều loại giải thuật gom cụm, KMeans là giải thuật phân hoạch phổ biến ([8]). Ưu điểm của K-Means là có thể được áp dụng cho tập dữ liệu lớn mà vẫn có hiệu quả về thời gian chạy. Độ phức tạp tính toán của K-Means là O(kn) với k là số cụm và n là số mẫu dữ liệu. Các vấn đề liên quan tới 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 12 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ì chúng ta còn phải xây dựng hàm đánh giá phù hợp để thuật toán cho ra kết quả phân cụm tốt. 1.2. Biểu diễn dữ liệu Điều kiện đầu tiên của tất cả các ứng dụng áp dụng thuật toán phân cụm dữ liệu là trích chọn các đặc trưng cần thiết của các đối tượng trong tập dữ liệu liệu thực, các đối tượng phải được biểu diễn dưới dạng dữ liệu, tức chúng ta phải xác định các kiểu dữ liệu cho các thuộc tính của đối tượng. Các thuật toán phân cụm được áp dụng cho từng kiểu dữ liệu. Phân cụm dữ liệu là một công cụ để khai thác dữ liệu và phải được bổ sung các kỹ thuật để hiển thị dữ liệu. Hầu hết việc hiển thị dữ liệu là các biểu đồ biểu diễn dữ liệu trong không gian 2 chiều để biểu diễn các đối tượng. Dữ liệu nhiều chiều không phải luôn luôn chính xác khi tạo ra hiển thị bởi một dãy các biểu đồ trong hai chiều, nhưng với tính hợp lệ thì việc biểu diễn này sẽ thuận lợi cho quá trình kiểm chứng các kết quả của các thuật toán phân cụm dữ liệu. Kiểu dữ liệu cung cấp mức độ lượng hóa dữ liệu. Một đặc trưng có thể là kiểu nhị phân, có kiểu rời rạc, hoặc liên tục. Các đặc trưng kiểu nhị phân có chính xác hai giá trị. Đặc trưng nhận giá trị rời rạc là đặc trưng có hữu hạn giá trị, lực lượng của tập giá trị mà đặc trưng rời rạc nhận được thường là nhỏ. Ví dụ các mẫu của tín hiệu tiếng nói được lượng hóa bởi 24 mức, vì vậy biểu điễn một đặc trưng cho một mẫu có thể được mã hóa bởi 4 bít. Tất cả các đại lượng và các số được lưu trong máy tính với số lượng hữu hạn các số có nghĩa, vì vậy, nói đúng ra tất cả các đặc trưng đều nhận giá trị rời rạc. Tuy nhiên, thường thuật tiện hơn khi nghĩ rằng khi giá trị đặc trưng như là một điểm trên đường thẳng thực, một điểm có thể nhận một giá trị thực bất kỳ trong một miền giá trị xác định. Do đó, đặc trưng này được gọi đặc trưng nhận giá trị liên tục. Tính chất thứ hai của đặc trưng là mức tỷ xích dữ liệu, nó cho biết ý nghĩa của các số. Mức tỷ xích dữ liệu có thể phân chia thành mức tỷ xích định tính (định danh và số thứ tự) và mức tỷ xích định lượng (khoảng, tỷ lệ). Mức tỷ xích định danh chỉ đơn giản là các số được sử dụng như là các tên. Ví dụ, câu trả lời (yes, no) có thể được mã hóa là (0,1) hoặc (1,0) hoặc (50,100); các số này không mang một ý nghĩa nào trong việc định tính. Với mức tỷ xích theo số thứ tự, mức chia số yếu nhất, các số chỉ mang một ý nghĩa với một số khác. Ví dụ các mức tỷ xích (1,2,3), (10,20,30) là tương đương theo các quan điểm của số thứ tự. Các đặc trưng và các chỉ số tương đồng nhận giá trị nhị phân và giá trị rời rạc có thể được mã hóa trên những mức tỷ xích định tính này. Tỷ xích mạnh nhất là tỷ xích theo tỷ lệ, các số mang một ý nghĩa tuyệt đối. Điều này có nghĩa là số 0 tồn tại với một đơn vị đo lường, vì vậy tỷ lệ giữa hai số mang ý nghĩa. Ví dụ, khoảng cách giữa hai thành phố được ước lượng trong đơn vị là mét, dặm, hoặc là inches. 13 Khi đã xác định được kiểu dữ liệu các đặc trưng của các các đối tượng. Chúng ta phải đưa ra cấu trúc dữ liệu để biểu diễn tập đối tượng cần phân cụm. Thông thường tập dữ liệu được biểu diễn dưới dạng ma trận gọi là ma trận mẫu. Chúng ta có thể đưa ra khái niệm về ma trận mẫu như sau: Nếu mỗi đối tượng trong một tập gồm n đối tượng được biểu diễn bởi một tập d thuộc tính, mỗi đối tượng được xem như một mẫu, hay là một vectơ d chiều. Tập hợp này được xem như một ma trận mẫu kích thước n*d. Mỗi dòng của ma trận này xác định một mẫu và mỗi cột tương ứng với một đặc trưng d. N mẫu là các điểm nằm trong không gian d chiều, không gian này còn được gọi là không gian mẫu. Chúng ta sử dụng từ “mẫu” như là một điểm trong không gian mẫu, không mô tả tôpô của các đối tượng. Một cụm được biểu diễn là một tập các mẫu gần nhau hoặc là các đối tượng thỏa mãn các quan hệ không gian. Nhiệm vụ của các thuật toán phân cụm dữ liệu là nhận ra các nhóm tự nhiên trong các không gian nhiều chiều. Một tiện lợi của phân cụm dữ liệu là giúp chúng ta tổ chức dữ liệu nhiều chiều khi dữ liệu không thể biểu diễn trong 2 hoặc 3 chiều. Hình 1.2: Hiển thị nhị phân của một chữ cái viết tay 1.3. Độ 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ự hay độ tương đồng cao 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 hoặc khác nhau giữa chúng theo một ý nghĩa nào đó. Khoảng cách giữa các đối tượng càng nhỏ thì độ tương đồng càng cao. Có rất nhiều hàm được dùng để biểu diễn độ tương đồng giữa các đối tượng. Tuy nhiên, trong khuôn khổ của luận văn chỉ trình bày một số hàm 14 đo tương đồng phổ biến gọi là các hàm khoảng cách. 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 các tính chất sau: 1. 2. 3. 4. d(i,i)=0 với mọi i. d(i,k)=d(k,i) với mọi cặp (i,k). d(i,k)>=0 với mọi cặp (i,k). d(i,j)<=d(i,k)+d(k,j) với mọi i,j,k Hàm đánh giá độ tương đồng có thể được xác định theo một số cách. Giả sử rằng chúng ta có một ma trận mẫu [xij] với xij là giá trị của đặc trưng thứ j của mẫu i. Tất cả các đặc trưng là liên tục và được ước lượng theo tỷ xích tỷ lệ. Hàm khoảng cách phổ biến là khoảng cách Minkowski [1] dùng để ước lượng độ bất tương đồng. Mẫu thứ i tương ứng với dòng thứ i của ma trận mẫu được ký hiệu là một vector cột xi. xi  ( xi1 , xi 2 ,....., xin ) T , i  1,2,..., n Với d là số đặc trưng, n là số lượng mẫu, T ký hiệu là vector chuyển vị. Khoảng cách Minkowski được định nghĩa như sau: d d (i, k )  ( | xij  x kj | r )1 / r với r>=1 j 1 Các hàm khoảng cách Minkowski thỏa mãn tính chất các tính chất sau: 1. d(i,k)=0 nếu và chỉ nếu xi=xk 2. d(i,k)  d (i, m)  d (m, k ) với mọi (i,m,k) Có ba khoảng cách phổ biến sử dụng khoảng cách Minkowsky được định nghĩa như sau: Khoảng cách Euclidean (r=2): d d (i, k )  ( | xij  x kj | 2 )1 / 2  [( xi  x k ) T ( xi  x k )]1 / 2 j 1 Khoảng cách Manhattan (r=1) d d (i, k )  ( | xij  x kj | ) j 1 Khoảng cách Max (r  ): 15 max d (i, k )  ( | xij  x kj |) 1 j  d Khoảng cách Euclidean được dùng phổ biến nhất trong các chuẩn theo khoảng cách Minkowski. Các khái niệm hình học quen thuộc về tính bất biến của phép tịnh tiến và phép quay của không gian mẫu phù hợp với chuẩn Euclidean. Các ứng dụng cụ thể tác động lớn đến việc chọn ra hàm khoảng cách nào được sử dụng. Ngoài các hàm khoảng cách được sử dụng để đánh giá độ tương đồng của các đối tượng nêu trên còn có rất nhiều cách đánh giá độ tương đồng khác, tùy thuộc vào tính chất của tập dữ liệu. Để biểu diễn độ tương đồng của tất cả các đối tượng trong tập dữ liệu, người ta thường sử dụng ma trận để lưu lại giá trị tương đồng giữa các cặp đối tượng. Ma trận này được gọi là ma trận tương đồng. Có thể đưa ra khái niệm về ma trận tương đồng như sau: Ma trận tương đồng [d(i,j)] lưu giá trị tương đồng trong một ma trận, mỗi dòng và mỗi cột của ma trận biểu diễn một mẫu. Trong đó d(i,j) là độ tương tự giữa mẫu thứ i và mẫu thứ j. Chúng ta bỏ qua các giá trị nằm trên đường chéo chính của ma trận tương đồng khi giả sử rằng tất cả các mẫu có cùng mức độ tương đồng với chính nó. Giả sử rằng ma trận tương đồng là ma trận có tính đối xứng, tất cả các cặp đối tượng có cùng một giá trị tương đồng, không phụ thuộc vào thứ tự sắp xếp. Một ma trận tương đồng có thể được gọi là ma trận độ tương tự hoặc cũng có thể gọi là ma trận bất tương đồng. Các giá trị tương đồng có thể nhận giá trị nhị phân, rời rạc hoặc nhận giá trị liên tục. Ví dụ, giả sử rằng một tập đối tượng được phân hoạch vào các tập con. Giá trị nhị phân đo độ tương đồng phân nhận giá trị 0 với các cặp đối tượng ở hai tập con khác nhau và nhận giá trị bằng 1 với các cặp ở cùng một tập con. Nếu giá trị tương đồng là một số nguyên từ 1 tới n(n-1)/2 với n là số lượng các đối tượng được xem là ma trận tương đồng nhận giá trị rời rạc. Nếu ma trận tương đồng mà các phần tử nhận giá trị là khoảng cách Euclidean giữa các mẫu trong không gian mẫu thì được xem là ma trận tương đồng nhận giá trị liên tục[5] Các thuật toán phân cụm nhóm các đối tượng, hay các dữ liệu thành phần dựa trên độ tương đồng giữa các cặp đối tượng. Các đối tượng được gọi là các điểm, các trường hợp, các thành phần trong các ứng dụng khác nhau. 1.4. Các phương pháp phân cụm dữ liệu không giám sát Phân cụm dữ liệu biểu diễn mỗi quan hệ giữa các đối tượng trong ma trân tương đồng. Nếu các đối tượng được đặc tả như là các mẫu hoặc các điểm trong không gian metric, thì độ tương đồng có thể là khoảng cách giữa các cặp đối tượng, như là khoảng cách Euclidean. Ma trận mẫu và ma trận tương đồng là những dữ liệu vào cho các 16 thuật toán phân cụm. Đã có rất nhiều thuật toán phân cụm được xây dựng nhằm áp dụng vào các mục đích cụ thể. Các thuật toán này có thể được phân theo một trong bốn phương pháp sau đây: 1.4.1. Phương pháp dựa vào phân hoạch Phương pháp phân cấp. Phương pháp dựa trên mật độ. Phương pháp dựa trên lưới. Các phương pháp phân hoạch Cho một cơ sở dữ liệu của n đối tượng hoặc dòng dữ liệu, một phương pháp phân cụm tạo ra k cụm của dữ liệu, trong đó mỗi vùng biểu diễn một cụm, và k  n . Phương pháp này phân chia dữ liệu vào k nhóm, đáp ứng những yêu cầu sau: (1) mỗi nhóm phải chứa ít nhất một đối tượng và, (2) mỗi đối tượng phải thuộc duy nhất một nhóm [1]. Chú ý rằng yêu cầu thứ hai có thể bỏ qua trong một số kĩ thuật được miêu tả ở phần dưới. Đưa ra k là số lượng cụm để xây dựng, một phương thức phân cụm cần khởi tạo cụm. Sau đó sử dụng một kỹ thuật định vị trí lặp lại để cố gắng tăng sự cụm bằng cách rời các đối tượng từ một nhóm tới một nhóm khác. Tiêu chuẩn chung của một sự phân cụm tốt là các đối tượng trong cùng vùng là gần giống hoặc liên quan đến những đối tượng khác, trong khi các đối tượng của các cụm khác nhau lại rất khác nhau. Có rất nhiều kiểu tiêu chuẩn dành cho việc đánh giá chất lượng cụm. Để có được sự tối ưu toàn diện trong cụm dựa trên sự phân cụm sẽ đòi hỏi số lượng cực lớn của mọi sự phân cụm có thể. Thay vào đó, hầu hết các ứng dụng chấp nhận một trong hai phương pháp heuristic phổ biến: thuật toán k-means, nơi mỗi cụm được biểu diễn bởi giá trị trung bình của các giá trị trong cụm; và thuật toán kmedoids, trong đó mỗi cụm được biểu diễn bởi một trong các đối tượng gần trung tâm của cụm. Các phương thức cụm heuristic này làm việc tốt khi tìm kiếm các cụm hình cầu trong cơ sở dữ liệu nhỏ hoặc trung bình. Khi tìm kiếm các cụm với hình dạng phức tạp và cho tập dữ liệu lớn, các phương pháp phân cụm trên cần phải mở rộng. 1.4.1.1 Phương pháp k-means Thuật toán K-Means [8] do MacQueen đề xuất năm 1967 thực hiện như sau. h h1 cho K cụm, mỗi K Bước 1. Khởi tạo K phần tử đại diện cụm Cj . j làm tâm cho Bước 2. Lặp lại nhiều lần quá trình gắn nhãn cho đối tượng vào cụm có tâm gần nó nhất và tính lại tâm cho đến khi các cụm không có thay đổi so với vòng lặp trước. 17 Thuật toán: K-Means. Đầu vào: Tập các đối tượng dữ liệu X  x1 ,..., xN  , xi d , Số lượng cụm: K Đầu ra: K phân hoạch tách rời:  X h h1 của X sao cho hàm mục tiêu được tối ưu. Các bước: K 1. Khởi tạo các cụm: các tâm ban đầu h(0)  được chọn ngẫu nhiên t0 h 1 K 2. Lặp cho tới khi hội tụ Gán cụm: Gán mỗi đối tượng dữ liệu x vào cụm h* (tức là tập Ước lượng tâm:  h(t 1) t  t+1 X  K ( t 1) h* h 1 ) với h*= argmin || x   h( t ) ||2 1   (t1) x | X h(t 1) | xX h Hình 1.3: Thuật toán K-Means Basu và các cộng sự [1]đã chỉ ra rằng thuật toán này có thể xem là thuật toán EM (Expectation-Maximization) với X là tập dữ liệu trộn từ K nguồn dữ liệu có phân bố chuẩn nhiều chiều. Thuật toán K-Means có ưu điểm là độ phức tạp tính toán nhỏ O (NKnt), trong đó t là số lần lặp, nhưng có nhược điểm cơ bản là: cần xác định trước số lượng cụm, thuật toán thường chỉ hội tụ tới cực tiểu địa phương của (1) và kết quả tùy thuộc vào các tâm khởi tạo được chọn. Để giảm các hạn chế này, người ta dùng các thông tin bổ trợ trên một tập con dữ liệu được khảo sát kỹ hơn và thực hiện phân cụm bán giám sát như Seeded-Kmeans, Constrained-Kmeans[12]. Thuật toán cố gắng xác định k cụm mà tối thiểu hóa hàm mục tiêu đưa ra. Phương thức này có khả năng mở rộng và hoạt động hiệu quả trong khi xử lý các tập dữ liệu lớn bởi vì độ phức tạp tính toán của thuật toán là O (knt), trong đó n là tổng số đối tượng, k là số cụm, và t là số lần lặp lại, thông thường k < - Xem thêm -