Tài liệu Luận văn cntt phƣơng pháp phân cụm dựa trên tập thô và giải thuật di truyền

  • Số trang: 42 |
  • Loại file: PDF |
  • Lượt xem: 145 |
  • Lượt tải: 0

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG HUYỀN TRANG PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN TẬP THÔ VÀ GIẢI THUẬT DI TRUYỀN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - 2016 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG HUYỀN TRANG PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN TẬP THÔ VÀ GIẢI THUẬT DI TRUYỀN Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. HOÀNG XUÂN HUẤN Hà Nội - 2016 2 LỜI CẢM ƠN Tôi xin gửi lời biết ơn sâu sắc đến ngƣời thầy PGS,TS Hoàng Xuân Huấn, những thầy cô trƣờng Đại học Công nghệ đã dành rất nhiều thời gian và tâm huyết giảng dạy, hƣớng dẫn khoa học; giúp tôi nâng cao, mở rộng kiến thức, phát triển năng lực nghiên cứu khoa học, vận dụng thiết thực vào lĩnh vực hệ thống thông tin, hoàn thành tốt luận văn tốt nghiệp này; Trân trọng cảm ơn tới lãnh đạo đơn vị, đồng nghiệp nơi tôi công tác đã tạo điều kiện thuận lợi cho tôi hoàn thành khóa đào tạo; Xin biết ơn, yêu quý gia đình, ngƣời thân đã luôn đồng hành vƣợt khó trong cuộc sống, công tác và học tập. Tôi xin chân thành cảm ơn! Học viên Hoàng Huyền Trang 3 LỜI CAM ĐOAN Tôi xin cam đoan kết quả đạt đƣợc trong luận văn là sản phẩm của cá nhân tôi, thực hiện dƣới sự hƣớng dẫn của PGS, TS Hoàng Xuân Huấn. Toàn bộ nội dung của luận văn, những điều đƣợc trình bày là của cá nhân hoặc đƣợc tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và đƣợc trích dẫn đúng quy định. Tôi xin hoàn toàn chịu trách nhiệm về lời cam đoan của mình. Hà Nội, tháng 11 năm 2016 Học viên Hoàng Huyền Trang 4 MỤC LỤC LỜI CẢM ƠN ....................................................................................................... 2 LỜI CAM ĐOAN.................................................................................................. 3 MỤC LỤC ............................................................................................................. 4 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ........................................... 6 DANH MỤC CÁC HÌNH VẼ............................................................................... 7 DANH MỤC CÁC BẢNG BIỂU ......................................................................... 8 MỞ ĐẦU ............................................................................................................... 9 CHƢƠNG I. PHÂN CỤM DỮ LIỆU VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN ... 10 1.1. Giới thiệu về phân cụm dữ liệu ................................................................. 10 1.1.1. Khái niệm và mục đích của phân cụm dữ liệu.................................... 10 1.1.2. Phƣơng pháp phân cụm dữ liệu .......................................................... 11 1.1.3. Phân cụm với giải thuật K-Means ...................................................... 12 1.2. Lý thuyết tập thô ....................................................................................... 14 1.2.1. Hệ thông tin và quyết định .................................................................. 14 1.2.2. Quan hệ bất khả phân biệt................................................................... 16 1.2.3. Xấp xỉ tập hợp ..................................................................................... 17 1.2.4. Thuộc tính thiết yếu và không thiết yếu ............................................. 18 1.3. Giải thuật di truyền ................................................................................... 19 1.3.1. Thông tin ............................................................................................. 19 1.3.2. Các thành phần cơ bản trong giải thuật di truyền ............................... 19 1.3.3. Quy trình thuật toán di truyền ............................................................. 23 1.3.4. Các thông số cơ bản của giải thuật di truyền ...................................... 25 CHƢƠNG II. PHÂN CỤM DỮ LIỆU DỰA TRÊN TẬP THÔ VÀ GIẢI THUẬT DI TRUYỀN ......................................................................................... 26 2.1. Giới thiệu................................................................................................... 26 2.2. Phƣơng pháp phân cụm tập thô................................................................. 26 2.3. Phƣơng pháp phân cụm dựa trên giải thuật di truyền ............................... 31 2.4. Phƣơng pháp phân cụm dựa trên tập thô và giải thuật di truyền .............. 33 CHƢƠNG III. CÀI ĐẶT VÀ PHÂN TÍCH THÍ NGHIỆM .............................. 35 5 3.1. Dữ liệu thử nghiệm ................................................................................... 35 3.2. Cài đặt thuật toán ...................................................................................... 35 3.3. Kết quả thử nghiệm ................................................................................... 37 KẾT LUẬN ......................................................................................................... 39 TÀI LIỆU THAM KHẢO ................................................................................... 40 6 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Chữ viết tắt GA NST Tiếng Anh Genetic Algorithm Nghĩa Tiếng Việt Giải thuật di truyền Nhiễm sắc thể 7 DANH MỤC CÁC HÌNH VẼ Hình 1.1. Quy trình phân cụm. Hình 1.2. Mô phỏng sự phân cụm dữ liệu. Hình 1.3. Mô tả phân cụm cứng/rõ và phân cụm mềm/mờ Hình 1.4. Sơ đồ thuật toán phân cụm K-Means. Hình 1.5. Mô tả quá trình phân cụm K-Means. Hình 1.6. Mô tả bộ xấp xỉ trên - dƣới. Hình 1.7. Sơ đồ giải thuật di truyền. Hình 2.1. Mô tả khoảng cách giữa đối tƣợng tới trung tâm cụm. Hình 2.2. Mô tả gom cụm vào bộ xấp xỉ trên - dƣới. Hình 2.3. Sơ đồ phân cụm K-Means thô. Hình 3.1. Giao diện chƣơng trình. Hình 3.2. Giao diện nhập dữ liệu và các thuộc tính. Hình 3.3. Giao diện hiển thị file dữ liệu. Hình 3.4. Giao diện kết quả thuật toán. 8 DANH MỤC CÁC BẢNG BIỂU Bảng 1.1. Hệ thống thông tin. Bảng 1.2. Bảng quyết định. Bảng 1.3. Các triệu chứng cảm cúm. Bảng 2.1. So sánh về hai giải thuật K-Means, di truyền. Bảng 3.1. Kết quả thực nghiệm với phân cụm K-Means thông thƣờng. Bảng 3.2. Kết quả thực nghiệm với phân cụm dựa trên tập thô và giải thuật di truyền. 9 MỞ ĐẦU Phân cụm dữ liệu là một trong những nghiên cứu quan trọng trong khai thác dữ liệu và đƣợc áp dụng cho đa lĩnh vực [7,8]. Mục tiêu chính trong phân cụm dữ liệu là để phân loại các đối tƣợng không có nhãn thành nhiều cụm mà các đối tƣợng thuộc cùng một cụm thì tƣơng tự nhau và khác nhau đối với các cụm khác nhau. Phân cụm dữ liệu đƣợc chia làm hai loại là phân cụm dữ liệu cứng/rõ (mỗi điểm dữ liệu chỉ thuộc về một cụm) và phân cụm dữ liệu mềm/mờ (mỗi điểm dữ liệu có thể thuộc về nhiều hơn một cụm dựa vào một xác suất nhất định) [12,15]. Một kỹ thuật đƣợc sử dụng phổ biến trong phân cụm dữ liệu là thuật toán KMeans, thuộc phân cụm rõ, với sự hội tụ nhanh chóng và khả năng tìm kiếm địa phƣơng mạnh mẽ. Trong quá trình phân cụm K-Means truyền thống, các đối tƣợng dữ liệu thu đƣợc trong cụm là nhất định. Tuy nhiên, trong thực tế giữa những đối tƣợng thuộc các lớp khác nhau thƣờng không có ranh giới rõ ràng, do đó việc mô tả bộ dữ liệu thực là khó khăn. Giải pháp cho những đối tƣợng này đƣợc cung cấp bởi lý thuyết tập thô, là phƣơng pháp tính toán mềm trong khai thác dữ liệu. Để tăng hiệu quả và kết quả chính xác cho phân cụm việc sử dụng lý thuyết tập thô tiếp cận hỗ trợ phân cụm K-Means đã đƣợc đề xuất, xây dựng nên phƣơng pháp phân cụm K-Means thô. Mặc dù giải thuật K-Means thô có khả năng tìm kiếm địa phƣơng mạnh mẽ nhƣng lại dễ rơi vào cực trị địa phƣơng. Một trong những biện pháp có thể khắc phục đƣợc hạn chế này là kết hợp với giải thuật di truyền. Thuật toán di truyền là một thuật toán tìm kiếm ngẫu nhiên với kỹ thuật tối ƣu toàn cầu dựa trên nguyên tắc của sự tiến hóa sinh học, có lƣợng lớn số song song tiềm ẩn thực hiện không gian tìm kiếm lớn và cung cấp giải pháp tối ƣu hóa toàn cầu giúp tránh đƣợc tối ƣu địa phƣơng. Luận văn trình bày khảo cứu một cách hệ thống của bài báo [6] các kiến thức về phân cụm dữ liệu rõ, thô theo hƣớng K-Means và ứng dụng giải thuật di truyền để phân cụm dữ liệu thô. Trên cơ sở đó xây dựng chƣơng trình thực nghiệm trên một số bộ dữ liệu, kết quả cho thấy ƣu điểm của phƣơng pháp mới. Thông qua các quy định phù hợp và áp dụng lợi thế của thuật toán, tính chính xác cụm đƣợc cải thiện. Kết quả thực nghiệm cho thấy các thuật toán đƣợc đề xuất có khả năng điều chỉnh các kết quả và có đƣợc độ chính xác cao hơn. Cấu trúc của luận văn gồm 3 chƣơng : Chƣơng I. Phân cụm dữ liệu và một số vấn đề liên quan. Chƣơng II. Phân cụm dựa trên tập thô và thuật toán di truyền. Chƣơng III. Cài đặt và phân tích thí nghiệm. 10 CHƢƠNG I. PHÂN CỤM DỮ LIỆU VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN 1.1. Giới thiệu về phân cụm dữ liệu Khai phá dữ liệu là giai đoạn quan trọng trong quá trình khám phá tri thức, hƣớng nghiên cứu thu hút đƣợc nhiều sự quan tâm của các chuyên gia công nghệ thông tin trong và ngoài nƣớc. Về bản chất là giai đoạn duy nhất tìm ra đƣợc thông tin mới, thông tin tiềm ẩn có trong cơ sở dữ liệu chủ yếu phục vụ cho mô tả và dự đoán. Trong những năm gần đây liên tục có những phƣơng pháp, giải thuật đƣợc công bố cho thấy ƣu thế, lợi ích và khả năng ứng dụng to lớn của khai phá dữ liệu. Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu với mục đích chính là khám phá cấu trúc của mẫu dữ liệu để thành lập các nhóm dữ liệu từ tập dữ liệu lớn, cho phép con ngƣời đi sâu vào phân tích và nghiên cứu cho từng cụm dữ liệu nhằm khám phá và tìm kiếm các thông tin tiềm ẩn, hữu ích phục vụ cho việc ra quyết định. 1.1.1. Khái niệm và mục đích của phân cụm dữ liệu Bài toán phân cụm dữ liệu là một nhánh ứng dụng chính của lĩnh vực học không giám sát, mà dữ liệu mô tả trong bài toán là không đƣợc dán nhãn. Trong trƣờng hợp này, thuật toán sẽ tìm cách phân cụm dữ liệu thành từng nhóm có đặc điểm tƣơng tự nhau, nhƣng đồng thời đặc tính giữa các nhóm đó lại phải càng khác biệt càng tốt. Số các cụm dữ liệu có thể đƣợc xác định trƣớc theo kinh nghiệm hoặc có thể đƣợc tự động xác định theo thuật toán. Hình 1.1. Quy trình phân cụm. Độ tƣơng tự đƣợc xác định dựa trên giá trị các thuộc tính mô tả đối tƣợng. Thông thƣờng, phép đo khoảng cách thƣờng đƣợc sử dụng để đánh giá độ tƣơng tự hay phi tƣơng tự. Vấn đề phân cụm có thể minh hoạ nhƣ hình 1,2: Hình 1.2. Mô phỏng sự phân cụm dữ liệu. 11 Hiện nay chƣa có phƣơng pháp phân cụm tổng quát nào giải quyết đƣợc tất cả các dạng cấu trúc cụm dữ liệu. Hơn nữa, với mỗi cách thức biểu diễn cấu trúc của các cụm dữ liệu khác nhau sẽ có tƣơng ứng một thuật toán phân cụm phù hợp. Vì vậy đối với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị dữ liệu, phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu. Ứng dụng của phân cụm dữ liệu Phân cụm dữ liệu đƣợc áp dụng trong rất nhiều lĩnh vực nhƣ: - Kinh doanh: Xác định các nhóm khách hàng (khách hàng tiềm năng, khách hàng giá trị, phân loại và dự đoán hành vi khách hàng,…) sử dụng sản phẩm hay dịch vụ của công ty để giúp công ty có chiến lƣợc kinh doanh hiệu quả hơn; - Sinh học: Phân nhóm động vật và thực vật dựa vào các thuộc tính của chúng; - Thƣ viện: Theo dõi độc giả, sách, dự đoán nhu cầu của độc giả…; - Bảo hiểm: Phân nhóm các đối tƣợng sử dụng bảo hiểm và các dịch vụ tài chính, dự đoán xu hƣớng (trend) của khách hàng, phát hiện gian lận tài chính (identifying frauds); - www: Phân loại tài liệu (document classification); phân loại ngƣời dùng web (clustering weblog);… 1.1.2. Phƣơng pháp phân cụm dữ liệu Phân cụm dữ liệu đƣợc chia làm hai loại là phân cụm dữ liệu cứng và phân cụm dữ liệu mềm:  Phân cụm dữ liệu cứng (hay phân cụm rõ) là phƣơng pháp gán mỗi đối tƣợng vào một và chỉ một cụm và xác định rõ ranh giới giữa các cụm. Một số thuật toán: Thuật toán K-Means, Thuật toán K-Medoids...  Phân cụm dữ liệu mềm (hay phân cụm mờ) là phƣơng pháp cho phép mỗi đối tƣợng có thể thuộc một hoặc nhiều cụm dữ liệu và có sự mơ hồ hoặc mờ ranh giới giữa các cụm: Thuật toán Fuzzy C-mean… 12 Hình 1.3. Mô tả phân cụm cứng/rõ và phân cụm mềm/mờ Tùy theo đặc điểm về tính tƣơng đồng của các đối tƣợng trong bài toán đang xét, có nhiều cách tiếp cận cho thuật toán phân cụm. Các kỹ thuật gồm: - Phân cụm phân cấp (Hierarchical Data Clustering) còn đƣợc gọi là phƣơng pháp phân cụm cây, trong đó sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình cây, cây phân cấp này đƣợc xây dựng theo kỹ thuật đệ quy; Các thuật toán trộn (phƣơng pháp dƣới lên-Bottum up) và phƣơng pháp tách (phƣơng pháp trên xuống – Top down). - Phân cụm phân hoạch (Partition Based Data Clustering) là phƣơng pháp phân cụm đang đƣợc dùng phổ biến nhất, đặc biệt cho các tập dữ liệu lớn với số cụm k đƣợc xác định trƣớc; Các thuật toán là K-Means, K-centroid… - Phân cụm dựa trên mật độ (Density Based Data Clustering): DBSCAN… - Phân cụm dựa trên lƣới (Grid Based Data Clustering): STING… 1.1.3. Phân cụm với giải thuật K-Means Thuật toán K-Means (MacQueen, 1967)[2] là một trong những thuật toán học không giám sát đơn giản nhất để giải quyết vấn đề phân cụm dữ liệu nổi tiếng, với số cụm đƣợc xác định trƣớc là k cụm. Thuộc nhóm phân cụm dữ liệu cứng/rõ, ý tƣởng chính là để xác định k trọng tâm cho k cụm, một trọng tâm cho mỗi cụm. Những trọng tâm nên đƣợc đặt ở vị trí thích hợp nhất vì vị trí khác nhau gây ra kết quả khác nhau. Vì vậy, sự lựa chọn tốt hơn là đặt chúng càng nhiều càng tốt và cách xa nhau. Bƣớc tiếp theo là với mỗi điểm thuộc tập dữ liệu cho trƣớc và liên kết nó với trọng tâm gần nhất. Giả sử thiết lập tập đối tƣợng X={x1,x2,…xn} và k trọng tâm cụm C={C1,C2,…Ck}; lấy w1,w2,…wk của k cụm. Công thức C j  1 Nj x với j=1, 2, …, jk trong đó Nj là số lƣợng cụm thứ j xw j k Xác định hàm mục tiêu nhƣ sau: E    d ( x, ci ) trong đó ci là tâm của cụm i 1 xw i wi tƣơng ứng. 13 Với d(x,ci)= x  ci 2 là khoảng cách Euclide từ điểm đối tƣợng của mỗi cụm đến các trung tâm cụm. Thuật toán K-Means: Đầu tiên, chọn ngẫu nhiên k trọng tâm cụm từ tập đối tƣợng. Tùy theo khoảng cách mỗi đối tƣợng đến các trọng tâm, nó sẽ đƣợc phân vào các cụm gần nhất, sau đó tính toán giá trị trung bình cho mỗi cụm. Quá trình này đƣợc lặp đi lặp lại cho đến khi sự hội tụ của hàm chuẩn. Quá trình phân cụm K-Means đƣợc biểu diễn bởi hình 1.4. Đầu vào: k: số cụm X: tập dữ liệu chứa n đối tƣợng Đầu ra: một tập hợp k các cụm Bƣớc 0. Xác định số lƣợng cụm k và điều kiện dừng Bƣớc 1. Khởi tạo ngẫu nhiên k trọng tâm cụm {C1,C2,…Ck} Bƣớc 2. Gom các đối tƣợng vào cụm mà nó gần tâm nhất Bƣớc 3. Tính lại các tâm theo đối tƣợng đã đƣợc phân hoạch ở bƣớc 2 Lặp cho đến khi điều kiện dừng thỏa mãn. Điều kiện dừng thƣờng chọn các điều kiện sau: • Số lần lăp t=Tmax trong đó Tmax là số cho trƣớc • |Et – Et-1|<∆ trong đó ∆ là hằng số bé cho trƣớc • Tới khi các cụm không đổi Khi tập dữ liệu không quá lớn thì ngƣời ta dùng điều kiện dừng thứ 3. Bắt đầu Input: k số cụm; tập đối tƣợng; Yes Sự thay đổi thành viên cụm? No Xác định các trọng tâm cụm Tính khoảng cách giữa các đối tƣợng đến k tâm Nhóm các đối tƣợng vào cụm gần nhất Hình 1.4. Sơ đồ thuật toán phân cụm K-means Kết thúc 14 Hình 1.5. Mô phỏng quá trình phân cụm K-Means Ví dụ quá trình phân cụm K-Means từ hình 1.5: (1) Khởi tạo ngẫu nhiên trọng tâm cho mỗi cụm; ở đây là C1,C2,C3 (2) Gán mỗi đối tƣợng có khoảng cách gần nhất với trọng tâm vào một cụm; (3) Xác định lại trọng tâm mới bằng cách tính toán giá trị trung bình của các đối tƣợng trong mỗi cụm; (4) Lặp đến khi trọng tâm cụm không đổi. 1.2. Lý thuyết tập thô Lý thuyết tập thô (Rough Set Theory - RST) đƣợc phát triển bởi Zdzislaw Pawlak, là phần mở rộng của lý thuyết tập hợp cho việc nghiên cứu hệ thống thông minh đặc trƣng bởi các thông tin không chính xác, không chắc chắn và không đầy đủ, chủ yếu dùng phân tích phân loại bảng dữ liệu. Mục đích chính của việc phân tích tập thô là tổng hợp khái niệm xấp xỉ từ các dữ liệu thu đƣợc, trong đó có sự mơ hồ, thiếu giá trị hoặc dự phòng của các thuộc tính. Trong phần này, một số thuật ngữ đƣợc sử dụng thƣờng xuyên trong tập thô đƣợc xác định. 1.2.1. Hệ thông tin và quyết định Một tập hợp dữ liệu đƣợc biểu diễn nhƣ một bảng trong đó mỗi hàng đại diện cho một trƣờng hợp, một sự kiện, một mô hình hay đơn giản là một đối tƣợng. Mỗi cột đại diện cho một thuộc tính của từng đối tƣợng; các thuộc tính cũng có thể đƣợc cung cấp bởi một chuyên gia hay ngƣời sử dụng. Bảng này đƣợc gọi là hệ thông tin. 15 Hình thức hơn, hệ thông tin là một cặp I=(U,A) với U là tập hữu hạn đối tƣợng khác rỗng đƣợc gọi là miền và A là một tập hữu hạn các thuộc tính khác rỗng. Với mỗi a  A, a : U  Va tập Va là tập giá trị của thuộc tính a. Ví dụ [1] Bảng 1.1, Một hệ thông tin bao gồm 8 đối tƣợng: U={u1,u2,u3,u4,u5,u6,u7,u8} Tập thuộc tính A={Color, Size } và miền giá trị cho từng thuộc tính là Vcolor = {Green, Yellow, Red}, VSize = {Small, Medium, Big }. 1 2 3 4 5 6 7 8 Bảng 1.1. Hệ thống thông tin Color Size Green Big Green Small Yellow Medium Red Medium Yellow Medium Green Big Red Small Red Small Bảng quyết định là dạng đặc biệt của hệ thông tin, kí hiệu S=(U,A) hay S  (U , C  D) với tập thuộc tính A đƣợc phân thành hai tập rời nhau C và D, trong đó C là tập các thuộc tính điều kiện, D là tập các thuộc tính quyết định sao cho C  D   Định nghĩa 1.[6] Bảng quyết định S  (U , C, D,V , f ) Trong đó: - U  x1 , x 2 , x n  là tập hữu hạn đối tƣợng khác rỗng, đƣợc gọi là miền; - A Tập hữu hạn thuộc tính khác rỗng: A  C  D và C  D   với C là một tập thuộc tính điều kiện, D là tập thuộc tính quyết định Va với Va là tập giá trị của thuộc tính a - V  a C D - f : UC  D V là hàm thông tin sao cho f  x, a  Va với a  C  D, x U Ví dụ [1] Bảng quyết định 1.2, bảng này có 8 đối tƣợng nhƣ trong bảng 1.1 nhƣng có thêm thuộc tính quyết định (Shape). Trong bài toán phân lớp thì thuộc tính quyết định chính là lớp của đối tƣợng cần xếp lớp. Trong ví dụ này thuộc tính quyết định Shape có 3 giá trị là Circle, square và Triangle 1 2 3 4 5 6 7 8 16 Bảng 1.2. Bảng quyết định Color Size Shape[D] Green Big Circle Green Small Circle Yellow Medium Square Red Medium Square Yellow Medium Triangle Green Big Circle Red Small Triangle Red Small Triangle Một bảng quyết định là phù hợp nếu cho mỗi bộ đối tƣợng thuộc tính giá trị là nhƣ nhau, các thuộc tính quyết định tƣơng ứng cũng giống hệt nhau. 1.2.2. Quan hệ bất khả phân biệt Một hệ quyết định (hay bảng quyết định) đại diện cho kiến thức về đối tƣợng. Tồn tại hai khả năng dƣ thừa thông tin: Các đối tƣợng giống nhau, không phân biệt đƣợc lặp lại nhiều lần hoặc thậm chí một số các thuộc tính có thể là dƣ thừa. Quan hệ hai ngôi R  X  X là tƣơng đƣơng khi: - R có tính phản xạ : xRx , với mọi x  X - R có tính đối xứng: xRy  yRx, với mọi x, y  X - R có tính bắc cầu: xRy và yRz  xRz, với mọi x, y, z  X Một quan hệ tƣơng đƣơng R phân hoạch tập đối tƣợng thành các lớp tƣơng đƣơng. Lớp tƣơng đƣơng của một đối tƣợng x  X là tập tất cả các đối tƣợng y  X có quan hệ R với x: khí hiệu xRy Với mỗi tập con thuộc tính B   C  D  tạo ra quan hệ tƣơng đƣơng kí hiệu : IND  B    x, y  U  U | a  B, f  x, a   f  y, a  IND(B) đƣợc gọi là B_quan hệ bất khả phân, nếu  x, y   IND( B) thì x,y không thể phân biệt đƣợc với nhau qua tập thuộc tính B. Ngƣợc lại là phân biệt đƣợc với B. Với mọi x U lớp tƣơng đƣơng của x trong quan hệ IND(B) đƣợc ký hiệu bởi [x]B. Quan hệ IND(B) phân hoạch tập đối tƣợng U thành các lớp tƣơng đƣơng đƣợc ký hiệu U/IND(B) hay U/B U / IND( B)  U / B   x B | x  U 17 Trong hệ quyết định, nếu x, y  D , a  C , f  x, a   f  y, a  tồn tại f  x, D   f  y, D  thì (x,y) là nhất quán, ngƣợc lại là không nhất quán. Ví dụ [1].Tập thuộc tính B= {Color, Size} trong Bảng 1.2 phân hoạch tập 8 đối tƣợng thành các lớp nhƣ sau (u1,u6),(u2),(u3,u5),(u4),(u7,u8) Nhận xét: Ta thấy, các đối tƣợng u1và u6, u7 và u8 cùng một lớp tƣơng đƣơng nên chúng không thể phân biệt với nhau trên tập thuộc tính {Color, Size}. 1.2.3. Xấp xỉ tập hợp Trong lý thuyết tập thô, các khái niệm không rõ ràng đƣợc thay bằng cặp khái niệm xấp xỉ gọi là xấp xỉ dƣới (lower approximation) và xấp xỉ trên (upper approximation). Xấp xỉ dƣới bao gồm tất cả các đối tƣợng chắc chắn thuộc về khái niệm, xấp xỉ trên bao gồm tất cả các đối tƣợng có thể thuộc về khái niệm. Định nghĩa 2.[6] Cho một bảng quyết định S  (U , C, D,V , f ) B  C, X  U với U / B   x B | x  U  B1 , B2 , Bt  thì : B  X    x | [x]B  X    Bi | Bi U / B, Bi  X  là B_xấp xỉ dƣới của X B  X    x | [x]B  X     Bi | Bi U / B, Bi  X   là B_xấp xỉ trên của X Tập BN B  X   B ( X )  B( X ) đƣợc gọi là B_vùng biên của X chứa các đối tƣợng không thể xác định đƣợc có thuộc X hay không. Nếu BN B  X    (tức B( X )  B ( X ) ) thì X đƣợc gọi là tập rõ (crisp), trái lại X đƣợc gọi là tập thô (rough) Hình 1.6. Mô tả bộ xấp xỉ trên-dưới Định nghĩa 3. Cho một bảng quyết định S  (U , C, D,V , f ) B  C, X  U với U / B   x B | x  U  B1 , B2 , Bt  Tập POS B  X   B( X ) gọi là B_miền dƣơng (positive region) của X NEGB  X   U  B  X  gọi là B_miền âm (negative region) của X (hay gọi là miền ngoài chứa những đối tƣợng mà sử dụng thuộc tính trong B chắc chắn không thuộc tập X) 18 Bảng 1.3. Các triệu chứng cảm cúm U u1 u2 u3 u4 u5 u6 u7 u8 Đau đầu Có Có Có Không Không Không Không Không Thân nhiệt Bình thƣờng Cao Rất cao Bình thƣờng Cao Rất cao Cao Rất cao Cảm cúm Không Có Có Không Không Có Có Không Ví dụ [1] Bảng 1.3, B={Đau đầu, Thân Nhiệt} ta có các lớp không phân biệt đƣợc là {u1},{u2},{u3},{u4},{u5,u7},{u6,u8} Nếu đặt X={u|u(Cảm cúm)=Có}={u2,u3,u6,u7}, lúc đó ta có: B  X  = {u2,u3} và B  X  = {u2,u3,u5,u7,u6,u8}. Từ đó ta có B-miền biên của X là tập : BN B  X   B ( X )  B( X ) ={ u5,u6,u7,u8}. 1.2.4. Thuộc tính thiết yếu và không thiết yếu Định nghĩa 4.[6] Cho một bảng quyết định S  (U , C, D,V , f ) , b  B  C Nếu POSB  D   POSBb  D  thì b là không thiết yếu (not necessary) trong B đối với D; Ngƣợc lại, thì b là thiết yếu trong B đối với D Cho B  C nếu mọi phần tử trong B đối với D là thiết yếu, thì B đối với D là độc lập. Bảng 1.4. Bảng quyết định về bệnh cúm U Đau đầu Đau cơ Thân nhiệt Cảm cúm u1 Có Có Bình thƣờng Không u2 Có Có Cao Có u3 Có Có Rất cao Có u4 Không Có Bình thƣờng Không u5 Không Không Cao Không u6 Không Có Rất cao Có Bảng 1.4 có 2 tập rút gọn là {Đau đầu, Thân nhiệt} và {Đau cơ, Thân nhiệt}. Tập lõi {Thân nhiệt}. Vậy Thân nhiệt là thuộc tính thiết yếu duy nhất, các thuộc tính Đau đầu, Đau cơ đều không cần thiết. Điều này có nghĩa rằng có thể loại bỏ 19 một trong hai thuộc tính Đau đầu hoặc Đau cơ (không thể bỏ đồng thời cả 2) mà không ảnh hƣởng đến kết quả chuẩn đoán bệnh. 1.3. Giải thuật di truyền Giải thuật di truyền cung cấp cách tiếp cận dựa vào mô phỏng sự tiến hóa. Các giả thuyết thƣờng đƣợc mô tả bằng các chuỗi bit, hoặc bằng các biểu thức ký hiệu, có khi ngay cả các chƣơng trình máy tính. Giải thuật di truyền đã đƣợc ứng dụng thành công vào các lĩnh vực khác nhau và việc tối ƣu hóa khác. Việc kết hợp giải thuật di truyền sẽ giúp quá trình phân cụm tối ƣu hơn. 1.3.1. Thông tin Giải thuật di truyền (Genetic Algorithm – GA), do John Holland (1975) và Goldberg (1989) đề xuất và phát triển. Ý tƣởng của giải thuật di truyền là mô phỏng theo cơ chế của quá trình tiến hóa trong tự nhiên. Từ tập các lời giải ban đầu, thông qua nhiều bƣớc tiến hóa để hình thành các tập mới với những lời giải tốt hơn, cuối cùng sẽ tìm đƣợc lời giải gần tối ƣu nhất. GA sử dụng các thuật ngữ lấy từ di truyền học: - Lớp hay quần thể (Population) là một tập hợp các lời giải - Một nhiễm sắc thể (NST) hay cá thể (Chromosome) biểu diễn cho mỗi lời giải - NST đƣợc tạo thành từ các Gen Quá trình tiến hóa đƣợc thực hiện trên một quần thể nhƣ là sự tìm kiếm các lời giải có thể của bài toán. Nó đòi hỏi sự cân bằng giữa hai mục tiêu chính là khai thác lời giải tốt nhất và tra xét toàn bộ không gian tìm kiếm. GA thực hiện tìm kiếm theo nhiều hƣớng: duy trì tập hợp các lời giải có thể và khuyến khích sự hình thành trao đổi thông tin giữa các hƣớng. Tập lời giải cần trải qua nhiều bƣớc tiến hoá, một tập mới các cá thể đƣợc tạo ra tại mỗi thế hệ có chứa các cá thể thích nghi nhất trong thế hệ cũ. Đồng thời khai thác có hiệu quả thông tin trƣớc đó để suy xét trên điểm tìm kiếm mới với mong muốn có đƣợc sự cải thiện qua từng thế hệ. 1.3.2. Các thành phần cơ bản trong giải thuật di truyền 1.3.2.1. Mã hóa nhiễm sắc thể Trong giải thuật di truyền, cách mã hóa nhiễm sắc thể (The coding of chromosome) quyết định đến hiệu quả của giải thuật và ảnh hƣởng đến việc lựa chọn các toán tử trong các bƣớc lai ghép và đột biến. Với mỗi kiểu bài toán khác nhau có nhiều cách mã hóa nhiễm sắc thể. Cách mã hoá nhiễm sắc thể là một
- Xem thêm -