Việc phân nhóm dựa trên khoảng cách có khả năng tiến hóa và trực tuyến đƣợc gọi là phương pháp phân nhóm tiến hóa (ECM). Phương pháp này được đề xuất để thực thi phân nhóm dữ liệu không gian đầu vào cho mục đích tạo ra các luật suy diễn mờ. Một nhóm được tạo ra sẽ tương đương với một nút luật ứng với một luật mờ trong hệ thống.
Phương pháp này có hai chế độ: đầu tiên thường được ứng dụng cho hệ thống học trực tuyến, thứ hai thích hợp cho hệ thống học ngoại tuyến. ECM đƣợc dùng trong mô hình DENFIS trực tuyến. ECMc là phần mở rộng của chế độ trực tuyến, nó lấy kết quả từ chế độ trực tuyến thành các giá trị ban đầu đƣợc và dùng cho chế độ DENFIS ngoại tuyến.
3.2.1 Phương pháp phân nhóm tiến hóa trực tuyến:
Phương pháp phân cụm ECM là một thuật toán nhanh và một pha dùng để ước lƣợng một cách linh động số nhóm có trong tập dữ liệu đầu vào và xác định vị trí tâm của nhóm. Đây là phương pháp phân nhóm dữ liệu dựa trên khoảng cách. Với phương pháp này, tâm nhóm đƣợc biểu thị bởi nút có khả năng tiến hóa. Trong bất kì nhóm nào, khoảng cách lớn nhất, MaxDist, giữa một điểm bất kỳ và tâm của nhóm sẽ thấp hơn gía trị ngƣỡng Dthr, đƣợc thiết lập nhƣ là tham số quá trình phân nhóm và ảnh hưởng đến số lượng các nhóm được tạo ra.
Khoảng cách giữa hai vector đƣợc tính dựa trên khoảng cách Eclide bằng công thức tổng quát:
|| -y|| = ( ∑ i-yi|2 )1/2 / q1/2 (3.1)
Với ,y Rq.
Trong quá trình phân nhóm, các mẫu dữ liệu đến từ một dòng dữ liệu và quá trình này bắt đầu với một nhóm rỗng. Khi một nhóm mới đƣợc tạo ra, tâm của nhóm Cc đƣợc xác định và bán kính của nhóm, Ru, đƣợc khởi tạo giá trị 0. Khi các mẫu đƣợc mới đƣợc tuần tự đƣa vào, một vài nhóm sẽ đƣợc cập nhật thông qua việc thay đổi vị trí tâm của chúng và làm tăng dần bán kính của nhóm. Những nhóm nào đƣợc cập nhật
và bán kính sẽ thay đổi bao nhiêu phụ thuộc vào vị trí của các mẫu hiện tại trong không gian đầu vào. Một nhóm sẽ không đƣợc cập nhật nữa khi bán kính Ru của nó đạt đến giá trị bằng với giá trị ngƣỡng Dthr.
Hình 3. 3 : Minh họa việc phân nhóm ECM trong không gian hai chiều.
Với: i : dữ liệu mẫu Ccjk: tâm nhóm
Cjk: nhóm (cụm) Rujk :bán kính nhóm
(a) Mẫu 1 : khởi tạo nhóm C10 (b) Mẫu 2:cập nhật nhóm C10 C11
3 : tạo nhóm C20
4 : không tác động (c) Mẫu 5:cập nhật nhóm C11 C12
6: không tác động
7: cập nhật nhóm C20 C21
8: tạo nhóm C30
(d) Mẫu 9: cập nhật nhóm C12 C13
Thuật toán ECM đƣợc mô tả nhƣ sau:
Bước 0: Tạo ra nhóm đầu tiên C10 bằng cách lấy đơn giản mẫu dữ liệu đầu tiên từ dòng dữ liệu đầu vào làm tâm của nhóm đó Cc10
và thiết lập bán kính Ru10=0.
Bước 1: Nếu tất cả các mẫu từ dòng dữ liệu đã được xử lý xong, thuật toán kết thúc. Ngƣợc lại, mẫu đầu vào hiện tại, i đƣợc thực hiện và khoảng cách giữa mẫu này và tất cả các tâm nhóm Ccj đƣợc thiết lập, Dij=|| i -Ccj||, j=1,2, . . .,n.
Bước 2: Nếu có bất kì khoảng cách Dij=|| i – Ccj||, bằng hoặc nhỏ hơn tối thiểu một bán kính Ruj, j=1,2, . . .n có nghĩa là mẫu i hiện tại thuộc về cụm Cm với khoảng cách tối thiểu đƣợc tính :
Dim=||xi - Ccm||= min (||xi - Ccj||) với ràng buộc Dij Ruj; j=1,2, . . .,n.
Trong trường hợp này, không có một nhóm mới được tạo ra cũng không có nhóm hiện tại được cập nhật (trường hợp x4 và x6 trong hình 3.2) thì thuật toán sẽ quay lại bước 1 ngược lại sẽ đến bước kế.
Bước 3: Tìm cụm Ca (với tâm Cca và bán kính Rua) từ tất cả n nhóm có giá trị Sij=Dij + Ruj, j=1,2,…,n nhỏ nhất :
Sia = Dia + Rua = min( Sij ), j=1,2, ...,n
Bước 4: Nếu Sia > 2*Dthr, mẫu xi không thuộc về bất kì cụm hiện tại nào. Một cụm mới sẽ được tạo ra theo cùng 1 cách như mô tả trong bước 0 (như trường hợp x3 và x8).Và thuật toán quay về bước 1.
Bước 5: Nếu Sia 2*Dthr: nhóm Ca được cập nhật bằng việc di chuyển tâm Cca và tăng giá trị bán kính Rua của nó. Cập nhật bán kính mới Ruanew =Sia/2. Và tâm Ccanew đặt tại điểm trên đường nối liền giữa xi và Cca,và khoảng cách từ tâm mới Ccanew đến điểm xi bằng với Rua new (trường hợp x2, x5, x7, x9).Thuật toán quay về bước 1.
Bằng cách này, khoảng cách tối đa từ bất kì tâm cụm nào đến mẫu thuộc cụm đó không lớn hơn giá trị ngƣỡng Dthr mặc dù các thuật toán không nắm giữ bất kì thông tin nào của các mẫu thông qua.
3.2.2 Phương pháp phân nhóm tiến hóa ngoại tuyến:
(Constrained Optimisation and Offline Elvolving Clustering-ECMc)
Phương pháp này sử dụng thêm một công đoạn để tối ưu hóa kết quả thu được sau khi áp dụng thuật toán ECM. Các dữ liệu phân vùng ECMc bao gồm p vector xi, i=1,2, ...,p , vào n nhóm Cj, j=1,2, …,n; và tìm một nút luật tương ứng mỗi nhóm. Sau đó, thuật toán tiến hành cực tiểu hóa hàm mục tiêu dựa trên độ đo khoảng cách áp dụng cho các ràng buộc trước. Hàm mục tiêu sử dụng khoảng cách Euclic tổng quát (giống 3.1) như là thước đo giữa vector mẫu xi trong nhóm j và tọa độ tâm nhóm Ccj tương ứng. Hàm mục tiêu được xác định bởi phương trình sau:
=∑ j = ∑ ∑ | xi - Ccj || ) (3.2) Với
j = ∑ | xi - Ccj|| ) là hàm mục tiêu trong nhóm j;
i=1, 2 ,…,p; j=1,2, …,n.
Yêu cầu xảy ra phương trình trên khi
|| i - Ccj || Dthr, j=1,2, …,n. (3.3)
Thông thường các nhóm phân vùng được định nghĩa bởi ma trận U (p x n) nhị phân, phần tử uij = 1 nếu các điểm dữ liệu i thứ i thuộc về cụm j; và ngƣợc lại bằng 0.
Một khi các tâm nhóm Ccj đƣợc cố định, việc cực tiểu hóa uij cho hai biểu thức (3.2) và (3.3) đƣợc thực hiện:
||xi - Ccj|| ||xi - Cck|| thì uij = 1 ngƣợc lại uij =0, với mỗi j k (3.4) Đối với chế độ hoạt động ngoại tuyến, phương pháp xác đinh tâm cụm Ccj và thành phần ma trận U sử dụng lặp đi lặp lại các bước sau:
Bước1: Khởi tạo các trung tâm cụm Ccj, j=1, 2, …, n với kết quả nhận được từ tiến trình ECM.
Bước 2: Xác đinh thành phần ma trận U theo biểu thức 3.4
Bước3: Dùng phương pháp cực tiểu hóa các ràng buộc với biểu thức 3.2 và 3.3 để có đƣợc tâm nhóm mới.
Bước 4: Tính toán hàm mục tiêu J theobiểu thức 3.3.Dừng thuật toán nếu kết quả dưới giá trị cho phép nào đó, hoặc kết quả thu được thấp hơn giá trị lần lặp trước đó, hoặc số lần lặp vượt qua một giá trị nào đó.Thuật toán quay lại bước 2.
3.2.3 Ứng dụng Phân cụm dữ liệu Gas-Furnace:
Chuỗi thời gian Gas-Furnace nổi tiếng với thiết lập dữ liệu chuẩn và thường đƣợc sử dụng bởi nhiều nghiên cứu trong lĩnh vực mạng neural mờ và hệ thống mờ cho điều khiển, việc dự đoán và học thích ứng. Nó chứa đựng 296 cặp dữ liệu tiếp nối của khí metan tại thời điểm (t-4), và sản xuất ra CO2 tại thời điểm (t-1) nhƣ là dữ liệu đầu vào, và số lượng CO2 sản xuất ra tại thời điểm t như là kết quả đầu ra.Trong trường hợp này, phép tính phân cụm đƣợc thực thi ở dữ liệu đầu vào. Để tiện cho việc phân tích so sánh, sau phương pháp phân cụm đã được thực hiện với dữ liệu gas-furnace.
Một trong những phương pháp trên đều chia dữ liệu thành 15 cụm. Khoảng cách lớn nhất, MaxD, giữa điểm ví dụ đầu vào và tâm tương ứng và giá trị của hàm mục tiêu J, được định nghĩa bởi phương trình 3.2, được lấy làm tiêu chuẩn để so sánh. Kết quả đƣợc thể hiện ở bảng sau:
Phương pháp MaxD Giá trị hàm mục tiêu J
ECM(online, one pass) 0.1 12.9
EFuNN(online, one pass) 0.11 13.3
SC(offline, one pass) 0.15 11.5
ECMc(offline) 0.1 11.5
FCM (học offline) 0.14 12.4
KM (học offline) 0.12 11.8
Bảng 1 : So sánh phương pháp phân cụm ECM với các phương pháp phân cụm khác qua dữ liệu gas-furnace
Bảng trên cho thấy phương pháp phân cụm ECM và ECMc có cùng giá trị nhỏ nhất MaxD (0.1), điều đó có nghĩa là cả hai phương pháp này phân vùng dữ liệu thống nhất hơn các phương pháp khác.Nói cách khác, chúng ta có thể thấy rằng nếu cả sáu phương pháp trên thu được cùng giá trị của MaxD, thì ECM và ECMc có thể thực hiện ít phân vùng hơn các phương pháp khác.