Tiếp cận thuật giải di truyền để tăng hiệu quả phân lớp dữ liệu - Th.S Đào Thị Nha Trang

pdf
Số trang Tiếp cận thuật giải di truyền để tăng hiệu quả phân lớp dữ liệu - Th.S Đào Thị Nha Trang 7 Cỡ tệp Tiếp cận thuật giải di truyền để tăng hiệu quả phân lớp dữ liệu - Th.S Đào Thị Nha Trang 259 KB Lượt tải Tiếp cận thuật giải di truyền để tăng hiệu quả phân lớp dữ liệu - Th.S Đào Thị Nha Trang 0 Lượt đọc Tiếp cận thuật giải di truyền để tăng hiệu quả phân lớp dữ liệu - Th.S Đào Thị Nha Trang 1
Đánh giá Tiếp cận thuật giải di truyền để tăng hiệu quả phân lớp dữ liệu - Th.S Đào Thị Nha Trang
4.9 ( 21 lượt)
Nhấn vào bên dưới để tải tài liệu
Để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

TIẾP CẬN THUẬT GIẢI DI TRUYỀN ĐỂ TĂNG HIỆU QUẢ PHÂN LỚP DỮ LIỆU Th.S Đào Thị Nha Trang GV khoa Cơ sở - Cơ bản I. ĐẶT VẤN ĐỀ lời giải tương đối tối ưu. Tính tối ưu Ý niệm về thuật giải di truyền được thể hiện ở chỗ thế hệ sau bao giờ (Genetic Algorithms: GA) đã được các cũng tốt hơn thế hệ trước (phát triển nhà sinh vật đưa ra vào khoảng năm hơn, hoàn thiện hơn). 1950. S. Fraser là người đầu tiên đưa ra II. NỘI DUNG sự tương đồng giữa quá trình tiến hóa Tiến hoá tự nhiên được quy định của sinh vật và chương trình máy tính giả duy trì nhờ hai quá trình cơ bản: sinh sản tưởng về thuật giải di truyền. J. H. và chọn lọc tự nhiên. Trong quá trình tiến Holland là người triển khai ý tưởng và hoá tự nhiên các cá thể mới luôn được phương thức giải quyết vấn đề dựa trên sinh ra để bổ sung, thay thế thế hệ cũ. Cá sự tiến hoá của con người. thể nào phát triển hơn, thích nghi hơn, Với tập sách xuất bản năm 1975 của thích ứng hơn với môi trường sẽ có nhiều mình - “ Adaptation in natural and artificical khả năng tồn tại hơn. Cả thể mới sinh ra systems ” - là tập sách đầu tiên đề cập đến trong quá trình tiến hoá có thể mang lĩnh vực này, J. H. Holland được xem là cha những tính trạng của cha mẹ (di truyền), đẻ của thuật giải di truyền. cũng có thể mang những tính trạng hoàn J. H. Holland và các đồng nghiệp toàn mới (đột biến) và chọn lọc tự nhiên. của ông ở trường đại học Michigan đã Cách tiếp cận giải quyết vấn đề - bài không ngừng phát triển và tạo nên cơ sở toán bằng thuật giải di truyền, theo đề lý thuyết vững chắc cho thuật giải di xuất ban đầu của J. H. Holland, bài toán truyền. Thuật giải di truyền được ứng sẽ được mã hoá thành các chuỗi bit với dụng trong nhiều lĩnh vực khác nhau, chiều dài cố định. Nên một lời giải tương trong đó thích hợp nhất là ứng dụng tìm ứng cũng biểu diễn bằng một chuỗi bit. kiếm giải pháp tối ưu. Trong thuật giải di truyền, ta gọi các lời Thuật giải di truyền hoạt động dựa giải là cá thể và chuỗi bit này được gọi là trên sự mô phỏng quá trình thích nghi và mã gen của cá thể . tiến hoá của tự nhiên trong điều kiện Trong thuật giải di truyền các quy định sẵn môi trường. Mục tiêu của thuật ngữ gen, cá thể, lời giải được sử thuật giải di truyền không nhằm đưa ra dụng lẫn lộn với ý nghĩa giống nhau. 2.1. Tìm hiểu thuật giải di truyền Cho bảng quyết định Dt = trong đó: U = { x1 , x2 ,..., xN } Tập thuộc tính quyết định : D = {d} chỉ có một thuộc tính. A D Thuộc tính d có r(d) giá trị. Khi đó, quan hệ bất khả phân IND(d) tách U thành r(d) lớp quyết định.  Với mọi a A , quan hệ tương tự Ra trên Va: x, y U : a x Ra a y với t(a) S a x, y t a 0,1 , gọi là giá trị ngưỡng tương tự của thuộc tính a, và : S a x, y d a x ,a y 1 d max Trong đó : o d a x , a y : khoảng cách giữa hai giá trị thuộc tính a(x) và a(y). o dmax : khoảng cách lớn nhất có thể giữa hai giá trị thuộc tính a(x)  Quan hệ dung sai ( tương tự ) A trên U : x, y U : x AY Với t(A) S A x, y t A 0,1 , gọi là giá trị ngưỡng tương tự của tập A. Và : S A x, y 1 A S a x, y a A Vấn đề đặt ra là tối ưu các giá trị ngưỡng tương tự t(A), t(a), a A theo yêu cầu: “ Nếu các đối tượng có quan hệ dung sai với nhau thi chúng cùng nằm trong một lớp càng nhiều càng tốt Nếu các đối tượng cùng nằm trong một lớp thì chúng có quan hệ dung sai với nhau càng nhiều càng tốt ”. Bài toán đặc tả như sau : Input : DT D Output : t A U, A D,V , f d ;A D t a :a A Ta giải bài toán bằng cách sử dụng thuật giải di truyền. Để thực hiện điều này, đầu tiên ta tìm hiểu cơ chế thực hiện thuật giải di truyền, sau đó vận dụng vào việc xác định giá trị ngưỡng tương tự tối ưu. Ý tưởng của thật giải di truyền như sau: - Đầu tiên, phát sinh ngẫu nhiên nhiều cá thể, gọi là quần thể ban đầu. - Đánh giá độ thích nghi của các cá thể. -Thực hiện các phương thức tiến hoá để tạo ra các quần thể mới tốt hơn (có độ thích nghi cao hơn). Như vậy, thuật giải di truyền là phương pháp tìm kiếm ngẫu nhiên được định hướng bởi số thích nghi. Thuật giải di truyền không chắc lúc nào cũng tìm được giải pháp tối ưu, nhưng chắc là trong thời gian cho phép, thuật giải di truyền cung cấp các giải pháp tốt nhất cho vấn đề. 2.1.1. Hàm thích nghi ( Fitness): Khả năng chọn lọc vào quá trình sinh sản quần thể kế tiếp phụ thuộc vào giá trị thích nghi của các cá thể trong quần thể. Các cá thể có độ thích nghi cao thì xác xuất được chọn sẽ lớn và ngược lại. Để tính giá trị thích nghi ta dựa vào một hàm, gọi là hàm thích nghi. Hàm thích nghi được xây dựng từ hàm mục tiêu của bài toán. Hàm mục tiêu (được xác định ban đầu) chỉ độ tốt của các cá thể. Độ tốt của một cá thể chỉ là cơ sở để xác định tính thích nghi của cá thể đó. Chỉ đơn giản vì cá thể tốt nhất ở thế hệ trước vẫn có khả năng bị kẹt trong các thế hệ sau và cá thẻ chưa tốt ở thế hệ trước vẫn có thê tiềm tàng khả năng dẫn đến lời giải tối ưu. Thông thường độ thích nghi của cá thể cũng là xác xuất để cá thể đó được chọn lọc hay lai ghép khi thực hiên tạo ra thế hệ kế tiếp. Có nhiều phương pháp xác định độ thích nghi của cá thể, chẳng hạn như các phương pháp sau : *) Phương thức Tạo Sinh (Preprodution) và Chọn ( Select) Phép tạo sinh là quá trình các cá thể được sao chép dựa trên độ thích nghi của nó. Cá thể nào có độ thích nghi cao thì xác suất được chọn vào quá trình sinh sản thế hệ kế tiếp sẽ lớn hơn. Điều đó không có nghĩa những cá thể có độ thích nghi thấp không được chọn. Có nhiều quy tắc chọn, ở đây ta tìm hiểu quy tắc chọn theo ban Roulete. Đây là nguyên tắc chọn lọc dựa theo hoạt động của bàn Roulete. Mỗi cá thể sẽ chiếm một cung trên bàn Roulete. Cá thể có độ thích nghi càng cao thì góc tương ứng với cung đó càng lớn. Việc chọn lọc theo bàn Roulete được tiến hành như sau : - Sắp xếp các cá thể theo độ thích nghi giảm dần (có thể không cần sắp xếp). - Lần lượt đặt giá trị thích nghi của các cá thể kề nhau trên cung một đoạn [0,1]. Như vậy mỗi cá thể sẽ chiếm một đoạn con trong đoạn [0,1]. Để chọn một cá thể, ta phát sinh một số ngẫu nhiên p trên đoạn [0,1]. Giá trị của p nằm trong khoảng con nào thì cá thể chiếm khoảng con đó sẽ được chọn. Còn có nhiều quy tắc chọn lọc khác như: quy tắc chọn lọc xén ( xác định bao nhiêu phần trăm cá thể tốt nhất trong quần thể sẽ được chọn), quy tắc chọn lọc theo kiểu rải, quy tắc chọn lọc cục bộ, quy tắc chọn lọc nhiều lần,... *) Lai ghép (CrossOver): Phép lai ghép là quá trình hình thành các cá thể mới trên cơ sở những cá thể cha mẹ. Có nhiều quy tắc lai ghép, đơn giản nhất là quy tắc lai ghép đơn điểm. Lấy hai cá thể cha mẹ A và B từ tập các cá thể đã được chọn lọc theo phương pháp chọn đã nêu ở trên. Phát sinh ngẫu nhiên một số tự nhiên k nằm trong đoạn [1,N-1] với N là chiều dài của gen. Điểm Ví dụ : ( biểu diễn gen bằng chuỗi nhị phân) A 001101 B 110101 k 2 A 000101 ( lai ghép tại vị trí k = 2) B 111101 Quy tắc lai ghép đa điểm là một dạng tổng quát của lai ghép đơn điểm. Trong lai ghép đa điểm, thay vì chỉ chọn một điểm lai ghép, ta chọn nhiều điểm lai ghép k1, k2 ,..., kn . n điểm lai Ví dụ: A B 001101 110101 k này chia gen của hai cá thể cha mẹ A thành A1A2 và B1B2. Lai ghép đơn điểm tạo ra hai cá thể mới có gen là A1B2 và B1A2. Phép lai xảy ra với xác suất lai plai cho trước. k 1 1, k 2 3, k 3 5 ghép này sẽ chia gen của hai cá thể cha mẹ A, B thành n +1 đoạn. Hai gen mới sẽ được tạo ra theo cách : các đoạn ở vị trí lẻ được giữ nguyên, các đoạn ở vị trí chẵn được hoán chuyển với nhau. A' B' 010101 101101 ( lai ghép tại vị trí k1= 1, k2= 3, k3= 5) Còn một quy tắc lai ghép khác như mặt nạ, quy tắc tạo sinh đường ... *) Đột biến ( mutation) Trong quá trình thực hiện thuật giải Đột biến là hiện tượng cá thể con di truyền phải luôn duy trì một quần thể mang một số tính trạng không có trong có tính đa dạng. Tính đa dạng thể hiện gen di truyền của cha mẹ. Phép đột biến trong quần thể không chỉ gồm những cá chỉ được phép xảy ra với xác suất thấp p thể có độ thích nghi cao sẽ chiếm tỉ lệ nhiều hơn do quy tắc chọn lọc quy định. độtbiến cho trước ( hoặc có thể lấy p độtbiến = 1/N với N là chiều dài gen cá thể). Đột Quá trình sinh sản (lai ghép, đột biến) biến có thể xảy ra tại một hay nhiều nhằm tạo ra những cá thể có gen mới. Cá thành phần gen nhưng do xác suất đột thể mới có thể có độ thích nghi cao hơn biến thấp nên người ta chỉ cho đột biến hoặc thấp hơn cá thể cha mẹ. Chính điều trên một thành phần gen là tối đa. đó tạo nên tính đa dạng của quần thể. Khi đó phép đột biến thực hiện 2.2. Mô tả thuật giải di truyền : như sau : phát sinh ngẫu nhiên một số Thuật giải di truyền bao gồm các thực k nằm trong khoảng [1,N] với N thành phần chính: là chiều dài của gen theo một công - Cách khởi tạo quần thể ban đầu. thức đột biến cho trước. - Hàm đánh giá độ thích nghi của các cá thể. Nhận xét: - Các phương thức tiến hoá.... Thuật giải di truyền mô tả như sau: Bắt đầu t = 0; Khởi tạo P( t); Tính độ thích nghi cho các cá thể thuộc P( t ); Khi ( điều kiện dừng chưa thoả) lặp Bắt đầu t = t + 1; Chọn lọc P(t) từ P( t - 1); Tính độ thích nghi cho các cá thể thuộc P(t); Kết thúc 2.3. Cơ chế thực hiện thuật giải di truyền -Tại thời điểm ban đầu ( t = 0) ta khởi tạo quần thể P(t) (gọi là quần thể ban đầu): phát sinh một số lượng lớn, hữu hạn các cá thể có gen ngẫu nhiên. Sau đó dựa vào một hàm số mà ta gọi là hàm thích nghi để xác định độ thích nghi các cá thể. Do phát sinh ngẫu nhiên nên tính thích nghi của cá thể trong quần thể không xác định. - Để cải thiện tính thích nghi của quẩn thể, ta tạo ra các quần thể mới. Từ thế hệ hiện tại, ta dùng các thao tác sau để tạo ra các thế hệ sau có tính thích nghi tốt hơn: + Đầu tiên là sao chép nguyên các cá thể có độ thích nghi cao từ thế hệ hiện tại đưa sang thế hệ kế tiếp bằng phương thức chọn, để đảm bảo tính thích nghi của thế hệ sau luôn ở mức hợp lý. Phương thức này thực hiện theo nguyên tắc cá thể có độ thích nghi cao thì xác suất chọn sẽ lớn và ngược lại. Nhưng điều này không có nghĩa là những cá thể có độ thích nghi thấp không được chọn. + Thao tác thứ hai là tạo ra các cá thể mới từ các cá thể được chọn có độ thích nghi cao từ thế hệ hiện tại bằng cách thực hiện kết hợp các phương thức lai ghép và đột biến. * Phép lai ghép thực hiện bằng cách kết hợp hai cá thể cha mẹ theo một quy tắc để tạo ra hai cá thể con mới. Phép lai ghép diễn ra theo một xác suất lai cho trước. Phương thức chọn và lai ghép cho phép tạo ra các thế hệ sau : * Trong trường hợp quần thể phát sinh ngẫu nhiên ban đầu có đặc tính chưa phong phú hay chưa phù hợp. Ta tạo ra quần thể mới chỉ bằng thao tác chọn lọc và lai ghép thì các cá thể lời giải trong quần thể sẽ chỉ tập trung trong một khoảng giới hạn mà không tiến tới được lời giải tối ưu. Để giải quyết vấn đề trên ta phải thực hiện phương thức đột biến. Tuy nhiên phép đột biến chỉ được phép diễn ra với xác suất thấp vì phép đột biến có thể làm mất đi những cá thể được chọn lọc và lai ghép có độ thích nghi cao. - Thế hệ mới sẽ được xử lí như thế hệ trước đó. Việc xử lý sẽ dừng khi đạt được lời giải tối ưu hoặc thời gian cho phép kết thúc 2.4. Các bước thực hiện quan trọng trong thuật giải di truyền Giải quyết bài toán bằng thuật giải di truyền, cần phải thực hiện các bước quan trọng sau đây : Bước 1: Chọn mô hình cho giải pháp của bài toán: Chọn một số tượng trưng cho toàn bộ các giải pháp có thể có của bài toán. Bước 2: Chỉ định cho mỗi giải pháp một ký hiệu. Ký hiệu có thể là một dãy các số nhị phân, hoặc dãy số thập phân, dãy các chữ, hoặc dãy hỗn hợp các số và chữ. Thường dùng nhất là dãy các số nhị phân. Bước 3: Tìm hàm số thích nghi và tính độ thích nghi của các cá thể. Bước 4: Dựa vào độ thích nghi của Xác định độ thích nghi các cá thể các cá thể để thực hiện việc tạo sinh và chọn lọc, thực hiện các phương thức tiến hoá như lai ghép, đột biến . Bước 5: Tính độ thích nghi của các cá thể mới. Loại bỏ các cá thể kém nhất và chỉ giữ lại các cá thể tương đối tốt. Bước 6: Nếu chưa tìm được lời giải (cá thể) tối ưu hay tương đối tối ưu hay chưa hết thời gian cho phép thì quay lại bước 4. Bước 7: Tìm được lời giải tối ưu hay hết thời gian cho phép thì báo cáo kết quả, kết thúc thuật giải . Sơ đồ minh họa quá trình tối ưu của thuật giải di truyền: Có cá thể nào đạt lời giải tối ưu chưa? Trình bày lời giải Tạo quần thể ban đầu Chọn lọc Lai ghép Bắt đầu Xây dựng quần thể mới Đột biến Xây dựng thế hệ kế tiếp 2.5. Áp dụng thuật giải di truyền xác định ngưỡng tương tự tối ưu Cũng như các bài toán tối ưu mà thuật giải di truyền giải quyết, ta cần giải quyết các vấn đề sau: - Biểu diễn các biến của vấn đề. - Tạo quần thể ban đầu. - Xác định hàm thích nghi của vấn đề, xác định giá trị thích nghi của các cá thể. - Thực hiện các phương thức tiến hoá. Mô tả thuật giải; 1. Khởi tạo : - Đọc bảng quyết định; - Định nghĩa độ đo tương tự; - Tạo quần thể ban đầu: Lấy các ngưỡng ban đầu trong khoảng [0,1]; - Tính độ thích nghi của quần thể ban đầu; 2. Tiến hành thuật giải di truyền while ( not( điều kiện kết thúc )) {Tạo sinh; Lai ghép; Đột biến; Tính hàm thích nghi của quần thể mới:} 3. Xác định giá trị ngưỡng tương tự tối ưu. III. KẾT LUẬN Khi sử dụng giá trị ngưỡng tối ưu tìm được bằng thuật giải di truyền để làm đầu vào cho thuật giải phân lớp, chưa chắc ta đã có kết quả phân lớp tốt theo nghĩa có ít phân tử không phân lớp được. Tuy nhiên bằng cách xử lý tiếp theo là chọn giá trị lớn nhất cho mỗi thành phần trong bộ ngưỡng tối ưu trong nhiều lần thực hiện, kết quả thu được thường tốt hơn. . 3. Hoàng Kiếm - Lê Hoàng Thái (2000), "Thuật Giải Di Truyền- Cách Giải Tự Nhiên Các Bài Toán Trên Máy Tính", NXB Giáo Dục Hà Nội. Tài liệu tiếng Anh: 4. Han Yin Shi, A clasification study of Ruogh Sets generalization, A thesis Master of science in Lakehead University 2004 5. Z. Pawlak, Rough Sets - Theorycal Aspect of Reasoning about Data, Kluwer Akademic publishers 1991 6. J. H. Holland, "Adaptation in natural and artifical systems" 1975 TÀI LIỆU THAM KHẢO Tài liệu tiếng việt: 1. (2011), Cơ sở dữ liệu Quan hệ & Ứng dụng . 2. Hoàng Kiếm (2001), ", Tập 2, NXB 7
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.