Phân cụm mờ với trọng số mũ ngôn ngữ

Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 DOI: 10.15625/vap.2015.000192 PHÂN CỤM MỜ VỚI TRỌNG SỐ MŨ NGÔN NGỮ Lê Thái Hưng1, Trần Đình Khang1, Lê Văn Hưng3 1 Trường Đại học Bách khoa Hà Nội 2 Trường Đại học Mỏ Địa chất leehung314@gmail.com, khangtd@soict.hust.edu.vn TÓM TẮT - Bài báo này được thực hiện nhằm mục đích nghiên cứu tìm hiểu thuật toán phân cụm FCM và các ý tưởng cải tiến đã có; tiến hành phân tích và phát hiện những đặc điểm phù hợp trong thuật toán FCM có thể áp dụng được đại số gia tử - một lý thuyết sử dụng đại số trong việc biểu diễn giá trị của các biến ngôn ngữ. Từ đó, đề xuất một hướng cải tiến mới, đó là sử dụng lý thuyết đại số gia tử vào trọng số mũ của thuật toán FCM và sau cùng là xây dựng cài đặt một thuật toán phân cụm mờ sử dụng đại số gia tử để có thể áp dụng giải quyết bài toán phân cụm trong các ứng dụng thực tế. Từ khóa - Phân cụm mờ, Thuật toán FCM, Đại số gia tử, Thuật toán HAmFCM. I. ĐẶT VẤN ĐỀ Bài toán phân cụm là bài toán phân hoạch các đối tượng vào các nhóm sao cho những đối tượng cùng một nhóm thì có nhiều điểm giống nhau trong khi những đối tượng khác nhóm thì có ít điểm giống nhau. Đây là một bài toán có ý nghĩa quan trọng trong nhiều lĩnh vực của đời sống con người, giúp chúng ta hiểu rõ hơn về bản chất, cấu trúc của dữ liệu để từ đó xử lý dữ liệu được hiệu quả hơn. Nhằm giải quyết bài toán này, đã có rất nhiều thuật toán phân cụm được đề xuất, trong đó có thể nói tiêu biểu nhất là thuật toán FCM (Fuzzy c-Means) [1] ra đời vào năm 1981. Kể từ đó đến nay, đã có rất nhiều các phương pháp mới được đưa ra dựa trên nền tảng FCM, nhằm cải tiến, khắc phục các điểm còn hạn chế, giúp cải thiện hơn nữa khả năng phân cụm của thuật toán này trong nhiều trường hợp khác nhau. Bài báo được thực hiện nhằm mục đích nghiên cứu tìm hiểu thuật toán phân cụm FCM và các ý tưởng cải tiến đã có; tiến hành phân tích và phát hiện những đặc điểm phù hợp trong thuật toán FCM có thể áp dụng được đại số gia tử (Hedge Algebra - HA) - một lý thuyết sử dụng đại số trong việc biểu diễn giá trị của các biến ngôn ngữ [3,4,5,6]. Từ đó, bài báo đề xuất một hướng cải tiến mới, đó là sử dụng lý thuyết đại số gia tử vào trọng số mũ của thuật toán FCM, và sau cùng là xây dựng cài đặt một thuật toán phân cụm mờ sử dụng đại số gia tử HAmFCM để có thể áp dụng giải quyết bài toán phân cụm trong các ứng dụng thực tế. Phần thực nghiệm với các bộ dữ liệu UCI [7] có so sánh với các phương pháp cải tiến khác FCMT2I, FCMT2G [2,8] để minh hoạ hiệu quả của phương pháp. Cấu trúc của bài báo như sau, Phần II trình bày về phân cụm mờ và thuật toán FCM, Phần III là đề xuất cải tiến HAmFCM và Phần IV là các thực nghiệm. II. BÀI TOÁN PHÂN CỤM MỜ A. Bài toán phân cụm: là bài toán phân hoạch các đối tượng vào các nhóm sao cho những đối tượng cùng một nhóm thì có nhiều điểm giống nhau trong khi những đối tượng khác nhóm thì có ít điểm giống nhau. Đây là một bài toán có ý nghĩa quan trọng trong nhiều lĩnh vực của đời sống con người, giúp chúng ta hiểu rõ hơn về bản chất, cấu trúc của dữ liệu để từ đó xử lý dữ liệu được hiệu quả hơn. Nhằm giải quyết bài toán này, đã có rất nhiều thuật toán phân cụm được đề xuất, trong đó có thể nói tiêu biểu nhất là thuật toán FCM (Fuzzy c-Means) ra đời vào năm 1981. Kể từ đó đến nay, đã có rất nhiều các phương pháp mới được đưa ra dựa trên nền tảng FCM, nhằm cải tiến, khắc phục các điểm còn hạn chế, giúp cải thiện hơn nữa khả năng phân cụm của thuật toán này trong nhiều trường hợp khác nhau. B. Thuật toán FCM Trước hết, ta sẽ định nghĩa một cách chính xác bài toán phân cụm. Xét bài toán phân cụm n phần tử trong tập dữ liệu: { }nxxxX ,...,, 21= Mỗi phần tử Xxi ∈ , i=1, 2,n là một vector d chiều. Ta định nghĩa một c-phân cụm của X là một phân hoạch X vào c tập (cụm) cCCC ,..., 21 , sao cho 3 điều kiện sau được thỏa mãn: - ܥ௜ ് ∅ với ݅ ൌ 1, 2, , ܿ - ∪ci i XC1= = - ܥ௜ ∩ ܥ௝ ൌ ∅ với ݅ ് ݆; ݅, ݆ ൌ 1, 2, , ܿ Trong thuật toán FCM, hàm thuộc được biểu diễn rời rạc thành một ma trận thực U kích thước n ൈ c: - ܷሺ݅, ݇ሻ là độ thuộc của phần tử ix vào cụm thứ kC : 1 ൑ ݅ ൑ ݊; 1 ൑ ݇ ൑ ܿ - ܷ có ݊ ൈ ܿ phần tử - 0 ൑ ܷሺ݅, ݇ሻ ൑ 1 538 PHÂN CỤM MỜ VỚI TRỌNG SỐ MŨ NGÔN NGỮ - ܷሺ݅, ݇ሻ càng lớn thì phần tử ݔ௜ càng có nhiều khả năng thuộc vào cụm ݇ - ܷ được gọi là ma trận thuộc Dựa trên mô hình ma trận thuộc này, một hàm mục tiêu được xác định sao cho thuật toán phân cụm phải tối thiểu hóa hàm mục tiêu. Thuật toán FCM sử dụng hàm mục tiêu là: ∑∑ = = −= n i c k m kCiXkiUCUJ 1 1 2)()(),(),( (1) Ở đây đã sử dụng các ký hiệu sau: - ܺሺ݅ሻ là vector giá trị của phần tử ix - ܥ là tập vector giá trị tâm cụm của ܿ cụm cCCC ,..., 21 - ܥሺ݇ሻ là vector giá trị tâm cụm kC - ܦሺ݅, ݇ሻ = 2)()( kCiX − là một độ đo khoảng cách giữa 2 vector ܺሺ݅ሻ và ܥሺ݇ሻ. Thuật toán FCM nguyên bản sử dụng độ đo Euclid - ݉ là tham số của thuật toán, gọi là trọng số mũ Thuật toán chi tiết: ™ Bước 1: Khởi tạo giá trị ܷ, ܥ, chọn giá trị tham số ݉ (݉ ൐ 1 và thường được chọn trong khoảng [2,40]) ™ Bước 2: Với mọi ݇, cập nhật giá trị ܥ theo công thức: ∑ ∑ = = = n i m n i m kiU iXkiU kC 1 1 ),( )(),( )( (2) ™ Bước 3: Với mọi ݅, ݇ cập nhật giá trị ܷ theo công thức: 1 1 1 2 ),( ),(),( − = − ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ = ∑c j m jiD kiDkiU (3) Với ܦሺ݅, ݇ሻ = 2)()( kCiX − ™ Bước 4: Kiểm tra điều kiện dừng: Tính giá trị hàm mục tiêu ܬ theo công thức (1.1). Nếu giá trị ܬ thay đổi, quay lại bước 2, trái lại ta kết thúc thuật toán. Ta có nhận xét rằng, thuật toán FCM gồm 2 bước chính là cập nhật tâm cụm-công thức (1.2) và cập nhật ma trận thuộc-công thức (1.3). Hai bước này được thực hiện luân phiên nhằm tối thiểu hóa hàm ܬ. Thuật toán sẽ dừng khi ܬ hội tụ. Sau khi kết thúc thuật toán, ta sẽ ra quyết định phân cụm dựa vào giá trị ܷ. Nhược điểm thuật toán FCM: FCM là một thuật toán đột phá so với các thuật toán phân cụm rõ khác vì FCM có khả năng biểu diễn tổng quát hơn và cho kết quả phân cụm chính xác hơn trong nhiều trường hợp. Nhưng FCM vẫn còn đó những nhược điểm: - Thuật toán ngầm định mỗi cụm có một tâm cụm và các phần tử thuộc cụm nào thì nằm gần tâm cụm đó - Kết quả của thuật toán phụ thuộc vào khởi tạo U, C ban đầu. Nếu khởi tạo không tốt, có thể bị hội tụ địa phương - Thuật toán nhạy cảm với sự xuất hiện của nhiễu và các phần tử ngoại lai do chưa có mô hình biểu diễn nhiễu - Phân cụm chưa xác đáng với các đối tượng nằm ở ranh giới giữa các cụm - Chưa có tiêu chí cụ thể để lựa chọn giá trị cho tham số m, thường chọn bằng thử nghiệm nhiều lần Với các nhược điểm đó, FCM vẫn cần được nghiên cứu để được cải thiện hơn nữa. Bài báo này sẽ đề xuất một hướng cải tiến cho FCM bằng cách sử dụng trọng số mũ ngôn ngữ xác định bởi đại số gia tử. C. Ý tưởng cải tiến FCM Khi đưa ra quyết định phân cụm, FCM dựa vào công thức: 1 1 1 2 ),( ),(),( − = − ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ = ∑c j m jiD kiDkiU Lh c c p c U tr A ê Thái Hưng, Trầ Công th ọa trong trườ Rõ ràng ác phần tử ở ác phần tử ở hần tử này. T ác phần tử đó là như nhau Để hợp - Khi k của U - Khi k m nên Tức là ị ܯሺ݅, ݇ሻ nằm Hàm m Vấn đề . Tập mờ trọ Đầu tiê n Đình Khang, L ức này có đặ ng hợp ܿ ൌ 2 , với các phầ gần tâm cụm ranh giới nga rong khi đó, luôn rơi vào với các phầ lý, ta có quy hoảng cách tư tăng lên hoảng cách tư lớn, phán ản m thay đổi t trong khoản ục tiêu trở thà bây giờ là xây ng số mũ n, ta cần định ê Văn Hưng c điểm, khi m : n tử ở ranh gi (khoảng cách y được, cho n các phần tử g cụm gần nhấ n tử gần tâm luật sau: ơng đối nhỏ ơng đối lớn ( h độ tuyệt đố heo khoảng g [m_min,m_ nh: UJ ,( dựng tập giá nghĩa lại kho càng nhỏ, độ ới cụm (khoả tương đối nh ên ta cần đồ ần tâm cụm n t. Do FCM ch cụm và các p (phần tử gần n phần tử nằm i của U giảm x cách tương đ max] và các c ),( ⎜⎜ ⎜ ⎝ ⎛ = ∑ j kiU ∑ = = n ikC )( ∑ ∑ = = n i c k C 1 ) trị M(i,k) nh III. THUẬ ảng cách tươn ௜ܶ,௞ tuyệt đối của ng cách tương ỏ). Lý do là thị U thoải h ên có đồ thị U ỉ sử dụng m hần tử ở ran hư đã ở rất g ở ranh giới giữ uống ối, như vậy ông thức cập 1 ),( ),( = ⎠ ⎞ ⎜⎜⎝ ⎛c jiD kiD ( ∑ = n i M kiM kiU kiU 1 1 , ),( ),( = MkiU 1 ),( ư thế nào để t T TOÁN HA g đối: ൌ ஽ሺ௜,௞ሻ∑ ஽ሺ௜,೎ೕసభ U (độ dốc củ đối lớn), độ bởi vì ta chưa ơn để linh độ dốc hơn để ột giá trị m d h giới, điều ần một cụm n a các cụm ho để biểu diễn nhật sẽ trở thà ( ) 1 1, 2 − − ⎟⎟ ⎟ ⎠ ⎞ ⎟⎟ kiM ) ( )ki iX , )( − ki iX),( )( hỏa mãn quy mFCM ௝ሻ a đồ thị) càng tuyệt đối của thể đưa ra q ng hơn trong đảm bảo kiểm uy nhất, nên này là chưa h ào đó) thì m n ặc chưa quá ݉, ta cần sử nh: kC 2)( luật nói ở trên cao, như hình U phải thấp uyết định phâ việc chọn cụ soát sự phâ mức độ tuy ợp lý. ên nhỏ, độ tu gần một cụm dụng một t . 539 sau minh hơn so với n cụm với m cho các n cụm cho ệt đối của yệt đối nào cả) thì ập các giá (4) (5) (6) (7) 540 PHÂN CỤM MỜ VỚI TRỌNG SỐ MŨ NGÔN NGỮ Dễ thấy độ đo này có tính chất: - Khi ݔ௜ tiến rất gần ܥ௞, ܦሺ݅, ݇ሻ tiến về 0, ௜ܶ,௞ sẽ có giá trị tiến về 0, nhưng luôn lớn hơn 0 - Khi ݔ௜ tiến ra xa ܥ௞, ܦሺ݅, ݇ሻ tiến ra ∞, ௜ܶ,௞ sẽ luôn lớn hơn 0 và có xu hướng tăng dần Ngoài ra, mẫu của ௜ܶ,௞ luôn khác 0, nên an toàn trong quá trình tính toán. Thêm nữa, để phù hợp với miền định lượng ngữ nghĩa của HA sau này (từ 0 đến 1), ta tiến hành chuẩn hóa ௜ܶ,௞ về miền [0,1] theo công thức như sau: ܳ௜,௞ ൌ ்೔,ೖି்೘೔೙೘்ೌೣି்೘೔೙ (8) Tiếp theo, nhắc lại quy luật cần thỏa mãn: - ܳ௜,௞ nhỏ thì ܯሺ݅, ݇ሻ nhỏ - ܳ௜,௞ lớn thì ܯሺ݅, ݇ሻ lớn Một hàm ánh xạ tuyến tính đơn giản có thể giúp tính ܯሺ݅, ݇ሻ từ ܳ௜,௞ như sau: ܯሺ݅, ݇ሻ ൌ ܳ௜,௞ ൈ ሺ݉_݉ܽݔ െ݉_݉݅݊ሻ ൅ ݉௠௜௡ ሺ9ሻ Như vậy, ta đã có phương pháp để xác định giá trị các trọng số mũ trong ma trận trọng số mũ ܯ. Ở đây, công thức (9) ngầm định mối quan hệ giữa khoảng cách tương đối và trọng số mũ là quan hệ tuyến tính cùng tăng cùng giảm. Điều này tất nhiên là chưa phản ánh chính xác thực tế, do đó, ta cần gắn với mỗi giá trị trọng số mũ một độ đo thể hiện độ tin cậy. Độ tin cậy, kí hiệu ܴሺ݅, ݇ሻ thể hiện mức độ tin cậy của giá trị ܯሺ݅, ݇ሻ khi tính theo công thức (9). Độ tin cậy có tính chất: - 0 ൑ ܴሺ݅, ݇ሻ ൑ 1 - ܴሺ݅, ݇ሻ nhỏ, độ chắc chắn của giá trị ܯሺ݅, ݇ሻ nhỏ, nhiều khả năng sẽ phải thay đổi bằng một giá trị khác phù hợp hơn - ܴሺ݅, ݇ሻ lớn, độ chắc chắn của giá trị ܯሺ݅, ݇ሻ lớn, nhiều khả năng sẽ phải giữ nguyên Cách tính độ tin cậy ܴሺ݅, ݇ሻ: ܴሺ݅, ݇ሻ ൌ ܴ൫ܯሺ݅, ݇ሻ൯ ൌ ܴ൫ܳ௜,௞൯ ൌ ௠݂ ቀݒିଵ൫ܳ௜,௞൯ቁ ሺ10ሻ Từ đây, ta có tập mờ trọng số mũ tương ứng là: (11) B. Cập nhật trọng số mũ Nếu sử dụng trực tiếp ܯሺ݅, ݇ሻ tính theo công thức (9) thì hơi cứng nhắc vì quan hệ giữa khoảng cách tương đối và trọng số mũ có thể không phải là quan hệ tuyến tính. Do đó để làm linh hoạt, ta sẽ dùng độ tin cậy của trọng số mũ để cập nhật lại giá trị trọng số mũ. Cách làm như sau, tại vòng lặp thứ t, tính ܳ௜,௞ሺ∗ሻ từ tập dữ liệu, sau đó cập nhật giá trị ܳ௜,௞ሺ௧ሻ ,ܯሺ݅, ݇ሻሺ௧ሻ như sau: ܳ௜,௞ሺ௧ሻ ൌ ܳ௜,௞ሺ௧ିଵሻ ൅ ܴሺ݅, ݇ሻ ൈ ൫ܳ௜,௞ሺ∗ሻ െ ܳ௜,௞ሺ௧ିଵሻ൯ ܯሺ݅, ݇ሻሺ௧ሻ ൌ ܳ௜,௞ሺ௧ሻ ൈ ሺ݉_݉ܽݔ െ݉_݉݅݊ሻ ൅݉_݉݅݊ ሺ12ሻ Ở đây dễ thấy, nếu độ tin cậy là tuyệt đối ܴሺ݅, ݇ሻ ൌ 1, khi đó ܳ௜,௞ሺ௧ሻ ൌ ܳ௜,௞ሺ∗ሻ và ܯሺ݅, ݇ሻ được tính y hệt như (9). Và khi độ tin cậy ܴሺ݅, ݇ሻ ൌ 0, ܳ௜,௞ሺ௧ሻ ൌ ܳ௜,௞ሺ௧ିଵሻ, tức là không có sự cập nhật giá trị ܳ௜,௞ሺ௧ሻ và ܯሺ݅, ݇ሻሺ௧ሻ. Nói chung, độ tin cậy càng cao, giá trị ܯሺ݅, ݇ሻ càng tiến gần đến giá trị tính được bằng công thức (9)-tức là tiến gần đến một giá trị mới xác định từ ánh xạ tuyến tính của trạng thái phân cụm hiện tại, còn khi độ tin cậy thấp, giá trị ܳ௜,௞ሺ௧ሻ và ܯሺ݅, ݇ሻሺ௧ሻ có xu hướng ít tuân theo quy luật tuyến tính của sự thay đổi của trạng thái phân cụm. C. Tối ưu tham số HA Trong công thức (3), ảnh hưởng của đại lượng độ tin cậy là rất to lớn, quyết định trực tiếp đến giá trị ܯሺ݅, ݇ሻ và độ tin cậy này hoàn toàn xác định bởi HA. Nói cách khác, giá trị các tham số mờ của HA cũng tham gia vào quá trình xác định ܯሺ݅, ݇ሻ. Việc cập nhật thay đổi các tham số HA làm thay đổi khả năng biểu diễn ngôn ngữ của HA, từ đó tác động đến hiệu quả của thuật toán HAmFCM. Ở đây, ta đưa ra tiêu chí cập nhật tham số HA đó là làm giảm lỗi ánh xạ ngữ nghĩa và hàm mục tiêu. Trước hết, ta định nghĩa lỗi ánh xạ ngữ nghĩa của giá trị thực ݍ chính là sai khác giữa ݍ và định lượng ngữ nghĩa của HA: ݁ሺݍሻ ൌ |ݒሺݒିଵሺݍሻሻ െ ݍ| (13) Ta thấy rằng khi lỗi này càng nhỏ, HA càng biểu diễn tốt các giá trị trọng số mũ vì các giá trị ngôn ngữ của HA có định lượng ngữ nghĩa rất gần với các giá trị ݍ - tương ứng với các trọng số mũ. Việc tìm ra một phương án cập nhật tham số HA sao cho chắc chắn làm giảm lỗi này là không dễ. Do đó, NVĐA đã sử dụng một ý tưởng heuristic như sau: khi lỗi này nhỏ, ta mong muốn HA sẽ được cập nhật ít đi, không cần thay đổi quá nhiều. Ngược lại, khi lỗi ( ) ( )( )[ ] ∑ ∈∀ = max_min,_ , , , mm kiM kiM kiRA Ln g đ v h đ s D T Đ tr Đ tử B ܪ K K K K K K K K B F ê Thái Hưng, Trầ ày còn lớn, c iúp lỗi ánh xạ Thêm n - ߤሺ݈݁ݏ - ௠݂ሺݏ݉ Sẽ là hợ ược giá trị ng à phần tử sinh Cách cậ - Khi lỗ - Chỉ c Tuy nh iện các phươn - Sau k - Nếu h trạng th - Ngoà phải ch Thực h ến một trạng au khoảng 15 . Thuật toán Các bước huật toán ܪ ầu vào: Tập ọng số mũ ሾ݉ ầu ra: Vị trí , với ݈ܾ݈ܽ݁ሺ݅ ước 1: Khởi ܣ ൌ ሺܣܺ, ሼݏ݉ hởi tạo ngẫu hởi tạo biến hởi tạo ma tr hởi tạo ma tr hởi tạo ma tr hởi tạo ma tr hởi tạo biến ܬ hởi tạo biến ước 2: Cập n OR ݅ ൌ 1 TO n Đình Khang, L ác tham số củ ngữ nghĩa nh ữa, các tham ݏሻ, ߤሺ݌݋ݏݏܾ݈݅ ݈݈ܽሻ, ௠݂ሺܾ݅݃ p lý nếu ta ch ôn ngữ ݔො ൌ ݒ này. Lấy ví p nhật như vậ i ánh xạ ngữ ập nhật các th iên, do đây ch g pháp sau: hi cập nhật th àm mục tiêu ái trước đó i ra, để đảm b uẩn hóa tham iện các quy tắ thái phân cụm -20 vòng lặp, HAmFCM chính thuật to ܣ݉ܨܥܯ các phần tử c _݉݅݊,݉_݉ܽ tâm các cụm ሻ, ݅ ൌ 1,2, ݊ tạo ݈݈ܽ, ܾ݅݃ሽ, ሼ݈݁ nhiên ܥ; ܥ௢௟ௗ ൌ 0; ận ܷሺ݅, ݇ሻ ൌ ận ܳሺ݅, ݇ሻ ൌ ận ܴሺ݅, ݇ሻ ൌ ận ܯሺ݅, ݇ሻ ൌ ௢௟ௗ ൌ ∞, ܬ ൌ ݑ݌݀ܽݐ݁ ൌ ݐݎݑ hật ܯ ݊ ê Văn Hưng a HA cần ph ỏ hơn. số HA ta cần ݕሻ, ߤሺ݉݋ݎ݁ሻ, ሻ ỉ cập nhật cá ିଵሺݍሻ, ݔො sẽ c dụ, nếu ݔො ൌ " ߤሺݒ݁ݎ ߤሺ݉݋ݎ ௠݂ሺܾ݅ y đảm bảo ng nghĩa nhỏ, th am số có liên ỉ là đề xuất m am số HA, ta giảm so với t ảo tính đúng số HA c trên không n tốt) mà còn ta có thể dừn án ần phân cụm ݔሿ ܥ, ݒớ݅ ܥሺ݇ሻ, là nhãn của ݏݏ, ݌݋ݏݏܾ݈݅ݕ 0 ∀݅, ݇; 0 ∀݅, ݇; 0 ∀݅, ݇; ݉௠௜௡ ∀݅, ݇; 1; ݁; ải được cập n cập nhật bao ߤሺݒ݁ݎݕሻ c tham số có hứa các gia t ݒ݁ݎݕ ݒ݁ݎݕ ݉ ݕሻ ൌ ߤሺݒ݁ݎݕ ݁ሻ ൌ ߤሺ݉݋ݎ ݃ሻ ൌ ௠݂ሺܾ݅݃ uyên tắc: ì lượng cập nh quan đến lỗi ang tính heu tính hàm mục rước đó, tiếp đắn của tham hững đảm bả đảm bảo sự g việc cập nhậ ܺ, ݒớ݅ ܺሺ݅ሻ, ݇ ൌ 1,2. . . ܿ l phần tử thứ ݅ , ݉݋ݎ݁, ݒ݁ݎݕሽ hật với một l gồm: liên quan đến ử và một phần ݋ݎ݁ ܾ݅݃" và ݁ ሻ ൅ ݁ሺݍሻ ∗ 2 ݁ሻ ൅ ݁ሺݍሻ ൌ ሻ ൅ ݁ሺݍሻ ൌ ật là nhỏ ristic, để đảm tiêu tục cập nhật H số HA (các o thuật toán đ hội tụ của thu t HA. ݅ ൌ 1,2݊ là à giá trị vecto . , ൑ሻ, quan hệ ượng lớn hơn lỗi ݁ሺݍሻ. Nói tử sinh. Ta ሺݍሻ=0.01, ta ൌ ߤሺݒ݁ݎݕሻ ൅ ߤሺ݉݋ݎ݁ሻ ൅ ௠݂ሺܾ݅݃ሻ ൅ 0 bảo tiêu chí h A, nếu khôn tham số HA úng về mặt to ật toán. Tron phần tử thứ r của tâm cụm ܵܫܩ, ܮ ൌ 3; với hi vọng cách khác, v sẽ chỉ cập nh tiến hành cập 0.02 0.01 .01 àm mục tiêu g ta dừng việ nằm trong kh án học (làm g thực tế thử ݅. Số cụm ܿ c thứ ݇. Nhã sẽ đạt được t ới một giá trị ật ߤ, ௠݂ của c nhật như sau luôn giảm, ta c cập nhật và oảng tử 0 đến hàm mục tiêu nghiệm, thườ ần phân loại. n tên cụm củ 541 rạng thái ݍ, ta tìm ác gia tử : (14) phải thực khôi phục 1) ta còn giảm, dẫn ng thì chỉ Dải giá trị a các phần 542 PHÂN CỤM MỜ VỚI TRỌNG SỐ MŨ NGÔN NGỮ FOR ݇ ൌ 1 TO ܿ Thực hiện (7); Thực hiện (8); Thực hiện (10); Thực hiện (12); Bước 3: Kiểm tra hàm mục tiêu Thực hiện (6); IF ܬ >ܬ௢௟ௗ THEN ݑ݌݀ܽݐ݁ ൌ ݂݈ܽݏ݁; ܬ௢௟ௗ ൌ ܬ; Bước 4: Cập nhật HA IF ݑ݌݀ܽݐ݁ THEN FOR ݅ ൌ 1 TO ݊ FOR ݇ ൌ 1 TO ܿ Cập nhật HA như (14) Chuẩn hóa tham số HA Bước 5: Cập nhật ܥ, ܷ FOR ݅ ൌ 1 TO ݊ FOR ݇ ൌ 1 TO ܿ Thực hiện (5); Thực hiện (6); Bước 6: Kiểm tra điều kiện dừng IF ܥ௢௟ௗ ് ܥ THEN ܥ௢௟ௗ ൌ ܥ; Quay lại Bước 2; ELSE Chuyển đến Bước 7; Bước 7: Đọc kết quả phân cụm FOR ݅ ൌ 1 TO ݊ ݈ܾ݈ܽ݁ሺ݅ሻ ൌ argmax௞൫ܷሺ݅, ݇ሻ൯ ; RETURN ሾܥ, ݈ܾ݈ܽ݁ሿ; Độ phức tạp thuật toán: Ở đây, ta đánh giá độ phức tạp theo số phần tử đầu vào cần phân cụm ݊. Các yếu tố khác tham gia vào độ phức tạp của thuật toán như số cụm ܿ cần phân hoạch và các tham số của HA như |ܪ|, |ܩ|, và ܮ đều được coi là hằng số. Trước hết, ta đánh giá độ phức tạp của một vòng lặp của thuật toán này (từ bước 2 đến bước 6) như sau: - Bước 2: Do các tính toán trong vòng lặp đều có độ phức tạp Οሺ1ሻ, độ phức tạp cho bước này là số vòng lặp, tức là Οሺ݊ ൈ ܿሻ ൌ Οሺ݊ሻ - Bước 3: Độ phức tạp Οሺ1ሻ - Bước 4: Do các tính toán trong vòng lặp đều có độ phức tạp Οሺ1ሻ, độ phức tạp cho bước này là số vòng lặp, tức là Οሺ݊ ൈ ܿሻ ൌ Οሺ݊ሻ - Bước 5: Do các tính toán trong vòng lặp đều có độ phức tạp Οሺ1ሻ, độ phức tạp cho bước này là số vòng lặp, tức là Οሺ݊ ൈ ܿሻ ൌ Οሺ݊ሻ - Bước 6: Độ phức tạp Οሺ1ሻ Ngoài vòng lặp chính này, ta còn phải xét: - Bước 1 (khởi tạo): khởi tạo các ma trận cũng chỉ mất Οሺ݊ሻ. - Bước 7 (đọc kết quả): Tìm giá trị lớn nhất của độ thuộc cũng chỉ có độ phức tạp là Οሺ݊ሻ Do đó, độ phức tạp của cả thuật toán sẽ là: số vòng lặp ൈ Οሺ݊ሻ Nhắc lại rằng thuật toán HAmFCM (và cả thuật toán FCM) chỉ dừng khi không còn sự cập nhật ở tâm cụm, tức là số vòng lặp là không biết trước, thậm chí trong trường hợp xấu, số vòng lặp có thể tiến đến vô cùng. Do đó, việc Lđ c ܯ Ư tr q n n t D [ d th A H th q T H ê Thái Hưng, Trầ ánh giá độ ph hỉ cần so sánh và cập nhật u điểm của Như ta ị trọng số mũ uả là: - Độ th cách cho c tử nằm - Việc như t phân hầu h cho m Việc H ghĩa của giá gữ của con ng ính chất này. ưới đây là hì Chương m_min, m_m iện bên phải ị một số thôn . Thử nghiệ Cụ thể: - Dữ liệ - Dữ liệ Hai thu AmFCM vẫn ể có thể thay uan tâm đến t ập mờ trọng A tìm được c n Đình Khang, L ức tạp chỉ có độ phức tạp HA, thì so vớ HAmFCM so đã biết, điểm trong quá trìn uộc U được x tương đối tươ ác phần tử nằm gần tâm cụm sử dụng một rong FCM, ta cụm tốt nhất, ết mọi bài toá ỗi phần tử tro AmFCM biểu trị các trọng s ười để dễ hìn nh ảnh minh h trình cho p ax] và số cụm là minh họa h g số, kết quả m với bộ dữ l u hoa, Iris: số u rượu vang, ật toán HAm là dải giá trị đổi theo từn rường hợp tố số mũ ngôn n ũng được nêu ê Văn Hưng ý nghĩa trong trong một vò i FCM, độ ph với FCM: khác biệt lớn h cập nhật độ ác định một c ng ứng được ở ranh giới . dải các giá trị cần phải thử thì HAmFCM n. Thuật toán ng quá trình diễn trọng s ố mũ trong q h dung, dễ n ọa giao diện hép người dù cần phân ho ình ảnh diễn b sau khi chạy iệu chuẩn UC chiều 4, số c Wine: số chi FCM và FC cho trọng số g bộ dữ liệu, t nhất, do đó gữ tìm được ra để tiện the ௠݂ሺݏ݉ܽ một vòng lặ ng lặp mà thô ức tạp lý thuy nhất giữa HA thuộc và tâm ách linh hoạt sử dụng. Điề giữa các cụm trọng số mũ chọn tham số chỉ cần xác HAmFCM s phân cụm. ố mũ như mộ uá trình vận ắm bắt và điề IV. TH chương trình: Hình 1. G ng nhập tham ạch c. Giao d iến quá trình thuật toán. I ụm 3, số mẫu ều 13, số cụm M cũng sẽ đ mũ, còn tham sẽ được ghi phần kết quả sẽ được chỉ r o dõi, bao gồ ݈݈ሻ, ௠݂ሺܾ݅݃ሻ, ߤ p. Và khi so s i. Và như ta t