Tài liệu ứng dụng của tập thô tolerant trong phân loại dữ liệu môn cơ sở tri thức và ứng dụng

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN LỚP CAO HỌC QUA MẠNG – KHÓA 6 BÀI THU HOẠCH MÔN HỌC: CƠ SỞ TRI THỨC ỨNG DỤNG CỦA TẬP THÔ TOLERANT TRONG PHÂN LOẠI DỮ LIỆU Giảng viên: GS TSKH Hoàng Kiếm Sinh viên thực hiện: Nguyễn Hoàng Hạc MSHV: CH1101081 TP. HCM, NĂM 2012 LỜI CÁM ƠN!  Tôi xin trân trọng dành nhưng lời cảm ơn đầu tiên tới GS TSKH Hoàng Kiếm, người trực tiếp hướng dẫn và giảng dạy môn Công nghệ tri thức này. Xin chân thành cám ơn các thầy cô khác trong trường Đại Học Công nghệ Thông tin Thành phố Hồ Chí Minh. Xin gởi lời cảm tới các bạn và những người đã hổ trợ và tạo điều kiện cho tôi hoàn thành đề tài này. Một lần nữa, xin chân thành cảm ơn mọi người bằng cả tấm lòng!. Học viên thực hiện: Nguyễn Hoàng Hạc 2 MỤC LỤC MỞ ĐẦU....................................................................................................................4 Chương 1 TẬP THÔ TOLERANT.............................................................................5 1.1 Giới thiệu.........................................................................................................5 1.2 Tập thô tolerant................................................................................................7 1.3 Quan hệ tương tự.............................................................................................8 1.4 Tập xấp xỉ trên và tập xấp xỉ dưới...................................................................9 1.5 Độ đo tương tự và ngưỡng tương tự................................................................9 Chương 2 XÁC ĐỊNH NGƯỠNG TƯƠNG TỰ BẰNG THUẬT GIẢI DI TRUYỀN.11 2.1 Giải thuật chung cho thuật giải di truyền.......................................................11 2.2 Biểu diễn nhiễm sắc thể cho thuật giải di truyền...........................................13 2.3 Khởi tạo quần thể ban đầu.............................................................................13 2.4 Hàm thích nghi .............................................................................................13 2.5 Các phép toán di truyền ................................................................................16 2.5.1 Phép chọn lọc tái sinh ............................................................................16 2.5.2 Phép lai ghép .........................................................................................18 2.5.3 Phép đột biến .........................................................................................18 Chương 3 PHÂN LOẠI DỮ LIỆU DỰA TRÊN TẬP THÔ TOLERANT..................20 3.1 Giai đoạn 1: dùng xấp xỉ dưới.......................................................................21 3.2 Giai đoạn 2: dùng xấp xỉ trên.........................................................................21 3.3 Ứng dụng tập thô tolerant trong phân loại dữ liệu IRIS.................................24 3.3.1 Bộ dữ liệu IRIS.......................................................................................24 3.3.2 Xác định tập thô tolerant.........................................................................26 3.3.3 Phân loại dữ liệu.....................................................................................27 3.3.4 So sánh kết quả phân loại với các phương pháp phân loại khác............30 3.4 Kết luận.........................................................................................................31 Chương 4 CÀI ĐẶT VÀ KẾT QUẢ THỰC HIỆN....................................................33 4.1 Cấu trúc dữ liệu.............................................................................................33 4.1.1 Lớp CUniverse........................................................................................33 4.1.2 Lớp CObjects..........................................................................................34 4.1.3 Lớp CChromosome.................................................................................35 4.1.4 Lớp CSimilarity......................................................................................36 4.1.5 Lớp CApproximation..............................................................................37 4.1.6 Lớp CTolerant........................................................................................37 4.2 Thử nghiệm với bộ dữ liệu IRIS....................................................................38 4.2.1 Bộ dữ liệu IRIS.......................................................................................38 4.2.2 Các tham số cho chương trình................................................................38 4.2.3 Kết quả thực hiện phân loại....................................................................39 4.3 Thử nghiệm với bộ dữ liệu gồm 25 ký tự......................................................39 4.3.1 Bộ dữ liệu của 25 ký tự...........................................................................39 4.3.2 Các tham số cho chương trình................................................................42 4.3.3 Kết quả thực hiện....................................................................................42 4.4 Đánh giá........................................................................................................43 3 MỞ ĐẦU Ngày nay, cùng với sự phát triển không ngừng của Công nghệ thông tin kèm theo đó là dữ liệu về thế giới thực được lưu trữ nhiều hơn. Với nguồn dữ liệu được lưu trữ ngày càng lớn làm cho việc phân loại dữ liệu trở nên hết sức khó khăn, đôi khi là bất khả thi. Để thực hiện việc phân loại dữ liệu, các nhà Trí tuệ nhân tạo đã đưa ra các phương pháp phân loại như: thuật toán Quinland, cây định danh, thuật toán Apriori, thuật toán Apriori Tid…. Nhưng các phương pháp này có nhược điểm không phân loại được phần dữ liệu mơ hồ (không chắn chắn, không xác định). Sau này, các phương pháp mới hơn được đưa ra như: Back-propagation neural networks (BPNN), the Object function-based unsupervised neural networks (OFUNN), Fuzzy C-means (FCM),…giải quyết vấn đề phân loại dữ liệu mơ hồ nhưng với độ chính xác không cao và thời gian xử lý khá lâu. Đề tài “Ứng dụng của tập thô tolerant trong phân loại dữ liệu” tập trung chủ yếu vào lý thuyết tập thô, tập thô tolerant, các bài toán sử dụng tập thô phân loại dữ liệu và ứng dụng của tập thô tolerant trong phân loại dữ liệu. Đây là phương pháp thực hiện phân loại dữ liệu chính xác hơn và thời gian xử lý nhanh hơn so với các phương pháp đã đưa ra trước đó. 4 Chương 1 TẬP THÔ TOLERANT 1.1 Giới thiệu Vấn đề của việc phân loại dữ liệu đó là phân chia một không gian dữ liệu n vào trong các lớp và sau khi xác định một điểm xn tới một điểm thuộc các lớp khác. Nhiều ứng dụng đã được tìm thấy trong các ngành khoa học như: nhận dạng dấu vân tay, phần phân loại trong sự quan sát của máy tính, phân tích máu,…và hơn thế nữa. Các phương pháp phân loại dữ liệu được phân loại thành 3 cách khác nhau: Phân loại dữ liệu thống kê, phân loại dữ liệu cú pháp và phân loại dữ liệu mạng nơron cơ sở (neural network-based). Một vài thuộc tính đã có bởi quan niệm của người phân loại dữ liệu được đề cập như sau: 1. Thích nghi tức thì (On-line adaptation): Chương trình phân loại dữ liệu cần học những lớp mới và tinh chế những lớp đang tồn tại nhanh chóng mà không phá hủy thông tin của lớp cũ. 2. Phân chia không định hướng (Nonlinear separation): Chương trình phân loại dữ liệu cần xây dựng những ranh giới quyết định đó là những lớp ngăn cách giữa hình dạng và kích thước 3. Các lớp chồng chéo (Overlapping classes): Chương trình phân loại dữ liệu cần có khả năng định dạng một ranh giới quyết định đó là việc giảm tối thiểu số lượng lớp không được phân loại đối với tất cả các lớp chồng chéo nhau. 4. Thời gian huấn luyện (Training time): Chương trình phân loại dữ liệu cần có khoảng thời gian học ngắn cho việc tạo những ranh giới quyết định 5. Các quyết định dễ và khó (Soft and hard decisions): Chương trình phân loại dữ liệu cần cung cấp cả hai loại quyết định phân loại dễ và khó. 6. Kiểm tra và xác nhận (Verification and validation): 5 Chương trình phân loại dữ liệu cần có kỹ thuật để kiểm tra và xác nhận lại sự thực hiện của chương trình bằng nhiều cách. 7. Tham số điều chỉnh (Tuning parameters): Chương trình phân loại dữ liệu nên có càng nhiều tham số điều chỉnh hệ thống càng tốt. 8. Sự phân loại không giới hạn (Nonparametric classification): Chương trình phân loại dữ liệu sẽ hoạt động tối ưu mà không cần biết đến sự phân phối dữ liệu bên dưới. Như đã đề cập ở trên, nhiều nhà nghiên cứu đã từng thực hiện bằng nhiều cách khác nhau. Carpenter và Grossberg đã phát triển nhanh chóng và đáng tin cậy các bộ mẫu tuần tự của hệ thống gọi là lý thuyết Fuzzy Adaptive Resonance (ART) nó liên kết logic mờ với ART1, Lin và Lee giới thiệu tổng quát mạng nơron cho việc điều khiển logich mờ và các hệ thống ra quyết định nó có thể thành lập các luật logich mờ và tối ưu chức năng nhập / xuất của các thành viên. Simpson đã phát triển sự phân loại min_max không rõ ràng của mạng nơron nó sử dụng các tập mờ như là những lớp mẫu, việc học trong mạng nơron được thực hiện tại một nơi nhất định và sự điều chỉnh hyberboxes trong không gian mẫu. Bởi vì, các lý thuyết phân loại trên có một cấu trúc kết nối giữa logic mờ và mạng nơron nên họ dự tính sẽ gặp những khó khăn giống như mạng nơron như sau:  Khả năng có giải pháp không hội tụ bởi vì sự chọn lựa sai các giá trị trọng số ban đầu.  Có liên quan đến thời gian học dài.  Khả năng có những giải pháp không tối ưu vì những vấn đề cục bộ. Gần đây Banzan đề xuất hai ứng dụng của logich cho việc phân loại các đối tượng bằng cách sử dụng multi-modal logics cho việc tự động lấy các đặc trưng ban đầu và sử dụng sự phương pháp qui nạp của tập thô để khám phá các tập đặc trưng tối ưu nhất đối với chất lượng của việc phân loại. Phương pháp của họ nhấn mạnh sự tối ưu các lựa chọn của những thuộc tính liên quan từ việc linh động thu nhỏ. Nhưng số lượng những đối tượng không thể phân biệt được thì quá hạn chế để xác 6 định sự tương tự của nó, bởi vì sự giao nhau không luôn luôn đúng trong trường hợp của vấn đề phân loại mẫu. Nguyễn đề xuất việc sử dụng số lượng mối quan hệ tolerant của các đối tượng cho việc phân loại mẫu. Nhưng phương pháp này không đề cập như thế nào xác định ngưỡng khởi tạo tối ưu của các thuộc tính cho việc phân loại tốt nhất của một vấn đề được đưa ra. Những yêu cầu đã gặp ở trên đã cho ra ý tưởng của người phân loại càng nhiều càng tốt khắc phục một số trở ngại của các phương pháp đã đề xuất trước đó, đó là lý do cho việc đề xuất một phương pháp phân loại mới dựa trên tập thô tolerant. 1.2 Tập thô tolerant Tập thô được Z. Pawlak giới thiệu vào đầu thập niên 80 là công cụ tính toán mới giải quyết tính gần đúng và không chắc chắn trong các lĩnh vực: máy học, thu nhận tri thức, phân tích quyết định, khám phá tri thức từ cơ sở dữ liệu, lập luận qui nạp và nhận dạng mẫu. Khi một số đối tượng không phân biệt từ những đối tượng khác với các thuộc tính đã cho có một mối quan hệ không phân I biệt thoả mãn các tính chất: Phản xạ (Reflexive): xIx Đối xứng (Symmetric): xIy  yIx Bắc cầu (Transitive): xIy yIz  xIz Với x, y và z là các đối tượng trong vũ trụ của đối tượng U. Vì vậy mối quan hệ không phân biệt là mối quan hệ tương đương nó sẽ phân chia tập U vào những lớp tương đương. Tuy nhiên, trong thực tế nhiều bài toán phân lớp không phải lúc nào tính chất bắc cầu cũng được thoả mãn. Ví dụ: xét bài toán phân lớp các điểm gần biên sau: biên 1 3 2 7 Rõ ràng, điểm 1 gần điểm 2 và điểm 2 gầ điểm 3, nhưng điểm 1 không gần điểm 3. Trong trường hợp này tính chất bắc cầu không còn đúng. Bởi vì 2 đối tượng dữ liệu x và z không thể được bảo đảm trong cùng một lớp thậm chí khi một cặp dữ liệu x và y được chứa trong cùng một lớp và cặp dữ liệu y và z cũng được chứa trong cùng một lớp thì chưa hẳn x và z thuộc về cùng một lớp (tính chất bắc cầu không thoả mãn). Vì vậy, tập thô Tolerant mở rộng quan hệ không phân biệt thành quan hệ tolerant (quan hệ tương tự) cho phù hợp với các bài toán phân lớp mà quan hệ giữa các đối tượng chỉ thoả mãn hai tính chất: phản xạ và đối xứng. 1.3 Quan hệ tương tự Cho A = (U, Ad) là một bảng quyết định. U là một tập gồm các yếu tố (các đối tượng, các mẫu). A là tập những thuộc tính điều kiện, aA tập những giá trị của thuộc tính a là Va, và {d} là một tập quyết định với d = {1, 2, …, r(d)}, r(d) là số các lớp quyết định. Cho A = {Ra: Ra  Va x Va  aA} là một tập của mối quan hệ tolerant. Mỗi mối quan hệ tolerant thoả mãn: Phản xạ (Reflexive):  v1  Va , v1Rav1, Đối xứng (Symmetric): v1Rav2  v2 Rav1 Với v1 và v2 là các thuộc tính giá trị trong Va. Hai đối tượng x và y là tương tự nhau đối với thuộc tính a. Khi giá trị a(x) và a(y) thoả mãn a(x)Raa(y). Hơn nữa, chúng ta nói hai đối tượng x và y là tương tự đối với trong toàn bộ thuộc tính A khi nó thoả mãn mối quan hệ tolerant với việc thừa nhận tất cả các thuộc tính nghĩa là: a  A, a(x)Raa(y) Một tập thô tolerant (tolerance rough set) TS(x) của một đối tượng x được định nghĩa bởi một tập của tất cả các đối tượng có mối quan hệ tolerant với đối tượng x đối với tất cả các thuộc tính như sau: 8 TS(x) = {yU | xAy} 1.4 Tập xấp xỉ trên và tập xấp xỉ dưới Xấp xỉ dưới A (Y) và xấp xỉ trên  A (Y) của tập YU nó có mối quan hệ tolerant đối với tất cả cá thuộc tính của A được định nghĩa như sau: A A (Y) = U {TS(x) | TS(x)Y} (Y) = U {TS(x) | TS(x)Y  } xU xU Ý nghĩa của 2 tập xấp xỉ trong mối quan hệ tolerant là như nhau đó là mối quan hệ tương tự. Để thành lập một mối quan hệ tolerant giữa dữ liệu với nhau chúng ta cần xác định một độ đo tương tự, nó xác định số lượng tính chặt chẽ giữa những giá trị thuộc tính của các đối tượng. 1.5 Độ đo tương tự và ngưỡng tương tự Để xác định độ đo tương tự Sa(x,y) đối với thuộc tính a giữa hai đối tượng x và y. Hai đối tượng là tương tự với thuộc tính a khi Sa(x,y)  t(a), với t(a) là một ngưỡng tương tự khởi tạo của thuộc tính a, giá trị của a nằm trong khoảng t(a)[0,1]. Vì vậy, chúng ta có thể liên hệ mối quan hệ tolerant với độ đo tương tự như sau: a(x)Raa(y)  Sa(a,y)  t(a) Trong vấn đề phân loại dữ liệu, thông thường sử dụng độ đo tương tự được dựa trên cơ sở một khoảng cách: Sa(x,y) = 1  d ( a ( x), a ( y )) d max Với dmax là giá trị khoảng cách tối đa giữa hai giá trị thuộc tính a(x) và a(y). Sự chọn lựa hàm khoảng cách phụ thuộc vào loại ứng dụng. Trong trường hợp này, chúng ta chọn sự khác nhau hoàn toàn giữa các giá trị thuộc tính như sau: d(a(x),a(y))=|a(x) - a(y)|. 9 Tiếp theo, chúng ta có thể mở rộng độ đo tương tự SA(x,y) giữa hai đối tượng x và y đối với tất cả các thuộc tính bởi một phép tính trung bình của các độ đo tương tự của tất cả các thuộc tính: 1 SA(x,y) = A S a ( x, y ) aA Với |A| là số các thuộc tính trong A. Trong trường hợp xét tất cả các thuộc tính của A cùng lúc, chúng ta có thể liên hệ mối quan hệ tolerant với độ đo tượng tự như sau: xAy  SA(x,y)  t(A) Với t(A)[0,1] là một ngưỡng tương tự khởi tạo cho sự phân loại dữ liệu dựa trên tất cả các thuộc tính A. Vấn đề ở đây là làm thế nào để xác định ngưỡng một cách tối ưu có thể. Bởi lẻ ngưỡng tương tự ảnh hưởng trực tiếp đến quan hệ tolerant từ đó ảnh hưởng đến việc xác định các tập thô tolerant, và kết quả phân lớp sau này. Nói cách khác việc xác định ngưỡng đóng vai trò rất quan trọng đến kết quả phân lớp như sẽ thấy ở các phần sau. Có nhiều cách để xác định bộ ngưỡng tối ưu như: vét cạn, heuristic, thuật giải di truyền…. Trong đó thuật giải di truyền thích hợp nhất. Bởi vì không gian tìm kiếm tương đối lớn, các miền giá trị của ngưỡng liên tục do đó chúng ta sử dụng thuật giải di truyền để giải quyết vấn đề này. Lúc này hàm thích nghi sẽ được xây dựng sao cho kết quả phân lớp là tốt nhất. 10 Chương 2 XÁC ĐỊNH NGƯỠNG TƯƠNG TỰ BẰNG THUẬT GIẢI DI TRUYỀN Thuật giải di truyền (GA - Genetic Algorithm) hình thành dựa trên quan niệm cho rằng quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Quan niệm này có thể xem như một tiền đề đúng, không chứng minh được, nhưng phù hợp với thực tế khách quan. Quá trình tiến hoá thể hiện tính tối ưu ở chổ, thế hệ sau bao giờ cũng tốt hơn (phát triển hơn, hoàn thiện hơn) thế hệ trước. Tiến hoá tự nhiên được duy trì nhờ hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hoá tự nhiên, các cá thể mới luôn được sinh ra để bổ sung thay thế thế hệ cũ. Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại. Cá thể nào không thích ứng được với môi trường sẽ bị đào thải. Sự thay đổi môi trường là động lực thúc đẩy quá trình tiến hoá. Ngược lại, tiến hoá cũng tác động trở lại góp phần làm thay đổi môi trường. Các cá thể mới sinh ra trong quá trình tiến hoá nhờ sự lai ghép ở thế hệ chamẹ. Một cá thể mới có thể mang những tính trạng của cha-mẹ (di truyền), cũng có thể mang những tính trạng hoàn toàn mới (đột biến). Di truyền và đột biến là hai cơ chế có vai trò quan trọng như nhau trong tiến trình tiến hoá, dù rằng đột biến với xác suất nhỏ hơn nhiều so với hiện tượng di truyền. Thuật giải di truyền là thuật toán lặp đi lặp lại khả năng thích ứng của quần thể cơ sở, sử dụng các phép toán di truyền (chọn lựa tái sinh, phép lai ghép và phép đột biến) dựa trên sự lựa chọn tự nhiên. Thuật giải di truyền đã được chứng minh là một phương pháp hữu dụng trong việc tìm kiếm, quan sát và máy học. Nó mã hoá một giải pháp tiềm tàng đến một vấn đề chi tiết trên một cấu trúc dữ liệu đơn giản giống nhiễm sắc thể và các phép toán liên kết. 2.1 Giải thuật chung cho thuật giải di truyền Thuật giải di truyền làm việc như sau: - Cho P là một quần thể của các nhiễm sắc thể |P|. 11 - P(0) là quần thể khởi tạo được phát sinh ngẫu nhiên. - P(t) là quần thể tại thời điểm t. - Quần thể mới P(t+1) được tạo ra bằng cách sử dụng một tập các toán tử phát sinh (tái sinh, lai ghép, đột biến) trên P(t). - Mỗi nhiễm sắc thể trong P(t+1) được tái sinh theo tỷ lệ giá trị thích nghi của nó tại thời điểm t. - Lai ghép là tổ hợp lại 2 nhiễm sắc thể từ việc cắt chúng ở những vị trí ngẫu nhiên và sự thay đổi những thông tin di truyền bằng cách ghép một hay nhiều đoạn gien của hai (hay nhiều) nhiễm sắc thể cha-mẹ với nhau. - Đột biến là hiện tượng cá thể con mang một (số) tính trạng không có trong mã di truền của cha-mẹ. Nói chung, hiệu quả của thuật giải di truyền là một quần thể mới được tạo và cho ra các giải pháp tốt hơn với các giá trị cao hơn của hàm thích nghi. Hình 3-1 là mã giả thể hiện cách làm việc của thuật giải di truyền. Begin t=0 Initialize P(t); Evaluate fitness functions in P(t); while ~(stop_condition) do Begin t=t+1; Select P(t) from P(t-1) Recombine chromosomes in P(t) Evaluate fitness functions in P(t) End End Hình 3-1 Thủ tục chung của thuật toán di truyền. Khi chúng ta sử dụng thuật giải di truyền để tìm một ngưỡng tương tự khởi tạo tốt nhất cho vấn đề phân loại dữ liệu. Chúng ta cần phải xem xét 5 vấn đề chính sau: 1. Lược đồ trình bày mối kết hợp của các nhiễm sắc thể cho việc phân loại. 2. Phương pháp tạo ra quần thể khởi tạo. 12 3. Hàm thích nghi cho các cá thể (nhiễm sắc thể). 4. Các toán tử phát sinh quần thể mới. 5. Tham số khởi tạo được cung cấp cho thuật giải di truyền. 2.2 Biểu diễn nhiễm sắc thể cho thuật giải di truyền Chúng ta sử dụng thuật giải di truyền để xác định các ngưỡng tương tự khởi tạo tối ưu nhất. Đầu vào là bảng A = (U, Ad) có độ đo sự tương tự Sa: VaxVa  [0,1] Đầu ra là một tập các ngưỡng tương tự khởi tạo tối ưu {t(A)  {t(a): aA}}. Như vậy, khi một đối tượng được thể hiện bằng n thuộc tính thì nhiễm sắc thể cho thuật giải di truyền bao gồm n+1 số thực liên tiếp của các điểm tương tự khởi tạo {t(a1), t(a2), …, t(an), t(A)}, với t(ai) / (i=1,2,…,n) thể hiện ngưỡng tương tự khởi tạo cho thuộc tính i và giá trị cuối cùng t(A) là ngưỡng tương tự khởi tạo xác định mối quan hệ tolerant khi tất cả các thuộc tính A được xem xét cùng lúc. Chúng ta chấp nhận một sự trình bày dạng số thực của các nhiễm sắc thể vì mỗi giá trị của gien trong nhiễm sắc thể là một số thực. 2.3 Khởi tạo quần thể ban đầu Các giá trị của gien khởi tạo trong nhiễm sắc thể có được bởi sự phát sinh n+1 số giá trị thực ngẫu nhiên trong khoảng [0.5, 1.0]. Lý do cho việc chọn khoảng [0.5,1.0] để khởi tạo các ngưỡng tương tự khởi tạo là hai đối tượng được xem là tương tự nhau khi giá trị tương tự khởi tạo giữa hai đối tượng tối thiểu lớn hơn 0.5. Chúng ta hoàn thành khởi tạo quần thể bằng cách lặp lại phép toán |P| ở trên nhiều lần. Khi đó |P| là kích thước của quần thể. 2.4 Hàm thích nghi 1 Trước khi xem xét hàm thích nghi cho việc xác định tốt nhất những ngưỡng tương tự khởi tạo, chúng ta xem xét một khái niệm của các mối kết hợp để diễn tả sự không phân biệt của các đối tượng. Khái niệm mối liên kết dựa trên một quan sát rất đơn giản đó là nếu xTS(y)  yTS(x) chúng ta có thể nói đó là mối liên kết giữa 1 Fitness function 13 hai đối tượng x và y. Từ đó, chúng ta xác định hai loại liên kết giữa hai đối tượng x và y như sau: x và y có mối liên kết tốt  xTS(y)  d(x) = d(y) x và y có mối liên kết xấu  xTS(y)  d(x)  d(y) Với d(x), d(y) là các quyết định tương ứng của hai lớp đối tượng x và y, chúng sẽ có mối liên kết tốt (hoặc xấu). Hình 3-2 minh hoạ hai loại của mối liên kết giữa các đối tượng. d1 d2 d3 Mối liên kết tốt Mối liên kết xấu Hình 3-2. Các mối liên kết tốt và mối liên kết xấu Khi chúng ta chọn hàm thích nghi cho việc xác định ngưỡng tương tự khởi tạo tối ưu chúng ta cần xem xét hai yêu cầu sau:  Nếu hai đối tượng x, yU có quan hệ tolerant thì chúng nằm trong cùng một lớp càng nhiều càng tốt.  Nếu hai đối tượng cùng nằm trong cùng một lớp thí chúng có quan hệ tolerant càng nhiều càng tốt. Đề cập yêu cầu thứ nhất, chúng ta cần xác định một đặc trưng xấp xỉ của sự phân loại   d A, nó biểu diễn tỷ lệ của tất cả quan hệ tolerant chính xác ( A- correctly) phân loại đối tượng. 14 Cho một tập của những đối tượng được chứa trong cùng một lớp Yi={xU / d(x) = di, i=1, 2, …, r(d)}, với r(d) là số các lớp quyết định. Xét tập thô tolerant TS(x) được chứa trong cùng lớp di, nghĩa là: {TS(x) | i TS(x)  Yi} Sự liên kết trong tập tolerant đối với tất cả các lớp đối tượng U được gọi là một vùng rõ ràng A của phân hoạch {Yi,i=1,2,…,r(d)} được định nghĩa như sau: r (d ) POS A , d    TS ( x ) / i TS(x)  Yi    A (Yi ) xU i 1 Chất lượng xấp xỉ của sự phân loại   d A, được xác định bởi tỷ số của tất cả A-corectly phân loại đối tượng từ U như sau:  A , d  card ( POS A , d  ) card U Như vậy, giá trị ngưỡng tương tự tăng lên, chất lượng xấp xỉ của việc phân loại   d A, sẽ được tăng lên làm cho kích thước của những tập tolerant giảm xuống. Do đó, sự thay đổi gồm cả những tập tolerant trong tập được chia {i } trở nên lớn hơn. Khi chúng ta chỉ xem xét chất lượng xấp xỉ của việc phân loại   d A, việc chúng ta tìm ngưỡng tương tự khởi tạo trở nên lớn hơn, bởi vì điều kiện là các yếu tố trong tập thô tolerant được chứa trong cùng một lớp do đó kết quả phân loại cho ra kích thước của các phần được chia trở nên nhỏ hơn. Đôi khi, kết quả phân loại làm cho phần được chia nhiều nhất chỉ chứa duy nhất một đối tượng đơn. Vì vậy, để thoả mãn yêu cầu thứ hai là các đối tượng được chứa trong cùng một lớp có quan hệ tolerant càng nhiều càng tốt. Với yêu cầu này chúng ta xác định tỷ lệ mối liên kết tốt là    d A, , xác định tỷ lệ các đối tượng nằm trong cùng một lớp có quan hệ với nhau trên tổng số các đối tượng trong cùng một lớp:   A , d   card  A    x, y  / d ( x) d ( y )  card   x, y  / d ( x) d ( y )  15 Bởi vì, giá trị ngưỡng tương tự khởi tạo tăng lên, tỉ lệ của các mối liên kết tốt   d A, giảm xuống, cho nên kích thước của các tập tolerant giảm xuống. Do đó, làm cho số lượng các mối liên kết tốt trở nên nhỏ hơn. Vì hai hệ số  dựa trên một tỷ lệ   d A,  d A, và    d A, làm việc ngược nhau. Nếu hàm thìch nghi chỉ thì quá trình tiến hoá có khuynh hướng làm cho kích thước các tập tolerant càng nhỏ càng tốt, và 1 là tốt nhất. Từ đó ta gặp phải vấn đề “phân mảnh lớp”, nghĩa là sẽ có nhiều lớp nhưng mỗi lớp chỉ có một ít đối tượng. Nếu hàm thích nghi chỉ dựa trên một tỷ lệ    d A, thì ngược lại ta sẽ được kết quả phân lớp chỉ tập trung vào một số các lớp nào đó. Do đó, vấn đề đặt ra là cần phải kết hợp hài hoà hai tỷ lệ này. Hàm thích nghi dựa trên việc kết hợp hai tỷ lệ này sẽ có dạng như sau: F   A  d   1    x  A  d  Với  và ( - 1) là các hằng số trọng lượng có thể được thay đổi theo mục đích phân loại. Ở đây, giới hạn thứ nhất là tạo một vài đối tượng có quan hệ tolerant được chứa trong cùng một lớp và giới hạn thứ hai là tạo các đối tượng trong cùng một lớp trở nên có quan hệ tolerant. 2.5 Các phép toán di truyền 2 Quần thể khởi tạo của ngưỡng tương tự khởi tạo được suy ra từ mối kết hợp của các phép toán phát sinh để tìm một tập ngưỡng tương tự khởi tạo tối ưu cho việc phân loại dữ liệu. Giải thích chi tiết về các phép toán phát sinh được sử dụng cho việc xác định các giá tri tương tự khởi tạo được đưa ra như sau: 2.5.1 Phép chọn lọc tái sinh 3 Chúng ta sử dụng một sự pha trộn của các phương pháp chọn lọc cho việc tái sinh các nhiễm sắc thể. Phương pháp chọn lọc đầu tiên là một nhiễm sắc thể tốt nhất (elitism) có hàm thích nghi cao nhất sẽ được đưa vào quần thể mới. 2 3 Genetic Operations Reproduction 16 Phương pháp chọn lọc thứ hai là phương pháp chọn lọc đấu loại k phần tử (k-tournament). Trong phương pháp này, một nhiễm sắc thể có hàm thích nghi tốt nhất trong số k nhiễm sắc thể được chọn ngẫu nhiên từ quần thể. Hai nhiễm sắc thể C1 và C2 có được từ việc lập lại thủ tục ở trên liên tiếp tạo ra một nhiễm sắc thể mới Cc+m bằng cách sử dụng các phép toán lai ghép và đột biến sẽ được giải thích sau. Thủ tục tái sinh ở trên được lập lại nhiều lần bằng pSelect  |P|, với |P| là kích thước quần thể. Cuối cùng, phần còn lại của tập quần thể mới được làm đầy bằng cách phát sinh ngẫu nhiên các nhiễm sắc thể. Hình 3-3 cho thấy một phương pháp lai ghép tái sinh dựa trên một hổn hợp của ba phương pháp tái sinh khác nhau. Hình 3-3: Lược đồ phương pháp chọn lọc tái sinh. 17 2.5.2 Phép lai ghép 4 Lai ghép giữa hai nhiễm sắc thể đã chọn C1 và C2 được thực hiện như sau: Cho các ngưỡng tương tự khởi tạo thứ i của 2 nhiễm sắc thể đã chọn C1 và C2 là t1(ai) và t2(ai). Hàm thích nghi của 2 nhiễm sắc thể đã chọn C1 và C2 là F1 và F2 . Ngưỡng tương tự khởi tạo thứ i là tc(ai) của nhiễm sắc thể mới Cc được tạo ra bằng phép toán lai ghép được tính bằng một số trung bình: t c  ai   F1 t1  ai   F2 t 2  ai  F1  F2 Phép toán này được áp dụng cho toàn bộ những ngưỡng tương tự khởi tạo của hai nhiễm sắc thể đã chọn với xác suất lai ghép Pc. 2.5.3 Phép đột biến 5 Đột biến được thực hiện như sau: Đầu tiên, một nhiễm sắc thể C’ được chọn ngẫu nhiên từ quần thể với xác suất của sự đột biến Pm. Tiếp theo, giá trị ngưỡng tương tự khởi tạo t’(ai) của nhiễm sắc thể C’ được chọn ngẫu nhiên và nó được đột biến theo cách sau: tm(ai) = 1.5 - t’(ai) Với t’(ai) và tm(ai) tương ứng là giá trị ngưỡng tương tự khởi tạo đã chọn và ngưỡng tương tự khởi tạo đột biến. Sự thực hiện liên tiếp của phép toán lai ghép và đột biến hoàn thành phép toán di truyền và nó tạo ra nhiễm sắc thể mới Cc+m. Dưới đây là tóm tắt việc xác định giá trị tương tự khởi tạo tối ưu bằng cách sử dụng thuật toán di truyền. Thuật toán: (Đầu vào: A=(U, Ad), Sa: Va x Va  [0,1] aA; Đầu ra: {t{t(a): aA}}) 1. Khởi tạo 4 5 - Đọc thông tin từ bảng. - Xác định độ đo tương tự. Crossover Mutation 18 - Phát sinh quần thể khởi tạo: ngưỡng tương tự khởi tạo nằm trong khoảng [0,1]. - Đánh giá hàm thích nghi của quần thể khởi tạo. 2. Thực hiện thuật toán di truyền while (stop_condition) { Reproduction(); Crossover(); Mutation(); Đánh giá hàm thích nghi của quần thể mới; (Evalute fitness function of new population) 1  A , d   1   1    A , d  } 3. Xác định ngưỡng tối ưu 19 Chương 3 PHÂN LOẠI DỮ LIỆU DỰA TRÊN TẬP THÔ TOLERANT Cho rằng, đó là một tập của những mẫu huấn luyện được chuẩn bị cho việc phân loại dữ liệu. Chúng ta xác định tối ưu các giá trị của các ngưỡng tương tự khởi tạo bằng phương pháp tiến hoá dựa trên thuật toán di truyền sử dụng tập của những mẫu huấn luyện. Sau khi xác định những ngưỡng tương tự khởi tạo tối ưu, chúng ta cần phải thu được tập xấp xỉ dưới và tập xấp xỉ trên của các mẫu huấn luyện. Một thủ tục xác định hai tập xấp xỉ được đưa ra như sau: Sử dụng các ngưỡng khởi tạo ta có được một tập tolerant TS(x) của mỗi mẫu x trong tập huấn luyện. Tiếp theo, Ta thu được tập xấp xỉ dưới  A  x  và tập xấp xỉ trên  A  x  của mỗi mẫu x trong các mẫu huấn luyện. Các tập  A  x  và  A  x  của mỗi đối tượng trong các mẫu huấn luyện có được bằng cách sử dụng các tập tolerat tương ứng. Một mẫu x sẽ thuộc vào tập xấp xỉ dưới hoặc tập xấp xỉ trên cho dù tất cả các mẫu trong tập tolerant TS(x) của mẫu x có cùng một lớp hay không. Khi một mẫu x thuộc vào tập xấp xỉ dưới, các mẫu khác trong tập tolerant TS(x) của mẫu x có thể có các lớp quyết định khác nhau từ những mẫu khác. Như vậy, chúng ta cần một kỹ thuật để đo lường sự không chắc chắn của lớp bao phủ của một mẫu x. Cho một lớp quyết định của một đối tượng y trong tập tolerant TS(x) là d(y) và lớp quyết định thứ i là di (i=1, 2, …, r(d)), với r(d) là số các lớp quyết định. Chúng ta cần xác định một hàm thành viên thô di(x) biểu diễn mức độ phổ biến của mẫu x trong lớp quyết định di như sau:  di  x   card  y  TS  x  | d  y  d  i   card TS  x   Chúng ta đưa ra một phương pháp phân loại hai giai đoạn dựa trên tập xấp xỉ dưới và tập xấp xỉ trên được trích từ tập các mẫu huấn luyện . Về cơ bản, phương pháp được thực hiện theo một cách đó là các mẫu thử sẽ được phân loại bằng cách sử dụng tập xấp xỉ dưới ở giai đoạn đầu và sau đó những mẫu thử này không thể 20