Phân cụm dữ liệu định danh với số chiều cao - Phan, Thị Luân (2016)
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á. 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 (Bottom-Up) 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ữ 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. Đưa ra 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..