- Phân cụm dữ liệu định danh với số chiều cao. - Giới thiệu về khám phá tri thức và phân cụm dữ liệu. - Tìm hiể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. - 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á. - 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. - 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 (Bottom-Up) hoặc trên xuống (Top-Down). - 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. - Đ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 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ữ 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. - 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. - 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. - 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. - 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... - Dữ liệu định danh Content.. - 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. - 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. - 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.. - 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. - Đối với phương pháp được phát triển dựa trên quan niệm về mật độ. - 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. - Ở 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.. - 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.. - 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.