Luận văn Thạc sĩ Toán học: Tối ưu DC và ứng dụng trong bài toán phân cụm

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:48

Thêm vào BST

Báo xấu

36
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong luận văn này, tìm hiểu phương pháp tối ưu DC và thuật toán DC để giải quyết bài toán phân cụm. Thuật toán được thử nghiệm trên các bộ dữ liệu thu được từ những vấn đề trong thực tế. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Tối ưu DC và ứng dụng trong bài toán phân cụm

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC —————o0o————— VŨ VĂN THỊNH TỐI ƯU DC VÀ ỨNG DỤNG TRONG BÀI TOÁN PHÂN CỤM LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC —————o0o————— VŨ VĂN THỊNH TỐI ƯU DC VÀ ỨNG DỤNG TRONG BÀI TOÁN PHÂN CỤM Chuyên ngành: Toán ứng dụng Mã số: 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. TẠ MINH THỦY Thái Nguyên - 2017
2 Mục lục Danh mục các ký hiệu 4 Mở đầu 5 1 Một số khái niệm cơ bản 7 1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Hàm DC . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.1 Định nghĩa hàm DC . . . . . . . . . . . . . . . . 10 1.3.2 Bài toán quy hoạch DC . . . . . . . . . . . . . . 11 1.3.3 Bài toán DC đối ngẫu . . . . . . . . . . . . . . . 11 1.4 Thuật toán DCA (DC Algorithm) . . . . . . . . . . . . . 13 1.5 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Bài toán phân cụm và một số thuật toán phân cụm dữ liệu 16 2.1 Khái niệm của phân cụm dữ liệu . . . . . . . . . . . . . 16 2.1.1 Phân cụm dữ liệu là gì? . . . . . . . . . . . . . . 16 2.1.2 Ví dụ phân cụm trong thực tế . . . . . . . . . . . 16 2.2 Những vấn đề của phân cụm dữ liệu . . . . . . . . . . . 17 2.2.1 Các bước cơ bản để phân cụm dữ liệu . . . . . . . 17 2.2.2 Các yêu cầu đối với phân cụm . . . . . . . . . . . 19 2.2.3 Những vấn đề của phân cụm dữ liệu . . . . . . . 20 2.2.4 Các ứng dụng của phân cụm . . . . . . . . . . . . 21 2.3 Các kiểu dữ liệu và độ đo trong bài toán phân cụm . . . 22 2.3.1 Các kiểu dữ liệu . . . . . . . . . . . . . . . . . . . 22 2.3.2 Độ đo trong bài toán phân cụm . . . . . . . . . . 22 2.4 Một số kỹ thuật trong phân cụm dữ liệu . . . . . . . . . 23
3 2.4.1 Phân cụm phân hoạch (Partitioning Methods) . . 23 2.4.2 Phân cụm phân cấp (Hierarchical Methods) . . . 24 2.4.3 Phân cụm dựa trên mật độ (Density-Based Meth- ods) . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4.4 Phân cụm dựa trên lưới (Grid-Based Methods) . 25 2.4.5 Phân cụm dựa trên mô hình . . . . . . . . . . . . 26 2.5 Một số thuật toán phân cụm phân hoạch . . . . . . . . . 27 2.5.1 Thuật toán k-Means . . . . . . . . . . . . . . . . 27 2.5.2 Thuật toán phân cụm mờ FCM . . . . . . . . . . 28 2.5.3 Thuật toán phân cụm sử dụng thông tin trọng số (SCAD) . . . . . . . . . . . . . . . . . . . . . . 31 2.6 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3 Phương pháp tối ưu DC cho bài toán phân cụm 37 3.1 Tối ưu DC và thuật toán DCA cho bài toán (2.2) . . . . 37 3.2 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . 41 3.3 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Tài liệu tham khảo 46
4 Danh mục các ký hiệu R Tập hợp số thực Rn Không gian số thực n-chiều X∗ Không gian liên hợp của X x∈C x thuộc tập C x∈/C x không thuộc tập C x := y x được định nghĩa bằng y ∃x Tồn tại x ∀x Với mọi x ∅ Tập hợp rỗng ∩ Phép giao các tập hợp ∪ Phép hợp các tập hợp hx, yi Tích vô hướng của x và y ∇x f (x) Véc tơ đạo hàm của hàm f tại điểm x AT Ma trận chuyển vị của ma trận A A∗ Toán tử liên hợp của toán tử A I Ánh xạ đơn vị kxk Chuẩn của véc tơ x arg min{f (x) : x ∈ C} Tập các điểm cực tiểu của hàm f trên C
5 Mở đầu Lý thuyết tối ưu đã được tìm hiểu và phát triển để giải quyết những vấn đề trong thực tế cuộc sống. Tuy nhiên với những bài toán có hàm mục tiêu không lồi, bài toán trở nên phức tạp hơn, và chính những bài toán thực tế lại thường dẫn đến hàm mục tiêu không lồi. Luận văn này sẽ tìm hiểu về lý thuyết tối ưu DC (hiệu 2 hàm lồi – difference of convex) và thuật toán DC (DCA - DC Algorithm) để giải quyết những vấn đề như vậy. Phân cụm là một trong những bài toán khó và được nghiên cứu nhiều trong lĩnh vực Tin học và Công nghệ thông tin. Bài toán phân cụm là chia dữ liệu thu thập được thành những cụm (nhóm) có cùng tính chất. Đây là bài toán NP – khó và đã được nghiên cứu từ lâu. Trong luận văn này, chúng tôi tìm hiểu phương pháp tối ưu DC và thuật toán DC để giải quyết bài toán phân cụm. Thuật toán được thử nghiệm trên các bộ dữ liệu thu được từ những vấn đề trong thực tế. Luận văn gồm có 3 chương: Chương 1: Giới thiệu các kiến thức cơ bản về giải tích lồi, đặc biệt chú trọng hàm lồi, hàm DC và một số tính chất của hàm DC; những kiến thức này được sử dụng làm nền tảng trong các chương tiếp theo. Chương 2: Giới thiệu về phân cụm dữ liệu và một số vấn đề của phân cụm dữ liệu. Trong chương này, luân văn sẽ trình bày về khái niệm của phân cụm, các yêu cầu và giới thiệu một số kỹ thuật trong phân cụm dữ liệu. Chương này sẽ trình bày cụ thể một số cách tiếp cận theo hướng phân cụm phân hoạch. Chương 3: Từ thuật toán phân cụm với trọng số của thuộc tính (SCAD) đã được trình bày trong chương 2, luận văn sẽ giới thiệu phương pháp tối ưu DC và giải thuật DC cho bài toán tối ưu không
6 lồi đã được trình bày. Chương này cũng trình bày các kết quả thực nghiệm của thuật toán với các bộ dữ liệu thực tế. Do thời gian có hạn nên luận văn này chủ yếu chỉ dừng lại ở việc tập hợp tài liệu, bước đầu tìm hiểu về lý thuyết tối ưu DC cũng như thuật toán DC. Luận văn cũng đưa ra được những kết quả thực nghiệm ban đầu minh họa cho thuật toán. Trong quá trình viết luận văn cũng như trong soạn thảo văn bản, luận văn chắc chắn không khỏi có những sai sót nhất định. Tác giả rất mọng nhận được sụ góp ý của các thầy cô, bạn bè đồng nghiệp để luận văn được hoàn thiện hơn. Nhân dịp này em xin được bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn TS. Tạ Minh Thủy đã tận tình giúp đỡ tác giả trong suốt quá trình làm luận văn. Em cũng xin chân thành cảm ơn các thầy, cô: GS, PGS, TS,... của khoa Toán - Tin trường Đại học Khoa học Thái Nguyên và Viện Toán học đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Thái Nguyên, tháng 4 năm 2017 Tác giả luận văn Vũ Văn Thịnh
7 Chương 1 Một số khái niệm cơ bản 1.1 Tập lồi Định nghĩa 1.1.1 Tập X ⊆ Rn được gọi là tập lồi nếu ∀x, y ∈ X và với mọi số thực λ ∈ [0, 1] thì λx + (1 − λ)y ∈ X. Nghĩa là nếu x, y ∈ X thì đoạn: [x, y] := {z ∈ Rn , z = λx + (1 − λ)y ∈ X, 0 ≤ λ ≤ 1} ⊆ X. Ví dụ: i) Cả không gian Rn và tập ∅ là các tập lồi. ii) Các hình cầu mở hoặc đóng trong Rn tức là các tập: B(x0 , r) = {x ∈ Rn , kx−x0 k < r} và B(x0 , r) = {x ∈ Rn , kx−x0 k ≤ r} là tập lồi. 1.2 Hàm lồi Định nghĩa 1.2.1 Hàm f : X → [−∞, +∞] xác định trên một tập lồi X ⊆ Rn được gọi là hàm lồi trên X nếu với mọi x1 , x2 ∈ X và mọi số thực λ ∈ [0, 1] ta có f [(1 − λ)x1 + λx2 ] ≤ (1 − λ)f (x1 ) + λf (x2 ). Hàm f : X → [−∞, +∞] được gọi là lồi chặt trên tập lồi X nếu với mọi x1 , x2 , x1 6= x2 và λ ∈ (0, 1) ta có f [(1 − λ)x1 + λx2 ] < (1 − λ)f (x1 ) + λf (x2 ).
8 Một hàm lồi chặt là lồi, nhưng điều ngược lại không đúng. Hàm f : X → [−∞, +∞] được gọi là lồi mạnh trên tập lồi X nếu tồn tại một số ρ > 0 sao cho với mọi x1 , x2 ∈ X, x1 6= x2 và λ ∈ (0, 1) ta có f [(1 − λ)x1 + λx2 ] ≤ (1 − λ)f (x1 ) + λf (x2 ) + ρkx1 − x2 k2 . Định nghĩa 1.2.2 Hàm f : X → [−∞, +∞] được gọi là lõm (lõm chặt) trên tập lồi X nếu −f là lồi (lồi chặt) trên X. Hàm f : X → [−∞, +∞] được gọi là tuyến tính afin (hay afin) trên X nếu f nhận giá trị hữu hạn và vừa lồi vừa lõm trên X. Một hàm afin trên Rn có dạng f (x) = ha, xi + α với a ∈ Rn , α ∈ R bởi vì ∀x1 , x2 ∈ Rn và ∀λ ∈ [0, 1], ta có f [(1 − λ)x1 + λx2 ] = (1 − λ)f (x1 ) + λf (x2 ). Tuy nhiên hàm afin không lồi chặt hay lõm chặt. Ví dụ về hàm lồi: p i) Hàm chuẩn Euclid kxk = hx, xi, x ∈ Rn ii) Hàm khoảng cách từ điểm x ∈ Rn tới tập C (C ⊂ Rn là một tập lồi khác rỗng): dC (x) = inf kx − yk. y∈C Định nghĩa 1.2.3 Cho hàm bất kỳ f : X → [−∞, +∞] với X ⊆ Rn , các tập dom f = {x ∈ X : −∞ < f (x) < +∞} , epi f = {(x, α) ∈ X × R : f (x) ≤ α} được gọi lần lượt là miền hữu dụng (hữu hiệu) và tập trên đồ thị của hàm f . Nếu domf 6= ∅ và f (x) > −∞ 6=, ∀x ∈ X thì ta nói hàm f là chính thường. Hàm lồi f : X → [−∞, +∞] có thể được mở rộng thành hàm lồi trên không gian Rn bằng cách đặt f (x) = +∞, ∀x ∈ / dom f . Vì vậy để đơn giản ta thường xét f là hàm lồi trên toàn Rn .
9 Định nghĩa 1.2.4 Một ma trận A được gọi là ma trận xác định dương nếu với vecto x bất kỳ ta có: xT Ax > 0. Ma trận A được gọi là ma trận nửa xác định dương nếu với vecto x bất kỳ ta có: xT Ax ≥ 0. Định nghĩa 1.2.5 Cho x0 ∈ X ⊆ Rn . Hàm chính thường f : X → [−∞, +∞] i) được gọi là nửa liên tục dưới tại x0 nếu lim sup f (y) ≥ f (x0 ). y→x0 ii) nửa liên tục trên tại x0 nếu lim sup f (y) ≤ f (x0 ). y→x0 iii) Hàm f được gọi là liên tục tại điểm x0 nếu nó vừa nửa liên tục trên và nửa liên tục dưới tại x0 . Định lý 1.2.6 i) Một hàm thực một biến ϕ(t) khả vi trong một khoảng mở (a, b) là lồi khi và chỉ khi đạo hàm của nó ϕ0 (t) là một hàm không giảm trên khoảng ấy. ii) Một hàm thực một biến ϕ(t) hai lần khả vi trong một khoảng mở là lồi khi và chỉ khi đạo hàm cấp hai của nó ϕ00 (t) không âm trên toàn bộ khoảng ấy. n Định lý 1.2.7 Cho một tập lồi X ⊂ R và một hàm f : Rn → R khả ∂f ∂f vi trên X. ∇f (x) = (x), ..., (x) là vectơ gradient của hàm ∂x1 ∂xn ∂f f tại điểm x và là các đạo hàm riêng cấp một của f tính theo biến ∂xi xi . Khi đó: i) Hàm f lồi trên X khi và chỉ khi: f (y) ≥ f (x) + h∇f (x), y − xi, ∀x, y ∈ X ii) Nếu f (y) > f (x) + h∇f (x), y − xi với mọi x, y ∈ X và x 6= y thì hàm f lồi chặt trên X. Định lý 1.2.8 Cho một tập lồi mở X ⊂ Rn và một hàm f : Rn → R hai lần khả vi liên tục trên X. Kí hiệu ∇2 f (x) là ma trận các đạo hàm riêng cấp hai (hay hessian) của f tại x.
10 i) Nếu ∇2 f (x) nửa xác định dương với mỗi x ∈ X hoặc nếu ∇2 f (x) có mọi giá trị riêng dương thì hàm f là lồi trên X. ii) Nếu ∇2 f (x) xác định dương với mỗi x ∈ X hoặc nếu ∇2 f (x) có mọi giá trị riêng dương thì hàm f là lồi chặt trên X. iii) Nếu X = Rn và hàm f là lồi trên X thì ∇2 f (x) nửa xác định dương với mọi x ∈ Rn . Hệ quả 1.2.9 (Điều kiện cần cho hàm lồi) Giả sử f : X ⊂ Rn → R 00 là một hàm hai lần khả vi liên tục và fjj (x) là đạo hàm riêng hai lần của f theo cùng biến xj . 00 i) Nếu f (x) lồi thì fjj (x) ≥ 0, j = 1, 2, ..., n với mọi x ∈ X. 00 ii) Nếu f (x) lõm thì fjj (x) ≤ 0, j = 1, 2, ..., n với mọi x ∈ X. iii) Nếu f (x) lồi chặt hay lõm chặt thì các bất đẳng thức trên được thay tương ứng bởi các bất đẳng thức > hay
11 Định lý 1.3.2 Mọi hàm f (x) khả vi cấp hai liên tục (f ∈ C 2 (X)) đều là hàm DC trên tập lồi compac X bất kỳ X ⊂ Rn ). Chứng minh. Xét hàm g(x) = f (x) + ρkxk2 . Nếu chứng minh được rằng có thể chọn ρ đủ lớn để g(x) trở thành hàm lồi thì khi ấy do ρkxk2 là hàm lồi nên f (x) = g(x) − ρkxk2 là hàm DC. Vậy phải chọn ρ sao cho g(x) = f (x) + ρkxk2 là hàm lồi. Theo Định lý 1.2.8 ta phải chọn ρ để cho ∇2 g(x) ≥ 0 với mọi x. Vì g(x) = f (x) + ρkxk2 = f (x) + ρ hx, xi nên ta có: ∇2 g(x) = ∇2 f (x) + ρ. Chứng tỏ u, ∇2 g(x)u = u, ∇2 f (x)u + ρkuk2 . Để ∇2 g(x) ≥ 0 tức là u, ∇2 g(x)u ≥ 0, ∀u hay u, ∇2 f (x)u +ρkuk2 ≥ 0 với mọi u mà kuk = 1. Ta cần chọn ρ sao cho ρ ≥ − u, ∇2 f (x)u với mọi u mà kuk = 1 và mọi x ∈ X, tức là: u, ∇2 f (x)u |x ∈ X, kuk = 1 . ρ ≥ − min Điều này có thể được vì: u, ∇2 f (x)u |x ∈ X, kuk = 1 > −∞ do X compact. − min 1.3.2 Bài toán quy hoạch DC Xét tập X = Rn . Ký hiệu Γ0 (X) là tập tất cả các hàm lồi chính thường, nửa liên tục dưới trên X. Định nghĩa 1.3.3 Bài toán quy hoạch tối ưu DC có dạng như sau: (P ) α = inf{f (x) := g(x) − h(x) : x ∈ X}, (1.2) trong đó g(x) ∈ Γ0 (X), h(x) ∈ Γ0 (X). 1.3.3 Bài toán DC đối ngẫu Cho g ∈ Γ0 (X). Hàm liên hợp của g được kí hiệu và định nghĩa như sau: g ∗ (y) = sup {hx, yi − g(x) : x ∈ X} .
12 Cho x0 ∈ domg và > 0. Ký hiệu ∂ g(x0 ) gọi là - dưới vi phân của g tại x0 được định nghĩa như sau: ∂e g(x0 ) = {y ∈ Y : g(x) ≥ g(x0 ) + hx − x0 , yi − e, ∀x ∈ X} . Mệnh đề 1.3.4 Xét bài toán quy hoạch DC: (P ) α = inf{f (x) = g(x) − h(x) : x ∈ X} trong đó g, f ∈ Γ0 (X). Khi đó α cũng là giá trị tối ưu của bài toán đối ngẫu sau: (D) α = inf{h∗ (y) − g ∗ (y) : y ∈ Y } Chứng minh. Xét bài toán tối ưu DC: (P ) α = inf{f (x) = g(x) − h(x) : x ∈ X} trong đó g, h ∈ Γ0 (x). Ta có α = inf{f (x) = g(x) − h(x) : x ∈ X} = inf{g(x) − sup {hx, yi − h∗ (y) : y ∈ Y } : x ∈ X} = inf {β(y) : y ∈ Y } . với (Py ) = inf{g(x) − (hx, yi − h∗ (y)) : x ∈ X}. Ta có  h∗ (y) − g ∗ (y) nếu y ∈ dom h∗ β(y) = +∞ trong các trường hợp còn lại. Ta phát biểu bài toán đối ngẫu: α = inf{h∗ (y) − g ∗ (y) : y ∈ dom h∗ }. Theo cách xác định β(y) ở trên ta có bài toán đối ngẫu của (P) là (D) α = inf{h∗ (y) − g ∗ (y) : y ∈ Y }. Nhận xét: Do α hữu hạn nên dom g ⊂ dom h và dom h∗ ⊂ dom g. Định lý 1.3.5 Cho P và D lần lượt là các tập nghiệm tương ứng của
13 hai bài toán (P) và (D). Đặt Pl = {x∗ ∈ X : ∂h(x∗ ) ⊂ ∂g(x∗ )} Dl = {y ∗ ∈ Y : ∂g ∗ (y ∗ ) ⊂ ∂h∗ (y ∗ )}. Khi đó i) x ∈ P nếu và chỉ nếu ∂ h(x) ⊂ ∂ g(x), ∀ > 0; ii) y ∈ D nếu và chỉ nếu ∂ g ∗ (y) ⊂ ∂ h∗ (y), ∀ > 0; iii) ∪{∂h(x) : x ∈ P} ⊂ D ⊂ dom h∗ ; iv) ∪{∂g ∗ (y) : y ∈ D} ⊂ P ⊂ dom g Định lý 1.3.6 i) Nếu x∗ là cực tiểu địa phương của g−h thì x∗ ∈ Pl , ii) Cho x∗ là điểm tới hạn của g − h và y ∗ ∈ ∂g(x∗ ) ∩ ∂h(x∗ ). Cho U là một lân cận của x∗ thỏa mãn: U ∩ domg ⊂ dom ∂h. Nếu với mỗi x ∈ U ∩ dom g tồn tại y ∈ ∂h(x) sao cho h∗ (y) − g ∗ (y) ≥ h∗ (y ∗ ) − g ∗ (y ∗ ) thì x∗ là cực tiểu địa phương của g − h nghĩa là: g(x) − h(x) ≥ g ∗ (x) − h∗ (x)), ∀x ∈ U ∩ dom g. Chứng minh các định lý trên, ta có thể xem chi tiết tại các tài liệu [1], [9]. 1.4 Thuật toán DCA (DC Algorithm) Với mỗi x∗ cố định thuộc tập X ⊆ Rn . Ta xét bài toán (S(x∗ )) = inf{h∗ (y) − g ∗ (y) : y ∈ ∂h(x∗ )}. Bài toán trên tương đương với bài toán: inf{hx, y ∗ i − h(x) : x ∈ ∂g ∗ (y ∗ ).
14 Tương tự, với mỗi y ∗ ∈ Y , ta xét bài toán đối ngẫu: (T (y ∗ )) = inf{g(x) − h(x) : x ∈ ∂g ∗ (y ∗ )}. Gọi S(x∗ ), T (y ∗ ) theo thứ tự là tập nghiệm của bài toán (S(x∗ )) và (T (y ∗ )). Phương pháp giải tổng quát được xem như phương pháp xấp xỉ nghiệm của bài toán gốc (P ) và bài toán đối ngẫu (D). Thuật toán DC sẽ xuất phát từ điểm x0 ∈ dom g đã cho, xây dựng hai dãy {xk } và {y k } được xác định bởi: y k ∈ S(xk ); xk+1 ∈ T (y k ). Dạng rút gọn của DCA: Thuật toán DCA rút gọn được xây dựng bởi hai dãy {xk } và {y k } thỏa mãn các điều kiện sau: i) Các dãy (g − h)(xk ) và (h∗ − g ∗ )(y k ) là các dãy giảm. ii) Mỗi điểm giới hạn x∗ (tương ứng y ∗ ) của dãy {xk } (tương ứng {y k }) là điểm dừng của g − h (tương ứng h∗ − g ∗ ). Các điều kiện trên gợi ý xây dựng hai dãy {xk } và {y k }, xuất phát từ điểm x0 ∈ dom g, như sau: y k ∈ ∂h(xk ); xk+1 ∈ ∂g ∗ (y k ). Ở mỗi bước lặp thứ k, ta tính toán: xk ∈ ∂g ∗ (y k−1 ) → y k ∈ ∂h(xk ) = argmin{h∗ (y) − [g ∗ (y k−1 ) + xk , y − y k−1 ]} (Dk ) y k ∈ ∂h(xk ) → xk+1 ∈ ∂g ∗ (y k ) = argmin{g(x) − [h(xk ) + x − xk , y k ]} (Pk ) (Dk ) và (Pk ) là những tập lồi được suy ra từ (D) và (P ). Ta thấy sự đối xứng giữa bài toán (Pk ) và (Dk ), cũng như giữa hai dãy {xk } và {y k } liên quan đến tính đối ngẫu của hàm DC. Thuật toán DCA sẽ được xác định nếu ta có thể xây dựng hai dãy {xk } và {y k } như trên với điểm khởi tạo x0 ∈ dom g. Sự hội tụ của thuật toán DCA hội tụ có thể tham khảo tài liệu [1],[7] và các tài liệu tham chiếu trong đó.
15 1.5 Kết luận Trong chương này, luận văn nhắc lại một số khái niệm của giải tích lồi như tập lồi, hàm lồi, hàm chính thường, ma trận xác định dương, điều kiện cần cho hàm lồi, afin, dưới vi phân, hàm DC và một số tính chất của hàm DC. Luận văn cũng giới thiệu bài toán quy hoạch DC, bài toán DC đối ngẫu và thuật toán DCA. Đây là những kiến thức cơ sở để tìm hiểu bài toán phân cụm ở các chương tiếp theo.
16 Chương 2 Bài toán phân cụm và một số thuật toán phân cụm dữ liệu 2.1 Khái niệm của phân cụm dữ liệu 2.1.1 Phân cụm dữ liệu là gì? Phân cụm dữ liệu là sự phân chia một tập dữ liệu lớn thành các nhóm dữ liệu khác nhau trong đó các đối tượng trong cùng một nhóm sẽ có những tính chất tương tự nhau và có những tính chất không tương tự nhau với những đối tượng ở những nhóm khác. Số các cụm dữ liệu có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động xác định bằng phương pháp phân cụm. Phân cụm dữ liệu nhằm mục đích chính là khai phá cấu trúc của mẫu dữ liệu để thành lập các cụm dữ liệu từ tập dữ liệu lớn, cho phép ta đi sâu vào phân tích và nghiên cứu từng cụm dữ liệu này nhằm tìm kiếm các thông tin tiềm ẩn, hữu ích phục vụ cho việc ra quyết định. Việc phân cụm cũng giúp ta tìm ra các đặc trưng của từng nhóm dữ liệu, giúp giảm kích thước của các tập dữ liệu lớn khi lưu trữ hay dự đoán tính chất khi có một dữ liệu mới đưa vào sẽ thuộc nhóm nào, giúp ta có thể đưa ra những quyết định quan trọng và chính xác. Ví dụ về phân cụm dữ liệu: Tại hình ảnh minh họa 2.1, trên không gian 3 chiều chúng ta có một tập dữ liệu, có thể phân chia thành 3 vùng dữ liệu với 3 màu khác nhau. 2.1.2 Ví dụ phân cụm trong thực tế Phân cụm có ứng dụng trong nhiều lĩnh vực, ví dụ như:
17 Hình 2.1: Phân cụm dữ liệu [11] • Y học: phân loại các loại bệnh; • Khoa học trái đất: phân chia các mảng địa chất khác nhau; • Thương mại: tìm kiếm nhóm các khách hàng quan trọng dựa vào các thuộc tính đặc trưng tương đồng và những đặc tả trong các bản ghi mua bán của cơ sở dữ liệu thu thập được; • Sinh học: phân loại động vật, thực vật qua các chức năng gen tương đồng của chúng; • Thư viện: phân loại nhóm sách có nội dung và ý nghĩa tương đồng nhau để cung cấp cho độc giả, cũng như đặt hàng với nhà cung cấp; • Quy hoạch đô thị: nhận dạng các nhóm nhà theo vị trí địa lí, giá trị,... nhằm cung cấp thông tin cho quy hoạch đô thị; • Trong viễn thông: khám phá các vị trí thuận lợi cho việc xây dựng các cột sóng để phát tín hiệu; • Xác định các cụm ảnh như ảnh của các loài động vật như chim, thú, cá,. . . trong tập cơ sở dữ liệu ảnh về động vật nhằm phục vụ việc tìm kiếm hay phân loại ảnh; • WWW: phân loại tài liệu, tìm kiếm,. . . trên mạng, phân tích dữ liệu từ weblog để khám phá các nhóm, thói quen của người dùng, giúp cho việc khai phá thông tin từ dữ liệu được nhanh chóng và chính xác hơn. 2.2 Những vấn đề của phân cụm dữ liệu 2.2.1 Các bước cơ bản để phân cụm dữ liệu • Chọn lựa đặc trưng: các dữ liệu sau khi được thu thập cần chọn
18 Hình 2.2: Ví dụ phân cụm xác định các cụm ảnh. Hình 2.3: Ví dụ tìm kiếm tài loại.
19 lọc lại một cách cẩn thận, hợp lý để giảm thiểu các dữ liệu nhiễu, giảm thiểu sự dư thừa thông tin giữa các dữ liệu đặc trưng. Bước này còn được gọi là bước tiền xử lý dữ liệu. • Lựa chọn độ đo: phải lựa chọn độ đo gần gũi để thực hiện các thuật toán phân cụm. Độ đo sẽ chỉ ra mức độ tương tự hay không tương tự giữa 2 điểm dữ liệu. Phải đảm bảo rằng các điểm dữ liệu đặc trưng là góp phần như nhau trong việc tính toán với độ đo này và không có dữ liệu đặc trưng nào át hẳn đặc trưng nào. • Tiêu chuẩn phân cụm: để đánh giá việc phân cụm là tốt hay xấu, chúng ta cần xác định trước tiêu chuẩn phân cụm. Tiêu chuẩn phân cụm thường được biểu diễn bởi một hàm tối ưu, hàm chi phí hay một vài loại quy tắc khác. Đôi khi ta có thể kết hợp nhiều tiêu chuẩn để đánh giá độ tốt của kết quả phân cụm. • Thuật toán phân cụm: lựa chọn một thuật toán để làm sáng tỏ cấu trúc cụm của tập dữ liệu. • Đánh giá và giải thích kết quả: Khi đã có kết quả, chúng ta cần kiểm tra tính đúng đắn, đánh giá kết quả. Việc này thường được thực hiện bởi việc dùng các kiểm định, tiêu chuẩn phù hợp. Đôi khi cần phải kết hợp với các bằng chứng thực nghiệm và phân tích để đưa ra các kết luận đúng đắn. Ngoài ra nên đưa ra khuynh hướng phân cụm, thuật toán có thể tốt trong những trường hợp nào, với loại dữ liệu nào,. . . Việc lựa chọn dữ liệu đặc trưng, độ đo, tiêu chuẩn phân cụm khác nhau có thể dẫn tới kết quả phân cụm khác nhau. Do đó việc lựa chọn một cách hợp lý nhất hoàn toàn phụ thuộc vào kinh nghiệm và kiến thức của người dùng. Đôi khi chúng ta phải sử dụng phương pháp thử nghiệm: lặp đi lặp lại nhiều lần thực hiện việc phân cụm với các độ đo, tiêu chuẩn hay thuật toán khác nhau. 2.2.2 Các yêu cầu đối với phân cụm Các thuật toán phân cụm cần đáp ứng được càng nhiều càng tốt các tiêu chí khác nhau, như: • Có khả năng mở rộng với dữ liệu lớn: nhiều dữ liệu, dữ liệu có số chiều lớn. Ngày nay, dữ liệu thu thập được càng ngày càng nhiều;