Mối liên quan giữa khái niệm tính bao đóng bắc cầu Min - Max với thuật toán phân cụm theo khoảng cách độ đo

Trong nội dung của bài viết này, tác giả trình bày một số khái niệm lí thuyết về quan hệ mờ quan trọng; chỉ ra có thể vận dụng tính chất của nó để đề xuất thuật toán phân cụm theo khoảng cách độ đo và tiến hành triển khai tường minh các bước giải thuật phân cụm theo khoảng cách độ đo.
Nội dung trích xuất từ tài liệu:
Mối liên quan giữa khái niệm tính bao đóng bắc cầu Min - Max với thuật toán phân cụm theo khoảng cách độ đo JOURNAL OF SCIENCE OF HNUE Natural Sci., 2014, Vol. 59, No. 4, pp. 96-105 This paper is available online at http://stdb.hnue.edu.vnMỐI LIÊN QUAN GIỮA KHÁI NIỆM TÍNH BAO ĐÓNG BẮC CẦU MIN - MAX VỚI THUẬT TOÁN PHÂN CỤM THEO KHOẢNG CÁCH ĐỘ ĐO Phạm Thanh Huyền Bộ môn Tin học, Khoa Tự nhiên, Trường Cao Đẳng Sư phạm Quảng Ninh Tóm tắt. Điểm giống nhau mà hầu hết các thuật toán phân cụm theo độ đo khoảng cách (thuật toán k-means, thuật toán c-means) là đều phụ thuộc vào khả năng chọn số cụm và tập tâm cụm ban đầu. Điều này ảnh hưởng lớn đến hiệu quả thực hiện của thuật toán, thậm chí dẫn đến kết quả thu được không có chất lượng. Trong bài báo này, chúng tôi xây dựng thuật toán phân cụm dựa vào khoảng cách Min - Max (tạm đặt tên là thuật toán phân cụm theo khoảng cách Min - Max). Thuật toán này được đảm bảo hiệu quả dựa vào tính chất độ đo khoảng cách Euclide (hoặc khoảng cách Hamming) và vận dụng khái niệm tính bao đóng Min - Max. Nói cách khác, chúng tôi đề xuất xây dựng thuật toán phân cụm theo khoảng cách Min - Max không phụ thuộc vào việc lựa chọn trước tập tâm cụm mà chỉ phụ thuộc vào n đối tượng cần phân cụm và việc xác định độ đo giữa các đối tượng đó. Từ khóa: Phân cụm, độ đo khoảng cách, bao đóng Min - Max1. Mở đầu Phân cụm (Clustering) là sắp xếp các đối tượng theo từng cụm dữ liệu tự nhiên, tứclà số lượng và tên cụm chưa được biết trước. Các đối tượng được gom cụm sao cho mứcđộ tượng tự giữa các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữacác đối tượng nằm trong các cụm khác nhau là nhỏ nhất. Phân cụm được sử dụng rộng rãitrong nhiều ứng dụng như nhận dạng mẫu, phân tích dữ liệu, xử lí ảnh, nghiên cứu vũ trụ,nén ảnh và phân khúc ảnh. Trong thực tế, người ta đã áp dụng lí thuyết tập mờ trong phâncụm dữ liệu để giải quyết những kiểu đối tượng này [2]. Phân cụm phân tích các đối tượng dữ liệu khi chưa biết nhãn của lớp. Nhãn của cáclớp không tồn tại trong suốt quá trình huấn luyện dữ liệu. Việc phân cụm sẽ xác định nhãncủa lớp. Mỗi cụm được tạo thành có thể xem như một lớp đối tượng có cùng quy tắc tạora nó. Do đó, để giải được bài toán phân cụm việc cuối cùng phải xác định được bản chấtnhóm đối tượng trong tập dữ liệu chưa có nhãn. Tuy nhiên, việc giải bài toán này vẫn đangNgày nhận bài: 25/4/2014. Ngày nhận đăng: 21/5/2014.Tác giả liên lạc: Phạm Thanh Huyền, địa chỉ e-mail: phamthanhhuyen34@gmail.com.96 Mối liên quan giữa khái niệm tính bao đóng bắc cầu Min - Max với thuật toán...còn là vấn đề khó và mở, vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phùhợp với nhiều dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càngtăng trong các hệ quản trị dữ liệu. Một số yếu tố cần quan tâm của bài toán phân cụm đó là nhạy cảm với các kiểu dữliệu khác nhau, có khả năng mở rộng, hình dạng các cụm không ấn định, dễ bị ảnh hưởngcủa các kết quả dữ liệu nhiễu. Trong lí thuyết quan hệ mờ, khái niệm bao đóng bắc cầu Min - Max và quan hệ bấttương đương đã được [2] nêu là căn cứ để phân cụm dữ liệu. Trong [3] có chỉ rõ khả năngứng dụng các khái niệm này trong phân cụm nhưng chưa trình bày tường minh các bướcgiải thuật phân cụm. Từ ý tưởng muốn có một thuật toán phân cụm không phụ thuộc vàoviệc lựa chọn trước tập tâm cụm (dữ liệu đầu vào) mà chỉ phụ thuộc vào n đối tượng cầnphân cụm và việc xác định độ đo giữa các đối tượng đó, chúng tôi đề xuất bổ sung thêmràng buộc về quan hệ bất tương đương, tính chất bao đóng bắc cầu để đảm bảo tính hiệuquả của thuật toán và tường mình các bước thực hiện phân cụm dữ liệu mà trong [2, 3]chưa trình bày. Trong nội dung của bài viết này, chúng tôi trình bày một số khái niệm líthuyết về quan hệ mờ quan trọng; chỉ ra có thể vận dụng tính chất của nó để đề xuất thuậttoán phân cụm theo khoảng cách độ đo và tiến hành triển khai tường minh các bước giảithuật phân cụm theo khoảng cách độ đo. Ở đây, chúng tôi không chỉ xác định được tínhdừng của giải thuật mà còn chứng minh được những căn cứ đúng đắn về xây dựng hệ tiêuchuẩn trên cơ sở lí thuyết quan hệ mờ.2. Nội dung nghiên cứu2.1. Cơ sở lí thuyết về quan hệ mờ Trong số những khái niệm mờ quan trọng nhất về phương diện ứng dụng có thể có,các quan hệ mờ mở rộng khái niệm quan hệ cổ điển được định nghĩa trên các tập dữ liệu.Chúng làm nổi bật những mối liên kết không chính xác hay có cấp độ giữa các phần tửcủa cùng một tập hợp giúp cho việc tổ chức, phân loại dữ liệu hiệu quả hơn [4]. * Định nghĩa các quan hệ mờ Định nghĩa một quan hệ mờ R: Một quan hệ mờ R giữa r tập tham chiếuX1 , X2 , . . . , Xr là một tập con mờ của X1 × X2 × . . . × Xr với hàm thuộc µR . Nghịch đảo của một quan hệ mờ R giữa X và Y là qua ...