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