Phân cụm bán giám sát dựa trên phương pháp gieo hạt sử dụng mạng nơron min-max mờ

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

23
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết này đề cập đến vấn đề chọn hạt giống tốt cho phân cụm bán giám sát sử dụng mạng nơron min-max mờ. Các hạt giống tốt được thu thập đúng cách có thể tăng chất lượng phân cụm và giảm thiểu số lượng truy vấn từ các chuyên gia.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phân cụm bán giám sát dựa trên phương pháp gieo hạt sử dụng mạng nơron min-max mờ

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), Nha Trang, ngày 8-9/10/2020 DOI: 10.15625/vap.2020.00197 PHÂN CỤM BÁN GIÁM SÁT DỰA TRÊN PHƯƠNG PHÁP GIEO HẠT SỬ DỤNG MẠNG NƠRON MIN-MAX MỜ Vũ Đình Minh1, Lê Bá Dũng2, Lê Anh Tú3, Nguyễn Thanh Sơn4 1 Khoa Công nghệ thông tin, Trƣờng Đại học Công nghiệp Hà Nội 2 Khoa Công nghệ thông tin, Đại học Điện lực 3 Đại học Hạ Long 4 Cao đẳng Công nghiệp và Thƣơng mại Minhvd.itvn@gmail.com, l_bdung@yahoo.com, anhtucntt@gmail.com, sonnt@pci.edu.vn TÓM TẮT: Phân cụm là kỹ thuật trong khai phá dữ liệu, nó thuộc lớp các phương pháp học không có giám sát. Quá trình phân tách các nhóm theo sự tương tự của dữ liệu được gọi là phân cụm. Có hai nguyên tắc cơ bản: (i) độ tương tự là cao nhất trong một cụm và (ii) độ tương tự giữa các cụm là ít nhất. Gần đây, phân cụm bán giám sát mờ là một mở rộng của phân cụm mờ cũng nhận được nhiều sự quan tâm của các nhà khoa học. Phân cụm bán giám sát mờ sử dụng các thông tin biết trước để hướng dẫn quá trình phân cụm, từ đó làm tăng chất lượng của cụm. Các thông tin biết trước hay còn gọi là các thông tin bổ trợ nhằm mục đích hướng dẫn, giám sát và điều khiển quá trình phân cụm. Các thông tin bổ trợ có thể được xây dựng dựa trên các ràng buộc Must- link/Cannot-link, hoặc các nhãn (dạng hạt giống) đi cùng các mẫu hay độ thuộc được xác định trước. Với phương pháp gán nhãn đi cùng mẫu đòi hỏi một phần mẫu nhất định trong không gian mẫu có các nhãn đi kèm. Nhìn chung, kết quả phân cụm thường phụ thuộc vào thông tin bổ trợ được cung cấp, vì vậy thông tin bổ trợ khác nhau sẽ tạo ra kết quả khác nhau. Trong một số trường hợp, hiệu suất của phân cụm có thể giảm nếu thông tin bổ trợ không được chọn cẩn thận. Bài viết này đề cập đến vấn đề chọn hạt giống tốt cho phân cụm bán giám sát sử dụng mạng nơron min-max mờ. Các hạt giống tốt được thu thập đúng cách có thể tăng chất lượng phân cụm và giảm thiểu số lượng truy vấn từ các chuyên gia. Với mục đích này, chúng tôi đề xuất một thuật toán cho nhiệm vụ thu thập hạt giống, xác định các ứng cử viên để nhận nhãn từ các chuyên gia bằng cách sử dụng mạng nơron min-max mờ (được gọi là SCFMS). Các thực nghiệm được thực hiện trên một số bộ dữ liệu thực từ UCI, CS và bộ dữ liệu thực được thu thập từ Bệnh viện Đa khoa Trung ương Thái Nguyên cho thấy hiệu quả của SCFMS so với các phương pháp khác. Từ khóa: Choosing seeds, fuzzy min-max, neural network, semi-supervised clustering. I. GIỚI THIỆU Phân cụm bán giám sát mờ là một mở rộng của phân cụm mờ, đã nhận đƣợc nhiều nhà khoa học quan tâm nghiên cứu [7, 22, 23, 24] và đƣợc ứng dụng trong nhiều lĩnh vực nhận dạng, xử lý ảnh, xử lý thông tin… [1, 5, 16, 19]. Phân cụm bán giám sát mờ sử dụng các thông tin bổ trợ để hƣớng dẫn, giám sát và điều khiển quá trình phân cụm. Các thông tin bổ trợ có thể là các ràng buộc (Must-link/Cannot-link), hoặc các nhãn (dạng hạt giống) đi cùng các mẫu hay độ thuộc đƣợc xác định trƣớc. Với phƣơng pháp chọn giống, đòi hỏi một phần mẫu nhất định trong không gian mẫu có các nhãn đi kèm để tạo ra các cụm ban đầu và giám sát quá trình phân cụm cho các mẫu không có nhãn. Ƣu điểm của phƣơng pháp này là khả năng sử dụng một tập hợp nhỏ thông tin bổ trợ để cải thiện kết quả phân cụm. Nhìn chung, kết quả phân cụm thƣờng phụ thuộc vào thông tin bổ trợ đƣợc cung cấp, do vậy thông tin bổ trợ khác nhau sẽ tạo ra kết quả khác nhau. Trong một số trƣờng hợp, hiệu suất của phân cụm có thể giảm nếu thông tin bổ trợ đƣợc lựa chọn tồi [6, 7]. Trên thực tế, các hạt giống đƣợc chọn ngẫu nhiên để lấy nhãn từ ngƣời dùng, tuy nhiên chi phí lấy nhãn từ các chuyên gia lại tốn kém [4]. Các hạt giống tốt đƣợc thu thập đúng cách có thể tăng chất lƣợng phân cụm và giảm thiểu số lƣợng truy vấn từ các chuyên gia. Các ứng dụng trong thế giới thực đòi hỏi nhiều cách thức trung gian của việc tìm kiếm cấu trúc trong bộ dữ liệu, hiệu quả của nó có thể đƣợc tăng cƣờng đáng kể bằng cách sử dụng các thông tin biết trƣớc, chỉ với một tỷ lệ phần trăm nhỏ của các mẫu đƣợc dán nhãn cũng cải thiện đáng kể các kết quả của phân cụm [10]. Báo cáo này đề cập đến vấn đề chọn hạt giống tốt cho phân cụm bán giám sát sử dụng mạng nơron min-max mờ (FMNN). Với mục đích này, chúng tôi đề xuất một thuật toán mới cho nhiệm vụ thu thập hạt giống tốt, xác định các ứng cử viên để nhận nhãn từ các chuyên gia bằng cách sử dụng mạng nơron min-max mờ. Các hạt giống đƣợc thu thập bằng phƣơng pháp của chúng tôi có thể giảm thiểu truy vấn của ngƣời và gia tăng số lƣợng hạt giống từ đó làm tăng hiệu suất phân cụm. Tóm lại, những đóng góp của bài báo này nhƣ sau: (i) khảo sát một số phƣơng pháp nguyên tắc về phân cụm dựa trên hạt giống và các phƣơng pháp chọn hạt chủ động cho các thuật toán phân cụm dựa trên hạt giống; (ii) đề xuất thuật toán học trong mạng nơron min-max mờ để lựa chọn hạt giống tốt nhận nhãn từ các chuyên gia; (iii) thực nghiệm trên một số bộ dữ liệu thực từ UCI, CS và bộ dữ liệu thực đƣợc thu thập từ Bệnh viện Đa khoa Trung ƣơng Thái Nguyên. Phần còn lại của bài báo đƣợc sắp xếp nhƣ sau. Phần II trình bày một số nghiên cứu liên quan. Phần III giới thiệu thuật toán đề xuất thu thập hạt giống. Phần IV mô tả các thực nghiệm đã đƣợc tiến hành trên các tập dữ liệu chuẩn từ UCI, CS và tập dữ liệu thực tế đƣợc thu thập từ Bệnh viện Đa khoa Trung ƣơng Thái Nguyên. Cuối cùng, phần V là kết luận và hƣớng nghiên cứu trong tƣơng lai.
436 PHÂN CỤM BAN GIÁM SÁT DỰA TRÊN PHƢƠNG PHÁP GIEO HẠT SỬ DỤNG MẠNG RRON MIN-MAX MỜ II. CÁC NGHIÊN CỨU LIÊN QUAN A. Một số thuật toán phân cụm dựa trên phương pháp gieo hạt Trong [7], một thuật toán phân cụm dựa trên mật độ bán giám sát đƣợc trình bày. Nhóm nghiên cứu sử dụng một tập hợp nhỏ dữ liệu có nhãn đề tìm kiếm các cụm trong dữ liệu mật độ riêng biệt, bằng cách sử dụng hạt giống để tính toán bán kính thích ứng cho mỗi cụm. Trong [11], các tác giả đã đề xuất thuật toán sử dụng hạt giống trợ giúp thuật toán K-Means trong bƣớc tìm trung tâm cụm. Nhóm tác giả đã chứng minh đề xuất cho kết quả phân cụm ổn định và khắc phục đƣợc ảnh hƣởng của việc chọn trung tâm cụm ở bƣớc ban đầu nhƣ thuật toán K-Means truyền thống. Trong [8], nhóm nghiên cứu đã trình bày thuật toán học tích cực cho nhiệm vụ thu thập hạt giống, xác định các ứng cử viên để nhận nhãn từ ngƣời dùng bằng cách kết hợp thuật toán K-Means và min-max. Thuật toán K-Means đƣợc sử dụng trong bƣớc thứ nhất để xác định cụm số cụm và trong bƣớc thứ hai sử dụng phƣơng pháp tối thiểu min-max chọn các ứng cử viên để nhận nhãn từ ngƣời dùng (tối thiểu mỗi cụm sẽ nhận đƣợc 1 nhãn). Trong [15], một phƣơng pháp thu thập hạt giống dựa trên min-max đã đƣợc đề xuất, nhóm nghiên cứu gọi đó là phƣơng pháp SMM. SMM thu thập các hạt giống dựa trên chiến lƣợc tối thiểu. Ý tƣởng của SMM là xây dựng một bộ hạt giống có thể bao gồm việc phân phối dữ liệu đầu vào. Với tập dữ liệu X, SMM sử dụng phƣơng pháp lặp lại để thu thập tập hạt giống Y. Trong [8], các tác giả đã phát triển một thuật toán học tập tích cực (gọi là SKMMM) cho nhiệm vụ thu thập hạt giống, xác định các ứng viên để nhận nhãn ngƣời dùng bằng cách sử dụng các thuật toán K-Means và min-max. Ở bƣớc đầu tiên, SKMMM sử dụng thuật toán K-Means để phân vùng tập dữ liệu đầu vào thành các cụm. Trong bƣớc thứ hai, SKMMM sử dụng phƣơng pháp min-max để chọn ứng viên hạt giống để lấy nhãn từ ngƣời dùng. Số lƣợng cụm trong bƣớc thứ nhất đƣợc chọn đủ lớn, tức là lên đến √ . B. Mô hình mạng nơron min-max mờ FMNN là một mô hình học tăng cƣờng dựa trên các tập siêu hộp mờ cho phép xử lý dữ liệu lớn [9], nó kế thừa mọi ƣu điểm của phƣơng pháp học tăng cƣờng. Thứ nhất, đó là hiệu quả trong việc khám phá kiến thức; thứ hai, nó cho phép sử dụng lại và thêm nhiều thông tin hơn trong một lần chạy; thứ ba, tất cả dữ liệu đào tạo có thể đƣợc sử dụng ngay lập tức cho quá trình học tập thay vì chờ đợi một tập hợp đƣợc đào tạo lại [14]. Ngoài ra, FMNN cung cấp một quyết định linh hoạt thông qua hàm thành viên mờ. Hình 1 là một ví dụ về phân cụm của FMNN trên tập dữ liệu Aggregation từ kho dữ liệu học máy CS. Hình 1. Ví dụ về phân cụm của FMNN trên tập dữ liệu Aggregation từ kho dữ liệu học máy CS Mô hình mạng nơron min-max mờ (FMNN) đầu tiên đƣợc đề xuất đầu tiên bởi Simpson. Học trong FMNN gồm học có giám sát áp dụng cho bài toán phân lớp dữ liệu [12] và học không giám sát áp dụng cho bài toán phân cụm dữ liệu [13]. FMNN biểu diễn dữ liệu bằng các siêu hộp mờ [2]. Sự kết hợp giữa logic mờ và khả năng học của mạng nơron là điểm mạnh của FMNN khi xử lý các thông tin không chắc chắn. Do đó, các mạng FMNN có thể ứng dụng trong rất nhiều lĩnh vực nhƣ hệ chuyên gia, dự báo, điều khiển... Một siêu hộp min-max mờ là một vùng của không gian mẫu n-chiều giới hạn bởi điểm min (ký hiệu là V) và điểm max (ký hiệu là W) với các mẫu đi kèm với hàm thuộc. Hàm thuộc siêu hộp mờ mô tả mức độ thuộc của mẫu vào siêu hộp. Hàm thuộc có vai trò rất quan trọng trong các thuật toán học min-max mờ. Giá trị thành thuộc nằm trong khoảng từ 0 đến 1. Giá trị hàm thuộc đo mức độ thuộc của mẫu dữ liệu tƣơng ứng với siêu hộp. Điều này quyết định xem mẫu dữ liệu thuộc về siêu hộp cụ thể nào đó. Một mẫu đƣợc chứa trong siêu hộp nếu có giá trị hàm thuộc bằng 1. Không gian mẫu có ma trận đơn vị In, giá trị hàm thuộc bj(A) của mẫu dữ liệu A với siêu hộp Bj thứ j (j=1,2,3,…,c) mô tả mức độ thuộc của A vào Bj. Siêu hộp thứ j (Bj) định nghĩa theo (1): Bj A,V j ,W j , b j A,V j ,W j , A I n (1)
Vũ Đình Minh, Lê Bá Dũng, Lê Anh Tú, Nguyễn Thanh Sơn 437 Trong đó A là mẫu dữ liệu; Vj là điểm min của Bj, Wj là điểm max của Bj; bj(A,Vj,Wj) là độ thuộc của A với siêu hộp Bj, đƣợc định nghĩa theo (2): 1 n b j A,V j ,W j 1 f ai w ji , f v ji ai , (2) ni 1 Trong đó: Vj v j1 , v j 2 ,..., v jn ; Wj w j1 , w j 2 ,..., w jn ; là tham số điều chỉnh tốc độ giảm của giá trị hàm thuộc bj khi một mẫu vào bị tách ra khỏi siêu hộp; f(x,y) là hàm ngƣỡng hai tham số, đƣợc xác định theo (3): 1, xy 1, f x, y xy, 0 xy 1, (3) 0, xy 0. Thuật toán học trong mạng nơron min-max mờ bao gồm quá trình mở rộng và thu hẹp các siêu hộp để điều chỉnh giá trị min-max của các siêu hộp trong mẫu không gian mẫu. Giả sử tập huấn luyện D ban đầu gồm m mẫu, với Ah ah1, ah 2 ,..., ahn I n là mẫu vào thứ h (h = 1, 2,…, m) của tập D. Quá trình học bắt đầu bằng việc lựa chọn lần lƣợt các mẫu Ah D và tìm các siêu hộp gần nhất để có thể mở rộng thêm mẫu. Nếu không thể tìm thấy một siêu hộp nào thỏa mãn các tiêu chí mở rộng, một siêu hộp mới đƣợc tạo ra. Quá trình tăng trƣởng này cho phép các cụm đƣợc tinh chỉnh theo thời gian, và cho phép các cụm mới đƣợc thêm vào mà không cần đào tạo lại. Khi thực hiện mở rộng siêu hộp, gây nên sự chồng lấn giữa các siêu hộp. Sự chồng lấn siêu hộp tạo nên sự không rõ ràng, đây chính là điều gây nên sự một mẫu có giá trị hàm thuộc nhƣ nhau tới các cụm khác nhau, giá trị hàm thuộc bằng 1. FMNN thực hiện điều chỉnh co lại các siêu hộp để loại trừ sự chồng lấn. Thuật toán học gồm 4 bƣớc: Bƣớc 1: Khởi tạo các siêu hộp, Bƣớc 2: Mở rộng siêu hộp, Bƣớc 3: Kiểm tra chồng lấn các siêu hộp, Bƣớc 4: Điều chỉnh chồng lấn siêu hộp. Từ Bƣớc 2 đến Bƣớc 4 đƣợc thực hiện cho mỗi mẫu đầu vào. Thuật toán dừng khi các siêu hộp ổn định hoặc các mẫu đầu vào đƣợc duyệt hết. Sơ đồ thuật toán học FMNN đƣợc mô tả trên Hình 2. Begin D, Ah D Có siêu hộp nào chứa n được Ah? y Tạo siêu hộp Bj Mở rộng siêu hộp Có chồng n lấn siêu hộp? y Co lại siêu hộp n Dữ liệu vào đã hết? y End Hình 2. Sơ đồ thuật toán học FMNN FMNN phân cụm là mạng nơron hai lớp [13]. Lớp đầu vào, FA gồm n nút (một nút tƣơng ứng với một chiều của dữ liệu) và lớp đầu ra, FB gồm m nút (mỗi nút tƣơng ứng với một cụm). Mỗi nút đầu vào đƣợc kết nối với một thành phần của Ah. Kết nối này đƣợc thiết lập bởi cặp trọng số bao gồm min vji và max wji.
438 PHÂN CỤM BAN GIÁM SÁT DỰA TRÊN PHƢƠNG PHÁP GIEO HẠT SỬ DỤNG MẠNG RRON MIN-MAX MỜ III. PHƢƠNG PHÁP ĐỀ XUẤT Trong phần này, chúng tôi trình bày mô hình đề xuất lựa chọn hạt giống cho phân cụm bán giám sát dựa trên FMNN phân cụm. Thuật toán học xây dựng tập hạt giống lớn và với số truy vấn ngƣời sử dụng thấp. SCFMS tạo ra các siêu hộp và nhận nhãn từ ngƣời dùng cho các siêu hộp, sau đó gán nhãn cho các hạt giống có giá trị hàm thuộc đầy đủ với siêu hộp tƣơng ứng. Thuật toán sử dụng phƣơng pháp thích nghi để tự xác định giá trị kích thƣớc siêu hộp đƣợc chúng tôi đề xuất trong mô hình SS-FMM [17]. Ý tƣởng của phƣơng pháp này dựa trên kết quả nghiên cứu của chúng tôi với phân cụm bán giám sát trong mô hình mạng nơron min-max mờ SS-FMM trong [17]. Trong mô hình này, tập huấn luyện bao gồm các mẫu không có nhãn. Đầu tiên, thuật toán hình thành các cụm bằng cách sử dụng thuật toán FMNN phân cụm. Với mỗi siêu hộp đại diện cho một cụm. Sau đó nhận nhãn từ ngƣời dùng cho các siêu hộp, mỗi siêu hộp sẽ bao gồm một tập các hạt giống có giá trị hàm thuộc đầy đủ với siêu hộp tƣơng ứng. Quá trình phân cụm bán giám sát tiếp theo sẽ sử dụng tập các hạt giống nhận đƣợc từ bƣớc 1 để giám sát, hƣớng dẫn quá trình phân cụm. Quá trình học của thuật toán đề xuất nhƣ thể hiện trong Hình 3. FMNN phân cụm bán giám sát Data Siêu hộp Hạt giống Các cụm FMNN Truy vấn phân cụm người dùng SCFMS Hình 3. Thuật toán phân cụm bán giám sát sử dụng mạng nơron min-max mờ Với tập dữ liệu huấn luyện D, ở bƣớc đầu tiên, sử dụng FMNN phân hoạch D thành c siêu hộp. Với mỗi siêu hộp sẽ nhận đƣợc nhãn từ ngƣời dùng và tạo tập các hạt giống tƣơng ứng với các mẫu có giá trị hàm thuộc đầy đủ với siêu hộp tƣơng ứng. Thuật toán SCFMS thực hiện bƣớc thứ nhất, gán nhãn cho các mẫu dữ liệu từ các truy vấn ngƣời sử dụng cho các điểm tâm của siêu hộp và chọn hạt giống là các mẫu thuộc siêu hộp tƣơng ứng. Các bƣớc của thuật toán học SCFMS đƣợc trình bày trong Bảng 1. Độ phức tạp của thuật toán FMNN là O(m) do cần một lần duyệt qua tập dữ liệu để điểu chỉnh các giá trị min- max để ổn định cụm. Độ phức tạp của quá trình chọn tập hạt giống Y cần một lần duyệt qua tập dữ liệu để kiểm tra độ thuộc các mẫu trên tập các siêu hộp là O(m×k). Vậy, độ phức tạp của SCFMS là O(m)+O(m×k). Bảng 1. Thuật toán học SCFMS SCFMS Input: Tập dữ liệu D, c cụm cho FMNN; Output: Tập hạt thu đƣợc Y; 1. Xử dụng FMNN phân D thành tập các siêu hộp B gồm c siêu hộp; 2. t = 0; 3. For Ah D 4. For Bj B 5. If bj(Ah,Bj) = 1 then 6. t = t+1; 7. yt Blabel j ; 8. Y Y yt ; 9. End if; 10. End for; 11. End for; 12. Rerurn Y;
Vũ Đình Minh, Lê Bá Dũng, Lê Anh Tú, Nguyễn Thanh Sơn 439 IV. KẾT QUẢ THỰC NGHIỆM A. Tập dữ liệu thực nghiệm và phương pháp đánh giá Để đánh giá hiệu suất của thuật toán đề xuất, nhóm nghiên cứu tiến hành thực nghiệm với các tập dữ liệu chuẩn (Benchmark) từ kho dữ liệu học máy UCI [20], CS [21]. Các tập dữ liệu từ CS bao gồm: Aggregation, Flame, Spiral, Jain, R15, Pathbased, Thyroidnew. Các tập dữ liệu từ UCI bao gồm: Iris, Wine, PID (Pima Indian Diabetes), Thyroid, Sonar. Thông tin về các tập dữ liệu đƣợc trình bày trên Bảng 2. Lý do để chúng tôi chọn các tập dữ liệu này là để so sánh hiệu suất với một số thuật toán khác đã công bố trƣớc đó. Các tập dữ liệu thực nghiệm đƣợc chuẩn hóa trƣớc khi tiến hành thực nghiệm. Với các tập dữ liệu bị thiếu thông tin (missing values) đƣợc xử lý tƣơng tự Batista [3]. Để đánh giá thuật toán đề xuất, chúng tôi sử dụng độ đo Accuracy [18], tổng số truy vấn ngƣời sử dụng. Độ đo Accuracy đƣợc tính theo (4), giá trị của độ đo Accuracy càng lớn càng tốt. Giả sử xi là mẫu dữ liệu thuộc tập dữ liệu, yi là nhãn thực sự của xi, yi là các nhãn tƣơng ứng của xi theo kết quả gom cụm. 1 n Accuracy H yi yi (4) ni 1 trong đó H(y) = 1 nếu yi yi , ngƣợc lại H(y) = 0 nếu yi yi , n là tổng số mẫu trong tập kiểm tra. Bảng 2. Thông tin các tập dữ liệu thực nghiệm Benchmark ID Data #Mẫu #Thuộc tính #Cụm 1 Iris 150 4 3 2 Soybean 47 35 4 3 Zoo 101 16 7 4 Yeast 1484 8 10 5 Aggregation 788 2 7 6 Flame 240 2 2 7 Jain 373 2 2 8 R15 600 2 15 9 Spiral 312 2 3 10 Thyroidnew 215 5 3 11 Wine 178 13 3 12 Liver 500 10 3 Tập dữ liệu thực tế đƣợc thu thập là kết quả xét nghiệm công thức máu và sinh hóa máu từ bệnh viện Đa khoa Trung ƣơng Thái Nguyên đi kèm kết luật của bác sĩ về tình trạng sức khỏe gan (Liver) của bệnh nhân. Đây là dữ liệu hồi cứu, không có thông tin cá nhân của bệnh nhân. B. Kết quả thực nghiệm Trong phần này, chúng tôi trình bày kết thực nghiệm bằng cách sử dụng các thuật toán SKMMM, SMM, phƣơng pháp ngẫu nhiên (Random) [8] và SCFMS. Để đánh giá thuật toán đề xuất, chúng tôi sử dụng độ đo Accuracy để đánh giá và so sánh số các truy vấn ngƣời sử dụng phải cung cấp cho mỗi thuật toán. Hình 4 minh họa số lƣợng truy vấn ngƣời sử dụng phải cung cấp trong quá trình thực hiện của mỗi thuật toán tƣơng ứng. Nhƣ thể hiện trong hình, phƣơng pháp SCFMS cần ít truy vấn hơn phƣơng pháp SKMMM, SMM và phƣơng pháp ngẫu nhiên. Đây là một thuận lợi đáng kể của SCFMS cho các bài toán thực tế, khi mà việc lấy nhãn mất nhiều chi phí [4]. Hình 4. Số truy vấn ngƣời dùng của 4 phƣơng thức trên các tập dữ liệu thực nghiệm Hình 5 cho thấy kết quả phân cụm bằng cách sử dụng hạt của SCFMS trên FMNN và ba phƣơng pháp còn lại. Kết quả cho thấy SCFMS có hiệu suất tốt hơn trên tập dữ liệu Iris, Soybean và Zoo. Có thể giải thích rằng, SCFMS cso khả năng thu đƣợc nhiều hạt giống hơn, với ít số lần truy vấn hơn. Thuật toán phân cụm bán giám sát có khả năng cho
440 PHÂN CỤM BAN GIÁM SÁT DỰA TRÊN PHƢƠNG PHÁP GIEO HẠT SỬ DỤNG MẠNG RRON MIN-MAX MỜ kết quả tốt hơn với số mẫu đƣợc gán nhãn nhiều hơn. Hơn nữa, các hạt giống thu đƣợc của FMNN đều tập trung ở tâm cụm nên rất tốt cho quá trình hình thành cụm và giám sát quá trình phân cụm. Hình 5. So sánh độ đo Accuracy của SCFMS với các thuật toán khác Để kiểm tra khả năng của SCFMS khi thay đổi số cụm ban đầu, chúng tôi tiến hành thực nghiệm và thay đổi số cụm vào ban đầu. Hình 6, Hình 7 là biểu diễn sự biến động của độ đo Accuracy khi thay đổi số cụm c đầu vào. Giá trị của c đƣợc chọn lớn nhất không vƣợt quá √ [25]. Độ đo Accuracy bị ảnh hƣởng bởi số cụm c đƣợc chọn ban đầu. Hình 6. Sự biến động độ đo Accuracy khi thay đổi số cụm vào trên tập dữ liệu Iris, Soybean, Zoo, Wine, Thyroidnew Hình 7. Sự biến động độ đo Accuracy khi thay đổi số cụm vào trên tập dữ liệu Flame, Jain, R15, Aggregation, Sprial Hình 8 và Hình 9 là kết quả thực nghiệm thuật toán SCFMS trên tập dữ liệu Liver. Hình 8 biểu diễn sự biến động độ đo Accuracy khi thay đổi số cụm đầu vào (số cụm đƣợc chọn nhỏ hơn √ [25]). Hình 9 thống kê tỉ lệ mẫu có nhãn khi thay đổi số cụm đầu vào. Kết quả cho thấy, khi thay đổi số cụm c đầu vào, độ đo Accuracy thay đổi. Tỷ lệ mẫu có nhãn tỷ lệ thuận với số cụm đầu vào. Kết quả cho thấy, SCFMS cho kết quả tốt trên tập dữ liệu thực tế. Hình 8. Biểu diễn sự biến động độ đo Accuracy khi thay đổi số cụm đầu vào trên tập Liver
Vũ Đình Minh, Lê Bá Dũng, Lê Anh Tú, Nguyễn Thanh Sơn 441 Hình 9. Thống kê tỉ lệ mẫu có nhãn khi thay đổi số cụm đầu vào V. KẾT LUẬN Bài báo đã trình bày mô hình lựa chọn hạt giống sử dụng mạng nơron min-max mờ cho phân cụm bán giám sát. So với các phƣơng pháp nhƣ lựa chọn hạt giống ngẫu nhiên, SMM [18], SKMMM [8] thì phƣơng pháp của chúng tôi có ƣu điểm là giảm thiểu số truy vấn ngƣời dùng. Các kết quả thực nghiệm cho thấy SCFMS có kết quả tốt khi xử lý các dữ liệu thực nghiệm. SCFMS còn có khả năng tự bổ sung thêm hạt giống mới khi tập dữ liệu phát sinh các cụm mới. Đặc điểm này có đƣợc là do đƣợc kế thừa từ FMNN [13]. Tuy nhiên, quá trình học thích nghi của SCFMS cần thời gian và kinh nghiệm bằng việc “thử sai” xác định các tham số điều chỉnh. Đây cũng là hạn chế của thuật toán phân cụm mờ min-max nói riêng và của hầu hết các mô hình mạng nơron nói chung. Đây cũng là một hƣớng nghiên cứu tiếp theo cần đƣợc xem xét. TÀI LIỆU THAM KHẢO [1] Allahyar, A., Yazdi, H. S., Harati, A. (2015), "Constrained SemiSupervised Growing Self-Organizing Map.", Neurocomputing, 147, pp. 456-471. [2] B. Alpern and L. Carter, “The siêu hộp,” in Proc. IEEE Conf. Visual., Oct. 1991, pp. 133-139. [3] Batista, G. E., & Monard, M. C. (2003). “An analysis of four missing data treatment methods for supervised learning.”, Applied artificial intelligence,17(5-6), pp. 519-533. [4] B. Settles, “Active learning literature survey,” in Computer Sciences Technical Report 1648. University of WisconsinMadison, 2010. [5] Gabrys, B., & Bargiela, A. (2000). "General fuzzy min-max neural network for clustering and classification.", IEEE transactions on neural networks, 11(3), pp.769-783. [6] K. Wagstaff, S. Basu, and I. Davidson, “When is constrained clustering beneficial, and why?” in In AAAI, 2006. [7] L. Lelis and J. Sander, “Semi-supervised density-based clustering,” in In proc. IEEE Intl. Conf. on Data Mining, 2009, pp. 842-847. [8] Le, C., Vu, V. V., & Yen, N. T. H. (2019). “Choosing seeds for semi-supervised graph based clustering”. Journal of Computer Science and Cybernetics, 35(4), 373-384. [9] Martínez-Rego, D.; Fontenla-Romero, O.; Alonso-Betanzos, A.: “Nonlinear single layer neural network training algorithm for incremental, nonstationary and distributed learning scenarios”. Pattern Recognit. 45(12), 4536-4546 (2012) [10] Pedrycz, W., & Waletzky, J. (1997). "Fuzzy clustering with partial supervision.", IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 27(5), pp. 787-795. [11] S. Basu, A. Banerjee, and R. Mooney, “Semi-supervised clustering by seeding,” in In Proc. of 19th Intl. Conf. on Machine Learning, 2002, pp. 281-304. [12] Simpson, P. K. (1992). “Fuzzy min-max neural networks. I. Classification.” IEEE transactions on Neural Networks, 3(5), 776-786. [13] Simpson, P. K. (1993). “Fuzzy min-max neural network-Part II: Clustering.” IEEE Trans. Fuzzy Syst, 1(1), 32-45 [14] Luo, C., Li, T., Chen, H., & Liu, D. “Incremental approaches for updating approximations in set-valued ordered information systems”, Knowledge-Based Systems, 50, 218-233, 2013. [15] V.-V. Vu and N. Labroche, “Active seed selection for constrained clustering,” Intelligent Data Analysis, vol. 21(3), pp. 537-552, 2017. [16] Yasunori, E., Yukihiro, H., Makito, Y., & Sadaaki, M. (2009). “On semi-supervised fuzzy c-means clustering.”, Proceeding of FUZZ-IEEE 2009, 1119-1124. [17] Vu, D. M., Nguyen, V. H., & Le, B. D. “Semi-supervised clustering in fuzzy min-max neural network”. In International Conference on Advances in Information and Communication Technology (pp.541-550), Springer International Publishing, 2016.
442 PHÂN CỤM BAN GIÁM SÁT DỰA TRÊN PHƢƠNG PHÁP GIEO HẠT SỬ DỤNG MẠNG RRON MIN-MAX MỜ [18] Zaki, M. J., & Meira Jr, W. Data mining and analysis: fundamental concepts and algorithms, Cambridge University Press, 2014. [19] Zhang, H., & Lu, J. “Semi-supervised fuzzy clustering: A kernelbased approach”, Knowledge-Based Systems, 22(6), pp. 477-481, 2009. [20] https://archive.ics.uci.edu/ml/datasets.html [21] https://cs.joensuu.fi/sipu/datasets/ [22] V.-V. Vu, “An efficient semi-supervised graph based clustering,” Intelligent Data Analysis., vol. 22(2), pp. 297- 307, 2018. [23] K. Wagstaff, C. Cardie, S. Rogers, and S. Schrodl, “Constrained k-means clustering with background knowledge,” in In Proc. of Intl. Conf. on Machine Learning, 2001, pp. 577-584. [24] R. Yan, J. Zhang, J. Yang, and A. Hauptmann, “A discriminative learning framework with pairwise constraints for video object classification,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28(4), pp. 578- 593, 2004. [25] C. Zhong, M. Malinen, D. Miao, and P. Franti, “A fast minimum spanning tree algorithm based on k-means,” Inf. Sci., Vol. 295, pp. 1-17, 2015. SEMI-SUPERVISED CLUSTERING BASED ON CHOOSING SEEDS METHOD USING FUZZY MIN-MAX NEURAL NETWORK Vu Dinh Minh, Le Ba Dung, Le Anh Tú, Nguyen Thanh Son ABSTRACT: Clustering is a technique in data mining that belongs to the class of unsupervised learning methods. The process of separating the groups according to the similarity of the data is called clustering. There are two basic principles: (i) the similarity is highest in a cluster, and (ii) the similarity between clusters is the least. Recently, fuzzy semi-supervised clustering is an extension of fuzzy clustering that has also received a lot of attention from scientists. The fuzzy semi-supervised clustering uses the prior information to guide the clustering process, thereby increasing the quality of the cluster. Predictive information, also known as supplementary information, is intended to guide, monitor and control the clustering process. Additional information can be constructed based on Must-link/Cannot-link constraints, or labels (seeds) accompanying the samples, or predefined membership. The method of labeling with the sample requires that a certain portion of the sample in the sample space is accompanied by labels. In general, the clustering result is often dependent on the additional information provided, so different complementary information will produce different results. In some cases, clustering performance may decrease if the supplemental information is not carefully selected. This article discusses the problem of selecting good seeds for semi-supervised clustering using fuzzy min-max neural networks. Properly collected good seeds can increase clustering quality and reduce the number of queries from experts. For this purpose, we propose an algorithm for the seed collection task, which identifies candidates to receive labels from experts using a fuzzy min-max neural network (called SCFMS). Experiments conducted on some real datasets from UCI, CS and real dataset collected from Thai Nguyen Central General Hospital showed the effectiveness of SCFMS compared to other methods.