Xem mẫu
- Công nghệ thông tin & Cơ sở toán học cho tin học
PHÂN CỤM C-MEANS KHẢ NĂNG MỜ LOẠI HAI KHOẢNG
DỰA TRÊN TÍNH TOÁN HẠT CẢI TIẾN
Trương Quốc Hùng*, Ngô Thành Long, Phạm Thế Long
Tóm tắt: Xây dựng không gian hạt giảm chiều dựa trên tính toán hạt là một
bước tiền xử lý nhằm loại bỏ những thuộc tính không cần thiết và tìm kiếm ngoại lai
đối với bài toán phân cụm dữ liệu không chắc chắn và quy mô lớn. Trong khi đó
thuật toán C-Means khả năng mờ loại hai khoảng thực hiện hiệu quả trong xử lý dữ
liệu không chắc chắn và có nhiễu. Tận dụng các ưu điểm đó, chúng tôi đề xuất
phương pháp phân cụm C-Means khả năng mờ loại hai khoảng dựa trên tính toán
hạt cải tiến (AGrIT2FPCM). Phương pháp này sử dụng tính toán hạt để tạo ra các
hạt giảm chiều, sau đó sử dụng lực hấp dẫn hạt để xác định tâm mỗi hạt nhằm cải
tiến phép đo khoảng cách giữa hạt với tâm cụm. Các kết quả thực nghiệm trên các
tập dữ liệu khác nhau cho thấy phương pháp công bố có kết quả tốt hơn so với các
phương pháp trước đó.
Từ khóa: Phân cụm mờ; Trích chọn đặc trưng; Phân cụm C-means khả năng mờ; Tính toán hạt; Lực hấp dẫn hạt.
1. MỞ ĐẦU
Thuật toán phân cụm có nhiều dạng khác nhau như phân cụm rõ như K-means [1],
phân cụm mờ loại một FCM [2], phân cụm mờ dựa trên khả năng PCM [3] hay kết hợp
giữa FCM và PCM (FPCM) [4]. Gần đây có nhiều nghiên cứu đề xuất các hướng cải tiến
nhằm nâng cao chất lượng phân cụm của thuật toán FPCM [5]-[8]. Ngoài ra, để xử lý tốt
hơn tính không chắc chắn, có nhiều phương pháp sử dụng kỹ thuật logic mờ loại hai được
đề xuất [9]-[14]. Trong đó nhóm E. Rubio đã đề xuất phương pháp phân cụm C-Means
khả năng mờ loại hai khoảng (IT2FPCM) là một mở rộng của FPCM sử dụng tập mờ loại
hai khoảng [15]. Các mở rộng này góp phần giảm ảnh hưởng của nhiễu và xử lý tính
không chắc chắn của thuật toán FCM gốc tốt hơn. Tuy nhiên, những thuật toán này vẫn
tồn tại hạn chế trong phân cụm dữ liệu lớn và nhiều chiều như tốc độ thực hiện chậm và độ
chính xác bị ảnh hưởng bởi các thuộc tính nhiễu.
Một trong những hướng giải quyết bài toán phân cụm dữ liệu lớn, nhiều chiều là tìm
cách loại bỏ nhiễu và các thuộc tính dư thừa hay rút gọn thuộc tính của dữ liệu [16], [21]. Có
nhiều thuật toán heuristic rút gọn thuộc tính đã được công bố. Trong khi J. Qian đề xuất một
số thuật toán giảm thuộc tính cho dữ liệu lớn sử dụng map-reduce [17] thì nhóm L.Sun đã
thiết kế một phương pháp lựa chọn thuộc tính dựa trên hệ số entropy thô [18], [19] hoặc tính
toán hạt [20]. Trong khi đó nhóm Q.H.Hu giới thiệu một phương pháp lựa chọn thuộc tính
bằng cách kết hợp tính toán hạt và lý thuyết xấp xỉ [21]. Tuy nhiên, các phương pháp lựa
chọn thuộc tính này cần gán nhãn như các mẫu huấn luyện và thường áp dụng vào bài toán
phân lớp.
Gần đây, tính toán hạt là một công cụ mạnh để nghiên cứu giải quyết bài toán phức
tạp, dữ liệu lớn, thông tin không chắc chắn và dữ liệu nhiều chiều [22], [23]. Tính toán hạt
trở thành một phương pháp mới có thể mô phỏng suy nghĩ của con người và giải quyết các
bài toán trí tuệ tính toán có liên quan đến ý tưởng hạt và logic hạt [24] và nó cũng được sử
dụng như một nền tảng cho các phương pháp rút gọn thuộc tính [21], [20].
Có nhiều mô hình lai giữa tính toán hạt và các phương pháp khác được đề xuất và tạo
ra một loại hình mới của các thuật toán học máy. Những mô hình này dựa trên cấu trúc hạt
đối với nhiều loại dữ liệu hoặc phương pháp học khác nhau [25], [26]. Trong công bố gần
đây, chúng tôi đã áp dụng tính toán hạt để thực hiện rút gọn thuộc tính cho bài toán phân
cụm nhằm giảm ảnh hưởng xấu từ số chiều lớn của tập dữ liệu [28]. Bên cạnh đó các
nghiên cứu về lực hấp dẫn hạt dựa trên ý tưởng của định luật vạn vật hấp dẫn Newton là
176 T. Q. Hùng, N. T. Long, P. T. Long, “Phân cụm C-Means … tính toán hạt cải tiến.”
- Nghiên cứu khoa học công nghệ
một trong những hướng nghiên cứu thu hút nhiều sự chú ý. Dựa trên ý tưởng này nhóm
M.A. Sanchez đã trình bày phương pháp mới để tìm kiếm các hạt thông tin mờ từ dữ liệu đa
chiều [29]. Nhóm tác giả M. Alswaitti cũng đề xuất thuật toán phân cụm dữ liệu dựa trên lực
hấp dẫn được tối ưu hóa [30].
Trên cơ sở đó, phương pháp phân cụm C-means khả năng mờ loại hai khoảng dựa trên
tính toán hạt cải tiến (AGrIT2FPCM) được đề xuất. Phương pháp này tận dụng khả năng
của IT2FPCM trong xử lý nhiễu kết hợp tính toán hạt để loại bỏ ảnh hưởng của các thuộc
tính dư thừa và các đối tượng nhiễu. Ngoài ra lực hấp dẫn hạt cũng được sử dụng để xác
định tâm của mỗi hạt, qua đó cải tiến phép đo khoảng cách giữa hạt và tâm cụm.
Các phần còn lại của bài báo này được tổ chức như sau: Phần 2 giới thiệu ngắn gọn
một số kiến thức cơ sở về phân cụm C-Means khả năng mờ loại hai khoảng, tính toán hạt
và lực hấp dẫn hạt; Phần 3 đề xuất phân cụm IT2FPCM dựa trên tính toán hạt cải tiến;
Phần 4 đưa ra một số kết quả thực nghiệm và Phần 5 phát biểu kết luận và đề xuất hướng
nghiên cứu tiếp theo.
2. KIẾN THỨC CƠ SỞ
2.1. Phân cụm C-Means khả năng mờ loại 2 khoảng
Thuật toán phân cụm C-Means khả năng mờ loại 2 khoảng là một mở rộng của thuật
toán phân cụm C-Means khả năng mờ loại 1 sử dụng tập mờ loại 2 [15]. Các trọng số mũ
mờ m và trọng số mũ khả năng p là các khoảng giá trị tương ứng: m = [m , m ]; p =
[p , p ].
Ma trận phân hoạch mờ u nằm trong khoảng u , u , trong đó u , u là các cận
dưới và cận trên của khoảng thuộc mờ độ thuộc của dữ liệu x vào cụm v . Ma trận phân
hoạch khả năng t nằm trong khoảng t , t , trong đó t , t là các cận dưới và cận
trên của khoảng thuộc khả năng độ thuộc của dữ liệu x vào cụm v . Chúng được xác
định như sau:
= , (1)
= , (2)
= , (3)
= , (4)
trong đó, 1 ≤ ≤ , 1 ≤ ≤ ; , lần lượt là số cụm và số phần tử dữ liệu.
Tâm cụm nằm trong khoảng , , trong đó , là các cận dưới và cận trên của tâm
cụm thứ . Chúng được xác định như sau:
∑ ( + )
= (5)
∑ ( + )
Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 177
- Công nghệ thông tin & Cơ sở toán học cho tin học
∑ ( + )
= (6)
∑ ( + )
trong đó, = ; = .
Giảm kiểu để xác định ma trận phân hoạch mờ, ma trận phân hoạch khả năng và tâm cụm:
+
= (7)
2
̅ +
= (8)
2
+
= (9)
2
2.2. Tính toán hạt
2.2.1. Hạt thông tin và tính chất hạt
Hạt thông tin [28] được định nghĩa là = , ( ) , trong đó liên quan đến khái
niệm của hạt thông tin, và ( ) mô tả sự mở rộng của hạt thông tin.
Đối với hệ thống phân cụm = ( , ), tính chất hạt của hệ thống với tập thuộc tính
và tập hạt = { } được biểu diễn là ( ), ⊆ được xác định như sau:
| / |
| ( )|
( ) = , ( )∈ (10)
| |
2.2.2. Mức độ ảnh hưởng của thuộc tính dựa trên tính chất hạt
Sự ảnh hưởng của mỗi tập thuộc tính trong hệ thống phân cụm [28] được xác định dựa
trên tính chất hạt. Trong một hệ thống phân cụm = ( , ), mức độ ảnh hưởng của thuộc
tính ∈ biểu diễn là { } ( ) và được xác định như sau:
{ }( ) = ( − )− ( ) (11)
Giá trị của { } ( ) càng lớn thì mức độ ảnh hưởng của thuộc tính a càng lớn,
ngược lại thuộc tính ∈ là dư thừa đối với A nếu giá trị ( − ) bằng với ( ).
Thuật toán rút gọn được trình bày ngắn gọn như sau:
Thuật toán 1: Rút gọn thuộc tính dựa trên tính toán hạt
1 Đầu vào: Một hệ thống thông tin hạt = ( , ) trong đó ≠ ∅ là tập các đối tượng
và ≠ ∅ là tập các thuộc tính.
2 Đầu ra: tập rút gọn thuộc tính tối thiểu của , biểu diễn là
3 Bước 1: Xác định lõi tập thuộc tính ( ) như sau:
Tính mức độ quan trọng của mỗi thuộc tính của A được biểu diễn là { } ( ) theo
công thức (11), nếu { } ( ) ≠ 0 thì chọn thuộc tính vào ( ).
4 Bước 2:
4.1 Gán ≔ ( )
4.2 Nếu ( ) = ( ) thì điều kiện dừng thỏa mãn
4.3 repeat:
4.3.1 Với mỗi thuộc tính ∈ − , tính toán mức độ ảnh hưởng của nó đối với
∪ { }: ( ).
4.3.2 Tìm thuộc tính mà mức độ ảnh hưởng đối với là lớn nhất ( )=
′
max ′ ∈
4.3.3 Thêm thuộc tính vào lõi: ≔ ∪
until GK(C) = GK(A)
178 T. Q. Hùng, N. T. Long, P. T. Long, “Phân cụm C-Means … tính toán hạt cải tiến.”
- Nghiên cứu khoa học công nghệ
2.2.3. Không gian hạt và trích chọn đặc trưng
Phương pháp xây dựng không gian hạt và trích chọn đặc trưng [28] được xác định như sau:
Các đối tượng = { , , … , } được phân cụm vào cụm theo mỗi thuộc tính thứ
bằng thuật toán FPCM [4], ∈ . Trên mỗi thuộc tính thứ , các cụm được gán nhãn bằng
cách đánh số tăng dần từ 1 đến tương ứng với giá trị tăng dần của dữ liệu trong các cụm.
Ma trận nhãn cụm được hình thành từ các phần tử ( , ) là nhãn của đối tượng thứ trên
thuộc tính thứ , 1 ≤ ( , ) ≤ , = [ ( , )]( × ) .
Từ các giá trị { , , … , } của một hàng trong ma trận nhãn cụm , chúng ta xây
dựng một hạt = { , ( )}, trong đó = { , , … , }, ( ) = { ∈ ∶
( , 1) = ∧ ( , 2) = ∧ … ∧ ( , ) = }. Như vậy một không gian hạt G được
hình thành từ tập các hạt, = { }, = 1,2, … , với là số hạt, 1 ≤ ≤ , biểu
diễn = | |.
Chú ý ta chỉ xét những hạt với = { , , … , }, ∃ ≠ với ≠
Phương pháp xây dựng không gian hạt và trích chọn đặc trưng có thể được mô tả ngắn
gọn như sau:
Thuật toán 2: Xây dựng không gian hạt và trích chọn đặc trưng
1 Đầu vào: Tập dữ liệu = { }, = 1. . , = , , … , , là số cụm và là tham
số lọc nhiễu.
2 Đầu ra: Tập thuộc tính là tập rút gọn tối thiểu của và không gian hạt
3 Bước 1:
3.1 Thực hiện thuật toán 1 trên mỗi thuộc tính ∈ để thành lập ma trận nhãn cụm
= [ ( , )]( × ) trong đó ( , ) là nhãn cụm đối tượng thứ trên thuộc tính thứ .
3.2 Loại bỏ các đối tượng và các thuộc tính ngoại lai theo thứ tự các công thức:
( ) (12)
≔ − { } nếu < ớ ∀ = 1,2. . . , à = 1,2, . . . ,
≔ − { } nếu (1, ) = (2, ) = ⋯ = ( ′ , ) (13)
4 Bước 2: Xây dựng không gian hạt
4.1 Khởi tạo G = ∅, r = 0, ID = {1,2, … , n}, k = 0, trong đó là chỉ số hàng của ma
trận , là tập chỉ số và là số hạt.
4.2 repeat
4.2.1 = + 1
4.2.2 repeat
= +1
until ∈
4.2.3 Thiết lập theo các giá trị của hàng thứ trong ma trận :
= ( , 1), ( , 2), … , ( , ) trong đó là số thuộc tính trong tập sau khi
đã loại các ngoại lai.
4.2.4 Tìm ( ) = { ∈ : ( , 1) = ( , 1) ∧ ( , 2) = ( , 2) ∧ … ∧
( , ) = ( , )}
if | ( )| > 0 then
4.2.4.1 for each ∈ ( ):
= − { }, = −{ }
4.2.4.2 = ( , ( ))
4.2.4.3 if not ( , 1) = ( , 2) = ⋯ = ( , ) then = ∪ { }
until =∅
5 Bước 3: Thực hiện thuật toán 1 trên tập hạt G để thu được tập rút gọn tối thiểu C của A
Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 179
- Công nghệ thông tin & Cơ sở toán học cho tin học
2.2.4. Lực hấp dẫn hạt
Định luật vạn vật hấp dẫn của Newton là một trong những lý thuyết cơ bản và quan
trọng nhất trong vật lý cơ học. Theo định luật vạn vật hấp dẫn thì mỗi khối điểm hút mỗi
khối điểm khác bởi một lực theo phương đường thẳng cắt hai điểm. Lực này tỷ lệ thuận
với tích của hai khối lượng và tỷ lệ nghịch với bình phương khoảng cách giữa hai điểm:
= (14)
‖ , ‖
trong đó, là lực hút giữa hai khối, là hằng số hấp dẫn có giá trị là 6.674 ∗ 10 , và
là khối lượng của khối thứ nhất và khối thứ hai, và ‖ , ‖ là khoảng cách giữa hai
tâm khối.
Định luật này lý giải các khối điểm trong không gian có lực tương tác đối với tất cả các
khối điểm còn lại trong vũ trụ, đây cũng là ý tưởng chính của thuật toán phân cụm dựa trên
lực hấp dẫn hạt FGGCA [29]. Thuật toán này mô phỏng các lực hấp dẫn trong không gian,
ở đó mỗi điểm dữ liệu được coi như một khối đơn có khối lượng giả định là 100 kg. Các
điểm dữ liệu hay khối có trọng lượng được xem xét bởi các thuộc tính gồm: vị trí , khối
lượng và mật độ lực hấp dẫn . Khi đó điểm dữ liệu thứ trong hạt thứ được biểu
diễn bởi = ( , , ), với 1≤ ≤ | ( )|, 1≤ ≤ | |.
3. PHÂN CỤM C-MEANS KHẢ NĂNG MỜ LOẠI HAI KHOẢNG DỰA TRÊN
TÍNH TOÁN HẠT CẢI TIẾN
3.1. Xác định trọng tâm hạt dựa trên lực hấp dẫn
Để xác định trọng tâm của mỗi hạt thu được từ thuật toán 2 chúng tôi thực hiện theo
trình tự sau:
Bước đầu tiên, tính toán lực tương tác giữa tất cả các điểm dữ liệu trong mỗi hạt hay
lực hấp dẫn tác động của mỗi điểm đối với tất cả các điểm khác trong mỗi hạt:
( . )×( . )
= (15)
. , .
Tổng lực hấp dẫn của một điểm đối với tất cả các điểm khác trong mỗi hạt tạo nên mật
độ lực hấp dẫn của điểm đó:
| ( )|
. =∑ , với ≠ (16)
Bước thứ hai, trong mỗi hạt sắp xếp tất cả các điểm dữ liệu theo thứ tự giảm dần của mật
độ lực hấp dẫn tương ứng. Sau khi được sắp xếp, phần tử đầu tương ứng với điểm có mật độ
lực hấp dẫn cao nhất và phần tử cuối tương ứng với điểm có mật độ lực hấp dẫn thấp nhất.
Bước thứ ba, trong mỗi hạt xét theo thứ tự ưu tiên từ các điểm có mật độ lực hấp dẫn
cao đến các điểm có mật độ hấp dẫn nhỏ hơn. Với điểm đang xét tìm hạt gần nhất
so với , sau đó thực hiện ghép và như sau:
= ∪ (17)
Như vậy sau khi ghép, biến mất và còn lại sẽ có sự thay đổi về khối lượng và vị
trí. Cụ thể khối lượng của sẽ được thêm phần khối lượng của :
. = . + . (18)
Vị trí mới của được cập nhật bằng tâm trọng lực của khối lượng hai điểm ,
trước đó, được biểu diễn bởi:
.
= . , . (19)
. + .
Tiếp theo là tính toán hệ số chia tỷ lệ , được biểu diễn bằng phương trình (20). Vị trí
180 T. Q. Hùng, N. T. Long, P. T. Long, “Phân cụm C-Means … tính toán hạt cải tiến.”
- Nghiên cứu khoa học công nghệ
mới của được cập nhật bằng phương trình (21), nghĩa là vị trí của được xác định bởi
độ xê dịch về phía một đoạn:
Ρ
λ = (20)
. , .
. = . + λ( . − . ) (21)
Sau mỗi quá trình trên, trong mỗi hạt số lượng điểm sẽ giảm trong khi đó khối lượng
chung từ tất cả các điểm trong mỗi hạt vẫn giữ nguyên.
Để tìm các trọng tâm hạt, thực hiện lặp lại tiếp quá trình trên đến khi số điểm trong mỗi hạt
còn lại bằng 1. Vị trí của các điểm kết quả chính là các trọng tâm của các hạt.
Thuật toán 3: Thuật toán tìm trọng tâm hạt
1 Đầu vào: Không gian hạt = { } với 1 ≤ ≤ | |, | | là số hạt trong không gian
hạt .
2 Đầu ra: Tập các trọng tâm hạt ={ }
3 For each = to | |
4 Bước 1:
3.1 Gán số điểm ban đầu = | ( )|
3.2 Khởi tạo: Khởi tạo các điểm dữ liệu , ,…, trong hạt thứ , trong đó:
. = 100, . = 0 ( . và . tương ứng là khối lượng và mật độ hấp dẫn
của hạt thứ )
5 Bước 2:
repeat:
5.1 Tính tất cả các lực hấp dẫn tương tác trong hạt thứ :
( . )×( . )
= với ≠ , 1 ≤ , ≤ ,
. , .
hằng số hấp dẫn = 6.674 × 10
5.2 Tính mật độ hấp dẫn cho mỗi điểm: . =∑ với ≠
5.3 Sắp xếp các điểm trong hạt thứ theo mật độ hấp dẫn giảm dần của .
5.4 Thực hiện ghép các điểm
Tìm gần nhất, thực hiện ghép hai điểm và ,
với ∀ , , 1 ≤ ≤ − 1; ≤ ≤
5.4.1 Xác định trọng lượng mới của điểm ghép: . = . + .
.
5.4.2 Xác định tâm trọng lực: = . , .
. .
5.4.3 Xác định hệ số tỷ lệ : =
. , .
5.4.4 Xác định vị trí mới của điểm ghép: . = . + . − .
5.4.5 Cập nhật số lượng điểm còn lại trong hạt: = −1
until: =1
6 Bước 3: Trọng tâm hạt thứ : =
7 Next
3.2. Thuật toán C-Means khả năng mờ loại hai khoảng dựa trên tính toán hạt cải tiến
(AGrIT2FPCM)
Xem xét hệ thống phân cụm hạt = ( , ), không gian hạt = { }, = 1. . và
| |. ( ) ′ | |
= Hạt đầu vào = , với = , , … , ′ , trong đó = là
số thuộc tính.
Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 181
- Công nghệ thông tin & Cơ sở toán học cho tin học
Thực hiện phương pháp tìm trọng tâm hạt dựa trên lực hấp dẫn, tương ứng mỗi hạt
sẽ thu được trọng tâm hạt . Khi đó, khoảng cách giữa một hạt và tâm cụm
, 1 ≤ ≤ được xác định bằng là khoảng cách giữa trọng tâm hạt và tâm cụm :
=‖ − ‖ (22)
Ma trận phân hoạch mờ nằm trong khoảng , , trong đó , là các cận
dưới và cận trên của khoảng thuộc mờ độ thuộc của hạt vào cụm . Ma trận phân hoạch
khả năng sẽ nằm trong khoảng , , trong đó , là các cận dưới và cận trên của
khoảng thuộc khả năng độ thuộc của hạt vào cụm . Chúng được xác định theo các
công thức (1), (2), (3) và (4), trong đó = 1,2, … , ; = 1,2, … , ; được tính bởi
công thức (22).
Các cận dưới và cận trên , của tâm cụm thứ được xác định như sau:
∑ ( + )× . ×| |
= (23)
∑ + ×| |
∑ ( + )× . ×| |
= (24)
∑ + ×| |
trong đó = 1,2, … , ; = , = và | | số điểm dữ liệu trong hạt .
Tiếp theo thực hiện giảm kiểu để xác định ma trận phân hoạch mờ, ma trận phân hoạch
khả năng và tâm cụm theo các công thức (7), (8) và (9).
Thuật toán C-Means khả năng mờ loại hai khoảng dựa trên tính toán hạt cải tiến
(AGrIT2FPCM) được trình bày ngắn gọn như sau:
Thuật toán 4: AGrIT2FPCM
1 Đầu vào: Hệ thống phân cụm ( , ) trong đó tập dữ liệu = { , , … , }, tập các
thuộc tính = , , … , , số cụm , sai số và tham số nhiễu .
2 Đầu ra: ma trận độ thuộc khả năng , ma trận độ thuộc mờ và ma trận tâm .
3 Bước 1: Áp dụng thuật toán 2 trên hệ thống phân cụm ( , ) để thu được tập thuộc
tính là rút gọn tối thiểu của và không gian hạt G.
4 Bước 2: Áp dụng thuật toán 3 trên không gian hạt để thu được tập các trọng tâm hạt
={ }
5 Bước 3:
Áp dụng thuật toán IT2FPCM trên hệ thống phân cụm = ( , ) như sau:
5.1 Gán số bước lặp = 0
5.2 repeat:
5.2.1 = + 1
5.2.2 Cập nhật ma trận độ thuộc khả năng ( ) dùng công thức (3), (4) và (8).
5.2.3 Loại bỏ hạt ngoại lai hoặc nhiễu
={ ∈ : max ( ) ≥ , ∀ = 1,2, … , }
5.2.4 Cập nhật ma trận độ thuộc mờ ( ) dùng công thức (1), (2) và (7).
() ( ) ( ) ( )
5.2.5 Cập nhật ma trận tậm cụm = , ,…, dùng công thức (23),
(24) và (9).
( )
until: − () ≤
6 Gán dữ liệu vào cụm thứ nếu > , = 1,2, . . , à ≠ .
4. THỰC NGHIỆM
Trong phần này, một số tập dữ liệu nổi tiếng đã công bố được sử dụng trong các thực
182 T. Q. Hùng, N. T. Long, P. T. Long, “Phân cụm C-Means … tính toán hạt cải tiến.”
- Nghiên cứu khoa học công nghệ
nghiệm. Để phân tích so sánh các kết quả phân cụm, bài báo sử dụng các phương pháp
phân cụm khác nhau bao gồm: FPCM [4], GrFPCM (thực hiện FPCM [4] trên không gian
hạt từ thuật toán 2) và AGrIT2FPCM, trong đó AGrIT2FPCM là các thuật toán được đề
xuất trong nghiên cứu này.
Các thuật toán được thực hiện trên chương trình VC++ và chạy trên máy tính Intel core
i7-3517U CPU 1.90GHz - 2.40GHz, RAM 8.0 GB. Thông qua các điều chỉnh trong các thực
nghiệm, các kết quả phân cụm ổn định với các tham số được thiết lập như sau: =
1.5, = 2.5, = 1.5, = 2.5, = 2, = 2, tham số nhiễu θ = 0.1 và = 0.0001.
Các kết quả thực hiện phân cụm được đánh giá qua các chỉ số tỷ lệ xác thực đúng và tỷ
lệ xác thực sai [31] được định nghĩa như sau:
TPR = ; FPR = (25)
trong đó TP là số dữ liệu phân lớp chính xác, FN là số dữ liệu phân lớp lỗi – không chính
xác, FP là số dữ liệu phân lớp không chính xác và TN là số dữ liệu phân lớp lỗi chính xác.
Các thuật toán cho giá trị TPR cao hơn và giá trị FTR thấp hơn tương ứng với độ chính
xác phân cụm cao hơn.
Bảng 1. Các tập dữ liệu thử nghiệm.
Tập dữ liệu Số phần Số thuộc Số lớp Số thuộc tính
tử tính sau khi rút gọn
WDBC 569 30 2 4
DNA 106 57 2 2
Madelon 4400 500 2 12
Lymphoma 45 4026 2 15
Leukaemia 38 7129 2 6
Global Cancer Map(GCM) 190 16063 14 16
Embryonal Tumours 60 7129 2 8
Colon 62 2000 2 9
Các tập dữ liệu được sử dụng bao gồm: Wis-consin Diagnostic Breast Cancer
(WDBC), E. coli promoter gene sequences (DNA), Madelon và năm tập dữ liệu ung thư
khác (Lymphoma, Leukaemia, Global Cancer Map (GCM), Embryonal Tumours và
Colon) [28]. Chi tiết của các tập dữ liệu và tập các thuộc tính rút gọn tối thiểu được thể
hiện trong Bảng 1.
Bảng 2. Kết quả thử nghiệm.
Tập dữ liệu FPCM GrFPCM AGrIT2FPCM
Chỉ số FS TPR FPR FS TPR FPR FS TPR FPR
WDBC 30 92.6% 2.8% 4 95.4% 1.9% 4 96.1% 1.6%
DNA 57 91.5% 2.80% 2 96.20% 1.90% 2 97.20% 1.90%
Madelon 500 90.8% 3.30% 12 94.80% 2.10% 12 95.80% 1.90%
Lymphoma 4026 88.9% 2.20% 15 95.60% 2.20% 15 95.60% 2.20%
Leukaemia 7129 81.6% 7.90% 6 94.70% 2.60% 6 97.40% 2.60%
Global Cancer 16063 90.0% 5.30% 16 96.80% 1.10% 16 97.90% 1.10%
Map
Embryonal 7129 88.3% 8.30% 8 95.00% 1.70% 8 96.70% 1.70%
Tumours
Colon 2000 80.6% 9.70% 9 93.50% 3.20% 9 95.20% 3.20%
Các tập dữ liệu trong bảng 1 được phân cụm bởi FPCM, GrFPCM và AGrIT2FPCM
với số cụm là số lớp. Trong khi FPCM thực hiện phân cụm trên các tập dữ liệu đầy đủ các
Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 183
- Công nghệ
nghệ thông tin & C
Cơ
ơ sở
sở toán học cho tin học
thuộcc tính thì GrFPCM và AGrIT2FPCM th
thu thựcc hiện
hi n phân ccụm m trên không gian hhạtt G vvớii
các thu
thuộ ộcc tính
tính rút gọ
gọnn là đđầầuu ra của
c a Thu
Thuậtt toán 2.
Các kết k t quả
qu phân ccụm m qua các ch chỉ sốố ho
hoặcc chất
ch t lượ
lượng
ng củcủaa phân ccụm m đư
đượcc báo cáo
trong B Bảảng
ng 2 và đư
đượ ợcc th
thể hi
hiệnn trự
trựcc quan bbằng
ng biểu
bi u đồđồ trong hình ình 1. Trong đó thu thuậậtt toán đđềề
xu t AGrIT2FPCM có đđộộ chính xác cao hơn tương ứng
xuất ng vvớớii các giá tr trị TPR cao hơn và
FTR th thấấp
p hơn. Thu
Thuậậtt toán AGrIT2FPCM thu đư đượợcc TPR cao nh nhấấtt và FPR nhnhỏ nhất
nh t trong
các ttậậpp dữ
d liệu
li u và tỷ
tỷ lệ xác thực
th c đúng hay ch chỉ số
s TPR củ củaa ttấtt ccả các bộ
bộ dữữ liệệu theo thu
thuậtt
toán đđề xuấxuất đềềuu có giá trtrị trên 95 %.
1 Biểểuu đđồ kkếtt quả
Hình 1. quả thử
ử nghi
nghiệm
m.
55.. K
KẾT
ẾT LUẬN
Bài báo này đđãã trình bày thu
thuật
ật toán phân cụm C C--Means
Means kh
khảả năng mờ loại hai khoảng
trên tính toán hhạt
ạt cải tiến. Ph
Phương
ương pháp này th thực
ực hiện rút gọn các thuộc tính của dữ liệu
nhằm giữ lại các thuộc tính chính vvàà lo
nhằm loại
ại đi các thuộc tính ddư ư th
thừa.
ừa. Hơn
Hơn nữa,
nữa, ph ương pháp
phương
đềề xuất sử dụng tính toán hạt vvàà hàm thu thuộc
ộc loại hai khoảng ccòn òn có ý ngh
nghĩa
ĩa nâng cao khả
năng xxửử lý tính không chắc chắn. NgoNgoàiài ra
ra, ddựa
ựa trên
trên llực
ực hấp dẫn hạt, ph
phương
ương pháp này xác
định
ịnh trọng tâm hạt để cải tiến phép đo khoảng cách giữa hạt với tâm cụm. Các th thực
ực
nghiệm được
nghiệm đ ợc thực hiện tr ên một
trên một số tập dữ liệu đđãã công bbố ố cho thấy các kết quả của
phương pháp đđềề xuất tốt hhơnơn so với
với các ph
phương
ương pháp phân ccụm ụm khác.
M
Mộtột số hư
hướng
ớng nghi
nghiên
ên ccứu
ứu tiếp theo nhnhưư ssử
ử dụng các ph phương
ương pháp titiến
ến hóa (như
(như các
giải
ải thuật di truyền) đểể tối ưu các tham ssố ố của thuật toán phân cụm hoặc mở rộng phân
cụm
ụm sử dụng hhàmàm thu
thuộc
ộc loại hai dạng hạt.
TÀI LI
LIỆU
ỆU THAM KHẢO
[1] T. Kanung et al
[1]. al,, “An Efficient kk-Means
Means Clustering Algorithm: Analysis and
Implementation”
Implementation”,, IEEE Trans. On Pattern Analysis and Machine Intelligence
Intelligence, Vol.
24, No. 7 (2002), pp. 881
881-893.
893.
FCM: The Fuzzy cc--Means
[2] J.C. Bezdek, R. Ehrlich, W. Full, ““FCM:
[2]. Means Clustering Algorithm
Algorithm”,
”,
Computers & Geosciences, Vol. 10 10,, No. 22--3
3 (1984), pp 191
191-203.
203.
[3] R. Krishnapuram, J. Keller, “A possibilistic approach to clustering“, IEEE Trans.
[3].
Fuzzy Syst., Vol. 1,, No. 2 (1993), pp. 98
98-110.
110.
[4] N.R. Pal, K.Pal, J.C. Bezdek, “A mixed cc-means
[4]. means clustering model“
model“,, Proceedings of the
Sixth IEEE International Conference on Fuzzy Systems, Vol. 11,, (1997), pp. 1111-21
21.
184 T. Q. Hùng, N. T. Long, P. T. Long, “Phân ccụm
ụm C
C--Means
Means … tính toán h tiến.””
ạt cải tiến.
hạt
- Nghiên cứu khoa học công nghệ
[5]. S. Askari et al, "Generalized Possibilistic Fuzzy C-Means with novel cluster validity
indices for clustering noisy data", Applied Soft Computing, Vol. 53, (2017), pp. 262-
283.
[6]. S. Askari et al, "Generalized entropy based possibilistic fuzzy C-Means for
clustering noisy data and its convergence proof", Neurocomputing, Vol. 219, (2017),
pp. 186-202.
[7]. M. B. Ferraro, P. Giordani, "Possibilistic and fuzzy clustering methods for robust
analysis of non-precise data", International Journal of Approximate Reasoning, Vol.
88, (2017), pp. 23-38.
[8]. J. Aparajeeta et al, "Modified possibilistic fuzzy C-means algorithms for segmentation
of magnetic resonance image", Applied Soft Computing, Vol. 41, (2016), pp. 104-119.
[9]. N. Karnik, M. Mendel, "Operations on type-2 set", Fuzzy Set Syst., Vol. 122, No. 2,
(2001), pp. 327–348.
[10]. M. Mendel, "Uncertain Rule-Based Fuzzy Logic Systems: Introduction and new
directions", Prentice-Hall Inc., Upper Saddle River (2001).
[11]. C. Hwang, F.C Rhee, "Uncertain fuzzy clustering: interval type-2 fuzzy approach to C-
means", IEEE Trans. Fuzzy Syst., Vol. 15, No. 1 (2007), pp. 107-120.
[12]. M.H.F Zarandi et al, "Type-II fuzzy possibilistic C-mean clustering", In:
IFSA/EUSFLAT Conference, (2009), pp. 30–35.
[13]. E. Rubio and O. Castillo, “Optimization of the Interval Type-2 Fuzzy C-Means using
Particle Swarm Optimization”, NaBIC, (2013), pp. 10-15.
[14]. J. P. Sarkar et al, "Rough Possibilistic Type-2 Fuzzy C-Means clustering for MR brain image
segmentation", Applied Soft Computing, Vol. 46, (2016), pp. 527-536.
[15]. E. Rubio et al, "A new Interval Type-2 Fuzzy Possibilistic C-Means clustering
algorithm", In: NAFIPS/WConSC Conference, (2015), pp. 1-5.
[16]. B. M. Joshi et al, “High Dimensional Unsupervised Clustering Based Feature Selection
Algorithm”, International Journal of Engineering Science and Technology (IJEST), Vol.
4, No. 5 (2012), pp.2022-2029.
[17]. J. Qian, L. Ping, et al, "Hierarchical attribute reduction Algorithms for big data using
Map Reduce", Knowledge-based Systems, Vol. 73, (2015), pp.18-31.
[18]. L. Sun et al, "New Approach for Feature Selection by Using Information Entropy",
Journal of Information and Computational Science, Vol. 8, (2011), pp.2259-2268.
[19]. L. Sun et al, "Feature Selection Using Rough Entropy-Based Uncertainty Measures in
Incomplete Decision Systems", Knowledge Based Systems, Vol. 36, (2012), pp.206-216.
[20]. L. Sun et al, "Granular Space-Based Feature Selection and Its Applications", Journal of
Software, Vol. 8, No. 4 (2013), pp.817-826.
[21]. Q. H. Hu et al, "Mixed Feature Selection Based on Granulation and Approximation",
Knowledge-Based System, Vol. 21, (2008), pp.294-304.
[22]. L.-y. Gao et al, "Research on Granular Computing Cased on Rough Set Theory and Its
Application", Control and APG, Vol. 24, No. 12-3 (2008), pp.189-191.
[23]. H. Li, "Research on Knowledge Reduction based on Knowledge Granularity", Journal of
Suzhou University, Vol. 25, No. 2 (2010), pp.16-19.
[24]. W. Pedrycz, "From fuzzy data analysis and fuzzy regression to granular fuzzy data
analysis", Fuzzy Sets and Systems, Vol. 274, (2015), pp.12-17.
[25]. S. Ding et al, "Research on the hybrid models of granular computing and support
vector machine", Artificial Intelligence Review, Vol. 43, No. 4 (2015), pp.565-577.
[26]. Y. Qian, Y. Li, J. Liang, "Fuzzy Granular Structure Distance", IEEE Trans. on Fuzzy
Systems , Vol. 23, No. 6 (2015), pp. 2245-2259.
[27]. H. Runxin and H. Nian, "The Reduction of Facial Feature Based on Granular
Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 185
- Công nghệ thông tin & Cơ sở toán học cho tin học
Computing", Electronics and Signal Processing, LNEE 97, (2011), pp. 1015-1021.
[28]. H. Q. Truong et al, "Advanced Fuzzy Possibilistic C-means Clustering Based on
Granular Computing", IEEE International Conference on Systems, Man, and
Cybernetics, (2016).
[29]. M.A. Sanchez et al, “Fuzzy granular gravitational clustering algorithm for multivariate
data”, Information Sciences, Vol. 279, (2014), pp. 498-511.
[30]. M. Alswaitti et al, "Optimized gravitational-based data clustering algorithm",
Engineering Applications of Artificial Intelligence, Vol. 73, (2018), pp. 126-148.
[31]. Kohavi R, Provost F, "Glossary of Terms", Machine Learning, Vol. 30, (1998), pp.
271-274.
ABSTRACT
INTERVAL TYPE-2 FUZZY POSSIBILISTIC C-MEANS CLUSTERING BASED ON
ADVANCED GRANULAR COMPUTING
The feature selection granular space construction is preprocessing step to
remove redundant features and detect outlier for clustering problems which often
are used to deal with large and high dimensional datasets. Meanwhile the Interval
Type 2 Fuzzy Possibilistic C-Means Clustering algorithm is effective in processing
uncertainty and noisy data. Utilizing this advantages, we propose the method of
Interval Type 2 Fuzzy Possibilistic C-Means Clustering based on advanced
Granular Computing (AGrIT2FPCM). In this method, Granular Computing is used
to create dimensional reduction granules, then the method of Granular
Gravitational Forces is used to determine the centroid of granules to improve the
measurement of the distance between the granules and centroids of the cluster.
Experimental results reported for various datasets in comparison with other
approaches exhibit the advantages of the proposed method.
Keywords: Fuzzy clustering; Feature selection; Fuzzy possibilistic C-means clustering; Granular computing;
Granular gravitational.
Nhận bài ngày 24 tháng 12 năm 2018
Hoàn thiện ngày 09 tháng 01 năm 2019
Chấp nhận đăng ngày 12 tháng 02 năm 2019
Địa chỉ: Học viện Kỹ thuật quân sự.
*
Email: truongqhung@gmail.com.
186 T. Q. Hùng, N. T. Long, P. T. Long, “Phân cụm C-Means … tính toán hạt cải tiến.”
nguon tai.lieu . vn
