chương 1 như: thuật toán k-means, thuật toán k-Medoids, DBSCAN, STING,. Phân cụm mờ Trong khi đó, đối với phân cụm dữ liệu mờ các đối tượng dữ liệu có thể thuộc về nhiều hơn một cụm, tương ứng với các mức độ liên thuộc khác nhau, đặc trưng cho mức độ mà các điểm dữ liệu đó thuộc về các cụm. Cho tập dữ liệu X gồm n đối tượng X={𝑥1 , 𝑥2 , … 𝑥𝑛 }⊂ 𝑅 𝑆 tổ chức thành c cụm thể hiện qua các hàm liên thuộc 𝑈𝑖𝑗 mô tả mức độ đối tượng dữ liệu 𝑥𝑗 thuộc về cụm i, với mọi𝑥𝑗 ∈ X. - Mức độ liên thuộc nhận giá trị giữa 0 và 1 (Công thức 1.
Đối tượng dữ liệu gần trung tâm cụm có mức độ thuộc cao hơn so với những đối tượng nằm ở gần biên của cụm. 19 Đối tượng 𝑥𝑗 càng xa tâm cụm i thì giá trị hàm liên thuộc 𝑈𝑖𝑗 càng dần về 0; Tương tự như vậy đối tượng 𝑥𝑗 càng gần tâm cụm i thì giá trị hàm liên thuộc 𝑈𝑖𝑗 càng dần tới 1; Nếu đối tượng 𝑥𝑗 nằm xa tất cả các cụm thì giá trị hàm liên thuộc 𝑈𝑖𝑗 dần tới 1/c. - Tổng mức độ liên thuộc của một đối tượng tới tất cả các cụm là 1 (Công thức 1.13b) - Điều kiện (công thức 1.13c) đảm bảo rằng không tồn tại một cụm nào mà không chứa bất kỳ đối tượng nào.13c) Đặt 𝑀𝑓𝑐 là tập tất cả phân hoạch mờ của X: 𝑀𝑓𝑐 = {𝑈 ∈ 𝑅𝑐𝑥𝑛 │𝑈𝑖𝑗 ∈ [0,1], ∀𝑖, 𝑗; ∑𝑐𝑖=1 𝑈𝑖𝑗 = 1 , ∀𝑗; 0 < ∑𝑛𝑗=1 𝑈𝑖𝑗 < n, ∀𝑖}.14) Rc x n là không gian của tất cả các ma trận thực cấp c x n. Để làm rõ hơn sự khác nhau giữa phân cụm rõ và phân cụm mờ ta xét ví dụ minh họa với tập dữ liệu hình cánh bướm (Butterfly) gồm 15 điểm (Hình 1.
Tập dữ liệu hình cánh bướm Sử dụng phương pháp phân cụm rõ để phân cụm những điểm dữ liệu trên, kết quả thu được hai cụm (xem Hình 1. Có thể thấy kết quả này không cho thấy cấu trúc tự nhiên của tập dữ liệu. Với điểm dữ liệu (4, 3.5) nằm ở giữa có khả năng thuộc về cả 2 cụm là như nhau, nhưng phương pháp phân cụm rõ đánh dấu điểm này thuộc về cụm A với độ thuộc bằng 1. Kết quả phân cụm rõ với tập dữ liệu hình cánh bướm Đối với tập dữ liệu hình cánh bướm trên phân cụm rõ không cho thấy sự khác biệt giữa các điểm dữ liệu trong cùng một cụm – những phần tử dữ liệu nằm ở trung tâm của cụm và những phần tử dữ liệu nằm ở gần biên của cụm.
Ngược lại trong phân cụm mờ mỗi điểm dữ liệu được mô tả bởi một giá trị liên thuộc, tùy vào việc chúng có nằm gần các trung tâm cụm hay không mà chỉ ra mức độ thuộc của chúng với cụm đó. Vẫn với tập dữ liệu hình cánh bướm ở trên, với phương pháp phân cụm mờ, điểm dữ liệu (4, 3.5) có giá trị mức độ liên thuộc về hai cụm A và B đều là 0.5, phản ánh đúng vị trí nằm giữa hai cụm của điểm dữ liệu này (Hình 1. Hai cụm mờ của tập dữ liệu hình cánh bướm) Hình 1. Hai cụm mờ của tập dữ liệu hình cánh bướm 21 Bảng 1.
Giá trị hàm liên thuộc của tập dữ liệu hình cánh bướm sử dụng thuật toán k-means và c-means mờ. Phân cụm rõ Phân cụm mờ Dữ liệu Thuật toán k-means Thuật toán C-means mờ 𝑈1 𝑈2 𝑈1 𝑈2 1. Tối ưu đa mục tiêu [1] 1. Bài toán tối ưu tổng quát F(X) => max (min) với X ∈ D gọi là miền ràng buộc.
Trong đó: - F(X) có thể là một hàm vô hướng hay hàm véc tơ, tuyến tính hay phi tuyến. + Nếu F là hàm vô hướng thì ta có mô hình quy hoạch (tối ưu) đơn mục tiêu, + Nếu F là vectơ thì có mô hình quy hoạch (tối ưu) đa mục tiêu. - X có thể là một biến đơn lẻ hay một tập hợp nhiều biến tạo thành một vectơ hay thậm chí là một hàm của nhiều biến khác. Biến có thể nhận các giá trị liên tục hay rời rạc.
- D là miền ràng buộc của X, thường được biểu diễn bởi các đẳng thức, bất đẳng thức và được gọi là miền phương án khả thi hay phương án chấp nhận được. Tối ưu đơn mục tiêu Dạng chính tắc của bài toán tối ưu toàn cục một mục tiêu được biểu diễn như sau: 22 Max (Min) f(X) X = (x1, x2, …, xn) với(i) g(X) ≤ 𝟎, j=1, 2, …, k, (ii) g(X) = 0, j=k+1, k+2, …, m, Trong các bài toán thực tế có thể bổ sung các ràng buộc dạng: (iii) 𝒂𝒊 ≤ 𝒙𝒊 ≤ 𝒃𝒊 , 𝒊 = 𝟏, 𝟐, … , 𝒏 Hàm mục tiêu f(x) và các hàm ràng buộc gj(x) với j=1, 2, …, m có thể là tuyến tính hay phi tuyến. Véctơ X có thể bao gồm các thành phần rời rạc hay liên tục hoặc là sự kết hợp giữa các thành phần rời rạc và các thành phần liên tục. Các dạng khác của bài toán tối ưu một mục tiêu đều có thể đưa về dạng chính tắc theo những quy tắc nhất định.
Nếu ký hiệu D là miền các phương án (miền ràng buộc) cho bởi các ràng buộc (i), (ii) hoặc (iii) thì bài toán trên đây có thể viết gọn hơn như sau: f(x) →max (min) với x ∈ D. Lúc này, x* ∈ D được gọi là phương án tối ưu toàn cục nếu ∀x∈ D ta luôn có: f(x*) ≤ f(x). Trong trường hợp f(x*) ≤ f(x) chỉ đúng với ∀x ∈ D trong một lân cận của x* thì x* được gọi là phương án tối ưu địa phương. Tối ưu đa mục tiêu 1.
Bài toán tối ưu đa mục tiêu Bài toán tối ưu đa mục tiêu tổng quát có thể xem xét dưới dạng sau : Cực đại hóa các hàm lợi ích : f i x max, i 1, k (1.15) Với xX Rn Nói chung không có lời giải đồng thời đạt cực đại của cả k hàm fi ( i 1, k ). Lời giải của nó được tìm theo nghĩa tối ưu Pareto như sau: Định nghĩa: Điểm x*X gọi là tối ưu Pareto của bài toán đa mục tiêu trên tập X nếu không tồn tại điểm y X sao cho có ít nhất ik mà f i y f i x* (1. Xử lý bài toán đa mục tiêu Bài toán tối ưu đa mục tiêu hiện nay đang được rất nhiều người quan tâm nghiên cứu và có nhiều phương pháp để tìm tập lời giải Pareto. Trong quá trình đó, việc lựa chọn lời giải thường theo hướng “hỗ trợ quyết định” và có thể xử lý được nhờ đưa về các bài toán đơn mục tiêu.
Đưa các mục tiêu thứ yếu vào điều kiện ràng buộc Theo phương pháp này, ta chọn hàm mục tiêu fj mà ta cho là quan trọng nhất và xét bài toán: f j x max (1.17) Với điều kiện f i x ci i 1, k i j (1.18) x X Trong đó các ci thay đổi theo ý muốn của người ra quyết định. Chọn trọng số ưu tiên Ta chọn các trọng số i 0 i 1, k sao cho 1 2 k 1 Độ lớn của i phụ thuộc vào mức độ quan trọng của hàm mục tiêu fi. Với các i i 1, k đã có ta giải bài toán k max i f i x x X (1.19) i 1 Người ta quyết định tùy theo sự thay đổi khi chọn các trọng số i để lựa chọn lời giải. Chọn phương án trong bài toán đơn mục tiêu và bài toán đa mục tiêu Trong bài toán đơn mục tiêu thì các phương án so sánh được với nhau.
Nếu 2 phương án x và y có hai giá trị hàm mục tiêu f(y) ≤ f(x) thì chấp nhận phương án x. Trong bài toán đa mục tiêu một nghiệm x* của bài toán (P1) được gọi là nghiệm lý tưởng nếu: fi(x*) ≤ fi(x) với ∀x X, i={1,. Nói một cách khác một nghiệm lý tưởng là một nghiệm mà nó phải thỏa mãn tất cả các hàm mục tiêu cần tối ưu ứng với miền chấp nhận được là X. Thực tế thì những nghiệm như vậy rất ít khi tồn tại.
Nên ta đưa ra một số khái niệm khác về tối ưu có vẻ “mềm dẻo” hơn đó là nghiệm tối ưu Pareto. 24 - Một điểm x* X được gọi là một nghiệm tối ưu Pareto nếu không tồn tại một nghiệm x ≠ x* X sao cho x trội hơn x*. - Một nghiệm x= (x1, x2, …, xn) được gọi là trội hơn nghiệm y= (y1, y2, …, yn) ký hiệu là: x ≤ y, nếu: 𝑓 (𝑥) ≤ 𝑓𝑖 (𝑦) 𝑖 ∈ {1, … , 𝑘} {𝑖 ∃𝑗 ∈ {1, … , 𝑛}𝑓𝑖 (𝑥) < 𝑓𝑖 (𝑦) - x = (x1, x2, …, xn) được gọi là nghiệm không trội hơn nghiệm y = (y1, y2, …, yn) nếu ∀𝑥 ∈ 𝑋, ∄𝑦 ∈ 𝑋 sao cho: 𝑦 >𝑋 𝑥. Giải thuật di truyền sử dụng để tối ưu hóa đa mục tiêu 1.
Giới thiệu Giải thuật di truyền (GA-Genetic Algorithms) [6] do D. Goldberg đề xuất, sau đó được L. Michalevicz tiếp tục phát triển. GA được hình thành dựa trên quan niệm: quá trình tiến hóa tự nhiên là quá trình hoàn hảo và hợp lý nhất, tự quá trình này đã mang tính tối ưu.
Quan niệm này là một tiên đề đúng, không chứng minh được nhưng phù hợp với thực tế khách quan. GA là giải thuật tìm kiếm, chọn lựa các phương án tối ưu để giải quyết các bài toán thực tế khác nhau, dựa trên cơ chế chọn lọc của tự nhiên: từ tập lời giải ban đầu, thông qua nhiều bước tiến hoá, hình thành tập lời giải mới phù hợp hơn và cuối cùng dẫn đến lời giải tối ưu toàn cục. Các giả thuyết thường được mô tả bằng các chuỗi bit, việc hiểu các chuỗi bit này tùy thuộc vào ứng dụng, ý tưởng các giả thuyết cũng có thể được mô tả bằng các biểu thức kí hiệu hoặc ngay cả các chương trình máy tính. Tìm kiếm giả thuyết thích hợp bắt đầu với một quần thể, hay một tập hợp có chọn lọc ban đầu của các giả thuyết.
Các cá thể của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt động chọn lọc, lai ghép và đột biến ngẫu nhiên – được lấy mẫu sau các quá trình tiến hóa sinh học. GA đã được ứng dụng rộng rãi cho những bài toán cụ thể khác nhau và cho các vấn đề liên quan tới tối ưu hóa.