PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN TẬP THÔ VÀ GIẢI THUẬT DI TRUYỀN

Abstract

Phân cụm dữ liệu là một trong những nghiên cứu quan trọng trong khai thác dữ liệu và đƣợc áp dụng cho đa lĩnh vực [7,8]. Mục tiêu chính trong phân cụm dữ liệu là để phân loại các đối tƣợng không có nhãn thành nhiều cụm mà các đối tƣợng thuộc cùng một cụm thì tƣơng tự nhau và khác nhau đối với các cụm khác nhau. Phân cụm dữ liệu đƣợc chia làm hai loại là phân cụm dữ liệu cứng/rõ (mỗi điểm dữ liệu chỉ thuộc về một cụm) và phân cụm dữ liệu mềm/mờ (mỗi điểm dữ liệu có thể thuộc về nhiều hơn một cụm dựa vào một xác suất nhất định) [12,15]. Một kỹ thuật đƣợc sử dụng phổ biến trong phân cụm dữ liệu là thuật toán K-Means, thuộc phân cụm rõ, với sự hội tụ nhanh chóng và khả năng tìm kiếm địa phƣơng mạnh mẽ. Trong quá trình phân cụm K-Means truyền thống, các đối tƣợng dữ liệu thu đƣợc trong cụm là nhất định. Tuy nhiên, trong thực tế giữa những đối tƣợng thuộc các lớp khác nhau thƣờng không có ranh giới rõ ràng, do đó việc mô tả bộ dữ liệu thực là khó khăn. Giải pháp cho những đối tƣợng này đƣợc cung cấp bởi lý thuyết tập thô, là phƣơng pháp tính toán mềm trong khai thác dữ liệu. Để tăng hiệu quả và kết quả chính xác cho phân cụm việc sử dụng lý thuyết tập thô tiếp cận hỗ trợ phân cụm K-Means đã đƣợc đề xuất, xây dựng nên phƣơng pháp phân cụm K-Means thô. Mặc dù giải thuật K-Means thô có khả năng tìm kiếm địa phƣơng mạnh mẽ nhƣng lại dễ rơi vào cực trị địa phƣơng. Một trong những biện pháp có thể khắc phục đƣợc hạn chế này là kết hợp với giải thuật di truyền. Thuật toán di truyền là một thuật toán tìm kiếm ngẫu nhiên với kỹ thuật tối ƣu toàn cầu dựa trên nguyên tắc của sự tiến hóa sinh học, có lƣợng lớn số song song tiềm ẩn thực hiện không gian tìm kiếm lớn và cung cấp giải pháp tối ƣu hóa toàn cầu giúp tránh đƣợc tối ƣu địa phƣơng.