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
1Khoa Công nghệ thông tin, Trƣờng Đại học Công nghiệp Hà Nội
2Khoa Công nghệ thông tin, Đại học Điện lực
3Đại học Hạ Long
4Cao đẳng Công nghiệp và Thƣơng mại
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
j Wj ,bj A,Vj ,Wj ,
(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):
n
1
bj A,Vj ,Wj
(2)
i
n
Trong đó:
Vj j1j2 ...,vjn
;
;
2 ,...,wjn
Wj
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,
xy 1,
f x,y
xy,
0
(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
A
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
h
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ó
n
siêu hộp nào chứa
được Ah?
Tạo
siêu hộp Bj
y
Mở rộng siêu hộp
Có chồng
lấn siêu hộp?
n
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.
2.
3.
4.
5.
6.
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;
t = 0;
For Ah
D
For Bj
B
If bj(Ah,Bj) = 1 then
t = t+1;
7.
8.
yt
;
Y
t ;
9.
End if;
10.
11.
12.
End for;
End for;
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,
là các nhãn tƣơng ứng của xi theo kết quả gom cụm.
yi
n
1
Accuracy
H yi yi
(4)
n i 1
trong đó H(y) = 1 nếu
, ngƣợc lại H(y) = 0 nếu
, n là tổng số mẫu trong tập kiểm tra.
yi i
yi i
Bảng 2.Thông tin các tập dữ liệu thực nghiệm Benchmark
ID
1
2
3
4
5
6
7
8
Data
Iris
Soybean
Zoo
Yeast
Aggregation
Flame
Jain
#Mẫu
150
#Thuộc tính
#Cụm
4
35
16
8
2
2
2
2
2
5
3
4
7
10
7
2
2
15
3
3
3
47
101
1484
788
240
373
600
312
215
178
500
R15
9
Spiral
Thyroidnew
Wine
10
11
12
13
10
Liver
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.
[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.
8 trang
15980
Free
Bạn đang xem tài liệu "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ờ", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- phan_cum_ban_giam_sat_dua_tren_phuong_phap_gieo_hat_su_dung.pdf
