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

Công nghệ thông tin & Cơ sở toán học cho tin học 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.” 176 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à Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 177 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) Công nghệ thông tin & Cơ sở toán học cho tin học 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.” 178 = ∑ ( + ) ∑ ( + ) (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: = + 2 (7) = ̅ + 2 (8) = + 2 (9) 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) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 179 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: ≔ − {} nếu () < ớ ∀ = 1,2. . . , à = 1,2, . . . , (12) ≔ − {} 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 Công nghệ thông tin & Cơ sở toán học cho tin học 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.” 180 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í Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 181 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. Công nghệ thông tin & Cơ sở toán học cho tin học 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.” 182 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 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 183 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 tử Số thuộc tính Số lớp Số thuộc 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 Map 16063 90.0% 5.30% 16 96.80% 1.10% 16 97.90% 1.10% Embryonal Tumours 7129 88.3% 8.30% 8 95.00% 1.70% 8 96.70% 1.70% 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 184 thu các thu trong B xu FTR th các t toán đ trên tính toán h nh đề xuất sử dụng tính toán hạt v năng x đị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 nghi phương pháp đ giải thuật di truyền) cụm sử dụng h [1] [2] [3] [4] ộc tính thì GrFPCM và AGrIT2FPCM th Các k ất AGrIT2FPCM có đ ậ Bài báo này đ ằm giữ lại các thuộc tính chính v ệm đ M . . . . ộ ả ấ p d ề xu ử lý tính không chắc chắn. Ngo ột số h T. Kanung Implementation” 24, J.C. Bezdek, R. Ehrlich, W. Full, “ Computers & Geosciences, R. Krishnapuram, J. Keller, Fuzzy Syst., N.R. Pal, K.Pal, J.C. Bezdek, Sixth IEEE International Conference on Fuzzy Systems, c tí ết qu ng 2 và đư p hơn. Thu ữ li ấ ược thực hiện tr No. 7 (2002), pp. 881 T. Q. Hùng, N. T. Long, P. T. Long, “Phân c nh rút g ệu và t t đề ư ả phân c u có giá tr ạt cải tiến. Ph ề xuất tốt h ớng nghi àm thu ọ ợ ậ ỷ ã trình bày thu et al Vol. n là đ c th t toán AGrIT2FPCM thu đư lệ để tối ộc loại hai dạng hạt. , ầ ụm qua các ch ể hi ộ xác th ị ơn so v ên c , “An Efficient k IEEE Trans. On Pattern Analysis and 1, No. 2 (1993), pp. 98 u ra c ện tr chính xác cao hơn tương trên 95 %. Hình 1 ên m ứu tiếp theo nh ưu các tham s ự ực đúng hay ch ương pháp này th à hàm thu ột số tập dữ liệu đ TÀI LI -893. ủa Thu c quan b . ật toán phân cụm C à lo ới các ph Vol. 10 “A possibilistic “A mixed c Biể 5 ài ra ật toán 2. ỉ số u đ . K ại đi các thuộc tính d ỆU THAM KHẢO FCM: The Fuzzy c , No. 2 Công ngh ho ằng bi ồ k ẾT LUẬN ộc loại hai khoảng c , d ương pháp phân c ư s ố của thuật toán phân cụm hoặc mở rộng phân -Means Clustering Algorithm: Analysis and ực hi ặc ch ỉ s ết qu ựa tr ử dụng các ph - -110. -means clustering model“ ểu đ ợ ố TPR c ả ực hiện rút gọn các thuộc tính của dữ liệu ên l 3 (1984), pp 191 ệ thông tin & C ện phân c ất lư ồ c TPR cao nh thử - ực hấp dẫn hạt, ph ã công b approach to clustering“, ụm C ợ trong ứng v ủ nghi Means kh - ng c ớ a t - Means tính toán h ụm trên không gian h ủ hình 1. i các giá tr ất c ệm ư th òn có ý ngh ố cho thấy các kết quả của ụm khác. ương pháp ti Means Clustering Algorithm Vol. 1 a phân c ấ ả các b . ả năng mờ loại hai khoảng ừa. H Machine -203. ơ s Trong đó t và FPR nh , (1997), pp. 11 ở toán học cho tin học ộ ơn n ương pháp này xác , Proceedings of the ụm đư ị TPR cao hơn và dữ ữa, ph ĩa nâng cao khả ến hóa (nh Intelligence thu liệ ạt cải tiến. ợc báo cáo ậ ỏ nh u theo thu ương IEEE Trans. ạt G v t toán đ ất trong -21 pháp th ư các , Vol. . ” ới ề ật ực ”, Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 185 [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 Công nghệ thông tin & Cơ sở toán học cho tin học 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.” 186 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.