Quy tắc phân loại Bayes
Quy tắc phân loại Bayes 2 lớp
Đầu tiên chúng ta xét bài toán phân loại 2 lớp (K = 2), trong đó chúng ta mong muốn phân biệt giữa 2 lớp Π1 , Π2.
P (X ∈ Π i ) = π i , i = 1, 2, (1.1) là xác suất tiên nghiệm mà 1 quan sát ngẫu nhiên được lựa chọn X = x thuộc Π1 hoặc Π2 Giả sử, mật độ xác xuất đa biến có điều kiện của
Theo định lý Bayes, chúng ta thu được xác suất hậu nghiệm f i ( x ) π i p(Π |x) = P (X ∈ Π |X = x) = , i = 1, 2 (1.3) i i 1(x)π
Với một giá trị x đã cho, chúng ta có thể phân loại bằng cách gán x vào lớp có xác suất hậu nghiệm cao nhất Quy tắc này được gọi là quy tắc phân loại.
Chương 1 Phân tích phân biệt tuyến tính 8 loại Bayes Hay nói cách khác, chúng ta sẽ gán x vào Π1 nếu p(Π 1 |x)
> 1, (1.4) p(Π2|x) và gán vào Π2 nếu ngược lại Thay (1.3) vào (1.4), chúng ta có quy tắc phân loại
Quy tắc phân loại x ∈ Π khi f 1(x)
}, chúng ta sẽ gán ngẫu nhiên x vào 1 trong hai lớp f 2(x) π 1
Phân tích phân biệt tuyến tính Gauss
Chúng ta sẽ cải thiện quy tắc phân lớp Bayes bằng cách áp dụng giả thiết Fisher, trong đó giả định rằng cả hai mật độ xác suất nhiều chiều đều tuân theo phân phối Gauss với các vectơ trung bình tùy ý.
(a) Trường hợp cú ma trận covariance chung Tức là, f 1(ã) là 1 mật độ
N r (à 1 , Σ1) và f 2(ã) là mật độ N r (à 2 , Σ2), trong đú Σ1 = Σ2 = Σ XX Tỷ số hai mật độ exp {− 1
Quy tắc phân loại x ∈ Π 1 khi L(x) >
Trên biên {x ∈ R r | L(X) = 0}, phương trình trở thành tuyến tính đối với x, xác định một siêu phẳng phân tách hai lớp Quy tắc (1.10) được gọi là phân tích phân biệt tuyến tính Gauss (LDA).
U = b T x = (à 1 − à 2) T Σ −1 x, (1.11) được gọi là hàm phân biệt tuyến tính Fisher(LDF).
Tổng xác suất phân loại sai
LDF chia không gian đặc trưng R thành hai lớp riêng biệt R1 và R2 Nếu một điểm x rơi vào R1, nó sẽ được gán vào Π1; ngược lại, nếu x rơi vào R2, nó sẽ được gán vào Π2 Chúng ta cần chú ý đến xác suất phân loại sai của x, xảy ra khi x được gán vào Π2 nhưng thực tế thuộc về Π1, hoặc ngược lại, x được gán vào Π1 nhưng thực tế lại thuộc về Π2 Khoảng cách Mahalanobis giữa hai lớp Π1 và Π2 được định nghĩa để đo lường sự khác biệt này.
Khi đó tổng xác suất phân loại sai là
Đồ thị P (∆) theo ∆ thể hiện một đường cong giảm dần, với giá trị bằng 1 khi ∆ = 0, tức là khi hai phần tử hoàn toàn giống nhau Khi ∆ tăng, giá trị này giảm dần về 0 Điều này có nghĩa là, khoảng cách giữa hai trung bình của các phần tử càng lớn, khả năng phân loại sai x càng thấp.
2 tham số khác nhau trong à 1
Chúng ta có thể ước lượng các tham số chưa biết của hai lớp Π1 và Π2 từ tập dữ liệu trên X Giả sử có các mẫu độc lập từ hai lớp này, với {X 1j} là mẫu kích thước n1 lấy từ lớp Π1 và {X 2j} là mẫu kích thước n2 lấy từ lớp Π2.
Các kịch bản khác nhau dưới đây là có khả năng khi lấy mẫu từ phần tử của
Lấy mẫu có điều kiện là phương pháp trong đó một mẫu kích thước cố định n = n 1 + n 2 được chọn ngẫu nhiên từ tập hợp P Tại một điểm x cố định, có n 1(x) quan sát từ hai phân phối Π i, với i = 1, 2 Kịch bản này thường được áp dụng trong lĩnh vực sinh trắc nghiệm.
Trong nghiên cứu sự phân biệt, việc lấy mẫu hỗn hợp thường được thực hiện bằng cách chọn ngẫu nhiên một mẫu có kích thước cố định n = n1 + n2 từ tập P, với n1 và n2 cũng được lựa chọn ngẫu nhiên.
3.Lấy mẫu tách, trong đó mẫu kích thước n i cố định được lựa chọn ngẫu nhiên từ Π i , i = 1, 2, và n = n 1 + n 2 Đây là kịch bản phổ biến nhất.
Trong cả 3 kịch bản, các ước lượng hợp lý nhất của b 0 , b có thể thu được
Cỏc ước lượng ML của à i , i = 1, 2 và Σ XX được cho bởi n i ¯ −1 i trong đó S XX = S (1) n i j=1 Σˆ XX = n −1 S XX , (1.19)
Nhận xét 1.1.2 Nếu chúng ta muốn ước lượng không chệch của Σ XX , chúng ta chia S XX trong (1.20) cho bậc tự do của nó n − 2 = n 1 + n 2 −
Nếu π 1 , π 2 chưa biết, chúng ta có thể sử dụng ước lượng πˆ i = n i
Thay thế các ước lượng này vào L(X) trong (1.9) thu được
, (1.25) n lần lượt là ước lượng ML của b, b 0 Quy tắc phân lớp
Quy tắc phân loại x ∈ Π 1 khi L ˆ(x) > 0 x ∈ Π2 ngược lại.
Số hạng ˆ T ¯ ¯ T −1 ước lượng LDF
Trong trường hợp ma trận covariance khác nhau, chúng ta sẽ phân tích sự thay đổi của quy tắc phân lớp (1.10) khi ma trận covariance của hai dữ liệu Gauss không giống nhau Điều này có nghĩa là Σ1 sẽ ảnh hưởng đến cách thức phân loại dữ liệu.
Trong trường hợp này (1.7) trở thành Σ2. log f 1 ( x )= c − {(x − à 1 ) T Σ −1 (x − à ) − (x − à ) T Σ −1 (x − à )} (1.27) f 2(x) 2 1 1 1 2 2 2
= c − x (Σ − Σ )x + (à Σ − à Σ )x, (1.28) trong đú c 0 , c 1 là cỏc hằng số mà chỉ phụ thuộc vào tham số à 1 , à 2 , Σ1 , Σ2.
Tỷ số hợp lý -log (1.28) có dạng 1 hàm bậc 2 của x Trong trường hợp này, lập
Chú ý rằng Ω là 1 ma trận đối xứng Quy tắc phân lớp gán x vào Π1 , nếu Q(x) >
Hàm Q(x) được gọi là hàm phân biệt bậc 2(QDF) và quy tắc phân lớp
(1.33) được gọi là phân tích phân biệt bậc 2 (QDA) Biên {x ∈ R r |Q(x) 0} mà tách 2 lớp là một hàm bậc 2 của x. Ước lượng hợp lý cực đại (ML)
Nếu r + 3 tham số phân biệt trong à 1, à 2, Σ1 và Σ2 chưa được xác định, cùng với π 1, π 2 chưa biết (với 1 tham số điều kiện), chúng có thể được ước lượng bằng cách sử dụng mẫu đã đề cập, ngoại trừ ma trận covariance Cụ thể, ước lượng của Σ i được tính theo công thức n i Σ^ i = n −1 (X ij − X¯ i )(X ij − X¯ i ) T; với i = 1, 2 và j = 1.
Thay thế các ước lượng vào Q(x) trong (1.29), chúng ta có
(1.36) β^ = Σ^ −1 X¯ 1 − Σ^ −1 X¯ 2 (1.37) n 1 β^ 0 = −^c 1 − log e n + log e (1.38) n và c 1 là ước lượng của số hạng đầu tiên trong (1.28).
Quy tắc phân loại Q(x) phụ thuộc vào nghịch đảo của Σ1 và Σ2, cho thấy rằng nếu n1 hoặc n2 nhỏ hơn r, thì Σi (với i = 1 hoặc 2) sẽ suy biến, dẫn đến việc QDA không thành công.
LDA thông qua hồi quy bội
Các kết quả nêu trên có thể đạt được thông qua phương pháp hồi quy bội Cụ thể, chúng ta sẽ tạo ra một biến chỉ số Y để biểu thị các quan sát thuộc về các lớp tương ứng, sau đó thực hiện hồi quy Y dựa trên vectơ đặc trưng X.
. là các nhãn lớp và cho Y = (y 11 y 21 T ) (1.40) là vector hàng (1 × n), các thành phần của nó là các giá trị của Y cho toàn bộ n quan sát Cho
X = (X1.X2) (1.41) là ma trận (r × n), trong đó X1 là ma trận (r × n 1) của các quan sát từ Π1 và
X2 là (r × n 2) - ma trận của các quan sát từ Π2 Cho
Y c = Y − Y¯ = YH n , (1.43) trong đó H n = I n − n −1 J n là ma trận trung tâm và J n = 1 n 1 T là ma trận cỡ n × n của 1.
Nếu chúng ta hồi quy vector hàng Y c trên ma trận X c thì ước lượng OLS của vector hệ số hồi quy bội β được cho bởi βˆ T = Y c X T (X c X T ) −1 (1.44) c c
(X 1 − X 2) (1.53) là thống kờ Hotelling T 2 , mà được sử dụng để kiểm tra giả thuyết à 1 à 2 Giả sử tớnh chuẩn tắc đa biến
F (1.54) r(n − 2) r,n−r−1 khi giả thuyết này là đúng Chú ý rằng D 2 = d T Σ X X −1 d là tỷ lệ thuận với 1 ước lượng của ∆ 2 Từ (1.24) và (1.52), ta có ˆ −1 ¯ ¯ ˆ β ∝ Σ^
XX (X 1 − X 2) = b, (1.55) trong đó, hằng số tỷ lệ làn 1 n 2 (y 1 − y 2 ) n(n 1 + n 2 − 2 + T
Điều này, lần đầu tiên được ghi nhận bởi Fisher(1936) Do đó, chúng ta có thể thu được ước lượng Fisher
LDF (1.24) thông qua hồi quy bội.
Quy tắc phân loại Bayes đa lớp
Chương 1 Phân tích phân biệt tuyến tính 10
Chúng ta giả sử rằng các phần tử sẽ được chia thành K > 2 lớp riêng biệt Ví dụ trong phân loại văn bản, ở mức độ cơ bản, việc lưu trữ và phân loại các file, email và URL là cần thiết Ở mức độ phức tạp hơn, chúng ta cần gán các mục như tin tức, câu hỏi thường gặp về máy tính, an ninh thông tin, xác định tác giả và nhận diện thư rác để thực hiện phân loại hiệu quả.
Chương 1 Phân tích phân biệt tuyến tính 10 là xác suất tiên nghiệm của một quan sát ngẫu nhiên được chọn X mà thuộc vào mỗi lớp khác nhau và cho p(X = x|X ∈ Π i ) = f i (x), i = 1, , K, (1.57) là mật độ xác suất nhiều chiều cho mỗi lớp Kết quả xác suất hậu nghiệm mà 1 quan sát x thuộc lớp thứ i được cho bởi p(Π |x) = p(X ∈ Π |X = x) = Σ f i (x)π i
Quy tắc phân loại Bayes cho K lớp là gán x vào lớp có xác suất hậu nghiệm lớn nhất Do mẫu số của (1.58) là như nhau với mọi Π i , i = 1,
2, , K, nên chúng ta sẽ gán x vào Π i nếu f i (x)π i = max
Nếu cực đại trong (1.59) không xác định duy nhất một lớp mà x được gán vào, chúng ta sẽ áp dụng phép gán ngẫu nhiên để phá vỡ ràng buộc giữa các lớp phù hợp.
X được gán vào Π i nếu f i (x)π i > f j (x)π j với mọi j khác i, hoặc có thể diễn đạt tương đương bằng log e (f i (x)π i ) > log e (f j (x)π j) với mọi j khác i Quy tắc phân loại Bayes có thể được biểu thị qua việc so sánh các xác suất hậu nghiệm Chúng ta định nghĩa "log −odds" để chỉ ra rằng x sẽ được gán vào Π i thay vì Π j.
Do đó, chúng ta gán x vào Π i nếu L ij (x) > 0, ∀j ƒ= i Chúng ta xác định vùng phân lớp R 1 , R 2 , , R K mà
Lập luận này có thể chính xác hơn khi giả định rằng lớp thứ i Π i có mật độ N (à i , Σ i ), trong đó à i là r-vector và Σ i là ma trận covariance (r × r) cho các lớp i = 1, 2, , K Chúng ta cũng giả định rằng ma trận covariance cho K lớp là đồng nhất, tức là Σ1 = ã ã ã = Σ K và bằng ma trận covariance chung Σ XX.
Chương 1 Phân tích phân biệt tuyến tính 12
1 thiết Gauss nhiều biến, log −odds của việc gán x vào Π i (phản đối Π j ) là một hàm tuyến tính của x,
L ij (x) = b 0ij + b T x, (1.62) trong đó b ij = (à i − à j ) T Σ −1 (1.63) b = 1 T
Do L ij (x) là tuyến tính theo x, các R i trong (1.61) chia không gian r- chiều bởi các siêu phẳng. Ước lượng hợp lý cực đại
Thông thường, vector trung bình và ma trận covariance chung sẽ chưa biết. Trong trường hợp đó, chúng ta ước lượng Kr + r(r +
2 tham số phân biệt bằng cách lấy mẫu từ mỗi K lớp Do đó, từ lớp thứ i, chúng ta lấy n i quan sát
X ij , j = 1, 2, , n i trên r- vect-tơ mà sau đó được lập thành ma trận dữ liệu r×n i
Cho K n n i i=1 là tổng số quan sát Do đó, K-ma trận dữ liệu (1.65) là được xếp thành 1 ma trận dữ liệu đơn X có dạng r×n r×n 1
= (X 11 , ã ã ã , X 1,n 1 , ã ã ã , X K1 , ã ã ã , X K,n K ) (1.66) Trung bình của mỗi biến cho lớp thứ i được cho bởi r-vector
= n −1 X ij , i = 1, 2, , K, (1.67) và K vector đó được sắp xếp thành ma trận r× n
X c = X − X = (X1H n 1 ã ã ã X K H n K ), (1.69) trong đó H n j là (n j × n j ) ma trận trung tâm Do đó, chúng ta tính toán
S XX = X c X c Bây giờ, chúng ta xét phân tích i=
X ij − X¯ = (X ij − X¯ i ) + (X¯ i − X¯ ), (1.71) cho quan sát thứ j trong lớp thứ i, trong đó
X ij = (X¯ 1 , , X¯ r ) T (1.72) đại diện cho vector giá trị trung bình, loại bỏ các lớp đồng nhất Bằng cách nhân hai vế của (1.71) với chuyển vị tương ứng và tính tổng trên n quan sát, chúng ta nhận thấy rằng số hạng tích trực giao sẽ biến mất, dẫn đến phân tích nhiều chiều với phương sai đồng nhất (MANOVA).
S tot = S B + S W , (1.73) trong đó S tot , S B và S W được cho bởi bảng trên.
Bảng 1.1: Bảng phân tích ma trận hiệp phương sai đa biến cho K lớp Π1 , Π2 , , Π K , khi có một mẫu ngẫu nhiên của n i quan sát được lấy từ Π i , i = 1, 2, , K.
Source of variation df Sum of Squares Matrix
Do đó, toàn bộ ma trận covariance của các quan sát, S tot có n − 1 bậc tự do và được tính toán bằng cách bỏ đi các lớp đồng nhất, được i= 1 j=
1 phân thành 1 phần ma biểu diễn ma trận covariance giữa các lớp S B, có K − 1 bậc tự do và
Ma trận covariance hợp nhất các lớp, ký hiệu là S W(S XX), có n − K bậc tự do Ước lượng không chệch cho ma trận covariance chung Σ XX của K lớp được xác định bởi công thức Σ XX = (n − K) −1 S W = (n − K) −1 S XX.
Nếu chúng ta định nghĩa f i (x) = f i (x, η i ) với η i là vector tham số chưa biết và {π i } đã biết, thì xác suất hậu nghiệm được ước lượng bởi pˆ(Π |x) = f i (x, ηˆ i )π i cho i = 1, , K Công thức tổng quát là pˆ(Π |x) = ∑_{j=1}^{K} f j (x, ηˆ j )π j Tại đây, ηˆ i là ước lượng của η i Quy tắc phân lớp được áp dụng bằng cách gán x vào Π i nếu f i (x, ηˆ i )π i lớn hơn giá trị tối đa của f j (x, ηˆ j )π j với 1 ≤ j ≤ K Quy tắc này thường được gọi là quy tắc phân loại "plug-in".
Nếu {f i (ã)} là mật độ Gauss nhiều chiều và η i = (à i , Σ XX ) thỡ phiờn bản mẫu của L ij (x) được cho bởi trong đó,
Chúng ta ước lượng tiên nghiệm π i
Quy tắc phân loại chuyển thành bởi ước lượng tỷ lệ π i n i
^ gán x vào Π i nếu L^ ij (x) > 0; j = 1, 2, , K; j ƒ= i (1.80) Nói cách khác, chúng ta gán x vào lớp Π i với giá trị lớn nhất của L^ ij (x).
Khi ma trận covariance không thể giả định là giống nhau, vector trung bình được ước lượng theo công thức (1.67), trong khi ma trận covariance của lớp thứ i, Σ i, được ước lượng bằng phương pháp ước lượng hợp lý cực đại, cụ thể là n i Σ^ i = n −1 (X ij − X¯ i )(X ij − X¯ T) với i = 1, 2, , K.
Như vậy, chúng ta sẽ có Kr + Kr(r +
Hai tham số phân biệt cần được ước lượng, và nếu giá trị r lớn, điều này sẽ mang lại sự gia tăng đáng kể so với việc thực hiện LDA Kết quả phân tích phân biệt bậc 2 (QDA) tương tự như trường hợp 2 lớp khi chúng ta quyết định dựa vào việc so sánh log e f i (x), với i = 1, 2.
Phân biệt Logistic
Trường hợp 2 lớp
Chúng ta thấy rằng từ (1.9) và thực tế rằng p(Π2|x) = 1−p(Π1|x) tại
X = x, mà mật độ xác suất hậu nghiệm thỏa mãn logit p(Π
Mô hình p(Π1|x) được xây dựng dựa trên hồi quy logistic, cho phép phân biệt giả thuyết rằng tỷ lệ hợp lý - log (1.9) có thể được biểu diễn dưới dạng một hàm tuyến tính của x Theo công thức (1.82), ta có thể diễn đạt p(Π1|x) và p(Π2|x) như sau: \[ p(Π1|x) = \frac{e^{L(x)}}{1 + e^{L(x)}} \]và \[ p(Π2|x) = \frac{1}{1 + e^{L(x)}} \]
Chúng ta có thể viết (1.83) là p(Π1|x) = 1
1 + e −u là một hàm sigmoid, lấy giá trị u ∈ R trên (0; 1). Ước lượng hợp lý cực đại Σ j= 1 i i
Bây giờ chúng ta viết p(Π1|x) là p 1(x, β 0 , β) và tương tự với p 2(x, β 0 , β).
Để ước lượng β 0 và vector hệ số β, chúng ta sẽ sử dụng phương pháp trực tiếp thông qua công thức (1.82) Đầu tiên, chúng ta cần thực hiện ước lượng cho các giá trị đầu tiên và Σ XX như đã trình bày trong (1.20) và (1.21) Chúng ta định nghĩa biến đáp ứng để tiến hành các bước ước lượng này.
Các giá trị của Y là các nhãn lớp Điều kiện trên X, biến ngẫu nhiên
Trong mô hình dữ liệu nhị phân, xác suất P(Y = 1) được biểu diễn bằng π1, trong khi P(Y = 0) là 1 - π1, tương đương với π2 Phương pháp phổ biến để phân tích dữ liệu nhị phân này là sử dụng hồi quy logistic.
Cho trước n quan sát, (X i , Y i ), i = 1, 2, , n trên (X, Y ), điều kiện hợp lý cho (β 0 , β) có thể được viết là n
L(β 0 , β) = (p 1(x i , β 0 , β)) y i (1 − p 1(x i , β 0 , β)) 1−y i , (1.88) i=1 khi đó điều kiện hợp lý -log là n
Các ước lượng hợp lý cực đại, β 0 và β, được xác định bằng cách cực đại hóa hàm log-likelihood ℓ(β 0 , β) theo các tham số này Thuật toán cực đại hóa được chuyển đổi thành một phiên bản lặp của quy trình bình phương tối thiểu có trọng số, trong đó trọng số và phản ứng được cập nhật tại mỗi bước Chi tiết về thuật toán lặp bình phương tối thiểu đánh lại trọng số sẽ được trình bày trong phần tiếp theo Các ước lượng hợp lý cực đại β 0 và β có thể được sử dụng trong công thức (1.85) để đưa ra một ước lượng khác cho LDF.
˜ ˜Σ ˜ được gọi là phân tích phân biệt logistic.
Chúng ta chú ý rằng cực đại (1.90) nói chung sẽ không thu được cùng ước lượng cho β 0 , β như chúng ta tìm được trong (1.24) và (1.25) cho
Fisher LDF. lượng xác suất p(Π1|x) trong (1.83) Thay thế lượng
1 + e L ˜ (x) , (1.92) vì vậy x được gán vào Π1 nếu p(Π1|x) là lớn hơn giá trị cắt nào đó, giả sử 0.5 và x được gán vào Π2 nếu ngược lại.
Thuật toán bình phương tối thiểu đánh lại trọng số lặp được định nghĩa lại với r-vector x i và β như (r + 1)-vector: x i ←− (1, x T ) T và β ←− (β 0 , β T ) T Do đó, biểu thức β 0 + β T x i có thể được viết gọn là β T x i Chúng ta ký hiệu p 1(x i , β 0 , β) là p 1(x i , β) và ℓ(β 0 , β) là ℓ(β) Đạo hàm của ℓ(β) được tính và khi đạo hàm bằng 0, ta thu được phương trình điểm ã(β) = ∂ℓ (β).
{y − p (x , β)} = 0 (1.93) Đây là r + 1 phương trình không tuyến tính trong r + 1 tham số logistic β.
Từ (1.93), chúng ta thấy rằng n 1 = Σ n p 1(x i , β) và do đó, chúng ta cũng có n 2 = Σ n p 2(x i , β).
Các phương trình (1.93) được giải quyết thông qua thuật toán bình phương tối thiểu đánh lại trọng số lặp (IRLS), với đạo hàm cấp 2 của ℓ(β) được biểu diễn bởi ma trận Hessian kích thước (r + 1) × (r + 1).
Thuật toán IRLS được dựa trên việc sử dụng tiếp cận lặp Newton-Raphson để tìm ước lượng ML.
Một quy trình phân lớp tương đương là để sử dụng L˜(x) trong (1.91) để ước ˜ ˜ i n
Thuật toán bắt đầu với β 0 = 0 Sau đó, bước thứ k + 1 trong thuật toán ˜ (k+1) ˜ (k
(β) ℓ (β) , (1.95) thay thế lặp thứ k β˜ (k) bởi β β trong đó các đạo hàm được tính tại β (k) Sử dụng ký hiệu ma trận, chúng ta lập
X = (X 1 , , X n ) và Y = (Y 1 , , Y n ) là ma trận dữ liệu có kích thước ((r + 1) × n) và n-vector W được định nghĩa là ma trận trọng số đường chéo (n × n) với các phần tử trên đường chéo được tính theo công thức w i = p 1(x i , β)(1 − p 1(x i , β)) cho i = 1, 2, , n Các đạo hàm cấp 1 của (1.93) và ma trận Hessian (1.94) có thể được diễn đạt lại một cách tương ứng.
Do đó, (1.95) có thể được viết là
), ãã(β) = −X WX T , (1.96) trong đó, β (k+1) = β (k) + (X WX T ) −1 X (y − p 1)
= (X WX T ) −1 X Wz (1.97) z = X T β˜ (k) + W −1 (y − p 1), (1.98) là một n- vector Phần tử thứ i của z được cho bởi z i = x T β˜ (k) + y i − p 1(x i , β (k) ) p 1(x i , β˜ (k) )(1 − p 1(x i , β˜ (k) ))
Cập nhật (1.97) thể hiện một ước lượng bình phương tối thiểu tổng quát, trong đó W là ma trận đường chéo của các trọng số, z là vector phản ứng và X là ma trận dữ liệu Lưu ý rằng p 1 = p (k), z = z (k) và W = W (k) được cập nhật tại mỗi bước của thuật toán, phụ thuộc vào β (k) Hơn nữa, công thức cập nhật (1.97) giả định rằng ma trận X WX T có thể lấy nghịch đảo, điều này sẽ không được đảm bảo khi n < r + 1.
1 ˜ rằng sự hội tụ của thuật toán IRLS tới cực đại của ℓ(β) không thể được đảm bảo, nhưng thuật toán hội tụ tới hầu hết các trường hợp.
Nhận xét 1.2.1 Phân tích phân biệt Gauss hay Phân biệt logistic
So sánh lý thuyết và thực tiễn giữa 2 loại phân biệt chúng ta rút ra một vài khác biệt dưới đây
1 Điều kiện hợp lý -log (1.90) là có hiệu lực dưới các giả thiết của họ hàm mũ trờn f (ã) (bao gồm mụ hỡnh Gauss đa biến với cựng ma trận covariance) Điều này cho thấy rằng phân biệt logistic là tốt hơn phân tích phân biệt Gauss khi không có giả thiết chuẩn.
2 Các nghiên cứu mô phỏng đã chỉ ra rằng khi giả thiết về phân phối Gauss hoặc giả thiết cùng ma trận covariance không được thỏa mãn thì phân biệt logistic thực hiện tốt hơn.
3 Phân tích phân biệt logistic là tiệm cận ít hiệu quả hơn phân tích phân biệt Gauss bởi vì Gauss LDA được dựa trên đầy đủ ML hơn là điều kiện ML.
4 Tại điểm mà chúng ta kỳ vọng phân biệt tốt sẽ diễn ra, phân biệt logistic đòi hỏi một kích thước mẫu lớn hơn Gauss LDA để đạt được cùng phân phối tỷ lệ sai số (Efron, 1975) và kết quả này mở rộng tới LDA bằng cách sử dụng 1 họ hàm mũ với ước lượng plug- in.
Trường hợp đa lớp
Phương pháp phân biệt logistic mở rộng cho trường hợp đa lớp (> 2) Đặt u i = log e {f i (x)π i }, chúng ta có thể biểu diễn (1.58) dưới dạng e u i p(Π i |x) = K k= 1 e u k
Trong ngôn ngữ thống kê, mô hình logistic bội được biểu thị bằng công thức (1.100), trong khi trong ngôn ngữ mạng neural, nó được gọi là hàm kích hoạt softmax Công thức σ i có thể được viết dưới dạng 1 + e −ω i, như thể hiện trong (1.101).
1 trong đó, ω i = u i log e u k nên σ i là 1 tổng quát của hàm kích hoạt sigmoid kƒ=i logistic.
Giả sử chúng ta thiết kế lớp cuối cùng (Π K ) như một lớp tham khảo với giả thiết phân phối Gauss và ma trận covariance chung Trong trường hợp này, chúng ta sẽ định nghĩa các tham số liên quan để đảm bảo tính chính xác và hiệu quả của mô hình.
Nếu chúng ta chia cả tử và mẫu của (1.100) cho e u K và sử dụng (1.102) thì xác suất tiên nghiệm có thể được viết là e L i (x) p(Π i |x) 1 + Σ K−1 e L (x) , i = 1, 2, , K − 1, (1.105) k=11 p(Π K x) = K−1 k
Khi viết f i (x) = f i (x, η k=1 i ), với η i là một vector chứa các tham số chưa biết, chúng ta sẽ ước lượng η i từ η i và f i (x) từ f i (x) = f i (x, η i ) Quy tắc phân lớp được thực hiện bằng cách gán x vào lớp có giá trị cực đại f (x, η ), với i = 1, 2, , K Quy tắc này được gọi là quy tắc phân biệt logistic bội.
Chương 1 Phân tích phân biệt tuyến tính 20 i
Support vector machine tuyến tính
Trường hợp tách tuyến tính
Đầu tiên, xét trường hợp đơn giản nhất: Giả sử các điểm dữ liệu dương (y i = +1) và âm (y i = −1) từ tập dữ liệu L có thể được tách bởi một siêu phẳng
Trong không gian Euclid, β là vector hệ số với chuẩn Euclid ǁβǁ, trong đó β 0 đại diện cho độ chệch, và b - β 0 là ngưỡng Siêu phẳng được gọi là siêu phẳng tách khi nó có khả năng phân chia tập dữ liệu thành hai lớp mà không gặp lỗi Điều này dẫn đến việc tồn tại vô số siêu phẳng tách, và câu hỏi quan trọng đặt ra là làm thế nào để xác định siêu phẳng tách tốt nhất.
Xét siêu phẳng tách, ta định nghĩa d− là khoảng cách ngắn nhất từ siêu phẳng đến điểm dữ liệu âm gần nhất và d+ là khoảng cách ngắn nhất đến điểm dữ liệu dương gần nhất Biên của siêu phẳng tách được xác định bởi công thức d = d− + d+ Khi khoảng cách giữa siêu phẳng và các quan sát gần nhất đạt giá trị tối đa, siêu phẳng này sẽ là tách tối ưu.
Nếu dữ liệu đầu vào từ 2 lớp là phân chia tuyến tính thì tồn tại β 0 và β thỏa mãn β 0 + x T β ≥ 1, nếu y i = +1 (2.4) β 0 + x T β ≤ −1, nếu y i = −1 (2.5)
Nếu một vector dữ liệu thuộc tập L thỏa mãn đẳng thức (2.4), thì nó nằm trên siêu phẳng H+ : (β 0 − 1) + x T β = 0 Tương tự, nếu vector dữ liệu trong L thỏa mãn đẳng thức (2.5), thì nó nằm trên siêu phẳng H− : (β 0 + 1) + x T β = 0 Các điểm trên L nằm trên H−1 hoặc H+1 được gọi là các support vector.
Gọi x−1 , x+1 lần lượt là điểm nằm trên siêu phẳng H−1 và H+1 thì β 0 + x T β = −1; β 0 + x T β = +1 (2.6)
Khoảng cách vuông góc từ điểm x−1; x+1 tới siêu phẳng β 0 + x T β = 0 lần lượt là |β0 + xT β| 1 |β0 + xT β| 1 d − = −1 ǁβǁ ǁβǁ; d + = +1 ǁβǁ ǁβǁ (2.7) i i
Do đó, biên của siêu phẳng tách là d = 2 ǁβǁ Bất đẳng thức (2.4) và (2.5) được viết lại dưới dạng y i (β 0 + x T β) ≥ +1; i = 1, 2, , n (2.8)
Hình 2.1 minh họa về máy vector hỗ trợ (SVM) trong trường hợp tách tuyến tính, với các điểm dữ liệu đỏ tương ứng với y = −1 và điểm xanh với y = +1 Siêu phẳng tách được biểu diễn bằng phương trình β 0 + x T β = 0, trong đó các vector hỗ trợ là những điểm dữ liệu nằm trên siêu phẳng H −1 và H +1 Biên của siêu phẳng được tính bằng d = 2 ǁβǁ Theo định nghĩa 2.1.2, đại lượng y i (β 0 + x T β) được gọi là biên của (x i , y i ) đối với siêu phẳng (2.3) cho i = 1, 2, , n.
Như vậy chúng ta thấy rằng x i là một support vector nếu biên của nó bằng 1.
Bài toán đặt ra là tìm siêu phẳng tách tối ưu, cụ thể là xác định siêu phẳng mà cực đại hóa biên 2 ǁβǁ, với các điều kiện đã cho Điều này tương đương với việc tìm β 0 và β sao cho thỏa mãn điều kiện cực tiểu 1 ǁβǁ 2, cùng với điều kiện y i (β 0 + x T β) ≥ 1 cho tất cả i = 1, 2, , n.
Chúng ta sẽ giải quyết bài toán này bằng cách sử dụng nhân tử Lagrange. Xét hàm gốc
Để tối thiểu hóa hàm F theo các biến gốc β₀ và β, chúng ta cần tối đa hóa kết quả của hàm F theo các biến đối ngẫu α, trong đó α = (α₁, , αₙ)ᵀ ≥ 0 là n vector không âm các hệ số Lagrange Điều kiện cần và đủ cho lời giải của bài toán tối ưu có điều kiện được đưa ra bởi Karush-Kuhn-Tucker Trong bài toán gốc, các biến β₀, β và α phải thỏa mãn n điều kiện nhất định.
= 0, (2.14) y i (β 0 + x T β) − 1 ≥ 0, (2.15) α i ≥ 0, (2.16) α i {y i (β 0 + x T β) − 1} = 0, (2.17) với i = 1, 2, , n Điều kiện (2.17) được gọi là điều kiện bổ sung Karush- Kuhn- Tucker.
Giải phương trình (2.13) và (2.14) thu được n α i y i = 0, (2.18) i=1 n β ∗ = α i y i x i (2.19) i=1
Thay (2.18) và (2.19) vào (2.11) chúng ta thu được giá trị cực tiểu của F P (β 0 , β, α), cụ thể là
Hàm đối ngẫu của bài toán tối ưu được biểu thị qua công thức (2.20) Để tìm các nhân tử Lagrange, chúng ta cần cực đại hóa hàm đối ngẫu này với các ràng buộc (2.16) và (2.18) Bài toán cực đại có ràng buộc, hay còn gọi là đối ngẫu Wolfe, có thể được diễn đạt dưới dạng ma trận như sau.
Bài toán Tìm α để cực đại F (α) = 1 T α − 1α T Hα (2.21)
D n 2 với ràng buộc α > 0; α T y = 0, (2.22) trong đó y = (y 1 , , y n ) T và H = (H ij ) là ma trận vuông cấp n với H ij y i y j (x T x j ).
Nếu α là lời giải của bài toán thì β^ Σ i
=1 α y x (2.23) thu được vector hệ số tối ưu Nếu α > 0 thì từ (2.17) chúng ta có y (β ∗ +
^ i i 0 với mọi quan sát mà không là support vector thì α i = 0.
Cho sv ⊂ {1, 2, , n} là tập con của các chỉ số mà đồng nhất các vector support, cùng với các nhân tử Lagrange khác 0 Tối ưu hóa β được xác định bởi công thức (2.23), trong đó tổng chỉ được thực hiện trên các vector support Cụ thể, β được tính bằng công thức β = α i y i x i, với i thuộc sv.
Hàm β là một hàm tuyến tính phụ thuộc vào các vector support {x i ; i ∈ sv}, cho thấy rằng các vector support chứa toàn bộ thông tin cần thiết để xác định siêu phẳng tối ưu.
^ i i i x T β ∗ ) = 1, và do đó x i là 1 support vector Từ đây, chúng ta thấy rằng, ứng i ^
Độ chệch tối ưu β 0 không được xác định rõ ràng từ lời giải tối ưu, nhưng có thể ước lượng bằng cách giải phương trình (2.17) với từng vector support và tính trung bình các kết quả Do đó, ước lượng độ chệch của siêu phẳng tối ưu là β^ 0 = 1.
T i ) (2.25) y i trong đó |sv| là số vector support trong L.
Theo đó, siêu phẳng tối ưu có thể được viết f^(x) = β^ 0 + x T β^ i∈sv
Quy tắc phân lớp được cho bởi
Nếu j ∈ sv thì từ (2.26) ta có y j f^(x j ) = y j β^ 0 + Σ α^ i y i y j (x T x i ) = 1 (2.28) i∈sv
Do đó, chuẩn bình phương của vector trọng số β^ của siêu phẳng tối ưu là ǁβ^ǁ 2 = Σ Σ α^ i α^ j y i y j (x T x j ) i∈sv j∈sv
Vậy, siêu phẳng tối ưu có biên cực đại
Ví dụ 2.1.1 Tìm siêu phẳng tách tối ưu tập dữ liệu
Lời giải Xét hàm gốc
Mặt khác, chúng ta lại có α 1[(1; 1)β + b − 1] = 0, α 2[(2; 3)β + b − 1] = 0, α 3[(3; 1)β + b + 1] = 0.
Theo (1) ta sẽ có hệ
Kết hợp với (2) chúng ta có hệ 4 phương trình
Giải hệ, chúng ta thu được
Do đó, chúng ta có phương trình
Trường hợp không tách tuyến tính
Trong thực tế, không thể xác định một ranh giới tuyến tính rõ ràng giữa các dữ liệu từ hai lớp, vì có khả năng xảy ra sự chồng chéo Điều này có nghĩa là một số dữ liệu trong lớp này có thể xâm nhập vào không gian của lớp kia và ngược lại Sự chồng chéo này sẽ gây khó khăn cho bất kỳ quy tắc phân loại nào, và mức độ phức tạp sẽ phụ thuộc vào mức độ chồng chéo giữa các lớp dữ liệu.
Trường hợp không tách xảy ra khi cả hai lớp dữ liệu có thể tách được nhưng không tuyến tính, hoặc khi không tồn tại một ranh giới tách rõ ràng giữa chúng Một nguyên nhân chính gây ra hiện tượng chồng chéo này là do mức độ ồn cao trong một hoặc cả hai lớp dữ liệu Hệ quả là sẽ có một hoặc nhiều ràng buộc bị vi phạm Để khắc phục vấn đề này, chúng ta sẽ áp dụng một công thức linh hoạt hơn, gọi là lời giải soft margin, bằng cách sử dụng biến bù không âm ξ i cho mỗi quan sát (x i , y i ) trong tập dữ liệu L, với i = 1, 2, , n.
Ràng buộc (2.10) được điều chỉnh thành y i (β 0 + x T β) + ξ i ≥ 1 cho mọi i = 1, 2, , n, trong đó các điểm dữ liệu tuân thủ ràng buộc có ξ i = 0 Quy tắc phân lớp hiện cần xác định siêu phẳng tối ưu, nhằm kiểm soát cả hai biên và 2 ǁβǁ.
Hàm tính toán các biến bù đơn giản hơn với n biến, trong đó n là số lượng biến và σ có thể là 1 (1-norm) hoặc 2 (2-norm) Ở đây, chúng ta sẽ xem xét trường hợp σ = 1 với các ràng buộc chắc chắn.
Hình 2.3 minh họa cho máy vector hỗ trợ (SVM) trong trường hợp không tách tuyến tính, với các điểm dữ liệu màu đỏ đại diện cho y = −1 và các điểm xanh cho y = +1 Siêu phẳng tách được xác định bởi phương trình β 0 + x T β = 0.
Các vector support là các điểm dữ liệu nằm trên siêu phẳng H −1 và H +1, trong đó biến bù ξ 1 tương ứng với điểm xanh vi phạm giới hạn H +1 và ξ 2 tương ứng với điểm đỏ vi phạm giới hạn H −1 Các điểm thỏa mãn giới hạn của siêu phẳng có ξ i = 0.
Bài toán Bài toán tối ưu 1-norm soft-margin là tìm β 0 , β và ξ để n cực tiểu β 2 + C ξ, (2.33)
Trong bài toán tối ưu hóa, có ràng buộc ξ i ≥ 0 và y i (β 0 + x β) ≥ 1 − ξ T i cho i = 1, 2, , n, với C > 0 là tham số quy chuẩn Tham số C đóng vai trò như một hằng số điều chỉnh, giúp kiểm soát kích thước của các biến bù và cân bằng hai số hạng trong hàm cực tiểu.
Chúng ta có dạng hàm gốc, F P = F P (β 0 , β, ξ, α, η), trong đó
(2.35) với α = (α 1 , , α n ) T ≥ 0 và η = (η 1 , , η n ) T ≥ 0 Cố định α và η, đạo hàm F P theo β 0 , β và ξ, chúng ta có
Cho các đạo hàm bằng 0, chúng ta thu được n n Σ α i y i = 0; β ∗ = Σ α i y i x i ; α i = C − η i (2.39)
Thay (2.36) và (2.32), chúng ta có hàm đối ngẫu n n n
Từ ràng buộc C − α i − η i = 0 và η i ≥ 0, chúng ta có 0 ≤ α i ≤ C Ngoài ra, chúng ta có điều kiện Karush- Kuhn- Tucker: Σ1 ǁ ǁ
Chương 2 Support Vector Machine 30 i α i {y i (β 0 + x T β) với i = 1, 2, , n Từ (2.46), chúng ta thấy rằng một biến bù ξ i có thể khác 0 chỉ khi α i = C Các điều kiện bổ sung (2.45) và (2.46) có thể được sử dụng để tìm độ chệch tối ưu β 0.
Bài toán cực đại đối ngẫu có thể viết lại dưới dạng ma trận như sau Tìm α để cực đại F (α) = 1 T α − 1α T Hα (2.47)
Sự khác biệt giữa bài toán tối ưu này và trường hợp tách tuyến tính
Trong các hệ số Lagrange α i (i = 1, 2, , n), có một giới hạn trên bởi C, điều này hạn chế ảnh hưởng của từng quan sát trong việc xác định giải pháp Ràng buộc này được gọi là ràng buộc hộp, do α bị giới hạn trong một hộp có cạnh C trong góc phần tư dương Theo (2.48), giới hạn khả thi cho bài toán tối ưu lồi là giao của siêu phẳng α T y = 0 với hộp ràng buộc 0 ≤ α ≤ C1 n.
Nếu C = ∞ thì bài toán đưa tới trường hợp tách hard- margin.
Nếu α là lời giải của bài toán tối ưu này thì
^ β = α i y i x i (2.49) i∈sv là vector hệ số tối ưu, trong đó tập sv của vector support bao gồm các quan sát trong L mà thỏa mãn ràng buộc (2.41).
Support vector machine phi tuyến
Không gian đặc trưng
Giả sử chúng ta biến đổi mỗi quan sát, x i ∈ R r trong L bằng cách sử dụng ánh xạ không tuyến tính φ : R r −→ H, trong đó H là không gian
N H chiều. Ánh xạ phi tuyến tính φ được gọi là ánh xạ đặc trưng và không gian H được gọi là không gian đặc trưng.
Không gian H có thể có nhiều chiều, thậm chí vô hạn Giả sử H là không gian Hilbert của các hàm giá trị thực trên R, với tích vô hướng (ã, ã) và chuẩn ǁ ã ǁ.
Hình 2.4: Ánh xạ φ từ không gian dữ liệu X sang không gian đặc trưng F
Do đó, không gian mẫu được biến đổi là {φ(x i ), y i } trong đó y i ∈ {−1, +1} xác định 2 lớp Nếu chúng ta thay thế φ(x i ) cho x i trong việc phát triển SVM
Trong không gian H tuyến tính, dữ liệu chỉ được đưa vào bài toán tối ưu thông qua các tích (φ(x i ), φ(x j )) Tuy nhiên, việc sử dụng phép biến đổi tuyến tính gặp khó khăn do tính toán các tích này trong không gian H có số chiều cao.
Thủ thuật Kernel
Thủ thuật Kernel là một phương pháp hiệu quả trong các thuật toán, cho phép tính toán các tích (φ(x i ), φ(x j )) trong không gian đặc trưng H mà không cần thực hiện các phép toán tốn kém trong không gian này Thay vào đó, chúng ta sử dụng một hàm kernel không tuyến tính K(x i , x j ) = (φ(x i ), φ(x j )) để thực hiện tính toán trong không gian đầu vào, từ đó tăng tốc độ xử lý Nhờ vậy, chỉ cần thực hiện một SVM tuyến tính, nhưng các phép toán lại được thực hiện trong một không gian khác.
Kernel và tính chất Định nghĩa 2.2.1 Một kernel K là một hàm K : R r ×R r −→ R mà ∀x, y ∈ R r thì
Ví dụ 2.2.1 Xét phép biến đổi dữ liệu từ không gian đầu vào X = R 2 vào không gian đặc trưng H = R 3 được cho bởi φ :R 2 −→ R 3 x = (x 1 , x 2) ›→ φ(x) = (φ 1(x), φ 2(x), φ 3(x)) = (x 2 , √
2x 1 x 2 , x 2 ) Ánh xạ trên cũng có thể được lý giải như sau Cho x = (x 1 , x 2) và z = (z 1 , z 2) ta có:
Khi đó, chúng ta sẽ lấy K(x, z) = (φ(x), φ(z)) = (x, z) 2 Như vậy, khi sử dụng kernel chúng ta không cần phải tính ánh xạ φ.
Hàm kernel được phát triển nhằm tính toán các tích trong không gian H chỉ bằng dữ liệu đầu vào gốc Vì vậy, mọi trường hợp xuất hiện tích (φ(x), φ(y)) sẽ được thay thế bằng hàm kernel K(x, y).
• Việc lựa chọn K ngầm xác định cả φ và H.
Tiến bộ quan trọng trong việc sử dụng kernel cho các tích vô hướng là chúng ta không cần biết rõ dạng của hàm φ nếu đã có hàm kernel K được xác định trước.
Hàm kernel cần phải thỏa mãn tính đối xứng K(x, y) = K(y, x) và bất đẳng thức [K(x, y)]² ≤ K(x, x)K(y, y), điều này được suy ra từ bất đẳng thức Cauchy-Schwarz Nếu K(x, x) = 1 cho mọi x ∈ R, điều này ngụ ý rằng ǁφ(x)ǁH = 1.
Tính chất 2.2.1 Một kernel K được gọi là có tính chất tái tạo nếu ∀f ∈ H,
Nếu K có tính chất này, chúng ta gọi K là kernel tái tạo.
Trong trường hợp cụ thể, nếu f (ã) = K(ã, x) thỡ
Trong không gian R^r, với tập hợp n điểm x1, , xn, ma trận vuông cấp n K = (Kij) được định nghĩa bởi Kij = K(xi, xj) cho i, j = 1, 2, , n, được gọi là ma trận Gram của K Nếu ma trận Gram K thỏa mãn điều kiện u^T Ku ≥ 0 cho mọi vector u, thì K được xem là xác định không âm với các giá trị riêng không âm Khi đó, K được gọi là một kernel xác định không âm hay kernel Mercer.
Tính chất 2.2.2 Nếu K là một kernel Mercer trên R r × R r thì chúng ta có thể xây dựng một không gian Hilbert duy nhất H K của các hàm giá trị thực mà
K là kernel tái tạo Khi đó chúng ta gọi H K là một không gian Hilbert kernel tái tạo (thực).
Một số hàm kernel thường gặp
• Kernel đa thức không thuần nhất bậc d,
K(x, y) = ((x, y) + c) d , x, y ∈ R r (2.54) trong đó, c và d là các tham số.
Khi c = 0, kernel trở thành dạng thuần nhất Nếu d = 1 và c = 0, ánh xạ đặc trưng sẽ đồng nhất Thông thường, giá trị c được chọn lớn hơn 0 Một ví dụ về ánh xạ không tuyến tính đơn giản là trường hợp r = 2 và d.
Hàm φ(x) trong ví dụ này có 6 đặc trưng (H = R 6 ), bao gồm tất cả các đơn thức với bậc cao nhất là 2 Kernel này cho thấy rằng tham số c điều khiển độ lớn của số hạng hằng số và số hạng bậc 1.
Tổng quát, có dim(H) = r + d các đặc trưng khác nhau, bao gồm tất cả
Đơn thức có bậc lớn nhất là d, và số chiều của H có thể tăng nhanh chóng Chẳng hạn, trong bài toán nhận diện trực quan, dữ liệu có thể là các bức ảnh 16 × 16 pixel, tương ứng với mỗi bức ảnh trở thành một vector có chiều r = 256 Nếu d = 2, thì dim(H) đạt 33.670, trong khi với d = 4, dim(H) sẽ là 186.043.585.
• Một số kernel phổ biến khác được cho bởi bảng dưới đây
Kernel sigmoid không phải là một kernel độc lập, mà chỉ thỏa mãn điều kiện Mercer với các giá trị cố định của a và b Tuy nhiên, nó trở nên phổ biến trong một số tình huống nhất định, đặc biệt là trong mạng neural 2 lớp Các ví dụ về kernel biến đổi bất invariant bao gồm kernel Gaussian RBF, Laplacian và thin-plate spline, với dạng tổng quát K(x, y) = k(x − y) trong đó k : R^r → R Ngược lại, kernel đa thức là một ví dụ về kernel không bất invariant Một kernel bất invariant K(x, y) được coi là đẳng hướng nếu nó chỉ phụ thuộc vào khoảng cách δ = ||x − y||.
Bảng 2.1: Các hàm kernel K(x, y), trong đó σ > 0 là tham số, a, b, c ≥ 0, và d là một số nguyên Chuẩn Euclid là ǁxǁ 2 = x T x.
Polynomial of degree d ((x, y) + c) d Gaussian radial basis function exp,− ǁx−yǁ 2 ,
Thin-plate spline ǁx−yǁ Σ2 log e , ǁ x − y ǁ ,
Việc lựa chọn kernel trong các ứng dụng không phải lúc nào cũng rõ ràng Thông tin trước đó hoặc nghiên cứu qua thuật ngữ có thể hữu ích Nếu không có thông tin khả dụng, cách tiếp cận tốt nhất là thử kernel Gaussian RBF với tham số đơn σ hoặc kernel đa thức bậc thấp (d = 1 hoặc 2) Nếu cần thiết, có thể sử dụng các kernel phức tạp hơn để so sánh kết quả.
Xâu kernel cho phân loại văn bản được định nghĩa trong ngữ cảnh của một tập hợp hữu hạn các ký tự A Một "xâu" s = s1 s2 s|s| là một chuỗi hữu hạn các phần tử thuộc A, bao gồm cả xâu rỗng, với |s| là độ dài của xâu Đồng thời, u được coi là một dãy con của s, được ký hiệu là u = s(i), nếu tồn tại các chỉ số i = (i1, i2, , i|u|) thỏa mãn điều kiện 1 ≤ i1 < < i|u| ≤ |s|.
Nếu chỉ số i là tiếp liên, chúng ta nói rằng u là một xâu con của s. Định nghĩa 2.2.6 Độ dài của u trong s được cho bởi
ℓ(i) = i |u| − i 1 + 1 (2.55) là số phần tử của s overlaid bởi dãy con u.
Ví dụ 2.2.2 Cho S là xâu "cat" Tìm tất cả các xâu con 2 ký tự có thể của s và tìm độ dài của nó.
Ta có s 1 =c, s 2 =a, s 3 =t Các dãy 2 ký tự có thể có "ca", "ct" và
"at" Với xâu u chúng ta có u 1 =c= s 1, u 2 =a= s 2, do đó u = s(i) với i = (i 1 , i 2) = (1, 2) Do đó ℓ(i) = 2 Tương tự cho xâu con u ="ct": u 1 =c= s 1, u 2 =t= s 3, từ đó i = (i 1 , i 2) = (1, 3) và ℓ(i) = 3 và xâu u ="at" có u 1 =a= s 2, u 2 =t= s 3, từ đó i = (i 1 , i 2) = (2, 3) và ℓ(i) = 2.
Gọi D = A m là tập tất cả các xâu hữu hạn có độ dài lớn nhất bằng m từ
Không gian đặc trưng của một xâu kernel là R^D, trong đó ánh xạ đặc trưng φ_u áp dụng cho một xâu s ∈ A_m được mô tả dựa trên các số hạng của xâu cho trước u ∈ A_m Đối với các dãy con không tiếp liên, tỷ lệ "drop-off" λ ∈ (0; 1) được định nghĩa như một nhân tố "decay".
Giá trị φ u (s) được xác định bằng cách đồng nhất các dãy con được đánh chỉ số i của s tương tự như u Đối với mỗi dãy con, ta nâng λ lên lũy thừa ℓ(i) và sau đó tính tổng các kết quả trên toàn bộ các dãy con.
Do λ < 1, giá trị ℓ(i) càng lớn thì trọng số của nó càng nhỏ Chúng ta có thể diễn đạt điều này bằng công thức φ u (s) i:u=s(i) λ ℓ(i) , với u thuộc A m Trong ví dụ cụ thể, ta có φ ca(cat) = λ 2, φ ct(cat) = λ 3, và φ at(cat) = λ 2.
Hai tài liệu được coi là "tương tự" khi chúng chia sẻ nhiều dãy con chung Theo định nghĩa 2.2.7, cho hai xâu s và t, kernel liên kết với ánh xạ đặc trưng tương ứng được xác định bằng tổng các tích vô hướng của tất cả các dãy con chung có độ dài m.
Khi đó, kernel (2.57) được gọi là một xâu kernel.
Ví dụ 2.2.3 Cho t là xâu "car" (t 1=c, t 2=a, t 3=r, |t| = 3) Ta thấy xâu
Tối ưu hóa trong không gian đặc trưng
Cho K là một kernel, và giả sử rằng các quan sát trong L được phân tách tuyến tính trong không gian đặc trưng tương ứng với kernel K Trong trường hợp này, bài toán tối ưu đối ngẫu là tìm các tham số α và β 0 nhằm tối đa hóa hàm F.
(α) = 1 T α − 1 α T Hα (2.59) với ràng buộc α ≥ 0, α T y = 0, (2.60) trong đó, y = (y 1 , , y n ) T , H = (H ij ) và
Bởi vì K là một kernel, ma trận Gram K = (K ij ) là xác định không âm và như vậy cũng là ma trận H với các phần tử được xác định trong
(2.61) Do đó, hàm F D (α) là lồi Vì vậy, chúng ta sẽ có lời giải duy nhất với bài toán tối ưu ràng buộc
Nếu α là hệ số và β là hằng số khác không, thì quy tắc quyết định của SVM được biểu diễn bằng công thức f(x) = β + Σ(α_i y_i K(x, x_i)), trong đó Σ là tổng qua các vector hỗ trợ (support vectors) và K là hàm kernel Công thức này xác định siêu phẳng tách tối ưu trong không gian đặc trưng tương ứng với kernel K.
Trong trường hợp không thể tách biệt, bài toán đối ngẫu của bài toán tối ưu 1 norm soft-margin là tìm α để cực đại hóa F ∗ (α) = 1 T α − 1 α T Hα với các ràng buộc 0 ≤ α ≤ C1 n và α T y = 0 Với một lời giải tối ưu, các điều kiện Karush-Kuhn-Tucker vẫn giữ nguyên cho bài toán gốc, do đó, lời giải α cần phải thỏa mãn tất cả các điều kiện này May mắn thay, việc kiểm tra một tập hợp các điều kiện đơn giản hơn cũng đảm bảo tính đúng đắn: cần xác minh rằng α thỏa mãn ràng buộc α T y = 0.
(2.41) đúng cho tất cả các điểm trong đó 0 ≤ α i < C và ξ i = 0 và cũng cho tất cả các điểm trong đó α i = C và ξ i ≥ 0.
SVM là một phương pháp quy chuẩn
Phương pháp SVM có thể được xem như một giải pháp cho bài toán quy chuẩn cụ thể Trong đó, f ∈ H K đại diện cho không gian Hilbert kernel tái tạo tương ứng với kernel K, với chuẩn bình phương ǁfǁ² trong H K.
Xét sai số phân loại y i − f (x i ), trong đó y i ∈ {−1, +1} Khi đó
(2.65) trong đó (x)+ = max{x, 0}. Định nghĩa 2.2.8 Đại lượng (1 − y i f (x i ))+ mà có thể bằng 0 nếu tất cả các x i được phân loại đúng thì được gọi là hàm tổn thất hinge.
Hình 2.5: Hàm tổn thất Hinge (1 − yf (x))+ cho y = −1 và y = +1.
Chúng ta mong muốn tìm f ∈ H K để cực tiểu phiên bản phạt của tổn thất hinge Cụ thể chúng ta muốn tìm f ∈ H K để n cực tiểu 1 Σ(1 − y f (x )) + λǁf ǁ 2 , λ > 0 (2.66)
Sau khi cực tiểu f được tìm thấy thì quy tắc phân loại SVM là C(x) sign{f (x)}, x ∈ R r
Tiêu chuẩn tối ưu (2.66) không khả vi do hình dạng của hàm tổn thất hinge Tuy nhiên, chúng ta có thể tái cấu trúc bài toán và giải quyết nó bằng cách nhận thấy rằng mỗi hàm f ∈ H có thể được biểu diễn không duy nhất dưới dạng tổng của hai thành phần: f ǁ (ã) và f ⊥ (ã) Cụ thể, f ǁ ∈ H K là phép chiếu của f lên không gian con H K, trong khi f ⊥ là thành phần thuộc không gian con vuông góc với H K.
= 0, i 1, 2, , n Chúng ta có thể viết f (x i ) thông qua tính chất tái tạo như sau f (x i ) = (f (ã), K(x i , ã)) = f ǁ (ã), K(x i , ã)Σ + f ⊥ (ã), K(x i , ã) (2.68)
Bởi vì số hạng thứ 2 trên không gian Hilbert tái tạo bằng 0 nên n f (x) = α i K(x i , x), (2.69) i=1 độc lập với f ⊥ , trong đú chỳng ta đó sử dụng (2.67) và (K(x i , ã), K(x j , ã))
K(x i , x j ) Bây giờ từ (2.67), ta có ǁf ǁ H K H K i
, (2.70) i với dấu bằng xảy ra khi và chỉ khi f ⊥ = 0, trong trường hợp đó bất kỳ f ∈
H K mà cực tiểu (2.66) sẽ thừa nhận 1 biểu diễn dạng (2.69).
Từ (2.70), chúng ta có ǁf ǁ 2 = Σi Σj α i α j K(x i , x j ) = ǁβǁ 2 , trong đó n i=
1 αφ(x i ) Nếu không gian H K bao gồm các hàm tuyến tính có dạng f (x) = β 0 + φ(x) T β với ǁf ǁ 2 = ǁβǁ 2 thì bài toán tìm f trong (2.66) tương đương với tìm β 0 , β để cực tiểu 1 Σ(1 − y (β + φ(x ) T β))
Do đó, ở (2.66), hàm tổn thất hinge không khả vi có thể được tính toán lại thông qua việc giải quyết bài toán tối ưu lề mềm chuẩn 1.
Support vector đa lớp
SVM đa lớp là một chuỗi bài toán nhị phân
Ý tưởng chính cho bài toán phân loại đa lớp (trên K lớp) là chuyển đổi thành một chuỗi các bài toán nhị phân Có hai phương pháp tiếp cận khác nhau cho ý tưởng này.
• One-versus-rest (một so với phần còn lại): Chia bài toán K lớp thành K bài toán phân loại nhị phân nhỏ kiểu "lớp thứ k" với
Trong bài toán phân loại nhiều lớp, không phải lớp thứ k (với k = 1, , K) được xây dựng bằng cách áp dụng quy tắc phân loại f k Trong đó, lớp thứ k được coi là dương và các lớp khác được mã hóa là âm Khi đó, một điểm dữ liệu mới x sẽ được gán vào lớp dựa trên giá trị f k (x).
, K trong đó f k (x) là lời giải SVM tối ưu cho bài toán nhị phân của lớp thứ k và phần còn lại.
One - versus-one (một so với một): Chia bài toán K lớp thành K
• 2 cặp so sánh của các lớp Một quy tắc phân loại f jk được xây dựng bằng cách mã hóa lớp thứ j là dương và lớp thứ k là âm, j, k = 1,
, K; j ƒ= k Do đó với một x mới, chúng ta tổng hợp số phiếu cho mỗi lớp và gán x vào lớp có nhiều phiếu nhất.
Một SVM đa lớp đúng
Để xây dựng quy tắc phân loại SVM đa lớp chính xác, cần xem xét đồng thời tất cả K lớp Π1, , ΠK, và quy tắc này sẽ trở thành quy tắc phân loại nhị phân khi K = 2 Bài viết này sẽ khám phá quy tắc phân loại SVM do Lee, Lin và Wahba (2004) đề xuất.
Cho v1 , , v K là một dãy K vector xác định như sau v = (1, − 1
Nếu K = 2 thì v1 = (1, −1) T và v2 = (−1, 1) T Mỗi x i có thể được gán nhãn là một trong K vector; nghĩa là, x i có nhãn y i = v k nếu x i ∈ Π k ; i
Tiếp theo, chúng ta tổng quát hàm tách f (x) là một K vector f(x) = (f 1(x), , f K (x)) T , (2.72) trong đó f k (x) = β 0k + h k (x), h k ∈ H k , k = 1, , K (2.73)
Trong (2.73), H k là một không gian Hilbert kernel - tái tạo được mở rộng bởi
{K(x i , ã), i = 1, , n} Vớ dụ trong trường hợp tuyến tớnh, h k (x) = x T β k , với vector của các hệ số β k nào đó Chúng ta còn giả thiết cho tính duy nhất là
Cho L(y i ) là một K vector với 0 ở vị trí thứ k nếu x i ∈ Π k và giá trị 1 trong tất cả các vị trí khác Nếu K = 2 và x i ∈ Π1 thì L(y i ) = (0, 1) T , trong khi nếu x i ∈ Π2 thì L(y i ) = (1, 0) T
Do đó, bài toán tối ưu đa lớp (2.66) là tìm hàm f(x) = (f 1(x), , f K (x)) T thỏa mãn (2.74), đó là cực tiểu I (f, Y) = 1 Σ[L(y )] T (f(x ) − y ) + λ Σ ǁh ǁ 2 , (2.75) trong đó (f(x i )−y i )+ = ((f 1(x i )−y i1)+ , , (f K (x i )−y iK )+) T và Y = (y1 , , y n ) là một ma trận K × n.
Bằng cách lấy K = 2, chúng ta có thể thấy rằng (2.75) là một tổng quát của (2.66) Nếu x i ∈ Π1 thì y i = v1 = (1, −1) T và
= (1 − f 1(x i ))+ , (2.76) trong khi nếu x i ∈ Π2, thì y i = v2 = (−1, 1) và
Số hạng đầu tiên của hàm f trong công thức (2.66) tương đương với số hạng đầu tiên của hàm f1 trong công thức (2.75) khi K = 2 Khi đặt K = 2 trong số hạng thứ hai của (2.75), chúng ta sẽ nhận được kết quả cụ thể.
2 ǁh k ǁ 2 = ǁh 1ǁ 2 + ǁ − h 1ǁ 2 = 2ǁh 1ǁ 2 , (2.78) k=1 vì thế, các số hạng thứ 2 của (2.66) và (2.75) là đồng nhất.
Hàm h k ∈ H k có thể phân tích thành 2 phần h k (ã) = Σ β ℓk K (x ℓ , ã) + h ⊥ (ã), (2.79)
Trong không gian Hilbert, ℓ=1 là một yếu tố quan trọng, với β ℓk là các hằng số và h ⊥ (ã) là phần tử trong không gian này Việc tái tạo trực giao với H K có thể được thực hiện bằng cách thay thế (2.74) vào (2.75), sau đó áp dụng (2.79) và sắp xếp lại các số hạng để đạt được kết quả mong muốn.
Do K(ã, ã) là một kernel tỏi tạo
Do đú, để cực tiểu (2.84), chỳng ta lập h ⊥ (ã) = 0 với mọi k Từ 2.82 , ràng buộc tổng 0 (2.74) trở thành n β¯ 0 + β¯ ℓ K(x ℓ , ã) = 0, (2.85)
6Kβ ik Tại n điểm dữ liệu k=1
{x i , i = 1, 2, , n}, (2.85) được ký hiệu dưới dạng ma trận bởi
(Σ β 0k )1 n + K(Σ β k ) = 0, (2.86) trong đó K = (K(x i , x j )) là một n × n ma trận Gram và β k = (β 1k , , β nk ) T Cho β ∗ = β 0k − β¯ 0 và β ∗ β ik = β ik − β¯ i Sử dụng (2.85), chúng ta thấy rằng k Σ n k k k k Σ k= 1 k= 1 k=
0 k i k phiên bản trung tâm của (2.82) là f ∗ (x i )
(2.87) trong đó, β¯ = (β¯ 1 , , β¯ n ) T ; nếu Kβ¯ = 0, thì bất đẳng thức trở thành đẳng thức và vì vậy Σ K β 0k = 0 Do đó, n K K n
Vì vậy, cực tiểu (2.75) ràng buộc tổng bằng 0 (2.74) chỉ tại n điểm dữ liệu tương đương với cực tiểu
(2.75) với ràng buộc cho mỗi x.
Tiếp theo, chúng ta sẽ xây dựng 1 biểu thức Lagrange của bài toán tối ưu
(2.75) bằng cách sử dụng các ký hiệu sau Cho ξ i = (ξ i1 , ã ã ã , ξ iK ) T là một K vector của các biến bù tương ứng với (f (x i ) − y i )+ , i = 1, 2,
ξ n ) T là (n × K) ma trận có cột thứ k là ξ k và hàng thứ i là ξ i Cho L1 , ã ã ã
) m a t rận có cột thứ k là
L iK ) Cho (y 1 , ã ã ã , y K ) = (y1 , ã ã ã , y n ) T là ma trận cỡ (n ×
K) mà cột thứ k là y k và hàng thứ i là y i
Bài toán gốc là tìm {β 0k }, {β k } và {ξ k } để cực tiểu Σ+
Lập hàm gốc F P = F P ({β 0k }, {β k }, {ξ k }), trong đó
Trong (2.94), vector α.k bao gồm các thành phần (α1k, ããã, αnk)T, và γk là vector hệ số Lagrange không âm cho các bất đẳng thức ràng buộc (2.91) và (2.92) Đồng thời, δ là vector của các hệ số Lagrange không ràng buộc cho phương trình (2.93) Khi thực hiện đạo hàm (2.94) theo các biến β0k, β.k và ξ.k, ta sẽ thu được kết quả cần thiết.
Các điều kiện Karush-Kuhn-Tucker là
k trong đó, từ (2.97), γ k = L k − α k Chú ý rằng, (2.100) và (2.101) là tích vô hướng của 2 vector cột.
Từ (2.97) và (2.99) chúng ta có 0 ≤ α k ≤ L k , k = 1, 2, , K Giả sử rằng với mỗi i, 0 ≤ α ik < L ik ; thì γ ik > 0 và từ (2.101) ξ ik = 0, từ đó, từ (2.100), y ik = β 0k + Σ n β ℓk K(x ℓ , x i ).
Cho các đạo hàm bằng 0 với k = 1, 2, , K chúng ta thu được δ = −α¯ −1 K k=1 α k từ (2.95), từ đó (α k −α¯) T 1 n = 0, và, từ (2.96), β k = −(nλ) −1 (α k −
ℓ= 1 Σ−K α¯), giả sử rằng K là xác định dương.
Bài toán đối ngẫu là tìm {α k } để
Từ lời giải αˆ k cho bài toán lập trình bậc hai này, chúng ta lập βˆ k = −(nλ) −1 (αˆ k − αˆ¯), (2.105) trong đó αˆ¯ = K −1 Σ K αˆ k
Lời giải của bài toán phân loại đa lớp cho một x mới được cho bởi
Giả sử vector hàng αˆ i = (αˆ i1 , ã ã ã , αˆ iK ) = 0 với (x i , y i ); thỡ từ (2.105), βˆ i (βˆ i1 , ã ã ã , βˆ iK ) = 0 Điều này chỉ ra rằng số hạng βˆ ik K(x i , x) = 0, k = 1,
Bất kỳ số hạng nào chứa (x i , y i ) sẽ không xuất hiện trong (2.107), vì vậy việc (x i , y i ) có nằm trong tập L hay không không ảnh hưởng đến lời giải Điều này dẫn đến định nghĩa về support vector: "Một quan sát (x i , y i ) được gọi là một support vector nếu βˆ i = (βˆ i1 , ã ã ã , βˆ ik ) ƒ= 0".
Một số ví dụ thực tế
Minh họa về phân tích phân biệt tuyến tính
Một công ty sản xuất sản phẩm cao cấp với giá thành đắt đỏ đã mô tả sản phẩm của mình qua hai đặc trưng chính: "độ cong" và "đường kính" Kết quả kiểm soát chất lượng của sản phẩm này được đánh giá bởi các chuyên gia và được trình bày trong bảng 3.1 dưới đây.
Để thiết lập mô hình tự động kiểm tra chất lượng sản phẩm trong công ty, chúng ta cần áp dụng phân tích phân biệt Ví dụ, với sản phẩm mới có độ cong 2.81 và đường kính 5.46, chúng ta sẽ xác định xem sản phẩm đó đạt yêu cầu hay không.
Bước đầu tiên là vẽ 7 sản phẩm dựa trên hai đặc trưng: độ cong theo trục Ox và đường kính theo trục Oy Qua đó, chúng ta nhận thấy có thể tạo ra một đường phân tách rõ ràng giữa hai lớp sản phẩm: lớp đạt gồm 4 sản phẩm và lớp không đạt gồm 3 sản phẩm Nhiệm vụ đặt ra là tìm ra đường phân tách tối ưu để tối đa hóa khoảng cách giữa hai lớp và đồng thời tối thiểu hóa khoảng cách giữa các đối tượng trong cùng một lớp.
Bước 2 Chúng ta biểu diễn các đối tượng dưới dạng ma trận như sau
- Ma trận các đặc trưng(biến độc lập) x Mỗi dòng biểu diễn 1 đối tượng và mỗi cột biểu diễn 1 đặc điểm.
- Ma trận các lớp y chứa các lớp của đối tượng(biến phụ thuộc) Như vậy ở
Bảng 3.1: Bảng dữ liệu kiểm tra kết quả chất lượng sản phẩm
Stt Độ cong Đường kính Kết quả
Hình 3.1: Đồ thị dữ liệu gốc. đây chúng ta sẽ có
Chương 3 Một số ví dụ thực tế 50
Trong ma trận x, gọi x k là dòng thứ k, với g là số lớp trong tập dữ liệu y Tại đây, g = 2, có nghĩa là chúng ta có hai lớp Đặt x i là ma trận chứa các đặc trưng của các đối tượng thuộc lớp i, với i = 1, 2 cho hai lớp này.
Gọi à i là trung bỡnh cỏc đặc trưng của cỏc đối tượng thuộc lớp i Như vậy, à1 = 3.05 6.38 à2 = 2.67 4.73
Gọi à là trung bỡnh của toàn thể dữ liệu à = 2.89 5.68Σ
Dữ liệu được điều chỉnh trung bình, hay còn gọi là "mean corrected data", được tính bằng cách lấy ma trận chứa các đặc trưng của đối tượng trong lớp i (x i) trừ đi ma trận chứa giá trị trung bình của toàn bộ dữ liệu Do đó, công thức được biểu diễn là x 0 = x i − à.
Chương 3 Một số ví dụ thực tế 56
Ma trận hiệp phương sai của lớp i được tính theo công thức sau
Ma trận gộp hiệp phương sai của 2 lớp được tính như sau
Như vậy, chúng ta có
0.791 0.701 p là vec tơ xác suất của mỗi lớp Hàng thứ i biểu diễn xác suất của lớp i được tính: p i n i
= Trong ví dụ này, chúng ta có
Hàm phân biệt được cho bởi
Sau khi tính toán các giá trị L i , chúng ta gán đối tượng k vào nhóm i sao cho
L i có giá trị lớn nhất Ở đây, chúng ta viết x k = 2.81 5.46Σ Khi đó,
Như vậy, sản phẩm sẽ được gán vào nhóm 2 Do đó, sản phẩm mới sẽ có kết quả kiểm tra là không đạt chất lượng.
Ứng dụng SVM để phân loại email và spam
Sự phát triển của dịch vụ thông tin trên Internet đã thúc đẩy sự gia tăng của hệ thống thư điện tử, nhưng cũng đi kèm với đó là tình trạng thư rác ngày càng nghiêm trọng, gây thiệt hại cho người dùng qua việc lãng phí tài nguyên mạng và thời gian Do đó, việc xây dựng các giải pháp tự động để lọc và chống thư rác trở thành nhu cầu thiết yếu Hệ thống lọc thư rác thường sử dụng phương pháp phân loại văn bản, với hai nhóm chính là thư rác (spam mail) và thư sạch (email) Tuy nhiên, việc xác định thư rác không có định nghĩa chính xác và có thể thay đổi tùy theo đối tượng và hoàn cảnh, thường bao gồm các thư có nội dung văn hóa độc hại, thư quảng cáo phát tán ồ ạt, và thư tuyên truyền với mục đích xấu.
Vì vậy, một hệ thống phân loại tự động có khả năng học để thích nghi là cần thiết cho các hệ thống thư điện tử.
Phương pháp SVM là một kỹ thuật hiệu quả trong phân loại thư rác, nhờ vào bản chất thống kê của nó, mang lại nhiều ưu điểm đáng kể.
Bộ dữ liệu mà chúng tôi sử dụng được lấy từ một bộ sưu tập email spam và email hợp lệ, bao gồm tổng cộng 4,601 tin nhắn, trong đó có 1,813 thư rác và 2,788 email Mỗi tin nhắn sẽ được chuyển đổi thành một vector với 57 tọa độ, tương ứng với 57 biến để phân biệt giữa email và thư rác Trong số đó, 48 biến có dạng "word_freq_WORD" thể hiện tỷ lệ phần trăm của các từ trong email, 6 biến có dạng "word_freq_CHAR" cho biết phần trăm của các ký tự, và 3 biến độ dài đo lường độ dài trung bình, độ dài lớn nhất và tổng độ dài của chuỗi chữ hoa liên tiếp Mỗi tin nhắn cũng được gán nhãn để phục vụ cho việc phân tích.
Chúng tôi đã sử dụng SVM để phân loại 4,601 tin nhắn vào hai lớp email và thư rác, nhằm đánh giá tỷ lệ phân loại sai và độ chính xác của phương pháp Cụ thể, chúng tôi áp dụng SVM không tuyến tính với kernel RBF cho 4,061 tin nhắn, bao gồm 2,788 email và 1,813 thư rác Giải pháp SVM phụ thuộc vào chi phí C của việc vi phạm ràng buộc và phương sai σ² của kernel Gauss RBF Thông qua phương pháp thử và sửa sai, chúng tôi đã sử dụng lưới các giá trị cho C và γ = 1.
Trong hình, các giá trị của 10-fold CV cho tỷ lệ phân loại sai tương ứng với γ được trình bày, với mỗi đường cong đại diện cho một giá trị khác nhau của C Đường cong phân loại sai CV/10 cho thấy sự tương đồng về hình dạng, với một giá trị cực tiểu gần γ bằng 0 và xu hướng tăng khi γ xa 0 Trong quá trình tìm kiếm, chúng ta xác định được cực tiểu CV/10 với tỷ lệ phân loại sai là 8.06% tại (C; γ) = (500, 0.0002) và (1,000, 0.0002) Điều này cho thấy tỷ lệ phân loại sai có xu hướng giảm khi C tăng và γ giảm đồng thời.
Một nghiên cứu cho thấy rằng với C > 1000 và γ gần 0, tỷ lệ phân loại sai trong phương pháp CV/10 đạt 6.91% khi C = 11,000 và γ = 0.00001, tương ứng với ước lượng 10 CV của tỷ lệ phân loại đúng.
Giải pháp này sử dụng 931 vector hỗ trợ, trong đó có 482 email và 449 spam, cho thấy rằng 79.8% số tin nhắn (cụ thể là 82.7% email và 75.2% spam) không nằm trong điểm hỗ trợ Trong tổng số 4601 tin nhắn, có 2697 email được phân loại.
Việc phân loại 1676 thư rác với 228 trường hợp phân loại sai đã cho thấy tỷ lệ sai số là 4.96% So với các phương pháp khác trong việc lọc thư rác, SVM tỏ ra ưu việt và đáp ứng tốt nhu cầu người dùng Tiêu chí phân loại có thể được học từ các mẫu riêng của từng cá nhân, cho phép mỗi người hoặc đơn vị phát triển phương pháp lọc riêng biệt Sự linh hoạt của SVM cũng giúp dễ dàng điều chỉnh để thích ứng với các loại thư rác mới Trong khi các công cụ khác cần nhiều công sức để cập nhật luật lọc, SVM chỉ cần học lại trên tập mẫu mở rộng, tự động phát triển tiêu chuẩn lọc phù hợp với tình huống mới.
Chương trình này không chỉ dựa vào các mẫu thư rác mà người dùng cung cấp để huấn luyện, mà còn sử dụng các mẫu thư mong muốn, được coi là hợp lệ Những đặc tính của thư mong muốn tạo ra một hệ thống chỉ dẫn thứ hai, tăng cường khả năng phân lớp cho các thư phức tạp và không rõ ràng Hệ thống cho phép thêm một phạm trù phân loại thứ ba mang tên “mong muốn đảm bảo”, bên cạnh các phạm trù “spam đảm bảo” và “không rõ, không giống spam”, giúp cho quá trình phân lớp trở nên cụ thể và rõ ràng hơn.
Dữ liệu chẩn đoán ung thư vú Wisconsin
Ung thư vú là nguyên nhân đứng thứ hai trong số các nguyên nhân gây tử vong do ung thư ở phụ nữ Hiện nay, có ba phương pháp chẩn đoán ung thư vú phổ biến được áp dụng.
• Sinh thiết tuyến vú bằng chọc hút kim nhỏ(FNA) với giải thích hình ảnh
Mặc dù phẫu thuật sinh thiết rất chính xác trong việc phân biệt khối u ác tính và khối u lành tính, nhưng quy trình này lại tốn thời gian và chi phí cao Đại học Wisconsin - Madison đã phát triển một hệ thống hình ảnh máy tính mới nhằm tạo ra quy trình chẩn đoán FNA với độ chính xác cao hơn.
FNA (chọc hút bằng kim nhỏ) là một thủ thuật nhằm lấy mẫu mô từ tổn thương nghi ngờ ở vú để chẩn đoán bệnh lý tuyến vú Mẫu FNA sau đó được đặt trên slide kính và nhuộm màu để làm nổi bật cấu trúc hạt nhân Hình ảnh từ FNA được chuyển đến máy trạm thông qua camera gắn trên kính hiển vi, giúp xác định ranh giới chính xác của hạt nhân Chúng tôi đã xác định 10 biến của hạt nhân từ các tế bào trong mẫu chất lỏng, được liệt kê trong bảng sau.
Các biến được thiết kế để chỉ ra khả năng mắc bệnh ác tính cao hơn thông qua các giá trị lớn Mỗi hình ảnh chứa từ 10 đến 40 nhân, với các chỉ số bao gồm giá trị trung bình (mv), giá trị cực (ev) là giá trị lớn nhất hoặc tồi tệ nhất, cùng với kích thước lớn nhất và hình dạng bất thường nhất, và độ lệch chuẩn (sd) của từng tế bào được tính toán Tổng cộng, chúng ta sẽ có những thông tin quan trọng để phân tích.
Trước khi tiến hành phân tích dữ liệu, chúng ta sẽ lấy loga tự nhiên của 30 biến không âm, do chúng có biểu đồ lệch nhau Để xử lý dữ liệu, giá trị 0 sẽ được thay thế bằng 0.001 trước khi thực hiện biến đổi Như vậy, các dữ liệu đã được biến đổi để phù hợp với yêu cầu phân tích.
Tập dữ liệu gồm 569 trường hợp hình ảnh, trong đó có 212 hình ảnh chẩn đoán ác tính (xác nhận bằng phẫu thuật sinh thiết) và 357 hình ảnh chẩn đoán lành tính (xác nhận bằng sinh thiết hoặc kiểm tra y tế định kỳ) Nhiều cặp biến có sự tương quan cao, với 19 cặp có hệ số lớn hơn 0.8 và 0.9, trong đó 6 cặp có hệ số lớn hơn 0.99 Bài toán đặt ra là làm thế nào để phân loại hiệu quả các khối u ác tính và lành tính mà không cần thực hiện phẫu thuật.
Để phân biệt giữa khối u lành tính và ác tính, cần sử dụng một hàm phân biệt tuyến tính (LDF) được suy ra từ việc ước lượng các hệ số cho một tổ hợp tuyến Mục tiêu là thực hiện điều này với số lượng biến tối thiểu.
Bảng 3.2 trình bày 10 biến trong nghiên cứu dữ liệu ung thư vú, bao gồm: bán kính hạt nhân (radius), phương sai mức xám bên trong ranh giới hạt nhân (texture), khoảng cách xung quanh chu vi hạt nhân (peri), diện tích hạt nhân (area), độ trơn của đường viền hạt nhân (smooth), và thước đo tính compact của nhân tế bào (comp) theo công thức peri.
Mức độ nghiêm trọng của các lõm trong nhân tế bào được đánh giá thông qua việc đo kích thước và số lượng các điểm lõm Tính đối xứng và chiều fractal của tế bào cũng được xem xét, với tối ưu hóa cho 30 biến đầu vào Từ kết quả LDF, chúng tôi tính toán một điểm cho mỗi 569 khối u và sau đó phân loại các điểm theo nhóm.
Chúng ta ước lượng tiên nghiệm π 1 và π 2 bởi πˆ1
569 = 0.3726 Các hệ số của LDF được ước lượng bởi tính toán đầu tiên X¯ 1 , X¯ 2 và ma trận covariance chung ˆ
XX và do đó sử dụng 1.24 Các kết quả được cho bởi bảng 3.2.
Sử dụng quy trình kiểm chứng chéo leave-one-out làm giảm 1 quan sát từ tập
Bảng 3.3 trình bày các hệ số ước lượng của hàm phân tích phân biệt Fisher cho dữ liệu ung thư vú, trong đó tất cả các biến đã được chuyển đổi sang dạng loga tự nhiên.
Bài viết trình bày các hệ số biến đổi (mv, sd, ev) cho các yếu tố như radius, texture, peri, area, smooth, comp, scav, ncav, symt, và fracd Dữ liệu được sử dụng để ước lượng lại LDF từ (n − 1) quan sát còn lại, và quy trình này được lặp lại 569 lần cho mỗi quan sát trong tập dữ liệu Bảng "sai số" cho việc phân loại 569 quan sát được cung cấp, trong đó tổng số hàng là số phân loại đúng và tổng số cột là dự đoán phân loại sử dụng Fisher LDF cùng với kiểm chứng chéo leave-one-out Từ đó, tỷ lệ phân loại chính xác được xác định.
Bảng 3.4: Bảng sai số trong nghiên cứu dữ liệu ung thư vú.
Dự đoán lành tính Dự đoán ác tính Tổng hàng
Tổng cột 373 196 569 lệ chia lớp sai với LDF Fisher trong ví dụ này được ước lượng là 24
Chương 3 Một số ví dụ thực tế 60