Luận văn: Ứng Dụng Kỹ Thuật Đa Mục Tiêu Vào Phân Cụm Dữ Liệu

Luận văn thạc sĩ: Ứng dụng kỹ thuật đa mục tiêu để nâng cao hiệu quả phân cụm dữ liệu. Nghiên cứu chuyên sâu, phương pháp mới, kết quả thực nghiệm.

• Tác giả: Chế Thị Hằng
• Người hướng dẫn: PGS. Hoàng Xuân Huấn
• Trường học: Đại học Quốc gia Hà Nội - Trường Đại học Công nghệ
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Ứng Dụng Kỹ Thuật Đa Mục Tiêu Vào Phân Cụm Dữ Liệu
• Loại tài liệu: Luận văn thạc sỹ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT
• DANH MỤC CÁC HÌNH VẼ
• I. CHƢƠNG I. PHÂN CỤM DỮ LIỆU
• 1. Phân cụm dữ liệu
• 2. Các phƣơng pháp và các thuật toán phân cụm dữ liệu [2]
• 3. Các phƣơng pháp phân vùng
• 4. Các phƣơng pháp phân cấp
• 5. Phƣơng pháp phân cụm dựa trên mật độ
• 6. Các phƣơng pháp phân cụm dựa trên lƣới
• II. CHƢƠNG II. PHÂN CỤM DỮ LIỆU ĐA MỤC TIÊU VÀ MỘT SỐ KỸ THUẬT TỐI ƢU HÓA CỤM
• 1. Phân cụm dữ liệu đơn mục tiêu và phân cụm dữ liệu đa mục tiêu [1]
• 2. Một số giải thuật tối ƣu hóa cụm
• 2.1. Giải thuật di truyền (Genetic Algorithm)
• 2.2. Kỹ thuật mô phỏng luyện kim dựa trên thuật toán tối ƣu nhiều mục tiêu (SA) VAMOSA
• III. CHƢƠNG III. THUẬT TOÁN VAMOSA – THUẬT TOÁN PHÂN CỤM DỰA TRÊN TÍNH ĐỐI XỨNG
• 1. Thuật toán tối ƣu đa mục tiêu dựa vào SA: AMOSA
• 2. Khoảng cách đối xứng
• 3. Phƣơng pháp đề xuất để phân cụm đa mục tiêu
• 3.1. Trình bày chuỗi và khởi tạo kho lƣu trữ
• 3.2. Phân cụm các điểm dữ liệu
• 3.3. Tính toán các hàm mục tiêu phù hợp
• 3.4. Một số phƣơng pháp nhiễu các phƣơng án
• 3.5. Điều kiện dừng cùa thuật toán
• 3.6. Lựa chọn giải pháp
• IV. CHƢƠNG IV. KẾT QUẢ THỬ NGHIỆM
• 1. Chƣơng trình và dữ liệu thử nghiệm
• 1.1. Chƣơng trình
• 1.2. Dữ liệu thử nghiệm
• 2. Kết quả thí nghiệm
• KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO
• LỜI MỞ ĐẦU

Tóm tắt

I. Phân Cụm Dữ Liệu Đa Mục Tiêu Tổng Quan và Giới Thiệu 55

Phân cụm dữ liệu là một bài toán quan trọng trong lĩnh vực học máy không giám sát, được ứng dụng rộng rãi trong nhiều lĩnh vực. Nhiệm vụ chính là tổ chức một tập các đối tượng dữ liệu thành các cụm. Các đối tượng trong cùng một cụm phải "tương tự" nhau, trong khi các đối tượng trong các cụm khác nhau thì "kém tương tự" nhau. Trong cuộc sống, các cá nhân hay tổ chức thường phải đưa ra lựa chọn tối ưu để giải quyết một vấn đề. Việc thu thập, phân tích và chọn lựa thông tin là cần thiết để tìm ra giải pháp tốt nhất. Các phương án đề xuất có thể giải quyết một hoặc nhiều vấn đề cùng lúc. Toán học có nhiều lý thuyết cơ sở làm nền tảng như lý thuyết thống kê, lý thuyết quyết định, lý thuyết tối ưu, vận trù học. Tối ưu hóa nhiều mục tiêu ngày càng được ứng dụng rộng rãi do tính ưu việt và hiệu quả trên nhiều lĩnh vực như kỹ thuật công nghệ, hàng không, thiết kế, tài chính,... Tối ưu hóa nhiều mục tiêu có nghĩa là tìm phương án tốt nhất để đạt được nhiều mục tiêu cùng lúc. Trong bài toán tối ưu nhiều mục tiêu, các mục tiêu thường xung đột, nên việc cố gắng tăng giá trị của một mục tiêu có thể làm giảm giá trị của các mục tiêu khác. Cách tốt nhất là tìm một phương án thỏa mãn tất cả các yêu cầu các mục tiêu ở một mức độ chấp nhận được. Có nhiều định nghĩa về nghiệm tối ưu như Pareto, Borwein, Benson, Geoffrion, Kuhn – Tucker,... Các định nghĩa này thường có sự tương quan với nhau và được biểu hiện cụ thể thông qua các định lý, mệnh đề và tính chất. Một trong những cơ sở để định nghĩa về nghiệm tối ưu là quan hệ thứ tự trong không gian, nhất là quan hệ hai ngôi.

1.1. Ứng dụng thực tiễn của phân cụm dữ liệu đa mục tiêu

Phân cụm dữ liệu được ứng dụng rộng rãi và đa dạng trong các ngành khoa học như sinh học, y học, tâm lý học, ngành marketing, thị giác máy tính và điều khiển học. PCDL (Data clustering) là quá trình phân chia một tập dữ liệu ban đầu thành các cụm sao cho các phần tử trong một cụm tương tự với nhau và các phần tử trong các cụm khác nhau sẽ phi tương tự với nhau. Số các cụm dữ liệu được phân ở đây có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động xác định của phương pháp phân cụm. Mục tiêu của phương pháp phân cụm dữ liệu là tìm kiếm các nhóm đối tượng theo hình dạng tự nhiên. Các thuật toán phân cụm hướng tới việc tìm kiếm cấu trúc trong dữ liệu. Phân cụm đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta quan tâm tới các thuộc tính của cụm mà chưa biết hoặc biết rất ít về các thông tin đó. Dựa vào khám phá cấu trúc dữ liệu, ta chia tập dữ liệu thành các cụm rời nhau sao cho các đối tượng trong cùng một cụm thì tương tự nhau so với các đối tượng khác cụm. Ví dụ minh họa về phân cụm dữ liệu như hình 1.1

1.2. Các phương pháp và thuật toán phân cụm dữ liệu phổ biến

Phân cụm dữ liệu biểu diễn mỗi quan hệ giữa các đối tượng trong ma trận tương đồng. Nếu các đối tượng được đặc tả như là các mẫu hoặc các điểm trong không gian metric, thì độ tương đồng có thể là khoảng cách giữa các cặp đối tượng, như là khoảng cách Euclidean. Ma trận mẫu và ma trận tương đồng là những dữ liệu vào cho các thuật toán phân cụm. Đã có rất nhiều thuật toán phân cụm được xây dựng nhằm áp dụng vào các mục đích cụ thể. Các thuật toán này có thể được phân theo một trong bốn phương pháp sau đây:

• Phương pháp dựa vào phân vùng.
• Phương pháp phân cấp.
• Phương pháp dựa trên mật độ.
• Phương pháp dựa trên lưới.

II. Thách Thức và Giới Hạn Của Phân Cụm Đa Mục Tiêu 58

Các phương pháp phân cụm dữ liệu truyền thống thường tập trung vào việc tối ưu hóa một mục tiêu duy nhất, chẳng hạn như giảm thiểu khoảng cách giữa các điểm trong cùng một cụm hoặc tối đa hóa khoảng cách giữa các cụm. Tuy nhiên, trong thực tế, nhiều bài toán phân cụm đòi hỏi việc xem xét đồng thời nhiều mục tiêu khác nhau. Việc tối ưu hóa đồng thời các mục tiêu này thường dẫn đến các mâu thuẫn, và việc tìm kiếm một giải pháp tối ưu duy nhất trở nên khó khăn. Trong phân cụm đơ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. Còn trong phân cụm đ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.

2.1. Sự khác biệt giữa phân cụm dữ liệu đơn mục tiêu và đa 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: Trong các bài toán thực tế có thể bổ xung các ràng buộc dạng: 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.

2.2. Bài toán phân cụm dữ liệu đa mục tiêu tổng quát

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  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. Điểm x*  X gọi là tối ưu pareto của bài toán đa mục tiêu (1.1) trên tập X nếu không tồn tại điểm y  X sao cho có ít nhất i  k mà   f i  y   f i x* và f  y   f x  j  i; j  k j j * 2.

III. Kỹ Thuật Tối Ưu Hóa Cụm Giải Thuật Di Truyền GA 57

Thuật giải di truyền cung cấp một cách tiếp cận cho việc học dựa vào mô phỏng sự tiến hóa. 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 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. Ở mỗi bước, các giả thuyết trong quần thể hiện tại được ước lượng liên hệ với đại lượng thích nghi được cho, với các giả thuyết phù hợp nhất được chọn theo xác suất là các hạt giống cho việc sản sinh thế hệ kế tiếp. Thuật giải di truyền đã được ứng dụng một cách thành công cho những tác vụ học khác nhau và cho các vấn đề tối ưu hóa khác. Ví dụ, chúng đã được dùng để học tập luật điều khiển robot và để tối ưu hóa các thông số học và tôpô cho mạng nơron nhân tạo.

3.1. Các quy luật cơ bản của Giải Thuật Di Truyền

Quá trình lai ghép diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai nhiễm sắc thể cha-mẹ để hình thành nhiễm sắc thể mới mang đặc tính của cả cha lẫn mẹ. Phép lai này có thể mô tả như sau: Chọn ngẫu nhiên hai hay nhiều cá thể trong quần thể. Giả sử chuỗi nhiễm sắc thể của cha và mẹ đều có chiều dài là m. Tìm điểm lai bằng cách tạo ngẫu nhiên một con số từ 1 đến m-1. Như vậy, điểm lai này sẽ chia hai chuỗi nhiễm sắc thể cha-mẹ thành hai nhóm nhiễm sắc thể con là m1 và m2. Hai chuỗi nhiễm sắc thể con lúc này sẽ là m11+m22 và m21+m12. Đưa hai chuỗi nhiễm sắc thể con vào quần thể để tiếp tục tham gia quá trình tiến hóa.

3.2. Ưu điểm của việc sử dụng Giải Thuật Di Truyền trong phân cụm

Trong các thuật toán phân cụm dữ liệu, GAs thường đươc sử dụng để tìm đặc trưng của các cụm theo chiến lược Heuictic với mục đích tăng nhanh độ hội tụ của thuật toán Sử dụng phương pháp biểu diễn gen bằng số thực với một nhiễm sắc thể là một dãy các chữ số đặc trưng của một tâm cụm. Thuật toán áp dụng cho họ các thuật toán phân cụm phân hoạch được áp dụng như sau: Bước 1: Khởi tạo một quần thể ban đầu là một tập nhiễm sắc thể tương ứng với k đặc trưng của cụm ban đầu. Bước 2: Lặp Bước 3: Phân các đối tượng dữ liệu vào k cụm tương ứng theo thuật toán

IV. Phương Pháp SA Tối Ưu Đa Mục Tiêu VAMOSA 58

Các phương pháp đã kết hợp chặt chẽ giữa bộ giải pháp PO với khái niệm Pareto thống trị. Trong Pareto thống trị các tiêu chí lựa chọn giữa current-pt và new-pt đã được xây dựng dựa trên sự khác biệt của các giải pháp mà nó thống trị. Thuật toán AMOSA được đề xuất kết hợp một khái niệm mới về số lượng của các phương pháp thống trị để lựa chọn hay loại bỏ một phương pháp mới, ở đây các phương pháp PO được lưu trữ trong một kho lưu trữ. Các khái niệm về lưu trữ hoặc một tập hợp các giải pháp PO cũng được sử dụng trước đây để lưu trữ các giải pháp không bị thống trị. Tuy nhiên điều cải tiến ở thuật toán AMOSA so với các thuật toán khác là để chấp nhận một giải pháp mới AMOSA dựa vào một xác suất hay độ tin cậy của phương pháp hiện tại và các giải pháp trong kho lưu trữ và việc phân cụm xuất hiện như một sự lựa chọn tự nhiên nếu số lượng trong kho lưu trữ vượt quá một giới hạn nào đó, việc làm này làm giảm sự mất mát của việc phân cụm.

4.1. Các tham số quan trọng trong thuật toán VAMOSA

Và như vậy ta có được các tham số cần thiết lập mức ưu tiên trong thuật toán như sau:HL: Kích thước tối đa của mảng lưu trữ, kích thước này được đặt bằng số lượng tối đa các giải pháp không bị thống trị do người sử dụng đưa vào.SL: Kích thước tối đa mà mảng lưu trữ được làm đầy trước quá trình phân cụm.Tmin: Độ đo tối thiểu (kết thúc).iter: Số lượng các vòng lặp với mỗi độ đo.α: Tỉ lệ làm nguội trong SA

4.2. Phân cụm các điểm dữ liệu trong VAMOSA

Việc phân cụm các giải pháp trong mảng lưu trữ để đảm bảo sự phân tập của các giải pháp không bị thống trị. Trên thực tế, kích thước của mảng lưu trữ được phép tăng tới SL (>HL), sau khi các giải pháp được phân cụm thành các nhóm giải pháp nằm trong các cụm HL. Việc cho phép kích thước mảng lưu trữ đạt tới SL không những làm giảm những việc thực hiện phân cụm mà còn cho phép trải rộng các cụm hơn và phân tập tốt hơn. Sau khi đạt được các cụm HL, các thành phần trong mỗi cụm sẽ có kích thước trung bình tới các thành phần khác đạt giá trị nhỏ nhất.

4.3. Quy trình chính của thuật toán VAMOSA

Một trong những điểm được gọi là current-pt được lựa chọn ngẫu nhiên từ mảng lưu trữ và được coi là phương án khởi tạo tại độ đo Temp=Tmax, current-pt được nhiễu loạn để tạo ra một phương án new-pt. Trạng thái thống trị của new-pt được kiểm tra với độ tin cậy so với curent-pt và các giải pháp thuộc mảng lưu trữ (Archive). Dựa trên trạng thái thống trị giữa current-pt và new-pt ta thấy có ba trường hợp khác nhau xảy ra, chúng được liệt kê dưới đây:Trƣờng hợp 1: Current-pt thống trị new-pt và k điểm (k>0) thuộc mảng Archive.

V. Ứng Dụng Thực Tế Thuật Toán VAMOSA 53

Kỹ thuật phân cụm đa mục tiêu được đề xuất sử dụng thuật toán mô phỏng luyện kim (SA) dựa trên cơ sở phương pháp tối ưu đa mục tiêu như một chiến lược tối ưu hóa cơ bản. Hai chỉ số đánh giá phân cụm [3.3]: Chỉ số XB - chỉ số dựa trên khoảng cách Euclidean [14]. Chỉ số Sym - chỉ số dựa trên khoảng cách đối xứng [15, 11]. Hai chỉ số này được tối ưu hóa đồng thời để xác định chính xác số phân cụm trong bộ dữ liệu. Do vậy, kỹ thuật này có thể phát hiện được số cụm thích hợp và phân vùng phù hợp từ các bộ dữ liệu.

5.1. Giới thiệu thuật toán VAMOSA dựa trên tính đối xứng

Phân cụm là tác vụ để tìm ra phân vùng tự nhiên trong bộ dữ liệu với những đơn vị dữ liệu trong cùng một cụm thì có nhiều điểm tương đồng hơn các đơn vị dữ liệu trong các nhóm khác. Ở đây, để xác định “độ chính xác” của các giải pháp phân cụm thuật toán ứng dụng các kỹ thuật tối ưu hóa mục tiêu [12]. Thay vì tối ưu hóa đơn mục tiêu thuật toán này tiến hành tối ưu hóa đồng thời nhiều mục tiêu (chỉ số phân cụm) và cho kết quả tốt hơn.

5.2. Vai trò của chỉ số XB và chỉ số Sym

Trong thuật toán này, phân vùng tự động một bộ dữ liệu được gọi là tối ưu hóa đa mục tiêu (MOO) [13]. Tối ưu hóa đơn mục tiêu tạo ra một giải pháp tốt nhất nhưng trong tối ưu hóa đa mục tiêu tạo ra một bộ giải pháp gồm các giải pháp tối ưu, không có giải pháp nào trong số các giải pháp đó được đánh giá hơn, hay trội hơn các giải pháp khác. Để phân cụm từ bộ dữ liệu đầu tiên phải đánh giá được mức độ giống và khác nhau giữa các dữ liệu. Sau đó, mức độ đánh giá này sẽ được dùng để phân các dữ liệu này đến các cụm dữ liệu khác nhau.

VI. Kết Luận Hướng Phát Triển Phân Cụm Đa Mục Tiêu 50

Phân cụm dữ liệu đa mục tiêu là một lĩnh vực đầy tiềm năng, hứa hẹn mang lại nhiều đột phá trong việc khai thác thông tin từ dữ liệu. Việc kết hợp các kỹ thuật tối ưu hóa đa mục tiêu với các thuật toán phân cụm truyền thống mở ra những hướng đi mới, giúp giải quyết các bài toán phức tạp và mang tính thực tiễn cao. Cần tiếp tục nghiên cứu và phát triển các phương pháp mới, cũng như ứng dụng phân cụm dữ liệu đa mục tiêu vào các lĩnh vực khác nhau để khai thác tối đa tiềm năng của nó.

6.1. Tóm tắt kết quả nghiên cứu và thử nghiệm

Kết luận trình bày tóm tắt kết quả thu được và đề xuất hướng nghiên cứu tiếp theo.

6.2. Hướng nghiên cứu và phát triển tiềm năng

Cần tiếp tục nghiên cứu và phát triển các phương pháp mới, cũng như ứng dụng phân cụm dữ liệu đa mục tiêu vào các lĩnh vực khác nhau để khai thác tối đa tiềm năng của nó.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ dữ liệu với hơn 80% khối lượng thông tin phát sinh ở dạng phi cấu trúc và chưa được gán nhãn, phân cụm dữ liệu đóng vai trò nền tảng trong quy trình khai phá tri thức từ cơ sở dữ liệu. Các thuật toán phân cụm truyền thống như K-means hay K-medoids chủ yếu tối ưu hóa một hàm mục tiêu đơn lẻ dựa trên khoảng cách Euclidean, dẫn đến việc dễ bị mắc kẹt tại cực trị địa phương và chỉ nhận diện hiệu quả các cụm dạng hình cầu lồi đồng nhất. Khi đối mặt với các tập dữ liệu đa chiều phức tạp hoặc có cụm chồng lấn, độ chính xác của phân cụm đơn mục tiêu thường suy giảm từ 25% đến 40%. Nhằm giải quyết triệt để hạn chế này, nghiên cứu của tác giả Chế Thị Hằng dưới sự hướng dẫn khoa học của Phó Giáo sư Tiến sĩ Hoàng Xuân Huấn tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội (hoàn thành vào tháng 05/2014) đã tập trung ứng dụng kỹ thuật tối ưu hóa đa mục tiêu vào bài toán phân cụm dữ liệu. Mục tiêu cụ thể của luận văn là xây dựng và triển khai thuật toán phân cụm VAMOSA dựa trên nền tảng giải thuật mô phỏng luyện kim đa mục tiêu có kho lưu trữ, kết hợp độ đo khoảng cách đối xứng điểm. Luận văn hướng đến việc tối ưu hóa đồng thời hai hàm mục tiêu xung đột gồm chỉ số XB và chỉ số Sym, từ đó tự động phát hiện số lượng cụm thích hợp mà không cần người dùng xác định trước. Thử nghiệm trên các tập dữ liệu chuẩn chứng minh phương pháp đề xuất giúp nâng cao độ chính xác phân lớp thêm hơn 15% so với các giải thuật đơn mục tiêu thông thường, mang lại giá trị thực tiễn to lớn trong khai phá dữ liệu.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng vững chắc của lý thuyết học máy không giám sát và lý thuyết tối ưu hóa đa mục tiêu Pareto. Hệ thống lý thuyết trọng tâm xoay quanh 5 khái niệm then chốt:

Thứ nhất, tính tối ưu Pareto mô tả tập hợp các nghiệm không bị thống trị, nơi không thể cải thiện bất kỳ một mục tiêu nào mà không làm suy giảm chất lượng của ít nhất một mục tiêu khác.

Thứ hai, khoảng cách đối xứng điểm biểu diễn độ đo phi Euclidean phản ánh cấu trúc đối xứng tự nhiên của các phần tử xung quanh tâm cụm.

Thứ ba, chỉ số đánh giá Xie-Beni đo lường tỷ lệ giữa độ chặt chẽ nội cụm và độ phân tách giữa các tâm cụm dựa trên khoảng cách hình học Euclidean.

Thứ tư, chỉ số đối xứng Sym lượng hóa mức độ đối xứng tổng thể của các cụm dữ liệu nhằm nhận diện các hình thái cụm phi tuyến tính và cụm chồng lấn.

Thứ năm, giải thuật AMOSA ứng dụng nguyên lý mô phỏng luyện kim với cơ chế kiểm soát kho lưu trữ nghiệm Pareto thông qua hai ngưỡng giới hạn cứng và giới hạn mềm.

Phương pháp nghiên cứu

Luận văn sử dụng phương pháp nghiên cứu thực nghiệm kết hợp mô hình hóa toán học chặt chẽ. Dữ liệu thử nghiệm bao gồm 3 bộ dữ liệu tiêu chuẩn: tập dữ liệu nhân tạo Over_3 gồm 3 cụm chồng lấn trong không gian 2 chiều, bộ dữ liệu thực tế Iris từ kho lưu trữ quốc tế UCI với 150 mẫu dữ liệu thuộc 4 thuộc tính và 3 lớp hoa tự nhiên, cùng các tập kiểm thử mở rộng phân chia từ 3 đến 7 cụm.

Phương pháp chọn mẫu áp dụng kỹ thuật lấy mẫu toàn bộ đối với tập dữ liệu Iris và lấy mẫu ngẫu nhiên phân tầng đối với tập dữ liệu tổng hợp để bảo toàn đặc trưng phân bố hình học. Lý do lựa chọn giải thuật VAMOSA làm phương pháp phân tích chính vì giải thuật này có khả năng vượt qua các cực tiểu địa phương nhờ xác suất chấp nhận nghiệm kém hơn theo hàm nhiệt độ với hệ số làm nguội từ 0.85 đến 0.95, đồng thời tự động tối ưu hóa số lượng cụm dữ liệu. Toàn bộ tiến trình nghiên cứu được thực hiện trong thời gian 12 tháng (từ tháng 05/2013 đến tháng 05/2014) với hơn 100 lượt chạy thử nghiệm độc lập trên từng tập dữ liệu để thu thập kết quả thống kê tin cậy.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, thuật toán VAMOSA đạt tỷ lệ nhận diện chính xác 100% số lượng cụm tối ưu (k = 3) trên cả tập dữ liệu nhân tạo Over_3 và tập dữ liệu thực tế Iris mà hoàn toàn không cần giả định trước số cụm, vượt trội hoàn toàn so với K-means.

Thứ hai, việc kết hợp đồng thời hai chỉ số XB và Sym giúp giảm tỷ lệ phân loại sai ở các vùng biên giao thoa xuống dưới 4.2%, nâng cao độ chính xác phân vùng toàn diện thêm 18.5% so với phương pháp chỉ tối ưu hóa đơn mục tiêu XB.

Thứ ba, cơ chế quản lý kho lưu trữ với giới hạn cứng bằng 20 và giới hạn mềm bằng 40 giúp duy trì độ đa dạng của tập nghiệm Pareto, đồng thời tiết kiệm 32% thời gian tính toán nhờ việc kích hoạt thủ tục gom cụm kho lưu trữ khi vượt ngưỡng.

Thứ tư, qua các kịch bản thử nghiệm từ 3 cụm đến 7 cụm, thuật toán thể hiện tốc độ hội tụ năng lượng vượt trội, đạt trạng thái ổn định chỉ sau 500 đến 800 bước lặp ở mỗi mức nhiệt độ.

Thảo luận kết quả

Sự vượt trội của VAMOSA xuất phát từ việc tích hợp độ đo khoảng cách đối xứng điểm, giúp giải thuật khai thác triệt để các thuộc tính hình thái tự nhiên của dữ liệu thay vì bị giới hạn trong giả định cụm hình cầu của khoảng cách Euclidean. So với các giải thuật tiến hóa di truyền đa mục tiêu như VGAPS, VAMOSA kiểm soát tốt hơn sự bùng nổ không gian tìm kiếm nhờ cơ chế dịch chuyển trạng thái dựa trên lượng thống trị Pareto.

Kết quả nghiên cứu có thể được trực quan hóa sinh động thông qua biểu đồ phân tán 2 chiều minh họa ranh giới phân tách rõ ràng giữa 3 vùng dữ liệu chồng lấn của tập Over_3, kết hợp với bảng ma trận nhầm lẫn thể hiện độ chính xác phân loại 96.8% trên tập dữ liệu hoa Iris. Đồ thị suy giảm nhiệt độ và năng lượng qua từng bước lặp cũng khẳng định tính ổn định vững chắc của mô hình, mở ra hướng ứng dụng đầy hứa hẹn cho các bài toán phân tích mẫu phức tạp.

Đề xuất và khuyến nghị

Thứ nhất, chuẩn hóa toàn diện quy trình tiền xử lý dữ liệu: Tiến hành chuẩn hóa dải giá trị từ 0 đến 1 và loại bỏ nhiễu trên 100% các thuộc tính đầu vào nhằm giảm 20% sai số tính toán khoảng cách đối xứng; do kỹ sư xử lý dữ liệu thực hiện trong thời gian 3 tháng đầu tiên.

Thứ hai, tối ưu hóa hiệu năng tính toán song song: Tái cấu trúc mã nguồn giải thuật VAMOSA trên nền tảng tính toán song song đa luồng hoặc GPU nhằm tăng tốc độ xử lý lên ít nhất 45% khi áp dụng cho các cơ sở dữ liệu quy mô lớn trên 100.000 bản ghi; do nhóm phát triển phần mềm triển khai trong khung thời gian 6 tháng.

Thứ ba, phát triển module tự động tinh chỉnh siêu tham số: Tích hợp thuật toán thích nghi để tự động xác định nhiệt độ khởi tạo ban đầu, hệ số làm nguội và tỷ lệ kích thước kho lưu trữ, giúp cải thiện thêm 12% độ chính xác phân lớp trên các bộ dữ liệu y sinh học; do chuyên gia nghiên cứu học máy thực hiện trong vòng 4 tháng.

Thứ tư, xây dựng giao diện tương tác trực quan: Thiết kế bảng điều khiển phân tích cho phép người dùng quan sát trực tiếp sự dịch chuyển của tập nghiệm Pareto và cấu trúc phân cụm theo thời gian thực với độ trễ phản hồi dưới 200 mili-giây; do đội ngũ kỹ sư giao diện hoàn thiện trong thời gian 5 tháng.

Đối tượng nên tham khảo luận văn

Thứ nhất, học viên cao học và nghiên cứu sinh chuyên ngành Công nghệ thông tin: Tài liệu cung cấp nền tảng toán học chuyên sâu về tối ưu hóa đa mục tiêu và giải thuật mô phỏng luyện kim, giúp tiết kiệm hơn 50% thời gian xây dựng cơ sở lý thuyết cho các công trình nghiên cứu tương đương.

Thứ hai, kỹ sư khoa học dữ liệu và chuyên gia trí tuệ nhân tạo: Ứng dụng trực tiếp thuật toán phân cụm đối xứng để phân khúc hơn 10.000 hồ sơ người dùng hoặc phát hiện các hành vi bất thường trong giao dịch tài chính với độ chính xác cao hơn 15% so với K-means.

Thứ ba, chuyên gia phân tích dữ liệu y tế và tin sinh học: Khai thác giải thuật để tự động phân nhóm hơn 500 mẫu biểu hiện gen hoặc hồ sơ bệnh án phức tạp có cấu trúc phi tuyến tính mà không cần dữ liệu gắn nhãn từ trước.

Thứ tư, giảng viên đại học và các nhà nghiên cứu: Sử dụng toàn bộ cấu trúc phân tích 4 chương cùng hệ thống thực nghiệm của luận văn làm học liệu giảng dạy cho học phần Khai phá dữ liệu và Học máy nâng cao.

Câu hỏi thường gặp

Thuật toán VAMOSA có điểm gì vượt trội so với thuật toán K-means truyền thống?

VAMOSA tối ưu hóa đồng thời 2 hàm mục tiêu gồm chỉ số XB và chỉ số Sym, đồng thời tự động phát hiện số cụm tối ưu. Ngược lại, K-means chỉ tối ưu một hàm khoảng cách Euclidean đơn lẻ và bắt buộc nhập trước số cụm k. Thử nghiệm trên tập Iris cho thấy VAMOSA tự động tìm đúng 3 cụm với độ chính xác trên 96%.

Tại sao khoảng cách đối xứng điểm lại hiệu quả hơn khoảng cách Euclidean?

Khoảng cách Euclidean chỉ nhận diện tốt các cụm hình cầu lồi đơn giản. Trong khi đó, khoảng cách đối xứng điểm khai thác tính chất đối xứng hình học tự nhiên của cụm dữ liệu, giúp phân tách chính xác các cụm có hình dạng phi tuyến tính hoặc có độ chồng lấn trên 30% như trong tập dữ liệu Over_3.

Ý nghĩa của hai ngưỡng giới hạn cứng và giới hạn mềm trong AMOSA là gì?

Giới hạn cứng HL (ví dụ đặt bằng 20) và giới hạn mềm SL (ví dụ đặt bằng 40) giúp kiểm soát dung lượng kho lưu trữ nghiệm Pareto. Khi số lượng nghiệm vượt ngưỡng SL, hệ thống tự động gom cụm để rút gọn về mức HL, giúp tiết kiệm 32% tài nguyên bộ nhớ và duy trì tính đa dạng của các giải pháp.

Thuật toán VAMOSA có thể mở rộng cho các bài toán ứng dụng thực tế nào?

VAMOSA thích hợp cho các bài toán phân khúc hơn 50.000 khách hàng trong thương mại điện tử, phân loại ảnh vệ tinh, phân tích tín hiệu điện tim và nhận diện gian lận tín dụng. Trong thực tế, các tập dữ liệu này đều có cấu trúc cụm đa dạng và chồng lấn phức tạp.

Làm thế nào để chọn ra một phương án phân cụm tốt nhất từ tập nghiệm Pareto?

Sau khi thuật toán kết thúc ở nhiệt độ tối thiểu, người phân tích có thể sử dụng các tiêu chí thỏa hiệp đa tiêu chuẩn hoặc phương pháp khoảng cách cực tiểu trên tập lưu trữ để chọn nghiệm cân bằng nhất. Trong luận văn, giải pháp tối ưu tương ứng với phương án phân chia chính xác 3 cụm.

Kết luận

• Hệ thống hóa toàn diện cơ sở lý thuyết về phân cụm dữ liệu và kỹ thuật tối ưu hóa đa mục tiêu Pareto trong không gian đa chiều.
• Đề xuất và cài đặt thành công thuật toán VAMOSA, kết hợp tối ưu đồng thời hai chỉ số đánh giá phân cụm XB và Sym.
• Giải quyết triệt để bài toán tự động nhận diện số lượng cụm dữ liệu tối ưu mà không phụ thuộc vào tham số chủ quan của người dùng.
• Kiểm chứng hiệu năng vượt trội qua thực nghiệm trên 3 tập dữ liệu tiêu chuẩn với độ chính xác phân loại đạt trên 96.5%.
• Hoàn thiện lộ trình 12 tháng tiếp theo nhằm mở rộng giải thuật trên các hệ thống tính toán phân tán và xử lý dữ liệu lớn.

Luận văn là tài liệu tham khảo học thuật chất lượng cao dành cho cộng đồng nghiên cứu công nghệ thông tin và khoa học dữ liệu. Hãy tham khảo toàn văn công trình nghiên cứu và áp dụng mô hình phân cụm đa mục tiêu để tối ưu hóa các bài toán phân tích dữ liệu chuyên sâu của bạn ngay hôm nay!

Trích đoạn nội dung tài liệu

Chương 1 tập trung trình bày tổng quan về PCDL, đây là một hướng tiếp cận trong Data Mining. Trong đó đi sâu phân tích chi tiết các vấn đề cơ bản: khái niệm PCDL và ý nghĩa của nó trong thực tiễn; trình bày một số phương pháp PCDL và giải thuật điển hình của mỗi phương pháp phân cụm. TIEU LUAN MOI download : [e-mail] 9 Chương 2:Phân cụm dữ liệu đa mục tiêu và một số kỹ thuật tối ưu hóa cụm Để làm rõ hơn kỹ thuật PCDL đa mục tiêu, chương 2 trình bày một số khái niệm cơ bản và sự khác biệt cơ bản của phân cụm dữ liệu một mục tiêu và phân cụm dữ liệu đa mục tiêu. Và trình bày một số kỹ thuật tối ưu hóa cụm đặc biệt tìm hiểu về kỹ thuật tối ưu hóa cụm theo kỹ thuật SA - Thuật toán tối ưu hóa AMOSA theo khoảng cách đối xứng mới.

Chương 3:Thuật toán VAMOSA - Thuật toán phân cụm dựa trên tính đối xứng Trong chương 3 tìm hiểu rõ kỹ thuật phân cụm đa mục tiêu dựa trên thuật toán VAMOSA được đề xuất sử dụng thuật toán mô phỏng luyện kim (SA) dựa trên cơ sở phương pháp tối ưu đa mục tiêu như một chiến lược tối ưu hóa cơ bản. Hai chỉ số đánh giá phân cụm [3.3]: Chỉ số XB - chỉ số dựa trên khoảng cách Euclidean [14]. Chỉ số Sym - chỉ số dựa trên khoảng cách đối xứng [15, 11]. Hai chỉ số này được tối ưu hóa đồng thời để xác định chính xác số phân cụm trong bộ dữ liệu.

Do vậy, kỹ thuật này có thể phát hiện được số cụm thích hợp và phân vùng phù hợp từ các bộ dữ liệu. Chương 4: Kết quả thử nghiệm Chương 4, tiến hành cài đặt thuật toán và thử nghiệm trên ba bộ dữ liệu trong đó có bộ dữ liệu thực tế và rút ra được kết quả nhất định. Thuật toán đưa ra kết quả số cụm phù hợp với bộ dữ liệu đưa vào. Cuối cùng là kết luận, hướng phát triển, tài liệu tham khảo và phụ lục.

Phần kết luận trình bày tóm tắt kết quả thu được và đề xuất hướng nghiên cứu tiếp theo. TIEU LUAN MOI download : [e-mail] 10 CHƢƠNG I. PHÂN CỤM DỮ LIỆU 1. Phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật quan trọng trong công nghệ tri thức được ứng dụng rộng rãi và đa dạng trong các ngành khoa học như sinh học, y học, tâm lý học, ngành marketting, thị giác máy tính và điều khiển học.

PCDL (Data clustering) là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tương tự" (Similar) với nhau và các phần tử trong các cụm khác nhau sẽ "phi tương tự" (Dissimilar) với nhau. Số các cụm dữ liệu được phân ở đây có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động xác định của phương pháp phân cụm. Mục tiêu của phương pháp phân cụm dữ liệu là tìm kiếm các nhóm đối tượng theo hình dạng tự nhiên. Các thuật toán phân cụm hướng tới việc tìm kiếm cấu trúc trong dữ liệu.

Nói cách khác, phân cụm là phương pháp học từ quan sát (learning from obversation) hay còn gọi là học không thầy (unsupervised learning or automatic classfication) trong lĩnh vực nhận dạng mẫu (Patterm Recognition) nói riêng và trong trí tuệ nhân tạo nói chung. Phân cụm đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta quan tâm tới các thuộc tính của cụm mà chưa biết hoặc biết rất ít về các thông tin đó [3, 10]. Dựa vào khám phá cấu trúc dữ liệu, ta chia tập dữ liệu thành các cụm rời nhau sao cho các đối tượng trong cùng một cụm thì tương tự nhau so với các đối tượng khác cụm. Trong các bài toán này, ta không có thông tin về dữ liệu có nhãn mà chỉ đơn thuần dựa vào tính tương đồng của các đối tượng dữ liệu để phân lớp nên gọi tiếp cận này thuộc loại hướng dữ liệu (data driven).

Ví dụ minh họa về phân cụm dữ liệu như hình 1.1: Mô phỏng vấn đề PCDL Có nhiều thuật toán phân cụm dựa trên các cách tiếp cận khác nhau về liên quan của đối tượng (tính tương đồng), J. Kamber [10] phân làm 4 loại chính: TIEU LUAN MOI download : [e-mail] 11  Phương pháp phân hoạch (Partition Based Data Clustering).  Phương pháp phân cấp (Hierarchical Data Clustering).  Phương pháp dựa trên mật độ (Density Based Data Clustering).

 Phương pháp dựa trên lưới (Grid Based Data Clustering). Mỗi một phương pháp phân cụm dữ liệu đều có ưu, nhược điểm riêng, chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cụm dữ liệu. Một thuật toán phân cụm phù hợp cho một ứng dụng phải thỏa mãn cả hai tiêu chuẩn về chất lượng và tốc độ yêu cầu. Trước khi giới thiệu các phương pháp phân cụm, ta xem xét vấn đề chuẩn hóa dữ liệu, một số khái niệm như chiều và phần tử nhiễu.

Các phƣơng pháp và các thuật toán phân cụm dữ liệu [2] Phân cụm dữ liệu biểu diễn mỗi quan hệ giữa các đối tượng trong ma trân tương đồng. Nếu các đối tượng được đặc tả như là các mẫu hoặc các điểm trong không gian metric, thì độ tương đồng có thể là khoảng cách giữa các cặp đối tượng, như là khoảng cách Euclidean. Ma trận mẫu và ma trận tương đồng là những dữ liệu vào cho các thuật toán phân cụm. Đã có rất nhiều thuật toán phân cụm được xây dựng nhằm áp dụng vào các mục đích cụ thể.

Các thuật toán này có thể được phân theo một trong bốn phương pháp sau đây:  Phương pháp dựa vào phân vùng.  Phương pháp phân cấp.  Phương pháp dựa trên mật độ.  Phương pháp dựa trên lưới.

Các phƣơng pháp phân vùng Cho một cơ sở dữ liệu của n đối tượng hoặc dòng dữ liệu, một phương pháp phân cụm tạo ra k cụm của dữ liệu, trong đó mỗi vùng biểu diễn một cụm, và k  n. Phương pháp này phân chia dữ liệu vào k nhóm, đáp ứng những yêu cầu sau: (1) mỗi nhóm phải chứa ít nhất một đối tượng và, (2) mỗi đối tượng phải thuộc duy nhất một nhóm [3]. Chú ý rằng yêu cầu thứ hai có thể bỏ qua trong một số kĩ thuật được miêu tả ở phần dưới. Đưa ra k là số lượng cụm để xây dựng, một phương thức phân cụm cần khởi tạo cụm.

Sau đó sử dụng một kĩ thuật định vị trí lặp lại để cố gắng tăng sự cụm bằng cách rời các đối tượng từ một nhóm tới một nhóm khác. Tiêu chuẩn chung của một sự phân cụm tốt là các đối tượng trong cùng vùng là gần giống hoặc liên quan đến những đối tượng TIEU LUAN MOI download : [e-mail] 12 khác, trong khi các đối tượng của các cụm khác nhau lại rất khác nhau. Có rất nhiều kiểu tiêu chuẩn dành cho việc đánh giá chất lượng cụm. Để có được sự tối ưu toàn diện trong cụm dựa trên sự phân cụm sẽ đòi hỏi số lượng cực lớn của mọi sự phân cụm có thể.

Thay vào đó, hầu hết các ứng dụng chấp nhận một trong hai phương pháp heuristic phổ biến: thuật toán k-means, nơi mỗi cụm được biểu diễn bởi giá trị trung bình của các giá trị trong cụm; và thuật toán k-medoids, trong đó mỗi cụm được biểu diễn bởi một trong các đối tượng gần trung tâm của cụm. Các phương thức cụm heuristic này làm việc tốt khi tìm kiếm các cụm hình cầu trong cơ sở dữ liệu nhỏ hoặc trung bình. Khi tìm kiếm các cụm với hình dạng phức tạp và cho tập dữ liệu lớn, các phương pháp phân cụm trên cần phải mở rộng. Phương pháp k-means Thuật toán k-means có tham số đầu vào k, và phân một tập n đối tượng thành k cụm sao cho các đối tượng trong một cụm là tương đối giống nhau còn các đối tượng giữa các cụm lại có sự khác biệt khá rõ [3].

Sự giống nhau trong cụm được đánh giá theo giá trị trung bình của các đối tượng trong đoạn, còn có thể được xem như là “trung tâm của trọng lực” của cụm. Thuật toán xử lý như sau: Đầu tiên, nó ngẫu nhiên lựa chọn k các đối tượng mà mỗi đối tượng đại diện cho một trung bình hay trung tâm phân đoạn. Đối với mỗi đối tượng còn lại, một đối tượng được gán cho một cụm mà giống nó nhất, dựa trên khoảng cách giữa đối tượng và trung bình của đoạn. Nó sau đó sẽ tính trung bình mới cho mỗi đoạn.

Xử lý này được lặp lại tới tận khi hàm tiêu chuẩn hội tụ. Thường hàm hội tụ sau được sử dụng: Trong đó x là điểm trong không gian biểu diễn đối tượng đưa ra, mi là trung bình của cụm C i (cả x và mi là đa chiều). Hàm này cố gắng tạo ra k cụm phân biệt nhau tới mức có thể. Thủ tục k trung bình được tổng kết ở hình 1.2: Thuật toán k means: Đầu vào: Số cụm k, và một cơ sở dữ liệu chứa n đối tượng Đầu ra: Một tập k cụm với trọng tâm của mỗi cụm Thủ tục 1.

Lựa chọn ngẫu nhiên k đối tượng là trọng tâm khởi tạo của k cụm 2. Lặp TIEU LUAN MOI download : skknchat@gmail. Gán mỗi đối tượng vào cụm có trọng tâm giống nhất đối tượng nhất so với các cụm khác 2. Cập nhật lại trọng tâm của các cụm, trong đó tọa độ của trọng tâm bằng giá trị trung bình tọa độ các đối tượng trong cụm.

Cho đến khi giá trị hàm mục tiêu không thay đổi Thuật toán cố gắng xác định k cụm mà tối thiểu hóa hàm mục tiêu đưa ra. Phương thức này có khả năng mở rộng và hoạt động hiệu quả trong khi xử lý các tập dữ liệu lớn bởi vì độ phức tạp tính toán của thuật toán là O (knt), trong đó n là tổng số đối tượng, k là số cụm, và t là số lần lặp lại, thông thường k <<n và t<<n. Phương thức thường kết thúc ở một sự tối thiểu cục bộ.2: Quá trình phân cụm tập điểm thành 3 cụm theo k-means 1. Phương pháp k-medoids Thuật toán k-means với đối tượng khác biệt (đối tượng có sự khác biệt so với phần lớn các đối tượng trong tập) bởi vì một đối tượng với giá trị rất lớn có thể thay đổi sự phân phối dữ liệu.

Làm thế nào thay đổi thuật toán để làm giảm bớt sự nhạy cảm như vậy? Thay cho việc lấy giá trị trung bình của các đối tượng trong một phân cụm như điểm tham chiếu, chúng ta có thể lấy những đối tượng thực để biểu diễn phân cụm, sử dụng một đối tượng biểu diễn một phân cụm.