�ݺ�ߣ

MỘT PHƯƠNG PHÁP TIẾN HÓA TRONG VIỆC TẠO HỒ CHỨA TẬP CÁC BỘ PHÂN LOẠI PHẠM ĐÌNH DUY PHƯƠNG [email_address]

Nội dung trình bày Hướng tiếp cận truyền thống trong nhận dạng mẫu Hướng tiếp cận kết hợp các bộ phân loại Các mô hình hệ thống kết hợp các bộ phân loại Mẫu kết hợp các bộ phân loại Vấn đề Giải pháp 1: Lựa chọn bộ phân loại động Giải pháp 2: Lựa chọn bộ phân loại động “mở rộng” GA/BGA Luật kết hợp

Hướng tiếp cận truyền thống Kết luận Giá trị đặc trưng (mô tả đối tượng) Bộ phân loại Thiết kế bộ phân loại tốt Chọn tập đặc trưng phù hợp

Hướng tiếp cận kết hợp các bộ phân loại Bộ phân loại Giá trị đặc trưng (Mô tả đối tượng) Bộ phân loại Bộ phân loại Kết quả Kết hợp

Hệ thống kết hợp bộ phân loại - Mô hình 1 Kết luận Bộ phân loại Bộ phân loại Bộ phân loại Kết hợp Lựa chọn mô hình kết hợp

Hệ thống kết hợp bộ phân loại - Mô hình 2 Kết luận Bộ phân loại Bộ phân loại Bộ phân loại Kết hợp Sử dụng các mô hình bộ phân loại khác nhau

Hệ thống kết hợp bộ phân loại - Mô hình 3 Kết luận Bộ phân loại Bộ phân loại Bộ phân loại Kết hợp Xây dựng các bộ phân loại dựa trên các tập con đặc trưng khác nhau Hữu dụng khi số lượng đặc trưng rất lớn, hoặc các đặc trưng này xuất phát từ các nguồn khác nhau.

Hệ thống kết hợp bộ phân loại - Mô hình 4 Thay đổi tập “đào tạo”, cho phép hình thành tập các bộ phân loại “đa dạng”. Nhiều chuyên gia đánh giá đây là hướng tiếp cận mạnh mẽ nhất trong 4 hướng tiếp cận. Hai hệ thống thực tế được đánh giá cao sử dụng mô hình này: AdaBoost ( Ada ptive Boost ing), Bagging ( B ootstrap Agg reagat ing )

Mẫu kết hợp các bộ phân loại Có 2 kiểu kết hợp các bộ phân loại chính: Classifier Selection (Modular approach) Mỗi bộ phân loại là một “chuyên gia” trong một số phạm vi không gian đặc trưng. Chỉ cần chọn duy nhất một “chuyên gia” để đưa ra quyết định. Classifier Fusion (Ensemble approach) Tất cả các bộ phân loại đều được “đào tạo” trên toàn bộ không gian đặc trưng. Mang tính chất “ cạnh tranh ” hơn là “ bổ trợ ”

Vấn đề Trong quá trình phát triển một phương pháp kết hợp, vấn đề được đặt ra Chọn tất cả các bộ phân loại có sẵn vào hồ chứa kết hợp, hay Chỉ chọn ra một tập con phù hợp . Lựa chọn thứ nhất đang chiếm ưu thế. Tuy nhiên, không có gì đảm bảo lựa chọn này cho hiệu quả tốt nhất.

Lựa chọn bộ phân loại động Tập các bộ phân loại Kết quả Bộ phân loại “tốt nhất” Mẫu Lựa chọn động

Lựa chọn bộ phân loại động Ưu điểm: Đơn giản hóa quá trình lựa chọn bộ phân loại. Hạn chế: Toàn bộ mô hình sẽ phức tạp hơn. Không đảm bảo được tính tối ưu. Thay vì chỉ chọn ra một bộ phân loại, chúng ta sẽ chọn động một hồ chứa gồm nhiều bộ phân loại

Lựa chọn bộ phân loại động “mở rộng” Luật kết hợp Kết quả Các bộ phân loại có sẵn Hồ chứa tập các bộ phân loại Mẫu Lựa chọn động

Độ tin cậy Bộ phân loại E i L ớp C ij Đ ộ tin cậy R ij Mẫu S j Lớp C ij là lớp E i gán cho mẫu cần phân loại Độ tin cậy R ij của việc phân loại Điều kiện để bộ phân loại E i được chọn?

Ngưỡng ϴ 1NC … ϴ 11 C NC … … C 1 E 1 … … … … … … … … ϴ NENC .. ϴ NE1 E NE Ngưỡng Số lượng ngưỡng này sẽ dựa trên số lượng các bộ phân loại N E cũng như số lượng lớp mẫu N C Ứng với mỗi bộ phân loại và mỗi lớp mẫu, giá trị của tập ngưỡng này được hiểu như là giá trị nhỏ nhất của độ tin cậy của bộ phân loại được chọn vào hồ chứa. Các ngưỡng trong mô hình nhằm mục đích với mỗi mẫu, chọn ra được một tập những bộ phân loại tốt nhất , và do đó tỉ lệ nhận dạng trên toàn bộ tập dữ liệu là lớn nhất.

Ngưỡng Từ vấn đề chọn động hồ chứa các bộ phân loại, ta đưa về bài toán tìm một tập giá trị các ngưỡng Thỏa điều kiện với mọi ϴ il , việc loại bộ phân loại E i ra khỏi hồ chứa khi C ij = C l và R ij < ϴ il hiệu quả của hệ thống trên toàn bộ tập dữ liệu sẽ tốt hơn so với khi chưa loại E i ra khỏi hồ chứa. Giải bài toán này như thế nào? Thuật giải di truyền nhân giống - BGA

Genetic Algorithm - GA GA là kỹ thuật chung giúp giải quyết vấn đề - bài toán bằng cách mô phỏng sự tiến hóa của con người hay của sinh vật nói chung trong điều kiện quy định sẵn của môi trường. Các GA vận hành trên một quần thể, mỗi cá thể là giải pháp tiềm tàng, áp dụng nguyên lý “ kẻ mạnh nhất là kẻ sống sót ” để sinh ra những xấp xỉ tốt hơn cho giải pháp.

Genetic Algorithm - GA Các thông số của bài toán sẽ được chuyển đổi và biểu diễn dưới dạng các chuỗi nhị phân. Ví dụ, một bài toán với hai biến, x 1 và x 2 có thể ánh xạ vào cấu trúc chromosome theo cách sau

Genetic Algorithm - GA Giá trị độ thích nghi này có thể đơn giản hiểu là độ “tốt” của lời giải Để cải thiện tính thích nghi của quần thể, người ta tìm cách tạo ra quần thể mới. Có hai thao tác thực hiện trên thế hệ hiện tại để tạo ra một thế hệ mới với độ thích nghi tốt hơn. Chọn lọc nguyên mẫu một nhóm các cá thể tốt từ thế hệ trước rồi đưa sang thế hệ sau. Tạo các cá thể mới bằng cách thực hiện các thao tác sinh sản trên một số cá thể được chọn từ thế hệ trước. Có hai loại thao tác sinh sản: Lai tạo ( crossover, recombination ) Đột biến ( mutation )

Breeder Genetic Algorithm - BGA BGA lần đầu tiên được giới thiệu bởi Muhleiibein và Schlierkamp-Voosen vào năm 1993 BGA là một thuật giải di truyền dựa trên việc chọn lọc nhân tạo tương tự như những gì con người thực hiện việc nhân giống. BGA biểu diễn những giải pháp dưới dạng vector các giá trị thực, cho phép biểu diễn gần với thực tế hơn những GA thông thường (sử dụng vector các giá trị nguyên hoặc nhị phân)

Breeder Genetic Algorithm - BGA Dựa trên thuật ngữ sinh học, mô hình GA truyền thống mô hình sự chọn lọc tự nhiên , trong khi BGA mô hình sự chọn lọc nhân tạo . BGA sử dụng mô hình chọn lọc xén T% (được gọi là tỉ lệ xén) những cá thể tốt nhất được chọn lựa và được “gây giống” một cách ngẫu nhiên cho đến khi số lượng con cháu đạt đến kích thước của quần thể. Thế hệ con cháu sẽ thay thế thế hệ bố mẹ.

Thuật toán BGA Phát sinh ngẫu nhiên một quần thể ban đầu gồm N cá thể while (chưa kết thúc được) do for i from 1 to N do Đánh giá độ thích nghi của mỗi cá thể end for //Đảm bảo thế hệ mới lúc nào cũng chứa cá thể tốt nhất của thế hệ trước Lưu cá thể tốt nhất vào thế hệ mới Chọn T% cá thể tốt nhất for i from 1 to N/2 do Chọn ngẫu nhiên 2 cá thể trong số T% cá thể Lai ghép 2 cá thể này để sinh ra 2 cá thể con Thực hiện đột biến trên 2 cá thể con này End for Cập nhật các biến cho việc kết thúc End while

Mô hình bài toán với BGA ϴ 1NC … ϴ 11 C NC … … C 1 E 1 … … … … … … … … ϴ NENC .. ϴ NE1 E NE Mã hóa Mã hóa gen gen Nhiễm sắc thể Mỗi gen trong nhiễm sắc thể của một cá thể trong quần thể tương ứng với giá trị mã hóa của một ngưỡng, tương ứng với một bộ phân loại và một lớp mẫu

Mô hình bài toán với BGA Môi trường BGA tương tác trong suốt quá trình tiến hóa chứa số lượng mẫu thử bằng đúng với số lượng mẫu “đào tạo”. Mỗi mẫu thử này (tương ứng với một bộ phân loại) chứa độ tin cậy của việc phân loại và lớp mẫu mà bộ phân loại tương ứng gán cho mẫu. Các mẫu thử này dùng để đánh giá độ tốt của một cá thể – hàm mục tiêu. Để từ giá trị hàm mục tiêu, ta có thể đi đến xác định độ thích nghi của cá thể. Độ thích nghi của nhiễm sắc thể thứ i trong quần thể được tính bởi công thức: n c là số mẫu “đào tạo” phân loại đúng, n t là tổng số mẫu “đào tạo”.

Majority Vote Gán mẫu s cho lớp k nếu Với Ý nghĩa: gán mẫu s cho lớp k nếu số lượng chuyên gia gán mẫu s cho lớp k là nhiều nhất .

Majority Vote Xét ví dụ đơn giản N E = 3, N C = 2 Kiểm tra việc gán mẫu S 1 cho lớp C 1 VT = δ 11 + δ 21 + δ 31 = 1 + 1 + 0 = 2 VP = max { δ 11 + δ 21 + δ 31 , δ 12 + δ 22 + δ 32 } = max { 1 + 1 + 0, 0 + 0 + 1} = 2 Vậy VT = VP. Kết luận: gán mẫu S 1 cho lớp C 1 S 1 E 1 E 2 E 3

Weighted Majority Vote Gán mẫu s cho lớp k nếu Trong đó, ω ij là trọng số liên quan đến chuyên gia thứ i trong việc gán mẫu cho lớp j. ω ij = 0 nếu E i gán mẫu cho lớp C j’ , j’ ≠ j Ngược lại, ω ij thể hiện độ tin cậy RDR ij của việc E i gán mẫu cho lớp C j Nhận xét: RDR ij = 0 nếu R j = ϴ ij RDR ij = 1 nếu R j = 1

Weighted Majority Vote Giả sử ϴ 11 = 0.5, ϴ 21 = 0.6, ϴ 31 = 0.6, ϴ 12 = 0.5, ϴ 22 = 0.4, ϴ 32 = 0.5 Xét k = 1 (lớp C 1 ), ω 11 = 0.4, ω 21 = 0.25, ω 31 = 0 VT = 0.4 + 0.25 = 0.65 VP = max { ω 11 + ω 21 + ω 31 , ω 12 + ω 22 + ω 32 } = max {0.65, 0 + 0 + 0} = 0.65 Vậy VT = VP S 1 E 1 , R 11 =0.7 E 2 , R 21 =0.7 E 3 , R 32 =0.2

Đánh giá thực nghiệm Đánh giá thực nghiệm do nhóm tác giả thực hiện trên hướng tiếp cận này cho thấy: Đạt kết quả tốt hơn so với việc kết hợp tất cả các bộ phân loại có sẵn. Đạt hiệu quả trong việc cân bằng giữa độ phức tạp của hệ thống đa bộ phân loại với tính không nhất quán trong các quyết định của hệ thống.

�ݺ�ߣ

Mot phuong phap tien hoa trong viec tao ho chua tap cac bo phan loai

More Related Content

Mot phuong phap tien hoa trong viec tao ho chua tap cac bo phan loai